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.
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 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ö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. The parameters are as for the Groebner procedure. Note that setting Walk := false 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 = 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.
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 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);
> 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);
> 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:
> S[1]^6 + S[1] + S[2]^2;
1