• « Previous
• Up
• Contents
• Index
• Search
• Next »

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.

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.

Let I be an ideal of a polynomial ring defined over a field, and choose a fixed monomial ordering on the ring. A finite subset G of I - {0} is called a Gröbner basis for I if, for every nonzero f ∈I, there exists g∈G such that the leading monomial of g divides the leading monomial of f. Every Gröbner basis for I is a set of generators of I [AL94, Cor. 1.6.3]. A Gröbner 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).

For a given fixed monomial ordering, every nonzero ideal of a polynomial ring over a field possesses a unique reduced Gröbner basis [AL94, Thm. 1.8.7]. This unique Gröbner basis (with respect to the order defined by the user) is the Gröbner basis computed by Magma, and is represented by Magma as a sequence of polynomials sorted by the monomial ordering (with decreasing order). This sorting is unique because any two polynomials in a reduced Gröbner basis have distinct leading monomials. This Gröbner basis 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 when the Gröbner basis is computed, the original basis will be discarded and will be replaced by the unique Gröbner basis. 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 discrete valuation rings. All of these have a Euclidean division algorithm with unique quotient/remainder output.

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, 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.

Just as for fields, every ideal of a polynomial ring over a Euclidean ring possesses a unique reduced Gröbner basis (with respect to some fixed monomial ordering), which can be proved by adapting the proof over fields. This unique Gröbner basis (with respect to the order defined by the user) is the Gröbner basis computed by Magma, and is represented by Magma as a sequence of polynomials sorted by the monomial ordering (with decreasing order). This sorting is unique because any two polynomials in a reduced Gröbner basis have distinct leading monomials. This Gröbner basis 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 when the Gröbner basis is computed, the original basis will be discarded and will be replaced by the unique Gröbner basis.

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 some 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 H112E5 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

     Dense: BoolElt                      Default:

     HomogeneousWeights: BoolElt         Default: true

     Homogenize: BoolElt                 Default: true

     DegreeStart: RngIntElt              Default: true

     GlobalModular: BoolElt              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).

Since V2.20, the Dense parameter controls the dense variant of F₄; see the next subsection.

Since V2.12, 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): grevlexw), 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.

Since V2.22 (May 2016), when computing the GB of an ideal I defined over K=Q or an algebraic number field K=Q(α), Magma by default uses a Monte-Carlo `global modular' algorithm where the complete GB of I is computed modulo successive primes and the GB of I over K is reconstructed from these modular GBs. The probability of incorrectness for this new algorithm is of the order of 1 in 10<sup>28</sup>. This algorithm can be also turned off by setting the parameter GlobalModular to {false}, so that the computation will revert to using the previous `step by step' modular F₄ algorithm where there is only one full GB computation and the GB polynomials are constructed over K in each matrix step (see also SetGBGlobalModular below, which has the same effect).

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

     DynamicStrategy: BoolElt            Default: false

     Nthreads: RngIntElt                 Default: 1

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).

Since V2.18, if the base ring is the finite field GF(p), where p is a prime with 2<p<2^23.5, then a multi-threaded version of the algorithm is available if POSIX threads are enabled in the current Magma version. In this case, setting the parameter Nthreads to a positive integer n will cause the F₄ algorithm to use n threads within the linear algebra phase of each step. One can alternatively use the procedure SetNthreads to set the global number of threads to a value n so that n threads are always used by default in this algorithm (unless overridden by the Nthreads parameter).

If the parameter DynamicStrategy is set to {true} and the algorithm is running in the dense mode only, then a strategy is used to try to speed up the computation for certain inputs in the case that when a step with a pairs limit has non-trivial reduction to zero, then most or all the remaining pairs of the current degree will probably reduce to zero.

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 ], [ RngIntElt ]

Given an ideal I, force the Gröbner basis of I to be computed, and then return that as a sorted sequence of polynomials.

The second return value is an integer sequence D which gives the sequence of step degrees encountered in each step of the F₄ algorithm, if that is used to compute the `easy' GB before a conversion (see EasyIdeal) or in a direct GB computation (without order change), when such a use of the algorithm F₄ is non-trivial.

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 ], [ RngIntElt ], []

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

    ReturnDenominators : BoolElt: false Default: 1

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

The second return value is the integer sequence D of F₄ step degrees, just as in the previous function (see above).

The parameters are the same as those for the procedure Groebner, except that there is also the parameter ReturnDenominators: if this is set to {true} and the input basis is defined over Q, then there is third return value S which is an integer sequence containing the denominators which arise in the algorithm (by which coefficients are possibly divided). As a result, for each prime p such that the leading monomials of the GB of the original ideal reduced modulo p do not equal the leading monomials of the GB over Q, it must be that p divides an element of S. Thus the sequence S can be used to determine such `bad primes' for the ideal.

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 G_d 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 thus a polynomial whose total degree is less than or equal to d is in the ideal iff its normal form with respect to the degree-d Gröbner basis G_d 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.

SetGBGlobalModular(f) : BoolElt ->

(Procedure.) Set to f a global flag which controls whether the global modular algorithm should be used when computing Groebner bases over Q or an algebraic number field. This is equivalent to the GlobalModular parameter to the procedure Groebner above, but affects all calls to the internal GB machinery. The related function GetGBGlobalModular gives the current value of the flag.

The Dense Variant of the F₄ algorithm

Since V2.20, Magma includes a new dense variant of the F₄ algorithm. The dense variant is currently only practically applicable to input systems over a finite field where the input polynomials are considered "dense"; that is, if the input polynomials are written as a matrix with columns labelled by the monomials, then the input matrix should be dense. Equivalently: if the field size is q and the set of all monomials occurring in the input has size m, then the number of monomials in each input polynomial should be reasonably close to (1 - 1/q).m.

Dense input systems which are applicable include various cryptographic inputs such as HFE, MQQ and Minrank systems, but systems which do not involve the solving of simultaneous equations are also applicable. (The algorithm does work correctly on sparser input systems but is usually not as efficient as the standard F₄ algorithm for such inputs.)

Some key features of the dense variant of the F₄ algorithm are as follows:

(1)

This variant essentially uses the same matrices as in the standard F₄ algorithm (i.e., uses the same S-polynomials and reductors as usual) but exploits dense portions of the matrices where possible in the linear algebra phase, leading to significant speedups for larger examples.

(2)

There is often also significant savings in memory usage over the standard F₄ algorithm.

(3)

If an NVIDIA GPU is available, then this is also exploited (in a special CUDA-enabled Magma executable), yielding greater speedups for larger examples.

(4)

Finally, there is a new experimental optional heuristic which can be selected for the algorithm when solving systems of equations over GF(2), called the Reduction Heuristic which can give an even greater reduction in time and memory usage for some large examples.

The Reduction Heuristic is a new experimental heuristic which can be selected in the dense variant of F₄ when attempting to solve certain kinds of systems of equations over GF(2) where it is assumed that there is a very small number of solutions, so the Groebner basis will consist of mostly linear polynomials or collapse to {1} when there is no solution. The heuristic attempts to reduce the size of the matrices involved in the linear algebra phase of each F₄ step. When the heuristic is selected, the run may simply fail, but when it succeeds, it often saves significant time and memory usage. The kinds of systems for which the saving in time and memory usage tends to be greatest are those such that in the F₄ steps of maximal degree D, the number of S-polynomials is relatively small compared to the total number of monomials of degree D.

Currently the Reduction Heuristic depends on a manual choice by the user of a numerical parameter M. Thus if B is the sequence of input polynomials, to select the Reduction Heuristic with parameter M, one should currently invoke the algorithm with something like the following:

GroebnerBasis(B, D: ReductionHeuristic := M);

where M is the expected maximal degree reached in the computation.

If M is large enough, then the computation will finish correctly and hopefully in considerably less time than the default algorithm without the heuristic. If M is too small, then the algorithm will fail: a runtime error is usually triggered at the point that the algorithm realizes that M was too small. Also, conceivably the algorithm could fail to discover that M is too small and so a wrong Groebner basis could be returned (thus making the algorithm Monte-Carlo). However: (1) a value of M which is too small is usually detected by Magma (and a runtime error is triggered); (2) the algorithm can actually be considered Las Vegas when solving a typical system known to have at least one solution since potential solutions can be trivially checked at the end (so coupled with checking, the algorithm either finds correct solutions or simply fails).

At the moment, it is impossible to suggest what is a suitable choice for M for any given system. But it is currently recommended in practice that one start with M=500 or 1000, and if there is failure, one should increase M successively by 500 or 1000 and restart from scratch and repeat this until the algorithm succeeds. Note that making M much larger than necessary reduces the effectiveness of the heuristic, so one should not just set M to a very large value.

It may seem inefficient if one has to try several runs with potential failure, but this is often alleviated as follows:

(1)

Since the algorithm often runs much faster with a small value for M (whether it succeeds or not), the total time taken for all runs including the ones which fail may still be significantly less than running without the heuristic selected.

(2)

Each run with the heuristic may use much less memory than the default run without the heuristic would use, so no matter how much time is taken, one will eventually be able to solve systems with the heuristic which are not solvable in the available memory without the heuristic.

(3)

When solving a whole class of systems of the same type, one can determine a suitable M for one system and then use that for all the others. This includes multiple systems arising from evaluating a number of variables in some original system.

{tinyurl.com/DenseF4}

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, [ RngIntElt ]

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" monomial order. This order is automatically chosen by Magma and 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. So this function allows one to access this "easy" Gröbner basis directly.

The second return value is an integer sequence D which gives the sequence of step degrees encountered in each step of the F₄ algorithm, if that is used to compute the `easy' GB, while the third return value is an isomorphism f from I onto E.

EasyBasis(I) : RngMPol -> [ RngMPolElt ]

Given an ideal I, return the Gröbner 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öbner basis of I w.r.t. the fixed basis of I. The Gröbner basis of I is first computed if it has not been already.

NormalForm(f, I) : RngMPolElt, RngMPol -> RngMPolElt

Given a polynomial f from a polynomial ring P, together with an ideal I of P, return the unique normal form of f with respect to (the Gröbner basis of) I. The normal form of f is zero if and only if f is in I.

NormalForm(f, S) : RngMPolElt, [ RngMPolElt ] -> RngMPolElt, [ RngMPolElt ]

Given a polynomial f from a polynomial ring P, together with a set or sequence S of polynomials from P, return a normal form g of f with respect to S. (This is not unique in general. If the normal form of f is zero then f is in the ideal generated by S, but the converse is false in general. In fact, the normal form is unique if and only if S forms a Gröbner basis.) If S is a sequence, one may also assign a second return value C which gives the coordinates of the reduction, so that C[i].S[i] is subtracted from f for each i to yield g.

SPolynomial(f, g) : RngMPolElt, RngMPolElt -> RngMPolElt

Given elements f and g from a polynomial ring P, return the S-polynomial of f and g.

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 H112E5 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.

Construction of Input Systems

MinRankSystem(K, n, k, r) : FldFin, RngIntElt, RngIntElt, RngIntElt -> [ RngMPolBool ]

For a finite field K and positive integer parameters n, k, r, the square (n, k, r)-MinRank problem is as follows: given a square linear matrix of size n with k variables (i.e., a matrix whose entries are k-variate polynomials of degree 1 over K), the goal is to find the locus of the points (assignment to the k variables) such that the evaluated matrix has rank less than or equal to r. This function returns the sequence of minors of the relevant symbolic matrix as multivariate polynomials with k variables, so solving the corresponding multivariate system solves the MinRank problem instance. See Example H5E5 in Chapter PARALLELISM on parallelism for example systems constructed by this function.

HFESystem(q, n, D) : RngIntElt, RngIntElt, RngIntElt -> [ RngMPolBool ]

For a prime power q and positive integer parameters n, d, this function returns a random Hidden Field Equations (HFE) system over GF(q) with n variables and secret degree D. See Example H5E7 in Chapter PARALLELISM on parallelism for example systems constructed by this function.

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.

> 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

> 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)
]

> 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]

> 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
]

> 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
]

> 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
]

> 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

> 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

> 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.

> 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
]

• « Previous
• Up
• Contents
• Index
• Search
• Next »