next | previous | forward | backward | up | top | index | toc | Macaulay2 web site
Macaulay2Doc > elimination of variables

elimination of variables

Let’s consider the problem of finding the polynomial relation of the three polynomials x = s3+st+1, y = t3+3t2+t, and z = st3. 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.156271 seconds

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.168941 seconds

            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.0312366 seconds

             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] → 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.171464 seconds

             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.00190906 seconds

         9    9      7    3
o20 = x*t  - t  - z*t  - z

o20 : R
i21 : time f2 = resultant(I_1,f1,t)
     -- used 0.0769997 seconds

         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!

See also