Groebner Bases in Mathematica

The Mathematica function for finding Groebner bases is called, not surprisingly, GroebnerBasis[ ].

?GroebnerBasis
Options[GroebnerBasis]

Consider the ideal I = < f1, f2 > where f1 and f2 are given below.  We can find Groebner bases for  I with respect to various monomial orderings.

f1=x^2+z;f2=y*z+x+1;
{f1,f2}
gb1 =  GroebnerBasis[{f1,f2},{x,y,z}]
gb2 =  GroebnerBasis[{f1,f2},{z,x,y}]
gb3 =  GroebnerBasis[{f1,f2},{x,y,z},MonomialOrder->DegreeReverseLexicographic]
gb4 =  GroebnerBasis[{f1,f2},{x,y,z},MonomialOrder->DegreeLexicographic]

This shows that f1 and f2 are already a Groebner basis with respect to glex and grevlex orderings.  However we get a new basis for the lex and permuted lex orders.

Uniqueness of Remainders and Ideal Membership

To illustrate the useful properties of Groebner bases, let’s calculate some remainders under division. According to the theory, the remainder of a given polynomial f(x,y,z) should not depend on the order that the basis polynomials are listed.  Also, we get a remainder r = 0 if and only if f is in the ideal generated by {g1, g2}.  We will use lex order for which gb1 is a Groebner basis.

{g1, g2}  = gb1
f = 2x^2*y+x*y*z+y*z^2;
PolynomialReduce[f,{g1,g2},{x,y,z}]
PolynomialReduce[f,{g2,g1},{x,y,z}]

The point is that the remainder is now uniquely determined.  The fact that the remainder is not zero shows that the polynomial f is not in the ideal.  Let's try creating something which is in the ideal and then taking the remainders under division by the original polynomials {f1, f2} and also by the Groeber basis {g1, g2}.  Note: to read off just the remainders you can use 
PolynomialReduce[  ][[2]] to read off just the second entry of the answer.

h = (x^2-y^17+12*z)*f1 + (x+y-z)^5*f2//Expand
PolynomialReduce[h,{g1,g2},{x,y}][[2]]
PolynomialReduce[h,{f1,f2},{x,y}][[2]]
PolynomialReduce[h,{f2,f1},{x,y}][[2]]

The non-Groebner basis fails to give remainder 0 and even gives two different remainders. This shows the advantage of the Groebner basis for testing ideal membership.

Testing Ideal Equality

Here is how to use Groebner bases to test ideal equality.  There are three ideals naturally associated to the twisted cubic curve, parametized by x = t, y = t^2, z = t^3.  We know that   I(V) = < x^2 - y, x^3 - z> is the ideal of the curve.  On the other hand we could look at  J=  < x^2 - y, y^3 - z^2> and K =  < x^3 - z, y^3-z^2>.   Since Mathematica produces reduced Groebner bases (except it doesn't necessarily make the leading coefficient be 1), two equal ideals will produce identical Groebner bases for any fixed monomial order.  Thus the following computations show that all three ideals are different.

GroebnerBasis[{x^2-y,x^3-z},{x,y,z}]
GroebnerBasis[{x^2-y,y^2-z^3},{x,y,z}]
GroebnerBasis[{x^3-z,y^2-z^3},{x,y,z}]

Weight Matrices

You can define your own monomial ordering by giving a weight matrix W.  In Mathematica a matrix is a list of lists.   A list of numbers represents a row of the matrix and a list of all the row lists represents the matrix.  Lexicographic order is given by the identity matrix.

f1=x^2+z;f2=y*z+x+1;
GroebnerBasis[{f1,f2},{x,y,z},MonomialOrder->Lexicographic]

W = {{1,0,0},{0,1,0},{0,0,1}};
W//MatrixForm
GroebnerBasis[{f1,f2},{x,y,z},MonomialOrder->W]

Similarly other orders are represented by appropriate matrices W chosen so that two exponent vectors a and b satisfy  a > b if and only if the leftmost nonzero entry of  W(a-b) is positive.  Here is grevlex.

GroebnerBasis[{f1,f2},{x,y,z},MonomialOrder->DegreeReverseLexicographic]

W = {{1,1,1},{0,0,-1},{0,-1,0}};
W//MatrixForm
GroebnerBasis[{f1,f2},{x,y,z},MonomialOrder->W]

Here is an example which is not built in.  It is a  four-variable "block order"  chosen so that any monomial  involving x, y is larger than any monomial involving only s, t.  The 2 x 2 blocks are the matrices representing two-variable grevlex orders.

f1 = x^4+y^4 + (x-y)^6
f2 = x+y - s
f3 = x*y - t

W = {{1,1,0,0},{0,-1,0,0},{0,0,1,1},{0,0,0,-1}};
W//MatrixForm
GroebnerBasis[{f1,f2,f3},{x,y,s,t},MonomialOrder->W]

This is an example of an elimination order.  Among the basis elements is a polynomial in (s,t) alone with variables (x,y) eliminated.  This will be very useful for applications.  Mathematica provides a way to compute such polynomials using a variation of the GrobnerBasis command where you specify two lists of variables, namely 
GroebnerBasis[ {polynomials}, {variables to keep}, {variables to eliminate}]
The command uses some sort of block order.

GroebnerBasis[{f1,f2,f3},{s,t},{x,y}]