Given a Gröbner Basis G for an ideal J over a polynomial ring R, the remainder of any polynomial p ∈ R with respect to G is unique. Although this remainder is unique, there may be many ways of finding it, as it is possible that several polynomials in G divide p, each giving a reduction path for p.
Consider the DegLex Gröbner basis G := {g_1, g_2, g_3} = {a^2-2ab+3, : 2ab+b^2+5, : frac54b^3-frac52a+frac374b} over the polynomial ring Q[a,b], and consider the polynomial p := a^2b+b^3+8b. The remainder of p with respect to G is 0 (so that p is a member of the ideal J generated by G), but there are two ways of obtaining this remainder, as shown in the following diagram.
\vcenter{\xymatrix{ & a^2b+b^3+8b \ar[dl]_{g_1} \ar[dr]^{g_2} \\ 2ab^2+b^3+5b \ar[d]_{g_2} && -\frac{1}{2}ab^2 + b^3 - \frac{5}{2}a+8b \ar[d]^{g_2} \\ 0 && \frac{5}{4}b^3-\frac{5}{2}a+\frac{37}{4}b \ar[d]^{g_3} \\ && 0 }}
An Involutive Basis for J is a Gröbner Basis G such that there is only one possible reduction path for any polynomial p ∈ R. In order to find such a basis, we restrict which reductions or divisions may take place by requiring, for each potential reduction of a polynomial p by a polynomial g_i ∈ G (so that LM(p) = LM(g_i)× u for some monomial u), some extra conditions on the variables in u to be satisfied, namely that all variables in u have to be in a set of multiplicative variables for g_i, a set that is determined by a particular choice of an involutive division.
Recall that a commutative monomial u is divisible by another monomial w if there exists a third monomial u' such that u = wu'. We use the notation w ∣ u and refer to w as a conventional divisor of u. An involutive division I partitions the variables in the polynomial ring into sets of multiplicative and nonmultiplicative variables for each polynomial. The set of multiplicative variables for w is denoted by M_I(w). Then w is an involutive divisor of u, written w ∣_I u, if all variables in u' are in M_I(w).
Let u := ab^3c, v := abc^3 and w := bc be three monomials over the polynomial ring R := Q[a,b,c]. Let an involutive division I partition the variables in R into the following two sets of variables for the monomial w: multiplicative = {a,b}; nonmultiplicative = {c}. It is true that w conventionally divides both monomials u and v, but w only involutively divides monomial u as, defining u' := ab^2 and v' := ac^2 (so that u = wu' and v = wv'), we observe that all variables in u' are in M_I(w), but the variables in v' (in particular the variable c) are not all in M_I(w). So w ∣_I u and w ∤_I v.
The global variable CommutativeDivision is a string which can take values "Pommaret", "Thomas" or "Janet". The default is "Pommaret". The example shows how to select the Pommaret division.
gap> CommutativeDivision := "Pommaret"; "Pommaret"
These three divisions are defined for a set of monomials, but we shall define a DivisionRecord below for a set of polynomials. The first step is therefore to select the leading monomials from this set, and that will bepend of the ordering chosen. We shall be using the orderings provided by the main GAP library as described in 2.3.
When calling MonomialLexOrdering, MonomialGrlexOrdering etc., it is essential to provide a list of indeterminates, as shown in the example. Otherwise some of the functions in this package will throw an error.
gap> R := PolynomialRing( Rationals, [ "x", "y", "z" ] );; gap> x := R.1;; y := R.2;; z := R.3;; gap> ord := MonomialLexOrdering( [x,y,z] );;
‣ PommaretDivision( alg, mons, order ) | ( operation ) |
Let R = F[a_1,...,a_n] with a_1 > a_2 > ... > a_n, and let w be a polynomial in R with leading monomoial a_1^e_1a_2^e_2 ... a_n^e_n where e_i is the first non-zero exponent. The Pommaret involutive division P sets M_P}(w) = {a_1, a_2, ..., a_i}.
Because M_P}(w) does not depend in any way on the other leading monomials in polys, this is a global division.
In the example the first five monomials u_i in U contain a power of x, so M_P}(u_i) = {x}. Then u_6 involves y and z, so M_P}(u_6) = {x,y}, and similarly M_P}(u_7) = {x,y,z}.
gap> U := [ x^5*y^2*z, x^4*y*z^2, x^2*y^2*z, x*y*z^3, x*z^3, y^2*z, z ]; [ x^5*y^2*z, x^4*y*z^2, x^2*y^2*z, x*y*z^3, x*z^3, y^2*z, z ] gap> PommaretDivision( R, U, ord ); [ [ 1 ], [ 1 ], [ 1 ], [ 1 ], [ 1 ], [ 1, 2 ], [ 1 .. 3 ] ]
‣ ThomasDivision( alg, mons, order ) | ( operation ) |
Let R = F[a_1,...,a_n] with a_1 > a_2 > ... > a_n, and let P be a set of polynomials P = {p_1,...,p_m} in R with leading monomials U = {u_1,...,u_m} where u_i = a_1^e^1_ia_2^e^2_i ... a_n^e^n_i. The Thomas involutive division T sets a_i to be multiplicative for p_j and u_j if e^i_j = max_k e^i_k for all 1 leqslant k leqslant m.
In the example, using the same seven monomials, the highest powers of [x,y,z] are [5,2,3] respectively. So x is multiplicative only for u_1, y is multiplicative for {u_1,u_3,u_6}, and z is multiplicative only for u_4 and u_5. Note that two of the monomials have no multiplicative variable.
gap> ThomasDivision( R, U, ord ); [ [ 1, 2 ], [ ], [ 2 ], [ 3 ], [ 3 ], [ 2 ], [ ] ]
‣ JanetDivision( alg, mons, order ) | ( operation ) |
Let R = F[a_1,...,a_n] with a_1 > a_2 > ... > a_n, and let P be a set of polynomials P = {p_1,...,p_m} in R with leading monomials U = {u_1,...,u_m} where u_i = a_1^e^1_ia_2^e^2_i ... a_n^e^n_i. The Janet involutive division J sets a_n to be multiplicative for u_j provided e^n_j = max_k e^n_k for all 1 leqslant k leqslant m. To determine whether a_i is multiplicative for u_j, let L = [e^i+1_j,e^i+2_j,...,e^n_j]. Let S be the subset of {1,...,m} containing those k such that [e^i+1_k,e^i+2_k,...,e^n_k] = L. Then a_i is multiplicative for u_j provided e^i_j = max_k ∈ Se^i_k.
In the example, recall that the exponent lists for the seven monomials are
[5,2,1],~~~ [4,1,2],~~~ [2,2,1],~~~ [1,1,3],~~~ [1,0,3],~~~ [0,2,1],~~~ [0,0,1].
As with the Thomas division, max_k e^3_k = 3 and z is multiplicative only for u_4 and u_5.
For y, L = [1] when k ∈ {1,3,6,7} and max_{1,3,6,7} e^2_k = 2, so y is multiplicative for u_1, u_3 and u_6, but not for u_7. L = [2] only for u_2, so y is multiplicative for u_2. L = [3] for u_4 and u_5, and e^2_4 > e^2_5, so y is multiplicative for u_4 but not u_5.
For x, L = [2,1] for k ∈ {1,3,6} and e^1_1 = 5 is greater than e^1_3 and e^1_6, so x is multiplicative for u_1. The other values for L, namely [1,2], [1,3], [0,3] and [0,1], occur just once each, so x is multiplicative for u_2, u_4, u_5 and u_7.
gap> JanetDivision( R, U, ord ); [ [ 1, 2 ], [ 1, 2 ], [ 2 ], [ 1, 2, 3 ], [ 1, 3 ], [ 2 ], [ 1 ] ]
‣ DivisionRecord( alg, polys, order ) | ( function ) |
‣ DivisionRecordCP( alg, polys, order ) | ( operation ) |
The global function DivisionRecord calls one of the operations DivisionRecordCP and DivisionRecordNP, depending on whether the algebra is commutative or not. In the commutative case, this function finds the sets of multiplicative variables for a set of polynomials using one of the involutive divisions listed above. The record constructed has three fields: the chosen division; a list of lists of positions of the multiplicative variables; and the set of polynomials.
In the following example, polynomials {u = b^3-3a, v=a^3-3b} define an ideal and form a Gröbner basis for that ideal. Using the Pommaret division, M_P}(u) = {a,b} and M_P}(v) = {a}. The variable drec2.mvars in the listing below contains the positions of these variables in the generating set {a,b}.
gap> R := PolynomialRing( Rationals, [ "a", "b" ] );; gap> a := R.1;; b := R.2;; gap> L2 := [ b^3 - 3*a, a^3 - 3*b ];; gap> ord := MonomialGrlexOrdering( [a,b] );; gap> GB2 := ReducedGroebnerBasis( L2, ord );; gap> GB2 = L2; true gap> CommutativeDivision := "Pommaret";; gap> drec2 := DivisionRecordCP( R, L2, ord ); rec( div := "Pommaret", mvars := [ [ 1, 2 ], [ 1 ] ], polys := [ b^3-3*a, a^3-3*b ] )
In the reduction diagrams below the nodes (j,k) represent the monomials a^jb^k. The lead monomials of u and v are marked by these two names. In the left hand diagram the two shaded areas indicate those monomials which are conventionally reducible by u and by v, so that the doubly shaded area contains those monomials which are conventionally reducible by both. For an involutive division, this must be avoided.
In the right-hand diagram we see that u involutively divides the same set of monomials in the main shaded area. On the other hand v just involutively divides monomials {a^j ∣ j ≥ 3}. So none of the monomials {a^jb, a^jb^2 ∣ j ≥ 3} reduce by v involutively. The operation InvolutiveBasis, to be described below, produces two further polynomials, w = vb = a^3b-3b^2 and vb^2 which reduces by u to x = a^3b^2 - 9a. Both w and x have multiplicative variables {a} and the monomials which they can reduce lie on the two horizantal line segments in the right-hand diagram. In this way, all the conventionally reducible monomials are involutively reducible by just one of {u,v,w,x}.
\vcenter{\xymatrix@=1em{ b & & & \ar@{-}[ddddrrrr] & \ar@{-}[dddrrr] & \ar@{-}[ddrr] & \ar@{-}[dr] & & & & b & & & & & & & \\ : \ar[u] \ar@{-}[ur] & \cdot & \cdot & \cdot \ar@{-}[ddddrrrr] & \cdot & \cdot & \cdot & & & & : \ar[u] \ar@{-}[ur] & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \\ 5 \ar@{-}[u] \ar@{-}[uurr] & \cdot & \cdot & \cdot \ar@{-}[ddddrrrr] & \cdot & \cdot & \cdot & & & & 5 \ar@{-}[u] \ar@{-}[uurr] & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \\ 4 \ar@{-}[u] \ar@{-}[uuurrr] & \cdot & \cdot & \cdot \ar@{-}[ddddrrrr] & \cdot & \cdot & \cdot & & & & 4 \ar@{-}[u] \ar@{-}[uuurrr] & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \\ u \ar@{-}[u] \ar@{-}[rrrrrrr] \ar@{-}[uuuurrrr] & \cdot \ar@{-}[uuuurrrr] & \cdot \ar@{-}[uuuurrrr] & \cdot \ar@{-}[dddrrr] \ar@{-}[uuuurrrr] & \cdot \ar@{-}[uuurrr] & \cdot \ar@{-}[uurr] & \cdot \ar@{-}[ur] & & & & u \ar@{-}[u] \ar@{-}[rrrrrrr] \ar@{-}[uuuurrrr] & \cdot \ar@{-}[uuuurrrr] & \cdot \ar@{-}[uuuurrrr] & \cdot \ar@{-}[uuuurrrr] & \cdot \ar@{-}[uuurrr] & \cdot \ar@{-}[uurr] & \cdot \ar@{-}[ur] & & \\ 2 \ar@{-}[u] & \cdot & \cdot & \cdot \ar@{-}[ddrr] & \cdot & \cdot & \cdot & & & & 2 \ar@{-}[u] & \cdot & \cdot & x \ar@{-}[rrrr]& \cdot & \cdot & \cdot & \\ 1 \ar@{-}[u] & \cdot & \cdot & \cdot \ar@{-}[dr] & \cdot & \cdot & \cdot & & & & 1 \ar@{-}[u] & \cdot & \cdot & w \ar@{-}[rrrr] & \cdot & \cdot & \cdot & \\ 0 \ar@{-}[r]\ar@{-}[u] & 1 \ar@{-}[r] & 2 \ar@{-}[r] & v \ar@{-}[r] \ar@{-}[uuuuuuu] & 4 \ar@{-}[r] & 5 \ar@{-}[r] & \cdots \ar[r] & a & & & 0 \ar@{-}[r]\ar@{-}[u] & 1 \ar@{-}[r] & 2 \ar@{-}[r] & v \ar@{-}[r] & 4 \ar@{-}[r] & 5 \ar@{-}[r] & \cdots \ar[r] & a }}
The polynomial p = a^3b^3 + 2a^3b + 3ab^3 reduces involutively as follows.
p \stackrel{u}{\longrightarrow} 3a^4 + 2a^3b + 3ab^3 \stackrel{v}{\longrightarrow} 2a^3b + 3ab^3 + 9ab \stackrel{w}{\longrightarrow} 3ab^3 + 9ab + 6b^2 \stackrel{u}{\longrightarrow} 9a^2 + 9ab + 6b^2
This reduction is computed in section 3.3-2.
‣ IPolyReduce( algebra, polynomial, DivisionRecord, order ) | ( function ) |
‣ IPolyReduceCP( algebra, polynomial, DivisionRecord, order ) | ( operation ) |
The global function IPolyReduce calls one of the operations IPolyReduceCP and IPolyReduceNP depending on whether the algebra is commutative or not. This function reduces a polynomial p using the current overlap record for a basis, and an ordering.
In the example, using drec2, the polynomial p reduces only to 2a^3b+9a^2+9ab
p \stackrel{u}{\longrightarrow} 3a^4 + 2a^3b + 3ab^3 \stackrel{v}{\longrightarrow} 2a^3b + 3ab^3 + 9ab \stackrel{u}{\longrightarrow} 2a^3b + 9a^2 + 9ab
because the polynomial x is not available to reduce 2a^3b to 6b^2.
gap> p := a^3*b^3 + 2*a^3*b + 3*a*b^3;; gap> q := IPolyReduce( R, p, drec2, ord ); 2*a^3*b+9*a^2+9*a*b
‣ LoggedIPolyReduce( algebra, polynomial, DivisionRecord, order ) | ( function ) |
‣ LoggedIPolyReduceCP( algebra, polynomial, DivisionRecord, order ) | ( operation ) |
The global function LoggedIPolyReduce calls one of the operations LoggedIPolyReduceCP and LoggedIPolyReduceNP depending on whether the algebra is commutative or not. This function is similar to IPolyReduce, reducing a polynomial p using the current overlap record for a basis, and an ordering. It's output, however, is a record containing, as well as the reduced polynomial r, logging information which shows how the reduction has been obtained:
p ~=~ r + \sum_i logs[i] * polys[i].
In the example r.result is equal to the previous result q, and the equation above is verified:
a^3b^3 + 2a^3b + 3ab^3 ~=~ (2a^3b+9a^2+9ab) + (a^3+3a)(b^3-3a) + 3a(a^3-3b).
gap> r := LoggedIPolyReduceCP( R, p, drec2, ord ); rec( logs := [ a^3+3*a, 3*a ], polys := [ b^3-3*a, a^3-3*b ], result := 2*a^3*b+9*a^2+9*a*b ) gap> r.result = q; true gap> p = r.result + r.logs[1]*r.polys[1] + r.logs[2]*r.polys[2]; true
‣ IAutoreduce( alg, polys, order ) | ( function ) |
‣ IAutoreduceCP( alg, polys, order ) | ( operation ) |
The global function IAutoreduce calls one of the operations IAutoreduceCP and IAutoreduceNP depending on whether the algebra is commutative or not. This function applies IPolyReduce to a list of polynomials recursively until no more reductions are possible. More specifically, this function involutively reduces each member of a list of polynomials with respect to all the other members of the list, removing the polynomial from the list if it reduces involutively to 0. This process is iterated until no more reductions are possible.
If no reduction takes place, so that the result is equal to the initial list of polynomials, then true is returned.
In the example we form L3 by adding p to L2. On applying IAutoreduceCP, only p reduces, and the concatenation of L2 with q is returned. Starting with L4 = [u,v,w,x], there are no reductions, and true is returned.
gap> L3 := Concatenation( L2, [p] );; gap> IAutoreduceCP( R, L3, ord ); [ b^3-3*a, a^3-3*b, 2*a^3*b+9*a^2+9*a*b ] gap> L4 := Concatenation( L2, [ a^3*b-3*b^2, a^3*b^2-9*a ] );; gap> IAutoreduceCP( R, L4, ord ); true
The involutive algorithm for constructing an involutive basis uses prolongations and autoreduction.
Given a set of polynomials P, a prolongation of p ∈ P is a product pa_i where the generator a_i is not multiplicative with respect to the current involutive division.
A set of polynomials P is said to be autoreduced if no polynomial p ∈ P contains a term which is involutively divisible by some polynomial p' ∈ P ∖ {p}.
We denote by rem_I(p,Q) the involutive remainder of polynomial p with respect to a set of polynomials Q. Here is the Commutative Autoreduction Algorithm:
Input: a set of polynomials P = {p_1,p_2,...,p_n} and an involutive division I
while there exists p_i in P such that rem_I(p_i, P\{p_i}) <> p_i do
q := Rem_I(p_i, P\{p_i});
P := P\{p_i};
if (q<>0) then
P := P union {q};
fi;
od;
return P;
It can be shown that if P is a set of polynomials over a polynomial ring R = F[a_1,...,a_n], such that P is autoreduced with respect to an involutive division I, and if p,q are two polynomials in R, then rem_I(p,P) + rem_I(q,P) = rem_I(p+q,P).
Given an involutive division I and an admissible monomial ordering O, an autoreduced set of polynomials P is a locally involutive basis with respect to I and O if any prolongation of any p_i ∈ P involutively reduces to zero using P. Further, P is an involutive basis with respect to I and O if any multiple p_it of any p_i ∈ P by any term t involutively reduces to zero using P.
The Commutative Involutive Basis Algorithm:
Input: a basis F = {f_1,f_2,...,f_m} for an ideal J
over a commutative polynomial ring R[a_1,...,a_n];
an admissible monomial ordering O;
a continuous and constructive involutive division I
Output: an involutive basis G = {g_1,g_2,...,g_k} for J (if it terminates)
G := { };
F := autoreduction of F with respect to O and I;
while G = { } do
P := set of all prolongations f_i*a_j, 1<=i<=m, 1<=j<=n;
q := 0;
while (P <> { }) and (q=0) do
p := a polynomial in P with minimal lead monomial w.r.t. O;
P := P \ {p};
q := rem_I(p,F);
od;
if (q <> 0) then ## new basis element found
F := autoreduction of (F union {q})
else ## all the prolongations have reduced to zero
G := F;
fi;
od;
return G;
‣ InvolutiveBasis( alg, polys, order ) | ( function ) |
‣ InvolutiveBasisCP( alg, polys, order ) | ( operation ) |
The global function InvolutiveBasis calls one of the operations InvolutiveBasisCP and InvolutiveBasisNP depending on whether the algebra is commutative or not. This function finds an involutive basis for the ideal generated by a set of polynomials, using a chosen ordering, and returns a division record.
Any involutive basis returned by this algorithm is a Gröbner basis, and remainders are involutively unique with respect to this basis.
gap> ibasP := InvolutiveBasis( R, L2, ord ); rec( div := "Pommaret", mvars := [ [ 1, 2 ], [ 1 ], [ 1 ], [ 1 ] ], polys := [ b^3-3*a, a^3-3*b, a^3*b-3*b^2, a^3*b^2-9*a ] ) gap> r := IPolyReduce( R, p, ibasP, ord ); 9*a^2+9*a*b+6*b^2
Here we have returned to the example in section 3.2-7. Starting with F={u,v}, there is only one prolongation, P={w=vb}, and F becomes {u,v,w}. At the second iteration, P={vb,wb}; vb reduces to zero; wb reduces to x=a^3b^2-9a; and F becomes {u,v,w,x}. At the third iteration P={vb,wb,xb} and all three of these reduce to zero, so G = F is returned.
It is then shown that the multiplicative variables for {u,v,w,x} are {{a,b},{a},{a},{a}}.
Finally, the full reduction r of p is computed.
If, instead of the Pommaret division, we use Janet or Thomas we obtain:
gap> CommutativeDivision := "Janet";; gap> ibasJ := InvolutiveBasis( R, L2, ord );; gap> ( ibasJ.mvars = ibasP.mvars ) and ( ibasJ.polys = ibasP.polys ); true gap> CommutativeDivision := "Thomas";; gap> ibasT := InvolutiveBasis( R, L2, ord ); rec( div := "Thomas", mvars := [ [ 2 ], [ 1 ], [ 2 ], [ 1 ], [ 2 ], [ 1 ], [ 1, 2 ] ], polys := [ b^3-3*a, a^3-3*b, a*b^3-3*a^2, a^3*b-3*b^2, a^2*b^3-9*b, a^3*b^2-9*a, a^3*b^3-9*a*b ] )
The Janet division gives the same involutive basis as Pommaret, but the Thomas Division produces 7, rather than 4 polynomials:
[u,v,y,w,z,x,t] ~=~ [~ b^3-3a,\ a^3-3b,\ ab^3-3a^2,\ a^3b-3b^2,\ a^2b^3-9b,\ a^3b^2-9a,\ a^3b^3-9ab ~].
The multiplicative variables for these polynomials are [ {b}, {a}, {b}, {a}, {b}, {a}, {a,b} ], so the reduction diagram for the Thomas basis is:
\vcenter{\xymatrix@=1em{ b & & & & & & & & \\ : \ar[u] & \cdot & \cdot & \cdot \ar@{-}[ur] & \cdot & \cdot & \cdot & & \\ 5 \ar@{-}[u] & \cdot & \cdot & \cdot \ar@{-}[uurr] & \cdot & \cdot & \cdot & & \\ 4 \ar@{-}[u] & \cdot & \cdot & \cdot \ar@{-}[uuurrr] & \cdot & \cdot & \cdot & & \\ u \ar@{-}[u] & y \ar@{-}[uuuu] & z \ar@{-}[uuuu] & t \ar@{-}[uuuurrrr] \ar@{-}[uuuu] \ar@{-}[rrrr] & \cdot \ar@{-}[uuurrr] & \cdot \ar@{-}[uurr] & \cdot \ar@{-}[ur] & & \\ 2 \ar@{-}[u] & \cdot & \cdot & x \ar@{-}[rrrr] & \cdot & \cdot & \cdot & & \\ 1 \ar@{-}[u] & \cdot & \cdot & w \ar@{-}[rrrr] & \cdot & \cdot & \cdot & & \\ 0 \ar@{-}[r]\ar@{-}[u] & 1 \ar@{-}[r] & 2 \ar@{-}[r] & v \ar@{-}[r] & 4 \ar@{-}[r] & 5 \ar@{-}[r] & \cdots \ar[r] & a & }}
The reduction of p with this basis is:
p = a^3b^3 + 2a^3b + 3ab^3 \stackrel{t}{\longrightarrow} 2a^3b + 3ab^3 + 9ab \stackrel{w}{\longrightarrow} 3ab^3 + 9ab + 6b^2 \stackrel{y}{\longrightarrow} 9a^2 + 9ab + 6b^2.
gap> r := LoggedIPolyReduceCP( R, p, ibasT, ord ); rec( logs := [ 0, 0, 3, 2, 0, 0, 1 ], polys := [ b^3-3*a, a^3-3*b, a*b^3-3*a^2, a^3*b-3*b^2, a^2*b^3-9*b, a^3*b^2-9*a, a^3*b^3-9*a*b ], result := 9*a^2+9*a*b+6*b^2 )
Here we consider Example 4.5.2 in the thesis [Eva05]. On setting InfoLevel(InfoIBNP) to 1 some of the intermediate calculations are displayed. The setting of the problem is a rational polynomial ring in three variables with the lex ordering [x,y,z], using the Janet involutive division.
the initial basis contains two polynomials {a=x^2+y^3,~b=x+z^3}
the reduced Gröbner basis is {c=y^3+z^6,~b=x+z^3}, and the irreducible monomials are {z^k,~yz^k,~y^2z^k~|~ k geqslant 0}
when starting to calculate an involutive basis, the autoreduction does nothing because x is not multiplicative for b
the only prolongation is bx = x^2+xz^3 which reduces, on subtracting a+bz^3 and changing the sign, to c=y^3+z^6
on restarting with basis [c,b,a], autoreduction replaces a with a-c = d = x^2-z^6
there are then 3 prolongations [by,bx,dy] and bx now reduces to zero
by = e = xy+yz^3 is then added to the basis: [c,b,e,d]
dy = x^2y-yz^6 reduces to zero on adding e(-x+z^3)
on restarting with basis [c,b,e,d] there are 4 prolongations [by,ey,bx,dy] and of these only f = ey = xy^2+y^2z^3 does not reduce to zero
restarting with basis [c,b,e,f,d], the 5 prolongations [by,ey,fy,bx,dy] all reduce to zero.
now see what happens when reducing p = x^7+y^7+z^7 using the basis [c,b,e,f,d]
x^7-dx^5 = x^5z^6 and x^5z^6 - dx^3z^6 = x^3z^12 and x^3z^12-dxz^12 = xz^18 and xz^18-bz^18=-z^21
y^7 - cy^4 = -y^4z^6 and -y^4z^6 + cyz^6 = yz^12, so p reduces to -z^21 + yz^12 + z^7.
gap> SetInfoLevel( InfoIBNP, 1 );; gap> CommutativeDivision := "Janet";; gap> R3 := PolynomialRing( Rationals, [ "x", "y", "z" ] );; gap> x := R3.1;; y := R3.2;; z := R3.3;; gap> ord3 := MonomialLexOrdering( [x,y,z] );; gap> F := [ y^3 + x^2, z^3 + x ];; gap> gbas := GrobnerBasis( F, ord3 ); [ y^3+x^2, z^3+x, -z^6-y^3 ] gap> rgbas := ReducedGrobnerBasis( F, ord3 ); [ z^6+y^3, z^3+x ] gap> ibasF := InvolutiveBasisCP( R3, F, ord3 ); #I restarting with basis: [ z^3+x, y^3+x^2 ] #I division record for basis: rec( div := "Janet", mvars := [ [ 2, 3 ], [ 1, 2, 3 ] ], polys := [ z^3+x, y^3+x^2 ] ) #I prolongations = [ x*z^3+x^2 ] #I restarting with basis: [ z^6+y^3, z^3+x, y^3+x^2 ] #I after autoreduction basis = [ z^6+y^3, z^3+x, -z^6+x^2 ] #I division record for basis: rec( div := "Janet", mvars := [ [ 1, 2, 3 ], [ 3 ], [ 1, 3 ] ], polys := [ z^6+y^3, z^3+x, -z^6+x^2 ] ) #I prolongations = [ y*z^3+x*y, x*z^3+x^2, -y*z^6+x^2*y ] #I restarting with basis: [ z^6+y^3, z^3+x, y*z^3+x*y, -z^6+x^2 ] #I division record for basis: rec( div := "Janet", mvars := [ [ 1, 2, 3 ], [ 3 ], [ 1, 3 ], [ 1, 3 ] ], polys := [ z^6+y^3, z^3+x, y*z^3+x*y, -z^6+x^2 ] ) #I prolongations = [ y*z^3+x*y, y^2*z^3+x*y^2, x*z^3+x^2, -y*z^6+x^2*y ] #I restarting with basis: [ z^6+y^3, z^3+x, y*z^3+x*y, y^2*z^3+x*y^2, -z^6+x^2 ] #I division record for basis: rec( div := "Janet", mvars := [ [ 1, 2, 3 ], [ 3 ], [ 1, 3 ], [ 1, 3 ], [ 1, 3 ] ], polys := [ z^6+y^3, z^3+x, y*z^3+x*y, y^2*z^3+x*y^2, -z^6+x^2 ] ) #I prolongations = [ y*z^3+x*y, y^2*z^3+x*y^2, y^3*z^3+x*y^3, x*z^3+x^2, -y*z\ ^6+x^2*y ] rec( div := "Janet", mvars := [ [ 1, 2, 3 ], [ 3 ], [ 1, 3 ], [ 1, 3 ], [ 1, 3 ] ], polys := [ z^6+y^3, z^3+x, y*z^3+x*y, y^2*z^3+x*y^2, -z^6+x^2 ] ) gap> ## now for a reduction - reset the info level: gap> SetInfoLevel( InfoIBNP, 2 );; gap> p := x^7 + y^7 + z^7;; gap> IPolyReduce( R3, p, ibasF, ord3 ); #I reduced to: x^5*z^6+y^7+z^7 #I reduced to: x^3*z^12+y^7+z^7 #I reduced to: x*z^18+y^7+z^7 #I reduced to: -z^21+y^7+z^7 #I reduced to: -z^21-y^4*z^6+z^7 #I reduced to: -z^21+y*z^12+z^7 -z^21+y*z^12+z^7
If the polynomials in an initial basis are not homogeneous then they may be made homogeneous by introducing an additional variable. The resulting involutive basis will contain only homogeneous polynomials. However, if these are de-homogenised by setting the additional variable equal to 1, the resulting basis may not be involutive.
Applying this to the previous example, the resulting basis contains 10 polynomials which include homogenised versions of [c,b,e,f], but not d.
gap> SetInfoLevel( InfoIBNP, 0 ); gap> R4 := PolynomialRing( Rationals, [ "x", "y", "z", "t" ] );; gap> x := R4.1;; y := R4.2;; z := R4.3;; t := R4.4;; gap> H := [ x^2*t + y^3, x*t^2 + z^3 ];; gap> ord4 := MonomialLexOrdering( [x,y,z,t] );; gap> ibasH := InvolutiveBasisCP( R4, H, ord4 ); rec( div := "Janet", mvars := [ [ 1, 2, 3, 4 ], [ 1, 2, 3 ], [ 1, 3, 4 ], [ 1, 2, 3 ], [ 1, 2, 3 ], [ 1, 3, 4 ], [ 1, 3, 4 ], [ 1, 2 ], [ 1, 2 ], [ 1, 2 ] ], polys := [ y^3*t^3+z^6, x*t^2+z^3, x*t^3+z^3*t, x*z^3-y^3*t, x*z^3*t-y^3*t^2, x*y*t^3+y*z^3*t, x*y^2*t^3+y^2*z^3*t, x^2*t+y^3, x^2*z*t+y^3*z, x^2*z^2*t+y^3*z^2 ] )
generated by GAPDoc2HTML