# elimination of variables

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 Groebner basis using an elimination order which eliminates the variables s,t, and then select those Groebner 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.111059s (cpu); 0.111059s (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.120402s (cpu); 0.120401s (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.0479432s (cpu); 0.0479443s (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.442229s (cpu); 0.153415s (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.00117354s (cpu); 0.00117317s (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.0344167s (cpu); 0.0344222s (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!