Buchberger algorithm

A Noetherian ring 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 with and unknown (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 , the Buchberger algorithm (cf. [a3], [a4]) solves the following problem concerning the polynomial ring in the variables :

1) Provide algorithms turning into an effective ring.

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

2) Given a finite set of polynomial equations over in the variables , produce an "upper triangular form" of the equations, thus providing solutions by elimination of variables.

3) Given a finite subset of , produce an effectively computable -linear projection mapping onto a complement in of , the ideal of generated by .

Monomials.

Denote by the monoid of all monomials of . For there is an such that . A total order (cf. also Totally ordered set) on is called a reduction ordering if, for all ,

implies ;

implies .

An important example is the lexicographical ordering (coming from the identification of with ). Starting from any reduction ordering and a vector , a new reduction ordering can be obtained by demanding that if and only if either or and . If 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 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 , set

The letters , , stand for leading monomial, leading coefficient and leading term, respectively.

The Buchberger algorithm in its simplest form.

Let be a field and a finite subset of . Let denote a remainder of with respect to , that is, the result of iteratively replacing by a polynomial of the form with such that as often as possible. This is effective because is well founded. The result is not uniquely determined by . Given , their -polynomial is

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

;

while  do

 choose ;

 ;

 ;

 if  then

  ;

  ;

 fi;

od; return .

It terminates because the sequence of consecutive sets , produced in the course of the algorithm, descends with respect to .

Note that is an invariant of the algorithm. Consequently, if is the output resulting from input , then . The output has the following characteristic property:

A subset of with this property is called a Gröbner basis. Equivalently, a subset of is a Gröbner basis if and only if, for all , one has .

Suppose that is a Gröbner basis. Then is uniquely determined for each . A monomial is called standard with respect to an ideal if it is not of the form for some . The mapping is an effectively computable projection onto the -span of all standard monomials with respect to , which is a complement as in Problem 3) above.

A reduction ordering with is called an elimination ordering if for and . If is a Gröbner basis with respect to an elimination ordering, then is the ideal of generated by . This is the key to solving Problem 2.

The Buchberger algorithm can be generalized to arbitrary effective rings . By keeping track of intermediate results in the algorithms, it is possible to express the Gröbner basis coming from input as an -linear combination of . Using this, one can find a particular solution, as well as a finite generating set for all homogeneous solutions to an -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 are dealt with in [a8], and generalizations from 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)
[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
[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
[a5]	D. Cox, J. Little, D. O'Shea, "Ideals, varieties, and algorithms" , Springer (1992)
[a6]	D. Eisenbud, "Commutative algebra with a view toward algebraic geometry" , GTM , 150 , Springer (1995)
[a7]	L. (ed.) Robbiano, "Computational aspects of commutative algebra" J. Symb. Comp. , special issue (1989)
[a8]	W. Trinks, "Über B. Buchbergers Verfahren, Systeme algebraischer Gleichungen zu lösen" J. Number Th. , 10 (1978) pp. 475–488