Next: 5. Zariski's question, Milnor Up: Standard bases, syzygies and Previous: 3. Examples and comparisons

# 4. On Schreyer's method to compute syzygies

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 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)

with L(hij) < 1 if and .

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.

Proposition 4..1   With respect to the ordering <1 the following holds:

1)
.
2)
s.t. L(gi), L(gj) are in the same component is a standard basis for syz(I)

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

Then, obviously, is a syzygy of . Especially, . Choose l such that for some n and . Because and the definition of <1 we have k < l.
Since mL(gk) = nL(gl) we have

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 (S)
L := initPairs (T)
WHILE DO
p := (a, b, s) the last element from L

s := spoly(a,b)
h := NF(s|T)
h:= h(t = 1)
END

T := initSyz
INPUT:
S, a standard basis
OUTPUT:
T, the set

i := r;
WHILE DO
s := the first element from S
i := i+1

s := s + ei
END
T := Th.

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

h := s
WHILE exist such that for some DO
choose the first possible f with respect to the ordering in T such that is minimal
IF THEN

END
h := spoly
update (h)
END

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 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]).

Lemma 4..2

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 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 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].

Theorem 4..3   Let be a standard basis of . Order S in such a way that whenever L(gi) and L(gj) involve the same component, say and , then in the lexicographical ordering if i < j. If do not depend on the variables , then the do not depend on the variables and

has a Loc;SPMlt; K[x]-free resolution of length . In particular, M always has a free resolution of length and, by Serre's theorem, is a regular ring.

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.

Remark 4..4   The above algorithm almost never gives a minimal free resolution (in the local or in the homogeneous case), on the contrary, every syzygy module is generated by a standard basis. In SINGULAR it is implemented with an option to cancel superfluous free factors in an additional step. Because of the non-minimality there are more reductions necessary than in the usual implementations of free resolutions. On the other hand, since we know explicitly a standard basis of the syzygy modules (for some ordering) by Proposition 4.1, we have an advantage. An effective implementation of the above algorithm requires avoiding comparisons of monomials with respect to the Schreyer ordering. We proceed in the following manner. Instead of computing directly the monomials of the syzygies we compute their product with the corresponding monomial defining the Schreyer ordering (weight monomial). This can be realized by an adapted initialization (just exchange the line s := s + ei in the procedure initSyz described above by with for a suitable k). This allows use of the initial ordering during the whole resolution. At the end we have, of course, to divide by the weight monomial to obtain the resolution. The results of our testing of the above method, and its comparison to other methods, is given at the end of this chapter. We see there that it is usually faster to compute a minimal free resolution by fixing an ordering and minimizing the syzygy module step by step if we are closed to complete intersections and, if we are far away from complete intersections, Schreyer's method seems to be faster. SINGULAR offers both possiblities.

Example 4.5

1.
the homogenization of Example 1 in Chapter 3 with respect to w
( t, x, y, z, w the order of the variables)

2.
the previous example with (w, t, x, y, z the order of the variables)

3.
the homogenization of Example 3 in Chapter 3 with respect to w
(w,x,y,z the order of the variables)

4.
the homogenization of Example 5 in Chapter 3 with respect to w
( w, x, y, z the order of the variables)

5.
the homogenization of Example 12 in Chapter 3 with respect to w
( t, x, y, z, w the order of the variables)

6.
the homogenization of Example 8 in Chapter 3 with respect to w
(w, x, y the order of the variables)

7.

the ideal where .

8.
Sparse
t18x2 - t19z - t18z2,
t26xy - t17z - t25z3,
t38y2 - t37xyw;
(t, x, y, z, w the order of the variables)

9.
five homogeneous random polynomials of degree 3 in the variables a, b, c, d, e

10.
cyclic roots 5
a + b + c + d + e,
de + cd + bc + ae + ab,
cde + bcd + ade + abe + abc,
bcde + acde + abde + abce + abcd,
abcde - h5;
( a, b, c, d, e, h the order of the variables)

11.
Kahn4
a4 - b4,
b4 - c4,
c4 - d4,
d4 - e4,
a3 b + b3c + c3 d + d3 e + e3a;
( a, b, c, d, e the order of the variables)

12.
Iarrobino
xy + y2 + uz - wz - xz + yz,
x2 - y2 + uz - wz - xz +z2,
wy,
wx - uz + yz,
w2 - y2 + uz - z2,
vz - yz - z2,
vy - y2 - wz + xz + yz + z2,
vx - y2 + uz + yz - z2,
vw - y2 + uz + yz - z2,
v2 + y2 + uz - xz - yz - z2,
uy + y2 + yz,
ux - y2 + wz - xz - z2,
uw - y2 + uz + yz - z2,
uv - y2 - xz + yz,
u2 + yz;
(u, v, w, x, y, z the order of the variables)

13.
three homogeneous random polynomials of degree 5 in the variables a, b, c, d, e

14.
Schreyer 1
polynomials created in a certain random manner such that the ideal generates a 0-dimensional Gorenstein ring in characteristic 31991.

bd+5023cd-874ae+4773be+14016ce,
cd+1617ae-14718be-1384ce+12060de,
a3-10731b3+5818ae2+13936be2+11725ce2+6401de2,
b3-4862c3-2334ae2+9991be2+14579ce2+10173de2,
c3-6087d3+1135ae2+4570be2+5250ce2+1393de2,
d3+11392ae2+7125be2-15188ce2-12706de2-10957e3;
( a, b, c, d, e the order of the variables)

15.
Schreyer 2
polynomials created as in 14

a3-7986a2e-744b2e+2389c2e-7991bde+11075cde-15425d2e+7645ae2-1871be2+869 8ce2-9609de2,
a2e+3582b2e-6012c2e-14933bde+14203cde+11560d2e+2294ae2+12826be2-12284ce^ 2+10870de2,

b2e+3097c2e+10611bde+6826cde+2785d2e-14231ae2+13731be2-1863ce2+8227de2,
c2e-8559bde+13444cde+3372d2e+5235ae2+9139be2-7685ce2+3756de2,
bde-14077cde-2960d2e-4481ae2-3950be2-850ce2-14832de2,
cde-13603d2e+4327ae2+15554be2+2054ce2-12484de2,
b3+7339d2e-3253ae2+8720be2+9224ce2-11849de2,
c3-9222d2e-12818ae2-11519be2+6703ce2-10364de2,
d3+4730d2e+7627ae2+14168be2+11428ce2+8632de2,
d2e+9376ae2+6688be2-11914ce2-295de2-5576e3;
(a,b,c,d,e the order of the variables)

16.
caprasse 4
-2w2x - w2z + 2 xyt + y2z
2w4+4w2x2 + 4w2xz - 10w2y2 - 10w2y2 - 10w2yt-x3z+4x2yt+4xy2z+2y3t
-w2x - 2w2z + xt2 + 2yzt
2w4 + 4w2xz - 10w2yt + 4w2z2 - 10w2t2 - xz3 + 4yz2t + 2yt3;
(w, x, y, z, t the order of the variables)

17.
Pellikaan, Jaworski S(9)
S(m) denotes the set of polynomials (describing a minimal elliptic Gorenstein surface singularity), defined inductively:

( the order of the variables)

18.
Pellikaan, Jaworski S(10)
compare example 17

19.
9 random i-forms in 4 variables,

20.
6 random i-forms in 4 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

Next: 5. Zariski's question, Milnor Up: Standard bases, syzygies and Previous: 3. Examples and comparisons
| ZCA Home | Reports |