View source for Buchberger algorithm

<!--
b1109801.png
$#A+1 = 112 n = 0
$#C+1 = 112 : ~/encyclopedia/old_files/data/B110/B.1100980 Buchberger algorithm
Automatically converted into TeX, above some diagnostics.
Please remove this comment and the {{TEX|auto}} line below,
if TeX found to be correct.
-->

{{TEX|auto}}
{{TEX|done}}

A [[Noetherian ring|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. [[#References|[a3]]], [[#References|[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|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|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|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 [[#References|[a1]]], [[#References|[a5]]], [[#References|[a6]]]. More advanced applications can be found in [[#References|[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 [[#References|[a8]]], and generalizations from  $  R [ {\mathcal X} ] $
to particular non-commutative algebras (e.g., the universal enveloping algebra of a Lie algebra) in [[#References|[a2]]].

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top"> W.W. Adam, P. Loustaunau, "An introduction to Gröbner bases" , ''Graduate Studies in Math.'' , '''3''' , Amer. Math. Soc. and Oxford Univ. Press (1994) {{MR|1287608}} {{ZBL|}} </TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top"> 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 {{MR|988423}} {{ZBL|}} </TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top"> 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)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top"> 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 {{MR|}} {{ZBL|0587.13009}} </TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top"> D. Cox, J. Little, D. O'Shea, "Ideals, varieties, and algorithms" , Springer (1992) {{MR|1189133}} {{ZBL|0756.13017}} </TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top"> D. Eisenbud, "Commutative algebra with a view toward algebraic geometry" , ''GTM'' , '''150''' , Springer (1995) {{MR|}} {{ZBL|0819.13001}} </TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top"> L. (ed.) Robbiano, "Computational aspects of commutative algebra" ''J. Symb. Comp.'' , '''special issue''' (1989) {{MR|1262830}} {{ZBL|0796.00017}} </TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top"> W. Trinks, "Über B. Buchbergers Verfahren, Systeme algebraischer Gleichungen zu lösen" ''J. Number Th.'' , '''10''' (1978) pp. 475–488 {{MR|0515056}} {{ZBL|0404.13004}} </TD></TR></table>