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. Elimination of variables is accomplished by computing a Gröbner basis with respect to a suitable elimination order (for more information about elimination orders, see Section Representation and Monomial Orders as well as comments in the function descriptions below).
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[x1, ..., xn], together with an integer k with 0 ≤k ≤n, return the k-th elimination ideal Ik of I, which is defined to be I ∩R[xk + 1, ..., xn]. Thus Ik consists of all polynomials of I which have the first k variables eliminated. If the elimination ideals Ik 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 ∩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[x1, ..., xn], together with a set S describing a subset U of the variables { x1, ... xn }, return the elimination ideal IU of I, which is defined to be I ∩R[U]. Thus IU 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 xi, 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 f1 = 2xy + Sqrt( - 5)y and f2 = (1 + Sqrt( - 5))x2 - xy. As before, we compute over Z, introduce a new variable S and include (S2 + 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
Ey = I ∩(Z[Sqrt( - 5))[y] is shown to be generated by
f5 = (5 + Sqrt( - 5))y2 - 15y and
f7 = - 2Sqrt( - 5)y2 + 5(1 + Sqrt( - 5))y.
We can compute Ey 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 f5 and f7 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 Ex = I ∩(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 Ex is generated by
(2 + 2Sqrt( - 5))x3 + ( - 5 + Sqrt( - 5))x2 and
12x3 + 6Sqrt( - 5)x2.
Given a zero-dimensional ideal I of a polynomial ring P of rank n with P = K[x1, ..., xn], together with an integer i with 1 ≤i ≤n, return the unique monic generator of the univariate elimination ideal I ∩K[xi].
Given a zero-dimensional ideal I of a polynomial ring P of rank n with P = K[x1, ..., xn], return the sequence of length n whose i-th element is the unique monic generator of the univariate elimination ideal I ∩K[xi].
> 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
> E := EliminationIdeal(I, {y, z});
> E;
Ideal of Polynomial ring of rank 3 over Rational Field
Order: Lexicographical
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,
y + 141944208/7806653*z^20 - 42803108/7806653*z^19 - 290535348/7806653*z^18
+ 309392460/7806653*z^17 - 164881460/7806653*z^16 -
331099258/7806653*z^15 + 203830442/7806653*z^14 - 894960798/7806653*z^13
+ 622205873/7806653*z^12 + 1352184655/31226612*z^11 -
4746138097/31226612*z^10 + 5122044359/31226612*z^9 +
991547639/31226612*z^8 - 830598655/7806653*z^7 + 1472712995/15613306*z^6
- 59983627/15613306*z^5 - 486698319/15613306*z^4 + 174173263/7806653*z^3
- 30672252/7806653*z^2 - 735083/664396*z + 30093391/31226612
]
> 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
Order: Lexicographical
Variables: x, y, z
Inhomogeneous, Dimension 0, Non-radical
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
Order: Lexicographical
Variables: x, y, z
Inhomogeneous, Dimension 0, Radical
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 S (not necessarily a field), return the relation ideal U of Q which is an ideal of the polynomial ring of rank k over S containing all algebraic relations between the elements of Q. That is, U consists of all polynomials r ∈S[y1, ..., yk] such that r(Q[1], ..., Q[k]) = 0. If U is desired to be an ideal of a particular polynomial ring T of rank k (to obtain predetermined names of variables, for example), then T may be passed as a second argument.The computation is the same as that for the image of an affine polynomial map, which this basically is, thinking of the polynomials in Q as giving a map from n-dimensional affine space (n = rank of P) to k-dimensional affine space. k new variables yi and relations yi - Q[i] are added and then the original variables xi of P are eliminated in the usual way.
> 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)
Order: Lexicographical
Variables: a, b
Inhomogeneous, Dimension >0
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