Groebner base

A Gröbner basis (according to Bruno Buchberger , 1965) or standard basis (according to Heisuke Hironaka , 1964) is a finite generating system for an ideal in the polynomial ring over the body , which is particularly well suited to decide whether a given polynomial belongs to the ideal or Not. ${\displaystyle I}$ ${\displaystyle K[X_{1},\ldots ,X_{n}]}$ ${\displaystyle K}$

Buchberger developed Gröbner bases in 1965 in his dissertation with Wolfgang Gröbner and named them after Gröbner.

Motivation: Ideal membership problem and generalized polynomial division

The ideal belonging problem

If the ideal is generated by the polynomials , then a polynomial belongs to if and only if it is a linear combination ${\displaystyle I=(g_{1},\ldots ,g_{n})\subseteq K[X_{1},\dots ,X_{k}]}$ ${\displaystyle I}$ ${\displaystyle g_{1},\ldots ,g_{n}}$ ${\displaystyle f}$ ${\displaystyle I}$ ${\displaystyle f}$

${\displaystyle f=a_{1}g_{1}+\dots +a_{n}g_{n}}$

can be written with polynomials . ${\displaystyle a_{1},\dots ,a_{n}\in K[X_{1},\dots ,X_{k}]}$

One can now try to find such a representation with the help of the polynomial division with remainder by dividing until the remainder obtained disappears and the division thus works:

${\displaystyle f=a_{1}g_{1}+r_{1}}$

${\displaystyle f=a_{1}g_{1}+a_{2}g_{2}+r_{2}}$

...

However, there are two problems:

1. In the case of multivariate polynomials , the terms can no longer be ordered "according to size" without further ado, which is necessary for the polynomial division. ${\displaystyle p\in K[X_{1},\ldots ,X_{k}]}$
2. Can we be sure that repeated polynomial division always results in the remainder 0?

The first problem can be solved quite simply by choosing a monomial order. Then the terms of each polynomial can be ordered according to this order; Above all, we can now speak of the leading term of a polynomial, i.e. the largest monomial with its coefficient in terms of the monomial order. The disadvantage remains that the arrangement of the monomials and also the result of the polynomial divisions depend on the choice of the monomial order. ${\displaystyle {\rm {LT}}}$

The second problem is more difficult because it is actually not solvable if the generating polynomials are fixed. It can only be solved by changing the generating system appropriately. A Groebner basis turns out to be a suitable generating system.

Generalized polynomial division

The task of the generalized polynomial division is now: For a polynomial and several polynomials , polynomials are to be found that satisfy the equation ${\displaystyle f}$ ${\displaystyle g_{1},\dots ,g_{n}}$ ${\displaystyle a_{1},\dots ,a_{n},r}$

${\displaystyle f=a_{1}g_{1}+\dots +a_{n}g_{n}+r}$

fulfill.

The following procedure is suitable for this:

1. Start with . ${\displaystyle a_{1}=\dots =a_{n}=r=0}$
2. If so , stop, otherwise compare everyone one after the other to see if they share. ${\displaystyle f=0}$ ${\displaystyle {\rm {LT}}(g_{i})}$ ${\displaystyle {\rm {LT}}(f)}$
3. If so, replace through and through and go to step 2. ${\displaystyle a{\rm {LT}}(g_{i})={\rm {LT}}(f)}$ ${\displaystyle a_{i}}$ ${\displaystyle a_{i}+a}$ ${\displaystyle f}$ ${\displaystyle f-ag_{i}}$
4. If no one shares, replace through and through and go to step 2. ${\displaystyle {\rm {LT}}(f)}$ ${\displaystyle {\rm {LT}}(g_{i})}$ ${\displaystyle r}$ ${\displaystyle r+{\rm {LT}}(f)}$ ${\displaystyle f}$ ${\displaystyle f-{\rm {LT}}(f)}$

Then in each step is the equation

${\displaystyle f_{urspr}=a_{1}g_{1}+\dots +a_{n}g_{n}+r+f_{aktuell}}$

fulfilled, and finally, if , the desired representation is found. ${\displaystyle f_{aktuell}=0}$

With this division we have reduced the problem to a smaller polynomial as desired, because it is exactly when . If so, that's clear, and . However , we cannot decide whether or not : ${\displaystyle f\in I}$ ${\displaystyle r\in I}$ ${\displaystyle r=0}$ ${\displaystyle f\in I}$ ${\displaystyle r\neq 0}$ ${\displaystyle r\in I}$ ${\displaystyle r\not \in I}$

Example: Be , and . If you test the generating polynomials one after the other (i.e. in the ascending order of the indices) and apply the division described, you get: ${\displaystyle g_{1}=x}$ ${\displaystyle g_{2}=x^{2}+1}$ ${\displaystyle f=g_{1}+g_{2}=x^{2}+x+1}$

${\displaystyle f=xg_{1}+(x+1)=(x+1)g_{1}+1}$

Obviously, however , also applies (namely ). So in general one can not infer from that and thus holds. ${\displaystyle f=g_{1}+g_{2}\in I}$ ${\displaystyle r=1\in I}$ ${\displaystyle 1=-xg_{1}+g_{2}}$ ${\displaystyle r\neq 0}$ ${\displaystyle r\not \in I}$ ${\displaystyle f\not \in I}$

definition

A generating system of is a Gröbner basis (with respect to a monomial order ) of , if for every polynomial there is a whose leading monomial divides the leading monomial of . ${\displaystyle G=(g_{1},\ldots ,g_{n})}$ ${\displaystyle I}$ ${\displaystyle <}$ ${\displaystyle I}$ ${\displaystyle f\in I\setminus \{0\}}$ ${\displaystyle g_{i}}$ ${\displaystyle f}$

A Gröbner basis is called reduced if all are normalized and no monomial of can be represented by the leading terms of the other Gröbner basis polynomials, i.e. no monomial of in lies. One can show that every ideal (for a given monomial order) has a uniquely determined reduced Gröbner basis. ${\displaystyle G}$ ${\displaystyle g\in G}$ ${\displaystyle g}$ ${\displaystyle g}$ ${\displaystyle \langle \{{\rm {{LT}(g'):g'\in G\setminus \{g\}\}\rangle }}}$

Applications

The concept of Gröbnerbasen initially provides a solution to the problem of ideal belonging. In connection with this, other problems can also be solved (or at least simplified).

Solution of the ideal belonging problem

With the method described above, this becomes a representation that cannot be further reduced

${\displaystyle f=k_{1}g_{1}+\ldots +k_{n}g_{n}+r}$

found with respect to a Gröbner basis of the ideal , then exactly if . But since there is a Gröbner basis, this again applies if and only if , according to the assumption, no leading monom of one divides the leading monom of . ${\displaystyle G=(g_{1},\ldots ,g_{n})}$ ${\displaystyle I}$ ${\displaystyle f\in I}$ ${\displaystyle r\in I}$ ${\displaystyle G}$ ${\displaystyle r=0}$ ${\displaystyle g_{i}}$ ${\displaystyle r}$

Gröbner bases can be calculated using the Buchberger algorithm . This means that the problem of whether a polynomial belongs to an ideal or not can be solved by computer algebra systems .

Example: If the generating polynomials are given as in the example above , as well as , then the polynomial division had returned a remainder . ${\displaystyle g_{1}=x,g_{2}=x^{2}+1}$ ${\displaystyle f=g_{1}+g_{2}=x^{2}+x+1}$ ${\displaystyle 1}$

Turning first to the Buchberger algorithm to this example, so we get the (unreduced) Gröbner basis of . With regard to this divisor, the division is not yet completed here, because it is with : ${\displaystyle (x,x^{2}+1,-1)}$ ${\displaystyle I}$ ${\displaystyle g_{3}=-1}$

${\displaystyle f=xg_{1}+(x+1)=(x+1)g_{1}+1=(x+1)g_{1}+(-1)g_{3}}$

We also see here that the representation with regard to the Gröbner basis is not unique (da ), but depends on the order of the generating polynomials and the selected monomial order. ${\displaystyle f=g_{1}+g_{2}=(x+1)g_{1}-g_{3}}$

Polynomial systems of equations

A polynomial system of equations consists of a finite number of equations , where given polynomials are sought in indeterminates over a body and their common zeros . The solution set of such a system of equations describes an algebraic variety . This is apparently the same , where is the ideal generated by the polynomials. ${\displaystyle f_{1}(x)=0,\ldots ,f_{k}(x)=0}$ ${\displaystyle f_{1},\ldots ,f_{k}\in K[x_{1},\ldots ,x_{n}]}$ ${\displaystyle n}$ ${\displaystyle K}$ ${\displaystyle x\in K^{n}}$ ${\displaystyle \{x\in K^{n}:f_{1}(x)=\cdots =f_{k}(x)=0\}}$ ${\displaystyle \{x\in K^{n}:f(x)=0\quad \forall f\in I\}}$ ${\displaystyle I=(f_{1},\ldots ,f_{k})}$

If a certain system of polynomial equations is to be solved, it is sufficient to consider the ideal that is generated by the polynomials. Then it can be helpful to find a reduced Gröbner basis with the help of the Buchberger algorithm and a suitable lexicographical monomial order. The problem then remains of finding the zeros of these polynomials (e.g. approximately using numerical methods), but the polynomials to be examined still have a smaller number of variables and smaller degrees.

Example: What solutions does the following system of equations have? ${\displaystyle (x,y,z)\in \mathbb {R} ^{3}}$

${\displaystyle x^{2}+y^{2}+z^{2}-1=0}$

${\displaystyle x^{2}-y+z^{2}=0}$

${\displaystyle x-z=0}$

With the help of the computer one obtains the (reduced) Gröbner basis and for the lexicographical monomial order . The solutions sought are therefore exactly the solutions of the simpler system of equations ${\displaystyle x>y>z}$ ${\displaystyle g_{1}=x-z,g_{2}=-y+2z^{2}}$ ${\displaystyle g_{3}=z^{4}+{\frac {1}{2}}z^{2}-{\frac {1}{4}}}$

${\displaystyle x=z}$

${\displaystyle y=2z^{2}}$

${\displaystyle z^{4}+{\frac {1}{2}}z^{2}-{\frac {1}{4}}=0}$

And we see that the solution set consists of only two points: (the two other solutions are not included in). ${\displaystyle \left\{(z,2z^{2},z):z=\pm {\frac {1}{2}}{\sqrt {{\sqrt {5}}-1}}\right\}}$ ${\displaystyle \pm {\frac {1}{2}}{\sqrt {-{\sqrt {5}}-1}}}$ ${\displaystyle \mathbb {R} }$

Equality of ideals and algebraic varieties

Since (for a given monomial order) the reduced Gröbner basis of an ideal is uniquely determined, the equality of ideals can be investigated by forming the reduced Gröbner bases (for any monomial order). The ideals are exactly the same when these reduced Gröbner bases are the same.

In this way one can also investigate the equality of algebraic varieties from a purely arithmetic point of view , since these are clearly determined by their generating ideals. If the reduced Gröbner bases are the same, then the generating ideals and thus also the generated varieties are the same.

literature

• Heisuke Hironaka: Resolution of singularities of an algebraic variety over a field of characteristic zero , In: Annals of Mathematics 79 (1964), No. 1, pp. 109-326
• Bruno Buchberger: An algorithm to find the basic elements of the residual class ring according to a zero-dimensional polynomial ideal (PDF; 1.8 MB). Austria, University of Innsbruck, dissertation, 1965
• Bruno Buchberger: An algorithmic criterion for the solvability of an algebraic system of equations (PDF; 475 kB). Aequationes Mathematicae 4 (1970): 374-383.
• T. Becker, BV Weispfenning: Gröbner bases: a computational approach to commutative algebra . Graduate Texts in Mathematics: readings in mathematics. Vol. 141, New York: Springer Verlag, 1993
• David Cox; Little, John; O'Shea, Donald: Ideals, varieties, and algorithms . New York: Springer-Verlag, 1997
• Joachim from z. Gathen, Jürgen Gerhard: Modern Computer Algebra . Cambridge University Press, 1999