How to Compute Linear Resolutions

by Martin Kreuzer and Mischa Lusteck (Regensburg)

Given a finitely generated, graded module M defined over P = K[X_{1}, …, X_{n}] with minimal graded free resolution

0 ⟶ ⨁_{i≥α+n−1} P (−i)^{b_{ni}} ⟶ ⋯ ⟶ ⨁_{i≥α+1} P (−i)^{b_{1i}} ⟶ ⨁_{i≥α} P (−i)^{b_{0i}} ⟶ M ⟶ 0

the subcomplex

0 ⟶ P (−α − n + 1)^{b_{n α+n−1}} ⟶ ⋯ ⟶ P (−α − 1)^{b_{1 α+1}} ⟶ P (−α)^{b_{0 α}} ⟶ M ⟶ 0

is called the linear part of the resolution of M. Our goal is to compute the numbers a_{i} = b_{i α+i−1} for i = 0, …, n as efficiently as possible. To this end we propose two methods.

The first method starts with a set of vectors v_{1}, …, v_{μ} ∈ P_{1}^{ν} of linear forms and finds their linear syzygies

(∗)  ℓ_{1}v_{1} + ⋯ + ℓ_{μ}v_{μ} = 0

with ℓ_{1}, …, ℓ_{μ} ∈ P_{1}^{μ} by comparing coefficients for X_{i}X_{j}e_{k} (such that 1 ≤ i ≤ j ≤ n and 1 ≤ k ≤ ν) and transforming (∗) into a linear system of equations

(∗∗)  L(v_{1}, …, v_{μ}) · (ℓ_{1 1}, …, ℓ_{1 n}, …, ℓ_{μ 1}, …, ℓ_{μ n})^{transp.} = 0

where L(v_{1}, …, v_{μ}) is a μ\binom{n}{2} × μn-matrix over K and ℓ_{i} = ℓ_{i 1}X_{1} + ⋯ + ℓ_{i n}X_{n} for i = 1, …, μ. The usual Buchberger algorithm for solving (∗) by computing a truncated Gröbner basis amounts to solving the linear system (∗∗) by Gaußian elimination (cf. [1]). We discover a recursive structure in L(v_{1}, …, v_{μ}) and propose to solve (∗∗) using a recursive version of the structured Gauß algorithm (cf. [2]). In this way the numbers a_{0}, …, a_{n} are computed inductively, and one can stop as soon as one of them vanishes.

Our second method is particularly apt to compute a single number a_{i} with i ∈ {0, …, n}. It is based on the formula

a_{i} = dim_{K} Tor_{i}^{P} (M, K)_{α+i}

and the possibility to compute the P -module Tor_{i}^{P} (M, K) from the Koszul resolution of K = P/(X_{1}, …, X_{n}). Again it turns out that we have to find the rank of a matrix which is rather sparse and has a lot of internal structure, so that we can use a suitable recursive version of the structured Gauß algorithm.

Both methods improve the speed of the calculation of linear syzygies tremendously. The paper ends with some applications of the presented methods to ideals of minors of homogeneous matrices and to the vanishing ideals of randomly chosen sets of points in the projective space over a finite field.

References:

[1] T. Mora, An introduction to commutative and noncommutative Gröbner bases, Theor. Computer Science 134 (1994), 131 – 173

[2] C. Pomerance and J.W. Smith, Reduction of huge, sparse matrices over finite fields via created catastrophes, Experimental Math. 1 (1992), 89 – 94