Finding Extreme Examples -- Ways to use random ideals to search for (counter)-examples

A common use of Macaulay2 is to look for extreme or particularly interesting examples. Here are some examples of how this may be done.

Supposing first that some space of examples is finite; for example, we might be interested in monomial ideals with a certain number of generators of a certain degree d. Suppose, to be concrete, that we want to compare the maximum degree of a first syzygy with the regularity of the ideal, and also with the maximum degree of the last syzygy. (To make the comparison interesting, it seems reasonable to subtract i from the maximum degree of an i-th syzygy.)

We may have no idea where to look for extreme examples, and it seems that examples with small numbers of variables and generators may not show the range of phenomena that actually occur. In large degree there may be too many examples to search systematically; so instead we may choose many examples at random, and hope to see a pattern.

Here is a simple example First we tally the projective dimensions of 500 random square-free monomial ideals (what's the average?), then looking how big the difference between the regularity of R/I and the "relation degree"-2 can be. It turns out this the differences are rather small, only 1 in a typical run of 5000. So one might look for ideals with a difference of 2, as in the following (in a real run, one would make the number of iterations much bigger; here we keep it small so that Macaulay2 doesn't take too long to build it's documentation files.)

i1 : kk=ZZ/101

o1 = kk

o1 : QuotientRing

i2 : S=kk[vars(0..5)]

o2 = S

o2 : PolynomialRing

i3 : L=for n from 1 to 100 list res randomSquareFreeMonomialIdeal(10:3,S);

i4 : tally apply(L, F -> length F)

o4 = Tally{3 => 34}
           4 => 66

o4 : Tally

i5 : tally apply(L, F -> regularity F - ((max flatten degrees F_2) - 2))

o5 = Tally{0 => 94}
           1 => 6

o5 : Tally

i6 : L=for n from 1 to 500 list res randomSquareFreeMonomialIdeal(10:3,S);

i7 : scan(L, F -> if 1<(regularity F - (max flatten degrees F_2) + 2) then print F.dd_1)

A typical problem might be to find how high the regularity of R/I can be when R has reasonably few variables, and the degrees of the generators of I are reasonably small; despite the wild examples of Mayr-Mayer, we don't know how to make examples with large regularity without letting the number of variables become large. The following program computes "rep" examples of random ideals with monomial and binomial generators, and prints any whose regularity exceeds the number "bound"

looper = (rep,bound, L1, L2) -> (for i from 1 to rep do ( if i % 1000 == 0 then << "." << flush; J := randomMonomialIdeal(L1,S) + randomBinomialIdeal(L2,S); m := regularity coker gens J; if m >= bound then << "reg " << m << " " << toString J << endl;))

For example: kk=ZZ/2 S=kk[a,b,c,d] looper(30000,10,{4},{4,4}) -- finds examples with on monomial of degree 4 and 2 binomials of degree 4. The largest largest regularity it has found (and the largest I know for an ideal in 4 variables of degree 4) is 14. Here is an example it found: ideal(a*b^3,a^4+b^4,b*c^3+a*d^3)

Similarly:

looper(30000,10,{4,4},{4}) -- looks for examples with 2 monomials and 1 binomial of degree 4. Suggestively, the largest regularity it found was also 14: betti res ideal(c^4,b^4,a^3*c+b*d^3) -- reg 14

A more sophisticated and difficult situation arises when the space of examples is not necessarily finite (except over a finite field) but is a unirational variety (such as the space of ideals generated by (at most) a certain number of forms of certain given degrees, or the space of smooth curves of genus g for some g <= 14) one may be able to do a search for random examples, taking a rational parametrization of the space of examples and plugging in random inputs.

If the "interesting" examples live in a subvariety whose codimension is small, then, working over a small field (say 2,3, or 5 elements) one might hope to see elements of the subvariety "not too rarely". This principle has been used to good effect for example by (Caviglia and Decker-Schreyer, ****--Schreyer).