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 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 }}
         2 3   3   1 2     3   1   2     1   3   2     1 2   1 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     2                 3   3           2   2     3  
o18 = {{x , x x x , x x , x x }, {x , x x x , x , x }, {x , x x , x x , x },
         3   1 2 3   1 2   1 3     1   1 2 3   2   3     3   1 3   1 3   1  
      -----------------------------------------------------------------------
              2   2     2
      {x , x x , x x , x x }}
        2   1 3   1 2   2 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   3         3     2   2           3     2   2         
o22 = {{x , x x , x , x }, {x , x , x x , x x }, {x , x , x x , x x }, {x ,
         3   1 2   2   1     1   2   2 3   2 3     2   1   1 3   1 3     3 
      -----------------------------------------------------------------------
         2   3   2
      x x , x , x x }}
       1 2   1   1 2

o22 : List
i23 : randomMonomialSets(n,D,{0.0,0.3,0.5},N, Strategy=>"Minimal")

               3   2       2   3   3           2   3   3                 3 
o23 = {{x x , x , x x , x x , x , x }, {x x , x , x , x }, {x x , x x , x ,
         1 3   1   1 2   1 2   2   3     1 2   2   1   3     1 3   2 3   1 
      -----------------------------------------------------------------------
       2       2   3     2     3   2     3
      x x , x x , x }, {x x , x , x x , x }}
       1 2   1 2   2     1 2   2   2 3   3

o23 : List
i24 : randomMonomialSets(n,D,0.1,N, Strategy=>"Minimal")

                              3     2     2
o24 = {{x }, {0}, {x , x x , x }, {x , x x }}
         2          1   2 3   3     3   1 2

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)

                                                                          
o25 = {monomialIdeal (x x , x ), monomialIdeal (x , x , x ), monomialIdeal
                       1 2   3                   1   2   3                
      -----------------------------------------------------------------------
        2   2   2
      (x , x , x ), monomialIdeal (x x , x )}
        1   2   3                   1 2   3

o25 : List
i26 : dimStats(ideals,ShowTally=>true)

o26 = (.5, .5, Tally{0 => 2})
                     1 => 2

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 = (2.5, .5, 1.75, .433013)

o27 : Sequence
i28 : bettiStats ideals

              0   1   2   3         0    1   2   3               1       2
o28 = (total: 1 1.5   1  .5, total: 1  2.5   2  .5, total: 2.17945 3.09808
           0: 1 .75 .25 .25      0: 1 1.25 .75 .25      0: 1.08972 1.29904
           1: . .75  .5   .      1: . 1.25  .5   .      1: 1.08972      .5
           2: .   . .25   .      2: .    . .75   .      2:       . 1.29904
           3: .   .   . .25      3: .    .   . .25      3:       .       .
      -----------------------------------------------------------------------
            3
      .866025)
      .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

              3   2 2   4
o34 = {y, w, y , 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 => 12 }}
                                   2 => 10
                                   3 => 10
                                   4 => 5
                                   5 => 8
                                   6 => 8
                                   7 => 7
                                   8 => 5
                                   9 => 1
                                   10 => 1
                                   11 => 7
                                   12 => 4
                                   14 => 1
                                   15 => 5
                                   16 => 1
                                   17 => 1
                                   18 => 1
                                   20 => 1
                                   22 => 1
                                   25 => 1
                                   26 => 1
                                   27 => 3
                                   30 => 2
                                   37 => 2
                                   77 => 1
                                   131 => 1
                        1059
                Mean => ----
                         100
                StdDev => 16.1097

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 
o37 = {{a, d, a*e, c , c*e, a d, a e, a*b*c, a*b*e, a*c , a*c*d, a*c*e, a*d ,
      -----------------------------------------------------------------------
                2   2    2      2            2            2   3   2          
      a*d*e, a*e , b c, b d, b*c , b*c*d, b*d , b*d*e, b*e , c , c e, c*d*e},
      -----------------------------------------------------------------------
                          2        2   2    2    2    2      2               
      {b, b*c, b*d, b*e, c , c*e, d , a b, a c, a d, a e, a*b , a*b*c, a*b*d,
      -----------------------------------------------------------------------
                     2                  3   2    2      2     2   3   2  
      a*b*e, a*c*d, b d, b*c*e, b*d*e, c , c d, c e, c*d , c*e , d , d e,
      -----------------------------------------------------------------------
         2           2   2             2             2   3   2         
      d*e }, {b, d, a , b , b*c, b*d, c , c*d, d*e, e , a , a e, a*b*c,
      -----------------------------------------------------------------------
                                   3   2    2                    2   2  
      a*b*d, a*b*e, a*c*d, a*d*e, b , b c, b d, b*c*d, b*c*e, b*e , c e,
      -----------------------------------------------------------------------
                2   3     2           2                  2        2   2  
      c*d*e, c*e , d , d*e }, {a, c, a , a*b, a*d, a*e, b , b*e, d , a c,
      -----------------------------------------------------------------------
       2                                3   2    2           2    3   2  
      a e, a*b*e, a*c*d, a*c*e, a*d*e, b , b c, b e, b*d*e, c e, d , d e,
      -----------------------------------------------------------------------
       3
      e }}

o37 : List
i38 : randomMonomialSets(n,D,p,N,VariableName=>"t")

             2         2   3     2   3     2             2         2   3 
o38 = {{t , t , t t , t , t , t t , t , t t }, {t , t , t , t t , t , t ,
         3   1   1 2   2   1   1 2   2   2 3     1   3   1   2 3   3   1 
      -----------------------------------------------------------------------
       2       2     2   3   2                                 3   2       2 
      t t , t t , t t , t , t t }, {t , t , t t , t t , t t , t , t t , t t ,
       1 2   1 2   1 3   2   2 3     1   2   1 2   1 3   2 3   1   1 3   1 3 
      -----------------------------------------------------------------------
       3                             2   2       2           3   2     3
      t }, {t , t , t , t t , t t , t , t t , t t , t t t , t , t t , t }}
       2     1   2   3   1 2   1 3   3   1 3   1 2   1 2 3   2   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

See also

Authors

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