In computer algebra, computational algebraic geometry, and computational commutative algebra, a Gröbner basis is a particular kind of generating subset of an ideal I in a polynomial ring R. One can view it as a multivariate, non-linear generalization of:

• the Euclidean algorithm for computation of univariate greatest common divisors,
• Gaussian elimination for linear systems, and
• modular arithmetic.

The theory of Gröbner bases was developed independently by Heisuke Hironaka in 1964, who named them standard bases, and by Bruno Buchberger in 1965, who named them after his advisor Wolfgang Gröbner.

Formal definition

A Gröbner basis G is characterised by any one of the following properties, stated relative to some monomial order:

• the ideal given by the leading terms of polynomials in the ideal I is itself generated by the leading terms of the basis G;
• the leading term of any polynomial in I is divisible by the leading term of some polynomial in the basis G;
• multivariate division of any polynomial in the polynomial ring R by G gives a unique remainder;
• multivariate division of any polynomial in the ideal I by G gives 0.

All these properties are equivalent; different authors use different definitions depending on the topic they choose. It is the last two properties which allow calculations in the factor ring R/I with the same facility as modular arithmetic. It is a significant fact of commutative algebra that Gröbner bases always exist, and can be effectively obtained starting for any ideal starting with a generating subset.

Multivariate division requires a monomial ordering, the basis depends on the monomial ordering chosen, and different orderings can give rise to radically different Gröbner bases. Two of the most commonly used orderings are lexicographic ordering, and degree lexicographic, a variant on lexicographic ordering where monomials are sorted first by degree, then by lexicographic ordering when two monomials are of the same degree.

In most cases (polynomials in finitely many variables with complex coefficients (more generally coefficients over any field), for example), Gröbner bases exist for any monomial ordering. One method for generating them is known as Buchberger's algorithm. All subsequent algorithms for computing Gröbner bases (including the justifiably celebrated algorithms of Faugère) are refinements of Buchberger's algorithm.

A Gröbner basis is termed reduced if the leading coefficient of each element of the basis is 1 and no monomial in any element of the basis is in the ideal generated by the leading terms of the other elements of the basis. Both standard and reduced Gröbner bases are often computable in practice.

The concept and algorithms of Gröbner bases have been generalized (in a limited way) to modules.

Properties and applications of Gröbner bases

Deciding equality of ideals

Reduced Gröbner bases can be shown to be unique for any given ideal and monomial ordering, and are also often computable in practice. Thus one can determine if two ideals are equal by looking at their reduced Gröbner bases.

Deciding membership of ideals

The reduction of a polynomial f by the multivariate division algorithm for an ideal using a Gröbner basis will yield 0 if and only if f is in the ideal. (This is not true in general for polynomials in more than one variable). This gives a test for determining whether or not a polynomial is in an ideal with a given set of generators.

Elimination property

If a Gröbner basis for an ideal I in

kx₂, ..., x_n

is computed relative to the lexicographic ordering with

x₁ > x₂ > ... > x_n,

the intersection of I with

kx_k+1, ..., x_n

is given by the intersection of the Gröbner basis with

kx_k'+1, ..., x_n.

In particular a polynomial f lies in

kx_k+1, ..., x_n,

if and only if its leading term lies in this subring. This is known as the elimination property.

Solving equations

In particular, this gives us a method for solving simultaneous polynomial equations. If there are only finitely many solutions to the system of equations

{f₁..., x_n = a₁, ..., f_m..., x_n = a_m},

we should be able to manipulate these equations to get something of the form

g(x_n) = b.

The elimination property says that if we compute a Gröbner basis for the ideal generated by {f₁ − a₁, ..., f_m − a_m} relative to the right lexicographic ordering, then we can find the polynomial g as one of the elements of our basis. Furthermore, (taking k = n − 1) there will be another polynomial in the basis involving only x_n−1 and x_n, so we can take our possible solutions for x_n and find corresponding values for x_n−1. This lifting continues all the way up until we've found the values of all the variables.

Conversion of parametric equations

The same elimination property can almost be used to convert parametric equations of polynomials into nonparametric equations. Given the equations

{x₁ = f₁(t₁, ..., t_m), ..., x_n = f_n(t₁, ..., t_m)},

we compute a Gröbner basis for the ideal generated by

{x₁ − f₁, ..., x_n − f_n}

relative to any ordering which places polynomials involving t greater than those which don't: for example, lexicographic ordering with

t₁ > t₂ > ... > t_m > x₁ > ... > x_n.

Taking only the elements of the basis which do not involve the t variables, we get a set of equations describing not the original surface, but the smallest affine variety containing it.

Intersecting ideals

• If I is generated by

{f₁, ..., f_m}

{g₁, ..., g_k},

then the intersection of I and J can be found by taking a Gröbner basis for the ideal generated by

{tf₁, ..., tf_m, (1 − t)g₁, ..., (1 − t)g_k}

relative to any lexicographic ordering which places t first, then taking only those terms not involving t. In particular, this allows us to calculate the least common multiple (and hence the greatest common divisor) of two polynomials f and g, since it is the generator of the intersection of the ideals generated by f and by g. This is true even if we do not know how to factor the polynomials! Also, note that for more than one variable the polynomial ring is not a Euclidean domain, so the Euclidean algorithm doesn't work here.

See also

• Buchberger's algorithm
• Gröbner-Shirshov basis

Further reading

• David Cox, John Little, and Donal O'Shea (1997). Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, Springer. ISBN 0-387-94680-2. See Chapter 2: Groebner Bases.

External links

• B. Buchberger, Groebner Bases: A Short Introduction for Systems Theorists in Proceedings of EUROCAST 2001.
• Comparative Timings Page for Gröbner Bases Software
• ogb Online Gröbner Basis, Galway, Eire
• Gröbner Basis Theory Leicester University

Computer algebra | Invariant theory | Algebraic geometry

Gröbnerbasis