cancelAll -- make all potentially possible cancellations in the graded free resolution of an ideal in a particular way

Let R be a polynomial ring, let I and J be homogeneous ideals in R of codimension c with the same Hilbert function, and assume that R/I and R/J are Cohen-Macaulay. Suppose that the graded Betti numbers of R/I are at most those of R/J; that is, beta_{ij}(R/I) <= beta_{ij}(R/J) for all i and j. (We can form a partial order on resolutions of modules with the same Hilbert function by saying that beta(R/I) <= beta(R/J) if and only if beta_{ij}(R/I) <= beta_{ij}(R/J) for all i and j.)

Let m_i(R/I) and M_i(R/I) be the minimum and maximum shifts at step i in the minimal graded free resolution of R/I. Let e(R/I) be the multiplicity of R/I. Herzog, Huneke, and Srinivasan have conjectured that

m_1(R/I) ... m_c(R/I) / c! <= e(R/I) <= M_1(R/I) ... M_c(R/I) / c!,

where the ellipses signfiy that we are taking the product of the shifts.

Suppose that R/I satisfies the conjectured inequalities. Then it is easy to show that R/J must as well: Since the resolution of R/J contains all the shifts in the resolution of R/I plus possibly more, the minimum shifts for R/J 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.

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 cancelAll 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 multUpperHF. 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.

cancelAll 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 L, and R/L is Cohen-Macaulay, minimize each M_i that could occur for a Cohen-Macaulay module with the same Hilbert function as R/L. Therefore if the upper bound of the conjecture holds for the potential Betti diagram that cancelAll produces, it holds for all Cohen-Macaulay modules with the same Hilbert function and codimension. Even if the potential Betti diagram cancelAll 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 cancelAll.

cancelAll makes all the cancellations with the process described above, prints the resulting Betti diagram, and then returns the shifts in a list of lists.

See C. Francisco, New approaches to bounding the multiplicity of an ideal, J. Algebra 299 (2006), no. 1, 309-328.

i1 : R=ZZ/32003[a..c];

i2 : L=lexIdeal(R,{1,3,6,9,9,6,2});

o2 : Ideal of R

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

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

i5 : M=lexIdeal(R,{1,3,4,3,2});

o5 : Ideal of R

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

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

i8 : A=ZZ/32003[a..e];

i9 : J=lexIdeal(A,{1,5,12,10,6,3})

             2               2            2   3   2    2    2      2        
o9 = ideal (a , a*b, a*c, a*d , a*d*e, a*e , b , b c, b d, b e, b*c , b*c*d,
     ------------------------------------------------------------------------
               2            2   4   3    3    2 2   2      2 2     3     2  
     b*c*e, b*d , b*d*e, b*e , c , c d, c e, c d , c d*e, c e , c*d , c*d e,
     ------------------------------------------------------------------------
          2     4   5   4    3 2   2 4     5   6
     c*d*e , c*e , d , d e, d e , d e , d*e , e )

o9 : Ideal of A

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

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