Buchberger's Algorithm

Buchberger's Algorithm for Groebner Bases.

 

Input: A polynomial set F = {f₁,f₂,...,f_s} that generates an ideal I
Output: A Groebner basis G = {g₁,g₂,...,g_t} that generates I
G := F
M := {{f_i, f_j}: f_i, f_j are in G and f_i<>f_j}
WHILE (M<>Ø) DO

{p, q} := a pair in M
M := M - {{p, q}}
S := S-Polynomial(p, q)
h := NormalForm(S, G)
IF (h <> 0) THEN

M := M U {{g, h} for all g in G}
G := G U {h}

Example.

Consider I = <F> where F = {f₁ = x² + 2xy², f₂ = xy + 2y³ - 1} with lex order and x>y in R[x,y].
Then we set G = F and M = {{f₁, f₂}}.
S(f₁, f₂) = x and NormalForm(x, G) = x. So we must add f₃ = x to our generating set G and update M; we get G = {f₁, f₂, f₃} and M = {{f₁, f₃},{f₂, f₃}}.
We pick a pair in M, say {f₂, f₃}, and compute S(f₂, f₃) = 2y³ - 1, which is already completely reduced modulo G. We add f₄ = 2y³ + 1 to G. We set G = {f₁, f₂, f₃, f₄} and M = {{f₁, f₃},{f₁, f₄},{f₂, f₄},{f₃, f₄}}.
If we compute the S-polynomials of the pairs in M, we will see that all reduce to 0 modulo G = {f₁, f₂, f₃, f₄}. In fact, we have:

S(f₁, f₃) = 2xy² = 2y² f₃ so NormalForm(S(f₁, f₃), G) = 0;
S(f₁, f₄) = ¹/ ₂x² + 2xy⁵ = ¹/ ₂ f₁ + xy² f₄ so NormalForm(S(f₁, f₄), G) = 0;
S(f₂, f₄) = ¹/ ₂x + 2y⁵ - y² = ¹/ ₂ f₃ + y² f₄ so NormalForm(S(f₂, f₄), G) = 0;
S(f₃, f₄) = ¹/ ₂x = ¹/ ₂ f₃ so NormalForm(S(f₃, f₄), G) = 0.

It follows that a Groebner basis for I is given by:

G = {f₁, f₂, f₃, f₄} = {x² + 2xy², xy + 2y³ - 1, x, 2y³ - 1}.

Groebner bases computed with the algorithm above are often bigger than necessary.
If in a Grobner basis G the leading term of a generator p is divisible by the leading term of another generator, we can eliminate p and G is still a Groebner basis by definition.

Example.

In the Groebner basis computed in the previous example we can eliminate f₁ and f₂ since their leading terms are both multiples of the leading term of f₃. This leads to the basis

G = {f₃, f₄} = {x, 2y³ - 1}.

Furthermore, if we adjust constants to make all leading coefficients 1, we get to what it is called a minimal Groebner basis.

Example.

A minimal Groebner basis of the ideal I = <x² + 2xy², xy + 2y³ - 1> of the previous example is

G = {x, y³ - ¹/ ₂}.

Note that any Grobner basis of the form

G = {x + a(y³ - ¹/ ₂), y³ - ¹/ ₂} where a is any constant in R

is a minimal Groebner basis for I (with lex order and x>y).

As we have just seen, a given ideal may have many minimal Groebner bases for a fixed monomial ordering. Fortunately, we can single out one minimal basis which is better than the others by requiring that each generator is completely reduced modulo the others. Here is the definition:

1. LC(p) = 1 for all p in G.
2. each p in G is completely reduced modulo G-{p}.

The reduced Groebner basis of the ideal I = <x² + 2xy², xy + 2y³ - 1> with lex order and x>y is

G = {x, y³ - ¹/ ₂}.

As a consequence of this uniqueness we get an ideal equality algorithm to test whether two polynomial sets {f₁, f₂,..., f_s} and {g₁, g₂,..., g_t} generate the same ideal: simply fix a monomial order and compute the reduced Groebner bases for <f₁, f₂,..., f_s> and <g₁, g₂,..., g_t>. Then the ideals are equal if and only if the Groebner bases are the same.

Last updated