Pierre Lairez

RIGID CONTINUATION PATHS I. QUASILINEAR AVERAGE COMPLEXITY FOR SOLVING POLYNOMIAL SYSTEMS

Keywords: Mathematics Subject Classification. Primary 68Q25; Secondary 65H10, 65H20, 65Y20. 1

How many operations do we need on average to compute an approximate root of a random Gaussian polynomial system? Beyond Smale's 17th problem that asked whether a polynomial bound is possible, we prove a quasi-optimal bound (input size) 1`op1q . This improves upon the previously known (input size) 3 2 `op1q bound. The new algorithm relies on numerical continuation along rigid continuation paths. The central idea is to consider rigid motions of the equations rather than line segments in the linear space of all polynomial systems. This leads to a better average condition number and allows for bigger steps. We show that on average, we can compute one approximate root of a random Gaussian polynomial system of n equations of degree at most D in n `1 homogeneous variables with Opn 4 D 2 q continuation steps. This is a decisive improvement over previous bounds that prove no better than ? 2 minpn,Dq continuation steps on average.

Introduction

Following a line of research opened in the 20th century by [START_REF] Smale | On the Efficiency of Algorithms of Analysis[END_REF]Smale ( , 1986)), [START_REF] Renegar | On the Efficiency of Newton's Method in Approximating All Zeros of a System of Complex Polynomials[END_REF]Renegar ( , 1989)), [START_REF] Demmel | The Probability That a Numerical Analysis Problem Is Difficult[END_REF], [START_REF] Shub | Complexity of Bézout's Theorem. I. Geometric Aspects[END_REF], [START_REF] Malajovich | On Generalized Newton Algorithms: Quadratic Convergence, Path-Following and Error Analysis[END_REF], and Shub and Smale (1993a,b,c, 1994[START_REF]Complexity of Bezout's Theorem. IV. Probability of Success; Extensions[END_REF] and developped in the 21st century by [START_REF] Armentano | Condition Length and Complexity for the Solution of Polynomial Systems[END_REF]Armentano et al. ( , 2018)), [START_REF] Bates | Numerically Solving Polynomial Systems with Bertini[END_REF], [START_REF] Beltrán | A Continuation Method to Solve Polynomial Systems and Its Complexity[END_REF], [START_REF] Beltrán | On Smale's 17th Problem: A Probabilistic Positive Solution[END_REF], 2009a,b, 2011), [START_REF] Beltrán | Complexity of Bezout's Theorem. VII. Distance Estimates in the Condition Metric[END_REF], [START_REF] Briquel | Fast Computation of Zeros of Polynomial Systems with Bounded Degree under Finite-Precision[END_REF], Bürgisser and[START_REF] Bürgisser | On a Problem Posed by Steve Smale[END_REF], [START_REF] Hauenstein | Certified Predictor-Corrector Tracking for Newton Homotopies[END_REF], [START_REF] Hauenstein | Algorithm 921: alphaCertified: Certifying Solutions to Polynomial Systems[END_REF], [START_REF] Lairez | A Deterministic Algorithm to Compute Approximate Roots of Polynomial Systems in Polynomial Average Time[END_REF]Malajovich (2018), to name a few, I am interested in the number of elementary operations that one needs to compute one zero of a polynomial system in a numerical setting. On this topic, Smale's question is a landmark: "Can a zero of n complex polynomial equations in n unknowns be found approximately, on average, in polynomial time with a uniform algorithm?" (Smale 1998, 17th problem). The wording is crafted to have a positive answer in spite of two major obstacles. The first one is the NP-completeness of many problems related to deciding the feasability of a polynomial system. Here, we consider well determined systems (as many equations as unknowns), over the complex numbers, in the average (a fortiori generic) case, so there will always be a zero. The second obstacle is the number of zeros: it is not polynomially bounded in terms of the input size (the number of coefficients that define the input system). Here, we ask for only one zero and numerical methods can take advantage of it.

Smale's question is now solved (Beltrán and Pardo 2009b;[START_REF] Bürgisser | On a Problem Posed by Steve Smale[END_REF][START_REF] Lairez | A Deterministic Algorithm to Compute Approximate Roots of Polynomial Systems in Polynomial Average Time[END_REF]; it is an achievement but not an end. The most obvious question that pops up is to improve the degree hidden behind the words "polynomial time". This article presents an optimal answer, bringing down "polynomial time", that is N Op1q , where N is the input size, to "quasilinear time", that is N 1`op1q . The previous state of the art was N 3 2 `op1q [START_REF] Armentano | Condition Length and Complexity for the Solution of Polynomial Systems[END_REF].

1.1. State of the art. Let n and d 1 , . . . , d n be positive integers, and let H be the vector space of tuples pf 1 , . . . , f n q of complex homogeneous polynomials of respective degrees d 1 , . . . , d n in the variables x 0 , . . . , x n . Let D denote maxpd 1 , . . . , d n q.

We are interested in the average complexity of finding one zero of a polynomial system, given as an element of H. The complexity is measured with respect to the input size, denoted N . This is the number of complex coefficients that describe a system, namely

N . " dim C H " ˆd1 `n n ˙`¨¨¨`ˆd n `n n ˙.
Note that N 2 minpn,Dq . "Average complexity" means that H is endowed with a probability measure (uniform on the unit sphere for some suitably chosen Hermitian norm) and that the behaviour the algorithms is analyzed on average, assuming that the input is distributed according to this probability measure. We will make use of randomized algorithms, that draw random numbers during their execution. In this case, the average complexity is an average with respect to both the input's distribution and the randomness used internally by the algorithm.

1.1.1. Classical theory. In the Shub-Smale-Beltrán-Pardo-Bürgisser-Cucker way of doing things, we compute a zero of a homogeneous polynomial system F P H by numerical continuation from a random system G P H of which we happen to know a zero ζ P PpC n`1 q. The continuation is performed along the deformation F t .

"

1 }tF `p1´tqG} ptF `p1 ´tqGq. Starting from t " 0, we repeatedly increment the parameter t and track a zero of F t with a projective Newton iteration applied to the previous approximation of the zero. If the increment is small enough then we can be sure not to loose the zero and to obtain, when t reaches 1, an approximate zero of the target system F . The total complexity of the algorithm depends on the number of continuation steps that are performed, which in turn depends on the size of the increment. The key issue is to specify how small is "small enough". Smale (1986) gave a sufficient condition for the Newton iteration to converge in terms of the gamma number γpF, zq, depending on a polynomial system F and a point z (see §2.5(8) for a definition). Difficulties in estimating the variations of γpF, zq with respect to F led Shub and Smale (1993a) to consider the condition number µpF, zq, which upperbounds γpF, zq and characterizes how much a zero z of a system F is affected by a small pertubation of F . They gave a sufficient condition for a continuation step to be small enough in terms of µ. After some refinements, [START_REF] Beltrán | Complexity of Bezout's Theorem. VII. Distance Estimates in the Condition Metric[END_REF] proved that KpF, G, ζq, the minimal number of steps to go from G to F while tracking the zero ζ, is bounded by (1) KpF, G, ζq (constant)

ż 1 0 µpF t , ζ t q b } 9 F t } 2 `} 9 ζ t } 2 dt.
This is called the "µ estimate". Explicit algorithms that achieve this bound have been designed by [START_REF] Beltrán | A Continuation Method to Solve Polynomial Systems and Its Complexity[END_REF], [START_REF] Dedieu | Adaptive Step-Size Selection for Homotopy Methods to Solve Polynomial Equations[END_REF], and [START_REF] Hauenstein | Certified Predictor-Corrector Tracking for Newton Homotopies[END_REF]. A simpler but weaker form, called the "µ 2 estimate", reads

(2) KpF, G, ζq (constant)D

3 2 d S pF, Gq ż 1 0 µpF t , ζ t q 2 dt,
where d S pF, Gq is the distance in the unit sphere SpHq from F to G, that is the length of the continuation path. It is often used in practice because it is much easier to design algorithms that achieve this bound rather than the former. In one form or the other, this kind of integral estimate for the number of steps is the first mainstay of the method.

The second mainstay is a procedure discovered by Beltrán and Pardo (2011) and simplified by [START_REF] Bürgisser | On a Problem Posed by Steve Smale[END_REF] to sample a Gaussian random system G P H together with one of its zeros without the need for solving a polynomial system: (1) sample a random Gaussian linear map L : C n`1 Ñ C n , (2) compute a nonzero vector ζ P C n`1 in the kernel of L and (3) sample a random Gaussian system in the affine subspace of H of all systems G such that Gpζq " 0 and d ζ G " L. By construction, we obtain a system G and one of its zeros ζ. Less trivially, G{}G} is uniformly distributed in the sphere SpHq. We could think of a simpler procedure that (1) samples some ζ P C n`1 isotropically and (2) samples a random Gaussian system in the linear subspace of H of all systems G such that Gpζq " 0. This also gives a random system with one of its zeros, by construction, but the system is not uniformly distributed in the sphere after normalization.

These two mainstays together give a randomized algorithm to compute a zero of a polynomial system and a way to analyze its average complexity on a random input. On input F P SpHq, the algorithm is: (1) uniformly sample a random system G P SpHq together with a zero ζ, (2) perform the numerical continuation from G to F tracking the zero ζ. If F itself is a uniformly distributed random variable, then for any t P r0, 1s, F t is also uniformly distributed, so pF t , ζ t q has the same distribution as pG, ζq. Therefore, the average number of steps performed by the algorithm is bounded by

E rKpF, G, ζqs (constant) E " D 3 2 d S pF, Gq ż 1 0 µpF t , ζ t q 2 dt  (constant)D 3 2 ż 1 0 E " µpF t , ζ t q 2 ‰ dt (constant)D 3 2 E " µpG, ζq 2 ‰ .
This leads us to the third mainstay: estimates for E " µpG, ζq 2 ‰ . Beltrán and Pardo (2011, Theorem 23) proved that E " µpG, ζq 2 ‰ nN . Therefore, the average number of steps performed by the algorithm on a random input is ErKpF, G, ζqs (constant)nN.

The cost of each continuation step (basically, the computation of µ and a Newton's iteration) can be done in OpN q operations (when D

2). All in all, the total average complexity of the classical algorithm is OpnD 3 2 N 2 q as N Ñ 8. When minpn, Dq Ñ 8, then this is N 2`op1q . 1.1.2. Improvements. How can we improve upon this complexity bound? We cannot do much about the OpN q cost of a continuation step, as it is already optimal. Concerning the number of steps, we can try to use the µ estimate instead of the µ 2 estimate. Bounding } 9

ζ t } by µpF t , ζ t q} 9 F t } (which turns the µ estimate into the µ 2 estimate) is optimal in the worst case, but on average, when the direction 9 F t is random, this is pessimistic. Building upon this idea, [START_REF] Armentano | Condition Length and Complexity for the Solution of Polynomial Systems[END_REF] proved that OpnD 3 2 N 1 2 q continuation steps are enough on average. This leads to a total average complexity of N 3 2 `op1q operations. [START_REF] Beltrán | Complexity of Bezout's Theorem. VII. Distance Estimates in the Condition Metric[END_REF] proved that there exist continuation paths that makes the µ estimate polynomially bounded in terms of n and D. The construction is explicit but it requires the knowledge of a zero of a target system. This prevents it from being used algorithmically. Yet, it was the first time that the possibility of performing numerical continuation in very few steps (polynomially many with respect to n and D, not N ) was supported.

Lastly, let us mention that [START_REF] Hauenstein | Certified Predictor-Corrector Tracking for Newton Homotopies[END_REF] developped a γ estimate, based on Smale's γ number. It may be used as a starting point to obtain very similar results to ours in a more traditional context. However, this direction is yet to be explored. 1.2. Contribution. I describe a randomized algorithm that uses a numerical continuation from a random start system to find one root of the input system. It performs Opn 4 D 2 q steps on average (and each step costs Opn 2 D 2 N q operations) for random Gaussian systems. This leads to a total average complexity of Opn 6 D 4 N q operations as N Ñ 8 to find one approximate root of a random Gaussian system (Theorem 40). When minpn, Dq Ñ 8, this is N 1`op1q . The algorithm relies on analogues of the three mainstays of the classical theory: integral estimate for the number of steps, randomization of the start system and average analysis of some condition number. However, the basic tools are thoroughly renewed.

The starting point is the observation that a typical system in H is poorly conditioned. As mentionned above, the expected squared condition number of a random system at a random zero is bounded by nN and it turns out that this is rather sharp. In view of Smale's question, this is satisfying, much more than bounds involving the total number of zeros, but this N is the limit of the method.

To improve the average conditioning, an idea is to define the notion of conditioning with respect to a much lower dimensional parameter space, but still big enough to be able to develop an analogue of Beltrán and Pardo's algorithm. I propose here the rigid setting, where the parameter space is not the whole space of polynomial systems, but the group U made of n copies of the unitary group U pn `1q, of real dimension " n 3 . It acts by rigid motions on the n components of a fixed, well determined, polynomial system. Figure 1 illustrates a rigid continuation path.

Less parameters is less opportunities for a dramatic pertubation that will ruin the conditioning of a system. Beyond that, the continuation paths in the rigid setting preserve the geometry of the input equations. This opens a way for studying the average complexity of solving certain structured systems. Forthcoming work will address this topic.

A noteworthy contribution is the introduction of the split gamma number which tightly upper bounds Smale's gamma number (Theorem 13) and which allows for (c) Continuously return to the original position while tracking the solution.

Figure 1. Resolution of a polynomial system with a rigid continuation path.

interesting average analysis, see §4.4. Finally, the foremost outcome of the rigid setting is Theorem 27 which gives an average bound on the necessary number of continuation steps to compute one root of a random system, with only a unitary invariance hypothesis on the probability distribution.

Ackowledgment. It is my pleasure to thank Carlos Beltrán, Peter Bürgisser and Felipe Cucker for many helpful discussions and valuable comments. I am very grateful to the referees for their conscientious work.

Notations and basic definitions.

n some positive integer (used as the number of nonhomogeneous variables).

P n complex projective space of dimension n. rzs projective class of some nonzero z P C n`1 . d P geodesic distance on P n endowed with the Fubini-Study metric, that is d P prxs, rysq " arcsin ´a1 ´|xx, yy| 2 ¯for any x, y P SpC n`1 q. H d space of complex homogeneous polynomials of degree d in x 0 , . . . , x n . r some positive integer (used as the number of equations

} ´}W

Weyl norm of a polynomial (see Bürgisser and Cucker 2013, §16.1). ~´~operator norm of a map between Hermitian spaces. For a multilinear map ϕ : E k Ñ V , this is sup t}ϕpe 1 , . . . , e k q} | }e 1 } " ¨¨¨" }e k } " 1u.

} ´}Frob

Frobenius norm of a map between Hermitian spaces. } ´}u 1{ ? 2 times } ´}Frob (used as the Riemannian metric on the tangent spaces of U pn `1q).

ϕ :

Moore-Penrose pseudo-inverse of a surjective linear map ϕ : E Ñ F , it is the unique linear map ψ : F Ñ E such that ϕψ " id F and ψϕ is the orthogonal projection onto the row space of ϕ (the orthogonal complement of the kernel).

d z F
the derivative of some polynomial map F : C n`1 Ñ C r at z P C n`1 . We will use the same notation with z P P n , which means that we choose a representative z P C n`1 of z such that }z} " 1. d z F :

the pseudo-inverse of the derivative. N F projective Newton's operator associated to F

.

"

"is defined as" A " OpBq as C Ñ 8

"there are C 0 0 and k 0 such that C C 0 ñ A kB". standard normal variable a Gaussian random variable of an Euclidean space with unit covariance matrix in some orthonormal basis. The notion is relative to the underlying Euclidean inner product. For a Hermitian space, we consider the induced Euclidean structure.

Rigid solution varieties

The classical solution variety is the subvariety of Hrrs ˆPn of all pF, ζq such that ζ is a zero of F . We now introduce an analogue variety in the rigid setting.

Let X 1 , . . . , X r be pure-dimensional subvarieties of P n , with ř i codim X i n. Let U denote the group U pn `1q r . It acts naturally on the product pP n q r of r copies of the projective space. We denote its elements in boldface u " pu 1 , . . . , u r q. Let X denote the product variety X 1 ˆ¨¨¨ˆX r Ă pP n q r . For u P U, let uX denote the image of X under the action of u, that is ś r i"1 u i X i , and let XuX denote the intersection X r i"1 u i X i Ď P n . The rigid solution variety is defined as

V . " tpu, xq P U ˆPn | x P XuX u .
There is not a single solution variety, but rather any choice of subvarieties X 1 , . . . , X r leads to a solution variety. In this section, we will study the geometry of V with X 1 , . . . , X r fixed. Later on, we will assume that X 1 , . . . , X r are hypersurfaces defined by random polynomials.

Let Gpkq denote the Grassmannian of k-dimensional projective subspaces of P n , that is k `1-dimensional linear subspaces of C n`1 . For a smooth point x P X i , the projectivization of the tangent space of the cone over X i at some representative x P C n`1 of x is an element of Gpk i q and is denoted T x X i . If X i is the zero set of some homogeneous polynomial system F i P Hrms, then T x pu i X i q is the projectivization of the kernel of d x pF i ˝u´1 i q. Let L .

" Gpdim X 1 q ˆ¨¨¨ˆGpdim X r q, and for h " ph 1 , . . . , h r q P L, let Xh denote the intersection of the h i in P n . To a generic point pu, xq of V, we associate the linearization

Lpu, xq

. " `Tx pu 1 X 1 q, . . . , T x pu r X r q ˘P L.

Note that x P XLpu, xq.

This section aims at three goals: describe precisely the so-called standard distribution on V (Theorem 8), give an algorithm to sample from this distribution (Algorithm 1) and define the split gamma number, a variant of the gamma number well adapted to the rigid setting.

2.1. Determinant of subspaces and incidence condition number. Let E 1 ,. . . , E r be nonzero linear subspaces of a Hermitian space V . Let π i be the orthogonal projector on E i . We define the multiprojection map projpE 1 , . . . , E r q by projpE 1 , . . . , E r q : V ÝÑ E 1 ˆ¨¨¨ˆE r v Þ ÝÑ pπ i v, . . . , π r vq.

We say that the family E 1 , . . . , E r is nondegenerate if

ř i dim E i " dim p ř i E i q,
or, equivalently, when the multiprojection map is surjective.

We define the determinant of E 1 , . . . , E r as detpE 1 , . . . , E r q

.

" ˇˇdet `projpE 1 , . . . , E r q |E1`¨¨¨`Er ˘ˇ, in the nondegenerate case and detpE 1 , . . . , E r q

.

" 0 otherwise. Note that the determinant of a map between two Hermitian spaces is well defined up to multiplication by some e iθ , so that the modulus is well defined. We also define the orthogonal determinant of E 1 , . . . , E r as det K pE 1 , . . . , E r q . " detpE K 1 , . . . , E K r q. Lastly, we define the incidence condition number of E 1 , . . . , E r as κpE 1 , . . . , E r q .

" projpE 1 , . . . , E r q :

when the multiprojection map is surjective, and κpE 1 , . . . , E r q . " 8 otherwise. With the appropriate distance, the incidence condition number is the inverse of the distance of the tuple pE 1 , . . . , E r q to the closest pF 1 , . . . , F r q such that dim p ř i F i q ă ř i dim F i (Breiding and Vannieuwenhoven 2018, Theorems 1.1 and 1.3). Lemma 1. For any subspaces E 1 , . . . , E r Ď V , κpE 1 , . . . , E r q 1, with equality if and only if E 1 , . . . , E r are orthogonal subspaces.

Proof. If the family E 1 , . . . , E r is degenerate then κpE 1 , . . . , E r q " 8 1, so we may assume it is nondegenerate. The Hermitian transpose of projpE 1 , . . . , E r q is the map sumpE 1 , . . . , E r q : E 1 ˆ¨¨¨ˆE r Ñ V defined by sumpE 1 , . . . , E r q : pu 1 , . . . , u r q Þ ÝÑ u 1 `¨¨¨`u r , so that κpE 1 , . . . , E r q " projpE 1 , . . . , E r q : " sumpE 1 , . . . , E r q : . In the nondegenerate case, sumpE 1 , . . . , E r q is injective, and sumpE 1 , . . . , E r q : is a left inverse, that is, for any pv 1 , . . . , v r q P ś i E i , pv 1 , . . . , v r q " sumpE 1 , . . . , E r q : pv 1 `¨¨¨`v r q, and, in particular, (3)

ÿ i }v i } 2 sumpE 1 , . . . , E r q : 2 › › › › ÿ i v i › › › › 2 .
Choosing v j ‰ 0 for some j and v i " 0 for i ‰ j shows that sumpE 1 , . . . , E r q :

1. If sumpE 1 , . . . , E r q : " 1, we have by (3), for any v i P E i and v j P E j , i ‰ j,

}v i } 2 `}v j } 2 }v i `vj } 2 " }v i } 2 `}v j } 2 `2 xv i , v j y,
which implies that the real part of xv i , v j y is nonnegative. Since it holds for ´vi and v j too, it follows that E i and E j are orthogonal. Conversely, if E 1 , . . . , E r are orthogonal, then the map sumpE 1 , . . . , E r q is an isometric embedding, and thus κpE 1 , . . . , E r q " 1.

Lemma 2. Let P . " π 1 `¨¨¨`π r , it is a self-adjoint endomorphism of the subspace ř i E i Ď V . In the nondegenerate case, detpE 1 , . . . , E r q 2 " det P .

Proof. Since P " sumpE 1 , . . . , E r q ¨projpE 1 , . . . , E r q |E1`¨¨¨`Er and since the map sumpE 1 , . . . , E r q is the Hermitian transpose of projpE 1 , . . . , E r q |E1`¨¨¨`Er , it follows the definition of detpE 1 , . . . , E r q that det P " detpE 1 , . . . , E r q 2 . We can check similarly that κpE 1 , . . . , E r q 2 " P ´1 , giving another interpretation of κ (which will not be used here).

Lemma 3. For any subspaces E 1 , . . . , E r Ď V ,

det K pE 1 , . . . , E r q " det K pE 1 , E 2 q det K pE 1 X E 2 , E 3 , . . . , E r q.
Proof. This follows from the factorization

projpE K 1 , . . . , E K r q ř i E K i " ´projpE K 1 , E K 2 q |E K 1 `EK 2 ˆid E K 3 ˆ¨¨¨ˆid E K r ¯projpE K 1 `EK 2 , E K 3 , . . . , E K r q | ř i E K i . 2.2.
Reminders on Riemannian geometry. We will work mainly with two Riemannian manifolds: P n , the n-dimensional complex projective space endowed with the Fubini-Study metric, and U pn `1q, the group of pn `1q ˆpn `1q unitary matrices. Concerning the latter, we endow C pn`1qˆpn`1q with the norm (4) }A} u

.

" 1 ? 2 }A} Frob . " b 1 2
TrpAA ˚q, A P C pn`1qˆpn`1q , where A ˚denote the conjugate transpose, and we choose on U pn`1q the Riemannian metric induced from the embedding of U pn `1q in C pn`1qˆpn`1q . This metric is invariant under left and right multiplication in U pn `1q.

Let X and Y be Riemannian manifolds and let f : X Ñ Y be an infinitely differentiable surjective map. For any x P X, we define the normal Jacobian of f at x as

NJ x f . " a det pd x f ¨dx f ˚q.
When d x f is bijective, this is the absolute value of the usual Jacobian. A fundamental result is the coarea formula for Riemannian manifolds (Federer 1959, Theorem 3.1;Howard 1993, Appendix): for any integrable map Θ :

X Ñ R, (5) ż
X dx ΘpxqNJ x f " ż Y dy ż f ´1pyq dx Θpxq.
The special case of Riemannian submersions is important. We say that f is a Riemannian submersion if for any x P X, the derivative d x f induces an isometry from pker d x f q K to T f pxq Y . In that case, we easily check that f is Lipschitzcontinuous with constant 1 and that NJ x f " 1 for all x P X. Note also that for any submanifold Z of Y , if f is a Riemannian submersion then so is f |f ´1pZq . The scaling in the definition of } ´}u is chosen to have the following result.

Lemma 4. For any p P P n , the map ϕ : u P U pn `1q Þ Ñ up P P n is a Riemannian submersion. In particular, for any variety X Ď P n , and any integrable map Θ :

ϕ ´1X Ñ R, ż ϕ ´1 X du Θpuq " ż X dx ż up"x
du Θpuq, where ş up"x du denotes the integration over the variety ϕ ´1pxq. Proof. Thanks to the invariance of the Riemannian metric of U pn `1q under right multiplication, it is enough to check that the defining property of Riemannian submersion holds at id, the identity matrix. With a suitable choice of coordinates, we may also assume that p " r1 : 0 : ¨¨¨: 0s. The tangent space of P n at p is canonically identified with tpu K , that is t0u ˆCn .

The tangent space T id U pn `1q of U pn `1q at id is the space of skew-Hermitian matrices, and for any u P T id U pn `1q, d id ϕp 9

uq " 9 up. Therefore,

pker d id ϕq K " `0 v v 0 ˘ˇv P C n ( ,
and since › › `0 v v 0
˘› › u " }v}, the map 9 u P pker d id ϕq K Ñ 9 up is clearly an isometry. The second claim follows from coarea formula (5), noting that the restriction of π to π ´1X is again a Riemannian submersion.

2.3. Basic integral formulas. For our problem, the manifold V has a natural distribution, the standard distribution, denoted ρ std , defined as follows. Let u P U and x P XuX be uniformly distributed, so that the random variable pu, xq belongs to V and let ρ std be its probability distribution. The uniform distribution is defined on U by the Riemannian metric; and on XuX by the Riemannian metric on the regular locus. This section aims at describing the conditional probability distribution of pu, xq, given x and the linearization Lpu, xq P L.

For any x P P n , y P X and h P L, we define

L x . " th P L | x P Xhu , U x . " tu P U | x P XuX u U x,y . " tu P U x | uy " px, . . . , xqu , U x,y,h . " tu P U x,y | Lpu, xq " hu .
Lemma 5. For any two submanifolds X and Y of P n , with codim X `codim Y n, and for any integrable function Θ : U pn `1q ˆPn Ñ R, ż

U pn`1q du ż XXuY dz Θpu, zq " ż X dx ż Y dy ż uy"x du Θpu, xq det K pT x X, T x uY q,
(where ş uy"x du denotes the integration over the variety of all u P U pn `1q such that uy " x, as in Lemma 4).

Proof. It is a corollary of the "basic integral formula" of Howard (1993, §2.7). Let p P P n be some point and let ϕ be the Riemannian submersion u P U pn `1q Þ Ñ up P P n (Lemma 4). Let M " ϕ ´1X and N " ϕ ´1Y . Howard's basic integral formula asserts that (6)

ż U pn`1q du ż M XuN dv Θpu, ϕvq " ż M dv ż N dw Θpvw ´1, ϕvq det K pv ´1T v M, w ´1T w N q,
where v ´1T v M and w ´1T w N are subspaces of T id U pn`1q. (The equality of our det K with Howard's σ is given by Lemma 2.) On the one hand, by Lemma 4, we obtain the following expression for the left-hand side of ( 6 where, for the last equality, we remark that tv P U pn `1q | vp " zu is isometric, by some left multiplication, to U p1q ˆU pnq, the stabilizer of a point in P n . This is the left-hand side of the claimed equality. On the other hand, regarding the right-hand side of (6), we check easily that

det K pv ´1T v M, w ´1T w N q " det K pv ´1T vp X, w ´1T wp Y q " det K `Tvp X, T vp pvw ´1Y q ȃnd therefore (using Lemma 4 again) ż M dv ż N dw Θpvw ´1, ϕvq det K pv ´1T v M, w ´1T w N q " ż X dx ż vp"x dv ż Y dy ż wp"y dw Θpvw ´1, xq det K pT x X, T x vw ´1Y q " volpU p1q ˆU pnqq ż X dx ż Y dy ż uy"x du Θpu, xq det K pT x X, T x uY q,
where the last equality is given by the change of variables v " uw. This gives the right-hand side of the claim.

In our setting where we consider r varieties X 1 , . . . , X r , we can give the following "basic integral formula". It has been proved very similarly in the real case by Bürgisser and Lerario (2018, §7.5). du Θpu, xq det K pT x P n , T x uX 1 q, by Lemma 5 with X " P n and Y " X 1 . Note that det K pT x P n , T x uX 1 q " det K pT x uX 1 q " 1, and it follows that ż This concludes the base case since det K pLpu, xqq is identically 1 when r " 1.

Proposition 6. For any measurable function

Θ : V Ñ r0, 8q ż U du ż XuX dx Θpu, xq " ż P n dx ż Ux du Θpu, xq det K pLpu, xqq.
Assume that the property holds for r´1 subvarieties X 1 , . . . , X r´1 , for some r 1, and let U 1 , X 1 , etc. denote the analogues of U, X , etc. for the varieties X 1 , . . . , X r´1 . From the decomposition U " U 1 ˆU pn `1q, we obtain by Lemma 5 ż

U du ż XuX dx Θpu, xq " ż U 1 du 1 ż U pn`1q du r ż pXu 1 X 1 qXurXr dx Θpu 1 , u r , xq " ż U 1 du 1 ż Xu 1 X 1 dx ż Xr dy ż ury"x du r Θpu 1 , u r , xq det K pT x pXu 1 X 1 q, T x u r X r q " ż P n dx ż U 1 x du 1 ż Xr dy ż ury"x du r Θpu 1 , u r , xq det K pT x pXu 1 X 1 q, T x u r X r q det K pLpu 1 , xqq,
using the induction hypothesis for the last equation. Lemma 3 shows that

det K pT x pXu 1 X 1 q, T x u r X r q det K pLpu 1 , xqq " det K pLpu, xqq.
Moreover, by Lemma 4 (applied as in the base case), ż

Xr dy ż ury"x du r hpu r q " ż xPurXr du r hpu r q, for any integrable function h : U pn `1q Ñ R. This implies that ż

U du ż XuX dx Θpu, xq " ż P n dx ż U 1 x du 1 ż xPurXr du r Θpu 1 , u r , xq det K x pLpu, xqq.
To conclude, we remark that

U x " U 1 x ˆtu r P U pn `1q | x P u r X r u.
If we apply the statement above to the case where the varieties X i are projective subspaces, that is X i P Gpdim X i q, we obtain the following corollary. Proof. Let us assume that each X i is a projective subspace of P n . The map

u P U Þ Ñ uX " pu 1 X 1 , . . . , u r X r q P L, is a Riemannian submersion, thus ż U du ż XuX dx ΘpuX , xq " ż L dh ż uX "h du ż Xh dx Θph, xq " volpStab U X q ż L dh ż Xh dx Θph, xq,
where Stab U X " tu P U | uX " X u, because all the subsets tu P U | uX " hu are isometric, by some left multiplication, to Stab U X . Similarly, ż

P n dx ż Ux du ΘpuX , xq det K pLpu, xqq " volpStab U X q ż P n dx ż Lx dh Θph, xq det K phq.
This reduces the claim to Proposition 6.

We now have all we need to prove the main result of this section.

Theorem 8. For any measurable function Θ :

V Ñ r0, 8q, ż U du ż XuX dx Θpu, xq " ż L dh ż X dy ż Xh dx ż U x,y,h du Θpu, xq.
In other words, if pu, xq P V is a ρ std -distributed random variable distributed, then:

(i) the random variable Lpu, xq is uniformly distributed in L;

(ii) the random variable y

.

" pu ´1 1 x, . . . , u ´1 r xq is uniformly distributed in X and independent from Lpu, xq; (iii) conditionally on Lpu, xq, the random variable x is uniformly distributed in XLpu, xq; (iv) conditionally on Lpu, xq, x and y, the random variable u is uniformly distributed in U x,y,Lpu,xq .

Algorithm 1. Sampling of a unitary solution variety Input. Varieties X1, . . . , Xr Ă P n with ř i codim Xi n. Output. pu, ζq P V, where V " tpu1, . . . , ur, xq P U ˆPn | x P XiuiXiu. Postcondition. pu, ζq " ρ std (Theorem 8) function Sample(X 1 , . . . , X r ) Sample h 1 P Gpdim X i q, . . . , h r P Gpdim X r q, uniformly and independently. Sample ζ P h 1 X ¨¨¨X h r Ă P n uniformly. Sample y 1 P X 1 , . . . , y r P X r uniformly and independently. Sample u 1 , . . . , u r P U pn`1q, such that u i y i " ζ and u i pT yi X i q " h i , uniformly and independently.

return pu 1 , . . . , u r q P U and ζ P P n . end function

Proof. By Corollary 7, ż L dh ż Xh dx ż X dy ż U x,y,h dv Θpu, xq " ż P n dx ż Lx dh det K phq ż X dy ż U x,y,h dv Θpu, xq " ż P n dx ż X dy ż Lx dh ż U x,y,h dv Θpu, xq det K pLpu, xqq.
Moreover, the map To conclude, we apply Proposition 6.

u P U x,y Þ Ñ Lpu, xq P L x is a Riemannian submersion, thus ż Lx dh ż U x,y,h dv Θpu, xq det K pLpu, xqq " ż Ux,y dv Θpu, xq det K pLpu, xqq. The map u P U x Þ Ñ pu ´1 1 x, . . . , u ´1 m xq P X is
Corollary 9. Let X be subvariety of P n and L P Gpcodim Xq be a uniformly distributed random projective subspace. Let ζ P X X L be a uniformly distributed random variable. Then ζ is uniformly distributed in X.

Proof. Let L 0 P Gpcodim Xq and let v P U pn `1q a be uniformly distributed random variable. The random subspace vL 0 is uniformly distributed in Gpcodim Xq: indeed, the probability distribution of vL 0 is invariant under the action of U pn `1q and, by transitivity of the action of U pn `1q on Gpcodim Xq, there is a unique invariant probability distribution on Gpcodim Xq. So we may assume that L " vL 0 . Let u P U pn `1q be an independent uniformly distributed random variable. The random variables u and v 1 .

" uv are independent and uniformly distributed, because the diffeomorphism pu, vq P U pn `1q ˆU pn `1q Þ Ñ pu, uvq P U pn `1q ˆU pn `1q has constant Jacobian, and so preserves the uniform distribution. Moreover, uζ is uniformly distributed in uX X v 1 L 0 . Therefore, the pair ppu, v 1 q, uζq is ρ stddistributed in the solution variety associated to X and L 0 . By Theorem 8(ii), u ´1puζ q is uniformly distributed in X, which is the claim.

2.4. Sampling the solution variety. Based on Theorem 8, Algorithm 1 samples a ρ std -distributed random pu, ζq P V. We explain briefly how to perform the four steps of the algorithm.

For each 1 i r, we sample independently linear forms λ i,1 , . . . , λ i,codim Xi P pC n`1 q ˚with a standard normal distribution. We define h i as the zero locus of λ i,1 , . . . , λ i,codim Xi . Next, we compute a unitary basis of the linear subspace h 1 X ¨¨¨X h n and use it to sample ζ P Pph 1 X ¨¨¨X h n q with a uniform distribution.

To sample uniformly a point y i P X i , we consider a random uniformly distributed subspace L i P Gpcodim X i q. Almost surely, the intersection X i X L i is finite and we sample uniformly a point y i in it. By Corollary 9, y i is uniformly distributed in X i . Since L i is a projective subpace, the computation of X i X L i requires a polynomial system solving in codim X i `1 homogeneous variables. In the typical case where X i is a hypersurface defined by a polynomial f i and L i is a projective line, this amounts to compute the zeros rx : ys P P 1 of the homogeneous equation f i pxp `yqq " 0, for some basis tp, qu of L i .

Once we get the y i , we compute, for each 1 i r, some v i P U pn `1q which maps y i to ζ and T yi X i to h i and we sample uniformly a w i in the subgroup of all w P U pn `1q such that wζ " ζ and wL i " L i . This subgroup is isometrically isomorphic to U p1q ˆU pdim X i q ˆU pcodim X i q. We can sample uniformly in a unitary group U pkq by considering the Q factor of the QR decomposition of a random k ˆk Gaussian matrix. And then, we define u i .

" w i v i . When X 1 , . . . , X r are all hypersurfaces, we have proved the following proposition.

Proposition 10. If X 1 , . . . , X r are all hypersurfaces, Algorithm 1 samples a ρ stddistributed point in the solution variety V with r times root-finding of bivariate homogeneous polynomials of respective degrees deg X 1 ,. . . , deg X r ; -Opn 3 q samplings of the standard normal distribution on R; and -Opn 4 q arithmetic operations.

2.5. The split gamma number. In the classical theory, the condition number µ plays two roles: first, by definition, it bounds the variation of a zero after a pertubation of the system; second, it is an upper bound for Smale's gamma number with some regularity properties (the Lipschitz properties). Each role is reflected by a factor µ in the µ 2 estimate.

In the rigid setting, the two roles are played by different numbers: the variation of a zero is bounded by the incidence condition number κ and the upper bound for γ that we use is the split gamma number γ. This will lead to a κγ estimate for the complexity of numerical continuation in the rigid setting. In this section, we introduce the split gamma number and we start with some reminders about the gamma number.

Let F " pf 1 , . . . , f s q P Hrss be a homogeneous polynomial system that we regard as a polynomial map

C n`1 Ñ C s . Let d i . " deg f i and D . " max i d i .
When s " n, the polynomial system F has generically finitely many zeros and our primary goal is to compute them numerically and approximately. A fundamental tool is Newton's operator. We use here the projective version introduced by [START_REF] Shub | On the Distance to the Zero Set of a Homogeneous Polynomial[END_REF]. For z P P n , projective class of some z P C n`1 , we define

(7) N F pzq . " " z ´dz F | ´1 z K pF pzqq ‰ P P n ,
where z K is the orthogonal complement of z in C n`1 . The definition does not depend on the choice of z. Given a zero ζ P P n of F , we say that z P P n approximates ζ as a zero of F , or that z is an approximate zero of F with associated zero ζ, if for any k 0,

d P `N k F pzq, ζ ˘ 2 1´2 k d P pz, ζq,
where d P is the geodesic distance in P n , see §1.3. The main result of the gamma theory is a sufficient condition for a point to approximate a zero. For a polynomial system F , in the general case r n, we will use the following definition (Shub and Smale 1996;Dedieu 2006, §4) for the gamma number of F at z P P n :

(8) γpF, zq . " # sup k 2 1 k! d z F : ¨dk z F 1 k´1 if d z F is surjective, 8 otherwise.
(The definition does not depend on the choice of a unit representative z of z.) When s " n, the pseudo-inverse d z F : is often replaced by d z F | ´1 z K , as in Newton's iteration (e.g. [START_REF] Bürgisser | On a Problem Posed by Steve Smale[END_REF]Shub and Smale 1994). If z is a zero of F , both definitions coincide, so the gamma theorem (Theorem 12) is equally true for both variants. When F " pf q is a single equation, that is s " 1, it is useful to remark that d z f is a linear form and so d z f : is simply }d z f } ´1π, where π is an isometric embedding of C in C n`1 . This gives γpf, zq the following form:

(9) γpf, zq " sup k 2 `1 k! }d z f } ´1~d k z f ~˘1 k´1 .
The following lower bound will be occasionally useful.

Lemma 11. For any z P P n , γpF, zq D´1 2 .

Proof. We may assume that d z F is surjective, otherwise the bound is trivial. Let d i .

" deg f i . Using the homogeneity, for any u P C n`1 , (10)

d 2 z F pz, uq " ˜d1´1 . . . dm´1 ¸dz F puq.
We fix some 1 i r and consider u

.

" d z F : pe i q, where e i .

" p0, . . . , 1, . . . , 0q P C r with a single one at the ith position. Becase d z F is surjective, d z F pd z F : pe i qq " e i , and by (10), we have d 2 z F pz, uq " pd i ´1qe i and then d z F : pd 2 z F pz, uqq " pd i ´1qu. This implies that d z F : d 2 z F d i ´1, for any 1 i m, and the claim follows.

We now state the main result of the gamma theory in the projective setting, primarily due to Shub and Smale (1993a).

Theorem 12 (Shub, Smale). Let F P Hrns be a homogeneous polynomial system. For any zero ζ P P n of F and any z P P n , if d P pz, ζqγpF, ζq 1 6 then z approximates ζ as a zero of F .

Proof. This is (Bürgisser and Cucker 2013, Theorem 16.38) with r " 0.981 (and we use that γpF, ζq 1 2 when D 2, Lemma 11).

Let F 1 P Hrs 1 s, . . . , F r P Hrs r s be homogeneous polynomial systems, with s 1 sr n. Based on the incidence condition number of linear subspaces ( §2.1), we define the incidence condition number of F 1 , . . . , F r at a point x P P n by ( 11)

κpF 1 , . . . , F r ; xq . " κ `kerpd x F 1 q K , . . . , kerpd x F r q K ˘.
Since the orthogonal projector on kerpd

x F i q K is d x F : i ˝dx F i , we can write (12) κpF 1 , . . . , F r ; xq " ¨dx F : 1 ˝dx F 1 . . . d x F : r ˝dx F r ‹ ' : .
The split gamma number of F 1 , . . . , F r at a point x P P n is defined by

(13) γpF 1 , . . . , F r ; xq . " κpF 1 , . . . , F r ; xq `γpF 1 , xq 2 `¨¨¨`γpF r , xq 2 ˘1 2 .
The split gamma number separates the contribution of the γ number of each block of equations from the more geometric information contained in κ: for x P X i V pF i q, the κ factor only depends on the relative position of the tangent spaces of the varieties V pF 1 q, . . . , V pF r q at x; while the γ factor quantifies how much each V pF i q deviates from its tangent space at x. Note that when r " 1, then γpF, xq " γpF, xq.

Theorem 13. Let G .

" pF 1 , . . . , F r q P Hrs 1 `¨¨¨`s r s denote the concatenation of the systems. For any x P P n , γpG, xq γpF 1 , . . . , F r ; xq r κpF 1 , . . . , F r ; xqγpG, xq.

Proof. It is easy to see that γpF 1 , . . . , F r ; xq is finite if and only if γpG, xq is. Thus, we may assume that dG and the dF i are surjective (we drop the index x in d x ). We begin with the first inequality. Let K i . " ker d x F i and P . " projpK K 1 , . . . , K K r q, so that κpF 1 , . . . , F r ; xq " P : . We first prove that for any k 2 and any y " py 1 , . . . , y k q P `Cn`1 ˘k, (14) dG : ¨dk Gpyq " P : ´dF :

1 ¨dk F 1 pyq, . . . , dF : r ¨dk F r pyq ¯.
It is clear that

d k Gpyq " `dk F 1 pyq, . . . , d k F r pyq ˘P C s1 ˆ¨¨¨ˆC sr . Let v i .
" d k F i pyq and v

.

" pv 1 , . . . , v r q. Because dG is surjective, we have dG dG : pvq " v and, equivalently, dF i ¨dG : pvq " v i . Therefore dF :

i ¨dF i ¨dG : v " dF : i v i . But dF : i ¨dF i is simply the orthogonal projection on K K i . This gives P ¨dG : ¨dk Gpyq " ´dF :

1 v 1 , . . . , dF : r v r ¯, and since the image of dG : is orthogonal to the kernel of P we have P : ¨P ¨dG : " dG : . This proves (14).

As a consequence, for any k 2,

1 k! dG : ¨dk G 1 k´1 P : 1 k´1 ˆÿ i 1 k! dF : i ¨dk F i 2 ˙1 2k´2 P : 1 k´1 ˆÿ i γpF i , xq 2k´2 ˙1 2k´2 P : ˆÿ i γpF i , xq 2
˙1 2 using P : 1 (Lemma 1) and the monotonicity of p-norms with respect to p. By definition, κpF 1 , . . . , F r ; xq " P : , so we obtain the first inequality.

Concerning the second inequality, Equation ( 14) implies that

1 k! dF : i ¨dk F i ~P ~ 1 k! dG : ¨dk G ~P ~γpG, xq k´1 .
We note that ~P ~ r 1 2 (as the direct sum of r orthogonal projectors with orthogonal images) and therefore γpF i , xq r 1 2 γpG, xq. Hence

˜r ÿ i"1 γpF i , xq 2 ¸1 2 `r ¨rγpG, xq 2 ˘1 2 rγpG, xq,
and the second inequality follows.

Numerical continuation

In this part, we consider a more specific setting than in the previous one. We are given a polynomial system F " pf 1 , . . . , f n q P Hrns, with nonzero squarefree polynomials f 1 , . . . , f n , and a u P U " U pn `1q n , and we look for a zero of the polynomial system u ¨F .

" pf 1 ˝u´1 1 , . . . , f n ˝u´1 n q. We will perform the average analyses in the case where u is uniformly distributed and F is fixed. To this end, we consider the rigid solution variety V relative to the projective hypersurfaces V pf 1 q, . . . , V pf n q. In concrete terms, we have r " n and

V " pu, xq P U ˆPn ˇˇf 1 pu ´1 1 xq " ¨¨¨" f n pu ´1 n xq " 0 ( .
As the Grassmannian of hyperplanes Gpn ´1q is isomorphic to P n , the manifold L is just pP n q n and Lpu, xq is the n-uple Lpu, xq " `rd x pf 1 ˝u´1 1 qs, . . . , rd x pf n ˝u´1 n qs ˘.

In particular, we can define Lpu, xq generically on U ˆPn , not only on V. Lpu, xq is not defined when one of the d x pf i ˝u´1 i q is zero. When it is defined, we can identify Lpu, xq with one of its preimages under the projection map SpC n`1 q n Ñ pP n q n , that is a n ˆpn `1q matrix with unit rows. Namely, (15)

Lpu, xq " diag `}d x pf 1 ˝u´1 1 q} ´1, . . . , }d x pf n ˝u´1 n q} ´1˘¨d

x pu ¨F q . Under this identification, we check that Lpu, xq is the matrix of the map proj `kerpd x pf 1 ˝u´1 1 q K , . . . , kerpd x pf n ˝u´1 n q K ˘, and therefore, by definition of κ ( 11 Section 3.1 studies the possibility of continuing a zero of a polynomial system u¨F when u varies continuously along a path. Section 3.2 introduces the condition number associated to the solution variety V: it quantifies the extend to which a zero of a polynomial system u ¨F is affected by a pertubation of u. Section 3.3 proves some Lipschitz-continuity properties for the condition number and γ. They are technical but crucial for designing the continuation algorithms, what does Section 3.4. Section 3.5 provides a bound on the average number of continuation steps required to compute a zero of a random system u ¨F in the rigid setting. Theorem 25 is the main outcome of this part.

3.1. Path lifting. Let Σ Ă V denote the singular locus:

Σ . " tpu, xq P V | d x pu ¨F q is not surjectiveu .
In other words, pu, xq P Σ if and only if u ¨F has a singular zero at x. Let π : V Ñ U be the projection πpu, xq " u and Σ 1 .

" πpΣq. For any u P UzΣ 1 , the polynomial system u ¨F has finitely many roots that vary continuously with u. Given a continous path pw t q 0 t 1 in UzΣ 1 and a zero ζ of w 0 ¨F , there is a unique continuous lifting pw t , η t q P V such that η 0 " ζ. In contrast with the classical setting, the parameter space U is not a complex variety, so it is not obvious anymore that a generic path in U does not meet Σ 1 and that this lifting is possible. This section aims at proving this fact.

Lemma 14. The real codimension of Σ 1 in U is at least 2.

Proof. We first observe that the map ϕ : U ˆPn Ñ pP n q n defined by pu, xq Þ Ñ pu ´1 1 x, . . . , u ´1 n xq is a proper submersion, and thus a locally trivial fibration, by Ehresmann's fibration theorem. The fibers have dimension

dim R ϕ ´1p˚q " dim R pU ˆPn q ´n dim R P n " dim R U ´pn ´1q dim R P n .
The solution variety V is ϕ ´1pX 1 ˆ¨¨¨ˆX n q, and so the restriction ϕ |V induces a locally trivial fibration V Ñ X 1 ˆ¨¨¨ˆX n . In particular

dim R V " n ÿ i"1 dim R X i `dim R ϕ ´1p˚q " npdim R P n ´2q `dim R U ´pn ´1q dim R P n " dim R U.
Let Σ 0 Ď Σ be the subset of all pu, xq such that x is a singular zero of one of the f i ˝u´1 i (that is a singular point of u i X i ). By definition,

Σ 0 " ϕ ´1 ˜n ď i"1 X 1 ˆ¨¨¨ˆSing X i ˆ¨¨¨ˆX n ¸,
so Σ 0 is the preimage by a locally trivial fibration of a complex subvariety of real codimension at least 2. Thus Σ 0 has codimension at least 2 in V.

Let Σ 1 Ď Σ be the subset of all pu, xq such that all u i X i are smooth at x but d x pu ¨F q is not surjective, so that Σ " Σ 0 Y Σ 1 . To compute the dimension of Σ 1 , we observe that the map

ψ : VzΣ 0 Ñ X reg 1 ˆ¨¨¨ˆX reg n ˆL pu, xq Þ Ñ `u´1 1 x, . . . , u ´1 n x, Lpu, xq
ȋs a proper submersion and thus, by Ehresmann's fibration theorem, a locally trivial fibration. Further, Σ 1 is the preimage of the complex subvariety of all py 1 , . . . , y n , hq such that the intersection of the hyperplanes h 1 , . . . , h n Ă C n`1 has complex dimension 2. So Σ 1 has real codimension at least 2 in V, and so does Σ.

Since Σ 1 is the image of Σ by the projection map π :

V Ñ U, dim R Σ 1 dim R Σ, and since dim R U " dim R V, it follows that Σ 1 has codimension at least 2 in U.
Proposition 15. For almost all u, v P U, the shortest path in U from u to v does not intersect Σ 1 .

Proof. The subset S Ă U ˆU of all ill-posed pairs pu, vq that do not satisfy the claim is parametrized by the data of a w P Σ 1 , a unit vector 9 γ in T w U and two real numbers t and s such that u " γptq and v " γpsq, where γ : R Ñ U is the unique geodesic with γp0q " w and γ 1 p0q " 9 γ. Therefore, by Lemma 14,

dim R S dim R Σ 1 `pdim R U ´1q `2 dim R U 2 ´1,
and S has real codimension at least 1 in U ˆU, which proves the claim.

The statement still holds for more general paths as long as they are unitary invariant. Let P : U ˆU ˆr0, 1s Ñ U be a map such that for any u, v, w P U and t P r0, 1s, P pwu, wv, tq " wP pu, v, tq. Let S Ă U ˆU be the set of all pu, vq such that P pu, v, tq P Σ 1 for some t P r0, 1s. We check easily that S " `wP p1 U , v, tq ´1, wP p1 U , v, tq ´1v ˘ˇt P r0, 1s, w P Σ 1 and v P U ( , The expected value of the incidence condition number κ is very tame and depends on the ambient dimension n only. This is one of the key points that strongly contrasts with the classical setting.

so if P is regular enough to allow dimension counting, then dim R S 1 `dim R Σ 1 dim R U,
ÿ i }d x f i } ´2|d x f i p 9 u i xq| 2 ÿ i } 9 u i } 2 u , by (19)
Proposition 17. If pu, ζq P V is ρ std -distributed then, E " κpu, ζq 2 ‰ 6n 2 .
Proof. Let M be a random n ˆpn `1q matrix whose rows are independent and uniformly distributed in SpC n`1 q. It follows from ( 16) and Theorem 8(i) that κpu, ζq has the same probability distribution as ~M : ~.

Let T be an n ˆn diagonal random matrix whose coefficients are independent χ-distributed random variables with 2n `2 degrees of freedom, so that T M is a random Gaussian matrix (the coefficients are independent standard normal complex numbers). Obviously, M : " pT M q : ¨T and therefore ~M : ~ ~pT M q : ~~T ~. Hölder's inequality with conjugate exponents n 1 .

" 1 `1 n`1 and n `2, gives

(20) E " ~M : ~2‰ E " ~pT M q : ~2n 1 ı 1 n 1 E " ~T ~2n`4 ı 1 n`2 .
We now give upper bounds for both factors in the right-hand side. According to Beltrán and Pardo (2011, Theorem 20), whose result is derived from the work of Edelman ( 1989), ( 21)

E " ~pT M q : ~2n 1 ı " 2 ´n1 n ÿ k"1 ˆn `1 k `1˙Γ pk ´n1 `1q Γpkq n ´k`n 1 ´1.
We proceed as in (Lairez 2017, Theorem 10) and deduce that

(22) E " ~pT M q : ~2n 1 ı 1 n 1 ˆ5 4p2 ´n1 q ˙1 n 1 n 2 n.
Concerning the second factor, ~T ~2 is the maximum of n χ 2 -distributed random variables with 2n `2 degrees of freedom, say Z 1 , . . . , Z n , hence

E " ~T ~2n`4 ı n ÿ i"1
ErZ n`2 i s " 2 n`2 p2n `2q! pn ´1q! .

Therefore,

E " ~M : ~2‰ n ˆ2n`2 p2n `2q! pn ´1q! ˙1 n`2 6n 2 ,
after a few numerical computations.

3.3. Lipschitz properties. We aim at bounding the variation of the numbers κ and γ on the Riemannian manifold U ˆPn . In particular, we will prove that 1{γ is Lipschitz-continuous. Traditionally, such results bound directly the value at some point x with respect to the value at some other point y and the distance from x to y. For example [START_REF] Dedieu | Points Fixes[END_REF], Lemme 131), for any x, y P P n , (23) γpF, yq γpF, xq q pd P px, yqγpF, xqq , where qpuq

. " 1 p1´uqp1´4u`2u 2 q " 1`5u`Opu 2 q, given that d P px, yqγpF, xq 1´1{ ? 2. As much as possible, I tried to express this kind of inequalities as a bound on the derivative of the function under consideration. To first order, this is equivalent.

Proposition 18. Let F P Hrrs and γ F : x P P n Þ Ñ γpF, xq. For any x P P n , we have }d x γ F } 5γ 2 F .

Note that γ F may not be differentiable everywhere, so the inequality }d x γ F } 5γ F pxq 2 really means that To prove the first inequality, we first remark that 1{κpu, xq is a Lipschitzcontinuous function of Lpu, xq with constant 1. Indeed, 1{κpu, xq is the least singular value of Lpu, xq as a matrix, see Equation ( 16), and the Eckart-Young theorem expresses this number as the distance to the set of singular matrices, which is a Lipschitz continuous function with constant 1. Moreover dκ " ´κ2 d 1 κ , so it is enough to prove that ~dL~is bounded by 1 `3 γ κ . Let L i pu i , zq P P n be the ith component of Lpu, zq, that is the projective class of the linear form d x pu i ¨fi q. The tangent space of P n at L i pu i , zq is isometrically identified with the quotient C n`1 {C ¨Li pu i , zq. Denoting h i .

" u i ¨fi , we check that, at a point pu, xq,

dL i p0, 9 xq " 1 }d x h i } d 2 x h i p 9 xq mod L i pu i , zq,
and in particular, }dL i p0, 9 xq} 2γph i , xq} 9 x} for any 9

x P T x P n . Besides, L i pu i , u i xq " L i pid, xq ˝ui , which is a 1-Lipschitz continuous function of u i (Lemma 4 applied to the dual projective space). This proves that }dL i p 9 u i , 9 u i xq} } 9 u i } u . Therefore,

}dL i p 9 u i , 9 xq} }dL i p 9 u i , 9 u i xq} `}dL i p0, 9 x ´9 u i xq} } 9 u i } u `2γph i , xq p} 9 x} `} 9 u i } u q } 9 u i } u `2? 2γph i , xq `} 9 u} 2 u `} 9 x} 2 ˘1 2 ,
and then, by the triangle inequality,

}dLp 9 u, 9 xq} } 9 u} u `2? 2 ˆÿ i γph i , xq 2 ˙1 2 `} 9 u} 2 u `} 9 x} 2 ˘1 2 ˆ1 `3 γpu; xq κpu, xq ˙`} 9 u} 2 u `} 9 x} 2 ˘1 2 ,
which concludes the proof.

We now derive a bound for }dγ}.

Lemma 20. For any homonegeneous polynomial f : C n`1 Ñ C the map pu, xq P U pn `1q ˆPn Þ ÝÑ 1 γpu ¨f, xq is Lipschitz continuous with constant at most 5 ? 2.

Proof. The γ number is invariant under unitary transformations, that is γpu f, xq " γpf, u ˚xq. Moreover, the map pu, xq P U pn `1q ˆPn Þ Ñ u ˚x P P n is 1-Lipschitz continuous with respect to u (Lemma 4) and to x, thus it is ? 2-Lipschitz continuous on U pn `1q ˆPn . Since 1{γpf, xq is 5-Lipschitz continous with respect to x (Proposition 18), the map 1{γpf, u ˚xq is 5 ? 2-Lipschitz continuous on U pn `1q ˆPn .

Lemma 21. On U ˆPn , }dγ} 13 γ2 . Equivalently, 1{γ is 13-Lipschitz continuous.

Proof. We may assume that D 2, otherwise γ is identically 0. 3.4. Numerical continuation along rigid paths. We describe a continuation algorithm in the rigid solution variety and bound its complexity in terms of the integral of κγ along the continuation path. It is the analogue of the µ 2 estimate of the classical theory, see §1.1. The approach proposed here differs from the usual treatment only in a more systematic use of derivatives. We assume D 2 as otherwise there is only a linear system of equations to solve.

As we will see in §4, it may be valuable not to compute γ but rather an easier to compute upper bound. That is why the algorithm is described in terms of a function g : U ˆPn Ñ p0, 8s that can be chosen freely, as long as:

(H1) γ g, on U ˆPn ; (H2) 1 g is C-Lipschitz continuous, for some C 10. The following proposition describes one continuation step. Observe that the conclusion (ii) concerning the triple pv, ζ 1 , z 1 q is similar to the hypothesis (a) concerning pu, ζ, zq, so that we can chain the continuation steps. The geodesic distance in U is denoted d U .

Proposition 22. Let u, v P U, let ζ be a zero of the polynomial system u ¨F , let z P P n and let z 1 .

" N v¨F pzq. For any positive real number A 1 4C , if (a) d P pz, ζqgpu, ζq A, and (b) d U pu, vqκpu, zqgpu, zq 1 4 A, then there exists a unique zero ζ 1 of v ¨F such that (i) z is an approximate zero of v ¨F with associated zero ζ 1 , and (ii)

d P pz 1 , ζ 1 qgpv, ζ 1 q A. Proof. It suffices to construct a zero ζ 1 of v ¨F such that d P pz, ζ 1 qgpv, ζ 1 q
2A. Indeed, since 2A 1 6 and γ γ g, it would imply by Theorem 12 that: (i) z is an approximate zero of v ¨F ; and (ii) that

d P pz 1 , ζ 1 qgpv, ζ 1 q 1 2 d P pz, ζ 1 qgpv, ζ 1 q A.
Consider a geodesic t P r0, 8q Þ Ñ v t P U such that } 9 v t } " 1, v 0 " u and v d U pu,vq " v. We may assume that κpu, ζq ă 8, otherwise u " v, by Hypothesis (b), and there is nothing to prove. So pu, ζq is not in the singular locus Σ and for t small enough, there is a unique lift pv t , η t q in VzΣ, see §3.1. Let r0, τ q, with 0 ă τ 8, be the maximal interval of definition of η t .

For t P r0, τ q, let p t .

" pv t , η t q and let δ t .

" It follows, after integration, that 1 κtgt 1 κ0g0 ´3Ct, and thus (26) κ t g t κ 0 g 0 1 ´3Ctκ 0 g 0 , for any t P r0, τ q such that 1 ´3Ctκ 0 g 0 ą 0.

A first consequence of ( 26) is that

(27) τ p3Cκ 0 g 0 q ´1.
Indeed, assuming that τ ă p3Cκ 0 g 0 q ´1, Inequalities ( 24), ( 26) and g t 1 2 (Lemma 11) show that } 9 p t } is bounded on r0, τ q. Therefore p t has a limit as t Ñ τ , and then η t is defined on the interval r0, τ s. But g τ ă 8, by (26) with t Ñ τ , therefore η τ is not a singular zero of v τ ¨F and η t can be continued in a neighborhood of τ contradicting that τ is maximal.

Next, we compute that

9 β t " g t 9 δ t `9 g t δ t g t κ t `2Cκ t g 2 t δ t " p1 `2Cβ t qκ t g t , then d dt logp1 `2Cβ t q 2Cκ t g t 2Cκ 0 g 0 1 ´3Ctκ 0 g 0 , by (26)
,

" ´2 3 d dt logp1 ´3Ctκ 0 g 0 q,
and therefore, after integration with respect to t,

(28) log ˆ1 `2Cβ t 1 `2Cβ 0 ˙ 2 3 log ˆ1 1 ´3Ctκ 0 g 0 ˙.
Exponentiating both sides leads to (29)

β t 1 `2Cβ 0 2C p1 ´3Ctκ 0 g 0 q 2 3 ´1 2C
.

We now bound κ 0 g 0 . As a function on U ˆPn , we compute that We multiply by d U pu, vq both sides, use the hypotheses (a) and (b), and obtain

(34) d U pu, vqκ 0 g 0 1 4 A exp ˆ3 2 CA 1 ´CA ˙ă 5 12 A,
where the last inequality follows from the hypothesis CA 1 4 . Together with ( 27) and the hypothesis CA 1 4 , we deduce d U pu, vq ă τ . In particular, we can define ζ 1 " η d U pu,vq , which is a zero of v¨F , and apply Inequality (29) at t " d U pu, vq. This gives, in combination with (34) and Hypothesis (a),

d P pz, ζ 1 qgpv, ζ 1 q 1 `2CA 2Cp1 ´5 4 CAq 2 3 ´1 2C ˜1 `2 4 2 4 p1 ´5 16 q 2 3 ´4 2 ¸A 2A using again that CA 1
4 . This concludes the proof.

Based on Proposition 22, the procedure NC (Algorithm 2) computes an approximate zero of a system u ¨F given a zero of another system v ¨F using a numerical continuation along a path pw t q 0 t T from v to u.

Theorem 23. On input F , u, v and z, assuming that z is a zero of v ¨F , Algorithm 2 ouputs an approximate zero of u ¨F or loops forever.

If the continuation path pw t q 0 t T chosen by the algorithm lifts as a continous path pw t , ζ t q in V with ζ 0 " z, then the the algorithm terminates after at most

25C ż T 0 κpw t , ζ t qgpw t , ζ t qdt continuation steps.
Algorithm 2. Numerical continuation Input. F P Hrns, u, v P U and z P P n Precondition. z is a zero of v ¨F and the function g satisfies ( H1) and (H2). Output. w P P n . Postcondition. w is an approximate zero of u ¨F .

function NC (F , u, v, z) pw t q 0 t T Ð a 1-Lipschitz continuous path from v to u t Ð 1{ p16C κpw 0 , zqgpw 0 , zqq while t ă T do z Ð N wt pzq t Ð t `1{ p16C κpw t , zqgpw t , zqq end while return z end function Proof. Let t 0 . " 0, let t k be the value of t at the beginning of the kth iteration, let z 0 . " z and let z k be the value of z at the end of the kth iteration; namely

t k`1 . " t k `1 16C κpw t k , z k qgpw t k , z k q (35) z k`1 . " N wt k`1 pz k q. ( 36
)
Let K be the largest integer such that t K T (or K . " 8 if there is no such integer). The output of the algorithm, if any, is z K . Thanks to the Lipschitz hypothesis for w, we have, for any k 0,

d U pw t k , w t k`1 q t k`1 ´tk " p16Cκpw t k , z k qgpw t k , z k qq ´1 .

Repeated application of Proposition 22 with A

.

" 1 4C leads to (37)

d P pz k , ζ t k qgpw t k , ζ t k q A " 1 4C ,
for any k 0 (conclusion (ii) of Proposition 22 is used for hypothesis (a) at the next step, initialization is trivial since z is a zero). By Proposition 22 again, for any k 0 and any t P rt k , t k`1 s, z k is an approximate zero of w t ¨F . In particular, z K is an approximate zero of w T ¨F . This proves the correctness of the algorithm.

Concerning the bound on the number of iterations, we first note that

ż T 0 κ t g t dt ż t K 0 κ t g t dt, because t K ă T , K´1 ÿ k"0 pt k`1 ´tk q min t k săt k`1 κ s g s " K´1 ÿ k"0 min t k săt k`1 κ s g s 16C κpw t k , z k qgpw t k , z k q , ( 38
)
where we use the notations of the proof of Proposition 22 applied to the path pw t q.

Similarly to (25), but aiming now for lower bounds, we compute that

d ds 1 κ s g s 3C.
After integration, analogously to (26), we obtain that for any t k s ă t k`1

κ s g s κ t k g t k 1 `3Cpt k`1 ´tk qκ t k g t k .
We also check, similarly to (33), integrating along a shortest path from ζ t k to z k , that

κ t k g t k κpw t k , z k qgpw t k , z k q exp ˆ´3 2 Cd P pz k , ζ t k qgpw t k , ζ k q 1 `Cd P pz k , ζ t k qgpw t k , ζ t k q ˙ κpw t k , z k qgpw t k , z k q expp´3 10 q, with (37).
Therefore, for any t k s ă t k`1 ,

κ s g s κpw t k , z k qgpw t k , z k q expp´3 10 q 1 `3Cpt k`1 ´tk qκpw t k , z k qgpw t k , z k q expp´3 10 q κpw t k , z k qgpw t k , z k q exp `3 10 ˘`3 16
, using the value for t k`1 ´tk (35), and then

min t k săt k`1 κ s g s 16C κpw t k , z k qgpw t k , z k q 1 16 exp `3 10 ˘`3 ¨1 C 1 25C
.

Therefore, by ( 38),

ş T 0 κ t g t dt 1 25C K.
We have some degrees of freedom but also some constraints in the choice of the path pw t q 0 t T from v to u:

(P1) the path is 1-Lipschitz continuous; (P2) the path pv ´1w t q 0 t T (from 1 U to v ´1u) depends only on v ´1u; and (P3) the length T of the path is at most 4n.

The first one is required by the numerical continuation algorithm. The two others will be useful for the complexity analysis.

An obvious choice of the path between v and u is the shortest one: we write v ´1u " pexppA 1 q, . . . , exppA n qq for some skew-Hermitian matrices A 1 , . . . , A n and define

w t . " v `expp t T A 1 q, . . . , expp t T A n q ˘, for 0 t T , where T . " p ř i }A i } 2 u q 1 2
. We can always choose the matrices A i such that T 4n as follows: diagonalize each A i in a unitary basis (which preserves the Frobenius norm) as diagpθ i,0 , . . . , θ i,n q ? ´1, for some θ i,j P R; add integer multiples of 2π to the θ i,j (which preserves the end points of the path) so that θ i,j P r´π, πs; and finally, obtain

T 2 " n ÿ i"1 }A i } 2 u " 1 2 n ÿ i"1 n ÿ j"0 θ 2 i,j 1 2 npn `1qπ 2 ă p4nq 2 .
Naturally, it may not be convenient to compute matrix logarithms and exponentials, especially for the complexity analysis in the BSS model. In §4.3.2 we will see paths that are cheaper to compute but still satisfy (P2) and (P3).

Remark 24. To implement Algorithm 2, the computation of the step size by which t is updated can be relaxed: it is enough to compute a number τ such that

M ´1 p16C κpw t , zqgpw t , zqq ´1 τ p16C κpw t , zqgpw t , zqq ´1 ,
for some constant M 1, and use it as the step size. Correctness is not harmed, and the number of continuation steps is now bounded by

25M C ż T 0 κpw t , ζ t qgpw t , ζ t qdt.
Algorithm 3. An analogue of Beltrán-Pardo algorithm in the rigid setting Input. Homogeneous polynomial system F P Hrns and u P U Output. z P P n . Postcondition. z is an approximate zero of u ¨F .

function Solve(F , u) pv, ηq Ð SamplepV F q return NC pu, v, ηq end function 3.5. A randomized algorithm. We have everything we need to mimic Beltrán-Pardo algorithm in the rigid setting: a continuation algorithm with an integral estimate for its complexity and a recipe to sample points in the solution variety with the appropriate distribution. This leads to Algorithm 3 (Solve): for finding a zero of u ¨F , we first sample a random element pv, ηq in V, with Algorithm 1 (Sample), and then perform, with Algorithm 2, the numerical continuation along a path in U from v to u. Based on Theorem 23, we can estimate the expected number of continuation steps performed by SolvepF, uq when u is uniformly distributed.

Theorem 25. If u P U is uniformly distributed then SolvepF, uq terminates almost surely and outputs an approximate zero of u ¨F after K continuation steps, with E rKs 100Cn E rκpv, ηqgpv, ηqs .

Proof. Let pw t q 0 t T be the path from v to u chosen in NC. By (P2), v ´1w t is a function of v ´1u. We first note that v and v ´1u are independent and uniformly distributed in U, because the Jacobian of the diffeomorphism pu, vq P U ˆU Þ Ñ pv, v ´1uq P U ˆU is constant. Secondly, by hypothesis, for any 0 s 1, the random variable v ´1w T s depends only on v ´1u, so it is independent from v. Therefore w T s , which equals vpv ´1w T s q, is uniformly distributed and independent from v ´1u.

By Proposition 15, with probability 1, all the polynomial systems w t ¨F , for 0 t T , have only regular zeros. So almost surely, all the zeros of v ¨F can be continued as zeros of w t ¨F . Let ζ t be the zero of w t ¨F obtained by continuation of the zero η of v ¨F . Since ζ is uniformly distributed among the zeros of v, it follows that ζ t is uniformly distributed among the zeros of w t , because the numerical continuation, which is almost surely well defined, induces a bijective correspondance between the two finite sets of zeros. Therefore, for any 0 s 1, pw T s , ζ T s q is a ρ std -distributed random variable independent from v ´1u, and in particular, independent from T .

Together with Theorem 23 (and the change of variable t " T s), this implies

ErKs E " 25C ż 1 0 κpw T s , ζ T s qgpw T s , ζ T s qT ds  " 25C ż 1 0 E rκpw T s , ζ T s qgpw T s , ζ T s qT s ds " 25C E rκpv, ηqgpv, ηqs ErT s,
which leads to the claim, with the bound T 4n given by (P3).

Average complexity for random dense polynomial systems

Theorem 25 on the average complexity of computing one zero of a random system u ¨F , with u P U uniformly distributed and F fixed, is applicable to the more common question of computing one zero of a random system F , under a unitary invariance condition on the probability distribution of F .

The polynomial system F P Hrns fixed in §3 is now a random variable. The probability distribution of F is assumed to be unitary invariant: that is, for any u P U, the random systems F and u ¨F are identically distributed.

An important example of a unitary invariant distribution is Kostlan's distribution: that is the standard Gaussian distribution on Hrns endowed with Weyl's Hermitian norm. The unitary invariance of Kostlan's distribution follows from the invariance of Weyl's norm under the action of H. Concretely, a Kostlan random system F P Hrns is a tuple pf 1 , . . . , f n q of independent Kostlan random polynomials, that is

f i . " ÿ j0`¨¨¨`jn"di ˆdi ! j 0 ! ¨¨¨j n ! ˙1 2 c j0,...,jn x j0 0 ¨¨¨x jn n ,
where the coefficients c j0,...,jn are independent standard normal variables in C. Section 4.1 contains the average analysis of the number of continuation steps in the general setting of a unitary invariant distribution. Section 4.2 describes the function γFrob that will be used for the numerical continuation (in the role of g). Next, Section 4.3 discusses the computational model and the construction of paths in U. And lastly, Section 4.4 concludes the average analysis for Kostlan's distribution.

4.1. Unitary invariant random systems. Let g : Hrns Ñ p0, 8s be a function of the form (compare to Equation (13) defining γ) (39) gpF, zq

.

" κpF, zq `g1 pf 1 , zq 2 `¨¨¨`g n pf n , zq 2 ˘1 2 , for some g i : H di ˆPn Ñ p0, 8s such that for any 1 i n and any f P H di , (H1') x P P n , γpf, xq g i pf, xq; (H2') for any x P P n Þ Ñ g i pf, xq ´1 is C 1 -Lipschitz continuous (C 1 4); and (H3') for any z P P n and u P U pn `1q, g i pu ¨f, xq " g i pf, u ´1xq. These assumptions make it possible to use g for numerical continuation in the rigid setting. Theorem 27. If the probability distribution of the system F " pf 1 , . . . , f n q P Hrns is unitary invariant, the procedure SolvepF, 1 U q, with gpu, xq . " gpu ¨F, xq for the continuation, computes an approximate root of F using K continuation steps, with

ErKs 1800C 1 n 3 ˆn ÿ i"1 E " g i pf i , ζ i q 2 ‰ ˙1 2 ,
where ζ 1 , . . . , ζ n P P n are random independent uniformly distributed zeros of the respective random polynomials f 1 , . . . , f n .

Proof. Let KpF, uq be the (random) number of continuation steps performed by SolvepF, uq. Let u P U be a uniformly distributed random variable independent from F . By the unitary invariance hypothesis, F " u¨F , so KpF, 1 U q " Kpu¨F, 1 U q, and by the assumption (P2) on the unitary invariance of the choice of the continuation path, Kpu ¨F, 1 U q " KpF, uq. In particular, E rKpF, 1 U qs " E rKpF, uqs. By Theorem 25 (with C " 3C

g i pf i , u ´1 i ζq 2 ˙1 2 ,
using also the unitary invariance of each g i (H3').

Conditionally on F , pu, ζq is ρ std -distributed in the solution variety V F . By Theorem 8, u ´1 1 ζ, . . . , u ´1 n ζ are independent and uniformly distributed zeros of f 1 , . . . , f n respectively, and κpu ¨F, ζq, which depends only on Lpu ¨F, ζq, see ( 16), is independent with them conditionally on F . So the two factors in the right-hand side of ( 41

g i pf i , u ´1 i ζq 2 ˙1 2 ff (43) 6n 2 ˆn ÿ i"1 E " g i pf i , u ´1 i ζq 2 ‰ ˙1 2 ,
where the last inequality follows from Jensen's inequality. We note as above that u ´1 i ζ is a uniformly distributed zero of f i , so that E " 40), this concludes the proof.

g i pf i , u ´1 i ζq 2 ‰ " E " g i pf i , ζ i q 2 ‰ . With (
Remark 28. Under the same hypotheses, we also have the bound " hpe i1 , . . . , e i k q P F , for 1 i 1 , . . . , i k n. This definition does not depend on he choices of the unitary basis.

ErKs 1800C 1 n 3 n ÿ i"1 E rg i pf i , ζ i qs , obtained by bounding `ři g i pf i , u ´1 i ζq 2 ˘1 2 ř i g i pf i , u ´1 i ζq in (43
Lemma 29. For any multilinear map h :

E k Ñ F , ~h~ }h} Frob pdim Eq k 2 ~h~.
Proof. This is better seen if we consider h as a map E Ñ pE Ñ ¨¨¨pE Ñ F qq. The claim follows from an induction on k and the usual comparison between the Frobenius and the operator norm.

The following lemma relates the Weyl norm of a homogeneous polynomial with the Frobenius norm of an appropriate higher derivative. Recall that the Weyl norm of a homogeneous polynomial of degree k is defined by ( 45)

› › › › ÿ j0`¨¨¨`jn"k c j0,...,jn x j0 0 ¨¨¨x jn n › › › › 2 W . " ÿ j0`¨¨¨`jn"k j 0 ! ¨¨¨j n ! k! |c j0,...,jn | 2 .
Lemma 30. For any homogeneous polynomial ppx 0 , . . . , x n q of degree k,

}p} W " › › 1 k! d k 0 p › › Frob . Proof. For any 0 i 1 , . . . , i k n, 1 k! d k 0 ppe i1 , . . . , e i k q " 1 k! B k p Bx i1 ¨¨¨Bx i k ˇˇˇx "0 " j 0 ! ¨¨¨j n ! k! c j0,...,jn ,
where j m is the number of indices i ˚that are equal to m and where c j0,...,jn is the coefficient of x j0 0 ¨¨¨x jn n in p. There are exactly k! j0!¨¨¨jn! k-uples i ˚that lead to a given pn `1q-uple j ˚. Therefore,

› › 1 k! d k 0 ppe i1 , . . . , e i k q › › 2 Frob " ÿ j0`¨¨¨`jn"k j 0 ! ¨¨¨j n ! k! |c j0,...,jn | 2 ,
and this is exactly }p} 2 W . 4.2.2. The γ number with Frobenius norms. For a homogeneous polynomial f :

C n`1 Ñ C, we define (46) γ Frob pf, zq . " $ & % sup k 2 ´1 k! }d z f } ´1 › › d k z f › › Frob ¯1 k´1 if d z f is nonzero, 8 otherwise,
and for a homogeneous polynomial system F " pf 1 , . . . , f r q P Hrrs, we define γFrob pF, zq

.

" κpF, zq `γFrob pf 1 , zq 2 `¨¨¨`γ Frob pf r , zq 2 ˘1 2 .

Compare with the definitions of γ and γ, §2.5. In order to use Algorithm 2 with γFrob as g, we must check (H1) and (H2). By Lemma 26, it is enough to check (H1'), (H2') and (H3') for γ Frob of a single polynomial. The condition (H1'), that is γ γ Frob , is clear by Lemma 29. The condition (H3'), that is γ Frob pu ¨f, zq " γ Frob pf, u ´1zq follows from the unitary invariance of the Frobenius norm. The following lemma shows (H2').

Lemma 31. For any polynomial f P H d , the function x P P n Þ Ñ 1{γ Frob pf, xq is 5-Lipschitz continuous.

Proof. Let px t q 0 t 1 be a differentiable path in SpC n`1 q. Let a t . [START_REF] Blum | On a Theory of Computation and Complexity over the Real Numbers: NP-Completeness, Recursive Functions and Universal Machines[END_REF]) extended with a "6th type of node", as did Shub and Smale (1996). Unlike Shub and Smale, we will apply it to univariate (or rather homogeneous bivariate) polynomials only. A node of this type has the following behavior. If it is given as input a homogeneous polynomial f P Crx, ys and an approximate zero z P P 1 of f , with associated zero ζ, it outputs ζ. In any other case, it fails. There is no need to specify how it fails because we will make sure that this will not happen.

" }d xt f } ´1 and pB k q t . " 1 k! a t d k xt f , so that pB k q t is a multilinear map pC n`1 q k Ñ C.
ˇˇˇd dt }B k } 1 k´1 Frob ˇˇˇ" 1 k ´1 }B k } 1 k´1 ´1 Frob ˇˇd dt }B k } Frob ˇˇ k `3 k ´1 γ k`1 Frob }B k } Frob } 9
| 9 γ Frob | k `3 k ´1 γ k`1 Frob }B k } Frob } 9 x}, by (51), " k `3 k ´1 γ k`1 Frob γ k´1 Frob } 9 x}, by (52)
From the practical point of view, given a point z which approximates a zero ζ of a homogeneous polynomial f P Crx, ys, one can refine the approximation to obtain d P pz, ζq ε in log 2 log 2 π ε Newton's iterations. For most practical purpose, this looks like infinite precision. In that sense, the 6th type of node does not add much power.

Do we really need a 6th type of node? The continuation method proposed here uses a start system defined in terms of the zeros of some homogeneous bivariate polynomials. Naturally, the algorithm would also work with approximate zeros only. However, if we do it this way, then the distribution of the start system is not easily described, it is only close to a nice distribution. I showed [START_REF] Lairez | A Deterministic Algorithm to Compute Approximate Roots of Polynomial Systems in Polynomial Average Time[END_REF]) how to deal with the complexity analysis in an analogue situation but it is too technical an argument for the little value it adds.

Interval arithmetic gives another way to remove the need for this extra type of node: wherever an exact zero is expected, we use bounding boxes instead and perform the subsequent operations with interval arithmetic. If the precision happens to be insufficient, we refine the bounding boxes with Newton's iteration and start over the computation. The convergence of Newton's iteration is so fast that even with naive estimations of the numerical stability, the number of start over will be moderate. However, this is no less technical to formalize.

For convenience, we will also assume the ability to compute fractional powers of a positive real number at unit cost. This will allow us to compute Hermitian norms and the numbers γ Frob and γFrob exactly. 4.3.2. Continuation paths in the unitary group. While geodesics in U are a natural choice for continuation paths, see §3.4, they are not easy to compute in the BSS model. We can describe more elementary continuation paths using Householder's reflections. For any 1-dimensional subspace l Ă C n`1 and any θ P R, let Rpl, θq P U pn `1q be the unique map such that Rpl, θq| l " e iθ id l and Rpl, θq| l K " id l K . Note that for the angle π, Rpl, πq is a reflection. The computation of a matrix multiplication ARpl, θq, for any A P U pn `1q, requires only Opn 2 q operations because Rpl, θq ´id has rank 1 and can be written vv ˚for some v P C pn`1qˆ1 .

Given a unitary matrix v P U pn`1q, the procedure of [START_REF] Householder | Unitary Triangularization of a Nonsymmetric Matrix[END_REF] (with the necessary changes in the complex case) decomposes v as v " e iα Rpl 1 , πq ¨¨¨Rpl n , πq, for some α P r´π, πs, with Opn 3 q operations. One can define the path w t . " e i t τ α Rpl 1 , t τ πq ¨¨¨Rpl n , t τ πq, where τ 2 .

" 1 2 `α2 `nπ 2 ˘ n`1 2 π 2 . Given u, v P U, we define a 1-Lipshitz continuous path pw t q t 0 from 1 U to v ´1u, component-wise with the method above.

It reaches v ´1u at t " b npn`1q 2 π ă 4n. To compute w t on a BSS machine, we can replace the trigonometric functions with any other functions parametrizing the circle. This construction satisfies the three conditions (P1)-(P3) from §3.4.

For a given t, the cost of computing w t is dominated by the the cost of multiplying by Rpl, θq matrices: there are n such multiplications for each of the n components of w t , that is Opn 4 q operations. 4.3.3. Computation of γFrob , cost of a continuation step. The reason for introducing γFrob is that we can compute it with low complexity. By contrast, computing γ is NP-hard because it involves the computation of the spectral norm of symmetric multilinear maps, and there is no polynomial-time approximation scheme, unless P " NP (Hillar and Lim 2013, Theorem 10.2). Beware though, a too naive algorithm for computing γ Frob requires ΩpN 2 q operations, where N is the input size (see §1.3). Given a polynomial f P H d and a point z P C n`1 , the evaluation f pzq and the vector d z f can be computed with Opdim H d q operations (Bürgisser and Cucker 2013, Lemma 16.32;[START_REF] Baur | The Complexity of Partial Derivatives[END_REF].

Proposition 32. Given a homogeneous polynomial f P H d and z P P n , one can compute γ Frob pf, zq with Opnd 2 dim H d q operations, as dim H d Ñ 8.

Proof. We can compute }d z f } ´1 in Opdim H d q operations, so the main task is to

compute › › 1 k! d k z f › ›
Frob for all 2 k d, see (46). Let g be the shifted polynomial g : x P C n`1 Þ Ñ f pz `xq, so that d k 0 g " d k z f . Let g k denote the homogeneous component of degree k of g. According to Lemma 30, } 1 k! d k 0 g} Frob " }g k } W . Let S denote the size of g, that is the number of coefficients in a dense nonhomogeneous polynomial of degree d in n `1 variables. He have S " `n`d`1

d ˘ d dim H d .
In view of (45), the computation of }g k } 2 W reduces to the computation of the coefficients of g k in the monomial basis and the multinomial coefficients i0!¨¨¨in! pi0`¨¨¨`inq! . We can compute them all with OpSq operations thanks to the recurrence relation

i 0 ! ¨¨¨i n´1 !pi n `1q! pi 0 `¨¨¨`i n `1q! " i n `1 i 0 `¨¨¨`i n `1 i 0 ! ¨¨¨i n ! pi 0 `¨¨¨`i n q! .
Therefore, we can compute γ Frob pf, zq in OpSq operations given the coefficients of g in the monomial basis.

To compute g, we shift the variables one after the other. To compute the first shift f px 0 `z0 , x 1 , . . . , x n q (subsequent shifts are identical), we write

f " ÿ i1`¨¨¨`in d p i1,...,in px 0 qx i1 1 ¨¨¨x in n ,
where the p i1,...,in px 0 q are polynomials of degree at most d. There are at most dim H d of them (the number of monomials of degree at most d in n variables). Moreover, computing them requires only OpSq copy operations and no arithmetic operation: their coefficients in the monomial basis are directly read from the coefficients of f in the monomial basis. One can compute p i1,...,in px 0 `z0 q with Opd 2 q operations with a naive algorithm. Note that we can do this with only d 1`op1q operations using fast evaluation and interpolation algorithms [START_REF] Bostan | Algorithmes Efficaces En Calcul Formel[END_REF][START_REF] Zur Gathen | Modern Computer Algebra[END_REF]. All together, this is Opd 2 dim H d q operations. We recover f px 0 `z0 , x 1 , . . . , x n q in OpSq operations from the p i1,...,in px 0 `z0 q (and no arithmetic operation). We repeat this shift operation for each one of the n `1 variables and this gives the claim.

Corollary 33. Given F P Hrns, u P U and z P P n , one can compute κpu ¨F, zq and γFrob pu ¨F, zq within a factor 2 in OpnD 2 N q operations as N Ñ 8.

Proof. The evaluation of u ¨F at a point z P C n`1 can be computed as pf 1 pu 1 zq, . . . , f n pu nzqq with Opn 3 q operations to compute the vectors u i z and ř i Opdim H di q " OpN q additional operations to evaluate the polynomials f i . Therefore, the matrix d z pu ¨F q be computed with OpN `n3 q operations too [START_REF] Baur | The Complexity of Partial Derivatives[END_REF]. The computation of Lpu ¨F, zq requires Opn 2 q additional operations, following (15). Then, we can compute κ, that is the inverse of the least singular value of Lpu, zq, within a factor of 2 in Opn 3 q operations, using a tridiagonalization with Householder's reflections and a result by [START_REF] Kahan | Accurate Eigenvalues of a Symmetric Tri-Diagonal Matrix[END_REF]. To compute γFrob , it only remains to compute the γ Frob pu i ¨f, zq " γ Frob pf, u i zq, for 1 i n, which requires all together OpnD 2 N `n3 q operations, by Proposition 32. The term n 3 is OpnN q, so this gives the claim.

Since κ is defined as the operator norm of some matrix, the exact computation is difficult in the BSS model. One could use the Frobenius norm instead but computing κ within a factor 2 is satisfactory, see Remark 24.

Corollary 34. In Algorithm 2 with g " γFrob , one continuation step can be performed in Opn 2 D 2 N q operations. Proof. A step boils down to: one evaluation of γFrob and κ, that is OpnD 2 N q operations by Corollary 33; one evaluation of the continuation path, that is Opn 4 q " Opn 2 N 2 q operations, see §4.3.2; and one Newton's iteration, that is Opn 3 `N q " OpnN q operations (Bürgisser and Cucker 2013, Proposition 16.32). 4.4. Gaussian random systems. We conclude with the study of the average complexity of SolvepF, 1 U q when F is a Kostlan random system, that is a standard normal variable in Hrns endowed with Weyl's norm. In view of Theorem 27, it only remains to study the average value of γ Frob pf, ζq when f is a Kostlan random polynomial and ζ a uniformly distributed zero of it. To this purpose, the main tool is a corollary of a result by Beltrán and Pardo (2011). Proof. Let λ 2 , . . . , λ n P pC n`1 q ˚be independent Gaussian linear forms, so that F . " pf, λ 2 , . . . , λ n q is a Kostlan random system of degree pd, 1, . . . , 1q. Let η P P n be a uniformly distributed random zero of F .

The zero set L of λ 2 , . . . , λ n is a uniformly distributed random line independent from f and η is uniformly distributed in V pf q X L. By Corollary 9, η is uniformly distributed in V pf q, so we may assume that ζ " η. Beltrán and Pardo (2011, Theorem 7), and Bürgisser and Cucker (2013, Prop. 17.21) for the Gaussian case, proved that: the matrix diagpd ´1 2 , 1, . . . , 1qdζF is a standard normal variable in C nˆpn`1q ; and conditionally on ζ, G is a standard normal variable in R ζ and is independent from d ζ F . The claim follows by considering the first row of dζF , that is dζf , and the first coordinate of G.

The following three lemmas deal with the average analysis of γ Frob .

Lemma 36. Let f P H d and ζ " r1 : 0 : ¨¨¨: 0s. We write f "

d ÿ i"0
x d´i 0 g i px 1 , . . . , x n q, for some uniquely determined homogeneous polynomials g 0 , . . . , g d of degrees 0, . . . , d respectively. For any k 2,

› › 1 k! d k ζ f › › 2 Frob " ˆd k ˙k ÿ l"0 ˆd ´l k ´l˙› › x d´l 0 g l › › 2 W .
Proof. Let f . " f px 0 `1, x 1 , . . . , x n q and let fpkq be the homogeneous component of degree k of f . We compute that fpkq " Looking closely at the definition of Weyl's inner product reveals that

› › x k´l 0 g l › › 2 W " `d d´l k k´l ˘› › x d´l 0 g l › › 2 W " `d k d´l k´l ˘› › x d´l 0 g l › › 2 W ,
and the claim follows.

Lemma 37. Let f P H d be a Kostlan random polynomial and ζ P P n be a uniformly distributed zero of f . For any k 2,

E " }d ζ f } ´2 › › 1 k! d k ζ f i › › 2 Frob ı 1 nd ˆd k ˙ˆd `n k ˙ `1 4 d 2 pd `nq ˘k´1 .
Proof. We can choose (random) coordinates such that ζ " r1 : 0 : ¨¨¨: 0s. Let g 0 , . . . , g d be the polynomials defined in Lemma 36. To begin with, we describe the distribution of the random polynomials g 0 , . . . , g d . The polynomial g 0 (of degree 0) is simply zero because ζ is a zero of f . The second one g 1 has degree 1, and as a linear form, it is equal to d ζ f . According to Proposition 35(i), it is a standard normal variable after multiplication by d ´1 2 . In particular d}g 1 } ´2 W is the inverse of a χ 2 -distributed variable with 2n `2 degrees of freedom, therefore

E " }g 1 } ´2 W ‰ " 1 2nd
.

For l 2, the polynomial x d´l 0 g l is the orthogonal projection of f on the subspace of all polynomials of the form x d´l 0 ppx 1 , . . . , x n q, a which is a subspace of tg P H d | gpζq " 0 and d ζ g " 0u Ă H d .

Thus, by Proposition 35(ii), x d´l 0 g l is a standard normal variable in the appropriate subspace and is independent from g 1 . In particular, for any l 2,

E " › › x d´l 0 g l › › 2 W ı " dim R x d´l
E " }d ζ f } ´2 › › 1 k! d k ζ f › › 2 Frob ı " k ÿ l"0 E « ˆd k ˙k ÿ l"0 ˆd ´l k ´l˙} g 1 } ´2 W › › x d´l 0 g l › › 2 W ff ˆd k ˙˜ˆd ´1 k ´1˙1 d `k ÿ l"2 ˆd ´l k ´l˙E " }g 1 } ´2 W ‰ E " }x d´l 0 g l } 2 W ‰ ¸ ˆd k ˙˜ˆd ´1 k ´1˙1 d `1 nd
E " γ Frob pf, ζq 2 ‰ d ÿ k"2 E " ´}d ζ f } ´1 › › 1 k! d k ζ f i › › Frob ¯2 k´1  d ÿ k"2 E " }d ζ f } ´2 › › 1 k! d k ζ f i › › 2 Frob

  zq vol tv P U pn `1q | vp " zu " volpU p1q ˆU pnqq ż U pn`1q du ż XXuY dz Θpu, zq,

Proof.

  We proceed by induction on r. When r "

  dv Θpv ´1, xq, by the change of variable v " u ´1, xq, by the change of variable u " v ´1.

Corollary 7 .

 7 For any measurable function Θ : tph, xq P L | x P Xhu Ñ r0, 8q ż xq det K phq.

  xq det K pLpu, xqq " ż Ux dv Θpu, xq det K pLpu, xqq.

Lemma 26 .

 26 If (H1')-(H3') hold, then for any F P Hrns, the function g : pu, xq P U ˆPn Þ Ñ gpu ¨F, xq satisfies conditions (H1) and (H2), with C " 3C 1 .Proof. Condition (H1) follows directly from the definitions of γ and g. Condition (H2) follows exactly as the Lipschitz continuity of γ (Lemma 21).

Proposition 35 .

 35 Let f P H d be a Kostlan random polynomial, let ζ be a random uniformly distributed point in tz P P n | f pzq " 0u and let ζ P C n`1 be a random uniformly distributed vector such that } ζ} " 1 and r ζs " ζ. Then (i) 1 ? d d ζ f is a standard normal variable in pC n`1 q ˚; and (ii) given ζ, the orthogonal projection of f on tg P H d | gpζq " 0 and d ζ g " 0u is a standard normal variable and is independent from d ζ f .

Let

  G the orthogonal projection of F on the subspace R ζ . " tG P H | Gpζq " 0 and d ζ G " 0u .

  we remark that `d´l k´l counts the number of monomials of degree k ´l in d ´k `1 variables while `n`l l counts the number of monomials of degree l in n `1 variables. Therefore, the sum over l counts the number of monomials of degree k in pd ´k `1q `pn `1q variables, that is `d`n k ˘.Concerning the second inequality, the maximum value of´1 nd `d k ˘`d`n k ˘¯1 k´1 ,with k 2, is reached for k " 2. That is, for any k 2Frob pf, ζq 2 ‰ 1 4 d 3 pd `nq. Proof. We bound the supremum in the definition of γ Frob by a sum:

  pd `nq, by Lemma 37,

  and by Lemma 14, the codimension of S in U ˆU is at least 1.3.2. Condition number.The rigid solution variety, considered as a manifold of pairs problem-solution has a natural condition number. We show that this is the incidence condition number κ, defined in §2.5. This is what makes the split gamma number γ fit nicely in the setting of the rigid solution variety. The system F being fixed, we will denote κpu ¨F, xq and γpu ¨F, xq simply as κpu, xq and γpu, xq.

		} 9 x} κpu, xq} 9 u} u .
	With the identification (15), we obtain that p 9 u, 9 xq P T u,x V if and only if
	(18)	Lpu, xqp 9 xq " `}d x f i } ´1d x f i p 9 u i xq ˘1	i n .
	For all 1 i n, d x f i pxq " degpf i qf i pxq " 0 (Euler's relation), therefore
	(19)	|d u i xq} } 9 u i } u ,
	as in Lemma 4. If Equation (18) does hold, then
		}Lpu, xqp 9 xq} 2 "

Lemma 16. For any pu, xq P VzΣ and any tangent vector p 9 u, 9

xq P T u,x V,

Proof. Without loss of generality, we may assume that u " 1 U which simplifies notations. The tangent space of V at pu, xq is

(17) T u,x V " tp 9 u, 9 xq P T u U ˆTx P n | @i, f i `p1 U `t 9 u i `optqq ´1px `t 9 x `optqq ˘" optq as t Ñ 0 ( " tp 9 u, 9 xq P T u U ˆTx P n | @i, f i px `tp 9 x ´9 u i xqq " optq as t Ñ 0u " tp 9 u, 9 xq P T u U ˆTx P n | @i, d x f i p 9 xq " d x f i p 9 u i xqu . x f i p 9 u i xq| " |d x f i pπ x p 9 u i xqq| }d x f i }}π x p 9 u i xq},

where π x is the orthogonal projection on txu K . We check that }π x p 9

  ,

		" } 9 u} 2 u .
	Moreover 9 x " Lpu, xq : pLpu, xqp 9 xqq, because 9 x is orthogonal to x and the kernel
	of Lpu, xq is Cx. Therefore
	} 9 x}	Lpu, xq : }Lpu, xqp 9 xq}	Lpu, xq : } 9 u} u ,
	and the claim follows with κpu, xq " Lpu, xq : , by (16).

  It is easy to check that Proposition 18 is equivalent to the Lipschitz continuity of the function 1{γ F , with Lipschitz constant at most 5. We give }dκ} and }dγ} an analogue meaning.Lemma 19. On U ˆPn , }dκ} κ 2 `3κγ. Moreover, if D 2 then }dκ} 5κγ.Proof. The second inequality follows from the first one: If D 2 then at least one γpu i ¨f, xq is greater or equal to D´1 2 , by Lemma 11. It follows that κ 2γ and then κ 2 `3κγ 5κγ.

	Proof of Proposition 18. The most direct way to see this is by (23):
	γ F pyq ´γF pxq d P py, xq	γ F pxq	5u `Opu 2 q d P py, xq	" 5γ F pxq 2 p1 `Opd P px, yqqq ,
	as y Ñ x, where u	. " d P px, yqγ F pxq, and
	γ F pxq ´γF pyq d P px, yq	γ F pyq	5v `Opv 2 q d P px, yq	" 5pγ F pxq `op1qq 2 p1 `Opd P px, yqq ,
	where v
	lim sup

yÑx |γ F pyq ´γF pxq| d P py, xq 5γ F pxq 2 . . " d P px, yqγ F pyq.

  Let γ i pu, xq

	γpu i ¨fi , xq and η	. "	ř	i γ 2 i , so that γ " κ ? η. By Lemma 20, }dγ i } 5	?	. " i and 2γ 2
	then
	}dη} 2	ÿ	γ i }dγ i } 10	?	2	ÿ	γ 3 i	10 ?	2η 3{2 .
			i							i
	Therefore,
	}dγ} }dκ} ? η `1 2 κη ´1 2 }dη}
	5γ 2 `5? 2γ	? η,			by Lemma 19,
	13γ 2 ,						using κ 1, Lemma 1.

  d P pz, η t q. Let moreover g t . " κpv t , η t q. The derivative with respect to t is denoted with a dot.

	β t	. " g t δ t and κ t	.	" gpv t , η t q,
		We first observe that 9 δ t κ t , by Lemma 16, and that
	(24)	} 9 p t } p1 `9 δ 2 t q	1 2	2κ t
	(using κ 1, by Lemma 1). By Lemma 19, 9 κ t	5κ t g t } 9 p t } 10κ 2 t g t and by the
	Lipschitz hypothesis on 1{g, we have 9 g t	Cg 2 t } 9 p t } 2Cκ t g 2 t . This implies that
	d dt κ t g t 3Cpκ t g t q 2 (using C 10) and equivalently,
	(25)	d dt	1 κ t g t	´3C.

  Since 1{g is C-Lipschitz continuous on U ˆPn , for any w P P n on a shortest path between z and ζ, |gpu, wq ´1 ´gpu, ζq ´1| Cd P pζ, zq and then After integrating the relation (31) on a path from pu, ζq to pu, zq, and bounding the right-hand side with (32), we obtain logpκ 0 g 0 q logpκpu, zqgpu, zqq `3 2 Cd P pζ, zqgpu, ζq 1 ´Cd P pζ, zqgpu, ζq ,

	(30)	}dpκgq} }dκ}g `}dg}κ
			5κγg `Cg 2 κ, by Lemma 19 and C-Lipschitz continuity of	1 g	,
			3 2 Cκg 2 , because γ g and 10 C, by assumption,
	and then,
	(31)	}d logpκgq} " pκgq ´1}dpκgq} 3 2 Cg.
	(32)	gpu, wq	gpu, ζq 1 ´Cd P pζ, zqgpu, ζq	.
	and then
	(33)	κ 0 g

0 κpu, zqgpu, zq exp ˆ3 2 Cd P pz, ζqgpu, ζq 1 ´Cd P pz, ζqgpu, ζq ˙.

  ). 4.2. An efficiently computable variant of γ. Controlling the total complexity of Algorithm 3 requires a function g that is easy to compute. The Frobenius gamma number is introduced here with this purpose. 4.2.1. Norms of a multilinear map. Let E and F be Hermitian spaces and let h : E k Ñ F be a multilinear map, the operator norm of h is defined by ~h~. " max t}hpx 1 , . . . , x k q} | x 1 , . . . , x k P SpEqu , where SpEq is the unit sphere of E, and the Frobenius norm of h is defined as where the a i1,...,i k are the coefficients of h in some unitary basis e 1 , . . . , e dim E of E, that is a i1,...,i k .

	(44)	}h} Frob	. "	ˆÿ 1 i1,...,i k n	}a i1,...,i k } 2	˙1 2	,

  From now on, we drop the index t and denote the derivative with respect to t with a dot or with d dt . Writing a as xd x f, d x f y ´1 2 , we compute that }B l } Frob γ Frob pf, xq l´1 , that Frob pf, xq k `pk `1qγ Frob pf, xq k ˘} 9 x} pk `3qγ Frob pf, xq k } 9 x}.

	(47)	9 a " ´a xa d 2 x f p 9 xq, a d x f y,
	where denotes the real part, and the Cauchy-Schwartz inequality implies that
	(48)	| 9 a| a }a d 2 x f p 9 xq},
	noting that }a d x f } " 1. By definition of a and γpf, xq,
		}a d 2 x f p 9 xq} }d x f } ´1 d 2 x f } 9 x}
		}d x f } ´1}d 2 x f } Frob } 9 x},	by Lemma 29,
		2γ Frob pf, xq} 9 x},	by definition of γ Frob pf, xq,
	which implies, in combination with (48), that
	(49)	| 9 a| 2aγ Frob pf, xq} 9 x}.
	We note that d dt d k x f " d k`1 x	f p 9 xq, therefore,
	(50)	9 B k " 9 aa ´1B k `pk `1qB k`1 p 9 xq,
	and it follows, since for any l, ˇˇd dt }B k } Frob ˇˇ } 9 B k } Frob , as } ´}Frob is 1-Lipschitz continuous,
		2γ Frob pf, xq}B k } Frob } 9 x} `pk `1q}B k`1 } Frob } 9 x},
			by (50) and (49),
	`2γ It follows that
	(51)

  x}. Frob is the supremum of all }B k }

	By definition, γ 1{pk´1q Frob	(k	2), finitely many of
	which are nonzero, so at a given time t, there is some k such that
	(52)	1{pk´1q γ Frob pf, xq " }B k } Frob
	in a (one sided) neighborhood of t. Therefore 9 γ Frob " d dt }B k } 1{pk´1q Frob	and the
	computation above shows that

  ,As a function on P n , d x γ Frob pf, ´qp 9xq " 9 γ Frob , so that|d x γ Frob pf, ´qp 9 xq| 5γ Frob pf, xq 2 } 9 x}.Since the inequality holds for any differentiable path, covering all possible values of 9x, it follows that }d x γ Frob pf, ´q} 5γ Frob pf, xq 2 . Consequently, }d x γ Frob pf, ´q´1 } 5 and the claim follows. 4.3. Implementation details, complexity. 4.3.1. Computational model. We use the Blum-Shub-Smale model

		5γ 2 Frob } 9 x},	because k 2.
	"	k k	`3 ´1 γ 2 Frob } 9 x}

  0 ppx 1 , . . . , x n q P H d

			(	l ˆn ´1 " 2	`l	˙.
	Note also that }g 1 } ´2 W	› › x d´l 0 g 1	› › 2 W " 1 d . It follows, by Lemma 36, that

P. LAIREZ

P. LAIREZ 1 4 d 3 pd `nq, and this is the claim. Proposition 39. If F P Hrns is a Kostlan random system, then SamplepF q (Algorithm 1) outputs a ρ std -distributed pu, ζq P V F with Opn 3 q samplings of the normal distribution on R and Opn 4 `nD 4 q operations on average. Proof. By Proposition 10, SamplepF q requires Opn 3 q samplings, Opn 4 q operations and n times root-finding of bivariate homogeneous polynomials of degree at most D. These polynomials are the restrictions of the polynomials f 1 , . . . , f n on independent uniformly distributed random projective line L 1 , . . . , L n respectively. Choosing random coordinates so that L i is spanned by r1 : 0 : ¨¨¨s and r0 : 1 : 0 : ¨¨¨s, the restriction of f i to L i is just f i px 0 , x 1 , 0, . . . , 0q. So the restriction map f P H di Ñ f |Li is an orthogonal projector (or equivalently, the adjoint map f P Crx 0 , x 1 s d Ñ H d is an isometric embedding, which follows from the definition (45) of Weyl's norm). In particular, f i | Li is a Kostlan random polynomial in Crx 0 , x 1 s d , and the algorithm of Beltrán and Pardo (2011) computes an approximate root of it with OpD 4 q operations on average. The 6th type of node recover the exact root.

Theorem 40 (Main result). If F P Hrns is a Kostlan random system, then SolvepF, 1 U q (with gpu, xq . " γFrob pu ¨F, xq for the continuation) outputs an approximate zero of F almost surely with Opn 4 D 2 q continuation steps on average and Opn 6 D 4 N q operations on average, when N Ñ 8. When minpn, Dq Ñ 8, this is N 1`op1q .

Proof. We first note that the conditions (H1')-(H3') are statisfied for γFrob , see §4.2.2, and that the probability distribution of F is unitary invariant (because U acts isometrically on Hrns), therefore Theorem 27 applies.

For 1 i n, let ζ i P P n be a uniformly distributed random zero of f i . Concerning the number of continuation steps K, Theorem 27 gives (with C 1 " 5 given by Lemma 31)

Concerning the total number of operations, the cost of Algorithm "Solve" splits into the cost of the sampling and the cost of the numerical continuation. The former is Opn 4 `nD 4 q on average, by Proposition 39. As for the latter, the cost of a step is Opn 2 D 2 N q (Corollary 34), and we need Opn 4 D 2 q continuation steps on average; as N Ñ 8, that is Opn 6 D 4 N q operations, by Corollary 34. When minpn, Dq Ñ 8, then both n and D are `n`D n ˘op1q

" N op1q .