-*- 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
|