Felipe Cucker
email: macucker@cityu.edu.hk

Alperen A Ergür
email: aergur@cs.cmu.edu

Josué Tonelli-Cueto
email: josue.tonelli.cueto@bizkaia.eu

On the Complexity of the Plantinga-Vegter Algorithm

Keywords: Plantinga-Vegter algorithm, subdivision methods, complexity Mathematics Subject Classification (2010) 65D18, 68W40

We introduce a general toolbox for precision control and complexity analysis of subdivision based algorithms in computational geometry. We showcase the toolbox on a well known example from this family; the adaptive subdivision algorithm due to Plantinga and Vegter. The only existing complexity estimate on this rather fast algorithm was an exponential worst-case upper bound for its interval arithmetic version. We go beyond the worst-case by considering smoothed analysis, and prove polynomial time complexity estimates for both interval arithmetic and finite precision versions of the Plantinga-Vegter algorithm. The employed toolbox is a blend of robust probabilistic techniques coming from geometric functional analysis with condition numbers and the continuous amortization paradigm introduced by Burr, Krahmer and Yap. We hope this combination of tools from different disciplines would prove useful for understanding complexity aspects of the broad family of subdivision based algorithms in computational geometry.

Introduction

Subdivision based algorithms are ubiquitous in computational geometry. These algorithms have the advantage of simplicity, and often have good practical performance. The two main challenges related to subdivision based algorithms are the control of precision (or a termination criterion), and complexity analysis. As late as summer 2019, complexity analysis aspect of subdivision based geometric algorithms was considered to be "largely open" [START_REF] Yap | Towards soft exact computation (invited talk)[END_REF]. In this paper, we contribute to both of the main challenges by introducing a hybrid toolbox that combines condition numbers, high dimensional probability theory, and continuous amortization framework introduced by Burr, Krahmer, and Yap [START_REF] Burr | Continuous amortization: A non-probabilistic adaptive analysis technique[END_REF]. To keep our writing focused, and the length of the article finite, we only showcase the toolbox on a well-known member of this large family; the algorithm of Plantinga and Vegter.

Plantinga-Vegter (PV) algorithm is an adaptive subdivison algorithm for meshing curves and surfaces [START_REF] Plantinga | Isotopic approximation of implicit curves and surfaces[END_REF]. The algorithm admits an implicit equation of a curve or a surface and outputs an isotopic piecewise linear approximation with controlled Hausdorff distance. The initial paper of Plantinga and Vegter contained no complexity analysis and not even a formal setting fixing either the kind of functions implicitly defining the considered curves and surfaces or the arithmetic used. However, concrete implementations in the paper indicated the efficiency of the algorithm. The algorithm is now widely considered to be very efficient.

The first complexity analysis of the PV algorithm was published thirteen years later by Burr, Gao and Tsigaridas [START_REF] Michael | The complexity of an adaptive subdivision method for approximating real curves[END_REF] (cf. [START_REF] Michael | The complexity of subdivision for diameter-distance tests[END_REF]). The paper of Burr, Gao, and Tsigaridas focused on the subdivision procedure of the Plantinga-Vegter algorithm and only analyzed the complexity for polynomials with integer coefficients. The paper provides bounds that are exponential both in the degree d of the input polynomial and in its logarithmic height τ . The discrepancy between the exponential complexity estimate and the practical efficiency of the PV algorithm was marked by the following comment at the end of the paper Even though our bounds are optimal, in practice, these are quite pessimistic [. . . ] The authors further observe that, following from their Proposition 5.2 (see Theorem 6.1 below) an instance-based analysis of the algorithm (i.e., one yielding a cost that depends on the input at hand) could be derived from the evaluation of a certain integral. And they conclude their paper by writing Since the complexity of the algorithm can be exponential in the inputs [size], the integral must be described in terms of additional geometric and intrinsic parameters.

In this paper, we make progress towards these aims by going beyond the worst-case analysis and by using condition numbers. We believe condition numbers are a perfect fit for the latter aim as they provide a geometric and an arguably intrinsic parameter.

We analyze the complexity of the PV algorithm in its two different versions, roughly speaking, one version that corresponds to the arithmetic complexity and the second that corresponds to the (arguably more realistic) bit complexity. We should note that our analysis contains the subdivision routine of the PV algorithm for curves and surfaces as the special cases for n = 2 and n = 3, where we aim for estimates that holds for any n. We conduct average and smoothed analysis of the two versions of the PV algorithm, so we provide four different complexity analysis.

Average analysis framework is perhaps familiar to all of our readers, but the smoothed analysis might require a bit of an explanation: Suppose we endow the space of n-variate degree d polynomials with a norm . , and a probability measure µ (with as few assumptions as possible on µ). Suppose g is a random polynomial distributed with respect to µ. Then we consider an arbitrary polynomial f , and we fix a tolerance parameter σ > 0. We consider q = f + σ f g as random perturbation of f with tolerance σ, and conduct average analysis of the PV algorithm for q. This type of an estimate could a priori depend on the arbitrary polynomial f . We aim for a uniform estimate that provides an upper bound for any f , and depends only on σ, n, and d. This uniform upper bound will be the smoothed analysis of the PV algorithm. It turns out that this random perturbation idea was already considered in computational geometry literature in an experimental fashion, and there were aims for building a theoretical framework (see section 4 of [START_REF] Funke | Of what use is floating-point arithmetic in computational geometry[END_REF]).

Our main results Theorem 3.1 and Theorem 3.2 provide the four promised estimates on the complexity of PV algorithm for any number of variables n. For the special case of the plane curves, the average and smoothed analysis of the arithmetic complexity of the PV algorithm are respectively O(d 7 ) and O d 7 (1 + 1 σ ) 3 . The average and smoothed analysis of the bit complexity are just slightly worse: O(d 7 log 2 d) and O(d 7 log 2 d (1 + 1 σ ) 3 ), respectively. These bounds are in marked contrast with the O(2 τ d 4 log d ) worst-case complexity bound in [START_REF] Michael | The complexity of an adaptive subdivision method for approximating real curves[END_REF].

For a clear presentation of our contribution and surrounding complexity considerations we need to make a few remarks:

(1) The use of floating-point arithmetic generates numerical errors which accumulate during the computation. An important remark is that, despite this accumulation of errors, our algorithm returns a correct output, a subdivision with the properties we want. It is, in this sense, a certified algorithm. At the heart of this remark is the fact that a sufficiently small perturbation of a correct subdivision is still a correct subdivision for a generic (i.e. non-singular) input. Condition numbers allow us to estimate how large this perturbation may be. Then, the fact that we can estimate these condition numbers, we control the precision of the operations' round-off, and we know how these operations are sequenced further allows us to ensure that the subdivision we constructed is close enough to the one we would have done in an error-free context.

Needless to say, for input data outside the set satisfying the generic property above our reasoning does not hold. The set of such inputs, referred to as ill-posed in numerical analysis, has measure zero. Condition numbers relate to ill-posedness in the sense that the closer a data is to the set of ill-posed inputs the larger becomes its condition number. It is these facts that allows one to establish average and smoothed analysis by means of probabilistic estimates on the condition numbers. This general scheme was proposed in [START_REF] Smale | Complexity theory and numerical analysis[END_REF]. A more detailed discussion of these issues is in [4, §9.5]. A relatively early case of a fully studied variable-precision algorithm is in [START_REF] Cucker | A primal-dual algorithm for solving polyhedral conic systems with a finite-precision machine[END_REF]. An account of the use of floating-point arithmetic in computational geometry is given in [START_REF] Funke | Of what use is floating-point arithmetic in computational geometry[END_REF].

(2) Most of the probabilistic analyses for cost measures or condition numbers use the Gaussian measure. This choice is mainly for technical convenience. For the analysis of condition numbers, this goes back to Goldstine and von Neumann [START_REF] Goldstine | Numerical inverting matrices of high order[END_REF] and, more recently, resulted in simple bounds for a large class of condition numbers [START_REF] Demmel | The probability that a numerical analysis problem is difficult[END_REF][START_REF] Bürgisser | Smoothed analysis of complex conic condition numbers[END_REF][START_REF] Bürgisser | The probability that a slightly perturbed numerical analysis problem is difficult[END_REF][START_REF] Lotz | On the volume of tubular neighborhoods of real algebraic varieties[END_REF].

In the last few years, however, the search for more robust complexity analysis resulted in estimates that hold for a (quite) general family of measures. The family of subgaussian measures which includes all compactly supported random variables provides a good testing ground. An analysis of a condition number for these distributions occupies [START_REF] Ergür | Probabilistic condition number estimates for real polynomial systems I: A broader family of distributions[END_REF]. It is for this class of distributions (subgaussians with an anti-concentration property) that our results are proved.

(3) The subdivision procedure we analyze can be considered at three levels of generality: the abstract, in which we only take into account the number of iterations of the subdivision procedure; the interval, in which we take also into account the number of arithmetic operations; and the effective, in which we take into account not only the number of arithmetic operations, but also the precision that they need, obtaining a realistic estimation of the bit-cost of the algorithm. This division follows a trend for analysing subdivision algorithms initiated by Xu and Yap [START_REF] Xu | Effective subdivision algorithm for isolating zeros of real systems of equations, with complexity analysis[END_REF] (cf. [START_REF] Yap | Towards soft exact computation (invited talk)[END_REF]).

Our condition-based analysis can be applied at each of these three levels, hopefully showing the usefulness of the approach. Whereas this paper focuses on a particular subdivision procedure we believe that the techniques in this paper can be readily applied to other subdivision based algorithms in computational geometry. We note, however, that the complexity analysis in this paper would have been impossible without the continuous amortization technique developed in the exact numerical context [START_REF] Burr | Continuous amortization: A non-probabilistic adaptive analysis technique[END_REF][START_REF] Michael | Continuous amortization and extensions: with applications to bisection-based root isolation[END_REF]. In this regard, we hope to trigger a fruitful exchange of ideas between the different approaches to continuous computation and improve our (seemingly preliminary) understanding of the complexity of subdivision algorithms in computational geometry.

Outline

The rest of the paper is structured as follows: We start with a section that contains notation. We beg readers' pardon for this inconvenient start; this seemed the simplest way for getting things clear. Then in Section 2 we discuss the Plantinga-Vegter algorithm and the n-dimensional generalization of its subdivision method in the abstract, the interval arithmetic, and the effective versions. Section 3 introduces our randomness model and contains main complexity estimates of this paper. In Section 4, we present a geometric framework (read Hilbert space structure) to deal with homogeneous polynomials. In Section 5, we introduce the condition number κ aff -both local, i.e., at a point x, and global-along with its main properties. In Section 6, we present the existing results on the complexity of Plantinga-Vegter algorithm from [START_REF] Michael | The complexity of an adaptive subdivision method for approximating real curves[END_REF], and we relate these results to the local condition number. In Section 7, we carry out the finite-precision analysis deriving the corresponding bounds for bit-cost. Finally, in Section 8, we derive average and smoothed complexity bounds under (quite) general randomness assumptions.

Notation

Throughout the paper, we will assume some familiarity with the basics of differential geometry and with the sphere S n as a Riemannian manifold. For scalar smooth maps f : R m → R, we will write the tangent map at x ∈ R m as ∂xf : R m → R when we want to emphasize it as a linear map and as ∂f : R m → R m , x → ∂f (x), when we want to emphasize it as a smooth function. For general smooth maps between smooth manifolds F : M → N , we will just write ∂xF : TxM → TxN as the tangent map.

In what follows, P n,d will denote the set of real polynomials in the n variables X 1 , . . . , Xn with degree at most d, H n,d the set of homogeneous real polynomials in the n + 1 variables X 0 , X 1 , . . . , Xn of degree d, and and , will denote the standard norm and inner product in R m as well as the Weyl norm and inner product in P m n,d and H m n,d . Given a polynomial f ∈ P n,d , f h ∈ H n,d will be its homogenization and ∂f the polynomial map given by its partial derivatives. We will denote by the Cyrillic character , 'yu', the central projection (4.1) that maps R n into S n . For details see Section 4. Additionally, V R (f ) and V C (f ) will be, respectively, the real and complex zero sets of f .

We will denote by X the set of n-boxes of the form x + I n , where I is an interval, that are contained in X and, for a given box B ∈ R n , m(B) will be its middle point, w(B) its width, and vol B = w(B) n its volume.

Regarding probabilistic conventions, we will denote the probability of an event by P, random variables by x, y, . . . and random polynomials by f, g, q, . . . The expression E x∈K g(x) will denote the expectation of g(x) when x is sampled uniformly from the set K and Eyg(y) the expectation of g(y) with respect to a previously specified probability distribution of y.

Regarding complexity parameters, n will be the number of variables, d the degree bound, and N = ( n+d n ) the dimension of P n,d . Finally, ln will denote the natural logarithm and log the logarithm in base 2.

Given a real smooth hypersurface in R n described implicitly by a map f : R n → R and a region [-a, a] n , the Plantinga-Vegter Algorithm constructs a piecewise-linear approximation of the intersection of its zero set V R (f ) with [-a, a] n isotopic to this intersection inside [-a, a] n . The Plantinga-Vegter algorithm (see Figure 2.1 for an illustration) is divided in two phases:

1) Subdivision phase: In this phase, the Plantinga-Vegter algorithm subdivides [-a, a] n into smaller and smaller boxes until all the boxes satisfy a certain condition (see (2.1)). 2) Post-processing phase: In this phase, the Plantinga-Vegter algorithm uses the obtained subdivision to produce a piecewise-linear approximation of the given hypersurface.

We will focus on the subdivision phase of the Plantinga-Vegter algorithm. We do this because the complexity of subdivision-based algorithms is usually dominated by the complexity of the subdivision phase. This follows the guidelines of the first complexity analysis given by Burr, Gao and Tsigaridas [START_REF] Michael | The complexity of an adaptive subdivision method for approximating real curves[END_REF] (cf. [START_REF] Michael | The complexity of subdivision for diameter-distance tests[END_REF]). We note that it would be interesting to incorporate the complexity of the post-processing phase of the algorithm to our estimates in this paper: either the original one by Plantinga-Vegter [START_REF] Plantinga | Isotopic approximation of implicit curves and surfaces[END_REF], for n ≤ 3, or the generalization to higher dimensions by Galehouse [START_REF] Benjamin | Topologically accurate meshing using domain subdivision techniques[END_REF], for arbitrary n. We also don't cover existing extensions of the Plantinga-Vegter algorithm to singular curves [START_REF] Burr | Complete subdivision algorithms II, Isotopic meshing of singular algebraic curves[END_REF].

From now on, when we say Plantinga-Vegter algorithm, we are referring to the Plantinga-Vegter subdivision phase, and we restrict to the case in which f : R n → R is a polynomial. We now describe this algorithm at the three levels: abstract, interval and effective.

Abstract level: Algorithm PV-Abstract

The Plantinga-Vegter algorithm subdivides [-a, a] n until a certain regularity condition is satisfied in each of the boxes B of the subdivision. Let h, h : R n → (0, ∞) be some fixed positive maps, conveniently chosen (see (2.3) below). Then this regularity condition is

C f (B): either 0 / ∈ (hf )(B) or 0 / ∈ (h ∂f )(B), (h ∂f )(B) . (2.1)
Note that this condition is satisfied when either B does not contain any zero of f or no pair of gradient vectors of f are orthogonal in B. Intuitively, the latter means that the level sets of f should approximately look like a set of parallel hyperplanes.

Step 0 of subdivision phase

Step 1 of subdivision phase

Step 2 of subdivision phase

Step 4 of subdivision phase

Post-processing phase

Green: V R (f ) Red: Subdivision Blue: PL approximation of V R (f ) Fig. 2.1 Plantinga-Vegter applied to f = X 4 -6X 3 + 2X 2 Y 2 -6X 2 Y -34X 2 -6XY 2 -320XY + 376X + Y 4 -6Y 3 -34Y 2 + 376Y + 3128 in [-10, 10] 2 .
[34, Figure 5 §2 1]

In its abstract form, the Plantinga-Vegter algorithm is described in Algorithm PV-Abstract below. The StandardSubdivision procedure in the description refers to taking a box B and subdividing it into 2 n boxes of equal size.

Algorithm 1: PV-Abstract

Input : f : R n → R with interval approximations [hf ] and [h ∇f ] a ∈ (0, ∞) Precondition : V R (f ) is smooth inside [-a, a] n S ← {[-a, a] n } S ← ∅ repeat Take B in S S ← S \ {B} if C f (B) true then S ← S ∪ {B} else S ← S ∪ StandardSubdivision(B) until S = ∅ return S Output : Subdivision S ⊆ [-a, a] n of [-a, a] n Postcondition : For all B ∈ S, C f (B) is true

Interval level: Algorithm PV-Interval

To check condition C f (B), we use interval approximations allowing us to certify whether or not 0 is in the image of B under a certain map. Recall that an interval approximation [START_REF] Ratschek | Computer methods for the range of functions[END_REF] of a function

F : R m → R m is a map [F ] : R m → R m such that for all B ∈ R m , F (B) ⊆ [F ](B). (2.2)
We notice that if we see B as an error bound for its midpoint m(B), then we can see [F ](B) as an error bound for F (m(B)).

A natural choice for the interval approximation of a C 1 -function

F : R m → R m is its standard interval approximation R m B → std [F ](B) := F (m(B)) + √ m sup x∈B DxF - w(B) 2 , w(B) 2
m
where DxF is the tangent map of F at x and DxF its operator norm. Note that to construct this one in practice, we need to be able to evaluate F and to compute efficiently upper bounds for sup x∈B DxF . In our case, this is possible due to the fact that we are working with polynomials. Let f ∈ P n,d . We will consider

h(x) = 1 f (1 + x 2 ) (d-1)/2 and h (x) = 1 d f (1 + x 2 ) d/2-1 (2.3)
along with the maps

f : x → h(x)f (x) = f (x) f (1 + x 2 ) (d-1)/2
(2.4)

and ∂f : x → h (x)∂f (x) = ∂f (x) d f (1 + x 2 ) d/2-1 (2.5)
where f is the Weyl norm of f (which we recall in Definition 4.2). These are "linearized" versions of f and its derivative. The intuition behind this fact is that for large values of x a polynomial map of degree d grows like x d . This Lipschitz property allows us to prove the following (in Subsection 4.3).

Proposition 2.1 Let f ∈ P n,d . Then

[hf ] :

B → f (m(B)) + (1 + √ d) √ n - w(B) 2 , w(B)
2 is an interval approximation of hf , and

[h ∂f ] : B → ∂f (m(B)) + 1 + √ d -1 √ n - w(B) 2 , w(B) 2 n
is an interval approximation of h ∂f .

Moreover, we note that checking the condition "0 / ∈ B, B " for a box B can be reduced to checking

n 2 w(B) ≤ m(B) .
To do the latter we will use Lemma 4.2 (which we also prove in Subsection 4.3). Together with the interval approximations in Proposition 2.1, we derive a condition C f , implying C f (B) and easy to check.

Theorem 2.1 Let B ∈ R n . If the condition C f (B) : f (m(B)) > 2 √ dnw(B) or ∂f (m(B)) > 2 √ 2 √ dnw(B). is satisfied, then C f (B) is true.
Theorem 2.1 is the basis of the interval version of Algorithm PV-Interval below.

Algorithm 2: PV-Interval

Input : f ∈ P n,d a ∈ (0, ∞) Precondition : V R (f ) is smooth inside [-a, a] n S ← {[-a, a] n } S ← ∅ repeat Take B in S S ← S \ {B} if f (m(B)) > (1 + √ d) √ nw(B) then S ← S ∪ {B} else if ∂f (m(B)) > √ 2(1 + √ d -1)nw(B) then S ← S ∪ {B} else S ← S ∪ StandardSubdivision(B) until S = ∅ return S Output : Subdivision S ⊆ [-a, a] n of [-a, a] n Postcondition : For all B ∈ S, C f (B) is true Remark 2.1
We could consider alternative interval approximations. For instance, the interval approximations in [START_REF] Michael | The complexity of an adaptive subdivision method for approximating real curves[END_REF], which we will refer to as BGT, are based on the Taylor expansion at the midpoint, so they differ from the ones in Proposition 2.1. In the interlude at the end of Section 6, we will show that our complexity analysis also applies to this interval approximation.

Effective level: Algorithm PV-Effective

For the effective version (Algorithm PV-Effective), we will use floating-point numbers (cf. [4, §O.3.1] or [25, §1.2]). We do this, instead of using fixed-point or big rationals, because the use of floating-point is computationally cheap, both in time and space.

A floating-point number has the form

± 0.a 1 a 2 • • • am 2 e
where a 1 , . . . , am ∈ {0, 1} and e ∈ Z. In general, the number of significant digits, m, is fixed during the computation of arithmetic expressions, but it can be updated at different iterations of an algorithm if an increase in precision is needed. We note that every real number x ∈ R has a floating-point approximation rm(x) with m digits, such that

rm(x) = x(1 + δ) for some δ ∈ (-2 -(m-1) , 2 -(m-1)
). Moreover, given two floating-point numbers x and y with m significant digits, we can easily compute rm(x + y), rm(x -y), rm(xy), rm(x/y), and rm

√ x
in O(m 2 ) bit-operations. Comparisons between floating-point numbers can also be made using this amount of bit-operations.

Remark 2.2 In the above estimation we are ignoring the complexity of adding the exponents or operating with them. In general the size of e is of the order of | log |x||, and so the bit-size of e is of the order of | log | log |x|||. This means that, unless the numbers we deal with are enormous, one should not worry about the bit-size of e for cost estimates.

Finite-precision analyses do not rely on the precise form of floating-point numbers but just in some general properties which we now summarize. There is a subset F ⊂ R of floating-point numbers (which we assume contains 0), a rounding map r : R → F, and a round-off unit u ∈ (0, 1) satisfying the following conditions:

(i) For any x ∈ F, r(x) = x. In particular, r(0) = 0. (ii) For any x ∈ R, r(x) = x(1 + δ) with |δ| ≤ u.
Moreover, for • ∈ {+, -, ×, /}, there are approximate versions

• : F × F → F such that for all x, y ∈ F, x • y = (x • y)(1 + δ) (2.6)
for some δ such that |δ| < u. We also assume that there is

√ : F → F such that for all x ∈ F with x ≥ 0, √ x = √ x(1 + δ)
for some δ such that |δ| < u. Each of these operations and comparisons between numbers in F can be done with cost O log 2 1 u . For the floating-point numbers we described above we have u = 2 -(m-1) . Once the way we deal with finite precision is clear, we introduce the efficient version of the Plantinga-Vegter algorithm (PV-Effective below). We note that the algorithm updates the number of significant digits, m := | log u| + 1, depending on the width of the box that is being considered, being able, if necessary, to read the coefficients of f with this updated precision.

Algorithm 3: PV-Effective

Input: f ∈ P n,d a ∈ [1, ∞) Precondition : V R (f ) is smooth inside [-a, a] n m 0 ← 7 + log √ dn S ← {[-a, a] n } S ← ∅ repeat Take B in S S ← S \ {B} m B ← m 0 + max {log a, log(a/w(B))} Switch to floating-point numbers with m B significant digits if f (m(B)) > 4 √ dnw(B) then S ← S ∪ {B} else if ∂f (m(B)) > 6 √ dnw(B) then S ← S ∪ {B} else S ← S ∪ StandardSubdivision(B) until S = ∅ return S Output: Subdivision S ⊆ [-a, a] n of [-a, a] n Postcondition : For all B ∈ S, C f (B) is true 3 Main results
In this section, we outline without proofs the main results of this paper. In the first part, we describe our randomness assumptions for polynomials. In the second one, we give precise statements for our bounds on the average and smoothed complexity of phase I of the Plantinga-Vegter Algorithm with infinite precision. In the last part, we state similar results in the context of finite-precision arithmetic.

Randomness Model

Most of the literature on random multivariate polynomials considers polynomials with Gaussian independent coefficients and relies on techniques that are only useful for Gaussian measures. We will instead consider a general family of measures relying on robust techniques coming from geometric functional analysis. Let us recall some basic definitions.

(P1) A random variable x ∈ R is called centered if Ex = 0. (P2) A random variable x ∈ R is called subgaussian if there exists a K such that for all p ≥ 1, (E|x| p ) 1 p ≤ K √ p.
The smallest such K is called the

Ψ 2 -norm of x. (P3) A random variable x ∈ R satisfies the anti-concentration property with constant ρ if max {P (|x -u| ≤ ε) | u ∈ R} ≤ ρε.
The subgaussian property (P2) has other equivalent formulations. We refer the interested reader to [START_REF] Vershynin | High-dimensional probability: An introduction with applications in data science[END_REF]. We note that the anti-concentration property (P3) is equivalent to having a density (with respect to the Lebesgue measure) bounded by ρ/2. Definition 3.1 A dobro random polynomial f ∈ H n,d with parameters K and ρ is a polynomial

f := |α|=d d α 1 2 cαX α (3.1)
such that the cα are independent centered subgaussian random variables with Ψ 2 -norm at most K and anti-concentration property with constant ρ. A dobro random polynomial f ∈ P n,d is a polynomial f such that its homogenization f h is so.

Remark 3.1 The word "dobro" comes from Russian and it means good. The word "dobra" in Turkish means straight and honest, and the word has similar connotations in Greek.

Some dobro random polynomials of interest are the following three.

(N) A KSS random polynomial is a dobro random polynomial such that each cα in (3.1) is Gaussian with unit variance. For this model we have Kρ = 1/ √ 2π. (U) A Weyl random polynomial is a dobro random polynomial such that each cα in (3.1) have uniform distribution in [-1, 1]. For this model we have Kρ ≤ 1. (E) For ≥ 2, a -random polynomial is a dobro random polynomial whose coefficients are independent identically distributed random variables with density function

t → 1 2Γ 1 + 1 e -|t| .
We have in this case that ρ ≤ 1 and K ≤ 6/5.

Remark 3.2

The relevant complexity parameter for a dobro random polynomial f ∈ P n,d with constants K and ρ is the product Kρ. This is so because this product is invariant under scalings of f and condition numbers will be scale-invariant. Note that tf is still dobro, but with constants tK and ρ/t. Remark 3.3 If we are interested in integer polynomials, dobro random polynomials may seem inadequate. One may be inclined to consider random polynomials f ∈ P n,d such that cα is a random integer in the interval [-2 τ , 2 τ ], i.e., cα is a random integer of bit-size at most τ . As τ → ∞ and after we normalize the coefficients dividing by 2 τ , this random model converges to that of Weyl random polynomials.

Yet, in order to have a more satisfactory understanding of random integer polynomials, one has to consider random variables without a continuous density function. The techniques used in this note have already been extended to deal with such distributions in the case of random matrices [START_REF] Rudelson | The Littlewood-Offord problem and invertibility of random matrices[END_REF][START_REF] Vershynin | High-dimensional probability: An introduction with applications in data science[END_REF]. We hope to pursue this delicate case in a more general setting (including complete intersections) in future work.

Complexity at the interval and effective levels

The following three theorems give bounds for, respectively, the average and smoothed complexity of PV-Interval and PV-Effective.

Theorem 3.1 Complexity of PV-Interval:

(A) Let f ∈ P n,d be a dobro random polynomial with parameters K and ρ. The expected number of boxes in the final subdivision S of PV-Interval on input (f, a) is at most

d n N n+1 2 max{1, a n }2 12n log n+8 (Kρ) n+1
and the expected number of arithmetic operations is at most

O d n+1 N n+3 2 max{1, a n }2 12n log n+8 (Kρ) n+1 .
(S) Let f ∈ P n,d , σ > 0, and g ∈ P n,d a dobro random polynomial with parameters K ≥ 1 and ρ .

Then the expected number of n-cubes of the final subdivision S of PV-Interval on input (qσ, a) where qσ = f + σ f g is at most

d n N n+1 2 max{1, a n }2 12n log n+8 (Kρ) n+1 1 + 1 σ n+1
and the expected number of arithmetic operations is at most

O d n+1 N n+3 2 max{1, a n }2 12n log n+8 (Kρ) n+1 1 + 1 σ n+1 .
Theorem 3.2 Complexity of PV-Effective:

(A) Let f ∈ P n,d be a dobro random polynomial with parameters K and ρ. The expected number of boxes in the final subdivision S of PV-Effective on input (f, a) is at most

d n N n+1 2 a n 2 15n log n+12 (Kρ) n+1
and the expected number of arithmetic operations is at most

O d n+1 N n+3 2 a n 2 15n log n+12 (Kρ) n+1 .
Moreover, the expected bit-cost of PV-Effective on input (f, a) is at most

O d n+1 N n+3 2 a n 2 15n log n+12 log 2 (dna)(Kρ) n+1 ,
under the assumptions that floating-point arithmetic is done using standard arithmetic and that that the cost of operating with the exponents is negligible.

(S) Let f ∈ P n,d , σ > 0, and g ∈ P n,d a dobro random polynomial with parameters K ≥ 1 and ρ . Then the expected number of n-cubes of the final subdivision S of PV-Effective on input (qσ, a) where qσ = f + σ f g is at most

d n N n+1 2 a n 2 15n log n+12 (Kρ) n+1 1 + 1 σ n+1
and the expected number of arithmetic operations is at most

O d n+1 N n+3 2 a n 2 15n log n+12 (Kρ) n+1 1 + 1 σ n+1 .
Moreover, the expected bit-cost of PV-Effective on input (qσ, a) is at most

O d n+1 N n+3 2 a n 2 15n log n+12 log 2 (dna)(Kρ) n+1 1 + 1 σ n+1 ,
under the assumptions that floating-point arithmetic is done using standard arithmetic and that that the cost of operating with the exponents is negligible. with τ being the largest bit-size of the coefficients of f . One can see that the smoothed analysis estimates are exponentially smaller than the worst case estimates, this seems to relate better with the practical efficiency of the Plantinga-Vegter algorithm.

We note, however, that the bound in [START_REF] Michael | The complexity of an adaptive subdivision method for approximating real curves[END_REF] and our bounds cannot be directly compared. Not only because the former is worst-case and the latter average-case (or smoothed) but because of the different underlying settings: the bound in [START_REF] Michael | The complexity of an adaptive subdivision method for approximating real curves[END_REF] applies to integer data, ours to real data. Nevertheless, the bounds for the effective version PV-Effective apply to the real data under finite precision and provides estimates for the bit complexity.

Geometric framework

There is an extensive literature on norms of polynomials and their relation to norms of gradients in H n,d . The PV algorithm, however, works in the affine space with non-homogenous polynomials. We first establish basic definitions and inequalities that allow us to translate existing results into the setting of the PV algorithm. After the transfer is completed, we continue with establishing interval approximations.

Weyl norm

We introduce the Weyl norm on H n,d .

Definition 4.1 The Weyl norm on H n,d is the norm given by

f := α d α -1 f 2 α for f = α fαX α ∈ H n,d
; and the Weyl norm on H q n,d is the norm given by

f := q i=1 f i 2 = q i=1 α d α -1 f 2 i,α for f = (f i ) = ( α f i,α X α ) ∈ H q n,d .
To extend this norm to P n,d , we use the homogeneization map

h : P n,d → H n,d f → f h := f (X 1 /X 0 , . . . , Xn/X 0 )X d 0 .
and its componentwise extension h : P q n,d → H q n,d . Definition 4.2 The Weyl norm on P q n,d is the norm given by f := f h for f ∈ P q n,d . We remark that the Weyl norm comes from the corresponding inner product, so this gives means to perform orthogonal projections in polynomials spaces.

Note that for F ∈ H q n,d , we have that ∂F (X) ∈ H q(n+1) n,d-1 and so we can talk about the Weyl norm of ∂F (X). The following proposition comes in handy.

Proposition 4.1 Let f ∈ H q n,d and y ∈ S n . Then, [START_REF] Bürgisser | Smoothed analysis of complex conic condition numbers[END_REF]

f (y) ≤ f , (2) ∂yf |TyS n ≤ √ d f , ( 3
) ∂f (X) ≤ d f . Proof (

Central projection and homogeneization

Let : R n → S n be the map given by

: x → 1 1 + x 2 1 x . (4.1)
One can see that is the map induce by the central projection of R n × {1} onto the sphere S n and that this map induces a diffeomorphism between R n and the upper half of S n .

Given f ∈ P q n,d , we observe that

f h ( (x)) = f (x) (1 + x 2 ) d/2 , (4.2)
and so, by the chain rule,

∂ (x) f h ∂x = ∂xf (1 + x 2 ) d/2 - d • f (x)x T (1 + x 2 ) d/2+1 (4.3)
where ∂yf h : R n+1 → R, ∂x : R n → TxS n = x ⊥ and ∂xf : R n → R are respectively the tangent maps of f h , and f . It is important to note that deforms the metric. For each x ∈ R n , we can see that the singular values of ∂x are

σ 1 (∂x ) = • • • = σ n-1 (∂x ) = 1 1 + x 2 , σn (∂x ) = 1 1 + x 2 , (4.4)
and so, in particular,

∂x = 1 1 + x 2 . (4.5)
With the above, we reprove a version of Proposition 4.1 for P q n,d instead.

Proposition 4.2 Let f ∈ P k n,d be a polynomial map. Then the map

F : x → f (x) f (1 + x 2 ) (d-1)/2 is (1 + √ d)-Lipschitz and, for all x, F(x) ≤ 1 + x 2 .
Proof For the Lipschitz property, it is enough to bound the norm of the derivative of the map by 1

+ √ d. Due to (4.2), F(x) = 1 + x 2 f h ( (x))
f and so, by the chain rule,

∂xF = f h ( (x)) f x T 1 + x 2 + 1 + x 2 ∂ φ(x) f ∂x f .
Now, by the triangle inequality,

∂xF ≤ f h ( (x)) f x 1 + x 2 + 1 + x 2 ∂ φ(x) f ∂x f .
On the one hand,

f h ( (x)) f ≤ 1,
by Proposition 4.1 [START_REF] Bürgisser | Smoothed analysis of complex conic condition numbers[END_REF]. On the other hand,

∂ φ(x) f ∂x = ∂ (x) f |T (x) S n ∂x ≤ ∂ (x) f |T (x) S n ∂x ≤ √ d f 1 + x 2
, by Proposition 4.1 (2) and (4.5). Hence

∂xF ≤ x 1 + x 2 + √ d ≤ 1 + √ d
as we wanted to show. The claim about F(x) follows from Proposition 4.1 (1) applied to the formula above.

Interval approximations

Recall that our interval approximations, given in Proposition 2.1, rely on the functions f and ∂f given, respectively, in (2.4) and (2.5). The following lemma will give us the justification of our interval approximations, and with it a proof of Proposition 2.1. Once we have shown that our interval approximations are so, we show Theorem 2.1 which reduces the interval condition C f (B) to the condition C f (B) at a point.

Lemma 4.2 Let x ∈ R n and s ∈ [0, 1/ √ 2]. Then for all v, w ∈ B(x, s x ), we have v, w > v w (1 - 2s 2 ) ≥ 0.
Proof (Proof of Theorem 2.1) By the 2 -∞ inequality, interval approximations of Proposition 2.1 satisfy that for all

B ∈ R n dist ((hf )(m(B)), [hf ](B)) ≤ 1 + √ d √ n w(B)/2 (4.6) and dist (h ∂f )(m(J)), [h ∂f ](B) ≤ 1 + √ d -1 nw(B)/2 (4.7)
where dist is the usual Euclidean distance.

When the condition on f (m(J)) is satisfied, (4.6) guarantees that 0 / ∈ [hf ](J). Whenever the condition on ∂f (m(J)) is satisfied, (4.7) and Lemma 4.

2 (with s = 1/ √ 2) guarantee that 0 / ∈ [h ∂f ](J), [h ∂f ](J) . Hence C f (B) implies C f (B).
Proof (Proof of Lemma 4.2) Let s = cos θ, so that θ ∈ [0, π/4], c = √ 1 -s 2 and Kc := {u ∈ R n | x, u ≥ x u c} the convex cone of those vectors u whose angle x u with x, is at most θ.

Given v, w ∈ Kc, we have, by the triangle inequality, that v w ≤ v x + x w ≤ 2θ ≤ π/2. Thus

cos v w ≥ cos ( v x + x w) ≥ cos 2θ = 1 -2s 2 ≥ 0.
And so, it is enough to show that B c x (x) ⊆ Kc or, equivalently, that dist(x, ∂Kc) ≤ c x . Now, dist(x, ∂Kc) = min{ x -u | x, u = x u c} where the latter equals the distance of x to a line having an angle θ with x, which is x s.

Condition number

As other numerical algorithms in computational geometry, the Plantinga-Vegter algorithm has a cost which significantly varies with inputs of the same bit size. One wants to explain this variation in terms of geometric properties of the input. Condition numbers allow for such an explanation. Definition 5.1 [START_REF] Bürgisser | Computing the homology of basic semialgebraic sets in weak exponential time[END_REF][START_REF] Cucker | Approximate zeros and condition numbers[END_REF][START_REF] Cucker | Computing the Homology of Real Projective Sets[END_REF]

Given f ∈ H n,d , the local condition number of f at y ∈ S n is κ(f, y) := f f (y) 2 + 1 d ∂yf |TyS n 2 . Given f ∈ P n,d , the local affine condition number of f at x ∈ R n is κ aff (f, x) := κ(f h , (x)).

What does κ aff measure?

The nearer the hypersurface V R (f ) is to having a singularity at x ∈ R n , the smaller are the boxes drawn by the Plantinga-Vegter algorithm around x. Instead of controlling how near x is of being a singularity of f , we perform a Copernican turn and we control instead how near f is of having a singularity at x. This is precisely what κ aff (f, x) does. be the set of polynomials in P n,d that have a singularity at x. Then for every f ∈ P n,d ,

f κ aff (f, x) = dist(f, Σx)
where dist is the distance induced by the Weyl norm on P n,d .

Proof This is a reformulation of [5, Theorem 4.4] (cf. [4, Proposition 19.6]).

Theorem 5.1 provides a geometric interpretation of the local condition number, and a corresponding "intrinsic" complexity parameter as desired by Burr, Gao and Tsigaridas in [START_REF] Michael | The complexity of an adaptive subdivision method for approximating real curves[END_REF][START_REF] Michael | The complexity of subdivision for diameter-distance tests[END_REF]. The next result is an essential tool for the probabilistic analyses. Note that, in the case under consideration, Σx is a linear subspace of codimension n + 1 inside P n,d .

Corollary 5.1 Let x ∈ R n and let Rx :

P n,d → Σ ⊥
x be the orthogonal projection onto the orthogonal complement of the linear subspace Σx. Then

κ aff (f, x) = f Rxf .
Proof We have that dist(f, Σx) = Rxf since Σx is a linear subspace. Hence Theorem 5.1 finishes the proof.

The equality in Corollary 5.1 should not come as a surprise, since κ aff is defined in a way that the denominator is the norm of a vector depending linearly on f .

Regularity inequality

After doing our Copernican turn, we can control how near is f ∈ P n,d of having a singularity at x ∈ R n . The regularity inequality [6, Proposition 3.6] (cf. [34, Proposition 1 §2 3]) allows us to recover how near is x of being a singularity of f . More precisely, the regularity inequality gives lower bounds for the value of the function or its derivative in terms of the condition number.

f (x) > 1 2 √ 2d κ aff (f, x) or ∂f (x) > 1 2 √ 2d κ aff (f, x) .
Proof Without loss of generality assume that f = 1. Let y := (x), g := f h and assume that the first inequality does not hold. Then, by (4.2),

|g(y)| ≤ 1 2 √ 2d κ(g, y) 1 + x 2 . Now, 1 √ 2κ(g, y) ≤ max |g(y)|, 1 √ d ∂yg Ty S n = 1 √ d ∂yg Ty S n , since |g(y)| < 1 √ 2κ(g,y)
. Thus, by (4.3) and (4.5), we get

1 √ 2 κ(F, y) ≤ ∂xf (1 + x 2 ) d/2 - df (x)x T (1 + x 2 ) d/2+1 1 + x 2 √ d .
We divide by √ d and use the triangle inequality to obtain

1 √ 2d κ(F, y) ≤ ∂xf d(1 + x 2 ) d/2-1 + |f (x)| (1 + x 2 ) (d-1)/2 x 1 + x 2 = ∂f (x) + f (x) x 1 + x 2 .
By our assumtption and x < 1 + x 2 , the above inequality implies

1 √ 2d κ(F, y) < ∂f (x) + 1 2 √ 2d κ aff (f, x)
, from where the desired inequality follows.

Complexity Analysis of the Interval version

We analyze the complexity of PV-Interval in terms of the number of arithmetic operations the algorithm performs. This task reduces to estimating the number of boxes in the final subdivision produced by the algorithm. At the interval level, this is so, because each iteration of the algorithm takes the same number of arithmetic operations and the number of iterations is bounded by twice the number of final cubes. This was the underlying strategy in [START_REF] Michael | The complexity of an adaptive subdivision method for approximating real curves[END_REF].

Local size bound framework

The original analysis in [START_REF] Michael | The complexity of an adaptive subdivision method for approximating real curves[END_REF] was based on the notion of local size bound. The idea behind the local size bound is that it gives us the size from which every box containing x satisfies C. In our case, we will apply this to the condition C f introduced in Theorem 2.1. Arguing as in [10, Proposition 4.1], one can easily get the following general bound. Although the proposition 6.1 is stated here for the particular case of the PV-algorithm, it's a general fact of subdivision based algorithms. Proposition 6.1 [START_REF] Michael | The complexity of an adaptive subdivision method for approximating real curves[END_REF] The number of boxes in the final subdivision S returned by PV-Interval on input

(f, a) is at most (2a) n / inf{b(x) | x ∈ [-a, a] n } (6.1)
where b is a local size bound for C f (of Theorem 2.1).

The bound above is quite conservative as it considers the worst b(x) over the x ∈ [-a, a] n . Continuous amortization developed by Burr, Krahmer and Yap [START_REF] Burr | Continuous amortization: A non-probabilistic adaptive analysis technique[END_REF][START_REF] Michael | Continuous amortization and extensions: with applications to bisection-based root isolation[END_REF], provides the following refined complexity estimate [10, Proposition 5.2] which is adaptive. To effectively use Theorem 6.1 we need explicit constructions for the local size bound.

Condition-based local size bound and complexity

The following result expresses a local size bound for C f in terms of the local condition number κ aff (f, x).

f (m(B)) ≥ 1 2 √ 2d κ aff (f, x) -(1 + √ d) √ n w(B)/2 or ∂f (m(B)) ≥ 1 2 √ 2d κ aff (f, x) -(1 + √ d -1) √ n w(B)/2.

This means that

C f (B) is true if either 2 √ 2d (1 + √ d) √ n κ aff (f, x)w(B) < 1 or 2 √ 2d (1 + √ d -1)nκ aff (f, x)w(B) < 1.
Hence we get that C f (B) is true when both conditions are satisfied and the inequality 1

+ √ d ≤ 2 √ d
finishes the proof.

Using the results above, we get the following theorem exhibiting a condition-based complexity analysis of Algorithm 1.

d n max{1, a n }2 n log n+ 9 2 n E x∈[-a,a] n (κ aff (f, x) n ) .
The number of arithmetic operations performed by PV-Interval on input (f, a) is at most

O d n+1 max{1, a n }2 n log n+ 9 2 n N E x∈[-a,a] n (κ aff (f, x) n ) .
Proof It follows from Theorems 6.1 and 6.2 combined with the fact that [-a,a] n κ aff (f, x) n dx equals (2a) n E x∈[-a,a] n (κ aff (f, x) n ). The latter follows from the fact that one performs O(dN ) arithmetic operations to test C f and that the number of boxes that the algorithm generates is at most two times the number of final boxes.

The above condition-based complexity estimate will become the main tool to prove Theorem 3.1 in Section 8 where we will study the quantity E x∈[-a,a] n (κ aff (f, x) n ) for random f. In the literature on numerical algorithms in real algebraic geometry [START_REF] Bürgisser | Computing the homology of basic semialgebraic sets in weak exponential time[END_REF][START_REF] Bürgisser | Computing the Homology of Semialgebraic Sets. I: Lax Formulas[END_REF][START_REF] Bürgisser | Computing the Homology of Semialgebraic Sets. II: General formulas[END_REF][START_REF] Cucker | A numerical algorithm for zero counting. I: Complexity and accuracy[END_REF][START_REF] Cucker | A numerical algorithm for zero counting. II: Distance to ill-posedness and smoothed analysis[END_REF][START_REF] Cucker | A numerical algorithm for zero counting. III: Randomization and condition[END_REF][START_REF] Cucker | Computing the Homology of Real Projective Sets[END_REF], it is customary the use the following condition number

κ aff (f ) := max x∈[-a,a] n κ aff (f, x).
The quantity E x∈[-a,a] n (κ aff (f, x) n ) in Theorem 6.3 is an average quantity, where else the customary condition number κ aff (f ) is a global suprema. The average quantity has finite expectation (over f), where the global suprema does not admit bounded first moment. This shows that a condition-based precision control combined with adaptive complexity techniques such as continuous amortization may lead to substantial improvements in computational real algebraic geometry.

Interlude: Complexity of the interval version of [10]

In [START_REF] Michael | The complexity of an adaptive subdivision method for approximating real curves[END_REF], Burr, Gao and Tsigaridas gave an interval version of PV-Abstract different from PV-Interval based in the BGT interval approximation which relies on Taylor series. We provide a conditionbased and probabilistic complexity analysis of this algorithm, although only for the interval version, on which we only bound the number of cubes and not the number of arithmetic operations.

We recall that Burr, Gao and Tsigaridas [START_REF] Michael | The complexity of an adaptive subdivision method for approximating real curves[END_REF] showed that

C(f, x) := min 2 n-1 d/ ln 1 + 2 2-2n + √ n/2 dist(x, V C (f )) , 2 2n (d -1)/ ln 1 + 2 2-4n + n/2 dist((x, x), V C (g f ))
where g f is the polynomial ∂f (X), ∂f (Y ) , is a local size bound for the condition that their interval version of PV-Abstract checks.

Theorem 6.4 [START_REF] Michael | The complexity of an adaptive subdivision method for approximating real curves[END_REF] The maps

x → 1/C(f, x) n
is a local size bound function for the condition that the BGT interval version of PV-Abstract checks.

Looking at the definition of C(f, x) in [START_REF] Michael | The complexity of an adaptive subdivision method for approximating real curves[END_REF] one can see that 1/C measures how near is x of being a singular zero of f . This is similar to 1/κ aff which, by Theorem 5.1, measures how near is f of having x as a singular zero. The following result relates these two quantities.

Theorem 6.5 Let d > 1 and f ∈ P n,d . Then, for all x ∈ R n , C(f, x) ≤ 2 3n d 2 κ aff (f, x).
Proof Note that Lemma 4.1 holds over the complex numbers as well. Due to this and the fact that

V C (f ) = V C ( f ), we have that f (x) ≤ (1 + √ d) dist(x, V C (f )). Now, if √ 2(1 + √ d -1) dist((y 1 , y 2 ), (x, x)) < ∂f (x) , then √ 2(1 + √ d -1) y i -x < ∂f (x)
. Thus, by Lemma 4.1, √ 2 ∂f (y i ) -∂f (x) < ∂f (x) and so, by Lemma 4.2, 0 = ∂f (y 1 ), ∂f (y 2 ) . Hence ∂f (x)

≤ √ 2(1 + √ d -1) dist(x, V C (g f ))
.

The bound now follows from Proposition 5.1, together with 2

3(n-1) d + √ n ≤ 2 3n-2 d and min 2 n-1 d ln (1 + 2 2-2n ) + √ n 2 , 2 2n (d -1) ln (1 + 2 2-4n ) + n 2 ≤ 2 3n-4 d + √ n 2 .
The latter follows from

1 ln (1 + 2 2-2n ) ≤ 2 2n-3 and 1 ln (1 + 2 2-4n ) ≤ 2 4n-3 , (6.2)
which are deduced from first-order approximations of the natural logarithm. Theorems 6.4 and 6.5 combined with the continuous amortization of Burr, Krahmer and Yap [START_REF] Burr | Continuous amortization: A non-probabilistic adaptive analysis technique[END_REF][START_REF] Michael | Continuous amortization and extensions: with applications to bisection-based root isolation[END_REF] gives the following complexity analysis.

d 2n max{1, a n }2 3n 2 +2n E x∈[-a,a] n (κ aff (f, x) n ) . Remark 6.1
The main difference between C(f, x) and κ(f, x) is that C(f, x) is a non-linear quantity and is hard to compute and to analyze, while the local condition number κ(f, x)-as indicated in Corollary 5.1-is a linear quantity, easier to compute and analyze.

We finish this interlude giving the probabilistic consequence of the above corollary. For proving it, one only has to use the techniques from Sections 8. Theorem 6.6(A) Let f ∈ P n,d be a dobro random polynomial with parameters K and ρ. The expected number of boxes in the final subdivision S of the BGT interval version of PV-Abstract on input (f, a) is at most

d n 2 N n+1 2 max{1, a n }2 3n 2 +n log n+7n+ 15 2 (Kρ) n+1 .
(S) Let f ∈ P n,d , σ > 0, and g ∈ P n,d a dobro random polynomial with parameters K ≥ 1 and ρ . Then the expected number of boxes of the final subdivision F of the BGT interval version of PV-Abstract on input (qσ, a) where qσ = f + σ f g is at most

d n 2 N n+1 2 max{1, a n }2 3n 2 +n log n+7n+ 15 2 (Kρ) n+1 .
Proof Apply Corollaries 8.1 and 8.3 to Corollary 6.1.

Error and complexity analysis of the effective version

For an arithmetic expression φ and a point x ∈ R, we will denote by fl(φ(x)) ∈ F the value obtained when evaluating φ at r(x) ∈ F using floating-point finite precision. In general, our objective is to show that for such expressions φ in our algorithm we have, for some other expression ψ(x) and some

k ∈ N, fl(φ(x)) = φ(x) + ψ(x)θ k where θ k is any number δ ∈ R satisfying |δ| ≤ ku 1 -ku .
Note, this requires ku < 1. This is the general strategy in [25, Chapter 3]. We proceed by introducing a new error symbol which will make our manipulations easier, then we recall some fundamental numerical algorithms for computing inner product and monomials and we apply them to the computed quantities during the execution of algorithm PV-Effective.

The arithmetic of error accumulation

To ease the notation of [25, Chapter 3], we slightly rewrite the notation used there. Instead of using the symbol θ k for controlling errors, we will use ((k)) and we will allow non-integer values inside. A fundamental way in which our treatment will differ is that we will reform the interpretation of the use of ((k)) to make manipulations easier, emphasizing the use of the symbol instead of the error bounds directly.

Let φ be some arithmetic expression. Whenever we write an expression of the form fl(φ(x)) = φ (x, ((t 1 )) , . . . , ((t ))) (

for some arithmetic expression φ and for some real numbers t 1 , . . . , t ≥ 1, we will mean that, as long as max{t 1 , . . . , t }u < 1/2, we have

fl(φ(x)) = φ (x, τ 1 , . . . , τ )
for some

τ 1 ∈ - t 1 u 1 -t 1 u , t 1 u 1 -t 1 u , . . . , τ ∈ - t u 1 -t u , t u 1 -t u .
We note that in this notation we are allowing more freedom as we don't require t 1 , . . . , t to be integers. Furthermore, and this will make it computationally as useful as Landau notation, we introduce the following additional, asymmetric, notation.

For max{t 1 , . . . , t , t 1 , . . . , t }u < 1/2, we write φ (x, ((t 1 )) , . . . , ((t ))) = φ x, t 1 , . . . , t (ii) On input x ∈ F m , the computed value fl( x ) satisfies fl( x ) = x (1 + ((log m + 3))). (7.4)

(iii) Assume x ∈ F m and x ∈ R m are such that, for all i, xi = x i + t i (( ))
for some t ∈ [0, ∞) m and ≥ 1. Then the computed value fl( x ) satisfies fl( x ) = x + max{ x , t } ((log m + + 3)) .

Proposition 7.4 There is a numerical algorithm which, with input x ∈ R n and α ∈ N, computes x α .

This algorithm satisfies the following:

(i) It performs O(log |α|) arithmetic operations. (ii) On input x ∈ F n , the computed value fl(x α ) satisfies fl(x α ) = x α (1 + ((|α| -1))) if |α| > 1
x α , otherwise.

(iii) Assume that x ∈ F n and x ∈ R n are such that, for all i,

xi = x i (1 + (( )))
for some t ∈ [0, ∞) m and ≥ 1. Then the computed value fl(x α ) satisfies

fl(x α ) = x α (1 + ((|α|(1 + ) -1))), if α = 0 1, otherwise.
Proof (Proof of Proposition 7.

2) The algorithm will first perform all the products x i y i and them perform their sum by recursively dividing the sum into

i∈I x i y i + i∈I x i y i
where I and its complement, I have size almost equal, differing in at most one. (i) We initially perform m products and then m -1 additions. Note that the latter is independent of how we achieve the final sum, we sum as we do to minimize the error.

(ii) We will prove using induction the stronger claim that for the above algorithm fl( x, y ) = x, y + |x|, |y| (( log m + 1))

where x is the minimum integer bigger or equal than x. Note that the claim is true for m = 1 and m = 2. By the recursive nature of the algorithm, we have that

fl m i=1 x i y i = fl i∈I x i y i + fl   i∈I x i y i   = i∈I x i y i + i∈I |x i ||y i | (( log |I| + 1)) + i∈I x i y i +   i∈I |x i ||y i |   (( log(n -|I|) + 1))   (1 + ((1))) (Induction) = n i=1 x i y i + n i=1 |x i ||y i | ((log max{|I|, n -|I|} + 1)) (1 + ((1))) (E6) = ( x, y + |x|, |y| (( log max{|I|, n -|I|} + 1))) (1 + (( 1

)))

Proof To compute the Weyl norm, we first compute the vector ( d α )

-1/2 fα and then its norm. To compute the vector, we take the floating point approximation of ( d α ), we compute its square root and we divide fα by the computed square root. Hence

fl   d α -1/2 fα   = d α -1/2 fα (1 + ((1))) 1 + ((1))(1 + ((1)) = d α -1/2 fα(1 + ((5))) (Proposition 7.1)
Now, the lemma follows from Proposition 7.3.

The following two propositions show that we can compute | f | and ∂f in a stable way.

Proposition 7.5 There is a numerical algorithm which, with input f ∈ P n,d and

x ∈ R n , computes | f (x)|.
This algorithm performs O(dN ) arithmetic operations, and, on input x ∈ F n and f

∈ P n,d ∩F[X 1 , . . . , Xn], the computed value fl(| f (x)|) satisfies fl(| f (x)|) = | f (x)| + 1 + x ((32d log(n + 1))) .
In particular, if the round-off unit satisfies

u ≤ 1 64d log(n + 1) , then for x ∈ [-a, a] n ∩ F n , fl(| f (x)|) -| f (x)| ≤ 64 √ 2d √ n + 1 log(n + 1) max{1, a}u.
The above remains true for arbitrary f and x if we apply the algorithm to r(f ) and r(x).

Proof We first compute f (x) as (fα), (x α )) , where the x α are computed one by one, and then divide the result by the computed f (1, x) d-1 to obtain f (x). By Propositions 7.2 and 7.4 and (E7), we have that

fl(f (x)) = f (x) + f (1, x) d ((log N + d + 1)) , since (
fl f (1, x) d-1 = f (1, x) d-1 (1 + ((log N + d log(n + 1) + 4d + 2))).
Now, N ≤ (n + 1) d . Thus we have that

fl(f (x)) = f (x) + f (1, x) d ((3d log(n + 1)))
and

fl( f (1, x) d-1 ) = f (1, x) d-1 (1 + ((8d log(n + 1)))).
Although, doing this we are not obtaining tight bounds, we have to recall that the number of digits is proportional to the logarithm of what is inside ((•)).

To finish, we only have to do the division. Thus where the first equality follows from how we compute f (x), the second one from the above identities, the fourth one from (E3) and (E2), the sixth one from Lemma 4.1 and (E7), the eighth one from (E2), and the last one from (E1).

fl( f (x)) = fl(f (x))/fl( f (1, x) d-1 )(1 + ((1))) = (f (x) + f (1, x) d ((3d log(n + 1))))/ f (1, x) d-1 (1 + ((7d log(n + 1)))) (1 + (( 1
The result for r(f ) and r(x) follows similarly.

Proposition 7.6 There is a round-off algorithm which, with input f ∈ P n,d and x ∈ R n , computes ∂f (x) . It performs O(dN ) arithmetic operations, and, on input x ∈ F n and f ∈ P n,d ∩ F[X 1 , . . . , Xn], the computed value ∂f (x) satisfies fl( ∂f (x) ) = ∂f (x) + 1 + x ((32d log(n + 1))) .

In particular, if the round-off unit satisfies

u ≤ 1 64d log(n + 1) , then for x ∈ [-a, a] n ∩ F n , fl( ∂f (x) ) -∂f (x) ≤ 64 √ 2d √ n + 1 log(n + 1) max{1, a}u.
The above remains true for arbitrary f and x if we apply the algorithm to r(f ) and r(x).

Proof We compute each ∂ j f (x) as we computed f (x). After that, we compute ∂f (x) , d f (1, x) d-2 and their quotient. By Propositions 7.2 and 7.4 and (E7), we have that

fl(∂ j f (x)) = ∂ j f (x) + ∂ j g(|x|) ((log N + d + 1)) ,
where g = α |fα|X α . Now, by Proposition 7.3, we have that fl( ∂f (x) ) = ∂f (x) + max{ ∂f (x) , ∂g(|x|) } ((log N + log n + d + 4)) .

However, by Lemma 4.1, both ∂f (x) and ∂g(|x|) are bounded by d f (1, x) d-1 . Thus, by (E7),

fl( ∂f (x) ) = ∂f (x) + d f (1, x) d-1 ((log N + log n + d + 4)) .
Again, by Proposition 7.3, Lemma 7.1 and (E2), we have that

fl d f (1, x) d-2 = d f (1, x) d-2 (1 + ((log N + d log(n + 1) + 4d + 2))).
Now, as N ≤ (n + 1) d , we have

fl( ∂f (x) ) = ∂f (x) + d f (1, x) d-1 ((7d log(n + 1)))
and

fl d f (1, x) d-2 = d f (1, x) d-2 (1 + ((8d log(n + 1)))).
Now, arguing as in Proposition 7.5, the desired statement follows.

We can now show the correctness of Algorithm PV-Effective. We will denote by fl(B) the rounding r(B) of a box given by m(fl(B)) = m(B)(1 + ((1))) and w(fl(B)) = w(B)(1 + ((1))).

Similarly, we will write fl(f ) to denote the rounding r(f ) of f . The next theorem shows that if the round-off unit is sufficiently small, then a floating-point version of condition C f (B) is good enough to check C f (B). Combining the two pairs of inequalities above we get

| f (m(B))| > 2 √ d √ n + 1w(B) + 2 √ d √ n + 1w(B) 1 - 1 4 √ dn min{1, w(B)} max{1, a} - log(n + 1) 2 √ n + 1 min 1, 1 w(B) (7.5)
and

∂f (m(B)) > 3 √ d(n + 1)w(B) + 3 √ d(n + 1)w(B) 1 - 1 6 √ dn min{1, w(B)} max{1, a} - log(n + 1) 2(n + 1) min 1, 1 w(B) (7.6)
Now, the term between parentheses in the right-hand side of (7.5) is positive since

1 4 √ dn min{1, w(B)} max{1, a} + log(n + 1) 2 √ n + 1 min 1, 1 w(B) ≤ 1 4 √ dn + log(n + 1) 2 √ n + 1 ≤ 1 4 + 1 2 < 1,
and so is the one in the right-hand side of (7.6) since 1 6

√ dn min{1, w(B)} max{1, a} + log(n + 1) 2(n + 1) min 1, 1

w(B) ≤ 1 6 √ dn + 1 2 √ n + 1 ≤ 1 6 + 1 2 √ 2 < 1.
Therefore our claim holds.

Complexity of Algorithm PV-Effective

We now prove the analogous of Theorem 6.2 in the finite-precision setting. To do so we have to slightly modify the sense of the term 'local size bound' to take finite precision into account.

Definition 7.1 A local size bound for C FP f is a function b FP f : R n → [0, ∞) such that for all x ∈ R n , b FP f (x) ≤ inf vol(B) | x ∈ B ∈ R n , C FP f (B) False with u ≤ 1 128 √ dn min{1, w(B)} max{1, a} .
The modifications takes into account that the condition C FP f is checked with sufficiently large precision, as indicated by Theorem 7.1. The theorem below gives us the local size bound for finite precision.

) > 1 2 √ 2dκ aff (f, x) - (1 + √ d) √ n 2 w(B) - √ d log(n + 1) min{1, w(B)} > 1 2 √ 2dκ aff (f, x) -2 √ dnw(B) or fl ∂fl(f )(m(fl(B))) > 1 2 √ 2dκ aff (f, x) - (1 + √ d -1) √ n 2 w(B) - √ d log(n + 1) min{1, w(B)} > 1 2 √ 2dκ aff (f, x) -2 √ dnw(B).
Hence C FP f (B) holds as long as

1 2 √ 2dκ aff (f, x) -2 √ dnw(B) > 6 √ d(n + 1)w(B) 1 + 1 8 √ dn min{1, w(B)} max{1, a} , which is implied by 2 6 d(n + 1)κ aff (f, x)w(B) < 1.
This means that C FP f (B) is true when vol(B) < 1/ 2 6 dnκ aff (f, x) n , which is what we wanted to show.

Using the continuous amarotization [START_REF] Burr | Continuous amortization: A non-probabilistic adaptive analysis technique[END_REF][START_REF] Michael | Continuous amortization and extensions: with applications to bisection-based root isolation[END_REF] (we use the statement in [11, Theorem 5]), we obtain the following condition-based complexity analysis of PV-Effective.

Theorem 7.3

The number of boxes in the final subdivision S of PV-Effective on input (f, a) is at most

d n a n 2 n log n+8n E x∈[-a,a] n (κ aff (f, x) n ) .
The number of arithmetic operations performed by PV-Effective on input (f, a) is at most

O d n+1 a n 2 n log n+8n N E x∈[-a,a] n (κ aff (f, x) n ) . Furthermore, the bit-cost of PV-Effective on input (f, a) is at most O d n+1 a n 2 n log n+8n N log 2 (dna) E x∈[-a,a] n κ aff (f, x) n log 2 κ aff (f, x)
under the assumptions that floating-point arithmetic is done using standard arithmetic and that that the cost of operating with the exponents is negligible.

Proof The first two points follow from Theorems 7.2 and 6.1. For the third point, we recall the following variant of Theorem 6.1 that can be found in [START_REF] Michael | The complexity of subdivision for diameter-distance tests[END_REF]Theorem 5]. Let S be the final subdivision output by PV-Interval and h : (0, ∞) → (0, ∞) a continuous map. Then

h (w(B)) ≤ max h(2a), [-a,a] n 2 n b FP f (x) h b FP f (x) 1 n 2 dx .
Applying Theorem 7.2, we get the bound

B∈S h (w(B)) ≤ max h(2a), 2 n log n+7n d n [-a,a] n κ aff (f, x) n h 2 5 dnκ aff (f, x) dx .
Now, we note that testing C FP f at each of the boxes along the way takes at most O(dN ) arithmetic operations and that the number of boxes that the algorithm deals with is at most twice the number of final boxes. Because of this, the bit-cost of the algorithm (ignoring the cost of operating with exponents) in floating-point arithmetic is

O dN B∈S m 2 B .
This is so, because each arithmetic operation takes O(m gives the final bound.

The above condition-based complexity estimate will become the complexity estimates in Theorem 3.2 in the coming Section 8.

Probabilistic analyses

In this section, we prove Theorems 3.1 and 3.2 stated in Section 3 using Theorems 6.2 and 7.2 respectively.

Probabilistic toolbox

We now introduce our probabilistic toolbox. The main tools are a tail bound on the norm of a random vector and a small ball type estimate to ensure norm of a random projection is not too small. Following [34, 5 §1 ], we will give explicit constants avoiding the use of undefined absolute constants. This will require us to sketch some proofs.

Theorem 8.1 Let x ∈ R N be a random vector where each component x i is centered and sub-Gaussian with ψ 2 -norm K. Then for all t ≥ 5K √ N , . By Markov's inequality and independence,

P ( x ≥ t) ≤ exp - t 2 (5K) 2 . ( 8
P ( x ≥ t) ≤ e -s 2 t 2 Ee s 2 x 2 = N i=1 Ee s 2 x 2 i .
By assumption, for each i,

Ee s 2l x 2 i = ∞ l=0 s 2l Ex 2l i l! ≤ ∞ l=1 s 2l K 2l (2l) l l! ≤ ∞ l=0 2eK 2 s l l
, since l! ≥ (l/e) l . Thus, taking s 2 = 1/(4eK 2 ), we get

P ( x ≥ t) = 2 N e -t 2 /(4eK 2 ) .
The claim is now trivial assuming t ≥ 8e ln(2)K √ N .

Theorem 8.2 [31, Corollary 1.4] Let x ∈ R N be a random vector where each component x i has the anticoncentration property with constant ρ and P : R N → R N an orthogonal projection onto a k-dimensional linear subspace of R N . Then for all ε > 0,

P P x ≤ √ kε ≤ (3ρε) k .
Proof (Sketch of proof ) Note that by assumption, each x i has probability density (with respect to the Lebesgue measure) bounded by ρ/2. Then, by [26, , from where the claim follows.

Average Complexity Analysis

The following theorem is the main technical result from which the average complexity bound will follow. for a dobro random polynomial f with parameters K and ρ. This fact will be used without mention in the bounds below.

Proof (Proof of Theorem 8.3) By Corollary 5.1, we have that κ aff (f, x) = f / Rxf with Rx an orthogonal projection onto the (n + 1)-dimensional linear subspace Σ ⊥

x . By the union bound, for all u, t > 0, P (κ aff (f, x) ≥ t) ≤ P ( f ≥ u) + P ( Rxf ≤ u/t) .

(8.2)

We apply now Theorems 8.1 to the first term and 8.2 to the second. Thus for u > 5K √ N and t > 0, P(κ aff (f, x) ≥ t) ≤ exp(-u 2 /(5K) 2 ) + 3uρ

t √ n + 1 n+1 .
We set u = 5K N ln(t), so we get where Γ is Euler's Gamma function. We note that e α ≤ e n+1 and that, by the Stirling estimates, Combining all these inequalities, we obtain the desired upper bound. and the claim follows using Theorem 8.4 with α = n + 1 2 .

P (κ aff (f, x) ≥ t) ≤ t -N + 15Kρ √ N √ n + 1 n+1 ln(t)

Smoothed Complexity Analysis

The tools used for our average complexity analysis yield also a smoothed complexity analysis (see [START_REF] Spielman | Smoothed analysis of algorithms[END_REF] or [4, §2.2.7]). We provide this analysis following the lines of [START_REF] Ergür | Probabilistic Condition Number Estimates for Real Polynomial Systems II: Structure and Smoothed Analysis[END_REF].

The main idea of smoothed complexity is to have a complexity measure interpolating between worst-case complexity and average-case complexity. More precisely, we are interested in the maximum -over f ∈ P n,d -of the average cost of the algorithm when the input polynomial has the form qσ := f + σ f g (8.3)

with g ∈ P n,d is a dobro random polynomials with parameters K ≥ 1 and ρ, and σ ∈ (0, ∞). Notice that the perturbation σ f g of f is proportional to both σ and f . The following lemma shows how Theorems 8.1 and 8.2 apply to this class of random polynomials.

Lemma 8.1 Let qσ be as in (8.3). Then for t > 1 + σ

√ N P ( qσ ≥ t f ) ≤ exp - (t -1) 2 (σ5K) 2
and for every x ∈ R n ,

P ( Rxqσ ≤ ε) ≤ 3ρε/ σ f √ n + 1 n+1
where Rx is as in Corollary 5.1.

Proof By the triangle inequality we have P( qσ ≥ t f ) ≤ P( g ≥ (t -1)/σ). Then we apply Theorem 8.1 which finishes the proof of the first claim. The second claim is a direct consequence of Theorem 8.2.

As in the average case, this leads to a tail bound. Proof We proceed as in the proof of Theorem 8.3, but with Lemma 8.1 using u = f (σ5K N ln(t) + 1). This gives the desired bound arguing as in that proof after noticing that

u ≤ f (1 + σ)5K N ln(t)
which holds since 5K N ln(t) ≥ 1.

As in the average case, Theorem 8.5 yields probabilistic bounds for both E x∈[-a,a] n (κ aff (f, x) n ) and E x∈[-a,a] n κ aff (f, x) n log 2 κ aff (f, x) for random f. The two corollaries below, together with Theorems 6.2 and 7.2, gives us the proof of the part (S) of Theorems 3.1 and 3.2.

Theorem 8.6 Let qσ be as in (8.3) and α ∈ [1, n + 1). Then for all f ∈ P n,d and all σ > 0,

Eq σ E x∈[-a,a] n (κ aff (qσ, x) α ) ≤ 4 α √ n + 1 n + 1 -α N n + 1 -α n+1 2 (25Kρ) n+1 1 + 1 σ n+1 .
Proof The proof is as that of Theorem 8.4, but using Theorem 8.5 instead of Theorem 8.3.

  If n is fixed and d is let to vary, N = ( n+d n ) ≤ e n (1 + d n ) n . Hence the bounds of Theorems 3.1 and 3.2 are of the order d n 2 +5n 2 for any fixed n. The complexity estimate in [10, Theorem 4.3] reads as follows:2 O(d n+1 (nτ +nd log (nd))n log a)

Lemma 4 . 1 ( 1 )F

 411 Let f ∈ P n,d . Then: The map f given in(2.4) is (1 + √ d)-Lipschitz and for all x ∈ R n , it satisfies | f (x)| ≤ 1 + x 2 .(2) The map ∂f given in(2.5) is (1 + √ d -1)-Lipschitz and for all x ∈ R n , it satisfies ∂f (x) ≤ 1 + x 2 .Proof (Proof of Proposition 2.1) It is a straightforward consequence of the Lipschitz properties in Lemma 4.1.Proof (Proof of Lemma 4.1) (1) Apply Proposition 4.2 with f = f , then f = F and the claim follows.(2) Apply Proposition 4.2 with f = f , then ∂f = ∂f (X) d f and the claims follows since ∂f (X)

Theorem 5 . 1 (

 51 Condition Number Theorem) Let x ∈ R n and Σx := {g ∈ P n,d | g(x) = 0, ∂xg = 0} (5.1)

Proposition 5 . 1 (

 51 Regularity inequality) Let f ∈ P n,d and x ∈ R n . Then either

Definition 6 . 1 A

 61 local size bound for C : R n → {True, False} is a function b : R n → [0, ∞) such that for all x ∈ R n , b(x) ≤ inf{vol(B) | x ∈ B ∈ R n and C(B) False}.

Theorem 6 . 1 [ 8 , 9 , 10 ]

 618910 The number of boxes in the final subdivision S returned by PV-Interval on input (f, a) is at most where b is a local size bound for C f (of Theorem 2.1). Moreover, the bound is finite if and only if the algorithm terminates.

Theorem 6 . 2

 62 The map x → 1/ 2 5/2 dnκ aff (f, x) n is a local size bound for C f (of Theorem 2.1). Proof Let x ∈ R n . Since x ∈ B, x -m(B) ≤ √ nw(B)/2. Hence, by Lemma 4.1 and the regularity inequality (Proposition 5.1), either

Theorem 6 . 3

 63 The number of boxes in the final subdivision S of PV-Interval on input (f, a) is at most

Corollary 6 . 1

 61 The number of boxes in the final subdivision S of the BGT interval version of Algorithm 1 on input (f, a) is at most

( i )

 i It performs O(m) arithmetic operations.

  ))) = ( f (x) + (1, x) ((3d log(n + 1))) (1 + ((8d log(n + 1)))) -1 (1 + ((1))) = ( f (x) + (1, x) ((3d log(n + 1))) (1 + ((16d log(n + 1) + 1))) = f (x) + f (x) ((10d log(n + 1) + 1)) + (1, x) (((3d log(n + 1))) + ((3d log(n + 1))) ((14d log(n + 1) + 1))) = f (x) + (1, x) (((16d log(n + 1) + 1)) + ((3d log(n + 1))) + ((3d log(n + 1))) ((16d log(n + 1) + 1))) = f (x) + (1, x) ((19d log(n + 1) + 1)) = f (x) + (1, x) ((20d log(n + 1)))

Theorem 7 . 1 6 √

 716 Let B ∈ [-a, a] n . If f )(m(fl(B))) > fl 4 √ d √ n + 1w(fl(B))or ∂fl(f )(m(fl(B))) > fl f (B) holds and, hence, so does C f (B).

Corollary 7 . 1

 71 Algorithm PV-Effective is correct.Proof Note that the conditions of Propositions 7.5 and 7.6 are satisfied. Therefore we have that| f (m(B))| > fl fl(f )(m(fl(B))) - √ d log(n + 1) min{1, w(B)} and that ∂f (m(B)) > fl ∂fl(f )(m(fl(B))) - √ d log(n + 1) min{1, w(B)}after taking into account the bound for u.By error analysis (Proposition 7.1), we have that

Theorem 7 . 2 4 √

 724 The map x → 1/ 2 6 dnκ aff (f, x) n is a local size bound for C FP f (of Theorem 7.1). Proof The proof is similar to the one of Theorem 7.1. For now on, let B ∈ R n be such that x ∈ B. By Proposition 7.5 and 7.6 and the bound on u, we have that fl fl(f )(m(fl(B))) > f (m(B)) -√ d log(n + 1) min{1, w(B)} and that fl ∂fl(f )(m(fl(B))) > ∂f (m(B)) - √ d log(n + 1) min{1, w(B)}. d(n + 1)w(fl(B)) . By the regularity inequality (Proposition 5.1) and Corollary 4.1, we know that either fl fl(f )(m(fl(B))

B∈S

n+1 2 t 2 (

 22 n+1 for t ≥ e. The inequality n + 1 ≤ N finishes the proof. Theorem 8.3 immediately gives probabilistic bounds for the expressionsE x∈[-a,a] n (κ aff (f, x) n ) and E x∈[-a,a] n κ aff (f, x) n log 2 κ aff (f, x)for a random f. The two corollaries below, together with Theorems 6.2 and 7.2, give us the proof of the part (A) of Theorems 3.1 and 3.2.Theorem 8.4 Let f ∈ P n,d be a dobro random polynomial with parameters K and ρ and α ∈ [1, n + 1).Then E f E x∈[-a,a] n (κ aff (f, x) α ) ≤ 4 α √ n + 1 n + 1 -α N n + 1 -α n+1 25Kρ) n+1 .Corollary 8.1 Let f ∈ P n,d be a dobro random polynomial with parameters K and ρ. Then

E2 2 5n+ 3 2 log n+ 15 2

 315 f E x∈[-a,a] n (κ aff (f, x) n ) ≤ N n+1 (Kρ) n+1 .Corollary 8.2 Let f ∈ P n,d be a dobro random polynomial with parameters K and ρ. Then

E2 2 1 P+ 2 N

 212 f E x∈[-a,a] n κ aff (f, x) n log 2 κ(f, x) ≤ N n+1 6n+ 3 2 log n+12 (Kρ) n+1 .Proof (Proof of Theorem 8.4) By the Fubini-Tonelli theorem,E f E x∈[-a,a] n (κ aff (f, x) α ) = E x∈[-a,a] α E f (κ aff (f, x) n )so it is enough to have a uniform bound forE f (κ aff (f, x) α ) = ∞ (κ aff (f, x) α ≥ t) dt.Now, by Theorem 8.3, this is bounded by e α

Theorem 8 . 5 2 N n + 1 n+1 2 (

 85212 Let qσ be as in(8.3) and x ∈ R n . Then for σ > 0 and t ≥ e, P (κ aff (qσ, x) ≥ t) ≤ 15Kρ) n+1 ln(t)

  |fα|), (|x α |) = g(|x|), where g = α |fα|X α , is bounded by f (1, x) d , by Lemma 4.1. Also, by Proposition 7.3, Lemma 7.1 and (E2), we have that

  2 ) bit-time and m B is the maximum precision needed to test C FP O max log 2 2 9 √ dna, log 2 2 9 √

	dn	a w(B)

f in any box that is an ancestor of B. Hence, taking h(w(B)) =

  .1) Proof (Sketch of proof ) We follow the ideas in [35, Theorems 2.6.3]. Note that x ≥ t is equivalent to e s 2 x 2 ≥ e s 2 t 2

  Theorem 1.1.], P x has probability density (with respect to the Lebesgue measure) bounded by ρ/

		√	2	k . Thus
	P P x ≤	√ kε ≤ ω k	√ √ kρ 2

k

where ω k is the volume of the k-dimensional Euclidean ball. Now,

ω k k k 2 ≤ (2e) k 2 π k 2

  Theorem 8.3 Let f ∈ P n,d be a dobro random polynomial with parameters K and ρ. For all x ∈ R n and t ≥ e, P (κ aff (f, x) ≥ t) ≤ 2

	N n + 1	n+1 2	n+1 2 t n+1 . (15Kρ) n+1 ln(t)

Remark 8.1 By [21, (1)], we have Kρ ≥ 1 4

  Proof (Proof ofCorollary 8.1) We take α = n in Theorem 8.4.Proof (Proof of Corollary 8.2) Recall that log 2 y ≤ 5 √ y for y ≥ 1. HenceE f E x∈[-a,a] n κ aff (f, x) n log 2 κ(f, x) ≤ 2 5/2 E f E x∈[-a,a] n κ aff (f, x) n+ 1 2

The Plantinga-Vegter (Subdivision) Algorithm

Acknowledgements

We cordially thank Michael Burr and Elias Tsigaridas for useful discussions.

This work was supported by the Einstein Foundation Berlin. An extended abstract containing some of the results was presented at ISSAC'19 [14]. Some preliminary versions of the results in Section 8 was included in the doctoral thesis of J. Tonelli-Cueto [34]. F.C. was partially supported by a GRF grant from the Research Grants Council of the Hong Kong SAR (project number CityU 11302418). J. T.-C. was partially supported by ANR JCJC GALOP (ANR-17-CE40-0009), the PGMO grant ALMA, and the PHC GRAPE.

whenever for every

there exist

such that φ (x, τ 1 , . . . , τ ) = φ x, τ 1 , . . . , τ .

This is consistent with notation (7.1) in the sense that if both (7.1) and (7.2) hold then fl(φ(x)) = φ (x, ((t 1 )) , . . . , ((t ))). This will allow us to mechanically perform the finite precision analysis using the following rules.

Proposition 7.1 For all x, y ≥ 1, the following holds for the error symbol:

In particular, ((x)) + ((y)) = ((x + y)) and

Proof This follows from [START_REF] Higham | Accuracy and Stability of Numerical Algorithms[END_REF]Lemmas 3.1 and 3.3] The definition and properties of (( )) follow the lines of classical error analysis, as e.g., in [START_REF] Higham | Accuracy and Stability of Numerical Algorithms[END_REF]Chapter 3]. The presentation may differ in minor details which we have chosen for our own convenience.

Basic finite precision algorithms

The following two propositions show the nice properties of the numerical computations that underlie the algorithm PV-Effective. Their statements refer to three aspects: 1) the number of arithmetic operations performed, 2) error estimates for a given input, and 3) error estimates for approximate inputs. From these bounds we can obtain bit-complexity estimates, as floating-point operations take O(| log u| 2 )-time (this being non-tight, one can obtain better bounds using fast multiplication algorithms). (iii) Note that

x, ỹ =

Proof (Proof of Proposition 7.

3) The proof is analogous to that of Proposition 7.2.

Proof (Proof of Proposition 7.4) The proof is analogous to that of Proposition 7.2, but we have to take into account that errors accumulate additively since in each multiplication the errors of the computed quantities are added by (E2).

Finite-precision computations

We study the errors due to finite-precision in algorithm PV-Effective and show its correctness. The following lemma is useful.