Gröbnerbasis

Gröbner basis is a concept in computational algebra that provides a canonical generating set for an ideal in a multivariate polynomial ring over a field. Let k be a field and x1, …, xn be variables, and let I be an ideal of the polynomial ring k[x1, …, xn]. With respect to a chosen monomial order, a finite subset G of I is a Gröbner basis of I if the ideal of leading terms of I is equal to the ideal generated by the leading terms of G. Equivalently, performing multivariate division by G yields a zero remainder for every element of I.

Among the Gröbner bases for a given I and order there is a particularly nice one called the reduced Gröbner basis. It is unique, consists of monic polynomials, and has the property that no monomial in the tail of any basis polynomial is divisible by the leading term of another basis polynomial.

Existence and computation are ensured by Buchberger's theory. For any ideal I in k[x1, …, xn] and any monomial order, a finite Gröbner basis exists. Buchberger's algorithm computes it by repeatedly forming S-polynomials from pairs of basis elements and reducing them by the current basis, adding nonzero remainders to the basis, and continuing until all S-polynomials reduce to zero. Criteria known as Buchberger's criteria help prune unnecessary calculations.

Monomial orders such as lexicographic, graded lexicographic, and reverse lexicographic influence the leading terms and the resulting basis. With lex order, Gröbner bases enable elimination of variables and can be used to solve systems of polynomial equations. More generally, Gröbner bases generalize Gaussian elimination to polynomial systems and underpin algorithms for ideal membership, dimension, and other invariants in computational algebraic geometry.