Random Polynomials and Approximate Zeros of Newton’s Method

Joel Friedman^{∗} Princeton University November 12, 1987

Contents

1 Introduction 2 2 Distances of Roots 4 3 The Uniform Root Distribution 6 4 Normally Distributed Coefficients 10 5 Uniform and Some Other Distributions 19 6 A Refined Estimate 32 7 Consequences of the Erdös-Turán Estimate 39 A Complex Random Variables 41 B Hammersley’s Formula 46

∗Part of the work was done at UC Berkeley, which was supported by an IBM (Yorktown Heights) fellowship and an IBM (Almaden) R.S.A.

1 Introduction

The goal of this paper is to give average case analyses of a randomized version of Newton’s method. For a function f: C → C we define Newton’s map

T_{f}(z) = z − \frac{f(z)}{f′(z)}.

z ∈ C is said to be an approximate zero of f (for Newton’s method) if the iterates of z, z_{0} = z, z_{1} = T_{f}(z_{0}), z_{2} = T_{f}(z_{1}),... converge to a root of f, ζ, and converge quickly enough so that

|z_{k} − z_{k−1}| ≤ (\frac{1}{2})^{2^{k−1}−1} |z_{1} − z_{0}| .

It is easy to see that the above condition implies

|z_{k} − ζ| ≤ \frac{7}{2} (\frac{1}{2})^{2^{k−1}} |z_{0} − ζ| .

The following α-test was proven in was proven independently in [Kim85] and [Sma86a]

Lemma 1.1 For some constant α_{0} > 0, α(f, z) < α_{0} implies that z is an approximate zero of f, where

α(f, z) ≡ \frac{|f(z)|}{|f′(z)|} sup_{k>1} |\frac{f^{(k)}(z)}{k!f′(z)}|^{\frac{1}{k−1}} .

Following [Sma86b], we consider the following randomized version of Newton’s method. For f ∈ P_{d}(1) = {f(z) = z^{d} +a_{1}z^{d−1} +⋯+a_{d} | |a_{i}| ≤ 1} choose z with |z| ≤ 3 at random and see if α(f, z) < α_{0}. If not, repeat the random choice until we find a z with α(f, z) < α_{0}. Then apply Newton’s method, which is known to converge very quickly, some small number of times. Since Newton’s method converges quickly there, the main cost of the algorithm will be the number of times needed to pick z’s until we find one with α(f, z) < α_{0} (times the cost of verifying this condition). Let

Λ_{f} ≡ {z ∈ C | α(f, z) < α_{0}},

and let

λ(f) ≡ \frac{|Λ_{f} ∩ B_{3}(0)|}{|B_{3}(0)|},

the density of Λ_{f} in B_{3}(0) with respect to Lebesgue measure. If z is chosen uniformly in B_{3}(0), then the expected time to a z with α(f, z) < α_{0} is 1/λ(f).

Let Q(ϵ) be the set of polynomials in P_{d}(1) with λ(f) < ϵ. View P_{d}(1) as a probability space with uniform distribution as a bounded subset of C^{d}. In [Sma86a] Smale proves

Pr {Q(ϵ)} < cd^{5}ϵ  (1.1)

for some absolute constant c. In this paper we use a different approach to estimate Pr {Q(ϵ)}, which gives estimates for various distributions of random polynomials. For uniform on P_{d}(1) we prove that for any integer N we have a c such that

Pr \{Q(ϵ)\} < c (ϵ^{2}d^{3} + (ϵ log \frac{1}{ϵ})^{\frac{N−1}{2}} d^{N} ) .

This shows that Pr {Q(ϵ)} decays like ϵ^{2} rather than ϵ, and that with arbitrarily high probability a function will have an approximate zero region of area > cd^{−2−β} for any β > 0 (as opposed to > cd^{−5} given by equation 1.1). For polynomials with roots chosen independently and uniformly in B_{1}(0) we get

Pr {Q(ϵ)} < (cϵd)^{d}.

The term approximate zero first appeared in [Sma81]. There Smale defined a weaker notion of approximate zero (exponential as opposed to doubly exponential convergence) and proved that an iterate of 0 under a relaxation of Newton’s method^{1} is an approximate zero (with bounds on how large an iterate). Related papers include [SS85] and [SS86]. Before that, double exponential convergence of Newton’s method was proven under conditions on the values of f and f′ at a point and of f′′ in a region; this was done by Kantorovich in [Kan52]; see also [KA70] and [GT74]. Independently, Kim in [Kim85] and Smale in [Sma86b] discovered the αtest. Kim used Schlicht function theory and obtained α_{0} = 1/54. Smale proved the α-test in the more general Banach space setting (e.g. Newton’s method for maps : C^{n} → C^{n}) and obtained α_{0} = .1307 . . .. Royden, in [Roy86], has recently improved the best known α_{0} value to .15767 … for maps C → C.

1Namely, T_{f,h} = z − h\frac{f′(z)}{f(z)} with 0 < h < 1.

Our method of proof obtains an estime of Pr {Q(ϵ)} in terms of the distribution of the roots, which is proven in §2^{2}. In §3 we apply this to the distribution on f where we take the roots to be chosen independently with uniform distribution.

In §4-7 we estimate Pr {Q(ϵ)} for f with coefficients chosen independently. This leads us to the problem of determining the distribution of the roots given independently chosen coefficients. This problem has received a lot of attention(see [BS86]), but most of it is concentrated on estimating the density function of one randomly chosen root of the polynomial (i.e. “the condensed distribution”). We are interested in the joint density of two or more roots. To do this we use a generalized formula of Hammersly (see [Ham60]) for the joint density of two or more roots. In §4 we calculate the joint density of two roots assuming the coefficients are distributed normally, and then prove a theorem about the density of approximate zeros. In §5 we show that if the coefficients are distributed uniformly similar results hold for the joint density of two roots and thus about the density of approximate zeros. These results also hold for a wider class of bounded distributions. In §6 we refine our estimate of Pr {Q(ϵ)} in §4-5 by estimating the joint density of three or more roots. In §7 we use an estimate of Erdös and Turán on the distribution of the roots to improve our Pr {Q(ϵ)} estimates further.

2 Distances of Roots

Lemma 2.1 Let x_{1},…, x_{d} be the roots of f. Let

r = \frac{1}{∑j>1 \frac{1}{|x_{j}−x_{1}|}} .

Then |z − x_{1}| < cr implies α(f, z) < α_{0} for some absolute constant c. Furthermore, Newton’s method starting at such a z converges to x_{1}.

2Independently, Rengar (see [Ren87]) has discovered such an estimate, though his is weaker by a factor of anywhere from d^{2} to d^{4}

Proof Consider g(y) = f(y − z) = ∑_{i=0}^{d} b_{i}y_{i}, which has roots x_{i} − z. We wish to bound

α(f, z) = |\frac{b_{0}}{b_{1}} | max_{k>1} |\frac{b_{k}}{b_{1}} |^{\frac{1}{k−1}} .

Consider h(y) = ∑_{i=0}^{d} b_{d−i}y^{i}. Since h(y) = y^{d}g(1/y), h has roots \frac{1}{x_{i}−z} and thus

∑_{i=0}^{d} b_{d−i}y^{i} = h(y) = b_{0} ∏_{i=1}^{d} (y − \frac{1}{x_{i} − z} ) .

Thus

b_{i} = (−1)^{i}b_{0} σ_{i}(\frac{1}{x_{1} − z} ,…, \frac{1}{x_{d} − z} )

where σ_{k} is the kth symmetric polynomial,

σ_{k}(w_{1},…, w_{d}) = ∑_{i_{1}<···<i_{k}} w_{i_{1}}w_{i_{2}} … w_{i_{d}}.

Now

σ_{k}(\frac{1}{x_{1} − z} ,…, \frac{1}{x_{d} − z} ) = σ_{k}(\frac{1}{x_{2} − z} ,…, \frac{1}{x_{d} − z} ) +

\frac{1}{x_{1} − z} σ_{k−1}(\frac{1}{x_{2} − z} ,…, \frac{1}{x_{d} − z} ) .

Since z ∈ B_{cr}(x_{1}) we have

\frac{c}{|x_{1} − z|} > ∑_{j>1} \frac{1}{|x_{j} − z|}.

Thus

|σ_{m}(\frac{1}{x_{2} − z} ,…, \frac{1}{x_{d} − z} )| ≤ (∑_{i=2}^{d} \frac{1}{|x_{i} − z|})^{m} ≤ (\frac{c}{|x_{1} − z|})^{m}

and

|σ_{m}(\frac{1}{x_{1} − z} ,…, \frac{1}{x_{d} − z} )| ≤ |σ_{m}(\frac{1}{x_{2} − z} ,…, \frac{1}{x_{d} − z} )|

+\frac{1}{|x_{1} − z|} |σ_{m−1}(\frac{1}{x_{2} − z} ,…, \frac{1}{x_{d} − z} )|

≤ \frac{c^{m} + c^{m−1}}{|x_{1} − z|^{m}} .

On the other hand

|σ_{1}(\frac{1}{x_{1} − z} ,…, \frac{1}{x_{d} − z} )| = |\frac{1}{x_{1} − z} + ⋯ + \frac{1}{x_{d} − z} |
≥ \frac{1}{|x_{1} − z|} − ∑_{i=2}^{d} \frac{1}{|x_{i} − z|}
≥ \frac{1 − c}{|x_{1} − z|}.

Hence

|\frac{b_{m}}{b_{1}} | ≤ \frac{c^{m} + c^{m−1}}{1 − c} \frac{1}{|x_{1} − z|^{m−1}}

and

|\frac{b_{0}}{b_{1}} | ≤ \frac{|x_{1} − z|}{1 − c}.

Thus

α(f, z) ≤ \frac{|x_{1} − z|}{1 − c} max_{k>1} (\frac{c^{k} + c^{k−1}}{1 − c} )^{\frac{1}{k−1}} \frac{1}{|x_{1} − z|}
= \frac{1}{1 − c} max_{k>1} c (\frac{1 + c}{1 − c})^{\frac{1}{k−1}} = \frac{c}{1 − c}\sqrt{\frac{1 + c}{1 − c}}.

And hence α(f, z) < α_{0} for appropriate choice of c.

3 The Uniform Root Distribution

We can use lemma 2.1 to estimate the measure of Q(ϵ) for various distributions on the set of degree d polynomials. In this section we illustrate this by carrying out such an estimate in a case where the roots are distributed independently. In this case we can apply lemma 2.1 without much difficulty. Consider the distribution on polynomials

f(z) = (z − x_{1}) … (z − x_{d})

with x_{1},…, x_{d} chosen independently, uniform in B_{1}(0) ⊂ C. We begin by proving Pr {Q(ϵ)} ≤ cdϵ for some c, and then we refine the argument to get Pr {Q(ϵ)} ≤ (cdϵ)^{d} for some c.

Theorem 3.1 Pr {Q(ϵ)} ≤ cdϵ for all ϵ for some absolute constant c.

Proof Viewing x_{1} as fixed, we have for any fixed j

Pr \{|x_{j} − x_{1}| < ρ\} = \frac{|B_{ρ}(0) ∩ B_{1}(0)|}{|B_{1}(0)|} ≤ ρ^{2}.

Thus, for any i_{1} < ⋯ < i_{k}, we have

Pr {|x_{i_{1}} − x_{1}|,…, |x_{i_{k}} − x_{1}| are ≤ ρ} ≤ ρ^{2k}.

Hence

Pr \{k of |x_{2} − x_{1}|, |x_{3} − x_{1}|,…, |x_{d} − x_{1}| are ≤ ρ\} ≤ \binom{d − 1}{k}ρ^{2k} ≤ (\frac{ed}{k})^{k} ρ^{2k},

(where \binom{d−1}{k} ≤ \binom{d}{k} ≤ (ed/k)^{k} was used) which is ≤ η/2^{k} if ρ ≤ \sqrt{\frac{k}{2ed}}η^{1/2k}. So if a_{1} ≤ … ≤ a_{d−1} are the |x_{2} − x_{1}|,…, |x_{d} − x_{1}| arranged in increasing order, we have

Pr \{a_{1} ≤ \sqrt{\frac{1}{2ed}}η^{1/2} or a_{2} ≤ \sqrt{\frac{2}{2ed}}η^{1/4} or … or a_{d−1} ≤ \sqrt{\frac{d − 1}{2ed}}η^{1/2(d−1)}\}

≤ \frac{η}{2} + \frac{η}{4} + ⋯ + \frac{η}{2^{d−1}} < η.

Hence with probability ≥ 1 − η we have

∑_{i=1}^{d−1} \frac{1}{a_{i}} ≤ \sqrt{2ed} ((\frac{1}{η} )^{1/2} + \frac{1}{\sqrt{2}} (\frac{1}{η} )^{1/4} + ⋯ \frac{1}{\sqrt{d − 1}} (\frac{1}{η} )^{1/2(d−1)}) . (3.1)

Lemma 3.2 N + \frac{1}{\sqrt{2}}N^{1/2} + ⋯ + \frac{1}{\sqrt{m}}N^{1/m} ≤ 2N + 4\sqrt{m} for N ≥ 4.

Proof Let t > 1 be the first integer for which N^{1/t} ≤ 2. Then t−1 ≤ log_{2} N and so

N + \frac{1}{\sqrt{2}}N^{1/2} + ⋯ + \frac{1}{\sqrt{t − 1}}N^{1/(t−1)} ≤ N + (t − 2)N^{1/2}
≤ N + (log_{2} N)N^{1/2} ≤ 2N

since log_{2} N ≤ N^{1/2} for N ≥ 4. Furthermore

\frac{1}{\sqrt{t}}N^{1/t} + ⋯ + \frac{1}{\sqrt{m}}N^{1/m} ≤ 2 (\frac{1}{\sqrt{2}} + ⋯ \frac{1}{\sqrt{m}})

≤ 2 ∫_{1}^{m} \frac{1}{\sqrt{x}} dx ≤ 4\sqrt{m}

and the lemma follows.

Applying lemma 3.2 to equation 3.1 yields that with probability ≤ 1−η,

∑_{i=1}^{d−1} \frac{1}{a_{i}} ≤ \sqrt{2πd}(2\sqrt{1/η} + 4\sqrt{d})

(for \sqrt{1/η} ≥ 4), and if 1/η ≥ d this gives

∑_{i=1}^{d−1} \frac{1}{a_{i}} ≤ \sqrt{2πd}(2\sqrt{1/η} + 2\sqrt{1/η}) ≤ \sqrt{8π}\sqrt{d/η}

and hence

\frac{1}{∑ \frac{1}{a_{i}}} ≥ c\sqrt{η/d}

for some constant c. Hence, by lemma 2.1, α(f, z) < α_{0} in a ball about x_{1} of area

c\frac{η}{d}.

Applying the arguments with x_{1} replaced by an arbitrary root, it follows that with probability ≥ 1 − dη, each root has α(f, z) ≤ α_{0} in a ball about it of area cη/d, for a total area of cη.

Lemma 3.3 The probability that there are d/2 roots each having k other roots within a distance δ is

≤ (δ^{2}d^{1+ \frac{1}{k}} /k)^{^{\frac{d}{2}}(1− \frac{1}{k+1})} .

Proof If there are d/2 roots each having k other roots within a distance δ, then for some distinct integers

i_{1}, i_{1}^{1}, i_{1}^{2},… i_{1}^{k}; i_{2}, i_{2}^{1},…, i_{2}^{k}; …; i_{j}, i_{j}^{1},… i_{j}^{k}

with j = d/2(k + 1) we have

x_{i_{n}^{m}} ∈ B_{δ}(x_{i_{n}}).  (3.2)

For any fixed set of integers this happens with probability

≤ (δ^{2})^{k \frac{d}{2(k+1)}} .

The number of ways of choosing a distinguished i_{1} and distinct set of size k, i_{1}^{1} < ⋯ < i_{1}^{k} is

d\binom{d − 1}{k} ≤ d (\frac{ed}{k})^{k} .

The total number of ways of choosing j such sets of integers is

≤ [d (\frac{ed}{k})^{k}]^{d/2(k+1)} = d^{d/2}(e/k)^{\frac{d}{2} \frac{k}{k+1}} .

Thus the probability that for some set of integers equation 3.2 holds is

≤ (δ^{2})^{\frac{d}{2} \frac{k}{k+1}} d^{d/2}(e/k)^{\frac{d}{2} \frac{k}{k+1}}
= (δ^{2}d^{1+ \frac{1}{k}} e/k)^{^{\frac{d}{2}}(1− \frac{1}{k+1})} .

Corollary 3.4 For any δ_{1},…, δ_{d−1} we have that with probability ≥ 1 − η_{1} − ⋯ − η_{d−1} the region of approximate zeros is

≥ \frac{d}{2}c (\frac{1}{∑ 1/δ_{k}} )^{2}

where

η_{k} = (δ_{k}^{2}d^{1+ \frac{1}{k}} e/k)^{^{\frac{d}{2}}(1− \frac{1}{k+1})} .

Proof This follows from lemma 2.1.

Take η_{k} = η/(d − 1) in corollary 3.4 so that

δ_{k} = \sqrt{\frac{k}{ed^{1+ \frac{1}{k}}}} ηk^{\frac{1}{d(1− \frac{1}{k+1})}}
≤ c\sqrt{\frac{1}{d}} \sqrt{\frac{k}{d^{1/k}}} η^{\frac{1}{d/2}} .

Lemma 3.5 \sqrt{d} + \sqrt{d^{1/2}/2} + \sqrt{d^{1/3}/3} + ⋯ + \sqrt{d^{(d−1)}/(d − 1)} = O (\sqrt{d}) .

Proof Since \sqrt{d^{1/x}/x} is monotone decreasing in x, we can estimate

\sqrt{d^{1/2}/2} + ⋯ + \sqrt{d^{1/(d−1)}/(d − 1)} ≤ ∫_{2}^{d} \sqrt{d^{1/x}/x} dx
≤ ∫_{2}^{d} \frac{1}{\sqrt{x}}e^{− \frac{log d}{2x}} dx
≤ [\sqrt{x}e^{− \frac{log d}{2x}} ]_{2}^{d} = O (\sqrt{d}) .

This gives us that with probablity ≥ 1 − η we have an area of

≥ c\frac{d}{2} (\sqrt{\frac{1}{d}}η^{\frac{1}{d/2}} \frac{c}{\sqrt{d}})^{2}
≥ cη^{\frac{1}{d}} .

Taking ϵ = cη^{1/d}/d, i.e. η = (ϵd/c)^{d} yields

Pr \{Q(ϵ)\} ≤ (\frac{ϵd}{c})^{d} .

4 Normally Distributed Coefficients

In the next sections we will estimate Pr {Q_{d}(ϵ)} for distributions in which the coefficients a_{i} of

f(z) = a_{d}z^{d} + ⋯ + a_{0}  (4.1)

are chosed independently with fixed distributions. In this section we consider the case in which the a_{i}’s are distibuted normally, i.e. ℜ(a_{i}) and ℑ(a_{i}) are independent random variables on R with density

ϕ(t) = \frac{1}{\sqrt{2π}} e^{−t^{2}/2}.

Here we have the problem that for any fixed value of d, there is some small probability that all the coefficients are large enough to enable B_{3}(0) to lie completely within a sink of period 2. Hence Pr {Q_{d}(0)} > 0 for each d; we cannot hope to prove Pr {Q_{d}(ϵ)} ≤ ϵd^{O(1)}. Instead, we shall prove

Pr {Q_{d}(ϵ)} ≤ c_{1}ϵ^{2}d^{7} + 2^{−c_{2}d},  (4.2)

the 2^{−c_{2}d} term taking Pr {Q_{d}(0))} > 0 into account.

We begin by noting that for d large the roots tend to be located on the circle of radius 1.

Lemma 4.1 (Specht) Let z_{1},…, z_{m} be roots of z^{n} + a_{n−1}z^{n−1} + ⋯ + a_{0}. Then

|z_{1} … z_{m}| ≤ \sqrt{1 + |a_{d−1}|^{2} + |a_{d−2}|^{2} + ⋯ + |a_{0}|^{2}}.

Proof See [Mar66].

Corollary 4.2 If less that d/2 of the roots of f(z) = a_{d}z^{d} + ⋯ + a_{0} have absolute value between 1/2 and 2 then either

\frac{1}{|a_{d}|}\sqrt{|a_{0}|^{2} + ⋯ + |a_{d}|^{2}} ≥ 2^{d/4}  (4.3)

or

\frac{1}{|a_{0}|}\sqrt{|a_{0}|^{2} + ⋯ + |a_{d}|^{2}} ≥ (1/2)^{−d/4} = 2^{d/4}.  (4.4)

Proof Either d/4 roots have absolute value > 2 or < 1/2. Apply lemma 4.1 to either \frac{1}{a_{n}} f(z) or \frac{1}{a_{0}} f(1/z)z^{d}.

Corollary 4.3 With probability ≥ 1 − 2^{cd} there are at least d/2 roots z in the range 1/2 ≤ |z| ≤ 2 for some constant c > 0.

Proof For equation 4.3 of equation 4.4 to hold, one of the a_{i}’s must be exponentially large or exponentially small (i.e. ≥ 2^{cd} or ≤ 2^{−cd}). For standard normal random variables, this occurs with probability ≤ 2^{−cd} for some c ≥ 0.

Next we deive a bound of the form Pr {|z_{1} − z_{2}| ≤ ϵ} ≤ O(ϵ^{4}) (O(ϵ^{4}) for fixed d) where z_{1}, z_{2} are randomly chosen roots of f(z) = a_{d}z^{d} + ⋯ + a_{0}. Constrasting this to Pr {|z_{1} − z_{2}| ≤ ϵ} = O(ϵ^{2}) when z_{1}, z_{2} are disributed independently and uniformly explains why in equation 4.2 we estimate Pr {Q(ϵ)} quadratically in ϵ rather than linearly (i.e. equation (3.1)).

In [Ham60], Hammersly gives a formula for the density function,^{3} P (z_{1}), of a randomly chosen root, z_{1}, of f(z) = a_{d}z^{d} + ⋯ + a_{0}. Viewing f(z_{1}) and f′(z_{1}), for z_{1} fixed, as sums of independent random variables (z_{1}^{d})a_{d}+⋯+a_{0} and (dz_{1}^{d−1})a_{d} + ⋯ + a_{1}, the formula for P can be written as

P (z_{1}) = \frac{1}{d} E \{|f′(z_{1})|^{2} subject to f(z_{1}) = 0\} ,

where by

E {|f′(z_{1})|^{2} s.t. f(z_{1}) = 0} ,

the expected value of |f′(z_{1})|^{2} subject to f(z_{1}) = 0, we mean

∫_{C} ψ(0, t)|t|^{2} dt

where ψ is the joint density function of f(z_{1}) and f′(z_{1}). One can generalize this formula to the joint density of k randomly chosen roots

P (z_{1},…, z_{k}) =

\frac{1}{d(d − 1) … (d − k + 1)} E \{|f′(z_{1})|^{2} … |f′(z_{k})|^{2} s.t. f(z_{1}) = ⋯ = f(z_{k}) = 0\};

see appendix B for the derivation. In particular

P (z_{1}, z_{2}) = \frac{1}{d(d − 1)} E \{|f′(z_{1})|^{2}|f′(z_{2})|^{2} s.t. f(z_{1}) = (z_{2}) = 0\} . (4.5)

We will estimate this expression for Δz = z_{2} − z_{1} with |Δz| ≤ 1/d^{5/4} (actually ≤ c/d for some constant c would give the same estimates) and \frac{1}{2} < |z_{i}| < 2.

For constants b_{0},…, b_{d} we can write the random variable ∑ b_{i}a_{i} as ⟨b, ā⟩, where b = (b_{0},…, b_{d}) ∈ C^{d+1}, ā = (ā_{0},…, ā_{d}) ∈ C^{d+1}, ¯ denoting complex conjugation, and ⟨ , ⟩ denotes the usual inner product on C^{d+1}. Analogous to sums of real normal random variables, one can easily verify that ⟨b, ā⟩ and ⟨b′, ā⟩ are independent random variables if ℜ ⟨b, b′⟩ = 0.

3Equivalently the chance of finding at least one root in B_{ϵ}(z_{1}) is dP (z_{1}) · πϵ^{2} + (lower order terms).

For i = 1, 2, let u_{i} denote (1, z_{i},…, z_{i}^{d}) ∈ C^{d+1} and v_{i} denote

v_{i} ≡ (0, 1, 2z_{i},…, dz_{i}^{d−1}) ∈ C^{d+1}.

Let ṽ_{i} be the projection of v_{i} onto (Cu_{1} + Cu_{2})^{⊥}, i.e.

ṽ_{i} = v_{i} − ∑_{j=1}^{2} \frac{⟨v_{i}, u_{j}⟩}{⟨u_{j}, u_{j}⟩}u_{j}.

We have

P (z_{1}, z_{2}) = \frac{1}{\binom{d}{2}} E \{| ⟨v_{1}, ā⟩ |^{2}| ⟨v_{2}, ā⟩ |^{2} s.t. ⟨u_{1}, ā⟩ = ⟨u_{2}, ā⟩ = 0\}

= \frac{1}{\binom{d}{2}} E \{| ⟨ṽ_{1}, ā⟩ |^{2}| ⟨ṽ_{2}, ā⟩ |^{2} s.t. ⟨u_{1}, ā⟩ = ⟨u_{2}, ā⟩ = 0\}

(since ⟨v_{j}, ā⟩ = ⟨ṽ_{j}, ā⟩ if ⟨u_{i}, ā⟩ = 0)

= \frac{1}{\binom{d}{2}} E \{| ⟨ṽ_{1}, ā⟩ |^{2}| ⟨ṽ_{2}, ā⟩ |^{2}\} ψ(0, 0)  (4.6)

by independence, where ψ is the joint density of ⟨u_{1}, ā⟩, ⟨u_{2}, ā⟩. Similar to the case of real normal random variables,

ψ(0, 0) = (\frac{1}{2π} )^{2} |det ( \begin{matrix}⟨u_{1}, u_{1}⟩ & ⟨u_{1}, u_{2}⟩ \\ ⟨u_{2}, u_{1}⟩ & ⟨u_{2}, u_{2}⟩ \end{matrix} )|^{−1} .

Add a note here giving a reference or explain real isomorphs of complex matrices. Letting Δu = u_{2} − u_{1}, we have

Δu = (z_{2} − z_{1})(0, 1, z_{1} + z_{2},…, z_{1}^{d−1} + z_{1}^{d−2}z_{2} + ⋯ + z_{2}^{d−1})
= Δz(0, 1, 2z_{1},…, dz_{1}^{d−1})(1 + O(d^{−1/4}))
= Δz v_{1}(1 + O(d^{−1/4}))

and so

|det ( \begin{matrix}⟨u_{1}, u_{1}⟩ & ⟨u_{1}, u_{2}⟩ \\ ⟨u_{2}, u_{1}⟩ & ⟨u_{2}, u_{2}⟩ \end{matrix} )| = |det ( \begin{matrix}⟨u_{1}, u_{1}⟩ & ⟨u_{1}, Δu⟩ \\ ⟨Δu, u_{1}⟩ & ⟨Δu, Δu⟩ \end{matrix} )|

= |Δz|^{2}(|u_{1}|^{2}|v_{1}|^{2}(1 + O(d^{−1/4})) − | ⟨u_{1}, v_{1}⟩ |^{2}(1 + O(d^{−1/4}))).

We have

|u_{1}|^{2} = 1 + |z_{1}|^{2} + ⋯ + |z_{1}|^{2d},
|v_{1}|^{2} = 1 + 4|z_{1}|^{2} + ⋯ + d^{2}|z_{1}|^{2d−2},
⟨u_{1}, v_{1}⟩ = z_{1}(1 + 2|z_{1}|^{2} + 3|z_{1}|^{4} + ⋯ + d|z_{1}|^{2d−2}),
| ⟨u_{1}, v_{1}⟩ |^{2} = |z_{1}|^{2}(1 + 2|z_{1}|^{2} + 3|z_{1}|^{4} + ⋯ + d|z_{1}|^{2d−2})^{2}.

Proposition 4.4 |u_{1}|^{2}|v_{1}|^{2}, | ⟨u_{1}, v_{1}⟩ |^{2}, and |u_{1}|^{2}|v_{1}|^{2} − | ⟨u_{1}, v_{1}⟩ |^{2} are each Θ(d^{4}) for 1 − (1/d) ≤ |z| ≤ 1 and Θ((1 − |z|^{2})^{−4}) for |z| ≤ 1 − (1/d). (For f to be Θ(g) means c_{1}g < f < c_{2}g for some constants c_{1} and c_{2}.)

Proof Let y = |z|^{2}. We have

|u_{1}|^{2}|v_{1}|^{2} = (1 + y + ⋯ + y^{d})(1 + 4y + ⋯ + d^{2}y^{d−1}),
| ⟨u_{1}, v_{1}⟩ |^{2} = y(1 + 2y + ⋯ + dy^{d−1})^{2},

and upon substraction

|u_{1}|^{2}|v_{1}|^{2} − | ⟨u_{1}, v_{1}⟩ |^{2} = 1 + \binom{4}{3}y + \binom{5}{3}y^{2} + ⋯ + \binom{d + 2}{3}y^{d−1} +
c_{d}y^{d} + c_{d+1}y^{d+1} + ⋯ + c_{2d−2}y^{2d−2},

where c_{d},…, c_{2d−2} are positive integers. If 1−(1/d) < |z| < 1, then we have e^{−2} ≤ |z|^{j} ≤ 1 for any j = 1,…, 2d − 1 and the aforementioned estimates easily follow. If |z| < 1 − (1/d), then the proposition follows using

∑_{i=0}^{d} i^{n}r^{i} and ∑_{i=0}^{∞} i^{n}r^{i} are both = Θ (\frac{1}{1 − r} )^{n}

for any n and any r < 1 − c/d for any fixed c (this latter condition ensures that the former sum has enough terms to approximate its limiting infinite sum).

Corollary 4.5

ψ(0, 0) ≤ \frac{c}{|Δz|^{2}} \{ \begin{matrix}d^{4} & if 1 − \frac{1}{d} ≤ |z_{1}| ≤ 1 \\ \frac{d^{2}}{(1−|z_{1}|^{2})^{4}} & if \frac{1}{2} ≤ |z_{1}| ≤ 1 − \frac{1}{d} \end{matrix}

To estimate

E {| ⟨ṽ_{1}, ā⟩ |^{2}| ⟨ṽ_{2}, ā⟩ |^{2}}

note that

u_{2} = u_{1} + (Δz)v_{1} + \frac{(Δz)^{2}}{2} w_{1}(1 + O(d^{−1/4}))

where

w_{1} = (0, 0, 2, 6z_{1},…, d(d − 1)z_{1}^{d−2}).

Hence

ṽ_{1} = (v_{1} − \frac{u_{2} − u_{1}}{Δz} ) = \frac{Δz}{2} w̃_{1}(1 + O(d^{−1/4}))

(where ˜ denotes the projection onto (Cu_{1} + Cu_{2})^{⊥}). Similarly we have

ṽ_{2} = \frac{Δz}{2} w̃_{1}(1 + O(d^{−1/4})).

So we estimate

E {| ⟨ṽ_{1}, ā⟩ |^{2}| ⟨ṽ_{2}, ā⟩ |^{2}} ≤ c(Δz)^{4}E {| ⟨w̃_{1}, ā⟩ |^{2}| ⟨w̃_{2}, ā⟩ |^{2}}

(where c is an absolute constant replacing (1 + O(d^{−1/4}))

≤ c(Δz)^{4} (E {| ⟨w̃_{1}, ā⟩ |^{4}} + E {| ⟨w̃_{1}, ā⟩ |^{4}})

by Schwartz’ inequality. To simplify estimating these fourth moments we use

Proposition 4.6 Let α, β, and γ be independent complex valued random variables with E {α^{i}ᾱ^{j}} = 0 for i ≠ j and similary for β and γ. Then

E {|α|^{4}} ≤ E {|α + β + γ|^{4}} .

Proof

E {|α + β + γ|^{4}} = E {(α + β + γ)^{2}(ᾱ + β̄ + γ̄)^{2}}

which, when expanded as sum of expectations of products has terms which are of the form E {δδ̄} > 0 or which drop out. One of these terms is E {α^{2}ᾱ^{2}}.

Since ⟨w_{1}, ā⟩ is the sum of the three independent, radially symmetric random variables ⟨w̃_{1}, ā⟩, α_{1} ⟨u_{1}, ā⟩, and α_{2} ⟨u_{2}, ā⟩ for appropriate α_{1}, α_{2}, we have

E {| ⟨w̃_{1}, ā⟩ |^{4}} ≤ E {| ⟨w_{1}, ā⟩ |^{4}} .

Now

E {| ⟨w_{1}, ā⟩ |^{4}} = E {|∑_{i=0}^{d} i(i − 1)z^{i−2}a_{i}|^{4}}
= ∑_{i,j,k,l} i(i − 1)j(j − 1)k(k − 1)l(l − 1)z^{i+j+k+l−8}E {a_{i}a_{j}ā_{k}ā_{l}} .

The only terms not vanishing in the latter sum are those for which either i = k, j = l, or i = l, j = k. By the symmetry of these conditions, and since the E {a_{i}a_{j}ā_{k}ā_{l}} are bounded, we can estimate the above sum by

≤ c ∑_{i,j} i^{4}j^{4}|z|^{2(i+j)−8} ≤ c′ ∑_{m=0}^{2d} m^{9}|z|^{2m−8}  (4.7)

where we have set m = i+j. If |z| < 1−(1/d), we can estimate equation 4.7 by using

∑_{i=0}^{∞} i^{9}r^{i} ≤ c (\frac{1}{1 − r} )^{10}

to get

E \{| ⟨w̃_{1}, ā⟩ |^{4}\} ≤ c (\frac{1}{1 − |z|^{2}} )^{10}

which gives O(d^{10}) or better for |z| in this range. For 1 − (1/d) ≤ |z| ≤ 1 we simply use |z|^{m} ≤ 1 in equation 4.7 to get

E {| ⟨w̃_{1}, ā⟩ |^{4}} ≤ c ∑_{m=0}^{2d} m^{9} ≤ c′d^{10}.

Summing up, we have Lemma 4.7

E \{| ⟨ṽ_{1}, ā⟩ |^{2}| ⟨ṽ_{2}, ā⟩ |^{2}\} ≤ c|Δz|^{4} \{ \begin{matrix}d^{10} & if 1 − \frac{1}{d} ≤ |z_{1}| ≤ 1 \\ (1 − |z_{1}|^{2})^{−10} & if \frac{1}{2} ≤ |z_{1}| ≤ 1 − \frac{1}{d} \end{matrix}

Combining lemma 4.7, corollary 4.5, and equation 4.6 yields Theorem 4.8

P (z_{1}, z_{2}) ≤ \frac{c}{d(d − 1)}(Δz)^{2} \{ \begin{matrix}d^{6} & if 1 − \frac{1}{d} ≤ |z_{1}| ≤ 1 \\ (1 − |z_{1}|^{2})^{−6} & if \frac{1}{2} ≤ |z_{1}| ≤ 1 − \frac{1}{d} \end{matrix}

Corollary 4.9 For 1 ≤ |z_{1}| ≤ 2, the same estimates, as in theorem 4.8, hold (with slightly different c and θ).

Proof Let y_{1} = 1/z_{1}, y_{2} = 1/z_{2}. Let P̃( , ) be the density of two random roots of

a_{0}y^{d} + a_{1}y^{d−1} + ⋯ + a_{d} = 0.  (4.8)

On the one hand, clearly P̃ = P. On the other hand, y satisfied equation 4.8 iff x = 1/y satisfies

a_{d}x^{d} + ⋯ + a_{0} = 0.

Thus

P (s, t) = P̃ (\frac{1}{s}, \frac{1}{t}) |\frac{∂(1/s, 1/t)}{∂(s, t)}|^{2}
= P̃ (\frac{1}{s}, \frac{1}{t}) \frac{1}{|st|^{4}}
= P (\frac{1}{s}, \frac{1}{t}) \frac{1}{|st|^{4}} .

Thus, since 1 ≤ |z_{1}|, |z_{2}| ≤ 2, we have

P (z_{1}, z_{2}) ≤ P (y_{1}, y_{2})\frac{1}{4^{4}} .

Since |y_{1} − y_{2}| ≤ c/d can be ensured by requiring |z_{1} − z_{2}| ≤ c′d, we can apply theorem 4.8 in this case to obtain the desired estimate (note that (1 − |z_{1}|)^{2} and (1 − |y_{1}|)^{2} differ from each other by some multiple in a bounded, positive range).

Lemma 4.10

Pr \{|z_{1} − z_{2}| ≤ δ and \frac{1}{2} ≤ |z_{1}| ≤ 2\} ≤ cδ^{4}d^{3}

Proof We have

∫_{t∈B_{2}(0)−B_{1/2}(0)} ∫_{s∈B_{δ}(t)} P (s, t) ds dt
≤ ∫_{t∈B_{2}(0)−B_{1/2}(0)} \frac{c}{d^{2}} δ^{4} \{ \begin{matrix}d^{6} & if 1 − \frac{1}{d} ≤ |t| ≤ 1 \\ (1 − |t|^{2})^{−6} & if \frac{1}{2} ≤ |t| ≤ 1 − \frac{1}{d} \end{matrix} \} dt. (4.9)

The integral in equation 4.9, over the range 1 − \frac{1}{d} ≤ |t| ≤ 1 + \frac{1}{d} is

≤ \frac{c}{d^{2}} δ^{4}d^{6} |B_{1+ \frac{1}{d}} (0) − B_{1− \frac{1}{d}} (0)|

= \frac{c}{d^{2}} δ^{4}d^{6} \frac{4π}{d} = c′δ^{4}d^{3}.

Over the range 1/2 ≤ |t| ≤ 1 − \frac{1}{d}, setting r = |t| the integral of equation 4.9 becomes

∫_{t} \frac{c}{d^{2}} δ^{4} (\frac{1}{1 − |t|^{2}} )^{6} dt = ∫_{r=1/2}^{1− \frac{1}{d}} \frac{c}{d^{2}} δ^{4} (\frac{1}{1 − r^{2}} )^{6} 2πr dr
= \frac{c′}{d^{2}} δ^{4} (1 − r^{2})^{−5}|_{1/2}^{1− \frac{1}{d}}
= \frac{c′}{d^{2}} δ^{4} [(\frac{2}{d} − \frac{1}{d^{2}} )^{−5} − (\frac{3}{4})^{−5}] ≤ c′′δ^{4}d^{3}.

Corollary 4.11 The probability that there is a root |z_{i}| with 1/2 ≤ |z_{i}| ≤ 2 for which there is some other root, |z_{j}| with |z_{i} − z_{j}| ≤ δ, is no more that cδ^{4}d^{5} for some constant c.

Proof For δ > d^{−5/4} the statement holds with c = 1. For δ ≤ d^{−5/4} we apply lemma 4.10 to each of the d(d−1) pairs of roots, z_{i}, z_{j}, i ≠ j; the total probability is no more than the sum of the d(d − 1) probabilities c′δ^{4}d^{3}.

Finally we arrive at our main theorem:

Theorem 4.12 For a_{i}’s distributed as independent standard normals,

Pr {Q_{d}(ϵ)} ≤ cϵ^{2}d^{7} + 2^{−c′d}

for some constants c, c′ > 0.

Proof By corollary 4.11 and corollary 4.3 we have that with probability ≥ 1 − cδ^{4}d^{3} − 2^{−c′d} we have at least d/2 of the roots z lying in the range 1/2 ≤ |z| ≤ 2 and each such root is separated from the others by a distance δ. By lemma 2.1 this guarentees for each of these d/2 roots an approximate zero region of area ≥ cδ^{2}/(d − 1)^{2}, for a total of ≥ cδ^{2}/d. Setting ϵ = cδ^{2}/d we get δ^{4}d^{5} = cϵ^{2}d^{7} and the theorem follows.

5 Uniform and Some Other Distributions

In this section we obtain estimates like those of the previous section for coefficients distributed independently according to some other distribution. We will assume the distribution is the uniform distribution in B_{1}(0) for a_{i} with i < d and a_{d} = 1. In fact, one can do the same estimates verbatum with a_{d} = 1 and for i < d taking a_{i} according to any distribution supported in B_{1}(0), possibly different for different i’s, which satisfy equation 5.3 for ℓ = 14 with uniform bounds on the m′_{i}s.

In Smale’s works, [Sma81] and [Sma86b], the polynomials a_{d}z^{d} +⋯+a_{0} are considered with a_{d} = 1 and a_{i} distributed uniformly in B_{1}(0) for i ≠ d. This has the advantage of guarenteeing that the roots lie in the ball of radius 2 (if |z| > 2, then clearly |z^{d}| > ∑_{i<d} |a_{i}z^{i}| if |a_{i}| ≤ 1 and so such a z cannot be a root of the polynomial). In contrast to the distribution of the previous section, (almost all) such polynomials have regions of approximate zeros in B_{3}(0), and we will obtain estimates of the form

Pr {Q(ϵ)} ≤ cd^{7}ϵ^{2}.  (5.1)

We begin by considering the probability measure on polynomials in which a_{d} = 1 and the remaining coefficients distributed uniformly in the unit ball, B_{1}(0); i.e. with density

ψ(z) = \{ \begin{matrix}1/π & for z ∈ B_{1}(0) \\ 0 & otherwise \end{matrix}

For the density ψ, we have its characteristic function, ψ̂, satisfies

|ψ̂(ξ)| ≤ \frac{k}{|ξ|} ∀ξ ∈ C  (5.2)

for some k, and

ψ̂(ξ) = 1 − m_{1}|ξ|^{2} − m_{2}|ξ|^{4} − ⋯ − m_{ℓ}|ξ|^{2ℓ} + O (|ξ|^{2ℓ+2})  (5.3)

for any ℓ (see appendix A).

It will be easier to have all the a_{i}’s radially symmetric, so we will take a_{d} to be distributed as

e^{2πiθ}

with θ uniform random variable in [0, 1]. We denote its characteristic function by

ψ̂_{1}(ξ) = E {e^{iℜ(⟨ξ,a_{d}⟩)}} .

For ψ̂_{1} we also have an expansion

ψ̂_{1}(ξ) = 1 − M_{1}|ξ|^{2} − M_{2}|ξ|^{4} −… − M_{ℓ}|ξ|^{2ℓ} + O (|ξ|^{2ℓ+2}) .

We begin by estimating P (z_{1}, z_{2}) for |z_{1} − z_{2}| small. As in the previous section, by |z_{1} − z_{2}| small it suffices to take |z_{1} − z_{2}| ≤ c|z_{1}|/d for some constant c, but we will only be applying the estimate when |z_{1} − z_{2}| ≤ c|z_{1}|d^{−5/4}; we will assume the latter for notational convenience.

To estimate P (z_{1}, z_{2}), from equation 4.5 we see that it suffices to estimate

E {|f′(z_{1})|^{4} s.t. f(z_{1}) = f(z_{2}) = 0} .  (5.4)

We can estimate it as

≤ \frac{c|Δz|^{2}}{d(d − 1)} ∫_{C} |t|^{4}Υ(0, 0, t) dt  (5.5)

where Υ is the joint density of

∑ a_{i}u_{i} , ∑ a_{i}v_{i} , ∑ a_{i}w_{i}  (5.6)

with

u_{i} = z_{1}^{i} , v_{i} = iz_{1}^{i−1} (1 + O(d^{−1/4})) , w_{i} = i(i − 1)z_{1}^{i−2} (1 + O(d^{−1/4})) .

Let ã_{i} be distributed as \sqrt{2m_{1}} times the standard normal distribution, and Ξ the distribution of

∑ ã_{i}u_{i} , ∑ ã_{i}v_{i} , ∑ ã_{i}w_{i}.  (5.7)

The main task of this section is to prove:

Theorem 5.1 There exist constants c and d_{0} independent of d, t, z_{1}, and z_{2} such that the following hold. For all z_{1} and z_{2} with |z_{1} − z_{2}| ≤ |z_{1}| (1 + O(d^{−5/4})), we have if d ≤ d_{0} or |z_{1}| ≤ \frac{1}{2} then

∫_{C} |t|^{4}Υ(0, 0, t) dt ≤ c,  (5.8)

if d > d_{0} and 1 − \frac{1}{d} ≤ |z_{1}| ≤ 1 + \frac{1}{d} then

Υ(0, 0, t) ≤ cΞ(0, 0, t) + cΞ(0, 0, t/2) + cd^{−15},  (5.9)

and if d > d_{0} and \frac{1}{2} ≤ |z_{1}| ≤ 1 − \frac{1}{d} then

Υ(0, 0, t) ≤ cΞ(0, 0, t) + cΞ(0, 0, t/2) + c(1 − |z_{1}|^{2})^{−12}.  (5.10)

This will give estimates on equation 5.5 and thus on equation 5.4 similar to those in §4.

For equation 5.8, notice that for any d_{0} there is a c such that for and d ≤ d_{0} or if |z_{1}| ≤ \frac{1}{2} we have

∫ |t|^{4}Υ(0, 0, t) dt = E {|∑ a_{i}w_{i}|^{4} s.t. ∑ a_{i}u_{i} = ∑ a_{i}v_{i} = 0}
≤ max |∑ a_{i}w_{i}|^{4} Υ(0, 0) ≤ c

where Υ(0, 0) is the joint density of ∑ a_{i}u_{i}, ∑ a_{i}v_{i} at (0, 0), since

∑ |a_{i}||v_{i}| ≤ ∑ |v_{i}|

which is bounded uniformly for such |z_{1}|, and

∑ a_{i}u_{i} = a_{0} + z_{1}a_{1} + ⋯
∑ a_{i}v_{i} = a_{1} + ⋯

so that

Pr {∑ a_{i}u_{i} ∈ B_{ϵ}(0) , ∑ a_{i}v_{i} ∈ B_{ϵ}(0)}
= Pr {a_{0} ∈ B_{ϵ}(l_{0}) , a_{1} ∈ B_{ϵ}(l_{1})}
≤ ϵ^{4},

where l_{0}, l_{1} are linear combinations of a_{2},… a_{d}, and so

Υ(0, 0) ≤ (\frac{1}{π} )^{2} .

Next we estimate Υ(0, 0, t) for 1 ≤ |z_{1}| ≤ 1 + \frac{1}{d}.

It will be convenient to rescale u, v, and w via

U_{i} ≡ \frac{u_{i}}{z_{1}^{d}} , V_{i} ≡ \frac{v_{i}}{dz_{1}^{d−1}} , W_{i} ≡ \frac{w_{i}}{d(d − 1)z_{1}^{d−2}} ,

and set

Y_{i} ≡ (U_{i}, V_{i}, W_{i}) ≈ z_{1}^{i−d} (1, \frac{i}{d}, \frac{i^{2}}{d^{2}} ) .

Note that |Y_{i}| ≤ c for some constant c independent of i and d. We will obtain estimates as in equation 5.9, with Ψ being the density of

∑ a_{i}U_{i} , ∑ a_{i}V_{i} , ∑ a_{i}W_{i}  (5.11)

and Φ the density of equation 5.11 with a_{i} replaced by ã_{i}.

Consider, for each j, (a_{j}U_{j}, a_{j}V_{j}, a_{j}W_{j}) ∈ C^{3} ≃ R^{6}. Since the characteristic function of a_{j} for j > d is

ψ̂(ξ) = E {e^{iℜ(ξā_{j})}} ,

the characteristic function of (a_{j}U_{j}, a_{j}V_{j}, a_{j}W_{j}) is

χ̃(η, σ, τ) = E \{e^{iℜ(η\overline{a_{j}uUj}+σ\overline{a_{j}V_{j}}+τ\overline{a_{j}W_{j}}} \}
= E \{e^{iℜ[(ηŪ_{j}+σV̄_{j}+τW̄_{j})\overline{a}_{j}]}\}
= ψ̂ (|ηŪ_{j} + σV̄_{j} + τW̄_{j}|) .

It follows that the characteristic function of the joint density of equation 5.6 is

Ψ̂ = ψ̂_{1} (|ηŪ_{j} + σV̄_{j} + τW̄_{j}|) ∏_{j=0}^{d−1} ψ̂ (|ηŪ_{j} + σV̄_{j} + τW̄_{j}|) ,

and its density is

Ψ(q, s, t) = (\frac{1}{2π} )^{6} ∫_{C^{3}} e^{−iℜ(qη̄+sσ̄+tτ̄)}Ψ̂(η, σ, τ) dη dσ dτ.

Let ξ = (η, σ, τ). Then

Ψ̂(ξ) = ψ̂_{1} (| ⟨ξ, Y_{d}⟩ |) ∏_{i=0}^{d−1} ψ̂ (| ⟨ξ, Y_{i}⟩ |) .

From equation 5.3 it follows that

ψ̂(ξ) = e^{−m_{1}|ξ|^{2}+m′_{2}|ξ|^{4}+···+m′_{7}|ξ|^{14}} + O (|ξ|^{16})

and

ψ̂_{1}(ξ) = e^{−M_{1}|ξ|^{2}+M′_{2}|ξ|^{4}+···+M′_{7}|ξ|^{14}} + O (|ξ|^{16})

for |ξ| small for some constants m′_{2},…, m′_{7} and M′_{2},…, M′_{7}. Let δ be a small positive number with 22δ ≤ 1. Let

B ≡ B_{d^{δ−1/2}}(0).

Let ω̂ be defined by

ω̂(ξ) = \{ \begin{matrix}e^{−m|ξ|^{2}+m′_{2}|ξ|^{4}+···+m′_{7}|ξ|^{14}} & for z ∈ B \\ 0 & otherwise \end{matrix} ,

and let ω̂_{1} be defined by replacing the m’s by M’s. Let Ω be given by

Ω̂(ξ) = ω̂_{1} (| ⟨ξ, Y_{d}⟩ |) ∏_{i=0}^{d−1} ω̂ (| ⟨ξ, Y_{i}⟩ |) .

Henceforth we will replace ϕ_{1} and ω_{1} by ψ and ω when we write our equations. It makes no difference in the analysis.

We reduce the study of Ψ to that of Ω.

Lemma 5.2 For some constant c we have for any z_{1} with 1 ≤ |z_{1}| ≤ 1+ \frac{1}{d},

|Ψ(0, 0, t) − Ω(0, 0, t)| ≤ cd^{−9} ∀t ∈ C.

Proof By the Fourier inversion formula,

|Ψ(0, 0, t) − Ω(0, 0, t)| ≤ (\frac{1}{2π} )^{6} ∫_{C^{3}} |[Ψ̂(ξ) − Ω̂(ξ)]e^{−iℜ⟨x,ξ⟩}| dξ
≤ (\frac{1}{2π} )^{6} ∫_{C^{3}} |Ψ̂(ξ) − Ω̂(ξ)| dξ

≤ (\frac{1}{2π} )^{6} [∫_{C^{3}−B} |Ψ̂(ξ)| dξ + ∫_{B} |Ψ̂(ξ) − Ω̂(ξ)| dξ] .  (5.12)

To estimate the second integral of equation 5.12, we have

∫_{B} |Ψ̂ − Ω̂| dξ = ∫_{B} |∏_{i=0}^{d} ψ̂(⟨ξ, Y_{i}⟩) − ∏_{i=0}^{d} ω̂(⟨ξ, Y_{i}⟩)| dξ

which, by lemma A.1, is

≤ ∫_{B} ∑ |ψ̂(⟨ξ, Y_{i}⟩) − ω̂(⟨ξ, Y_{i}⟩)| dξ ≤ c ∫_{B} ∑ |⟨ξ, Y_{i}⟩|^{16} dξ

which, by Cauchy-Schwartz and since the |Y_{i}| are bounded independent of i and d,

≤ c ∫_{B} ∑ |ξ|^{16} dξ ≤ c|B|d (d^{δ−1/2})^{16} = c (d^{δ−1/2})^{22} d
= cd^{22δ−10} ≤ cd^{−9}  (5.13)

since 22δ ≤ 1, where we have used the fact that |B_{r}(0)| = cr^{6} for balls in C^{3}.

To estimate the first integral of equation 5.12, let

D_{0} ≡ \{i ∈ Z : \frac{5}{6}d − 2 ≤ i < d\} ,
D_{1} ≡ \{i ∈ Z : \frac{3}{6}d − 1 ≤ i ≤ \frac{4}{6}d\} ,
D_{2} ≡ \{i ∈ Z : \frac{1}{6}d − 1 ≤ i ≤ \frac{2}{6}d\} .

Note that for d sufficiently large the D_{j}’s are disjoint and each D_{j} contains ≥ d/6 integers. Let d_{0} be an integer such that this is the case for d > d_{0}. This will be our d_{0} in theorem 5.1. We will use

Sublemma 5.3 Let i ∈ D_{0}, j ∈ D_{1}, k ∈ D_{2}. Then for each ξ ∈ C^{3}, either

| ⟨ξ, Y_{i}⟩ | , | ⟨ξ, Y_{j}⟩ | , or | ⟨ξ, Y_{k}⟩ | is ≥ c_{2}|ξ|

for some absolute constant c_{2} (independent of ξ and z_{1} with 1 ≤ |z_{1}| ≤ 1+\frac{1}{d}).

Proof This is an easy calulation. For d small one can use compactness in z_{1} ∈ B_{1+ \frac{1}{d}} (0) − B_{1}(0). For d large we have

Y_{i} ≈ z_{1}^{i−d}(1, θ, θ^{2})

with \frac{1}{6} − \frac{1}{d} ≤ θ ≤ \frac{2}{6}; note that z_{1}^{i−d} ∈ B_{1}(0) − B_{1/ϵ}(0) since |z_{1}|^{−d} ≥

(1 + \frac{1}{d})^{−d} ≥ 1/e. Similar estimates hold for Y_{j} and Y_{k} in which θ takes on a different range of values, leading to the desired estimate.

Let A = B_{2kc_{2}}(0) where c_{2} is the constant in lemma 5.3 and k is the constant in lemma 5.2. We write

∫_{C^{3}−B} |Ψ̂(ξ)| dξ = ∫_{C^{3}−A} |Ψ̂(ξ)| dξ + ∫_{A−B} |Ψ̂(ξ)| dξ.  (5.14)

In C^{3} − A we use

|Ψ̂(ξ)| = ∏_{i=0}^{d} |ψ̂(⟨ξ, Y_{i}⟩)| ≤ (\frac{k}{c_{2}|ξ|})^{d/6} ,

which follows from equation 5.2 and lemma 5.3, to obtain

∫_{C^{3}−A} |Ψ̂(ξ)| dξ ≤ ∫_{C^{3}−A} (\frac{k}{c_{2}|ξ|})^{d/6} dξ ≤ c (\frac{1}{2})^{d/6} .  (5.15)

In A − B, we take a constant k′′ with the property that

|ψ̂(ξ)| ≤ e^{−|ξ|^{2}k′′} ∀ξ ∈ A,

and estimate

|Ψ̂(ξ)| ≤ ∏_{i=0}^{d} e^{−k′′|⟨ξ,Y_{i}⟩|^{2}} ≤ e^{−k′′ \frac{d}{6} |ξ|^{2}c_{2}^{2}} = e^{−cd|ξ|^{2}}

so that

∫_{A−B} |Ψ̂(ξ)| dξ ≤ ∫_{A−B} e^{−cd|ξ|^{2}} dξ ≤ c′e^{−cd^{2δ}}.  (5.16)

Combining equations 5.12, 5.13, 5.14, 5.15, and 5.16 yields lemma 5.2. To deal with Ω, note that for ξ ∈ B,

Ω̂(ξ) = e^{−Q_{2}(ξ)−···−Q_{14}(ξ)},

where the Q_{i} are homogeneous polynomials of degree i in ξ = (η, σ, τ) given by

Q_{2k}(ξ) = ∑_{i=0}^{d} m′_{k} |⟨ξ, Y_{i}⟩|^{2k} ,

where m′_{1} = m_{1}. Note that

Q_{2}(ξ) ≥ m_{1}c_{2}^{2} \frac{d}{6}|ξ|^{2} ≥ cd|ξ|^{2}

and that

|Q_{2k}(ξ)| ≤ ∑_{i=0}^{d} m′_{k}|ξ|^{2k}|Y_{i}|^{2k} ≤ cd|ξ|^{2k}.

Expanding by power series we get

Ω̂(ξ) = e^{−Q_{2}(ξ)−···−Q_{14}(ξ)}
= e^{−Q_{2}(ξ)} (1 + R_{4}(ξ) + ⋯ + R_{14}(ξ)) + O (|ξ|^{16}) ,

where R_{k}(ξ) are homogeneous polynomials of degree 2k in ξ. Since

|Q_{2k}(ξ)| ≤ cd^{k/2}|ξ|^{2k}

for 2k ≥ 4, we have

|R_{2k}(ξ)| ≤ c′d^{k/2}|ξ|^{2k}  (5.17)

for some c′, and hence

|R_{2k}(ξ)| ≤ cd^{3}|ξ|^{2k}  (5.18)

for k = 2,…, 7 (in equation 5.17, we can replace fractional powers of d by the nearest lower integral power of d).

Let Θ be given by

Θ̂(ξ) = e^{−Q_{2}(ξ)} (1 + R_{4}(ξ) + ⋯ + R_{14}(ξ)) .

We finish the proof of lemma 5.2 with:

Lemma 5.4

|Ω(0, 0, t) − Θ(0, 0, t)| ≤ cd^{−9}.

Lemma 5.5

|Θ(0, 0, t)| ≤ cΦ(0, 0, t).

The proof of lemma 5.4 is the same as the proof of lemma 5.2. Note

∫_{C^{3}} |Ω̂ − Θ̂| dξ = ∫_{C^{3}−B} |Θ̂| dξ + ∫_{B} |Ω̂ − Θ̂| dξ.

Similar to the proof of lemma 5.2, we can estimate

∫_{B} |Ω̂ − Θ̂| dξ ≤ cd^{−9}

and estimate

∫_{C^{3}−B} |Θ̂| dξ ≤ ∫_{C^{3}−A} + ∫_{A−B}
≤ cd^{3} [(\frac{1}{2})^{d/6} + e^{−c′d^{2δ}}] ,

the d^{3} coming from equation 5.18.

The proof of lemma 5.5 is a straightforward calculation. We have

Φ̂(ξ) = ∏_{i=0}^{d} e^{−m_{1}|⟨ξ,Y_{i}⟩|^{2}} = e^{−Q_{2}(ξ)}.

It follows that

Θ(x) = (1 + R_{4} (i\frac{∂}{∂x}) + ⋯ + R_{14} (i\frac{∂}{∂x})) Φ(x).

Sublemma 5.6 Let B be an n × n, complex Hermitian matrix, and let

g(x) = e^{−⟨B^{−1}x,x⟩}.

Then for any muti-index α we have

|\frac{∂^{α}g}{∂x^{α}} (t)| ≤ ∥B^{−1}∥^{|α|/2} cg(t/2) ∀t

for some constant c = c(α, n) independent of B.

Proof Since B is Hermitian, it suffices to prove it assuming B is diagonal. To prove it for B diagonal it suffices to prove it for the one variable case. In the one variable case,

g(t) = e^{−t^{2}/b}

and

\frac{∂^{α}g}{∂x^{α}} (t) = (\frac{1}{b})^{|α|/2} P_{α} (\frac{t}{\sqrt{b}}) e^{−t^{2}/b}

where P_{α} is a polynomial of degree α. We have

P_{α} (\frac{t}{\sqrt{b}}) e^{− \frac{3}{4} t^{2}/b} < c(α)

for some constant c(α) for each α, and thus the sublemma follows. Taking B to be the matrix given by

⟨Bξ, ξ⟩ = Q_{2}(ξ)

we get that since Q_{2}(ξ) ≥ cd|ξ|^{2} that ∥B^{−1}∥ ≤ c/d and thus

R_{2k} (i\frac{∂}{∂x}) Φ(x) ≤ cd^{k/2} |(i\frac{∂}{∂x})^{2k} Φ(x)| ≤ cd^{k/2}d^{−k}Φ(x/2)

for k ≥ 2 and lemma 5.5 follows.

Combining lemmas 5.4, 5.5, and 5.2 we get

Ψ(0, 0, t) ≤ cΦ(0, 0, t) + cΦ(0, 0, t/2) + cd^{−9}

for all t for some c for 1 ≤ |z_{1}| ≤ 1+ \frac{1}{d}. Changing from U_{i}, V_{i}, W_{i} to u_{i}, v_{i}, w_{i} sums yields the desired estimate.

The same estimates hold for 1 − \frac{1}{d} ≤ |z_{1}| ≤ 1. One can see this directly, or by using the same trick as in corollary 4.9.

Next we estimate for \frac{1}{2} ≤ |z_{1}| ≤ 1 − \frac{1}{d}. Let m be the largest integer such that

|z_{1}|^{m} ≥ \frac{1}{2}.

We remark that

m = θ(− log |z_{1}|) = θ(1 − |z_{1}|) = θ(1 − |z_{1}|^{2})

(where f = θ(g) means c_{1}g ≤ f ≤ c_{2}g for some positive constants c_{1} and c_{2}). We claim that

Υ(0, 0, t) ≤ cΞ(0, 0, t) + cΞ(0, 0, t/2) + cm^{−12}

which is the same as equation 5.10. To see this we go through estimates similar to those for 1 ≤ |z_{1}| ≤ 1 + \frac{1}{d}. We rescale

U_{i} ≡ u_{i} , V_{i} ≡ \frac{z_{1}v_{i}}{m} , W_{i} ≡ \frac{z_{1}^{2}w_{i}}{m^{2}}

and let

Y_{i} = (U_{i}, V_{i}, W_{i}).

Then we have

|Y_{i}| ≤ ce^{−c′(i/m)}

for positive constants c and c′ independent of i and z_{1}. We define Ψ and Φ as before. Set

B ≡ B_{m^{δ−1/2}}(0)

and define ω and Ω as before. As before we get

|Ψ(0, 0, t) − Ω(0, 0, t)| ≤ cm^{−9}

using

∑_{i=0}^{d} |Y_{i}|^{16} ≤ c ∑_{i=0}^{d} |z_{1}|^{16i} ≤ c ∑_{i=0}^{∞} |z_{1}|^{16i} ≤ cm.

Next let

D_{0} ≡ {i ∈ Z : m ≤ i ≤ 2m} ,
D_{1} ≡ {i ∈ Z : 3m ≤ i ≤ 4m} ,
D_{2} ≡ {i ∈ Z : 5m ≤ i ≤ 6m} .

Then sublemma 5.3 holds for these D_{0}, D_{1}, D_{2}. Defining Θ and Q_{i} and R_{i} as before we have

Q_{2}(ξ) ≥ cm|ξ|^{2}

and

|Q_{2k}(ξ)| ≤ cm|ξ|^{2k}

and all the estimates go through as before to yield

Ψ(0, 0, t) ≤ cΨ(0, 0, t) + cΨ(0, 0, t/2) + cm^{−9}.

Upon rescaling to get Υ and Ξ we get the desired result.

Corollary 5.7 If |z_{1} − z_{2}| ≤ |z_{1}|O (d^{−5/4}), then we have

P (z_{1}, z_{2}) ≤ \frac{c}{d(d − 1)}(Δz)^{2} \{ \begin{matrix}d^{6} & if 1 − \frac{1}{d} ≤ |z_{1}| ≤ 1 + \frac{1}{d} \\ (1 − |z_{1}|^{2})^{−6} & for other |z_{1}| ∈ [0, 2] \end{matrix} .

(5.19)

Proof If 1 − \frac{1}{d} ≤ |z_{1}| ≤ 1 + \frac{1}{d} then

| ∑ a_{i}w_{i}| ≤ c ∑ |w_{i}| ≤ cd^{3}

so that Υ(0, 0, t) = 0 for |t| > cd^{3} and so

∫ Υ(0, 0, t)|t|^{4} dt = ∫_{B_{cd^{3}}(0)} Υ(0, 0, t)|t|^{4} dt
≤ c ∫_{B_{cd^{3}}(0)} (Ξ(0, 0, t) + Ξ(0, 0, t/2) + d^{−12}) |t|^{4} dt
≤ c ∫_{C} (Ξ(0, 0, t) + Ξ(0, 0, t/2)) |t|^{4} dt + cd^{6}

and using the estimates on Ξ in §4 the above is

≤ cd^{6}.

For \frac{1}{2} ≤ |z_{1}| ≤ 1 − \frac{1}{d} we have

∑ |w_{i}| ≤ cm^{3}

and the same estimates as before yield the theorem. For 1 + \frac{1}{d} ≤ |z_{1}| ≤ 2 we use the same trick as in corollary 4.9 and note that the same estimates hold for 1/z_{1} and the equation

∑_{i=0}^{d} a_{d−i}z^{i} = 0

(note that the fact that a_{d} = 1 doesn’t affect the estimates since D_{0}, D_{1}, D_{2} never contain a_{0} or a_{d}). For 0 ≤ |z_{1}| ≤ \frac{1}{2} we use theorem 5.1 to get the desired result.

We can finally prove

Theorem 5.8

Pr {Q_{d}(ϵ)} ≤ cϵ^{2}d^{7}.

Proof By integrating corollary 5.7 as in §4 we get that for any constant k there is a constant c such that

Pr {|z_{1} − z_{2}| ≤ δ and kδd^{5/4} ≤ |z_{1}| ≤ 2} ≤ cδ^{4}d^{3}.

We need |z_{1}| ≥ kδd^{5/4} to apply corollary 5.7. By lemma 4.1 we see that for f(z) to have ≥ d/2 roots of absolute value ≤ kδd^{5/4} would imply

(kδd^{5/4})^{d/2} ≤ \frac{1}{|a_{0}|}\sqrt{|a_{0}|^{2} + ⋯ + |a_{d}|^{2}} ≤ \frac{d + 1}{|a_{0}|}

so that

|a_{0}| ≤ \frac{d + 1}{(kδd^{5/4})^{d/2}}

which happens with probabilty

≤ \frac{cd^{2}}{(kδd^{5/4})^{d}}

which is dominated by δ^{2}d^{5} if δ < d^{−5/4} and if we take, say, k = \frac{1}{2}. Thus the probability that some root in B_{2}(0) − B_{kδd^{5/4}}(0) is within δ of another or that there are less that d/2 roots in B_{2}(0) − B_{kδd^{5/4}}(0) is ≤ cδ^{4}d^{5}. When this is not the case then lemma 2.1 guarentees a total approximate zero region of area ≥ c′δ^{2}d. Setting ϵ = c′′δ^{2}/d yields the theorem.

6 A Refined Estimate

In this section improve the estimates of the previous two sections by considering the joint density of three or more roots, similar to the latter part of §3.

Theorem 6.1 Let z_{1},…, z_{k} ∈ C satisfy |z_{i} − z_{1}| = |z_{1}|O(d^{−1−β}) for some fixed β. Then

P (z_{1},…, z_{k}) ≤ \frac{c}{d(d − 1) … (d − k + 1)} ∏_{i<j} |z_{j} − z_{i}|^{2}

\{ \begin{matrix}d^{k(k+1)} & if 1 − \frac{1}{d} ≤ |z_{1}| ≤ 1 + \frac{1}{d} \\ (1 − |z_{1}|)^{−k(k+1)} & for other |z_{1}| ∈ [0, 2] \end{matrix} . (6.1)

Proof The calculations are similar to the ones done in §4 and §5. We wish to estimate

E {|f′(z_{1})|^{2} … |f′(z_{k})|^{2} s.t. f(z_{1}) = … = f(z_{k}) = 0} .

As in theorem 5.1, it suffices to prove the theorem for \frac{1}{2} ≤ |z_{1}| ≤ 1 and d sufficiently large; for 0 ≤ |z_{1}| ≤ \frac{1}{2} and small d the theorem will be clear from the estimates used elsewhere and the bounded sums of the linear combinations of the a_{i}’s involved, and for 1 ≤ |z_{1}| ≤ 2 we have that the 1/z_{i}’s satisfy the equation with coefficients reversed and the \frac{1}{2} ≤ |z_{1}| ≤ 1 estimates can be invoked.

For convenience, let

m = \{ \begin{matrix}d & if 1 − \frac{1}{d} ≤ |z_{1}| ≤ 1 \\ ⌊− log_{2} |z_{1}|⌋ & if \frac{1}{2} ≤ |z_{1}| < 1 − \frac{1}{d} \end{matrix} ,

where ⌊a⌋ denotes the largest integer ≤ a.

We first deal with the case of a_{i} being distributed normally. It suffices to estimate

E {|F (z_{1})|^{2} … |F (z_{k})|^{2}}

and

ψ(0,…, 0)

where ψ is the density of f(z_{1}),…, f(z_{k}) and where F (z_{i}) is the random variable f′(z_{i})’s projection in (Cf(z_{1}) + ⋯ + Cf(z_{k}))^{⊥}.

For the latter, note that setting

u_{i} = (1, z_{i}, z_{i}^{2},…, z_{i}^{d})

we have, first of all,

u_{1} = (1, z_{1},…, z_{1}^{d}).

Secondly, if we set u′_{j} = \frac{u_{j}−u_{1}}{z_{j}−z_{1}} for j > 1, then we have

u′_{2} = (0, 1, 2z_{1},…, dz_{1}^{d−1}) (1 + O(d^{−β})) .

Next, if we set u′′_{j} = \frac{u′_{j}−u′_{2}}{z_{j}−z_{2}} for j > 2, then we have

u′′_{3} = (0, 0, 2, 6z_{1},…, d(d − 1)z_{1}^{d−2}) (1 + O(d^{−β})) .

Continuing in this fashion, we see that

det ( \begin{matrix}⟨u_{1}, u_{1}⟩ & ⋯ & ⟨u_{1}, u_{k}⟩ \\ ⋮ & ... & ⋮ \\ ⟨u_{k}, u_{1}⟩ & ⋯ & ⟨u_{k}, u_{k}⟩ \end{matrix} )

= ∏_{j>i}(z_{j} − z_{i})^{2} det ( \begin{matrix}⟨u_{1}, u_{1}⟩ & ⟨u_{1}, u′_{1}⟩ & ⋯ & ⟨u_{1}, u_{1}^{(k−1)}⟩ \\ ⟨u′_{1}, u_{1}⟩ & ⟨u′_{1}, u′_{1}⟩ & ⋯ & ⟨u′_{1}, u_{1}^{(k−1)}⟩ \\ ⋮ & ⋮ & ... & ⋮ \\ ⟨u_{1}^{(k−1)}, u_{1}⟩ & ⟨u_{1}^{(k−1)}, u′_{1}⟩ & ⋯ & ⟨u_{1}^{(k−1)}, u_{1}^{(k−1)}⟩ \end{matrix} )

where

u_{1}^{(j)} = (0,…, 0, j!,…, d(d − 1) … (d − j + 1)z_{1}^{d−j}) (1 + O(d^{−β})) .

We claim that

det ( \begin{matrix}⟨u_{1}, u_{1}⟩ & ⟨u_{1}, u′_{1}⟩ & ⋯ & ⟨u_{1}, u_{1}^{(k−1)}⟩ \\ ⟨u′_{1}, u_{1}⟩ & ⟨u′_{1}, u′_{1}⟩ & ⋯ & ⟨u′_{1}, u_{1}^{(k−1)}⟩ \\ ⋮ & ⋮ & ... & ⋮ \\ ⟨u_{1}^{(k−1)}, u_{1}⟩ & ⟨u_{1}^{(k−1)}, u′_{1}⟩ & ⋯ & ⟨u_{1}^{(k−1)}, u_{1}^{(k−1)}⟩ \end{matrix} ) ≥ cm^{k^{2}}. (6.2)

If we expand the above determinant into a sum of products of the entries of the matrix, each entry has size proportional to m^{k^{2}}. It suffices to show that equaiton 6.2 with the u_{1}^{(j)} replaced by

v_{j} = (0,…, 0, j!,…, d(d − 1) … (d − j + 1)z_{1}^{d−j})

(i.e. the old u_{1}^{(j)}’s without the error term (1 + O(d^{−β}))). Next note that

det ( \begin{matrix}⟨v_{0}, v_{0}⟩ & ⋯ & ⟨v_{0}, v_{k−1}⟩ \\ ⋮ & ... & ⋮ \\ ⟨v_{k−1}, v_{0}⟩ & ⋯ & ⟨v_{k−1}, v_{k−1}⟩ \end{matrix} ) = det ( \begin{matrix}⟨v_{0}, v_{0}⟩ & ⟨v_{0}, ṽ_{1}⟩ & ⋯ & ⟨v_{0}, ṽ_{k−1}⟩ \\ ⟨ṽ_{1}, v_{0}⟩ & ⟨ṽ_{1}, ṽ_{1}⟩ & ⋯ & ⟨ṽ_{1}, ṽ_{k−1}⟩ \\ ⋮ & ⋮ & ... & ⋮ \\ ⟨ṽ_{k−1}, v_{0}⟩ & ⟨ṽ_{k−1}, ṽ_{1}⟩ & ⋯ & ⟨ṽ_{k−1}, ṽ_{k−1}⟩ \end{matrix} )

= ⟨v_{0}, v_{0}⟩ ⟨ṽ_{1}, ṽ_{1}⟩… ⟨ṽ_{k−1}, ṽ_{k−1}⟩

where ṽ_{j} is the projection of v_{j} onto (Cv_{0} + ⋯ + Cv_{j−1})^{⊥}, i.e.

ṽ_{j} = v_{j} − ∑_{i=0}^{j−1} \frac{⟨v_{j}, v_{i}⟩}{⟨v_{i}, v_{i}⟩}v_{i}.

Lemma 6.2 For any n there exist c, d_{0} > 0 such that for any d > d_{0} and α_{1},…, α_{n} we have

|t^{n} − α_{1}t^{n−1} − ⋯ − α_{n}| ≥ cd^{n}  (6.3)

for at least d/4 of the integers t = 1, 2,…, d.

Proof We can write

t^{n} − α_{1}t^{n−1} − ⋯ − α_{n} = (t − γ_{1}) … (t − γ_{n})

for some γ_{i} ∈ C. For each i we have

|t − γ_{i}| ≥ |ℜ(t − γ_{i})| ≥ \frac{1}{9n}d

for all integers t, \frac{d}{2} − 1 ≤ t ≤ d, except for possibly \frac{2}{9n}d + 1 values of t. If d is sufficiently large we have

\frac{2}{9n}d + 1 ≤ \frac{1}{4n}d,

and thus for d/4 values of t, \frac{d}{2} − 1 ≤ t ≤ d, we have

|t^{n} − α_{1}t^{n−1} − ⋯ − α_{n}| ≥ cd^{n}

where c = 1/(9n)^{n}.

Corollary 6.3 For any k there is a c > 0 such that

⟨ṽ_{j}, ṽ_{j}⟩ ≥ cm^{2j+1}  (6.4)

for j = 0, 1,…, k − 1. Proof We have

⟨ṽ_{j}, ṽ_{j}⟩ = ∑_{i=j}^{d} |i^{j} − α_{1}i^{j−1} − ⋯ − α_{j}|^{2}|z_{1}|^{2(i−j)}

for some α_{1},…, α_{j}. For sufficiently large d we can estimate this sum as

≥ ∑_{\frac{m}{2} −1≤i≤m}(ci^{j})^{2}|z_{1}|^{2m} ≥ c′m^{2j+1}.

Corollary 6.3 establishes equation 6.2, and thus

ψ(0,…, 0) ≤ c |∏_{j>i}(z_{j} − z_{i})^{2} d^{1+3+···+(2k+1)}|^{−1}
= c |∏_{j>i}(z_{j} − z_{i})^{2} d^{k^{2}} |^{−1} .

To estimate

E {|F (z_{1})|^{2} … |F (z_{k})|^{2}}

we notice that the equations

\frac{f(z_{j}) − f(z_{1})}{z_{j} − z_{1}} = f′(z_{1}) + \frac{z_{j} − z_{1}}{2} f′′(z_{1}) + ⋯ + \frac{(z_{j} − z_{1})^{k−2}}{(k − 1)!} f^{(k−1)}(z_{1})
+ \frac{(z_{j} − z_{1})^{k−1}}{k!} f^{(k)}(z_{1}) (1 + O(d^{−β}))

enables us to write

|f′(z_{1}) − L| ≤ c (∏_{j>1} |z_{j} − z_{1}|) |f^{(k)}(z_{1})|

where L is a linear combination of f(z_{1}),…, f(z_{n}). This is true because the linear combination of the above k − 1 equations which eliminates the f′′(z_{1}),…, f^{(k−1)}(z_{1}) terms and gives an f′(z_{1}) term with coefficient 1 on the right hand side is the linear combination gotten by taking α_{j} times the z_{j} equation and adding them, where the α_{j}’s satisfy

( \begin{matrix}1 & ⋯ & 1 \\ \frac{z_{2}−z_{1}}{2} & ⋯ & \frac{z_{k}−z_{1}}{2} \\ ⋮ & ... & ⋮ \\ \frac{(z_{2}−z_{1})^{k−2}}{(k−1)!} & ⋯ & \frac{(z_{k}−z_{1})^{k−2}}{(k−1)!} \end{matrix} ) ( α_{2} ; α_{3} ; ⋮ ; α_{k} ) = ( 1 0 0 ⋮ 0 ) .

Using Kramer’s rule and solving van der Monde determinants yields

α_{i} = ∏_{j≠i,1} \frac{z_{j} − z_{1}}{z_{j} − z_{i}} .

The f^{(k)}(z_{1}) term in the linear combination therefore has coefficient

\frac{1}{k!} ∑_{i>1}(z_{i} − z_{1})^{k−1} ∏_{j≠i,1} \frac{z_{j} − z_{1}}{z_{j} − z_{i}}

= \frac{1}{k!} (∏_{i>1}(z_{i} − z_{1})) ∑_{i>1} \frac{(z_{i} − z_{1})^{k−2}}{∏_{j≠i,1}(z_{j} − z_{i})}
= \frac{1}{k!} (∏_{i>1}(z_{i} − z_{1})) 1

since

∑_{i>1} \frac{(z_{i} − z_{1})^{k−2}}{∏_{j≠i,1}(z_{j} − z_{i})} = \frac{∑_{i>1} [(−1)^{i+1}(z_{i} − z_{1})^{k−2} ∏_{1<n<l, n,l≠i}(z_{l} − z_{n})]}{∏_{1<n<l}(z_{l} − z_{n})}

= 1 since the numerator is a polynomial, with the same z_{i}^{k−2} ∏_{1<n<l, n,l≠i}(z_{l}− z_{n}) coefficient as in ∏_{1<n<l}(z_{l} − z_{n}), and the numerator vanishes whenever z_{l} = z_{n} for some l ≠ n.

Hence we may write

E {|F (z_{1})|^{2} … |F (z_{k})|^{2}} ≤ c (∏_{j>i} |z_{j} − z_{i}|^{4}) E {|f^{(k)}(z_{1})|^{2} … |f^{(k)}(z_{k})|^{2}}

where the analogue of proposition 4.6 for 2kth powers was used, and by Minkowski’s inequality the above is

≤ c (∏_{j>i} |z_{j} − z_{i}|^{4}) ∑_{i=1}^{k} E {|f^{(k)}(z_{i})|^{2k}}

≤ c (∏_{j>i} |z_{j} − z_{i}|^{4}) m^{k+2k^{2}},

the bound on E {|f^{(k)}(z_{i})|^{2k}} coming from expanding the expression as in equation 4.7 and the preceding equation. Combining the above and the estimate on ψ(0,…, 0) yields

E {|f′(z_{1})|^{2} … |f′(z_{k})|^{2} s.t. f(z_{1}) = … = f(z_{k}) = 0} ≤ c ∏_{j>i} |z_{j}−z_{i}|^{2} m^{k(k+1)}

which gives the desired result.

For the a_{i}’s distributed uniformly, we do the same estimates as in §5. From the above discussion we see that it suffices to estimate

∫_{C} |t|^{2k}Υ(0,…, 0, t) dt

where Υ is the joint density of ∑ a_{i}u_{i}, ∑ a_{i}v_{i}, ..., ∑ a_{i}s_{i} with

u_{i} = z_{1}^{i},
v_{i} = iz_{1}^{i−1} (1 + O(d^{−β})) ,
⋮
s_{i} = i(i − 1) … (i − k + 1)z_{1}^{i−k} (1 + O(d^{−β})) .

From here the arguments are just like those in §5.

Corollary 6.4 The probability that there are k roots within distance δ ≤ d^{−1−β} of each other in B_{2}(0) − B_{δd^{−1−β}}(0) is

≤ cδ^{k^{2}+k−2}d^{k^{2}+k−1}.

Proof By integrating theorem 6.1

Applying corollary 6.4 to the case of k = 1 and to some other value of k yields that each root in B_{2}(0) − B_{max(δ_{1},δ_{2})d^{−1−β}}(0) has no roots within a distance δ_{1} and at most k − 1 roots within a distance δ_{2} with probability ≥ 1 − τ_{1} + τ_{2}, where

cδ_{1}^{4}d^{5} = τ_{1}

and

c′δ_{2}^{k^{2}+k−2}d^{k^{2}+k−1} = τ_{2}.

If we have at least d/2 such roots we get an approximate zero region of area

≥ cd ( \frac{1}{\frac{k−1}{δ_{1}} + \frac{d−k}{δ_{2}}} )^{2} ≥ cd min(δ_{1}^{2}, \frac{δ_{2}^{2}}{d}).

Setting ϵ = dδ_{1}^{2} = δ_{2}^{2}/d yields

τ_{1} = cϵ^{2}d^{3}, τ_{2} = cd(ϵd^{3})^{\frac{k^{2}+k−2}{2}} .

The probability of having < d/2 roots in B_{2}(0) − B_{max(δ_{1},δ_{2})d^{−1−β}}(0) can be estimated as in the proof of theorem 5.8 and is dominated by τ_{1} +τ_{2}. Hence we can replace the

ϵ^{2}d^{7}

term in equations 4.2 and 5.1 by

ϵ^{2}d^{3} + ϵ^{\frac{k^{2}+k−2}{2}} d^{\frac{3k^{2}+3k−4}{2}} .

We summarize the improved results:

Theorem 6.5 For any fixed N ≥ 2, there are positive constants c and c′ such that

Pr {Q_{d}(ϵ)} ≤ c (ϵ^{2}d^{3} + ϵ^{N}d^{3N+1}) + 2^{−c′d}

if the a_{i}’s are normally distributed, and

Pr {Q_{d}(ϵ)} ≤ c (ϵ^{2}d^{3} + ϵ^{N}d^{3N+1})

if the a_{i}’s are uniform.

7 Consequences of the Erdös-Turán Estimate

In this section we give two types of improvements of the previous estimates using the following theorem of Erdös and Turán:

Lemma 7.1 Let N(α, β) be the number of roots of ∑_{i=0}^{d} a_{i}z^{i} = 0 of the form re^{iθ} with r, θ real and α ≤ θ ≤ β (and β − α ≤ 2π). Then

|N(α, β) − \frac{(β − α)d}{2π}| ≤ 16\sqrt{d log \frac{∑_{i=0}^{d} |a_{i}|}{|a_{0}||a_{d}|}}.

Proof See [ET50].

We will now argue assuming the a_{i}’s are distributed uniformly in B_{1}(0). The same estimates hold for the a_{i}’s distributed normally, with minor modifications in the arguments. From the above it follows that with probability ≥ 1 − τ we have |a_{0}| is > c\sqrt{τ} and thus

|N(α, β) − \frac{(β − α)d}{2π}| ≤ c\sqrt{d log \frac{d}{\sqrt{τ}}} .

This implies that the k-th closest root to a given root, z, has distance

≥ c′ \frac{k − c\sqrt{d log \frac{d}{\sqrt{τ}}}}{d} |z|.

By lemma 4.1 we have that more than d/2 of the roots lying in B_{ρ}(0) implies

|a_{0}| ≤ ρ^{d/2}

so that

ρ ≥ (\frac{τ}{π} )^{1/d} .

If follows that with probability ≥ 1 − τ − τ_{1} − τ_{2} we have a region of approxiamte zeros of size

≥ cd [\frac{k − 1}{δ_{1}} + \frac{\sqrt{d log \frac{d}{\sqrt{τ}}}}{δ_{2}} + ∑_{k=1}^{d} \frac{d}{k} (\frac{τ}{π} )^{−1/d}]^{−2}

≥ cd [min (δ_{1}, δ_{2}/\sqrt{d log \frac{d}{\sqrt{τ}}} , τ^{1/d}/(d log d))]^{2}

where

τ_{1} = c′δ_{1}^{4}d^{5}
τ_{2} = c′′δ_{2}^{N−1}d^{N},  N = k^{2} + k − 1.

Setting

ϵ = dδ_{1}^{2} = δ_{2}^{2}/ log \frac{d}{\sqrt{τ}}

we get

τ_{1} = cϵ^{2}d^{3}, τ_{2} = c (ϵ log \frac{d}{\sqrt{τ}} )^{\frac{N−1}{2}} d^{N}.

Choosing τ = ϵ^{2}d^{2} and assuming ϵ < 1/d^{2} we get that with probability

≥ 1 − c (ϵ^{2}d^{3} + (ϵ log \frac{1}{ϵ})^{\frac{N−1}{2}} d^{N} )

we have an approximate zero region of area ≥ c′ϵ since δ_{1} = \sqrt{ϵ/d} is smaller than τ^{1/d}/(d log d) > cϵ^{2/d}/(d log d).

Hence we can replace the

ϵ^{2}d^{7}

terms in equations 4.2 and 5.1 by

ϵ^{2}d^{3} + (ϵ log \frac{1}{ϵ})^{\frac{N−1}{2}} d^{N}

for any fixed N.

Second, we claim that the ϵ^{2}d^{3} term can be replaced by (ϵ^{2}d^{3})^{M} for any fixed integer M for all ϵ > e^{−cd}, c depending on M. This is because lemma 7.1 gives that with probability > 1 − e^{−cd} we have

N(0, π/M), N(2π/M, 3π/M),…, N((2M − 2)π/M, (2M − 1)π/M)

each contain c′d/M roots. For i = 1,…, M,

z_{1}^{i},…, z_{k}^{i} ∈ N((2i − 2)π/M, (2i − 1)π/M) ∩ (B_{2}(0) − B_{τ^{1/d}}(0))

with |z_{j}^{i} − z_{1}^{i}| ≤ c|z_{1}^{i}|/d we have that

P (z_{1}^{1},…, z_{k}^{1}, z_{1}^{2},…, z_{k}^{2},…, z_{1}^{M},…, z_{k}^{M}) ≈ ∏_{i=1}^{M} P (z_{1}^{i},…, z_{k}^{i}),  (7.1)

i.e. the events of finding roots at z_{1}^{i},…, z_{k}^{i} for i = 1,…, M are approximately independent. This can be seen by considering for

v_{j}^{i} ≡ (0,…, 0, j!,…, d(d − 1) … (d − j + 1)(z_{1}^{i})^{d−j})

the matrix

( \begin{matrix}⟨v_{0}^{1}, v_{0}^{1}⟩ & ⟨v_{0}^{1}, v_{1}^{1}⟩ & ⋯ & ⟨v_{0}^{1}, v_{k−1}^{M}⟩ \\ ⟨v_{1}^{1}, v_{0}^{1}⟩ & ⟨v_{1}^{1}, v_{1}^{1}⟩ & ⋯ & ⟨v_{1}^{1}, v_{k−1}^{M}⟩ \\ ⋮ & ⋮ & ... & ⋮ \\ ⟨v_{k−1}^{M}, v_{0}^{1}⟩ & ⟨v_{k−1}^{M}, v_{1}^{1}⟩ & ⋯ & ⟨v_{k−1}^{M}, v_{k−1}^{M}⟩ \end{matrix} )

and noting that its determinant is approximately

∏_{i=1}^{M} det ( \begin{matrix}⟨v_{0}^{i}, v_{0}^{i}⟩ & ⋯ & ⟨v_{0}^{i}, v_{k−1}^{i}⟩ \\ ⋮ & ... & ⋮ \\ ⟨v_{k−1}^{i}, v_{0}^{i}⟩ & ⋯ & ⟨v_{k−1}^{i}, v_{k−1}^{i}⟩ \end{matrix} ) = cd^{Mk^{2}}  (7.2)

since for i ≠ j the term

⟨v_{l}^{i}, v_{m}^{j}⟩ = O (d^{l+m})

instead of proportional to d^{l+m+1}. Hence any term in the expansion of the determinant involving at least one and therefore at least two such terms has size O(1/d^{2}) times the term in equation 7.2.

From here on, calculations similar to those done previously yield equation 7.1 and thus the ability to replace ϵ^{2}d^{3} by (ϵ^{2}d^{3})^{M}.

A Complex Random Variables

In this appendix we give some basic facts about complex random variables and their Fourier transforms.

The real isomorph of a m × n complex matrix M = U + iV, with U, V real, is the real 2m × 2n matrix given in block form as

M̂ or Mˆ = ( \begin{matrix}U & −V \\ V & U \end{matrix} ) .

It is easy to see that (M_{1} + M_{2})ˆ = M̂_{1} + M̂_{2}, (M_{1}M_{2})ˆ = M̂_{1}M̂_{2}, M̂^{⊤} = M̂^{∗} where M^{⊤} denotes the transpose of M and M^{∗} denotes the complex conjugate transpose of M, and

det M̂ = | det M|^{2}.

For v = (v_{1},…, v_{n}) ∈ C^{n}, let

ṽ = (ℜ(v_{1}),…, ℜ(v_{n}), ℑ(v_{1}),…, ℑ(v_{n})) ∈ R^{2n}.

One can check that v^{⊤} = Au^{⊤} ⇔ ṽ^{⊤} = Âũ^{⊤}, and that ℜ ⟨u, v⟩ = (ũ, ṽ), where ⟨ , ⟩ and ( , ) denote the usual inner products on C^{n} and R^{2n} respectively.

We say that u is a normally distributed complex random variable if ℜ(u) and ℑ(u) are independent, identically and normally distributed, real random variables. The standard complex normal u has distribution

ϕ(z) = \frac{1}{2π} e^{−|z|^{2}/2}.

If w_{1},…, w_{m} are independently, normally distributed real random variables with mean 0, and v_{1},…, v_{k} are linear combinations of them, then the v_{1},…, v_{k} have distribution ϕ: R^{k} → R

ϕ(x) = \frac{1}{2π^{k/2}} \frac{1}{\sqrt{det C}} e^{−(C^{−1}x,x)},

where C is the variance-covariance matrix for the v’s. If v_{j} = ∑ a_{ij}w_{i}, then

C = ( \begin{matrix}(a_{1}, a_{1}) & (a_{1}, a_{2}) & ⋯ & (a_{1}, a_{k}) \\ (a_{2}, a_{1}) & (a_{2}, a_{2}) & ⋯ & (a_{2}, a_{k}) \\ ⋮ & ⋮ & ... & ⋮ \\ (a_{k}, a_{1}) & (a_{k}, a_{2}) & ⋯ & (a_{k}, a_{k}) \end{matrix} )

where a_{j} = (a_{1j},…, a_{nj}). Writing w = Au, we have C = AA^{⊤}.

If u = (u_{1},…, u_{m}) are standard complex normals, and w = Au, then one has ṽ^{⊤} = Âũ^{⊤}. Thus ṽ^{⊤} are real normals with distribution

(\frac{1}{2π} )^{k} \frac{1}{\sqrt{det C}} e^{−(C^{−1}x,x)/2}.

with C = ÂÂ^{⊤}. Hence C = B̂, where

B = AA^{∗} = ( \begin{matrix}⟨a_{1}, a_{1}⟩ & ⋯ & ⟨a_{1}, a_{k}⟩ \\ ⋮ & ... & ⋮ \\ ⟨a_{k}, a_{1}⟩ & ⋯ & ⟨a_{k}, a_{k}⟩ \end{matrix} )

Also C^{−1} = B̂^{−1}, and so (C^{−1}x, x) = ℜ ⟨B^{−1}z, z⟩, where x = z̃. Since B^{−1} = (AA^{∗})^{−1} = (A^{−1})^{∗}A^{−1}, we have ⟨B^{−1}z, z⟩ = ⟨A^{−1}z, A^{−1}z⟩, which is real, and so ℜ ⟨B^{−1}z, z⟩ = ⟨B^{−1}z, z⟩. Thus w has the distribution

ϕ(z) = (\frac{1}{2π} )^{k} \frac{1}{\sqrt{det C}} e^{−(C^{−1}x,x)/2}
= (\frac{1}{2π} )^{k} \frac{1}{| det B|}e^{−⟨B^{−1}z,z⟩/2}.

In particular, v_{1} and v_{2} are independent iff ⟨a_{1}, a_{2}⟩ = 0.

Next we recall some facts about the characteristic functions (Fourier transform) of complex random variables. For an R^{n} valued random variable, u, with density ϕ, its characteristic function ϕ̂: R^{n} → R is

ϕ̂(ξ) ≡ E {e^{i(ξ,u)}} = ∫_{R^{n}} e^{i(ξ,x)}ϕ(x) dx.

By the Fourier inversion formula,

ϕ(x) = (\frac{1}{2π} )^{n} ∫_{R^{n}} e^{−i(ξ,x)}ϕ̂(ξ) dξ.

For a complex valued random variable u with density ϕ: C → R, we can view u as two real random variables and define its characteristic function

ϕ̂(ξ_{1}, ξ_{2}) = E {e^{i[ξ_{1}ℜ(u)+ξ_{2}ℑ(u)]}} = ∫_{C} e^{iℜ⟨ξ,x⟩}ϕ(x) dx

where ξ = ξ_{1} + iξ_{2}.

If ϕ is radially symmetric, i.e. ϕ(z) = ϕ̃(|z|), then we claim that ϕ̂ is radially symmetric. To see this, note

ϕ̂(ξ) = ∫_{R^{2}} ϕ(x, y)e^{−i(xξ_{1}+yξ_{2})} dx dy
= ∫_{r=0}^{∞} ∫_{θ=0}^{2π} ϕ̃(r)e^{−ir(ξ_{1} cos θ+ξ_{2} sin θ)} dθ r dr.

Writing ξ = |ξ|e^{iψ} and substituting we get

ϕ̂(ξ) = ∫ ∫ ϕ̃(r)e^{ir|ξ| cos(θ−ψ)} dθ r dr

which is independent of ψ.

Assuming that the fourth moments of u are finite we have

ϕ̂(ξ) = ∫ ∫ ϕ̃(r) (1 + (ir|ξ| cos θ) + \frac{(ir|ξ| cos θ)^{2}}{2} + ⋯) dθ r dr
= 1 − m_{1}|ξ|^{2} + O(|ξ|^{4})

since the integrals involving odd powers of cos θ vanish. Furthermore, if the 2ℓ + 2-th moments of u are finite, we have

ϕ̂(ξ) = 1 − m_{1}|ξ|^{2} − ⋯ − m_{ℓ}|ξ|^{2ℓ} + O(|ξ|^{2ℓ+2}).

Furthermore, for any a ∈ C, it is easy to see that the characteristic function of ua is ϕ̂(|aξ|^{2}).

The characteristic function of the standard normal v, with density

ψ(z) = \frac{1}{2π} e^{−|z|^{2}/2}

is

ψ̂(ξ) = e^{−|ξ|^{2}/2} = 1 − \frac{1}{2}|ξ|^{2} + O (|ξ|^{4})

for ξ small.

In §5 we will need to make estimates similar to those used in proving the central limit theorem. For these estimates, we recall the following facts. If u is a complex random variable with density ϕ then

|ϕ̂(ξ)| ≤ 1 ∀ξ

If ϕ is bounded, of bounded support, and, say, has ϕ(x, y) for fixed y of bounded total variation in x, then

|ϕ̂(ξ)| < \frac{a}{|ξ|} ∀ξ for some a.

To see this, given ϕ is supported in [−B, B]^{2} we estimate

|ϕ̂(ξ)| = |∫_{R^{2}} ϕ(x, y)e^{ix|ξ|} dx dy|
≤ 2B max_{y} |∫_{x=−B}^{x=B} ϕ(x, y)e^{ix|ξ|} dx|

= 2B max_{y} |ϕ(x, y)\frac{e^{ix|ξ|}}{i|ξ|} |_{−B}^{B} − ∫_{−B}^{B} \frac{∂ϕ}{∂x}(x, y)\frac{e^{ix|ξ|}}{i|ξ|} dx|

≤ \frac{2B}{|ξ|} [max_{x,y} |ϕ(x, y)| + ∫_{−B}^{B} |\frac{∂ϕ}{∂x}(x, y)| dx]
≤ \frac{c}{|ξ|} [max_{x,y} |ϕ(x, y)| + T.V._{x}ϕ(x, y)] .

One can calculate the density of u = u_{1} + ⋯ + u_{n} by taking the characteristic functions and using

ϕ̂(ξ) = E {e^{iℜ⟨ξ,u⟩}} = ∏_{j=1}^{n} E {e^{iℜ⟨ξ,u_{i}⟩}} = ∏_{j=1}^{n} ϕ̂_{i}(ξ).

Finally, the following lemma is useful

Lemma A.1 If z_{1},…, z_{n}, z′_{1},…, z′_{n} ∈ B_{1}(0) ⊂ C, then

|z_{1} ⋯ z_{n} − z′_{1} ⋯ z′_{n}| ≤ ∑_{i=1}^{n} |z_{i} − z′_{i}|.

Proof See [Bil79].

B Hammersley’s Formula

In [H], Hammersley gives the formula

P (z_{1},…, z_{r}) = ∫_{f(z_{1})=···=f(z_{r})=0} \frac{|f′(z_{1})|^{2} … |f′(z_{r})|^{2}}{∏_{1≤p<q<r} |z_{p} − z_{q}|^{2}} ω(c) dc_{r}… dc_{d} (2.1)

where P (z_{1},…, z_{r}) dz_{1} … dz_{r} is the probability of finding a root in the region of volume dz_{1} … dz_{r} at (z_{1},…, z_{r}),

f(z) = ∑_{i=0}^{d} c_{j}z^{j}

and ω(c) is the density function of the coefficients. Note that this P differs from the P defined in §4 by a factor of

d(d − 1) … (d − r + 1)

since in §4 we first choose r roots at random to calculate P. Then he claims that

P (z_{1}) = ∫_{C} |t|^{2}ψ(0, t) dt

where ψ is the joint density of f and f′. More generally we have

P (z_{1},…, z_{r}) = E {|f′(z_{1})|^{2} … |f′(z_{r})|^{2} s.t. f(z_{1}) = ⋯ = f(z_{r}) = 0}

where by the right hand side of the above we mean

∫_{C^{r}} |t_{1}|^{2} … |t_{r}|^{2}ψ(0,…, 0, t_{1},…, t_{r}) dt_{1} … dt_{r}

where ψ is the joint density of f(z_{1}),…, f(z_{r}), f′(z_{1}),…, f′(z_{r}). This can be derived from equation 2.1 by setting

s_{i} = ∑_{j=0}^{d} c_{j}z_{i}^{j}

(= f(z_{i})) and writing

P (z_{1},…, z_{r}) = lim_{ϵ→0} (\frac{1}{πϵ^{2}} )^{r} ∫_{s_{i}∈B_{ϵ}(0),i=1,...,r} \frac{|f′(z_{1})|^{2} … |f′(z_{r})|^{2}}{∏_{1≤p<q<r} |z_{p} − z_{q}|^{2}} ω(c) dc_{r}… dc_{d} ds_{1} … ds_{r}

and noting that

\frac{∂(s_{1},…, s_{r}, c_{r},… c_{d})}{∂(c_{0},…, c_{d})} = \frac{∂(s_{1},…, s_{r})}{∂(c_{0},…, c_{r−1})} = ∏_{i<j<r}(z_{j} − z_{i})

and so

P (z_{1},…, z_{r}) = lim_{ϵ→0} (\frac{1}{πϵ^{2}} )^{r} ∫_{s_{i}∈B_{ϵ}(0),i=1,...,r} |f′(z_{1})|^{2} … |f′(z_{r})|^{2}ω(c) dc_{0} … dc_{d}
= ∫_{C^{r}} |t_{1}|^{2} … |t_{r}|^{2}ψ(0,…, 0, t_{1},…, t_{r}) dt_{1} … dt_{r}

where ψ is the joint density of f(z_{1}),…, f(z_{r}), f′(z_{1}),…, f′(z_{r}).

References

[Bil79] Patrick Billingsley. Probability and Measure. John Wiley & Sons, 1979.

[BS86] A.T. Bharucha-Reid and M. Sambandham. Random Polynomials. Probability and Mathematical Statistics, Academic Press, New York, 1986.

[ET50] P. Erdös and P. Turán. On the distribution of roots of polynomials. Annals of Math., 51(1):105–119, 1950.

[GT74] W. Greg and R. Tapia. Optimal error bounds for the newtonkantorovich theorem. SIAM J. Numer. Anal., 11:10–13, 1974.

[Ham60] J.M. Hammersley. The zeros of a random polynomial. In The Third Berkeley Symp. ..., pages 89–111, 1960.

[KA70] L. Kantorovich and G. Akilov. Functional Analysis in Normed Spaces. MacMillan, 1970.

[Kan52] L. Kantorovich. Functional Analysis and Applied Mathematics. National Bureau of Standards, 1952.

[Kim85] M. Kim. Ph.D. Thesis. PhD thesis, City University of New York, 1985.

[Mar66] M. Marden. Geometry of Polynomials. Amer. Math. Soc., 1966.

[Ren87] James Renegar. On the worst-case arithmetic complexity of approximating zeros of polynomials. 1987. preprint.

[Roy86] H.L. Royden. Newton’s method. Preprint, 1986.

[Sma81] Steve Smale. The fundamental theorem of algebra and complexity theory. Bull. of the AMS, 4(1):1–35, 1981.

[Sma86a] Steve Smale. Algorithms for solving equations. In written for the International Congress of Mathematicians, 1986.

[Sma86b] Steve Smale. Newton’s method estimates from data at one point. In R.E. Ewing, K.I. Gross, and C.F. Martin, editors, The Merging of Disciplines: New Directions in Pure, Applied, and Computational Mathematics, pages 185–196, Springer-Verlag, 1986.

[SS85] Mike Shub and Steve Smale. Computational complexity: on the geometry of polynomials and a theory of cost: part i. Ann. Scient. École Norm. Sup. 4 serie t, 18:107–142, 1985.

[SS86] Mike Shub and Steve Smale. Computational complexity: on the geometry of polynomials and a theory of cost: part ii. SIAM J. on Computing, 15(1):145–161, 1986.