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 [ x 1 , … , x n ] {\displaystyle K[x_{1},\ldots ,x_{n}]} over a field K {\displaystyle 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. Gröbner bases were introduced by Bruno Buchberger in his 1965 Ph.D. thesis, which also included an algorithm to compute them (Buchberger's algorithm). 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. 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.
Tools
Polynomial ring
Gröbner bases are primarily defined for ideals in a polynomial ring R = K [ x 1 , … , x n ] {\displaystyle R=K[x_{1},\ldots ,x_{n}]} over a field K. Although the theory works for any field, most Gröbner basis computations are done either when K is the field of rationals or the integers modulo a prime number. In the context of Gröbner bases, a nonzero polynomial in R = K [ x 1 , … , x n ] {\displaystyle R=K[x_{1},\ldots ,x_{n}]} is commonly represented as a sum c 1 M 1 + ⋯ + c m M m , {\displaystyle c_{1}M_{1}+\cdots +c_{m}M_{m},} where the c i {\displaystyle c_{i}} are nonzero elements of K, called coefficients, and the M i {\displaystyle M_{i}} are monomials (called power products by Buchberger and some of his followers) of the form x 1 a 1 ⋯ x n a n , {\displaystyle x_{1}^{a_{1}}\cdots x_{n}^{a_{n}},} where the a i {\displaystyle a_{i}} are nonnegative integers. The vector A = [ a 1 , … , a n ] {\displaystyle A=[a_{1},\ldots ,a_{n}]} is called the exponent vector of the monomial. When the list X = [ x 1 , … , x n ] {\displaystyle X=[x_{1},\ldots ,x_{n}]} of the variables is fixed, the notation of monomials is often abbreviated as x 1 a 1 ⋯ x n a n = X A . {\displaystyle x_{1}^{a_{1}}\cdots x_{n}^{a_{n}}=X^{A}.}
Monomials are uniquely defined by their exponent vectors, and, when a monomial ordering (see below) is fixed, a polynomial is uniquely represented by the ordered list of the ordered 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 as polynomial factorization and polynomial greatest common divisor. If F = { f 1 , … , f k } {\displaystyle F=\{f_{1},\ldots ,f_{k}\}} is a finite set of polynomials in the polynomial ring R, the ideal generated by F is the set of linear combinations of elements of F with coefficients in R; that is the set of polynomials that can be written ∑ i = 1 k g i f i {\textstyle \sum _{i=1}^{k}g_{i}f_{i}} with g 1 , … , g k ∈ R . {\displaystyle g_{1},\ldots ,g_{k}\in R.}
Monomial ordering
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,
M ≤ N ⟺ M P ≤ N P {\displaystyle M\leq N\Longleftrightarrow MP\leq NP}
M ≤ M P {\displaystyle M\leq MP} . 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 especially important for the applications:
Lexicographical ordering, commonly called lex or plex (for pure lexical ordering). Total degree reverse lexicographical ordering, commonly called degrevlex. 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". 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.
Basic operations
Leading term, coefficient and monomial Once a monomial ordering is fixed, the terms of a polynomial (a term is the 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 a canonical 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 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). 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).
Polynomial operations 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 a merge 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 monomial m consists of multiplying each monomial of the polynomial by m. This does not change the term ordering by definition of a monomial ordering.
Divisibility of monomials Let M = x 1 a 1 ⋯ x n a n {\displaystyle M=x_{1}^{a_{1}}\cdots x_{n}^{a_{n}}} and N = x 1 b 1 ⋯ x n b n {\displaystyle N=x_{1}^{b_{1}}\cdots x_{n}^{b_{n}}} be two monomials, with exponent vectors A = [ a 1 , … , a n ] {\displaystyle A=[a_{1},\ldots ,a_{n}]} and B = [ b 1 , … , b n ] . {\displaystyle B=[b_{1},\ldots ,b_{n}].}
One says that M divides N, or that N is a multiple of M, if a i ≤ b i {\displaystyle a_{i}\leq b_{i}} for every i; that is, if A is componentwise not greater than B. In this case, the quotient N M {\textstyle {\frac {N}{M}}} is defined as N M = x 1 b 1 − a 1 ⋯ x n b n − a n . {\textstyle {\frac {N}{M}}=x_{1}^{b_{1}-a_{1}}\cdots x_{n}^{b_{n}-a_{n}}.} In other words, the exponent vector of N M {\textstyle {\frac {N}{M}}} is the componentwise subtraction of the exponent vectors of N and M. The greatest common divisor gcd(M, N) of M and N is the monomial x 1 min ( a 1 , b 1 ) ⋯ x n min ( a n , b n ) {\textstyle x_{1}^{\min(a_{1},b_{1})}\cdots x_{n}^{\min(a_{n},b_{n})}} whose exponent vector is the componentwise minimum of A and B. The least common multiple lcm(M, N) is defined similarly with max instead of min. One has
lcm ( M , N ) = M N gcd ( M , N ) . {\displaystyle \operatorname {lcm} (M,N)={\frac {MN}{\gcd(M,N)}}.}
Reduction The reduction of a polynomial by other polynomials with respect to a monomial ordering is central to Gröbner basis theory. It is a generalization of both row reduction occurring in Gaussian elimination and division steps of the Euclidean division of univariate polynomials. When completed as much as possible, it is sometimes called multivariate 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 polynomial f is lead-reducible by another polynomial g if the leading monomial lm(f) is a multiple of lm(g). The polynomial f is reducible by g if some monomial of f is a multiple of lm(g). (So, if f is lead-reducible by g, it is also reducible, but f may be reducible without being lead-reducible.) Suppose that f is reducible by g, and let cm be a term of f such that the monomial m is a multiple of lm(g). A one-step reduction of f by g consists of replacing f by
red 1 ( f , g ) = f − c lc ( g ) m lm ( g ) g . {\displaystyle \operatorname {red} _{1}(f,g)=f-{\frac {c}{\operatorname {lc} (g)}}\,{\frac {m}{\operatorname {lm} (g)}}\,g.}
This operation removes the monomial m from f without changing the terms with a monomial greater than m (for the monomial ordering). In particular, a one step lead-reduction of f produces a polynomial all of whose monomials are smaller than lm(f). Given a finite set G of polynomials, one says that f is reducible or lead-reducible by G if it is reducible or lead-reducible, respectively, by at least one element g of G. In this case, a one-step reduction (resp. one-step lead-reduction) of f by G is any one-step reduction (resp. one-step lead-reduction) of f by an element of G. The (complete) reduction (resp. lead-reduction) of f by G consists of iterating one-step reductions (respect. one-step lead reductions) until getting a polynomial that is irreducible (resp. lead-irreducible) by G. It is sometimes called a normal form of f by G. In general this form is not uniquely defined because there are, in general, several elements of G that can be used for reducing f; this non-uniqueness is the starting point of Gröbner basis theory. The definition of the reduction shows immediately that, if h is a normal form of f by G, one has
f = h + ∑ g ∈ G q g g , {\displaystyle f=h+\sum _{g\in G}q_{g}\,g,}
where h is irreducible by G and the q g {\displaystyle q_{g}} are polynomials such that lm ( q g g ) ≤ lm ( f ) . {\displaystyle \operatorname {lm} (q_{g}\,g)\leq \operatorname {lm} (f).} In the case of univariate polynomials, if G consists of a single element g, then h is the remainder of the Euclidean division of f by g, and qg is the quotient. Moreover, the division algorithm is exactly the process of lead-reduction. For this reason, some authors use the term multivariate division instead of reduction.
Non uniqueness 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 the lexicographic order with x > y , {\displaystyle x>y,} and we consider the reduction of f = 2 x 3 − x 2 y + y 3 + 3 y {\displaystyle f=2x^{3}-x^{2}y+y^{3}+3y} , by G = { g 1 , g 2 } , {\displaystyle G=\{g_{1},g_{2}\},} with g 1 = x 2 + y 2 − 1 , g 2 = x y − 2. {\displaystyle {\begin{aligned}g_{1}&=x^{2}+y^{2}-1,\\g_{2}&=xy-2.\end{aligned}}}
For the first reduction step, either the first or the second term of f 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 2 x 3 {\displaystyle 2x^{3}} of f is reducible by g 1 {\displaystyle g_{1}} and not by g 2 . {\displaystyle g_{2}.} So the first reduction step consists of multiplying g 1 {\displaystyle g_{1}} by −2x and adding the result to f:
f → − 2 x g 1 f 1 = f − 2 x g 1 = − x 2 y − 2 x y 2 + 2 x + y 3 + 3 y . {\displaystyle f\;\xrightarrow {\overset {}{-2xg_{1}}} \;f_{1}=f-2xg_{1}=-x^{2}y-2xy^{2}+2x+y^{3}+3y.}
The leading term − x 2 y {\displaystyle -x^{2}y} of f 1 {\displaystyle f_{1}} is a multiple of the leading monomials of both g 1 {\displaystyle g_{1}} and g 2 , {\displaystyle g_{2},} So, one has two choices for the second reduction step. If one chooses g 2 , {\displaystyle g_{2},} one gets a polynomial that can be reduced again by g 2 : {\displaystyle g_{2}\colon }
f → − 2 x g 1 f 1 → x g 2 − 2 x y 2 + y 3 + 3 y → 2 y g 2 f 2 = y 3 − y . {\displaystyle f\;\xrightarrow {\overset {}{-2xg_{1}}} \;f_{1}\;\xrightarrow {xg_{2}} \;-2xy^{2}+y^{3}+3y\;\xrightarrow {2yg_{2}} \;f_{2}=y^{3}-y.}
No further reduction is possible, so f 2 {\displaystyle f_{2}} is a complete reduction of f. One gets a different result with the other choice for the second step:
f → − 2 x g 1 f 1 → y g 1 − 2 x y 2 + 2 x + 2 y 3 + 2 y → 2 y g 2 f 3 = 2 x + 2 y 3 − 2 y . {\displaystyle f\;\xrightarrow {\overset {}{-2xg_{1}}} \;f_{1}\;\xrightarrow {yg_{1}} \;-2xy^{2}+2x+2y^{3}+2y\;\xrightarrow {2yg_{2}} \;f_{3}=2x+2y^{3}-2y.}
Again, the result f 3 {\displaystyle f_{3}} is irreducible, although only lead reductions were done. In summary, the complete reduction of f can result in either f 2 = y 3 − y {\displaystyle f_{2}=y^{3}-y} or f 3 = 2 x + 2 y 3 − 2 y . {\displaystyle f_{3}=2x+2y^{3}-2y.}
It is for dealing with the problems set by this non-uniqueness that Buchberger introduced Gröbner bases and S-polynomials. Intuitively, 0 = f − f {\displaystyle 0=f-f} may be reduced to f 2 − f 3 . {\displaystyle f_{2}-f_{3}.} This implies that f 2 − f 3 {\displaystyle f_{2}-f_{3}} belongs to the ideal generated by G. So, this ideal is not changed by adding f 3 − f 2 {\displaystyle f_{3}-f_{2}} to G, and this allows more reductions. In particular, f 3 {\displaystyle f_{3}} can be reduced to f 2 {\displaystyle f_{2}} by f 3 − f 2 {\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 to G the polynomial
g 3 = y g 1 − x g 2 = 2 x + y 3 − y . {\displaystyle g_{3}=yg_{1}-xg_{2}=2x+y^{3}-y.}
This polynomial, called S-polynomial by Buchberger, is the difference of the one-step reductions of the least common multiple x 2 y {\displaystyle x^{2}y} of the leading monomials of g 1 {\displaystyle g_{1}} and g 2 {\displaystyle g_{2}} , by g 2 {\displaystyle g_{2}} and g 1 {\displaystyle g_{1}} respectively:
g 3 = ( x 2 y − x 2 y l t ( g 2 ) g 2 ) − ( x 2 y − x 2 y l t ( g 1 ) g 1 ) = x 2 y l t ( g 1 ) g 1 − x 2 y l t ( g 2 ) g 2 {\displaystyle g_{3}=\left(x^{2}y-{\frac {x^{2}y}{\mathrm {lt} (g_{2})}}g_{2}\right)-\left(x^{2}y-{\frac {x^{2}y}{\mathrm {lt} (g_{1})}}g_{1}\right)={\frac {x^{2}y}{\mathrm {lt} (g_{1})}}g_{1}-{\frac {x^{2}y}{\mathrm {lt} (g_{2})}}g_{2}} . In this example, one has g 3 = f 3 − f 2 . {\displaystyle g_{3}=f_{3}-f_{2}.} This does not complete Buchberger's algorithm, as xy gives different results, when reduced by g 2 {\displaystyle g_{2}} or g 3 . {\displaystyle g_{3}.}
S-polynomial Given monomial ordering, the S-polynomial or critical pair of two polynomials f and g is the polynomial
S ( f , g ) = red 1 ( l c m , g ) − red 1 ( l c m , f ) {\displaystyle S(f,g)=\operatorname {red} _{1}(\mathrm {lcm} ,g)-\operatorname {red} _{1}(\mathrm {lcm} ,f)} ; where lcm denotes the least common multiple of the leading monomials of f and g. Using the definition of red 1 {\displaystyle \operatorname {red} _{1}} , this translates to:
S ( f , g ) = ( l c m − 1 lc ( g ) l c m lm ( g ) g ) − ( l c m − 1 lc ( f ) l c m lm ( f ) f ) = 1 lc ( f ) l c m lm ( f ) f − 1 lc ( g ) l c m lm ( g ) g . {\displaystyle {\begin{aligned}S(f,g)&=\left(\mathrm {lcm} -{\frac {1}{\operatorname {lc} (g)}}\,{\frac {\mathrm {lcm} }{\operat