Buchberger algorithm

The Buchberger algorithm (after Bruno Buchberger ) is in algebra a method for calculating a Gröbner basis of an ideal in a polynomial ring .

Due to the possibility of algorithmically determining Gröbner bases, many problems of computer algebra systems that can be solved with it can be solved, for example the problem of ideal affiliation or the solving of certain non-linear systems of equations (as a description of an affine variety ).

The Buchberger criterion

Be

• ${\displaystyle K}$a body and the corresponding polynomial ring in symbols, ${\displaystyle {\mathcal {P}}=K[X_{1},\ldots ,X_{n}]}$ ${\displaystyle n}$
• ${\displaystyle I\subseteq {\mathcal {P}}}$ an ideal
• a monomial order " " given up, ${\displaystyle \prec }$ ${\displaystyle {\mathcal {P}}}$
• defines the generalized polynomial division with multiple dividing polynomials.

Furthermore, for every two polynomials ${\displaystyle f,g\in {\mathcal {P}}\setminus \{0\}}$

${\displaystyle S(f,g)={\frac {\operatorname {kgV} (\operatorname {LT} (f),\operatorname {LT} (g))}{\operatorname {LT} (f)}}f-{\frac {\operatorname {kgV} (\operatorname {LT} (f),\operatorname {LT} (g))}{\operatorname {LT} (g)}}g}$

explained, where denotes the leading term of a polynomial , i.e. the largest monomial with respect to the monomial order together with its coefficient. ${\displaystyle \operatorname {LT} (f)}$ ${\displaystyle f}$ ${\displaystyle \prec }$

The Buchberger criterion then says that a generating system of is a Gröbner basis if and only if all of them yield with (generalized polynomial) division by the remainder . ${\displaystyle H=(h_{1},\dots ,h_{k})}$ ${\displaystyle I}$ ${\displaystyle S(h_{i},h_{j})}$ ${\displaystyle H}$ ${\displaystyle 0}$

The algorithm

The Buchberger algorithm can then be formulated as follows.

The idea is that gradually all are formed (for all pairs from different generators and ) and those from different residues are added to the generator system. With the generating system expanded in this way, the process is repeated until finally all of them disappear; thus the Buchberger criterion is fulfilled. ${\displaystyle S(h_{i},h_{j})}$ ${\displaystyle h_{i}}$ ${\displaystyle h_{j}}$ ${\displaystyle 0}$ ${\displaystyle S(h_{i},h_{j})}$

 INPUT:  ${\displaystyle H=(h_{1},\dots ,h_{s})}$
 OUTPUT: Gröbnerbasis  ${\displaystyle G=(g_{1},\dots ,g_{t})}$
 INIT:  ${\displaystyle G:=H}$
 1. DO
 2.      ${\displaystyle G':=G}$
 3.     FOREACH  ${\displaystyle p,q\in G',p\neq q}$
 4.          ${\displaystyle s=Rest(S(p,q),G)}$
 5.         IF  ${\displaystyle s\neq 0}$ THEN  ${\displaystyle G:=G\cup \{s\}}$
 6.     NEXT
 7. UNTIL  ${\displaystyle G=G'}$

Since it is true in every iteration of the inner loop , it is also , so in the end you really get a generating system from (and not from a larger ideal). That this generating system is a Gröbner basis follows from the Buchberger criterion. Note: applies exactly when dividing by a Gröbner basis. ${\displaystyle s\in I}$ ${\displaystyle \langle G\cup \{s\}\rangle =\langle G\rangle =I}$ ${\displaystyle I}$ ${\displaystyle s\in I\Rightarrow s=0}$

If after the -th iteration of the outer loop the ideal is generated by the leading monomials of , then we get a chain of ideals. Since a chain of ideals cannot rise endlessly (real) (a simple consequence from Hilbert's basic theorem ), this chain must ultimately remain constant. However, this means that from then on no new leading monomials will be added; the algorithm terminates at this point, i.e. H. after a finite number of steps. ${\displaystyle j}$ ${\displaystyle I_{j}}$ ${\displaystyle G_{j}}$ ${\displaystyle I_{1}\subseteq I_{2}\subseteq \dots \subseteq I}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle G}$

example

The Gröbner basis that the algorithm delivers quickly becomes very large and therefore confusing; in addition, evaluating the polynomial divisions is also quite time-consuming. Therefore, the algorithm shall only be presented here for a very small and simple example: Let and im . ${\displaystyle h_{1}=X}$ ${\displaystyle h_{2}=X^{2}+1}$ ${\displaystyle \mathbb {R} [X]}$

Run the Outer Loop	${\displaystyle G}$	${\displaystyle p}$	${\displaystyle q}$	${\displaystyle s=S(p,q)}$	${\displaystyle Rest}$
First: consider a couple	${\displaystyle (X,X^{2}+1)}$	${\displaystyle X}$	${\displaystyle X^{2}+1}$	${\displaystyle {\frac {X^{2}}{X}}X-{\frac {X^{2}}{X^{2}}}(X^{2}+1)=-1}$	${\displaystyle -1}$
Second: three pairs to consider	${\displaystyle (X,X^{2}+1,-1)}$	${\displaystyle X}$	${\displaystyle X^{2}+1}$	${\displaystyle {\frac {X^{2}}{X}}X-{\frac {X^{2}}{X^{2}}}(X^{2}+1)=-1}$	${\displaystyle 0}$
		${\displaystyle X}$	${\displaystyle -1}$	${\displaystyle {\frac {X}{X}}X-{\frac {X}{-1}}(-1)=0}$	${\displaystyle 0}$
		${\displaystyle X^{2}+1}$	${\displaystyle -1}$	${\displaystyle {\frac {X^{2}}{X^{2}}}(X^{2}+1)-{\frac {X^{2}}{-1}}(-1)=1}$	${\displaystyle 0}$

Thus, the Buchberger criterion is already met after the addition has been made as a producer and the algorithm aborts because no new producer was added in the second run of the loop . ${\displaystyle -1}$ ${\displaystyle G}$

See also

• Quine and McCluskey method

Individual evidence

1. ↑ Cox, Little, O'Shea: Ideals, Varieties, and Algorithms. 2007, 2.6. Theorem 6.
2. ↑ Cox, Little, O'Shea: Ideals, Varieties, and Algorithms. 2007, 2.7. Theorem 2.

literature

• David A. Cox , John B. Little , Donal O'Shea : Ideals, Varieties, and Algorithms . An Introduction to Computational Algebraic Geometry and Commutative Algebra (=  Undergraduate Texts in Mathematics ). 3. Edition. Springer, New York 2007, ISBN 978-0-387-35650-1 , 2.7. Buchberger's Algorithm.