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 "Converting Bases with the Gröbner Walk", by Collart, Kalkbrener and Mall [J. Symbolic Computation, to appear]).
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 equivalent to I which has the "easy" order of I and the same (Gröbner) basis of I w.r.t. the 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.
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 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 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.
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.
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.
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.
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 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.
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.
> 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
> print 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
> print #Basis(I);
20
> time W := GroebnerWalk(I, Q);
Time: 1.500
> print 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);
> print 1 in I;
true
> C := Coordinates(I, P!1);
> print 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:
> print C[1]*S[1] + C[2]*S[2] + C[3]*S[3];
1