# Computing Generic Fibers of Polynomial Ideals with FGLM and Hensel Lifting

Jérémy Berthomieu, Rafael Mohr

► To cite this version:

Jérémy Berthomieu, Rafael Mohr. Computing Generic Fibers of Polynomial Ideals with FGLM and Hensel Lifting. 49th International Symposium on Symbolic and Algebraic Computation, Jul 2024, Raleigh, NC, United States. pp.307-315, 10.1145/3666000.3669703. hal-04440914v2

HAL Id: hal-04440914

https://hal.science/hal-04440914v2

Submitted on 11 Sep 2024

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_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Computing Generic Fibers of Polynomial Ideals
with FGLM and Hensel Lifting

Jérémy Berthomieu

Sorbonne Université, CNRS, LIP6

F-75005 Paris, France

jeremy.berthomieu@lip6.fr

Rafael Mohr

Sorbonne Université, CNRS, LIP6

F-75005 Paris, France

Rheinland-Pfälzische Technische Universität

Kaiserslautern-Landau, Fachbereich Mathematik

G-67663 Kaiserslautern, Germany

rafael.mohr@lip6.fr

ABSTRACT

We describe a version of the FGLM algorithm that can be used to compute generic fibers of positive-dimensional polynomial ideals. It combines the FGLM algorithm with a Hensel lifting strategy. In analogy with Hensel lifting, we show that this algorithm has a complexity quasi-linear in the number of terms of certain m-adic expansions we compute. Some provided experimental data also demonstrates the practical efficacy of our algorithm.

CCS CONCEPTS

• Computing methodologies → Algebraic algorithms; • Theory of computation → Design and analysis of algorithms.

KEYWORDS

Gröbner basis; polynomial system solving; change of monomial order; Hensel lifting

ACM Reference Format:

Jérémy Berthomieu and Rafael Mohr. 20NN. Computing Generic Fibers of Polynomial Ideals with FGLM and Hensel Lifting. In *Proceedings of the 20NN International Symposium on Symbolic and Algebraic Computation (ISSAC 'NN)*, July XX-YY, 20NN, City, ZZ, USA. ACM, New York, NY, USA, 9 pages. https://doi.org/10.xxxx/xxxxxxx.xxxxxxx

# 1 INTRODUCTION

*Scientific Context.* Gröbner bases lie at the forefront of the algo-
rithmic treatment of polynomial systems and ideals in symbolic
computation. They are defined as special generating sets of polyno-
mial ideals which allow to decide the ideal membership problem via

a multivariate version of polynomial long division. Given a Gröb-
ner basis for a polynomial ideal, a lot of geometric and algebraic
information about the polynomial ideal at hand can be extracted,
such as the degree, dimension or Hilbert function. We refer to [3]
for a comprehensive treatment of the subject.

Notably, Gröbner bases depend on two parameters: The polynomial ideal which they generate and a *monomial order*, i.e. a certain kind of total order on the set of monomials of the underlying polynomial ring. Then, the geometric and ideal-theoretic information that can be extracted from a Gröbner basis depends on the chosen monomial order. For example, *elimination orders* allow, as the name suggests, to eliminate a chosen subset of variables from the given polynomial ideal (i.e. to project on an affine subspace in a geometric sense). While Gröbner bases for elimination orders are frequently of interest, it has been observed that all algorithms to compute Gröbner bases based on the famous Buchberger algorithm [10], such as F<sub>4</sub> [17] and F<sub>5</sub> [18], are substantially more well-behaved when used with non-elimination orders (most notably, the *degree reverse lexicographical* <sub>drl</sub> order).

This has motivated the design of numerous *change of order* algo-
rithms: The task is to convert a given Gröbner basis w.r.t. one
order into a Gröbner basis w.r.t. another order. We mention here
the Hilbert-driven algorithm by [38], the Gröbner walk algorithm
by [11] and, most notably for this paper, the FGLM algorithm [20]
and its variants [6, 19, 21, 31].

Furthermore, most ideal-theoretic operations in commutative alge-
bra (such as saturation and intersection) can be performed using
Gröbner bases by writing down a certain ideal associated to the
given polynomial ideal, choosing a certain monomial order and
computing a Gröbner basis for this associated ideal. Here, Gröb-
ner basis computation is used as a black box. It has recently been
observed, partly by the authors of this paper, that it can be (some-
times substantially) more efficient to design *dedicated* Gröbner basis
algorithms for specific ideal-theoretic tasks, see [5, 16].

*Problem Statement & Contributions.* This paper is concerned with the algorithmic treatment of the following problem: Fix a polynomial ring $R := K[z, x]$ in two finite sets of variables $x$ and $z$ over a field $K$ and an ideal $I$ in $R$. Assume that the map $\varphi : K[z] \to K[z, x]/I$ is injective and has *generically finite fiber*, i.e. assume that the the *generic fiber* $I^{\text{gen}} := I \cdot K(z)[x]$ of $I$ is zero-dimensional. Given a Gröbner basis of $I$ w.r.t. a monomial order $<_{\text{in}}$, we want to compute a Gröbner basis $G$ of $I^{\text{gen}}$ w.r.t. another monomial order $<_{\text{out}}$. One key motivation to solve this problem is that, when $<_{\text{out}}$ is a suitable elimination order, the Gröbner basis $G$ can be used to

The authors are supported by the joint ANR-FWF ANR-19-CE48-0015 ECARP and ANR-22-CE91-0007 EAGLES projects, ANR-19-CE40-0018 DE RERUM NATURA project, DFG Sonderforschungsbereich TRR 195 project and grants DIMRFSI 2021-02-C21/1131 of the Paris Ile-de-France Region, FA8665-20-1-7029 of the EORD-AFOSR, and Forschungsinitiative Rheinland-Pfalz. We thank the referees for their valuable comments on the paper and Ch. Eder, P. Lairez, V. Neiger and M. Safey El Din for fruitful discussions.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org.

ISSAC 'NN, July XX-YY, 20NN, City, ZZ, USA

© 20NN Copyright held by the owner/author(s). Publication rights licensed to ACM.
ACM ISBN xxx-x-xxxx-xxxx-x/xx/xx...$yy.00
https://doi.org/10.xxxx/xxxxxxx.xxxxxx
compute a primary decomposition of the ideal I (or an irreducible decomposition of the algebraic set defined by I), see [3] for details. Being able to compute such decompositions has numerous applications, we mention for example the algorithm presented in [27] which uses primary decompositions to compute so-called Whitney stratifications of singular varieties.

The algorithm we design to solve this problem relates to the two research directions previously mentioned: It is a dedicated algorithm to perform an ideal-theoretic operation (by computing a representation of the generic fiber of a suitably chosen map) and it performs a change of order (by going from $<_{in}$ to $<_{out}$). Our proposed solution to this problem can be seen as a combination of the previously mentioned FGLM algorithm with classical Hensel lifting techniques. More precisely, if we let $\mathfrak{m} := \langle z \rangle$, then, under some assumptions which are detailed in this paper, we will compute G by computing its image in $(\mathbb{K}[z]/\mathfrak{m})[x] \simeq \mathbb{K}[x]$ and then lifting it modulo higher and higher powers of $\mathfrak{m}$. This lifting step uses the same core idea as the FGLM algorithm. With this approach, we expect that our algorithm can be transported without much difficulty to the setting where a Gröbner basis G of a zero-dimensional ideal in $\mathbb{Q}[x]$ is required: Given p a well-chosen prime number and $k \in \mathbb{N}^*$ sufficiently large, it would extract G from its image in $(\mathbb{Z}/p\mathbb{Z})[x]$ and then lift it modulo $p^k$. We show that, similar to classical Hensel lifting, our algorithm runs in arithmetic complexity quasi-linear in the number of terms of degree at most the precision up to which we need to lift when a “quadratic lifting strategy” is chosen, see Corollary 4.7, which implies in particular the following

**THEOREM 1.1.** Let $f_1, \dots, f_c$ be generic polynomials of respective degrees $d_1, \dots, d_c$ in $\mathbb{K}[z, x]$. Assume that the $<_{\text{drl}}$-Gröbner basis of $I = \langle f_1, \dots, f_c \rangle$ is known and that the $<_{\text{out}}$-Gröbner basis G of $I \cdot \mathbb{K}(z)[x]$ has coefficients which are rational functions with degrees at most $\delta$ in the numerators and denominators. Let $m_{2\delta}$ be the number of monomials in z up to degree $2\delta$. Then, one can compute G up to precision $2\delta$ using $\tilde{O}(m_{2\delta c}(d_1 \cdots d_c)^3)$ operations in $\mathbb{K}$.

Note that knowing G up to precision $2\delta$ is enough to recover G by means of Padé approximants, see Lemma 3.6.

**Related Work.** Gröbner bases of generic fibers, as defined in the previous paragraph, are classically computed using block monomial orders, see e.g. [3, Lemma 8.93]. Besides that, morally similar to our algorithm, there is a rich body of literature about multi-modular Gröbner basis computations [1, 14, 32, 37] and Hensel/modular lifting techniques for Gröbner bases [25, 34, 39].

Outside of the world of Gröbner bases, there are other data structures for algorithmically manipulating polynomial ideals, or the algebraic sets defined by them, which encode polynomial ideals by their generic fiber associated to a well-chosen projection. We mention in particular geometric resolutions, see e.g. [24, 33], and triangular sets, see e.g. [28] for a survey.

Our work also relates to specialization results for Gröbner basis, i.e. results on the question whether a Gröbner basis remains a Gröbner basis after specializing some of the variables, see [2, 23, 29].

**Outline.** In Section 2, we give necessary preliminaries both on Gröbner bases and on the needed commutative algebra to state and prove the correctness of our algorithms in Section 3. In Section 4, we transport the complexity statements for the original FGLM algorithm

to our setting. Finally we give some benchmarks for a Julia implementation of our main algorithm in Section 5, comparing it to computing generic fibers using just elimination orders.

# 2 PRELIMINARIES

## 2.1 Gröbner Bases

In order to be self-contained, we recall some definitions and basic properties related to Gröbner bases of polynomial ideals.

For a set of variables $\mathbf{x} := \{x_1, \dots, x_n\}$, we denote by $\text{Mon}(\mathbf{x})$ the set of monomials in $\mathbf{x}$, and for a field $\mathbb{K}$, we let $R := \mathbb{K}[\mathbf{x}]$ be the multivariate polynomial ring in $\mathbf{x}$ over $\mathbb{K}$.

**Definition 2.1.** A monomial order $<_{\mathbf{x}}$ on $\mathbf{x}$ is a total order on $\text{Mon}(\mathbf{x})$

(1) extending the partial order on $\text{Mon}(\mathbf{x})$ given by divisibility and

(2) compatible with multiplication, i.e. we have

$$u < v \Rightarrow wu < wv \quad \forall u, v, w \in \text{Mon}(\mathbf{x}).$$

Of importance for us is the degree reverse lexicographic order:

**Definition 2.2.** The degree reverse lexicographic $<_{\text{drl}}$ order on $\text{Mon}(\mathbf{x})$ is defined as follows for $u, v \in \text{Mon}(\mathbf{x})$: $u <_{\text{drl}} v$ iff $\text{deg} u < \text{deg} v$ or $\text{deg} u = \text{deg} v$ and the last nonzero exponent of $u/v$ is positive.

We will also need the notion of a block order:

**Definition 2.3.** Let $\mathbf{x}$ and $\mathbf{z}$ be two finite sets of variables. Write each monomial $u \in \text{Mon}(\mathbf{x} \cup \mathbf{z})$ uniquely as a product $u = u_{\mathbf{x}}u_{\mathbf{z}}$ with $u_{\mathbf{x}} \in \text{Mon}(\mathbf{x})$ and $u_{\mathbf{z}} \in \text{Mon}(\mathbf{z})$. Fix a monomial order $<_{\mathbf{x}}$ on $\text{Mon}(\mathbf{x})$ and a monomial order $<_{\mathbf{z}}$ on $\text{Mon}(\mathbf{z})$. The corresponding block order eliminating $\mathbf{x}$ is defined as follows: $u < v$ iff $u_{\mathbf{x}} <_{\mathbf{z}} v_{\mathbf{x}}$ or $u_{\mathbf{x}} = v_{\mathbf{x}}$ and $u_{\mathbf{z}} <_{\mathbf{z}} v_{\mathbf{z}}$ for $u, v \in \text{Mon}(\mathbf{x} \cup \mathbf{z})$.

A monomial order on $\mathbf{x}$ yields a notion of leading monomial in $R$:

**Definition 2.4.** Let $<_{\mathbf{z}}$ be a monomial order on $\text{Mon}(\mathbf{x})$. For a nonzero element $f \in R$ the leading monomial of $f$ w.r.t. $<_{\mathbf{z}}$, denoted $\text{lm}_{<_{\mathbf{z}}}(f)$, is the $<_{\mathbf{z}}$-largest monomial in the support of $f$. For a finite set $F$ in $R$ we define $\text{lm}_{<_{\mathbf{z}}}(F) := \{\text{lm}_{<_{\mathbf{z}}}(f) \mid f \in F\}$. For an ideal $I$ in $R$ we define the leading monomial ideal of $I$ as $\text{lm}_{<_{\mathbf{z}}}(I) := \langle \text{lm}_{<_{\mathbf{z}}}(f) \mid f \in I \rangle$.

Fixing a monomial order gives normal forms for images of elements in quotient rings of $R$:

**Definition 2.5.** Let $I$ be an ideal in $R$ and let $<_{\mathbf{z}}$ be a monomial order on $\text{Mon}(\mathbf{x})$.

(1) The set $S_{I, <_{\mathbf{z}}} := \{u \in \text{Mon}(\mathbf{x}) \mid u \notin \text{lm}_{<_{\mathbf{z}}}(I)\}$ is the staircase of $I$ w.r.t. $<_{\mathbf{z}}$. It naturally forms a $\mathbb{K}$-vector space basis of $R/I$.

(2) The image of every element $f \in R$ in $R/I$ can be uniquely written as a $\mathbb{K}$-linear combination of elements in $S_{I, <_{\mathbf{z}}}$, This linear combination of elements in $S_{I, <_{\mathbf{z}}}$ is called the normal form of $f$ w.r.t. $I$ and $<_{\mathbf{z}}$. The corresponding vector of coefficients of this linear combination, with the elements in $S_{I, <_{\mathbf{z}}}$ ordered by $<_{\mathbf{z}}$, will be denoted $\text{nf}_{I, <_{\mathbf{z}}}(f)$.

We finally define the notion of Gröbner bases.

**Definition 2.6.** A Gröbner basis of an ideal $I \subset R$ w.r.t. a monomial order $<_{\mathbf{z}}$ is a finite set $G \subset I$ such that $\langle \text{lm}_{<_{\mathbf{z}}}(G) \rangle = \text{lm}_{<_{\mathbf{z}}}(I)$. A Gröbner basis is called reduced if, for any $g \in G$, no monomial in the support of $g$ is divisible by any element in $\text{lm}_{<_{\mathbf{z}}}(G \setminus \{g\})$.
A Gröbner basis $G$ of an ideal $I \subset R$ w.r.t. a monomial order $< \text{en-}$ables the computation of normal forms w.r.t. $I$ and $< \text{via a straight-}$forward multivariate generalization of polynomial long division, see e.g. [3, Table 5.1]. This, in particular, yields an ideal membership test for $I$. Indeed, an element $f \in R$ is contained in $I$ if and only if its normal form w.r.t. $I$ and $< \text{is zero. Finally, recall that reduced}$ Gröbner bases are unique for a given ideal and monomial order.

## 2.2 Points of Good Specialization

We start by fixing some notation. For an element $f \in R$ we denote by $R[f^{-1}]$ the localization of $R$ at the multiplicatively closed set $\{f^k | k \in \mathbb{N}\}$. For a prime ideal $\mathfrak{p} \subset R$ we denote by $R_{\mathfrak{p}}$ the localization of $R$ at the multiplicatively closed set $R \setminus \mathfrak{p}$.

We further fix a polynomial ring $\mathbb{K}[\mathbf{z}, \mathbf{x}]$ in two finite sets of variables $\mathbf{z}$ and $\mathbf{x}$. Let $I \subseteq \mathbb{K}[\mathbf{z}, \mathbf{x}]$ be an ideal. Suppose that the map

$$ \mathbb{K}[\mathbf{z}] \to \mathbb{K}[\mathbf{z}, \mathbf{x}]/I $$

is injective and has generically finite fiber, i.e. we assume that $I^{\text{gen}} := I \cdot \mathbb{K}(\mathbf{z})[\mathbf{x}] \neq \mathbb{K}(\mathbf{z})[\mathbf{x}]$ is a zero-dimensional ideal.

**Definition 2.7.** In this setting we call $I^{\text{gen}}$ the generic fiber of $I$.

Let us introduce some further notation.

**Definition 2.8.** We denote for a monomial $u \in \text{Mon}(\mathbf{z})$

$$ m_u := \langle v \in \text{Mon}(\mathbf{z}) | v >_{\text{drl}} u \rangle \text{ and } I_u := I + m_u, $$

$$ \mathfrak{m} := \mathfrak{m}_1 = \langle \mathbf{z} \rangle, \text{ as well as next}(u) = \min \{v \in \text{Mon}(\mathbf{z}) | v >_{\text{drl}} u\}. $$

**Definition 2.9.** Let $g \in \mathbb{K}[\mathbf{z}]_\mathfrak{m}[\mathbf{x}]$. Write

$$ g = \sum_{w \in \text{Mon}(\mathbf{x})} \frac{p_w}{q_w} w $$

with $p_w, q_w \in \mathbb{K}[\mathbf{z}]$ and $q_w(0) \neq 0$ for all $w \in \text{Mon}(\mathbf{x})$ whenever $p_w \neq 0$. Then, each $p_w/q_w$ can be written as a formal power series

$$ \frac{p_w}{q_w} = \sum_{v \in \text{Mon}(\mathbf{z})} r_{w,v} v \in \mathbb{K}[[\mathbf{z}]] $$

and for a monomial $u \in \text{Mon}(\mathbf{z})$ we denote

$$ g_u := \sum_{w \in \text{Mon}(\mathbf{x})} \sum_{v \in \text{Mon}(\mathbf{z})} r_{w,v} v w = g \mod m_u $$

For a set $G \subset \mathbb{K}[\mathbf{z}]_\mathfrak{m}[\mathbf{x}]$ we define $G_u := \{g_u | g \in G\}$.

Let $G \subset \mathbb{K}(\mathbf{z})[\mathbf{x}]$ be the reduced Gröbner basis of $I^{\text{gen}}$ w.r.t. a monomial order $<_{\mathbf{x}}$ on $\text{Mon}(\mathbf{x})$. Our algorithms will work under the assumption that $G \subset \mathbb{K}[\mathbf{z}]_\mathfrak{m}[\mathbf{x}]$ and that given the set $G_u$ we can lift $G_u$ uniquely to $G_{\text{next}}(u)$. In fact the condition $G \subset \mathbb{K}[\mathbf{z}]_\mathfrak{m}[\mathbf{x}]$ turns out to be sufficient. We capture this in a definition:

**Definition 2.10.** We say that $\mathfrak{m}$ is a point of good specialization (for $<_{\mathbf{x}}$) if $G \subset \mathbb{K}[\mathbf{z}]_\mathfrak{m}[\mathbf{x}]$.

**Remark 2.11.** By definition, being a point of good specialization is a Zariski-open condition, so that, if $\mathbb{K}$ is infinite, it is ensured with probability 1 after replacing each $z_i \in \mathbf{z}$ by $z_i - a_i$ for randomly chosen $a_i \in \mathbb{K}$. In Remark 4.11 we point out a situation in which an upper bound for the probability that $\mathfrak{m}$ is a point of good specialization can be given intrinsically in terms of $I$ if $\mathbb{K}$ is finite.

First we show

**Theorem 2.12.** If the ideal $\mathfrak{m}$ is a point of good specialization, then the $\mathbb{K}[\mathbf{z}]_\mathfrak{m}$-module $\mathbb{K}[\mathbf{z}]_\mathfrak{m}[\mathbf{x}]/I$ is free of finite rank.

**Proof.** Write $A := \mathbb{K}[\mathbf{z}]_\mathfrak{m}$, $K = \mathbb{K}(\mathbf{z})$ for the field of fractions of $A$ and $F := A[\mathbf{x}]/I$.

Suppose that $\mathfrak{m}$ is a point of good specialization so that $G \subset A[\mathbf{x}]$. Let $S := S_{I^{\text{gen}}, <_{\mathbf{x}}}$, note that $S$ is finite. We first show that $S$ generates $F$ as an $A$-module. Let $u \in \text{Mon}(\mathbf{x})$ with $u \notin S$ so that $u \in \text{Im}_{<_{\mathbf{x}}} (I^{\text{gen}})$. Then there exists $g \in G$ and $v \in \text{Mon}(\mathbf{x})$ such that $\text{Im}_{<_{\mathbf{x}}}(vg) = u$ and therefore such that $\text{Im}_{<_{\mathbf{x}}}(u - vg) <_{\mathbf{x}} u$.

Reducing further the expression $u - vg$ by $G$ is done with arithmetic over $A$ only and hence shows that, in $F$, we can write $u = \sum_{s \in S} r_s s$ with $r_s \in A$. This shows that $S$ generates the $A$-module $F$. Now, to prove that $F$ is free over $A$, it suffices to show that there are no non-trivial $A$-relations between the elements of $S$. Suppose that for certain $s_1, \dots, s_t \in S$, there is a relation

$$ \sum_{i=1}^{t} r_i s_i = 0 $$

in $F$ with $r_i \in A \setminus \{0\}$ for all $i$. This gives in particular a relation between the $s_i$ over $K$. Hence, if $j$ is such that $s_j <_{\mathbf{x}}$-maximal among the $s_i$, then $s_j \in L$, but $L \cap S = \emptyset$, a contradiction. $\square$

We now give some further properties regarding points of good specializations. Item 1 in the theorem below will be used to show the correctness of our lifting algorithm in Section 3 whereas Item 2 will be used for our complexity analysis in Section 4.

**Theorem 2.13.** Suppose that $\mathfrak{m}$ is a point of good specialization.

(1) For each $u \in \text{Mon}(\mathbf{z})$ and $z_i \in \mathbf{z}$, the multiplication by $z_i$ induces an isomorphism of $\mathbb{K}$-vector spaces:

$$ u\mathbb{K}[\mathbf{z}, \mathbf{x}]/I_u \to z_i u\mathbb{K}[\mathbf{z}, \mathbf{x}]/I_{z_i u}. $$

(2) Let $< \text{be the block order eliminating } \mathbf{x}$ with $<_{=}<_{\mathbf{x}}$ on $\text{Mon}(\mathbf{x})$ and $<_{=}<_{\text{drl}}$ on $\text{Mon}(\mathbf{z})$. Let $M_u$ be the (unique) minimal generating set of $m_u$. Then, the reduced $< \text{-Gröbner basis of } I_u$ is precisely $G_u \cup M_u$.

**Proof.** We reuse the notation from the proof of Theorem 2.12. By Theorem 2.12, $\mathfrak{m}$ being a point of good specialization implies that $F$ is a free $R$-module of finite rank.

**Proof of (1):** It is first easy to check that now multiplication by $z_i$ induces a surjective, well-defined map of finite-dimensional $\mathbb{K}$-vector spaces

$$ u\mathbb{K}[\mathbf{z}, \mathbf{x}]/I_u \to z_i u\mathbb{K}[\mathbf{z}, \mathbf{x}]/I_{z_i u}. $$

Note that the structure of $V_u := u\mathbb{K}[\mathbf{z}, \mathbf{x}]/I_u$ as a vector space is induced by the canonical $A$-module structure of $F$, because $mV_u = 0$ and therefore $(V_u)_{\mathfrak{m}} = V_u$. Hence, if $F \cong A^r$, we have,

$$ V_u \cong (uA/m_u)^r \cong \mathbb{K}^r. $$

Therefore multiplication by $z_i$ induces an epimorphism between vector spaces of the same dimension, so it must be an isomorphism. **Proof of (2):** Let $S := S_{I^{\text{gen}}, <_{\mathbf{x}}}$.

$$ S_{I_u, <} = S_u := \bigcup_{v \leq_{\text{drl}} u} vS. $$

Note that the set $S_u$ certainly generates $\mathbb{K}[\mathbf{z}, \mathbf{x}]/(I + m_u)$ as a $\mathbb{K}$-vector space. As $\mathbb{K}[\mathbf{z}, \mathbf{x}]/(I + m_u) \cong F/m_u$, and since $F$ is free, a
K-dimension count shows that the set $S_u$ is K-linearly independent. Now, let $s \in S$ be <x-minimal such that there exists some $w \in \text{Mon}(z)$, $w \leq_{\text{drl}} u$ with $ws \in \text{Im}_<(I_u)$. By minimality, the <normal form of ws w.r.t. $I_u$ has support in $\cup_{v \leq_{\text{drl}} u} \{vt | t <_x s, t \in S\} \subset S_u$, therefore inducing a linear dependence between the elements of $S_u$, a contradiction. □

We will want to perform finite-dimensional linear algebra akin to the FGLM algorithm in certain staircases of the ideals $I_u$. This will rely on the fact that $I_1$ is zero-dimensional.

**COROLLARY 2.14.** Suppose $m$ is a point of good specialization. Then for each $u \in \text{Mon}(z)$, the ideal $I_u$ is zero-dimensional.

**PROOF.** Note that Item 2 in Theorem 2.13 implies that a K-basis of $K[z, x]/I_u$ is given by $\cup_{v \leq_{\text{drl}} u} vS_{I_{\text{gen}}, <_x}$ which is a finite set. □

### 3 THE MAIN ALGORITHM

As in the last section, we fix an ideal $I \subset K[z, x]$ with generically finite fiber over $K[z]$, we will use the notation introduced in Definition 2.8 and Definition 2.9. We now further fix any monomial order $<_{\text{out}}$ on $\text{Mon}(x)$ and another monomial order $<_{\text{in}}$ on $\text{Mon}(x \cup z)$. We suppose that $m$ is a point of good specialization for $<_{\text{out}}$. Suppose that we can compute, with some black box, the reduced $<_{\text{in}}$-Gröbner basis $H_u$ of $I_u$ for any $u \in \text{Mon}(z)$. Our goal is to use this data to compute the reduced $<_{\text{out}}$-Gröbner basis $G$ of $I^{\text{gen}}$.

**REMARK 3.1.** Note that we have so far required that the partition of the variables of $K[z, x]$ is given. It can be computationally determined: From any Gröbner basis of $I$ we can determine $z$ as a maximally independent set of $I$ and let $x$ be the set of remaining variables, see [3, Definition 9.22]. Then, as in the last section, the map $K[z] \to K[z, x]/I$ is injective with generically finite fiber, see [3, Corollary 9.28].

Let us sketch our strategy. By the assumption that $m$ is a point of good specialization, we have $G \subset K[z]_m[x]$. Recall that $m_1 = m$. We start by computing the $<_{\text{in}}$-Gröbner basis $H_1$ of $I_1 = I+m$. Then, we run the FGLM algorithm [20] with $H_1$ to obtain the reduced $<_{\text{out}}$-Gröbner basis of the image of $I$ in $(K[z]/m)[x] \simeq K[x]$. By Theorem 2.13 this Gröbner basis will now precisely be the set $G_1$ in the notation introduced in Definition 2.9.

For a monomial $u \in \text{Mon}(z)$, let $v := \text{next}(u)$. Starting with $u = 1$ and a given $g_1 \in G_1$, we will lift $g_u$ to $g_v$ by performing linear algebra in the finite-dimensional, see Corollary 2.14, K-vector space $vK[z, x]/I_v$, using the $<_{\text{in}}$-Gröbner basis $H_v$. This will rely on Item 1 in Theorem 2.13.

**REMARK 3.2.** In this section we treat the computation of the required Gröbner bases $H_u$, $u \in \text{Mon}(z)$ as a black box. We recall in Section 4 that these sets may be obtained free of arithmetic operations from an $<_{\text{in}}$-Gröbner basis of $I$ when $<_{\text{in}}= <_{\text{drl}}$ and $I$ satisfies a certain genericity assumption. Under the assumption that $<_{\text{in}}$ is a suitable block order and that $m$ is also a point of good specialization for $<_{\text{in}}$ restricted to $\text{Mon}(x)$ one can give a tracer-based [37] method to compute the sets $H_u$. This will be the subject of a future paper.

This lifting step is now given by Algorithm 1.

**THEOREM 3.3.** If $m$ is a point of good specialization for $<_{\text{out}}$, then Algorithm 1 terminates and is correct in that it satisfies its output specification.

### Algorithm 1 The Lifting Algorithm

**Input** A monomial $u \in \text{Mon}(z)$, $g_u \in G_u$, $v := \text{next}(u)$, the reduced Gröbner basis $H_v$ of $I_v$ w.r.t. $<_{\text{in}}$, the set $S_{I_1, <_{\text{out}}}$.

**Output** The corresponding element $g_v \in G_v$.

1. **function** lift($g_u, H_v, S_{<_{\text{out}}}$)

2. $c \leftarrow \text{nf}_{I_v, <_{\text{in}}}(g_u)$ [via $H_v$]

3. **if** $c = 0$ **return** $g_u$

4. **else**

5. find $(\alpha_w)_{w \in S_{I_1, <_{\text{out}}}}$. s.t. $c = \sum_{w \in S_{I_1, <_{\text{out}}}} \alpha_w \text{nf}_{I_v, <_{\text{in}}}(uw)$ [via $H_v$]

6. **return** $g_u - \sum_{w \in S_{I_1, <_{\text{out}}}} \alpha_w u w$

**PROOF.** We use the notation from the pseudocode of the algorithm. The termination of the algorithm is clear. For the correctness of the algorithm, note that the vectors $\text{nf}_{I_v, <_{\text{in}}}(uw)$ in line 5 are linearly independent thanks to Item 1 of Theorem 2.13. Thus, there exists at most one choice of coefficients $\alpha_w$, $w \in S_{I_1, <_{\text{out}}}$, such that $c = \sum_{w \in S_{I_1, <_{\text{out}}}} \alpha_w \text{nf}_{I_v, <_{\text{in}}}(uw)$. Furthermore, since $m$ is a point of good specialization, the element $g \in G$ corresponding to $g_u$ provides such a choice of coefficients, implying that there exists at least one solution to this linear system. This proves the correctness. □

**REMARK 3.4.** We want to emphasize that our algorithms never verify deterministically (and cannot verify deterministically) whether $m$ is a point of good specialization, this is a probabilistic assumption. Nonetheless, running Algorithm 1 can sometimes detect when $m$ is not a point of good specialization, namely if there exists no or more than one solution to the linear system in line 5 of Algorithm 1. In this case one would apply a random change of coordinates $z_i \leftarrow z_i - a_i$ for each $z_i \in z$ and restart the computation.

**Example 3.5.** Let us unroll Algorithm 1 0,n the following example. We work over the polynomial ring $\mathbb{F}_{11}[z, x_1, x_2, x_3]$, where $\mathbb{F}_{11}$ is the finite field with eleven elements. Our ideal $I$ is generated by

$$ (z+8)x_1 + x_2 + x_3, (z+8)x_1 + x_1x_2 + x_2x_3 + x_3(z+8), \\ (z+8)x_1x_2 + x_1x_2x_3 + x_2x_3(z+8) + x_3(z+8)x_1, (z+8)x_1x_2x_3 - 1. $$

Following Remark 3.1, one verifies that $\mathbb{F}_{11}[z] \to \mathbb{F}_{11}[z, x_1, x_2, x_3]/I$ is injective with generically finite fiber.

Readers may recognize this example as the Cyclic 4 polynomial system where we have replaced the variable $z$ by the random choice $z+8$ to ensure, probabilistically, that $m = \langle z \rangle$ is a point of good specialization.

For our orders we choose $<_{\text{in}}= <_{\text{drl}}$ on $\text{Mon}(x \cup \{z\})$ and $<_{\text{out}}$ as the lexicographic order on $\text{Mon}(x)$. Now, the set $G_1$ is given by

$$ G_1 := \{x_3^2 + 6, x_2 + 8, x_1 + x_3\}. $$

Hence $S_{I_1, <_{\text{out}}} = \{1, x_3\}$. Assuming that $g_1 := x_3^2 + 6$ is the image of some element $g$ in the target Gröbner basis $G \subset \mathbb{F}_{11}(z)[x]$, we now try to lift $g_1$ to $g_z$, i.e. the image of $g$ modulo $m_z = \langle z^2 \rangle$, so that, in the notation of Algorithm 1, we have $u = 1$ and $v = z$.

If such a $g$ exists, there must now exist, by Item 1 in Theorem 2.13, unique scalars $\alpha_1, \alpha_{x_3} \in \mathbb{F}_{11}$ such that

$$ g_z = g_1 + \alpha_1 z + \alpha_{x_3} z x_3 = 0 \quad \text{mod} \quad I_z = I + \langle z^2 \rangle, $$

and Algorithm 1 attempts to compute these scalars by finding a linear relation between the normal forms w.r.t. $<_{\text{in}}$ of $g_1, z$ and $zx_3$
modulo $I_z$. Using an $<_{in}$-Gröbner basis of $I_z$, we find that $S_{I_z, <_{in}} = \{1, z, x_3, zx_3\}$ and we compute, using normal form computations

$$
\begin{align*}
\mathrm{nf}_{I_2, <_{in}}(g_1) &= (0, 7, 0, 0) \\
\mathrm{nf}_{I_2, <_{in}}(z) &= (0, 1, 0, 0) \\
\mathrm{nf}_{I_2, <_{in}}(zx_3) &= (0, 0, 0, 1)
\end{align*}
$$

so that finally, $\alpha_1 = 6$ and $\alpha_{x_3} = 0$ which yields for $g_z$ the unique
candidate $g_z = x_3^2 + (4z + 6)$, finishing the example.

Algorithm 1 is only able to compute the set $G_u$ for a monomial $u \in \text{Mon}(z)$, i.e. it “approximates” the set $G$ up to order $u$. A natural question is then how to extract the actual set $G$ out of $G_u$. For this, we may use the classical technique of Padé approximants. Having computed the set $G_u$, we have computed the image $g_u$ of a given element $g \in G$ as

$$
g_u = \sum_{w \in \text{Mon}(x)} \sum_{v \le \text{drl} | u} r_{w,v} v w.
$$

Now we have for the coefficient $p_w/q_w \in \mathbb{K}(z)$ of $w$ in $g$

$$
p_w - q_w \sum_{v \leq \mathrm{drl} | u} r_{w,v} v = 0 \quad \mathrm{mod} \; m_u, \qquad (1)
$$

which determines a set of linear equations in the unknown coef-
ficients of $p_w$ and $q_w$. Let $d := \deg u$. Suppose that $\deg \text{next}(u) =
d+1$, so that $m_u = m^{d+1}$. Fix $d_1$ and $d_2$ with $d_1 + d_2 = d$ and let
$n$ be the cardinality of the set $z$. If we impose that $\deg p_w \le d_1$
and $\deg q_w \le d_2$, then the linear system (1) has a finite set of
unknowns and equations. Let us say that any solution to this lin-
ear system of equations is a Padé approximant of order $(d_1, d_2)$ of
$\lambda_w := \sum_{\deg v < d+1} r_{w,v} v$. If $d_1$ and $d_2$ are large enough then any
Padé approximant of order $(d_1, d_2)$ of $\lambda_w$ is equal to $p_w/q_w$, see
e.g. [26, Proposition 2.1]:

LEMMA 3.6. Let $p/q$ be a Padé approximant of order $(d_1, d_2)$ of $\lambda_w$. If $d_1 \ge \deg p_w$ and $d_2 \ge \deg q_w$ then $p/q = p_w/q_w$.

By solving this linear system we obtain an algorithm *pade*($g_u$, $d_1$, $d_2$)
which computes a candidate $g_{\text{cand}} \in \mathbb{K}(z)[x]$ whose coefficients
are Padé approximants of the coefficients of $g_u$ of order $(d_1, d_2)$
regarded as a polynomial in the variables $x$. Let us say that $g_u$ has
*stable Padé approximation* if for $v := \text{next}(u)$ we have

$g_{\text{cand}} = g_v \bmod m_v.$

Based on this, we now obtain Algorithm 2 for computing the set
$G$ probabilistically. We state this algorithm in an informal way. In
Line 7 by "lifting $G_{\text{lift}}$ to degree $d$" we mean that we compute the
set $G_u$ where $u$ is the $<_{\text{drl}}$-maximal monomial of degree $d$.
Clearly, by Theorem 3.3 and Lemma 3.6, this algorithm returns the
correct result if the computed Padé approximants are of sufficiently
large degree and $\mathfrak{m}$ is a point of good specialization.

REMARK 3.7. Note that Algorithm 1 works also if we replace $v$ by any monomial larger than $u$: In this case we just have to write $c$ as a linear combination of all the vectors $c_{I_v, <_{in}}(uv')$ where $u <_{\text{drl}} v' \le_{\text{drl}} v$.

Example 3.8 (Example 3.5 continued). Let us try to see how Al-
gorithm 2 recovers the element denoted *g* in Example 3.5. First,
Algorithm 2 lifts the element *g*₁ = *x*<sub>3</sub><sup>2</sup> + 6 to degree *d* = 2, i.e. we

**Algorithm 2 Computing the generic fiber**

**Input** A generating set $F$ of $I$, a monomial order $<_{in}$, a monomial order $<_{out}$.

**Output** A guess for the set $G$.

1 function genfglm($F$, $<_{in}$, $<_{out}$)

2 $H_1 \leftarrow$ reduced $<_{in}$-Gröbner basis of $I_1$ [using $F$]

3 $G_{\text{lift}}$, $S_{<\text{out}} \leftarrow \text{fglm}(H_1, <\text{out})$

4 $G_{\text{result}} \leftarrow \emptyset$

5 $d \leftarrow 2$

6 while $G_{\text{lift}} \neq \emptyset$

7 $G_{\text{lift}} \leftarrow \text{lift } G_{\text{lift}} \text{ to degree } d \text{ using Algorithm 1}$

8 Run *pade*(*g*, *d*/*2*, *d*/*2*) for all *g* ∈ *G*<sub>*lift*</sub>

9 Lift $G_{\text{lift}}$ one monomial higher

10 add to $G_{\text{result}}$ all elements with stable Padé approx.

11 remove the corresponding elements from $G_{\text{lift}}$

12 $d \leftarrow 2d$

13 return $G_{\text{result}}$

compute the image of $g$ modulo $z^3$ (line 7 in Algorithm 2). This
yields, in our usual notation,

$$
g_2 = x_3^2 + (2z^2 + 4z + 6).
$$

Now we attempt (line 8 in Algorithm 2) to find a Padé approximation
of order (1, 1) for $g$, i.e., here, $p, q \in \mathbb{F}_{11}[z]$ of degree at most one
such that $p/q = 2z^2 + 4z + 6 \pmod{z^3}$ by solving a linear system as
outlined above. This yields the candidate

$$
g_{\text{cand}} = x_3^2 + \frac{z+6}{5z+1}
$$

which satisfies $g_{\text{cand}} = g_2 \bmod z^3$. Next, in line 9, we lift $g$ one
monomial higher, i.e. modulo $z^4$. This yields

$$
g_3 = x_3^2 + (7z^3 + 2z^2 + 4z + 6),
$$

But $p/q$ has now the truncated power series $z^3 + 2z^2 + 4z + 6$, so
that $g_2$ does not have stable Padé approximation. Hence we double
$d$ to 4 and lift $g_3$ to $g_4$, i.e. from modulo $z^4$ to modulo $z^5$, and
attempt another Padé approximation. This time, computing a Padé
approximation of order (2, 2), this yields the candidate

$$
g_{\text{cand}} = x_3^2 + \frac{1}{10z^2 + 6z + 2}.
$$

Finally, we lift $g_4$ to $g_5$ and find that $g_5 = g_{\text{cand}} \bmod z^6$. So $g_4$
has stable Padé approximation and we terminate with $g := g_{\text{cand}}$.
Computing the $<_{\text{out}}$-Gröbner basis $G$ of $I^{\text{gen}}$ using block orders as
in [2, Lemma 8.93] shows that $g$ is indeed the correct element.

4 COMPLEXITY ESTIMATES

In this section, we analyze the arithmetic complexity of a version
of our algorithm more akin to the original FGLM algorithm as
presented in [20]. We will reuse the notation from the last section.
We now add the additional assumption that $<_{in}$ is a block order
eliminating $x$ with $<_{in} = <_{drl}$ on $\text{Mon}(z)$ and that $\mathfrak{m}$ is a point of
good specialization for both $<_{in}$ and $<_{out}$. Here, we analyze the
number of arithmetic operations in $\mathbb{K}$ required to obtain the sought
$<_{out}$-Gröbner basis $G$ using the same strategy as in Algorithm 2,
but with a more optimized lifting step.
Our cost analysis will require measuring the cost of performing certain linear algebra operations on structured matrices. The matrices that will appear in the analysis are block-Toeplitz:

**Definition 4.1.** Let $k, D \in \mathbb{N}$. A block matrix $M = (M_{pq})_{0\le p,q<k} \in \mathbb{K}^{kD \times kD}$ where each $M_{pq}$ is in $\mathbb{K}^{D \times D}$ is called block-Toeplitz of type $(k, D)$ if $M_{pq} = M_{p'q'}$ whenever $p-q=p'-q'$. We say that $M$ is Toeplitz when $D=1$.

If $M$ is block-Toeplitz of type $(k, D)$ then we will need the arithmetic complexity of computing a matrix vector product $Mv, v \in \mathbb{K}^{kD}$, and of inverting $M$. For this we need the concept of displacement rank of a matrix, see e.g. [9]:

**Definition 4.2.** Let $Z \in \mathbb{K}^{n \times n}$ be the matrix defined by

$$Z := (\delta_{i-1,j})_{1\le i,j\le n},$$

where $\delta_{i-1,j}$ is the Kronecker delta and let $Z^T$ be the transpose of $Z$. The displacement rank of a matrix $M \in \mathbb{K}^{n \times n}$ is

$$\alpha(M) := \operatorname{rank}(M - ZMZ^T).$$

Note that the displacement rank of a Toeplitz matrix is upper bounded by 2. The concept of displacement rank can be used as a general method to utilize “Toeplitz-like” structures in algorithmic linear algebra. In this vein, we have

**PROPOSITION 4.3.** Let $M$ be block-Toeplitz of type $(k, D)$ and let $v \in \mathbb{K}^{kD}$. Then

(1) $Mv$ can be computed in $\tilde{O}(kD^2)$ arithmetic operations in $\mathbb{K}$;

(2) $M$ can be inverted in $\tilde{O}(kD^\omega)$.

**PROOF.** For any matrix $M \in \mathbb{K}^{n \times n}$, according to [9], a matrix-vector product $Mv$ can be computed in time $\tilde{O}(\alpha(M)n)$ and $M$ can be inverted in time $\tilde{O}(\alpha(M)^{\omega-1}n)$. Using a series of rows and column swaps, more precisely sending row $pD + i$ to $ik + p$ (resp. column $qD + j$ to $jk + q$), we may transform a block-Toeplitz matrix $M$ of type $(k, D)$ into a matrix $N = (N_{ij})_{0\le i,j\le D} \in \mathbb{K}^{kD \times kD}$ where each $N_{ij}$ lies in $\mathbb{K}^{k \times k}$ and is Toeplitz. Now, $N - ZNZ^T$ has $D$ dense columns and $(k-1)D$ columns with potentially nonzero coefficients in positions $iD$ for all $i$. Only $D$ of these latter columns can be linearly independent so that $\alpha(M) \le 2D$, proving both claims. $\square$

Our cost analysis follows closely the one of the original FGLM algorithm. To this end, we give the following definition:

**Definition 4.4 (Multiplication Tensor).** Let $I$ be a zero-dimensional ideal in a polynomial ring $\mathbb{K}[\mathbf{x}]$ and let $< \le$ be a monomial order. Let $S := S_{I,<}$. The multiplication tensor of $I$ w.r.t. $<$ is defined as the 3-tensor

$$M(I, <) = (\mathrm{nf}_{I,<}(x_i u))_{x_i \in \mathbf{x}, u \in S},$$

where the vectors of coefficients are in the basis $S$.

It turns out that computing these multiplication tensors dominates the cost of the original FGLM algorithm and similarly it dominates the cost of our algorithm. In this section, we denote by $D$ the degree of $I^{\mathrm{gen}}$, i.e. the $\mathbb{K}(z)$-dimension of $\mathbb{K}(z)[\mathbf{x}]/I^{\mathrm{gen}}$. Note that this degree is upper-bounded by that of $I$. For $u \in \mathrm{Mon}(\mathbf{x})_{<\mathrm{drl}}$-maximal of degree $k$, we also denote $I_k := I_u$ and similarly $H_k := H_u$ and $G_k := G_u$ with these sets defined as in the last section.

To simplify the notation, we assume in the following two proofs, that the set $z = \{z\}$ consists of a single variable. It will be clear from the proofs that they translate accordingly to the more general setting where $z$ consists of several variables.

In our assumed setting, we obtain the following statement for computing multiplication tensors:

**THEOREM 4.5.** Let $k \in \mathbb{N}$ and $m_k$ be the number of monomials in $z$ up to degree $k$. Let $c$ be the cardinality of $\mathbf{x}$. Suppose that we are given the set $H_{2k}$ and the multiplication tensor of $I_k$ w.r.t. $<\mathrm{in}$. Then the multiplication tensor of $I_{2k}$ w.r.t. $<\mathrm{in}$ is computed in arithmetic complexity $\tilde{O}(m_k c D^3)$.

**PROOF.** Let $S := S_{I_1, <\mathrm{in}}$. Applying the third item of Theorem 2.13 with $<\mathrm{in}$ instead of $<$, since $<\mathrm{in}$ eliminates $\mathbf{x}$, for any $\ell \in \mathbb{N}$, yields

$$S_{I_\ell, <\mathrm{in}} = \bigcup_{i=0}^{\ell-1} z^i S.$$

Let us now describe the structure of the multiplication matrices of $I_{2k}$, i.e. the matrices

$$M(I_{2k}, <\mathrm{in})_y := (c_{I_{2k}, <\mathrm{in}}(y u))_{u \in S_{I_{2k}, <\mathrm{in}}}, \quad \text{for } y \in \mathbf{x} \cup \mathbf{z}.$$

The matrix $(c_{I_{2k}, <\mathrm{in}}(zu))_{u \in S_{I_{2k}, <\mathrm{in}}}$ of the multiplication by $z$ is

$$S \quad zS \quad \dots \quad z^{2k-1}S \\ S \\ zS \\ \vdots \\ z^{2k-1}S \quad \begin{bmatrix} \text{Id} \\ \vdots \\ \vdots \\ \text{Id} \end{bmatrix}$$

and so is extracted without any arithmetic operations. Further, denote $S_0 := \bigcup_{i=0}^{k-1} z^i S$ and $S_1 := \bigcup_{i=k}^{2k-1} z^i S = z^k S_0$. Now, for $x_i \in \mathbf{x}$ the multiplication matrix $M_{x_i}$ by $x_i$ is determined by two matrices $M_{x_i,0}, M_{x_i,1} \in \mathbb{K}^{D \times D}$ as follows

$$M_{x_i} = \begin{bmatrix} S_0 & S_1 \\ S_1 & \begin{bmatrix} M_{x_i,0} & M_{x_i,1} \\ M_{x_i,0} & M_{x_i,0} \end{bmatrix} \end{bmatrix},$$

where each $M_{x_i, i}$ is easily seen to be block-Toeplitz of type $(m_k, D)$ and $M_{x_i, 0}$ is known as part of the $<\mathrm{in}$-multiplication tensor of $I_k$. Thanks to the block-Toeplitz structure, it now suffices to compute the columns of $M_{x_i, 1}$ coming from the normal forms of the set $\mathbf{x}S$, which is of cardinality at most $cD$. Now, we proceed as follows: Sort the set $\mathbf{x}S$ by the monomial order $<\mathrm{in}$. Choose $u \in \mathbf{x}S$ and suppose that the normal forms of all elements less than $u$ in $\mathbf{x}S$ are known. Two easy cases can arise:

(1) $u \in S$, in which case the normal form of $u$ is computed without any arithmetic operations;

(2) $u \in \mathrm{lm}(H_{2k})$, in which case the normal form of $u$ is computed without any arithmetic operations, it is just given by the tail of the corresponding element in $H_{2k}$.

Lastly, it can happen that $u \in \mathrm{lm}(I_{2k})$ but $u \notin \mathrm{lm}(H_{2k})$. In this case there exists $v \in \mathbf{x}S$ and $x_j \in \mathbf{x}$ with $u = x_j v$. By assumption the normal form of $v$ is known and so is the normal form of each element $x_j b$ with $b \in S$ and $b <\mathrm{in} \ v$. Since $M_{x_j}$ has the same structure as $M_{x_i}$, we can now compute the required column of
$M_{x_i, 1}$ as the sum of two matrix-vector products where each of the two matrices is block-Toeplitz of type $(m_k, D)$. This is done in time $\tilde{O}(m_k D^2)$ thanks to Proposition 4.3, concluding the proof, since $xS$ has cardinality at most $cD$. $\square$

Now, we can estimate the complexity of lifting the set $G_k$:

**COROLLARY 4.6.** Let $k \in \mathbb{N}$ and $m_k$ be the number of monomials in $z$ up to degree $k$. Let $c$ be the cardinality of $x$. Suppose that we are given the set $H_{2k}$, the multiplication tensor of $I_k$ w.r.t. $<in$, the $<in$-normal forms of the $<out$-staircase of $I_1$ w.r.t. $I_k$ and the $<in$-normal forms of the minimal $<out$-leading monomials of $I_0$ w.r.t. $I_k$. Then $G_{2k}$ is computed in arithmetic complexity $\tilde{O}(m_k cD^3)$.

**PROOF.** By Theorem 4.5, the $<in$-multiplication tensor of $I_{2k}$ can be computed in arithmetic complexity $\tilde{O}(m_k cD^3)$. Having computed this tensor, we proceed as follows: let $S$ be the $<in$-staircase of $I_1 = I + \langle z \rangle$, $T$ be the $<out$-staircase of $I_1$ and $L$ be the set of minimal $<out$-leading terms of $I_1$, with $z$ removed. Denoting $S_0$ and $S_1$ as in the proof of the preceding theorem, and similarly $T_0$ and $T_1$, now we first compute the $<in$-normal forms of each element in $T \cup L$ w.r.t. $I_{2k}$, this will yield a tableau of the form

$$C := \begin{array}{c@{\quad}c@{\quad}c} & \begin{array}{ccc} T_0 & T_1 & L \end{array} & \\ \begin{array}{c} S_0 \\ S_1 \end{array} & \left[ \begin{array}{ccc} C_0 & & D_0 \\ C_1 & C_0 & D_1 \end{array} \right]. & \end{array}$$

Note that by assumption the matrix $C_0$ is already known by the $<in$-normal forms of $T$ w.r.t. $I_1$ and the matrix $D_0$ is given by the $<in$-normal forms of $L$ w.r.t. $I_1$. Note also that $C_0$ and $C_1$ are again block-Toeplitz of type $(m_k, D)$.

The required matrices $C_1$ and $D_1$ can be computed by using the $<in$-multiplication tensor of $I_{2k}$, enumerating the monomials in $\text{Mon}(x)$ in order of $<out$ and computing their normal forms via matrix-vector multiplications similar to the proof of the preceding theorem. Combining this with the block-Toeplitz structure of the multiplication matrices of $I_{2k}$ w.r.t. $<in$, this can again be done in time $\tilde{O}(m_k cD^3)$. Finally, to compute the set $G_{2k}$, we have to write each column in $C$ corresponding to an element in $L$ as a $\mathbb{K}$-linear combination of the columns corresponding to $T_0 \cup T_1$, i.e. by solving the linear system

$$\begin{bmatrix} C_0 \\ C_1 & C_0 \end{bmatrix} \begin{bmatrix} X_0 \\ X_1 \end{bmatrix} = \begin{bmatrix} D_0 \\ D_1 \end{bmatrix},$$

where $X_0$ is known via $G_k$. Hence this requires

* inverting the submatrix $C_0$ which, by Proposition 4.3, is done in time $\tilde{O}(m_k D^\omega)$;

* computing the product $C_0^{-1}(D_1 - C_1 X_0)$.

Note that $C_0^{-1}$ has displacement rank bounded above by $2D + 2$, see [8, Proposition 10.10 and Theorem 10.11], and that the cardinality of $L$ is upper bounded by $cD$. Thus, for the second step above, we have to compute at most $cD$ matrix-vector products of the form $C_0^{-1}v$ and $cD$ matrix-vector products of the form $C_1 v$. Again, thanks to Proposition 4.3, this is done in time $\tilde{O}(m_k cD^3)$. This finally yields the desired complexity. $\square$

The following corollary now gives the complexity of computing successively the sets $G_{2i}$ from $H_{2i}$ until $i$ is large enough to recover $G$, like in Algorithm 2.

**COROLLARY 4.7.** For $k \in \mathbb{N}$, let $m_k$ be the number of monomials in $z$ up to degree $k$. Let $c$ be the cardinality of $x$. Let $\delta = 1$ be the maximum degree of all numerators and denominators of all coefficients of $G$. Further, let $\ell$ be minimal such that $2^\ell \ge 2\delta$.

Given $H_{2\ell}$, computing successively the sets $G_{2i}$, for $i = 1, \dots, \ell$, can be done in arithmetic complexity $\tilde{O}(m_{2\ell} cD^3) = \tilde{O}(m_\delta cD^3)$.

**PROOF.** Note that the sets $H_{2i}$, for $i = 1, \dots, \ell$, are obtained from $H_{2\ell}$ free of arithmetic operations. By Corollary 4.6, the computation of $G_{2i}$ requires $\tilde{O}(m_{2i} cD^3)$ operations. Since $m_{2i} = \binom{n-c+2i}{n-c} = O(2^{(n-c)i})$, where $n$ is the total number of variables, and thus $n-c$ the cardinality of $z$, summing these complexities for $i$ from 1 to $\ell$ yields the desired complexity. $\square$

Note that going up to degree $2^\ell$ suffices to recover the coefficients of $G$ by Padé approximation thanks to Lemma 3.6.

**REMARK 4.8.** In a follow-up paper, we plan to study the complexity of our algorithm using variants of FGLM, such as [6, 19, 21, 31].

We close this section by pointing out a well-known case in which $<in$ is the $<drl>$ order, the required Gröbner bases $H_u$ of $I + m_u$ are extracted without any arithmetic operations of the $<drl>$-Gröbner basis $H$ of $I$ and the $<drl>$-staircase of $I + m_u$ behaves the same as in the above case when $<in$ is a block order. We start with

**Definition 4.9.** Let $y$ be an extra variable and let $I^{\text{hom}} \subset \mathbb{K}[z, x, y]$ be the homogenization of $I$ w.r.t. $y$. Suppose that $I^{\text{hom}}$ is Cohen-Macaulay. We say that $I$ is in projective generic position if $\{y\} \cup z$ is a maximal homogeneous regular sequence in $\mathbb{K}[z, x, y]/I^{\text{hom}}$.

Supposing that $I^{\text{hom}}$ is Cohen-Macaulay we now have the following statement, see e.g. [30]. This statement has frequently been used in the complexity analysis of Gröbner basis algorithms.

**LEMMA 4.10.** Let $I$ be in projective generic position with $I^{\text{hom}}$ Cohen-Macaulay. Let $H$ be the reduced $<drl>$-Gröbner basis of $I$ (with the variables in $z$ considered smaller as those in $x$). Then

$$\text{lm}(H) \subset \text{Mon}(x).$$

In particular, if $S$ is the $<drl>$-staircase of $I_1 := I + m$, then the $\leq_{drl}$-staircase of $I + m_u$ is given by

$$S_u := \bigcup_{v \leq_{drl} u} vS.$$

This implies that when $I$ is such that $I^{\text{hom}}$ is Cohen-Macaulay and is in projective generic position then we can replace $<in$ with $<drl>$ and $H_u$ with $H$ in the statements of Theorem 4.5 and Corollary 4.6. Now we are ready to prove:

**PROOF OF THEOREM 1.1.** The genericity assumption on $f_1, \dots, f_c$ implies that they form a Cohen-Macaulay ideal in projective generic position and that the ideal has degree $D = d_1 \cdots d_c$. Thus, Algorithm 2 can be called on $\{f_1, \dots, f_c\}$, $<drl>$ and the chosen $<out$ in order to compute the reduced $<out$-Gröbner basis of $I \cdot \mathbb{K}(z)[x]$ up to precision $2\delta$. Finally, using Corollaries 4.6 and 4.7, we obtain the desired complexity. $\square$

**REMARK 4.11.** Let us close this section with a remark on the probability of $m$ being a point of good specialization in the situation of
**Theorem 1.1** if $<_{\text{out}}=<_{\text{lex}}$, the lexicographic order on $\text{Mon}(\mathbf{x})$. If $I^{\text{gen}}$ is in shape position, then the reduced $<_{\text{lex}}$-Gröbner basis of $I^{\text{gen}}$ is of the form

$$ \{g_c(\mathbf{z}, x_c), x_1 - g_1(\mathbf{z}, x_c), \dots, x_{c-1} - g_{c-1}(\mathbf{z}, x_c)\} $$

with $g_c(\mathbf{z}, x_c) \in \mathbb{K}[\mathbf{z}, x_c]$ of total degree $D$. One can then show, using [33], that the degree of the $\text{lcm}$ of the denominators of the coefficients of $g_1, \dots, g_{c-1}$ is bounded by $D^2$ where $D := d_1 \cdots d_c$ is the Bézout bound of our system. Then, if $\mathbb{K} = \mathbb{F}_q$ for a prime power $q$, the Schwartz-Zippel lemma [35] implies that the probability of $m$ not being a point of good specialization is bounded by $D^2/q$ which goes to zero as $q$ increases.

# 5 BENCHMARKS

In this section, we provide benchmarks for a proof-of-concept implementation of Algorithm 2. We first give a brief description thereof. This implementation is written using the computer algebra system OSCAR [36] which itself is written in Julia [7]. All required Gröbner basis computations use the Gröbner basis libraries `msolve` [4] via its `Julia-interface AlgebraicSolving.jl` or `Groebner.jl` [12], also written in Julia. The main step in Algorithm 2, Algorithm 1, was implemented naively, close to the provided pseudocode, i.e. without the use of multiplication tensors to compute normal forms as described in Section 4. The implementation is available at https://gitlab.lip6.fr/mohr/genfglm. For the below benchmarks, the following computations were performed, keeping the notation from the last sections:

(1) Compute a $<_{\text{drl}}$-Gröbner basis for the polynomial ideal $I$ in question.

(2) Use this $<_{\text{drl}}$-Gröbner basis to compute a maximally independent set of variables modulo $I$, this gives us the partition of the variables into the subsets $\mathbf{x}$ and $\mathbf{z}$ as above.

(3) If $\mathbf{z} = \{z_1, \dots, z_{n-c}\}$, choose random $a_1, \dots, a_{n-c} \in \mathbb{K}$ and make the coordinate substitution $z_i \leftarrow z_i - a_i$.

(4) Choose $<_{\text{in}}$ as the block order on $\text{Mon}(\mathbf{z}, \mathbf{x})$ eliminating $\mathbf{x}$ with $<_{\text{drl}}$ on both blocks of variables.

(5) If $\mathbf{x} = \{x_1, \dots, x_c\}$, choose $<_{\text{out}}$ as a block order on $\text{Mon}(\mathbf{x})$ eliminating $\mathbf{x}' := \{x_1, \dots, x_{c-1}\}$ with $<_{\text{drl}}$ on $\mathbf{x}'$ and $<_{\text{in}}$ on $\{x_c\}$.

(6) By the elimination property of block orders, the target Gröbner basis $G$ contains a single polynomial $g_c$ in the univariate polynomial ring $\mathbb{K}(\mathbf{z})[x_c]$.

(7) Use Algorithm 2 to compute only the polynomial $g_c$, ignoring the rest of the set $G$. Note that this is indeed possible, in line 7 of Algorithm 2 we may choose which of the elements in $G_{\text{lift}}$ to actually keep and lift and ignore the rest.

In a certain generic situation (more precisely, when the variable $x_c$ is “generic”), the computed polynomial $g_c$ can be used for a primary decomposition of $I$, see e.g. [3, Sections 8.6 and 8.7], this motivates our choice of $<_{\text{out}}$. We should emphasize however that we did not verify whether this generic situation is met in the examples below. In the context of primary decomposition, it suffices to know just the polynomial $g_c$ in $G$, the rest of the Gröbner basis can be ignored. This is a potential advantage our algorithm has over the classical way of computing Gröbner bases of generic fibers using elimination orders for which there is no way of getting around computing the entire set $G$.

<table><caption>**Table 1: Benchmarks for Algorithm 2**</caption><thead><tr><th rowspan="2">System</th><th colspan="2">Algorithm 2</th><th rowspan="2">msolve with &lt;out<br>Timing (in s)</th></tr><tr><th>Timing (in s)</th><th>Memory</th></tr></thead><tbody><tr><td>ED(3,3)</td><td>237.9</td><td>95.47 GB</td><td>43521.43</td></tr><tr><td>R1</td><td>0.01</td><td>140.49 GB</td><td>0.01</td></tr><tr><td>R2</td><td>0.01</td><td>251.95 MB</td><td>0.01</td></tr><tr><td>R3</td><td>0.01</td><td>248.93 MB</td><td>0.01</td></tr><tr><td>M2</td><td>2.75</td><td>1.56 GB</td><td>0.03</td></tr><tr><td>M3</td><td>0.19</td><td>410.09 MB</td><td>0.01</td></tr><tr><td>PS(2,10)</td><td>0.8</td><td>417.63 MB</td><td>0.3</td></tr><tr><td>PS(2,12)</td><td>44.82</td><td>1.38 GB</td><td>7.3</td></tr><tr><td>Sing(2,10)</td><td>0.2</td><td>275.17 MB</td><td>0.1</td></tr><tr><td>SOS(5,4)</td><td>1.2</td><td>1.2 GB</td><td>0.3</td></tr><tr><td>SOS(6,4)</td><td>11.97</td><td>1.07 GB</td><td>30.35</td></tr><tr><td>SOS(6,5)</td><td>22.19</td><td>954.41 MB</td><td>26.61</td></tr><tr><td>RD(3)</td><td>4.29</td><td>650.98 MB</td><td>0.11</td></tr><tr><td>RD(4)</td><td>33.42</td><td>10.46 GB</td><td>13.43</td></tr><tr><td>RD(5)</td><td>729.51</td><td>185.87 GB</td><td>780.92</td></tr></tbody></table>

We never directly computed the reduced Gröbner basis $H$ of $I$ w.r.t. $<_{\text{in}}$, but only the reduced $<_{\text{in}}$-Gröbner basis $H_u$ of the ideals $I + m_u$. When doing this, we found that the computations were better-behaved when choosing $<_{\text{in}}$ as above rather than $<_{\text{in}}=<_{\text{drl}}$. All computations were performed with $\mathbb{K} = \mathbb{Z}/p\mathbb{Z}$ where $p$ was a randomly chosen prime of 16 bits.

We compared the time this computation took with the computation of the set $G$ using `msolve` and which, in this case, just runs the $F_4$ algorithm with a suitable block order on $\text{Mon}(\mathbf{z}, \mathbf{x})$. These timings are given in Table 1.

The polynomial systems used for these benchmarks are:

* ED(3,3) encodes the parametric *euclidean distance* problem for a hypersurface of degree 3 in 3 variables, see [13];

* R1, R2, R3 come from a problem in Robotics, see [22];

* M2 and M3 are certain jacobian ideals of single multivariate polynomials which define singular hypersurfaces;

* The “PS”, “Sing” and “SOS” systems are all critical loci of certain projections, see [15] for a more detailed description;

* The RD(d) systems are randomly generated sequences of 3 polynomials of degree d in 4 variables.

All computations were performed on an Intel Xeon Gold 6244 CPU @ 3.60 GHz with 1.5 TB of memory. To illustrate the memory usage of our algorithm, we give in addition the total memory allocated by our implementation.

On most small examples in Table 1, we achieve a comparable timing with `msolve`, with the exception of PS(2,12). On the larger example RD(5) we have a small improvement, while on ED(3,3) we achieve a much better timing. We should mention that our implementation is not yet optimized (for example, we observed that the linear systems to be solved in Algorithm 1 are very sparse, yet our implementation relies on dense representations and arithmetic) and does not incorporate the idea mentioned in Remark 3.2.

**Example 5.1.** Continuing Example 3.8, we provide a detailed log file with explanatory comments for running our implementation on the Cyclic 8 polynomial system at https://polsys.lip6.fr/~mohr/assets/fglm_log.txt.
REFERENCES

[1] Elizabeth A. Arnold. 2003. Modular Algorithms for Computing Gröbner Bases. *Journal of Symbolic Computation* 35, 4 (2003), 403–419. https://doi.org/10.1016/S0747-7171(02)00140-2

[2] Thomas Becker. 1994. On Gröbner Bases under Specialization. *Applicable Algebra in Engineering, Communication and Computing* 5, 1 (1994), 1–8. https://doi.org/10.1007/BF01196621

[3] Thomas Becker and Volker Weispfenning. 1993. *Gröbner Bases*. Graduate Texts in Mathematics, Vol. 141. Springer-Verlag, New York. https://doi.org/10.1007/978-1-4612-0913-3

[4] Jérémy Berthomieu, Christian Eder, and Mohab Safey El Din. 2021. msolve: A Library for Solving Polynomial Systems. In *Proceedings of the 2021 on International Symposium on Symbolic and Algebraic Computation* (Virtual Event, Russian Federation) (ISSAC '21). Association for Computing Machinery, New York, NY, USA, 51–58. https://doi.org/10.1145/3452143.3465545

[5] Jérémy Berthomieu, Christian Eder, and Mohab Safey El Din. 2023. New Efficient Algorithms for Computing Gröbner Bases of Saturation Ideals (F4SAT) and Colon Ideals (Sparse-FGLM-colon). https://doi.org/10.48550/arXiv.2202.13387 arXiv:2202.13387 [cs, math]

[6] Jérémy Berthomieu, Vincent Neiger, and Mohab Safey El Din. 2022. Faster Change of Order Algorithm for Gröbner Bases under Shape and Stability Assumptions. In *Proceedings of the 2022 International Symposium on Symbolic and Algebraic Computation (ISSAC '22)*. Association for Computing Machinery, New York, NY, USA, 409–418. https://doi.org/10.1145/3476446.3535484

[7] Jeff Bezanson, Alan Edelman, Stefan Karpinski, and Viral B Shah. 2017. Julia: A Fresh Approach to Numerical Computing. *SIAM review* 59, 1 (2017), 65–98.

[8] Alin Bostan, Frédéric Chyzak, Marc Giusti, Romain Lebreton, Grégoire Lecerf, Bruno Salvy, and Éric Schost. 2017. *Algorithmes Efficaces en Calcul Formel*. Frédéric Chyzak (auto-édit.), Palaiseau.

[9] Alin Bostan, Claude-Pierre Jeannerod, Christophe Mouilleron, and Éric Schost. 2017. On Matrices With Displacement Structure: Generalized Operators and Faster Algorithms. *SIAM J. Matrix Anal. Appl.* 38, 3 (2017), 733–775. https://doi.org/10.1137/16M1062855

[10] Bruno Buchberger. 1965. *Ein Algorithmus Zum Auffinden Der Basiselemente Des Restklassenringes Nach Einem Nulldimensionalen Polynomideal*. Ph. D. Dissertation. Universität Innsbruck.

[11] S. Collart, M. Kalkbrener, and D. Mall. 1997. Converting Bases with the Gröbner Walk. *Journal of Symbolic Computation* 24, 3 (1997), 465–469. https://doi.org/10.1006/jsco.1996.0145

[12] Alexander Demin and Shashi Gowda. 2023. *Groebner,jl: A Package for Gröbner Bases Computations in Julia*. https://doi.org/10.48550/arXiv.2304.06935

[13] Jan Draisma, Emil Horobet, Giorgio Ottaviani, Bernd Sturmfels, and Rekha R. Thomas. 2016. The Euclidean distance degree of an algebraic variety. *Found. Comput. Math.* 16, 1 (2016), 99–149. https://doi.org/10.1007/s10208-014-9240-x

[14] Gary L. Ebert. 1983. Some comments on the modular approach to Gröbner-bases. *SIGSAM Bull.* 17, 2 (1983), 28–32. https://doi.org/10.1145/1089330.1089336

[15] Christian Eder, Pierre Lairez, Rafael Mohr, and Mohab Safey El Din. 2023. A Direttissimo Algorithm for Equidimensional Decomposition. In *Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation (ISSAC '23)*. Association for Computing Machinery, New York, NY, USA, 260–269. https://doi.org/10.1145/3597066.3597069

[16] Christian Eder, Pierre Lairez, Rafael Mohr, and Mohab Safey El Din. 2023. A Signature-Based Algorithm for Computing the Nondegenerate Locus of a Polynomial System. *Journal of Symbolic Computation* 119 (2023), 1–21. https://doi.org/10.1016/j.jsc.2023.02.001

[17] Jean-Charles Faugère. 1999. A New Efficient Algorithm for Computing Gröbner Bases (F4). *Journal of Pure and Applied Algebra* 139, 1 (1999), 61–88. https://doi.org/10.1016/S0022-4049(99)00005-5

[18] Jean-Charles Faugère. 2002. A new efficient algorithm for computing Gröbner bases without reduction to zero (F5). In *Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation (Lille, France) (ISSAC '02)*. Association for Computing Machinery, New York, NY, USA, 75–83. https://doi.org/10.1145/780506.780516

[19] Jean-Charles Faugère, Pierrick Gaudry, Louise Huot, and Guénaël Renault. 2014. Sub-Cubic Change of Ordering for Gröbner Basis: A Probabilistic Approach. In *Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation (ISSAC '14)*. Association for Computing Machinery, New York, NY, USA, 170–177. https://doi.org/10.1145/2608628.2608669

[20] Jean-Charles Faugère, Patrizia Gianni, Daniel Lazard, and Teo Mora. 1993. Efficient Computation of Zero-dimensional Gröbner Bases by Change of Ordering. *Journal of Symbolic Computation* 16, 4 (1993), 329–344. https://doi.org/10.1006/jsco.1993.1051

[21] Jean-Charles Faugère and Chenqi Mou. 2017. Sparse FGLM Algorithms. *Journal of Symbolic Computation* 80 (2017), 538–569. https://doi.org/10.1016/j.jsc.2016.07.025

[22] Jorge García Fontán, Abhilash Nayak, Sébastien Briot, and Mohab Safey El Din. 2022. Singularity Analysis for the Perspective-Four and Five-Line Problems.

International Journal of Computer Vision 130, 4 (2022), 909–932. https://doi.org/10.1007/s11263-021-01567-4

[23] Patrizia Gianni. 1989. Properties of Gröbner Bases under Specializations. In *Eurocal '87 (Lecture Notes in Computer Science)*, James H. Davenport (Ed.). Springer, Berlin, Heidelberg, 293–297. https://doi.org/10.1007/3-540-51517-8_128

[24] Marc Giusti, Grégoire Lecerf, and Bruno Salvy. 2001. A Gröbner Free Alternative for Polynomial System Solving. *Journal of Complexity* 17, 1 (2001), 154–211. https://doi.org/10.1006/jcom.2000.0571

[25] Hans-Gert Gräbe. 1993. On Lucky Primes. *Journal of Symbolic Computation* 15, 2 (1993), 199–209. https://doi.org/10.1006/jsco.1993.1014

[26] Philippe Guillaume and Alain Huard. 2000. Multivariate Padé Approximation. *J. Comput. Appl. Math.* 121, 1 (2000), 197–219. https://doi.org/10.1016/S0377-0427(00)00337-X

[27] Martin Helmer and Vidit Nanda. 2023. Conormal Spaces and Whitney Stratifications. *Foundations of Computational Mathematics* 23, 5 (Oct. 2023), 1745–1780. https://doi.org/10.1007/s10208-022-09574-8 arXiv:2106.14555 [cs, math]

[28] Evelyne Hubert. 2003. Notes on Triangular Sets and Triangulation-Decomposition Algorithms I. In *Symbolic and Numerical Scientific Computation (Lecture Notes in Computer Science)*. Springer, 1–39. https://doi.org/10.1007/3-540-45084-X_1

[29] Michael Kalkbrener. 1989. Solving Systems of Algebraic Equations by Using Gröbner Bases. In *Eurocal '87, James H. Davenport (Ed.). Springer, Berlin, Heidelberg, 282–292. https://doi.org/10.1007/3-540-51517-8_127*

[30] Monique Lejeune-Jalabert. 1986. *Effectivité de calculs polynomiaux. Cours de D.E.A. Laboratoire de Mathématiques associé au C. N. R. S.*

[31] Vincent Neiger and Eric Schost. 2020. Computing Syzygies in Finite Dimension Using Fast Linear Algebra. *Journal of Complexity* 60 (2020), 101502. https://doi.org/10.1016/j.jco.2020.101502

[32] Franz Pauer. 1992. On Lucky Ideals for Gröbner Basis Computations. *Journal of Symbolic Computation* 14, 5 (1992), 471–482. https://doi.org/10.1016/0747-7171(92)00018-Y

[33] Éric Schost. 2003. Computing parametric geometric resolutions. *Appl. Algebra Engrg. Comm. Comput.* 13, 5 (2003), 349–393. https://doi.org/10.1007/s00200-002-0109-X

[34] Éric Schost and Catherine St-Pierre. 2023. P-Adic Algorithm for Bivariate Gröbner Bases. In *Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation (ISSAC '23)*. Association for Computing Machinery, New York, NY, USA, 508–516. https://doi.org/10.1145/3597066.3597086

[35] J. T. Schwartz. 1980. Fast Probabilistic Algorithms for Verification of Polynomial Identities. *J. ACM* 27, 4 (Oct. 1980), 701–717. https://doi.org/10.1145/322217.322225

[36] The OSCAR team. 2022. OSCAR – Open Source Computer Algebra Research System.

[37] Carlo Traverso. 1989. Gröbner Trace Algorithms. In *Symbolic and Algebraic Computation (Lecture Notes in Computer Science)*, P. Gianni (Ed.). Springer, Berlin, Heidelberg, 125–138. https://doi.org/10.1007/3-540-51084-2_12

[38] Carlo Traverso. 1996. Hilbert Functions and the Buchberger Algorithm. *Journal of Symbolic Computation* 22, 4 (1996), 355–376. https://doi.org/10.1006/jsco.1996.0056

[39] Franz Winkler. 1988. A p-adic Approach to the Computation of Gröbner Bases. *Journal of Symbolic Computation* 6, 2 (1988), 287–304. https://doi.org/10.1016/S0747-7171(88)80049-X