Josué Tonelli-Cueto

Elias Tsigaridas

Condition Numbers for the Cube. I: Univariate Polynomials and Hypersurfaces

Keywords: condition number, random polynomial, subdivision algorithm, univariate solver

The condition-based complexity analysis framework is one of the gems of modern numerical algebraic geometry and theoretical computer science. One of the challenges that it poses is to expand the currently limited range of random polynomials that we can handle. Despite important recent progress, the available tools cannot handle random sparse polynomials and Gaussian polynomials, that is polynomials whose coefficients are i.i.d. Gaussian random variables.

. In both cases, we provide a bound that is polynomial in the size of the input (size of the support plus logarithm of the degree) for not only on the average, but all higher moments.

Introduction

The complexity of numerical algorithms is not uniform. It depends on a measure of the numerical sensitivity of the output with respect to perturbations of the input, called condition number and introduced originally by [START_REF] Turing | Rounding-off errors in matrix processes[END_REF] and von Neumann and [START_REF] Von Neumann | Numerical inverting of matrices of high order[END_REF]. When the condition number of an input is large, then this means that small numerical perturbations of the input can significantly change the solution of the problem at hand. Consequently, numerical algorithms need to use more computational resources to guarantee a correct computation.

The above phenomenon motivates the condition-based complexity analysis of numerical algorithms. Although a condition-based complexity analysis can explain the success of an algorithm for a given input, it cannot explain, at least on its own, why a numerical algorithm is efficient. The reason is that condition-based complexity analyses are not input-independent. Thus a common technique that goes back [START_REF] Goldstine | Numerical inverting of matrices of high order[END_REF], [START_REF] Demmel | On condition numbers and the distance to the nearest ill-posed problem[END_REF][START_REF] Demmel | The probability that a numerical analysis problem is difficult[END_REF] and [START_REF] Smale | Complexity theory and numerical analysis[END_REF] is to randomize the input. In this way, we obtain a probabilistic complexity analysis that can explain the successful behaviour of an algorithm. Moreover, the framework of smoothed analysis [START_REF] Spielman | Smoothed analysis of algorithms[END_REF] fully explains the practical behaviour of an algorithm. We refer the reader to [START_REF] Bürgisser | of Grundlehren der mathematischen Wissenschaften[END_REF] and references therein for more details about this complexity paradigm for numerical algorithms.

After the complete solution1 of Smale's 17th problem by [START_REF] Lairez | A deterministic algorithm to compute approximate roots of polynomial systems in polynomial average time[END_REF], following the steps of [START_REF] Beltrán | On Smale's 17th problem: a probabilistic positive solution[END_REF] and [START_REF] Bürgisser | On a problem posed by Steve Smale[END_REF], the main challenge in numerical algebraic geometry is to extend (and analyze) the current algorithms for solving polynomial systems to handle more general inputs; for example sparse and structured polynomials.

In the complex setting, [START_REF] Malajovich | Complexity of sparse polynomial solving: homotopy on toric varieties and the condition metric[END_REF][START_REF] Malajovich | Complexity of Sparse Polynomial Solving 2: Renormalization[END_REF] and Malajovich andRojas (2002, 2004) did groundbreaking work in the development for numerical algorithms for finding a solution of sparse polynomial systems, and recently [START_REF] Bürgisser | Rigid continuation paths II. Structured polynomial systems[END_REF] (following the ideas of Lairez (2020)) introduces efficient numerical algorithms for finding a solution of determinant polynomial systems. Additionally, [START_REF] Armentano | The polynomial eigenvalue problem is well conditioned for random inputs[END_REF] provided a probabilistic estimate of the condition number for the Polynomial Eigenvalue Problem, although they did not provide an algorithm.

In the real setting, the situation is far more difficult. For example, as of today, the real version of Smale's 17th problem (asking to decide numerically the feasibility of a real polynomial system) remains open as no algorithm running in finite expected time is known (see (Bürgisser and Cucker, 2013, Ch. 17 and P.18) for more details). Of course, ideally, we want to solve the real sparse Smale's 17th problem (which was proposed by [START_REF] Rojas | On solving univariate sparse polynomials in logarithmic time[END_REF]):

Find an algorithm that finds all the real roots of a real fewnomial system with average run-time bounded by a polynomial in the size of the system (which is the size of the support and the logarithm of the degree).

However, such a result (although motivated by [START_REF] Khovanskiȋ | of Translations of Mathematical Monographs[END_REF] and Kushnirenko's hypothesis) seems to be out of reach today. Nevertheless, some progress has been made by [START_REF] Rojas | Counting positive roots in polynomial-time for systems supported on circuits[END_REF] (although not in the numerical setting). Regarding structured systems, there are some results by [START_REF] Beltrán | The real polynomial eigenvalue problem is well conditioned on the average[END_REF] and [START_REF] Ergür | Probabilistic condition number estimates for real polynomial systems I: A broader family of distributions[END_REF]; [START_REF] Ergür | Probabilistic Condition Number Estimates for Real Polynomial Systems II: Structure and Smoothed Analysis[END_REF].

A common problem with many of the current techniques is that they rely on unitary/orthogonal invariance. Therefore, it is central for an effective algorithmic framework to develop techniques that do not rely on this invariance to compute with sparse/structured polynomials and more general probability distributions. We make one step in this research direction by developing a condition-based complexity framework that relies on the ∞-norm of the cube, and which consequently does not rely on unitary invariance. We develop the above framework for univariate polynomials and hypersurfaces. We hope to extend it for polynomial systems in a future work. To illustrate its advantages we apply it to two problems. First, to study the complexity of the Plantinga-Vegter algorithm [START_REF] Plantinga | Isotopic approximation of implicit curves and surfaces[END_REF][START_REF] Burr | The complexity of an adaptive subdivision method for approximating real curves[END_REF]. Then, to study the separation bounds of the roots of real univariate polynomials. Using the latter bounds we deduce a bound on the average number of subdivisions that Descartes' solver performs to isolate the real roots of univariate polynomials and we estimate the average bit complexity of the algorithm by [START_REF] Jindal | Efficiently computing real roots of sparse polynomials[END_REF] for solving sparse univariate polynomials. The latter bound is polynomial in the input size, providing a first approximation to the real sparse version of Smale's 17th problem by [START_REF] Rojas | On solving univariate sparse polynomials in logarithmic time[END_REF].

In the case of the Plantinga-Vegter algorithm, we demonstrate its efficiency by showing that its complexity is polynomial on the average, for a wide class of random sparse polynomials (Theorem 7.19). This significantly extends the results by [START_REF] Cucker | Plantinga-Vegter Algorithm Takes Average Polynomial Time[END_REF], (cf. Cucker et al., 2020b). Additionally, our approach applies to Gaussian random polynomials, when all coefficients have the same variance.

We note that our aim is not to show that the Plantinga-Vegter is the most efficient algorithm for random sparse polynomials, but that it remains efficient when we restrict it to a wide class of random sparse polynomials. We note that our bounds depend polynomially on the degree and not logarithmically. A similar approach was employed by [START_REF] Ergür | Probabilistic Condition Number Estimates for Real Polynomial Systems II: Structure and Smoothed Analysis[END_REF] for the algorithm for finding real zeros of real polynomial systems from [START_REF] Cucker | A numerical algorithm for zero counting. I: Complexity and accuracy[END_REF]. However, unlike [START_REF] Ergür | Probabilistic Condition Number Estimates for Real Polynomial Systems II: Structure and Smoothed Analysis[END_REF], our analysis applies to structured polynomials that are sparse, but with a combinatorial restriction on the support. We note that our sparseness condition is similar to that of [START_REF] Renegar | On the efficiency of Newton's method in approximating all zeros of a system of complex polynomials[END_REF] and so is the bound we obtain; the latter is polynomial in the degree and the size of the support and exponential in the number of variables. Many computational problems in real algebraic geometry lack algorithms that are polynomial in the degree, so such bounds push the limits of the state-of-the-art.

In the case of univariate polynomials, our results imply that the complex roots of a random real univariate sparse polynomial around the unit interval are well separated with high probability. The logarithm of the separation bound is an important parameter that controls the complexity of many, if not all, univariate solvers. We exploit its relation with the condition number to obtain bounds on the size of the subdivision tree of Descartes' solver and on the average run-time of the sparse univariate solver of [START_REF] Jindal | Efficiently computing real roots of sparse polynomials[END_REF].

In both cases, that for both Descartes' solver and the solver of [START_REF] Jindal | Efficiently computing real roots of sparse polynomials[END_REF], the bounds that we obtain are: 1) polynomial in the size of the sparse polynomial (meaning polynomial in the size of the support and the logarithm of the degree, and 2) extend to all higher moments. The importance of these bounds is that they are the first step towards solving the real sparse version of Smale's 17th problem, as stated by [START_REF] Rojas | On solving univariate sparse polynomials in logarithmic time[END_REF].

Our framework is based on the one hand on variational properties of the polynomials and the corresponding condition numbers and on the other on probabilistic techniques from geometric functional analysis. The former follows the variational approach to condition numbers of (Tonelli-Cueto, 2019, 2 §2 ) and extends Cucker et al. (2020a) to new norms. The latter has been already applied by [START_REF] Ergür | Probabilistic condition number estimates for real polynomial systems I: A broader family of distributions[END_REF]; [START_REF] Ergür | Probabilistic Condition Number Estimates for Real Polynomial Systems II: Structure and Smoothed Analysis[END_REF] and by [START_REF] Cucker | Plantinga-Vegter Algorithm Takes Average Polynomial Time[END_REF], but the way that we apply these methods takes them to the maximum development.

The 1-norm on the space of polynomials behaves as the "dual"norm to the ∞-norm on the cube. This norm is naturally suited for subdivision methods on the cube. The analysis of the Plantinga-Vegter subdivision process using our framework serves the purpose to convince the reader of the advantages of the new framework for the analysis of algorithms. It also has the ambition to bring new insights in the study of algorithms in numerical algebraic geometry. Our approach continues the trend started by [START_REF] Cucker | Plantinga-Vegter Algorithm Takes Average Polynomial Time[END_REF] of bringing further interactions between the communities of numerical algebraic geometry and symbolic computation.

A preliminary version of the paper appeared in the proceedings of ISSAC 2020 [START_REF] Tonelli-Cueto | Condition numbers for the cube. I: Univariate polynomials and hypersurfaces[END_REF]. Compared with the conference paper, the current paper extends significantly the probabilistic model, incorporating random polynomials whose coefficient are subexponential, and extends significantly the treatment of the univariate case, adding several new results. Among these results, one can find polynomial (in the size of the support and logarithm of the degree) bounds for all the moments of the size of the subdivision tree of Descartes' solver and for the bit complexity of the algorithm by [START_REF] Jindal | Efficiently computing real roots of sparse polynomials[END_REF] for solving a random sparse polynomial. The latter, to our knowledge, is the first such bound.

Notation. We denote by P n,d the space of polynomials in n variables of total degree at most d. Then a polynomial is f = |α|≤d f α X α ∈ P n,d , where α ∈ N n ; nevertheless, we commonly omit the summation index. By H n,d we denote the space of homogeneous polynomials of degree d in n + 1 variables.

The unit cube is

I n := [-1, 1] n ⊂ R n and B C (x, r) is the complex disk centered at x with radius r. The polydisc is D n := B C (x, 1) n ⊆ C n .
For A ⊆ R n , we denote by B(A) the set of boxes (i.e., cubes) contained in A. For any B ∈ B(R n ), we denote by m(B) its midpoint and by w(B) its width, so that

B = m(B) + w(B)/2[-1, 1] n .
Outline of the paper. In the next section, we outline and discuss the main results of the paper: the average run-time of the Plantinga-Vegter algorithm, and the average size of the subdivsion tree of Descartes' solver and the average run-time of the algorithm by [START_REF] Jindal | Efficiently computing real roots of sparse polynomials[END_REF]. In Section 3, we introduce the norms with which we will be working and their main properties. In Section 4, we introduce a new condition number adapted to the introduced norms and we prove its main properties. In Section 5, we perform the condition-based complexity analysis of the subdivision routine of the Plantinga-Vegter algorithm; and in Section 6, we introduce the separation bound, give condition-based bounds for it and apply them to the Descartes' solver and the solver by [START_REF] Jindal | Efficiently computing real roots of sparse polynomials[END_REF]. Finally, in Section 7, we introduce the randomness model that we will consider, zintzo random polynomials and p-zintzo random polynomials and provide the relevant probabilistic bounds to prove our results.

Overview

We present a condition-based framework that allows us to control the probability of numerical algorithms with respect to random polynomials that are sparse and do not have any scaling in their coefficients, as it has been usual with the so-called KSS or dobro random polynomials introduced in [START_REF] Cucker | Plantinga-Vegter Algorithm Takes Average Polynomial Time[END_REF]. We illustrate our techniques by analyzing the expected complexity of the Plantinga-Vegter algorithm and the univariate solvers Descartes and JindalSagraloff for a class of random sparse polynomials.

We will consider a very general class of random polynomials: the class of zintzo random polynomials (see Definition 7.8). Moreover, our probabilistic estimates are both in the average and smoothed paradigm (see Proposition 7.12). However, for the sake of concreteness, we will expose our results here only for Gaussian and uniform random polynomials.

Definition 2.1. Let M ⊆ N n be such that it contains 0, e 1 , . . . , e n .

(G) A Gaussian polynomial supported on M is a random polynomial f = α∈M f α X α supported on M whose coefficients f α are i.i.d. Gaussian random variables of mean 0 and variance 1.

(U) A uniform random polynomial supported on M is a random polynomial f = α∈M f α X α supported on M whose coefficients f α are i.i.d. uniform random variables on [-1, 1].

The condition 0, e 1 , . . . , e n ∈ M is a technicality that we need for the proofs. In layman's terms, this technical condition states that all the terms of the first order approximation of f at 0,

f 0 + f e 1 X 1 + • • • + f e n X n
, appear with probability one. When we translate this condition to an homogeneous setting, this condition would be translated into M ⊆ {(d -1)e i + e j | i, j ∈ {0, . . . , n}}, which means that the support would contain not only the vertices of the standard simplex, but also the adjacent lattice points to those vertices. We observe this sparseness condition, considered already by [START_REF] Renegar | On the efficiency of Newton's method in approximating all zeros of a system of complex polynomials[END_REF], is a kind of pseudo-sparseness condition. Nevertheless, we note that this is an improvement over the restrictions of other existing analysis such as the one by [START_REF] Ergür | Probabilistic Condition Number Estimates for Real Polynomial Systems II: Structure and Smoothed Analysis[END_REF].

Expected complexity of the Plantinga-Vegter algorithm

The probabilistic complexity bound for the subdivision routine of the Plantinga-Vegter algorithm, PV-Subdivsion, is the following one. We refer to Section 5 for more details on the Plantinga-Vegter algorithm.

Theorem 2.2. Let f ∈ P n,d be a random polynomial supported on M. The average number of boxes of the final subdivision of PV-Subdivsion using the interval approximations (3) and (4) on input f is at most 2n if f is uniform.

We notice that the above theorem is a particular case of Theorem 7.19, which gives the claim for the more general class of zintzo random polynomials.

We notice that the bounds on the number of boxes are polynomial in the degree, as in [START_REF] Cucker | Plantinga-Vegter Algorithm Takes Average Polynomial Time[END_REF]. This is an additional theoretical justification of the practical success of the Plantinga-Vegter algorithm. However, unlike the estimates in [START_REF] Cucker | Plantinga-Vegter Algorithm Takes Average Polynomial Time[END_REF], the bounds we present justify the success of the Plantinga-Vegter algorithm even for sparse random polynomials. This is one of the first such probabilistic complexity estimates in numerical algebraic geometry.

Complexity results on univariate solvers

In the setting of univariate solvers, we present two results. First for the Descartes solver in [START_REF] Sagraloff | Computing real roots of real polynomials[END_REF] we bound the average size of the subdivision tree. Second, we bound the average bit complexity of algorithm by [START_REF] Jindal | Efficiently computing real roots of sparse polynomials[END_REF] for isolating the roots of sparse univariate polynomial. In both cases, we don't only bound the average (1st moment), but all the higher moments.

Theorem 2.3. Let f ∈ P n,d be a random polynomial supported on M that is either Gaussian or uniform. The average size of the subdivision tree of Descartes on input f is at most

O |M| log d .
Moreover, the kth moment of the size is bounded by

O k|M| log d k .
The above result shows that Descartes' univariate solver can perform well in practice for sparse polynomials in [-1, 1]. It shows that in average the size of the subdivision tree will be polynomial in the size of the sparse polynomial. This provides an insight on the special character of Mignotte-like 4-mials. The above theorem is a particular case of Theorem 7.23, which states the result for zintzo random polynomials.

Theorem 2.4. Let f ∈ P n,d be a random polynomial supported on M that is either Gaussian or uniform. The average bit-complexity of JindalSagraloff on input (f, I) is at most

O |M| 12 log 7 d .
Moreover, the kth moment of the bit-run-time is bounded by

O k|M| 12 log 7 d k .
This theorem provides a first step into the solution of the Rojas-Ye version of Smale's 17th problem for sparse systems [START_REF] Rojas | On solving univariate sparse polynomials in logarithmic time[END_REF]. The later theorem is a particular case of Theorem 7.24, where the claim is shown for a restricted class of zintzo random polynomials. In future work, we hope to be able to extend this analysis to polynomials distributed not only with continuous probability distributions, but with discrete probability distributions.

Norms for the cube and polynomials over the cube

In the traditional setting, for homogeneous polynomial F = |α|=d F α X α ∈ H n,d of degree d in n + 1 variables, we consider the Weyl norm,

F W := α d α -1 |F α | 2 ,
to control the evaluations of the polynomial, F(p), and its gradient, ∇ p F, at points p ∈ S n . Unfortunately, the scaling introduced by the norm in the coefficients affects the probabilistic model and forces us to consider random polynomials with a particular variance structure that excludes Gaussian polynomials.

To avoid the scaling of the coefficients, we work in the cube and we will use the ∞-norm,

x ∞ := max i |x i |.
One of the main disadvantages of this norm is that it does not come from an inner product. However, we can overcome this problem as shown by Cucker et al. (2020a).

For P n,d , the space of affine polynomials of degree at most d in n variables. For a polynomial f := |α|≤d f α X α ∈ P n,d , motivated by duality, we consider the following norm

f 1 := α | f α |.
(1)

To demonstrate that all the results generalize to the complex case we will prove the various bounds for polydics, z ∈ D n := B C (0, 1) n , which is the complex analogous of the cube.

The motivation to choose the 1-norm emanates from the following proposition which shows that we can control the evaluation of f at x ∈ I n := [-1, 1] n , that is f (x), using the 1-norm for f .

Proposition 3.1. Let f ∈ P n,d and z ∈ D n . Then | f (z)| ≤ f 1 . Proof. It holds | f (z)| = α f α z α ≤ α | f α | z |α| ∞ ≤ f 1 ; as z ∈ D n implies that z ∞ ≤ 1.
Remark 3.2. A reader might wonder why we do not choose another norm. For example, if we choose

f 2 := α | f α | 2 , then we can prove that for all z ∈ D n , it holds | f (z)| ≤ √ N f 2 ,
where N is the number of terms in f . This gives worse bounds than using f 1 since

f 2 ≤ f 1 ≤ √ N f 2 ,
which makes us prefer f 1 to √ N f 2 as a bounding quantity.

Notation 3.3. Before continuing, let us clarify notations so that the statements that we consider are clear. By convention,

D f := ∂ f ∂X 1 • • • ∂ f ∂X n
represents the formal tangent covector of f , whose entries are the formal partial derivatives of f . Similarly, the formal tensor of kth derivatives of f is

D k f := ∂ k f ∂X i 1 •∂X i k i 1 ,••• ,i k .
When we want to refer to the gradient vector, the tangent covector or the tensor of kth derivatives of f (evaluated) at a point z ∈ R n , we will use respectively D z f and D k z f . Thus we have that

D z f is a covector T z (R n ) R n → R and that D k z f is a multilinear map T z (R n ) k (R n ) k → R.
An important feature of the 1-norm is that for polynomials we can use it to control the 1-norm of their derivatives. In our notation

, if v 1 , . . . , v k ∈ R n and f ∈ P n,d , then D k f (v 1 , . . . , v k ) is a polynomial of degree ≤ d -k and so it makes sense to compute its 1-norm. Proposition 3.4. Let f ∈ P n,d and v ∈ R n . Then D f (v) 1 ≤ d f 1 v ∞ . In particular, for all z ∈ D n , | D z f (v)| ≤ d f 1 v ∞ . Corollary 3.5. Let f ∈ P n,d , d ≥ k ≥ 0 and v 1 , . . . , v k ∈ R n . Then 1 k! D k f (v 1 , . . . , v k ) 1 ≤ d k f 1 v 1 ∞ • • • v k ∞ .
In particular, for all

z ∈ D n , 1 k! D k z f (v 1 , . . . , v k ) ≤ d k f 1 v 1 ∞ • • • v k ∞ .
Proof of Proposition 3.4. We have

d f 1 v ∞ = α d| f α | v ∞ and D f (v) 1 ≤ α | f α | D X α (v) 1 .
Therefore, it is enough to prove the claim for X α . By a simple computation, we get

D X α (v) 1 = n i=1 α i v i X α /X i 1 ≤ n i=1 α i |v i | ≤ α 1 v ∞ ≤ d v ∞ ,
which is the desired inequality for the 1-norm. The last claim is Proposition 3.1.

Proof of Corollary 3.5. By induction hypothesis, we have that

1 k! D k f (v 1 , . . . , v k ) 1 = 1 k 1 (k -1)! D k-1 (D f (v k )) (v 1 , . . . , v k-1 ) 1 ≤ 1 k d -1 k -1 D f (v k ) 1 v 1 ∞ • • • v k-1 ∞ .
Proposition 3.4 finishes the induction step and provides the base case for induction. The last claim is again Proposition 3.1.

The bounds on the derivatives allows us to bound the (Lipschitz constants) of the variations of a polynomial f and all its derivatives inside D n .

Proposition 3.6. Let f ∈ P n,d , d ≥ k ≥ 0 and v 1 , . . . , v k ∈ R n such that v i ∞ = 1. Then the map D n → [-1, 1] n z → 1 d k f 1 D k z f (v 1 , . . . , v k )
is well-defined and (dk)-Lipschitz with respect the ∞-norm.

Proof. Without loss of generality, assume that f 1 = 1. Let x, y ∈ D n . By the fundamental theorem of calculus,

D k y f (v 1 , . . . , v k ) -D k x f (v 1 , . . . , v k ) = 1 0 D k ty+(1-t)x f (v 1 , . . . , v k , y -x) dt.
Hence, taking absolute values and using Corollary 3.5, we get that

1 d k D k y f (v 1 , . . . , v k ) - 1 d k D k x f (v 1 , . . . , v k ) ≤ d! d k (d -k -1)! y -x ∞ ≤ (d -k) x -y ∞ ,
which gives the Lipschitz property. The choice of the co-domain follows from Corollary 3.5.

Recall that for a multilinear map

A : (R n ) k → R we can consider the induced norm A ∞,∞ := sup v 1 ,...,v k 0 |A(v 1 , . . . , v k )| v 1 ∞ • • • v k ∞ , instead of the 1-norm A 1 := i 1 ,...,i k |A i 1 ,...,i k |.
Although A ∞,∞ ≤ A 1 is not an equality in general, it is so in the case that A is a linear map, which allows us to deduce the following.

Proposition 3.7. Let f ∈ P n,d and d ≥ k ≥ 0. Then the map

D n → [0, 1] n z → 1 d k f 1 D k z f ∞,∞
is well-defined and (dk)-Lipschitz with respect the ∞-norm.

Proof. Without loss of genreality, assume that f 1 = 1. By Proposition 3.6, we have that for all x, y ∈ D n and all v 1 , . . . ,

v k ∈ R n such taht v i ∞ = 1, 1 d k D k y f - 1 d k D k x f (v 1 , . . . , v k ) ≤ (d -k) y -x ∞ .
By maximixing the left-hand side with respect v 1 , . . . , v k , we get that for all x, y ∈ D n ,

1 d k D k y f - 1 d k D k x f ∞,∞ ≤ (d -k) y -x ∞ .
This gives the Lipzchitz property. The choice of codomain is justified in a similar way.

Corollary 3.8. Let f ∈ P n,d . Then the maps

D n → [0, 1] z → 1 f 1 | f (z)| and D n → [0, 1] z → 1 d f 1 D z f 1
are well-defined and d-Lipschitz with respect the ∞-norm.

Proof. Just note that D z f ∞,∞ = D z f 1 .
The rest is straightforward from Proposition 3.7.

We finish with a slightly stronger version of some of the above results that will be useful later. When we are outside the polydisk D n , then the non-linear factors of the polynomials dominate. However, we can retain control around D n if we are not too far.

Proposition 3.9. Let f ∈ P n,d , ε > 0 and D n ε := B C (0, 1 + ε) n . If ε ≤ 1 d , then: 1. For all z ∈ D n ε , k ≥ 0, and all v 1 , . . . , v k ∈ R n , 1 k! D k z f (v 1 , . . . , v k ) ≤ e d k f 1 v 1 ∞ • • • v k ∞ .
2. The maps

D n ε → [0, e] z → 1 f 1 | f (z)| and D n ε → [0, e] z → 1 d f 1 D z f 1
are well-defined and ed-Lipschitz with respect the ∞-norm.

Proof. We consider the polynomial

g := f ((1 + ε)X) .
We can see that

g 1 ≤ e f 1 ,
since for k ∈ {0, 1, . . . , d},

(1 + ε) k ≤ 1 + 1 d d ≤ e. Moreover, for z ∈ D n ε , D k z f = 1 (1 + ε) k D k z/(1+ε) g,
and so, by Corollary 3.5,

1 k! D k z f ≤ 1 (1 + ε) k d k g 1 ≤ e d k f 1 .
This proves 1. Point 2 follows from point 1 in the same way we prove Corollary 3.8 from Corollary 3.5 (after passing through Propositions 3.6 and 3.7).

Condition and its properties

In this section, we define and study the properties of the condition number. The following definition adapts the real local condition number (Bürgisser and Cucker, 2013, Chapter 19) (cf. [START_REF] Cucker | Computing the Homology of Real Projective Sets[END_REF]) to our setting. Definition 4.1. Let f ∈ P n,d and x ∈ I n , the local condition number of f at x is the quantity

C 1 ( f, x) := f 1 max | f (x)|, 1 d D x f 1 .
The intuition behind this condition number is simple. It holds C 1 ( f, x) = ∞ if and only if x is a singular zero of f . Thus C 1 ( f, x) measures how close is f to have a singularity at x. An important point to note is that, since we will be dealing with problems from real algebraic geometry, we do not only have to guarantee that zeros are smooth, but also that they exist. The latter is the reason why the term | f (x)| appears in the denominator and it is fundamental in numerical real algebraic geometry, where a perturbation of a polynomial not only perturbs the zeros, but also can make them disappear.

In (Tonelli-Cueto, 2019, 2 §2 ) a series of explicit properties of the condition number are underlined as the important properties to carry out a condition-based complexity analysis. These properties are: the regularity inequality, the 1st and the 2nd Lipschitz property, and the higher derivative estimate. The following theorem shows that the condition number in (4.1) has these properties. We recall that Smale's gamma, γ, is the invariant2 given by

γ( f, z) := sup k≥2 1 D z f 2 1 k! D k z f 2,2 1 k-1 , (2)
for a polynomial f ∈ P n,d and z ∈ C n , where • 2,2 is the induced norm for multilinear maps for the usual Euclidean norm.

Theorem 4.2. Let f ∈ P n,d and x ∈ I n . Then:

• Regularity inequality: Either | f (x)| f 1 ≥ 1 C 1 ( f, x) or D x f 1 d f 1 ≥ 1 C 1 ( f, x)
.

In particular, if C 1 ( f, x) | f (x)| f 1 < 1, then D x f 0. • 1st Lipschitz inequality: The map P n,d → [0, ∞) g → g 1 C 1 (g, x)
is 1-Lipschitz with respect the 1-norm. In particular, C 1 ( f, x) ≥ 1.

• 2nd Lipschitz inequality: The map

I n → [0, 1] y → 1 C 1 ( f, y) is d-Lipschitz with respect the ∞-norm. • Higher derivative estimate: If C 1 ( f, x) | f (x)| f 1 < 1, then γ( f, x) ≤ √ n(d -1) 2 C 1 ( f, x).
Remark 4.3. We note that the theorem still holds if we replace I n by D n .

Before continuing with the proof of Theorem 4.2, let's discuss why these properties are important for us.

• The regularity inequality tells us (in a quantitative way depending on the condition number) that either the value of f at a point x is big or that the gradient of f at that point x is big. In this way, the regularity inequality guarantees us that the covector field x → D x f does not vanish near the zero set of f . The latter allows us to guarantee that the Newton operator is well-defined or that geometric arguments based on following the gradient flow work near the zero set.

• The 1st and 2nd Lipschitz properties allow us to guarantee that C 1 ( f, x) can be numerically evaluated at ( f, x), since it guarantees us that C 1 ( f, x) can be bounded by C 1 ( f , x) for sufficiently good approximations f of f and x of x. Making this concrete, we have that

C 1 ( f, x) ≤ C 1 f , x 1 -C 1 f , x 2 f -f 1 f 1 + x -x ∞ ≤ C 1 f , x (1 + δ), whenever 2 f -f 1 f 1 + x -x ∞ < 1 C 1 ( f , x)
δ for some δ ∈ (0, 1).

• The higher derivative estimate allows us to control how the Newton method converges near the zero set. This is based on Smale's α-theory, which can be found in (Bürgisser and Cucker, 2013, 15.2) and [START_REF] Dedieu | Points fixes, zéros et la méthode de Newton[END_REF], Chapter 4) among many other references.

Proof of Theorem 4.2. For the regularity inequality, note that 1

C 1 ( f,x) is the maximum of | f (x)| f 1 and D x f 1 d f 1 .
Note that we don't only get an inequality, but an equality, but this is not important for later arguments.

For the 1st Lipschitz property, let g 0 , g 1 ∈ P n,d . Then:

g 0 1 C 1 (g 0 , x) - g 1 1 C 1 (g 1 , x) = max |g 0 (x)|, 1 d D x g 0 1 -max |g 1 (x)|, 1 d D x g 1 1 (Definition 4.1 ≤ max |g 0 (x) -g 1 (x)|, 1 d D x g 0 -D x g 1 1 (Triangle inequality) ≤ max |(g 0 -g 1 )(x)|, 1 d D x (g 0 -g 1 ) 1 ≤ g 0 -g 1 1 (Corollary 3.8)
Note that we use that the codomain is [0, 1] in Corollary 3.8. For the later inequality, note that 0 1

C 1 (0,x) = 1 (or simply use Corollary 3.8 again).

For the 2nd Lipschitz property, the argument is similar to the one above. Without loss of generality, assume that f 1 = 1. Let y 0 , y 1 ∈ I n , then:

1 C 1 ( f, y 0 ) - 1 C 1 ( f, y 1 ) = max | f (y 0 )| f 1 , D y 0 f 1 d f 1 -max | f (y 1 )| f 1 , D y 1 f 1 d f 1 (Definition 4.1 ≤ max | f (y 0 )| f 1 - | f (y 1 )| f 1 , D y 0 f 1 d f 1 - D y 1 f 1 d f 1 (Triangle inequality) ≤ y 0 -y 1 ∞ (Corollary 3.8)
For the higher derivative estimate, note that for a multilinear map

A : (R n ) k → R, A 2,2 = sup x 1 ,...,x k 0 |A(x 1 , . . . , x k )| x 1 2 • • • x k 2 ≤ sup x 1 ,...,x k 0 |A(x 1 , . . . , x k )| x 1 ∞ • • • x k ∞ = A ∞,∞ ,
since z 2 ≥ z ∞ for all z, and that for a linear map a : R n → R,

a 2 ≥ a 1 √ n .
In this way, for k ≥ 2,

1 D x f 2 1 k! D k x f 2,2 ≤ √ n D x f 1 1 k! D k x f ∞,∞ = √ n f 1 D x f 1 1 k! D k x f ∞,∞ f 1 .
By the above, the regularity inequality and Corollary 3.5, the above becomes

1 D x f 2 1 k! D k x f 2,2 ≤ √ n d C 1 ( f, x) d k = √ n d d k 1 C 1 ( f, x) . Now, for k ≥ 2, 1 C 1 ( f,x) 1 k-1 ≤ 1 C 1 ( f,x) , since C 1 ( f, x) ≥ 1, and √ n d d k 1 k-1 ≤ √ n ((d -1) • • • (d -k + 1)) 1 k-1 (k!) 1 k-1 ≤ √ n(d -1) 2 , since (k!) 1 k-1 ≥ 2.
This finishes the proof.

Using the above theorem, we can provide a sort of geometric interpretation of the condition number above. Fix x ∈ I n and consider

Σ x := {g ∈ P n,d | g(x) = 0, ∇ x g = 0} ⊂ P n,d ,
which is the subset of polynomials that are singular at 0. The following proposition, usually referred as 'Condition Number Theorem' relates the distance of a polynomial to Σ x to the defined condition number. Although the version we provide does not give an equality, it provides a bound in both relations.

Proposition 4.4 (Condition Number Theorem). For all f ∈ P n,d and x ∈ I n ,

f 1 dist 1 ( f, Σ x ) ≤ C 1 ( f, x) ≤ (1 + d) f 1 dist 1 ( f, Σ x )
,

where dist 1 is the distance induced by the 1-norm.

Proof. The left hand side follows from the 1st Lipschitz property (Theorem 4.2), since for g ∈ Σ x ,

f 1 C 1 ( f, x) = f 1 C 1 ( f, x) - g 1 C 1 (g, x) ≤ f -g 1 .
Thus, minimizing for

g ∈ Σ x , f 1 C 1 ( f, x) ≤ dist 1 ( f, Σ x ).
For the right hand side, consider the polynomial

g := f -f (x) - n i=1 ∂ i f (x)X i . Then g ∈ Σ x and f -g 1 ≤ | f (x)| + D x f 1 . Hence dist 1 ( f, Σ x ) ≤ f -g 1 ≤ (1 + d) max | f (x)|, 1 d D x f 1 = (1 + d) f 1 C 1 ( f, x) ,
as desired.

We conclude this section, introducing the global condition number and stating its properties.

Definition 4.5. Let f ∈ P n,d , the global condition number of f is the quantity

C 1 ( f ) := max{C 1 ( f, x) | x ∈ I n }.
Notice that C 1 ( f ) is infinity if and only if the zero set of f has a singularity in I n . The following proposition quantifies this fact, which interprets geometrically f . We denote by

Σ n,d := {g ∈ P n,d | for some x ∈ I n , g(x) = 0, D x g = 0} = x∈I n Σ x ⊂ P n,d
the set of polynomials whose zero sets have a singularity in I n .

Proposition 4.6. The map

f → f 1 C 1 ( f ) is 1-Lipschitz. Moreover, for every f ∈ P n,d , f 1 dist 1 ( f, Σ n,d ) ≤ C 1 ( f ) ≤ (1 + d) f 1 dist 1 ( f, Σ n,d )
,

where dist 1 is the distance induced by the 1-norm.

Proof. This follows immediately from the 1st Lipschitz property, Theorem 4.2 and the Condition Number Theorem (Proposition 4.4).

Plantinga-Vegter Algorithm and its complexity

The Plantinga-Vegter algorithm [START_REF] Plantinga | Isotopic approximation of implicit curves and surfaces[END_REF]) is a subdivision-based algorithm that computes an isotopically correct approximation of the zeros of a univariate polynomial in an interval, of a curve in the plane, or of a surface in the 3-dimensional space. This algorithm can be generalized to hypersurfaces of arbitrary dimension as shown by [START_REF] Galehouse | Topologically accurate meshing using domain subdivision techniques[END_REF] and to singular curves as shown by [START_REF] Burr | Complete subdivision algorithms, II: Isotopic meshing of singular algebraic curves[END_REF].

Following [START_REF] Burr | The complexity of an adaptive subdivision method for approximating real curves[END_REF] 2020b) did a complexity analysis of the Plantinga-Vegter algorithm for all three levels. However, our objective is not to reproduce the analysis in (Cucker et al., 2020b) to the last detail, but to show that changing from the Weyl norm to the 1-norm improves the complexity. For this reason, we only focus on the interval level. We do this, because if we reproduce all the arguments for the effective level, then the analysis would not only be technically tedious, but will also distract us from highlighting the complexity improvement.

While analyzing the interval level, we estimate the number of boxes of the final subdivision. This is our measure of complexity. We refer to [START_REF] Burr | The complexity of an adaptive subdivision method for approximating real curves[END_REF], Cucker et al. (2020b) and (Tonelli-Cueto, 2019, 5 §2 ) for further justifications of this approach.

Interval version of the PV Algorithm

The subdivision routine of the PV algorithm, PV-Subdivsion, relies on subdividing the unit cube I n until each box B in the subdivision satisfies the condition

C f (B) : either 0 f (B) or 0 D x f D y f T | x, y ∈ B . Note that D x f D y f T = n i=1 ∂ i f (x)∂ i f (y)
, as D z f is a covector (and so a row-vector). To implement this algorithm one uses interval arithmetic. Recall that an interval approximation of a map g :

I n → R q is a map [g] : [I n ] → [R q ],
where [X] is the set of (coordinate) boxes contained in X, such that for all B ∈ [I n ], we have

g(B) ⊆ [g](B).
The following proposition provides interval approximations for f and D f 1 .

Proposition 5.1. Let f ∈ P n,d . Then [ f ](B) := f (m(B)) + d f 1 w(B) 2 [-1, 1] (3)
and

[ D f 1 ](B) := D m(B) f 1 + √ 2nd 2 f 1 w(B) 2 [-1, 1]. ( 4
)
Proof. We only need to show, respectively, that

f (B) ⊆ f (m(B)) + d f 1 w(B) 2 [-1, 1] and that D f 1 (B) ⊆ ∇ m(B) f 1 + d 2 f 1 w(B) 2 [-1, 1].
However, this follows from Corollary 3.8. We now show how to test C f (B) using the above interval approximations. The reason we have the factor √ n in (4) is so that the next proposition provides a nicer statement.

Proposition 5.2. The condition C f (B) is implied by the condition

C f (B) : | f (m(B))| > d f 1 w(B) 2 or D m(B) f 1 > d 2 √ 2n f 1 w(B) 2 15
Hence, PV-Subdivsion with the interval approximations given in (3) and ( 4) is correct if we substitute the condition C f (B) by

C f (B) : either 0 [ f ](B) or 0 [ ∇ f 1 ](B).
Proof. On the one hand, by Corollary 3.8, the map

| f | is d f 1 -Lipschitz. Thus | f (m(B))| > d f 1 w(B) 2 implies that for all x ∈ B, | f (x)| ≥ | f (m(B))| -d f 1 w(B)
2 . This is the first clause of C f (B).

On the other hand, by (Cucker et al., 2019, Lemma 4.4), we have that if for all x ∈ B,

D x f -D m(B) f 2 ≤ 1 √ 2 D m(B) f , then for all x, y ∈ B, D x f D y f T 0, which is the second clause of C f (B). For x ∈ B, D x f -D m(B) f 2 ≤ D x f -D m(B) f 1 ≤ d 2 f 1 w(B) 2 , due to Corollary 3.8. Hence d 2 f 1 w(B) 2 ≤ 1 √ 2 D m(B) f 2 implies the second clause of C f (B), and so does D m(B) f 1 ≥ d 2 √ 2n f 1 w(B), since y 1 ≤ √ n y 2 .

The two paragraphs above together give the desired claim.

In what follows the interval version of PV-Subdivsion will be a variant that exploits the interval approximations in (3) and (4).

Complexity analysis of the interval version

As in [START_REF] Burr | The complexity of an adaptive subdivision method for approximating real curves[END_REF] and [START_REF] Cucker | Plantinga-Vegter Algorithm Takes Average Polynomial Time[END_REF], our complexity analysis relies on the construction of a local size bound for PV-Subdivsion and the application of the continuous amortization developed by [START_REF] Burr | Continuous amortization: A non-probabilistic adaptive analysis technique[END_REF]; [START_REF] Burr | Continuous amortization and extensions: with applications to bisection-based root isolation[END_REF].

We recall the definition of the local size bound and the result that we will exploit in our complexity analysis.

Definition 5.3. A local size bound for the interval version of PV-Subdivsion on input

f is a function b f : I n → [0, 1] such that for all x ∈ R n , b f (x) ≤ inf{vol(B) | x ∈ B ∈ B(I n ) and C f (B) false}.
Theorem 5.4. [START_REF] Burr | Continuous amortization: A non-probabilistic adaptive analysis technique[END_REF][START_REF] Burr | Continuous amortization and extensions: with applications to bisection-based root isolation[END_REF][START_REF] Burr | The complexity of an adaptive subdivision method for approximating real curves[END_REF] The number of boxes of the final subdivision of the interval version of PV-Subdivsion on input f is at most

4 n E x∈I n 1 b f (x)
.

In addition, the bound is finite if and only if PV-Subdivsion terminates.

Theorem 5.5. The function

x → d √ 2n C 1 ( f, x) -n
is a local size bound for PV-Subdivsion on input f .

Proof. Without loss of generality, assume that f 1 = 1. Let x ∈ B ∈ B(I n ). Then m(B)x ∞ ≤ w(B)/2 and so, by Corollary 3.8 and the regularity inequality (Theorem 4.2), we have that either

| f (m(B))| > 1 C 1 ( f, x) -d w(B) 2 (5) or D m(B) f 1 > d 1 C 1 ( f, x) -d 2 w(B) 2 . ( 6
)
Hence, C f (B) is true as long as either

C 1 ( f, x) -1 ≥ dw(B), or C 1 ( f, x) -1 > d √ 2nw(B). The result follows, since vol(B) = w(B) n .
Theorem 5.4 and Theorem 5.5 result the following corollary, which is the preamble of one of our results.

Corollary 5.6. The number of boxes of the final subdivision of the interval version of PV-Subdivsion on input f is at most

2 5 2 n n n 2 d n E x∈I n C 1 ( f, x) n .
Theorem 7.19 follows now from the corollary above and the following proposition.

Remark 5.7. A similar argument as in the proof of (Cucker et al., 2019, Theorem 6.4) shows that we can bound the local size bound of [START_REF] Burr | The complexity of an adaptive subdivision method for approximating real curves[END_REF] in terms of 1/ C 1 ( f, x) n . Since the interval approximation of the analyzed version is simpler, requiring a single evaluation, we only analyze the complexity of this.

Remark 5.8. We note that previous bound can be generalized for a cube [-a, a] n bigger than the unit cube. A straightforward argument might try to consider the polynomial f (aX) which considered on I n behaves like f inside [-a, a] n . Unfortunately, f (aX) 1 ≤ a d f 1 , which will complicated things as the bounds would become exponential in the degree. To avoid this, one should reprove Corollary 3.8. The trick is to consider the maps

x → | f (x)| d f 1 max 1, x d ∞ and x → | f (x)| d 2 f 1 max 1, x d-1
∞ and prove that they are Lipschitz. Let us demonstrate this approach for the first map. We only have to consider the map as the composition of

∂I n x 0 x → x d 0 d f 1 f x x 0 together with R 1+n x → 1 max {1, x ∞ } 1 x ∈ ∂I n ,
and since each map is Lipschitz, this is also the case for their composition.

Condition, separation bounds and univariate solvers

In this section we turn our attention to the separation of the roots of a real univariate polynomial. In general, we are interested in the separation between the real roots and the separation between the conjugate complex roots, as these affect the complexity of some univariate solvers. As we will focus on searching roots in I, we will consider the following separation quantities. Definition 6.1. Let f ∈ P 1,d . Then we define:

(R) The real separation of f , ∆( f ), is given by

∆( f ) := min ζ -ζ | ζ, ζ ∈ I, f (ζ) = f ζ = 0 ,
if f has no double roots in I, and it is zero otherwise.

(C) Let ε ∈ 0, 1 d . The ε-real separation of f , ∆ ε ( f ), is ∆ ε ( f ) := min ζ -ζ | ζ, ζ ∈ I ε := {z ∈ Z | dist(z, I) ≤ ε}, f (ζ) = f ζ = 0 ,
if f has no double roots in I and it is zero otherwise.

We observe that ∆( f ) gives the minimum distance between two roots of f in I, while ∆ ε ( f ) takes into account how near to the real line complex roots near I are. The quantity ∆( f ) plays a role controlling the complexity of univariate solvers that do not depend on the complex roots, such as the Sturm's solver, while ∆ ε ( f ) plays a role controlling the complexity of of univariate solvers that depend on the complex roots near the real line, such as the Descartes' solver.

Our objective is to give lower bounds on these two quantities in terms of the condition number and use them for analysing two univariate solvers: Descartes and JindalSagraloff.

Condition-based bounds for separation

For bounding the real separation, we follow the ideas of [START_REF] Raffalli | Distance to the discriminant[END_REF] which allow us to obtain a bound depending on the square root of the global condition number. The main idea is to exploit that between two consecutive roots there is a point where the derivative vanishes and so a point where the Taylor expansion becomes quadratic. Theorem 6.2. Let f ∈ P 1,d . Then

∆( f ) ≥ 2 √ 2 d C 1 ( f )
.

Proof. Let ζ, ζ ∈ I be the pair of real roots of f in I with the minimum distance. By Rolle's theorem, there is x 0 ∈ I between these roots such that

f (x 0 ) = 0.
Without loss of generality assume that ζ is the roots closest to x 0 , so that ζζ /2 ≥ |x 0 -ζ|.

Then by Taylor's theorem,

0 = f (ζ) = f (x 0 ) + 1 2 f (x)(ζ -x 0 ) 2 ,
for some x ∈ I between ζ and x 0 . Hence

| f (x 0 )| = 1 2 | f (x)||ζ -x 0 | 2 ≤ ζ -ζ 2 8 | f (x)| = (∆( f )) 2 8 | f (x)|.
Since f (x 0 ) = 0, we obtain the desired result dividing by f 1 and applying Corollary 3.5.

For the ε-real separation bound, our results are based on [START_REF] Dedieu | Estimations for the Separation Number of a Polynomial System[END_REF], Theorem 3.2 and Theorem 5.1). The main idea is to use the higher derivative estimate and the fact that the inverse of the Smale's γ is Lipschitz.

Theorem 6.3. Let f ∈ P 1,d . Then for all ε ∈ 0, 1 ed C 1 ( f ) , ∆ ε ( f ) ≥ 1 12d C 1 ( f ) .
Proof. Let ζ ∈ I ε be a complex root. By (Dedieu, 2006, Théorème 91), the Newton method converges for any point in

B C (ζ, 1/(6γ( f, ζ)), where γ is Smale's gamma. Hence, taking ζ ∈ I ε maximizing γ( f, ζ), we have that 1 3γ( f, ζ) ≤ ∆ ε ( f ), since 1 3γ( f,ζ)
is the distance from ζ to the rest of the roots of f . By (Dedieu, 2006, Lemme 98),

γ( f, ζ) ≤ γ( f, x) (1 -γ( f, x)ε)(1 -4γ( f, x)ε + 2γ( f, x) 2 ε 2 )
for some x ∈ I such that |ζ -x| ≤ ε.

By Proposition 3.9, we have that

| f (x)| f 1 ≤ edε ≤ 1 C 1 ( f, x) ,
where the last inequality is by assumption. Hence, by the above inequality and the higher derivative estimate (Theorem 4.2),

γ( f, ζ) ≤ 4(d -1) C 1 ( f, x), since γ( f, x)ε ≤ 1 2e . Hence 1 3γ( f, ζ) ≥ 1 24(d -1) C 1 ( f ) ,
which concludes the proof.

Complexity of univariate solvers

By "univariate solver", we refer to an algorithm that given a univariate polynomial f ∈ P 1,d and an interval J where f has only simple roots, it outputs a set of isolating intervals for the roots of f in J. The latter means that we are focusing on finding real roots. In our case, we will focus in the case where the interval is I.

In general, an univariate solver will be of the form where the input is a polynomial f and the natural number L and the output, {B C (x i , r i )} t i=0 , is a disjoint family of complex disks with centers at I and radius at 2 -L , each containing at most n i roots; that is for all i it holds f -1 (0) ∩ B C (x i , r i ) ≤ n i . In the particular case, where it also holds that for all i,

1 ≤ f -1 (0) ∩ B C (x i , r i ) = n i ,
we say that {(x i , r i , n i )} t i=0 is an (I, L)-covering of f (Jindal and Sagraloff, 2017, Definition 1). In our computational model, the input polynomials will be bitstream polynomials (Eigenwillig, 2010, Definition 3.35), i.e., we can access the coefficients of the polynomial at any desired precision and we will consider the bit complexity. We will focus on two solvers: Descartes and JindalSagraloff.

Descartes Solver

Descartes is a prominent representative of the subdivision-based algorithms for isolating the real roots of polynomials, usually with integer coefficients. The algorithm is extremely efficient in practice [START_REF] Rouillier | Efficient isolation of polynomial's real roots[END_REF][START_REF] Hemmer | Experimental evaluation and cross-benchmarking of univariate real solvers[END_REF]. We refer to [START_REF] Eigenwillig | Real root isolation for exact and approximate polynomials using Descartes' rule of signs[END_REF] for general exposition about Descartes.

For simplicity, we would focus on the size of the subdivision tree of Descartes. Recall that the subdivision tree of a subdivision-based algorithm is the tree of intervals, ordered by containment, that the algorithm processes during its execution. Proposition 6.4. Given f ∈ P 1,d with support |M|, the algorithm Descartes computes isolating intervals for all the roots of f in I in at most O log C 1 ( f ) + log d iterations (this is the depth of the subdivision tree). In particular, the subdivision tree of Descartes at input ( f, I) has size

O |M| log C 1 ( f ) + log d .
Proof. We note that an interval J ⊆ I is a terminal interval for Descartes as long as B C (m(J), w(J)/2) does not contain roots or B C (m(J)+i √ 3w(J)/6, ) contains exactly one real root, by the one-circle and two-circles theorems (Mehlhorn and Sagraloff, 2011, Theorem 2). Hence the depth of the subdivision tree is at most O log max{ε -1 , ∆ ε ( f ) -1} for some ε > 0, and so, by Theorem 6.3, at most O log C 1 ( f ) + log d . Now, since f has support |M|, the number of sign variations in (0, ∞) and (-∞, 0) is at most O(|M|). Hence, no level of the subdivision tree can have more than O(|M|) nodes by the Schoenberg's theorem (Mehlhorn and Sagraloff, 2011, Theorem 3). This finishes the proof.

JindalSagraloff Solver

Jindal and [START_REF] Jindal | Efficiently computing real roots of sparse polynomials[END_REF] propose an algorithm, JindalSagraloff, to solve sparse polynomials. In this setting , the representation of the polynomial f ∈ P 1,d consists of its support M ⊂ N, which has size |M| log d, and a sequence of |M| coefficients.

Theorem 6.5. The algorithm JindalSagraloff outputs an (L, I)-covering of f on input ( f, L) ∈ P 1,d × N with f supported on M ⊆ N. The algorithm JindalSagraloff runs with at most

O |M| 12 log 3 d max{log 2 f 1 , L 2 } bit operations.
Proof. This is essentially (Jindal and Sagraloff, 2017, Lemma 8) rewritten. For the rest of the claims, one has just to read the assumptions in the introduction. Remark 6.6. We note that for dense polynomials the estimate of JindalSagraloff is far from optimal, because of that we will state many of the later results only as poly(|M|, log d), since determining the exact form of the polynomial does not lead to optimal bounds.

The following proposition it is based on the fact that in order to find the roots of a polynomial with an (I, L)-cover, we only need to compute (I, k)-covers until k > max{log ∆ ε ( f ), log ε -1 } for some ε > 0.

Proposition 6.7. Given f ∈ P 1,d with support |M|, the algorithm JindalSagraloff computes isolating intervals for all the roots of f in I with a run-time of

O |M| 12 log 3 d max{log 2 f 1 , log 3 C 1 ( f )} bit operations.
Proof. We only need to apply the bounds in Theorem 6.3.

Probability estimates of the condition number and complexity

We refine the techniques of [START_REF] Cucker | Plantinga-Vegter Algorithm Takes Average Polynomial Time[END_REF] to obtain explicit constants in the bounds and to deal with a restricted classes of sparse polynomials. We also add certain variations of the randomness models we consider. Of very special interest are the relaxation of the hypotheses

Probabilistic concepts and toolbox

We introduce now the relevant probabilistic definitions and results. There will be two kind of probabilistic results: tail bounds, mainly subgaussian and subexponential; and anti-concentration bounds.

Subgaussian and other tail bounds

The more usual tail bound is some form of Markov's inequality [START_REF] Vershynin | High-dimensional probability: An introduction with applications in data science[END_REF], Proposition 1.2.4) where for a random variable x ∈ R,

P( x ≥ t) ≤ E|x| k t k .
The variables in which we will focus will satisfy such a tail bound, but in an stronger sense.

Definition 7.1. (see Vershynin, 2018, 2.5 and 2.7) Let x ∈ R be a random variable.

(SE) We call x subexponential, if there exist a E > 0 such that for all t ≥ E,

P(|x| > t) ≤ 2 exp(-t 2 /E 2 ).
The smallest such E is the subexponential constant of x.

(SG) We call x subgaussian, if there exist a K > 0 such that for all t ≥ K,

P(|x| > t) ≤ 2 exp(-t 2 /K 2 ).
The smallest such K is the subgaussian constant of x.

(pSE) Let p ≥ 1. We call x p-subexponential, if there exist a L > 0 such that for all t ≥ L,

P(|x| > t) ≤ 2 exp(-t p /L p ).
The smallest such L is the p-subexponential of x.

Remark 7.2. We note that the technical term for the subexponetial, subgaussian and p-subexponential constants are, respectively, the ψ 1 -, ψ 2 -and ψ p -norms (see Vershynin, 2018, 2.5 and 2.7). However, note that these norms can be defined in many ways, although all of them are equivalent up to an absolute constant.

Remark 7.3. Note that we are not requiring the random variables to be centered, i.e., to have zero expectation. This plays a role into having an uniform approach for the average and smoothed analyses.

The main inequality is a variant of Hoeffding inequality which we will use in our bounds of the condition number.

Proposition 7.4. Let x ∈ R M be a random vector.

(SE) If for each α ∈ M, x α is subexponential with subexponential constant E α . Then for all t ≥ α E α , we have

P( x 1 ≥ t) ≤ 2|M| exp        -t/        α∈M K α               .
(SG) If for each α ∈ M, x α is subgaussian with subgaussian constant K α . Then for all t ≥ α K α , we have

P( x 1 ≥ t) ≤ 2|M| exp         -t 2 /        α∈M K α        2         . (pSE) Let p ≥ 1. If for each α ∈ M, x α is p-subexponential with subexponential constant L α .
Then for all t ≥ α L α , we have

P( x 1 ≥ t) ≤ 2|M| exp        -t p /        α∈M K α        p        .
Proof. We prove the last claim, as the other two are only particular cases of this. We have that for t ≥ α∈M L α ,

P α∈M |x α | ≥ t = P α∈M |x α | ≥ α∈M L α t/ α∈M L α        α∈M L α t/ α∈M L α = t        ≤ P ∃α ∈ M | |x α | ≥ L α t/ α∈M L α (Implication bound) ≤ |M| max α∈M P |x α | ≥ L α t/ α∈M L α (Union bound) ≤ 2|M| exp -t 2 / α∈M L α 2 , (Hypothesis)
where the implication bound is based on the fact that n i=1 x i ≥ n i=1 y i implies that for some i, x i ≥ y i and the application of the hypothesis follows from the fact that L α t/ α∈M L α ≥ L α for t ≥ α∈M L α .

Anti-concentration bounds

A random variable x ∈ R such that for some x ∈ R has P(x = x) > 0 is said to be concentrated at x. If this phenomenon happens with some of the coefficients of our random polynomial, we cannot guarantee that our random polynomial has finite condition almost-surely,it might happen that it equals a particular ill-posed polynomial (one with infinite condition) with non-zero probability. Because of this, we introduce the following.

Definition 7.5. A random variable x has the anti-concentration property, if there exists a ρ > 0, such that for all ε > 0, max{P (|x

-u| ≤ ε) | u ∈ R} ≤ 2ρε.
The smallest such ρ is the anti-concentration constant of x.

The above definition is good at giving the property in a clear way. The following proposition characterizes anti-concentration in terms of having a bounded continuous density. We will use this equivalence without mentioning it.

Proposition 7.6. Let x ∈ R be a random variable. Then x has the anti-concentration property with anti-concentration constant ≤ ρ if and only if x is absolutely continuous with respect the Lebesgue measure with density δ x bounded by ρ.

Proof. This is (Rudelson and Vershynin, 2015, Proposition 2.2). The precise bounds follow immediately once we have shown the equivalence.

We conclude with the following proposition which is a generalization of (Rudelson and Vershynin, 2015, Theorem 1.1) for more general linear maps. The explicit constants are thanks to the work of [START_REF] Livshyts | On sharp bounds for marginal densities of product measures[END_REF].

Proposition 7.7. Let A ∈ R k×N be a surjective linear map and x ∈ R N be a random vector such that the x i 's are independent random variables with densities (with respect the Lebesgue measure) bounded almost everywhere by ρ. Then, for all measurable U ⊆ R k ,

P(Ax ∈ U) ≤ vol(U) √ 2ρ k / √ det AA * .
Proof. Using SVD, write A = QS P where, P ∈ R k×N is an orthogonal projection, S a diagonal matrix containing the singular values of A, and Q an orthogonal matrix. By [START_REF] Rudelson | Small ball probabilities for linear images of high-dimensional distributions[END_REF], Theorem 1.1), see also [START_REF] Livshyts | On sharp bounds for marginal densities of product measures[END_REF], Theorem 1.1) for the explicit constant, we have that Px ∈ R k is a random vector with density bounded, almost everywhere, by ( √ 2ρ) k . Hence

P(Ax ∈ U) = P(Px ∈ (QS ) -1 U) ≤ vol (QS ) -1 U ( √ 2ρ) k .
This suffices to conclude the proof, since we have vol (QS ) -1 U = vol(U)/ det(QS ) and det(QS ) = √ det AA * .

Zintzo random polynomials

We introduce a new class of random polynomials; we call them zintzo3 polynomials. The zintzo polynomials have many simililarities with the dobro random polynomials, introduced by [START_REF] Cucker | Plantinga-Vegter Algorithm Takes Average Polynomial Time[END_REF]. The main difference between the two is in the variance structure of the coefficients. While dobro polynomials scale the coefficients according to the weights induced by the Weyl norm, zintzo polynomials do not. This property makes zintzo random polynomials a more natural model of random polynomials. Moreover, it allows us to explicitly include sparseness in the model of randomness.

Definition 7.8. Let M ⊆ N n be a finite set such that 0, e 1 , . . . , e n ∈ M. A zintzo random polynomial supported on M is a random polynomial f = α∈M f α X α ∈ P n,d such that the coefficients f α are independent subgaussian random variables with the anti-concentration property.

Remark 7.9. We recall that the condition on the support is important to guarantee the smoothness of zero and necessary for our technical assumptions. We stress this, as we will be assuming this in all this section.

The bounds and the complexity estimates involving zintzo random polynomials that we present in the sequel depend on (the product of) the following two quantities:

1. The subgaussian constant of f which is

K f := α∈M K α , (7)
where K α is the subgaussian constant of f α .

2. The anti-concentration constant of f which is

ρ f := n+1 √ ρ 0 ρ e 1 • • • ρ e n , (8)
where ρ 0 is the anti-concentration constant of f 0 and ρ e i is the anti-concentration constant of f e i , for i ∈ [n].

Example 7.10. Both Gaussian and uniform random polynomials are zintzo random polynomials with

K f ρ f ≤ |M| 2 . (9)
In general, we should think of zintzo random polynomials as a robust version of Gaussian polynomials.

The product K f ρ f is invariant under multiplication of f by a non-zero scalar and it is bounded from below.

Proposition 7.11. Let f be a zintzo random polynomial supported on M. Then K f ρ f > (n+1)/4 ≥ 1/2.

Proof. Using the positivity of the subgaussian constants, K α , of the coefficients of the zintzo polynomial f and the arithmetic-geometric inequality,

K f ρ f ≥ (n + 1) n+1 (K 0 ρ 0 )(K e 1 ρ e 1 ) • • • (K e n ρ e n ).
Hence, it suffices to show that for a random variable with X with subgaussian constant K and anti-concentration constant ρ, Kρ ≥ 1/4. Now, by definition, (-2.25) .

3Kρ ≥ P (|X| ≤ 1.5K) = 1 -P (|X| > 1.5K) ≥ 1 -2 exp
Calculating we get Kρ ≥ 1/4, as desired.

Smoothed analysis

Recall that in the context of smoothed analysis, as introduced by Spielman and Teng ( 2002), we study the complexity algorithms when the input polynomial is a fixed polynomial with a random perturbation. The importance of smoothed analysis lies in that it explains the behaviour of an algorithm in practice better than the average case, since in practice we tend to have a fixed input with a perturbation produced by errors. In our setting, it is natural to consider this perturbation proportional to the norm of the polynomial. The following proposition shows that for zintzo random polynomials the average complexity already includes the smoothed case as a particular case. Because of that, there is no need to give a smoothed analysis of any of our results.

Proposition 7.12. Let f be a zintzo random polynomial supported on M, f ∈ P n,d a polynomial supported on M, and σ > 0. Then,

f σ := f + σ f 1 f is a zintzo random polynomial supported on M such that K f σ ≤ f 1 (1 + σK f ) and ρ f σ ≤ ρ f /(σ f 1 ). In particular, K f σ ρ f σ = (K f + 1/σ)ρ f .
Note that both the worst case and the average case are limit cases of the smoothed case. When the perturbation, σ, becomes zero, the smoothed case becomes the worst case, and when the perturbation becomes of infinite magnitude, the smoothed case becomes the average case. Because of this, it is not surprising that

lim σ→0 K f σ ρ f σ = ∞ and lim σ→∞ K f σ ρ f σ = K f ρ f ,
which shows that this is the case.

Proof of Proposition 7.12. It is enough to show that for x, s ∈ R and a random variable x with subgaussian constant K and anti-concentration constant ρ, x + sx is a random variable with subgaussian constant ≤ |x|+sK and anti-concentration constant ≤ ρ/s. We note that the latter follows directly from the definition, so we only prove the former. Now, for all t ≥ |x| + sK,

P(|x + sx| ≥ t) ≤ P(|x| ≥ (t -|x|)/s) ≤ 2 exp(-(t -|x|) 2 /(sK) 2 ).
We can easily check that t ≥ |x| + sK implies (t -|x|)/(sK) ≥ t/(|x| + sK). Hence, the claim follows.

7.2.2. p-zintzo random polynomials Zintzo random polynomials have subgaussian coefficients, we can relax or tighten up this condition which leads to p-zintzo random polynomials. We note that 1-zintzo polynomials will have subexponential coefficients, extending the results that concern zintzo polynomials further. Definition 7.13. Let p ≥ 1 and M ⊆ N n be a finite set such that 0, e 1 , . . . , e n ∈ M. A p-zintzo random polynomial supported on M is a random polynomial f = α∈M f α X α ∈ P n,d such that the coefficients f α are independent p-subexpoential random variables with the anti-concentration property.

Given a p-zintzo random polynomial f ∈ P n,d , we define the following quantities:

1. The tail constant of f which is

L := α∈M L α , (10)
where L α is the p-subgaussian constant of f α .

2. The anti-concentration constant of f which is

ρ f := n+1 √ ρ 0 ρ e 1 • • • ρ e n , (11)
where ρ 0 is the anti-concentration constant of f 0 and ρ e i is the anti-concentration constant of f e i , for i ∈ [n].

Example 7.14. We note that Gaussian polynomials are p-zintzo for p ∈ [1, 2], while uniform random polynomials are p-zintzo random polynomials with

L f ρ f ≤ |M| 2 m
for p ≥ 1. This is the reason we have slightly better results for uniform random polynomials, as we can take the bound for p-zintzo random polynomials when p → ∞.

We note that we only vary the constants that control the how the tail goes to zero as we goes to infinity. Again, our estimates will depend on L f ρ f which has a universal lower bound. The proof is analogous to that of Proposition 7.11. Proposition 7.15. Let p ≥ 1 and f a p-zintzo random polynomial supported on M. Then L f ρ f > 9(n + 1)/50 ≥ 9/25.

In the same way, a version of Proposition 7.12 holds also for p-zintzo random polynomials.

Condition of zintzo random polynomials

The following two theorems are our main probabilistic results.

Theorem 7.16. Let f ∈ P n,d be a zintzo random polynomial supported on M. Then for all t ≥ e,

P(C 1 (f, x) ≥ t) ≤ √ nd n |M| 8K f ρ f √ n + 1 n+1 ln n+1 2 t t n+1 .
Theorem 7.17. Let p ≥ 1 and f ∈ P n,d a p-zintzo random polynomial supported on M. Then for all t ≥ e,

P(C 1 (f, x) ≥ t) ≤ √ nd n |M|        8L f ρ f (n + 1) 1-1 p        n+1 ln n+1 p t t n+1 .
The main idea of the proof is to use a union bound to control P(C 1 (f, x) ≥ t) by the sum of P( f 1 ≥ u) and P( R x f ≤ u/t) which are controlled, respectively, by Propositions 7.4 and 7.7. The reason that this works is because P( f 1 ≥ t) decreases exponentially fast. To apply Proposition 7.7, we need the following lemma, which we proof at the end of this subsection.

Lemma 7.18. Let M ⊆ N n as in Definition 7.8 and P n,d (M) the set of polynomials in P n,d supported on M. Let R x : P n,d (M) → R n+1 be the linear map given by

R x : f → f (x) 1 d ∂ 1 f (x) • • • 1 d ∂ n f (x) * ,
and S : P n,d (M) → P n,d (M) be the linear map given by

S : f = α∈M f α X α → α∈M ρ α f α X α ,
where ρ ∈ R M + . Then for Rx := R x S -1 we have that

det Rx R * x ≥ 1 d n ρ 0 ρ e 1 • • • ρ e n ,
with respect to coordinates induced by the standard monomial basis.

Proof of Theorem 7.16. We write C 1 (f, x) = f 1 / R x f , where R x is as in Lemma 7.18 and the norm • in the denominator is given by y = max{|y 1 |, |y 2 | + • • • + |y n+1 |}. By the union bound, we have that for u, s > 0, it holds

P(C 1 (f, x) ≥ t) ≤ P( f 1 ≥ u) + P( R x f ≤ u/t). (12)
By Propositions 7.4, we have that for u ≥ K f ,

P( f ≥ u) ≤ 2|M| exp -u 2 /K 2 f . (13)
Let S : P n,d (M) → P n,d (M) be as in Lemma 7.18 with ρ α the anti-concentration constant of f α . Then, we have that S f has independent random coefficients with densities bounded (almost everywhere) by 1 and so we can apply to it to the Proposition 7.7. We do so with the help of Lemma 7.18, so that we obtain

P( R x f ≤ u/t) = P( Rx (S f) ≤ u/t) ≤ 2 n+1 n! d n ( √ 2ρ f u/t) n+1 , ( 14
)
where Rx is as in Lemma 7.18. Combining ( 12), (13), and ( 14) with u = K f √ (n + 1) ln t, we get

P(C 1 (f, x) ≥ t) ≤ 2|M| t n+1 + 2 n+1 n! d n √ 2K f ρ f √ n + 1 n+1 ln n+1 2 t t n+1 .
By Stirling's formula, (n + 1) n+1 /n! ≤ √ ne n+1 , and so the desired claim follows for t ≥ e, by Proposition 7.11.

Proof of Theorem 7.17. The proof is as that of Theorem 7.16, but with p instead of 2 in the exponents of ( 13), u = L f ((n + 1) ln t)

1 p instead of u = K f √
(n + 1) ln t, and Proposition 7.15 instead of Proposition 7.11.

Proof of Lemma 7.18. The maximal minor of A x is given by

R X = 1 x * 0 1 d I .
This is precisely the minor associated to the subset {1, X 1 , . . . , X n } of the standard monomial basis of P n,d (M). Note that at this point we require the assumption that 0, e 1 , . . . , e n ∈ M.

By the Cauchy-Binet identity, det A x A * x is lower-bounded by the absolute value of the determinant of the given maximal minor. Hence the lemma follows.

Probabilistic complexity analysis for the Plantinga-Vegter algorithm

We now proceed to the complexity analysis of the condition-based quantities in the complexity analysis of the Plantinga-Vegter algorithm. The theorems of interest are the following two.

Theorem 7.19. Let f ∈ P n,d be a zintzo random polynomial supported on M. The average number of boxes of the final subdivision of PV-Subdivsion using the interval approximations (3) and (4) on input f is at most

2n 3 2 d 2n |M| 20(n + 1)K f ρ f n+1 .
Theorem 7.20. Let p ≥ 1 and f ∈ P n,d be a p-zintzo random polynomial supported on M. The average number of boxes of the final subdivision of PV-Subdivsion using the interval approximations (3) and (4) on input f is at most

2n 3 2 (n + 1) 1 p -1 2 d 2n |M| 64n 1 p (n + 1) 1 p L f ρ f n+1 .
The above two results follow from Corollary 5.6 together with the following two results.

Proposition 7.21. Let f ∈ P n,d be a zintzo random polynomial supported on M. Then,

E f E f∈I n C 1 ( f, x) n ≤ 2n 2 d n |M| 7 √ n + 1K f ρ f n+1 .
Proposition 7.22. Let p ≥ 1 and f ∈ P n,d a p-zintzo random polynomial supported on M. Then,

E f E f∈I n C 1 ( f, x) n ≤ 2n 2 (n + 1) 1 p -1 2 d n |M|        e 1-1 p 8 p 1 p n 1 p -1 2 (n + 1) 1 p L f ρ f        n+1 .
Proof of Proposition 7.21. By the Fubini-Tonelli theorem, we have

E f E f∈I n C 1 ( f, x) n = E f∈I n E f C 1 ( f, x) n , so it is enough to compute E f C 1 ( f, x) n = ∞ 1 P(C 1 (f, x) n ≥ t).
The latter, by Theorem 7.16, is bounded from above by

e n √ nd n |M|       8K f ρ f √ n √ n + 1       n+1 ∞ 1 ln n+1 2 t t 1+ 1 n dt.
After straightforward calculations, we obtain

∞ 1 ln n+1 2 t t 1+ 1 n dt = n n+3 2 Γ n + 3 2 ≤ e √ πn n+4 2 n + 1 2e n+1 2
, where Γ is Euler's Gamma function and the second inequality follows from Striling's approximation. Hence, the bound follows.

Proof of Proposition 7.22. We do as in the proof of Proposition 7.21, but applying Theorem 7.17 instead of Theorem 7.16. We obtain this way that the desired quantity is bounded by

e n √ nd n |M|        8L f ρ f √ n(n + 1) 1-1 p        n+1 ∞ 1 ln n+1 p t t 1+ 1 n dt.
Computing the integral turns into Remark 7.25. The global assumption on the anti-concentrarion constants is to control log f 1 when f 1 is small.

These results follow from Propositions 6.4 and 6.7 and the following two propositions. We give the computations below.

Proposition 7.26. Let f ∈ P n,d be a zintzo random polynomial supported on M. Then, for all t > 2e,

P(C 1 (f) ≥ t) ≤ 2 √ nd 2n |M| 16K f ρ f √ n + 1 n+1 ln n+1 2 t t ≤ 2 √ nd 2n |M| 10K f ρ f n+1 1 √ t .
Proposition 7.27. Let p ≥ 1 and f ∈ P n,d be a p-zintzo random polynomial supported on M.

Then, for all t > 2e,

P(C 1 (f) ≥ t) ≤ 2 √ nd 2n |M|        16L f ρ f (n + 1) 1-1 p        n+1 ln n+1 p t t ≤ 2 √ nd 2n |M|        16L f ρ f (n + 1) 1-2 p        n+1 1 t 1-1 p .
Proof of Proposition 7.26. The idea is to use an efficient ε-net of I n and the 2nd Lipschitz property to turn our local estimates into global ones, as is done in (Tonelli-Cueto, 2019, Theorem 1 §2 19). Recall, that an ε-net of I n (with respect to the ∞-norm) is a finite subset G ⊆ I n such that, for all y ∈ I n , dist ∞ (y, G) ≤ ε.

Note that for every ε ∈ (0, 1), we have an ε-net G ε ⊆ I n of size ≤ 2ε -n . To construct it, we take the uniform grid in the cube.

If C 1 (f) ≥ t, then max C 1 (f, x) | x ∈ G 1 dt ≥ t 2 by the 2nd Lipschitz property (Theorem 4.2). Effectively, let x * ∈ I n such that C 1 (f) = C 1 (f, x * ), then there is x ∈ G 1 dt such that dist ∞ (x, x * ) ≤ 1 dt and therefore

max{C 1 (f, x) | x ∈ G 1 2dt } ≥ C 1 (f, x) = 1 C 1 (f, x) -1 ≥ 1 C 1 (f, x * ) + 1 t -1 = 1 C 1 (f) + 1 t -1 ≥ t 2 .
To obtain the first inequality, we argue as follows:

P(C 1 (f) ≥ t) ≤ P ∃x ∈ G 1 dt | C 1 (f, x) ≥ t 2 (Implication bound) ≤ G 1 dt max P C 1 (f, x) ≥ t 2 | x ∈ G 1 dt (Union bound) ≤ 2d n t n max P C 1 (f, x) ≥ t 2 | x ∈ G 1 dt G 1 dt ≤ 2d n t n ≤ 2 √ nd 2n |M| 16K f ρ f √ n + 1 n+1 ln n+1 2 t t (Theorem 7.16)
For the second one, note that ln n+1 t ≤ (n+1) ( n+1) e n+1 t Proof of Proposition 7.26. Like the proof of Proposition 7.26, but using Theorem 7.16 instead of Theorem 7.17.

We restrict ourselves now to the technical results needed in the proofs. The following propistion proves Theorem 7.23 and so Theorem 2.3. Proposition 7.28. Let p ≥ 1 and f ∈ P 1,d be a p-zintzo random polynomial supported on M. Then for k ≥ 1,

E f log k C 1 (f) ≤ O k(log(dL f ρ f )) k .
Proof. Let x ∈ [1, ∞) be a random variable such that P(x ≥ t) ≤ Ct -α for all t ≥ t 0 , where C, α > 0 and t 0 ≥ 2. Then we have that

E x log k x ≤ log k t 0 + Ck k α k t α 2 0 .
To see this note that

∞ 0 P log k x ≥ s ds ≤ log k t 0 + ∞ log k t 0 P log k x ≥ t ds ≤ log k t 0 + C ∞ log k t 0 2 -αs 1 k ds.
Then, we have that

∞ log k t 0 2 -αs 1 k ds = k α k ∞ α ln 2 log t 0 u k-1 e -u du s = α ln 2 t 1 k ≤ k α k 2(k -1) e k-1 ∞ α ln 2 log t 0 e -u 2 du        u k-1 e -u 2 ≤ 2(k -1) e k-1        = k α k 2(k -1) e k-1 t -α 2 0 ≤ k k α k t α 2 0
. Now, we take log t 0 = Ω log d + log(L f ρ f ) .

The following two propositions gives the proof of Theorem 7.24 and so of Theorem 2.4. For applying it, just notice that E max{|x|, |y|} ≤ E|x| + E|y|.

Proposition 7.29. Let p ≥ 1 and f ∈ P 1,d be a p-zintzo random polynomial supported on M.

Assume that for all α ∈ M, the anti-concentration constant of f α is ≤ 1. Then for k ≥ 1,

E f | log k f 1 | ≤ O k k + 1 + k k p k log k L f .
Proof. We have that

E f | log k f 1 | = 1 0 | log k t|δ f 1 (t) dt + ∞ 1 | log k t|δ f 1 (t) dt,
where δ f 1 is the density of f. By our assumption, f has density (with respect the Lebesgue measure) and this density is bounded by 1. Hence we have that for J ⊆ [0, 1],

P( f 1 ∈ J) = vol{x ∈ R M | x 1 ∈ J} ≤ 2w(J);
and so f 1 has density bounded by 2. To finish the estimation of the first summand, note now that If we define the random variable x to be f 1 if f 1 ≥ 1 and zero otherwise, then

E x log k x ≤ 1 + k k p k log k L f .

  n + 1)) n+1 d 2n |M| n+2 if f is Gaussian, and 2n 32 n+1 d 2n |M| n+2

  and Cucker et al. (2020b) (cf. Cucker et al. (2019)), we focus on the subdivision procedure. To analyze the complexity, we notice that three levels that we focus on (following[START_REF] Xu | Effective subdivision algorithm for isolating zeros of real systems of equations, with complexity analysis[END_REF] (cf. Yap (2019))): A) Abstract level: Evaluations are modelled with exact arithmetic. I) Interval level: Evaluations are modelled with exact interval arithmetic. E) Effective level: Evaluations are modelled with finite precision interval arithmetic. Cucker et al. (

Algorithm 1 :

 1 PV-SubdivsionInput : f ∈ P n,d which is non-singular in I n Output : A subdivision S of I n into boxes such that for all B ∈ S, C f (B) holds 1 S 0 ← {I n }, S ← ∅ ;

  Stirling's approximation in the last inequality. The result now follows.7.5. Probabilistic complexity analysis for univariate solversFor Descartes and JindalSagraloff, we prove the two following general result.Theorem 7.23. Let p ≥ 1 and f ∈ P n,d be a zintzo random polynomial supported on M. The average size of the subdivision tree of Descartes on input f is at mostO |M|| log(dL f ρ f )| .Moreover, the kth moment of the size is bounded byO k|M|| log(dL f ρ f )| k .Theorem 7.24. Let p ≥ 1 and f ∈ P n,d be a p-zintzo random polynomial supported on M. The average bit-complexity of JindalSagraloff on input (f, I) is at mostO |M| 12 log 6 d| log(L f ρ f )| .Moreover, the kth moment of the bit-run-time is bounded byO k|M| 12 log 6 d| log(L f ρ f )| k .

1 0|

 1 log k t| dt =∈ ∞ 0 e -s 1 k ds = k!.

  | log k t|δ f 1 (t) dt = E x log k x ≥ L f , by Proposition 7.4. Arguing as in the proof of Proposition 7.28, we obtain then that

	and x satisfies	P(x ≥ t) ≤ e	-t p L p f ≤	L p f t p
	for t

∞ 1

Email addresses: josue.tonelli.cueto@bizkaia.eu (Josué Tonelli-Cueto), elias.tsigaridas@inria.fr (Elias Tsigaridas) URL: https://tonellicueto.xyz (Josué Tonelli-Cueto), https://who.paris.inria.fr/Elias.Tsigaridas/ (Elias Tsigaridas)Preprint submitted to ElsevierDecember 22, 2020

One should notice that the solution of[START_REF] Lairez | A deterministic algorithm to compute approximate roots of polynomial systems in polynomial average time[END_REF] does not construct a good starting system, but exploits the randomness of the input as a source of randomness for a deterministic algorithm. Constructing such initial systems is hard, although there was a breakthrough construction for the univariate case by[START_REF] Etayo | A sequence of polynomials with optimal condition number[END_REF].

The formula looks different from the usual one because it is simplified for the case of one multivariate polynomial.

P 1,d × N ( f, L) → {(x i , r i , n i )} t i=0 ⊆ I × (0, 2 -L ) × N

The word "zintzo" is a Basque word that means honest, upright, righteous. We note that this is the same meaning as that of the word "dobro" in a certain sense. This coincidence is not by chance, since it show that dobro and zintzo random polynomials are polynomials of the same kind, but different.

Acknowledgments

The first author is supported by a postdoctoral fellowship of the 2020 "Interaction" program of the Fondation Sciences Mathématiques de Paris. The authors are partially supported by ANR JCJC GALOP (ANR-17-CE40-0009), the PGMO grant ALMA and the PHC GRAPE.

Both authors are grateful to Alperen Ergür for various discussions and suggestions. The first author is grateful to Evgenia Lagoda for moral support.