6.31.1  Gröbner basis: gbasis

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.

• Input:
  gbasis([2*x*y-y^2,x^2-2*x*y],[x,y])
  Output:

  ⎡ ⎣

  y3,x2−y2,2 x y−y2

  ⎤ ⎦

  Input:
  gbasis([x1+x2+x3,x1*x2+x1*x3+x2*x3,x1*x2*x3-1], [x1,x2,x3],tdeg,with_cocoa=false)
  Output:

  ⎡ ⎣

  x33−1,−x22−x2 x3−x32,x1+x2+x3

  ⎤ ⎦