Bounded regularity

Claus Diem

October 7, 2014

Abstract Let k be a field and S the polynomial ring k[x_{1}, …, x_{n}]. For a nontrivial finitely generated homogeneous S-module M with grading in ℤ, an integer D and some homogeneous polynomial f in S, it is defined what it means that f is regular on M up to degree D. Following the usual definition of regularity, a generalization to finite sequences of polynomials in S is given.

Different criteria for a finite sequence of polynomials in S to be regular up to a particular degree are given: first a characterization with Hilbert series, then a characterization with first syzygies, and finally, for M = S, characterizations with Betti numbers as well as with the Koszul complex and free resolutions.

1 The notion of bounded regularity

Let k be a field and S = k[x_{1}, …, x_{n}] be a polynomial ring over k. We consider finite sequences of homogeneous polynomials of positive degrees and their operation on non-trivial finitely generated graded S-modules (with grading in ℤ). Here and in the following, by a polynomial, we always mean an element of S. Moreover, by an S-module we mean in the following a graded S-module with grading in ℤ.

If now M is such a module and additionally M has finite length, that is, M_{n} = 0 for n ≫ 0, then clearly, there is no regular element on M. It might however be the case that a homogeneous polynomial is regular on M “up to a particular degree”. This motivates our basic definition:

Definition 1 Let M be a non-trivial finitely generated S-module.

Let f be a homogeneous polynomial of degree d and D an integer. Then f is regular regular up to degree D on M if f is non-constant and for all i ≤ D − d, the linear map M_{i} ⟶ M_{i+d} given by multiplication with f is injective.

More generally, let f_{1}, …, f_{r} be a sequence of homogeneous polynomials and D ∈ ℤ. Then the sequence is regular up to degree D on M if all the polynomials are non-constant and for each q = 1, …, r, f_{q} is regular on M/(f_{1}, …, f_{q−1})M up to degree D.

Following the usual terminology, a sequence is simply called regular up to degree D if it fulfills the definition with S = M.

Let M and f_{1}, …, f_{r} be as in the definition. As M is assumed to be finitely generated, d_{min} := min{i ∈ ℤ | M_{i} ≠ 0} exists. As the polynomials are homogeneous of positive degree, we then have (M/(f_{1}, …, f_{r})M)_{d_{min}} = M_{d_{min}} ≠ 0. Therefore, M/(f_{1}, …, f_{r})M ≠ 0 which is a necessary condition in order that a sequence be regular; cf. [Mat86], [Eis95]. Clearly, the system is regular if and only if it is regular up to degree D for each D ∈ ℤ. This confirms that our definition is reasonable.

Let us call a Laurant series over ℤ in the variable t simply a Laurant series, and let us extend the meaning of a ≡ b mod t^{d} for two Laurant series a, b and d ∈ ℕ to any d ∈ ℤ in the obvious way: a ≡ b mod t^{d} if and only if the t-valuation of a − b is at least d.

Let now M be as above and let f be a homogeneous polynomial of positive degree d. Furthermore, let H_{M} = H_{M}(t) = ∑_{i=−∞}^{∞} dim_{k}(M_{i})t^{i} be the Hilbert series of M, which is a Laurent series over ℤ defined by a rational function.

It is immediate that f is regular up to degree D on M if and only if H_{M/fM} ≡ (1−t^{d})·H_{M} mod t^{D+1}. Therefore, if the sequence f_{1}, …, f_{r} with homogeneous polynomials of degrees d_{1}, …, d_{r} is regular up to degree D on M then H_{M/(f_{1},...,f_{r})M} ≡ ∏_{i=1}^{r}(1 − t^{d_{i}}) · H_{M} mod t^{D+1}. We will prove, in Section 4, that the converse of this statement also holds. This establishes in particular that regularity up to a particular degree is independent of the ordering of the polynoimials.

Further contributions in this article are: In the fith section, we give characterizations of regularity up to some degree in terms of first syzygies. In the sixth and last section, we characterize regularity up to some degree on S itself in terms of Betti numbers as well as in terms of the Koszul complex and free resolutions. We also prove some general results on complexes, in particular on the Koszul complex, from a “bounded degree” point of view.

2 Relationship with other works and applications

This article is closely related to the article [Par10] by K. Pardue, the article [PR09] by K. Pardue and B. Richert, to the extended abstract [BFS04] by M. Bardet, J.-C. Faugère, B. Salvy, the work [BFSY05] by these authors and B.-Y. Yang and thesis of M. Bardet ([Bar04]). It is also inspired by R. Fröberg’s article [Frö85]. Furthermore, it has applications to the analysis of algorithms for the solution of systems of polynomial equations, for example via J.-C. Faugère’s F_{5}-algorithm ([Fau02]).

We comment on some of these relationships in this section. Further comments can be found in remarks in the following sections.

Bounded regularity and semi-regularity

The notion of regularity up to a particular degree is related to semi-regularity, which was defined in [Par00] in the following way; see [Par10].

Definition 2 Let I be a homogeneous ideal of S and f a homogeneous polynomial of degree d. Then f is semi-regular on S/I if for each i ∈ ℤ the linear map (S/I)_{i} ⟶ (S/I)_{i+d} induced by multiplication with f is injective or surjective.

Let now f_{1}, …, f_{r} be homogeneous polynomials. Then the sequence is semi-regular if for all q = 1, …, r, f_{q} is semi-regular on S/(f_{1}, …, f_{q−1}).

The condition on the linear maps can of course be reformulated as follows: Any coordinate matrices of the linear maps always have full rank.

Recall that for a non-trivial finitely generated module M of finite length, the Castelnuovo-Mumford regularity of M is equal to the maximal d ∈ ℤ with M_{d} ≠ 0; see [Eis05, Corollary 4.4]. We see that any semi-regular sequence f_{1}, …, f_{r} is regular up to the Castelnuovo-Mumford regularity of S/(f_{1}, …, f_{r}). The converse to this statement does of course not hold. The easiest example for this is arguably the sequence x^{2}, xy, y^{2} which was already mentioned in [Par00]. Note however that the sequence x^{2}, y^{2}, xy is indeed semi-regular.

Let us note also that one defines the Hilbert regularity of a non-trivial finitely generated S-module as the smallest index from which on the Hilbert function agrees with the Hilbert polynomial. Thus for a finitely generated Smodule M of finite length the Hilbert regularity is equal to the Castelnuovo-Mumford regularity plus one.

There is also the following reformulation of semi-regularity in terms of Hilbert series:

For any power series ∑_{i=0}^{∞} a_{i}t^{i} ∈ ℤ[[t]], let | ∑_{i=0}^{∞} a_{i}t^{i}| be the series ∑_{i=0}^{∞} b_{i}t^{i} with

b_{i} = \{ \begin{matrix}a_{i} & if a_{j} > 0 for all 0 ≤ j ≤ i \\ 0 & otherwise . \end{matrix}

Then f of degree d is semi-regular on S/I if and only if H_{S/(I,f)} = |(1 − t^{d}) · H_{S/I}|. It follows that a system f_{1}, …, f_{r} with degrees d_{1}, …, d_{r}

is semi-regular if and only if for all q ≤ r, H_{S/(f_{1},...,f_{q})} = |^{\frac{∏_{i=1}^{q}(1−t^{d_{i}})}{(1−t)^{n}}}|.

Bounded regularity and d-regularity

Regularity up to a particular degree as defined in this work is closely related to what is called d-regularity in [BFS04]: There a sequence of homogeneous polynomials f_{1}, …, f_{r} for which S/(f_{1}, …, f_{r}) is Artinian called d-regular for some natural number d if and only if it is regular up to degree d + 1 in our terminology.

There and also in [BFSY05] and [Bar04] the phrase “semi-regular sequence” was given a new meaning, different from the one introduced in [Par00]: First, in order that a system of homogeneous polynomials f_{1}, …, f_{r} can be semi-regular in the sense of these works, the quotient S/(f_{1}, …, f_{r}) has be be Artinian (which implies that r ≥ n). Now, for such a sequence the Hilbert regularity of S/(f_{1}, …, f_{r}) is called degree of regularity and is denoted by d_{reg}. Finally, such a sequence is called semi-regular if it is d_{reg}- regular. This means that it is called semi-regular if it is regular up to the Castelnuovo-Mumford regularity of S/(f_{1}, …, f_{r}).

Fröberg’s conjecture

A well known conjecture due to R. Fröberg ([Frö85]) states that for any n and any generic sequence of homogeneous polynomials f_{1}, …, f_{r} ∈ k[x_{1}, …, x_{n}] for a field k of characteristic 0, one has H_{S/(f_{1},...,f_{r})} = |^{\frac{∏_{i=1}^{r}(1−t^{d_{i}})}{(1−t)^{n}}}|. Here by a generic sequence of homogeneous polynomials of degrees d_{1}, …, d_{r} we mean a sequence of polynomials of the given degrees in which all monomials occur and the system of coefficients is algebraically independent over the prime field.

Equivalently, the conjecture says that any generic sequence of polynomials in characteristic 0 is semi-regular in the original sense. Another reformulation is: For r ≥ n, a generic sequence of homogeneous polynomials f_{1}, …, f_{r} is regular up to the Castelnuovo-Mumford regularity of S/(f_{1}, …, f_{r}), which means that it is semi-regular in the sense of [BFS04],

[BFSY05] and [Bar04]. Note that this reformulation is immediate even though for a concrete sequence it does not hold that semi-regularity and regularity up to the Castelnuovo-Mumford regularity of the quotient are equivalent.

In line with Fröberg’s conjecture, one observes experimentally that for a randomly generated sequence over a finite field k one usually has H_{S/(f_{1},...,f_{r})} =

|^{\frac{∏_{i=1}^{r}(1−t^{d_{i}})}{(1−t)^{n}}}|. Moreover, also in line with the conjecture as it was first stated in [Frö85], one observes: If one considers random sequences with at least one non-trivial common solution in \overline{k} (that is, V (f_{1}, …, f_{r}) is non-trivial), then one usually has H_{S/(f_{1},...,f_{r})} = sup\{|^{\frac{∏_{i=1}^{r}(1−t^{d_{i}})}{(1−t)^{n}}}|, 1\}, where the supremum is given by the coefficient-wise maximum. By the characterization of sequences which are regular up to a particular degree given in Proposition 1 below, the sequence is then regular up to the degree of |^{\frac{∏_{i=1}^{r}(1−t^{d_{i}})}{(1−t)^{n}}}|.

Applications on the analysis of algorithms

These observations have implications for the analysis of algorithms to compute solutions of systems. For example, let us consider the following basic algorithmic problem: The input consists of a system of homogeneous polynomials f_{1}, …, f_{r} of positive degrees over a finite field k such that either the system f_{1}, …, f_{r} has no solution in ℙ^{n}(\overline{k}) or exactly one solution, counted with multiplicities, which lies in k. (The latter condition is automatic if k is perfect.) With other words, the assumption is that the projective scheme defined by f_{1}, … f_{n} is either empty or consists of exactly one isolated and reduced point which moreover is k-rational. The task is to determine if there is a solution or not and if this is the case to compute the solution.

A possible algorithm for this is as follows: One determines the subspaces (f_{1}, …, f_{r})_{d} inside k[x_{1}, …, x_{n}]_{d} for increasing d (that is, one computes a basis). If for some d, the subspace is the full space, one knows that there is no solution. If on the other hand for some d the subspace has codimension 1, one computes a “potential solution” by linear algebra. If this “potential solution” is correct, one has found the solution. If it is incorrect, the system is not solvable. The algorithm terminates because the assumption can be reformulated by saying that the Hilbert polynomial of S/(f_{1}, …, f_{r}) is either 0 or 1.

Let D be the minimal integer j > 1 for which the j^{th} coefficient of the series |^{\frac{∏_{i=1}^{r}(1−t^{d_{i}})}{(1−t)^{n}}}| is ≤ 1. Then by the experimental observations, the algorithm usually terminates at degree D.

Another – related – application is the analysis of appropriate variants of the F_{5} algorithm ([Fau02]) for the computation of Gröbner bases. If a sequence is regular up to a particular degree then no reduction to zero occurs in the algorithm up to that degree. (This statement does however not hold for the original algorithm; see Remark 8 for further information.)

3 Terminology and notations

We set ℕ := {1, 2, 3, …} and ℕ_{0} := {0, 1, 2, 3, …}. As already stated, by an S-module we mean a graded S-module with grading in ℤ. For a module M and d ∈ ℤ, we define M(d) by M(d)_{i} := M_{d+i}. By a homomorphism of S-modules φ : M ⟶ N we mean a homogeneous homomorphism, that is, a homomorphism from M to N as plain modules which preserves the grading but which might change the degrees by a shift. By a free S-module we mean a graded module which has a basis of homogeneous elements.

By a complex of S-modules, we mean a complex of S-modules of the form ⋯ ⟶ C_{1} ⟶ C_{0}. We denote such a complex by C_{•}, and we denote the i^{th} differential of C_{•} by δ_{i}^{C}.

We emphasize that C_{•}(d) is the complex obtained from C_{•} by degree shift as defined above, that is, (C_{•}(d))_{i} = C_{i}(d). We do not fix a notation for “left-right shifts”.

Let now C_{•} be a complex of finitely generated free S-modules, where C_{i} = ⨁_{j} S(−j)^{γ_{i,j}}. Then we define the Hilbert-Poincaré series of C_{•} as P_{C_{•}} := ∑_{i,j} γ_{i,j}s^{i}t^{j}; cf. [PR09]. The Hilbert-Poincaré series of some finitely generated S-module M, P_{M}, is then the Hilbert-Poincaré series of some minimal free resolution of M.

We denote free resolutions of modules by F_{•} and Koszul complexes of sequences of homogeneous polynomials f_{1}, …, f_{r} by K(f_{1}, …, f_{r})_{•} or simply by K_{•}. The j^{th} basis element of S^{r} is denoted by \underline{e}_{j}. Moreover, for \underline{j} = (j_{1}, …, j_{i}) ∈ \{1, …, r\}^{i}, we set \underline{e}\underline{j} := \underline{e}_{j_{1}} ∧ ⋯ ∧ \underline{e}_{j_{i}} ∈ ⋀^{i} S^{r}. We have K_{i} = ⋀^{i} K_{1}, thus the elements \underline{e}\underline{j} with strictly increasing \underline{j} = (j_{1}, …, j_{r}) ∈ {1, …, r}^{i} form a basis of K_{i}.

Finally, we mention that besides using the letter k to denote the field already introduced we sometimes also use it to denote an integer.

4 Characterization with Hilbert series

We are going to compare Laurent series with integer coefficients. We have the lexicographic order ≥^{l} on the ring of Laurent series, and as usual, we denote the corresponding strict order by >^{l}. Moreover, for two such series a, b we write a ≥ b if a is coefficient-wise greater-than-or-equal to b.

As above, let M be a non-trivial finitely generated S-module.

Proposition 1

a) Let f be a homogeneous polynomial of positive degree d. Then H_{M/fM} ≥ (1 − t^{d})H_{M} with equality if and only if f is regular on M.

b) Let f_{1}, …, f_{r} be homogeneous polynomials of positive degrees d_{1}, …, d_{r}. Then H_{M/(f_{1},...,f_{r})M} ≥^{l} ∏_{i=1}^{r}(1 − t^{d_{i}}) · H_{M}. Equality holds if and only if f_{1}, …, f_{r} is regular on M. Moreover, H_{M/(f_{1},...,f_{r})M} ≥^{l} | ∏_{i=1}^{r}(1 − t^{d_{i}}) · H_{M}|.

c) Additionally to b), let D ∈ ℤ. Then H_{M/(f_{1},...,f_{r})M} ≡ ∏_{i=1}^{r}(1 − t^{d_{i}}) · H_{M} mod t^{D+1} if and only if the sequence f_{1}, …, f_{r} is regular up to degree D on M.

d) For M = S, suppose that S/(f_{1}, …, f_{r}) is Artinian. Then H_{S/(f_{1},...,f_{r})} = |^{\frac{∏_{i=1}^{r}(1−t^{d_{i}})}{(1−t)^{n}}}| if and only if f_{1}, …, f_{r} is regular up to the Castelnuovo-Mumford regularity of S/(f_{1}, …, f_{r}).

Note here that in the series on the right-hand sides of a), c) and the first part of b) there might be negative coefficients. This does not matter – the statements are still correct.

Statement a) of the proposition is immediate and statement d) is an immediate consequence of statement c).

For b) and c), we need the following lemma.

Lemma 1 Let a, b be two Laurent series with integer coefficients and a >^{l} b, and let d ∈ ℕ. Then (1 − t^{d})a >^{l} (1 − t^{d})b, and the minimal index at which the sequences a and b are different is equal to the minimal index at which the sequences (1 − t^{d})a and (1 − t^{d})b are different.

Proof. Let j be minimal with a_{j} ≠ b_{j}. Then for i < j, the i^{th} coefficient of (1 − t^{d})a, a_{i} − a_{i−d}, is equal to the i^{th} coefficient of (1 − t^{d})b, b_{i} − b_{i−d}.

We have a_{j} > b_{j} by assumption. Thus the j^{th} coefficient of (1 − t^{d})a, a_{j} − a_{j−d}, is larger than the j^{th} coefficient of (1 − t^{d})b_{j}, b_{j} − b_{j−d}. □

We fix the following definition.

Definition 3 For a Laurent series a with integer coefficients and D ∈ ℤ we define [a]_{≤D} as the unique Laurent polynomial which is congruent to a modulo t^{D+1}.

We now prove statement b). If the sequence is regular, we clearly have H_{M/(f_{1},...,f_{r})M} = ∏_{i=1}^{r}(1−t^{d_{i}})H_{M}. So, let us assume that the sequence is not regular. Let q be minimal such that f_{q} is not regular on M/(f_{1}, …, f_{q−1})M. Then H_{M/(f_{1},...,f_{q−1})M} = ∏_{i=1}^{q−1}(1−t^{d_{i}})·H_{M}. By a), we have H_{M/(f_{1},...,f_{q})M} >^{l} ∏_{i=1}^{q}(1 − t^{d_{i}})H_{M}. By repeatedly applying a) and the lemma it follows that

H_{M/(f_{1},...,f_{r})M} ≥^{l} ∏_{i=q+1}^{r}(1 − t^{d_{i}})H_{M/(f_{1},...,f_{q})M} >^{l} ∏_{i=1}^{r}(1 − t^{d_{i}})H_{M} .

The last statement in b) is trivial if ∏_{i=1}^{r}(1 − t^{d_{i}})H_{M} = | ∏_{i=1}^{r}(1 − t^{d_{i}})H_{M}|. So let us assume that this is not the case and let D := deg(| ∏_{i=1}^{r}(1 − t^{d_{i}})H_{M}|). Now H_{M/(f_{1},...,f_{r})M} ≥ [H_{M/(f_{1},...,f_{r})M}]_{≤D} ≥^{l} [∏_{i=1}^{r}(1 − t^{d_{i}})H_{M}]_{≤D} = | ∏_{i=1}^{r}(1 − t^{d_{i}})H_{M}|.

The proof of c) is analogous to the one of b): By the lemma we have for two Laurent series with integer coefficients a, b with [a]_{D} >^{l} [b]_{D} and some D ∈ ℤ that [(1 − t^{d})a]_{D} >^{l} [(1 − t^{d})b]_{D}. The statement now follows just as statement b).

Remark 1 For a, b ∈ ℤ[t] and n ∈ ℕ the implication a ≤ b ⟶ (1 − t^{n})a ≤ (1 − t^{n})b does of course not hold in general. The converse implication, that is a ≤ b ⟶ \frac{1}{1−t^{n}} a ≤ \frac{1}{1−t^{n}} b does however hold. (Just note that \frac{1}{1−t^{n}} = ∑_{i=0}^{∞} t^{in}.)

With this observation one sees easily that in the context of b), one has H_{M} ≤ \frac{1}{∏_{i=1}^{r}(1−t^{d_{i}})}H_{M/(f_{1},...,f_{r})M}. Again equality holds if and only if f_{1}, …, f_{r} is a regular sequence on M.

This statement was proven by R. Stanley in [Sta78].

Remark 2 For M = S, b) says in particular that H_{S/(f_{1},...,f_{r})} ≥^{l}|^{\frac{∏_{i=1}^{r}(1−t^{d_{i}})}{(1−t)^{n}}}|. This is one of the key statements in [Frö85].

The characterization in d) is claimed in [BFSY05] and in [Bar04]. However, in both works, the arguments for the more difficult “reverse” direction are incorrect. In fact, in [BFSY05] the argument for the difficult direction is essentially a repetition of the correct proof of the easy direction.

In [Bar04], first there is an argument for r ≤ n which is the same as the one in [BFSY05] and which is incorrect (see “Pour la réciproque ...” in the proof of Proposition 1.7.4).

Later, in Corollaire 3.3.4, there is also an argument for arbitrary r, which is however also false: The argument relies on the study of certain matrices M_{d,r} for d ∈ ℕ_{0} up to the Castelnuovo-Mumford regularity of S/(f_{1}, …, f_{r}). The mistake is that it is asserted without proof that for any such d the number of rows of such a matrix is equal to the d^{th} coefficient of ^{\frac{∏_{i=1}^{r}(1−t^{d_{i}})}{(1−t)^{n}}}. No argument is given why this statement should hold under the given conditions on f_{1}, …, f_{r}, and clearly it does not hold if f_{1}, …, f_{r} is is arbitrary (under the condition that S/(f_{1}, …, f_{r}) be Artinian) rather than regular up to the Castelnuovo-Mumford regularity of S/(f_{1}, …, f_{r}).

Remark 3 It immediately follows from the proposition that f_{1}, …, f_{r} is regular up to degree D on M if and only if every permutation is.

For d ∈ ℕ, let e_{d} be the number of f_{i} with deg(f_{i}) = d, and let N := (f_{1}, …, f_{r})M. Then ∏_{i=1}^{r}(1 − t^{d_{i}}) · H_{M} = ∏_{d∈ℕ}(1 − t^{d})^{e_{d}} · H_{M}. Therefore f_{1}, …, f_{r} is regular on M if and only if H_{N} = (1 − ∏_{d∈ℕ}(1 − t^{d})^{e_{d}}) · H_{M}, and f_{1}, …, f_{r} is regular up to degree D on M if and only if H_{N} ≡ (1 − ∏_{d∈ℕ}(1 − t^{d})^{e_{d}}) · H_{M} mod t^{D+1}.

Remark 4 Let R be a local Noetherian domain with maximal ideal 𝔪 and N a finitely generated R-module. Let K := Quot(R), k := R/𝔪, N_{η} := N ⊗_{R}K and N_{𝔪} := N ⊗_{R}k. By Nakayama, we have dim_{K}(N_{η}) ≤ dim_{k}(N_{𝔪}).

Let now M be a finitely generated R[x_{1}, …, x_{n}]-module, and let M_{η} := M ⊗_{R} K and M_{𝔪} := M ⊗_{R} k; these are K[x_{1}, …, x_{n}]- respectively k[x_{1}, …, x_{n}]-modules. Now for every integer j, M_{j} is a finitely generated R-module with generic fiber (M_{η})_{j} and special fiber (M_{η})_{j}. Therefore, we have the coefficient-wise inequality H_{M_{η}} ≤ H_{M_{𝔪}}.

As a special case, we can consider a finitely generated free R[x_{1}, …, x_{n}]- module M and a sequence of homogeneous polynomials f_{1}, …, f_{r} ∈ R[x_{1}, …, x_{n}]. For f ∈ R[x_{1}, …, x_{n}], let \overline{f} ∈ k[x_{1}, …, x_{n}] be the reduction of f modulo 𝔪. We then have H_{M_{η}} = H_{M_{𝔪}} and H_{M_{η}/(f_{1},...,f_{r})M_{η}} ≤ H_{M_{𝔪}/(\overline{f}_{1},...,\overline{f}_{r})M_{𝔪}}.

This implies in particular that in order to prove that a generic sequence with degrees d_{1}, …, d_{r} in characteristic 0 is regular up to a particular bound, one only has to establish that there exists one such sequence over some field. Fröberg indeed originally stated his conjecture as an existence statement.

5 Characterization with first syzygies

Let M still be a non-trivial finitely generated S-module. In this section we characterize regularity up to some degree on M in terms of first syzygies.

Notation 1 For D ∈ ℤ we set M_{≤D} := ⨁_{j≤D} M_{j}.

The following proposition is a variant of a well-known statement on the vanishing of cohomology groups of Koszul complexes. The subsequent theorem is then a variant of a characterization of regularity in terms of first syzygies; cf. Theorem 17.6 in [Eis95]. The proof of part a) of the proposition is due to P. Roberts (see also Remark 5 below).

Proposition 2 Let f_{1}, …, f_{r} be a sequence of homogeneous polynomials of positive degrees, and let D ∈ ℕ and i ∈ ℕ with H_{i}(M ⊗ K(f_{1}, …, f_{r})_{•})_{≤D} = 0.

a) For q < r, H_{i}(M ⊗ K(f_{1}, …, f_{q})_{•})_{≤D} = 0.

b) Let m := min{deg(f_{ℓ}) | ℓ = 1, …, r}. Then for k ∈ ℕ, H_{i+k}(M ⊗ K(f_{1}, …, f_{r})_{•})_{≤D+km} = 0.

Proof. a) By induction, we only have to show the statement for q = r − 1.

Let d_{r} := deg(f_{r}). The complex M ⊗ K(f_{1}, …, f_{r})_{•} is the mapping cone

of K(M ⊗ f_{1}, …, f_{r−1})_{•}(−d_{r}) ⟶^{f_{r}·} M ⊗ K(f_{1}, …, f_{r−1})_{•}. The short exact

sequence for the mapping cone induces a long exact sequence on Koszul homology; cf. Sections 17.3 and A3.12 of [Eis95]. We consider the part

\begin{matrix}H_{i}(M ⊗ K(f_{1}, …, f_{r−1})_{•}(−d_{r})) ⟶^{f_{r}·} H_{i}(M ⊗ K(f_{1}, …, f_{r−1})_{•}) \\ ⟶ H_{i}(M ⊗ K(f_{1}, …, f_{r})_{•}) \end{matrix}

of this sequence. Let us assume that H_{i}(M ⊗K(f_{1}, …, f_{r−1})_{•}) ≠ 0. Let j be minimal with H_{i}(M ⊗ K(f_{1}, …, f_{r−1})_{•})_{j} ≠ 0. Then H_{i}(M ⊗ K(f_{1}, …, f_{r−1})_{•}(−d_{r}))_{j} = H_{i}(M ⊗ K(f_{1}, …, f_{r−1})_{•})_{j−d_{r}} = 0 and therefore H_{i}(M ⊗ K(f_{1}, …, f_{r})_{•})_{j} ≠ 0. With the assumption it follows that j > D.

b) We only have to show the statement for k = 1, that is, we have to show that under the given condition, H_{i+1}(M ⊗ K(f_{1}, …, f_{r})_{•})_{≤D+m} = 0.

We show the statement by induction on r, using r = 0 as induction base. Like this, the induction base is trivial.

On the induction step: Let f_{1}, …, f_{r} with r ≥ 1 and D, i be as in the proposition, that is, H_{i}(M ⊗ K(f_{1}, …, f_{r})_{•})_{≤D} = 0. We now consider the following part of the long exact sequence induced by the short exact sequence for the mapping cone:

\begin{matrix}H_{i+1}(M ⊗ K(f_{1}, …, f_{r−1})_{•}) ⟶ H_{i+1}(M ⊗ K(f_{1}, …, f_{r})_{•}) \\ ⟶ H_{i}(M ⊗ K(f_{1}, …, f_{r−1})_{•}(−d_{r})) \end{matrix}

We have H_{i}(M ⊗ K(f_{1}, …, f_{r−1})_{•})_{≤D} = 0 by a) and therefore H_{i+1}(M ⊗ K(f_{1}, …, f_{r−1})_{•})_{≤D+m} = 0 by induction hypothesis. Moreover, H_{i}(M⊗K(f_{1}, …, f_{r−1})_{•}(−d_{r}))_{≤D+m} = H_{i}(M⊗K(f_{1}, …, f_{r−1})_{•})_{≤D+m−d_{r}} = 0 as m ≤ d_{r}. We conclude that H_{i+1}(M ⊗ K(f_{1}, …, f_{r})_{•})_{≤D+m} = 0. □

Theorem 1 Let M be a finitely generated non-trivial S-module. Let f_{1}, …, f_{r} be a sequence of homogeneous polynomials of positive degrees d_{1}, …, d_{r} and let D be a natural number.

The following statements are equivalent:

a) The sequence f_{1}, …, f_{r} is regular up to degree D.

b) H_{M/(f_{1},...,f_{r})M} ≡ ∏_{i=1}^{r}(1 − t^{d_{i}}) · H_{M} mod t^{D+1}

c) H_{1}(M ⊗ K(f_{1}, …, f_{r})_{•})_{≤D} = 0.

Proof. We have already shown in the previous section that statements a) and b) are equivalent.

On implication a) ⟶ c). We again use induction on r.

The induction base is r = 1. So let f_{1} be regular up to degree D on M. The complex M ⊗ K(f_{1})_{•} is ⋯ ⟶ 0 ⟶ M ⟶ M. By assumption, the complex 0 ⟶ M_{≤D} ⟶ M_{≤D} is exact and thus H_{1}(M ⊗ K(f_{1})_{•})_{≤D} = 0.

On the induction step. Let a) be satisfied. We consider the exact sequence

\begin{matrix}H_{1}(M ⊗ K(f_{1}, …, f_{r−1})_{•}) ⟶ H_{1}(M ⊗ K(f_{1}, …, f_{r})_{•}) ⟶ \\ (M/(f_{1}, …, f_{r−1})M)(−d_{r}) ⟶^{f_{r}·} M/(f_{1}, …, f_{r−1})M . \end{matrix}

By induction hypothesis we have H_{1}(M ⊗ K(f_{1}, …, f_{r−1})_{•})_{≤D} = 0. Moreover, by assumption, the kernel of (M/(f_{1}, …, f_{r−1})M)(−d_{r})_{≤D} ⟶^{f_{r}·} (M/(f_{1}, …, f_{r−1})M)_{≤D} is trivial. We conclude that H_{1}(M ⊗ K(f_{1}, …, f_{r})_{•})_{≤D} = 0.

On implication c) ⟶ a). Let c) be satisfied. Let q ∈ ℕ with q ≤ r. By Proposition 2 a) we have H_{1}(M ⊗ K(f_{1}, …, f_{q})_{•})_{≤D} = 0. By the exact sequence

\begin{matrix}H_{1}(M ⊗ K(f_{1}, …, f_{q})_{•}) ⟶ (M/(f_{1}, …, f_{q−1})M)(−d_{q−1}) \\ ⟶^{f_{q}·} M/(f_{1}, …, f_{q−1})M \end{matrix}

we conclude that the kernel of the map (M/(f_{1}, …, f_{q−1})M)(−d_{r})_{≤D} ⟶^{f_{q}·} (M/(f_{1}, …, f_{q−1})M)_{≤D} is trivial. □

Remark 5 In the last paragraph of Theorem 4.4 of [PR09] it is claimed, in our terminology:

Let some natural number D be given. Let us assume that all first syzygies of f_{1}, …, f_{r} of degree ≤ D are Koszul syzygies. Then the sequence f_{1}, …, f_{r} is regular up to degree D.

Or with other words, it is claimed that implication c) ⟶ a) of Theorem 1 holds for M = S. However, there is a gap in the argument because Proposition 2 a) is not proven but implicitly assumed to hold. This gap was noticed by the author of this article and then closed by P. Roberts; cf. [PR12].

6 Characterization with free resolutions

We now study sequences which are regular up to some degree on S itself via free resolutions and Betti numbers.

Notation 2 Following [PR09], we denote the submodule of M generated by M_{≤D} by M_{(D)}.

Remark 6 Let M and D be as above. Then M_{≤D} is a vector subspace of M and a quotient of M as an S-module. For i > D we have (M_{(D)})_{i} = (𝔪M_{(D)})_{i} = 𝔪(M_{(D)})_{i−1}, and we have (M/𝔪M)_{≤D} ≃ M_{≤D}/𝔪M_{≤D} ≃ M_{(D)}/𝔪 M_{(D)} as S-modules.

The following lemma holds by Nakayama.

Lemma 2 Let M be a finitely generated S-module and A be a set of homogeneous elements of M_{≤D}. Then the following statements are equivalent:

a) A generates M_{≤D} as an S-module.

b) A generates M_{(D)} as an S-module.

c) A defines a generating set of the vector space (M/𝔪M)_{≤D} ≃ M_{≤D}/𝔪M_{≤D} ≃ M_{(D)}/𝔪M_{(D)}.

Furthermore, the following statements are equivalent:

a) A is a minimal generating set of M_{≤D} as an S-module.

b) A is a minimal generating set of M_{(D)} as an S-module.

c) A defines a basis of (M/𝔪M)_{≤D} ≃ M_{≤D}/𝔪M_{≤D} ≃ M_{(D)}/𝔪M_{(D)}.

The following lemma is easy.

Lemma 3 Let φ : M ⟶ N be a degree preserving homomorphism of Smodules, and let D ∈ ℤ. Then we have φ(M_{≤D}) = φ(M)_{≤D}, φ(M_{(D)}) = φ(M)_{(D)} and φ(M_{≤D}) ⊆ N_{≤D}, φ(M_{(D)}) ⊆ N_{(D)}. Moreover, φ(M_{(D)}) ⊆ 𝔪N if and only if φ(M_{(d)}) ⊆ N_{(d−1)} for all d ≤ D. In particular φ(M) ⊆ 𝔪N if and only if φ(M_{(d)}) ⊆ N_{(d−1)} for all d ∈ ℤ.

Let C_{•} : ⋯ ⟶ C_{1} ⟶ C_{0} be a complex and D ∈ ℤ such that for each i, δ_{i}^{C}((C_{i})_{(D+i)}) ⊆ (C_{i−1})_{(D+i−1)}. We then have the restricted complex ⋯ ⟶ (C_{i})_{(D+i)} ⟶ (C_{i−1})_{(D+i−1)} ⟶ · · ·. The converse holds too.

Again following [PR09] we define:

Notation 3 We denote the complex just described by C_{•}^{(D)}. Therefore, ((C_{•})^{(D)})_{i} = (C_{i})_{(D+i)}.

Example 1 Let f_{1}, …, f_{r} be a sequence of homogeneous polynomials of positive degrees, and let K_{•} = K(f_{1}, …, f_{r})_{•} be the Koszul complex of the sequence. Then δ_{•}^{K}(K_{•}) ⊆ (f_{1}, …, f_{r}) K_{•} ⊆ 𝔪 K_{•}. Therefore, for all D ∈ ℤ we have the complex K_{•}^{(D)}.

The following lemma characterizes the existence of C_{•}^{(D)} for free resolutions and more general complexes. The lemma generalizes an obvious variant of Lemma 19.4 in [Eis95] for S-modules.

Lemma 4 Let C_{•} be a complex of S-modules and D ∈ ℤ with H_{i}(C_{•})_{≤D+i+1} = 0 for all i ∈ ℕ. Then the following statements are equivalent.

a) For all i ∈ ℕ, δ_{i}^{C}(C_{i})_{≤D+i} ⊆ 𝔪 C_{i−1}.

b) For all d ∈ ℤ with d ≤ D, the complex C_{•}^{(d)} exists.

c) For all i ∈ ℕ, the differential map induces an isomorphism

(C_{i}/𝔪 C_{i})_{≤D+i+1} ⟶ (δ_{i}^{C}(C_{i})/𝔪 δ_{i}^{C}(C_{i}))_{≤D+i+1}

and we have an induced isomorphism

(C_{0}/𝔪 C_{0})_{≤D+1} ⟶ (H_{0}(C_{•})/𝔪H_{0}(C_{•}))_{≤D+1} .

If the modules C_{i} are finitely generated, the statements are also equivalent to:

d) For all i ∈ ℕ,

dim_{k}((C_{i}/𝔪 C_{i})_{≤D+i+1}) = dim_{k}((δ_{i}^{C}(C_{i})/𝔪 ker(δ_{i}^{C}(C_{i})))_{≤D+i+1})

and

dim_{k}((C_{0}/𝔪 C_{0})_{≤D+1}) = dim_{k}((H_{0}(C_{•})/𝔪H_{0}(C_{•}))_{≤D+1}) .

e) For all i ∈ ℕ, any (or some) homogeneous minimal generating system of (C_{i})_{(D+i+1)} is mapped to a minimal generating system of δ_{i}^{C}(C_{i})_{(D+i+1)} and any (or some) minimal homogeneous generating system of (C_{0})_{(D+1)} is mapped to a minimal generating system of H_{0}(C_{•})_{(D+1)}.

Proof. Statements a) and b) are clearly equivalent.

We have

δ_{i}^{C}(C_{i})_{≤D+i+1} ≃ (C_{i}/ ker(δ_{i}^{C}))_{≤D+i+1} = (C_{i}/δ_{i+1}^{C}(C_{i+1}))_{≤D+i+1}

as H_{i}(C_{•})_{≤D+i+1} ≤ 0. The statement in c) can thus be reformulated as follows: For all i ∈ ℕ_{0}, the induced maps

(C_{i}/𝔪C_{i})_{≤D+i+1} ⟶ (C_{i}/δ_{i+1}^{C}(C_{i+1})/(𝔪 · C_{i}/δ_{i+1}^{C}(C_{i+1})))_{≤D+i+1}

are isomorphisms. This means that the maps

(C_{i}/𝔪C_{i})_{≤D+i+1} ⟶ (C_{i}/(𝔪 C_{i} + δ_{i+1}^{C}(C_{i+1})))_{≤D+i+1}

are isomorphisms. This is equivalent to (δ_{i+1}^{C}(C_{i+1}))_{≤D+i+1} ⊆ (𝔪 C_{i})_{≤D+i+1}, that is, (δ_{i+1}^{C}(C_{i+1})_{≤D+i+1}) ⊆ 𝔪 C_{i} for all i ∈ ℕ_{0}, which is the statement in a).

The equivalence between statement c) and statement d) is obvious. The equivalence with the last statement follows from Lemma 2. □

Lemma 5 Let M be an S-module, C_{•} a complex of finitely generated free S-modules, φ : C_{0} ⟶ M and D ∈ ℕ such that

- the complex C_{•} and the integer D satisfy the conditions of the previous lemma,

- the complex C_{•}^{(D)} is equal to C_{•},

- φ induces an isomorphism H_{0}(C_{•})_{≤D} ⟶ M_{≤D},

- ker(φ)_{≤D+1} = δ_{1}^{C}(C_{1})_{≤D+1}.

Then there exists a minimal free resolution F_{•} of M and an inclusion of complexes C_{•} ↪ F_{•} such that the diagram

\xymatrix{F_{0} \ar[dr] \\ C_{0} \ar@{^{(}->}[u] \ar[r] & M}

is commutative and C_{•}^{(D)} = F_{•}^{(D)} holds.

Proof. We show by induction on i ∈ ℕ the following statement: For j ≤ i, there exist free modules F_{j}, inclusions C_{j} ↪ F_{j} and maps δ_{j}^{F} : F_{j} ⟶ F_{j−1}, F_{0} ⟶ M such that we have a complex

⟶ C_{i+2} ⟶^{δ_{i+2}^{C}} C_{i+1} ⟶^{δ_{i+1}^{C}} F_{i} ⟶^{δ_{i}^{F}} F_{i−1} ⟶^{δ_{i−1}^{F}} F_{i−2} ⟶ ⋯ ⟶ F_{0}

with

- H_{0}(F_{•}) ≃ M, where a basis of F_{0} generates M minimally,

- the inclusions C_{j} ⟶ F_{j} define an inclusion from the complex C_{•} to the complex F_{•} which is compatible with the maps to M,

- C_{j} = (C_{j})_{(D+j)} = (F_{j})_{(D+j)} for all i ≤ j,

- for 0 < j ≤ i, the image of a basis of F_{j} in F_{j−1} generates δ_{j}^{F} (F_{j}) minimally.

Moreover, in the proof by induction, we do not change the F_{j}, the inclusions C_{j} ⟶ F_{j}, the differential maps between the F_{j} and the map F_{0} ⟶ M which have already been defined in previous steps. The desired free resolution of M is then F_{•}.

The induction base is i = 1. We choose a homogeneous basis of C_{0} as S-module. As by assumption (C_{0})_{(D)} = C_{0}, the degrees of the basis elements are at most D. Under map C_{0} ⟶ M the basis is mapped to a homogeneous minimal generating system of the S-module M_{(D)}; see also the previous lemma. We extend this minimal generating system of M_{(D)} to a minimal homogeneous generating system of M. We consider the free module on this minimal homogeneous generating system of M and call it F_{0}. Like this, the map φ : C_{0} ⟶ M extends to a surjective map F_{0} ⟶ M. We clearly have ker(φ)_{≤D} = ker(F_{0} → M)_{≤D}.

We claim that ker(φ)_{≤D+1} = ker(F_{0} → M)_{≤D+1}. Let M_{D+1} = (M_{(D)})_{D+1} ⊕ k^{r}. Then M_{D+1} = φ(C_{0})_{D+1} ⊕ k^{r}, (F_{0})_{(D+1)} = C_{0} ⊕ S(−(D + 1))^{r}, (F_{0})_{D+1} = (C_{0})_{D+1} ⊕ k^{r}, and the map (F_{0})_{D+1} ⟶ M ⊕k^{r} is given by φ_{|(C_{0})_{D+1}} ×id_{k^{r}}. It follows that ker(φ)_{D+1} = ker(F_{0} → M)_{D+1}.

We now have ker(F_{0} → M)_{≤D+1} = ker(φ)_{≤D+1} = δ_{1}^{C}(C_{1})_{≤D+1} (the second equality by the assumptions). Therefore ker(F_{0} → M)_{(D+1)} = ker(φ)_{(D+1)} = δ_{1}^{C}(C_{1})_{(D+1)} = δ_{1}^{C}((C_{1})_{(D+1)}) = δ_{1}^{C}(C_{1}) and the map δ_{1}^{C} : C_{1} ⟶ C_{0} defines a minimal homogeneous generating system of this module. We extend this minimal generating system to a minimal homogeneous generating system of ker(F_{0} → M). This defines F_{1} and the desired map δ_{1}^{F} : F_{1} ⟶ F_{0}. Clearly, (F_{1})_{(D+1)} = (C_{1})_{(D+1)} = C_{1}.

On the induction step: Because of (F_{i})_{≤D+i} = (C_{i})_{≤D+i} and because of the definition of the differential maps, we have ker(δ_{i}^{F})_{≤D+i} = ker(δ_{i}^{C})_{≤D+i}.

We also have ker(δ_{i}^{F})_{≤D+i+1} = ker(δ_{i}^{C})_{≤D+i+1}. The proof is just as the proof for ker(φ)_{D+1} = ker(F_{0} → M)_{D+1}.

It follows that ker(δ_{i}^{F})_{≤D+i+1} = ker(δ_{i}^{C})_{≤D+i+1} = δ_{i+1}^{C}(C_{i+1})_{≤D+i+1} and thus ker(δ_{i}^{F})_{(D+i+1)} = ker(δ_{i}^{C})_{(D+i+1)} = δ_{i+1}^{C}(C_{i+1})_{(D+i+1)} = δ_{i+1}^{C}(C_{i+1}).

We choose a homogeneous basis of C_{i+1} as S-module. This defines a minimal generating system of δ_{i+1}^{C}(C_{i+1}), which we extend to a minimal homogeneous generating system of ker(δ_{i}^{F}). We define now F_{i+1} as the free module on this homogeneous generating system. We obtain an inclusion C_{i+1} ↪ F_{i+1} and a differential map F_{i+1} ⟶ F_{i}. We have (F_{i+1})_{(D+i+1)} = (C_{i+1})_{(D+i+1)}, and the new differential map agrees with the old one on this space. □

We now study the Koszul complex of a system of homogeneous polynomials. Let us first mention the following statement which seems to be well known to the experts. As we cannot find a proof in the literature, we state it here with proof.

Lemma 6 Let f_{1}, …, f_{r} be a sequence of homogeneous polynomials of degrees d_{1}, …, d_{r}. Let K_{•} be the Koszul complex of f_{1}, …, d_{r}. Then we have P_{K_{•}} = ∏_{i=1}^{r}(1 + st^{d_{i}}).

Proof. We have

K_{i} = ⋀^{i} K_{1} = ⋀^{i} ⨁_{k=1}^{r} S(−d_{k}) =

⨁_{\underline{a}∈\{1,...,r\}^{i} with a_{1}<···<a_{i}} S(−(d_{a_{1}} + ⋯ + d_{a_{i}})) = ⨁_{\underline{e}∈\{0,1\}^{r} with |\underline{e}|=i} S(−\underline{e}^{t}\underline{d}) .

The (i, j)^{th} coefficient of P_{K_{•}} is therefore equal to #\{\underline{e} ∈ ℕ_{0}^{r} | |\underline{e}| = i, \underline{e}^{t}\underline{d} = j\}. This is also the (i, j)^{th}-coefficient of ∏_{ℓ=1}^{r}(1 + st^{d_{ℓ}}). □

The following lemmata are easy generalizations of statements proven for Theorem 4.4 in [PR09].

Lemma 7 Let R be any commutative ring (with unity), and let f_{1}, …, f_{r} be a system of ring elements. Let us assume that the system f_{1}, …, f_{r} generates the ideal (f_{1}, …, f_{r}) minimally, that is, for no q = 1, …, r, f_{q} is

contained in (f_{1}, …, f^{∨}_{q}, …, f_{r}). Let K_{•} := K(f_{1}, …, f_{r})_{•}. Then for each i, the image of δ_{i}^{K} in K_{i−1} is minimally generated by the images of elements \underline{e}\underline{j} with |j| = i and strictly increasing \underline{j} = (j_{1}, …, j_{i}) ∈ \{1, …, r\}^{i}.

Proof. Let us assume that the statement is wrong for some i ∈ ℕ. Let us wlog. assume that the image of \underline{e}_{(1,2,...,i)} is an S-linear combination of the images of the other elements:

δ_{i}^{K}(\underline{e}_{(1,2,...,i)}) = ∑_{\underline{j}≠(1,2,...,i)} g\underline{j}δ_{i}^{K}(\underline{e}\underline{j})

with g\underline{j} ∈ S, where the sum is over strictly increasing \underline{j}. We now consider the coefficient of \underline{e}_{(1,2,...,i−1)}. We have:

f_{i} = ∑_{k=i+1}^{r} ±g_{(1,2,...,i−1,k)}f_{k} ,

a contradiction. □

Lemma 8 Let f_{1}, …, f_{r} be a system of homogeneous polynomials which generates the ideal I := (f_{1}, …, f_{r}) minimally. Let K_{•} be the Koszul complex of the sequence, let F_{•} be a minimal free resolution of S/I with F_{i} = ⨁_{j} S(−j)^{β_{i,j}}. Let i, D ∈ ℕ. Then the following statements are equivalent:

a) (K_{i+1})_{(D)} ≈ (F_{i+1})_{(D)}.

b) For j ≤ D, β_{i+1,j} is the coefficient of s^{i+1}t^{j} in ∏_{k=1}^{r}(1 + st^{deg(f_{k})}).

c) H_{i}(K_{•})_{≤D} = 0.

Proof. The first two statements are clearly equivalent.

For the equivalence between these statements and the third statement, we need the following easy fact (cf. Lemma 4.3 in [PR09]).

Let M ⊆ N be finitely generated S-modules such that minimal generating sets for M and for N have the same number of elements for each degree. Then M = N.

The third statement is equivalent to ker(δ_{i}^{K})_{≤D} = δ_{i+1}^{K}(K_{i+1})_{≤D} which is equivalent to: The system consisting of \underline{e}\underline{j} with |j| = i, \underline{j}^{t}\underline{d} ≤ D and strictly increasing \underline{j} generates ker(δ_{i}^{K})_{(D)}. By the previous lemmata and the fact just mentioned, this is equivalent to the second statement. □

Finally, we obtain our main theorem on the characterization of bounded regularity on S itself.

Theorem 2 Let f_{1}, …, f_{r} be a sequence of homogeneous polynomials of positive degrees d_{1}, …, f_{r} and let D be a natural number. Let I := (f_{1}, …, f_{r}), and let K_{•} be the Koszul complex of the sequence. Furthermore, let F_{•} be a minimal free resolution of S/I, and let F_{i} = ⨁_{j} S(−j)^{β_{i,j}}.

The following statements are equivalent:

a) The sequence f_{1}, …, f_{r} is regular up to degree D. b) H_{S/I} ≡ ^{\frac{∏_{i=1}^{r}(1−t^{d_{i}})}{(1−t)^{n}}} mod t^{D+1}

c) H_{1}(K_{•})_{≤D} = 0.

d) For j ≤ D, β_{1,j} agrees with the coefficient of st^{j} in ∏_{i=1}^{r}(1 + st^{d_{i}}) and β_{2,j} agrees with the coefficient of s^{2}t^{j} in ∏_{i=1}^{r}(1 + st^{d_{i}}).

e) The subsystem of degree ≤ D of the system of polynomials f_{1}, …, f_{r} generates the ideal I_{(D)} minimally and the complexes K_{•}^{(D−2)} and F_{•}^{(D−2)} are isomorphic.

Proof. We already know by Theorem 1 that a), b) and c) are equivalent. We show that each of the statements d) or e) is equivalent to the first three statements.

On implication a) ⟶ d). Let a) be satisfied. Let wlog. f_{1}, …, f_{s} be the subsystem of polynomials of degree ≤ D of f_{1}, …, f_{r}. Now f_{1}, …, f_{s} generates the ideal (f_{1}, …, f_{s}) minimally and we have H_{1}(K(f_{1}, …, f_{s}))_{≤D} = 0. By Lemma 8 the second part of statement d) follows. The first part is exactly the statement that f_{1}, …, f_{s} generates the ideal (f_{1}, …, f_{s}) minimally.

On implication d) ⟶ a). Lemma 8 immediately gives the implication d) ⟶ c).

On implication a) ⟶ e). Let a) hold. The system of polynomials f_{i} of degree ≤ D generates I_{(D)} minimally. By c), H_{1}(K_{•})_{≤D} = 0 and therefore also H_{i}(K_{•})_{≤D+i−1} = 0 for all i ∈ ℕ by Proposition 2. With Lemma 5 applied to the complex K_{•}^{(D−2)} and the canonical map (K_{0})_{(D−2)} = S ⟶ S/I the result follows.

On implication e) ⟶ a). We obviously have the implication e) ⟶ d) and therefore also e) ⟶ a). □

Remark 7 Let f_{1}, …, f_{r} be a sequence of homogeneous polynomials of positive degrees d_{1}, …, d_{r}, where r ≥ n. Let again I := (f_{1}, …, f_{r}). Let us now assume that H_{S/I} = |^{\frac{∏_{i=1}^{r}(1−t^{d_{i}})}{(1−t)^{n}}}|. Let ρ := deg(|^{\frac{∏_{i=1}^{r}(1−t^{d_{i}})}{(1−t)^{n}}}|); this is the Castelnuovo-Mumford regularity of S/I. Then the sequence f_{1}, …, f_{r} is regular up to degree ρ. With the notations of the theorem we then have K_{•}^{(ρ−2)} ≈ F_{•}^{(ρ−2)}. If moreover the first non-positive coefficient of ^{\frac{∏_{i=1}^{r}(1−t^{d_{i}})}{(1−t)^{n}}}

is zero, the sequence is regular up to degree ρ+1, and then K_{•}^{(ρ−1)} ≈ F_{•}^{(ρ−1)}.

These statements are very closely related to Theorem 3.6 of [PR09]: In this theorem the same conclusions are stated under the assumption that the sequence is semi-regular.

We remark that there is the following mistake in the arguments for Theorem 3.6 in [PR09]: In the notation above, it is claimed that (Ĩ: f_{r})_{j} = Ĩ_{j} for all j ≤ D, where the correct statement is that (Ĩ : f_{r})_{j} = Ĩ_{j} for all j ≤ D − d_{r}. This mistake is implicitly corrected in the following. Moreover, the induction argument arguably is a bit unclear. With the obvious corrections, one obtains an alternative proof of implication a) ⟶ e); cf. [PR12].

Remark 8 Faugère’s F_{5} algorithm to compute Gröbner bases of homogeneous systems is presented in the short paper [Fau02]. In the algorithm, given f_{1}, …, f_{r}, Gröbner bases of f_{1}, …, f_{q} are computed for increasing q.^{1} For each q, the Gröbner bases are computed by increasing degree, using the already computed Gröbner basis of (f_{1}, …, f_{q−1}). We call this computation the new computation for f_{1}, …, f_{q}.

In the algorithm tuples (me_{q}, f) with a monomial m, a standard vector e_{q} and a homogeneous polynomial f are considered. Here me_{q} is the so-called signature of f.

Theorem 4 of [Fau02] states:

If any (me_{q}, f) is reduced to zero in a reduction step of the algorithm, then me_{q} is the head term of a syzygy of f_{1}, …, f_{r} which is not a Koszul syzygy.

This is not established. In fact, what is established is this:

Let us assume that a Gröbner base of (f_{1}, …, f_{q−1}) has already been computed and let us assume that currently the Gröbner base of (f_{1}, …, f_{q}) is being computed. Let us assume that there occurs a reduction to zero, (me_{q}, f) ⟶ 0. Then me_{q} is the head term of a syzygy of f_{1}, …, f_{q} which is not a Koszul syzygy of f_{1}, …, f_{q}.

It is however not clear whether such a syzygy is a Koszul syzygy of f_{1}, …, f_{r} of not. To study this question, one should consider the canonical map H_{1}(K(f_{1}, …, f_{q})_{•}) ⟶ H_{1}(K(f_{1}, …, f_{r})_{•}) which factors as H_{1}(K(f_{1}, …, f_{q})_{•}) ⟶ H_{1}(K(f_{1}, …, f_{q+1})_{•}) ⟶ ⋯ ⟶ H_{1}(K(f_{1}, …, f_{r−1})_{•}) ⟶ H_{1}(K(f_{1}, …, f_{r})_{•}). Let the degrees of the input polynomials be positive. (Otherwise {1} or the empty set is a Gröbner base.) By the proof of Proposition 2 we see: If H_{1}(K(f_{1}, …, f_{q})_{•}) is non-trivial and a is an element of minimal degree, then the image of a in H_{1}(K(f_{1}, …, f_{r})_{•}) is non-trivial. It is however not obvious what this means for a computation with the F_{5} algorithm.

What holds in any case is: If f_{1}, …, f_{r} is a regular sequence, then there is no reduction to zero. As mentioned in the introduction, one can change the algorithm in the following way: An outer loop is on the degree, and for each degree the computation is performed by increasing the system. Like this one can obtain an algorithm which computes a Gröbner basis up to degree D of some input system in such a way that no reduction to zero occurs for systems which are regular up to degree D.

1In the algorithm in [Fau02] the order of polynomials is reversed. For our modification, the order on S has to be reversed as well.

We make some more comments on the F_{5} algorithm as presented in [Fau02].

There are some gaps, misprints and mistakes in this paper. In particular, there is problem with the assurance of termination. This problem is addressed in [EGP11].

There is also room for improvement: One should be aware of the fact that the algorithm computes a Gröbner basis and not a reduced Gröbner basis. And even for computations up to degree D for systems which are regular up to degree D and with the interchanged order of the loops, the algorithm might compute polynomials which turn out to be redundant. An improvement of the algorithm which addresses these redundancies is [EP10]. A good overview over various algorithms similar to F_{5} is [Ede12].

Acknowledgments

I thank C. Eder, J.-C. Faugère, K. Pardue, P. Roberts, P.-J. Spaenlehauer and J. Stückrad for discussions.

References

[Bar04] M. Bardet. Étude des systémes algébriques surdéterminés. applications aux codes correcteurs et à la cryptographie. Thesis at Université Paris VI. Available under http://magali.bardet.free.fr/publications.html, 2004.

[BFS04] M. Bardet, J.-C. Faugère, and B. Salvy. On the complexity of gröbner basis computation of semi-regular overdetermined algebraic equations. Presented at International Conference on Polynomial System Solving, 2004.

[BFSY05] M. Bardet, J.-C. Faugère, B. Salvy, and B.-Y. Yang. Asymptotic Behaviour of the Degree of Regularity of Semi-Regular Polynomial Systems. Presented at MEGA 2005. Available under http://magali.bardet.free.fr/publications.html, 2005.

[Ede12] C. Eder. Signature-based algorithms to compute standard bases. PhD thesis, University of Kaiserslautern, 2012.

[EGP11] C. Eder, J. Gash, and J. Perry. Modifying Faugère’s F5 Algorithm to ensure termination. In ACM Communications in Computer Algebra, volume 45, pages 70–89. 2011.

[Eis95] D. Eisenbud. Commutative algebra with a view towards algebraic geometry. Springer, 1995.

[Eis05] D. Eisenbud. The Geometry of Syzygies. Springer, 2005.

[EP10] C. Eder and J. Perry. F5C: a variant of Faugère’s algorithm with reduced Gröbner bases. J. Symb. Computation, 45:1442–1458, 2010.

[Fau02] J.-C. Faugère. A new efficient algorithm for computing Gröbner bases without reduction to zero (F_{5}). In Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation, pages 75–83, New York, 2002. ACM.

[Frö85] R. Fröberg. An inequality for Hilbert series of graded algebras. Math. Scand., 56(2):117–144, 1985.

[Mat86] H. Matsumura. Commutative Ring Theory. Cambridge University Press, 1986.

[Par00] K. Pardue. Generic sequences of polynomials. Preprint, 2000.

[Par10] K. Pardue. Generic sequences of polynomials. J. Algebra, 324:579–590, 2010.

[PR09] K. Pardue and B. Richert. Syzygies of semi-regular sequences. Illinois J. Math., 53:349–364, 2009.

[PR12] K. Pardue and B. Richert. Errata on Syzygies of semi-regular sequences. Illinois J. Math., 56:1001–1003, 2012.

[Sta78] R. Stanley. Hilbert functions and graded algebras. Adv. Math., 28:57–83, 1978.

Claus Diem Mathematical Institute University of Leipzig 04103 Leipzig Germany diem@math.uni-leipzig.de