Gröbner bases

PolynomialReduction can be used to determine remainders. The first entry is the remainder, the second the coefficients with respect to the list of basis elements. (Note that the division algorithm works slightly different than the one in the book, thus if $G$ is not a Gröbner basis you might get different remainders.)

gap> PolynomialReduction(x^5*y,G,MonomialGrlexOrder);
[ x, [ 1+y+y^2+y^3+x^4+x^3*y+x^2*y^2+x*y^3+y^4, 1+y+y^2+y^3+y^4, 0 ] ]

Exercise 2.13.13   Let $F$ be a field and let $R=F[x,y]$. Let $<$ denote the lexicographical order with $x >y$. Let $f(x,y)=x^2y+xy^2+y^2$, $f_1(x,y)=xy-1$, and $f_2(x,y)=y^2-1$. Find the normal form of $f$ mod $F=\{f_1,f_2\}$. (Use PolynomialReduction.)

To sort the monomials using the lexicographical ordering in GAP, one can use the following commands (available in GAP):

gap> x:=X(Rationals,"x");
x
gap> y:=X(Rationals,"y");
y
gap> r:=DefaultRing(x,y);
PolynomialRing(..., [ x, y ])
gap> elms:=[x^5*y+y,y^2*x^2+2*x];
[ y+x^5*y, 2*x+x^2*y^2 ]
gap> GroebnerBasis(elms,MonomialLexOrdering());
[ y+x^5*y, 2*x+x^2*y^2, -y^2+2*x^4, -2*y-x*y^3, -4*x^3-y^4, 8*x^2-y^6, 
  -16*x-y^8, -32*y+y^11 ]
gap> ReducedGroebnerBasis(elms,MonomialLexOrdering());
[ -32*y+y^11, -16*x-y^8 ]
gap> order:=MonomialLexOrdering();
MonomialLexOrdering()
gap> List(Cartesian([0..3],[0..3]),i->x^i[1]*y^i[2]);
[ 1, y, y^2, y^3, x, x*y, x*y^2, x*y^3, x^2, x^2*y, x^2*y^2, x^2*y^3, x^3, 
  x^3*y, x^3*y^2, x^3*y^3 ]
gap> l:=last;
[ 1, y, y^2, y^3, x, x*y, x*y^2, x*y^3, x^2, x^2*y, x^2*y^2, x^2*y^3, x^3, 
  x^3*y, x^3*y^2, x^3*y^3 ]
gap> Sort(l,MonomialComparisonFunction(order));
gap> l;
[ 1, y, y^2, y^3, x, x*y, x*y^2, x*y^3, x^2, x^2*y, x^2*y^2, x^2*y^3, x^3, 
  x^3*y, x^3*y^2, x^3*y^3 ]

LeadingTerm gives the leading term of a polynomial.

gap> LeadingTerm(x*y^2+2*x^2*y,MonomialGrlexOrder);  
2*x^2*y

Exercise 2.13.14   Rewrite the following polynomial, ordering its terms according to the lex, grlex and grevlex ordering and give $LM(f)$, $LT(f)$ and multideg$(f)$ in each case.

$$f(x,y,z)=2x^2y^8-3x^5yz^4+xyz^3-xy^4.$$

Exercise 2.13.15   Let $B=(x^2y-z,xy-1)$ and $f=x^3-x^2y-x^2z+x$.

(a) Compute the remainder of dividing $f$ by $B$ for both the lex and the grlex ordering.

(b) Repeat part (a) with the order of the pair $B$ reversed.

Exercise 2.13.16   Compute the S-polynomial for $x^4y-z^2$ and $3xz^2-y$ with respect to the lex ordering with $x>y>z$ and for $z>y>x$.

To compute Gröbner bases using GAP, one has to define indeterminates and polynomials. Indeterminates are displayed either by their internal numbers or you can prescribe names. (Note however that the names hide the internal numbers and these numbers are basis for the monomial orderings. The best is to define a set of variables at the start and then not to redefine them afterwards.

GBasis computes a Gröbner basis. (You can set the info level as done here to get some information about the calculations.)

gap> SetInfoLevel(InfoGrobner,1);                  
gap> B:=[x*y-y^2,y^2-x];
[ x*y-y^2, -x+y^2 ]
gap> G:=GBasis(B,MonomialGrlexOrder);
[ x*y-y^2, -x+y^2, x-x^2 ]

If you want to change the variable ordering, the best way is to permute the variables in the polynomials instead (in the inverse order!). For example to change to an order $y>x$ we could do:

gap> B2:=List(B,i->OnIndeterminates(i,(1,2)));
[ -x^2+x*y, -y+x^2 ]
gap> G:=GBasis(B2,MonomialGrlexOrder);
[ -x^2+x*y, -y+x^2, y-x*y, -y+y^2 ]

Exercise 2.13.17   Let $I=\langle x^5+y^4+z^3-1,x^3+y^2+z^2-1\rangle$. Compute a Gröbner basis for $I$ with respect to the lex, grlex, and grevlex orderings. Compare.
Repeat the calculations for $I=\langle x^5+y^4+z^3-1,x^3+y^3+z^2-1\rangle$ (only one exponent changed!)