Random polynomials having few or no real zeros

Amir Dembo ^{∗}  Bjorn Poonen ^{†}  Qi-Man Shao ^{‡}  Ofer Zeitouni ^{§}

May 29, 2000

Abstract

Consider a polynomial of large degree n whose coefficients are independent, identically distributed, nondegenerate random variables having zero mean and finite moments of all orders. We show that such a polynomial has exactly k real zeros with probability n^{−b+o(1)} as n → ∞ through integers of the same parity as the fixed integer k ≥ 0. In particular, the probability that a random polynomial of large even degree n has no real zeros is n^{−b+o(1)}. The finite, positive constant b is characterized via the centered, stationary Gaussian process of correlation function sech(t/2). The value of b depends neither on k nor upon the specific law of the coefficients. Under an extra smoothness assumption about the law of the coefficients, with probability n^{−b+o(1)} one may specify also the approximate locations of the k zeros on the real line. The constant b is replaced by b/2 in case the i.i.d. coefficients have a nonzero mean.

1 Introduction

Let {a_{i}}_{i=0}^{∞} denote a sequence of independent, identically distributed (i.i.d.) random variables of zero mean and unit variance. Consider the random polynomial

f_{n}(x) = ∑_{i=0}^{n−1} a_{i}x^{i} .  (1.1)

For n odd, define

P_{n} = P (f_{n}(x) > 0 ∀x ∈ ℝ) .  (1.2)

As described in Section 1.1, the study of the number of roots of random polynomials has a long history. Our main goal is to prove that P_{n} = n^{−b+o(1)} as n → ∞ for a finite constant b > 0, at least when the coefficient distribution has finite moments of all orders. The constant b can be described in terms of the centered stationary Gaussian process Y_{t} with correlation function R_{y}(t) = sech(t/2) (see (1.4) for an explicit construction of Y_{·}). Define

b = −4 lim_{T →∞} \frac{1}{T} log P ( sup_{0≤t≤T} Y_{t} ≤ 0) ,  (1.3)

∗Research partially supported by NSF grant DMS-9704552.

†Supported by NSF grant DMS-9801104, a Sloan Fellowship, and a Packard Fellowship.

‡Research partially supported by NSF grant DMS-9802451.

§Research partially supported by a grant from the Israel Science Foundation and by the fund for promotion of research at the Technion.

AMS subject classification: primary 60G99; secondary 12D10, 26C10.

Keywords: Random polynomials, Gaussian processes

where, throughout this paper, log denotes the natural logarithm. The existence of the limit in (1.3) and the estimate b ∈ [0.4, 2] are proved in Lemma 2.5. We note in passing that our numerical simulations of random polynomials of degree n − 1 ≤ 1024 suggest b = 0.76 ± 0.03.

Our main result, which is a consequence of Theorem 1.3 stated in Section 1.2, is the following

Theorem 1.1 a) Suppose {a_{i}} is a sequence of zero-mean, unit-variance, i.i.d. random variables possessing finite moments of all order. Then,

lim_{n→∞} \frac{log P_{2n+1}}{log n} = −b .

b) If {a_{i}} is as above but with E(a_{i}) = μ ≠ 0, we denote P_{n}^{μ} = P (f_{n}(x) ≠ 0 ∀x ∈ ℝ). Then,

lim_{n→∞} \frac{log P_{2n+1}^{μ}}{log n} = −b/2 .

It is interesting to note that one may answer questions related to a prescribed number of zeros. Our main result in this direction is the following theorem. For a slightly different variant, allowing to prescribe the location of zeros, see also Proposition 1.5.

Theorem 1.2 Under the assumptions of Theorem 1.1 a), the probability that the random polynomial f_{n+1}(x) of degree n has o(log n/ log log n) real zeros is n^{−b+o(1)} as n → ∞. For any fixed k, the probability p_{n,k} that f_{n+1} has exactly k real zeros, all of which are simple, satisfies

lim_{n→∞} \frac{log p_{2n+k,k}}{log n} = −b .

(Obviously, p_{n,k} = 0 when n − k is odd.)

The key to our analysis is a detailed study of the case where the coefficients are Gaussian, implying that f_{n}(·) is a Gaussian process (Gaussian processes are particularly useful in this context because for them comparisons can be made via Slepian’s lemma). The extension to general distribution uses the strong aproximation results of Komlós-Major-Tusnády [KMT]. Although this technique requires finite moments of all order, we conjecture that the asymptotic n^{−b+o(1)} applies to p_{n,k} for n − k even, whenever the nondegenerate zero-mean i.i.d. a_{i} are in the domain of attraction of the Normal distribution. This conjecture is supported by the following heuristic derivation of P_{n} = n^{−b+o(1)}.

For x ∈ [0, 1] near 1, let x = 1 − e^{−t}. Note that x^{i} ≈ exp(−e^{−t}i) when t ≫ 0, and moreover, the function h_{t}(u) := exp(−e^{−t}u) changes slowly in u for t ≫ 0. Summation by parts suggests that the sign of f_{n}(x) is mostly determined by the behavior of ∑_{i=0}^{j} a_{i} for large j depending on t. Hence, for a_{i} in the domain of attraction of the Normal distribution, we next replace a_{i} with i.i.d. standard Normal variables b_{i}. Using the representation b_{i} = W_{i+1} − W_{i} for a standard Brownian motion W_{t} we further replace the sum over i = 0, …, n − 1 with the corresponding stochastic integral over [0, ∞). This in turn yields the approximation of the normalized f̂_{n}(x) := f_{n}(x)/\sqrt{Var(f_{n}(x))} by the centered, Gaussian process

Y_{t} = \frac{∫_{0}^{∞} h_{t}(u)dW_{u}}{(∫_{0}^{∞} h_{t}(u)^{2}du)^{1/2}} .  (1.4)

It is easy to check that the process Y_{·} of (1.4) is stationary, with correlation function sech(t/2). By continuity arguments, f_{n}(x) typically has a constant sign in [1 − n^{−1}, 1], so our approximation procedure is relevant only as long as t ≤ log n. Alternatively, t = log n is where we start seeing h_{t}(n) = O(1), contrasting the replacement of the upper limit n in the discrete sum with the upper limit ∞ in the stochastic integral of (1.4). We are to consider the possibility of f_{n}(x) = 0 for x in the left and in the right neighborhoods of both −1 and +1. In each of these four regimes of x the function f̂_{n}(x) is amenable to a similar treatment, leading to an approximation by the process Y_{t}. With f̂_{n} having approximately independent values in the four different regimes, we arrive at the formula (1.3) for b.

It is natural to wonder what happens when a_{i} are of a symmetric law that is in the domain of attraction of an α-stable law, for some α ∈ (0, 2). A lower bound on P_{n} of the form n^{−c} for some finite value of c is then easily obtained by considering the event that a_{0} and a_{n−1} are “huge” and positive, while other coefficients are “reasonable.” Repeating the above heuristic for this case, one is led to believe that the formula (1.3) still applies, but now with Y_{t} of (1.4) replaced by

Y_{t,α} = \frac{∫_{0}^{∞} h_{t}(u)dX_{u}^{(α)}}{(∫_{0}^{∞} h_{t}(u)^{α}du)^{1/α}} ,  (1.5)

where X_{·}^{(α)} denotes the symmetric stable process of index α and the stochastic integral in (1.5) is to be interpreted via integration by parts. We have yet no strong evidence to support the above statement. However, our numerical simulations indicate the behavior P_{n} = n^{−b_{1}+o(1)} for i.i.d. Cauchy random variables a_{i} (that is, α = 1), where b_{1} ≈ 0.86 is larger than b.

1.1 Historical remarks

Throughout this section, {a_{i}} are independent, identically distributed, nondegenerate, real-valued random variables.^{1} Let N_{n} denote the number of distinct^{2} real zeros of f(x) := ∑_{i=0}^{n} a_{i}x^{i}. (For the sake of definiteness, we define N_{n} = 0 when f is the zero polynomial.) So, p_{n} := P (N_{n} = 0) = p_{n,0} and we also let E_{n} and V_{n} denote the mean and variance of N_{n}.

The study of real roots of random polynomials has a long and full history, but most of it deals with the asymptotic behavior of E_{n} instead of p_{n}. Presumably this is because E_{n} is much easier to estimate: because expectation is linear, one can compute E_{n} by integrating over the real line the probability of having a root in (t, t + dt), for example.

Although as mentioned in [To, p. 618], one can find probabilistic statements in the context of roots of polynomials as early as 1782 (Waring) and 1864 (Sylvester), the first people to study the asymptotic behavior of N_{n} seem to be Bloch and Pólya [BP]. In 1932, they proved E_{n} = O(n^{1/2}) for the coefficient distribution P (a_{i} = 1) = P (a_{i} = 0) = P (a_{i} = −1) = 1/3. This work led Littlewood and Offord to undertake a systematic study of N_{n} in a series of papers [LO1],[LO2],[LO3] starting in 1938. They proved that if the a_{i} are all uniform on [−1, 1], or all Normal, or all uniform on {−1, 1}, (i.e. P (a_{i} = 1) = P (a_{i} = −1) = 1/2), then

P (N_{n} > 25(log n)^{2}) ≤ \frac{12 log n}{n}, and P (N_{n} < \frac{α log n}{(log log n)^{2}} ) < \frac{A}{log n}

for some constants α and A. In particular, for some constant α′,

\frac{α′ log n}{(log log n)^{2}} ≤ E_{n} ≤ 25(log n)^{2} + 12 log n

1Some authors whose work we mention assumed a_{0} = 1 or a_{n} = 1, but as far as asymptotic behavior as n → ∞ is concerned, it makes little difference.

2The asymptotic behavior does not depend on whether roots are counted with multiplicity or not.

and p_{n} = O(1/ log n) for these distributions. This upper bound for p_{n} has apparently not been improved, until the current paper.^{3}

In 1943 Kac [Ka1] found the exact formula

E_{n} = \frac{1}{π} ∫_{−∞}^{∞} \sqrt{\frac{1}{(t^{2} − 1)^{2}} − \frac{(n + 1)^{2}t^{2n}}{(t^{2n+2} − 1)^{2}}} dt ,  (1.6)

when a_{i} is Normal with mean zero, and extracted from it the asymptotic estimate

E_{n} ∼ \frac{2}{π} log n .  (1.7)

Much later Jamrom [Ja] and Wang [Wa] improved this to E_{n} = (2/π) log n + C + o(1) for an explicit constant C, and ultimately Wilkins [Wi] obtained an asymptotic series for E_{n} from (1.6). In 1949 Kac [Ka2] obtained (1.7) for the case where a_{i} is uniform on [−1, 1]. Erdős and Offord [EO] obtained the same asymptotics for a_{i} uniform on {−1, 1}. Stevens [St] proved (1.7) for a wide class of distributions, and this estimate was finally extended by Ibragimov and Maslova [IM1],[IM2] to all mean-zero distributions in the domain of attraction of the Normal law.

At around the same time (the late 1960’s), Logan and Shepp [LS1],[LS2] discovered that if the coefficient distribution is the symmetric stable distribution with characteristic function exp(−|z|^{α}), 0 < α ≤ 2, then E_{n} ∼ c_{α} log n, where

c_{α} := \frac{4}{π^{2}α^{2}} ∫_{−∞}^{∞} dx log ∫_{0}^{∞} \frac{|x − y|^{α}e^{−y}}{|x − 1|^{α}} dy > \frac{2}{π} .

They also proved lim_{α→0^{+}} c_{α} = 1, and performed calculations that suggested that c_{α} is a decreasing function of α, terminating at c_{2} = 2/π, Kac’s value for the Normal distribution. Ibragimov and Maslova [IM4] extended these results by finding the asymptotic behavior of E_{n} for arbitrary distributions in the domain of attraction of a stable distribution. The asymptotics are different when the distribution has nonzero mean; for instance [IM3], if a_{i} are Normal with nonzero mean, then E_{n} ∼ (1/π) log n instead of (2/π) log n. Shepp (private communication) has conjectured that there exists a universal constant B such that

lim sup_{n→∞} \frac{E_{n}}{log n} ≤ B

for any coefficient distribution (satisfying only the hypotheses at the beginning of this section). If B exists, then B ≥ 1 by the work of Logan and Shepp mentioned above.

In 1974, Maslova [Ma1],[Ma2] proved that if P (a_{i} = 0) = 0, Ea_{i} = 0 and E(a_{i}^{2+ϵ}) < ∞ for some ϵ > 0, then

V_{n} ∼ \frac{4}{π} (1 − \frac{2}{π} ) log n  (1.8)

and N_{n} is asymptotically Normal.

Much work was also done on complex roots of f_{n}; see [IZ] and references therein for an updated account. Further results on random polynomials and their generalizations can be found in the books [BR, Fa] and the survey article [EK].

Our interest in the asymptotics of p_{n} grew out of a problem in arithmetic geometry. The paper [PS] showed that Jacobians of curves over ℚ could be odd, in the sense of having Shafarevich-Tate groups of nonsquare order (despite prior claims in the literature that this was impossible).

3The only result in the literature that might be said to have improved our knowledge of p_{n} is (1.8), which together with (1.7) implies for many distributions that lim sup_{n→∞} p_{n} log n ≤ π − 2. The bound has the same form as that arising from the work of Littlewood and Offord, but the constant has been made explicit.

Moreover it was shown (in a sense that was made precise) that the probability that a random hyperelliptic curve y^{2} = f(x) of genus g over ℚ has odd Jacobian could be related to a sequence of “local” probabilities, one for each nontrivial absolute value on ℚ. The computation of the local probability for the standard archimedean absolute value reduced to the knowledge of the probability that the curve y^{2} = f(x) has no real point, or equivalently, the probability that the random polynomial f(x) satisfies f(x) < 0 for all real x. Although the asymptotic behavior of this probability was not needed in a substantial way in [PS], the authors of that paper found the question to be of sufficient interest in its own right that they developed heuristics that led them to conjecture the existence of a universal constant b > 0 such that p_{n} = n^{−b+o(1)}, for any mean-zero distribution in the domain of attraction of the Normal law.

1.2 Statement of main theorems

Let f̂_{n}(x) := f_{n}(x)/\sqrt{E(f_{n}(x)^{2})} denote the normalized random polynomial, so f̂_{n}(x) has unit variance for each x. Instead of proving only P_{n} = n^{−b+o(1)}, we generalize in the following, to facilitate applications to related problems.

Theorem 1.3 Suppose a_{i} are zero-mean i.i.d. random variables of unit variance and with finite moments of all orders. For n − 1 even, let

P_{n,γ_{n}} = P (f̂_{n}(x) > γ_{n}(x) ∀x ∈ ℝ) ,

for nonrandom functions γ_{n}(x) such that n^{δ}|γ_{n}(x)| → 0 uniformly in x ∈ ℝ for some δ > 0. Then,

\frac{log P_{n,γ_{n}}}{log n} ⟶_{n→∞} −b .  (1.9)

The upper bound P_{n,γ_{n}} ≤ n^{−b+o(1)} applies as soon as

inf{γ_{n}(x) : ||x| − 1| ≤ n^{−ε_{n}}} → 0 for any ε_{n} → 0 .

The key to the proof of Theorem 1.3 is the analysis of P_{n,γ_{n}} for random polynomials f_{n}(x) with coefficients {b_{i}} that are i.i.d. standard Normal variables. To distinguish this case, we use throughout the notations f_{n}^{b}(x), f̂_{n}^{b} and P_{n,γ_{n}}^{b} for f_{n}(x), f̂_{n}(x) and P_{n,γ_{n}}, respectively, when dealing with polynomials of coefficients that are Normal variables. The next theorem summarizes our results in this special case.

Theorem 1.4 The convergence of log P_{n,γ_{n}}^{b}/ log n to −b applies in the standard Normal case, as soon as the nonrandom functions γ_{n}(x) ≤ M < ∞ are such that

sup{|γ_{n}(x)| : ||x| − 1| ≤ n^{−ε_{n}}} → 0 for some ε_{n} → 0 .

The following proposition is the variant of Theorem 1.2 alluded to above. It shows that with probability n^{−b+o(1)} one may also prescribe arbitrarily the location of the k real zeros of f_{n+1}(x), provided the support of the law of a_{i} contains an open interval around 0. The latter assumption is to some extent necessary. For example, when P (a_{i} = 1) = P (a_{i} = −1) = 1/2 it is easy to see that f_{n+1}(x) cannot have zeros in [−1/2, 1/2].

Proposition 1.5 Suppose a_{i} are zero-mean i.i.d. random variables of unit variance, finite moments of all orders, and the support of the law of each a_{i} contains the interval (−η, η) for some η > 0. Given disjoint open intervals U_{1}, …, U_{ℓ} and positive integers m_{1}, …, m_{ℓ}, the probability that the random polynomial f_{n+1}(x) has exactly m_{i} real zeros in U_{i} for each i and no real zeros anywhere else is n^{−b+o(1)} for n → ∞ through integers of the same parity as k = ∑_{i} m_{i}.

The organization of this paper is as follows. Auxiliary lemmas about Gaussian processes, needed for the proof of Theorem 1.4, are grouped in Section 2 (including the bounds on b mentioned in the introduction, c.f. Lemma 2.5). Relying upon Gaussian techniques, the proof of the lower bound of Theorem 1.4 is in Section 3, and the complementary upper bound in Section 4. Building upon Theorem 1.4, and with the help of strong approximation, Section 5 provides the proof of our main result, Theorem 1.3. Theorem 1.1 is then derived in Section 6. Section 7 provides the upper bound on the probability of interest in Theorem 1.2, with the lower bound proved in Section 8. Finally, Proposition 1.5 is proved in Section 9.

2 Auxiliary lemmas

We start by introducing several notations that appear throughout this work. For n odd, let c_{n}(x, y) denote the covariance function of f̂_{n}(x), that is

c_{n}(x, y) = \frac{E(f_{n}(x)f_{n}(y))}{\sqrt{E(f_{n}(x)^{2})E(f_{n}(y)^{2})}}  (2.1)

Then, for x ≠ ±1 and y ≠ ±1,

c_{n}(x, y) = \frac{g(x^{n}, y^{n})}{g(x, y)}  (2.2a)

where

g(x, y) = \frac{|xy − 1|}{\sqrt{|(1 − x^{2})(1 − y^{2})|}} ≥ 0 .  (2.2b)

Note that g(x, y) = g(−x, −y) = g(\frac{1}{x}, \frac{1}{y}). Further,

∀x, y ∈ (−1, 1), g(x, y) ≥ 1  (2.2c)

and the change of variables z = 1 − x, w = 1 − y, leads to

\frac{1}{g(x, y)} = \frac{2\sqrt{zw}}{z + w} [1 − [\frac{1 − \frac{wz}{z+w} − \sqrt{1 − \frac{z}{2}} \sqrt{1 − \frac{w}{2}}}{1 − \frac{wz}{z+w}} ]]  (2.3)

A good control on g(x, y) is provided by the following lemma.

Lemma 2.1 For any z, w ∈ (0, 1/2]

\frac{1}{8}(w − z)^{2} ≤ (1 − \frac{wz}{w + z} − \sqrt{1 − \frac{z}{2}} \sqrt{1 − \frac{w}{2}} )\frac{max(z, w)}{(1 − \frac{wz}{w+z} )} ≤ (w − z)^{2} .

Proof: Let z + w = η, z − w = ξ, assuming without loss of generality that 0 < ξ ≤ η ≤ 1. Since

1 ≥ 1 − \frac{wz}{w + z} ≥ \frac{1}{2} , 1 ≥ \frac{max(z, w)}{(z + w)} ≥ \frac{1}{2} ,

it suffices to prove that

f(w, z) = \frac{1}{(z − w)^{2}} [1 − \frac{wz}{w + z} − \sqrt{1 − \frac{z}{2}} \sqrt{1 − \frac{w}{2}} ](z + w) ∈ [1/4, 1/2] .

To this end, observe that for all 0 < ξ ≤ η ≤ 1 we have

f(w, z) = \frac{η}{ξ^{2}} [1 − \frac{η^{2} − ξ^{2}}{4η} − \sqrt{(1 − \frac{η}{4} )^{2} − (\frac{ξ}{4})^{2}} ]

= \frac{η}{ξ^{2}} [(1 − \frac{η}{4} ) + \frac{ξ^{2}}{4η} − \sqrt{(1 − \frac{η}{4} )^{2} − (\frac{ξ}{4})^{2}} ] = \frac{1}{4} + \frac{η̃}{4ξ̃^{2}} [1 − \sqrt{1 − ξ̃^{2}}] ,

where ξ̃ = ξ/(4 − η), η̃ = η/(4 − η). Since ξ ≤ η ≤ 4 − η and 0 ≤ 1 − \sqrt{1 − ξ̃^{2}} ≤ ξ̃^{2} it follows that 1/4 ≤ f(w, z) ≤ 1/4 + η̃/4 ≤ 1/2 as needed.

The control of Lemma 2.1 on g(x, y), hence on c_{n}(x, y), shall give rise to the perturbed centered Gaussian processes Y^{(α)} of the next lemma.

Lemma 2.2 Let α ∈ [0, 1] and define the covariance

R^{(α)}(τ) = sech(τ/2){1 − α(1 − e^{−|τ|})^{2}} .

Then there exist independent, stationary centered Gaussian processes Y_{t}, Z_{t}, with covariances R_{y}(τ) = R^{(0)}(τ) and

R_{z}(τ) = R^{(1)}(τ) = sech(τ/2)(2e^{−|τ|} − e^{−2|τ|})

respectively, such that the process Y_{t}^{(α)} := \sqrt{1 − α} Y_{t} + \sqrt{α}Z_{t} has covariance R^{(α)}(τ).

Proof: Since R^{(α)}(τ) = (1−α)R_{y}(τ)+αR_{z}(τ), all one needs is to check that both R_{y}(τ) and R_{z}(τ) are covariance functions, i.e. to check that their Fourier transforms are nonnegative. To this end, note that

S_{y}(ω) := F(R_{y}(τ)) = ∫_{−∞}^{∞} e^{iωτ} R_{y}(τ)dτ = 2 ∫_{0}^{∞} cos(ωτ)sech(τ/2)dτ = 2πsech(ωπ) ≥ 0 ,

c.f. [GR, p. 503, formula 3.981.3]. Furthermore,

S_{z}(ω) := F(R_{z}(τ)) = ∫_{−∞}^{∞} e^{iωτ} R_{z}(τ)dτ = S_{y}(ω) ∗ F (ω) ,

where ∗ stands throughout for the convolution operation and

F (ω) = ∫_{−∞}^{∞} e^{iωτ} (2e^{−|τ|} − e^{−2|τ|})dτ = 2 ∫_{0}^{∞} cos(ωτ)(2e^{−τ} − e^{−2τ} )dτ
= \frac{4}{1 + ω^{2}} − \frac{4}{4 + ω^{2}} = \frac{12}{(4 + ω^{2})(1 + ω^{2})} ≥ 0 .

Hence, S_{z}(ω) ≥ 0.

The effect of nonrandom functions γ_{n}(x) as well as that of considering the processes Y^{(α)} for some α_{n} ↓ 0 are dealt with by the continuity properties of Y_{t} and Z_{t} outlined in the next lemma.

Lemma 2.3 Let Y_{t}, Z_{t} be as in Lemma 2.2. Then, for any positive ε_{T} → 0,

lim_{T →∞} P ( sup_{0≤t≤T} Z_{t} ≤ \sqrt{ε_{T}^{−1} log T} ) = 1 ,  (2.4)

whereas

lim sup_{T →∞} \frac{1}{T} log P ( sup_{0≤t≤T} Y_{t} ≤ ε_{T} ) = lim inf_{T →∞} \frac{1}{T} log P ( sup_{0≤t≤T} Y_{t} ≤ −ε_{T} )
= lim_{T →∞} \frac{1}{T} log P ( sup_{0≤t≤T} Y_{t} ≤ 0) = −\frac{b}{4} .  (2.5)

Moreover, for any positive γ_{T} → 0 and α_{T} log T → 0,

lim inf_{T →∞} \frac{1}{T} log P ( inf_{0≤t≤T} Y_{t}^{(α_{T})} ≥ γ_{T} ) ≥ −\frac{b}{4} .  (2.6)

Proof: The existence of the limit in the right hand side of (2.5) (and hence in (1.3)) is ensured by sub-additivity: since R_{y}(·) > 0, Slepian’s lemma (c.f. [Ad, Page 49]), and the stationarity of Y_{·} imply

P ( sup_{0≤t≤T +S} Y_{t} ≤ 0) ≥ P ( sup_{0≤t≤T} Y_{t} ≤ 0)P ( sup_{T ≤t≤T +S} Y_{t} ≤ 0)
= P ( sup_{0≤t≤T} Y_{t} ≤ 0)P ( sup_{0≤t≤S} Y_{t} ≤ 0) .

Fix ε_{T} → 0. From Lemma 2.2, we have that

S_{z}(ω) = F(R_{z}(τ)) = 2πsech(ωπ) ∗ \frac{12}{(4 + ω^{2})(1 + ω^{2})} ,

which implies that sup_{ω}{S_{z}(ω)ω^{4}} < ∞. Hence ∫_{−∞}^{∞} ω^{2}S_{z}(ω)dω < ∞. It follows that

−\frac{∂^{2}}{∂τ^{2}} R_{z}(τ)|_{τ=0} = E(Ż_{t}^{2}) < ∞ .

Since |Z_{t}| ≤ |Z_{0}| + ∫_{0}^{1} |Ż_{t}|dt, it follows by stationarity of the centered Gaussian process Ż_{t} that

m_{1} := E( sup_{0≤t≤1} |Z_{t}|) ≤ \sqrt{E(Z_{0}^{2})} + \sqrt{E(Ż_{t}^{2})} < ∞ .

By the stationarity of Z_{t} and Borell’s inequality (c.f. [Ad, Page 43]), for all λ ≥ m_{1},

P ( sup_{0≤t≤T} Z_{t} ≥ λ) ≤ T P ( sup_{0≤t≤1} |Z_{t}| ≥ λ) ≤ 2T exp(−\frac{(λ − m_{1})^{2}}{2R_{z}(0)} ) .

Setting λ = \sqrt{ε_{T}^{−1} log T} we obtain that as T → ∞,

P ( sup_{0≤t≤T} Z_{t} ≥ \sqrt{ε_{T}^{−1} log T} ) → 0 ,

which yields (2.4).

To see (2.5), let the Gaussian law of Y_{·} on C(ℝ; ℝ) be denoted by P_{y}. Let R_{y} denote the covariance operator associated with P_{y}, that is, R_{y}g(t) = ∫_{−∞}^{∞} R_{y}(t − s)g(s)ds, with K_{y} = R_{y}^{−1} denoting its inverse (defined on the range of R_{y}). We also let ⟨·, ·⟩ denote the inner product of

L^{2}(ℝ). Fixing T < ∞ note that the deterministic function f_{T} (t) := ε_{T} exp(\frac{1}{4} − (\frac{t}{T} )^{2}) is in the Reproducing Kernel Hilbert Space (RKHS) associated with the process Y_{·}. Indeed, the Fourier transform of f_{T} is f̂(ω) = c_{1}T ε_{T} e^{−ω^{2}T^{2}} (for some c_{1} < ∞), so it follows by Parseval’s theorem that for some c_{2} < ∞ and all T,

⟨f_{T} , K_{y}f_{T} ⟩ = ∫_{−∞}^{∞} \frac{|f̂(ω)|^{2}}{S_{y}(ω)} dω = 2π ∫_{−∞}^{∞} |f̂(ω)|^{2}sech(ωπ)dω ≤ c_{2}T ε_{T}^{2} ,  (2.7)

In particular, ⟨f_{T} , K_{y}f_{T} ⟩ is finite and the Radon-Nikodým derivative

Λ_{T} (Y) = exp(⟨f_{T} , K_{y}Y ⟩ − \frac{1}{2} ⟨f_{T} , K_{y}f_{T} ⟩) ,

is well defined and finite for P_{y}-almost-every Y_{·}. Since f_{T} (t) ≥ ε_{T} for all −\frac{T}{2} ≤ t ≤ \frac{T}{2} , it follows that

P ( sup_{− \frac{T}{2} ≤t≤ \frac{T}{2}} Y_{t} ≤ ε_{T} ) = P ( sup_{− \frac{T}{2} ≤t≤ \frac{T}{2}} \{Y_{t} − ε_{T} \} ≤ 0) ≤ P ( sup_{− \frac{T}{2} ≤t≤ \frac{T}{2}} \{Y_{t} − f_{T} (t)\} ≤ 0)

= E(Λ_{T} (Y) 1_{\{sup_{− \frac{T}{2} ≤t≤ \frac{T}{2}} Y_{t}≤0\}}) ≤ E(Λ_{T} (Y)^{q})^{\frac{1}{q}} [P ( sup_{− \frac{T}{2} ≤t≤ \frac{T}{2}} Y_{t} ≤ 0)]^{\frac{1}{p}}  (2.8)

where \frac{1}{p} + \frac{1}{q} = 1. Note that

(E(Λ_{T} (Y)^{q}))^{\frac{1}{q}} = exp(\frac{q − 1}{2}⟨f_{T} , K_{y}f_{T} ⟩) .

Hence, choosing q_{T} = (1/ε_{T}) → ∞ it follows from (2.7) that

\frac{1}{T} log(E(Λ_{T} (Y)^{q}))^{\frac{1}{q}} ⟶_{T →∞} 0 .

Substituting in (2.8) and using the stationarity of Y_{·} and existence of the limit in (1.3), one has that

lim sup_{T →∞} \frac{1}{T} log P ( sup_{0≤t≤T} Y_{t} ≤ ε_{T} ) ≤ lim_{T →∞} \frac{1}{T} log P ( sup_{0≤t≤T} Y_{t} ≤ 0) .  (2.9)

The equality in (2.9) is then obvious. The other equality in (2.5) follows by a similar proof, starting with

P ( sup_{− \frac{T}{2} ≤t≤ \frac{T}{2}} Y_{t} ≤ 0) ≤ P ( sup_{− \frac{T}{2} ≤t≤ \frac{T}{2}} \{Y_{t} − f_{T} (t)\} ≤ −ε_{T} ) ≤ E(Λ_{T} (Y)^{q})^{\frac{1}{q}} P ( sup_{− \frac{T}{2} ≤t≤ \frac{T}{2}} Y_{t} ≤ −ε_{T} )^{\frac{1}{p}} .

Turning to prove (2.6), set ε_{T} = 3 max(γ_{T} , (α_{T} log T)^{1/3}) → 0, and note that

\sqrt{1 − α_{T}} ε_{T} − \sqrt{α_{T}} \sqrt{ε_{T}^{−1} log T} ≥ γ_{T} ,

once T is large enough that α_{T} ≤ 1/3. Then, by the independence of Y_{t} and Z_{t},

P ( inf_{0≤t≤T} Y_{t}^{(α_{T})} ≥ γ_{T} ) ≥ P ( inf_{0≤t≤T} Y_{t} ≥ ε_{T} )P ( inf_{0≤t≤T} Z_{t} ≥ −\sqrt{ε_{T}^{−1} log T} ) .

With the laws of the processes Y_{t} and Z_{t} invariant to a change of sign, the inequality (2.6) is thus a direct consequence of (2.4) and (2.5).

The control of f̂_{n}^{b}(x) for x ∈ [1 − n^{−1}, 1] is achieved in the next lemma by means of the sample path smoothness of f_{n}^{b}(·).

Lemma 2.4 For any finite γ, the set of limit points of C_{n} = P (f̂_{n}^{b}(x) > γ, ∀x ∈ [1 − n^{−1}, 1] ) is bounded below by some C_{∞} = C_{∞}(γ) > 0.

Proof: Without loss of generality we assume that γ ≥ 0. Since x ↦ E(f_{n}^{b}(x)^{2}) is increasing on [0, ∞), with E(f_{n}^{b}(1)^{2}) = n, it follows that for any λ > 0

C_{n} ≥ P (f_{n}^{b}(x) > γ\sqrt{n}, ∀x ∈ [1 − n^{−1}, 1] )
≥ P (f_{n}^{b}(1) > (λ + γ)\sqrt{n}) − P ( sup_{(1−n^{−1})≤ξ≤1} f_{n}^{b} ′(ξ) ≥ λn^{3/2})  (2.10)

We wish to apply Borell’s inequality to bound the second term in (2.10). To this end, note that

f_{n}^{b} ′(ξ) = ∑_{i=0}^{n} ib_{i}ξ^{i−1} = ∑_{i=0}^{n}(∑_{j=0}^{i} b_{j})[iξ^{i−1} − (i + 1)ξ^{i}] + (n + 1)ξ^{n} ∑_{j=0}^{n} b_{j} .

By Kolmogorov’s maximal inequality,

E[sup_{i≤n}|∑_{j=0}^{i} b_{j}|] ≤ c_{1}n^{1/2} .

Hence, for some c_{2} > 0,

E| sup_{1−n^{−1}≤ξ≤1} f_{n}^{b} ′(ξ)| ≤ c_{2}n^{3/2} .  (2.11)

Furthermore, we have that

sup_{1−n^{−1}≤ξ≤1} E[\frac{1}{n^{3/2}} f_{n}^{b} ′(ξ)]^{2} = \frac{1}{n^{3}} ∑_{i=1}^{n−1} i^{2} ⟶_{n→∞} \frac{1}{3} ,

implying, by Borell’s inequality and (2.11), that for some finite c_{3}, all n and any λ ≥ c_{2},

P ( sup_{1−n^{−1}≤ξ≤1} f_{n}^{b} ′(ξ) ≥ λn^{3/2}) ≤ c_{3}e^{−3(λ−c_{2})^{2}/2} .  (2.12)

Since n^{−1/2}f_{n}^{b}(1) is a standard Normal random variable, it follows that for some positive c_{4} = c_{4}(γ), λ = λ(γ) large enough and all n,

P (f_{n}^{b}(1) > (λ + γ)\sqrt{n}) ≥ c_{4}e^{−λ^{2}} ≥ 2c_{3}e^{−3(λ−c_{2})^{2}/2} .  (2.13)

Substituting (2.12) and (2.13) in (2.10), one concludes that lim inf_{n→∞} C_{n} ≥ C_{∞} > 0 as claimed.

The next lemma provides the bounds on the value of b stated in the introduction.

Lemma 2.5 The limit in (1.3) exists, and the constant b there satisfies the bounds 0.4 ≤ b ≤ 2.

Proof: The existence of the limit in (1.3) was proved in the course of proving Lemma 2.3. Recall that R_{y}(t) ≥ e^{−|t|/2}, the covariance of the stationary Ornstein-Uhlenbeck process X_{·} As can be checked by computing the covariance, a representation of the process {X_{t}} can be obtained as

X_{t} = e^{−t/2}V_{e^{t}} = e^{−t/2}(V_{e^{t}} − V_{1} + V_{1}) = e^{−t/2}(W_{e^{t}−1} + X_{0}) ,  (2.14)

for some standard Brownian motions V_{·}, W_{·} and a standard normal random variable X_{0} that is independent of W_{·}. Hence, for η = (e^{T} − 1)^{−1/2},

P ( sup_{0≤t≤T} X_{t} ≤ 0) = E[1_{X_{0}≤0} P ( sup_{0≤t≤e^{T} −1}{W_{t}} ≤ −X_{0}|X_{0})]
= E[1_{X_{0}≤0} (1 − 2P (W_{e^{T} −1} ≥ −X_{0}|X_{0}))]
= \frac{1}{π} ∫_{−∞}^{0} ∫_{0}^{−ηx} e^{−(x^{2}+y^{2})/2}dydx = \frac{1}{π} arctan(η) = \frac{1}{π} e^{−T/2}(1 + o(1)).

Consequently, Slepian’s lemma implies the bound b ≤ 2.

The proof of the complementary bound is based on the following observation. Suppose that X ∈ ℝ^{n} and Y ∈ ℝ^{n} are zero-mean, normally distributed random vectors with covariance matrices Σ_{x} and Σ_{y} respectively. If Σ_{x} − Σ_{y} is a positive semidefinite matrix, then the Radon-Nikodým

derivative of the law of Y with respect to that of X is at most (det Σ_{x}/ det Σ_{y})^{1/2}, hence

P (Y ∈ C) ≤ (\frac{det Σ_{x}}{det Σ_{y}} )^{1/2}P (X ∈ C),  (2.15)

for all C ⊂ ℝ^{n} (c.f. [Sh, Lemma 3.1]). Indeed, to prove that b ≥ 0.4, it suffices to show that

P ( max_{1≤i≤n} Y_{5i} ≤ 0) ≤ exp(−0.5 n)  (2.16)

for all n ≥ 2. Let

ρ = 2 sech(5/2) = \frac{2e^{−2.5}}{1 + e^{−5}} , λ_{0} = 4 ∑_{i=2}^{∞} sech(5i/2) = 4 ∑_{i=2}^{∞} \frac{e^{−2.5i}}{1 + e^{−5i}}

and (X_{1}, ⋯, X_{n}) be independent normal random variables each having zero mean and variance λ := 1 + 2ρ + λ_{0}. Denote the covariance matrices of (X_{i}, 1 ≤ i ≤ n) and (Y_{5i}, 1 ≤ i ≤ n) by Σ_{x} and Σ_{y}, respectively. It is easy to see that Σ_{x} − Σ_{y} is a dominant principal diagonal matrix and as such it is positive semidefinite. Thus, by (2.15)

P ( max_{1≤i≤n} Y_{5i} ≤ 0) ≤ (\frac{det Σ_{x}}{det Σ_{y}} )^{1/2}P ( max_{1≤i≤n} X_{i} ≤ 0) = \frac{λ^{n/2}2^{−n}}{(det Σ_{y})^{1/2}} .

To estimate det Σ_{y}, let Σ_{n} = (r_{ij}, 1 ≤ i, j ≤ n) be a tri-diagonal matrix with r_{ii} = 1 − λ_{0}, r_{i,i+1} = r_{i−1,i} = ρ and r_{ij} = 0 for other i, j. Then, Σ_{y} − Σ_{n} is a positive semidefinite matrix and hence

det Σ_{y} ≥ det Σ_{n} := D_{n}.

Since D_{n} = (1 − λ_{0})D_{n−1} − ρ^{2}D_{n−2}, direct calculation shows that

D_{n} ≥ (\frac{1}{2}(1 − λ_{0} + \sqrt{(1 − λ_{0})^{2} − 4ρ^{2}}))^{n}.

Putting the above inequalities together yields

P ( max_{1≤i≤n} Y_{5i} ≤ 0) ≤ (\frac{λ}{2(1 − λ_{0} + \sqrt{(1 − λ_{0})^{2} − 4ρ^{2}})})^{n/2}
= exp \{0.5n ln (\frac{λ}{2(1 − λ_{0} + \sqrt{(1 − λ_{0})^{2} − 4ρ^{2}})})\}
≤ exp(−0.5n)

(here, λ = 1.3555 ⋯, ρ = 0.163071 ⋯ and λ_{0} = 0.029361 ⋯).

3 Lower bound for Theorem 1.4

Hereafter let θ_{1}(x) = x, θ_{2}(x) = x^{−1}, θ_{3}(x) = −x^{−1} and θ_{4}(x) = −x be the symmetry transformations preserved by the Gaussian processes f̂_{n}^{b}(x) and let \overline{γ}_{n}(x) = max_{j=1}^{4} γ_{n}(θ_{j}(x)) (with the exception of x = 0 for which \overline{γ}_{n}(0) = γ_{n}(0)). We begin by noting that, with I_{1} = [0, 1], I_{2} = [1, ∞), I_{3} = (−∞, −1] and I_{4} = [−1, 0],

P (f̂_{n}^{b}(x) > γ_{n}(x), ∀x ∈ ℝ) = P (f̂_{n}^{b}(x) > γ_{n}(x), ∀x ∈ I_{1} ∪ I_{2} ∪ I_{3} ∪ I_{4})
≥ ∏_{i=1}^{4} P (f̂_{n}^{b}(x) > γ_{n}(x), ∀x ∈ I_{i})
≥ [P (f̂_{n}^{b}(x) > \overline{γ}_{n}(x), ∀x ∈ [0, 1])]^{4}  (3.1)

where the first inequality follows by Slepian’s lemma due to the positivity of the covariance c_{n}(x, y) of f̂_{n}^{b}, while the second holds because c_{n}(x, y) = c_{n}(−x, −y) = c_{n}(\frac{1}{x}, \frac{1}{y}). Set T = log n. The assumptions of Theorem 1.4 imply the existence of the integers log log T ≪ τ_{T} ≪ T such that δ_{n} := sup\{\overline{γ}_{n}(x) : x ∈ [1 − ξ_{n}, 1]\} → 0 for ξ_{n} = exp(−τ_{T}). Recall also our assumption that sup{γ_{n}(x) : x ∈ ℝ, n} ≤ M < ∞. Applying Slepian’s lemma once more yields that,

P (f̂_{n}^{b}(x) > \overline{γ}_{n}(x), ∀x ∈ [0, 1])
≥ P ( inf_{0≤x≤1−ξ_{n}} f̂_{n}^{b}(x) > M)P (  inf_{1−ξ_{n}≤x≤1−n^{−1}} f̂_{n}^{b}(x) > δ_{n})P ( inf_{1−n^{−1}≤x≤1} f̂_{n}^{b}(x) > M)
:= A_{n}B_{n}C_{n} .  (3.2)

Starting with A_{n}, note that for 1 > x ≥ y ≥ 0 one has

1 ≤ g(x, y) = \frac{1 − xy}{\sqrt{(1 − x^{2})(1 − y^{2})}} ≤ \sqrt{\frac{1 − y}{1 − x}}

and hence, by (2.2), taking x = 1 − e^{−t} and y = 1 − e^{−s} we see that for x, y ∈ [0, 1),

c_{n}(x, y) ≥ \sqrt{\frac{1 − x ∨ y}{1 − x ∧ y}} = e^{−|t−s|/2} .  (3.3)

Recall that exp(−|t − s|/2) is the covariance of the stationary Ornstein-Uhlenbeck process (see (2.14)). In view of (3.3), we have by Slepian’s lemma that

A_{n} = P ( inf_{0≤x≤1−ξ_{n}} f̂_{n}^{b}(x) > M) ≥ P ( inf_{0≤t≤τ_{T}} X_{t} > M) .

Since X_{t} is a centered stationary Gaussian process of positive covariance, yet another application of Slepian’s lemma yields that

lim inf_{n→∞} \frac{log A_{n}}{log n} ≥ lim inf_{T →∞} \frac{τ_{T}}{T} log P ( inf_{0≤t≤1} X_{t} > M) = 0 .  (3.4)

(since the random variable inf_{0≤t≤1} X_{t} is unbounded).

We next turn to the dominant term B_{n}. Setting z = 1 − x, w = 1 − y, for all x, y ∈ [1 − ξ_{n}, 1), n large, it follows from (2.2), (2.3) and Lemma 2.1 that

c_{n}(x, y) ≥ \frac{1}{g(x, y)} ≥ \frac{2\sqrt{zw}}{z + w} [1 − \frac{(z − w)^{2}}{max(z, w)}]

Making yet another change of variables z = e^{−t}, w = e^{−s}, we thus get that for α = e^{−τ_{T}}, in the notations of Lemma 2.2,

c_{n}(x, y) ≥ \frac{2e^{− \frac{|s−t|}{2}}}{1 + e^{−|s−t|}} [1 − α(1 − e^{−|s−t|})^{2}] = R^{(α)}(s − t) .

With R^{(α)}(0) = c_{n}(x, x) = 1, it follows by Slepian’s lemma that

B_{n} ≥ P ( inf_{0≤t≤T} Y_{t}^{(α)} > δ_{n})

Since δ_{n} → 0 and α_{T} log T → 0 by our choice of τ_{T}, it follows by (2.6) of Lemma 2.3 that

lim inf_{n→∞} \frac{log B_{n}}{log n} ≥ −\frac{b}{4} .  (3.5)

Finally, we recall that the sequence C_{n} is bounded away from zero by Lemma 2.4. Combining (3.1), (3.2), (3.4) and (3.5), we thus arrive at the stated lower bound

lim inf_{n→∞} \frac{log P_{n,γ_{n}}^{b}}{log n} ≥ −b ,

of (1.9).

4 Upper bound for Theorem 1.4

Fixing \frac{1}{2} > δ > 0, define the four disjoint intervals I_{1} = [1 − n^{−δ}, 1 − n^{−(1−δ)}] and I_{j} = θ_{j}(I_{1}), j = 2, 3, 4. Let V = ⋃_{j=1}^{4} I_{j} and U = ⋃_{j=1}^{4}{(x, y) : x, y ∈ I_{j}}.

The crucial tool in the proof of the upper bound is the following lemma, whose proof is deferred to the end of this section:

Lemma 4.1 For all n sufficiently large there exist 0 ≤ α_{n} ≤ n^{−δ/2} such that

c_{n}(x, y) ≤ \frac{(1 − α_{n})}{g(x, y)}1_{(x,y)∈U} + α_{n}  ∀x, y ∈ V .  (4.1)

Equipped with Lemma 4.1, we show how to complete the proof of the upper bound. Let {N, b_{i}^{(j)}, j = 1, 2, 3, 4, i = 0, …} be independent, identically distributed standard Normal random variables. For x ∈ I_{1} consider the infinite random polynomials f̂_{∞}^{(j)}(x) = \sqrt{1 − x^{2}} ∑_{i=0}^{∞} b_{i}^{(j)}x^{i} which are for j = 1, 2, 3, 4 well defined i.i.d. centered Gaussian processes of covariance function 1/g(x, y). Recall that g(x, y) is invariant to application of each of the invertible transformations θ_{j}(·), j = 2, 3, 4 on both x and y. Each such transformation is a one to one map of I_{j} to I_{1}. Hence, the right hand side of (4.1) represents the covariance of the centered Gaussian field f̃_{n}(·) defined on V, of the form

f̃_{n}(x) = \sqrt{1 − α_{n}} ∑_{j=1}^{4} 1_{x∈I_{j}} f̂_{∞}(θ_{j}(x)) + \sqrt{α_{n}}N

Observe that the assumptions of Theorem 1.4 imply that η_{n} := n^{−δ/8} ∨ sup{−γ_{n}(x) : x ∈ V } decay to zero as n → ∞. With g(x, x) = 1 for all x ∈ V, relying upon (4.1) and the positivity of 1/g(x, y) we get by two applications of Slepian’s lemma that for all n sufficiently large

P_{n,γ_{n}}^{b} = P (f̂_{n}^{b}(x) < −γ_{n}(x) , ∀x ∈ ℝ) ≤ P (sup_{x∈V} f̂_{n}^{b}(x) ≤ η_{n}) ≤ P (sup_{x∈V} f̃_{n}(x) ≤ η_{n})
≤ P (N ≤ −n^{δ/8}) + ∏_{j=1}^{4} P (sup_{x∈I_{j}} f̂_{∞}(θ_{j}(x)) ≤ \frac{2η_{n}}{\sqrt{1 − α_{n}}} )
≤ e^{−n^{δ/4}/2} + P (sup_{x∈I_{1}} f̂_{∞}(x) ≤ 3η_{n})^{4} .  (4.2)

Hence, it is enough to show that

lim sup_{δ→0} lim sup_{n→∞} \frac{1}{log n} log P (sup_{x∈I_{1}} f̂_{∞}(x) ≤ 3η_{n}) ≤ −\frac{b}{4} .  (4.3)

The change of variables x = 1 − z = 1 − e^{−t}, y = 1 − w = 1 − e^{−s} yields, by (2.3) and Lemma 2.1, that for all sufficiently large n and all x, y ∈ I_{1},

\frac{1}{g(x, y)} ≤ \frac{2\sqrt{zw}}{z + w} = sech(\frac{t − s}{2}) .  (4.4)

For T = log n, T′ = (1 − 2δ)T and ε_{T′} := 3η_{n} → 0, by yet another application of Slepian’s lemma and the stationarity of the process Y_{t} of Lemma 2.2, it follows from (4.4) that

P (sup_{x∈I_{1}} f̂_{∞}(x) ≤ 3η_{n}) ≤ P ( sup_{t∈[δT,(1−δ)T]} Y_{t} ≤ 3η_{n}) ≤ P ( sup_{0≤t≤T′} Y_{t} ≤ ε_{T′}) .  (4.5)

Consequently, by (2.5),

lim sup_{n→∞} \frac{1}{log n} log P (sup_{x∈I_{1}} f̂_{∞}(x) ≤ 3η_{n}) ≤ (1 − 2δ) lim sup_{T →∞} \frac{1}{T} log P ( sup_{0≤t≤T} Y_{t} ≤ ε_{T} ) = −(1 − 2δ)\frac{b}{4}.

(4.6)

Taking δ → 0, we see that (4.6) implies (4.3) hence the proof of the upper bound in (1.9), modulo the proof of Lemma 4.1 which we provide next.

Proof of Lemma 4.1 Considering separately (x, y) ∈ U and (x, y) ∉ U, it is enough by the symmetry relations g(x, y) = g(−x, −y) = g(\frac{1}{x}, \frac{1}{y}) to show that

g(x^{n}, y^{n}) ≤ (1 − α_{n}) + α_{n}g(x, y),  x, y ∈ I_{1}  (4.7a)
g(x^{n}, y^{n}) ≤ α_{n}g(x, y),  x ∈ I_{1}, y ∈ I_{j}, j ≠ 1  (4.7b)

Turning first to (4.7a), recall that g(x, y) is a symmetric function, which equals 1 on the diagonal x = y. We thus may and shall take without loss of generality y > x. Fixing x ∈ I_{1}, the change of variables y = y(η) = 1 − (1 − x)(1 − η)^{2} for η ∈ (0, 1) then corresponds to η = 1 − \sqrt{w/z} where z = 1 − x and w = 1 − y. It follows from (4.4) that for all n sufficiently large,

g(x, y) − 1 ≥ \frac{z + w}{2\sqrt{zw}} − 1 = \frac{1}{2}(1 − \sqrt{\frac{w}{z}} )^{2} = \frac{η^{2}}{2} .

Moreover, when n is large enough,

\sqrt{1 − x^{2n}}\sqrt{1 − y^{2n}} ≥ \frac{2}{3}  ∀x, y ∈ I_{1}  (4.8)

So that,

\frac{g(x^{n}, y^{n}) − 1}{g(x, y) − 1} ≤ \frac{2}{η^{2}} \frac{1 − x^{n}y^{n} − \sqrt{1 − x^{2n}} \sqrt{1 − y^{2n}}}{\sqrt{1 − x^{2n}} \sqrt{1 − y^{2n}}} ≤ \frac{3}{η^{2}} h(η) ,  (4.9)

where

h(η) := 1 − x^{n}y(η)^{n} − \sqrt{1 − x^{2n}} \sqrt{1 − y(η)^{2n}} .

Note that y(0) = x, hence h(0) = 0. It is not hard to check that h′(0) = 0 and

h′′(ξ) = ny′′(ξ)[\begin{matrix}√ & \overline{1 − x^{2n}} \\ √ & \overline{1 − y^{2n}} \end{matrix} y^{2n−1} − x^{n}y^{n−1}]

+ny′(ξ)^{2}[(2n − 1)y^{2n−2} \begin{matrix}√ & \overline{1 − x^{2n}} \\ √ & \overline{1 − y^{2n}} \end{matrix} + \frac{ny^{4n−2}}{1 − y^{2n}} \begin{matrix}√ & \overline{1 − x^{2n}} \\ √ & \overline{1 − y^{2n}} \end{matrix} − (n − 1)x^{n}y^{n−2}] ,

evaluated at y = y(ξ). Observing that |y′(ξ)| ≤ 2, y′′(ξ) ∈ [−2, 0] and x^{n} ≤ y(ξ)^{n} ≤ y(η)^{n} ≤ e^{−n^{δ}} for all ξ ∈ [0, η], it is easy to check that there exists a universal finite constant c_{1} such that

sup_{ξ∈[0,η]} h′′(ξ) ≤ c_{1}y(η)^{n} ≤ c_{1}e^{−n^{δ}} ,

for all n large enough and any x, y ∈ I_{1}. Hence, h(η) ≤ \frac{1}{2}c_{1}e^{−n^{δ}}η^{2}. Substituting in (4.9), we conclude that

sup_{x,y∈I_{1}} \frac{g(x^{n}, y^{n}) − 1}{g(x, y) − 1} ≤ 2c_{1}e^{−n^{δ}}

proving (4.7a).

Turning to the proof of (4.7b) we assume first that x ∈ I_{1} and y ∈ I_{2} ∪ I_{3}. Then, x, |y|^{−1} ∈ I_{1} with \sqrt{1 − x^{2}}\sqrt{1 − y^{−2}} ≤ 1 and (4.8) holding for x and y^{−1}. Moreover, x^{n} ∨ |y|^{−n} ≤ e^{−n^{δ}}, so we have in this case that

\frac{g(x^{n}, y^{n})}{g(x, y)} ≤ \frac{3}{2} \frac{|x^{n} − y^{−n}|}{|x − y^{−1}|} ≤ \frac{3}{2} ∑_{k=0}^{n−1} x^{k}|y|^{−(n−1−k)} ≤ 2ne^{−n^{δ}} .

In the remaining case of x ∈ I_{1} and y ∈ I_{4} we have that |y|^{n} ≤ e^{−n^{δ}}, hence g(x^{n}, y^{n}) ≤ 2 while

\frac{1}{g(x, y)} = \frac{\sqrt{1 − x^{2}}\sqrt{1 − y^{2}}}{1 + |xy|} ≤ [1 − (1 − n^{−δ})^{2}] ≤ 2n^{−δ},

thus completing the proof of (4.7b).

5 Proof of Theorem 1.3

Our proof of Theorem 1.3 combines the Komlós-Major-Tusnády strong approximation theorem with Theorem 1.4. To this end, note that for every k and |x| ≤ 1, the sequence {(1 − x^{2})x^{2j} : j = 0, …, k − 1} ∪ {x^{2k}} is a probability distribution, hence for any real valued s_{j},

|s_{0} + ∑_{j=1}^{k}(s_{j} − s_{j−1})x^{2j}| = |s_{k}x^{2k} + (1 − x^{2}) ∑_{j=0}^{k−1} s_{j}x^{2j}| ≤ max_{0≤j≤k} |s_{j}| .  (5.1)

Recall that E(a_{i}) = 0 and E(a_{i}^{2}) = 1. Hence, applying the strong approximation theorem of [KMT] twice we can redefine {a_{i}, 0 ≤ i ≤ n−1} on a new probability space with a sequence of independent standard normal random variables {b_{i}, 0 ≤ i ≤ n − 1} such that for any p ≥ 2, some c_{p} < ∞, all t > 0 and n,

P ( max_{0≤j≤(n−1)/2} |∑_{i=0}^{j} a_{2i} − ∑_{i=0}^{j} b_{2i}| ≥ t)+P ( max_{0≤j≤(n−2)/2} |∑_{i=0}^{j} a_{2i+1} − ∑_{i=0}^{j} b_{2i+1}| ≥ t) ≤ c_{p}nE|a_{0}|^{p}t^{−p}.

(5.2)

Let

g_{k}(x) := x^{k−1}f_{k}(x^{−1}) = ∑_{i=0}^{k−1} a_{i}x^{k−1−i} ,

and for k ∈ {1, …, n}, define

f_{k}^{b}(x) = ∑_{i=0}^{k−1} b_{i}x^{i} , g_{k}^{b}(x) = x^{k−1}f_{k}^{b}(x^{−1}) .

Let σ_{k}(x) := \sqrt{E(f_{k}(x)^{2})} = \sqrt{|1 − x^{2k}|/|1 − x^{2}|}, when |x| ≠ 1 with σ_{k}(±1) = \sqrt{E(f_{k}(±1)^{2})} = \sqrt{k}. Define f̂_{k}(x) := f_{k}(x)/σ_{k}(x) and f̂_{k}^{b}(x) := f_{k}^{b}(x)/σ_{k}(x). As σ_{k}(x) = \sqrt{E(g_{k}(x)^{2})}, we shall also use ĝ_{k}(x) = g_{k}(x)/σ_{k}(x) and ĝ_{k}^{b}(x) = g_{k}^{b}(x)/σ_{k}(x). Since

|∑_{i=0}^{k} a_{i}x^{i} − ∑_{i=0}^{k} b_{i}x^{i}| ≤ | ∑_{j=0}^{⌊k/2⌋}(a_{2j} − b_{2j})x^{2j}| + | ∑_{j=0}^{⌊(k−1)/2⌋}(a_{2j+1} − b_{2j+1})x^{2j+1}|  (5.3)

we get from (5.2) by two applications of (5.1) (using once s_{j} = ∑_{i=0}^{j}(a_{2i} − b_{2i}) and once s_{j} = ∑_{i=0}^{j}(a_{2i+1} − b_{2i+1})) that for all k ≤ n,

P ( sup_{|x|≤1} |f_{k}(x) − f_{k}^{b}(x)| ≥ 2t) ≤ c_{p}nE|a_{0}|^{p}t^{−p}  (5.4)

The same construction of {b_{i}} leads by a similar argument also to

P ( sup_{|x|≤1} |g_{k}(x) − g_{k}^{b}(x)| ≥ 4t) ≤ c_{p}nE|a_{0}|^{p}t^{−p}  (5.5)

Indeed, bounding g_{k} − g_{k}^{b} amounts to changing (a_{i}, b_{i}) to (a_{k−1−i}, b_{k−1−i}), resulting with using once s_{j} = ∑_{i=0}^{j}(a_{k−1−2i} − b_{k−1−2i}) and once s_{j} = ∑_{i=0}^{j}(a_{k−1−2i−1} − b_{k−1−2i−1}). One controls all these as before, but for doubling the total approximation error.

In order to apply effectively the strong approximation results, we need that contributions to the value of f_{n}(x) come from many variables. This obviously is easier for ||x| − 1| small. In order to avoid appearance of zeros in other locations, we decompose f_{n} to the dominant “bulk term”, which will not be too negative everywhere and will be rather far from 0 for ||x| − 1| small, and to “boundary terms”, which involve a small number of coefficients and thus can be made to have prescribed positive values with a not too small probability.

In order to define precisely the different regions considered for values of x and the splitting into bulk and boundary terms, we introduce, for n large enough odd integers, a few n-dependent parameters as follows:

p_{n} :  p_{n} ↑ ∞, c_{p_{n}}E|a_{0}|^{p_{n}} ≤ n  c_{p} is the KMT constant in (5.2).
ϵ = ϵ_{n} : ϵ_{n} ↓ 0, ϵ_{n} ≥ max{20/p_{n}, (log n)^{−1/2}},  ϵ_{n} is taken as the smallest possible
2n^{3ϵ_{n}} = 2^{j} for some j integer  value satisfying constraints.
m = m_{n} : m_{n} → ∞, m_{n} = 2n^{3ϵ_{n}}  m_{n} is an integer power of 2.
γ̄_{n}(x) : γ̄_{n} → 0, γ̄_{n}(x) = max{0, γ_{n}(x), γ_{n}(x^{−1})} γ_{n}(x) as in statement of theorem.
ρ_{n} :  ρ_{n} → 0, ρ_{n} = sup_{|x|≤1−m^{−1}} {σ_{n}(x)γ̄_{n}(x)} ρ_{n} ≤ cn^{−δ/2}, some finite c > 0.
r = r_{n} : cn^{−δ/2}  for n ≥ 3m; c is as in bound on ρ_{n}.
ξ_{n}(x) :  ξ_{n}(x) = 6x^{m}σ_{n−2m}(x)γ̄_{n}(x)

(5.6)

In order to state the decomposition alluded to above, first partition the interval [−1, 1] to I = {x : |x| ≥ 1 − 0.5n^{−ϵ}} and I^{c} = [−1, 1] \ I. We note that 2r + ξ_{n}(x) ≥ σ_{n}(x)γ̄_{n}(x) for all x ∈ I. Next, let f_{n} = f_{n}^{L} + f_{n}^{M} + f_{n}^{H} where

f_{n}^{L}(x) = ∑_{i=0}^{m−1} a_{i}x^{i},  f_{n}^{M}(x) = ∑_{i=m}^{n−1−m} a_{i}x^{i},  f_{n}^{H}(x) = ∑_{i=n−m}^{n−1} a_{i}x^{i} .  (5.7)

Similarly, we let g_{n} = g_{n}^{L} + g_{n}^{M} + g_{n}^{H} with g_{n}^{L}(x) = x^{n−1}f_{n}^{L}(x^{−1}), etc. With these definitions, we have the inclusions

{f̂_{n}(x) > γ_{n}(x), ∀ x ∈ ℝ} ⊃ {f̂_{n}(x) > γ̄_{n}(x), ĝ_{n}(x) > γ̄_{n}(x), ∀ x ∈ [−1, 1]}
⊃ {f_{n}^{M}(x) > ξ_{n}(x), g_{n}^{M}(x) > ξ_{n}(x), ∀ x ∈ I}
∩{f_{n}^{M}(x) > −r, g_{n}^{M}(x) > −r, ∀ x ∈ I^{c}}
∩{f_{n}^{L}(x) > 3r, g_{n}^{L}(x) ≥ −r, ∀x ∈ [−1, 1]}
∩{f_{n}^{H}(x) ≥ −r, g_{n}^{H}(x) > 3r, ∀x ∈ [−1, 1]}

(f_{n}^{M}, g_{n}^{M} are the “bulk terms” whereas f_{n}^{L}, g_{n}^{L}, f_{n}^{H}, g_{n}^{H} are the “boundary terms”). Since the polynomial pairs (f_{n}^{L}, g_{n}^{L}), (f_{n}^{M}, g_{n}^{M}) and (f_{n}^{H}, g_{n}^{H}) are mutually independent, it follows that

P_{n,γ_{n}} = P (f̂_{n}(x) > γ_{n}(x), ∀ x ∈ ℝ)
≥ P ({f_{n}^{M}(x) > ξ_{n}(x), g_{n}^{M}(x) > ξ_{n}(x), ∀ x ∈ I} ∩ {f_{n}^{M}(x) > −r, g_{n}^{M}(x) > −r, ∀ x ∈ I^{c}})
P (f_{n}^{L}(x) > 3r, g_{n}^{L}(x) ≥ −r, ∀ x ∈ [−1, 1])
P (f_{n}^{H}(x) ≥ −r, g_{n}^{H}(x) > 3r, ∀ x ∈ [−1, 1])  (5.8)

Note that g_{n}^{M} and f_{n}^{M} are identically distributed, as are the polynomial pairs x^{−m}(f_{n}^{M}, g_{n}^{M}) and (f_{n−2m}, g_{n−2m}). Thus, we have that

P ({f_{n}^{M}(x) > ξ_{n}(x), g_{n}^{M}(x) > ξ_{n}(x), ∀ x ∈ I} ∩ {f_{n}^{M}(x) > −r, g_{n}^{M}(x) > −r, ∀ x ∈ I^{c}})

≥ P (f̂_{n−2m}(x) > 6γ̄_{n}(x), ĝ_{n−2m}(x) > 6γ̄_{n}(x), ∀ x ∈ I) − 2P (f_{n}^{M}(x) ≤ −r, for some x ∈ I^{c})
:= Q_{1} − 2Q_{2}

Since the polynomial pairs (f_{n}^{L}, g_{n}^{L}), (g_{n}^{H}, f_{n}^{H}) and (f_{m}, x^{n−m}g_{m}) have identical laws, it now follows that

P_{n,γ_{n}} ≥ (Q_{1} − 2Q_{2})(Q_{3} − Q_{4})^{2} ,

where

Q_{3} := P (f_{m}(x) > 3r, ∀ x ∈ [−1, 1], x^{n−m}g_{m}(x) ≥ −r, ∀ |x| ∈ [1 − m^{−1}, 1]) ,

and

Q_{4} := P (x^{n−m}g_{m}(x) ≤ −r, for some |x| ≤ 1 − m^{−1}).

To deal with the dominant term Q_{1}, we consider (5.4) and (5.5) for p = p_{n} as above, k = n − 2m, and t = n^{ϵ/4}. Noting that η_{n} = sup{6γ̄_{n}(x) + 4t/σ_{n−2m}(x) : x ∈ I} approaches zero as n → ∞, we get that for all n large enough,

Q_{1} ≥ P (f̂_{n−2m}^{b}(x) > η_{n}, ĝ_{n−2m}^{b}(x) > η_{n}, ∀ x ∈ I) − 2n^{−3}
≥ P (f_{n−2m}^{b}(x) > η_{n}σ_{n−2m}(x),  ∀ ||x| − 1| ≤ n^{−ϵ_{n}}) − 2n^{−3}
≥ (n − 2m)^{−b+o(1)},  (5.9)

where the last inequality follows by applying Theorem 1.4 for threshold η_{n} → 0 for ||x| − 1| ≤ n^{−ϵ_{n}} and zero otherwise.

Turning to estimate Q_{2}, recall that f_{n}^{M} has the same distribution as x^{m}f_{n−2m} and m = 2n^{3ϵ}. Recall also that ϵ ≥ (log n)^{−1/2}, implying that n^{c} exp(−n^{ϵ}) → 0 for any fixed c < ∞. Hence, for all n large enough,

Q_{2} ≤ P ( sup_{x∈I^{c}} |x|^{m}|f_{n−2m}(x)| ≥ r)
≤ P ( sup_{x∈I^{c}} |f_{n−2m}(x)| ≥ cn^{−δ/2}(1 − \frac{1}{2n^{ϵ}} )^{2n^{3ϵ}}) ≤ P ( sup_{x∈I^{c}} |f_{n−2m}(x)| ≥ 2 exp(n^{ϵ})).

Observe that for any x, y ∈ [−1, 1],

E (|f_{n−2m}(x) − f_{n−2m}(y)|^{2}) ≤ ∑_{i=1}^{n}(x^{i} − y^{i})^{2} ≤ (x − y)^{2}n^{3} .

Recall the following well known lemma (see [Sto] for a proof).

Lemma 5.1 Let {T_{x}, x ∈ [a, b]} be an a.s. continuous stochastic process with T_{a} = 0. Assume that

∀ x, y ∈ [a, b], E|T_{x} − T_{y}|^{2} ≤ K(x − y)^{2}.

Then, we have

E( sup_{x∈[a,b]} T_{x}^{2}) ≤ 4K(b − a)^{2}.

Applying Lemma 5.1 for T_{x} = f_{n−2m}(x) − f_{n−2m}(0), first when x ∈ [0, 1], then when x ∈ [−1, 0], we get by Markov’s inequality that for all n large enough, and any c_{1} < ∞ (for our use, c_{1} = 3 will do),

Q_{2} ≤ P (|a_{0}| ≥ exp(n^{ϵ}))+P ( sup_{|x|≤1} T_{x}^{2} ≥ exp(2n^{ϵ})) ≤ exp(−2n^{ϵ})(1+E( sup_{|x|≤1} T_{x}^{2})) = o(n^{−c_{1}}) . (5.10)

Recall that m = 2n^{ϵ_{n}} and ϵ_{n} → 0, so with g_{m} and f_{m} of identical law, it follows that for all n large enough,

Q_{4} ≤ P ( sup_{|x|≤1−m^{−1}} |x|^{n−m}|f_{m}(x)| ≥ r) ≤ P ( sup_{|x|≤1−m^{−1}} |f_{m}(x)| ≥ 2 exp(\sqrt{n})).

Similarly to the derivation of (5.10), by twice applying Lemma 5.1 for T_{x} = f_{m}(x) − f_{m}(0), then using Markov’s inequality, we get that Q_{4} ≤ exp(−n^{1/3}) for all n large enough. The lower bound P_{n,γ_{n}} ≥ n^{−b+o(1)} in Theorem 1.3 is thus a direct consequence of the bounds (5.9), (5.10) and Lemma 5.2 below which provides the estimate Q_{3} ≥ n^{−c_{2}ϵ} with ϵ = ϵ_{n} → 0 and c_{2} < ∞ fixed.

Turning to the upper bound P_{n,γ_{n}} ≤ n^{−b+o(1)} in Theorem 1.3, let η_{n} := inf{γ_{n}(x) : ||x| − 1| ≤ n^{−ϵ}}. Recall that η_{n} → 0 by our assumptions. Then, similarly to the derivation of (5.9), now with m = 0, we see that for all n large enough

P_{n,γ_{n}} = P (f̂_{n}(x) > γ_{n}(x), ∀ x ∈ ℝ)
≤ P (f̂_{n}(x) > η_{n}, ĝ_{n}(x) > η_{n}, ∀ x ∈ I)
≤ P (f̂_{n}^{b}(x) > η_{n} − n^{−ϵ/8}, ĝ_{n}^{b}(x) > η_{n} − n^{−ϵ/8}, ∀ x ∈ I) + 2n^{−3}
≤ n^{−b+o(1)}

(the last inequality follows by Theorem 1.4 for a threshold η_{n} − n^{−ϵ_{n}/8} when x ∈ I ∪ {x : x^{−1} ∈ I} and −∞ otherwise).

Lemma 5.2 Suppose a_{i} are i.i.d. with E(a_{0}) = 0 and E(a_{0}^{2}) = 1. There exists c < ∞ such that for all m = 2^{k+1} and k large enough,

P (f_{m}(x) > m^{−2}, ∀ x ∈ [−1, 1] ,  xg_{m}(x) ≥ 0, ∀ |x| ∈ [1 − 2^{−k}, 1]) ≥ m^{−c}  (5.11)

Proof: Define the intervals J_{j} = {x : 1 − 2^{−j} ≤ |x| ≤ 1 − 2^{−j−1}} for j = 1, …, k − 1 and J_{k} = {x : 1 − 2^{−k} ≤ |x| ≤ 1}. Throughout this proof, l_{j} := 2^{j} for integer j, and complements are taken inside the interval [−1, 1].

The proof of the lemma is based on decomposing f_{m} to a sum (over a number of terms logarithmic in m) of polynomials f^{j}, such that for each x ∈ J_{j}, f^{j}(x) is large while f^{i}(x), i ≠ j are not too large; at the same time, g_{m}(x) is decomposed to a sum of polynomials all but the highest order of which are large and positive on J_{k}, while the latter is not too negative on J_{k}. Unfortunately, we need to introduce a few constants in order to define explicitly this decomposition.

Note first that for some c_{0} < ∞ which does not depend on k,

(c_{0} − 1)2^{j/2}x^{l_{j}} − ∑_{i=4,i≠j}^{k} 2^{i/2}x^{l_{i}} ≥ 0 ,  ∀x ∈ J_{j}, j = 4, …, k  (5.12)

Define c_{1} = c_{0} + 1. In Lemma 5.3 below, we define a constant θ_{1} = θ_{1}(c_{1}) > 0. Define then θ = P (|N| ≤ 1)θ_{1}/2 > 0 where N is a standard Gaussian random variable of zero mean and unit variance. Since E(a_{0}) = 0, E(a_{0}^{2}) = 1, we can use Strassen’s weak approximation theorem (see [Str] or [CS, Page 89]), to deduce the existence of independent standard normal random variables {b_{i}, i ≥ 0} such that, for all j ≥ j_{0},

P ( max_{0≤ℓ≤2^{j}} |∑_{i=0}^{ℓ} a_{2i} − ∑_{i=0}^{ℓ} b_{2i}| + max_{0≤ℓ≤2^{j}} |∑_{i=0}^{ℓ} a_{2i+1} − ∑_{i=0}^{ℓ} b_{2i+1}| ≥ 2^{j/2−3}) ≤ θ.  (5.13)

Finally, since Ea = 0 and Ea^{2} = 1 there exists α > 0 such that P (|a − α| ≤ δ) > 0. Fixing such α, define s > j_{0} such that

\frac{α}{10} − ∑_{i=s}^{∞} 2^{i/2}x^{l_{i}} ≥ 0,  ∀x ∈ J_{0} := \{x : |x| ≤ 1 − 2^{−s}\}.  (5.14)

Such an s always exists because the sum in (5.14) tends to 0 in s. Note that s does not depend on k and all estimates above are valid uniformly for all k large enough. We write l := l_{s} and note that {J_{0}, J_{s}, J_{s+1}, …, J_{k}} form a partition of the interval [−1, 1]. We keep s fixed throughout the rest of the proof.

As mentioned above, the proof of the lemma is based on decomposing f_{m} to a sum (over k − s + 2 terms, i.e. a number of terms logarithmic in m) of polynomials f^{j}, j = 0, s, s + 1, …, k, while decomposing g_{m}(x) to a similar sum of k − s + 2 polynomials. Specifically, we write

f_{m}(x) = f^{0}(x) + ∑_{j=s}^{k} x^{l_{j}}f^{j}(x)

where f^{0} = f_{l_{s}} and

f^{j}(x) = ∑_{i=0}^{2^{j}−1} a_{i+l_{j}}x^{i} .

Similarly,

g_{m}(x) = x^{m−l_{s}}g^{0}(x) + ∑_{j=s}^{k} x^{m−l_{j+1}}g^{j}(x)

where g^{0} = g_{l_{s}} and

g^{j}(x) = ∑_{i=0}^{2^{j}−1} a_{i+l_{j}}x^{2^{j}−1−i} .

One checks that for k large enough, it holds that

m^{−2} ≤ min\{\frac{α}{10}, inf_{x∈J_{j},j=s,...,k} 2^{j/2}x^{l_{j}}\} .  (5.15)

Moreover, by (5.12), for all k ≥ s,

(c_{0} − 1)2^{j/2}x^{l_{j}} − ∑_{i=s,i≠j}^{k} 2^{i/2}x^{l_{i}} ≥ 0 ,  ∀x ∈ J_{j}, j = s, …, k  (5.16)

It follows that

{f_{m}(x) > m^{−2}, ∀ x ∈ [−1, 1]} ⊃ ⋂_{j=s}^{k}{f^{j}(x) > c_{0}2^{j/2}, ∀ x ∈ J_{j}, f^{j}(x) ≥ −2^{j/2}, ∀ x ∈ J_{j}^{c}}
⋂ \{f^{0}(x) > \frac{α}{5}, ∀ x ∈ J_{0}, f^{0}(x) ≥ 0, ∀ x ∈ J_{0}^{c}\} . (5.17)

Note that for all x ∈ [−1, 1],

{xg_{m}(x) ≥ 0} ⊃ {xg^{0}(x) ≥ −2^{k/2}} ⋂_{j=s}^{k}{xg^{j}(x) ≥ c_{0}2^{j/2}} .  (5.18)

The polynomial pairs (f^{j}, g^{j}), j = 0, s, …, k are mutually independent, with (f^{0}, g^{0}) having the same law as (f_{l}, g_{l}), while (f^{j}, g^{j}) has the same law as (f_{2^{j}}, g_{2^{j}}) for each j ≠ 0. It thus follows from (5.17) and (5.18) that

P (f_{m}(x) > m^{−2}, ∀ x ∈ [−1, 1] , xg_{m}(x) ≥ 0, ∀ x ∈ J_{k})
≥ P (f_{l}(x) > \frac{α}{5}, ∀ x ∈ J_{0}, f_{l}(x) ≥ 0, ∀ x ∈ J_{0}^{c}, xg_{l}(x) ≥ −2^{k/2}, ∀ x ∈ J^{k})
∏_{j=s}^{k} P (f_{2^{j}}(x) > c_{0}2^{j/2}, ∀ x ∈ J_{j}, f_{2^{j}}(x) ≥ −2^{j/2}, ∀ x ∈ J_{j}^{c}, xg_{2^{j}}(x) ≥ c_{0}2^{j/2}, ∀ x ∈ J_{k})
:= η_{s,k} ∏_{j=s}^{k} q_{j} ,  (5.19)

where

η_{s,k} := P (f_{l}(x) > α/5, ∀ x ∈ J_{0}, f_{l}(x) ≥ 0, ∀ x ∈ J_{0}^{c}, xg_{l}(x) ≥ −2^{k/2}, ∀ x ∈ J^{k}) . (5.20)

We first show that η_{s,k} is uniformly (in k, for k ≥ 2 log_{2}(2αl)), bounded away from zero, and then provide a uniform (in k) bound (independent of j) on q_{j}. Toward the first goal, let Q_{s}(x) := α(1+x+⋯+x^{l_{s}−1}), noting that Q_{s}(x) is monotone increasing on [−1, 1], with Q_{s}(−(1−2^{−s})) ≥ α/4, implying that Q_{s}(x) ≥ α/4 for all x ∈ J_{0}. Thus, for each s ≥ 1 there exists δ_{s} ∈ (0, α) such that f_{l_{s}}(x) > α/5 whenever x ∈ J_{0} and |a_{i} − α| ≤ δ_{s} for i = 0, …, l_{s} − 1. Further taking a_{2i} ≥ a_{2i+1} ≥ 0 for i = 0, …, 2^{s−1} − 1 guarantees that f_{l_{s}}(x) ≥ 0 for all x ∈ [−1, 1]. Considering only such {a_{i}}, we also have that |xg_{l}(x)| ≤ 2αl, and hence, combining the above and using 2^{k/2} ≥ 2αl, we have that

lim inf_{k→∞} η_{s,k} > 0 .  (5.21)

To estimate q_{j}, we note that xg_{2^{j}}^{b} = x^{2}g_{2^{j}−1}^{b} + xb_{2^{j}−1}. Thus, combining (5.1), (5.3) and (5.13), it follows that for all j ∈ {s, …, k},

q_{j} ≥ P (|b_{2^{j}−1}| ≤ 1)q_{j}^{b} − θ  (5.22)

where

q_{j}^{b} := P (f_{2^{j}−1}^{b}(x) ≥ c_{1}2^{j/2}, ∀ x ∈ J_{j}, f_{2^{j}−1}^{b}(x) ≥ −2^{(j−1)/2}, ∀ x ∈ J_{j}^{c}, g_{2^{j}−1}^{b}(x) ≥ c_{1}2^{j/2}, ∀ x ∈ J_{k}) .

for say, c_{1} = c_{0} + 1. Slepian’s lemma thus yields that for all k ≥ j ≥ s,

q_{j}^{b} ≥ P (f_{2^{j}−1}^{b}(x) ≥ c_{1}2^{j/2}, ∀x ∈ [1 − 2^{−j}, 1])^{4}P (f_{2^{j}−1}^{b}(x) ≥ −2^{(j−1)/2}, ∀x ∈ [0, 1 − 2^{−j}])^{2} := q̄_{j}^{b}.

Note that q̄_{j}^{b} does not depend on k, and in fact it depends on c_{1} and j only. The following lemma provides estimates on q̄_{j}^{b} while defining the constant θ_{1}:

Lemma 5.3 There exists a constant θ_{1} > 0 such that for all j ≥ 4,

q̄_{j}^{b} ≥ θ_{1} .

Applying (5.22) using θ = \frac{1}{2}P (|b| ≤ 1)θ_{1} then leads to q^{j} ≥ θ for all j ≥ s. In view of (5.21) and (5.19) this proves (5.11). Proof of Lemma 5.3: Note that σ_{2^{j}−1}(x) ≥ 2^{j/2−1} when x ∈ [1 − 2^{−j}, 1], hence by Lemma 2.4, for some ξ_{1} > 0 and all j large enough,

P (f_{2^{j}−1}^{b}(x) ≥ c_{1}2^{j/2}, ∀x ∈ [1 − 2^{−j}, 1]) ≥ P (f̂_{2^{j}−1}^{b}(x) ≥ 2c_{1}, ∀x ∈ [1 − 1/(2^{j} − 1), 1]) ≥ ξ_{1} .

Note that σ_{2^{j}−1}(x) ≤ 1/\sqrt{1 − x} ≤ 2^{i/2} for x ∈ [0, 1 − 2^{−i}]. Hence, by Slepian’s lemma and (3.3), we have that for the Ornstein-Uhlenbeck process X_{t} of (2.14),

P (f_{2^{j}−1}^{b}(x) ≥ −2^{(j−1)/2}, ∀x ∈ [0, 1 − 2^{−j}])
≥ ∏_{i=0}^{j−1} P (f_{2^{j}−1}^{b}(x) ≥ −2^{(j−1)/2}, ∀x ∈ [1 − 2^{−i}, 1 − 2^{−i−1}])

≥ ∏_{i=0}^{j−1} P (X_{t} ≥ −2^{(j−i)/2−1}, ∀t ∈ [i ln 2, (i + 1) ln 2])

= ∏_{l=1}^{j} P ( inf_{0≤t≤ln 2} X_{t} ≥ −2^{l/2−1})

≥ ∏_{l=1}^{∞} [1 − P ( sup_{0≤t≤ln 2} X_{t} ≥ 2^{l/2−1})] =: ξ_{2}

and ξ_{2} > 0 since E(sup_{t∈[0,ln 2]} X_{t}) < ∞. This completes the proof.

6 Proof of Theorem 1.1

Part a) of Theorem 1.1 is a direct consequence of Theorem 1.3 with γ_{n} = 0. Thus, it only remains to prove part b). Fixing μ ≠ 0, it is easy to see that

P_{n}^{μ} = P (f̂_{n}(x) ≠ −μκ_{n}(x), ∀x ∈ ℝ) ,

where the nonrandom κ_{n}(x) = (∑_{i=0}^{n−1} x^{i})(∑_{i=0}^{n−1} x^{2i})^{−1/2} are strictly positive and f̂_{n}(x) are the normalized polynomials that correspond to a_{i} of zero mean. With P̃_{n} for the value of P_{n} when coefficients {−a_{i}} are used instead of {a_{i}}, it is easy to see that

P_{n}^{μ} = P_{n,−μκ_{n}} + P̃_{n,μκ_{n}} .

Consequently, we may and shall assume without loss of generality that μ > 0, proving only that P_{n,−μκ_{n}} = n^{−b/2+o(1)}. Observe that κ_{n}(1) = \sqrt{n}, κ_{n}(−1) = 1/\sqrt{n} and if |x| ≠ 1 then,

κ_{n}(x) = κ_{n}(x^{−1}) = κ_{n}(−x)^{−1} = [\frac{(1 + x)(1 − x^{n})}{(1 − x)(1 + x^{n})}]^{1/2} .  (6.1)

Moreover, there exists c = c(μ) > 0 such that for all n large enough,

μκ_{n}(x) ≥ n^{−ϵ/8} + \frac{c}{\sqrt{1 − x}}  ∀x ∈ [0, 1 − n^{−1}] .  (6.2)

For an upper bound on P_{n,−μκ_{n}} let I_{−} = [−1, −1 + 0.5n^{−ϵ}] be the subset of I of Section 5 near the point −1 and V_{−} = I_{3} ∪ I_{4} be the (corresponding) subset of V of Section 4. It is easy to check that

sup{κ_{n}(x) : x ∈ I_{−}} ≤ c_{1}n^{−ϵ/2}

for some c_{1} < ∞ and all n. Hence, applying the arguments of Section 5 followed by those of Section 4 with I_{−} replacing I and V_{−} replacing V, respectively, results in the stated upper bound P_{n,−μκ_{n}} ≤ n^{−b/2+o(1)}. Turning to prove the corresponding lower bound on P_{n,−μκ_{n}}, let I_{+} = [1 − 0.5n^{−ϵ}, 1] denote the subset of I near the point +1. It follows from (6.1) that ρ_{n} of (5.6) is zero for γ_{n} = −μκ_{n}, allowing for the use of r_{n} = n^{−1} and ξ_{n}(x) = −μx^{m}σ_{n−2m}(x)κ_{n}(x) ≤ 0 in (5.8). We then deal with the terms Q_{2}, Q_{3} and Q_{4} as in Section 5. For the dominant term Q_{1}, instead of (5.9) we have in view of (6.2) that

Q_{1} ≥ P (f̂_{n′}^{b}(x) > n^{−ϵ/8}, ĝ_{n′}^{b}(x) > n^{−ϵ/8}, ∀ x ∈ [−1, 0] ∪ [1 − \frac{1}{n′} , 1],

f̂_{n′}^{b}(x) > −\frac{c}{\sqrt{1 − x}}, ĝ_{n′}^{b}(x) > −\frac{c}{\sqrt{1 − x}}, ∀ x ∈ [0, 1 − \frac{1}{n′}]) − 2n^{−3}

= Q̃_{1} − 2n^{−3},  (6.3)

where n′ := n − 2m = n(1 + o(1)). By Slepian’s lemma, similarly to (3.1) we see that

Q̃_{1} ≥ P (f̂_{n′}^{b}(x) > −\frac{c}{\sqrt{1 − x}} ∀ x ∈ [0, 1 − \frac{1}{n′}])^{2}

P (f̂_{n′}^{b}(x) > n^{−ϵ/8} ∀ x ∈ [0, 1])^{2}P (f̂_{n′}^{b}(x) > 1 ∀ x ∈ [1 − \frac{1}{n′} , 1])^{2}

:= (A_{n′})^{2}(B_{n′})^{2}(C_{n′})^{2} .  (6.4)

The sequence C_{n′} is bounded away from zero by Lemma 2.4. Moreover, it is shown in Section 3 that B_{n} ≥ n^{−b/4+o(1)}. In view of (6.3) and (6.4), it thus suffices to show that the sequence A_{n} is bounded below by some A_{∞} > 0 in order to conclude that P_{n}^{μ} ≥ P_{n,−μκ_{n}} ≥ n^{−b/2+o(1)} and complete the proof of part b) of Theorem 1.1. To this end, recall that the function \sqrt{(1 − x ∨ y)/(1 − x ∧ y)} in the right side of (3.3) is the covariance of the process W_{1−x}/\sqrt{1 − x}. Consequently, we have by (3.3) and Slepian’s lemma that

A_{n} ≥ P (W_{1−x} > −c, ∀x ∈ [0, 1 − n^{−1}]) ≥ P ( inf_{0≤x≤1} W_{x} > −c) = A_{∞} > 0 ,

as needed.

7 Upper bound for Theorem 1.2

Fixing small δ > 0 and integers k_{n} = o(log n/ log log n), it suffices for the upper bound in Theorem 1.2 to provide an n^{−(1−2δ)b+o(1)} upper bound on the probability q_{n,k} that f(x) = f̂_{n+1}(x) has at most k = k_{n} zeros in the set V = ∪_{i=1}^{4}I_{i} of Section 4. To this end, let x = θ_{i}(1 − e^{−t}) within I_{i}, i = 1, 2, 3, 4, where θ_{i} is defined in Section 3. With T = log n cut the range t ∈ [δT, (1 − δ)T] for each I_{i} to (1 − 2δ)T unit length intervals, denoting by J_{(i−1)T +1}, …, J_{iT} the corresponding image in I_{i}. If f(x) has ℓ zeros in some I_{i}, then there must exist j_{1}, …, j_{ℓ} such that f(x) has a constant sign s ∈ {−1, 1} on each of the “long” subintervals obtained by deleting J_{(i−1)T +j_{1}}, …, J_{(i−1)T +j_{ℓ}} from I_{i}. We partition the event that f(x) has at most k zeros in V according to the possible vector j = (j_{1}, …, j_{k}) of “crossing indices” among the 4T intervals {J_{1}, …, J_{4T} } and the possible signs s_{m} ∈ {−1, 1} of f(x) on the resulting long subintervals L_{m}, m = 1, …, k + 4 within V. Let

q_{n,s,j} = P (min_{m=1}^{k+4} inf_{x∈L_{m}} s_{m}f(x) > 0) ,

for s = (s_{1}, …, s_{k+4}). Since

q_{n,k} ≤ ∑_{j} ∑_{s} q_{n,s,j} ,

and the number of choices of j and s is at most 2^{k+4}(4T)^{k} = n^{o(1)}, it suffices to show that

max_{s,j} q_{n,s,j} ≤ n^{−(1−2δ)b+o(1)} .  (7.1)

Applying the coupling of (f_{k}, g_{k}) and (f_{k}^{b}, g_{k}^{b}) as provided in (5.4) and (5.5) for t = n^{δ/4} and p = 16/δ, we see that for all j and s,

q_{n,s,j} ≤ P (min_{m=1}^{k+4} inf_{x∈L_{m}} s_{m}f̂_{n+1}^{b}(x) > −n^{−δ/8}) + cn^{−3} := q_{n,s,j}^{b} + cn^{−3} ,  (7.2)

where c < ∞ depends on δ but is independent of j, s and n. Thus, the proof reduces to the Gaussian case.

Suppose first that n is even. The covariance function of s_{m}f̂_{n+1}^{b}(x) on V′ = ∪_{m}L_{m} is then given by s_{m}s_{l}c_{n+1}(x, y) for x ∈ L_{m} and y ∈ L_{l}. Since c_{n+1}(x, y) ≥ 0 for all x, y, it follows by Slepian’s lemma that per choice of j, the probability q_{n,s,j}^{b} is maximal when s_{m} = 1 for all m. In case n is odd, note that f_{n+1}^{b}(x) = σ_{n}(x)f̂_{n}^{b}(x) + b_{n}x^{n} and

|x|^{n} ≤ 2n^{−δ/2}σ_{n}(x) ∀ x ∈ V

Consequently, for all j and s,

q_{n,s,j}^{b} ≤ P (|b_{n}| ≥ n^{δ/4}) + P (min_{m=1}^{k+4} inf_{x∈L_{m}} s_{m}f̂_{n}^{b}(x) > −2n^{−δ/8}) .  (7.3)

With n − 1 even, continuing as before, we see that the right-most term in (7.3) is maximal when s_{m} = 1 for all m. In conclusion, it suffices to consider

q_{n,j}^{b} = P ( inf_{x∈V′} f̂_{n+1}^{b}(x) > −2n^{−δ/8}) ,

for n even. Applying the arguments of (4.2), (4.4) and (4.5) with γ_{n}(x) ≡ −n^{−δ/8} on the subset V′ of V, we find that

q_{n,j}^{b} ≤ e^{−n^{δ/4}/2} + ∏_{i=1}^{4} P (sup_{t∈T_{i}} Y_{t} ≤ ε_{T′}) ,  (7.4)

where Y_{t} is the stationary Gaussian process of Lemma 2.2 and for i = 1, …, 4 the set T_{i} ⊂ [δT, (1−δ)T] is the image of V′ ∩I_{i} under the transformation t = − log(1−θ_{i}(x)). Since τ ↦ R_{y}(τ) is monotonically decreasing on [0, ∞), it follows by Slepian’s lemma that P (sup_{t∈T_{i}} Y_{t} ≤ ε_{T′}) is maximal per fixed size of T_{i} when the latter set is an interval, that is, when the J_{j_{l}} are all at one end of I_{i} for each i (easiest to see this by considering first J_{j_{1}} only, then J_{j_{2}} etc.). In this case each interval T_{i} has at least the length (1 − 2δ)T − k, so the upper bound of (7.1) follows from (2.5) and (7.2)–(7.4).

8 Proof of Theorem 1.2

In view of the upper bound q_{n,k} ≤ n^{−b+o(1)} of Section 7, it suffices to show that p_{n,k} ≥ n^{−b−o(1)}, in order to complete the proof of Theorem 1.2.

Since a_{i} are of zero mean and positive variance, the support of their law must intersect both (0, ∞) and (−∞, 0). Consequently, there exist β < 0 < α such that P (|a_{i} − α| < ϵ) > 0 and P (|a_{i} − β| < ϵ) > 0 for all ϵ > 0. Replacing {a_{i}} by {−a_{i}} does not affect the number of zeros of f_{n+1}(x). Hence, we may and shall assume without loss of generality that |α| ≥ |β|. Let s ≥ 4 be an even integer such that α + (s − 1)β < 0. Define

Q(x) = βx^{s−1} + ∑_{i=0}^{s−2} αx^{i}, R(x) = α + ∑_{i=1}^{s−1} βx^{i},

and note that

Q(x) > 0 ∀|x| ≤ 1,  R(1) < 0 < R(−1) .  (8.1)

8.1 Proof for k and n even

Suppose that k and n are even. After k, s, α, β are fixed, we shall choose δ > 0 sufficiently small, then a large enough integer r = r(δ), followed by a small enough positive ϵ = ϵ(δ, r), all of which are independent of n. Let r_{i} denote the multiple of s nearest to r^{i}, for i = 1, …, k and ρ_{n} := max{5/p_{n}, (log n)^{−1/2}} for p_{n} ↑ ∞ such that E|a_{i}|^{p_{n}} ≤ n (these choices are slightly different from the ones made in Section 5). Let m = m_{n} be the multiple of s nearest to 2r_{k}ρ_{n} log n/| log(1−δ)| and define the polynomials

B(x) = ∑_{i=0}^{m−1} b_{i}x^{i} := (1 + x^{s} + x^{2s} + … + x^{r_{1}−s})Q(x) + (x^{r_{1}} + x^{r_{1}+s} + … + x^{r_{2}−s})R(x)
+ (x^{r_{2}} + x^{r_{2}+s} + … + x^{r_{3}−s})Q(x) + (x^{r_{3}} + x^{r_{3}+s} + … + x^{r_{4}−s})R(x)
+ … + (x^{r_{k}} + x^{r_{k}+s} + … + x^{m−s})Q(x),
C(X) = ∑_{i=0}^{m−1} c_{i}X^{i} := (1 + X^{s} + X^{2s} + … + X^{m−s})Q(X).

Each coefficient b_{i} of B(x) equals either α or β. The same holds for each coefficient c_{i} of C(X). Let A_{n} denote the event that the following hold:

A1 |a_{i} − b_{i}| < ϵ for i = 0, 1, …, m − 1

A2 |a_{n−i} − c_{i}| < ϵ for i = 0, 1, …, m − 1

A3 a_{m} + a_{m+1}x + … + a_{n−m}x^{n−2m} > n^{−1/4}σ_{n−2m+1}(x) for all x ∈ ℝ.

A4 |a_{i}| < n^{ρ_{n}} for i = 0, 1, …, n.

Most of our work shall be to show that the polynomial B(x) has the required behavior in terms of zeros for |x| ≤ (1 − δ)^{1/r_{k}}. Conditions A1 and A4 ensure that f(x) is close enough to B(x) on this interval so as to have there exactly k simple zeros. The condition A3 precludes additional zeros of f(x) near ±1. Moreover, with A2 and the positivity of C(X) for |X| ≤ 1, we conclude that f(x) > 0 when |x| > 1.

The stated lower bound on p_{n,k} is an immediate consequence of the following two lemmas.

Lemma 8.1 For any fixed δ > 0, ϵ > 0 and an integer r, the probability of the event A_{n} is at least n^{−b−o(1)} for even n → ∞.

Lemma 8.2 Suppose the even integer k is fixed. There exist small enough δ > 0, large enough r = r(δ) and a small enough ϵ = ϵ(δ, r) positive, such that for all sufficiently large even n, any polynomial f(x) = ∑_{i=0}^{n} a_{i}x^{i} whose coefficients are in A_{n} has exactly k real zeros, each of which is a simple zero.

Proof of Lemma 8.1: Since all coefficients of B(x) and C(x) belong to {α, β}, our choice of α and β implies that each coefficient condition in A1 and A2 is satisfied with probability at least c for some c > 0 depending only on ϵ. The probability that condition A3 holds is P_{n′,γ_{n′}} of Theorem 1.3 for n′ = n − 2m + 1 odd and γ_{n′}(x) ≡ n^{−1/4} that satisfy the assumptions of this theorem. Consequently, condition A3 holds with probability of at least (n′)^{−b−o(1)} = n^{−b−o(1)}. Since conditions A1, A2 and A3 are independent, the probability that all of them hold is at least

c^{2m}(n′)^{−b+o(1)} = n^{−b−o(1)}.  (8.2)

(Recall that ρ_{n} → 0, hence also m_{n}/ log n → 0.) By Markov’s inequality and the choice of ρ_{n}, the probability that condition A4 fails for a given i is at most n^{−4}. Hence the probability that this condition fails for any i in the range 0 ≤ i ≤ n is at most O(n^{−3}). Since b ≤ 2, imposing condition A4 does not affect the n^{−b−o(1)} lower bound of (8.2). Proof of Lemma 8.2: The proof of the lemma is divided in three steps. Step 1: For δ > 0 sufficiently small, r > (log δ)/(log(1−δ)) sufficiently large, ϵ > 0 sufficiently small and all large even integers n, each polynomial f(x) with coefficients in A_{n} has exactly k simple zeros in [0, 1]. Step 2: Under same conditions on the parameters, f(x) > 0 on [−1, 0]. Step 3: g(X) = X^{n}f(X^{−1}) > 0 on (−1, 1). Step 1. Fixing f(x) as above, observe that the zeros of f(x) in (0, 1) are the same as those of F (x) := (1 − x^{s})f(x), so it suffices to prove that

• F (x) > 0 for x ∈ [0, δ^{1/r_{1}}]

• F′(x) < 0 for x ∈ [δ^{1/r_{1}}, (1 − δ)^{1/r_{1}}]

• F (x) < 0 for x ∈ [(1 − δ)^{1/r_{1}}, δ^{1/r_{2}}]

• F′(x) > 0 for x ∈ [δ^{1/r_{2}}, (1 − δ)^{1/r_{2}}]

• F (x) > 0 for x ∈ [(1 − δ)^{1/r_{2}}, δ^{1/r_{3}}]

• F′(x) < 0 for x ∈ [δ^{1/r_{3}}, (1 − δ)^{1/r_{4}}]

⋮

• F′(x) > 0 for x ∈ [δ^{1/r_{k}}, (1 − δ)^{1/r_{k}}]

• F (x) > 0 for x ∈ [(1 − δ)^{1/r_{k}}, 2^{−1/m})

• f(x) > 0 for x ∈ [2^{−1/m}, 1]

Indeed, the sign changes in F (x) force at least one real zero in each of the k gaps between the intervals on which F is guaranteed positive or negative, and the monotonicity of F′(x) on these gaps guarantees that each of them contains exactly one zero and that the zero is simple. Note also that m = m_{n} → ∞, so per choice of δ > 0 all the intervals of x above are nonempty as soon as r is large enough.

Recall that our choice of m = m_{n} is such that for any l < ∞,

m^{l}n^{ρ}(1 − δ)^{m/r_{k}} → 0 .  (8.3)

Consequently, by conditions A1 and A4 of A_{n}, there exists c(r, δ) finite, such that for all ϵ > 0, n large enough and |x| ≤ (1 − δ)^{1/r_{k}},

|F (x) − (1 − x^{s})B(x)| ≤ (1 − x^{s}) [ϵ(1 + |x| + … + |x|^{m−1}) + n^{ρ}(|x|^{m} + … + |x|^{n})]
≤ (1 − |x|)^{−1}(ϵ + n^{ρ}x^{m}) ≤ c(r, δ)ϵ.  (8.4)

Fix M such that |Q(x)| ≤ M and |R(x)| ≤ M for all x ∈ [0, 1]. By definition of B(x),

(1 − x^{s})B(x) = Q(x) + [∑_{ℓ=1}^{k}(−1)^{ℓ}(Q(x) − R(x))x^{r_{ℓ}}] − Q(x)x^{m}.  (8.5)

Suppose x ∈ [0, δ^{1/r_{1}}]. Then, each x^{r_{ℓ}} and x^{m} is at most δ, so

(1 − x^{s})B(x) ≥ Q(x) − (2k + 1)Mδ .

Therefore, for all δ sufficiently small, the positivity of Q(x) on [0, 1] (see (8.1)) implies that (1 − x^{s})B(x) ≥ η for some η > 0 independent of n, and all x ∈ [0, δ^{1/r_{1}}]. For ϵ > 0 small enough, this in turn implies the positivity of F (x) on this interval (see (8.4)).

Suppose x ∈ [(1 − δ)^{1/r_{j}}, δ^{1/r_{j+1}}] for some j ∈ {1, 2, …, k − 1}. Then, x^{m} ≤ x^{r_{ℓ}} ≤ δ for all ℓ > j and x^{r_{ℓ}} ∈ [1 − δ, 1], for all ℓ ≤ j. In view of the identity

Q(x) + ∑_{ℓ=1}^{j}(−1)^{ℓ}(Q(x) − R(x)) = Q(x)1_{j is even} + R(x)1_{j is odd}  (8.6)

and (8.5), it follows that for all x as above,

|(1 − x^{s})B(x) − [Q(x)1_{j is even} + R(x)1_{j is odd}]| ≤ (2k + 1)Mδ.

For δ small enough, the error (2k+1)Mδ is at most min{Q(1), −R(1)}/3. Once δ is chosen, taking r sufficiently large guarantees that Q(x) ≥ Q(1)/2 and R(x) ≤ R(1)/2 for all x ∈ [(1−δ)^{1/r_{1}}, 1]. Since Q(1) is positive and R(1) is negative (see (8.1)), we conclude that there exists η > 0 independent of n such that (−1)^{j}(1 − x^{s})B(x) ≥ η for all n large enough and all x ∈ [(1 − δ)^{1/r_{j}}, δ^{1/r_{j+1}}], j = 1, …, k − 1. In view of (8.4), for all ϵ > 0 small enough (−1)^{j}F (x) is then positive throughout the interval x ∈ [(1 − δ)^{1/r_{j}}, δ^{1/r_{j+1}}], as needed.

Suppose x ∈ [(1 − δ)^{1/r_{k}}, 2^{−1/m}]. Then, x^{r_{ℓ}} ∈ [1 − δ, 1] for all ℓ ≤ k and x^{m} ≤ 1/2. With k even, it follows from (8.5) and (8.6) that

(1 − x^{s})B(x) ≥ \frac{1}{2}Q(x) − 2kMδ .

So, when δ > 0 is small enough, then for some η > 0 independent of n, it holds that (1−x^{s})B(x) ≥ η for all n large enough and all x ∈ [(1 − δ)^{1/r_{k}}, 2^{−1/m}]. Recall that

(1 − x^{s})x^{m}(a_{m} + a_{m+1}x + … + a_{n−m}x^{n−2m}) ≥ 0  (8.7)

by condition A3. So, while F (x) − (1 − x^{s})B(x) is no longer negligible as in (8.4), the positivity of the expression in (8.7) results in

F (x) − (1 − x^{s})B(x) ≥ −(1 − x^{s})(ϵ(1 + |x| + … + |x|^{m−1}) + m(α + ϵ)|x|^{n−m}) ≥ −c(δ, r)ϵ

for some finite c(δ, r), all ϵ > 0 and large enough n. (This is because m_{n} = o(log n), so m_{n}x^{n−m_{n}} → 0 as n → ∞, uniformly on x ∈ [(1 − δ)^{1/r_{k}}, 2^{−1/m}]). Consequently, when ϵ > 0 is small enough, the uniform positivity of (1−x^{s})B(x) ≥ η > 0 results in the positivity of F (x) for x ∈ [(1−δ)^{1/r_{k}}, 2^{−1/m}].

Suppose x ∈ [2^{−1/m}, δ^{1/n}]. Using the decomposition f = f^{L} + f^{M} + f^{H} as in (5.7), note that by condition A1

f^{L}(x) ≥ B(x) − ϵ ∑_{i=0}^{m−1} |x|^{i} ≥ (x^{r_{k}} + x^{r_{k}+s} + … + x^{m−s})Q(x) − r_{k}M − ϵm
≥ (\frac{m − r_{k}}{2s} )Q(x) − r_{k}M − ϵm.

Note that f^{M}(x) ≥ 0 by condition A3 and

|f^{H}(x)| ≤ m(α + ϵ)x^{n−m} ≤ m(2α)δ^{1−m/n} ≤ 2mαδ^{1/2}

by condition A2. Since m_{n} → ∞ while m_{n}/n → 0, and Q(x) is strictly positive, we see by combining the above that if δ and ϵ are small enough then for all n large enough the “main” term m_{n}Q(x)/(2s) dominates, so f(x) > 0 for all x ∈ [2^{−1/m}, δ^{1/n}].

Suppose x ∈ [δ^{1/n}, 1]. In this case, by condition A3,

f^{M}(x) ≥ x^{m}n^{−1/4}σ_{n−2m+1}(x) ≥ δ^{2}n^{−1/4}\sqrt{n − 2m + 1} > n^{1/8}  (8.8)

as n → ∞. Condition A1 implies that |f^{L}(x)| ≤ (α + ϵ)m, whereas condition A2 implies that |f^{H}(x)| ≤ (α + ϵ)m. Since m = o(log n), we conclude that f(x) > 0 for large n and all x ∈ [δ^{1/n}, 1].

We turn to deal with the sign of F′(x) in the gaps [δ^{1/r_{j}}, (1 − δ)^{1/r_{j}}] for j = 1, …, k. To this end, first note that

F′(x) = \frac{d}{dx} [(1 − x^{s})B(x)] + e(x)

where by conditions A1 and A4, there exists c(δ, r) finite, such that for all ϵ > 0, n large enough and x ∈ [0, (1 − δ)^{1/r_{k}}],

|e(x)| ≤ | − sx^{s−1}| [ϵ(1 + x + … + x^{m−1}) + n^{ρ}(x^{m} + x^{m+1} + … + x^{n})]

+ (1 − x^{s}) [ϵ(1 + 2x + … + (m − 1)x^{m−2}) + n^{ρ}(mx^{m−1} + (m + 1)x^{m} + … + nx^{n−1})]

≤ s(1 − x)^{−1}(ϵ + n^{ρ}x^{m}) + (1 − x)^{−2}(ϵ + n^{ρ}mx^{m−1}) ≤ c(δ, r)ϵ  (8.9)

(see (8.3) and (8.4)). Next, using (8.5), we obtain

\frac{d}{dx} [(1 − x^{s})B(x)] = Q′(x) + ∑_{ℓ=1}^{k}(−1)^{ℓ} [(Q′(x) − R′(x))x^{r_{ℓ}} + (Q(x) − R(x))r_{ℓ}x^{r_{ℓ}−1}] − o(1). (8.10)

(The o(1) denotes two terms involving x^{m}, which by (8.3) converge to 0 uniformly on x ∈ [0, (1 − δ)^{1/r_{k}}].) The sum of the terms involving Q′(x) or R′(x) in (8.10) is at most (2k + 2)M′, where M′ is such that |Q′(x)| ≤ M′ and |R′(x)| ≤ M′ for all x ∈ [0, 1]. Per fixed δ > 0, if r is sufficiently large then Q(x)−R(x) ≥ η for some η > 0 and all x ∈ [δ^{1/r_{1}}, 1] (see (8.1)). We claim that if x ∈ [δ^{1/r_{j}}, (1− δ)^{1/r_{j}}] for some j ∈ {1, 2, …, k} then the term h_{j} := (−1)^{j}(Q(x) − R(x))r_{j}x^{r_{j}−1} dominates the right hand side of (8.10) for all r large enough. Indeed, |h_{j}| ≥ ηδr_{j} for all x ∈ [δ^{1/r_{j}}, (1 − δ)^{1/r_{j}}], whereas for such x we have that |h_{ℓ}| ≤ 2Mr_{j−1} when ℓ < j and |h_{ℓ}| ≤ 2Mr_{k}(1 − δ)^{(r_{j+1}−1)/r_{j}} when ℓ > j. Since r_{ℓ} = r^{ℓ}(1 + o(1)), combining the above we see that for all large enough r,

(−1)^{j} \frac{d}{dx} [(1 − x^{s})B(x)] ≥ \frac{η}{2}δr^{j} − 3Mk(r^{j−1} + r^{k}(1 − δ)^{\sqrt{r}}) − (2k + 2)M′ − o(1) ≥ \frac{η}{3}δr^{j}.

By (8.9) we then get that for small enough ϵ > 0, (−1)^{j}F′(x) also is positive in the j-th gap. This completes Step 1.

Step 2. As before, define F (x) := (1−x^{s})f(x). The proof that F (x) > 0 on [−δ^{1/r_{1}}, 0] is the same as the proof for [0, δ^{1/r_{1}}], now using the positivity of Q(x) on [−1, 0]. For each j ∈ {1, 2, …, k−1}, the analysis for [−δ^{1/r_{j+1}}, −(1 − δ)^{1/r_{j}}] is the same as that for [(1 − δ)^{1/r_{j}}, δ^{1/r_{j+1}}], the only difference is that Q(x) and R(x) are both positive near −1 (whereas they have opposite signs near 1), so the result is that F (x) > 0 on these intervals, independent of the parity of j. The analyses for [−2^{−1/m}, −(1 − δ)^{1/r_{k}}] and for [−1, −2^{−1/m}] are the same as for the symmetric intervals on the positive side.

To complete the proof that f(x) > 0 on [−1, 0], it remains to show that F (x) > 0 on each gap [−(1 − δ)^{1/r_{j}}, −δ^{1/r_{j}}] for j = 1, …, k. By (8.4), it suffices to show that on such an interval (1 − x^{s})B(x) ≥ η for some η > 0, independent of ϵ and n. On the j-th such interval, x^{m} ≤ x^{r_{ℓ}} ≤ δ for all ℓ > j, whereas if r is sufficiently large, then 1 ≥ x^{r_{ℓ}} ≥ δ^{r_{ℓ}/r_{j}} ≥ (1 − δ) for all ℓ < j. Hence, it follows from (8.5) and (8.6) that

|(1 − x^{s})B(x) − [t(x)Q(x) + (1 − t(x))R(x)]| ≤ (2k − 1)Mδ ,  (8.11)

where t(x) = 1 − x^{r_{j}} for j even, and t(x) = x^{r_{j}} otherwise. Let η = min{Q(−1), R(−1)}/4 > 0, and take δ small enough that (2k − 1)Mδ < η. Since t(x) ∈ [0, 1], if r is large enough that min{Q(x), R(x)} > 2η for all x ∈ [−1, −δ^{1/r_{1}}], then (8.11) implies that (1 − x^{s})B(x) ≥ η for all x ∈ [−(1 − δ)^{1/r_{j}}, −δ^{1/r_{j}}], j = 1, …, k. The positivity of F (x) for small ϵ and large n follows (by (8.4)).

Step 3. To complete the proof of Lemma 8.2, it suffices to show that g(X) := X^{n}f(X^{−1}) is positive on (−1, 1). For ϵ < α, conditions A1, A2 and A3 result in

g(X) ≥ C(X) − (ϵ + 2αX^{n−m}) ∑_{i=0}^{m−1} |X|^{i} + X^{m}n^{−1/4}σ_{n−m+1}(X) ,  (8.12)

for all |X| ≤ 1. Since (1 − X^{s})C(X) = (1 − X^{m})Q(X), we see that for n large enough and all |X| ≤ 2^{−1/m},

(1 − X^{s})g(X) ≥ (1 − X^{m})Q(X) − (ϵ + 4α2^{−n/m}) ∑_{i=0}^{s−1} |X|^{i} ≥ \frac{1}{2}Q(X) − 2sϵ

is positive for ϵ < Q(1)/(8s). Since C(X) ≥ \frac{m}{2s}Q(X) when |X| ∈ [2^{−1/m}, δ^{1/n}], it follows from (8.12) that

g(X) ≥ m [\frac{Q(X)}{2s} − ϵ − 2αδ^{1−m/n}]

is positive for any such X, provided ϵ < Q(1)/(8s), 2αδ^{1/2} < Q(1)/(8s) and n is large enough. Finally, for large n, if |X| ∈ [δ^{1/n}, 1] then X^{m}n^{−1/4}σ_{n−m+1}(X) ≥ n^{1/8} (see (8.8)). Since m = o(log n), the positivity of g(X) for such X is a direct consequence of (8.12).

8.2 Proof for k and n odd

In this section we sketch the modifications to the argument of the previous section that are required for the case where k and n are odd. We will specify an event occurring with probability at least n^{−b−o(1)} that forces k − 1 simple zeros in (0, 1), one simple zero in (−∞, −1), and no other real zeros. Fix positive δ, integer r and ϵ > 0, and define r_{i}, ρ = ρ_{n} and m = m_{n} as in Section 8.1. Define the polynomials

B(x) = ∑_{i=0}^{m−1} b_{i}x^{i} := (1 + x^{s} + x^{2s} + … + x^{r_{1}−s})Q(x) + (x^{r_{1}} + x^{r_{1}+s} + … + x^{r_{2}−s})R(x)
+ (x^{r_{2}} + x^{r_{2}+s} + … + x^{r_{3}−s})Q(x) + (x^{r_{3}} + x^{r_{3}+s} + … + x^{r_{4}−s})R(x)
+ … + (x^{r_{k−1}} + x^{r_{k−1}+s} + … + x^{m−s})Q(x),
C(X) = ∑_{i=0}^{m} c_{i}X^{i} := (1 + X^{s} + X^{2s} + … + X^{r_{1}−s})Q(X)
+ αX^{r_{1}} + X(X^{r_{1}} + X^{r_{1}+s} + … + X^{m−s})Q(X)

the coefficients of which are in {α, β}. Let B_{n} denote the event that the following hold:

B1 |a_{i} − b_{i}| < ϵ for i = 0, 1, …, m − 1

B2 |a_{n−i} − c_{i}| < ϵ for i = 0, 1, …, m

B3 a_{m} + a_{m+1}x + … + a_{n−m−1}x^{n−2m−1} > n^{−1/4}σ_{n−2m}(x) for all x ∈ ℝ

B4 |a_{i}| < n^{ρ} for i = 0, 1, …, n.

Note that the degree of C(X) is one larger than in Section 8.1. This ensures that the “middle polynomial” in condition B3 has even degree, so that Theorem 1.3 applies to it. Hence, similarly to the proof of Lemma 8.1, one has that the event B_{n} occurs for odd n with probability exceeding n^{−b−o(1)}.

For all small enough δ > 0, large enough r and small enough ϵ, the argument of the proof of Lemma 8.2, using the shape of B(x), shows that if the coefficients of f(x) are in B_{n} then f(x) has exactly k − 1 zeros in [0, 1], all simple, and no zeros in [−1, 0]. We next prove that the function F (X) := (1 − X^{s})X^{n}f(1/X) satisfies

• F (X) > 0 for X ∈ (0, 1)

• F (X) > 0 for X ∈ [−δ^{1/r_{1}}, 0)

• F′(X) > 0 for X ∈ [−(1 − δ)^{1/r_{1}}, −δ^{1/r_{1}}]

• F (X) < 0 for X ∈ [−2^{−1/m}, −(1 − δ)^{1/r_{1}}]

• F (X) < 0 for X ∈ (−1, −2^{−1/m}]

These will imply that f(x) has a simple zero in (−∞, −1), and no other zeros with |x| > 1. Together with the k − 1 simple zeros in [0, 1], this will bring the total number of zeros to k.

First, a proof analogous to that of (8.4) shows that there exists c(r, δ) finite, such that for |X| ≤ (1 − δ)^{1/r_{1}},

|F (X) − (1 − X^{s})C(X)| ≤ c(r, δ)ϵ.  (8.13)

The analogue of (8.5) is

(1 − X^{s})C(X) = (1 − X^{r_{1}} + X^{r_{1}+1} − X^{m+1})Q(X) + αX^{r_{1}}(1 − X^{s}).  (8.14)

Suppose X ∈ [0, (1 − δ)^{1/r_{1}}]. Then (8.14) implies

(1 − X^{s})C(X) ≥ (1 − X^{r_{1}})Q(X) ≥ δQ(X) > c(r, δ)ϵ

if ϵ is small enough, so F (X) > 0 by (8.13).

Suppose X ∈ [−δ^{1/r_{1}}, 0]. Then (8.14) implies

(1 − X^{s})C(X) ≥ (1 − 3δ)Q(X)

so F (X) > 0 by (8.13) assuming suitable δ and ϵ.

Suppose X ∈ [−(1 − δ)^{1/r_{1}}, −δ^{1/r_{1}}]. The analogues of (8.9) and (8.10) are

|F′(X) − \frac{d}{dX} [(1 − X^{s})C(X)]| ≤ c(δ, r)ϵ

and, with r_{1}, s even,

\frac{d}{dX} [(1 − X^{s})C(X)] = (1 − X^{r_{1}} + X^{r_{1}+1}) Q′(X) + [−r_{1}X^{r_{1}−1} + (r_{1} + 1)X^{r_{1}}] Q(X)
+ αr_{1}X^{r_{1}−1}(1 − X^{s}) − αsX^{r_{1}+s−1} − o(1)
≥ −3M′ + r_{1}δQ(X) − αr_{1}(1 − δ^{s/r_{1}}) − o(1)
≥ (r_{1}δ/2)Q(X),

in which the last inequality holds for r sufficiently large. Hence for ϵ small enough, F′(X) will be positive.

Suppose X ∈ [−2^{−1/m}, −(1 − δ)^{1/r_{1}}]. Then, for r sufficiently large, 1 − X^{r_{1}} + X^{r_{1}+1} − X^{m+1} ≤ −(1/2 − 3δ)/2 and αX^{r_{1}}(1 − X^{s}) = O(s/r_{1}). For δ small and r large (8.14) thus implies that

(1 − X^{s})C(X) ≤ −(1/2 − 3δ)Q(X)/2 + O(s/r_{1}) ≤ −Q(X)/8

Although (8.13) is no longer valid, we may apply B3 to deduce

F (X) − (1 − X^{s})C(X) ≤ ϵs + (1 − X^{s})(a_{m}X^{n−m} + a_{m+1}X^{n−m−1} + … + a_{n−m−1}X^{m+1})
+ m(α + ϵ)X^{n−m+1}
≤ ϵs + m(α + ϵ)2^{−(n−m+1)/m} ≤ 2ϵs

since m2^{−n/m} → 0. Hence F (X) < 0 if we take first δ small then r large and finally ϵ small. Similarly, for r large enough, if X ∈ [(1 − δ)^{1/r_{1}}, 2^{−1/m}], then

(1 − X^{s})C(X) ≥ (1 − X^{m})XQ(X) ≥ Q(X)/3,

and

F (X) − (1 − X^{s})C(X) ≥ −ϵs − m(α + ϵ)X^{n−m+1} ≥ −2ϵs

implying that F (X) > 0 in this interval.

Both the proof that F (X) > 0 on [2^{−1/m}, 1) and the proof that F (X) < 0 on (−1, −2^{−1/m}] parallel the proof in Section 8.1 that f(x) > 0 for x ∈ [2^{−1/m}, 1).

9 Proof of Proposition 1.5

In view of the upper bound q_{n,k} ≤ n^{−b+o(1)} of Section 7, it suffices to provide a lower bound on the probability of the event considered in Proposition 1.5. To this end, partitioning and shrinking the U_{i} if necessary, we may assume that m_{1} = … = m_{k} = 1, and that the closures of the U_{i} avoid both 1 and −1. Let δ ∈ (0, 1/3) then be such that each of the U_{i} is contained either in (−1 + δ, 1 − δ) or its image under the map inv(x) = x^{−1}. Let r be the number of U_{i} of the former type and s = k − r the number of those of the latter type. Let S = (−η/2, η/2) for η > 0 as in the statement of the proposition. Fix the polynomials B(x) = ∑_{i=0}^{r} b_{i}x^{i} ∈ S[x] and C(X) = ∑_{i=0}^{s} c_{i}X^{i} ∈ S[X] with coefficients in S, such that B(x) has r real zeros, one in each of the U_{i} that are contained in (−1, 1) whereas C(X) has s real zeros, one in inv(U_{i}) for each U_{i} contained in (−∞, −1) ∪ (1, ∞). Without loss of generality we can set b_{r} > 0 and c_{s} > 0. Let ρ_{n} = 5/p_{n} for p_{n} ↑ ∞ such that E|a_{i}|^{p_{n}} ≤ n (these differ from the quantities defined in Section 5). Define the even integer m = m_{n} = 2⌊ρ_{n} log n/| log(1 − δ)|⌋ depending on n. For fixed ϵ ∈ (0, η/11), consider the event C_{n} that all of the following are satisfied:

C1 |a_{i} − b_{i}| < ϵ for 0 ≤ i ≤ r, |a_{r+i} − 9ϵ1_{i even} | < ϵ for 0 < i < m.

C2 |a_{n−i} − c_{i}| < ϵ for 0 ≤ i ≤ s, |a_{n−s−i} − 9ϵ1_{i even} | < ϵ for 0 < i < m.

C3 a_{m+r} + a_{m+r+1}x + … + a_{n−s−m}x^{n−k−2m} > 0 for all x ∈ ℝ.

C4 |a_{i}| < n^{ρ_{n}} for 0 ≤ i ≤ n.

Proposition 1.5 is an immediate consequence of the following two lemmas.

Lemma 9.1 For any fixed B(x), C(X) with coefficients in S and positive ϵ < η/11, the probability of the event C_{n} is at least n^{−b−o(1)}.

Lemma 9.2 For fixed B(x) and C(X), if ϵ > 0 is sufficiently small and n sufficiently large, then any polynomial f(x) = ∑_{i=0}^{n} a_{i}x^{i} satisfying the conditions of C_{n} has exactly k real zeros, one in each of the U_{i} intervals.

Proof of Lemma 9.1: Note that P (a ∈ G) > 0 for any open subset G of (−η, η) (by our assumption about the support of the law of a_{i}). Hence each coefficient condition in C1 and C2 is satisfied with probability at least c for some c > 0 depending only on B(x), C(X) and ϵ. We continue along the lines of the proof of Lemma 8.1 (taking now n′ = n − k − 2m + 1 and γ_{n′} = 0).

Proof of Lemma 9.2: Our choice of ρ = ρ_{n} and m = m_{n} guarantees that for any l < ∞, m^{l}n^{ρ}(1 − δ)^{m} →_{n→∞} 0. Consequently, by C1 and C4, for some κ_{0} = κ_{0}(δ), all ϵ > 0, n > n_{0} for some n_{0} = n_{0}(δ, ε) large enough and |x| ≤ (1 − δ)

|f(x) − B(x)| ≤ 10ϵ(1 + |x| + … + |x|^{m+r−1}) + n^{ρ}(|x|^{m+r} + |x|^{m+r+1} + …)
≤ (10ϵ + n^{ρ}(1 − δ)^{m+r})/δ ≤ κ_{0}ϵ .

Hence if ϵ is small enough and n large enough, f must have at least as many zeros as B(x) within (−1 + δ, 1 − δ). On the other hand, B^{(r)}(x) is a positive constant, and for x ∈ (−1 + δ, 1 − δ),

|f^{(r)}(x) − B^{(r)}(x)| ≤ 10ϵ ∑_{i=r}^{m+r−1} i^{r}|x|^{i−r} + n^{ρ} ∑_{i=m+r}^{∞} i^{r}|x|^{i−r}

≤ 10ϵ ∑_{i=r}^{∞} i^{r}(1 − δ)^{(i−r)} + n^{ρ} ∑_{i=m+r}^{∞} i^{r}(1 − δ)^{(i−r)},

which again can be made arbitrarily small by shrinking ϵ. So, we can and shall assume f^{(r)}(x) > 0 in (−1 + δ, 1 − δ). By Rolle’s Theorem, this bounds the number of real zeros in (−1 + δ, 1 − δ) by r, so f(x) has exactly r zeros in (−1 + δ, 1 − δ). Moreover, taking ϵ > 0 such that |B(x)| > κ_{0}ϵ for all |x| ≤ (1 − δ), x ∉ U_{i}, i = 1, …, k, implies that the constant sign of f(x) between each adjacent pair of intervals U_{i} that are contained in (−1 + δ, 1 − δ) is the same as the sign of B(x) there. Hence f(x) has exactly one zero in each of the r intervals U_{i} contained in (−1, 1). Similar arguments (using C2 and C4) show that for some κ_{1} = κ_{1}(δ) and all |X| < (1 − δ),

|X^{n}f(X^{−1}) − C(X)| ≤ κ_{1}ϵ,

with the s-th derivative of the polynomial X^{n}f(X^{−1}) made positive throughout |X| < (1 − δ) by shrinking ϵ. Recall that C(X) has exactly one zero in each of the intervals inv(U_{i}) for the U_{i} contained in (−∞, −1) ∪ (1, ∞). Thus, for small enough ϵ, the same property holds for the s zeros of X^{n}f(X^{−1}) within |X| < (1 − δ).

It thus remains to show that x^{r}f(x) > 0 for (1 − δ) ≤ |x| ≤ (1 − δ)^{−1}. Since 2r + m is an even integer, we have by condition C3 that for all x ∈ ℝ,

x^{r} ( ∑_{i=m+r}^{n−s−m} a_{i}x^{i}) = x^{2r+m} ( ∑_{i=0}^{n−k−2m} a_{m+r+i}x^{i}) ≥ 0 .  (9.1)

It is easy to check that

h_{m}(x) := 8x^{2} ∑_{j=0}^{(m−4)/2} x^{2j} − |x| ∑_{j=0}^{(m−2)/2} x^{2j} ≥ 0 ,

for all even m ≥ 4 and 2/3 ≤ |x| ≤ 3/2. Consequently, for (1 − δ) ≤ |x| ≤ (1 − δ)^{−1} and δ < 1/3, by condition C1,

x^{r} ( ∑_{i=r+1}^{r+m−1} a_{i}x^{i}) = x^{2r} ( ∑_{i=1}^{m−1} a_{r+i}x^{i}) ≥ ϵx^{2r}h_{m}(x) ≥ 0, ,  (9.2)

whereas for r + (n − s) = 2r + n − k an even integer, by condition C2,

x^{r} ( ∑_{i=n−s−m+1}^{n−s−1} a_{i}x^{i}) = x^{r+(n−s)} ( ∑_{i=1}^{m−1} a_{n−s−i}x^{−i}) ≥ ϵx^{2r+n−k}h_{m}(x^{−1}) ≥ 0.  (9.3)

Next note that for sufficiently small ϵ > 0, the polynomial ∑_{i=0}^{r} a_{i}x^{i} has a positive leading coefficient and no zeros for |x| ≥ (1 − δ), so x^{r}(∑_{i=0}^{r} a_{i}x^{i}) > 0 for all |x| ≥ (1 − δ). Similarly, x^{−(n−s)} ∑_{i=n−s}^{n} a_{i}x^{i} is then a polynomial with positive constant coefficient and no zeros for |x| ≤ (1 − δ)^{−1}. With r + (n − s) an even integer, it follows that x^{r}(∑_{i=n−s}^{n} a_{i}x^{i}) ≥ 0 for |x| ≤ (1 − δ)^{−1}. In view of (9.1)–(9.3), we find that x^{r}f(x) > 0 for (1 − δ) ≤ |x| ≤ (1 − δ)^{−1}.

References

[Ad] Adler, R. J. An introduction to continuity, extrema, and related topics for general Gaussian processes. Institute of Mathematical Statistics Lecture Notes—Monograph Series, 12. Institute of Mathematical Statistics, Hayward, CA, 1990.

[BR] Bharucha-Reid, A. T.; Sambandham, M. Random polynomials. Probability and Mathematical Statistics. Academic Press, Inc., Orlando, Fla., 1986.

[BP] Bloch, A.; Pólya, G. On the roots of certain algebraic equations. Proc. London Math. Soc. 33(1932), 102–114.

[CS] Csörgő, M. and Révész, P. Strong aprroximations in probability and statistics. Academic Press, New York, 1981.

[DZ] Dembo, A; Zeitouni, O. Large Deviations Techniques and Applications, second ed. Springer-Verlag, New York, 1998.

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

[EO] Erdős, Paul; Offord, A. C. On the number of real roots of a random algebraic equation. Proc. London Math. Soc. 6 (1956), 139–160.

[Fa] Farahmand, K. Topics in random polynomials. Pitman research notes in mathematics series 393. Longman, harlow, 1998.

[GR] Gradshteyn, I. S.; Ryzhuk, I. M. Tables of integrals, series, and products, 4-th ed. Academic Press, San Diego, 1980.

[IM1] Ibragimov, I. A.; Maslova, N. B. The average number of zeros of random polynomials. Vestnik Leningrad. Univ. 23 (1968), 171–172.

[IM2] Ibragimov, I. A.; Maslova, N. B. The mean number of real zeros of random polynomials. I. Coefficients with zero mean. Theor. Probability Appl. 16 (1971), 228–248.

[IM3] Ibragimov, I. A.; Maslova, N. B. The mean number of real zeros of random polynomials. II. Coefficients with a nonzero mean. Theor. Probability Appl. 16 (1971), 485–493.

[IM4] Ibragimov, I. A.; Maslova, N. B. The average number of real roots of random polynomials. Soviet Math. Dokl. 12 (1971), 1004–1008.

[IZ] Ibragimov, I. A.; Zeitouni, O. On roots of random polynomials. Trans. American Math. Soc. 349 (1997), 2427–2441.

[Ja] Jamrom, B. R. The average number of real zeros of random polynomials. Soviet Math. Dokl. 13 (1972), 1381–1383.

[Ka1] Kac, M. On the average number of real roots of a random algebraic equation. Bull. Amer. Math. Soc. 49, (1943), 314–320. Erratum: Bull. Amer. Math. Soc. 49, (1943), 938.

[Ka2] Kac, M. On the average number of real roots of a random algebraic equation. II. Proc. London Math. Soc. 50, (1949), 390–408.

[KMT] Komlós, J., Major, P. and Tusnády, G. An approximation of partial sums of independent R.V.’s and the sample D.F. II. Z. Wahr. verw. Gebiete 34 (1976), 35–58.

[LO1] Littlewood, J. E.; Offord, A. C. On the number of real roots of a random algebraic equation. I. J. London Math. Soc. 13, (1938), 288–295.

[LO2] Littlewood, J. E.; Offord, A. C. On the number of real roots of a random algebraic equation. II. Proc. Cambridge Philos. Soc. 35, (1939), 133–148.

[LO3] Littlewood, J. E.; Offord, A. C. On the number of real roots of a random algebraic equation. III. Rec. Math. [Mat. Sbornik] N.S. 54, (1943), 277–286.

[LS1] Logan, B. F.; Shepp, L. A. Real zeros of random polynomials. Proc. London Math. Soc. 18 (1968), 29–35.

[LS2] Logan, B. F.; Shepp, L. A. Real zeros of random polynomials. II. Proc. London Math. Soc. 18 (1968), 308–314.

[Ma1] Maslova, N. B. The variance of the number of real roots of random polynomials. Teor. Verojatnost. i Primenen. 19 (1974), 36–51.

[Ma2] Maslova, N. B. The distribution of the number of real roots of random polynomials. Theor. Probability Appl. 19 (1974), 461–473 (1975).

[PS] Poonen, B.; Stoll, M. The Cassels-Tate pairing on polarized abelian varieties. Annals of Math. 150 (1999), 1109–1149.

[Sh] Shao, Q.M. A Gaussian correlation inequality and its applications to the existence of small ball constant. Preprint, (1999).

[St] Stevens, D. C. The average number of real zeros of a random polynomial. Comm. Pure Appl. Math. 22 (1969), 457–477.

[Sto] Stout, W. F. Almost sure convergence. Academic Press, New York, 1974.

[Str] Strassen, V. An invariance principle for the law of the iterated logarithm. Z. Wahrscheinlichkeitstheorie verx. Gebiete 3, (1964), 211-226.

[To] Todhunter, I. A history of the mathematical theory of probability. Stechert, New York, 1931.

[Wa] Wang, You Jing. Bounds on the average number of real roots of a random algebraic equation. Chinese Ann. Math. Ser. A 4 (1983), 601–605. An English summary appears in Chinese Ann. Math. Ser. B 4 (1983), 527.

[Wi] Wilkins, J. Ernest, Jr. An asymptotic expansion for the expected number of real zeros of a random polynomial. Proc. Amer. Math. Soc. 103 (1988), 1249–1258.