# RandomMonomialIdeals -- A package for generating Erdos-Renyi-type random monomial ideals and variations

## Description

RandomMonomialIdeals is a package for sampling random monomial ideals from an Erdos-Renyi-type distribution, the graded version of it, and some extensions. It also introduces new objects, Sample and Model, to allow for streamlined handling of random objects and their statistics in Macaulay2. Most of the models implemented are drawn from the paper Random Monomial Ideals by Jesus A. De Loera, Sonja Petrovic, Lily Silverstein, Despina Stasi, and Dane Wilburne (https://arxiv.org/abs/1701.07130).

The main method, randomMonomialSets, generates a sample of size N from the distribution B(n, D, p) of sets of monomials of degree at most D, on n variables, where p is the probability of selecting any given monomial:

 `i1 : n=3; D=2; p=0.5; N=4;` ```i5 : L = randomMonomialSets(n,D,p,N) 2 2 2 o5 = {{x , x x , x x , x }, {x , x , x x , x x , x }, {x , x , x x , x x }, 3 1 2 2 3 3 3 1 1 3 2 3 3 2 3 1 2 1 3 ------------------------------------------------------------------------ 2 2 2 {x , x , x x , x , x x , x }} 1 1 1 2 2 2 3 3 o5 : List```

For a formal definition of the model, see Section 1 of https://arxiv.org/abs/1701.07130.

This model was inspired by random graphs. To parallel the two variants of the Erdos-Renyi model for graphs - fixing either the probability of an edge or the total number of edges - the package also includes the model with fixed number of monomials to be generated:

 `i6 : n=3; D=2; M=3; N=4;` ```i10 : L = randomMonomialSets(n,D,M,N) 2 2 2 o10 = {{x , x x , x x }, {x , x , x }, {x x , x x , x }, {x x , x , x }} 1 1 2 1 3 3 3 1 1 2 2 3 2 2 3 3 3 o10 : List```

To sample from the graded model from Section 6 of https://arxiv.org/abs/1701.07130, simply replace p by a list of D probabilities, one for each degree. In the example below, monomials of degree 1 are not selected (probability = 0), while each monomial of degree 2 is selected with probability 1.

 `i11 : n=3; D=2; N=4;` ```i14 : randomMonomialSets(n,D,{0.0,1.0},N) 2 2 2 2 2 2 2 o14 = {{x , x x , x x , x , x x , x }, {x , x x , x x , x , x x , x }, {x , 1 1 2 1 3 2 2 3 3 1 1 2 1 3 2 2 3 3 1 ----------------------------------------------------------------------- 2 2 2 2 2 x x , x x , x , x x , x }, {x , x x , x x , x , x x , x }} 1 2 1 3 2 2 3 3 1 1 2 1 3 2 2 3 3 o14 : List```

The package also allows for sampling from the graded version of the fixed number of monomials model, where we specify the requested number of monomials of each degree. In the example below, we sample random sets of monomials with one monomial of degree 1, zero of degree 2 and three monomials of degree 3.

 `i15 : n=3; D=3; N=4;` ```i18 : randomMonomialSets(n,D,{1,0,3},N) 2 3 3 2 2 2 3 2 2 o18 = {{x , x x , x , x }, {x , x x , x x , x x }, {x , x , x x , x x }, {x , 1 2 3 2 3 2 1 2 1 2 1 3 3 2 1 2 1 2 3 ----------------------------------------------------------------------- 3 2 3 x , x x , x }} 1 1 3 3 o18 : List```

Finally we can request the monomial sets generated by the graded model with fixed number of monomials, to be minimal generating sets. We can also employ the minimal strategy for a couple of the other versions of the randomMonomialSets method.

 `i19 : n=3; D=3; N=4;` ```i22 : randomMonomialSets(n,D,{1,0,3},N, Strategy=>"Minimal") 2 3 2 3 2 2 2 2 3 o22 = {{x , x x , x , x x }, {x , x , x x , x x }, {x , x x , x x , x }, {x , 1 2 3 2 2 3 3 2 1 2 1 2 1 2 3 2 3 2 1 ----------------------------------------------------------------------- 2 2 3 x x , x x , x }} 2 3 2 3 2 o22 : List``` ```i23 : randomMonomialSets(n,D,{0.0,0.3,0.5},N, Strategy=>"Minimal") 2 3 2 2 3 2 2 2 2 o23 = {{x x , x x , x , x }, {x , x , x }, {x , x x , x , x x }, {x , x x , 1 2 2 3 3 2 1 3 2 1 1 2 2 2 3 1 1 2 ----------------------------------------------------------------------- 2 2 3 x x x , x x , x x , x }} 1 2 3 2 3 2 3 3 o23 : List``` ```i24 : randomMonomialSets(n,D,0.1,N, Strategy=>"Minimal") 3 2 2 o24 = {{x x , x }, {x , x x x }, {x x }, {0}} 2 3 2 1 1 2 3 1 3 o24 : List```

Once a sample is generated, one can compute various statistics regarding algebraic properties of the sample. The methods in the package offer a way to compute and summarize statistics on some of the common properties, such as degree, dimension, projective dimension, Castelnuovo-Mumford regularity, etc. For example, we can use dimStats to get the Krull dimension statistics:

 ```i25 : ideals=idealsFromGeneratingSets(L) 2 o25 = {monomialIdeal x , monomialIdeal (x , x ), monomialIdeal (x x , x , 1 1 3 1 2 2 ----------------------------------------------------------------------- x x ), monomialIdeal x } 2 3 3 o25 : List``` ```i26 : dimStats(ideals,ShowTally=>true) o26 = (1.75, .433013, Tally{1 => 1}) 2 => 3 o26 : Sequence```

The first entry in the output of dimStats is the mean Krull dimension of the sample. The second entry is the standard deviation. Similarly, one can obtain the mean and standard deviations of the number of minimal generators and degree complexity via mingenStats, and the average Betti table shape, mean Betti table, and its standard deviation via bettiStats:

 ```i27 : mingenStats ideals o27 = (1.75, .829156, 1.25, .433013) o27 : Sequence``` ```i28 : bettiStats ideals 0 1 2 3 0 1 2 3 1 2 o28 = (total: 1 1 .5 .25, total: 1 1.75 1 .25, total: 2.00614 1.73205 0: 1 .75 .25 . 0: 1 1 .25 . 0: .707107 .433013 1: . .25 .25 .25 1: . .75 .75 .25 1: 1.29904 1.29904 ----------------------------------------------------------------------- 3 .433013) . .433013 o28 : Sequence```

For developing other models and computing statistics on objects other than monomial ideals, the package also defines a new Type, Sample, which allows for a convenient storage of statistics from a sample of algebraic objects and streamlines writing sample data into files.

For example, below we create a sample of size 10 over the Erdos-Renyi distribution B(n, D, p) on monomials over the ring Q[y,w] with D=4, and p=0.5, and then a sample of size 15 over the graded version of this distribution on monomials over the ring Z/101[z1..z8] with D=2, and p=0.25,0.5:

 ```i29 : sample1 = sample(ER(QQ[y,w],4,0.5),10) o29 = Sample{...4...} o29 : Sample``` ```i30 : sample2 = sample(ER(ZZ/101[z_1..z_8],2,{0.25,0.75}),15) o30 = Sample{...4...} o30 : Sample```

The output is a hashtable with 4 entries. To obtain the random sets of monomials (the actual data we are interested in), use the command getData:

 ```i31 : keys sample1 o31 = {SampleSize, ModelName, Data, Parameters} o31 : List``` ```i32 : sample2.Parameters ZZ o32 = (---[z , z , z , z , z , z , z , z ], 2, {.25, .75}) 101 1 2 3 4 5 6 7 8 o32 : Sequence``` `i33 : myData = getData(sample1);` ```i34 : myData_0 2 3 3 3 2 2 4 o34 = {w, w , y , w , y w, y w , w } o34 : List```

We can also use the Sample object to calculate the mean, standard deviation, and tally of the dimension of the ideals generated by the sample:

 ```i35 : statistics(sample(ER(CC[z_1..z_8],5,0.1),100), degree@@ideal) -- warning: experimental computation over inexact field begun -- results not reliable (one warning given per session) o35 = HashTable{Histogram => Tally{1 => 17}} 2 => 11 3 => 11 4 => 5 5 => 5 6 => 3 7 => 7 8 => 3 9 => 2 10 => 1 11 => 3 12 => 4 13 => 3 14 => 5 15 => 2 17 => 3 18 => 1 20 => 1 22 => 1 23 => 4 25 => 2 26 => 1 27 => 2 29 => 1 35 => 1 53 => 1 453 Mean => --- 50 StdDev => 9.15841 o35 : HashTable```

Most of the methods in this package offer various options, such as selecting a specific ring with which to work, or change variable names, coefficients, etc. Here is a simple example:

 `i36 : R=ZZ/101[a..e];` ```i37 : randomMonomialSets(R,D,p,N) 2 2 2 2 2 2 2 o37 = {{a, d, a , a*b, a*c, b , b*d, c , a c, a d, a e, a*b , a*b*e, a*c*e, ----------------------------------------------------------------------- 2 2 2 3 2 3 2 2 b d, b*d , b*e , d , d e, e }, {b, c, d, e, a , a*b, a*c, a*e, b , b*d, ----------------------------------------------------------------------- 2 3 2 2 2 2 2 b*e, c*d, c*e, d , d*e, a , a c, a*c , b*c , b*c*d, b*c*e, b*d , b*e , ----------------------------------------------------------------------- 3 2 3 2 2 3 2 2 2 c , c*d*e, c*e , d , d e, d*e , e }, {a, b, d, b , c , c*e, d*e, e , ----------------------------------------------------------------------- 3 2 2 2 2 2 2 2 a , a b, a d, a e, a*b , a*b*c, a*c , a*c*e, a*d*e, b e, b*c , b*c*d, ----------------------------------------------------------------------- 2 2 2 2 2 3 2 b*d , b*d*e, c d, c e, c*d , d e, e }, {a, b, d, a*b, a*d, a*e, b , ----------------------------------------------------------------------- 2 2 3 2 2 2 2 2 b*e, c , d , a , a c, a d, a e, a*b*c, a*b*e, a*c*d, a*d*e, a*e , b c, ----------------------------------------------------------------------- 2 2 3 2 2 b d, b e, b*c*e, c , c*e , d e}} o37 : List``` ```i38 : randomMonomialSets(n,D,p,N,VariableName=>"t") 2 2 2 3 2 2 2 2 2 2 o38 = {{t , t , t t , t , t , t , t t , t t }, {t , t t , t , t , t t , t t , 2 1 1 2 2 3 1 1 3 2 3 2 1 3 2 3 1 3 1 2 ----------------------------------------------------------------------- 3 3 3 2 2 2 2 3 t t t , t , t }, {t , t t , t t , t , t t , t t , t t , t t , t }, {t , 1 2 3 2 3 3 1 3 2 3 1 1 3 1 2 2 3 2 3 3 1 ----------------------------------------------------------------------- 2 3 2 2 2 3 t , t t , t t , t , t , t t , t t t , t t , t t , t }} 3 1 2 1 3 2 1 1 2 1 2 3 1 3 2 3 3 o38 : List```

In some cases, we may want to work directly with the sets of randomly chosen monomials, while at other times it may be more convenient to pass directly to the random monomial ideals. Both options induce the same distribution on monomial ideals:

 ```i39 : randomMonomialSets(3,4,1.0,1) 2 2 2 3 2 2 2 o39 = {{x , x , x , x , x x , x x , x , x x , x , x , x x , x x , x x , 1 2 3 1 1 2 1 3 2 2 3 3 1 1 2 1 3 1 2 ----------------------------------------------------------------------- 2 3 2 2 3 4 3 3 2 2 2 2 2 x x x , x x , x , x x , x x , x , x , x x , x x , x x , x x x , x x , 1 2 3 1 3 2 2 3 2 3 3 1 1 2 1 3 1 2 1 2 3 1 3 ----------------------------------------------------------------------- 3 2 2 3 4 3 2 2 3 4 x x , x x x , x x x , x x , x , x x , x x , x x , x }} 1 2 1 2 3 1 2 3 1 3 2 2 3 2 3 2 3 3 o39 : List``` ```i40 : monomialIdeal flatten oo o40 = monomialIdeal (x , x , x ) 1 2 3 o40 : MonomialIdeal of QQ[x , x , x ] 1 2 3``` ```i41 : randomMonomialIdeals(3,4,1.0,1) o41 = {monomialIdeal (x , x , x )} 1 2 3 o41 : List```

• randomMonomialSet -- randomly generates a list of monomials in fixed number of variables up to a given degree
• Verbose -- optional input to request verbose feedback
• Sample -- a type used to store a sample from a statistical model

## Authors

• Parker Joncus
• Richard Osborn
• Monica Yun
• Genevieve Hummel

## Version

This documentation describes version 1.0 of RandomMonomialIdeals.

## Source code

The source code from which this documentation is derived is in the file RandomMonomialIdeals.m2.

## Exports

• Types
• Model -- a type used to store a statistical model and its parameters
• Sample -- a type used to store a sample from a statistical model
• Functions and commands
• bettiStats -- statistics on Betti tables of a sample of monomial ideals
• borelFixedStats -- fraction of Borel-fixed monomial ideals in the given list
• CMStats -- fraction of monomial ideals in the given list whose quotient ring is Cohen-Macaulay
• degStats -- statistics on the degrees of a list of monomial ideals
• dimStats -- statistics on the Krull dimension of a list of monomial ideals
• ER -- model for sampling from Erdos-Renyi type distributions on monomials
• getData -- get the underlying samples
• idealsFromGeneratingSets -- creates ideals from sets of monomials
• mingenStats -- statistics on the minimal generators of a list of monomial ideals: number and degree complexity
• pdimStats -- statistics on projective dimension of a list of monomial ideals
• randomMonomialIdeals -- generates random sets of monomial ideals
• randomMonomialSet -- randomly generates a list of monomials in fixed number of variables up to a given degree
• randomMonomialSets -- randomly generates lists of monomials in fixed number of variables up to a given degree
• regStats -- statistics on the regularities of a list of monomial ideals
• sample -- generates a Sample object sampling from the given Model
• statistics -- generate statistics for a sample
• writeSample -- write sample to a file
• Methods
• getData(Sample), see getData -- get the underlying samples
• sample(Model,ZZ), see sample -- generates a Sample object sampling from the given Model
• statistics(Sample,Function), see statistics -- generate statistics for a sample
• writeSample(Sample,String), see writeSample -- write sample to a file
• Symbols
• Coefficients -- optional input to choose the coefficients of the ambient polynomial ring
• CountPure -- optional input to show the number of objects in the list whose Betti tables are pure
• Histogram -- return value for statistics
• IncludeZeroIdeals -- optional input to choose whether or not zero ideals should be included
• Mean -- return value for statistics
• ModelName -- model name from Sample
• Parameters -- model parameters from Sample
• SampleSize -- size of the sample
• SaveBettis -- optional input to store all Betti tables computed
• ShowTally -- optional input to choose if the tally is to be returned
• StdDev -- return value for statistics
• VariableName -- optional input to choose the variable name for the generated polynomials
• Verbose -- optional input to request verbose feedback