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 2
o10 = ideal (a*b*c - d*e*f, a c - d f, - b*c*d + a*e*f, a - d , - c*d + 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 acd-acf a2c-a2f+acf-d2f -a2f+acf
{3} | 0 0 aef-def abe-bde 0 a3-d3 -bcd-ace+bcf+aef ace-bcf-aef+def abc+ace-bcf-aef
{3} | a2+ad+d2 abc-def acd+adf+d2f abd+bd2+d2e 0 0 d2f-df2 cd2-adf-d2f+df2 cd2-adf-d2f+df2
{3} | -bc-ef 0 -bcf-cef -b2c-bce -abc+def -a2c+d2f c2e-cef -bc2-c2e+bcf+cef -bc2-c2e+bcf+cef
{3} | 0 0 0 0 0 0 -cde+def cde-def cde-def
---------------------------------------------------------------------------------------------------------------------------
a2d-a2f a2e+bdf+aef d3-d2f 0 0 0 cd2-af2 0 ad2-adf 0 abc2-def2
-a2e+ade ae2-bef a2e-d2e -ade+abf 0 a2c-df2 0 cd2-af2 -ade+bdf 0 -b2c2+e2f2
d3-d2f ade+d2e+abf ad2-adf -d3+d2f -cd2+af2 0 0 0 0 0 bcdf-acef
-bcd+ace-cde+bcf -bce-ce2 -ace+ef2 cde-bcf 0 -ac2+f3 0 0 cde-bf2 cd2-af2 0
-ade+d2e -abe+de2 -a2e+ade bd2-d2e bcd-aef acd-a2f abc-def a2c-d2f a2b-d2e a3-d3 0
---------------------------------------------------------------------------------------------------------------------------
ac2f-df3 ab2c+bdef+ae2f cdef-bcf2 |
ac2e-bc2f-acef+ef3 -b3c+abe2+ae3-be2f 0 |
cdf2-af3 bd2e+d2e2+b2df -bc2d+ef3 |
-c3e+c2ef -bce2-ce3 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 acd-acf a2c-a2f+acf-d2f -a2f+acf
{3} | 0 0 aef-def abe-bde 0 a3-d3 -bcd-ace+bcf+aef ace-bcf-aef+def abc+ace-bcf-aef
{3} | a2+ad+d2 abc-def acd+adf+d2f abd+bd2+d2e 0 0 d2f-df2 cd2-adf-d2f+df2 cd2-adf-d2f+df2
{3} | -bc-ef 0 -bcf-cef -b2c-bce -abc+def -a2c+d2f c2e-cef -bc2-c2e+bcf+cef -bc2-c2e+bcf+cef
{3} | 0 0 0 0 0 0 -cde+def cde-def cde-def
---------------------------------------------------------------------------------------------------------------------------
a2d-a2f a2e+bdf+aef d3-d2f 0 0 0 cd2-af2 0 ad2-adf 0 abc2-def2
-a2e+ade ae2-bef a2e-d2e -ade+abf 0 a2c-df2 0 cd2-af2 -ade+bdf 0 -b2c2+e2f2
d3-d2f ade+d2e+abf ad2-adf -d3+d2f -cd2+af2 0 0 0 0 0 bcdf-acef
-bcd+ace-cde+bcf -bce-ce2 -ace+ef2 cde-bcf 0 -ac2+f3 0 0 cde-bf2 cd2-af2 0
-ade+d2e -abe+de2 -a2e+ade bd2-d2e bcd-aef acd-a2f abc-def a2c-d2f a2b-d2e a3-d3 0
---------------------------------------------------------------------------------------------------------------------------
ac2f-df3 ab2c+bdef+ae2f cdef-bcf2 |
ac2e-bc2f-acef+ef3 -b3c+abe2+ae3-be2f 0 |
cdf2-af3 bd2e+d2e2+b2df -bc2d+ef3 |
-c3e+c2ef -bce2-ce3 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
|