Macaulay2 » Documentation
Packages » Macaulay2Doc > basic commutative algebra > Elementary uses of Groebner bases I. Math 634 Fall 2005
next | previous | forward | backward | up | index | toc

Elementary uses of Groebner bases I. Math 634 Fall 2005

-*- coding: utf-8 -*- In this tutorial we introduce a number of basic operations using Gröbner bases, and at the same time become familiar with a range of useful Macaulay2 constructs.

A. A first Gröbner basis

To compute the Gröbner basis of an ideal $(x^2y,xy^2+x^3)$ in the polynomial ring in four variables we proceed as follows:

Our favorite field

i1 : KK = ZZ/32003

o1 = KK

o1 : QuotientRing

The polynomial ring

i2 : R = KK[x,y,z,w]

o2 = R

o2 : PolynomialRing

and the ideal

i3 : I = ideal(x^2*y,x*y^2+x^3)

             2    3      2
o3 = ideal (x y, x  + x*y )

o3 : Ideal of R

now the punch line:

i4 : J = gens gb I

o4 = | x2y x3+xy2 xy3 |

             1      3
o4 : Matrix R  <-- R

This is the Gröbner basis of $I$ under the graded reverse lexicographic order. In Macaulay2, monomial orders are associated with a polynomial ring. For example, the lexicographic order is specified using:

i5 : R = KK[x,y,z,w,MonomialOrder=>Lex]

o5 = R

o5 : PolynomialRing
i6 : I = substitute(I,R)

             2    3      2
o6 = ideal (x y, x  + x*y )

o6 : Ideal of R
i7 : gens gb I

o7 = | xy3 x2y x3+xy2 |

             1      3
o7 : Matrix R  <-- R

The Gröbner basis is the same, since this is a small example. The polynomials are sorted in ascending monomial order by their lead terms, but otherwise the two Gröbner bases are the same here.

B. Random regular sequences

An interesting and illustrative open problem is to understand the initial ideal (and the Gröbner basis) of a ``generic'' regular sequence. To study a very simple case we take a matrix of 2 random forms in a polynomial ring in 3 variables:

i8 : R = KK[x,y,z]

o8 = R

o8 : PolynomialRing
i9 : F = random(R^1, R^{-2,-3})

o9 = | 107x2+4376xy+3187y2-5570xz+3783yz-5307z2
     ------------------------------------------------------------------------
     8570x3-15344x2y-10480xy2-8251y3+8444x2z+10359xyz+2653y2z-7464xz2+5071yz2
     ------------------------------------------------------------------------
     -6203z3 |

             1      2
o9 : Matrix R  <-- R

makes $F$ into a $1 \times 2$ matrix whose elements have degrees $2,3$ (that is, $F$ is a random map to the free module $R^1$, which has its one generator in the (default) degree, $0$, from the free module with generators in the listed degrees, $\{2,3\}$). We now can compute

i10 : GB = gens gb F

o10 = | x2-9231xy+3918y2+6528xz+11700yz-4536z2
      -----------------------------------------------------------------------
      xy2+10930y3+4639xyz+2060y2z+1339xz2+14261yz2+12812z3
      -----------------------------------------------------------------------
      y4-15921y3z+15391xyz2-3537y2z2-14321xz3+7226yz3-14465z4 |

              1      3
o10 : Matrix R  <-- R
i11 : LT = leadTerm GB

o11 = | x2 xy2 y4 |

              1      3
o11 : Matrix R  <-- R
i12 : betti LT

             0 1
o12 = total: 1 3
          0: 1 .
          1: . 1
          2: . 1
          3: . 1

o12 : BettiTally

betti is a routine that displays degrees of generators and also in free resolutions (which we will learn about later). In this case, the output shows that there are Gröbner basis elements of degrees 2,3, and 4. This result is dependent on the monomial order in the ring $R$; for example we could take the lexicographic order

i13 : R = KK[x,y,z, MonomialOrder => Lex]

o13 = R

o13 : PolynomialRing

(see help MonomialOrder for other possibilities). We get

i14 : F = random(R^1, R^{-2,-3})

o14 = | 12365x2-13508xy-9480xz-11950y2+8231yz+5864z2
      -----------------------------------------------------------------------
      5026x3+10259x2y-7501x2z+9534xy2-7216xyz-10125xz2+7256y3-5321y2z+6230yz2
      -----------------------------------------------------------------------
      +9033z3 |

              1      2
o14 : Matrix R  <-- R
i15 : GB = gens gb F

o15 = | y6+10526y5z-2376y4z2+5954y3z3+4992y2z4+12208yz5-83z6
      -----------------------------------------------------------------------
      xz4+9709y5-12534y4z+5436y3z2-12036y2z3+754yz4+9317z5
      -----------------------------------------------------------------------
      xyz2-904xz3+1531y4-7686y3z-14508y2z2+11404yz3-7z4
      -----------------------------------------------------------------------
      xy2+12914xyz+3687xz2+3377y3+2831y2z-15591yz2-13423z3
      -----------------------------------------------------------------------
      x2-5589xy-3676xz-1528y2-9542yz+10889z2 |

              1      5
o15 : Matrix R  <-- R
i16 : LT = leadTerm GB

o16 = | y6 xz4 xyz2 xy2 x2 |

              1      5
o16 : Matrix R  <-- R
i17 : betti LT

             0 1
o17 = total: 1 5
          0: 1 .
          1: . 1
          2: . 1
          3: . 1
          4: . 1
          5: . 1

o17 : BettiTally

and there are Gröbner basis elements of degrees $2,3,4,5,6.$

C. Division With Remainder

A major application of Gröbner bases is to decide whether an element is in a given ideal, and whether two elements reduce to the same thing modulo an ideal. For example, everyone knows that the trace of a nilpotent matrix is 0. We can produce an ideal $I$ that defines the variety $X$ of nilpotent $3 \times 3$ matrices by taking the cube of a generic matrix and setting the entries equal to zero. Here's how:

i18 : R = KK[a..i]

o18 = R

o18 : PolynomialRing
i19 : M = genericMatrix(R,a,3,3)

o19 = | a d g |
      | b e h |
      | c f i |

              3      3
o19 : Matrix R  <-- R
i20 : N = M^3

o20 = | a3+2abd+bde+2acg+bfg+cdh+cgi       
      | a2b+b2d+abe+be2+bcg+ach+ceh+bfh+chi
      | a2c+bcd+abf+bef+c2g+cfh+aci+bfi+ci2
      -----------------------------------------------------------------------
      a2d+bd2+ade+de2+cdg+afg+efg+dfh+fgi a2g+bdg+cg2+adh+deh+fgh+agi+dhi+gi2
      abd+2bde+e3+bfg+cdh+2efh+fhi        abg+beg+bdh+e2h+cgh+fh2+bgi+ehi+hi2
      acd+cde+bdf+e2f+cfg+f2h+cdi+efi+fi2 acg+bfg+cdh+efh+2cgi+2fhi+i3       
      -----------------------------------------------------------------------
      |
      |
      |

              3      3
o20 : Matrix R  <-- R
i21 : I = flatten N

o21 = | a3+2abd+bde+2acg+bfg+cdh+cgi a2b+b2d+abe+be2+bcg+ach+ceh+bfh+chi
      -----------------------------------------------------------------------
      a2c+bcd+abf+bef+c2g+cfh+aci+bfi+ci2 a2d+bd2+ade+de2+cdg+afg+efg+dfh+fgi
      -----------------------------------------------------------------------
      abd+2bde+e3+bfg+cdh+2efh+fhi acd+cde+bdf+e2f+cfg+f2h+cdi+efi+fi2
      -----------------------------------------------------------------------
      a2g+bdg+cg2+adh+deh+fgh+agi+dhi+gi2 abg+beg+bdh+e2h+cgh+fh2+bgi+ehi+hi2
      -----------------------------------------------------------------------
      acg+bfg+cdh+efh+2cgi+2fhi+i3 |

              1      9
o21 : Matrix R  <-- R

(actually this produces a 1 x 9 matrix of of forms, not the ideal: J = ideal I; the matrix will be more useful to us). But the trace is not in $I$! This is obvious from the fact that the trace has degree $1$, but the polynomials in $I$ are of degree $3$. We could also check by division with remainder:

i22 : Tr = trace M 

o22 = a + e + i

o22 : R
i23 : Tr //I  -- the quotient, which is 0

o23 = 0

              9      1
o23 : Matrix R  <-- R
i24 : Tr % I  -- the remainder, which is Tr again

o24 = a + e + i

o24 : R

(Here Tr is an element of $R$, not a matrix. We could do the same thing with a $1 \times 1$ matrix with Tr as its element.) This is of course because the entries of $I$ do NOT generate the ideal of all forms vanishing on $X$ -- this we may find with J = radical ideal I, (but this takes a while: see the documentation for radical on a faster way to find this) which shows that the radical is generated by the trace, the determinant, and the sum of the principal $2 \times 2$ minors, that is, by the coefficients of the characteristic polynomial. In particular, we can try the powers of the radical:

i25 : Tr^2 % I

       2           2                  2
o25 = a  + 2a*e + e  + 2a*i + 2e*i + i

o25 : R
i26 : Tr^3 % I

        2                 2     3                                2          
o26 = 3a e + 3b*d*e + 3a*e  + 3e  + 3b*f*g + 3c*d*h + 6e*f*h + 3a i + 6a*e*i
      -----------------------------------------------------------------------
          2                          2       2     3
      + 3e i + 3c*g*i + 6f*h*i + 3a*i  + 3e*i  + 3i

o26 : R
i27 : Tr^4 % I

        2 2         2       3     4                                   
o27 = 6a e  + 6b*d*e  + 6a*e  + 6e  + 6b*e*f*g + 6c*d*e*h - 6b*d*f*h +
      -----------------------------------------------------------------------
                    2                   2 2      2                       2   
      6a*e*f*h + 12e f*h - 6c*f*g*h - 6f h  + 12a e*i + 12b*d*e*i + 12a*e i +
      -----------------------------------------------------------------------
         3                                                               2 2
      12e i + 12c*e*g*i + 6b*f*g*i + 6c*d*h*i + 6a*f*h*i + 36e*f*h*i + 6a i 
      -----------------------------------------------------------------------
               2     2 2         2          2       3        3     4
      + 12a*e*i  + 6e i  + 6c*g*i  + 12f*h*i  + 6a*i  + 12e*i  + 6i

o27 : R
i28 : Tr^5 % I

         2 2           2         3       4         2         2       
o28 = 30a e i + 30b*d*e i + 30a*e i + 30e i + 30c*e g*i + 30a f*h*i +
      -----------------------------------------------------------------------
                                     2                         2 2   
      30b*d*f*h*i + 60a*e*f*h*i + 90e f*h*i + 30c*f*g*h*i + 30f h i +
      -----------------------------------------------------------------------
         2   2            2        2 2      3 2            2            2  
      30a e*i  + 30b*d*e*i  + 30a*e i  + 30e i  + 30c*e*g*i  + 60a*f*h*i  +
      -----------------------------------------------------------------------
                2      2 3          3          3      2 3          3  
      120e*f*h*i  + 30a i  + 30b*d*i  + 30a*e*i  + 30e i  + 30c*g*i  +
      -----------------------------------------------------------------------
             3        4        4      5
      90f*h*i  + 30a*i  + 30e*i  + 30i

o28 : R
i29 : Tr^6 % I

         2 2 2          2 2        3 2      4 2        2   2      2     2  
o29 = 90a e i  + 90b*d*e i  + 90a*e i  + 90e i  + 90c*e g*i  + 90a f*h*i  +
      -----------------------------------------------------------------------
                 2               2       2     2              2      2 2 2  
      90b*d*f*h*i  + 180a*e*f*h*i  + 270e f*h*i  + 90c*f*g*h*i  + 90f h i  +
      -----------------------------------------------------------------------
         2   3            3        2 3      3 3            3             3  
      90a e*i  + 90b*d*e*i  + 90a*e i  + 90e i  + 90c*e*g*i  + 180a*f*h*i  +
      -----------------------------------------------------------------------
                3      2 4          4          4      2 4          4  
      360e*f*h*i  + 90a i  + 90b*d*i  + 90a*e*i  + 90e i  + 90c*g*i  +
      -----------------------------------------------------------------------
              4        5        5      6
      270f*h*i  + 90a*i  + 90e*i  + 90i

o29 : R
i30 : Tr^7 % I

o30 = 0

o30 : R

The seventh power is the first one in the ideal! (Bernard Mourrain has worked out a formula for which power in general.) In this case

i31 : Tr^6 // I

o31 = {3} | a3+6a2e+3bde+15ae2+22e3+6efh+6a2i+30aei+60e2i+6fhi+15ai2+60ei2+22
      {3} | 0                                                                
      {3} | 0                                                                
      {3} | -27abe-45be2+9ceh+30bfh-72abi-144bei+75chi                       
      {3} | -2a3+15a2e+21bde+6ae2+e3+33bfg+9cdh-36afh+51efh+60a2i+72bdi+30aei
      {3} | 18abg+45beg+3a2h+9bdh-21aeh+3e2h+9cgh+36fh2+114bgi-135ahi-39ehi+3
      {3} | 18ace+6abf-36bef-18cfh+66aci+36cei-57bfi+132ci2                  
      {3} | -3a2f-39bdf+75aef-12e2f+9cfg-36f2h-66cdi+135afi+51efi+69fi2      
      {3} | -2a3-18abd-30a2e-60bde-30ae2-44e3-18ceg-33bfg-9cdh+18afh-93efh-75
      -----------------------------------------------------------------------
      i3                                                  |
                                                          |
                                                          |
                                                          |
      +6e2i+66cgi+147fhi-30ai2-75ei2-26i3                 |
      6hi2                                                |
                                                          |
                                                          |
      a2i-90bdi-60aei-75e2i-66cgi-171fhi-84ai2-84ei2-89i3 |

              9      1
o31 : Matrix R  <-- R

is not 0. It is a matrix that makes the following true:

i32 : Tr^6 == I * (Tr^6 // I) + (Tr^6 % I)

o32 = true

D. Elimination Theory

Computing the elimination ideal $I \cap k[xi, \ldots, xn]$ is one of the most important applications of Gröbner bases.

i33 : R = KK[t,y,z,MonomialOrder=>Lex]

o33 = R

o33 : PolynomialRing
i34 : I = ideal(y-(t^2+t+1), z-(t^3+1))

                2                 3
o34 = ideal (- t  - t + y - 1, - t  + z - 1)

o34 : Ideal of R
i35 : GB = gens gb I

o35 = | y3-3y2-3yz+6y-z2+4z-4 tz-2t-y2+3y+2z-4 ty-y-z+2 t2+t-y+1 |

              1      4
o35 : Matrix R  <-- R
i36 : F = GB_(0,0)

       3     2                2
o36 = y  - 3y  - 3y*z + 6y - z  + 4z - 4

o36 : R
i37 : substitute(F, {y =>t^2+t+1, z=>t^3+1})

o37 = 0

o37 : R

F is the polynomial that gives an algebraic relation between $t^2+t+1$ and $t^3+1$. Another way to accomplish this in Macaulay2 is to use the eliminate function. In this case, the monomial order of the ring is not important.

i38 : R = KK[y,z,t]

o38 = R

o38 : PolynomialRing
i39 : I = substitute(I,R)

                2                 3
o39 = ideal (- t  + y - t - 1, - t  + z - 1)

o39 : Ideal of R
i40 : eliminate(I,t)

             3     2           2
o40 = ideal(y  - 3y  - 3y*z - z  + 6y + 4z - 4)

o40 : Ideal of R

Yet another method is to use ring maps.

i41 : A = KK[t]

o41 = A

o41 : PolynomialRing
i42 : B = KK[y,z]

o42 = B

o42 : PolynomialRing
i43 : G = map(A,B,{t^2+t+1, t^3+1})

                   2           3
o43 = map (A, B, {t  + t + 1, t  + 1})

o43 : RingMap A <-- B
i44 : kernel G

             3     2           2
o44 = ideal(y  - 3y  - 3y*z - z  + 6y + 4z - 4)

o44 : Ideal of B

E. Intersections and ideal quotients

An interesting problem is to investigate ideals of the form $I = (x^d, y^d, z^d, f)$, where $f$ is a polynomial, in three variables $x,y,z$. First, let's compute the ideal quotient for an example, by using the method given in class.

i45 : R = KK[t,x,y,z]

o45 = R

o45 : PolynomialRing
i46 : I = ideal(x^3,y^3,z^3)

              3   3   3
o46 = ideal (x , y , z )

o46 : Ideal of R
i47 : F = x+y+z

o47 = x + y + z

o47 : R
i48 : L = t*I + (1-t)*ideal(F)

                3     3     3
o48 = ideal (t*x , t*y , t*z , - t*x - t*y - t*z + x + y + z)

o48 : Ideal of R
i49 : L1 = eliminate(L,t)

                3      3    4     3    4    3    3     4    3      3        3
o49 = ideal (x*z  + y*z  + z , x*y  + y  + y z, x y + y  - x z + 2y z - 2y*z 
      -----------------------------------------------------------------------
         4   4    4     3      3        3    4   3 2    3 2     2 3       4  
      - z , x  - y  + 2x z - 2y z + 2y*z  + z , x z  + y z  + 3y z  + 3y*z  +
      -----------------------------------------------------------------------
       5
      z )

o49 : Ideal of R
i50 : gens gb L1

o50 = | xz3+yz3+z4 xy3+y4+y3z x3y+y4-x3z+2y3z-2yz3-z4 x4-y4+2x3z-2y3z+2yz3+z4
      -----------------------------------------------------------------------
      x3z2+y3z2+3y2z3+3yz4+z5 |

              1      5
o50 : Matrix R  <-- R

Each of these is divisible by F:

i51 : (gens L1) % F

o51 = 0

              1      5
o51 : Matrix R  <-- R

Divide by F.

i52 : J = ideal ((gens L1)//F)

              3   3   2       2    3    2     2       2      2    3   3    2 
o52 = ideal (z , y , x y - x*y  + y  - x z + y z + x*z  - y*z  - z , x  - x y
      -----------------------------------------------------------------------
           2    3    2     2       2      2    3   2 2        2    2 2      3
      + x*y  - y  + x z - y z - x*z  + y*z  + z , x z  - x*y*z  + y z  - x*z 
      -----------------------------------------------------------------------
            3    4
      + 2y*z  + z )

o52 : Ideal of R
i53 : mingens J

o53 = | z3 y3 x2y-xy2-x2z+y2z+xz2-yz2 x3 x2z2-xyz2+y2z2 |

              1      5
o53 : Matrix R  <-- R
i54 : betti oo

             0 1
o54 = total: 1 5
          0: 1 .
          1: . .
          2: . 4
          3: . 1

o54 : BettiTally

J is defined by 5 equations: the original 3, another cubic and also a quartic. (oo is the previous output). Now, let's do this the easier way.

i55 : R = KK[x,y,z]

o55 = R

o55 : PolynomialRing
i56 : I = ideal(x^3,y^3,z^3)

              3   3   3
o56 = ideal (x , y , z )

o56 : Ideal of R
i57 : F = x+y+z

o57 = x + y + z

o57 : R
i58 : J = I : F

              3   3   2       2    2     2       2      2   3   2 2        2
o58 = ideal (z , y , x y - x*y  - x z + y z + x*z  - y*z , x , x z  - x*y*z 
      -----------------------------------------------------------------------
         2 2
      + y z )

o58 : Ideal of R
i59 : betti J

             0 1
o59 = total: 1 5
          0: 1 .
          1: . .
          2: . 4
          3: . 1

o59 : BettiTally
i60 : transpose gens J

o60 = {-3} | z3                      |
      {-3} | y3                      |
      {-3} | x2y-xy2-x2z+y2z+xz2-yz2 |
      {-3} | x3                      |
      {-4} | x2z2-xyz2+y2z2          |

              5      1
o60 : Matrix R  <-- R
i61 : transpose gens gb J

o61 = {-3} | z3                      |
      {-3} | y3                      |
      {-3} | x2y-xy2-x2z+y2z+xz2-yz2 |
      {-3} | x3                      |
      {-4} | x2z2-xyz2+y2z2          |

              5      1
o61 : Matrix R  <-- R

Problem: how many generators can you obtain using this construction, where you may try different positive integers $d$, and polynomials $f$?

F. Saturation

A very useful construction is the saturation of an ideal $I$ with respect to a polynomial $f$, or another ideal $J$.

i62 : R = KK[t,a..f]

o62 = R

o62 : PolynomialRing
i63 : I = ideal(a*b*c-d*e*f, a^2*b-c^2*d, a*f^2-d*b*c)

                             2     2                2
o63 = ideal (a*b*c - d*e*f, a b - c d, - b*c*d + a*f )

o63 : Ideal of R
i64 : F = a*b*c*d*e*f

o64 = a*b*c*d*e*f

o64 : R
i65 : J = eliminate(I + ideal(t*F-1), t)

              2     2            2              2   3                        
o65 = ideal (d e - a f, b*d*e - c f, b*c*d - a*f , c  - a*e*f, a*b*c - d*e*f,
      -----------------------------------------------------------------------
         2      2   2     2    3     4   2 2      3
      a*b  - c*f , a b - c d, b d - f , b c  - e*f )

o65 : Ideal of R
i66 : transpose gens J

o66 = {-3} | d2e-a2f  |
      {-3} | bde-c2f  |
      {-3} | bcd-af2  |
      {-3} | c3-aef   |
      {-3} | abc-def  |
      {-3} | ab2-cf2  |
      {-3} | a2b-c2d  |
      {-4} | b3d-f4   |
      {-4} | b2c2-ef3 |

              9      1
o66 : Matrix R  <-- R

There is a builtin routine in Macaulay2 for computing saturations:

i67 : R = KK[a..f]

o67 = R

o67 : PolynomialRing
i68 : I = substitute(I,R)

                             2     2                2
o68 = ideal (a*b*c - d*e*f, a b - c d, - b*c*d + a*f )

o68 : Ideal of R
i69 : F = product gens R

o69 = a*b*c*d*e*f

o69 : R
i70 : J' = saturate(I,F)

              2     2            2              2   3                        
o70 = ideal (d e - a f, b*d*e - c f, b*c*d - a*f , c  - a*e*f, a*b*c - d*e*f,
      -----------------------------------------------------------------------
         2      2   2     2    3     4   2 2      3
      a*b  - c*f , a b - c d, b d - f , b c  - e*f )

o70 : Ideal of R
i71 : transpose gens J'

o71 = {-3} | d2e-a2f  |
      {-3} | bde-c2f  |
      {-3} | bcd-af2  |
      {-3} | c3-aef   |
      {-3} | abc-def  |
      {-3} | ab2-cf2  |
      {-3} | a2b-c2d  |
      {-4} | b3d-f4   |
      {-4} | b2c2-ef3 |

              9      1
o71 : Matrix R  <-- R