Elimination theory plays an important role when working with ideals of multivariate polynomial rings. Magma provides an assortment of functions to perform various kinds of elimination easily.
All of the functions in this section may be applied to ideals over general Euclidean rings, not just over fields.
Given an ideal I of a polynomial ring P of rank n with P = R[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 R[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öbner 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öbner basis stored with respect to lexicographical order, then a Gröbner basis computation will be necessary each time an elimination ideal is desired.If k=n, then I intersect R is returned, which, if R is a field, is always the full ring P or the empty ideal, according to whether I is the full polynomial ring or not. But if R is not a field, then this intersection will yield the ideal generated by the normalized smallest element of R which is in I (according to the Euclidean norm), which could be neither 0 nor 1.
The parameters are as for the Groebner procedure. Note that setting Al := "Direct" occasionally produces much better performance since the relevant elimination order may yield a better Gröbner basis than the default method of going via the grevlex order.
Given an ideal I of a polynomial ring P of rank n with P = R[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 R[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. S may be the empty set, in which case this is equivalent to EliminationIdeal(I, n); see above.
As before, R = Z[Sqrt( - 5)] and I is the ideal of R[x, y] generated by f_1 = 2xy + Sqrt( - 5)y and f_2 = (1 + Sqrt( - 5))x^2 - xy. As before, we compute over Z, introduce a new variable S and include (S^2 + 5) in I, so we can effectively work over R.
> 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, Ex. 4.3.8], the elimination ideal
E_y = I intersect (Z[Sqrt( - 5))[y] is shown to be generated by
f_5 = (5 + Sqrt( - 5))y^2 - 15y and
f_7 = - 2Sqrt( - 5)y^2 + 5(1 + Sqrt( - 5))y.
We can compute E_y in Magma easily using EliminationIdeal.
We must be careful to include S in the second argument (the set of variables
which we want), since S should be considered a `constant' (member of R)
in this context.
> Ey := EliminationIdeal(I, {y, S});
> GroebnerBasis(Ey);
[
y^2*S + 5*y^2 - 15*y,
10*y^2 + 5*y*S - 25*y,
S^2 + 5
]
Obviously, the polynomials yielded are simply the last 3
polynomials of the full Gröbner basis given above. We check also
that the ideal generated by f_5 and f_7 over R is the same as
that given by Magma.
> f_5 := y^2*S + 5*y^2 - 15*y; > f_7 := -2*y^2*S + 5*y*S + 5*y; > E := ideal<P | f_5, f_7, S^2 + 5>; > E eq Ey; trueFinally, we also compute E_x = I intersect (Z[Sqrt( - 5))[x], which requires more effort this time, since it cannot be read off the Gröbner basis.
> Ex := EliminationIdeal(I, {x, S});
> GroebnerBasis(Ex);
[
2*x^3*S + 2*x^3 + x^2*S - 5*x^2,
12*x^3 + 6*x^2*S,
S^2 + 5
]
From this, we see that E_x is generated by
(2 + 2Sqrt( - 5))x^3 + ( - 5 + Sqrt( - 5))x^2 and
12x^3 + 6Sqrt( - 5)x^2.
Given a zero-dimensional ideal I of a polynomial ring P of rank n with P = K[x_1, ..., x_n], together with an integer i with 1 <= i <= n, return the unique monic generator of the univariate elimination ideal I intersect K[x_(i)].
Given a zero-dimensional ideal I of a polynomial ring P of rank n with P = K[x_1, ..., x_n], return the sequence of length n whose i-th element is the unique monic generator of the univariate elimination ideal I intersect K[x_(i)].
> 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 >;
> UnivariateEliminationIdealGenerator(I, 1);
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
> UnivariateEliminationIdealGenerator(I, 2);
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
> 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
]
> function ZRadical(I)
> // Find radical of zero dimensional ideal I
> P := Generic(I);
> n := Rank(P);
> G := UnivariateEliminationIdealGenerators(I);
> N := {};
>
> for i := 1 to n do
> // Set FF to square-free part of the i-th univariate
> // elimination ideal generator
> F := G[i];
> FF := F;
> while true do
> D := GCD(FF, Derivative(FF, 1, i));
> if D eq 1 then
> break;
> end if;
> FF := FF div D;
> end while;
> // Include FF in N if FF is a proper divisor of F
> if FF ne F then
> Include( N, FF);
> end if;
> end for;
>
> // Return the sum of I and N
> if #N eq 0 then
> return I;
> else
> return ideal<P | I, N>;
> end if;
> end function;
We now apply ZRadical to an ideal of Q[x, y, z].
> P<x, y, z> := PolynomialRing(RationalField(), 3);
> I := ideal<P | (x+1)^3*y^4, x*(y-z)^2+1, z^3-z^2>;
> R := ZRadical(I);
> Groebner(I);
> Groebner(R);
> I;
Ideal of Polynomial ring of rank 3 over Rational Field
Lexicographical Order
Variables: x, y, z
Dimension 0
Groebner basis:
[
x - 4*y^9 + 21*y^8 - 32*y^7 + 7*y^6 + 432*y^5*z^2 - 546*y^5*z + 120*y^5 -
137*y^4*z^2 + 288*y^4*z - 146*y^4 - 956*y^3*z^2 + 1088*y^3*z -
128*y^3 + 393*y^2*z^2 - 576*y^2*z + 186*y^2 + 498*y*z^2 - 540*y*z +
44*y - 220*z^2 + 288*z - 67,
y^10 - 6*y^9 + 12*y^8 - 8*y^7 + 288*y^5*z^2 - 348*y^5*z + 60*y^5 -
110*y^4*z^2 + 192*y^4*z - 82*y^4 - 624*y^3*z^2 + 696*y^3*z - 72*y^3 +
273*y^2*z^2 - 384*y^2*z + 111*y^2 + 322*y*z^2 - 348*y*z + 26*y -
150*z^2 + 192*z - 42,
y^6*z - y^6 - 6*y^5*z^2 + 6*y^5*z - 3*y^4*z + 3*y^4 + 12*y^3*z^2 -
12*y^3*z + 3*y^2*z - 3*y^2 - 6*y*z^2 + 6*y*z - z + 1,
z^3 - z^2
]
> R;
Ideal of Polynomial ring of rank 3 over Rational Field
Lexicographical Order
Variables: x, y, z
Dimension 0
Groebner basis:
[
x + 1,
y^2 - 2*y*z + z - 1,
z^2 - z
]
> I subset R;
true
> R subset I;
false
> IsInRadical(x + 1, I);
true
Given a sequence Q of k polynomials of a polynomial ring P over a ring R (not necessarily a field), return the relation ideal U of Q which is an ideal of the polynomial ring of rank k over R containing all algebraic relations between the elements of Q. That is, U consists of all polynomials r in R[y_1, ..., y_k] such that r(Q[1], ..., Q[k]) = 0. If U 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 be passed as a second argument.
> 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);
> 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);
> U := RelationIdeal(S, Q);
> U;
Ideal of Polynomial ring of rank 2 over GF(2)
Lexicographical Order
Variables: a, b
Basis:
[
a^6 + a + b^2 + 1
]
Finally, we check the algebraic expression, evaluating it at the
original polynomials:
> S[1]^6 + S[1] + S[2]^2; 1