Computation in ideals of multivariate polynomial rings is possible because of the construction of Gröbner bases of such ideals. Since V2.8 (July 2001), 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 of ideals defined over fields have been studied for some time now, and there is a large literature concerning them. Magma computes Gröbner bases over fields by means of the Buchberger algorithm [CLO96, Chap. 2, Para 7] (including the advanced criteria for eliminating useless pairs in [Möl88]), the FGLM algorithm [FGLM93] and the Gröbner Walk algorithm [CKM97]. See below for details as to how these algorithms are employed.
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 [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.
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`ere's F_4 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 in I, there exists a g in 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^2, 2x } is a Gröbner basis and the polynomial x^2 is not redundant since 2 does not divide 1, but over Q, the polynomial x^2 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_1 = x^2 + 14xy and f_2 = 5y + 9 are in Z[x, y]. Then { f_1, f_2 } is not reduced, since the second term of f_1 can be reduced by f_2 (y divides xy and the Euclidean quotient of 14 by 5 is 2, with remainder 4). But if we were to replace f_1 by f_1 - 2xf_2 = x^2 + 4xy - 18x, then { f_1, f_2 } would now be reduced.
Steel's extension of Faug`ere'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!
The following functions and procedures allow one to construct Gröbner bases. Magma incorporates efficient implementations of both the FGLM algorithm [FGLM93] and the Gröbner Walk algorithm [CKM97] which both change the Gröbner basis of an ideal defined over a field with respect to one monomial order to the Gröbner basis with respect to another monomial order (the FGLM algorithm only works for a zero-dimensional ideal).
Note that a Gröbner basis for an ideal will be automatically generated when necessary; the Groebner procedure below just allows control of the algorithms used to compute the Gröbner basis.
Al: MonStgElt Default: "Default"
Homogenize: BoolElt Default: true
ReduceInitial: BoolElt Default: true
RemoveRedundant: BoolElt Default: true
ReduceByNew: BoolElt Default: true
Walk: BoolElt Default: true
SigmaEpsilon: FldRatElt Default: 1/2
TauEpsilon: FldRatElt Default: 1/n
SigmaVectors: RngIntElt Default: n
TauVectors: RngIntElt Default: Ceiling(n/2)
(Procedure.) Explicitly force a Gröbner basis for I to be constructed. This procedure is normally not necessary, as Magma will automatically compute the Gröbner basis when needed, but it does allow one to control how the Gröbner basis is constructed by various parameters.The parameter Al may be set to one of: "Default", "Direct", "FGLM" or "Walk". The value "Direct" specifies that the Buchberger algorithm (for fields) or the Faug`ere algorithm (for non-fields) should be used directly with no order conversion. For ideals over fields only, the values "FGLM" and "Walk" specify that a Gröbner basis with respect to an "easy" order should first be computed, and then the FGLM algorithm or Gröbner Walk algorithm, respectively, should be used to convert this to the final Gröbner basis with respect to the original order. 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.
Since V2.7, the obsolete parameter Walk is supported but will be removed in the future, so its use is discouraged. Setting Walk to {true} is equivalent to setting Al to "Walk", while setting Walk to {false} is equivalent to setting Al to "Direct" (since this mirrors the previous behaviour).
The control parameters Homogenize, ReduceInitial, RemoveRedundant and ReduceByNew control the Buchberger algorithm (used for the whole computation if the direct method is specified, or used for the first step to find a Gröbner basis with respect to the easy order if a conversion algorithm is used).
Setting Homogenization to {true} specifies that the ideal should first be homogenized: a Gröbner basis of the homogenization of the ideal is computed and then the homogenization variable is removed and the final basis reduced.
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 Gröbner basis 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), since in Magma most computations are improved by these defaults, but there exist many ideals 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 Gröbner bases is very difficult to design.)
For the Walk algorithm, the parameters SigmaEpsilon and TauEpsilon control the factor epsilon which is used to perturb the initial weight vector sigma and the final weight vector tau 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 sigma and the final weight vector tau respectively. By default, the epsilon factor and number of weight vectors for sigma are determined dynamically to be "optimal", while the epsilon factor for tau is taken to be 1/n and the number of weight vectors for tau is taken to be Ceiling(n/2), where n is the rank of I.
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.
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.
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.
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.
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.
(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.
(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.
(Procedure.) Change the verbose printing level for the Faug`ere 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.
(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.
(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.
The following functions and procedures perform operations related to Gröbner bases.
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.
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, 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.
(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.
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.
Given an ideal I of a polynomial ring P, together with a polynomial f in I, and supposing that I has basis b_1, ..., b_k, return a sequence [g_1, ..., g_k] of elements of P so that f = g_1 * b_1 + ... + g_k * b_k. If I has a user basis, then that is used as the basis b_1, ..., b_k; otherwise the Gröbner basis of I is used as the basis b_1, ..., b_k. The resulting sequence is not necessarily unique.
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.
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).
> 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.290
> I;
Ideal of Polynomial ring of rank 11 over
Rational function field of rank 2 over Integer Ring
Variables: c2, c3
Lexicographical Order
Variables: c4, b4, b3, b2, b1, a21, a31, a32, a41, a42, a43
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<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
]
Notice that the Gröbner basis contains polynomials whose leading
terms are x^2, xz and 2x, but the third cannot eliminate the
first two since the leading coefficient 2 does not divide the other
leading coefficients 1 and 1.
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*zIf we compute the normal form of ( - x) modulo I, then even though the x monomial cannot be reduced, the result is NOT the negative of the normal form of x, since one can use the 2x - yz polynomial and the fact that (( - 1) mod 2) is 1 to reduce the polynomial to a unique normal form. This behaviour differs from that for ideals defined over fields, where the normal form of -f will always be the negative of the normal form of f.
> NormalForm(-x, I); x - y*zIf we reduce the Gröbner basis modulo various primes, we obtain familiar Gröbner bases over fields:
> 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
]
But if we reduce modulo 4, using the ring of integers modulo 4, then
the Gröbner basis still has a structure not encountered when working
over fields:
> GroebnerBasis(ChangeRing(I, IntegerRing(4)));
[
x^2 + 3,
x*z + 2*y,
2*x + y*z,
y^2 + 3,
z^2,
2*z
]
In fact, the new polynomial 2z has been included in this Gröbner basis.
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
]
However, when we compute the Gröbner basis of I (defined over Z),
we note that there is a certain integer in the ideal which is not 1.
> GroebnerBasis(I);
[
x + 170269749119,
y + 2149906854,
z + 170335012540,
282687803443
]
Now for each prime p dividing this integer 282687803443, the
Gröbner basis of I modulo p will be non-trivial and will
thus give a solution of the original system modulo p.
> 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
]
Of course, modulo any other prime the Gröbner basis is trivial so
there are no other solutions. For example:
> GroebnerBasis(ChangeRing(I, GF(3)));
[
1
]
Note that the problem can also be solved by using resultants,
but this may yield many extraneous potential primes, while
the Gröbner basis technique yields the exact list of primes
for which there are modular solutions.
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_1 = 2xy + Sqrt( - 5)y and f_2 = (1 + Sqrt( - 5))x^2 - 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^2 + 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
]
In [AL94, p. 224], a (weak) Gröbner basis for the ideal
is given as {f_2, f_5, f_7, f_9}, where
f_5 = (5 + Sqrt( - 5))y^2 - 15y,
f_7 = - 2Sqrt( - 5)y^2 + 5(1 + Sqrt( - 5))y, and
f_9 = xy + Sqrt( - 5)y^3 - 5Sqrt( - 5)y^2 + 8Sqrt( - 5)y.
We can easily verify that the ideal J generated by these 4 polynomials
describes the same ideal as I (and so has the same Gröbner basis
in Magma).
> 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); trueWe can even write f_5, f_7 and f_9 as combinations of the Gröbner basis elements of I, as follows.
> 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
]
We can see that these elements are fairly trivially derived from the
Gröbner basis which Magma computes for I.
But if we now create J again using the Ideal function
and the sequence
Q = [f_2, f_5, f_7, f_9, S^2 + 5],
then we can see the coordinates of any element
of I=J as a linear combination of the elements of Q.
We find the coordinates of the second element
of Magma's original Gröbner basis of I with respect to Q.
The resulting coordinates are rather non-trivial.
> Q := [f2, f5, f7, f9, S^2 + 5];
> J := Ideal(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
]
We check that multiplying out the expression recovers g.
> &+[C[i]*Q[i]: i in [1 .. #C]] eq g; trueNote that in the terminology of Adams and Loustaunau, Magma is here computing a "strong" Gröbner basis (for this representation which uses an extra variable for Sqrt( - 5)), while these authors show that {f_2, f_5, f_7, f_9} constitutes a "weak" Gröbner basis for I over the ring Z[Sqrt( - 5)]. The fact that the coordinates of g with respect to Q are rather non-trivial shows that Magma's strong Gröbner basis computation has computed a lot more information than the weak Gröbner basis (i.e., g, which must be included in the strong Gröbner basis, is not trivially derived from Q).
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 alpha = (1 + Sqrt(5))/2, we can introduce a variable new A and the polynomial (2A - 1)^2 - 5.
> P<x, y> := PolynomialRing(RationalField(), 2);
> S := [x^2 - y, x^3 + y^2, x*y^3 - 1];
> I := Ideal(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
]
Now we check that multiplying out by the coordinates gives 1.
> C[1]*S[1] + C[2]*S[2] + C[3]*S[3]; 1Now we move the problem to being over the integer ring Z.
> P<x, y> := PolynomialRing(IntegerRing(), 2);
> S := [x^2 - y, x^3 + y^2, x*y^3 - 1];
> I := Ideal(S);
> 1 in I;
false
> GroebnerBasis(I);
[
x + 1,
y + 1,
2
]
We note that 1 is not in the ideal this time, but 2 is! So we compute
the coordinates of 2 with respect to I this time.
> 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
]
Note that C is the same as above, except that each polynomial has
been scaled by 2 to make it integral.
Finally we check again that multiplying out by the coordinates gives 2.
> C[1]*S[1] + C[2]*S[2] + C[3]*S[3]; 2Incidentally, we can see from the Gröbner basis of I over Z that the only solution to the system of equations described by S is the local solution x=y=1 over GF(2).