# A Signature-based Algorithm for Computing the Nondegenerate Locus of a Polynomial System

Christian Eder, Pierre Lairez, Rafael Mohr, Mohab Safey El Din

<figure><img src="image_1.png" /></figure>

## To cite this version:

Christian Eder, Pierre Lairez, Rafael Mohr, Mohab Safey El Din. A Signature-based Algorithm for Computing the Nondegenerate Locus of a Polynomial System. Journal of Symbolic Computation, 2023, 119, pp.1-21. 10.1016/j.jsc.2023.02.001. hal-03590675v4

HAL Id: hal-03590675

https://hal.science/hal-03590675v4

Submitted on 10 Mar 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>
# A Signature-based Algorithm for Computing the Nondegenerate Locus of a Polynomial System*

Christian Ederª, Pierre Lairezᵇ, Rafael Mohrª,ᶜ,*, Mohab Safey El Dinᶜ

ªRPTU Kaiserslautern-Landau, Department of Mathematics, Gottlieb-Daimler-Straße 48,
67663 Kaiserslautern, Germany

ᵇUniversité Paris-Saclay, Inria, Inria Saclay, 91120 Palaiseau, France

ᶜSorbonne Université, LIP6, CNRS, Boîte courrier 169, 75252 Paris Cedex 05, France

## Abstract

Polynomial system solving arises in many application areas to model non-linear geometric properties. In such settings, polynomial systems may come with degeneration which the end-user wants to exclude from the solution set. The nondegenerate locus of a polynomial system is the set of points where the codimension of the solution set matches the number of equations.

Computing the nondegenerate locus is classically done through ideal-theoretic operations in commutative algebra such as saturation ideals or equidimensional decompositions to extract the component of maximal codimension.

By exploiting the algebraic features of signature-based Gröbner basis algorithms we design an algorithm which computes a Gröbner basis of the equations describing the closure of the nondegenerate locus of a polynomial system, without computing first a Gröbner basis for the whole polynomial system.

**Keywords:** Gröbner Basis, Ideal Decomposition, Algorithm

## 1. Introduction

*Problem Statement.* Fix a field $K$ with an algebraic closure $\overline{K}$ and a polynomial ring $R := K[x_1, \dots, x_n]$ over $K$. Let $f_1, \dots, f_c \in R$ and $V := \{p \in \overline{K}^n \mid f_1(p) = \dots = f_c(p) = 0\}$. Further define the ideal $I := \langle f_1, \dots, f_c \rangle = \{\sum_{i=1}^c q_i f_i \mid q_i \in R\}$. The algebraic set $V$ is a finite union of irreducible components. By the

<footnote>*This work has been supported by European Union's Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Actions, grant agreement 813211 (POEMA) by European Research Council under the European Union's Horizon Europe research and innovation programme, grant agreement 101040794 (10000 DIGITS); by the joint ANR-FWF grant ANR-19-CE48-0015 (ECARP), the ANR grant ANR-19-CE40-0018 (De Rerum Natura), the DFG Sonderforschungsbereich TRR 195, and the Forschungsinitiative Rheinland-Pfalz.</footnote>

<footnote>*Corresponding author</footnote>

<footnote>Email addresses: ederc@mathematik.uni-kl.de (Christian Eder), pierre.lairez@inria.fr (Pierre Lairez), Rafael.Mohr@lip6.fr (Rafael Mohr), mohab.safey@lip6.fr (Mohab Safey El Din)</footnote>
Principal Ideal Theorem [21, Theorem 10.2] the codimension of the $K$-irreducible components of $V$ is at most $c$. Let $V_c$ denote the union of the components of $V$ of codimension exactly $c$. In particular $V_c = \emptyset$ when $c > n$.

The goal of this paper is to compute a Gröbner basis of an ideal whose zero set is $V_c$, which we call the *nondegenerate locus* of the system $f_1, \dots, f_c$ (note that we may not compute a *radical* ideal).

*Prior works and scientific locks.* State-of-the-art algorithms to compute the nondegenerate locus of $f_1, \dots, f_c$ rely on the more general problem of computing the equidimensional decomposition of the ideal that they generate. There is a vast body of literature split along what data structure is used for the output into two research lines.

The first family of algorithms computes a Gröbner basis of the ideal of each component. There are two different approaches in this line. The first uses projections, computed with *elimination orderings*, to reduce the problem to a problem for hypersurfaces [27, 35, 8]. The second relies on homological characterizations of the dimension and the computation of free resolutions [22]. See [15, 31, 43] and references therein for further references. Both approaches use Gröbner basis algorithms as a black box for performing various ideal-theoretic operations, in particular ideal quotients (also known as colon ideals).

A second family of algorithms outputs equidimensional components of $I$ or its radical through *lazy* representations, i.e. as complete intersections over a non-empty Zariski open set. This is the case for the so-called regular chains which go back to Wu-Ritt characteristic sets [46]. Algorithms based on regular chains put into practice a kind of D5 principle [17] to split geometric objects by enforcing an equiprojectability property. See [32, 44, 45, 12, 2, 38] and references therein for further references.

When the base field $K$ has characteristic 0 (or large enough characteristic), geometric resolution algorithms [28] can also be used. This class of algorithms culminates with the incremental algorithm in [36, 37] which avoids equiprojectability issues by performing a linear change of variables to ensure Noether position properties. One feature is that input polynomials are encoded with straight-line programs to take advantage of evaluation properties. See also [34] for a similar approach. It also gives the best known complexity for equidimensional decomposition: linear in the evaluation complexity of the input system and polynomial in some algebraic degree.

As of software, the computer algebra systems Singular [16], Macaulay2 [30] and Magma [6] implement the algorithm of [22] to perform equidimensional decomposition. Maple implements algorithms for computing regular chains [14, 13, 9, 10, 39] and algorithms based on Gröbner bases. The algorithm by Gianni et al. [27] is used for prime decomposition and, combined with techniques from [3], for equidimensional decomposition. All these implementations use Gröbner basis algorithms as a black box.

*Main results.* By contrast with previous work, we only focus on computing the nondegenerate locus of a system, not the full equidimensional decomposition of the corresponding ideal. The main difference to other Gröbner basis based tech-
niques to compute equidimensional decompositions is that we enlarge *I* while a Gröbner basis for *I* is computed and return a Gröbner basis of a nondegenerate locus of *I* when this Gröbner basis computation is finished. Modifying or splitting the ideal in question in the middle of Gröbner basis algorithms is a natural and appealing idea [e.g. 29].

This idea requires one to answer (i) when the ideal in question should be enlarged and (ii) how to minimize the cost of enlarging the ideal in question. The algorithm we propose tackles both issues.

We tackle problem (i) by following the incremental structure of certain signature-based Gröbner basis (sGB) algorithms on which our work is based [24, 25, 26]. We describe a version of such an sGB algorithm in section 3. Incremental means here that these algorithms proceed by computing first a Gröbner basis for $\langle f_1, f_2 \rangle$ then use the result to compute a Gröbner basis for $\langle f_1, f_2, f_3 \rangle$ and so on. In addition, sGB algorithms keep track of an auxiliary data structure, called a *signature*, which is attached to each considered polynomial. This enables one to *exclude* certain polynomials from the set of polynomials to be processed by reduction in Buchberger's algorithm.

As a consequence these algorithms have the feature that, having computed a Gröbner basis for $I_{i-1} := \langle f_1, \dots, f_{i-1} \rangle$, a reduction to zero happens in the Gröbner basis computation for $I_i$ if any only if $f_i$ is a zero divisor modulo $I_{i-1}$. In this case $V_{i-1} := V(I_{i-1})$ has irreducible components on which $f_i$ is identically zero (the union of which is henceforth denoted $V_{i-1, f_i=0}$) and components which are not contained in the hypersurface $V(f_i)$ (the union of which is henceforth denoted $V_{i-1, f_i \neq 0}$). Assuming that $V(I_{i-1})$ is equidimensional of codimension $i-1$, to compute an ideal representing the nondegenerate locus of $V(I_i)$ we may then proceed as follows (see Algorithm 1):

1. Compute ideals representing $V_{i-1, f_i=0}$ and $V_{i-1, f_i \neq 0}$ (via the ideal-theoretic operation of saturation).

2. Compute an ideal representing $W := V_{i-1, f_i \neq 0} \cap V(f_i)$.

3. Remove from $W$ all components contained in $V_{i-1, f_i=0}$ (again via saturation).

Iterating over the set of input equations with these three steps, using the result of each iterative step as input for the next invocation of this loop and slightly adapting the third step to remove all components which are contained in components of higher dimension then yields an ideal representing the nondegenerate locus of $I$. We describe this algorithm from a purely algebraic perspective in section 2.

To tackle problem (ii) we exploit a feature of the incremental sGB algorithms first captured in the G2V algorithm [25]: The data of a signature can be enlarged so as to simultaneously compute a Gröbner basis for $I_i$ and the quotient ideal $(I_{i-1} : f_i) := \{g \in R \mid gf_i \in I_{i-1}\}$ (which, if $I_{i-1}$ is a radical ideal, corresponds precisely to $V(I_{i-1, f_i \neq 0})$ in each incremental step.

Using this idea we modify the baseline sGB algorithm we use to simultaneously perform steps 1 and 2 of the above loop (i.e. in a single Gröbner basis
computation). This is done essentially by immediately inserting an element $g \in (I_{i-1} : f_i)$ once it is identified during the run of the sGB algorithm. We manage this insertion of elements that do not lie in the original ideal $I$ with a data structure we call an sGB tree (see section 3.3) which allows us to perform this modification with the needed technical properties of signatures ensured. This yields a signature-based version of Algorithm 1, Algorithm 8. Besides managing the insertion of new generators into some initial ideal, the sGB data structure also leaves open the future possibility of designing signature-based ideal decomposition algorithms.

We finally show experimentally in section 5.2 that the consequence of this simple modification is a massive cost reduction in the overhead compared to a “naive” implementation of Algorithm 1 where one uses saturation procedures as a blackbox. As is also shown, it additionally enables us to compute the nondegenerate locus of systems which are out of the reach of equidimensional decomposition algorithms available in state of the art computer algebra systems.

## 2. The basic algorithm

Consider a codimension $k$ irreducible variety $X \subseteq \overline{\mathbb{K}}^n$ and a polynomial $f \in R$. Assume that $X \cap V(f) \neq \emptyset$. Either $X \subseteq V(f)$, and so $X \cap V(f) = X$, or $X \cap V(f)$ is equidimensional of codimension $k+1$ (that is, all the irreducible components of $X \cap V(f)$ have codimension $k+1$). If $X$ is not irreducible, then $X \cap V(f)$ may not be equidimensional. Yet, the alternative above applies to each irreducible component of $X$. The components of $X$ which are not included in $V(f)$ are exactly the components of the closure of $X \setminus V(f)$, while the components of $X$ which are included in $V(f)$ are exactly the components of the closure of $X \setminus (X \setminus V(f))$. This leads to the decomposition of $X \cap V(f)$ as the union of two equidimensional varieties of codimension $k$ and $k+1$ respectively:

$$X \cap V(f) = (X \setminus \overline{X \setminus V(f)}) \cup (\overline{X \setminus V(f)} \cap V(f)).$$

This is the basic identity that we leverage to compute, incrementally, the codimension $c$ components of an ideal $\langle f_1, \dots, f_c \rangle$. In an ideal theoretic language, this reformulates as follows.

For two ideals $I, J \subseteq R$, we write $I \stackrel{\text{rad}}{=} J$ for the equality of the radicals $\sqrt{I} = \sqrt{J}$. An ideal $I$ is equidimensional if all the irreducible components of $V(I)$ have the same dimension. Recall that $I : J$ is the ideal $\{p \in R \mid pJ \subseteq I\}$. Recall also that $I : J^k$ yields an increasing sequence of ideals as $k \to \infty$, so it eventually stabilizes in an ideal denoted $I : J^\infty$, the saturation of $I$ by $J$. If $J$ is generated by a single element $f$, it is simply denoted $I : f^\infty$.

**Lemma 2.1.** For any ideal $J \subseteq R$ and any $f \in R$ we have

$$J + \langle f \rangle \stackrel{\text{rad}}{=} (\langle J : f^\infty \rangle + \langle f \rangle) \cap (J : (J : f^\infty))$$

Moreover, if $J$ is equidimensional of codimension $c < n$ then $(\langle J : f^\infty \rangle + \langle f \rangle)$ is either the unit ideal or equidimensional of codimension $c+1$ and $(J : (J : f^\infty))$ is either the unit ideal or equidimensional of codimension $c$.
**Proof.** For the left-to-right inclusion, it is clear that $J$ is included in the right-hand side, so it remains to check that $f$ is in the radical of both terms of the intersection. It is obvious that $f \in (J : f^{\infty}) + \langle f \rangle$, so it remains to prove that $f$ is in the radical of $J : (J : f^{\infty})$. So let $g \in J : f^{\infty}$, that is $gf^{\ell} \in J$ for some $\ell \ge 0$, which we may rewrite as $f \in \sqrt{J : g}$. To conclude, we observe that

$$ \sqrt{J : (J : f^{\infty})} = \bigcap_{g \in J : f^{\infty}} \sqrt{J : g}, $$

so $f \in \sqrt{J : (J : f^{\infty})}$.

Conversely, let $p \in ((J : f^{\infty}) + \langle f \rangle) \cap (J : (J : f^{\infty}))$. Write $p = q + af$ where $q \in (J : f^{\infty})$ and $a \in R$. Since $p \in (J : (J : f^{\infty}))$, we have $pq \in J$. But $pq = q^2 + aqf$, so $q^2 \in J + \langle f \rangle$. It follows that $q \in \sqrt{J + \langle f \rangle}$, thus proving the stated equality.

For the statement on equidimensionality, assume that neither of the two ideals on the right hand side are the unit ideal. We may rely on the geometric interpretation above: the zero set of $J : f^{\infty} + \langle f \rangle$ is $\overline{X} \setminus V(f) \cap V(f)$, where $X = V(J)$. It thus only remains to show the equidimensionality of $J : (J : f^{\infty})$. Note that the equidimensionality of $J : (J : f^{\infty})^{\infty}$ is clear because its associated algebraic set consists of the union of the components of $X$ on which $f$ identically vanishes. Now it holds that $J : (J : f^{\infty})^{\text{rad}} = J : (J : f^{\infty})^{\infty}$, see e.g. [33, Proposition 23]. This shows the equidimensionality of $J : (J : f^{\infty})$. $\square$

We are now ready to describe Algorithm 1. To do this we suppose for now that we have an algorithm for computing the quotient ideal $J : K$ and the saturation $J : K^{\infty}$, given generators for $J$ and $K$. Given $c \le n$ elements $f_1, \dots, f_c \in R$ the core loop of Algorithm 1 starts with the ideal $J = \langle f_1 \rangle$ and continuously replaces it with $(J : f_k^{\infty}) + \langle f_k \rangle$ for each $k$. By Lemma 2.1 the resulting ideal will be equidimensional of codimension $c$. Note however that it may have components that the original ideal $I = \langle f_1, \dots, f_c \rangle$ does not have, as shown by the following example. In the algorithm, these additional components are removed with saturations at every iterative step with the loop on line 7.

**Example 2.2.** Let $R = \mathbb{Q}[x, y, z]$ and $f_1 = xy$, $f_2 = xz$. Then $(\langle xy \rangle : xz^{\infty}) + \langle xz \rangle = \langle y, xz \rangle$ which has the component $\langle y, x \rangle$ which is not a component of $\langle f_1, f_2 \rangle = \langle x \rangle \cap \langle y, z \rangle$.

To prove the correctness of Algorithm 1 we also need the following proposition:

**Lemma 2.3.** For any ideals $I, J \subseteq R$ and any $f \in R$, we have

$$ (i) \quad (I \cap J) + \langle f \rangle^{\text{rad}} = (I + \langle f \rangle) \cap (J + \langle f \rangle); $$

$$ (ii) \quad I \cap J^{\text{rad}} = (I : J^{\infty}) \cap J; $$

$$ (iii) \quad \text{if } f \in I, \text{ then } I : J^{\infty} = I : (J + \langle f \rangle)^{\infty}. $$
**Algorithm 1** Computation of the nondegenerate locus

**Input:** A set of generators $f_1, \dots, f_c$ for an ideal $I$ in $R$ where $c \le n$

**Output:** A set of generators $G$ for the nondegenerate part of $f_1, \dots, f_c$

1: $J \leftarrow 0$, as an ideal of $R$

2: $K \leftarrow \emptyset$

3: **for** $k$ from 1 to $c$ **do**

4: &nbsp;&nbsp;&nbsp;&nbsp;$H \leftarrow J : f_k^\infty$

5: &nbsp;&nbsp;&nbsp;&nbsp;$K \leftarrow K \cup \{J : H\}$

6: &nbsp;&nbsp;&nbsp;&nbsp;$J \leftarrow H + \langle f_k \rangle$

7: &nbsp;&nbsp;&nbsp;&nbsp;**for** $K \in K$ **do**

8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$J \leftarrow J : K^\infty$

9: &nbsp;&nbsp;&nbsp;&nbsp;**end for**

10: **end for**

11: **return** $J$

*Proof.* For the first item,

$$(I + \langle f \rangle) \cap (J + \langle f \rangle) \stackrel{\text{rad}}{=} (I + \langle f \rangle)(J + \langle f \rangle) \stackrel{\text{rad}}{=} IJ + \langle f \rangle \stackrel{\text{rad}}{=} (I \cap J) + \langle f \rangle.$$

For the second one, the left-to-right inclusion is clear. Conversely, let $f \in (I : J^\infty) \cap J$ and let $k > 0$ such that $fJ^k \subseteq I$. In particular $f^{k+1} \in I$. So $f \in \sqrt{I}$. For the last item is trivial from the definition of saturation. $\square$

**Theorem 2.4.** On input $f_1, \dots, f_c \in R$ with $c \le n$, Algorithm 1 terminates and outputs an ideal $J$ such that $V(J)$ is the nondegenerate locus of the input system.

*Proof.* We define $J_0 := \langle 0 \rangle$, and then recursively

$$K_i := (J_{i-1} : (J_{i-1} : f_i^\infty)),$$

$$\text{and } J_i := \left( (J_{i-1} : f_i^\infty) + \langle f_i \rangle : \left( \prod_{j=1}^i K_j \right)^\infty \right).$$

It is clear that Algorithm 1 returns the ideal $J_c$. Now, let $I_i = \langle f_1, \dots, f_i \rangle$. The main loop invariant, that we prove by induction on $i$, is

$$I_i \stackrel{\text{rad}}{=} J_i \cap \bigcap_{j=1}^i (K_j + \langle f_{j+1}, \dots, f_i \rangle). \qquad (1)$$

From this, we deduce that the zero set of $J_c$ is contained in the algebraic set defined by $f_1 = \dots = f_c = 0$. We will prove later that $J_c$ is equidimensional of codimension $c$, that the components of the ideals $(K_j + \langle f_{j+1}, \dots, f_c \rangle)$ have codimension less than $c$ and do not contain any components of $J_c$.
It is trivially true that (1) holds for $i = 0$. For $i > 0$, we have

$$ 
\begin{aligned}
I_i = I_{i-1} + \langle f_i \rangle^{\text{rad}} &\equiv \left( J_{i-1} \cap \bigcap_{j=1}^{i-1} (K_j + \langle f_{j+1}, \dots, f_{i-1} \rangle) \right) + \langle f_i \rangle \\
&\equiv (J_{i-1} + \langle f_i \rangle) \cap \bigcap_{j=1}^{i-1} (K_j + \langle f_{j+1}, \dots, f_i \rangle), \quad \text{by Lemma 2.3(i).}
\end{aligned}
$$

Besides, by Lemma 2.1,

$$ 
\begin{aligned}
J_{i-1} + \langle f_i \rangle^{\text{rad}} &\equiv ((J_{i-1} : f_i^{\infty}) + \langle f_i \rangle) \cap (J_{i-1} : (J_{i-1} : f_i^{\infty})) \\
&= ((J_{i-1} : f_i^{\infty}) + \langle f_i \rangle) \cap K_i.
\end{aligned}
$$

For short, let $J'_i = (J_{i-1} : f_i^{\infty}) + \langle f_i \rangle$. Combining the equalities above, we have

$$ 
\begin{aligned}
I_i^{\text{rad}} &= J'_i \cap \bigcap_{j=1}^{i} (K_j + \langle f_{j+1}, \dots, f_i \rangle) \\
&= \text{rad} \left( J'_i : \left( \prod_{j=1}^{i} K_j \right)^{\infty} \right) \cap \bigcap_{j=1}^{i} (K_j + \langle f_{j+1}, \dots, f_i \rangle),
\end{aligned}
$$

using Lemma 2.3(ii) and (iii) (note that $f_1, \dots, f_i \in J'_i$). This last equality is exactly (1).

Now, we analyze the dimensions and show that $V(J_i)$ is exactly the nondegenerate locus of $f_1, \dots, f_i$. Indeed, using Lemma 2.1, we check by induction on $i$ that $J_i$ is equidimensional of codimension $i$ (unless $J_i = \langle 1 \rangle$ in which case the nondegenerate locus of $f_1, \dots, f_i$ is the unit ideal) and that $K_i$ is equidimensional of codimension $i-1$ (unless $K_i = \langle 1 \rangle$ in which case the nondegenerate locus of $f_1, \dots, f_i$ is the one of $f_1, \dots, f_{i-1}$ plus $\langle f_i \rangle$). It follows that all the components of $K_j + \langle f_{j+1}, \dots, f_i \rangle$ have codimension at most $i-1$. Moreover, no component of $J_i$ is included in any $K_j$, for $j \le i$, since $J_i$ is saturated by the $K_j$. Therefore, using (1), the codimension $i$ components of $I_i$ are exactly the components of $J_i$.

Hence, we deduce that $J_c$ is equidimensional of codimension $c$ whose components are not contained in the ones of $K_j + \langle f_{j+1}, \dots, f_c \rangle$, the components of which have codimension less than $c$. Besides, we already observed that its zero set is contained in the one defined by the input polynomials $f_1, \dots, f_c$. Since (1) holds, we conclude that $V(J_c)$ is the nondegenerate locus of the input system. $\square$

### 3. Signature-based Gröbner basis computations

We will rely on the theory of signature-based Gröbner bases in order to efficiently implement Algorithm 1.
### 3.1. Signatures and extended sig-poly pairs

We fix in the following a monomial order on $R$ and a sequence of polynomials $f_1, \dots, f_r \in R$. Let $I := \langle f_1, \dots, f_r \rangle$ and $I_i := \langle f_1, \dots, f_i \rangle$. We describe an algorithm which computes a Gröbner basis for $I$ and presents the following features:

1. It computes a Gröbner basis for $I$ incrementally, i.e. first for $\langle f_1 \rangle$ then for $\langle f_1, f_2 \rangle$ etc.

2. It simultaneously computes Gröbner bases for each ideal $(\langle f_1, \dots, f_{i-1} \rangle : f_i)$, $i = 2, \dots, r$.

This algorithm belongs to the class of so called signature-based Gröbner basis algorithms, the first of which was the F5 algorithm presented in [24]. Since then the class of signature-based algorithms has been greatly extended, see [18] for a survey. The idea of leveraging signature-based algorithms to compute simultaneously some colon ideals first appeared in [25]. The algorithm we present here is closely related, with some elements from the F5 algorithm. The algorithm presented in this section is fully encompassed by the general algorithmic framework presented in [18].

We start by defining signatures.

**Definition 3.1.** A signature is a pair $\sigma = (i, m)$ of an index in $\{1, \dots, r\}$ and a monomial in $R$. The first component is called the *index*, and denoted $\text{ind}(\sigma)$. The second component is called the *monomial part* of $\sigma$.

We order the signatures lexicographically, i.e. by writing

$$ (i, m) < (j, n) \Leftrightarrow i < j \text{ or } i = j \text{ and } m < n. $$

The product of a monomial $a \in R$ and a signature $\sigma = (i, h)$ is defined by $a\sigma = (i, ah)$. A signature $\sigma$ divides another signature $\tau$ if there is a monomial $a$ such that $a\sigma = \tau$, so in particular $\text{ind}(\sigma) = \text{ind}(\tau)$.

The possible indices of a signature are the indices of the input equations. This relation between the index of a signature and one of the equations $f_i$ is made stronger by the following object:

**Definition 3.2.** An *extended sig-poly pair* is a triple $\alpha = (f, \sigma, h)$, where $f, h \in R$ and $\sigma$ is a signature such that $\text{lm}(h)$ is equal to the monomial part of $\sigma$. The first component $f$ is called the *polynomial part* of $\alpha$, denoted $\text{poly}(\alpha)$, the second component $\sigma$ is called the *signature*, denoted $\mathfrak{s}(\alpha)$, and the third component is called the *quotient*, denoted $\text{quo}(\alpha)$. The index of $\alpha$, denoted $\text{ind}(\alpha)$ is the index of its signature. We further impose that

$$ \text{poly}(\alpha) - \text{quo}(\alpha) f_{\text{ind}(\alpha)} \in I_{\text{ind}(\alpha)-1}. \qquad (2) $$

The product of a monomial $a \in R$ and an extended sig-poly pair $\alpha$ is defined by

$$ \text{poly}(a\alpha) = a \text{ poly}(\alpha), \quad \mathfrak{s}(a\alpha) = a\mathfrak{s}(\alpha), \quad \text{and} \quad \text{quo}(a\alpha) = a \text{ quo}(\alpha). $$
<caption>**Algorithm 2 Regular reduction**</caption>

1: **procedure** REGULARREDUCTION(α, G)
2: &nbsp;&nbsp;&nbsp;&nbsp;f ← poly(α)
3: &nbsp;&nbsp;&nbsp;&nbsp;h ← quo(α)
4: &nbsp;&nbsp;&nbsp;&nbsp;**while** R := {(b, β) ∈ R × G | b ln(poly(β)) = ln(f), bS(β) < s(α)} ≠ ∅
5: &nbsp;&nbsp;&nbsp;&nbsp;**do**
6: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(b, β) ← some element in R
7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;f ← f - b poly(β)
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** ind(β) = ind(α) **then**
9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;h ← h - b quo(β)
10: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**end if**
11: &nbsp;&nbsp;&nbsp;&nbsp;**end while**
12: **return** (f, s(α), h)
13: **end procedure**

The concept of an S-pair from Buchberger's algorithm extends to extended sig-poly pairs. Given two extended sig-poly pairs α and β with poly(α) ≠ 0 and poly(β) ≠ 0 let c = lcm(lm(poly(α)), lm(poly(β))), a = c/lt(poly(α)) and b = c/lt(poly(β)), then define the S-pair of α and β, denoted sp(α, β) by

$$ \mathrm{poly}(\mathfrak{s}p(\alpha, \beta)) = a \mathrm{poly}(\alpha) - b \mathrm{poly}(\beta), \quad \mathfrak{s}(\mathfrak{s}p(\alpha, \beta)) = \max(\mathfrak{s}(a\alpha), \mathfrak{s}(b\beta)), $$

and

$$ \mathrm{quo}(\mathfrak{s}p(\alpha, \beta)) = \begin{cases} a \mathrm{quo}(\alpha) & \text{if } \mathrm{ind}(\alpha) > \mathrm{ind}(\beta), \\ a \mathrm{quo}(\alpha) - b \mathrm{quo}(\beta) & \text{if } \mathrm{ind}(\alpha) = \mathrm{ind}(\beta), \\ -b \mathrm{quo}(\beta) & \text{if } \mathrm{ind}(\alpha) < \mathrm{ind}(\beta). \end{cases} $$

In particular, the polynomial part of sp(α, β) is the usual S-pair of poly(α) and poly(β). We say that α and β form a regular S-pair if s(aα) ≠ s(bβ). (We will only consider such S-pairs.) It is easy to check that Invariant (2) is preserved.

The regular reduction of an extended sig-poly pair α with respect to a set G of sig-poly pairs is defined to be the output of Algorithm 2. The procedure tries to reduce the leading term of poly(α) using some multiple bβ of an extended sig-poly pair β ∈ G such that bS(β) < s(α). The procedure stops when there is no such reducer. Compared to the usual division algorithm in polynomial rings, only reduction by lower signature elements is allowed. Moreover, there is some extra computations to preserve Invariant (2).

We may now describe a variant of Buchberger's algorithm using extended sig-poly pairs and regular reduction, see Algorithm 3. In line 6 we always choose the S-pair with minimal signature for reduction, and signatures are ordered first by indices. As a result, signatures are processed in index 1 (which may produce further S-pairs with index ≥ 1), then in index 2 (which may produce further S-pairs with index ≥ 2), etc. So a Gröbner basis for I is computed incrementally: first for ⟨f₁⟩, then for ⟨f₁, f₂⟩ etc. Computing with extended sig-poly pairs
<caption>**Algorithm 3** Buchberger with signatures</caption>

**Input:** $f_1, \dots, f_r \in R$
**Output:** Gröbner bases of $\langle f_1, \dots, f_r \rangle$ and of $\langle f_1, \dots, f_{k-1} \rangle : f_k \ (1 \le k \le r)$
1: **procedure** BUCHBERGER($f_1, \dots, f_r$)
2: &nbsp;&nbsp;&nbsp;&nbsp;$G \leftarrow \{(f_i, (i, 1), 1) \mid 1 \le i \le r\}$
3: &nbsp;&nbsp;&nbsp;&nbsp;$S_1, \dots, S_r \leftarrow \emptyset$
4: &nbsp;&nbsp;&nbsp;&nbsp;$P \leftarrow \{(\alpha, \beta) \mid \alpha, \beta \in G \text{ form a regular S-pair}\}$
5: &nbsp;&nbsp;&nbsp;&nbsp;**while** $P \neq \emptyset$ **do**
6: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$(\alpha, \beta) \leftarrow \text{the pair in } P \text{ with } \mathfrak{s}(\mathfrak{sp}(\alpha, \beta)) \text{ minimal}$
7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$P \leftarrow P \setminus \{(\alpha, \beta)\}$
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\gamma \leftarrow \text{REGULARREDUCTION}(\mathfrak{sp}(\alpha, \beta), G)$
9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$G \leftarrow G \cup \{\gamma\}$
10: &nbsp;&nbsp;&nbsp;&nbsp;**if** $\text{poly}(\gamma) \neq 0$ **then**
11: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$P \leftarrow P \cup \{(\gamma, \beta) \mid \beta \in G, \text{poly}(\beta) \neq 0\}$, forms a regular S-pair with $\gamma$
12: &nbsp;&nbsp;&nbsp;&nbsp;**else** (record the quotient of the zero reduction)
13: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$S_{\text{ind}(\gamma)} \leftarrow S_{\text{ind}(\gamma)} \cup \{\text{quo}(\gamma)\}$
14: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
15: &nbsp;&nbsp;&nbsp;&nbsp;**end while**
16: &nbsp;&nbsp;&nbsp;&nbsp;**return** $\{\text{poly}(\beta) \mid \beta \in G\}, S_1, \dots, S_r$
17: **end procedure**

makes it possible to simultaneously compute a Gröbner basis for $I$ and for all the ideals $\langle\langle f_1, \dots, f_{i-1} \rangle\rangle : f_i$ for $i=2, \dots, r$. Indeed, if for an extended sig-poly pair $\gamma$ we find during the run of Algorithm 3 that $\text{poly}(\gamma) = 0$, then $\text{quo}(\gamma)$ is an element of the quotient ideal $I_{\text{ind}(\gamma)-1} : f_{\text{ind}(\gamma)}$, in view of Definition 3.2.

**Proposition 3.3.** On input $f_1, \dots, f_r \in R$, Algorithm 3 terminates and the set $\{\text{poly}(\alpha) \mid \alpha \in G\}$ is a Gröbner basis of the ideal $\langle f_1, \dots, f_r \rangle$. The sets $S_i$ are Gröbner bases of the ideals $\langle f_1, \dots, f_{i-1} \rangle : f_i$ for each $i = 2, \dots, r$.

We skip the proof as we will only rely on the stronger Theorem 3.5 below.

## 3.2. From Buchberger to sGB

The signature and the quotient of each extended sig-poly pair in the data makes it possible to compute the colon ideals $\langle f_1, \dots, f_{i-1} \rangle : f_i$ as a by-product of an incremental computation of a Gröbner basis of $\langle f_1, \dots, f_r \rangle$. Moreover, this is the discovery of Faugère [24], signatures make it possible to discard many S-pairs while preserving the essential properties of Algorithm 3. The overarching principle is the following: *at most one sig-poly pair has to be regular-reduced at each signature*. This is made precise by the following statement.

**Lemma 3.4** ([20, Lemma 4]). In the course of Algorithm 3, assume that only S-pairs in signature $\sigma \ge \sigma := (i, m)$ are left in $P$. Then for any extended sig-poly pairs $\gamma$ and $\gamma'$ with $\mathfrak{s}(\gamma) = \mathfrak{s}(\gamma') = \sigma$,

$$ \text{poly}(\text{REGULARREDUCTION}(\gamma, G)) = \text{poly}(\text{REGULARREDUCTION}(\gamma', G)) $$
<caption>**Algorithm 4** The rewritability criterion</caption>

**Input:** $\alpha$ an extended sig-poly pair, $m$ a monomial, $G$ a set of extended sig-poly pairs with $\alpha \in G$
**Output:** Returns true if $m\alpha$ is rewritable w.r.t. $G$; false otherwise
1: **procedure** REWRITABLE($\alpha$, $m$, $G$)
2: &nbsp;&nbsp;&nbsp;&nbsp;**for** $\delta \in G$ **do**
3: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $s(\delta)$ divides $s(m\alpha)$ and $\delta$ was added to $G$ later than $\alpha$ **then**
4: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**return** true (Singular criterion)
5: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**else if** $s(\delta)$ divides $s(m\alpha)$ and $\text{poly}(\delta) = 0$ **then**
6: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**return** true (Syzygy criterion)
7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**else if** $\text{ind}(\delta) < \text{ind}(\alpha)$ and $\text{lm}(\text{poly}(\delta))$ divides $\text{lm}(\text{quo}(\alpha))$ **then**
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**return** true (Koszul criterion)
9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**end if**
10: &nbsp;&nbsp;&nbsp;&nbsp;**end for**
11: &nbsp;&nbsp;&nbsp;&nbsp;**return** false
12: **end procedure**

This leads to Algorithm 5. It is similar to Algorithm 3, the only difference is the check on line 9, the *rewritability check*, which trims many computations. At a given signature, this check will retain at most one element of $P$. The condition on line 7 discards even more S-pairs by predicting that they will reduce to zero.

More precisely, in the context of Lemma 3.4, we can predict that all S-pairs with signature $\sigma$ will reduce to the same element. The first effect of the *rewritability check* is the removal of all S-pairs with signature $\sigma$, except at most one. Secondly, Lemma 3.4 may be used to predict that an S-pair will reduce to zero. There are two criteria for that:

**Syzygy criterion** If an element in signature $\tau$ has reduced to zero, then every element in signature $a\tau$ (for any monomial $a$) will reduce to zero;

**Koszul criterion** If we have a sig-poly pair with polynomial part $h$ and index $< \text{ind}(\sigma)$, then every element in signature $(a \text{lm} h, \text{ind}(\sigma))$ will reduce to zero, (because $h f_{\text{ind}(\sigma)}$ will obviously reduce to zero).

This explains the different checks in the rewritability criterion (Algorithm 3.2), see [18, section 7.1] for a detailed discussion.

**Theorem 3.5.** On input $f_1, \dots, f_r \in R$, Algorithm 5 terminates and outputs subsets $G, S_1, \dots, S_r$ of $R$ such that:

(i) $G$ is a Gröbner basis of $\langle f_1, \dots, f_r \rangle$;

(ii) $I_{i-1} + \langle S_i \rangle = I_{i-1} : f_i$.

Moreover, on line 15, when a polynomial $g$ is inserted in some $S_i$, then $\text{lm}(g)$ is not divisible by the leading monomial of any element of $I_{i-1}$ or any element previously inserted in $S_i$.
<caption>**Algorithm 5** sGB with recording of syzygies</caption>

**Input:** $f_1, \dots, f_r \in R$
**Output:** See Theorem 3.5
1: **procedure** sGB($f_1, \dots, f_r$)
2: &nbsp;&nbsp;&nbsp;&nbsp;G $\leftarrow \{(f_i, (i, 1), 1) \mid 1 \le i \le r\}$
3: &nbsp;&nbsp;&nbsp;&nbsp;$S_1, \dots, S_r \leftarrow \emptyset$
4: &nbsp;&nbsp;&nbsp;&nbsp;$P \leftarrow \{(\alpha, \beta) \mid \alpha, \beta \in G \text{ form a regular S-pair}\}$
5: &nbsp;&nbsp;&nbsp;&nbsp;**while** $P \ne \emptyset$ **do**
6: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$(\alpha, \beta) \leftarrow \text{the element in } P \text{ with minimal signature}$
7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$P \leftarrow P \setminus \{(\alpha, \beta)\}$
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$a, b \leftarrow \text{the monomials such that } a \text{ poly}(\alpha) - b \text{ poly}(\beta) = \text{poly}(sp(\alpha, \beta))$}
9: &nbsp;&nbsp;&nbsp;&nbsp;**if** not REWRITABLE($\alpha, a, G$) and not REWRITABLE($\beta, b, G$) **then**
10: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\gamma \leftarrow \text{REGULARREDUCTION}(sp(\alpha, \beta), G)$
11: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$G \leftarrow G \cup \{\gamma\}$
12: &nbsp;&nbsp;&nbsp;&nbsp;**if** $\text{poly}(\gamma) \ne 0$ **then**
13: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$P \leftarrow P \cup \{(\gamma, \beta) \mid \beta \in G, \text{poly}(\beta) \ne 0, \text{ forms a regular S-pair with } \gamma\}$
14: &nbsp;&nbsp;&nbsp;&nbsp;**else** (record the quotient of the zero reduction)
15: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$S_{\text{ind}(\gamma)} \leftarrow S_{\text{ind}(\gamma)} \cup \{\text{quo}(\gamma)\}$
16: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
17: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
18: &nbsp;&nbsp;&nbsp;&nbsp;**end while**
19: &nbsp;&nbsp;&nbsp;&nbsp;**return** $\{\text{poly}(\beta) \mid \beta \in G\}, S_1, \dots, S_r$

20: **end procedure**
*Proof.* Termination and the first two points are a special case of [18, Theorem 7.1], where we only compute partial information about the syzygy module.

The last point is a consequence from the rewritability check. We first note that every time a polynomial $h$ is inserted into $S_i$, the extended sig-poly pair $(0, (i, \mathrm{lm} \, h), h)$ has been inserted into $G$ just before. (The monomial part of the signature is always the leading monomial of the quotient, this is an invariant of sig-poly pairs.) Next, in the context of line 15, if $g = \mathrm{quo}(\gamma)$, then $\mathfrak{s}(\gamma) = (\mathrm{ind}(\gamma), \mathrm{lm}(g))$. Moreover, $\gamma$ comes from a S-pair $\mathfrak{sp}(\alpha, \beta)$, so $\mathfrak{s}(\gamma) = \mathrm{as}(\alpha)$ or $\mathrm{bs}(\beta)$, and both REWRITABLE($\alpha$, $a$, $G$) and REWRITABLE($\beta$, $b$, $G$) were false.

The Syzygy criterion implies that $\mathfrak{s}(\gamma)$ is not divisible by any $\mathfrak{s}(\delta)$, where $\delta \in G$ and $\mathrm{poly}(\delta) = 0$. In other words, $\mathrm{lm}(g)$ is not divisible by any $\mathrm{lm} \, h$, where $h$ has been previously inserted into $S_i$.

The Koszul criterion implies that $\mathrm{lm}(g)$ is not divisible by any $\mathrm{lm}(\mathrm{poly}(\delta))$, where $\delta \in G$ and $\mathrm{ind}(\delta) < i$. But due to the incremental nature of the algorithm, the set $\{\mathrm{poly}(\delta) \mid \delta \in G, \mathrm{ind}(\delta) < i\}$ is a Gröbner basis of $I_{i-1}$. So $\mathrm{lm}(g)$ is not divisible by any element in $I_{i-1}$. $\square$

### 3.3. The sGB tree datastructure

#### 3.3.1. Specification

We now specify a data structure, called sGB tree. It is meant to extend the sGB algorithm presented above in two ways: by offering the possibility to add new input equations during the computation; and by offering the possibility to split the computation into different branches while sharing the common base.

An sGB tree represents a rooted tree $T$ where each node holds an element of the polynomial ring $R$. The nodes are partially ordered by the ancestor- descendant relation: $\nu \leq_T \mu$ if $\nu$ is on the unique path from $\mu$ to the root of $T$ (or, equivalently, if $\mu$ is in the subtree rooted at $\nu$). For a node $\nu$, the polynomial contained in $\nu$ is denoted $\mathrm{poly}(\nu)$, and the ideal generated by the polynomials contained by the ancestors of $\nu$ (not including $\nu$) is denoted $I_{<\nu}$. An sGB tree offers the following three operations. How we implement them is the matter of the next section.

**Node insertion** Insert a new node, containing a given polynomial $f$, anywhere in the tree, as a new leaf or on an existing edge. Denoted `INSERTNODE($T$, $f$, position)`.

**Gröbner basis** Given a node $\nu$, outputs a Gröbner basis of the ideal generated by the polynomials contained in the nodes $\leq_T \nu$. Denoted `BASIS($T$, $\nu$)`.

**Get a syzygy** Given a node $\nu$, outputs an element of $I_{<\nu} : \mathrm{poly}(\nu)$. Denoted `GETSYZYGY($T$, $\nu$)`.

If `GETSYZYGY($T$, $\nu$)` outputs zero, then $I_{<\nu} + J = I_{<\nu} : \mathrm{poly}(\nu)$, where $J$ is the ideal generated by all previous invocations of `GETSYZYGY($T$, $\nu$)`.

It is guaranteed that `GETSYZYGY($T$, $\nu$)` eventually outputs zero after sufficiently many invocation, even if nodes are inserted or `GETSYZYGY` is called on other nodes in between.
### 3.3.2. Implementation

From the point of implementation, an sGB tree is made of:

(a) a rooted tree $T$ whose nodes are labelled with integer IDs;

(b) a set $G$ of extended sig-poly pairs whose indices are nodes of $T$ (see below);

(c) a set $P$ of pairs of elements of $G$ forming regular S-pairs;

(d) for each node $\nu$ of $T$, a subset $S_\nu$ of $R$.

The sets $G$, $P$ and $S_\nu$ have the same role as their counterparts in the sGB algorithm (Algorithm 5). The main difference is a twist in the definition of signatures and indices. In §3.1, an index (that is the first component of a signature) is a nonnegative integer. From now on, indices are nodes in $T$. Indices are partially ordered by the ancestor-descendant relation $\le_T$. Note that for a given node $\nu$, the subset $\{\mu \mid \mu \le_T \nu\}$ is totally ordered: it is the set of nodes on the path from the root of $T$ to $\nu$. Lastly, we adjust the definition of a regular S-pair. We say that sig-poly pairs $\alpha$ and $\beta$ form a regular S-pair if $\text{ind}(\alpha)$ and $\text{ind}(\beta)$ are comparable (that is either $\text{ind}(\alpha) \le_T \text{ind}(\beta)$ or $\text{ind}(\beta) \le_T \text{ind}(\alpha)$) and $\mathfrak{s}(\alpha\alpha) \neq \mathfrak{s}(\beta\beta)$, with $a$ and $b$ as in §3.1. To analyze the behavior of the sGB tree data structure, we always consider totally ordered subsets of indices, thus reducing to the context of Algorithm 5.

To implement $\text{BASIS}(\mathcal{T}, \nu)$, we process the S-pairs with index $\le_T \nu$. The indices of these S-pairs are totally ordered, so we are actually in the situation of §3.2 and we may apply the main loop of Algorithm 5. The body of this loop is isolated in the procedure $\text{PROCESSSPAIR}$ (Algorithm 6), with the appropriate alterations.

The implementation of $\text{GETSYZYGY}(\mathcal{T}, \nu)$ is similar, with the difference that we abort the computation as soon as the set $S_\nu$ is not empty and return an element of it, see Algorithm 6. If $S_\nu$ is still empty after having processed all S-pairs which may lead to new elements in $S_\nu$, the value 0 is returned.

We assume that the state of a sGB tree always results from a sequence of calls to $\text{INSERTNODE}$, $\text{BASIS}$ or $\text{GETSYZYGY}$ applied to an initially empty tree.

**Proposition 3.6.** Let $\mathcal{T}$ be a sGB tree and let $\nu$ be a node of $\mathcal{T}$. $\text{BASIS}(\mathcal{T}, \nu)$ (Algorithm 6) terminates and outputs a Gröbner basis of $I_{\le \nu} := \{\text{poly}(\mu) \mid \mu \le \nu\}$.

*Proof.* This algorithm considers only S-pairs whose signatures are above a given node $\nu$. After this restriction, the signatures are totally ordered, so $\text{BASIS}$ behaves exactly like Algorithm 5 (sGB). We note that, contrary to sGB, $\text{BASIS}$ may start in a state where several S-pairs have already been processed, in an unspecified order, by earlier calls to $\text{BASIS}$ or $\text{GETSYZYGY}$ on different nodes. This does not invalidate neither the termination proof given in [20], nor the proof of correctness. $\square$

**Proposition 3.7.** Let $\mathcal{T}$ be a sGB tree and let $\nu$ be a node of $\mathcal{T}$. $\text{GETSYZYGY}(\mathcal{T}, \nu)$ (Algorithm 6) terminates and outputs some $f \in R$ such that:
**Algorithm 6 Implementation of the sGB tree data structure**

**Input:** An sGB tree $\mathcal{T}$ and a label $\nu$ of $T$

**Output:** Process the pair in $P$ with index above $\nu$ with smallest signature

1: **procedure** PROCESSSPAIR($\mathcal{T}$, $\nu$)

2: (restrict to S-pairs whose indices are above $\nu$)

3: $P' \leftarrow \{(\alpha, \beta) \mid \alpha, \beta \in G, \max\{\mathrm{ind}(\alpha), \mathrm{ind}(\beta)\} <_T \nu\}$

4: **if** $P' \neq \emptyset$ **then**

5: $(\alpha, \beta) \leftarrow \text{the pair in } P' \text{ with } \mathfrak{s}(\mathfrak{sp}(\alpha, \beta)) \text{ minimal}$

6: $P \leftarrow P \setminus \{(\alpha, \beta)\}$

7: $a, b \leftarrow \text{the monomials such that } a \mathrm{poly}(\alpha) - b \mathrm{poly}(\beta) = \mathrm{poly}(\mathfrak{s}p(\alpha, \beta))$

8: **if** not REWRITABLE($\alpha$, $a$, $G$) and not REWRITABLE($\beta$, $b$, $G$) **then**

9: $\gamma \leftarrow \mathrm{REGULARREDUCTION}(\mathfrak{s}p(\alpha, \beta), G)$

10: $G \leftarrow G \cup \{\gamma\}$

11: **if** $\mathrm{poly}(g) \neq 0$ **then**

12: $P \leftarrow P \cup \{(\gamma, \beta) \mid \beta \in G, \mathrm{poly}(\beta) \neq 0, \text{ forms a regular S-pair with } \gamma\}$

13: **else** (record the quotient of the zero reduction)

14: $S_{\mathrm{ind}(\gamma)} \leftarrow S_{\mathrm{ind}(\gamma)} \cup \{\mathrm{quo}(\gamma)\}$

15: **end if**

16: **end if**

17: **end if**

18: **end procedure**

**Input:** A sGB tree $\mathcal{T}$ and a label $\nu$ of $T$

**Output:** A Gröbner basis of $I_{<\nu}$

1: **procedure** BASIS($\mathcal{T}$, $\nu$)

2: **while** there is a pair in $P$ with index $\leq_T \nu$ **do**

3: PROCESSSPAIR($\mathcal{T}$, $\nu$)

4: **end while**

5: **return** $\{\mathrm{poly}(\alpha) \mid \alpha \in G \text{ and } \mathrm{ind}(\alpha) \leq_T \nu\}$

6: **end procedure**

**Input:** A sGB tree $\mathcal{T}$ and a label $\nu$ of $T$

**Output:** An element of the quotient ideal $I_{<\nu} : \mathrm{poly}(\nu)$ not contained in $I_{<\nu}$

1: **procedure** GETSYZYGY($\mathcal{T}$, $\nu$)

2: **while** there is a pair in $P$ with index $\leq_T \nu$ **and** $S_\nu = \emptyset$ **do**

3: PROCESSSPAIR($\mathcal{T}$, $\nu$)

4: **end while**

5: **if** $S_\nu \neq \emptyset$ **then**

6: **pick and remove some** $h$ **in** $S_\nu$

7: **return** $h$

8: **else**

9: **return** 0

10: **end if**

11: **end procedure**
**Algorithm 7** The sGB tree data structure, insertion of a node

**Input:** A sGB tree $\mathcal{T}$, a polynomial $f$ and a description of the position of the new node in $\mathcal{T}$

**Output:** The label of the newly inserted node

1: **procedure** INSERTNODE($\mathcal{T}$, $f$, position)

2: $\nu \leftarrow (\text{largest label in } \mathcal{T}) + 1$

3: insert a node in $\mathcal{T}$ with label $\nu$, as described by "position"

4: $S_\nu \leftarrow \emptyset$

5: $\epsilon \leftarrow (f, (\nu, 1), 1)$

6: $P \leftarrow \{(\epsilon, \beta) \mid \beta \in G \text{ and } (\epsilon, \beta) \text{ forms a regular S-pair}\}$

7: $G \leftarrow G \cup \{\epsilon\}$

8: **return** $\nu$

9: **end procedure**

(i) $f \in I_{<\nu} : \text{poly}(\nu);$

(ii) if $f \neq 0$, then $\text{lm}(f)$ is not divisible by the leading monomial of any other polynomial previously output by GETSYZYGY($\mathcal{T}$, $\nu$), or any polynomial in $I_{<\nu}$;

(iii) if $f = 0$, then $I_{<\nu} : \text{poly}(\nu)$ is generated by $I_{<\nu}$ and the polynomials previously output by GETSYZYGY($\mathcal{T}$, $\nu$).

*Proof.* Termination follows from the termination of BASIS since the main loop is similar, but with the possibility of earlier termination. Correctness follows from Theorem 3.5 after restricting to indices above $\nu$. $\square$

As a consequence of Proposition 3.7(ii), it is guaranteed that GETSYZYGY($\mathcal{T}$, $\nu$) eventually outputs zero after sufficiently many invocation, even if nodes are inserted or GETSYZYGY is called on other nodes in between. Indeed, the leading monomial of a nonzero output of GETSYZYGY($\mathcal{T}$, $\nu$) is constrained to be outside the monomial ideal generated by the leading monomials of previous output. By Dickson's lemma, this may only happen finitely many times.

## 4. Computation of the nondegenerate locus

The sGB tree data structure can be used to implement an efficient variant of Algorithm 1 for computing the nondegenerate locus. We use an sGB tree to efficiently compute saturations $I : f^\infty$, and also double quotient $I : (I : f^\infty)$, with the idea to exploit as soon as possible newly discovered relations to simplify further computations. This leads to Algorithm 8, which we describe informally as follows.

Similarly to Algorithm 1, we introduce the equations $f_1, \dots, f_r$ one after the other. We maintain a sGB tree which, at the beginning of the $k$th iteration,
that is after having processed $f_1, \dots, f_{k-1}$, has the following shape:

$$ g_1 \leftarrow f_1 \leftarrow p_1 \leftarrow \dots \leftarrow g_{k-1} \leftarrow f_{k-1} \leftarrow p_{k-1} \leftarrow \underbrace{0}_{\nu} \leftarrow h_2, \dots $$

where bold letters represent a sequence of zero, one or several nodes. The tree grows from the node labeled $\nu$, by adding new leaf nodes, or inserting nodes just above $\nu$. Using the notations of Algorithm 1, the nodes $g_i$ are related to the saturation by the $f_i$, the leaf nodes $h_i$ are generic elements of the ideals in the set $\mathcal{K}$, and the nodes $p_i$ are related to the cleaning steps $G: K^\infty$. We added $g_1$ for the consistency of the above picture although it will always be empty and so $f_1$ is the root of the tree.

**Remark 4.1** (Deterministic variant). The leaf nodes $h_i$ are generic in the sense that they are linear combinations of generators of the ideals in $\mathcal{K}$ where all coefficients are either random scalars or new variables. Algorithm 8 chooses either a random scalar or a new variable in line 12. For a randomized algorithm, favoring speed over certain correctness, choose $t$ to be a random scalar, this choice is justified by lemma 4.2. For a deterministic algorithm, choose $t$ to be a slack variable, unused in the input equation. It is guaranteed that such a $t$ is generic enough. In this case the monomial order on $R$ has to be extended to $R[t]$ by a monomial order that eliminates $t$. The implementation discussed in the next section exclusively chooses $t$ to be a random scalar.

The $k$th iteration proceeds as follows. Firstly, a new node $\mu$ containing $f_k$ is created just above $\nu$:

$$ \dots \leftarrow \underbrace{f_k}_{\mu} \leftarrow \underbrace{0}_{\nu} \leftarrow \dots $$

As long as $\text{GETSYZYGY}(\mathcal{T}, \mu)$ returns nonzero elements $(g_1, g_2, \dots)$, we insert them above $\mu$:

$$ \dots \leftarrow g_1 \leftarrow g_2 \leftarrow \dots \leftarrow \underbrace{f_k}_{\mu} \leftarrow \underbrace{0}_{\nu} \leftarrow \dots $$

This saturation has the effect of completing $I_{<\mu}$ into $I_{<\mu}: f_k^\infty$. Each time we insert a polynomial $g_i$ in a node, say $\gamma$, we also record the syzygies $\text{GETSYZYGY}(\mathcal{T}, \gamma)$, take a generic linear combination and insert it as a new leaf node. These syzygies are related to the double quotient $I_{<\mu}: (I_{<\mu}: f_k^\infty)$. Before going to the next iteration, insert above $\nu$ all the syzygies obtained from the children of $\nu$. Which again has the effect of saturating $I_{<\nu}$ by the polynomials contained in these nodes.

After all the input equations have been processed, the ideal $I_{<\nu}$ is a nondegenerate part of the input ideal, which we prove by comparing with Algorithm 1.

**Lemma 4.2.** Let $I, J \subseteq R$ be two ideals with $J = \langle g_1, \dots, g_u \rangle$.
**Algorithm 8** Computation of the nondegenerate locus with an sGB tree

**Input:** $f_1, \dots, f_c \in \mathbb{R}$

**Output:** A Gröbner basis $G$ of a nondegenerate locus of $(f_1, \dots, f_c)$

1: $\mathcal{T} \leftarrow$ an empty sGB tree

2: $\nu \leftarrow \text{INSERTNODE}(\mathcal{T}, 0)$

3: **for** $k$ from 1 to $c$ **do**

4: &nbsp;&nbsp;&nbsp;&nbsp; $\mu \leftarrow \text{INSERTNODE}(\mathcal{T}, f_k)$, just above $\nu$

5: **loop**

6: &nbsp;&nbsp;&nbsp;&nbsp; $g \leftarrow \text{GETSYZYGY}(\mathcal{T}, \mu)$

7: &nbsp;&nbsp;&nbsp;&nbsp; **if** $g = 0$ **then**

8: &nbsp;&nbsp;&nbsp;&nbsp; **break**

9: **end if**

10: &nbsp;&nbsp;&nbsp;&nbsp; $\gamma \leftarrow \text{INSERTNODE}(\mathcal{T}, g)$, just above $\mu$

11: &nbsp;&nbsp;&nbsp;&nbsp; $h \leftarrow 0$

12: &nbsp;&nbsp;&nbsp;&nbsp; $t \leftarrow$ a random scalar (or the slack variable, see Remark 4.1)

13: **loop**

14: &nbsp;&nbsp;&nbsp;&nbsp; $h' \leftarrow \text{GETSYZYGY}(\mathcal{T}, \gamma)$

15: &nbsp;&nbsp;&nbsp;&nbsp; **if** $h' = 0$ **then**

16: &nbsp;&nbsp;&nbsp;&nbsp; **break**

17: **end if**

18: &nbsp;&nbsp;&nbsp;&nbsp; $h \leftarrow th + h'$

19: **end loop**

20: &nbsp;&nbsp;&nbsp;&nbsp; $\text{INSERTNODE}(\mathcal{T}, h)$, as a child of $\nu$

21: **end loop**

22: **for** all child $\beta$ of $\nu$ **do**

23: **loop**

24: &nbsp;&nbsp;&nbsp;&nbsp; $b \leftarrow \text{GETSYZYGY}(\mathcal{T}, \beta)$

25: &nbsp;&nbsp;&nbsp;&nbsp; **if** $b = 0$ **then**

26: &nbsp;&nbsp;&nbsp;&nbsp; **break**

27: **end if**

28: &nbsp;&nbsp;&nbsp;&nbsp; $\text{INSERTNODE}(\mathcal{T}, b)$, just above $\nu$

29: **end loop**

30: **end for**

31: **end for**

32: **return** $\text{Basis}(\nu)$
1. If $S = R[t_1, \dots, t_u]$ then $(I : J^\infty) = (IS : (\sum_{j=1}^u t_j g_j)^\infty) \cap R$.

2. There exists a Zariski-open subset $D \subset \mathbb{K}^u$ such that for any $(a_1, \dots, a_u) \in D$ we have $(I : J^\infty) = (I : (\sum_{j=1}^u a_j g_j)^\infty)$.

3. If $K \stackrel{\text{rad}}{=} J$ then $(I : K^\infty) \stackrel{\text{rad}}{=} (I : J^\infty)$.

*Proof.* (1) and (2) follows e.g. from [21, Exercise 15.41]. For (3), if $p \in R$ such that $p^k J^l \subset I$ for $k, l \in \mathbb{N}$ then for a suitably large $m \in \mathbb{N}$ we have $K^m \subseteq J^l$ so $p^k K^m \subset I$ and hence $p \in \sqrt{(I : K^\infty)}$. $\square$

**Theorem 4.3.** *Algorithm 8 terminates. Algorithm 8 is correct, provided that one chooses t as a new variable in line 12 or that t is chosen as a random scalar in a suitable Zariski open subset of $\mathbb{K}$.*

*Proof.* Termination follows from the assumption that for any node $\nu$ of an sGB tree $\mathcal{T}$, GETSYZYGY($\mathcal{T}$, $\nu$) eventually returns 0 after sufficiently many calls.

To prove correctness, we show that Algorithm 8 computes the same ideal as Algorithm 1. Let $J_{k-1}$ be the value of $I_\nu$ at the beginning of the $k$th iteration. After line 4, we also have $I_{<\mu} = J_{k-1}$, while $I_{<\nu} = I_{<\mu} + \langle f_k \rangle$.

We first examine the loop on line 5. It inserts above the node $\mu$ all the polynomials obtained from GETSYZYGY($\mathcal{T}$, $\mu$). Every node inserted on line 10 is in $I_{<\mu} : f_k$. No other node is inserted above $\mu$. So by induction, it follows that all along the loop, we have $J_{k-1} \subseteq I_{<\mu} \subseteq J_{k-1} : f_k^\infty$. Moreover, after the loop terminates, we have $I_{<\mu} : f_k = I_{<\mu}$, due to the specification of GETSYZYGY (Proposition 3.7). If now $g \in J_{k-1} : f_k^\infty$ then $g \in I_{<\mu} : f_k^\infty = I_{<\mu}$ and so all in all it follows that before line 22, we have

$$I_{<\mu} = J_{k-1} : f_k^\infty \quad \text{and} \quad I_{<\nu} = (J_{k-1} : f_k^\infty) + \langle f_k \rangle. \qquad (3)$$

Next, we examine the loop on line 22 and its inner loop on line 23. By the same argument as above, the inner loop has the effect of saturating $I_{<\nu}$ by $\text{pol}(\beta)$. So after the loop on line 22, we have

$$I_{<\nu} = J_k = ((J_{k-1} : f_k^\infty) + \langle f_k \rangle) : \left( \prod_{\beta \text{ child of } \nu} \text{pol}(\beta) \right)^\infty. \qquad (4)$$

It remains to understand the nature of the children of $\nu$. They all come from the insertion of $h$ on line 20. And $h$ is simply a generic linear combination of the return values of GETSYZYGY($\mathcal{T}$, $\gamma$). So $h$ is a generic linear combination of some $h_1, \dots, h_r$ such that $I_{<\gamma} + \langle h_1, \dots, h_r \rangle = I_{<\gamma} : \text{poly}(\gamma)$ (by Proposition 3.7). For each node $\gamma$ inserted on line 10, let $L_\gamma$ denote the ideal $I_{<\gamma} : \text{poly}(\gamma)$. If $g_1, \dots, g_s$ are the successive return values of GETSYZYGY($\mathcal{T}$, $\mu$) on line 6, and $\gamma_1, \dots, \gamma_r$ the corresponding nodes, we have $L_{<\gamma_i} = I_{<\gamma_i} : g_i$ and $I_{<\gamma_i} = J_{k-1} + \langle g_1, \dots, g_i \rangle$. By Lemma 4.4, it follows that

$$L_{\gamma_1} \cap \dots \cap L_{\gamma_r} \stackrel{\text{rad}}{=} J_{k-1} : \langle g_1, \dots, g_r \rangle^\infty. \qquad (5)$$
Moreover, by (3), we obtain that before line 22

$$I_{<\mu} = J_{k-1} + \langle g_1, \dots, g_r \rangle = J_{k-1} : f_k^{\infty}, \qquad (6)$$

so, combining with (5),

$$L_{\gamma_1} \cap \dots \cap L_{\gamma_r} \stackrel{\text{rad}}{=} J_{k-1} : \langle g_1, \dots, g_r \rangle^{\infty} \qquad (7)$$

$$= J_{k-1} : (J_{k-1} + \langle g_1, \dots, g_r \rangle)^{\infty} \qquad (8)$$

$$\stackrel{\text{rad}}{=} J_{k-1} : (J_{k-1} : f_k^{\infty}). \qquad (9)$$

As remarked above, the loop on line 23 has the effect of saturating $I_{<\nu}$ by $\text{pol}(\beta)$. By the analysis above, $\text{pol}(\beta)$ is actually a generic linear combination of some $h_1, \dots, h_r$ such that $I_{<\gamma} + \langle h_1, \dots, h_r \rangle = L_{\gamma}$, for some node $\gamma$ above $\nu$. By Lemma 4.2, saturating by $\text{pol}(\beta)$ is the same as saturating by $\langle h_1, \dots, h_r \rangle$ (assuming that $\text{pol}(\beta)$ is sufficiently generically in the case where Algorithm 8 chooses random scalars in line 12). Besides, $I_{<\nu}$ contains $I_{<\gamma}$, so saturating $I_{<\nu}$ by $\langle h_1, \dots, h_r \rangle$ is the same as saturating by $L_{\gamma}$. Back to (4), we conclude from (9) that saturating $I_{<\nu}$ by all the $\text{pol}(\beta)$ is the same as saturating by all the ideals $J_{i-1} : (J_{i-1} : f_i^{\infty})$, for $i \le k$.

Therefore $J_k$ satisfies the same recurrence relation as its analogue defined the proof of Theorem 2.4:

$$J_k = \left( (J_{k-1} : f_k^{\infty}) + \langle f_k \rangle \right) : \left( \bigcap_{i \le k} (J_{i-1} : (J_{i-1} : f_i^{\infty})) \right)^{\infty}. \qquad (10)$$

This proves that Algorithm 8 and Algorithm 1 compute the same ideal. $\square$

**Lemma 4.4.** Let $I, J \subseteq R$ be two ideals and let $J = \langle g_1, \dots, g_t \rangle$. Then

$$(I : J)^{\text{rad}} = (I : g_1) \cap ((I + \langle g_1 \rangle) : g_2) \cap \dots \cap ((I + \langle g_1, \dots, g_{t-1} \rangle) : g_t).$$

*Proof.* The inclusion $\subseteq$ is obvious. Now, let $p \in R$ be such that

$$p^m \in (I : g_1) \cap ((I + \langle g_1 \rangle) : g_2) \cap \dots \cap ((I + \langle g_1, \dots, g_{t-1} \rangle) : g_t)$$

for some $m \in \mathbb{N}$. Then we have in particular $p^m g_1 \in I$. Now let $i > 1$. By induction, if for some $k \in \mathbb{N}$ we have $p^k g_j \in I$ for all $j \le i$ then

$$p^{km} g_{i+1} = p^k f + p^k a_1 g_1 + \dots + p^k a_i g_i \in I$$

for a suitable $f \in I$, $a_1, \dots, a_i \in R$ and so $p^{km} \in (I : g_{i+1})$. We deduce that a power of $p$ actually lies in $(I : J)$ which ends the proof. $\square$

# 5. Implementation and Experiments

## 5.1. Further Implementational Considerations

We start by describing some further optimizations in our implementations of Algorithms 5 and 8.
Both these implementations use an F4-like reduction strategy. This means that several S-pairs are selected out of the pairset at once and are subsequently, together with their regular reducers, organized in a matrix whose rows are labeled by the selected extended sig-poly pairs and whose columns are labeled by all the monomials occuring in the polynomial parts of these extended sig-poly pairs. This matrix is then put into row echelon form and the rows of this reduced matrix whose first entry has changed during the computation of this row echelon form are then processed as new basis elements or newly identified zero divisors, depending on if this reduced row is zero or not. Compared to the original F4 algorithm, one has to make sure during the computation of this row echelon form that a row is only reduced by rows whose corresponding sig-poly pair has lower signature. We refer to [23] for details on the original F4 algorithm or to [18, section 13] for a more thorough explanation as to how to combine the F4 algorithm with signature-based techniques.

For Algorithm 8, this has the consequence that the GETSYZYGY routine has the ability to return several zero divisors $g_1, \dots, g_s$ at once and Algorithm 8 may benefit from it. We implemented the following probabilistic optimization: We replaced $g_1$ by a random linear combination $g'_1 := \sum_{j=1}^s a_j g_i$. Let $\nu_1, \dots, \nu_s$ be the nodes assigned to $g'_1, g_2, \dots, g_s$ in Algorithm 8. Then, if the choice of the $a_i$ was “sufficiently random”, we know by Lemma 4.2 that for $h \in R$ we have

$$hg'_1 \in I_{<\nu_1} \Leftrightarrow hg_i \in I_{<\nu_1} \forall i.$$

If then GETSYZYGY($\mathcal{T}$, $\nu_1$) returned such an element $h \neq 0$ we regarded the signatures $(\nu_2, \mathrm{lm}(h)), \dots, (\nu_s, \mathrm{lm}(h))$ as known signatures of syzygies during the calls to RWRITEABLE, i.e. GETSYZYGY($\mathcal{T}$, $\nu_i$) would, for $i = 2, \dots, s$, only return a non-zero result if there exists an element $h' \in (I_{<\nu_i} : g_i)$ with $\mathrm{lm}(h')$ not divisible by $\mathrm{lm}(h)$. Furthermore, only the zero divisors $h$ of $g'_1$ as above were considered in the loop from line 14-20 of Algorithm 8.

We implemented both Algorithm 5 and 8 in the programming language Julia [5] with an interface to the Singular.jl Julia-library [16]. An interface to the new computer algebra system OSCAR [1] is planned for the future. The implementation is available at

https://github.com/RafaelDavidMohr/SignatureGB.jl

In this implementation we use our own data structures for polynomials and polynomial arithmetic. The linear algebra routines for computing row echelon forms in our implementations closely follow the corresponding routines presented in [41]. Additionally, our implementation makes use of the modifications to Algorithm 5 presented in [19]. Currently the implementation works only for fields of finite characteristic.

While our implementation is currently not competitive with optimized implementations of Gröbner basis algorithms such as in Maple [40] or msolve [4], we do make use of some standard optimization techniques in Gröbner basis algorithm implementations such as monomial hash tables and divisor bitmasks (see e.g. [42] for a description of these techniques).
## 5.2. Experimental Results

We used the following examples to benchmark our implementations. All computations were made over the field $\mathbb{Z}/65521\mathbb{Z}$

1. Cyclic(8), coming from the classical Cyclic(n) benchmark.

2. Pseudo(n), encoding pseudo-singularities via polynomials

$$f_1, \dots, f_{n-1}, g_1, \dots, g_{n-1}$$

with $f_i \in \mathbb{K}[x_1, \dots, x_{n-2}, z_1, z_2]$, $g_i \in \mathbb{K}[y_1, \dots, y_{n-2}, z_1, z_2]$, the $f_i$ being chosen as a random dense quadrics, and $g_i$ chosen such that $g_i(x_1, \dots, x_{n-2}, z_1, z_2) = f$, i.e. as a copy of $f_i$ in the variables $y_1, \dots, y_{n-2}, z_1, z_2$.

3. Sos(s, n), encoding the critical points of the restriction of the projection on the first coordinate to a hypersurface which is a sum of s random dense quadrics in $\mathbb{K}[x_1, \dots, x_n]$.

$$f, \frac{\partial f}{\partial x_2}, \dots, \frac{\partial f}{\partial x_n}, \quad f = \sum_{i=1}^{s} g_i^2.$$

4. Sing(n), encoding the critical points of the restriction of the projection on the first coordinate to a (generically singular) hypersurface which is defined by the resultant of two random dense quadrics A, B in $\mathbb{K}[x_1, \dots, x_{n+1}]$:

$$f, \frac{\partial f}{\partial x_2}, \dots, \frac{\partial f}{\partial x_n}, \quad f = \text{resultant}(A, B, x_{n+1}).$$

5. The Steiner polynomial system, coming from [7].

All these systems are generated by a number of polynomials equal to the number of variables of the underlying polynomial ring. They all have components of different dimensions, one of those being zero-dimensional, i.e. they have a nontrivial nondegenerate locus.

In Table 1 we compare Algorithm 8 and a straightforward implementation of ours of Algorithm 1 in Maple. In this implementation, we saturated an ideal $J$ by an ideal $K$ by picking a random linear combination $p$ of generators of $K$ and saturating $J$ by $p$ using Maple's internal saturation routine. Table 1 shows the improvement of Algorithm 8 over Algorithm 1: While Maple's highly optimized Gröbner basis engine beats our implementation of Algorithm 5 by a wide margin the ratio between the timings of our F5 implementation and our implementation of Algorithm 8 is much better than the ratio between the time it took to compute a Gröbner basis in Maple and our Maple implementation of Algorithm 1. This indicates that the overhead over a Gröbner basis computation incurred by Algorithm 1 is significantly reduced by bringing in signature-based techniques as in Algorithm 8. This can be seen by looking at the two respect "ratio"-columns of table 1. To additionally show the overhead of Algorithm 8
over Algorithm 5 we noted the number of arithmetic operations in $K$ when running each of the two algorithms on the polynomial system in question. Our implementation of Algorithm 8 never takes more than 10 times the number of arithmetic operations Algorithm 5 takes, on certain examples we compare very favorably in terms of arithmetic operations to Algorithm 5.

In Table 2 we compare Algorithm 8 to other ideal decomposition methods available in the computer algebra systems Singular, Maple and Macaulay2 [30]. In Singular there is an elimination method [15] and an implementation of the algorithm for equidimensional decomposition presented in [22]. In Maple we compared against the Regular Chains package [11, 10]. In Macaulay2 one is able to compute the intersection of all components of non-minimal dimension again with the method presented in [22]. We then saturated the original ideal by the result to obtain the nondegenerate locus. On a high level, our algorithm works similarly, incrementally obtaining information about the component of higher dimension and then removing it via saturation. One should keep in mind that all of these methods, compared to Algorithm 8, work more generally: Except for what we tried in Macaulay2 they are all able to obtain a full equidimensional decomposition of the input ideal.

We gave all of these methods at least an hour for each polynomial system and at most roughly 50 times the time our implementation of Algorithm 8 took. We indicated when these times were exceeded by using ">" in Table 2. We computed all examples on a single Intel Xeon Gold 6244 CPU @ 3.60GHz with a limit of 200G memory. If this limit was exceeded, or if another segfault occurred, we indicate it with 'segfault' in Table 2.
<table><caption>Table 1: Comparing Algorithm 1 and Algorithm 8</caption><thead><tr><th></th><th>Alg. 5 arith. op.</th><th>Alg. 8 arith. op.</th><th>Alg. 5</th><th>Alg. 8</th><th>Ratio</th><th>GB in Maple</th><th>Alg. 1 in Maple</th><th>Ratio</th></tr></thead><tbody><tr><td>Cyclic 8</td><td>1.2 · 10<sup>10</sup></td><td>1.3 · 10<sup>11</sup></td><td>4m</td><td>40m</td><td>10</td><td>1.2s</td><td>154m</td><td>7700</td></tr><tr><td>Pseudo(2, 12)</td><td>5.3 · 10<sup>7</sup></td><td>3.1 · 10<sup>8</sup></td><td>1.16s</td><td>5.2s</td><td>4.5</td><td>0.268s</td><td>3.44s</td><td>13</td></tr><tr><td>Sing(2, 10)</td><td>5.6 · 10<sup>7</sup></td><td>6.5 · 10<sup>7</sup></td><td>1.9s</td><td>2.9s</td><td>1.5</td><td>0.11s</td><td>1.642s</td><td>14.5</td></tr><tr><td>Sing(2, 9)</td><td>2.5 · 10<sup>7</sup></td><td>2.9 · 10<sup>7</sup></td><td>1.1s</td><td>1.4s</td><td>1.27</td><td>0.06s</td><td>0.788s</td><td>13.1</td></tr><tr><td>Sos(2,5,4)</td><td>1.3 · 10<sup>8</sup></td><td>1.1 · 10<sup>8</sup></td><td>8.5s</td><td>7.3s</td><td>0.85</td><td>0.022s</td><td>0.479s</td><td>21.3</td></tr><tr><td>Sos(2,6,3)</td><td>2.1 · 10<sup>7</sup></td><td>2.1 · 10<sup>7</sup></td><td>1.11s</td><td>1.4s</td><td>1.26</td><td>0.021s</td><td>0.261s</td><td>12.4</td></tr><tr><td>Sos(2,6,4)</td><td>4.8 · 10<sup>9</sup></td><td>3.8 · 10<sup>9</sup></td><td>148s</td><td>169s</td><td>1.14</td><td>0.172s</td><td>22.7s</td><td>132</td></tr><tr><td>Sos(2,6,5)</td><td>4.2 · 10<sup>9</sup></td><td>2.0 · 10<sup>9</sup></td><td>75s</td><td>43s</td><td>0.57</td><td>0.458s</td><td>10.38s</td><td>22.7</td></tr><tr><td>Sos(2,7,3)</td><td>1.3 · 10<sup>8</sup></td><td>6.7 · 10<sup>8</sup></td><td>5.2s</td><td>41s</td><td>7.9</td><td>0.047s</td><td>7.162s</td><td>152.4</td></tr><tr><td>Sos(2,7,4)</td><td>6.5 · 10<sup>9</sup></td><td>4.5 · 10<sup>10</sup></td><td>3m</td><td>32m</td><td>10.7</td><td>0.433s</td><td>1h</td><td>8314</td></tr><tr><td>Sos(2,7,5)</td><td>7.2 · 10<sup>10</sup></td><td>3.5 · 10<sup>11</sup></td><td>25m</td><td>20h</td><td>48</td><td>2.294s</td><td>>359h</td><td>> 4.4 · 10<sup>6</sup></td></tr><tr><td>Sos(2,7,6)</td><td>1.7 · 10<sup>12</sup></td><td>3.0 · 10<sup>12</sup></td><td>31h</td><td>73h</td><td>2.4</td><td>14.348s</td><td>5.5h</td><td>23</td></tr><tr><td>Steiner</td><td>3.1 · 10<sup>10</sup></td><td>2.3 · 10<sup>11</sup></td><td>4.2m</td><td>42m</td><td>10</td><td>27s</td><td>13m</td><td>28.9</td></tr></tbody></table>

<table><caption>Table 2: Comparing with other Decomposition Methods</caption><thead><tr><th></th><th>Algorithm 8</th><th>Singular: Elimination Method</th><th>Singular: Algorithm in [22]</th><th>Maple: Regular Chains</th><th>Macaulay2</th></tr></thead><tbody><tr><td>Cyclic 8</td><td>40m</td><td>segfault</td><td>>35h</td><td>>35h</td><td>>35h</td></tr><tr><td>Pseudo(2, 10)</td><td>0.3s</td><td>40s</td><td>>1h</td><td>>1h</td><td>>1h</td></tr><tr><td>Pseudo(2, 12)</td><td>5.2s</td><td>>1h</td><td>>1h</td><td>>1h</td><td>>1h</td></tr><tr><td>Pseudo(2, 6)</td><td>0.008s</td><td><1s</td><td><1s</td><td>0.29s</td><td>0.07s</td></tr><tr><td>Pseudo(2, 8)</td><td>0.03s</td><td><1s</td><td>23m</td><td>5.82s</td><td>13.78s</td></tr><tr><td>Sing(2, 10)</td><td>2.9s</td><td>>1h</td><td>>1h</td><td>>1h</td><td>>1h</td></tr><tr><td>Sing(2, 4)</td><td>0.02s</td><td>1s</td><td>>1h</td><td>91.32s</td><td>0.42s</td></tr><tr><td>Sing(2, 5)</td><td>0.07s</td><td>4s</td><td>>1h</td><td>>1h</td><td>1.94s</td></tr><tr><td>Sing(2, 6)</td><td>0.15s</td><td>56s</td><td>>1h</td><td>>1h</td><td>16.64s</td></tr><tr><td>Sing(2, 7)</td><td>0.35s</td><td>8m</td><td>>1h</td><td>>1h</td><td>289s</td></tr><tr><td>Sing(2, 8)</td><td>0.68s</td><td>23m</td><td>>1h</td><td>>1h</td><td>>1h</td></tr><tr><td>Sing(2, 9)</td><td>1.4s</td><td>>1h</td><td>>1h</td><td>>1h</td><td>>1h</td></tr><tr><td>Sos(2,4,2)</td><td>0.03s</td><td><1s</td><td><1s</td><td>19.4s</td><td>0.16s</td></tr><tr><td>Sos(2,4,3)</td><td>0.03s</td><td>1s</td><td>3m</td><td>14m</td><td>0.63s</td></tr><tr><td>Sos(2,5,2)</td><td>0.02s</td><td><1s</td><td>>1h</td><td>>1h</td><td>0.37s</td></tr><tr><td>Sos(2,5,3)</td><td>0.34s</td><td>>1h</td><td>>1h</td><td>>1h</td><td>9.35s</td></tr><tr><td>Sos(2,5,4)</td><td>7.3s</td><td>>1h</td><td>>1h</td><td>>1h</td><td>183s</td></tr><tr><td>Sos(2,6,2)</td><td>0.17s</td><td><1s</td><td>>1h</td><td>>1h</td><td>0.7s</td></tr><tr><td>Sos(2,6,3)</td><td>1.4s</td><td>>1h</td><td>>1h</td><td>>1h</td><td>107s</td></tr><tr><td>Sos(2,6,4)</td><td>169s</td><td>>140m</td><td>>140m</td><td>>140m</td><td>>140m</td></tr><tr><td>Sos(2,6,5)</td><td>43s</td><td>>1h</td><td>>1h</td><td>>1h</td><td>>1h</td></tr><tr><td>Sos(2,7,2)</td><td>2.91s</td><td><1s</td><td>>1h</td><td>2.94s</td><td>0.18s</td></tr><tr><td>Sos(2,7,3)</td><td>41s</td><td>>1h</td><td>>1h</td><td>>1h</td><td>>1h</td></tr><tr><td>Sos(2,7,4)</td><td>32m</td><td>>26h</td><td>segfault</td><td>>26h</td><td>>26h</td></tr><tr><td>Sos(2,7,5)</td><td>20h</td><td>segfault</td><td>segfault</td><td>>200h</td><td>>200h</td></tr><tr><td>Sos(2,7,6)</td><td>73h</td><td>segfault</td><td>segfault</td><td>>334h</td><td>>500h</td></tr><tr><td>Steiner</td><td>42m</td><td>>50h</td><td>segfault</td><td>>50h</td><td>>50h</td></tr></tbody></table>

*Acknowledgments.* We wish to thank the two anonymous referees for their helpful remarks and suggestions which allowed us to improve the exposition of several results in this article.

References

[1] OSCAR – open source computer algebra research system, version 0.7.1, 2022.
[2] P. Aubry, D. Lazard, and M. Moreno Maza. On the Theories of Triangular Sets. *Journal of Symbolic Computation*, 28(1):105–124, 1999.

[3] T. Becker and V. Weispfenning. *Gröbner Bases*, volume 141 of *Graduate Texts in Mathematics*. Springer-Verlag, New York, 1993.

[4] J. Berthomieu, C. Eder, and M. Safey El Din. Msolve: A library for solving polynomial systems. In *ISSAC'21*, Saint Petersburg, Russia, 2021.

[5] J. Bezanson, A. Edelman, S. Karpinski, and V. B. Shah. Julia: A fresh approach to numerical computing. *SIAM review*, 59(1):65–98, 2017.

[6] W. Bosma, J. Cannon, and C. Playoust. The Magma algebra system. I. The user language. *Journal of Symbolic Computation*, 24(3-4):235–265, 1997.

[7] P. Breiding, B. Sturmfels, and S. Timme. 3264 conics in a second. *Notices of the American Mathematical Society*, 67(1):30–37, 2020.

[8] M. Caboara, P. Conti, and C. Traverse. Yet another ideal decomposition algorithm. In *Applied Algebra, Algebraic Algorithms and Error-Correcting Codes*, Lecture Notes in Computer Science, pages 39–54. Springer, 1997.

[9] C. Chen, O. Golubitsky, F. Lemaire, M. M. Maza, and W. Pan. Comprehensive triangular decomposition. In *International Workshop on Computer Algebra in Scientific Computing*, pages 73–101. Springer, 2007.

[10] C. Chen, F. Lemaire, M. M. Maza, W. Pan, and Y. Xie. Efficient computations of irredundant triangular decompositions with the regularchains library. In *International Conference on Computational Science*, pages 268–271. Springer, 2007.

[11] C. Chen and M. Moreno Maza. Algorithms for computing triangular decomposition of polynomial systems. *Journal of Symbolic Computation*, 47(6):610–642, 2012.

[12] S.-C. Chou and X.-S. Gao. Ritt-Wu's decomposition algorithm and geometry theorem proving. In *10th International Conference on Automated Deduction*, Lecture Notes in Computer Science, pages 207–220. Springer, 1990.

[13] X. Dahan, X. Jin, M. M. Maza, and E. Schost. Change of order for regular chains in positive dimension. *Theoretical Computer Science*, 392(1-3):37–65, 2008.

[14] X. Dahan, M. Moreno Maza, E. Schost, W. Wu, and Y. Xie. Lifting techniques for triangular decompositions. In *ISSAC'05*, pages 108–115. ACM, New York, 2005.

[15] W. Decker, G.-M. Greuel, and G. Pfister. Primary decomposition: Algorithms and comparisons. In *Algorithmic Algebra and Number Theory*, pages 187–220. Springer, 1999.
[16] W. Decker, G.-M. Greuel, G. Pfister, and H. Schönemann. Singular 4-3-0
— A computer algebra system for polynomial computations, 2022.

[17] J. Della Dora, C. Dicrescenzo, and D. Duval. About a new method for computing in algebraic number fields. In *Research Contributions from the European Conference on Computer Algebra-Volume 2*, EUROCAL '85, pages 289–290. Springer-Verlag, 1985.

[18] C. Eder and J.-C. Faugère. A survey on signature-based algorithms for computing Gröbner bases. *Journal of Symbolic Computation*, 80:719–784, 2017.

[19] C. Eder and J. Perry. F5C: A variant of Faugère's F5 algorithm with reduced gröbner bases. *Journal of Symbolic Computation*, 45(12):1442–1458, 2010.

[20] C. Eder and B. H. Roune. Signature rewriting in Gröbner basis computation. In *Proceedings of ISSAC 2013*, pages 331–338. ACM, 2013.

[21] D. Eisenbud. *Commutative Algebra: With a View toward Algebraic Geometry*. Springer New York, New York, NY, 1995.

[22] D. Eisenbud, C. Huneke, and W. Vasconcelos. Direct methods for primary decomposition. *Inventiones Mathematicae*, 110(1):207–235, Dec. 1992.

[23] J.-C. Faugère. A new efficient algorithm for computing Gröbner bases (F4). *Journal of Pure and Applied Algebra*, 139(1):61–88, 1999.

[24] J.-C. Faugère. A new efficient algorithm for computing Gröbner bases without reduction to zero (F5). In *ISSAC'02*, pages 75–83, 2002.

[25] S. Gao, Y. Guan, and F. Volny IV. A new incremental algorithm for computing Gröbner bases. In *ISSAC'10*, pages 13–19, 2010.

[26] S. Gao, F. Volny IV, and M. Wang. A new framework for computing Gröbner bases. *Mathematics of computation*, 85(297):449–465, 2016.

[27] P. Gianni, B. Trager, and G. Zacharias. Gröbner bases and primary decomposition of polynomial ideals. *Journal of Symbolic Computation*, 6(2):149–167, 1988.

[28] M. Giusti, G. Lecerf, and B. Salvy. A Gröbner free alternative for polynomial system solving. *Journal of Complexity*, 17(1):154–211, 2001.

[29] H.-G. Gräbe. Minimal primary decomposition and factorized Gröbner bases. *Applicable Algebra in Engineering, Communication and Computing*, 8(4):265–278, 1997.

[30] D. R. Grayson and M. E. Stillman. Macaulay2, a software system for research in algebraic geometry. Available at http://www.math.uiuc.edu/Macaulay2/.
[31] G.-M. Greuel and G. Pfister. *A Singular Introduction to Commutative Algebra*. Springer Berlin Heidelberg, second edition, 2007.

[32] E. Hubert. Notes on triangular sets and triangulation-decomposition algorithms I. In *Symbolic and Numerical Scientific Computation*, Lecture Notes in Computer Science, pages 1–39. Springer, 2003.

[33] Y. Ishihara and K. Yokoyama. Effective localization using double ideal quotient and its implementation. In V. P. Gerdt, W. Koepf, W. M. Seiler, and E. V. Vorozhtsov, editors, *Computer Algebra in Scientific Computing*, Lecture Notes in Computer Science, pages 272–287. Springer, 2018.

[34] G. Jeronimo and J. Sabia. Effective equidimensional decomposition of affine varieties. *Journal of Pure and Applied Algebra*, 169(2):229–248, Apr. 2002.

[35] T. Krick and A. Logar. An algorithm for the computation of the radical of an ideal in the ring of polynomials. In *AAECC 1991*, pages 195–205. Springer-Verlag, 1991.

[36] G. Lecerf. Computing an equidimensional decomposition of an algebraic variety by means of geometric resolutions. In *ISSAC'00*, pages 209–216, 2000.

[37] G. Lecerf. Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers. *Journal of Complexity*, 19(4):564–596, Aug. 2003.

[38] F. Lemaire, M. Moreno Maza, W. Pan, and Y. Xie. When does $\langle T \rangle$ equal $\mathrm{sat}(T)$? *Journal of Symbolic Computation*, 46(12):1291–1305, 2011.

[39] X. Li, M. Moreno Maza, and W. Pan. Computations modulo regular chains. In *ISSAC'09*, pages 239–246. ACM, New York, 2009.

[40] Maplesoft, a division of Waterloo Maple Inc.. Maple, 2021.

[41] M. Monagan and R. Pearce. A compact parallel implementation of F4. In *Proceedings of the 2015 International Workshop on Parallel Symbolic Computation*, pages 95–100, 2015.

[42] B. H. Roune and M. Stillman. Practical gröbner basis computation. In *ISSAC'12*, pages 203–210, 2012.

[43] W. Vasconcelos. *Computational Methods in Commutative Algebra and Algebraic Geometry*. Algorithms and Computation in Mathematics. Springer-Verlag, 1998.

[44] D. Wang. An elimination method for polynomial systems. *Journal of Symbolic Computation*, 16(2):83–114, Aug. 1993.

[45] D. Wang. *Elimination Methods*. Texts and Monographs in Symbolic Computation. Springer Vienna, 2001.
[46] W.-T. Wu. Basic principles of mechanical theorem proving in elementary geometries. 2(3):221–252, Sept. 1986.