# Condition-based Low-Degree Approximation of Real Polynomial Systems I: The Zero-Dimensional Case

Josué Tonelli-Cueto, Elias Tsigaridas

► To cite this version:

Josué Tonelli-Cueto, Elias Tsigaridas. Condition-based Low-Degree Approximation of Real Polynomial Systems I: The Zero-Dimensional Case. MEGA 2024 - Effective Methods in Algebraic Geometry, Jul 2024, Leipzig, Germany. hal-04902434

HAL Id: hal-04902434

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

Submitted on 20 Jan 2025

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

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

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

Distributed under a Creative Commons Attribution 4.0 International License
# Condition-based Low-Degree Approximation of Real Polynomial Systems.
## I: The Zero-Dimensional Case

Josué Tonelli-Cueto*
Johns Hopkins University
Dept. Applied Mathematics and Statistics
Baltimore, MD, USA
josue.tonelli.cueto@bizkaia.eu

Elias Tsigaridas†
Inria Paris & IMJ-PRG
Sorbonne Université
Paris, FRANCE
elias.tsigaridas@inria.fr

### Abstract

We provide new bounds on the number of real zeros of a (zero-dimensional) polynomial system in terms of the condition number of the system. In the probabilistic setting, this translates into new estimates on all the moments of the number of the real zeros of random polynomial systems, including Kac and KSS polynomial systems. Moreover, the provided bounds are robust: they do not require the Gaussian assumption.

### Contents

<table><tr><td><b>1 Introduction</b></td><td><b>3</b></td></tr><tr><td><b>2 Taylor variations on Smale and Kantorovich</b></td><td><b>6</b></td></tr><tr><td>2.1 Error of Taylor approximations</td><td>6</td></tr><tr><td>2.2 Variation of Smale's parameters</td><td>10</td></tr><tr><td>2.3 Variation of the parameters of Kantorovich's theory</td><td>13</td></tr><tr><td><b>3 Condition numbers in $[-1, 1]^n$ and $\mathbb{P}^n$</b></td><td><b>13</b></td></tr><tr><td>3.1 Condition numbers in $[-1, 1]^n$</td><td>14</td></tr><tr><td>3.1.1 The 1-norm and some variational inequalities</td><td>14</td></tr><tr><td>3.1.2 A condition number for the 1-norm</td><td>15</td></tr><tr><td>3.1.3 A normalized condition number for the 1-norm</td><td>18</td></tr><tr><td>3.2 Condition numbers in $\mathbb{P}^n$</td><td>19</td></tr><tr><td>3.2.1 The Weyl norm and some variational inequalities</td><td>19</td></tr><tr><td>3.2.2 A condition number for the Weyl norm</td><td>21</td></tr><tr><td>3.2.3 A normalized condition number for the Weyl norm</td><td>23</td></tr></table>

<footnote>*This work and the author were partially supported by an AMS-Simons Travel Grant; by start-up funds of Alperen A. Ergür and NSF CCF 2110075 while at UT San Antonio, and by a postdoctoral fellowship of the 2020 "Interaction" program of the *Fondation Sciences Mathématiques de Paris*. Partially supported by ANR JCJC GALOP (ANR-17-CE40-0009) while at Inria Paris and IMJ-PRG.</footnote>

<footnote>†Partially supported by ANR JCJC GALOP (ANR-17-CE40-0009)</footnote>
<table>
  <tbody>
    <tr>
      <td>4</td>
      <td>Condition-based bounds I: Number of Zeros</td>
      <td>24</td>
    </tr>
    <tr>
      <td>4.1</td>
      <td>Bounds in [-1, 1]<sup>n</sup></td>
      <td>24</td>
    </tr>
    <tr>
      <td>4.1.1</td>
      <td>Bounds in [-1, 1]<sup>n</sup>: Local bound</td>
      <td>24</td>
    </tr>
    <tr>
      <td>4.1.2</td>
      <td>Bounds in [-1, 1]<sup>n</sup>: Cover Construction</td>
      <td>28</td>
    </tr>
    <tr>
      <td>4.2</td>
      <td>Bounds in P<sup>n</sup></td>
      <td>28</td>
    </tr>
    <tr>
      <td>4.2.1</td>
      <td>Bounds in P<sup>n</sup>: Local bound</td>
      <td>29</td>
    </tr>
    <tr>
      <td>4.2.2</td>
      <td>Bounds in P<sup>n</sup>: Cover construction</td>
      <td>31</td>
    </tr>
    <tr>
      <td>5</td>
      <td>Probabilistic bounds I: Number of Zeros</td>
      <td>32</td>
    </tr>
    <tr>
      <td>5.1</td>
      <td>Zintzo Random Polynomial Systems</td>
      <td>32</td>
    </tr>
    <tr>
      <td>5.2</td>
      <td>Dobro Random Polynomials</td>
      <td>35</td>
    </tr>
    <tr>
      <td>A</td>
      <td>Subexponential random variables</td>
      <td>41</td>
    </tr>
  </tbody>
</table>
# 1 Introduction

How many real zeros does a real polynomial system have? In the complex world, thanks to intersection theory, the analogous question has, at least in principle, a unique answer for a generic system. In the real world, even for a generic system, there is not one answer, but many possible answers depending on the coefficients of the polynomials of the system. Consequently, a common approach is to study the number of real zeros of a random polynomial system, which in turn emanates the field of the so-called random real algebraic geometry.

In more concrete terms, one central<fnref n="1" /> question in random real algebraic geometry is the following one: Let $f \in \mathbb{R}[X_1, \dots, X_n]^n$ be a random polynomial system, $U \subset \mathbb{R}^n$ some region, and consider the random variable

$$ \#\mathcal{Z}(f, U) := \#\{\zeta \in U \mid f(\zeta) = 0\}. $$

What can we say about the distribution of $\#\mathcal{Z}(f, U)$? As $f$ can follow many different probability distributions, to answer, in a satisfactory generality, this question is a hard problem.

In general<fnref n="2" />, random real algebraic geometry has well-developed general frameworks that allows us to compute

$$ \mathbb{E}_f \#\mathcal{Z}(f, U) $$

in terms of kinematic formulas [33], Kac-Rice formulas [7] or zonoid sections [44, 54]. However, turning these general formulas into concrete estimates is extremely hard. In the restricted setting of KSS<fnref n="3" /> random polynomials, these formulas have been translated into concrete estimates for the variance and the expectation [46, 61, 4, 50, 51], where recently a central limit theorem [5, 6] was shown to hold. Beyond the KSS setting, concrete explicit estimates are scarce [8, 45], with the notable exception of probabilistic real Schubert calculus [15, 48] and random fewnomial theory [17, 16, 38].

Outside the realm of the expectation of the number of real zeros, random real algebraic geometry has several approximation results in the setting of KSS polynomials [42, 29, 9] and in the more general Gaussian setting [1, 2]. In these results, it is shown that a low-degree global approximation exist with high probability, which implies some level of concentration around low values. The main consequence of these results can be summarized in the following rarefaction claim:

<footnote n="1">¹As we focus on zero-dimensional systems, we will not comment on the existing literature of Betti numbers of random real varieties [13, 40, 39, 49, 41].</footnote>

<footnote n="2">²Since the objective of this paper is not the univariate setting, our exposition in this introduction does not focus on it. However, as of today, the theory of real roots of random univariate polynomials is the *de facto gold standard* against which random real algebraic geometry compares, because the generality of the probabilistic assumptions in the univariate setting is impressive.</footnote>

<footnote>Under a wide range of assumptions, universality theorems [62, 31, 58] (see the last reference for a nice overview on this) guarantee that the expected number of real roots depends only on the variance structure of the coefficients—as the degree goes to infinity. Moreover, in many cases, one can obtain explicit ‘nice’ formulas for this expectation (see [33] for an exposition on this), being the most famous ones those by Kac [43] and Littlewood and Offord [52].</footnote>

<footnote>Under more restricted assumptions, there are central limit theorems for the three main families of Gaussian random polynomials: Kac [53], Kostlan [27, 3] and Weyl [32]. These theorems guarantee that the number of real roots converge to a normal random variable. Moreover, recently, Nguyen and Vu [57] developed a strong version of this theorem for random polynomials whose variance structure is that of Kac polynomials.</footnote>

<footnote n="3">³Kostlan-Shub-Smale</footnote>
$\mathcal{Z}(f, U)$ exceeds significantly $\mathbb{E}_f\#\mathcal{Z}(f, U)$ very rarely.

Of course, due to the central limit theorem [5], in the unmmixed KSS setting, something stronger is true:

$\mathcal{Z}(f, U)$ is concentrated around $\mathbb{E}_f\#\mathcal{Z}(f, U)$.

In this paper, we extend the above rarefaction and concentration results beyond the Gaussian setting. In particular, our two main probabilistic results can be summarized in the following two theorems. We refer to Appendix A for a definition of subexponential.

**Theorem 1.1.** Let $f \in \mathcal{P}_{n,d}[n]$ be a random polynomial system given by

$$f_i = \sum_{\alpha} f_{i,\alpha} X^{\alpha},$$

where the $f_{i,\alpha}$ are independent random variables that are (in any combination) standard Gaussians or uniformly distributed in $[-1, 1]$. Then

$$\sqrt[n]{\#\mathcal{Z}(f, [-1, 1]^n)}$$

is a subexponential random variable with constant $O(n^4 \log^3 \mathbf{D})$. In particular, for $\ell \ge 1$,

$$(\mathbb{E}_f \# \mathcal{Z}(f, \mathbb{P}^n))^{\frac{1}{\ell}} \le O(n)^{4n \log^3 n} \mathbf{D}^{\ell n}.$$

**Theorem 1.2.** Let $f \in \mathcal{H}_{n,d}[n]$ be a random homogeneous polynomial system given by

$$f_i = \sum_{\alpha} \sqrt{\binom{d_i}{\alpha}} c_{i,\alpha} X^{\alpha},$$

where the $c_{i,\alpha}$ are independent random variables that are (in any combination) standard Gaussians or uniformly distributed in $[-1, 1]$. Then

$$\sqrt[n]{\#\mathcal{Z}(f, \mathbb{P}^n)}$$

is a subexponential random variable with constant $O(n^4 \mathbf{D}^{\frac{1}{2}} \log^2 \mathbf{D})$. In particular, for $\ell \ge 1$,

$$(\mathbb{E}_f \# \mathcal{Z}(f, \mathbb{P}^n))^{\frac{\ell}{2}} \le O(n)^{4n \mathbf{D}^{\frac{n}{2}} \log^2 n} \mathbf{D}^{\ell n}.$$

To make explicit the rarefaction that these two theorems imply, we state the following two corollaries that justify the hardness of finiding zero sets with many zeros [30, 34]:

**Corollary 1.3.** Let $f \in \mathcal{P}_{n,d}[n]$ be a random polynomial system as in Theorem 1.1 and $\ell > 0$ a constant. Then

$$\mathbb{P}(\#\mathcal{Z}(f, [-1, 1]^n) \le c\mathbf{D}^\ell) \le O\left(e^{-\Omega\left(\frac{\mathbf{D}^{\frac{\ell}{n}}}{n^4 \log^3 \mathbf{D}}\right)}\right).$$

In other words, zero sets with many zeros are exponentially rare.
**Corollary 1.4.** Let $f \in \mathcal{H}_{n,d}[n]$ be a random homogeneous polynomial system as in Theorem 1.2 and $\ell > 0$ a constant. Then

$$ \mathbb{P}(\#\mathcal{Z}(f, \mathbb{P}^n) \le c\mathbf{D}^{n/2+\ell}) \le \mathcal{O}\left(e^{-\Omega\left(\frac{\mathbf{D}^\ell}{n^4 \log^2 \mathbf{D}}\right)}\right). $$

In other words, zero sets with many zeros are exponentially rare.

The general version follows from Corollary 5.5 combined with Theorem 1.5 below and Corollary 5.10 combined with Theorem 1.6 below, respectively, where it is stated, respectively, for the robust classes of zintzo and dobro random polynomial systems. Although we state the above results for a variant of Kac and KSS random polynomial system, the above theorem holds for a robust class of random polynomial system, e.g., we can vary slightly the mean and variance of the random variables involved.

However, our results are not just probabilistic, but they follow from new deterministic estimates in terms of two condition numbers:

$$ c_1(f) \propto \frac{\|f\|_1}{\mathrm{dist}_1(f, \Sigma)} \quad \text{and} \quad \kappa_W(f) = \frac{\|f\|_W}{\mathrm{dist}_W(f, \Sigma)}, $$

where $\|\cdot\|_1$ is the 1-norm (see Def. 3.1) and the Weyl norm (see Def. 3.11); and $\Sigma$ is the discriminant variety. This fundamental invariant of the system plays a fundamental role in numerical real algebraic geometry, where it is the basis of the development of many numerically stable algorithms [26, 22, 23, 25, 10, 11, 12, 20, 55, 56] and novel complexity analyses of existing algorithms [19, 21, 64, 65, 35].

We prove the following two estimates, which hold for any fixed polynomial system.

**Theorem 1.5.** Let $f \in \mathcal{P}_{n,d}[n]$ be a polynomial system. Then

$$ \#\mathcal{Z}(f, [-1, 1]^n) \le \mathcal{O}(n)^{2n} \log^{2n}(2\mathbf{D}) \log^n(2c_1(f)). $$

**Theorem 1.6.** Let $f \in \mathcal{H}_{n,d}[n]$ be an homogeneous polynomial system. Then

$$ \#\mathcal{Z}(f, \mathbb{P}^n) \le \mathcal{O}\left(\mathbf{D}^{\frac{1}{2}}\right)^n \log^n(2\mathbf{D}) \log^n(2\kappa_W(f)). $$

We refer to Theorems 4.1 and 4.8 for the bounds with explicit constants. The importance of these condition-based estimates for our probabilistic results cannot be underestimated. As of today, using geometric functional analysis [66], one can successfully perform probabilistic analyses of the condition numbers obtaining robust non-asymptotic bounds for them [24, 36, 37, 21].

Interestingly, the obtained condition-based bounds translated into the following two corollaries justifying the hardness of polynomial systems with many real zeros.

**Corollary 1.7.** Let $f \in \mathcal{P}_{n,d}[n]$ be a polynomial system and $\ell > 0$ a constant. If

$$ \#\mathcal{Z}(f, [-1, 1]^n) \ge \Omega(\mathbf{D}^\ell), $$

then

$$ c_1(f) \ge 2^{\Omega\left(\frac{\mathbf{D}^\ell/n}{n^2 \log^2 \mathbf{D}}\right)}. $$

In other words, polynomial systems with many real zeros are ill-conditioned.
**Corollary 1.8.** Let $f \in \mathcal{H}_{n,d}[n]$ be an homogeneous polynomial system and $\ell > 0$ a constant. If

$$ \#\mathcal{Z}(f, \mathbb{P}^n) \geq \Omega\left(\mathbf{D}^{\frac{n}{2}+\ell}\right), $$

then

$$ \kappa_W(f) \geq 2^{\Omega\left(\frac{D^{\ell/n}}{\log D}\right)}. $$

In other words, polynomial systems with many real zeros are ill-conditioned.

Finally, we note that the developed techniques could open the way to a new family of algorithms whose complexity only depends on the logarithm of the condition number. Unfortunately, as of today, we would need to know the condition number to make such algorithms work, but there might be a way around it in the future. In the univariate complex setting, this technique was used successfully by Moroz [55, 56] to get efficient algorithms for solving univariate polynomials.

**Overview** The rest of the paper is structured as follows. In the next section we present variations of Smale's and Kantorovich's approximation parameters for the roots of analytic functions based on Taylor expansions. Section 3 introduces condition number theorems for the hyperbox $[-1, 1]^n$ and $\mathbb{P}^n$. In Section 4 we bound the roots of a system in $[-1, 1]^n$ and $\mathbb{P}^n$ based the related condition numbers. Finally, in the last section, Section 5, by combining all the previous results, we present probabilistic bounds for roots of two classes of random polynomials, that is zintzo (Section 5.1) and dobro (Section 5.2).

# 2 Taylor variations on Smale and Kantorovich

Let $\mathcal{A}_n^0[n]$ be the complex space of analytic germs from $\mathbb{C}^n$ to $\mathbb{C}^n$ at zero. In other words, $\mathcal{A}_n^0[n]$ is the set of analytic maps $U \to \mathbb{C}^n$, where $U \subseteq \mathbb{C}^n$ is an open neighborhood of 0, identified up to equality on the common domain around zero. This last condition is an equivalence relation, and it is equivalent to having the same Taylor series at zero.

We will consider on $\mathbb{C}^n$ a fixed Banach structure. This choice induces Banach structures on the dual $(\mathbb{C}^n)^*$ and on the set of multilinear maps. Given a $k$-multilinear map $A : (\mathbb{C}^n)^k \to \mathbb{C}^q$, its induced norm will be given by

$$ \|A\| := \sup_{v_1, \dots, v_k \in \mathbb{C}^n} \frac{\|A(v_1, \dots, v_k)\|}{\|v_1\| \cdots \|v_k\|}. $$

## 2.1 Error of Taylor approximations

Recall that for any $f \in \mathcal{A}_n^0[n]$, its radius of convergence (around 0) is

$$ R_f := \left( \limsup_{k \to \infty} \left\| \frac{1}{k!} \mathrm{D}_0^k f \right\|^{\frac{1}{k}} \right)^{-1}. \qquad (2.1) $$

In this setting, it is meaningful to consider the evaluation of $f$ and its derivatives at $\|x\| < R_f$. Also the quantity

$$ \sup_{k \ge \ell} \left\| \frac{R^k}{k!} \mathrm{D}_0^k f \right\|, \qquad (2.2) $$
that will use in several estimates in the sequel, is finite for $R < R_f$.

First, we bound the difference of two functions in terms of the difference of their (corresponding) Taylor series or, equivalently, the values of an analytic function in terms of the values of the coefficients of its Taylor series.

**Proposition 2.1.** Let $f \in \mathcal{A}_n^0[n]$, $R < R_f$, $x \in \mathbb{C}^n$, and $\ell \in \mathbb{N}$. If $\|x\| < R$, then

$$ \left\| \frac{1}{\ell!} D_x^\ell f \right\| \le \frac{R}{(R - \|x\|)^{\ell+1}} \sup_{k \ge \ell} \left\| \frac{R^k}{k!} D_0^k f \right\|. $$

**Lemma 2.2.** Let $f \in \mathcal{A}_n^0[n]$, $x \in \mathbb{C}^n$, and $\ell \in \mathbb{N}$. If $\|x\| < R_f$, then

$$ \frac{1}{\ell!} D_x^\ell f = \sum_{k=\ell}^{\infty} \binom{k}{\ell} \frac{1}{k!} D_0^k f \underbrace{(x, \dots, x)}_{k-\ell \text{ times}}. $$

*Proof of Proposition 2.1.* Without loss of generality, we can assume that $\sup_{k \ge \ell} \left\| \frac{R^k}{k!} D_0^k f \right\| = 1$, since we can always multiply $f$ by a suitable constant. We prove the bound under this assumption.

By Lemma 2.2 and our assumption, we have that

$$ \left\| \frac{1}{\ell!} D_x^\ell f \right\| \le \frac{1}{R^\ell} \sum_{k=\ell}^{\infty} \binom{k}{\ell} \left\| \frac{R^k}{k!} D_0^k f \right\| \left( \frac{\|x\|}{R} \right)^{k-\ell} \le \frac{1}{R^\ell} \sum_{k=\ell}^{\infty} \binom{k}{\ell} \left( \frac{\|x\|}{R} \right)^{k-\ell}. $$

Now,

$$ \frac{1}{R^\ell} \sum_{k=\ell}^{\infty} \binom{k}{\ell} \left( \frac{\|x\|}{R} \right)^{k-\ell} = \frac{1}{R^\ell \ell!} \left. \frac{1}{dt^\ell} \right|_{t=\frac{\|x\|}{R}} \left( \frac{1}{1-t} \right) = \frac{R}{(R - \|x\|)^{\ell+1}}, \quad (2.3) $$

where the last equality follows from expanding $\frac{1}{1-t} = \frac{1}{(1-\|x\|/R)-(t-\|x\|/R)}$ as a series in $(t - \|x\|/R)$. This concludes the proof. $\square$

*Proof of Lemma 2.2.* Let $v \in \mathbb{C}^n$. Then

$$ \sum_{\ell=0}^{\infty} \frac{1}{\ell!} D_x^\ell (\underbrace{v, \dots, v}_{\ell \text{ times}}) T^\ell = f(x + Tv) = \sum_{k=0}^{\infty} \frac{1}{k!} D_0^k f (\underbrace{x + Tv, \dots, x + Tv}_{k \text{ times}}). $$

Expanding the right-hand side, we have that

$$ \frac{1}{k!} D_0^k f (\underbrace{x + Tv, \dots, x + Tv}_{k \text{ times}}) = \sum_{\ell=0}^{k} \binom{k}{\ell} \frac{1}{k!} D_0^k f (\underbrace{x, \dots, x}_{\ell \text{ times}}, \underbrace{v, \dots, v}_{\ell \text{ times}}) T^\ell, $$

where $\binom{k}{\ell}$ is due to the fact that $D_0^k f$ is a symmetric multilinear map. Hence, rearranging the series,

$$ \sum_{\ell=0}^{\infty} \frac{1}{\ell!} D_x^\ell f (\underbrace{v, \dots, v}_{\ell \text{ times}}) T^\ell = \sum_{\ell=0}^{\infty} \left( \sum_{k=\ell}^{\infty} \binom{k}{\ell} \frac{1}{k!} D_0^k f (\underbrace{x, \dots, x}_{k-\ell \text{ times}}, \underbrace{v, \dots, v}_{\ell \text{ times}}) \right) T^\ell, $$

and so we conclude that

$$ \frac{1}{\ell!} D_x^\ell f (\underbrace{v, \dots, v}_{\ell \text{ times}}) = \sum_{k=\ell}^{\infty} \binom{k}{\ell} \frac{1}{k!} D_0^k f (\underbrace{x, \dots, x}_{k-\ell \text{ times}}, \underbrace{v, \dots, v}_{\ell \text{ times}}). $$
Since $v$ was arbitrary and we are in characteristic zero, the polarization gives the desired claim—i.e., for two symmetric $k$-multilinear maps $A$ and $B$ to be equal is enough that for every $v$, $A(v, \dots, v) = B(v, \dots, v)$. $\square$

Now, we introduce the Taylor truncation and show a result giving us bounding the error of the Taylor approximation.

**Definition 2.3.** Let $f \in \mathcal{A}_n^0[n]$ and $\delta \in \mathbb{N}$. The Taylor approximation of degree $\delta$ of $f$, $f|_{\delta}$, is the polynomial function

$$f|_{\delta} := \sum_{k=0}^{\delta} \frac{1}{k!} D_0^k f(\overbrace{X, \dots, X}^{k \text{ times}}) \in \mathcal{P}_{n, \delta} [q].$$

**Proposition 2.4.** Let $f \in \mathcal{A}_n^0[n]$, $R < R_f$, $x \in \mathbb{C}^n$, and $\ell, \delta \in \mathbb{N}$. If $\|x\| < R$, then

$$\left\| \frac{1}{\ell!} D_x^\ell f - \frac{1}{\ell!} D_x^\ell f|_{\delta} \right\| \le \frac{R}{(R - \|x\|)^{\ell+1}} \min \left\{ 1, e^{(\delta+1)\ell} \left( \frac{\|x\|}{R} \right)^{\delta+1-\ell} \right\} \sup_{k \ge \delta+1} \left\| \frac{R^k}{k!} D_0^k f \right\|.$$

Furthermore, we have that

$$(1) \qquad \left\| f(x) - f|_{\delta}(x) \right\| \le \frac{R}{R - \|x\|} \left( \frac{\|x\|}{R} \right)^{\delta+1} \sup_{k \ge \delta+1} \left\| \frac{R^k}{k!} D_0^k f \right\|.$$

$$(2) \qquad \left\| D_x f - D_x f|_{\delta} \right\| \le \frac{(R + \delta(R - \|x\|))}{(R - \|x\|)^2} \left( \frac{\|x\|}{R} \right)^{\delta} \sup_{k \ge \delta+1} \left\| \frac{R^k}{k!} D_0^k f \right\|.$$

*Proof.* As with Proposition 2.1, we can assume without loss of generality that $R = 1$ and that $\sup_{k \ge \delta+1} \left\| \frac{1}{k!} D_0^k f \right\| = 1$.

By Lemma 2.2, we have that

$$\left\| \frac{1}{\ell!} D_x^\ell f - \frac{1}{\ell!} D_x^\ell f|_{\delta} \right\| \le \frac{1}{R^\ell} \sum_{k=\ell}^{\infty} \binom{k}{\ell} \left\| \frac{R^k}{k!} D_0^k (f - f|_{\delta}) \right\| \left( \frac{\|x\|}{R} \right)^{k-\ell}.$$

By the definition of $f|_{\delta}$, $D_0^k(f - f|_{\delta}) = 0$ for $k \le \delta$, and $D_0^k(f - f|_{\delta}) = D_0^k f$ for $k \ge \delta + 1$. Thus

$$\left\| \frac{1}{\ell!} D_x^\ell f - \frac{1}{\ell!} D_x^\ell f|_{\delta} \right\| = \frac{1}{R^\ell} \sum_{k=\max\{\ell, \delta+1\}}^{\infty} \binom{k}{\ell} \left\| \frac{R^k}{k!} D_0^k f \right\| \left( \frac{\|x\|}{R} \right)^{k-\ell} \\ \le \frac{1}{R^\ell} \sum_{k=\max\{\ell, \delta+1\}}^{\infty} \binom{k}{\ell} \left( \frac{\|x\|}{R} \right)^{k-\ell}.$$

On the one hand, arguing as in Proposition 2.1,

$$\frac{1}{R^\ell} \sum_{k=\max\{\ell, \delta+1\}}^{\infty} \binom{k}{\ell} \left( \frac{\|x\|}{R} \right)^{k-\ell} \le \frac{1}{R^\ell} \sum_{k=\ell}^{\infty} \binom{k}{\ell} \left( \frac{\|x\|}{R} \right)^{k-\ell} \\ = \frac{1}{R^\ell} \frac{1}{\ell!} \left. \frac{d^\ell}{dt^\ell} \right|_{t=\frac{\|x\|}{R}} \left( \frac{1}{1-t} \right) = \frac{R}{(R - \|x\|)^{\ell+1}}.$$
On the other hand,

$$ \frac{1}{R^\ell} \sum_{k=\max\{\ell, \delta+1\}}^\infty \binom{k}{\ell} \left(\frac{\|x\|}{R}\right)^{k-\ell} \le \frac{1}{R^\ell} \sum_{k=\delta+1}^\infty \binom{k}{\ell} \left(\frac{\|x\|}{R}\right)^{k-\ell} = \frac{1}{R^\ell} \frac{1}{\ell!} \left. \frac{d^\ell}{dt^\ell} \right|_{t=\|x\|} \left(\frac{t^{\delta+1}}{1-t}\right), $$

where we use that $\sum_{k=\delta+1} t^k = t^{\delta+1}/(1-t)$. Now,

$$ \frac{1}{1-t} = \sum_{k=0}^{\infty} \frac{\left(t - \frac{\|x\|}{R}\right)^k}{\left(1 - \frac{\|x\|}{R}\right)^{k+1}} \quad \text{and} \quad t^{\delta+1} = \sum_{k=0}^{\delta+1} \binom{\delta+1}{k} \left(\frac{\|x\|}{R}\right)^{\delta+1-k} \left(t - \frac{\|x\|}{R}\right)^k. $$

Therefore, by multiplying the two series and using Taylor's theorem, we have

$$ \frac{1}{R^\ell} \frac{1}{\ell!} \left. \frac{d^\ell}{dt^\ell} \right|_{t=\|x\|} \left( \frac{t^{\delta+1}}{1-t} \right) = \frac{1}{R^\ell} \sum_{k=0}^\ell \binom{\delta+1}{k} \left( \frac{\|x\|}{R} \right)^{\delta+1-k} \frac{1}{\left(1 - \frac{\|x\|}{R}\right)^{\ell-k+1}} \quad (2.4) $$

To finish the proof, we only have to note that

$$ \begin{aligned} & \frac{1}{R^\ell} \sum_{k=0}^\ell \binom{\delta+1}{k} \left(\frac{\|x\|}{R}\right)^{\delta+1-k} \frac{1}{\left(1 - \frac{\|x\|}{R}\right)^{\ell-k+1}} \\ & \le \left(\frac{\|x\|}{R}\right)^{\delta+1-\ell} \frac{R}{(R - \|x\|)^{\ell+1}} \sum_{k=0}^\ell \binom{\delta+1}{k} \left(1 - \frac{\|x\|}{R}\right)^k \\ & \le (\delta+1)^\ell \left(\frac{\|x\|}{R}\right)^{\delta+1-\ell} \frac{R}{(R - \|x\|)^{\ell+1}} \sum_{k=0}^\ell \frac{1}{k!} \left(1 - \frac{\|x\|}{R}\right)^k \\ & \le (\delta+1)^\ell \left(\frac{\|x\|}{R}\right)^{\delta+1-\ell} \frac{1}{\left(1 - \frac{\|x\|}{R}\right)^{\ell+1}} e^{1 - \frac{\|x\|}{R}}, \end{aligned} $$

since $\|x\|/R < 1$, by assumption, and $(1 - \|x\|/R)^{-1} \ge 1$, also by assumption. For the more specific claims for $\ell \le 1$, we just compute directly. $\square$

In our setting, we restrict ourselves to $x \in \mathbb{B}^n$, i.e., $\|x\| < 1$, and $R = 2$. In this case, we obtain better inequalities.

**Proposition 2.5.** Let $f \in \mathcal{A}_n^0[n]$ such that $2 < R_f$, $x \in \mathbb{B}^n$, and $\ell, \delta \in \mathbb{N}$. Then

$$ \left\| \frac{1}{\ell!} D_x^\ell f - \frac{1}{\ell!} D_x^\ell f|_\delta \right\| \le \min \left\{ 2, \frac{e(\delta+1)^\ell}{2^\delta} \right\} \sup_{k \ge \delta+1} \left\| \frac{2^k}{k!} D_0^k f \right\|. $$

Furthermore, we have that

$$ (0) \qquad \left\| f(x) - f|_\delta(x) \right\| \le \frac{1}{2^\delta} \sup_{k \ge \delta+1} \left\| \frac{2^k}{k!} D_0^k f \right\|. $$

$$ (1) \qquad \left\| D_x f - D_x f|_\delta \right\| \le \frac{\delta+2}{2^\delta} \sup_{k \ge \delta+1} \left\| \frac{2^k}{k!} D_0^k f \right\|. $$
$$ (2) \qquad \|D_x^2 f - D_x^2 f|_{\delta}\| \le \frac{(\delta+2)^2}{2^{\delta}} \sup_{k \ge \delta+1} \left\| \frac{2^k}{k!} D_0^k f \right\|. $$

*Proof.* The proof is analogous to that of Proposition 2.4. However, now, (2.4) is bounded by

$$ \frac{1}{2^\ell} \sum_{k=0}^{\ell} \binom{\delta+1}{k} \left(\frac{1}{2}\right)^{\delta+1-k} \frac{1}{\left(\frac{1}{2}\right)^{\ell-k+1}} = \frac{1}{2^\delta} \sum_{k=0}^{\ell} \binom{\delta+1}{k} \le \frac{e^{(\delta+1)^\ell}}{2^\delta}. $$

The latter gives the improved bound over the conclusion of Proposition 2.4. □

## 2.2 Variation of Smale's parameters

We recall the parameters of Smale's $\alpha$-theory.

**Definition 2.6.** Let $f \in \mathcal{A}_n^0[n]$ and $x \in \text{dom } f$. We define:

(a) Smale's $\alpha$: $\alpha(f, x) := \beta(f, x)\gamma(f, x)$.

(b) Smale's $\beta$: $\beta(f, x) := \|D_x f^{-1} f(x)\|$.

(c) Smale's $\gamma$:

$$ \gamma(f, x) := \begin{cases} \max\{1, \sup_{k \ge 2} \|D_x f^{-1} \frac{1}{k!} D_x^k f\|^{\frac{1}{k-1}}\}, & \text{if } D_x f \text{ is invertible} \\ \infty, & \text{otherwise} \end{cases}. $$

We study how these parameters vary inside the unit ball when we substitute $f$ by its approximation of degree $\delta$ under the condition $2 < R_f$. We note that our estimates will depend on

$$ \tau(f, x; \delta) := \sup_{k \ge \delta+1} \left\| D_x f^{-1} \frac{2^k}{k!} D_0^k f \right\|. \quad (2.5) $$

The latter has the advantage of having the same invariance as Smale's parameters and playing the role of a sort of condition number. Note that this is the same as working with $D_x f^{-1} f : y \mapsto D_x f^{-1} f(y)$ which has the same radius of convergence as $f$. Moreover, observe that $(D_x f^{-1} f)|_{\delta} = D_x f^{-1} f|_{\delta}$.

**Theorem 2.7.** Let $f \in \mathcal{A}_n^0[n]$ such that $2 < R_f$, $x \in \mathbb{B}^n$ and $\delta \in \mathbb{N}$. If $D_x f$ is invertible and

$$ \delta - \log(\delta + 2) \ge \log \tau(f, x; \delta), \quad (2.6) $$

then $D_x f|_{\delta}$ is invertible ant the following hold:

$$ (a) \qquad \alpha(f|_{\delta}, x) \le \frac{2\alpha(f, x) + \frac{1}{2^{\delta-1}}\gamma(f, x) \tau(f, x; \delta)}{\left(1 - \frac{\delta+2}{2^{\delta}} \tau(f, x; \delta)\right)^2}. $$

$$ (b) \qquad \beta(f|_{\delta}, x) \le \frac{\beta(f, x) + \frac{1}{2^{\delta}} \tau(f, x; \delta)}{1 - \frac{\delta+2}{2^{\delta}} \tau(f, x; \delta)}. $$
(c)

$$ \gamma(f|_{\delta}, x) \leq \frac{2\gamma(f, x)}{1 - \frac{\delta+2}{2^{\delta}} \tau(f, x; \delta)}. $$

**Corollary 2.8.** Let $f \in \mathcal{A}_n^0[n]$ such that $2 < R_f, \zeta \in \mathbb{B}^n$ and $\delta \in \mathbb{N}$. If $\zeta$ is a regular zero of $f$ and (2.6), then $D_\zeta f|_\delta$ is invertible and

$$ \alpha(f|_{\delta}, \zeta) \leq \frac{\gamma(f, \zeta) \tau(f, \zeta; \delta)}{2^{\delta-1} \left(1 - \frac{\delta+2}{2^{\delta}} \tau(f, \zeta; \delta)\right)^2}. \quad \square $$

**Lemma 2.9.** Let $A, H \in \mathbb{C}^{q \times n}$. If A is invertible and $\|A^{-1}H\| < 1$, then $A+H$ is invertible and

$$ \|(A+H)^{-1}A\| \leq \frac{1}{1 - \|A^{-1}H\|}. $$

*Proof of Theorem 2.7.* We only have to show (b) and (c), since (a) follows from them.

(b) We have that

$$ \begin{aligned} \beta(f|_{\delta}, x) &= \|D_x f|_{\delta}^{-1} D_x f D_x f^{-1} f|_{\delta}(x)\| && (D_x f D_x f^{-1} = \mathbb{I}) \\ &\le \|D_x f|_{\delta}^{-1} D_x f\| \|D_x f^{-1} f|_{\delta}(x)\| && (\text{Submultiplicativy}) \\ &\le \|D_x f|_{\delta}^{-1} D_x f\| (\|D_x f^{-1} f(x)\| + \|D_x f^{-1} (f|_{\delta}(x) - f(x))\|) && (\text{Triangle ineq.}) \\ &\le \|D_x f|_{\delta}^{-1} D_x f\| (\beta(f, x) + \|D_x f^{-1} (f|_{\delta}(x) - f(x))\|) && (\text{Def. } \beta). \end{aligned} $$

Now, Proposition 2.5 (applied to $y \mapsto D_x f^{-1} f(y)$) and by assumption, $\|D_x f^{-1}(D_x f|_{\delta} - D_x f)\| \le \frac{\delta+2}{2^{\delta}} \tau(f, x; \delta) < 1$. Thus, by Lemma 2.9,

$$ \|D_x f|_{\delta}^{-1} D_x f\| \le \frac{1}{1 - \frac{\delta+2}{2^{\delta}} \tau(f, x; \delta)}. \quad (2.7) $$

Again, Proposition 2.5 (applied to $y \mapsto D_x f^{-1} f(y)$), we have that

$$ \|D_x f^{-1}(f|_{\delta}(x) - f(x))\| \le \frac{1}{2^{\delta}} \tau(f, x; \delta). \quad (2.8) $$

The proof of (b) concludes combining (2.7) and (2.8).

(c) Arguing as in (b), we have that

$$ \begin{aligned} \gamma(f|_{\delta}, x) &\le \sup_{\ell \ge 2} \left\| D_x f|_{\delta}^{-1} D_x f \right\|^{\frac{1}{\ell-1}} \left\| D_x f^{\dagger} \frac{1}{\ell!} D_x^{\ell} f|_{\delta} \right\|^{\frac{1}{\ell-1}} \\ &\le \sup_{\ell \ge 2} \left\| D_x f|_{\delta}^{-1} D_x f \right\|^{\frac{1}{\ell-1}} \left( \left\| D_x f^{\dagger} \frac{1}{\ell!} D_x^{\ell} f \right\| + \left\| D_x f^{\dagger} \frac{1}{\ell!} (D_x^{\ell} f|_{\delta} - D_x^{\ell} f) \right\| \right)^{\frac{1}{\ell-1}} \\ &\le \sup_{\ell \ge 2} \left\| D_x f|_{\delta}^{-1} D_x f \right\|^{\frac{1}{\ell-1}} \left( \left\| D_x f^{\dagger} \frac{1}{\ell!} D_x^{\ell} f \right\|^{\frac{1}{\ell-1}} + \left\| D_x f^{\dagger} \frac{1}{\ell!} (D_x^{\ell} f|_{\delta} - D_x^{\ell} f) \right\|^{\frac{1}{\ell-1}} \right) \\ &\le \sup_{\ell \ge 2} \left\| D_x f|_{\delta}^{-1} D_x f \right\|^{\frac{1}{\ell-1}} \left( \gamma(f, x) + \sup_{\ell \ge 2} \left\| D_x f^{\dagger} \frac{1}{\ell!} (D_x^{\ell} f|_{\delta} - D_x^{\ell} f) \right\|^{\frac{1}{\ell-1}} \right), \end{aligned} $$

where the first inequality follows as that of $\beta$, the second one by the triangle inequality, the third one by the Minkowski's inequality, and the last one by the definition of $\gamma$.
Now, by (2.7),

$$ \sup_{\ell \ge 2} \left\| D_x f_{|\delta}^{-1} D_x f \right\|^{\frac{1}{\ell-1}} \le \frac{1}{1 - \frac{\delta+2}{2^\delta} \tau(f, x; \delta)}, \quad (2.9) $$

and, by Proposition 2.5 (applied to $y \mapsto D_x f^{-1} f(y)$),

$$ \sup_{\ell \ge 2} \left\| D_x f^{\dagger} \frac{1}{\ell!} (D_x^{\ell} f_{|\delta} - D_x^{\ell} f) \right\|^{\frac{1}{\ell-1}} \le \sup_{\ell \ge 2} (2 \tau(f, x; \delta))^{\frac{1}{\ell-1}} \le 1 \le \gamma(f, x), \quad (2.10) $$

these two inequalities finish the proof of (c).

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

*Proof of Lemma 2.9.* If $\|X\| < 1$, then we have that

$$ (\mathbb{I} + X)^{-1} = \mathbb{I} + \sum_{k=1}^{\infty} X^k, $$

since the series on the right-hand side is absolutely convergent. Thus, if $\|A^{-1}H\| < 1$, we have that

$$ (A + H)^{-1} = (\mathbb{I} + A^{-1}H)^{-1}A^{-1} = \left( \mathbb{I} + \sum_{k=1}^{\infty} (A^{-1}H)^k \right) A^{-1}, $$

and so $A+H$ is invertible. Finally, $(A+H)^{-1}A = \mathbb{I} + \sum_{k=1}^{\infty} (A^{-1}H)^k$. Thus, taking norms, the desired inequality follows. □

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

The following theorem and its corollary are the converses of Theorem 2.7 and Corollary 2.8, where we bound the Smale's parameters of $f$ in terms of those of $f_{|\delta}$. The latter is important for algorithms, as it guarantees that finding the zeros of $f_{|\delta}$ leads to finding the zeros of $f$ à la Smale.

**Theorem 2.10.** Let $f \in \mathcal{A}_n^0[n]$ such that $2 < R_f, x \in \mathbb{B}^n$ and $\delta \in \mathbb{N}$. If $D_x f_{|\delta}$ is surjective and (2.6), then:

(a) $$ \alpha(f, x) \le \frac{2\alpha(f_{|\delta}, x) + \frac{1}{2^{\delta-1}}\gamma(f_{|\delta}, x) \tau(f, x; \delta)}{\left(1 - \frac{\delta+2}{2^\delta} \tau(f, x; \delta)\right)^2}. $$

(b) $$ \beta(f, x) \le \frac{\beta(f_{|\delta}, x) + \frac{1}{2^\delta} \tau(f, x; \delta)}{1 - \frac{\delta+2}{2^\delta} \tau(f, x; \delta)}. $$

(c) $$ \gamma(f, x) \le \frac{2\gamma(f_{|\delta}, x)}{1 - \frac{\delta+2}{2^\delta} \tau(f, x; \delta)}. $$

**Corollary 2.11.** Let $f \in \mathcal{A}_n^0[n]$ such that $2 < R_f, \zeta \in \mathbb{B}^n$ and $\delta \in \mathbb{N}$. If $\zeta$ is a regular zero of $f_{|\delta}$, $D_x f$ is invertible and (2.6), then

$$ \alpha(f, \zeta) \le \frac{\gamma(f, \zeta) \tau(f, \zeta; \delta)}{2^{\delta-1} \left(1 - \frac{\delta+2}{2^\delta} \tau(f, \zeta; \delta)\right)^2}. \quad \square $$
Proof of Theorem 2.10. The proof is analogous to that of Theorem 2.7 but interchanging the role of $f$ and $f_{|\delta}$. Because of this, we omit the details, but let us point the main differences. On the one hand, we first split the sum, and then subsitute $D_x f^{-1}$ by $D_x f_{|\delta}^{-1}$. On the other hand, to do this latter substitution we will apply

$$ \|D_x f^{-1} D_x f_{|\delta}\| \le 1 + \|D_x f^{-1} (D_x f_{|\delta} - D_x f)\| \le 1 + \frac{\delta+2}{2^\delta} \tau(f, x; \delta) \quad (2.11) $$

instead of the inequality (2.7). The rest is straightforward. □

## 2.3 Variation of the parameters of Kantorovich's theory

In the same way, we can control the variation of Smale's parameters with respect Taylor approximations. We can do the same with the parameters of Kantorovich's theory.

**Definition 2.12.** Let $f \in \mathcal{A}_n^0[n]$, $x \in \text{dom } f$ and $r > 0$ such that $\mathbb{B}(x, r) \subseteq \text{dom } f$. We define:

$$ K(f, x, r) := \sup_{\|y-x\| \le r} \|D_x f^{-1} D_y^2 f\|. $$

The following theorem gives the variation of $K$ in terms of the above parameters.

**Theorem 2.13.** Let $f \in \mathcal{A}_n^0[n]$ such that $2 < R_f$, and $x \in \mathbb{B}^n$ and $r > 0$ such that $\|x\| + r \le 1$. If $D_x f$ is surjective and and (2.6), then

$$ K(f_{|\delta}, x, r) \le \frac{K(f, x, r) + \frac{(\delta+2)^2}{2^\delta} \tau(f, x; \delta)}{1 - \frac{\delta+2}{2^\delta} \sup_{k \ge \delta+1} \left\| D_x f^{-1} \frac{2^k}{k!} D_0^k f \right\|} $$

and

$$ K(f, x, r) \le \frac{K(f_{|\delta}, x, r) + \frac{(\delta+2)^2}{2^\delta} \tau(f, x; \delta)}{1 - \frac{\delta+2}{2^\delta} \sup_{k \ge \delta+1} \left\| D_x f^{-1} \frac{2^k}{k!} D_0^k f \right\|} $$

*Proof.* The proof is very similar to those of Theorems 2.7 and 2.10. Because of this, we only sketch it. Arguing as we did in Theorems 2.7(c), we obtain

$$ K(f_{|\delta}, x, r) \le \|D_x f^{-1} D_x f\| \left( K(f, x, r) + \sup_{\|y-x\| \le r} \|D_x f^{-1} (D_y^2 f_{|\delta} - D_y^2 f)\| \right), $$

and arguing as in Theorems 2.10(c), we obtain

$$ K(f, x, r) \le \|D_x f^{-1} D_x f\| K(f_{|\delta}, x, r) + \sup_{\|y-x\| \le r} \|D_x f^{-1} (D_y^2 f - D_y^2 f_{|\delta})\|. $$

Finally, we just apply Proposition 2.5 (obtaining bounds analogous to (2.8) and (2.9)) together with (2.7) and (2.10). □

## 3 Condition numbers in $[-1, 1]^n$ and $\mathbb{P}^n$

In this section, we prove some results regarding the condition numbers of polynomial systems with respect to $[-1, 1]^n$ and with respect to $\mathbb{P}^n$. In both cases, we will be not using functional norms as in [20], since it is not clear how to use such norms to improve the estimates that we get. Because of that, we will employ the 1-norm of polynomials when we work in $[-1, 1]^n$, and the Weyl norm when we work in $\mathbb{P}^n$.
## 3.1 Condition numbers in $[-1, 1]^n$

The present subsection can be considered as an apère for the second part of [65] (cf. [64]). We will generalize the results there to arbitrary co-dimension.

### 3.1.1 The 1-norm and some variational inequalities

We define the 1-norm for polynomials. Note that this norm is not the 1-norm of all coefficients, but the maximum of the 1-norm of the coefficients of each polynomial in the tuple.

**Definition 3.1.** Let $f \in \mathcal{P}_{n,d}[q]$. The 1-norm of $f$ is the norm given by

$$ \|f\|_1 := \max_{i \in [q]} \sum_{|\alpha|=d_i} |f_{i,\alpha}|. $$

The following theorem is a straight generalization of [65, Proposition 3.4 & Corollary 3.5] and its corollaries.

**Theorem 3.2.** Let $f \in \mathcal{P}_{n,d}[q]$ and $\ell \ge 0$. For $v_1, \dots, v_\ell \in \mathbb{R}^n$,

$$ \left\| \Delta^{-\ell} \mathcal{D}_X^{\ell} f(v_1, \dots, v_\ell) \right\|_1 \le \|f\|_1 \|v_1\|_{\infty} \cdots \|v_\ell\|_{\infty}, $$

and

$$ \left\| \frac{1}{\ell!} \mathcal{D}_X^{\ell} f(v_1, \dots, v_\ell) \right\|_1 \le \binom{\mathbf{D}}{\ell} \|f\|_1 \|v_1\|_{\infty} \cdots \|v_\ell\|_{\infty}. $$

In particular, for $z \in \mathbb{D}^n$, $\left\| \frac{1}{\ell!} \mathcal{D}_z^{\ell} f(v_1, \dots, v_\ell) \right\|_{\infty} \le \binom{\mathbf{D}}{\ell} \|f\|_1 \|v_1\|_{\infty} \cdots \|v_\ell\|_{\infty}.$

*Proof.* The claim holds for $q = 1$ by [65, Proposition 3.4 & Corollary 3.5]. The case for $q > 1$ holds from the fact that the 1-norm takes the maximum 1-norm of the $f_i$. $\square$

The following proposition, analogous to [65, Proposition 3.9], extends the above claims to the larger domain $\mathbb{D}_\varepsilon^n := \{z \in \mathbb{C}^n \mid \mathrm{dist}_\infty(z, \mathbb{D}^n) \le \varepsilon\}$.

**Proposition 3.3.** Let $f \in \mathcal{P}_{n,d}[q]$, $\varepsilon \le \frac{1}{\mathbf{D}}$ and $\ell \ge 0$. For $z \in \mathbb{D}_\varepsilon^n$ and $v_1, \dots, v_\ell \in \mathbb{C}^n$,

$$ \left\| \Delta^{-\ell} \mathcal{D}_z^{\ell} f(v_1, \dots, v_\ell) \right\|_{\infty, \infty} \le e \|f\|_1 \|v_1\|_{\infty} \cdots \|v_\ell\|_{\infty}. $$

and

$$ \left\| \frac{1}{\ell!} \mathcal{D}_z^{\ell} f(v_1, \dots, v_\ell) \right\|_{\infty, \infty} \le e \binom{\mathbf{D}}{\ell} \|f\|_1 \|v_1\|_{\infty} \cdots \|v_\ell\|_{\infty}. $$

*Proof.* We only have to prove that for a polynomial $g$ of degree $\mathbf{D}$, we have that for $z \in \mathbb{D}_\varepsilon^n$,

$$ |g(z)| \le e \|g\|_1. $$

Now, let $z_0 \in \mathbb{D}^n$ be such that $\|z - z_0\|_{\infty} \le \varepsilon$. By Taylor's theorem and Theorem 3.2, we have that

$$ |g(z)| \le \sum_{\ell=0}^{\mathbf{D}} \binom{\mathbf{D}}{\ell}^2 \|g\|_1 \|z - z_0\|_{\infty}^{\ell} = \|g\|_1 (1 + \|z - z_0\|_{\infty})^{\mathbf{D}} \le \|g\|_1 (1 + \varepsilon)^{\mathbf{D}}. $$

Now, $\varepsilon \le 1/\mathbf{D}$, so $(1 + \varepsilon)^{\mathbf{D}} \le e$ and the claim follows. $\square$

<figure><img src="image_4.png" /></figure>
We finish showing some Lipschitz properties, which generalizes [65, Propositions 3.7 & 3.9].

**Proposition 3.4.** Let $f \in \mathcal{P}_{n,d}[q]$ and $\ell \in \mathbb{N}$. Then the map

$$ \mathbb{D}^n \to ((\mathbb{R}^n)^{\otimes k})^q \\ x \mapsto \frac{1}{\|f\|_1} \Delta^{-\ell} \mathcal{D}_x^{\ell} f $$

is well-defined and $(\mathbf{D} - \ell)$-Lipschitz with respect to the $\infty$-norm in the domain and $\| \cdot \|_{\infty, \infty}$ in the codomain. Moreover, for $\epsilon \in (0, 1/\mathbf{D}]$, the extension of this map to $\mathbb{D}_\epsilon^n$ is $e(\mathbf{D} - \ell)$-Lipschitz.

*Proof.* Without loss of generality, assume that $\|f\|_1 = 1$. We only have to show the claim for maps of the form

$$ x \mapsto \Delta^{-\ell} \mathcal{D}_x^{\ell} f(v_1, \dots, v_\ell) $$

with $v_1, \dots, v_\ell \in \partial \mathbb{D}^n$ arbitrary and where we use the $\infty$-norm both in the domain and codomain.

Now, for $t \mapsto x_t$ such that $\|\dot{x}_t\|_\infty = \|x_1 - x_0\|_\infty$, we have that, by the intermediate value theorem,

$$ \| \Delta^{-\ell} \mathcal{D}_{x_1}^{\ell} f(v_1, \dots, v_\ell) - \Delta^{-\ell} \mathcal{D}_{x_0}^{\ell} f(v_1, \dots, v_\ell) \|_{\infty} \\ \le \sup_{t \in [0,1]} \| \Delta^{-\ell} \mathcal{D}_{x_t}^{\ell+1} f(v_1, \dots, v_\ell) \|_{\infty} \| x_1 - x_0 \|_{\infty}. $$

Now, the right-hand side is bounded by the desired quantity by Theorem 3.2. For the last claim, we use Proposition 3.3 instead. $\square$

### 3.1.2 A condition number for the 1-norm

Recall that for $A \in \mathbb{C}^{q \times n}$,

$$ \|A^{-1}\|_{\infty, \infty}^{-1} = \min_{v \in \mathbb{C}^n} \frac{\|Av\|_{\infty}}{\|v\|_{\infty}}, \qquad (3.1) $$

and so $A \mapsto \|A^{-1}\|_{\infty, \infty}^{-1}$ is 1-Lipschitz with respect $\| \cdot \|_{\infty, \infty}$. Also, note that when $A$ is a real matrix, we have that

$$ \|A^{-1}\|_{\infty, \infty}^{-1} = \min_{v \in \mathbb{C}^n} \frac{\|Av\|_{\infty}}{\|v\|_{\infty}} = \min_{v \in \mathbb{R}^n} \frac{\|Av\|_{\infty}}{\|v\|_{\infty}}. \qquad (3.2) $$

Now, we can define a condition number and prove its properties.

**Definition 3.5.** Let $f \in \mathcal{P}_{n,d}[n]$. The local condition number of $f$ at $x \in \mathbb{D}^n$ is

$$ \mathcal{C}_1(f, x) := \frac{\|f\|_1}{\max\{\|f(x)\|_{\infty}, \|\mathcal{D}_x f^{-1} \Delta\|_{\infty, \infty}^{-1}\}}, $$

and the global condition number of $f$ is

$$ \mathcal{C}_1(f, x) := \max_{x \in \mathbb{I}^n} \mathcal{C}_1(f, x) $$
The following theorem showcases the main properties of the condition numbers defined above. It is analogous to [65, Theorem 4.2].

**Theorem 3.6.** Let $f \in \mathcal{P}_{n,d}[n]$ and $x \in I^n$. Then:

* **Regularity inequality:** Either

$$ \frac{\|f(x)\|_{\infty}}{\|f\|_{1}} \geq \frac{1}{C_{1}(f, x)} \quad \text{or} \quad \frac{\|D_{x} f^{-1} \Delta\|_{\infty, \infty}^{-1}}{\|f\|_{1}} \geq \frac{1}{C_{1}(f, x)}. $$

In particular, if $C_1(f, x) \frac{\|f(x)\|_{\infty}}{\|f\|_{1}} < 1$, then $D_x f$ is invertible.

* **1st Lipschitz inequality:** The maps

$$ \begin{array}{ccc} \mathcal{P}_{n,d}[n] \to [0, \infty) & & \mathcal{P}_{n,d}[n] \to [0, \infty) \\ g \mapsto \frac{\|g\|_{1}}{C_{1}(g, x)} & \text{and} & g \mapsto \frac{\|g\|_{1}}{C_{1}(g)} \end{array} $$

are 1-Lipschitz with respect the 1-norm. In particular, $C_1(f, x) \ge 1$.

* **2nd Lipschitz inequality:** The map

$$ \begin{array}{l} \mathbb{D}^n \to [0, 1] \\ y \mapsto \frac{1}{C_1(f, y)} \end{array} $$

is D-Lipschitz with respect the $\infty$-norm.

* **Higher derivative estimate:** If $C_1(f, x) \frac{\|f(x)\|_{\infty}}{\|f\|_{1}} < 1$, then

$$ \gamma_2(f, x) \leq \frac{n(\mathbf{D} - 1)}{2} C_1(f, x). $$

*Proof.* All arguments are very similar to those of [65, Theorem 4.2], so we only sketch them.

The regularity inequality follows immediately from the definition.

The 1st Lipschitz follows from the Lipschitz properties of $\|\cdot\|_{\infty}$ and (3.2). The 2nd Lipschitz property follows again from the Lipschitz properties of $\|\cdot\|_{\infty}$ and (3.2) and the Lipschitz properties stated in Proposition 3.4.

For the Higher Derivative Estimate, note that

$$ \left\| D_x f^{-1} \frac{1}{k!} \Delta^{-1} D_x^k f \right\|_{2,2} \le \left\| (\Delta^{-1} D_x f)^{\dagger} \right\|_{2,2} \left\| \frac{1}{k!} \Delta^{-1} D_x^k f \right\|_{2,2}. $$

Now, by standard comparisons between norms,

$$ \left\| (\Delta^{-1} D_x f)^{\dagger} \right\|_{2,2} = \frac{1}{\sigma_q (\Delta^{-1} D_x f)} \le \frac{\sqrt{n}}{\zeta_q (\Delta^{-1} D_x f)} \le \frac{\sqrt{n} C_1(f, x)}{\|f\|_{1}}, $$

where the last inequality follows from the regularity inequality and our assumption. Similarly,

$$ \left\| \frac{1}{k!} \Delta^{-1} D_x^k f \right\|_{2,2} \le \sqrt{n} \left\| \frac{1}{k!} \Delta^{-1} D_x^k f \right\|_{\infty, \infty} \le \frac{\sqrt{n}}{k} \binom{\mathbf{D}-1}{k-1} \|f\|_1. $$
Thus

$$ \gamma_2(f, x) \leq \sup_{k \geq 2} \left( \frac{n}{k} \binom{\mathbf{D}-1}{k-1} \|f\|_1 \mathcal{C}_1(f, x) \right)^{\frac{1}{k-1}} \leq \left( \frac{1}{k} \binom{\mathbf{D}-1}{k-1} \|f\|_1 \right)^{\frac{1}{k-1}} n \mathcal{C}_1(f, x), $$

where the supremum is attained at $k=2$, since $k! \geq 2^{k-1}$.

Moreover, if $q=1$ or $q=n$, the term $\sqrt{qn}$ on the right-hand side can be omitted. $\square$

We finish with the following theorem relating the condition number to the inverse of the distance to the discriminant.

**Proposition 3.7 (Condition Number Theorem).** Let $f \in \mathcal{P}_{n,d}[n]$ and $x \in I^n$. Then

$$ \frac{\|f\|_1}{\operatorname{dist}_1(f, \Sigma_{n,d}[n]_x)} \le \mathcal{C}_1(f, x) \le n(\mathbf{D}+1) \frac{\|f\|_1}{\operatorname{dist}_1(f, \Sigma_{n,d}[n]_x)} $$

where $\Sigma_{n,d}[n]_x := \{g \in \mathcal{P}_{n,d}[n] \mid g(x) = 0, \det D_x g = 0\}$, and

$$ \frac{\|f\|_1}{\operatorname{dist}_1(f, \Sigma_{n,d}[n])} \le \mathcal{C}_1(f) \le n(\mathbf{D}+1) \frac{\|f\|_1}{\operatorname{dist}_1(f, \Sigma_{n,d}[n])} $$

where $\Sigma_{n,d}[n] := \bigcup \{\Sigma_{n,d}[n]_x \mid x \in I^n\}$.

*Proof of Proposition 3.7.* By the 1st Lipschitz property, we have that $\frac{\|f\|_1}{\operatorname{dist}_1(f, \Sigma_{n,d}[n]_x)} \le \mathcal{C}_1(f, x)$. Now, let $A \in \mathbb{R}^{n \times n}$ be non-invertible, then $f - f(x) + (A - D_x f)X \in \Sigma_{n,d}[n]$, and so

$$ \operatorname{dist}_1(f, \Sigma_{n,d}[n]_x) \le \|f(x) + (A - D_x f)X\|_1 \\ \le \|f(x)\|_{\infty} + \|A - D_x f\|_{\infty, \infty} \le \|f(x)\|_{\infty} + \mathbf{D} \|\Delta^{-1}(A - D_x f)\|_{\infty, \infty}. $$

By minimizing over $\Delta^{-1}A$ non-invertible, we have that

$$ \operatorname{dist}_1(f, \Sigma_{n,d}[n]_x) \le \|f(x)\|_{\infty} + \mathbf{D} \operatorname{dist}_{\infty,\infty}(\Delta^{-1}D_x f, \Sigma^{n \times n}) $$

where $\Sigma^{n \times n}$ is the set of singular matrices. If we show that

$$ \operatorname{dist}_{\infty,\infty}(A, \Sigma^{n \times n}) = \min_{v \neq 0} \frac{\|Av\|_{\infty}}{\|v\|_{\infty}}, $$

then some easy estimates finish the proof. Now, since both sides are 1-Lipschitz on $A$ and the left-hand side is a distance, we automatically have that the left-hand side dominates the right-hand side. So we only need to show that $\min_{v \neq 0} \frac{\|Av\|_{\infty}}{\|v\|_{\infty}} \ge \operatorname{dist}_{\infty,\infty}(A, \Sigma^{n \times n})$.

Let $w$ be of $\infty$-norm one such that $\min_{v \neq 0} \|Av\|_{\infty}/\|v\|_{\infty} = \|Aw\|_{\infty}$. Now, let $a = \pm e_i$ be such that $a^T w = 1$, which exist by definition of the $\infty$-norm. Now, consider

$$ \tilde{A} = A - (Aw)a^T, $$

then $\tilde{A}w = 0$ and $\|\tilde{A} - A\|_{\infty,\infty} = \|(Aw)a^T\|_{\infty,\infty} = \|Aw\|_{\infty}$. Hence $\operatorname{dist}_{\infty,\infty}(A, \Sigma^{n \times n}) \le \|\tilde{A} - A\|_{\infty,\infty} = \min_{v \neq 0} \|Av\|_{\infty}/\|v\|_{\infty}$ as we wanted to show.

For the second part, we only maximize over the inequalities of the first part. $\square$
### 3.1.3 A normalized condition number for the 1-norm

The above condition number does not give the best estimates, the following variation is normalized to take advantage in the probabilistic computations.

**Definition 3.8.** Let $f \in \mathcal{P}_{n,d}[n]$. The local normalized condition number of $f$ at $x \in \mathbb{D}^n$ is

$$ \hat{\mathcal{C}}_1(f, x) := \frac{1}{\max\left\{\|\Delta^{-1}\hat{f}(x)\|_{\infty}, \|\mathrm{D}_x\hat{f}^{-1}\Delta^2\|_{\infty,\infty}^{-1}\right\}} $$

where $\hat{f} = (f_i/\|f_i\|_1)$, and the global normalized condition number of $f$ is

$$ \hat{\mathcal{C}}_1(f, x) := \max_{x \in I^n} \hat{\mathcal{C}}_1(f, x) $$

The following are the analogues of Theorems 3.6 and Proposition 3.7.

**Theorem 3.9.** Let $f \in \mathcal{P}_{n,d}[n]$ and $x \in I^n$. Then:

* **Normalization Effect:**

$$ \hat{\mathcal{C}}_1(f, x) \le \mathbf{D} \mathcal{C}_1(f, x) \quad \text{and} \quad \hat{\mathcal{C}}_1(f) \le \mathbf{D} \mathcal{C}_1(f). $$

* **Regularity inequality:** Either

$$ \|\Delta^{-1}\hat{f}(x)\|_{\infty} \ge \frac{1}{\hat{\mathcal{C}}_1(f, x)} \quad \text{or} \quad \|\mathrm{D}_x\hat{f}^{-1}\Delta^2\|_{\infty,\infty}^{-1} \ge \frac{1}{\hat{\mathcal{C}}_1(f, x)} $$

where $\hat{f} = (f_i/\|f_i\|_1)$. In particular, if $\hat{\mathcal{C}}_1(f, x) \|\hat{f}(x)\|_{\infty} < 1$, then $\mathrm{D}_x f$ is invertible.

* **1st Lipschitz inequality:**

$$ \left| \frac{1}{\hat{\mathcal{C}}_1(f, x)} - \frac{1}{\hat{\mathcal{C}}_1(g, x)} \right| \le \|\Delta^{-1}(\hat{f} - \hat{g})\|_1 \quad \text{and} \quad \left| \frac{1}{\hat{\mathcal{C}}_1(f)} - \frac{1}{\hat{\mathcal{C}}_1(g)} \right| \le \|\Delta^{-1}(\hat{f} - \hat{g})\|_1 $$

In particular, $\hat{\mathcal{C}}_1(f, x) \ge 1$.

* **2nd Lipschitz inequality:** The map

$$ \begin{gathered} \mathbb{D}^n \to [0, 1] \\ y \mapsto \frac{1}{\hat{\mathcal{C}}_1(f, y)} \end{gathered} $$

is 1-Lipschitz with respect to the $\infty$-norm.

* **Higher derivative estimate:** If $\mathcal{C}_1(f, x) \frac{\|f(x)\|_{\infty}}{\|f\|_1} < 1$, then

$$ \gamma_2(f, x) \le \frac{n(\mathbf{D} - 1)}{2} \hat{\mathcal{C}}_1(f, x). $$

□
**Proposition 3.10 (Normalized Condition Number Theorem).** Let $f \in \mathcal{P}_{n,d}[n]$, $x \in I^n$ and $\hat{f} = (f_i/\|f_i\|_1)$. Then

$$ \frac{1}{\mathrm{dist}_1(\hat{f}, \Sigma_{n,d}[n]_x)} \le \hat{\mathcal{C}}_1(f, x) \le n\mathbf{D}(\mathbf{D}+1) \frac{1}{\mathrm{dist}_1(f, \Sigma_{n,d}[n]_x)} $$

where $\Sigma_{n,d}[n]_x := \{g \in \mathcal{P}_{n,d}[n] | g(x) = 0, \det D_x g = 0\}$, and

$$ \frac{1}{\mathrm{dist}_1(\hat{f}, \Sigma_{n,d}[n])} \le \hat{\mathcal{C}}_1(f) \le n\mathbf{D}(\mathbf{D}+1) \frac{1}{\mathrm{dist}_1(\hat{f}, \Sigma_{n,d}[n])} $$

where $\Sigma_{n,d}[n] := \bigcup \{\Sigma_{n,d}[n]_x | x \in I^n\}$. $\square$

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

## 3.2 Condition numbers in $\mathbb{P}^n$

The present section will only recall some basic properties of the real condition number used in real numerical algebraic geometry [22, 25, 10, 11, 12] (cf. [18]). We will mainly follow the exposition in [63], since this is the nearest to the exposition used here.

### 3.2.1 The Weyl norm and some variational inequalities

The definition of the Weyl norm is standard.

**Definition 3.11.** Let $f \in \mathcal{H}_{n,d}[q]$. The Weyl norm of $f$ is the norm given by

$$ \|f\|_{\mathrm{W}} := \sqrt{\sum_{i=1}^{q} \sum_{|\alpha|=d_i} \left(\binom{d_i}{\alpha}\right)^{-1} |f_{i,\alpha}|^2}. $$

We denote by $\langle \cdot, \cdot \rangle_{\mathrm{W}}$ the associated inner product.

The main technical advantage of this norm is that it is orthogonally invariant. However, we note that this is not the only such norm, although it is the only norm that can be extended to a unitarily invariant norm in the space of complex polynomials.

**Proposition 3.12.** Let $f \in \mathcal{H}_{n,d}[q]$ and $u \in O(n+1)$. Then

$$ \|f^u\|_{\mathrm{W}} = \|f\|_{\mathrm{W}} $$

where $f^u := f(uX)$. $\square$

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

The following proposition is standard. Recall that by convention our representative $z \in \mathbb{P}^n$ satisfies $\|z\| = 1$.

**Proposition 3.13.** Let $f \in \mathcal{H}_{n,d}[q]$ and $\ell \ge 0$. For $v_1, \dots, v_\ell \in \mathbb{R}^n$,

$$ \|\Delta^{-\ell} \overline{\mathbb{D}}_X^\ell f(v_1, \dots, v_\ell)\|_{\mathrm{W}} \le \|f\|_{\mathrm{W}} \|v_1\| \cdots \|v_\ell\|, $$

and

$$ \left\| \frac{1}{\ell!} \overline{\mathbb{D}}_X^\ell f(v_1, \dots, v_\ell) \right\|_{\mathrm{W}} \le \binom{\mathbf{D}}{\ell} \|f\|_{\mathrm{W}} \|v_1\| \cdots \|v_\ell\|. $$

In particular, for $z \in \mathbb{P}^n$, $\left\| \frac{1}{\ell!} \overline{\mathbb{D}}_z^\ell f(v_1, \dots, v_\ell) \right\| \le \binom{\mathbf{D}}{\ell} \|f\|_{\mathrm{W}} \|v_1\| \cdots \|v_\ell\|$. $\square$

<figure><img src="image_7.png" /></figure>
The following proposition shows that the inequality above can be improved in the case where the vectors are in the tangent space. This stronger set of inequalities will be needed later on for our applications.

**Proposition 3.14.** Let $f \in \mathcal{H}_{n,d}[q]$ and $\ell \in \mathbb{N}$. For all $z \in \mathbb{P}^n$ and $v_1, \dots, v_\ell \in \mathbb{T}_z \mathbb{P}^n$,

$$ \left\| \frac{1}{\ell!} \bar{D}_x^\ell f(v_1, \dots, v_\ell) \right\| \le \sqrt{\binom{\mathbf{D}}{\ell}} \|f\|_{\mathbb{W}} \|v_1\| \cdots \|v_\ell\|. $$

*Proof of Proposition 3.14.* By the invariance, we can assume that $x = e_0$. We will prove the stronger claim that

$$ \sqrt{\sum_{j_1, \dots, j_\ell \in [n]} \left\| \frac{1}{\ell!} \bar{D}_{e_0}^\ell f(e_{j_1}, \dots, e_{j_\ell}) \right\|^2} \le \left\| \sqrt{\binom{\Delta}{\ell}} f \right\|_{\mathbb{W}} \quad (3.3) $$

where $\sqrt{\binom{\Delta}{\ell}}$ is the diagonal matrix with $\sqrt{\binom{d_i}{\ell}}$ in its entries. Note the left-hand side is the Frobenius norm of $\frac{1}{\ell!} \bar{D}_{e_0}^\ell f|_{\mathbb{T}_{e_0} \mathbb{P}^n \times \dots \times \mathbb{T}_{e_0} \mathbb{P}^n}$, so (3.3) implies the desired inequality for $v_1, \dots, v_\ell \in \mathbb{T}_{e_0} \mathbb{P}^n$.

By direct computation,

$$ \frac{1}{\ell!} \bar{D}_{e_0}^\ell f_i(e_{j_1}, \dots, e_{j_\ell}) = \left. \frac{\partial^\ell}{\partial X_{j_1} \dots \partial X_{j_\ell}} \right|_{x=e_0} f_i = \frac{\alpha_1! \cdots \alpha_\ell!}{\ell!} f_{i,\alpha} $$

with $\alpha_0 = d_i - \ell \alpha_k$ and $\alpha_k = \#\{s \mid j_s = k\}$ for $k > 0$. Now, we can easily see that the summand corresponding to $\alpha_1! \cdots \alpha_\ell! f_{i,\alpha}$ will appear $\frac{\ell!}{\alpha_1! \cdots \alpha_n!}$ times—to see this we only need the orbit-stabilizer formula—. Thus we have that

$$ \sqrt{\sum_{j_1, \dots, j_\ell \in [n]} \left\| \frac{1}{\ell!} \bar{D}_{e_0}^\ell f(e_{j_1}, \dots, e_{j_\ell}) \right\|^2} = \sqrt{\sum_{i=1}^q \frac{1}{\ell!} \sum_{|\alpha|=d_i} \prod_{k=1}^n \alpha_k! |f_{i,\alpha}|^2} \\ = \sqrt{\sum_{i=1}^q \frac{d_i!}{\ell!(d_i-\ell)!} \sum_{|\alpha|=d_i} \left(\binom{d_i}{\alpha}\right)^{-1} |f_{i,\alpha}|^2} \le \sqrt{\sum_{i=1}^q \binom{d_i}{\ell} \|f_i\|_{\mathbb{W}}^2}, $$

where the second equality follows from $\alpha_0 = d_i - \ell$. Now the claim is obvious. $\square$

We finish with a proposition stating several Lipschitz properties. Recall that $D_x f = \bar{D}_x f(\mathbb{I} - xx^*)$

**Proposition 3.15.** Let $f \in \mathcal{H}_{n,d}[q]$ and $\ell \in \mathbb{N}$. Then the map

$$ \mathbb{P}^n \to [0, 1] \\ z \mapsto \frac{1}{\|f\|_{\mathbb{W}}} \left\| \Delta^{-\ell} \bar{D}_x^\ell f \right\|_{2,2} $$

is $(\mathbf{D} - \ell)$-Lipschitz with respect to the geodesic norm on the codomain.

Moreover, the maps

$$ \mathbb{P}^n \to [0, 1] \\ z \mapsto \frac{1}{\|f\|_{\mathbb{W}}} \left\| \Delta^{-\frac{1}{2}} f(z) \right\| \quad \text{and} \\ \mathbb{P}^n \to [0, 1] \\ z \mapsto \frac{1}{\|f\|_{\mathbb{W}}} \left\| \Delta^{-1} D_z f \right\| $$

are, respectively, 1- and 2-Lipschitz with respect to the geodesic norm on the codomain.
*Proof.* The first part is proven as in the proof Proposition 3.4, but using Proposition 3.13 instead of Theorem 3.2. Note that some care has to be taken as we should consider a geodesic $t \mapsto x_t$ on $\mathbb{P}^n$.

Assume without loss of generality that $\|f\|_W = 1$ after re-scaling $f$. Take an arbitrary (unit-speed) geodesic $t \mapsto x_t \mathbb{P}^n$. We have, respectively, that

$$ \left| \frac{d}{dt} \left\| \Delta^{-\frac{1}{2}} f(x_t) \right\| \right| \le \left\| \Delta^{-\frac{1}{2}} \bar{D}_{x_t} f(\dot{x}_t) \right\| $$

and

$$ \left| \frac{d}{dt} \left\| \Delta^{-1} \mathrm{D}_{x_t} f \right\| \right| \le \left\| \Delta^{-1} \bar{\mathrm{D}}_{x_t}^2 f(\dot{x}_t)(\mathbb{I} - x_t x_t^*) - f(x_t) \dot{x}_t^* - \Delta^{-1} \mathrm{D}_{x_t} f(\dot{x}_t) x_t^* \right\|, $$

where we have used that $\bar{D}_{x_t} f(x_t) = \Delta f(x_t)$ by Euler's formula for homogeneous functions. To show our claim it is enough to bound the both right-hand sides by the respective Lipschitz constants.

On the one hand, by Proposition 3.14 applied to each component of $f$, we have $\|\Delta^{-\frac{1}{2}} \bar{D}_{x_t} f(\dot{x}_t)\| \le 1$. This shows the first claim of the second part.

On the other hand, by arguing as in Proposition 3.14 applied to each component of $f$, we have that $\|\Delta^{-1} \bar{D}_{x_t}^2 f(\dot{x}_t)(\mathbb{I} - x_t x_t^*) - f(x_t) \dot{x}_t^*\| \le \sqrt{3}$ and $\|\Delta^{-1} \mathrm{D}_{x_t} f(\dot{x}_t) x_t^*\| \le 1$. Now, $\|\Delta^{-1} \bar{D}_{x_t}^2 f(\dot{x}_t)(\mathbb{I} - x_t x_t^*)\| - f(x_t) \dot{x}_t^*$ and $f(x_t) \dot{x}_t^*$ have orthogonal kernel, so

$$ \begin{aligned} & \left\| \Delta^{-1} \bar{\mathrm{D}}_{x_t}^2 f(\dot{x}_t)(\mathbb{I} - x_t x_t^*) - f(x_t) \dot{x}_t^* - \Delta^{-1} \mathrm{D}_{x_t} f(\dot{x}_t) x_t^* \right\| \\ & = \sqrt{ \left\| \Delta^{-1} \bar{\mathrm{D}}_{x_t}^2 f(\dot{x}_t)(\mathbb{I} - x_t x_t^*) - f(x_t) \dot{x}_t^* \right\|^2 + \left\| \Delta^{-1} \mathrm{D}_{x_t} f(\dot{x}_t) x_t^* \right\|^2 } \end{aligned} $$

Hence the desired bound follows. $\square$

### 3.2.2 A condition number for the Weyl norm

We can now define a condition number and prove its properties. Recall that we assume that $x \in \mathbb{P}^n$ is represented $x \in \mathbb{C}^{n+1}$ with $\|x\| = 1$.

**Definition 3.16.** Let $f \in \mathcal{H}_{n,d}[n]$. The local condition number of $f$ at $x \in \mathbb{P}^n$ is

$$ \kappa_W(f, x) := \frac{\|f\|_W}{\sqrt{\|f(x)\|^2 + \sigma_n(\Delta^{-\frac{1}{2}} \mathrm{D}_x f)^2}}, $$

where $\sigma_n$ is the nth singular value and $\mathrm{D}_x f = \bar{\mathrm{D}}_x f(\mathbb{I} - xx^*)$, and the global condition number of $f$ is

$$ \kappa_W(f, x) := \max_{x \in \mathbb{P}^n} \kappa_W(f, x). $$

The following theorem showcases the main properties of the condition numbers defined above. It is analogous to [65, Theorem 4.2]. We define the following variants of Smale's $\gamma$:

$$ \gamma_T(f, x) := \sup_{k \ge 2} \left\| \mathrm{D}_x f^{-1} \frac{1}{k!} \bar{\mathrm{D}}_x^k f \left|_{(\mathrm{T}_x \mathbb{P}^n)^k} \right| \right\|^{\frac{1}{k-1}}, \quad (3.4) $$

and

$$ \bar{\gamma}_T(f, x) := \sup_{k \ge 2} \left\| \mathrm{D}_x f^{-1} \frac{1}{k!} \bar{\mathrm{D}}_x^k f \right\|^{\frac{1}{k-1}}. \quad (3.5) $$
**Theorem 3.17.** Let $f \in \mathcal{H}_{n,d}[n]$ and $x \in \mathbb{P}^n$. Then:

* **Regularity inequality:** Either

$$ \frac{\|f(x)\|}{\|f\|_W} \ge \frac{1}{\sqrt{2} \kappa_W(f, x)} \quad \text{or} \quad \frac{\sigma_n(\Delta^{-\frac{1}{2}} \mathrm{D}_x f)}{\|f\|_W} \ge \frac{1}{\sqrt{2} \kappa_W(f, x)}. $$

In particular, if $\sqrt{2} \kappa_W(f, x) \frac{\|f(x)\|}{\|f\|_W} < 1$, then $\mathrm{D}_x f$ is surjective.

* **1st Lipschitz inequality:** The maps

$$ \mathcal{H}_{n,d}[n] \to [0, \infty) \qquad \text{and} \qquad \mathcal{H}_{n,d}[n] \to [0, \infty) \\ g \mapsto \frac{\|g\|_W}{\kappa_W(g, x)} \qquad g \mapsto \frac{\|g\|_W}{\kappa_W(g)} $$

are 1-Lipschitz with respect to the 1-norm. In particular, $\kappa_W(f, x) \ge 1$.

* **2nd Lipschitz inequality:** The map

$$ \mathbb{P}^n \to [0, 1] \\ y \mapsto \frac{1}{\kappa_W(f, y)} $$

is $\min\{\sqrt{5\mathbf{D}}, \mathbf{D}\}$-Lipschitz with respect to the geodesic distance.

* **Higher derivative estimate:** If $\sqrt{2} \kappa_W(f, x) \frac{\|f(x)\|}{\|f\|_W} < 1$, then

$$ \gamma_T(f, x) \le \sqrt{\frac{\mathbf{D}-1}{2}} \kappa_W(f, x) \quad \text{and} \quad \bar{\gamma}(f, x) \le \frac{1}{2} \mathbf{D}^{\frac{3}{2}} \kappa_W(f, x). $$

* **Condition Number Theorem:** Let $\Sigma_{n,d}[n]_x := \{g \in \mathcal{H}_{n,d}[q] \mid g(x) = 0, \det \mathrm{D}_x g = 0\}$ and $\Sigma_{n,d}[n] := \bigcup \{\Sigma_{n,d}[n]_x \mid x \in \mathbb{P}^n\}$. Then

$$ \kappa_W(f, x) = \frac{\|f\|_W}{\mathrm{dist}_W(f, \Sigma_{n,d}[n]_x)} \quad \text{and} \quad \kappa_W(f) = \frac{\|f\|_W}{\mathrm{dist}_W(f, \Sigma_{n,d}[n])}. $$

*Proof.* All the parts are standard except the 2nd Lipschitz property and the inequality regarding $\gamma_T$. For the proof of the rest, we refer the reader to [63] for a detailed proof.

For the 2nd Lipschitz property, note that $x \mapsto 1/\kappa_W(f, x)$ is **D**-Lipschitz by [63, ]. Thus we only have to prove that this map is $\sqrt{5\mathbf{D}}$-Lipschitz. By Proposition 3.15, the maps $x \mapsto \|f(x)\|/\|f\|_W$ and $x \mapsto \sigma_q(\Delta^{-\frac{1}{2}}\mathrm{D}_x f)/\|f\|_W$ are respectively $\sqrt{\mathbf{D}}$ and $2\sqrt{\mathbf{D}}$-Lipschitz. Therefore the map $x \mapsto 1/\kappa_W(f, x) = \|(\|f(x)\|/\|f\|_W, \sigma_q(\Delta^{-\frac{1}{2}}\mathrm{D}_x f)/\|f\|_W)\|$ is $\sqrt{5\mathbf{D}}$-Lipschitz by the reverse triangle inequality.

For the higher derivative estimate for $\gamma_T$, we proceed as in [63] (cf. [14, §]). Assume without loss of generality that $\|f\|_W = 1$. We have that

$$ \left\| \mathrm{D}_x f^{-1} \frac{1}{k!} \bar{\mathrm{D}}_x^k f_{|(T_x \mathbb{P}^n)^k} \right\| \le \sqrt{2} \kappa_W(f, x) \left\| \frac{1}{k!} \Delta^{-\frac{1}{2}} \bar{\mathrm{D}}_x^k f_{|(T_x \mathbb{P}^n)^k} \right\| \quad (3.6) $$

by the regularity inequality. Now, by Proposition 3.14, the right-hand side is bounded by $\sqrt{\frac{1}{\mathbf{D}}(\bar{\mathbf{D}}_k)}$. The latter is bounded by $(\frac{\mathbf{D}-1}{2})^{\frac{k-1}{2}}$, which gives the desired bound. $\square$
### 3.2.3 A normalized condition number for the Weyl norm

We now define the normalized version. Again, recall that we assume that $x \in \mathbb{P}^n$ is represented $x \in \mathbb{C}^{n+1}$ with $\|x\| = 1$.

**Definition 3.18.** Let $f \in \mathcal{H}_{n,d}[n]$. The local normalized condition number of $f$ at $x \in \mathbb{P}^n$ is

$$ \hat{\kappa}_W(f, x) := \frac{\sqrt{n}}{\sqrt{\|\Delta^{-\frac{1}{2}}\hat{f}(x)\|^2 + \sigma_n(\Delta^{-1}\mathrm{D}_x\hat{f})^2}} $$

where $\hat{f} = (f_i/\|f_i\|_W)$, $\sigma_n$ is the nth singular value and $\mathrm{D}_x f = \bar{\mathrm{D}}_x f(\mathbb{I} - xx^*)$, and the global normalized condition number of $f$ is

$$ \hat{\kappa}_W(f, x) := \max_{x \in \mathbb{P}^n} \hat{\kappa}_W(f, x). $$

We now provide the analogues of Theorem 3.17, whose proof we omit.

**Theorem 3.19.** Let $f \in \mathcal{H}_{n,d}[n]$, $\hat{f} = (f_i/\|f_i\|_W)$ and $x \in \mathbb{P}^n$. Then:

* **Normalization Effect:**

$$ \hat{\kappa}_W(f, x) \le \sqrt{n\mathbf{D}} \kappa_W(f, x) \quad \text{and} \quad \hat{\kappa}_W(f) \le \sqrt{n\mathbf{D}} \kappa_W(f). $$

* **Regularity inequality:** Either

$$ \|\hat{f}(x)\| \ge \frac{1}{\sqrt{2} \hat{\kappa}_W(f, x)} \quad \text{or} \quad \sigma_n(\Delta^{-\frac{1}{2}} \mathrm{D}_x \hat{f}) \ge \frac{1}{\sqrt{2} \hat{\kappa}_W(f, x)} $$

In particular, if $\sqrt{2} \hat{\kappa}_W(f, x) \|\hat{f}(x)\| < 1$, then $\mathrm{D}_x f$ is invertible.

* **1st Lipschitz inequality:**

$$ \left| \frac{1}{\hat{\kappa}_W(f, x)} - \frac{1}{\hat{\kappa}_W(g, x)} \right| \le \left\| \Delta^{-\frac{1}{2}} (\hat{f} - \hat{g}) \right\|_{W} \quad \text{and} \quad \left| \frac{1}{\hat{\kappa}_W(f)} - \frac{1}{\hat{\kappa}_W(g)} \right| \le \left\| \Delta^{-\frac{1}{2}} (\hat{f} - \hat{g}) \right\|_{W} $$

In particular, $\hat{\kappa}_W(f, x) \ge 1$.

* **2nd Lipschitz inequality:** The map

$$ \begin{gathered} \mathbb{P}^n \to [0, 1] \\ y \mapsto \frac{1}{\hat{\kappa}_W(f, y)} \end{gathered} $$

is $\min\{\sqrt{5}, \sqrt{\mathbf{D}}\}$-Lipschitz with respect the geodesic distance.

* **Higher derivative estimate:** If $\sqrt{2} \hat{\kappa}_W(f, x) \|\hat{f}(x)\| < 1$, then

$$ \gamma_T(f, x) \le \sqrt{\frac{\mathbf{D} - 1}{2}} \hat{\kappa}_W(f, x) \quad \text{and} \quad \bar{\gamma}(f, x) \le \frac{1}{2} \mathbf{D}^{\frac{3}{2}} \hat{\kappa}_W(f, x). $$
• Normalized Condition Number Theorem: Let $\Sigma_{n,d}[n]_x := \{g \in \mathcal{H}_{n,d}[q] \mid g(x) = 0, \det D_x g = 0\}$ and $\Sigma_{n,d}[n] := \bigcup \{\Sigma_{n,d}[n]_x \mid x \in \mathbb{P}^n\}$. Then

$$ \frac{1}{\text{dist}_W(\hat{f}, \Sigma_{n,d}[n]_x)} \le \hat{\kappa}_W(f, x) \le \frac{\sqrt{n\mathbf{D}}}{\text{dist}_W(\hat{f}, \Sigma_{n,d}[n]_x)} $$

and

$$ \frac{1}{\text{dist}_W(\hat{f}, \Sigma_{n,d}[n])} \le \hat{\kappa}_W(f) \le \frac{\sqrt{n\mathbf{D}}}{\text{dist}_W(\hat{f}, \Sigma_{n,d}[n])} $$

□

# 4 Condition-based bounds I: Number of Zeros

We bound the number of zeros of a real polynomial system in terms of the condition number. For that, we combine the results in the two previous sections. In this section, we will rely mainly in Kantorovich's theory [28, §3.2], as it provides better bounds.

## 4.1 Bounds in $[-1, 1]^n$

To bound the number of zeros of $f \in \mathcal{P}_{n,d}[n]$, we will cover $I^n$ by rectangular boxes $a + P I^n$—with $a \in I^n$ and $P = \text{diag}(\rho)$ with $\rho \in (0, 1]^n$— where fast approximations by low-degree polynomials can happen. Because of this, the bound is divided in a local bound (Theorem 4.2) and cover construction (Proposition 4.7) that add up to the following global bound:

**Theorem 4.1.** Let $f \in \mathcal{P}_{n,d}[n]$. Then:

$$ \#\mathcal{Z}(f, [-1, 1]^n) \le (4.53+1.27\log D)^n \max\{13^n, 8^n(n-1)^n\log^n(2\mathbf{D}), 8^n\log^n \hat{C}_1(f)\}. \quad (4.1) $$

### 4.1.1 Bounds in $[-1, 1]^n$: Local bound

Given a rectangular box $a + P I^n$, we will consider the polynomial

$$ f_{a,\rho} := (f_i(a + PX)/\|f_i\|_1) \quad (a \in I^n, P = \text{diag}(\rho), \rho \in (0,1]^n) \quad (4.2) $$

to which we want to apply Proposition 2.5. The following lemma imposes technical conditions on $a$ and $P = \text{diag}(\rho)$ for this to be possible.

**Theorem 4.2.** Let $f \in \mathcal{P}_{n,d}[n]$, $a \in I^n$, $\rho \in [\frac{1}{4\mathbf{D}}, \frac{1}{2}]^n$. If

$$ \text{for all } i, \text{ either } 2|\rho_i| \le 1 - |a_i| \text{ or } |\rho_i| \le \frac{1}{2\mathbf{D}}, \quad (4.3) $$

then

$$ \#(\mathcal{Z}(f) \cap (a + P I^n) \cap I^n) \le \delta_1^n = \max\{13^n, 8^n(n-1)^n\log^n(2\mathbf{D}), 8^n\log^n \hat{C}_1(f)\}, $$

where $P := \text{diag}(\rho)$.

To prove this local bound, we will use the following lemma and Kantorovich's theorem. Recall that for $g \in \mathcal{P}_{n,d}[n]$, $x \in \mathbb{C}^n$ and $r > 0$, we have

$$ \beta_{\infty}(g, x) := \|D_x g^{-1} g(x)\|_{\infty} \quad \text{and} \quad K_{\infty}(f, x, r) := \sup_{\|y-x\| \le r} \|D_x g^{-1} D_y^2 g\|_{\infty, \infty}. $$
**Lemma 4.3.** Let $f \in \mathcal{P}_{n,d}[q]$, $a \in I^n$, and $\rho \in (0,1]^n$. If (4.3), then for $\ell \in \mathbb{N}$,

$$ \left\| \frac{2^\ell}{\ell!} \mathrm{D}_0^k f_{a,\rho} \right\|_{\infty,\infty} \le \binom{\mathbf{D}+n-1}{n-1} \le \left(1+\frac{2\ln(n-1)}{n-1}\mathbf{D}\right)^{n-1}. $$

**Theorem 4.4 (Kantorovich's theory for $\infty$-norm).** [28, Théorèmes 85 et 88]. Let $g \in \mathcal{P}_{n,d}[n]$.

(K1) Let $\zeta \in \mathbb{C}^n$ and $r > 0$. If $\zeta$ is a zero of $f$ and $2K_\infty(g, \zeta, r) \le 1$, then $\bar{B}(\zeta, r)$ does not contain any other zero of $g$.

(K2) Let $x \in \mathbb{C}^n$ and $r > 0$. If

a) $D_x g$ is non-singular,

b) $2\beta_\infty(g, x) \le r$, and

c) $2\beta_\infty(g, x)K_\infty(g, x, r) \le 1$,

then $B_\infty(x, r)$ contains a zero of $g$. Moreover, if $g$ is real and $x$ is real, so it is the zero in $B_\infty(x, r)$. $\square$

*Proof of Theorem 4.2.* Without loss of generality, assume that $\|f_i\|_1 = 1$ so that $\hat{f} = f$. Let $g = f_{a,\rho} = f(a+Px)$ where $P = \mathrm{diag}(\rho)$. As a consequence we will have by the chain rule,

$$ D_x g = D_{a+Px} f \quad \text{and} \quad D_x^2 g = D_{a+Px} f \circ (P \otimes P). \qquad (4.4) $$

Let $\zeta_1, \dots, \zeta_a$ be the zeros of $f$ in $(a+PD^n) \cap I^n$. These zeros correspond to zeros $\eta_1, \dots, \eta_r$ of $g$ in $I^n$. Note that $\eta_i$ Now, consider

$$ r := \frac{1}{4e\mathbf{D}\hat{\mathcal{C}}_1(f)} \le \frac{1}{\mathbf{D}}. $$

We have that

$$ 2K_\infty(g, \eta_i, r)r \le \frac{1}{2}. \qquad (4.5) $$

To see this inequality, we argue as follows:

$$ \begin{align} K_\infty(g, \eta_i, r) &\le \|D_{\eta_i} g^{-1} \Delta^2\|_{\infty,\infty} \sup_{\|x-\eta_i\|_\infty \le r} \|\Delta^{-2} D_x^2 g\|_{\infty,\infty} \nonumber \\ &\le \mathbf{D} \|D_{\zeta_i} f^{-1} \Delta^2\|_{\infty,\infty} \sup_{\|x-\eta_i\|_\infty \le r} \|\Delta^{-2} D_{a+Px}^2 f\|_{\infty,\infty} \tag{4.4} \\ &\le \mathbf{D} \hat{\mathcal{C}}_1(f) \sup_{\|x-\eta_i\|_\infty \le r} \|\Delta^{-2} D_{a+Px}^2 f\|_{\infty,\infty} \nonumber \\ &\le \mathbf{D} \hat{\mathcal{C}}_1(f) \sup_{\|x\|_\infty \le 1+1/\mathbf{D}} \|\Delta^{-2} D_x^2 f\|_{\infty,\infty} \nonumber \\ &\le e \mathbf{D} \hat{\mathcal{C}}_1(f) \tag{Prop. 3.3} \end{align} $$

where we used that $\|a+Px\|_\infty \le \|a+P\eta_i\|_\infty + \|P(x-\eta_i)\|_\infty \le 1+\varepsilon + \|\rho\|_\infty r \le 1+\frac{1}{\mathbf{D}}$ in the 4th line.

In this way, by Theorem 4.4(K1) and (4.5), we have that the $\mathbb{B}_\infty(\eta_i, r)$ are disjoint. Hence, to show the desired bound, it is enough to show that for appropriately chosen $\delta \ge 1$, $g|_\delta$, which has at most $\delta^n$ zeros, has a zero in each $\mathbb{B}(\eta_i, r)$. For this, we will need to use Theorem 4.4(K2).
Fix $\eta_i$. We have that for all $k \ge 0$,

$$
\begin{align}
\left\| D_{\eta_i} g^{-1} \frac{2^k}{k!} D_0^k g \right\|_{\infty, \infty}
&\le \left\| D_{\eta_i} g^{-1} \Delta^2 \right\|_{\infty, \infty} \left\| \Delta^{-2} \frac{2^k}{k!} D_0^k g \right\|_{\infty, \infty} \nonumber \\
&\le 4 \mathbf{D} \left\| D_{\zeta_i} f^{-1} \Delta^2 \right\|_{\infty, \infty} \left\| \Delta^{-2} \frac{2^k}{k!} D_0^k g \right\|_{\infty, \infty} \tag{4.4} \\
&\le 4 \mathbf{D} \hat{c}_1(f) \left\| \Delta^{-2} \frac{2^k}{k!} D_0^k g \right\|_{\infty, \infty} \nonumber \\
&\le \frac{4}{\mathbf{D}} \binom{\mathbf{D} + n - 1}{n - 1} \hat{c}_1(f) \nonumber
\end{align}
$$

(Lemma 4.3)

To improve the bound in Lemma 4.3 by $\mathbf{D}^2$, we use the fact that each $f_i$ is divided by $d_i^2$.
In this way, if

$$
\delta - 2 \log(\delta + 2) \geq \log \hat{c}_1(f) + 3 + \max\{0, n - 2\} \log(2\mathbf{D}), \quad (4.6)
$$

then

$$
\delta - 2 \log(\delta + 2) \geq 1 + \tau(g, \eta_i; \delta), \quad (4.7)
$$

and so, by Theorem 2.7, $D_{\zeta} g|_{\delta}$ is invertible and

$$
\beta_{\infty}(g|_{\delta}, \eta_i) \le \frac{1}{2^{\delta-1}} \tau(g, \eta_i; \delta) \le \frac{1}{2^{\delta-1}} \frac{4}{\mathbf{D}} \binom{\mathbf{D}+n-1}{n-1} \hat{c}_1(f), \quad (4.8)
$$

and, by Proposition 2.13 and (4.5),

$$
K_{\infty}(g|_{\delta}, \eta_i, r) \le 2(K(f, \eta_i, r) + 1) \le 2/r = 8e \mathbf{D} \hat{c}_1(f). \quad (4.9)
$$

Hence we have that if

$$
\frac{1}{2^{\delta-1}} 32 \binom{\mathbf{D} + n - 1}{n - 1} \hat{c}_1(f)^2 \le 1,
$$

then we can apply Theorem 4.4 (K2) and are done. If $t \ge 13$, then $\frac{3}{4}t \ge 2\log(t+2)+\log e$.
Thus we only need to take

$$
\delta = \max\{13, 8(n-1)\log(2\mathbf{D}), 8\log \hat{c}_1(f)\}
$$

to get the desired bound.

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

Proof of Lemma 4.3. Without loss of generality, assume that $\|f_i\|_1 = 1$ for all $i$, after
scaling each component of $f$. Since, by definition,

$$
\left\| \frac{2^\ell}{\ell!} D_0^k f_{a,\rho} \right\|_{\infty,\infty} = \max_i \left\| \frac{2^\ell}{\ell!} D_0^k (f_i(a + PX)) \right\|_{\infty,\infty},
$$

it is enough to prove our claim for the case $q = 1$. Also, we will assume without loss of
generality, $a \ge 0$.

Arguing as in Lemma 2.2,

$$
\begin{align*}
\frac{2^\ell}{\ell!} D_0^k f_{a,\rho}(v_1, \dots, v_\ell) &= \sum_{k=\ell}^{\mathbf{D}} \binom{k}{\ell} \frac{2^\ell}{k!} D_0^k f(\underbrace{a, \dots, a}_{k-\ell \text{ times}}, P v_1, \dots, P v_\ell) \\
&= \sum_{k=\ell}^{\mathbf{D}} \binom{k}{\ell} \sum_{r_1, \dots, r_{k-\ell} \atop s_1, \dots, s_\ell} \frac{2^\ell}{k!} D_0^k f(e_{r_1}, \dots, e_{r_{k-\ell}}, e_{s_1}, \dots, e_{s_\ell}) \prod_{i=1}^{k-\ell} a_{r_i} \prod_{j=1}^{\ell} \rho_{s_j} v_j^{s_j}
\end{align*}
$$
where $a_{r_i}$ is the $r_i$th component of $a$ and $v_j^{s_j}$ the $s_j$th component of $v_j$. Choose $v_1, \dots, v_\ell$ of $\infty$-norm 1, so that

$$ \left| \frac{2^\ell}{\ell!} D_0^k f_{a,\rho}(v_1, \dots, v_\ell) \right| = \left\| \frac{2^\ell}{\ell!} D_0^k f_{a,\rho} \right\|_{\infty,\infty}. $$

So, by the triangle inequality,

$$ \left\| \frac{2^\ell}{\ell!} D_0^k f_{a,\rho} \right\|_{\infty,\infty} \le \sum_{k=\ell}^{\mathbf{D}} \binom{k}{\ell} \sum_{\substack{r_1, \dots, r_{k-\ell} \\ s_1, \dots, s_\ell}} \left| \frac{2^\ell}{k!} D_0^k f(e_{r_1}, \dots, e_{r_{k-\ell}}, e_{s_1}, \dots, e_{s_\ell}) \right| \prod_{i=1}^{k-\ell} a_{r_i} \prod_{j=1}^{\ell} \rho_{s_j}. $$

If we let $\alpha, \beta \in \mathbb{N}^n$ be given by

$$ \alpha_t := \#\{i \mid r_i = t\} \text{ and } \beta_t := \#\{j \mid s_j = t\}, $$

then we have that

$$ \left| \frac{2^\ell}{k!} D_0^k f(e_{r_1}, \dots, e_{r_{k-\ell}}, e_{s_1}, \dots, e_{s_\ell}) \right| \prod_{i=1}^{k-\ell} a^{r_i} \prod_{j=1}^{\ell} \rho_{s_j} = 2^\ell \binom{k}{\alpha+\beta}^{-1} |f_{\alpha+\beta}| a^\alpha \rho^\beta. $$

Each one of the terms on the right-hand side appears $\binom{k-\ell}{\alpha} \binom{\ell}{\rho}$ times. Therefore we get

$$ \begin{aligned} \left\| \frac{2^\ell}{\ell!} D_0^k f_{a,\rho} \right\|_{\infty,\infty} &\le \sum_{k=\ell}^{\mathbf{D}} \sum_{\substack{\|\alpha\|_1=k-\ell \\ \|\beta a \beta\|_1=\ell}} 2^\ell \frac{(\alpha+\beta)!}{\alpha!\beta!} |f_{\alpha+\beta}| a^\alpha \rho^\beta \\ &= \sum_{k=\ell}^{\mathbf{D}} \sum_{\substack{\|\alpha\|_1=k-\ell \\ \|\beta a \beta\|_1=\ell}} |f_{\alpha+\beta}| \prod_{i=1}^n \left( \binom{\alpha_i + \beta_i}{\alpha_i} a_i^{\alpha_i} (2\rho_i)^{\beta_i} \right). \end{aligned} $$

By assumption, either $2\rho_i \le 1 - a_i$, and so

$$ \binom{\alpha_i + \beta_i}{\alpha_i} a_i^{\alpha_i} (2\rho_i)^{\beta_i} \le \binom{\alpha_i + \beta_i}{\alpha_i} a_i^{\alpha_i} (1 - a_i)^{\beta_i} \le \sum_{t=0}^{\alpha_i + \beta_i} \binom{\alpha_i + \beta_i}{t} a_i^t (1 - a_i)^{\alpha_i + \beta_i - t} = 1; $$

or $\rho_i \le 1/(2\mathbf{D})$, and so

$$ \binom{\alpha_i + \beta_i}{\alpha_i} a_i^{\alpha_i} (2\rho_i)^{\beta_i} \le \binom{\alpha_i + \beta_i}{\alpha_i} \mathbf{D}^{-\beta_i} = \binom{\alpha_i + \beta_i}{\beta_i} \mathbf{D}^{-\beta_i} \le \binom{\mathbf{D}}{\beta_i} \mathbf{D}^{-\beta_i} \le \frac{1}{\beta_i!} \le 1. $$

Hence, in either case,

$$ \binom{\alpha_i + \beta_i}{\alpha_i} a_i^{\alpha_i} (2\rho_i)^{\beta_i} \le 1, $$

and so

$$ \left\| \frac{2^\ell}{\ell!} D_0^k f_{a,\rho} \right\|_{\infty,\infty} \le \sum_{k=\ell}^{\mathbf{D}} \sum_{\substack{\|\alpha\|_1=k-\ell \\ \|\beta\|_1=\ell}} |f_{\alpha+\beta}|. $$
The summand $|f_{\alpha+\beta}|$ appears at most $\binom{\ell+n-1}{n-1}$ times—note that $\binom{\ell+n-1}{n-1}$ is the number of $\beta \in \mathbb{N}^n$ so that $\|\beta\|_1 = \ell$. Thus we conclude that

$$ \left\| \frac{2^\ell}{\ell!} \mathrm{D}_0^k f_{a,\rho} \right\|_{\infty,\infty} \le \binom{\mathbf{D}+n-1}{n-1}. $$

By the arithmetic-geometric inequality and $\sum_{i=1}^{n-1} i^{-1} \le 2 \ln(n-1)$, we have that

$$ \binom{\mathbf{D}+n-1}{n-1} = \prod_{i=1}^{n-1} \left( \frac{\mathbf{D}}{i} + 1 \right) \le \left( \frac{\sum_{i=1}^{n-1} i}{n-1} \mathbf{D} + 1 \right)^{n-1} \le \left( \frac{2 \ln(n-1)}{n-1} \mathbf{D} + 1 \right)^{n-1}, $$

which is the remaining inequality to show. $\square$

### 4.1.2 Bounds in $[-1, 1]^n$: Cover Construction

We consider the following cover which generalizes the construction of Moroz [55, 3.2] to higher dimensions.

**Definition 4.5.** A Moroz cover of degree $\mathbf{D}$ for $I^n$ is a cover of $I^n$ by rectangular boxes so that each box $a + \mathrm{diag}(\rho)I^n$ in the cover satisfies (4.3).

**Remark 4.6.** Note that for a Moroz cover, we can apply Proposition 4.2 at each element.

The following proposition shows that this the Moroz subdivision is indeed a subdivision.

**Proposition 4.7.** There is a Moroz cover of degree $\mathbf{D}$ for $I^n$ of size $(4.53 + 1.27 \log \mathbf{D})^n$.

*Proof.* Consider the cover given by

$$ \{a_{k,\mathbf{D}} + \mathrm{diag}(\rho_{k,\mathbf{D}})I^n \mid k \in \mathbb{Z}^n \cap [-\lceil \log(4D)/\log(3) \rceil, \lceil \log(4D)/\log(3) \rceil]\} $$

where

$$ a_{k,\mathbf{D}} := \left( \mathrm{sgn}(k_i) \left(1 - \frac{1}{3^{k_i}}\right) \right) \in I^n \quad \text{and} \quad (\rho_{k,\mathbf{D}})_i := \begin{cases} \frac{1}{2} \frac{1}{3^{k_i}}, & \text{if } |k_i| < \frac{\log(4\mathbf{D})}{\log(3)} \\ \frac{1}{4\mathbf{D}}, & \text{otherwise} \end{cases}. $$

One can easily check that this is a Moroz cover of degree $\mathbf{D}$ for $I^n$. Note that it is enough to show the claim for the one-dimensional case, since the multi-dimensional version of this cover is the one-dimensional version tensorized. $\square$

## 4.2 Bounds in $\mathbb{P}^n$

To bound the number of zeros of $f \in \mathcal{H}_{n,d}[n]$, we will cover $\mathbb{P}^n$ by a cover of geodesic balls where fast approximation by low-degree polynomials can happen. Because of this, the bound is divided in a local bound (Theorem 4.9) and a cover construction (Proposition 4.11) that add up to the following global bound:

**Theorem 4.8.** Let $f \in \mathcal{H}_{n,d}[n]$. Then:

$$ \mathcal{Z}(f, \mathbb{P}^n) \le \frac{3}{2} 3^n \mathbf{D}^{\frac{n}{2}} \max\{13^n, 3^n \log^n \mathbf{D}, 8^n \log^n \hat{\kappa}_W(f)\}. $$
### 4.2.1 Bounds in $\mathbb{P}^n$: Local bound

We will bound the number of real zeros in a geodesic ball $B_P(a, \rho)$.

**Theorem 4.9.** Let $f \in \mathcal{H}_{n,d}[n]$, $a \in \mathbb{P}^n$ and $\rho \in (0, \arctan \frac{1}{\sqrt{D}}]$. Then
$$ \#\mathcal{Z}(f, \mathbb{B}_P(a, \rho)) \le \delta_W^n = \max\{13^n, 3^n \log^n \mathbf{D}, 8^n \log^n \hat{\kappa}_W(f)\} $$

**Theorem 4.10 (Kantorovich's theory for 2-norm).** [28, Théorèmes 85 et 88]. Let $g \in \mathcal{P}_{n,d}[n]$.

(K1) Let $\zeta \in \mathbb{C}^n$ and $r > 0$. If $\zeta$ is a zero of $f$ and $2K_2(g, \zeta, r) \le 1$, then $\bar{B}_2(\zeta, r)$ does not contain any other zero of $g$.

(K2) Let $x \in \mathbb{C}^n$ and $r > 0$. If

a) $D_x g$ is non-singular,

b) $2\beta_2(g, x) \le r$, and

c) $2\beta_2(g, x)K_2(g, x, r) \le 1$,

then $B_2(x, r)$ contains a zero of $g$. Moreover, if $g$ is real and $x$ is real, so it is the zero in $B_2(x, r)$. $\square$

*Proof of Theorem 4.2.* Without loss of generality, as all the relevant invariant are othogonally invariant, we can assume that $a = e_0$. Moreover, we can also assume $\hat{f} = f$ and that $\rho = \arctan(1/\sqrt{D})$. Hence the central projection map $\text{IO}: \mathbb{R}^n \to \mathbb{P}^n$ given by

$$ \text{IO}(x) := \frac{1}{\sqrt{1 + \|x\|}} \begin{pmatrix} 1 \\ x \end{pmatrix} \qquad (4.10) $$

establishes a bijection between $B_2(0, \tan \rho)$ and $\mathbb{B}_P(e_0, \rho)$ for $\rho < \pi/2$. Moreover, observe that the map

$$ x \mapsto \text{IO}_{\rho}(x) := \text{IO}((\tan \rho)x) $$

establishes a bijection between $B_2$ and $\mathbb{B}_P(e_0, \rho)$ and that we have

$$ \#\mathcal{Z}(f, \mathbb{B}_P(e_0, \rho)) = \#\mathcal{Z}(g, B_2(0, 1)) $$

where $g \in \mathcal{P}_{n,d}[n]$ is the polynomial given by

$$ g(X) = \sum_{k=0}^{\mathbf{D}} \frac{\tan^k \rho}{k!} \bar{D}_{e_0}^k f \left( \begin{pmatrix} 0 \\ X \end{pmatrix}, \dots, \begin{pmatrix} 0 \\ X \end{pmatrix} \right). $$

Denote by $\eta_i$ the zeros of $g$ in $B_2$ and by $\zeta_i$ the corresponding zeros of $f$ in $\mathbb{B}_P(e_0, \rho)$. Observe that $g$ satisfies the following properties:

(p1) For all $x \in B_2(0, 1)$,

$$ g(x) = f \left( \begin{pmatrix} 1 \\ (\tan \rho)x \end{pmatrix} \right) = (1 + \|x\|^2 \tan^2 \rho)^{\frac{\Delta}{2}} f(\text{IO}_{\rho}(x)). $$
(p2) For all $x \in B_2(0, 1)$,

$$D_x^2 g = (\tan^2 \rho) \overline{D}^2 \begin{pmatrix} 1 \\ (\tan \rho)x \end{pmatrix} f = (\tan^2 \rho)(1 + \|x\|^2 \tan^2 \rho)^{\frac{\Delta}{2}-1} \overline{D}_{\text{IO}_\rho(x)}^2 f.$$

(p3) For all $k \in \mathbb{N}$,

$$\frac{1}{k!} D_0^k g = \frac{\tan^k \rho}{k!} \overline{D}^k f|_{T_{e_0} \mathbb{P}}.$$

(p4) For all $i$,

$$\zeta_i = \text{IO}_\rho(\eta_i).$$

Moreover,

$$D_{\eta_i} g = (1 + \|\eta_i\|^2 \tan^2 \rho)^{\frac{\Delta}{2}} D_{\zeta_i} f D_{\eta_i} \text{IO}_\rho.$$

Now, by the chain rule and [47, Appendix 2], we have that the singular values of $D_{\eta_i} \text{IO}_\rho$ are

$$\frac{\tan \rho}{1 + \|\eta_i\|^2 \tan^2 \rho}, \frac{\tan \rho}{\sqrt{1 + \|\eta_i\|^2 \tan^2 \rho}}, \dots, \frac{\tan \rho}{\sqrt{1 + \|\eta_i\|^2 \tan \rho}},$$

which lie in the interval $[\frac{1}{2} \tan \rho, \tan \rho]$.

Now, let

$$r = \frac{\tan \rho}{4\mathbf{D} \hat{\kappa}_W(f)}.$$

For this choice, we have that

$$2K_2(g, \eta_i, r)r \leq \frac{1}{2}. \qquad (4.11)$$

To see this inequality, we argue as follows:

$$
\begin{align*}
K_2(g, \eta_i, r) & \le \left\| D_{\eta_i} g^{-1} \Delta (1 + \|x\|^2 \tan^2 \rho)^{\frac{\Delta}{2}} \right\| \sup_{\|x-\eta_i\| \le r} \left\| (1 + \|x\|^2 \tan^2 \rho)^{-\frac{\Delta}{2}} \Delta^{-1} D_x^2 g \right\| \\
& \le \left\| D_{\eta_i} \text{IO}^{-1} D_{\zeta_i} f^{-1} \Delta \right\| \sup_{\|x-\eta_i\| \le r} \frac{\left\| \Delta^{-1} \overline{D}_{\text{IO}_\rho(x)}^2 f \right\|}{1 + \|x\|^2 \tan^2 \rho} \tag{p2\&p4} \\
& \le \left\| D_{\eta_i} \text{IO}^{-1} D_{\zeta_i} f^{-1} \Delta \right\| \sup_{z \in \mathbb{P}^n} \left\| \Delta^{-1} \overline{D}_z^2 f \right\| \\
& \le \left\| D_{\eta_i} \text{IO}^{-1} D_{\zeta_i} f^{-1} \Delta \right\| (\mathbf{D} - 1) \tag{Prop. 3.13} \\
& \le \frac{2(\mathbf{D} - 1)}{\tan \rho} \left\| D_{\eta_i} \text{IO}^{-1} D_{\zeta_i} f^{-1} \Delta \right\| \\
& \le \frac{2(\mathbf{D} - 1)}{\tan \rho} \hat{\kappa}_W(f).
\end{align*}
$$

Hence, by Theorem 4.10 (K1), the $\mathbb{B}_2(\eta_i, r)$ are disjoint. In this way, to show the desired bound, we only have to choose appropriate $\delta \ge 1$ such that $g|_\delta$, which has at most $\delta^n$ zeros, has a zero in each $\mathbb{B}_2(\eta_i, r)$. For this, we will use Theorem 4.10 (K2).
Now, for each $k \ge 0$, we have

$$
\begin{align*}
\|D_{\eta_i} g^{-1} \frac{2^k}{k!} D_0^k g\| &\le \|D_{\eta_i} g^{-1} \Delta\| \|\Delta^{-2} \frac{2^k}{k!} D_0^k g\| \\
&\le \frac{2}{\tan \rho} \|D_{\zeta_i} f \Delta\| \|\Delta^{-2} \frac{2^k}{k!} D_0^k g\| \tag{p4} \\
&\le \frac{2}{\tan \rho} \hat{\kappa}_W(f) \|\Delta^{-1} \frac{2^k}{k!} D_0^k g\| \\
&\le \frac{2}{\tan \rho} \hat{\kappa}_W(f) \tan^k \rho \|\Delta^{-1} \frac{2^k}{k!} \bar{D}_{e_0}^k f_{|T_{e_0} \mathbb{P}^n}\| \tag{p3} \\
&\le 2^{k+1} \tan^{k-1} \rho \frac{1}{\bar{D}} \sqrt{\binom{\mathbf{D}}{k!}} \hat{\kappa}_W(f) \tag{Prop. 3.14} \\
&\le \frac{2^{k+1}}{\sqrt{k!}} \left(\sqrt{\mathbf{D}} - 1 \tan \rho\right)^{k-1} \\
&\le \frac{2^{k+1}}{\sqrt{k!}} \tag{tan $\rho \le 1/\sqrt{\mathbf{D}}$}
\end{align*}
$$

Hence, if $\delta \ge 13$ and

$$
\delta - 2 \log(\delta + 2) \ge \log \hat{\kappa}_W(f), \quad (4.12)
$$

then

$$
\delta - 2 \log(\delta + 2) \ge 1 + \tau(g, \eta_i; \delta), \quad (4.13)
$$

and so, by Theorem 2.7, $D_{\zeta}g|_{\delta}$ is invertible and

$$
\beta_{\infty}(g|_{\delta}, \eta_i) \le \frac{1}{2^{\delta-1}} \tau(g, \eta_i; \delta) \le \frac{1}{2^{\delta+1}} \hat{\kappa}_W(f), \quad (4.14)
$$

and, by Proposition 2.13 and (4.11),

$$
K_{\infty}(g|_{\delta}, \eta_i, r) \le 2(K(f, \eta_i, r) + 1) \le 2/r = \frac{8\mathbf{D}}{\tan \rho} \hat{\kappa}_W(f). \quad (4.15)
$$

Hence, to apply Theorem 4.10 (K2), we need that

$$
\frac{1}{2^{\delta}} \frac{4\mathbf{D}}{\tan \rho} \hat{\kappa}_{W}(f)^{2} \leq 1.
$$

Therefore, by our assumption of $\rho$, it is enough to take

$$
\delta = \max\{13, 3 \log \mathbf{D}, 8 \log \hat{\kappa}_W(f)\}
$$

to get the desired bound.

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

4.2.2 Bounds in $\mathbb{P}^n$: Cover construction

We only need to construct a cover by geodesic balls of radius $1/\sqrt{\bar{D}}$ of $\mathbb{P}^n$. The following
result is standard.

**Proposition 4.11.** Let $\delta \in (0, \pi/3)$. Then there is a finite set $\mathcal{N}_{\delta} \subseteq \mathbb{P}^n$ such that

$$
\{\mathbb{B}_{\mathbb{P}}(a, \delta) \mid a \in \mathcal{N}_{\delta}\}
$$

is a cover of $\mathbb{P}^n$ and such that

$$
\# \mathcal{N}_{\delta} \le \frac{3}{2} \left( \frac{3}{\delta} \right)^n .
$$

*Proof.* See [66, §4.2] (and [63, Prop. 2§20]) for detailed proof with the estimates). $\square$

<figure><img src="image_10.png" /></figure>
# 5 Probabilistic bounds I: Number of Zeros

We provide a probabilistic analysis for zintzo random polynomials, introduced in [64], and dobro random polynomials, introduced in [21]. Let us recall the main probabilistic notions that we will use:

**Definition 5.1.** Let $\mathfrak{x} \in \mathbb{R}$ be a random variable and $p \ge 1$. Then:

1. $\mathfrak{x}$ has anticoncentration if there is some $\rho > 0$ such that for all $\varepsilon, x \in \mathbb{R}$, $P(|\mathfrak{x} - x| < \varepsilon) < 2\rho\varepsilon$. The smallest such $\rho$ is called the anticoncentration constant of $\mathfrak{x}$.

2. $\mathfrak{x}$ is p-subexponential (subgaussian if $p \ge 0$) if there is some $L > 0$ such that for all $t \ge L$, $P(|\mathfrak{x}| \ge t) \le e^{-t^p/L^p}$. The smallest such constant is called the p-subexponential constant of $\mathfrak{x}$. When $p = 2$, we simply say that $\mathfrak{x}$ is subgaussian and talked about the subgaussian constant of $\mathfrak{x}$.

## 5.1 Zintzo Random Polynomial Systems

Zintzo random polynomials where introduced in [65] (cf. [64]) modelling a robust probabilistic model of polynomials. The condition in the support is similar to that of [59].

**Definition 5.2.** Let $p \ge 1$ and $M_1, \dots, M_n \subseteq \mathbb{N}^n$ finite sets such that

$$0, e_1, \dots, e_n M_i \qquad (5.1)$$

where the $e_i$ are the canonical vectors. A p-zintzo random polynomial system supported on $M_1, \dots, M_n$ is a random polynomial system $f \in \mathcal{P}_{n,d}[n]$ with

$$f_i = \sum_{\alpha \in M_i} f_{i,\alpha} X^{\alpha} \quad (i \in \{1, \dots, n\}),$$

such that the coefficients $f_\alpha$ are independent p-subexponential random variables with the anti-concentration property.

Given a p-zintzo random polynomial system $f \in \mathcal{P}_{n,d}[n]$, we define the following quantities:

1. The tail constants of $f$ given by

$$L_f := \max_i \sum_{\alpha \in M_i} L_{i,\alpha}, \qquad (5.2)$$

where $L_{i,\alpha}$ is the p-subexponential constant of $f_{i,\alpha}$.

2. The anti-concentration constant of $f$ given by

$$\rho_f := \max_{k,l} \rho_{i,(d_i-1)e_k+e_l} \qquad (5.3)$$

where $\rho_{i,\alpha}$ is the anti-concentration constant of $f_{i,\alpha}$.

It is important to note that Kac polynomial systems and polynomials with noise given by Kac random polynomials are zintzo random polynomial systems.

**Proposition 5.3.** Let $f \in \mathcal{P}_{n,d}[q]$ be a random polynomial system with supports $M_1, \dots, M_q$ satisfying (5.1). The following holds:
(g) If the coefficients of $f$ are independent normal variables of mean contained in $[-R, R]$ and variance at least $\sigma_0^2$ and at most $\sigma_1^2$, then $L_{f,i} = \max\{R, 2\sigma_1\} \max_i |M_i|$ and $\rho_{f,i} = (2\pi)^{-1/2}\sigma_0^{-1}$. Moreover, if all coefficients are standard normal variables, then $f$ is a 2-zintzo random polynomial system such that for all $i$, $L_f = \sqrt{2}\max_i |M_i|$ and $\rho_{f,i} = (2\pi)^{-1/2}$.

(u) If the coefficients of $f$ are independent random variables uniformly distributed in intervals of length at least $\lambda$ contained in $[-R, R]$, then for all $p \ge 1$, $f$ is a $p$-zintzo random polynomial system such that for all $i$, $L_{f,i} \le \max_i |M_i| R$ and $\rho_{f,i} \le \lambda^{-1}$. In particular, if all coefficients are uniformly distributed in $[-1, 1]$, then $L_{f,i} \le \max_i |M_i|$ and $\rho_{f,i} = 1/2$.

□

It is important to note that, arguing as in [65, Proposition 7.11], for a $p$-zintzo random polynomial,

$$L_f \rho_f \ge \frac{1}{4} \max_i |M_i| \ge \frac{1}{2} \binom{n+1}{2} \ge \frac{n^2}{4}. \qquad (5.4)$$

We provide now the tail bounds on the condition number:

**Theorem 5.4.** Let $f \in \mathcal{P}_{n,d}[q]$ be a $p$-zintzo random polynomial system with supports $M_1, \dots, M_n$. Then for $t \ge e^{n+1}$,

$$\mathbb{P}(\hat{\mathcal{C}}_1(f) \ge t) \le 4n^{\frac{2n}{p}} \mathbf{D}^{4n} (16L_f \rho_f)^{2n} \frac{\ln^{\frac{2n}{p}} t}{t}.$$

**Corollary 5.5.** Let $f \in \mathcal{P}_{n,d}[q]$ be a $p$-zintzo random polynomial system with supports $M_1, \dots, M_n$. Then $\log \hat{\mathcal{C}}_1(f)$ is a subexponential random variable with constant

$$n\mathcal{O}(\ln n + \log \mathbf{D} + \ln(4L_f \rho_f)).$$

**Theorem 5.6.** Let $f \in \mathcal{P}_{n,d}[q]$ be a $p$-zintzo random polynomial system with supports $M_1, \dots, M_n$ and $x \in \mathbb{R}^n$. Then for $t \ge e^{n+1}$,

$$\mathbb{P}(\hat{\mathcal{C}}_1(f, x) \ge t) \le 4n^{\frac{2n}{p}} \mathbf{D}^{4n} (8L_f \rho_f)^{2n} \frac{\ln^{\frac{2n}{p}} t}{t^{n+1}}.$$

*Proof of Theorem 5.4.* By the 2nd Lipschitz property of the condition number, we will show that

$$\mathbb{P}(\hat{\mathcal{C}}_1(f) \ge t) \le t^n \left(1 + \frac{1}{2t}\right)^n \sup_{x \in I^n} \mathbb{P}(\hat{\mathcal{C}}_1(f, x) \ge t/2). \qquad (5.5)$$

Once this is shown, Theorem 5.6 finishes the proof.

Let $\mathcal{G}_t \subset I^n$ be a finite subset such that for all $x \in C$, $\text{dist}_\infty(c, \mathcal{G}_t) \le 1/t$. Now, by the 2nd Lipschitz property (Theorem 3.9),

$$\hat{\mathcal{C}}_1(f) \le 2 \sup_{x \in \mathcal{G}_t} \hat{\mathcal{C}}_1(f, x)$$

whenever $2\mathcal{C}(f)t \le 1$. Thus $\mathcal{C}(f) \ge t$ implies

$$\sup_{x \in \mathcal{G}_t} \mathcal{C}(f, x) > t/2,$$
and so, by the implication bound,

$$ \mathbb{P}(\mathcal{C}(\mathfrak{f}) \ge t) \le \mathbb{P}\left(\sup_{x \in \mathcal{G}_t} \mathcal{C}(\mathfrak{f}, x) \ge t/2\right), $$

and, by the union bound,

$$ \mathbb{P}(\mathcal{C}(\mathfrak{f}) \ge t) \le |\mathcal{G}_t| \sup_{x \in I^n} \mathbb{P}(\mathcal{C}(\mathfrak{f}, x) \ge t/2). $$

Finally, we can achieve $|\mathcal{G}_t| \le t^n (1 + \frac{1}{2t})^n$ by putting the points in a uniform cubical grid. Thus (5.5) follows. □

*Proof of Corollary 5.5.* Use Theorem 5.4 together with Proposition A.2. □

*Proof of Theorem 5.6.* Consider

$$ \hat{\mathcal{C}}_1(f, x, v) := \frac{1}{\max \left\{ \|\Delta^{-1} \hat{f}(x)\|_{\infty}, \|\Delta^{-2} \mathrm{D}_x \hat{f}v\|_{\infty} \right\}}. $$

We can easily see that

$$ \hat{\mathcal{C}}_1(f, x) = \min_{v \in \partial I^n} \hat{\mathcal{C}}_1(f, x, v) \qquad (5.6) $$

and, using standard norm inequalities as in the proof of the 2nd Lipschitz property of Theorem 3.9, that the map

$$ \partial I^n \ni v \mapsto 1/\hat{\mathcal{C}}_1(f, x, v) \qquad (5.7) $$

is 1-Lipschitz with respect both $\| \cdot \|_{\infty}$.

Now, let $\mathfrak{v}_* \in \partial I^n$, be the random vector such that

$$ \max_{v \in \partial I^n} \hat{\mathcal{C}}_1(\mathfrak{f}, x, v) = \hat{\mathcal{C}}_1(\mathfrak{f}, x, \mathfrak{v}_*). $$

Then, if $\max_{v \in \partial I^n} \hat{\mathcal{C}}_1(\mathfrak{f}, x, v) \ge t$, we have that for all $v \in B_{\infty}(\mathfrak{v}_*, 1/t) \cap \partial I^n$, $\hat{\mathcal{C}}_1(\mathfrak{f}, x, v) \ge t/2$. Hence $\max_{v \in \partial I^n} \hat{\mathcal{C}}_1(\mathfrak{f}, x, v) \ge t$ implies that

$$ \mathbb{P}_{\mathfrak{v} \in \partial I^n} (\hat{\mathcal{C}}_1(\mathfrak{f}, x, \mathfrak{v}) \ge t/2) \ge \frac{\mathrm{vol} B_{\infty}(\mathfrak{v}_*, 1/t) \cap \partial I^n}{\mathrm{vol} \partial I^n} \ge \frac{n}{n+1} \frac{1}{2^n t^{n-1}}. $$

Thus

$$ \mathbb{P}_f(\hat{\mathcal{C}}_1(f, x) \ge t) \le \mathbb{P}(\max_{v \in \partial I^n} \hat{\mathcal{C}}_1(f, x, v) \ge t) \qquad (\text{Implication bound}) $$

$$ \le \mathbb{P}_f \left( \mathbb{P}_{\mathfrak{v} \in \partial I^n} (\hat{\mathcal{C}}_1(f, x, v) \ge t/2) \ge \frac{n}{n+1} \frac{1}{2^n t^{n-1}} \right) \qquad (\text{Implication bound}) $$

$$ \le \frac{n+1}{n} t^{n-1} \mathbb{E}_f \mathbb{P}_{\mathfrak{v} \in \partial I^n} (\hat{\mathcal{C}}_1(f, x, v) \ge t/2) \qquad (\text{Markov's bound}) $$

$$ \le \frac{n+1}{n} t^{n-1} \mathbb{E}_{\mathfrak{v} \in \partial I^n} \mathbb{P}_f (\hat{\mathcal{C}}_1(f, x, v) \ge t/2) \qquad (\text{Tonelli's theorem}) $$

$$ \le \frac{n+1}{n} t^{n-1} \sup_{v \in \partial I^n} \mathbb{P}_f (\hat{\mathcal{C}}_1(f, x, v) \ge t/2). $$

All this reduces us to estimate

$$ \mathbb{P}_f(\hat{\mathcal{C}}_1(f, x, v) \ge t/2). $$
By the union bound, the implication bound and [65, Proposition 7.4], we have that for $u \ge L_f$,

$$ \mathbb{P}_f(\hat{\mathcal{C}}_1(f, x, v) \ge t/2) \le \left(\sum_i |M_i|\right) e^{-u^p/L_f^p} + \mathbb{P}_f(\max\{\|\Delta^{-1}f(x)\|_{\infty}, \|\Delta^{-2}\mathrm{D}_x f v\|_{\infty}\} \le u/t), $$

where the implication used is that either the numerator of $\hat{\mathcal{C}}_1(f, x, v)$ is $\ge u$ or the denominator $\le u/t$.

To bound the last summand, we will use [65, Proposition 7.7]. This proposition, a explicit refinement of [60, Theorem 1.1], states that given a random vector $\mathbf{x} \in \mathbb{R}^N$ with independent coordinates with anticoncentration constants $\le \rho$, a surjective matrix $A \in \mathbb{R}^{k \times N}$ and $U \subseteq \mathbb{R}^k$, then

$$ \mathbb{P}(A \mathbf{x} \in U) \le \mathrm{vol}(U) (\sqrt{2\rho})^k / \sqrt{\det(AA^*)}. $$

By the Cauchy-Binet formula, we only have to find appropriate submatrices of $A$ to obtain lower bounds on $\sqrt{\det(AA^*)}$.

Now, to apply the above result, we consider the linear projection,

$$ f \mapsto \begin{pmatrix} \Delta^{-1}f(x) \\ \Delta^{-2}\mathrm{D}_x f v \end{pmatrix} \in \mathbb{R}^{2n} \qquad (5.8) $$

with $U = u/tI^{2n}$ and so $\mathrm{vol}U = (2u/t)^{2n}$. Now, this projection has the following submatrix:

$$ \begin{pmatrix} \Delta^{-1} & x_1\Delta^{-1} & \cdots & x_n\Delta^{-1} \\ \Delta^{-2}v_1 & \cdots & \Delta^{-2}v_n \end{pmatrix} \qquad (5.9) $$

by looking at the monomials $1, X_1, \dots, X_n$. Hence, by the Cauchy-Binet formula,

$$ \sqrt{\det AA^*} \ge \mathcal{D}^{-3} \|v\|^n \ge \mathcal{D}^{-3}. \qquad (5.10) $$

Therefore $\mathbb{P}(\hat{\mathcal{C}}_1(f, x, v) \ge t/2)$ is upper bounded by

$$ \left(\sum_i |M_i|\right) e^{-u^p/L_f^p} + \mathcal{D}^3 \left(\frac{2\sqrt{2}u\rho_f}{t}\right)^{2n}, $$

and so $\mathbb{P}(\hat{\mathcal{C}}_1(f, x) \ge t)$ by

$$ 2t^{n-1} \left( \sum_i |M_i| \right) e^{-u^p/L_f^p} + \mathcal{D}^3 \frac{(2\sqrt{2}u\rho_f)^{2n}}{t^{n+1}} $$

Taking $u = L_f(2n \ln t)^{1/p}$ and estimating gives the bound. We use that $|M_i| \le (2\mathbf{D})^n$ among others. $\square$

## 5.2 Dobro Random Polynomials

Dobro random polynomials where introduced in [21] (cf. [19]) modelling a robust probabilistic model of polynomials.
**Definition 5.7.** A dobro random polynomial system is a random homogeneous polynomial system $f \in \mathcal{H}_{n,d}[n]$ with

$$f_i = \sum_{\alpha} \sqrt{\binom{d_i}{\alpha}} c_{i,\alpha} X^{\alpha} \quad (i \in \{1, \dots, n\})$$

such that the coefficients $c_\alpha$ are independent centered subgaussian random variables with the anti-concentration property.

Given a dobrio random polynomial system $f \in \mathcal{H}_{n,d}[n]$, we define the following quantities:

1. The tail constants of $f$ given by

$$L_f := \max_i \max_{\alpha} L_{i,\alpha}, \qquad (5.11)$$

where $L_{i,\alpha}$ is the subgaussian constant of $c_{i,\alpha}$.

2. The anti-concentration constant of $f$ given by

$$\rho_f := \max_{k,l} \rho_{i,(d_i-1)e_k+e_l} \qquad (5.12)$$

where $\rho_{i,\alpha}$ is the anti-concentration constant of $c_{i,\alpha}$.

It is important to note that KSS polynomial systems are dobro random polynomial systems.

**Proposition 5.8.** Let $f \in \mathcal{H}_{n,d}[q]$ be a random homogeneous polynomial system with

$$f_i = \sum_{\alpha} \sqrt{\binom{d_i}{\alpha}} c_{i,\alpha} X^{\alpha} \quad (i \in \{1, \dots, n\}).$$

The following holds:

(g) If the $c_{i,\alpha}$ are independent centered normal variables of variance at least $\sigma_0^2$ and at most $\sigma_1^2$, then $L_{f,i} = 2\sigma_1$ and $\rho_{f,i} = (2\pi)^{-1/2}\sigma_0^{-1}$. Moreover, if all the $c_{i,\alpha}$ are standard normal variables, then $f$ is a dobro random polynomial system such that for all $i$, $L_f = \sqrt{2}\max_i |M_i|$ and $\rho_{f,i} = (2\pi)^{-1/2}$.

(u) If the $c_{i,\alpha}$ are independent random variables uniformly distributed in centered intervals of length at least $\lambda$ contained in $[-R, R]$, then $f$ is a dobro random polynomial system such that for all $i$, $L_{f,i} \le R$ and $\rho_{f,i} \le \lambda^{-1}$. In particular, if all coefficients are uniformly distributed in $[-1, 1]$, then $L_{f,i} \le 1$ and $\rho_{f,i} = 1/2$.

□

It is important to note that, arguing as in [65, Proposition 7.11], for a dobro random polynomial,

$$L_f \rho_f \ge \frac{1}{4}. \qquad (5.13)$$

To provide now the tail bounds on the condition number we proceed as in the previous subsection. The techniques are similar to those in [21] and [20] so we omit the proofs.
**Theorem 5.9.** Let $f \in \mathcal{H}_{n,d}[q]$ be a dobro random polynomial system. Then for $t \ge e^{n+1}$,

$$P(\hat{\kappa}_W(f) \ge t) \le 4n^n \mathbf{D}^{3n/2} (16L_f \rho_f)^{2n} \frac{\ln^n t}{t}$$

**Corollary 5.10.** Let $f \in \mathcal{H}_{n,d}[q]$ be a dobro random polynomial system. Then $\log \hat{\kappa}_W(f)$ is a subexponential random variable with constant

$$n \mathcal{O}(\ln n + \log \mathbf{D} + \ln(4L_f \rho_f)).$$

**Theorem 5.11.** Let $f \in \mathcal{H}_{n,d}[q]$ be a dobro random polynomial system and $x \in \mathbb{R}^n$. Then for $t \ge e^{n+1}$,

$$P(\hat{\kappa}_W(f, x) \ge t) \le 4n^n \mathbf{D}^{3n/2} (8L_f \rho_f)^{2n} \frac{\ln^n t}{t^{n+1}}$$

## References

[1] Michele Ancona. Exponential rarefaction of maximal real algebraic hypersurfaces, 2022.

[2] Michele Ancona. On the topology of random real complete intersections. *J. Geom. Anal.*, 33(1):Paper No. 32, 26, 2023.

[3] Michele Ancona and Thomas Letendre. Roots of Kostlan polynomials: moments, strong law of large numbers and central limit theorem. *Ann. H. Lebesgue*, 4:1659-1703, 2021.

[4] D. Armentano, J.-M. Azaïs, F. Dalmao, and J. R. León. Asymptotic variance of the number of real roots of random polynomial systems. *Proc. Amer. Math. Soc.*, 146(12):5437-5449, 2018.

[5] D. Armentano, J.-M. Azaïs, F. Dalmao, and J. R. León. Central limit theorem for the number of real roots of Kostlan Shub Smale random polynomial systems. *Amer. J. Math.*, 143(4):1011-1042, 2021.

[6] D. Armentano, J.-M. Azaïs, F. Dalmao, and J. R. León. Central limit theorem for the volume of the zero set of Kostlan-Shub-Smale random polynomial systems. *J. Complexity*, 72:Paper No. 101668, 22, 2022.

[7] J.-M. Azaïs and M. Wschebor. *Level sets and extrema of random processes and fields*. John Wiley & Sons, Inc., Hoboken, NJ, 2009.

[8] P. Breiding, S. Fairchild, P. Santarsiero, and E. Shehu. Average degree of the essential variety, 2022.

[9] Paul Breiding, Hanieh Keneshlou, and Antonio Lerario. Quantitative singularity theory for random polynomials. *Int. Math. Res. Not.*, 2022(8):5685-5719, 2022.

[10] P. Bürgisser, F. Cucker, and P. Lairez. Computing the homology of basic semialgebraic sets in weak exponential time. *J. ACM*, 66(1):5:1-5:30, December 2018.

[11] P. Bürgisser, F. Cucker, and J. Tonelli-Cueto. Computing the Homology of Semialgebraic Sets. I: Lax Formulas. *Foundations of Computational Mathematics*, 20(1):71-118, 2020. On-line from May of 2019.

[12] P. Bürgisser, F. Cucker, and J. Tonelli-Cueto. Computing the Homology of Semialgebraic Sets. II: General formulas. *Foundations of Computational Mathematics*, 1 2021. On-line from January of 2021. arXiv: 1903.10710.

[13] Peter Bürgisser. Average Euler characteristic of random real algebraic varieties. *C. R. Math. Acad. Sci. Paris*, 345(9):507-512, 2007.

[14] Peter Bürgisser and Felipe Cucker. *Condition*, volume 349 of *Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]*. Springer, Heidelberg, 2013. The geometry of numerical algorithms.
[15] Peter Bürgisser and Antonio Lerario. Probabilistic Schubert calculus. *J. Reine Angew. Math.*, 760:1–58, 2020.

[16] P. Bürgisser. Real zeros of mixed random fewnomial systems. In *Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation*, ISSAC '23, page 107–115, New York, NY, USA, 2023. Association for Computing Machinery.

[17] P. Bürgisser, A. A. Ergür, and J. Tonelli-Cueto. On the number of real zeros of random fewnomials. *SIAM J. Appl. Algebra Geom.*, 3(4):721–732, 2019.

[18] F. Cucker. Grid methods in computational real algebraic (and semialgebraic) geometry. *Chin. Ann. Math. Ser. B*, 39(2):373–396, 2018.

[19] F. Cucker, A. A. Ergür, and J. Tonelli-Cueto. Plantinga-Vegter Algorithm Takes Average Polynomial Time. In *Proceedings of the 2019 on International Symposium on Symbolic and Algebraic Computation*, pages 114–121. ACM, 07 2019.

[20] F. Cucker, A. A. Ergür, and J. Tonelli-Cueto. Functional norms, condition numbers and numerical algorithms in algebraic geometry, 2 2021. arXiv:2102.11727.

[21] F. Cucker, A. A. Ergür, and J. Tonelli-Cueto. On the Complexity of the Plantinga-Vegter Algorithm. *Discrete & Computational Geometry*, 68(3):664–708, 08 2022.

[22] F. Cucker, T. Krick, G. Malajovich, and M.Wschebor. A numerical algorithm for zero counting. I. Complexity and accuracy. *J. Complexity*, 24(5-6):582–605, 2008.

[23] F. Cucker, T. Krick, G. Malajovich, and M. Wschebor. A numerical algorithm for zero counting. II. Distance to ill-posedness and smoothed analysis. *J. Fixed Point Theory Appl.*, 6(2):285–294, 2009.

[24] F. Cucker, T. Krick, G. Malajovich, and M. Wschebor. A numerical algorithm for zero counting. III: Randomization and condition. *Adv. in Appl. Math.*, 48(1):215–248, 2012.

[25] F. Cucker, T. Krick, and M. Shub. Computing the homology of real projective sets. *Found. Comput. Math.*, 18(4):929–970, 2018.

[26] Felipe Cucker. Approximate zeros and condition numbers. *J. Complexity*, 15(2):214–226, 1999.

[27] Federico Dalmao. Asymptotic variance and CLT for the number of zeros of Kostlan Shub Smale random polynomials. *C. R. Math. Acad. Sci. Paris*, 353(12):1141–1145, 2015.

[28] Jean-Pierre Dedieu. *Points fixes, zéros et la méthode de Newton*, volume 54 of *Mathématiques & Applications (Berlin) [Mathematics & Applications]*. Springer, Berlin, 2006.

[29] Daouda Niang Diatta and Antonio Lerario. Low-degree approximation of random polynomials. *Found. Comput. Math.*, 22(1):77–97, 2022.

[30] Alicia Dickenstein, J. Maurice Rojas, Korben Rusek, and Justin Shih. Extremal real algebraic geometry and $\mathcal{A}$-discriminants. *Mosc. Math. J.*, 7(3):425–452, 574, 2007.

[31] Yen Do, Oanh Nguyen, and Van Vu. Roots of random polynomials with coefficients of polynomial growth. *Ann. Probab.*, 46(5):2407–2494, 2018.

[32] Yen Do and Van Vu. Central limit theorems for the real zeros of Weyl polynomials. *Amer. J. Math.*, 142(5):1327–1369, 2020.

[33] A. Edelman and E. Kostlan. How many zeros of a random polynomial are real? *Bull. Amer. Math. Soc. (N.S.)*, 32(1):1–37, 1995.

[34] Boulos El Hilany. Constructing polynomial systems with many positive solutions using tropical geometry. *Rev. Mat. Complut.*, 31(2):525–544, 2018.
[35] Alperen Ergür, Josué Tonelli-Cueto, and Elias Tsigaridas. Beyond worst-case analysis for root isolation algorithms. In *ISSAC '22—Proceedings of the 2022 International Symposium on Symbolic and Algebraic Computation*, pages 139–148. ACM, New York, [2022] ©2022.

[36] Alperen A. Ergür, Grigoris Paouris, and J. Maurice Rojas. Probabilistic condition number estimates for real polynomial systems I: A broader family of distributions. *Found. Comput. Math.*, 19(1):131–157, 2019.

[37] Alperen A. Ergür, Grigoris Paouris, and J. Maurice Rojas. Smoothed analysis for the condition number of structured real polynomial systems. *Math. Comp.*, 90(331):2161–2184, 2021.

[38] Alperen A. Ergür, Máté L. Telek, and Josué Tonelli-Cueto. On the number of real zeros of random sparse polynomial systems, 2023.

[39] Yan V. Fyodorov, Antonio Lerario, and Erik Lundberg. On the number of connected components of random algebraic hypersurfaces. *J. Geom. Phys.*, 95:1–20, 2015.

[40] Damien Gayet and Jean-Yves Welschinger. What is the total Betti number of a random real hypersurface? *J. Reine Angew. Math.*, 689:137–168, 2014.

[41] Damien Gayet and Jean-Yves Welschinger. Betti numbers of random real hypersurfaces and determinants of random symmetric matrices. *J. Eur. Math. Soc. (JEMS)*, 18(4):733–772, 2016.

[42] V. Gichev. Decomposition of the Kostlan-Shub-Smale model for random polynomials. In *Complex analysis and dynamical systems VII*, volume 699 of *Contemp. Math.*, pages 103–120. Amer. Math. Soc., Providence, RI, 2017.

[43] M. Kac. On the average number of real roots of a random algebraic equation. *Bull. Amer. Math. Soc.*, 49:314–320, 1943.

[44] B. Ya. Kazarnovskii. Average number of roots of systems of equations. *Functional Analysis and Its Applications*, 54(2):100–109, 2020.

[45] B. Ya. Kazarnovskii. How many roots of a system of random laurent polynomials are real? *Sbornik: Mathematics*, 213(4):466, 4 2022.

[46] E. Kostlan. On the distribution of roots of random polynomials. In *From Topology to Computation: Proceedings of the Smalefest (Berkeley, CA, 1990)*, pages 419–431. Springer, New York, 1993.

[47] Kh. Kozhasov and J. Tonelli-Cueto. Probabilistic bounds on best rank-one approximation ratio, 01 2022.

[48] A. Lerario and L. Mathis. Probabilistic Schubert calculus: asymptotics. *Arnold Math. J.*, 7(2):169–194, 2021.

[49] Antonio Lerario and Erik Lundberg. Statistics on Hilbert’s 16th problem. *Int. Math. Res. Not. IMRN*, (12):4293–4321, 2015.

[50] T. Letendre. Variance of the volume of random real algebraic submanifolds. *Trans. Amer. Math. Soc.*, 371(6):4129–4192, 2019.

[51] T. Letendre and M. Puchol. Variance of the volume of random real algebraic submanifolds II. *Indiana Univ. Math. J.*, 68(6):1649–1720, 2019.

[52] J. E. Littlewood and A. C. Offord. On the distribution of the zeros and $a$-values of a random integral function. I. *J. London Math. Soc.*, 20:130–136, 1945.

[53] N. B. Maslova. The distribution of the number of real roots of random polynomials. *Teor. Verojatnost. i Primenen.*, 19:488–500, 1974.

[54] L. Mathis and M. Stecconi. Expectation of a random submanifold: the zonoid section, 2022.
[55] G. Moroz. Fast real and complex root-finding methods for well-conditioned polynomials, 6 2021. arXiv:2102.04180.

[56] G. Moroz. New data structure for univariate polynomial approximation and applications to root isolation, numerical multipoint evaluation, and other problems, 6 2021. arXiv:2106.02505.

[57] Oanh Nguyen and Van Vu. Random Polynomials: Central Limit Theorems for the Real Roots, 2020.

[58] Oanh Nguyen and Van Vu. Roots of random functions: a framework for local universality.
* Amer. J. Math.*, 144(1):1–74, 2022.

[59] J. Renegar. On the efficiency of Newton’s method in approximating all zeros of a system of complex polynomials. *Math. Oper. Res.*, 12(1):121–148, 1987.

[60] M. Rudelson and R. Vershynin. Small ball probabilities for linear images of high-dimensional distributions. *Int. Math. Res. Not. IMRN*, 19:9594–9617, 2015.

[61] M. Shub and S. Smale. Complexity of Bezout's theorem. II. Volumes and probabilities. In *Computational algebraic geometry (Nice, 1992)*, volume 109 of *Progr. Math.*, pages 267–285. Birkhäuser Boston, Boston, MA, 1993.

[62] Terence Tao and Van Vu. Local universality of zeroes of random polynomials. *Int. Math. Res. Not. IMRN*, (13):5053–5139, 2015.

[63] J. Tonelli-Cueto. *Condition and Homology in Semialgebraic Geometry*. Doctoral thesis, Technische Universität Berlin, DepositOnce Repository, December 2019. http://dx.doi.org/10.14279/depositonce-9453.

[64] J. Tonelli-Cueto and E. Tsigaridas. Condition numbers for the cube. i: Univariate polynomials and hypersurfaces. In *Proceedings of the 45th International Symposium on Symbolic and Algebraic Computation*, ISSAC '20, page 434–441, New York, NY, USA, 2020. Association for Computing Machinery.

[65] J. Tonelli-Cueto and E. Tsigaridas. Condition Numbers for the Cube. I: Univariate Polynomials and Hypersurfaces, 2021. To appear in the special issue of the Journal of Symbolic Computation for ISSAC 2020. Available at arXiv:2006.04423.

[66] R. Vershynin. *High-dimensional probability: An introduction with applications in data science*, volume 47 of *Cambridge Series in Statistical and Probabilistic Mathematics*. Cambridge University Press, Cambridge, 2018.
# A Subexponential random variables

In this self-contained appendix, we recall the notion of subexponential random variable. We include this appendix, since standard references, such as [66], do not include the constants explicitly.

We begin with the definition of subexponential random variable, and its $\psi_1$-norm.

**Definition A.1.** A subexponential random variable is a random variable $\mathfrak{r} \in \mathbb{R}$ such that for some $C \ge 0$,

$$ \text{for all } \ell \in \mathbb{Z}_+, \mathbb{E}|\mathfrak{r}|^\ell \le (C\ell)^\ell. \qquad (A.1) $$

The $\psi_1$-norm of such a subexponential random variable $\mathfrak{r}$ is the norm given by

$$ \|\mathfrak{r}\|_{\psi_1} := \sup_{\ell \in \mathbb{Z}_+} \frac{(\mathbb{E}|\mathfrak{r}|^\ell)^{\frac{1}{\ell}}}{\ell}, $$

i.e., $\|\mathfrak{r}\|_{\psi_1}$ is the smallest real number such that (A.1) is satisfied.

The following proposition shows how the $\psi_1$-norm relates to subexponential tail bounds.

**Proposition A.2.** Let $\mathfrak{r} \in \mathbb{R}$ be a random variable.

(1) If $\mathfrak{r} \in \mathbb{R}$ is subexponential, then for all $t > 0$,

$$ \mathbb{P}(|\mathfrak{r}| \ge t) \le e^{1 - \frac{t}{3\|\mathfrak{r}\|_{\psi_1}}}. \qquad (A.2) $$

(2) Let $A \ge 1$, $C > 0$. If for $t > 0$,

$$ \mathbb{P}(|\mathfrak{r}| \ge t) \le A e^{-\frac{t}{C}}, $$

then $\mathfrak{r}$ is subexponential with

$$ \|\mathfrak{r}\|_{\psi_1} \le 2C \ln(eA). $$

(3) Let $A, B \ge 1$, $C > 0$ and $b \in \mathbb{N}$. If for $t > 0$,

$$ \mathbb{P}(|\mathfrak{r}| \ge t) \le A(t + B)^b e^{-\frac{t}{C}}, $$

then $\mathfrak{r}$ is subexponential with

$$ \|\mathfrak{r}\|_{\psi_1} \le 4C \left[ \ln(eA) + \frac{b}{2} \ln(2bBC) \right]. $$

*Proof.* (1) We have that

$$ \mathbb{P}(|\mathfrak{r}| \ge t) = \mathbb{P}(e^{a|\mathfrak{r}|} \ge e^{at}) \qquad (a > 0) $$

$$ \le e^{-at} \mathbb{E}e^{a|\mathfrak{r}|} \qquad (\text{Markov's inequality}) $$

$$ = e^{-at} \sum_{k=0}^{\infty} \frac{a^k \mathbb{E}|\mathfrak{r}|^k}{k!} \qquad (\text{Monotone convergence theorem}) $$

$$ \le e^{-at} \sum_{k=0}^{\infty} \frac{(\|\mathfrak{r}\|_{\psi_1} a)^k k^k}{k!} \qquad (\text{Definition } \psi_1\text{-norm}) $$
Now, for $a = \frac{1}{3||\mathbf{r}||_{\psi_1}}$, we have

$$ \sum_{k=0}^{\infty} \frac{\left(\|\mathbf{r}\|_{\psi_1} a\right)^k k^k}{k!} = \sum_{k=0}^{\infty} \frac{1}{k!} \left(\frac{k}{3}\right)^k = 2.62 \dots < e, $$

after a numerical computation. Hence the desired inequality follows.

(2) Fix $\ell \in \mathbb{Z}_+$ and $T > 0$. We have that

$$ \mathbb{E}|\mathbf{r}|^{\ell} = \ell \int_{0}^{\infty} \mathbb{P}(|\mathbf{r}| \ge s) s^{\ell-1} ds \le T^{\ell} + C^{\ell} \ell \int_{T/C}^{\infty} \mathbb{P}(|\mathbf{r}| \ge Cu) u^{\ell-1} du, \quad (A.3) $$

after dividing the integration domain into $[0, T]$ and $[T, \infty)$, where we use $\mathbb{P} \le 1$ on the first subinterval and the change of variables $u = s/C$ on the second one.

Thus

$$ \mathbb{E}|\mathbf{r}|^{\ell} \le T^{\ell} + AC^{\ell} \ell \int_{T/C}^{\infty} s^{\ell-1} e^{-s} ds. $$

On the right hand side, we have the incomplete Gamma function:

$$ \Gamma(s, x) := \int_{x}^{\infty} t^{s-1} e^{-t} dt. \quad (A.4) $$

We have that for $\ell \in \mathbb{Z}_+$ and $x \ge 1$,

$$ \Gamma(\ell, x) \le (\ell - 1)! \min\{1, x^{\ell-1} e^{1-x}\}. \quad (A.5) $$

Effectively, we have that

$$ \Gamma(\ell, x) = e^{-x} \int_{0}^{\infty} (t+x)^{\ell-1} e^{-t} dt \quad (\text{Change of variables}) $$

$$ = e^{-x} \sum_{k=0}^{\ell-1} \binom{\ell-1}{k} x^k \int_{0}^{\infty} t^{\ell-k-1} e^{-t} dt \quad (\text{Newton's binomial}) $$

$$ = (\ell - 1)! e^{-x} \sum_{k=0}^{\ell-1} \frac{x^k}{k!} \quad \left( \int_{0}^{\infty} t^{\ell-k-1} e^{-t} dt = (\ell - k - 1)! \right) $$

Now, for $x \ge 1$, on the one hand, $\sum_{k=0}^{\ell-1} \frac{x^k}{k!} \le e^x$, and, on the other hand, $\sum_{k=0}^{\ell-1} \frac{x^k}{k!} \le ex^{\ell-1}$. These two expression give the stated inequality.

Hence, by (A.5),

$$ \mathbb{E}|\mathbf{r}|^{\ell} \le T^{\ell-1} \left( T + AC\ell!e^{1-\frac{T}{C}} \right). $$

If we take $T = C \ln(eA)$, we obtain

$$ \mathbb{E}|\mathbf{r}|^{\ell} \le (C \ln(eA))^{\ell} \left(1 + \frac{\ell!}{\ln(eA)}\right) \le \left(1 + \frac{1}{\ln(eA)}\right) (C \ln(eA))^{\ell} \ell^{\ell}. $$

The latter gives the stated bound on the $\psi_1$-norm.

(3) Using a simple maximization argument, we have that for $t \ge 0$,

$$ (B + t)^b e^{-\frac{t}{2C}} \le \max\{B^b, (2bC)^b\} \le (2bBC)^{\frac{b}{2}}. \quad (A.6) $$

Thus we have that

$$ \mathbb{P}(|\mathbf{r}| \ge t) \le A(2bBC)^{\frac{b}{2}} e^{-\frac{t}{2C}}, \quad (A.7) $$

and, by (2), we conclude the desired claim.

□