<?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>cancelAll -- make all potentially possible cancellations in the graded free resolution of an ideal</title>
<link rel="stylesheet" type="text/css" href="../../../../Macaulay2/Style/doc.css"/>
</head>
<body>
<table class="buttons">
<tr>
<td><div><a href="_generate__L__P__Ps.html">next</a> | <a href="index.html">previous</a> | <a href="_generate__L__P__Ps.html">forward</a> | <a href="index.html">backward</a> | up | <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>
<hr/>
<div><h1>cancelAll -- make all potentially possible cancellations in the graded free resolution of an ideal</h1>
<div class="single"><h2>Synopsis</h2>
<ul><li><div class="list"><dl class="element"><dt class="heading">Usage: </dt><dd class="value"><div><tt>l=cancelAll I</tt></div>
</dd></dl>
</div>
</li>
<li><div class="single">Inputs:<ul><li><span><tt>I</tt>, <span>an <a href="../../Macaulay2Doc/html/___Ideal.html">ideal</a></span>, a homogeneous ideal in a polynomial ring</span></li>
</ul>
</div>
</li>
<li><div class="single">Outputs:<ul><li><span><tt>l</tt>, <span>a <a href="../../Macaulay2Doc/html/___List.html">list</a></span>, lists of the new shifts in the Betti diagram</span></li>
</ul>
</div>
</li>
</ul>
</div>
<div class="single"><h2>Description</h2>
<div><p>This function was useful in testing the upper bound of the conjecture of Herzog-Huneke-Srinivasan on the multiplicity of an ideal; it is designed to make all potentially possible cancellations in a Betti diagram in a certain order described below.</p>
<p>Let <tt>R</tt> be a polynomial ring, let <tt>I</tt> and <tt>J</tt> be homogeneous ideals in <tt>R</tt> of codimension <tt>c</tt> with the same Hilbert function, and assume that <tt>R/I</tt> and <tt>R/J</tt> are Cohen-Macaulay. Suppose that the graded Betti numbers of <tt>R/I</tt> are at most those of <tt>R/J</tt>; that is, <tt>beta<sub>ij</sub>(R/I) <= beta<sub>ij</sub>(R/J)</tt> for all <tt>i</tt> and <tt>j</tt>. (We can form a partial order on resolutions of modules with the same Hilbert function by saying that <tt>beta(R/I) <= beta(R/J)</tt> if and only if <tt>beta<sub>ij</sub>(R/I) <= beta<sub>ij</sub>(R/J)</tt> for all <tt>i</tt> and <tt>j</tt>.)</p>
<p>Let <tt>m<sub>i</sub>(R/I)</tt> and <tt>M<sub>i</sub>(R/I)</tt> be the minimum and maximum shifts at step <tt>i</tt> in the minimal graded free resolution of <tt>R/I</tt>. Let <tt>e(R/I)</tt> be the multiplicity of <tt>R/I</tt>. Herzog, Huneke, and Srinivasan conjectured that</p>
<p><tt>m<sub>1</sub>(R/I) ... m<sub>c</sub>(R/I) / c! <= e(R/I) <= M<sub>1</sub>(R/I) ... M<sub>c</sub>(R/I) / c!</tt>,</p>
<p>where the ellipses signfiy that we are taking the product of the shifts. This conjecture was proven in 2008 work of Eisenbud-Schreyer and Boij-Soderberg using decompositions of Betti diagrams as positive linear combinations of Betti diagrams of modules with pure resolutions.</p>
<p>Suppose that <tt>R/I</tt> satisfies the conjectured inequalities. Then it is easy to show that <tt>R/J</tt> must as well: Since the resolution of <tt>R/J</tt> contains all the shifts in the resolution of <tt>R/I</tt> plus possibly more, the minimum shifts for <tt>R/J</tt> can only be the same or lower, and the maximum shifts can only be the same or higher. Therefore one can attack this conjecture by looking at resolutions minimal in the partial order discussed above.</p>
<p>It is difficult to find which potential resolutions at the bottom of the partial order for a given Hilbert function do occur for a module, however. The function <tt>cancelAll</tt> implements a fast way of proving that the upper bound of the Herzog-Huneke-Srinivasan conjecture is satisfied for particular Hilbert functions; it is used in <a href="_mult__Upper__H__F.html" title="test a sufficient condition for the upper bound of the multiplicity conjecture">multUpperHF</a>. The idea is to create a Betti diagram that is minimal in the partial order that may or may not actually occur for a module; we can then test the upper bound on that potential resolution. As we explain below, if the inequality holds, it doesn’t matter whether the Betti diagram occurs for a module or not.</p>
<p><tt>cancelAll</tt> starts with the far left side of the Betti diagram of the ideal I the user inputs, and it makes all potentially possible cancellations in the first two columns. Then it moves to the first and second syzygies columns and makes all potentially possible cancellations, continuing through the rest of the Betti diagram. This technique is designed to investigate the upper bound of the conjecture. One may have choices of which syzygies to cancel from the resolution of the lexicographic ideal. This algorithm selects the cancellations that, if we start out with a lexicographic ideal <tt>L</tt>, and <tt>R/L</tt> is Cohen-Macaulay, minimize each <tt>M<sub>i</sub></tt> that could occur for a Cohen-Macaulay module with the same Hilbert function as <tt>R/L</tt>. Therefore if the upper bound of the conjecture holds for the potential Betti diagram that <tt>cancelAll</tt> produces, it holds for all Cohen-Macaulay modules with the same Hilbert function and codimension. Even if the potential Betti diagram <tt>cancelAll</tt> produces doesn’t occur for a module, the maximum shifts could only increase, which won’t cause the inequality to fail if it holds for the result of <tt>cancelAll</tt>.</p>
<p><tt>cancelAll</tt> makes all the cancellations with the process described above, prints the resulting Betti diagram, and then returns the shifts in a list of lists.</p>
<div>See C. Francisco, New approaches to bounding the multiplicity of an ideal, <em>J. Algebra</em> <b>299</b> (2006), no. 1, 309-328.</div>
<table class="examples"><tr><td><pre>i1 : R=ZZ/32003[a..c];</pre>
</td></tr>
<tr><td><pre>i2 : L=lexIdeal(R,{1,3,6,9,9,6,2});
o2 : Ideal of R</pre>
</td></tr>
<tr><td><pre>i3 : betti res L
0 1 2 3
o3 = total: 1 16 27 12
0: 1 . . .
1: . . . .
2: . 1 . .
3: . 3 5 2
4: . 5 9 4
5: . 5 9 4
6: . 2 4 2
o3 : BettiTally</pre>
</td></tr>
<tr><td><pre>i4 : cancelAll L
total: 1 4 5 2
0: 1 . . .
1: . . . .
2: . 1 . .
3: . 3 . .
4: . . 2 .
5: . . 3 .
6: . . . 2
o4 = {{3, 4, 4, 4}, {6, 6, 7, 7, 7}, {9, 9}}
o4 : List</pre>
</td></tr>
<tr><td><pre>i5 : M=lexIdeal(R,{1,3,4,3,2});
o5 : Ideal of R</pre>
</td></tr>
<tr><td><pre>i6 : betti res M
0 1 2 3
o6 = total: 1 7 10 4
0: 1 . . .
1: . 2 1 .
2: . 2 3 1
3: . 1 2 1
4: . 2 4 2
o6 : BettiTally</pre>
</td></tr>
<tr><td><pre>i7 : cancelAll M
total: 1 3 5 3
0: 1 . . .
1: . 2 . .
2: . 1 2 1
3: . . . .
4: . . 3 2
o7 = {{2, 2, 3}, {4, 4, 6, 6, 6}, {5, 7, 7}}
o7 : List</pre>
</td></tr>
<tr><td><pre>i8 : A=ZZ/32003[a..e];</pre>
</td></tr>
<tr><td><pre>i9 : J=lexIdeal(A,{1,5,12,10,6,3})
2 2 2 2 2 2
o9 = ideal (a*c, a*b, a , b*e , a*e , b*d*e, a*d*e, b*c*e, b e, b*d , a*d ,
------------------------------------------------------------------------
2 2 2 3 2 2 2 2 2 3 3 2 2
b*c*d, b d, b*c , b c, b , c*d*e , c e , c*d e, c d*e, c e, c*d , c d ,
------------------------------------------------------------------------
3 4 4 3 2 4 5 6 5 2 4
c d, c , c*e , d e , d e, d , e , d*e , d e )
o9 : Ideal of A</pre>
</td></tr>
<tr><td><pre>i10 : betti res J
0 1 2 3 4 5
o10 = total: 1 32 102 130 76 17
0: 1 . . . . .
1: . 3 3 1 . .
2: . 13 41 50 28 6
3: . 9 31 40 23 5
4: . 4 15 21 13 3
5: . 3 12 18 12 3
o10 : BettiTally</pre>
</td></tr>
<tr><td><pre>i11 : cancelAll J
total: 1 13 31 28 17 8
0: 1 . . . . .
1: . 3 . . . .
2: . 10 31 23 . .
3: . . . . 8 5
4: . . . . . .
5: . . . 5 9 3
o11 = {{2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3}, {4, 4, 4, 4, 4, 4, 4, 4, 4,
-----------------------------------------------------------------------
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4}, {5,
-----------------------------------------------------------------------
5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 8, 8,
-----------------------------------------------------------------------
8, 8, 8}, {7, 7, 7, 7, 7, 7, 7, 7, 9, 9, 9, 9, 9, 9, 9, 9, 9}, {8, 8,
-----------------------------------------------------------------------
8, 8, 8, 10, 10, 10}}
o11 : List</pre>
</td></tr>
</table>
</div>
</div>
<div class="single"><h2>See also</h2>
<ul><li><span><a href="_mult__Upper__H__F.html" title="test a sufficient condition for the upper bound of the multiplicity conjecture">multUpperHF</a> -- test a sufficient condition for the upper bound of the multiplicity conjecture</span></li>
<li><span><a href="_mult__Upper__Bound.html" title="determine whether an ideal satisfies the upper bound of the multiplicity conjecture">multUpperBound</a> -- determine whether an ideal satisfies the upper bound of the multiplicity conjecture</span></li>
<li><span><a href="_mult__Lower__Bound.html" title="determine whether an ideal satisfies the lower bound of the multiplicity conjecture">multLowerBound</a> -- determine whether an ideal satisfies the lower bound of the multiplicity conjecture</span></li>
<li><span><a href="_mult__Bounds.html" title="determine whether an ideal satisfies the upper and lower bounds of the multiplicity conjecture">multBounds</a> -- determine whether an ideal satisfies the upper and lower bounds of the multiplicity conjecture</span></li>
</ul>
</div>
<div class="waystouse"><h2>Ways to use <tt>cancelAll</tt> :</h2>
<ul><li>cancelAll(Ideal)</li>
</ul>
</div>
</div>
</body>
</html>
