# Universality of the minimum modulus for
random trigonometric polynomials

Nicholas A. Cook  Hoi H. Nguyen The second author is supported by NSF CAREER
grant DMS-1752345.

(
$\limsup_{n\to\infty}{\mathbf{P}}\Big{(}\,\min_{|z|=1}|F_{n}(z)|\leq\varepsilon
n^{-1/2}\,\Big{)}\leq C\varepsilon$ (1.3) for a universal constant
$C<\infty$.; unit variance at each fixed $x$. Up to a factor of unit modulus,
which does not affect our results, $P_{n}$ is the restriction of the Kac
polynomial $(2n+1)^{-1/2}F_{2n}(z)$ to the unit circle (all of our arguments
extend to the case of odd degree).; ,; For the interested reader, we note that
a new proof of Liggett’s general result in a special case sufficient for this
application was recently obtained in [CGS].; $|J|\times(4m)$;

######  Theorem 3.2.

Let $\boldsymbol{t}=(t_{1},\dots,t_{m})$ be $n^{\kappa}$-smooth and $1$-spread
for some ${\kappa}>0$. Fix $K>0$ and let $Q\subset{\mathbb{R}}^{4k}$ be a box
(cartesian product of intervals) with side lengths at least $n^{-K}$. Then

$\Big{|}{\mathbf{P}}\Big{(}\frac{1}{\sqrt{2n+1}}S_{n}(\boldsymbol{t})\in
Q\Big{)}-{\mathbf{P}}\big{(}\Gamma_{n}(\boldsymbol{t})\in Q\big{)}\Big{|}\ll
n^{-1/2}|Q|$

where $|Q|$ is the volume of $Q$, and the implied constant depends only on
$m,{\kappa},K$, and the sub-Gaussian constant for $\xi$.

; supw∈R4m; (recall the rescaled polynomial $\widetilde{P}_{n}$ from (2.5));
~P; ~P; The proof below can be read as a warmup to the more technical proof of
Theorem 3.1, where a similar (but more complicated) differencing strategy is
used.;

######  Remark 3.8.

We point out that if $\lambda$ is growing with $n$, it is not hard to show by
computations similar to [KS99, Lemma 3.2] that
$\frac{1}{|J|}W_{J}(\boldsymbol{t})^{\mathsf{T}}W_{J}(\boldsymbol{t})$
asymptotically splits into $m$ well-conditioned blocks. However, when
$\lambda$ is bounded or shrinking with $n$ the covariance matrix becomes
increasingly degenerate. We note that [KS99, Lemma 3.2] also contains
estimates for the covariance matrix of the real and imaginary parts of
$P_{n}(t)$ at a single point $t$ that is only $n^{-1/2}$-spread. In principle
it should be possible to extend those arguments to the above setting with
$m>1$ and additional columns for $P_{n}^{\prime}$; however, this appears to
involve technical case analysis, and in the end we do not think it would lead
to a significantly shorter proof than the one given below.

; $W_{J}(\boldsymbol{t})u$; consequence of Esseen’s inequality (see e.g.
[TV06, Lemma 7.17] and its proof); |; |; We are free to assume $K$ is larger
than any fixed constant. By approximating $Q$ with a union of smaller boxes
with disjoint interiors it suffices to establish the claim for boxes of the
form $Q=w+B_{m}(\boldsymbol{\delta})$ with
$B_{m}(\boldsymbol{\delta}):=\prod_{i=1}^{4}[-\delta_{i},\delta_{i}]^{m}\subset{\mathbb{R}}^{4m}$
for arbitrary $\delta_{i}\in[n^{-2K},1]$ for $1\leq i\leq 4$ (assuming $K\geq
1$, say). ; $K_{*}>2K$.; $\delta:=n^{-2K}$.; where we used in the last line
that $\delta_{i}\leq 1$ for each $1\leq i\leq 4$.; Recalling the notation
$M_{\ell}(f)$ from Theorem 8.1, we have
$M_{\ell}(f)\leq\|f\|_{\infty}=O(1/\delta)^{4{m}}$ for any $\ell\geq 0$.;
ftr,ℓ(j))

###### Abstract

It has been shown in [YZ] that the minimum modulus of random trigonometric
polynomials with Gaussian coefficients has a limiting exponential
distribution. We show this is a universal phenomenon. Our approach relates the
joint distribution of small values of the polynomial at a fixed number $m$ of
points on the circle to the distribution of a certain random walk in a
$4m$-dimensional phase space. Under Diophantine approximation conditions on
the angles, we obtain strong small ball estimates and a local central limit
theorem for the distribution of the walk.

title = Universality of the minimum modulus for
random trigonometric polynomials, author = Nicholas A. Cook and Hoi H. Nguyen,
plaintextauthor = Nicholas A. Cook and Hoi H. Nguyen, plaintexttitle =
Universality of the minimum modulus for random trigonometric polynomials,
runningtitle = The minimum modulus for random trigonometric polynomials,
runningauthor = Nicholas A. Cook and Hoi H. Nguyen, copyrightauthor = N. A.
Cook and H. H. Nguyen, keywords = Random trigonometric polynomials,
Universality, Edgeworth expansion, year=2021, number=20, received=5 February
2021, published=6 October 2021, doi=10.19086/da.28985, purplergb0.9,0,0.8

[classification=text]

##  1 Introduction

Consider the Kac polynomial

$F_{n}(z)=\sum_{j=0}^{n}\xi_{j}z^{j}$ (1.1)

for a sequence of iid random variables $\xi_{j}$ (real or complex). The study
of the distribution of zeros of $F_{n}$, and in particular on the number of
real zeros, has a long history: the case that $\xi_{j}\in\\{-1,0,1\\}$ was
considered by Bloch and Polya [BP31] and Littlewood and Offord [LO38, LO43] in
the 1930s, and the Gaussian case by Kac in the 1940s [Kac43, Kac49]. We refer
to [TV15] for an overview of the vast literature inspired by those early
works.

To the best of our knowledge, the question of the size of the minimum modulus
over the unit circle for Kac polynomials was first raised by Littlewood
[Lit66], who considered the case of Rademacher signs $\xi_{j}=\pm 1$.111We
also refer the readers to [BBM+20] for a recent striking result answering
another question of Littlewood. In particular, Littlewood asked whether
$\min_{|z|=1}|F_{n}(z)|=o(1).$222Here and throughout the article asymptotic
notation is with respect to the limit $n\to\infty$; see Section 1.3 for our
notational conventions. This question was answered in the affirmative by
Kashin [Kas87]; a significant improvement was later obtained by Konyagin
[Kon94], who showed

${\mathbf{P}}\Big{(}\,\min_{|z|=1}|F_{n}(z)|\geq
n^{-1/2+\varepsilon}\,\Big{)}\to 0$ (1.2)

as $n\to\infty$, for any $\varepsilon>0$. Subsequently, Konyagin and Schlag
[KS99] showed that for any $\varepsilon>0$, From the above two estimates, it
is thus natural to ask whether $n^{1/2}m(F_{n})$ converges in law, and to
identify the limiting distribution.

This question was recently addressed for the case of Gaussian coefficients by
a beautiful result of Yakir and Zeitouni [YZ], which we now recall. As we
consider the restriction of $F_{n}$ over the unit circle we parametrize
$z=e(x)$, where here and throughout we abbreviate $e(t):=\exp({\sqrt{-1}}t)$.
The work [YZ] considers the normalized trigonometric series

$P_{n}(x)=\frac{1}{\sqrt{2n+1}}\sum_{j=-n}^{n}\xi_{j}e(jx),\qquad
x\in{\mathbb{R}},$ (1.4)

where $\xi_{j}$ are iid copies of a real or complex, centered random variable
$\xi$ of unit variance. Note that $P_{n}$ has been scaled to have We denote

${m}_{n}:=\min_{x\in[-\pi,\pi]}|P_{n}(x)|.$ (1.5)

With our normalization and from (1.2) and (1.3) we expect that ${m}_{n}$ is
typically of order $n^{-1}$. For the case of Gaussian coefficients, in [YZ]
the limiting distribution of $n\cdot m_{n}$ was shown to be exponential:

######  Theorem 1.1 ([YZ]).

Assume that $\xi$ is a standard real or complex Gaussian. Then for any
$\tau>0$,

$\lim_{n\to\infty}{\mathbf{P}}\Big{(}\,{m}_{n}>\frac{\tau}{n}\,\Big{)}=e^{-{\lambda}\tau}$
(1.6)

where ${\lambda}=2\sqrt{\pi/3}$.

As shown in [YZ, Section 5], their argument in fact extends to allow some
distributions with a small Gaussian component – specifically, $\xi$ of the
form

$\xi^{\prime}+\delta X$ (1.7)

with $\delta$ at least of order $n^{-1}\log n$, where $\xi^{\prime}$ and $X$
are independent, $X\sim{\mathcal{N}}_{\mathbb{R}}(0,1)$, and $\xi^{\prime}$ is
an arbitrary random variable satisfying Cramér’s condition. While Cramér’s
condition is weaker than assuming a bounded density, it does not allow
$\xi^{\prime}$ to be discrete.

In the present work we show that the limiting exponential law for ${m}_{n}$ is
universal. Here and in the sequel,
${\mathbf{P}}_{{\mathcal{N}}_{{\mathbb{R}}}(0,1)}$ denotes a probability
measure under which the real variables $\xi$ or
$\xi^{\prime},\xi^{\prime\prime}$ are standard Gaussian.

######  Theorem 1.2 (Main result).

Assume $\xi$ is a centered sub-Gaussian variable of unit variance, which is
either real-valued, or takes the form
$\frac{1}{\sqrt{2}}(\xi^{\prime}+{\sqrt{-1}}\xi^{\prime\prime})$ for iid real
variables $\xi^{\prime},\xi^{\prime\prime}$. Then for any $\tau>0$,

${\mathbf{P}}\Big{(}\,m_{n}>\frac{\tau}{n}\,\Big{)}-{\mathbf{P}}_{{\mathcal{N}}_{\mathbb{R}}(0,1)}\Big{(}\,m_{n}>\frac{\tau}{n}\,\Big{)}\longrightarrow
0$ (1.8)

as $n\to\infty$.

######  Remark 1.3.

In the proof we treat the case (1.4) with real-valued $\xi$ – the complex case
is slightly simpler. The necessary modifications as well as an extension to
another model of random trigonometric series, are given in Section 10.

######  Remark 1.4.

The sub-Gaussianity assumption is mainly for convenience, and one can check
that for our arguments it suffices to assume $\xi$ has a finite moment of
sufficiently large order.

As an immediate consequence we extend Theorem 1.1 to general sub-Gaussian
coefficients:

######  Corollary 1.5.

The limit (1.6) holds when $\xi$ is any sub-Gaussian random variable of mean
zero and unit variance.

In particular, (1.6) holds for Rademacher polynomials, which were the focus of
the aforementioned works of Littlewood and others. In fact, the Rademacher
case in some sense captures the main challenges for our proof. We comment on
some of these challenges below. See Figure 1 for a numerical illustration of
the universality phenomenon.

Figure 1: Histogram of the minimum modulus over $10^{4}$ points equally spaced
points on the unit circle, for $10^{4}$ samples of a random degree 20
polynomial $P_{n}(x)$ of (1.4) with Rademacher (left) and Gaussian (right)
coefficients.

We mention that the distribution of the _maximum_ value over a curve for
various random analytic functions has been studied extensively; see for
instances the books [AT07, AW09] and the references therein. Sharp asymptotics
for the maximum of random trigonometric polynomials with Rademacher
coefficients were obtained by Salem and Zygmund [SZ54] and Halász [Hal73], and
extended to more general coefficient distributions by Kahane [Kah85]. In
recent years there has been particular focus on characteristic polynomials of
random unitary matrices, with $\gamma$ the unit circle [ABB17, PZ17, CMN18,
CZ20], and the Riemann zeta function on a randomly shifted unit interval on
the critical axis [ABB+19, Naj18, Har, ABR]. Such questions are closely tied
to a fine understanding of large deviations and concentration of measure for
values of the function at given points.

The minimum modulus has received comparatively less attention. As we explain
below, its behavior is governed by central limit theorems and anti-
concentration for the distribution at given points. (Another well-known
instance of the dichotomy of concentration/anti-concentration for large/small
values of random fields is in the study of singular values of random
matrices.)

We further note that proving universality for roots of classical random
ensembles has become an active direction of research in recent years, see for
instance [BD04, DNV15, DNV18, IKM16, KZ14, NNV16, NV17, TV15] and the
references therein. Our main result stands out from the above works in two
ways: that our focus is not on the statistics of roots, and our method is
totally different. Corollary 1.5 can be seen as a polynomial analogue of the
result [TV10a] by Tao an Vu where they showed that the least singular value
statistics of random iid matrices is universal, although there is no real
connection between the random matrix model and our random polynomials. It is
remarked that the study of both the minimum modulus of Kac polynomials and of
the least singular values of random matrices have important implications to
the study of the condition number of matrices, see for instance [BG05] and
[TV10b].

Finally, we note that since the completion of this work, there has been
progress on the related problem of the distance of the _nearest root_ of Kac
polynomials to the unit circle. A beautiful result of Michelen and
Sahasrabudhe [MiSa] establishes the limiting distribution for the Gaussian
case, resolving a conjecture of Shepp and Vanderbei [ShVa]. In recent work
with Yakir and Zeitouni [CNYZ] we apply some tools developed in the present
paper to show their result is universal.

###  1.1 Some comments on the proof

We briefly sketch some highlights of the proof of Theorem 1.2. Consider the
parametrized random curve $\\{P_{n}(x):x\in[-\pi,\pi]\\}$ as the trajectory of
a particle in the complex plane. Following [KS99] we approximate the time the
particle is closest to the origin by a point in a discrete mesh
${\mathcal{X}}=\\{x_{\alpha}\\}_{\alpha=1}^{N}\subset[-\pi,\pi]$. Since the
velocity $P_{n}^{\prime}(x)$ is typically of order $n$, in order to capture
this moment we must take $N$ much larger than $n$. However, this means that
each approach within distance $O(1/n)$ of the origin will carry several points
$P_{n}(x)$, $x\in{\mathcal{X}}$ near the origin, so that a union bound over
events that $P_{n}(x_{\alpha})=O(1/n)$ is too wasteful to isolate the
distribution of $m_{n}$. Following [YZ], we isolate a single time
$x_{\alpha}\in{\mathcal{X}}$ for each approach, so that $|P_{n}(x_{\alpha})|$
is approximately a local minimum, by considering both $P_{n}(x_{\alpha})$ and
$P_{n}^{\prime}(x_{\alpha})$ – the precise criterion is given in Section 2.1.
The result is a collection of events ${\mathcal{A}}_{\alpha}$, $\alpha\in[N]$,
that $x_{\alpha}$ is an approximate local minimizer, with each event
determined by the positions and velocities of the particle on the discrete set
${\mathcal{X}}$. In this way we obtain a point process ${\mathcal{M}}_{n}$ on
${\mathbb{R}}_{+}$ of approximate local minima $n|P_{n}(x_{\alpha})|$,
rescaled so that the global minimum is of order one.

For the Gaussian case, it was shown in [YZ] that ${\mathcal{M}}_{n}$ is
approximately a Poisson point process of intensity $2\sqrt{\pi/3}$, from which
the result clearly follows. In Section 2.2 we provide a sketch of their key
argument using an invariance principle of Liggett. For universality, our
approach is to establish universality for the joint distribution of

$S_{n}=S_{n}(\alpha_{1},\dots,\alpha_{m}):=(P_{n}(x_{\alpha_{i}}),P_{n}^{\prime}(x_{\alpha_{i}}))_{i\in[m]}\in{\mathbb{C}}^{2{m}}$

giving the positions and velocities of the particle at any fixed collection of
times $x_{\alpha_{1}},\dots,x_{\alpha_{m}}$; this allows us to deduce
universality for the global minimum by comparison of moments.

The event that the real and imaginary parts of the positions and velocities
lie in given ranges, and moreover that ${\mathcal{A}}_{\alpha_{i}}$ holds for
each $i\in[m]$, is the event that the vector $S_{n}$ lies in a certain compact
domain ${\mathcal{U}}_{n}$ in $4m$-(real-)dimensional phase space. While
${\mathcal{U}}_{n}$ has piecewise smooth boundary, its regularity depends
strongly on $n$, so that estimating its measure under the law of $S_{n}$
requires precise estimates of the measure of boxes at polynomially-small
scales.

Recalling that $P_{n}$ is a trigonometric polynomial, we see that $S_{n}$ is a
random walk of the form $\sum_{j=-n}^{n}\xi_{j}{\boldsymbol{w}}_{j}$, with
${\boldsymbol{w}}_{j}\in{\mathbb{R}}^{4m}$ giving the real and imaginary parts
of $e(jx)$ and its derivative $je(jx)$ at the times
$x_{\alpha_{1}},\dots,x_{\alpha_{m}}$. In particular, when the coefficients
$\xi_{j}$ are Gaussian, $S_{n}$ is a Gaussian vector, and so the main problem
is to obtain a quantitative central limit theorem for $S_{n}$ when the
coefficients are general sub-Gaussian variables. This, as well as a small ball
estimate, hinge on a strong decay estimate on the characteristic function of
$S_{n}$ (Theorem 3.1), which is the main technical component of the proof. (In
fact our argument yields more than a CLT, giving a quantitative _Edgeworth
expansion_ for the distribution of $S_{n}$, though for our purposes we only
need that each term of the expansion is smooth.)

In our general setting and in particular when the coefficients have discrete
distribution, the distribution of the polynomial and its derivative at given
points $x_{\alpha_{1}},\dots,x_{\alpha_{m}}$ depends strongly on arithmetic
properties of the $x_{\alpha_{i}}$ (compared to the complex Gaussian case of
Theorem 1.1 where the distribution is stationary under rotations.) In
particular, the desired control on the characteristic function does not hold
for all choices of the $x_{\alpha_{i}}$ – basically when two of the points are
too close together or nearly antipodal, or when $e(x_{\alpha_{i}})$ is close
to a root of unity of order $n^{o(1)}$ for some $i\in[m]$. We handle such
“bad” $m$-tuples with relatively crude arguments (following [KS99]), and
establish the decay estimate on the characteristic function for “nice” tuples.

The latter is the most technically challenging part of the proof. A similar
estimate for the case ${m}=2$ was obtained in [DNN], but the generalization to
higher dimensions, together with the complexity of the case when $\xi$ is
real-valued, pose significant challenges. For this, roughly speaking, we must
show that it is not possible to simultaneously dilate the steps
${\boldsymbol{w}}_{j}$ of the walk by a factor $K$, for any $K=n^{O(1)}$, so
that their projections $\psi_{j}$ in some common direction all approximately
lie in the integer lattice. We argue by contradiction, showing that if there
is such a projection and dilation, then the sequence $\psi_{j}$ can be locally
approximated by polynomial progressions of controlled degree. Here we
crucially use the trigonometric properties of the steps
${\boldsymbol{w}}_{j}$. Combining this information with some judicious
differencing manipulations, we can isolate an angle $x_{i}$ that is well-
approximated by a rational of small denominator, contradicting the smoothness
assumption.

To summarize, some highlights of our note include:

  1. 1.

A nearly sharp characterization, in terms of arithmetic properties, of the
collection of arcs of the circle over which the Kac polynomial is strongly
approximated by a Gaussian Kac polynomial (in the sense of joint distributions
at any fixed number of points);

  2. 2.

Sharp small ball estimates under microscopic scaling for random walks in
${\mathbb{R}}^{m}$ of the form
$\sum_{j}\xi_{j}(g(\frac{jt_{1}}{n}),\dots,g(\frac{jt_{m}}{n}))$ for various
smooth functions $g:S^{1}\to{\mathbb{C}}$, such as $e(x)$, or $x\sin x$;

  3. 3.

Local limit theorems for such high-dimensional random walks;

  4. 4.

A sub-polynomial decay estimate on the associated characteristic function,
which greatly improves on estimates from [KS99].

All of these results seem to be new and of independent interest.

###  1.2 Organization

In Section 2 we will discuss the proof of [YZ] and reduce our task to
establishing Proposition 2.7, establishing universality for the joint
distribution of low-lying near-local minima over a discrete subset of the
torus. Along the way we recall some lemmas from [YZ], and identify two
important arithmetic properties for collections of points in the torus that
will be crucial for subsequent analysis. Section 3 reformulates Proposition
2.7 in terms of a vector-valued random walk, and proves it using a small-ball
estimate (Theorem 3.4) and local central limit theorem (Theorem 3.2), which
are consequences of a strong decay estimate for the characteristic function
(Theorem 3.1). The deduction of the main result from Proposition 2.7 is given
in Sections 5 and 6. Theorem 3.4 and Theorem 3.2 are deduced from Theorem 3.1
in Sections 7 and 8, respectively, and Theorem 3.1 is proved in Section 9.
Finally, in Section 10 we describe how our result can be extended to other
models of random trigonometric polynomials.

###  1.3 Notation

We write $C,C^{\prime},C_{0},c$ etc. to denote positive absolute constants,
which may change from line to line, while $C(\tau)$ etc. denotes a constant
that depends only on the parameter (or set of parameters) $\tau$. We use the
standard asymptotic notation $f=O(g)$, $f\ll g$ and $g\gg f$ to mean $|f|\leq
Cg$ for some absolute constant $C>0$, and $f=O_{\tau}(g)$, $f\ll_{\tau}g$ and
$g\gg_{\tau}f$ to mean $|f|\leq C(\tau)g$. For positive sequences
$\\{f_{n}\\},\\{g_{n}\\}$ we say that $g_{n}=o(f_{n})$ and
$f_{n}=\omega(g_{n})$ if $\lim f_{n}/g_{n}\to\infty$ with $n$. We allow
implied constants to depend on the sub-Gaussian constant of $\xi$ without
explicitly indicating this.

For a real number $x$, $\|x\|_{{\mathbb{R}}/{\mathbb{Z}}}$ denotes the
distance from $x$ to the nearest integer, and
$m=m_{\operatorname{{Leb}}}(\cdot)$ denotes the Lebesgue measure on
${\mathbb{R}}^{d}$ for any $d$. For a compact interval $J\subset{\mathbb{R}}$
we write $|J|:=m_{\operatorname{{Leb}}}(J)$ for its length. $\\{t\\}=t-\lfloor
t\rfloor$ denotes the fractional part of $t\in{\mathbb{R}}$. We write
$e_{n}(\theta)$ for $e(\theta/n)$. The singular values of a matrix $M$ are
ordered $\sigma_{1}(M)\geq\sigma_{2}(M)\geq\cdots$.

Sequences $(\xi_{j})_{j}$ are understood to be sequences of iid copies of the
variable $\xi$ from Theorem 1.2. We write
${\mathbf{P}}_{{\mathcal{N}}_{{\mathbb{R}}}(0,1)}$ for a probability measure
under which the coefficients $\xi_{j}$ in (1.4) are standard real Gaussians,
and write ${\mathbf{E}}_{{\mathcal{N}}_{{\mathbb{R}}}(0,1)}$ for the
associated expectation. (This notation is only used for comparisons of random
variables in law – we do not consider couplings.)

###  1.4 Acknowledgements

We thank Pavel Bleher, Yen Do, Oanh Nguyen, Oren Yakir and Ofer Zeitouni for
helpful discussions and comments, and to Yakir and Zeitouni for showing us an
early draft of their work [YZ] on the Gaussian case. This project was
initiated at the American Institute of Mathematics meeting “Zeros of random
polynomials” in August 2019, where Bleher and Zeitouni were also participants.
In particular, the idea used here and in [YZ] to study local linearizations
emerged from those discussions. We thank the workshop organizers and the
Institute for providing a stimulating research environment.

##  2 Preliminary reductions

Our main objective in this section is to reduce our task to proving
Proposition 2.7 below, which gives a comparison principle for the joint
distribution of low-lying values for a discretized process over the circle.
Along the way we recall elements of the proof from [YZ] that we will need. For
completeness we also include a brief description of their argument for the
Gaussian case.

###  2.1 Passage to local linearizations

We begin by recalling the approach from [YZ] for selecting near-local-
minimizers of $|P_{n}(x)|$ on a discrete set; we refer to Section 1.1 for the
high-level motivation of this approach. The criterion for $x_{\alpha}$ to be
such a representative point is in terms of the local linearization
$F_{\alpha}$ of $P_{n}$ at $x_{\alpha}$ – the intuition is that for the mesh
point $x_{\alpha}$ that is closest to a local minimizer of $|P_{n}(x)|$, it
will also be close to the minimizer of $|F_{\alpha}(x)|$. A key take-away from
this approximation is that all information on near-minimizers of $|P_{n}(x)|$
is encoded in the values of $P_{n}$ _and its derivative_ at the mesh points.

We collect some notation and lemmas from [YZ], with some minor modifications.
Let ${K_{0}}>4$ be a sufficiently large constant and set

$N:=\bigg{\lfloor}\frac{n^{2}}{\log^{{K_{0}}}n}\bigg{\rfloor}.$ (2.1)

We divide $[-\pi,\pi]$ into $N$ intervals: letting

$x_{\alpha}=\frac{2\pi\alpha}{N}\,,\qquad\alpha=1,\dots,N,$

we decompose

$[-\pi,\pi]=\bigcup_{\alpha=1}^{N}I_{\alpha},\quad\text{ where
}I_{\alpha}=\Big{[}x_{\alpha}-\frac{\pi}{N},x_{\alpha}+\frac{\pi}{N}\Big{]}.$

Note that for the case of real coefficients it suffices to consider
$x_{\alpha}\in[0,\pi]$.

Define

$\displaystyle Y_{\alpha}$
$\displaystyle:=-\frac{{\operatorname{Re}}({P}_{n}(x_{\alpha})\overline{{P}_{n}^{\prime}(x_{\alpha})})}{|{P}_{n}^{\prime}(x_{\alpha})|^{2}}\,,\qquad
Z_{\alpha}:=n\frac{{\operatorname{Im}}({P}_{n}(x_{\alpha})\overline{{P}_{n}^{\prime}(x_{\alpha})})}{|{P}_{n}^{\prime}(x_{\alpha})|}\,.$
(2.2)

We denote the local linearizations of ${P}_{n}$ given by

$F_{\alpha}(x):={P}_{n}(x_{\alpha})+(x-x_{\alpha}){P}_{n}^{\prime}(x_{\alpha}).$
(2.3)

As shown in [YZ, Section 1.3], $|F_{\alpha}(x)|$ is minimized at
$x=x_{\alpha}+Y_{\alpha}$, where it takes the value $|Z_{\alpha}|/n$; thus

$|F_{\alpha}(x_{\alpha}+Y_{\alpha})|=|Z_{\alpha}|/n=\min_{x\in{\mathbb{R}}}|F_{\alpha}(x)|.$
(2.4)

(The sign is kept on $Z_{\alpha}$ only for convenience – we mention that the
sign encodes whether the origin is to the left or right of the curve
$\\{P_{n}(x):x\in[-\pi,\pi]\\}$ as $x$ increases through $x_{\alpha}$, but
this fact will not be used.)

We denote the $2\pi n$-periodic trigonometric polynomial

${\widetilde{P}}_{n}(s)={P}_{n}(s/n),\qquad s\in{\mathbb{R}}.$ (2.5)

This scaling will often be convenient since all of its derivatives are
typically of order 1.

We consider the collection $\\{Z_{\alpha}\\}_{\alpha\in[N]}$ as a point
process on ${\mathbb{R}}$. The scaling by $n$ means we focus on (signed) low-
lying values of $|P_{n}|$. Now we give the criterion by which “representative”
near-minimizers are selected. Let
${\mathcal{A}}_{\alpha}:={\mathcal{A}}_{\alpha}^{\prime}\cap{\mathcal{A}}_{\alpha}^{\prime\prime}$
where

${\mathcal{A}}_{\alpha}^{\prime}:=\\{|Y_{\alpha}|\leq\pi/N,|Z_{\alpha}|\leq\log
n\\}$

and

$\displaystyle{\mathcal{A}}_{\alpha}^{\prime\prime}:$
$\displaystyle=\\{|{P}_{n}(x_{\alpha})|\leq
n^{-1/2},|{P}_{n}^{\prime}(x_{\alpha})|\in[n\log^{-{K_{0}}/2}n,C_{0}n\sqrt{\log
n}]\\}\,,$

and define the point process

${{\mathcal{M}}}_{n}=\sum_{\alpha=1}^{N}\delta_{X_{\alpha}},\qquad
X_{\alpha}:=Z_{\alpha}\mathbbm{1}_{{\mathcal{A}}_{\alpha}}+\infty\mathbbm{1}_{{\mathcal{A}}_{\alpha}^{c}}\,.$
(2.6)

The event ${\mathcal{A}}_{\alpha}^{\prime}$ is the condition on the local
linearization that was described above, while
${\mathcal{A}}_{\alpha}^{\prime\prime}$ enforces some regularity of $P_{n}$ on
$I_{\alpha}$.

The following control on the second derivative will be used to show that the
local linearizations $F_{\alpha}$ are good approximations to ${P}_{n}$ at the
scale of the intervals $I_{\alpha}$.

######  Lemma 2.1 (Derivative bounds).

For ${K}>1$ and integer $k\geq 0$ let ${\mathcal{G}}_{k}({K})$ be the event
that

$\sup_{s\in{\mathbb{R}}}|{\widetilde{P}}_{n}^{(k)}(s)|=\frac{1}{n^{k}}\sup_{x\in[-\pi,\pi]}|P_{n}^{(k)}(x)|\leq\log^{K}n.$

There exists $c=c(k)>0$ depending only on $k$ and the sub-Gaussian moment of
$\xi$ such that

${\mathbf{P}}({\mathcal{G}}_{k}({K})^{c})\leq\exp(-c\log^{2{K}}n).$

###### Proof.

Fix $K$ and $k$. It suffices to show the claimed bound for
$R:={\operatorname{Re}}{\widetilde{P}}_{n}^{(k)}$. By Bernstein’s inequality,

$\sup_{t\in[-n\pi,n\pi]}|R^{\prime}(t)|\ll\sup_{t\in[-n\pi,n\pi]}|R(t)|\,,$

so if we assume that $\sup_{t}|R(t)|$ is attained at $t_{0}$, then for all
$|t-t_{0}|\leq c_{0}$ for a sufficiently small constant $c>0$, we have

$|R(t)|\geq|R(t_{0})|-|t-t_{0}|\sup_{t\in[-n\pi,n\pi]}|R^{\prime}(t)|>|R(t_{0})|/2.$

It follows that if we divide $[-n\pi,n\pi]$ into $O(n)$ intervals $J_{i}$ of
sufficiently small length and with midpoints $t_{i}$, then we have
$\sup_{i}|R(t_{i})|>\frac{1}{2}\sup_{t\in[-n\pi,n\pi]}|R(t)|$. Hence

$\displaystyle{\mathbf{P}}(\sup_{t\in[-n\pi,n\pi]}|R(t)|\geq(\log
n)^{{K}})\leq\sum_{i}{\mathbf{P}}(|R(t_{i})|$ $\displaystyle\geq(\log
n)^{{K}}/2)$ $\displaystyle\ll n\exp(-c^{\prime}(\log
n)^{2{K}})\leq\exp(-c(\log n)^{2{K}})\,,$

where we used a sub-Gaussian tail estimate for the upper bound for each
$t_{i}$. ∎

The next proposition shows that near-minimizers are typically well separated.
The proof is a straightforward modification of the proof of [YZ, Lemma 2.11]
and is deferred to Appendix A. There is the minor issue that a local minimizer
for ${P}_{n}$ may cause a low value for two neighboring linearizations
simultaneously, as accounted for in part (i). This will (unfortunately)
present some issues of a purely technical nature in the proof of Proposition
2.5 below.

######  Lemma 2.2.

On the event ${\mathcal{G}}_{2}({K_{0}}/2)$ we have

  1. (i)

If ${\mathcal{A}}_{\alpha}$ and ${\mathcal{A}}_{\alpha+1}$ hold, then

$Y_{\alpha}\in[\frac{\pi}{N}-\frac{\pi}{N\log^{{K_{0}}/4}n},\frac{\pi}{N}].$

  2. (ii)

Furthermore, ${\mathcal{A}}_{\alpha}$ and ${\mathcal{A}}_{\alpha^{\prime}}$
cannot hold simultaneously as long as

$2\leq|\alpha^{\prime}-\alpha|\leq\frac{n}{\log^{3{K_{0}}}n}.$

###  2.2 The Yakir–Zeitouni invariance argument

Now we discuss briefly the key remaining ideas of [YZ] for the Gaussian case
(or the case with small Gaussian component as in (1.7)), which employs a
strategy used by Biskup and Louidor in their work on extreme values of the
planar discrete Gaussian free field [BL16] . The approach combines the
following ingredients:

  1. 1.

A Gaussian computation showing that for any interval
$[a,b]\subset{\mathbb{R}}$ we have
$\lim_{n\to\infty}{\mathbf{E}}({\mathcal{M}}_{n}([a,b]))=\sqrt{\frac{\pi}{3}}(b-a)$.

  2. 2.

A consequence of a general result of Liggett [Lig78]:333 that if the law of a
point process is invariant under adding an independent Gaussian perturbation
to each point, then it is a Poisson point process of constant intensity.

  3. 3.

A consequence of the Gaussianity of the field
$\\{P_{n}(x)\\}_{x\in[-\pi,\pi]}$: that if $Q_{n}$ is an independent copy of
$P_{n}$, then
$\widehat{P_{n}}(x)=\sqrt{1-\frac{1}{n^{2}}}P_{n}(x)+\frac{1}{n}Q_{n}(x)$ is
identically distributed to $P_{n}(x)$.

  4. 4.

The fact that near-minimizers of $|P_{n}|$ are well separated (from a
strengthening of Lemma 2.2).

Roughly speaking, from (3) one can view $\widehat{P_{n}}$ as a perturbation of
$P_{n}$ by an independent Gaussian field $\frac{1}{n}Q_{n}$ of typical size
$1/n$, which is the scale of the minimum modulus. Thus, the point process
$\widehat{{\mathcal{M}}}_{n}$ is obtained from ${\mathcal{M}}_{n}$ by (a
slight rescaling and) a perturbation of each point by a standard Gaussian. Now
from (4), the low values of $|P_{n}(x)|$ occur at points $x$ that are
sufficiently separated that (as one can show) the values of $Q_{n}(x)$ at
these near-minimizers are nearly uncorrelated. Hence, the point process
$\widehat{{\mathcal{M}}}_{n}$ is approximately a point process obtained from
${\mathcal{M}}_{n}$ by perturbing each $X_{\alpha}$ by an independent
Gaussian. From (2) we get that $\widehat{{\mathcal{M}}}_{n}$, and hence,
${\mathcal{M}}_{n}$, is a Poisson point process of constant intensity, and
from (1) it follows that the intensity is $\sqrt{\pi/3}$. (To apply (2) one
cannot actually argue at finite $n$ as just described, but instead one needs
to pass to subsequential limiting point processes, obtained from the tightness
implied by (1); in the end one finds a limiting Poisson point process of the
same intensity regardless of the subsequence.)

Morally speaking, the exponential law is then a straightforward consequence of
the minimum being approximately the smallest (absolute) value of a Poisson
point process on ${\mathbb{R}}$. The formal argument requires some
considerable work to justify all of the approximations, and the above sketch
glides over many important points; we invite the reader to see [YZ] for
further details.

###  2.3 Towards universality: matching moments over smooth points

It should be evident that the beautiful argument of [YZ] just described relies
heavily and in several different ways on properties of the Gaussian
distribution. Towards establishing Theorem 1.2, our approach is to establish
universality for the joint distribution of $X_{\alpha}$ at any fixed number of
indices $\alpha\in[N]$ (in particular this yields universality for the joint
intensity functions of the point process ${\mathcal{M}}_{n}$). From this one
can deduce universality of moments
${\mathbf{E}}({\mathcal{M}}_{n}([-\tau,\tau])^{m})$ of all order, leading to
universality for the distribution function ${\mathbf{P}}(m_{n}\leq\tau/n)$.

For general $\xi$, the main difficulty for studying the joint distribution of
$P_{n}(x_{i})$ and its derivative at $m$ different points $x_{i}$, or even at
a single point $x$, is that the distribution is highly dependent on arithmetic
properties of the points. Consider the case of Rademacher coefficients. At
$x=0$ we have $P_{n}(0)=\frac{1}{\sqrt{2n+1}}\sum_{j=-n}^{n}\xi_{j}$ – while
from the Central Limit Theorem this approaches the
${\mathcal{N}}_{\mathbb{R}}(0,1)$ distribution, it does so at the slowest
possible rate, and the distribution is only smooth (i.e. comparable to
Lebesgue measure on balls of radius $\delta$) at scales $\delta$ much larger
than $1/\sqrt{n}$. At $x=\pi/2$ we have that $P_{n}(\pi/2)$ splits into
independent real and imaginary sums, each tending to the
${\mathcal{N}}_{\mathbb{R}}(0,1/2)$ distribution at the slowest possible rate.
The situation is slightly improved at $x=\pi/4$, for which one can obtain a
meaningful small ball estimate at scale $\delta\sim 1/n$ with some effort. As
we shrink the scale $\delta$ at which we desire $P_{n}(x)$ to have an
effectively smooth distribution, the collection of “structured” angles that we
must avoid increases.

Thus we see that Diophantine approximation will play a crucial role in our
arguments. Indeed, such considerations played a strong role in the argument of
Konyagin and Schlag for the upper bound (1.3). That work only dealt with the
field at single points, however; to compare the joint distribution of $P_{n}$
and its derivative at an arbitrary fixed number of points we need finer
control.

We quantify the level of approximability of points $x$ by rationals as
follows:

######  Definition 2.3 (Smooth points).

For ${K}>0$, we say a point $t\in{\mathbb{R}}$ is _${K}$ -smooth_ if

$\Big{\|}\frac{p_{0}t}{\pi
n}\Big{\|}_{{\mathbb{R}}/{\mathbb{Z}}}>\frac{{K}}{n}\qquad\forall\;p_{0}\in{\mathbb{Z}}\cap[-{K}-1,{K}+1],p_{0}\neq
0.$

We say a tuple $(t_{1},\dots,t_{m})$ is ${K}$-smooth if $t_{r}$ is
${K}$-smooth for each $1\leq r\leq{m}$.

Thus in the special case that $K<1$ then $t\in{\mathbb{R}}$ is _${K}$ -smooth_
if $\|\frac{t}{\pi n}\|_{{\mathbb{R}}/{\mathbb{Z}}}>\frac{{K}}{n}.$ Observe
also that if $n^{-1+\kappa}\leq\|\frac{t}{\pi
n}\|_{{\mathbb{R}}/{\mathbb{Z}}}\leq n^{-2\kappa}$ then $t$ is
$n^{\kappa}$-smooth.

The following lets us focus on potential minimizers that are smooth.

######  Lemma 2.4 (Ruling out bad arcs).

For ${\kappa}>0$ let ${E_{\operatorname{{bad}}}}({\kappa})$ be the set of
points $x\in{\mathbb{R}}$ such that $nx$ is not $n^{\kappa}$-smooth. There
exist absolute constants ${\kappa}_{0},c_{0}>0$ such that

${\mathbf{P}}\big{(}\,\exists
x\in{E_{\operatorname{{bad}}}}({\kappa}_{0}):|{P}_{n}(x)|\leq
n^{-1+c_{0}}\,\big{)}=o(1).$

###### Proof.

This follows from the argument for [KS99, Lemma 3.3]; one only needs two
modifications:

  1. 1.

Whereas they considered $A$-smooth points for $A$ fixed, their bounds in fact
allow $A$ to grow as fast as $n^{{\kappa}_{0}}$ for $\kappa_{0}$ sufficiently
small. (One also notes that their parameter $\varepsilon$ may grow as fast as
$O(n^{3/4})$.)

  2. 2.

Whereas their model takes the sum in (1.4) to run over $[0,n]$ rather than
$[-n,n]$, they only need that the covariance matrix for
$({\operatorname{Re}}P_{n}(x),{\operatorname{Im}}P_{n}(x))$ has eigenvalues
bounded below by $\gg n^{2}\min(1,|x|,|\pi-x|)^{2}$ for $\min(|x|,|\pi-x|)\gg
n^{-1-c}$ for a small absolute constant $c>0$, which for the present model
follows from display (2.21) in [YZ]. (One may alternatively apply the proof of
[KS99, Lemma 3.3] but condition on the variables $(\xi_{j})_{-n\leq j<0}$
before applying the Berry–Esseen theorem.)

∎

With ${\kappa}_{0}$ as in Lemma 2.4 we now consider the thinned point process

${{\mathcal{M}}}_{n}^{\sharp}:=\sum_{\alpha:x_{\alpha}\notin{E_{\operatorname{{bad}}}}({\kappa}_{0})}\delta_{X_{\alpha}}.$
(2.7)

Theorem 1.2 will be deduced from the following comparison of moments. The
proof is deferred to Section 5.

######  Proposition 2.5 (Moment matching).

For any fixed $0pt>0$ and integer ${m}\geq 1$ we have

$\lim_{n\to\infty}{\mathbf{E}}\Big{(}{{\mathcal{M}}}_{n}^{\sharp}\big{(}[-0pt,0pt]\big{)}^{m}\Big{)}=\lim_{n\to\infty}{\mathbf{E}}_{{{\mathcal{N}}_{{\mathbb{R}}}(0,1)}}\Big{(}{{\mathcal{M}}}_{n}^{\sharp}\big{(}[-0pt,0pt]\big{)}^{m}\Big{)},$
(2.8)

where we recall that ${\mathbf{E}}_{{{\mathcal{N}}_{{\mathbb{R}}}(0,1)}}$
stands for expectation under the Gaussian model from Theorem 1.1.

###  2.4 Joint distribution over spread points

Expanding the moments in (2.8) leads to consideration of joint events that
$X_{\alpha_{i}}$ is small at $m$ different points $x_{\alpha_{i}}$, $1\leq
i\leq m$. In addition to the smoothness already imposed in the definition of
${{\mathcal{M}}}_{n}^{\sharp}$, we will require all of the points to be
separated from one another, in the following sense:

######  Definition 2.6 (Spread tuples).

For $m\geq 2$ and ${\lambda}>0$, we say
$\boldsymbol{t}=(t_{1},\dots,t_{m})\in{\mathbb{R}}^{m}$ is _${\lambda}$
-spread_ if

$\Big{\|}\frac{t_{r}\pm t_{r^{\prime}}}{2\pi
n}\Big{\|}_{{\mathbb{R}}/{\mathbb{Z}}}\geq\frac{{\lambda}}{n}\qquad\forall\,1\leq
r<r^{\prime}\leq{m}\mbox{ (and all choices of the signs $\pm$). }$

For $m=1$, we say that $\boldsymbol{t}=t\in{\mathbb{R}}$ is _${\lambda}$
-spread_ if

$\Big{\|}\frac{t}{2\pi
n}\Big{\|}_{{\mathbb{R}}/{\mathbb{Z}}}\geq\frac{{\lambda}}{n}.$

It is remarked that in the definition above we prevent $t_{r}$ from being
close to $t_{r^{\prime}}$ and $-t_{r^{\prime}}$ at the same time, and this
condition is necessary to hope for asymptotically independence between
$P_{n}(t_{r})$ and $P_{n}(t_{r^{\prime}})$, especially in the case that $\xi$
is real-valued.

In what follows we denote

$s_{\alpha}:=nx_{\alpha},\qquad\alpha\in[N].$ (2.9)

Recalling the scaled polynomial $\widetilde{P}$ from (2.5), we have

$Y_{\alpha}=-\frac{1}{n}\frac{{\operatorname{Re}}(\widetilde{P}_{n}(s_{\alpha})\overline{\widetilde{P}_{n}^{\prime}(s_{\alpha})})}{|\widetilde{P}_{n}^{\prime}(s_{\alpha})|^{2}}\qquad
Z_{\alpha}=n\frac{{\operatorname{Im}}(\widetilde{P}_{n}(s_{\alpha})\overline{\widetilde{P}_{n}^{\prime}(s_{\alpha})})}{|\widetilde{P}_{n}^{\prime}(s_{\alpha})|}.$
(2.10)

The main step towards the proof of Proposition 2.5 is the following:

######  Proposition 2.7.

Fix an $m$-tuple of indices $(\alpha_{1},\dots,\alpha_{m})\in[N]^{m}$. Assume
for some ${\kappa}>0$ that $s_{\alpha_{1}},\dots,s_{\alpha_{m}}$ are
$n^{\kappa}$-smooth and that
$\boldsymbol{s}=(s_{{\alpha_{1}}},\dots,s_{{\alpha_{m}}})$ is $1$-spread. Then
for any $0pt>0$,

$\bigg{|}\,{\mathbf{P}}\bigg{(}\bigwedge_{i\in[{m}]}|X_{\alpha_{i}}|\leq
0pt\bigg{)}-{\mathbf{P}}_{{{\mathcal{N}}_{{\mathbb{R}}}(0,1)}}\bigg{(}\bigwedge_{i\in[m]}|X_{\alpha_{i}}|\leq
0pt\bigg{)}\,\bigg{|}=o(N^{-{m}}),$

where the rate of convergence depends on ${m},0pt,{\kappa},$ and ${K_{0}}$.

We prove Proposition 2.7 in Section 3 below, where we convert the task to a
problem involving a random walk in ${\mathbb{R}}^{4m}$. Before proceeding we
collect the following useful property of a smooth $m$-tuples, which basically
says that we can simultaneously dilate the points $t_{r}$ to be well separated
on the torus. This result will be useful for the proof of Lemma 3.6 below for
showing that the distribution of an associated random walk is genuinely full-
dimensional, and also for Section 9 when we bound
$\prod_{r=1}^{{m}-1}\|\frac{L(t_{m}\pm t_{r})}{2\pi
n}\|_{{\mathbb{R}}/{\mathbb{Z}}}$ from below for some $L$.

######  Lemma 2.8.

Assume $(t_{1},\dots,t_{m})\in{\mathbb{R}}^{m}$ is ${\lambda}$-spread for some
${\lambda}>0$, and let ${\lambda}\leq K=o(n)$. There exists an integer
${L}\asymp n/K$ such that

$\Big{\|}\frac{{L}\cdot(t_{r}\pm t_{r^{\prime}})}{2\pi
n}\Big{\|}_{{\mathbb{R}}/{\mathbb{Z}}}\gg_{m}{\lambda}/K\qquad\forall 1\leq
r<r^{\prime}\leq m$ (2.11)

(and all choices of the signs). In particular, if $(t_{1},\dots,t_{m})$ is
$\omega(1)$-spread then there exists ${L}\leq n$ such that

$\Big{\|}\frac{{L}\cdot(t_{r}\pm t_{r^{\prime}})}{2\pi
n}\Big{\|}_{{\mathbb{R}}/{\mathbb{Z}}}\gg_{m}1\qquad\forall 1\leq
r<r^{\prime}\leq m.$ (2.12)

In case $m=1$ then there exists an integer ${L}\asymp n/K$ such that
$\|\frac{{L}\cdot t}{2\pi n}\|_{{\mathbb{R}}/{\mathbb{Z}}}\gg_{m}{\lambda}/K.$

###### Proof.

The case $m=1$ is clear, so we just need to focus on $m\geq 2$. Assume towards
a contradiction that there exists $\varepsilon=\varepsilon({m})>0$ such that
for every $j\in[n/2K,n/K]$ there exists a pair of distinct indices
$r,r^{\prime}\in[m]$ such that

$\min\bigg{\\{}\bigg{\|}\frac{j(t_{r}-t_{r^{\prime}})}{2\pi
n}\bigg{\|}_{{\mathbb{R}}/{\mathbb{Z}}}\,,\,\bigg{\|}\frac{j(t_{r}+t_{r^{\prime}})}{2\pi
n}\bigg{\|}_{{\mathbb{R}}/{\mathbb{Z}}}\bigg{\\}}\leq\varepsilon{\lambda}/K$
(2.13)

By pigeonholing, there is a pair of distinct indices $r,r^{\prime}\in[{m}]$
and subset $J\subset[n/2K,n/K]$ of size $\gg n/K{m}^{2}$ such that either the
first quantity in the minimum in (2.13) is bounded by $\varepsilon{\lambda}/K$
for all $j\in J$, or the second is bounded by $\varepsilon{\lambda}/K$ for all
$j\in J$. We focus on the former case; the latter is handled by a similar
argument.

As $|J|$ is of the same order as its diameter, there exists $C=O_{m}(1)$ so
that $CJ-CJ$ contains a homogeneous arithmetic progression of length $\gg n/K$
(see for instance [Tao10, Lemma B.3]).

######  Claim 2.9.

Assume that $z=e^{i\theta},|\theta|\leq\pi/8$ such that for all $1\leq\ell\leq
M$ we have $|1-z^{\ell}|\leq 1/32$ for a sufficiently large $M$. Then
$|\theta|=O(1/M)$.

###### Proof.

By assumption, $|\theta|\leq\pi/8$ and
$\|2^{k}\theta\|_{{\mathbb{R}}/{\mathbb{Z}}}\leq\pi/8$ for all $1\leq
k\leq\log M$, and so we can repeatedly estimate $|\theta|$ to obtain
$|\theta|=O(1/M)$. ∎

By the triangle inequality, for $\varepsilon$ sufficiently small depending on
$C$, by 2.9 this would imply there exists $C_{r,r^{\prime}}=O_{m}(1)$ such
that

$\bigg{\|}\frac{C_{r,r^{\prime}}(t_{r}-t_{r^{\prime}})}{2\pi
n}\bigg{\|}_{{\mathbb{R}}/{\mathbb{Z}}}\ll_{m}\frac{\varepsilon{\lambda}/K}{n/K}\ll_{m}\varepsilon{\lambda}/n.$
(2.14)

Let ${\mathcal{N}}_{1}$ be the collection of all pairs $(r,r^{\prime})$ such
that (2.14) holds, taking $C_{r,r^{\prime}}$ to be the smallest such positive
integer. We have shown that ${\mathcal{N}}_{1}$ is nonempty. By the assumption
that $\boldsymbol{t}$ is ${\lambda}$-spread we have that $C_{r,r^{\prime}}>1$
for all $(r,r^{\prime})\in{\mathcal{N}}_{1}$.

######  Claim 2.10.

Assume that for some $x\in{\mathbb{R}},\delta>0$ and positive integer $M$ we
have $\|x\|_{{\mathbb{R}}/{\mathbb{Z}}}>\delta$ and
$\|Mx\|_{{\mathbb{R}}/{\mathbb{Z}}}\leq\delta$. Then

$\|x\|_{{\mathbb{R}}/{\mathbb{Z}}}>1/2M.$

###### Proof.

Assuming otherwise, we have
$\|Mx\|_{{\mathbb{R}}/{\mathbb{Z}}}=M\|x\|_{{\mathbb{R}}/{\mathbb{Z}}}>M\delta$,
a contradiction. ∎

From the above claim, (2.14), and the assumption $\boldsymbol{t}$ is
${\lambda}$-spread, it follows that if $\varepsilon$ is sufficiently small,
then

$\bigg{\|}\frac{t_{r}-t_{r^{\prime}}}{2\pi
n}\bigg{\|}_{{\mathbb{R}}/{\mathbb{Z}}}\geq 1/2C_{r,r^{\prime}}$

for each $(r,r^{\prime})\in{\mathcal{N}}_{1}$. Set
$D_{1}=\prod_{(r,r^{\prime})\in{\mathcal{N}}_{1}}C_{r,r^{\prime}}=O_{m}(1)$,
and let $I_{1}$ be intersection of the progression $\\{1+\ell
D_{1}\\}_{\ell\in{\mathbb{Z}}}$ with $[n/2K,n/K]$. Applying the triangle
inequality, if $L=1+lD_{1}\in I_{1}$ then for all
$(r,r^{\prime})\in{\mathcal{N}}_{1}$,

$\displaystyle\bigg{\|}\frac{L(t_{r}-t_{r^{\prime}})}{\pi
n}\bigg{\|}_{{\mathbb{R}}/{\mathbb{Z}}}=\bigg{\|}\frac{(1+lD_{1})(t_{r}-t_{r^{\prime}})}{2\pi
n}\bigg{\|}_{{\mathbb{R}}/{\mathbb{Z}}}$
$\displaystyle\geq\bigg{\|}\frac{t_{r}-t_{r^{\prime}}}{2\pi
n}\bigg{\|}_{{\mathbb{R}}/{\mathbb{Z}}}-\bigg{\|}\frac{l\frac{D_{1}}{C_{r,r^{\prime}}}C_{r,r^{\prime}}(t_{r}-t_{r^{\prime}})}{2\pi
n}\bigg{\|}_{{\mathbb{R}}/{\mathbb{Z}}}$ $\displaystyle\geq
1/2C_{r,r^{\prime}}-(n/K)O_{m}(\varepsilon{\lambda}/n)\geq\varepsilon{\lambda}/K$

provided that $\varepsilon$ is sufficiently small. Now if no $L\in I_{1}$
satisfies the conclusion of our lemma, then for each $L\in I_{1}$ there is a
pair $(r,r^{\prime})\notin{\mathcal{N}}_{1}$ that violates the condition, and
then we repeat the above process, with ${\mathcal{N}}_{2}$ being the
collection of such pairs. Set
$D_{2}=\prod_{(r,r^{\prime})\in{\mathcal{N}}_{2}}C_{r,r^{\prime}}$ (and so
$D_{2}=O_{m}(1)$) and let $I_{2}$ be intersection of the progression
$\\{1+\ell D_{1}D_{2}\\}_{\ell\in{\mathbb{Z}}}$ with $[n/2K,n/K]$, we then
continue the process as above. As each time we get rid of at least one pair
$(t_{r},t_{r^{\prime}})$, the process for differences terminates after
$\binom{{m}}{2}$ steps with $\Theta(n/K)$ indices left to choose. Finally, we
can start the process for $t_{r}+t_{r^{\prime}}$ with $j$ (appearing in
(2.14)) chosen from these indices; the remaining iterations are identical as
above.∎

##  3 Random walk in phase space

The key ingredients for the proof of Proposition 2.7 are local small ball
estimates and a comparison principle for an associated random walk in
${\mathbb{R}}^{4{m}}$, which we now define.

For a fixed tuple $\boldsymbol{t}=(t_{1},\dots,t_{m})\in{\mathbb{R}}^{m}$ and
$j\in{\mathbb{Z}}$ we denote the vectors

$\displaystyle{\boldsymbol{a}}_{j}={\boldsymbol{a}}_{j}(\boldsymbol{t})$
$\displaystyle:=\big{(}\sin(jt_{1}/n),\dots,\sin(jt_{m}/n)\big{)}\;\in{\mathbb{R}}^{m}$
$\displaystyle{\boldsymbol{b}}_{j}={\boldsymbol{b}}_{j}(\boldsymbol{t})$
$\displaystyle:=\big{(}\cos(jt_{1}/n),\dots,\cos(jt_{m}/n)\big{)}\;\in{\mathbb{R}}^{m}$

and

$\qquad{\boldsymbol{w}}_{j}={\boldsymbol{w}}_{j}(\boldsymbol{t})=\big{(}{\boldsymbol{a}}_{j}\,,\,(j/n){\boldsymbol{b}}_{j}\,,\,{\boldsymbol{b}}_{j}\,,\,-(j/n){\boldsymbol{a}}_{j}\big{)}\;\in{\mathbb{R}}^{4m}\,.$
(3.1)

For a finite set $J\subset{\mathbb{Z}}$ we let $W_{J}=W_{J}(\boldsymbol{t})$
be the matrix with rows ${\boldsymbol{w}}_{j}$, $j\in J$. Note that
$\boldsymbol{w}_{j}$ gives the values of the functions
$\sin(\frac{j}{n}\,\cdot),\cos(\frac{j}{n}\,\cdot)$ and their derivatives at
the points $t_{1},\dots,t_{m}$. We consider the random walk

$S_{n}(\boldsymbol{t}):=\sum_{j=-n}^{n}\xi_{j}\boldsymbol{w}_{j}(\boldsymbol{t})=W_{[-n,n]}^{\mathsf{T}}{\boldsymbol{\xi}}\;\in\,{\mathbb{R}}^{4m}$
(3.2)

with ${\boldsymbol{\xi}}=(\xi_{j})_{j\in[-n,n]}$ a vector of iid copies of a
real-valued $\xi$.

###  3.1 Control on the characteristic function

The following is the key technical ingredient for controlling the distribution
of the random walks $S_{n}(\boldsymbol{t})$.

######  Theorem 3.1.

Let $\boldsymbol{t}=(t_{1},\dots,t_{m})\in{\mathbb{R}}^{m}$ be
$n^{\kappa}$-smooth and ${\lambda}$-spread for some ${\kappa}\in(0,1)$ and
$\omega(n^{-1/8{m}})\leq{\lambda}\leq 1$. Then for any fixed $K_{*}<\infty$
and any $\boldsymbol{x}\in{\mathbb{R}}^{4m}$ with
$n^{-1/8}\leq\|\boldsymbol{x}\|_{2}\leq n^{K_{*}}$,

$|{\mathbf{E}}e(\langle
S_{n}(\boldsymbol{t}),\boldsymbol{x}\rangle)|\leq\exp(-\log^{2}n)$

for all $n$ sufficiently large depending on $K_{*},m,\kappa,$ and the sub-
Gaussian constant for $\xi$.

We note that here the sub-Gaussianity hypothesis enters only to have a uniform
anti-concentration bound for $\xi$ and could be replaced by a bound on the
Lévy concentration function.

We defer the proof of this theorem to Section 9. Now we state the two main
consequences of Theorem 3.1 towards the proof of Theorem 1.2. By combining
Theorem 3.1 with an Edgworth expansion, we will obtain the following
quantitative comparison with the Gaussian model. In the following we write
$\Gamma=\Gamma_{n}(\boldsymbol{t})\in{\mathbb{R}}^{4m}$ for a Gaussian vector
with covariance matrix $\frac{1}{2n+1}W_{[-n,n]}^{\mathsf{T}}W_{[-n,n]}$. Note
that this is the distribution of $\frac{1}{\sqrt{2n+1}}S_{n}(\boldsymbol{t})$
with iid standard real Gaussians in place of $\xi_{j}$.

######  Remark 3.3.

The proof shows that in place of the sub-Gaussianity assumption we only need
that $\xi$ has $O({m})$ finite moments.

We defer the proof of Theorem 3.2 to Section 8.

By standard arguments, the control on the characteristic function of
$S_{n}(\boldsymbol{t})$ provided by Theorem 3.1 yields an optimal small ball
estimate at arbitrary polynomial scales:

######  Theorem 3.4 (Small ball estimate).

With $\boldsymbol{t}=(t_{1},\dots,t_{m})$ as in Theorem 3.1, for any
$K<\infty$ and any $\delta\geq n^{-K}$,

$\sup_{w\in{\mathbb{R}}^{4m}}{\mathbf{P}}\bigg{(}\frac{1}{\sqrt{2n+1}}S_{n}(\boldsymbol{t})\in
B(w,\delta)\bigg{)}=O_{{m},{\kappa},K}({\lambda}^{-3{m}}\delta^{4{m}}).$

The proof of Theorem 3.4 is deferred to Section 7. We note the following
consequence, giving anti-concentration for the polynomial $P_{n}$ .

######  Corollary 3.5 (Small ball estimate for polynomials).

Assume that $t$ is $n^{\kappa}$-smooth. Then for any $K>0$ and
$\delta\in[n^{-K},1]$,

${\mathbf{P}}(|_{n}(t/n)|\leq\delta)=O_{\kappa,K}(\delta^{2})\qquad\text{ and
}\qquad{\mathbf{P}}(|^{\prime}_{n}(t/n)|\leq\delta)=O_{\kappa,K}(\delta^{2}).$

###  3.2 Non-degeneracy of the covariance matrix

As a first step towards controlling the distribution of
$S_{n}(\boldsymbol{t})$ we need to show that the random walk is genuinely
$4m$-dimensional, which amounts to showing the covariance matrix
$W_{[-n,n]}^{\mathsf{T}}W_{[-n,n]}$ has smallest singular value of order $n$.
This is accomplished by the following lemma, under the (necessary) assumption
that the points $t_{1},\dots,t_{m}$ are spread.

######  Lemma 3.6.

Let $J\subset[n]$ be an interval with $|J|\gg n$. If
$\boldsymbol{t}=(t_{1},\dots,t_{m})\in{\mathbb{R}}^{m}$ is ${\lambda}$-spread
for some ${\lambda}>0$, then

$\|W_{J}(\boldsymbol{t})u\|_{2}^{2}\gg_{m}\min({\lambda},1)^{6m-3}n$

uniformly over unit vectors $u\in S^{4m-1}$.

######  Remark 3.7.

We note that for the case $\xi_{j}\sim{\mathcal{N}}_{\mathbb{R}}(0,1)$, the
above control on the covariance matrix is enough to deduce an optimal small
ball estimate at all scales. For general distributions we need Theorem 3.1,
the proof of which amounts to showing that for $v$ of size $n^{O(1)}$, the
vector $W_{J}(\boldsymbol{t})v$ avoid the _lattice_ ${\mathbb{Z}}^{n}$, rather
than just the origin as above.

###### Proof of Lemma 3.6.

Without loss of generality we may assume ${\lambda}\in(0,1)$. Fix a vector
$u=(u^{1},u^{2},u^{3},u^{4})\in S^{4{m}-1}$. The $j$th entry of is

$\langle\boldsymbol{w}_{j},u\rangle=\sum_{r=1}^{m}u^{1}_{r}\sin(jt_{r}/n)+u^{2}_{r}(j/n)\cos(jt_{r}/n)+u^{3}_{r}\cos(jt_{r}/n)-u^{4}_{r}(j/n)\sin(jt_{r}/n).$

Substituting $\cos(jt_{r}/n)=\frac{1}{2}(e_{n}(jt_{r})+e_{n}(-jt_{r}))$ and
$\sin(jt_{r}/n)=-\frac{{\sqrt{-1}}}{2}(e_{n}(jt_{r})-e_{n}(-jt_{r}))$, the
above becomes

$\displaystyle\frac{1}{2}\sum_{r=1}^{m}(u_{r}^{3}-{\sqrt{-1}}u_{r}^{1})e_{n}(jt_{r})+(u_{r}^{3}+{\sqrt{-1}}u_{r}^{1})e_{n}(-jt_{r})$
$\displaystyle\qquad\qquad\qquad\qquad+(u_{r}^{2}+{\sqrt{-1}}u_{r}^{4})(j/n)e_{n}(jt_{r})+(u_{r}^{2}-{\sqrt{-1}}u_{r}^{4})(j/n)e_{n}(-jt_{r})$
$\displaystyle\qquad=\Big{\langle}\big{(}\boldsymbol{e}_{j},\bar{\boldsymbol{e}}_{j},(j/n)\boldsymbol{e}_{j},(j/n)\bar{\boldsymbol{e}}_{j}\big{)}\,,\,Au\Big{\rangle}$

where

$\boldsymbol{e}_{j}:=(e_{n}(jt_{1}),\dots,e_{n}(jt_{m}))$

and

$A=\frac{1}{2}\begin{pmatrix}-{\sqrt{-1}}I_{m}&0&I_{m}&0\\\
{\sqrt{-1}}I_{m}&0&I_{m}&0\\\ 0&I_{m}&0&{\sqrt{-1}}I_{m}\\\
0&I_{m}&0&-{\sqrt{-1}}I_{m}\end{pmatrix}$

where $I_{m}$ is the ${m}\times{m}$ identity matrix and 0 is the square matrix
of 0s. Since $\|A^{-1}\|=O(1)$, it suffices to show

$\|Mv\|_{2}^{2}\gg_{m}{\lambda}^{6m-3}n$

uniformly for $v$ in the complex sphere $S_{\mathbb{C}}^{4{m}-1}$, where
$M\in{\mathbb{C}}^{n\times 4m}$ is the matrix with rows

$(\boldsymbol{e}_{j},\bar{\boldsymbol{e}}_{j},{\sqrt{-1}}(j/n)\boldsymbol{e}_{j},{\sqrt{-1}}(j/n)\bar{\boldsymbol{e}}_{j}).$

From Lemma 2.8 there exists an integer ${L}$ with $n\ll_{m}{L}<n/100m$ such
that

$\Big{\|}\frac{{L}\cdot(t_{r}\pm t_{r^{\prime}})}{2\pi
n}\Big{\|}_{{\mathbb{R}}/{\mathbb{Z}}}\gg_{m}{\lambda}\qquad\forall 1\leq
r<r^{\prime}\leq m.$

For notational convenience we will consider $M$ with rows of the general form

$(e_{n}(jt_{1}),\dots,e_{n}(jt_{d}),{\sqrt{-1}}(j/n)e_{n}(jt_{1}),\dots,{\sqrt{-1}}(j/n)e_{n}(t_{d}))$

satisfying

$\Big{\|}\frac{{L}\cdot(t_{r}-t_{r^{\prime}})}{2\pi
n}\Big{\|}_{{\mathbb{R}}/{\mathbb{Z}}}\geq{\lambda}_{0}\qquad\forall 1\leq
r<r^{\prime}\leq d$ (3.3)

for some ${\lambda}_{0}\in(0,1)$ and $n\ll_{d}L<n/50d$, and aim to show

$\inf_{v\in S_{\mathbb{C}}^{2d-1}}\|Mv\|_{2}^{2}\gg_{d}{\lambda}_{0}^{3d-3}n.$
(3.4)

One passes back to the previous case by taking $d=2{m}$ and
$(t_{1},\dots,t_{2{m}})=(t_{1},\dots,t_{m},-t_{1},\dots,-t_{m})$, and
substituting any $c(m){\lambda}$ for ${\lambda}_{0}$.

Let $P$ denote the intersection of the interval $J$ with the progression
$\\{iL:i\in{\mathbb{Z}}\\}$, and let $M_{P}$ denote the submatrix of $M$ with
rows indexed by $P$. Note that $|P|\asymp_{d}1$. We will first show

$\inf_{v\in
S_{\mathbb{C}}^{2d-1}}\|M_{P}v\|_{2}^{2}\gg_{d}{\lambda}_{0}^{2d-2}.$ (3.5)

To do this we consider the twisted second-order differencing operators of the
form

$(D_{t_{0}}f)(j):=\sum_{a=0}^{2}{2\choose a}(-1)^{a}e(-aLt_{0})f(j+aL)$ (3.6)

acting on sequences $f:P\to{\mathbb{C}}$, for various choices of the parameter
$t_{0}\in{\mathbb{R}}$. Let us denote

$f_{t}(j)=e_{n}(jt),\qquad
g_{t}(j)={\sqrt{-1}}(j/n)e_{n}(jt)=\partial_{t}f_{t}(j).$

For $t,t_{0}\in{\mathbb{R}}$ and any $j\in P$ with $j+2L\in P$, we have

$(D_{t_{0}}f_{t})(j)=e_{n}(jt)\sum_{a=0}^{2}{2\choose
a}(-1)^{a}e(aL(t-t_{0}))=\big{[}1-e_{n}(L(t-t_{0}))\big{]}^{2}f_{t}(j)$ (3.7)

and

$\displaystyle(D_{t_{0}}g_{t})(j)$ $\displaystyle=\sum_{a=0}^{2}{2\choose
a}(-1)^{a}e(aL(t-t_{0})){\sqrt{-1}}\frac{j+aL}{n}e_{n}((j+aL)t)$
$\displaystyle={\sqrt{-1}}(j/n)(D_{t_{0}}f_{t})(j)+e_{n}(jt)\bigg{[}-2{\sqrt{-1}}\frac{L}{n}e_{n}(L(t-t_{0}))+2{\sqrt{-1}}\frac{L}{n}e_{n}(2L(t-t_{0}))\bigg{]}$
$\displaystyle=\big{[}1-e_{n}(L(t-t_{0}))\big{]}^{2}g_{t}(j)-2{\sqrt{-1}}\frac{L}{n}e_{n}(L(t-t_{0}))\big{[}1-e_{n}(L(t-t_{0}))\big{]}f_{t}(j)$
$\displaystyle=\big{[}1-e_{n}(L(t-t_{0}))\big{]}^{2}\big{[}g_{t}(j)+\beta_{L}(t-t_{0})f_{t}(j)\big{]}$
(3.8)

where we write
$\beta_{L}(s):=-2{\sqrt{-1}}\frac{L}{n}e_{n}(Ls)/\big{[}1-e_{n}(Ls)\big{]}$.
In particular, we have

$(D_{t_{0}}f_{t_{0}})(j)=(D_{t_{0}}g_{t_{0}})(j)=0\qquad\forall j.$ (3.9)

The key point about the factors $1-e_{n}(L\,\cdot)$ and $\beta_{L}(\cdot)$ is
that they are independent of $j$ and hence pass through the difference
operators $D_{t_{0}}$.

For the lower bound (3.5) we partition the sphere into $d$ pieces

$S_{r}=\\{v\in S_{\mathbb{C}}^{2d-1}:|v_{r}|^{2}+|v_{r+d}|^{2}\geq
1/d\\}\,\qquad 1\leq r\leq d$

and prove the bound separately on each piece. By symmetry it suffices to treat
$S_{d}$. We abbreviate

$G:=\prod_{r=1}^{d-1}\big{[}1-e_{n}(L(t_{d}-t_{r}))\big{]}^{2}\,,\qquad
H:=\sum_{r=1}^{d-1}\beta_{L}(t_{d}-t_{r}).$

Iterating the identities (3.7)–(3.9), we obtain that for any $j\in P$ such
that $j+2dL\in P$,

$\big{(}D_{t_{1}}\circ\cdots\circ D_{t_{d-1}}f_{t_{r}}\big{)}(j)=0\qquad 1\leq
r\leq d-1$

and otherwise

$\big{(}D_{t_{1}}\circ\cdots\circ D_{t_{d-1}}f_{t_{d}}\big{)}(j)=G\cdot
f_{t_{d}}(j).$

Similarly,

$\big{(}D_{t_{1}}\circ\cdots\circ D_{t_{d-1}}g_{t_{r}}\big{)}(j)=0\qquad 1\leq
r\leq d-1$

and otherwise

$\big{(}D_{t_{1}}\circ\cdots\circ
D_{t_{d-1}}g_{t_{d}}\big{)}(j)=G\cdot\big{(}g_{t_{d}}(j)+H\cdot
f_{t_{d}}(j)\big{)}.$

Fix an arbitrary $v\in S_{d}$. Recognizing the sequences $(f_{t_{r}}(j))_{j\in
P},(g_{t_{r}}(j))_{j\in P}$ as the $2d$ columns of $M_{P}$, we have

$(M_{P}v)_{j}=\sum_{r=1}^{d}v_{r}f_{t_{r}}(j)+v_{r+d}g_{t_{r}}(j).$

Letting $\boldsymbol{D}$ be the matrix associated to the linear operator
$D_{t_{1}}\circ\cdots\circ D_{t_{d-1}}$ on ${\mathbb{C}}^{P}$, we have

$\displaystyle(\boldsymbol{D}M_{P}v)_{j}$
$\displaystyle=v_{d}Gf_{t_{d}}(j)+v_{2d}G(g_{t_{d}}(j)+Hf_{t_{d}}(j))$
$\displaystyle=G\cdot
e_{n}(jt_{d})\big{[}v_{d}+\big{(}{\sqrt{-1}}(j/n)+H\big{)}v_{2d}\big{]}$

for each $j\in P$ such that $j+2dL\in P$. Taking the modulus of each side and
square-summing we obtain

$\displaystyle\sum_{j\in P:j+2dL\in P}|(\boldsymbol{D}M_{P}v)_{j}|^{2}$
$\displaystyle=|G|^{2}\sum_{j\in P:j+2dL\in
P}\big{|}v_{d}+\big{(}{\sqrt{-1}}(j/n)+H\big{)}v_{2d}\big{|}^{2}.$

From (3.3) we have

$G\geq(c{\lambda}_{0})^{2d-2},\qquad H=O(d/{\lambda}_{0}).$

In particular, since $v_{d},v_{2d}$ and $H$ are independent of $j$, and
$|v_{d}|^{2}+|v_{2d}|^{2}\geq 1/d$, the sum on the right hand side of the
previous display is at least $\gg|P|/d^{2}\gg_{d}1$, so

$\sum_{j\in P:j+2dL\in
P}|(\boldsymbol{D}M_{P}v)_{j}|^{2}\gg_{d}{\lambda}_{0}^{2d-2}.$

On the other hand, since the matrix $\boldsymbol{D}$ has
$\ell_{2}(P)\to\ell_{2}(P)$ operator norm $O(d)$, the left hand side is
bounded above by $\ll_{d}\|M_{P}v\|_{2}^{2}$, and we obtain (3.5) as desired.

It only remains to prove (3.4). Consider the submatrices
$M_{P},M_{1+P},\dots,M_{n_{0}+P}$ composed of rows indexed by the shifted
progressions $P,1+P,\dots,n_{0}+P$, respectively. If $n_{0}<L$ then these
submatrices are all disjoint. Moreover, letting $F$ denote the
$2d$-dimensional diagonal matrix with diagonal entries
$e_{n}(t_{1}),\dots,e_{n}(t_{d}),e_{n}(t_{1}),\dots,e_{n}(t_{d})$, we note
that $M_{k+P}$ and $M_{P}F^{k}$ differ by a matrix of norm $O_{d}(k/n)$ (as
they only differing in the dilations by ${\sqrt{-1}}j/n$ in the last $d$
columns). Since $F$ is unitary we have
$\sigma_{2d}(M_{P}F^{k})=\sigma_{2d}(M_{P})\gg_{d}{\lambda}_{0}^{d-1}$, and
taking $n_{0}=c(d){\lambda}_{0}^{d-1}n$ for $c(d)>0$ sufficiently small
depending on $d$, from the triangle inequality we obtain that
$\sigma_{2d}(M_{k+P})\gg_{d}{\lambda}_{0}^{d-1}$ for all $1\leq k\leq n_{0}$.
Since $1+P,\dots,n_{0}+P$ are disjoint, we conclude that for any fixed $v\in
S_{\mathbb{C}}^{2d-1}$,

$\|Mv\|_{2}^{2}\geq\sum_{k=1}^{n_{0}}\|M_{k+P}v\|_{2}^{2}\gg_{d}n_{0}{\lambda}_{0}^{2d-2}\gg_{d}{\lambda}_{0}^{3d-3}n$

giving (3.4) as desired. ∎

##  4 Proof of Proposition 2.7

In this section we combine Theorems 3.2 and 3.4 to prove Proposition 2.7. In
fact we will need the following more general result, which in particular
establishes universality for the joint distribution of the recentered near-
local minimizers $Y_{\alpha_{i}}$ and corresponding near-local minima
$X_{\alpha_{i}}$.

######  Proposition 4.1.

Fix an $m$-tuple of indices $(\alpha_{1},\dots,\alpha_{m})\in[N]^{m}$, and
assume $\boldsymbol{s}=(s_{{\alpha_{1}}},\dots,s_{{\alpha_{m}}})$ is
$n^{\kappa}$-smooth and $1$-spread for some ${\kappa}>0$. Let
$J_{1},\dots,J_{m}\subset{\mathbb{R}}$,
$J^{\prime}_{1},\dots,J^{\prime}_{m}\subseteq[-\pi,\pi]$ be arbitrary compact
intervals with lengths in the range $[n^{-L_{0}},n^{L_{0}}]$ for some
$L_{0}>0$, and denote the event

${\mathcal{E}}=\bigwedge_{i\in[{m}]}\big{\\{}X_{\alpha_{i}}\in
J_{i},\,NY_{\alpha_{i}}\in J_{i}^{\prime}\big{\\}}.$ (4.1)

We have

$\displaystyle\big{|}{\mathbf{P}}({\mathcal{E}})-{\mathbf{P}}_{{\mathcal{N}}_{{\mathbb{R}}}(0,1)}({\mathcal{E}})\big{|}\ll_{{m},{\kappa},L_{0}}\frac{\log^{O(m)}n}{n^{1/2}N^{m}}\prod_{i=1}^{m}|J_{i}||J_{i}^{\prime}|.$
(4.2)

Moreover, if $\boldsymbol{s}$ is $n^{\kappa}$-smooth and ${\lambda}$-spread
for some $\omega(n^{-1/8{m}})\leq{\lambda}\leq 1$, then we have the upper
bounds

${\mathbf{P}}({\mathcal{E}})\ll_{{m},{\kappa},L_{0}}\frac{\log^{O(m)}n}{{\lambda}^{3{m}}N^{{m}}}\prod_{i=1}^{m}|J_{i}||J_{i}^{\prime}|\,,$
(4.3)

and

${\mathbf{P}}_{{\mathcal{N}}_{\mathbb{R}}(0,1)}({\mathcal{E}})\ll_{{m},{\kappa},L_{0}}\frac{1}{{\lambda}^{O({m}^{2})}N^{{m}}}\prod_{i=1}^{m}|J_{i}||J_{i}^{\prime}|\,.$
(4.4)

For the above bounds, the point is that the trivial bound on
${\mathbf{P}}_{{\mathcal{N}}_{{\mathbb{R}}}(0,1)}({\mathcal{E}})$, obtained by
controlling the Gaussian measure by Lebesgue measure, is of order
$N^{-m}\prod_{i=1}^{m}|J_{i}||J_{i}^{\prime}|$ (this will be shown in the
proof, but can also be understood on the heuristic level). For the error in
(4.2) we save $\ll n^{-1/2+\varepsilon}$ on this bound, while in (4.3) we
obtain the same order upper bound for ${\mathbf{P}}({\mathcal{E}})$ up to a
tolerable loss of a factor ${\lambda}^{-3m}\log^{O(m)}n$.

We commence with the proof of Proposition 4.1. Let $K_{*}>0$ to be chosen
sufficiently large and set $\delta=n^{-K_{*}}$. We first describe the event
${\mathcal{E}}$ as a domain in ${\mathbb{R}}^{4{m}}$. Let ${\mathcal{D}}$
denote the annulus

${\mathcal{D}}:=B(0,C_{0}\sqrt{\log n})\setminus
B(0,\log^{-{K_{0}}/2}n)\subset{\mathbb{R}}^{2}.$

For ${\mathbf{b}}=(b,b^{\prime})\in{\mathbb{R}}^{2}$ we write
${\mathbf{b}}^{\perp}:=(b^{\prime},-b)$, and define the rectangles

$T_{i}({\mathbf{b}})=\bigg{\\{}{\mathbf{a}}\in{\mathbb{R}}^{2}:\frac{{\mathbf{a}}\cdot{\mathbf{b}}^{\perp}}{\|{\mathbf{b}}\|_{2}}\in\frac{1}{n}\cdot
J_{i}\;,\;\;-\frac{{\mathbf{a}}\cdot{\mathbf{b}}}{\|{\mathbf{b}}\|_{2}^{2}}\in\frac{n}{N}\cdot
J_{i}^{\prime}\bigg{\\}}\,,\,\qquad 1\leq i\leq{m},$ (4.5)

which have sides of length $n\|{\mathbf{b}}\|_{2}|J_{i}^{\prime}|/N$ and
$|J_{i}|/n$ in the direction of ${\mathbf{b}}$ and ${\mathbf{b}}^{\perp}$,
respectively. (Here we write $C\cdot J_{i}$ for the dilation of $J_{i}$ by a
factor $C$.) Let

$U_{i}=\Big{\\{}(a,a^{\prime},b,b^{\prime})=({\mathbf{a}},{\mathbf{b}})\in{\mathbb{R}}^{4}:{\mathbf{b}}\in{\mathcal{D}},\;{\mathbf{a}}\in
T_{i}({\mathbf{b}})\Big{\\}}\,,\qquad{\mathcal{U}}=\prod_{i=1}^{m}U_{i}\,.$
(4.6)

Abbreviating henceforth

$\widetilde{S}:=\frac{1}{\sqrt{2n+1}}S_{n}(\boldsymbol{t}),$ (4.7)

one sees that the left hand sides of (4.2) and (4.3) can be expressed as
$|{\mathbf{P}}(\widetilde{S}\in{\mathcal{U}})-{\mathbf{P}}(\Gamma\in{\mathcal{U}})|$
and ${\mathbf{P}}(\widetilde{S}\in{\mathcal{U}})$, respectively.

From the dimensions of the rectangles $T_{i}({\mathbf{b}})$ we have from
Fubini’s theorem that

$m_{\operatorname{{Leb}}}(U_{i})=\int_{\mathcal{D}}m_{\operatorname{{Leb}}}(T_{i}({\mathbf{b}}))d{\mathbf{b}}=\frac{\Delta}{N}|J_{i}||J^{\prime}_{i}|$
(4.8)

where we denote

$\Delta:=\int_{\mathcal{D}}\|{\mathbf{b}}\|d{\mathbf{b}}\sim\frac{2\pi
C_{0}}{3}\log^{3/2}n.$ (4.9)

Thus,

$m_{\operatorname{{Leb}}}({\mathcal{U}})=(\Delta/N)^{m}\prod_{i=1}^{m}|J_{i}||J_{i}^{\prime}|=\frac{\log^{O(m)}n}{N^{m}}\prod_{i=1}^{m}|J_{i}||J_{i}^{\prime}|.$
(4.10)

For the measure of ${\mathcal{U}}$ under the law of $\Gamma$, recall from
Lemma 3.6 that the norm of the inverse of the covariance matrix of $\Gamma$
has operator norm of size $O({\lambda}^{-3m})$, and hence determinant of size
$O({\lambda}^{-O(m^{2})})$. By controlling the conditional density of $\Gamma$
in directions $({\mathbf{a}}_{1},\dots,{\mathbf{a}}_{m})$ for fixed
$({\mathbf{b}}_{1},\dots,{\mathbf{b}}_{m})$ by the Lebesgue measure, and then
integrating over ${\mathcal{D}}^{m}$ under the marginal Gaussian measure, we
get

${\mathbf{P}}(\Gamma\in{\mathcal{U}})\ll_{{m},{\kappa},L_{0}}\frac{1}{{\lambda}^{O({m}^{2})}N^{{m}}}\prod_{i=1}^{m}|J_{i}||J_{i}^{\prime}|,$
(4.11)

giving (4.4) as desired.

We next note that the corners of the rectangles $T_{i}({\mathbf{b}})$ are
$n^{O(L_{0}+1)}$-Lipschitz functions of ${\mathbf{b}}\in{\mathcal{D}}$. From
this it follows that if $K_{*}$ is sufficiently large depending on $L_{0}$ and
$m$, we can find sets
${\mathcal{U}}_{-}\subset{\mathcal{U}}\subset{\mathcal{U}}_{+}$ such that
${\mathcal{U}}_{-}$ and ${\mathcal{U}}_{+}\setminus{\mathcal{U}}_{-}$ are
unions of cubes in ${\mathbb{R}}^{4m}$ of side length $\delta$ with disjoint
interiors, and such that
$m_{\operatorname{{Leb}}}({\mathcal{U}}_{+}\setminus{\mathcal{U}}_{-})\leq
n^{-100}m_{\operatorname{{Leb}}}({\mathcal{U}})$ (say).

The bound (4.3) now follows by covering each cube in ${\mathcal{U}}_{+}$ with
balls of bounded overlap and applying the union bound, Theorem 3.4, and
(4.10).

For (4.2), we bound

$|{\mathbf{P}}(\widetilde{S}\in{\mathcal{U}})-{\mathbf{P}}(\Gamma\in{\mathcal{U}})|\leq{\mathbf{P}}(\widetilde{S}\in{\mathcal{U}}_{+}\setminus{\mathcal{U}}_{-})+{\mathbf{P}}(\Gamma\in{\mathcal{U}}_{+}\setminus{\mathcal{U}}_{-})+\sum_{Q}|{\mathbf{P}}(\widetilde{S}\in
Q)-{\mathbf{P}}(\Gamma\in Q)|$

where the sum runs over the cubes comprising ${\mathcal{U}}_{-}$. Using the
union bound and Theorem 3.4 as we did for ${\mathcal{U}}_{+}$, the first two
terms above are of size

$\ll m_{\operatorname{{Leb}}}({\mathcal{U}}_{+}\setminus{\mathcal{U}}_{-})\ll
n^{-100}m_{\operatorname{{Leb}}}({\mathcal{U}}).$

For the sum over $Q$, use Theorem 3.2 to bound each term by
$\ll_{m,\kappa,K_{*}}n^{-1/2}m_{\operatorname{{Leb}}}(Q)$. Altogether we have

$|{\mathbf{P}}(\widetilde{S}\in{\mathcal{U}})-{\mathbf{P}}(\Gamma\in{\mathcal{U}})|\ll_{m,\kappa,K_{*}}n^{-1/2}m_{\operatorname{{Leb}}}({\mathcal{U}})$

and the claim now follows from (4.10). This concludes the proof of Proposition
4.1. ∎

##  5 Proof of Proposition 2.5 for the real-valued case (moment comparison)

We condition on ${\mathcal{G}}_{2}({K_{0}}/2)$ throughout the proof. As
remarked before, in the real-valued case it suffices to work with
$x_{\alpha}\in[0,\pi]$ because $P_{n}(-x)=\overline{P_{n}}(x)$. We allow
implied constants to depend on ${m}$ and $0pt$ without indication. Recall also
that ${\kappa}_{0}$ in the definition (2.7) of ${{\mathcal{M}}}^{\sharp}_{n}$
is an absolute constant. For
$\boldsymbol{\alpha}=(\alpha_{1},\dots,\alpha_{m})\in[N]^{m}$ we denote events

${\mathcal{E}}(\boldsymbol{\alpha}):=\bigg{\\{}\bigwedge_{i\in[{m}]}|X_{\alpha_{i}}|\leq
0pt\bigg{\\}}\,.$

We have

$\displaystyle{\mathbf{E}}\Big{(}{{\mathcal{M}}}^{\sharp}_{n}\big{(}[-0pt,0pt]\big{)}^{m}\Big{)}$
$\displaystyle=\sum_{\boldsymbol{\alpha}\in
E}{\mathbf{P}}({\mathcal{E}}(\boldsymbol{\alpha}))=\sum_{\boldsymbol{\alpha}\in
E^{\prime}}{\mathbf{P}}({\mathcal{E}}(\boldsymbol{\alpha}))+\sum_{\boldsymbol{\alpha}\in
E\setminus E^{\prime}}{\mathbf{P}}({\mathcal{E}}(\boldsymbol{\alpha}))$ (5.1)

where

$\displaystyle E$
$\displaystyle:=\big{\\{}\boldsymbol{\alpha}=(\alpha_{1},\dots,\alpha_{m})\in[N/2]^{m}:x_{\alpha_{1}},\dots,x_{\alpha_{m}}\notin{E_{\operatorname{{bad}}}}({\kappa}_{0})\big{\\}}\,,$
$\displaystyle E^{\prime}$ $\displaystyle:=\big{\\{}\boldsymbol{\alpha}\in
E:|x_{\alpha_{i}}-x_{\alpha_{j}}|>4\pi/n\;\forall 1\leq
i<j\leq{m}\big{\\}}\,.$

Note that if $x,x^{\prime}\in[0,\pi]$ such that
$|\frac{x-x^{\prime}}{2\pi}|\geq\frac{\lambda}{n}$ then we also have
$\frac{\lambda}{n}\leq\frac{x+x^{\prime}}{2\pi}\leq 1-\frac{\lambda}{n}$.
Hence within $E^{\prime}$ the angles are $1$-spread and by Proposition 2.7

$\bigg{|}\sum_{\boldsymbol{\alpha}\in
E^{\prime}}{\mathbf{P}}\big{(}{\mathcal{E}}(\boldsymbol{\alpha})\big{)}-\sum_{\boldsymbol{\alpha}\in
E^{\prime}}{\mathbf{P}}_{{\mathcal{N}}_{{\mathbb{R}}}(0,1)}\big{(}{\mathcal{E}}(\boldsymbol{\alpha})\big{)}\bigg{|}\leq
N^{{m}}o(N^{-m})=o(1).$

It only remains to bound the sum over $\boldsymbol{\alpha}\in E\setminus
E^{\prime}$.

By Lemma 2.2, under ${\mathcal{G}}_{2}({K_{0}}/2)$, it suffices to consider
$m$-tuples of the form

$(\alpha_{1},\dots,\alpha_{{m}-k},\alpha_{1}+1,\alpha_{2}+1,\dots,\alpha_{k}+1)$
(5.2)

consisting of $k$ pairs of points $(\alpha_{l},\alpha_{l}+1)$ that are
immediate neighbors, for some $0\leq k\leq{m}/2$, while the ${m}-k$ points
$x_{\alpha_{1}},\dots,x_{\alpha_{{m}-k}}$ are separated by at least
$4\pi/(n\log^{3{K_{0}}}n)$ in $[0,\pi]$. Note also that by the remark above we
also have $\frac{x_{\alpha_{i}}+x_{\alpha_{j}}}{2\pi}\geq
1/(n\log^{3{K_{0}}}n)$.

We divide this class of such $\boldsymbol{\alpha}$ into two sets
$E_{1},E_{2}$, where $E_{1}$ is the set of $\boldsymbol{\alpha}\in E\setminus
E^{\prime}$ of the form (5.2) (possibly with $k=0$) such that
$|x_{\alpha_{i}}-x_{\alpha_{j}}|\leq 4\pi/n$ for some $1\leq i<j\leq{m}-k$,
and $E_{2}$ is the set of $\boldsymbol{\alpha}\in E\setminus E^{\prime}$ of
the form (5.2) with $k\geq 1$ and $|x_{\alpha_{i}}-x_{\alpha_{j}}|>4\pi/n$ for
all $1\leq i<j\leq{m}-k$.

For the sum over $E_{1}$, we have $|E_{1}|=O(N^{{m}-k}/n)$ since there are
$O(N/n)$ options for the close point with all others fixed. As the points
$x_{\alpha_{1}},\dots,\dots,x_{\alpha_{{m}-k}}$ are separated by at least
$4\pi/(n\log^{3{K_{0}}}n)$, from the upper bound (4.3) in Proposition 4.1 with
$J_{i}\equiv[-0pt,0pt]$ and $J_{i}^{\prime}\equiv[-\pi,\pi]$, we have

$\displaystyle\sum_{\boldsymbol{\alpha}\in
E_{1}}{\mathbf{P}}\big{(}{\mathcal{E}}(\boldsymbol{\alpha})\big{)}\ll(N^{{m}-k}/n)\times
N^{-{m}}0pt^{m}\log^{O(K_{0}m)}n\ll\frac{1}{n}\log^{O(m)}n=o(1).$

For the sum over $E_{2}$, by Lemma 2.2, under ${\mathcal{G}}_{2}({K_{0}}/2)$
we have the containment of events

$\big{\\{}|X_{\alpha_{i}}|\leq 0pt\;,\;|X_{\alpha_{i}+1}|\leq
0pt\big{\\}}\subset\bigg{\\{}|X_{\alpha_{i}}|\leq
0pt\;,\;Y_{\alpha_{i}}\in\Big{[}\frac{\pi}{N}-\frac{\pi}{N\log^{{K_{0}}/4}n},\frac{\pi}{N}\Big{]}\bigg{\\}}\,,$

so for each such $\boldsymbol{\alpha}$ we can bound

${\mathbf{P}}\big{(}{\mathcal{E}}(\boldsymbol{\alpha})\big{)}\leq{\mathbf{P}}\bigg{(}\,Y_{\alpha_{1}}\in\Big{[}\frac{\pi}{N}-\frac{\pi}{N\log^{{K_{0}}/4}n},\frac{\pi}{N}\Big{]}\,,\,\bigwedge_{i\in[{m}-k]}|X_{\alpha_{i}}|\leq
0pt\,\bigg{)}.$

Applying (4.2) with ${m}-k$ in place of ${m}$, ${\lambda}=1/2$ (say),
$J_{i}\equiv[-0pt,0pt]$, $J_{1}^{\prime}=[\pi(1-\log^{-{K_{0}}/4}n),\pi]$, and
$J_{i}^{\prime}=[-\pi,\pi]$ for $2\leq i\leq{m}-k$, the right hand side above
is bounded by

${\mathbf{P}}_{{\mathcal{N}}_{\mathbb{R}}(0,1)}\bigg{(}\,Y_{\alpha_{1}}\in\Big{[}\frac{\pi}{N}-\frac{\pi}{N\log^{{K_{0}}/4}n},\frac{\pi}{N}\Big{]}\,,\,\bigwedge_{i\in[{m}-k]}|X_{\alpha_{i}}|\leq
0pt\,\bigg{)}+o(N^{-(m-k)}).$

Finally, we apply (4.4) to bound the first term above by $o(N^{-(m-k)})$.
Combining the preceding displays and summing over $\boldsymbol{\alpha}\in
E_{2}$ gives

$\displaystyle\sum_{\boldsymbol{\alpha}\in
E_{2}}{\mathbf{P}}\big{(}{\mathcal{E}}(\boldsymbol{\alpha})\big{)}=o(1).$

We have thus shown that the sum over $\boldsymbol{\alpha}\in E\setminus
E^{\prime}$ in (5.1) is $o(1)$, which completes the proof of Proposition 2.5.∎

##  6 Proof of Theorem 1.2 (main result)

We fix $\kappa=\kappa_{0}$ as in Lemma 2.4, and let $\tau>0$ be arbitrary. As
in the previous section we allow implied constants to depend on ${m}$ and
$\tau$. It follows from Proposition 2.5 that

$\lim_{n\to\infty}\Big{|}{\mathbf{P}}\big{(}{{{\mathcal{M}}}^{\sharp}_{{{\mathcal{N}}_{{\mathbb{R}}}(0,1)}}}([-0pt,0pt])=0\big{)}-{\mathbf{P}}\big{(}{{\mathcal{M}}}^{\sharp}([-0pt,0pt])=0\big{)}\Big{|}=0.$

On the other hand, by Theorem 1.1 and Lemma 2.4,

$\lim_{n\to\infty}\bigg{|}{\mathbf{P}}_{{{\mathcal{N}}_{{\mathbb{R}}}(0,1)}}\Big{(}m_{n}>\frac{0pt}{n}\Big{)}-{\mathbf{P}}_{{{\mathcal{N}}_{{\mathbb{R}}}(0,1)}}\Big{(}{{\mathcal{M}}}^{\sharp}([-0pt,0pt])=0\Big{)}\bigg{|}=0$

and hence it suffices to show

$\lim_{n\to\infty}\bigg{|}{\mathbf{P}}\Big{(}m_{n}>\frac{0pt}{n}\Big{)}-{\mathbf{P}}\Big{(}{{\mathcal{M}}}^{\sharp}([-0pt,0pt])=0\Big{)}\bigg{|}=0.$

To this end, recall that on the event ${\mathcal{G}}_{2}({K_{0}})$,

$|P(x)-F_{\alpha}(x)|\leq
N^{-2}\sup_{x\in[-\pi,\pi]}|P^{\prime\prime}(x)|\leq\frac{\log^{3{K_{0}}}n}{n^{2}}$
(6.1)

for all $x\in I_{\alpha}$. By Lemma 2.4 we have

$\displaystyle\bigg{|}{\mathbf{P}}\Big{(}m_{n}>\frac{0pt}{n}\Big{)}-{\mathbf{P}}\Big{(}{{\mathcal{M}}}^{\sharp}([-0pt,0pt])=0\Big{)}\bigg{|}$
$\displaystyle\qquad\qquad\leq{\mathbf{P}}\Big{(}m_{n}>\frac{0pt}{n}\;,\;{{\mathcal{M}}}^{\sharp}([-0pt,0pt])\geq
1\Big{)}+{\mathbf{P}}\Big{(}m_{n}\leq\frac{0pt}{n}\;,\;{{\mathcal{M}}}^{\sharp}([-0pt,0pt])=0\Big{)}$
$\displaystyle\qquad\qquad\leq\sum_{\alpha\in[N]:x_{\alpha}\notin{E_{\operatorname{{bad}}}}({\kappa})}{\mathbf{P}}\Big{(}{\mathcal{G}}_{2}({K_{0}})\,\wedge\,|X_{\alpha}|<0pt\,\wedge\,\min_{x\in
I_{\alpha}}|P(x)|\geq 0pt/n\Big{)}$
$\displaystyle\qquad\qquad\qquad\qquad+\sum_{\alpha\in[N]:x_{\alpha}\notin{E_{\operatorname{{bad}}}}({\kappa})}{\mathbf{P}}\Big{(}{\mathcal{G}}_{2}({K_{0}})\,\wedge\,|X_{\alpha}|\geq
0pt\,\wedge\,\min_{x\in I_{\alpha}}|P(x)|<0pt/n\Big{)}+o(1)$
$\displaystyle\qquad\qquad\leq\sum_{\alpha\in[N]:x_{\alpha}\notin{E_{\operatorname{{bad}}}}({\kappa})}{\mathbf{P}}\bigg{(}|X_{\alpha}|\in\bigg{[}0pt-\frac{\log^{3{K_{0}}}n}{n},0pt+\frac{\log^{3{K_{0}}}n}{n}\bigg{]}\bigg{)}+o(1),$

where we used the definition of $X_{\alpha}$ and (6.1) in the last estimate.

Applying the bound (4.3) of Proposition 4.1 with ${m}=1$,
$J_{1}=[0pt-n^{-1}\log^{3{K_{0}}}n,0pt+n^{-1}\log^{3{K_{0}}}n]$,
$J_{1}^{\prime}=[-\pi,\pi]$, and ${\lambda}=1$, say (with a single point
$x_{\alpha}$ being trivially ${\lambda}$-spread), we have

${\mathbf{P}}\bigg{(}X_{\alpha}\in\bigg{[}0pt-\frac{\log^{3{K_{0}}}n}{n},0pt+\frac{\log^{3{K_{0}}}n}{n}\bigg{]}\bigg{)}\ll\frac{\log^{3{K_{0}}}n}{nN}$

for each $\alpha$ with $x_{\alpha}\notin{E_{\operatorname{{bad}}}}({\kappa})$,
as well as the same bound for the event with $X_{\alpha}$ replaced by
$-X_{\alpha}$. From the union bound and summing over $\alpha$ we conclude

$\bigg{|}{\mathbf{P}}\Big{(}m_{n}>\frac{0pt}{n}\Big{)}-{\mathbf{P}}\Big{(}{{\mathcal{M}}}^{\sharp}([-0pt,0pt])=0\Big{)}\bigg{|}\ll\frac{\log^{3{K_{0}}}n}{n}+o(1)=o(1)$

as desired.

##  7 Proof of Theorem 3.4

Fix $\boldsymbol{t}$ as in the theorem statement. Recall the notation
$S_{n}=S_{n}(\boldsymbol{t})$ (we henceforth suppress $\boldsymbol{t}$) and
$\boldsymbol{w}_{j}$ from (3.2) and (3.1). Let $t_{0}=\delta^{-1}$ and let
$\phi_{j}$ denote the characteristic function of $\xi_{j}\boldsymbol{w}_{j}$.
By a standard we can bound the small ball probability by

${\mathbf{P}}(\frac{1}{\sqrt{2n+1}}S_{n}\in B(w,\delta))\leq
C_{m}(\frac{n}{t_{0}^{2}})^{4{m}/2}\int_{{\mathbb{R}}^{4{m}}}\prod_{j=-n}^{n}\phi_{j}(u)e^{-\frac{n\|u\|_{2}^{2}}{2t_{0}^{2}}}du=:J_{1}+J_{2}+J_{3},$

where in $J_{1},J_{2},J_{3}$ the integral is restricted to the ranges
$\|u\|_{2}\leq r_{0}=O(1)$, $r_{0}\leq\|u\|_{2}\leq R=n^{K_{*}}$, and
$\|u\|_{2}>R$, respectively for $K_{*}>0$ to be chosen sufficiently large.

For $J_{1}$, from (9.1) and (9.2) below we can bound

$\bigg{|}\prod_{j=-n}^{n}\phi_{j}(u)\bigg{|}\leq\exp\bigg{(}-c\inf_{a_{1}\leq|a|\leq
a_{2}}\sum_{j}\|a\langle{\boldsymbol{w}}_{j},u/2\pi\rangle\|_{{\mathbb{R}}/{\mathbb{Z}}}^{2}\bigg{)}.$

Thus, if $r_{0}$ is sufficiently small, then we have
$\|a\langle{\boldsymbol{w}}_{j},u/2\pi\rangle\|_{{\mathbb{R}}/{\mathbb{Z}}}=|a|\|\langle{\boldsymbol{w}}_{j},u/2\pi\rangle\|_{2}$,
and so from Lemma 3.6 we have

$\sum_{j}\|a\langle{\boldsymbol{w}}_{j},u/2\pi\rangle\|_{{\mathbb{R}}/{\mathbb{Z}}}^{2}\geq
c^{\prime}n\|u\|_{2}^{2}\min({\lambda},1)^{6{m}-3}.$

Hence

$\displaystyle J_{1}$
$\displaystyle=C_{m}(\frac{n}{t_{0}^{2}})^{2{m}}\int_{\|u\|_{2}\leq
r_{0}}\prod_{j}\phi_{j}(u)e^{-\frac{n\|u\|_{2}^{2}}{2t_{0}^{2}}}du$
$\displaystyle\leq C_{m}(\frac{n}{t_{0}^{2}})^{2{m}}\int_{\|u\|_{2}\leq
r_{0}}e^{-\frac{n\|u\|_{2}^{2}}{2t_{0}^{2}}-c^{\prime}n\|u\|_{2}^{2}{\lambda}^{6{m}-3}}du$
$\displaystyle=O_{m}(\frac{1}{{\lambda}^{3{m}}(t_{0}^{2}+1)^{2{m}}})=O_{m}({\lambda}^{-3{m}}\delta^{4{m}}).$

For $J_{2}$, recall by Theorem 3.1 that for $r_{0}\leq\|u\|_{2}\leq
R=n^{K_{*}}$ we have

$|\prod_{j=-n}^{n}\phi_{j}(u)|=O(e^{-\log^{2}n}).$

Thus

$\displaystyle J_{2}$
$\displaystyle=C_{m}(\frac{n}{t_{0}^{2}})^{2{m}}\int_{r_{0}\leq\|u\|_{2}\leq
R}\prod_{j=-n}^{n}\phi_{j}(u)e^{-\frac{n\|u\|_{2}^{2}}{2t_{0}^{2}}}du$
$\displaystyle\leq
C_{m}(\frac{n}{t_{0}^{2}})^{2{m}}\int_{r_{0}\leq\|u\|_{2}\leq
R}e^{-\log^{2}n}e^{-\frac{n\|u\|_{2}^{2}}{2t_{0}^{2}}}du$
$\displaystyle\ll_{m}n^{O_{{m},K_{*}}(1)}e^{-\log^{2}n}\ll_{{m},K}e^{-\frac{1}{2}\log^{2}n}.$

For $J_{3}$, we have

$\displaystyle J_{3}$
$\displaystyle=C_{m}(\frac{n}{t_{0}^{2}})^{4{m}/2}\int_{\|u\|_{2}\geq
n^{K_{*}}}\prod_{j=-n}^{n}\phi_{j}(u)e^{-\frac{n\|u\|_{2}^{2}}{2t_{0}^{2}}}du=O_{m}(e^{-n})$

for $K_{*}$ sufficiently large.

##  8 Proof of Theorem 3.2

For the proof we make use of a quantitative Edgeworth expansion for the
distribution of $S_{n}=S_{n}(\boldsymbol{t})$ (we will suppress the dependence
of $S_{n}$ on $\boldsymbol{t}$ in much of what follows). Our treatment is
similar to [DNN]. Let

$V_{n}:=\frac{1}{2n+1}\sum_{j=-n}^{n}\boldsymbol{w}_{j}\boldsymbol{w}_{j}^{\mathsf{T}}.$
(8.1)

be the covariance matrix of $S_{n}/\sqrt{2n+1}$. Let $\widetilde{Q}_{n}$
denote the distribution of $S_{n}/\sqrt{2n+1}$, and let $\widetilde{Q}_{n}(x)$
denote the cumulative distribution function for this distribution. The theorem
below shows that $\widetilde{Q}_{n}$ is asymptotically
$\widetilde{Q}_{n,\infty}$, where

$\widetilde{Q}_{n,\ell}:=\sum_{r=0}^{\ell-2}n^{-r/2}T_{r}(-\Phi_{0,V_{n}},\\{\overline{\chi}_{\nu}\\}),\qquad\ell\geq
2,$ (8.2)

for (signed) measures $T_{r}(-\Phi_{0,V_{n}},\\{\overline{\chi}_{\nu}\\})$ to
be defined below. For convenience, the density of $\widetilde{Q}_{n,\ell}$ is
denoted by $Q_{n,\ell}$ while the density of $\widetilde{Q}_{n}$ is denoted by
$Q_{n}$.

Let $W$ be the standard Gaussian vector in ${\mathbb{R}}^{4{m}}$. For any
covariance matrix $V$, $V^{1/2}W$ is the Gaussian random vector in
${\mathbb{R}}^{4{m}}$ with mean zero and covariance $V$. Let $\phi_{0,V}$
denote the density of its distribution and let $\Phi_{0,V}$ denote the
cumulative distribution function. If $V$ is the identity matrix then we simply
write $\phi$ and $\Phi$, respectively. Recall that the cumulants of a random
vector $X$ in ${\mathbb{R}}^{4{m}}$ are the coefficients in the following
formal power series expansion

$\log{\mathbf{E}}[e^{z\cdot
X}]=\sum_{\nu\in{\mathbf{N}}^{d}}\frac{\chi_{\nu}z^{\nu}}{|\nu|!}\,,\qquad
z\in{\mathbb{C}}^{4{m}}.$ (8.3)

From the independence of the random coefficients $\xi_{j}$, it follows that
the cumulants of $S_{n}$ are the sum of the corresponding cumulants of
$\xi_{j}\boldsymbol{w}_{j}$, which in turn are polynomials in the moments of
$\xi$ and the entries of $\boldsymbol{w}_{j}$. Let
$\overline{\chi}_{\nu}:=\chi_{\nu}(S_{n})/(2n+1)$, which is the average of
cumulants of $\xi_{j}\boldsymbol{w}_{j},-n\leq j\leq n$.

Note that cumulants of $V_{n}^{1/2}W$ match the cumulants of
$S_{n}/\sqrt{2n+1}$ for any $|\nu|\leq 2$, while the higher order cumulants of
the Gaussian vector $V_{n}^{1/2}W$ vanish. Therefore,

$\displaystyle\log{\mathbf{E}}[e^{z\cdot(S_{n}/\sqrt{2n+1})}]$
$\displaystyle=$
$\displaystyle\log{\mathbf{E}}[e^{z\cdot(V_{n}^{1/2}W)}]+\sum_{\nu\in{\mathbf{N}}^{d}:|\nu|\geq
3}(n\overline{\chi}_{\nu})\frac{z^{\nu}}{|\nu|!}n^{-|\nu|/2}$ $\displaystyle=$
$\displaystyle\log{\mathbf{E}}[e^{z\cdot V_{n}^{1/2}W}]+\sum_{\ell\geq
1}(\sum_{\nu\in{\mathbf{N}}^{d}:|\nu|=\ell+2}\overline{\chi}_{\nu}\frac{z^{\nu}}{|\nu|!})n^{-\ell/2}.$

Letting
$\overline{\chi}_{\ell}(z)=\ell!\sum_{\nu\in{\mathbf{N}}^{4{m}}:|\nu|=\ell}\overline{\chi}_{\nu}z^{\nu}/|\nu|!$
for all $z\in{\mathbb{C}}^{4{m}}$, we obtain

$\displaystyle{\mathbf{E}}[e^{z\cdot(S_{n}/\sqrt{2n+1})}]/{\mathbf{E}}[e^{z\cdot
V_{n}^{1/2}W}]$ $\displaystyle=$ $\displaystyle\exp[\sum_{\ell\geq
1}\frac{\overline{\chi}_{\ell+2}(z)}{(\ell+2)!}n^{-\ell/2}]$ $\displaystyle=$
$\displaystyle\sum_{m\geq 0}\frac{1}{m!}\Big{(}\sum_{\ell\geq
1}\frac{\overline{\chi}_{\ell+2}(z)}{(\ell+2)!}n^{-\ell/2}\Big{)}^{m}$
$\displaystyle=$ $\displaystyle\sum_{\ell\geq
0}\widetilde{T}_{\ell}n^{-\ell/2},$

where $\widetilde{T}_{\ell}$ is obtained by grouping terms of the same order
$n^{-\ell/2}$. It is clear that $\widetilde{T}_{\ell}$ depends only on $z$ and
the average cumulants $\overline{\chi}_{\nu},|\nu|\leq\ell+2$. We will write
$\widetilde{T}_{\ell}(z,\\{\overline{\chi}_{\nu}\\})$ to stress this
dependence. Replacing $z$ by $iz$, we obtain the following expansion for the
characteristic function of $S_{n}/\sqrt{2n+1}$:

$\displaystyle{\mathbf{E}}[e^{iz\cdot(S_{n}/\sqrt{2n+1})}]$ $\displaystyle=$
$\displaystyle{\mathbf{E}}[e^{iz\cdot V_{n}^{1/2}W}]\sum_{\ell\geq
0}\widetilde{T}_{\ell}(iz,\\{\overline{\chi}_{\nu}\\})n^{-\ell/2}.$

Next, let $D=(D_{1},\dots,D_{4{m}})$ be the partial derivative operator and
let $\widetilde{T}_{\ell}(-D,\\{\overline{\chi}_{\nu}\\})$ be the differential
operator obtained by formally replacing all occurences of $iz$ by $-D$ inside
$\widetilde{T}_{\ell}(iz,\\{\overline{\chi}_{\nu}\\})$. We define the signed
measures $T_{\ell}(-\Phi_{0,V_{n}},\\{\overline{\chi}_{\nu}\\})$ in (8.2) to
have the following density with respect to the Lebesgue measure:

$T_{\ell}(-\phi_{0,V_{n}},\\{\overline{\chi}_{\nu}\\})(x):=\Big{(}\widetilde{T}_{\ell}(-D,\\{\overline{\chi}_{\nu}\\})\phi_{0,V_{n}}\Big{)}(x).$

The following result gives a quantitative comparison between
$\widetilde{Q}_{n}$ and $\widetilde{Q}_{n,\ell}$; cf. also [DNN, Theorem 4.1].
For convenience of notation, for each $\ell>0$, let

$\rho_{\ell}:=\frac{1}{n}\sum_{-n\leq j\leq
n}\|\boldsymbol{w}_{j}\|_{2}^{\ell}\cdot{\mathbf{E}}|\xi|^{\ell}.$

Thus $\rho_{\ell}=O_{\ell,{m}}({\mathbf{E}}|\xi|^{\ell})=O_{\ell,{m}}(1)$ if
$\xi$ is sub-Gaussian. To stay slightly more general, here we only assume that
$\xi$ has bounded moments up to some sufficiently large order. For a given
measurable function $f:{\mathbb{R}}^{4{m}}\to{\mathbb{R}}$, define

$M_{\ell}(f):=\sup_{x\in{\mathbb{R}}^{4{m}}}\frac{|f(x)|}{1+\|x\|_{2}^{\ell}}.$

######  Theorem 8.1 (Edgeworth expansion).

Assume ${\mathbf{E}}|\xi|^{\ell+4{m}+1}<\infty$ for some $\ell\geq 4$. Let
$f:{\mathbb{R}}^{4{m}}\to{\mathbb{R}}$ be a measurable function such that
$M_{\ell}(f)<\infty$. Suppose that $\boldsymbol{t}=(t_{1},\dots,t_{m})$ is
$n^{\kappa}$-smooth and $1$-spread for some ${\kappa}>0$. Then for any fixed
$K_{*}>0$ and any $n^{-K_{*}}\leq\varepsilon\leq 1$,

$\displaystyle|\int f(x)d\widetilde{Q}_{n}(x)-\int
f(x)d\widetilde{Q}_{n,\ell}(x)|$ $\displaystyle\leq$ $\displaystyle
CM_{\ell}(f)(n^{-(\ell-1)/2}+e^{-\log^{2}n})+\overline{\omega}_{f}(2\varepsilon:\sum_{r=0}^{\ell+4{m}-2}n^{-r/2}T_{r}(-\phi_{0,V_{n}}:\\{\overline{\chi}_{\nu}\\})$

where for a density $\phi$,

$\overline{\omega}_{f}(\varepsilon:\phi)=\int(\sup_{y\in
B(x,\varepsilon)}f(y)-\inf_{y\in B(x,\varepsilon)}f(y))d\phi(x),$

for some $C=C(\\{\rho_{k},k\leq\ell\\},{\kappa},K_{*})>0$.

###### Proof of Theorem 8.1.

This follows from [DNN, Section 4] (which in turns follows the approach of
[BR10] with some important modifications, see also [BCP19]). For completeness
we sketch the proof below. Let $d=4m$. For convenience, we assume that
$\varepsilon=n^{-K_{*}}$ and denote

$\widetilde{H}_{n}=\widetilde{Q}_{n}-\widetilde{Q}_{n,\ell},$

and let $H_{n}$ be its density. As usual the characteristic function of
$H_{n}$ is
$\widehat{H_{n}}(\eta)=\int_{{\mathbb{R}}^{d}}e^{it\cdot\eta}\widetilde{H}_{n}(dt)$.

Let $\widetilde{K}$ be a probability measure supported inside the unit ball
$B(0,1)=\\{x\in{\mathbb{R}}^{d}:\|x\|\leq 1\\}$ (whose density is denoted by
$K$) such that its characteristic function $\widehat{K}(\eta)$ satisfies

$|D^{\alpha}\widehat{K}(\eta)|=O(e^{-\|\eta\|_{2}^{1/2}}),\quad|\alpha|\leq\ell+d+1.$
(8.4)

Such a measure could be constructed using elementary arguments, see for
instance [BR10, Section 10]. We then let $\widetilde{K}_{\epsilon}$ be the
$\epsilon$-dilation of $K$, namely
$\widetilde{K}_{\epsilon}(A)=\widetilde{K}(\epsilon^{-1}A)$ and
$\epsilon^{-1}A:=\\{x/\epsilon:x\in A\\}$ for all measurable $A$. Some simple
computation yields

$\displaystyle|\int f(y)d\widetilde{H}_{n}(y)|$ $\displaystyle\leq$
$\displaystyle
C_{\ell}M_{\ell}(f)\int(1+\|t\|_{2})^{\ell}|H_{n}*K_{\epsilon}|(t)dt+\bar{\omega}_{f}(2\varepsilon:|\widetilde{Q}_{n,\ell}|)$
$\displaystyle=$ $\displaystyle
O\Big{(}\max\\{\int|D^{\alpha}(\widehat{H_{n}})(\eta)D^{\beta}(\widehat{K_{\epsilon}})(\eta)|d\eta:\
\ |\alpha|+|\beta|\leq\ell+d+1\\}\Big{)}.$

Following [BR10] (see [DNN, Corollary 4.3] for a different proof) we can show
that for some $c_{1}>0$ sufficiently small we have

$\displaystyle\int_{\|\eta\|_{2}\leq
c_{1}\sqrt{n}}|D^{\alpha}\widehat{H_{n}}(\eta)D^{\beta}\widehat{K_{\epsilon}}(\eta)|d\eta$
$\displaystyle=$ $\displaystyle O\Big{(}\int_{\|\eta\|_{2}\leq
c_{1}\sqrt{n}}|D^{\alpha}\widehat{H_{n}}(\eta)|d\eta\Big{)}$ $\displaystyle=$
$\displaystyle O(n^{-(\ell+d-1)/2}).$

It thus remains to consider the range $\|\eta\|_{2}\geq c_{1}\sqrt{n}$. We use
triangle inequality to estimate (where $Q_{n}$ is the density of
$\widetilde{Q}_{n}$)

$\displaystyle\int_{\|\eta\|_{2}\geq
c_{1}\sqrt{n}}|D^{\alpha}\widehat{H}_{n}(t)D^{\beta}\widehat{K}_{\varepsilon}|d\eta$
$\displaystyle\leq\int_{\|\eta\|_{2}\geq
c_{1}\sqrt{n}}|D^{\alpha}\widehat{Q}_{n}(t)D^{\beta}\widehat{K}_{\varepsilon}|d\eta$
$\displaystyle+\int_{\|\eta\|_{2}\geq
c_{1}\sqrt{n}}|D^{\alpha}(\sum_{r=0}^{\ell-2+d}n^{-r/2}P_{r}(i\eta:\\{\chi_{\nu,n}\\}))\exp(-1/2\langle\eta,B_{n}\eta\rangle)|d\eta,$

where $B_{n}^{2}=V_{n}^{-1}$ (defined in (8.1).)

The second term can be controlled by $O(e^{-cn})$ thanks to the Gaussian decay
of $\exp(-1/2\langle\eta,B_{n}\eta\rangle)$.

Let $\phi_{i}(\eta)={\mathbf{E}}e^{i\eta\cdot{\mathbf{w}}_{i}}$. Then for
$|\alpha|\leq\ell+d+1$ we have
$D^{\alpha}_{\eta}(\phi_{i}(\eta/\sqrt{n}))=n^{-|\alpha|/2}O({\mathbf{E}}\|X_{n,i}\|_{2}^{|\alpha|})=O(1)$.
Thus,

$|D^{\alpha}\widehat{Q}_{n}(\eta)|=|D^{\alpha}(\prod_{i=1}^{n}\phi_{i}(\frac{\eta}{\sqrt{n}}))|=O(\sum_{\gamma_{1}+\dots+\gamma_{n}=\alpha}|\prod_{i=1,\gamma_{i}=0}^{n}\phi_{i}(\frac{\eta}{\sqrt{n}})|),$

while we also have
$|D^{\beta}\widehat{K}_{\varepsilon}(\eta)|=O(\varepsilon^{|\beta|}e^{-(\varepsilon\|\eta\|_{2})^{1/2}})=O(e^{-(\varepsilon\|\eta\|_{2})^{1/2}})$.
Thus, it remains to control, for each $(\gamma_{1},\dots,\gamma_{n})$ with
$|\gamma_{1}|+\dots+|\gamma_{n}|\leq\ell+d+1$ and each $r>0$ independent of
$n$:

$\displaystyle J_{\gamma}(n,\varepsilon)$
$\displaystyle=\int_{\|\eta\|_{2}\geq
r\sqrt{n}}|\prod_{i=1,\gamma_{i}=0}^{n}\phi_{i}(\frac{\eta}{\sqrt{n}})|e^{-(\varepsilon\|\eta\|_{2})^{1/2}}d\eta$
$\displaystyle=n^{d/2}\int_{\|\eta\|_{2}\geq
r}|\prod_{i=1,\gamma_{i}=0}^{n}\phi_{i}(\eta)|e^{-(n^{-K_{\ast}+1/2}\|\eta\|_{2})^{1/2}}d\eta.$

Clearly it suffices to consider $r\leq\|\eta\|_{2}\leq n^{K_{\ast}-1/2+\tau}$
because the integral for $\|\eta\|_{2}\geq n^{K_{\ast}-1/2+\tau}$ is extremely
small. Again, because $\alpha$ is fixed, by throwing away from the set
$\\{{\mathbf{w}}_{i}\\}$ a fixed number of elements, let us assume that
$\alpha=0$ for simplicity 444In the general case $\alpha\neq 0$ we apply
Theorem 10.2 instead of Theorem 3.1.. To this end, by Theorem 3.1 for
sufficiently large $n$ we have

$|\prod_{i}\phi_{i}(\eta)|\leq e^{-\log^{2}n}.$

Thus we just shown that, with $\varepsilon=n^{-K_{\ast}}$ we have
$J_{\gamma}(n,\varepsilon)=O(e^{-\log^{2}n})$, completing the proof. ∎

We turn now to the proof of Theorem 3.2. We follow [DNN, Section 5] with some
slight modifications. Let $\eta,\varepsilon>0$ to be chosen later, and towards
an application of Theorem 8.1 we fix some In the sequel we abbreviate We let

$g:=\frac{1}{16\delta_{1}\delta_{2}\delta_{3}\delta_{4}}1_{w+B_{m}(\boldsymbol{\delta})}$

be the $L^{1}$-normalized indicator for the box
$w+B_{m}(\boldsymbol{\delta})\subset{\mathbb{R}}^{4{m}}$. For $1\leq i\leq 4$
let $\varphi_{i,\eta}:{\mathbb{R}}\to[0,1]$ be a $C^{\infty}({\mathbb{R}})$
function with support inside $[-\delta_{i},\delta_{i}]$ such that

(i) $\varphi_{i,\eta}(x)=\delta_{i}^{-1}$ for $|x|\leq\delta_{i}(1-\eta)$, and

(ii) $|\varphi_{i,\eta}^{(k)}(x)|=O_{k}(\delta_{i}^{-(k+1)}\eta^{-k})$ for any
$k\geq 0$,
and set

$f(\boldsymbol{x})=\prod_{r=1}^{m}\prod_{i=1}^{4}\varphi_{i,\eta}(w^{i}_{r}+x^{i}_{r})$

where we write
$\boldsymbol{w}=(w^{1},\dots,w^{4}),\boldsymbol{x}=(x^{1},\dots,x^{4})\in{\mathbb{R}}^{4{m}}$.
We have

$\|\nabla f(\boldsymbol{x})\|_{2}\ll_{m}\frac{2}{\delta^{4{m}+1}\eta}$

uniformly in $\boldsymbol{x}$. Recall that
$\bar{\omega}_{f}(\varepsilon:\phi)=\int(\sup_{y\in
B(x,\varepsilon)}f(y)-\inf_{y\in B(x,\varepsilon)}f(y))\phi(x)dx$, and $\phi$
is the density of a Gaussian vector. Consequently, for any polynomial $p(x)$
with bounded degree and bounded coefficients we have

$\bar{\omega}_{f}(\varepsilon:p(x)\phi_{0,V_{n}}(x))=O(\eta^{-1}\delta^{-4{m}-1}\varepsilon),$

where the implied constant depends on the eigenvalues of $V_{n}$, and on the
degree and coefficients of $p$. In particular, the final error term in Theorem
8.1 can be expressed as

$\sum_{r=0}^{\ell+4{m}-2}n^{-r/2}T_{r}(-\phi_{0,V_{n}}:\\{\overline{\chi}_{\nu}\\})=p(x)\phi_{0,V_{n}}(x)$

for some polynomial $p$ with degree at most $4{m}+\ell$ and coefficients
bounded by the first $4{m}+\ell$ moments of $\xi$. Therefore

$\bar{\omega}_{f}(2\varepsilon:\sum_{r=0}^{\ell+4{m}-2}n^{-r/2}T_{r}(-\phi_{0,V_{n}}:\\{\overline{\chi}_{\nu}\\}))=O(\eta^{-1}\delta^{-4{m}-1}\varepsilon),$
(8.5)

where the implied constant depends on the eigenvalues of $V_{n}$ and the
moments up to order $O({m})$ of $\xi$.

Recall the shorthand notation
$\widetilde{S}:=S_{n}(\boldsymbol{t})/\sqrt{2n+1}$ from (4.7), and that
$\Gamma$ has the distribution of $\widetilde{S}$ with standard real Gaussians
in place of the variables $\xi_{j}$. From Theorem 3.4 and Corollary 3.5,

$\displaystyle\big{|}{\mathbf{E}}f(\widetilde{S})-{\mathbf{E}}g(\widetilde{S})\big{|}$
$\displaystyle\leq$
$\displaystyle(\frac{C}{\delta})^{4{m}}\sum_{r=1}^{m}{\mathbf{P}}(||{\operatorname{Re}}P_{n}(s_{r})|-\delta_{1}|\leq\eta\delta_{1})+{\mathbf{P}}(|{\operatorname{Re}}P_{n}^{\prime}(s_{r})|-\delta_{2}|\leq\eta\delta_{2})$
$\displaystyle+$
$\displaystyle{\mathbf{P}}(||{\operatorname{Im}}P_{n}(s_{r})|-\delta_{3}|\leq\eta\delta_{3})+{\mathbf{P}}(|{\operatorname{Im}}P_{n}^{\prime}(s_{r})|-\delta_{4}|\leq\eta\delta_{4})\Big{)}$
$\displaystyle\ll_{m}$ $\displaystyle(\frac{C}{\delta})^{4{m}}\eta$

By Theorem 8.1 and (8.5) (with $\ell=16{m}K+3$), after keeping the first term
of the expansion, and by the triangle inequality we have

$\displaystyle\Big{|}{\mathbf{E}}f(\widetilde{S})-{\mathbf{E}}f(\Gamma)\Big{|}$
$\displaystyle\leq\Big{|}\int
f(x)\sum_{r=1}^{\ell-2}n^{-r/2}T_{r}(-\phi_{0,V_{n}}(x),\\{\overline{\chi}_{\nu}\\})\Big{|}$
$\displaystyle+M_{\ell}(f)O\Big{(}n^{-8{m}K-1}+e^{-\log^{2}n}\Big{)}+\bar{\omega}_{f}(2\varepsilon:\sum_{r=0}^{4{m}+1}n^{-r/2}T_{r}(-\phi_{0,V_{n}}:\\{\overline{\chi}_{\nu}\\}))$
$\displaystyle=O(n^{-1/2})+(C/\delta)^{4{m}}O(n^{-8{m}K-1}+e^{-\log^{2}n})+O((C/\delta)^{4{m}+1}\eta^{-1}\varepsilon),$

where we used the fact that $|\int
f(x)T_{r}(-\phi_{0,V_{n}}(x),\\{\overline{\chi}_{\nu}\\})|=O(1)$ with the
implied constant depending on the moments of $\xi$ up to order $r$ and on the
implicit constant from (ii) of $\varphi$. In particular, the above is also
true for the Gaussian case. Consequently, again by the triangle inequality

$\displaystyle|{\mathbf{E}}g(\widetilde{S})-{\mathbf{E}}g(\Gamma)|$
$\displaystyle\leq$
$\displaystyle|{\mathbf{E}}g(\widetilde{S})-{\mathbf{E}}f(\widetilde{S})|+|{\mathbf{E}}f(\Gamma)-{\mathbf{E}}g(\Gamma)|+|{\mathbf{E}}f(\widetilde{S})-{\mathbf{E}}f(\Gamma)|$
$\displaystyle\ll_{m}$ $\displaystyle
n^{-1/2}+(\frac{1}{\delta})^{4{m}}(n^{-8{m}K-1}+e^{-\log^{2}n}+\delta^{-1}\eta^{-1}\varepsilon+\eta)=O(n^{-1/2}),$

where we took $\eta=\varepsilon^{1/2}$ and $\varepsilon=n^{-K_{*}}$ with
$K_{*}$ sufficiently large compared to $K$.

##  9 Proof of Theorem 3.1

We assume throughout this section that $n$ is sufficiently large depending on
${m},{\kappa},K_{*}$ and the sub-Gaussian constant for $\xi$. We first recall
a definition and fact from [TV08]. For a real number $w$ and a random variable
$\xi$, define the $\xi$-norm of $w$ as

$\|w\|_{\xi}:=({\mathbf{E}}\|w(\xi-\xi^{\prime})\|_{{\mathbb{R}}/{\mathbb{Z}}}^{2})^{1/2},$

where $\xi^{\prime}$ is an iid copy of $\xi$. For instance, if $\xi$ has the
Rademacher distribution ${\mathbf{P}}(\xi=\pm 1)=1/2$, then
$\|w\|_{\xi}^{2}=\|2w\|_{{\mathbb{R}}/{\mathbb{Z}}}^{2}/2$. For any real
number $w$ we have

$|{\mathbf{E}}e(w\xi)|\leq\exp(-c\|w/2\pi\|_{\xi}^{2})$

for an absolute constant $c>0$.

Now with ${\phi}_{j}:{\mathbb{R}}^{4{m}}\to{\mathbb{C}}$ the characteristic
function of $\xi_{j}\boldsymbol{w}_{j}$, we have

$\displaystyle\Big{|}{\mathbf{E}}e\big{(}\langle
S_{n}(\boldsymbol{t}),\boldsymbol{x}\rangle\big{)}\Big{|}$
$\displaystyle=|\prod_{j}{\phi}_{j}(\boldsymbol{x})|=\prod_{j}|{\mathbf{E}}e(\xi_{j}\langle\boldsymbol{w}_{j},\boldsymbol{x}\rangle)|\leq\exp(-c\sum_{j}\|\langle\boldsymbol{w}_{j},\boldsymbol{x}/2\pi\rangle\|_{\xi}^{2}).$
(9.1)

Furthermore, as $\xi$ is sub-Gaussian and of unit variance, there exist
positive constants $a_{1},a_{2},c>0$ depending only on the sub-Gaussian moment
of $\xi$ such that ${\mathbf{P}}(a_{1}<|\xi-\xi^{\prime}|<a_{2})\geq c$, and
so

$\displaystyle\sum_{j}\|\langle\boldsymbol{w}_{j},\boldsymbol{x}/2\pi\rangle\|_{\xi}^{2}={\mathbf{E}}\sum_{j}\|\langle\boldsymbol{w}_{j},\boldsymbol{x}/2\pi\rangle(\xi-\xi^{\prime})\|_{{\mathbb{R}}/{\mathbb{Z}}}^{2}\geq
c\inf_{a_{1}\leq|a|\leq
a_{2}}\sum_{j}\|a\langle\boldsymbol{w}_{j},\boldsymbol{x}/2\pi\rangle\|_{{\mathbb{R}}/{\mathbb{Z}}}^{2}.$
(9.2)

It hence suffices to show that
$\sum_{j}\|a\langle\boldsymbol{w}_{j},\boldsymbol{x}/2\pi\rangle\|_{{\mathbb{R}}/{\mathbb{Z}}}^{2}\gg\log^{3}n$
uniformly for $|a|\in[a_{1},a_{2}]$. Fixing an arbitrary such $a$, since
$a_{1},a_{2}\asymp 1$ we will abuse notation and absorb $a$ into the
definition of $\boldsymbol{x}$. Recalling (3.1), since
$\boldsymbol{w}_{j}+\boldsymbol{w}_{-j}=2(0,0,\boldsymbol{b}_{j},-(j/n)\boldsymbol{a}_{j})$
and
$\boldsymbol{w}_{j}-\boldsymbol{w}_{-j}=2(\boldsymbol{a}_{j},(j/n)\boldsymbol{b}_{j},0,0)$,
for
$\boldsymbol{x}=(\boldsymbol{x}^{1},\boldsymbol{x}^{2},\boldsymbol{x}^{3},\boldsymbol{x}^{4})\in{\mathbb{R}}^{4{m}}$
and each $0\leq j\leq n$, we have from the triangle inequality that

$\displaystyle\|\langle\boldsymbol{w}_{j},\boldsymbol{x}\rangle\|_{{\mathbb{R}}/{\mathbb{Z}}}^{2}+\|\langle\boldsymbol{w}_{-j},\boldsymbol{x}\rangle\|_{{\mathbb{R}}/{\mathbb{Z}}}^{2}$
$\displaystyle\geq\frac{1}{2}\max\big{\\{}\|\langle\boldsymbol{w}_{j}+\boldsymbol{w}_{-j},\boldsymbol{x}\rangle\|_{{\mathbb{R}}/{\mathbb{Z}}}^{2}\,,\,\|\langle\boldsymbol{w}_{j}-\boldsymbol{w}_{-j},\boldsymbol{x}\rangle\|_{{\mathbb{R}}/{\mathbb{Z}}}^{2}\big{\\}}$
$\displaystyle=2\max\Big{\\{}\|\langle\boldsymbol{b}_{j},\boldsymbol{x}^{3}\rangle-(j/n)\langle\boldsymbol{a}_{j},\boldsymbol{x}^{4}\rangle\|_{{\mathbb{R}}/{\mathbb{Z}}}^{2}\,,\,\|\langle\boldsymbol{a}_{j},\boldsymbol{x}^{1}\rangle+(j/n)\langle\boldsymbol{b}_{j},\boldsymbol{x}^{2}\rangle\|_{{\mathbb{R}}/{\mathbb{Z}}}^{2}\Big{\\}}.$

Recalling our assumption $\|\boldsymbol{x}\|_{2}\geq n^{-1/8}$, we will assume
$\|\boldsymbol{x}^{3}\|_{2}^{2}+\|\boldsymbol{x}^{4}\|_{2}^{2}\geq\frac{1}{2}n^{-1/4}$;
the complementary case that
$\|\boldsymbol{x}^{1}\|_{2}^{2}+\|\boldsymbol{x}^{2}\|_{2}^{2}\geq\frac{1}{2}n^{-1/4}$
can be handled by the same argument. Fix now a vector
$(\boldsymbol{y},\boldsymbol{y}^{\prime})\in{\mathbb{R}}^{2{m}}$ satisfying

$n^{-1/8}\leq\|(\boldsymbol{y},\boldsymbol{y}^{\prime})\|_{2}\leq n^{K_{*}}$

and denote

$\psi(j)=\psi(j;\boldsymbol{t}):=\langle\boldsymbol{b}_{j},\boldsymbol{y}\rangle-(j/n)\langle\boldsymbol{a}_{j},\boldsymbol{y}^{\prime}\rangle=\sum_{r=1}^{m}y_{r}\cos(jt_{r}/n)-y^{\prime}_{r}(j/n)\sin(jt_{r}/n)\,.$
(9.3)

With $(\boldsymbol{y},\boldsymbol{y}^{\prime})$ playing the role of
$(\boldsymbol{x}^{3},\boldsymbol{x}^{4})$, to establish Theorem 3.1 our task
thus reduces to establishing the following:

######  Proposition 9.1.

Let $\boldsymbol{t}=(t_{1},\dots,t_{r})\in{\mathbb{R}}^{m}$ be
$n^{{\kappa}}$-smooth and ${\lambda}$-spread for some ${\kappa}\in(0,1)$ and
$\omega(n^{-1/8{m}})\leq{\lambda}<1$. Then

$\sum_{j=0}^{n}\|\psi(j)\|_{{\mathbb{R}}/{\mathbb{Z}}}^{2}>\log^{4}n.$

Turning to prove the proposition, we henceforth denote

$T:=\log^{4}n.$

In the remainder of this section we suppose towards a contradiction that

$\sum_{j=0}^{n}\|\psi(j)\|_{{\mathbb{R}}/{\mathbb{Z}}}^{2}\leq T\,.$ (9.4)

From (9.4) and Markov’s inequality we have

$|\\{j\in[0,n]\cap{\mathbb{Z}}:\|\psi(j)\|_{{\mathbb{R}}/{\mathbb{Z}}}>1/T\\}|\leq
2T^{3}$

and it follows that there is an interval $J\subset[n]$ of length at least
$n/T^{6}$ such that

$\|\psi(j)\|_{{\mathbb{R}}/{\mathbb{Z}}}\leq 1/T\qquad\forall\;j\in J.$ (9.5)

We henceforth fix such an interval $J=[n_{1},n_{2}]$.

Next we claim we can find $q_{0}\in{\mathbb{Z}}\cap[1,n^{{\kappa}}]$ and
$s_{1},\dots,s_{m}\in{\mathbb{R}}$ such that

$q_{0}t_{r}/2\pi n-s_{r}\in{\mathbb{Z}}$ (9.6)

and

$\sum_{r=1}^{m}s_{r}^{2}\leq{m}n^{-2{\kappa}/{m}}.$ (9.7)

Indeed, considering the sequence of points $(\\{qt_{1}/2\pi
n\\},\dots,\\{qt_{m}/2\pi n\\})\in[0,1]^{m}$ for $1\leq q\leq n^{{\kappa}}$,
it follows from Dirichlet’s principle that

$\sum_{r=1}^{m}|\\{q_{1}(t_{r}/2\pi n)\\}-\\{q_{2}(t_{r}/2\pi
n)\\}|^{2}\leq{m}n^{-2{\kappa}/{m}}$

for some $1\leq q_{1},q_{2}\leq n^{\kappa}$. Then we have

$|(q_{1}-q_{2})t_{r}/2\pi n-p_{r}|^{2}\leq{m}n^{-2{\kappa}/{m}}$

for some $p_{1},\dots,p_{m}\in{\mathbb{Z}}$. Now (9.6) and (9.7) follow by
taking $q_{0}=q_{1}-q_{2}$ and $s_{r}=(q_{1}-q_{r})t_{r}/2\pi n-p_{r}$.

Fixing such $q_{0},s_{1},\dots,s_{r}$, we have

$|e_{n}(q_{0}t_{r})-1|=|e(2\pi s_{r})-1|\leq
2\pi{m}^{1/2}n^{-{\kappa}/{m}}\qquad\forall\;1\leq r\leq{m}.$ (9.8)

We next combine (9.5) and (9.8) to deduce some smoothness of the sequence
$\psi(j)$ over $j\in J$, via Lemma 9.2 below. For $g:[n]\to{\mathbb{C}}$ and
positive integers $k,q$ we define the discrete differential of order $k$ and
step $q$ as

$\Delta^{k}_{q}g:[n]\to{\mathbb{C}}\,,\qquad(\Delta^{k}_{q}g)(j):=\sum_{i=0}^{k}{k\choose
i}(-1)^{i}g(j+iq).$

For any integer $q$ and $t\in{\mathbb{R}}$,

$\displaystyle\sum_{i=0}^{k}{k\choose
i}(-1)^{i}e_{n}((j+iq)t)=(1-e_{n}(qt))^{k}e_{n}(jt).$

Taking real parts on both sides, we obtain

$\sum_{i=0}^{k}{k\choose
i}(-1)^{i}\cos((j+iq)t/n)={\operatorname{Re}}\big{[}(1-e_{n}(qt))^{k}e_{n}(jt)\big{]},$

and differentiating in $t$ yields

$\sum_{i=0}^{k}{k\choose
i}(-1)^{i}\frac{j+iq}{n}\sin((j+iq)t/n)={\operatorname{Re}}\Big{[}\partial_{t}\big{[}(1-e_{n}(qt))^{k}e_{n}(jt)\big{]}\Big{]}\,.$

Combining the previous two identities over $t=t_{r},r\in[m]$ we obtain the
identity

$(\Delta_{q}^{k}\psi)(j)={\operatorname{Re}}\bigg{[}\sum_{r=1}^{m}y_{r}(1-e_{n}(qt_{r}))^{k}e_{n}(jt_{r})-y^{\prime}_{r}\partial_{t}\big{[}(1-e_{n}(qt_{r}))^{k}e_{n}(jt_{r})\big{]}\bigg{]}.$
(9.9)

Denoting henceforth

$f_{t,\ell}(j):=(1-e_{n}(\ell q_{0}t))^{k}e_{n}(jt),$ (9.10)

substituting $q=\ell q_{0}$ in the above identity yields

$(\Delta^{k}_{\ell
q_{0}}\psi)(j)={\operatorname{Re}}\bigg{[}\sum_{r=1}^{m}y_{r}+y_{r}^{\prime}\partial_{t_{r}}f_{t_{r},\ell}(j)\bigg{]}\,$
(9.11)

######  Lemma 9.2.

There exists $k=O_{K_{*},{\kappa},{m}}(1)$ such that for any $\ell\geq 1$ and
any $j\in J$ such that $[j,j+k\ell q_{0}]\subset J$,

$(\Delta_{\ell
q_{0}}^{k}\psi)(j)\ll_{K_{*},{\kappa},{m}}\sum_{i=0}^{k}\|\psi(j+i\ell
q_{0})\|_{{\mathbb{R}}/{\mathbb{Z}}}.$

###### Proof.

Fix $k\geq 1$ to be chosen sufficiently large depending on
$K_{*},{\kappa},{m}$. From (9.8), for $\ell=1$ we have

$|f_{t_{r},1}(j)|\leq(2\pi{m}^{1/2}n^{-{\kappa}/{m}})^{k}<n^{-k{\kappa}/2{m}}$

and

$|f_{t_{r},1}^{\prime}(j)|\leq
kq_{0}(2\pi{m}^{1/2}n^{-{\kappa}/{m}})^{k-1}+(2\pi{m}^{1/2}n^{-{\kappa}/{m}})^{k}<n^{-k{\kappa}/2{m}}$

and hence

$|(\Delta_{q_{0}}^{k}\psi)(j)|\leq
n^{-{\kappa}k/2{m}}\sum_{r=1}^{m}|y_{r}|+|y^{\prime}_{r}|<mn^{K_{*}-{\kappa}k/2{m}}.$

Let $p(j)$ denote the closest integer to $\psi(j)$. From the triangle
inequality and (9.5) it follows that

$|(\Delta^{k}_{q_{0}}p)(j)|<mn^{K_{*}-{\kappa}k/2{m}}+\frac{2^{k}}{T}$

as long as $\\{j,j+q_{0},\dots,j+kq_{0}\\}\subset J$. Taking $k=\lfloor
4{m}K_{*}/{\kappa}\rfloor+1$, the right hand side is smaller than 1. Since the
numbers $(\Delta^{k}_{q_{0}}p)(j)$ are integers, it follows that

$(\Delta^{k}_{q_{0}}p)(j)=0$

for all $j$ such that $\\{j,j+q_{0},\dots,j+kq_{0}\\}\subset J$. By repeated
application of the above for $j$ running over progressions
$j_{0},j_{0}+q_{0},j_{0}+2q_{0},\dots$ with $j_{0}\in J$, we deduce that for
any $j$ such that $[j,j+kq_{0}]\subset J=[n_{1},n_{2}]$ there exists a
polynomial $Q_{j}$ of degree at most $k-1$ such that

$p(j+iq_{0})=Q_{j}(i)\qquad\forall\;0\leq i\leq(n_{2}-j)/q_{0}.$

Thus we have $(\Delta^{k}_{\ell q_{0}}p)(j)=0$ for all $\ell\geq 1$ and $j$
such that $[j,j+k\ell q_{0}]\subset J$. Hence, for such $j$ we conclude by the
triangle inequality that

$|(\Delta^{k}_{\ell q_{0}}\psi)(j)|=|(\Delta^{k}_{\ell
q_{0}}\psi)(j)-(\Delta^{k}_{\ell q_{0}}p)(j)|\leq
2^{k}\sum_{i=0}^{k}\|\psi(j+i\ell q_{0})\|_{{\mathbb{R}}/{\mathbb{Z}}}$

as desired. ∎

Note that $\|\boldsymbol{y}\|_{2}+\|\boldsymbol{y}^{\prime}\|_{2}\gg
n^{-1/8}$. Thus either (1) there exists $i$ such that $|y_{i}^{\prime}|\gg
n^{-1/16}$ (with room to spare) or (2) $|y_{i}^{\prime}|\leq n^{-1/16}$ for
all $i$ and there exists $i$ such that $|y_{i}|\gg_{m}n^{-1/8}$. In what
follows we will mainly working with the first case (which is significantly
harder as one needs to deal with differentials of order two). We will comment
in Remark 9.4 below how to handle the second case. For the rest of the
section, without loss of generality we will assume

$|y_{1}^{\prime}|\gg_{m}n^{-1/16}$ (9.12)

On the other hand, by applying Lemma 9.2 to linear combinations of shifts of
$\Delta^{k}_{\ell q_{0}}\psi$ we can show the following:

######  Lemma 9.3.

For any positive integers $j,L,L^{\prime}$ and $\ell$ such that $[j,j+k\ell
q_{0}+4({m}-1)L+3L^{\prime}]\subset J$, we have

$\displaystyle\frac{L^{\prime}}{n}\left|y_{1}^{\prime}\big{(}1-e_{n}(2L^{\prime}t_{1})\big{)}^{2}\big{(}1-e_{n}(\ell
q_{0}t_{1})\big{)}^{k}\prod_{r=2}^{m}\big{(}1-e_{n}(L(t_{1}-t_{r}))\big{)}^{2}\big{(}1-e_{n}(L(t_{1}+t_{r}))\big{)}^{2}\right|$
$\displaystyle\qquad\qquad\qquad\qquad\ll_{K_{*},{\kappa},{m}}\sum_{i=1}^{k}\sum_{a=0}^{4({m}-1)}\sum_{b=0}^{3}\|\psi(j+i\ell
q_{0}+aL+bL^{\prime})\|_{{\mathbb{R}}/{\mathbb{Z}}}.$ (9.13)

We defer the proof of Lemma 9.3 for now and conclude the proof of 9.1.

Recall from (9.5) that $J=[n_{1},n_{2}]\subset[n]$ has length $|J|\geq
n/T^{6}$. Consider any $\ell\geq 1$ such that $k\ell q_{0}\leq|J|/2$. From
Lemma 2.8 we can choose ${L}\asymp n/T^{7}=o(|J|)$ such that

$\bigg{\|}\frac{{L}\cdot(t_{r}\pm t_{r^{\prime}})}{2\pi
n}\bigg{\|}_{{\mathbb{R}}/{\mathbb{Z}}}\gg_{m}\frac{{\lambda}}{T^{7}}$

for all distinct $r,r^{\prime}\in[m]$ and all choices of the signs.

Furthermore, because $t_{1}$ is smooth, we can choose $L^{\prime}$ such that
$n/T^{8}\leq L^{\prime}=o(|J|)$ and

$|1-e_{n}(2L^{\prime}t_{1})|>{\lambda}^{2}=\omega(n^{-1/4{m}}).$

From these choices of $\ell,{L}$ and $L^{\prime}$, together with (9.12), we
have that the left hand side in (9.13) is at least

$\gg_{m}n^{-1/16}{\lambda}^{4}T^{-16}({\lambda}/T^{7})^{4({m}-1)}|1-e_{n}(\ell
q_{0}t_{1})|^{k}.$

On the other hand, from (9.4) and the Cauchy–Schwarz inequality we have

$\sum_{j=0}^{n}\|\psi(j)\|_{{\mathbb{R}}/{\mathbb{Z}}}\leq\sqrt{nT}\,,$ (9.14)

and it follows that that we can choose $j$ so that the right hand side in
Equation 9.13 is $O_{K_{*},{\kappa},{m}}(T^{1/2}n^{-1/2})$. Thus,

$|1-e_{n}(\ell q_{0}t_{1})|\leq n^{-1/3k}$ (9.15)

and this holds for any integer $\ell\geq 1$ such that $\ell kq_{0}\leq|J|/2$.
Applying 2.9, we conclude

$\|q_{0}t_{1}/2\pi n\|_{{\mathbb{R}}/{\mathbb{Z}}}=n^{-1}\log^{O(1)}n.$

But since we chose $q_{0}\leq n^{\kappa}$ this contradicts the assumption that
$t_{1}$ is $n^{{\kappa}}$-smooth. This concludes the proof of 9.1 and hence of
Theorem 3.1.∎

###### Proof of Lemma 9.3.

We begin by recording some identities. Recall the definition of
$f_{t,\ell}(j)$ from (9.10). To lighten notation we will suppress the
subscript $\ell$ as it is fixed throughout the proof. First note that

$g_{t}(j):=\partial_{t}f_{t}(j)=\sqrt{-1}\bigg{[}\frac{j}{n}-\frac{k\ell
q_{0}}{n}\big{(}1-e_{n}(\ell q_{0}t)\big{)}^{-1}\bigg{]}f_{t}(j).$ (9.16)

In particular, we have

$\overline{f_{t}(j)}=f_{-t}(j)\,,\qquad\overline{g_{t}(j)}=-g_{-t}(j)$

and from (9.11) we can express

$\frac{1}{2}(\Delta_{\ell
q_{0}}^{k}\psi)(j)=\sum_{r=1}^{m}y_{r}f_{t_{r}}(j)+y_{r}f_{-t_{r}}(j)+y^{\prime}_{r}g_{t_{r}}(j)-y^{\prime}_{r}g_{-t_{r}}(j).$
(9.17)

As in the proof of Lemma 3.6 we will eliminate terms in the above sum by
repeated application of the twisted second-order differencing operators
defined in (3.6). For a positive integer $L$ and $t_{0}\in{\mathbb{R}}$ we
have

$\displaystyle D_{t_{0}}f_{t}(j)$ $\displaystyle=\sum_{a=0}^{2}{2\choose
a}(-1)^{a}e_{n}(-aLt_{0})f_{t}(j+aL)$
$\displaystyle=f_{t}(j)\sum_{a=0}^{2}{2\choose a}(-1)^{a}e_{n}(aL(t-t_{0}))$
$\displaystyle=\big{[}1-e_{n}(L(t-t_{0}))\big{]}^{2}f_{t}(j).$

Note that the sequences $f_{t}(j)$ from that proof differ from the present
definition by a factor $(1-e_{n}(\ell q_{0}t))^{k}$. This is a key point:
whereas there our aim was to lower bound $\sum_{j}|\psi(j)|^{2}$, here we have
the more difficult task of lower bounding
$\sum_{j}\|\psi(j)\|_{{\mathbb{R}}/{\mathbb{Z}}}^{2}$ (which we are doing by
contradiction, starting from the assumption (9.4)). We are now in a similar
position as in the proof of Lemma 3.6 thanks to Lemma 9.2 and the application
of the differencing operators $\Delta_{\ell q_{0}}^{k}$, which is responsible
for the extra factor $(1-e_{n}(\ell q_{0}t))^{k}$.

Differentiating the above expression for $D_{t_{0}}f_{t}(j)$ yields

$\displaystyle D_{t_{0}}g_{t}(j)$
$\displaystyle=\big{[}1-e_{n}(L(t-t_{0}))\big{]}^{2}\partial_{t}f_{t}(j)+{\sqrt{-1}}\frac{L}{n}f_{t}(j)\sum_{a=0}^{2}{2\choose
a}(-1)^{a}a\cdot e_{n}(aL(t-t_{0}))$
$\displaystyle=\big{[}1-e_{n}(L(t-t_{0}))\big{]}^{2}\partial_{t}f_{t}(j)-2{\sqrt{-1}}\frac{L}{n}\big{[}1-e_{n}(L(t-t_{0}))\big{]}e_{n}(L(t-t_{0}))f_{t}(j)$
$\displaystyle=\big{[}1-e_{n}(L(t-t_{0}))\big{]}^{2}\big{[}g_{t}(j)+\beta_{L}(t-t_{0})f_{t}(j)\big{]}$
(9.18)

with $\beta_{L}(s):=-2{\sqrt{-1}}\frac{L}{n}e_{n}(Ls)/[1-e_{n}(Ls)]$, as in
(3.8). In particular,

$D_{t_{0}}f_{t_{0}}(j)=D_{t_{0}}g_{t_{0}}(j)=0.$ (9.19)

Now for general $t\in{\mathbb{R}}$, two applications with $t_{0}$ and $-t_{0}$
yield

$D_{t_{0}}\circ
D_{-t_{0}}f_{t}(j)=\big{[}1-e_{n}(L(t-t_{0}))\big{]}^{2}\big{[}1-e_{n}(L(t+t_{0}))\big{]}^{2}f_{t}(j)$
(9.20)

and

$D_{t_{0}}\circ
D_{-t_{0}}g_{t}(j)=\partial_{t}\Big{[}\big{[}1-e_{n}(L(t-t_{0}))\big{]}^{2}\big{[}1-e_{n}(L(t+t_{0}))\big{]}^{2}f_{t}(j)\Big{]}.$
(9.21)

For compactness, we write

$\delta_{L}(s):=1-e_{n}(Ls)$

for the remainder of the proof. Applying the above identities with
$t_{0}=t_{m}$ and $t$ running over $t_{r}$, $r\in[{m}-1]$, we obtain

$\displaystyle\frac{1}{2}\Big{(}D_{t_{m}}\circ D_{-t_{m}}\circ\Delta_{\ell
q_{0}}^{k}\,\psi\Big{)}(j)$
$\displaystyle\qquad=\sum_{r=1}^{{m}-1}\left(y_{r}+y_{r}^{\prime}\partial_{t_{r}}\right)\bigg{[}\delta_{L}(t_{r}-t_{m})^{2}\delta_{L}(t_{r}+t_{m})^{2}f_{t_{r}}(j)+\delta_{L}(-t_{r}-t_{m})^{2}\delta_{L}(-t_{r}+t_{m})^{2}f_{-t_{r}}(j)\bigg{]}\,.$

Iteratively applying $D_{t_{r}}\circ D_{-t_{r}}$ for $r={m}-1,{m}-2,\dots,2$,
we get

$\displaystyle\frac{1}{2}\big{(}D_{t_{2}}\circ D_{-t_{2}}\circ\cdots\circ
D_{t_{m}}\circ D_{-t_{m}}\circ\Delta_{\ell q_{0}}^{k}\,\psi\Big{)}(j)$
$\displaystyle\qquad=y_{1}f_{t_{1}}(j)\prod_{r=2}^{m}\delta_{L}(t_{1}-t_{r})^{2}\delta_{L}(t_{1}+t_{r})^{2}+y_{1}f_{-t_{1}}(j)\prod_{r=2}^{m}\delta_{L}(-t_{1}-t_{r})^{2}\delta_{L}(-t_{1}+t_{r})^{2}$
$\displaystyle\qquad+y_{1}^{\prime}\partial_{t}\bigg{[}f_{t}(j)\prod_{r=2}^{m}\delta_{L}(t-t_{r})^{2}\delta_{L}(t+t_{r})^{2}\bigg{]}_{t=t_{1}}+y_{1}^{\prime}\partial_{t}\bigg{[}f_{-t}(j)\prod_{r=2}^{m}\delta_{L}(-t-t_{r})^{2}\delta_{L}(-t+t_{r})^{2}\bigg{]}_{t=t_{1}}\,,$

and we have passed from a sum of $4{m}$ terms (see (9.17)) to a sum of 4. Now
we will reduce from four terms to one. Let $L^{\prime}$ be a positive integer
and define $D^{\prime}_{t_{0}}$ as in (3.6) with $L^{\prime}$ in place of $L$.
For any univariate function $G$ we have

$\displaystyle D^{\prime}_{t_{0}}f_{t_{0}}(j)G(t_{0})$
$\displaystyle=G(t_{0})D^{\prime}_{t_{0}}f_{t_{0}}(j)=0\,,$ $\displaystyle
D^{\prime}_{t_{0}}\partial_{t}\big{[}f_{t}(j)G(t)\big{]}_{t=t_{0}}$
$\displaystyle=G(t_{0})D^{\prime}_{t_{0}}g_{t_{0}}(j)+G^{\prime}(t_{0})D^{\prime}_{t_{0}}f_{t_{0}}(j)=0$

(using (9.19)). Set

$G(t):=\prod_{r=2}^{m}\delta_{L}(t-t_{r})^{2}\delta_{L}(t+t_{r})^{2}$

for which we have $\overline{G(t)}=G(-t)$. Application of
$D^{\prime}_{-t_{1}}$ to the previous expression for
$\frac{1}{2}(D_{t_{2}}\circ D_{-t_{2}}\circ\cdots\circ D_{t_{m}}\circ
D_{-t_{m}}\circ\Delta_{\ell q_{0}}^{k}\,\psi)(j)$ eliminates the second and
fourth terms on the right hand side, leaving

$\displaystyle\frac{1}{2}\Big{(}D^{\prime}_{-t_{1}}\circ D_{t_{2}}\circ
D_{-t_{2}}\circ\cdots\circ D_{t_{m}}\circ D_{-t_{m}}\circ\Delta_{\ell
q_{0}}^{k}\,\psi\Big{)}(j)$
$\displaystyle\qquad=y_{1}f_{t_{1}}(j)\delta_{L^{\prime}}(2t_{1})^{2}G(t_{1})+y_{1}^{\prime}D^{\prime}_{-t_{1}}\partial_{t}\Big{[}f_{t}(j)G(t)\Big{]}_{t=t_{1}}$
$\displaystyle\qquad=y_{1}f_{t_{1}}(j)\delta_{L^{\prime}}(2t_{1})^{2}G(t_{1})+y_{1}^{\prime}g_{t_{1}}(j)\delta_{L^{\prime}}(2t_{1})^{2}G(t_{1})+y_{1}^{\prime}f_{t_{1}}(j)\delta_{L^{\prime}}(2t_{1})^{2}G^{\prime}(t_{1})$
$\displaystyle\qquad=f_{t_{1}}(j)\bigg{[}y_{1}\delta_{L^{\prime}}(2t_{1})^{2}G(t_{1})+y_{1}^{\prime}\sqrt{-1}\frac{j}{n}\delta_{L^{\prime}}(2t_{1})^{2}G(t_{1})$
$\displaystyle\qquad\qquad\qquad\qquad-y_{1}^{\prime}\sqrt{-1}\frac{k\ell
q_{0}}{n}\big{(}1-e_{n}(\ell
q_{0}t_{1})\big{)}^{-1}\delta_{L^{\prime}}(2t_{1})^{2}G(t_{1})+y_{1}^{\prime}\delta_{L^{\prime}}(2t_{1})^{2}G^{\prime}(t_{1})\bigg{]}\,,$

where in the final line we substituted (9.16). Now since
$f_{t_{1}}(j+L^{\prime})=e_{n}(L^{\prime}t_{1})f_{t_{1}}(j)$, we can eliminate
all but the second term inside the brackets by multiplying both sides by
$e_{n}(L^{\prime}t_{1})$ and subtracting the result from the equation with $j$
replaced with $j+L^{\prime}$. We thus obtain

$\displaystyle\frac{1}{2}\Big{(}D^{\prime}_{-t_{1}}\circ D_{t_{2}}\circ
D_{-t_{2}}\circ\cdots\circ D_{t_{m}}\circ D_{-t_{m}}\circ\Delta_{\ell
q_{0}}^{k}\,\psi\Big{)}(j+L^{\prime})$ $\displaystyle\qquad\qquad-
e_{n}(L^{\prime}t_{1})\times\frac{1}{2}\Big{(}D^{\prime}_{-t_{1}}\circ
D_{t_{2}}\circ D_{-t_{2}}\circ\cdots\circ D_{t_{m}}\circ
D_{-t_{m}}\circ\Delta_{\ell q_{0}}^{k}\,\psi\Big{)}(j)$
$\displaystyle\qquad=y_{1}^{\prime}\sqrt{-1}\frac{L^{\prime}}{n}\delta_{L^{\prime}}(2t_{1})^{2}G(t_{1})f_{t_{1}}(j).$

Recalling our definitions of $\delta_{L^{\prime}}(2t_{1}),G(t_{1}),$ and
$f_{t_{1}}(j)$, the claimed bound now follows from taking the modulus of both
sides, applying the triangle inequality to the left hand side, and applying
Lemma 9.2 applied at various shifts of $\psi$. ∎

######  Remark 9.4.

For the case that $|y_{i}^{\prime}|\leq n^{-1/16}$ and
$|y_{1}|\gg_{m}n^{-1/8}$ in place of (9.12), we can show the following simpler
analogue of Lemma 9.3 (see also [DNN, Lemma 10.5] for a bivariate variant).

######  Lemma 9.5.

For any positive integers $j,L,L^{\prime}$ and $\ell$ such that $[j,j+k\ell
q_{0}+4({m}-1)L+3L^{\prime}]\subset J$, we have

$\displaystyle\frac{L^{\prime}}{n}\left|y_{1}\big{(}1-e_{n}(\ell
q_{0}t_{1})\big{)}^{k}\prod_{r=2}^{m}\big{(}1-e_{n}(L(t_{1}-t_{r}))\big{)}^{2}\big{(}1-e_{n}(L(t_{1}+t_{r}))\big{)}^{2}\right|$
$\displaystyle\qquad\qquad\qquad\qquad\ll_{K_{*},{\kappa},{m}}\sum_{i=1}^{k}\sum_{a=0}^{4({m}-1)}\sum_{b=0}^{3}\|\psi(j+i\ell
q_{0}+aL+bL^{\prime})\|_{{\mathbb{R}}/{\mathbb{Z}}}+O(2^{k}n^{-1/16}).$ (9.22)

Here the additional bound $2^{k}n^{-1/16}$ on the RHS is caused by applying
triangle inequalities basing on (9.9) (where we use $|y_{i}^{\prime}|\ll
n^{-1/16}$ for all $i$ to bound all the terms involving $\partial_{t}$ by
$O(n^{-1/6})$ and move to the right hand side during the differential
process). The proof of Lemma 9.5 can be carried out exactly the same way we
proved Lemma 9.3, and in fact it is simpler because we don’t have to take care
any of the terms involving $\partial_{t}$ because we started with the variant
of (9.9) without the $\partial_{t}$ term. From Lemma 9.5, by using the
assumption that $|y_{1}|\geq n^{-1/8}$ we can deduce (9.15), and hence
conclude 9.1 the same way.

Before concluding this section, as our approach to prove Proposition 9.1
starts with (9.5), by passing to subintervals of $J$ when needed (where we
note that at least one of such subintervals still has length
$\Omega(n/T^{6}))$, we obtain the following analogue of Theorem of Theorem 3.1
(where we recall $\phi_{j}({\mathbf{x}})$ from (9.1)).

######  Theorem 9.6 (Decay of the truncated characteristic function).

Let $\boldsymbol{t}=(t_{1},\dots,t_{m})\in{\mathbb{R}}^{m}$ be
$n^{\kappa}$-smooth and ${\lambda}$-spread for some ${\kappa}\in(0,1)$ and
$\omega(n^{-1/8{m}})\leq{\lambda}<1$. Then for any index set $I\subset[n]$
with $|I|=O(1)$, and for any fixed $K_{*}<\infty$ and any
$v\in{\mathbb{R}}^{4m}$ with $n^{-1/8}\leq\|v\|_{2}\leq n^{K_{*}}$ the
following holds for sufficiently large $n$

$\prod_{j\notin I}|\phi_{j}({\mathbf{x}})|\leq\exp(-\log^{2}n).$

##  10 Complex coefficients and extensions

###  10.1 Theorem 1.2 when $\xi$ is complex-valued

In the case that the random coefficients are complex-valued, our polynomial
can be written as

$\displaystyle P_{n}(x)$
$\displaystyle=\sum_{k=-n}^{n}(\xi_{k}+\sqrt{-1}\xi_{k}^{\prime})(\cos(kx)+\sqrt{-1}\sin(kx))$
$\displaystyle=\xi_{0}+\sqrt{-1}\xi_{0}^{\prime}+\sum_{k=1}^{n}(\xi_{k}+\xi_{-k})\cos(kx)-(\xi_{k}^{\prime}-\xi_{-k}^{\prime})\sin(kx)$
$\displaystyle+\sqrt{-1}\sum_{k=1}^{n}(\xi_{k}^{\prime}+\xi_{-k}^{\prime})\cos(kx)+(\xi_{k}-\xi_{-k})\sin(kx)$

where $\xi_{k},\xi_{k}^{\prime}$ are iid copies $\xi$. By limiting to only the
imaginary part, the corresponding random walk of interest is

$T_{n}(\boldsymbol{t}):=\sum_{j=1}^{n}\xi_{j}^{(1)}\boldsymbol{u}_{j}+\xi_{j}^{(2)}\boldsymbol{v}_{j}$

where $\xi_{j}^{(1)},\xi_{j}^{(2)}$ are independent sub-Gaussian of mean zero
and variance one with the property that
$\xi_{j}^{(1)}-\xi_{j}^{{}^{\prime}(1)},\xi_{j}^{(2)}-\xi_{j}^{{}^{\prime}(2)}$
have the same distribution (here $\xi_{j}^{{}^{\prime}(1)}$ and
$\xi_{j}^{{}^{\prime}(2)}$ are independent copies of $\xi_{j}^{(1)}$ and
$\xi_{j}^{(2)}$ respectively), and where for a fixed tuple
$\boldsymbol{t}=(t_{1},\dots,t_{m})\in{\mathbb{R}}^{m}$ and $j\in{\mathbb{Z}}$
we denote the vectors (see also (3.1))

$\qquad{\boldsymbol{u}}_{j}={\boldsymbol{u}}_{j}(\boldsymbol{t}):=\big{(}{\boldsymbol{a}}_{j}\,,\,(j/n){\boldsymbol{b}}_{j}\big{)},\
\qquad{\boldsymbol{v}}_{j}={\boldsymbol{v}}_{j}(\boldsymbol{t}):=\big{(}{\boldsymbol{b}}_{j}\,,\,-(j/n){\boldsymbol{a}}_{j}\big{)}.$
(10.1)

Because this random walk is only on ${\mathbb{R}}^{2m}$ with the steps
$\boldsymbol{u}_{j},\boldsymbol{v}_{j}$ compensating each other, we can
establish all of our previous results under the following weakly spreading
condition.

######  Definition 10.1.

For $m\geq 2$ and ${\lambda}>0$, we say
$\boldsymbol{t}=(t_{1},\dots,t_{m})\in{\mathbb{R}}^{m}$ is weakly
${\lambda}$-spread if

$\Big{\|}\frac{t_{r}-t_{r^{\prime}}}{2\pi
n}\Big{\|}_{{\mathbb{R}}/{\mathbb{Z}}}\geq\frac{{\lambda}}{n}\qquad\forall\,1\leq
r<r^{\prime}\leq{m}.$

Under this condition we have the following analog of Theorem 3.1.

######  Theorem 10.2 (Decay of the characteristic function).

Let $\boldsymbol{t}=(t_{1},\dots,t_{m})\in{\mathbb{R}}^{m}$ be
$n^{\kappa}$-smooth and weakly ${\lambda}$-spread for some ${\kappa}\in(0,1)$
and $\omega(n^{-1/8{m}})\leq{\lambda}<1$. Then for any fixed $K_{*}<\infty$
and any $\boldsymbol{x}\in{\mathbb{R}}^{2m}$ with
$n^{-1/8}\leq\|\boldsymbol{x}\|_{2}\leq n^{K_{*}}$,

$|{\mathbf{E}}e(\langle
T_{n}(\boldsymbol{t}),\boldsymbol{x}\rangle)|\leq\exp(-\log^{2}n)$

for all $n$ sufficiently large depending on $K_{*},m,\kappa,$ and the sub-
Gaussian constants.

We next sketch the main idea to prove this result. Fix a vector
$n^{-1/8}\leq\|(\boldsymbol{y},\boldsymbol{y}^{\prime})\|_{2}\leq n^{K_{*}}$,
recalling (9.3), we further denote

$\psi^{\prime}(j):=\psi^{\prime}(j;\boldsymbol{t})=\langle\boldsymbol{b}_{j},\boldsymbol{y}\rangle-(j/n)\langle\boldsymbol{a}_{j},\boldsymbol{y}^{\prime}\rangle=\sum_{r=1}^{m}y_{r}\sin(jt_{r}/n)+y^{\prime}_{r}(j/n)\cos(jt_{r}/n)\,.$
(10.2)

The main proposition is the following analog of Proposition 9.1.

######  Proposition 10.3.

Let $\boldsymbol{t}=(t_{1},\dots,t_{r})\in{\mathbb{R}}^{m}$ be
$n^{{\kappa}}$-smooth and assume that $\boldsymbol{t}$ is weakly
${\lambda}$-spread for some ${\kappa}\in(0,1)$ and
$\omega(n^{-1/8{m}})\leq{\lambda}<1$. Then

$\sum_{j=0}^{n}\|\psi(j)\|_{{\mathbb{R}}/{\mathbb{Z}}}^{2}+\sum_{j=0}^{n}\|\psi^{\prime}(j)\|_{{\mathbb{R}}/{\mathbb{Z}}}^{2}>\log^{4}n.$

We next sketch the proof, omitting most details. We follow the proof of
Proposition 9.1 with some simplifications, that instead of focusing on
$(\Delta^{k}_{\ell q_{0}}\psi)(j)$ as the real part of
$\sum_{r=1}^{m}y_{r}f_{j,\ell}(t_{r})+y_{r}^{\prime}\partial_{t_{r}}f_{t_{r},\ell}(j)$
in (9.11) we can study the sum directly. This would allow use to shorten the
differential process significantly, namely in the proof of Lemma 9.3 we will
only need to consider $D_{t_{1}}^{\prime}\circ D_{t_{2}}\circ\cdots\circ
D_{t_{m}}$ (without negative perturbations), leading to a simpler
multiplicative factor
$\prod_{r=2}^{m}\big{(}1-e_{n}(L(t_{1}-t_{r}))\big{)}^{2}$ (without
$(1-e_{n}(L(t_{1}+t_{r})))^{2}$), hence justifying the weakly spreadness
condition.

Finally, one can similarly prove Lemma 3.6, Theorem 3.2, and Theorem 3.4 for
the random walk $T_{n}(\boldsymbol{t})$ above under the weakly spreadness
condition on $\boldsymbol{t}$. Using these results, we can now conclude the
proof of Proposition 2.5 for the complex-valued case as in Section 5 where we
can now allow the $x_{\alpha_{i}}$ to vary entirely over $[-\pi,\pi]$.

###  10.2 Other extensions

As noted in Remark 1.3, with minor modifications our arguments extend Theorem
1.2 to $P_{n}$ of the general form $P_{n}(x)=|J_{n}|^{-1/2}\sum_{j\in
J_{n}}\xi_{j}e(jx)$ for any sequence of finite intervals
$J_{n}\subset{\mathbb{Z}}$ with $|J_{n}|\to\infty$. By multiplying by the
phase $e(-n_{0}x)$, which does not change the minimum modulus, where
$J=[n_{0},n_{1}]$, one sees it suffices to consider the form

$P_{n}(x)=\frac{1}{\sqrt{n+1}}\sum_{j=0}^{n}\xi_{j}e(jx).$ (10.3)

Our arguments also extend to another well-studied class of trigonometric
polynomials, of the form

$P_{n}(x)=\frac{1}{\sqrt{n+a}}\bigg{[}\sqrt{a}\xi_{0}+\sum_{j=1}^{n}\xi_{j}\cos(jx)+\eta_{j}\sin(jx)\bigg{]}\,,$
(10.4)

where the variables $\xi_{j},\eta_{j}$ are iid copies of a random variable
$\xi$, and $a>0$ is a fixed parameter. We note that for this model it is
natural to focus only on the complex $\xi$ case as otherwise $P_{n}$ is likely
to have roots.

######  Theorem 10.4.

Theorem 1.2 extends to hold for $P_{n}$ of the forms (10.3) and (10.4).

For the model (10.4), by combining with Theorem 1.1 we obtain the following:

######  Corollary 10.5.

The limit (1.6) holds also for the model (10.4) with $\xi$ a complex variable
as in Theorem 1.2, and $a=1/2$.

###### Proof.

From Theorem 10.4 it suffices to verify that (1.6) holds under
${\mathbf{P}}_{{\mathcal{N}}_{{\mathbb{R}}}(0,1)}$. Note that under this
measure, $\xi_{j},j\geq 0$ and $\eta_{j},j\geq 1$ are iid standard complex
Gaussians. Set $\zeta_{0}=\xi_{0}$ and for $1\leq j\leq n$ set
$\zeta_{j}:=\frac{1}{\sqrt{2}}(\xi_{j}+\eta_{j})$,
$\zeta_{-j}:=\frac{1}{\sqrt{2}}(\xi_{j}-\eta_{j})$. From the rotational
invariance of the complex Gaussian law it follows that $\zeta_{j},-n\leq j\leq
n$ are iid standard complex Gaussians. Then one verifies that with the change
of variables, (10.4) becomes

$P_{n}(x)=\frac{1}{\sqrt{2n+2a}}\sum_{j=-n}^{n}\zeta_{j}e(jx).$

The claim now follows from the complex Gaussian case of Theorem 1.1 and the
choice $a=1/2$. ∎

We comment on the minor modifications of the proof of Theorem 1.2 that are
needed to obtain Theorem 10.4. The probabilistic Lemmas 2.1 and 2.4 follow
from straightforward modifications. Lemma 2.2 is deterministic and does not
depend on the specific form of $P_{n}$ after conditioning on the good event.
The remainder of the argument only depends on the specific model through the
the matrix $W$ in the definition (3.2) of the random walks
$S_{n}(\boldsymbol{t})$, and the only proofs that need modification are those
of Lemma 3.6 and Theorem 3.1. For the model (10.4), we may condition on
$\xi_{0}$ and $\eta_{j},j\geq 1$. As the trigonometric series is now real, we
only need to consider a $2m$-dimensional walk of the form

$\sum_{j=1}^{n}\xi_{j}\boldsymbol{v}_{j}$

with notation as in (10.1). The $n\times m$ matrix $V$ with rows
$\boldsymbol{v}_{j}$ is a submatrix of $W_{[-n,n]}$ as defined in (3.1) one
checks that the argument for Lemma 3.6 yields the same bound on the smallest
singular value of $V$. Moreover, the proof of Theorem 3.1 began by reduction
of the problem to the submatrix $V$ (see (9.3)), so the result also holds in
this case.

##  Appendix A Separation of near-minimizers

In this appendix we prove Lemma 2.2, restated below, along similar lines to
the proof of [YZ, Lemma 2.11].

######  Lemma A.1.

On the event ${\mathcal{G}}_{2}({K_{0}}/2)$ we have

  1. (i)

If ${\mathcal{A}}_{\alpha}$ and ${\mathcal{A}}_{\alpha+1}$ hold, then

$Y_{\alpha}\in[\frac{\pi}{N}-\frac{\pi}{N\log^{{K_{0}}/4}n},\frac{\pi}{N}].$

  2. (ii)

Furthermore, ${\mathcal{A}}_{\alpha}$ and ${\mathcal{A}}_{\alpha^{\prime}}$
cannot hold simultaneously as long as

$2\leq|\alpha^{\prime}-\alpha|\leq\frac{n}{\log^{3{K_{0}}}n}.$

###### Proof.

We first show (i). Assume that ${\mathcal{A}}_{\alpha}$ holds and
$Y_{\alpha}\in[0,\frac{\pi}{N}-\frac{\pi}{N\log^{{K_{0}}/4}n})$. Then

$\displaystyle|F_{\alpha}(x_{\alpha}+\pi/N)|=|Z_{\alpha}/n+(\pi/N-Y_{\alpha})P^{\prime}(x_{\alpha})|$
$\displaystyle\geq|(\pi/N-Y_{\alpha})P^{\prime}(x_{\alpha})|-|Z_{\alpha}|/n$
$\displaystyle\gg\frac{1}{N\log^{{K_{0}}/4}n}\times\frac{n}{\log^{{K_{0}}/2}n}-\frac{\log
n}{n}$ $\displaystyle\gg\frac{\log^{{K_{0}}/4}n}{n}-\frac{\log
n}{n}\gg\frac{\log^{{K_{0}}/4}n}{n}.$

Now for $x\in I_{\alpha+1}$ and under ${\mathcal{G}}_{2}({K_{0}}/2)$

$\displaystyle|F_{\alpha+1}(x)-F_{\alpha}(x)|$
$\displaystyle\leq|F_{\alpha+1}(x)-P(x)|+|F_{\alpha}(x)-P(x)|$
$\displaystyle\ll N^{-2}\sup_{x\in[-\pi,\pi]}|P^{\prime\prime}(x)|$
$\displaystyle\ll\frac{\log^{3{K_{0}}}n}{n^{2}}.$

So if $x\in I_{\alpha+1}$ then

$\displaystyle|F_{\alpha+1}(x)|$
$\displaystyle\geq|F_{\alpha}(x)|-|F_{\alpha+1}(x)-F_{\alpha}(x)|$
$\displaystyle\geq|F_{\alpha}(x_{\alpha}+\pi/N)|-|F_{\alpha+1}(x)-F_{\alpha}(x)|$
$\displaystyle\gg\frac{\log^{{K_{0}}/4}n}{n},$

where $|F_{\alpha}(x)|\geq|F_{\alpha}(x_{\alpha}+\pi/N)|$ because
$x_{\alpha}+\pi/N$ is closer than $x$ to the minimizer
$x_{\alpha}+Y_{\alpha}$. The above implies that
$|Z_{\alpha+1}|=n|F_{\alpha+1}(Y_{\alpha+1}+x_{\alpha+1})|>\log n$ and hence
that ${\mathcal{A}}_{\alpha+1}$ does not hold.

We turn to prove (ii). For $x\in I_{\alpha^{\prime}}$ we have

$\displaystyle|F_{\alpha}(x)-F_{\alpha^{\prime}}(x)|$
$\displaystyle\leq|F_{\alpha}(x)-P(x)|+|F_{\alpha^{\prime}}(x)-P(x)|$
$\displaystyle\ll(x_{\alpha}-x_{\alpha^{\prime}})^{2}\sup_{x\in[-\pi,\pi]}|P^{\prime\prime}(nx)|$
$\displaystyle\leq(x_{\alpha}-x_{\alpha^{\prime}})^{2}n^{2}\log^{{K_{0}}/2}n.$

On the other hand, on ${\mathcal{A}}_{\alpha}$, for all $x\in
I_{\alpha^{\prime}}$

$\displaystyle|F_{\alpha}(x)|\geq|F_{\alpha}(x_{\alpha^{\prime}}-\pi/N)|$
$\displaystyle\geq|F_{\alpha}(x_{\alpha^{\prime}}-\pi/N)-F_{\alpha}(Y_{a})|-|F_{\alpha}(Y_{a})|$
$\displaystyle\geq|(x_{\alpha^{\prime}}-\pi/N-Y_{\alpha})P^{\prime}(x_{\alpha})|-|Z_{\alpha}|/n$
$\displaystyle\gg
n|x_{\alpha^{\prime}-1}-x_{\alpha}|\log^{-{K_{0}}/2}n-\frac{\log n}{n}$
$\displaystyle\gg n|x_{\alpha^{\prime}-1}-x_{\alpha}|\log^{-{K_{0}}/2}n.$

Thus for all $x\in I_{\alpha^{\prime}}$,

$\displaystyle|F_{\alpha^{\prime}}(x)|$
$\displaystyle\geq|F_{\alpha}(x)|-(x_{\alpha}-x_{\alpha^{\prime}})^{2}n^{2}\log^{{K_{0}}/2}n$
$\displaystyle\gg|x_{\alpha^{\prime}-1}-x_{\alpha}|n\log^{-{K_{0}}/2}n-(x_{\alpha}-x_{\alpha^{\prime}})^{2}n^{2}\log^{{K_{0}}/2}n$
$\displaystyle\gg
n|x_{\alpha^{\prime}-1}-x_{\alpha}|(\log^{-{K_{0}}/2}n-4|x_{\alpha^{\prime}-1}-x_{\alpha}|n\log^{{K_{0}}/2}n)$
$\displaystyle\gg
n|x_{\alpha^{\prime}-1}-x_{\alpha}|(\log^{-{K_{0}}/2}n-4n^{-1}\log^{3{K_{0}}/2}n)$
$\displaystyle\gg|x_{\alpha^{\prime}-1}-x_{\alpha}|n\log^{-{K_{0}}/2}n\gg\frac{\log^{{K_{0}}/2}n}{n},$

implying $|Z_{\alpha^{\prime}}|>\log n$ and hence that
${\mathcal{A}}_{\alpha^{\prime}}$ does not hold. ∎

## Acknowledgments

We thank Pavel Bleher, Yen Do, Oanh Nguyen, Oren Yakir and Ofer Zeitouni for
helpful discussions and comments, and to Yakir and Zeitouni for showing us an
early draft of their work [YZ] on the Gaussian case. This project was
initiated at the American Institute of Mathematics meeting “Zeros of random
polynomials” in August 2019, where Bleher and Zeitouni were also participants.
In particular, the idea used here and in [YZ] to study local linearizations
emerged from those discussions. We thank the workshop organizers and the
Institute for providing a stimulating research environment.

## References

  * [ABB17] L.-P. Arguin, D. Belius, and P. Bourgade.  Maximum of the characteristic polynomial of random unitary matrices.  Comm. Math. Phys., 349(2):703–751, 2017.
  * [ABB+19] L.-P. Arguin, D. Belius, P. Bourgade, M. Radziwiłł, and K. Soundararajan.  Maximum of the Riemann zeta function on a short interval of the critical line.  Comm. Pure Appl. Math., 72(3):500–535, 2019.
  * [ABR] L.-P. Arguin, P. Bourgade, and M. Radziwiłł.  The Fyodorov–Hiary–Keating Conjecture. i.  Preprint, arXiv:2007.00988.
  * [AT07] R. J. Adler and J. E. Taylor.  Random fields and geometry.  Springer Monographs in Mathematics. Springer, New York, 2007.
  * [AW09] J.-M. Azaïs and M. Wschebor.  Level sets and extrema of random processes and fields.  John Wiley & Sons, Inc., Hoboken, NJ, 2009.
  * [BBM+20] P. Balister, B. Bollobás, R. Morris, J. Sahasrabudhe, and M. Tiba.  Flat Littlewood polynomials exist.  Ann. of Math. (2), 192(3):977–1004, 2020.
  * [BCP19] V. Bally, L. Caramellino, and G. Poly.  Non universality for the variance of the number of real roots of random trigonometric polynomials.  Probab. Theory Related Fields, 174(3-4):887–927, 2019.
  * [BD04] P. Bleher and X. Di.  Correlations between zeros of non-Gaussian random polynomials.  Int. Math. Res. Not., (46):2443–2484, 2004.
  * [BG05] A. Böttcher and S. M. Grudsky.  Structured condition numbers of large Toeplitz matrices are rarely better than usual condition numbers.  Numer. Linear Algebra Appl., 12(2-3):95–102, 2005.
  * [BL16] M. Biskup and O. Louidor.  Extreme local extrema of two-dimensional discrete Gaussian free field.  Comm. Math. Phys., 345(1):271–304, 2016.
  * [BP31] A. Bloch and G. Pólya.  On the Roots of Certain Algebraic Equations.  Proc. London Math. Soc. (2), 33(2):102–114, 1931.
  * [BR10] R. N. Bhattacharya and R. R. Rao.  Normal approximation and asymptotic expansions, volume 64 of Classics in Applied Mathematics.  Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2010.  Updated reprint of the 1986 edition [ MR0855460], corrected edition of the 1976 original [ MR0436272].
  * [CGS] X. Chen, C. Garban, and A. Shekhar.  A new proof of liggett’s theorem for non-interacting brownian motions.  Preprint, arXiv:2012.03914.
  * [CMN18] R. Chhaibi, T. Madaule, and J. Najnudel.  On the maximum of the ${\rm C}\beta{\rm E}$ field.  Duke Math. J., 167(12):2243–2345, 2018.
  * [CNYZ] N. A. Cook, H. H. Nguyen, O. Yakir and O. Zeitouni, Universality of Poisson limits for moduli of roots of Kac polynomials, arXiv preprint, 2021.
  * [CZ20] N. Cook and O. Zeitouni.  Maximum of the characteristic polynomial for a random permutation matrix.  Comm. Pure Appl. Math., 73(8):1660–1731, 2020.