next | previous | forward | backward | up | top | index | toc | Macaulay2 web site
RandomMonomialIdeals :: RandomMonomialIdeals

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 types of 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 distribution, see Section 1 of https://arxiv.org/abs/1701.07130. As is customary, we use the word ‘model’ when referring to a distribution of the random objects at hand.

The model defined by B(n, D, p) was inspired by the Erdos-Renyi random graph model denoted by G(n,p): it is a natural generalization, as squarefree monomials of degree tww can be encoded by edges of a graph whose vertices are the variables. The random graph model can be introduced in two ways: one can either fix the probability of an edge or fix the total number of edges. Thus the package also includes the model variant that generates a fixed number of monomials:

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 since their 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 a fixed number of monomials to be minimal generating sets. We can also employ the minimal strategy for a couple of 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 (that is, a set of random objects) is generated, one can compute various statistics of algebraic properties of the sample. The methods in the package offer a way to compute and summarize statistics of some of the common properties, such as degree, dimension, projective dimension, Castelnuovo-Mumford regularity, etc. For example, we can use the method 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 the method 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 two new types of object, Model and Sample, which allow for 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 from the Erdos-Renyi distribution B(n, D, p) on monomials in Q[y,w] with D=4, and p=0.5, and then a sample of size 15 from the graded version of this distribution on monomials in 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 hash table with 4 entries. To obtain the random sets of monomials that were generated (that is, 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 object of type Sample to calculate the mean, standard deviation, and tally of the dimension of the ideals in 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 specifying 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 corresponding 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

See also

Authors

Certification a gold star

Version 1.0 of this package was accepted for publication in volume 9 of the journal The Journal of Software for Algebra and Geometry on 11 April 2019, in the article Random Monomial Ideals: a Macaulay2 package. That version can be obtained from the journal or from the Macaulay2 source code repository, http://github.com/Macaulay2/M2/blob/master/M2/Macaulay2/packages/RandomMonomialIdeals.m2, commit number 902570b14480e7590b6960b1352331acce3ef817.

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 data sample from a statistical model
  • Functions and commands
    • bettiStats -- statistics on Betti tables of a sample of monomial ideals or list of objects
    • borelFixedStats -- fraction of Borel-fixed monomial ideals in the given list
    • CMStats -- fraction of monomial ideals (or other objects) in the given list whose quotient ring is Cohen-Macaulay
    • degStats -- statistics on the degrees of a list of objects
    • dimStats -- statistics on the Krull dimension of a list of objects
    • 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 ideals: number and degree complexity
    • model -- creates a new model for random objects with a given list of parameters and generating function
    • pdimStats -- statistics on projective dimension of a list of objects
    • 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 objects
    • sample -- generates a sample from the given model
    • statistics -- generate statistics for a sample
    • writeSample -- write sample data to a directory
  • Methods
    • getData(Sample), see getData -- get the underlying samples
    • sample(Model,ZZ), see sample -- generates a sample from the given model
    • statistics(Sample,Function), see statistics -- generate statistics for a sample
    • writeSample(Sample,String), see writeSample -- write sample data to a directory
  • 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
    • Generate -- model construct function
    • Histogram -- a summary statistic for a list of objects
    • IncludeZeroIdeals -- optional input to choose whether zero ideals should be included
    • Mean -- a summary statistic for a list of objects
    • ModelName -- name of the model used to generate a given sample
    • Parameters -- values of the model parameters that were used to generate a given sample
    • SampleSize -- size of the random sample
    • SaveBettis -- optional input to store all Betti tables computed
    • ShowTally -- optional input to choose if the tally is to be returned
    • StdDev -- a summary statistic for a list of objects
    • VariableName -- optional input to choose the indexed variable name for the polynomial ring