# 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