Namespaces
Variants
Actions

Difference between revisions of "Buchberger algorithm"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (MR/ZBL numbers added)
m (tex encoded by computer)
Line 1: Line 1:
A [[Noetherian ring|Noetherian ring]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b1109801.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b1109802.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b1109803.png" /> and unknown <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b1109804.png" /> (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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b1109805.png" />, the Buchberger algorithm (cf. [[#References|[a3]]], [[#References|[a4]]]) solves the following problem concerning the polynomial ring <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b1109806.png" /> in the variables <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b1109807.png" />:
+
<!--
 +
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.
 +
-->
  
1) Provide algorithms turning <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b1109808.png" /> into an effective ring.
+
{{TEX|auto}}
 +
{{TEX|done}}
  
If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b1109809.png" /> is a [[Field|field]], the algorithm also solves the following two problems:
+
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} \} $:
  
2) Given a finite set of polynomial equations over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098010.png" /> in the variables <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098011.png" />, produce an "upper triangular form" of the equations, thus providing solutions by elimination of variables.
+
1) Provide algorithms turning  $  R [ {\mathcal X} ] $
 +
into an effective ring.
  
3) Given a finite subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098012.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098013.png" />, produce an effectively computable <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098014.png" />-linear projection mapping onto a complement in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098015.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098016.png" />, the ideal of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098017.png" /> generated by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098018.png" />.
+
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.==
 
==Monomials.==
Denote by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098019.png" /> the [[Monoid|monoid]] of all monomials of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098020.png" />. For <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098021.png" /> there is an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098022.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098023.png" />. A total order (cf. also [[Totally ordered set|Totally ordered set]]) on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098024.png" /> is called a reduction ordering if, for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098025.png" />,
+
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} $,
  
<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098026.png" /> implies <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098027.png" />;
+
$  m \neq 1 $
 +
implies $  1 < m $;
  
<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098028.png" /> implies <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098029.png" />.
+
$  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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098030.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098031.png" />). Starting from any reduction ordering <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098032.png" /> and a vector <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098033.png" />, a new reduction ordering <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098034.png" /> can be obtained by demanding that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098035.png" /> if and only if either <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098036.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098037.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098038.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098039.png" /> is the all-one vector, the order refines the partial order by total degree.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098040.png" /> is well founded.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098041.png" />, set
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098042.png" /></td> </tr></table>
+
$$
 +
{ \mathop{\rm lm} } _ {f} = \max  \left \{ {m \in {\mathcal M} } : {f _ {m} \neq 0 } \right \} ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098043.png" /></td> </tr></table>
+
$$
 +
{ \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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098044.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098045.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098046.png" /> stand for leading monomial, leading coefficient and leading term, respectively.
+
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.==
 
==The Buchberger algorithm in its simplest form.==
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098047.png" /> be a field and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098048.png" /> a finite subset of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098049.png" />. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098050.png" /> denote a remainder of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098051.png" /> with respect to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098052.png" />, that is, the result of iteratively replacing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098053.png" /> by a polynomial of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098054.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098055.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098056.png" /> as often as possible. This is effective because <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098057.png" /> is well founded. The result is not uniquely determined by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098058.png" />. Given <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098059.png" />, their <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098061.png" />-polynomial is
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098062.png" /></td> </tr></table>
+
$$
 +
S ( f,g ) = 0  \textrm{ if  } f = 0  \textrm{ or  }  g = 0,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098063.png" /></td> </tr></table>
+
$$
 +
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.
 
The following routine is the Buchberger algorithm in its simplest form.
  
  <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098064.png" />
+
$ { \mathop{\rm GroebnerBasis} } ( B ) = $
  
  <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098065.png" />;
+
$ {\mathcal P} = \{ \textrm{ unordered  pairs  }  \textrm{ _ } {  } B \} $;
  
  while <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098066.png" /> do
+
   
 +
while $  {\mathcal P} \neq \emptyset $
 +
do
  
  choose <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098067.png" />;
+
  choose $  \{ f,g \} \in {\mathcal P} $;
  
  <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098068.png" />;
+
$ {\mathcal P} = {\mathcal P} \setminus  \{ \{ f,g \} \} $;
  
  <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098069.png" />;
+
$ c = { \mathop{\rm Reduce} } ( B, S ( f,g ) ) $;
  
  if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098070.png" /> then
+
   
 +
if $  c \neq0 $
 +
then
  
  <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098071.png" />;
+
$ {\mathcal P} = {\mathcal P} \cup \{ {\{ b,c \} } : {b \in B } \} $;
  
  <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098072.png" />;
+
$ B = B \cup \{ c \} $;
  
  fi;
+
   
 +
fi;
  
  od; return <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098073.png" />.
+
  od; return $  B $.
  
It terminates because the sequence of consecutive sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098074.png" />, produced in the course of the algorithm, descends with respect to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098075.png" />.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098076.png" /> is an invariant of the algorithm. Consequently, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098077.png" /> is the output resulting from input <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098078.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098079.png" />. The output <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098080.png" /> has the following characteristic property:
+
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:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098081.png" /></td> </tr></table>
+
$$
 +
( \left \{ { { \mathop{\rm lt} } _ {f} } : {f \in ( C ) } \right \} ) = ( \left \{ { { \mathop{\rm lt} } _ {f} } : {f \in C } \right \} ) .
 +
$$
  
A subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098082.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098083.png" /> with this property is called a Gröbner basis. Equivalently, a subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098084.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098085.png" /> is a Gröbner basis if and only if, for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098086.png" />, one has <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098087.png" />.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098088.png" /> is a Gröbner basis. Then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098089.png" /> is uniquely determined for each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098090.png" />. A monomial is called standard with respect to an ideal <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098091.png" /> if it is not of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098092.png" /> for some <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098093.png" />. The mapping <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098094.png" /> is an effectively computable projection onto the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098095.png" />-span of all standard monomials with respect to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098096.png" />, which is a complement as in Problem 3) above.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098097.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098098.png" /> is called an elimination ordering if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098099.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b110980100.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b110980101.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b110980102.png" /> is a Gröbner basis with respect to an elimination ordering, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b110980103.png" /> is the ideal of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b110980104.png" /> generated by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b110980105.png" />. This is the key to solving Problem 2.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b110980106.png" />. By keeping track of intermediate results in the algorithms, it is possible to express the Gröbner basis <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b110980107.png" /> coming from input <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b110980108.png" /> as an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b110980109.png" />-linear combination of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b110980110.png" />. Using this, one can find a particular solution, as well as a finite generating set for all homogeneous solutions to an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b110980111.png" />-linear equation, and hence a solution to Problem 1.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b110980112.png" /> are dealt with in [[#References|[a8]]], and generalizations from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b110980113.png" /> to particular non-commutative algebras (e.g., the universal enveloping algebra of a Lie algebra) in [[#References|[a2]]].
+
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====
 
====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>
 
<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>

Revision as of 06:29, 30 May 2020


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