Computation in ideals of multivariate polynomial rings is possible because of the construction of Gröbner bases of such ideals. Currently it is only possible to create ideals of multivariate polynomial rings over fields.
In this section, the term "basis" will refer to an ordered sequence of polynomials which generate an ideal. (Thus a basis can contain duplicates and zero elements so is not like a basis of a vector space.) Every ideal of a polynomial ring over a field possesses a unique sorted reduced Gröbner basis (with respect to some fixed monomial ordering). 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 that will be changed into the unique Gröbner basis when needed. Thus the original basis will be discarded. It is also possible to create an ideal with a specific basis U and then find the coordinates of polynomials from the polynomial ring with respect to U (see the function Coordinates below). This is done by specifying a user basis with the Ideal intrinsic. In this case, when Magma computes the Gröbner basis of the ideal, extra information is stored so that polynomials of the ideal can be rewritten in terms of the original basis. However, the use of this feature makes the Gröbner basis computation much more expensive so an ideal should usually not be created with a user basis.
Different monomial orderings give different Gröbner bases for a fixed ideal. When an ideal I is created of the 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.
Given a multivariate polynomial ring P over a field K, return the ideal of P generated by the elements of P specified by the list L. Each term of the list L must be an expression defining an object of one of the following types:
- An element of P;
- A set or sequence of elements of P;
- An ideal of P;
- A set or sequence of ideals of P.
Given a sequence Q of polynomials from a polynomial ring P over a field K, return the ideal of P generated by the elements of Q with given user basis Q. This function should only be used when it is desired to express polynomials of the ideal in terms of the elements of Q.
The following functions allow one to manipulate the bases of polynomial ideals. Magma incorporates an implementation of the exciting new Gröbner Walk algorithm for changing the Gröbner basis of an ideal with respect to one monomial order to the Gröbner basis with respect to another monomial order (see [S. Collart, M. Kalkbrener and D. Mall, Converting Bases with the Gröbner Walk, J. Symb. Comp. 24 (1997), pp. 465--469.]).
Note that a Gröbner basis for an ideal will be automatically generated when
necessary; the Groebner procedure just allows control of the algorithm
to determine the Gröbner basis.
Basis(I) : RngMPol -> RngMPolElt
Given an ideal I, return the current basis of I. If I has a user basis, that is returned; otherwise the current basis of I (whether it has been converted to a Gröbner basis or not) is returned.
Given an ideal I together with an integer i, return the i-th element of the current basis of I.
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 an ideal I, return the ideal E which is mathematically equal to I but whose basis is the Gröbner basis of the 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.
Homogenize: BoolElt Default: true
ReduceInitial: 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. If the parameter Walk is false, the Gröbner Walk algorithm is not used but the plain Buchberger algorithm with respect to the order of I. Otherwise, a Gröbner basis of I is constructed with respect to an "easy" order, and then the Gröbner Walk algorithm is applied to this basis to change the basis to be with respect to the order of I.The parameters Homogenize, ReduceInitial, and ReduceByNew control the main Buchberger algorithm (used for the whole computation if the Walk algorithm is not used, or used for the first step to find a Gröbner basis with respect to the easy order if the Walk algorithm is used). Homogenization specifies whether the ideal should be homogenized first; if so, a Gröbner basis of the homogenization of the ideal is computed and then the homogenization variable is removed and the final basis reduced. ReduceInitial specifies whether the basis of the ideal should first be reduced (see the function Reduce) before any S-polynomial pairs are considered. ReduceByNew specifies whether 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 parameters have the default values of true, 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 false 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 perturbe 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 perturbe 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.
Homogenize: BoolElt Default: true
ReduceInitial: 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)
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.
Homogenize: BoolElt Default: true
ReduceInitial: 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)
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.
Homogenize: BoolElt Default: true
ReduceInitial: BoolElt Default: true
ReduceByNew: BoolElt Default: true
Given a set or sequence S of polynomials, return a 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.
SigmaEpsilon: FldRatElt Default: 1/2
TauEpsilon: FldRatElt Default: 1/n
SigmaVectors: RngIntElt Default: n
TauVectors: RngIntElt Default: Ceiling(n/2)
Given ideals I and J of a polynomial ring P, with <_I the term order of I, and <_J the term order of J, perform the Gröbner Walk of the Gröbner basis of I with respect to the order <_I to the order <_J. Thus an ideal containing a Gröbner basis with respect to the same order as J is returned. The parameters are the same as for the procedure Groebner. Note that the Gröbner Walk algorithm is also automatically called internally when relevant. This function is now practically superseded by the ChangeOrder function.
(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 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, 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 monomial is a multiple of another leading monomial 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).
Change the verbose printing level for the Buchberger algorithm which is used to compute a Gröbner basis to be v. Currently the legal values for v are true, false, 0, or 1.
Change verbose printing for the Gröbner Walk algorithm to be v. Currently the legal values for v are true, false, 0, 1, or 2. If v is 1, the "Groebner" verbose flag is turned off in each of the steps in the Walk if it is on. If v is 2, the "Groebner" verbose flag is not turned off at any stage.
> 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: 3.870
> #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
> 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>
]
> 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: 1.940
> 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)
]
> Q<x, y, z, t, u> := PolynomialRing(RationalField(), 5);
> P<x, y, z, t, u> := PolynomialRing(RationalField(), 5, "grevlex");
> I := ideal<P |
> x + y + z + t + u,
> x*y + y*z + z*t + t*u + u*x,
> x*y*z + y*z*t + z*t*u + t*u*x + u*x*y,
> x*y*z*t + y*z*t*u + z*t*u*x + t*u*x*y + u*x*y*z,
> x*y*z*t*u - 1>;
> time Groebner(I);
Time: 0.760
> #Basis(I);
20
> time W := GroebnerWalk(I, Q);
Time: 1.500
> W;
Ideal of Polynomial ring of rank 5 over Rational Field
Lexicographical Order
Variables: x, y, z, t, u
Dimension 0
Groebner Basis:
[
x + y + z + t + u
y^2 + 3*y*u + 2*t^6*u + 6*t^5*u^2 + t^4*u^3 - 2*t^3*u^4 + t^2 -
566/275*t*u^11 - 6273/25*t*u^6 + 69019/275*t*u - 1467/275*u^12 -
16271/25*u^7 + 179073/275*u^2
y*z - y*u + z^2 + 2*z*u - 6/5*t^6*u - 19/5*t^5*u^2 - t^4*u^3 + t^3*u^4 -
2*t^2 + 334/275*t*u^11 + 3702/25*t*u^6 - 40726/275*t*u + 867/275*u^12
+ 9616/25*u^7 - 105873/275*u^2
y*t - y*u - 2/5*t^6*u - 8/5*t^5*u^2 - t^4*u^3 + t^3*u^4 + 124/275*t*u^11 +
1372/25*t*u^6 - 15106/275*t*u + 346/275*u^12 + 3838/25*u^7 -
42124/275*u^2
y*u^5 - y + 1/55*u^11 + 13/5*u^6 - 144/55*u
z^3 + 2*z^2*u - 2*z*u^2 + t^6*u^2 + 2*t^5*u^3 - 2*t^4*u^4 + 2*t^2*u -
232/275*t*u^12 - 2576/25*t*u^7 + 28018/275*t*u^2 - 568/275*u^13 -
6299/25*u^8 + 69307/275*u^3
z*t - z*u + 8/5*t^6*u + 22/5*t^5*u^2 - t^3*u^4 + t^2 - 442/275*t*u^11 -
4901/25*t*u^6 + 53913/275*t*u - 1121/275*u^12 - 12433/25*u^7 +
136674/275*u^2
z*u^5 - z + 1/55*u^11 + 13/5*u^6 - 144/55*u
t^7 + 3*t^6*u + t^5*u^2 - t^2 - 398/55*t*u^11 - 4414/5*t*u^6 + 48787/55*t*u
- 1042/55*u^12 - 11556/5*u^7 + 128103/55*u^2
t^2*u^5 - t^2 - 2/55*t*u^11 - 21/5*t*u^6 + 233/55*t*u - 8/55*u^12 -
89/5*u^7 + 987/55*u^2
u^15 + 122*u^10 - 122*u^5 - 1
]
> 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
]
// Check the expression:
> C[1]*S[1] + C[2]*S[2] + C[3]*S[3];
1