# 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].

How to Cite This Entry:
Buchberger algorithm. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Buchberger_algorithm&oldid=46215
This article was adapted from an original article by A.M. Cohen (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article