Macaulay2 » Documentation
Packages » Macaulay2Doc » rings » polynomial rings » monomial orderings » monomial orders for free modules » Schreyer orders
next | previous | forward | backward | up | index | toc

# Schreyer orders -- induced monomial order on a free module

The Schreyer order is a monomial order on a free module that is particularly efficient for computing Gröbner bases and syzygies. The size of Gröbner bases of submodules using such orders is often much much smaller than if a position over term or term over position order would be used. We call these Schreyer orders, after Frank-Olaf Schreyer, who used them to give an algorithm for syzygies, and who also recognized many of their beneficial properties. See [S1] and [S2] for the algorithm, and [LS] for improvements and details on the implementation in Macaulay2

- [LS] Strategies for computing minimal free resolutions.(R. LaScala and M. Stillman, J. Symb. Comp. 26, 409-431, 1998).
- [S1] Die Berechnung von Syzygien mit dem verallgemeinerten Weierstrassschen Divisionssatz.(F.-O. Schreyer, Diplomarbeit, Hamburg, 1980).
- [S2] A standard basis approach to syzygies of canonical curves.F.-O. Schreyer, J. reine angew. Math. 421, 83-123 (1991)

Given a free $R$-module $G$, a set of monomials $m_0, \ldots, m_{s-1}$ of $G$, and a monomial order on the monomials of $G$, the induced order, or, Schreyer order on $F = R^s$ is defined by: $a F_i > b F_j$ (in $F$) iff $a m_i > b m_j$ (in $G$), or $a m_i and b m_j$ are scalar multiples of each other, and $i>j$, where $F_i$ are the unit column vectors of $F$. Typically the monomials $m_0, \ldots, m_{s-1}$ are the initial monomials of a Gröbner basis of a submodule of $G$.

In Macaulay2, free modules with a Schreyer order on them can be created using schreyerOrder(Matrix).

    i1 : R = ZZ/101[a..f];

    i2 : m = matrix{{a,b,c,d}};

                 1      4
    o2 : Matrix R  <-- R

    i3 : m1 = schreyerOrder m

    o3 = | a b c d |

                 1      4
    o3 : Matrix R  <-- R

    i4 : F = source m1

          4
    o4 = R

    o4 : R-module, free, degrees {4:1}

    i5 : g = syz m1

    o5 = {1} | -b 0  -c 0  0  -d |
         {1} | a  -c 0  0  -d 0  |
         {1} | 0  b  a  -d 0  0  |
         {1} | 0  0  0  c  b  a  |

                 4      6
    o5 : Matrix R  <-- R

    i6 : leadTerm g

    o6 = {1} | 0 0 0 0 0 0 |
         {1} | a 0 0 0 0 0 |
         {1} | 0 b a 0 0 0 |
         {1} | 0 0 0 c b a |

                 4      6
    o6 : Matrix R  <-- R

In Macaulay2, free modules are displayed without any indication of whether they are endowed with a Schreyer order or not. To determine whether one is, use schreyerOrder(Module). If the result is the zero matrix, then the monomial order associated with this free module is not a Schreyer order. In that case, the monomial order for the free module is the one determined directly from the ring.

    i7 : schreyerOrder target m

    o7 = 0

                       1
    o7 : Matrix 0 <-- R

    i8 : schreyerOrder source g

    o8 = 0

                       6
    o8 : Matrix 0 <-- R

Over quotient rings, the multiplications $a m_i$ and $b m_j$ are over the ambient polynomial ring, not the quotient.

It is fine for the free module G above to be endowed with a Schreyer order too.

The only places that Schreyer orders are considered is in computation of Gröbner bases, syzygies, and free resolutions, and with the leadTerm routine.

The size of the Gröbner bases of syzygy modules is often dramatically smaller if the monomial order is the Schreyer order, as in the following example.

    i9 : R = QQ[a..f];

    i10 : I = ideal"abc-def,a2c-d2f,aef-bcd,a3-d3,af2-cd2"

                                 2     2                     3    3       2
    o10 = ideal (a*b*c - d*e*f, a c - d f, - b*c*d + a*e*f, a  - d , - c*d  +
          -----------------------------------------------------------------------
             2
          a*f )

    o10 : Ideal of R

    i11 : F = syz gens I

    o11 = {3} | a2+ad+d2 bcd-aef cd2+a2f+d2f a2b+bd2+ade a3-d3    0
          {3} | 0        0       aef-def     abe-bde     0        a3-d3
          {3} | a2+ad+d2 abc-def acd+adf+d2f abd+bd2+d2e 0        0
          {3} | -bc-ef   0       -bcf-cef    -b2c-bce    -abc+def -a2c+d2f
          {3} | 0        0       0           0           0        0
          -----------------------------------------------------------------------
          acd-acf          a2c-a2f+acf-d2f  -a2f+acf         a2d-a2f
          -bcd-ace+bcf+aef ace-bcf-aef+def  abc+ace-bcf-aef  -a2e+ade
          d2f-df2          cd2-adf-d2f+df2  cd2-adf-d2f+df2  d3-d2f
          c2e-cef          -bc2-c2e+bcf+cef -bc2-c2e+bcf+cef -bcd+ace-cde+bcf
          -cde+def         cde-def          cde-def          -ade+d2e
          -----------------------------------------------------------------------
          a2e+bdf+aef d3-d2f   0        0        0       cd2-af2 0       ad2-adf
          ae2-bef     a2e-d2e  -ade+abf 0        a2c-df2 0       cd2-af2 -ade+bdf
          ade+d2e+abf ad2-adf  -d3+d2f  -cd2+af2 0       0       0       0
          -bce-ce2    -ace+ef2 cde-bcf  0        -ac2+f3 0       0       cde-bf2
          -abe+de2    -a2e+ade bd2-d2e  bcd-aef  acd-a2f abc-def a2c-d2f a2b-d2e
          -----------------------------------------------------------------------
          0       abc2-def2  ac2f-df3            ab2c+bdef+ae2f     cdef-bcf2 |
          0       -b2c2+e2f2 ac2e-bc2f-acef+ef3  -b3c+abe2+ae3-be2f 0         |
          0       bcdf-acef  cdf2-af3            bd2e+d2e2+b2df     -bc2d+ef3 |
          cd2-af2 0          -c3e+c2ef           -bce2-ce3          0         |
          a3-d3   0          c2de-acef-cdef+aef2 -b2de+de3          b2c2-e2f2 |

                  5      23
    o11 : Matrix R  <-- R

    i12 : betti gens gb syz F

                  0  1
    o12 = total: 23 67
              5:  1  .
              6: 18 19
              7:  4 27
              8:  .  8
              9:  .  8
             10:  .  5

    o12 : BettiTally

    i13 : G = schreyerOrder F

    o13 = {3} | a2+ad+d2 bcd-aef cd2+a2f+d2f a2b+bd2+ade a3-d3    0
          {3} | 0        0       aef-def     abe-bde     0        a3-d3
          {3} | a2+ad+d2 abc-def acd+adf+d2f abd+bd2+d2e 0        0
          {3} | -bc-ef   0       -bcf-cef    -b2c-bce    -abc+def -a2c+d2f
          {3} | 0        0       0           0           0        0
          -----------------------------------------------------------------------
          acd-acf          a2c-a2f+acf-d2f  -a2f+acf         a2d-a2f
          -bcd-ace+bcf+aef ace-bcf-aef+def  abc+ace-bcf-aef  -a2e+ade
          d2f-df2          cd2-adf-d2f+df2  cd2-adf-d2f+df2  d3-d2f
          c2e-cef          -bc2-c2e+bcf+cef -bc2-c2e+bcf+cef -bcd+ace-cde+bcf
          -cde+def         cde-def          cde-def          -ade+d2e
          -----------------------------------------------------------------------
          a2e+bdf+aef d3-d2f   0        0        0       cd2-af2 0       ad2-adf
          ae2-bef     a2e-d2e  -ade+abf 0        a2c-df2 0       cd2-af2 -ade+bdf
          ade+d2e+abf ad2-adf  -d3+d2f  -cd2+af2 0       0       0       0
          -bce-ce2    -ace+ef2 cde-bcf  0        -ac2+f3 0       0       cde-bf2
          -abe+de2    -a2e+ade bd2-d2e  bcd-aef  acd-a2f abc-def a2c-d2f a2b-d2e
          -----------------------------------------------------------------------
          0       abc2-def2  ac2f-df3            ab2c+bdef+ae2f     cdef-bcf2 |
          0       -b2c2+e2f2 ac2e-bc2f-acef+ef3  -b3c+abe2+ae3-be2f 0         |
          0       bcdf-acef  cdf2-af3            bd2e+d2e2+b2df     -bc2d+ef3 |
          cd2-af2 0          -c3e+c2ef           -bce2-ce3          0         |
          a3-d3   0          c2de-acef-cdef+aef2 -b2de+de3          b2c2-e2f2 |

                  5      23
    o13 : Matrix R  <-- R

    i14 : betti gens gb syz G

                  0  1
    o14 = total: 23 45
              5:  1  .
              6: 18 19
              7:  4 22
              8:  .  4

    o14 : BettiTally

## See also

- leadTerm -- get the greatest term
- gb -- compute a Gröbner basis
- syz -- the syzygy matrix
- resolution -- projective resolution
- betti -- display or modify a Betti diagram

### Menu

- schreyerOrder -- create or obtain free modules with Schreyer monomial orders
- schreyerOrder(Matrix) -- create a matrix with the same entries whose source free module has a Schreyer monomial order
- schreyerOrder(Module) -- obtain Schreyer order information

The source of this document is in /build/macaulay2-88fgJW/macaulay2-1.25.11+ds/M2/Macaulay2/packages/Macaulay2Doc/ov_monomial_orderings.m2:369:0.