Gröbner Basis

A Gröbner basis of an ideal in a polynomial ring over a field , for a fixed monomial order, is a finite generating set of nonzero polynomials such that the leading monomial of every nonzero is divisible by the leading monomial of some member of . The empty set is used for the zero ideal.

Equivalently, polynomial reduction by gives each polynomial a unique remainder, and iff that remainder is zero (Buchberger 2001b, pp. 230-231). A Gröbner basis generates the same ideal as the original polynomials, so it has the same common zeros over any extension field. Equality of zero sets alone is a weaker condition. For example, and have the same zero set but are different ideals. For linear polynomials, the calculation specializes to Gaussian elimination.

The algorithm for computing Gröbner bases is known as Buchberger's algorithm. Calculating a Gröbner basis is typically a very time-consuming process for large polynomial systems (Trott 2006, p. 37).

For example, in with lexicographic order , the generating set

(1)

has the reduced Gröbner basis

(2)

The identity shows that the new polynomial belongs to the original ideal. Conversely, shows that and generate the same ideal. The monic normalization and reduction by the other members make a reduced Gröbner basis unique for a fixed monomial order.

Gröbner bases are pervasive in the construction of symbolic algebra algorithms. For lexicographic order and , the basis members involving only , ..., form a Gröbner basis of the corresponding elimination ideal (Cox et al. 1997, p. 113). This permits elimination of the initial variables and is useful in implicitization. For example, the following Wolfram Language command solves for the onset of the period-4 bifurcation of the logistic map in parameter by eliminating the variables , , , and from a set of five equations describing the system.

  Factor /@ GroebnerBasis[
    {
      x2 - r x1(1 - x1),
      x3 - r x2(1 - x2),
      x4 - r x3(1 - x3),
      x1 - r x4(1 - x4),
      r^4(1 - 2x1)(1 - 2x2)(1 - 2x3)(1 - 2x4) + 1
    },
    r,
    {x1, x2, x3, x4},
    MonomialOrder -> EliminationOrder
  ]

Because computing a Gröbner basis can be so computationally expensive, variables can sometimes be eliminated more readily from a system of equations by manually computing the resultant of successive pairs of equations to iteratively eliminate one variable at each step.

The determination of a Gröbner basis is very roughly analogous to computing an orthonormal basis from a set of basis vectors and can be described roughly as a combination of Gaussian elimination (for linear systems) and the Euclidean algorithm (for univariate polynomials over a field).

The time and memory required to calculate a Gröbner basis depend very much on the variable ordering, monomial ordering, and on which variables are regarded as constants. Gröbner bases are used implicitly in many routines in the Wolfram Language, and can be called explicitly with the command GroebnerBasis[poly1, poly2, ..., x1, x2, ...].

In the common case of computing a Gröbner basis to eliminate trigonometric functions from a system of equations, the Weierstrass substitution

			(3)
			(4)

where can be (but are not always) preferable to using and with the additional equation because they reduce the number of variables (Trott 2006, p. 39).

A bibliography about Gröbner bases is maintained by Buchberger and Zapletal.

In the Season 4 opening episode "Trust Metric" (2007) of the television crime drama NUMB3RS, math genius Charlie Eppes mentions that he used Gröbner bases in an attempt to derive an equation describing friendship.