Properties of Groebner Bases

We will see first that the undesirable behavior of the division algorithm in K[x₁,x₂,...,x_n] does not occur when dividing by the elements of a Groebner basis.

Proposition 1. Let G = {g₁,g₂,...,g_t} be a Groebner basis for an ideal I in K[x₁,x₂,...,x_n] and let f be a polynomial in K[x₁,x₂,...,x_n]. Then there is a unique r in K[x₁,x₂,...,x_n] such that

r is completely reduced with respect to G.
there is g in K[x₁,x₂,...,x_n] 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" a_i produced by the algorithm in f=a₁g₁+a₂g₂+...+a_tg_t+rmay change if we rearrange the g_i).

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[x₁,x₂,...,x_n] and let f be a polynomial in K[x₁,x₂,...,x_n]. 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[x₁,x₂,...,x_n] 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.

Let f = x²y + 2xy² and g = 3y² + 2 with lex order and x>y. Then J = x²y² and

x²y² x²y²

S(f,g) = -------- · f - -------- · g = y · f - (¹/₃ x²) · g = -²/₃x²+ 2xy³

x²y 3y²

Now we can give an alternate characterization of Groebner bases [3].

Proposition 4. G = {g₁,g₂,...,g_t} is a Groebner basis for an ideal I if and only if S(g_i,g_j) -->^*_G0 for all g_i,g_j in G, g_i<>g_j.

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[x₁,x₂,...,x_n], we can immediately test F by checking whether

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

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

S(p,q) -->^*_Fr <> 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, it 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 H_i, be the set of leading terms of the basis after the i-th new polynomial r_i is added. Since new leding terms are not multiple of the old ones (r_i is completely reduced, so no term of r_i is divisible by any of the elements in H_i-1), the inclusions

<H₁> C <H₂> C <H₃> C ...

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

Example.

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

S(y - x², z - x³) = -zx²+ yx³

and -zx²+ yx³ -->^*_F0 since, using the division algorithm,

-zx²+ yx³ = x³(y - x²) + (-x²)(z - x³) + 0.

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

Last updated

Last updated