Gröbner basis

Gröbner bases are certain sets of multivariate polynomials with field coefficients. The importance of Gröbner bases stems from the fact that

i) many fundamental problems in algebraic geometry (commutative algebra, polynomial ideal theory) can be reduced by structurally easy algorithms to the construction of Gröbner bases; and

ii) there exists an algorithm by which for any given (finite) set $F$ of multivariate polynomials a Gröbner basis $G$ is constructed such that $F$ and $G$ generate the same polynomial ideal. (This implies, in particular, that, conceived as algebraic sets of equations, $F$ and $G$ have the same set of solutions.) Thus, Gröbner bases establish a uniform approach to the algorithmic solution of quite a few fundamental problems in algebraic geometry. New applications of Gröbner bases are discovered permanently. Also, the method of Gröbner bases has been carried over to domains other than polynomials over fields, e.g. polynomials with coefficients in certain rings, non-commutative polynomials, polynomial modules, and differential algebras. The algorithm that constructs Gröbner bases, various subalgorithms necessary for the construction of Gröbner bases, and various applications of Gröbner bases are routinely available in all modern mathematical software systems, as for example Mathematica and Maple.

A set $F$ of polynomials in $K[x_1,\ldots,x_n]$, the polynomial ring over a field $K$ with indeterminates $x_1,\ldots,x_n$, is called a Gröbner basis if and only if all polynomials $p$ in the ideal generated by $F$ can be reduced to $0$ with respect to $F$.

This definition involves the notion of "reduction", which can be conceived as a generalized division for multivariate polynomials. For example, let

$$p=xy^2-2xy+x$$

and

$$f=xy-4x.$$

Then $p$ can be reduced, in one reduction step, with respect to $f$ by subtracting $yf$ from $p$, yielding a new polynomial $q_1$:

$$q_1=p-yf=2xy+x.$$

Note that, by the reduction, the power product $xy^2$ occurring in $p$ is replaced by "smaller" power products. In fact, a large class of total orderings $\prec$ on power products can be used in the Gröbner-bases approach for defining the notion of "smaller". In the example, the polynomial $q_1$ can be reduced further with respect to $f$ by subtracting $2f$, yielding a new polynomial $q_2$:

$$q_2=q_1-2f=9x.$$

The polynomial $q_2$ cannot be reduced further with respect to $f$ and is called a reduced form of $p$ with respect to $f$. A polynomial $p$ is reducible with respect to a set $F$ of polynomials if it is reducible with respect to some $f\in F$.

Gröbner bases $F$ can be characterized in many other ways, for example by saying that the above reduction relation with respect to $F$ has the Church–Rosser property, i.e. reduced forms are unique. The most important characterization of Gröbner bases is the content of the following main theorem: $F$ is a Gröbner basis if and only if, for all $f,g\in F$, the $S$-polynomial $SP(f,g)$ can be reduced to $0$ with respect to $F$.

The $S$-polynomial $SP(f,g)$ of two polynomials $f$ and $g$ (without loss of generality, $f$ and $g$ are taken to have leading coefficient $1$) is defined as follows:

$$SP(f,g)=uf-vg,$$

where

$$u=\frac{\operatorname{LCM}(LP(f),LP(g))}{LP(f)}$$

and

$$v=\frac{\operatorname{LCM}(LP(f),LP(g))}{LP(g)}.$$

Here, $LP(p)$ denotes the leading power product of the polynomial $p$, i.e. the power product in $p$ which is maximal with respect to the total ordering $\prec$ and $\operatorname{LCM}$ denotes the least common multiple.

The above theorem is the crucial handle for constructing, for any given (finite) set $F$ of polynomials, a corresponding Gröbner basis $G$, i.e. a Gröbner basis $G$ that generates the same ideal as $F$: One first checks whether the condition formulated in the main theorem holds for $F$. If this is the case, $F$ is already a Gröbner basis. If, however, the reduction of any of the $S$-polynomials yields a polynomial $h\neq0$, then $h$ is added to the basis, new $S$-polynomials must be considered, etc., until the algorithm terminates. Termination of this algorithm can be proved by an invocation of either Hilbert's basis theorem (cf. Hilbert theorem) or Dickson's lemma. By the above main theorem, whose proof is combinatorial, it is easy to see that the resulting basis is a Gröbner basis corresponding to the initial set $F$.

Important applications of Gröbner bases are: exact and complete solution of algebraic systems of equations, analysis of algebraic varieties, computation of Hilbert functions and Hilbert polynomials, complete solution of linear Diophantine systems of equations with polynomial coefficients, effective computation in polynomial residue class rings, structural analysis of hypercomplex systems, automated geometrical theorem proving, implicitization of parameter representations of manifolds, solution of various problems in invariant theory and integer programming, and solution of word problems in commutative semi-groups.

The notion of a Gröbner basis, the main theorem, the algorithm based on the main theorem and some of the applications were introduced in [a2]. An easy-to-read summary of the theory is [a3]. The most comprehensive textbook on the subject is [a1].

References

[a1]	Th. Becker, V. Weispfenning, H. Kredel, "Gröbner bases: a computational approach to commutative algebra" , Springer (1993)
[a2]	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)
[a3]	B. Buchberger, "Gröbner bases: an algorithmic method in polynomial ideal theory" N.K. Bose (ed.) , Recent Trends in Multidimensional Systems Theory , Reidel (1985) pp. 184–232