11.5.1  Gröbner basis

A set of polynomials {F₁,…,F_N} generate an ideal I; namely, I is the set of all linear combinations of the F_j. Given such an ideal, a Gröbner basis for I is a subset G={G₁,…,G_n} of I such that for any F in I, there is a G_k in G such that the leading monomial of G_k divides the leading monomial of F. (Note that the leading monomial depends on a fixed ordering of the monomials.)

If G is a Gröbner basis for such an ideal I, then for any nonzero F in I, if you do a Euclidean division of F by the corresponding G_k, take the remainder of this division, do again the same and so on, at some point you get a remainder of zero.

Example

Let I be the ideal generated by {x³−2xy, x²y−2y²+x} with the standard lexicographic order on the monomials. One Gröbner basis for I is

Consider the element F(x,y)=2x²y−3x²+6xy−4y²+2x of I. The leading monomial x²y of F(x,y) is divisible by the leading monomial x² of g₁(x,y). Dividing F(x,y) by g₁(x,y) leaves a remainder of R₁(x,y)=6xy−4y²+2x. The leading monomial of R₁(x,y), which is xy, is divisible by the leading monomial of g₂(x,y), which is xy. Dividing R₁(x,y) by g₂(x,y) leaves a remainder of R₂(x,y)=−4y²+2x. Finally, the leading monomial of R₂(x,y), which is y², is divisible by the leading monomial of g₃(x,y), which is y². Dividing R₂(x,y) by g₃(x,y) leaves a remainder of 0.

The gbasis command computes Gröbner bases.

• gbasis takes two mandatory arguments and three optional arguments:
  • polys, a list of polynomials.
  • vars, a list of the variable names.
  • Optionally, order, which can be one of:
    • plex, to order the monomials lexicographically (this is the default).
    • tdeg, to order the monomials first by total degree then by lexicographic order.
    • revlex, to order the monomials reverse lexicographically.
  • Optionally, with_cocoa=boolean, where boolean can be true or false. A value of true means to use the CoCoA library to compute the Gröbner basis, a value of false means not to use it.

    A value of true is recommended, but requires that CoCoA support be compiled into Xcas.

  • Optionally, with_f5=boolean, where boolean can be true or false. A value of true means to use the F5 algorithm of the CoCoA library, a value of false means not to use it. If this is true, then the polynomials are homogenized and so the specified order is not used.
• gbasis(polys,vars ⟨,order,with_cocoa=boolean, with_f5=boolean ⟩) returns a Gröbner basis of the ideal spanned by polynomials in polys.

Note that the lexicographic order depends on the order the variables are given in vars. For example, if vars=[x,y,z], then x^2*y^4*z^3 comes before x^2*y^3*z^4, but if vars=[x,z,y], then x^2*y^4*z^3 comes after x^2*y^3*z^4.

Examples