Use elimination when you want equations involving only selected variables, for example to eliminate parameters from a parametrization. The main approaches are to use an elimination monomial order with
selectInSubring, call
eliminate, or construct a ring map and compute its
kernel(RingMap).
Let's consider the problem of finding the polynomial relation of the three polynomials $x = s^3+st+1$, $y = t^3+3t^2+t$, and $z = st^3$. The first method we use is to compute a Gröbner basis using an elimination order which eliminates the variables s,t, and then select those Gröbner basis elements that do not involve the variables s and t.
i1 : R = QQ[s,t,x,y,z, MonomialOrder=>Eliminate 2];
|
i2 : I = ideal(x-s^3-s*t-1, y-t^3-3*t^2-t, z-s*t^3)
3 3 2 3
o2 = ideal (- s - s*t + x - 1, - t - 3t - t + y, - s*t + z)
o2 : Ideal of R
|
i3 : time leadTerm gens gb I
-- used 0.231438s (cpu); 0.137371s (thread); 0s (gc)
o3 = | x3y9 5148txy3 108729sxy2z2 sy4z 46644741sxy3z 143sy5 6sxy4
------------------------------------------------------------------------
563515116021sx2y3 4374txy2z3 612704350498473090tx2yz3 217458ty4z2
------------------------------------------------------------------------
267076255345488270sy3z4 5256861933965245618410txyz6
------------------------------------------------------------------------
259806064190048723110954950tx2z6 281231296878799148310ty3z5
------------------------------------------------------------------------
178193459663956600213275sx2yz5 2019525876191508135750450sy2z7
------------------------------------------------------------------------
3470026149887950992631901569317758202349494375sx2z8 4004st 12012t2z
------------------------------------------------------------------------
3003s2z 9009t2x 14s2y3 t3 4004s3 |
1 25
o3 : Matrix R <-- R
|
i4 : G = selectInSubring(1,gens gb I)
o4 = | x3y9-3x2y9-6x2y8z-3x2y6z3+3xy9-x2y7z+12xy8z+7xy7z2-324x2y5z3+6xy6z3-
------------------------------------------------------------------------
y7z3-15xy5z4+3xy3z6-y9+2xy7z-6y8z-7y7z2-1233x2y4z3+648xy5z3-3y6z3+
------------------------------------------------------------------------
440xy4z4+15y5z4-70y4z5-405xy2z6-3y3z6+21y2z7-z9-y7z-945x2y3z3+2466xy4z3-
------------------------------------------------------------------------
324y5z3+1749xy3z4-440y4z4-252y3z5+3393xyz6+405y2z6-385yz7-252x2y2z3+
------------------------------------------------------------------------
1890xy3z3-1233y4z3+930xy2z4-1749y3z4-133y2z5-5778xz6-3393yz6+843z7-
------------------------------------------------------------------------
27x2yz3+504xy2z3-945y3z3+147xyz4-930y2z4-21yz5+5778z6-x2z3+54xyz3-
------------------------------------------------------------------------
252y2z3+7xz4-147yz4-z5+2xz3-27yz3-7z4-z3 |
1 1
o4 : Matrix R <-- R
|
i5 : ans1 = G_(0,0)
3 9 2 9 2 8 2 6 3 9 2 7 8 7 2
o5 = x y - 3x y - 6x y z - 3x y z + 3x*y - x y z + 12x*y z + 7x*y z -
------------------------------------------------------------------------
2 5 3 6 3 7 3 5 4 3 6 9 7 8
324x y z + 6x*y z - y z - 15x*y z + 3x*y z - y + 2x*y z - 6y z -
------------------------------------------------------------------------
7 2 2 4 3 5 3 6 3 4 4 5 4 4 5
7y z - 1233x y z + 648x*y z - 3y z + 440x*y z + 15y z - 70y z -
------------------------------------------------------------------------
2 6 3 6 2 7 9 7 2 3 3 4 3 5 3
405x*y z - 3y z + 21y z - z - y z - 945x y z + 2466x*y z - 324y z
------------------------------------------------------------------------
3 4 4 4 3 5 6 2 6 7
+ 1749x*y z - 440y z - 252y z + 3393x*y*z + 405y z - 385y*z -
------------------------------------------------------------------------
2 2 3 3 3 4 3 2 4 3 4 2 5
252x y z + 1890x*y z - 1233y z + 930x*y z - 1749y z - 133y z -
------------------------------------------------------------------------
6 6 7 2 3 2 3 3 3 4
5778x*z - 3393y*z + 843z - 27x y*z + 504x*y z - 945y z + 147x*y*z
------------------------------------------------------------------------
2 4 5 6 2 3 3 2 3 4
- 930y z - 21y*z + 5778z - x z + 54x*y*z - 252y z + 7x*z -
------------------------------------------------------------------------
4 5 3 3 4 3
147y*z - z + 2x*z - 27y*z - 7z - z
o5 : R
|
This method (with some optimizations incorporated) is provided by the
eliminate function.
i6 : R = QQ[x,y,z,s,t];
|
i7 : I = ideal(x-s^3-s*t-1, y-t^3-3*t^2-t, z-s*t^3)
3 3 2 3
o7 = ideal (- s - s*t + x - 1, - t - 3t + y - t, - s*t + z)
o7 : Ideal of R
|
i8 : time G = eliminate(I,{s,t})
-- used 0.22861s (cpu); 0.134108s (thread); 0s (gc)
3 9 2 9 2 8 2 6 3 9 2 7 8
o8 = ideal(x y - 3x y - 6x y z - 3x y z + 3x*y - x y z + 12x*y z +
------------------------------------------------------------------------
7 2 2 5 3 6 3 7 3 5 4 3 6 9 7
7x*y z - 324x y z + 6x*y z - y z - 15x*y z + 3x*y z - y + 2x*y z
------------------------------------------------------------------------
8 7 2 2 4 3 5 3 6 3 4 4 5 4
- 6y z - 7y z - 1233x y z + 648x*y z - 3y z + 440x*y z + 15y z -
------------------------------------------------------------------------
4 5 2 6 3 6 2 7 9 7 2 3 3 4 3
70y z - 405x*y z - 3y z + 21y z - z - y z - 945x y z + 2466x*y z
------------------------------------------------------------------------
5 3 3 4 4 4 3 5 6 2 6
- 324y z + 1749x*y z - 440y z - 252y z + 3393x*y*z + 405y z -
------------------------------------------------------------------------
7 2 2 3 3 3 4 3 2 4 3 4
385y*z - 252x y z + 1890x*y z - 1233y z + 930x*y z - 1749y z -
------------------------------------------------------------------------
2 5 6 6 7 2 3 2 3 3 3
133y z - 5778x*z - 3393y*z + 843z - 27x y*z + 504x*y z - 945y z +
------------------------------------------------------------------------
4 2 4 5 6 2 3 3 2 3
147x*y*z - 930y z - 21y*z + 5778z - x z + 54x*y*z - 252y z +
------------------------------------------------------------------------
4 4 5 3 3 4 3
7x*z - 147y*z - z + 2x*z - 27y*z - 7z - z )
o8 : Ideal of R
|
i9 : ans2 = G_0
3 9 2 9 2 8 2 6 3 9 2 7 8 7 2
o9 = x y - 3x y - 6x y z - 3x y z + 3x*y - x y z + 12x*y z + 7x*y z -
------------------------------------------------------------------------
2 5 3 6 3 7 3 5 4 3 6 9 7 8
324x y z + 6x*y z - y z - 15x*y z + 3x*y z - y + 2x*y z - 6y z -
------------------------------------------------------------------------
7 2 2 4 3 5 3 6 3 4 4 5 4 4 5
7y z - 1233x y z + 648x*y z - 3y z + 440x*y z + 15y z - 70y z -
------------------------------------------------------------------------
2 6 3 6 2 7 9 7 2 3 3 4 3 5 3
405x*y z - 3y z + 21y z - z - y z - 945x y z + 2466x*y z - 324y z
------------------------------------------------------------------------
3 4 4 4 3 5 6 2 6 7
+ 1749x*y z - 440y z - 252y z + 3393x*y*z + 405y z - 385y*z -
------------------------------------------------------------------------
2 2 3 3 3 4 3 2 4 3 4 2 5
252x y z + 1890x*y z - 1233y z + 930x*y z - 1749y z - 133y z -
------------------------------------------------------------------------
6 6 7 2 3 2 3 3 3 4
5778x*z - 3393y*z + 843z - 27x y*z + 504x*y z - 945y z + 147x*y*z
------------------------------------------------------------------------
2 4 5 6 2 3 3 2 3 4
- 930y z - 21y*z + 5778z - x z + 54x*y*z - 252y z + 7x*z -
------------------------------------------------------------------------
4 5 3 3 4 3
147y*z - z + 2x*z - 27y*z - 7z - z
o9 : R
|
Sometimes giving the variables different degrees will speed up the computations. Here, we set the degrees of x, y, and z to be the total degrees.
i10 : R1 = QQ[x,y,z,s,t, Degrees=>{3,3,4,1,1}];
|
i11 : I1 = substitute(I,R1);
o11 : Ideal of R1
|
i12 : time G = eliminate(I1,{s,t})
-- used 0.168404s (cpu); 0.0744937s (thread); 0s (gc)
3 9 2 6 3 3 6 9 2 8 5 4 2 7
o12 = ideal(x y - 3x y z + 3x*y z - z - 6x y z - 15x*y z + 21y z -
-----------------------------------------------------------------------
2 9 2 5 3 6 3 7 3 2 6 3 6 7 2
3x y - 324x y z + 6x*y z - y z - 405x*y z - 3y z + 7x*y z -
-----------------------------------------------------------------------
4 5 2 7 8 4 4 5 4 7 9
70y z - x y z + 12x*y z + 440x*y z + 15y z - 385y*z + 3x*y -
-----------------------------------------------------------------------
2 4 3 5 3 6 3 6 2 6 7 2 3 5
1233x y z + 648x*y z - 3y z + 3393x*y*z + 405y z - 7y z - 252y z
-----------------------------------------------------------------------
7 8 3 4 4 4 7 9 2 3 3
+ 2x*y z - 6y z + 1749x*y z - 440y z + 843z - y - 945x y z +
-----------------------------------------------------------------------
4 3 5 3 6 6 2 5 7 2 4
2466x*y z - 324y z - 5778x*z - 3393y*z - 133y z - y z + 930x*y z
-----------------------------------------------------------------------
3 4 2 2 3 3 3 4 3 6 5
- 1749y z - 252x y z + 1890x*y z - 1233y z + 5778z - 21y*z +
-----------------------------------------------------------------------
4 2 4 2 3 2 3 3 3 5 4
147x*y*z - 930y z - 27x y*z + 504x*y z - 945y z - z + 7x*z -
-----------------------------------------------------------------------
4 2 3 3 2 3 4 3 3 3
147y*z - x z + 54x*y*z - 252y z - 7z + 2x*z - 27y*z - z )
o12 : Ideal of R1
|
i13 : ans3 = G_0
3 9 2 6 3 3 6 9 2 8 5 4 2 7 2 9
o13 = x y - 3x y z + 3x*y z - z - 6x y z - 15x*y z + 21y z - 3x y -
-----------------------------------------------------------------------
2 5 3 6 3 7 3 2 6 3 6 7 2 4 5
324x y z + 6x*y z - y z - 405x*y z - 3y z + 7x*y z - 70y z -
-----------------------------------------------------------------------
2 7 8 4 4 5 4 7 9 2 4 3
x y z + 12x*y z + 440x*y z + 15y z - 385y*z + 3x*y - 1233x y z +
-----------------------------------------------------------------------
5 3 6 3 6 2 6 7 2 3 5 7
648x*y z - 3y z + 3393x*y*z + 405y z - 7y z - 252y z + 2x*y z -
-----------------------------------------------------------------------
8 3 4 4 4 7 9 2 3 3 4 3
6y z + 1749x*y z - 440y z + 843z - y - 945x y z + 2466x*y z -
-----------------------------------------------------------------------
5 3 6 6 2 5 7 2 4 3 4
324y z - 5778x*z - 3393y*z - 133y z - y z + 930x*y z - 1749y z -
-----------------------------------------------------------------------
2 2 3 3 3 4 3 6 5 4
252x y z + 1890x*y z - 1233y z + 5778z - 21y*z + 147x*y*z -
-----------------------------------------------------------------------
2 4 2 3 2 3 3 3 5 4 4 2 3
930y z - 27x y*z + 504x*y z - 945y z - z + 7x*z - 147y*z - x z
-----------------------------------------------------------------------
3 2 3 4 3 3 3
+ 54x*y*z - 252y z - 7z + 2x*z - 27y*z - z
o13 : R1
|
Another approach is to create the ring map $F : k[x,y,z] \rightarrow{} k[s,t]$, and find its kernel.
i14 : A = QQ[s,t];
|
i15 : B = QQ[x,y,z];
|
i16 : F = map(A,B,{s^3+s*t+1, t^3+3*t^2+t, s*t^3})
3 3 2 3
o16 = map (A, B, {s + s*t + 1, t + 3t + t, s*t })
o16 : RingMap A <-- B
|
i17 : time G = kernel F
-- used 0.23094s (cpu); 0.137664s (thread); 0s (gc)
3 9 2 9 2 8 2 6 3 9 2 7 8
o17 = ideal(x y - 3x y - 6x y z - 3x y z + 3x*y - x y z + 12x*y z +
-----------------------------------------------------------------------
7 2 2 5 3 6 3 7 3 5 4 3 6 9 7
7x*y z - 324x y z + 6x*y z - y z - 15x*y z + 3x*y z - y + 2x*y z
-----------------------------------------------------------------------
8 7 2 2 4 3 5 3 6 3 4 4 5 4
- 6y z - 7y z - 1233x y z + 648x*y z - 3y z + 440x*y z + 15y z -
-----------------------------------------------------------------------
4 5 2 6 3 6 2 7 9 7 2 3 3 4 3
70y z - 405x*y z - 3y z + 21y z - z - y z - 945x y z + 2466x*y z
-----------------------------------------------------------------------
5 3 3 4 4 4 3 5 6 2 6
- 324y z + 1749x*y z - 440y z - 252y z + 3393x*y*z + 405y z -
-----------------------------------------------------------------------
7 2 2 3 3 3 4 3 2 4 3 4
385y*z - 252x y z + 1890x*y z - 1233y z + 930x*y z - 1749y z -
-----------------------------------------------------------------------
2 5 6 6 7 2 3 2 3 3 3
133y z - 5778x*z - 3393y*z + 843z - 27x y*z + 504x*y z - 945y z
-----------------------------------------------------------------------
4 2 4 5 6 2 3 3 2 3
+ 147x*y*z - 930y z - 21y*z + 5778z - x z + 54x*y*z - 252y z +
-----------------------------------------------------------------------
4 4 5 3 3 4 3
7x*z - 147y*z - z + 2x*z - 27y*z - 7z - z )
o17 : Ideal of B
|
i18 : ans4 = G_0
3 9 2 9 2 8 2 6 3 9 2 7 8 7 2
o18 = x y - 3x y - 6x y z - 3x y z + 3x*y - x y z + 12x*y z + 7x*y z -
-----------------------------------------------------------------------
2 5 3 6 3 7 3 5 4 3 6 9 7 8
324x y z + 6x*y z - y z - 15x*y z + 3x*y z - y + 2x*y z - 6y z -
-----------------------------------------------------------------------
7 2 2 4 3 5 3 6 3 4 4 5 4 4 5
7y z - 1233x y z + 648x*y z - 3y z + 440x*y z + 15y z - 70y z -
-----------------------------------------------------------------------
2 6 3 6 2 7 9 7 2 3 3 4 3
405x*y z - 3y z + 21y z - z - y z - 945x y z + 2466x*y z -
-----------------------------------------------------------------------
5 3 3 4 4 4 3 5 6 2 6
324y z + 1749x*y z - 440y z - 252y z + 3393x*y*z + 405y z -
-----------------------------------------------------------------------
7 2 2 3 3 3 4 3 2 4 3 4
385y*z - 252x y z + 1890x*y z - 1233y z + 930x*y z - 1749y z -
-----------------------------------------------------------------------
2 5 6 6 7 2 3 2 3 3 3
133y z - 5778x*z - 3393y*z + 843z - 27x y*z + 504x*y z - 945y z
-----------------------------------------------------------------------
4 2 4 5 6 2 3 3 2 3
+ 147x*y*z - 930y z - 21y*z + 5778z - x z + 54x*y*z - 252y z +
-----------------------------------------------------------------------
4 4 5 3 3 4 3
7x*z - 147y*z - z + 2x*z - 27y*z - 7z - z
o18 : B
|
This appears to be much faster than the first two methods.
Finally, we may use resultants to find elements of the ideal I which do not involve the variables s and t.
i19 : use ring I
o19 = R
o19 : PolynomialRing
|
i20 : time f1 = resultant(I_0,I_2,s)
-- used 0.00136849s (cpu); 0.0013689s (thread); 0s (gc)
9 9 7 3
o20 = x*t - t - z*t - z
o20 : R
|
i21 : time f2 = resultant(I_1,f1,t)
-- used 0.0298622s (cpu); 0.0298675s (thread); 0s (gc)
3 9 2 9 2 8 2 6 3 9 2 7 8 7 2
o21 = - x y + 3x y + 6x y z + 3x y z - 3x*y + x y z - 12x*y z - 7x*y z +
-----------------------------------------------------------------------
2 5 3 6 3 7 3 5 4 3 6 9 7 8
324x y z - 6x*y z + y z + 15x*y z - 3x*y z + y - 2x*y z + 6y z +
-----------------------------------------------------------------------
7 2 2 4 3 5 3 6 3 4 4 5 4 4 5
7y z + 1233x y z - 648x*y z + 3y z - 440x*y z - 15y z + 70y z +
-----------------------------------------------------------------------
2 6 3 6 2 7 9 7 2 3 3 4 3
405x*y z + 3y z - 21y z + z + y z + 945x y z - 2466x*y z +
-----------------------------------------------------------------------
5 3 3 4 4 4 3 5 6 2 6
324y z - 1749x*y z + 440y z + 252y z - 3393x*y*z - 405y z +
-----------------------------------------------------------------------
7 2 2 3 3 3 4 3 2 4 3 4
385y*z + 252x y z - 1890x*y z + 1233y z - 930x*y z + 1749y z +
-----------------------------------------------------------------------
2 5 6 6 7 2 3 2 3 3 3
133y z + 5778x*z + 3393y*z - 843z + 27x y*z - 504x*y z + 945y z
-----------------------------------------------------------------------
4 2 4 5 6 2 3 3 2 3
- 147x*y*z + 930y z + 21y*z - 5778z + x z - 54x*y*z + 252y z -
-----------------------------------------------------------------------
4 4 5 3 3 4 3
7x*z + 147y*z + z - 2x*z + 27y*z + 7z + z
o21 : R
|
i22 : ans5 = -f2
3 9 2 9 2 8 2 6 3 9 2 7 8 7 2
o22 = x y - 3x y - 6x y z - 3x y z + 3x*y - x y z + 12x*y z + 7x*y z -
-----------------------------------------------------------------------
2 5 3 6 3 7 3 5 4 3 6 9 7 8
324x y z + 6x*y z - y z - 15x*y z + 3x*y z - y + 2x*y z - 6y z -
-----------------------------------------------------------------------
7 2 2 4 3 5 3 6 3 4 4 5 4 4 5
7y z - 1233x y z + 648x*y z - 3y z + 440x*y z + 15y z - 70y z -
-----------------------------------------------------------------------
2 6 3 6 2 7 9 7 2 3 3 4 3
405x*y z - 3y z + 21y z - z - y z - 945x y z + 2466x*y z -
-----------------------------------------------------------------------
5 3 3 4 4 4 3 5 6 2 6
324y z + 1749x*y z - 440y z - 252y z + 3393x*y*z + 405y z -
-----------------------------------------------------------------------
7 2 2 3 3 3 4 3 2 4 3 4
385y*z - 252x y z + 1890x*y z - 1233y z + 930x*y z - 1749y z -
-----------------------------------------------------------------------
2 5 6 6 7 2 3 2 3 3 3
133y z - 5778x*z - 3393y*z + 843z - 27x y*z + 504x*y z - 945y z
-----------------------------------------------------------------------
4 2 4 5 6 2 3 3 2 3
+ 147x*y*z - 930y z - 21y*z + 5778z - x z + 54x*y*z - 252y z +
-----------------------------------------------------------------------
4 4 5 3 3 4 3
7x*z - 147y*z - z + 2x*z - 27y*z - 7z - z
o22 : R
|
This is the fastest method in this case.
These answers should all be the same (with the possible exception of the last), but are they? They live in different rings, so we cannot compare them directly. Instead, let's move them to the ring B, and then remove duplicates.
i23 : L = {ans1,ans2,ans3,ans4,ans5};
|
i24 : L = apply(L, f -> substitute(f,B));
|
i25 : length unique L
o25 = 1
|
They are all the same!