MAGMA Computational Algebra System

Gröbner Bases

Computation in ideals of multivariate polynomial rings is possible because of the construction of Gröbner bases of such ideals. In Magma, it is possible to create ideals and compute their Gröbner bases for polynomial rings defined not only over fields but also over general Euclidean rings.

Different monomial orderings give different Gröbner bases for a fixed ideal. When an ideal I is created from a polynomial ring P or another ideal J, then the monomial order of I is taken to be the monomial order of P or J. Ideals can only be compatible if they have the same monomial order.

Subsections

• Gröbner Bases over Fields
• Gröbner Bases over Euclidean Rings
• Construction of Gröbner Bases
• Related Functions
• Gröbner Bases of Boolean Polynomial Rings
• Verbosity
• Degree-d Gröbner Bases

Gröbner Bases over Fields

Gröbner bases of ideals defined over fields have been studied for some time now, and there is a large literature concerning them.

For ideals defined over fields, a basis is called minimal if each polynomial in it is monic and not contained in the ideal generated by all the other polynomials [CLO96, Chap. 2, Para 7, Def. 4]. A basis is called reduced if each polynomial in it is monic and, for every monomial of each polynomial in the basis, that monomial is not divisible by the leading monomial of any other polynomial in the basis (equivalently, each leading monomial does not divide any monomial in any of the other polynomials) [CLO96, Chap. 2, Para 7, Def. 5].

For a given fixed monomial ordering, every ideal of a polynomial ring over a field possesses a unique sorted minimal reduced Gröbner basis (GB) [CLO96, Chap. 2, Para 7, Prop. 7]. This unique Gröbner basis (with respect to the order defined by the user) will be computed automatically when needed by Magma. Before this happens, an ideal will usually possess a basis which is not a Gröbner basis, but that will be changed into the unique Gröbner basis when needed. Thus the original basis will be discarded. See the procedure Groebner below for details on the algorithms available.

Gröbner Bases over Euclidean Rings

Since V2.8 (July 2001), Magma provides facilities for computing with Gröbner bases of ideals of polynomial rings over Euclidean rings (including the important case of the integer ring Z). Such Gröbner bases are computed in Magma by an extension, due to Allan Steel (unpublished), of Jean-Charles Faugère's F₄ algorithm [Fau99], which uses sparse linear algebra.

The current Euclidean rings in Magma supported are: the integer ring Z, the integer residue class rings Z_m, the univariate polynomial rings K[x] over any field K, Galois rings, p-adic quotient rings, and valuation rings.

We first outline some of the things which are peculiar to Gröbner bases defined over a Euclidean ring. Let I be an ideal of a polynomial ring defined over a Euclidean ring R. A subset G of I is called a Gröbner basis for I in Magma if, for every f∈I, there exists a g∈G such that the leading term of g divides the leading term of f. Recall that "leading term" here means the leading coefficient times the leading monomial, so the leading coefficient of g must divide the leading coefficient of f in the base ring R. If R were a field, then obviously the leading coefficients would be insignificant and the Gröbner basis elements could be normalized (made monic) to yield an equivalent Gröbner basis. But if R is not a field, the leading coefficients are quite significant. For example, over the ring Z, the set { x², 2x } is a Gröbner basis and the polynomial x² is not redundant since 2 does not divide 1, but over Q, the polynomial x² would be redundant.

Note that the definition here for a Gröbner basis in Magma is actually what some authors (e.g., [AL94, Def. 4.5.6]) call a strong Gröbner basis. Weak Gröbner bases have also been defined, but strong Gröbner bases satisfy stronger conditions, yield a simple effective normal form algorithm, provide more information about the ideal, are easier to get into a unique form, and are no more difficult to compute using the algorithm implemented in Magma. Thus Magma always computes a strong Gröbner basis, so the distinction between weak and strong is ignored. Magma also effectively computes a D-Gröbner basis as defined in [BW93, Def. 10.4, Table 10.1], although Magma also allows Euclidean rings which are not integral domains (i.e., which have zero divisors).

Over Euclidean rings, the definition of a minimal basis is practically the same as for fields (there must be no polynomial in the ideal generated by the others and each polynomial must be normalized), but the definition of a reduced basis is more subtle. A basis is called reduced if each polynomial in it is normalized and if, for every term c.s of every polynomial in the basis (where c is the coefficient and s is the monomial), then if some other polynomial in the basis has leading term d.t, with t dividing s, then the Euclidean quotient of c by d must be zero (the remainder will be non-zero of course). Informally, this means that each polynomial is reduced modulo all the other polynomials, where each coefficient must be reduced modulo all other appropriate leading coefficients. As an example, suppose f₁ = x² + 14xy and f₂ = 5y + 9 are in Z[x, y]. Then { f₁, f₂ } is not reduced, since the second term of f₁ can be reduced by f₂ (y divides xy and the Euclidean quotient of 14 by 5 is 2, with remainder 4). But if we were to replace f₁ by f₁ - 2xf₂ = x² + 4xy - 18x, then { f₁, f₂ } would now be reduced.

Magma's extension of Faugère's algorithm depends on sparse linear algebra over Euclidean rings. (Note also that the advanced criteria for eliminating useless pairs in [Möl88]) are also implemented in this extension to work for general Euclidean rings as well.) Magma now contains an algorithm for computing a unique echelon form of a sparse matrix over such a ring; uniqueness is ensured because there is a unique Euclidean quotient-remainder algorithm for each Euclidean ring (and zero divisors are also handled properly). Consequently, based on this unique echelon form algorithm and some other techniques, Magma ensures that a Gröbner basis over a Euclidean ring is not only minimal (contains no redundant polynomials), but it is also reduced, and unique.

Thus every ideal of a polynomial ring over a Euclidean ring possesses a unique sorted minimal reduced Gröbner basis (with respect to some fixed monomial ordering), just as for ideals defined over fields. Also, as for ideals defined over fields, this unique Gröbner basis will be computed automatically when needed by Magma, and before this happens, an ideal will usually possess a basis which is not a Gröbner basis, but that will be changed into the unique Gröbner basis when needed.

The uniqueness of the Gröbner basis also ensures that the normal form of an element with respect to an ideal for a fixed monomial order is always unique. All of this holds even for Euclidean rings which have zero divisors.

See the examples below for illustrations of the points made above, and also how one can effectively compute with Gröbner bases of ideals defined over rings which are not even Euclidean.

Construction of Gröbner Bases

The following functions and procedures allow one to construct Gröbner bases. Note that a Gröbner basis for an ideal will be automatically generated when necessary; the Groebner procedure below simply allows control of the algorithms used to compute the Gröbner basis.

NOTE: Magma applies a special monomial representation and a special variant of the F₄ algorithm if the ideal I is defined over GF(2) and the polynomials (x_i)² + x_i for all i are present in the input basis of the ideal I. So if one wishes to solve a system of equations over GF(2), then one should include these polynomials in the input basis (they can be at any place and in any order; as long as there is at least one copy of (x_i)² + x_i present for each i). Alternatively (since V2.15), one can create a boolean polynomial ring (via the function BooleanPolynomialRing below) and construct the ideal within this. See also Example H98E5 below.

Groebner(I: parameters) : RngMPol ->

(Procedure.) Explicitly force a Gröbner basis (GB) for the ideal I to be constructed. This procedure is normally not necessary, as Magma will automatically compute the GB when needed, but it does allow one to control how the GB is constructed by various parameters.

By default, the parameters are set to default values which tend to work best for the particular kinds of inputs which are given, but there exist many inputs for which setting at least one of the parameters to a non-default value will lead to a dramatic improvement. (A general strategy for the computation of GBs is very difficult to design.)

If I is defined over a Euclidean ring, then Magma always uses the extension of the Faugère algorithm directly, and of the parameters given below, only Homogenize is applicable. So the rest of this description assumes that I is defined over a field.

We call a GB algorithm direct if it takes the initial basis of the ideal I (with no structure) and computes the unique minimal reduced GB of I with respect to some monomial order. Since V2.11 (May 2004), Magma has two direct algorithms for computing GBs over fields:

(1)

The Faugère F₄ algorithm [Fau99], which works by specialized sparse linear algebra and is applicable to ideals defined over a finite field or the rational field;

(2)

The Buchberger algorithm [CLO96, Chap. 2, Para 7] for ideals defined over any field.

Both direct algorithms use the advanced criteria for eliminating useless pairs in [Möl88]. Magma also uses two order change algorithms which both change the GB of an ideal with respect to one monomial order to the GB with respect to another monomial order:

(1)

The FGLM algorithm [FGLM93], which works by efficient linear algebra and is only applicable if I is zero-dimensional;

(2)

The Gröbner Walk algorithm [CKM97].

This parameter affects the main strategy:

     Al: MonStgElt                       Default: "Default"

The parameter Al may be set to one of: "Default", "Direct", "FGLM" or "Walk". The value "Direct" specifies that Magma should compute the GB of I (with respect to the order of I) by a direct algorithm alone, so that an order-conversion algorithm is not used (the parameter Faugere below controls which direct algorithm is used).

The alternative strategy is to compute the GB first with respect to an "easy" order, and then to convert this to the GB with respect to the order of I. Setting Al to the values "FGLM" or "Walk" will cause this strategy to be used, where the order change algorithm will be the FGLM algorithm or Gröbner Walk algorithm, respectively.

If no algorithm is specified, or if "Default" is specified, an appropriate strategy is chosen by Magma, which is usually the FGLM method if the ideal is zero-dimensional and over a finite field or the rational field, and the Walk method otherwise.

The following parameters affect the direct algorithms:

     Faugere: BoolElt                    Default: true

     HomogeneousWeights: BoolElt         Default: true

     Homogenize: BoolElt                 Default: true

     DegreeStart: RngIntElt              Default: true

If the parameter Faugere is set to true, then the Faugère F₄ algorithm will be used (if the field is a finite field or the rational field); otherwise the Buchberger algorithm is used.

The current implementation of the Faugère algorithm is usually very much faster than the Buchberger algorithm and usually does not take much more memory, so that it is why it is now selected by default. However, there may be examples for which it may be more desirable to use the Buchberger algorithm (particularly to save some memory). [If you encounter an example where the Faugère algorithm is significantly slower than the Buchberger algorithm, then please mail it to us (magma@maths.usyd.edu.au)!]

Since V2.12 (July 2005), if the input basis is not homogeneous, then Magma first attempts to find a weight vector W with respect to which the ideal is homogeneous; if such a W is found, then the "easy" order used internally for the direct algorithm (accessed by EasyIdeal) is taken to be the grevlexw order with respect to W (see subsection Graded Reverse Lexicographical (Weighted): grev-lexw), since the GB is likely to be smaller with respect to this order. The selection of such an order may be suppressed by setting the parameter HomogeneousWeights to {false}.

If no appropriate grevlexw order is used, then setting Homogenization to true specifies that the ideal should first be homogenized: a GB of the homogenization of the ideal is computed and then the homogenization variable is removed and the final basis reduced. This parameter has the default value of true over the rational field and false over all other fields, since most computations are improved by these defaults.

If the parameter DegreeStart is set to an integer d, then any S-polynomial pairs of degree less than d will be ignored.

The following parameters affect the Faugère F₄ algorithm:

     AllPairs: BoolElt                   Default: false

     PairsLimit: BoolElt                 Default: 0

     ReversePairs: BoolElt               Default: false

     HFE: BoolElt                        Default: false

     Boolean: BoolElt                    Default: false

By default, the Faugère F₄ algorithm includes all pairs of the next degree at each step (see [Fau99, Sec.2.5]), since this usually produces the best performance. However, setting the parameter AllPairs to true will cause the algorithm to include all pairs currently in the queue at each new step; this generally makes the matrix larger and is usually less efficient, but for some inputs (e.g., inhomogeneous ideals where there are only a small number of pairs for each degree at each step) this option may yield a significant improvement.

Alternatively, setting the parameter PairsLimit to a positive integer n will cause the algorithm to include at most n pairs from the queue at each step; this will usually make the matrix smaller, thus saving memory, but will often also make the running time longer. Setting also the parameter ReversePairs to {true} will reverse the list of pairs of the current degree from which the restricted set of pairs is taken: this may help a lot for certain types of input, since this may lead to new polynomials of lower degree being found more quickly. (If there is no pairs limit, then the value of ReversePairs is irrelevant since all pairs of the current degree are taken at each step.)

If the input basis is an HFE system over GF(2) such that the secret degree d is less than or equal to 127, then one should set the HFE parameter to {true}. In this case, Magma can apply various optimizations which save memory and time (only pairs of degree of most 4 are considered, as this is sufficient for systems for which d≤127).

The following parameters affect the Buchberger algorithm:

     ReduceInitial: BoolElt              Default: true

     RemoveRedundant: BoolElt            Default: true

     ReduceByNew: BoolElt                Default: true

Setting ReduceInitial to true specifies that the basis of the ideal should be first reduced (see the function Reduce) before any S-polynomial pairs are considered. Setting RemoveRedundant to true specifies that redundant polynomials in the input (which reduce to zero with respect to the other polynomials) should first be removed. Setting ReduceByNew to true specifies that when a new polynomial f is inserted into the current GB being constructed, the current basis should be reduced by f (thus the basis stays close to being fully reduced throughout the algorithm).

Each of these control parameters usually have the default values of true (it depends on the coefficient ring).

The following parameters affect the Walk algorithm:

     SigmaEpsilon: FldRatElt             Default: 1/2

     TauEpsilon: FldRatElt               Default: 1/n

     SigmaVectors: RngIntElt             Default: n

     TauVectors: RngIntElt               Default: ⌈n/2 ⌉

The parameters SigmaEpsilon and TauEpsilon control the factor εwhich is used in the Walk algorithm to perturb the initial weight vector σand the final weight vector τrespectively. The parameters SigmaVectors and TauVectors determine how many weight vectors of the initial and final orders are used to perturb the initial weight vector σand the final weight vector τrespectively. By default, the εfactor and number of weight vectors for σare determined dynamically to be "optimal", while the εfactor for τis taken to be 1/n and the number of weight vectors for τis taken to be ⌈n/2 ⌉, where n is the rank of I.

GroebnerBasis(I: parameters) : RngMPol -> RngMPolElt

Given an ideal I, force the Gröbner basis of I to be computed, and then return that. The parameters are the same as those for the procedure Groebner.

See also the function GroebnerBasis(S,d) below, which creates a truncated degree-d Gröbner basis.

GroebnerBasis(S: parameters) : [ RngMPolElt ] -> [ RngMPolElt ]

GroebnerBasis(S: parameters) : { RngMPolElt } -> [ RngMPolElt ]

Given a set or sequence S of polynomials, return the unique Gröbner basis of the ideal generated by S as a sorted sequence. This function is useful for computing Gröbner bases without the need to construct ideals. The parameters are the same as those for the procedure Groebner.

See also the function GroebnerBasis(S,d) below, which creates a truncated degree-d Gröbner basis.

GroebnerBasisUnreduced(S: parameters) : [ RngMPolElt ] -> [ RngMPolElt ]

GroebnerBasisUnreduced(S: parameters) : { RngMPolElt } -> [ RngMPolElt ]

    Homogenize: BoolElt                 Default: true

    ReduceInitial: BoolElt              Default: true

    ReduceByNew: BoolElt                Default: true

Given a set or sequence S of polynomials, return an unreduced Gröbner basis of the ideal generated by S as a sorted sequence. This function is useful for computing Gröbner bases without the need to construct ideals and when the reduction of the Gröbner basis is very expensive. The parameters behave the same as for the procedure Groebner.

GroebnerBasis(S, d: parameters) : [ RngMPol ], RngInt -> RngMPolElt

Given a set or sequence S of polynomials, return the degree-d Gröbner basis of the ideal generated by S, which is the truncated Gröbner basis obtained by ignoring S-polynomial pairs whose total degree is greater than d.

If the ideal is homogeneous, then it is guaranteed that the result is equal to the set of all polynomials in the full Gröbner basis of the ideal whose total degree is less than or equal to d, and a polynomial whose total degree is less than or equal to d is in the ideal iff its normal form with respect to this truncated basis is zero. But if the ideal is not homogeneous, these last properties may not hold, but it may be still useful to construct the truncated basis.

The parameters are the same as those for the procedure Groebner. See the section on graded polynomial rings below for an example. See also [BW93, section 10.2], for further discussion.

Related Functions

The following functions and procedures perform operations related to Gröbner bases.

HasGroebnerBasis(I) : RngMPol -> BoolElt

Given an ideal I, return whether the Gröbner basis of I can be computed. This depends on the type of base ring of I: the base ring must currently be a field or a Euclidean ring.

EasyIdeal(I) : RngMPol -> RngMPol

Given an ideal I, return the ideal E which is mathematically equal to I but whose basis is the Gröbner basis of I with respect to an "easy" order, together with an isomorphism f from I onto E. The easy order is usually the grevlex order or grevlexw order with suitable weights, and the easy basis (the Gröbner basis of the easy ideal) of I is used extensively by Magma in many of its internal algorithms; this function allows one to access this "easy" Gröbner basis directly.

EasyBasis(I) : RngMPol -> [ RngMPolElt ]

Given an ideal I, return the Gröebner basis of the easy ideal of I.

SmallBasis(I) : RngMPol -> [ RngMPolElt ]

Given an ideal I, return the basis of I with shortest length which is currently known. This may be the original basis with which I was constructed, or a Gröbner basis, but the result is always has the the same monomial order as the main monomial order of I.

MarkGroebner(I) : RngMPol ->

(Procedure.) Given an ideal I, mark the current basis of I to be the Gröbner basis of the ideal w.r.t. the monomial order of the ideal. Note that the current basis must exactly equal the unique (reverse) sorted minimal reduced Gröbner basis for the ideal, as returned by the function GroebnerBasis. This procedure is useful when one creates an ideal with a basis known to be the Gröbner basis of the ideal from a previous computation or for other reasons. If the basis is not the unique Gröbner basis, the results are unpredictable.

IsGroebner(S) : { RngMPolElt } -> BoolElt

IsGroebner(S) : [ RngMPolElt ] -> BoolElt

Given a set or sequence S of polynomials describing a basis of an ideal, return whether the basis is itself a (not necessarily minimal or reduced) Gröbner basis of the ideal.

Coordinates(I, f) : RngMPol, RngMPolElt -> [ RngMPolElt ]

Given an ideal I of a polynomial ring P, together with a polynomial f in I, and supposing that I has basis b₁, ..., b_k, return a sequence [g₁, ..., g_k] of elements of P so that f = g₁ * b₁ + ... + g_k * b_k. If I was created by IdealWithFixedBasis(B), then the fixed basis B is used as the basis b₁, ..., b_k; otherwise the (unique) Gröbner basis of I is used as the basis b₁, ..., b_k. The resulting sequence is not necessarily unique.

CoordinateMatrix(I) : RngMPol -> Matrix

Given an ideal I such that I has a fixed basis (i.e., such that I was created via the function IdealWithFixedBasis), return the coordinate matrix C of I. The i-th row of C gives the coordinates of the i-th element of the Gröebner basis of I w.r.t. the fixed basis of I. The Gröebner basis of I is first computed if it has not been already.

Reduce(S) : [ RngMPolElt ] -> [ RngMPolElt ]

Reduce(S) : { RngMPolElt } -> [ RngMPolElt ]

Given a set or sequence S of polynomials, return the sequence consisting of the reduction of S. The reduction is obtained by reducing to normal form each element of S with respect to the other elements and sorting the resulting non-zero elements left. Note that all Gröbner bases returned by Magma are automatically reduced so that this function would usually only be used just to simplify a set or sequence of polynomials which is not a Gröbner basis.

ReduceGroebnerBasis(S) : [ RngMPolElt ] -> [ RngMPolElt ]

ReduceGroebnerBasis(S) : { RngMPolElt } -> [ RngMPolElt ]

Given a set or sequence S of polynomials which is assumed to be a (not necessarily minimal or reduced) Gröbner basis for an ideal, return the sequence consisting of the reduction of S. The reduction is obtained by first removing each redundant polynomial whose leading term is a multiple of another leading term and then reducing the remaining polynomials as in the function Reduce. This function would usually only be used to reduce a set or sequence of polynomials which is known to be a non-reduced Gröbner basis (created in some way other than by one of Magma's internal Gröbner basis construction algorithms).

Gröbner Bases of Boolean Polynomial Rings

Since V2.15, a special type of polynomial ring is available: the boolean polynomial ring in n variables. Such a ring is a multivariate polynomial ring defined over GF(2) but such that all monomials are reduced modulo the field relations x_i² = x_i for each i (so a bit vector representation can be used for monomials). Technically, the ring is thus the quotient algebra GF(2)[x₁, ..., x_n] / < x₁² + x₁, ..., x_n² + x_n >.

Besides the basic creation and access functions for elements and ideals of such a ring, the main interest is to compute and examine a Gröbner basis of an ideal. Since the field relations are always present, an ideal represents a zero-dimensional system of multivariate polynomial equations over GF(2) with the solution components always lying in GF(2); these are particularly of interest for algebraic attacks on cryptosystems. Otherwise, there are not many other operations applicable to such rings and their elements.

Note that if one creates an ideal I of GF(2)[x₁, ..., x_n] such that the basis of I includes the field polynomials (x_i² + x_i for each i), then Magma automatically uses the boolean polynomial ring representation internally, so this is basically equivalent to using the boolean polynomial ring type, except that Magma will have to move back to the original ring GF(2)[x₁, ..., x_n] at the end, and this may take much more time and memory. So it is preferable to use the boolean polynomial ring from the outset if one wishes to create the Gröbner basis of such an ideal and examine it (particularly if it does not collapse down to a sequence of linear polynomials).

See example H98E5 below for simple uses of boolean polynomial rings.

BooleanPolynomialRing(n) : RngIntElt -> RngMPolBool

Create the boolean polynomial ring with n variables (whose coefficients lie in GF(2)). The default monomial order chosen is the lexicographical (lex) order.

BooleanPolynomialRing(n, order) : RngIntElt, MonStgElt -> RngMPolBool

Create the boolean polynomial ring with n variables (whose coefficients lie in GF(2)) and with the given order {order} on the monomials. Currently, {order} must be one of the following strings: "lex", "grevlex", "glex".

BooleanPolynomialRing(B, Q) : RngMPolBool, [RngIntElt] -> RngMPolBoolElt

Given a boolean polynomial ring B of rank n and a sequence Q of integers, create the boolean polynomial in B whose monomials are given by the entries of Q: each integer must be in the range [0 ... 2ⁿ - 1] and its binary expansion gives the exponents of the monomial in order (the resulting monomials are sorted w.r.t. the monomial order of B, so may be given in any order and duplicate monomials are added).

This function is simply provided so that boolean polynomials may be stored and read back in a compact form; otherwise, one can create a boolean polynomial in the usual way from the generators of B after B is created. Note also that if one prints B, an ideal of B, or an element of B with the Magma print level, then this function will be used to print the elements in a compact form.

Verbosity

This subsection describes the verbose flags available for the Gröbner basis algorithms. There are separate verbose flags for each algorithm (Buchberger, etc.), but the all-encompassing verbose flag Groebner includes all these flags implicitly.

For each procedure provided for setting one of these flags, the value {false} is equivalent to level 0 (nothing), and {true} is equivalent to level 1 (minimal verbosity). For each Set- procedure, there is also a corresponding Get- function to return the value of the corresponding flag.

SetVerbose("Groebner", v) : MonStgElt, RngIntElt ->

(Procedure.) Change the verbose printing level for all Gröbner basis algorithms to be v. This includes all of the algorithms whose verbosity is controlled by flags subsequently listed, as well as some other minor related algorithms. Currently the legal levels are 0, 1, 2, 3, or 4. One would normally set this flag to 1 for minimal verbosity for Gröbner basis-type computations, and possibly also set one or more of the following flags to levels higher than 1 for more verbosity.

SetVerbose("Buchberger", v) : MonStgElt, RngIntElt ->

(Procedure.) Change the verbose printing level for the Buchberger algorithm to be v. Currently the legal levels are 0, 1, 2, 3, or 4. If the value w of the Groebner verbose flag is greater than v, then w is taken to be the current value of this flag.

SetVerbose("Faugere", v) : MonStgElt, RngIntElt ->

(Procedure.) Change the verbose printing level for the Faugère algorithm to be v. Currently the legal levels are 0, 1, 2, or 3. If the value w of the Groebner verbose flag is greater than v, then w is taken to be the current value of this flag.

SetVerbose("FGLM", v) : MonStgElt, RngIntElt ->

(Procedure.) Change the verbose printing level for the FGLM order change algorithm to be v. Currently the legal levels are 0, 1, 2, or 3. If the value w of the Groebner verbose flag is greater than v, then w is taken to be the current value of this flag.

SetVerbose("GroebnerWalk", v) : MonStgElt, RngIntElt ->

(Procedure.) Change verbose printing for the Gröbner Walk order change algorithm to be v. Currently the legal levels are 0, 1, 2, or 3. If the value w of the Groebner verbose flag is greater than v, then w is taken to be the current value of this flag.

Example GB_Cyclic6 (H98E3)

> Q := RationalField();
> P<x, y, z, t, u, v> := PolynomialRing(Q, 6);
> I := ideal<P |
>     x + y + z + t + u + v,
>     x*y + y*z + z*t + t*u + u*v + v*x,
>     x*y*z + y*z*t + z*t*u + t*u*v + u*v*x + v*x*y,
>     x*y*z*t + y*z*t*u + z*t*u*v + t*u*v*x + u*v*x*y + v*x*y*z,
>     x*y*z*t*u + y*z*t*u*v + z*t*u*v*x + t*u*v*x*y + u*v*x*y*z + v*x*y*z*t,
>     x*y*z*t*u*v - 1>;
> time B := GroebnerBasis(I);
Time: 1.140
> #B;
17
> B[17];
v^48 - 2554*v^42 - 399710*v^36 - 499722*v^30 + 499722*v^18 + 399710*v^12 + 
    2554*v^6 - 1
> time Factorization(B[17]);
[
    <v - 1, 1>,
    <v + 1, 1>,
    <v^2 + 1, 1>,
    <v^2 - 4*v + 1, 1>,
    <v^2 - v + 1, 1>,
    <v^2 + v + 1, 1>,
    <v^2 + 4*v + 1, 1>,
    <v^4 - v^2 + 1, 1>,
    <v^4 - 4*v^3 + 15*v^2 - 4*v + 1, 1>,
    <v^4 + 4*v^3 + 15*v^2 + 4*v + 1, 1>,
    <v^8 + 4*v^6 - 6*v^4 + 4*v^2 + 1, 1>,
    <v^8 - 6*v^7 + 16*v^6 - 24*v^5 + 27*v^4 - 24*v^3 +
        16*v^2 - 6*v + 1, 1>,
    <v^8 + 6*v^7 + 16*v^6 + 24*v^5 + 27*v^4 + 24*v^3 +
        16*v^2 + 6*v + 1, 1>
]
Time: 0.060

Example GB_RungeKutta2 (H98E4)

> K<c2, c3> := FunctionField(IntegerRing(), 2);
> P<c4, b4, b3, b2, b1, a21, a31, a32, a41, a42, a43> := PolynomialRing(K, 11);
> I := ideal<P |
>    b1 + b2 + b3 + b4 - 1,
>    b2*c2 + b3*c3 + b4*c4 - 1/2,
>    b2*c2^2 + b3*c3^2 + b4*c4^2 - 1/3,
>    b3*a32*c2 + b4*a42*c2 + b4*a43*c3 - 1/6,
>    b2*c2^3 + b3*c3^3 + b4*c4^3 - 1/4,
>    b3*c3*a32*c2 + b4*c4*a42*c2 + b4*c4*a43*c3 - 1/8,
>    b3*a32*c2^2 + b4*a42*c2^2 + b4*a43*c3^2 - 1/12,
>    b4*a43*a32*c2 - 1/24,
>    c2 - a21,
>    c3 - a31 - a32,
>    c4 - a41 - a42 - a43>;
> time Groebner(I);
Time: 0.110
> I;
Ideal of Polynomial ring of rank 11 over Multivariate rational function field
    of rank 2 over Integer Ring
Order: Lexicographical
Variables: c4, b4, b3, b2, b1, a21, a31, a32, a41, a42, a43
Inhomogeneous, Dimension 0
Groebner basis:
[
    c4 - 1,
    b4 + (-6*c2*c3 + 4*c2 + 4*c3 - 3)/(12*c2*c3 - 12*c2 - 12*c3 + 12),
    b3 + (2*c2 - 1)/(12*c2*c3^2 - 12*c2*c3 - 12*c3^3 + 12*c3^2),
    b2 + (-2*c3 + 1)/(12*c2^3 - 12*c2^2*c3 - 12*c2^2 + 12*c2*c3),
    b1 + (-6*c2*c3 + 2*c2 + 2*c3 - 1)/(12*c2*c3),
    a21 - c2,
    a31 + (-4*c2^2*c3 + 3*c2*c3 - c3^2)/(4*c2^2 - 2*c2),
    a32 + (-c2*c3 + c3^2)/(4*c2^2 - 2*c2),
    a41 + (-12*c2^2*c3^2 + 12*c2^2*c3 - 4*c2^2 + 12*c2*c3^2 - 15*c2*c3 + 6*c2 - 
        4*c3^2 + 5*c3 - 2)/(12*c2^2*c3^2 - 8*c2^2*c3 - 8*c2*c3^2 + 6*c2*c3),
    a42 + (-c2^2 + 4*c2*c3^2 - 5*c2*c3 + 3*c2 - 4*c3^2 + 5*c3 - 2)/(12*c2^3*c3 -
        8*c2^3 - 12*c2^2*c3^2 + 6*c2^2 + 8*c2*c3^2 - 6*c2*c3),
    a43 + (-2*c2^2*c3 + 2*c2^2 + 3*c2*c3 - 3*c2 - c3 + 1)/(6*c2^2*c3^2 - 
        4*c2^2*c3 - 6*c2*c3^3 + 3*c2*c3 + 4*c3^3 - 3*c3^2)
]

Example GB_SolveOverGF2 (H98E5)

We construct a sequence B of 4 polynomials in 5 variables, and note that the Gröbner basis of B contains monomials having degrees greater than 1.

> P<a,b,c,d,e> := PolynomialRing(GF(2), 5);
> B := [a*b + c*d + 1, a*c*e + d*e, a*b*e + c*e, b*c + c*d*e + 1];
> GroebnerBasis(B);
[
    a + c^2*d + c + d^2*e,
    b*c + d^3*e^2 + d^3*e + d^2*e^2 + d*e + e + 1,
    b*e + d*e^2 + d*e + e,
    c*e + d^3*e^2 + d^3*e + d^2*e^2 + d*e,
    d^4*e^2 + d^4*e + d^3*e + d^2*e^2 + d^2*e + d*e + e
]

> L := [P.i^2 + P.i: i in [1 .. Rank(P)]];
> BB := B cat L;
> BB;
[
    a*b + c*d + 1,
    a*c*e + d*e,
    a*b*e + c*e,
    b*c + c*d*e + 1,
    a^2 + a,
    b^2 + b,
    c^2 + c,
    d^2 + d,
    e^2 + e
]
> GroebnerBasis(BB);
[
    a + d + 1,
    b + 1,
    c + 1,
    d^2 + d,
    e
]
> I := ideal<P|BB>;             
> Variety(I);
[ <0, 1, 1, 1, 0>, <1, 1, 1, 0, 0> ]

> P<a,b,c,d,e> := BooleanPolynomialRing(5, "grevlex");
> B := [a*b + c*d + 1, a*c*e + d*e, a*b*e + c*e, b*c + c*d*e + 1];
> I := Ideal(B);
> I;
Ideal of Boolean polynomial ring of rank 5 over GF(2)
Order: Graded Reverse Lexicographical (bit vector word)
Variables: a, b, c, d, e
Basis:
[
    a*b + c*d + 1,
    a*c*e + d*e,
    a*b*e + c*e,
    c*d*e + b*c + 1
]
> GroebnerBasis(I);
[
    a + d + 1,
    b + 1,
    c + 1,
    e
]
> Variety(I);
[ <0, 1, 1, 1, 0>, <1, 1, 1, 0, 0> ]

> R<[x]> := BooleanPolynomialRing(10, "grevlex");
> R;
Boolean polynomial ring of rank 10 over GF(2)
Order: Graded Reverse Lexicographical (bit vector word)
Variables: x[1], x[2], x[3], x[4], x[5], x[6], x[7], x[8], x[9], x[10]
> f := x[2]*x[3]*x[5]*x[7] + x[2]*x[4]*x[5]*x[8] + x[3]*x[4]*x[5]*x[9] + 
>    x[3]*x[6]*x[7]*x[9] + x[2]*x[3]*x[5] + x[2]*x[4]*x[5] + x[2]*x[3]*x[7] +
>    x[2]*x[5]*x[7] + x[3]*x[5]*x[7] + x[3]*x[6]*x[7] + x[2]*x[4]*x[8] + 
>    x[2]*x[5]*x[8] + x[4]*x[5]*x[8] + x[3]*x[6]*x[9] + x[3]*x[7]*x[9] + 
>    x[6]*x[7]*x[9] + x[2]*x[3] + x[2]*x[4] + x[3]*x[5] + x[4]*x[5] + 
>    x[3]*x[6] + x[2]*x[7] + x[5]*x[7] + x[6]*x[7] + x[2]*x[8] + x[4]*x[8] + 
>    x[5]*x[8] + x[3]*x[9] + x[6]*x[9] + x[7]*x[9] + x[1]*x[10] + x[1] + x[4]
>    + x[6] + x[8] + x[9] + x[10];
> I := Ideal([f]);
> G := GroebnerBasis(I);
> #G;
38
> [Length(f): f in G];
[ 188, 50, 80, 82, 26, 22, 20, 26, 20, 20, 26, 32, 8, 8, 8, 8, 32, 32, 8, 8, 8, 
8, 8, 8, 8, 8, 8, 32, 8, 8, 8, 8, 40, 5, 8, 8, 8, 8 ]
> G[38];
x[1]*x[4]*x[7]*x[10] + x[1]*x[5]*x[7]*x[10] + x[1]*x[4]*x[7] + x[1]*x[5]*x[7] + 
    x[4]*x[7]*x[10] + x[5]*x[7]*x[10] + x[4]*x[7] + x[5]*x[7]

Example GB_GBoverZ (H98E6)

> P<x, y, z> := PolynomialRing(IntegerRing(), 3);
> I := ideal<P| x^2 - 1, y^2 - 1, 2*x*y - z>;
> GroebnerBasis(I);
[
    x^2 - 1,
    x*z - 2*y,
    2*x - y*z,
    y^2 - 1,
    z^2 - 4
]

When we compute normal forms modulo I, x is clearly not reducible by any polynomial, while 2x can be reduced by the 2x - yz polynomial.

> NormalForm(x, I);  
x
> NormalForm(2*x, I);
y*z

> NormalForm(-x, I); 
x - y*z

> GroebnerBasis(ChangeRing(I, GF(2)));
[
    x^2 + 1,
    y^2 + 1,
    z
]
> GroebnerBasis(ChangeRing(I, GF(3)));
[
    x + y*z,
    y^2 + 2,
    z^2 + 2
]

> GroebnerBasis(ChangeRing(I, IntegerRing(4)));
[
    x^2 + 3,
    x*z + 2*y,
    2*x + y*z,
    y^2 + 3,
    z^2,
    2*z
]

Example GB_FindingPrimes (H98E7)

We first form a certain ideal I in Z[x, y, z], and note that the Gröbner basis of I over Q contains 1, so there are no solutions over Q or an algebraic closure of it (this is not surprising as there are 4 equations in 3 unknowns).

> P<x, y, z> := PolynomialRing(IntegerRing(), 3);
> I := ideal<P | x^2 - 3*y, y^3 - x*y, z^3 - x, x^4 - y*z + 1>;
> GroebnerBasis(ChangeRing(I, RationalField()));
[
    1
]

> GroebnerBasis(I);                               
[
    x + 170269749119,
    y + 2149906854,
    z + 170335012540,
    282687803443
]

> Factorization(282687803443);
[ <101, 1>, <103, 1>, <27173681, 1> ]
> GroebnerBasis(ChangeRing(I, GF(101)));
[
    x + 19,
    y + 48,
    z + 68
]
> GroebnerBasis(ChangeRing(I, GF(103)));
[
    x + 39,
    y + 8,
    z + 85
]
> GroebnerBasis(ChangeRing(I, GF(27173681)));
[
    x + 26637654,
    y + 3186055,
    z + 10380032
]

> GroebnerBasis(ChangeRing(I, GF(3)));
[
    1
]

Example GB_QuadraticOrderGB (H98E8)

Let R = Z[Sqrt( - 5)]. R is the maximal order of Q(Sqrt( - 5)) and is NOT a PIR. We consider the ideal I of R[x, y] generated by f₁ = 2xy + Sqrt( - 5)y and f₂ = (1 + Sqrt( - 5))x² - xy. To work over R, we simply compute over Z, introduce a new variable S to represent Sqrt( - 5), make sure that S is less than both x and y in the monomial order, and include the polynomial (S² + 5) in the ideal I. We then print out the Gröbner basis of I.

> P<x, y, S> := PolynomialRing(IntegerRing(), 3);
> f1 := 2*x*y + S*y;          
> f2 := (1 + S)*x^2 - x*y;
> I := ideal<P | f1, f2, S^2 + 5>;
> GroebnerBasis(I);
[
    x^2*S + x^2 + 5*y^3 + 13*y*S - 25*y,
    6*x^2 + 5*y^2 + 3*y*S - 10*y,
    x*y + 5*y^3 + 13*y*S - 25*y,
    y^2*S + 5*y^2 - 15*y,
    10*y^2 + 5*y*S - 25*y,
    S^2 + 5
]

> f5 := (5 + S)*y^2 - 15*y;
> f7 := -2*S*y^2 + (5 + 5*S)*y;
> f9 := x*y + S*y^3 - 5*S*y^2 + 8*S*y;
> J := ideal<P |  f2, f5, f7, f9, S^2 + 5>;
> I eq J;
true
> GroebnerBasis(I) eq GroebnerBasis(J);
true

> Coordinates(I, f5);
[
    0, 0, 0, 1, 0, 0
]
> Coordinates(I, f7);
[
    0, 0, 0, -2, 1, 0
]
> Coordinates(I, f9);
[
    0, 0, 1, y, -y - 1, 0
]

> Q := [f2, f5, f7, f9, S^2 + 5];         
> J := IdealWithFixedBasis(Q);                        
> J eq I;
true
> g := GroebnerBasis(I)[2];
> g;
6*x^2 + 5*y^2 + 3*y*S - 10*y
> C := Coordinates(J, g);
> C;
[
    -S + 1,
    -5*y + 1,
    -x - y^2*S + 7*y*S - 2*y - 7*S - 2,
    -2*y*S + 4*S + 6,
    x^2 + 5*y^3 - 13*y^2 + 3*y
]

> &+[C[i]*Q[i]: i in [1 .. #C]] eq g;
true

Most importantly of all, the fact that we have done all this by defining things over Z with the extra variable S has been no less powerful: we can still do full membership testing, normal forms, coordinate computations, etc. with this representation. Also, see below for an elimination computation which continues this example.

Gröbner bases over very many other general rings can be effectively handled in just the same way as that presented in this example! For example, if we need α= (1 + Sqrt(5))/2, we can introduce a variable new A and the polynomial (2A - 1)² - 5.

Example GB_Coordinates (H98E9)

> P<x, y> := PolynomialRing(RationalField(), 2);
> S := [x^2 - y, x^3 + y^2, x*y^3 - 1];       
> I := IdealWithFixedBasis(S);                              
> 1 in I;
true
> C := Coordinates(I, P!1);
> C;
[
    -1/2*x^2*y^3 - 1/2*x^2*y^2 + 1/2*x^2*y + 1/2*x^2 + 1/2*x*y^3 +
        1/2*x*y^2 - 1/2*x*y - 1/2*y^4 - 1/2*y^3 + 1/2*y^2 + 1/2*y,
    1/2*x*y^3 + 1/2*x*y^2 - 1/2*x*y - 1/2*x - 1/2*y^3 - 1/2*y^2 + 1/2*y,
    -1/2*y^2 + 1
]

> C[1]*S[1] + C[2]*S[2] + C[3]*S[3];
1

> P<x, y> := PolynomialRing(IntegerRing(), 2);
> S := [x^2 - y, x^3 + y^2, x*y^3 - 1];       
> I := IdealWithFixedBasis(S);                              
> 1 in I;
false
> GroebnerBasis(I);
[
    x + 1,
    y + 1,
    2
]

> C := Coordinates(I, P!2);
> C;
[
    x^2*y^2 - x^2*y - x^2 - x*y^2 + x*y + x + y^4 + y^3 - y^2 - y - 1,
    -x*y^2 + x*y + x + y^3 + y^2 - y - 1,
    -x^2 - x*y + y - 2
]

> C[1]*S[1] + C[2]*S[2] + C[3]*S[3];
2

Example GB_ValuationRing (H98E10)

We construct an ideal I of the polynomial ring P = Q[x, y] with a specific fixed basis S, determine that I is the full polynomial ring P, and then find coordinates of the polynomial 1 of P with respect to S. Note that we use the function IdealWithFixedBasis to construct the ideal so that the fixed basis will be remembered.

> P<x, y> := PolynomialRing(RationalField(), 2);
> S := [x^2 - y, x^3 + y^2, x*y^3 - 1];       
> I := IdealWithFixedBasis(S);                              
> 1 in I;
true
> C := Coordinates(I, P!1);
> C;
[
    -1/2*x^2*y^3 - 1/2*x^2*y^2 + 1/2*x^2*y + 1/2*x^2 + 1/2*x*y^3 +
        1/2*x*y^2 - 1/2*x*y - 1/2*y^4 - 1/2*y^3 + 1/2*y^2 + 1/2*y,
    1/2*x*y^3 + 1/2*x*y^2 - 1/2*x*y - 1/2*x - 1/2*y^3 - 1/2*y^2 + 1/2*y,
    -1/2*y^2 + 1
]

> C[1]*S[1] + C[2]*S[2] + C[3]*S[3];
1

> P<x, y> := PolynomialRing(IntegerRing(), 2);
> S := [x^2 - y, x^3 + y^2, x*y^3 - 1];       
> I := IdealWithFixedBasis(S);                              
> 1 in I;
false
> GroebnerBasis(I);
[
    x + 1,
    y + 1,
    2
]

> C := Coordinates(I, P!2);
> C;
[
    x^2*y^2 - x^2*y - x^2 - x*y^2 + x*y + x + y^4 + y^3 - y^2 - y - 1,
    -x*y^2 + x*y + x + y^3 + y^2 - y - 1,
    -x^2 - x*y + y - 2
]

> C[1]*S[1] + C[2]*S[2] + C[3]*S[3];
2

Degree-d Gröbner Bases

GroebnerBasis(S, d : parameters) : [ RngMPolElt ], RngInt -> RngMPolElt

Given a set or sequence S of polynomials from a graded polynomial ring P, return the weighted degree-d Gröbner basis of the ideal generated by S, which is the truncated Gröbner basis obtained by ignoring S-polynomial pairs whose weighted degree (with respect to the grading on P) is greater than d.

If the ideal is homogeneous, then it is guaranteed that the result is equal to the set of all polynomials in the full Gröbner basis of the ideal whose weighted degree is less than or equal to d, and a polynomial whose weighted degree is less than or equal to d is in the ideal iff its normal form with respect to this truncated basis is zero. But if the ideal is not homogeneous, these last properties may not hold, but it may be still useful to construct the truncated basis.

The parameters are the same as those for the procedure Groebner. See also [BW93, section 10.2] for further discussion. Note that the base ring may be a field or Euclidean ring.

Example GB_Degree-d (H98E11)

> P<a,b,c,d> := PolynomialRing(RationalField(), [4,3,2,1]);
> L := [a*b - c^2*d^3, b*c*d + c^3, c^2*d - d^5, a*d - b*c];
> [IsHomogeneous(f): f in L];
[ true, true, true, true ]
> [Degree(f): f in L];
[ 7, 6, 5, 5 ]
> G:=GroebnerBasis(L);
> G;
[
    a*b - d^7,
    a*c^3 + d^10,
    a*d - b*c,
    b^2*c - d^8,
    b*c^3 + d^9,
    b*c*d + c^3,
    b*d^5 + c^4,
    c^5 - d^10,
    c^2*d - d^5,
    c*d^7 - d^9
]
> #G;
10
> [Degree(f): f in G];
[ 7, 10, 5, 8, 9, 6, 8, 10, 5, 9 ]
> for D := 1 to 10 do
>     T := GroebnerBasis(L, D);
>     printf "D = %o, #GB = %o, contains all degree-D polynomials: %o\n",
>         D, #T, {f: f in G | Degree(f) le D} subset T;
> end for;
D = 1, #GB = 4, contains all degree-D polynomials: true
D = 2, #GB = 4, contains all degree-D polynomials: true
D = 3, #GB = 4, contains all degree-D polynomials: true
D = 4, #GB = 4, contains all degree-D polynomials: true
D = 5, #GB = 4, contains all degree-D polynomials: true
D = 6, #GB = 4, contains all degree-D polynomials: true
D = 7, #GB = 4, contains all degree-D polynomials: true
D = 8, #GB = 6, contains all degree-D polynomials: true
D = 9, #GB = 8, contains all degree-D polynomials: true
D = 10, #GB = 10, contains all degree-D polynomials: true
> GroebnerBasis(L, 5);
[
    a*b - d^7,
    a*d - b*c,
    b*c*d + c^3,
    c^2*d - d^5
]
> GroebnerBasis(L, 8);
[
    a*b - d^7,
    a*d - b*c,
    b^2*c - d^8,
    b*c*d + c^3,
    b*d^5 + c^4,
    c^2*d - d^5
]