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 $K[x]^r = \sum^r_{i=1} K[x] e_i$. For the treatment of syzygies in a different context, or for different algorithms see [M2], [Ba], [MM], [MMT] and [LS].
Let $S = \{g_1, \ldots, g_q\}$ be a standard basis of $I \subseteq K[x]^r$.

For $K[x]^q = \sum^{q+r}_{i=r+1} K[x] e_i$ we choose the following Schreyer ordering <₁ (depending on S): $x^\alpha e_{i+r} <_1 x^\beta e_{j+r}$ if and only if either $L(x^\alpha g_i) < L(x^\beta g_j)$ or $L(x^\alpha g_i) = L(x^\beta g_j)$ and i > j.

For g_i, g_j having the leading term in the same component, that is $L(g_i) = x^{\alpha_i} e_k, L(g_j) = x^{\alpha_j} e_k$ we consider spoly (g_i, g_j) := m_jig_i - m_ijg_j with $m_{ji} = c(g_j) {lcm(L(g_i),\, L(g_j))\over x^{\alpha_i}}$.

Because S is a standard basis we obtain (Corollary 1.11)

$$(1 + h_{ij}) (m_{ji} g_i - m_{ij} g_j) = \sum \xi^{ij}_\nu g_\nu$$

with L(h_ij) < 1 if $h_{ij} \not= 0$ and $L(\xi^{ij}_\nu g_\nu) < L(m_{ji}g_i)$.

For j > i such that g_i, g_j have leading term in the same component, let

$$\tau_{ij} := (1 + h_{ij}) (m_{ji} e_{i+r} - m_{ij} e_{j+r}) - \sum \xi^{ij}_\nu e_{\nu + r}.$$

Let ker $(K[x]^q \to K[x]^r, \sum w_i e_{i+r} \mapsto \sum w_i g_i)$ denote the module of syzygies, syz(I), of $\{g_1, \ldots, g_q\}$. The following proposition is essentially due to Schreyer.

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

1)

$L(\tau_{ij}) = m_{ji} e_{i+r}$.

2)

$\{\tau_{ij} \mid i < j$ s.t. L(g_i), L(g_j) are in the same component $\}$ is a standard basis for syz(I)

Proof: 1) $L(\tau_{ij}) = L(m_{ji} e_{i+r} - m_{ij} e_{j+r}) = m_{ji} e_{i+r}$ holds by definition of <₁.

To prove 2) it has to be shown that $L(\mbox{syz}(I)) = \langle\{m_{ji} e_{i+r}\}\rangle$ (Definition 1.3).

Let $\sum w_i g_i = 0$, that is $\tau := \sum w_i e_{i+r} \in$ syz(I), and let $me_{k+r} = L(\tau)$ with respect to <₁. Let

$$T := \{ ne_{r+l} \mid n e_{r+l} \mbox{ be a monomial of } \tau, L(ng_l) = L(mg_k)\}.$$

Then, obviously, $\tau\vert _T := \sum_{ne_{r+l} \in T} ne_{r+l}$ is a syzygy of $L(g_1), \ldots, L(g_q)$. Especially, $\char93 T \ge 2$. Choose l such that $ne_{r+l} \in T$ for some n and $ne_{r+l} \not= me_{k+r}$. Because $L(\tau) = me_{k+r}$ and the definition of <₁ we have k < l.
Since mL(g_k) = nL(g_l) we have $m_{lk} \mid m.$

But $L(\tau_{kl}) = m_{lk} e_{k+r}$ implies $L(\tau_{kl}) \mid \tau$, that is $L(\tau) \in L(\langle\{m_{ji} e_{i+r}\}\rangle)$, which proves the proposition.

The principle of the algorithm is now easy.

Let S be a standard basis of $I \subseteq K[x]^r = \sum^r_{i=1} K[x]e_i$. We may assume that $L(s) \not\vert$ L(s') for different $s, s' \in S$.

Let $q := \char93 S$.

W := Syz$(\bf S)$
INPUT: S, a standard basis
OUTPUT: W, the module of syzygies of S

$W:= \emptyset$
T := initSyz (S)
L := initPairs (T)
WHILE $L \not= \emptyset$ DO

p := (a, b, s) the last element from L
$L := L \backslash \{(a, b, s)\}$
s := spoly(a,b)
h := NF(s|T)
h:= h(t = 1)
$W := W \cup \{h\}$

END

T := initSyz$(\bf S)$
INPUT: S, a standard basis $v_1, \ldots, v_s$
OUTPUT: T, the set $[v_1, 1, 0, \ldots, 0], \ldots, [v_s, §, \ldots, 0,1]$

i := r; $T := \emptyset$
WHILE $S \not= \emptyset$ DO

s := the first element from S
i := i+1
$S := S \backslash \{s\}$
s := s + e_i
$T := T \cup \{s\}$

END
T := T^h.

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 $f \in T$ such that $L(f) \mid t^\alpha L(h)$ for some $\alpha$ DO

choose the first possible f with respect to the ordering in T such that $\alpha$ is minimal
IF $\alpha > 0$ THEN
$T := T \cup \{ h\}$
END
h := spoly $(t^\alpha h, f)$
update (h)

END

Here we use on $K[t, x]^{r+q} = \sum^{r+q}_{i=1} K[t, x] e_i$ the following ordering <₂:

If $i \le r$ and $j \ge r + 1$ then m e_j <₂ n e_i for all monomials $m, n \in K[t, x]$.

On $\sum^r_{i=1} K[t,x]e_i$ respectively $\sum^q_{i=r+1} K[t, x]e_i$ we use the extension of < (respectively <₁) 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 $\{g_1, \ldots, g_q\}$ be a standard basis of $I \subset K[x]^r = \sum_{i=1, \ldots, r} K[x]e_i$. We assume that the leading terms are a basis vector of K[x]^r, that is $L(g_{i}) = e_{\nu_i}$. We set $J = \{\nu \mid \exists i$ s.t. $\nu = \nu_i\}$ and for $\nu \in J$ we choose exactly one $g_{i_\nu}$ such that $L(g_{i_\nu})= e_\nu$. Then ILoc_;SPMlt; K[x] is a free Loc_;SPMlt; K[x]-module with basis $\{g_{i_\nu} \mid \nu \in J\}$ and (Loc _;SPMlt; K[x])^r/ILoc_;SPMlt;K[x] is Loc_;SPMlt; K[x]-free with basis represented by the $\{e_j \mid j \not\in J\}$.

Proof: Let us renumber the g_i such that $g_{i_\nu} = g_\nu$ for $\nu \in J$. First of all, the subset $\{g_\nu \mid \nu \in J\} \subset \{g_{1}, \ldots, g_{q}\}$ 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, $\{g_\nu \mid \nu \in J\}$ generates ILoc_;SPMlt; K[x]. Now consider a relation

$$\sum_{j\not\in J} \xi_j e_j = \sum_{j \in J} \xi_j g_j,\quad \xi_j \in \mbox{Loc}_< K[x].$$

After clearing denominators we may assume that $\xi_j \in K[x]$. Since the leading terms involve different e_i on each side, we obtain $\xi_1 = \cdots = \xi_n = 0$. This shows that the $g_\nu,\, \nu \in J$ are linear independent and that the $e_j, j \not\in J$ are independent modulo ILoc_;SPMlt; K[x]. Since $\{ L(g_j) \mid j \in J\} \cup \{e_i \mid i\not\in J\}$ generate L(K[x]^r)=(e₁,...,e_r)K[x] $\{g_j \mid j\in J\}\cup\{e_i\mid i\not\in J\}$ is a standard basis of K[x]^r this set generates $(\mbox{Loc}_< K[x])^r$ by Corollary 1.11. Therefore, $\{e_j \mid j \not\in J\}$ generates $(\mbox{Loc}_< K[x])^r/I\mbox{ Loc}_< K[x]$ over Loc_;SPMlt; K[x].

Theorem 4..3   Let $S = \{g_1, \ldots, g_q\}$ be a standard basis of $I \subseteq K[x]^r$. Order S in such a way that whenever L(g_i) and L(g_j) involve the same component, say $L(g_i) = x^{\alpha_i} e_k$ and $L(g_j) = x^{\alpha_j}e_k$, then $\alpha_i \ge \alpha_j$ in the lexicographical ordering if i < j. If $L(g_1), \ldots, L(g_q)$ do not depend on the variables $x_1, \ldots, x_s$, then the $L(\tau_{ij})$ do not depend on the variables $x_1, \ldots, x_{s+1}$ and

$$M:= (\mbox{Loc}_< K[x])^r / I\mbox{ Loc}_< K[x]$$

has a Loc_;SPMlt; K[x]-free resolution of length $\le n - s$. In particular, M always has a free resolution of length $\le n$ and, by Serre's theorem, $\mbox{Loc}_< K[x]$ is a regular ring.

Proof: For i < j and $L(g_i) = x^{\alpha_i} e_k$, $L(g_j) = x^{\alpha_j}e_k$ we have $\alpha_i = (0, \ldots, 0, \alpha_{i, s+1}, \ldots), \alpha_j = (0, \ldots, 0, \alpha_{j, s+1}, \ldots)$ with $\alpha_{i, s+1} \ge \alpha_{j, s+1}$. Therefore, $L(\tau_{ij}) = m_{ji} e_{i+r}$ does not depend on $x_1, \ldots, x_{s+1}$.

Let q₁ := q and $\varphi_1 : K[x]^{q_1} \to K[x]^r$ the morphism given by $\{g_i\}$, $\sum w_i e_{i+r} \mapsto \sum w_i g_i$, and $\varphi_2 :K[x]^{q_2} \to K[x]^{q_1}$ the analog morphism given by the standard basis $\{\tau_{ij}\}$, $q_2 = \char93 \{\tau_{ij}\}$. Applying the same construction as above to syz $^1(I) := \mbox{syz}(I) = \mbox{ker}(\varphi_1)$ and $\{\tau_{ij}\}$ we obtain a standard basis $\{\tau^2_{kl}\}$ of szy²(I) := syz(syz(I)) = ker $(\varphi_2)$ such that the leading terms of $\tau^2_{kl}$ do not depend on $x_1, \ldots, x_{s+2}$.

Continuing in the same way we obtain an exact sequence

$$0 \to K[x]^{q_{n-s}}/\mbox{ker}(\varphi_{n-s}) \buildrel \var... ...x]^{q_1} \buildrel\varphi_1\over\to K[x]^r \to K[x]^r/I \to 0.$$

Moreover, ker $(\varphi_{n-s}) =$ syz^n-s(I) has a standard basis $\{\tau^{n-s}_{k,l}\}$ such that none of the variables appear in $L(\tau^{n-s}_{k,l})$. Hence, by the preceding lemma, $K[x]^{q_{n-s}}/\mbox{ker}(\varphi_{n-s})$ 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 + e_i in the procedure initSyz described above by $s := s + lm(s)\cdot e_i$ with $L(s) = lm(s) \cdot e_k$ 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.

$(\max\, 5)^2$
the ideal $(f_1, \ldots, f_5)^2$ where $f_i = x_i (x_0^8 + x_1^2 \cdot \ldots \cdot \hat{x}_i \cdot \ldots \cdot x_5^2),\; i = 1, \ldots, 5$.

8.

Sparse
t¹⁸x² - t¹⁹z - t¹⁸z²,
t²⁶xy - t¹⁷z - t²⁵z³,
t³⁸y² - t³⁷xyw;
(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 - h⁵;
( a, b, c, d, e, h the order of the variables)

11.

Kahn4
a⁴ - b⁴,
b⁴ - c⁴,
c⁴ - d⁴,
d⁴ - e⁴,
a³ b + b³c + c³ d + d³ e + e³a;
( a, b, c, d, e the order of the variables)

12.

Iarrobino
xy + y² + uz - wz - xz + yz,
x² - y² + uz - wz - xz +z²,
wy,
wx - uz + yz,
w² - y² + uz - z²,
vz - yz - z²,
vy - y² - wz + xz + yz + z²,
vx - y² + uz + yz - z²,
vw - y² + uz + yz - z²,
v² + y² + uz - xz - yz - z²,
uy + y² + yz,
ux - y² + wz - xz - z²,
uw - y² + uz + yz - z²,
uv - y² - xz + yz,
u² + 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.

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³-10731b³+5818ae²+13936be²+11725ce²+6401de²,
b³-4862c³-2334ae²+9991be²+14579ce²+10173de²,
c³-6087d³+1135ae²+4570be²+5250ce²+1393de²,
d³+11392ae²+7125be²-15188ce²-12706de²-10957e³;
( a, b, c, d, e the order of the variables)

15.

Schreyer 2
polynomials created as in 14

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³-7986a²e-744b²e+2389c²e-7991bde+11075cde-15425d²e+7645ae²-1871be²+869 8ce²-9609de²,
a²e+3582b²e-6012c²e-14933bde+14203cde+11560d²e+2294ae²+12826be²-12284ce^ 2+10870de²,

b²e+3097c²e+10611bde+6826cde+2785d²e-14231ae²+13731be²-1863ce²+8227de²,
c²e-8559bde+13444cde+3372d²e+5235ae²+9139be²-7685ce²+3756de²,
bde-14077cde-2960d²e-4481ae²-3950be²-850ce²-14832de²,
cde-13603d²e+4327ae²+15554be²+2054ce²-12484de²,
b³+7339d²e-3253ae²+8720be²+9224ce²-11849de²,
c³-9222d²e-12818ae²-11519be²+6703ce²-10364de²,
d³+4730d²e+7627ae²+14168be²+11428ce²+8632de²,
d²e+9376ae²+6688be²-11914ce²-295de²-5576e³;
(a,b,c,d,e the order of the variables)

16.

caprasse 4
-2w²x - w²z + 2 xyt + y²z
2w⁴+4w²x² + 4w²xz - 10w²y² - 10w²y² - 10w²yt-x³z+4x²yt+4xy²z+2y³t
-w²x - 2w²z + xt² + 2yzt
2w⁴ + 4w²xz - 10w²yt + 4w²z² - 10w²t² - xz³ + 4yz²t + 2yt³;
(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:

$\begin{array}{ll} S(4): & x_4x_1 - x_2^2,\; x_4x_2 - x_3^2;\\ S(5): & S(4),\; ... ...1}^2 - x_{m-1}^2 - x_{m-2} x_{m-6};\; \mbox{ if } m \mbox{ is even} \end{array}$

( $x_1, \ldots, x_m$ the order of the variables)

18.

Pellikaan, Jaworski S(10)
compare example 17

19.

9 random i-forms in 4 variables,
$i = 2, \ldots, 10$

20.

6 random i-forms in 4 variables,
$i = 5, \ldots, 10$.

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