■ **Algorithm 6** Variant of Algorithm 5 with the F5 strategy for the reductant selection

72 Similar to Algorithm 5, except for the following chunk

73 « select a reductant *f* in signature *σ* with corresponding node *k* » ≡

74 $k \leftarrow 0$

75 **for** $1 \le j < n$ **do**

76 &nbsp;&nbsp;&nbsp;&nbsp; **if** $\text{sig } L[j]$ divides $\sigma$ **then** $k \leftarrow j$

77 &nbsp;&nbsp;&nbsp;&nbsp; **if** $\text{lm } L[j] = 0$ **then break** &nbsp;&nbsp;&nbsp;&nbsp; —stop the search if $\sigma$ is a syzygy signature

78 pick $a \in A$ such that $a \text{sig } L[k] = \sigma$

79 $f \leftarrow aL[k]$

This leads to Algorithm 7. Checking correctness is an easy exercise.

■ **Algorithm 7** Variant of Algorithm 5 with signature pruning

80 Similar to Algorithm 5, except for the following chunk

81 « update the queue with the new relation *g* » ≡

82 **for** $h \in G$ **do**

83 &nbsp;&nbsp;&nbsp;&nbsp; $Q \leftarrow Q \cup \Sigma(g, h) \cup \Sigma(h, g)$

84 **for** $\sigma \in Q$ **do**

85 &nbsp;&nbsp;&nbsp;&nbsp; **if** $\exists \tau \in Q \setminus \{\sigma\}, \tau$ divides $\sigma$ **then**

86 &nbsp;&nbsp;&nbsp;&nbsp; $Q \leftarrow Q \setminus \{\sigma\}$

## 5.7 Simultaneous reduction

As another variation of Algorithm 5, we may handle several signatures at a time, in the F4 style (Faugère, 1999; Albrecht & Perry, 2010; Eder & Faugère, 2017, §13). Concretely, the sigset $G$ that is used to compute the reductions not updated each time a new element is discovered. The new elements are inserted in a sigset $N$ and after a bunch of signatures is handled (how many is to be determined by the implementation), the elements of $N$ are inserted in $G$. On line 98, the reductant $g$ is reduced with respect to $G$ (and as usual, multiples of elements of $G$ can be used in reduction steps) and also with respect to $N$ (but multiples cannot be used in reduction steps). In other words, the polynomial part $f^g$ is reduced modulo the set $AG^{<\sigma} \cup N$.

The reason to delay insertion into $G$ is the principle of simultaneous reduction. If we have to perform the reductions of sigpairs $f_1, \dots, f_r$ with respect to the same sigset $G$, it is possible to formulate the problem in terms of a matrix whose rows represent the $f_i$ and all possibly useful reducers from $AG$ in a reduction chain starting from any of the $f_i$. Once this matrix is computed (this is the *symbolic preprocessing* step), it can be used to compute the reductions efficiently. This matrix aspect is crucial for high-performance computations but it is a transparent transformation of the algorithm: it does not change what is computed, compared to the naive reductions of the $f_i$. For a more detailed introduction to the F4 strategy, see Cox et al. (2015, Chapter 10, §3).

► **Theorem 62.** *Algorithm 8 is correct and terminates.*

**Proof.** Termination is clear because the algorithm produces a well-formed sigtree (where the rank of a node is the number of the iteration at which it was produced), and at each iteration, either $Q$ diminishes or the sigtree grows. Correctness follows from Invariant (1) which also holds for this algorithm, with a slightly different argument than the one in Section 5.6.1. Indeed,
■ **Algorithm 6** Variant of Algorithm 5 with the F5 strategy for the reductant selection

72 Similar to Algorithm 5, except for the following chunk

73 « select a reductant *f* in signature *σ* with corresponding node *k* » ≡

74 $k \leftarrow 0$

75 **for** $1 \le j < n$ **do**

76 &nbsp;&nbsp;&nbsp;&nbsp; **if** $\text{sig } L[j]$ divides $\sigma$ **then** $k \leftarrow j$

77 &nbsp;&nbsp;&nbsp;&nbsp; **if** $\text{lm } L[j] = 0$ **then break** &nbsp;&nbsp;&nbsp;&nbsp; —stop the search if $\sigma$ is a syzygy signature

78 pick $a \in A$ such that $a \text{sig } L[k] = \sigma$

79 $f \leftarrow aL[k]$

This leads to Algorithm 7. Checking correctness is an easy exercise.

■ **Algorithm 7** Variant of Algorithm 5 with signature pruning

80 Similar to Algorithm 5, except for the following chunk

81 « update the queue with the new relation *g* » ≡

82 **for** $h \in G$ **do**

83 &nbsp;&nbsp;&nbsp;&nbsp; $Q \leftarrow Q \cup \Sigma(g, h) \cup \Sigma(h, g)$

84 **for** $\sigma \in Q$ **do**

85 &nbsp;&nbsp;&nbsp;&nbsp; **if** $\exists \tau \in Q \setminus \{\sigma\}, \tau$ divides $\sigma$ **then**

86 &nbsp;&nbsp;&nbsp;&nbsp; $Q \leftarrow Q \setminus \{\sigma\}$

## 5.7 Simultaneous reduction

As another variation of Algorithm 5, we may handle several signatures at a time, in the F4 style (Faugère, 1999; Albrecht & Perry, 2010; Eder & Faugère, 2017, §13). Concretely, the sigset $G$ that is used to compute the reductions not updated each time a new element is discovered. The new elements are inserted in a sigset $N$ and after a bunch of signatures is handled (how many is to be determined by the implementation), the elements of $N$ are inserted in $G$. On line 98, the reductant $g$ is reduced with respect to $G$ (and as usual, multiples of elements of $G$ can be used in reduction steps) and also with respect to $N$ (but multiples cannot be used in reduction steps). In other words, the polynomial part $f^g$ is reduced modulo the set $AG^{<\sigma} \cup N$.

The reason to delay insertion into $G$ is the principle of simultaneous reduction. If we have to perform the reductions of sigpairs $f_1, \dots, f_r$ with respect to the same sigset $G$, it is possible to formulate the problem in terms of a matrix whose rows represent the $f_i$ and all possibly useful reducers from $AG$ in a reduction chain starting from any of the $f_i$. Once this matrix is computed (this is the *symbolic preprocessing* step), it can be used to compute the reductions efficiently. This matrix aspect is crucial for high-performance computations but it is a transparent transformation of the algorithm: it does not change what is computed, compared to the naive reductions of the $f_i$. For a more detailed introduction to the F4 strategy, see Cox et al. (2015, Chapter 10, §3).

► **Theorem 62.** *Algorithm 8 is correct and terminates.*

**Proof.** Termination is clear because the algorithm produces a well-formed sigtree (where the rank of a node is the number of the iteration at which it was produced), and at each iteration, either $Q$ diminishes or the sigtree grows. Correctness follows from Invariant (1) which also holds for this algorithm, with a slightly different argument than the one in Section 5.6.1. Indeed,
**Algorithm 8** Computation of a rewrite basis, with simultaneous reduction. Pseudocode chunks are defined in Algorithm 5.

87 &lt;&lt; initialize signature queue and sigtree &gt;&gt; line 43
88 while Q is not empty do
89 &nbsp;&nbsp;&nbsp;&nbsp;S ← some nonempty subset of Q &nbsp;&nbsp;&nbsp;&nbsp;—select several signatures at a time
90 &nbsp;&nbsp;&nbsp;&nbsp;Q ← Q \ S
91 &nbsp;&nbsp;&nbsp;&nbsp;F ← ∅
92 &nbsp;&nbsp;&nbsp;&nbsp;for σ ∈ S do
93 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;« select a reductant f in signature σ with corresponding node k &gt;&gt; line 64
94 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if f is →G-reducible then
95 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;F ← F ∪ {(f, k)} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;—we keep the information of the parent
96 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;N ← ∅ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;—set of newly computed relations
97 &nbsp;&nbsp;&nbsp;&nbsp;for (f, k) ∈ F by increasing order of sig f do—reduction of reductants
98 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;g‡ ← a →-normal form of f‡ w.r.t. AG&lt;σ ∪ {h‡ | h ∈ N}
99 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;g ← (g‡, σ)
100 &lt;&lt; insert a node with label g and parent k &gt;&gt; line 54
101 &lt;&lt; update the queue with the new relation g &gt;&gt; line 60
102 &nbsp;&nbsp;&nbsp;&nbsp;N ← N ∪ {g} &nbsp;&nbsp;&nbsp;&nbsp;—insertion of g in G is delayed
103 &nbsp;&nbsp;&nbsp;&nbsp;G ← G ∪ N
104 return G

when an element *g* is inserted into *G*, if *g* is →*G*-reduced, then *G* ∪ {*g*} is a rewrite basis at *σ* so we may remove *σ* from *Q* without breaking the invariant. However, due to the nature of simultaneous reduction, it may happen that we insert an element that is not →*G*-reduced. In this case, then there is some *h* ∈ *G* which reduces *g* and we check easily that Σ(*g*, *h*) = {*sig* *g*}. So in this case, *sig* *g* is not actually removed from *Q* and the invariant is preserved. ◀

6 Settings

This section describes different monomial spaces coming from different settings in computer
algebra. Some are noncommutative or non-Noetherian.

**6.1 Polynomial ring**

Let $M = K[x_1, \dots, x_n]$ be the polynomial ring in $n$ variables over $K$, which we endow with a monomial order, so the function $\text{lm}$ is well defined. Let $A = \{x_1^{i_1} \cdots x_n^{i_n} \mid i_1, \dots, i_n \in \mathbb{N}\}$. The axioms for monomial orders ensure that $M$ is a monomial module over $A$. It is Noetherian. Moreover, it satisfies the extra property M4, so construction of prebases is easy, see Remark 25.

For sigpairs *f* and *g*, the critical set Σ(*f*, *g*) has zero or one element. There is the trivial case where *f*‡ = 0 or *g*‡ = 0. In this case, every multiple of *f* is →(*g*)-reduced, so Σ(*f*, *g*) = ∅. When *f*‡ and *g*‡ are both nonzero, there are monomials *a*, *b* ∈ *A* such that *a*lm *f* = *b*lm *g* = lcm(lm *f*, lm *g*). Then there are two cases, if *a*sig *f* ≤ *b*sig *g*, then Σ(*f*, {*g*}) = ∅; on the contrary, if *b*sig *g* < *a*sig *f*, then Σ(*f*, *g*) = {*a*sig *f*}.
**Algorithm 8** Computation of a rewrite basis, with simultaneous reduction. Pseudocode chunks are defined in Algorithm 5.

87 **« initialize signature queue and sigtree »** → line 43
88 **while** Q is not empty **do**
89 &nbsp;&nbsp;&nbsp;&nbsp;S ← some nonempty subset of Q &nbsp;&nbsp;&nbsp;&nbsp;—select several signatures at a time
90 &nbsp;&nbsp;&nbsp;&nbsp;Q ← Q \ S
91 &nbsp;&nbsp;&nbsp;&nbsp;F ← ∅
92 **for** σ ∈ S **do**
93 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;« select a reductant f in signature σ with corresponding node k » → line 64
94 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** f is →G-reducible **then**
95 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;F ← F ∪ {(f, k)} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;—we keep the information of the parent
96 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;N ← ∅ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;—set of newly computed relations
97 **for** (f, k) ∈ F by increasing order of sig f **do**—reduction of reductants
98 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;g‡ ← a →-normal form of f‡ w.r.t. AG<σ ∪ {h‡ | h ∈ N}
99 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;g ← (g‡, σ)
100 **« insert a node with label g and parent k »** → line 54
101 **« update the queue with the new relation g »** → line 60
102 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;N ← N ∪ {g} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;—insertion of g in G is delayed
103 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;G ← G ∪ N
104 **return** G

when an element *g* is inserted into *G*, if *g* is →G-reduced, then *G* ∪ {*g*} is a rewrite basis at *σ*
so we may remove *σ* from *Q* without breaking the invariant. However, due to the nature of
simultaneous reduction, it may happen that we insert an element that is not →G-reduced. In
this case, then there is some *h* ∈ *G* which reduces *g* and we check easily that Σ(*g*, *h*) = {*sig* *g*}.
So in this case, *sig* *g* is not actually removed from *Q* and the invariant is preserved. ◀

6 Settings

This section describes different monomial spaces coming from different settings in computer
algebra. Some are noncommutative or non-Noetherian.

**6.1 Polynomial ring**

Let $M = K[x_1, \dots, x_n]$ be the polynomial ring in $n$ variables over $K$, which we endow with a monomial order, so the function $\text{lm}$ is well defined. Let $A = \{x_1^{i_1} \cdots x_n^{i_n} \mid i_1, \dots, i_n \in \mathbb{N}\}$. The axioms for monomial orders ensure that $M$ is a monomial module over $A$. It is Noetherian. Moreover, it satisfies the extra property M4, so construction of prebases is easy, see Remark 25.

For sigpairs *f* and *g*, the critical set Σ(*f*, *g*) has zero or one element. There is the trivial case where *f*‡ = 0 or *g*‡ = 0. In this case, every multiple of *f* is →(*g*)-reduced, so Σ(*f*, *g*) = Ø. When *f*‡ and *g*‡ are both nonzero, there are monomials *a*, *b* ∈ *A* such that *a*lm *f* = *b*lm *g* = lcm(lm *f*, lm *g*). Then there are two cases, if *a*sig *f* ≤ *b*sig *g*, then Σ(*f*, {*g*}) = Ø; on the contrary, if *b*sig *g* < *a*sig *f*, then Σ(*f*, *g*) = {*a*sig *f*}.
## 6.2 Modules over polynomial rings

Let $r$ be a positive integer and let $M = K[x_1, \dots, x_n]^r$, which we endow with a term ordering – typically position-over-term, term-over-position, or Schreyer’s order (Kreuzer & Robbiano, 2000, §1.4). The monoid $A$ is the same as before. $M$ is a Noetherian monomial module and satisfies the extra condition M4.

The computation of $\Sigma(f, g)$ is slightly different. In the case where $f^\ddagger$ and $g^\ddagger$ are both nonzero, it may happen that no multiple of $\mathrm{lm}\,f$ and $\mathrm{lm}\,g$ coincide. Indeed, nonzero monomials in $M$ have an index in $\{1, \dots, r\}$ which is unchanged under multiplication. Therefore, if $f^\ddagger = 0$ or $g^\ddagger = 0$, or $\mathrm{lm}\,f$ and $\mathrm{lm}\,g$ have different indices, then $\Sigma(f, g) = \emptyset$. Otherwise, there are monomial $a, b \in A$ such that $\mathrm{alm}\,f = b \mathrm{alm}\,g$ (and $\mathrm{alm}\,f$ minimal). Depending on the comparison of $a$ sig $f$ and $b$ sig $g$, $\Sigma(f, g)$ is either $\emptyset$ or $\{a \text{ sig } f\}$, as in the polynomial case.

## 6.3 Monoid algebras

Let $A$ be a submonoid of $\{x_1^{i_1} \cdots x_n^{i_n} \mid i_1, \dots, i_n \in \mathbb{N}\}$ and let $M = K[A]$ be the ring of polynomials whose monomials are contained in $A$. It is clear that $M$ is a Noetherian monomial module over $A$. This case includes the “semigroup algebras” studied by Bender et al. (2019). It also includes some algebras that are interesting in singularity theory such that $K[x^2, xy, y^2]$, that are polynomial ring with finitely many monomials removed (in this case $x, y$, and $xy$).

The critical set $\Sigma(f, g)$ can contain more than one element. Assume, for example, that $M = K[x^2, xy, y^2]$ – that is $A = \{x^i y^j \mid i + j \ge 2\}$ – and that $f^\ddagger = x^2$ and $g^\ddagger = xy$. The set of all $a \in A$ such that $\mathrm{lm}(af^\ddagger)$ is divided by $\mathrm{lm}(g^\ddagger)$ is generated by $xy$ and $y^2$. It is not generated by $y$ because $y$ is not in $A$. Assuming that $xy$ sig $f > x^2$ sig $g$ and $y^2$ sig $f > xy$ sig $g$, we have

$$ \Sigma(f, g) = \{xy \text{ sig } f, y^2 \text{ sig } f\}. $$

## 6.4 Weyl algebras

Let $M = K[x_1, \dots, x_n, \partial_1, \dots, \partial_n]$ be the Weyl algebra on $n$ variables. It is noncommutative. We may define it as the subalgebra of $\mathrm{End}_K(K[X_1, \dots, X_n])$ where $x_i$ is the multiplication by $X_i$ and $\partial_i$ is the differentiation with respect to $X_i$. Concretely, $x_i x_j = x_j x_i$, $\partial_i \partial_j = \partial_j \partial_i$, $\partial_i x_j = x_j \partial_i$ (if $i \neq j$) and $\partial_i x_i = x_i \partial_i + 1$. A basis of $M$ is given by the monomials $x_1^{i_1} \cdots x_n^{i_n} \partial_1^{j_1} \cdots \partial_n^{j_n}$ and we can consider the same monomial orderings as we would do for a commutative polynomial ring in $2n$ variables.

For the monoid $A$, we cannot choose the set of monomials because it is not closed under multiplication. We choose instead $A$ to be the submonoid of $M$ generated by $x_1, \dots, x_n$ and $\partial_1, \dots, \partial_n$. We could also choose $A = M$. This turns $M$ into a Noetherian monomial module with the extra property M4, so we can construct signature modules with Remark 25. We could also choose $A$ to be the monoid of nonzero elements of $R$. Things behave similarly to the polynomial case, due to *quasicommutativity*: for any $a, b \in M$, $\mathrm{lm}(ab) = \mathrm{lm}(ba)$.

## 6.5 Differential algebras

Let $M = K[t, x_0, x_1, x_2, \dots]$ be a polynomial ring in infinitely many variables with a derivation defined by $t' = 1$ and $x'_i = x_{i+1}$. Let $W = M\langle\partial\rangle$ be the subalgebra of $\mathrm{End}_K M$ where $M$ acts by multiplication and $\partial$ be the derivation, similarly to the Weyl algebra case. This turns $M$ into a
## 6.2 Modules over polynomial rings

Let $r$ be a positive integer and let $M = K[x_1, \dots, x_n]^r$, which we endow with a term ordering – typically position-over-term, term-over-position, or Schreyer’s order (Kreuzer & Robbiano, 2000, §1.4). The monoid $A$ is the same as before. $M$ is a Noetherian monomial module and satisfies the extra condition M4.

The computation of $\Sigma(f, g)$ is slightly different. In the case where $f^\ddagger$ and $g^\ddagger$ are both nonzero, it may happen that no multiple of $\mathrm{lm}\,f$ and $\mathrm{lm}\,g$ coincide. Indeed, nonzero monomials in $M$ have an index in $\{1, \dots, r\}$ which is unchanged under multiplication. Therefore, if $f^\ddagger = 0$ or $g^\ddagger = 0$, or $\mathrm{lm}\,f$ and $\mathrm{lm}\,g$ have different indices, then $\Sigma(f, g) = \emptyset$. Otherwise, there are monomial $a, b \in A$ such that $\mathrm{alm}\,f = b \mathrm{alm}\,g$ (and $\mathrm{alm}\,f$ minimal). Depending on the comparison of $a$ sig $f$ and $b$ sig $g$, $\Sigma(f, g)$ is either $\emptyset$ or $\{a \text{ sig } f\}$, as in the polynomial case.

## 6.3 Monoid algebras

Let $A$ be a submonoid of $\{x_1^{i_1} \cdots x_n^{i_n} \mid i_1, \dots, i_n \in \mathbb{N}\}$ and let $M = K[A]$ be the ring of polynomials whose monomials are contained in $A$. It is clear that $M$ is a Noetherian monomial module over $A$. This case includes the “semigroup algebras” studied by Bender et al. (2019). It also includes some algebras that are interesting in singularity theory such that $K[x^2, xy, y^2]$, that are polynomial ring with finitely many monomials removed (in this case $x, y$, and $xy$).

The critical set $\Sigma(f, g)$ can contain more than one element. Assume, for example, that $M = K[x^2, xy, y^2]$ – that is $A = \{x^i y^j \mid i + j \ge 2\}$ – and that $f^\ddagger = x^2$ and $g^\ddagger = xy$. The set of all $a \in A$ such that $\mathrm{lm}(af^\ddagger)$ is divided by $\mathrm{lm}(g^\ddagger)$ is generated by $xy$ and $y^2$. It is not generated by $y$ because $y$ is not in $A$. Assuming that $xy$ sig $f > x^2$ sig $g$ and $y^2$ sig $f > xy$ sig $g$, we have

$$ \Sigma(f, g) = \{xy \text{ sig } f, y^2 \text{ sig } f\}. $$

## 6.4 Weyl algebras

Let $M = K[x_1, \dots, x_n, \partial_1, \dots, \partial_n]$ be the Weyl algebra on $n$ variables. It is noncommutative. We may define it as the subalgebra of $\mathrm{End}_K(K[X_1, \dots, X_n])$ where $x_i$ is the multiplication by $X_i$ and $\partial_i$ is the differentiation with respect to $X_i$. Concretely, $x_i x_j = x_j x_i$, $\partial_i \partial_j = \partial_j \partial_i$, $\partial_i x_j = x_j \partial_i$ (if $i \neq j$) and $\partial_i x_i = x_i \partial_i + 1$. A basis of $M$ is given by the monomials $x_1^{i_1} \cdots x_n^{i_n} \partial_1^{j_1} \cdots \partial_n^{j_n}$ and we can consider the same monomial orderings as we would do for a commutative polynomial ring in $2n$ variables.

For the monoid $A$, we cannot choose the set of monomials because it is not closed under multiplication. We choose instead $A$ to be the submonoid of $M$ generated by $x_1, \dots, x_n$ and $\partial_1, \dots, \partial_n$. We could also choose $A = M$. This turns $M$ into a Noetherian monomial module with the extra property M4, so we can construct signature modules with Remark 25. We could also choose $A$ to be the monoid of nonzero elements of $R$. Things behave similarly to the polynomial case, due to *quasicommutativity*: for any $a, b \in M$, $\mathrm{lm}(ab) = \mathrm{lm}(ba)$.

## 6.5 Differential algebras

Let $M = K[t, x_0, x_1, x_2, \dots]$ be a polynomial ring in infinitely many variables with a derivation defined by $t' = 1$ and $x'_i = x_{i+1}$. Let $W = M\langle\partial\rangle$ be the subalgebra of $\mathrm{End}_K M$ where $M$ acts by multiplication and $\partial$ be the derivation, similarly to the Weyl algebra case. This turns $M$ into a
left W-module and differential ideals are defined to be the submodules of M. We choose on M a lexicographic ordering with $t < x_0 < x_1$...

We choose A to be the monoid generated by $\partial, t, x_0, x_1...$. This turns M into a monomial module. It is quasicommutative (that is $\text{lm}(abm) = \text{lm}(bam)$ for any $a, b \in W$ and $m \in M$) but not Noetherian. However, it satisfies the extra condition M4 and the critical sets $\Sigma(f, G)$ are finite. This example extends to several independent variables and several function variables.

## 6.6 Free algebras

Let M be the free algebra generated by $n$ variables $x_1, \dots, x_n$. A basis of M is given by the monoid of words in $x_1, \dots, x_n$. A monomial order may be given, for example, by comparing the degree first and then the lexicographic order. We choose A to be the monoid of words, which acts naturally on M by left multiplication. This turn M into a monomial space with extra condition M4. If $n > 1$, it is not Noetherian, but the critical sets are finite.

To deal with two-sided ideals of M, we need to consider not only left multiplications but also right multiplications. We introduce the monoid $A' = A \times A^{\text{OP}}$ of pairs of words with the composition $(a, b)(a', b') = (aa', b'b)$ and the action on M given by $(a, b)m = amb$. This turn M into another monomial space. When $n > 1$, it is not Noetherian and does not satisfy extra condition M4. For example, as shown by Green et al. (1998), if $x_1 > x_2$ then $x_1x_1 - x_1x_2$ generates a two-sided ideal without a finite Gröbner basis. Moreover, the critical sets may be infinite, eventhough they may contain only finitely many nonsyzygy signatures (Hofstadler & Verron, 2022).

## References

* Albrecht, M., & Perry, J. (2010). *F4/5*. arXiv: 1006.4933.

* Arri, A., & Perry, J. (2011). The F5 criterion revised. *J. Symb. Comput.*, **46**(9), 1017–1029.
https://doi.org/10/cd5td7

* Arri, A., & Perry, J. (2017). Corrigendum to “The F5 criterion revised”. *J. Symb. Comput.*, **82**, 164–165.
https://doi.org/10/gp8639

* Bardet, M., Faugère, J.-C., & Salvy, B. (2015). On the complexity of the F5 Gröbner basis algorithm. *J. Symb. Comput.*, **70**, 49–70.
https://doi.org/10/gntfcb

* Becker, T., & Weispfenning, V. (1993). *Gröbner Bases: A Computational Approach to Commutative Algebra*. Springer-Verlag.
https://doi.org/10/cfhwn9

* Bender, M. R., Faugère, J.-C., & Tsigaridas, E. (2019). Gröbner basis over semigroup algebras: Algorithms and applications for sparse polynomial systems. *Proc. ISSAC 2019*, 42–49.
https://doi.org/10/gnt5z9

* Berthomieu, J., Eder, C., & Safey El Din, M. (2021). Msolve: A library for solving polynomial systems. *Proc. ISSAC 2021*, 51–58.
https://doi.org/10/gk8549

* Bosma, W., Cannon, J., & Playoust, C. (1997). The Magma algebra system I: The user language. *J. Symb. Comput.*, **24**(3-4), 235–265.
https://doi.org/10/ckdngx

* Buchberger, B. (1965). *Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal*.
left W-module and differential ideals are defined to be the submodules of M. We choose on M a lexicographic ordering with $t < x_0 < x_1$...

We choose A to be the monoid generated by $\partial, t, x_0, x_1...$. This turns M into a monomial module. It is quasicommutative (that is $\text{lm}(abm) = \text{lm}(bam)$ for any $a, b \in W$ and $m \in M$) but not Noetherian. However, it satisfies the extra condition M4 and the critical sets $\Sigma(f, G)$ are finite. This example extends to several independent variables and several function variables.

## 6.6 Free algebras

Let M be the free algebra generated by $n$ variables $x_1, \dots, x_n$. A basis of M is given by the monoid of words in $x_1, \dots, x_n$. A monomial order may be given, for example, by comparing the degree first and then the lexicographic order. We choose A to be the monoid of words, which acts naturally on M by left multiplication. This turn M into a monomial space with extra condition M4. If $n > 1$, it is not Noetherian, but the critical sets are finite.

To deal with two-sided ideals of M, we need to consider not only left multiplications but also right multiplications. We introduce the monoid $A' = A \times A^{\text{OP}}$ of pairs of words with the composition $(a, b)(a', b') = (aa', b'b)$ and the action on M given by $(a, b)m = amb$. This turn M into another monomial space. When $n > 1$, it is not Noetherian and does not satisfy extra condition M4. For example, as shown by Green et al. (1998), if $x_1 > x_2$ then $x_1x_1 - x_1x_2$ generates a two-sided ideal without a finite Gröbner basis. Moreover, the critical sets may be infinite, eventhough they may contain only finitely many nonsyzygy signatures (Hofstadler & Verron, 2022).

## References

* Albrecht, M., & Perry, J. (2010). *F4/5*. arXiv: 1006.4933.

* Arri, A., & Perry, J. (2011). The F5 criterion revised. *J. Symb. Comput.*, **46**(9), 1017–1029.
https://doi.org/10/cd5td7

* Arri, A., & Perry, J. (2017). Corrigendum to “The F5 criterion revised”. *J. Symb. Comput.*, **82**, 164–165.
https://doi.org/10/gp8639

* Bardet, M., Faugère, J.-C., & Salvy, B. (2015). On the complexity of the F5 Gröbner basis algorithm. *J. Symb. Comput.*, **70**, 49–70.
https://doi.org/10/gntfcb

* Becker, T., & Weispfenning, V. (1993). *Gröbner Bases: A Computational Approach to Commutative Algebra*. Springer-Verlag.
https://doi.org/10/cfhwn9

* Bender, M. R., Faugère, J.-C., & Tsigaridas, E. (2019). Gröbner basis over semigroup algebras: Algorithms and applications for sparse polynomial systems. *Proc. ISSAC 2019*, 42–49.
https://doi.org/10/gnt5z9

* Berthomieu, J., Eder, C., & Safey El Din, M. (2021). Msolve: A library for solving polynomial systems. *Proc. ISSAC 2021*, 51–58.
https://doi.org/10/gk8549

* Bosma, W., Cannon, J., & Playoust, C. (1997). The Magma algebra system I: The user language. *J. Symb. Comput.*, **24**(3-4), 235–265.
https://doi.org/10/ckdngx

* Buchberger, B. (1965). *Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal*.
Buchberger, B. (2006). An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal (M. P. Abramson, Trans.). *J. Symb. Comput.*, **41**(3), 475–511. https://doi.org/10/dz9kz6 (Original work published 1965)

Caruso, X., Vaccon, T., & Verron, T. (2020). Signature-based algorithms for Gröbner bases over Tate algebras. *Proc. ISSAC 2020*, 70–77. https://doi.org/10/gp99pq

Cox, D. A., Little, J., & O'Shea, D. (2015). *Ideals, Varieties, and Algorithms* (4th ed.). Springer. https://doi.org/10/hzv6

Decker, W., Greuel, G.-M., Pfister, G., & Schönemann, H. (2022). Singular 4-3-0 — A computer algebra system for polynomial computations. http://www.singular.uni-signaturebasiskl.de

Eder, C., & Faugère, J.-C. (2017). A survey on signature-based algorithms for computing Gröbner bases. *J. Symb. Comput.*, **80**(3), 719–784. https://doi.org/10/ggck7f

Eder, C., Lairez, P., Mohr, R., & Safey El Din, M. (2023). A signature-based algorithm for computing the nondegenerate locus of a polynomial system. *J. Symb. Comput.*, **119**, 1–21. https://doi.org/10/jxn2

Eder, C., & Perry, J. (2011). Signature-based algorithms to compute Gröbner bases. *Proc. ISSAC 2011*, 99–106. https://doi.org/10/dmwqmp

Eder, C., Pfister, G., & Popescu, A. (2017). On signature-based Gröbner bases over Euclidean rings. *Proc. ISSAC 2017*, 141–148. https://doi.org/10/gsbxs2

Eder, C., & Roune, B. H. (2013). Signature rewriting in Gröbner basis computation. *Proc. ISSAC 2013*, 331–338. https://doi.org/10/ggkppx

Faugère, J.-C. (1999). A new efficient algorithm for computing Gröbner bases ($F_4$). *J. Pure Appl. Algebra*, **139**(1-3), 61–88. https://doi.org/10/bpq5dx

Faugère, J.-C. (2001). Finding all the solutions of Cyclic 9 using Gröbner basis techniques. *Comput. Math.*, 1–12. https://doi.org/10/d9297x

Faugère, J.-C. (2002). A new efficient algorithm for computing gröbner bases without reduction to zero ($F_5$). *Proc. ISSAC 2002*, 75–83. https://doi.org/10/bd4nnq

Faugère, J.-C., & Joux, A. (2003). Algebraic cryptanalysis of hidden field equation (HFE) cryptosystems using Gröbner bases. *CRYPTO 2003*, 44–60. https://doi.org/10/fpfzgc

Francis, M., & Verron, T. (2020). A signature-based algorithm for computing Gröbner bases over principal ideal domains. *Math. Comput. Sci.*, **14**(2), 515–530. https://doi.org/10/gsbxs4

Galkin, V. V. (2014). Termination of the F5 algorithm. *Program. Comput. Softw.*, **40**(2), 47–57. https://doi.org/10/ghjx58

Gao, S., Guan, Y., & Volny, F. (2010). A new incremental algorithm for computing Groebner bases. *Proc. ISSAC 2010*, 13–19. https://doi.org/10/cwg6rj

Gao, S., Volny, F., & Wang, M. (2016). A new framework for computing Gröbner bases. *Math. Comp.*, **85**(297), 449–465. https://doi.org/10/f7t889

Gebauer, R., & Möller, H. M. (1986). Buchberger's algorithm and staggered linear bases. *Symp. Symb. Algebr. Comput.*, 218–221. https://doi.org/10/cb24fn

Gebauer, R., & Möller, H. M. (1988). On an installation of Buchberger's algorithm. *J. Symb. Comput.*, **6**(2), 275–286. https://doi.org/10/bfjdwc

Green, E. D., Mora, T., & Ufnarovski, V. (1998). The non-commutative Gröbner freaks. In M. Bronstein, V. Weispfenning, & J. Grabmeier (Eds.), *Symb. Rewriting Tech*. (pp. 93–104). Birkhäuser. https://doi.org/10/dfbt7g
Buchberger, B. (2006). An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal (M. P. Abramson, Trans.). *J. Symb. Comput.*, **41**(3), 475–511. https://doi.org/10/dz9kz6 (Original work published 1965)

Caruso, X., Vaccon, T., & Verron, T. (2020). Signature-based algorithms for Gröbner bases over Tate algebras. *Proc. ISSAC 2020*, 70–77. https://doi.org/10/gp99pq

Cox, D. A., Little, J., & O'Shea, D. (2015). *Ideals, Varieties, and Algorithms* (4th ed.). Springer. https://doi.org/10/hzv6

Decker, W., Greuel, G.-M., Pfister, G., & Schönemann, H. (2022). Singular 4-3-0 — A computer algebra system for polynomial computations. http://www.singular.uni-signaturebasiskl.de

Eder, C., & Faugère, J.-C. (2017). A survey on signature-based algorithms for computing Gröbner bases. *J. Symb. Comput.*, **80**(3), 719–784. https://doi.org/10/ggck7f

Eder, C., Lairez, P., Mohr, R., & Safey El Din, M. (2023). A signature-based algorithm for computing the nondegenerate locus of a polynomial system. *J. Symb. Comput.*, **119**, 1–21. https://doi.org/10/jxn2

Eder, C., & Perry, J. (2011). Signature-based algorithms to compute Gröbner bases. *Proc. ISSAC 2011*, 99–106. https://doi.org/10/dmwqmp

Eder, C., Pfister, G., & Popescu, A. (2017). On signature-based Gröbner bases over Euclidean rings. *Proc. ISSAC 2017*, 141–148. https://doi.org/10/gsbxs2

Eder, C., & Roune, B. H. (2013). Signature rewriting in Gröbner basis computation. *Proc. ISSAC 2013*, 331–338. https://doi.org/10/ggkppx

Faugère, J.-C. (1999). A new efficient algorithm for computing Gröbner bases ($F_4$). *J. Pure Appl. Algebra*, **139**(1-3), 61–88. https://doi.org/10/bpq5dx

Faugère, J.-C. (2001). Finding all the solutions of Cyclic 9 using Gröbner basis techniques. *Comput. Math.*, 1–12. https://doi.org/10/d9297x

Faugère, J.-C. (2002). A new efficient algorithm for computing gröbner bases without reduction to zero ($F_5$). *Proc. ISSAC 2002*, 75–83. https://doi.org/10/bd4nnq

Faugère, J.-C., & Joux, A. (2003). Algebraic cryptanalysis of hidden field equation (HFE) cryptosystems using Gröbner bases. *CRYPTO 2003*, 44–60. https://doi.org/10/fpfzgc

Francis, M., & Verron, T. (2020). A signature-based algorithm for computing Gröbner bases over principal ideal domains. *Math. Comput. Sci.*, **14**(2), 515–530. https://doi.org/10/gsbxs4

Galkin, V. V. (2014). Termination of the F5 algorithm. *Program. Comput. Softw.*, **40**(2), 47–57. https://doi.org/10/ghjx58

Gao, S., Guan, Y., & Volny, F. (2010). A new incremental algorithm for computing Groebner bases. *Proc. ISSAC 2010*, 13–19. https://doi.org/10/cwg6rj

Gao, S., Volny, F., & Wang, M. (2016). A new framework for computing Gröbner bases. *Math. Comp.*, **85**(297), 449–465. https://doi.org/10/f7t889

Gebauer, R., & Möller, H. M. (1986). Buchberger's algorithm and staggered linear bases. *Symp. Symb. Algebr. Comput.*, 218–221. https://doi.org/10/cb24fn

Gebauer, R., & Möller, H. M. (1988). On an installation of Buchberger's algorithm. *J. Symb. Comput.*, **6**(2), 275–286. https://doi.org/10/bfjdwc

Green, E. D., Mora, T., & Ufnarovski, V. (1998). The non-commutative Gröbner freaks. In M. Bronstein, V. Weispfenning, & J. Grabmeier (Eds.), *Symb. Rewriting Tech*. (pp. 93–104). Birkhäuser. https://doi.org/10/dfbt7g
Hashemi, A., & Ars, G. (2010). Extended F5 criteria. *J. Symb. Comput.*, **45**(12), 1330–1340.
https://doi.org/10/bmfh29

Hashemi, A., & Javanbakht, M. (2021). On the construction of staggered linear bases. *J. Algebra Appl.*, **20**(8), 21501–32. https://doi.org/10/gqwrpn

Higman, G. (1952). Ordering by divisibility in abstract algebras. *Proc. Lond. Math. Soc.*, **2**(1), 326–336. https://doi.org/10/fmt8nh

Hofstadler, C., & Verron, T. (2022). Signature Gröbner bases, bases of syzygies and cofactor reconstruction in the free algebra. *J. Symb. Comput.*, **113**, 211–241. https://doi.org/10/gp85ss

Hofstadler, C., & Verron, T. (2023). Signature Gröbner bases in free algebras over rings. *Proc. ISSAC 2023*, 298–306. https://doi.org/10/gskrd2

Huet, G. (1980). Confluent reductions: Abstract properties and applications to term rewriting systems. *J. ACM*, **27**(4), 797–821. https://doi.org/10/fj7n4g

Kambe, Y. (2023). *Analysis of computing Gr|"obner bases and Gr|"obner degenerations via theory of signatures*. arXiv: 2305.13639 [math]. Retrieved 2023, from
http://arxiv.org/abs/2305.13639

Kreuzer, M., & Robbiano, L. (2000). *Computational commutative algebra* (Vol. 1). Springer.
https://doi.org/10/ffxbqr

Lu, D., Wang, D., Xiao, F., & Zhou, J. (2018). Extending the GVW algorithm to local ring. *Proc. ISSAC 2018*, 271–278. https://doi.org/10/gsbxr9

Möller, H. M., Mora, T., & Traverso, C. (1992). Gröbner bases computation using syzygies. *Proc. ISSAC 1992*, 320–328. https://doi.org/10/cgb2ts

Monagan, M., & Pearce, R. (2015). A compact parallel implementation of F4. *Proc. PASCO 2015*, 95–100. https://doi.org/10/ggpbmk

Mora, T. (1994). An introduction to commutative and noncommutative Gröbner bases. *Theor. Comput. Sci.*, **134**(1), 131–173. https://doi.org/10/dvwxsv

Mora, T. (2005). *Solving polynomial equation systems* (Vol. 2). Cambridge University Press.
https://doi.org/10/jdwm

Roune, B. H., & Stillman, M. (2012). Practical Gröbner basis computation. *Proc. ISSAC 2012*,
203–210. https://doi.org/10/ggkpqd

Stillman, M. (1990). Methods for computing in algebraic geometry and commutative algebra. *Acta Appl. Math.*, **21**(1), 77–103. https://doi.org/10/dsx7mz

Sun, Y., & Wang, D. (2011). *Solving detachability problem for the polynomial ring by signature-based Gröbner basis algorithms*. arXiv: 1108.1301.

Sun, Y., & Wang, D. (2013). A new proof for the correctness of the F5 algorithm. *Sci. China Math.*, **56**(4), 745–756. https://doi.org/10/gp867m

Sun, Y., Wang, D., Ma, X., & Zhang, Y. (2012). A signature-based algorithm for computing Gröbner bases in solvable polynomial algebras. *Proc. ISSAC 2012*, 351–358.
https://doi.org/10/ghtkmx

Traverso, C. (1996). Hilbert functions and the Buchberger algorithm. *J. Symb. Comput.*, **22**(4), 355–376. https://doi.org/10/b3x2ct

Vaccon, T., Verron, T., & Yokoyama, K. (2018). On affine tropical F5 algorithms. *Proc. ISSAC 2018*, 383–390. https://doi.org/10/d3mr
Hashemi, A., & Ars, G. (2010). Extended F5 criteria. *J. Symb. Comput.*, **45**(12), 1330–1340.
https://doi.org/10/bmfh29

Hashemi, A., & Javanbakht, M. (2021). On the construction of staggered linear bases. *J. Algebra Appl.*, **20**(8), 21501–32. https://doi.org/10/gqwrpn

Higman, G. (1952). Ordering by divisibility in abstract algebras. *Proc. Lond. Math. Soc.*, **2**(1), 326–336. https://doi.org/10/fmt8nh

Hofstadler, C., & Verron, T. (2022). Signature Gröbner bases, bases of syzygies and cofactor reconstruction in the free algebra. *J. Symb. Comput.*, **113**, 211–241. https://doi.org/10/gp85ss

Hofstadler, C., & Verron, T. (2023). Signature Gröbner bases in free algebras over rings. *Proc. ISSAC 2023*, 298–306. https://doi.org/10/gskrd2

Huet, G. (1980). Confluent reductions: Abstract properties and applications to term rewriting systems. *J. ACM*, **27**(4), 797–821. https://doi.org/10/fj7n4g

Kambe, Y. (2023). *Analysis of computing Gr|"obner bases and Gr|"obner degenerations via theory of signatures*. arXiv: 2305.13639 [math]. Retrieved 2023, from
http://arxiv.org/abs/2305.13639

Kreuzer, M., & Robbiano, L. (2000). *Computational commutative algebra* (Vol. 1). Springer.
https://doi.org/10/ffxbqr

Lu, D., Wang, D., Xiao, F., & Zhou, J. (2018). Extending the GVW algorithm to local ring. *Proc. ISSAC 2018*, 271–278. https://doi.org/10/gsbxr9

Möller, H. M., Mora, T., & Traverso, C. (1992). Gröbner bases computation using syzygies. *Proc. ISSAC 1992*, 320–328. https://doi.org/10/cgb2ts

Monagan, M., & Pearce, R. (2015). A compact parallel implementation of F4. *Proc. PASCO 2015*, 95–100. https://doi.org/10/ggpbmk

Mora, T. (1994). An introduction to commutative and noncommutative Gröbner bases. *Theor. Comput. Sci.*, **134**(1), 131–173. https://doi.org/10/dvwxsv

Mora, T. (2005). *Solving polynomial equation systems* (Vol. 2). Cambridge University Press.
https://doi.org/10/jdwm

Roune, B. H., & Stillman, M. (2012). Practical Gröbner basis computation. *Proc. ISSAC 2012*,
203–210. https://doi.org/10/ggkpqd

Stillman, M. (1990). Methods for computing in algebraic geometry and commutative algebra. *Acta Appl. Math.*, **21**(1), 77–103. https://doi.org/10/dsx7mz

Sun, Y., & Wang, D. (2011). *Solving detachability problem for the polynomial ring by signature-based Gröbner basis algorithms*. arXiv: 1108.1301.

Sun, Y., & Wang, D. (2013). A new proof for the correctness of the F5 algorithm. *Sci. China Math.*, **56**(4), 745–756. https://doi.org/10/gp867m

Sun, Y., Wang, D., Ma, X., & Zhang, Y. (2012). A signature-based algorithm for computing Gröbner bases in solvable polynomial algebras. *Proc. ISSAC 2012*, 351–358.
https://doi.org/10/ghtkmx

Traverso, C. (1996). Hilbert functions and the Buchberger algorithm. *J. Symb. Comput.*, **22**(4), 355–376. https://doi.org/10/b3x2ct

Vaccon, T., Verron, T., & Yokoyama, K. (2018). On affine tropical F5 algorithms. *Proc. ISSAC 2018*, 383–390. https://doi.org/10/d3mr
Vaccon, T., & Yokoyama, K. (2017). A tropical F5 algorithm. *Proc. ISSAC 2017*, 429–436.
https://doi.org/10/gsbxs8

Winkler, F. (1996). *Polynomial algorithms in computer algebra*. Springer-Verlag.
https://doi.org/10/bkh6hq
Vaccon, T., & Yokoyama, K. (2017). A tropical F5 algorithm. *Proc. ISSAC 2017*, 429–436.
https://doi.org/10/gsbxs8

Winkler, F. (1996). *Polynomial algorithms in computer algebra*. Springer-Verlag.
https://doi.org/10/bkh6hq