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 |