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
|