Groebner basis

• Dr. Bruno Buchberger, Institute for Symbolic Computation, Johannes Kepler University, Hagenberg, Austria

• Manuel Kauers, Institute for Symbolic Computation, Johannes Kepler University, Hagenberg, Austria

A Gröbner basis is a set of multivariate nonlinear polynomials enjoying certain properties that allow simple algorithmic solutions for many fundamental problems in mathematics and natural and technical sciences.

Examples of such problems are: the solution of algebraic systems of equations, the representability of polynomials in terms of other polynomials, the analysis and construction of nonlinear cryptosystems, the closed form summation and integration of expressions involving special functions, the closed form solution of linear boundary value problems (differential equations). Amazingly, also problems that seem to be far away form algebra as, for example, the automated proof and discovery of geometrical theorems, the construction of graph colorings and the solution of Sudoku games can be reduced to Gröbner bases computations. Examples of problems in natural and technical sciences that have recently been solved by the Gröbner bases methodology are intelligent control of oil platforms, reverse engineering of software, finding genetic relationship between species, and solving the inverse robotic kinematics.

Here is a typical example of a Gröbner basis consisting of three polynomials in three variables:

\[ \{x^3 - x^2+2, y - 2x^2 +1, z - 3x+5\}. \]

In this example, we see one of the advantageous properties of Gröbner bases: The equation system

\[ x^3 - x^2+2=0,\quad y - 2x^2 +1=0,\quad z - 3x+5=0 \]

in this Gröbner basis form can be easily solved. Namely, one first will find the three possible solutions \(x\) of the first equation and then substitute each of these solutions into the second and third equation to determine the corresponding \(y\) and \(z\ ,\) respectively.

The fundamental insight and contribution of Gröbner bases theory is that every polynomial system, no matter how complicated, can be transformed---by an algorithm---into Gröbner basis form, see Buchberger's algorithm.

In this article, we will explain by examples the general notion of Gröbner basis, the fundamental mathematical properties of Gröbner bases, the algorithm for constructing Gröbner bases, and some example applications of Gröbner bases. The notion of Gröbner basis and the fundamental results of Gröbner bases theory was introduced by Bruno Buchberger [ 5, 6 ]. Further information can be found in the textbooks and survey articles on Gröbner bases given in the list of references [ 2, 3, 4, 7, 8, 9, 11, 14, 15, 16, 17, 18, 19, 20, 21, 22, 24, 29, 30, 32, 33, 35, 36, 39, 47, 48 ]. For a comprehensive collection of research articles, see [1].

The Notion of Gröbner bases

Gröbner bases are sets of multivariate polynomials satisfying certain conditions. There are numerous equivalent conditions by which Gröbner bases can be defined. We give here two of them.

Definition via the Leading Power Product Property

In this article, a "basis" is just a set \(B\) of multivariate polynomials, like \[ B=\{x z^2-3 y z+1,x^2-2 y,x y-5 z\}. \] Such a basis is called a Gröbner basis if and only if

all leading power products of linear combinations of polynomials in the basis are multiples of at least one of the leading power products in the set.

By a linear combination of polynomials we mean a sum of polynomial multiples of these polynomials. For example, \[ -2 y^2 z^2+15 y z^2-5 z=(-x y)(x z^2-3 y z+1)+(y z^2)(x^2-2 y)+(-3yz+1) (x y-5 z) \] is a linear combination of the polynomials \(x z^2-3 y z+1\ ,\) \(x^2-2 y\ ,\) and \(x y-5 z\ .\)

By a power product we mean polynomials that are obtained from the variables only by multiplication. For example, \(x^3 y^2\) is a power product. Every polynomial can be written uniquely as a linear combination of power products with constant coefficients. For example, the polynomial \[ -2 y^2 z^2+15 y z^2-5 z \] consists of the power products \(y^2z^2\ ,\) \(yz^2\ ,\) and \(z\) with coefficients \(-2\ ,\) \(15\ ,\) and \(-5\ ,\) respectively.

Figure 1: The multiples of \(x^3y^2\)

Multiplicative relations among power products can be visualized by arranging the power products into a grid as shown in Figure Figure 1 for two variables. The multiples of some power product, as for example \(x^3y^2\ ,\) can then be visualized by the shaded area in Figure Figure 1.

The leading power product of a polynomial is the largest power product appearing in the polynomial. For this, some ordering has to be imposed on the power products, for example (in the case of the three variables \(x,y,z\)) \[ 1 \prec x \prec y \prec z \prec x^2 \prec x y \prec x z \prec y^2 \prec y z \prec z^2 \prec x^3 \prec \dots \] In Figure Figure 2 a suitable ordering for the power products in two variables is shown. In Gröbner bases theory, the order can be chosen freely as long as \(1\) is the minimum element and \(u\prec v\) implies \(ut\prec vt\) for all power products \(u,v,t\ .\)

Figure 2: A degree ordering

With the ordering above, the leading power products of \[ x z^2-3 y z+1,\quad x^2-2 y,\quad x y-5 z \] are \(x z^2\ ,\) \(x^2\ ,\) and \(xy\ ,\) respectively.

The basis \[ B=\{x z^2-3 y z+1,x^2-2 y,x y-5 z\} \] is not a Gröbner basis because, as seen above, \[ -2 y^2 z^2+15 y z^2-5 z \] is a linear combination of the basis elements, but its leading power product \(y^2z^2\) is not a multiple of any of \(xz^2\ ,\) \(x^2\ ,\) and \(xy\ .\)

The phenomenon that linear combinations of basis elements may have a leading power product that is not a multiple of any of the leading power products in the basis comes from the fact that, by linear combination, multiples of leading polynomials of the basis polynomials may cancel. In our example, the power product \(x^2yz^2\) appears in \[ (-x y)(x z^2-3 y z+1)=-x^2yz^2+3xy^2z-xy \] and in \[ (y z^2)(x^2-2 y)=x^2yz^2-2y^2z^2 \] but disappears in their sum.

Definition via the Church-Rosser Property

An alternative definition of Gröbner bases is as follows. A basis is called a Gröbner basis if and only if

the division process with respect to the basis has the Church-Rosser property.

The division process for a polynomial with respect to a basis is a repeated subtraction by multiples of basis elements to the effect of replacing a power product in the polynomial by several power products that are smaller in the chosen ordering. This process is also called reduction. As an example, \[ 3x^3z+x^2z^2 \quad\to\quad x^2 z^2+6xyz \quad\to\quad 9xyz-x \quad\to\quad 45z^2-x \] is a chain of three reduction steps with respect to the basis \(B=\{x z^2-3 y z+1,x^2-2 y,x y-5 z\}\ .\) To explain the first arrow, observe that the polynomial on its right is obtained from the polynomial on the left by subtraction of \(3xz\) times the second basis element. By this operation, the term \(3x^3z\) got rewritten to the smaller term \(6xyz\ .\) Similarly, the second and third arrow are obtained using the \(x\) times the first and \(9z\) times the third basis element, respectively. The last polynomial, \(45z^2-x\ ,\) cannot be reduced any further. It is therefore called a remainder of \(3x^3z+x^2z^2\) upon division by \(B\ .\)

A binary relation like \(\to\) is said to have the Church-Rosser property if whenever \(f\) and \(g\) are connected by a path of arrows and reverse arrows, then \(f\) and \(g\) have some common successor \(u\) with respect to the relation (Figure Figure 3).

Figure 3: The Church-Rosser property

For example, consider \(f=3x^3z+3xyz-x\) and \(g=x^2z^2+30z^3\) and let \(\to\) be the reduction with respect to \(B=\{x z^2-3 y z+1,x^2-2 y,x y-5 z\}\ .\) Then \[ \begin{array}{rlll} f = 3x^3z+3xyz-x &\quad\leftarrow\quad 3x^3z+x^2 z^2&\qquad&\text{(by }x\text{ times the first basis element)}\\ &\quad\rightarrow\quad x^2z^2+6xyz&\qquad&\text{(by }3xz\text{ times the second basis element)}\\ &\quad\rightarrow\quad x^2z^2+30z^3=g&\qquad&\text{(by }6z\text{ times the third basis element)} \end{array} \] and \(f\) and \(g\) have indeed a common successor \(u=45z^2-x\ ,\) because \[ \begin{array}{rlll} f &\quad\rightarrow\quad 9x y z - x&\qquad&\text{(by }3xz\text{ times the second basis element)}\\ &\quad\rightarrow\quad 45z^2-x&\qquad&\text{(by }9z\text{ times the third basis element)}\\ \text{and}\quad g &\quad\rightarrow\quad 3xyz+30z^2-x&\qquad&\text{(by }x\text{ times the first basis element)}\\ &\quad\rightarrow\quad 45z^2-x&\qquad&\text{(by }3z\text{ times the third basis element)}. \end{array} \] However, \(B\) is not a Gröbner basis, because \(f=2 y^2 z^2-5 y\) and \(g=25 z^3-x y\) are also connected via \[ \begin{array}{rlll} f=2 y^2 z^2-5 y &\quad\leftarrow\quad x^2 y z^2 - 5 y&\qquad&\text{(by }yz^2\text{ times the second basis element)}\\ &\quad\rightarrow\quad 3 x y^2 z-x y-5 y&\qquad&\text{(by }xy\text{ times the first basis element)}\\ &\quad\rightarrow\quad -x y+15 y z^2-5 y&\qquad&\text{(by }3yz\text{ times the third basis element)}\\ &\quad\leftarrow\quad 5 x y z^2-x y&\qquad&\text{(by }5y\text{ times the first basis element)}\\ &\quad\rightarrow\quad 25 z^3-x y=g&\qquad&\text{(by }5z^2\text{ times the third basis element)} \end{array} \] but do not have a common successor \(u\ .\) (\(f\) cannot be reduced further and has thus no successor at all. Using the third basis element with multiplier \(-1\ ,\) the only successor of \(g\) is \(25 z^3 - 5 z \neq f\ .\))

It is not hard to see that this definition is equivalent to the previous (and to several other characterizations not mentioned here). These characterizations have in common that they are not constructive in the sense that they involve a statement about infinitely many objects ("all linear combinations" or "all pairs \(f\) and \(g\)"). Later, we will give another characterization of Gröbner bases by which it can be checked in finitely many steps whether a given basis is a Gröbner basis. The proof of this criterion is not trivial, and it is the corner stone of the Gröbner bases methodology.

Fundamental Properties of Gröbner Bases

The Elimination Property

For solving a system of multivariate polynomial equations, it is interesting to know linear combinations of the given polynomials that contain as few variables as possible. For example, it is not obvious at first glance how to find the solutions of the system \[ x z^2-3 y z+1=0,\quad x^2-2 y=0,\quad x y-5 z=0 \] But from the linear combination \[ \begin{array}{rl} x^7-15 x^5+100&= 100 (x z^2-3 y z+1)\\ &\quad{}+(x^5-15 x^3+10 x^2 z-150 z)(x^2-2 y) \\ &\quad{}+(2 x^4-30 x^2+20 x z) (x y-5 z) \end{array} \] it can be seen that any solution \((x,y,z)\) of the system must have as \(x\)-coordinate a root of this univariate polynomial of degree 7. (Observe that the linear combination becomes zero whenever all the polynomials of the original system become zero.)

Linear combinations only containing some of the variables are hard to find for arbitrary bases, but easy to find for Gröbner bases: it can be proved that if the ordering of the power products is such that all power products containing unwanted ("bad") variables are greater than any power product only containing wanted ("good") variables, then

the linear combinations containing only good variables of all Gröbner basis elements are precisely the linear combinations of the Gröbner basis elements containing only good variables.

In particular, a linear combination only with good variables exists if and only if already the Gröbner basis contains some polynomial with only good variables.

Figure 4: Lexicographic ordering

The prototypical example for an ordering supporting the elimination property is the lexicographic order, which for three variables looks as follows (cf. Figure Figure 4 for two variables): \[ \begin{array}{rl} & 1 \prec x \prec x^2 \prec x^3 \prec x^4 \prec \cdots \\ \prec& y \prec xy \prec x^2y \prec x^3y \prec x^4y \prec \cdots \\ \prec& y^2 \prec xy^2 \prec x^2y^2 \prec x^3y^2 \prec x^4y^2 \prec \cdots\\ & \cdots\cdots\cdots\cdots\\ \prec& z \prec xz \prec x^2z \prec x^3z \prec x^4z \prec \cdots \\ \prec& yz \prec xyz \prec x^2yz \prec x^3yz \prec x^4yz \prec \cdots \\ \prec& y^2z \prec xy^2z \prec x^2y^2z \prec x^3y^2z \prec x^4y^2z \prec \cdots\\ & \cdots\cdots\cdots\cdots \end{array} \]

Here is a Gröbner basis with respect to that ordering: \[ \left. \begin{array}{ll} &\left. \begin{array}{ll} &\{x^2-5x+6,\qquad\qquad\qquad\bigr\}\quad x \text{ only}\\ &\,\,2 x y-4 y-x+2,\\ &\,\,4 y^2+3 x-10, \end{array}\right\}\quad x,y\text{ only}\\ &\qquad x z^2-2 z^2-4 x+8,\\ &\qquad z^3-4 x z+8 z+2 x-6\}. \end{array}\right\}\text{all variables} \] All linear combinations free of \(y\) and \(z\) of these polynomials are multiples (with polynomials in \(x\)) of the first polynomial. All linear combinations free of \(z\) of these polynomials are linear combinations (with polynomial coefficients in \(x\) and \(y\)) of the first three polynomials.

In analogy to systems of linear equations, a Gröbner basis with respect to lexicographic ordering is also called a triangular system. The solutions of such a system can be easily determined. In the example:

• First solve \(x^2-5x+6=0\ ,\) yielding \(x=2\) and \(x=3\ .\)

• Setting \(x=2\ ,\) the system simplifies to

\[\{0,0,4 y^2-4,0,z^3-2\}\ :\] giving \(y=\pm1\) and \(z=\sqrt[3]{2}\ ,\) \(z=\omega\sqrt[3]{2}\ ,\) \(z=\omega^2\sqrt[3]{2}\) where \(\omega=\exp(2\pi\mathrm{i}/3)=(1+\sqrt3\mathrm{i})/2\ .\)

• Setting \(x=3\ ,\) the system simplifies to

\[ \{0,2 y-1,4 y^2-1,z^2-4,z^3-4 z\} \ :\] giving \(y=\tfrac12\) and \(z=\pm\sqrt2\ .\)

• Together, the solutions of the system are precisely the eight points

\[ \begin{array}{rl} &(2,1,\sqrt[3]{2}), \,\, (2,-1,\sqrt[3]{2}), \,\, (2,1,\omega\sqrt[3]{2}), \,\, (2,-1,\omega\sqrt[3]{2}), \\ &(2,1,\omega^2\sqrt[3]{2}), \,\, (2,-1,\omega^2\sqrt[3]{2}), \,\, (3,\tfrac12,-\sqrt2), \,\, (3,\tfrac12,\sqrt2). \end{array} \]

For Gröbner bases, unlike for arbitrary triangular systems, it is guaranteed that each partial solution can be extended to a full solution of the system. This means that every solution \(x\) of the first polynomial can be extended to a solution \((x,y)\) of the polynomials in \(x\) and \(y\ ,\) and each of these solutions can be further extended to a solution \((x,y,z)\) of the polynomials in \(x,y,z\ ,\) etc.

The Canonicality Property

Call two polynomials \(f\) and \(g\) congruent modulo a basis \(B\) if \(f\) can be obtained from \(g\) by adding a linear combination of elements from \(B\ .\)

In general, given some \(f\ ,\) \(g\) and \(B\ ,\) it is hard to decide whether or not \(f\) and \(g\) are congruent modulo \(B\) because for deciding this, in general one has to check infinitely many linear combinations. But if \(B\) is a Gröbner basis, congruence of two polynomials modulo \(B\) can be decided easily, because it can be proved for Gröbner bases \(B\) that

\(f\) is congruent to \(g\) modulo \(B\) if and only if \(R(f,B)=R(g,B)\ .\)

Here, \(R(f,B)\) denotes the remainder of the polynomial \(f\) upon multivariate division by the polynomials in \(B\ ,\) i.e., the congruence of \(f\) and \(g\) modulo \(B\) can be decided by computing remainders. This can also be expressed in the following way: For a Gröbner basis \(G\ ,\) the function \(R(f,G)\) is a canonical simplifier for the congruence modulo \(G\ .\)

In general, a function \(S\) is called a canonical simplifier for an equivalence relation \(\sim\) if \(S\) maps all elements of an equivalence class to the same representative of that class, i.e., whenever \(f\sim g\ ,\) then \(S(f)=S(g)\ .\) In our case, the equivalence relation is the congruence modulo a fixed basis \(B\ ,\) sometimes denoted by the symbol \(\equiv_B\ .\)

As an example, let \(f=2z^2-2y^3+2y-4\ ,\) \(g=z^5-4z^3-y^2+5\) and \[ \begin{array}{rl} B=\{&x^2-5 x+6, \,\, 2 x y-4 y-x+2, \,\, 4 y^2+3 x-10, \\ &x z^2-2 z^2-4 x+8, \,\, z^3-4 x z+8 z+2 x-6\}. \end{array} \] \(B\) is a Gröbner basis and \(f\) and \(g\) are congruent because \[ R(f,B)=2z^2+\tfrac34x+\tfrac{11}2\text{ and }R(g,B)=2z^2+\tfrac34x+\tfrac{11}2 \] are equal. In contrast, for \(h=z^5-4y^3-x^2+5\) we find \[ R(h,B)=2z^2+16xz-32z-4y-\tfrac{23}2x+24 \] and we can conclude that none of the infinitely many possible linear combinations will turn \(h\) into \(f\ .\) If \(B\) were not a Gröbner basis, no such conclusion could be drawn at this point.

As an important special case, if \(B\) is a Gröbner basis and \(f\) is a polynomial, it can be decided whether or not \(f\) is a linear combination of the elements of \(B\ :\) This is the case if and only if \(R(f,B)=0\ .\) For example, the polynomial \(z^5-4z^3-2z^2+8\) is a linear combination of elements of \(B\ ,\) because

\[ \begin{array}{rlrlrlrlrlrlrlrlrlrlrl} &z^5-4z^3-2z^2+8\\ \to\quad& 4xz^3-12z^3-2xz^2+4z^2+8&\quad&\text{(by }z^2\text{ times the fifth basis element)}\\ \to\quad& -12z^3-2xz^2+4z^2+16x^2z-32xz-8x^2+24x+8&\quad&\text{(by }4x\text{ times the fifth basis element)}\\ \to\quad& -2xz^2+4z^2+16x^2z-80xz+96z-8x^2+48x-64&\quad&\text{(by }-12\text{ times the fifth basis element)}\\ \to\quad& 16x^2z-80xz+96z-8x^2+40x-48&&\text{(by }-2\text{ times the fourth basis element)}\\ \to\quad& -8x^2+40x-48&&\text{(by }16z\text{ times the first basis element)}\\ \to\quad& 0&&\text{(by }-8\text{ times the first basis element)}. \end{array} \]

It is important to note that the computation of \(R(f,B)\) can be done by an algorithm, and therefore, it can be checked by an algorithm whether or not a given polynomial can be written as a linear combination of the polynomials in a given Gröbner basis.

In commutative algebra, the above result is also expressed in the following terminology: if \(G\) is a Gröbner basis and \(f\) a polynomial, then \(R(f,G)=0\) if and only if "\(f\) belongs to the ideal generated by the elements of \(G\)".

The Syzygy Property

A representation of zero as a linear combination of some polynomials is called a syzygy. For example, as \[ 0=(-1)(2y^2+x z-y z+4y-2z)+(-x)(x y+2x-z)+(y+2)(x^2+2y-z), \] the tuple \((-1,-x,y+2)\) is a syzygy for \((2y^2+x z-y z+4y-2z,x y+2x-z,x^2+2y-z)\ .\) An alternative terminology calls \((-1,-x,y+2)\) a solution of the linear diophantine equation

\[ 0=(2y^2+x z-y z+4y-2z)P_1+(x y+2x-z)P_2+(x^2+2y-z)P_3 \]

with unknown polynomials \(P_1,P_2,P_3\ .\)

In general, given a tuple of polynomials, it is hard to find its infinitely many syzygies. But if the coefficients of the diophantine equation form a Gröbner basis, then the syzygies can be determined easily: It can be shown that

in this case, the syzygies are precisely the linear combinations of the finitely many principal syzygies obtained from cofactors of all S-polynomials.

The S-polynomial of two polynomials \(f,g\) is defined as

\[ \mathrm{SPOL}(f,g):=\mathrm{lcm}(\mathrm{LPP}(f),\mathrm{LPP}(g))\Bigl(\frac{f}{\mathrm{LM}(f)}-\frac{g}{\mathrm{LM}(g)}\Bigr), \]

where \(\mathrm{LPP}(p)\) is the leading power product of the polynomial \(p\) and \(\mathrm{LM}(p)\) is the leading monomial of \(p\ ,\) i.e., the leading power product together with its coefficient. For example, for \(f=xy+2x-z\ ,\) \(g=x^2+2y-z\ ,\) we have

\[ \mathrm{SPOL}(f,g)=\mathrm{lcm}(xy,x^2)\Bigl(\frac{f}{xy}-\frac{g}{x^2}\Bigr)= xf-yg=2x^2-xz-2y^2+yz. \]

The notion of S-polynomials plays a key role not only for finding syzygies, but also for the construction of Gröbner bases (see below and Buchberger algorithm).

The S-polynomial of two polynomials \(f\) and \(g\) is, by definition, a particular linear combination of \(f\) and \(g\ ,\) and so its remainder upon division by a Gröbner basis containing \(f\) and \(g\) must be zero. For the example \(f=xy+2x-z\ ,\) \(g=x^2+2y-z\) with \(B=\{2y^2+xz-yz+4y-2z,f,g\}\) (which is a Gröbner basis), we have \[ \begin{array}{rll} \mathrm{SPOL}(f,g)&=2x^2-xz-2y^2+yz\\ &\to -x z-2 y^2+y z-4 y+2 z&\qquad\text{(by }2\text{ times }g)\\ &\to 0&\qquad\text{(by }-1\text{ times the first basis element)}. \end{array} \] This reduction gives rise to the alternative representation \[ 2x^2-xz-2y^2+yz=(-1)(2y^2+xz-yz+4y-2z)+(0)(xy+2x-z)+(2)(x^2+2y-z), \] in which \((-1,0,2)\) is called a cofactor tuple of \(2x^2-xz-2y^2+yz\) with respect to \(B\ .\)

A principal syzygy is obtained by taking the difference of such a representation of \(\mathrm{SPOL}(f,g)\) and the representation \(\mathrm{SPOL}(f,g)=xf-yg\) above. In the example, \[ 0 = (-1)(2y^2+xz-yz+4y-2z)+(-x)(xy+2x-z)+(y+2)(x^2+2y-z) \] gives the syzygy \((-1,-x,y+2)\ .\)

From the S-polynomial of the first and the second element of \(B\ ,\) we get the principal syzygy \((-\tfrac12x,y-\tfrac12z,\tfrac12z)\ ,\) and from the S-polynomial of the first and the third element of \(B\ ,\) we get the principal syzygy \((-\tfrac12x^2-y+2,2x-\tfrac12xz,y^2+\tfrac12xz-4)\ .\) According to the syzygy property, since \(B\) is a Gröbner basis, all the syzygies for \((2y^2+x z-y z+4y-2z,x y+2x-z,x^2+2y-z)\) are linear combinations of \[ (-1,-x,y+2),\quad(-\tfrac12x^2-y+2,2x-\tfrac12xz,y^2+\tfrac12xz-4), \quad\text{and}\quad(-\tfrac12x,y-\tfrac12z,\tfrac12z). \] If \(B\) was not a Gröbner basis, this construction would in general not produce a finite representation of all syzygies.

Construction of Gröbner bases

An arbitrary set of polynomials is in general not a Gröbner basis. However, for every basis \(B\) there exists a Gröbner basis \(G\) which is equivalent to \(B\) in the sense that the linear combinations of elements of \(B\) are precisely the same as the linear combinations of elements of \(G\ .\) For \(B\) and \(G\) equivalent in this sense, the congruence of polynomials modulo \(B\) agrees with the congruence modulo \(G\ .\)

Given an arbitrary basis \(B\ ,\) an equivalent Gröbner basis \(G\) can be found constructively by Buchberger's Algorithm. This algorithm relies on Buchberger's Theorem:

A basis is a Gröbner basis if and only if all S-polynomials of any two basis elements reduce to zero.

As an example, \(B=\{x y+2 x-z,x^2+2 y-z\}\) is not a Gröbner basis, because \[ \begin{array}{rl} \mathrm{SPOL}(x y+2 x-z,x^2+2 y-z)&=x(x y+2 x-z) - y(x^2+2 y-z)\\ &=2x^2-2y^2-xz+yz\\ &\to\quad -x z-2 y^2+y z-4 y+2 z \end{array} \] (by \(2\) times the second basis element), where the latter cannot be reduced any further.

Buchberger's algorithm for computing a Gröbner basis \(G\) equivalent to a given arbitrary basis \(B\) is a completion procedure. Starting with \(G=B\ ,\) the algorithm searches for polynomials \(f,g\in G\) whose S-polynomial \(\mathrm{SPOL}(f,g)\) does not reduce to zero. If no such pair exists, then \(G\) is a Gröbner basis by the above theorem. Otherwise, some \(\mathrm{SPOL}(f,g)\) has a nonzero remainder \(r\) after division by \(G\ .\) In this case, we replace \(G\) by \(G\cup\{r\}\) and iterate. It is not trivial to prove that this procedure will always terminate after finitely many such extensions of the basis.

In the example above, \(G:=B\cup\{-x z-2 y^2+y z-4 y+2 z\}\) is a Gröbner basis, because for this extended basis all S-polynomials reduce to zero.

More on the construction of Gröbner bases can be found in a separate Scholarpedia article on Buchberger's Algorithm. All examples of Gröbner bases in the present article were constructed by using this algorithm, which is implemented in all computer algebra systems like Maple, Mathematica, etc.

Applications of Gröbner Bases

In the following, we will illustrate some of the many applications of Gröbner bases

• in commutative algebra, the field from which Gröbner bases theory originated,
• in other areas of mathematics,
• in science and engineering.

Some of the applications in commutative algebra are immediate consequences of the various (equivalent) definitions of Gröbner bases and were exemplified already above: solving systems of nonlinear equations, solving the congruence problem modulo polynomial systems, and solving linear diophantine polynomial equations.

Other Applications in Commutative Algebra

Intersection of Ideals

Given two bases \(B\ ,\) \(B'\ ,\) we can ask for the set of polynomials that can be written as a linear combination of the polynomials in \(B\) and also as a linear combination of the polynomials in \(B'\ .\) For example, if \(B=\{x^2-2y+1\}\) and \(B'=\{3x-5,3y+1\}\ ,\) then \(p=x^3+5x^2y-2xy-10y^2+x+5y\) is such a polynomial, because there are the two representations \[ p=(x+5y)(x^2-2y+1) \] and \[ p=\tfrac19(3x^2+5)(3x-5)+\tfrac19(15x^2-30y-6x+25)(3y+1). \] All the polynomials with this property can again be described in terms of a single finite basis. For example, the polynomials which can be written as multiples of \(x^2-2y+1\) and also as linear combinations of \(3x-5\) and \(3y+1\) are precisely the linear combinations of \(3x^2y+x^2-6y^2+y+1\) and \(3x^3-5x^2-6xy+3x+10y-5\ .\)

It can be shown that, given two bases \(B\) and \(B'\ ,\) the polynomials in the Gröbner basis of \(tB\cup(1-t)B'\) (with respect to an elimination ordering ranking \(t\) highest) that do not contain the variable \(t\) form a basis whose linear combinations form exactly the polynomials that simultaneously are linear combinations of \(B\) and linear combinations of \(B'\ .\)

Indeed, the two polynomials \(3x^2y+x^2-6y^2+y+1\) and \(3x^3-5x^2-6xy+3x+10y-5\) in our example were obtained as precisely those two \(t\)-free elements in the Gröbner basis of \(\{t(x^2-2y+1),(1-t)(3x-5),(1-t)(3y+1)\}\) with respect to some ordering that ranks \(t\) highest: \[ \{3x^2y+x^2-6y^2+y+1, 3x^3-5x^2-6xy+3x+10y-5, 40t + 9x^2 - 18y - 31\}. \]

Envelopes

Figure 5: Envelope of a family of circles.

Consider a family of curves defined by equations \(p(x,y,t)=0\) depending on a parameter \(t\ .\) Under suitable conditions, an equation for the envelope of this family can be found by eliminating \(t\) from the equations \(p=0\) and \(\frac\partial{\partial t}p=0\ .\) If \(p\) is a polynomial, this can be done with Gröbner bases.

For example, the polynomial \(p=(x-t)^2+y^2-t\) describes the circles with center \((t,0)\) and radius \(\sqrt t\) (Figure Figure 5, red). The Gröbner basis of \(\{(x-t)^2+y^2-t,-2(x-t)-1\}\) with respect to the lexicographic order with \(t>y>x\) is \[ \{4 y^2-4 x-1,2 t-2 x-1\}, \] and the equation \(4y^2-4x-1=0\) describes the (blue) enveloping curve in Figure Figure 5.

Hilbert Dimension

Figure 6: A space curve (red) obtained as the intersection of two hypersurfaces (gray).

A collection of multivariate polynomials defines the geometric object in the multidimensional space consisting of those points where all the polynomials in the collection vanish simultaneously. For example, the equation \(x+y+z-1\) defines a plane in \(\mathbb{R}^3\ ,\) the equation \(x^2+y^2-1\) defines a cylinder with radius \(1\) parallel to the \(z\)-axis, and both equations together define the red curve shown in Figure Figure 6.

One of the possibilities to define the dimension of such a geometric object is via variables that are algebraically independent modulo the defining equations: the dimension is the minimal number \(d\) of variables such that no (nonzero) linear combination of the defining polynomials involves only \(d\) variables. Except in some degenerate cases, this definition matches the geometric intuition (points have dimension 0, curves have dimension 1, surfaces have dimension 2, etc.)

The dimension of a geometric object can be read off from the leading power products in the Gröbner basis of the defining polynomials: it is the maximum number of variables for which there exists no power product in these variables in the Gröbner basis with respect to a degree order. In the example of the cylinder defined by \(x^2+y^2-1\ ,\) the dimension is \(2\ ,\) because there is no leading power product in \(y\) and \(z\) alone (so the dimension is at least \(2\)) and there is a leading power product in \(x\ ,\) \(y\ ,\) \(z\ ,\) (so the dimension is less than \(3\)). For the intersection curve of the cylinder with the plane defined by \(x+y+z-1\ ,\) we have the Gröbner basis \[ \{\,x+y+z-1,2 y^2+2 y z-2 y+z^2-2 z\,\}. \] We have no leading power product in \(z\) alone, so the dimension is at least \(1\ ,\) but we have a leading power product for any choice of two variables (\(x,y\) or \(x,z\) or \(y,z\)), so the dimension is less than \(2\ .\)

Applications in Other Areas of Mathematics

Geometric Theorem Proving

Figure 7: The theorem of Apollonius.

Gröbner bases can be used for proving theorems in elementary geometry that can be rephrased as quantified formulas involving polynomial equations and inequations. As an example, consider the theorem of Apollonius: If \(ABC\) is a right triangle with its right angle at \(A\ ,\) then the circle through the midpoints of all three sides also contains the foot point \(H\) of the altitude drawn from \(A\) to the side \(BC\) (Figure Figure 7).

(It is also true, and even simpler to prove, that \(A\) always lies on the circle.)

In order to prove this theorem, we choose a cartesian coordinate system where \(A\) is the origin and \(B\) and \(C\) are on the axes, so that \(A=(0,0)\ ,\) \(B=(x,0)\) and \(C=(0,y)\) for some \(x,y\ .\) In terms of these coordinates, we clearly have \(U=(x/2,0)\ ,\) \(V=(x/2,y/2)\ ,\) \(W=(0,y/2)\) as the midpoints of the three sides. The other relevant points can be described implicitly by equations that must be satisfied by their coordinates. The point \(H=(h_1,h_2)\) is determined by the equations \[ \begin{array}{ll} h_1x-h_2y=0&\qquad(AH\text{ is orthogonal to }BC)\\ h_1y+h_2x-xy=0&\qquad(B,H,C\text{ are on one line}). \end{array} \] The midpoint \(M=(m_1,m_2)\) of the circle through \(U,V,W\) can be expressed by the equations \[ \begin{array}{llll} &(m_1-x/2)^2+m_2^2=(m_1-x/2)^2+(m_2-y/2)^2&\qquad(|MU|=|MV|)\\ &(m_1-x/2)^2+m_2^2=m_1^2+(m_2-y/2)^2&\qquad(|MU|=|MW|). \end{array} \] To prove that \(H\) lies on the circle through \(U,V,W\ ,\) it suffices to show that for all \(x,y,h_1,h_2,m_1,m_2\) the equations above imply \[ (m_1-x/2)^2+m_2^2=(m_1-h_1)^2+(m_2-h_2)^2. \] This is equivalent to saying that there do not exist \(x,y,h_1,h_2,m_1,m_2\) such that the equations above and \[ (m_1-x/2)^2+m_2^2\neq (m_1-h_1)^2+(m_2-h_2)^2 \] hold at the same time.

Now, this is equivalent to saying that there do not exist \(x,y,h_1,h_2,m_1,m_2\) and \(z\) such that the equations above and \[ 1 - z ((m_1-x/2)^2+m_2^2-( (m_1-h_1)^2+(m_2-h_2)^2 )) = 0 \] hold at the same time.

This question about the existence of common solutions of polynomials can now be decided by the Gröbner basis method: A set of polynomials has no common solutions if and only if its Gröbner basis contains \(1\ .\)

In many cases, however, the corresponding Gröbner basis delivers possible solutions which can be considered as "degenerate" cases (in which the validity of the theorem cannot be guaranteed) whereas, for all other cases the theorem is guaranteed to be true.

In our example, the Gröbner basis of \[ \begin{array}{rl} \{&h_1x-h_2y, h_1y+h_2x-xy,\\ &(m_1-x/2)^2+m_2^2 - (m_1-x/2)^2 -(m_2-y/2)^2,\\ &(m_1-x/2)^2+m_2^2-m_1^2-(m_2-y/2)^2,\\ &((m_1-x/2)^2+m_2^2- (m_1-h_1)^2-(m_2-h_1)^2)z-1\} \end{array} \] is \[ \{x,y,1+z(h_1^2+h_2^2-2h_1m_1-2h_2m_2)\}. \] This means that the theorem may be violated for the degenerate triangle where \(x=y=0\ ,\) but certainly holds true for all interesting triangles.

Graph Coloring

Figure 8: Graph coloring.

A \(k\)-coloring of a graph \(G=(V,E)\) is an assignment of colors taken from \(k\) colors to the vertices of the graph in such a way that any two vertices \(v_1,v_2\in V\) connected by an edge have a different color. Figure Figure 8 shows an example for a \(3\)-coloring of a graph.

The problem of finding all \(k\)-colorings for a given graph can be reduced to the solution of a system of polynomial equations, and so it can be done by means of Gröbner bases. We use the \(k\)th roots of unity as colors, and variables to represent vertices. The condition that a vertex should have a color is then encoded by the polynomials \(x^k-1\ .\) The polynomial \[ \frac{x^k-y^k}{x-y}=x^{k-1}+x^{k-2}y+x^{k-3}y^2+\cdots+x y^{k-2}+y^{k-1} \] encodes the condition that the vertices corresponding to the variables \(x\) and \(y\) must have different colors.

For the example graph in Figure Figure 8, the equation system for finding all \(3\)-colorings is \[ \begin{array}{rllll} \{&x_1^3-1=0,x_2^3-1=0,x_3^3-1=0,x_4^3-1=0,&\quad&\text{(one out of three color per vertex)}\\ &x_1^2+x_2 x_1+x_2^2=0,&&\text{(different colors for vertex 1 and 2)}\\ &x_1^2+x_3 x_1+x_3^2=0,&&\text{(different colors for vertex 1 and 3)}\\ &x_2^2+x_3 x_2+x_3^2=0,&&\text{(different colors for vertex 2 and 3)}\\ &x_2^2+x_4 x_2+x_4^2=0,&&\text{(different colors for vertex 2 and 4)}\\ &x_3^2+x_4 x_3+x_4^2=0\}&&\text{(different colors for vertex 3 and 4)}. \end{array} \] The system has six solutions, one of which is \[ x_1=\omega,\quad x_2=\omega^2,\quad x_3=\omega^3,\quad x_4=\omega, \] where \(\omega=\exp(2\pi\mathrm{i}/3)=\tfrac12(-1+\sqrt3\mathrm{i})\ .\) It corresponds to the coloring depicted above. (In this simple example, all colorings are identical up to permutation of colors.)

Summation and Integration

Gröbner bases can be used for evaluating integrals of special functions. Many analytic functions can be defined by some finite set of initial values and a finite set of differential equations they satisfy. For example, the function \[ f(x,t):=\exp(-t^2 x) \] can be described as the (unique) function satisfying \[ \begin{array}{ll} &\frac{d}{dx}f(x,t)+t^2 f(x,t)=0\\ &\frac{d}{dt}f(x,t)+2 x t f(x,t)=0, \end{array} \] and \(f(0,0)=1\ .\) Suppose we are given these differential equations, as a description of \(f(x,t)\ ,\) and want to find differential equations which have the function \[ F(x):=\int_0^\infty f(x,t)\,dt \] as (unique) solution.

The basic idea is to construct from the given differential equations for \(f(x,t)\) by suitable linear combinations and/or applications of partial derivatives a new differential equation for \(f(x,t)\) from which a differential equation for \(F(x)\) can be obtained. The application of a derivative with respect to a variable \(x\) may be rephrased as multiplication with an additional variable \(D_x\ .\) In this point of view, differential equations in \(x\) and \(t\) are polynomials in \(x,t,D_x,D_t\) which can be added and multiplied. It must be noted however that multiplication in this setting is no longer commutative: The product rule \[ \frac{d}{dx} x u(x) = u(x) + x \frac{d}{dx} u(x) \] requires commutation rules such as \(D_x x = x D_x + 1\ .\)

Gröbner bases can be generalized to such domains with noncommutative multiplication [ 13, 27, 31, 34, 41 ], and this can be used for solving the integration problem. In order to find a differential equation in \(x\) satisfied by the integral \(F(x)\ ,\) compute a non-commutative Gröbner basis with respect to an ordering that ranks \(t\) highest. In the example, this gives \[ \{4x^2 D_x+2x+D_t^2,t D_t-2xD_x,2tx+D_t,t^2+D_x\}. \] The first element of this Gröbner basis corresponds to the differential equation \[ \frac{d^2}{dt^2}f(x,t)+4x^2\frac{d}{dx}f(x,t)+2x f(x,t)=0. \] We integrate this equation from \(0\) to \(\infty\ .\) In the first term, the integral cancels the derivative \(d/dt\) and we are left with \(\frac d{dt}f(x,t)|_0^\infty\ ,\) which evaluates to \(0\ .\) In the other two terms, the integral threads over multiplications by \(x\) and \(d/dx\ ,\) so we finally find \[ 4x^2\frac{d}{dx} F(x)+2x F(x)=0. \] Many integrals can be handled in this way, including integrals involving special functions such as Bessel functions or Jacobi polynomials. Also recurrence equations for infinite sums can be found by a similar technique.

Linear Integer Optimization

Gröbner bases can be used to solve certain integer optimization problems. For example, consider the question of finding the minimum number of coins (pennies, nickels, dimes, and quarters) that is needed to pay  \(\$1.17\).

The key idea is to encode the number of coins as exponents of variables. For example, using variables \(P,N,D,Q\) for the various kinds of coins, the power product \(P^7 N^2 D^5 Q^2\) represents seven pennies and two nickles and five dimes and two quarters. The total number of coins is then given by the total degree of the term, \(7+2+5+2=16\) in the example.

In order to minimize the number of coins, compute a Gröbner basis with respect to a degree ordering of \[ \{P^5-N,P^{10}-D,P^{25}-Q\}. \] This gives \[ G=\{N^2-D,D^3-NQ,D^2N-Q,P^5-N\}. \] Because of the chosen ordering, reduction of some polynomial with respect to \(G\) yields a polynomial whose degree is minimal among all the polynomials which are equivalent to the original one. Therefore, an optimal way of paying  \(\$1.17\) is found by computing the normal form of some arbitrary way of paying  \(\$1.17\). Because of \[ R(P^7 N^2 D^5 Q^2, G) = P^2DNQ^4, \] we find that eight coins are needed.

A general description of this technique applicable to arbitrary linear optimization problems can be found in Section 2.8 of [ 2 ].

Applications in Science and Engineering

Coding Theory

One of the aims of coding theory is to conceive schemes for transmitting information through a communication channel in such a way that errors that may possibly occur during the transmission can be detected and corrected by the receiver. According to a classical coding scheme, instead of transmitting data items \(a_0,a_1,\dots,a_n\) directly, we take the polynomial \(p(x)=a_0+a_1x+\cdots+a_nx^n\) and transmit the values \(p(0),p(1),p(2),\dots,p(n),p(n+1),\dots,p(n+5)\ ,\) say. If the transmission was correct, then the coefficients of \(p\) can be recovered from these values by interpolation. If not, i.e., if some of the values \(p(i)\) were transmitted incorrectly, then we will typically find that there does not exist a polynomial of degree \(n\) matching all the transmitted values.

In this case, Gröbner bases can be used to determine a plausible candidate for the correct data vector from an erroneous vector of transmitted data. Continuing the example situation sketched before, assume we have received the data values \(p_0,p_1,\dots,p_{n+5}\ .\) Our goal is to construct a polynomial \(p(x)=a_0+a_1x+\cdots+a_nx^n\) of degree at most \(n\) such that \(p(i)=p_i\) for many points \(i\ .\) At these points, we will have the equations \[ a_0+a_1i+a_2i^2+\cdots+a_ni^n=p_i. \] At points \(i\) where an error occurred in the transmission, the equation will not hold, but if we knew that the errors occurred at positions \(e_1,e_2,\dots,e_5\ ,\) say, then \[ (i-e_1)(i-e_2)(i-e_3)(i-e_4)(i-e_5)(a_0+a_1i+a_2i^2+\cdots+a_ni^n-p_i)=0 \] would be valid for every \(i=0,1,\dots,n+5\ .\) Considering now the unknown quantities \(e_1,e_2,\dots,e_5\) and \(a_0,a_1,\dots,a_n\) as variables, we have an algebraic system of equations \[ \begin{array}{ll} &e_1e_2e_3e_4e_5(a_0-p_0)=0,\\ &(1-e_1)(1-e_2)(1-e_3)(1-e_4)(1-e_5)(a_0+a_1+\cdots+a_n-p_1)=0,\\ &(2-e_1)(2-e_2)(2-e_3)(2-e_4)(2-e_5)(a_0+a_12+\cdots+a_n2^n-p_2)=0,\\ &\vdots \end{array} \] with \(n+6\) variables and \(n+6\) equations, which can be solved with Gröbner bases.

This solves the error correction problem in principle. However, the method given here is a somewhat oversimplified version of what is actually applied in practice. In order to obtain efficient error correcting algorithms, refined techniques have to be applied which are beyond the scope of this text. (In particular, the appropriate coefficient fields in the context of coding are finite and specific algorithmic techniques available in such fields can be applied. See [ 42 ] for details.)

Robotics

The "general inverse kinematics problem" in robotics asks for determining how the various joints in a robot have to be turned in order to reach a certain position. For example, given a point in 3D space and an orientation, we may ask for the appropriate angles of the joints in order to reach the point with the requested orientation. In general, these problems lead to a system of nonlinear equations, which in principle can be solved by Gröbner bases.

Figure 9: Example robot.

As a simple example, consider the "robot" depicted in Figure Figure 9, consisting of three straight segments of length \(1\) connected via joints that can independently rotate around angles \(\phi_1\ ,\) \(\phi_2\ ,\) and \(\phi_3\ ,\) respectively. Choosing the foot of the robot as the origin of a coordinate system, we want to access the point \((2,0)\) (cross in Figure Figure 9) from northwest (arrow in Figure Figure 9). By elementary trigonometry, it can be found that the position of the robot's gripper can be expressed in terms of \(\phi_1,\phi_2,\phi_3\) as \[ \binom{-\sin(\phi_1)-\sin(\phi_1+\phi_2)-\sin(\phi_1+\phi_2+\phi_3)} {\cos(\phi_1)+\cos(\phi_1+\phi_2)+\cos(\phi_1+\phi_2+\phi_3)} = \binom 20. \] The restriction on the direction simply translates into \(\phi_1+\phi_2+\phi_3=-\tfrac34\pi\ .\)

In order to solve these equations via Gröbner bases, it is necessary to transform them into polynomial equations. One way of doing this is to introduce auxiliary variables \(s_1,s_2,s_3,c_1,c_2,c_3\) for \(\sin(\phi_1),\sin(\phi_2),\sin(\phi_3),\cos(\phi_1),\cos(\phi_2),\cos(\phi_3)\ ,\) respectively, and solve the equations for the auxiliary variables first rather than directly for \(\phi_1,\phi_2,\phi_3\ .\) The requirement for \((s_i,c_i)\) to be on the unit circle is accommodated by additional equations \(s_i^2+c_i^2-1=0\) for \(i=1,2,3\ .\)

In our example, using trigonometric addition theorems, the requirement on the target position translates into the polynomials \[ \begin{array}{rl} p_1&={-}c_2 s_1-c_2 c_3 s_1-c_1 s_2-c_1 c_3 s_2-c_1 c_2 s_3+s_2 s_3 s_1-s_1-2,\\ p_2&={-}c_1 s_2 s_3-c_3 s_1 s_2-c_2 s_1 s_3+c_2 c_1+c_2 c_3 c_1+c_1-s_1 s_2. \end{array} \] From the requirement on the target direction, we obtain the two polynomials \[ \begin{array}{rl} p_3&={-}c_2 c_3 s_1-c_1 c_3 s_2-c_3 s_1 s_2-c_1 c_2 s_3-c_2 s_1 s_3-c_1 s_2 s_3+c_1 c_2 c_3+s_1 s_2 s_3,\\ p_4&={-}c_2 c_3 s_1-c_1 c_3 s_2+c_3 s_1 s_2-c_1 c_2 s_3+c_2 s_1 s_3+c_1 s_2 s_3-c_1 c_2 c_3+s_1 s_2 s_3-\sqrt{2}, \end{array} \] by applying \(\sin\) and \(\cos\ ,\) respectively, on both sides of \(\phi_1+\phi_2+\phi_3=-\tfrac34\pi\) and using trigonometric addition theorems to rewrite the right hand sides in terms of \(\sin(\phi_1)\ ,\) \(\sin(\phi_2)\ ,\) \(\sin(\phi_3)\ ,\) \(\cos(\phi_1)\ ,\) \(\cos(\phi_2)\ ,\) \(\cos(\phi_3)\ .\) Finally, the polynomials \[ \begin{array}{rl} p_5&=c_1^2+s_1^2-1,\\ p_6&=c_2^2+s_2^2-1,\\ p_7&=c_3^2+s_3^2-1 \end{array} \] restrict the solutions to the unit circle.

Figure 10: The two solution configurations.

It turns out that the equation system \[ p_1=p_2=p_3=p_4=p_5=p_6=p_7=0 \] has two distinct solutions, which correspond to the two configurations shown in Figure Figure 10. Computer algebra systems like Mathematica can do the required Gröbner basis computation in less than a second.

Software Engineering

Gröbner bases can be used for finding invariant properties of loops, which are needed in automated program verification. As an example, consider the following program for computing the product of two integers \(a,b\ :\)

(x, y, z) := (a, b, 0);
while not (y = 0) do
  if y mod 2 = 0
  then (x, y, z) := (2*x, y/2, z)
  else (x, y, z) := (2*x, (y-1)/2, x+z)
  end if
end while
return z

Writing \(X,Y,Z\) for the respective values of the program variables \(x,y,z\) at the beginning of the loop, a polynomial \(p\) is a loop invariant if \[ p(X,Y,Z,x,y,z)=0 \] in all subsequent iterations. Such polynomials can be found by Gröbner bases computations as follows. Denote by \(f_1,f_2\) the maps in the assignments of the two branches of the conditional statement in the example code above, \[ \begin{array}{rl} f_1(x,y,z)&=(2x,\tfrac12 y,z),\\ f_2(x,y,z)&=(2x,\tfrac12(y-1),x+z). \end{array} \] Using a symbolic recurrence solver, it is possible to find closed form expressions for the \(n\)-fold iterated application of these maps to \((x,y,z)\ .\) For \(n\geq0\ ,\) we have \[ \begin{array}{rl} f_1^n(x,y,z)&=(2^n x, \bigl(\tfrac12\bigr)^n y, z),\\ f_2^n(x,y,z)&=(2^n x, \bigl(\tfrac12\bigr)^n(y+1)-1, (2^n-1)x+z). \end{array} \] In examples where such closed form representations are not immediate, symbolic recurrence solvers can be used to obtain these representations. To rephrase the iterated maps as polynomial maps, define \[ \begin{array}{rlrlrlrl} F_1\colon &x\mapsto u x,&\quad&y\mapsto v y, &\quad&z\mapsto z\\ F_2\colon &x\mapsto u x,&\quad&y\mapsto v(y+1)-1,&\quad& z\mapsto (u-1)x+z, \end{array} \] where \(u\) and \(v\) are new variables that denote \(2^n\) and \(\bigl(\tfrac12\bigr)^n\ ,\) respectively.

We can find all the polynomials which remain fixed under an arbitrary number \(n\) of applications of \(f_1\) by eliminating the auxiliary variables \(u\) and \(v\) from \[ \{F_1(x-X),F_1(y-Y),F_1(z-Z),uv-1\} =\{u x - X, v y - Y, z - Z, u v - 1\}. \] Using Gröbner bases, one finds \[ \{x - X - z + Z, X y - X Y + z + y z - Z - y Z\}. \] For these two polynomials we have \(F_1(p)=p\ ,\) and all other polynomials with this property are linear combinations of those.

Next, we search among these linear combinations for polynomials that are also fixed under \(f_2^n\) by eliminating \(u\) and \(v\) from \[ \{F_2(x - X - z + Z), F_2(X y - X Y + z + y z - Z - y Z), uv-1\}. \] This gives \(\{x y - X Y + z - Z\}\ .\)

Further applications of \(F_1\) or \(F_2\) will leave this basis fixed, and therefore \[ x y - X Y + z - Z = 0 \] is an invariant of the loop.

Taking into account the initialization \(X=a,Y=b,Z=0\ ,\) it follows that \[ x y - a b + z = 0 \] is true in each iteration of the loop. Taking also into account the termination condition \(y=0\) of the loop, it follows that \[ z - a b = 0 \] is true after the loop. This proves the correctness of the program.

See [ 28, 40, 44 ] for further information on loop invariant generation using Gröbner bases.

Petroleum Industry

Figure 11: Oil production.

Gröbner bases can be used to analyze and optimize the production of oil in offshore platforms. If an oil field is accessed through several points (Figure Figure 11), then the amount of oil or gas which can be maximally extracted at one point depends on how much oil is extracted at the other points. The oil compartments in a field are not independent from each other but there are geological interactions between them, so that it is possible that reducing the extraction rate at one access point may increase the total production of all points.

These interactions are hard to model as they depend on parameters which are difficult to measure. A pragmatic approach is therefore to directly establish the relations between extraction parameters at the access points and the resulting production gains.

In the oversimplified situation given in Figure Figure 11, we have three access points. Denote by \(e_1,e_2,e_3\) the extraction parameters and let \(p_1,p_2,p_3\) denote the amount of oil obtained at the respective points. We are interested in how \(p_1,p_2,p_3\) are related to \(e_1,e_2,e_3\ .\) If we assume that these relations can be described by a system of polynomials \(f_1,\dots,f_m\) such that \[ f_i(e_1,e_2,e_3,p_1,p_2,p_3)=0\quad(i=1,\dots,m) \] then such polynomials can be constructed from sample values that are obtained by testing many different values for the extraction parameters \(e_1,e_2,e_3\) and measuring the resulting values for \(p_1,p_2,p_3\ .\) This problem is a multivariate version of polynomial interpolation, which can be solved by the algorithm of Buchberger and Moeller [ 10 ], which in fact yields a Gröbner bases \(\{f_1,\dots,f_m\}\ .\) In practice, since measurements are inaccurate, a numerical variant of this algorithm must be applied [ 25 ].

From this Gröbner basis, it is then possible to determine how \(e_1,e_2,e_3\) have to be chosen such that that total production gain \(p_1+p_2+p_3\) is maximal or some other optimality criterion is met.

Other Applications

The Gröbner bases methodology has been applied successfully in literally dozens of other areas [ 12, 23, 26, 37, 38, 41, 43, 45, 46 ]. In all these applications, the general principle is to reformulate a particular problem as a question about sets of multivariate polynomials, then to do one or more Gröbner bases computations, so that finally the key properties of Gröbner bases (the elimination property, the canonicality property, or the syzygy property) can be used to answer the question.

We encourage experts in the various application fields to complement this article by additional subsections describing these applications.

References

1. Gröbner Bases Bibliography. Compiled by B. Buchberger and A. Zapletal in the course of the Special Semester on Gröbner Bases at RICAM (Radon Institute for Computational and Applied Mathematics) and RISC (Research Institute for Symbolic Computation), Linz, Austria, 2006: http://www.ricam.oeaw.ac.at/Groebner-Bases-Bibliography/.
2. W. Adams and P. Loustaunau. An Introduction to Gröbner Bases. AMS, Providence, 1994.
3. T. Becker, V. Weispfenning, and H. Kredel. Gröbner Bases: A Computational Approach to Commutative Algebra. Springer New York, 1993.
4. B. Buchberger. Introduction to Gröbner Bases. In [11], pages 3--31.
5. B. Buchberger. Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal (An Algorithm for Finding the Basis Elements of the Residue Class Ring of a Zero Dimensional Polynomial Ideal). PhD thesis, University of Innsbruck, 1965. English translation in Journal of Symbolic Computation, 41(3--4):475--511, 2006.
6. B. Buchberger. Ein algorithmisches Kriterium für die Lösbarkeit eines algebraischen Gleichungssystems (An algorithmic criterion for the solvability of algebraic systems of equations). Aequationes Mathematicae, 4(3):374--383, 1970. English translation in [11], pages 535--545.
7. B. Buchberger. Gröbner-bases: An algorithmic method in polynomial ideal theory.In Multidimensional Systems Theory -- Progress, Directions and Open Problems in Multidimensional Systems, pages 184--232. Reidel Publishing Company, Dodrecht--Boston--Lancaster, 1985.
8. B. Buchberger. Gröbner bases and systems theory. Multidimensional Systems and Signal Processing, 12(3--4):223--251, 2001.
9. B. Buchberger and R. Loos. Algebraic simplification. In Computer Algebra: Symbolic and Algebraic Computation, pages 11--43. Springer, Wien, 1982.
10. B. Buchberger and H. M. Möller. The construction of multivariate polynomials with preassigned zeros. In Proceedings of EUROCAM'82, volume 144 of LNCS, pages 24--31. Springer, Berlin/Heidelberg, 1982.
11. B. Buchberger and F. Winkler, editors. Gröbner Bases and Applications, London Mathematical Society Lectures Notes Series 251. Cambridge University Press, 1998.
12. J. Bueso, J. G. Torrecillas, and A. Verschoren. Algorithmic Methods in Non-Commutative Algebra: Applications to Quantum Groups Kluwer, Dordrecht, 2003.
13. F. Chyzak and B. Salvy. Non-commutative elimination in Ore algebras proves multivariate identities. Journal of Symbolic Computation, 26(5--6):187--227, 1998.
14. A. Cohen. Gröbner bases, an introduction. In Some Tapas of Computer Algebra, volume 4 of Algorithms and Computation in Mathematics, pages 1--33. Springer, Berlin, 1999.
15. D. Cox. Gröbner bases: A sampler of recent developments. In Proceedings of ISSAC'07, pages 387--388, ACM, New York, 2007.
16. D. Cox, J. Little, and D. O'Shea. Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra. Springer, New York, 1992.
17. D. Cox, J. Little, and D. O'Shea. Using Algebraic Geometry. Springer, New York, 1998.
18. A. Dickenstein and I.Z. Emiris, editors. Solving Polynomial Equations. Algorithms and Computation in Mathematics. Springer, Berlin/Heidelberg, 2005.
19. D. Eisenbud. Gröbner Bases. In Commutative Algebra With a View Toward Algebraic Geometry, chapter 15, pages 321--384. Springer, New York, 1999.
20. R. Fröberg. An Introduction to Gröbner Bases. John Wiley & Sons, Chichester, 1998.
21. K. Geddes, S. Czapor, and G. Labahn. Gröbner bases for polynomial ideals. In Algorithms for Computer Algebra, chapter 10, pages 429--472. Kluwer, Dordrecht, 1992.
22. J. von zur Gathen and J. Gerhard. Gröbner bases. In Modern Computer Algebra, chapter 21, pages 565--596. Cambridge University Press, 1999.
23. D. J. Green. Gröbner Bases and the Computation of Group Cohomology, volume 1828 of Lecture Notes in Mathematics. Springer, Berlin/Heidelberg, 2003.
24. G. Greuel and G. Pfister. A Singular Introduction to Commutative Algebra. Springer, Berlin/Heidelberg, 2002.
25. D. Heldt, M. Kreuzer, S. Pokutta, and H. Poulisse. Approximate computation of zero-dimensional polynomial ideals. Journal of Symbolic Computation, 44(11):1566--1591, 2009.
26. M. Klin, G.A. Jones, A. Jurisic, M. Muzychuk, and I. Ponomarenko, editors. Algorithmic Algebraic Combinatorics and Gröbner Bases. Springer, Berlin/Heidelberg, 2009.
27. C. Koutschan. Advanced Applications of the Holonomic Systems Approach. PhD thesis, RISC-Linz, Johannes Kepler Universität Linz, 2009.
28. L. Kovacs and T. Jebelean. An algorithm for automated generation of invariants for loops with conditionals. In Proceedings of SYNASC'05, pages 245--249. IEEE Computer Society Press, 2005.
29. M. Kreuzer and L. Robbiano. Computational Commutative Algebra 1. Springer, Berlin/Heidelberg, 2000.
30. M. Kreuzer and L. Robbiano. Computational Commutative Algebra 2. Springer, Berlin/Heidelberg, 2005.
31. H. Li. Noncommutative Gröbner Bases and Filtered-Graded Transfer, volume 1795 of Lecture Notes in Mathematics. Springer, Berlin/Heidelberg, 2002.
32. M. Maruyama. Gröbner Basis and its Applications. Kyoritsu Shuppan, Tokyo, 2002. (Japanese.)
33. B. Mishra. Computational ideal theory. In Algorithmic Algebra, Texts and Monographs in Computer Science, chapter 3, pages 71--132. Springer, New York, 1993.
34. F. Mora. An introduction to commutative and non-commutative Gröbner bases. Theoretical Computer Science, 134(1):131--173, 1994.
35. F. Mora. Solving Polynomial Equation Systems II: Macaulay's Paradigm and Gröbner Technology. Cambridge University Press, New York, 2005.
36. M. Noro and K. Yokoyama. Computational Fundamentals of Gröbner bases. University of Tokyo Press, Tokyo, 2003. (Japanese.)
37. L. Pachter and B. Sturmfels. Algebraic Statistics for Computational Biology. Cambridge University Press, Cambridge, 2005.
38. H. Park and G. Regensburger, editors. Gröbner Bases in Control Theory and Signal Processing. Radon Series on Computational and Applied Mathematics. De Gruyter, Berlin, 2007.
39. V. V. Prasolov. Gröbner bases. In Polynomials, Algorithms and Computation in Mathematics, chapter 6.2. Springer, Berlin/Heidelberg, 2004. English translation of Mnogotchleny, Moscow Center for Continuous Math. Education, 2001.
40. E. Rodriguez-Carbonell and D. Kapur. Generating all polynomial invariants in simple loops. Journal of Symbolic Computation, 42(4):443--476, 2007.
41. M. Rosenkranz and D. Wang, editors. Gröbner Bases in Symbolic Analysis. Radon Series on Computational and Applied Mathematics. De Gruyter, Berlin, 2007.
42. S. Sakata. Gröbner bases in coding theory. In [11], pages 205--220.
43. M. Sala, T. Mora, L. Perret, S. Sakata, and C. Traverso, editors. Gröbner Bases, Coding, and Cryptography. Springer, Berlin/Heidelberg, 2009.
44. S. Sankaranarayanan, H. B. Sipma, and Z. Manna. Non-linear Loop Invariant Generation using Gröbner Bases. In Proceedings of POPL'04, pages 318--329. ACM, New York, 2004.
45. B. Sturmfels. Algorithms for Invariant Theory. Texts and Monographs in Symbolic Computation. Springer, Wien, 1993.
46. W. V. Vasconcelos. Computational Methods in Commutative Algebra and Algebraic Geometry. Algorithms and Computation in Mathematics. Springer, Berlin/Heidelberg, 1998.
47. D. Wang. Elimination Methods. Texts and Monographs in Symbolic Computation. Springer, Wien, 2001.
48. F. Winkler. The method of Gröbner bases. In Polynomial Algorithms in Computer Algebra, Texts and Monographs in Symbolic Computation, chapter 8. Springer, Wien, 1996.

See also

(pending)

Sponsored by: Eugene M. Izhikevich, Editor-in-Chief of Scholarpedia, the peer-reviewed open-access encyclopedia

Sponsored by: Prof. James Meiss, Applied Mathematics University of Colorado, Boulder, CO, USA

Reviewed by: Anonymous

Reviewed by: Prof. Willy Hereman, Dept. of Math & CS, Colorado School of Mines

Accepted on: 2010-10-12 08:13:13 GMT