Groebner Bases

 

Definition 1. Let I be an ideal in K[x 1,x 2,...,x n] other than {0}.
  1. We define LT(I) as the set of the leading terms of elements of I, i.e.
    LT(I) = {LT(f) : f is an element of I}.
  2. We denote by <LT(I)> the ideal generated by the elements of LT( I).
Note that if I = <f 1,f 2,...,f s> than <LT(f1),LT(f 2),...,LT(f s)> and <LT(I)> may be different ideals. It is true that <LT(f 1),LT(f 2),...,LT(f s)> is included in <LT(I)>, since LT(fi) is an element of LT(I) by definition, but the converse is not true in general.

Example.

Let I = <f1,f 2>, where f1 = x2 + 2xy2 and f2 = xy + 2y3 - 1. Using lex order on K[x,y], we have LT(f1) = x2, LT(f 2) = xy and:

y·(x2 + 2xy2) - x·(xy + 2y3 - 1) = x

so that x is in I. Moreover LT(x) = x. But x cannot be written as h(x,y)·LT(f 1)+ h(x,y)·LT(f 2) for some h in K[x,y] so x is not in <LT(f1),LT(f 2)>.

We will give a particular name to those special bases for which <LT(<g1,g 2,...,g t>)> = <LT(g1),LT(g 2),...,LT(g t)>.
Definition 2. Fixed a monomial ordering, a subset G = {g1,g 2,...,g t} of an ideal I is said to be a Groebner basis if:

LT(I) = <LT(g1),LT(g 2),...,LT(g t)>.
This means that a subset G = {g 1,g 2,...,g t} of an ideal I is a Groebner basis if and only if the leading term of any element of I is divisible by one of the LT(g i).

But, does any ideal in K[x 1,x 2,...,x n] have a Groebner basis? And what is the relationship between <f1,f 2,...,f s> and <g1,g 2,...,g t>? The following result will answer our questions [3].
Proposition 3. Fix a monomial ordering. Then every ideal I = <f 1,f 2,...,f s> in K[x1,x 2,...,x n] other than {0} has a Groebner basis G = {g 1,g 2,...,g t}. Futhermore, any Groebner basis of I is a basis of I, i.e. I=<f 1,f 2,...,f s>=<g 1,g 2,...,g t>.
Examples.

Let's see some examples of Groebner bases.

  1. First consider the ideal I from the example above, which has the basis {f 1,f 2}={ x2 + 2xy2, xy + 2y3 - 1}. Then, {f1,f 2} is not a Groebner basis of I w.r.t. lex order on K[x,y], since we have seen that x is in <LT(I)> but x is not in <LT(f1),LT(f 2)>. We will find a Groebner basis of I when we discuss the Buchberger's algorithm.
  2. Next, consider the ideal J = <g 1,g 2 > = <x+z,y-z>. We claim that {g 1,g 2} is a Groebner basis using lex order in R[x,y,z]. Thus, we must show that <LT( J)> is included in <LT(g 1),LT(g 2)>=< x,y>, since the converse is always true. So pick up a nonzero polynomial f in J. Suppose on the contrary that LT(f) is not expressible as A(x,y,z) x + B(x,y,z)y, i.e. is not divisible by neither x nor y. So, by definition of lex order, f must be a polynomial in z alone. However f vanishes on the subspace of R3 L={(x,y,z): x+z=0,y-z=0}={( -t,t,t) for any t in R}; but the only polynomial in z alone which vanishes in all R is the zero polynomial, which is a contradiction. It follows that {g1,g 2} is a Groebner basis w.r.t. lex order in R[x,y,z].
  3. We must point out that the relative order of the variables (as well as the ordering on the monomials) plays a foundamental role in establishing if a subset {g 1,g 2,...,g t} of an ideal is a Groebner basis of that ideal (see Monomial orderings).
    If we reconsider {g 1,g 2} of the example 2 w.r.t. the lex with z>y>x we can see that {g 1,g 2} is not a Grobner basis of J. In fact, we have:
    <LT(g1),LT(g 2)>=< z>, y+x=g1+g 2 (so y+x is in J) and LT(y+x)= y, but y is not in <z>.

Greobner bases have some other nice properties that we will investigate further.

 

Last updated