Universality theorems for zeros of random real polynomials with fixed coefficients
Matthew C. King Ashvin Swaminathan





theoremTheorem
lemma[theorem]Lemma
corollary[theorem]Corollary
definition
definition[theorem]Definition
example[theorem]Example
*unnumlemmaLemma
remark
remark[theorem]Remark







:=
ℝ
ℙ
𝔼


ℤ
ℚ

    Universality theorems for zeros of random real polynomials 
     with fixed coefficients
        Matthew C. King and Ashvin A. Swaminathan
        September 9, 2024
    =====================================================================================
    
    § ABSTRACT 
    Consider a monic polynomial of degree n whose subleading coefficients are independent, identically distributed, nondegenerate random variables having zero mean, unit variance, and finite moments of all orders, and let m ≥ 0 be a fixed integer. We prove that such a random monic polynomial has exactly m real zeros with probability n^-b+o(1) as n→∞ through integers of the same parity as m, where b ≈ 0.76 is a positive constant. More generally, we determine conditions under which a similar asymptotic formula describes the corresponding probability for families of random real polynomials with multiple fixed coefficients. Our work extends well-known universality results of Dembo, Poonen, Shao, and Zeitouni, whose considered the family of real polynomials with all coefficients random. 
    
     As a number-theoretic consequence of these results, we deduce that an algebraic integer α of degree n has exactly m real Galois conjugates with probability n^-b+o(1), when such α are ordered by the heights of their minimal polynomials.
    
    
    § INTRODUCTION
    
    
    
    
    Let (a_i)_i ∈ℕ  denote a sequence of independent and identically distributed (i.i.d.) random variables of zero mean and unit variance possessing finite moments of all order. Consider the polynomials
    
        f_n(x)  x^n-1 + ∑_i= 2^n a_n-ix^n-i,   and   f_n^*(x) ∑_i= 1^n a_n-ix^n-i.
    
    Note that f_n is monic with all subleading coefficients random, whereas f_n^* has all coefficients random. For n odd, let P_n (resp., P_n^*) be the probability that f_n(x) (resp., f_n^*(x)) is everywhere positive; i.e., define
    
        P_n ℙ(f_n(x) > 0, ∀ x ∈),   and   P_n^* ℙ(f_n^*(x) > 0, ∀ x ∈).
    
    In <cit.>, Dembo, Poonen, Shao, and Zeitouni (henceforth, DPSZ) study the asymptotic behavior of P_n^* in the limit as n →∞. Strikingly, they prove that there exists a universal positive constant b, independent of n, such that P_n^* = n^-b+o(1) (i.e., the limit lim_n →∞log_n P_n^* exists and equals -b); see Theorem 1.1(a) in loc. cit. While the value of b remains unknown, it was proven by DPSZ that 0.4≤ b≤ 2, and their numerical simulations suggest that b ≈ 0.76. In light of their remarkable result, 
      *  Does the above result of DPSZ for the full family of random polynomials f_n^*(x) admit an analogue for the special family of monic random 
    polynomials f_n(x)? More specifically, is there a constant b' > 0 such that P_n = n^-b' + o(1)?
    
      *  If the answer to the first question is yes, then how is b' related to b? Are they equal?
    
    In this paper, we give an affirmative answer to both of the above questions. Indeed, we prove:
    
        We have that P_n = n^-b + o(1). 
    
    
    More generally, take j ∈ℕ, take n ≥ j to be of parity different from that of j, and let P_n,j (resp., P_n,j^*) be the probability that f_n(x) (resp., f_n^*(x)) has exactly j simple real zeros; i.e., define
    
        P_n,j(#{x ∈ : f_n(x) = 0,  f_n'(x) ≠ 0} = j),   and   P_n,j^* (#{x ∈ : f_n^*(x) = 0,  f_n^*'(x) ≠ 0} = j).
    
    In this setting, one can ask how P_n,j and P_n,j^* behave asymptotically as n →∞. When j = 0, we have that P_n,0 = P_n and P_n,0^* = P_n^*, and the aforementioned asymptotic formulas apply. In <cit.>, DPSZ prove that, for the full family of random polynomials f_n(x), the same asymptotic formula holds — i.e., we have that P_n,j^* = n^-b+o(1)— for each j, all the way up to j = o(log n/loglog n); see Theorem 1.2 in loc. cit. Our next result gives the analogue for the family of random monic polynomials f_n^*(x):
    
    
        Let j ∈ℕ be such that j ≡ n-1  2. Then we have that P_n,j = n^-b + o(1) as n →∞. In fact, f_n(x) has at most o(log n/loglog n) real zeros with probability n^-b + o(1).
    
    
    Roughly speaking, our methods to prove Theorems <ref> and <ref> involve separating the behavior of the leading term of the random monic polynomial from that of the remaining terms, which comprise a fully random polynomial of one smaller degree. The behavior of this lower-degree polynomial can then be analyzed using results obtained by DPSZ in the course of proving their asymptotic formulas in the context of fully random polynomials. It is natural to expect that similar arguments might work much more generally, to prove analogues of Theorems <ref> and <ref> for random polynomials with multiple fixed coefficients. In this paper, we actually prove these more general theorems, the statements of which are given in <ref>, and we deduce Theorems <ref> and <ref> as consequences.
    
    
    
    
     §.§ Generalizations of Theorems <ref> and <ref> to polynomials with multiple fixed coefficients
    
    
    As alluded to above, our methods allow us to generalize Theorems <ref> and <ref> in two different directions. Firstly, we can fix the values of several coefficients, not just the leading coefficient; and secondly, we can replace the condition of positivity with a much stronger condition. To state these generalizations, we require some further notation. Let k ∈_> 0 be fixed, let S ⊂{1, …, k} be a subset containing k, and for each i ∈ S, fix a number c_i ∈; if 1 ∈ S, take c_1 > 0. Consider the polynomial
    
        f_n,S(x) ∑_i ∈ S c_ix^n-i + ∑_i ∈{1, …,n}
         i ∉S a_n-ix^n-i,
    
    which has random coefficients with the exception of the terms c_i x^n-i for i ∈ S. Let (γ_n)_n be a sequence of non-random functions on , and assume that exists δ > 0 for which n^δ|γ_n(x)| → 0 uniformly over x ∈. For n odd, let P_n,S,γ_n be the probability that the normalized polynomial
    
        f̂_n,S(x) f_n,S(x)/√((f_n,S(x)^2))
    
    is everywhere bigger than γ_n(x); i.e., define
    
        P_n,S,γ_nℙ(f̂_n,S(x) > γ_n(x), ∀ x ∈).
    
    Note that demanding f̂_n,S(x) to be everywhere greater than γ_n(x) is a considerably stronger condition than merely asking f_n,S(x) to be everywhere positive!
    
    
    One cannot reasonably expect that an unconditional analogue of Theorem <ref> would hold with P_n replaced by, say, P_n,S,0 (where by the subscript “0” we mean that γ_n  ≡ 0 is taken to be identically zero for each n). Indeed, one can choose the coefficient data— i.e., the data of the set S, the fixed coefficients c_i for i ∈ S, and the distribution of the random coefficients a_i— in such a way that P_n,S,0 = 0 for infinitely many n.[As we detail in Example <ref> (to follow), one way to do this is to choose the distribution of the a_i to be bounded in absolute value by some constant C, and to choose some of the c_i to be considerably less than -C.] We then analyze the positivity of f_n,S(x) on three ranges of |x|. First, when |x|< 1, the fixed terms matter little, and the lower-degree random terms dominate, making f_n,S(x) > 0 with positive probability. The same  occurs when |x| -1 is sufficiently large, in which case the leading term is positive and dominates over all other terms. But in the middle range, when 0 ≤ |x| -1 is sufficiently small, the fixed terms can contribute large negative quantities to the value of f_n,S(x), forcing it to be negative regardless of the values of the random coefficients. 
    
    The upshot is that, if we are to prove that P_n,S,γ_n obeys an asymptotic similar to that which we obtained for P_n in Theorem <ref>, then we must impose a nontrivial condition on the coefficient data, one that addresses the potential for f_n,S(x) to be negative on the aforementioned “middle range” of |x|. To this end, we shall stipulate the coefficient data be “nice,” where the notion of niceness is defined as follows: 
    
    
        With notation as above, we say that the coefficient data are nice if there exists an even integer s > k such that we have 
        
        ℙ(f_s,S(x) ≠ 0,  ∀ x  s.t.  |x| > 1) > 0.
    
    
    Conditional on the coefficient data being nice, we prove the following generalization of Theorem <ref> about the asymptotic behavior of P_n,S,γ_n:
    
      We have the upper bound P_n,S,γ_n≤ n^-b + o(1). Furthermore, if the chosen data are nice, then we have equality P_n,S,γ_n = n^-b + o(1).
    
         We note that many natural choices of coefficient data are nice. A few interesting examples of such choices are listed as follows:
         
      *  Take the a_i to be standard normal random variables, with any choice of fixed coefficients. In fact, the main results of <cit.>, along with Theorems <ref> and <ref> in the present paper, are proven by using strong approximation results to reduce to the Gaussian case; see Theorem <ref> below.
         
      *  Take the distribution of the a_i to be arbitrary (of zero mean, unit variance, and finite moments of all orders), but take S to consist entirely of odd numbers and take c_i > 0 for each i ∈ S, so that the fixed terms have even degree and positive coefficients. This includes the case of monic polynomials considered in Theorems <ref> and <ref>. In particular, these theorems follow immediately from Theorem <ref> and <ref> by setting S = {1}, c_1 = 1, and γ_n ≡ 0 for all n.
         
      *  Take the distribution of the a_i to have sufficiently large support, relative to the data of the fixed coefficients. More precisely, for every choice of S and (c_i)_i ∈ S, there exists a constant M > 0 depending on these choices such that the coefficient data are nice if (a_i > M) > 0.
         
    
    As mentioned above, the key to proving Theorem <ref> is to prove the corresponding result where the random coefficients a_i are assumed to be Gaussians. In this case, the result of Theorem <ref> holds under a much weaker assumption than stipulating that the functions γ_n converge everywhere to zero. Indeed, we prove:
    
        
            Suppose that (a_i)_i are standard normal random variables, that sup{γ_n(x) : x ∈,  n ∈ℕ} < 1, and that there exists a sequence (ε_n)_n of positive real numbers with limit 0 such that
            
        sup{|γ_n(x)| : ||x|-1| ≤ n^-ε_n}→ 0.
    
            as n →∞. Then we have that P_n,S,γ_n = n^-b+o(1).
        
    
        We also prove the following generalization of Theorem <ref> concerning the probability P_n,j,S that f_n,S(x) has exactly j zeros; once again, the niceness condition is required for the lower bound:
    
    
        Let j∈ℕ be such that j ≡ n-1  2. Then we have the upper bound P_n,j,S≤ n^-b + o(1). If the chosen data are nice, then we have equality P_n,j,S = n^-b + o(1). Furthermore, the polynomial f_n(x) has at most o(log n/loglog n) real zeros with probability at most n^-b + o(1), with equality if the 
    It is important to note that our proof of Theorem <ref> does not rely on Theorem <ref> or its proof. Observe that if we take n to be odd and j to be even in Theorem <ref>, we obtain Theorem <ref> in the special case where γ_n ≡ 0. Further taking S = {1} and c_1 = 1 gives a second proof of Theorem <ref>. On the other hand, the much stronger Theorem <ref> cannot be similarly deduced from Theorem <ref>.
    
     Incidentally, our methods allow us to obtain some results in cases where the number of fixed coefficients is allowed to grow slowly with n. A particular case of interest is that of monic polynomials with many consecutive coefficients fixed to be zero. To set this up, let k(n) be a nondecreasing function with values in ℕ, let S_n = {1, …, k(n)}, let c_1 = 1 and c_i = 0 for all i ≥ 2, and consider the random polynomial f_n,S_n(x). Explicitly, we have
          
        f_n,S_n(x) = x^n-1 + ∑_i = k(n)+1^n a_n-ix^n-i.
    
          Then we have the following analogue of Theorem <ref>, which holds in the regime where log k(n) grows slower than √(log n) (with a somewhat weaker condition in the Gaussian case):
        
        Let notation be as above, and suppose that k(n) = n^o(1) in the case of Gaussian coefficients, and that k(n) = n^o(1/√(log n)) in the case of general coefficients. Then we have
        P_n, S_n,γ_n = n^-b + o(1).
        
        The following analogue of Theorem <ref> holds in the tighter regime where k(n) grows slower than log n.
        
        Let notation be as above, and suppose that k(n) = o(log n). Let j∈ℕ be such that j ≡ n-1  2.  Then we have
        P_n, j,S_n = n^-b + o(1).
        
    
     §.§ Application to counting algebraic integers
    
    
    
    As a consequence of Theorem <ref>, we can deduce asymptotic counts of algebraic integers having few or no real Galois conjugates. Before stating this application, we must define how we count algebraic  we must put a height function on them. Given an algebraic integer α, let α' be the unique -translate of α with trace lying in {0,…, n-1}, and let p(x) = x^n + ∑_i = 1^n p_ix^n-i∈[x] be the minimal polynomial of α'. Then we define the height of the equivalence class of α to be max_i ∈{1,  …, n} |p_i|^1/i.
    
    We say that a nonzero algebraic integer α is j-realizable if it has exactly j real Galois conjugates. For instance, an algebraic integer α of degree n is 0-realizable if it is totally complex and n-realizable if it is totally real. Then Theorem <ref> has the following immediate corollary giving an asymptotic formula for the density of j-realizable algebraic integers:
    
    
    
        Let j ∈ℕ be fixed. When algebraic integers α of degree n ≡ j  2 are ordered by height, the density of α that are j-realizable is n^-b+o(1).
    
    
    Indeed, note that Corollary <ref> follows from Theorem <ref> by taking the distribution of the a_i to be the uniform distribution on [-√(3),√(3)], and taking k = 1, S = {1}, and c_1 = √(3). Note that the factor of √(3) arises because the a_i are required to have unit variance.
    
    
    The problem of counting algebraic integers satisfying interesting conditions at the archimedean places has been studied before in the literature. Of particular relevance to the present paper is the work of Calegari and Huang <cit.> (cf. the closely related earlier work of Akiyama and Pethő <cit.>), who consider algebraic integers ordered by a somewhat different height function, namely, the absolute value of the largest Galois conjugate. With respect to this height, they determine precise asymptotics for densities of various types of algebraic integers, including the totally complex subfamily, for which they obtain a density ≍ n^-3/8. Proving this result amounts to studying monic real polynomials, all of whose roots have absolute value at most 1; note that such polynomials are special in that they are positive on  if and only if they are positive on [-1,1]. On the other hand, by modifying the proof of Theorem <ref>, it is possible to show that a random monic polynomial is positive on [-1,1] with probability n^-b/2 + o(1). As observed in <cit.>, this raises the intriguing question of whether the densities n^-3/8 and n^-b/2 + o(1) agree — i.e., whether b is in fact equal to 3/4, a result that would seemingly concur with the aforementioned numerical simulations performed by DPSZ, which indicated that b ≈ 0.76.
    
         Our main results have other applications of arithmetic interest. For instance, by combining this theorem with the main results of <cit.>, one obtains an tighter upper bound on the proportion of superelliptic equations having no integral solutions. Specifically, in <cit.>, the proportion of  superelliptic equations having no integral solutions is bounded in terms of various local densities, one of which happens to be the density of monic polynomials of bounded height with a specified number of real roots. To control this density, the trivial bound of 1 is used; however, applying Theorem <ref> instead of the trivial bound would tighten the main results of <cit.> by a factor of o(1). This is in complete analogy with how the results of <cit.> were applied in <cit.> and in <cit.> to obtain bounds on the proportion of hyperelliptic curves having no rational points over odd-degree number fields. Here, the proportion of such “pointless” curves is bounded in terms of various local densities, one of which happens to be the density of not-necessarily-monic polynomials of bounded height with a specified number of real roots (hence the relevance of <cit.>).
    
    
     §.§ Summary of related earlier work
    
    For at least the past century, mathematicians have been interested in the number of real zeros, say N_n of random degree n - 1 polynomials of the form 
    ∑_i = 1^n a_n - i A_n - i x^n - i where the A_n - i are deterministic real numbers depending on n and i, and the a_n - i are i.i.d. with zero mean and unit variance, as above. The case of Kac polynomials, which arise from setting each A_n - i = 1 has been of particular interest. In 1932, Bloch and Polya considered a_i chosen uniformly at random from {-1, 0, 1} and showed 𝔼(N_n) = O(n^1/2)<cit.>. 
    Beginning in 1938, Littlewood and Offord followed this with a series of papers <cit.> studying N_n for three coefficient distributions: standard normal, uniform on [-1, 1], and Bernoulli on {-1, 1}. In each case, they showed that there exist constants A, B > 0 such that the following holds:
    
        A log n/(loglog n)^2≤ N_n ≤ B (log n)^2 
            w.p. 1 - o(1) as n →∞.
    
    In 1943, Kac found an exact formula for the density function of N_n for any coefficient distribution with zero mean and finite variance, which he used to obtain the estimate 𝔼(N_n) = (2/π + o(1)) log n in the case of the standard Gaussian distribution <cit.>. Kac stated that along with the central limit theorem, his work would give the same formula for 𝔼(N_n) for many other coefficient distributions. 
    
    Kac's work was the first suggestion of the universality phenomenon in the context of N_n. In probability theory, universality refers to the case when a limiting random object as n goes to infinity (such as the real number lim_n →∞𝔼(N_n)/log n) is insensitive to the particular distributions of i.i.d. atoms (such as coefficients a_i) from which the random object is obtained. The study of universality for the quantity N_n has attracted significant interest from probabilists and number theorists.  
    Indeed, it is not only the expectation lim_n →∞𝔼(N_n)/log n that exhibits universality. 
    In several papers <cit.> ending in Maslova's work in 1974, Ibragimov and Maslova further illuminated the distribution of N_n, culminating in a central limit theorem for N_n. 
    In 2002, DPSZ demonstrated with their study of ℙ(N_n = 0) that it was not just the limiting shape of the CDF in Maslova's work but also the extreme left tail of the CDF for N_n that exhibits a universal behavior, independent of the law of a_i. When some of the leading coefficients are fixed, our Theorem <ref> reveals a clean dichotomy: unless the choices of fixed coefficients and random coefficient distribution force the problem to be degenerate in a precise way, the limiting behavior of ℙ(N_n = 0) is universal with respect to the random coefficient distribution and the fixed coefficients. 
    
    DPSZ state that their interest in P_n^* arose from work of Poonen and Stoll in arithmetic geometry, which found the probability that a random hyperelliptic curve y^2 = f(x) of genus g over  has odd Jacobian <cit.>. Poonen and Stoll reduced the problem to the computation of local probabilities, one for each completion of , and the archimedean completion required the computation of the probability that y^2 = f(x) has no real points, or, equivalently, that f(x) < 0 holds on all of . Importantly, this probability arose with the coefficients of f having a uniform distribution. Further, for the application of DPSZ's work in <cit.> and <cit.> and for the application of our main results to <cit.> and our Corollary 10, the relevant case is again that of uniformly distributed a_i. Meanwhile, the work of DPSZ shows that the probability P_n^* is easiest to find when the coefficient distribution is Gaussian. Indeed, for DPSZ, handling the uniform distribution is no easier than handling a general distribution with zero mean, unit variance, and finite moments, and we find the same in our work. Even for the problem of determining asymptotics of 𝔼(N_n), Kac found the Gaussian distribution most tractable and did not solve the uniform case until six years later <cit.>. Thus, when studying the real zeros of f_n, S(x), proving universality reduces the arithmetically interesting case of the uniform distribution to the case of the Gaussian distribution, 
    The question of how often a polynomial over  has a specified number of zeros admits an interesting analogue over the nonarchimedean completions of . Specifically, for a prime number p, one can ask: what is the probability that a random polynomial (or random monic polynomial) with p-adic integer coefficients has exactly m roots in the fraction field _p? This and other related questions were studied in detail by Bhargava, Cremona, Fisher, and Gajović <cit.>, who proved that the desired probability is a rational function of n, m, and p. Intriguingly, they show that this rational function is invariant under p ↦ 1/p; this invariance phenomenon was subsequently demonstrated by G., Wei, and Yin to be a consequence of Poincaré duality for the zeta-functions of certain relevant varieties
    <cit.>.
    
    
     §.§ Organization
    
    
    The rest of this paper is organized as follows. We start in <ref> by proving Theorem <ref>, and then in <ref>, we deduce Theorems <ref> and <ref> (and hence also Theorem <ref>) from Theorem <ref>. We finish in <ref> by proving Theorems <ref> and <ref> (and hence also Theorem <ref> and Corollary <ref>). Each of <ref>–<ref> is divided into two subsections, the first of which proves the relevant “lower bound”— i.e., that the desired probability is at least n^-b + o(1)— and the second of which proves the corresponding “upper bound”— i.e., that the desired probability 
    
    § PROOF OF THEOREM <REF>— THE CASE OF GAUSSIAN COEFFICIENTS
    
    
    In this section, we prove Theorem <ref>, which is a version of our main result where the random coefficients (a_i)_i are taken to be standard normal random variables. Where necessary, we highlight how the proof readily adapts to obtain Theorem <ref>
    
    In the rest of this section, we take k, S, (c_i)_i ∈ S, and (γ_n)_n to be as in the setting of Theorem <ref>. Following notation used in <cit.> for the Gaussian case, we denote the random degree-n polynomial with fixed coefficients as f_n,S^b(x) and the fully random degree-n polynomial as f_n^b,*(x), and we denote the corresponding normalized polynomials as f̂_n,S^b(x) and f̂_n^b,*(x), respectively. The proof makes crucial use of Slepian's lemma, which is a Gaussian comparison inequality and can be stated as follows (c.f. <cit.>):
    
    [Slepian] Let X_t and Y_t be two centered Gaussian processes of equal variance on a subset T ⊂. (I.e., take X_t and Y_t such that (X_t) = (Y_t) = 0 and (X_t^2) = (Y_t^2) for all t ∈ T.) Suppose that X_t has everywhere greater covariance, so that for all s, t ∈ T, we have Cov(X_s, X_t) ≥Cov(Y_s, Y_t). Then, for any λ∈, we have (inf_t ∈ T X_t ≥λ) ≥(inf_t ∈ T Y_t ≥λ). 
    
    
     §.§ Lower bound
    
    
    To obtain the lower bound, we split into cases according to the parity of k. In <ref>, we handle the case where k is even, and in <ref>, we explain how the argument of <ref> can be modified when k is odd. 
    
    
    
      §.§.§ The case where k is even
    
    
    Let k be even. By moving the terms a_n-1x^n-1, …,  a_n-kx^n-k to the right-hand side and renormalizing, one readily verifies that the condition f̂_n^b(x) > γ_n(x) is equivalent to the following condition:
    
        f̂_n-k^b,*(x) >  γ_n(x)√(1+i ∈  S∑ c_i^2x^2(n-i) + i ∈{1, …, k}∖ S∑ x^2(n-i)/i=1n-k∑ x^2(n-k-i)) -i ∈ S∑ c_ix^n-i + i ∈{1,…,k}∖ S∑ a_n-ix^n-i/√(i = 1n-k∑x^2(n-k-i)).
    
    For the purpose of obtaining a lower bound, we can restrict a_n-i to lie within the interval [1/2,1] for each i ∈{1, …, k}∖ S. After making this restriction, we can also strengthen the condition (<ref>) (i.e., make it less probable) by replacing the right-hand side with a larger quantity. To this end, for each i ∈{1,…,k}∖ S, let χ_i →{0,1/2,1} be the function defined as follows:
    
        χ_i(x) =  1,     if i is even and x < 0,
        
        1/2,     if i is odd,
         
        0,     otherwise.
    
    Then define γ_n^*(x) by
    
        γ_n^*(x) γ_n(x)√(1+i ∈  S∑ c_i^2x^2(n-i) + i ∈{1, …, k}∖ S∑ x^2(n-i)/i=1n-k∑ x^2(n-k-i))  -i ∈ S∑ c_ix^n-i + i ∈{1,…,k}∖ S∑χ_i(x)x^n-i/√(i = 1n-k∑x^2(n-k-i)).
    
    Then the condition (<ref>) is implied by the stronger condition f̂_n-k^b,*(x) > γ_n^*(x), and so we have that
    
        (f̂_n,S^b(x) > γ_n(x), ∀ x ∈)    ≥(f̂_n,S^b(x) > γ_n(x), ∀ x ∈;  and  a_n-i∈ [1/2,1], ∀ i ∈{1, …, k}∖ S) 
           ≥(f̂_n-k^b,*(x) > γ_n^*(x), ∀ x ∈;  and  a_n-i∈ [1/2,1], ∀ i ∈{1, …, k}∖ S) 
            = (f̂_n-k^b,*(x) > γ_n^*(x), ∀ x ∈)×∏_i ∈{1,…, k}
         i ∉S(a_n-i∈ [1/2,1]).
    
    In (<ref>), the product over i is a nonzero constant, depending only on k and S. Note that this product is trivial in the setting of Theorem <ref>. Thus, it suffices to bound the first probability in (<ref>).
    
    Our assumptions on γ_n(x) in the statement of Theorem <ref> imply that there exist integers τ_n such that logloglog n τ_n log n and such that sup{γ_n(x) : |x| ∈ [1 - ξ_n,(1-ξ_n)^-1]}→ 0, where ξ_n = e^-τ_n.[Here, we say that a  a' if a = o(a') as n →∞.] In the setting of Theorem <ref>, this changes slightly: we take τ_n log k(n), instead of logloglog n. Since k is even, the covariance of f_n-k^b,*(x) is everywhere nonnegative,[Note that this is not true in the case where k is odd, which therefore necessitates separate treatment (see <ref>).] which allows us to apply Slepian's lemma. Doing so, we find that
    
        (f̂_n-k^b,*(x) > γ_n^*(x), ∀ x ∈) ≥
               (f̂_n-k^b,*(x) > γ_n^*(x), ∀ x ∈ [0,(1-ξ_n)^-1]) ×(f̂_n-k^b,*(x) > γ_n^*(x), ∀ x ∈ [-(1-ξ_n)^-1,0])×
                   (f̂_n-k^b,*(x) > γ_n^*(x), ∀ x ∈ [(1 - ξ_n)^-1,∞))  ×(f̂_n-k^b,*(x) > γ_n^*(x), ∀ x ∈ (-∞,-(1 - ξ_n)^-1]).
    
    We start by handling the first two probabilities on the right-hand side of (<ref>). The idea is to verify that these probabilities are of the form studied in <cit.>. Indeed, it follows immediately from the results of <cit.> in conjunction with Slepian's lemma that each of the first two probabilities on the right-hand side of (<ref>) is at least n^-b/2+o(1), as long as the following two conditions are satisfied:
    
        sup{γ_n^*(x) : x ∈ [-1+ξ_n,1-ξ_n],  n ∈ℕ} < ∞,   and
           sup{|γ_n^*(x)| : |x| ∈ [1-ξ_n,(1-ξ_n)^-1]}→ 0
    
    as n →∞. To verify the conditions (<ref>) and (<ref>), note that we have the following useful bound:
    
        sup{|x^n-j|/√(∑_i = 1^n-k x^2(n-k-i)): |x| ∈ [0,(1-ξ_n)^-1]} = (1-ξ_n)^-(n-j)/√(∑_i = 1^n-k(1-ξ_n)^-2(n-i))≪√(ξ_n)/(1-ξ_n)^k-j,
    
    where the implied constant is absolute. In the first step of (<ref>), we have used the fact that the quantity being maximized is increasing in |x|. Summing the bound (<ref>) over j ∈{1, …, k} using our assumption that log k τ_n, which implies that k  1/√(ξ_n) = e^τ_n/2 (note that this holds in both the settings of Theorems <ref> and <ref>), we find that
    
        ∑_j = 1^k √(ξ_n)/(1-ξ_n)^k-j≪√(ξ_n)×(1 - ξ_n)^-k-1/(1 - ξ_n)^-1-1≪√(ξ_n)×kξ_n/ξ_n≪ k√(ξ_n),
    
    which tends to zero as n →∞. From this, we deduce a few consequences: first, the factor multiplied by γ_n(x) in (<ref>) is bounded for | x |≤ (1 - ξ_n)^-1; and second, the terms being subtracted on the right-hand side of (<ref>) converge to zero uniformly over |x| ≤ (1-ξ_n)^-1. Note that both of these conclusions continue to be true in the setting of Theorem <ref>. The conditions (<ref>) and (<ref>) now follow from our assumptions on γ_n(x).
    
    
    
    We now bound the second two probabilities on the right-hand side of (<ref>). Since c_1 > 0 if 1 ∈ S and since χ_1(x) > 0 if 1 ∉S, and because γ_n(x) < 1 for all x ∈ and n ∈ℕ, there exists a constant C > 0, depending only on S and the values of the c_i, such that γ_n^*(x) < C for all x such that |x| ∈ [(1-ξ_n)^-1,∞). Note that C can be taken to be an absolute constant in the setting of Theorem <ref>. Thus, we have that
    
        (f̂_n-k^b,*(x) > γ_n^*(x), ∀ x ∈ [(1-ξ_n)^-1,∞))     ≥(f̂_n-k^*(x) > C, ∀ x ∈ [(1-ξ_n)^-1,∞)),
        
        (f̂_n-k^b,*(x) > γ_n^*(x), ∀ x ∈ (-∞,-(1-ξ_n)^-1])     ≥(f̂_n-k^*(x) > C, ∀ x ∈ (-∞,-(1-ξ_n)^-1]),
    
    for all n ≫ 1. The probabilities on the right-hand sides of (<ref>) and (<ref>) are of the form studied in <cit.>, where they were each shown to be at least n^o(1). This completes the proof of the lower bound.
    
    
    
      §.§.§ The case where k is odd
    
    
    Now let k be odd. Here, in addition to moving the first k terms of the polynomial f_n^b(x) to the right-hand side, we move the (random) term a_n-k-1x^n-k-1 to the right-hand side as well. As before, we restrict a_n-k-1 to lie within the interval [1/2,1], and we replace a_n-k-1 with χ_k+1(x), and the rest of the argument proceeds exactly as in <ref>.
    
    
    
     §.§ Upper bound
    
    
    We now proceed with the proof of the upper bound. We start in <ref>, where we work out the case in which the fixed coefficients c_i are all zero, and we finish in <ref> by explaining how to deduce the result for general c_i from the case where they are all zero.
    
    
    
      §.§.§ The case where c_i = 0 for all i ∈ S
    
    
     In this section, we assume that c_i = 0 for all i ∈ S. In particular, we may assume without loss of generality that 1 ∉S (recall, on the other hand, that k ∈ S by assumption), and in particular, we are not in the setting of Theorem <ref>, and so we may keep k fixed.
    
     Notation. We first set some notation. To bound the probability (f̂_n,S^b(x) > γ_n(x)), it is useful to obtain bounds on the covariance c_n of f̂_n,S^b, which is given explicitly as follows:
    
        c_n(x, y)     = 𝔼(f_n,S^b(x) f_n,S^b(y))/√(𝔼(f_n,S^b(x)^2) 𝔼(f_n,S^b(y)^2))
            = (xy)^n-k-1r(xy) + ∑_i = 1^n-k (xy)^n-k-i/√((x^2(n-k-1)r(x^2) + ∑_i = 1^n-k x^2(n-k-i))(y^2(n-k-1)r(y^2) + ∑_i = 1^n-k y^2(n-k-i))),
    
    where we have set r(z) ∑_i ∈{1, … , k}∖ S z^k + 1 - i. 
    We will also have occasion to use the function g defined by
    
        g(x, y) = | xy - 1|/√(| (x^2-1)(y^2-1) |).
    
    Lastly, for the purpose of proving upper bounds, it suffices to restrict our attention to small subintervals of . To this end, fix δ∈ (0,1/2), and define the four intervals I_1  [1 - n^-δ,1 - n^-(1-δ)], I_2I_1^-1, I_3  -I_2, and I_4  -I_1. Set 
    
        V ⋃_i=1^4 I_i   and   U ⋃_i = 1^4 I_i^2 ⊂ V^2.
    The proof. Let n be odd or even. Let α_n ∈ [0,n^-δ/2], to be chosen later, and let χ_U ^2 →{0,1} denote the indicator function of the subset U ⊂^2. In <cit.>, the upper bound (f̂_n^b,*(x) > γ_n(x)) ≤ n^-b+o(1) is obtained in the case of Gaussian coefficients by constructing an auxiliary Gaussian process f_n(x) with covariance given by
    
        (1 - α_n)/g(x,y)χ_U(x,y) + α_n.
    
    Let c_n^*(x,y) denote the covariance of f̂_n^*(x)  f_n^*(x)/(f_n^*(x)^2). It is shown in <cit.> that, for a suitable choice of α_n, the covariance (<ref>) is an upper bound on c_n^*(x,y) for all x,y ∈ V, and that this upper bound specializes to an equality when x = y.  Thus, Slepian's lemma implies that to bound (f̂_n^b,*(x) > γ_n(x)) from above, the process f̂_n^b,*(x) can effectively be replaced with the process f_n(x), which turns out to be easier to work with.
    
    An identical argument applies to prove that (f̂_n,S^b(x) > γ_n(x)) ≤ n^-b+o(1), so long as we can show that the covariance c_n(x,y) is bounded above by (<ref>), with equality when x = y. We prove this as follows:
    
         For x,y ∈ V, and for all n ≫ 1, there exists α_n ∈ [0, n^-δ/2] such that
        
        c_n(x,y) ≤(1 - α_n)/g(x,y)χ_U(x,y) + α_n,
    
        with equality when x = y.
    
    First, assume (x,y) ∈ U. That we have equality when x = y is obvious — indeed, c_n(x,x) = g(x,x) = 1. Consequently, we may assume that x ≠ y (in particular, we can divide by x -y, as we do multiple times in what follows). Now, by symmetry, it in fact suffices to take x,y ∈I_1 or x,y ∈I_2. We handle each of these cases separately as follows:
    
    Case 1: x,y ∈I_1. 
    To start, note that the product g(x,y)c_n(x,y) may be rewritten as follows, writing r(z) for (z - 1) r(z):
    
        g(x,y)c_n(x,y) = 
           |xy-1|/√(|(x^2-1)(y^2-1)|)×(xy)^n-k-1r(xy) + ∑_i = 1^n-k (xy)^n-k-i/√((x^2(n-k-1)r(x^2) + ∑_i = 1^n-k x^2(n-k-i))(y^2(n-k-1)r(y^2) + ∑_i = 1^n-k y^2(n-k-i))) = 
           sign(xy-1) ×r(xy) + 1 - (xy)^k-n/√((r(x^2) + 1 - x^2(k-n))(r(y^2) + 1 - y^2(k-n))).
    
    Rearranging (<ref>) using (<ref>), and observing that 0 ≤ g(x,y)≪ 1 and g(x,y)c_n(x,y) = 1 + o(1) for x,y ∈I_1 we see that it suffices to prove the following bound:
        
        n^-δ   ≫(g(x,y)c_n(x,y))^2 - 1/g(x,y)^2-1 = (1-x^2)(1-y^2)  [r(xy)^2-r(x^2)r(y^2)/(x-y)^2 +  . 
               . -r(x^2)x^2 + 2r(xy)xy - r(y^2)y^2/(x-y)^2   + -r(y^2)x^-2n + 2r(xy)x^-ny^-n - r(x^2)y^-2n/(x-y)^2  + (x^-n-y^-n/x-y)^2 ]
    
    The first and second terms in the square brackets on the right-hand side of (<ref>) are easily seen to be ≪ 1 (where the implied constant depends on k =  r). The third and fourth terms are each o(1) as n →∞, and the external factor of (1-x^2)(1-y^2) is ≪ n^-2δ.
    
        Case 2: x,y ∈I_2. Here, we prove the stronger result that
    g(x,y)c_n(x,y) ≤ 1 (i.e., for this case, we can take α_n = 0). Applying (<ref>), squaring both sides of this stronger inequality, cross-multiplying, and moving the terms to the left-hand side, we see that it suffices to prove that
    
        (r(xy)+1)^2 - (r(x^2)+1)(r(y^2)+1) ≤ 0.
    
    Denote the left-hand side of (<ref>) by L(x,y), and for any integer m ≥ k =   r, let L_m(x,y) denote the same expression with r(z) replaced by r(z) + z^m. Then it suffices to prove that L_m(x,y)  L_m(x,y) - L(x,y) ≤ 0. We compute that
    
        L_m(x,y)/(x-y)^2    = x^2my^2m + (x^m-y^m/x-y)^2-(x^m+1-y^m+1/x-y)^2 + 
                                 2(xy-1/x-y)^2r(xy)x^my^m -(x^2-1)(y^2-1)/(x-y)^2(r(y^2)x^2m+r(x^2)y^2m).
    
    We start by estimating the first line of the right-hand side of (<ref>). For x,y ∈I_2, the first term is 1 + o(1), the second is m^2 + o(1), and the third is -(m+1)^2 + o(1), making for a total of -2m + o(1). As for the second line of (<ref>), assume that r(z) = z^e, where e ∈{1, …, k}. Under this assumption, the second line of (<ref>) may be conveniently reexpressed as follows:
    
        x^2ky^2k[(x^m-k+1-y^m-k+1/x-y)^2 + x^2y^2(x^m-k-1-y^m-k-1/x-y)^2-(x^2y^2+1)(x^m-k-y^m-k/x-y)^2]
    
    For x,y ∈I_2, the quantity (<ref>) the first term is (m-k+1)^2 + o(1), the second is (m-k-1)^2 + o(1), and the third is -2(m-k)^2 + o(1), making for a total of 2 + o(1). Thus, when r is a monomial, the second line of (<ref>) contributes 2 + o(1). Since this second line is linear in r, it follows that for any r, we get a contribution of at most 2k + o(1) ≤ 2m-2 + o(1). We conclude that L_m(x,y) ≤ (x-y)^2(-2 + o(1)) for all x,y ∈I_2, so taking n ≫ k to be sufficiently large yields the desired inequality.
    
     Finally, consider the case where x,y ∈ V ∖ U. Without loss of generality, we may assume that |x| ∈I_1 and |y| ∈I_2. Then y^-n≪ e^-n^1-δ and x^-n≫ e^n^δ, from which we can apply (<ref>) to deduce that |g(x,y)c_n(x,y)| ≪ e^-n^δ. Since |g(x,y)| ≪ n^1-δ, the desired bound follows.
    
    The upper bound  (f̂_n,S^b(x) > γ_n(x)) ≤ n^-b+o(1) is then deduced from Lemma <ref> exactly as the upper bound (f̂_n^b,*(x) > γ_n(x)) ≤ n^-b+o(1) is deduced from <cit.>; we omit the details for the sake of brevity. 
    
    
    
      §.§.§ The case of general c_i
    
    
    We now take c_i ∈ for each i ∈ S in such a way that c_1 > 0 if 1 ∈ S. Let f_n,0(x)  f_n,S^b(x) - ∑_i ∈ Sc_ix^n-i, and as usual, let f̂_n,0(x)  f_n,0(x)/(f_n,0(x)^2). Define γ_n^**(x) by
    
        γ_n^**(x) γ_n(x)√(1+i ∈  S∑ c_i^2x^2(n-i) + i ∈{1, …, k}∖ S∑ x^2(n-i)/i=1n-k∑ x^2(n-k-i))  -i ∈ S∑ c_ix^n-i/√(i = 1n-k∑x^2(n-k-i)).
    
    (Note the distinction between γ_n^*(x), defined in (<ref>), and γ_n^**(x).) 
    Evidently the condition f̂_n,S^b(x) > γ_n(x) is equivalent to the condition f̂_n,0(x) > γ_n^**(x), so we have that
    
        (f̂_n,S^b(x) > γ_n(x), ∀ x ∈)     = (f̂_n,0(x) > γ_n^**(x), ∀ x ∈) ≤(f̂_n,0(x) > γ_n^**(x), ∀ x ∈ V).
    
    Now, it is shown in <ref> that
    
        (f̂_n,0(x) > γ_n^**(x), ∀ x ∈ V) ≤ n^-b+o(1),
    
    as long as |γ_n^**(x)| → 0 uniformly for x ∈ V. To verify that this condition holds, we imitate the bound in (<ref>) to find that
    
        sup{|x^n-j|/√(∑_i = 1^n-k x^2(n-k-i)): x ∈ V} = (1-n^-δ)^-(n-j)/√(∑_i = 1^n-k(1-n^-δ)^-2(n-i))≪n^-δ/2/(1-n^-δ)^k-j.
    
    Summing the bound (<ref>) over j ∈{1,…,k} just as in (<ref>), we obtain a bound of kn^-δ/2, which converges to zero as n →∞. Note that this convergene holds even in the setting of Theorem <ref>, where k = n^o(1).
    
    
    
    This completes the proof of Theorem <ref>, as well as the proof of Theorem <ref> in the case where the coefficient distributions are Gaussians.
    
    
    
    § PROOFS OF THEOREMS <REF> AND <REF>— THE CASE OF GENERAL COEFFICIENTS
    
    
    In <cit.>, the authors use the  Komlós-Major-Tusnády (henceforth, KMT) strong approximation theorem (see, e.g., <cit.>) to extend their asymptotic formula for P_n^* in the case of Gaussian coefficients to the case where the coefficient distribution is arbitrary (having zero mean, unit variance, and finite moments of all orders). The rough idea of their argument is to partition the random polynomial into several chunks, and to analyze the contributions of each chunk separately.
    
    The purpose of this section is to deduce Theorems <ref> and <ref> (and hence also Theorem <ref>) from Theorem <ref> by means of an analogous method. The key difference is that one of the chunks of the polynomial contains all of the terms with the fixed coefficients. It is precisely to control the behavior of this chunk that we impose the “niceness” condition introduced in Definition <ref>. The following simple example demonstrates the necessity of the niceness condition:
    
       Let the law of the a_i be the uniform distribution from [-√(3),√(3)], let k = 2, let S = {1,2}, and let c_1 = 1 and c_2 = -2024. Then, no matter what values are taken by the a_i, and for every n ≥ 2, the polynomial f_n,S(x) takes a negative value at x = 2. Indeed, we have in this case that
       
        f_n,S(2) ≤ 2^n-1 - 2024 × 2^n-2 + √(3)×(2^n-2-1) ≤ 2^n-2×(2 - 2024 + √(3)) < 0.
    
    
     §.§ Approximation of coefficients by Gaussians via KMT
    
    
    We start by applying the KMT strong approximation theorem. In doing so, we shall make use of the following observation: for every strictly increasing sequence of nonnegative even integers 0 = k_0 < k_1 < … <  k_ℓ and every x ∈ [-1,1], the sequence
    
        {x^k_j - x^k_j+1 : j∈{0,…,ℓ-1}}∪{x^k_ℓ}
    
    forms a probability distribution (i.e., each term is nonnegative, and the sum of the terms is 1). Thus, for any s_0,…,s_k ∈, we have that
    |s_0 + ∑_j=1^ℓ (s_j-s_j-1) x^k_j|
    = |s_ℓ x^k_ℓ +  ∑_j=0^ℓ-1 s_j (x^k_j - x^k_j+1) |
    ≤max_0 ≤ j ≤ℓ|s_k_j|  .
    
    
    Now, let k ≥ 1, let m ≫ k, and choose any subset S ⊂{1,…,k} that is either empty or contains k. Because (a_i)=0 and (a_i^2)=1 for each i ∈ℕ, a double application of the KMT strong approximation theorem yields the following result: we can redefine the random variables {a_i : i ∈{0, …, m-1} and  m-i ∉S} on a new probability space
    with a corresponding sequence of
    independent standard normal random variables {b_i : i∈{0,…,m-1} and  m-i ∉S}
    such that for any p≥ 2, some χ_p > 0 that depends only on p, and all t>0, we have that
    (max_0 ≤ j ≤n-1/2|∑_ i ∈{0,…,j}
     n-2i ∉S(a_2i - b_2i)|
    ≥ t) +
    (max_0 ≤ j ≤n-3/2|∑_i ∈{0,…,j}
     n-(2i+1) ∉S(a_2i+1 -b_2i+1)|
     ≥ t) ≤χ_p n |a_0|^p t^-p .
    
    Note that we can express the right-hand side of (<ref>) solely in terms of a_0 because the coefficients a_i are identically distributed. By the triangle inequality, we have
    |∑_i ∈{0,…, m-1}
     m-i ∉S (a_i - b_i) x^i| ≤|∑_i ∈{0,…, ⌊m-1/2⌋}
     m-2i ∉S (a_2i-b_2i) x^2i|
    +|∑_i ∈{0,…,⌊m-2/2⌋}
     m-(2i+1) ∉S (a_2i+1- b_2i+1)
    x^2i+1|
    
    so applying (<ref>) twice — first taking s_j=∑_i ∈{0,…,j}
     m-2i ∉S (a_2i-b_2i), and then taking
    s_j=∑_i ∈{0,…, j}
     m-(2i+1) ∉S(a_2i+1-b_2i+1)— and combining the result with (<ref>) and (<ref>) yields that for all m ≤ n, we have
    (sup_|x| ≤ 1|f_m,S(x)-f_m,S^b(x)| ≥  2 t ) ≤χ_p n |a_0|^p t^-p,
    
    where f_m,S^b is defined by
    
        f_m,S^b(x) ∑_i ∈ S c_i x^m-i + ∑_i ∈{1, …, m}
         i ∉S b_m-ix^m-i.
    
    
    Notice that (<ref>) only covers the region where |x| ≤ 1. To handle the region |x| ≥ 1, we invert x and consider the random polynomial in reverse. Indeed, define
    
        g_m,S(x)  x^m-1 f_m,S(x^-1) = ∑_i∈ S c_i x^i-1 + ∑_i ∈{1, …, m}
         i ∉S a_m-i x^i-1 ,
    
    and similarly define g_m,S^b(x)  x^m-1 f_m,S^b(x^-1). By an analogous argument, we also obtain for all m ≤ n the bound
    (sup_|x| ≤ 1|g_m,S(x)-g_m,S^b(x)| ≥  4t) ≤χ_p n |a_0|^p t^-p.
    
    Indeed, bounding |g_m,S-g_m,S^b| amounts to replacing (a_i,b_i) with
    (a_m-1-i,b_m-1-i)— which leads us to take s_j = ∑_i ∈{0,…, j}
     m-2i ∉S (a_m-1-2i-b_m-1-2i) first, and to take next s_j = ∑_i ∈{0,…, j}
     m-(2i+1) ∉S (a_m-1-(2i+1)-b_m-1-(2i+1)). Note that the approximation error doubles from 2t to 4t because the partial sums s_j are now computed in reverse; for instance, we have
    
        max_0 ≤ j ≤⌊m-1/2⌋|∑_ i ∈{0,…,j}
         2i+1 ∉S(a_m-1-2i - b_m-1-2i)| ≥ 2t   ⟹  max_0 ≤ j ≤⌊m-1/2⌋|∑_ i ∈{0,…,j}
         m-2i ∉S(a_2i - b_2i) |  ≥ t.
    
    
     §.§ Notation and setup
    
    
    In this section, we introduce the notation necessary for us to partition the random polynomial into pieces and complete the proof of Theorem <ref>. Let n, k, S be as in the setting of the theorem, and for m ≫ k, define the following quantities
    
        σ_m,S(x)√((f_m,S(x)^2))  and  σ_m,S(x) √((g_m,S(x)^2)),
    
    and following (<ref>), define the normalized random polynomials
    
        f̂_m,S(x)f_m,S(x)/σ_m,S(x)  and  f̂^b_m,S(x) f^b_m,S(x)/σ_m,S(x); 
           ĝ_m,S(x)g_m,S(x)/σ_m,S(x)  and  ĝ^b_m,S(x) g^b_m,S(x)/σ_m,S(x).
    
    Following the convention in <ref>, we write f_m  f_m,∅, g_m  g_m,∅, and σ_m σ_m,∅ = σ_m,∅.
    Just as in <cit.>, we introduce the following list of n-dependent quantities and functions:
    [                                              p_n:                          p_n↑∞, χ_p_n|a_0|^p_n≤ n                                             χ_p_n;                                              ϵ_n:             ϵ_n↓ 0, ϵ_n≥max{20/p_n,(log n)^-1/2},                                               ϵ_n;                                                                                         2n^3ϵ_n=2^j                                                  ;                                              m_n:                                m_n→∞, m_n=2n^3ϵ_n                                                  ;                                              γ_n:                    γ_n(x)=max{0,γ_n(x),γ_n(x^-1)}                                                  ;                                              σ_n:                     σ_n(x)=max{σ_n,S(x),σ_n,S(x)}                                                  ;                                              ρ_n: ρ_n→ 0,
    ρ_n = sup_|x| ≤ 1-m_n^-1 {σ_n(x) γ_n(x) }                                    ρ_n≤ c n^-δ/2,;                                              r_n:                                          c n^-δ/2                                                  ;                                              ξ_n:                       ξ_n(x)=6x^m σ_n-2m(x)γ_n(x)                                                   ]
    Partition the interval [-1,1] into
    I{ x : |x| ≥ 1-0.5 n^- ϵ_n} and I^c  [-1,1]
    ∖I. Then the constant 6 in the definition of the function ξ_n(x) in (<ref>) is chosen to ensure that, for all n ≫ 1, we have ξ_n(x) ≥σ_n(x) γ_n(x) for all x ∈I such that |x| ≥ 1 - m_n^-1. Since r_n ≥σ_n(x)γ_n(x) for all x such that |x| ≤ 1 - m_n^-1, it follows that 2r_n + ξ_n(x) ≥σ_n(x) γ_n(x) for all n ≫ 1 and x ∈I.
    
    
    Next, let
    f_n,S=f_n,S^L+f_n,S^M+ f_n,S^H where
    
    f_n,S^L(x) ∑_i=0^m_n-1 a_i x^i,     
    f_n,S^M(x) ∑_i=m_n^n-(m_n+1) a_i x^i,     
    f_n,S^H(x) ∑_i ∈ S c_ix^n-i + ∑_i ∈{1, …, m_n}
     i ∉S a_n-i x^n-i.
    
    Similarly, we let g_n,S=g_n,S^L+g_n,S^M+ g_n,S^H, where for each ∙∈{L,M,H} we define g_n,S^∙(x)  x^n-1f_n,S^∙(x^-1).
    
    
    
     §.§ Lower bound
    
    
    We first handle the lower bound in Theorem <ref>, leaving the upper bound to <ref>. With notation as in <ref>, we have the following chain of implications for all n ≫ 1:
    
        f̂_n,S(x) > γ_n(x) , ∀ x ∈   ⟸   f̂_n,S(x) >γ_n(x) , ĝ_n,S(x) > γ_n(x),  ∀  x ∈ [-1,1] 
           ⟸    f_n,S^M(x) > ξ_n(x),  g_n,S^M(x) > ξ_n(x) : ∀ x ∈I,   and
                   f_n,S^M(x) >-r_n,  g_n,S^M(x) >-r_n : ∀  x ∈I^c,  and
                       f_n,S^L(x) >3r_n,   g_n,S^L(x) ≥ -r_n : ∀ x ∈ [-1,1],  and
                           f_n,S^H(x) ≥ -r_n,   g_n,S^H(x) > 3r_n : ∀ x ∈ [-1,1].
    
    Since the polynomial pairs (f_n,S^L,g_n,S^L), (f_n,S^M,g_n,S^M) and
    (f_n,S^H,g_n,S^H) are mutually independent, 
        P_n,S,γ_n =
        ( f̂_n,S(x) >γ_n(x), ∀ x ∈) ≥
             (
         {f_n,S^M (x) >ξ_n(x),   g_n,S^M(x) >ξ_n(x),
         ∀ x ∈I}∩{f_n,S^M(x) >-r_n,   g_n,S^M(x) > -r_n,  ∀  x ∈I^c}) ×
                 ( f_n,S^L(x) >3r_n,   g_n,S^L(x) ≥ -r_n , ∀ x ∈ [-1,1] ) ×( f_n,S^H(x) ≥ -r_n,   g_n,S^H(x) > 3r_n , ∀ x ∈ [-1,1] ).
    
    Call the three factors in (<ref>)Q_1, Q_2, and Q_3, respectively. The factor Q_1 was estimated in <cit.> using the strong approximation results (<ref>) and (<ref>) in the case S = ∅, and a lower bound of 
    
        Q_1 ≥ n^-b+o(1)
    
    was obtained. The factor Q_2 was also estimated in <cit.>, where a lower bound of 
    
        Q_2 ≥ n^o(1)
    
    was obtained. (To be clear, in loc. cit., the probabilities Q_i are expressed as Q_1 = Q_1 - 2Q_2 and Q_2 = Q_3 - Q_4, where each Q_i is a certain probability, and they bound the Q_i by controlling each of the Q_i separately.)
    
    As for bounding Q_3, define the following probabilities:
    
        Q_3'    (g_m_n,S(x) > 3r_n, ∀ x ∈ [-1,1];  and  x^n-m_nf_m_n,S(x) ≥ -r_n, ∀ x ∈±[1-m_n^-1,1]),
        Q_4'    ( x^n-m_n f_m_n,S(x) ≤ -r_n,  x  such that  |x| ≤ 1 - m_n^-1).
    
    Then Q_3 ≥Q_3' - Q_4', so it suffices to determine lower and upper bounds on Q_3' and Q_4', respectively. To bound Q_4', recall that m_n=2 n^3ϵ_n and ϵ_n → 0. It then follows that
    for all n ≫ 1, we have
    
        Q_4' ≤( sup_|x| ≤ 1 - m_n^-1 |x|^n-m_n|f_m_n(x)| ≥ r_n )
        ≤( sup_|x| ≤ 1 - m_n^-1|f_m_n(x)|≥  e^√(n)).
    
    To proceed, we make use of the following lemma (this is <cit.>; see <cit.> for a proof).
    
    Let {T_x : x ∈ [a, b]} be an almost surely continuous
    stochastic process with T_a=0.
    Assume that |T_x-T_y|^2 ≤ K (x-y)^2 for all x, y ∈ [a,b]. 
    Then, we have that
    
        ( sup_x ∈ [a,b] T_x^2 ) ≤ 4 K (b-a)^2.
    
    
    Take T_x=f_m_n,S(x)-f_m_n,S(0) = f_m_n,S(x) - a_0. Then, just as in <cit.>, we have the bound
    
        |T_x-T_y|^2 = |f_m_n,S(x) - f_m_n,S(y)|^2 ≤ n^3(x-y)^2.
    
    Using (<ref>) and applying Lemma <ref> two times, once with a=0, b = 1 - m_n^-1 and once with a = -1 + m_n^-1, b = 0, we find that
    
        ( sup_|x| ≤ 1 - m_n^-1 T_x^2 ) ≤ 8 n^3 (1 - m_n^-1)^2.
    
    Upon combining (<ref>) with (<ref>) and applying Markov's inequality multiple times, it follows that for all n ≫ 1 we have
    
        Q_4' ≤(|a_0| ≥ e^√(n)) + (sup_|x| ≤ 1 - m_n^-1 T_x^2 ≥ e^2√(n)) ≪ e^-√(n)
         + 8n^3 (1 - m_n^-1)^2e^-2√(n)≪ e^-n^1/3.
    
    
    We now turn our attention to bounding Q_3'. For this, we prove the next lemma, from which one readily deduces that
    
        Q_3' ≫ n^-O(ϵ_n),
    
    where the implied constants are fixed.
    
    There exists c<∞ such that for all m=2^κ+1, where κ∈ℕ is sufficiently large, we have
    ( g_m,S(x) > m^-2, ∀ x ∈ [-1,1];   and  
    x f_m,S(x) ≥ 0, ∀ x ∈± [1-2^-κ,1] )
    ≥ m^-c.
    
        The statement and proof of Lemma <ref> draw heavy inspiration from <cit.>, except that the roles of f and g are reversed. This distinction matters not in loc. cit. but is of particular importance in the present article, where we use the niceness condition to prove the lemma.
        
    Define the intervals
    J_j{ x : 1-2^-j≤ |x| ≤ 1-2^-j-1} for j ∈{1,…,κ-1}
    and J_κ={ x : 1-2^-κ≤ |x| ≤ 1 }. Let 1 ≪ s ≤κ, and further define J_0 { x : |x| ≤ 1-2^-s}. We will decompose f_m,S and g_m,S into sums over
    κ-s+2
    terms involving polynomials f^j and g^j of smaller degree, where j ∈{0,s,s+1,…,κ}.
    Specifically, we
    write
    
        f_m,S(x) =x^m-2^s f^0 (x) + ∑_j = s^κ  x^m-2^j+1  f^j(x)   and   g_m,S(x) =g^0 (x) + ∑_j=s^κ x^2^j g^j(x),
    
    where the f^j and g^j are completely determined by the conditions f^0 = 2^s-1 =  g^0 and f^j = 2^j - 1 =  g^j for each j ∈{s, …, κ}.
    
    For some sufficiently large Γ_0 > 0 that does not depend on κ, we have
    
        2^j/2 (Γ_0-1) x^2^j -
        ∑_i=s 
         i ≠ j^κ 2^i/2 x^2^i≥ 0  ,     ∀ x ∈J_j,    j ∈{s,…,κ}.
    
    Moreover, since (a_0)=0 and (a_0^2)=1, there exist real numbers α > β > 0 such that (|a_0-α| ≤β')>0 for every β' ∈ (0,β). Fixing such an α, let M ∈ℕ be an integer to be chosen later, and take s ≫ 1 to be sufficiently large, so that
    
        ∑_i=s^∞ 2^i/2 x^2^i≤α/2M ,     ∀ x ∈J_0.
    
    Note that such an s always exists because, for every x ∈J_0, the sum on the left-hand side of (<ref>) converges.
    
    
    The sets J_0,J_s,J_s+1,
    …,J_κ form a partition of the interval [-1,1]. One checks that for κ large enough,
    we have
    
        m^-2≤min{α/2M,inf_x ∈J_j, 
         j ∈{s,…,κ}  2^j/2 x^2^j}
    
    Combining (<ref>) with (<ref>), we deduce that
    
        { g_m,S(x) > m^-2, ∀ x ∈ [-1,1] }   ⊃⋂_j=s^κ{ g^j(x) > 2^j/2Γ_0 , ∀ x ∈J_j;  and  g^j(x) ≥ -2^j/2, ∀ x ∈J^c_j }
                     ∩{ g^0(x) > α/M, ∀  x ∈J_0;  and 
         g^0(x) ≥ 0, ∀ x ∈J^c_0 }
    
    Note that for all x ∈ [-1,1], we have
    { x f_m,S(x) ≥ 0 }⊃{ x f^0(x) ≥ -2^κ/2}∩⋂_j=s^κ{ x f^j(x) ≥ 2^j/2Γ_0 }.
    
    
    The polynomial pairs (f^j,g^j) for j ∈{0,s,…,κ} are mutually
    independent of each other, with the pair (f^j,g^j) obeying
    the same law as that of (f_2^j,g_2^j) for each j ≠ 0. Consequently, combining (<ref>) and (<ref>) yields that
    
        ℙ( g_m,S(x) > m^-2, ∀ x ∈ [-1,1];  and 
        x f_m,S(x) ≥ 0, ∀ x ∈J_κ) ≥η_s,κ×∏_j = s^κ q_j,
    
    where the factors η_s,κ and q_j are defined as follows:
    
        η_s,κ   ℙ( g_2^s,S(x) > α/M, ∀ x ∈J_0;  and 
         g_2^s,S(x) ≥ 0, ∀ x ∈J^c_0;  and 
         x f_2^s,S(x) ≥ -2^κ/2, ∀ x ∈J_κ) 
        
        q_j    ℙ( f_2^j (x) > Γ_0 2^j/2, ∀ x ∈J_j;  and 
         f_2^j(x) ≥ -2^j/2, ∀  x ∈J^c_j;  and 
         x g_2^j(x) ≥Γ_0 2^j/2, ∀ x ∈J_κ)
    
    That q_j is uniformly bounded away from zero in κ, independently of j, was established in <cit.>— indeed, note that q_j arises from the pieces of the random polynomials f_m,S and g_m,S that do not involve the fixed coefficients c_i for i ∈ S. It remains to show that η_s,κ is uniformly bounded away from zero in κ, for all sufficiently large κ. By our assumption that the coefficient data is nice, there exists an even integer s' > k, a set of values {v_i : i ∈{0,…, s'-1}∖ S}⊂, and a small constant β > 0 such that (|a_i - v_i| ≤β) > 0 for each i ∈{0,…, s'-1} and such that whenever v_i' ∈ [v_i - β, v_i + β] for every i ∈{0, …, s'-1}∖ S, we have 
    
        ∑_i ∈ S c_i x^i-1 + ∑_i ∈{0, …, s'-1}
         i ∉S v_i' x^i > 0,  ∀ x ∈ (-1,1).
    
    Indeed, the niceness assumption guarantees that the left-hand side of (<ref>) is nonzero for all x ∈ (-1,1) and v_i' ∈ [v_i - β, v_i + β], and so the fact that c_1 > 0 ensures that it is actually positive. For any ℓ > s'/2, consider the sum of terms
    
        v_s'' x^s' + v_s'+1'x^s'+1 + ⋯ + v_2ℓ'x^2ℓ + v_2ℓ+1' x^2ℓ+1.
    
    If we restrict the coefficients in (<ref>) to satisfy 
    
        α + β≥ v_2i' ≥ v_2i+1' ≥α - β,   for every i ∈{s'/2,…,ℓ},
    
    then the sum in (<ref>) is nonnegative for all x ∈ [-1,1]. Now, choose s so that 2^s > s', and take ℓ = 2^s-1-1. We claim that, if the coefficients v_i' satisfy v_i' ∈ [v_i - β, v_i + β] for every i ∈{0, …, s'-1}∖ S along with (<ref>), then we have
    
        ∑_i ∈ S c_i x^i-1 + ∑_i ∈{0, …, 2^s-1}
         i ∉S v_i' x^i > α/M,  ∀ x ∈ [-1 + 2^-s, 1 - 2^-s]
    
    for sufficiently small β and large M. Indeed, there exists some ξ∈ (0,1-2^-s) such that the left-hand side of (<ref>) is at least c_1/2 for all x such that |x| ≤ξ. Then for all x such that ξ≤ |x| ≤ 1 - 2^-s, we have that
    
        ∑_i = s'^2^s-1α x^i = x^s'×∑_i = 0^2^s - s' - 1α x^i  ≥ξ^s'/4×α.
    
    Note that the quantities c_0/2 and ξ^s'/4 are fixed. Thus, if we take β to be sufficiently small, then the sum on the left-hand side of (<ref>) is bounded away from zero by some fraction of α, proving the claim. Finally, with the coefficients v_i' chosen as above and for β sufficiently small, we also have that
    
        |xf_2^s(x)| = |∑_i ∈ S c_i x^2^s-i + ∑_i ∈{0, …, 2^s-1}
         i ∉S v_i' x^2^s-1-i| > 2^sC ×α,  ∀ x ∈J_k,
    
    where C > 0 depends on the coefficients c_i,  v_i as well as on β, β. Taking κ to be so large that 2^κ/2 > 2^sC ×α, we conclude that η_s,κ is uniformly bounded away from zero in κ.
    
    It remains to explain how the proof of the lemma adapts to the setting of Theorem <ref>. Because of our assumption that k(n) = n^o(1/√(log n)), the only aspects of the proof that change are the choice of s = s(n), which must be taken so that 2^s(n) k(n), as well as the estimation of the factor η_s(n),κ. But because the subleading fixed coefficients c_2, …, c_k(n) are all equal to zero, it is easy to see that the coefficient data are nice, in the sense that a statement analogous to (<ref>) holds. The rest of the proof is the same.
    
    
    Combining the bounds on Q_3' and Q_4' obtained in (<ref>) and (<ref>), respectively, we deduce that
    
        Q_3 ≥Q_3' - Q_4' ≥ n^-o(1).
    
    The lower bound P_n,S,γ_n≥ n^-b+o(1)
    in Theorem <ref>, as well as the lower bound P_n,S_n≥ n^-b + o(1) in Theorem <ref>,
    then follows by substituting the bounds (<ref>), (<ref>), and (<ref>) on the factors Q_1, Q_2, and Q_3 into the right-hand side of (<ref>).
    
    
    
     §.§ Upper bound
    
    
    We finish by handling the upper bound in
    Theorem <ref>. Let η_n inf{γ_n(x) : ||x|-1|≤ n^-ϵ_n}, and recall that our assumptions imply that η_n → 0. Then, by applying the strong approximation results (<ref>) and (<ref>) with m = n, t = n^ϵ_n/4, and p = p_n, we deduce that
    
        P_n,S,γ_n   =
        ( f̂_n,S(x) >γ_n(x),  ∀ x ∈) ≤(
        f̂_n,S(x) >η_n  and ĝ_n,S(x) >η_n,  ∀ x ∈I)  
                   ≤( f̂^b_n,S(x) > η_n - n^-ϵ_n/4 and ĝ_n,S^b(x) >η_n  -n^-ϵ_n/4,
         ∀ x ∈I) + 2 n^-3≤ n^-b+o(1)
    
    for all n ≫ 1. The second-to-last inequality follows because inf_x ∈I{σ_n,S(x),σ_n,S(x)}≥ n^ϵ_n/2 for all n ≫ 1; the last inequality follows by an application of Theorem <ref>, taking the threshold to be η_n-n^-ϵ_n/4 when x ∈I∪I^-1
    and -∞ for all other x. This completes the proof of Theorem <ref>.
    
    
    
    
    
    
    
    § PROOF OF THEOREM <REF> AND <REF>
    
    
    The purpose of this section is to prove Theorems <ref> and <ref> (and hence also Theorem <ref> and Corollary <ref>). The arguments given in this section are logically independent of the previous two sections, so in particular, we obtain a second proof of Theorem <ref>. We retain notation (n, k, S, and j) as in the setting of the theorem.
    
    
    
     §.§ Lower bound
    
    
    
    To obtain the lower bound, we split into cases according to the parity of n,j. In <ref>, we treat the case where n-1,j are even, and in <ref>, we handle the case where n-1,j are odd. 
    
    
    
      §.§.§ The case where n-1,j are even
    
    
    Let n-1,j be even. Note that by the assumptions of the theorem, the support of the distribution of the random coefficients intersects both intervals (-∞, 0) and (0, ∞). Further, there exists a sequence (p_n)_n with lim_n →∞ p_n = ∞ and (|a_0|^p_n) ≤ n. Set ρ_n max{5p_n^-1, (log n)^-1/2}; note that the definitions of p_n and ρ_n are not the same as in <ref>. 
    Let M ≫ 1 be such that ℙ(|a_i| < M) > 0. Define the set 
    
        𝒱{v ∈ : ℙ(|a_i-v|<ϵ) > 0, ∀ϵ > 0}⊆,
     and observe that 𝒱≠∅. We begin with the following result, a somewhat weaker version of which is claimed and proven in <cit.>. 
    
    There exist a constant C_j(depending only on j and the law of the a_i), a small enough constant ϵ > 0, a constant B > 0, choices of even m = m(n) ∼ C_j ρ_n log n, and a polynomial B(x) = ∑_i = 0^m - 1 b_i x^i, with | b_i |≤ B and b_i ∈𝒱, such that the following holds. Suppose g(x) = ∑_i = 0^n - 1 g_i x^i is any polynomial satisfying the following four properties: 
    
    H1:    | g_i - b_i | < ϵ for i ∈{0, 1, … , m - 1}
    H2:    | g_n - 1 - i|≤ M for i ∈{0, 1, … , m - 1}
    H3:    g_m + g_m + 1 x + ⋯ + g_n - m - 1 x^n - 2m - 1 > n^-1/4σ_n - 2m(x) for all x ∈
    H4:    | g_i | < (n-1)^ρ_n-1 for i ∈{0, 1, … , n - 1}.
    
    Then g(x) has exactly j zeros in [0, 1], all of them simple, and is positive on [-1, 0].
    
    This is proved as Step 1 and Step 2 of Lemma 8.2 in DPSZ. Our property H2 replaces the stronger property A2 in DPSZ, but one sees readily in their proofs of Step 1 and Step 2 that in each of the two occurrences where A2 is invoked, only the estimate 
    
        | g_n - 1 x^n - 1 + ... + g_n - m x^n - m|≤ m M | x^n - m|
    
    on | x |≤ 1 is necessary. This estimate follows immediately from H2. 
    We now show that with large enough probability, f_n, S satisfies simultaneously H1, H2, H3, and H4, which we may call satisfying H. The proof is essentially the same as the proof of Lemma 8.1 in DPSZ, but it is nonetheless short and instructive.  
    
    Take M > max_i ∈ S |c_i|. The probability that f_n, S satisfies 𝐇 is at least n^-b + o(1). 
    
    It is easy to see that, because j = o(log n), we have (𝐇1) ≥ n^o(1) and (𝐇2) ≥ n^o(1). By <cit.> (i.e., the analogue of our Theorem <ref> for fully random polynomials), we have that (H3) ≥ n^-b + o(1). Because H1, H2, and H3 are independent, the probability that they occur together is at least n^-b + o(1). As for H4 note that by Markov's inequality, we have for each i that 
        (|a_i| ≥ (n-1)^ρ_n-1) = ( |a_i|^p_n-1≥ n^p_n-1ρ_n-1) ≪ n^-5,
     so H4 fails with probability O(n^-3). Using the fact that (𝐇) ≥(𝐇1, 𝐇2, 𝐇3) - (not 𝐇4), together with the fact that b < 3, the desired lower bound follows.
    
    
    Now, let
    𝐇' be the condition on g(x) = ∑_i = 0^n - 1 g_i x^i that g_n - i = c_i for each i ∈ S, that
    H also holds, and further that
    
        x^m σ_n - 2m(x)/n^1/4 - ∑_i = 0^m - 1 (B + ϵ) | x |^i + ∑_i ∈ S c_i x^n - i + 
        ∑_i ∈{1, … , m}
         i ∉S g_n - i x^n - i
         > 0, ∀ x  such that | x |≥ 1.
    
    Observe that the condition 𝐇' may be obtained from the condition 𝐇 by keeping 𝐇1, 𝐇3, and 𝐇4 intact and by replacing 𝐇2 with the stronger condition that |g_n-1-i| ≤ M for i ∈{0,…,m-1} and (<ref>) holds.
    
    Suppose g(x) = ∑_i = 0^n - 1 g_i x^i satisfies 𝐇'. Then g(x) has exactly j real zeros, all of them simple. 
    
    It only remains to be shown that if 𝐇' holds, then g(x) has no real zeros with | x |≥ 1, which holds by combining (<ref>), H1, and H3.
    
    The probability that f_n, S satisfies 𝐇' is at least n^-b + o(1).
    
    By the proof of Lemma <ref>, it suffices to show that f_n, S satisfies (<ref>) with probability at least n^o(1). For | x |≥ 1, we have σ_n - 2m(x) ≥ (n - 2m)^1/2. Consequently, for all n ≫ 1, we have
    
        x^m n^-1/4σ_n - 2m(x) - ∑_i = 0^m - 1 (B + ϵ) | x |^i > 0
    
    for all x such that | x |≥ 1. It now suffices to prove that 
    
        ∑_i ∈ S c_i x^m - i + 
        
        ∑_i ∈{1, ... , m}
         i ∉S a_m - i x^m - i≠ 0
    
    for x such that |x| > 1 with probability at least n^o(1), but this follows from the niceness condition, just as in the proof of Lemma <ref>.
    
     In the context of Theorem <ref>, it is also clear that if k = k(n) grows as slowly as o(log n) that the above estimates continue to hold — Lemma <ref> needs to be modified to permit fixing more than m coefficients at the top of the polynomial, but this is possible because the behavior of the polynomial on [-1,1] is determined almost entirely by the last m coefficients.
    
    
    
      §.§.§ The case where n-1,j are odd
    
    
    Let n-1,j be odd. Recall that in <ref>, our idea was to adapt the proof given in <cit.> to work in our setting. This was possible because the proof in loc. cit. involves choosing very tiny ranges for the low-degree coefficients and only requires that the high-degree coefficients be bounded. But when n-1,j are odd, the proof given in <cit.> does not similarly adapt to our setting: their argument involves choosing tiny ranges for both the low- and high-degree coefficients of the polynomial, which prevents us from fixing the high-degree coefficients to have the desired values c_i. Thus, to handle the case where n-1,j are odd, we must prove a new analogue of Lemma <ref> that allows us to control the number of zeros using only the low-degree coefficients.
    
    Since the a_i are of zero mean and unit variance, there exist β < 0 < α such that α,β∈V. We may assume without loss of generality that α > -β. Let s ≥ 4 be an even integer such that α + (s-1)β < 0, and define polynomials
    
        Q(x)  -β x^s-1 - ∑_i = 0^s-2α x^i,     R(x) = -α - ∑_i = 1^s-1β x^i.
    
    Note that by construction we have Q(x) < 0 for all x such that |x| ≤ 1 and R(1) > 0 > R(-1). 
    
    Let δ > 0 be sufficiently small, let r = r(δ) be sufficiently large, and let ϵ = ϵ(r,δ) be sufficiently small; we will choose the values of these quantities, all of which are independent of n, later. Let r_i denote the multiple of s nearest to r^i, for each i ∈{1,…, j}. Let m = m(n) be the multiple of s nearest to 2r_kρ_n log n/|log(1-δ)|. Define the polynomial
    
        B(x) = ∑_i = 0^m b_ix^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_j-1 + x^r_j-1+s + ⋯ + x^r_j-s)Q(x) + (x^r_j + x^r_j + s + ⋯ + x^m -s)R(x) + α x^m.
    
    Then we have the following lemma (which also applies in the setting of <cit.> and gives a different proof of their result for fully random polynomials):
    
    For suitable choices of δ, r, and ϵ, suppose that g(x) = ∑_i = 0^n - 1 g_i x^i is any polynomial satisfying the following four properties: 
    
    K1:    | g_i - b_i | < ϵ for i ∈{0, 1, … , m}
    K2:    | g_n - 1 - i|≤ M for i ∈{0, 1, … , m - 1}
    K3:    g_m+1 + g_m + 2 x + ⋯ + g_n - m - 1 x^n - 2m - 2 > n^-1/4σ_n - 2m-2(x) for all x ∈
    K4:    | g_i | < (n-1)^ρ_n-1 for i ∈{0, 1, … , n - 1}.
    
    Then g(x) has exactly j zeros in [0, 1], all of them simple, and is negative on [-1, 0].
    
        The proof of the lemma follows the argument given in <cit.> for the proof of Lemma <ref>, and it is likewise divided into three steps. The first step is to prove that g has the desired behavior on [0,1]; the second step is to do the same for [-1,0]; and the third step is to prove the same for ∖ [-1,1]. The third step is entirely identical to that of the proof of Lemma <ref>, so we omit it and focus on the first two steps.
    
        Step 1. The zeros of g(x) in (0,1) are the same as those of F(x)  (1 - x^s)g(x), so it suffices to prove the following conditions, which ensure that g(x) has exactly j zeros on [0,1]:
        
      * 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_3]
    ⋮
      * F'(x) > 0 for x ∈ [δ^1/r_j,(1-δ)^1/r_j]
      * F(x) > 0 for x ∈ [(1-δ)^1/r_j,2^-1/m]
      * g(x) > 0 for x ∈ [2^-1/m,1]
        To proceed, first note that for all x such that |x| ≤ (1-δ)^1/r_k, the polynomial F is approximated very well by the polynomial (1-x^s)B(x). Indeed, by conditions 𝐊1 and 𝐊4, we have the following bound for all x such that |x| ≤ (1-δ)^1/r_k and all n ≫ 1:
        
        |F(x) - (1-x^s)B(x)|    ≤ (1-x^s) (ϵ(1 + |x| + ⋯ + |x|^m-1) + n^ρ_n(|x|^m+1 + ⋯ + |x|^n) 
           ≤ (1-|x|)^-1(ϵ + n^ρ_nx^m+1) ≪ϵ,
    
        where the implied constant depends on r and δ. We are thus led to consider the polynomial (1-x^s)B(x), which can be expanded as follows:
        
        (1-x^s)B(x) = Q(x) + (∑_ℓ = 1^j(-1)^ℓ(Q(x) - R(x))x^r_ℓ) - R(x)x^m + α x^m(1-x^s).
    
        We start by verifying that the signs of F(x) are correct on the relevant intervals. Fix N such that sup_x ∈ [0,1]max{|Q(x)|,|R(x)|}≤ N, and take x ∈ [0,δ^1/r_1]. Then the factors x^r_ℓ, x^m, and x^m-s occurring in (<ref>) are all at most δ in size, so we have
        
        (1-x^s)B(x) ≤ Q(x) + (2j+3)Nδ.
    
    Thus, for all sufficiently small δ, the negativity of Q(x) on [0,1] implies in conjunction with (<ref>) that (1-x^s)B(x) is negative and bounded away from zero for all x ∈ [0,δ^1/r_1]. Using (<ref>), for all sufficiently small ϵ we conclude that F(x) is negative on this interval.
    
    Next, take x ∈ [(1-δ)^1/r_i,δ^1/r_i+1] for some i ∈{1,…, j-1}, and note that we have x^m ≤ x^r_ℓ≤δ for all ℓ > i and x^r_ℓ∈ [1-δ,1] for all ℓ≤ i. Observe that we have the identity
    
        Q(x) + ∑_ℓ = 1^i(-1)^ℓ(Q(x) - R(x)) = QR(x)  Q(x),    if i is even,
         R(x),    if i is odd.
    
    Combining (<ref>) with (<ref>), it follows that for all x ∈ [(1-δ)^1/r_i,δ^1/r_i+1]  we have
    
        |(1-x^s)B(x) - QR(x)| ≤ (2j+3)Nδ.
    
    Thus, for all sufficiently small δ, the polynomial (1-x^s)B(x) is as close as we like to QR(x), which is negative if i is even, and which is positive if i is odd and r is sufficiently large. That we have the desired behavior on this interval of x then follows from (<ref>) by taking ϵ to be sufficiently small.
    
    Next, take x ∈ [(1-δ)^1/r_j,2^-1/m]— note that on this interval, the bound (<ref>) no longer applies, but it follows from conditions 𝐊1, 𝐊2, and 𝐊3 that for all n ≫ 1,
    
        F(x) - (1-x^s)B(x) ≥ -(1-x^s)(ϵ(1 + |x| + ⋯ + |x|^m) + mM|x|^n-m) ≫ -ϵ,
    
    where the implied constant is positive and depends on r and δ.
    Then, from (<ref>) and (<ref>), taking i = j, we deduce that
    
        (1-x^s)B(x) ≥1/2R(x) - 2jNδ.
    
    Thus, for all sufficiently small δ, the polynomial (1-x^s)B(x) is bounded away from zero, and the desired behavior on this interval of x then follows from (<ref>) by taking ϵ to be sufficiently small.
    
        Next, take x ∈ [2^-1/m,δ^1/n]. Applying conditions 𝐊1, 𝐊2, and 𝐊3 to control the three ranges of terms in the polynomial g yields the following lower bound:
        
        g(x)    ≥ B(x) - ϵ (1 + ⋯ + |x|^m) - mMx^n-m≥ (x^r_j + x^r_j + s + ⋯ + x^m-s)R(x) - r_jN - ϵ m - mMδ^1/2
           ≥(m-r_j/2s)R(x) - r_jN - ϵ m - mMδ^1/2
    
        Since m = m(n) →∞ as n →∞, and since R(1) > 0, we see the bound in (<ref>) is positive for all n ≫ 1 so long as δ and ϵ are sufficiently small.
    
        Next, take x ∈ [δ^1/n,1]. In this range, conditions 𝐊1, 𝐊2, and 𝐊3 imply that the terms g_m+1x^m+1 + ⋯ + g_n-m-1x^n-m-1 dominate, contributing at least n^1/8 as n →∞. The other terms contribute ≪ m = o(log n) on this range, giving the desired positivity.
    
        
    
        We now move on to verifying that the signs of F'(x) are correct on the relevant intervals. We note that for all x ∈ [0,(1-δ)^1/r_j], the derivative F'(x) is approximated very well by the derivative of (1-x^s)B(x). Indeed, by conditions 𝐊1 and 𝐊4, we have the following bound for all x ∈ [0,(1-δ)^1/r_j] and all n ≫ 1:
        
        |F'(x) - d/dx((1-x^s)B(x))|    ≤ sx^s-1(ϵ(1 + ⋯ + x^m) + n^ρ_n(x^m+1 + ⋯ + x^n)) + 
                  (1-x^s)(ϵ(1 + 2x + ⋯ + mx^m-1) + n^ρ_n((m+1)x^m + ⋯ + nx^n-1)) 
           ≤ s(1-x)^-1(ϵ + n^ρ_nx^m+1) + (1-x)^-2(ϵ + n^ρ_n(m+1)x^m) ≪ϵ,
    
        where the implied constant depends on r and δ. By differentiating (<ref>), we obtain the identity
        
        d/dx((1-x^s)B(x)) = Q'(x) + ∑_ℓ = 1^j (-1)^ℓ((Q'(x) - R'(x))x^r_ℓ + (Q(x)-R(x))r_ℓ x^r_ℓ - 1) - o(1).
    
        Even though our choice of the polynomial B is different from the choice made in <cit.>, and we chose Q and R to be the negatives of the choices made in loc. cit., the identity (<ref>) takes the exact same shape in both settings, and thus their analysis applies with minimal change. In particular, their argument shows that the term (-1)^i(Q(x) - R(x))r_ix^r_i-1 dominates the right-hand side of (<ref>) on the interval [δ^1/r_i,(1-δ)^1/r_i], and the desired behavior then follows from the fact that Q(x) - R(x) is negative and bounded away from zero on the interval [δ^1/r_1,1], so long as r is sufficiently large. 
        
        Step 2. The analysis here is similar to that of Step 1, except that both Q(x) and R(x) are negative when x is close to -1, as is the middle range of terms g_m+1x^m+1 + ⋯ + g_n-m-1x^n-2m-2. For the sake of brevity, we just highlight two important places in which the proof in Step 1 needs to be modified here. Firstly, in (<ref>), the contribution of α x^m(1-x^s) cannot be ignored, but we observe that this term is ≪δ on the interval [-2^-1/m,-(1-δ)^1/r_j], so it is negligible as long as δ is sufficiently small. Secondly, we are no longer interested in studying the sign of the derivative F'(x); rather, we must show that F(x) < 0 on the intervals [-(1-δ)^1/r_i,-δ^1/r_i]. To do this, it suffices by (<ref>) (taking ϵ to be sufficiently small) to prove that (1-x^s)B(x) is negative and bounded away from zero on [-(1-δ)^1/r_i,-δ^1/r_i]. Combining (<ref>) and (<ref>), we see that for all x ∈ [-(1-δ)^1/r_i,-δ^1/r_i],
        
        |(1-x^s)B(x) - t_i(x)Q(x) - (1-t_i(x))R(x)| ≤ (2j+1)Nδ,
    
        where t_i(x) = 1 - x^r_i if i is even and t_i(x) = x^r_i if i is odd. Thus, if δ is sufficiently small, it suffices to see that t_i(x)Q(x) + (1-t_i(x))R(x) is negative and bounded away from zero, but this is true for all sufficiently large r because then both Q(x) and R(x) are negative and bounded away from zero.
    
    
    The lower bound in Theorem <ref> in the case where n-1,j are odd now follows from Lemma <ref> in exactly the same way as the case where n-1,j are even follows from Lemma <ref>. In the context of Theorem <ref>, it is also clear that if k = k(n) grows as slowly as o(log n) that the above estimates continue to hold — Lemma <ref> needs to be modified to permit fixing more than m coefficients at the top of the polynomial, but this is possible because the behavior of the polynomial on [-1,1] is determined almost entirely by B(x).
    
    
    
     §.§ Upper bound
     Fix δ∈ (0, 1/2), and let V be as defined in (<ref>). Then restricting x to lie in V, we have that 
    
        P_n, j≤(#{x ∈: f_n,S(x) = 0}≤ j) ≤(#{x ∈ V: f_n,S(x) = 0}≤ j).
    
    Consider the range T = [δlog n, (1 - δ) log n], chosen so that setting x = w_1(t) = 1 - e^-t for t ∈ T traces out the interval I_1  [1 - n^-δ, 1 - n^-(1 - δ)], while x = w_2(t) = w_1(t)^-1, x = w_3(t) = -w_1(t)^-1, and x = w_4(t) = -w_1(t) trace out the remaining closed intervals I_2, I_3, and I_4 that constitute V.
    Divide T into R ⌊ (1 - 2 δ) log n ⌋ unit-length intervals — the last one slightly longer if necessary — with images J_(i - 1) R + 1, ... , J_iR in I_i under w_i. If f_n,S indeed has at most j zeros in V, then there is at least one way of choosing j intervals J_i_1, ... , J_i_j to ignore, so that f_n,S has constant sign on each of the ℓ≤ j + 4 maximal leftover intervals comprising V ∖(J_i_1∪⋯∪ J_i_j). Number these maximal leftover intervals L_1, ... , L_ℓ. A quick calculation reveals that, because j = o(log n/loglog n), there are n^o(1) choices of (i_1, ... , i_j) and n^o(1) choices of (s_i)_i ∈{± 1}^ℓ for the signs of f_n,S on the L_i. Thus, it suffices to obtain an upper bound on the quantity
    
        (min_1 ≤ i ≤ℓinf_x ∈ L_i s_i f_n,S(x) >  0 )
    
    for each choice of intervals J_i_1,…,J_i_j to ignore and each choice of signs (s_i)_i ∈{± 1}^ℓ.
    
    To estimate (<ref>), we split off the first ≈ k terms of f_n,S, leaving behind a fully random polynomial to which we can apply the results of <cit.>. More precisely, let r be the smallest even integer such that r ≥ k. 
    Then we write
    
        f_n,S(x) = σ_n - r(x) f̂_n - r(x) + ∑_i ∈ S 
        c_i x^n - i + ∑_i ∈{1, … , r}
         i ∉S a_n-i x^n - i.
    
    For s_if_n,S(x) to be positive, s_iσ_n-rf̂_n-r(x) must be at least as large as the negative of the sum of the remaining terms on the right-hand side (<ref>). To bound these remaining terms from above, observe that there exists a constant ξ > 0 such that for all x ∈ V, i ∈{1, …, r}, and n ≫ 1, we have 
    
        |x^n-i| ≤ξ× n^-δ/2σ_n - r(x).
     Applying the bound in (<ref>) to the terms of degree n-i where i ∈ S, we find for all n ≫ 1 that
    
        (min_1 ≤ i ≤ℓinf_x ∈ L_i s_i f_n,S(x) >  0 ) ≤(min_1 ≤ i ≤ℓinf_x ∈ L_i s_i f̂_n - r(x) > - r ξ n^-δ/4)
        +
        ∑_i ∈{1, … , r}
         i ∉S(|a_i| ≥ n^δ/4).
    
    Note that the summation on the right-hand side of (<ref>) is O(n^-3)— indeed, it is O(n^-a) for every a > 0, because the coefficient law has finite moments of all orders. As for the first term on the right-hand side of (<ref>), this is shown in <cit.> to be bounded by n^-(1-2δ)b + o(1). Taking the limit as δ→ 0 yields the desired upper bound. It is also clear that if k = k(n) (and hence r) grows as slowly as o(log n) that the above estimates continue to hold.
    
    
    
    
    § ACKNOWLEDGMENTS
      
     We thank Kumar Murty, Bjorn Poonen, Qi-Man Shao, and Melanie Matchett Wood for helpful conversations. AS was supported by the National Science Foundation, under the Graduate Research Fellowship, as well as Award No. 2202839. 
    
    alpha
