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],
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 gi, gj having the leading term in the same component, that is we consider spoly (gi, gj) := mjigi - mijgj with .
Because S is a standard basis we obtain (Corollary 1.11)
For j > i such that gi, gj 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).
with respect to <1. Let
The principle of the algorithm is now easy.
Let S be a standard basis of . We may assume that L(s') for different .
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 ej <2 n ei 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
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 gi such that
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
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 ei 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)=(e1,...,er)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 q1 := 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 szy2(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 syzn-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.
( a, b, c, d, e the order of the variables)
(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.