Magma contains a powerful system for computing in ideals of multivariate polynomial rings. This is based on the construction of Gr"obner bases of such ideals. Currently it is only possible to create ideals and quotient rings in 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"obner basis (with respect to some fixed monomial ordering). This Gr"obner basis will be computed automatically when needed by Magma. Before this happens, an ideal will usually possess a basis which is not a Gr"obner basis, but that will be changed into the unique Gr"obner 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"obner 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"obner basis computation much more expensive so a user basis should usually not be specified.
Different monomial orderings give different Gr"obner bases for a fixed ideal. The basic rule within Magma is that 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"obner Walk algorithm for changing the Gr"obner basis with respect to one monomial order to the Gr"obner basis with respect to another monomial order (see "Converting Bases with the Gr"obner Walk", by Collart, Kalkbrener and Mall [J. Symbolic Computation, to appear]).
Note that a Gr"obner basis for an ideal will be automatically generated when
necessary; the Groebner procedure just allows control of the algorithm
to determine the Gr"obner basis.
Basis(I) : RngDPol -> RngDPolElt
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"obner 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"obner basis of I is used as the basis b_1, ..., b_k. The resulting sequence is not necessarily unique.
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"obner basis for I to be constructed. If the parameter Walk is false, the Gr"obner Walk algorithm is not used but the Buchberger algorithm with respect to the order of I. Otherwise, a Gr"obner basis of I is constructed with respect to an "easy" order, and then the Gr"obner 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.
Given an ideal I, force the Gr"obner basis of I to be computed, and then return that.
Given a set or sequence S of polynomials, return the unique Gr"obner basis of the ideal generated by as a sorted sequence. This function is useful for computing Gr"obner bases without the need to construct ideals.
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"obner Walk of the Gr"obner basis of I with respect to the order <_I to the order <_J. Thus an ideal containing a Gr"obner basis with respect to the same order as J is returned. The parameters are the same as for the procedure Groebner.
Change verbose printing for the Buchberger algorithm which is used to compute a Gr"obner basis to be v.
Change verbose printing for the Gr"obner Walk algorithm to be v. It is recommended that the "Groebner" verbose flag be turned off when this flag is turned on.
> 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: 11.931
> 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
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
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
Note that since ideals of a full polynomial ring P are regarded as subrings
of P, the ring P itself is a valid ideal as well.
I + J : RngDPol, RngDPol -> RngDPol
Given ideals I and J of the same polynomial ring P, return the sum of I and J, which is the ideal generated by the generators of I and those of J.
Given ideals I and J of the same polynomial ring P, return the product of I and J, which is the ideal generated by the products of the generators of I and those of J.
Given an ideal I of the polynomial ring P, and an integer k, return the k-th power of I.
Given ideals I and J of the same polynomial ring P such that J is a subideal of I, return the quotient ring I/J.
Given ideals I and J of the same polynomial ring P, return the colon ideal I:J (or ideal quotient of I by J), consisting of the polynomials f of P such that f * g is in I for all g in J.
Given an ideal I of a generic polynomial ring P, return P.
Given an ideal I, return the leading monomial ideal of I; that is, the ideal generated by all the leading monomials of I.
Given ideals I and J of the same polynomial ring P, return the intersection of I and J.
Given two ideals I and J of the same polynomial ring P, return true if and only if I and J are the same, and false otherwise.
Given a set or sequence S of polynomials describing a basis of an ideal, return whether the basis is a Groebner basis.
Given an ideal I of the polynomial ring P, return whether I is proper; that is, whether I is strictly contained in P.
Given an ideal I of the polynomial ring P, return whether I is the zero ideal.
Given an ideal I of the polynomial ring P, return whether I is zero-dimensional (so the quotient of P by I has finite dimension as a vector space over the coefficient field).
Given two ideals I and J of the same polynomial ring P, return false if and only if I and J are the same.
Given two ideals I and J in the same polynomial ring P return false if and only if I is contained in J.
Given two ideals I and J in the same polynomial ring P return true if and only if I is contained in J.
> P<x, y, z> := PolynomialAlgebra(RationalField(), 3);
> I := ideal<P | x*y - 1, x^3*z^2 - y^2, x*z^3 - x - 1>;
> J := ideal<P | x*y - 1, x^2*z - y, x*z^3 - x - 1>;
> A := I * J;
> print A;
Ideal of Polynomial ring of rank 3 over Rational Field
Lexicographical Order
Variables: x, y, z
Basis:
[
x^2*y^2 - 2*x*y + 1
x^3*y*z - x^2*z - x*y^2 + y
x^2*y*z^3 - x^2*y - x*y - x*z^3 + x + 1
x^4*y*z^2 - x^3*z^2 - x*y^3 + y^2
x^5*z^3 - x^3*y*z^2 - x^2*y^2*z + y^3
x^4*z^5 - x^4*z^2 - x^3*z^2 - x*y^2*z^3 + x*y^2 + y^2
x^2*y*z^3 - x^2*y - x*y - x*z^3 + x + 1
x^3*z^4 - x^3*z - x^2*z - x*y*z^3 + x*y + y
x^2*z^6 - 2*x^2*z^3 + x^2 - 2*x*z^3 + 2*x + 1
]
> M := I meet J;
> print M;
Ideal of Polynomial ring of rank 3 over Rational Field
Lexicographical Order
Variables: x, y, z
Basis:
[
x^3 + x^2 + y^5 - y^2*z - z^2
x^4 + x^3 - x*z^2 + y^4 - y*z
-y + z^3 - 1
x*y - 1
]
> print A eq M;
true
> print ColonIdeal(I, J);
Ideal of Polynomial ring of rank 3 over Rational Field
Lexicographical Order
Variables: x, y, z
Basis:
[
-x*z^2 + y^4
-x^2 - x + y^3*z
x^2*z^2 - y^3
x^3 + x^2 - y^2*z
-y + z^3 - 1
x*y - 1
]
Given a polynomial f from a polynomial ring P, together with an ideal I of P, return whether f is in I.
Given a polynomial f from a polynomial ring P, together with an ideal I of P, return whether f is in the radical of I.
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"obner basis of) I.
Given a polynomial f from a polynomial ring P, together with an ideal I of P, return whether f is not in I.
Given elements f and g from a polynomial ring P, return the S-polynomial of f and g.
> P<x, y, z> := PolynomialRing(RationalField(), 3); > I := ideal<P | (x + y)^3, (y - z)^2, y^2*z + z>; > print NormalForm(y^2*z + z, I); 0 > print NormalForm(x^3, I); -3*x^2*y - 3*x*z^4 - 6*x*z^2 + 1/2*z^3 + 3/2*z > print NormalForm(z^4 + y^2, I); 2*z^4 + 2*z^2 > print x + y in I; false > print IsInRadical(x + y, I); true > print IsInRadical((x + y)^2, I); true > print IsInRadical(z, I); false > print SPolynomial(x^4 + y - z, x^2 + y - z); -x^2*y + x^2*z + y - z
Given a zero-dimensional ideal I of a polynomial ring P whose order is of lexicographic type, return the variety of I as a sequence of vectors. Each vector is of length n, where n is the rank of P, and corresponds to an assignment of the n variables of P (in order) such that all polynomials in I vanish with this assignment. The ideal must be zero-dimensional so that the variety is known to be finite.
Given a zero-dimensional ideal I of a polynomial ring P whose order is of lexicographic type, return the variety of I as a sequence of sequences of field elements. Each inner sequence is of length n, where n is the rank of P, and corresponds to an assignment of the n variables of P (in order) such that all polynomials in I vanish with this assignment. The ideal must be zero-dimensional so that the variety is known to be finite.
> K<w> := GF(27);
> P<x, y> := PolynomialRing(K, 2);
> I := ideal<P | x^8 + y + 2, y^6 + x*y^5 + x^2>;
> Groebner(I);
> print I;
Ideal of Polynomial ring of rank 2 over GF(3^3)
Lexicographical Order
Variables: x, y
Groebner basis:
[
x + 2*y^47 + 2*y^45 + y^44 + 2*y^43 + y^41 + 2*y^39 + 2*y^38 + 2*y^37 +
2*y^36 + y^35 + 2*y^34 + 2*y^33 + y^32 + 2*y^31 + y^30 + y^28 + y^27 +
y^26 + y^25 + 2*y^23 + y^22 + y^21 + 2*y^19 + 2*y^18 + 2*y^16 + y^15 +
y^13 + y^12 + 2*y^10 + y^9 + y^8 + y^7 + 2*y^6 + y^4 + y^3 + y^2 + y +
2
y^48 + y^41 + 2*y^40 + y^37 + 2*y^36 + 2*y^33 + y^32 + 2*y^29 + y^28 +
2*y^25 + y^24 + y^2 + y + 1
]
> V := Variety(I);
> print V;
[
(w^14 w^12),
(w^16 w^10),
(w^22 w^4)
]
> // Check that the original polynomials vanish:
> print [
> <x^8 + y + 2, y^6 + x*y^5 + x^2> where x is v[1] where y is v[2]: v in V
> ];
[ <0, 0>, <0, 0>, <0, 0> ]
Given an ideal I of a polynomial ring P of rank n with P = K[x_1, ..., x_n], together with an integer k with 0 <= k < n, return the k-th elimination ideal I_k of I, which is defined to be I intersect K[x_(k + 1), ..., x_n]. Thus I_k consists of all polynomials of I which have the first k variables eliminated. If the elimination ideals I_k are to be computed for several different k, it is recommended first that a Gr"obner basis with respect to lexicographical order for I first be computed as then the elimination ideals can be determined trivially. If I does not have a Gr"obner basis stored with respect to lexicographical order, then a Gr"obner basis computation will be necessary each time an elimination ideal is desired.
Given an ideal I of a polynomial ring P of rank n with P = K[x_1, ..., x_n], together with a set S describing a subset U of the variables { x_1, ... x_n }, return the elimination ideal I_U of I, which is defined to be I intersect K[U]. Thus I_U consists of all polynomials of I which contain variables only found in U. U can be specified in two ways: either as a set S of integers in the range 1 ... n such the integer i corresponds to the i-th variable x_i, or as a set S of variables lying in P.
> P<x, y, z> := PolynomialRing(RationalField(), 3);
> I := ideal<P |
> 1 - x + x*y^2 - x*z^2,
> 1 - y + y*x^2 + y*z^2,
> 1 - z - z*x^2 + z*y^2 >;
> print EliminationIdeal(I, {x});
Ideal of Polynomial ring of rank 3 over Rational Field
Lexicographical Order
Variables: x, y, z
Basis:
[
x^21 - x^20 - 2*x^19 + 4*x^18 - 5/2*x^17 - 5/2*x^16 + 4*x^15 - 15/2*x^14 +
129/16*x^13 + 11/16*x^12 - 103/8*x^11 + 131/8*x^10 - 49/16*x^9 -
171/16*x^8 + 12*x^7 - 3*x^6 - 29/8*x^5 + 15/4*x^4 - 17/16*x^3 -
5/16*x^2 + 5/16*x - 1/16
]
> print EliminationIdeal(I, {y});
Ideal of Polynomial ring of rank 3 over Rational Field
Lexicographical Order
Variables: x, y, z
Basis:
[
y^14 - y^13 - 13/2*y^12 + 8*y^11 + 53/4*y^10 - 97/4*y^9 - 45/8*y^8 + 33*y^7
- 25/2*y^6 - 18*y^5 + 107/8*y^4 + 5/8*y^3 - 27/8*y^2 + 9/8*y - 1/8
]
> print EliminationIdeal(I, {z});
Ideal of Polynomial ring of rank 3 over Rational Field
Lexicographical Order
Variables: x, y, z
Basis:
[
z^21 - z^20 - 2*z^19 + 4*z^18 - 5/2*z^17 - 5/2*z^16 + 4*z^15 - 15/2*z^14 +
129/16*z^13 + 11/16*z^12 - 103/8*z^11 + 131/8*z^10 - 49/16*z^9 -
171/16*z^8 + 12*z^7 - 3*z^6 - 29/8*z^5 + 15/4*z^4 - 17/16*z^3 -
5/16*z^2 + 5/16*z - 1/16
]
> print EliminationIdeal(I, {y, z});
Ideal of Polynomial ring of rank 3 over Rational Field
Lexicographical Order
Variables: x, y, z
Basis:
[
y^5*z^2 - 1/4*y^5 + 1/4*y^4 - 9/4*y^3*z^2 + y^3*z + 1/2*y^3 + 1/4*y^2*z^2 -
1/2*y^2 + 5/4*y*z^2 - 5/4*y*z + 1/4*y - 1/4*z^2 + 1/4*z + 1/4
y^6*z - 15/4*y^4*z + y^4 + y^3*z - 3/4*y^2*z^2 + 15/4*y^2*z - 2*y^2 - 2*y*z
+ 1/4*y - 1/4*z^5 + 1/4*z^4 - 1/2*z^3 + 1/2*z^2 - 1/4*z + 1/4
y^7 - y^6 + 4*y^5*z - 15/4*y^5 + 3*y^4*z^2 + 15/4*y^4 + 1/4*y^3*z^2 -
10*y^3*z + 13/2*y^3 - 25/4*y^2*z^2 + 4*y^2*z - 9/2*y^2 - 5/4*y*z^2 +
25/4*y*z - 13/4*y + z^4 - z^3 + 9/4*z^2 - 13/4*z + 7/4
-y^6 + y^5 + 6*y^4*z^2 - 3*y^4*z + 2*y^4 - 3*y^3*z^2 - 2*y^3 - 10*y^2*z^2 +
9*y^2*z - 2*y^2 + 7*y*z^2 - 3*y*z + y + z^6 - z^5 + 2*z^4 - 2*z^3 + z^2
- z
y^3*z + y*z^3 - 2*y*z + y + z
]
Given a sequence Q of k polynomials of a polynomial ring P over a field K, return the relation ideal R of Q which is an ideal of the polynomial ring of rank k over K containing all algebraic relations between the elements of Q. That is, R consists of all polynomials r in K[y_1, ..., y_k] such that r(Q[1], ..., Q[k]) = 0. If R is desired to be an ideal of a particular polynomial ring S of rank k (to obtain predetermined names of variables, for example), then S may also be passed.
> P<x, y, z> := PolynomialRing(GF(2), 3, "grevlex");
> S := [(x + y + z)^2, (x^2 + y^2 + z^2)^3 + x + y + z + 1];
> I := ideal<P | S>;
> Groebner(I);
> print I;
Ideal of Polynomial ring of rank 3 over GF(2)
Graded Reverse Lexicographical Order
Variables: x, y, z
Groebner basis:
[
1
]
> Q<a, b> := PolynomialRing(GF(2), 2);
> R := RelationIdeal(S, Q);
> print R;
Ideal of Polynomial ring of rank 2 over GF(2)
Lexicographical Order
Variables: a, b
Basis:
[
a^6 + a + b^2 + 1
]
> // Check the expression:
> print S[1]^6 + S[1] + S[2]^2;
1