# Generalised Buchberger and Schreyer algorithms for strongly discrete coherent rings

Henri Lombardi*, Stefan Neuwirth*, and Ihsen Yengui**

*Université de Franche-Comté, CNRS, UMR 6623, LmB, 25000 Besançon, France, henri.lombardi@univ-fcomte.fr, stefan.neuwirth@univ-fcomte.fr.

**Département de mathématiques, Faculté des sciences, Université de Sfax, 3000 Sfax, Tunisia, ihsen.yengui@fss.rnu.tn.

## Abstract

Let $M$ be a finitely generated submodule of a free module over a multivariate polynomial ring with coefficients in a discrete coherent ring. We prove that its module $MLT(M)$ of leading terms is countably generated and provide an algorithm for computing explicitly a generating set. This result is also useful when $MLT(M)$ is not finitely generated.

Suppose that the base ring is strongly discrete coherent. We provide a Buchberger-like algorithm and prove that it converges if, and only if, the module of leading terms is finitely generated. We also provide a constructive version of Hilbert's syzygy theorem by following Schreyer's method.

MSC 2020: 13D02, 13P10, 13C10, 13P20, 14Q20.

Keywords: Generalised Buchberger algorithm, syzygy theorem, free resolution, monomial order, Schreyer's monomial order, Schreyer's syzygy algorithm.

## Contents

<table><tr><td>1</td><td>Introduction</td><td>2</td></tr><tr><td>2</td><td>Constructive definitions and contexts</td><td>3</td></tr><tr><td>3</td><td>Gröbner bases for modules over a discrete ring</td><td>4</td></tr><tr><td>4</td><td>Syzygies in a polynomial ring over a discrete coherent ring</td><td>7</td></tr><tr><td></td><td>Syzygies of terms, examples in the case of an ideal</td><td>9</td></tr><tr><td></td><td>S-lists and iterated S-lists, a fundamental theorem</td><td>10</td></tr></table>
<table><tr><td>5 Basic algorithms</td><td>12</td></tr><tr><td>The division algorithm</td><td>12</td></tr><tr><td>Syzygy algorithms</td><td>13</td></tr><tr><td>S-list algorithms</td><td>15</td></tr><tr><td>Rewriting algorithms</td><td>16</td></tr></table>

<table><tr><td>6 Buchberger's algorithm</td><td>17</td></tr></table>

<table><tr><td>7 Schreyer's syzygy algorithm</td><td>18</td></tr></table>

<table><tr><td>References</td><td>20</td></tr></table>

# 1 Introduction

This paper is written in Bishop's style of constructive mathematics (see Bishop 1967, Bishop and Bridges 1985, Mines, Richman, and Ruitenburg 1988, Lombardi and Quitté 2015, Yengui 2015). It can be seen as a sequel to the paper Gamanda, Lombardi, Neuwirth, and Yengui 2020 (see also Hadj Kacem and Yengui 2010, Yengui 2006). It generalises results in Adams and Loustaunau 1994 to suitable nonnoetherian contexts.

Our general context is the following.

**General context 1.1.** In this article, $\mathbf{R}$ is a commutative ring with unit, $X_1, \dots, X_n$ are $n$ indeterminates ($n \ge 1$), $\mathbf{R}[\mathbf{X}] = \mathbf{R}[X_1, \dots, X_n]$, $\mathbf{H}_n^m = \mathbf{R}[\mathbf{X}]^m$ is a free $\mathbf{R}[\mathbf{X}]$-module with basis $(e_1, \dots, e_m)$ ($m \ge 1$), and $>$ is a monomial order on $\mathbf{H}_n^m$ (see Definition 3.1). The case of an ideal in $\mathbf{R}[\mathbf{X}]$ is addressed by considering $m = 1$: $\mathbf{H}_n^1 = \mathbf{R}[\mathbf{X}]$ and $e_1$ is the unit of $\mathbf{R}$.

We shall need to qualify this context by suitable hypotheses of coherence and discreteness (see Definition 2.1). Let us consider a finitely generated submodule $M$ of $\mathbf{H}_n^m$ and its module MLT($M$) of leading terms with respect to our monomial order.

Our first Fundamental theorem 4.11 states that MLT($M$) is countably generated and provides an algorithm for computing explicitly a generating set. This result is also useful when MLT($M$) is not finitely generated.

The second Fundamental theorem 6.1 indicates a precise context in which the (generalised) Buchberger criterion applies and Buchberger's algorithm computes a Gröbner basis for $M$.

The third Fundamental theorem 7.4 indicates a precise context in which the (generalised) Schreyer method computes a finite free resolution for $M$.

These are central problems since polynomials or vectors of polynomials always admit nontrivial algebraic relations and such computations are a basic step, for instance, for computing resolutions of modules.

The main results of the paper are two generalisations of classical theorems/algorithms, Buchberger's algorithm for the computation of a Gröbner basis and
Schreyer's algorithm for the computation of a Gröbner bases of the first syzygy module. The generalisations are given for so-called strongly-discrete coherent rings, namely rings with membership test for finitely generated ideals and with finitely generated syzygy modules.

An important aspect of extending classical theorems in the theory of Gröbner bases from polynomial rings over fields to polynomial rings over more general algebraic structures is the emergence of more elementary arguments.

## 2 Constructive definitions and contexts

We start with recalling the following constructive definitions.

### Definition 2.1.

* The ring $\mathbb{R}$ is discrete if it is equipped with a zero test: equality is decidable.

* Let $U$ be an $\mathbb{R}$-module. The syzygy module of an $n$-tuple $(v_1, \dots, v_n) \in U^n$ is

$$ \mathrm{Syz}(v_1, \dots, v_n) := \{ (b_1, \dots, b_n) \in \mathbb{R}^{1 \times n} ; b_1 v_1 + \dots + b_n v_n = 0 \}. $$

The syzygy module of a 1-tuple $v$ is the annihilator $\mathrm{Ann}(v)$ of $v$.

* An $\mathbb{R}$-module $U$ is coherent if the syzygy module of every $n$-tuple of elements of $U$ is finitely generated, 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. The ring $\mathbb{R}$ is coherent if it is coherent as an $\mathbb{R}$-module. It is well-known that a module is coherent if, and only if, 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.

* A ring is strongly discrete if it is equipped with a membership test for finitely generated ideals, i.e. if, given $a, b_1, \dots, b_n \in \mathbb{R}$, one can answer the question $a \in? \langle b_1, \dots, b_n \rangle$ and, in the case of a positive answer, one can explicitly provide $c_1, \dots, c_n \in \mathbb{R}$ such that $a = b_1 c_1 + \dots + b_n c_n$.

* $\mathbb{R}$ is a Bézout ring if every finitely generated ideal is principal, i.e. of the form $\langle a \rangle = \mathbb{R}a$ with $a \in \mathbb{R}$. A Bézout ring is strongly discrete if, and only if, it is equipped with a divisibility test; it is coherent if, and only if, the annihilator of any element is principal. To be a valuation ring (in the Kaplansky sense) is to be a Bézout local ring (see Lombardi and Quitté 2015, Lemma IV-7.1).

* A Bézout ring $\mathbb{R}$ is strict if for all $b_1, b_2 \in \mathbb{R}$ we can find $d, b'_1, b'_2, c_1, c_2 \in \mathbb{R}$ such that $b_1 = db'_1, b_2 = db'_2$, and $c_1b'_1 + c_2b'_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 Lombardi and Quitté 2015, 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 Díaz-Toca, Lombardi, and Quitté 2014, Exercise XVI-9 p. 355, solution p. 526, and Lombardi and Quitté 2015, Exercise IV-8 pp. 221-222, solution p. 228).

We shall consider three contexts that are more specific than General context 1.1.

**Discrete coherent context 2.2.** General context 1.1 with $\mathbf{R}$ discrete and coherent.

**Simple division context 2.3.** General context 1.1 with $\mathbf{R}$ strongly discrete.

*Remark 2.4.* We could have considered a “Division with remainder context” in which we would assume moreover that we have a partial preorder $\leq_R$ on elements of $\mathbf{R}$ (with $a \leq_R b$ if $a = b$) and a generalised division algorithm *Rem* for $\mathbf{R}$ which computes, for given $c, c_1, \dots, c_k \in \mathbf{R}$, a remainder $r_0 = c - a_1c_1 - \dots - a_kc_k$ satisfying $r_0 = 0$ if, and only if, $c \in (c_1, \dots, c_k)$, and $r_0, a_1c_1, \dots, a_kc_k \leq_R c$ otherwise. Simple division context 2.3 might be seen as the particular case where $\leq_R$ is equality and *Rem* returns $c$ if $c \notin (c_1, \dots, c_k)$.

**Strongly discrete coherent context 2.5.** General context 1.1 with $\mathbf{R}$ strongly discrete and coherent.

### 3 Gröbner bases for modules over a discrete ring

**Definition 3.1** (Monomial orders on finite-rank free $\mathbf{R}[\mathbf{X}]$-modules, see Adams and Loustaunau 1994, Cox, Little, and O’Shea 2005, Yengui 2021b, General context 1.1).

(1) Monomials, terms.

• A monomial in $\mathbf{H}_n^m$ is a vector of the form $M = \mathbf{X}^\alpha e_i$ ($1 \leq i \leq m$), where $\mathbf{X}^\alpha = X_1^{\alpha_1} \cdots X_n^{\alpha_n}$ is a monomial in $\mathbf{R}[\mathbf{X}]$; the index $i$ is the position of the monomial. The set of monomials in $\mathbf{H}_n^m$ is denoted by $\mathbb{M}_n^m$, with $\mathbb{M}_1^1 \cong \mathbb{M}_n$ (the set of monomials in $\mathbf{R}[\mathbf{X}$]). For example, $X_1X_2^3e_2$ is a monomial in $\mathbf{H}_n^m$, but $2X_1e_3$, $(X_1+X_2^3)e_2$, and $X_1e_2+X_1e_3$ are not.

• If $M = \mathbf{X}^\alpha e_i$ and $N = \mathbf{X}^\beta e_j$, we say that $M$ divides $N$ if $i = j$ and $\mathbf{X}^\alpha$ divides $\mathbf{X}^\beta$. For example, $X_1e_1$ divides $X_1X_2e_1$, but does not divide $X_1X_2e_2$. Note that in the case that $M$ divides $N$, there exists a monomial $\mathbf{X}^\gamma$ in $\mathbb{M}_n$ such that $N = \mathbf{X}^\gamma M$: in this case we define $N/M := \mathbf{X}^\gamma$; for example, $(X_1X_2e_1)/(X_1e_1) = X_2$.

• A term in $\mathbf{H}_n^m$ is a vector of the form $cM$, where $c \in \mathbf{R} \setminus \{0\}$ and $M \in \mathbb{M}_n^m$. We say that a term $cM$ divides a term $c'M'$, with $c, c' \in \mathbf{R} \setminus \{0\}$ and $M, M' \in \mathbb{M}_n^m$, if $c$ divides $c'$ and $M$ divides $M'$.

(2) A monomial order on $\mathbf{H}_n^m$ is a relation $>_{\mathbf{H}_n^m}$ such that
• > is a total order on $\mathbb{M}_n^m$;

• $\underline{X}^\alpha M > M$ for all $M \in \mathbb{M}_n^m$ and $\underline{X}^\alpha \in \mathbb{M}_n \setminus \{1\}$;

• $M > N \implies \underline{X}^\alpha M > \underline{X}^\alpha N$ for all $M, N \in \mathbb{M}_n^m$ and $\underline{X}^\alpha \in \mathbb{M}_n$.

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

(3) Let the ring $\mathbb{R}$ be discrete. Any nonzero vector $u \in \mathbb{H}_n^m$ can be written as a sum of terms

$$u = c_t M_t + c_{t-1} M_{t-1} + \cdots + c_1 M_1$$

with $c_1, \dots, c_t \in \mathbb{R} \setminus \{0\}, M_1, \dots, M_t \in \mathbb{M}_n^m$, and $M_t > M_{t-1} > \cdots > M_1$.

• We define the *leading coefficient*, *leading monomial*, and *leading term* of $u$ as in the ring case: $\mathrm{LC}(u) = c_t$, $\mathrm{LM}(u) = M_t$, $\mathrm{LT}(u) = \mathrm{LC}(u) \mathrm{LM}(u)$.

• Letting $M_t = \underline{X}^\alpha e_\ell$ with $\underline{X}^\alpha \in \mathbb{M}_n$ and $1 \le \ell \le m$, we say that $\alpha$ is the *multidegree of* $u$ and write $\mathrm{mdeg}(u) = \alpha$, and that the index $\ell$ is the *leading position* of $u$, and write $\mathrm{LPos}(u) = \ell$.

• We stipulate that $\mathrm{LC}(0) = 0$, $\mathrm{LM}(0) = 0$, and $\mathrm{mdeg}(0) = -\infty$, but we do not define $\mathrm{LPos}(0)$.

(4) A monomial order on $\mathbb{R}[\underline{X}]$ gives rise to the two following canonical monomial orders on $\mathbb{H}_n^m$. Let us consider monomials $M = \underline{X}^\alpha e_i$ and $N = \underline{X}^\beta e_j \in \mathbb{M}_n^m$.

• We say that

$$M >_{\mathrm{TOP}} N \quad \text{if} \quad \begin{cases} \text{either } \underline{X}^\alpha > \underline{X}^\beta \\ \text{or both } \underline{X}^\alpha = \underline{X}^\beta \text{ and } i < j. \end{cases}$$

This monomial order is called *term over position* (TOP) because it gives precedence to the monomial order on $\mathbb{R}[\underline{X}]$ over the monomial position. For example, when $X_2 > X_1$, we have

$$X_2 e_1 >_{\mathrm{TOP}} X_2 e_2 >_{\mathrm{TOP}} X_1 e_1 >_{\mathrm{TOP}} X_1 e_2.$$

• We say that

$$M >_{\mathrm{POT}} N \quad \text{if} \quad \begin{cases} \text{either } i < j \\ \text{or both } i = j \text{ and } \underline{X}^\alpha > \underline{X}^\beta. \end{cases}$$

This monomial order is called *position over term* (POT) because it gives precedence to the monomial position over the monomial order on $\mathbb{R}[\underline{X}]$. For example, when $X_2 > X_1$, we have

$$X_2 e_1 >_{\mathrm{POT}} X_1 e_1 >_{\mathrm{POT}} X_2 e_2 >_{\mathrm{POT}} X_1 e_2.$$
**Definition 3.2** (list and module of leading terms, Gröbner bases). Let $\mathbf{R}$ be a discrete ring and consider a list $G = g_1, \dots, g_p$ in $\mathbf{H}_n^m$. We denote by $\mathrm{LT}(G) = \mathrm{LT}(g_1), \dots, \mathrm{LT}(g_p)$ the list of its leading terms. Suppose now that the $g_i$'s are nonzero and consider the finitely generated submodule $U = \langle G \rangle = \mathbf{R}[\mathbf{X}]g_1 + \dots + \mathbf{R}[\mathbf{X}]g_p$ of $\mathbf{H}_n^m$.

(1) The module of leading terms of $U$ is $\mathrm{MLT}(U) := \langle \mathrm{LT}(u); u \in U \rangle$.

(2) $G$ is a Gröbner basis for $U$ if $\mathrm{MLT}(U) = \langle \mathrm{LT}(G) \rangle$.

The following proposition comes from Gamanda, Lombardi, Neuwirth, and Yengui 2020. We give it as a motivating example showing that the “obvious” syzygies do not suffice to generate all of them.

**Proposition 3.3.** Let $\mathbf{R}$ be a strict Bézout ring, and $a_1, \dots, a_s \in \mathbf{R} \setminus \{0\}$. Denote by $(\epsilon_1, \dots, \epsilon_s)$ the canonical basis of $\mathbf{R}^s$. For $j \neq i$, write $a_j = d_{i,j}a_{i,j}$ with $d_{i,j} = \mathrm{gcd}(a_i, a_j)$. Then $\mathrm{Syz}(a_1, \dots, a_s)$ is generated by the $\binom{s}{2}$ vectors $a_{i,j}\epsilon_i - a_{j,i}\epsilon_j$ with $i < j,^1$ together with all the $z\epsilon_i$ with $z \in \mathrm{Ann}(a_i)$. In particular, $\mathbf{R}$ is coherent if and only if $\mathrm{Ann}(a)$ is finitely generated (and thus can be generated by just one element) for any $a \in \mathbf{R}$. In that case, letting $\mathrm{Ann}(a_k) = \langle b_k \rangle$ for $1 \le k \le s$, we have:

$$ \mathrm{Syz}(a_1, \dots, a_s) = \langle a_{i,j}\epsilon_i - a_{j,i}\epsilon_j, b_k\epsilon_k; 1 \le i < j \le s, 1 \le k \le s \rangle. $$

*Proof.* Let $c_1\epsilon_1 + \dots + c_s\epsilon_s \in \mathrm{Syz}(a_1, \dots, a_s)$, and let $s(a_i, a_j) := a_{i,j}\epsilon_i - a_{j,i}\epsilon_j$. Note that $\mathrm{gcd}(a_{i,j}, a_{j,i}) = 1$. For each permutation $i_1, \dots, i_s$ of $1, \dots, s$, consider the product $a_{i_1, i_2} \cdots a_{i_{s-1}, i_s}$. We claim that there is a Bézout identity for these products, so that it suffices to rewrite the expression $a_{i_1, i_2} \cdots a_{i_{s-1}, i_s} (c_1\epsilon_1 + \dots + c_s\epsilon_s)$ in terms of $s(a_{i_1}, a_{i_2}), \dots, s(a_{i_{s-1}}, a_{i_s})$ and $\mathrm{Ann}(a_{i_s})\epsilon_{i_s}$: let us replace successively

$$ \begin{array}{ll} a_{i_1, i_2} \epsilon_{i_1} & \text{by } s(a_{i_1}, a_{i_2}) + a_{i_2, i_1} \epsilon_{i_2}, \\ \vdots & \vdots \\ a_{i_{s-1}, i_s} \epsilon_{i_{s-1}} & \text{by } s(a_{i_{s-1}}, a_{i_s}) + a_{i_s, i_{s-1}} \epsilon_{i_s}. \end{array} $$

At the end, the sum will be a linear combination of $s(a_{i_1}, a_{i_2}), s(a_{i_2}, a_{i_3}), \dots, s(a_{i_{s-1}}, a_{i_s})$, and $\epsilon_{i_s}$; let $z$ be the coefficient of $\epsilon_{i_s}$ in this combination. As $c_1\epsilon_1 + \dots + c_s\epsilon_s \in \mathrm{Syz}(a_1, \dots, a_s)$, we have $z\epsilon_{i_s} \in \mathrm{Syz}(a_1, \dots, a_s)$, i.e. $za_{i_s} = 0$.

It remains to obtain the Bézout identity for the products $a_{i_1, i_2} \cdots a_{i_{s-1}, i_s}$. For this, it is enough to develop the product of the $\binom{s}{2}$ Bézout identities with respect to $a_{i,j}$ and $a_{j,i}$, $1 \le i < j \le s$: this yields a sum of products of $\binom{s}{2}$ terms, each of which is either $a_{i,j}$ or $a_{j,i}$, $1 \le i < j \le s$, so that it is indexed by the tournaments on the vertices $1, \dots, s$ (i.e. the directed graphs with exactly one edge between each two vertices); every such product contains a product of the above form $a_{i_1, i_2} \cdots a_{i_{s-1}, i_s}$ because every tournament contains a hamiltonian path (see Rédei 1934–1935). $\square$

<footnote n="1">¹These are the *obvious* syzygies.</footnote>
**Remark 3.4.** The above proof results from an analysis of the following proof in the case where $\mathbf{R}$ is local, which entails in fact the general case. Since $\mathbf{R}$ is a valuation ring, we may consider a permutation $i_1, \dots, i_s$ of $1, \dots, s$ such that $a_{i_s} | a_{i_{s-1}} | \dots | a_{i_1}$. Thus $s(a_{i_1}, a_{i_2}) = \epsilon_{i_1} - a_{i_2, i_1} \epsilon_{i_2}, \dots, s(a_{i_{s-1}}, a_{i_s}) = \epsilon_{i_{s-1}} - a_{i_s, i_{s-1}} \epsilon_{i_s}$ for some $a_{i_2, i_1}, \dots, a_{i_s, i_{s-1}}$. Then, by replacing successively $\epsilon_{i_k}$ by $s(a_{i_k}, a_{i_{k+1}}) + a_{i_{k+1}, i_k} \epsilon_{i_{k+1}}$, the syzygy $(c_1, \dots, c_s)$ may be rewritten as a linear combination of $s(a_{i_1}, a_{i_2}), \dots, s(a_{i_{s-1}}, a_{i_s})$, and $\epsilon_{i_s}$, with the coefficient of $\epsilon_{i_s}$ turning out to lie in $\mathrm{Ann}(a_{i_s})$. ■

In the following, we give examples of coherent rings over which syzygy modules are not always generated by vectors with at most 2 nonzero components.

**Example 3.5.** Consider the (noetherian) coherent ring $\mathbb{Z}[u]$ and the syzygy module $\mathrm{Syz}(2, u, u+2)$. As $\mathrm{Syz}(2, u) = \langle(u, -2)\rangle$, $\mathrm{Syz}(2, u+2) = \langle(u+2, -2)\rangle$, and $\mathrm{Syz}(u+2, u) = \langle(-u, u+2)\rangle$, we conclude that if $s = (s_1, s_2, s_3) \in \mathrm{Syz}(2, u, u+2)$ can be written as a $\mathbb{Z}[u]$-linear combination of syzygies in $\mathrm{Syz}(2, u, u+2)$ with at most 2 nonzero components, then it has entries $s_i$ in $\langle 2, u \rangle$. The syzygy $(1, 1, -1) \in \mathrm{Syz}(2, u, u+2)$ does not satisfy this property.

**Example 3.6.** Consider the ring $\mathbf{R} = \mathbb{Z}[u] + v\mathbb{Q}(u)[v]_{(v)}$. It is coherent by Dobbs and Papick (1976, Theorem 3, since q.f.($\mathbb{Z}[u]$)) = $\mathbb{Q}(u)$ and $\mathbb{Z}[u]$ is coherent) but nonnoetherian (since $\mathbb{Z}[u]$ is not a field, see Gilmer 1972, § 17, Exercise 14). As in Example 3.5, $(1, 1, -1) \in \mathrm{Syz}_{\mathbf{R}}(2, u, u+2)$ cannot be written as an $\mathbf{R}$-linear combination of syzygies in $\mathrm{Syz}_{\mathbf{R}}(2, u, u+2)$ with at most 2 nonzero components (suppose so and take $v=0$).

# 4 Syzygies in a polynomial ring over a discrete coherent ring

**Definition 4.1** (syzygies of terms, Discrete coherent context 2.2). Let $p \ge 1$ and $\mathcal{P}_p = \{E; \emptyset \ne E \subseteq [1..p]\}$ be the set of nonempty subsets of the set of indices $[1..p] = \{1, \dots, p\}$. Consider $M_1 = M'_1 e_{i_1}, \dots, M_p = M'_p e_{i_p}$ monomials in $\mathbf{H}_m^n$, $a_1, \dots, a_p \in \mathbf{R}$. Let $\mathcal{P}(M_1, \dots, M_p) \subseteq \mathcal{P}_p$ be the subset of those $E$ which are position level sets of $(M_1, \dots, M_p)$, i.e. such that $i_j = i_{j'}$ for $j, j' \in E$. Note that all singletons belong to $\mathcal{P}(M_1, \dots, M_p)$. For each position level set $E$ of $(M_1, \dots, M_p)$, let $s_i^E = \sum_{j \in E} s_{i,j}^E/M_j$ be a finite number of generators of $\mathrm{Syz}((a_j)_{j \in E})$ as given by a certificate of coherence for $\mathbf{R}$; here $s_i^E = (s_{i,j}^E)_{j \in E}$. Let $M^E = \mathrm{lcm}(M_j; j \in E)$ and $S^E(a_1 M_1, \dots, a_p M_p)$ be the list $S_1^E, \dots, S_{\ell_E}^E$, where $S_i^E = (S_{i,j}^E, \dots, S_{i,p}^E)$ with

$$S_{i,j}^E = \begin{cases} s_{i,j}^E M^E/M_j & \text{if } j \in E, \\ 0 & \text{otherwise.} \end{cases}$$

This is a syzygy for $(a_1 M_1, \dots, a_p M_p)$: see Equation (1) below. Finally, let $S(a_1 M_1, \dots, a_p M_p)$ be the concatenation of all the lists $S^E(a_1 M_1, \dots, a_p M_p)$ when $E$ ranges over the position level sets $E$ of $(M_1, \dots, M_p)$.
**Example 4.2.** Let $T_1 = (2X^2Y, 0) = 2M_1$, $T_2 = (XY^2, 0) = M_2$, $T_3 = (0, 4X) = 4M_3$ in $(\mathbb{Z}/8\mathbb{Z})[X, Y]^2$. We have $\mathcal{P}(M_1, M_2, M_3) = \{\{1\}, \{2\}, \{3\}, \{1,2\}\}, S_1^{\{1\}} = (4, 0, 0)$, $S_1^{\{2\}} = (0, 0, 0)$, $S_1^{\{3\}} = (0, 0, 2)$, $S_1^{\{1,2\}} = (Y, 6X, 0)$, and $\ell^{\{1\}} = \ell^{\{2\}} = \ell^{\{3\}} = \ell^{\{1,2\}} = 1$.

**Definition 4.3** (leading monomial of summands and their leading monomial index set). Let $f_1, \dots, f_p \in \mathbf{H}_n^m$ not all zero with $\mathrm{LC}(f_j) = a_j$ and $\mathrm{LM}(f_j) = M_j$. Let $g_1, \dots, g_p \in \mathbf{R}[\underline{X}]$ with $\mathrm{LC}(g_j) = b_j$ and $\mathrm{LM}(g_j) = N_j$. The leading monomial of the summands of $g_1f_1 + \dots + g_pf_p$ is the monomial $L = L(\underline{g}) = \sup_{j \in [1..p]} N_j M_j$, and their leading monomial index set is $E = \{j; N_j M_j = L\}$.

Propositions 4.4 and 4.6 as well as Fundamental theorem 4.11 generalise the method of Gamanda, Lombardi, Neuwirth, and Yengui 2020, Theorem 4.5.

**Proposition 4.4** (Discrete coherent context 2.2). The finite list $S(a_1M_1, \dots, a_pM_p)$ generates the syzygy module $\mathrm{Syz}(a_1M_1, \dots, a_pM_p) \subseteq \mathbf{R}[\underline{X}]^p$.

*Proof.* Let us use the notation of Definition 4.1. We first check that each $S_i^E$ is a syzygy for $(a_1M_1, \dots, a_pM_p)$:

$$S_{i,1}^E a_1 M_1 + \dots + S_{i,p}^E a_p M_p = \sum_{j \in E} s_{i,j}^E a_j M^E = \left( \sum_{j \in E} s_{i,j}^E a_j \right) M^E = 0. \quad (1)$$

Conversely, let $\underline{g} = (g_1, \dots, g_p) \in \mathrm{Syz}(a_1M_1, \dots, a_pM_p)$, not all $g_j$ zero, let $L = L(\underline{g})$ be the leading monomial of the summands of $g_1a_1M_1 + \dots + g_pa_pM_p$, and let $\underline{E}$ be their leading monomial index set. We have $\sum_{j \in E} b_j a_j = 0$, and thus $(b_j)_{j \in E} = c_1s_1^E + \dots + c_{\ell E} s_{\ell E}^E$ for some $c_1, \dots, c_{\ell E} \in \mathbf{R}$. Let

$$\underline{g'} = (g'_1, \dots, g'_p) = \underline{g} - \frac{L}{M^E} \sum_{i=1}^{\ell^E} c_i S_i^E \in \mathrm{Syz}(a_1M_1, \dots, a_pM_p);$$

note that $M^E$ divides $L$ because every $M_j, j \in E$, does. We have $g'_j = g_j$ for $j \notin E$ and, for $j \in E$,

$$\begin{align*}
g'_j &= g_j - \frac{L}{M^E} \sum_{i=1}^{\ell^E} c_i S_{i,j}^E = g_j - \frac{L}{M^E} \sum_{i=1}^{\ell^E} c_i \frac{M^E}{M_j} s_{i,j}^E \\
&= g_j - \frac{L}{M_j} \sum_{i=1}^{\ell^E} c_i s_{i,j}^E = g_j - \frac{L}{M_j} b_j = g_j - \mathrm{LT}(g_j).
\end{align*}$$

Thus $L(\underline{g'}) < L(\underline{g})$. Reiterating this (with $\underline{g'}$ instead of $\underline{g}$), we reach the desired result after a finite number of steps since the set of monomials is well ordered. $\square$

<footnote n="2">²Note that this is not in general the leading monomial of the vector that is the sum of the expression.</footnote>
*Example 4.5 (Example 4.2 continued).* In $(\mathbb{Z}/8\mathbb{Z})[X, Y]^2$, we have

$$ \mathrm{Syz}(T_1, T_2, T_3) = \langle (4, 0, 0), (0, 0, 2), (Y, 6X, 0) \rangle. $$

Following in detail the first step in the preceding proof we get the following proposition.

**Proposition 4.6** (notation of Definition 4.1, Discrete coherent context 2.2). Let

$$ u = \sum_{j \in [1..p]} g_j f_j, \quad L = \sup_{j \in [1..p]} N_j M_j, \quad \text{and } E = \{ j \in [1..p] ; N_j M_j = L \}. $$

If $\mathrm{LM}(u) < L$, then $f_{p+1}, \dots, f_{p+\ell^E} \in \mathbf{H}_n^m$ and $g_{p+1}, \dots, g_{p+\ell^E} \in \mathbf{R}[\underline{X}]$ defined by

$$ f_{p+i} = \sum_{j \in E} S_{i,j}^E f_j \quad \text{and} \quad g_{p+i} = c_i \frac{L}{M^E} $$

are such that

$$ u = \sum_{j \in E} (g_j - \mathrm{LT}(g_j)) f_j + \sum_{j \in [1..p+\ell^E] \setminus E} g_j f_j $$

is an expression for $u$ whose summands have leading monomial $<L$.

*Proof.* As $\mathrm{LM}(u) < L$, the coefficient of $L$ in $\sum_{j \in E} g_j f_j$ vanishes, so that $\sum_{j \in E} b_j a_j = 0$: we have

$$ \begin{aligned} \sum_{j \in E} \mathrm{LT}(g_j) f_j &= \sum_{j \in E} \sum_{1 \le i \le \ell^E} c_i s_{i,j}^E N_j f_j = \sum_{1 \le i \le \ell^E} c_i \sum_{j \in E} S_{i,j}^E \frac{M_j N_j}{M^E} f_j \\ &= \sum_{1 \le i \le \ell^E} g_{p+i} f_{p+i} \end{aligned} $$

with

$$ \mathrm{LM}(g_{p+i}) \mathrm{LM}(f_{p+i}) \le \frac{L}{M^E} \mathrm{LM} \left( \sum_{j \in E} S_{i,j}^E f_j \right) < \frac{L}{M^E} M^E = L. \quad \square $$

## Syzygies of terms, examples in the case of an ideal

This case is Discrete coherent context 2.2 with $m = 1$; every subset of $\mathcal{P}_p$ is a position level set.

*Example 4.7.* Let us consider the following syzygy of $(6XY^2, 15X^2YZ, 10Z^2)$ in $\mathbb{Z}[X, Y, Z]$:

$$ \underline{g} = (g_1, g_2, g_3) = (5XZ + 10Z^2, -2Y + 2Z, -3X^2Y - 6XY^2). $$

Following the algorithm given in the proof of Proposition 4.4 and considering the graded monomial lexicographic order with $X > Y > Z$, we have $L(\underline{g}) = L = X^2Y^2Z$, $E = \{1, 2\}$, $\mathrm{Syz}(6, 15) = \langle s_1^E = \frac{1}{3}(-15, 6) = (-5, 2) \rangle$, $\ell^E = 1$, $M^E = X^2Y^2Z$, $S_1^E = (-5\frac{X^2Y^2Z}{XY^2}, 2\frac{X^2Y^2Z}{X^2YZ}, 0) = (-5XZ, 2Y, 0)$, $(b_1, b_2) = (5, -2) = (-1) \cdot s_1^E$,
$c_1 = -1, g' = (g'_1, g'_2, g'_3) = g - \frac{L}{M^E} \sum_{i=1}^{\ell^E} c_i S_i^E = g + \frac{X^2 Y^2 Z}{X^2 Y^2 Z} S_1^E = g + (-5XZ, 2Y, 0) = (10Z^2, 2Z, -3X^2Y - 6XY^2) = (g_1 - \text{LT}(g_1), g_2 - \text{LT}(g_2), g_3)$, with $L(g') = L' = X^2YZ^2 < L(g)$.

Continuing with $g'$, we obtain $E' = \{2,3\}$, $\text{Syz}(15,10) = \langle s_1^{E'} = \frac{1}{5}(-10,15) = (-2,3)\rangle$, $\ell_{E'} = 1$, $M_{E'} = X^2YZ^2$, $S_1^{E'} = (0,-2\frac{X^2YZ^2}{X^2YZ}, 3\frac{X^2YZ^2}{Z^2}) = (0,-2Z, 3X^2Y)$, $(b'_2, b'_3) = (2,-3) = (-1) \cdot s_1^{E'}$, $g'' = g' - \frac{L'}{M_{E'} \sum_{i=1}^{\ell_{E'}} c'_i S_i^{E'}} = g' + \frac{X^2YZ^2}{X^2Y^2Z^2} S_1^{E'} = g' + (0,-2Z, 3X^2Y) = (10Z^2, 0, -6XY^2) = (g'_1, g'_2 - \text{LT}(g'_2), g'_3 - \text{LT}(g'_3)) = -2S_1^{\{1,3\}}$. We conclude that

$$g = -S_1^{\{1,2\}} - S_1^{\{2,3\}} - 2S_1^{\{1,3\}}.$$

*Example 4.8.* Let us consider the following syzygy of $(3XY, 3Y, X)$ in $\mathbb{Z}[X, Y]$:

$$g = (g_1, g_2, g_3) = (2X + Y, -3X^2 + 2XY, 3XY - 9Y^2).$$

Following the algorithm given in the proof of Proposition 4.4 and considering the lexicographic monomial order with $X > Y$, we have $L(g) = L = X^2Y$, $E = \{1,2,3\}$, $\text{Syz}(3,3,1) = \langle s_1^E = (-1,1,0), s_2^E = (-1,0,3)\rangle$, $\ell^E = 2$, $M^E = XY$, $S_1^E = (-1, X, 0)$, $S_2^E = (-1, 0, 3Y)$, $(b_1, b_2, b_3) = (2, -3, 3) = -3s_1^E + s_2^E$, $(c_1, c_2) = (-3, 1)$, $g' = (g'_1, g'_2, g'_3) = g - \frac{L}{M^E} \sum_{i=1}^{\ell^E} c_i S_i^E = g - \frac{X^2Y}{XY}(-3S_1^E + S_2^E) = g - X(2, -3X, 3Y) = (Y, 2XY, -9Y^2) = (g_1 - \text{LT}(g_1), g_2 - \text{LT}(g_2), g_3 - \text{LT}(g_3)) = 2Y S_1^E - 3Y S_2^E$, with $L(g') = XY^2 < L(g)$. We conclude that

$$g = (-3X + 2Y)S_1^{\{1,2,3\}} + (X - 3Y)S_2^{\{1,2,3\}}.$$

## S-lists and iterated S-lists, a fundamental theorem

**Definition 4.9** (Discrete coherent context 2.2). Let $f_1, \dots, f_p \in \mathbf{H}_n^m \setminus \{0\}$ and consider their leading terms $a_1 M_1, \dots, a_p M_p \in \mathbf{H}_n^m$. If $S_1, \dots, S_\ell$ is the list of generators of $\text{Syz}(\text{LT}(f_1, \dots, f_p))$ computed in Proposition 4.4, the S-list of $f_1, \dots, f_p$ is the list

$$\mathcal{S}(f_1, \dots, f_p) = S_{1,1}f_1 + \dots + S_{1,p}f_p, \dots, S_{\ell,1}f_1 + \dots + S_{\ell,p}f_p$$

after having deleted the vanishing items. By induction, we define the iterated S-lists by

* $\mathcal{S}^0(f_1, \dots, f_p) = f_1, \dots, f_p$;

* $\mathcal{S}^{q+1}(f_1, \dots, f_p)$ is the concatenation of $\mathcal{S}^q(f_1, \dots, f_p)$ with $\mathcal{S}(\mathcal{S}^q(f_1, \dots, f_p))$.

Note that each item of an iterated S-list is in $\langle f_1, \dots, f_p \rangle$.
**Remark 4.10.** If $\mathbf{R}$ is a Bézout ring then for any $a_1, \dots, a_q \in \mathbf{R}$ there exists a finite generating set for $\mathrm{Syz}(a_1, \dots, a_q)$ whose vectors have at most two nonzero components (see Proposition 3.3). Choose this generating set of syzygies in $\mathbf{R}^q$. It follows that in the corresponding iterated S-lists of $f_1, \dots, f_p$ there are only S-pairs ($\#E = 2$) and auto-S-polynomials ($\#E = 1$), as expected. Similarly, if $\mathbf{R}$ is a Prüfer domain (e.g. $\mathbf{R} = \{f \in \mathbb{Q}[X] ; f(\mathbb{Z}) \subseteq \mathbb{Z}\}$, which has Krull dimension equal to 2, see Lombardi 2010, Ducos 2015), then for any $a_1, \dots, a_q \in \mathbf{R}$ there exists a finite generating set for $\mathrm{Syz}(a_1, \dots, a_q)$ whose vectors have at most two nonzero components: in fact, a Prüfer domain is locally a valuation domain (thus, locally a Bézout domain). So in the corresponding iterated S-lists of $f_1, \dots, f_p$ there are only S-pairs (the auto-S-polynomials vanish since the ring $\mathbf{R}$ is supposed to be integral). ■

**Fundamental theorem 4.11** (Discrete coherent context 2.2). Let $f_1, \dots, f_p \in \mathbf{H}_n^m \setminus \{0\}$. For any $u \in \langle f_1, \dots, f_p \rangle$ there exist $q \in \mathbb{N}$ and items $p_1, \dots, p_t$ in the list $\mathcal{S}^q(f_1, \dots, f_p)$ such that $\mathrm{LT}(u) \in \langle \mathrm{LT}(p_1, \dots, p_t) \rangle$. In other words,

$$ \mathrm{MLT}(\langle f_1, \dots, f_p \rangle) = \bigcup_{q \in \mathbb{N}} \langle \mathrm{LT}(\mathcal{S}^q(f_1, \dots, f_p)) \rangle. $$

**Comment 4.12.** Compared to Theorem 4.2.8 of Adams and Loustaunau (1994), who suppose that the base ring $\mathbf{R}$ is strongly discrete, coherent, and noetherian, our Theorem 4.11 supposes only that $\mathbf{R}$ is discrete and coherent. Moreover, we do not perform divisions. This could be useful when one tries to prove results on the structure of the leading terms ideals (see Ben Amor and Yengui 2021, Guyot and Yengui 2024, Yengui 2021a, 2022 and the recent solution of the Gröbner ring conjecture in Yengui 2024). However Theorem 4.11 does not give a termination condition when one knows that the leading terms ideal is finitely generated (such a condition is given in Theorem 6.1). Our Theorem 4.11 is also useful when the leading terms ideal is not finitely generated (see Example 4.14 (1) and the counterexample given in Yengui 2021a). ■

*Proof.* Write

$$ u = \sum_{j=1}^{p} g_j f_j \quad \text{with } N_j = \mathrm{LM}(g_j) \text{ and } M_j = \mathrm{LM}(f_j). \qquad (2) $$

So $\mathrm{LM}(u) \le \sup_{1 \le j \le p} (N_j M_j) =: L$ (the leading monomial of the summands of $u$ in (2)).

Case 1. $\mathrm{LM}(u) = L$. Clearly $\mathrm{LT}(u) \in \langle \mathrm{LT}(f_1, \dots, f_p) \rangle$.

Case 2. $\mathrm{LM}(u) < L$. Let $E = \{ j ; N_j M_j = L \}$. By virtue of Proposition 4.6, we obtain another expression for $u$,

$$ u = \sum_{j \in E} (g_j - \mathrm{LT}(g_j)) f_j + \sum_{j \in [1..p+\ell E] \setminus E} g_j f_j \qquad (3) $$

with the $f_j$'s in $\mathcal{S}^1(f_1, \dots, f_p)$ and the $g_j$'s in $\mathbf{R}[\mathbf{X}]$, and the leading monomial of the summands of $u$ in (3) is $< L$. Reiterating this, we end up with a situation like that
of Case 1 because the set of monomials is well ordered. So we reach the desired result after a finite number of steps. □

*Remark 4.13.* In the proof of Fundamental theorem 4.11 with $m = 1$, if the considered monomial order refines total degree (i.e. if $M > N$ whenever $\text{tdeg}(M) > \text{tdeg}(N)$), then, letting $d = \max_{1 \le j \le p}(\text{tdeg}(g_j) + \text{tdeg}(f_j))$ and $\delta = \text{tdeg}(u)$ (assumed $\ge 1$), we have $q \le \binom{n+d}{d} - \binom{n+\delta-1}{\delta-1}$ (the number of monomials in $X_1, \dots, X_n$ of total degree at least $\delta$ and at most $d$). ■

*Example 4.14.* Let $\mathbf{V}$ be a nonarchimedean valuation domain, i.e. a valuation domain $\mathbf{V}$ such that there exist nonunits $a, b \in \mathbf{V}$ with $a^q$ dividing $b$ for every $q \in \mathbb{N}$.

(1) Let $f_1 = aX + 1, f_2 = b \in \mathbf{V}[X]$. Then MLT$(\langle f_1, f_2 \rangle)$ is not finitely generated (see Yengui 2015, Example 253): $\text{LT}(\mathcal{S}^q(f_1, f_2)) = \langle aX, b, \frac{b}{a}, \dots, \frac{b}{a^q} \rangle$ and $\text{MLT}(\langle f_1, f_2 \rangle) = \langle aX, b, \frac{b}{a}, \frac{b}{a^2}, \dots \rangle$.

(2) Let $f_1 = a^2 + aXY, f_2 = bY^2 \in \mathbf{V}[X, Y]$. We have

$$ \begin{aligned} \langle \text{LT}(\mathcal{S}^0(f_1, f_2)) \rangle &= aY \langle X, \frac{b}{a}Y \rangle \subsetneq \langle \text{LT}(\mathcal{S}^1(f_1, f_2)) \rangle = aY \langle X, \frac{b}{a}Y, b \rangle \\ &\subsetneq \langle \text{LT}(\mathcal{S}^2(f_1, f_2)) \rangle = \langle aXY, bY^2, abY, a^2b \rangle = \text{MLT}(\langle f_1, f_2 \rangle). \end{aligned} $$

**Corollary 4.15** (Discrete coherent context 2.2). Let $I = \langle f_1, \dots, f_p \rangle$ be a nonzero finitely generated submodule of $\mathbf{H}_n^m$. Suppose that MLT($I$) is finitely generated, i.e. that there exist $u_1, \dots, u_t \in I$ such that MLT($I$) = $\langle \text{LT}(u_1, \dots, u_t) \rangle$. Then there exists $q \in \mathbb{N}$ such that MLT($I$) = $\langle \text{LT}(\mathcal{S}^q(f_1, \dots, f_p)) \rangle$.

*Remark 4.16.* In Corollary 4.15 with $m = 1$, if the considered monomial order refines total degree, then, writing $u_k = \sum_{j=1}^p g_{k,j}f_j$ with $g_{k,j} \in \mathbf{R}[\mathbf{X}]$ and letting $d = \max_{1 \le k \le t, 1 \le j \le p}(\text{tdeg}(g_{k,j}) + \text{tdeg}(f_j))$ and $\delta = \min_{1 \le k \le t} \text{tdeg}(u_k)$ (assumed to be $\ge 1$), we have $q \le \binom{n+d}{d} - \binom{n+\delta-1}{\delta-1}$. ■

# 5 Basic algorithms

## The division algorithm

This algorithm in Simple division context 2.3 needs $\mathbf{R}$ to be strongly discrete; note that coherence is not used here. Like the classical division algorithm for $\mathbf{F}[\mathbf{X}]^m$ with $\mathbf{F}$ a discrete field (see Yengui 2015, Algorithm 211), this algorithm has the following
goal.

**Input** $u \in \mathbf{H}_n^m, h_1, \dots, h_p \in \mathbf{H}_n^m \setminus \{0\}$.
**Output** $q_1, \dots, q_p \in \mathbf{R}[\mathbf{X}]$ and $r \in \mathbf{H}_n^m$ such that
$$ \begin{cases} u = q_1h_1 + \dots + q_ph_p + r, \\ \mathrm{LM}(u) \ge \mathrm{LM}(q_j) \mathrm{LM}(h_j) \text{ whenever } q_j \ne 0, \\ T \notin \langle \mathrm{LT}(h_1, \dots, h_p) \rangle \text{ for each term } T \text{ of } r. \end{cases} $$

**Definition 5.1.** The vector $r$ is called a remainder of $u$ on division by the list $H = h_1, \dots, h_p$ and is denoted by $r = \bar{u}^H$.

Algorithm 5.2 provides a suitable answer: a suitable remainder $r$ and suitable quotients $q_j$. Nevertheless, there are a priori many different possible answers.

**Division algorithm 5.2 (Simple division context 2.3).**

1. Division $(u, h_1, \dots, h_p)$

2. local variables $j: [1..p]$, $D$: subset of $[1..p]$, $c, c_1, \dots, c_p, a_1, \dots, a_p: \mathbf{R}$, $M, M_1, \dots, M_p: \mathbf{H}_n^m$;

3. $r \leftarrow 0$;

4. $\mathbf{for} \ j \ \mathbf{from} \ 1 \ \mathbf{to} \ p \ \mathbf{do} \ q_j \leftarrow 0$; $M_j \leftarrow \mathrm{LM}(h_j)$; $c_j \leftarrow \mathrm{LC}(h_j)$ **od**;

5. while $u \ne 0$ **do**

7. $M \leftarrow \mathrm{LM}(u)$; $c \leftarrow \mathrm{LC}(u)$; $D \leftarrow \{j; M_j | M\}$;

8. if $c \in \langle c_j; j \in D \rangle$ **then**

10. $\mathbf{find} \ (a_j)_{j \in D}$ **such that** $\sum_{j \in D} a_j c_j = c$;

12. $u \leftarrow u - \sum_{j \in D} a_j (M/M_j) h_j$;

11. for $j \in D$ **do** $q_j \leftarrow q_j + a_j (M/M_j)$ **od**

12. else $r \leftarrow r + cM$; $u \leftarrow u - cM$ **fi**

13. **od**;

14. return $r, q_1, \dots, q_p$

One checks by induction that $\mathrm{LM}(q_j) \mathrm{LM}(h_j) \le \mathrm{LM}(u)$ and $u = q_1h_1 + \dots + q_ph_p + r$.

# Syzygy algorithms

**Notation 5.3.** We denote by $\mathrm{List}(A)$ the set of (finite) lists of elements of $A$.

These algorithms take place in Discrete coherent context 2.2. They are a key tool for constructing a Gröbner basis and have been introduced by Buchberger (1965) for the case where the base ring is a discrete field.

We begin with the basic syzygy algorithm returning $S^E(a_1M_1, \dots, a_pM_p) = S_1^E, \dots, S_\ell^E$ for $a_1M_1, \dots, a_pM_p \in \mathbf{H}_n^m$ and a subset $E \subseteq \mathcal{P}(M_1, \dots, M_p)$: see Definition
tion 4.1. Let us recall that $\mathbf{H}_n^1 = \mathbf{R}[\underline{X}]$.

**Input** $a_1M_1, \dots, a_pM_p$ terms in $\mathbf{H}_n^m$, $E \subseteq \mathcal{P}(M_1, \dots, M_p)$.

**Output** A list of syzygies $(S_{1,j}^E)_{j \in [1..p]}$, $(S_{\ell,j}^E)_{j \in [1..p]}$ for $(a_1M_1, \dots, a_pM_p)$ such that $S_{i,j}^E = 0$ for $j \notin E$ and, for every syzygy expression $g_1a_1M_1 + \dots + gPa_pM_p$ whose summands have leading monomial index set $E$, $(\mathrm{LT}(g_j))_{j \in E} \in \langle (S_{1,j}^E)_{j \in E}, \dots, (S_{\ell,j}^E)_{j \in E} \rangle$.

**Basic syzygy algorithm for terms 5.4** (basic syzygies of terms, Definition 4.1, Discrete coherent context 2.2).

1 BasicSyzygiesOfTerms $(a_1M_1, \dots, a_pM_p, E)$

2 **local variables** $j: [1..p]$, $\ell, i: \mathbb{N}$, $s_1, \dots, s_\ell: \mathbf{R}^E$, $M^E: \mathbf{H}_n^m$;

3 **find** $\ell, s_1, \dots, s_\ell$ **such that** $\mathrm{Syz}((a_j)_{j \in E}) = \langle s_1, \dots, s_\ell \rangle$;

4 **for** $i$ **from** 1 **to** $\ell$ **do**

5 **for** $j$ **from** 1 **to** $p$ **do**

6 $M^E \leftarrow \mathrm{lcm}(M_j; j \in E)$;

7 **if** $j \in E$ **then** $S_{i,j}^E \leftarrow s_{i,j}(M^E/M_j)$ **else** $S_{i,j}^E \leftarrow 0$ **fi**

8 **od**

9 **od**;

10 **return** $(S_{1,j}^E)_{j \in [1..p]}$, ..., $(S_{\ell,j}^E)_{j \in [1..p]}$

We now give an algorithm whose goal is to provide a generating set of syzygies for a vector of terms in $\mathbf{H}_n^m$; see Definition 4.1 and Proposition 4.4.

**Input** $a_1M_1 = a_1M'_1e_{i_1}, \dots, a_pM_p = a_pM'_pe_{i_p}$ terms in $\mathbf{H}_n^m$.

**Output** a list of syzygies $S_i^E \in \mathbf{R}[\underline{X}]^p$ such that the $S_i^E$'s generate $\mathrm{Syz}(a_1M_1, \dots, a_pM_p)$.

In the algorithm, we construct the syzygies $S_i^E$ by successive concatenations of the lists obtained by the previous algorithm.

**Syzygy algorithm for terms 5.5** (syzygies of terms, see Definition 4.1, Discrete coherent context 2.2).

1 SyzygiesOfTerms $(a_1M_1, \dots, a_pM_p)$

2 **local variables** $E$: subset of $[1..p]$, $S^E$: List$(\mathbf{R}[\underline{X}]^p)$;

3 $S \leftarrow$;

4 **for** $E$ **in** $\mathcal{P}(M_1, \dots, M_p)$ **do**

5 $S^E \leftarrow$ BasicSyzygiesOfTerms $(a_1M_1, \dots, a_pM_p, E)$;

6 $S \leftarrow S, S^E$

7 **od**;

8 **return** $S$
In the case of an ideal ($m = 1$), one may forget about the basis vectors $e_{i_1}, \dots, e_{i_p}$
and one has $\mathcal{P}(M_1, \dots, M_p) = \mathcal{P}_p$.

S-list algorithms

We have the following goal corresponding to the S-list $\mathcal{S}(f_1, \dots, f_p)$ in Definition 4.9
(Discrete coherent context 2.2).

**Input** $f_1, \dots, f_p \in \mathbf{H}_n^m$ not all zero,
**Output** The S-list $\mathcal{S} = \mathcal{S}(f_1, \dots, f_p)$ of $f_1, \dots, f_p$ as in Definition 4.9.

**S-list algorithm 5.6 (S-list algorithm, Definition 4.9, Discrete coherent context 2.2).**

1 Slist($f_1, \dots, f_p$)

2 local variables $Si, Ss : \mathbf{R}[\mathbf{X}]^p; S, Slist : \text{List}(\mathbf{R}[\mathbf{X}]^p)$;

3 $\mathcal{S} \leftarrow$;

4 $S \leftarrow$ SyzygiesOfTerms(LT($f_1, \dots, f_p$));

5 **for** $Si$ **in** $S$ **do**

6 $Ss \leftarrow Si_1f_1 + \dots + Si_pf_p;$

7 **if** $Ss \neq 0$ **then** $\mathcal{S} \leftarrow \mathcal{S}, Ss$ **fi**

8 **od;**

9 **return** $\mathcal{S}$

We have the following goal corresponding to the S-list $\mathcal{S}^q(f_1, \dots, f_p)$ in Definition 4.9 (Discrete coherent context 2.2.)

**Input** $q \in \mathbb{N}, f_1, \dots, f_p \in \mathbf{H}_n^m$ not all zero,
**Output** The iterated S-list $\mathcal{S}^q = \mathcal{S}^q(f_1, \dots, f_p)$ of $f_1, \dots, f_p$ as in Definition 4.9.

**S-list algorithm 5.7 (iterated S-list algorithm, Definition 4.9, Discrete coherent context 2.2).**

1 IteratedSlist($q, f_1, \dots, f_p$)

2 local variables $r : \mathbb{N}$;

3 $\mathcal{S}^q \leftarrow f_1, \dots, f_p;$

4 **for** $r$ **from** 1 **to** $q$ **do** $\mathcal{S}^q \leftarrow \mathcal{S}^q, \text{Slist}(\mathcal{S}^q)$ **od;**

5 **return** $\mathcal{S}^q$
Rewriting algorithms

The next algorithm corresponds to Proposition 4.6.

**Input** $f_1, \dots, f_p \in \mathbf{H}_n^m$ not all zero; $g_1, \dots, g_p \in \mathbf{R}[\mathbf{X}]$;
the leading monomial $L$ of the summands of $\sum_{j=1}^p g_j f_j = u$
(let $E$ be the corresponding leading monomial index set) is $> \mathrm{LT}(u)$.

**Output** $f_1, \dots, f_{p+\ell}$ in $\mathcal{S}(f_1, \dots, f_p)$ extending $f_1, \dots, f_p$; $g_1, \dots, g_{p+\ell} \in \mathbf{R}[\mathbf{X}]$ with the original $g_j$'s replaced by $g_j - \mathrm{LT}(g_j)$ for $j \in E$ and unchanged outside $E$; $u = \sum_{j=1}^{p+\ell} g_j f_j$ and the leading monomial of its summands is $< L$.

**Rewriting algorithm 5.8** (rewriting a linear combination, Proposition 4.6, Discrete coherent context 2.2).

1. Rewriting $((g_1, f_1), \dots, (g_p, f_p))$

2. local variables $j: [1..p]$, $\ell, i: \mathbb{N}$, $E$: subset of $[1..p]$, $N_1, \dots, N_p: \mathbf{R}[\mathbf{X}]$,
   $M_1, \dots, M_p, L, M^E: \mathbf{H}_n^m$, $a_1, \dots, a_p, b_1, \dots, b_p, c_1, \dots, c_\ell: \mathbf{R}$,

3. $s_1, \dots, s_\ell: \mathbf{R}^E$, $(S_{1,j}^E)_{j \in [1..p]}, \dots, (S_{\ell,j}^E)_{j \in [1..p]}: \mathbf{R}[\mathbf{X}]^p$;

4. for $j$ in $[1..p]$ do

5. $a_j \leftarrow \mathrm{LC}(f_j)$; $M_j \leftarrow \mathrm{LM}(f_j)$; $b_j \leftarrow \mathrm{LC}(g_j)$; $N_j \leftarrow \mathrm{LM}(g_j)$ od;

6. $L \leftarrow \sup\{N_j M_j; j \in [1..p]\}$; $E \leftarrow \{j \in [1..p]; N_j M_j = L\}$;

7. $M^E \leftarrow \mathrm{lcm}(M_j; j \in E)$;

8. $(S_{i,j}^E)_{j \in [1..p]}, \dots, (S_{\ell,j}^E)_{j \in [1..p]} \leftarrow \text{BasicSyzygiesOfTerms}(a_1 M_1, \dots, a_p M_p, E)$;

9. for $i$ in $[1..\ell]$ do $s_i \leftarrow (\mathrm{LC}(S_{i,j}^E))_{j \in E}$ od;

10. find $(c_i)_{i \in [1..\ell]}$ such that $(b_j)_{j \in E} = \sum_{i \in [1..\ell]} c_i s_i$;

11. for $i$ in $[1..\ell]$ do $g_{p+i} \leftarrow c_i \frac{L}{M^E}$; $f_{p+i} \leftarrow \sum_{j \in E} S_{i,j}^E f_j$ od;

12. for $j$ in $E$ do $g_j \leftarrow g_j - \mathrm{LT}(g_j)$ od;

13. return $(g_1, f_1), \dots, (g_{p+\ell}, f_{p+\ell})$

We have the following goal corresponding to Fundamental theorem 4.11 in Discrete coherent context 2.2. This is an iteration of the previous one with a counter $q$ for the number of iterations.

**Input** $f_1, \dots, f_p \in \mathbf{H}_n^m \setminus \{0\}$, $g_1, \dots, g_p \in \mathbf{R}[\mathbf{X}]$; we let $u = \sum_{j=1}^p g_j f_j$.

**Output** $q \in \mathbb{N}$ and $f_1, \dots, f_t$ in $\mathcal{S}^q(f_1, \dots, f_p)$ extending $f_1, \dots, f_p$ such that $\mathrm{LT}(u) \in \langle \mathrm{LT}(f_1, \dots, f_t) \rangle$.

**Rewriting algorithm 5.9** (iterated rewriting of a linear combination, Fundamental theorem 4.11, Discrete coherent context 2.2).

1. Iterated Rewriting $((g_1, f_1), \dots, (g_p, f_p))$

2. $q \leftarrow 0$;

3. while $\mathrm{LM}(g_1 f_1 + \dots + g_p f_p) < \sup\{\mathrm{LM}(g_1) \mathrm{LM}(f_1), \dots, \mathrm{LM}(g_p) \mathrm{LM}(f_p)\}$ do
4

$(g_1, f_1), \dots, (g_{p+\ell}, f_{p+\ell}) \leftarrow \text{Rewriting}((g_1, f_1), \dots, (g_p, f_p));$

5

$p \leftarrow p + \ell; q \leftarrow q + 1 \ \mathbf{od};$

6

return $q, f_1, \dots, f_p$

# 6 Buchberger's algorithm

The proof of the following theorem parallels exactly the proof of the analogue Theorem 4.2.3 of Adams and Loustaunau (1994).

## Fundamental theorem 6.1 (Strongly discrete coherent context 2.5).

(1) Buchberger's criterion. Let $f_1, \dots, f_p \in \mathbf{H}_n^m$ not all zero, and denote by $S_1, \dots, S_\ell$ the generators of $\text{Syz}(\text{LT}(f_1, \dots, f_p))$ computed in Proposition 4.4. Then $G = f_1, \dots, f_p$ is a Gröbner basis for $\langle f_1, \dots, f_p \rangle$ if and only if for every $1 \le i \le \ell$, we have

$$ \overline{S_{i,1}f_1 + \dots + S_{i,p}f_p}^G = 0. $$

(2) Buchberger's algorithm works. Let $f_1, \dots, f_p \in \mathbf{H}_n^m \setminus \{0\}$ and $M = \langle f_1, \dots, f_p \rangle$. If the module of leading terms $\text{MLT}(M)$ of the module $M$ is finitely generated, then the (generalised) Buchberger algorithm 6.2 computes a Gröbner basis for $\langle f_1, \dots, f_p \rangle$.

The (generalised) Buchberger algorithm has the following goal.

**Input** $f_1, \dots, f_p \in \mathbf{H}_n^m \setminus \{0\}$.

**Output** a Gröbner basis $f_1, \dots, f_p, \dots, f_\ell$ for $\langle f_1, \dots, f_p \rangle$ extending $f_1, \dots, f_p$.

## Buchberger's algorithm 6.2 (Strongly discrete coherent context 2.5).

1 Buchberger($f_1, \dots, f_p$)

2 local variables $\mathcal{S} : \text{List}(\mathbf{H}_n^m)$; $f, r : \mathbf{H}_n^m$; $L : \text{List}(\mathbf{R}[\underline{\mathcal{X}}])$;

3 $G \leftarrow f_1, \dots, f_p$;

4 repeat

5 $\mathcal{S} \leftarrow \text{Slist}(G)$;

6 for $f$ in $\mathcal{S}$ do

7 remove $f$ from $\mathcal{S}$;

8 $r, L \leftarrow \text{Division}(f, G)$;

9 if $r \neq 0$ then $\mathcal{S} \leftarrow \mathcal{S}, r$ fi

10 od;

11 if $\mathcal{S} \neq \emptyset$ then $G \leftarrow G, \mathcal{S}$ fi

12 until $\mathcal{S} = \emptyset$;

13 return $G$
Remark 6.3. If the algorithm terminates, then we can transform the obtained Gröbner basis into a Gröbner basis $h_1, \dots, h_p$ such that no term of an element $h_\ell$ lies in $\langle \mathrm{LT}(h_k); k \neq \ell \rangle$ 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 terminology of “reduced” Gröbner basis is used only in the case where a way of normalising its elements is specified: see Yengui 2015, Remark 239. ■

# 7 Schreyer's syzygy algorithm

**Definition 7.1** (Schreyer's monomial order). Let $\mathbf{R}$ be a discrete ring. Consider a list $G = f_1, \dots, f_p$ in $\mathbf{H}_n^m \setminus \{0\}$ and the finitely generated submodule $U = \langle G \rangle = \mathbf{R}[\mathbf{X}]f_1 + \dots + \mathbf{R}[\mathbf{X}]f_p$ of $\mathbf{H}_n^m$. Let $(\epsilon_1, \dots, \epsilon_p)$ be the canonical basis of $\mathbf{R}[\mathbf{X}]^p$. Schreyer's monomial order induced by $> \text{ and } G$ on $\mathbf{R}[\mathbf{X}]^p$ is the order $>_G$ defined as follows:

$$ \underline{\mathbf{X}}^{\alpha} \epsilon_k >_G \underline{\mathbf{X}}^{\beta} \epsilon_j \quad \text{if} \quad \left( \begin{array}{l} \text{either } \mathrm{LM}(\underline{\mathbf{X}}^{\alpha} f_k) > \mathrm{LM}(\underline{\mathbf{X}}^{\beta} f_j) \\ \text{or both } \mathrm{LM}(\underline{\mathbf{X}}^{\alpha} f_k) = \mathrm{LM}(\underline{\mathbf{X}}^{\beta} f_j) \text{ and } k < j. \end{array} \right. $$

Schreyer's monomial order is defined on $\mathbf{R}[\mathbf{X}]^p$ in the same way as when $\mathbf{R}$ is a discrete field (see Ene and Herzog 2012, p. 66). Note that it actually depends only on the leading monomials $\mathrm{LM}(G)$ of $G$.

Now we shall follow closely the ingenious proof by Schreyer (1980) of Hilbert's syzygy theorem via Gröbner bases, but with a strongly discrete coherent ring instead of a field. Schreyer's proof is very well explained in Ene and Herzog 2012, §§ 4.4.1–4.4.3.

Schreyer's syzygy algorithm below takes also place in Strongly discrete coherent context 2.5 for $\mathbf{R}$. It has the following goal.

**Input** a Gröbner basis $f_1, \dots, f_p$ for a submodule of $\mathbf{H}_n^m$.

**Output** a Gröbner basis $(u_i^E)_{1 \le i \le \ell^E, E \in \mathcal{P}(\mathrm{LM}(f_1), \dots, \mathrm{LM}(f_p))}$ for $\mathrm{Syz}(f_1, \dots, f_p)$ with respect to Schreyer's monomial order induced by $> \text{ and } f_1, \dots, f_p$.

**Schreyer's syzygy algorithm 7.2** (Strongly discrete coherent context 2.5).

1. SchreyerSyzygy($f_1, \dots, f_p$)

2. local variables ($S_i^E$) $1 \le i \le \ell^E, E \in \mathcal{P}(\mathrm{LM}(f_1), \dots, \mathrm{LM}(f_p))$: $\mathrm{List}(\mathbf{R}[\mathbf{X}]^p)$,

3. $q_1, \dots, q_p$: $\mathbf{R}[\mathbf{X}]$;

4. ($S_i^E$) $1 \le i \le \ell^E, E \in \mathcal{P}(\mathrm{LM}(f_1), \dots, \mathrm{LM}(f_p))$ $\leftarrow$ SyzygiesOfTerms($f_1, \dots, f_p$);

5. for $E$ in $\mathcal{P}(\mathrm{LM}(f_1), \dots, \mathrm{LM}(f_p))$ do

6. for $i$ from 1 to $\ell^E$ do

7. $0, q_1, \dots, q_p \leftarrow \mathrm{Division}(S_{i,1}^E f_1 + \dots + S_{i,p}^E f_p, f_1, \dots, f_p)$

8. (note that $\mathrm{LM}(S_{i,1}^E f_1 + \dots + S_{i,p}^E f_p) \ge \mathrm{LM}(q_j f_j)$ whenever $q_j f_j \ne 0$);
9

od

10

od;

12

return $(u_i^E)_{1\le i\le l^E, E\in\mathcal{P}(\text{LM}(f_1),\dots,\text{LM}(f_p))}$

Note that the polynomials $q_1, \dots, q_p$ of lines 7-8 may have been computed while constructing the Gröbner basis.

**Remark 7.3.** For an arbitrary system of generators $h_1, \dots, h_p$ for a submodule $U$ of $\mathbf{H}_n^m$, the syzygy module of $h_1, \dots, h_p$ is easily obtained from the syzygy module of a Gröbner basis for $U$ (see Yengui 2015, Theorem 296). ■

**Fundamental theorem 7.4** (Schreyer's algorithm, Strongly discrete coherent context 2.5). Let $U$ be a submodule of $\mathbf{H}_n^m$ with Gröbner basis $f_1, \dots, f_p$. Then the relations $u_i^E$ computed by Schreyer's syzygy algorithm 7.2 form a Gröbner basis for the syzygy module $\text{Syz}(f_1, \dots, f_p)$ with respect to Schreyer's monomial order induced by $>$ and $f_1, \dots, f_p$. Moreover, for $E$ a position level subset of $[1 \dots p]$ and $1 \le i \le l^E$,

$$ \mathrm{LT}(u_i^E) = s_{i,r}^E M^E / M_r \epsilon_r \text{ with } r = \min\{j \in E; s_{i,j}^E \neq 0\} \quad (4) $$

in the notation of Definition 4.1 with $M_1 = \text{LM}(f_1)$, $\dots$, $M_p = \text{LM}(f_p)$.

*Proof* (a slight modification of the proof of Ene and Herzog 2012, Theorem 4.16).

Let us use the notation of Schreyer's syzygy algorithm 7.2. Recall that $u_i^E = (S_{i,1}^E - q_1)\epsilon_1 + \dots + (S_{i,p}^E - q_p)\epsilon_p$, $S_{i,1}^E f_1 + \dots + S_{i,p}^E f_p = q_1 f_1 + \dots + q_p f_p$, and $\text{LM}(q_j f_j) \le \text{LM}(S_{i,1}^E f_1 + \dots + S_{i,p}^E f_p) < (M^E/M_k)M_k = M^E$ for any $k \in E$. So $\text{LT}(u_i^E) = \text{LT}(S_i^E) = s_{i,r}^E M^E / M_r \epsilon_r$ where $r = \min\{j \in E; s_{i,j}^E \neq 0\}$.

Let us show now that the relations $u_i^E$ form a Gröbner basis for the syzygy module $\text{Syz}(f_1, \dots, f_p)$. For this, let $v = v_1\epsilon_1 + \dots + v_p\epsilon_p \in \text{Syz}(f_1, \dots, f_p)$ and let us show that $\text{LT}(v) \in \langle \text{LT}(u_i^E) ; 1 \le i \le l^E, E \in \mathcal{P}(M_1, \dots, M_p) \rangle$. Let us write $\text{LM}(v_j\epsilon_j) = N_j\epsilon_j$ and $\text{LC}(v_j\epsilon_j) = c_j$ for $1 \le j \le p$. Then $\text{LM}(v) = N_k\epsilon_k$ for some $1 \le k \le p$. Now let $v' = \sum_{j \in D} c_j N_j \epsilon_j$, where $D$ is the set of those $j$ for which $N_j M_j = N_k M_k$. By definition of Schreyer's monomial order, we have $j \ge k$ for all $j \in D$. Substituting each $\epsilon_j$ in $v'$ by $T_j = \text{LT}(f_j)$, the sum becomes zero. Therefore $v'$ is a syzygy of the terms $T_j$ with $j \in D$. By virtue of Proposition 4.4, $v'$ is a linear combination of elements in $S((T_j)_{j \in D})$ of the form $S_i^E$ with $E \subseteq D$ and $1 \le i \le l^E$. By inspecting the $j$th component of $v'$, we deduce that there exist $w_1, \dots, w_t \in \mathbf{R}[X]$, position level subsets $E_1, \dots, E_t$ of $D$ with $j \in E_1 \cap \dots \cap E_t$, nonnegative integers $1 \le i_1 \le l_{E_1}, \dots, 1 \le i_t \le l_{E_t}$, such that $c_j N_j = w_1 s_{E_1, i_1, j} M_{E_1} / M_j + \dots + w_t s_{E_t, i_t, j} M_{E_t} / M_j$, and $s_{E_1, i_1, j}, \dots, s_{E_t, i_t, j} \neq 0$. As $j > k$ for all $j \in D \setminus \{k\}$, it follows that $\text{LT}(v') \in \langle \text{LT}(S_{E_1, i_1}, \dots, S_{E_t, i_t}) \rangle$. The desired result follows since $\text{LT}(v) = \text{LT}(v')$. □

Schreyer's monomial order is a tailor-made term over position monomial order which changes at each iteration, i.e. after each computation of a Gröbner basis
of the syzygy module of the considered Gröbner basis. Schreyer's trick is, for $v = v_1\epsilon_1 + \cdots + v_p\epsilon_p \in \text{Syz}(f_1, \dots, f_p)$, to prioritise (by deciding that they are greater) the $\text{LM}(v_j\epsilon_j)$ such that $\text{LM}(v_jf_j) = \max(\text{LM}(v_1f_1), \dots, \text{LM}(v_pf_p))$, and to order the obtained generators $u_i^E$ of $\text{Syz}(f_1, \dots, f_p)$ in such a way that $X_n$ does not appear in the leading terms of the $u_i^E$ (when computing a Gröbner basis for the first syzygy module), and to iterate this process until exhausting all the indeterminates $X_n, X_{n-1}, \dots, X_1$ from the leading terms of the Gröbner basis of the syzygy module. Once we reach this situation, we continue the resolution over the base ring $\mathbb{R}$.

As a consequence of Theorem 7.4, we obtain the following constructive version of Hilbert's syzygy theorem for a strongly discrete coherent ring.

**Theorem 7.5** (Hilbert's syzygy theorem, Strongly discrete coherent context 2.5). Let $\mathbf{H}_n^m$ be a free $\mathbb{R}[\mathbf{X}]$-module with basis $(e_1, \dots, e_m)$, and $> \text{a monomial order on } \mathbf{H}_n^m$. Let $U$ be a finitely generated submodule of $\mathbf{H}_n^m$ such that $\text{MLT}(U)$ is finitely generated with respect to some monomial order. Then $M = \mathbf{H}_n^m/U$ admits an $\mathbb{R}[\mathbf{X}]$-resolution

$$0 \to F_q/V \to F_{q-1} \to \cdots \to F_1 \to F_0 \to M \to 0$$

such that $q \le n+1$, $F_0, \dots, F_q$ are finitely generated free $\mathbb{R}[\mathbf{X}]$-modules, and $V$ is generated by finitely many iterated syzygies whose leading terms with respect to Schreyer's induced monomial order do not depend on the indeterminates $X_n, \dots, X_1$.

*Proof.* Let $(f_1, \dots, f_p)$ be a Gröbner basis for $U$ with respect to the considered order. Reorder the $f_j$'s so that whenever $\text{LM}(f_j)$ and $\text{LM}(f_k)$ involve the same position for some $k < j$, say $\text{LM}(f_k) = M_k'e_{i_k}$ and $\text{LM}(f_j) = M_j'e_{i_j}$ with $i_j = i_k$, then $\text{deg}_{X_n}(M_k') \ge \text{deg}_{X_n}(M_j')$. Consider the leading monomials $\text{LM}(u_i^E) = M^E/M_r \epsilon_r$, $r = \min\{j \in E; s_{i,j}^E \ne 0\}$, computed by Schreyer's syzygy algorithm 7.2: our reordering entails that $\text{deg}_{X_n} M_E = \text{deg}_{X_n} M_r$, so that the indeterminate $X_n$ does not appear in $\text{LM}(u_i^E)$. Thus, after at most $n$ computations of the iterated syzygies, we reach the desired situation. $\square$

*Remark 7.6.* This theorem generalises Theorems 5.5 and 6.2 of Gamanda, Lombardi, Neuwirth, and Yengui 2020. Note that their statement there, as well as that of its Theorem 5.9, needs to be amended: “the TOP lexicographic monomial order” needs to be replaced by “some monomial order”; the proof given here shows how their proof needs to be amended. See the arXiv version Gamanda, Lombardi, Neuwirth, and Yengui 2024.

## References

*William W. Adams and Philippe Loustaunau. An introduction to Gröbner bases*. American Mathematical Society, Providence, 1994. (pp. 2, 4, 11, and 17.)
Faten Ben Amor and Ihsen Yengui. The trailing terms ideal. *J. Algebra Appl.*, 20(9):2150153, 2021. doi:10.1142/S021949882150153X. (p. 11.)

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

Errett Bishop and Douglas Bridges. *Constructive analysis*. Grundlehren der mathematischen Wissenschaften, 279. Springer, Berlin, 1985. (p. 2.)

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:475–511, 2006. doi:10.1016/j.jsc.2005.09.007. (p. 13.)

David A. Cox, John Little, and Donal O'Shea. *Using algebraic geometry*. Graduate Texts in Mathematics, 185. Springer, New York, second edition, 2005. (p. 4.)

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

David E. Dobbs and Ira J. Papick. When is $D + M$ coherent? *Proc. Amer. Math. Soc.*, 56: 51–54, 1976. doi:10.2307/2041572. (p. 7.)

Lionel Ducos. Polynômes à valeurs entières : un anneau de Prüfer de dimension 2. *Comm. Algebra*, 43:1146–1155, 2015. doi:10.1080/00927872.2013.865040. (p. 11.)

Viviana Ene and Jürgen Herzog. *Gröbner bases in commutative algebra*. Graduate Studies in Mathematics, 130. American Mathematical Society, Providence, 2012. (pp. 18 and 19.)

Maroua Gamanda, Henri Lombardi, Stefan Neuwirth, and Ihsen Yengui. The syzygy theorem for Bézout rings. *Math. Comput.*, 89:941–964, 2020. doi:10.1090/mcom/3466. See Gamanda, Lombardi, Neuwirth, and Yengui 2024 for an amended version; the changes have been typeset in green. (pp. 2, 6, 8, and 20.)

Maroua Gamanda, Henri Lombardi, Stefan Neuwirth, and Ihsen Yengui. The syzygy theorem for Bézout rings. *arXiv*, 1905.08117, 2024. doi:10.48550/arXiv.1905.08117. (pp. 20 and 21.)

Robert Gilmer. *Multiplicative ideal theory*. Pure and Applied Mathematics, 12. Marcel Dekker, New York, 1972. (p. 7.)

Luc Guyot and Ihsen Yengui. The multivariate Serre conjecture ring. *J. Algebra*, 640:385–400, 2024. doi:10.1016/j.jalgebra.2023.10.032. (p. 11.)

Amina Hadj Kacem and Ihsen Yengui. Dynamical Gröbner bases over Dedekind rings. *J. Algebra*, 324:12–24, 2010. doi:10.1016/j.jalgebra.2010.04.014. (p. 2.)

Henri Lombardi. Un anneau de Prüfer. *Actes Rencontres C.I.R.M.*, 2(2):59–69, 2010. doi:10.5802/acirm.35. (p. 11.)

Henri Lombardi and Claude Quitté. *Commutative algebra: constructive methods. Finite projective modules*. Algebra and applications, 20. Springer, Dordrecht, 2015. Translated from the French (Calvage & Mounet, Paris, 2011, revised and extended by the authors) by Tania K. Roblot. (pp. 2, 3, and 4.)

Ray Mines, Fred Richman, and Wim Ruitenburg. *A course in constructive algebra*. Universitext. Springer, New York, 1988. (p. 2.)

László Rédei. Ein kombinatorischer Satz. *Acta Sci. Math. (Szeged)*, 7:39–43, 1934–1935. URL http://acta.bibl.u-szeged.hu/13432. (p. 6.)

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. 18.)
Ihsen Yengui. Dynamical Gröbner bases. *J. Algebra*, 301:447-458, 2006.
doi:10.1016/j.jalgebra.2006.01.051. (p. 2.)

Ihsen Yengui. *Constructive commutative algebra: projective modules over polynomial rings and dynamical Gröbner bases*. Lecture Notes in Mathematics, 2138. Springer, Cham, 2015.
(pp. 2, 12, 18, and 19.)

Ihsen Yengui. A counterexample to the Gröbner ring conjecture. *J. Algebra*, 586:526-536, 2021a. doi:10.1016/j.jalgebra.2021.07.009. (p. 11.)

Ihsen Yengui. *Computational algebra: course and exercises with solutions*. World Scientific, New Jersey, 2021b. (p. 4.)

Ihsen Yengui. The trailing terms ideal over a valuation domain. *Comm. Algebra*, 50:2290-2295, 2022. doi:10.1080/00927872.2021.2005080. (p. 11.)

Ihsen Yengui. A solution to the Gröbner ring conjecture. Preprint, 2024. (p. 11.)