Properties of Groebner Bases

 

We will see first that the undesirable behavior of the division algorithm in K[x1,x2,...,xn] does not occur when dividing by the elements of a Groebner basis.
Proposition 1. Let G = {g1,g2,...,gt} be a Groebner basis for an ideal I in K[x1,x2,...,xn] and let f be a polynomial in K[x1,x2,...,xn]. Then there is a unique r in K[x1,x2,...,xn] such that
  1. r is completely reduced with respect to G.
  2. there is g in K[x1,x2,...,xn] such that f = g + r.
This tells us that on division of f by G the remainder is uniquely determined, no matter how the elements of G are listed when using the division algorithm (although the "quotiens" ai produced by the algorithm in f=a1g1+a2g2+...+atgt+rmay change if we rearrange the gi).

As a corollary we get the following criterion for establishing when a polynomial f lies in an ideal.
Corollary 2. Let G be a Groebner basis for an ideal I in K[x1,x2,...,xn] and let f be a polynomial in K[x1,x2,...,xn]. Then f is in I if and only if the remainder r on division of f by G is zero.
This corollary gives an algorithm to solve the ideal membership problem.
First we compute a Groebner basis G of I. Then we divide f by G and get the remainder r. If r = 0.then f lies in I, otherwise it does not.

In order to compute a Groebner basis of an ideal, our definition of Groebner bases doesn't help us very much. So we will give an alternate characterization of Groebner bases which shows us a practical way to construct them. To do this, we need to introduce the term of S-polynomial. Recall that we define the LCM of two monomials as the product of all the variables, each to a power which is the maximum of its powers in the two monomials.
Definition 3. Fix a monomial ordering. Let f and g be two polynomials in K[x1,x2,...,xn] and let J = LCM(LM(f),LM(g)). The S-polynomial of f and g is the combination
  J     J  
S(f,g) = -------- · f - -------- · g
  LT(f)     LT(g)  
Since J/LT(f) and J/LT(g) are monomials, then S(f,g) belongs to the same ideal to which f and g belong.

S-polynomials are constructed to cancel LT(f) and LT(g). In fact, the leading term of the two components of S(f,g) are equal and cancel each other.

Example.

  1. Let f = x2y + 2xy2 and g = 3y2 + 2 with lex order and x>y. Then J = x2y2 and
  x2y2     x2y2          
S(f,g) = -------- · f - -------- · g = y · f - (1/3 x2)· g = -2/3x2 + 2xy3
  x2y     3y2          

Now we can give an alternate characterization of Groebner bases [3].
Proposition 4. G = {g1,g2,...,gt} is a Groebner basis for an ideal I if and only if S(gi,gj) -->*G 0 for all gi, gj in G, gi<>gj.
This criterion is the driving force behind Groebner bases method since it suggests how we can transform an arbritary ideal basis into a Groebner basis. Given a finite set F in K[x1,x2,...,xn], we can immediately test F by checking whether

S(p,q) -->*F 0 for all p,q in F, p<>q.

If we find a pair (p, q) such that

S(p,q) -->*F r <> 0,

we can add r to F without changing the ideal generated (<F> = <F, r> because r is already in <F>). Moreover, once r is added to F, S(p,q) will reduce to 0. However there will be new S-polynomials to be considered in F U r.
To see that such a process will terminate, let Hi, be the set of leading terms of the basis after the i-th new polynomial ri is added. Since new leading terms are not multiple of the old ones (ri is completely reduced, so no term of ri is divisible by any of the elements in Hi-1), the inclusions

<H1> C <H2> C <H3> C...

are proper. Thus, by the Ascending Chain Condition such a chain must stabilize with <Hn> for some n.
This is the essence of Buchberger's algorithm to compute Groebner bases.

Example.

Consider the ideal I = <y - x2, z - x3>. Then G = {y - x2, z - x3} is a Groebner basis for lex order with z>y>x. In fact, we have

S(y - x2, z - x3) = -zx2 + yx3

and -zx2 + yx3 -->*F 0 since, using the division algorithm,

-zx2 + yx3 = x3 (y - x2) + (-x2)(z - x3) + 0.

Note that G is not a Groebner basis when we use lex order with x>y>z.

 

Last updated 09/14/2009 08:07:07