The syzygy theorem for Bézout rings

Maroua Gamanda^{*}, Henri Lombardi^{**}, Stefan Neuwirth^{**,1}, and Ihsen Yengui^{*,2}

*Département de mathématiques, Faculté des sciences de Sfax, Université de Sfax, 3000

         Sfax, Tunisia, marwa.gmenda@hotmail.com, ihsen.yengui@fss.rnu.tn.

** Laboratoire de mathématiques de Besançon, Université Bourgogne Franche-Comté,

       25030 Besançon Cedex, France, henri.lombardi@univ-fcomte.fr, stefan.
                            neuwirth@univ-fcomte.fr.

Abstract

We provide constructive versions of Hilbert’s syzygy theorem for ℤ and ℤ/Nℤ following Schreyer’s method. Moreover, we extend these results to arbitrary coherent strict Bézout rings with a divisibility test for the case of finitely generated modules whose module of leading terms is finitely generated.

MSC 2010: 13D02, 13P10, 13C10, 13P20, 14Q20 Keywords: Syzygy theorem, free resolution, monomial order, Schreyer’s monomial order, Schreyer’s syzygy algorithm, dynamical Gröbner basis, valuation ring, Gröbner ring, strict Bézout ring.

Contents

Introduction 2

1 Gröbner bases for modules over a discrete ring 2

The statement of Theorems 5.5, 5.8, 6.2 has been amended with respect to the published version, as well as the free resolution at the end of Example 6.7. The changes have been typeset in green.

1Supported by the French “Investissements d’avenir” program, project ISITE-BFC (contract ANR-15-IDEX-03).

2Supported by the John Templeton Foundation (ID 60842).

2 The algorithms 6 The context . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 The division algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 6 The S-polynomial algorithm . . . . . . . . . . . . . . . . . . . . . . 7 Buchberger’s algorithm . . . . . . . . . . . . . . . . . . . . . . . . 9 The syzygy algorithm for terms . . . . . . . . . . . . . . . . . . . . 10 Schreyer’s syzygy algorithm . . . . . . . . . . . . . . . . . . . . . . 10

3 The algorithms in the case of a valuation ring 11

4 Termination of Buchberger’s algorithm for a Bézout ring 13 When is a valuation ring a Gröbner ring? . . . . . . . . . . . . . . 17

5 The syzygy theorem and Schreyer’s algorithm for a valuation ring 19

6 The syzygy theorem and Schreyer’s algorithm for a Bézout ring 25 The case of the integers . . . . . . . . . . . . . . . . . . . . . . . . 27 The case of ℤ/Nℤ . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

References 30

Introduction

This paper is written in the framework of Bishop style constructive mathematics (see [2, 3, 11, 12]). It can be seen as a sequel to the papers [10, 16]. The main goal is to obtain constructive versions of Hilbert’s syzygy theorem for Bézout domains of Krull dimension ≤ 1 with a divisibility test and for coherent zero-dimensional Bézout rings with a divisibility test (e.g. for ℤ and ℤ/Nℤ, see [11, 13, 18, 19]) following Schreyer’s method. These two cases are instances of Gröbner rings. Moreover, we extend these results to arbitrary coherent strict Bézout rings with a divisibility test for the case of finitely generated modules whose module of leading terms is finitely generated.

1 Gröbner bases for modules over a discrete ring

General context. In this article, R is a commutative ring with unit, X_{1}, …, X_{n} are n indeterminates (n ≥ 1), R[\underline{X}] = R[X_{1}, …, X_{n}], H_{m} ≃ 𝔸^{m}(R[\underline{X}]) is a free R[\underline{X}]-module with basis (e_{1}, …, e_{m}) (m ≥ 1), and > is a monomial order on H_{m} (see Definition 1.3).

We start with recalling the following constructive definitions.

Definition 1.1.

• R is discrete if it is equipped with a zero test: equality is decidable.

• R is zero-dimensional and we write dimR ≤ 0 if

∀a ∈ R ∃k ∈ ℕ ∃x ∈ R a^{k}(ax − 1) = 0.

• R has Krull dimension ≤ 1 and we write dimR ≤ 1 if

∀a, b ∈ R ∃k, ℓ ∈ ℕ ∃x, y ∈ R b^{ℓ}(a^{k}(ax − 1) + by) = 0.

• Let U be an R-module. The syzygy module of a p-tuple (v_{1}, …, v_{p}) ∈ U^{p} is

Syz(v_{1}, …, v_{p}) := { (b_{1}, …, b_{p}) ∈ R^{n} ; b_{1}v_{1} + ⋯+ b_{p}v_{p} = 0 }.

The syzygy module of a single element v is the annihilator Ann(v) of v.

• An R-module U is coherent if the syzygy module of every p-tuple of elements of U is finitely generated,^{1} i.e. if there is an algorithm providing a finite system of generators for the syzygies, and an algorithm that represents each syzygy as a linear combination of the generators. R is coherent if it is coherent as an R-module. It is well known that a module is coherent iff on the one hand any intersection of two finitely generated submodules is finitely generated, and on the other hand the annihilator of every element is a finitely generated ideal.

• R is local if, for every element x ∈ R, either x or 1 + x is invertible.

• R is equipped with a divisibility test if, given a, b ∈ R, one can answer the question a ∈? ⟨b⟩ and, in the case of a positive answer, one can explicitly provide c ∈ R such that a = bc.

• R is strongly discrete if it is equipped with a membership test for finitely generated ideals, i.e. if, given a, b_{1}, …, b_{p} ∈ R, one can answer the question a ∈? ⟨b_{1}, …, b_{p}⟩ and, in the case of a positive answer, one can explicitly provide c_{1}, …, c_{p} ∈ R such that a = c_{1}b_{1} + ⋯+ c_{p}b_{p}.

1In contradistinction to Bourbaki and to the Stacks project, we do not require U to be finitely generated.

• R is a valuation ring^{2} if every two elements are comparable w.r.t. division, i.e. if, given a, b ∈ R, either a | b or b | a. A valuation ring is a local ring; it is coherent iff the annihilator of any element is principal. A valuation domain is coherent. A valuation ring is strongly discrete iff it is equipped with a divisibility test.

• R is a Bézout ring if every finitely generated ideal is principal, i.e. of the form ⟨a⟩ = Ra with a ∈ R. A Bézout ring is strongly discrete iff it is equipped with a divisibility test; it is coherent iff the annihilator of any element is principal. To be a valuation ring is to be a Bézout local ring (see [11, Lemma IV-7.1]).

• A Bézout ring R is strict if for all b_{1}, b_{2} ∈ R we can find d, b′_{1}, b′_{2}, c_{1}, c_{2} ∈ R such that b_{1} = db′_{1}, b_{2} = db′_{2}, and c_{1}b′_{1} + c_{2}b′_{2} = 1. Valuation rings and Bézout domains are strict Bézout rings; a quotient or a localisation of a strict Bézout ring is again a strict Bézout ring (see [11, Exercise IV-7 pp. 220–221, solution pp. 227–228]). A zero-dimensional Bézout ring is strict (because it is a “Smith ring”, see [7, Exercice XVI-9 p. 355, solution p. 526] and [11, Exercise IV-8 pp. 221-222, solution p. 228]).

Remark 1.2. In some cases, e.g. euclidean domains or polynomial rings over a discrete field, a strongly discrete ring is equipped with a division algorithm which, for arbitrary a ∈ R and (b_{1}, …, b_{p}) ∈ R^{p}, provides an expression a = c′_{1}b_{1} + ⋯+ c′_{p}b_{p} + e with quotients c′_{1}, …, c′_{p} and a remainder e, where e = 0 iff a ∈ ⟨b_{1}, …, b_{p}⟩. When a strongly discrete ring is not equipped with a division algorithm, we shall consider that the division is trivial if a ∉ ⟨b_{1}, …, b_{p}⟩: the quotients vanish and e = a. In the case of Bézout rings, dividing a by (b_{1}, …, b_{p}) amounts to dividing a by the gcd d of (b_{1}, …, b_{p}), since a = c′d + e can be read as a = (c′c_{1})b_{1} + ⋯+ (c′c_{p})b_{p} + e, where d = c_{1}b_{1} + ⋯+ c_{p}b_{p}.

Definition 1.3 (Monomial orders on finite-rank free R[\underline{X}]-modules, see [1, 5]).

(1) A monomial in H_{m} is a vector of type \underline{X}^{α} e_{ℓ} (1 ≤ ℓ ≤ m), where \underline{X}^{α} = X_{1}^{α_{1}} ⋯ X_{n}^{α_{n}} is a monomial in R[\underline{X}]; the index ℓ is the position of the monomial. The set of monomials in H_{m} is denoted by 𝕄_{n}^{m}, with 𝕄_{n}^{1} ≅ 𝕄_{n} (the set of monomials in R[\underline{X}]). E.g., X_{1}X_{2}^{3}e_{2} is a monomial in H_{m}, but 2X_{1}e_{3}, (X_{1} + X_{2}^{3})e_{2} and X_{1}e_{2} + X_{2}^{3}e_{3} are not.

2Here we follow Kaplansky’s definition: R may have nonzero zerodivisors. In [19] it is required that a valuation ring be strongly discrete. We prefer to add this hypothesis when the argument requires it, so as to discriminate the algorithms that rely on the divisibility test from those that do not.

If M = \underline{X}^{α} e_{ℓ} and N = \underline{X}^{β}e_{k}, we say that M divides N if ℓ = k and \underline{X}^{α} divides \underline{X}^{β}. E.g., X_{1}e_{1} divides X_{1}X_{2}e_{1}, but does not divide X_{1}X_{2}e_{2}. Note that in the case that M divides N, there exists a monomial \underline{X}^{γ} in R[\underline{X}] such that N = \underline{X}^{γ}M: in this case we define N/M := \underline{X}^{γ}; e.g., (X_{1}X_{2}e_{1})/(X_{1}e_{1}) = X_{2}.

A term in H_{m} is a vector of type cM, where c ∈ R\{0} and M ∈ 𝕄_{n}^{m}. We say that a term cM divides a term c′M′, with c, c′ ∈ R\{0} and M, M′ ∈ 𝕄_{n}^{m}, if c divides c′ and M divides M′.

(2) A monomial order on H_{m} is a relation > on 𝕄_{n}^{m} such that

(i) > is a total order on 𝕄_{n}^{m},

(ii) \underline{X}^{α} M > M for all M ∈ 𝕄_{n}^{m} and \underline{X}^{α} ∈ 𝕄_{n} \ \{1\},

(iii) M > N ⟹ \underline{X}^{α} M > \underline{X}^{α} N for all M, N ∈ 𝕄_{n}^{m} and \underline{X}^{α} ∈ 𝕄_{n}.

Note that, when specialised to the case m = 1, this definition coincides with the definition of a monomial order on R[\underline{X}].

When R is discrete, any nonzero vector h ∈ H_{m} can be written as a sum of terms

h = c_{t}M_{t} + c_{t−1} M_{t−1} + ⋯+ c_{1}M_{1},

with c_{ℓ} ∈ R \ {0}, M_{ℓ} ∈ 𝕄_{n}^{m}, and M_{t} > M_{t−1} > ⋯> M_{1}. We define the leading coefficient, leading monomial, and leading term of h as in the ring case: LC(h) = c_{t}, LM(h) = M_{t}, LT(h) = c_{t}M_{t}. Letting M_{t} = \underline{X}^{α} e_{ℓ} with \underline{X}^{α} ∈ 𝕄_{n}^{m} and 1 ≤ ℓ ≤ m, we say that α is the multidegree of h and write mdeg(h) = α, and that the index ℓ is the leading position of h and write LPos(h) = ℓ.

We stipulate that LT(0) = 0 and mdeg(0) = −∞, but we do not define LPos(0).

(3) A monomial order on R[\underline{X}] gives rise to the following canonical monomial order on H_{m}: for monomials M = \underline{X}^{α} e_{ℓ} and N = \underline{X}^{β}e_{k} ∈ 𝕄_{n}^{m}, let us define that

M > N if | \begin{matrix}either & \underline{X}^{α} > \underline{X}^{β} \\ or both & \underline{X}^{α} = \underline{X}^{β} and ℓ < k. \end{matrix}

This monomial order is called term over position (TOP) because it gives more importance to the monomial order on R[\underline{X}] than to the vector position. E.g., when X_{2} > X_{1}, we have

X_{2}e_{1} > X_{2}e_{2} > X_{1}e_{1} > X_{1}e_{2}.

Definition 1.4 (Gröbner bases and Schreyer’s monomial order). Let R be a discrete ring. Consider G = (g_{1}, …, g_{p}), g_{j} ∈ H_{m} \ {0}, and the finitely generated submodule U = ⟨g_{1}, …, g_{p}⟩ = R[\underline{X}]g_{1} + ⋯+ R[\underline{X}]g_{p} of H_{m}.

(1) The module of leading terms of U is LT(U) := ⟨ LT(u) ; u ∈ U ⟩.

(2) G is a Gröbner basis for U if LT(U) = ⟨LT(G)⟩ := ⟨LT(g_{1}), …, LT(g_{p})⟩.

(3) Let (ϵ_{1}, …, ϵ_{p}) be the canonical basis of R[\underline{X}]^{p}. Schreyer’s monomial order induced by > and (g_{1}, …, g_{p}) on R[\underline{X}]^{p} is the order denoted by >_{g_{1} ,...,g_{p}} , or again by >, defined as follows:

\underline{X}^{α} ϵ_{ℓ} > \underline{X}^{β}ϵ_{k} if | \begin{matrix}either & LM(\underline{X}^{α} g_{ℓ}) > LM(\underline{X}^{β}g_{k}) \\ or both & LM(\underline{X}^{α} g_{ℓ}) = LM(\underline{X}^{β}g_{k}) and ℓ < k. \end{matrix}

Schreyer’s monomial order is defined on R[\underline{X}]^{p} in the same way as when R is a discrete field (see [8, p. 66]).

2 The algorithms

The context

Let us now present the algorithms to be discussed in this article in a form that adapts as well to the case where R is a coherent valuation ring with a divisibility test as to the case where R is a coherent strict Bézout ring with a divisibility test (note that the former case is the local case of the latter). This is achieved by appeals to “find … such that …” commands that will adapt to the corresponding framework. I.e., the following context is needed for the algorithms, except that coherence and strictness is not used in the division algorithm and that the divisibility test is not used for the computation of S-polynomials.

Context 2.1. The algorithms take place in a coherent strict Bézout ring R with a divisibility test. In the local case, R is a coherent valuation ring with a divisibility test.

The division algorithm

This algorithm takes place in Context 2.1 for R; note however that coherence and strictness are not used here. Like the classical division algorithm for F[\underline{X}]^{m} with F a discrete field (see [19, Algorithm 211]), this algorithm has the following goal.

Input h ∈ H_{m}, h_{1}, …, h_{p} ∈ H_{m} \ {0}.
Output q_{1}, …, q_{p} ∈ R[\underline{X}] and r ∈ H_{m} such that
h = q_{1}h_{1} + ⋯+ q_{p}h_{p} + r,
LM(h) ≥ LM(q_{j}) LM(h_{j}) whenever q_{j} ≠ 0,
T ∉ ⟨LT(h_{1}), …, LT(h_{p})⟩ for each term T of r.

Definition and notation 2.2. The vector r is called a remainder of h on division by H = (h_{1}, …, h_{p}) and is denoted by r = \overline{h}^{H}.

This notation would gain in precision if it included the dependence of the remainder on the algorithm mentioned in Remark 1.2.

Division algorithm 2.3.

1 l o c a l v a r i a b l e s j : {1, …, p} , D : subset of {1, …, p},
2  c, c_{j} , d, e : R , h′: H_{m} ;
3 q_{1} ← 0 ; …; q_{p} ← 0 ; r ← 0 ; h′ ← h ;
4 while h′ ≠ 0 do
5 D ← { j ; LM(h_{j}) | LM(h′) } ;
6 f i n d d, c_{j} (j ∈ D) such that
7  d = gcd(LC(h_{j}))_{j∈D} = ∑ _{j∈D} c_{j} LC(h_{j}) ;
8 f i n d c, e such that

9 LC(h′) = cd + e (with e = 0 iff d divides LC(h′), see Remark 1.2) ;

10  f o r j in D do
11  q_{j} ← q_{j} + cc_{j} (LM(h′)/ LM(h_{j}))
12 od ;
13 r ← r + e LM(h′) ;
14 h′ ← h′− ∑ _{j∈D} cc_{j} (LM(h′)/ LM(h_{j}))h_{j} − e LM(h′)
15 od

By convention, if D is empty, then d = 0. At each step of the algorithm, the equality h = q_{1}h_{1} + ⋯+ q_{p}h_{p} + h′+ r holds while mdeg(h′) decreases.

Note that in the case of a valuation ring, the gcd d is an LC(h_{j_{0}} ) dividing all the LC(h_{j}), and the Bézout identity may be given by setting c_{j_{0}} = 1 and c_{j} = 0 for j ≠ j_{0}: see Algorithm 3.1.

The S-polynomial algorithm

This algorithm takes also place in Context 2.1 for R. Note however that the divisibility test is not used here; only the zero test is used. This algorithm is a key tool for constructing a Gröbner basis and has been introduced by Buchberger [4] for the case where the base ring is a discrete field. It has the following goal.

Input f, g ∈ H_{m} \ {0}.
Output the S-polynomial given by b\underline{X}^{β} and a\underline{X}^{α} as S(f, g) = b\underline{X}^{β}f − a\underline{X}^{α} g:

if f = g, then b\underline{X}^{β} = b is a generator of Ann(LC(f)) and a\underline{X}^{α} = 0; otherwise, if LM(f) = \underline{X}^{μ}e_{i} and LM(g) = \underline{X}^{ν}e_{i}, then S(f, g) = b\underline{X}^{(ν−μ)^{+}} f − a\underline{X}^{(μ−ν)^{+}} g with b LC(f) = a LC(g), gcd(a, b) = 1; otherwise, S(f, g) = 0.

Here α^{+} = (max(α_{1}, 0), …, max(α_{n}, 0)) is the positive part of α ∈ ℤ^{n}.

S-polynomial algorithm 2.4.

1 l o c a l v a r i a b l e s a, b : R , μ, ν : ℕ^{n} ;
2 i f f = g then
3 f i n d b such that Ann(LC(f)) = ⟨b⟩ ;
4 S(f, f) ← bf
5 e l s e
6 i f LPos(f) ≠ LPos(g) then
7  S(f, g) ← 0
8 e l s e
9  μ ← mdeg(f) ; ν ← mdeg(g) ;
10  f i n d a, b such that
11  gcd(a, b) = 1,
12  a gcd(LC(f), LC(g)) = LC(f),
13  b gcd(LC(f), LC(g)) = LC(g) ;
14  S(f, g) ← b\underline{X}^{(ν−μ)^{+}} f − a\underline{X}^{(μ−ν)^{+}} g
15  f i
16 f i

Note the following important properties of S(f, g):

• If LM(f) = \underline{X}^{μ}e_{i} and LM(g) = \underline{X}^{ν}e_{i}, then either S(f, g) = 0 or LM(S(f, g)) < \underline{X}^{sup (μ,ν)} e_{i}; if LPos(f) ≠ LPos(g), then S(f, g) = 0;

• S(\underline{X}^{δ}f, \underline{X}^{δ}g) = \underline{X}^{δ}S(f, g) for all δ ∈ ℕ^{n}.

S(f, f) is called the auto-S-polynomial of f. It is designed to produce cancellation of the leading term of f by multiplying f with a generator of the annihilator of LC(f). If the leading coefficient of f is regular, then S(f, f) = 0 as in the discrete field case. In case R is a domain, this algorithm is not supposed to compute auto-S-polynomials and we can remove lines 2–5 and 16: if nevertheless executed with f = g, it yields S(f, f) = 0.

The S-polynomial S(f, g) is designed to produce cancellation of the leading terms of f and g. It is worth pointing out that S(f, g) is not uniquely determined (up to a unit) when R has nonzero zerodivisors. Also S(g, f) is generally not equal (up to a unit) to S(f, g) (in the discrete field case, this ambiguity is taken care of by making the S-polynomial monic). These issues are repaired through the consideration of the auto-S-polynomials S(f, f) and S(g, g).

Note that in the case of a valuation ring, the computation of the coefficients a, b is particularly easy: see Algorithm 3.2.

Buchberger’s algorithm

This algorithm takes place in Context 2.1 for R. Here coherence, strictness, and the divisibility test are used. Concerning the termination of the algorithm, see Section 4.

This algorithm has the following goal.

Input g_{1}, …, g_{p} ∈ H_{m} \ {0}.
Output a Gröbner basis (g_{1}, …, g_{p}, …, g_{t}) for ⟨g_{1}, …, g_{p}⟩.

Buchberger’s algorithm 2.5.

1 l o c a l v a r i a b l e s S : H_{m} , i, j, u : ℕ ;
2 t ← p ;
3 repeat
4 u ← t ;
5 f o r i from 1 to u do
6  f o r j from i to u do

7 S ← \overline{S(g_{i}, g_{j})}^{(g_{1} ,...,g_{u} )} by A l g o r i t h m s 2.4 and 2.3 ;

8  i f S ≠ 0 then
9  t ← t + 1 ;
10  g_{t} ← S
11  f i
12  od
13 od
14 u n t i l t = u

This algorithm is almost the same algorithm as in the case where the base ring is a discrete field. The modifications are in the definition of Spolynomials, in the consideration of the auto-S-polynomials, and in the division of terms (see Item (1) of Definition 1.3). In line 7, the algorithm may be sped up by computing the remainder w.r.t. (g_{1}, …, g_{t}) instead of (g_{1}, …, g_{u}) only. Remark 2.6. If the algorithm terminates, then we can transform the obtained Gröbner basis into a Gröbner basis (g′_{1}, …, g′_{t′}) such that no term of an element g′_{j} lies in ⟨ LT(g′_{k}) ; k ≠ j ⟩ by replacing each element of the Gröbner basis with a remainder of it on division by the other nonzero elements and by repeating this process until it stabilises. Such a Gröbner basis is called a pseudo-reduced Gröbner basis.

The syzygy algorithm for terms

This algorithm takes also place in Context 2.1 for R. Note however that the divisibility test is not used here; only the zero test is used. It has the following goal.

Input terms T_{1}, …, T_{p} ∈ H_{m}.
Output a generating system (S_{i,j} )_{1≤i≤j≤p,LPos (T_{j} )=LPos (T_{i} )} for Syz(T_{1}, …, T_{p}).

In this algorithm, (ϵ_{1}, …, ϵ_{p}) is the canonical basis of R[\underline{X}]^{p}.

Syzygy algorithm for terms 2.7.

1 l o c a l v a r i a b l e s i, j : {1, …, p} , J : subset of {1, …, p},
2  a, b : R , α, β : ℕ^{n} ;
3 f o r i from 1 to p do
4 J ← { j ≥ i ; LPos(T_{j}) = LPos(T_{i}) } ;
5 f o r j in J do
6  compute b\underline{X}^{β}, a\underline{X}^{α} such that S(T_{i}, T_{j}) = b\underline{X}^{β}T_{i} − a\underline{X}^{α} T_{j}

7 by Algorithm 2.4 ;

8  S_{i,j} ← b\underline{X}^{β}ϵ_{i} − a\underline{X}^{α} ϵ_{j}
9 od
10 od

Schreyer’s syzygy algorithm

This algorithm takes also place in Context 2.1 for R. It has the following goal.

Input a Gröbner basis (g_{1}, …, g_{p}) for a submodule of H_{m}.
Output a Gröbner basis (u_{i,j} )_{1≤i≤j≤p,LPos (g_{j} )=LPos (g_{i} )}  for Syz(g_{1}, …, g_{p})

w.r.t. Schreyer’s monomial order induced by > and (g_{1}, …, g_{p}).

In this algorithm, (ϵ_{1}, …, ϵ_{p}) is the canonical basis of R[\underline{X}]^{p}.

Schreyer’s syzygy algorithm 2.8.

1 l o c a l v a r i a b l e s i, j : {1, …, p} , J : subset of {1, …, p},
2  a, b : R , α, β : ℕ^{n} , q_{ℓ} : R[\underline{X}];
3 f o r i from 1 to p do
4 J ← { j ≥ i ; LPos(g_{j}) = LPos(g_{i}) } ;
5 f o r j in J do
6  compute b\underline{X}^{β}, a\underline{X}^{α} such that S(g_{i}, g_{j}) = b\underline{X}^{β}g_{i} − a\underline{X}^{α} g_{j}

7 by Algorithm 2.4 ;

8  compute q_{1}, …, q_{p} such that

9 S(g_{i}, g_{j}) = q_{1}g_{1} + ⋯+ q_{p}g_{p} by Algorithm 2.3 (note that

10  LM(S(g_{i}, g_{j})) ≥ LM(q_{ℓ}) LM(g_{ℓ}) whenever q_{ℓ} ≠ 0) ;
11  u_{i,j} ← b\underline{X}^{β}ϵ_{i} − a\underline{X}^{α} ϵ_{j} − q_{1}ϵ_{1} − ⋯− q_{p}ϵ_{p}
12 od
13 od

The polynomials q_{1}, …, q_{p} of lines 8–10 may have been computed while constructing the Gröbner basis.

Remark 2.9. For an arbitrary system of generators (h_{1}, …, h_{r}) for a submodule U of H_{m}, the syzygy module of (h_{1}, …, h_{r}) is easily obtained from the syzygy module of a Gröbner basis for U (see [19, Theorem 296]).

3 The algorithms in the case of a valuation ring

This is the case of a local Bézout ring. We consider a coherent valuation ring R with a divisibility test. In this case, we get simplified versions of the algorithms given in Section 2. We recover the algorithms given in [16, 19], but for modules instead of ideals. In particular, we generalise Buchberger’s algorithm to convenient valuation rings and modules. Note that the algorithm given in [16] contains a bug which is corrected in the corrigendum [17] to the papers [10, 16].

Division algorithm 3.1 (see [19, Definition 226]). Let R be a valuation ring with a divisibility test. In the Division algorithm 2.3, instead of defining the set D and finding the gcd d, one may look out for the first LT(h_{i}) such that LT(h_{i}) divides LT(h′); in case of success, the algorithm proceeds with this index i, and the Bézout identity of line 7 is not needed.

1 l o c a l v a r i a b l e s i : {1, …, p}, c : R , h′: H_{m} , n o t d i v : boolean;
2 q_{1} ← 0 ; …; q_{p} ← 0 ; r ← 0 ; h′ ← h ;

3 while h′ ≠ 0 do
4 i ← 1 ;
5 n o t d i v ← true ;
6 while i ≤ p and n o t d i v do
7  i f LT(h_{i}) | LT(h′) then
8  f i n d c such that c LC(h_{i}) = LC(h′) ;
9  q_{i} ← q_{i} + c(LM(h′)/ LM(h_{i})) ;
10  h′ ← h′− c(LM(h′)/ LM(h_{i}))h_{i} ;
11  n o t d i v ← f a l s e
12  e l s e
13  i ← i + 1
14  f i
15 od ;
16  i f n o t d i v then
17  r ← r + LT(h′) ;
18  h′ ← h′− LT(h′)
19  f i
20 od

S-polynomial algorithm 3.2 (see [19, Definition 229]). Let R be a coherent valuation ring. We define the S-polynomial of two nonzero vectors in H_{m} by the S-polynomial algorithm 2.4. In this algorithm, the finding of a, b in lines 10-13 will take the following simple form, typical for valuation rings:

f i n d a, b such that
a LC(g) = b LC(f) with a = 1 or b = 1

This does not rely on the divisibility test: the explicit disjunction “a divides b or b divides a” is sufficient. When we have a divisibility test, the following expression arises for S(f, g) with f ≠ g, LPos(f) = LPos(g), mdeg(f) = μ, mdeg(g) = ν:

S(f, g) = \{ \begin{matrix}\underline{X}^{(ν−μ)^{+}} f − a\underline{X}^{(μ−ν)^{+}} g & if LC(g) | LC(f), where LC(f) = a LC(g) \\ b\underline{X}^{(ν−μ)^{+}} f − \underline{X}^{(μ−ν)^{+}} g & otherwise, where b LC(f) = LC(g). \end{matrix}

Note also that the annihilator Ann(LC(f)) appearing in the computation of the auto-S-polynomial is principal because R is a coherent valuation ring: there is a b such that Ann(LC(f)) = bR (b being defined up to a unit, see [11, Exercise IX-7]).

Example 3.3 (S-polynomials over R = 𝔽_{2}[Y]/⟨Y^{r}⟩, r ≥ 2, a generalisation of [19, Example 231]). The ring R = 𝔽_{2}[Y]/⟨Y^{r}⟩ = 𝔽_{2}[y] (where y = \overline{Y}) is a zero-dimensional coherent valuation ring with nonzero zerodivisors (Ann(y^{k}) = ⟨y^{r−k} ⟩). Each nonzero element a of this ring may be written in a unique way as y^{k}(1 + yb) with k = 0, …, r − 1 and 1 + yb a unit. Let f ≠ g ∈ R[\underline{X}]\\{0\} and μ = mdeg(f), ν = mdeg(g). If LC(g) = y^{k}(1+yb) and LC(f) = y^{ℓ}(1 + yc), then

S(f, g) = \{ \begin{matrix}\underline{X}^{(ν−μ)^{+}} f − (1 + yc)(1 + yb)^{−1} y^{ℓ−k} \underline{X}^{(μ−ν)^{+}} g & if k ≤ ℓ \\ (1 + yb)(1 + yc)^{−1} y^{k−ℓ} \underline{X}^{(ν−μ)^{+}} f − \underline{X}^{(μ−ν)^{+}} g & if k > ℓ \end{matrix}

=_{up to a unit} \{ \begin{matrix}(1 + yb)\underline{X}^{(ν−μ)^{+}} f − (1 + yc)y^{ℓ−k} \underline{X}^{(μ−ν)^{+}} g & if k ≤ ℓ \\ (1 + yb)y^{k−ℓ} \underline{X}^{(ν−μ)^{+}} f − (1 + yc)\underline{X}^{(μ−ν)^{+}} g & if k > ℓ. \end{matrix}

For the computation of the auto-S-polynomial S(f, f), two cases may arise:

• If LC(f) is a unit, then S(f, f) = 0.

• If LC(f) is y^{k} (k > 0) up to a unit, then S(f, f) = y^{r−k} f.

E.g., with r = 2, using the lexicographic order for which X_{2} > X_{1} and considering the polynomials f = yX_{2} + X_{1} and g = yX_{1} + y, we have:

S(f, g) = X_{1}f − X_{2}g = X_{1}^{2} + yX_{2}, S(f, f) = yf = yX_{1}, S(g, g) = yg = 0.

4 Termination of Buchberger’s algorithm for a Bézout ring

The following lemma provides a necessary and sufficient condition for a term to belong to a module generated by terms over a coherent strict Bézout ring with a divisibility test.

Lemma 4.1 (Term modules, see [19, Lemma 227]). Let R be a coherent strict Bézout ring with a divisibility test. Let U be a submodule of H_{m} generated by a finite collection of terms a_{α} \underline{X}^{α} e_{i_{α}} with α ∈ A. A term b\underline{X}^{β}e_{r} lies in U iff there is a nonempty subset A′ of A such that \underline{X}^{α} e_{i_{α}} divides \underline{X}^{β}e_{r} for every α ∈ A′ (i.e. i_{α} = r and \underline{X}^{α} | \underline{X}^{β}) and gcd_{α∈A′} (a_{α}) divides b. In the local case, there hence is an a_{α} with α ∈ A′ that divides b.

Proof. The condition is clearly sufficient. For the necessity, write

b\underline{X}^{β}e_{r} = ∑ _{α∈Ã} c_{α} a_{α} \underline{X}^{γ_{α}} \underline{X}^{α} e_{i_{α}}

with Ã ⊆ A, c_{α} ∈ R \ \{0\}, and \underline{X}^{γ_{α}} ∈ 𝕄_{n}. Then b = ∑ _{α∈A′} c_{α} a_{α}, where A′ is the set of those α such that γ_{α} + α = β and i_{α} = r. For each α ∈ A′, \underline{X}^{α} divides \underline{X}^{β}. Since the gcd of the a_{α} ’s with α ∈ A′ divides every a_{α}, it also divides b.

The following lemma is a key result for the characterisation of Gröbner bases by means of S-polynomials: see [6, Chapter 2, §6, Lemma 5] and, for valuation rings, [19, Lemma 233, adding the hypothesis of coherence].

Lemma 4.2. Let R be a coherent strict Bézout ring and f_{1}, …, f_{p} ∈ H_{m} \ {0} with the same leading monomial M. Let c_{1}, …, c_{p} ∈ R. If c_{1}f_{1} + ⋯+ c_{p}f_{p} vanishes or has leading monomial < M, then c_{1}f_{1} + ⋯+ c_{p}f_{p} is a linear combination with coefficients in R of the S-polynomials S(f_{i}, f_{j}) with 1 ≤ i ≤ j ≤ p.

Proof. Let us write, for j ≠ i, LC(f_{j}) = d_{i,j} a_{i,j} with d_{i,j} = gcd(LC(f_{i}), LC(f_{j})), so that gcd(a_{i,j} , a_{j,i} ) = 1 and S(f_{i}, f_{j}) = a_{i,j} f_{i} − a_{j,i} f_{j}. For each permutation i_{1}, …, i_{p} of 1, …, p, we shall transform the sum a_{i_{1} ,i_{2}} ⋯ a_{i_{p−1} ,i_{p}} (c_{1}f_{1} + ⋯+ c_{p}f_{p}) by replacing successively

a_{i_{1} ,i_{2}} f_{i_{1}}  by S(f_{i_{1}} , f_{i_{2}} ) + a_{i_{2} ,i_{1}} f_{i_{2}} ,
⋮  ⋮
a_{i_{p−1} ,i_{p}} f_{i_{p−1}} by S(f_{i_{p−1}} , f_{i_{p}} ) + a_{i_{p} ,i_{p−1}} f_{i_{p}} .

At the end, the sum will be a linear combination of S(f_{i_{1}} , f_{i_{2}} ), S(f_{i_{2}} , f_{i_{3}} ), …, S(f_{i_{p−1}} , f_{i_{p}} ), and f_{i_{p}} ; let z be the coefficient of f_{i_{p}} in this combination. The sum as well as each of the S-polynomials vanish or have leading monomial < M, so that the hypothesis yields z LC(f_{i_{p}} ) = 0; therefore zf_{i_{p}} is a multiple of S(f_{i_{p}} , f_{i_{p}} ).

It remains to obtain a Bézout identity w.r.t. the products a_{i_{1} ,i_{2}} ⋯ a_{i_{p−1} ,i_{p}} , because it yields an expression of c_{1}f_{1} + ⋯+ c_{p}f_{p} as a linear combination of the required form. For this, it is enough to develop the product of the \binom{s}{2} Bézout identities w.r.t. a_{i,j} and a_{j,i} , 1 ≤ i < j ≤ p: this yields a sum of products of \binom{s}{2} terms, each of which is either a_{i,j} or a_{j,i} , 1 ≤ i < j ≤ p, so that it is indexed by the tournaments on the vertices 1, …, p; every such product contains a product of the above form a_{i_{1} ,i_{2}} ⋯ a_{i_{p−1} ,i_{p}} because every tournament contains a hamiltonian path (see [14]).

Remark 4.3. The above proof results from an analysis of the following proof in the case where R is local and m = 1, which entails in fact the general case. Since R is a valuation ring, we may consider a permutation i_{1}, …, i_{p} of 1, …, p such that LC(f_{i_{p}} ) | LC(f_{i_{p−1}} ) | ⋯| LC(f_{i_{1}} ). Thus S(f_{i_{1}} , f_{i_{2}} ) = f_{i_{1}} −a_{i_{2} ,i_{1}} f_{i_{2}} , …, S(f_{i_{p−1}} , f_{i_{p}} ) = f_{i_{p−1}} −a_{i_{p} ,i_{p−1}} f_{i_{p}} for some a_{i_{2} ,i_{1}} , …, a_{i_{p} ,i_{p−1}} . Then, by replacing successively f_{i_{k}} by S(f_{i_{k}} , f_{i_{k+1}} ) + a_{i_{k+1} ,i_{k}} f_{i_{k+1}} , the linear combination c_{1}f_{1} + ⋯+ c_{p}f_{p} may be rewritten as a linear combination of S(f_{i_{1}} , f_{i_{2}} ), …, S(f_{i_{p−1}} , f_{i_{p}} ), and f_{i_{p}} , with the coefficient of f_{i_{p}} turning out to lie in Ann(LC(f_{i_{p}} )).

Lemma 4.2 enables us to generalise some classical results on the existence and characterisation of Gröbner bases to the case of coherent strict Bézout rings with a divisibility test. See [19, Theorem 234] for the case of valuation rings and ideals.

Theorem 4.4 (Buchberger’s criterion for Gröbner bases). Let R be a coherent strict Bézout ring with a divisibility test and U = ⟨g_{1}, …, g_{p}⟩ a nonzero submodule of H_{m}. Then G = (g_{1}, …, g_{p}) is a Gröbner basis for U iff the remainder of S(g_{i}, g_{j}) on division by G vanishes for all pairs i ≤ j.

Theorem 4.4 entails that Buchberger’s algorithm 2.5 constructs a Gröbner basis for finitely generated ideals of coherent valuation rings with a divisibility test when such a basis exists (compare [19, Algorithm 235]). The two following theorems provide a general explanation for the termination of Buchberger’s algorithm and are therefore pivotal.

Theorem 4.5 (Termination of Buchberger’s algorithm, case m = 1). Let R be a coherent valuation ring with a divisibility test, I a nonzero finitely generated ideal of R[\underline{X}], and > a monomial order on R[\underline{X}]. If LT(I) is finitely generated, then Buchberger’s algorithm 2.5 computes a finite Gröbner basis for I.

Proof. Let f_{1}, …, f_{p} ∈ R[\underline{X}] \ \{0\} be generators of I. Let LT(I) = ⟨LT(g_{1}), …, LT(g_{r})⟩ with g_{i} ∈ I \ {0}. Let 1 ≤ k ≤ r. As g_{k} ∈ I, there exist E ⊆ \{1, …, p\} and h_{i} ∈ R[\underline{X}] \ \{0\}, i ∈ E, such that

g_{k} = ∑ _{i∈E} h_{i}f_{i}  (4.1)

with mdeg(g_{k}) ≤ sup_{i∈E} (mdeg(M_{i}N_{i})) =: γ (we call it the multidegree of the expression (4.1) for g_{k} w.r.t. the generating set {f_{1}, …, f_{p}} of I), where M_{i} = LM(h_{i}) and N_{i} = LM(f_{i}). Let F = { i ∈ E ; mdeg(M_{i}N_{i}) = γ }.

Case 1: mdeg(g_{k}) = γ, say mdeg(g_{k}) = mdeg(M_{i_{0}} N_{i_{0}} ) for some i_{0} ∈ F. As the leading coefficients of the h_{i}f_{i}’s with i ∈ F are comparable w.r.t. division, we can suppose that all of them are divisible by the leading coefficient of h_{i_{0}} f_{i_{0}} . It follows that LT(g_{k}) ∈ ⟨LT(f_{i_{0}} )⟩ ⊆ ⟨LT(f_{1}), …, LT(f_{p}) ⟩.

Case 2: mdeg(g_{k}) < γ. We have

\begin{aligned}g_{k} & = ∑ _{i∉F} h_{i}f_{i} + ∑ _{i∈F} h_{i}f_{i} \\ & = ∑ _{i∉F} h_{i}f_{i} + ∑ _{i∈F} (h_{i} − LT(h_{i}))f_{i} + ∑ _{i∈F} LT(h_{i})f_{i}. \end{aligned}

Letting c_{i} = LC(h_{i}), we get

mdeg( ∑ _{i∈F} c_{i}M_{i}f_{i}) < γ.

By virtue of Lemma 4.2, there exists a finite family (a_{i,j} ) of elements of R such that

∑ _{i∈F} c_{i}M_{i}f_{i} = ∑ _{i≤j∈F} a_{i,j} S(M_{i}f_{i}, M_{j} f_{j}).

But, for i ≤ j ∈ F, letting N_{i,j} = lcm(N_{i}, N_{j}) and writing S(f_{i}, f_{j}) = a\frac{N_{i,j}}{N_{i}} f_{i} + b\frac{N_{i,j}}{N_{j}} f_{j} for some a, b ∈ R, we have S(M_{i}f_{i}, M_{j} f_{j}) = a\frac{X^{γ}}{M_{i} N_{i}} M_{i}f_{i} + b\frac{X^{γ}}{M_{j} N_{j}} M_{j} f_{j} = \frac{X^{γ}}{N_{i,j}} S(f_{i}, f_{j}). It follows that

∑ _{i∈F} c_{i}M_{i}f_{i} = ∑ _{i≤j∈F} a_{i,j} m_{i,j} S(f_{i}, f_{j}),

where the m_{i,j} ’s are monomials. Thus we obtain another expression for g_{k},

g_{k} = ∑ _{i∉F} h_{i}f_{i} + ∑ _{i∈F} (h_{i} − LT(h_{i}))f_{i} + ∑ _{i≤j∈F} a_{i,j} m_{i,j} S(f_{i}, f_{j}),

and the multidegree of this expression, now w.r.t. the generating set of I obtained by adding the elements S(f_{i}, f_{j}), i ≤ j ∈ F, to the f_{1}, …, f_{p}, is < γ. Reiterating this, we end up with a situation like that of Case 1 for all the g_{k}’s because the set of monomials is well-ordered. So we reach the termination condition in Algorithm 2.5 after a finite number of steps.

Theorem 4.6 (Termination of Buchberger’s algorithm). Let R be a coherent strict Bézout ring with a divisibility test and U a nonzero finitely generated submodule of H_{m}. If LT(U) is finitely generated, then Buchberger’s algorithm 2.5 computes a Gröbner basis for U.

Proof. It suffices to prove the result when R is local and m = 1, in which case this is Theorem 4.5. Let us explain in a few words how to pass from the local to the global case (compare [19, Section 3.3.11] and [9]). Suppose that we are computing S(f, g) and that the leading coefficients a and b of f and g are uncomparable under division. A key fact is that if we write a = gcd(a, b) a′, b = gcd(a, b) b′ with gcd(a′, b′) = 1, then a divides b in R[\frac{1}{a′}], b divides a in R[\frac{1}{b′}], and the two multiplicative subsets a^{′ℕ} and b^{′ℕ} are comaximal because 1 ∈ ⟨a′, b′⟩. Then R splits into R[\frac{1}{a′}] and R[\frac{1}{b′}], and we can continue as if R were a valuation ring. If mdeg(f) = μ and mdeg(g) = ν, then S(f, g) is being computed as follows:

• in the ring R[\frac{1}{b′}], S(f, g) = X^{(ν−μ)^{+}} f − \frac{a′}{b′}X^{(μ−ν)^{+}} g =: S_{1};

• in the ring R[\frac{1}{a′}], S(f, g) = \frac{b′}{a′}X^{(ν−μ)^{+}} f − X^{(μ−ν)^{+}} g =: S_{2}.

But, letting S := b′X^{(ν−μ)^{+}} f − a′X^{(μ−ν)^{+}} g, we have

S = b′S_{1} = a′S_{2}.

As S is equal to S_{1} up to a unit in R[\frac{1}{b′}], and to S_{2} in R[\frac{1}{a′}], it can replace both of them, and thus there was no need to open the two branches R[\frac{1}{a′}] and R[\frac{1}{b′}].

When is a valuation ring a Gröbner ring?

We recall here some results given in [19] on the interplay between the concepts of Gröbner ring, Krull dimension, and archimedeanity; here are the relevant definitions.

Definition 4.7.

• The (Jacobson) radical Rad(R) of an arbitrary ring R is the ideal { a ∈ R ; 1 + aR ⊆ R^{×} }, where R^{×} is the unit group of R.

• The residual field of a local ring R is the quotient R/ Rad(R). The local ring R is residually discrete if its residual field is discrete: this means that x ∈ R^{×} is decidable. A nontrivial local ring R is residually discrete iff it is the disjoint union of R^{×} and Rad(R).

• A residually discrete valuation ring R is archimedean if

∀a, b ∈ Rad(R) \ {0} ∃k ∈ ℕ a | b^{k}.

• A strongly discrete ring R is a Gröbner ring if for every n ∈ ℕ and every finitely generated ideal I of R[\underline{X}] endowed with the lexicographic monomial order, the module LT(I) is finitely generated as well.

One sees easily that a Gröbner ring is coherent ([19, Proposition 224]). Moreover if R is Gröbner, then so is R[Y].

For a coherent valuation ring with a divisibility test, it is proved in [19] that archimedeanity is equivalent to being a Gröbner ring (at least when we assume that there is no nonzero zerodivisor or there exists a nonzero zerodivisor, see [19, Theorem 272]). For a valuation domain with a divisibility test, it is proved that the condition is equivalent to having Krull dimension ≤ 1 ([19, Theorem 256]). This implies that a strongly discrete Prüfer domain is Gröbner iff it has Krull dimension ≤ 1 ([18, Corollary 6]). This applies to Bézout domains with a divisibility test. When a coherent valuation ring with a divisibility test has a nonzero zerodivisor, it is proved that archimedeanity is equivalent to being zero-dimensional ([19, Proposition 265]).

Let us now, for the comfort of the reader, provide simple arguments for some of these results. Recall that a ring R has Krull dimension ≤ 1 if, given a, b ∈ R,

∃k, ℓ ∈ ℕ ∃x, y ∈ R b^{ℓ}(a^{k}(ax − 1) + by) = 0;  (4.2)

when b is regular and a ∈ Rad(R), we get that a^{k} = zb for some k and some z. This shows that a valuation domain of Krull dimension ≤ 1 is archimedean. Conversely, an equality a^{k} = zb is a particularly simple case of (4.2) (take x = 0). Also, when a is invertible, one has ax − 1 = 0 for some x, which is also a form of (4.2). So, if in a local ring the disjunction “x is invertible or x ∈ Rad(R)” is explicit (i.e. if the residual field is discrete), then archimedeanity implies Krull dimension ≤ 1. Summing up, an archimedean valuation ring with a divisibility test has Krull dimension ≤ 1, and a valuation domain with Krull dimension ≤ 1 is archimedean: so a valuation domain is archimedean iff it has Krull dimension ≤ 1.

Recall now that for a local ring, being zero-dimensional means that every element is invertible or nilpotent. Let us consider a valuation ring with a divisibility test containing a nonzero zerodivisor x. We have xy = 0 with y ≠ 0. If x = yz, then y^{2}z = 0, so that x^{2} = 0. If y = xz, then y^{2} = 0. So we have a nonzero nilpotent element u. In this case archimedeanity is equivalent to being zero-dimensional. Indeed, assume first archimedeanity. For an a ∈ Rad(R), we have u | a^{k}, so a^{2k} = 0. Then assume zero-dimensionality. For any a, b ∈ Rad(R), we have a k such that a^{k} = 0, so b | a^{k}.

So, for a coherent valuation ring with a divisibility test, if 0 is the unique zerodivisor, archimedeanity is equivalent to having dimension ≤ 1, and if R has a nonzero zerodivisor, archimedeanity is equivalent to being zerodimensional.

Now assume that R is a coherent valuation ring with a divisibility test. We first compute (c : d) when c, d ≠ 0. We note that (c : d) = ⟨u⟩ for some u (since it is finitely generated). If c | d, then (c : d) = ⟨1⟩. If d | c, then we have a y with c = dy. So y ∈ ⟨u⟩, say y = tu. Since u ∈ (c : d), we have a z with du = cz = dyz = dutz. So du(1 − tz) = 0. If 1 − tz is invertible, then du = 0, so that c = dy = dut = 0, which is impossible. So tz is invertible and ⟨u⟩ = ⟨y⟩: more precisely u = yt′ with t′ invertible.

Now let a, b ∈ Rad(R) \ {0}. We show that (b : a^{∞} ) is finitely generated iff b | a^{k} for some k. If a^{k} = bx then (b : a^{k}) = ⟨1⟩, so (b : a^{∞} ) = ⟨1⟩. If (b : a^{∞} ) is finitely generated, then we have a k such that (b : a^{k}) = (b : a^{k+1} ). If b | a^{k} or b | a^{k+1} , then we are done. The other case (a^{k} | b and a^{k+1} | b) is impossible, for if we have x, y such that b = a^{k}x = a^{k+1} y = a^{k}(ay), then

⟨y⟩ = (b : a^{k+1} ) = (b : a^{k}) = ⟨x⟩ = ⟨ay⟩,

so that y = uay and (1 − ua)y = 0 for some u; since a ∈ Rad(R), 1 − ua is invertible, so that y = 0, which implies b = 0, a contradiction.

We have shown that R is archimedean iff (b : a^{∞} ) is finitely generated for all a, b ∈ Rad(R) \ {0}.

We note also that for an arbitrary commutative ring R, one has

∀a, b ∈ R ⟨1 + bY, a⟩ ∩ R = (b : a^{∞} ).

So a coherent valuation ring R with a divisibility test is archimedean iff the ideal ⟨1 + bY, a⟩ ∩ R is finitely generated for all a, b ∈ R. This condition is fulfilled as soon as R is 1-Gröbner (i.e. satisfies the definition of Gröbner rings with n = 1).

For other details on this topic see [19, Exercise 372 p. 207, solution p. 221, Exercise 387 p. 218, solution p. 251].

5 The syzygy theorem and Schreyer’s algorithm for a valuation ring

In the book Gröbner bases in commutative algebra, Ene and Herzog propose the following exercise.

Problem ([8, Problem 4.11, p. 81]). Let > be a monomial order on the free S-module F = ⨁ _{j=1}^{m} Se_{j} [where S = K[\underline{X}] with K a discrete field], let U ⊂ F be a submodule of F, and suppose that LT(U) = ⨁ _{j=1}^{m} I_{j} e_{j}. Show that U is a free S-module iff I_{j} is a principal ideal for j = 1, …, m.

It is obvious that this condition is sufficient. Unfortunately, it is not necessary as shows the following example, so that the statement of [8, Problem 4.11] is not correct.

Example 5.1. Let > be a TOP monomial order on K[X, Y]^{2} for which Y > X, K being a field, let e_{1} = (1, 0) and e_{2} = (0, 1), and consider the free submodule U of K[X, Y]^{2} generated by u_{1} = (Y, X) and u_{2} = (X, 0). Then LT(u_{1}) = Y e_{1}, LT(u_{2}) = Xe_{1}, S(u_{1}, u_{2}) = Xu_{1} − Y u_{2} = X^{2}e_{2} =: u_{3}, and S(u_{1}, u_{3}) = S(u_{2}, u_{3}) = 0. It follows that (u_{1}, u_{2}, u_{3}) is a Gröbner basis for U, and LT(U) = ⟨Y, X⟩e_{1} ⊕ ⟨X^{2}⟩e_{2}. One can see that ⟨Y, X⟩ is not principal and LT(U) is not free, while U is free.

So we content ourselves with the following observation.

Remark 5.2. Let > be a monomial order on the free S-module F = ⨁ _{j=1}^{m} Se_{j}, where S = R[\underline{X}] and R is a valuation domain. Let U be a submodule of F and suppose that LT(U) = ⨁ _{j=1}^{m} I_{j} e_{j}, where I_{j} is a principal ideal for j = 1, …, m. Then LT(U) and U are free S-modules. (Of course, this is not true anymore if R is a valuation ring with nonzero zerodivisors. Consider e.g. the ideal U = ⟨8X + 2 ⟩ in (ℤ/16ℤ)[X]: we have LT(U) = ⟨2⟩ (so that it is principal), but U is not free since 8U = ⟨0⟩.)

We shall need the following proposition, which generalises [19, Theorem 291] to the case of modules.

Proposition 5.3 (Generating set for the syzygy module of a list of terms for a coherent valuation ring). Let R be a coherent valuation ring, H_{m} a free R[\underline{X}]- module with basis (e_{1}, …, e_{m}), and terms T_{1}, …, T_{p} in H_{m}. Considering the canonical basis (ϵ_{1}, …, ϵ_{p}) of R[\underline{X}]^{p}, the syzygy module Syz(T_{1}, …, T_{p}) is generated by the

S_{i,j} ∈ R[\underline{X}]^{p} with 1 ≤ i ≤ j ≤ p and LPos(T_{i}) = LPos(T_{j}),

as computed by the Syzygy algorithm for terms 2.7.

Note that in the Syzygy algorithm for terms 2.7, the a, b will be found as in the S-polynomial algorithm 3.2, so that we get

S_{i,j} = \{ \begin{matrix}bϵ_{i} & if i = j, where ⟨b⟩ = Ann(LC(T_{i})), \\ \underline{X}^{β}ϵ_{i} − a\underline{X}^{α} ϵ_{j} & if i < j and LC(T_{i}) = a LC(T_{j}), else \\ b\underline{X}^{β}ϵ_{i} − \underline{X}^{α} ϵ_{j} & if i < j and b LC(T_{i}) = LC(T_{j}). \end{matrix}  (5.1)

Here β = (mdeg(T_{j}) − mdeg(T_{i}))^{+} and α = (mdeg(T_{i}) − mdeg(T_{j}))^{+} .

Now we shall follow closely Schreyer’s ingenious proof [15] of Hilbert’s syzygy theorem via Gröbner bases, but with a valuation ring instead of a field. Schreyer’s proof is very well explained in [8, §§ 4.4.1–4.4.3].

Theorem 5.4 (Schreyer’s algorithm for a coherent valuation ring with a divisibility test). Let R be a coherent valuation ring with a divisibility test. Let U be a submodule of H_{m} with Gröbner basis (g_{1}, …, g_{p}). Then the relations u_{i,j} computed by Schreyer’s syzygy algorithm 2.8 form a Gröbner basis for the syzygy module Syz(g_{1}, …, g_{p}) w.r.t. Schreyer’s monomial order induced by > and (g_{1}, …, g_{p}). Moreover, for 1 ≤ i ≤ j ≤ p such that LPos(g_{i}) = LPos(g_{j}),

LT(u_{i,j} ) = \{ \begin{matrix}bϵ_{i} & if i = j, with ⟨b⟩ = Ann(LC(g_{i})), \\ \underline{X}^{β}ϵ_{i} & if i < j and LC(g_{j}) | LC(g_{i}), else \\ b\underline{X}^{β}ϵ_{i} & if i < j and b LC(g_{i}) = LC(g_{j}), \end{matrix}  (5.2)

with β = (mdeg(g_{j}) − mdeg(g_{i}))^{+} .

Proof (a slight modification of the proof of [8, Theorem 4.16]). Let us use the notation of Schreyer’s syzygy algorithm 2.8. Let 1 ≤ i = j ≤ p. As LM(q_{ℓ}) LM(g_{ℓ}) ≤ LM(S(g_{i}, g_{i})) < LM(g_{i}) whenever q_{ℓ} ≠ 0, we infer that LT(u_{i,i} ) = bϵ_{i} with ⟨b⟩ = Ann(LC(g_{i})).

Let 1 ≤ i < j ≤ p such that LPos(g_{i}) = LPos(g_{j}). Suppose that LC(g_{i}) = a LC(g_{j}) for an a: as LM(\underline{X}^{β}g_{i}) = LM(a\underline{X}^{α} g_{j}) and i < j, LT(\underline{X}^{β}ϵ_{i} − a\underline{X}^{α} ϵ_{j}) = \underline{X}^{β}ϵ_{i} w.r.t. Schreyer’s monomial order induced by >, and because LM(q_{ℓ}) LM(g_{ℓ}) ≤ LM(S(g_{i}, g_{j})) < LM(\underline{X}^{β}g_{i}) whenever q_{ℓ} ≠ 0, we infer that LT(u_{i,j} ) = \underline{X}^{β}ϵ_{i}; otherwise, with b such that b LC(g_{i}) = LC(g_{j}), we obtain similarly LT(u_{i,j} ) = b\underline{X}^{β}ϵ_{i}.

Let Equation (5.1) hold with T_{ℓ} = LT(g_{ℓ}): then LT(u_{i,j} ) = LT(S_{i,j} ) holds for all 1 ≤ i ≤ j ≤ p.

Let us show now that the relations u_{i,j} form a Gröbner basis for the syzygy module Syz(g_{1}, …, g_{p}). For this, let v = ∑ _{ℓ=1}^{p} v_{ℓ}ϵ_{ℓ} ∈ Syz(g_{1}, …, g_{p}) and let us show that there exist 1 ≤ i ≤ j ≤ p with LPos(g_{i}) = LPos(g_{j}) such that LT(u_{i,j} ) divides LT(v). Let us write LM(v_{ℓ}ϵ_{ℓ}) = N_{ℓ}ϵ_{ℓ} and LC(v_{ℓ}ϵ_{ℓ}) = c_{ℓ} for 1 ≤ ℓ ≤ p. Then LM(v) = N_{i}ϵ_{i} for some 1 ≤ i ≤ p. Now let v′ = ∑ _{ℓ∈S} c_{ℓ}N_{ℓ}ϵ_{ℓ}, where S is the set of those ℓ for which N_{ℓ} LM(g_{ℓ}) = N_{i} LM(g_{i}). By definition of Schreyer’s monomial order, we have ℓ ≥ i for all ℓ ∈ S. Substituting each ϵ_{ℓ} in v′ by T_{ℓ}, the sum becomes zero. Therefore v′ is a relation of the terms T_{ℓ} with ℓ ∈ S. By virtue of Proposition 5.3, v′ is an R[\underline{X}]-linear combination of the S_{ℓ,j} with ℓ ≤ j in S. Taking into consideration Equation (5.1), we infer, by virtue of Lemma 4.1, that LT(v′) is a multiple of LT(S_{i,j} ) for some j ∈ S. The desired result follows since LT(v) = LT(v′).

As a consequence of Theorem 5.4, we obtain the following constructive versions of Hilbert’s syzygy theorem for a valuation domain.

Theorem 5.5 (Syzygy theorem for a valuation domain with a divisibility test). Let M = H_{m}/U be a finitely presented R[\underline{X}]-module, where R is a valuation domain with a divisibility test. Assume that, w.r.t. some monomial order, LT(U) is finitely generated. Then M admits a free R[\underline{X}]-resolution

0 → F_{p} → F_{p−1} → ⋯→ F_{1} → F_{0} → M → 0

of length p ≤ n + 1.

Proof. It suffices to prove that U has a free R[\underline{X}]-resolution of length p ≤ n. Let (g_{1}, …, g_{p}) be a Gröbner basis for U w.r.t. the considered monomial order. We can reorder the g_{j} ’s so that whenever LM(g_{i}) and LM(g_{j}) involve the same basis element for some i < j, say LM(g_{i}) = N_{i}ϵ_{k} and LM(g_{j}) = N_{j} ϵ_{k}, then deg_{X_{n}} (N_{i}) ≥ deg_{X_{n}} (N_{j}). It follows that the indeterminate X_{n} cannot appear in the leading terms of the u_{i,j} ’s in (5.2). Thus, after at most n computations of the iterated syzygies, we reach a situation where none of the indeterminates X_{n}, …, X_{1} appears in the leading terms of the computed Gröbner basis for the iterated syzygy module. This implies that the iterated syzygy module is free (as noted in Remark 5.2).

Corollary 5.6 (Syzygy theorem for a valuation domain of Krull dimension ≤ 1 with a divisibility test). Let M = H_{m}/U be a finitely presented R[\underline{X}]-module, where R is a valuation domain of Krull dimension ≤ 1 with a divisibility test. Then M admits a finite free R[\underline{X}]-resolution

0 → F_{p} → F_{p−1} → ⋯→ F_{1} → F_{0} → M → 0

of length p ≤ n + 1.

Example 5.7. Let g_{1} = Y^{4} − Y, g_{2} = 2Y, g_{3} = X^{3} − 1 ∈ ℤ_{2ℤ}[X, Y], and let us use the lexicographic order >_{1} for which Y >_{1} X. We have

\begin{aligned}S(g_{1}, g_{2}) & = 2g_{1} − Y^{3}g_{2} = −2Y = −g_{2}, \\ S(g_{1}, g_{3}) & = X^{3}g_{1} − Y^{4}g_{3} = Y^{4} − Y X^{3} = g_{1} − Y g_{3}, \\ S(g_{2}, g_{3}) & = X^{3}g_{2} − 2Y g_{3} = 2Y = g_{2}. \end{aligned}

Thus (g_{1}, g_{2}, g_{3}) is a (pseudo-reduced) Gröbner basis for I = ⟨g_{1}, g_{2}, g_{3}⟩ and LT(I) = ⟨Y^{4}, 2Y, X^{3}⟩. By Theorem 5.4, u_{1,3} = (X^{3} − 1, 0, −Y^{4} + Y), u_{1,2} = (2, −Y^{3} + 1, 0), u_{2,3} = (0, X^{3} − 1, −2Y) form a (pseudo-reduced) Gröbner basis for the syzygy module Syz(g_{1}, g_{2}, g_{3}) w.r.t. Schreyer’s monomial order >_{2} induced by >_{1} and (g_{1}, g_{2}, g_{3}). In particular,

LT(Syz(g_{1}, g_{2}, g_{3})) = ⟨LT(u_{1,3}), LT(u_{1,2}), LT(u_{2,3})⟩
= ⟨X^{3}ϵ_{1}, 2ϵ_{1}, X^{3}ϵ_{2}⟩ = ⟨2, X^{3}⟩ϵ_{1} ⊕ ⟨X^{3}⟩ϵ_{2},

where (ϵ_{1}, ϵ_{2}, ϵ_{3}) stands for the canonical basis of ℤ_{2ℤ}[X, Y]^{3}. We have

\begin{aligned}S(u_{1,3}, u_{1,2}) & = 2u_{1,3} − X^{3}u_{1,2} \begin{matrix}= (−2, Y^{3}X^{3} − X^{3}, −2Y^{4} + 2Y) \\ = −u_{1,2} + (Y^{3} − 1)u_{2,3}, \end{matrix} \\ S(u_{1,3}, u_{2,3}) & = S(u_{1,2}, u_{2,3}) = 0. \end{aligned}

We recover that (u_{1,3}, u_{1,2}, u_{2,3}) is a Gröbner basis for Syz(g_{1}, g_{2}, g_{3}). By Theorem 5.4, the element u_{1,3;1,2} = (2, −X^{3} + 1, −Y^{3} + 1) forms a (pseudoreduced) Gröbner basis for the syzygy module Syz(u_{1,3}, u_{1,2}, u_{2,3}) w.r.t. Schreyer’s monomial order >_{3} induced by >_{2} and (u_{1,3}, u_{1,2}, u_{2,3}). In particular, LT(Syz(u_{1,3}, u_{1,2}, u_{2,3})) = ⟨LT(u_{1,3;1,2} )⟩ = ⟨2⟩ϵ′_{1}, where (ϵ′_{1}, ϵ′_{2}, ϵ′_{3}) stands for the canonical basis of ℤ_{2ℤ}[X, Y]^{3}. By Remark 5.2, Syz(u_{1,3}, u_{1,2}, u_{2,3}) is free. We conclude that I admits the following length-2 free ℤ_{2ℤ}[X, Y]- resolution:

0 −→ ℤ_{2ℤ}[X, Y] −−−−→^{u_{1,3;1,2}} ℤ_{2ℤ}[X, Y]^{3} \underrightarrow{( \begin{matrix}u_{1,3} \\ u_{1,2} \\ u_{2,3} \end{matrix} )} ℤ_{2ℤ}[X, Y]^{3} \underrightarrow{( \begin{matrix}g_{1} \\ g_{2} \\ g_{3} \end{matrix} )} I → 0.

It follows that ℤ_{2ℤ}[X, Y]/I admits the following length-3 free ℤ_{2ℤ}[X, Y]- resolution:

0 → ℤ_{2ℤ}[X, Y] → ℤ_{2ℤ}[X, Y]^{3} → ℤ_{2ℤ}[X, Y]^{3} → ℤ_{2ℤ}[X, Y] →^{π} ℤ_{2ℤ}[X, Y]/I → 0.

Another consequence of Theorem 5.4 is the following result.

Theorem 5.8 (Syzygy theorem for a coherent valuation ring with nonzero zerodivisors and a divisibility test). Let M = H_{m}/U be a finitely presented R[\underline{X}]-module, where R is a coherent valuation ring with a divisibility test and nonzero zerodivisors. Assume that, w.r.t. some monomial order, LT(U) is finitely generated. Then M admits a resolution by finite free R[\underline{X}]-modules

⋯−→^{φ_{p+3}} F_{p} −→^{φ_{p+2}} F_{p} −→^{φ_{p+1}} F_{p} −→^{φ_{p}} F_{p−1} −→^{φ_{p−1}} ⋯−→^{φ_{2}} F_{1} −→^{φ_{1}} F_{0} −→^{φ_{0}} M −→ 0

such that for some p ≤ n + 1,

• LT(Ker(φ_{p})) = ⨁ _{j=1}^{m_{p}} ⟨b_{j}⟩ϵ_{j} with b_{1}, …, b_{m_{p}} ∈ R and (ϵ_{1}, …, ϵ_{m_{p}} ) a basis for F_{p},

• LT(Ker(φ_{p+2k−1} )) = ⨁ _{j=1}^{m_{p}} Ann(b_{j})ϵ_{j} for k ≥ 1,

• LT(Ker(φ_{p+2k} )) = ⨁ _{j=1}^{m_{p}} Ann(Ann(b_{j}))ϵ_{j} for k ≥ 1,

and at each step where indeterminates remain present, the considered monomial order is Schreyer’s monomial order (as in the proof of Theorem 5.5).

Proof. The part

F_{p} −→^{φ_{p}} F_{p−1} −→^{φ_{p−1}} ⋯−→^{φ_{2}} F_{1} −→^{φ_{1}} F_{0} −→^{φ_{0}} M −→ 0

of the free R[\underline{X}]-resolution with p ≤ n + 1 and LT(Ker(φ_{p})) = ⨁ _{j=1}^{m_{p}} ⟨b_{j}⟩ϵ_{j} follows from the proof of Theorem 5.5. W.l.o.g., the b_{j} ’s are ≠ 0. Let us denote by (g_{1}, …, g_{m_{p}} ) a Gröbner basis for Ker(φ_{p}) such that LT(g_{j}) = b_{j} ϵ_{j} for 1 ≤ j ≤ m_{p}. So S(g_{i}, g_{j}) = 0 for i < j. Thus the fact that LT(Ker(φ_{p+1} )) = ⨁ _{j=1}^{m_{p}} Ann(b_{j})ϵ_{j}, LT(Ker(φ_{p+2} )) = ⨁ _{j=1}^{m_{p}} Ann(Ann(b_{j}))ϵ_{j}, etc. follows immediately from Theorem 5.4. Finally, let us recall the equality Ann(Ann(Ann(I))) = Ann(I) for an ideal I.

Let us point out that this shows that the free resolution is in general not a finite one.

Corollary 5.9 (Syzygy theorem for a zero-dimensional coherent valuation ring with a divisibility test). Let M = H_{m}/U be a finitely presented R[\underline{X}]- module, where R is a zero-dimensional coherent valuation ring^{3} with a divisibility test. Then M admits a free R[\underline{X}]-resolution as described in Theorem 5.8.

Example 5.10. Let g_{1} = Y^{4} − Y, g_{2} = 2Y, g_{3} = X^{3} − 1 ∈ (ℤ/4ℤ)[X, Y], and let us use the lexicographic order >_{1} for which Y >_{1} X. We have

\begin{aligned}S(g_{1}, g_{1}) & = 0g_{1} = 0, & S(g_{1}, g_{2}) & = 2g_{1} − Y^{3}g_{2} = −2Y = −g_{2}, \\ S(g_{2}, g_{2}) & = 2g_{2} = 0, & S(g_{2}, g_{3}) & = X^{3}g_{2} − 2Y g_{3} = 2Y = g_{2}, \\ S(g_{3}, g_{3}) & = 0g_{3} = 0, & S(g_{1}, g_{3}) & = X^{3}g_{1} − Y^{4}g_{3} = Y^{4} − Y X^{3} = g_{1} − Y g_{3}. \end{aligned}

Thus (g_{1}, g_{2}, g_{3}) is a (pseudo-reduced) Gröbner basis for I = ⟨g_{1}, g_{2}, g_{3}⟩ and LT(I) = ⟨Y^{4}, 2Y, X^{3}⟩. By Theorem 5.4, u_{1,3} = (X^{3} − 1, 0, −Y^{4} + Y), u_{1,2} = (2, −Y^{3} + 1, 0), u_{2,3} = (0, X^{3} − 1, −2Y), u_{2,2} = (0, 2, 0) form a (pseudoreduced) Gröbner basis for the syzygy module Syz(g_{1}, g_{2}, g_{3}) w.r.t. Schreyer’s monomial order >_{2} induced by >_{1} and (g_{1}, g_{2}, g_{3}). In particular,

LT(Syz(g_{1}, g_{2}, g_{3})) = ⟨LT(u_{1,3}), …, LT(u_{2,2})⟩
= ⟨X^{3}ϵ_{1}, 2ϵ_{1}, X^{3}ϵ_{2}, 2ϵ_{2}⟩ = ⟨2, X^{3}⟩ϵ_{1} ⊕ ⟨2, X^{3}⟩ϵ_{2},

where (ϵ_{1}, ϵ_{2}, ϵ_{3}) stands for the canonical basis of (ℤ/4ℤ)[X, Y]^{3}. We have

\begin{aligned}S(u_{1,3}, u_{1,3}) & = 0u_{1,3} = 0, \\ S(u_{1,3}, u_{1,2}) & = 2u_{1,3} − X^{3}u_{1,2} \\ & = (−2, Y^{3}X^{3} − X^{3}, −2Y^{4} + 2Y) \\ & = −u_{1,2} + (Y^{3} − 1)u_{2,3}, \\ S(u_{1,3}, u_{2,3}) & = S(u_{1,3}, u_{2,2}) = 0, \\ S(u_{1,2}, u_{1,2}) & = 2u_{1,2} = (0, −2Y^{3} + 2, 0) \\ & = (−Y^{3} + 1)u_{2,2}, \end{aligned}  \begin{aligned}S(u_{1,2}, u_{2,3}) & = S(u_{1,2}, u_{2,2}) = 0, \\ S(u_{2,3}, u_{2,3}) & = 0u_{2,3} = 0, \\ S(u_{2,3}, u_{2,2}) & = 2u_{2,3} − X^{3}u_{2,2} \\ & = (0, −2, 0Y) \\ & = (0, −2, 0) \\ & = −u_{2,2}, \\ S(u_{2,2}, u_{2,2}) & = 2u_{2,2} = 0. \end{aligned}

We recover that (u_{1,3}, u_{1,2}, u_{2,3}, u_{2,2}) is a Gröbner basis for Syz(g_{1}, g_{2}, g_{3}). By Theorem 5.4, u_{1,3;1,2} = (2, −X^{3} + 1, −Y^{3} + 1, 0), u_{1,2;1,2} = (0, 2, 0, Y^{3} − 1), u_{2,3;2,2} = (0, 0, 2, −X^{3} + 1), u_{2,2;2,2} = (0, 0, 0, 2) form a (pseudo-reduced)

3Note that a zero-dimensional ring without nonzero zerodivisors is a discrete field.

Gröbner basis for the syzygy module Syz(u_{1,3}, u_{1,2}, u_{2,3}, u_{2,2}) w.r.t. Schreyer’s monomial order >_{3} induced by >_{2} and (u_{1,3}, u_{1,2}, u_{2,3}, u_{2,2}). In particular,

LT(Syz(u_{1,3}, u_{1,2}, u_{2,3}, u_{2,2})) = ⟨LT(u_{1,3;1,2} ), …, LT(u_{2,2;2,2} )⟩

= ⟨2ϵ′_{1}, …, 2ϵ′_{4}⟩ = ⟨2⟩ϵ′_{1} ⊕ ⟨2⟩ϵ′_{2} ⊕ ⟨2⟩ϵ′_{3} ⊕ ⟨2⟩ϵ′_{4},

where (ϵ′_{1}, …, ϵ′_{4}) stands for the canonical basis of (ℤ/4ℤ)[X, Y]^{4}. By Theorem 5.4, we find four vectors u_{(1,3;1,2),(1,3;1,2)} , …, u_{(2,2;2,2),(2,2;2,2)} ∈ (ℤ/4ℤ)[X, Y]^{4} forming a (pseudo-reduced) Gröbner basis for the syzygy module Syz(u_{1,3;1,2} , …, u_{2,2;2,2} ) w.r.t. Schreyer’s monomial order >_{4} induced by >_{3} and (u_{1,3;1,2} , …, u_{2,2;2,2} ). In particular,

LT(Syz(u_{1,3;1,2} , …, u_{2,2;2,2} )) = ⟨LT(u_{(1,3;1,2),(1,3;1,2)} ), …, LT(u_{(2,2;2,2),(2,2;2,2)} )⟩
= ⟨2⟩ϵ′_{1} ⊕ ⟨2⟩ϵ′_{2} ⊕ ⟨2⟩ϵ′_{3} ⊕ ⟨2⟩ϵ′_{4},

etc. We conclude that I admits the free (ℤ/4ℤ)[X, Y]-resolution

⋯−→^{φ_{3}} (ℤ/4ℤ)[X, Y]^{4} −→^{φ_{2}} (ℤ/4ℤ)[X, Y]^{4} −→^{φ_{1}} (ℤ/4ℤ)[X, Y]^{3} −→^{φ_{0}} I −→ 0

such that LT(Ker(φ_{i})) = ⟨2⟩ϵ′_{1} ⊕ ⟨2⟩ϵ′_{2} ⊕ ⟨2⟩ϵ′_{3} ⊕ ⟨2⟩ϵ′_{4} for i ≥ 1.

6 The syzygy theorem and Schreyer’s algorithm for a Bézout ring

As explained in the proof of Theorem 4.6, one can avoid branching when computing a dynamical Gröbner basis (see [10, 16, 19]) for a Bézout domain of Krull dimension ≤ 1 (e.g. ℤ and the ring of all algebraic integers—note that the last one is not a PID) or a zero-dimensional coherent Bézout ring. Note that this is not possible for Prüfer domains of Krull dimension ≤ 1 which are not Bézout domains (e.g. ℤ[\sqrt{−5} ], see [10, Section 4]).

Let us now generalise the results of Section 5 to the case of coherent strict Bézout rings.

Theorem 6.1 (Schreyer’s algorithm for Bézout rings). We consider a coherent strict Bézout ring R with a divisibility test. Let U be a submodule of H_{m} with Gröbner basis (g_{1}, …, g_{p}). Then the relations u_{i,j} computed by Algorithm 2.8 form a Gröbner basis for the syzygy module Syz(g_{1}, …, g_{p}) w.r.t. Schreyer’s monomial order induced by > and (g_{1}, …, g_{p}).

Proof. This follows directly from the local case given by Theorem 5.4: see the proof of Theorem 4.6 for an explanation.

Theorem 6.2 (Syzygy theorem for a Bézout domain with a divisibility test). Let M = H_{m}/U be a finitely presented R[\underline{X}]-module, where R is a Bézout domain with a divisibility test. Assume that, w.r.t. some monomial order, LT(U) is finitely generated. Then M admits a finite free R[\underline{X}]-resolution

0 → F_{p} → F_{p−1} → ⋯→ F_{1} → F_{0} → M → 0

of length p ≤ n + 1.

Proof. This follows directly from the local case.

Corollary 6.3 (Syzygy theorem for a one-dimensional Bézout domain with a divisibility test). Let M = H_{m}/U be a finitely presented R[\underline{X}]-module, where R is a Bézout domain of Krull dimension ≤ 1 with a divisibility test. Then M admits a finite free R[\underline{X}]-resolution

0 → F_{p} → F_{p−1} → ⋯→ F_{1} → F_{0} → M → 0

of length p ≤ n + 1.

Let us now treat the case of zero-dimensional coherent Bézout rings.

Theorem 6.4 (Syzygy theorem for a zero-dimensional Bézout ring with a divisibility test). Let M = H_{m}/U be a finitely presented R[\underline{X}]-module, where R is a coherent zero-dimensional Bézout ring with a divisibility test. Then M admits a free R[\underline{X}]-resolution

⋯−→^{φ_{p+3}} F_{p} −→^{φ_{p+2}} F_{p} −→^{φ_{p+1}} F_{p} −→^{φ_{p}} F_{p−1} −→^{φ_{p−1}} ⋯−→^{φ_{2}} F_{1} −→^{φ_{1}} F_{0} −→^{φ_{0}} M −→ 0

such that for some p ≤ n + 1,

• LT(Ker(φ_{p})) = ⨁ _{j=1}^{m_{p}} ⟨b_{j}⟩ϵ_{j} with b_{1}, …, b_{m_{p}} ∈ R and (ϵ_{1}, …, ϵ_{m_{p}} ) a basis for F_{p},

• LT(Ker(φ_{p+2k−1} )) = ⨁ _{j=1}^{m_{p}} Ann(b_{j})ϵ_{j} for k ≥ 1,

• LT(Ker(φ_{p+2k} )) = ⨁ _{j=1}^{m_{p}} Ann(Ann(b_{j}))ϵ_{j} for k ≥ 1,

and at each step where indeterminates remain present, the considered monomial order is Schreyer’s monomial order.

Proof. This follows directly from the local case.

The case of the integers

The following theorems are particular cases of Theorem 6.1 and Corollary 6.3 for R = ℤ.

Theorem 6.5 (Schreyer’s algorithm for R = ℤ). Let U be a submodule of H_{m} with Gröbner basis (g_{1}, …, g_{p}). Then the relations u_{i,j} computed by Algorithm 2.8 form a Gröbner basis for the syzygy module Syz(g_{1}, …, g_{p}) w.r.t. Schreyer’s monomial order induced by > and (g_{1}, …, g_{p}). Moreover, for 1 ≤ i < j ≤ p such that LPos(g_{i}) = LPos(g_{j}), we have

LT(u_{i,j} ) = \frac{LC(g_{j} )}{gcd (LC(g_{i} ),LC(g_{j} ))} \underline{X}^{(mdeg (g_{j} )−mdeg (g_{i} ))^{+}} ϵ_{i}.

Theorem 6.6 (Syzygy theorem for R = ℤ). Let M be a finitely generated ℤ[\underline{X}]-module. Then M admits a finite free ℤ[\underline{X}]-resolution

0 → F_{p} → F_{p−1} → ⋯→ F_{1} → F_{0} → M → 0

of length p ≤ n + 1.

Example 6.7. Let g_{1} = Y^{2} − X + 3, g_{2} = 4X^{2} − 4, g_{3} = 6X + 6 ∈ ℤ[X, Y], and let us use the lexicographic order >_{1} for which Y >_{1} X. We have:

\begin{aligned}S(g_{1}, g_{2}) & = 4X^{2}g_{1} − Y^{2}g_{2} = 4g_{1} + (−X + 3)g_{2}, \\ S(g_{1}, g_{3}) & = 6Xg_{1} − Y^{2}g_{3} = −6g_{1} + (−X + 3)g_{3}, \\ S(g_{2}, g_{3}) & = 3g_{2} − 2Xg_{3} = −2g_{3}. \end{aligned}

Thus (g_{1}, g_{2}, g_{3}) is a Gröbner basis for I = ⟨g_{1}, g_{2}, g_{3}⟩ and LT(I) = ⟨Y^{2}, 4X^{2}, 6X⟩. By Theorem 6.5, u_{1,2} = (4X^{2} − 4, −Y^{2} + X − 3, 0), u_{1,3} = (6X + 6, 0, −Y^{2} + X − 3), u_{2,3} = (0, 3, −2X + 2) form a Gröbner basis for the syzygy module Syz(g_{1}, g_{2}, g_{3}) w.r.t. Schreyer’s monomial order >_{2} induced by >_{1} and (g_{1}, g_{2}, g_{3}). In particular,

LT(Syz(g_{1}, g_{2}, g_{3})) = ⟨LT(u_{1,2}), LT(u_{1,3}), LT(u_{2,3})⟩ = ⟨4X^{2}ϵ_{1}, 6Xϵ_{1}, 3ϵ_{2}⟩

= ⟨4X^{2}, 6X ⟩ϵ_{1} ⊕ ⟨3⟩ϵ_{2} = 2⟨2X^{2}, 3X ⟩ϵ_{1} ⊕ ⟨3⟩ϵ_{2} = 2⟨X^{2}, 3X ⟩ϵ_{1} ⊕ ⟨3⟩ϵ_{2},

where (ϵ_{1}, ϵ_{2}, ϵ_{3}) stands for the canonical basis of ℤ[X, Y]^{3}. Thus

u′_{1,2} = Xu_{1,3} − u_{1,2} = (2X^{2} + 6X + 4 , Y^{2} − X + 3 , −Y^{2}X + X^{2} − 3X ), u_{1,3}, u_{2,3}

form a reduced Gröbner basis for Syz(g_{1}, g_{2}, g_{3}). We have:

\begin{aligned}S(u′_{1,2}, u_{1,3}) & = 3u′_{1,2} − Xu_{1,3} = 2u_{1,3} + (Y^{2} − X + 3)u_{2,3}, \\ S(u′_{1,2}, u_{2,3}) & = S(u_{1,3}, u_{2,3}) = 0. \end{aligned}

We recover that (u′_{1,2}, u_{1,3}, u_{2,3}) is a Gröbner basis for Syz(g_{1}, g_{2}, g_{3}). By Theorem 6.5, u_{1,2;1,3} = (3, −X − 2, −Y^{2} + X − 3) forms a (pseudo-reduced) Gröbner basis for the syzygy module Syz(u′_{1,2}, u_{1,3}, u_{2,3}) w.r.t. Schreyer’s monomial order >_{3} induced by >_{2} and (u′_{1,2}, u_{1,3}, u_{2,3}). In particular, LT(Syz(u′_{1,2}, u_{1,3}, u_{2,3})) = ⟨LT(u_{1,2;1,3} )⟩ = ⟨3⟩ϵ′_{1} where (ϵ′_{1}, ϵ′_{2}, ϵ′_{3}) stands for the canonical basis of ℤ[X, Y]^{3}. It follows that Syz(u′_{1,2}, u_{1,3}, u_{2,3}) is free. We conclude that I admits the following length-2 free ℤ[X, Y]-resolution:

0 → ℤ[X, Y] −−−−→^{u_{1,2;1,3}} ℤ[X, Y]^{3} \underrightarrow{( \begin{matrix}u′_{1,2} \\ u_{1,3} \\ u_{2,3} \end{matrix} )} ℤ[X, Y]^{3} \underrightarrow{( \begin{matrix}g_{1} \\ g_{2} \\ g_{3} \end{matrix} )} I → 0.

The case of ℤ/Nℤ

The elements of ℤ/Nℤ are simply written as integers (their representatives in [[0, N − 1]]). When talking about the gcd of two nonzero elements in ℤ/Nℤ we mean the gcd of their representatives in [[1, N − 1]]. For a nonzero element

a in ℤ/Nℤ, letting b = gcd(N, a), the class of \frac{N}{b} in ℤ/Nℤ will be denoted by ann(a); it generates Ann(a).

• The Division algorithm 2.3 attains its goal: the gcd and the Bézout identity to be found in line 7 will be computed by finding d, b, b_{i} (i ∈ D) in ℤ such that d = gcd(N, gcd{ LC(h_{i}) ; i ∈ D }) = bN + ∑ _{i∈D} b_{i} LC(h_{i}); the euclidean division in line 7 will be performed in ℤ;

• The S-polynomial algorithm 2.4 attains its goal: note that in this case, the generator of the annihilator of LC(f) to be found on line 3 may be taken to be ann(LC(f)), so that the auto-S-polynomial of f is

S(f, f) = ann(LC(f))f;

• Buchberger’s algorithm 2.5 attains its goal.

The following theorems are particular cases of Theorems 6.1 and 6.4 for R = ℤ/Nℤ.

Theorem 6.8 (Schreyer’s algorithm for R = ℤ/Nℤ). Let U be a submodule of H_{m} with Gröbner basis (g_{1}, …, g_{p}). Then the relations u_{i,j} computed by Algorithm 2.8 form a Gröbner basis for the syzygy module Syz(g_{1}, …, g_{p}) w.r.t. Schreyer’s monomial order induced by > and (g_{1}, …, g_{p}). Moreover, for all 1 ≤ i ≤ j ≤ p such that LPos(g_{i}) = LPos(g_{j}), we have

LT(u_{i,j} ) = \{ \begin{matrix}ann(LC(g_{i}))ϵ_{i} & if i = j, \\ \frac{LC(g_{j} )}{gcd (LC(g_{i} ),LC(g_{j} ))} \underline{X}^{(mdeg (g_{j} )−mdeg (g_{i} ))^{+}} ϵ_{i} & otherwise. \end{matrix}

28 Theorem 6.9 (Syzygy theorem for R = ℤ/Nℤ). Let M be a finitely presented (ℤ/Nℤ)[\underline{X}]-module. Then M admits a free (ℤ/Nℤ)[\underline{X}]-resolution

⋯−→^{φ_{p+3}} F_{p} −→^{φ_{p+2}} F_{p} −→^{φ_{p+1}} F_{p} −→^{φ_{p}} F_{p−1} −→^{φ_{p−1}} ⋯−→^{φ_{2}} F_{1} −→^{φ_{1}} F_{0} −→^{φ_{0}} M −→ 0

such that for some p ≤ n + 1,

LT(Ker(φ_{p})) = ⨁_{j=1}^{m_{p}} ⟨b_{j}⟩ϵ_{j}, LT(Ker(φ_{p+1} )) = ⨁_{j=1}^{m_{p}} \frac{N}{gcd(N, b_{j})}ϵ_{j},

LT(Ker(φ_{p+2} )) = ⨁_{j=1}^{m_{p}} ⟨b_{j}⟩ϵ_{j}, LT(Ker(φ_{p+3} )) = ⨁_{j=1}^{m_{p}} \frac{N}{gcd(N, b_{j})}ϵ_{j}, etc.,

where (ϵ_{1}, …, ϵ_{m_{p}} ) is a basis for F_{p}, b_{1}, …, b_{m_{p}} ∈ ℤ/Nℤ, and the considered monomial order is Schreyer’s monomial order.

Example 6.10. Let g_{1} = Y + 1, g_{2} = X^{3} + X^{2} + 6, g_{3} = 3X^{2}, g_{4} = 9 in (ℤ/12ℤ)[X, Y], and let us use the lexicographic order >_{1} for which Y >_{1} X. We have

\begin{aligned}S(g_{1}, g_{1}) & = 0g_{1} = 0, \\ S(g_{1}, g_{2}) & = X^{3}g_{1} − Y g_{2} = (−X^{2} − 6)g_{1} + g_{2}, \\ S(g_{1}, g_{3}) & = 3X^{2}g_{1} − Y g_{3} = g_{3}, \\ S(g_{1}, g_{4}) & = 9g_{1} − Y g_{4} = g_{4}, \\ S(g_{2}, g_{2}) & = 0g_{2} = 0, \end{aligned} \begin{aligned}S(g_{2}, g_{3}) & = 3g_{2} − Xg_{3} = g_{3} + 2g_{4}, \\ S(g_{2}, g_{4}) & = 9g_{2} − X^{3}g_{3} = (X^{2} + 6)g_{4}, \\ S(g_{3}, g_{3}) & = 4g_{3} = 0, \\ S(g_{3}, g_{4}) & = 3g_{3} − X^{2}g_{4} = 0, \\ S(g_{4}, g_{4}) & = 4g_{4} = 0. \end{aligned}

Thus (g_{1}, g_{2}, g_{3}, g_{4}) is a (pseudo-reduced) Gröbner basis for I = ⟨g_{1}, g_{2}, g_{3}, g_{4}⟩ and LT(I) = ⟨Y, X^{3}, 3X^{2}, 9⟩. By Theorem 6.8, u_{1,2} = (X^{3} + X^{2} + 6, −Y − 1, 0, 0), u_{1,3} = (3X^{2}, 0, −Y − 1, 0), u_{1,4} = (9, 0, 0, −Y − 1), u_{2,3} = (0, 3, −X − 1, −2), u_{2,4} = (0, 9, −X^{3}, −X^{2} − 6), u_{3,3} = (0, 0, 4, 0), u_{3,4} = (0, 0, 3, −X^{2}), u_{4,4} = (0, 0, 0, 4) form a Gröbner basis for the syzygy module Syz(g_{1}, g_{2}, g_{3}, g_{4}) w.r.t. Schreyer’s monomial order >_{2} induced by >_{1} and (g_{1}, g_{2}, g_{3}, g_{4}). In particular,

LT(Syz(g_{1}, g_{2}, g_{3}, g_{4}))= ⟨LT(u_{1,2}), …, LT(u_{4,4})⟩
= ⟨X^{3}, 3X^{2}, 9⟩ϵ_{1} ⊕ ⟨3, 9⟩ϵ_{2} ⊕ ⟨4, 3⟩ϵ_{3} ⊕ ⟨4⟩ϵ_{4}
= ⟨X^{3}, 3⟩ϵ_{1} ⊕ ⟨3⟩ϵ_{2} ⊕ ⟨1⟩ϵ_{3} ⊕ ⟨4⟩ϵ_{4},

where (ϵ_{1}, ϵ_{2}, ϵ_{3}, ϵ_{4}) stands for the canonical basis of (ℤ/12ℤ)[X, Y]^{4}. Thus u_{1,2}, u′_{1,4} = −u_{1,4} = (3, 0, 0, Y + 1), u_{2,3}, u′_{3,3} = u_{3,3} − u_{3,4} = (0, 0, 1, X^{2}), u_{4,4} form a reduced Gröbner basis for Syz(g_{1}, g_{2}, g_{3}, g_{4}). We have

S(u_{1,2}, u′_{1,4}) = 3u_{1,2} − X^{3}u′_{1,4}

= \begin{matrix}(X^{2} + 2)u′_{1,4} + (3Y + 3)u_{2,3} + (3Y X + 3Y + 3X + 3)u′_{3,3} \\ +(2Y X^{3} + 2Y X^{2} + 2X^{3} + 2X^{2} + Y + 1)u_{4,4}, \end{matrix}

S(u′_{1,4}, u′_{1,4}) = 4u′_{1,4} = (Y + 1)u_{4,4},
S(u_{2,3}, u_{2,3}) = 4u_{2,3} = (8X + 8)u′_{3,3} + (X^{3} + X^{2} + 1)u_{4,4},
S(u_{4,4}, u_{4,4}) = 3u_{4,4} = 0.

By Theorem 6.8, the elements u_{1,2;1,4} = (3, −X^{3} − X^{2} − 2, −3Y − 3 , −3Y X − 3Y − 3X − 3, −2Y X^{3} − 2Y X^{2} − Y − 2X^{3} − 2X^{2} − 1), u_{1,4;1,4} = (0, 4, 0, 0, −Y − 1), u_{2,3;2,3} = (0, 0, 4, −8X − 8 , −X^{3} − X^{2} − 1), u_{4,4;4,4} = (0, 0, 0, 0, 3) form a (pseudo-reduced) Gröbner basis for the syzygy module Syz(u_{1,2}, u′_{1,4}, u_{2,3}, u′_{3,3}, u_{4,4}) w.r.t. Schreyer’s monomial order >_{3} induced by >_{2} and (u_{1,2}, u′_{1,4}, u_{2,3}, u′_{3,3}, u_{4,4}). In particular, LT(Syz(u_{1,2}, u′_{1,4}, u_{2,3}, u′_{3,3}, u_{4,4})) = ⟨3⟩ϵ′_{1} ⊕ ⟨4⟩ϵ′_{2} ⊕ ⟨4⟩ϵ′_{3} ⊕ ⟨3⟩ϵ′_{5}, where (ϵ′_{1}, …, ϵ′_{5}) stands for the canonical basis of (ℤ/12ℤ)[X, Y]^{5}.

We conclude that I admits the free R[X, Y]-resolution (R = ℤ/12ℤ)

⋯−→^{φ_{4}} R[X, Y]^{4} −→^{φ_{3}} R[X, Y]^{4} −→^{φ_{2}} R[X, Y]^{5} −→^{φ_{1}} R[X, Y]^{4} −→^{φ_{0}} I → 0

with LT(Ker(φ_{2i})) = ⟨4⟩ϵ′′_{1}⊕ ⟨3⟩ϵ′′_{2}⊕ ⟨3⟩ϵ′′_{3}⊕ ⟨4⟩ϵ′′_{4} and LT(Ker(φ_{2i+1} )) = ⟨3⟩ϵ′′_{1}⊕ ⟨4⟩ϵ′′_{2}⊕ ⟨4⟩ϵ′′_{3}⊕ ⟨3⟩ϵ′′_{4} for i ≥ 1, where (ϵ′′_{1}, …, ϵ′′_{4}) stands for the canonical basis of R[X, Y]^{4}.

References

[1] William W. Adams and Philippe Loustaunau. An introduction to Gröbner bases, Graduate Studies in Mathematics, vol. 3. American Mathematical Society, Providence, 1994. doi:10.1090/gsm/003. (p. 4)

[2] Errett Bishop. Foundations of constructive analysis. McGraw-Hill, New York, 1967. (p. 2)

[3] Errett Bishop and Douglas Bridges. Constructive analysis, Grundlehren der mathematischen Wissenschaften, vol. 279. Springer, Berlin, 1985. doi:10.1007/978-3-642-61667-9. (p. 2)

[4] Bruno Buchberger. Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal.

Ph.D. thesis, Mathematisches Institut, Universität Innsbruck, 1965. Translation by Michael P. Abramson: An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal, J. Symbolic Comput., 41(3–4):475–511, 2006. . (p. 8)

[5] David A. Cox, John Little, and Donal O’Shea. Using algebraic geometry, Graduate Texts in Mathematics, vol. 185. Springer, New York, second ed., 2005. doi:10.1007/b138611. (p. 4)

[6] David A. Cox, John Little, and Donal O’Shea. Ideals, varieties, and algorithms: an introduction to computational algebraic geometry and commutative algebra. Undergraduate Texts in Mathematics, Springer, Cham, fourth ed., 2015. doi:10.1007/978-3-319-16721-3. (p. 14)

[7] Gema-Maria Díaz-Toca, Henri Lombardi, and Claude Quitté. Modules sur les anneaux commutatifs: cours et exercices. Calvage & Mounet, Paris, 2014. (p. 4)

[8] Viviana Ene and Jürgen Herzog. Gröbner bases in commutative algebra, Graduate Studies in Mathematics, vol. 130. American Mathematical Society, Providence, 2012. (pp. 6, 19, 20, and 21)

[9] Maroua Gamanda and Ihsen Yengui. Noether normalization theorem and dynamical Gröbner bases over Bezout domains of Krull dimension 1. J. Algebra, 492, 52–56, 2017. doi:10.1016/j.jalgebra.2017.09.002. (p. 16)

[10] Amina Hadj Kacem and Ihsen Yengui. Dynamical Gröbner bases over Dedekind rings. J. Algebra, 324(1), 12–24, 2010. doi:10.1016/j.jalgebra.2010.04.014. (pp. 2, 11, and 25)

[11] Henri Lombardi and Claude Quitté. Commutative algebra: constructive methods. Finite projective modules, Algebra and Applications, vol. 20. Springer, Dordrecht, 2015. doi:10.1007/978-94-017-9944-7. Translated from the French (Calvage & Mounet, Paris, 2011, revised and extended by the authors) by Tania K. Roblot. (pp. 2, 4, and 12)

[12] Ray Mines, Fred Richman, and Wim Ruitenburg. A course in constructive algebra. Universitext, Springer, New York, 1988. doi:10.1007/978-1-4419-8640-5. (p. 2)

[13] Samiha Monceur and Ihsen Yengui. On the leading terms ideals of polynomial ideals over a valuation ring. J. Algebra, 351, 382–389, 2012. doi:10.1016/j.jalgebra.2011.11.015. (p. 2)

[14] László Rédei. Ein kombinatorischer Satz. Acta Sci. Math. (Szeged), 7,

    39–43, 1934–1935. http://acta.bibl.u-szeged.hu/13432. (p. 14)

[15] Frank-Olaf Schreyer. Die Berechnung von Syzygien mit dem verallgemeinerten Weierstraßschen Divisionssatz und eine Anwendung auf analytische Cohen-Macaulay Stellenalgebren minimaler Multiplizität. Master’s thesis, Universität Hamburg, 1980. (p. 20)

[16] Ihsen Yengui. Dynamical Gröbner bases. J. Algebra, 301(2), 447–458, 2006. doi:10.1016/j.jalgebra.2006.01.051. (pp. 2, 11, and 25)

[17] Ihsen Yengui. Corrigendum to “Dynamical Gröbner bases” and to “Dynamical Gröbner bases over Dedekind rings”. J. Algebra, 339(1), 370–375, 2011. doi:10.1016/j.jalgebra.2011.05.004. (p. 11)

[18] Ihsen Yengui. The Gröbner ring conjecture in the lexicographic order case. Math. Z., 276(1–2), 261–265, 2014. doi:10.1007/s00209-013-1197-y. (pp. 2 and 17)

[19] Ihsen Yengui. Constructive commutative algebra: projective modules over polynomial rings and dynamical Gröbner bases, Lecture Notes in Mathematics, vol. 2138. Springer, Cham, 2015. doi:10.1007/978-3-319-19494-3. (pp. 2, 4, 7, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, and 25)