# Certificates for nonnegativity of multivariate integer polynomials under perturbations

Matías R Bender, Khazhgali Kozhasov, Elias Tsigaridas, Chaoping Zhu

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

## To cite this version:

Matías R Bender, Khazhgali Kozhasov, Elias Tsigaridas, Chaoping Zhu. Certificates for nonnegativity of multivariate integer polynomials under perturbations. 2025. hal-05407890

HAL Id: hal-05407890

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

Preprint submitted on 11 Dec 2025

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

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

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

Distributed under a Creative Commons Attribution 4.0 International License
# Certificates for nonnegativity of multivariate integer polynomials under perturbations

Matías Bender * Khazhgali Kozhasov † Elias Tsigaridas ‡ Chaoping Zhu §

December 9, 2025

## Abstract

We develop a general and unconditional framework for certifying the global nonnegativity of multivariate integer polynomials; based on rewriting them as sum of squares modulo their gradient ideals. We remove the two structural assumptions typically required by other approaches, namely that the polynomial attains its infimum and zero-dimensionality of the gradient ideal. Our approach combines a denominator-free stereographic transformation with a refined variant of the Hanzon-Jibetean perturbation scheme. The stereographic transformation preserves nonnegativity while making the polynomial coercive, with explicit bounds on the radius of positivity and on the nonzero critical values. Subsequently, we apply carefully constructed explicit perturbations that enforce zero-dimensionality of the gradient ideal without altering nonnegativity, allowing us to invoke recent algorithms to derive algebraic certificates or rational witness points. We present three algorithms implementing our framework and analyze their bit complexity in detail, which is single exponential with respect to the number of variables.

A second contribution is a new explicit SOS perturbation scheme, which allows us to perturb any nonnegative polynomial in such a way that it can be written as a sum of squares (SOS). In contrast to Lasserre's classical SOS approximation, which guarantees density but currently does not provide an effective control over the perturbation size, we only derive concrete perturbation bounds ensuring that a nonnegative polynomial enters the SOS cone.

**Keywords:** Nonnegative polynomials, certificates of positivity, stereographic projection, sum of squares decomposition, sum of squares approximations, gradient ideal, bit complexity

**AMS subject classifications:** 14Q30, 14N05, 11E25, 13P15 90C23

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

<footnote>†Université Côte d'Azur, 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 Introduction</td><td>3</td></tr><tr><td>2 Preliminaries</td><td>7</td></tr><tr><td>2.1 Ideals and varieties</td><td>7</td></tr><tr><td>2.2 SOS modulo zero-dimensional gradient ideals</td><td>7</td></tr><tr><td>2.3 Lower bounds for critical values</td><td>10</td></tr><tr><td>2.4 Coercive polynomials and radius of positivity</td><td>10</td></tr><tr><td>3 Stereographic transformation and positivity</td><td>11</td></tr><tr><td>3.1 Stereographic transformation preserves nonnegativity</td><td>11</td></tr><tr><td>3.2 Stereographic transformation and coercive polynomials</td><td>12</td></tr><tr><td>3.3 Tracing witness points from S(f) to f</td><td>13</td></tr><tr><td>3.4 Bounds on critical values</td><td>14</td></tr><tr><td>4 Perturbations preserving nonnegativity</td><td>14</td></tr><tr><td>4.1 Hanzon-Jibetean perturbations</td><td>14</td></tr><tr><td>4.2 Positive perturbations preserving nonnegativity</td><td>16</td></tr><tr><td>4.3 Negative perturbations preserving nonnegativity</td><td>17</td></tr><tr><td>5 Algorithms</td><td>18</td></tr><tr><td>6 Complexity analysis</td><td>22</td></tr><tr><td>7 SOS perturbations</td><td>24</td></tr><tr><td>7.1 Comparison with Lasserre's perturbations</td><td>27</td></tr></table>
# 1 Introduction

A central topic at the intersection of real algebraic geometry and polynomial optimization is to decide whether a multivariate polynomial of even degree is nonnegative over $\mathbb{R}^n$. Deciding nonnegativity also allows us to verify whether a given value is a global lower bound for a multivariate polynomial; this simple observation has culminated in the development of a vibrant area of optimization. As this decision problem is NP-hard already for polynomials of degree 4 [MK87], current algorithms are computationally demanding. Hence, it naturally arises the question of verifying their output, namely, nonnegativity, without having to solve the optimization problem itself; this is what we call a *certificate of nonnegativity*.

For a polynomial nonnegative on $\mathbb{R}^n$, the ultimate certificate is Artin's solution [Art27] to Hilbert's 17th problem, which ensures the existence of a representation of any nonnegative polynomial as a sum of squares of rational functions. Unfortunately, the state-of-the-art degree bounds for the numerators and denominators in such representations are prohibitive [LPR20]. This motivates the search for certificates of nonnegativity that are easier and less expensive to compute in important special cases.

Following Powers [Pow21], a certificate consists of one or more "simple" algebraic identities which, if satisfied, imply the nonnegativity of the polynomial under consideration. Such a certificate must be *perfectly complete*, it should always certify a nonnegative polynomial, and *perfectly sound*, it should correctly reject any polynomial that is not nonnegative; see [BTZ25] for further details.

We consider global certificates of nonnegativity for a polynomial $f \in \mathbb{Z}[\mathbf{X}] := \mathbb{Z}[X_1, \dots, X_n]$. Given $f$, our aim is to provide algebraic identities that verify that $f(\mathbf{x}) \ge 0$ for all $\mathbf{x} \in \mathbb{R}^n$, or, if this is not the case, a point $\mathbf{p} \in \mathbb{Q}^n$ such that $f(\mathbf{p}) < 0$, which we call a *witness* point. Existing approaches, discussed in more detail in the sequel, are powerful but typically require structural assumptions on $f$ (e.g., that the gradient ideal of $f$ is zero-dimensional and/or radical, or that the infimum of $f$ over $\mathbb{R}^n$ is attained). However, many classical examples violate these assumptions, and it is of clear interest to develop alternative certificates of nonnegativity without imposing any conditions on the input polynomial.

We show that, by performing suitable invertible transformations, one can transform any nonnegative polynomial into another one whose gradient ideal is zero-dimensional and whose infimum is attained. In this way, we can leverage existing methods for zero-dimensional systems (see for example [BTZ25]), to provide global certificates of nonnegativity for an arbitrary input polynomial with integer coefficients.

**Prior works** The most commonly used certificate of nonnegativity is the SOS certificate, that is, decomposing $f$ as a sum of squares of polynomials or rational functions. In the univariate case, it is well known that any $f \in \mathbb{R}[X]$ that is nonnegative can be written as a sum of two squares in $\mathbb{R}[X]$ [Hil88]. Over the rational numbers, the strongest general result is that if $f \in \mathbb{Q}[X]$ is nonnegative, then it admits a weighted sum of squares representation with $t \le 5$ squares, $f(X) = \sum_{i=1}^t w_i s_i^2(X)$, where $s_i \in \mathbb{Q}[X]$, $w_i \in \mathbb{Q}_+$, and $t \le 5$ [Lan06; Pou71]. Unfortunately, no known algorithm achieves such a decomposition with $t \le 5$, although there has been recent significant progress [KMV23]; see also [Ben+25]. By allowing up to $t \le \deg f + 3$ summands, the algorithms of [Sch99; Che+11] provide constructive decompositions, with complexity analyzed in [MSEDS19]; see [BDDT25] for the most recent improvements.

For multivariate polynomials, certificates of nonnegativity are considerably more intricate. The first major mathematical breakthrough is Artin's solution to Hilbert's 17th problem [Art27], which establishes that every real nonnegative polynomial is a sum of squares of rational functions. Although Lombardi, Perrucci, and Roy [LPR20] give an algorithmic realization of Artin's theorem, its complexity is prohibitive, in particular, the degree bounds for the numerators and denominators form a tower of five exponentials, rendering the method impractical. Unlike the univariate case, not all multivariate nonnegative polynomials are sums of squares, with Motzkin's polynomial $M(\mathbf{X}) = X_1^4 X_2^2 + X_1^2 X_2^4 - 3 X_1^2 X_2^2 + 1$ providing the first explicit example. Scheiderer's striking result [Sch16] further shows that there exist nonnegative polynomials in $\mathbb{Q}[\mathbf{X}]$ that are SOS in $\mathbb{R}[\mathbf{X}]$ but not in $\mathbb{Q}[\mathbf{X}]$. Semidefinite programming hierarchies [Las01; Par00] introduced weighted SOS relaxations that approximate nonnegativity; these methods are particularly effective in optimization due to the availability of numerical solvers. Alternative certificates include SAGE/SONC polynomials [CS14; MSW19; WM20], though they suffer from analogous limitations, as general nonnegative polynomials need not admit SAGE/SONC representations.

Because of these limitations, SOS representations cannot serve as universal, computationally affordable certificates of nonnegativity. However, when the input polynomial satisfies certain structural
assumptions (such as radicality and/or zero-dimensionality of the gradient ideal, or attainment of the global minimum), one can express $f$ as a sum of squares modulo its gradient ideal. The *gradient ideal* of $f \in \mathbb{R}[\mathbf{X}]$ is defined as the ideal generated by its partial derivatives,

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

and the associated *gradient variety* $\mathbb{V}(I_{\nabla f}) \subseteq \mathbb{C}^n$ consists of all (complex) critical points of $f$. First, Lasserre [Las02] gave an SOS certificate for nonnegativity of polynomials over finite Cartesian grids in $\mathbb{R}^n$, and then, Parrilo [Par02] obtained a more general certificate over finite point sets defined by radical ideals. Nie, Demmel, and Sturmfels [NDS06] proved that $f$ is nonnegative on the real locus $\mathbb{V}(I_{\nabla f}) \cap \mathbb{R}^n$ of its gradient variety if and only if $f$ is a sum of squares modulo the radical of the gradient ideal $\sqrt{I_{\nabla f}}$. Assuming that $f$ attains its infimum, this yields the certificate

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

provided $I_{\nabla f}$ is radical.

Let $f \in \mathbb{Q}[\mathbf{X}]$ have degree $d$ and maximum coefficient bitsize $\tau$. Magron, Safey El Din, and Vu [MSEDV23] gave an algorithm that partially realizes the above certificate under the assumptions that the gradient ideal $I_{\nabla f}$ is zero-dimensional, radical and that the $X_1$-coordinates of the critical points are pairwise distinct. The algorithm first computes a representation

$$\mathbb{V}(I_{\nabla f}) = \{ \mathbf{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_1)}{w'(x_1)} \},$$

where $w, \kappa_2, \dots, \kappa_n \in \mathbb{Z}[X_1]$ are univariate polynomials and $w'$ is the derivative of $w$. Then $f$ is nonnegative if and only if it admits a decomposition

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

where $s \in \mathbb{Z}$, $q_j \in \mathbb{Z}[X_1]$, $\phi_i \in \mathbb{Z}[\mathbf{X}]$, and $c_j \in \mathbb{Q}_+$ for all $i \in [n]$ and $j \in [s]$. In particular, $\sum_{j=1}^s c_j q_j^2 \in \mathbb{Z}[X_1]$ is the remainder of $(w')^d f$ upon division by the divisors $\{w'X_2 - \kappa_2, \dots, w'X_n - \kappa_n\}$. When $f$ is nonnegative, this remainder is a nonnegative univariate polynomial and thus a weighted sum of squares in $\mathbb{Z}[X_1]$ [Che+11; MSEDS19].

More recently, Baldi, Krick, and Mourrain [BKM24] provided an SOS certificate of $f$ over a finite semi-algebraic set under specific assumptions on its defining polynomials. Furthermore, [BTZ25] obtained a similar certificate of nonnegativity based on the rational univariate representation of the roots, valid when the infimum of $f$ is attained and the gradient ideal is zero-dimensional; in particular, this removes the radicality assumption. This yields the SOS-RUR algorithm, which we also employ in our setting; see Sec. 2.2 for further details.

When the infimum of $f$ over $\mathbb{R}^n$ is not attained, instead of considering the gradient variety of $f$ and its values on it, one can look at *asymptotic critical values*. A complex number $c \in \mathbb{R}$ is called an asymptotic critical value of $f$, if there exists a sequence $(x_k)_{k \in \mathbb{N}} \subset \mathbb{C}^n$ tending to infinity, that is, $\|x_k\| \xrightarrow{k \to \infty} +\infty$, such that $f(x_k) \xrightarrow{k \to \infty} c$ and $\|x_k\| \cdot \|\nabla f(x_k)\| \xrightarrow{k \to \infty} 0$. There are algorithms to compute asymptotic critical values relying on Gröbner bases, e.g., [KOS00; JK03; SED07], or resultants [HT24]. However, though these algorithms allow us to compute these asymptotic values, it is not clear how to transform them into certificates of nonnegativity. An important work on this direction is due to Schweighofer [Sch06] who powered the classical SOS approach to global minimization of a polynomial with the idea to certify nonnegativity over so called gradient tentacles, which are sets stretching out to infinity and that contain asymptotic minimizing sequences.

In general, perturbation methods are used to transform a possibly degenerate problem (for example, one with solutions of high multiplicity, non-proper intersections, non-surjective projections, etc.) into one with generic properties. In the context of polynomial optimization, we may regard as degenerate those configurations in which the gradient ideal is not zero-dimensional or the polynomial does not attain its infimum, to mention a few important ones. Parrilo and Sturmfels [Pab03] considered this problem for polynomials having a finite number of critical points. They computed their minimum by determining all critical points (explicitly or implicitly) and then checking the sign of the finite set of
corresponding critical values. These critical points may be obtained by Gröbner bases, resultants, or homotopy continuation techniques. Hanzon and Jibetean [HJ03] provided a symbolic method for the global minimization of multivariate polynomials, without assuming convexity or coercivity. Given a polynomial $f$, they introduced the parametrized family of perturbations

$$f_{\lambda} := f + \lambda(X_{1}^{2m} + \dots + X_{n}^{2m}),$$

where $2m > \deg f$. For any fixed positive $\lambda$, these perturbed polynomials have finitely many critical points and their minimum is always attained. As the perturbation parameter tends to zero, the method recovers the infimum of the original polynomial. Thus, this approach provides a unified treatment of the cases where a minimum exists, where only a finite infimum exists, and where the infimum is attained “at infinity”. The main drawback is that one is forced to work with polynomials whose coefficients are themselves polynomials in $\lambda$. Later, Jibetean and Laurent [JL05] combined this perturbation scheme with Lasserre’s SOS hierarchy to provide certificates for the infimum using sums of squares. Our approach builds on Hanzon and Jibetean’s perturbation framework, but we specialize $\lambda$ to avoid working with polynomials having other polynomials as coefficients.

The geometric viewpoint of polynomial optimization also provides a wealth of information. The cones of nonnegative and SOS polynomials are fundamental in this setting. However, on the one hand, deciding the positivity of a polynomial is a difficult problem, and the boundary structure of the nonnegativity cone is highly intricate. On the other hand, verifying whether a polynomial admits an SOS representation reduces to checking the positive semidefiniteness of an associated Gram matrix [Pow21; CLR95], and therefore to solving a semidefinite feasibility problem. Hence, the SOS cone is a (rather) tractable inner approximation of the nonnegativity cone, and a substantial body of work studies how well SOS polynomials approximate globally nonnegative ones.

One can quantify the discrepancy between the two cones in several ways. For fixed degree, Blekherman [Ble06] showed that the volume of the nonnegativity cone is overwhelmingly larger than that of the SOS cone, and that the ratio grows superpolynomially with the number of variables; see also [Erg18] for a similar result for multihomogeneous polynomials. At the opposite end of the spectrum, when the degree is allowed to increase, a classical result of Berg [Ber87] shows that sums of squares are dense in the cone of polynomials nonnegative on the hypercube $[-1, 1]^n$ with respect to the $\ell_1$-norm of the coefficient vector. Later, Lasserre and Netzer [Las06; LN07] introduced explicit perturbation schemes that yielded fully explicit sequences of SOS polynomials converging to any given nonnegative polynomial in the $\ell_1$-topology; thus they quantified, in a sense, the density of SOS polynomials in the cone of nonnegative ones. However, even though Lasserre’s SOS approximation [Las06] leads to certificates of nonnegativity for the perturbed polynomial, it does not imply nonnegativity of the original polynomial. The difficulty lies in the rate of convergence of the corresponding sequence: even when a perturbed polynomial is nonnegative, it is not known how small the perturbation must be in order to conclude that the original polynomial is nonnegative. We introduce a new perturbation scheme, with explicit bounds on the perturbation, that places a nonnegative polynomial inside the SOS cone; unfortunately, this does not yet come with a convergence guarantee.

**Our contributions** We introduce a general and unconditional framework to certify the global non-negativity of a multivariate integer polynomial $f \in \mathbb{Z}[X]$, based on certificates of positivity modulo their gradient ideal. We remove the two strong assumptions usually imposed by other approaches; namely: (i) that the polynomial attains its infimum, and (ii) that its gradient ideal is zero-dimensional. We no longer impose either assumption by relying on perturbations to decide nonnegativity for any polynomial $f \in \mathbb{Z}[X]$, with $f(0) > 0$, without appealing to asymptotic critical values or semidefinite approximations. For this, we employ a series of transformations that preserve nonnegativity and enforce both conditions (i) and (ii); this allows to use SOS-RUR algorithm [BTZ25] to certify our input polynomial, see Def. 2.5 and Thm. 2.4.

First, we employ a denominator-free variant of stereographic transformation (Def. 3.2). The transformed polynomial, $S(f)$, preserves the nonnegativity of $f$ (Thm.3.3) and is coersive (Def. 2.14). Even more, it holds (Thm. 3.4), for any $x \in \mathbb{R}^n$, with $\|x\|_2^2 \ge 1$, that

$$S(f)(x) \ge \|x\|_2^{2d} - C \|x\|_2^{2d-1}, \quad (1)$$

for a constant $C$ depending only on $(n, d, \hbar(f))$; hence, we derive an explicit radius outside which $S(f)$ is strictly positive (Cor. 3.5). Using a quantitative lower bound on the nonzero critical values, by
Brownawell and Yap [BY09] (Cor. 3.9), we form the backbone of our geometric reduction, as the behavior of $f$ at infinity can be normalized into a coercive regime through a transformation (with fully explicit complexity and bitsize estimates). A second key property of $S(f)$ is that negative evaluations of $S(f)$ can be transported back to negative evaluations of $f$ (Lem. 3.7). If $S(f)(\boldsymbol{x}_0) < 0$ for some rational point $\boldsymbol{x}_0$, then we can explicitly construct a rational point $\mathcal{Q}(\boldsymbol{x}_0)$ such that $f(\mathcal{Q}(\boldsymbol{x}_0)) < 0$. Therefore, deciding the nonnegativity of $f$ is algorithmically equivalent to deciding the nonnegativity of $S(f)$.

**Hanzon–Jibetean-like perturbations and zero-dimensionality.** Even though $S(f)$ is coercive and attains its infimum, its gradient ideal may still be positive-dimensional. We enforce zero-dimensionality through a refined Hanzon–Jibetean perturbation [HJ03]. We introduce positive and negative perturbations, $\mathcal{P}_\lambda(f)$ and $\mathcal{N}_\lambda(f)$ (Def. 4.1) for a polynomial $f$ of degree $d$, that is,

$$ \mathcal{P}_{\lambda}(f)(\mathbf{X}) := f(\mathbf{X}) + \lambda \sum_{i=1}^{n} (1 + X_i^2 + X_i^{d+2}) \quad \text{and} \quad \mathcal{N}_{\lambda}(f)(\mathbf{X}) := f(\mathbf{X}) - \lambda \sum_{i=1}^{n} (1 + X_i^2 + X_i^d). $$

For small enough $\lambda$, both perturbations preserve nonnegativity. Even more, for any fixed $\lambda > 0$ the gradient ideal of $\mathcal{P}_\lambda(S(f))$ is zero-dimensional and has no solutions “at infinity” (Thm. 4.2). We then combine the coercivity and critical value bounds for $S(f)$ to obtain explicit inequalities on $\lambda$ (Thm. 4.6) that ensure the preservation of nonnegativity. In particular, it holds

$$ f \ge 0 \iff \mathcal{P}_{\lambda}(S(f)) \ge 0. $$

By combining these results with SOS-RUR (Thm. 2.4), we introduce the algorithm HJ-SOS-POS (Alg. 2) that certifies the nonnegativity of any input polynomial $f$ or computes a point at which it is negative.

The main disadvantage of HJ-SOS-POS is that it requires us to perform a very small perturbations and it forces us, when the input consists of an integer polynomial, to work with rationals having the worst case bitsize, right from the beginning. Even though this is not an obstacle from the theoretical perspective, it limits the practicality of the algorithm. To overcome this obstacle, we exploit the negative perturbation, $\mathcal{N}_\lambda(S(f))$, that allows us to gradually decrease the perturbations (Alg. 3). Unfortunately, this perturbation preserves nonnegativity only when both $f$ and its highest degree homogeneous part are positive (Thm. 4.10); also, it does not provide a witness point, if $f$ is not nonnegative. Nevertheless, it leads to the algorithm HJ-SOS-NEG (Alg. 3) that certifies nonnegativity, under the conditions that we mentioned previously, and fails otherwise.

However, the combination of both perturbation schemes, and hence the combination of the corresponding algorithms, leads to the algorithm HJ-SOS-RUR (Alg. 4) that incorporates the advantages of both approaches and certifies the nonnegativity of any polynomial $f$, without requiring us to work with small perturbations right from the beginning, or demanding the nonnegativity of the highest degree homogeneous part.

We study in detail the bit complexity of both HJ-SOS-POS (Thm. 6.2) and HJ-SOS-NEG (Thm. 6.3), as well as the bit complexity of HJ-SOS-RUR (Thm. 6.4). We obtain single exponential, with respect to the number of variables, bit complexity bounds. In particular, if the input is a polynomial with $n$ variables, of degree $d$, and maximum coefficient bitsize $\tau$, then HJ-SOS-RUR in

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

bit operations, where $\omega$ is the exponent of matrix multiplication, provides a certificate for $f$, involving rationals of bitsize at most $\tilde{\mathcal{O}}(2^{4n}(d+1)^{4n+2}(d+\tau)))$.

**SOS under perturbation.** Finally, we consider the problem of expressing a positive polynomial as a sum of squares. As this is not possible in general, we consider a suitable perturbation to place it in the cone of SOS polynomials. In particular, if $f$ is a positive polynomial in $n$ variables, of degree $2d$, then we show (Thm. 7.1) that for any $t \in \mathbb{N}$, such that

$$ t \ge \max \left\{ d, \left[ \frac{1}{\varepsilon} \left( \|f\|_1 + \frac{\|\nabla f(\mathbf{0})\|_2^2}{f_0 + \varepsilon} \right) \right] \right\}, $$

the degree $2t$ polynomial $f_{t,\varepsilon}(\mathbf{X}) = f(\mathbf{X}) + \varepsilon(1 + \|\mathbf{X}\|_2^2)^t$ is a sum of squares. This leads to the claim that, if $f$ is any positive polynomial in $n$ variables, of degree $2d$, then the polynomial $f(\mathbf{X}) + \varepsilon(1 + \|\mathbf{X}\|_2^2)^t$ is a sum of squares, if

$$ t \ge \binom{n+2d}{n} \frac{2^{\tau+1}}{\varepsilon}. $$
This builds on the results of Lasserre [Las06] and Lasserre and Netzer [LN07], but in our case we have explicit bounds on the power of the perturbation. Alas, our perturbation scheme does not have the property that $f_{t,ε} \to f$, when $ε \to 0$, cf. [Las10; Las06].

**Organization** The next section (Sec. 2) presents the preliminaries from computational (real) algebraic geometry. Next, in Sec. 3 we present the stereographic transformation and in Sec. 4 we present the Hanzon-Jibetean perturbations we exploit. We present the algorithm(s) for computing the certificates of nonnegativity in Sec. 5 and their bit complexity analysis in Sec. 6. Finally, in Sec. 7 we present our results on approximating a positive polynomial with a sum of squares.

**Notations** Let $\mathbb{N}$, $\mathbb{Z}$, $\mathbb{Q}$, $\mathbb{R}$ and $\mathbb{C}$ be the set of natural numbers (including zero), integers, rational numbers, real numbers and complex numbers. We denote by $\mathbb{K}[\mathbf{X}]$ the polynomial ring in the variables $X_1, X_2, \dots, X_n$ with coefficients in some ring or field $\mathbb{K}$, where $\mathbb{K}$ can be $\mathbb{Z}$, $\mathbb{Q}$, $\mathbb{R}$, $\mathbb{C}$, etc. We denote by $\mathbf{X}^{\alpha}$ the monomial $X_1^{\alpha_1} \dots X_n^{\alpha_n}$, where $\alpha = (\alpha_1, \dots, \alpha_n) \in \mathbb{N}^n$ is a multi-index. When $\alpha \in \mathbb{N}^n$ denotes the exponent of a monomial, we define $|\alpha| := \sum_i \alpha_i$. 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. For a given polynomial $f \in \mathbb{K}[\mathbf{X}]$, we denote by $f^h$ the homogenization of $f$, i.e. $f^h := \sum_{|\alpha| \le d} a_{\alpha} \mathbf{X}^{\alpha} X_0^{d-|\alpha|} \in \mathbb{K}[\mathbf{X}, X_0]$, if $f = \sum_{|\alpha| \le d} a_{\alpha} \mathbf{X}^{\alpha} \in \mathbb{K}[\mathbf{X}]$. We also denote by $f^{(d)}$ the degree $d$ homogeneous part of $f$, it is the highest degree homogeneous part of $f$ especially when $\deg f = d$.

We use bold lowercase letters to represent a point to distinguish it from the variables, e.g. $\mathbf{x} = (x_1, \dots, x_n) \in \mathbb{R}^n$. We use $\|\mathbf{x}\|_2$ to denote the Euclidean norm of $\mathbf{x}$, i.e. $\|\mathbf{x}\|_2 := (\sum_{i=1}^n x_i^2)^{\frac{1}{2}}$. We denote by $\mathbb{S}^n := \{\mathbf{x} \in \mathbb{R}^{n+1} : \|\mathbf{x}\|_2 = 1\}$, the unit sphere in $\mathbb{R}^{n+1}$.

We denote by $\mathcal{O}$ and $\mathcal{O}_B$ the arithmetic and, respectively, bit complexity; we also use $\tilde{\mathcal{O}}$ and $\tilde{\mathcal{O}}_B$, to ignore (poly-)logarithmic factors. For an integer $n$, we denote by $[n]$ the set $\{1, 2, \dots, n\}$. For $r \in \mathbb{Q}$, we denote by $H(r)$ the height of $r$, which is the maximum absolute value of its numerator and denominator in the representation of $r$ as an irreducible fraction. For $f \in \mathbb{Q}[\mathbf{X}]$, we denote by $H(f)$ the maximum height of all the coefficients of $f$ and by $\mathcal{H}(f)$ the bitsize of $H(f)$, i.e. $\mathcal{H}(f) = \lceil \lg H(f) \rceil + 1$, where $\lg = \log_2$ and $\lceil \cdot \rceil$ is the floor function that outputs the greatest integer less than or equal to the input. We say that $f \in \mathbb{Q}[\mathbf{X}]$ has size $(d, \tau)$ if it has degree $d$ and bitsize at most $\tau$.

For a polynomial $f \in \mathbb{R}[\mathbf{X}]$, we denote its nonnegativity over the reals by the abbreviation $f \ge 0$, or $f \ge 0$ on $\mathbb{R}^n$, instead of writing $f(\mathbf{x}) \ge 0$, for all $\mathbf{x} \in \mathbb{R}^n$.

# 2 Preliminaries

In this section, we introduce some notations, tools, and results from computational algebraic geometry that we will later use; namely, rational univariate representation, certificates of nonnegativity, lower bounds for critical values of multivariate functions, and coercive polynomials.

## 2.1 Ideals and varieties

Let $\mathbb{K}$ be a field and let $\mathbb{K}[\mathbf{X}]$ be the corresponding polynomial ring, where $\mathbf{X} = (X_1, \dots, X_n)$. Given an ideal $I \subseteq \mathbb{K}[\mathbf{X}]$, we denote by $\sqrt{I} := \{f \in \mathbb{K}[\mathbf{X}] : f^n \in I, \text{ for some } n \in \mathbb{N}\}$ the radical ideal of $I$. For an ideal $I$, if $I = \sqrt{I}$, we say that $I$ is radical. Given an ideal $I$ in $\mathbb{K}[\mathbf{X}]$, we define its variety to be the set $\mathbb{V}_{\mathbb{K}}(I) := \{\mathbf{x} \in \mathbb{K}^n : f(\mathbf{x}) = 0, \forall f \in \mathbb{K}[\mathbf{X}]\}$. If we omit the subscript we refer to the complex variety, i.e., $\mathbb{V}(I) = \mathbb{V}_{\mathbb{C}}(I)$. Given equations $(f_1, \dots, f_r)$, the solutions “at infinity” of the system correspond to the non-zero points in the variety $\mathbb{V}_{\mathbb{C}}(f_1^h(0, X_1, \dots, X_n), \dots, f_r^h(0, X_1, \dots, X_n))$, where $f_i^h(0, X_1, \dots, X_n)$ corresponds to the restriction of the homogenization of $f_i$ to the hyperplane $X_0 = 0$. In particular, we say that the system has no solutions “at infinity”, when this projective variety is empty. For further details on (computational) commutative algebra and algebraic geometry, we refer the reader to [CLO15; CLO05].

## 2.2 SOS modulo zero-dimensional gradient ideals

Consider a polynomial $f \in \mathbb{Q}[\mathbf{X}]$. If the infimum of $f$ is attained, then we can decide if $f$ is nonnegative by computing the signs of all its critical values. The latter are the evaluations of $f$ at its critical points,
that are in turn the (real) zeros of $I_{\nabla f}$, the gradient ideal of $f$.

**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 all 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 gradient variety $\mathcal{V}(I_{\nabla f})$ consists of all the complex critical points of $f$.

Under the assumption that the infimum of $f$ is attained, Nie, Demmel, and Sturmfels [NDS06] proved that we can write $f$ as a sum of squares modulo the radical of the gradient ideal of $f$, that is $\sqrt{I_{\nabla f}}$. However, their proof is non-constructive. The most recent result on the constructive version of this is the SOS-RUR algorithm by Bender et al. [BTZ25], that computes this SOS decomposition when the gradient ideal is zero-dimensional, based on a rational univariate representation (RUR) [Rou98] of the points of the gradient variety.

Given a zero-dimensional variety $V$, we say that a linear form $L \in \mathbb{Q}[\mathbf{X}]$ is separating if for every $\mathbf{p}, \mathbf{q} \in V$, it holds $L(\mathbf{p}) \pm L(\mathbf{q})$, when $\mathbf{p} \pm \mathbf{q}$.

**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 $\mathcal{V}(I)$. A RUR of $\mathcal{V}_C(I)$ 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

$$ \mathcal{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 and $R'_0$ is its derivative with respect to $T$. Also, it holds $t = L(\frac{R_1}{R'_0}(t), \dots, \frac{R_n}{R'_0}(t))$, for every root $t \in \mathbb{C}$ of $R_0(T)$. We denote this representation as

$$ \mathrm{RUR}(I) = (R_0(T), R_1(T), \dots, R_n(T), T - L(\mathbf{X})). $$

We also define an 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]. $$

Given $f \in \mathbb{Q}[\mathbf{X}]$ of even degree $d$ 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)$ for the gradient ideal of $f$, [BTZ25, Thm. 3.2] (see also [MSEDV23, Thm. 4.1]) proved that, when $f$ attains its infimum and the gradient ideal $I_{\nabla f}$ is zero-dimensional, $f(\mathbf{X})$ is nonnegative if and only if the univariate polynomial $(R'_0(t))^d f(\frac{R_1}{R'_0}(t), \dots, \frac{R_n}{R'_0}(t))$ is nonnegative. This last property can be verified/certified by writing the univariate polynomial as a weighted sum of squares of polynomials; see, e.g., [BDDT25].

**Definition 2.3** (The condition (Π)). Let $f \in \mathbb{Q}[\mathbf{X}]$ be a polynomial of even degree. We say that $f$ satisfies condition (Π), when

(1) $f$ attains its infimum, and (Π)

(2) the gradient ideal $I_{\nabla f}$ is zero-dimensional.

**Theorem 2.4** ([BTZ25, Thm. 3.2]; see also [MSEDV23, Thm. 4.1]). Let $f \in \mathbb{Q}[\mathbf{X}]$ be a polynomial of even degree satisfying (Π). 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)$ be a rational univariate representation of $\mathcal{V}_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 (2) $$

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]$.

Equation (2) leads to a valid certificate of nonnegativity: algebraic identities that, when verified, prove that the polynomial is nonnegative; see [BTZ25, Sec. 4].

**Definition 2.5.** A certificate of nonnegativity for $f \in \mathbb{Q}[\mathbf{x}]$ of even degree consists of tuples of polynomials and constants
• $(R_0(T), R_1(T), \dots, R_n(T)) \in \mathbb{Q}[T]^{n+1}.$

• $(q_1, \dots, q_n) \in \mathbb{Q}[T, \mathbf{X}]^n.$

• $s_1, \dots, s_\nu \in \mathbb{Q}[T]$ (for some $\nu \in \mathbb{N}$).

• $(\lambda_1, \dots, \lambda_n) \in \mathbb{Q}^n.$

• $r \in \mathbb{Q}[T].$

• $w_1, \dots, w_\nu \in \mathbb{Q}_+.$

We say that the certificate is valid if,

(1) $f$ satisfies (Π),

(2) $R_0(t)$ is non-zero and square-free, and $T = \sum_{i=1}^n \lambda_i \frac{R_i}{R_0}(T)$,

(3) We have the inclusion $\left\{ \left( \frac{R_1}{R_0}(t), \dots, \frac{R_n}{R_0}(t) \right) : t \in \mathbb{C}, R_0(t) = 0 \right\} \supseteq \mathbb{V}(I_{\nabla f})$, and

(4) The polynomials satisfy the equality in (2).

**Remark 2.6.** Observe that condition (1) and (3) are related: if condition (3) is satisfied, then the gradient ideal of $f$ must have a finite number of points, so it is zero-dimensional. Therefore, we can replace condition (1) by the condition “$f$ attains its minimum”.

**Corollary 2.7** ([BTZ25, Cor. 4.4]). For any $f \in \mathbb{Q}[\mathbf{X}]$ satisfying (Π), we have the equivalence: $f$ is nonnegative if and only if there exists a valid certificate of nonnegativity as in Def. 2.5.

If $f$ is not nonnegative, then we can certify this by computing a rational point where $f$ is negative. SOS-RUR algorithm computes either of these certificates.

<caption>**Algorithm 1 SOS-RUR** [BTZ25, Alg. 1]</caption>

**Input:** A multivariate polynomial $f \in \mathbb{Q}[\mathbf{X}]$ of even degree satisfying (Π).

**Output:** A certificate given by the pair [NonNeg, Cert].

**NonNeg** : a Boolean; **True** if $f$ is nonnegative, **False** otherwise.

**Cert** : a list containing one of the following (depending on the value of NonNeg):

- If $f$ is not nonnegative (NonNeg = **False**), then $Cert = [\mathbf{p}]$, where $\mathbf{p} \in \mathbb{Q}^n$ is such that $f(\mathbf{p}) < 0$.

- If $f$ is nonnegative (NonNeg = **True**), then $Cert$ is a valid certificate of nonnegativity for $f$; see Def. 2.5 and Eq. (2).

**Theorem 2.8** ([BTZ25, Thm. 3.9, Cor. 3.18, Rem. 2.14]). Consider $f \in \mathbb{Z}[\mathbf{X}]$ of size $(d, \tau)$ and even degree. Assume that $f$ satisfies (Π), that is, the gradient ideal of $f$ is zero-dimensional and $f$ attains its infimum. The SOS-RUR algorithm [BTZ25, Alg. 1] computes either

• If $f$ is nonnegative, the RUR of $I_{\nabla f}$ and the decomposition from Equation (2). The largest coefficient of the polynomials involved in this decomposition has bitsize $\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 $f$ is not nonnegative, a rational point $\mathbf{p} \in \mathbb{Q}^n$ such that $f(\mathbf{p}) < 0$. The bitsize of the witness point is $\tilde{\mathcal{O}}(nd^{2n+2}(d + n\tau))$.

SOS-RUR is a Monte Carlo algorithm and its bit complexity is $\tilde{\mathcal{O}}_B(e^{\omega n+\mathcal{O}(\lg n)} d^{(\omega+2)n}(n+\tau))$, where $\omega$ is the exponent of matrix multiplication. When $I_{\nabla f}$ has no solutions “at infinity”, the complexity reduces to $\tilde{\mathcal{O}}_B(e^{\omega n+\mathcal{O}(\lg n)} d^{(\omega+1)n-1}(d+\tau))$.

The probability of success of SOS-RUR is $1 - \frac{1}{k}$, for any constant $k$.

**Remark 2.9** (Checking zero-dimensionality). In this paper we will deal with coercive polynomials, which we will obtain through the stereographic transformation. These polynomials attain their minimum, but their gradient ideal might not be zero-dimensional. We can modify the procedures introduced in [BTZ25] in order to check this last condition within the same complexity of SOS-RUR. We can perform a deterministic
check to verify if a gradient ideal is zero-dimensional and it has no solutions “at infinity”. To do so, let $(\partial_1 f)^h \in \mathbb{Q}[X_0, \dots, X_n]$ be the homogenization of the partial derivative $\partial_i f$. The resultant of $\langle (\partial_1 f)^h, \dots, (\partial_n f)^h, X_0 \rangle$ does not vanish if an only if the projective variety associated to this ideal is empty, which only happens when the projective variety defined by the homogenized partial derivatives has dimension zero (as otherwise this variety would intersect the hyperplane “at infinity” $X_0 = 0$) and they have no solutions “at infinity”. By [BTZ25, Rmk. 2.16], we can perform this check in $\tilde{\mathcal{O}}_B(e^{\omega n} d^{(\omega+1)n} \tau)$ bit operations, where $\omega$ is the exponent of matrix multiplication. The SOS-RUR algorithm performs several of these resultant computations to compute the RUR of $I_{\nabla f}$, so at no extra cost, we can perform this test.

The following theorem bounds the bit complexity of verifying if a certificate is valid. For more details on the verification, we refer the reader to [BTZ25, Sec. 4].

**Theorem 2.10** ([BTZ25, Thm. 4.5]). Consider $f \in \mathbb{Q}[X]$ of even degree and size $(d, \tau)$. Assume that its infimum is attained (see Rmk. 2.6). Given a certificate of nonnegativity of $f$ as in Def. 2.5, we can verify if the certificate is valid in $\tilde{\mathcal{O}}_B((nd)^{(3\omega+4)n} \tau)$ bit operations.

**Remark 2.11.** Observe that, a valid certificate of nonnegativity of $f$ exists only if its gradient ideal is zero-dimensional. If this is not the case, then condition (3) in Def. 2.5 is not satisfied.

## 2.3 Lower bounds for critical values

In this work we will perturb polynomials without changing their nonnegativity. In order to quantify how small pertubations we can consider, we need to study lower bounds for critical values.

**Definition 2.12.** Let $f \in \mathbb{R}[X]$. We denote by $\mathbf{B}(f)$ the greatest lower bound on the absolute values of the nonzero critical values of $f$, that is

$$ \mathbf{B}(f) := \inf\{|f(\boldsymbol{x})| : \boldsymbol{x} \in \mathbb{C}^n, f(\boldsymbol{x}) \neq 0, \nabla f(\boldsymbol{x}) = \mathbf{0}\}. $$

For polynomial with integer coefficients, Brownawell and Yap [BY09] give a universal lower bound for $\mathbf{B}(f)$, that depends on the number of variables, the degree, and the bitsize of the polynomial, and not on the polynomial itself.

**Theorem 2.13** ([BY09, Cor. 2]). Consider any nonzero $f \in \mathbb{Z}[X]$ of degree at most $d$, such that $H(f) \le 2^\tau$. It holds

$$ \mathbf{B}(f) \ge \mathbf{B}(n, d, \tau) := ((n+2)^2 e^{n+3})^{-(n+1)(n+2)d^{n+1}} (n^n(n+1)d^{2\tau})^{-(n+1)d^n} = 2^{-\tilde{\mathcal{O}}(nd^n(n^2d+\tau))}. $$

## 2.4 Coercive polynomials and radius of positivity

A (special) family of polynomials that attain their infimum and are useful in our study is defined next.

**Definition 2.14** (Coerciveness). A function $f: \mathbb{R}^n \to \mathbb{R}$ is coercive, if for any sequence $\{\boldsymbol{x}_i\}_{i \in \mathbb{N}}$ of points in $\mathbb{R}^n$, such that $\|\boldsymbol{x}_i\|_2 \to +\infty$, we have $f(\boldsymbol{x}_i) \to +\infty$. A real polynomial $f \in \mathbb{R}[X]$ is coercive if it is coercive as a real function.

A coercive function always attains its infimum. For a detailed treatment of the properties of coercive functions, we refer the readers to [Per88, Sec. 1.4].

**Lemma 2.15.** Every coercive function attains its infimum.

The radius of positivity of a function (in our case, polynomial) is the radius of a ball centered at the origin, outside of which the function is nonnegative. In most cases that we study, we do not need the exact value of the radius, as an upper bound suffices. For coercive functions the existence of (trivial or at least effective bounds on) the radius of positivity is guaranteed by the definition of the limit.

**Definition 2.16** (Radius of positivity). Let $f \in \mathbb{R}[X]$ be a polynomial in $n$ variables, of even degree. The radius of positivity of $f$ is the smallest nonnegative number $R(f)$ such that $f(\boldsymbol{x}) \ge 0$, for all $\boldsymbol{x} \in \mathbb{R}^n$ with $\|\boldsymbol{x}\|_2 \ge R(f)$. Abusing the notation, we also use $R(f)$ for an upper bound on this quantity.
# 3 Stereographic transformation and positivity

We introduce the stereographic transformation. This transformation preserves the nonnegativity of polynomials. Its principal advantage is that the transformed polynomial is coercive, which means that its value tends to +∞ as the argument tends to infinity. Consequently, the transformed polynomial is positive outside a sufficiently large Euclidean ball and all minimizers are confined to its interior. This property allows us to avoid the difficulty of analyzing and certifying asymptotic critical values of polynomials. Moreover, we can derive an a priori bound for the radius of such a ball; this bound depends only on the degree of the polynomial and the bitsize of its coefficients, and not on the particular polynomial. In this way, we reduce the problem of determining whether a polynomial is globally nonnegative to the problem of verifying its nonnegativity on a compact set that has a size depending solely on its degree and bitsize. The compactness enable us to perform uniformly small perturbations.

## 3.1 Stereographic transformation preserves nonnegativity

To establish nonnegativity of a polynomial, we study transformations that preserve this property. We begin with homogenization. It is a classical result that a polynomial is nonnegative if and only if its homogenization is nonnegative. We recall the following lemma and refer the reader to Marshall's monograph [Mar08] for the proof.

**Lemma 3.1** ([Mar08, Prop. 1.2.4]). Let $f \in \mathbb{R}[X]$ and let $f^h$ denote the homogenization of $f$. Then, $f$ is nonnegative if and only if $f^h$ is nonnegative.

From a geometric point of view, the stereographic projection maps the sphere, minus the projection point, diffeomorphically onto a hyperplane. Within its domain it is smooth, bijective, and conformal, although it does not preserve distances or areas.

We need a variant of stereographic projection, that we call the stereographic transformation. We obtain it from substituting into the homogenized polynomial the numerator(s) of the stereographic projection; this results in a polynomial and helps us to avoid manipulating rational functions.

**Definition 3.2** (Stereographic transformation). Consider $f \in \mathbb{R}[X]$ with degree $d$ and let $f^h$ denote its homogenization. The stereographic transformation of $f$ is

$$S(f)(\mathbf{X}) := f^h(2X_1, \dots, 2X_n, -1 + \sum_{i=1}^n X_i^2).$$

As a function, the stereographic transformation of a polynomial behaves as follows,

$$S(f)(\mathbf{x}) = \begin{cases} (-1 + \|\mathbf{x}\|_2^2)^d f\left(\frac{2x_1}{-1+\|\mathbf{x}\|_2^2}, \dots, \frac{2x_n}{-1+\|\mathbf{x}\|_2^2}\right), & \text{if } \|\mathbf{x}\|_2 \neq 1 \\ 2^d f^{(d)}(\mathbf{x}), & \text{if } \|\mathbf{x}\|_2 = 1 \end{cases} \quad (3)$$

where $f^{(d)}$ is the highest degree homogeneous part of $f$.

We now show that the stereographic transformation preserves nonnegativity of polynomials.

**Theorem 3.3.** $f \in \mathbb{R}[X]$ is nonnegative on $\mathbb{R}^n$ if and only if $S(f) \in \mathbb{R}[X]$ is nonnegative on $\mathbb{R}^n$.

*Proof.* If $f \in \mathbb{R}[X]$ is homogeneous in variables $X_1, \dots, X_n$, then

$$S(f)(\mathbf{X}) = f^h(2X_1, \dots, 2X_n, -1 + \sum_{i=1}^n X_i^2) = f(2X_1, \dots, 2X_n),$$

and the claim follows immediately. Hence, we may assume that $f$ is not homogeneous.

The proof proceeds by successively reducing the nonnegativity of $f$ to that of $f^h$ on the unit sphere,
and finally to $\mathbb{R}^n$ via the stereographic projection, which establishes the equivalence for $S(f)$. We have

$$ 
\begin{aligned}
f \ge 0 \text{ on } \mathbb{R}^n &\iff f^h \ge 0 \text{ on } \mathbb{R}^{n+1} \iff f^h \ge 0 \text{ on the unit sphere } \mathbb{S}^n \\
&\iff f^h \ge 0 \text{ on } \mathbb{S}^n \setminus \{p\}, \quad \text{where } p = (0, \dots, 0, 1) \text{ is the north pole of } \mathbb{S}^n, \\
&\quad \text{(by the continuity of } f^h\text{)} \\
&\iff f^h \left( \frac{2X_1}{1 + \sum_{i=1}^n X_i^2}, \dots, \frac{2X_n}{1 + \sum_{i=1}^n X_i^2}, \frac{-1 + \sum_{i=1}^n X_i^2}{1 + \sum_{i=1}^n X_i^2} \right) \ge 0 \text{ on } \mathbb{R}^n \\
&\iff f^h (2X_1, \dots, 2X_n, -1 + \sum_{i=1}^n X_i^2) \ge 0 \text{ on } \mathbb{R}^n, \\
&\quad \text{(since } 1 + \sum_{i=1}^n X_i^2 > 0 \text{ everywhere, we can omit the denominators)} \\
&\iff S(f) \ge 0 \text{ on } \mathbb{R}^n.
\end{aligned}
\quad \square
$$

## 3.2 Stereographic transformation and coercive polynomials

In what follows we show that, when the constant term of $f$ is positive, $S(f)$ is a coercive function (Def. 2.14). This follows from the observation that the highest degree homogeneous part of $S(f)$ is of even degree on each variable and each leading monomial has a positive coefficient.

**Theorem 3.4.** Let $f \in \mathbb{Z}[\mathbf{X}]$ be a polynomial of even degree $d$ with $f(0) > 0$. When $\|\mathbf{x}\|_2 \ge 1$, we have

$$ S(f)(\mathbf{x}) \ge \|\mathbf{x}\|_2^{2d} - 2^{n+2d} H(f) \|\mathbf{x}\|_2^{2d-1}. $$

Thus, $S(f)$ is coercive and attains its infimum.

*Proof.* Let $f = \sum_{|\alpha| \le d} a_\alpha \mathbf{X}^\alpha$ and denote by $f^h = \sum_{|\alpha| \le d} a_\alpha \mathbf{X}^\alpha X_0^{d-|\alpha|}$ its homogenization. For $\mathbf{x} \in \mathbb{R}^n$, we have

$$ 
\begin{aligned}
S(f)(\mathbf{x}) &= a_0 \|\mathbf{x}\|_2^{2d} + a_0 \left( \sum_{i=1}^d \binom{d}{i} (-1)^i \|\mathbf{x}\|_2^{2d-2i} \right) + \sum_{0 < |\alpha| \le d} a_\alpha 2^{|\alpha|} |\mathbf{x}^\alpha| (-1 + \|\mathbf{x}\|_2^2)^{d-|\alpha|} \\
&\ge a_0 \|\mathbf{x}\|_2^{2d} - \left| a_0 \left( \sum_{i=1}^d \binom{d}{i} (-1)^i \|\mathbf{x}\|_2^{2d-2i} \right) \right| - \left| \sum_{0 < |\alpha| \le d} a_\alpha 2^{|\alpha|} |\mathbf{x}^\alpha| (-1 + \|\mathbf{x}\|_2^2)^{d-|\alpha|} \right|.
\end{aligned}
\quad (4) $$

Observe that, for any $\alpha$, $|a_\alpha| \le H(f)$, as $a_\alpha \in \mathbb{Z}$. Moreover, $|\mathbf{x}^\alpha| \le \|\mathbf{x}\|_2^{|\alpha|}$. As $\|\mathbf{x}\|_2 \ge 1$, $\|\mathbf{x}\|_2^i < \|\mathbf{x}\|_2^j$, for $i < j$, and $\|\mathbf{x}\|_2^{|\alpha|} (-1 + \|\mathbf{x}\|_2^2)^{d-|\alpha|} \le \|\mathbf{x}\|_2^{2d-|\alpha|}$. Hence, we have that

$$ 
\begin{aligned}
\left| a_0 \left( \sum_{i=1}^d \binom{d}{i} (-1)^i \|\mathbf{x}\|_2^{2d-2i} \right) \right| &\le 2^d H(f) \|\mathbf{x}\|_2^{2d-2} \quad \text{and} \\
\left| \sum_{0 < |\alpha| \le d} a_\alpha 2^{|\alpha|} |\mathbf{x}^\alpha| (-1 + \|\mathbf{x}\|_2^2)^{d-|\alpha|} \right| &\le 2^d \left( \binom{d+n}{n} - 1 \right) H(f) \|\mathbf{x}\|_2^{2d-1}.
\end{aligned}
$$

Observe that, as $a_0 \in \mathbb{Z}$ is positive, $a_0 \ge 1$. Therefore,

$$ S(f)(\mathbf{x}) \ge \|\mathbf{x}\|_2^{2d} - 2^d \binom{d+n}{n} H(f) \|\mathbf{x}\|_2^{2d-1} \ge \|\mathbf{x}\|_2^{2d} - 2^{n+2d} H(f) \|\mathbf{x}\|_2^{2d-1}. \quad (5) $$

In particular, when $\|\mathbf{x}\|_2 \ge 2^{n+2d} H(f)$, we have $S(f) \ge 0$. It also follows that $S(f)$ is coercive and therefore attains infimum. $\square$

**Corollary 3.5.** Let $f \in \mathbb{Z}[\mathbf{X}]$ be a polynomial of even degree $d$ such that $f(0) > 0$ and $H(f) \le 2^\tau$. Let

$$ \mathbb{R}(n, d, \tau) := 2^{n+2d+\tau} = 2^{\mathcal{O}(n+d+\tau)}. \quad (6) $$

If $\|\mathbf{x}\|_2 \ge \mathbb{R}(n, d, \tau)$, then $S(f)(\mathbf{x}) \ge 0$. We also use $\mathbb{R}(n, d, \tau)$ for the value of $\mathbb{R}(S(f))$ following Def. 2.16.
**Remark 3.6.** We can prove the coerciveness of $\mathcal{S}(f)$ and compute (actually bound) the radius $\mathbb{R}$ in a more general framework, that is the class of stably bounded from below polynomials, studied by Marshall [Mar03, Thm. 5.1], see also [JL05, Lem. 1]. We choose to prove the coerciveness directly for the polynomial $\mathcal{S}(f)$, as this results in a better bound of the radius $\mathbb{R}(\mathcal{S}(f))$. In particular, following Marshall [Mar03, Thm. 5.1] or Jibetean and Laurent [JL05, Lem. 1] we bound the radius by $\max\{1, \frac{1}{\min\mathcal{S}(f)^{(2d)}} \sum_{|\alpha| \le 2d-1} |c_\alpha|\}$, where $c_\alpha$ is the coefficient of $\mathbf{X}^\alpha$ in the polynomial $\mathcal{S}(f)$, $\mathcal{S}(f)^{(2d)}$ is the highest degree homogeneous part of $\mathcal{S}(f)$, and $\min\mathcal{S}(f)^{(2d)}$ is its minmum on the unit sphere $\mathbb{S}^{n-1}$. Straightforward computations yield the estimations $\min\mathcal{S}(f)^{(2d)} = a_0 \ge 1$ and $\sum_{|\alpha| \le 2d-1} |c_\alpha| \le (n+1)^d 2^{2n+4d+\tau}$, and so the radius is bounded by $(n+1)^d 2^{2n+4d+\tau}$.

## 3.3 Tracing witness points from $\mathcal{S}(f)$ to $f$

We now establish a relation between a negative evaluation of $\mathcal{S}(f)$ and a corresponding negative evaluation of $f$. In particular, any (rational) point at which $\mathcal{S}(f)$ takes a negative value corresponds to an explicit (rational) witness point; the latter establishes that $f$ is not nonnegative.

**Lemma 3.7.** Let $f = \sum_{\alpha} a_{\alpha} X^{\alpha} \in \mathbb{Z}[\mathbf{X}]$ be a polynomial of even degree $d$, and let $\mathbf{x} \in \mathbb{Q}^n$ be such that $\mathcal{S}(f)(\mathbf{x}) < 0$. Define $H(\mathbf{x}) := \max_{1 \le i \le n} H(x_i)$ and

$$C_{f, \mathbf{x}} := 2^{n+2d-1} H(\mathbf{x})^{(n+1)d-1} H(f).$$

We define

$$\mathcal{Q}(f, \mathbf{x}) := \begin{cases} \left( \frac{2x_1}{-1+\|\mathbf{x}\|_2^2}, \dots, \frac{2x_n}{-1+\|\mathbf{x}\|_2^2} \right), & \text{if } \|\mathbf{x}\|_2 \ne 1 \\ (2x_1 C_{f, \mathbf{x}}, \dots, 2x_n C_{f, \mathbf{x}}), & \text{if } \|\mathbf{x}\|_2 = 1. \end{cases}$$

Then $f(\mathcal{Q}(f, \mathbf{x})) < 0$. Moreover, we have

$$H(\mathcal{Q}(f, \mathbf{x})) \le 2^{n+2d} H(\mathbf{x})^{(n+1)d} H(f).$$

*Proof.* Given the expansion of the stereographic transformation from Eq. 4, we distinguish two cases. Case 1: $\|\mathbf{x}\|_2 \ne 1$. From (4) we can factor out $(-1 + \|\mathbf{x}\|_2^2)^d$, which leads to

$$\mathcal{S}(f)(\mathbf{x}) = (-1 + \|\mathbf{x}\|_2^2)^d \left( f_0 + \sum_{0 < |\alpha| \le d} f_\alpha 2^{|\alpha|} \mathbf{x}^\alpha (-1 + \|\mathbf{x}\|_2^2)^{-|\alpha|} \right).$$

Since $d$ is even, the factor $(-1 + \|\mathbf{x}\|_2^2)^d$ is nonnegative. Hence, the sign of $\mathcal{S}(f)(\mathbf{x})$ is determined by the factor in the parentheses. The assumption $\mathcal{S}(f)(\mathbf{x}) < 0$ implies

$$f_0 + \sum_{0 < |\alpha| \le d} f_\alpha 2^{|\alpha|} \mathbf{x}^\alpha (-1 + \|\mathbf{x}\|_2^2)^{-|\alpha|} < 0,$$

which is precisely the evaluation $f(\mathcal{Q}(f, \mathbf{x})) < 0$ with $\mathcal{Q}(f, \mathbf{x}) = (2x_1/(-1 + \|\mathbf{x}\|_2^2), \dots, 2x_n/(-1 + \|\mathbf{x}\|_2^2))$. In this case, we have $H(\mathcal{Q}(f, \mathbf{x})) \le (n+1)H(\mathbf{x})^{2n}$.

Case 2: $\|\mathbf{x}\|_2 = 1$. In this case, (4) simplifies to

$$\mathcal{S}(f)(\mathbf{x}) = \sum_{|\alpha|=d} f_{\alpha} 2^{|\alpha|} \mathbf{x}^{\alpha} = 2^d \sum_{|\alpha|=d} f_{\alpha} \mathbf{x}^{\alpha}, \quad (7)$$

since all terms with $|\alpha| < d$ vanish. As $\mathcal{S}(f)(\mathbf{x}) < 0$ and $f_\alpha \in \mathbb{Z}$, we have the lower bound $\mathcal{S}(f)(\mathbf{x}) \le -H(\mathbf{x})^{-nd}$. Because $d$ is even, the sign of $f(\mathcal{Q}(f, \mathbf{x})) = (C_{f, \mathbf{x}})^d f^h(2x_1, \dots, 2x_n, 1/C_{f, \mathbf{x}})$ coincides with the sign of $f^h(2x_1, \dots, 2x_n, 1/C_{f, \mathbf{x}})$. We thus estimate

$$\begin{align*} f^h(2x_1, \dots, 2x_n, 1/C_{f, \mathbf{x}}) &= \sum_{|\alpha| \le d} a_\alpha 2^{|\alpha|} \mathbf{x}^\alpha C_{f, \mathbf{x}}^{-(d-|\alpha|)} = \mathcal{S}(f)(\mathbf{x}) + \sum_{|\alpha| < d} a_\alpha 2^{|\alpha|} \mathbf{x}^\alpha C_{f, \mathbf{x}}^{-(d-|\alpha|)} \quad \text{(by (7))} \\ &\le -\frac{1}{H(\mathbf{x})^{nd}} + \sum_{|\alpha| < d} H(f) 2^{d-1} H(\mathbf{x})^{d-1} C_{f, \mathbf{x}}^{-1} \quad \text{(since } |\mathbf{x}^\alpha| \le H(\mathbf{x})^{|\alpha|}) \\ &\le -\frac{1}{H(\mathbf{x})^{nd}} + 2^{n+d-1} H(f) 2^{d-1} H(\mathbf{x})^{d-1} C_{f, \mathbf{x}}^{-1} < 0. \end{align*}$$
Therefore $f(\mathcal{Q}(f, \boldsymbol{x})) = (C_{f,\boldsymbol{x}})^d f^h(2x_1, \dots, 2x_n, 1/C_{f,\boldsymbol{x}}) < 0$, and $H(\mathcal{Q}(f, \boldsymbol{x})) \le H(\boldsymbol{x})^{(n+1)d}H(f)2^{n+2d}$. $\square$

## 3.4 Bounds on critical values

In this subsection, we study upper bounds for the smallest absolute value of the nonzero critical values of $S(f)$. For this, we need the following auxiliary inequality relating the coefficient sizes of $f$ and $S(f)$.

**Lemma 3.8.** Let $f \in \mathbb{Z}[\mathbf{X}]$ be a polynomial in $n$ variables of degree $d$ such that $H(f) \le 2^\tau$. Then,

$$H(S(f)) \le 2^d \binom{n+d}{d} (n+1)^d H(f) \le 2^{d \lg(n+1)+n+2d+\tau}.$$

*Proof.* If we write $f = \sum_{|\alpha| \le d} f_\alpha \mathbf{X}^\alpha$, we have that $S(f)(\mathbf{X}) = \sum_{|\alpha| \le d} a_\alpha 2^{|\alpha|} \mathbf{X}^\alpha (-1 + \sum_{i=1}^n X_i^2)^{d-|\alpha|}$. To estimate $H(S(f))$ we bound the coefficients of the right-hand side of the previous equation. Thus

$$ \begin{aligned} H(S(f)) &\le 2^d H(f) \sum_{|\alpha| \le d} H \left( \mathbf{X}^\alpha (-1 + \sum_{i=1}^n X_i^2)^{d-|\alpha|} \right) \\ &\le 2^d H(f) \sum_{|\alpha| \le d} \max \left\{ \binom{d}{k_0, \dots, k_n} : k_0 + \dots + k_n = d \right\} \\ &\le 2^d \binom{n+d}{d} (n+1)^d H(f) \quad \left( \text{since } \binom{d}{k_0, \dots, k_n} \le (n+1)^d \right) \quad \square \end{aligned} $$

**Corollary 3.9.** Let $f \in \mathbb{Z}[\mathbf{X}]$ be a polynomial in $n$ variables of degree $d$ such that $H(f) \le 2^\tau$. The smallest absolute value of the nonzero critical values of $S(f)$, $\mathbf{B}(S(f))$, is upper-bounded by

$$\mathbf{B}(S(f)) \ge \mathbf{B}(n, 2d, d \lg(n+1) + n + 2d + \tau) = 2^{-\tilde{\phi}(n(2d)^n(n^2d+\tau))},$$

where $\mathbf{B}(n, d, \tau)$ is as defined in Thm. 2.13.

*Proof.* By Lem. 3.8, we have $H(S(f)) \le 2^{d \lg(n+1)+n+2d+\tau}$. Combining this bound with Thm. 2.13, we have $\mathbf{B}(S(f)) \ge \mathbf{B}(n, 2d, d \lg(n+1) + n + 2d + \tau)$. $\square$

# 4 Perturbations preserving nonnegativity

The stereographic transformation allows us to transform (back-and-forth) nonnegative polynomials into nonnegative polynomials attaining their infimum. For a polynomial attaining its infimum, we can certify its nonnegativity by certifying that all its critical values are nonnegative. Algorithm SOS-RUR can do this when the gradient ideal is zero-dimensional (and so, there is a finite number of critical points). We introduce a perturbation that guarantees that the gradient ideal of the perturbed polynomial is zero-dimensional.

## 4.1 Hanzon-Jibetean perturbations

Hanzon and Jibetean [HJ03] studied algebraic algorithms to approximate the global minimum of a polynomial. Their main idea is, when the critical points are finite, to approximate the critical values by approximating these points. However, when this is not the case, then they showed that it is possible to perturb the input polynomial to obtain a coercive polynomial that has a similar minimum but also a finite number of critical points. Hence, to approximate the minimum, they proceed by considering successive smaller perturbations.

Inspired by their construction, we show that, given a coercive polynomial, one can construct a sufficiently small perturbation, which we call *Hanzon-Jibetean perturbation*, such that the perturbed polynomial is nonnegative if and only if the original polynomial is nonnegative.
**Definition 4.1** (HJ perturbation). Let $f \in \mathbb{R}[\mathbf{X}]$ be a polynomial in $n$ variables, of degree $d$, and let $\lambda$ be any positive real number. The positive (respectively, negative) HJ perturbation of $f$ is defined as

$$ \mathcal{P}_{\lambda}(f)(\mathbf{X}) := f(\mathbf{X}) + \lambda \sum_{i=1}^{n} (1 + X_{i}^{2} + X_{i}^{d+2}), \quad \text{and} \\ \mathcal{N}_{\lambda}(f)(\mathbf{X}) := f(\mathbf{X}) - \lambda \sum_{i=1}^{n} (1 + X_{i}^{2} + X_{i}^{d}). $$

Notice that $\mathcal{P}_{\lambda}(f)$ and $\mathcal{N}_{\lambda}(f)$ apply perturbations of different degrees. The slightly higher degree perturbation in $\mathcal{P}_{\lambda}(f)$ simplifies some arguments in the proof that follows and it corresponds to (a slight variant of) the original perturbation introduced by Hanzon-Jibetean.

**Theorem 4.2** ([HJ03, Sec. 3 and Prop. 3.1]). Let $f \in \mathbb{R}[\mathbf{X}]$ be a polynomial of even degree $d$. For any positive constant $\lambda \in \mathbb{R}$, the polynomial $\mathcal{P}_{\lambda}(f)(\mathbf{X})$ is coercive and its corresponding gradient ideal $I_{\nabla\mathcal{P}_{\lambda}(f)}$ is zero-dimensional. Moreover, the gradient ideal has $(d+1)^n$ complex solutions (counted with multiplicities) and no solutions “at infinity”.

*Proof.* Following [HJ03, Prop. 3.1], the partial derivatives of $\mathcal{P}_{\lambda}(f)$ form a Gröbner basis for the gradient ideal $I_{\nabla\mathcal{P}_{\lambda}(f)}$ with respect to any graded order. Each partial derivative has leading monomial $X_i^{d+1}$, so the stair-case of the Gröbner basis is closed, and thus, the gradient ideal is zero-dimensional. Moreover, $\mathbb{K}[\mathbf{X}]/I_{\nabla\mathcal{P}_{\lambda}(f)}$ has dimension $(d+1)^n$, so the gradient system has the same number of complex points, counted with multiplicities. Each partial derivative at infinity is a power of a monomial, that is, $(\partial_i f)^h(0, X_1, \dots, X_n) = X_i^{d+1}$, so there are no solutions “at infinity”. $\square$

We show that, for generic choices of $\lambda$, that is for all $\lambda$ belonging to a Zariski open set, the perturbed polynomials of Def. 4.1 have radical gradient ideal, a zero dimensional gradient variety, and no solutions “at infinity”.

**Proposition 4.3.** For a generic $\lambda \neq 0$, $\mathcal{P}_{\lambda}(f)$ and $\mathcal{N}_{\lambda}(f)$ have zero-dimensional and radical gradient ideals. Moreover, the gradient system of $\mathcal{P}_{\lambda}(f)$, respectively $\mathcal{N}_{\lambda}(f)$, has $(d+1)^n$, respectively $(d-1)^n$, complex solutions (counted with multiplicities) and no solutions at “infinity”.

*Proof.* We show the statement for $F_t = \sum_i (1 + X_i^2 + X_i^l) + tf$, where $l = d$ or $d+2$. The original claim then follows by taking $t = \pm 1/\lambda$, $\lambda \neq 0$. We now establish zero-dimensionality of $I_{\nabla F_t}$ for generic $t \neq 0$ and treat only the case $l = d$, as $l = d+2$ was treated in Thm. 4.2.

For $t=0$ we have a polynomial $\sum_i (1 + X_i^2 + X_i^d)$, whose gradient ideal is obviously zero-dimensional. Consider the variety

$$ C = \{ (\mathbf{a}, t) \in \mathbb{A}_{\mathbb{C}}^{n} \times \mathbb{A}_{\mathbb{C}}^{1} : \partial_{1}F_{t}(\mathbf{a}) = \cdots = \partial_{n}F_{t}(\mathbf{a}) = 0 \} $$

and the projection $\pi|_C : C \to \mathbb{A}_{\mathbb{C}}^1$ to the second argument. By [Gro66, Thm. 3.1.5] the dimension of $C \cap \pi^{-1}(t)$ is an upper-semicontinuous function of $t \in \mathbb{A}_{\mathbb{C}}^1$. Therefore, since $C \cap \pi^{-1}(0)$ is a finite set, so is a generic fiber $C \cap \pi^{-1}(t)$, $t \in \mathbb{A}_{\mathbb{C}}^1 \setminus \{0\}$. The latter exactly means that the gradient ideal of $F_t$ is zero-dimensional. As at $t=0$ there are not solutions “at infinity”, the same holds for a generic fiber, and so the number of (affine) solutions for a generic fiber is the Bézout bound $(d-1)^n$.

Radicality of a zero-dimensional ideal $I_{\nabla F_t}$ (whose zero set is denoted by $X_t \subset \mathbb{A}_{\mathbb{C}}^n$) is equivalent to reducedness of local rings $\mathcal{O}_{X_t, \mathbf{a}}$ at every $\mathbf{a} \in X_t$. The latter condition is equivalent for $\mathbf{a} \in X_t$ to be a non-denenerate critical point of $F_t$, that is, $\partial_1 F_t(\mathbf{a}) = \cdots = \partial_n F_t(\mathbf{a}) = 0$ and $\det(\frac{\partial^2 F_t}{\partial x_i \partial x_j}(\mathbf{a})) \neq 0$. Consider now the variety

$$ D = \left\{ (\mathbf{a}, t) \in \mathbb{A}_{\mathbb{C}}^{n} \times \mathbb{A}_{\mathbb{C}}^{1} : \partial_{1}F_{t}(\mathbf{a}) = \cdots = \partial_{n}F_{t}(\mathbf{a}) = 0, \det\left(\frac{\partial^{2}F_{t}}{\partial x_{i}\partial x_{j}}(\mathbf{a})\right) = 0 \right\} \quad (8) $$

of “bad” pairs (that is, non-reduced points together with the parameter $t$). Its projection $\pi(D)$ under $\pi: \mathbb{A}_{\mathbb{C}}^n \times \mathbb{A}_{\mathbb{C}}^1 \to \mathbb{A}_{\mathbb{C}}^1$ is a constructible subset of $\mathbb{A}_{\mathbb{C}}^1$. Because $0 \notin \pi(D)$ (as the gradient ideal of $\sum_i (1 + X_i^2 + X_i^l)$ is radical), $\pi(D)$ is a finite set. This means that $I_{\nabla F_t}$ is radical for all but finitely many $t \in \mathbb{A}_{\mathbb{C}}^1$. $\square$

Working with polynomials with zero-dimensional gradient ideal and no solutions “at infinity” allow us to compute our certificates faster, see Thm. 2.8. Prop. 4.3 implies that for most $\lambda$'s, $\mathcal{N}_{\lambda}(S(f))$ satisfies the above assumptions. In what follows we quantify how many *unlucky* choices of $\lambda$'s there are.
**Lemma 4.4.** Consider non-zero $f \in \mathbb{Z}[\mathbf{X}]$, in $n$ variables, of even degree $d$, such that $f$ and its highest degree homogeneous part are positive. We have that there are at most $(2d-1)^{n-1}(2d-1+n)$ values for $\lambda$ such that either the gradient ideal of $\mathcal{N}_{\lambda}(\mathcal{S}(f))$ is not zero-dimensional or it has solutions “at infinity”.

*Proof.* We proceed as in Rmk. 2.9. Let $g_i := \partial_i(\mathcal{N}_{\lambda}(\mathcal{S}(f)))$ and consider its homogenization $g_i^h \in \mathbb{Z}[X_0, X_1, \dots, X_n]$. The resultant of the homogeneous system $(g_1^h, \dots, g_n^h, X_0)$ vanishes if and only if this system has a solution in $\mathbb{P}^n$, the $n$-dimensional complex projective space. If the resultant does not vanish, then the system has no solutions at infinity. Moreover, the variety defined by $(g_1^h, \dots, g_n^h)$ is zero-dimensional, as otherwise it has to intersect the hyperplane $X_0 = 0$. The resultant of this system is a polynomial in $\lambda$ of degree at most $(2d-1)^{n-1}(2d-1+n)$ [CLO05]. The proof follows straightforwardly by noting that, by Prop. 4.3, this resultant is a non-zero polynomial. $\square$

## 4.2 Positive perturbations preserving nonnegativity

We quantify the size of perturbations of coercive polynomials that preserve nonnegativity.

**Theorem 4.5.** Let $f \in \mathbb{Z}[\mathbf{X}]$ be a coercive polynomial in $n$ variables, of even degree $d$. Consider $\lambda \in (0, \frac{1}{6n} \frac{\mathbf{B}(f)}{\mathbf{R}(f)^{d+2}}]$, where $\mathbf{B}(f)$ is a lower bound on the absolute values of the nonzero critical values of $f$ (Def. 2.12) and $\mathbf{R}(f)$ is the radius of positivity (Def. 2.16). We assume with no loss of generality that $\mathbf{R}(f) > 1$. We have the following equivalence:

$$f \ge 0 \iff \mathcal{P}_{\lambda}(f) \ge 0.$$

*Proof.* The implication ($\implies$) is immediate. The perturbation term $\lambda(\sum_{i=1}^n 1 + X_i^2 + X_i^{d+2})$ is nonnegative on $\mathbb{R}^n$ because $d$ is even and $\lambda > 0$. Hence, if $f(\mathbf{x}) \ge 0$ for $\mathbf{x} \in \mathbb{R}^n$, then $\mathcal{P}_{\lambda}(f)(\mathbf{x}) \ge 0$.

For the converse implication ($\iff$), suppose that $f$ is not nonnegative. Let $\mathcal{D}(\mathbf{R}(f)) := \{\mathbf{x} \in \mathbb{R}^n : \|\mathbf{x}\| \le \mathbf{R}(f)\}$ and choose $\mathbf{x}_0 = (x_{01}, \dots, x_{0n}) \in \mathcal{D}(\mathbf{R}(f))$, such that $f(\mathbf{x}_0) = \min_{\mathbf{x} \in \mathcal{D}(\mathbf{R}(f))} f(\mathbf{x})$. Since $f$ is not nonnegative, $f(\mathbf{x}_0) < 0$. By the definition of $\mathcal{D}(\mathbf{R}(f))$, we have $\mathbf{x}_0 \in \text{Int} \mathcal{D}(\mathbf{R}(f))$ and $\mathbf{x}_0$ is a critical point of $f$, where $\text{Int} \mathcal{D}(\mathbf{R}(f))$ is the interior of the ball $\mathcal{D}(\mathbf{R}(f))$. As $\mathbf{B}(f)$ is a positive lower bound for the absolute values of all nonzero critical values of $f$, it follows that $f(\mathbf{x}_0) \le -\mathbf{B}(f)$. Moreover,

$$\lambda \sum_{i=1}^{n} (1 + x_{0i}^2 + x_{0i}^{d+2}) \le \frac{1}{6n} \frac{\mathbf{B}(f)}{\mathbf{R}(f)^{d+2}} \sum_{i=1}^{n} (1 + x_{0i}^2 + x_{0i}^{d+2}) \le \frac{1}{6n} \frac{\mathbf{B}(f)}{\mathbf{R}(f)^{d+2}} \cdot 3n \mathbf{R}(f)^{d+2} = \frac{1}{2} \mathbf{B}(f).$$

The evaluation of $\mathcal{P}_{\lambda}(f)$ at $\mathbf{x}_0$ yields $\mathcal{P}_{\lambda}(f)(\mathbf{x}_0) \le -\mathbf{B}(f) + \frac{1}{2}\mathbf{B}(f) = -\frac{1}{2}\mathbf{B}(f) < 0$, which contradicts the assumption that $\mathcal{P}_{\lambda}(f)$ is nonnegative on $\mathbb{R}^n$. Thus, $f$ is nonnegative on $\mathbb{R}^n$. $\square$

As the stereographic transformation preserves nonnegativity (Thm. 3.3) and leads to coercive polynomials, we can mix the previous theorem with this transformation. In what follows we do so by mixing these ideas with precise bounds for critical values and radii of positivity.

**Theorem 4.6.** Let $f \in \mathbb{R}[\mathbf{X}]$ be a polynomial in $n$ variables, of even degree $d$, such that $f(\mathbf{0}) > 0$ and $H(f) \le 2^{\tau}$. Consider the following positive $\epsilon(n, d, \tau)$ defined as

$$\epsilon(n, d, \tau) := \frac{\mathbf{B}(n, 2d, d \lg(n+1) + n + 2d + \tau)}{6n \mathbf{R}(n, d, \tau)^{2d+2}} = 2^{-\tilde{\Theta}(n(2d)^n(n^2d+\tau))}, \quad (9)$$

where $\mathbf{B}(n, d, \tau)$, respectively $\mathbf{R}(n, d, \tau)$, are as defined in Thm. 2.13, respectively Cor. 3.5. Then, for any $\lambda \in (0, \epsilon(n, d, \tau)]$, we have, over $\mathbb{R}^n$,

$$f \ge 0 \iff \mathcal{P}_{\lambda}(\mathcal{S}(f)) \ge 0,$$

Moreover $\mathcal{P}_{\lambda}(\mathcal{S}(f))$ satisfies (II) and, for generic choices of $\lambda$, the gradient ideal of $\mathcal{P}_{\lambda}(\mathcal{S}(f))$ is also radical.

*Proof.* First, we will prove that the transformation preserves nonnegativity. By Thm. 3.3, $f \ge 0 \iff \mathcal{S}(f) \ge 0$. Hence, we will prove that $\mathcal{S}(f) \ge 0 \iff \mathcal{P}_{\lambda}(\mathcal{S}(f)) \ge 0$. By Cor. 3.9, we have $\mathbf{B}(\mathcal{S}(f)) \ge \mathbf{B}(n, 2d, d \lg(n+1) + n + 2d + \tau)$. By Cor. 3.5, we can choose $\mathbf{R}(\mathcal{S}(f)) = \mathbf{R}(n, d, \tau)$. As $\mathcal{S}(f)$ is a coercive (Thm. 3.4), the equivalence $\mathcal{S}(f) \ge 0 \iff \mathcal{P}_{\lambda}(\mathcal{S}(f)) \ge 0$ follows straightforwardly from Thm. 4.5.

To conclude, observe that $\mathcal{S}(f)$ is coercive (and hence also $\mathcal{P}_{\lambda}(\mathcal{S}(f))$ for all $\lambda > 0$) and, by Thm. 4.2, the gradient ideal of $\mathcal{P}_{\lambda}(\mathcal{S}(f))$ is zero-dimensional, so it satisfies condition (II). Moreover, by Prop. 4.3, for a generic $\lambda$, the gradient ideal of $\mathcal{P}_{\lambda}(\mathcal{S}(f))$ is also radical. $\square$
## 4.3 Negative perturbations preserving nonnegativity

Given any polynomial $f$, we can always find $\lambda > 0$ such that $\mathcal{P}_\lambda(f)$ is nonnegative, regardless of $f$. This is why, if we want positive perturbations $\mathcal{P}_\lambda()$ to preserve positivity, we are forced to work with very small values of $\lambda$, depending on the size of $f$ and not the function defined by $f$. If we want to consider bigger perturbations, we can work with negative perturbations as the following lemma illustrates.

**Lemma 4.7.** Let $f \in \mathbb{Z}[X]$ and $\lambda > 0$ such that $\mathcal{N}_\lambda(f)(X) \ge 0$. Then, $f > 0$.

*Proof.* Observe that $\mathcal{N}_\lambda(f)(X) \ge 0$ is equivalent to $f(X) \ge \lambda \sum_{i=1}^n (1 + X_i^2 + X_i^d)$. As $\lambda > 0$, we have that $\lambda \sum_{i=1}^n (1 + X_i^2 + X_i^d) > 0$, so $f > 0$. $\square$

The problem with negative perturbations is that, even for positive functions, there might not be $\lambda > 0$ such that $\mathcal{N}_\lambda(f) \ge 0$.

**Example 4.8.** Let $f = (X_1X_2 - \frac{1}{2})^2 + \frac{1}{2}$. This function is positive, but for any $\lambda > 0$, $\mathcal{N}_\lambda(f)(\frac{1}{\sqrt{\lambda}}, 0) < 0$.

In what follows we restrict ourselves to negative perturbations of coercive functions obtained by the stereographic transformation. The zeros of these functions are related to zeros at infinity.

**Lemma 4.9.** Let $f \in \mathbb{Z}[X]$ be a polynomial in $n$ variables, of even degree $d$, and $f(0) \ne 0$. Then, $S(f)$ is strictly positive on $\mathbb{R}^n$ if and only if the highest degree homogeneous part of $f$, $f^{(d)}$, has no zeros on the unit sphere $S^{n-1}$, and $f$ is strictly positive on $\mathbb{R}^n$.

*Proof.* By Thm. 3.3, the stereographic transformation preserves nonnegativity. Assume that $S(f)(x) = 0$. By (3), either $||x||_2 \ne 1$ and there is $y \in \mathbb{R}^n$ such that $f(y) = 0$ (as $(-1 + ||x||_2^2)^d > 0$), or $f^{(d)}(x) = 0$. Alternately, as $f^{(d)}$ is homogeneous, if there is $x$ such that $f^{(d)}(x) = 0$, we can assume that $||x||_2 = 1$, and so $S(f)(x) = 0$. Assume now that $f(x) = 0$ for some $x \in \mathbb{R}^n$. Then $f^h(1, x) = 0$. Scaling down this vector to the unit sphere, we have that $f^h(z_0, z) = 0$ for some $(z_0, z) \in S^n$ with $z_0 \ne 0$. Under stereographic projection, points with zero first coordinates correspond to vectors in $\mathbb{R}^n$ of unit length. It follows that there is $y \in \mathbb{R}^n$ such that $||y||_2 \ne 1$ and $S(f)(y) = 0$. $\square$

Like in the case of positive HJ perturbations, in what follows we establish an equivalence of strict positivity between a polynomial and its negative HJ perturbation under the assumption that the highest degree homogeneous part the polynomial has no zeros on the unit sphere.

**Theorem 4.10.** Let $f \in \mathbb{Z}[X]$ be a polynomial in $n$ variables, of even degree $d$, $f(0) > 0$, and $H(f) \le 2^\tau$. Let $f^{(d)}$ be the highest degree homogeneous part of $f$ and let $\mathbb{R}(n, d, \tau)$ be the constant defined in Eq. 6. For any $\lambda \in (0, \frac{1}{6n \min \mathbb{R}(n, d, \tau)^{2d}}]$, we have the following equivalence

$$ \left\{ \begin{array}{ll} f > 0 & \text{on } \mathbb{R}^n, \text{ and} \\ f^{(d)} & \text{no zeros on } S^{n-1} \end{array} \right\} \iff \mathcal{N}_\lambda(S(f)) \ge 0 \text{ on } \mathbb{R}^n. $$

In particular, we can consider any $\lambda \in (0, \epsilon(n, d, \tau)]$, where $\epsilon(n, d, \tau)$ is as defined in Eq. (9).

*Proof.* For the first part of the statement, observe that ($\iff$) is implied by Lem. 4.7. Hence we prove the direction ($\implies$). It follows from Eq. (3) that, if $d$ is even, $f > 0$ and $f^{(d)} > 0$, then $S(f) > 0$. Moreover, we have that $\min S(f) \le S(f)(0) = f(0) \le 2^\tau$.

Consider $\lambda \in (0, \frac{1}{2n \min \mathbb{R}(f)^{2d}}]$. When $||x||_2 \ge 1$, the inequality from Eq. (5), implies that

$$ \begin{aligned} \mathcal{N}_\lambda(S(f))(x) &\ge S(f)(x) - \left( \frac{1}{6n \min S(f)} \right) (3n \|x\|_2^{2d}) \\ &\ge \|x\|_2^{2d} - 2^d \binom{d+n}{n} H(f) \|x\|_2^{2d-1} - \left( \frac{2^\tau}{2 \mathbb{R}(n, d, \tau)^{2d}} \right) \|x\|_2^{2d} \end{aligned} $$

Hence, $\mathcal{N}_\lambda(S(f))$ is coercive and $\mathcal{N}_\lambda(S(f)) \ge 0$ when $||x||_2 \ge 2^{d+\tau+1} \binom{d+n}{n}$, as $2^\tau < \mathbb{R}(n, d, \tau)^{2d}$.

Next, we lower-bound the minimum of $\mathcal{N}_\lambda(S(f))$ on the ball of radius $2^{d+\tau+1} \binom{d+n}{n}$ centered at 0. As the maximum of $\sum_{i=1}^n (1 + x_i^2 + x_i^{2d})$ on this ball is attained in the boundary, it is upper bounded by
$3n (2^{d+\tau+1} \binom{d+n}{n})^{2d}$. Moreover, as $d > 1$, we have that $\binom{d+n}{n} \le 2^{d+n-1}$, and so $\mathbb{R}(n, d, \tau) \ge 2^{d+\tau+1} \binom{d+n}{n}$. Hence, we conclude that $\mathcal{N}_\lambda(\mathcal{S}(f)) \ge 0$, as for any $\|\mathbf{x}\|_2 \le 2^{d+\tau+1} \binom{d+n}{n}$,

$$ \mathcal{N}_\lambda(\mathcal{S}(f))(\mathbf{x}) \ge \min \mathcal{S}(f) - \frac{1}{6n} \min \mathcal{S}(f) \left( 3n \left( 2^{d+\tau+1} \binom{d+n}{n} \right)^{2d} \right) = \frac{\min \mathcal{S}(f)}{2} > 0 $$

The second part of the statement follows from Cor. 3.9, as when $\min \mathcal{S}(f) > 0$, $\min \mathcal{S}(f) \ge \mathbb{B}(\mathcal{S}(f))$. $\square$

In Thm. 4.10, the equivalence of strict positivity between $f$ and $\mathcal{N}_\lambda(\mathcal{S}(f))$ depends on $\lambda$ being small enough. In practice, if we find $\lambda$ such that $\mathcal{N}_\lambda(\mathcal{S}(f)) > 0$, then we can use it to certify the positivity of $f$ (Lem. 4.7). The following lemma shows that, if $\lambda$ is not too big, say $\lambda < f(\mathbf{0})$, then $\mathcal{N}_\lambda(\mathcal{S}(f))$ is still coercive. Therefore, we can choose any generic-enough $\lambda < f(\mathbf{0})$ and verify if $\mathcal{N}_\lambda(\mathcal{S}(f)) > 0$ using SOS-RUR. This way, Thm. 4.10 gives a lower bound on how small $\lambda$ can be in the worst-case.

**Lemma 4.11.** Let $f \in \mathbb{Z}[\mathbf{X}]$ be a polynomial in $n$ variables, of even degree $d$, and $f(\mathbf{0}) > 0$. If $\lambda < f(\mathbf{0})$, then $\mathcal{N}_\lambda(\mathcal{S}(f))$ is coercive.

*Proof.* By the definition of $\mathcal{N}_\lambda(\mathcal{S}(f))$, we have $\mathcal{N}_\lambda(\mathcal{S}(f))(\mathbf{X}) := \mathcal{S}(f)(\mathbf{X}) - \lambda \sum_{i=1}^n (1+X_i^2+X_i^{2d})$. Note that the highest degree homogeneous part of $\mathcal{N}_\lambda(\mathcal{S}(f))$ is the degree $2d$ terms in $a_0(-1+\|\mathbf{X}\|_2^2)^{d-\lambda} \sum_{i=1}^n X_i^{2d}$, which is $\sum_{0 \le i_1, \dots, i_n < d} a_0 \binom{d}{i_1, \dots, i_n} X_1^{2i_1} \cdots X_n^{2i_n} + \sum_{i=1}^n (a_0 - \lambda) X_i^{2d}$, where $a_0$ is the constant terms of $f$, i.e $a_0 = f(\mathbf{0}) \ge 1$. All these degree $2d$ terms are of positive coefficients and of even powers for each variable $X_1, \dots, X_n$, so $f$ must be coercive. $\square$

# 5 Algorithms

In this section we introduce algorithms to certify that a polynomial is nonnegative, or to prove that it is not. Our algorithms reduce the problem of certification to the setting of Thm. 2.4, that is, certify that a polynomial whose gradient ideal is zero-dimensional and whose minimum is attained, is nonnegative. Using this reduction, we perform our certification via algorithm SOS-RUR.

In most of the cases, the stereographic transformation leads to polynomials satisfying (II), i.e, zero dimensional gradient ideal and minimum attained (by coerciveness, see Lem. 2.15). If this is the case, then we can certify the nonnegativity of $f$ by applying SOS-RUR to $\mathcal{S}(f)$. However, as the next example demonstrates, this is not always the case.

**Example 5.1.** Let $f(\mathbf{X}) = \|\mathbf{X}\|_2^2 + 4 = X_1^2 + \cdots + X_n^2 + 4$. Then, $\mathcal{S}(f)(\mathbf{X}) = 4\|\mathbf{X}\|_2^2 + 4(-1 + \|\mathbf{X}\|_2^2)^2$. In this case, the gradient variety is

$$ \mathbb{V}(I_{\nabla \mathcal{S}(f)}) = \mathbb{V}(X_1(-1 + 2\|\mathbf{X}\|_2^2), \dots, X_n(-1 + 2\|\mathbf{X}\|_2^2)) \supseteq \mathbb{V}(-1 + 2\|\mathbf{X}\|_2^2). $$

Hence, the gradient ideal of $\mathcal{S}(f)$, $I_{\nabla \mathcal{S}(f)}$, has dimension $n-1$.

To overcome the obstacle that the gradient ideal of the stereographic transformation of $f$ might not be zero dimensional, we combine the stereographic transformation with the Hanzon-Jibetean perturbations. We introduce two algorithms; one based on the positive HJ perturbation and one based on the negative HJ perturbation, see Def. 4.1.

The first one, based on the positive perturbation, certifies the nonnegativity of a polynomial $f$, by applying the SOS-RUR algorithm on the polynomial $\mathcal{P}_\lambda(\mathcal{S}(f))$, where $\lambda$ is sufficiently small and depends on the size of $f$. We call it HJ-SOS-POS. It makes no assumption on $f$, other than $f(\mathbf{0}) > 0$.

The second algorithm, based on the negative perturbation, we call it HJ-SOS-NEG. It certifies the nonnegativity of a polynomial $f$ by applying SOS-RUR on the polynomial $\mathcal{N}_\lambda(\mathcal{S}(f))$. Its main difference, and advantage, compared to HJ-SOS-POS is that $\lambda$ depends on actual minimum of $\mathcal{S}(f)$; in practice this is significantly smaller than the $\lambda$ used in HJ-SOS-POS. Even more, we do not need to know the bound a priori. However, the algorithm only succeeds to certify the nonnegativity of polynomials $f$ when $f$ and its higher degree homogeneous part are positive. Nevertheless, we do not need to know if these assumptions are satisfied before running the algorithm. If they are not satisfied, then the algorithm reports that it cannot handle the input.
Finally, by combining HJ-SOS-POS and HJ-SOS-NEG we can get the best of the two. We introduce the algorithm HJ-SOS-RUR, that proceeds as follows: First, it checks whether it can decide nonnegativity using only the stereographic transformation. If this is not the case, then it applies HJ-SOS-NEG. If the latter fails, then it applies HJ-SOS-POS, which relies on worst case bounds and never fails. In this way, either it certifies the nonnegativity of the input polynomial or computes one point at which the polynomial has a negative value.

**Algorithm HJ-SOS-POS.** The first algorithm relies on the positive HJ perturbation.

**Algorithm 2 HJ-SOS-POS**

**Input:** A nonzero polynomial $f \in \mathbb{Z}[X]$, in $n$ variables, of even degree $d$, such that $H(f) \le 2^\tau$.

**Assumption:** $f(0) > 0$.

**Output:** A tuple [NonNeg, Cert].

NonNeg : a boolean; True if $f$ is nonnegative, False otherwise.

Cert : a list containing one of the following (depending on the value of NonNeg):

- If $f$ is nonnegative (NonNeg = True), then $Cert = [\lambda, C]$,
where $\lambda \in \mathbb{Q}$ and $\lambda < \epsilon(n, d, \tau)$ (see Thm. 4.6), $\mathcal{P}_{\lambda}(S(f))$ satisfies (II), and
$C$ is a valid certificate of nonnegativity for $\mathcal{P}_{\lambda}(S(f))$.

- If $f$ is not nonnegative (NonNeg = False), then $Cert = [x]$,
where $x \in \mathbb{Q}^n$ is such that $f(x) < 0$.

**Steps:**

1. Let $\epsilon(n, d, \tau)$ be the constant of Eq. (9), that is, (see Thm. 4.6)

$$ \epsilon(n, d, \tau) := \frac{1}{6n} \frac{\mathbf{B}(n, 2d, d \lg(n+1) + n + 2d + \tau)}{\mathbf{R}(n, d, \tau)^{2d+2}} $$

2. Choose any $\lambda \in (0, \epsilon(n, d, \tau)]$ (the simplest rational in the interval) (See Rmk. 5.4)

3. Compute $\mathcal{P}_{\lambda}(S(f)) = S(f) + \lambda \sum_{i=1}^{n} (1 + X_i^2 + X_i^{2d+2})$ (Def. 4.1)

4. [NonNeg, C] $\leftarrow$ SOS-RUR($\mathcal{P}_{\lambda}(S(f))$)

5. If NonNeg = True then
   RETURN [True, [λ, C]] // f is nonnegative, return the certificate

6. If NonNeg = False then
   RETURN [False, [Q(f, p)]] // in this case C = [p]
   // return the witness point (See Lem. 3.7)

**Theorem 5.2.** *Algorithm HJ-SOS-POS (Alg. 4) is correct. In particular,*

* If $f$ is nonnegative, then it outputs $\lambda \in \mathbb{Q}$, such that $\mathcal{P}_{\lambda}(S(f))$ satisfies (II) and a valid certificate of nonnegativity for $\mathcal{P}_{\lambda}(S(f))$. The existence of this certificate guarantees that $f$ is nonnegative.

* If $f$ is not nonnegative, then it outputs a (witness) point $x \in \mathbb{Q}^n$, such that $f(x) < 0$.

*Proof.* At line (2), we choose a $\lambda \in (0, \epsilon(n, d, \tau)]$. By Thm. 4.6, for any such $\lambda$, $f$ is nonnegative if and only if $\mathcal{P}_{\lambda}(S(f))$ is nonnegative. Moreover, $\mathcal{P}_{\lambda}(S(f))$ satisfies (II). Therefore, the output of SOS-RUR with input $\mathcal{P}_{\lambda}(S(f))$ is, either a valid certificate of nonnegativity for $\mathcal{P}_{\lambda}(S(f))$, or a point $p \in \mathbb{Q}^n$, such that $\mathcal{P}_{\lambda}(S(f))(p) < 0$ [BTZ25]. In the second case, we have that $0 > \mathcal{P}_{\lambda}(S(f))(p) > S(f)(p)$, so by Lem. 3.7, we have that $f(\mathbb{Q}(f, p)) < 0$ and $\mathbb{Q}(f, p) \in \mathbb{Q}^n$. $\square$

**Remark 5.3** (Verification of the certificate). Consider $f \in \mathbb{Q}[x]$ of degree $d$ such that $H(f) \le 2^\tau$ and $f(0) > 0$. If HJ-SOS-POS asserts that $f$ is nonnegative, then it outputs [True, [λ, Cert]]. We verify the
consistency of the output in two steps. First, we check whether $\lambda < \epsilon(n, d, \tau)$. If this is the case, then $\mathbb{P}_{\lambda}(S(f))$ satisfies (II) (Def. 2.3 and Thm. 4.6). The second step is to verify that Cert is indeed a valid certificate of nonnegativity for $\mathbb{P}_{\lambda}(S(f))$; for this we use the algorithm supported by Thm. 2.10.

**Remark 5.4** (About the bitsize of $\lambda$). As $\lambda \in (0, \epsilon(n, d, \tau)]$, we can assume that the worst case bitsize of $\lambda$ is $\mathfrak{h}(\lambda) = \mathfrak{h}(\epsilon(n, d, \tau)) = \mathcal{O}(n^2 d^n (n^2 d + \tau))$; see Eq. (9). In practice, we might choose the simplest rational in this interval by considering the continued fraction expansion of $\epsilon(n, d, \tau)$.

**Algorithm HJ-SOS-NEG.** The second algorithm relies on the negative HJ perturbation (Def. 4.1). It does not work with rationals having the worst case bitsize right from the beginning, as HJ-SOS-POS does, and hence it is more efficient in practice. On the negative side, it requires that both $f$ and $f^{(d)}$, that is the highest degree homogeneous part of $f$, are positive, so the algorithm can fail.

**Algorithm 3 HJ-SOS-NEG**

**Input:** A nonzero polynomial $f \in \mathbb{Z}[X]$, in $n$ variables, of even degree $d$, such that $H(f) \le 2^\tau$.
**Assumption:** $f(0) > 0$.

**Output:** One of the following:

[λ, Cert] : if $f$ and its highest degree homogeneous part $f^{(d)}$ are positive. We have that $\lambda \in \mathbb{Q}$, $N_{\lambda}(S(f))$ satisfies (II) and Cert is a valid certificate of nonnegativity of $N_{\lambda}(S(f))$.

Fail : if $f$ or $f^{(d)}$ are not positive.

**Steps:**

1. Let $\gamma \leftarrow \frac{1}{2}$ and compute the constant $\varepsilon := \epsilon(n, d, \tau)$, as in Eq. (9) (see Thm. 4.6)

2. While $2^{-\gamma} > \varepsilon$
   (a) $\gamma \leftarrow 2\gamma$
   (b) Choose $\lambda \in (2^{-2}\gamma, 2^{-\gamma}]$. (See Rmk. 5.6)

(c) If the gradient ideal of $N_{\lambda}(S(f))$ is not zero-dimensional or has solutions “at infinity”,
   Go to (b).

(d) Compute $N_{\lambda}(S(f)) = S(f) - \lambda \sum_{i=1}^{n} (1 + X_i^2 + X_i^{2d})$ (Def. 4.1)

(e) [NonNeg, Cert] $\leftarrow$ SOS-RUR($N_{\lambda}(S(f))$)

(f) If NonNeg = True then
   RETURN [λ, Cert]

3. RETURN Fail

**Theorem 5.5.** *Algorithm HJ-SOS-NEG (Alg. 3) is correct. In particular,*

* If $f$ and its highest degree homogeneous part are positive, then it returns $\lambda \in \mathbb{Q}$ and Cert such that $N_{\lambda}(S(f))$ satisfies condition (II) and Cert is a valid certificate of nonnegativity for $N_{\lambda}(S(f))$. Moreover, the existence of this certificate implies that $f$ is positive.

* If the algorithm fails, then either $f$ or its highest degree homogeneous part $f^{(d)}$ are not positive.

*Proof.* Starting from $\gamma = 1$, HJ-SOS-NEG repeatedly doubles $\gamma$ until, either $2^{-\gamma} < \epsilon(n, d, \tau)$ or we can decide the nonnegativity (or not) of $N_{\lambda}(S(f))$ using SOS-RUR. The bound on $\gamma$ guarantees termination; provided that we loop a finite number of times between steps (b) and (c).

As $\lambda < 1 \le f(0)$, Lem. 4.11 implies that $N_{\lambda}(S(f))$ is coercive and so it attains its infimum. Moreover, if $\lambda$ is generic, then the gradient ideal of $N_{\lambda}(S(f))$ is zero dimensional (and has not solutions at infinity), by Prop. 4.3; hence it satisfies condition (II). Lem. 4.4 implies that there are at most $(2d-1)^{n-1}(2d-1+n)$ values for $\lambda \in \mathbb{Q}$, such that $N_{\lambda}(S(f))$ does not satisfy condition (II) (or has solutions at infinity). So, for
every $\gamma$, we loop a finite number of times between steps (b) and (c). This establishes the termination of
the algorithm.

Moreover, if we choose any $\lambda < \epsilon(n, d, \tau)$, by Thm. 4.10, then $\mathcal{N}_\lambda(S(f))$ is nonnegative if and only if both $f$ and $f^{(d)}$ are positive. Thus, if both $f$ and $f^{(d)}$ are positive, any $\lambda$ computed from the loop of steps (b) and (c) enforces $\mathcal{N}_\lambda(S(f))$ to satisfy condition (II), and thus, we can certify the nonnegativity of $\mathcal{N}_\lambda(S(f))$ using SOS-RUR.

On the other hand, if $f$ or $f^{(d)}$ are not positive, we cannot certify the positivity of $f$ from the nonnegativity of $\mathcal{N}_\lambda(S(f))$. The algorithm exhausts all the values of $\gamma$ and outputs fail. $\square$

**Remark 5.6 (Lucky choices and bitsize of $\lambda$).** Notice that, if we choose a generic $\lambda$ at the step (b) of the algorithm, then, by Prop. 4.3, $\mathcal{N}_\lambda(S(f))$ will satisfy (II) and its gradient ideal will have no solutions “at infinity”. Hence, there are only finite unlucky $\lambda$'s that do not satisfy the previous properties and so, they do not go through step (c). These $\lambda$'s are characterised by Lem. 4.4. If we combine this lemma with Schwartz-Zippel lemma, e.g. [Lip09], then we can lower bound the probability of finding a lucky $\lambda$. Fix $k \in \mathbb{N}$ and consider a set $S \subset \mathbb{Q}$ with $k \cdot (2d-1)^{n-1}(2d-1+n)$ different elements. The probability that a uniformly random chosen $\lambda \in S$ is unlucky is upper-bounded by $\frac{1}{k}$. Moreover, given $\gamma \in \mathbb{N}$, we can choose a set $S \subset (2^{-2\gamma}, 2^{-\gamma}]$ such that its elements have bitsize at most $\gamma + 2 + \lg(k \cdot (2d-1)^{n-1}(2d-1+n)) = \tilde{\mathcal{O}}(\gamma + n \lg d + \lg k)$. For this reason, we say that $\lambda \in (2^{-2\gamma}, 2^{-\gamma}]$ has small bitsize when its bitsize is $\tilde{\mathcal{O}}(\gamma + n \lg d + \lg k)$.

**Remark 5.7 (Verification of the certificate).** To verify that the algorithm does not fail when $f$ is positive, we first need to check that $0 < \lambda < f(\mathbf{0})$. In this case, $\mathcal{N}_\lambda(S(f))$ coercive, and so its minimum is attained. Therefore, we can verify if Cert is a valid certificate of nonnegativity for $\mathcal{N}_\lambda(S(f))$ using Thm. 2.10.

**Algorithm HJ-SOS-RUR.** We combine the algorithms HJ-SOS-POS and HJ-SOS-NEG to introduce an algorithm that have the advantages of both. We call the algorithm HJ-SOS-RUR to emphasize that is based on (both) HJ perturbations (Def. 4.1) and SOS-RUR [BTZ25].

**Theorem 5.8.** *Algorithm HJ-SOS-RUR (Alg. 4) is correct, that is,*

* If $f$ is not nonnegative, then it outputs an $\boldsymbol{x} \in \mathbb{Q}^n$, such that $f(\boldsymbol{x}) < 0$.

* Otherwise, the algorithm returns polynomials whose nonnegativity imply the nonnegativity of $f$ together with valid certificates of nonnegativity for them (see the output of HJ-SOS-RUR in Alg. 4).

*Proof.* Assume first that $I_{\nabla S(f)}$ is zero-dimensional. As $S(f)$ is coercive, it attains its minimum. Hence, $f$ satisfies condition (II). In this case, we can certify if $S(f)$ nonnegative using SOS-RUR. If this is the case, then, by Thm. 3.3, a valid certificate of nonnegativity for $S(f)$ implies that $f$ is nonnegative. If $f$ is not nonnegative, then we will obtain a point $\boldsymbol{x} \in \mathbb{Q}$ such that $S(f)(\boldsymbol{x}) < 0$ and so, by Lem. 3.7, $\mathbb{Q}(f, \boldsymbol{p}) \in \mathbb{Q}^n$ and $f(\mathbb{Q}(f, \boldsymbol{p})) < 0$.

If we are not sure if $I_{\nabla S(f)}$ is zero-dimensional, then we try to certify that $f$ is positive using SOS-CS-NEG. By Thm. 5.5, if the algorithm does not fail, $\mathcal{N}_\lambda(S(f))$ satisfies (II), and $\mathcal{C}$ is a valid certificate of nonnegativity for $\mathcal{N}_\lambda(S(f))$. By Lem. 4.7, this certificate implies that $f$ is positive.

Finally, if we could not certify the nonnegativity of $f$ using the previous approaches, we use SOS-CS-POS, which by Thm. 5.2, leads either to a certificate of nonnegativity for $f$ or to a rational point where the function vanishes. $\square$

**Remark 5.9 (Verification).** *Remarks 5.3 and 5.7 detail how to verify the certificates induced by HJ-SOS-POS and HJ-SOS-NEG, respectively. Hence, to verify the certificate induced by HJ-SOS-RUR, it suffices to verify the certificate we obtain when PertType = NoPert. In this case, we certify the nonnegativity of $S(f)$. As $S(f)$ is coercive, it attains its infimum, so the validity of the certificate follows from Thm. 2.10.*

**On the assumption $f(\mathbf{0}) > 0$.** The algorithms that we present assume that the input polynomial $f$ has a positive constant coefficient. If this coefficient is zero, then $S(f)$ may not be a coercive function, and so our perturbation schemes, Thm. 4.5, do not hold. To ensure this property, we need to translate $f$. For this, we find a $\boldsymbol{c} = (c_1, \dots, c_n) \in \mathbb{R}^n$, such that $f(\boldsymbol{c}) \neq 0$. Then, we apply HJ-SOS-RUR on $f(X_1 + c_1, \dots, X_n + c_n)$, if $f(\boldsymbol{c}) > 0$; otherwise we return the point $\boldsymbol{c}$. We can find a suitable $\boldsymbol{c}$ using a randomized procedure that has probability of success arbitrarily close to 1, by applying straightforwardly Schwartz-Zippel lemma, see [Lip09] and references therein.
**Algorithm 4 HJ-SOS-RUR**

**Input:** A nonzero polynomial $f \in \mathbb{Z}[\mathbf{X}]$, in $n$ variables of even degree $d$, such that $H(f) \le 2^\tau$.
**Assumption:** $f(\mathbf{0}) > 0$.

**Output:** A tuple [NonNeg, PertType, Cert].

NonNeg: a Boolean; True if $f$ is nonnegative, False otherwise.

PertType: an element of {$\text{NoPert}, \text{NegPert}, \text{PosPert}$} indicating whether we applied no, a negative, or a positive HJ perturbation to $f$; see Def. 4.1.

Cert: a list, the contents of which depend on the other two outputs. In particular:

- If $\text{NonNeg} = \text{False}$, then $\text{Cert} = [\mathbf{x}]$, where $\mathbf{x} \in \mathbb{Q}^n$ is such that $f(\mathbf{x}) < 0$.

- If $\text{NonNeg} = \text{True}$, then

* If $\text{PertType} = \text{NoPert}$, then $S(f)$ satisfies condition (II) (Def. 2.3) and $\text{Cert}$ is a valid certificate of nonnegativity for $S(f)$.

* If $\text{PertType} = \text{NegPert}$, then $\text{Cert} = [\lambda, C]$, where $\lambda \in \mathbb{Q}$ and $\lambda < f(\mathbf{0})$, $\mathcal{N}_\lambda(S(f))$ satisfies (II), and $C$ is a valid certificate of nonnegativity for $\mathcal{N}_\lambda(S(f))$. In this case, $f$ is positive.

* If $\text{PertType} = \text{PosPert}$, then $\text{Cert} = [\lambda, C]$, where $\lambda \in \mathbb{Q}$ and $\lambda < \epsilon(n, d, \tau)$ (see Thm. 4.6), $\mathcal{P}_\lambda(S(f))$ satisfies (II), and $C$ is a valid certificate of nonnegativity for $\mathcal{P}_\lambda(S(f))$.

**Steps:**

1. If $I_{\nabla S(f)}$ is zero-dimensional and has no solutions “at infinity”, then

(a) [NonNeg, Cert] $\leftarrow$ SOS-RUR($S(f)$)

(b) If $\text{NonNeg} = \text{True}$, RETURN $[\text{True, NoPert, Cert}]$

(c) Else, $\text{Cert} = [\mathbf{p}]$ RETURN $[\text{False, -, }[\mathbb{Q}(f, \mathbf{p})]]$ (See Lem. 3.7)

2. Else, try $[\lambda, \text{Cert}] \leftarrow$ HJ-SOS-NEG($f$)

(a) If does not Fail, RETURN $[\text{True, NegPert, }[\lambda, \text{Cert}]]$

(b) Else, [NonNeg, Cert] $\leftarrow$ HJ-SOS-POS($f$)

i. If $\text{NonNeg} = \text{True}$, RETURN $[\text{True, PosPert, Cert}]$

ii. Else, RETURN $[\text{False, -, Cert}]$

**Lemma 5.10.** Let $f$ be a polynomial of degree $d$ and fix a constant $k \in \mathbb{N}$. Let $S$ be the grid of points in $\mathbb{Z}^n$ whose coordinates belong to the set $\{1, \dots, k \cdot d\}$. If we choose $c \in S$ uniformly at random, then the probability that $f(c) = 0$ is at most $\frac{1}{k}$.

When we translate $f$, we also increase its bitsize; this (slightly) affects the complexity of HJ-SOS-RUR. We address this issue in Lem. 6.5.

# 6 Complexity analysis

We study the complexity of Alg. HJ-SOS-RUR and its subroutines. Our main ingredient is the bit complexity of the SOS-RUR (Alg. 1). Because this is a Monte Carlo algorithm, our algorithms will be of the same kind, and their the probability of success will be the same as SOS-RUR; see Thm. 2.8.

We start this section by studying the effect of the Hanzon-Jibetean perturbations on the (bit)size of the polynomials.
**Lemma 6.1.** Let $f \in \mathbb{Z}[X]$ be a polynomial in $n$ variables of degree $d$ such that $H(f) \le 2^\tau$. Let $\lambda \in \mathbb{Q}$, such that $\mathcal{h}(\lambda) = \mathcal{h}(\epsilon(n, d, \tau))$ (see Eq. (9) and Thm. 4.10), then

$$ \mathcal{h}(\mathcal{P}_{\lambda}(S(f))), \mathcal{h}(\mathcal{N}_{\lambda}(S(f))), \mathcal{h}(\lambda) = \tilde{\mathcal{G}}(n 2^n d^n (n^2 d + \tau)). $$

*Proof.* The polynomials $\mathcal{P}_{\lambda}(S(f))$ and $\mathcal{N}_{\lambda}(S(f))$ have similar bitsize, so it suffices to consider one of them. By Lem. 3.8, $\mathcal{h}(S(f)) = \mathcal{O}(d \lg(n+1) + n + 2d + \tau) = \tilde{\mathcal{G}}(n+d+\tau)$. Hence, the bitsize of the $\lambda$ dominates the bound. As $\mathcal{h}(\lambda) = \mathcal{h}(\epsilon(n, d, \tau)) = \tilde{\mathcal{G}}(n 2^n d^n (n^2 d + \tau))$, the bound follows. $\square$

Next, we study the complexity of Algorithm HJ-SOS-POS.

**Theorem 6.2 (Complexity of HJ-SOS-POS).** Consider $f \in \mathbb{Z}[X]$ of size $(d, \tau)$ and even degree. Algorithm HJ-SOS-POS (Alg. 2) computes

* If $f$ is nonnegative, a constant $\lambda \in \mathbb{Q}$ of bitsize $\tilde{\mathcal{G}}(2^n d^n (d + \tau))$ and a valid certificate of nonnegativity of $\mathcal{P}_{\lambda}(S(f))$ of the total bit-size $\tilde{\mathcal{G}}(2^{4n}(d+1)^{4n+2} (d+\tau)))$.

* If $f$ is not nonnegative, a rational point $\mathbf{p} \in \mathbb{Q}^n$ such that $f(\mathbf{p}) < 0$. The bitsize of the witness point is $\tilde{\mathcal{G}}(2^{3n}(d+1)^{3n+3}(d+\tau))$.

*The bit complexity of HJ-SOS-RUR is $\tilde{\mathcal{G}}_B(e^{2(\omega+1)n} (d+1)^{(\omega+2)n} \tau)$, where $\omega$ is the exponent of matrix multiplication.*

*Proof.* The complexity bound follows from Thm. 2.8, taking into account that, by Thm. 4.2, the gradient ideal of $\mathcal{P}_{\lambda}(S(f))$ has no solutions “at infinity”. Observe that, by Lem. 6.1, we have that the bitsize of $\mathcal{P}_{\lambda}(S(f))$ and $\lambda$ is $\tilde{\mathcal{G}}(2^n d^n (d + \tau))$. Moreover, by Lem. 3.7, for any $\mathbf{x} \in \mathbb{Q}^n$, the bitsize of $\mathcal{Q}(f, \mathbf{x})$ is $\mathcal{O}(n d (\lg H(\mathbf{x})) + \mathcal{h}(f))$. $\square$

In what follows, we study the expect and worst-case complexity of HJ-SOS-NEG.

**Theorem 6.3 (Complexity of HJ-SOS-NEG).** Consider $f \in \mathbb{Z}[X]$ of size $(d, \tau)$ and even degree. Let $f^{(d)}$ be the highest degree homogeneous part of $f$. Algorithm HJ-SOS-NEG (Alg. 3) is randomized<fnref n="1" /> and its expected bit complexity is as follows.

* If $f$ and $f^{(d)}$ are positive, the algorithm computes $\lambda \in \mathbb{Q}$ of bitsize $\tilde{\mathcal{G}}(d (d + n + \tau) + |\lg(\min S(f))|)$ and a valid certificate of nonnegativity for $\mathcal{N}_{\lambda}(S(f))$ of total bitsize $\tilde{\mathcal{G}}(2^{3n} d^{3n+2} (d^2 + d \tau + |\lg(\min S(f))|))$ in expected $\tilde{\mathcal{G}}_B(e^{(2\omega+1)n} d^{(\omega+1)n} (d + \tau + |\lg(\min S(f))|))$ bits operations.

* Otherwise, the algorithm fails in expected $\tilde{\mathcal{G}}_B(e^{2(\omega+1)n} d^{(\omega+2)n} \tau)$ bit operations.

*The worst-case complexity of the algorithm is $\tilde{\mathcal{G}}_B(e^{(2\omega+3)n} d^{(\omega+3)n} \tau)$.*

*Proof.* We want to estimate the expected complexity of our algorithm. To do so, we define $\gamma^{\max}$ as the biggest $\gamma$ that our algorithm considers. As we do exponential search, it follows from Thm. 4.10 that, if $f$ and $f^{(d)}$ are positive, we can assume $\gamma^{\max} = \mathcal{O}(\lg(\mathcal{R}(n, d, \tau)^{2d}) + |\lg(\min S(f))|)$ or, if this is not the case, $\gamma^{\max} = \mathcal{O}(|\lg(\epsilon(n, d, \tau))|)$. Observe that we will go through the loop of step 2 $\mathcal{O}(\lg(\gamma^{\max}))$ times.

Recall that the complexity of checking if the gradient ideal of $S(f)$ is zero-dimensional and has no solutions “at infinity” (step (c)) is upper-bounded by the complexity of computing SOS-RUR($\mathcal{N}_{\lambda}(S(f))$) (step (e)); see Rmk. 2.9. Moreover, this complexity increases with the bitsize of $\lambda$, which is at most $\tilde{\mathcal{G}}_B(\gamma^{\max} + n \lg d + \lg k)$; where $k$ is as defined in Rmk. 5.6. Hence, by Thm. 2.8, the complexity of computing SOS-RUR($\mathcal{N}_{\lambda}(S(f))$) each time is at most

$$ \tilde{\mathcal{G}}_B(e^{(2\omega+1)n} d^{(\omega+1)n-1} (d + \gamma^{\max} + \tau + \lg k)). \quad (10) $$

Finally, observe that the probability of choosing an *unlucky* $\lambda$, such that we loop in step (c), is upper-bounded by $\frac{1}{k}$. So for each value of $\gamma$, we expect to iterate at most $\frac{k}{k-1}$ times in this step. Therefore, the expected total complexity of the algorithm is as in Eq. 10. If either $f$ or $f^{(d)}$ are not positive,

<footnote n="1">¹If SOS-RUR was deterministic or Las Vegas, then HJ-SOS-NEG would be Las Vegas.</footnote>
then the algorithm fails after performing (expected) $\tilde{\mathcal{O}}_B(e^{2(\omega+1)n} d^{(\omega+2)n} (\tau + \lg k))$ bit operations. If both $f$ and $f^{(d)}$ are positive, then the algorithm certifies the nonnegativity of $\mathcal{N}_\lambda(S(f))$ in an expected complexity of the algorithm is $\tilde{\mathcal{O}}_B(e^{(2\omega+1)n}d^{(\omega+1)n} (d+\tau+|\lg(\min S(f))|+\lg k))$. In this case, $\lambda$ has bitsize $\tilde{\mathcal{O}}_B(d (d+n+\tau) + |\lg(\min S(f))| + \lg k)$ and the bitsize of the certificate of nonnegativity for $\mathcal{N}_\lambda(S(f))$ is $\tilde{\mathcal{O}}_B(2^{3n}d^{3n+2}(d^2+d\tau+|\lg(\min S(f))|+\lg k))$.

In the worse case, that is, where our algorithm chooses every possible unlucky $\lambda$, the complexity of our algorithm is $\tilde{\mathcal{O}}_B(e^{(2\omega+3)n} d^{(\omega+3)n} (\tau + \lg k))$, by Rmk. 5.6. $\square$

**Theorem 6.4.** Consider $f \in \mathbb{Z}[\mathbf{X}]$ of size $(d, \tau)$ and even degree. Algorithm HJ-SOS-RUR (Alg. 4) is randomized$^2$ and its expected complexity is $\tilde{\mathcal{O}}_B(e^{2(\omega+1)n} (d+1)^{(\omega+2)n} \tau)$ bit operations. In the worst-case, the bit complexity is $\tilde{\mathcal{O}}_B(e^{(2\omega+3)n} d^{(\omega+3)n} \tau))$.

The size of the output is as follows.

* If $f$ is nonnegative, the algorithm outputs a rational polynomial of bitsize $\tilde{\mathcal{O}}_B(2^n d^n (d+\tau))$ and a valid certificate of nonnegativity for it of total bit-size $\tilde{\mathcal{O}}_B(2^{4n}(d+1)^{4n+2} (d+\tau)))$ (see output of HJ-SOS-RUR in Alg. 4).

* If $f$ is not nonnegative, a rational point $\mathbf{p} \in \mathbb{Q}^n$ such that $f(\mathbf{p}) < 0$. The bitsize of the witness point is $\tilde{\mathcal{O}}_B(2^{3n}(d+1)^{3n+3}(d+\tau))$.

*Proof.* In the average case, the complexity of the algorithm is dominated by the complexity of HJ-SOS-POS (Thm. 6.2). In the worst case, the complexity is dominated by the worst-case complexity of HJ-SOS-NEG (Thm. 6.3). $\square$

**On the assumptions** $f(0) > 0$. Given $k \in \mathbb{N}$ and a point $(c_1, \dots, c_n) \in \{1, \dots, k \cdot d\}^n$, our next lemma offers an upper bound for the bitsize of the polynomial $f(X_1 + c_1, \dots, X_n + c_n)$.

**Lemma 6.5.** Let $f$ be a polynomial of degree $d$ and fix a constant $k \in \mathbb{N}$. Let $S$ be the grid of points in $\mathbb{Z}^n$ whose coordinates belong to the set $\{1, \dots, k \cdot d\}$. If $\mathcal{H}(f) \le \tau$, then $\mathcal{H}(f(X_1 + c_1, \dots, X_n + c_n)) = \mathcal{O}(\tau + n d (\lg(k) + \lg(d)))$.

*Proof.* First, observe that $\mathcal{H}(c_i) = \mathcal{O}(\lg k + \lg d)$. Second, note that if $f$ is an univariate polynomial, then $\mathcal{H}(f(X_1 + c_1)) \le \tau + \lg(d+1) + \lg d + d \lg c_1$. Hence, $\mathcal{H}(f(X_1 + c_1, X_2, \dots, X_n)) = \mathcal{O}(\tau + d \lg(k) + d \lg(d))$. Applying the previous equality for each variable $X_i$, we conclude that $\mathcal{O}(\tau + n d (\lg(k) + \lg(d)))$. $\square$

# 7 SOS perturbations

Sums of squares polynomials form an important subclass of nonnegative polynomials that nowadays plays a key role in optimization of real polynomials over semi-algebraic sets, see [Par00] and [Las01]. They form a closed convex full-dimensional subcone of the cone of all nonnegative polynomials of a given degree. While not every nonnegative polynomial is a sum of squares, Artin's solution [Art27] of the Hilbert's 17th problem shows that every nonnegative polynomial becomes a sum of squares after multiplication by the square of some real polynomial. Checking whether a given polynomial is a sum of squares boils down to verifying whether a certain affine-linear subspace associated to the polynomial non-trivially intersects the cone of positive semi-definite matrices. Because of their importance both for theory and applications, there has been a lot of interest in different aspects of sums of squares polynomials and their relation to general nonnegative polynomials, see [Ble06], [Rez95], [Las01] and references therein. Lasserre [Las06] proved that for a nonnegative polynomial $f \in \mathbb{R}[\mathbf{X}]$ and any $\varepsilon > 0$, for all sufficiently large $t \in \mathbb{N}$ the perturbed polynomial $f + \varepsilon\theta_t$ is a sum of squares, where $\theta_t = \sum_{k=0}^t \sum_{i=1}^n \frac{X_k^{2t}}{k!}$. Here we study a similar but different perturbation,

$$f_{t,\varepsilon} := f + \varepsilon(1 + \|\mathbf{X}\|_2^2)^t, \quad \|\mathbf{X}\|_2^2 = \sum_{i=1}^n X_i^2. \qquad (11)$$

As we remark in Subsection 7.1, it follows from Lasserre's result [Las06] that $f_{t,\varepsilon}$ is a sum of squares for all sufficiently large $t \in \mathbb{N}$. We now prove this fact in a completely different way giving at the same time bounds on $t$.

<footnote>$^2$As HJ-SOS-NEG, if SOS-RUR was deterministic or Las Vegas, then HJ-SOS-RUR would be Las Vegas.</footnote>
**Theorem 7.1.** Let $f = \sum_{|\alpha| \le d} f_\alpha \mathbf{X}^\alpha \in \mathbb{R}[\mathbf{X}]$ be a nonnegative polynomial of degree $2d$ and let $\varepsilon > 0$. Then, for any $t \in \mathbb{N}$, such that

$$t \ge \max \left\{ d, \left[ \frac{1}{\varepsilon} \left( \|f\|_1 + \frac{\|\nabla f(\mathbf{0})\|_2^2}{f_0 + \varepsilon} \right) \right] \right\},$$

the degree $2t$ polynomial $f_{t,\varepsilon}(\mathbf{X}) = f(\mathbf{X}) + \varepsilon(1 + \|\mathbf{X}\|_2^2)^t$ is a sum of squares.

**Remark 7.2.** Theorem 7.1 holds for any $f \in \mathbb{R}[\mathbf{X}]$ with $f(\mathbf{0}) \ge 0$.

Before giving a proof let us recall some basics on Gram matrices of sums of squares polynomials. Let $[m_s]$ be the vector of all ordered (with respect to any fixed order) monomials in $n+1$ variables $X_0, X_1, \dots, X_n$ of degree $t$; it has $N_s = \binom{n+t}{t}$ elements. If $g$ is a real homogeneous polynomial $g$ of degree $2t$ in $n+1$ variables, we can write it as

$$g(X_0, \mathbf{X}) = [m_t]^\top G [m_t], \qquad (12)$$

where $G$ is a real symmetric matrix of size $N_t \times N_t$. Such matrices $G$ form an affine subspace defined by the equation (12). Then, it holds that, $g$ is a sum of squares (of real homogeneous polynomials) if and only if (12) holds for some positive semidefinite matrix $G$ [CLR95, Thm. 2.4], [Pow21, Thm. 3.1]; we call such a matrix a *Gram matrix* of $g$. By slightly abusing notation and terminology, we will refer to (12) as a Gram matrix representation of $g$, even when it is not a sum of squares (or even a nonnegative polynomial). Furthermore, $g$ belongs to the interior of the cone of sums of squares of degree $2t$ in $n+1$ variables if and only if there exists a positive definite Gram matrix satisfying (12).

*Proof of Thm. 7.1.* Let $f^h$ be the homogenization of $f$. Then the homogenization of $f_{t,\varepsilon}$ (with $t \ge d$) is given as

$$f_{t,\varepsilon}^{h}(X_0, \mathbf{X}) = X_0^{2(t-d)} f^{h}(X_0, \mathbf{X}) + \varepsilon (X_0^2 + \|\mathbf{X}\|_2^2)^t \in \mathbb{R}[X_0, \mathbf{X}]_{2t}. \qquad (13)$$

The property of being a sum of squares is preserved under (de)homogenization. Thus, it suffices to prove that $f_{t,\varepsilon}^h$ is SOS for a suitable $t$. We prove this by showing that the Gram matrix of $f_{t,\varepsilon}^h$, for a sufficiently large $t$, is positive semidefinite. We construct Gram matrices of the two summands of $f_{t,\varepsilon}^h$ separately. For this, we order the degree $t$ monomials by first putting $X_0^t, X_0^{t-1}X_1, \dots, X_0^{t-1}X_n$.

*The Gram matrix of* $(X_0^2 + \|\mathbf{X}\|_2^2)^t$

Consider first the second summand of $f_{t,\varepsilon}^h$, that is, $(X_0^2 + \|\mathbf{X}\|_2^2)^t = \sum_{|\alpha|=t} \binom{t}{\alpha} X_0^{2\alpha_0} X_1^{2\alpha_1} \dots X_n^{2\alpha_n}$. It has a diagonal Gram matrix $A_t$ with the first diagonal entry being 1. The matrix $A_t$ has the form

$$A_t = \mathrm{diag}\left\{\begin{pmatrix} t \\ \alpha \end{pmatrix}\right\}_{|\alpha|=t} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & A_{t,1} & 0 \\ 0 & 0 & A_{t,2} \end{bmatrix},$$

where $A_{t,1} = \mathrm{diag}\left\{\begin{pmatrix} t \\ \alpha \end{pmatrix} : t-d \le \alpha_0 < t\right\}$, and $A_{t,2} = \mathrm{diag}\left\{\begin{pmatrix} t \\ \alpha \end{pmatrix} : \alpha_0 < t-d\right\}$ for $\alpha = (\alpha_0, \alpha_1, \dots, \alpha_n)$. We now bound smallest eigenvalues of $A_{t,1}$ and $A_{t,2}$. First, if $s = t - \alpha_0 \in [d]$, for $t \ge 2d$, then

$$(A_{t,1})_{\alpha,\alpha} = \begin{pmatrix} t \\ \alpha \end{pmatrix} \ge \begin{pmatrix} t \\ s \end{pmatrix} \ge \begin{pmatrix} t \\ 1 \end{pmatrix} = t \Rightarrow \lambda_{\min}(A_{t,1}) \ge t. \qquad (14)$$

On the other hand, $A_{t,2}$ has some (diagonal) entries that correspond to the indices $te_i$ for $i \ge 1$, and, using the monotonicity of the multinomial coefficients, we have $\lambda_{\min}(A_{t,2}) = 1$.

*The Gram matrix of the first summand*

We consider a particular Gram matrix $F_d$ of $f^h(X_0, \mathbf{X}) = [m_d]^\top F_d [m_d]$ that is of the form

$$F_d = \begin{bmatrix} f_0 & \mathbf{v}^\top \\ \mathbf{v} & \tilde{F}_d \end{bmatrix},$$

where $f_0 = f(\mathbf{0}) = f^h(1, 0, \dots, 0)$,

$$\mathbf{v}^\top = \frac{1}{2} (f_{(2d-1)e_0+e_1}, \dots, f_{(2d-1)e_0+e_n}, 0, \dots, 0) = \frac{1}{2} (\partial_1 f(\mathbf{0}), \dots, \partial_n f(\mathbf{0}), 0, \dots, 0).$$
and such that elements of the submatrix $\tilde{F}_d$ depend linearly on the coefficients of $f^h$. The fact that we can obtain the degree 2d monomials $(X_0, \mathbf{X})^{de_0+\alpha}$, with $\alpha \neq (d-1)e_0 + e_i$ (with some $i=0, 1, \dots, n$), in more than one way (as a product of two degree d monomials) justifies that $F_d$ has the required form.

We set $F_t$ to be a $N_t \times N_t$ symmetric matrix whose entries are $(F_t)_{(t-d)e_0+\alpha, (t-d)e_0+\beta} = (F_d)_{\alpha,\beta}$, with $|\alpha| = |\beta| = d$. Then,

$$X_0^{2(t-d)} f^h(X_0, \mathbf{X}) = X_0^{2(t-d)}[m_d]^\top F_d [m_d] = [m_t]^\top F_t [m_t],$$

that is, $F_t$ is a Gram matrix representation of $X_0^{2(t-d)} f^h(X_0, \mathbf{X})$. Overall, the $N_t \times N_t$ symmetric matrix $F_t$ has a block-diagonal structure

$$F_t = \begin{pmatrix} f_0 & \mathbf{v}^\top & 0 \\ \mathbf{v} & \tilde{F}_d & 0 \\ 0 & 0 & 0 \end{pmatrix}, \qquad (15)$$

where the entries of the submatrix $F_d$ of size $N_d \times N_d$ are labeled by $(t-d)\mathbf{e}_0 + \alpha$ and $(t-d)\mathbf{e}_0 + \beta$.

### The Gram matrix of $f_\epsilon^h$ and its eigenvalues

Consider $G_t := F_t + \varepsilon A_t$. Then $f_{t,\varepsilon}^h = [m_t]^\top G_t [m_t]$, that is, $G_t$ is a Gram matrix for $f_{t,\varepsilon}^h$. We have

$$G_t = \begin{bmatrix} f_0 + \varepsilon & \mathbf{v}^\top & 0 \\ \mathbf{v} & \tilde{F}_d + \varepsilon A_{t,1} & 0 \\ 0 & 0 & \varepsilon A_{t,2} \end{bmatrix}.$$

For the lower (bottom right) block, it holds $\varepsilon A_{t,2} \geq \varepsilon I$. In particular, it is always positive definite and $\lambda_{\min}(\varepsilon A_{t,2}) = \varepsilon$. So, $G_t$ is positive semi-definite ($G \geq 0$) if and only if so is its submatrix

$$\begin{bmatrix} f_0 + \varepsilon & \mathbf{v}^\top \\ \mathbf{v} & \tilde{F}_d + \varepsilon A_{t,1} \end{bmatrix}.$$

As the constant term of a nonnegative polynomial is nonnegative, we have $f_0 + \varepsilon > 0$. Thus, $G_t \geq 0$ if and only if the following Schur complement is positive semi-definite [HJ13, Thm. 7.7.7]:

$$\tilde{F}_d + \varepsilon A_{t,1} - \frac{\mathbf{v}\mathbf{v}^\top}{f_0 + \varepsilon} \geq 0.$$

To ensure that the smallest eigenvalue of this matrix is nonnegative we use $\lambda_{\min}(M_1+M_2) \geq \lambda_{\min}(M_1)+\lambda_{\min}(M_2)$. Therefore, it is sufficient to prove that

$$t\varepsilon + \lambda_{\min}(\tilde{F}_d) + \lambda_{\min}\left(-\frac{\mathbf{v}\mathbf{v}^\top}{f_0 + \varepsilon}\right) \geq 0,$$

where we use $\lambda_{\min}(A_{t,1}) \geq t$ shown in (14). Now, using the inequality $\lambda_{\min}(M) \geq -\|M\|_2$ and $\|\mathbf{v}\|_2$, it is enough to ensure that

$$t\varepsilon - \|\tilde{F}_d\|_2 - \frac{\|\mathbf{v}\|_2^2}{f_0 + \varepsilon} \geq 0. \qquad (16)$$

Using the properties of the operator norm, we have that

$$\|\tilde{F}_d\|_2 \leq \|F_d\|_2 \leq \sqrt{\|F_d\|_\infty \|F_d\|_1} = \|F_d\|_1 \leq \|f^h\|_1 = \|f\|_1.$$

This, together with $\|\mathbf{v}\|_2 = \frac{1}{2}\|\nabla f(\mathbf{0})\|_2 \leq \|\nabla f(\mathbf{0})\|_2$, implies that the bound (16) holds if

$$t \geq \frac{1}{\varepsilon} \left( \|f\|_1 + \frac{\|\nabla f(\mathbf{0})\|_2^2}{f_0 + \varepsilon} \right).$$

□

**Remark 7.3.** Let $f \in \mathbb{Z}[\mathbf{X}]$ be any positive polynomial in $n$ variables, of degree $2d$, and $H(f) \leq 2^\tau$. Also, let $\varepsilon = 2^{-L}$, for a positive integer $L$. Then, Thm. 7.1 implies that for any $t$, such that

$$t \geq \binom{n+2d}{n} 2^{L+\tau+1},$$

the polynomial $f(\mathbf{X}) + \varepsilon(1 + \|\mathbf{X}\|_2^2)^t$ is a sum of squares.
## 7.1 Comparison with Lasserre's perturbations

The bound on $t$ of Theorem 7.1 seems to be quite non-optimal for a concrete polynomial. For example, the perturbation $M + \varepsilon(1 + X_1^2 + X_2^2)^t$ of the Motzkin polynomial $M = X_1^2 X_2^4 + X_1^4 X_2^2 + 1 - 3X_1^2 X_2^2$ is a sum of squares for all $t > \max\{3, 6/\varepsilon\}$ by Theorem 7.1. Using JuMP/MathOptInterface [DHL17; Leg+22] in Julia and MOSEK [MOS24] for solving an SDP, we find that the smallest eigenvalue of $\tilde{F}_d$ among all Gram matrices as in the proof of Theorem 7.1 is $\lambda_{\min}(\tilde{F}_d) \gtrsim -0.23$ which implies that $M + \varepsilon(1 + X_1^2 + X_2^2)^t$ is a sum of squares already for $t \ge \max\{3, 0.23/\varepsilon\}$. Allowing all (that is, not necessarily structured as above) Gram matrices reveals that $M + \varepsilon(1 + X_1^2 + X_2^2)^t$ is a sum of squares for $\varepsilon = 0.0002, t = 4$ and $\varepsilon = 0.0000027, t = 5$.

As we already mentioned above, Lasserre proved in [Las06] that for a nonnegative $f \in \mathbb{R}[\mathbf{X}]$ and any $\varepsilon > 0$, for all $t \in \mathbb{N}$ sufficiently large, the polynomial $f + \varepsilon\theta_t$ is a sum of squares, where $\theta_t = \sum_{k=0}^t \sum_{i=1}^n \frac{X_i^{2k}}{k!}$. Let us look at the expansion of the polynomial appearing in the perturbation (11),

$$h_t := (1 + X_1^2 + \cdots + X_n^2)^t = \sum_{|\alpha| \le t} \frac{t!}{(t - |\alpha|)! \alpha!} \mathbf{X}^{2\alpha},$$

which is a sum of squares of monomials. Looking only at the terms with $\alpha = ke_i$ for $k = 0, \dots, t$ and $i = 1, \dots, n$, we obtain

$$\sum_{k=0}^{t} \sum_{i=1}^{n} \frac{t!}{(t-k)!k!} X_i^{2k} = \theta_t + \sum_{k=0}^{t} \sum_{i=1}^{n} \left( \frac{t!}{(t-k)!} - 1 \right) \frac{X_i^{2k}}{k!},$$

that is, a sum of $\theta_t$ and a sum of squares of some monomials. The remaining terms in $h_t$ are also squared monomials. As a consequence, for all $t \in \mathbb{N}$ for which Lasserre's perturbation $f + \varepsilon\theta_t$ is a sum of squares we also have that $f + \varepsilon h_t$ is a sum of squares. However, it is not fair to compare these two perturbations as they have different sizes. For example, the 1-norm of coefficients of the perturbations are $\|\theta_t\|_1 = ns_t$, where $s_t := \sum_{k=0}^t \frac{1}{k!} \le e$ is bounded by a constant independent of $t$, and $\|h_t\|_1 = (n+1)^t$ which is exponential in $t$. We compare the normalized perturbations $f + \varepsilon \tilde{\theta}_t$ with $\tilde{\theta}_t := \frac{\theta_t}{ns_t}$ and $f + \varepsilon \tilde{h}_t$ with $\tilde{h}_t := \frac{h_t}{(n+1)^t}$. For each of the two models we computed the smallest $\varepsilon > 0$ for which a normalized perturbation of the Motzkin polynomial $f = M = X_1^2 X_2^4 + X_1^4 X_2^2 + 1 - 3X_1^2 X_2^2$ is a sum of squares, below we display the results rounded up to two significant digits.

$$\begin{array}{c|cccc}
 & t=3 & t=4 & t=5 & t=6 \\
\hline
M + \varepsilon \tilde{\theta}_t & 0.14 & 0.025 & 0.0023 & 0.00011 \\
\hline
M + \varepsilon \tilde{h}_t & 0.13 & 0.016 & 0.00063 & 0.000011
\end{array}
\qquad (17)$$

Lasserre showed [Las10] that, given a nonnegative polynomial $f \in \mathbb{R}[\mathbf{X}]$, a sum of squares polynomial of degree at most $2t \ge \deg f$ that is closest to $f$ with respect to the 1-norm of coefficients is obtained as $f + \lambda_0^* + \sum_{i=1}^n \lambda_i^* X_i^{2t}$ for some $\lambda_0^*, \lambda_1^*, \dots, \lambda_n^* \in \mathbb{R}$. The perturbation $f + \varepsilon\theta_t$ from [Las06] has a similar form to this one. In the following table we compare the 1-norm of errors of three SOS perturbations of a Motzkin-like polynomial $\tilde{M} = X_1^2 X_2^4 + X_1^4 X_2^2 + 1 - 3X_1^2 X_2^2$ considered in [Las10, Table 1].

$$\begin{array}{c|ccc}
 & t=3 & t=4 & t=5 \\
\hline
\tilde{M} + \lambda_0^* + \lambda_1^* x_1^{2t} + \lambda_2^* x_2^{2t} & 0.016 & 0.0021 & 0.000087 \\
\hline
\tilde{M} + \varepsilon \tilde{\theta}_t & 0.037 & 0.016 & 0.0053 \\
\hline
\tilde{M} + \varepsilon \tilde{h}_t & 0.054 & 0.023 & 0.0038
\end{array}
\qquad (18)$$

A universal perturbation valid for all (or almost all) nonnegative polynomials of a given degree might not exist. Even though the class of perturbations considered in [Las10] is rather simple and contains optimal ones (in 1-norm), for each given $f \in \mathbb{R}[\mathbf{X}]$ one needs to solve a semi-definite program. The above two tables show that the normalized perturbations $f + \varepsilon \tilde{h}_t$ and $f + \varepsilon \tilde{\theta}_t$ are in general incomparable. For the Motzkin polynomial $M$ at least for $t = 3, 4, 5$ and $6$, “moving” from $M$ in the direction of $\tilde{h}_t$ results in a sum of squares polynomial a bit faster than moving along $\tilde{\theta}_t$. On the other hand, the polynomial $\tilde{M}$ is closer in 1-norm to sums of squares of the form $\tilde{M} + \varepsilon\theta_t$ than to sums of squares of the form $\tilde{M} + \varepsilon h_t$ for
$t=3$ and $t=4$, but for $t=5$ the proximity relation reverses. We plan to carry out a careful comparison of these two natural perturbations in a future work.

## Acknowledgements

This research benefited from the support of the FMJH Program Gaspard Monge for optimization and operations research and their interactions with data science through the PGMO grant SOAP. MB is supported by the grant ANR JCJC PeACE (ANR-25-CE48-3760). KK is supported by the grant ANR "Chaire de Professeur Junior Mathématiques, Applications des Mathématiques, Géométrie Computationnelle GeoComp". ET is supported by the grant ANR PRC ZADyG (ANR-25-CE48-7058). CZ is supported by the Chinese Scholarship Council.

## References

[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.

[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).

[BDDT25] M. Bender, P. Di Dio, and E. Tsigaridas. "Positive Univariate Polynomials: SOS certificates, algorithms, bit complexity, and T-systems". preprint. Sept. 2025. URL: https://inria.hal.science/hal-05269445.

[BTZ25] M. Bender, E. Tsigaridas, and C. Zhu. "Certificates of nonnegativity of multivariate polynomials with zero-dimensional gradient ideal and infimum attained". Preprint. Nov. 2025. URL: https://inria.hal.science/hal-05382946.

[Ben+25] T. C. Benitez, C. D'Andrea, A. B. de Felipe, J. H. Moreno, and M. E. Montoro. *On the effective Pourchet's Theorem*. 2025. URL: https://arxiv.org/abs/2511.11783.

[Ber87] C. Berg. "The multidimensional moment problem and semigroups". In: *Proc. Symp. Appl. Math*. Vol. 37. 1987, pp. 110–124.

[Ble06] G. Blekherman. "There are significantly more nonegative polynomials than sums of squares". In: *Israel Journal of Mathematics* 153.1 (Dec. 2006), pp. 355–380. URL: http://link.springer.com/10.1007/BF02771790.

[BY09] W. D. Brownawell and C. K. Yap. "Lower bounds for zero-dimensional projections". In: *Proceedings of the 2009 International Symposium on Symbolic and Algebraic Computation*. ISSAC '09. Seoul, Republic of Korea: Association for Computing Machinery, 2009, 79–86. URL: https://doi.org/10.1145/1576702.1576716.

[CS14] V. Chandrasekaran and P. Shah. "Relative Entropy Relaxations for Signomial Optimization". In: *SIAM J. Optim*. 26 (2014), pp. 1147–1173.

[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.

[CLR95] M.-D. Choi, T. Y. Lam, and B. Reznick. "Sums of squares of real polynomials". In: *Proceedings of Symposia in Pure mathematics*. Vol. 58. American Mathematical Society. 1995, pp. 103–126.

[CLO05] D. A. Cox, J. Little, and D. O'Shea. *Using algebraic geometry*. 2nd edition. Graduate texts in mathematics. New York: Springer, 2005. xii+572.

[CLO15] D. A. Cox, J. Little, and D. O'Shea. *Ideals, varieties, and algorithms: an introduction to computational algebraic geometry and commutative algebra*. 4th edition. Undergraduate Texts in Mathematics. Cham: Springer International Publishing, 2015.
[DHL17] I. Dunning, J. Huchette, and M. Lubin. "JuMP: A Modeling Language for Mathematical Optimization". In: *SIAM Review* 59.2 (2017), pp. 295–320. URL: https://doi.org/10.1137/15M1020575.

[Erg18] A. A. Ergür. "Multihomogeneous nonnegative polynomials and sums of squares". In: *Discrete & Computational Geometry* 60.2 (2018), pp. 318–344.

[Gro66] A. Grothendieck. *Éléments de Géométrie Algébrique. IV. Étude locale des schémas et des morphismes de schémas. Troisième partie.* Vol. 28. Publ. Math. IHÉS. Rédigé avec la collaboration de J. Dieudonné. Institut des Hautes Études Scientifiques, 1966.

[HJ03] B. Hanzon and D. Jibetean. "Global minimization of a multivariate polynomial using matrix methods". In: *Journal of Global optimization* 27 (2003), pp. 1–23.

[HT24] B. E. Hilany and E. Tsigaridas. "Bounds on the infimum of polynomials over a generic semi-algebraic set using asymptotic critical values". In: *arXiv preprint arXiv:2407.17093* (2024).

[Hil88] D. Hilbert. "Über die Darstellung definit er Formen als Summe von Formenquadraten". In: *Mathematische Annalen* 32.3 (1888), pp. 342–350.

[HJ13] R. A. Horn and C. R. Johnson. *Matrix Analysis*. 2nd. Cambridge, UK: Cambridge University Press, 2013.

[JK03] Z. Jelonek and K. Kurdyka. "On asymptotic critical values of a complex polynomial". In: *Journal für die reine und angewandte Mathematik* 565 (2003), pp. 1–11.

[JL05] D. Jibetean and M. Laurent. "Semidefinite approximations for global unconstrained polynomial optimization". In: *SIAM Journal on Optimization* 16.2 (2005), pp. 490–514.

[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.

[KOS00] K. Kurdyka, P. Orro, and S. Simon. "Semialgebraic Sard theorem for generalized critical values". In: *Journal of Differential Geometry* 56.1 (2000), pp. 67–92.

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

[Las06] J.-B. Lasserre. "A Sum of Squares Approximation of Nonnegative Polynomials". In: *SIAM Journal on Optimization* 16.3 (2006), pp. 751–765.

[Las10] J.-B. Lasserre. "Best $\ell_1$-approximation of nonnegative polynomials by sums of squares". *arXiv:1012.3271 [math.OC]*. 2010.

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

[Las01] J. B. Lasserre. "Global Optimization with Polynomials and the Problem of Moments". In: *SIAM Journal on Optimization* 11.3 (Jan. 2001), pp. 796–817.

[LN07] J. B. Lasserre and T. Netzer. "SOS approximations of nonnegative polynomials via simple high degree perturbations". In: *Mathematische Zeitschrift* 256.1 (2007), pp. 99–112.

[Leg+22] B. Legat, O. Dowson, J. D. Garcia, and M. Lubin. "MathOptInterface: A Data Structure for Mathematical Optimization Problems". In: *INFORMS Journal on Computing* 34.2 (2022), pp. 672–689. URL: https://doi.org/10.1287/ijoc.2021.1067.

[Lip09] R. J. Lipton. *The curious history of Schwarz-Zippel Lemma*. http://web.archive.org/web/20080207010024/http://www.808multimedia.com/winnt/kernel.htm. 2009.

[LPR20] H. Lombardi, D. Perrucci, and M.-F. Roy. *An elementary recursive bound for effective Positivstellensatz and Hilbert's 17th problem*. Vol. 263. 1277. Memoirs of the 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.

[MSW19] V. Magron, H. Seidler, and T. de Wolff. "Exact Optimization via Sums of Nonnegative Circuits and Arithmetic-geometric-mean-exponentials". In: *Proceedings of the 2019 International Symposium on Symbolic and Algebraic Computation*. ISSAC '19. Beijing, China: Association for Computing Machinery, 2019, 291–298. URL: https://doi.org/10.1145/3326229.3326271.

[Mar03] M. Marshall. "Optimization of polynomial functions". In: *Canadian Mathematical Bulletin* 46.4 (2003), pp. 575–587.

[Mar08] M. Marshall. *Positive polynomials and sums of squares*. Mathematical surveys and monographs. Providence, R.I: American Mathematical Society, 2008.

[MOS24] MOSEK ApS. *MOSEK Optimizer*. Version 11.0.30. URL: https://www.mosek.com/documentation/. 2024.

[MK87] K. G. Murty and S. N. Kabadi. "Some NP-complete problems in quadratic and nonlinear programming". In: *Mathematical Programming* 39.2 (1987), pp. 117–129.

[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.

[Pab03] Pablo A. Parrilo, Bernd Sturmfels. "Minimizing Polynomial Functions". In: *Algorithmic and quantitative real algebraic geometry*. Ed. by S. Basu and L. Gonzalez-Vega. Vol. 60. DIMACS Series in Discrete Mathematics and Theoretical Computer Science. American Mathematical Society, Providence, RI, 2003, pp. 83–99.

[Par00] P. A. Parrilo. *Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization*. California Institute of Technology, 2000. URL: https://search.proquest.com/openview/ff5fe1a4311720ae2dad28ddc1d22cf8/1?pq-origsite=gscholar&cbl=18750&diss=y.

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

[Per88] A. L. Peressini. *The mathematics of nonlinear programming*. Undergraduate texts in mathematics. Berlin Heidelberg [etc: Springer-Verlag, 1988. x+273.

[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.

[Rez95] B. Reznick. "Uniform denominators in Hilbert's seventeenth problem". In: *Math. Z.* 220.1 (1995), pp. 75–97. URL: https://doi.org/10.1007/BF02572604.

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

[SED07] M. Safey El Din. "Testing sign conditions on a multivariate polynomial and applications". In: *Mathematics in Computer Science* 1.2 (2007), pp. 177–207.

[Sch16] C. Scheiderer. "Sums of squares of polynomials with rational coefficients". In: *Journal of the European Mathematical Society* 18.7 (May 20, 2016), pp. 1495–1513.

[Sch06] M. Schweighofer. "Global Optimization of Polynomials Using Gradient Tentacles and Sums of Squares". In: *SIAM Journal on Optimization* 17.3 (2006), pp. 920–942.

[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.
[WM20] J. Wang and V. Magron. "A second order cone characterization for sums of nonnegative circuits". In: *In Proc. 45th International Symposium on Symbolic and Algebraic Computation (ISSAC)*. Kalamata, Greece: ACM, 2020, 450-457. URL: https://doi.org/10.1145/3373207.3404033.