In this chapter we shall prove that Schreyer's method to compute syzygies
(cf. [S1], [S2], [E]) extends to any semigroup ordering < on
.
For the treatment of syzygies in a different
context, or for different algorithms see [M2], [Ba], [MM],
[MMT] and
[LS].
Let
be a standard basis of
.
For we choose the following Schreyer ordering <_{1} (depending on S): if and only if either or and i > j.
For g_{i}, g_{j} having the leading term in the same component, that is we consider spoly (g_{i}, g_{j}) := m_{ji}g_{i} - m_{ij}g_{j} with .
Because S is a standard basis we obtain (Corollary 1.11)
For j > i such that g_{i}, g_{j} have leading term in the same component, let
Let ker denote the module of syzygies, syz(I), of . The following proposition is essentially due to Schreyer.
Proof: 1) holds by definition of <_{1}.
To prove 2) it has to be shown that (Definition 1.3).
Let
,
that is
syz(I), and
let
with respect to <_{1}. Let
But
implies
,
that is
,
which proves
the proposition.
The principle of the algorithm is now easy.
Let S be a standard basis of . We may assume that L(s') for different .
Let .
W := Syz
INPUT: S, a standard basis
OUTPUT: W, the module of syzygies of S
T := initSyz
INPUT: S, a standard basis
OUTPUT: T, the set
h := NF(s|T)
INPUT: S, a polynomial vector to reduce
T, a set of polynomials with which to reduce
OUTPUT: h, the reduced ponyomial vector
Here we use on the following ordering <_{2}:
If and then m e_{j} <_{2} n e_{i} for all monomials .
On respectively we use the extension of < (respectively <_{1}) described in Chapter 1.
The algorithm is extremely sensitive with respect to the ordering of the standard basis S of the input.
Assuming that the set L is ordered as in Chapter 1, then S should be ordered in an opposite manner to Chapter 1, that is it should be ordered by decreasing monomial ordering. This produces potentially more syzygies of smaller degree at the beginning.
Because of Proposition 4.1 we know the leading term of the
s-polynomial of a pair in L without conputing the s-polynomial. If
this leading term is divisible by another one, the pair can be cancelled from
L.
The algorithm ``Standard basis'' of paragraph 1, together with repeated application of the algorithm ``Syz'', provides an effective way to construct finite Loc_{;}SPMlt; K[x]-free resolutions and gives a sharpened version of Hilbert's syzygy theorem which generalizes Schreyer's proof (cf. [E], [S1], [S2]).
Let be a standard basis of . We assume that the leading terms are a basis vector of K[x]^{r}, that is . We set s.t. and for we choose exactly one such that . Then ILoc_{;}SPMlt; K[x] is a free Loc_{;}SPMlt; K[x]-module with basis and (Loc _{;}SPMlt; K[x])^{r}/ILoc_{;}SPMlt;K[x] is Loc_{;}SPMlt; K[x]-free with basis represented by the .
Proof: Let us renumber the g_{i} such that
for .
First of all, the subset
remains a standard basis of I since the set of
leading terms is not changed. Hence, we may assume that all leading terms are
different.
By Proposition 1.4,
generates ILoc_{;}SPMlt; K[x]. Now consider a relation
After clearing denominators we may assume that . Since the leading terms involve different e_{i} on each side, we obtain . This shows that the are linear independent and that the are independent modulo ILoc_{;}SPMlt; K[x]. Since generate L(K[x]^{r})=(e_{1},...,e_{r})K[x] is a standard basis of K[x]^{r} this set generates by Corollary 1.11. Therefore, generates over Loc_{;}SPMlt; K[x].
Proof: For i < j and , we have with . Therefore, does not depend on .
Let q_{1} := q and the morphism given by , , and the analog morphism given by the standard basis , . Applying the same construction as above to syz and we obtain a standard basis of szy^{2}(I) := syz(syz(I)) = ker such that the leading terms of do not depend on .
Continuing in the same way we obtain an exact sequence
Moreover, ker syz^{n-s}(I) has a standard basis such that none of the variables appear in . Hence, by the preceding lemma, becomes free after tensoring with Loc_{;}SPMlt;K[x]. If we tensor the whole sequence with Loc_{;}SPMlt;K[x] it stays exact (since Loc_{;}SPMlt;K[x] is K[x]-flat) and is the desired free resolution of M.
Example 4.5
ab+14766ac-12713bc+8997ad+1878ae,
ac+9210bc+9399ad+13903bd-9583ae,
bc-13988ad-4712bd+6771ae-7341be,
ad-2340bd-7515cd+1575ae-4211be,
bd+5023cd-874ae+4773be+14016ce,
cd+1617ae-14718be-1384ce+12060de,
a^{3}-10731b^{3}+5818ae^{2}+13936be^{2}+11725ce^{2}+6401de^{2},
b^{3}-4862c^{3}-2334ae^{2}+9991be^{2}+14579ce^{2}+10173de^{2},
c^{3}-6087d^{3}+1135ae^{2}+4570be^{2}+5250ce^{2}+1393de^{2},
d^{3}+11392ae^{2}+7125be^{2}-15188ce^{2}-12706de^{2}-10957e^{3};
(
a, b, c, d, e the order of the variables)
ab-2302ac+1504bc-2175ad-13468bd-8487ae+2984be,
ac+7021bd-2524ad-8459bd+4807cd-4372ae-1908be,
bc-1768ad+12994bd+7816cd-7083ae+2769be-354ce,
ad+8219bd-13765cd+14989ae+36be-4732ce+8648de,
a^{3}-7986a^{2}e-744b^{2}e+2389c^{2}e-7991bde+11075cde-15425d^{2}e+7645ae^{2}-1871be^{2}+869
8ce^{2}-9609de^{2},
a^{2}e+3582b^{2}e-6012c^{2}e-14933bde+14203cde+11560d^{2}e+2294ae^{2}+12826be^{2}-12284ce^
2+10870de^{2},
b^{2}e+3097c^{2}e+10611bde+6826cde+2785d^{2}e-14231ae^{2}+13731be^{2}-1863ce^{2}+8227de^{2},
c^{2}e-8559bde+13444cde+3372d^{2}e+5235ae^{2}+9139be^{2}-7685ce^{2}+3756de^{2},
bde-14077cde-2960d^{2}e-4481ae^{2}-3950be^{2}-850ce^{2}-14832de^{2},
cde-13603d^{2}e+4327ae^{2}+15554be^{2}+2054ce^{2}-12484de^{2},
b^{3}+7339d^{2}e-3253ae^{2}+8720be^{2}+9224ce^{2}-11849de^{2},
c^{3}-9222d^{2}e-12818ae^{2}-11519be^{2}+6703ce^{2}-10364de^{2},
d^{3}+4730d^{2}e+7627ae^{2}+14168be^{2}+11428ce^{2}+8632de^{2},
d^{2}e+9376ae^{2}+6688be^{2}-11914ce^{2}-295de^{2}-5576e^{3};
(a,b,c,d,e the order of the variables)
( the order of the variables)
For these examples we computed a minimal resolution with MACAULAY and SINGULAR using the regularity bound (cf. [E]) with the ordering degrevlex (in both systems realized as scripts; without this bound the computation is, at least for complicated examples, usually much slower) and computed a resolution with Schreyer's method (SING/SCHREYER).
vars denotes the number of variables, minbase the number of a minimal system
of generators, stdbase the number of elements in the standard base and dim the
dimension of the zero-set of the ideal.
For versions and notations cf. Chapter 3.
SING | |||||||
[-1.5ex]MAC | [-1.5ex]SING | SCHREYER | [-1.5ex]vars | [-1.5ex]dim | [-1.5ex]minbase | [-1.5ex]stdbase | |
1. | 552 | 96 | 13769 | 5 | 3 | 3 | 63 |
2. | 2222 | 87 | 6293 | 5 | 3 | 3 | 82 |
3. | 16 | 5 | 9 | 4 | 1 | 3 | 75 |
4. | 20 | 5 | 7 | 4 | 1 | 3 | 44 |
5. | 10 | 2 | 9 | 4 | 2 | 3 | 83 |
6. | 12 | 2 | 23 | 5 | 2 | 3 | 22 |
7. | 4 | 12 | 542 | 5 | 4 | 15 | 138 |
8. | 14 | 1 | 1 | 5 | 4 | 3 | 38 |
9. | 238 | 91 | 1228 | 5 | 1 | 5 | 76 |
10. | 299 | 322 | 15 | 6 | 1 | 5 | 38 |
11. | 950 | 166 | 2412 | 5 | 0 | 5 | 142 |
12. | 49 | 24 | 3 | 6 | 0 | 15 | 22 |
13. | 44 | 23 | 31 | 5 | 2 | 3 | 25 |
14. | 101 | 60 | 1 | 5 | 0 | 10 | 19 |
15. | 78 | 23 | 2 | 5 | 0 | 14 | 23 |
16. | 1 | 1 | 12 | 5 | 2 | 4 | 23 |
17. | 2 | 4 | 3 | 9 | 2 | 27 | 27 |
18. | 20 | 29 | 22 | 10 | 2 | 35 | 35 |
19. | 12 | 7 | 6 | 4 | 0 | 6 | 31 |
20. | 825 | 446 | 7958 | 4 | 0 | 6 | 192 |