Gröbner basis

In mathematics, and more specifically in computer algebra, computational algebraic geometry, and computational commutative algebra, a Gröbner basis is a particular kind of generating set of an ideal in a polynomial ring K[x1, …, xn] over a field K. A Gröbner basis allows many important properties of the ideal and the associated algebraic variety to be deduced easily, such as the dimension and the number of zeros when it is finite. Gröbner basis computation is one of the main practical tools for solving systems of polynomial equations and computing the images of algebraic varieties under projections or rational maps.

Gröbner basis computation can be seen as a multivariate, non-linear generalization of both Euclid's algorithm for computing polynomial greatest common divisors, and Gaussian elimination for linear systems.[1]

Gröbner bases were introduced in 1965, together with an algorithm to compute them (Buchberger's algorithm), by Bruno Buchberger in his Ph.D. thesis. He named them after his advisor Wolfgang Gröbner. In 2007, Buchberger received the Association for Computing Machinery's Paris Kanellakis Theory and Practice Award for this work. However, the Russian mathematician Nikolai Günther had introduced a similar notion in 1913, published in various Russian mathematical journals. These papers were largely ignored by the mathematical community until their rediscovery in 1987 by Bodo Renschuch et al.[2] An analogous concept for multivariate power series was developed independently by Heisuke Hironaka in 1964, who named them standard bases. This term has been used by some authors to also denote Gröbner bases.

The theory of Gröbner bases has been extended by many authors in various directions. It has been generalized to other structures such as polynomials over principal ideal rings or polynomial rings, and also some classes of non-commutative rings and algebras, like Ore algebras.

All operations related to Gröbner bases require the choice of a total order on the monomials, with the following properties of compatibility with multiplication. For all monomials M, N, P,

A total order satisfying these condition is sometimes called an admissible ordering.

These conditions imply that the order is a well-order, that is, every strictly decreasing sequence of monomials is finite.

Although Gröbner basis theory does not depend on a particular choice of an admissible monomial ordering, three monomial orderings are specially important for the applications:

Gröbner basis theory was initially introduced for the lexicographical ordering. It was soon realised that the Gröbner basis for degrevlex is almost always much easier to compute, and that it is almost always easier to compute a lex Gröbner basis by first computing the degrevlex basis and then using a "change of ordering algorithm". When elimination is needed, degrevlex is not convenient; both lex and lexdeg may be used but, again, many computations are relatively easy with lexdeg and almost impossible with lex.

Once a monomial ordering is fixed, the terms of a polynomial (product of a monomial with its nonzero coefficient) are naturally ordered by decreasing monomials (for this order). This makes the representation of a polynomial as an ordered list of pairs coefficient–exponent vector a canonical representation of the polynomials. The first (greatest) term of a polynomial p for this ordering and the corresponding monomial and coefficient are respectively called the leading term, leading monomial and leading coefficient and denoted, in this article, lt(p), lm(p) and lc(p).

The concept of reduction, also called multivariate division or normal form computation, is central to Gröbner basis theory. It is a multivariate generalization of the Euclidean division of univariate polynomials.

In this section we suppose a fixed monomial ordering, which will not be defined explicitly.

Given two polynomials f and g, one says that f is reducible by g if some monomial m in f is a multiple of the leading monomial lm(g) of g. If m happens to be the leading monomial of f then one says that f is lead-reducible by g. If c is the coefficient of m in f and m = q lm(g), the one-step reduction of f by g is the operation that associates to f the polynomial

The main properties of this operation are that the resulting polynomial does not contain the monomial m and that the monomials greater than m (for the monomial ordering) remain unchanged. This operation is not, in general, uniquely defined; if several monomials in f are multiples of lm(g), then one may choose arbitrarily which one to reduce. In practice, it is better to choose the greatest one for the monomial ordering, because otherwise subsequent reductions could reintroduce the monomial that has just been removed.

For Gröbner basis computations, except at the end, it is not necessary to do a complete reduction: a lead-reduction is sufficient, which saves a large amount of computation.

The definition of the reduction shows immediately that, if h is a normal form of f by G, then we have

For having a clear view of the reduction process, one has to rewrite polynomials with their terms in a decreasing order. For example, if

For the first reduction step, either the first or the second term may be reduced. However, the reduction of a term amounts to remove this term at the cost of adding new lower terms, and, if it is not the first reducible term that is reduced, it is possible that a further reduction adds a similar term, which must be reduced again. It is therefore always better to reduce first the largest (for the monomial order) reducible term.

Buchberger's algorithm has been introduced for solving the difficulties induced by this non-uniqueness. Roughly speaking it consists in adding to G the polynomials that are needed for the uniqueness of the reduction by G.

A Gröbner basis G of an ideal I in a polynomial ring R over a field is a generating set of I characterized by any one of the following properties, stated relative to some monomial order:

All these properties are equivalent; different authors use different definitions depending on the topic they choose. The last two properties 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 computed for any ideal given by a finite 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 reverse lexicographic order (also called graded reverse lexicographic order or simply total degree order). Lexicographic order eliminates variables, however the resulting Gröbner bases are often very large and expensive to compute. Degree reverse lexicographic order typically provides for the fastest Gröbner basis computations. In this order monomials are compared first by total degree, with ties broken by taking the smallest monomial with respect to lexicographic ordering with the variables reversed.

In most cases (polynomials in finitely many variables with complex coefficients or, more generally, coefficients over any field, for example), Gröbner bases exist for any monomial ordering. Buchberger's algorithm is the oldest and most well-known method for computing them. Other methods are the Faugère's F4 and F5 algorithms, based on the same mathematics as the Buchberger algorithm, and involutive approaches, based on ideas from differential algebra.[3] There are also three algorithms for converting a Gröbner basis with respect to one monomial order to a Gröbner basis with respect to a different monomial order: the FGLM algorithm, the Hilbert-driven algorithm and the Gröbner walk algorithm. These algorithms are often employed to compute (difficult) lexicographic Gröbner bases from (easier) total degree Gröbner bases.

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. In the worst case, computation of a Gröbner basis may require time that is exponential or even doubly exponential in the number of solutions of the polynomial system (for degree reverse lexicographic order and lexicographic order, respectively). Despite these complexity bounds, both standard and reduced Gröbner bases are often computable in practice, and most computer algebra systems contain routines to do so.

The concept and algorithms of Gröbner bases have also been generalized to ideals over various rings, commutative or not, like polynomial rings over a principal ideal ring or Weyl algebras.

with c a nonzero rational number and p a polynomial in the variable y only; the reason being that such an m can never have two distinct zeroes with the same value for y (in this case, the points (1,1) and (−1,1)).

From the above it follows that I, apart from the zero polynomial, only contains polynomials whose leading term has degree greater than or equal to 2; therefore their leading terms are divisible by at least one of the three monomials

Unless explicitly stated, all the results that follow[4] are true for any monomial ordering (see that article for the definitions of the different orders that are mentioned below).

It is a common misconception that the lexicographical order is needed for some of these results. On the contrary, the lexicographical order is, almost always, the most difficult to compute, and using it makes impractical many computations that are relatively easy with graded reverse lexicographic order (grevlex), or, when elimination is needed, the elimination order (lexdeg) which restricts to grevlex on each block of variables.

Reduced Gröbner bases are unique for any given ideal and any monomial ordering. Thus two ideals are equal if and only if they have the same (reduced) Gröbner basis (usually a Gröbner basis software always produces reduced Gröbner bases).

Any set of polynomials may be viewed as a system of polynomial equations by equating the polynomials to zero. The set of the solutions of such a system depends only on the generated ideal, and, therefore does not change when the given generating set is replaced by the Gröbner basis, for any ordering, of the generated ideal. Such a solution, with coordinates in an algebraically closed field containing the coefficients of the polynomials, is called a zero of the ideal. In the usual case of rational coefficients, this algebraically closed field is chosen as the complex field.

An ideal does not have any zero (the system of equations is inconsistent) if and only if 1 belongs to the ideal (this is Hilbert's Nullstellensatz), or, equivalently, if its Gröbner basis (for any monomial ordering) contains 1, or, also, if the corresponding reduced Gröbner basis is [1].

Given the Gröbner basis G of an ideal I, it has only a finite number of zeros, if and only if, for each variable x, G contains a polynomial with a leading monomial that is a power of x (without any other variable appearing in the leading term). If this is the case, then the number of zeros, counted with multiplicity, is equal to the number of monomials that are not multiples of any leading monomial of G. This number is called the degree of the ideal.

When the number of zeros is finite, the Gröbner basis for a lexicographical monomial ordering provides, theoretically, a solution: the first coordinate of a solution is a root of the greatest common divisor of polynomials of the basis that depend only on the first variable. After substituting this root in the basis, the second coordinate of this solution is a root of the greatest common divisor of the resulting polynomials that depend only on the second variable, and so on. This solving process is only theoretical, because it implies GCD computation and root-finding of polynomials with approximate coefficients, which are not practicable because of numeric instability. Therefore, other methods have been developed to solve polynomial systems through Gröbner bases (see System of polynomial equations for more details).

The dimension of an ideal I in a polynomial ring R is the Krull dimension of the ring R/I and is equal to the dimension of the algebraic set of the zeros of I. It is also equal to number of hyperplanes in general position which are needed to have an intersection with the algebraic set, which is a finite number of points. The degree of the ideal and of its associated algebraic set is the number of points of this finite intersection, counted with multiplicity. In particular, the degree of a hypersurface is equal to the degree of its definition polynomial.

Both degree and dimension depend only on the set of the leading monomials of the Gröbner basis of the ideal for any monomial ordering.

The dimension is the maximal size of a subset S of the variables such that there is no leading monomial depending only on the variables in S. Thus, if the ideal has dimension 0, then for each variable x there is a leading monomial in the Gröbner basis that is a power of x.

Most computer algebra systems that provide functions to compute Gröbner bases provide also functions for computing the Hilbert series, and thus also the dimension and the degree.

The computation of Gröbner bases for an elimination monomial ordering allows computational elimination theory. This is based on the following theorem.

This elimination property has many applications, some described in the next sections.

A rational curve is an algebraic curve that has a set of parametric equations of the form

Implicitization consists in computing the implicit equations of such a curve. In case of n = 2, that is for plane curves, this may be computed with the resultant. The implicit equation is the following resultant:

When modeling a problem by polynomial equations, it is often assumed that some quantities are non-zero, so as to avoid degenerate cases. For example, when dealing with triangles, many properties become false if the triangle degenerates to a line segment, i.e. the length of one side is equal to the sum of the lengths of the other sides. In such situations, one cannot deduce relevant information from the polynomial system unless the degenerate solutions are ignored. More precisely, the system of equations defines an algebraic set which may have several irreducible components, and one must remove the components on which the degeneracy conditions are everywhere zero.

This is done by saturating the equations by the degeneracy conditions, which may be done via the elimination property of Gröbner bases.

consists of the components of the primary decomposition of I that do not contain any power of f

Instead of using F, one may also start from a Gröbner basis of F. Which method is most efficient depends on the problem. However, if the saturation does not remove any component, that is if the ideal is equal to its saturated ideal, computing first the Gröbner basis of F is usually faster. On the other hand, if the saturation removes some components, the direct computation may be dramatically faster.

Hilbert's Nullstellensatz has two versions. The first one asserts that a set of polynomials has no common zeros over an algebraic closure of the field of the coefficients, if and only if 1 belongs to the generated ideal. This is easily tested with a Gröbner basis computation, because 1 belongs to an ideal if and only if 1 belongs to the Gröbner basis of the ideal, for any monomial ordering.

The second version asserts that the set of common zeros (in an algebraic closure of the field of the coefficients) of an ideal is contained in the hypersurface of the zeros of a polynomial f, if and only if a power of f belongs to the ideal. This may be tested by saturating the ideal by f; in fact, a power of f belongs to the ideal if and only if the saturation by f provides a Gröbner basis containing 1.

By definition, an affine rational variety of dimension k may be described by parametric equations of the form

Therefore, if k>1, two Gröbner basis computations are needed to implicitize:

Gröbner basis has been applied in the theory of error-correcting codes for algebraic decoding. By using Gröbner basis computation on various forms of error-correcting equations, decoding methods were developed for correcting errors of cyclic codes,[7] affine variety codes,[8] algebraic-geometric codes and even general linear block codes.[9] Applying Gröbner basis in algebraic decoding is still a research area of channel coding theory.