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

HAL
open science

# Solving parametric polynomial systems using Generic Rational Univariate Representation

Florent Corniquel

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

## To cite this version:

Florent Corniquel. Solving parametric polynomial systems using Generic Rational Univariate Representation. 2026. hal-05487354

HAL Id: hal-05487354

https://hal.science/hal-05487354v1

Preprint submitted on 6 Feb 2026

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.
# Solving parametric polynomial systems using Generic Rational Univariate Representation

Florent Corniquel¹

Sorbonne Université, Université Paris-Cité, CNRS (IMJ-PRG), INRIA

florent.corniquel@inria.fr

**Abstract.** In this paper, we present a generic parametrization of generically zero-dimensional parametric polynomial systems. More specifically, we study the specialization properties of the Rational Univariate Representation and derive bounds on the degrees and heights of its elements. In addition to that, we propose two algorithms to effectively compute this parametrization.

**Keywords:** computer algebra, polynomial systems, parametric systems, zero-dimensional

# 1 Introduction

## 1.1 Classical zero-dimensional case

Consider $K$ a field with characteristic zero and $f_1, \dots, f_n \in K[X_1, \dots, X_n]$ polynomials that generate a zero-dimensional ideal $\mathcal{I}$. It is possible to find a parametrization of the affine variety $V(\mathcal{I})$ using Chow forms. Define the so called Chow form by $h(U_0, \dots, U_n) := \prod_{x \in V(\mathcal{I})} (U_0 - x_1 U_1 - \dots - x_n U_n)^{\mu(x)}$ where $U_0, \dots, U_n$ are independent variables and $\mu(x)$ denotes the multiplicity of $x$. We then chose coefficients $a_1, \dots, a_n \in K$ such that the linear form $t = a_1 X_1 + \dots + a_n X_n$ is injective on $V(\mathcal{I})$. In that case, we say that $t$ separates $V(\mathcal{I})$. The initial system $f_1 = \dots = f_n = 0$ then becomes equivalent to the one given by

$$ \left\{ \begin{array}{l} h(U_0, a_1, \dots, a_n) = 0 \\ X_i = \frac{\partial h}{\partial U_i}(U_0, a_1, \dots, a_n), \quad 1 \le i \le n \end{array} \right. . $$

We denote by $h_0 := h(U_0, a_1, \dots, a_n)$, $h_1 := \frac{\partial h}{\partial U_0}(U_0, a_1, \dots, a_n)$ and $h_{X_i} := \frac{\partial h}{\partial U_i}(U_0, a_1, \dots, a_n)$ for $i \in [1, n]$. Here, $[1, n]$ is the set of integers between 1 and $n$. The family $\mathcal{F} := \{h_0, h_1, h_{X_1}, \dots, h_{X_n}\} \subseteq K[U_0]$ is called a *Rational Univariate Representation (RUR)* of $V(\mathcal{I})$.

Different approaches have been tried to compute these polynomials. Renergar in [25] expresses $h$ as a factor of Van der Waerden's $u$-resultant. The main issue with this approach is that the $u$-resultant can identically vanish, for example when the variety $V(\mathcal{I})$ has a component of dimension greater than zero or
points at infinity. However, this problem can be solved using Canny's Generalized Characteristic Polynomial ([3]).

The most successful implementations have been based on the knowledge of the quotient $\mathcal{A} := K[X_1, \dots, X_n]/\mathcal{I}$, and more specifically through a basis $\mathcal{B} = \{p_1, \dots, p_D\}$ of $\mathcal{A}$ as well as the multiplication matrices $M_{X_1, \dots, X_n}$ by each variable in $\mathcal{A}$. These can be computed from a Gröbner basis of the initial system with $O(nD^3)$ operations in $K$ (see for example [10]). This approach is sharpened by Rouillier in [26] where he shows that the elements of $\mathcal{F}$ can be computed using traces of multiplication matrices with regard to $\mathcal{B}$. The fact that the linear form $t = a_1X_1 + \dots + a_nX_n$ separates $V(\mathcal{I})$ is crucial and the proposed algorithm is Las-Vegas : the linear form is chosen "randomly" and certified to be injective afterwards.

Certifying that the form $t$ separates $V(\mathcal{I})$ is an important part of the problem which in most cases turns out to be as costly as the computations of the polynomials. As the polynomials $h_0, h_1, h_{X_1}, \dots, h_{X_n}$ can be computed without knowing whether $t$ separates $V(\mathcal{I})$ or not, the family $\mathcal{F}$ is rather called a *Rational Univariate Representation-candidate* (RUR-candidate) in general, and specified to be a RUR when $t$ is separating. This distinction makes sense as the elements of $\mathcal{F}$ can be computed anyway.

In [8], the authors propose a new Las-Vegas algorithm which given a zero-dimensional ideal $\mathcal{I}$ solves both the problem of computing a RUR of $V(\mathcal{I})$ and certifying that a given linear form $t$ is separating in $\tilde{O}(D^2\delta + nD^2(D - \delta + 1))$ arithmetic operations, from the knowledge of the multiplication matrices $M_{X_1, \dots, X_n}$ by the variables in the quotient algebra $K[X_1, \dots, X_n]/\mathcal{I}$. Here, $\delta$ is the degree of the minimal polynomial of $t$ and $D$ is the dimension of the quotient algebra.

## 1.2 Parametric systems

In the case of parametric systems, we consider $f_1, \dots, f_n \in K[W, X]$. We say that $W := [W_1, \dots, W_s]$ represents the parameters (which we want to replace by specific values) and that $X := [X_1, \dots, X_n]$ are the unknowns that we would like to express in terms of the parameters. Different approaches exist and we will briefly summarize them.

First, one can mention comprehensive Gröbner bases first introduced by Weispfenning in [31]. A comprehensive Gröbner basis can be understood as a family of polynomials which specializes to a Gröbner basis of the specialized system for all values of parameters. They are usually built from a Gröbner system, that is, a family of couple $(S_i, G_i)$ such that $S_i$ is a constructible subset of the parameters space and $G_i$ specializes to a Gröbner basis for all parameters values in $S_i$. The $S_i$'s are constructed to form a partition of the parameters space and the main drawback of the method is the size of the partition which tends to exponentially grow. This method comes with a very high complexity and it is not clear whether it can be effectively implemented.

In his Ph. D. thesis ([28, Chapter 7]), Eric Schost extends the use of triangular sets to solve parametric systems by working in $\mathbb{Q}(W)[X]$. He reaches a bound on
the degree of the polynomials appearing in the triangular sets not better than $d^{o(n^2)}$ where $d$ is the maximum degree of the polynomials in the initial system, and does not try to implement the method. After that, Schost proposes in [29] a probabilistic algorithm to compute a parametric resolution. The idea is to lift the solution of a specialized system using a formal Newton operator. The use of Straight-Line Programs allows him to reach a polynomial complexity in the size of the output. However, the proposed solution works when excluding the jacobian ideal, which means by excluding possible multiplicities.

In general, studying parametric systems is difficult and asking for certified pieces of information concerning the system often leads to costly computations. For example in the case of real geometry, Collins introduces in [4] the Cylindrical Algebraic Decomposition (CAD) which is a partition of the space into cells where given polynomials have a constant sign. The complexity is known to be doubly exponential in the worst case with regard to the number of variables (see for example [6]).

This technique can for example complement the computation of a discriminant variety of the space of parameters. This object introduced in [17] is a variety formed by the parameters values for which the specialized system has a "bad" behavior like roots at infinity or an infinite number of solutions. This variety has a very convenient property : its complement is a union of open subsets where the specialized system has a finite and constant number of solutions. The authors in [17] propose an algorithm to compute the discriminant variety and one can also compute a CAD of its complement to get an explicit description of the aforementioned open subsets. However, the complexity of computing a discriminant variety is also essentially exponential (see [23]).

Finally, we can mention the work done in [18] where the authors compute semi-algebraic formulas defining semi-algebraic subsets of the parameters space where the specialized system has a constant number of real solutions. Their approach relies on computing the matrix of the parametric Hermite's quadratic form and study its rank.

## 1.3 Contributions and outline of the article

In Section 2, we introduce the notion of Generic Rational Univariate Representation (GRUR) and show that the Rational Univariate Representation (RUR) (in the sense introduced by Rouillier in [26]) computed in $C(W)$ has great specialization properties. Consider $t \in C[X]$ a linear form that separates the specialized variety for almost all values of parameters. Then we show that except for an algebraic set of parameters with measure zero, the RUR computed in $C(W)[X]$ specializes to a Rational Univariate Representation of the specialized variety thus justifying the name of *Generic* RUR. For that purpose, we construct the parametric *u*-resultant of the system using Van der Waerden's approach and study its specialization behavior.

Unfortunately, this approach is too costly complexity-wise. Indeed, even though the *u*-resultant can be computed from the Macaulay matrix as the quotient of two determinants (see [20]), factorizing this resultant quickly becomes
too hard. However, we can derive bounds for the degrees and height of the polynomials of the GRUR from this. We present it in Section 3 by making good use of some Arithmetic Nullstellensatz proved in [5].

In Section 4 and 5, we propose two different algorithms to compute the GRUR. The first one relies on linear algebra and more precisely on the fact that the quotient algebra $C(W)[X]/\mathcal{I}_W$, where $\mathcal{I}_W$ is the ideal generated by the equations in $C(W)[X]$, is a vector space of finite dimension. This approach is based on the work of [26]. The second algorithm is based on an evaluation/interpolation scheme. The idea is to compute as many specialized RURs as possible using the new algorithm proposed in [8] and to interpolate the coefficients of the GRUR. If the initial equations have degree in $X$ bounded by $d_X$ and degree in $W$ bounded by $d_W$, we show that the GRUR can be computed using $\tilde{O}(sn^{2s+2}d_X^{2ns+2n}d_W^{2s+1} + n^{s+1}d_X^{2ns+5n}d_W^s)$ operations in $\mathbb{Q}$. We can then use the first polynomial of the computed GRUR to tackle the real roots classification problem and propose an algorithm to solve it whose complexity is higher than existing algorithms, but does not require any assumption on the system.

## 2 Construction of the GRUR

We start by introducing some notations.

- $W := [W_1, \dots, W_s]$ are parameters and $X := [X_1, \dots, X_n]$ are unknowns;

- given a value of parameters $w \in \mathbb{C}^s$, we denote by $\phi_w$ the specialization morphism that sends $W_i$ to $w_i$;

- we denote by respectively $\langle X := \text{grevlex}(X)$ and $\langle W := \text{grevlex}(W)$ the graded reverse lexicographic orderings in variables $X$ and $W$, and by $\langle_{X,W} := \text{grevlex}(W) \prec \text{grevlex}(X)$ the associated elimination block ordering;

- we will use the notation LT, LM and LC indicated by "$\prec_X$", "$\prec_W$" or "$\prec_{W,X}$" for the leading term, monomial and coefficient given one of the three aforementioned monomial orderings.

### 2.1 Definition of the GRUR

We consider $f_1, \dots, f_n \in \mathbb{C}[W, X]$ a family of polynomials that generate a generically zero-dimensional ideal $\mathcal{I} := \langle f_1, \dots, f_n \rangle \subseteq \mathbb{C}[W, X]$. Then there exists a Zariski-closed subset $\mathcal{D}$ of $\mathbb{C}^s$ with measure 0 such that for all values of parameters $w \in \mathbb{C}^s \setminus \mathcal{D}$, the specialized ideal $\mathcal{I}(w) := \langle f_1(w, X), \dots, f_n(w, X) \rangle \subseteq \mathbb{C}[X]$ is zero-dimensional, or equivalently, the variety $\mathcal{V}_w := V(\mathcal{I}(w)) \subseteq \mathbb{C}^s$ has dimension zero.

We want to extend the notion of RUR to parametric systems in the sense that we want to find a family of univariate polynomials $\mathcal{F} = \{h_0, h_1, h_{X_1}, \dots, h_{X_n}\} \subseteq \mathbb{C}(W)[U_0]$ such that for almost all values of parameters $w \in \mathbb{C}^s$, we have the equivalence

$$ \left\{ \begin{array}{l} f_1(w, X) = 0 \\ \vdots \\ f_n(w, X) = 0 \end{array} \right. \iff \left\{ \begin{array}{l} h_0(U_0, a_1, \dots, a_n; w) = 0 \\ X_i = \frac{\partial h_i}{\partial U_0(U_0, a_1, \dots, a_n; w)}, \quad 1 \le i \le n \end{array} \right. . \quad (1) $$
with a preservation of the multiplicities. In other words, we want the family $\mathcal{F}$ to specialize to a (classical) RUR of $V(\mathcal{I}(w))$ in the sense of [26, Definition 3.2] for almost all values of parameters. That motivates the following definition.

**Definition 1.** A family $\mathcal{F} := \{h_0, h_1, h_{X_1}, \dots, h_{X_n}\}$ is called a Generic RUR (GRUR) of $V(\mathcal{I}_W)$ (respectively a Generic RUR-candidate) if for almost all $w \in \mathbb{C}^s$ the family $\phi_w(\mathcal{F})$ defines a RUR (respectively a RUR-candidate) of $V(\mathcal{I}(w))$.

We now see $f_1, \dots, f_n$ as elements of $\mathbb{C}(W)[X]$. They generate an ideal $\mathcal{I}_W \subseteq \mathbb{C}(W)[X]$. Denote by $\mathcal{G} \subseteq \mathbb{C}[W, X]$ a reduced Gröbner basis of $\mathcal{I}$ for the product ordering $<_{W,X}$. Then $\mathcal{G} \subseteq \mathbb{C}(W)[X]$ is also a Gröbner basis of $\mathcal{I}_W$ for the ordering $<_X$ (see for example [18]). However, it might not be reduced. We denote by $W_\mathcal{G}$ the variety $\cup_{g \in \mathcal{G}} V(LC_{<X}(g))$.

**Lemma 1.** Denote by $\overline{\mathbb{C}(W)}$ an algebraic closure of $\mathbb{C}(W)$. Then the variety

$$V(I_W) := \{x \in \overline{\mathbb{C}(W)}^n \mid f_1(W, x) = \dots = f_n(W, x) = 0\}$$

has dimension zero.

*Proof.* For all values of parameters $w$ outside of $\mathcal{D} \cup W_\mathcal{G}$, the specialized ideal $\mathcal{I}(w)$ has dimension zero and $\mathcal{G}(w) := \{g(w, X), g \in \mathcal{G}\}$ is a Gröbner basis of $\mathcal{I}(w)$ for $<_X$ (see 8).

By the finiteness theorem (see [7, §5.3 Theorem 6]) there exists non-negative integers $m_1, \dots, m_n$ and $g_1, \dots, g_n \in \mathcal{G}$ such that each $g_i$ has leading monomial $\mathrm{LM}_{<X}(g_i) = X_i^{m_i}$. By hypothesis, we have that $\mathrm{LM}_{<X}(g_i(w, X)) = \mathrm{LM}_{<X}(g_i)$, which also means that $V(\mathcal{I}_W)$ has dimension zero. $\square$

Knowing that $V(\mathcal{I}_W)$ has dimension zero, we can follow the construction of the classical RUR as in the introduction. Consider a linear form $t := a_1X_1 + \dots + a_nX_n \in \mathbb{C}[X]$ (it does not involve $W$) and consider the polynomial $h := \prod_{x \in V(\mathcal{I}_W)} (U_0 - U_1x_1 - \dots - U_nx_n)^{\mu(x)}$ where $\mu(x)$ is the multiplicity of $x$.

We then define polynomials $h_0, h_1, h_{X_1}, \dots, h_{X_n}$ in the following way :

$$\left\{ \begin{array}{l} h_0(U_0; W) := h(U_0, a_1, \dots, a_n; W) \\ h_1(U_0; W) := \frac{\partial h}{\partial U_0}(U_0, a_1, \dots, a_n; W) \\ h_{X_i}(U_0; W) := \frac{\partial h}{\partial U_i}(U_0, a_1, \dots, a_n; W), \quad 1 \le i \le n \end{array} \right. . \qquad (2)$$

**Definition 2.** We say that the linear form $t \in \mathbb{C}[X]$ is generically separating if $t$ separates $V(\mathcal{I}_W)$, that is, if $V(\mathcal{I}(w))$ for almost all values of $w \in \mathbb{C}^s$.

There is a natural algebraic rephrasing of the geometric fact that $t$ separates $V(\mathcal{I}_W)$.

**Proposition 1.** The linear form $t = a_1X_1 + \dots + a_nX_n$ separates $V(\mathcal{I}_W)$ if and only if the discriminant $\mathrm{Disc}_{U_0}(\bar{h}(a_1, \dots, a_n; W)) \in \mathbb{C}(W)$ is not identically zero where $\bar{h}$ is the squarefree part with regard to the variable $U_0$.
*Proof.* We recall that $h := \prod_{x \in V(\mathcal{I}_W)} (U_0 - x_1 U_1 - \cdots - x_n U_n)^{\mu(x)}$. Then, the squarefree part with regard to $U_0$ is given by $\bar{h} := \prod_{x \in V(\mathcal{I}_W)} (U_0 - x_1 U_1 - \cdots - x_n U_n)$. In other words, we get rid of the geometric multiplicities. When we substitute the values of $U_1, \dots, U_n$ to $a_1, \dots, a_n$, we obtain $\bar{h}(U_0, a_1, \dots, a_n; W) = \prod_{x \in V(\mathcal{I}_W)} (U_0 - t(x))$. This polynomial is squarefree if and only if none of the linear factors appearing in the product repeat, that is, if and only if $t$ is injective on $V(\mathcal{I}_W)$. $\square$

**Remark 1.** A linear form that separates $V(\mathcal{I}_W)$ also separates $V(\mathcal{I}(w))$ for almost all $w \in \mathbb{C}^s$. The converse is also true, but two linear forms that both separate $V(\mathcal{I}_W)$ might differ through the algebraic sets of parameters for which they do not separate the specialized system.

**Theorem 1.** Consider $f_1, \dots, f_n \in \mathbb{C}[W, X]$ that generate a generically zero-dimensional ideal $\mathcal{I}$. Let $t = a_1 X_1 + \dots + a_n X_n \in \mathbb{C}[X]$ be a linear form. Then the family $\mathcal{F} := \{h_0, h_1, h_{X_1}, \dots, h_{X_n}\}$ defined by 2 is a GRUR-candidate of $V(\mathcal{I}_W)$. Moreover, if $t$ is generically separating, $\mathcal{F}$ is a GRUR of $V(\mathcal{I}_W)$.

The next subsections are there to give some ingredients to prove Theorem 1. We specify in Corollary 1 the parameters values to avoid.

## 2.2 Van der Waerden-like approach

They key-point in this approach is an idea already used by Renegar in [25]. The idea is that the polynomial $h$ (from which we can derive the elements of $\mathcal{F}$) is a factor of Van der Waerden's $u$-resultant. This resultant has great specialization properties we can use to study the specialization of $h$. Let us quickly recall Van der Waerden's idea ([30, §11.83]). We add a new equation given by $f_0 = 0$ where $f_0 := U_0 - U_1 X_1 - \cdots - U_n X_n$. Here $U := [U_0, \dots, U_n]$ are independent new variables. We then homogeneize $f_0, \dots, f_n$ into $F_0, \dots, F_n$ using a new variable named $X_0$. Observe that $F_0 \in \mathbb{Z}[U][X_0, \dots, X_n]$ and $F_1, \dots, F_n \in \mathbb{C}[W][X_0, \dots, X_n]$. Now $F_0, \dots, F_n$ are $n+1$ polynomials in $n+1$ variables so their resultant is well defined. It is called the $u$-resultant and we write it $\mathrm{Res}(F_0, \dots, F_n)$. It is an element of $\mathbb{C}[W][U_0, \dots, U_n]$.

**Remark 2.** The $u$-resultant can be identically zero. In that case, the method that we describe below will fail. This is the case when the variety has a component of positive dimension for example. With our assumptions, $V(\mathcal{I}_W)$ is zero-dimensional so this will not happen. It can also be identically zero if the projective closure of $V(\mathcal{I}_W)$ has a point at infinity. This problem can be avoided by a generic change of variables (see [22]).

For the rest of this section, we suppose that $V(\mathcal{I}_W)$ has no point at infinity. Denote by $\tilde{F}_i := F_i(0, X_1, \dots, X_n)$. Under these assumptions, the resultant $\mathrm{Res}(\tilde{F}_1, \dots, \tilde{F}_n) \in \mathbb{C}[W]$ is not identically zero and we get the following result.
**Proposition 2.** The u-resultant factorizes as

$$ \mathrm{Res}(F_0, \dots, F_n)(U; W) = \mathrm{Res}(\tilde{F}_1, \dots, \tilde{F}_n)(W) \prod_{x \in V(\mathcal{I}_W)} (U_0 - x_1 U_1 - \dots - x_n U_n)^{\mu(x)}. \quad (3) $$

*Proof.* First, the Poisson formula for homogeneous resultants (see [14, Proposition 2.7]) gives that $\mathrm{Res}(F_0, \dots, F_n) = \mathrm{Res}(\tilde{F}_1, \dots, \tilde{F}_n) \cdot \det(m_{f_0})$ where $m_{f_0}$ is the endomorphism of multiplication by $f_0$ in the quotient $\mathbb{C}(W)[X]/\mathcal{I}_W$. We can then apply Stickelberger's theorem 5 to get the announced expression. □

We recall that $h(U; W) = \prod_{x \in V(\mathcal{I}_W)} (U_0 - x_1 U_1 - \dots - x_n U_n)^{\mu(x)}$ and that given $t = a_1 X_1 + \dots + a_n X_n$ we have $h_0(U_0; W) = h(U_0, a_1, \dots, a_n; W)$.

## 2.3 Proof of Theorem 1

First we prove that the family $\mathcal{F} = \{h_0, h_1, h_{X_1}, \dots, h_{X_n}\}$ is a GRUR-candidate. We show that $\phi_w(\mathcal{F})$ is a RUR-candidate of $V(\mathcal{I}(w))$ in the sense of [26, Definition 3.2]. Let us introduce a short lemma.

**Lemma 2.** For all $i \in [1, n]$,

$$ \frac{\frac{\partial \bar{h}}{\partial U_i}(U_0, a_1, \dots, a_n; W)}{\frac{\partial h}{\partial U_0}(U_0, a_1, \dots, a_n; W)} = \frac{h_{X_i}(U_0; W)}{h_1(U_0; W)} \quad (4) $$

where $\bar{h}$ is the squarefree part with regard to $U_0$.

*Proof.* The left-hand side in Equation (4) is just the reduced version of the right-hand side. By multiplying both the numerator and the denominator of the right-hand side by $\prod_{y \in V(\mathcal{I}_W)} (U_0 - x_1 U_1 - \dots - x_n U_n)^{\mu(x)-1}$ we get the result. □

The meaning of this lemma is that in the definition of the RUR given by Rouillier, using $h_0$ or its squarefree part to define the rational fractions does not change anything. In our case, we will use the formulas with multiplicities as they have better specialization properties. Thus, using that $\phi_w$ commutes with derivatives, the only remaining thing to show is that for almost all $w \in \mathbb{C}^s$, $h_0(U_0; w)$ is the characteristic polynomial of the multiplication by $t$ in the quotient $\mathbb{C}[X]/\mathcal{I}(w)$, that is, that $h_0(U_0; w) = \prod_{x \in V(\mathcal{I}(w))} (U_0 - t(x))^{\mu(x)}$.

With that objective in mind, let us summarize the algebraic sets of $\mathbb{C}^s$ that will appear in what follows :

- we recall that $\mathcal{D}$ is the set of parameters for which the specialized system is not zero-dimensional ;

- we denote by $\mathcal{L} := \cup_{i=0}^n V(LT_{<X}(f_i)) \subseteq \mathbb{C}^s$ the set of parameters for which one or more of the leading coefficient in $X$ of the initial equations vanish ;

- we denote by $\mathcal{S}$ the set of parameters $w$ for which $t$ is not injective on $V(\mathcal{I}(w))$ ;
- we denote by $W_\infty$ the set of parameters for which the specialized system has roots at infinity.

**Remark 3.** The fact that $W_\infty$ is an algebraic set comes from the fact that $W_\infty = V(\mathrm{Res}(\tilde{F}_1, \dots, \tilde{F}_n))$.

We start by studying the specialization of formula (3).

**Lemma 3.** For any value of parameters $w \in \mathbb{C}^s \setminus \mathcal{L}$, both resultants appearing in 3 specialize. In other words,

$$ \phi_w(\mathrm{Res}(F_0, \dots, F_n)) = \mathrm{Res}(\phi_w(F_0), \dots, \phi_w(F_n)) \quad (5) $$

and

$$ \phi_w(\mathrm{Res}(\tilde{F}_1, \dots, \tilde{F}_n)) = \mathrm{Res}(\phi_w(\tilde{F}_1), \dots, \phi_w(\tilde{F}_n)) \quad (6) $$

*Proof.* Resultants specialize as long as the degrees of their arguments do not change. Outside of $\mathcal{L}$, the degrees of $f_0, \dots, f_n$ and thus those of $F_0, \dots, F_n$ and $\tilde{F}_1, \dots, \tilde{F}_n$ do not change after specializing so both resultants specialize. $\square$

That specialization property makes us able to identify what the polynomial $h(U; W)$ specializes to.

**Lemma 4.** For any value of parameters $w \in \mathbb{C}^s \setminus (\mathcal{D} \cup \mathcal{L} \cup W_\infty)$, we have

$$ \phi_w(h(U; W)) = \prod_{x \in V_w} (U_0 - x_1 U_1 - \dots - x_n U_n)^{\mu(x)}. \quad (7) $$

*Proof.* First, we can use one more time the Poisson formula from [14, Proposition 2.7] and Stickelberger's theorem to get that

$$ \mathrm{Res}(\phi_w(F_0), \dots, \phi_w(F_n)) = $$

$$ \mathrm{Res}(\phi_w(\tilde{F}_1), \dots, \phi_w(\tilde{F}_n)) \prod_{x \in V(\mathcal{I}(w))} (U_0 - x_1 U_1 - \dots - x_n U_n)^{\mu(x)}. \quad (8) $$

We can then substitute (5) and (6) into (8). Because $w \notin W_\infty$, the specialized system has no root at infinity, and thus formula (8) is non trivial. We can compare it to the specialization of (3) to yield the wanted formula. $\square$

Now we just have to substitute the values $U_1, \dots, U_n$ to $a_1, \dots, a_n$ in (7) to get

$$ \phi_w(h(U_0, a_1, \dots, a_n; W)) = \phi_w(h_0) = \prod_{x \in V(\mathcal{I}(w))} (U_0 - t(x))^{\mu(x)}. \quad (9) $$

and the right hand side of this equation is exactly the characteristic polynomial of the multiplication by $t$ in the quotient $\mathbb{C}[X]/\mathcal{I}(w)$ (this is once again Stickelberger's theorem). We summarize everything in the following proposition.
**Proposition 3.** For any values of the parameters $w \in \mathbb{C}^s \setminus (\mathcal{D} \cup \mathcal{L} \cup W_\infty)$ the family $\phi_w(\mathcal{F})$ is a RUR-candidate of $V(\mathcal{I}(w))$.

We now suppose that the linear form $t$ is generically separating and we denote by $S \subseteq \mathbb{C}^s$ the algebraic set of measure 0 formed by the $w \in \mathbb{C}^s$ for which $t$ is not injective on $V(\mathcal{I}(w))$. We have an immediate corollary.

**Corollary 1.** For any values of the parameters $w \in \mathbb{C}^s \setminus (\mathcal{D} \cup \mathcal{L} \cup W_\infty \cup S)$, the family $\phi_w(\mathcal{F})$ is a RUR of $V(\mathcal{I}(w))$.

*Proof.* We know from Proposition 3 that $\mathcal{F}$ specializes to a RUR-candidate of $V(\mathcal{I}(w))$. It becomes a RUR whenever $t$ separates $V(\mathcal{I}(w))$. By definition, this is the case when $w \notin S$.

*Remark 4.* We have the inclusion $\mathcal{D} \subseteq W_\infty$ so the generic condition can be expressed as $w \in \mathbb{C}^s \setminus (W_\infty \cup \mathcal{L} \cup S)$. The statement comes from the fact that if $w \in \mathcal{D}$, then $V(\mathcal{I}(w))$ has dimension zero and thus its projective closure intersects the hyperplane at infinity, that is, $w \in W_\infty$.

## 3 Size of the GRUR

We present in this section some bounds that can be obtained on the degrees and size of the polynomials of the GRUR.

In what follows, we will use the notation $\mathfrak{h}(f) := \log_2(\|f\|_\infty)$ for the height of a polynomial $f$ with integer coefficients. We suppose for this section that $f_1, \dots, f_n$ have integer coefficients by chasing denominators. We denote by:

- $d_{1,X}, \dots, d_{n,X}$ the total degrees of $f_1, \dots, f_n$ in $X$ and $d_X := \max_{1 \le i \le n} d_{i,X}$;

- $d_{1,W}, \dots, d_{n,W}$ the total degrees of $f_1, \dots, f_n$ in $W$ and $d_W := \max_{1 \le i \le n} d_{i,W}$;

- $c := \max_{1 \le i \le n} \|f_i\|_\infty$ the maximum coefficient among $f_1, \dots, f_n$ and $\tau := \max_{1 \le i \le n} \mathfrak{h}(f_i)$.

### 3.1 Bounds for $\mathfrak{h}$

The work presented in this section makes great use of the arithmetic Nullstellensatz presented in [5]. We warmly thank Teresa Krick for the reference.

**Theorem 2.** There exists $\Delta \in \mathbb{Z}[W][U]$ and $P \in \mathbb{Z}[W]$ such that

$$h(U; W) = \frac{\Delta(U; W)}{P(W)}$$

with the following bounds:

- $\deg_U(\Delta) \le d_X^n$;

- $\deg_W(\Delta) \le (n+1)d_X^n d_W$;

- $\deg_W(P) \le nd_X^{n-1}d_W$;

- $\mathfrak{h}(\Delta), \mathfrak{h}(P) \le O的日$nd_X^n\tau + nd_X^n d_W \log_2(s+1)$.
*Proof.* We start by following the ideas of [5, Example 4.18 and 4.37] and consider the generic polynomials of total degrees $d_0, \dots, d_n$

$$ \mathbf{F}_j := \sum_{|\alpha|=d_j} u_{j,\alpha} X^{\alpha}, \quad 0 \le j \le n $$

where $\mathbf{u}_j := \{u_{j,\alpha}, |\alpha| = d_j\}$ and $X^{\alpha} = X_0^{\alpha_0} \cdots X_n^{\alpha_n}$. Denote by $\mathbf{u} := \{\mathbf{u}_1, \dots, \mathbf{u}_n\}$. These generic coefficients will later be specialized to those of $F_0, \dots, F_n$ of the previous section.

The arithmetic Nullstellensätz in [5, Theorem 4.28] applied to $V = \mathbb{A}_Q^n$ and $\mathbf{F}_0, \dots, \mathbf{F}_n$ states that there exists $\alpha \in \mathbb{Z}[\mathbf{u}]$ and $g_0, \dots, g_n \in \mathbb{Z}[\mathbf{u}, X]$ such that

$$ g_0(\mathbf{u}, X)\mathbf{F}_0 + \dots + g_n(\mathbf{u}, X)\mathbf{F}_n = \alpha \quad (10) $$

with the following bounds on the degrees and the height:

$$ - \deg_{\mathbf{u}_l}(\alpha) \le \prod_{\substack{j=0 \\ j \ne l}}^{n} d_j, \quad 0 \le l \le n; $$

$$ - \mathfrak{h}(\alpha) \le d_X^{n-1}(6n+10) \log_2(n+2). $$

The resultant $\mathrm{Res}(\mathbf{F}_0, \dots, \mathbf{F}_n)$ generates the elimination ideal $\langle \mathbf{F}_0, \dots, \mathbf{F}_n \rangle \cap \mathbb{Z}[\mathbf{u}]$ so there exists some $\Lambda \in \mathbb{Z}[\mathbf{u}]$ such that $\alpha = \Lambda \mathrm{Res}(\mathbf{F}_0, \dots, \mathbf{F}_n)$. It is well known (see for example [7, §3.3, Theorem 3.1]) that $\mathrm{Res}(\mathbf{F}_0, \dots, \mathbf{F}_n)$ has partial degree $\deg_{\mathbf{u}_l}$ equal to $\prod_{\substack{j=0 \\ j \ne l}}^{n} d_j$. In other words, $\Lambda$ has partial degree in each variable equal to zero, that is, $\Lambda \in \mathbb{Z}$.

We can then specialize the coefficients $\mathbf{u}$ to those of $F_0, \dots, F_n$. Relation (10) transforms into

$$ G_0(W, X)F_0 + \dots + G_n(W, X)F_n = \Lambda \mathrm{Res}(F_0, \dots, F_n) $$

where $G_0, \dots, G_n \in \mathbb{Z}[W, X]$.

We know from Proposition 2 that the $\mathrm{Res}(F_0, \dots, F_n)$ factorizes into a product $C(W)h(U; W)$ where $C = \mathrm{Res}(\tilde{F}_1, \dots, \tilde{F}_n)$.

Let us denote by $\Delta := \Lambda \mathrm{Res}(F_0, \dots, F_n) \in \mathbb{Z}[W][U]$. That means we have

$$ h(U; W) = \frac{\Delta(U; W)}{P(W)} \quad (11) $$

where $P(W) := \Lambda C(W)$.

What we want now is a bound on the degree in $W$ and a bound on the height of $\Delta$ and $\Lambda C$ to derive bounds for the polynomials of the GRUR. Thanks to the definition of $h(U; W)$, we know that $\deg_U(\Delta) \le d_X^n$.

The bounds given by [5, Theorem 4.28] on Equation (10) can be derived into bounds for $\Delta$. Indeed, we specialize Equation (10) with the coefficients of $F_0, \dots, F_n$ which have degrees in $W$ at most $d_W$. For each $l \in [0, n]$, $\alpha$ has partial degree in $\mathbf{u}_l$ bounded by $d_X^n$ so the total degree in $\mathbf{u}$ is bounded by $(n+1)d_X^n$ and thus $\deg_W(\Delta) \le (n+1)d_X^n d_W$.

For the bound on the height, we use a lemma presented in [5, Lemma 2.37]
**Lemma 5.** Let $f_1, \dots, f_r \in \mathbb{Z}[x_1, \dots, x_k]$ with total degrees bounded by $d$, bitsize bounded by $\tau$, and let $g \in \mathbb{Z}[y_1, \dots, y_r]$. Then

$$ \mathfrak{h}(f_1 \cdots f_r) \le \sum_{i=1}^{r} \mathfrak{h}(f_i) + \log_2(k+1) \sum_{i=2}^{r} \deg(f_i), $$

and

$$ \mathfrak{h}(g(f_1, \dots, f_r)) \le \mathfrak{h}(g) + \deg(g)(\tau + \log_2(r+1) + d \log_2(k+1)). $$

In our case, the $f_i$'s are the coefficients of $F_0, \dots, F_n$ so $r \le n(d_X+1)^n+(n+1)$ and $k=s$. Using the bounds on $\alpha$, and keeping only the dominant terms, we get

$$ \mathfrak{h}(\Delta) \le O的日_X^n\tau + nd_X^n d_W \log_2(s+1)). $$

In addition to that, since $\mathfrak{h}(\Lambda) \le \mathfrak{h}(\Delta)$, that bound is also true for $\Lambda$.

We can follow a very similar reasoning to get an upper bound on the height of $C$ as it is the resultant of $\tilde{F}_1, \dots, \tilde{F}_n$. Indeed, $\tilde{F}_1, \dots, \tilde{F}_n$ have the same degrees in $X$ as $F_1, \dots, F_n$ and we can take the bound $\tau$ for their height. Denote by $\mathbf{u}' := \mathbf{u}_1, \dots, \mathbf{u}_n$. We first apply theorem 4.28 from [5] to the generic polynomials $\mathbf{F}_1, \dots, \mathbf{F}_n$ and thus get the existence of $\beta \in \mathbb{Z}[\mathbf{u}']$ and $z_1, \dots, z_n \in \mathbb{Z}[\mathbf{u}', X]$ such that

$$ z_1(\mathbf{u}', X)\mathbf{F}_1 + \cdots + z_n(\mathbf{u}', X)\mathbf{F}_n = \beta $$

with the following bounds on the degrees and the height:

$$ - \deg_{\mathbf{u}_l}(\beta) \le \prod_{\substack{j=1 \\ j \ne l}}^{n} d_j \le d_X^{n-1}, \quad 1 \le l \le n; $$

$$ - \mathfrak{h}(\beta) \le d_X^{n-2}(6n+10) \log_2(n+2). $$

In addition to that, $\beta = \Lambda' \mathrm{Res}(\mathbf{F}_1, \dots, \mathbf{F}_n)$ with $\Lambda' \in \mathbb{Z}$ just like before. We can then use lemma 5 to yield a bound on the height of $\Lambda'C$ which can be kept as a bound on the height of $C$. Once again we only keep the dominant terms.

$$ \mathfrak{h}(C) \le O的日_X^{n-1}\tau + nd_X^{n-1}d_W \log_2(s+1)). \quad (12) $$

Since $\mathfrak{h}(\Lambda C) = \mathfrak{h}(\Lambda) + \mathfrak{h}(C)$, we get $\mathfrak{h}(P) = \mathfrak{h}(\Lambda C) \le O的日_X^n\tau + nd_X^n d_W \log_2(s+1))$.

For the degree, we use the fact that $\mathrm{Res}(\mathbf{F}_1, \dots, \mathbf{F}_n)$ has total degree in $\mathbf{u}'$ bounded by $nd_X^{n-1}$, and thus that $C$ (which means also $P$) has degree in $W$ at most $nd_X^{n-1}d_W$. $\square$

## 3.2 Bounds for the GRUR polynomials

Now that we have a bound on the degree and the height of $h(U; W)$, we can deduce bounds on the degree and the height of the polynomials of the family $\mathcal{F}$. We write that $f = \tilde{O}(g)$ when $f = O(g \log_2^k(g))$ for some $k \ge 0$.
**Corollary 2.** Suppose that $a_1X_1 + \cdots + a_nX_n \in \mathbb{Q}[X]$ is a generically separating form. Then the polynomials $h_0, h_1, h_{X_1}, \ldots, h_{X_n}$ of the GRUR have a height bounded by

$$O的日X_n\tau + 日X_n dW \log_2(s+1) + n^2日X_n \log_2(d_X)) = \tilde{O}(日X_n\tau + 日X_n dW \log_2(s+1))$$
and degree in W bounded by

$$\kappa := (n+1)d_X^n dW$$

We consider the height and the degree to be the maximum of those of the respective numerators and the denominators.

*Proof.* Denote by $\tau_t$ the height of the linear form $t$. In [26, Lemma 2.1], it is shown that one can find a linear form that separates $V(\mathcal{I}_W)$ in the set $\mathcal{T} = \{X_1 + kX_2 + \cdots + k^{n-1}X_n, 0 \le k \le nD(D-1)/2\}$. In other words, the chosen linear form will have its coefficients not bigger than $(nd_X^{2n})^{n-1}$ which means that $\tau_t \le O(n \log_2(n) + n^2 \log_2(d_X))$.

Let us begin with the polynomial $h_0(U_0; W)$ which is obtained as $h_0(U_0; W) = h(U_0, a_1, \ldots, a_n; W) = \Delta(U_0, a_1, \ldots, a_n; W)/P(W)$. Specializing the variables $U$ does not affect the denominator $P$. It does not change the bound on the degree in $W$ of $\Delta$ either. For the height, we can use once more lemma 5 to get

$$\mathfrak{h}(\Delta(U_0, a_1, \ldots, a_n; W)) \le \mathfrak{h}(\Delta) + \deg_U(\Delta)(\tau_t + \log_2(n+1)) \\ \le \mathfrak{h}(\Delta) + d_X^n \tau_t + d_X^n \log_2(n+1)$$

and by keeping the dominant terms,

$$\mathfrak{h}(\Delta(U_0, a_1, \ldots, a_n; W)) \le O的日X_n\tau + 日X_n dW \log_2(s+1) + n^2日X_n \log_2(d_X)).$$

Then the polynomials $h_1, h_{X_1}, \ldots, h_{X_n}$ are obtained as

$$h_1(U_0; W) = \frac{\partial h}{\partial U_1}(U_0, a_1, \ldots, a_n; W) = \frac{\frac{\partial \Delta}{\partial U_1}(U_0, a_1, \ldots, a_n; W)}{P(W)}$$

and

$$h_{X_k}(U_0; W) = \frac{\partial h}{\partial U_k}(U_0, a_1, \ldots, a_n; W) = \frac{\frac{\partial \Delta}{\partial U_k}(U_0, a_1, \ldots, a_n; W)}{P(W)}, \quad 1 \le k \le n.$$

Each $\partial\Delta/\partial U_i$ has height bounded by $\mathfrak{h}(\Delta) + n \log_2(d_X)$ and using once more lemma 5 we get

$$\mathfrak{h}\left(\frac{\partial \Delta}{\partial U_i}(U_0, a_1, \ldots, a_n; W)\right) \le \mathfrak{h}(\Delta) + n \log_2(d_X) + d_X^n \tau_t + d_X^n \log_2(n+1) \\ \le O的日X_n\tau + 日X_n dW \log_2(s+1) + n^2日X_n \log_2(d_X)).$$

Since the height of $P$ is not bigger than that, the bounds on the height of $h_1, h_{X_1}, \ldots, h_{X_n}$ are proved.

We present in the two following sections two Las-Vegas algorithm to compute the polynomials of $\mathcal{F}$. The first one relies on linear algebra and the second one is based on a evaluation/interpolation scheme.
# 4 First algorithm : linear algebra approach

In this subsection we will simultaneously work with the generic quotient $\mathcal{A}_W := \mathbb{C}(W)[X]/\mathcal{I}_W$ and the specialized quotient for values $w \in \mathbb{C}^s$ that we denote by $\mathcal{A}(w) := \mathbb{C}[X]/\mathcal{I}(w)$. Every object related to one of these quotients will have an exponent $\mathcal{A}_W$ or $\mathcal{A}(w)$ (or an index) to make the distinction. This distinction will be particularly useful to show specialization properties. For any $v \in \mathbb{C}(W)[X]$, we will denote by respectively Trace$^{\mathcal{A}W}(v)$ and $\chi_v^{\mathcal{A}W}$ the trace and characteristic polynomial of

$$m_v^{\mathcal{A}W} : \mathcal{A}_W \to \mathcal{A}_W. \\ [f]_{\mathcal{A}_W} \mapsto [fv]_{\mathcal{A}_W}$$

We choose analogous notations for $v \in \mathbb{C}[X]$ by replacing $\mathcal{A}_W$ by $\mathcal{A}(w)$ in the previous notations when we specialize to $w \in \mathbb{C}^s \setminus \mathcal{D}$.

## 4.1 Pre-computations

This approach to the computation of the polynomials in the family $\mathcal{F}$ takes some pre-requisites that we mention now.

* **Gröbner basis**: we denote by $\mathcal{G}$ a reduced Gröbner basis of $\mathcal{I} \subseteq \mathbb{C}[W, X]$ for the block ordering $<_{W,X}$. We recall that $\mathcal{G}$ when seen as a subset of $\mathbb{C}(W)[X]$ can also be interpreted as a Gröbner basis of $\mathcal{I}_W$ for the ordering $<_X$. In what follows, we consider that $\mathcal{G}$ has been reduced.

* **Basis of the quotient**: a basis $\mathcal{B}_{\mathcal{A}_W} := \{[p_1]_{\mathcal{A}_W}, \dots, [p_D]_{\mathcal{A}_W}\}$ of $\mathcal{A}_W$ can be computed from $\mathcal{G}$ by keeping all the monomials not reducible by $\mathcal{G}$.

* **Multiplication matrices**: we also need the multiplication matrices by each variables $M_{X_1}^{\mathcal{A}W}, \dots, M_{X_n}^{\mathcal{A}W}$ in the quotient $\mathcal{A}_W$. This can be done by following FGLM's approach as in [10, Proposition 2.1].

* **Multiplicative tensor**: to avoid repeating the same computations over and over, one can compute the multiplicative tensor

$$\mathrm{MT}(\mathcal{A}_W) := \{[\overrightarrow{p_i p_j}]_{\mathcal{A}_W}, 1 \le i, j \le D\}$$

where $\overrightarrow{\cdot}_{\mathcal{A}_W}$ are the coordinates with regard to the basis $\mathcal{B}_{\mathcal{A}_W}$.

## 4.2 Computation of $\mathcal{F}$

The formulas that we present in this subsection are directly adapted from Rouilier's work in [26, §4].

**Computation of $h_0$ and $h_1$** We recall that $h_0 = \chi_t^{\mathcal{A}W}$. That being said, Newton's formulas translate really nicely in terms of traces as shown in the following lemma.
**Lemma 6.** Let us write $\chi_t^{Aw} = \sum_{i=0}^{D} b_i U_0^{D-i}$ with $b_0 = 1$. Then the coefficients of $\chi_t^{Aw}$ satisfy the following equations:

$$ (D-k)b_k = \sum_{i=0}^{k} b_{k-i} \mathrm{Trace}^{Aw}(t^i), \quad 0 \le k \le D. \qquad (13) $$

The equations given by (13) form a triangular linear system, which is convenient to solve. In addition to that, the system only depends on the traces $\mathrm{Trace}^{Aw}(t^i)$.

Once $\chi_t^{Aw} = h_0$ is obtained, we directly get $h_1$ by taking its derivative.

**Computation of $h_{X_1}, \dots, h_{X_n}$** We can express the polynomials $h_{X_1}, \dots, h_{X_n}$ using computable closed formulas depending only on $t$ and $h_0$. They are similar to [26, Theorem 3.1] formulas when we decide to keep the fractions of the GRUR unreduced (see Lemma 2).

**Lemma 7.** Sticking with the notation $h_0 = \chi_t^{Aw} = \sum_{i=0}^{D} b_i T^{D-i}$, we get that for each $j \in [1, n]$,

$$ h_{X_j}(U_0; W) = \sum_{i=0}^{D-1} \mathrm{Trace}^{Aw}(X_j t^i) H_{D-i-1}(U_0; W) \qquad (14) $$

where $H_i(U_0; W) := \sum_{j=0}^{i} b_j U_0^{i-j}$ is the $i$-th Hörner polynomial of $h_0$.

*Proof.* Let us recall that $\chi_t^{Aw}(U_0) = \prod_{x \in V(\mathcal{I}_W)} (U_0 - t(x))^{\mu(x)}$. We can then rewrite $h_{X_i}$ as

$$ \begin{aligned} h_{X_i}(U_0; W) &= \sum_{x \in V(\mathcal{I}_W)} \mu(x) x_i (U_0 - t(x))^{\mu(x)-1} \prod_{\substack{y \in V(\mathcal{I}_W) \\ y \neq x}} (U_0 - t(y))^{\mu(y)} \\ &= \sum_{x \in V(\mathcal{I}_W)} \frac{\mu(x) x_i \prod_{y \in V(\mathcal{I}_W)} (U_0 - t(y))^{\mu(y)}}{U_0 - t(x)} \\ &= \chi_t^{Aw}(U_0) \sum_{x \in V(\mathcal{I}_W)} \frac{\mu(x) x_i}{U_0 - t(x)} \\ &= \chi_t^{Aw}(U_0) \sum_{x \in V(\mathcal{I}_W)} \sum_{i=0}^{+\infty} \frac{\mu(x) x_i t^i(x)}{U_0^{i+1}} = \chi_t^{Aw}(U_0) \sum_{i=0}^{+\infty} \frac{\mathrm{Trace}^{Aw}(X_i t^i)}{U_0^{i+1}}. \end{aligned} $$

The last equality is obtained by permuting the summation symbols and using the expression of $\mathrm{Trace}(X_i t^i)$ given by Stickelberger's theorem. We can then use the expanded expression of $\chi_t^{Aw}$ to get that

$$ h_{X_i}(U_0; W) = \sum_{i=0}^{+\infty} \sum_{j=0}^{D} b_j \mathrm{Trace}^{Aw}(X_i t^i) U_0^{D-j-i-1}. \qquad (15) $$
The left part of (15) is a polynomial so there must be bounds on the values of $i$ and $j$ in the above sums. More precisely, $D - i - j - 1$ must be non-negative. That means $i$ must be less or equal than $D - 1$, and for each value of $i$, $j$ must be less or equal than $D - i - 1$. Then (15) becomes

$$h_{X_i}(U_0; W) = \sum_{i=0}^{D-1} \mathrm{Trace}^{A_W}(X_i t^i) \sum_{j=0}^{D-i-1} b_j U_0^{D-j-i-1} \\ = \sum_{i=0}^{D-1} \mathrm{Trace}^{A_W}(X_i t^i) H_{D-i-1}(U_0; W)$$

which is the announced formula. □

## 4.3 Specialization of the formulas

We now justify the good specialization of the formulas given in Lemma 7. The main dependency comes from traces so we need conditions for them to specialize well.

**Specialization of the Gröbner basis** Let us consider $w \in \mathbb{C}^s$ and $\mathcal{G}(w) := \{\phi_w(g), g \in \mathcal{G}\}$. We recall that $W_G = \cup_{g \in \mathcal{G}} V(LC_{<X}(g))$. The following lemma presents a specialization property of the parametric Gröbner basis. In [24, Theorem 2.6], a similar result is presented for modular Gröbner bases.

**Lemma 8.** For all $w \in \mathbb{C}^s \setminus W_G$, the family $\mathcal{G}(w)$ is a Gröbner basis of the specialized ideal $\mathcal{I}(w)$ for the ordering grevlex($X$).

*Proof.* All the reduction sequences of the $S$-polynomials of elements of $\mathcal{G}$ commute with the specialization morphism $\phi_w$ because the only denominators that appear are products of leading terms for $<X$ of elements of $\mathcal{G}$ and by hypothesis they do not vanish.

In addition to that, every $S$-polynomial reduces to zero because $\mathcal{G}$ is a gröbner basis. This remains true for the $S$ polynomials of elements of $\mathcal{G}(w)$ which are the specialization of $S$-polynomials of elements of $\mathcal{G}$. The conclusion is given by Buchberger's criterion. □

This result has an important consequence on the dimension of the quotients $\mathcal{A}(w)$.

**Corollary 3.** For all $w \in \mathbb{C}^s \setminus (D \cup W_G)$, the quotients $\mathcal{A}_W$ and $\mathcal{A}(w)$ have the same dimension $D$ as vector spaces.

Moreover, if $\mathcal{B}_{\mathcal{A}_W} = \{[p_1]_{\mathcal{A}_W}, \dots, [p_D]_{\mathcal{A}_W}\}$ is a $\mathbb{C}(W)$-basis of $\mathcal{A}_W$ then $\mathcal{B}(w) := \{[p_1]_{\mathcal{A}(w)}, \dots, [p_D]_{\mathcal{A}(w)}\}$ is a $\mathbb{C}$-basis of $\mathcal{A}(w)$.

*Proof.* This comes from the fact that with our hypothesis, the elements of $\mathcal{G}$ and $\mathcal{G}(w)$ have the same leading monomials, which means that the non reducible monomials are the same for both Gröbner bases. □
**Specialization of the normal forms** Denote by NF<sub>G</sub>(f) the normal form of an element f of C(W)[X] with regard to G and by NF<sub>G(w)</sub>(g) the normal form of an element g of C[X] with regard to G(w). The key point for the specialization properties is the following proposition.

**Proposition 4.** Let $w \in \mathbb{C}^s \setminus (\mathcal{D} \cup \mathcal{W}_G)$ and $v \in \mathbb{C}(W)[X]$ with no denominator vanishing at $w$. Then we have

$$NF_{G(w)}(\phi_w(v)) = \phi_w(NF_G(v)).$$

*Proof.* We start by saying that $v$ can be uniquely written as

$$v = \sum_{g \in \mathcal{G}} v_g \cdot g + \mathrm{NF}_{\mathcal{G}}(v) \qquad (16)$$

where each $v_g$ is an element of C(W)[X]. They are obtained by successive reductions using G so the only new denominators potentially appearing are products of leading terms of G. In other words, there is no denominator vanishing at w in (16) which means that we can specialize it at w yielding

$$\phi_w(v) = \sum_{g \in \mathcal{G}} \phi_w(v_g) \cdot \phi_w(g) + \phi_w(\mathrm{NF}_{\mathcal{G}}(v)). \qquad (17)$$

By hypothesis we know that each $g \in G$ satisfies the relation $LM_{<X}(g) = LM_{<X}(\phi_w(g))$. In addition to that, each monomial in X appearing in NF<sub>G</sub>(v) (and consequently, in $\phi_w(\mathrm{NF}_G(v))$) is not divisible by any leading monomial of elements of G (and consequently by any leading monomial of elements of G(w)).

We know by lemma 8 that G(w) is a Gröbner basis of I(w) so the normal form of $\phi_w(v)$ with regard to G(w) is uniquely defined, and we can identify it to $\phi_w(\mathrm{NF}_G(v))$ thanks to (17). □

A direct consequence of this is the specialization of the coordinates when going from $\mathcal{A}_W$ to $\mathcal{A}(w)$.

**Corollary 4.** Let $w \in \mathbb{C}^s \setminus (\mathcal{D} \cup \mathcal{W}_G)$ and $v \in \mathbb{C}(W)[X]$ with no denominator vanishing at $w$. Denote by $\overrightarrow{[\cdot]_{\mathcal{A}_W}}$ and $\overrightarrow{[\cdot]_{\mathcal{A}(w)}}$ the respective coordinates in $\mathcal{A}_W$ and $\mathcal{A}(w)$, respectively with regard to the bases $\mathcal{B}_{\mathcal{A}_W}$ and $\mathcal{B}_{\mathcal{A}(w)}$. Then we have

$$\overrightarrow{[\phi_w(v)]_{\mathcal{A}(w)}} = \phi_w(\overrightarrow{[v]_{\mathcal{A}_W}})$$

where $\phi_w$ is naturally applied to every coordinate.

*Proof.* The starting point is the fact that any element of C(W)[X] or C[X] is represented in $\mathcal{A}_W$ or $\mathcal{A}(w)$ by its normal form. In particular, thanks to Corollary 4 we get that

$$[\phi_w(v)]_{\mathcal{A}(w)} = [\mathrm{NF}_{\mathcal{G}(w)}(\phi_w(v))]_{\mathcal{A}(w)} = [\phi_w(\mathrm{NF}_{\mathcal{G}(w)}(v))]_{\mathcal{A}(w)}.$$
Next, write $NF_G(v) = \sum_{i=1}^n c_i p_i$ where each $c_i$ is an element of $\mathbb{C}(W)$ with no vanishing denominator. That translates to $[NF_G(v)]_{\mathcal{A}_W} = (c_1, \dots, c_n)$. We can then apply $\phi_w$ to get that

$$ \phi_w(\mathrm{NF}_G(v)) = \sum_{i=1}^{n} \phi_w(c_i)p_i. \qquad (18) $$

We now recall (Corollary 3) that $\mathcal{A}_W$ and $\mathcal{A}(w)$ share the same monomials in their respective bases so we can interpret 18 as

$$ [\overrightarrow{\mathrm{NF}_G(v)}]_{\mathcal{A}_W} = (\phi_w(c_1), \dots, \phi_w(c_n)) = \phi_w((c_1, \dots, c_n)). \qquad \square $$

**Specialization of the multiplication matrices** We can derive the specialization of multiplication matrices.

**Lemma 9.** Let $w \in \mathbb{C}^s \setminus (D \cup W_G)$. Then for any $v \in \mathbb{C}(W)[X]$ with no denominator vanishing at $w$ we have

$$ \phi_w(M_v^{\mathcal{A}_w}) = M_v^{\mathcal{A}(w)} $$

where $\phi_w$ is applied entry-wise.

*Proof.* For each $i \in [1, D]$, the $i$-th column of $M_v^{\mathcal{A}_w}$ is given by the coordinates with regard to $\mathcal{B}_{\mathcal{A}_W}$ of $[vp_i]_{\mathcal{A}_W}$. We can then use Corollary 4 to get that $\phi_w(\overrightarrow{[vp_i]_{\mathcal{A}_W}}) = \overrightarrow{[vp_i]_{\mathcal{A}(w)}}$ which is the $i$-th column of $M_v^{\mathcal{A}(w)}$. $\square$

A direct consequence of that is the specialization of traces.

**Corollary 5.** Let $w \in \mathbb{C}^s \setminus (D \cup W_G)$. Then for any $v \in \mathbb{C}(W)[X]$ with no denominator vanishing at $w$ we have

$$ \phi_w(\mathrm{Trace}^{\mathcal{A}_w}(v)) = \mathrm{Trace}^{\mathcal{A}(w)}(\phi_w(v)). $$

**Specialization of $h_0$ and $h_1$** The following lemma shows that the two first polynomials of $\mathcal{F}$ specialize well using the computations with traces.

**Lemma 10.** Let $w \in \mathbb{C}^s \setminus (D \cup W_G)$. Then we have

$$ \phi_w(\chi_t^{\mathcal{A}_w}) = \chi_t^{\mathcal{A}(w)} $$

and in particular the Hörner polynomials of $\chi_t^{\mathcal{A}(w)}$ are obtained by applying $\phi_w$ to the ones of $\chi_t^{\mathcal{A}_w}$.

Moreover, we have

$$ \phi_w \left( \frac{d\chi_w^{\mathcal{A}_w}}{dT} \right) = \frac{d\chi_t^{\mathcal{A}(w)}}{dT}. $$
*Proof.* The first point comes from applying both Lemma 9 and the fact that specialization commutes with the determinant to get

$$ \phi_w(\chi_t^{Aw}) = \phi_w(\det(U_0 I_D - M_t^{Aw})) \\ = \det(T I_D - \phi_w(M_t^{Aw})) = \det(U_0 I_D - M_t^{A(w)}) = \chi_t^{A(w)}. $$

The second part comes from the fact that specialization commutes with derivation. □

### Specialization of $h_{X_1}, \dots, h_{X_n}$

**Lemma 11.** Let $w \in \mathbb{C}^s \setminus (D \cup W_G)$. Then for each $i \in [1, n]$ we have

$$ \phi_w(h_{X_i})(U_0; W) = \sum_{i=0}^{D-1} \mathrm{Trace}^{A(w)}(X_i t^i) \phi_w(H_{D-i-1})(U_0; W) $$

and $\phi_w(H_{D-i-1})$ is the $(D-i-1)$-th Hörner polynomial of $\chi_t^{A(w)}$.

*Proof.* This is a direct consequence of Corollary 5 and Lemma 10.

### Specialization of $\mathcal{F}$ We can summarize the previous result into the following theorem.

**Theorem 3.** Suppose that $t \in \mathbb{C}[X]$ is a linear form and that the family $\mathcal{F} = \{h_0, h_1, h_{X_1}, \dots, h_{X_n}\}$ was computed using the formulas given in Lemma 6 and $\mathfrak{I}$. Then for all $w \in \mathbb{C}^s \setminus (D \cup W_G)$, the family $\phi_w(\mathcal{F})$ is a RUR-candidate of $V(\mathcal{I}(w))$.

Moreover, if we suppose that $t$ separates the specialized variety outside of the closed Zariski subset $S$ of measure 0, then for all $w \in \mathbb{C}^s \setminus (D \cup W_G \cup S)$, $\phi_w(\mathcal{F})$ is a RUR of $V(\mathcal{I}(w))$.

## 4.4 Certifying whether $t$ is generically separating or not

We present now a criterion to effectively check whether a given linear form $t$ is generically separating or not. The main issue is that we cannot directly compute the polynomial $h(U_0, \dots, U_n)$. However what we can compute are specific instances $h(U_0, a_1, \dots, a_n)$ for values $a_1, \dots, a_n \in \mathbb{C}$. This is more than enough as shown by the following lemma.

**Lemma 12.** Let $w \in \mathbb{C}^s \setminus (D \cup W_G)$ such that $\mathrm{Disc}_{U_0}(\overline{\chi_t^{Aw}})(w) \neq 0$. Then $t$ is generically separating if and only if $t$ separates the specialized variety $V(\mathcal{I}(w))$.

*Proof.* If $t$ separates $V(\mathcal{I}_W)$ then we can write $\overline{\chi_t^{Aw}} = \prod_{x \in V(\mathcal{I}_W)} (T - t(x))$. It is quite classical that the discriminant is then given by $\mathrm{Disc}_T(\overline{\chi_t^{Aw}}) = \prod_{y \neq x} (t(x)-
$t(y))^2$, and the set of parameters for which $t$ does not separate $V(\mathcal{I}(w))$ is thus given by $V(\text{Disc}_T(\chi_t^{\mathcal{A}_w}))$. By hypothesis, $w$ is indeed a value outside of this variety.

Conversely, suppose that the form $t$ separates $V(\mathcal{I}(w))$. Using the notations of §1.2, that means that the discriminant $\text{Disc}_{U_0}(\bar{h})$ does not vanish at $(w, a)$ where $a = (a_1, \dots, a_n)$ are the coefficients of $t$. In particular, $\text{Disc}_{U_0}(\bar{h}(U_0, a_1, \dots, a_n)) \in \mathbb{C}(W)$ is not identically zero. Moreover, $\bar{h}(U_0, a_1, \dots, a_n)$ is monic in $U_0$, allowing us to write

$$ \begin{aligned} \text{Disc}_{U_0}(\bar{h}(U_0, \dots, U_n))(a_1, \dots, a_n) &= \text{Disc}_{U_0}(\bar{h}(U_0, a_1, \dots, a_n)) \\ &= \text{Disc}_{U_0}\left(\prod_{x \in V(\mathcal{I}_W)} (U_0 - t(x))\right) \neq 0. \end{aligned} $$

This exactly means that $t$ is injective on $V(\mathcal{I}_W)$, and thus that $t$ is generically separating. $\square$

In other words, we can check whether $t$ is generically separating checking whether it separates one specific specialized variety. This can done using for instance the new algorithm proposed in [8].

## 4.5 About the different genericity levels

Considering the different algebraic sets to avoid introduced in the previous sections, we find it relevant to make a summarize of their meaning. In Corollary 1 we showed that the GRUR can be specialized outside $\mathcal{D} \cup \mathcal{L} \cup W_\infty \cup S$.

- Outside $\mathcal{D} \cup W_\infty \cup \mathcal{L}$, the specialized systems have a constant number of roots counted with multiplicities. Their number is $D$ which is the degree of $h_0$ or equivalently the dimension of the quotient $\mathbb{C}(W)[X]/\mathcal{I}_W$ as a $\mathbb{C}(W)$-vector space.

- Outside $\mathcal{D} \cup W_\infty \cup S \cup \mathcal{L}$, the specialized systems have a constant number of distinct roots. Their number is $d$ which is the degree of $\bar{h}_0$ when $t$ is generically separating.

In Theorem 3 we showed that if we compute $\mathcal{F}$ using linear algebra in the quotient $\mathbb{C}(W)[X]/\mathcal{I}_W$, specialization holds for parameters outside $W_\mathcal{G}$. This is the condition for the computations in the quotient $\mathcal{A}_W$ to specialize but they are just raised by the algorithmic way of computing $\mathcal{F}$.

## 4.6 Algorithm

We propose here a first Las-Vegas algorithm to compute $\mathcal{F}$. The sub-algorithms can be found in the Appendix. We do all the computations with a fixed linear form chosen in the set $\mathcal{T} := \{X_1+kX_2+\dots+k^{n-1}X_n, k \in [1, D(D-1)/2]\}$ which contains at least one linear form that separates $V(\mathcal{I}_W)$ (see [26, Lemma 2.1]). The
so-called traces vector VTr 1 refers to the vector $(\text{Trace}^{A_W}(p_1), \dots, \text{Trace}^{A_W}(p_D))^T$
which turns out to simplify some computations.

<caption>**Algorithm 1 GRUR-LA**</caption>

**Require:** $\mathcal{G}$ a reduced Gröbner basis of $\mathcal{I}_W$ w.r.t $<X$; a basis $\mathcal{B}_{A_W}$ of $A_W$; the multiplication matrices $M_{X_1}, \dots, M_{X_n}$ by $X_1, \dots, X_n$ in $A_W$; $\text{MT}(A_W)$ the multiplicative tensor of $A_W$.

**Ensure:** $\mathcal{F} = \{h_0, h_1, h_{X_1}, \dots, h_{X_n}\}$ a generic RUR of $V(\mathcal{I}_W)$.

Step 0: Compute VTr 1 the traces vector

Step 1: Choose a not already chosen linear form $t$ in $\mathcal{T}$

**while** $t$ is not generically separating **do**

$h_0 \leftarrow \text{CharacteristicPolynomial}(\text{MT}(A_W), M_t, \text{VTr } 1)$

Test whether $t$ is separating or not using DRR

**if** $t$ is separating **then**

**return** $\mathcal{F} = \{\chi_t, \chi'_t, \text{GRURPolynomials}(h_0, M_{X_1}, \dots, M_{X_n}, \text{VTr } 1)\}$

**else**

Go back to Step 1.

**end if**

**end while**

# 5 Second algorithm : evaluation/interpolation scheme

## 5.1 Presentation of the algorithm

We propose here a second algorithm for computing $\mathcal{F}$. The reason is that Algorithm 1 requires the computation of a Gröbner basis of the ideal generated by $f_1, \dots, f_n$. This Gröbner basis depends on parameters in a rather uncontrollable way and there is a high chance that the degree in the parameters explodes. In addition to that, computing the characteristic polynomial of $t$ requires the computation of $\text{Trace}^{A_W}(t^i)$ for $i \in [1, D]$ whose memory size might explode even though we know that the final result has a controlled size (see the bounds of Corollary 2). For these reasons, we propose a second approach using an evaluation/interpolation scheme.

The proposed algorithm is presented below. Each step will be precisely studied through this section.
<caption>**Algorithm 2 GRUR-EI**</caption>

**Require:** Polynomials $f_1, \dots, f_n \in \mathbb{Q}[W_1, \dots, W_s, X_1, \dots, X_n] = \mathbb{Q}[W, X]$ that form a generically zero-dimensional system with degree in $X$ bounded by $d_X$ and degree in $W$ bounded by $d_W$.

**Ensure:** $\mathcal{F} = \{h_0, h_1, h_{X_1}, \dots, h_{X_n}\} \subseteq \mathbb{Q}(W)[T]$ a generic RUR of $V(\mathcal{I}_W)$.

Step 0: Compute a grid $\mathcal{A} \subseteq \mathbb{Q}^s$ of at least $((n+1)d_X^m d_W + 1)^s$ of points $w \notin (\mathcal{D} \cup \mathcal{L} \cup \mathcal{S})$.

Step 1: Choose a not already chosen linear form $t \in \mathcal{T}$.

Step 2: For each $w \in \mathcal{A}$ use the algorithm *BlackBoxRUR* to compute specialized RURs of the system and eventually check if $t$ is generically separating.

if $t$ is not generically separating **then**
Go back to Step 1.

**end if**

Step 3: Using the computed RURs interpolate $h_0, h_1, h_{X_1}, \dots, h_{X_n}$.

**return** $\mathcal{F} = \{h_0, h_1, h_{X_1}, \dots, h_{X_n}\}$

*Remark 5.* In practice, it is even better to first try with $t$ being one of the variables. If none is working, then we start taking elements from $\mathcal{T}$. Moreover, experiments tend to show that we only need a few tries to find a generically separating form.

## 5.2 Complexity analysis of Algorithm GRUR-EI

**Complexity of Step 0** Thanks to Corollary 2, we know that the polynomials of the GRUR have degree in $W$ bounded by $\kappa := (n+1)d_X^m d_W$. Therefore, we need at least $\binom{\kappa+s}{s} \le (\kappa+1)^s$ interpolation points. The idea is to find an estimate on the degrees of the polynomials defining $\mathcal{D}$, $\mathcal{L}$ and $\mathcal{S}$ and then construct a grid in $\mathbb{Q}^s$ that contains enough good interpolation points.

**Proposition 5.** Let $q := \kappa' + nd_X^{n-1}d_X + nd_W$. The grid $\mathcal{A} = A_{k_0}^s$ where $k_0 = \lceil q + (\kappa + 1)^s/q^{s-1} \rceil$ is formed of $O(n^s d_X^{2ns} d_W^s)$ points in $\mathbb{Q}$ and contains at least $(\kappa + 1)^s$ values $w \in \mathbb{Q}^s \setminus (\mathcal{D} \cup \mathcal{L} \cup \mathcal{S})$.

*Proof.* For $\mathcal{D}$, we recall that $\mathcal{D} \subseteq W_\infty = V(C)$ where $C = \text{Res}(\tilde{F}_1, \dots, \tilde{F}_n)$ and $\tilde{F}_i = F_i(0, X_1, \dots, X_n)$ (see Remark 4). So that whenever $C(w) \ne 0$, the specialized system at $w$ has a finite number of solutions. We also recall that $\text{deg}_W(C) \le nd_X^{n-1}d_W$.

For $\mathcal{L}$, denote by $L(W) := \prod_{i=1}^n \text{LT}_{<X}(f_i)(W)$. Then $\mathcal{L} = V(L)$ and $L$ has degree in $W$ bounded by $nd_W$.

For $\mathcal{S}$, we write $h_0(U_0; W) = \Delta(U_0; W)/p(W)$ with $\Delta \in \mathbb{Z}[U_0, W]$ and $p \in \mathbb{Z}[W]$. Recall that whenever $t$ is generically separating, $\mathcal{S} = V(\text{Disc}_{U_0}(\bar{\Delta}))$. Since $\text{deg}_W(\bar{\Delta}) \le \kappa = (n+1)d_X^m d_W$, [27, Proposition 8.45] explains that this discriminant has degree in $W$ bounded by $\kappa' := 2(n+1)d_X^{2n} d_W$.

Now to find enough good interpolation points, we build a grid $A_k \times \dots \times A_k = A_k^s$ where $A_k = [1, k]$ and we look for a value $k_0$ such that $A_{k_0}^s$ contains enough parameters values for which neither $C(W)$, $L(W)$ nor $\text{Disc}_{U_0}(\bar{\Delta})(W)$ vanish.
The main ingredient is Schwartz-Zippel theorem ([32, Proposition 97, §12]). It states that a non-zero polynomial $F \in \mathbb{Q}[X_1, \dots, X_n]$ of total degree $d$ vanishes at most $d|S|^{n-1}$ times on the grid $S^n$.

Here, we take $F$ to be $\text{Disc}_T(\bar{\Delta}) \cdot C \cdot L \subseteq \mathbb{Z}[W]$ which has degree in $W$ bounded by $\kappa' + nd_X^{n-1}d_W + nd_W$. Denote by $q := \kappa' + nd_X^{n-1}d_X + nd_W$. We want to find $k_0 \ge 0$ such that $|A_{k_0}|^s - q|A_{k_0}|^{s-1} \ge (\kappa+1)^s$. Consider $g: x \mapsto x^s - qx^{s-1} - (\kappa+1)^s = x^{s-1}(x-q) - (\kappa+1)^s$. Clearly, $g(x) \le 0$ for $x \in [0, q]$ so $k_0 \ge q$. In addition to that, $g$ is increasing on $[q, +\infty[$. Denote by $x_0$ the solution to the equation $g(x) = 0$. Then for all $x \ge x_0$ we have $g(x) \ge 0$. Moreover, $x_0 > q$ so that $x_0^{s-1} > q^{s-1}$ and then $x_0^{s-1}(x_0 - q) = (\kappa + 1)^s > q^{s-1}(x_0 - q)$. In other words, we have shown that $x_0 < q + (\kappa + 1)^s/q^{s-1}$ and we thus choose $k_0 := \lceil q + (\kappa + 1)^s/q^{s-1} \rceil$ where $\lceil \cdot \rceil$ is the ceiling function. For complexity purposes, observe that $k_0 = O(q) = O(nd_X^{2n}d_W)$. $\square$

**Complexity of Step 2** First, we describe the algorithm *BlackBoxRUR* and give an estimate of its complexity.

**Algorithm 3** *BlackBoxRUR*

**Require:** Polynomials $g_1, \dots, g_n \in \mathbb{Q}[X_1, \dots, X_n]$ that form a zero-dimensional system, and a linear form $t \in \mathbb{Q}[X_1, \dots, X_n]$.

**Ensure:** $\mathcal{F} = \{h_0, h_1, h_{X_1}, \dots, h_{X_n}\} \subseteq \mathbb{Q}[T]$ a RUR of $V(g_1, \dots, g_n)$.

Step 1: Compute a Gröbner basis $\mathcal{G}$ of $\langle g_1, \dots, g_n \rangle$ for the ordering $\mathring{X}$.

Step 2: Compute the multiplication matrices $M_{X_1}, \dots, M_{X_n}$ of the multiplication by each variables in the quotient $\mathbb{Q}[X]/\langle g_1, \dots, g_n \rangle$.

Step 3: If $t$ separates $V(g_1, \dots, g_n)$, compute $\mathcal{F}$ a RUR of $V(g_1, \dots, g_n)$ with regard to $t$.

return $\mathcal{F}$ or "False"

**Proposition 6.** *A single call of *BlackBoxRUR* for polynomials of degrees bounded by $d$ requires at most $O(nd^{3n})$ operations in $\mathbb{Q}$.*

*Proof.* We study separately every step of the algorithm.

• Step 1: The key ingredient here is the following lemma that we directly prove. We recall that a family $g_1, \dots, g_n$ is a *regular sequence* if for each $i \in [2, n]$, $g_i$ is not a zero-divisor in the quotient $\mathbb{Q}[X]/\langle g_1, \dots, g_{i-1} \rangle$.

**Lemma 13.** Let $g_1, \dots, g_n$ be a sequence of elements of $\mathbb{Q}[X_1, \dots, X_n]$ such that $V(\langle g_1, \dots, g_n \rangle)$ has dimension zero. Then the sequence $g_1, \dots, g_n$ is regular.

*Proof.* To prove this, we use height theory for ideals (see for instance [21]). Since $\mathbb{Q}[X]$ is a Cohen-Macaulay ring, proving that the sequence $g_1, \dots, g_n$ is regular is equivalent to showing that for each $i \in [1, n]$ we have $\text{ht}(\langle f_1, \dots, f_i \rangle) = i$ where $\text{ht}$ denotes the height. In what follows, we denote by $\mathcal{J}_i := \langle g_1, \dots, g_i \rangle$, $1 \le i \le n$.
Let $\mathfrak{p} \supseteq \mathcal{J}_n$ be a prime ideal. Then we have

$$ \mathrm{ht}(\mathfrak{p}) + \dim_{\mathrm{Krull}} \left( \frac{\mathbb{Q}[X]}{\mathfrak{p}} \right) = \dim_{\mathrm{Krull}}(\mathbb{Q}[X]) = n \quad (19) $$

where $\dim_{\mathrm{Krull}}$ denotes the Krull dimension (see [13, Theorem 1.8A]). Since $\mathfrak{p} \supseteq \mathcal{J}_n$ we have that $V(\mathfrak{p}) \subseteq V(\mathcal{J}_n)$. Then $V(\mathfrak{p})$ is also finite, and thus $\mathbb{Q}[X]/\mathfrak{p}$ has Krull dimension zero which means that Equation (19) yields $\mathrm{ht}(\mathfrak{p}) = n$ and thus that $\mathrm{ht}(\mathcal{J}_n) = n$.

In addition to that, Krull Principal Ideal Theorem (see [21, Theorem 18 §12]) states that for each $i \in [1, n]$, $\mathrm{ht}(\mathcal{J}_i) \le i$. Adding a generator to an ideal can increase its height by at most one, so having $\mathrm{ht}(\mathcal{J}_n) = n$ forces each of these inequalities to be an equality. $\square$

During a call of *BlackBoxRUR*, the sequence $g_1, \dots, g_n$ satisfies the assumptions of lemma 13 and is thus a regular sequence. The authors in [2, Proposition 6] show that the complexity of computing a Gröbner basis of $\langle g_1, \dots, g_n \rangle$ lies in $O((n+d_{reg})^\omega)$, with $\omega$ the exponent of linear algebra. A usual bound on $d_{reg}$ is the Macaulay bound $d_{reg} \le nd - n + 1$. In other words, the Gröbner basis of $\langle g_1, \dots, g_n \rangle$ for the ordering $<_X$ can be computed within $O((n+d_{reg})^\omega) = O(nd^{wn})$ operations in $\mathbb{Q}$.

*Step 2:* With the knowledge of a Gröbner basis of $\langle g_1, \dots, g_n \rangle$, it is possible to compute the multiplication matrices $M_{X_1}, \dots, M_{X_n}$ with $O(nd^{3n})$ operations in $\mathbb{Q}$ (see [10, Proposition 3.1]).

*Step 3:* For this step we refer to the algorithm proposed in [8, Algorithm 6]. Given the multiplication matrices $M_{X_1}, \dots, M_{X_n}$ of the multiplication by the variables in $\mathbb{Q}[X]/\langle g_1, \dots, g_n \rangle$ and the linear form $t$, this algorithm will either return "False" if $t$ does not separate $V(\langle g_1, \dots, g_n \rangle)$ or will compute a (reduced) RUR of the radical with regard to $t$ otherwise with $\tilde{O}(nd^{3n})$ operations in $\mathbb{Q}$. The passage from this reduced RUR to a RUR of $\langle g_1, \dots, g_n \rangle$ can be done by replacing the first polynomial of the reduced RUR of $V(\sqrt{\langle g_1, \dots, g_n \rangle})$ by the characteristic polynomial of $t$ (which can be computed with $\tilde{O}(d^{3n})$ operations in $\mathbb{Q}$). The overall complexity of this step then lies in $\tilde{O}(nd^{3n})$.

Thus, the global complexity of algorithm *BlackBoxRUR* lies in $\tilde{O}(nd^{3n})$. $\square$

**Corollary 6.** *Step 2 in Algorithm GRUR-EI requires $\tilde{O}(n^{s+2}d_X^{2ns+3n}d_W^s(d_X^{2n} + d_W^s))$ operations in $\mathbb{Q}$.*

*Proof.* For each value of parameters $w \in \mathcal{A}$, we want to specialize the $f_i$'s to $w$. One specialization can be done using $O(nd_W^s d_X^n)$. Indeed, each $f_i$ can be written as $f_i = \sum_{|\alpha| \le d_X} c_{i,\alpha} X^\alpha$ with $c_{i,\alpha} \in \mathbb{Q}[W]$ and $\deg_W(c_{i,\alpha}) \le d_W$. We can evaluate all monomials in $W$ of degree less or equal than $d_W$ using $\binom{d_W+s}{s}$ operations in $\mathbb{Q}$ by successively computing them in degree increasing order. As each $f_i$ is made of at most $\binom{d_X+n}{n}$ monomials in $X$, the total number of operations to compute $f_1(w, X), \dots, f_n(w, X)$ lies in $O(n \binom{d_W+s}{s} \binom{d_X+n}{n}) = O(nd_W^s d_X^n)$.

We need to perform at most $\binom{\kappa+s}{s} + (\kappa' + nd_X^{n-1}d_W + nd_W)k_0^{s-1} = O(n^s d_X^{2ns} d_W^s)$ evaluations. The total cost of these evaluations thus lies in $O(n^{s+1}d_X^{2ns+n}d_W^{2s})$.
Then, for each of these specialized systems we use the algorithm *BlackBoxRUR* for $\tilde{O}(nd_X^{3n})$ additional operations in $\mathbb{Q}$. Computing all specialized RURs requires $\tilde{O}(n^{s+1}d_X^{2ns+3n}d_W^s)$ operations in $\mathbb{Q}$. The cost of evaluating all the systems and using the black-box for each value $w \in \mathcal{A}$ therefore requires at most $\tilde{O}(n^{s+1}d_X^{2ns+n}d_W^s(d_X^{2n} + d_W^s))$ operations in $\mathbb{Q}$.

Now, this part of Step 2 runs until a generically separating form is found. The set $\mathcal{T}$ from which the candidates are chosen has size bounded by $nd_X^n(d_X^n - 1) = O(nd_X^{2n})$ and is guaranteed to contain at least one generically separating form so the preceding computations are done at most $O(nd_X^{2n})$ times. The final complexity then lies in $\tilde{O}(n^{s+2}d_X^{2ns+3n}d_W^s(d_X^{2n} + d_W^s))$. $\square$

**Remark 6.** The result from Schwartz and Zippel guarantees that on the grid $\mathcal{A}$ there are at most $\kappa'k_0^{s-1}$ points on which $\text{Disc}_{U_0}(\bar{h}_0)$ can vanish. If during the computations of Step 2, *BlackBoxRUR* returns more than $\kappa'k_0^{s-1}$ times "False" then we know that $\text{Disc}_{U_0}\bar{h}_0$ is identically zero. In that case, $t$ is not generically separating and the algorithm *GRUR-EI* should go back to step 1.

**Complexity of Step 3** We denote by $I(n, d)$ a bound on the number of operations in $\mathbb{Q}$ to interpolate a polynomial in $n$ variables of total degree $d$ from its values on $\binom{d+n}{n}$ points.

**Proposition 7.** *Step 3 of algorithm GRUR-EI requires $O(nd_X^n I(\kappa, s))$ operations in $\mathbb{Q}$.*

*Proof.* We need to interpolate the $2(D+1)$ numerators and denominators of $h_0$, and the $2(n+1)D$ numerators and denominators of $h_1, h_{X_1}, \dots, h_{X_n}$. All have degree in $W$ bounded by $\kappa$. That means the interpolation part requires $O(nd_X^n I(\kappa, s))$ operation in $\mathbb{Q}$. $\square$

**Global complexity** We summarize the complexity result into the following theorem.

**Theorem 4.** *In Algorithm GRUR-EI,*

- the evaluation part requires at most $\tilde{O}(n^{s+2}d_X^{2ns+3n}d_W^s(d_X^{2n}+d_W^s))$ operations in $\mathbb{Q}$;

- the interpolation part requires at most $O(nd_X^n I(\kappa, s))$ operations in $\mathbb{Q}$.

Therefore, Algorithm GRUR-EI can be performed using $\tilde{O}(n^{s+2}d_X^{2ns+3n}d_W^s(d_X^{2n} + d_W^s) + nd_X^n I(\kappa, s))$ operations in $\mathbb{Q}$.

We can now give a more precise expression using known complexities for interpolation.

**Corollary 7.** *Algorithm GRUR-EI can be performed using at most*

$$ \tilde{O}(sn^{2s+2}d_X^{2ns+2n}d_W^{s+1} + n^{s+1}d_X^{2ns+5n}d_W^s) $$

operations in $\mathbb{Q}$.
Proof. The algorithm proposed in [15] allows to interpolate a polynomial in n variables, with total degree d and at most θ terms with $O(dn \log_2(n)\theta M(\theta) \log_2(\theta))$ arithmetic operations. Here $M(\theta)$ is the complexity bound for multiplying two univariate polynomials of degree less than θ. We can take the classical Schönhage bound with $M(\theta) = O(\theta \log_2(\theta) \log_2(\theta))$. In our case, $d \le \kappa$ and $\theta \le (\kappa+1)^s$, and with our notations, the cost of a single interpolation is $I(\kappa, s) = \tilde{O}(sn^{2s+1}d_X^{2ns+n}d_W^{2s+1})$ arithmetic operations. By substituting that in the complexity found in Theorem 4 we get that the GRUR polynomials can be computed with $\tilde{O}(sn^{2s+2}d_X^{2ns+2n}d_W^{2s+1})$ operations in $\mathbb{Q}$. $\square$

## 5.3 Real roots classification

This problem consists in finding polynomials formulas describing semi-algebraic sets $S_1, \dots, S_l \subseteq \mathbb{R}^s$ such that their union is dense in $\mathbb{R}^s$, and above each of them, the specialized systems have a constant number of real roots. In addition to that, we want to be able to compute one point in each of these connected component.

In [18], the authors tackle this problem by computing the parametric Hermite matrix, that is, the matrix $\mathcal{H} := (\text{Trace}^{A_W}(p_i p_j))_{1 \le i,j \le D}$ where we recall that $\mathcal{B} = \{[p_1]_{A_W}, \dots, [p_D]_{A_W}\}$ is a basis of $A_W$. The authors show that the looked for semi-algebraic sets can be described by the principal minors of the Hermite matrix as they encode the parameters values for which the signature of $\mathcal{H}$ changes (and thus the number of distinct real roots). Their algorithm is general and they show that it runs with at most $\tilde{O}((s+\mathcal{D})^2 3^s n^{2s+1} d^{3ns+2(n+s)+1})$ where d is the total degree of the equations and $\mathcal{D} = n(d-1)d^n$. To reach this complexity, the author make some assumptions on the Gröbner basis computed for the block ordering $<_{X,W}$ that give a great control on the potential explosion of the degrees in the parameters during the computation of $\mathcal{H}$ (see [18, Assumptions B and C]). We propose here a general approach with an estimated higher complexity that do not depend on these hypothesis.

The formulas describing the semi-algebraic sets $S_1, \dots, S_l$ can be derived from the computation of a Sturm-Habicht (or Sylvester-Habicht) sequence, or rather the leading coefficients of this sequence. We stick to the definition given in [27, Notation 4.21] and our main tool will be [12, Theorem 3] to count to number of real roots of the system. Given $\mathbb{A}$ a ring and $P, Q \in \mathbb{A}[U_0]$, denote by $\mathbf{sres}(P, Q)$ the signed subresultant sequence of $P$ and $Q$. The Sturm-Habicht sequence of $P$ is given by $\mathbf{sres}(P, P')$.

The fact that $\mathcal{F} = \{h_0, h_1, h_{X_1}, \dots, X_n\}$ forms a generic RUR of $V(\mathcal{I}_W)$ can be rephrased as the fact that for almost all $w \in \mathbb{C}^s$, the morphism of algebraic sets

$$ \Psi_w : V(\phi_w(h_0)) \to V(\mathcal{I}(w)) \\ y \mapsto \left( \frac{\phi_w(h_{X_1})(y)}{\phi_w(h_1)(y)}, \dots, \frac{\phi_w(h_{X_n})(y)}{\phi_w(h_1)(y)} \right) $$

preserves multiplicities, and also the number of real roots. In other words, the number of real roots of $V(\mathcal{I}(w))$ is exactly the number of real roots of $\phi_w(h_0) =$
$\chi_{\mathcal{I}(w)}$. We recall that $h_0$ can be computed under the form $h_0 = \Delta/P$ with $\Delta \in \mathbb{Z}[W][U_0]$ and $P \in \mathbb{Z}[W]$. The number of real roots of $h_0$ is the same as the number of real roots of $\Delta$.

Since $\phi_w(\Delta)$ is a univariate polynomial, [12, Theorem 3] guarantees that the number of its real roots is given by the number of sign changes (see [12, §1]) in the sequence $sres(\Delta), \phi_w(\Delta)'$ computed with regard to the variable $U_0$. The great advantage of using subresultants is that they have really great specialization properties. Indeed, for each $w \in \mathbb{C}^s$ such that the leading coefficient of $\Delta$ in $U_0$ does not vanish at $w$, the Sturm-Habicht sequence specializes in the sense that $\phi_w(\mathbf{sres}(\Delta, \Delta')) = \mathbf{sres}(\phi_w(\Delta), \phi_w(\Delta))'$.

The Sturm-Habicht sequence $sres(\Delta, \Delta')$ is made of polynomials of $\mathbb{Z}[W]$ that describe the semi-algebraic sets $S_1, \dots, S_l \subseteq \mathbb{R}^s$ on which the number of real roots of $V(\mathcal{I}(w))$ is constant. The excluded parameters values are those for which the GRUR does not specialize, that is those contained in $\mathcal{D} \cup \mathcal{L} \cup W_\infty \cup S$ (see Corollary 1) and those for which the leading coefficient of $\Delta$ vanishes. The union of these algebraic sets is of measure zero so the union of the $S_i$'s is indeed dense in $\mathbb{R}^s$. This description leads to the following algorithm whose complexity is studied in Proposition 8.

**Algorithm 4** RealRootClassification

**Require:** Polynomials $f_1, \dots, f_n \in \mathbb{Z}[W, X]$ generating a generically zero-dimensional ideal $\mathcal{I}$.

**Ensure:** Polynomials $P_1, \dots, P_D \in \mathbb{Z}[W]$ that are the formulas of the semi-algebraic sets solving the real roots classification problem along at least one point in each of them.

Step 1: Compute $\mathcal{F} = \{h_0, h_1, h_{X_1}, \dots, h_{X_n}\}$ a GRUR of $V(\mathcal{I}_W)$ with $h_0 = \Delta/P$.

Step 2: The subresultants sequence $\mathbf{sres}(\Delta, \Delta') = \{P_1, \dots, P_D\}$.

Step 3: Compute a set $\mathcal{P}$ of at least one point per connected component of the semi-algebraic set $\mathcal{Q} = \{P_1 \neq 0, \dots, P_D \neq 0\}$.

return $P_1, \dots, P_D$ and $\mathcal{P}$

**Proposition 8.** Given polynomials $f_1, \dots, f_n \in \mathbb{Z}[W, X]$ generating a generically zero-dimensional ideal $\mathcal{I}$, Algorithm 5.3 solves the real roots classification problem and can be performed using at most

$$ \tilde{O}(2^{6s+1}n^{3s+1}d_X^{7ns+3n}d_W^{3s+1}) $$

operations in $\mathcal{Q}$.

*Proof.* The discussion held in the previous subsection showed that we can compute the elements of a GRUR of $V(\mathcal{I}_W)$ with at most $\tilde{O}(sn^{2s+2}d_X^{2ns+2n}d_W^{2s+1})$ operations in $\mathcal{Q}$. That represents the cost of Step 1. We write $h_0 = \Delta/P$ where $\Delta \in \mathbb{Q}[W, T]$ and $P \in \mathbb{Q}[W]$.

Next, we need to compute the Sturm-Habicht sequence $\mathbf{sres}(\Delta, \Delta')$. Thanks to the bounds found in corollary 2, we know that $\Delta$ has total degree bounded
by $\kappa + d_X^n$ and height bounded by $\tilde{O}(nd_X^n\tau + nd_X^n d_W \log_2(s+1))$. The idea is to use binary segmentation to transform $\Delta$ and $\Delta'$ into polynomials in $\mathbb{Z}[Y][T]$, compute the subresultants sequence of the transformed polynomials and then recover the result in $\mathbb{Z}[W]$ using inverse binary segmentation. To do that, we need bounds on both the height and degrees of the expected result. From [27, proposition 8.45] we know that each polynomial of $\mathbf{sres}(\Delta, \Delta')$ has degree bounded by $\kappa' := 2(n+1)d_X^{2n}d_W$.

The ring homomorphism $\Theta : \mathbb{Z}[W][T] \to \mathbb{Z}[Y][T]$ such that $W_1 \mapsto Y$, $W_2 \mapsto Y^{\kappa'+1}, \dots, W_s \mapsto Y^{\kappa'^{s-1}+1}$ where $T$ is a new variable allows us to obtain $\mathbf{sres}(\Delta, \Delta')$ through the computation of $\mathbf{sres}(\Theta(\Delta), \Theta(\Delta')) = \Theta(\mathbf{sres}(\Delta, \Delta'))$ (see for example [9, §3], [16, Theorem 3.3]). Since $\Delta$ has degree in $W$ bounded by $\kappa$, we know that $\Theta(\Delta)$ has degree in $Y$ bounded by $\kappa(\kappa'^{s-1}+1)$, that is, $\deg_Y(\Delta) = O(2^{s-1}n^s d_X^{2ns-n} d_W^s)$. According to [11, Corollary 11.18], we can compute $\mathbf{sres}(\Theta(\Delta), \Theta(\Delta'))$ using $\tilde{O}(2^{s-1}n^s d_X^{2ns} d_W^s)$ operations in $\mathbb{Q}$. From that, we can decode the leading coefficients of every polynomial in $\mathbf{sres}(\Theta(\Delta), \Theta(\Delta'))$ and obtain polynomials $P_1, \dots, P_D \in \mathbb{Z}[W]$. The overall cost of Step 2 is thus $\tilde{O}(2^{s-1}n^s d_X^{2ns} d_W^s)$ operations in $\mathbb{Q}$.

Now, [12, Theorem 3] states that for each parameters value $w \in \mathbb{R}^s$, the number of real roots of $\Delta$ is given by the modified number of sign variations. This number changes if and only if some $P_i$ vanish when evaluated at $w$. The semi-algebraic $\mathcal{Q}$ defined by $P_1 \neq 0, \dots, P_D \neq 0$ is such that the number of real roots of $\Delta$ is constant on each of its connected components.

The final step is to actually compute one point per connected component of $\mathcal{Q}$. This can be done using for instance the probabilistic algorithm proposed in [18, Corollary 3]. The latter requires $\tilde{O}(2^{6s+1}n^{3s+1}d_X^{7ns+2n+s}d_W^{3s^2+1})$ operations in $\mathbb{Q}$ to compute a set of at most $O(4^s n^s d_X^{3ns} d_W^s)$ points in $\mathbb{Q}^s$ that meets at least one time each connected component of $\mathcal{Q}$.

The complexity of the overall approach is dominantly held by the very last step. $\square$

*Remark 7.* We only need $h_0$ to perform Algorithm 5.3. However, since the overall complexity is held by the last step, that would not change the complexity bound.

*Remark 8.* One could use the half-gcd algorithm as presented in [19, Algorithm 4] and reach a complexity lying in $\tilde{O}(n^s d_X^{2ns+n} d_W^s)$ for Step 2 by using the known bound on the degrees in $W$ appearing in the subresultants sequence. However, since the complexity is dominantly held by the last step, that would not change the overall complexity.

# 6 Appendix

## 6.1 Stickelberger's theorem

For simplicity, we refer to this result as Stickelberger's theorem. It can be found in [1, §2.3.1 Corollary 3.6].
**Theorem 5 (Stickelberger).** Let $K$ be a field and $\mathcal{I} \subseteq K[X_1, \dots, X_n]$ a zero-dimensional ideal. Let $m_p$ be the endomorphism of multiplication by $p$ in the quotient $K[X_1, \dots, X_n]/\mathcal{I}$. Then :

- the characteristic polynomial of $m_p$ is $\prod_{x \in V(\mathcal{I})} (T - p(x))^{\mu(x)}$;

- the determinant of $m_p$ is $\prod_{x \in V(\mathcal{I})} p(x)^{\mu(x)}$;

- the trace of $m_p$ is $\sum_{x \in V(\mathcal{I})} \mu(x)p(x)$;

where $\mu(x)$ is the multiplicity of $x$.

## 6.2 Sub-algorithms for GRUR-LA

**Algorithm 5 QuotientBasis**

**Require:** $\mathcal{G}$ a Gröbner basis of $\mathcal{I}_W$ w.r.t. `grevlex$(X)$`.

**Ensure:** $\mathcal{B}$ a basis of $\mathcal{A}_W$.

if 1 is reducible by $\mathcal{G}$ then return $\emptyset$

end if

$\mathcal{B} \leftarrow \{[1]\}$

$L \leftarrow [X_1, \dots, X_n]$; $L' \leftarrow [1]$

while $L' \neq \emptyset$ do

$L' \leftarrow \emptyset$

for $m \in L$ do

if $m$ is not reducible by $\mathcal{G}$ then

$\mathcal{B} \leftarrow \mathcal{B} \cup \{[m]\}$

$L' \leftarrow L' \cup \{m \cdot X_1, \dots, m \cdot X_n\}$

$L \leftarrow L'$

end if

end for

end while

return $\mathcal{B}$
**Algorithm 6 MultiplicationMatrices**

**Require:** $\mathcal{G}$ a Gröbner basis of $\mathcal{I}_W$ w.r.t. $<X$; $B(\mathcal{G})$ the set of monomials from a basis $B_{\mathcal{A}_W}$ of $\mathcal{A}_W$.

**Ensure:** The multiplication matrices $M_{X_1}, \dots, M_{X_n}$ by $X_1, \dots, X_n$ in $\mathcal{A}_W$. Compute $M(\mathcal{G})$ and order $B(\mathcal{G}) \cup M(\mathcal{G})$ using $<X$.

**for** $m \in B(\mathcal{G}) \cup M(\mathcal{G})$ **do**

**if** $m \in B(\mathcal{G})$ **then**

Write $m = p_i$ for some $i \in [1, D]$. Then $\overrightarrow{[m]} \leftarrow [\delta_{i,i}, 1 \le l \le D]^T$.

**end if**

**if** $m = \text{LT}_{<X}(g)$ for some $g \in \mathcal{G}$ written $g = m + \sum_{l=1}^D a_l p_l$ **then**
    $\overrightarrow{[m]} \leftarrow [-a_1, \dots, -a_D]^T$.

**else**

Write $m = X_j m'$ with $m' = X_s b$.

**for** $u \stackrel{?}{=} 1 \dots D$ **do**
    $\overrightarrow{[m]}_u \leftarrow \sum_{v=1}^D \overrightarrow{[X_s b]_v} \overrightarrow{[X_j p_v]}_u$.

**end for**

**end if**

**end for**

**for** $i = 1 \dots n$ **do**
    Build $M = (\overrightarrow{[X_i p_1]} | \dots | \overrightarrow{[X_i p_D]})$

**end for**

**return** $M_{X_1}, \dots, M_{X_n}$

**Algorithm 7 MultiplicativeTensor**

**Require:** $\mathcal{B}$ a basis of $\mathcal{A}_W$ and $M_{X_1}, \dots, M_{X_n}$.

**Ensure:** The multiplicative tensor $\text{MT}(\mathcal{A}_W)$.

$\text{MT}(\mathcal{A}_W) \leftarrow \emptyset$

$\mathcal{M} \leftarrow \{p_i p_j, 1 \le i, j \le D\}$.

Order $\mathcal{M}$ using $<X$

**for** $m \in \mathcal{M}$ of total degree 0 or 1 **do**

$\text{MT}(\mathcal{A}_W) \leftarrow \text{MT}(\mathcal{A}_W) \cup [m]$

**end for**

**for** $m \in \mathcal{M}$ of total degree greater or equal than 2 **do**

Write $m = X_j m'$ with $\deg(m') < \deg(m)$

$\overrightarrow{[m]} \leftarrow M_{X_j} \cdot \overrightarrow{[m']}$

$\text{MT}(\mathcal{A}_W) \leftarrow \text{MT}(\mathcal{A}_W) \cup [m]$

**end for**

**return** $\text{MT}(\mathcal{A}_W)$
**Algorithm 8 CharacteristicPolynomial**

**Require:** $\mathcal{M}(\mathcal{A}_W)$; $M_t$ the multiplication matrix by $t$ in $\mathcal{A}_W$; VTr 1.

**Ensure:** $\chi_t$ the characteristic polynomial of $t$.

$N_0 \leftarrow D$.

$\vec{v} \leftarrow [1, 0, \dots, 0]^T$.

**for** $i = 1, \dots, D$ **do**

$\vec{v} \leftarrow M_t \cdot \vec{v}$.

$N_i \leftarrow \text{Trace}(t^i) = \vec{v} \cdot \text{VTr}(1).$

**end for**

Solve the triangular system $\{(D-k)b_k = \sum_{j=0}^{k} b_{k-j}N_j\}_{k \in [1, D]}$ whose unknowns are the $b_k$.

**return** $\chi_t = T^D + \sum_{k=0}^{D-1} b_k U_0^{D-k}$.

**Algorithm 9 RURPolynomials**

**Require:** $\chi_t = \sum_{i=0}^{D} b_i T^{D-i}$; $M_{X_1}, \dots, M_{X_n}$ the multiplication matrices of $X_1, \dots, X_n$ in $\mathcal{A}_W$; VTr 1.

**Ensure:** $h_{X_1}, \dots, h_{X_n}$.

**for** $i = 1, \dots, D$ **do**

$H_i(T) \leftarrow \sum_{j=0}^{i} b_j T^{i-j}$.

**end for**

**for** $k = 1, \dots, n$ **do**

**for** $i = 0, \dots, D-1$ **do**

$\text{Trace}(X_k t^i) \leftarrow \overrightarrow{X_k t^i} \cdot \text{VTr}(1).$

**end for**

$h_{X_k} \leftarrow \frac{\sum_{i=0}^{D-1} \text{Trace}(X_k t^i) H_{D-1-i}(T)}{\frac{\partial \chi_t}{\partial T}}$.

**end for**

**return** $h_{X_1}, \dots, h_{X_n}$.

**Algorithm 10 SeparationCheck**

**Require:** A linear form $t = a_1X_1 + \dots + a_nX_n \in \mathbb{C}[X]$; $\chi_t$ the characteristic polynomial of $t$ in $\mathcal{A}_W$; $\mathcal{G}$ a reduced Gröbner basis of $\mathcal{I}_W$ for $\langle X \rangle$.

**Ensure:** True if $t$ is generically separating and False otherwise.

Compute $\text{Disc}(\chi_t)$

if $\text{Disc}(\chi_t) = 0$ then return (False)

**end if**

Choose $w \in \mathbb{C}^s$ such that $w \notin \bigcup_{g \in \mathcal{G}} V(\text{LC}_< X) ; V(\mathcal{I}(w))$ has dimension zero and $\text{Disc}(\chi_t)(w) \neq 0$

Use [8, Algorithm 6] with $\mathcal{G}(w)$ to know if $t$ is separating

**return** The answer given
References

1. Hans Sterk Arjeh M. Cohen, Hans Cuypers. *Some Tapas of Computer Algebra*. Springer Berlin Heidelberg, https://doi.org/10.1007/978-3-662-03891-8, 1999.

2. Magali Bardet, Jean-Charles Faugère, and Bruno Salvy. Asymptotic Behaviour of the Index of Regularity of Semi-Regular Quadratic Polynomial Systems. In *MEGA 2005 - 8th International Symposium on Effective Methods in Algebraic Geometry*, pages 1–17, Porto Conte, Alghero, Sardinia, Italy, May 2005.

3. John Canny. Generalised characteristic polynomials. *Journal of Symbolic Computation*, 9(3):241–250, 1990. Computational algebraic complexity editorial.

4. George E. Collins. Quantifier elimination for real closed fields by cylindrical algebraic decompostion. In H. Brakhage, editor, *Automata Theory and Formal Languages*, pages 134–183, Berlin, Heidelberg, 1975. Springer Berlin Heidelberg.

5. Carlos D'Andrea, Teresa Krick, and Martin Sombra. Heights of varieties in multi-projective spaces and arithmetic nullstellensatze, 2012.

6. James H. Davenport and Joos Heintz. Real quantifier elimination is doubly exponential. *Journal of Symbolic Computation*, 5(1):29–35, 1988.

7. Donal O’Shea David A. Cox, John Little. *Using Algebraic Geometry*. Graduate Texts in Mathematics. Springer New York, NY, https://doi.org/10.1007/b138611, 2005.

8. Alexander Demin, Fabrice Rouillier, and Joao Ruiz. Reading rational univariate representations on lexicographic groebner bases, 2025.

9. Dimitrios I. Diochnos, Ioannis Z. Emiris, and Elias P. Tsigaridas. On the asymptotic and practical complexity of solving bivariate systems over the reals. *Journal of Symbolic Computation*, 44(7):818–835, July 2009.

10. J.C. Faugère, P. Gianni, D. Lazard, and T. Mora. Efficient computation of zero-dimensional gröbner bases by change of ordering. *Journal of Symbolic Computation*, 16(4):329–344, 1993.

11. Joachim Von Zur Gathen and Jurgen Gerhard. *Modern Computer Algebra*. Cambridge University Press, USA, 2 edition, 2003.

12. L. Gonzalez, H. Lombardi, T. Recio, and M.-F. Roy. Sturm-habicht sequence. In *Proceedings of the ACM-SIGSAM 1989 International Symposium on Symbolic and Algebraic Computation*, ISSAC '89, pages 136–146, New York, NY, USA, 1989. Association for Computing Machinery.

13. Robin Hartshorne. *Algebraic Geometry*. Springer New York, NY, https://doi.org/10.1007/978-1-4757-3849-0, 1 edition, 1977.

14. J.P Jouanolou. Le formalisme du résultant. *Advances in Mathematics*, 90(2):117–263, 1991.

15. Erich Kaltofen and Lakshman Yagati. Improved sparse multivariate polynomial interpolation algorithms. In P. Gianni, editor, *Symbolic and Algebraic Computation*, pages 467–474, Berlin, Heidelberg, 1989. Springer Berlin Heidelberg.

16. J. Klose. Binary segmentation for multivariate polynomials. *Journal of Complexity*, 11(3):330–343, 1995.

17. Daniel Lazard and Fabrice Rouillier. Solving parametric polynomial systems. *J. Symb. Comput.*, 42(6):636–667, 2007.

18. Huu Phuoc Le and Mohab Safey El Din. Solving parametric systems of polynomial equations over the reals through hermite matrices. *Journal of Symbolic Computation*, 112:25–61, 2022.

19. Grégoire Lecerf. On the complexity of the Lickteig-Roy subresultant algorithm. *Journal of Symbolic Computation*, 92:243–268, 2019.
20. F. S. Macaulay. Some formulæ in elimination. *Proceedings of The London Mathematical Society*, pages 3–27, 1902.

21. Hideyuki Matsumura. *Commutative Algebra*, volume 56 of *Math Lecture Notes Series*. Benjamin/Cummings Publishing Company, 1980.

22. Alexander P. Morgan. A transformation to avoid solutions at infinity for polynomial systems. *Applied Mathematics and Computation*, 18(1):77–86, 1986.

23. Guillaume Moroz. Complexity of Resolution of Parametric Systems of Polynomial Equations and Inequations. Research Report RR-5929, INRIA, 2006.

24. Masayuki Noro and Kazuhiro Yokoyama. A modular method to compute the rational univariate representation of zero-dimensional ideals. *Journal of Symbolic Computation*, 28(1):243–263, 1999.

25. James Renegar. On the computational complexity and geometry of the first-order theory of the reals. part i: Introduction. preliminaries. the geometry of semi-algebraic sets. the decision problem for the existential theory of the reals. *Journal of Symbolic Computation*, 13(3):255–299, 1992.

26. Fabrice Rouillier. Solving Zero-dimensional Polynomial Systems through the Rational Univariate Representation. Research Report RR-3426, INRIA, 1998.

27. Marie-Françoise Roy Saugata Basu, Richard Pollack. *Algorithms in Real Algebraic Geometry*. Springer Berlin Heidelberg, 2006.

28. Éric Schost. *Sur la résolution des systèmes polynomiaux à paramètres*. PhD thesis, 2001.

29. Éric Schost. Computing parametric geometric resolutions. *Applicable Algebra in Engineering, Communication and Computing*, 13(5):349–393, 2003.

30. B. L. Waerden. *Moderne Algebra*, volume 2. Springer Berlin Heidelberg, 1931.

31. Volker Weispfenning. Comprehensive gröbner bases. *J. Symb. Comput.*, 14(1):1–30, 1992.

32. Richard Zippel. *Effective Polynomial Computation*. Springer New York, NY, https://doi.org/10.1007/978-1-4615-3188-3, 2012.