Elimination#
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.
Construction of Elimination Ideals#
- EliminationIdeal(I, k: parameters): RngMPol, RngIntElt -> RngMPol#
Given an ideal \(I\) of a polynomial ring \(P\) of rank \(n\) with \(P = R[x_1, \ldots, x_n]\), together with an integer \(k\) with \(0 \le k \le n\), return the \(k\)-th elimination ideal \(I_k\) of \(I\), which is defined to be \(I \cap R[x_{k+1}, \ldots, 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 \cap 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
Groebnerprocedure. Note that settingAl := "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 thegrevlexorder.
- EliminationIdeal(I, S): RngMPol, { RngIntElt } -> RngMPol#
- EliminationIdeal(I, S): RngMPol, { RngMPolElt } -> RngMPol#
Given an ideal \(I\) of a polynomial ring \(P\) of rank \(n\) with \(P = R[x_1, \ldots, x_n]\), together with a set \(S\) describing a subset \(U\) of the variables \(\lbrace x_1, \ldots x_n \rbrace\), return the elimination ideal \(I_U\) of \(I\), which is defined to be \(I \cap 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 \ldots 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.
- Example: Quadratic Order Elim (ex-0217ea)#
This example continues the example above which computed a Gröbner basis over a ring which was not even a PIR.
As before, \(R = {\mathbb{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 \({\mathbb{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 [Adams and Loustaunau, 1994, Ex. 4.3.8], the elimination ideal \(E_y = I \cap ({\mathbb{Z}}[\sqrt{-5})[y]\) is shown to be generated by \(f_5 = (5 + \sqrt{-5})y^2 - 15y\) and \(f_7 = -2\sqrt{-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; true
Finally, we also compute \(E_x = I \cap ({\mathbb{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 + 2\sqrt{-5})x^3 + (-5 + \sqrt{-5})x^2\) and \(12x^3 + 6\sqrt{-5}x^2\).
Univariate Elimination Ideal Generators#
- UnivariateEliminationIdealGenerator(I, i): RngMPol, RngIntElt -> RngMPolElt#
Given a zero-dimensional ideal \(I\) of a polynomial ring \(P\) of rank \(n\) with \(P = K[x_1, \ldots, x_n]\), together with an integer \(i\) with \(1 \le i \le n\), return the unique monic generator of the univariate elimination ideal \(I \cap K[x_{i}]\).
- UnivariateEliminationIdealGenerators(I): RngMPol -> [ RngMPolElt ]#
Given a zero-dimensional ideal \(I\) of a polynomial ring \(P\) of rank \(n\) with \(P = K[x_1, \ldots, x_n]\), return the sequence of length \(n\) whose \(i\)-th element is the unique monic generator of the univariate elimination ideal \(I \cap K[x_{i}]\).
- Example: Elimination Ideal (ex-09af2f)#
We construct an ideal \(I\) (derived from Neural networks theory) of the polynomial ring \({\mathbb{Q}}[x, y, z]\), and then find various elimination ideals of \(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 > 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 ]
- Example: Z Radical (ex-84cd6f)#
We write a simple function ZRadical to compute the radical of a zero dimensional ideal defined over a field using the univariate elimination ideal generators. See [Becker and Weispfenning, 1993, p. 345].
> 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 \({\mathbb{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
Relation Ideals#
- RelationIdeal(Q): [ RngMPol ] -> RngMPol#
- RelationIdeal(Q, T): [ RngMPol ], RngMPol -> RngMPol#
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 \in S[y_1, \ldots, y_k]\) such that \(r(Q[1], \ldots, 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 \(y_i\) and relations \(y_i - Q[i]\) are added and then the original variables \(x_i\) of \(P\) are eliminated in the usual way.
- Example: Relation Ideal (ex-d17522)#
We construct an ideal \(I\) of the polynomial ring \({\bf F}_{2}[x, y, z]\), and discover that the ideal is the full polynomial ring. Suppose we then wish to write \(1\in I\) as an (algebraic) expression in terms of the original generators. We use
RelationIdealto find that expression.> 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