# Nonnegativity certificates for finite semi-algebraic sets

Matías R Bender, Elias Tsigaridas, Alexander Zenkovich

► To cite this version:

Matías R Bender, Elias Tsigaridas, Alexander Zenkovich. Nonnegativity certificates for finite semi-algebraic sets. 2026. hal-05537275

HAL Id: hal-05537275

https://inria.hal.science/hal-05537275v1

Preprint submitted on 5 Mar 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.

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

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Nonnegativity certificates for finite semi-algebraic sets

Matias Bender¹, Elias Tsigaridas², and Alexander Zenkovich³

¹Inria Saclay and École Polytechnique, IP Paris, France

²Inria Paris and Sorbonne University, Paris, France

³École Normale Supérieure de Paris, Paris, France

March 5, 2026

## Abstract

We introduce new certificates for nonnegativity of multivariate polynomials with rational coefficients over zero-dimensional semi-algebraic sets. They are perfectly complete, certifying every nonnegative polynomial, and perfectly sound, correctly identifying negativity. We rely on resultants computations and Rational Univariate Representations (RUR) and make no assumptions on the input.

For the univariate case, we introduce a perturbation technique that avoids root approximation and does not alter the (bit)size of the input. For multivariate polynomials, we make a reduction to the univariate case using RUR.

For the dense case, we compute a certificate in $\tilde{\mathcal{O}}_B(d^{4n+3}(d+\tau))$ bit operations; it involves numbers of bitsize $\tilde{\mathcal{O}}(d^{3n+2}(d+\tau))$, where $n$ is the number of variables, $d$ the degree, and $\tau$ the maximum coefficient bitsize of the polynomials. For the sparse case, we provide the first sparse certificate based on the Newton polytope $Q$ of the input polynomials. We compute in $\tilde{\mathcal{O}}_B(\mathrm{vol}(Q)^8(n!)^8 2^{5n+3}(n+\tau))$,

For semi-algebraic sets with $s$ inequalities, we present two approaches. The first performs a reduction to the algebraic case and has complexity $\tilde{\mathcal{O}}_B(2^{(3\omega+3)s} d^{5n\tau})$; it is purely algebraic approach and does not require root approximation. The second exploits approximate Lagrange interpolation and matches the $\tilde{\mathcal{O}}(sd^{4n\tau})$ bitsize bounds of recent work by Baldi, Krick, and Mourrain [2] while improving complexity by orders of magnitude and removing all structural assumptions on the input.

Additionally, we provide a witness of negativity, ensuring that we either obtain a certificate or it does not exist.

## 1 Introduction

We study algebraic certificates for the nonnegativity of a polynomial $F \in \mathbb{Z}[X] := \mathbb{Z}[X_1, \dots, X_n]$, of degree $d$ and maximum coefficient bitsize $\tau$, over a zero dimensional (that is consisting only of finitely many points) semi-algebraic set $S(G, H) \subseteq \mathbb{R}^n$; the latter is defined by polynomial equalities $H = (H_1, \dots, H_m)$ and inequalities $G = (G_1, \dots, G_s)$. The certificate consists of a finite collection of (polynomial) algebraic identities, with sizes precisely bounded in terms of $d$, $\tau$, and $n$, and gives us the means to certify the correctness of algorithms deciding positivity. Following Powers [39] and [5], and based on interactive proof systems [18, 1] and certified linear algebra [15], we address the following questions:
(Q₀) What is a theorem that implies the existence of one or more algebraic identities corresponding to the certificate?

(Q₁) Is there an algorithm to compute the certificate, and what is its (bit) complexity?

(Q₂) What is the (bit) size of the integers in the certificate?

(Q₃) What is the (bit) complexity of verifying the algebraic identity induced by the certificate?

(Q₄) If $F$ attains a negative value on $\mathcal{S}(G, H)$, how (and at which bit complexity) can we provide a witness for this?

**Previous work** The study of certificates of positivity finds its roots at the origins of real algebraic geometry, dating back to Hilbert's work on positive polynomials and quadratic forms. A foundational milestone was Artin's solution of Hilbert's 17th problem, which established that we can write every globally nonnegative multivariate polynomial as a sum of squares of rational functions.

Krivine, Stengle, Schmüdgen, and Putinar, among others, extended this result and introduced certificates of positivity over semi-algebraic sets; we refer to [39] and references therein for a detailed presentation. Besides their intrinsic mathematical interest, the importance of certificates of positivity stems from the fact that they transform an inherently hard problem of establishing the nonnegativity of a polynomial into a concrete (and easily) verifiable algebraic identity. They are central to the theoretical foundations of modern polynomial optimisation and they find applications ranging from control [7, 32] to formal verification [19, 10].

In the early 2000s, Lasserre [24] and Parrilo [37] introduced moment and sum-of-squares hierarchies that relax polynomial optimization problems to a sequence of semidefinite programs, the optimal values of which, under some assumptions, converge to the global optimum. Since then, the research community has devoted substantial efforts to understand if (and when) the hierarchies have finite convergence [31, 3], to establish precise degree bounds for the corresponding Positivstellensatz representations [42, 33], and to give improved representations and bounds for special cases of interest, such as positivity over finite semialgebraic sets [25, 2]. Moreover, recent efforts [28] exploit the sparsity of the input.

However, these methods generally yield only approximate certificates and may fail to converge. While there approaches to transform numerical approximations into exact certificates [21, 26], this limitation has motivated research on exact symbolic certificates over the rationals [38, 27, 5, 2]. For instance, [27] certified global non-negativity for polynomials with zero-dimensional radical gradient ideals using Gröbner bases, achieving single exponential complexity. More recently, an approach based on Rational Univariate Representations, SOS-RUR, dropped the radicality assumptions with improved (bit) complexity estimates [5], while an extension [6] certifies non-negativity (modulo the gradient ideal) without any assumptions, alas at the cost of increasing the coefficient bitsize.

A more general problem is the construction of certificates of positivity over *finite semialgebraic sets*, that is sets of real points defined by finite Boolean combinations of polynomial equalities and inequalities and consisting of finitely many points.

In the case where the polynomial equalities generate a zero-dimensional *radical* ideal, Parrilo [36] introduced explicit sum-of-squares certificates based on Lagrange interpolation. For a polynomial that is strictly positive on the real points of the variety, this yields a sum-of-squares representation modulo the defining ideal with explicit degree bounds. However, the construction inherently relies on computations over the algebraic closure.

The most recent and important development in this line of research is due to Baldi, Krick, and Mourrain [2] that refined and extended Parrilo's approach by constructing *rational* certificates
of positivity; see also [22] for the univariate case. Assuming that the defining ideal is radical (or satisfies a colon-ideal condition) and that its generators form a graded basis, they obtain SOS certificates with coefficients in $\mathbb{Q}$, together with explicit bit complexity estimates. Their techniques rely on arithmetic Nullstellensatz and bounds on semidefinite programming. While the radicality assumption is intrinsic to this class of certificates [2, Ex. 3.1], the requirement of a graded-basis demands nontrivial preprocessing and the resulting bounds increase considerably with respect to the input parameters; the following example illustrates this situation:

**Example 1.** Given a bitsize $\tau \in \mathbb{N}$, consider the system $(x_1 - 2^\tau, x_2 - x_1^d, \dots, x_n - x_{n-1}^d) \subset \mathbb{Q}[x_1, \dots, x_n]$. Its graded basis is $\{x_i - 2^\tau d^{i-1}\}_{1 \le i \le n}$, and its bitsize is $\tilde{\mathcal{O}}(\tau d^n)$.

Under this consideration, if the input polynomials have degree at most $d$ and coefficient bitsize at most $\tau$, then their certificate involves rationals of bitsize $\tilde{\mathcal{O}}(d^{4n\tau})$.

**Our contribution** We introduce a new class of exact certificates of positivity (nonnegativity) for polynomials over zero-dimensional semialgebraic sets that are both *perfectly complete*, as they certify every nonnegative polynomial, and *perfectly sound*, as they correctly identify any polynomial that is not nonnegative. We rely on resultant computations and Rational Univariate Representations (RURs), providing explicit answers to questions $(\mathbb{Q}_0)-(\mathbb{Q}_4)$; without making any assumptions on the input. We provide a unified mathematical and algorithmic framework that treats both algebraic (Sec. 2) and semi-algebraic cases (Sec. 3.2).

For the univariate algebraic case, i.e., to certify that $A \in \mathbb{Z}[X]$ in nonnegative on the real roots of $B \in \mathbb{Z}[X]$ (Problem 1) we introduce a novel approach based on the nonnegativity of the resultant $\text{Res}_X(B, Y^2 + A)$ and we introduce a perturbation $A_{u,v}(X) := (1 + u(X - v)^2)A(X)$ to avoid degenerate cases where $A$ evaluates to real negative values at complex roots of $B$ (Thm 3). This technique avoids the use of (approximation) of the roots of $B$ and serves as the foundation for our multivariate certificates. For the multivariate case (Problem 2), we employ RUR-based reduction to transform the problem to the univariate one (Lem. 5). If the size of the input polynomials is $(d, \tau)$, then we compute the certificate in $\tilde{\mathcal{O}}_B(d^{4n+3}(d+\tau))$ and it has bitsize $\tilde{\mathcal{O}}(d^{3n+2}(d+\tau))$ (Thm 4). Even more, we introduce the first certificate based on the sparsity of the input polynomials. If the Newton polytope of the polynomials is $Q$, then we compute the certificate in $\tilde{\mathcal{O}}_B(\text{vol}(Q)^8 (n!)^8 2^{5n+3}(n+\tau))$. and its bitsize is $\tilde{\mathcal{O}}(\text{vol}(Q)^6 (n!)^6 2^{4n+2}(n+\tau))$.

For the univariate semi-algebraic case, we present two approaches. The first one considers a novel reduction to the multivariate algebraic case (Sec. 3.1.1), where we also exploit the special structure of the RUR. The bit complexity is $\tilde{\mathcal{O}}_B(2^{(3\omega+3)s}d^{(8n+7)n\tau})$ and it involves rationals of bitsize $\tilde{\mathcal{O}}(2^{4s}d^{(7n+3)n\tau})$. The second approach uses (approximate) Lagranges polynomial (Sec. 3.1.2) and it is the univariate analog of the approach of [2]. It has bit complexity $\tilde{\mathcal{O}}_B(sd^{5n\tau})$ and involves rationals of bitsize $\tilde{\mathcal{O}}(sd^{4n\tau})$. The bitsize bound matches the previously known [2]; however, we make no assumptions on the input polynomials. The complexity bound improves the previously known by orders of magnitude. The algorithms that we present for the multivariate case are Monte Carlo; this is due to the computation of the RUR.

Finally, we also present effective witness computations, that certify the refutation of a positivity statement (Problem 5). This ensures that our framework provides either a certificate of nonnegativity or a witness of negativity in all cases.

**Notation** We denote by $\mathbb{K}[\mathbf{X}]$ the polynomial ring in the variables $X_1, \dots, X_n$ with coefficients in $\mathbb{K} \in \{\mathbb{Z}, \mathbb{Q}, \mathbb{R}, \mathbb{C}\}$. Also, $\mathbf{X}^\alpha$ is the monomial $X_1^{\alpha_1} \dots X_n^{\alpha_n}$, where $\alpha = (\alpha_1, \dots, \alpha_n) \in \mathbb{N}^n$ is a multi-index, and $f = \sum_{|\alpha| \le d} a_\alpha \mathbf{X}^\alpha \in \mathbb{K}[\mathbf{X}]$. We denote by $\langle R_1, \dots, R_r \rangle$ the ideal generated by
$R_1, \dots, R_r \in \mathbb{K}[\mathbf{X}]$. We use bold lowercase letters to represent a point to distinguish it from the variables, e.g. $\mathbf{x} = (x_1, \dots, x_n) \in \mathbb{R}^n$. We denote by $\mathcal{O}$, resp. $\mathcal{O}_B$, the arithmetic, respectively bit, complexity; we also use $\tilde{\mathcal{O}}$, resp. $\tilde{\mathcal{O}}_B$, to ignore (poly-)logarithmic factors. For an integer $n$, we denote by $[n]$ the set $\{1, 2, \dots, n\}$. For $r \in \mathbb{Q}$, its bitsize is the maximum bitsize of its numerator and denominator. The bitsize of $f \in \mathbb{Q}[\mathbf{X}]$ is the maximum bitsize of its coefficients; Also, for $f \in \mathbb{Q}[\mathbf{X}]$ of degree $d$ and bitsize $\tau$, we say that it has size $(d, \tau)$. For $f \in \mathbb{R}[\mathbf{X}]$, we denote its nonnegativity over the reals by the abbreviation $f \ge 0$, or $f \ge 0$ on $\mathbb{R}^n$, instead of writing $f(\mathbf{x}) \ge 0$, for all $\mathbf{x} \in \mathbb{R}^n$.

# 2 Positivity over a 0-dim real algebraic set

## 2.1 Univariate positivity (algebraic)

Consider the following rational univariate polynomials in $\mathbb{Z}[X]$

$$A(X) = a_{d_1} \prod_{i=1}^{d_1} (X - \alpha_i) \quad \text{and} \quad B(X) = b_{d_2} \prod_{j=1}^{d_2} (X - \beta_j), \qquad (1)$$

where $d_1 > 0$, $a_{d_1} > 0$, $b_{d_2} > 0$; the size of $A$ is $(d_1, \tau_1)$, and of $B$ is $(d_2, \tau_2)$. We study the following problem.

**Problem 1.** Let $A, B \in \mathbb{Z}[X]$ as in (1); $B$ is square-free. Certify that $[A(\beta) \ge 0, \text{ for all } \beta \in \mathbb{R} \text{ with } B(\beta) = 0]$ is true or give a witness that is false.

We introduce a new variable $Y$ and consider the resultant

$$R := \mathrm{Res}_X(B(X), Y^2 + A(X)) = b_{d_2}^{d_1} \prod_{i=1}^{d_2} (Y^2 + A(\beta_i)) \in \mathbb{Z}[Y], \qquad (2)$$

where the last equality follows from Poisson's formula [20]. We shall see that the nonnegativity of $R$ leads to a solution of Problem 1.

**Theorem 1.** Let $R$ be as in (2) and assume there are $w_0, \dots, w_\nu \in \mathbb{Q}_{\ge 0}$, $s_1, \dots, s_\nu \in \mathbb{Q}[Y]$, $k \in \mathbb{N}$ such that $R(Y)$ is the following SOS,

$$R(Y) = w_0 Y^{2k} + \sum_{i=1}^{\nu} w_i s_i(Y)^2. \qquad (3)$$

Then, for every $\beta \in \mathbb{R}$ such that $B(\beta) = 0$, we have that $A(\beta) \ge 0$.

*Proof.* The proof is by contradiction. Assume there is $\beta \in \mathbb{R}$ such that $B(\beta) = 0$ and $A(\beta) < 0$. Eq. (2), implies that $\sqrt{-A(\beta)} > 0$ is a real root of $R$. At the same time, by (3), $R(Y) \ge w_0 Y^{2k}$, for any real $Y$. Hence, the only real root of $R(Y)$ is $Y = 0 \ne \sqrt{-A(\beta)}$. $\square$

Next we show when the SOS from (3) exists and how to compute it.

**Lemma 1.** Assume that for every $\beta \in \mathbb{C}$ such that $B(\beta) = 0$ and $A(\beta) \in \mathbb{R}$, we have that $A(\beta) \ge 0$. Then, there is an SOS decomposition for $R$, as in (3), which we can compute using uSOS [4].

*Proof.* By Poisson's formula (2), we know that only the real roots of $R$ correspond to roots $\beta$ of $B$ such that $A(\beta) \le 0$. However, under our assumptions, this only happens when $A(\beta) = 0$; in this case, the root of $R$ is $Y = 0$ and has even multiplicity. Let $2k$ be the multiplicity of the root $Y = 0$ in $R$, and consider the polynomial $\bar{R} = R \cdot Y^{-2k}$. Then, $\bar{R}$ has no real roots and its leading monomial $b_{d_2}^{d_1}$ is positive, so it is strictly positive. Using uSOS [4], we can compute an SOS decomposition for $\bar{R}$ of the form, $\bar{R} = w_0 + \sum_{i=1}^{\nu} w_i s_i^2$, where $\nu \le 2d_2 + 2$, $w_0, \dots, w_\nu \in \mathbb{Q}_{>0}$ and $s_1, \dots, s_\nu \in \mathbb{Q}[Y]$. If we multiply both sides of this identity by $Y^{2k}$, then we obtain the claimed decomposition for $R$. $\square$
The previous condition might not be satisfied for every pair $(A, B)$ for which $A$ is nonnegative at the real roots of $B$, as the evaluation of $A$ at a complex root of $B$ might be a real number and, in particular, a negative one. To avoid this situation, we perturb $A$. If $u \in \mathbb{Q}_{>0}$ and $v \in \mathbb{Q}$, then we define the perturbed polynomial

$$A_{u,v}(X) := (1 + u (X - v)^2)A(X), \qquad (4)$$

Our next lemma shows that, for almost all pairs $(u, v)$, the evaluation of $A$ at the complex roots of $B$ results a complex number.

**Lemma 2.** Consider $A, B \in \mathbb{Z}[X]$, as in (1), and $\beta \in \mathbb{C} \setminus \mathbb{R}$ a root of $B$ that is not a root of $A$. For any $v \in \mathbb{Q}$, such that $v \neq \mathrm{Re}(\beta)$, there is at most one $u \in \mathbb{Q}$ such that $A_{u,v}(\beta)$ is real.

*Proof.* Say $A(\beta) = \zeta_1 + i\zeta_2$ and $(\beta - v)^2 A(\beta) = \psi_1 + i\psi_2$, where $\zeta_i, \psi_i \in \mathbb{R}$. Then, $A_{u,v}(\beta) = (\zeta_1 + u\psi_1) + i(\zeta_2 + u\psi_2)$. If $\psi_2 \neq 0$, then $A_{u,v}(\beta) \in \mathbb{R}$ only when $\zeta_2 + u\psi_2 = 0 \Rightarrow u = -\frac{\zeta_2}{\psi_2}$. That is, $A_{u,v}(\beta)$ is real for at most one value of $u$. If $\psi_2 = 0$ and $A_{u,v}(\beta) \in \mathbb{R}$, $(\beta - v)^2 A(\beta) \in \mathbb{R}$ and so it must hold $v = \mathrm{Re}(\beta)$; so there is no suitable choice for $u$. Overall, there is at most one such $u$. $\square$

The next lemma shows that we can use $A_{u,v}$ to check or show that $A$ is nonnegative at the roots of $B$. It follows from the fact that $(1 + u (X - v)^2)$ is strictly positive for any real value of $X$.

**Lemma 3.** Consider $A, B \in \mathbb{Z}[X]$, as in (1), and $(u, v) \in \mathbb{Q}_{>0} \times \mathbb{Q}$. For every real root $\beta \in \mathbb{R}$ of $B$, $A_{u,v}(\beta) \ge 0 \iff A(\beta) \ge 0$.

Putting all together, we obtain a certificate for Problem 1.

**Theorem 2.** Let $A, B \in \mathbb{Z}[X]$ be as in (1). Then, $A(\beta) \ge 0$ for every real root $\beta$ of $B$ if and only if there exist $(u, v) \in \mathbb{Q}_{>0} \times \mathbb{Q}$, $w_0, \dots, w_\nu \in \mathbb{Q}_{>0}$, $s_1, \dots, s_\nu \in \mathbb{Q}[Y]$, $k \in \mathbb{N}$, and $P, Q \in \mathbb{Q}[X, Y]$ st

$$1. \quad \tilde{R}(Y) := P(X, Y)B(X) + Q(X, Y)(Y^2 + A_{u,v}(X)) \in \mathbb{Q}[Y],$$

$$2. \quad \deg \tilde{R} = 2d_2 \text{ and the leading coefficient of } \tilde{R} \text{ is positive,}$$

$$3. \quad \tilde{R}(Y) = w_0 Y^{2k} + \sum_{i=1}^{\nu} w_i s_i (Y)^2.$$

The above data form a certificate for Problem 1.

*Proof.* To prove the forward implication, Consider $(u, v) \in \mathbb{Q}_{>0} \times \mathbb{Q}$ such that, for any $\beta \in \mathbb{C} \setminus \mathbb{R}$ such that $B(\beta) = 0$, either $A(\beta) = 0$ or $A_{u,v}(\beta) \in \mathbb{C} \setminus \mathbb{R}$. The existence of this pair follows from Lem. 2. Then, by Lem. 3, if $A \ge 0$ at every real root of $B$, then either $A_{u,v}$ is complex or non-negative at every root of $B$. Let $\tilde{R}(Y) = \mathrm{Res}_X(B(X), Y^2 + A_{u,v}(X)) \in \mathbb{Q}[Y]$. From the cofactors of the resultant, we know that there are two polynomials $P, Q \in \mathbb{Q}[X, Y]$ such that $\tilde{R}(Y) := P(X, Y)B(X) + Q(X, Y)(Y^2 + A_{u,v}(X)) \in \mathbb{Q}[Y]$. As $u > 0$, the leading monomial of $\tilde{R}(Y)$ is positive and its degree $2d_2$. Therefore, by Lem. 1, we can decompose $\tilde{R}$ as in (3).

For the opposite implication, we first show that $\tilde{R}(Y)$ is a multiple of the resultant. As $d_1 > 2$, the leading monomials of $B(X)$ and $Y^2 + A_{u,v}(X)$ wrt to $X$ are independent of $Y$. Hence, the elimination ideal $\langle B(X), Y^2 + A_{u,v}(X) \rangle \cap \mathbb{Q}[Y]$ is generated by the resultant $\mathrm{Res}_X(B(X), Y^2 + A_{u,v}(X))$; see [11, Thm 3.6.8]. As the existence of $P, Q$ guarantee that $\tilde{R}(Y)$ also belongs to this elimination ideal and its degree agrees with the one of the resultant, $2d_2$, then one must be a non-zero multiple of the other. Moreover, both have non-zero and rational leading monomial, so the constant is rational and positive. By Thm. 1, the SOS decomposition of $\tilde{R}$ implies that for every $\beta \in \mathbb{R}$ such that $B(\beta) = 0$, we have that $A_{u,v}(\beta) \ge 0$. The rest of the proof follows from Lem. 3. $\square$
The previous theorem supports a randomized algorithm for Problem 1: choose generic $(u, v) \in \mathbb{Q}_{>0} \times \mathbb{Q}$ and try to write $\mathbf{Res}_X(B(X), Y^2 + A_{u,v}(X))$ (after factoring out the variable $Y$) as a SOS with a constant term using uSOS [4]. Lem. 2 shows that, for most $v$s, there is at most $d_2$ values of $u$ such that this approach does not work. So in the worst case, we consider $\mathcal{O}(d_2^2)$ different pairs.

Our next lemma allow us to split the choice of $u$ from $v$, by noting that the "good" values of $v$ should avoid the real parts of the roots of $B$. This is equivalent to say that $B(X - v)$ has no pure imaginary root, which we can check with a GCD computation. This follows (among others) from Hermite-Biehler's theorem [40, Thm. 6.3.4].

**Lemma 4.** Consider $B \in \mathbb{Z}[X]$ and let $B(X) = B_e(X^2) + XB_o(X^2)$ be its decomposition to even and odd parts. Then, $B_e(X)$ and $B_o(X)$ are not coprime if and only if there exists two roots $(\beta_1, \beta_2)$ of $B$, not necessarily different, which are symmetric wrt the imaginary axis, that is, $\beta_1 = a + ib$ and $\beta_2 = -a + ib$. In particular, if $\gcd(B_e, B_o) \in \mathbb{Q}$, then $B$ has no purely imaginary roots.

It remains to introduce a witness of negativity. We postpone this discussion for Section 4 to also consider the semi-algebraic case. Putting all together, the following algorithm solves Problem 1.

<caption>**Algorithm 1:** Univariate Algebraic Certification</caption>

**Input:** $A(X), B(X) \in \mathbb{Z}[X]$ as in (1); $B$ square-free.
**Output:** A certificate for Problem 1 as in Theorem 2 or a witness that it does not hold as in Theorem 6.

(S1) Using Alg. 2, try to compute a witness for Problem 1. If it succeeds, **return** witness (see Sec. 4)

(S2) Choose $v \sim \text{Unif}[2d_2^2]$.
Let $B_{v,e}(X), B_{v,o}(X)$ be even and odd parts of $B(X - v)$ If $\gcd(B_{v,e}(X), B_{v,o}(X)) \notin \mathbb{Q}$, **GOTO** (S2)

(S3) Choose $u \sim \text{Unif}[2d_2^2]$. Compute resultant and cofactors $R_{u,v}(Y) \leftarrow \mathbf{Res}_X(B(X), Y^2 + (1 + u(X - v)^2)A(X))$

(S4) Try to compute SOS for $R_{u,v}(Y)$ as in (3) (see Lem. 1) If it fails, **GOTO** (S3) and make a different choice for $u$.

(S5) **return** the certificate for Problem 1 (see Thm. 2)

**Theorem 3.** Let $A, B \in \mathbb{Z}[X]$ be polynomials of size $(d_1, \tau_1)$ and $(d_2, \tau_2)$, respectively. There is a Las Vegas algorithm, (Alg. 1), to compute the certificate of Thm. 2 for Problem 1 in expected $\tilde{\mathcal{O}}_B((d_1+d_2)^2(d_1\tau_2+d_2\tau_1))$ bit operations. Both the certificate and the witness involve rationals of bitsize $\tilde{\mathcal{O}}_B(d_2^2\tau_1+d_1d_2\tau_2)$.

*Proof.* The correctness of Alg. 1 follows from Thm 2, Lem. 4, and Thm 7. We analyze the bit complexity step by step. The bitsize of $u$ and $v$ is at most $\mathcal{O}(\lg d_2) = \tilde{\mathcal{O}}_B(1)$ and do not affect the bounds.

The complexity of (S1) is $\tilde{\mathcal{O}}_B(d_1^3 + d_1^2d_2\tau_2 + d_1^2\tau_1 + d_2^2)$; see Cor. 3.

In (S2) we need to compute the even and odd part of $B(X - v)$. For this, we compute $B(X - v)$ in $\tilde{\mathcal{O}}_B(d_2^2 + d_2\tau_2)$ which has bitsize $\tilde{\mathcal{O}}_B(d_2 + \tau_2)$ [16, Thm. 2.4]; the same holds for its odd and even parts. The computation of the GCD takes $\tilde{\mathcal{O}}_B(d_2^3 + d_2^2\tau_2)$ [17, Cor. 11.20]. We observe that there are at most $d_2^2$ values for $v$ such that the even and odd part are not coprime (for each pair of roots,
there is at most one bad choice for $v$). So, in expectation, our algorithm considers a constant time of different values for $v$ and its bitsize is negligible.

In (S3), we choose $u$ and compute the resultant $R_{u,v} \in \mathbb{Z}[Y]$, which has size $(2d_2, \tilde{\mathcal{O}}(d_1\tau_2+d_2\tau_1))$. Following [17, Cor. 11.21], we can compute it using $\tilde{\mathcal{O}}((d_1+d_2)^2)$ arithmetic operations; hence the bit complexity is $\tilde{\mathcal{O}}_B((d_1+d_2)^2(d_1\tau_2+d_2\tau_1))$. The cofactors $P, Q \in \mathbb{Z}[X, Y]$ have degrees $\mathcal{O}(d_1+d_2)$ and their bitsize is $\tilde{\mathcal{O}}(d_1\tau_2+d_2\tau_1)$. We compute them at the same complexity as $R_{u,v}$ [17, Cor. 11.14].

In (S4), we apply uSOS on $R_{u,v}$. This takes $\tilde{\mathcal{O}}_B(d_2^3\tau_1 + d_1d_2^2\tau_2)$ and return rationals of bitsize $\tilde{\mathcal{O}}(d_2^2\tau_1 + d_1d_2\tau_2)$ (Prop. 4). There are at most $d_2$ bad choices for $u$, so in expectation, we repeat (S3) and (S4) a constant number of times. $\square$

The complexity of verifying the equalities of Thm 2 that consist the certificate is linear in the input (bit)size and we omit the details.

**What about positivity?** To handle positivity in Problem 1, that is when $A(X) > 0$, we need to check both $A(X) \ge 0$ and $A(X) \ne 0$, when $B(X) = 0$. For the second check, we check if $A$ and $B$ are coprime via their GCD, so the bounds of Thm. 3 still apply.

## 2.2 Multivariate positivity (algebraic)

Let $F, G_1, \dots, G_m \in \mathbb{Z}[\mathbf{X}]$ of size $(d, \tau)$. Consider the ideal $I_G := \langle G_1, \dots, G_m \rangle$, the corresponding variety $\mathbb{V}(I_G) \subseteq \mathbb{C}^n$, and the real algebraic set $\mathcal{S}(\mathbf{G}) = \mathbb{V}(I_G) \cap \mathbb{R}^n$; we also use $\mathcal{S}(I_G)$. We say that $I_G$ is 0-dimensional, when $\mathbb{V}(I_G)$ contains a finite set of points.

**Problem 2.** Let $F, G_1, \dots, G_n \in \mathbb{Z}[\mathbf{X}]$, such that $I_G$ is 0-dimensional. Give a certificate that $[F(\boldsymbol{\beta}) \ge 0, \text{ for all } \boldsymbol{\beta} \in \mathcal{S}(\mathbf{G}) \subseteq \mathbb{R}^n]$ is true or a witness that it is false.

A key object in our construction is a rational univariate representation (RUR) of $\mathbb{V}(I_G)$. In turn, RUR depends on a separating linear form $\ell \in \mathbb{Q}[\mathbf{X}]$ on $\mathbb{V}(I_G)$, which is such that for every $\alpha, \beta \in \mathbb{V}(I_G)$ with $\alpha \ne \beta$, we have $\ell(\alpha) \ne \ell(\beta)$.

**Definition 1.** Let $I_G \subseteq \mathbb{Q}[\mathbf{X}]$ be such that $\mathbb{V}(I_G)$ is a zero-dimensional and $\ell(\mathbf{X})$ is a separating linear form. A rational univariate representation (RUR) for $\mathbb{V}(I_G)$, wrt $\ell$, is a rational parameterization of the points in $\mathbb{V}(I_G)$, given as a set of univariate polynomials $B, R'_0, R_1, \dots, R_n \in \mathbb{Q}[T]$, such that

$$ \mathbb{V}(I_G) = \left\{ \left( \frac{R_1}{R'_0}(T), \dots, \frac{R_n}{R'_0}(T) \right) : B(T) = 0 \right\}, $$

$B$ and $R'_0$ are coprime, and $t = \ell(\frac{R_1}{R'_0}(t), \dots, \frac{R_n}{R'_0}(t))$, when $B(t) = 0$.

*Remark 1.* By the definition of the separating linear form, $\ell$, there is a one-to-one correspondence between the complex roots $B$ and the points in $\mathbb{V}(I_G)$. If $\ell$ has real coefficients, as in our case that $\ell \in \mathbb{Q}[\mathbf{X}]$, then there is also a one-to-one correspondence between the real roots of $B$ and the points in $\mathcal{S}(I_G) = \mathbb{V}(I_G) \cap \mathbb{R}^n$, e.g., [41].

For recent theoretical and practical developments on computing RUR, see [14]. Following [29, 5], we have the following complexity bounds for computing RURs, supported by a Monte Carlo algorithm.

**Proposition 1.** Let $I_G := \langle G_1, \dots, G_m \rangle \subseteq \mathbb{Q}[\mathbf{X}]$, be a zero-dimensional ideal, with generators of size $(d, \tau)$.
▷ (Dense) There is a Monte Carlo algorithm which computes a separating linear form and a RUR of $V(I_G)$ in bit complexity

$$ \tilde{\mathcal{G}}_B(e^{\omega n+O(\lg n)} d^{(\omega+2)n} (d+\tau)). $$

The polynomials in the RUR have size $(d^n, \tilde{\mathcal{G}}(d^n + nd^{n-1}(\tau + n)))$.

▷ (Sparse) Let $Q$ be the convex hull of the union of the Newton polytopes of $G_i(\mathbf{X})$ and assume $Q$ contains a (integer-displaced) standard $n$-dimensional simplex. Then, we can compute the RUR in

$$ \tilde{\mathcal{G}}_B(n^{(3\omega+2)n+O(1)} \mathrm{vol}(Q)^{\omega+2} \tau). $$

bit operations. The degree and the bitsize of the polynomials in RUR are at most $n! \mathrm{vol}(Q)$ and $\tilde{\mathcal{G}}((n+1)! \mathrm{vol}(Q)(n+\tau))$, respectively.

*Proof.* When $m = n$, [5, Sec. 2] gives an algorithm to compute a RUR for the isolated solution of system in the claimed bounds. If $m > n$, we proceed by constructing two square systems, by generic linear combinations of the input polynomials.

In particular, we construct two generic square systems $G_1, G_2$; each consists of $n$ polynomials of the form $\sum_{k=1}^m h_{j,k}^{(i)} G_k$, where $h_{j,k}^{(i)} B_k$ has degree $d$ (or Newton polytope $Q$) and $h_{j,k}^{(i)}$ are polynomials with generic-enough coefficients of bitsize $\mathcal{O}(n \lg d)$; see App. B. The varieties defined by $G_1$ and $G_2$ contain $V(I_G)$ and, under genericity assumptions, are zero-dimensional; see proof of [9, Thm. 14]. Similarly, their intersection is exactly $V(I_G)$. Let $\ell(\mathbf{X})$ be a linear form separating for $G_1 \cup G_2$. Let $(B^{(1)}(T), R_0^{(1)}(T), \dots, R_n^{(1)}(T))$, respectively $(B^{(2)}(T), R_0^{(2)}(T), \dots, R_n^{(2)}(T))$, be the polynomials in the RUR of $\mathbb{V}_C(G_1)$, resp. $\mathbb{V}_C(G_2)$, with respect to $\ell(\mathbf{X})$. Complexity and bitsize bounds for these operations appear in [5, Cor. 2.15] (dense) and [5, Thm. 2.12] (sparse). Observe that, for each $i \in \{1, 2\}$, the roots of $B^{(i)}(T)$ correspond to $\{\ell(p) : p \in V(G_i)\}$. As both RURs depend on the same separating form and $\ell(\mathbf{X})$ separates $G_1 \cup G_2$, we have that the common roots of $B^{(1)}(T)$ and $B^{(2)}(T)$, i.e. the roots of their GCD, are $\{\ell(p) : p \in \mathbb{V}_C(G_1) \cap \mathbb{V}_C(G_2)\} = V(I_G)$. Therefore, $\mathrm{gcd}(B^{(1)}, B^{(2)})$, $R_0^{(1)}$, $R_1^{(1)}, \dots, R_n^{(1)}$ define a RUR for $V(I_G)$ with respect to $\ell(\mathbf{X})$. The computation of the GCD does not increase neither the complexity nor the bitsizes. $\square$

Using the RUR, the quest for a certificate for Problem 2 becomes a univariate problem. Indeed, if $(B, R_0^{(1)}, \dots, R_n)$ is a RUR of $V(I_G)$, then $F(\mathbf{X})$ is nonnegative at $\mathcal{S}(G)$ if and only if the univariate rational function $F(\frac{R_1}{R_0^{(1)}}, \dots, \frac{R_n}{R_0^{(1)}})$ is nonnegative at every real root of $B$. We can use any polynomial congruent to $F(\mathbf{X})$ modulo the equations for the RUR to test this property.

**Lemma 5.** Consider $F(\mathbf{X})$ and let $(B, R_0^{(1)}, \dots, R_n)$ be a RUR of $V(I_G)$. Further assume, polynomials $\mathbf{X}^\alpha, r, q_0, \dots, q_m \in \mathbb{Q}[T, \mathbf{X}]$, and $Q \in \mathbb{Q}[T]$ coprime to $B$, such that

$$ Q^2 F(\mathbf{X}) = q_0 B(T) + \sum_{i \ge 1} q_i (R_0'(T) X_i - R_i(T)) + r(T) (\mathbf{X}^\alpha)^2, \quad (5) $$

and $\bar{R}^\alpha := \prod_i R_i^{\alpha_i}$ is coprime with $B$. Let $|\alpha| := \sum_i \alpha_i$ and define:

$$ A(T) := r(T) \cdot R_0'(T)^{|\alpha| \bmod 2}. \quad (6) $$

Then, $F(\mathbf{X})$ is nonnegative, resp. positive, at $\mathcal{S}(G) \subseteq \mathbb{R}^n$ if and only if $A(T)$ is nonnegative, resp. positive, at $V_\mathbb{R}(B)$.
**Proof.** Following Rmk. 1, there is a one-to-one correspondence between the points in $\mathcal{S}(I_G)$ and the real roots in $B$. Hence, consider $t \in \mathbb{V}_R(B)$ and $\mathbf{x}(t) = (\frac{R_1(t)}{R'_0(t)}, \dots, \frac{R_n(t)}{R'_0(t)}) \in \mathcal{S}(\mathbf{G})$. If we evaluate both sides of (5) at $(t, \mathbf{x}(t))$, then we obtain the identity

$$Q(t)^2 F\left(\frac{R_1}{R'_0}(t), \dots, \frac{R_n}{R'_0}(t)\right) = r(t) \frac{\bar{R}^\alpha(t)}{R'_0(t)^{|\alpha|}}.$$

As $B$ is coprime to $Q$ and $\bar{R}^\alpha$, the sign of $F(\mathbf{x}(t))$ agrees with the sign of $A(t) = (R'_0(t))^2 \lfloor \frac{|\alpha|+1}{2} \rfloor^{-|\alpha|} r(t)$, at every $t \in \mathbb{V}_R(B)$. $\square$

Overall, Eq. (5) transforms the multivariate certification problem to a univariate one. Provided that we know a correct RUR for $\mathbb{V}(I_G)$, the polynomials in (5) together with a certificate that $A$ in (6) is nonnegative at $\mathbb{V}_R(B)$ gives a certificate for Problem 2.

**Theorem 4.** Let $F, G_1, \dots, G_m \in \mathbb{Z}[\mathbf{X}]$ be of size $(d, \tau)$; assume all have the same Newton polytope $Q$ and it contains a (integer-displaced) standard simplex and a even point, i.e., $2\alpha \in Q$, with $\alpha \in \mathbb{Z}^n$. Let $(B, R'_0, \dots, R_n)$ be a RUR of $\mathbb{V}(I_G)$. The bit complexity of computing a dense of sparse certificate for Problem 2, consisting of the polynomials in (5) and a certificate that $A$ in (6) is nonnegative, or positive, at $\mathbb{V}_R(B)$, or a witness of negativity is:

▷ (Dense) $\tilde{\mathcal{O}}_B(d^{4n+3}(d+\tau))$. It involves rationals of bitsize $\tilde{\mathcal{O}}(d^{3n+2}(d+\tau))$.

▷ (Sparse) if $\mathbb{V}(I_G) \subset (\mathbb{C}^*)^n$, $\tilde{\mathcal{O}}_B(\mathrm{vol}(Q)^8 (n!)^8 2^{5n+3}(n+\tau))$. It involves rationals of bitsize $\tilde{\mathcal{O}}(\mathrm{vol}(Q)^6 (n!)^6 2^{4n+2}(n+\tau))$.

**Proof.** First, we study the complexity of transforming the problem to a univariate one. Then, we apply Thm. 3.

**Dense certificate.** Let $r_0 = F(\mathbf{X})$ and, recursively define the polynomials $m_i, r_i, q_i$ by the pseudo-division of the $r_i$ by $R'_0(T)X_i - R_i(T)$ wrt the variable $X_i$. They satisfy the identity

$$m_i r_{i-1} = q_i(T, \mathbf{X}) (R'_0(T)X_i - R_i(T)) + r_i.$$

By induction, we have that $m_i = (R'_0(T))^{\mathrm{deg}_{X_i}(F)}$ and, as each $R'_0(T)X_i - R_i(T)$ has degree 1 wrt $X_i$, $r_i \in \mathbb{Q}[T, X_{i+1}, \dots, X_n]$. Hence,

$$r_n(T) = (R'_0)^d F(\mathbf{X}) + \sum_{i=1}^{n} (-1)^i (R'_0)^{\sum_{j<i} m_j} q_i (R'_0(T)X_i - R_i(T)).$$

The bit complexity analysis follows from [5, Sec. 3.1]: see [5, Lem. 3.6] for the reminders $r_i$, and [5, Lem. 3.7] for the quotients $q_i$. They are of size $(\mathcal{O}(d^{n+1}), \tilde{\mathcal{O}}(d^n(d+\tau))$; the degree of $q_i$ wrt $T$ is at most $d$. So, by (6), this is also the size of $A$. The size of $B$, as an element of the RUR is $(d^n, \tilde{\mathcal{O}}(d^{n-1}(d+\tau))$ (Prop. 1). Finally, to obtain the certificate, we apply Alg. 2 to $A$ and $B$. This costs $\tilde{\mathcal{O}}_B(d^{n+3}(d+\tau))$ and involves rationals of bitsize $\tilde{\mathcal{O}}(d^{3n+2}(d+\tau))$ (Thm. 3).

**Dense certificate.** We use the sparse resultant as in [5, Sec. 3.3]. Given a polytope $Q$, we consider the vector space $\mathbb{Q}(T)[\mathbf{X}]_Q := \mathrm{span}_{\mathbb{Q}(T)}\{\mathbf{X}^\alpha : \alpha \in Q \cap \mathbb{Z}^n\}$. We define $L_i$ as the Newton polytope in $\mathbb{R}^n$ of the polynomial $X_i + 1$ and, for each $i$, we consider the Minkowski sum $\hat{L}_i := Q + L_1 + \dots + L_{i-1} + L_{i+1} + \dots + L_n$. Let $\hat{L}_0 := L_1 + \dots + L_n$. Let $\bar{\varepsilon} := (-\varepsilon, \dots, -\varepsilon)$, where $\varepsilon$ is sufficiently
small positive constant. We have that $\mathbb{Q}(T) \simeq \mathbb{Q}(T)[\mathbf{X}]_{\hat{L}_0+\hat{\varepsilon}}$. For each $F \in \mathbb{Q}(T)_Q$, we consider the Sylvester map

$$ \text{Sylv}_F : \prod_{i=0}^{n} \mathbb{Q}(T)[\mathbf{X}]_{\hat{L}_i + \hat{\varepsilon}} \rightarrow \mathbb{Q}(T)[\mathbf{X}]_{Q+\hat{L}_0+\hat{\varepsilon}} \quad (7) \\ (c_0(T), c_1(T, \mathbf{X}), \dots, c_n(T, \mathbf{X})) \mapsto c_0 \cdot F(\mathbf{X}) + \sum_i c_i \cdot (R'_0 X_i - R_i). $$

For generic choices of $F$, it follows from [12, Thm 1.8] that $\text{Sylv}_F$ is surjective. Let $E = \#((Q + \hat{L}_0 + \hat{\varepsilon})\cap \mathbb{Z}^n)$. We fix a generic-enough subspace $V$ of the domain of the map of dimension $E$ generated by vectors of polynomials $\{(c_{j,i})_j\}_i$ of bitsize $\tilde{\mathcal{G}}(\log(E))$ and degree 0 in $T$. For our argument, it is with no loss of generality to assume that $(c_{j,0})_j = (1, 0, \dots, 0)$ and $c_{0,i} = 0$, for $i > 0$. We fix this basis and the monomial basis of $\mathbb{Q}(T)[\mathbf{X}]_{Q+\hat{L}_0+\hat{\varepsilon}}$. From the genericity of $V$, the fact that $\mathbb{Q}(T)[\mathbf{X}]_{\hat{L}_0+\hat{\varepsilon}}$ is a one-dimensional $\mathbb{Q}(T)$-vector space, and the Poisson formula for the sparse resultant [12], it follows that

$$ \det(\text{Sylv}_F|_V) = H(T) \cdot F\left(\frac{R_1}{R'_0}(T), \dots, \frac{R_n}{R'_0}(T)\right) \in \mathbb{Q}[T], $$

with $H(T) \neq 0$; the degree and the bitsize determinant (and $H$) are $(E n! \text{vol}(Q))$ and $\tilde{\mathcal{G}}(E (\lg(E) + (n+1)! \text{vol}(Q) (n+\tau)))$.

Fix a monomial $(\mathbf{X}^\alpha)^2$ in the codomain of the map. By Cramer's rule, we can compute $(c_0^\alpha, \dots, c_n^\alpha) \in V$ such that $\text{Sylv}_F(c_0^\alpha, \dots, c_n^\alpha) = H(T) \cdot F\left(\frac{R_1}{R'_0}(T), \dots, \frac{R_n}{R'_0}(T)\right) \cdot (\mathbf{X}^\alpha)^2$. Moreover, the bitsize of every (sparse) polynomial $c_i^\alpha$ is $\tilde{\mathcal{G}}(E (\lg(E) + (n+1)! \text{vol}(Q) (n+\tau)))$, and its degree wrt $T$ is at most $(E n! \text{vol}(Q))$. Also, as $V$ is generic-enough, $c_0^\alpha$ and $B$ are coprime (Sec. C). Hence, we conclude that

$$ c_0^\alpha(T)^2 F(\mathbf{X}) = - \sum_i c_0^\alpha(T) c_i^{F,\alpha}(\mathbf{X}, T) (R'_0(T)X_i - R_i(T)) + c_0^\alpha(T) H(T) F\left(\frac{R_1}{R'_0}(T), \dots, \frac{R_n}{R'_0}(T)\right) (\mathbf{X}^\alpha)^2. \quad (8) $$

Observe that $(\prod_i R_i^{2\alpha_i})$ is coprime to $B(t)$ as every solution in $\mathbb{V}_C(I_G)$ has every coordinate different to zero.

To estimate the complexity of computing these polynomials, similarly to [5, Lem. 3.13], we use [23] and conclude that we need to perform $\tilde{\mathcal{G}}_B(E^\omega n! \text{vol}(Q) E (\log(E) + (n+1)! \text{vol}(Q) (n+\tau)))$ bit operations. As $E \le 2^{n+1}n! \text{vol}(Q)$ [8], we conclude that we can compute the identity in (8) in $\tilde{\mathcal{G}}((n!)^{\omega+4} \text{vol}(Q)^{\omega+3} \tau)$, the bitsize of the polynomials is $\tilde{\mathcal{G}}(2^n (n+1)!^2 \text{vol}(Q)^2 (n+\tau))$, and their degree wrt $T$ is at most $(2^{n+1} n!^2 \text{vol}(Q)^2)$. Finally, we apply Thm. 3. The cost is $\tilde{\mathcal{G}}_B(\text{vol}(Q)^8 (n!)^8 2^{5n+3} (n+\tau))$ and the rationals of the certificate have bitsize $\tilde{\mathcal{G}}(\text{vol}(Q)^6 (n!)^6 2^{4n+2} (n+\tau))$. $\square$

**Remark 2 (Certification of the RUR).** To certify that our reduction from the multivariate to the univariate case is correct, we need the polynomials satisfying the identity (5), but we also have to check that the RUR we use is a correct RUR for $G_1, \dots, G_m$. Verifying if the candidate RUR is correct is not straightforward. Moreover, an incorrect RUR can lead to fake certificates, see [5, Ex. 1.2]. Using the notation from Prop. 1, in [5, Sec. 4], we show that we can validate the RUR in $\tilde{\mathcal{G}}_B(n^{(3\omega+4)n} \text{vol}(Q)^{3\omega+4} (\tau + \lg \text{vol}(Q)))$ bit operations [5, Thm. 4.5]. For dense systems, the bound becomes $\tilde{\mathcal{G}}_B(e^{(3\omega+4)n} d^{(3\omega+4)n} (\tau + n \lg d))$.
# 3 Non-negativity over 0-dim semi-algebraic sets

We consider the problem of certifying a polynomial is nonnegative over a zero-dimensional basic closed semialgebraic set.

## 3.1 Univariate non-negativity (semi-algebraic)

Consider $A, B \in \mathbb{Z}[X]$ of sizes $(d_1, \tau_1)$, $(d_2, \tau_2)$, as in (1); $B$ is square-free. Consider $C = \{C_1, \dots, C_s\} \subseteq \mathbb{Z}[X]$ of sizes $(d_3, \tau_3)$, with

$$C_i(X) = \sum_{k=0}^{d_3} c_{k,i} X^k = c_{d_3} \prod_{\ell=1}^{d_3} (X - \gamma_{\ell,i}) \in \mathbb{Z}[X], i \in [s]. \quad (9)$$

Let $\mathcal{S}(B, C) = \{x \in \mathbb{R} | B(x) = 0 \text{ and } C_i(x) \ge 0, i \in [s]\}$ be a basic and closed semi-algebraic set defined by the polynomials $B$ and $C$.

**Problem 3.** Let $A, B, C_1, \dots, C_s \in \mathbb{Z}[X]$, such that $B$ is square-free. Give a certificate that $[A(\beta) \ge 0, \text{ for all } \beta \in \mathcal{S}(B, C)]$ is true or a witness that it is false.

We propose two approaches for Problem 3. The first one reduces the problem to the multivariate algebraic case (Sec. 2.2) and the second one, as in [2] uses approximate Lagrange polynomials.

For simplicity, we let $d := \max\{d_2, d_3\}$ and $\tau = \max\{\tau_2, \tau_3\}$.

### 3.1.1 Reduction to the multivariate algebraic case

Consider the ideal $I_{B,C} = \langle B(X), C_1(X) - Y_1^2, \dots, C_s(X) - Y_s^2 \rangle \subseteq \mathbb{Z}[X, Y]$, where $Y = (Y_1, \dots, Y_s)$ are new variables. Also $\mathcal{S}(I_{B,C}) := \mathbb{V}(I_{B,C}) \cap \mathbb{R}^{s+1}$.

We make the following observation: The projection on the first coordinate of $\mathcal{S}(I_{B,C})$ is the the semi-algebraic set $\mathcal{S}(B, C)$. Hence, $A$ is nonnegative at the semi-algebraic set $\mathcal{S}(B, C)$ if and only if $A$ is nonnegative at $\mathcal{S}(I_{B,C})$. To certify the latter, we can use the certificate from Section 2.2. However, we notice that the polynomials defining $I_{B,C}$ form a very special structured polynomial system. Thus, we exploit this structure to compute its RUR and obtain better bounds than the ones we get by directly applying the algorithm supported by Prop. 1.

**Proposition 2.** Consider $B, C_1, \dots, C_s \in \mathbb{Z}[X]$ of size $(d, \tau)$, and the ideal $I_{B,C} = \langle B(X), C_1(X) - Y_1^2, \dots, C_s(X) - Y_s^2 \rangle \subseteq \mathbb{Z}[X, Y]$. Then, $I_{B,C}$ is 0-dimensional.

Moreover, we can compute a separating form $\ell(X, Y)$ for $\mathbb{V}(I_{B,C})$ and its RUR in $\tilde{\mathcal{O}}(d^{\omega+2} 2^{(3\omega+2)s} s^{1+\omega/2}(\tau+s^2))$. The polynomials in the RUR have size $(\mathcal{O}(2^s d), \tilde{\mathcal{O}}(2^s d\tau))$.

*Proof.* We assume that $B(X)$ has degree exactly $d$ and the monomial 1 appears in at least of the polynomials; we refer to Rmk. 3 for the general case. Let $Q$ be Newton polytope of the union of the Newton polytopes of $B(X), C_1(X) - Y_1^2, \dots, C_s(X) - Y_s^2$ in $\mathbb{R}^{s+1}$. Then, $Q$ is a simplex and its vertices are $0, 2e_1, \dots, 2e_s, de_{s+1}$, where $\{e_i\}_{i \in [s+1]}$ is the canonical basis of $\mathbb{R}^{s+1}$. We will show that we can treat each polynomial as a sparse polynomial having the same Newton polytope $Q$. First, observe that the degree of $\mathbb{V}_Q(I_{B,C})$ is $2^s d$, as for each root $\beta$ of $B(X)$, each equation $Y_i^2 - C_i(\beta)$ has two solutions (counting multiplicities). This number agrees with the normalized volume of $Q$. From a toric geometry point-of-view, the toric variety associated to $Q$ contains the affine space $\mathbb{C}^{s+1}$ and, if we homogenize each polynomial wrt $Q$, the previous sentence implies that we do not add any solution to the system; see Rmk. 3.

Now we consider the sparse resultant of $s+2$ polynomials with Newton polytope $Q$ and specialize it for the system of polynomials $\{B(X), Y_1^2 - C_1(X), \dots, Y_s^2 - C_s(X)\}$ and the $U$-polynomial $U_0 +$
$U_x X + \sum_i U_{y_i} Y_i$. By Poisson's formula [13, Thm. 4.2], this resultant is a non-zero polynomial of the following form:

$$c \prod_{\beta=(\beta, \beta_y) \in \mathcal{V}(I_{B,C})} (U_0 + U_x \beta + \sum_i U_{y_i} \beta_{y_i})^{m_\beta},$$

where $c$ is a non-zero constant and $m_\beta$ is the multiplicity of the solution $\beta = (\beta, \beta_{y_1}, \dots, \beta_{y_s}) \in \mathbb{C}^{s+1}$. Hence, if we specialize the variables $U_x, U_{y_1}, \dots, U_{y_s}$, then we can recover the RUR of the system [29, Sec. 2.2]. From this fact, we conclude that the polynomials in the RUR have degree at most $2^s d$ and bitsize $\tilde{\mathcal{O}}(2^s d\tau)$ [5, Sec. 2.3].

As detailed in [5, Sec. 2.3], the complexity of computing the RUR is upper-bounded by the complexity of computing the resultant of the systems. By [5, Prop. 2.11], this complexity is given by $\tilde{\mathcal{O}}(E^{\omega 2^{2s} d^2 \tau})$, where $E$ is the size of the resultant matrix and $\omega$ is the exponent of matrix multiplication.

To upper-bound $E$, observe that its size is bounded by the number of lattice points in $(s+2)Q$. For any $k$, the number of lattice points in $kQ$ is upper bounded by $(d k + 1) (2^{k+s})$. If $k = s + 2$, then

$$|kQ \cap \mathbb{Z}^{s+1}| \le \frac{d(s+2)+1}{\sqrt{\pi s}} 2^{3s+2} \in \mathcal{O}(d\sqrt{s} 2^{3s}).$$

The complexity bound follows straightforwardly. $\square$

**Remark 3 (Solutions at infinity).** The projective toric variety associated to $Q$ is the weighted projective space $\mathbb{P}(1, 2, d, \dots, d)$ and its associated homogeneous coordinate ring is the one given by $\mathbb{C}[Z, X, Y_1, \dots, Y_s]$, where the degree of $z$ is 1, the one of $X$ is 2, and the degree of the $Y_i$s is $d$. We can homogenize the input polynomials in this ring as weighted homogeneous polynomials of degree $2d$, and consider the resultant associated to $\mathbb{P}(1, 2, d, \dots, d)$ to obtain equivalent results.

If the degree of $B(X)$ is smaller than $d$, then the previous approach will introduce solutions at infinity. However, this solutions are finite: if we homogenize the polynomials we obtain $B(\frac{X}{Z^2}) \cdot Z^{2d}$ and $Y_i^2 - C_i(\frac{X}{Z^2}) \cdot Z^{2d}$. Hence, when $Z = 0$, the system degenerates to $b_d X^d, Y_i^2 - c_{i,d} X^d$, where $b_d$, resp. $c_{i,d}$, is the coefficient of degree $d$ wrt $X$ in $B(X)$, resp. $C_i(X)$. This new system has finite solutions in $\mathbb{P}(1, 2, d, \dots, d) \cap \{Z = 0\}$. Therefore, the unmixed sparse resultant for the polytope $Q$ specialized in $(B(X), Y_1^2 - C_1(X), \dots, Y_d^2 - C_d(X), (U_0 + U_x X + \sum_i U_{y_i} Y_i))$, vanishes identically, as the homogenization of the U-polynomial, $(U_0 Z^{2d} + U_x X Z^{2d-2} + \sum_i U_{y_i} Y_i Z^d)$, vanishes at $Z = 0$. To avoid this issue, we need to consider the U-polynomial $U_0 + U_x X + \sum_i U_{y_i} Y_i Z^d + U_{x^d} X^d + \sum_i U_{y_i^2} Y_i^2$. However, this does not change our analysis complexity.

**Corollary 1.** We compute a certificate of nonnegativity for Problem 3 in $\tilde{\mathcal{O}}_B(2^{(3\omega+2)s} d^3 d_1^2 (2^s dd_1 \tau + \tau_1))$, and its bitsize is

$$\tilde{\mathcal{O}}_B(2^{2s} d^2 (2^s dd_1 \tau + \tau_1)), \text{ where } d := \max\{d_2, d_3\} \text{ and } \tau = \max\{\tau_2, \tau_3\}.$$

*Proof.* Using the algorithm supported by Prop. 2 we compute the RUR of $\mathcal{V}(I_{B,C})$, given by polynomials $B_R, R'_0, R_x, R_1, \dots, R_s \in \mathbb{Q}[T]$. The projection onto the $X$-coordinate agrees with $\mathcal{S}(B, C)$ and is given by $\{\frac{R_x(t)}{R'_0(t)} \mid t \in \mathbb{R} \text{ and } B_R(t) = 0\}$.

The polynomials in the RUR have size $(\mathcal{O}(2^s d), \tilde{\mathcal{O}}(2^s d\tau))$ (Prop. 2).

We substitute the rational representation of $X$ in $A$. After clearing denominators, as we did in (6) to maintain the sign, we obtain a univariate polynomial in $T$, say $A_N \in \mathbb{Z}[T]$, of degree $\tilde{\mathcal{O}}(2^s dd_1)$ and bitsize $\tilde{\mathcal{O}}(\tau_1 + 2^s dd_1 \tau)$. It remains to certify that $A_N$ is nonnegative at the real roots of $B_R$; this is Problem 1 and we rely on Thm. 3. The certification costs $\tilde{\mathcal{O}}_B(2^{3s} d^3 d_1^2 (2^s dd_1 \tau + \tau_1))$ and it involves rationals of bitsize $\tilde{\mathcal{O}}(2^{2s} d^2 (2^s dd_1 \tau + \tau_1))$. Now we replace $2^{3s}$ with $2^{(3\omega+2)s}$ to account for the computation of the RUR (Prop. 2). $\square$
### 3.1.2 Approximate Lagrange polynomials

We present an alternative solution to Problem 3 based closely on the work of Baldi et al. [2]. Our next lemma introduces our certificate and how to compute it.

**Lemma 6.** Let A and B be coprime. Then, $A(\beta) \ge 0$, for all $\beta \in \mathcal{S}(B, C)$ if and only if there exist $\varrho_1, \dots, \varrho_r \in \mathbb{Q}_{>0}$ and $\tilde{\ell}_1, \dots, \tilde{\ell}_r \in \mathbb{Q}[T]$ such that $\tilde{\Phi} \in \mathbb{Q}[T]$ is nonnegative on $\mathcal{S}(B)$, where

$$ \tilde{\Phi}(T) := A(T) - \sum_{k=1}^{r} \varrho_k \tilde{\ell}_k^2(T) C_k(T). \quad (10) $$

*Proof.* For ($\Leftarrow$), take $\beta \in \mathcal{S}(B, C)$. Then, $\tilde{\Phi}(\beta) \ge 0$ (by assumption) and $C_k(\beta) \ge 0$ (by definition of $\mathcal{S}(B, C)$). Hence, $A(\beta) \ge 0$.

For ($\Rightarrow$), we construct an specific $\tilde{\Phi}(T)$ as follows: Let $\beta_1, \dots, \beta_r$ be the real roots of B, such that $A(\beta_k) < 0$ and there is at least one $C_i$, with $C_i(\beta_k) < 0$, for $k \in [r]$; wlog, assume that for $\beta_k$ the corresponding polynomial is $C_k$.

With this notation, we consider as in [2, Lem. 2.8] the polynomial

$$ \Phi(T) = A(T) - \sum_{k=1}^{r} \varrho_k \ell_k^2(T) C_k(T), \quad (11) $$

where $\ell_k$ is the Lagrange polynomial for the root $\beta_k$, that is $\ell_k(\beta_i) = \text{Indicator}[k=i]$, and $\varrho_k \in \mathbb{Z}$ is such that $\Phi(\beta_i) > 0$, for all $i \in [r]$. If so, $\Phi(\beta) > 0$ for every $\beta \in \mathcal{S}(B)$, as A and B are coprime.

Each $\varrho_k$ should be such that $\Phi(\beta_k) = A(\beta_k) - \varrho_k C_k(\beta_k) > 0$, which is satisfied when

$$ \varrho_k > \frac{2 A(\beta_k)}{C_k(\beta_k)} = \left| \frac{2 A(\beta_k)}{C_k(\beta_k)} \right| > 0. $$

Hence, we take $\varrho_k \ge \varrho := 2^{\mu_A+\mu_C+1}$, where $\mu_A$ and $\mu_C$ are such that $2^{-\mu_A} \le |2 A(\beta)| \le 2^{\mu_A}$, for every $\beta \in \mathcal{S}(B)$ (A are B are coprime), and $2^{-\mu_C} \le |C(\beta_k)| \le 2^{\mu_C}$, for all $k \in [r]$. It holds $\mu_A = \tilde{\mathcal{O}}(d_1\tau_2 + d_2\tau_1)$ and $\mu_C = \tilde{\mathcal{O}}(d_3\tau_2 + d_4\tau_3)$ [4, Lem. B.3].

Unfortunately, we cannot use $\Phi(T)$ as the polynomials $\ell_k(T)$ involve algebraic numbers and might not belong to $\mathbb{Q}[T]$. To overcome this obstacle, we approximate the $\beta_k$'s with sufficient precision to obtain polynomials $\tilde{\ell}_k \in \mathbb{Q}[T]$ and define $\tilde{\Phi}(T)$ as in (10). If the precision is high-enough, $\tilde{\Phi}(T)$ is "close" to $\Phi$ and so both are positive at all the roots of B as $\tilde{\Phi}(T) = \Phi(T) - \sum_k \rho_k (\ell_k^2(T) - \tilde{\ell}_k^2(T)) C_k(T)$ and the maximum of $\sum_k \rho_k (\ell_k^2(\beta) - \tilde{\ell}_k^2(\beta)) C_k(\beta)$ for every $\beta \in \mathcal{S}(B)$ is upper-bounded by how close the functions are.

Recall that $\ell_k(T) = \prod_{j \neq k} \frac{T-\beta_j}{\beta_k-\beta_j} = \text{lc}(B') \prod_{B'(\beta_k) \neq \beta_k} \frac{T-\beta_j}{B'(\beta_k)}$. First, we approximate the evaluations $B'(\beta_k)$. We approximate all the roots of B with (dyadic) rationals $\tilde{\beta}_k$, up to accuracy $\kappa$, that is $|\beta_k - \tilde{\beta}_k| \le 2^{-\kappa}$. The cost is $\tilde{\mathcal{O}}_B(d_2^3 + d_2^2\tau + d^2\kappa)$ [30, 35]. Then, using an approximate multipoint evaluation algorithm [34, Lemma 21], we obtain, for all $k$, an approximate evaluation $\tilde{B}'(\tilde{\beta}_k)$, such that $|\tilde{B}'(\tilde{\beta}_k) - \tilde{B}'(\tilde{\beta}_k)| \le 2^{-\kappa+\tilde{\mathcal{O}}(d_2\tau_2)}$. This costs $\tilde{\mathcal{O}}_B(d_2\kappa+d_2^2\tau_2)$. It also holds $2^{-\tilde{\mathcal{O}}(d_2\tau_2)} \le |\tilde{B}'(\tilde{\beta}_k)| \le 2^{\tilde{\mathcal{O}}(d_2\tau_2)}$. To compute the products $m_k := \prod_{j \neq k} (T-\beta_j)$, we employ the approximate fan-in algorithm [34, Lemma 19] to obtain polynomials $\tilde{m}_k \in \mathbb{Q}[T]$, such that $\|m_k - \tilde{m}_k\|_{\infty} \le 2^{-\kappa+\tilde{\mathcal{O}}(d_2\tau_2)}$. It also holds $\|m_k\|_{\infty} \le 2^{\tilde{\mathcal{O}}(d_2\tau_2)}$. So, overall, $\|\ell_k - \tilde{\ell}_k\|_{\infty} \le 2^{-\kappa+\tilde{\mathcal{O}}(d_2\tau_2)}$. These computations take $\tilde{\mathcal{O}}_B(d_2\kappa + d_2^2\tau_2)$.

It remains to estimate $\kappa$. For a root $\beta \in \mathbb{R}$ of B, we have

$$ |\Phi(\beta) - \tilde{\Phi}(\beta)| = \left| \sum_{k=1}^{r} \varrho_k (\ell_k^2(\beta) - \tilde{\ell}_k^2(\beta)) C_k(\beta) \right| \le r \varrho 2^{\mu_C} 2^{-\kappa+\tilde{\mathcal{O}}(d_2\tau_2)}. $$
Consequently, $\Phi(\beta) - 2^{-\kappa+\eta} < \tilde{\Phi}(\beta)$ where $\eta = \mu_A + 2\mu_C - \lg r + \tilde{\mathcal{O}}(d_2\tau_2)$. However, for every real root $\beta$, it holds $\Phi(\beta) > |A(\beta)| > 2^{-\mu_A}$; if $\beta \in \mathcal{S}(B, C)$, the sum of Lagrange polynomials is zero and if not, then both summands of $\Phi(\beta)$ are positive. So, it suffices $2^{-\mu_A} > 2^{-\kappa+\eta}$, which leads to $\kappa > \mu_A + \eta = 2\mu_A + 2\mu_C + \lg r + \tilde{\mathcal{O}}(d_2\tau_2)$. As $\mu_A = \tilde{\mathcal{O}}(d_2\tau_1 + d_1\tau_2)$ and $\mu_C = \tilde{\mathcal{O}}(d_2\tau_3 + d_1\tau_2)$, we have $\kappa = \tilde{\mathcal{O}}(d_2(\tau_1 + \tau_2 + \tau_3) + (d_1+d_3)\tau_2 + \lg r)$. Hence, $\tilde{\Phi} \in \mathbb{Z}[T]$ is of degree $2d_2$ and bitsize $\tilde{\mathcal{O}}(r\kappa)$. The factor $r$ in the bitsize appears after clearing denominators, as we want polynomials in $\mathbb{Z}[T]$.

We can replace $r$ with $s$, the number of inequalities because if two roots, say $\beta_1$ and $\beta_2$, violate the same inequality, say $C_1$, then the rhs of (10) (for these two roots) factors as $\varrho(\ell_1^2(T) - \ell_2^2(T))C_1(T)$. $\square$

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

**Corollary 2.** Assume that $A(\beta) \ge 0$ for all $\beta \in \mathcal{S}(B, C)$. Then, we can certify Problem 3 by computing the GCD and the cofactors of $\gcd(A, B)$, computing $\tilde{\Phi}(T)$ as in (10) for the polynomials $A, \tilde{B}$, where $\tilde{B} := B/\gcd(A, B)$, and a certificate that $\tilde{\Phi}(T)$ is non-negative on $\mathcal{S}(\tilde{B})$. We do this in $\tilde{\mathcal{O}}_B(rd_2^4(\tau_1 + \tau_2 + \tau_3) + rd_2^3(d_1 + d_3)\tau_2)$ bit operations. The size of the rational involved is $\tilde{\mathcal{O}}_B(rd_2^3(\tau_1 + \tau_2 + \tau_3) + rd_2^2(d_1 + d_3)\tau_2)$.

If all the polynomial are of size $(d, \tau)$, then the cost and bitsize become $\tilde{\mathcal{O}}_B sd^4\tau)$ and $\tilde{\mathcal{O}}_B sd^3\tau)$, respectively.

*Proof.* First, observe that computing the GCD of $A$ and $B$ (and its cofactors) and replacing $B$ by $\tilde{B}$ in the analysis of the proof of Lem.6 does not affect our bit estimations, so it is wlog to assume $A$ and $B$ coprime. In the same proof, the bit complexity and sizes of computing $\tilde{\Phi}(T)$ were established.

It remains to certify that $\tilde{\Phi}$ is non-negative at all the roots of $\tilde{B}$. For this, we rely on Thm 3. The cost is $\tilde{\mathcal{O}}_B(rd_2^3(\tau_1 + \tau_2 + \tau_3) + rd_2^2(d_1 + d_3)\tau_2)$ and involves numbers of bitsize $\tilde{\mathcal{O}}_B(rd_2^3(\tau_1 + \tau_2 + \tau_3) + rd_2^2(d_1 + d_3)\tau_2)$. If all the polynomial are of size $(d, \tau)$, then the cost and bitsize become $\tilde{\mathcal{O}}_B(r d^4\tau)$ and $\tilde{\mathcal{O}}_B(4d^3\tau)$, respectively. $\square$

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

**What about strict inequalities?** If we want to certify that $A(X) \ge 0$ when $B(X) = 0, C_1(X), \dots, C_s(X) \ge 0$ and $D > 0$, we replace $B(X)$ by the $B(X)/\gcd(B, D)$. To certify the GCD we do as in the algebraic case. The case of more than one strict inequality, follows similarly.

## 3.2 Multivariate non-negativity (semi-algebraic)

Given $G_1, \dots, G_m, H_1, \dots H_s \in \mathbb{Z}[\mathbf{X}]$, let

$$ \mathcal{S}(\mathbf{G}, \mathbf{H}) := \{\mathbf{x} \in \mathbb{R}^n : (\forall i, j) G_i(\mathbf{x}) = 0, H_j(\mathbf{x}) \ge 0\}. $$

**Problem 4.** Let $F, G_1, \dots, G_m, H_1, \dots H_s \in \mathbb{Z}[\mathbf{X}]$, such that $I_G$ is 0-dimensional. Give a certificate that $[F(\beta) \ge 0, \text{ for all } \beta \in \mathcal{S}(\mathbf{G}, \mathbf{H}) \subseteq \mathbb{R}^n]$ is true, or a witness that it is false.

As we did in the algebraic case, we will reduce this problem to the univariate semi-algebraic case using the RUR. Let the RUR of $\mathbb{V}(I_G)$ be $(B, R'_0, R_1, \dots, R_n)$ wrt $\ell(\mathbf{X})$. The rational curve $x(t) := (\frac{R_i(T)}{R'_0(T)})_i$ goes through every point in $\mathbb{V}(I_G)$, and it maps bijectively every root (resp. real root) of $B$ to a point (resp. real point) in $\mathbb{V}(I_G)$ (the inverse of the map is given by evaluations as $\ell(\mathbf{X}))$. Hence, we compose $\mathbf{x}(T)$ and the polynomials $F$ and $H_j$ to obtain the following systems of inequalities

$$ \frac{F_N(T)}{R'_0^{d_1}(T)} \ge 0, \text{ where } B(T) = 0, \text{ and } \frac{H_{1N}(T)}{R'_0^{d_{3,1}}} \ge 0, \dots, \frac{H_{sN}(T)}{R'_0^{d_{3,1}}} \ge 0, $$
which we transform to polynomial inequalities, as in Lem. 5, to reduce this problem to Problem 2,
with $A(T) := F_N(T)(R'_0(T))^{d_1 \bmod 2}$, $B(T)$ coming from the RUR, and $C_i(T) := H_{iN}(T)(R'_0(T))^{d_{3,i} \bmod 2}$.

Prop. 3 summarizes this discussion. Its proof is the same as the one of Lem. 5, so we skip it. A
similar analysis can be done in the sparse case, but we skip it for brevity.

**Proposition 3.** The polynomial $F(X)$ is nonnegative, resp. positive, in the semialgebraic set defined by $\mathcal{S}(G, H)$ if and only if $A(T)$ is positive, resp. nonnegative, in the semialgebraic set defined by $\{t \in \mathbb{R} : B(t) = 0, (\forall i) C_i(t) \ge 0\}$.

**Theorem 5.** Let $F, G_1, \dots, G_m, H_1, \dots, H_s \in \mathbb{Z}[X]$, of sizes $(d_1, \tau_1)$, $(d_2, \tau_2)$, and $(d_3, \tau_3)$, such that $I_G$ is 0-dimensional. We can compute a certificate (or a witness) for Problem 4:

▷ using a reduction to the algebraic case (Sec. 3.1.1) in

$\tilde{\mathcal{G}}_B(2^{(3\omega+3)s} d_1^3 d_2^{8n-1} d_3^5 (\tau_1+\tau_2+\tau_3))$ bit operations, involving rationals of bitsize $\tilde{\mathcal{G}}(2^{4s} d_1 d_2^{7n-1} d_3^3 (\tau_1+\tau_2+\tau_3))$.

▷ using approximate Lagrange polynomials (Sec. 3.1.2) in

$\tilde{\mathcal{G}}_B(s d_2^{5n-1} (\tau_1 + (d_1+d_3)\tau_2 + \tau_3))$ bit operations, involving rationals of bitsize $\tilde{\mathcal{G}}(s d_2^{4n-1} (\tau_1 + (d_1+d_3)\tau_2 + \tau_3))$.

For the same size, $(d, \tau)$, the bounds become $\tilde{\mathcal{G}}(2^{(3\omega+3)s} d^{(8n+7)n\tau})$ and $\tilde{\mathcal{G}}(2^{4s} d^{(7n+3)n\tau})$, and $\tilde{\mathcal{G}}_B sd^{5n\tau}$ and $\tilde{\mathcal{G}}_B sd^{4n\tau}$, respectively.

*Proof.* The complexity is dominated by the computation of the certificated for the univariate problem. Using the bounds on the RUR, we deduce that the polynomials $A, B$, and $C_i$ (in the univariate reduction) have sizes $(2d_1d_2^n, \tilde{\mathcal{G}}(d_1d_2^{n-1}\tau_2 + \tau_1))$, $(d_2^n, \tilde{\mathcal{G}}(d_2^{n-1}\tau_2))$, and $(2d_3d_2^n, \tilde{\mathcal{G}}(d_3d_2^{n-1}\tau_2 + \tau_3))$, respectively. The bounds for the reduction to algebraic case follow by applying Cor. 1 while the approximate Langrange polynomials we use Cor. 2. $\square$

# 4 Certifying a polynomial is not nonnegative

We consider the problem of certifying that a polynomial is not nonnegative over a zero-dimensional
basic closed semialgebraic set. We consider only the univariate case, as we can reduce the multivariate
to it, using the techniques of Sec. 3.2.

**Problem 5.** Let $A, B, C_1, \dots, C_s \in \mathbb{Z}[X]$, where $B$ is square-free. Suppose there exists a real root $\beta$ of $B$ such that $A(\beta) < 0$ and $C_1(\beta) \ge 0, \dots, C_s(\beta) \ge 0$. Provide a certificate for the existence of such root.

A certificate for Problem 5 certifies the negativity of $A$; we call it witness of negativity and its
precise definition is as follows:

**Theorem 6.** There exists $\beta \in \mathcal{S}(B, C)$ such that $A(\beta) < 0$ if and only if there exist the following (data):

• An interval with rational endpoints, $J = [a, b] \subset \mathbb{R}$

• A partition of $[s] = I_1 \cup I_2$,

• SOS decompositions $\{\sigma_0, \sigma_i, \text{ for } i \in I_2\}$, and

• Polynomials $G, U_0 \in \mathbb{Q}[X]$ and $\{U_i\}_{i \in I_1} \subset \mathbb{Q}[X]$
satisfing the following

$$
\triangleright B(a) \cdot B(b) < 0,
$$

$$
\triangleright \sigma_0 \text{ is a SOS certificate of (strict) positivity for } -A \text{ on } J \text{ (Prop. 5)},
$$

$$
\triangleright \text{For all } i \in I_2, \sigma_i \text{ is a SOS certificate of nonnegativity of } C_i \text{ on } J,
$$

$$
\triangleright G \text{ divides } B \text{ and } C_i, \text{ i.e., } G \cdot U_0 = B \text{ and } G \cdot U_i = C_i, \text{ for all } i \in I_1, \text{ and } G(a) \cdot G(b) < 0 \text{ (or } I_1 = \emptyset).
$$

A witness of negativity of $A$ on $\mathcal{S}(B, C)$ consists of the above data.

Proof. To prove (⇒), let $\beta \in \mathcal{S}(B, C)$ be the point where $A$ is negative. Choose an interval $J$ containing $\beta$ which does not contain any other roots of $A, B$ or $C$. Let $I_1$ be the set of indices s.t. $C_i(\beta) = 0$ for all $i \in I_1$, and let $I_2$ be its complement. Then, $G = \gcd(B, \{C_i\}_{i \in I_1})$ is zero at $\beta$ and square-free (as $B$ is) and it has no other roots in $J$. So, it changes sign at the endpoints of $J$. Since $J$ contains no other roots, $A$ is strictly negative and $C_i$ is positive for every $i \in I_2$, so they admit SOS decompositons on $J$ by Prop. 5.

For the converse, since $G$ changes sign, there must be a common root $\beta$ of $B$ and $C_i$, for every $i \in I_1$. From the SOS decompositions, it follows that $A(\beta)$ is strictly negative and $C_i(\beta)$ is nonnegative, for every $i \in I_2$. Then, $A(\beta) < 0$ and $\beta \in \mathcal{S}(B, C)$. $\square$

The pseudo-code for computing a witness appears in Alg. 2.

**Theorem 7.** Consider polynomials $A, B, C_1, \dots, C_s \in \mathbb{Z}[X]$ of size $(d, \tau)$. Alg. 2 compute a witness of negativity of $A$ on $\mathcal{S}(B, C)$ in $\tilde{\mathcal{O}}_B(sd^3\tau)$ bit operations. It involves rationals of bitsize $\tilde{\mathcal{O}}(s d^2\tau)$.

**Corollary 3.** Consider $A, B \in \mathbb{Z}[X]$ of size $(d_1, \tau_1)$ and $(d_2, \tau_2)$. We can compute a witness of negativity of $A$ on $\mathbb{V}_{\mathbb{R}}(B)$ or decide that such witness does not exist, in $\tilde{\mathcal{O}}_B(d_1^3 + d_1^2\tau_2 + d_2^2\tau_1 + d_2^2)$. It involves rationals of bitsize $\tilde{\mathcal{O}}(d_1d_2\tau_2 + d_1\tau_1)$.

Proof of Thm 7. The correctness follows from Thm. 6.

In Step (S1), we isolate the real roots the polynomials $B, BA$, and $BC_j$, for $j \in [s]$. These polynomials have sizes most $(\tilde{\mathcal{O}}(d), \tilde{\mathcal{O}}(\tau))$. The cost of root isolation is $\tilde{\mathcal{O}}_B(s d^3 + d^2 \tau)$ [30, Thm. 4]. As the aggregate separation bound of all the polynomials is $\tilde{\mathcal{O}}(d\tau)$, at the same cost, we refine the isolating intervals for the roots of $B$ so that they are disjoint from all the isolating intervals of all $C_j$'s and $A$. Let these intervals be $J_k = [a_k, b_k]$, where $k \le d$. Then, each $C_j$ either has constant sign on $J_k$, or, has a single root $\beta$ in $J_k$.

In Step (S2), we evaluate each $C_j$ at the endpoints of all $J_k$ to identify the intervals, and hence the roots of $B$, for which all the $C_j$'s are nonnegative. For this we use multipoint evaluation; it costs $\tilde{\mathcal{O}}_B(d^3 + d^2\tau)$ and in total $s \tilde{\mathcal{O}}_B(d^3 + d^2\tau)$ [34, Lem. 21].

In Step (S3), we compute the GCD $G$ of $B$ and all the polynomials $C_i$ which change sign on $J_k$
and the factors $U_0 = B/G, U_i = C_i/G$. In the worst case we need to perform $s$ GCD computations
and $s$ exact divisions; their total cost $\tilde{\mathcal{O}}_B(s \, d^2 \tau)$.

In Step (S4) we compute certificates of nonnegativity on $J := [a, b]$ for $-A, C_i$, for every $i \in I_2$. These are polynomials of size $(d, \tau)$ and the endpoints of $J$ have bitsize $\tilde{\mathcal{O}}(d\tau)$. So, we compute each certificate in $\tilde{\mathcal{O}}_B(d^3\tau)$ and it involves rationals of size $\tilde{\mathcal{O}}(d^2\tau)$ [4, Thm 2.14]. Overall, it takes $\tilde{\mathcal{O}}_B(s d^3\tau)$ bit operations. $\square$
*Proof Cor. 3.* The proof is similar to the proof of Thm. 7. The SOS representation of $-A$ on an isolating interval of $B$ dominates the complexity. The endpoints of the interval have bitsize $\tilde{\Theta}(d_2\tau_2)$ and the SOS representation costs $\tilde{\Theta}_B(d_1^3 + d_1^2d_2\tau_2 + d_1^2\tau_1 + d_2^2)$ and involves numbers of bitsize $\tilde{\Theta}(d_1d_2\tau_2 + d_1\tau_1)$ ([4, Thm. 2.14]). □

<caption>**Algorithm 2:** Univariate Algebraic Witness Computation</caption>

**Input:** Univariate polynomials $A, B, C_1, \dots, C_s \in \mathbb{Q}[X]$ 
**Output:** A witness of negativity of $A$ on $\mathcal{S}(B, C)$ 
or **False** if none exists

(S1) Compute isolating intervals for the roots of $B$. Refine them to exclude other roots of $A, C_1, \dots, C_s$.

(S2) Find an interval $J$ where $A$ is negative and each of the $C_i$ is either positive or changes signs. If no such interval exists, **return False**.

(S3) Let $I_2 \subseteq [s]$ be the indices $i$ st $C_i$ does not change signs on $J$. Compute $G = \gcd(B, \{C_i : [s] \setminus J_2\})$.

(S4) Compute the SOS decompositon for $-A, C_i$ for every $i \in J_2$.

(S5) **return** the certificate for Problem 5 (see Thm.6)

## Acknowledgements

The authors thank Lorenzo Baldi, Teresa Krick, and Bernard Mourrain, for various useful comments and suggestions, and also making more clear the connections with [2]. The authors thank Fabrice Rouillier for various discussions and suggestions about RUR and clarifications regarding [14] and its efficient implementation. This research benefited from the support of the FMJH Program Gaspard Monge for optimization and operations research and their interactions with data science. The authors are partially supported by the PGMO grant SOAP, ANR JCJC PeACE (ANR-25-CE48-3760), and ANR PRC ZADyG (ANR-25-CE48-7058).

## References

[1] László Babai and Shlomo Moran. "Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity classes". In: *Journal of Computer and System Sciences* 36.2 (1988), pp. 254-276.

[2] Lorenzo Baldi, Teresa Krick, and Bernard Mourrain. "An effective Positivstellensatz over the rational numbers for finite semialgebraic sets". en. In: *Math. Comput.* (Dec. 2025).

[3] Lorenzo Baldi and Bernard Mourrain. "On the effective Putinar's Positivstellensatz and moment approximation". In: *Mathematical Programming* 200.1 (2023), pp. 71-103.

[4] Matías Bender, Philipp di Dio, and Elias Tsigaridas. "Positive Univariate Polynomials: SOS certificates, algorithms, bit complexity, and T-systems". https://inria.hal.science/hal-05269445. Sept. 2025. URL: https://inria.hal.science/hal-05269445.
[5] Matías Bender, Elias Tsigaridas, and Chaoping Zhu. "Certificates of nonnegativity of multivariate polynomials with zero-dimensional gradient ideal and infimum attained". https://inria.hal.science/hal-05382946. Nov. 2025. URL: https://inria.hal.science/hal-05382946.

[6] Matías R Bender et al. "Certificates for nonnegativity of multivariate integer polynomials under perturbations". https://inria.hal.science/hal-05407890. Dec. 2025. URL: https://inria.hal.science/hal-05407890.

[7] Grigoriy Blekherman, Pablo A Parrilo, and Rekha R Thomas. *Semidefinite optimization and convex algebraic geometry*. SIAM, 2012.

[8] Hans Frederik Blichfeldt. "A new principle in the geometry of numbers, with some applications". In: *Trans of the American Mathematical Society* 15.3 (1914), pp. 227-235.

[9] Leandro Caniglia, André Galligo, and Joos Heintz. "Some new effectivity bounds in computational geometry". In: *International Conference on Applied Algebra, Algebraic Algorithms, and Error-Correcting Codes*. Springer. 1988, pp. 131-151.

[10] Sylvain Chevillard et al. "Efficient and accurate computation of upper bounds of approximation errors". In: *Theoretical Computer Science* 412.16 (2011). Elsevier, pp. 1523-1543. URL: https://www.sciencedirect.com/science/article/pii/S0304397510006900.

[11] David A. Cox, John Little, and Donal O'Shea. *Ideals, varieties, and algorithms: an introduction to computational algebraic geometry and commutative algebra*. 4th edition. Undergraduate Texts in Mathematics. Cham: Springer International Publishing, 2015. ISBN: 978-3-319-16721-3.

[12] Carlos D'Andrea and Gabriela Jeronimo. "Sparse Nullstellensatz, resultants and determinants of complexes". In: *arXiv preprint arXiv:2407.13450* (2024).

[13] Carlos D'Andrea and Martín Sombra. "A Poisson formula for the sparse resultant". In: *Proceedings of the London Mathematical Society* 110.4 (2015), pp. 932-964.

[14] Alexander Demin, Fabrice Rouillier, and Joao Ruiz. "Reading Rational Univariate Representations on lexicographic Groebner bases". In: *arXiv preprint arXiv:2402.07141* (2024).

[15] Jean-Guillaume Dumas and Erich Kaltofen. "Essentially optimal interactive certificates in linear algebra". In: *Proc. 39th International Symposium on Symbolic and Algebraic Computation (ISSAC)*. 2014, pp. 146-153.

[16] Joachim von zur Gathen and Jürgen Gerhard. "Fast algorithms for Taylor shifts and certain difference equations". In: *Proc, Intl Symposium on Symbolic and Algebraic Computation (ISSAC)*. Kihei, Maui, Hawaii, United States: ACM Press, 1997.

[17] Joachim von zur Gathen and Jürgen Gerhard. *Modern computer algebra*. 3rd. Cambridge University press, 2003.

[18] Shafi Goldwasser, Silvio Micali, and Chales Rackoff. "The knowledge complexity of interactive proof-systems". In: *Providing sound foundations for cryptography: On the work of shafi goldwasser and silvio micali*. 2019, pp. 203-225.

[19] John Harrison. "Verifying nonlinear real formulas via sums of squares". In: *International Conference on Theorem Proving in Higher Order Logics*. Springer. 2007, pp. 102-118.

[20] Jean-Pierre Jouanolou. "Le formalisme du résultant". In: *Advances in Mathematics* 90.2 (1991), pp. 117-263.
[21] Erich L. Kaltofen et al. "Exact certification in global polynomial optimization via sums-of-squares of rational functions with rational coefficients". In: *Journal of Symbolic Computation* 47.1 (2012). Publisher: Elsevier, pp. 1-15. URL: https://www.sciencedirect.com/science/article/pii/S0747717111001143.

[22] Teresa Krick, Bernard Mourrain, and Agnes Szanto. "Univariate Rational Sums of Squares". In: *Revista de la Unión Matemática Argentina* 64.2 (2022), pp. 215-237.

[23] George Labahn, Vincent Neiger, and Wei Zhou. "Fast, deterministic computation of the Hermite normal form and determinant of a polynomial matrix". In: *Journal of Complexity* 42 (2017), pp. 44-71.

[24] Jean B. Lasserre. "Global Optimization with Polynomials and the Problem of Moments". In: *SIAM Journal on Optimization* 11.3 (2001), pp. 796-817. ISSN: 1052-6234, 1095-7189. DOI: 10.1137/S1052623400366802. URL: http://epubs.siam.org/doi/10.1137/S1052623400366802.

[25] Monique Laurent. "Semidefinite representations for finite varieties". In: *Mathematical programming* 109.1 (2007), pp. 1-26.

[26] Victor Magron and Mohab Safey El Din. "On exact Polya and Putinar's Representations". In: *Proc. Intl Symp. on Symbolic and Algebraic Computation (ISSAC)*. New York USA, 2018, pp. 279-286. ISBN: 978-1-4503-5550-6. DOI: 10.1145/3208976.3208986. URL: https://dl.acm.org/doi/10.1145/3208976.3208986.

[27] Victor Magron, Mohab Safey El Din, and Trung-Hieu Vu. "Sum of Squares Decompositions of Polynomials over their Gradient Ideals with Rational Coefficients". In: *SIAM Journal on Optimization* 33.1 (2023), pp. 63-88. ISSN: 1052-6234, 1095-7189. DOI: 10.1137/21M1436245. URL: https://epubs.siam.org/doi/10.1137/21M1436245.

[28] Victor Magron and Jie Wang. *Sparse Polynomial Optimization*. WORLD SCIENTIFIC (EUROPE), 2023. DOI: 10.1142/q0382. eprint: https://www.worldscientific.com/doi/pdf/10.1142/q0382. URL: https://www.worldscientific.com/doi/abs/10.1142/q0382.

[29] Angelos Mantzaflaris, Éric Schost, and Elias Tsigaridas. "Sparse rational univariate representation". In: *Proc. ACM on International Symposium on Symbolic and Algebraic Computation (ISSAC)*. 2017, pp. 301-308.

[30] Kurt Mehlhorn, Michael Sagraloff, and Pengming Wang. "From approximate factorization to root isolation with application to cylindrical algebraic decomposition". In: *Journal of Symbolic Computation* 66 (2015), pp. 34-69.

[31] Jiawang Nie. "Certifying convergence of Lasserre's hierarchy via flat truncation". In: *Mathematical Programming* 142.1 (2013), pp. 485-510.

[32] Jiawang Nie. *Moment and polynomial optimization*. SIAM, 2023.

[33] Jiawang Nie and Markus Schweighofer. "On the complexity of Putinar's Positivstellensatz". In: *Journal of Complexity* 23.1 (2007), pp. 135-150.

[34] Victor Pan and Elias Tsigaridas. "Nearly optimal computations with structured matrices". In: *Theoretical Computer Science* 681 (2017), pp. 117-137.

[35] Victor Y Pan and Elias P Tsigaridas. "Nearly optimal refinement of real roots of a univariate polynomial". In: *Journal of Symbolic Computation* 74 (2016), pp. 181-204.

[36] Pablo A Parrilo. "An explicit construction of distinguished representations of polynomials nonnegative over finite sets". In: *Preprint, ETH, Zürich* (2002).
[37] Pablo A. Parrilo. "Semidefinite programming relaxations for semialgebraic problems". In: *Mathematical Programming, Ser. B* 96.2 (2003), pp. 293-320.

[38] Helfried Peyrl and Pablo A. Parrilo. "Computing sum of squares decompositions with rational coefficients". In: *Theoretical Computer Science* 409.2 (2008). Elsevier, pp. 269-281. URL: https://www.sciencedirect.com/science/article/pii/S0304397508006452.

[39] Victoria Powers. *Certificates of Positivity for Real Polynomials*. Springer, 2021.

[40] Qazi Ibadur Rahman and Gerhard Schmeisser. *Analytic theory of polynomials*. 26. Oxford University Press, 2002.

[41] Fabrice Rouillier. "Solving zero-dimensional systems through the rational univariate representation". In: *Applicable Algebra in Engineering, Communication and Computing* 9.5 (1999), pp. 433-461.

[42] Markus Schweighofer. "On the complexity of Schmüdgen's Positivstellensatz". In: *Journal of Complexity* 20.4 (2004), pp. 529-543.
# A SOS decompositions and certificates

The following proposition provides bit complexity estimates for decomposing a nonnegative univariate polynomial with rational coefficients as a weighted sum of squares of polynomials.

**Proposition 4 ([4]).** Consider $A \in \mathbb{Z}[T]$ of size $(\delta, L)$ that is nonnegative over $\mathbb{R}$. A variant of the algorithm in [10], uSOS, computes a weighted SOS decomposition of $f$, that is $A(T) = \sum_{j=1}^{\nu} w_j s_j^2(T)$, where $\nu \le \delta+3$, $s_j \in \mathbb{Q}[T]$ and $w_j \in \mathbb{Q}_+$, for $j \in [\nu]$, in $\tilde{\mathcal{G}}_B(\delta^3 + \delta^2 L)$ bit operations. In addition, if $A$ is strictly positive, then $s_1 = 1$. The rational numbers involved in the decomposition have bitsize at most $\tilde{\mathcal{G}}(\delta^2 + \delta L)$ and the bitsize of the (whole) decomposition is $\tilde{\mathcal{G}}(\delta^3 + \delta^2 L)$.

Additionally, the following proposition provides bit complexity estimates for SOS certification of nonnegativity on an interval.

**Proposition 5 ([4]).** Let $A \in \mathbb{Z}[T]$ of size $(\delta, L)$ nonnegative over $[a, b] \subset \mathbb{R}$, with the bitsize of a and $b$ being at most $\sigma$.

A variant of the algorithm in [10], uSOS at an interval, computes a certificate of nonnegativity, that is, a weighted SOS like below,

$$A_{\phi} := (1 + Y^2)^d A \left( \frac{a + bY^2}{1 + Y^2} \right) = \sum_{j=1}^{n+3} w_j s_j^2(Y) \in \mathbb{Z}[Y],$$

on $[a, b]$ in $\tilde{\mathcal{G}}_B(\delta^3 + \delta^2 \sigma + \delta^2 L)$ bit operations. In addition, if $f$ is strictly positive, then $s_1 = 1$ and uSOS at an interval computes a certificate of strict positivity. The polynomials involved in the decomposition have bitsize at most $\tilde{\mathcal{G}}(\delta^2 + \delta L + \delta \sigma)$ and the bitsize of the (whole) decomposition is $\tilde{\mathcal{G}}(\delta^3 + \delta^2 L + \delta^2 \sigma)$.

# B Generic linear combinations of polynomials

In this appendix, we follow [9] to study the irreducible components of varieties defined by linear combinations of specific polynomials.

**Proposition 6.** Let $F := (f_1, \dots, f_r) \in \mathbb{Q}[x_1, \dots, x_n]^r$ and consider a matrix $A \in \mathbb{Q}^{r \times s}$ parameterizing the systems defined by $s$ linear combinations of the polynomials in $F$, that is $F \cdot A \in \mathbb{Q}[x_1, \dots, x_n]^s$. There is a Zariski open set $O \subset \mathbb{Q}^{r \times s}$ such that, for any matrix $A$ in this open set, every irreducible component of $\mathbb{V}_C(F \cdot A)$ not contained in $\mathbb{V}_C(F)$ has dimension $n-s$. Moreover, we can find a matrix $A \in O \cap \mathbb{Z}^{r \times s}$ where the entries have bitsize $O(n \lg d)$, where $d$ is an upper bound for the degrees of the polynomials in $F$.

*Proof.* The existence of the Zariski open set $O$ is proved as part of the proof of [9, Thm. 14]. Following their argument, we prove our preposition by induction on $s$. For $s=1$, the statement follows from Krull's principal ideal theorem. Assume that the proposition holds from $s=k$ and let $O_k \subset \mathbb{Q}^{r \times k}$ be the associated Zariski open set. Fix any $A \in O_k$ and let $V$ be an irreducible component of $\mathbb{V}_C(A \cdot F)$ not included in $\mathbb{V}_C(F)$ and let $P$ be its associated prime. By induction, the dimension of $V$ is $n-k$. For a fixed $\lambda \in \mathbb{Q}^r$, the intersection $V \cap \mathbb{V}_C(\sum_i \lambda_i f_i)$ will have dimension $n-k$ if and only if $\sum_i \lambda_i f_i = 0$ in $\mathbb{Q}[x_1, \dots, x_n]/P$. This follows from Krull's principal ideal theorem, as $\mathbb{Q}[x_1, \dots, x_n]/P$ is an integral domain. On the one hand, as $V$ is not an irreducible component of $\mathbb{V}_C(F)$, we have that for generic $\lambda$s, the dimension of the intersection is $n-k-1$. On the other hand, each irreducible component induces a hyperplane (of dimension $\le s-1$) for the values of
$\lambda \in \mathbb{Q}^r$ such that the intersection has dimension $n-k$. As there are at most $d^n$ of such irreducible components, we can find $\lambda \in \mathbb{Z}^s$ of bitsize $\mathcal{O}(n \lg d)$ such that the intersection of $V$ with $\mathbb{V}_C(\sum_i \lambda_i f_i)$ has dimension $n-k-1$, for every irreducible component $V \subset \mathbb{V}_C(A \cdot F)$, not in $\mathbb{V}_C(F)$. Therefore, every irreducible component of $\mathbb{V}_C(A \cdot F) \cap \mathbb{V}_C(\sum_i \lambda_i f_i)$ not in $\mathbb{V}_C(F)$ has dimension $n-k-1$. $\square$

## C Cofactors of sparse polynomials

In this appendix, we follow the notation from Thm. 4 and its proof. In the proof, when considering the sparse case, we claim that the polynomial $c_0$ and $B$ are coprime. In what follows, we prove this. Let $V$ be a generic subspace of the domain of $\text{Sylv}_F$ of dimension $E$. As every $R_i$ is coprime to $B$, there is a sparse polynomial $\bar{F}$ with the same Newton polytope as $F$ such that $\bar{F}(\frac{R_1}{R'_0}(t), \dots, \frac{R_n}{R'_0}(t)) \neq 0$ for every root in $t \in \mathbb{V}_C(B)$. As we proved in [5, Lem. 3.12], it follows from [12, Thm 1.8] that the map $\text{Sylv}_{\bar{F}}$ is surjective and keeps being surjective when we specialize $T=t$, for $t \in \mathbb{V}_C(B)$. Therefore, a generic subspace of the domain of this map of dimension $E$ satisfy that $(\text{Sylv}_F|_V)|_{T=t}$ is invertible for every $t \in \mathbb{V}_C(B)$. To construct such subspace $V$, for each $t \in \mathbb{V}_C(B)$, we need to consider a subspace $V_t$ with basis given by monomials and then take a generic-enough linear combination of these basis elements. By Schwartz-Zippel lemma, if we take the random linear combinations of bitsize $k \log(E)$, for a constant $k$, the probability of finding a $V$ with the wanted properties is upper bounded by $\frac{k-1}{k}$. Observe that, we can take $V$ to be its basis $\{(c_{i,j})_i\}_{j \le E}$ satisfies $(c_{i,1})_i = (1, 0, \dots, 0)$ and $c_{0,j} = 0$, for $j > 1$. This follows from $\mathbb{Q}(T)[\mathbf{X}]_{\hat{L}_i+\bar{\epsilon}}$ being a 1-dimensional $\mathbb{Q}(T)$-vector space and the system $(R'_0(T)X_i - R_i(T))_i$ having a solution on the torus $(\mathbb{Q}(T) \setminus 0)^n$.

Now, fix any monomial $\mathbf{X}^\alpha$ in the codomain of $\text{Sylv}_{\bar{F}}$. Then, by Cramer's rule, there are $c_0^{\bar{F}}(T), c_1^{\bar{F}}(X, T), \dots, c_n^{\bar{F}}(X, T) \in \mathbb{Q}[T]$ st

$$ \text{Sylv}_{\bar{F}}(c_0^{\bar{F},\alpha}(T), c_1^{\bar{F},\alpha}(X, T), \dots, c_n^{\bar{F},\alpha}(X, T)) = \det(\bar{M}_{\bar{F}}) \mathbf{X}^{\alpha} \\ = \bar{F} \left( \frac{R_1}{R'_0}(T), \dots, \frac{R_n}{R'_0}(T) \right) \cdot E(T), $$

for some non-zero $E(T) \in \mathbb{Q}[T]$, independent of the coefficients of $\bar{F}$. Also, the coefficients of $\{c_i^{\bar{F},\alpha}\}_i$ are given by minors of $\bar{M}_{\bar{F}}$.

Interestingly, as the restriction of the map $\text{Sylv}_{\bar{F}}|_{c_0=0}$ spans a vector space defined by binomial polynomials, no monomial belong to the image of this restricted map. This proves that $c_0^{\bar{F},\alpha}(T) \neq 0$. Moreover, for any $t \in \mathbb{V}_C(B)$, $c_0^{\bar{F},\alpha}(t) \neq 0$ as $\bar{M}_{\bar{F}}|_{T=t}$ is invertible and, as $R'_0(t) \neq 0, R_i \neq 0$, $\text{Sylv}_{\bar{F}}|_{c_0=0, T=t}$ is also spanned by monomials. Therefore, $B$ and $c_0^{\bar{F},\alpha}$ are coprime. Lastly, observe that $c_0^{\bar{F},\alpha}$ is independent of the coefficients of $\bar{F}$, in contrast to $c_i^{\bar{F},\alpha}$, for $i > 0$, which are polynomial in the coefficients of $\bar{F}$. To denote this independence, we drop the upper script $\bar{F}$ and only write $c_0^\alpha(T)$. Therefore, we can construct the identity,

$$ c_0^\alpha(T)^2 \bar{F}(\mathbf{X}) = - \sum_i c_0^\alpha(T) c_i^{\bar{F},\alpha}(\mathbf{X}, T) (R'_0(T)X_i - R_i(T)) \\ + c_0^\alpha(T) E(T) \bar{F} \left( \frac{R_1}{R'_0}(T), \dots, \frac{R_n}{R'_0}(T) \right) \mathbf{X}^\alpha $$

Once constructed $\bar{M}_{\bar{F}}$, this identity holds for any specialization of $\bar{F}$, in particular, we can consider $\bar{F} = F$.