What is a Gröbner basis?

pdf

A Gröbner basis is a set of multivariate polynomials that has desirable algorithmic properties. Every set of polynomials can be transformed into a Gröbner basis. This process generalizes three familiar techniques: Gaussian elimination for solving linear systems of equations, the Euclidean algorithm for computing the greatest common divisor of two univariate polynomials, and the Simplex Algorithm for linear programming; see [3]. For example, the input for Gaussian elimination is a collection of linear forms such as $ℱ=\{2x+3y+4z-5,3x+4y+5z-2\}$ and the algorithm transforms $ℱ$ into the Gröbner basis $𝒢=\{\underset{\_}{x}-z+14,\underset{\_}{y}+2z-11\}$.
Let $K$ be any field, such as the real numbers $K=ℝ$, the complex numbers $K=ℂ$, the rational numbers $K=\mathbb{Q}$, or a finite field $K={𝔽}_p$. We write $K[x_1,...,x_n]$ for the ring of polynomials in $n$ variables $x_i$ with coefficients in the field $K$. If $ℱ$ is any set of polynomials, then the ideal generated by $ℱ$ is the set $⟨ℱ⟩$ consisting of all polynomial linear combinations:$$⟨ℱ⟩=\{p_1{f}_1+\cdots +p_r{f}_r:f_1,\dots ,f_r\in ℱ\text{ and }{p}_1,\dots ,p_r\in K[x_1,\dots ,x_n]\}$$In our example the set $ℱ$ and its Gröbner basis $𝒢$ generate the same ideal: $⟨𝒢⟩=⟨ℱ⟩$. By Hilbert’s Basis Theorem, every ideal $I$ in $K[x_1,...,x_n]$ has the form $I=⟨ℱ⟩$; i.e., it is generated by some finite set $ℱ$ of polynomials.
A term order on $K[x_1,...,x_n]$ is a total order ≺ on the set of all monomials $x^a=x_1^{a_1}\cdot \cdot \cdot x_n^{a_n}$ which has the following two properties:
(1) It is multiplicative; i.e., $x^a\prec x^b$ implies $x^{a+c}\prec x^{b+c}$ for all $a,b,c\in {\mathbb{N}}^n$.
(2) The constant monomial is the smallest; i.e., $1\prec x^a$ for all $a\in {\mathbb{N}}^n\setminus \{0\}$.
An example of a term order (for $n=2$) is the degree lexicographic order $1\prec x_1\prec x_2\prec x_1^2\prec x_1{x}_2\prec x_2^2\prec x_1^3\prec x_1^2{x}_2\prec \cdots$
If we fix a term order ≺, then every polynomial $f$ has a unique initial term ${\text{in}}_{\prec }\left(f\right)=x^a$. This is the ≺-largest monomial $x^a$ which occurs with nonzero coefficient in the expansion of $f$. We write the terms of $f$ in ≺-decreasing order, and we often underline the initial term. For instance, a quadratic polynomial is written $f=3x_2^2+5x_1{x}_2+7x_1^2+11x_1+13x_2+17$. Suppose now that $I$ is an ideal in $K[x_1,...,x_n]$. Then its initial ideal ${in}_{\prec }\left(I\right)$ is the ideal generated by the initial terms of all the polynomials in $I$:${in}_{\prec }\left(I\right)=⟨{in}_{\prec }\left(f\right):f\in I⟩$
A finite subset $𝒢$ of $I$ is a Gröbner basis with respect to the term order ≺ if the initial terms of the elements in $𝒢$ suffice to generate the initial ideal: ${in}_{\prec }\left(I\right)=⟨{in}_{\prec }\left(g\right):g\in G⟩$
There is no minimality requirement for being a Gröbner basis. If $𝒢$ is a Gröbner basis for $I$, then any finite subset of $I$ that contains $𝒢$ is also a Gröbner basis. To remedy this nonminimality, we say that $𝒢$ is a reduced Gröbner basis if
(1) for each $g\in G$, the coefficient of ${in}_{\prec }\left(g\right)$ in $g$ is 1,
(2) the set $\{{in}_{\prec }\left(g\right):g\in G\}$ minimally generates ${in}_{\prec }\left(I\right)$, and
(3) no trailing term of any $g\in G$ lies in ${in}_{\prec }\left(I\right)$.
With this definition, we have the following theorem:

If the term order ≺ is fixed, then every ideal $I$ in $K[x_1,...,x_n]$ has a unique reduced Gröbner basis.

The reduced Gröbner basis $𝒢$ can be computed from any generating set of $I$ by a method that was introduced in Bruno Buchberger’s 1965 dissertation.
Buchberger named his method after his advisor, Wolfgang Gröbner. With hindsight, the idea of Gröbner bases can be traced back to earlier sources, including a paper written in 1900 by the invariant theorist Paul Gordan. But Buchberger was the first to give an algorithm for computing Gröbner bases.
Gröbner bases are very useful for solving systems of polynomial equations. Suppose $K\subseteq ℂ$, and let $ℱ$ be a finite set of polynomials in $K[x_1,...,x_n]$.
The variety of $ℱ$ is the set of all common complex zeros:$$𝒱\left(ℱ\right)=\{(z_1,\dots ,z_n)\in {ℂ}^n:f(z_1,\dots ,z_n)=0\text{ for all }f\in ℱ\}$$The variety does not change if we replace $ℱ$ by another set of polynomials that generates the same ideal in $K[x_1,...,x_n]$. In particular, the reduced Gröbner basis $𝒢$ for the ideal $ℱ$ specifies the same variety:$$𝒱\left(ℱ\right)=𝒱(⟨ℱ⟩)=𝒱(⟨𝒢⟩)=𝒱\left(𝒢\right)$$The advantage of $𝒢$ is that it reveals geometric properties of the variety that are not visible from $ℱ$. The first question that one might ask about a variety $𝒱\left(F\right)$ is whether it is empty. Hilbert’s Nullstellensatz implies that

the variety $𝒱\left(ℱ\right)$ is empty if and only if $𝒢$ equals {1}.

How can one count the number of zeros of a given system of equations? To answer this, we need one more definition. Given a fixed ideal $I$ in $K[x_1,...,x_n]$ and a term order ≺, a monomial $x^a=x_1^{a_1}\cdot \cdot \cdot x_n^{a_n}$ is called standard if it is not in the initial ideal ${in}_{\prec }\left(I\right)$. The number of standard monomials is finite if and only if every variable $x_i$ appears to some power in the initial ideal. For example, if ${in}_{\prec }\left(I\right)=⟨x_1^3,x_2^4,x_3^5⟩$, then there are sixty standard monomials, but if ${in}_{\prec }\left(I\right)=⟨x_1^3,x_2^4,x_1{x}_3^4⟩$, then the set of standard monomials is infinite.
The variety $𝒱\left(I\right)$ is finite if and only if the set of standard monomials is finite, and the number of standard monomials equals the cardinality of $𝒱\left(I\right)$, when zeros are counted with multiplicity.
For $n=1$ this is the Fundamental Theorem of Algebra, which states that the variety $𝒱\left(f\right)$ of a univariate polynomial $f\in K[x]$ of degree $d$ consists of $d$ complex numbers. Here the singleton $\{f\}$ is a Gröbner basis, and the standard monomials are $1,x,x^2,...,x^{d-1}$.
Our criterion for deciding whether a variety is finite generalizes to the following formula for the dimension of a variety. Consider a subset $S$ of the variables $\{x_1,...,x_n\}$ such that no monomial in the variables in $S$ appears in ${in}_{\prec }\left(I\right)$, and suppose that $S$ has maximal cardinality among all subsets with this property. That maximal cardinality $\left|S\right|$ equals the dimension of $𝒱\left(I\right)$.
The set of standard monomials is a $K$-vectorspace basis for the residue ring $K[x_1,...,x_n]/I$.
The image of a polynomial $p$ modulo $I$ can be expressed uniquely as a $K$-linear combination of standard monomials. This expression is the normal form of $p$. The process of computing the normal form is the division algorithm. In the familar case of only one variable $x$, where $I=⟨f⟩$ and $f$ has degree $d$, the division algorithm writes any polynomial $p\in K[x]$ as a $K$-linear combination of $1,x,x^2,...,x^{d-1}$. But the division algorithm works relative to any Gröbner basis $𝒢$ in any number of variables.
How can we test whether a given set of polynomials $𝒢$ is a Gröbner basis or not? Consider any two polynomials $g$ and $g^{\prime }$ in $𝒢$, and form their S-polynomial $m^{\prime }g-m{g}^{\prime }$. Here $m$ and $m^{\prime }$ are monomials of smallest possible degree such that $m^{\prime }\cdot {in}_{\prec }\left(g\right)=m\cdot {in}_{\prec }\left(g^{\prime }\right)$. The S-polynomial $m^{\prime }g-m{g}^{\prime }$ lies in the ideal $𝒢$. We apply the division algorithm with respect to the tentative Gröbner basis $𝒢$ to $m^{\prime }g-m{g}^{\prime }$.
The resulting normal form is a $K$-linear combination of monomials none of which is divisible by an initial monomial from $𝒢$. A necessary condition for $𝒢$ to be a Gröbner basis is

${\mathrm{normalform}}_{𝒢}(m^{\prime }g-m{g}^{\prime })=0$ for all $g,g^{\prime }\in G$.

Buchberger’s Criterion states that this necessary condition is sufficient: a set $𝒢$ of polynomials is a Gröbner basis if and only if all its S-polynomials have normal form zero. From this criterion, one derives Buchberger’s Algorithm [1] for computing the reduced Gröbner basis $𝒢$ from any given input set $ℱ$.
In summary, Gröbner bases and the Buchberger Algorithm for finding them are fundamental notions in algebra. They furnish the engine for more advanced computations in algebraic geometry, such as elimination theory, computing cohomology, resolving singularities, etc. Given that polynomial models are ubiquitous across the sciences and engineering, Gröbner bases have been used by researchers in optimization, coding, robotics, control theory, statistics, molecular biology, and many other fields. We invite the reader to experiment with one of the many implementations of Buchberger’s algorithm (e.g., in CoCoA, Macaulay2, Magma, Maple, Mathematica, or Singular).

References
[1] David Cox, John Little, and Donal O’ Shea, Ideals, Varieties and Algorithms. An Introduction to Computational Algebraic Geometry and Commutative Algebra, second ed., Undergraduate Texts in Mathematics, Springer-Verlag, New York, 1997.
[2] Niels Lauritzen, Concrete Abstract Algebra: From Numbers to Gröbner Bases, Cambridge University Press, 2003.
[3] Bernd Sturmfels, Two Lectures on Gröbner Bases, New Horizons in Undergraduate Mathematics, VMath Lecture Series, Mathematical Sciences Research Institute, Berkeley, California, 2005, http://www.msri.org/communications/vmath/special_productions/.