Buchberger algorithm

A Noetherian ring $ R $ is called effective if its elements and ring operations can be described effectively as well as the problem of finding all solutions to a linear equation $ \sum _ {i} a _ {i} x _ {i} = b $ with $ a _ {i} ,b \in R $ and unknown $ x _ {i} \in R $( in terms of a particular solution and a finite set of generators for the module of all homogeneous solutions). Examples are the rings of integers and of rational numbers, algebraic number fields, and finite rings. For such a ring $ R $, the Buchberger algorithm (cf. [a3], [a4]) solves the following problem concerning the polynomial ring $ R [ {\mathcal X} ] $ in the variables $ {\mathcal X} = \{ X _ {1} \dots X _ {n} \} $:

1) Provide algorithms turning $ R [ {\mathcal X} ] $ into an effective ring.

If $ R $ is a field, the algorithm also solves the following two problems:

2) Given a finite set of polynomial equations over $ R $ in the variables $ {\mathcal X} $, produce an "upper triangular form" of the equations, thus providing solutions by elimination of variables.

3) Given a finite subset $ B $ of $ R [ {\mathcal X} ] $, produce an effectively computable $ R $- linear projection mapping onto a complement in $ R [ {\mathcal X} ] $ of $ ( B ) $, the ideal of $ R [ {\mathcal X} ] $ generated by $ B $.

Monomials.

Denote by $ {\mathcal M} $ the monoid of all monomials of $ R [ {\mathcal X} ] $. For $ m \in {\mathcal M} $ there is an $ a \in \mathbf N ^ {n} $ such that $ m = X ^ {a} = X _ {1} ^ {a _ {1} } \dots X _ {n} ^ {a _ {n} } $. A total order (cf. also Totally ordered set) on $ {\mathcal M} $ is called a reduction ordering if, for all $ m,m ^ \prime ,m ^ {\prime \prime } \in {\mathcal M} $,

$ m \neq 1 $ implies $ 1 < m $;

$ m ^ \prime < m ^ {\prime \prime } $ implies $ m m ^ \prime < m m ^ {\prime \prime } $.

An important example is the lexicographical ordering (coming from the identification of $ {\mathcal M} $ with $ \mathbf N ^ {n} $). Starting from any reduction ordering $ < $ and a vector $ c \in \mathbf N $, a new reduction ordering $ < _ {c} $ can be obtained by demanding that $ X ^ {a} < X ^ {b} $ if and only if either $ a \cdot c < b \cdot c $ or $ a \cdot c = b \cdot c $ and $ X ^ {a} < X ^ {b} $. If $ c $ is the all-one vector, the order refines the partial order by total degree.

Termination of the Buchberger algorithm follows from the fact that a reduction ordering on $ {\mathcal M} $ is well founded.

These orderings are used to compare (sets of) polynomials. To single out the highest monomial and coefficient from a non-zero polynomial $ f \in R [ {\mathcal X} ] $, set

$$ { \mathop{\rm lm} } _ {f} = \max \left \{ {m \in {\mathcal M} } : {f _ {m} \neq 0 } \right \} , $$

$$ { \mathop{\rm lc} } _ {f} = \textrm{ the coefficient of the monomial } { \mathop{\rm lm} } _ {f} \textrm{ of } f, { \mathop{\rm lt} } _ {f} = { \mathop{\rm lc} } _ {f} { \mathop{\rm lm} } _ {f} . $$

The letters $ { \mathop{\rm lm} } $, $ { \mathop{\rm lc} } $, $ { \mathop{\rm lt} } $ stand for leading monomial, leading coefficient and leading term, respectively.

The Buchberger algorithm in its simplest form.

Let $ R $ be a field and $ B $ a finite subset of $ R [ {\mathcal X} ] $. Let $ { \mathop{\rm Reduce} } ( B,f ) $ denote a remainder of $ f $ with respect to $ B $, that is, the result of iteratively replacing $ f $ by a polynomial of the form $ f - ( { {{ \mathop{\rm lt} } _ {f} } / { { \mathop{\rm lt} } _ {b} } } ) b $ with $ b \in B $ such that $ { {{ \mathop{\rm lm} } _ {b} } \mid { { \mathop{\rm lm} } _ {f} } } $ as often as possible. This is effective because $ < $ is well founded. The result is not uniquely determined by $ < $. Given $ f,g \in R [ {\mathcal X} ] $, their $ S $- polynomial is

$$ S ( f,g ) = 0 \textrm{ if } f = 0 \textrm{ or } g = 0, $$

$$ S ( f,g ) = { \frac{ { \mathop{\rm lt} } _ {g} }{ { \mathop{\rm gcd} } ( { \mathop{\rm lm} } _ {f} , { \mathop{\rm lm} } _ {g} ) } } f - { \frac{ { \mathop{\rm lt} } _ {f} }{ { \mathop{\rm gcd} } ( { \mathop{\rm lm} } _ {f} , { \mathop{\rm lm} } _ {g} ) } } g \textrm{ otherwise } . $$

The following routine is the Buchberger algorithm in its simplest form.

$ { \mathop{\rm GroebnerBasis} } ( B ) = $

$ {\mathcal P} = \{ \textrm{ unordered pairs } \textrm{ _ } { } B \} $;

while $ {\mathcal P} \neq \emptyset $ do

choose  $  \{ f,g \} \in {\mathcal P} $;

$ {\mathcal P} = {\mathcal P} \setminus \{ \{ f,g \} \} $;

$ c = { \mathop{\rm Reduce} } ( B, S ( f,g ) ) $;

if $ c \neq0 $ then

$ {\mathcal P} = {\mathcal P} \cup \{ {\{ b,c \} } : {b \in B } \} $;

$ B = B \cup \{ c \} $;

fi;

od; return  $  B $.

It terminates because the sequence of consecutive sets $ \{ { { \mathop{\rm lm} } _ {b} } : {b \in B } \} $, produced in the course of the algorithm, descends with respect to $ < $.

Note that $ ( B ) $ is an invariant of the algorithm. Consequently, if $ C $ is the output resulting from input $ B $, then $ ( C ) = ( B ) $. The output $ C $ has the following characteristic property:

$$ ( \left \{ { { \mathop{\rm lt} } _ {f} } : {f \in ( C ) } \right \} ) = ( \left \{ { { \mathop{\rm lt} } _ {f} } : {f \in C } \right \} ) . $$

A subset $ C $ of $ R [ {\mathcal X} ] $ with this property is called a Gröbner basis. Equivalently, a subset $ B $ of $ R [ {\mathcal X} ] $ is a Gröbner basis if and only if, for all $ f,g \in B $, one has $ { \mathop{\rm Reduce} } ( B,S ( f,g ) ) =0 $.

Suppose that $ B $ is a Gröbner basis. Then $ { \mathop{\rm Reduce} } ( B,f ) $ is uniquely determined for each $ f \in R [ {\mathcal X} ] $. A monomial is called standard with respect to an ideal $ I $ if it is not of the form $ { \mathop{\rm lm} } _ {f} $ for some $ f \in I $. The mapping $ f \mapsto { \mathop{\rm Reduce} } ( B,f ) $ is an effectively computable projection onto the $ R $- span of all standard monomials with respect to $ ( B ) $, which is a complement as in Problem 3) above.

A reduction ordering $ < $ with $ X _ {1} < \dots < X _ {n} $ is called an elimination ordering if $ X _ {i} ^ {j} < X _ {i + 1 } $ for $ j \in \mathbf N $ and $ i = 1 \dots n - 1 $. If $ C $ is a Gröbner basis with respect to an elimination ordering, then $ ( C ) \cap R [ X _ {1} \dots X _ {i} ] $ is the ideal of $ R [ X _ {1} \dots X _ {i} ] $ generated by $ C \cap R [ X _ {1} \dots X _ {i} ] $. This is the key to solving Problem 2.

The Buchberger algorithm can be generalized to arbitrary effective rings $ R $. By keeping track of intermediate results in the algorithms, it is possible to express the Gröbner basis $ C $ coming from input $ B $ as an $ R [ {\mathcal X} ] $- linear combination of $ B $. Using this, one can find a particular solution, as well as a finite generating set for all homogeneous solutions to an $ R [ {\mathcal X} ] $- linear equation, and hence a solution to Problem 1.

General introductions to the Buchberger algorithm can be found in [a1], [a5], [a6]. More advanced applications can be found in [a7], which also contains an indication of the badness of the complexity of finding Gröbner bases. Buchberger algorithms over more general coefficient domains $ R $ are dealt with in [a8], and generalizations from $ R [ {\mathcal X} ] $ to particular non-commutative algebras (e.g., the universal enveloping algebra of a Lie algebra) in [a2].

References

[a1]	W.W. Adam, P. Loustaunau, "An introduction to Gröbner bases" , Graduate Studies in Math. , 3 , Amer. Math. Soc. and Oxford Univ. Press (1994) MR1287608
[a2]	J. Apel, W. Lassner, "An extension of Buchberger's algorithm and calculations in enveloping fields of Lie algebras" J. Symb. Comp. , 6 (1988) pp. 361–370 MR988423
[a3]	B. Buchberger, "An algorithmic criterion for the solvability of algebraic systems of equations" Aequationes Math. , 4 (1965) pp. 374–383 (This paper is a published version of the author's Ph.D. Thesis (Innsbruck, 1965) under the advice of Prof. W. Gröbner)
[a4]	B. Buchberger, "Gröbner bases: an algorithmic method in polynomial ideal theory" N.K. Bose (ed.) , Recent Trends in Multidimensional System Theory , Reidel (1985) pp. 184–232 Zbl 0587.13009
[a5]	D. Cox, J. Little, D. O'Shea, "Ideals, varieties, and algorithms" , Springer (1992) MR1189133 Zbl 0756.13017
[a6]	D. Eisenbud, "Commutative algebra with a view toward algebraic geometry" , GTM , 150 , Springer (1995) Zbl 0819.13001
[a7]	L. (ed.) Robbiano, "Computational aspects of commutative algebra" J. Symb. Comp. , special issue (1989) MR1262830 Zbl 0796.00017
[a8]	W. Trinks, "Über B. Buchbergers Verfahren, Systeme algebraischer Gleichungen zu lösen" J. Number Th. , 10 (1978) pp. 475–488 MR0515056 Zbl 0404.13004