<?xml version="1.0" encoding="utf-8" ?> <!-- for emacs: -*- coding: utf-8 -*- -->
<!-- Apache may like this line in the file .htaccess: AddCharset utf-8 .html -->
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1 plus MathML 2.0 plus SVG 1.1//EN" "http://www.w3.org/2002/04/xhtml-math-svg/xhtml-math-svg-flat.dtd" >
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head><title>Tutorial: Elementary uses of Groebner bases</title>
<link rel="stylesheet" type="text/css" href="../../../../Macaulay2/Style/doc.css"/>
</head>
<body>
<table class="buttons">
<tr>
<td><div><a href="___Tutorial_co_sp__Canonical_sp__Embeddings_spof_sp__Plane_sp__Curves_spand_sp__Gonality.html">next</a> | <a href="_mathematical_spexamples.html">previous</a> | <a href="___Tutorial_co_sp__Canonical_sp__Embeddings_spof_sp__Plane_sp__Curves_spand_sp__Gonality.html">forward</a> | backward | <a href="_mathematical_spexamples.html">up</a> | <a href="index.html">top</a> | <a href="master.html">index</a> | <a href="toc.html">toc</a> | <a href="http://www.math.uiuc.edu/Macaulay2/">Macaulay2 web site</a></div>
</td>
</tr>
</table>
<div><a href="index.html" title="">Macaulay2Doc</a> > <a href="_mathematical_spexamples.html" title="">mathematical examples</a> > <a href="___Tutorial_co_sp__Elementary_spuses_spof_sp__Groebner_spbases.html" title="">Tutorial: Elementary uses of Groebner bases</a></div>
<hr/>
<div><h1>Tutorial: Elementary uses of Groebner bases</h1>
<div>-*- 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. The sections are:<p/>
A. First steps; example with a monomial curve<p/>
B. Random regular sequences<p/>
C. Division with remainder<p/>
D. Elimination theory<p/>
E. Quotients and saturation<h4>A. First Steps; example with a monomial curve</h4>
To compute the Gröbner basis of an ideal <i>(x<sup>2</sup>y,xy<sup>2</sup>+x<sup>3</sup>)</i> in the polynomial ring in four variables we proceed as follows:<p/>
Our favorite field<table class="examples"><tr><td><pre>i1 : KK = ZZ/31991
o1 = KK
o1 : QuotientRing</pre>
</td></tr>
</table>
The polynomial ring<table class="examples"><tr><td><pre>i2 : R = KK[x,y,z,w]
o2 = R
o2 : PolynomialRing</pre>
</td></tr>
</table>
and the ideal<table class="examples"><tr><td><pre>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</pre>
</td></tr>
</table>
now the punch line:<table class="examples"><tr><td><pre>i4 : J = gens gb I
o4 = | x2y x3+xy2 xy3 |
1 3
o4 : Matrix R <--- R</pre>
</td></tr>
</table>
From this we can for example compute the codimension, dimension, degree, and the whole Hilbert function and polynomial. This will be more fun if we work with an example having some meaning. We choose to work with the ideal defining the rational quartic curve in <i><b>P</b><sup>3</sup></i> given parametrically in an affine representation by <p align=center><i>t → (t,t<sup>3</sup>,t<sup>4</sup>).</i></p> (The reader who doesn’t understand this terminology may ignore it for the moment, and treat the ideal given below as a gift from the gods... .) We obtain the ideal by first making the polynomial ring in 4 variables (the homogeneous coordinate ring of <i><b>P</b><sup>3</sup></i>)<table class="examples"><tr><td><pre>i5 : R = KK[a..d]
o5 = R
o5 : PolynomialRing</pre>
</td></tr>
</table>
and then using a function <tt>monomialCurveIdeal</tt>, which we shall treat for now as a black box<table class="examples"><tr><td><pre>i6 : I = monomialCurveIdeal(R,{1,3,4})
3 2 2 2 3 2
o6 = ideal (b*c - a*d, c - b*d , a*c - b d, b - a c)
o6 : Ideal of R</pre>
</td></tr>
</table>
From Macaulay2’s point of view, <i>I</i> is an ideal, and the codimension of its support is 2, while its dimension is 2:<table class="examples"><tr><td><pre>i7 : codim I
o7 = 2</pre>
</td></tr>
<tr><td><pre>i8 : dim I
o8 = 2</pre>
</td></tr>
</table>
This is the codimension of <i>R/I</i> in <i>R</i> and the dimension of <i>R/I</i>. We could work with the module <i>R/I</i> as well. Precision requires writing <i>R<sup>1</sup></i> instead of <i>R</i> (<i>R</i> is a ring, and <i>R<sup>1</sup></i> is the free module of rank 1 over it)<table class="examples"><tr><td><pre>i9 : codim (R^1/(I*R^1))
o9 = 2</pre>
</td></tr>
</table>
We could also extract the generators of <i>I</i> (as a matrix) and take the cokernel to get the same thing:<table class="examples"><tr><td><pre>i10 : M = coker gens I
o10 = cokernel | bc-ad c3-bd2 ac2-b2d b3-a2c |
1
o10 : R-module, quotient of R</pre>
</td></tr>
<tr><td><pre>i11 : codim M
o11 = 2</pre>
</td></tr>
<tr><td><pre>i12 : dim M
o12 = 2</pre>
</td></tr>
</table>
And similarly for the degree:<table class="examples"><tr><td><pre>i13 : degree I
o13 = 4</pre>
</td></tr>
<tr><td><pre>i14 : degree M
o14 = 4</pre>
</td></tr>
</table>
As one might expect, the degree of the quartic is 4 ! The Hilbert polynomial is obtained by<table class="examples"><tr><td><pre>i15 : hilbertPolynomial M
o15 = - 3*P + 4*P
0 1
o15 : ProjectiveHilbertPolynomial</pre>
</td></tr>
</table>
The term <i><b>P</b><sup>i</sup></i> represents the Hilbert polynomial of projective <i>i</i>-space. This formula tells us that the Hilbert polynomial of <i>M</i> is <i>H(m) = 4(m+1) - 3 = 4m + 1</i>. Thus the degree is four, the dimension of the projective variety which is the support of <i>M</i> is 1 (and so the affine dimension is 2), and that the (arithmetic) genus is 0 (1 minus the constant term, for curves).<p/>
The Hilbert series of <i>M</i> (the generating function for the dimensions of the graded pieces of <i>M</i>) is<table class="examples"><tr><td><pre>i16 : hilbertSeries M
2 3 4 5
1 - T - 3T + 4T - T
o16 = -----------------------
4
(1 - T)
o16 : Expression of class Divide</pre>
</td></tr>
</table>
The indeterminate in this expression is $T.<p/>
Another way to get information about the module <i>M</i> is to see its free resolution<table class="examples"><tr><td><pre>i17 : Mres = res M
1 4 4 1
o17 = R <-- R <-- R <-- R <-- 0
0 1 2 3 4
o17 : ChainComplex</pre>
</td></tr>
</table>
To get more precise information about <tt>Mres</tt>, we could do<table class="examples"><tr><td><pre>i18 : betti Mres
0 1 2 3
o18 = total: 1 4 4 1
0: 1 . . .
1: . 1 . .
2: . 3 4 1
o18 : BettiTally</pre>
</td></tr>
</table>
The display is chosen for compactness: B total: 1 4 4 1 B 0: 1 . . . B 1: . 1 . . B 2: . 3 4 1 the first line gives the total betti numbers, the same information given when we type the resolution. The remaining lines express the degrees of each of the generators of the free modules in the resolution. The <i>j</i>th column after the colons gives the degrees of generators of the <i>j</i>th module(counting from <i>0</i>); an <i>n</i> in the <i>j</i>th column in the row headed by “<i>d</i>:” means that the <i>j</i>th free module has <i>n</i> generators of degree <i>n+j</i>. Thus for example in our case, the generator of the third (last) free module in the resolution has degree <i>3+2=5</i>.<h4>B. Random regular sequences</h4>
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:<table class="examples"><tr><td><pre>i19 : R = KK[x,y,z]
o19 = R
o19 : PolynomialRing</pre>
</td></tr>
<tr><td><pre>i20 : F = random(R^1, R^{-2,-3})
o20 = | 305x2-8319xy+14216y2+4825xz+1360yz-7636z2
-----------------------------------------------------------------------
-11783x3+4017x2y+1915xy2-13519y3-6295x2z-14966xyz-3634y2z-9977xz2-
-----------------------------------------------------------------------
8554yz2-1894z3 |
1 2
o20 : Matrix R <--- R</pre>
</td></tr>
</table>
makes <i>F</i> into a <i>1 ×2</i> matrix whose elements have degrees <i>2,3</i> (that is, <i>F</i> is a random map to the free module <i>R<sup>1</sup></i>, which has its one generator in the (default) degree, <i>0</i>, from the free module with generators in the listed degrees, <i>{2,3}</i>). We now can compute<table class="examples"><tr><td><pre>i21 : GB = gens gb F
o21 = | x2-15341xy+15675y2+12078xz+4200yz-10409z2
-----------------------------------------------------------------------
xy2+5163y3+7367xyz-2253y2z-7818xz2-10970yz2-15144z3
-----------------------------------------------------------------------
y4+2900y3z-13269xyz2-9273y2z2+11675xz3-3549yz3+1498z4 |
1 3
o21 : Matrix R <--- R</pre>
</td></tr>
<tr><td><pre>i22 : LT = leadTerm gens gb F
o22 = | x2 xy2 y4 |
1 3
o22 : Matrix R <--- R</pre>
</td></tr>
<tr><td><pre>i23 : betti LT
0 1
o23 = total: 1 3
0: 1 .
1: . 1
2: . 1
3: . 1
o23 : BettiTally</pre>
</td></tr>
</table>
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 <i>R</i>; for example we could take the lexicographic order<table class="examples"><tr><td><pre>i24 : R = KK[x,y,z, MonomialOrder => Lex]
o24 = R
o24 : PolynomialRing</pre>
</td></tr>
</table>
(see <tt>help MonomialOrder</tt> for other possibilities). We get <table class="examples"><tr><td><pre>i25 : F = random(R^1, R^{-2,-3})
o25 = | -4743x2-15027xy-2999xz-1334y2-12991yz+7321z2
-----------------------------------------------------------------------
-1568x3-9457x2y-6588x2z+376xy2-12945xyz-6735xz2-2368y3-2846y2z+5916yz2+
-----------------------------------------------------------------------
4396z3 |
1 2
o25 : Matrix R <--- R</pre>
</td></tr>
<tr><td><pre>i26 : GB = gens gb F
o26 = | y6+6781y5z+9886y4z2-5922y3z3+15586y2z4+3142yz5+3816z6
-----------------------------------------------------------------------
xz4+1736y5+13680y4z-3939y3z2-15144y2z3-10905yz4+1763z5
-----------------------------------------------------------------------
xyz2+6036xz3-15150y4-10154y3z-14712y2z2+619yz3-13974z4
-----------------------------------------------------------------------
xy2-623xyz+14807xz2-5117y3-8439y2z+12868yz2-10042z3
-----------------------------------------------------------------------
x2-9669xy-13017xz-9193y2+15489yz-1708z2 |
1 5
o26 : Matrix R <--- R</pre>
</td></tr>
<tr><td><pre>i27 : LT = leadTerm gens gb F
o27 = | y6 xz4 xyz2 xy2 x2 |
1 5
o27 : Matrix R <--- R</pre>
</td></tr>
<tr><td><pre>i28 : betti LT
0 1
o28 = total: 1 5
0: 1 .
1: . 1
2: . 1
3: . 1
4: . 1
5: . 1
o28 : BettiTally</pre>
</td></tr>
</table>
and there are Gröbner basis elements of degrees <i>2,3,4,5,6.</i><h4>C. Division With Remainder</h4>
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>I</i> that defines the variety <i>X</i> of nilpotent <i>3 ×3</i> matrices by taking the cube of a generic matrix and setting the entries equal to zero. Here’s how:<table class="examples"><tr><td><pre>i29 : R = KK[a..i]
o29 = R
o29 : PolynomialRing</pre>
</td></tr>
<tr><td><pre>i30 : M = genericMatrix(R,a,3,3)
o30 = | a d g |
| b e h |
| c f i |
3 3
o30 : Matrix R <--- R</pre>
</td></tr>
<tr><td><pre>i31 : N = M^3
o31 = | 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
o31 : Matrix R <--- R</pre>
</td></tr>
<tr><td><pre>i32 : I = flatten N
o32 = | 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
o32 : Matrix R <--- R</pre>
</td></tr>
</table>
(actually this produces a 1 x 9 matrix of of forms, not the ideal: <tt>J = ideal I</tt>; the matrix will be more useful to us). But the trace is not in <i>I</i>! This is obvious from the fact that the trace has degree <i>1</i>, but the polynomials in <i>I</i> are of degree <i>3</i>. We could also check by division with remainder:<table class="examples"><tr><td><pre>i33 : Tr = trace M
o33 = a + e + i
o33 : R</pre>
</td></tr>
<tr><td><pre>i34 : Tr //I -- the quotient, which is 0
o34 = 0
9 1
o34 : Matrix R <--- R</pre>
</td></tr>
<tr><td><pre>i35 : Tr % I -- the remainder, which is Tr again
o35 = a + e + i
o35 : R</pre>
</td></tr>
</table>
(Here <tt>Tr</tt> is an element of <i>R</i>, not a matrix. We could do the same thing with a <i>1 ×1</i> matrix with <tt>Tr</tt> as its element.) This is of course because the entries of <i>I</i> do NOT generate the ideal of all forms vanishing on <i>X</i> -- this we may find with <tt>J = radical ideal I</tt>, (but this takes a while: see the documentation for <tt>radical</tt> 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 <i>2 ×2</i> minors, that is, by the coefficients of the characteristic polynomial. In particular, we can try the powers of the radical:<table class="examples"><tr><td><pre>i36 : Tr^2 % I
2 2 2
o36 = a + 2a*e + e + 2a*i + 2e*i + i
o36 : R</pre>
</td></tr>
<tr><td><pre>i37 : Tr^3 % I
2 2 3 2
o37 = 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
o37 : R</pre>
</td></tr>
<tr><td><pre>i38 : Tr^4 % I
2 2 2 3 4
o38 = 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
o38 : R</pre>
</td></tr>
<tr><td><pre>i39 : Tr^5 % I
2 2 2 3 4 2 2
o39 = 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
o39 : R</pre>
</td></tr>
<tr><td><pre>i40 : Tr^6 % I
2 2 2 2 2 3 2 4 2 2 2 2 2
o40 = 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
o40 : R</pre>
</td></tr>
<tr><td><pre>i41 : Tr^7 % I
o41 = 0
o41 : R</pre>
</td></tr>
</table>
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<table class="examples"><tr><td><pre>i42 : Tr^6 // I
o42 = {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
o42 : Matrix R <--- R</pre>
</td></tr>
</table>
is not 0. It is a matrix that makes the following true:<table class="examples"><tr><td><pre>i43 : Tr^6 == I * (Tr^6 // I) + (Tr^6 % I)
o43 = true</pre>
</td></tr>
</table>
<h4>D. Elimination Theory</h4>
Consider the problem of projecting the “twisted cubic”, a curve in <i><b>P</b><sup>3</sup></i> defined by the three <i>2 ×2</i> minors of a certain <i>2 ×3</i> matrix into the plane. Such problems can be solved in a very simple and direct way using Gröbner bases. The technique lends itself to many extensions, and in its developed form can be used to find the closure of the image of any map of affine varieties. <p/>
In this section we shall first give a simple direct treatment of the problem above, and then show how to use Macaulay2’s general tool to solve the problem. We first clear the earlier meaning of <tt>x</tt> to make it into a subscripted variable<table class="examples"><tr><td><pre>i44 : x = global x
o44 = x
o44 : Symbol</pre>
</td></tr>
</table>
and then set<table class="examples"><tr><td><pre>i45 : R = KK[x_0..x_3]
o45 = R
o45 : PolynomialRing</pre>
</td></tr>
</table>
the homogeneous coordinate ring of <i><b>P</b><sup>3</sup></i> and<table class="examples"><tr><td><pre>i46 : M = map(R^2, 3, (i,j)->x_(i+j))
o46 = | x_0 x_1 x_2 |
| x_1 x_2 x_3 |
2 3
o46 : Matrix R <--- R</pre>
</td></tr>
<tr><td><pre>i47 : I = gens minors(2,M)
o47 = | -x_1^2+x_0x_2 -x_1x_2+x_0x_3 -x_2^2+x_1x_3 |
1 3
o47 : Matrix R <--- R</pre>
</td></tr>
</table>
a matrix whose image is the ideal of the twisted cubic. As projection center we take the point defined by<table class="examples"><tr><td><pre>i48 : pideal = ideal(x_0+x_3, x_1, x_2)
o48 = ideal (x + x , x , x )
0 3 1 2
o48 : Ideal of R</pre>
</td></tr>
</table>
To find the image we must intersect the ideal <i>I</i> with the subring generated by the generators of <tt>pideal</tt>. We make a change of variable so that these generators become the last three variables in the ring; that is, we write the ring as <i>KK[y<sub>0</sub>..y<sub>3</sub>]</i> where <p align=center><i>y<sub>0</sub> = x<sub>0</sub>, y<sub>1</sub> = x<sub>1</sub>, y<sub>2</sub> = x<sub>2</sub>, y<sub>3</sub> = x<sub>0</sub>+x<sub>3</sub></i></p> and thus <i>x<sub>3</sub> = y<sub>3</sub>-y<sub>0</sub></i>, etc. We want the new ring to have an “elimination order” for the first variable.<table class="examples"><tr><td><pre>i49 : y = global y
o49 = y
o49 : Symbol</pre>
</td></tr>
<tr><td><pre>i50 : S = KK[y_0..y_3,MonomialOrder=> Eliminate 1]
o50 = S
o50 : PolynomialRing</pre>
</td></tr>
</table>
Here is one way to make the substitution<table class="examples"><tr><td><pre>i51 : I1 = substitute(I, matrix{{y_0,y_1,y_2,y_3-y_0}})
o51 = | y_0y_2-y_1^2 -y_0^2+y_0y_3-y_1y_2 -y_0y_1-y_2^2+y_1y_3 |
1 3
o51 : Matrix S <--- S</pre>
</td></tr>
</table>
The elimination of 1 variable from the matrix of Gröbner basis elements proceeds as follows:<table class="examples"><tr><td><pre>i52 : J = selectInSubring(1,gens gb I1)
o52 = | y_1^3+y_2^3-y_1y_2y_3 |
1 1
o52 : Matrix S <--- S</pre>
</td></tr>
</table>
and gives (a matrix with element) the cubic equation of a rational curve with one double point in the plane. However, we are still in a ring with 4 variables, so if we really want a plane curve (and not the cone over one) we must move to yet another ring:<table class="examples"><tr><td><pre>i53 : S1 = KK[y_1..y_3]
o53 = S1
o53 : PolynomialRing</pre>
</td></tr>
<tr><td><pre>i54 : J1 = substitute(J, S1)
o54 = | y_1^3+y_2^3-y_1y_2y_3 |
1 1
o54 : Matrix S1 <--- S1</pre>
</td></tr>
</table>
This time we didn’t have to give so much detail to the <tt>substitute</tt> command because of the coincidence of the names of the variables.<p/>
Having shown the primitive method, we now show a much more flexible and transparent one: we set up a ring map from the polynomial ring in <i>3</i> variables (representing the plane) to <i>R/I</i>, taking the variables <i>y</i> to the three linear forms that define the projection center. Then we just take the kernel of this map! (“Under the hood”, Macaulay2 is doing a more refined version of the same computation as before.) Here is the ring map<table class="examples"><tr><td><pre>i55 : Rbar = R/(ideal I)
o55 = Rbar
o55 : QuotientRing</pre>
</td></tr>
<tr><td><pre>i56 : f = map(Rbar, S1, matrix(Rbar,{{x_0+x_3, x_1,x_2}}))
o56 = map(Rbar,S1,{x + x , x , x })
0 3 1 2
o56 : RingMap Rbar <--- S1</pre>
</td></tr>
</table>
and the desired ideal<table class="examples"><tr><td><pre>i57 : J1 = ker f
3 3
o57 = ideal(y - y y y + y )
2 1 2 3 3
o57 : Ideal of S1</pre>
</td></tr>
</table>
<h4>E. Quotients and saturation</h4>
Another typical application of Gröbner bases and syzygies is to the computation of ideal quotients and saturations. Again we give an easy example that we can treat directly, and then introduce the tool used in Macaulay2 to treat the general case.<p/>
If <i>I</i> and <i>J</i> are ideals in a ring <i>R</i>, we define <i>(I:J)</i>, the ideal quotient, by <p align=center><i>(I:J) = {f ∈R | fJ ⊂I}.</i></p><p/>
In our first examples we consider the case where <i>J</i> is generated by a single element <i>g</i>. This arises in practice, for example, in the problem of homogenizing an ideal. Suppose we consider the affine space curve parametrized by <i>t → (t,t<sup>2</sup>,t<sup>3</sup>)</i>. The ideal of polynomials vanishing on the curve is easily seen to be <i>(b-a<sup>2</sup>, c-a<sup>3</sup>)</i> (where we have taken <i>a,b,c</i> as the coordinates of affine space). To find the projective closure of the curve in <i><b>P</b><sup>3</sup></i>, we must homogenize these equations with respect to a new variable d, getting <i>db-a<sup>2</sup>, d<sup>2</sup>c-a<sup>3</sup></i>. But these forms do NOT define the projective closure! In general, homogenizing the generators of the ideal <i>I</i> of an affine variety one gets an ideal <i>I<sub>1</sub></i> that defines the projective closure UP TO a component supported on the hyperplane at infinity (the hyperplane <i>d=0</i>). To see the ideal of the closure we must remove any such components, for example by replacing <i>I<sub>1</sub></i> by the union <i>I<sub>2</sub></i> of all the ideals <i>(I<sub>1</sub>:d<sup>n</sup>)</i>, where <i>n</i> ranges over positive integers. This is not so hard as it seems: First of all, we can successively compute the increasing sequence of ideals <i>(I<sub>1</sub>:d), (I<sub>1</sub>:d<sup>2</sup>), ...</i> until we get two that are the same; all succeeding ones will be equal, so we have found the union. A second method involves a special property of the reverse lex order, and is much more efficient in this case. We shall illustrate both. First we set up the example above:<table class="examples"><tr><td><pre>i58 : R = KK[a,b,c,d]
o58 = R
o58 : PolynomialRing</pre>
</td></tr>
<tr><td><pre>i59 : I1 = ideal(d*b-a^2, d^2*c-a^3)
2 3 2
o59 = ideal (- a + b*d, - a + c*d )
o59 : Ideal of R</pre>
</td></tr>
</table>
How to compute the ideal quotient: If <i>I</i> is generated by <i>f<sub>1</sub>,...,f<sub>n</sub></i>, we see that <i>s∈(I:g)</i> iff there are ring elements <i>r<sub>i</sub></i> such that <p align=center><i>∑<sub>i=1</sub><sup>n</sup> r<sub>i</sub> f<sub>i</sub> + s g = 0. </i></p> Thus it suffices to compute the kernel (syzygies) of the <i>1 ×(n+1)</i> matrix <p align=center><i>(f<sub>1</sub>, ... ,f<sub>n</sub>, g)</i></p> and collect the coefficients of <i>g</i>, that is, the entries of the last row of a matrix representing the kernel. Thus in our case we may compute <i>(I<sub>1</sub>:d)</i> by concatenating the matrix for <i>I<sub>1</sub></i> with the single variable <i>d</i><table class="examples"><tr><td><pre>i60 : I1aug = (gens I1) | matrix{{d}}
o60 = | -a2+bd -a3+cd2 d |
1 3
o60 : Matrix R <--- R</pre>
</td></tr>
<tr><td><pre>i61 : augrelations = gens ker I1aug
o61 = {2} | -a d |
{3} | 1 0 |
{1} | ab-cd a2-bd |
3 2
o61 : Matrix R <--- R</pre>
</td></tr>
</table>
There are 3 rows (numbered 0,1,2 !) and 2 columns, so to extract the last row we may do<table class="examples"><tr><td><pre>i62 : I21 = submatrix(augrelations, {2}, {0,1})
o62 = {1} | ab-cd a2-bd |
1 2
o62 : Matrix R <--- R</pre>
</td></tr>
</table>
But this is not an “ideal” properly speaking: first of all, it is a matrix, not an ideal, and second of all its target is not <i>R<sup>1</sup></i> but <i>R(-1)</i>, the free module of rank 1 with generator in degree 1. We can fix both of these problems by<table class="examples"><tr><td><pre>i63 : I21 = ideal I21
2
o63 = ideal (a*b - c*d, a - b*d)
o63 : Ideal of R</pre>
</td></tr>
</table>
This is larger than the original ideal, having two quadratic generators instead of a quadric and a cubic, so we continue. Instead of doing the same computation again, we introduce the built-in command<table class="examples"><tr><td><pre>i64 : I22 = I21 : d
2 2
o64 = ideal (b - a*c, a*b - c*d, a - b*d)
o64 : Ideal of R</pre>
</td></tr>
</table>
which is again larger than <tt>I21</tt>, having three quadratic generators. Repeating,<table class="examples"><tr><td><pre>i65 : I23 = I22 : d
2 2
o65 = ideal (b - a*c, a*b - c*d, a - b*d)
o65 : Ideal of R</pre>
</td></tr>
</table>
we get another ideal with three quadratic generators. It must be the same as <tt>I21</tt>, but the generators are written differently because of the route taken to get it, so (being suspicious) we might check with<table class="examples"><tr><td><pre>i66 : (gens I23) % (gens I22)
o66 = 0
1 3
o66 : Matrix R <--- R</pre>
</td></tr>
</table>
which returns 0, showing that <tt>I23</tt> is contained in (gives remainder 0 when divided by) <tt>I22</tt>. Thus the homogeneous ideal <tt>I2</tt> of the projective closure is equal to <tt>I23</tt> (this is the homogeneous ideal of the twisted cubic, already encountered above).<p/>
A more perspicuous way of approaching the computation of the union of the <i>(I:d<sup>n</sup>)</i>, which is called the saturation of <i>I</i> with respect to <i>d</i>, and written <i>(I:d<sup>∞</sup>)</i>, is first to compute a reverse lex Gröbner basis.<table class="examples"><tr><td><pre>i67 : gens gb I1
o67 = | a2-bd abd-cd2 b2d2-acd2 |
1 3
o67 : Matrix R <--- R</pre>
</td></tr>
</table>
This yields <tt>(a2-bd, abd-cd2, b2d2-acd2)</tt>, meaning <p align=center><i>(a<sup>2</sup>-bd, abd-cd<sup>2</sup>, b<sup>2</sup>d<sup>2</sup>-acd<sup>2</sup>).</i></p> We see that the second generator is divisible by <i>d</i>, and the third is divisible by <i>d<sup>2</sup></i>. General theory says that we get the right answer simply by making these divisions, that is, the saturation is <p align=center><i>(a<sup>2</sup>-cd, ab-cd, b<sup>2</sup>-ac),</i></p> as previously computed. The same thing can be accomplished in one line by<table class="examples"><tr><td><pre>i68 : I2 = divideByVariable(gens gb I1,d)
o68 = (| a2-bd ab-cd b2-ac |, 2)
o68 : Sequence</pre>
</td></tr>
</table>
This saturation may be found directly in Macaulay2:<table class="examples"><tr><td><pre>i69 : saturate(I1, d)
2 2
o69 = ideal (b - a*c, a*b - c*d, a - b*d)
o69 : Ideal of R</pre>
</td></tr>
</table>
</div>
</div>
</body>
</html>
