Certificates of nonnegativity of multivariate polynomials with
zero-dimensional gradient ideal and infimum attained

Matías Bender *

Elias Tsigaridas †

Chaoping Zhu ‡

Abstract

We study the problem of certifying nonnegativity of multivariate polynomials with rational co-
efficients, under the assumptions that the polynomial attains its infimum and its gradient ideal is
zero-dimensional.

We introduce a new certificate, based on Rational Univariate Representations (RUR), that is both perfectly complete, it certifies every nonnegative polynomial, and perfectly sound, it correctly identifies any polynomial that is not nonnegative. The certificate reduces the problem to checking whether a univariate polynomial admits a weighted sum-of-squares decomposition modulo an ideal defined by the RUR, thereby avoiding the radicality assumption that limits other existing approaches. We present a Monte Carlo algorithm, SOS-RUR, that produces such a certificate or returns a rational witness point where the polynomial takes a negative value. For a polynomial in $n$ variables of degree $d$ and maximum coefficient bitsize $\tau$, SOS-RUR runs in bit complexity $\tilde{O}_B(e^{\omega n+O(\lg n)} d^{(\omega+2)n}(d+\tau))$, and the polynomials in the certificate have coefficients of bitsize at most $\tilde{O}(d^{2n+1}(d+n\tau))$, when we ignore polylogarithmic factors. If the polynomial can take negative values, then the algorithm outputs a rational witness point with coordinates of bitsize $\tilde{O}(nd^{2n+2}(d+n\tau))$. In the special case where the gradient ideal is radical, in addition to the improvement in the bit size, our certificate specializes in a representation with improved degree bounds, better by an additive factor of $d$, and lower bit complexity compared to previous results, together with an explicit validation of the RUR, which had previously been overlooked.

We also consider sparse certificates, that their structure, complexity, and (bitsize) bounds depend on the Newton polytope $Q$ of the input polynomial and not on the total degree $d$. To compute them, we rely on a Monte Carlo algorithm to obtain a sparse RUR for unmixed systems, which is of independent interest. In particular, we compute the sparse certificate in $\tilde{O}_B(n^{6n} \mathrm{vol}(Q)^6 \tau)$ bit operations, where $\mathrm{vol}(Q)$ is the volume of $Q$. The certificate involves sparse polynomials of degree at most $2^{n+2} n!^2 \mathrm{vol}(Q)^2$ and coefficient bitsize $\tilde{O}(n^{4n} \mathrm{vol}(Q)^4 \tau)$. These bounds provide sharper guaranties in the presence of sparsity, as they are input sensitive. This result contributes to the ongoing effort to encode polynomial optimization problems through compact descriptions, in our case by exploiting the sparsity of the input, thereby extending the current frontier of tractability from a computational point of view.

Overall, our results extend the scope of certificates modulo the gradient ideal by eliminating
the radicality requirement, introduce a variant that exploits the sparsity of the input polynomial,
improve existing bitsize complexity bounds by at least a factor of $d^n$, and provide efficient, verifiable
algebraic certificates of nonnegativity for polynomial optimization.

<footnote>*Inria Saclay and CMAP, École Polytechnique, IP Paris, France</footnote>

<footnote>†Inria Paris and IMJ-PRG, Sorbonne Université, France</footnote>

<footnote>‡Inria Paris and IMJ-PRG, Sorbonne Université, France</footnote>
# Contents

<table><tr><td>1</td><td>Introduction</td><td>3</td></tr><tr><td>2</td><td>Algebraic preliminaries and RUR computation</td><td>7</td></tr><tr><td>2.1</td><td>Zero-dimensional ideals and (Sparse) Rational Univariate Representations (RUR)</td><td>8</td></tr><tr><td>2.2</td><td>Polynomial multiplication and bitsizes</td><td>8</td></tr><tr><td>2.3</td><td>SRUR of umixed systems and its bit complexity</td><td>9</td></tr><tr><td>2.4</td><td>Sparse versions of Nullstellensatz</td><td>13</td></tr><tr><td>2.5</td><td>Univariate SOS decompositions and certificates</td><td>14</td></tr><tr><td>3</td><td>SOS decomposition à la RUR (SOS-RUR)</td><td>14</td></tr><tr><td>3.1</td><td>(Sub)algorithms and bit complexity bounds: the dense case</td><td>15</td></tr><tr><td>3.2</td><td>Overall complexity of SOS-RUR</td><td>18</td></tr><tr><td>3.3</td><td>Sparse certificates of nonnegativity</td><td>19</td></tr><tr><td>3.4</td><td>The case of a radical gradient ideal</td><td>22</td></tr><tr><td>4</td><td>Validation (of the correctness) of the certificate</td><td>23</td></tr><tr><td>5</td><td>Experimental evaluation</td><td>27</td></tr><tr><td>6</td><td>Conclusions and perspectives</td><td>29</td></tr></table>
# 1 Introduction

We consider certificates of nonnegativity for a polynomial $f \in \mathbb{Q}[\mathbf{X}] := \mathbb{Q}[X_1, \dots, X_n]$ of even degree $d$, that is, certificates verifying whether $f$ is nonnegative as a function on $\mathbb{R}^n$. We assume that $f$ attains its infimum on $\mathbb{R}^n$ and that the complex variety defined by its gradient ideal $I_{\nabla f}$—the ideal generated by the partial derivatives of $f$—is zero-dimensional. Following the framework of Powers [Pow21], a certificate consists of one or more “simple” algebraic identities that imply the nonnegativity of $f$. These identities serve as a means to verify the output of an algorithm that determines whether $f$ is nonnegative. Furthermore, the construction and verification of such certificates must take into account the maximum bitsize of the coefficients of $f$, both in the polynomials involved and in the corresponding algorithms.

Certificates of nonnegativity naturally raise the following mathematical, algorithmic, and complexity related questions:

(Q$_0$) What is the mathematical framework—typically a theorem—that implies the existence of one or more algebraic identities corresponding to the certificate?

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

(Q$_2$) What is the (bit) size of (the numbers involved in) the certificate?

(Q$_3$) What is the (bit) complexity of verifying the algebraic identity induced by the certificate; that is, the complexity of checking its correctness?

(Q$_4$) If no certificate exists, that is, if $f$ can take negative values, can we compute a witness point where $f$ evaluates to a negative number? What is the cost of computing such a witness and what is the bitsize of its coordinates?

We emphasize the connection between certificates of nonnegativity (and the associated questions on verification) and the framework of interactive proof systems [GMR19; BM88]. In particular, our work is closely related to recent developments in certifying algorithms in linear algebra, see [DK14] and subsequent works, as well as in optimization [Kal+12]. We construct certificates of nonnegativity that provide definitive answers to the questions listed above. These certificates are *perfectly complete*, they always certify a nonnegative polynomial, and *perfectly sound*, they correctly reject any polynomial that is not nonnegative. These properties hold under the assumptions that the infimum of the polynomial is attained and the gradient ideal is zero-dimensional. For an illuminating exposition of the notions of completeness and soundness in this context, we refer the reader to the introduction of [DK14].

**Previous and related works** The base case for nonnegativity certificates concerns univariate polynomials. Over $\mathbb{R}$, every nonnegative univariate polynomial is a sum of two squares. On the other hand, if $f \in \mathbb{Z}[X]$ is a univariate polynomial with integer coefficients that is nonnegative over $\mathbb{R}$, then there exists a weighted sum-of-squares (SOS) decomposition over $\mathbb{Q}$ of the form

$$f(X) = \sum_{j=1}^{\nu} w_j s_j^2(X),$$

where $s_j \in \mathbb{Q}[X]$, $w_j \in \mathbb{Q}_+$ for $j \in [\nu]$, and $\nu \le 5$ [Lan06; Pou71]. Unfortunately, this result is not constructive, although there has been significant recent progress [KMV23]. Fortunately, constructive alternatives exist [Sch99; Che+11], albeit at the cost of increasing the number of summands to $\nu \le \deg(f) + 3$. Univariate SOS decompositions are useful in our context and we employ them via a recent algorithmic and complexity improvement (Prop. 2.20). Specifically, for a nonnegative univariate polynomial $f$ of degree $\delta$ and coefficient bitsize $L$, a recent variant of the algorithm by Chevillard, Harrison, Joldeş, and Lauter [Che+11], which we refer to as uSOS [BDT25], computes a weighted SOS decomposition in $\tilde{O}_B(\delta^3 + \delta^2 L)$ bit operations. The rational numbers involved in the decomposition have bitsize at most $\tilde{O}(\delta^2 + \delta L)$; see Prop. 2.20 and [BDT25] for further details.

Certificates for multivariate polynomials are significantly more involved. The most general such certificate is the Positivstellensatz of Artin [Art27], which states that every polynomial that is nonnegative over $\mathbb{R}^n$ has a representation as a sum of squares of rational functions. Although Lombardi, Perrucci, and Roy [LPR20] proposed an algorithm to realize Artin’s theorem, the degree bounds for the resulting representation are highly pessimistic, forming a tower of five exponents; hence, they are not practically
useful. This motivates the research for more efficient or more structured certificates under reasonable theoretical and/or practical assumptions.

A central approach is to investigate the structural properties of the *gradient ideal* of a polynomial and to study the nonnegativity of the polynomial modulo this ideal. The *gradient ideal* of *f* is

$$I_{\nabla f} := \langle \partial_1 f, \dots, \partial_n f \rangle \subseteq \mathbb{R}[\mathbf{X}],$$

that is, the ideal generated by the partial derivatives of $f$. The corresponding *gradient variety* is $V_C(I_{\nabla f}) \subseteq \mathbb{C}^n$; its elements are precisely the *critical points* of $f$. If $f$ attains its infimum over $\mathbb{R}^n$, then this infimum is necessarily realized at a critical point.

We assume throughout that the *gradient ideal* $I_{\nabla f}$ is zero-dimensional, meaning that $V_C(I_{\nabla f})$ is a finite set, or equivalently, that the quotient ring $\mathbb{R}[\mathbf{X}]/I_{\nabla f}$ is a finite-dimensional $\mathbb{R}$-vector space. Parillo [Par02] introduced a constructive SOS certificate in the more general setting where $f$ is nonnegative over a finite set of points described by a radical ideal. This generalizes a result by Lasserre [Las02], which handles nonnegativity over a Cartesian grid in $\mathbb{R}^n$. Building on (and extending) this framework, Nie, Demmel, and Sturmfels [NDS06] showed that a polynomial $f \in \mathbb{R}[\mathbf{X}]$ is nonnegative on its gradient variety $V_\mathbb{R}(I_{\nabla f})$ if and only if $f$ is a sum of squares modulo the radical ideal $\sqrt{(I_{\nabla f})}$.

This line of work leads naturally to the following certificate:

(C-rad-0) Assumptions: $\exists \min f, \dim V_C(I_{\nabla f}) = 0, I_{\nabla f}$ is radical

$$f \ge 0 \text{ on } \mathbb{R}^n \Leftrightarrow f = \text{SOS} \mod I_{\nabla f}.$$

When $f \in \mathbb{Q}[\mathbf{X}]$ has degree $d$ and maximum coefficient bitsize $\tau$, Magron, Safey El Din, and Vu [MSEDV23], presented an algorithm to realize the certificate (C-rad-0). Under the additional gener- icity assumption on $I_{\nabla f}$, that all the points have a different $X_1$ coordinate, that is satisfied if we perform a generic linear change of coordinates, they exploit a rational parametrization of the points in $V(I_{\nabla f})$. They compute a representation $V(I_{\nabla f}) = \{x \in \mathbb{C}^n | w(x_1) = 0, x_2 = \frac{\kappa_2(x_1)}{w'(x_1)}, \dots, x_n = \frac{\kappa_n(x_n)}{w'(x_1)}\}$, where $w, \kappa_1, \dots, \kappa_n$ are univariate polynomials. Subsequently, they decompose $f$ as an SOS of rational func- tions, by considering the quotients and remainder of the division of $(w')^d f$ with $[X_2 - \frac{\kappa_2}{w'}, \dots, X_n - \frac{\kappa_n}{w'}]$ [MSEDV23, Thm. 4.1 and Alg. 4.1]. Thus, they decompose $f$ as

$$f = \frac{1}{(w')^d} r + \sum_{i=2}^{n} (X_i - \frac{\kappa_i}{w'}) \phi_i, \quad (1)$$

where $r \in \mathbb{Z}[X_1]$ is a univariate polynomial corresponding to the remainder of $(w')^d f$ modulo the polynomials $\{w'X_2 - \kappa_2, \dots, w'X_n - \kappa_n\}$, and $w'$ is the derivative of $w$. If $f$ is nonnegative, then $r$ is nonnegative and, since it is a univariate polynomial, we can write it as a (weighted) SOS of polynomial [Che+11; MSED519]. This leads to the decomposition

$$f = \frac{1}{(w')^d} \sum_{j=1}^{s} c_j q_j^2 + \sum_{i=2}^{n} (X_i - \frac{\kappa_i}{w'}) \phi_i, \quad (2)$$

where $w, \kappa_i, q_j \in \mathbb{Z}[X_1]$, $\phi_i \in \mathbb{Z}[\mathbf{X}]$, and $c_i \in \mathbb{Q}_+$, for $i \in [n]$ and $j \in [s]$. Hence, we write $f$ as an SOS of rational functions modulo $\langle w'X_2 - \kappa_2, \dots, w'X_n - \kappa_n \rangle$, which is a subset of $I_{\nabla f}$ when the gradient ideal is radical. The maximum bitsize of the coefficients of the polynomials that appear in this decomposition is $\tilde{O}((\tau + n + d)d^{3n+3})$ [MSEDV23, Thm. 4.5] and the complexity of the algorithm is $\tilde{O}_B((\tau + n + d)d^{4n+4})$ [MSEDV23, Thm. 4.6]. Also, the remainder $r$ has degree at most $d(d-1)^n$ and so the polynomials $q_j$'s have degree at most $d(d-1)^n/2$.

In this line of research, the most recent contribution is by Baldi, Krick, and Mourrain [BKM24], for the more general problem of $f$ being nonnegative over a finite semi-algebraic set. They do not require $I_{\nabla f}$ to be radical, but they need the condition $\langle f \rangle + \langle I_{\nabla f} : f \rangle = 1$. This condition is always satisfied when $I_{\nabla f}$ is radical. Their degree and bitsize bounds depend, among others on the Castelnuovo-Mumford regularity of the ideal $I_{\nabla f}$ [BKM24, Theorem A and C]. The specialization of their results to our case lead to a maximum bitsize of $\tilde{O}_B((\tau + n + d)d^{dn+4})$ [BKM24, Theorem C] for the coefficients of their certificate. For another recent related work for polynomials over $\mathbb{R}[\mathbf{X}]$ we refer to [HQ25]. Based on our tools and on the work of [BKM24] and [KMS22] we present a not-very-detailed and non-optimal approach of the semi-algebraic case in Section 6. We postpone the presentation of a new approach for a future communication.
Unfortunately, the theorem supporting (C-rad-0) does not allows us to get rid of the radicality assumption, as the following example indicates.

**Example 1.1 ([NDS06]).** Let $f = x^8 + y^8 + z^8 + M$, where $M = x^4y^2 + x^2y^4 + x^6 - 3x^2y^2z^2$ is the Motzkin form. It is nonnegative over $\mathbb{R}^3$, thus over $\mathbb{V}_{\mathbb{R}}(I_{\nabla f})$, but it is not a sum of squares modulo $I_{\nabla f}$. Indeed, one can verify that $f - M/4 \in I_{\nabla f}$ and that $M$ is not a sum of squares modulo $I_{\nabla f}$.

Therefore, we need another certificate to work with nonnegative polynomials having nonradical gradient ideal. Even more, (C-rad-0) and the algorithms that realize it, e.g., [MSEDV23, Alg. 4.1], implicitly require that we already have, or we are able to compute, a correct representation of the gradient ideal. If this is not the case, for example if our Gröbner basis or rational univariate representation corresponds to an ideal which does not include all the points in $\mathbb{V}(I_{\nabla f})$, then we might still be able to write our polynomial as a sum of squares modulo this new ideal. However, this provides a fake certificate of positivity, since the polynomial may nonetheless evaluate to negative values. The following example illustrates this situation.

**Example 1.2.** Assume $f(X_1, X_2) = X_1^4 - 6X_1^3 + 12X_1^2 + 2X_1X_2 + X_2^2 - 6X_1$. The gradient ideal of $f$ is $I_{\nabla f} = \langle 4X_1^3 - 18X_1^2 + 24X_1 + 2X_2 - 6, 2X_1 + 2X_2 \rangle$ and it is radical. The gradient variety is zero dimensional and it contains three critical points. A parametrization is $\mathbb{V}(I_{\nabla f}) = \{(X_1, X_2) \in \mathbb{C}^2 | (2X_1 - 3)(X_1^2 - 3X_1 + 1) = 0, X_1 + X_2 = 0\}$, and the points are $\{(\frac{3}{2}, -\frac{3}{2}), (\alpha_1, -\alpha_1), (\alpha_2, -\alpha_2)\}$, where $\alpha_i$ are the two real roots of $X_1^2 - 3X_1 + 1$.

Assume that we are given, or we compute, a wrong parametrization of the gradient variety, for example $\{2X_1 - 3 = 0, -X_1 + X_2 + 3 = 0\}$; hence, we are missing two points $\{(\alpha_1, -\alpha_1), (\alpha_2, -\alpha_2)\}$. Then, with this wrong parametrization at hand, we represent $f$ as

$$f = (X_1^2 - 3X_1 + 3)^2 + (3X_1 + X_2 - 3)(-X_1 + X_2 + 3) + 0 \cdot (2X_1 - 3).$$

The remainder $r = (X_1^2 - 3X_1 + 3)^2$ is a positive univariate polynomial, as it is already a square, which leads us to conclude that $f$ is nonnegative. However, $f$ can be negative; $f(\frac{1}{2}, -\frac{1}{2}) = -\frac{15}{16} < 0$.

Even more, the wrong parametrization $\{2X_1 - 3 = 0, 3 - X_1 + X_2 = 0\}$ is a Gröbner basis and contains the gradient ideal of $f$. Hence, it is not straightforward to figure out that this is not the correct parametrization.

As the previous example illustrates, perfect completeness and perfect soundness require certification that the chosen representation of the gradient ideal is correct. Verifying that this representation indeed encodes all points of the gradient ideal incurs a non-negligible computational cost; nevertheless, this step is unavoidable.

**Our contribution** We present a certificate of positivity over $\mathbb{R}^n$ for a polynomial $f$, when its gradient ideal is zero-dimensional and attains its infimum (or, in other words, it has a minimum); we do not assume that the gradient ideal is radical. The certificate is perfectly complete and perfectly sound. The bound on the bitsize of the polynomials of the certificate improves all the previous estimates by at least a factor of $d^n$. This improvement together with recent advancement on the SOS representation of univariate polynomials, Prop. 2.20 and [BDT25], leads to an algorithm with improved bit complexity bound, even in the case of radical zero-dimensional gradient ideals. Besides the dense case, we also consider a sparse version of the certificate that depends on the (volume of the) Newton polytope of $f$. This result contributes to the ongoing effort to encode polynomial optimization problems by exploiting the sparsity and structure of the input, e.g., [MW23].

**Certificate of positivity** We consider a nonnegative $f \in \mathbb{Q}[\mathbf{X}]$ with rational coefficients, of even degree $d$, and (maximum coefficient) bitsize $\tau$. We denote a rational univariate representation (RUR), Def. 2.2, of the variety of its gradient ideal $I_{\nabla f}$ (Def. 2.1) as $\text{RUR}(I_{\nabla f}) = (R_0(T), R_1(T), \dots, R_n(T), T - \sum_{i=1}^n \lambda_i X_i)$, where $T$ is a new variable, $R_0$ is square-free, $\lambda_i \in \mathbb{Q}$, and $T - \sum_{i=1}^n \lambda_i X_i$ is a separating linear form on $\mathbb{V}(I_{\nabla f})$. The parametrization of the points in the gradient variety is $\mathbb{V}(I_{\nabla f}) = \{\mathbf{x} \in \mathbb{C}^n | x_i = \frac{R_i(t)}{R_0'(t)}, i \in [n], R_0(t) = 0, t \in \mathbb{C}\}$. We also need the ideal $I_{\text{RUR}(\nabla f)} := \langle R_0'(T)X_1 - R_1(T), \dots, R_0'(T)X_n - R_n(T) \rangle \subseteq \mathbb{Q}[\mathbf{X}, T]$ (Def. 3.1).

We answer the questions required by certificates (of positivity) as follows:
(Answering $Q_0$) The following theorem (see Thm. 3.2 for further details) implies an algebraic identity corresponding to a certificate of nonnegativity of $f$:

**Theorem.** A polynomial $f \in \mathbb{Z}[\mathbf{X}]$, of degree $d$ and maximum coefficient bitsize $\tau$, that attains its infimum and has zero dimensional gradient ideal, is nonnegative over $\mathbb{R}^n$ if and only if we can decompose $(R'_0)^d f$ as an SOS of polynomials modulo the ideal $I_{\text{RUR}(\nabla f)} \subseteq \mathbb{Q}[\mathbf{X}, T]$, that is

$$ (R'_0)^d f = r + \sum_{i=1}^{n} (R'_0 X_i - R_i)q_i = \sum_{j=1}^{\nu} w_j s_j^2 + \sum_{i=1}^{n} (R'_0 X_i - R_i)q_i, \quad (3) $$

where $r, s_j \in \mathbb{Q}[T]$, $w_j \in \mathbb{Q}_+$, for $j \in [\nu]$, and $q_i \in \mathbb{Q}[T, \mathbf{X}]$, for $i \in [n]$.

The certificate is

(C-RUR) Assumptions: $\exists \min f, \dim \mathbb{V}(I_{\nabla f}) = 0$

$$ f \ge 0 \text{ on } \mathbb{R}^n \Leftrightarrow (R'_0)^d f = \text{SOS} \mod \langle R'_0 X_1 - R_1, \dots, R'_0 X_n - R_n \rangle $$

The certificate consists in validating the algebraic identity of Eq. (3) and, in addition, in validating that $\text{RUR}(I_{\nabla f}) = (R_0(T), R_1(T), \dots, R_n(T), T - \sum_{i=1}^n \lambda_i X_i)$ parametrizes all the points of $\mathbb{V}(I_{\nabla f})$. We dedicate Section 4 to this procedure.

(Answering $Q_1$) Algorithm SOS-RUR (Alg. 1) computes the decomposition supported by Thm. 3.2 corresponding to (C-RUR) in $\tilde{\mathcal{O}}_B(e^{\omega n+\mathcal{O}(\lg n)}d^{(\omega+2)n}(d+\tau))$ bit operations, where $\omega$ is the exponent of matrix multiplication (Thm. 3.9).

(Answering $Q_2$) The polynomials involved in the decomposition have degree at most $d(d-1)^n$, while their largest coefficient, and hence the largest coefficient in the certificate, has bitsize $\tilde{\mathcal{O}}(d^{2n+1}(d+n\tau))$. The total bitsize of the decomposition is $\tilde{\mathcal{O}}(d^{3n+2}(d+n\tau))$ (Thm. 3.9, Lem. 3.6, and Lem. 3.7).

(Answering $Q_3$) Algorithm Is-the-RUR-sufficient (Alg. 2), based on Cor. 4.4, validates the RUR of $\mathbb{V}(I_{\nabla f})$, the separating linear form, and the quotients in the representation of Eq. (3). The maximum bitsize of the numbers involved in validating the RUR is $\tilde{\mathcal{O}}(n^{4n}d^{4n\tau})$ (Thm. 4.5 and Rem. 4.6).

(Answering $Q_4$) If $f$ can be negative, then SOS-RUR (Alg. 1) computes a point $\mathbf{x} \in \mathbb{Q}^n$ (witness point) such that $f(\mathbf{x}) < 0$; the coordinates of $\mathbf{x}$ have bitsize $\tilde{\mathcal{O}}(nd^{2n+2}(d+n\tau))$ (Lem. 3.8).

The special case of $I_{\nabla f}$ being radical If we consider the specialization of our results in the case where the gradient ideal is radical (Sec. 3.4), then our SOS representation is similar to the one in [MSEDV23], where they also exploit the RUR. Compared to the latter approach, besides the improved bit complexity estimates of the corresponding algorithms and certification of the RUR, the degrees of the polynomials involved in our representation are always better by an additive factor of $d$. We dedicate Sec. 3.4 on this special case and we illustrate the improvements with an example based on Scheiderer's polynomial.

## Sparse certificates

We also consider the case of providing certificates of positivity for a sparse multivariate polynomial $f$ (Sec. 3.3), where we exploit sparsity through the Newton polytope of $f$, say $Q$.

The following lemma (we refer to Lem. 3.12 for a detailed presentation) implies an algebraic identity corresponding to a certificate of nonnegativity of $f$, where the sparsity and the degree of the involved polynomials depend on the Newton polytope of $f$.

**Lemma.** Let $f \in \mathbb{Z}[\mathbf{X}]$ be of degree $d$ and bitsize $\tau$, $Q \subset \mathbb{R}^n$ be its Newton polytope, and assume Vertices($Q$) $\subset (2 \cdot \mathbb{Z})^n$. There are sparse polynomials $q_1, \dots, q_r \in \mathbb{Z}[T][\mathbf{X}]$ with supports depending on $Q$ and an exponent $2\alpha \in Q$ such that,

$$ G(T)^2 f(\mathbf{X}) = \sum_i q_i(\mathbf{X}, T) (R'_0(T)X_i - R_i(T)) + (\mathbf{X}^\alpha)^2 r(T). $$

Moreover, $G$, $r$, and the coefficients of each $q_i$ in $\mathbb{Z}[T]$<fnref n="1" /> have degree at most $2^{n+2} n!^2 \text{vol}(Q)^2$ and bitsize $\tilde{\mathcal{O}}(2^n (n+1)!^2 \text{vol}(Q)^2 (n+\tau))$, where $\text{vol}(Q)$ is the volume of $Q$.

<footnote n="1">¹we consider them as sparse polynomials in $\mathbf{X}$ with coefficients in $\mathbb{Z}[T]$</footnote>
Similarly to the dense case, we answer all the questions related to the (sparse) certificate and the precise bit complexity bounds and bitsizes depend on the (volume of the) Newton polytope of $f$ (Thm. 3.16).

**Bit complexity of computing the RUR** On our way to support the complexity of the certificate and SOS-RUR, we present a Monte Carlo algorithm, based on resultant computations, see also [MST17], to compute the RUR of a zero-dimensional system of polynomials having the same Newton polytope, say $Q$; this is the case of unmixed polynomial systems. The bit complexity of the algorithm and the sizes of the polynomials in the RUR depend on (the volume of) $Q$. This is a result of independent interest. In particular, the bit complexity of computing the RUR is $\tilde{O}_B(\frac{n^{(3\omega+2)n+O(1)}}{e^{(\omega+2)n}} \mathrm{vol}(Q)^{\omega+2}\tau)$, while the size of the polynomials in the RUR is $(n!\mathrm{vol}(Q), \tilde{O}_B((n+1)!\mathrm{vol}(Q)(n+\tau))$, (Theorem 2.12), where $n$ is the number of variables and $\tau$ the maximum coefficient bitsize.

In the case of dense polynomial systems, where all the polynomials have the same degree $d$ and bitsize $\tau$, we compute the RUR in $\tilde{O}_B(e^{\omega n+O(\lg n)}d^{(\omega+2)n}(n+\tau))$ bit operations, while the size of its polynomials is $(d^n, \tilde{O}_B(d^n+nd^{n-1}(\tau+n)))$ (Cor. 2.15).

If the system has no solutions at infinity, then the exponent of $\mathrm{vol}(Q)$ in the sparse case and the exponent of $d$, in the dense case, reduces by one; that is, they become $\mathrm{vol}(Q)^{(\omega+1)n}$ and $d^{(\omega+1)n}$, respectively (Rem. 2.17).

**Notations** Let $\mathbb{K}$ be a field and consider the variables $X_1, \dots, X_n$ variables; we use $\mathbf{X}$ for $(X_1, \dots, X_n)$. We denote by $\mathbb{K}[\mathbf{X}]$ the polynomial ring in the variables $X_1, \dots, X_n$ with coefficients in $\mathbb{K}$. Our focus is on the cases where $\mathbb{K}$ is either the field of rationals, real, and complex numbers, or the field of rational functions $\mathbb{K} = \mathbb{C}(\mathbf{X})$. We denote by $\bar{\mathbb{K}}$ the algebraic closure of the field $\mathbb{K}$. We also use $\mathbb{Q}_+$ and $\mathbb{R}_+$ for nonnegative rationals and real numbers respectively. For a set of polynomials $g_1, \dots, g_r \in \mathbb{K}[\mathbf{X}]$, we denote by $\langle g_1, \dots, g_r \rangle$ the ideal that they generate.

Given integer polytopes $Q$ and $Q'$, we denote by $Q \oplus Q'$ its Minkowski sum. Moreover, given a positive integer $k$, we denote by $k \cdot Q$ the Minkowski sum $\sum_{i=1}^k Q$.

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. If $a \in \mathbb{Z}$, then its bitsize is the length of its binary representation, including a bit for sign; if $a \in \mathbb{Q}$, then its bitsize is the maximum bitsize of the numerator and the denominator. For a (multivariate) polynomial $A \in \mathbb{Q}[\mathbf{X}]$, its bitsize is the maximum bitsize of all its coefficients. We say that a polynomial $A \in \mathbb{Q}[\mathbf{X}]$ has size $(d, \tau)$, if its (total) degree is $d$ and its bitsize is $\tau$. If $A \in \mathbb{Z}[\mathbf{X}]$, then we also write $H(A)$ for the maximum absolute value of the integer coefficients of $A$; this the (absolute) height of $A$ and it holds $\mathcal{H}(A) = \lg H(A) + 1$. Finally, we use the abbreviation $[n] = \{1, \dots, n\}$, for a positive integer $n$.

**Organization** Sec. 2 introduces various algebraic preliminaries that we need for our study. Also it presents the algorithm (and its complexity) for computing the RUR of a zero-dimensional polynomial system. Sec. 3 presents the certificate, the algorithm, SOS-RUR, as well their complexity analysis. Finally, in Sec. 4 we present the theory and the algorithms to validate the RUR. In Sec. 5 we present some preliminary experiments of our implementation of the various algorithms in MAPLE. In Sec. 6 we summarize our results and we sketch an extension of our approach to the semi-algebraic case.

## 2 Algebraic preliminaries and RUR computation

We present some results from (computational) algebraic geometry that are useful in our study.

An ideal $I \subseteq \mathbb{K}[\mathbf{X}]$ is radical if, for every polynomial $f \in \mathbb{K}[\mathbf{X}]$ and some $k \in \mathbb{N}$ such that $f^k \in I$, then $f \in I$. For an ideal $I \subset \mathbb{R}[\mathbf{X}]$, we denote its associated complex algebraic variety by

$$V_{\mathbb{C}}(I) := \{x \in \mathbb{C}^n : \forall g \in I, g(x) = 0\}.$$

We denote by $V_{\mathbb{R}}(I)$ its real part, i.e., $V_{\mathbb{R}}(I) = V_{\mathbb{C}}(I) \cap \mathbb{R}^n$. When we omit the subscript, then we refer to the complex variety. If $V_{\mathbb{C}}(I)$ contains only a finite number of points, then we say that $I$ is a zero-dimensional ideal. Let $V \subseteq \mathbb{K}^n$, we define the ideal of all polynomials vanishing on $V$ as:

$$I(V) := \{f \in \mathbb{K}[\mathbf{X}] | f(x) = 0, \forall x \in V\}.$$
Hilbert's Nullstellensatz relates varieties and ideals. Given an ideal $I \subseteq \mathbb{R}[\mathbf{X}]$, $I(\mathbb{V}_C(I)) = \sqrt{I}$. In particular, if $\mathbb{V}_C(I)$ is empty, then $1 \in I$.

**Definition 2.1** (Gradient ideal and gradient variety). Given $f \in \mathbb{R}[\mathbf{X}]$, its gradient ideal, $I_{\nabla f}$, is the ideal generated by its partial derivatives, that is, $I_{\nabla f} := \langle \partial_1 f, \dots, \partial_n f \rangle$, where $\partial_i f$ is the derivative of $f$ with respect to $X_i$. The variety $\mathbb{V}(I_{\nabla f})$, that we call gradient variety, contains the critical points of $f$.

## 2.1 Zero-dimensional ideals and (Sparse) Rational Univariate Representations (RUR)

Let $I \subset \mathbb{Q}[\mathbf{X}]$ be a 0-dimensional ideal; then, the corresponding variety, $\mathbb{V}(I) \subseteq \mathbb{C}^n$, is a finite set of points. Even more, there is a (rational) parameterization of these points [Rou98; Alo+96]; we call it Rational Univariate Representation (RUR) [Rou98].

The RUR depends on a separating linear form $L \in \mathbb{Q}[\mathbf{X}]$ on $\mathbb{V}(I_{\nabla f})$. We call it separating linear form, because we require that $L$ is such that, for every $\alpha, \beta \in \mathbb{V}_C(I)$ with $\alpha \neq \beta$, to have $L(\alpha) \neq L(\beta)$.

Our presentation is a simplified version of the approach of Rouillier [Rou98], as we do not need to take into account the multiplicities of the solutions.

**Definition 2.2** (RUR). Consider a zero-dimensional ideal $I \subseteq \mathbb{Q}[\mathbf{X}]$ and a separating linear form $L \in \mathbb{Q}[\mathbf{X}]$ on $\mathbb{V}(I)$. A RUR of $\mathbb{V}(I)^2$ is a tuple of univariate polynomials $R_0(T), R_1(T), \dots, R_n(T) \in \mathbb{Q}[T]$, where $T$ is a new variable, such that

$$ \mathbb{V}_C(I) = \left\{ \left( \frac{R_1(t)}{R'_0(t)}, \frac{R_2(t)}{R'_0(t)}, \dots, \frac{R_n(t)}{R'_0(t)} \right) : t \in \mathbb{C} \text{ and } R_0(t) = 0 \right\}, $$

where $R_0$ is square-free, $R'_0$ is its derivative with respect to $T$, and the degree of each $R_i$ for each $i > 1$, is smaller than the one of $R_0$. Also, it holds $t = L(\frac{R_1(t)}{R'_0(t)}, \dots, \frac{R_n(t)}{R'_0(t)})$, for every root $t \in \mathbb{C}$ of $R_0(T)$. We denote this representation as $\text{RUR}(I) = ((R_0(T), R_1(T), \dots, R_n(T)), T - L(\mathbf{X}))$.

**Remark 2.3.** In Def. 2.2, the condition $t = L(\frac{R_1}{R'_0}(t), \dots, \frac{R_n}{R'_0}(t))$ on the linear form $L$ forces $L$ to be separating over $\mathbb{V}(I)$.

Rouillier [Rou98] studied in detail the efficient theoretical and practical complexity of RUR. For the most recent developments in this line of research we refer the reader to [DRR24].

In many cases, it is important to take into account the sparsity of the input polynomials. For this we rely on a variant of RUR, that is called Sparse Rational Univariate Representation (SRUR) [MST17]. The sparsity structure, through the use of Newton polytopes, allows us to compute and estimate the size of polynomials in RUR based on sparse resultant computations and also to bound the degree and bitsize in RUR using (the volume of) the Newton polytope(s). In Section 2.3 we present a brief introduction to sparse polynomials and also an algorithm (and its precise bit complexity analysis) for computing the RUR and its sparse variant (SRUR). We refer the interested reader to [GKZ94] for further details regarding sparsity in algebraic geometry and to [EMT20; MST17] for algorithms and various relevant bitsize estimates.

## 2.2 Polynomial multiplication and bitsizes

For various proof and bounds, we need the following result(s) on multivariate polynomial multiplication. For the rather straightforward proofs we refer the reader to [MST17].

**Lemma 2.4** (Bitsize bounds for polynomial multiplication). The following bounds hold:

(i) Consider two multivariate polynomials, $f_1$ and $f_2$, in $\nu$ variables of total degrees $\delta$, having bitsize $\tau_1$ and $\tau_2$, respectively. Then $f = f_1 f_2$ is a polynomial in $\nu$ variables, of total degree $2\delta$ and bitsize $\tau_1 + \tau_2 + 2\nu \lg(\delta)$.

(ii) Using induction, the product of $m$ polynomials in $\nu$ variables, $f = \prod_{i=1}^m f_i$, each of total degree $\delta_i$ and bitsize $\tau_i$, is a polynomial of total degree $\sum_{i=1}^m \delta_i$ and bitsize $\sum_{i=1}^m \tau_i + 12\nu m \lg(\sum_{i=1}^m \delta_i)$.

(iii) Let $f$ be a polynomial in $\nu$ variables of total degree $\delta$ and bitsize $\tau$. The $m$-th power of $f$, $f^m$, is a polynomial of total degree $m\delta$ and bitsize $m\tau + 12\nu m \lg(\delta)$.

<footnote n="2">²We also refer to this as the RUR of $I$, but we will ignore the multiplicity structure of $I$.</footnote>
## 2.3 SRUR of umixed systems and its bit complexity

Let $A_i \subset \mathbb{Z}^n$, for $i \in [n]$, be finite sets that span the affine lattice $\mathbb{Z}^n$; also $A = \{A_1, \dots, A_n\}$. We consider the following (sparse) polynomials, for $i \in [n]$,

$$f_i(\mathbf{X}) = \sum_{a \in A_i} c_{i,a} \mathbf{X}^a, \quad \text{where } c_{i,a} \neq 0 \text{ and } c_{i,a} \in \mathbb{Z}, \qquad (4)$$

along with the well-constrained polynomial system

$$(\Sigma): f_1(\mathbf{X}) = f_2(\mathbf{X}) = \dots = f_n(\mathbf{X}) = 0. \qquad (5)$$

Assume that the total degree of the $f_i$'s is at most $d$. We call the set $A_i$ the support of $f_i$, $A_i = \text{supp}(f_i)$. The Newton polytope $Q_i$ of $f_i$ is the convex hull of its support; also $\#Q_i$ is the number of lattice points in $Q_i$. We assume that the system is unmixed, that is $Q_i = Q$, for all $i \in [n]$. Let $\text{MV}(Q_1, \dots, Q_n)$ be the mixed volume of the convex polytopes $Q_1, \dots, Q_n \subset \mathbb{R}^n$; in our case it is $M_0 := \text{MV}(Q, \dots, Q) = n!\text{vol}(Q)$, where $\text{vol}(Q)$ is the volume of $Q$. We use $Q_0$ to denote the standard simplex, that in turn corresponds to a linear polynomial; it holds $\text{vol}(Q_0) = 1/n!$. We also need the expression $M_i = \text{MV}(Q_0, Q, \dots, Q)$, where the polytope $Q$ appears in $(n-1)$ times, for $i \in [n]$.

If we make the assumption that the volume of $Q$ is bigger than the volume of $Q_0$, for example, this is the case when it contains it, then $M_1 \le M_0$.

Our goal is to compute a rational parametrization of the roots of $(\Sigma)$; this is the so-called rational univariate representation (RUR) [Rou98]. The sparse rational univariate representation (SRUR) [MST17] is a variant of RUR that exploits the Newton polytopes of the polynomials, both for the computations and the complexity bounds. When the polynomials are dense, that is when they contain all the monomials of degree at most $d$, then the RUR and SRUR are the same$^3$.

There is an algorithm [MST17], see also [Roj99a], to compute the SRUR based on the sparse (or toric) resultant of a system of $n+1$ polynomial equations in $n$ variables, assuming we have fixed the $n+1$ supports. The sparse resultant generalizes the classical resultant of $n+1$ homogeneous polynomials by taking into account the supports of the polynomials; it provides a condition on the coefficients of the input polynomials for the solvability of the system. The BKK bound [Ber75; GKZ94] bounds the isolated toric solutions of the system using the mixed volume of the Newton polytopes, say $M_0$. Under our assumption that the system is unmixed, that is all the polynomials have the same support, it holds $M_0 := \text{MV}(Q_0, Q, \dots, Q) = n!\text{vol}(Q)$. There is also an extension [Roj99b; LW96] that counts all the affine solutions by forcing the exponents of the terms $1, X_1, \dots, X_n$ to be in the support of the polynomials.

**A warm up; the (generic) zero-dimensional case** To simplify the presentation, first we assume that $(\Sigma)$, Eq. (5), is a zero-dimensional polynomial system and the number of solutions is $M_0$. To compute SRUR, we use the technique of u resultant and we add an additional linear equation to $(\Sigma)$ to obtain the system:

$$(\Sigma_0): f_0(\mathbf{X}) = f_1(\mathbf{X}) = \dots = f_n(\mathbf{X}) = 0, \qquad (6)$$

$$\text{where} \quad f_0 = T - \sum_{i=1}^{n} \lambda_i X_i, \qquad (7)$$

where $T$ is a new variable and $\lambda_i$'s are integers that have to satisfy certain constraints. The first constraint is that the linear polynomial $f_0$ is such that if $\alpha = (\alpha_1, \dots, \alpha_n)$ and $\beta = (\beta_1, \dots, \beta_n)$ are two distinct roots of $(\Sigma)$, then $\sum_{i=1}^n \lambda_i \alpha_i \neq \sum_{i=1}^n \lambda_i \beta_i$. Based on this requirement, we call $f_0$ separating linear form. The forbidden set of values for $\lambda_i$'s that prevent $f_0$ of being separating is finite. There are additional constraints that $\lambda_i$'s have to satisfy that also result to finite set of forbidden values. We refer to [MST17, Section 2.3] for further details. Overall, if we consider a set of integers large enough, then we can be sure that we can find among them an assignment for $\lambda_i$'s suitable for computing the SRUR of the system. In this way, we bound the bitsize of $f_0$ as follows:

**Lemma 2.5.** [MST17, Eq. (9)] The bitsize of $f_0$ is bounded by $\tilde{O}(n + \lg(M_0))$.

<footnote>$^3$This is also holds when the Newton polytope is a (dilated) simplex. But we do not proceed further with this discussion.</footnote>
The bounds on the coefficients of $f_0$ and the precise description of the "forbidden" set allows us to pick the coefficients of $f_0$ uniformly at random from a sufficiently big finite set of integers; this leads to a Monte Carlo algorithm for computing SRUR. Alternatively, we can employ (a modification of) the algorithm by Brand and Sagraloff [BS16] to compute them deterministically. We will follow the Monte Carlo approach and we postpone the presentation of the deterministic algorithm for a future communication.

The computation of SRUR relies on sparse resultant computations, in particular on computing (a multiple of) the resultant as a determinant of a matrix. To be more specific, first we need to compute the sparse resultant of the system $(\Sigma_0)$; the resultant eliminates the variables $X$ and is a polynomial in $T$ (and in the coefficients of the input polynomials). To emphasize the dependency of the resultant on the coefficients of $f_0$, we denote its square-free part as $R(T) = R(T, \lambda_1, \dots, \lambda_n)$. Following [MST17], that in turn follows [Can88], we also compute the following $2n$ resultants $R(T, \lambda_1, \dots, (\lambda_k \pm 1), \dots, \lambda_n)$, for $k \in [n]$. The resultant is a factor of the determinant of the sparse resultant matrix. In particular, if the sparse resultant matrix is $M$, then the resultant is $\det(M)/\det(M_1)$, where $M_1$ is a submatrix of $M$ [DJS23]. However, there might be solutions at infinity or positive dimensional components that can make the matrix $M_1$ singular. In this case, this approach does not work.

**Solutions at infinity and symbolic perturbation** If the system $(\Sigma_0)$ has solutions at infinity, or if it is positive dimensional, or if the coefficients of $f_i$'s are not generic enough, then the determinant of the (sparse) resultant matrix, $M$, can be identically zero or the submatrix $M_1$ might be singular. To overcome these obstacles, we perform the resultant computations by exploiting the technique of the generalized characteristic polynomial [Can90] and in particular its sparse variant [DE01; Roj99a]. The idea is to perturb symbolically the initial system, using a new parameter, say $s$. In the worst case, we perturb all the coefficients of all the polynomials, except $f_0$. This ensures that the determinant of the sparse resultant matrix of the perturbed system, $M$, is not zero and the same holds for the submatrix $M_1$. These determinants, $\det(M)$ and $\det(M_1)$, are bivariate polynomials in $s$ and $T$. We can recover the sparse resultant as the quotient of the trailing coefficients of $\det(M)$ and $\det(M_1)$, seen as polynomials in $s$ with coefficients in $T$. This is a univariate polynomial in $T$ that we denote by $H$. Now, the roots of $H$ encode the isolated roots of the system, as well as points from all the irreducible components of the variety defined by the zero set of the polynomials $f_i$ [Roj99a, Thm. 2.4].

More formally, the perturbation of $(\Sigma_0)$ in (6) is as follows:

$$ (\tilde{\Sigma}_0) \quad \left\{ \begin{array}{l} \tilde{f}_0 = f_0 = 0, \\ \tilde{f}_i = f_i + s p_i = 0, \quad 1 \le i \le n, \end{array} \right. $$

where $s$ is a new parameter and $p_i$ are polynomials in $\mathbb{Z}[X]$ with support $\text{supp}(p_i) \subseteq A_i$, such that their resultant is not zero, that is $\text{Res}_A(p_1, \dots, p_n) \neq 0$.

The following theorem bounds the bitsize of the polynomials in SRUR that encode the isolated solutions of $(\tilde{\Sigma}_0)$. The polynomial $R_0$ is the square-free part of $H$.

**Theorem 2.6 ([MST17, Thm. 4.3])**. Let $(\Sigma)$ be a, not necessarily zero-dimensional, polynomial system with $n$ polynomials of maximum degree $d$ and maximum coefficient bitsize $\tau$. There is a representation of the isolated roots of $(\Sigma)$ using a separating linear form $f_0$, for $i \in [n]$, as

$$ X_i = R_i(\theta)/R'_0(\theta), \text{ where } \theta \text{ is such that } R_0(\theta) = 0, $$

where $\deg(R), \deg(R'), \deg(R_i) \le M_0$, and their bitsizes are bounded by $\tilde{O}(M_0 + (\tau + n) \sum_{i=0}^n M_i)$.

In this notation, $M_0$ is mixed volume of $(\Sigma)$ and $M_i$ is the mixed volume of the system resulting from $(\Sigma)$ if we ignore the $i$-the polynomial, i.e., $f_i$.

**Remark 2.7.** We emphasize that the degrees of $R'_0$ and $R_i$, for $i \ge 1$, are strictly smaller than $M_0$.

**Remark 2.8.** In the case where the polynomials in $(\Sigma)$ have degrees $d_1, \dots, d_n$, it holds $M_0 = \prod_{i=1}^n d_i$ and $M_i = \prod_{j \neq i} d_j$, for $i \in [n]$.

Similarly to the generic zero-dimensional case, we recover the SRUR based on $2n + 1$ resultant computations.

**Lemma 2.9 ([MST17, Lem. 4.4])**. Assuming that we have an oracle to perform resultant computations, we can compute the SRUR of the isolated roots of a, not necessarily zero-dimensional, polynomial system in $\tilde{O}_B(nM_0^2(n + \tau) \sum_{i=0}^n M_i)$ bit operations.
**Computing the resultants** The computation of SRUR relies on $2n+1$ sparse resultant computations. All the $2n+1$ resultant computations have similar costs, so it suffices to estimate the cost of computing one of them, say the resultant of $(\tilde{\Sigma}_0)$, that is $H$. To do so, we use the sparse version of the generalized characteristic polynomial to exploit the sparsity of $f_i$'s, which in turn is related to the Newton polytope $Q$.

We need to bound several quantities related to the Newton polytope(s). Recall, that as the system is unmixed, the number of isolated complex solutions is at most $M_0 = n!\mathrm{vol}(Q) \le d^n$. It also holds $M_1 = \cdots = M_n$ and $M_1 \le n!\mathrm{vol}(Q)$ and $M_1 \le nd^{n-1}$. The sparse resultant matrix of $(\tilde{\Sigma}_0)$, say $M$, has dimension $E \times E$, where $E$ is the number of lattice points in the Minkowski sum of the Newton polytopes of the $n+1$ polynomials of the system [CE00]. In our case, $E = \#(Q_0 \oplus n \cdot Q \cap \mathbb{Z}^n)$. The following lemma will allow us to bound $E$ using the volume of $Q$.

**Lemma 2.10 ([Bli14]).** Let $Q \subset \mathbb{R}^n$ be a full-dimensional integer polytope. Then, for every $k \in \mathbb{N}$, we have that $\#(k \cdot Q \cap \mathbb{Z}^n) \le k^n n! \mathrm{vol}(Q) + n$.

*Proof.* By [Bli14], we have that $\#(k \cdot Q \cap \mathbb{Z}^n) \le n! \mathrm{vol}(k \cdot Q) + n$. The proof follows from the fact that, as the volume function $k \mapsto \mathrm{vol}(k \cdot Q)$ is an homogeneous polynomial of degree $n$ [BR15, Ch. 3.5], we have that $k^n \mathrm{vol}(Q) = \mathrm{vol}(k \cdot Q)$. $\square$

First, we bound the degree and the bitsize of the resultant of $(\tilde{\Sigma}_0)$, that eliminates the variables $X$. The resultant is a polynomial in $\mathbb{Z}[s, T]$ and its terms are of the form

$$R(s, T) = \cdots + \varrho_k c_0^{M_0} c_{1,k}^{M_1} c_{2,k}^{M_2} \cdots c_{n,k}^{M_n} + \cdots, \quad (8)$$

where the semantics of $c_i^{M_i}$ are that it corresponds to a product of coefficients of the polynomial $\tilde{f}_i$ of total degree $M_i$, and $\varrho_k$ is an integer [EMT20]. As the coefficients of the polynomials $\tilde{f}_i$ are polynomials in $s$ or $T$, each factor in (8) is a polynomial in $s$ or $T$, and each term of $R$ is a polynomial in $s$ and $T$.

As our goal is to obtain worst case bounds, we consider the worst case scenario where we perturb all the coefficients of the polynomials $f_i$. Regarding the sizes, all the polynomials, except $f_0$, have bitsize at most $\tau$ and degree bounded by $d$; $f_0$ is linear and has bitsize $\tilde{O}(n + \lg M_0)$. The following remarks are in order regarding the terms of $R(s, T)$ in (8):

* The factor $c_0^{M_0}$ corresponds to a polynomial in $\mathbb{Z}[T]$, actually a monomial, of degree at most $M_0$ in $T$ and bitsize $\tilde{O}(nM_0 + M_0 \lg M_0)$. In particular, $c_0^{M_0}$ is of the form $T^k \prod_{i=1}^n \lambda_i^{M_i}$, where $\sum_i M_i = M_0 - k$. Thus, the number of terms in $R(s, T)$, as in (8), is at most $M_0 + 1$.

* Along the same lines (of the worst case scenario), we consider that $c_i^{M_i}$ is of the form $(s + 2^\tau)^{M_i}$. Thus, $c_i^{M_i}$ is a polynomial in $\mathbb{Z}[s]$ of degree $M_i$ and bitsize $\tilde{O}(M_i \tau + M_i \lg M_i)$.

Hence, $\prod_{i=1}^n c_i^{M_i}$ is a polynomial $\mathbb{Z}[s]$ of degree $nM_1$ and bitsize $\tilde{O}(nM_1 \tau + n \lg M_1)$, as $M_i = M_1$, for all $i$. Consequently, $c_i^{M_0} \prod_{i=1}^n c_i^{M_i}$ results a polynomial in $\mathbb{Z}[s, T]$, of degree at most $M_0$ in $T$ and $nM_1$ in $s$; its bitsize is $\tilde{O}(nM_1 \tau + M_0 \lg M_0 + n \lg M_1)$.

* The integer coefficient, $\rho_k$, of each term in (8) has magnitude $|\rho_k| \le \prod_{i=0}^n (\#Q_i)^{M_i} \le (2d^n)^{d^n}$ [EMT20], and so its bitsize is $\tilde{O}((nM_1+M_0) \lg(\#Q))$. Using Lem. 2.10, $\#Q \le n!\mathrm{vol}(Q)+n = M_0+n$, and so the bitsize becomes $\tilde{O}((nM_1+M_0) \lg M_0)$.

* The previous bounds leads to the conclusion that $R(s, T)$ is a polynomial in 2 variables of degree $nM_1$ in $s$ and $M_0$ in $T$, and bitsize $\tilde{O}(nM_1 \tau + M_0 \lg M_0 + n \lg M_1 + (nM_1 + M_0) \lg M_0)$. If we use that $M_1 \le M_0$, then the bitsize becomes $\tilde{O}(nM_1 \tau + nM_0 \lg M_0)$.

Recall that we compute $R(s, t)$ as the quotient of the trailing coefficients of $\det(M)$ and $\det(M_1)$, seen as polynomials in $s$ with coefficients in $T$.

Our current arsenal employs a fast algorithm to compute the determinant of a matrix whose elements are univariate polynomials [LNZ17]. In our case, the elements of the resultant matrix are bivariate polynomials. To transform the matrix $M$ into a matrix whose elements are univariate polynomials, we will specialize the variable $T$ to various values and compute the determinant of the (various) specialized matrices. Then, we will recover the determinant, in our case a bivariate polynomial, using interpolation.
The number of values of $T$ that we need to specialize the polynomials corresponds to the degree of the resultant as a polynomial in $T$; this is $M_0$. We choose the first $O(M_0)$ numbers, and so the elements of the specialized matrix are univariate polynomials in $s$ of bitsize at most $O(\tau + \lg M_0)$.

We compute the determinant of this matrix in $O(E^\omega(\lg E)^c \cdot 1)$ arithmetic operations [LNZ17, Theorem 1.1], where 1 bounds the average of the degrees of (the polynomials in) the columns (or the rows) of resultant matrix, and $c$ is constant$^4$. Hence, the bit complexity becomes $O_B(E^\omega(\lg E)^c (nM_1\tau + nM_0\lg M_0))$. However, we have to compute the determinant $O(M_0)$ times, as we want to recover a polynomial in $T$ of degree $O(M_0)$, therefore, the total complexity is $O_B(E^\omega(\lg E)^c (nM_0M_1\tau + nM_0^2\lg M_0))$.

Finally, it remains to recover the polynomial. We can do this using fast, univariate or multivariate polynomial interpolation algorithms [HL23; HL15; GG03]; their complexities are softly linear in the output. Hence, the computation of the determinants dominates the complexity of the algorithm.

**Proposition 2.11.** The bit complexity of computing each of the $2n+1$ resultants of the system $(\tilde{\Sigma}_0)$ is $O_B(E^\omega(\lg E)^c (nM_0M_1\tau + nM_0^2\lg M_0))$.

**Overall complexity** The combination of all previous results leads to the following theorem.

**Theorem 2.12 (SRUR computation).** Let $(\Sigma)$ be a, not necessarily zero-dimensional, polynomial system with $n$ polynomials of maximum degree $d$ and maximum coefficient bitsize $\tau$. The system is unmixed and all the polynomials have Newton polytope $Q$. Assume that $Q$ contains a (possibly integer-displaced) standard simplex.

There is a Monte Carlo algorithm that computes a SRUR of the isolated roots of $(\Sigma)$ in

$$ \tilde{O}_B \left( \frac{n^{(3\omega+2)n+3+c}}{e^{(\omega+2)n}} \mathrm{vol}(Q)^{\omega+2} (\tau + n \lg \mathrm{vol}(Q)) \right), $$

where $c$ is a small constant defined above. Alternatively, we have the simpler, but slightly less informative, bound

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

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

**Proof** The computation of the resultants dominates the complexity of the algorithm; thus, it suffices to bound the quantities appearing in Prop. 2.11, $E$, $M_0$, and $M_1$, using the volume of $Q$ to obtain bounds based on the sparsity of $f$.

To bound $E$, the dimension of the sparse resultant matrix, we express the number of lattice points using the volume of the Newton polytope of $f$ using Lem. 2.10. As we assume that $Q$ contains a integer-displaced standard simplex, it holds that $E = \#(Q_0 \oplus n \cdot Q \cap \mathbb{Z}^n) \le \#((n+1) \cdot Q \cap \mathbb{Z}^n) \le (n+1)^n n! \mathrm{vol}(Q) + n$, where the last inequality follows from Lem. 2.10. Also, by the BKK bound, $M_0 = n!\mathrm{vol}(Q)$. Moreover, because we assume that $Q$ contains a integer-displaced standard simplex and the mixed volume is a monotonically increasing function, it holds $M_1 \le n!\mathrm{vol}(Q)$. By applying Stirling's approximation of the factorial to Prop. 2.11 we obtain the complexity bound. $\square$

**Remark 2.13.** We emphasize that the exponent of $n$ in the previous bound is highly overestimated. A more careful analysis can reduce it significantly. As our purpose is to express the complexity bound with respect to the volume of $Q$ we do not proceed in this direction further.

**Remark 2.14 (Probability of success).** The algorithm for computing $(S)RUR$ is Monte Carlo because of the choice of the linear separating element. Lem. 2.5 counts the number of bad choices for the linear separating element $f_0$ and allows us to quantify the probability of success for the algorithm. Let $\eta := \tilde{O}(n+\lg M_0)$ and we choose the coefficients of $f_0$ uniformly at random from the discrete set $\{1, \dots, k 2^n\}$, where $k$ is a constant. This choice does not affect the bit complexity of the algorithm. Then, the probability of obtaining a suitable linear form, is $1 - \frac{1}{k}$; this is also the probability of success of the algorithm for computing the $(S)RUR$.

<footnote>$^4$In [LNZ17, Theorem 1.1] the complexity is in soft-O notation and it is far from straightforward to deduce the exponent of the logarithm, as the bound depends on many other results. In any case, it is constant and this is the reason we use $c$.</footnote>
**Corollary 2.15 (RUR computation).** If the $f_i$ are dense polynomials of degree $d$ and bitsize $\tau$, then, using a Monte Carlo algorithm, we can compute the RUR of their isolated solutions in $\tilde{O}_B(e^{\omega n+O(\lg n)} d^{(\omega+2)n} (d+\tau))$, or equivalently, in $\tilde{O}_B(e^{\omega n} d^{(\omega+2)n} (d+\tau))$. The polynomials in the RUR have degree at most $d^n$ and bitsize $\tilde{O}(d^n + nd^{n-1}(\tau+n))$.

*Proof.* To obtain the bound in the dense case, we should employ the Macaulay matrix to compute the $2n+1$ resultants. The dimension of the Macaulay matrix is the number of all monomials in $n$ variables of degree at most $nd-n+1$; that is $\binom{nd+1}{n}$. To bound this number, similarly to Stirling's approximation, we have that, for any $n \ge 1$, $n! > (\frac{n}{e})^n$. Moreover, as $1+k < e^k$ for any $k > 0$, we have that $(1+\frac{1}{nd})^n \le e^{\frac{1}{d}}$. Hence,

$$ \binom{nd+1}{n} \le (nd+1)^n \frac{1}{n!} \le (nd)^n e^{\frac{1}{d}} \frac{e^n}{n^n} = d^n e^{n+\frac{1}{d}}. $$

Observe that $M_0 \le d^n$ and $M_i \le d^{n-1}$. Then, the bound becomes $\tilde{O}_B(e^{\omega n} n^{2+c} d^{(\omega+2)n-1} (d+\tau))$, where $c$ is a constant. To conclude, we remark that $\tilde{O}_B(e^{\omega n}) = \tilde{O}_B(e^{\omega n} \lg(e^{\omega n})^{2+c}) = \tilde{O}_B(e^{\omega n} n^{2+c}) = \tilde{O}_B(e^{\omega n+(2+c)\lg n})$. $\square$

**Remark 2.16.** The degree of the polynomials $R_i$, for $i \in [n]$ is strictly less than the degree of $R_0$.

**Remark 2.17 (Systems with no solutions at infinity).** If we know that the system does not have solutions at infinity, then we do need to perform the symbolic perturbation. Hence, both the exponent of $\text{vol}(Q)$ in the sparse case and the exponent of $d$ in the dense case becomes $\omega+1$, instead of $\omega+2$. In particular, for the dense case the complexity bound becomes $\tilde{O}_B(e^{\omega n} n^{2+c} d^{(\omega+1)n-1} (d+\tau))$, or, $\tilde{O}_B(e^{\omega n} d^{(\omega+1)n} \tau)$. This bound, as well as the bound in Cor. 2.15, is slightly better than the bound of Brand and Sagraloff [BS16]. However, in their approach, they do not compute the RUR. Instead they project on the $x_i$ coordinates, there are $n$ of them. In other words, they employ the technique of hiding a variable.

There is the important recent work on polynomial system solving by van der Hoeven and Lecerf [HL21]; they introduce a probabilistic algorithm for solving that achieves almost quadratic arithmetic complexity bound, under some genericity assumptions (e.g., no solutions at infinity). As we cannot verify these assumptions in our problems, we do not proceed in this direction further. There is also a probabilistic algorithm for solving based on symbolic homotopy techniques [Jer+09], see also [SEDS18] for a variant with a bit complexity analysis, under the assumptions that the systems is radical and there are no solutions at infinity. It is not clear to us how to incorporate sparsity through the Newton polytopes in these algorithms and how to drop their assumptions to be applicable in our setting, hence, we also do not exploit this direction further.

## 2.4 Sparse versions of Nullstellensatz

To validate our certificates we will rely on (effective sparse versions of) Hilbert's Nullstellensatz. This is an algebraic identity that provides an algebraic certificate for a system of polynomial to have no common zeros. We need to bound the degrees of the polynomials involved in the identity, this is the *Effective Nullstellensatz* (Thm. 2.18), and their bitsize, this is the *Arithmetic Nullstellensatz* (Thm. 2.19). Both versions take into account the sparsity of the input polynomials.

**Theorem 2.18 (Sparse Effective Nullstellensatz [Som99, Thm 1]).** Let $f_1, \dots, f_s \in \mathbb{K}[X_1, \dots, X_n]$ be polynomials without common zeros in $\mathbb{C}^n$, where $\mathbb{K}$ is an algebraically closed field. Let $\mathcal{N}$ be an integer polytope containing the Newton polytopes of the polynomials $X_1, \dots, X_n, f_1, \dots, f_s$. Then, there exist $g_1, \dots, g_s \in k[X_1, \dots, X_n]$ satisfying

$$ 1 = g_1 f_1 + \cdots + g_s f_s, $$

such that $\text{NP}(g_i f_i) \subseteq (n^{n+3} (n!) \text{vol}(\mathcal{N})) \cdot \mathcal{N}$ for $i \in [s]$. Moreover, it holds $\text{deg}(g_i f_i) \le n^{n+3} d (n!) \text{vol}(\mathcal{N})$.

There is also an improvement of sparse Nullstellensatz by Herrero, Jeronimo, and Sabia [HJS19, Prop. 2] that allows us to remove the $n^{n+3}$ factor from the bound.

**Theorem 2.19 (Arithmetic Nullstellensatz [KPS01, Cor. 3]).** Let $f_1, \dots, f_s \in \mathbb{Z}[X_1, \dots, X_n]$ be polynomials without common zeros in $\mathbb{C}^n$. Let $d := \max_i \text{deg} f_i$ and $h := \max_i \mathfrak{h}(f_i)$. Let $\mathcal{N}$ be an integer polytope containing the Newton polytopes of $1, X_1, \dots, X_n, f_1, \dots, f_s$. Then, there exist $a \in \mathbb{Z} \setminus \{0\}$ and $g_1, \dots, g_s \in \mathbb{Z}[x_1, \dots, x_n]$ such that
• $a = g_1f_1 + \dots + g_s f_s,$

• $\deg g_i \le 2n^2 d(n!) \mathrm{vol}(\mathcal{N})$, and

• $\mathcal{H}(a), \mathcal{H}(g_i) \le (n+1)^3 d(n!) \mathrm{vol}(\mathcal{N})(h + \log s + 2^{2n+4}d \log(d+1)).$

## 2.5 Univariate 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 2.20 ([BDT25]).** Consider $f \in \mathbb{Z}[T]$ of size $(\delta, L)$ that is nonnegative over $\mathbb{R}$. A variant of the algorithm in [Che+11], uSOS, computes a weighted SOS decomposition of $f$, that is

$$f(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{O}}_B(\delta^3 + \delta^2 L)$ bit operations.

The rational numbers involved in the decomposition have bitsize at most $\tilde{\mathcal{O}}(\delta^2 + \delta L)$ and the bitsize of the (whole) decomposition is $\tilde{\mathcal{O}}(\delta^3 + \delta^2 L)$.

# 3 SOS decomposition à la RUR (SOS-RUR)

We present Theorem 3.2 that rewrites a polynomial $f \in \mathbb{Q}[\mathbf{X}]$ based on the RUR of its gradient ideal, $\mathrm{RUR}(I_{\nabla f})$, in a way that allows us to decide and certify if it is nonnegative; this answers $(\mathbb{Q}_0)$. We introduce a new variable, $T$, which in turn corresponds to a (sufficiently generic) linear combination of the variables $\mathbf{X}$. Thus, we work in the ring $\mathbb{Q}[\mathbf{X}, T]$, instead of $\mathbb{Q}[\mathbf{X}]$.

First, we introduce some additional notation for the ideals appearing in our computations.

**Definition 3.1.** Consider $f \in \mathbb{Q}[\mathbf{X}]$ such that its gradient ideal $I_{\nabla f}$ is zero-dimensional and $\mathrm{RUR}(I_{\nabla f}) = (R_0(T), R_1(T), \dots, R_n(T), T - \sum_{i=1}^n \lambda_i X_i)$. We define the following ideal in $\mathbb{Q}[\mathbf{X}, T]$:

$$I_{\mathrm{RUR}(\nabla f)} := \langle R'_0(T)X_1 - R_1(T), \dots, R'_0(T)X_n - R_n(T) \rangle \subseteq \mathbb{Q}[\mathbf{X}, T].$$

It is generated by the polynomials that parametrize the points of $\mathbb{V}_{\mathbb{C}}(I_{\nabla f})$, without $R_0$.

**Theorem 3.2.** Let $f \in \mathbb{Q}[\mathbf{X}]$ be of even total degree $d$. We assume that (i) $f$ attains its infimum and (ii) the gradient ideal $I_{\nabla f}$ is zero-dimensional.

Let $\mathrm{RUR}(I_{\nabla f}) = (R_0(T), R_1(T), \dots, R_n(T), T - \sum_{i=1}^n \lambda_i X_i)$, where $R_0, \dots, R_n \in \mathbb{Q}[T]$, $\lambda_1, \dots, \lambda_n \in \mathbb{Q}$ be a rational univariate representation of $\mathbb{V}_{\mathbb{C}}(I_{\nabla f})$. Then, $f$ is nonnegative over $\mathbb{R}^n$ if and only if we can decompose $(R'_0)^d f$ as an SOS of polynomials modulo the ideal $I_{\mathrm{RUR}(\nabla f)} \subseteq \mathbb{Q}[\mathbf{X}, T]$, that is

$$(R'_0)^d f = r + \sum_{i=1}^{n} (R'_0 X_i - R_i) q_i = \sum_{j=1}^{\nu} w_j s_j^2 + \sum_{i=1}^{n} (R'_0 X_i - R_i) q_i, \quad (9)$$

where $r, s_j \in \mathbb{Q}[T]$, $w_j \in \mathbb{Q}_+$, for $j \in [\nu]$, and $q_i \in \mathbb{Q}[T, \mathbf{X}]$, for $i \in [n]$.

**Remark 3.3.** The previous theorem holds even if $\mathrm{RUR}(I_{\nabla f})$ parameterizes some additional points on top of $\mathbb{V}_{\mathbb{C}}(I_{\nabla f})$. This additional points are always finite, as $R_0$ has only finitely many roots.

*Proof.* The proof is similar to [MSEDV23, Thm. 4.1], but exploits the RUR instead of the projection to the first variable and does not rely on any properties of Gröbner basis, that in any case are not needed for the proof.

(= ⇒ ) We divide $(R'_0)^d f$ by the following list of divisors $R'_0(T)X_1 - R_1(T), \dots, R'_0(T)X_n - R_n(T)$; one at a time. Then,

$$(R'_0)^d f = \sum_{i=1}^{n} (R'_0 X_i - R_i) q_i + r, \quad (10)$$
where $q_i, r \in \mathbb{Q}[T, X]$. During the process of the division algorithm, we consider $R'_0 X_i$ as a new variable $Y_i$. In this way, $(R'_0)^d f$ is a polynomial in $Y_i$'s and $T$, and the divisors are the monic polynomials $Y_i - R_n(T)$ that will eliminate all the $Y_i$'s in $(R'_0)^d f$, during the division process. Hence, $r$ is a polynomial in the variable $T$ only.

Moreover, if we substitute $\frac{R_i}{R'_0}$ in the place of $X_i$ in (10) and clear denominators, then we get $r = (R'_0)^d f(\frac{R_i}{R'_0}, \dots, \frac{R_n}{R'_0})$, which is a nonnegative polynomial in $\mathbb{Q}[T]$. The nonnegativity of $r$ follows from the fact that $d$ is even and $f$ is nonnegative. As $r$ is a univariate nonnegative polynomial, we can write it as a sum of weighted squares

$$r = \sum_{j=1}^{\nu} w_j s_j^2,$$

where $s_j \in \mathbb{Q}[T]$ and $w_j \in \mathbb{Q}_+$, for $j \in [\nu]$.

Altogether, we get the decomposition $(R'_0)^d f = \sum_{j=1}^{\nu} w_j s_j^2 + \sum_{i=1}^{n} (R'_0 X_i - R_i)q_i$ we are aiming at.

( $\Leftarrow$ ) If $f$ admits a representation as in (9), then the nonnegativity of $\sum_{j=1}^{\nu} w_j s_j^2$ over the reals implies the nonnegativity of $(R'_0)^d f$ over all the points in $\mathbb{V}_{\mathbb{R}}(I_{\mathbb{R}R(\nabla f)} + \langle R_0 \rangle)$, that in turn implies the nonnegativity of $f$ on $\pi_T(\mathbb{V}_{\mathbb{R}}(I_{\mathbb{R}R(\nabla f)} + \langle R_0 \rangle)) \subseteq \mathbb{R}^n$, where $\pi_T$ is the projection $(X, T) \mapsto X$, as $d$ is even. Note that $\mathbb{V}_{\mathbb{R}}(I_{\nabla f}) \subseteq \pi_T(\mathbb{V}_{\mathbb{R}}(I_{\mathbb{R}R(\nabla f)} + \langle R_0 \rangle))$. In fact, for any point in the gradient variety $x = (x_1, \dots, x_n) \in \mathbb{V}_{\mathbb{R}}(I_{\nabla f})$, we have $t = \sum_{i=1}^{n} \lambda_i x_i \in \mathbb{R}$; that is, all the real critical points are parametrized by real $t$. So, $f$ is nonnegative over all critical points and consequently nonnegative globally since, by our assumptions, $f$ attains its infimum. $\square$

**Corollary 3.4.** The polynomial $r(T) \in \mathbb{Z}[T]$ from Theorem 3.2 is not zero and satisfies

$$r = R_0^d f \left( \frac{R_1}{R_0^\prime}, \dots, \frac{R_n}{R_0^\prime} \right) \in \mathbb{Z}[T]. \qquad (11)$$

*Proof.* The algebraic identity follows from the substitution of $X_i \leftarrow \frac{R_i}{R_0^\prime}$ in (9). To see that $r(T) \neq 0$, observe that, by the construction of RUR, it holds $R_0^\prime(T) \neq 0$. We consider $(\frac{R_1}{R_0^\prime}, \dots, \frac{R_n}{R_0^\prime})$ as a rational parameterization of a curve that includes all the critical points of $f$. Thus, if $r(T) = 0$, then $f$ vanishes at every point defined by the rational parameterization. As these points include the critical points of $f$ and $f$ attains its minimum, then the minimum of $f$ is zero and it is attained by an infinite number of points. However, this cannot happen as we assumed that $f$ has a finite number of critical points. $\square$

Theorem 3.2, under its assumptions, supports a nonnegativity certificate for a nonnegative $f \in \mathbb{Q}[X]$ by representing it as an SOS modulo the ideal $I_{\mathbb{R}R(\nabla f)}$, Eq. (9); under the condition that we can certify that we have computed the correct RUR of the points in $\mathbb{V}_{\mathbb{R}}(I_{\nabla f})$ (see Sec. 4). Even more, it leads to an algorithm, we call it SOS-RUR, for obtaining this decomposition. The pseudo-code of SOS-RUR appears in Alg. 1; this answers $(\mathbb{Q}_1)$.

The crucial steps of the algorithm SOS-RUR consist in computing the RUR of the gradient ideal of $f$, computing the remainder of a polynomial modulo an ideal, and writing a nonnegative univariate polynomial as SOS. We detail on these (sub)algorithms in the sequel, where we also present their precise bit complexity analysis.

## 3.1 (Sub)algorithms and bit complexity bounds: the dense case

We present bit complexity bounds for the various subalgorithms that SOS-RUR employs, that is to compute the (S)RUR of the gradient ideal, and the remainder and quotients modulo the ideal $I_{\mathbb{R}R(\nabla f)}$, as well as bounds on the sizes of the corresponding polynomials. Finally, we estimate the bit complexity of SOS-RUR and we bound the (overall) bitsize of the certificate.

**The RUR of the gradient ideal** The generators of the gradient ideal, $I_{\nabla f}$, are the derivatives of $f$, so the system $\partial_1 f = \dots = \partial_n f = 0$, has as solutions, $\mathbb{V}_C(I_{\nabla f})$, the critical points of $f$. If $f$ has size $(d, \tau)$, then its derivatives have size $(d-1, \tilde{\mathcal{O}}(\tau))$. A direct application of Cor. 2.15, see also Rem. 2.7, leads to the following lemma:
**Algorithm 1 SOS-RUR**

**Input:** A multivariate polynomial $f \in \mathbb{Q}[\mathbf{X}]$.

**Assumptions:** (i) The gradient ideal $I_{\nabla f}$ is zero-dimensional, and (ii) $f$ attains its infimum.

**Output:** A pair $[\mathfrak{b}, \mathfrak{L}]$.

The first element of the pair, $\mathfrak{b}$, is a boolean, that is True or False, depending on whether $f$ is nonnegative or not. The second element $\mathfrak{L}$ is a list, that is as follows:

* If $f(\mathbf{x}) < 0$ for some point(s) $\mathbf{x} \in \mathbb{Q}^n$, then $\mathfrak{L}$ contain such a witness point.

* If $f$ is nonnegative, then $\mathfrak{L}$ contains the polynomials of the RUR of $I_{\nabla f}$, $\text{RUR}(I_{\nabla f}) = (R_0(T), R_1(T), \dots, R_n(T), T - \sum_{i=1}^n \lambda_i X_i)$, where $R_i \in \mathbb{Q}[T]$, $\lambda_i \in \mathbb{Q}$, as well as polynomials $s_j \in \mathbb{Q}[T]$ and numbers $w_j \in \mathbb{Q}_+$, for $j \in [\nu]$, $q_i \in \mathbb{Q}[T, \mathbf{X}]$, for $i \in [n]$, such that

$$ (R'_0)^d f = r + \sum_{i=1}^{n} (R'_0 X_i - R_i) q_i, \text{ with } r = \sum_{j=1}^{\nu} w_j s_j^2. $$

(S1) Compute a rational univariate representation of $\mathbb{V}(I_{\nabla f})$.

$$ \text{This is } \text{RUR}(I_{\nabla f}) = (R_0(T), R_1(T), \dots, R_n(T), T - \sum_{i=1}^n \lambda_i X_i). $$

For this computation rely on the algorithms supported by Theorem 3.5.

(S2) Divide $(R'_0)^d f$ by the list of divisors $R'_0(T)X_1 - R_1(T), \dots, R'_0(T)X_n - R_n(T)$ and get the remainder $r \in \mathbb{Q}[T]$ and the quotients $q_i \in \mathbb{Q}[T, X]$, for $i \in [n]$.

For these computations rely on the algorithms supported by lemmata 3.6 and 3.7.

(S3) Check if $r$ is nonnegative (see Theorem 3.8).

If $r$ can be negative, then $f$ can be negative. Return a point $\mathbf{x}$ such that $f(\mathbf{x}) < 0$. That is
RETURN $[\text{False}, \mathbf{x}]$.

If $r$ is nonnegative, then write $r$ as a weighted SOS, i.e., $r = \sum_{j=1}^{\nu} w_j s_j^2$, where $s_j \in \mathbb{Q}[T]$ and $w_j \in \mathbb{Q}_+$, for $j \in [\nu]$. Return all the polynomials appearing in Eq. (9). That is
RETURN $[\text{True}, [R_0, R_i, w_j, s_j]]$.

**Lemma 3.5.** Let $f \in \mathbb{Z}[X]$ be of size $(d, \tau)$ and assume that $I_{\nabla f}$ is zero-dimensional. We can compute the RUR of the points of $\mathbb{V}_{\mathbb{C}}(I_{\nabla f})$ at the cost of $\tilde{\mathcal{O}}_B(e^{\omega n+\mathcal{O}(\lg n)}d^{(\omega+2)n}(d+\tau))$ bit operations, where $\omega$ is the exponent of matrix multiplication and $c$ is a small constant. The polynomials in RUR have degree at most $(d-1)^n$ and bitsize $\tilde{\mathcal{O}}((d-1)^n + n(d-1)^{n-1}(\tau+n))$.

**Computing and bounding the remainder** First, we estimate the degree and the bitsize of the remainder $r$, see (9), based on (11). The size $f$ is $(d, \tau)$. Further assume, to simplify the calculations, that $R_i$ has size $(\delta, L)$; the precise bounds are in Lem. 3.5. Then, the size of $r \in \mathbb{Z}[T]$ is $(d\delta, \tilde{\mathcal{O}}(\tau + dL + d \lg \delta))$; this follows from performing the substitution $X_i \leftarrow \frac{R_i(T)}{R_0(T)}$ and applying the (bitsize) bounds for polynomial multiplication (Lem. 2.4).

Based on Eq. (11), we can compute $r$ using multipoint evaluation and interpolation. If we know the evaluations of $r$ at $\mathcal{O}(d\delta)$ points, then we can perform interpolation to recover its coefficients. In turn, this means that we need to evaluate (each) $R_i$ at $\mathcal{O}(d\delta)$ numbers. We pick the first $\mathcal{O}(d\delta)$ integers; thus, we evaluate at numbers of bitsize $\mathcal{O}(\lg(d\delta)) = \tilde{\mathcal{O}}(\lg \delta)$. This tasks requires $\mathcal{O}(d)$ multipoint evaluations of (each) $R_i$, it has size $(\delta, L)$, at $\mathcal{O}(\delta)$ numbers of bitsize $\mathcal{O}(\lg \delta)$.

Each multipoint evaluation costs $\tilde{\mathcal{O}}_B(\delta(\delta \lg \delta + L))$ and results in $\mathcal{O}(\delta)$ numbers of bitsize $\tilde{\mathcal{O}}(\delta \lg \delta + L)$ each [PT17, Lemma 21]. Hence, the overall cost of all multipoint evaluations that we need to perform for all $R_i$'s is $\tilde{\mathcal{O}}_B(\delta n\delta(\delta \lg \delta + L))$. It results $\tilde{\mathcal{O}}(d\delta)$ n-tuples of numbers of bitsize $\tilde{\mathcal{O}}(\delta \lg \delta + L)$.

Now, we evaluate $f$ at these $\mathcal{O}(d\delta)$ n-tuples. The degree of $f$ is $d$. By Bézout's bound, we have $d^n \ge \delta$. Therefore, we can perform $\mathcal{O}(d)$ multipoint evaluations of $f$ at $\mathcal{O}(\delta)$ points each time. Each multipoint evaluation requires $\tilde{\mathcal{O}}(nd^n)$ operations [HL23, Theorem 1]. The evaluation of $f$ results numbers of bitsize
$\tilde{O}(n^2d(\delta \lg \delta + L))$. Hence, the bit complexity of the $d$ multipoint evaluations of $f$ is $\tilde{O}_B(n^3d^{n+1}(\delta \lg \delta + L))$. Finally, we perform univariate interpolation to recover $r$. This costs $\tilde{O}_B(n^2d^3\delta^2(\delta \lg \delta + L))$ [PT17, Lemma 24].

So, the overall costs is $\tilde{O}_B(n^2d^3\delta^2(\delta \lg(d\delta) + L))$. Using the bounds of Lem. 3.5 for $\delta$ and $L$, we obtain the following lemma:

**Lemma 3.6.** Let $f \in \mathbb{Z}[X]$ be of size $(d, \tau)$ and assume that $I_{\nabla f}$ is zero-dimensional. The size of the remainder $r \in \mathbb{Z}[T]$ in (9) is $(d(d-1)^n, \tilde{O}(d^{n+1} + nd^n\tau))$ and, assuming that RUR($I_{\nabla f}$) is available, we can compute it at the cost of $\tilde{O}_B(n^3 d^{3n+2}(n+d+\tau))$ bit operations.

**Computing and bounding the quotients** To bound and compute the quotients, $q_i$, in (9), we consider successive evaluations of $f$ to obtain the remainder $r$ of (11). At the $k$-th step, for $k \in [n]$, we obtain the quotient $q_k$ by dividing the polynomial

$$r_{k-1} = R'_{0}^{d} f(\frac{R_{1}}{R'_{0}}, \dots, \frac{R_{k-1}}{R'_{0}}, X_{k}, \dots, X_{n}) \in (\mathbb{Q}[X_{k+1}, \dots, X_{n}])[X_{k}],$$

with the polynomial $R'_{0}X_{k} - R_{1}$. Notice that the remainder of this division corresponds to the evaluation

$$r_k = R'_{0}^{d} f(\frac{R_1}{R'_{0}}, \dots, \frac{R_k}{R'_{0}}, X_{k+1}, \dots, X_{n}) \in \mathbb{Q}[X_{k+1}, \dots, X_{n}].$$

Therefore, we have the equation

$$r_{k-1} = (R'_{0}X_{k} - R_{k})q_{k} + r_{k},$$

where $q_k$ is the quotient that we want estimate. We use this equation to bound the size of $q_k$.

Let the size of $r_k$ be $(d\delta, \tilde{O}(dL+d\lg\delta))$, where as before $(\delta, L)$ is the size of $R_i$ (that we will eventually bound using Lem. 3.5). The (total) degree of $q_k$ with respect to the variables $X_k, \dots, X_n$ is $d$ and with respect to $T$ is $\mathcal{O}(d\delta)$. Its bitsize is $\tilde{O}(dL+d\lg\delta+d\delta)$; this follows by observing that $q_k$ is an exact divisor of the polynomial $r_{k-1} - r_k$ and apply Mignotte's bound for the bitsize of the factors of a polynomial [Mah62; AM01].

To compute $q_k$ we employ (multipoint) evaluation and interpolation, as we did for the remainder $r$. Actually, we can exploit a classical, specially adopted, exact univariate polynomial division algorithm with (almost) linear arithmetic complexity; in this case we compute $q_k$ as $q_k = (r_{k-1} - r_k)/(R'_{0}X_k - R_k)$. In any case, the cost is $\tilde{O}_B(d^3\delta^2(L + \lg \delta + \delta))$ bit operations [GG03, Ex. 9.14].

**Lemma 3.7.** Let $f \in \mathbb{Z}[X]$ be of size $(d, \tau)$ and assume that $I_{\nabla f}$ is zero-dimensional. The quotient $q_k \in \mathbb{Z}[X_k, \dots, X_n, T]$, in (9), for $k \in [n]$, is of degree $d$ with respect to the variables $X_k, \dots, X_n$ and of degree $\mathcal{O}(d(d-1)^n)$ with respect to $T$; its bitsize is $\tilde{O}(d^n(d + n\tau))$.

Assuming RUR($I_{\nabla f}$) is available, we can compute all the quotients $q_k$ in $\tilde{O}_B(d^{3n+2}(d + n\tau))$ bit operations.

**Decomposition of $r$ and witness points of negativity** If $r \in \mathbb{Z}[T]$ is nonnegative, we can use uSOS (Prop. 2.20) to write it as a weighted SOS of polynomials with rational coefficients; that is $r(T) = \sum_{j=1}^{\nu} w_j s_j^2(T)$, where $\nu \le \deg(r) + 3$, $s_j \in \mathbb{Q}[T]$, and $w_j \in \mathbb{Q}_+$, for $j \in [\nu]$. This is always possible because $r$ is univariate. Lemma 3.6 implies that $r$ has size $(d(d-1)^n, d^{n+1} + nd^n\tau)$. Hence, we can compute the decomposition in $\tilde{O}_B(d^{3n+2}(d+n\tau))$ (Prop. 2.20). Even more, the bitsize of the polynomials involved in this decomposition is $\tilde{O}(d^{2n+1}(d+n\tau))$ and the bitsize of all them is $\tilde{O}(d^{3n+2}(d+n\tau))$.

If $r \in \mathbb{Z}[T]$ is not nonnegative, then we cannot write it as a sum of squares. There are two cases. It might happen that $r(t) < 0$, for every $t \in \mathbb{R}$. Alternatively, if $f$ takes both positive and negative values, then we can find a (rational) number $t$, such that $r(t) < 0$, which lies between two consecutive real roots of $r$. In the literature of real root isolation, this point $t$ is known as intermediate point, e.g., [BPR06, Alg. 10.107]. To find $t$, we isolate the real roots of $f$ in $\tilde{O}_B(d^{3n+3} + nd^{3n+2}\tau)$ [MSW15; Pan02]. The endpoints of the isolating intervals can serve as intermediate points and hence $t$. Their bitsize, and hence the bitsize of $t$, is $\tilde{O}(d^{2n+2} + nd^{2n+1}\tau)$.

It remains to evaluate RUR at $t$ to obtain a witness point for $f$; this results to the point $(\frac{R_1(t)}{R'_0(t)}, \dots, \frac{R_n(t)}{R'_0(t)})$.

The coordinates of the witness point have bitsize $\tilde{O}(nd^{2n+3} + n^2d^{2n+2}\tau)$.

The previous discussion leads to the following lemma:
**Lemma 3.8.** Let $f \in \mathbb{Z}[X]$ be of size $(d, \tau)$ and assume that $I_{\nabla f}$ is zero-dimensional and $f$ attains its minimum.

If the remainder $r \in \mathbb{Z}[T]$, in (9), is nonnegative, then uSOS, see Prop. 2.20, can decompose it as a weighted SOS in $\tilde{\mathcal{O}}_B(d^{3n+3} + nd^{3n+2}\tau)$. The largest bitsize of all the rationals involved in the decomposition is $\tilde{\mathcal{O}}(d^{2n+1}(d+n\tau))$ and the total bitsize of the decomposition is $\tilde{\mathcal{O}}(d^{3n+2}(d+n\tau))$.

If $r$ is not nonnegative, then we can compute a number $t \in \mathbb{Q}$ such that $r(t) < 0$ and, assuming that $\text{RUR}(I_{\nabla f})$ is available, using $t$, we can compute a witness point of negativity of $f$ in $\tilde{\mathcal{O}}_B(d^{3n+2}(d+n\tau))$ bit operations. The bitsize of the coordinates of the witness point is $\tilde{\mathcal{O}}(nd^{2n+2}(d+n\tau))$.

## 3.2 Overall complexity of SOS-RUR

We have all the ingredients to give answers to many of the questions related to the certificates of nonnegativity. The following theorem bounds, by combining the results of the previous section, the complexity of SOS-RUR and answers $(Q_1)$; it also bounds the bitsize of the certificate $(Q_2)$ and the complexity of computing and bounding the witness point $(Q_4)$.

**Theorem 3.9.** Consider $f \in \mathbb{Z}[X]$ of size $(d, \tau)$. Assume that the gradient ideal of $f$ is zero-dimensional and that $f$ attains its infimum.

If $f$ is nonnegative, then SOS-RUR computes a weighted SOS decomposition of $f$ modulo the ideal $I_{\text{RUR}(\nabla f)}$, as in (9), in $\tilde{\mathcal{O}}_B(e^{\omega n+\mathcal{O}(\lg n)}d^{(\omega+2)n}(d+\tau))$ bit operations, where $\omega$ is the exponent of matrix multiplication.

The polynomials involved in the decomposition have degree at most $d(d-1)^n$ and their largest coefficient has bitsize $\tilde{\mathcal{O}}(d^{2n+1}(d+n\tau))$. The total bitsize of the decomposition is $\tilde{\mathcal{O}}(d^{3n+2}(d+n\tau))$.

If $f$ is not nonnegative, then SOS-RUR returns a (witness) point $\mathbf{x} \in \mathbb{Q}^n$, such that $f(\mathbf{x}) < 0$. The bitsize (of the coordinates) of the witness point is $\tilde{\mathcal{O}}(nd^{2n+2}(d+n\tau))$.

*Proof.* The pseudo-code of SOS-RUR appears in Alg. 1.

Regarding the (bit)size of the various polynomials appearing in the decomposition of $f$, we have the following:

* The polynomials in $\text{RUR}(I_{\nabla f})$, $R_i$, have $((d-1)^n, \tilde{\mathcal{O}}((d-1)^n+n(d-1)^{n-1}(\tau+n)))$ (Lem. 3.5).

* The quotients $q_i$ have degree at most $d$ with respect to $\mathbf{X}$ and at most $d(d-1)^n$ with respect to $T$; their bitsize is $\tilde{\mathcal{O}}(d^n(d+n\tau))$ (Lem. 3.7).

* The remainder $r$ has size $(d(d-1)^n, d^{n+1}+nd^n\tau)$ (Lem. 3.6).

The complexity of the various steps is as follows:

(S1) The computation of $\text{RUR}(I_{\nabla f})$ costs $\tilde{\mathcal{O}}_B(e^{\omega n+\mathcal{O}(\lg n)}d^{(\omega+2)n}(d+\tau))$ (Lem. 3.5).

(S2) The computation of the remainder and the quotients costs $\tilde{\mathcal{O}}_B(nd^{3n+2}(d+\tau))$ (Lem. 3.6) and $\tilde{\mathcal{O}}_B(d^{3n+2}(d+n\tau))$ (Lem. 3.7), respectively.

(S3) If $r$ is nonnegative over $\mathbb{R}$, then, using uSOS (Prop 2.20) we compute a weighted SOS decomposition of $r$ in $\tilde{\mathcal{O}}_B(d^{3n+2}(d+n\tau))$ (Lem. 3.8). This decomposition involves polynomials of bitsize $\tilde{\mathcal{O}}(d^{2n+1}(d+n\tau))$.

The computation of RUR dominates the overall complexity.

The decomposition of $r$ results in $\mathcal{O}(d^{n+1})$ polynomials and positive rationals. Their total bitsize is at most $\tilde{\mathcal{O}}(d^{3n+2}(d+n\tau))$ (Lem. 3.8).

If $r$ can be negative, then we return a number such that $f(\mathbf{x}) < 0$. Following, Lem. 3.8 the complexity of this step is $\tilde{\mathcal{O}}_B(d^{3n+2}(d+n\tau))$, and it is dominated by the complexity of RUR. The bitsize of $\mathbf{x}$ is $\tilde{\mathcal{O}}(nd^{2n+2}(d+n\tau))$. $\square$
## 3.3 Sparse certificates of nonnegativity

We turn our attention to the construction of sparse certificates of nonnegativity. We consider a variant of Theorem 3.2 that certifies the nonnegativity of $f$ using polynomials having degree and Newton polytopes related to the Newton polytope of $f$. We employ a univariate polynomial $G(T)$, such that $G(T)^2f(X)$ is a sum of sparse polynomials in the ideal $I_{\text{RUR}(\nabla f)}$ and the product of a monomial and a positive (univariate) polynomial, see (12). We modify SOS-RUR accordingly to compute the sparse certificate and we present bit complexity bounds for the various subalgorithms involved in the process as well as bounds on the sizes of the polynomials involved in the decomposition.

We refer the reader to the beginning of Section 2.3 for a brief introduction to sparse polynomials. Given a polytope $Q \subset \mathbb{R}^n$ and a ring $R$, we denote by $R[X]_Q$ the $R$-vector space of polynomials supported on $Q$; thus

$$R[X]_Q \approx \operatorname{span}_R \{X^\alpha : \alpha \in Q \cap \mathbb{Z}^n\}.$$

For our purposes, we consider $R \in \{\mathbb{Z}, \mathbb{Z}[T], \mathbb{Z}(T)\}$, where the latter corresponds to rational functions in the variable $T$.

**The SRUR of the gradient ideal** If the Newton polytope of $f$ is $Q$, then, as we opt for worst case bounds, we can assume that Newton polytope of its derivatives is also $Q$. Then, Thm. 2.12 leads to the following:

**Corollary 3.10.** Let $f \in \mathbb{Z}[X]$ be of size $(d, \tau)$ and let $Q$ be its Newton polytope. Further assume that $I_{\nabla f}$ is zero-dimensional. We can compute the SRUR of $V_C(I_{\nabla f})$ in

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

The size of the polynomials in SRUR is $(n!\operatorname{vol}(Q), \tilde{O}((n+1)!\operatorname{vol}(Q)(n+\tau)))$.

**Sparse reduction modulo gradient ideal** Assume $f \in \mathbb{Z}[X]$ with Newton polytope $Q$. Let $L_i \subset \mathbb{R}^n$ be the Newton polytope of the linear polynomial $X_i+1$ in $\mathbb{R}^n$, for $i \in [n]$; this is a segment. We consider the polytope $\hat{L}_i$ to be the Minkowski sum of $Q$ and all $L_j$, with $j \neq i$, that is

$$\hat{L}_i = Q \oplus L_1 \oplus \cdots \oplus L_{i-1} \oplus L_{i+1} \oplus \cdots L_n.$$

Let $L := L_1 + \cdots + L_n$. As we are interested in sparse nonnegative polynomials, the Newton polytope of $f$, $Q$, has to be an integral over the lattice $(2\mathbb{Z})^n$.

**Lemma 3.11** ([Rez78, Lem. 1, Sect. 3]). If $f \ge 0$, then for every $\alpha \in \text{Vertices}(Q)$, $\alpha \in (2\mathbb{Z})^n$.

If the condition on the vertices of $Q$ is not satisfied, then we can deduce that $f$ can be negative by showing that there is a vertex of $Q$ that has an odd coordinate.

If we know the vertices of the Newton polytope, then we can easily check if a point is one of them. If we are given the Newton polytope as the intersection of halfspaces, then the point should be the unique solution of a subset of linearly independent (tight) inequalities, that correspond to a full rank matrix. Finally, to verify that a point, say $v_j$ for some $j \in [N]$, is a vertex of a polytope defined by a set of points $V = \{v_i, i \in [N]\}$, for some positive integer $N$ that denotes the number of points, it suffices to show that the following feasibility problem

$$\text{Find } \lambda_i \ge 0 \quad \text{s.t.} \quad \sum_{i \neq j} \lambda_i (v_i - v_j) = 0, \quad \sum_{i \neq j} \lambda_i = 1,$$

has no solution; that is to verify that $v_j$ is not a convex combination of the other points. In all the cases, the arithmetic complexity is single exponential if we employ the simplex method to solve linear programs, or polynomial in the bit complexity model, if we use an interior point algorithm. As this complexity is dominated, we do not elaborate further.

To simplify our exposition, we only consider the case where all the vertices of $Q$ have even coordinates.
**Lemma 3.12.** Let $f \in \mathbb{Z}[\mathbf{X}]$ be of size $(d, \tau)$ and let $Q \subset \mathbb{R}^n$ be its Newton polytope. Assume that Vertices$(Q) \subset (2 \cdot \mathbb{Z})^n$. Consider the sparse RUR$(I_{\nabla f}) = (R_0(T), \dots, R_n(T), T - \sum_{i=1}^n \lambda_i X_i)$ obtained from Theorem 3.10. There are sparse polynomials $q_i \in \mathbb{Z}[T][\mathbf{X}]_{\hat{L}_i}$, for $i \in [n]$, $r(T), G(T) \in \mathbb{Z}[T]$, and a monomial $X^{2\alpha} \in \mathbb{Z}[\mathbf{X}]_Q$ such that,

$$G(T)^2 f(\mathbf{X}) = \sum_i q_i(\mathbf{X}, T) (R'_0(T)X_i - R_i(T)) + (\mathbf{X}^\alpha)^2 r(T). \quad (12)$$

Moreover, $G$, $r$, and the coefficients of every $q_i$, if we consider them as polynomials in $\mathbf{X}$ with coefficients in $\mathbb{Z}[T]$, have degree at most $2^{n+2} n!^2 \mathrm{vol}(Q)^2$ and bitsize $\tilde{\mathcal{O}}(2^n (n+1)!^2 \mathrm{vol}(Q)^2 (n+\tau))$.

*Proof.* Let $\bar{\epsilon} := (-\epsilon, \dots, -\epsilon)$, where $\epsilon$ is sufficiently small positive rational number. Consider the Sylvester map

$$\text{Sylv} : \mathbb{Z}(T)[\mathbf{X}]_{L+\bar{\epsilon}} \times \mathbb{Z}(T)[\mathbf{X}]_{\hat{L}_1+\bar{\epsilon}} \times \mathbb{Z}(T)[\mathbf{X}]_{\hat{L}_n+\bar{\epsilon}} \to \mathbb{Z}(T)[\mathbf{X}]_{Q+L+\bar{\epsilon}} \\ (c_0(T, \mathbf{X}), c_1(T, \mathbf{X}), \dots, c_n(T, \mathbf{X})) \xrightarrow{\text{Sylv}} c_0(T, \mathbf{X})f(\mathbf{X}) + \sum_i c_i(T, \mathbf{X})(R'_0(T)X_i - R_i(T)).$$

By [DJ24, Thm 1.8], this map is surjective if and only if the (toric) homogenized system associated to the equations $\{f(\mathbf{X}) = 0, R'_0(T)X_1 - R_1(T) = 0, \dots, (R'_0(T)X_n - R_n(T)) = 0\}$ over the projective toric variety $Y$, induced by the polytopes $Q, L_1, \dots, L_n$ over the algebraic closure of $\mathbb{Z}(T)$, has no solutions. By toric homogenization, we mean the standard homogenization over the coordinate ring (Cox ring) of $Y$, where the degree is the class of the Newton polytope of the polynomial; see e.g., [DJ24, Sec. 2].

The homogenized system has solutions in $Y$ if and only if the following algebraic identity holds,

$$f\left(\frac{R_1}{R'_0}(T), \dots, \frac{R_n}{R'_0}(T)\right) = 0. \qquad (13)$$

This is so because the only solution of the systems associated to $\{(R'_0(T)X_1 - R_1(T)) = 0, \dots, (R'_0(T)X_n - R_n(T)) = 0\}$ over $Y$ is $(\frac{R_1}{R'_0}(T), \dots, \frac{R_n}{R'_0}(T))$. To see this, notice that the polynomials are linear forms with respect to the $\mathbf{X}$ variables with nonzero coefficients over $\mathbb{Z}(T)$ and as $Q$ is the Newton polytope of $f$, it follows that $f$ does not have any trivial solution at infinity in $Y$. Hence, by Cor. 3.4, the map Sylv is surjective.

The elements of the Macaulay matrix associated to the map Sylv are in $\mathbb{Z}(T)$, to be more precise they are polynomials in $\mathbb{Z}[T]$. We obtain them by fixing a monomial basis for the polynomials in $(\mathbb{Z}(T))[\mathbf{X}]$, that is polynomials in $\mathbf{X}$ with coefficients in $(\mathbb{Z}(T))$. As the entries of $\bar{\epsilon}$ are small enough, we have that $\{0\} = (L + \bar{\epsilon}) \cap \mathbb{Z}^n$, so the $\mathbb{Z}(T)$-vector space $\mathbb{Z}(T)[\mathbf{X}]_{L+\bar{\epsilon}}$ is spanned by the monomial $1 = \mathbf{X}^0$. Hence, only the first column of the Macaulay matrix corresponds to multiplication by $f$; so its elements are the coefficients of $f$. The rest of the columns correspond to a multiplication by $X^\beta \cdot (R'_0(T)X_i - R_i(T))$, for appropriate values of $\beta$ and $i$; the elements of each of these columns are all zero except for two entries, that are $R'_0(T)$ and $R_i(T)$. As the coefficients of $f$ only appear in one column of the Macaulay matrix, we conclude that the rank of the matrix obtained by excluding this column is $E - 1$, where $E$ is the number of monomials in $\mathbb{Z}[X]_{Q+L+\bar{\epsilon}}$ or, equivalently, the number of integer points in $(Q + L + \bar{\epsilon}) \cap \mathbb{Z}^n$. This is so because the system $R'_0(T)X_1 - R_1(T) = 0, \dots, (R'_0(T)X_n - R_n(T)) = 0$ has nonzero solutions in $\mathbb{C}(T)^n$ and thus, the Sylvester map associated to it (and consequently the aforementioned matrix) is not full rank [DJ24, Thm 1.8]. However, the rank has to be greater or equal to $E - 1$, as we can always find some $f$ that does not vanish at this solution, so the original Sylvester map has to be full-rank. In particular, if we assume that $\#(2Q \cap \mathbb{Z}^n) \ge \#((Q + L + \bar{\epsilon}) \cap \mathbb{Z}^n)$, then, by Lem. 2.10, we have that $E \le 2^{n+1} n! \mathrm{vol}(Q)$. As the map Sylv is surjective, we can extract a square invertible maximal submatrix of its corresponding (Macaulay) matrix. We denote this matrix as $M \in \mathbb{Z}[T]^{E \times E}$. Notice that $M$ has to contain a column with the coefficients of $f$.

The determinant of $M$, $\det(M) \in \mathbb{Z}[T]$ has degree at most $E \cdot n! \cdot \mathrm{vol}(Q)$ and bitsize $\tilde{\mathcal{O}}(E(n+1)! \mathrm{vol}(Q)(n+\tau))$ (Cor. 3.10). By Cramer's rule, using the adjugate matrix of $M$, $\mathrm{adj}(M)$, we have that $\det(M) \cdot v = M \cdot \mathrm{adj}(M) \cdot v$, for any vector $v$. We observe that at least one vertex of $Q$ belongs to $(Q + L + \bar{\epsilon}) \cap \mathbb{Z}^n$. So, by Theorem 3.11, there is a monomial $\mathbf{X}^{2\alpha}$ in $\mathbb{Z}[T][\mathbf{X}]_{Q+L+\bar{\epsilon}}$. Putting all together, we find the preimage of $\det(M)\mathbf{X}^{2\alpha} \in \mathbb{Z}[T][\mathbf{X}]_{Q+L+\bar{\epsilon}}$, given by polynomials in the ring $\mathbb{Z}[T][\mathbf{X}]$. That
is, there are polynomials $G(T)$, $\bar{q}_1(T, \mathbf{X})$, ..., $\bar{q}_n(T, X) \in \mathbb{Z}[T][\mathbf{X}]$ such that $G(T) \in \mathbb{Z}[T][\mathbf{X}]_{L+\varepsilon} = \mathbb{Z}[T]$, each $\bar{q}_1(T, \mathbf{X}) \in \mathbb{Z}[T][\mathbf{X}]_{L_1+\varepsilon}$, and

$$G(T)f(\mathbf{X}) - \sum_{i} \bar{q}_i(\mathbf{X}, T)(R_0'(T)X_i - R_i(T)) = (\mathbf{X}^{\alpha})^2 \det(M). \quad (14)$$

The coefficients of these polynomials, if we consider them as polynomials in $\mathbf{X}$ with coefficients in $\mathbb{Z}[T]$, are determinants of submatrices of $M$ of size $E-1$. Also $G(T)$ is not zero. The degree of $G(T)$ is at most $(E \cdot n! \cdot \mathrm{vol}(Q))$ and its bitsize $\tilde{O}(E(n+1)! \mathrm{vol}(Q)(n+\tau))$. Each $\bar{q}_i(X, T)$ has degree with respect to $T$ at most $((E-1) \cdot n! \cdot \mathrm{vol}(Q))$ and bitsize $\tilde{O}(E(n+1)! \mathrm{vol}(Q)(n+\tau))$. Moreover, because the matrix $M$, without the column involving the coefficients of $f$, has rank $E-1$, it follows that $G(T) \neq 0$. We conclude the proof by multiplying both sides of (14) by $G(T)$, setting $r(T) := G(T) \cdot \det(M)$, and $q_i(T, X) := G(T) \cdot \bar{q}_i(T, X)$, for $i \in [n]$. $\square$

**Lemma 3.13.** *Assuming that the (sparse) RUR($I_{\nabla f}$) is available, we can compute the representation supported by Lem. 3.12 in $\tilde{O}_B(n^{2(\omega+2)n+O(1)} \mathrm{vol}(Q)^{\omega+3}\tau)$ bit operations.*

*Proof.* We use the notation and the algebraic objects introduced in the proof of Lem. 3.12. The polynomial $G$ and the coefficients of $q_i$'s, if we consider them as polynomials in $\mathbf{X}$, are polynomials in $\mathbb{Z}[T]$ and each one of them is a minor of the (Macaulay) matrix $M$. The size of these minors is at most $E$. The elements of $M$ are polynomials in $\mathbb{Z}[T]$ of degree at most at most $n! \mathrm{vol}(Q)$. We can compute each a minor in $\tilde{O}_B(E^\omega \delta)$ arithmetic operations [LNZ17], where $\delta$ upper bounds the average degree of the polynomials in the columns (or the rows) of the matrix. Looking at the columns, the first column has only constants, thus the average degree is 0. The other columns have at most two nonzero elements that contain the polynomials $R_0$ and $R_i$; the latter have degree $n! \mathrm{vol}(Q)$. As $E \le 2^{n+1} n! \mathrm{vol}(Q)$, we can assume that $\delta = O(1)$. So, we compute the minors in $\tilde{O}_B(E^\omega (\lg E)^c)$ arithmetic operations [LNZ17], for some small constant $c$. As the polynomials have bitsize at most $\tilde{O}(2^n (n+1)!^2 \mathrm{vol}(Q)^2 (n+\tau))$ (Theorem 3.12), the bit complexity to compute a minor is the bit complexity is $\tilde{O}_B(E^\omega (\lg E)^c \cdot 2^n (n+1)!^2 \mathrm{vol}(Q)^2 (n+\tau))$. We have to perform this at most $O(E)$ times to recover $G$ and all the coefficients of $q_i$'s, the total complexity is

$$\tilde{O}_B(E^{\omega+1} (\lg E)^c 2^n (n+1)!^2 \mathrm{vol}(Q)^2 (n+\tau)).$$

By taking into account that $E \le 2^{n+1} n! \mathrm{vol}(Q)$ (Theorem 2.10), the overall complexity becomes

$$\tilde{O}_B(2^{(\omega+2)n} (n+1)!^{2\omega+4+O(1)} \mathrm{vol}(Q)^{\omega+3}(n+\tau)),$$

which after some simplifications leads to the claimed bound. $\square$

**Remark 3.14.** *If we specialize the previous bound to the dense case, then we obtain a bound that is worse than the one in Theorem 3.9 by a square factor. To improve our sparse bound to match the one of Theorem 3.9, we would need a division algorithm for sparse polynomials with a priori bounds on the sparsity structure of the quotients. We do not exploit this direction further. Regarding the complexity aspects of this problem, we refer the reader to [Hoe17].*

**Sparse certificates of positivity and their bit complexity** The next lemma exploits the representation from (12) to construct sparse certificates of positivity. We omit its proof as it is the same as the one of Theorem 3.2.

**Lemma 3.15.** *With the assumptions and notation from Theorem 3.12, assume that $f$ attains its infimum. Then, $f \ge 0$ if and only if $r(T) \ge 0$.*

**Theorem 3.16.** Let $f \in \mathbb{Z}[X]$ be a polynomial of size $(d, \tau)$ and let $Q \subset \mathbb{R}^n$ be its Newton polytope. Assume that Vertices($Q$) $\subset (2 \cdot \mathbb{Z})^2$, the gradient ideal $I_{\nabla f}$ is zero-dimensional, and $f$ attains its infimum. Then, there is an algorithm such that,

* If $f(\mathbf{x}) < 0$, for some point(s) $\mathbf{x} \in \mathbb{Q}^n$, then it outputs such a witness point.
* If $f$ is nonnegative, then it outputs the polynomials of a (sparse) RUR of $I_{\nabla f}$, which is RUR($I_{\nabla f}$) = $(R_0(T), R_1(T), \dots, R_n(T), T - \sum_{i=1}^n \lambda_i X_i)$, where $R_i \in \mathbb{Z}[T]$, and polynomials $q_i \in \mathbb{Z}[T][\mathbf{X}]_{\hat{\mathcal{I}}_i}$, and $r(T), G(T) \in \mathbb{Z}[T]$, as well as the polynomials $s_j \in \mathbb{Q}[T]$ and the numbers $w_j \in \mathbb{Q}_+$, for $j \in [\nu]$, such that

$$G(T)^2 f(\mathbf{X}) = \sum_i q_i(\mathbf{X}, T) (R'_0(T)X_i - R_i(T)) + (\mathbf{X}^\alpha)^2 r(T), \text{ with } r = \sum_{j=1}^\nu w_j s_j^2.$$

It holds that $2\alpha \in \mathbb{Q}$. Moreover, $G$, $r$, and the coefficients of each $q_i$ in $\mathbb{Z}[T]^5$ have degree at most $2^{n+2} n!^2 \text{vol}(Q)^2$ and bitsize $\tilde{\mathcal{O}}(2^n (n+1)!^2 \text{vol}(Q)^2(n+\tau))$.

The bit complexity of the algorithm is $\tilde{\mathcal{O}}_B(n^{6n} \text{vol}(Q)^6 \tau)$, while the largest bitsize of the rationals appearing in the decomposition (or the witness point) is $\tilde{\mathcal{O}}(n^{4n} \text{vol}(Q)^4 \tau)$.

*Proof.* Following Lem. 3.13 we can compute all the polynomials in this sparse weighted SOS representation of (12) in $\tilde{\mathcal{O}}_B(n^{2(\omega+2)n+\mathcal{O}(1)} \text{vol}(Q)^{\omega+3} \tau)$ bit operations.

The polynomials in the variable $T$ have size $(2^{n+2} n!^2 \text{vol}(Q)^2, \tilde{\mathcal{O}}(2^n (n+1)!^2 \text{vol}(Q)^2(n+\tau)))$.

Using Prop. 2.20, we can write $r$ as a weighted SOS in $\tilde{\mathcal{O}}_B(2^{3n} n!^6 \text{vol}(Q)^6 (n+\tau))$. The bitsize of the coefficients is $\tilde{\mathcal{O}}(2^{2n} n!^4 \text{vol}(Q)^4 (n+\tau))$. These bounds, as in the dense case, dominate the ones for the computation of the witness point. The claimed bounds follow after simplifications. $\square$

## 3.4 The case of a radical gradient ideal

In the case where the gradient ideal, besides being zero-dimensional, is also radical, our representation is close to the SOS representation appeared in [MSEDV23], which is valid only in the case of radical gradient ideals; however, the polynomials involved in our representation, especially the remainder, are of smaller degree. Even more, if we assume that there are no solutions at infinity, as the other approaches, then complexity of SOS-RUR is also better than the other algorithms.

Magron et al [MSEDV23] consider, after performing a generic linear change of variables, that the separating linear form is $T - X_1$, to compute the RUR. Then, using this RUR, they obtain the remainder $r$ by the substitution

$$r = \text{numer} \left( f(X_1, \frac{R_2(X_1)}{R_0'(X_1)}, \dots, \frac{R_n(X_1)}{R_0'(X_1)}) \right) \in \mathbb{R}[X_1].$$

If the monomial $X_1^d$ exists in $f$, which is the case when $f$ is dense, then the degree bound of $r$ is $d(d-1)^n$ as polynomial in $\mathbb{R}[X_1]$, since we have to multiply $X_1^d$ with $R_0'(X_1)^d$ to clear denominators, and the latter is of degree bound $d((d-1)^n - 1)$, see Cor. 2.15 and Rem. 2.16.

On the other hand, SOS-RUR considers a generic (that in addition certifies that is appropriate) separating linear form. After computing the RUR, we obtain the remainder by the substitution

$$r = \text{numer} \left( f\left(\frac{R_1(T)}{R_0'(T)}, \dots, \frac{R_n(T)}{R_0'(T)}\right) \right) \in \mathbb{R}[T].$$

This results in a polynomial of degree bound $d(d-1)^n - d$ as polynomial in $\mathbb{R}[T]$. Thus, the representation supported by SOS-RUR, in the case of radical ideals, involves polynomials having degree less by an additive factor of $d$, compared to other approaches. We demonstrate the previous discussion with the following example, that also appears in [MSEDV23].

**Example 3.17.** We consider Scheiderer's, degree 4, polynomial

$$f = X_1^4 + X_1 X_2^3 + X_2^4 + 3X_1^2 X_2 + 4X_1 X_2^2 + 2X_1^2 - X_1 - X_2 + 1.$$

The corresponding gradient ideal is radical. If we consider the separating linear form $T - X_2$, then we obtain the following RUR:

$$R_0 = 4T^9 + T^6 - 16T^5 - 4T^3 - 4T^2 - 1, \qquad (15)$$

$$R_1 = 15T^7 - 32T^6 - 9T^4 - 36T^3 - 6T - 4, \qquad (16)$$

$$R_2 = -3T^6 + 64T^5 + 24T^3 + 28T^2 + 9. \qquad (17)$$

<footnote n="5">⁵We consider each $q_i$ as a sparse polynomials in $\mathbf{X}$ with coefficients in $\mathbb{Z}[T]$</footnote>
After we do the substitution $X_1 = R_1/R'_0$, and $X_2 = R_2/R'_0$, we obtain the nonnegative polynomial

$$r(T) = (1679616T^{20} - 699840T^{19} + 2216160T^{18} - 4354560T^{17} + 1208925T^{16} + 1391472T^{15} - 5740416T^{14} \\ + 10025025T^{13} + 1244857T^{12} - 17280T^{11} + 8037267T^{10} + 18304T^{9} + 1608984T^{8} + 2094993T^{7} \\ + 20166T^{6} + 494640T^{5} + 203199T^{4} + 28276T^{3} + 44280T^{2} + 4074T + 3901)(T^{6} - 4T^{2} - 1)^{2}.$$

The degree of $r$ is 32 as predicted by the theory.

In [MSEDV23], the authors compute the same polynomials for the RUR as in (15) and they also take as the separating linear form the polynomial $T - X_2$.<fnref n="6" /> The substitution $f(R_1(X_2)/R'_0(X_2), X_2)$ results in the polynomial

$$r(X_2) = (1679616X_2^{24} + 699840X_2^{22} + 746496X_2^{21} - 5785344X_2^{20} + 104976X_2^{19} - 3149280X_2^{18} - 3856896X_2^{17} \\ + 3777921X_2^{16} - 1139616X_2^{15} + 2471040X_2^{14} + 4610472X_2^{13} + 3168688X_2^{12} + 2222208X_2^{11} + 2778072X_2^{10} \\ + 1348000X_2^{9} + 712800X_2^{8} + 588960X_2^{7} + 214080X_2^{6} + 86400X_2^{5} + 51216X_2^{4} + 13696X_2^{3} \\ + 3456X_2^{2} + 1536X_2 + 256)(X_2^{6} - 4X_2^{2} - 1)^{2}.$$

The degree of $r$ is 36, as predicted previously.

In addition to degree, the bit size of the polynomials that appear in the SOS representation by our approach is of the order $\tilde{O}(d^{2n+1}(d+n\tau))$ (Thm. 3.9) which is better by a factor of $d^n$ compared with other approaches [MSEDV23].

Recall that the complexity of SOS-RUR is dominated by the computation of the RUR. However, if we assume, as the other approaches in the case of radical ideals, that there are no solutions at infinity, then we can compute the RUR faster, see Rem. 2.17. Hence, the complexity of SOS-RUR is $\tilde{O}_B(n^{\omega n} d^{(\omega+1)n-1} (d+\tau))$ that is also better than all the other approaches. The following corollary summarizes this section.

**Corollary 3.18.** Consider $f \in \mathbb{Z}[X]$ of size $(d, \tau)$. Assume that the gradient ideal of $f$ is zero-dimensional, it has no solutions at infinity, and $f$ attains its infimum.

If $f$ is nonnegative, then SOS-RUR computes a weighted SOS decomposition of $f$ modulo the ideal $I_{\text{RUR}(\nabla f)}$, as in (9), in $\tilde{O}_B(e^{\omega n} d^{(\omega+1)n-1} (d+\tau))$ bit operations, where $\omega$ is the exponent of matrix multiplication. The polynomials involved in the decomposition have degrees at most $d(d-1)^n - d$ and their largest coefficient has bitsize $\tilde{O}(d^{2n+1}(d+n\tau))$.

# 4 Validation (of the correctness) of the certificate

Let $f \in \mathbb{Q}[X]$ be size $(d, \tau)$ such that it has a zero-dimensional gradient ideal and attains its infimum. We assume, that an algorithm provides us with the polynomials $r, R_0, R_i \in \mathbb{Q}[T]$, $q_i \in \mathbb{Q}[X, T]$, for $i \in [n]$, and $s_j \in \mathbb{Q}[T]$, $w_j \in \mathbb{Q}_+$, for $j \le \text{deg}(r) + 3$, of degrees and bitsize according to Thm. 3.9 and (9). Moreover, the algorithms claims that its output satisfies (9) and consequently $f$ is nonnegative. As mentioned in the introduction, and demonstrated in Example 1.2, the validity of (9), or (1) alone it is not enough to certify the nonnegativity of $f$.

To validate the nonnegativity claim we have to perform the following two tasks:

(i) Test the validity of the algebraic identity (9), that is to check if the lhs equals the rhs. For this task we also need to check if the decomposition of the remainder $r$ as a weighted SOS is correct.

(ii) Verify that the RUR of the gradient ideal $\text{RUR}(I_{\nabla f}) = (R_0(T), R_1(T), \dots, R_n(T), T - \sum_{i=1}^n \lambda_i X_i)$ is correct (up to a finite number of some additional points); that is ensure that it encodes all the points of $\mathbb{V}_C(I_{\nabla f})$ and $T - \sum_{i=1}^n \lambda_i X_i$ is a separating linear form.

These two tasks validate the certificate of nonnegativity and its correctness. In what follows, we give details on their algorithmic counterpart and analyze their bit complexity.

**Remark 4.1.** In Alg. 1, we compute the exact RUR of the gradient ideal $I_{\nabla f}$. However, to certify that this (or a) RUR is good enough, we need to certify that it contains all critical points.

<footnote n="6">⁶The example provided in [MSEDV23] is wrong: instead of considering the separating linear form $T - X_1$ in their computations, they consider $T - X_2$ and mistakenly interchange both variables. We fix their example in this exposition.</footnote>
**Validation of the algebraic identity** First, we consider the validation of the weighted SOS decomposition of $r$. Recall that $r$ has size $(d(d-1)^n, \tilde{O}(d^n(d+n\tau))$ (Lem. 3.6). To verify the decomposition of $r$, which is $r = \sum_{j=1}^{\nu} w_j s_j^2$, where $w_j \in \mathbb{Q}_+$ and $s_j \in \mathbb{Q}[T]$, we need to perform $O(\deg(r)) = \tilde{O}(n)$ univariate polynomial multiplications to compute the squares $s_j^2$. Each polynomial multiplication requires $\tilde{O}(\deg(r))$ operations. We perform the multiplications and the addition needed afterwards using multimodular arithmetic; it suffices to use primes of bitsize at most the bitsize of $r$. Thus, the overall complexity is $\tilde{O}_B(nd^{2n+1}(d+n\tau))$ bit operations.

For validating (9) we proceed as follows. The $\text{lhs}$ of (9), $R_0^d f$, requires to compute $R_0^d$ and then multiply it by $f$. For the former, we need $O(\lg d)$ multiplications of univariate polynomials of degree $O(d^{n+1})$; each multiplication requires $\tilde{O}(d^{n+1})$ arithmetic operations. The multiplication with $f$ is dominated. The result, $R_0^d f$, has bitsize $\tilde{O}(d^n(d+n^2+\tau))$. We can perform all the multiplications using multimodular techniques with primes of bitsize $\tilde{O}(d^n(d+n^2+\tau))$. Thus, we compute the $\text{lhs}$ in $\tilde{O}_B(d^{2n+1}(d+n^2+\tau))$. The $\text{rhs}$ of (9) requires us to perform $n+1$ multiplications of multivariate polynomials, $q_i(R_0'X_i - R_i)$, of total degree $\tilde{O}(d^{n+1})$; each needs $\tilde{O}(d^{n+1})$ operations. As before, we can use multimodular arithmetic with primes of bitsize the bitsize of the result, that is $R_0^d f$. Finally, the bitsize of the primes is $\tilde{O}(d^n(d+n^2+\tau))$ and the overall validation costs $\tilde{O}_B(nd^{2n+1}(d+n^2+\tau))$.

**Lemma 4.2.** *The cost of validating the algebraic identity (9) is $\tilde{O}_B(nd^{2n+1}(d+n^2+\tau))$ bit operations. At the same cost, we also validate the weighted SOS decomposition of $r$.*

**Validating the correctness of RUR** We introduce Cor. 4.4 to validate that a set of polynomials $\{R_0(T), R_1(T), \dots, R_n(T), T - \sum_{i=1}^n \lambda_i X_i \in \mathbb{Q}[X, T]\}$ consist a RUR for the gradient ideal of $f$ (possibly also encoding a finite number of additional points) and the linear form is separating over the gradient variety. This result is a direct consequence of Lem. 4.3, based on Rabinowitsch trick, that gives a condition to check if a variety is contained in another, and leads to Alg. 2.

**Lemma 4.3.** Let $f_1, \dots, f_s, g_1, \dots, g_t \in \mathbb{K}[X]$, where $\mathbb{K}$ is a field. Then,

$$ \mathbb{V}(f_1, \dots, f_s) \subseteq \mathbb{V}(g_1, \dots, g_t) \iff \mathbb{V}(f_1, \dots, f_s, Yg_i - 1) = \emptyset, \text{ for all } i \in [t], $$

where $Y$ is a new variable.

*Proof.* ($\implies$) Assume that there is a $(x, y) \in \mathbb{V}(f_1, \dots, f_s, Yg_i - 1)$, for some $i \in [t]$; wlog say that $i=1$. Then, $g_1(x) \neq 0$ and so $x \notin \mathbb{V}(g_1, \dots, g_t)$. However, $x \in \mathbb{V}(f_1, \dots, f_s)$, which contradicts the condition $\mathbb{V}(f_1, \dots, f_s) \subseteq \mathbb{V}(g_1, \dots, g_t)$.

($\Leftarrow$) Assume that there an $x \in \mathbb{V}(f_1, \dots, f_s) \setminus \mathbb{V}(g_1, \dots, g_t)$. Then, there exists an $i \in [t]$ such that $g_i(x) \neq 0$; wlog say $i=1$. Therefore, $(x, \frac{1}{g_1(x)}) \in \mathbb{V}(f_1, \dots, f_s, Yg_1 - 1)$, which contradicts $\mathbb{V}(f_1, \dots, f_s, Yg_1 - 1) = \emptyset$. $\square$

Using the previous proposition, we can provide conditions to ensure that a set of polynomials is the RUR of the gradient ideal of a polynomial (possibly encoding a finite number of additional points).

**Corollary 4.4.** Let $f \in \mathbb{Q}[X]$, $\{R_0(T), R_1(T), \dots, R_n(T)\}$ be a set of polynomials in $\mathbb{Q}[T]$ where $R_0(T)$ is square-free and of strictly higher degree than the other polynomials. Consider a linear form $T - \sum_{i=1}^n \lambda_i X_i \in \mathbb{Q}[X, T]$.

If

$$ \begin{align*} \mathbb{V}_{\mathbb{C}}(\partial_1 f, \dots, \partial_n f, T - \sum_{i=1}^n \lambda_i X_i, R_0(T)Y - 1) &= \emptyset, \quad \text{and} \\ \mathbb{V}_{\mathbb{C}}(\partial_1 f, \dots, \partial_n f, T - \sum_{i=1}^n \lambda_i X_i, (R_0'X_j - R_j)Y - 1) &= \emptyset, \quad \forall j \in [n], \\ \text{then } \mathbb{V}_{\mathbb{C}}(\partial_1 f, \dots, \partial_n f, T - \sum_{i=1}^n \lambda_i X_i) &\subseteq \mathbb{V}_{\mathbb{C}}(R_0, R_0'X_1 - R_1, \dots, R_0'X_n - R_n). \end{align*} $$

Moreover, the set $\{R_0(T), R_1(T), \dots, R_n(T)\}$ is a RUR of $I_{\nabla f}$ (possibly encoding a finite number of additional points) and the linear form $T = \sum_{i=1}^n \lambda_i X_i$ is a separating linear form on $\mathbb{V}_{\mathbb{C}}(I_{\nabla f})$. In particular, any real critical point can be parametrized by a real parameter $t$.
Proof. By the previous proposition, we have

$$ \mathbb{V}_{\mathbb{C}}(\partial_1 f, \dots, \partial_n f, T - \sum_{i=1}^n \lambda_i X_i) \subseteq \mathbb{V}_{\mathbb{C}}(R_0(T), R'_0(T)X_1 - R_1(T), \dots, R'_0(T)X_n - R_n(T)) $$

So that $Q$ is a rational univariate representation of a variety containing $\mathbb{V}_{\mathbb{C}}(I_{\nabla f})$ with respect to the linear form $T = \sum_{i=1}^n \lambda_i X_i$. Now $\forall \mathbf{x} \in \mathbb{V}_{\mathbb{R}}(\partial_1 f, \dots, \partial_n f)$, let $t = \sum_{i=1}^n \lambda_i x_i$, then $(\mathbf{x}, t) \in \mathbb{V}_{\mathbb{C}}(\partial_1 f, \dots, \partial_n f, T - \sum_{i=1}^n \lambda_i X_i) \subseteq \mathbb{V}_{\mathbb{C}}(R_0, R'_0 X_1 - R_1, \dots, R'_0 X_n - R_n)$. Notice that $t$ is real because each $\lambda_i$ and $x$ are. Thus, we have $(\mathbf{x}, t) \in \mathbb{V}_{\mathbb{R}}(R_0, R'_0 X_1 - R_1, \dots, R'_0 X_n - R_n)$ which means $\mathbf{x}$ is parametrized by the real parameter $t$. Moreover, once fixed $t$, there is at most one solutions for the system $R'_0(t)X_1 - R_1(t) = 0$, so $x$ is uniquely defined, that is, the linear form $\sum_{i=1}^n \lambda_i X_i$ separates the roots of the gradient ideal. $\square$

Cor. 4.4 directly implies an algorithm to validate the RUR. The pseudo-code appears in Alg. 2.

**Algorithm 2 Is-the-RUR-sufficient**

**Input:** $f \in \mathbb{Q}[\mathbf{X}]$ and a set of polynomials $\{R_0(T), R_1(T), \dots, R_n(T), \sum_{i=1}^n \lambda_i X_i\}$, where $R_0, R_i \in \mathbb{Q}[T]$ and $\lambda_i \in \mathbb{Q}$, for $i \in [n]$.

**Assumptions:** The gradient ideal $I_{\nabla f}$ is zero-dimensional.

**Output:** YES if the set of polynomials is a RUR for $I_{\nabla f}$ (possibly encoding a finite number of additional points), NO otherwise.

Check if there are polynomials $g_i^j \in \mathbb{Q}[\mathbf{X}, T, Y]$ where $i \in [n+2]$ and $0 \le j \le n$, such that

$$ \sum_{i=1}^{n} g_i^0 \partial_i f + g_{n+1}^0 (T - \sum_{i=1}^{n} \lambda_i x_i) + g_{n+2}^0 (R_0 Y - 1) = 1, \quad (18) $$

$$ \sum_{i=1}^{n} g_i^j \partial_i f + g_{n+1}^j (T - \sum_{i=1}^{n} \lambda_i x_i) + g_{n+2}^j ((R'_0 X_j - R_j)Y - 1) = 1, \quad \forall j \in [n]. \quad (19) $$

If this is the case, then return YES, as it holds (see Cor.4.4)

$$ \mathbb{V}_{\mathbb{C}}(\partial_1 f, \dots, \partial_n f, T - \sum_{i=1}^{n} \lambda_i x_i) \subseteq \mathbb{V}_{\mathbb{C}}(R_0, R'_0 X_1 - R_1, \dots, R'_0 X_n - R_n). $$

Otherwise, return NO.

Alg. 2, Is-the-RUR-sufficient, validates the RUR by attesting the algebraic identities in (18) and (19), imposed by the Hilbert's Nullstellensatz. We notice that the algebraic identities are linear equations in the coefficients of the polynomials $g_i^j$. Hence, if we bound the degrees of $g_i^j$'s, then it suffices to solve a linear system with unknowns the coefficients of $g_i^j$'s. Even more, if we have bounds on the bitsize of these coefficients, then we can also estimate the bit complexity of the whole procedure and the bitsize of the certificates. We obtain the degree and bitsize bounds for the effective and arithmetic version of Hilbert's Nullestellensatz.

To bound the degrees of the polynomials $g_i^j$ we exploit the sparse version of the effective Nullstellensatz by Sombra (Thm. 2.18) [Som99] to exploit the structure of the polynomials appearing in the algebraic identities (18) and (19). First, let the Newton polytope of $f$ to be $Q$.

As the identities in (18) and (19) are similar, it suffices to consider one of them to obtain worst case bounds. Let assume the following:

$$ \sum_{i=1}^{n} g_i^1 \partial_i f + g_{n+1}^1 (T - \sum_{i=1}^{n} \lambda_i x_i) + g_{n+2}^1 ((R'_0 X_1 - R_1)Y - 1) = 1. $$

Consider $F_1 := \frac{\partial f}{\partial x_1}, \dots, F_n := \frac{\partial f}{\partial x_n}, F_{n+1} := T - \sum_{i=1}^{n} \lambda_i x_i, F_{n+2} := (R'_0(T)X_j - R_j(T))Y - 1$. Then, using Thm. 2.18, it holds

$$ \deg(g_i^j F_i) \le n^{n+3} d \mathcal{V} = n^{n+3} d \mathrm{vol}(\mathcal{N}), $$

where $d := \max_{1 \le i \le n+2} \deg(F_i)$ and $\mathcal{V}$ is the unmixed volume of the Newton polytope $\mathcal{N}$ of the polynomials $x_1, \dots, x_n, T, Y, F_1, \dots, F_{n+2}$.

To simplify notation, let us assume that the size of the polynomials $R_i$ is $(\delta, L)$; we refer to Thm. 2.12 and Cor. 2.15 for their specific values. Recall that the degree of $R_0$, in this case $\delta$ bounds the degree of
the gradient ideal. Consequently, the polynomials $R_i$ have the largest degree among the polynomials we consider; hence $d \le \delta$. Additionally, we assume that $\delta = O(n! \text{vol}(Q))$.

We assume that the polytope $Q$, the Newton polytope of $f$, contains the $n$-dimensional standard simplex $Q_0$ over $\mathbb{R}^n$. Our objective is to bound the polytope $\mathcal{N}$:

* All the derivatives of $f$ are contained in (integer displacements of) $Q$.

* Consider the Newton polytope of the polynomial $T - \sum_i \lambda_i X_i$. This polytope is contained in the Minkowski sum of the segment $[0, 1]_T$ corresponding to the Newton polytope of $1+T$ and $Q$, as $Q_0 \subseteq Q$.

* Lastly consider the Newton polytope of the polynomial $(R'_0(T)X_j - R_j(T))Y - 1$. By a similar argument, it is contained in the Minkowski sum of $[0, 1]_{X_j}$, corresponding to the Newton polytope of $1+X_j$, $[0, \delta]_T$, corresponding to the Newton polytope of $1+T^\delta$ and $\delta \sim n! \text{vol}(Q)$, and $[0, 1]_Y$, corresponding to the Newton polytope of $1+Y$.

Therefore, $\mathcal{N} \subset Q \times [0, 1]_Y \times [0, \delta]_T$. Using this decomposition, we bound the volume of $\mathcal{N} \subset \mathbb{R}^{n+2}$ as $\text{vol}(\mathcal{N}) \le \frac{\delta^{2+\delta}}{n!}$.

To bound the bitsize of the polynomials $g_i^j$ we rely on arithmetic Nullstellensatz (Thm. 2.19).

$$ 
\begin{aligned}
h(g_i^j) &\le (n+3)^3 \delta (n+2)! \text{vol}(\mathcal{N})(L + \lg(n+2) + 2^{2n+8}\delta \lg(\delta+1)) \\
&\le (n+3)^3 \delta (n+2)^2 (\delta^2 + \delta)(L + \lg(n+2) + 2^{2n+8}\delta \lg(\delta+1)) \\
&= \tilde{O}(\delta^3 n^5 (L + 2^{2n}\delta \lg(\delta))).
\end{aligned}
$$

As $L = \tilde{O}((n+1)! \text{vol}(Q)(n+\tau)) = \tilde{O}(n\delta(n+\tau))$, the bound becomes

$$ 
\begin{aligned}
h(g_i^j) &= \tilde{O}(n^5 \delta^4 (n(n+\tau) + 2^{2n}\delta \lg \delta)) \\
&\subseteq \tilde{O}\left(\frac{n^9 2^{2n}}{e^{4n}} n^{4n} \text{vol}(Q)^4 (\tau + \lg \text{vol}(Q))\right) \\
&\subseteq \tilde{O}(n^{4n} \text{vol}(Q)^4 (\tau + \lg(\text{vol}(Q)))).
\end{aligned}
$$

Following Thm. 2.12 the polynomials $g_i^j$ have size

$$ (\tilde{O}(n^{3n} \text{vol}(Q)^3), \tilde{O}(n^{4n} \text{vol}(Q)^4 (\tau + \lg(\text{vol}(Q)))). $$

**Theorem 4.5.** Let $f \in \mathbb{Z}[X]$ be of size $(d, \tau)$. Assume that its gradient ideal, $I_{\nabla f}$, is zero-dimensional. Consider a set of polynomials $\{R_0(T), R_1(T), \dots, R_n(T), \sum_{i=1}^n \lambda_i X_i\}$, where $R_0, R_i \in \mathbb{Q}[T]$ and $\lambda_i \in \mathbb{Q}$, for $i \in [n]$. Assume that the Newton polytope of $f$, $Q$, contains the $n$-dimensional standard simplex and the maximum degree of the polynomials $R_i$ is proportional to $n! \text{vol}(Q)$. The maximum degree and bitsize of the coefficients of the polynomials involved in the verification of the RUR, see Eq. (18) and (19), is

$$ (\tilde{O}(n^{3n} \text{vol}(Q)^3), \tilde{O}(n^{4n} \text{vol}(Q)^4 (\tau + \lg(\text{vol}(Q)))). $$

The algorithm Is-the-RUR-sufficient verifies a RUR of the gradient ideal of $f$ at the cost of

$$ \tilde{O}_B(n^{(3\omega+4)n} \text{vol}(Q)^{3\omega+4} (\tau + \lg(\text{vol}(Q)))) \text{ bit operations,} $$

where $\omega$ is the exponent of matrix multiplication.

*Proof.* It suffices to construct the linear systems corresponding to the identities in (18) and (19), where the unknowns are the coefficients of the polynomials $g_i^j$. The dimension of the corresponding matrices is the degree(s) of the polynomials. Hence, the overall bit complexity at most the dimension to the power of $\omega$ times the (worst case) bitsize. $\square$

**Remark 4.6.** To express the bounds of the previous theorem using the degree of $f$, instead of using the volume of the Newton polytope, we can consider the rough estimate $\text{vol}(Q) \le d^n$. Then, the size of the polynomials is $(\tilde{O}((nd)^{3n}), \tilde{O}((nd)^{4n}\tau))$, while the bit complexity becomes $\tilde{O}_B((nd)^{(3\omega+4)n}\tau)$.
The complexity of Thm 4.5 is worse than the complexity of actually computing RUR. Nevertheless, it is not clear if we can improve it significantly when we aim at worst case bounds. If we relax our requirements and we opt for randomized algorithms, then we can achieve better (bit) complexity bounds based on the Koiran's [Koi96] results that put the problem of feasibility in Arthur-Merlin complexity class. We do not proceed in this direction further.

**Remark 4.7 (Enhanced certificates).** It is worth noting that we can compute the polynomials {$g_j^i$}$_{i,j}$ realizing the identities in (18) and (19) as part of Alg. 1, instead of using them to verify the correctness of the certificates provided by Alg. 1. This leads to an enhanced certificate that we verify faster, at the cost of a slower algorithm to compute it.

**Remark 4.8 (An alternative approach).** Whenever the gradient ideal $I_{\nabla f}$ is radical, we can certify that our rational univariate representation contains all the points of $\mathbb{V}(I_{\nabla f})$ by writing the polynomials $(R_0, R'_0 X_1 - R_1, \dots, R'_0 X_n - R_n)$ as a polynomial combination of the polynomials $(\partial_1 f, \dots, \partial_n f, T - \sum_i \lambda_i X_i)$, in $\mathbb{Q}[\mathbf{X}, T]$. If $I_{\nabla f}$ is not radical, then we can proceed similarly. The difference is that need to work with the polynomials $(R_0^k, (R'0X_1 - R_1)^k, \dots, (R'0X_n - R_n)^k)$, for some $k \in \mathbb{N}$. The power $k$ is bounded above by the maximal multiplicity of the points in $I_{\nabla f}$ and, more precisely, by the largest of the Loewy lengths of the maximal ideals of the local rings obtained by localizing $I_{\nabla f}$ at each point in $\mathbb{V}(I_{\nabla f})$. We do not proceed further in this direction.

# 5 Experimental evaluation

In general, it is difficult to sample uniformly from the cone of positive multivariate polynomials and therefore also difficult to obtain a representative family of positive instances for experiments. To ensure positivity, we restrict our attention to certain families of polynomials that are already sums of squares (SOS), while also having non-radical gradient ideals.

We present a set of experiments computing SOS representations of positive polynomials, see (9), using our prototype open-source implementation of SOS-RUR<fnref n="7" /> in MAPLE. The code relies on MAPLE's functionality for computing rational univariate representations (RURs) and the quotients appearing in (9). For the SOS representation of the univariate polynomials involved, we use the implementation of uSOS<fnref n="8" /> presented in [BDT25].

The computation times vary significantly—from a few seconds for polynomials with two or three variables to several hours for those with five variables. The overall performance of SOS-RUR depends on several sub-algorithms, and the timing strongly depends on their specific implementations. Notably, using the new RUR algorithm (not yet in MAPLE) of [DRR24] results in at least a fivefold speed-up; the next version of SOS-RUR will depend on this. As the dominant parameter influencing performance is the bitsize of the output, we decided to report only the bitsizes rather than the raw timings, as these better reflect the intrinsic computational complexity of the algorithms.

**Radical and non-radical gradient ideals.** The first set of experiments illustrates the growth of bitsizes when computing with non-radical gradient ideals. We consider random polynomials of the form

$$f(\mathbf{X}) = \ell_0(\mathbf{X})^4 + \sum_{i=1}^{n-1} \ell_i(\mathbf{X})^2 + 10^6,$$

where each $\ell_i(\mathbf{X})$, for $0 \le i \le n-1$, is a random linear form with integer coefficients in $[-10, 10]$. Such polynomials have non-radical gradient ideals.

Table 1 reports the results for $n \in \{2, 3, 4, 5\}$. The first three columns describe the input size. The number of complex critical points (counted with multiplicity) is $3^n$. The next two columns give the bitsizes of the RUR and the quotients $q_i$, see (9). The last three columns provide the degree and bitsize of the remainder $r(T)$, and the bitsize of its univariate SOS decomposition.

We obtain the SOS decomposition of $r(T)$ using our MAPLE implementation of the uSOS algorithm [BDT25]. As the number of variables increases, both the degree and bitsize of $r(T)$ grow rapidly, which in turn makes the SOS decomposition extremely large—its bitsize roughly scales with the product of these two quantities. The symbol '*' indicates that the computation of the SOS representation did not terminate within one hour.

<footnote n="7">⁷https://gitlab.inria.fr/cert/mpos</footnote>

<footnote n="8">⁸https://gitlab.inria.fr/cert/upos</footnote>
<table><caption>Table 1: Non-radical gradient ideal.</caption><thead><tr><th># vars</th><th>Degree</th><th>Input bitsize</th><th>RUR bsz</th><th>quotients bsz</th><th>remainder degree</th><th>remainder bsz</th><th>univ SOS bsz</th></tr></thead><tbody><tr><td>2</td><td>4</td><td>19</td><td>34</td><td>116</td><td>20</td><td>157</td><td>3086</td></tr><tr><td>3</td><td>4</td><td>19</td><td>218</td><td>675</td><td>76</td><td>898</td><td>32741</td></tr><tr><td>4</td><td>4</td><td>19</td><td>840</td><td>2539</td><td>260</td><td>3388</td><td>*</td></tr><tr><td>5</td><td>4</td><td>19</td><td>36602</td><td>10831</td><td>844</td><td>14442</td><td>*</td></tr></tbody></table>

We observe an exponential growth in all quantities with the number of variables. For $n = 2, 3$, the SOS decomposition remains tractable, but beyond $n = 4$, the size of the RUR and the remainder grows rapidly, and the univariate SOS step becomes very difficult to compute, even for 4 variables.

The second set of experiments considers the case of *radical gradient ideals*. Here, we consider random polynomials of the form

$$f(\mathbf{X}) = \ell_0(\mathbf{X})^4 + \sum_{i=1}^{n} \ell_i(\mathbf{X})^2 + 10^6,$$

where each $\ell_i(\mathbf{X})$, for $0 \le i \le n$, is again a random linear form with integer coefficients in $[-10, 10]$. Table 2 presents the results for $n \in \{2, 3, 4, 5\}$, with the same column interpretation as in the non-radical case.

<table><caption>Table 2: Radical gradient ideal.</caption><thead><tr><th># vars</th><th>Degree</th><th>Input bitsize</th><th>RUR bsz</th><th>quotients bsz</th><th>remainder degree</th><th>remainder bsz</th><th>univ SOS bsz</th></tr></thead><tbody><tr><td>2</td><td>4</td><td>19</td><td>67</td><td>216</td><td>32</td><td>292</td><td>6447</td></tr><tr><td>3</td><td>4</td><td>19</td><td>278</td><td>850</td><td>104</td><td>1135</td><td>89488</td></tr><tr><td>4</td><td>4</td><td>19</td><td>1123</td><td>2291</td><td>320</td><td>4522</td><td>*</td></tr><tr><td>5</td><td>4</td><td>19</td><td>4270</td><td>12834</td><td>968</td><td>17113</td><td>*</td></tr></tbody></table>

Compared with the non-radical case, the bitsizes of the RUR, quotients, and remainders are systematically larger. This is consistent with our intuition: when the gradient ideal is radical, the number of distinct solutions (the degree of variety) reaches the full Bézout bound, leading to higher-degree elimination polynomials and consequently larger coefficients. In contrast, the non-radical case involves multiplicities, which effectively reduce the degrees of intermediate polynomials. Hence, symbolic computations in the radical case tend to be more demanding, even though the underlying variety has a simpler geometric structure.

**Two families of polynomials with non-radical gradient ideal** The last two sets of experiments involve multivariate polynomials with non-radical gradient ideals. In both cases, the non-radicality arises because the gradient equations contain repeated factors, so that some critical points occur with multiplicities greater than one.

The first family contains polynomials of the form

$$f_A(\mathbf{X}) = \sum_{i=1}^{n} L_i(X_i)^d - \rho X_1^2 + 10^{10}, \qquad (20)$$

where $L_i$ is a random linear polynomial in $X_i$ with coefficients sampled uniformly from the interval $[-100, 100]$, and $\rho$ is an integer sampled uniformly from $[0, 100]$.

As shown in Table 3, the bitsize of both the RUR and the remainder grows moderately with the polynomial degree $d$ and the number of variables $n$. The growth is substantially smaller than in the previous families with generic random coefficients, because the structure of $f_A$—a sum of univariate components—reduces algebraic dependency between the variables.

The second family of polynomials has a slightly more complicated gradient ideal. Let $p(t) = p_1(t)^3 \prod_{i=1}^3 (a_{i,1}t - a_{i,0})$ be a univariate polynomial with a triple factor at the roots of $p_1$, and define

$$f_B(\mathbf{X}) = \left( \int p(X_1) dX_1 \right)^2 + \frac{1}{2} \sum_{i=2}^{n} L_i(X_i)^2 + 10, \qquad (21)$$
<table><caption>Table 3: SOS representations of polynomials $f_A$, (20).</caption><thead><tr><th># vars</th><th>Degree</th><th>Input<br>bitsize</th><th>RUR<br>bsz</th><th>quotients<br>bsz</th><th>remainder<br>degree</th><th>remainder<br>bsz</th><th>univ SOS<br>bsz</th></tr></thead><tbody><tr><td>2</td><td>4</td><td>33</td><td>28</td><td>108</td><td>12</td><td>141</td><td>231</td></tr><tr><td>2</td><td>6</td><td>40</td><td>42</td><td>248</td><td>28</td><td>289</td><td>383</td></tr><tr><td>2</td><td>8</td><td>54</td><td>60</td><td>479</td><td>56</td><td>540</td><td>613</td></tr><tr><td>3</td><td>4</td><td>33</td><td>37</td><td>137</td><td>12</td><td>179</td><td>255</td></tr><tr><td>3</td><td>6</td><td>41</td><td>52</td><td>302</td><td>30</td><td>353</td><td>638</td></tr><tr><td>3</td><td>8</td><td>54</td><td>59</td><td>463</td><td>52</td><td>517</td><td>817</td></tr><tr><td>4</td><td>4</td><td>33</td><td>37</td><td>135</td><td>12</td><td>177</td><td>263</td></tr><tr><td>4</td><td>6</td><td>41</td><td>58</td><td>329</td><td>30</td><td>386</td><td>682</td></tr><tr><td>4</td><td>8</td><td>56</td><td>71</td><td>547</td><td>56</td><td>614</td><td>952</td></tr><tr><td>5</td><td>4</td><td>33</td><td>44</td><td>158</td><td>12</td><td>209</td><td>310</td></tr><tr><td>5</td><td>6</td><td>41</td><td>61</td><td>339</td><td>30</td><td>397</td><td>750</td></tr></tbody></table>

where each $L_i$ is a random linear polynomial in $X_i$ with coefficients sampled uniformly from the interval $[-100, 100]$; the same holds for the coefficients $a_{i,j}$. In this construction, the derivative of the first term with respect to $X_1$ is proportional to $p(X_1)p'(X_1)$, which vanishes with multiplicity at the roots of $p_1(t)$; consequently, the gradient ideal is non-radical.

<table><caption>Table 4: SOS representations of polynomials $f_B$, (21).</caption><thead><tr><th># vars</th><th>Degree</th><th>Input<br>bitsize</th><th>RUR<br>bsz</th><th>quotients<br>bsz</th><th>remainder<br>degree</th><th>remainder<br>bsz</th><th>univ SOS<br>bsz</th></tr></thead><tbody><tr><td>2</td><td>14</td><td>79</td><td>64</td><td>896</td><td>150</td><td>960</td><td>3235</td></tr><tr><td>3</td><td>14</td><td>78</td><td>65</td><td>928</td><td>152</td><td>993</td><td>2449</td></tr><tr><td>4</td><td>14</td><td>80</td><td>67</td><td>949</td><td>150</td><td>1017</td><td>2907</td></tr><tr><td>5</td><td>14</td><td>82</td><td>63</td><td>909</td><td>147</td><td>974</td><td>3272</td></tr><tr><td>6</td><td>14</td><td>78</td><td>65</td><td>938</td><td>154</td><td>1004</td><td>2928</td></tr><tr><td>7</td><td>14</td><td>80</td><td>65</td><td>931</td><td>152</td><td>997</td><td>3292</td></tr><tr><td>8</td><td>14</td><td>81</td><td>68</td><td>980</td><td>154</td><td>1050</td><td>3278</td></tr><tr><td>9</td><td>14</td><td>76</td><td>65</td><td>936</td><td>154</td><td>1002</td><td>2660</td></tr><tr><td>10</td><td>14</td><td>83</td><td>68</td><td>986</td><td>154</td><td>1056</td><td>3354</td></tr></tbody></table>

The results in Table 4 show that the bitsize values remain relatively stable as the number of variables increases, which indicates that the computational complexity is dominated by the univariate structure in the first variable. Even though the degrees are much higher, compared to $f_A$, we can compute easier with these polynomials, because of the simple structure of the gradient ideal. However, due to the multiple roots introduced by $p_1(t)^3$, the gradient ideal remains non-radical for all $n$, and the remainder and quotients still exhibit significant growth in the bitsize.

**Overall asessement.** Overall, the experiments confirm that bitsize growth is the key limiting factor in computing SOS representations symbolically. The difference between radical and non-radical gradient ideals is reflected both in algebraic structure and computational cost: non-radical ideals yield smaller intermediate bitsizes while radical ones lead to larger elimination polynomials and heavier computations. These observations suggest that controlling bitsize growth—possibly through modular or numeric-symbolic hybrid techniques—remains a major challenge for extending SOS-RUR to higher-dimensional instances.

# 6 Conclusions and perspectives

We introduce a certificate for polynomial nonnegativity based on Rational Univariate Representation, valid without assuming radicality of the gradient ideal. The corresponding algorithm, SOS-RUR, either
constructs such a certificate or provides a rational witness of negativity, with explicit bounds on com-
plexity and coefficient size. In the radical case, the method specializes to a more efficient representation
with improved degree bounds. We further extended the approach to sparse polynomials, deriving input-
sensitive complexity estimates in terms of the Newton polytope. These results provide a unified and
computationally explicit framework for certifying nonnegativity in both dense and sparse polynomial
settings.

Regarding the next steps, the RUR representation of the roots of a zero-dimensional ideal is also useful
to compute certificates for semi-algebraic problems; we refer the reader to [BKM24] for the most recent
advancements in this directions. In particular, (the proof of) Thm. 3.2 apply, mutatis mutandis, when
we want to certify that $f \in \mathbb{Z}[\mathbf{X}]$ is positive over the real algebraic set $\{\mathbf{x} \in \mathbb{R}^n | g_1(\mathbf{x}) = \cdots = g_n(\mathbf{x}) = 0\}$,
when the ideal $\langle g_1, \ldots, g_n \rangle$ is 0-dimensional. The bounds on the degrees and bitsize of the various poly-
nomials involved in the decomposition are similar to the unconstrained case, at least for the multivariate
polynomials. The main difference is that, at the end, we need to certify that a univariate, $r(T)$, is positive,
not over the whole $\mathbb{R}$, but over a finite semi-algebraic set of the form $\{t \in \mathbb{R} | a(T) = 0, \text{where } a \in \mathbb{Z}[T]\}$.
Now, the SOS decomposition of uSOS supported by Prop. 2.20 does not apply. Instead, we should em-
ploy (a variant of) the algorithm from Krick, Mourrain, and Szanto [KMS22]. If we combine, Thm. 3.2,
Thm. 3.9 and the results from [BKM24] and [KMS22] we can obtain explicity bit complexity bounds.
We postpone this technical analysis for a future communication.

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 [BKM24]. The authors thank Fabrice Rouillier for various discussions and suggestions about RUR and clarifications regarding [DRR24] 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). CZ is also supported by the Chinese Scholarship Council.

References

[Alo+96] M.-E. Alonso, E. Becker, M.-F. Roy, and T. Wörmann. “Zeros, multiplicities, and idempotents for zero-dimensional systems”. In: *Algorithms in algebraic geometry and applications*. Springer. 1996, pp. 1–15.

[AM01] F. Amoroso and M. Mignotte. “Upper bounds for the coefficients of irreducible integer polynomials in several variables”. In: *Acta Arithmetica* 99.1 (2001), pp. 1–12.

[Art27] E. Artin. “Über die Zerlegung definiter Funktionen in Quadrate”. In: *Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg* 5.1 (Dec. 1927), pp. 100–115. URL: http://link.springer.com/10.1007/BF02952513.

[BM88] L. Babai and S. 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.

[BKM24] L. Baldi, T. Krick, and B. Mourrain. “An Effective Positivstellensatz over the Rational Numbers for Finite Semialgebraic Sets”. In: *arXiv preprint arXiv:2410.04845* (2024).

[BPR06] S. Basu, R. Pollack, and M.-F. Roy. *Algorithms in real algebraic geometry*. Springer, 2006.

[BR15] M. Beck and S. Robins. *Computing the Continuous Discretely*. Undergraduate Texts in Mathematics. New York, NY: Springer New York, 2015. URL: http://link.springer.com/10.1007/978-1-4939-2969-6.

[BDT25] M. Bender, P. di Dio, and E. Tsigaridas. “Positive Univariate Polynomials: SOS certifi-cates, algorithms, bit complexity, and T-systems”. Sept. 2025. URL: https://inria.hal.science/hal-05269445.
[Ber75] D. Bernstein. "The Number of Roots of a System of Equations". In: *Funct. Anal. and Appl.* 9.2 (1975), pp. 183-185.

[Bli14] H. F. Blichfeldt. "A new principle in the geometry of numbers, with some applications". In: *Transactions of the American Mathematical Society* 15.3 (1914), pp. 227-235.

[BS16] C. Brand and M. Sagraloff. "On the complexity of solving zero-dimensional polynomial systems via projection". In: *Proc ACM on International Symposium on Symbolic and Algebraic Computation (ISSAC)*. 2016, pp. 151-158.

[Can88] J. Canny. "Some algebraic and geometric computations in PSPACE". In: *Proc. 20th annual ACM Symposium on Theory of Computing (STOC)*. 1988, pp. 460-467.

[Can90] J. Canny. "Generalised characteristic polynomials". In: *Journal of Symbolic Computation* 9.3 (Mar. 1990), 241-250. URL: http://dx.doi.org/10.1016/S0747-7171(08)80012-0.

[CE00] J. F. Canny and I. Z. Emiris. "A subdivision-based algorithm for the sparse resultant". In: *Journal of the ACM (JACM)* 47.3 (2000), pp. 417-451.

[Che+11] S. Chevillard, J. Harrison, M. Joldeş, and C. Lauter. "Efficient and accurate computation of upper bounds of approximation errors". In: *Theoretical Computer Science* 412.16 (2011). Publisher: Elsevier, pp. 1523-1543. URL: https://www.sciencedirect.com/science/article/pii/S0304397510006900.

[DE01] C. D'Andrea and I. Z. Emiris. "Computing sparse projection operators". In: *Contemporary Mathematics* 286 (2001), pp. 121-140.

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

[DRR24] A. Demin, F. Rouillier, and J. Ruiz. "Reading Rational Univariate Representations on lexicographic Groebner bases". In: *arXiv preprint arXiv:2402.07141* (2024).

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

[DJS23] C. D'Andrea, G. Jeronimo, and M. Sombra. "The Canny-Emiris conjecture for the sparse resultant". In: *Foundations of Computational Mathematics* 23.3 (2023), pp. 741-801.

[EMT20] I. Emiris, B. Mourrain, and E. Tsigaridas. "Separation bounds for polynomial systems". In: *Journal of Symbolic Computation* 101 (2020), pp. 128-151.

[GG03] J. von zur Gathen and J. Gerhard. *Modern computer algebra*. Cambridge university press, 2003.

[GKZ94] I. Gelfand, M. Kapranov, and A. Zelevinsky. *Discriminants, Resultants and Multidimensional Determinants*. Boston, Birkhäuser, 1994.

[GMR19] S. Goldwasser, S. Micali, and C. 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.

[HJS19] M. I. Herrero, G. Jeronimo, and J. Sabia. "On degree bounds for the sparse Nullstellensatz". In: *Journal of Algebra* 534 (2019), pp. 531-544.

[HL15] J. van der Hoeven and G. Lecerf. "Sparse polynomial interpolation in practice". In: *ACM Commun. Comput. Algebra* 48.3/4 (2015), pp. 187-191.

[HL21] J. van der Hoeven and G. Lecerf. "On the complexity exponent of polynomial system solving". In: *Foundations of Comp. Math.* 21 (2021), pp. 1-57.

[HL23] J. van der Hoeven and G. Lecerf. "Amortized multi-point evaluation of multivariate polynomials". In: *J. of Complexity* 74 (2023).

[Hoe17] J. van der Hoeven. "On the complexity of multivariate polynomial division". In: *Applications of Computer Algebra: Kalamata, Greece, July 20-23 2015*. Springer. 2017, pp. 447-458.
[HQ25]
Z. Hua and Z. Qu. "Exactness and Effective Degree Bound of Lasserre's Relaxation for Polynomial Optimization over Finite Variety". In: *Mathematics of Operations Research* (2025).

[Jer+09]
G. Jeronimo, G. Matera, P. Solerno, and A. Waissbein. "Deformation techniques for sparse systems". In: *Foundations of Computational Mathematics* 9.1 (2009), pp. 1-50.

[Kal+12]
E. L. Kaltofen, B. Li, Z. Yang, and L. Zhi. "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.

[Koi96]
P. Koiran. "Hilbert's Nullstellensatz is in the polynomial hierarchy". In: *Journal of complexity* 12.4 (1996), pp. 273-286.

[KMV23]
P. Koprowski, V. Magron, and T. Vaccon. "Pourchet's theorem in action: decomposing univariate nonnegative polynomials as sums of five squares". In: *Proc 2023 International Symposium on Symbolic and Algebraic Computation (ISSAC)*. 2023, pp. 425-433.

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

[KPS01]
T. Krick, L. M. Pardo, and M. Sombra. "Sharp estimates for the arithmetic Nullstellensatz". In: *Duke Mathematical Journal* 109.3 (2001), pp. 521-598. URL: https://doi.org/10.1215/S0012-7094-01-10934-4.

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

[Lan06]
E. Landau. "Über die Darstellung definitier Funktionen durch Quadrate". In: *Mathematische Annalen* 62.2 (June 1906), pp. 272-285. URL: http://link.springer.com/10.1007/BF01449981.

[Las02]
J. Lasserre. "Polynomials nonnegative on a grid and discrete optimization". In: *Transactions of the American Mathematical Society* 354.2 (2002), pp. 631-649.

[LW96]
T.-Y. Li and X. Wang. "The BKK root count in $\mathbb{C}^n$". In: *Mathematics of computation* 65.216 (1996), pp. 1477-1484.

[LPR20]
H. Lombardi, D. Perrucci, and M.-F. Roy. *An elementary recursive bound for effective Positivstellensatz and Hilbert's 17th problem*. Vol. 263. 1277. American mathematical society, 2020.

[MSEDS19]
V. Magron, M. Safey El Din, and M. Schweighofer. "Algorithms for weighted sum of squares decomposition of non-negative univariate polynomials". In: *Journal of Symbolic Computation* 93 (2019). Publisher: Elsevier, pp. 200-220.

[MSEDV23]
V. Magron, M. Safey El Din, and T.-H. Vu. "Sum of Squares Decompositions of Polynomials over their Gradient Ideals with Rational Coefficients". In: *SIAM Journal on Optimization* 33.1 (Mar. 31, 2023), pp. 63-88. URL: https://epubs.siam.org/doi/10.1137/21M1436245.

[MW23]
V. Magron and J. Wang. *Sparse polynomial optimization: theory and practice*. World Scientific, 2023.

[Mah62]
K. Mahler. "On some inequalities for polynomials in several variables". In: *J. London Math. Soc* 37.341-344 (1962), p. 29.

[MST17]
A. Mantzaflaris, É. Schost, and E. Tsigaridas. "Sparse rational univariate representation". In: *Proc. ACM on International Symposium on Symbolic and Algebraic Computation (IS-SAC)*. 2017, pp. 301-308.

[MSW15]
K. Mehlhorn, M. Sagraloff, and P. Wang. "From approximate factorization to root isolation with application to cylindrical algebraic decomposition". In: *Journal of Symbolic Computation* 66 (2015), pp. 34-69.
[NDS06] J. Nie, J. Demmel, and B. Sturmfels. "Minimizing Polynomials via Sum of Squares over the Gradient Ideal". In: *Mathematical Programming* 106.3 (May 2006), pp. 587–606. URL: http://link.springer.com/10.1007/s10107-005-0672-6.

[PT17] V. Pan and E. Tsigaridas. "Nearly optimal computations with structured matrices". In: *Theoretical Computer Science* 681 (2017), pp. 117–137.

[Pan02] V. Y. Pan. "Univariate Polynomials: Nearly Optimal Algorithms for Numerical Factorization and Root-finding". In: *Journal of Symbolic Computation* 33.5 (May 2002), 701–733. URL: http://dx.doi.org/10.1006/jsco.2002.0531.

[Par02] P. A. Parrilo. "An explicit construction of distinguished representations of polynomials nonnegative over finite sets". In: *Preprint, ETH, Zürich* (2002).

[Pou71] Y. Pourchet. "Sur la représentation en somme de carrés des polynômes à une indéterminée sur un corps de nombres algébriques". In: *Acta Arithmetica* 19.1 (1971), pp. 89–104. URL: https://eudml.org/doc/205020.

[Pow21] V. Powers. *Certificates of Positivity for Real Polynomials*. Springer, 2021.

[Rez78] B. Reznick. "Extremal PSD forms with few terms". In: *Duke Mathematical Journal* 45.2 (1978), pp. 363–374. URL: https://doi.org/10.1215/S0012-7094-78-04519-2.

[Roj99a] J. M. Rojas. "Solving degenerate sparse polynomial systems faster". In: *Journal of Symbolic Computation* 28.1-2 (1999), pp. 155–186.

[Roj99b] J. M. Rojas. "Toric intersection theory for affine root counting". In: *Journal of Pure and Applied algebra* 136.1 (1999), pp. 67–100.

[Rou98] F. Rouillier. "Solving zero-dimensional polynomial systems through the Rational Univariate Representation". PhD thesis. INRIA, 1998. URL: https://inria.hal.science/inria-00073264/.

[SEDS18] M. Safey El Din and É. Schost. "Bit complexity for multi-homogeneous polynomial system solving—application to polynomial minimization". In: *Journal of Symbolic Computation* 87 (2018), pp. 176–206.

[Sch99] M. Schweighofer. "Algorithmische beweise für nichtnegativ-und positivstellensätze". In: *Master's thesis, Universität Passau* 136 (1999). URL: https://www.math.uni-konstanz.de/~schweigh/publications/diploma.thesis.pdf.

[Som99] M. Sombra. "A sparse effective Nullstellensatz". In: *Advances in Applied Mathematics* 22.2 (1999), pp. 271–295.