Inmathematics, and more specifically incomputer algebra, computationalalgebraic geometry, and computationalcommutative algebra, aGröbner basis is a particular kind ofgenerating set of an ideal in apolynomial ring${\displaystyle K[x_1,\dots ,x_n]}$ over afield${\displaystyle K}$. A Gröbner basis allows many important properties of the ideal and the associatedalgebraic variety to be deduced easily, such as thedimension and the number of zeros when it is finite. Gröbner basis computation is one of the main practical tools for solvingsystems of polynomial equations and computing the images ofalgebraic varieties underprojections orrational maps.

Gröbner basis computation can be seen as a multivariate, non-linear generalization of bothEuclid's algorithm for computingpolynomial greatest common divisors, andGaussian elimination for linear systems.^[1]

Gröbner bases were introduced byBruno Buchberger in his 1965 Ph.D. thesis, which also included an algorithm to compute them (Buchberger's algorithm). He named them after his advisorWolfgang Gröbner. In 2007, Buchberger received theAssociation for Computing Machinery'sParis Kanellakis Theory and Practice Award for this work.However, the Russian mathematicianNikolai 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 Renschuchet al.^[2] An analogous concept for multivariatepower series was developed independently byHeisuke Hironaka in 1964, who named themstandard 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 overprincipal ideal rings orpolynomial rings, and also some classes of non-commutative rings and algebras, likeOre algebras.

Gröbner bases are primarily defined forideals in apolynomial ring${\displaystyle R=K[x_1,\dots ,x_n]}$ over afieldK. Although the theory works for any field, most Gröbner basis computations are done either whenK is thefield of rationals or the integers modulo a prime number.

In the context of Gröbner bases, a nonzeropolynomial in${\displaystyle R=K[x_1,\dots ,x_n]}$ is commonly represented as a sum${\displaystyle c_1{M}_1+\cdots +c_m{M}_m,}$ where the${\displaystyle c_i}$ are nonzero elements ofK, calledcoefficients, and the${\displaystyle M_i}$ aremonomials (calledpower products by Buchberger and some of his followers) of the form${\displaystyle x_1^{a_1}\cdots x_n^{a_n},}$ where the${\displaystyle a_i}$ are nonnegative integers. The vector${\displaystyle A=[a_1,\dots ,a_n]}$ is called theexponent vector of the monomial. When the list${\displaystyle X=[x_1,\dots ,x_n]}$ of the variables is fixed, the notation of monomials is often abbreviated as${\displaystyle x_1^{a_1}\cdots x_n^{a_n}=X^A.}$

Monomials are uniquely defined by their exponent vectors, and, when amonomial ordering (see below) is fixed, a polynomial is uniquely represented by theordered list of theordered pairs formed by an exponent vector and the corresponding coefficient. This representation of polynomials is especially efficient for Gröbner basis computation in computers, although it is less convenient for other computations such aspolynomial factorization andpolynomial greatest common divisor.

If${\displaystyle F=\{f_1,\dots ,f_k\}}$ is a finite set of polynomials in the polynomial ringR, theideal generated byF is the set of linear combinations of elements ofF with coefficients inR; that is the set of polynomials that can be written$\sum _{i=1}^k{g}_i{f}_i$ with${\displaystyle g_1,\dots ,g_k\in R.}$

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

1. ${\displaystyle M\le N⟺MP\le NP}$
2. ${\displaystyle M\le MP}$.

A total order satisfying these condition is sometimes called anadmissible ordering.

These conditions imply that the order is awell-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 especially important for the applications:

• Lexicographical ordering, commonly calledlex orplex (for pure lexical ordering).
• Total degree reverse lexicographical ordering, commonly calleddegrevlex.
• Elimination ordering,lexdeg.

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". Whenelimination 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 a sorted list of pairs coefficient–exponent vector acanonical representation of the polynomials (that is, two polynomials are equal if and only if they have the same representation).

The first (greatest) term of a polynomialp for this ordering and the corresponding monomial and coefficient are respectively called theleading term,leading monomial andleading coefficient and denoted, in this article,lt(p), lm(p) andlc(p).

Most polynomial operations related to Gröbner bases involve the leading terms. So, the representation of polynomials as sorted lists make these operations particularly efficient (reading the first element of a list takes a constant time, independently of the length of the list).

The other polynomial operations involved in Gröbner basis computations are also compatible with the monomial ordering; that is, they can be performed without reordering the result:

• The addition of two polynomials consists in amerge of the two corresponding lists of terms, with a special treatment in the case of a conflict (that is, when the same monomial appears in the two polynomials).
• The multiplication of a polynomial by a scalar consists of multiplying each coefficient by this scalar, without any other change in the representation.
• The multiplication of a polynomial by a monomialm consists of multiplying each monomial of the polynomial bym. This does not change the term ordering by definition of a monomial ordering.

Let${\displaystyle M=x_1^{a_1}\cdots x_n^{a_n}}$ and${\displaystyle N=x_1^{b_1}\cdots x_n^{b_n}}$ be two monomials, with exponent vectors${\displaystyle A=[a_1,\dots ,a_n]}$ and${\displaystyle B=[b_1,\dots ,b_n].}$

One says thatMdividesN, or thatN is amultiple ofM, if${\displaystyle a_i\le b_i}$ for everyi; that is, ifA is componentwise not greater thanB. In this case, the quotient$\frac{N}{M}$ is defined as$\frac{N}{M}=x_1^{b_1-a_1}\cdots x_n^{b_n-a_n}.$ In other words, the exponent vector of$\frac{N}{M}$ is the componentwise subtraction of the exponent vectors ofN andM.

Thegreatest common divisorgcd(M,N) ofM andN is the monomial$x_1^{min(a_1,b_1)}\cdots x_n^{min(a_n,b_n)}$ whose exponent vector is the componentwise minimum ofA andB. Theleast common multiplelcm(M,N) is defined similarly withmax instead ofmin.

One has

${\displaystyle \mathrm{lcm}(M,N)=\frac{MN}{gcd(M,N)}.}$

Thereduction of a polynomial by other polynomials with respect to a monomial ordering is central to Gröbner basis theory. It is a generalization of bothrow reduction occurring inGaussian elimination and division steps of theEuclidean division of univariate polynomials.^[1] When completed as much as possible, it is sometimes calledmultivariate division although its result is not uniquely defined.

Lead-reduction is a special case of reduction that is easier to compute. It is fundamental for Gröbner basis computation, since general reduction is needed only at the end of a Gröbner basis computation, for getting a reduced Gröbner basis from a non-reduced one.

Let an admissible monomial ordering be fixed, to which refers every monomial comparison that will occur in this section.

A polynomialf islead-reducible by another polynomialg if the leading monomiallm(f) is a multiple oflm(g). The polynomialf isreducible byg if some monomial off is a multiple oflm(g). (So, iff is lead-reducible byg, it is also reducible, butf may be reducible without being lead-reducible.)

Suppose thatf isreducible byg, and letcm be a term off such that the monomialm is a multiple oflm(g). Aone-step reduction off byg consists of replacingf by

${\displaystyle {\mathrm{red}}_1(f,g)=f-\frac{c}{\mathrm{lc}(g)}\frac{m}{\mathrm{lm}(g)}g.}$

This operation removes the monomialm fromf without changing the terms with a monomial greater thanm (for the monomial ordering). In particular, aone step lead-reduction off produces a polynomial all of whose monomials are smaller thanlm(f).

Given a finite setG of polynomials, one says thatf isreducible orlead-reducible byG if it is reducible or lead-reducible, respectively, by at least one elementg ofG. In this case, a one-step reduction (resp. one-step lead-reduction) off byG is any one-step reduction (resp. one-step lead-reduction) off by an element ofG.

The (complete) reduction (resp. lead-reduction) off byG consists of iterating one-step reductions (respect. one-step lead reductions) until getting a polynomial that is irreducible (resp. lead-irreducible) byG. It is sometimes called anormal form off byG. In general this form is not uniquely defined because there are, in general, several elements ofG that can be used for reducingf; this non-uniqueness is the starting point of Gröbner basis theory.

The definition of the reduction shows immediately that, ifh is a normal form off byG, one has

${\displaystyle f=h+\sum _{g\in G}{q}_{g}g,}$

whereh is irreducible byG and the${\displaystyle q_g}$ are polynomials such that${\displaystyle \mathrm{lm}(q_{g}g)\le \mathrm{lm}(f).}$ In the case of univariate polynomials, ifG consists of a single elementg, thenh is the remainder of theEuclidean division off byg, andq_g is the quotient. Moreover, the division algorithm is exactly the process of lead-reduction. For this reason, some authors use the termmultivariate division instead of reduction.

In the example that follows, there are exactly two complete lead-reductions that produce two very different results. The fact that the results are irreducible (not only lead-irreducible) is specific to the example, although this is rather common with such small examples.

In this two variable example, the monomial ordering that is used is thelexicographic order with${\displaystyle x>y,}$ and we consider the reduction of${\displaystyle f=2x^3-x^{2}y+y^3+3y}$, by${\displaystyle G=\{g_1,g_2\},}$ with

For the first reduction step, either the first or the second term off may be reduced. However, the reduction of a term amounts to removing this term at the cost of adding new lower terms; if it is not the first reducible term that is reduced, it may occur 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; that is, in particular, to lead-reduce first until getting a lead-irreducible polynomial.

The leading term${\displaystyle 2x^3}$ off is reducible by${\displaystyle g_1}$ and not by${\displaystyle g_2.}$ So the first reduction step consists of multiplying${\displaystyle g_1}$ by−2x and adding the result tof:$${\displaystyle f\stackrel{\stackrel{}{-2x{g}_1}}{\to }{f}_1=f-2x{g}_1=-x^{2}y-2x{y}^2+2x+y^3+3y.}$$

The leading term${\displaystyle -x^{2}y}$ of${\displaystyle f_1}$ is a multiple of the leading monomials of both${\displaystyle g_1}$ and${\displaystyle g_2,}$ So, one has two choices for the second reduction step. If one chooses${\displaystyle g_2,}$ one gets a polynomial that can be reduced again by${\displaystyle g_2:}$$${\displaystyle f\stackrel{\stackrel{}{-2x{g}_1}}{\to }{f}_1\stackrel{x{g}_2}{\to }-2x{y}^2+y^3+3y\stackrel{2y{g}_2}{\to }{f}_2=y^3-y.}$$No further reduction is possible, so${\displaystyle f_2}$ is a complete reduction off.

One gets a different result with the other choice for the second step:$${\displaystyle f\stackrel{\stackrel{}{-2x{g}_1}}{\to }{f}_1\stackrel{y{g}_1}{\to }-2x{y}^2+2x+2y^3+2y\stackrel{2y{g}_2}{\to }{f}_3=2x+2y^3-2y.}$$Again, the result${\displaystyle f_3}$ is irreducible, although only lead reductions were done.

In summary, the complete reduction off can result in either${\displaystyle f_2=y^3-y}$ or${\displaystyle f_3=2x+2y^3-2y.}$

It is for dealing with the problems set by this non-uniqueness thatBuchberger introduced Gröbner bases andS-polynomials. Intuitively,${\displaystyle 0=f-f}$ may be reduced to${\displaystyle f_2-f_3.}$ This implies that${\displaystyle f_2-f_3}$ belongs to the ideal generated byG. So, this ideal is not changed by adding${\displaystyle f_3-f_2}$ toG, and this allows more reductions. In particular,${\displaystyle f_3}$ can be reduced to${\displaystyle f_2}$ by${\displaystyle f_3-f_2}$ and this restores the uniqueness of the reduced form.

Here Buchberger's algorithm for Gröbner bases would begin by adding toG the polynomial

${\displaystyle g_3=y{g}_1-x{g}_2=2x+y^3-y.}$

This polynomial, calledS-polynomial by Buchberger, is the difference of the one-step reductions of the least common multiple${\displaystyle x^{2}y}$ of the leading monomials of${\displaystyle g_1}$ and${\displaystyle g_2}$, by${\displaystyle g_2}$ and${\displaystyle g_1}$ respectively:

${\displaystyle g_3=\left(x^{2}y-\frac{x^{2}y}{lt(g_2)}{g}_2\right)-\left(x^{2}y-\frac{x^{2}y}{lt(g_1)}{g}_1\right)=\frac{x^{2}y}{lt(g_1)}{g}_1-\frac{x^{2}y}{lt(g_2)}{g}_2}$.

In this example, one has${\displaystyle g_3=f_3-f_2.}$ This does not complete Buchberger's algorithm, asxy gives different results, when reduced by${\displaystyle g_2}$ or${\displaystyle g_3.}$

Given monomial ordering, theS-polynomial orcritical pair of two polynomialsf andg is the polynomial

${\displaystyle S(f,g)={\mathrm{red}}_1(\mathrm{l}\mathrm{c}\mathrm{m},g)-{\mathrm{red}}_1(\mathrm{l}\mathrm{c}\mathrm{m},f)}$;

wherelcm denotes the least common multiple of the leading monomials off andg.Using the definition of${\displaystyle {\mathrm{red}}_1}$, this translates to:

Using the property that relates thelcm and thegcd, theS-polynomial can also be written as:

${\displaystyle S(f,g)=\frac{1}{\mathrm{lc}(f)}\frac{\mathrm{lm}(g)}{\mathrm{g}\mathrm{c}\mathrm{d}}f-\frac{1}{\mathrm{lc}(g)}\frac{\mathrm{lm}(f)}{\mathrm{g}\mathrm{c}\mathrm{d}}g;}$

wheregcd denotes the greatest common divisor of the leading monomials off andg.

As the monomials that are reducible by bothf andg are exactly the multiples oflcm, one can deal with all cases of non-uniqueness of the reduction by considering only theS-polynomials. This is a fundamental fact for Gröbner basis theory and all algorithms for computing them.

For avoiding fractions when dealing with polynomials with integer coefficients, theS polynomial is often defined as

${\displaystyle S(f,g)=\mathrm{lc}(g)\frac{\mathrm{lm}(g)}{\mathrm{g}\mathrm{c}\mathrm{d}}f-\mathrm{lc}(f)\frac{\mathrm{lm}(f)}{\mathrm{g}\mathrm{c}\mathrm{d}}g;}$

This does not change anything to the theory since the two polynomials areassociates.

Let${\displaystyle R=F[x_1,\dots ,x_n]}$ be apolynomial ring over a fieldF. In this section, we suppose that an admissible monomial ordering has been fixed.

LetG be a finite set of polynomials inR thatgenerates anidealI. The setG is a Gröbner basis (with respect to the monomial ordering), or, more precisely, a Gröbner basis ofI if

1. the ideal generated by the leading monomials of the polynomials inI equals the ideal generated by the leading monomials ofG,

or, equivalently,

There are many characterizing properties, which can each be taken as an equivalent definition of Gröbner bases. For conciseness, in the following list, the notation "one-word/another word" means that one can take either "one-word" or "another word" for having two different characterizations of Gröbner bases. All the following assertions are characterizations of Gröbner bases:

Counting the above definition, this provides 12 characterizations of Gröbner bases. The fact that so many characterizations are possible makes Gröbner bases very useful. For example, condition 3 provides an algorithm for testingideal membership; condition 4 provides an algorithm for testing whether a set of polynomials is a Gröbner basis and forms the basis ofBuchberger's algorithm for computing Gröbner bases; conditions 5 and 6 allow computing in${\displaystyle R/I}$ in a way that is very similar tomodular arithmetic.

For every admissible monomial ordering and every finite setG of polynomials, there is a Gröbner basis that containsG and generates the same ideal. Moreover, such a Gröbner basis may be computed withBuchberger's algorithm.

This algorithm uses condition 4, and proceeds roughly as follows: for any two elements ofG, compute the complete reduction byG of theirS-polynomial, and add the result toG if it is not zero; repeat this operation with the new elements ofG included until, eventually, all reductions produce zero.

The algorithm terminates always because ofDickson's lemma or because polynomial rings areNoetherian (Hilbert's basis theorem). Condition 4 ensures that the result is a Gröbner basis, and the definitions ofS-polynomials and reduction ensure that the generated ideal is not changed.

The above method is an algorithm for computing Gröbner bases; however, it is very inefficient. Many improvements of the original Buchberger's algorithm, and several other algorithms have been proposed and implemented, which dramatically improve the efficiency. See§ Algorithms and implementations, below.

A Gröbner basis isminimal if all leading monomials of its elements are irreducible by the other elements of the basis. Given a Gröbner basis of an idealI, one gets a minimal Gröbner basis ofI by removing the polynomials whose leading monomials are multiple of the leading monomial of another element of the Gröbner basis. However, if two polynomials of the basis have the same leading monomial, only one must be removed. So, every Gröbner basis contains a minimal Gröbner basis as a subset.

All minimal Gröbner bases of a given ideal (for a fixed monomial ordering) have the same number of elements, and the same leading monomials, and the non-minimal Gröbner bases have more elements than the minimal ones.

A Gröbner basis isreduced if every polynomial in it is irreducible by the other elements of the basis, and has1 as leading coefficient. So, every reduced Gröbner basis is minimal, but a minimal Gröbner basis need not be reduced.

Given a Gröbner basis of an idealI, one gets a reduced Gröbner basis ofI by first removing the polynomials that are lead-reducible by other elements of the basis (for getting a minimal basis); then replacing each element of the basis by the result of the complete reduction by the other elements of the basis; and, finally, by dividing each element of the basis by its leading coefficient.

All reduced Gröbner bases of an ideal (for a fixed monomial ordering) are equal. It follows that two ideals are equal if and only if they have the same reduced Gröbner basis.

Sometimes, reduced Gröbner bases are defined without the condition on the leading coefficients. In this case, the uniqueness of reduced Gröbner bases is true onlyup to the multiplication of polynomials by a nonzero constant.

When working with polynomials over the field${\displaystyle \mathbb{Q}}$ of therational numbers, it is useful to work only with polynomials with integer coefficients. In this case, the condition on the leading coefficients in the definition of a reduced basis may be replaced by the condition that all elements of the basis areprimitive polynomials with integer coefficients, with positive leading coefficients. This restores the uniqueness of reduced bases.

For every monomial ordering, theempty set of polynomials is the unique Gröbner basis of thezero ideal.

For every monomial ordering, a set of polynomials that contains a nonzero constant is a Gröbner basis of theunit ideal (the whole polynomial ring). Conversely, every Gröbner basis of the unit ideal contains a nonzero constant. The reduced Gröbner basis of the unit is formed by the single polynomial1.

In the case of polynomials in a single variable, there is a unique admissible monomial ordering, the ordering by the degree. The minimal Gröbner bases are thesingletons consisting of a single polynomial. The reduced Gröbner bases are themonic polynomials.

Let${\displaystyle R=\mathbb{Q}[x,y]}$ be the ring of bivariate polynomials with rational coefficients and consider the ideal${\displaystyle I=⟨f,g⟩}$ generated by the polynomials

${\displaystyle f=x^2-y}$,

${\displaystyle g=x^3-x}$.

By reducingg byf, one obtains a new polynomialk such that${\displaystyle I=⟨f,k⟩:}$

${\displaystyle k=g-xf=xy-x.}$

None off andk is reducible by the other, butxk is reducible byf, which gives another polynomial inI:

${\displaystyle h=xk-(y-1)f=y^2-y.}$

Under lexicographic ordering with${\displaystyle x>y}$ we have

lt(f) =x²

lt(k) =xy

lt(h) =y²

Asf,k andh belong toI, and none of them is reducible by the others, none of${\displaystyle \{f,k\},}$${\displaystyle \{f,h\},}$ and${\displaystyle \{h,k\}}$ is a Gröbner basis ofI.

On the other hand,{f,k,h} is a Gröbner basis ofI, since the S-polynomials

can be reduced to zero byf,k andh.

The method that has been used here for findingh andk, and proving that{f,k,h} is a Gröbner basis is a direct application ofBuchberger's algorithm. So, it can be applied mechanically to any similar example, although, in general, there are many polynomials and S-polynomials to consider, and the computation is generally too large for being done without a computer.

Unless explicitly stated, all the results that follow^[3] are true for anymonomial 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 areunique 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).

Thereduction of a polynomialf by the Gröbner basisG of an idealI yields 0if and only iff is inI. This allows to test the membership of an element in an ideal. Another method consists in verifying that the Gröbner basis ofG∪{f} is equal toG.

To test if the idealI generated byf₁, ...,f_k is contained in the idealJ, it suffices to test that everyf_I is inJ. One may also test the equality of the reduced Gröbner bases ofJ andJ ∪ {f₁, ...,f_k}.

Any set of polynomials may be viewed as asystem 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 analgebraically closed field containing the coefficients of the polynomials, is called azero of the ideal. In the usual case ofrational coefficients, this algebraically closed field is chosen as thecomplex field.

An ideal does not have any zero (the system of equations isinconsistent) if and only if 1 belongs to the ideal (this isHilbert'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 basisG of an idealI, it has only a finite number of zeros, if and only if, for each variablex,G contains a polynomial with a leading monomial that is a power ofx (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 ofG. This number is called thedegree 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 thegreatest 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 (seeSystem of polynomial equations for more details).

Thedimension of an idealI in a polynomial ringR is theKrull dimension of the ringR/I and is equal to thedimension of the algebraic set of the zeros ofI. It is also equal to number ofhyperplanes ingeneral position which are needed to have an intersection with the algebraic set, which is a finite number of points. Thedegree 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 ahypersurface is equal to the degree of its definition polynomial.

The dimension depend only on the set of the leading monomials of the Gröbner basis of the ideal for any monomial ordering. The same is true for the degree and degree-compatible monomial orderings; a monomial ordering isdegree compatible is smaller for the degree implies smaller for the monomial ordering.

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

Both dimension anddegree may be deduced from theHilbert series of the ideal, which is the series$\sum _{i=0}^{\mathrm{\infty }}{d}_i{t}^i$, where${\displaystyle d_i}$ is the number of monomials of degreei that are not multiple of any leading monomial in the Gröbner basis.^[4] The Hilbert series may be summed into a rational fraction

${\displaystyle \sum _{i=0}^{\mathrm{\infty }}{d}_i{t}^i=\frac{P(t)}{(1-t{)}^d},}$

whered is the dimension of the ideal and${\displaystyle P(t)}$ is a polynomial. The number${\displaystyle P(1)}$ is thedegree of the algebraic set defined by the ideal, in the case of ahomogeneous ideal or a monomial ordering compatible with the degree; that is, to compare two monomials, one compares their total degrees first.

The dimension does not depend on the choice of a monomial ordering, although the Hilbert series and the polynomial${\displaystyle P(t)}$ may change with changes of the monomial ordering. However, for homogeneous ideals or monomial orderings compatible with the degree, the Hilbert series and the polynomial${\displaystyle P(t)}$ do not depend on the choice of monomial ordering.^[5]

Mostcomputer 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 anelimination monomial ordering allows computationalelimination theory. This is based on the following theorem.

Consider a polynomial ring${\displaystyle K[x_1,\dots ,x_n,y_1,\dots ,y_m]=K[X,Y],}$ in which the variables are split into two subsetsX andY. Let us also choose an elimination monomial ordering "eliminating"X, that is a monomial ordering for which two monomials are compared by comparing first theX-parts, and, in case of equality only, considering theY-parts. This implies that a monomial containing anX-variable is greater than every monomial independent ofX.IfG is a Gröbner basis of an idealI for this monomial ordering, then${\displaystyle G\cap K[Y]}$ is a Gröbner basis of${\displaystyle I\cap K[Y]}$ (this ideal is often called theelimination ideal). Moreover,${\displaystyle G\cap K[Y]}$ consists exactly of the polynomials ofG whose leading terms belong toK[Y] (this makes the computation of${\displaystyle G\cap K[Y]}$ very easy, as only the leading monomials need to be checked).

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

Another application, inalgebraic geometry, is thatelimination realizes the geometric operation ofprojection of anaffine algebraic set into a subspace of the ambient space: with above notation, the (Zariski closure of) the projection of the algebraic set defined by the idealI into theY-subspace is defined by the ideal${\displaystyle I\cap K[Y].}$

The lexicographical ordering such that${\displaystyle x_1>\cdots >x_n}$ is an elimination ordering for every partition${\displaystyle \{x_1,\dots ,x_k\},\{x_{k+1},\dots ,x_n\}.}$ Thus a Gröbner basis for this ordering carries much more information than usually necessary. This may explain why Gröbner bases for the lexicographical ordering are usually the most difficult to compute.

IfI andJ are two ideals generated respectively by {f₁, ...,f_m} and {g₁, ...,g_k}, then a single Gröbner basis computation produces a Gröbner basis of their intersectionI ∩J. For this, one introduces a new indeterminatet, and one uses an elimination ordering such that the first block contains onlyt and the other block contains all the other variables (this means that a monomial containingt is greater than every monomial that does not containt). With this monomial ordering, a Gröbner basis ofI ∩J consists in the polynomials that do not containt, in the Gröbner basis of the ideal

${\displaystyle K=⟨t{f}_1,\dots ,t{f}_m,(1-t)g_1,\dots ,(1-t)g_k⟩.}$

In other words,I ∩J is obtained byeliminatingt inK.This may be proven by observing that the idealK consists of the polynomials${\displaystyle (a-b)t+b}$ such that${\displaystyle a\in I}$ and${\displaystyle b\in J}$. Such a polynomial is independent oft if and only ifa =b, which means that${\displaystyle b\in I\cap J.}$

Arational curve is analgebraic curve that has a set ofparametric equations of the form

where${\displaystyle f_i(t)}$ and${\displaystyle g_i(t)}$ are univariate polynomials for 1 ≤i ≤n. One may (and will) suppose that${\displaystyle f_i(t)}$ and${\displaystyle g_i(t)}$ arecoprime (they have no non-constant common factors).

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

${\displaystyle {\text{Res}}_t(g_1{x}_1-f_1,g_2{x}_2-f_2).}$

Elimination with Gröbner bases allows to implicitize for any value ofn, simply by eliminatingt in the ideal${\displaystyle ⟨g_1{x}_1-f_1,\dots ,g_n{x}_n-f_n⟩.}$Ifn = 2, the result is the same as with the resultant, if the map${\displaystyle t\mapsto (x_1,x_2)}$ is injective for almost everyt. In the other case, the resultant is a power of the result of the elimination.

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 withtriangles, 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 analgebraic set which may have severalirreducible components, and one must remove the components on which the degeneracy conditions are everywhere zero.

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

Thelocalization of a ring consists in adjoining to it the formal inverses of some elements. This section concerns only the case of a single element, or equivalently a finite number of elements (adjoining the inverses of several elements is equivalent to adjoining the inverse of their product). Thelocalization of a ringR by an elementf is the ring${\displaystyle R_f=R[t]/(1-ft),}$ wheret is a new indeterminate representing the inverse off. Thelocalization of an idealI ofR is the ideal${\displaystyle I_f=R_{f}I}$ of${\displaystyle R_f.}$ WhenR is a polynomial ring, computing in${\displaystyle R_f}$ is not efficient because of the need to manage the denominators. Therefore, localization is usually replaced by the operation ofsaturation.

Thesaturation with respect tof of an idealI inR is the inverse image of${\displaystyle R_{f}I}$ under the canonical map fromR to${\displaystyle R_f.}$ It is the ideal${\displaystyle I:f^{\mathrm{\infty }}=\{g\in R\mid (\mathrm{\exists }k\in \mathbb{N})f^{k}g\in I\}}$ consisting in all elements ofR whose product with some power off belongs toI.

IfJ is the ideal generated byI and 1−ft inR[t], then${\displaystyle I:f^{\mathrm{\infty }}=J\cap R.}$ It follows that, ifR is a polynomial ring, a Gröbner basis computation eliminatingt produces a Gröbner basis of the saturation of an ideal by a polynomial.

The important property of the saturation, which ensures that it removes from the algebraic set defined by the idealI theirreducible components on which the polynomialf is zero, is the following:Theprimary decomposition of${\displaystyle I:f^{\mathrm{\infty }}}$consists of the components of the primary decomposition of I that do not contain any power of f.

A Gröbner basis of the saturation byf of a polynomial ideal generated by a finite set of polynomialsF, may be obtained by eliminatingt in${\displaystyle F\cup \{1-tf\},}$ that is by keeping the polynomials independent oft in the Gröbner basis of${\displaystyle F\cup \{1-tf\}}$ for an elimination ordering eliminatingt.

Instead of usingF, one may also start from a Gröbner basis ofF. 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 ofF is usually faster. On the other hand, if the saturation removes some components, the direct computation may be dramatically faster.

If one wants to saturate with respect to several polynomials${\displaystyle f_1,\dots ,f_k}$ or with respect to a single polynomial which is a product${\displaystyle f=f_1\cdots f_k,}$ there are three ways to proceed which give the same result but may have very different computation times (it depends on the problem which is the most efficient).

• Saturating by${\displaystyle f=f_1\cdots f_k}$ in a single Gröbner basis computation.
• Saturating by${\displaystyle f_1,}$ then saturating the result by${\displaystyle f_2,}$ and so on.
• Adding toF or to its Gröbner basis the polynomials${\displaystyle 1-t_1{f}_1,\dots ,1-t_k{f}_k,}$ and eliminating the${\displaystyle t_i}$ in a single Gröbner basis computation.

Hilbert's Nullstellensatz has two versions. The first one asserts that a set of polynomials has no common zeros over analgebraic 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 thehypersurface of the zeros of a polynomialf, if and only if a power off belongs to the ideal. This may be tested by saturating the ideal byf; in fact, a power off belongs to the ideal if and only if the saturation byf provides a Gröbner basis containing 1.

By definition, an affinerational variety of dimensionk may be described byparametric equations of the form

where${\displaystyle p_0,\dots ,p_n}$ aren+1 polynomials in thek variables (parameters of the parameterization)${\displaystyle t_1,\dots ,t_k.}$ Thus the parameters${\displaystyle t_1,\dots ,t_k}$ and the coordinates${\displaystyle x_1,\dots ,x_n}$ of the points of the variety are zeros of the ideal

${\displaystyle I=⟨p_0{x}_1-p_1,\dots ,p_0{x}_n-p_n⟩.}$

One could guess that it suffices to eliminate the parameters to obtain the implicit equations of the variety, as it has been done in the case of curves. Unfortunately this is not always the case. If the${\displaystyle p_i}$ have a common zero (sometimes calledbase point), everyirreducible component of the non-empty algebraic set defined by the${\displaystyle p_i}$ is an irreducible component of the algebraic set defined byI. It follows that, in this case, the direct elimination of the${\displaystyle t_i}$ provides an empty set of polynomials.

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

1. Saturate${\displaystyle I}$ by${\displaystyle p_0}$ to get a Gröbner basis${\displaystyle G}$
2. Eliminate the${\displaystyle t_i}$ from${\displaystyle G}$ to get a Gröbner basis of the ideal (of the implicit equations) of the variety.

Buchberger's algorithm is the oldest algorithm for computing Gröbner bases. It has been devised byBruno Buchberger together with the Gröbner basis theory. It is straightforward to implement, but it appeared soon that raw implementations can solve only trivial problems. The main issues are the following ones:

1. Even when the resulting Gröbner basis is small, the intermediate polynomials can be huge. It results that most of the computing time may be spent inmemory management. So, specialized memory management algorithms may be a fundamental part of an efficient implementation.
2. Theintegers occurring during a computation may be sufficiently large for makingfast multiplication algorithms andmultimodular arithmetic useful. For this reason, most optimized implementations use theGMPlibrary. Also,modular arithmetic,Chinese remainder theorem andHensel lifting are used in optimized implementations
3. The choice of the S-polynomials to reduce and of the polynomials used for reducing them is devoted toheuristics. As in many computational problems, heuristics cannot detect most hidden simplifications, and if heuristic choices are avoided, one may get a dramatic improvement of the algorithm efficiency.
4. In most cases most S-polynomials that are computed are reduced to zero; that is, most computing time is spent to compute zero.
5. Themonomial ordering that is most often needed for the applications (pure lexicographic) is not the ordering that leads to the easiest computation, generally the orderingdegrevlex.

For solving 3. many improvements, variants andheuristics have been proposed before the introduction ofF4 and F5 algorithms byJean-Charles Faugère. As these algorithms are designed for integer coefficients or with coefficients in theintegers modulo a prime number, Buchberger's algorithm remains useful for more general coefficients.

Roughly speaking, F4 algorithm solves 3. by replacing many S-polynomial reductions by therow reduction of a single large matrix for which advanced methods oflinear algebra can be used. This solves partially issue 4., as reductions to zero in Buchberger's algorithm correspond to relations between rows of the matrix to be reduced, and the zero rows of the reduced matrix correspond to abasis of thevector space of these relations.

F5 algorithm improves F4 by introducing a criterion that allows reducing the size of the matrices to be reduced. This criterion is almost optimal, since the matrices to be reduced havefull rank in sufficiently regular cases (in particular, when the input polynomials form aregular sequence). Tuning F5 for a general use is difficult, since its performances depend on an order on the input polynomials and a balance between the incrementation of the working polynomial degree and of the number of the input polynomials that are considered. To date (2022), there is no distributed implementation that is significantly more efficient than F4, but, over modular integers F5 has been used successfully for severalcryptographic challenges; for example, for breakingHFE challenge.

Issue 5. has been solved by the discovery of basis conversion algorithms that start from the Gröbner basis for one monomial ordering for computing a Gröbner basis for another monomial ordering.FGLM algorithm is such a basis conversion algorithm that works only in the zero-dimensional case (where the polynomials have a finite number of complex common zeros) and has apolynomial complexity in the number of common zeros. A basis conversion algorithm that works is the general case is theGröbner walk algorithm.^[6] In its original form, FGLM may be the critical step for solvingsystems of polynomial equations because FGML does not take into account thesparsity of involved matrices. This has been fixed by the introduction ofsparse FGLM algorithms.^[7]

Most general-purposecomputer algebra systems have implementations of one or several algorithms for Gröbner bases, often also embedded in other functions, such as for solving systems of polynomial equations or for simplifying trigonometric functions; this is the case, for example, ofCoCoA,GAP,Macaulay 2,Magma,Maple,Mathematica,SINGULAR,SageMath andSymPy. When F4 is available, it is generally much more efficient than Buchberger's algorithm. The implementation techniques and algorithmic variants are not always documented, although they may have a dramatic effect on efficiency.

Implementations of F4 and (sparse)-FGLM are included in thelibraryMsolve.^[8] Beside Gröbner algorithms, Msolve contains fast algorithms forreal-root isolation, and combines all these functions in an algorithm for the real solutions ofsystems of polynomial equations that outperforms dramatically the other software for this problem (Maple and Magma).^[8] Msolve is available onGitHub, and is interfaced withJulia, Maple and SageMath; this means that Msolve can be used directly from within these software environments.

Thecomplexity of the Gröbner basis computations is commonly evaluated in term of the numbern of variables and the maximal degreed of the input polynomials.

In the worst case, the main parameter of the complexity is the maximal degree of the elements of the resulting reduced Gröbner basis. More precisely, if the Gröbner basis contains an element of a large degreeD, this element may contain${\displaystyle \mathrm{\Omega }(D^n)}$ nonzero terms whose computation requires a time of${\displaystyle \mathrm{\Omega }(D^n)>D^{\mathrm{\Omega }(n)}.}$ On the other hand, if all polynomials in the reduced Gröbner basis ahomogeneous ideal have a degree of at mostD, the Gröbner basis can be computed bylinear algebra on thevector space of polynomials of degree less than2D, which has a dimension${\displaystyle O(D^n).}$^[1] So, the complexity of this computation is${\displaystyle O(D^n{)}^{O(1)}=D^{O(n)}.}$

The worst-case complexity of a Gröbner basis computation is doubly exponential inn. More precisely, the complexity is upper bounded by a polynomial in$d^{2^n}.$ Usinglittle o notation, it is therefore bounded by$d^{2^{n+o(n)}}.$ On the other hand, examples have been given of reduced Gröbner bases containing polynomials of degree$d^{2^{\mathrm{\Omega }(n)}},$or containing$d^{2^{\mathrm{\Omega }(n)}}$ elements. As every algorithm for computing a Gröbner basis must write its result, this provides a lower bound of the complexity.

Gröbner basis isEXPSPACE-complete.^[9]

The concept and algorithms of Gröbner bases have been generalized tosubmodules offree modules over a polynomial ring. In fact, ifL is a free module over a ringR, then one may consider thedirect sum${\displaystyle R\oplus L}$ as a ring by defining the product of two elements ofL to be0. This ring may be identified with${\displaystyle R[e_1,\dots ,e_l]/⟨\{e_i{e}_j|1\le i\le j\le l\}⟩}$, where${\displaystyle e_1,\dots ,e_l}$ is a basis ofL. This allows identifying a submodule ofL generated by${\displaystyle g_1,\dots ,g_k}$ with the ideal of${\displaystyle R[e_1,\dots ,e_l]}$ generated by${\displaystyle g_1,\dots ,g_k}$ and the products${\displaystyle e_i{e}_j}$,${\displaystyle 1\le i\le j\le l}$. IfR is a polynomial ring, this reduces the theory and the algorithms of Gröbner bases of modules to the theory and the algorithms of Gröbner bases of ideals.

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

Gröbner bases have 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,^[10] affine variety codes,^[11] algebraic-geometric codes and even general linear block codes.^[12] Applying Gröbner basis in algebraic decoding is still a research area of channelcoding theory.

• Bergman's diamond lemma, an extension of Gröbner bases to non-commutative rings
• Graver basis
• Janet basis
• Regular chains, an alternative way to represent algebraic sets

• Adams, William W.; Loustaunau, Philippe (1994).An Introduction to Gröbner Bases.Graduate Studies in Mathematics. Vol. 3.American Mathematical Society.ISBN 0-8218-3804-0.
• Li, Huishi (2011).Gröbner Bases in Ring Theory.World Scientific.ISBN 978-981-4365-13-0.
• Becker, Thomas; Weispfenning, Volker (1998).Gröbner Bases: A Computational Approach to Commutative Algebra. Graduate Texts in Mathematics. Vol. 141. Springer.ISBN 0-387-97971-9.
• Buchberger, Bruno (1965).An Algorithm for Finding the Basis Elements of the Residue Class Ring of a Zero Dimensional Polynomial Ideal(PDF) (PhD). University of Innsbruck.— (2006)."Bruno Buchberger's PhD thesis 1965: An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal".Journal of Symbolic Computation.41 (3–4). Translated by Abramson, M.:471–511.doi:10.1016/j.jsc.2005.09.007. [This is Buchberger's thesis inventing Gröbner bases.]
• Buchberger, Bruno (1970)."An Algorithmic Criterion for the Solvability of a System of Algebraic Equations"(PDF).Aequationes Mathematicae.4:374–383.doi:10.1007/BF01844169.S2CID 189834323. (This is the journal publication of Buchberger's thesis.)Burchberger, B.; Winkler, F., eds. (26 February 1998)."An Algorithmic Criterion for the Solvability of a System of Algebraic Equations".Gröbner Bases and Applications. London Mathematical Society Lecture Note Series. Vol. 251. Cambridge University Press. pp. 535–545.ISBN 978-0-521-63298-0.
• Buchberger, Bruno; Kauers, Manuel (2010)."Gröbner Bases".Scholarpedia.5 (10): 7763.Bibcode:2010SchpJ...5.7763B.doi:10.4249/scholarpedia.7763.
• Fröberg, Ralf (1997).An Introduction to Gröbner Bases. Wiley.ISBN 0-471-97442-0.
• Sturmfels, Bernd (November 2005)."What is ... a Gröbner Basis?"(PDF).Notices of the American Mathematical Society.52 (10):1199–1200, a brief introduction{{cite journal}}: CS1 maint: postscript (link)
• Shirshov, Anatoliĭ I. (1999)."Certain algorithmic problems for Lie algebras"(PDF).ACM SIGSAM Bulletin.33 (2):3–6.doi:10.1145/334714.334715.S2CID 37070503. (translated from Sibirsk. Mat. Zh. Siberian Mathematics Journal3 (1962), 292–296).
• Aschenbrenner, Matthias; Hillar, Christopher (2007)."Finite generation of symmetric ideals".Transactions of the American Mathematical Society.359 (11):5171–92.arXiv:math/0411514.doi:10.1090/S0002-9947-07-04116-5.S2CID 5656701. (on infinite dimensional Gröbner bases for polynomial rings in infinitely many indeterminates).

• Faugère's own implementation of his F4 algorithm
• "Gröbner basis",Encyclopedia of Mathematics,EMS Press, 2001 [1994]
• Buchberger, B. (2003)."Gröbner Bases: A Short Introduction for Systems Theorists"(PDF). In Moreno-Diaz, R.; Buchberger, B.; Freire, J. (eds.).Computer Aided Systems Theory — EUROCAST 2001: A Selection of Papers from the 8th International Workshop on Computer Aided Systems Theory. Springer. pp. 1–19.ISBN 978-3-540-45654-4.
• Buchberger, B.; Zapletal, A."Gröbner Bases Bibliography".
• Comparative Timings Page for Gröbner Bases Software
• Prof. Bruno Buchberger Bruno Buchberger
• Weisstein, Eric W."Gröbner Basis".MathWorld.
• Gröbner basis introduction onScholarpedia

• Algebraic geometry
• Commutative algebra
• Computer algebra
• Invariant theory
• Rewriting systems

• CS1 maint: numeric names: authors list
• Articles with short description
• Short description is different from Wikidata
• Use American English from March 2019
• All Wikipedia articles written in American English
• CS1 maint: postscript