IDEALIZATION OF MODULES IN COMPUTER ALGEBRA

MARTIN KREUZER AND LORENZO ROBBIANO

Abstract. Based on an explicit description of the idealization of a graded submodule of a graded free module, we examine the behaviour of Gröbner bases and minimal homogeneous systems of generators under this process. Then we show how one can idealize a homogeneous presentation. Using this theory, we present a unified description of several strategies for computing minimal homogeneous presentations and minimal graded free resolutions, in particular of the vertical and horizontal strategies. We obtain at a simple and compact algorithm for computing minimal graded free resolutions degree-by-degree which lends itself well to further optimizations.

1. Introduction

One of the central and notoriously difficult tasks in Computational Commutative Algebra is the computation of a minimal graded free resolution of a finitely generated graded module. The implementators of the major computer algebra systems spent considerable energy on this problem and produced a number of different strategies for achieving an efficient solution (see for instance [2], [6], [3],

[10] and [12]). Since the efficiency of a particular strategy strongly depends on the nature of the examples to which it is applied, it has proven difficult to determine an optimal strategy. Furthermore, inspired by the actual implementation, the mathematical description of these strategies frequently uses specially adapted terminologies. This fact makes it hard to compare the various approaches.

In this paper we propose a unified framework for treating algorithms which compute minimal homogeneous presentations or minimal graded free resolutions. It is based on the notion of the idealization of a module. In commutative algebra idealizations were first used by M. Nagata in [11]. In other areas of mathematics they are known under different names, e.g. one-point-extensions. The basic idea is to construct a ring which contains a given module as an ideal. In this way computations for the module become computations for that ideal. In our case we follow an idea pioneered in [1] and [6]: we idealize not only the module under consideration but also the graded free modules appearing in its minimal homogeneous presentation or its minimal graded free resolution. Thus the computation of the minimal graded free resolution becomes a Gröbner basis computation in a large polynomial ring. Different strategies for computing resolutions turn out to be nothing but different selection strategies for that Gröbner basis computation.

Besides being able to unify and explain several approaches we will also formulate our own version of the “horizontal” (i.e. degree-by-degree) strategy for computing minimal homogeneous presentations or minimal graded free resolutions. With this algorithm we obtain a simplicity and compactness which is a good basis for efficient implementations.

Now we describe the contents of the paper in more detail. In the second section we recall the construction of the idealization of a module and apply it to the cases of graded free modules and their graded submodules. After finding an explicit description of the ideal representing the idealization of the module, we study the connections between Gröbner bases and minimal systems of generators of the module and its idealization ideal.

In Section 3 we proceeed to idealize the entire minimal homogeneous presentation of the module. The ideal representing this idealization is shown to contain both the minimal homogeneous system of generators of the module and (via an elimination process) the module of its syzygies. Then we use this description in Section 4 to compute minimal homogeneous presentations. We present two strategies for this purpose: the vertical and the horizontal strategy. The vertical strategy proceeds by first computing the minimal homogeneous system of generators of the module and then the minimal homogeneous system of generators of its syzygy module. The horizontal strategy computes both systems simultaneously and proceeds degree-by-degree.

Both the vertical and the horizontal strategy can be generalized to compute the minimal graded free resolution of the module. This is done in the last section where we obtain algorithms which lend themselves well to further study and optimization. To keep the paper uniform and accessible, we have adhered to the definitions and notation in our book [7] and in the foundational paper [9]. Explicit computations of examples for the algorithms introduced here are contained in [8].

2. Idealization of Graded Modules

Let us begin by defining the idealization of a module and collecting some basic properties of this process.

Definition 2.1. Let R be a ring and M an R-module. We equip the product set R×M with two operations. The addition + : (R×M)×(R×M) ⟶ R×M is given by (r, m)+(r′, m′) = (r+r′, m+m′) and the multiplication · : (R×M)×(R×M) ⟶ R×M is given by (r, m)·(r′, m′) = (rr′, rm′ +r′m) for r, r′ ∈ R and m, m′ ∈ M. In this way, the set R × M becomes a commutative ring with identity element (1, 0). We call this ring the idealization of M and denote it by R ⋉ M.

The ring R ⋉ M is an R-algebra via the ring homomorphism R ⟶ R ⋉ M given by r ↦ (r, 0). The canonical map ı : M ⟶ R ⋉ M defined by ı(m) = (0, m) is injective and R-linear. Its image is an ideal in R ⋉ M. We shall denote this ideal by ı(M) and identify the elements of M with their images under ı.

Remark 2.2. Let R be a ring and M an R-module.

a) The ideal ı(M) satisfies ı(M)^{2} = 0.

b) Given an R-submodule N ⊆ M, the inclusion R × N ⊆ R × M defines an injective ring homomorphism R ⋉ N ⟶ R ⋉ M. The image of N in R ⋉ M is an ideal which is contained in the ideal ı(M).

c) Let Γ be a monoid, let R be Γ-graded, and let M be a Γ-graded R-module. Then R⋉M is a Γ-graded ring via (R⋉M)_{γ} = R_{γ} ×M_{γ} for all γ ∈ Γ, and ı(M) is a homogeneous ideal in this ring.

In the sequel we want to study the idealization of a graded submodule of a graded free module. In the remainder of this paper we use the following setting. Let K be a field, and let the polynomial ring P = K[x_{1}, …, x_{n}] be positively graded by a matrix W ∈ Mat_{m,n}(ℤ). Thus P is equipped with a ℤ^{m} grading such that 1 ∈ P_{0}, the indeterminate x_{i} is homogeneous, and the degree of x_{i} (given by the i^{th} column of W) is lexicographically positive.

Furthermore, let d_{01}, …, d_{0r} ∈ ℤ^{m}, let F_{0} = ⊕_{i=1}^{r} P (−d_{0i}), and let M be a graded submodule of F_{0}. The canonical basis vectors of F_{0} will be denoted by e_{1}, …, e_{r}. By considering e_{1}, …, e_{r} as indeterminates, we form the polynomial ring \overline{P} = K[x_{1}, …, x_{n}, e_{1}, …, e_{r}] = P [e_{1}, …, e_{r}]. We equip \overline{P} with the grading given by \overline{W} = (W | d_{01} ⋯ d_{0r}) ∈ Mat_{m,n+r}(ℤ). A vector v = f_{1}e_{1}+⋯+f_{r}e_{r} ∈ F_{0} will be identified with the corresponding polynomial in \overline{P}.

Moreover, we let 𝔢 be the ideal generated by E = \{e_{i}e_{j} | 1 ≤ i ≤ j ≤ r\} in \overline{P}, and let E be the tuple

E = (e_{1}e_{1}, e_{1}e_{2}, …, e_{1}e_{r}, e_{2}e_{2}, e_{2}e_{3}, …, e_{2}e_{r}, …, e_{r}e_{r}) ∈ \overline{P} ^{r(r+1)/2}

In this situation we can represent the idealization of M as follows.

Proposition 2.3. (Idealization of a Graded Submodule) Let V = (v_{1}, …, v_{s}) be a tuple of homogeneous vectors which generate M.

a) The map φ : P ⋉ F_{0} ⟶ \overline{P} /𝔢 which sends (f, (g_{1}, …, g_{r})) to the residue class of f + g_{1}e_{1} + ⋯ + g_{r}e_{r} is an isomorphism of graded rings.

b) Under the composition M ⟶^{ı} P ⋉ M ⟶ P ⋉ F_{0} ⟶^{φ} \overline{P} /𝔢, the module M is identified with the residue class ideal of I_{M} = (v_{1}, …, v_{s}) + 𝔢 ⊆ \overline{P}.

Proof. First we prove a). Since φ is obviously R-linear, we check that φ is compatible with multiplication. Let (f, (g_{1}, …, g_{r})) and (f′, (g′_{1}, …, g′_{r})) be two elements of R ⋉ M. Computing modulo 𝔢, we get

φ((f, (g_{1}, …, g_{r})) · (f′, (g′_{1}, …, g′_{r}))) = φ((ff′, (fg′_{1} + f′g_{1}, …, fg′_{r} + f′g_{r})))
= ff′ + (fg′_{1} + f′g_{1})e_{1} + ⋯ + (fg′_{r} + f′g_{r})e_{r}
= (f + g_{1}e_{1} + ⋯ + g_{r}e_{r}) · (f′ + g′_{1}e_{1} + ⋯ + g′_{r}e_{r})
= φ((f, (g_{1}, …, g_{r}))) · φ((f′, (g′_{1}, …, g′_{r})))

Since φ is clearly both injective and surjective, it remains to show that φ is homogeneous. The monomial ideal 𝔢 is homogeneous. Given a homogeneous element (f, (g_{1}, …, g_{r})) of R ⋉ M, the residue class of f + g_{1}e_{1} + ⋯ + g_{r}e_{r} is homogeneous of the same degree. Therefore φ is a homomorphism of graded rings.

To prove b), we combine the descriptions of the maps in Definition 2.1.b, Remark 2.2.b, and part a). For i = 1, …, s, we see that v_{i} is mapped to the residue class v_{i} + 𝔢 by the composition. Hence the claim follows. ⊓ ⊔

Definition 2.4. In the above setting, the ideal I_{M} = (v_{1}, …, v_{s}) + 𝔢 of \overline{P} is called the idealization ideal, or simply the ideal of M.

Gröbner bases of graded submodules and Gröbner bases of their ideals are related as follows. A module term ordering σ on 𝕋^{n}⟨e_{1}, …, e_{r}⟩ is called compatible with a term ordering τ on 𝕋^{n} if t ≥_{τ} t′ implies te_{i} ≥_{σ} t′e_{i} for all t, t′ ∈ 𝕋^{n} and i ∈ \{1, …, r\}. We shall say that a term ordering \overline{σ} on 𝕋(x_{1}, …, x_{n}, e_{1}, …, e_{r}) extends both σ and τ if the restriction of \overline{σ} to 𝕋^{n} is τ and its restriction to 𝕋^{n}⟨e_{1}, …, e_{r}⟩ is σ.

Proposition 2.5. (Gröbner Bases and Idealization) Let I_{M} ⊆ \overline{P} be the ideal of M. Furthermore, let τ be a term ordering on 𝕋^{n}, let σ be a module term ordering on 𝕋^{n}⟨e_{1}, …, e_{r}⟩ which is compatible with τ, and let \overline{σ} be a term ordering on 𝕋(x_{1}, …, x_{n}, e_{1}, …, e_{r}) which extends both σ and τ.

a) Let G be a σ-Gröbner basis of M. Then G ∪ E is a \overline{σ}-Gröbner basis of I_{M}.

b) Let G be the reduced σ-Gröbner basis of M. Then the reduced \overline{σ}-Gröbner basis of I_{M} is G ∪ {e_{i}e_{j} ∈ E | e_{i}, e_{j} ∉ LT_{σ}(M)}.

Proof. To prove a), we let G = {g_{1}, …, g_{s′}} and f ∈ I_{M}. By subtracting suitable multiples of polynomials e_{i}e_{j}, we see that we may reduce f to the form h = h_{0} + h_{1}e_{1} + ⋯ + h_{r}e_{r} with h_{0}, …, h_{r} ∈ P. Since I_{M} is contained in (e_{1}, …, e_{r}), we have h_{0} = 0. The polynomial h = h_{1}e_{1} + ⋯ + h_{r}e_{r} ∈ I is linear in e_{1}, …, e_{r}. The only generators of I_{M} which are linear in e_{1}, …, e_{r} are v_{1}, …, v_{s}. Hence h is a P -linear combination of those generators. Thus we have (h_{1}, …, h_{r}) ∈ ⟨v_{1}, …, v_{s}⟩ and LT_{σ}((h_{1}, …, h_{r})) = t LT_{σ}(g_{i}) for some t ∈ 𝕋^{n} and i ∈ {1, …, s′}. Since the term ordering \overline{σ} extends σ, we get LT\overline{σ}(h) = t LT\overline{σ}(g_{i}). Therefore we can reduce h by G. After several such reduction steps we eventually get zero, because G is a σ-Gröbner basis of M. Altogether, the polynomial f reduces to zero using G ∪ E.

To show claim b), we let \overline{G} be the reduced \overline{σ}-Gröbner basis of I_{M}. Since we have e_{i}e_{j} ∈ I_{M}, we know e_{i}e_{j} ∈ LT\overline{σ}(I_{M}) for all 1 ≤ i ≤ j ≤ r. Now it follows from the additional condition e_{i}, e_{j} ∉ LT_{σ}(M) that e_{i}e_{j} is a minimal generator of LT\overline{σ}(I_{M}), and therefore e_{i}e_{j} is contained in \overline{G}. Thus \overline{G} has the form \overline{G} = G ∪ \{e_{i}e_{i} ∈ E | e_{i}, e_{j} ∉ LT_{σ}(I)\} for some set of polynomials G ⊆ \overline{P}. The fact that the polynomials in G are irreducible with respect to E implies that they have degree ≤ 1 in the indeterminates e_{1}, …, e_{r}. Since we have I_{M} ⊆ (e_{1}, …, e_{r}), this shows that the polynomials in G are linear forms in e_{1}, …, e_{r}. Since the Buchberger Algorithm preserves homogeneity, they are homogeneous with respect to the grading given by \overline{W}. Hence they are actually images of homogeneous vectors in M. Their leading terms generate all elements in LT_{σ}(I_{M}) of degree one in e_{1}, …, e_{r}. Thus the leading terms of the corresponding elements of M generate LT_{σ}(M). Finally, since the elements of G are fully reduced against each other, the corresponding elements of M are fully reduced, too. Hence G is the image of the reduced σ-Gröbner basis of M in \overline{P}. ⊓ ⊔

In particular, notice that the reduced \overline{σ}-Gröbner basis of I_{M} is G ∪ E if we have M ⊆ (x_{1}, …, x_{n}) F_{0} and G is the reduced σ-Gröbner basis of M. Let us give some typical examples of simultaneous extensions \overline{σ} of σ and τ as required by this proposition (for a classification, see [5]).

Remark 2.6. Let τ = Ord(V) be a term ordering on 𝕋^{n} given by a non-singular matrix V ∈ Mat_{n}(ℤ).

a) Let σ be the module term ordering τ − Pos on 𝕋^{n}⟨e_{1}, …, e_{r}⟩ (see [7], 1.4.16). Then \overline{σ} = Ord \binom{V 0}{0 I_{r}} is a term ordering on 𝕋^{n}(x_{1}, …, x_{n}, e_{1}, …, e_{r}) which extends both τ and σ.

b) Let σ be the module term ordering Pos−τ on 𝕋^{n}⟨e_{1}, …, e_{r}⟩. Then \overline{σ} = Ord \binom{0 I_{r}}{V 0} is a term ordering on 𝕋^{n}(x_{1}, …, x_{n}, e_{1}, …, e_{r}) which extends both τ and σ.

c) Suppose that τ is a degree compatible term ordering of the form τ = Ord \binom{W}{W′} with W′ ∈ Mat_{n−m,n}(ℤ) and that d_{0i} >_{Lex} 0 for i = 1, …, r. Then the module term ordering σ = Deg−τ−Pos is compatible with τ, and the term ordering

\overline{σ} = (\begin{matrix}W & d_{01} ⋯ d_{0r} \\ W′ & 0 ⋯ 0 \\ 0 & I_{r} \end{matrix}) on 𝕋(x_{1}, …, x_{n}, e_{1}, …, e_{r}) extends both τ and σ.

Example 2.7. Let P = K[x, y, z] be standard graded, and let τ be the term ordering DegRevLex on 𝕋^{3}. Then σ = PosDegRevLex is a module term ordering on 𝕋^{3}⟨e_{1}, e_{2}, e_{3}⟩ which is compatible with τ. Moreover, the term ordering \overline{σ} = Ord \binom{0 I_{3}}{V 0} with V = ( \begin{matrix}1 1 1 \\ 0 0 −1 \\ 0 −1 0 \end{matrix} ) extends both σ and τ.

Now let M be the graded submodule of P (−1)^{3} generated by the set of vectors {(x, y, 0), (0, 1, 0), (0, z^{2}, xy)}. Then the reduced σ-Gröbner basis of M is \{e_{2}, xe_{1}, xye_{3}\}. By applying the proposition, we see that the reduced \overline{σ}-Gröbner basis of the ideal I_{M} is {e_{2}, xe_{1}, xye_{3}, e_{1}^{2}, e_{1}e_{3}, e_{3}^{2}}.

After clarifying the behaviour of Gröbner bases with respect to idealization, we turn to minimal homogeneous systems of generators.

Proposition 2.8. (Minimal Generators and Idealization) Let M be a graded submodule of a graded free P -module F_{0} = ⊕_{i=1}^{r} P (−d_{0i}) such that M ⊆ (x_{1}, …, x_{n}) F_{0} and where d_{0i} >_{Lex} 0 for i = 1, …, r Furthermore, let V = (v_{1}, …, v_{s}) be a tuple of non-zero homogeneous vectors which generate M.

a) Assume that V is a minimal homogeneous system of generators of M. Then the set {v_{1}, …, v_{s}} ∪ E is a minimal homogeneous system of generators of I_{M}.

Let τ be a term ordering on 𝕋^{n}, let σ be a module term ordering on 𝕋^{n}⟨e_{1}, …, e_{r}⟩ which is compatible with τ, and let \overline{σ} be a term ordering on 𝕋(x_{1}, …, x_{n}, e_{1}, …, e_{r}) which extends both σ and τ.

b) If we apply Buchberger’s Algorithm with Minimalization (see [8], 4.6.3 or [9], Cor. 13) to the tuple (V | E), it computes a minimal system of generators of the ideal I_{M} ⊆ \overline{P} of the form (V_{min} | E), where V_{min} is a minimal homogeneous system of generators of M.

c) If we apply the variant of Buchberger’s Algorithm with Minimalization (see [8], 4.6.5 or [9], Rem. 14.b) to the tuple (V | E), it computes a homogeneous \overline{σ}- Gröbner basis of I_{M} of the form (G | E) and a minimal system of generators of the form (G_{min} | E), where G is a σ-Gröbner basis of M and G_{min} is a minimal homogeneous system of generators of M which is contained in G.

Proof. First we show a). By definition, the set {v_{1}, …, v_{s}} ∪ E generates I_{M}. Consider the grading on \overline{P} defined by deg(x_{i}) = 0 and deg(e_{j}) = 1 for i = 1, …, n and j = 1, …, r. Then I_{M} is a homogeneous ideal with respect to this grading. Its homogeneous component of degree one is P v_{1} + ⋯ + P v_{s}, so that it follows from the minimality of V that we cannot drop any of these generators in (V | E). Next we consider the image of I_{M} under the substitution x_{i} ↦ 0 for i = 1, …, n. Since M ⊆ (x_{1}, …, x_{n}) F_{0}, we have v_{i} ↦ 0 for i = 1, …, s. The images of the elements e_{i}e_{j} are minimal generators. Therefore the elements e_{i}e_{j} are minimal generators of I_{M}.

Now we prove b). The hypothesis d_{0i} >_{Lex} 0 implies that \overline{P} is positively graded. Hence we can apply Buchberger’s Algorithm with Minimalization. Since (V | E) generates I_{M}, the algorithm computes a minimal system of generators of I_{M} which is contained in (V | E). By considering the grading deg(x_{i}) = 0, deg(e_{j}) = 1 again, we see that the vectors in V chosen by the algorithm correspond to a minimal system of generators of M. Moreover, the algorithm has to choose all polynomials e_{i}e_{j} because they are all minimal generators of I_{M}.

To show c), we claim that the \overline{σ}-Gröbner basis of I_{M} computed by the algorithm has the form (G | E). Clearly, a critical pair (i, j) such that LT\overline{σ}(v_{i}) = c_{i}t_{i}e_{γ_{i}} and LT\overline{σ}(v_{j}) = c_{j}t_{j}e_{γ_{j}} satisfy γ_{i} = γ_{j} corresponds to a critical pair of the vectors v_{1}, …, v_{s} in M. However, if we have γ_{i} ≠ γ_{j}, then the corresponding S-vector has degree two in the indeterminates e_{1}, …, e_{r}. It reduces to zero, because the terms in its support are of the form te_{k}e_{ℓ} where e_{k}e_{ℓ} has a smaller degree and has been appended to the Gröbner basis already. Moreover, every time the algorithm encounters a term e_{k}e_{ℓ}, that term is irreducible with respect to the part of the Gröbner basis computed so far and is appended to the Gröbner basis and to the minimal system of generators. Altogether, we see that the algorithm computes a Gröbner basis of the form (G | E). As above, it follows that the minimal set of generators it finds is of the form (G_{min} | E). ⊓ ⊔

Let us briefly discuss the hypotheses of this proposition.

Remark 2.9. Suppose we are in the setting of the proposition.

a) The assumption M ⊆ (x_{1}, …, x_{n}) F_{0} is essential for the proposition to be true. Otherwise, S-vectors of the form e_{γ_{i}}v_{j} −e_{γ_{j}}v_{i} could be appended to the Gröbner basis, because they contain terms of the form c e_{k}e_{ℓ} with c ∈ K which have not yet been treated, i.e. which are not yet in the Gröbner basis.

b) The assumption d_{0i} >_{Lex} 0 for i = 1, …, r is used to conclude that the grading on \overline{P} given by \overline{W} is positive, but it is not essential for the correctness of the algorithm (see also the discussion below).

3. Idealization of Homogeneous Presentations

In this section we want to idealize not only a graded submodule, but a whole homogeneous presentation. We continue to assume that M is a graded submodule of a graded free P -module F_{0} = ⊕_{i=1}^{r} P (−d_{0i}), where d_{01}, …, d_{0r} ∈ ℤ^{m}, and that V = (v_{1}, …, v_{s}) is a tuple of non-zero homogeneous elements which generate M. Moreover, it will be convenient to assume that V is deg-ordered, i.e. that we have deg_{W} (v_{1}) ≤_{Lex} ⋯ ≤_{Lex} deg_{W} (v_{s}).

Then we form the graded free P -module F_{1} = ⊕_{j=1}^{s} P (−d_{1j}) where d_{1j} = deg_{W} (v_{j}) for j = 1, …, s. We let {ε_{1}, …, ε_{s}} be the canonical basis of F_{1} and consider a homogeneous presentation

F_{2} ⟶^{ψ} F_{1} ⟶^{φ} M ⟶ 0

of M where φ(ε_{j}) = v_{j} for j = 1, …, s and where F_{2} is a another graded free P -module.

Remark 3.1. For every d ∈ ℤ^{m}, a homogeneous presentation of the shifted module M(d) is given by

F_{2}(d) ⟶^{ψ̃} F_{1}(d) ⟶^{φ̃} M(d) ⟶ 0

where F_{1}(d) and F_{2}(d) are graded free P -modules, and where the homogeneous P -linear maps φ̃ and ψ̃ are given by the same homogeneous matrices as φ and ψ, respectively. Therefore the computation of a minimal homogeneous presentation of M is equivalent to the computation of a minimal homogeneous presentation of M(d).

In view of this remark, we shall from now on assume that d_{0i} >_{Lex} 0 for i = 1, …, r. Notice that this implies d_{1j} >_{Lex} 0 for j = 1, …, s. This assumption will prove useful in our theoretical discussion below. In an actual implementation it is not really necessary, because shifting the entire computation by a fixed degree does not change its correctness.

In order to idealize the above presentation of M, we introduce the polynomial ring P̃ = P [e_{1}, …, e_{r}, ε_{1}, …, ε_{s}] = K[x_{1}, …, x_{n}, e_{1}, …, e_{r}, ε_{1}, …, ε_{s}] and equip it with the grading given by W̃ = (W | d_{01} ⋯ d_{0r} | d_{11} ⋯ d_{1s}). Notice that, because of our assumption, this grading is positive. By Proposition 2.3.a, the idealization of the module F_{0} ⊕ F_{1} is the ring P̃/𝔢̃, where 𝔢̃ is the homogeneous ideal generated by the union of {e_{i}e_{j} | i, j = 1, …, r}, {e_{i}ε_{j} | i ∈ {1, …, r}, j ∈ {1, …, s}}, and {ε_{i}ε_{j} | i, j = 1, …, s}.

Let ı_{0} : F_{0} ⟶ P̃/𝔢̃ be the homogeneous injective P -linear map given by ı_{0}((f_{1}, …, f_{r})) = f_{1}e_{1} + ⋯ f_{r}e_{r} + 𝔢̃, and let ı_{1} : F_{1} ⟶ P̃/𝔢̃ be the homogeneous injective P -linear map given by ı_{1}((f_{1}, …, f_{s})) = f_{1}ε_{1} + ⋯ f_{s}ε_{s} + 𝔢̃. By [7], 3.6.1, if (f_{1}, …, f_{s}) ∈ Syz_{P} (V) is a homogeneous syzygy of V, then the corresponding element f_{1}ε_{1} + ⋯ + f_{s}ε_{s} of P̃ is contained in the ideal (v_{1} − ε_{1}, …, v_{s} − ε_{s}).

Definition 3.2. The ideal Ĩ_{M} = (v_{1} − ε_{1}, …, v_{s} − ε_{s}) + 𝔢̃ in P̃ is called the ideal of the presentation of M given above.

Our next proposition serves to justify this name.

Proposition 3.3. (Idealization of a Homogeneous Presentation) Let Ĩ_{M} ⊆ P̃ be the ideal of the presentation of M.

a) There exists a unique P -algebra homomorphism

Φ : P [ε_{1}, …, ε_{s}]/(ε_{i}ε_{j})_{i,j=1,...,s} ⟶ \overline{P} /𝔢

which maps the residue class of ε_{i} to v_{i} + 𝔢 for i = 1, …, s.

b) The image of Φ is the residue class ideal of the ideal of M.

c) The kernel of Φ is the residue class ideal of the ideal of Syz_{P} (V).

d) The ideal of Syz_{P} (V) is given by Ĩ_{M} ∩ P [ε_{1}, …, ε_{s}].

Proof. To prove a), it suffices to note that Φ is well-defined, because we have v_{i}v_{j} ∈ 𝔢 for i, j = 1, …, s. Claim b) follows from Proposition 2.3.b.

To show c), we note that Φ is induced by the substitution homomorphism Ψ : P [ε_{1}, …, ε_{s}] ⟶ \overline{P} /𝔢 with ε_{k} ↦ v_{k} + 𝔢 for k = 1, …, s. The ideal (ε_{k}ε_{ℓ})_{k,ℓ=1,...,s} is contained in ker(Ψ). Since v_{1}, …, v_{s} ∈ (e_{1}, …, e_{r}), the kernel of the composition of Ψ with the canonical surjection \overline{P} /𝔢 ⟶ P is (ε_{1}, …, ε_{s}), and therefore we have ker(Ψ) ⊆ (ε_{1}, …, ε_{s}). Furthermore, we have f_{1}ε_{1} + ⋯ + f_{s}ε_{s} ∈ ker(Ψ) if and only if f_{1}v_{1} + ⋯ + f_{s}v_{s} = 0. Hence {f_{1}ε_{1} + ⋯ + f_{s}ε_{s} | (f_{1}, …, f_{s}) ∈ Syz_{P} (V)} ∪ {ε_{k}ε_{ℓ} | k, ℓ = 1, …, s} generates ker(Ψ), and the claim follows from Proposition 2.3.b.

Finally, part d) follows from c) by a slight generalization of [7], 3.6.2, but the proof of that proposition still applies without modifications. ⊓ ⊔

4. Computation of Minimal Homogeneous Presentations

As above, we assume that M is a submodule of a graded free module F_{0} = ⊕_{i=1}^{r} P (−d_{0i}) and that it is given by a deg-ordered homogeneous system of generators V = (v_{1}, …, v_{s}). We want to compute a minimal homogeneous presentation of M. The graded version of Nakayama’s lemma implies that we may assume M ⊆ (x_{1}, …, x_{n}) F_{0}. There is an obvious method to solve our task.

Remark 4.1. Consider the following instructions.

1) Using the Buchberger Algorithm with Minimalization (see [8], 4.6.3), compute a subtuple V_{min} of V of homogeneous vectors which generate M minimally.

2) Using the lifting of syzygies (see [7], 3.1.8), compute a matrix S whose columns generate the module Syz_{P} (V_{min}). (Notice that all computations involved here keep the homogeneity of the input. Thus S is a homogeneous matrix.)

3) Using the Buchberger Algorithm with Minimalization, compute a subtuple S_{min} of S of homogeneous vectors which generate Syz_{P} (S_{min}) minimally.

4) Return V_{min} and S_{min} and stop. This is an algorithm which computes two tuples V_{min} and S_{min} of homogeneous vectors such that V_{min} generates M minimally and S_{min} generates Syz_{P} (V_{min}) minimally. In particular, we have a minimal homogeneous presentation

F_{2} ⟶^{ψ} F_{1} ⟶^{φ} M ⟶ 0

where F_{1} and F_{2} are graded free P -modules, where ψ is given by S_{min} and where φ is given by V_{min}.

This algorithm is rather wasteful, because the reduction steps involved in computing the Gröbner basis of M in step 1) have to be done again in step 2). Using the idealization of the presentation discussed in the previous subsection, we can proceed in a more efficient way. The method we use in the next theorem is called the vertical strategy. The reason is that we compute first a minimal system of generators G_{min} of M by looping through all necessary degrees (which we think of as being on top of each other) and then a minimal system of generators of Syz_{P} (G_{min}) by a similar loop.

To ease the notation, we shall resort to the following convention. Given a tuple G = (g_{1}, …, g_{s′}), we write LT_{σ}(g_{i}) = t_{i} e_{γ_{i}} with t_{i} ∈ 𝕋^{n} and γ_{i} ∈ {1, …, r} for i = 1, …, s′. Moreover, we identify the elements of the graded free P -module F_{0} = ⊕_{i=1}^{r} P (−d_{0i}) with their canonical images in the polynomial ring \overline{P} = P [e_{1}, …, e_{r}] and equip \overline{P} with the grading given by \overline{W} = (W | d_{01} ⋯ d_{0r}).

Theorem 4.2. (Computing Minimal Presentations Vertically) Let M be a graded submodule of a graded free P -module F_{0} = ⊕_{i=1}^{r} P (−d_{0i}) where d_{0i} >_{Lex} 0 for i = 1, …, r. Let V = (v_{1}, …, v_{s}) be a deg-ordered tuple of non-zero homogeneous vectors which generate M. Consider the following instructions.

1) Choose a term ordering σ on 𝕋^{n}(e_{1}, …, e_{r}). Let B = ∅, W = V, G = ∅, s′ = 0, G_{min} = ∅, μ = 0, and S = ∅.

2) Let d be the smallest degree with respect to Lex of an element in B or in W. Form the subset B_{d} and the subtuple W_{d}, and delete their entries from B and W, respectively.

3) If B_{d} = ∅, continue with step 6). Otherwise, chose a pair (i, j) ∈ B_{d} and remove it from B_{d}.

4) Compute the S-vector S_{ij} of g_{i} and g_{j}. Then compute S′_{ij} = NR_{σ,G}(S_{ij}). If S′_{ij} = 0 continue with step 3). If S′_{ij} ≠ 0 and it does not involve the indeterminates e_{1}, …, e_{r}, append it to S and continue with step 3).

5) Increase s′ by one, append g_{s′} = S′_{ij} to the tuple G, and append the set {(i, s′) | 1 ≤ i < s′, γ_{i} = γ_{s′}} to B. Then continue with step 3).

6) If W_{d} = ∅, continue with step 9). Otherwise, choose a vector v ∈ W_{d} and remove it from W_{d}.

7) Compute v′ = NR_{σ,G}(v) and v̄ = v′(x_{1}, …, x_{n}, e_{1}, …, e_{r}, 0, …, 0). If v̄ = 0, continue with step 6).

8) Increase s′ and μ by one. Adjoin a new indeterminate ε_{μ} to \overline{P} and extend the grading to this new ring by defining deg\overline{W} (ε_{μ}) = deg\overline{W} (v̄). Extend the term ordering σ to the new ring in such a way that the extension is an elimination ordering for {e_{1}, …, e_{r}}. Append g_{s′} = v̄ − ε_{μ} to G and v̄ to G_{min}. Append the set {(i, s′) | 1 ≤ i < s′, γ_{i} = γ_{s′}} to B. Continue with step 6).

9) If B ≠ ∅ or W ≠ ∅, continue with step 2).

10) Apply the Buchberger Algorithm with Minimalization to the module generated by S and obtain a subtuple S_{min} of S which minimally generates that module. Return the pair (G_{min}, S_{min}) and stop.

This is an algorithm which computes a pair (G_{min}, S_{min}) where G_{min} is a deg-ordered tuple of homogeneous vectors in F_{0} which generate M minimally, and S_{min} is a degordered tuple of homogeneous vectors in ⊕_{i=1}^{μ} P (−d_{1i}) which generate Syz_{P} (G_{min}) minimally. Here μ is the number of elements in G_{min} and d_{1i} is the degree of the i^{th} element in G_{min} for i = 1, …, μ.

Proof. To prove the finiteness of this procedure, we note that elements are appended to G and B only in steps 5) and 8). By induction on s′, we see that all elements of G are of the form a_{1}e_{1} + ⋯ + a_{r}e_{r} + b_{1}ε_{1} + ⋯ + b_{μ}ε_{μ} with a_{i}, b_{j} ∈ P. Moreover, the checks in step 4) and step 7) make sure that at least one polynomial a_{i} is non-zero. Since B is enlarged only when an element is appended to G which has a new leading term, and since this can happen only finitely many times, the procedure terminates after finitely many steps.

Now we prove correctness. If we substitute ε_{1} ↦ 0, …, ε_{μ} ↦ 0 everywhere, the algorithm reduces to the Buchberger Algorithm with Minimalization. Thus the resulting tuple G_{min} is a minimal homogeneous set of generators of M. To show that S_{min} is correct, we use Proposition 3.3. Notice that the elements g_{s′} = v̄ − ε_{μ} appended to G in step 8) are exactly the generators of Ĩ_{M} corresponding to the minimal system of generators G_{min} of M. Thus Proposition 3.3.e says that Syz_{P} (G_{min}) corresponds to the residue class ideal of Ĩ_{M} ∩ P [ε_{1}, …, ε_{μ}] in P [ε_{1}, …, ε_{μ}]/(ε_{1}ε_{j} | i, j = 1, …, μ). Since all extensions of σ are elimination orderings for {e_{1}, …, e_{r}}, the σ-Gröbner basis of Ĩ_{M} contains a system of generators of Syz_{P} (G_{min}).

In fact, we claim that the elements of S are a σ-Gröbner basis of Syz_{P} (G_{min}) when the algorithm stops. This follows by inspecting the effect of step 4): a σ-Gröbner basis element S′_{ij} of Ĩ_{M} corresponds to a syzygy of G_{min} if and only if it is contained in P [ε_{1}, …, ε_{μ}]. Finally, we note that S_{min} is indeed a minimal system of generators of Syz_{P} (G_{min}) because we apply Buchberger’s Algorithm with Minimalization in step 10). ⊓ ⊔

Unlike Remark 4.1, the algorithm described in this theorem returns a minimal system of generators which is not necessarily contained in the given set of generators. Our next remark shows how we can modify the theorem to get this property as well.

Remark 4.3. In the algorithm of the theorem, the elements v of the tuple V for which the corresponding v′ does not involve the indeterminates e_{1}, …, e_{r} form a subtuple V_{min} of V which minimally generates M. By keeping track of the representations of new Gröbner basis elements in terms of the elements in V_{min}, we compute a homogeneous matrix A such that G = V_{min} A. Since G_{min} is a subtuple of G, the columns corresponding to the elements of G_{min} in this matrix equality yield a ma-

trix B such that G_{min} = V_{min} B. Then the exact sequence F_{2} ⟶^{ψ′} F_{1} ⟶^{φ′} M ⟶ 0, where ψ′ is given by the matrix B S_{min} and where φ′ is given by V_{min}, is a minimal homogeneous presentation of M.

Sometimes the vertical strategy is not the most efficient way to compute a minimal homogeneous presentation. For instance, suppose that we have some information about the highest degrees occurring in the minimal presentation of M. In this case, it is desirable to compute the minimal generators and their minimal syzygies degree by degree, and to truncate the computation at the appropriate degree. A method which proceeds degree by degree and determines both the minimal generators and their minimal syzygies simultaneously for each degree is called a horizontal strategy. Our next theorem shows how we can implement it effectively.

To ease the notation, we shall again resort to the convention LT_{σ}(g_{i}) = t_{i}e_{γ_{i}} with t_{i} ∈ 𝕋^{n} and γ_{i} ∈ {1, …, r}. Moreover, we let LT_{σ}(h_{j}) = t̃_{j}e_{η_{j}} with t̃_{j} ∈ 𝕋^{n} and η_{j} ∈ {1, …, μ}.

Theorem 4.4. (Computing Minimal Presentations Horizontally) Let M be a graded submodule of a graded free P -module F_{0} = ⊕_{i=1}^{r} P (−d_{0i}), where d_{0i} >_{Lex} 0 for i = 1, …, r, and let V = (v_{1}, …, v_{s}) be a deg-ordered tuple of nonzero homogeneous vectors which generate M. Consider the following instructions.

1) Choose a term ordering σ on the monoid 𝕋^{n}(e_{1}, …, e_{r}). Let B = ∅, B′ = ∅, W = V, G = ∅, s′ = 0, G_{min} = ∅, μ = 0, S = ∅, s′′ = 0, and S_{min} = ∅.

2) Let d be the smallest degree with respect to Lex of an element in B ∪ B′ or in W. Form the subset B_{d} of B, the subset B′_{d} of B′, the subtuple W_{d} of W, and delete their entries from B, B′, and W, respectively.

3) If B′_{d} = ∅, continue with step 6). Otherwise, choose a pair (i, j) ∈ B′_{d} and remove it from B′_{d}.

4) Compute the S-vector of h_{i} and h_{j} and call it S_{ij}. Then compute the normal remainder S′_{ij} = NR_{σ,S}(S_{ij}). If S′_{ij} = 0, continue with step 3).

5) Increase s′′ by one, append h_{s′′} = S′_{ij} to the tuple S, append the set {(i, s′′) | 1 ≤ i < s′′, η_{i} = η_{s′′}} to B′, and continue with step 3).

6) If B_{d} = ∅, continue with step 10). Otherwise, choose a pair (i, j) ∈ B_{d} and remove it from B_{d}.

7) Compute the S-vector of g_{i} and g_{j} and call it S_{ij}. Then compute the normal remainder S′_{ij} = NR_{σ,G}(S_{ij}). If S′_{ij} involves one of the indeterminates e_{1}, …, e_{r} then increase s′ by one, append g_{s′} = S′_{ij} to G, append {(i, s′) | 1 ≤ i < s′, γ_{i} = γ_{s′}} to B, and continue with step 6).

8) Compute the normal remainder S′′_{ij} = NR_{σ,S}(S′_{ij}). If S′′_{ij} = 0, continue with step 6).

9) Increase s′′ by one. Append h_{s′′} = S′′_{ij} to the tuples S and S_{min}. Append {(i, s′′) | 1 ≤ i < s′′, η_{i} = η_{s′′}} to B′. Continue with step 6).

10) If W_{d} = ∅, continue with step 13). Otherwise, choose a vector v ∈ W_{d} and remove it from W_{d}.

11) Compute v′ = NR_{σ,G}(v) and v̄ = v′(x_{1}, …, x_{n}, e_{1}, …, e_{r}, 0, …, 0). If v̄ = 0, continue with step 10).

12) Increase s′ and μ by one. Adjoin a new indeterminate ε_{μ} to \overline{P} and extend the grading to this new ring by defining deg\overline{W} (ε_{μ}) = deg\overline{W} (v′). Extend the term ordering σ to the new ring in such a way that the extension is an elimination ordering for {e_{1}, …, e_{r}}. Append g_{s′} = v̄ − ε_{μ} to the tuple G and v̄ to G_{min}. Append {(i, s′) | 1 ≤ i < s′, γ_{i} = γ_{s′}} to B. Continue with step 10).

13) If B = B′ = ∅ and W = ∅, return the pair (G_{min}, S_{min}) and stop. Otherwise, continue with step 2).

This is an algorithm which computes a pair (G_{min}, S_{min}) where G_{min} is a degordered tuple of homogeneous vectors in F_{0} which generate M minimally, and where S_{min} is a deg-ordered tuple of homogeneous vectors in ⊕_{i=1}^{μ} P (−d_{1i}) which generate Syz_{P} (G_{min}) minimally. Here μ is the number of elements in G_{min} and d_{1i} is the degree of the i^{th} element in G_{min} for i = 1, …, μ.

Proof. First we show finiteness. The procedure terminates when B, B′, and W are empty. Only B and B′ are enlarged during the computation. Each time the loop in steps 3)–5) is executed, one pair is removed from B_{d} (and thus from B). Similarly, performing the loops in steps 6)–9) and 10)–12) removes one element from B_{d} and W_{d}, respectively. Hence it suffices to show that B and B′ are enlarged only finitely many times.

The set B is enlarged in steps 7) and 12) only if an element g_{s′} is appended to G whose normal remainder with respect to the previous elements of G is nonzero. In this case, ⟨LT_{σ}(G)⟩ is enlarged, and this can happen only finitely many times. Similarly, the set B′ is enlarged in steps 5) and 9) only if an element h_{s′′} is appended to S which has a new leading term. Again this can happen only finitely many times.

Now we prove correctness. We consider the entire computation as a computation in P̃ = K[x_{1}, …, x_{n}, e_{1}, …, e_{r}, ε_{1}, …, ε_{μ}]. We claim that the elements of W, G, G_{min}, S, and S_{min} are always of the form f_{1}e_{1} + ⋯ + f_{r}e_{r} + f̃_{1}ε_{1} + ⋯ + f̃_{μ}ε_{μ} with f_{i}, f̃_{j} ∈ P. This is clearly true at the outset. By the manner in which B and B′ are enlarged in steps 5), 7), 9), and 12), the new S-vectors continue to have this shape. Furthermore, reducing one such vector using another one preserves the shape. Hence the elements of G and S have the desired form. Clearly the construction of G_{min} in step 12) and S_{min} in step 9) also preserves the given shape.

By induction on s′′ it follows that elements h_{s′′} which are appended to S in step 5) and 9) do not involve the indeterminates {e_{1}, …, e_{r}}. In particular, their leading position is an element η_{j} ∈ {1, …, μ}.

If we set ε_{1} ↦ 0, …, ε_{μ} ↦ 0 in the entire algorithm and ignore the instructions concerning S and S_{min}, we see that we are applying Buchberger’s Algorithm with Minimalization to the tuple V. Therefore the tuple \overline{G} = (ḡ_{1}, …, ḡ_{s′}) where ḡ_{i} = g_{i}(x_{1}, …, x_{n}, e_{1}, …, e_{r}, 0, …, 0) is a σ-Gröbner basis of M and G_{min} is a subtuple of \overline{G} whose elements are a minimal system of generators of M.

Next we let G_{min} = (g̃_{1}, …, g̃_{μ}). We claim that the elements of G map to zero under the homomorphism defined by ε_{1} ↦ g̃_{1}, …, ε_{μ} ↦ g̃_{μ}. This follows by induction on s′ because in step 5) an element of ⟨g_{1}, …, g_{s′−1}⟩ is appended to G and in step 8) we have

g_{s′}(x_{1}, …, x_{n}, e_{1}, …, e_{r}, g̃_{1}, …, g̃_{μ−1}) = v̄ − g_{μ} = 0

Hence the elements of G are contained in the ideal (g̃_{1} −ε_{1}, …, g̃_{μ} −ε_{μ}) of \overline{P}. Since we know already that G_{min} is a minimal system of generators of M, it follows that Ĩ_{M} = (g̃_{1} − ε_{1}, …, g̃_{μ} − ε_{μ}) + Ẽ is the ideal of a homogeneous presentation of M. Therefore, by Proposition 3.3, it suffices to prove that S ∪ {ε_{i}ε_{j} | i, j = 1, …, μ} is a σ-Gröbner basis of Ĩ_{M} ∩ P [ε_{1}, …, ε_{μ}] and S_{min} ∪ {ε_{i}ε_{j} | i, j = 1, …, μ} is a minimal set of generators of this ideal.

Since σ is an elimination ordering for {e_{1}, …, e_{r}}, steps 3), 4), 5), 8), and 9) correspond to the application of Buchberger’s Algorithm with Minimalization to this ideal. Hence the claim follows from Propositions 2.5.a and 2.8.a,b. Altogether, we have shown that G_{min} is a minimal system of generators of M and S_{min} is a minimal system of generators of Syz_{P} (G_{min}). ⊓ ⊔

Let us add a few remarks about the inner workings of this algorithm.

Remark 4.5. Assume that we are in the setting of Theorems 4.2 and 4.4.

a) If we view the vertical and the horizontal strategy for computing a minimal homogeneous presentation as algorithms in \overline{P}, they are nothing but two concrete versions of the same general algorithm, namely the Homogeneous Buchberger Algorithm. The difference lies in the particular strategies for choosing the next pair to work on, and that we do not have to consider critical pairs (i, s′) with γ_{i} ≠ γ_{s′} because e_{i} e_{s′} maps to zero in the idealization of M.

b) The proof of Theorem 4.4 shows that when the algorithm stops the tuple \overline{G} = (ḡ_{1}, …, ḡ_{s′}) where ḡ_{i} = g_{i}(x_{1}, …, x_{n}, e_{1}, …, e_{r}, 0, …, 0) is a σ-Gröbner basis of M, and the tuple S is a σ-Gröbner basis of Syz_{P} (G_{min})

c) Note that one can choose the term ordering on 𝕋^{n}⟨ε_{1}, …, ε_{μ}⟩ freely, as long as it extends σ. Hence the algorithm can be used to compute a Gröbner basis of the syzygy module Syz(G_{min}) with respect to an arbitrary term ordering.

5. Computation of Minimal Graded Free Resolutions

As in the preceding sections, let K be a field, let P = K[x_{1}, …, x_{n}] be positively graded by W ∈ Mat_{m,n}(ℤ), let M be a graded P -submodule of a graded free P -module F_{0} = ⊕_{i=1}^{r_{0}}(−d_{0i}), and let V = (v_{1}, …, v_{s}) be a tuple of non-zero homogeneous vectors which generate M. For d ∈ ℤ^{m}, the minimal graded free resolutions of M and M(d) differ only by the shift d. Therefore we shall henceforth assume that we have d_{0i} >_{Lex} 0 for i = 1, …, r_{0}. In order to facilitate the formulation of our algorithms, we introduce a number of conventions.

The i^{th} graded free module F_{i} is always of the form F_{i} = ⊕_{j=0}^{r_{i}}(−d_{ij}). Its canonical basis is denoted by {ε_{1}^{(i)}, …, ε_{r_{i}}^{(i)}} and is always kept deg-ordered. The idealization of the module F_{0} ⊕ ⋯ ⊕ F_{n} is a residue class ring of the ring P̃ = P [{ε_{j}^{(i)} | i ∈ {0, …, n}, j ∈ {1, …, r_{i}}}]. As in the previous section, the entire computation can be viewed as a computation in P̃. In particular, the elements of each F_{i} are identified with their images in this ring.

The first algorithm we present is a straightforward generalization of the vertical strategy for computing minimal presentations (see Theorem 4.2).

Theorem 5.1. (Computing Minimal Resolutions Vertically) Let M be a graded submodule of a graded free P -module F_{0} = ⊕_{i=1}^{r_{0}} P (−d_{0i}), where d_{0i} >_{Lex} 0 for i = 1, …, r_{0}. Let V = (v_{1}, …, v_{s}) be a deg-ordered tuple of nonzero homogeneous vectors which generate M. Consider the following sequence of instructions.

1) Let i = 0. Equip \overline{P} = P [ε_{1}^{(i)}, …, ε_{r_{i}}^{(i)}] with the grading defined by \overline{W} = (W | d_{i1} ⋯ d_{ir_{i}}). Choose a term ordering σ on 𝕋^{n}(ε_{1}^{(i)}, …, ε_{r_{i}}^{(i)}). Let B = ∅, W = V, G = ∅, s′ = 0, G_{min}^{(i)} = ∅, r_{i+1} = 0, and S = ∅.

2) Let d be the smallest degree with respect to Lex of an element in B or in W. Form the subset B_{d} and the subtuple W_{d}, and delete their entries from B and W, respectively.

3) If B_{d} = ∅, continue with step 6). Otherwise, chose a pair (j, k) ∈ B_{d} and remove it from B_{d}.

4) Form the S-vector S_{jk} of g_{j} and g_{k}. Then compute S′_{jk} = NR_{σ,G}(S_{jk}). If S′_{jk} = 0 continue with step 3). If S′_{jk} ≠ 0 and it does not involve the indetermi-

nates ε_{1}^{(i)}, …, ε_{r_{i}}^{(i)}, then append it to S and continue with step 3).

5) Increase s′ by one, append g_{s′} = S′_{jk} to the tuple G, and append the set {(j, s′) | 1 ≤ j < s′, γ_{j} = γ_{s′}} to B. Then continue with step 3).

6) If W_{d} = ∅, continue with step 9). Otherwise, choose a vector v ∈ W_{d} and remove it from W_{d}.

7) Compute v′ = NR_{σ,G}(v) and v̄ = v′(x_{1}, …, x_{n}, ε_{1}^{(i)}, …, ε_{r_{i}}^{(i)}, 0, …, 0). If v̄ = 0, continue with step 6).

8) Increase s′ and r_{i+1} by one. Adjoin a new indeterminate ε_{r_{i+1}}^{(i+1)} to \overline{P} and extend the grading to this new ring by defining deg\overline{W} (ε_{r_{i+1}}^{(i+1)}) = deg\overline{W} (v̄). Extend the term ordering σ to the new ring in such a way that the extension is an elimination ordering for {ε_{1}^{(i)}, …, ε_{r_{i}}^{(i)}}. Append the element g_{s′} = v̄ − ε_{r_{i+1}}^{(i+1)} to G and the element v̄ to G_{min}^{(i)}. Append the set {(j, s′) | 1 ≤ j < s′, γ_{j} = γ_{s′}} to B. Continue with step 6).

9) If B ≠ ∅ or W ≠ ∅, continue with step 2).

10) If S ≠ 0, then increase i by one and equip \overline{P} = P [ε_{1}^{(i)}, …, ε_{r_{i}}^{(i)}] with the grading defined by \overline{W} = (W | d_{i1} ⋯ d_{ir_{i}}). Restrict the term ordering σ to 𝕋^{n}(ε_{1}^{(i)}, …, ε_{r_{i}}^{(i)}). Let B = ∅, W = S, G = ∅, s′ = 0, G_{min}^{(i)} = ∅, r_{i+1} = 0, and S = ∅. Then continue with step 2).

11) Let ℓ = i + 1. Return the list (G_{min}^{(0)}, …, G_{min}^{(ℓ−1)}) and stop. This is an algorithm which computes a list of deg-ordered homogeneous matrices (G_{min}^{(0)}, …, G_{min}^{(ℓ−1)}) such that the P -linear maps φ_{j} : F_{j} ⟶ F_{j−1} given by G_{min}^{(j−1)} for j = 1, …, ℓ yield a minimal graded free resolution

0 ⟶ F_{ℓ} ⟶^{φ_{ℓ}} F_{ℓ−1} ⟶^{φ_{ℓ−1}} ⋯ ⟶^{φ_{3}} F_{2} ⟶^{φ_{2}} F_{1} ⟶^{φ_{1}} M ⟶ 0

Proof. The loop defined by steps 2)–9) agrees with the main loop used in Theorem 4.2 to compute a minimal homogeneous presentation of M vertically. In the proof of this theorem we saw that, after this loop is finished for some particular value of i, the tuple G_{min}^{(i)} contains a minimal set of generators of the module generated by W and the tuple S contains a σ-Gröbner basis of Syz_{P} (G_{min}^{(i)}). Thus, if we feed S as the new input tuple W into the next iteration of the loop, we compute a minimal system of generators G_{min}^{(i+1)} of Syz_{P} (G_{min}^{(i)}) and a Gröbner basis of Syz_{P} (G_{min}^{(i+1)}). By Hilbert’s Syzygy Theorem, this process stops after at most n − 1 steps, i.e. after at most n − 1 steps we have S = ∅ and the algorithm stops. ⊓ ⊔

Although the vertical strategy for computing minimal graded free resolutions is in general rather crude, it has some merits.

Remark 5.2. Suppose we are in the setting of the theorem.

a) If we do not want to know the whole minimal graded free resolution of M, or if we discover during the computation that the going is getting too tough, we can stop the execution of the algorithm after the loop of steps 2)–9) is finished for a particular value of i and get the correct first i + 1 graded free modules and maps.

b) When i ≥ 1, we can save some applications of step 4), since we know that S is a Gröbner basis after the loop 2)–9) for i − 1 is finished and this is the new input tuple W.

c) In step 10) we can choose σ freely. Then we do not know that W is a Gröbner basis, i.e. the optimization of b) cannot be used, but we get in G a σ-Gröbner basis of Syz_{P} (G_{min}^{(i−1)}) for the chosen term ordering σ.

Our second algorithm for computing minimal graded free resolutions generalizes the horizontal strategy for computing minimal homogeneous presentations (see Theorem 4.4). As before, we consider the entire computation as a computation in a large polynomial ring P̃ = P [ε_{1}^{(0)}, …, ε_{r_{n}}^{(n)}] a residue class ring of which is the idealization of F_{0} ⊕ ⋯ ⊕ F_{n}, and we identify all vectors with their images in P̃. For the purposes of this theorem it will be convenient to replace the Division Algorithm (see for instance [7], 1.6.4) with a procedure that merely head reduces a given polynomial f with respect to a list of polynomials G. We shall denote the result of such a reduction procedure by HR_{σ,G}(f) and call it a head reduction remainder of f.

Theorem 5.3. (Computing Minimal Resolutions Horizontally) Let M be a graded submodule of a graded free P -module F_{0} = ⊕_{i=1}^{r_{0}} P (−d_{0i}), where d_{0i} >_{Lex} 0 for i = 1, …, r_{0}. Let V = (v_{1}, …, v_{s}) be a deg-ordered tuple of nonzero homogeneous vectors which generate M. Consider the following sequence of instructions.

1) Let σ be a term ordering on 𝕋^{n}(ε_{1}^{(0)}, …, ε_{r_{0}}^{(0)}), let \overline{P} = P [ε_{1}^{(0)}, …, ε_{r_{0}}^{(0)}] be graded by \overline{W} = (W | d_{01} ⋯ d_{0r_{0}}), let r_{1} = ⋯ = r_{n} = 0, let B = \{v_{1}, …, v_{s}\}, let G = ∅, and let G_{min} = ∅.

2) Let d be the smallest degree with respect to Lex of an element of B. Form the subset B_{d} of B and remove it from B.

3) If B_{d} = ∅, continue with step 7). Otherwise, let i be the largest upper index of an indeterminate ε_{k}^{(j)} occurring in a polynomial of B_{d}. Let f ∈ B_{d} be a polynomial which involves that indeterminate. Remove f from B_{d}.

4) Compute f′ = HR_{σ,G}(f). If one of the indeterminates ε_{1}^{(i−1)}, …, ε_{r_{i−1}}^{(i−1)} occurs in f′, append f′ to G, append to B all S-polynomials of f′ and a polynomial g in G such that LT_{σ}(f′) and LT_{σ}(g) involve the same indeterminate ε_{j}^{(i−1)}, and continue with step 3).

5) If none of the indeterminates {ε_{1}^{(i)}, …, ε_{r_{i}}^{(i)}} occurs in f′, continue with step 3).

6) Increase r_{i+1} by one. Adjoin a new indeterminate ε_{r_{i+1}}^{(i+1)} to \overline{P} and extend the grading to this new ring by defining deg\overline{W} (ε_{r_{i+1}}^{(i+1)}) = d. Extend the term ordering σ to the new ring in such a way that the extension is an elimination ordering for {ε_{1}^{(0)}, …, ε_{r_{i}}^{(i)}}. Compute the polynomial

\overline{f} = f′(x_{1}, …, x_{n}, ε_{1}^{(i)}, …, ε_{r_{i}}^{(i)}, 0, …, 0)

Append g = \overline{f} − ε_{r_{i+1}}^{(i+1)} to G and \overline{f} to G_{min}. For all h ∈ B such that LT_{σ}(g) and LT_{σ}(h) involve the same indeterminate ε_{j}^{(i)}, compute the S-polynomial of g and h and append it to B. Then continue with step 3).

7) If B = ∅, return the tuple G_{min} and stop. Otherwise, continue with step 2). This is an algorithm which computes a deg-ordered tuple G_{min} of homogeneous polynomials in \overline{P} = P [ε_{1}^{(0)}, …, ε_{r_{0}}^{(0)}, …, ε_{1}^{(ℓ)}, …, ε_{r_{ℓ}}^{(ℓ)}] such that the homogeneous maps of graded free P -modules φ_{i} : F_{i} ⟶ F_{i−1} defined by the elements of G ∩ P [ε_{1}^{(i)}, …, ε_{r_{i}}^{(i)}] yield a minimal graded free resolution

0 ⟶ F_{ℓ} ⟶^{φ_{ℓ}} F_{ℓ−1} ⟶^{φ_{ℓ−1}} ⋯ ⟶^{φ_{3}} F_{2} ⟶^{φ_{2}} F_{1} ⟶^{φ_{1}} M ⟶ 0

Proof. First we prove that the procedure is well-defined, i.e. that all instructions can be executed. For this purpose it suffices to show the following claim: For a polynomial f which is contained in B or in G at some point during the computation, there exists a number i ≥ 0 such that f is of the shape

f = a_{1}ε_{1}^{(i)} + ⋯ + a_{r_{i}}ε_{r_{i}}^{(i)} + b_{1}ε_{1}^{(i+1)} + ⋯ + b_{r_{i+1}}ε_{r_{i+1}}^{(i+1)}

with a_{j}, b_{k} ∈ P. This is clearly the case at the outset when v_{1}, …, v_{s} involve only the indeterminates ε_{1}^{(0)}, …, ε_{r_{0}}^{(0)}. Later B and G are enlarged only in steps 4) and 6).

When f′ = HR_{σ,G}(f) is appended to G in step 4), the element f ∈ B has been head reduced using only elements of the shape shown above. Thus also f′ has this shape. When g = \overline{f′} − ε_{r_{i+1}}^{(i+1)} is appended to G in step 6), the element f′ involves only indeterminates ε_{k}^{(j)} with upper index j ∈ {i, i+1}. Consequently, the polynomial \overline{f′} = f′(x_{1}, …, x_{n}, ε_{1}^{(i)}, …, ε_{r_{i}}^{(i)}, 0, …, 0) involves only indeterminates ε_{k}^{(j)} with upper index j = i, and so g has the claimed shape. When B is enlarged in step 4) or 6), the new elements are S-polynomials of polynomials of the claimed shape. By the construction of σ, the leading term of a polynomial involves one of the indeterminates ε_{k}^{(j)} with the smaller of the two upper indices. Since both leading terms are required to involve the same indeterminate ε_{k}^{(j)}, it follows that the S-polynomials appended to B have the claimed shape, and the claim is proved.

Now we turn to proving finiteness and correctness of the procedure. The procedure stops when B becomes empty. New S-polynomials are appended to B in step 4) or 6) only if a new element is appended to G in the same step. The new element of G has a leading term which is not contained in the ideal generated by LT_{σ}(G). Hence finiteness will follow if we can show that only finitely many new indeterminates ε_{r_{i+1}}^{(i+1)} are introduced in step 6).

To prove this and the correctness of the algorithm, it is sufficient to prove the following claim by induction on i: After finitely many steps, all elements f ∈ B involving indeterminates ε_{k}^{(i)} with upper index i have been treated, and at that point the tuple G_{i} = G_{min} ∩ P [ε_{1}^{(i)}, …, ε_{r_{i}}^{(i)}] is a minimal system of generators of Syz(G_{i−1}). To this end, we set ε_{k}^{(j)} ↦ 0 for j > i everywhere and show that the resulting algorithm reduced to the horizontal strategy for computing minimal homogeneous presentations (see Theorem 4.4). The choice of f in step 3) ensures that S-polynomials involving only the indeterminates ε_{1}^{(i)}, …, ε_{r_{i}}^{(i)} are treated first. This corresponds to doing the loop in steps 3) – 5) before the loops in steps 6) – 9) and 10) – 12) in Theorem 4.4. The fact that we replaced the normal remainder computation by a head reduction remainder does not affect the correctness of the algorithm by Remark 2.5.6.a. The elements f ∈ B which produce an f′ appended to G in step 4) correspond to the pairs treated in steps 6) – 9) in Theorem 4.4. The elements f′ discarded by step 5) correspond to the vectors v′ discarded in step 11) in Theorem 4.4. Finally, step 6) corresponds to step 12) in Theorem 4.4. Altogether, it follows inductively from Theorem 4.4 that the algorithm is correct. By Hilbert’s Syzygy Theorem, the tuple G_{min} is finite and the computation stops after finitely many steps. ⊓ ⊔

The preceding algorithm admits several further optimizations.

Remark 5.4. Suppose that we are in the setting of the theorem.

a) In view of the checks preformed in steps 4) and 5), it suffices that the procedure HR_{σ,G}(f) stops when all indeterminates ε_{k}^{(i−1)}, ε_{ℓ}^{(i)} are eliminated from f.

b) Let W be a matrix of non-negative integers. Then the head reduction procedure can be further optimized by noting that a polynomial f can be head reduced by g ∈ G only if deg\overline{W} (f) is componentwise larger than or equal to deg\overline{W}. For instance, a homogeneous polynomial f of degree \binom{4}{3} cannot be reduced by a homogeneous polynomial of degree \binom{3}{4}. This observation restricts the set of possible reductors in G.

Aside from the simplicity of the formulation of the algorithm described in Theorem 4.4 (it requires merely seven steps!), it offers ample possibilities for introducing optimizations. For instance, the optimizations provided by M. Caboara and the authors in [4] can be used without difficulty. Although extensive practical tests are still lacking, the authors expect that this algorithm will provide a valuable tool for actual implementations.

Acknowledgements: With great pleasure we acknowledge the kind hospitality and the cordial atmosphere during the NATO workshop in Chisinau/Moldavia. We thank the organizers of this workshop for the superb job they have done. The reseach reported in this paper was partially supported by GNSAGA (Italy) and Genova University.

References

[1] J. Apel, A relationship between Gröbner bases of ideals and vector modules of G-algebras, In: Proc. Int. Conf. Novosibirsk 1989, Contemp. Math. 131, Amer. Math. Soc., Providence 1992, pp. 195–204.

[2] A. Capani, G. De Dominicis, G. Niesi and L. Robbiano, Computing minimal resolutions, J. Pure Appl. Alg. 117-118 (1997), 105–117.

[3] M. Caboara, A modified Buchberger algorithm for resolutions, preprint 2003.

[4] M. Caboara, M. Kreuzer and L. Robbiano, Efficiently computing minimal sets of critical pairs, J. Symb. Comput. (to appear)

[5] M. Caboara and M. Silvestri, Classification of compatible module orderings, J. Pure Appl. Alg. 142 (1999), 13–24.

[6] M. Caboara and C. Traverso, The powerful Buchberger algorithm for modules, ??? (1997)

[7] M. Kreuzer and L. Robbiano, Computational Commutative Algebra 1, Springer, Heidelberg 2000.

[8] M. Kreuzer and L. Robbiano, Computational Commutative Algebra 2, Springer, Heidelberg 2004.

[9] M. Kreuzer and L. Robbiano, Basic tools for computing in multigraded rings, in: J. Herzog, V. Vuletescu (eds.), Commutative Algebra, Singularities and Computer Algebra, Proc. Conf. Sinaia 2002, NATO Science Series II, Kluwer Acad. Publ., Dordrecht 2003, pp. 197–216.

[10] R. La Scala and M. Stillman, Strategies for computing minimal free resolutions, J. Symb. Comput. 26 (1998), 409–431.

[11] M. Nagata, Local rings, Wiley & Sons, New York 1962.

[12] T. Siebert, Algorithms for the computation of free resolutions, in: B.H. Matzat, G.-M. Greuel and G. Hiss (eds.), Algorithmic Algebra and Number Theory, Springer, Berlin 1998, pp. 295– 310.

Martin Kreuzer, Fachbereich Mathematik, Universität Dortmund, D-44221 Dortmund, Germany

Lorenzo Robbiano, Dipartimento di Matematica, Università di Genova, I-16146 Genova, Italy