\chapter{A local limit theorem for the linearized increments}\label{s:llt}

The goal of this section is to prove \zcref{p:llt}, whose normalization is explained heuristically in \zcref{s:ov-resampling}. Recall from \zcref{s:reduction} that, for a $k$-tuple $\mathbf i$, the vector $S_{\mathbf i}$ is a sum of $m = 2 \lfloor \tau/8 \rfloor$ increments that are independent and identically distributed conditionally on $H$. The central limit theorem describes $S_{\mathbf i}$ on the scale $\tau^{1/2}$, but \zcref{p:llt} concerns the probability that $S_{\mathbf i} + x$ belongs to a bounded set, which is a statement on the unit scale. For sums of independent copies of a fixed law, local limit theorems of this kind hold when the law is nonlattice \cite{stone1965local}. Here the law of an increment depends on $N$ and on $H$, and the main task of this section is to show that it stays away from lattice laws, uniformly over $H$ outside an event of small probability.

This is a genuine issue when $X$ is discrete. Suppose, for example, that $X$ takes the values $1$ and $-1$, so that $Y - X_{ab} \in \{-2, 0, 2\}$, and that every coordinate of $u_i$ and $u_{i + 1}$ has modulus $N^{-1/2}$. Then every $D^{(i)}_{ab}$ belongs to $\{(\pm 2, 0), (0, \pm 2)\}$, and $S_i$ takes values in the lattice $4 \Z^2$. The conclusion of \zcref{p:llt} would then fail for test functions supported near $(2, 2)$, although such eigenvectors satisfy the delocalization bound in the definition of $\mathcal G_\eps$.

After computing the moments of one increment in \zcref{s:llt-moments}, we show in \zcref{s:llt-fewvalues} that with overwhelming probability every unit eigenvector of $H$ is far, in a normalized $\ell^2$ norm, from all vectors whose coordinates take at most a small power of $\tau$ distinct values. In \zcref{s:llt-nonlattice}, we show by a deterministic argument that this property prevents the phases in the characteristic function of one increment from concentrating near $2 \pi \Z$. A symmetrization in \zcref{s:llt-charfunction} then bounds the squared modulus of this characteristic function away from $1$ at all frequencies between a small negative power and a small positive power of $N$. With the parameters chosen in \zcref{s:llt-sums}, this bound reads $1 - c \tau^{-1/4}$. This bound is the main input to the local limit theorem for sums of increments, \zcref{l:llt}, which we prove in \zcref{s:llt-sums} by Fourier inversion. Finally, in \zcref{s:llt-largegap} we add a large deviation estimate for pairs with large gaps and complete the proof of \zcref{p:llt}. Throughout this section, we fix an integer $k \ge 1$.

\section{Notation and moments of one increment}\label{s:llt-moments}

Throughout \zcref{s:llt}, $\mathbf i = (i_1, \dots, i_k)$ denotes a $k$-tuple of integers in $[N - 1]$ such that $i_{j + 1} \ge i_j + 2$ for all $j \in [k - 1]$. For $w \in \R^{2k}$, we let $w_j = (w_{j, 1}, w_{j, 2}) \in \R^2$ denote its $j$-th block, so that $w = (w_1, \dots, w_k)$, and we let $w(\eta)$ denote its $\eta$-th coordinate, where $\eta \in [2k]$. We let $U_{\mathbf i}$ denote the $N \times 2k$ matrix with columns $u_{i_1}, u_{i_1 + 1}, \dots, u_{i_k}, u_{i_k + 1}$, in this order. Since these $2k$ indices are distinct, we have $U_{\mathbf i}^T U_{\mathbf i} = \Id_{2k}$. For $b \in [N]$, let $r_b \in \R^{2k}$ denote the $b$-th row of $N^{1/2} U_{\mathbf i}$, so that $r_{b, j} = N^{1/2} (u_{i_j}(b), u_{i_j + 1}(b))$. The relation $U_{\mathbf i}^T U_{\mathbf i} = \Id_{2k}$ is equivalent to
\begin{equation}\label{e:llt-rows}
\frac{1}{N} \sum_{b = 1}^N r_b r_b^T = \Id_{2k}.
\end{equation}

For $\xi \in \R^{2k}$, let $\Gamma(\xi)$ denote the block-diagonal $2k \times 2k$ matrix whose $j$-th diagonal block is
\begin{equation}\label{e:llt-gamma}
\begin{pmatrix} \xi_{j, 1} & \xi_{j, 2} \\ \xi_{j, 2} & -\xi_{j, 1} \end{pmatrix}.
\end{equation}
For $k = 1$, this defines $\Gamma(\xi_j)$ for $\xi_j \in \R^2$, and we have $\Gamma(\xi) = \diag(\Gamma(\xi_1), \dots, \Gamma(\xi_k))$. The matrix $\Gamma(\xi_j)$ is symmetric with eigenvalues $|\xi_j|$ and $-|\xi_j|$. Hence $\|\Gamma(\xi)\| = \max_j |\xi_j| \le |\xi|$, and $\Gamma(\xi_j)$ is invertible with $\|\Gamma(\xi_j)^{-1}\| = |\xi_j|^{-1}$ when $\xi_j \neq 0$. The map $\xi \mapsto \Gamma(\xi)$ is linear, and we let $\Gamma_\eta$ denote its value at the $\eta$-th standard basis vector of $\R^{2k}$, so that $\Gamma(\xi) = \sum_{\eta = 1}^{2k} \xi(\eta) \Gamma_\eta$.

Recall the vectors $D^{(i)}_{ab} \in \R^2$ from \eqref{e:reduction-D}. In \zcref{s:llt}, we use the formula on the right side of \eqref{e:reduction-D} to define $D^{(i)}_{ab}$ for all $a, b \in [N]$, so that $D^{(i)}_{ab} = D^{(i)}_{ba}$, and we let $D^{(\mathbf i)}_{ab} \in \R^{2k}$ denote the vector with blocks $D^{(i_1)}_{ab}, \dots, D^{(i_k)}_{ab}$. Expanding the quadratic forms on the right side and comparing with the definition of $D^{(i_j)}_{ab}$, we find
\begin{equation}\label{e:llt-phase}
\xi \cdot D^{(\mathbf i)}_{ab} = r_a^T \Gamma(\xi) r_b, \qquad a, b \in [N], \quad \xi \in \R^{2k}.
\end{equation}
Further, after identifying $\R^2$ with $\C$, we have
\begin{equation}
D^{(i_j)}_{ab} = N \bigl( u_{i_j}(a) + \iu u_{i_j + 1}(a) \bigr) \bigl( u_{i_j}(b) + \iu u_{i_j + 1}(b) \bigr),
\end{equation}
and therefore
\begin{equation}\label{e:llt-dmodulus}
|D^{(i_j)}_{ab}| = |r_{a, j}| \, |r_{b, j}|, \qquad a, b \in [N], \quad j \in [k].
\end{equation}

\begin{definition}\label{d:llt-increment}
Let $(a, b)$ be a random pair with the uniform distribution on $\{(a', b') \in [N]^2 : a' < b'\}$, and let $Y$ be a copy of $X$, such that $H$, $(a, b)$, and $Y$ are independent. We define the \emph{increment}
\begin{equation}\label{e:llt-increment}
J = (Y - X_{ab}) D^{(\mathbf i)}_{ab} \in \R^{2k}.
\end{equation}
We define the conditional mean $\bar J = \E[J \mid H]$, the conditional covariance $\Sigma_H = \E[(J - \bar J)(J - \bar J)^T \mid H]$, and the conditional characteristic function
\begin{equation}\label{e:llt-charfunction}
\Phi_H(\xi) = \E\bigl[ e^{\iu \xi \cdot J} \bigm| H \bigr], \qquad \xi \in \R^{2k}.
\end{equation}
For an integer $n \ge 1$, let $S^{(n)}$ denote a random vector in $\R^{2k}$ whose conditional law given $H$ is the law of a sum of $n$ independent random vectors, each with the conditional law of $J$ given $H$. We let $\Phi_Y$ denote the characteristic function of $Y$, so that $\Phi_Y(t') = \E e^{\iu t' Y}$ for $t' \in \R$.
\end{definition}

These objects depend on $\mathbf i$, which we suppress from the notation. By the definition of $S^{(n)}$, we have
\begin{equation}\label{e:llt-charsum}
\E\bigl[ e^{\iu \xi \cdot S^{(n)}} \bigm| H \bigr] = \Phi_H(\xi)^n, \qquad \xi \in \R^{2k}.
\end{equation}
Recall from \zcref{s:reduction} that $S_{\mathbf i} = \sum_{l = 1}^m (Y_l - X_{a_l b_l}) D^{(\mathbf i)}_{a_l b_l}$, where $X_{a_l b_l}$ is the entry of $H$ for every $l$, also when a position is selected more than once. Conditionally on $H$, the $m$ summands are therefore independent, and each has the conditional law of $J$. Hence the conditional law of $S_{\mathbf i}$ given $H$ is that of $S^{(m)}$.

We next introduce the event on which the estimates below take place. It involves the matrix $\mathring X$ below, which records the fluctuations of the squared entries; these fluctuations appear in the covariance of $J$.

\begin{definition}\label{d:llt-regular}
Let $\mathring X$ denote the $N \times N$ real symmetric matrix with zero diagonal and entries $\mathring X_{ab} = X_{ab}^2 - 1$ for $a \neq b$. For $\eps > 0$, we let $\mathcal A^{\mathrm{reg}}_N(\eps)$ denote the event that
\begin{equation}\label{e:llt-regular}
H \in \mathcal G_\eps, \qquad \max_{a \le b} |X_{ab}| \le N^{\eps}, \qquad \|\mathring X\| \le N^{1/2 + \eps}.
\end{equation}
\end{definition}

Recall from \zcref{d:regular} that $H \in \mathcal G_\eps$ implies $\|H\| \le 3$ and $\|v\|_\infty \le N^{-1/2 + \eps}$ for every unit eigenvector $v$ of $H$. Hence, on $\mathcal A^{\mathrm{reg}}_N(\eps)$, we have for every $k$-tuple $\mathbf i$ and all $a, b \in [N]$ that
\begin{equation}\label{e:llt-rowbound}
|r_{b, j}| \le 2^{1/2} N^{\eps}, \qquad |r_b| \le (2k)^{1/2} N^{\eps}, \qquad |D^{(\mathbf i)}_{ab}| \le 2 k^{1/2} N^{2\eps},
\end{equation}
where the last bound follows from \eqref{e:llt-dmodulus}.

\begin{lemma}\label{l:llt-regular}
For every $\eps > 0$, the event $\mathcal A^{\mathrm{reg}}_N(\eps)$ holds with overwhelming probability.
\end{lemma}

\begin{proof}
The three conditions in \eqref{e:llt-regular} become weaker as $\eps$ increases, so we may assume that $\eps \le 1/4$. By \zcref{p:regularity}, we have $H \in \mathcal G_\eps$ with overwhelming probability. The sub-Gaussian tail bound for $X$ and $Z$ and a union bound over the at most $N^2$ entries give
\begin{equation}\label{e:llt-entrytail}
\Prob\Bigl( \max_{a \le b} |X_{ab}| > N^{\eps/4} \Bigr) \le C_0 N^2 \exp\bigl( -c_0 N^{\eps/2} \bigr),
\end{equation}
which is smaller than every negative power of $N$ for large $N$. This gives the second condition in \eqref{e:llt-regular}.

To bound $\|\mathring X\|$, we truncate the entries at $N^{\eps/4}$ and center them. Set
\begin{equation}
\mathsf c_N = \E\bigl[ (X^2 - 1) \1\{|X| \le N^{\eps/4}\} \bigr] = - \E\bigl[ (X^2 - 1) \1\{|X| > N^{\eps/4}\} \bigr],
\end{equation}
where we used $\E X^2 = 1$. The sub-Gaussian tail of $X$ gives
\begin{equation}
|\mathsf c_N| \le C \exp(-c N^{\eps/2}).
\end{equation}
Recall that $V^{ab} = e_a e_b^T + e_b e_a^T$ for $a < b$, and define
\begin{equation}\label{e:llt-truncated}
A_{ab} = \Bigl( (X_{ab}^2 - 1) \1\{|X_{ab}| \le N^{\eps/4}\} - \mathsf c_N \Bigr) V^{ab}, \qquad \mathring X' = \sum_{a < b} A_{ab}.
\end{equation}
The matrices $A_{ab}$ are independent, centered, and real symmetric. Since $\|V^{ab}\| = 1$ and $|\mathsf c_N| \le 1$ for large $N$, we have $\|A_{ab}\| \le 4 N^{\eps/2}$. Further, $(V^{ab})^2 = e_a e_a^T + e_b e_b^T$, so $\sum_{a < b} \E A_{ab}^2$ is a diagonal matrix, and
\begin{equation}
\Bigl\| \sum_{a < b} \E A_{ab}^2 \Bigr\| \le (N - 1) \E\bigl[ (X^2 - 1)^2 \bigr] \le C N.
\end{equation}

We now use the matrix Bernstein inequality \cite[Theorem~1.4]{tropp2012user}, which we state in the form needed here. Let $(A_{ab})_{a < b}$ be independent, centered, real symmetric random $N \times N$ matrices such that $\lambda_N(A_{ab}) \le R'$ almost surely for all $a < b$. Then for all $t' \ge 0$,
\begin{equation}
\Prob\Bigl( \lambda_N\Bigl( \sum_{a < b} A_{ab} \Bigr) \ge t' \Bigr) \le N \exp\biggl( - \frac{t'^2/2}{\| \sum_{a < b} \E A_{ab}^2 \| + R' t'/3} \biggr).
\end{equation}
We apply it to the matrices $A_{ab}$ and to their negatives, with $R' = 4 N^{\eps/2}$ and $t' = N^{1/2 + \eps}/2$. Our assumption $\eps \le 1/4$ gives $R' t' \le 2N$, and we obtain
\begin{equation}
\Prob\Bigl( \|\mathring X'\| \ge \frac{N^{1/2 + \eps}}{2} \Bigr) \le 2N \exp\bigl( - c N^{2\eps} \bigr).
\end{equation}
When $\max_{a < b} |X_{ab}| \le N^{\eps/4}$, we have
\begin{equation}
\mathring X = \mathring X' + \mathsf c_N \sum_{a < b} V^{ab}, \qquad \text{and hence} \qquad \|\mathring X\| \le \|\mathring X'\| + N^2 |\mathsf c_N| \le \|\mathring X'\| + C N^2 e^{- c N^{\eps/2}}.
\end{equation}
Combining the last two displays with \eqref{e:llt-entrytail}, we conclude that $\|\mathring X\| \le N^{1/2 + \eps}$ with overwhelming probability.
\end{proof}

For $v, v' \in \R^N$, we let $v \odot v' \in \R^N$ denote the vector with coordinates $(v \odot v')(a) = v(a) v'(a)$. The following lemma identifies the first three conditional moments of one increment.

\begin{lemma}\label{l:moments}
Let $0 < \eps \le 1/8$. There exists $C > 0$ such that on $\mathcal A^{\mathrm{reg}}_N(\eps)$, for every $k$-tuple $\mathbf i$,
\begin{equation}\label{e:llt-moments}
\begin{gathered}
|\bar J| \le C N^{-1/2}, \qquad \E\bigl[ |J|^3 \bigm| H \bigr] \le C N^{9 \eps}, \\
\bigl\| \E[J J^T \mid H] - 4 \Id_{2k} \bigr\| + \| \Sigma_H - 4 \Id_{2k} \| \le C N^{3 \eps - 1/2}.
\end{gathered}
\end{equation}
Moreover, on $\mathcal A^{\mathrm{reg}}_N(\eps)$ we have $|J| \le 2 k^{1/2} N^{2 \eps} (|Y| + N^{\eps})$.
\end{lemma}

\begin{proof}
The last claim follows from \eqref{e:llt-increment}, \eqref{e:llt-rowbound}, and $|X_{ab}| \le N^\eps$. We begin with the mean. Since $\E Y = 0$ and $Y$ is independent of $H$ and $(a, b)$, we have
\begin{equation}\label{e:llt-meanformula}
\bar J = - \binom{N}{2}^{-1} \sum_{a < b} X_{ab} D^{(\mathbf i)}_{ab}.
\end{equation}

The main point is that the sum in \eqref{e:llt-meanformula} can be computed exactly with the eigenvalue equation; a bound by absolute values would give only $|\bar J| \le C N^{3\eps}$, while the drift $m \bar J$ must be small on the unit scale. Fix $j \in [k]$, and abbreviate $u = u_{i_j}$ and $v = u_{i_j + 1}$. Recall that $X_{ba} = X_{ab}$ and $X_{aa} = N^{1/2} H_{aa}$, so that
\begin{equation}
\sum_{a, b = 1}^N X_{ab} u(a) u(b) = N^{1/2} u^T H u = N^{1/2} \lambda_{i_j}.
\end{equation}
Separating the diagonal terms, we obtain
\begin{equation}
\sum_{a < b} X_{ab} u(a) u(b) = \frac{1}{2} \Bigl( N^{1/2} \lambda_{i_j} - \sum_{a = 1}^N X_{aa} u(a)^2 \Bigr),
\end{equation}
and the same identity holds with $v$ and $\lambda_{i_j + 1}$ in place of $u$ and $\lambda_{i_j}$. Similarly, since $H v = \lambda_{i_j + 1} v$ and $u^T v = 0$, we have
\begin{equation}
\sum_{a < b} X_{ab} \bigl( u(a) v(b) + v(a) u(b) \bigr) = N^{1/2} u^T H v - \sum_{a = 1}^N X_{aa} u(a) v(a) = - \sum_{a = 1}^N X_{aa} u(a) v(a).
\end{equation}
Inserting these identities into the definition of $D^{(i_j)}_{ab}$, we find
\begin{equation}\label{e:llt-meanidentity}
\sum_{a < b} X_{ab} D^{(i_j)}_{ab} = N \biggl( \frac{N^{1/2} (\lambda_{i_j} - \lambda_{i_j + 1}) - \sum_a X_{aa} (u(a)^2 - v(a)^2)}{2}, \, - \sum_a X_{aa} u(a) v(a) \biggr).
\end{equation}

We have $|X_{aa}| \le N^\eps$ on $\mathcal A^{\mathrm{reg}}_N(\eps)$, and
\begin{equation}
|\lambda_{i_j} - \lambda_{i_j + 1}| \le 2 \|H\| \le 6.
\end{equation}
Hence the norm of the right side of \eqref{e:llt-meanidentity} is bounded by
\begin{equation}
N (3 N^{1/2} + 2 N^{\eps}) \le 5 N^{3/2}.
\end{equation}
Inserting this into \eqref{e:llt-meanformula} gives $|\bar J| \le 20 k^{1/2} N^{-1/2}$.

We now compute the second moment. Since $\E (Y - y)^2 = 1 + y^2$ for $y \in \R$, we have
\begin{equation}\label{e:llt-secondmoment}
\E[J J^T \mid H] = \binom{N}{2}^{-1} \sum_{a < b} (1 + X_{ab}^2) D^{(\mathbf i)}_{ab} (D^{(\mathbf i)}_{ab})^T = \binom{N}{2}^{-1} \sum_{a < b} \bigl( 2 + \mathring X_{ab} \bigr) D^{(\mathbf i)}_{ab} (D^{(\mathbf i)}_{ab})^T.
\end{equation}

To evaluate the first term, observe that $D^{(\mathbf i)}_{ab}(\eta) = r_a^T \Gamma_\eta r_b$ by \eqref{e:llt-phase}. Using \eqref{e:llt-rows} twice and the symmetry of $\Gamma_{\eta'}$, we obtain for $\eta, \eta' \in [2k]$ that
\begin{equation}\label{e:llt-trace}
\begin{split}
\sum_{a, b = 1}^N D^{(\mathbf i)}_{ab}(\eta) D^{(\mathbf i)}_{ab}(\eta') &= \sum_{a = 1}^N r_a^T \Gamma_\eta \Bigl( \sum_{b = 1}^N r_b r_b^T \Bigr) \Gamma_{\eta'} r_a = N \Tr\Bigl( \Gamma_\eta \Gamma_{\eta'} \sum_{a = 1}^N r_a r_a^T \Bigr) \\
&= N^2 \Tr(\Gamma_\eta \Gamma_{\eta'}) = 2 N^2 \delta_{\eta \eta'}.
\end{split}
\end{equation}
In the last equality, we used that $\Gamma_\eta \Gamma_{\eta'} = 0$ when $\eta$ and $\eta'$ belong to different blocks, that $\Gamma_\eta^2$ is the identity on the block of $\eta$, and that $\Gamma_{2j - 1} \Gamma_{2j}$ has trace zero, which can be read off from \eqref{e:llt-gamma}.

Since $D^{(\mathbf i)}_{ab} = D^{(\mathbf i)}_{ba}$ and $\binom{N}{2} = N(N - 1)/2$, the identity \eqref{e:llt-trace} gives
\begin{equation}
2 \binom{N}{2}^{-1} \sum_{a < b} D^{(\mathbf i)}_{ab} (D^{(\mathbf i)}_{ab})^T = \frac{2}{N (N - 1)} \Bigl( 2 N^2 \Id_{2k} - \sum_{a = 1}^N D^{(\mathbf i)}_{aa} (D^{(\mathbf i)}_{aa})^T \Bigr).
\end{equation}
Using $|D^{(\mathbf i)}_{aa}|^2 \le 4 k N^{4\eps}$ from \eqref{e:llt-rowbound}, we conclude that
\begin{equation}\label{e:llt-firstpart}
\Bigl\| 2 \binom{N}{2}^{-1} \sum_{a < b} D^{(\mathbf i)}_{ab} (D^{(\mathbf i)}_{ab})^T - 4 \Id_{2k} \Bigr\| \le \frac{4}{N - 1} + \frac{8 k N^{4 \eps}}{N - 1} \le C N^{4\eps - 1}.
\end{equation}

Next, we bound the contribution of $\mathring X$ to \eqref{e:llt-secondmoment}. Since $\mathring X$ is symmetric with zero diagonal, the entry $(\eta, \eta')$ of this contribution is
\begin{equation}\label{e:llt-xring}
\binom{N}{2}^{-1} \sum_{a < b} \mathring X_{ab} D^{(\mathbf i)}_{ab}(\eta) D^{(\mathbf i)}_{ab}(\eta') = \frac{1}{N (N - 1)} \sum_{a, b = 1}^N \mathring X_{ab} D^{(\mathbf i)}_{ab}(\eta) D^{(\mathbf i)}_{ab}(\eta').
\end{equation}

By the definition of $D^{(i)}_{ab}$, each coordinate $D^{(\mathbf i)}_{ab}(\eta)$ is $N$ times a sum of two terms of the form $\pm v(a) v'(b)$, where $v$ and $v'$ are columns of $U_{\mathbf i}$. Hence the sum on the right side of \eqref{e:llt-xring} is $N^2$ times a sum of four terms of the form $\pm (v_1 \odot v_2)^T \mathring X (v_3 \odot v_4)$, where $v_1, \dots, v_4$ are columns of $U_{\mathbf i}$. Every two columns $v, v'$ of $U_{\mathbf i}$ satisfy, on $\mathcal A^{\mathrm{reg}}_N(\eps)$,
\begin{equation}
\|v \odot v'\|_2 \le \|v\|_\infty \|v'\|_2 \le N^{\eps - 1/2},
\end{equation}
and therefore
\begin{equation}
\bigl| (v_1 \odot v_2)^T \mathring X (v_3 \odot v_4) \bigr| \le \|\mathring X\| \, N^{2\eps - 1} \le N^{3 \eps - 1/2}.
\end{equation}

It follows that the absolute value of \eqref{e:llt-xring} is bounded by
\begin{equation}
\frac{4 N^2 N^{3\eps - 1/2}}{N (N - 1)} \le 8 N^{3 \eps - 1/2}.
\end{equation}
The operator norm of a $2k \times 2k$ matrix is bounded by $2k$ times its largest entry, so \eqref{e:llt-secondmoment} and \eqref{e:llt-firstpart} give
\begin{equation}
\bigl\| \E[J J^T \mid H] - 4 \Id_{2k} \bigr\| \le C N^{4\eps - 1} + 16 k N^{3\eps - 1/2} \le C N^{3 \eps - 1/2},
\end{equation}
where we used $\eps \le 1/8$. Since $\Sigma_H = \E[J J^T \mid H] - \bar J \bar J^T$ and $|\bar J|^2 \le C N^{-1}$, the same bound holds for $\Sigma_H$.

Finally, the bound on $|J|$ and the elementary inequality $(y_1 + y_2)^3 \le 4 (y_1^3 + y_2^3)$ for $y_1, y_2 \ge 0$ give
\begin{equation}
\E\bigl[ |J|^3 \bigm| H \bigr] \le 8 k^{3/2} N^{6 \eps} \E\bigl[ (|Y| + N^\eps)^3 \bigr] \le 32 k^{3/2} N^{6 \eps} \bigl( \E |Y|^3 + N^{3\eps} \bigr) \le C N^{9 \eps}.
\end{equation}
This completes the proof.
\end{proof}

\section{Eigenvectors with few coordinate values}\label{s:llt-fewvalues}

For an integer $n \ge 1$, let $\mathcal V_n$ denote the set of vectors $v \in \R^N$ whose coordinates $v(1), \dots, v(N)$ take at most $n$ distinct values. For $v \in \R^N$, we set
\begin{equation}
\|v\|_{2, N} = \Bigl( \frac{1}{N} \sum_{b = 1}^N v(b)^2 \Bigr)^{1/2} = N^{-1/2} \|v\|_2.
\end{equation}
Observe that $\mathcal V_n$ is the union of the finitely many linear subspaces of vectors that are constant on the blocks of a partition of $[N]$ into at most $n$ blocks. Hence $\mathcal V_n$ is closed, and the infimum of $\|w - v\|_{2, N}$ over $v \in \mathcal V_n$ is attained for every $w \in \R^N$.

The following lemma states that, with overwhelming probability, no delocalized unit eigenvector of $H$ is close to $\mathcal V_n$ when $n$ grows slowly. Its proof follows the net and small-ball arguments developed for the invertibility of random matrices \cite{rudelson2008littlewood, vershynin2014invertibility}.

\begin{lemma}\label{l:fewvalues}
Let $\mathfrak p > 0$ and $\mathfrak a > 4 \mathfrak p$. Let $(\Omega_N)$ and $(K_N)$ be deterministic sequences of positive numbers such that $\Omega_N \to \infty$, $\Omega_N^{\mathfrak p} = o(N)$, $\Omega_N^{\mathfrak a + 1} = o(N^{1/2})$, and $1 \le K_N \le \Omega_N$ for all sufficiently large $N$, and write $\Omega = \Omega_N$ and $K = K_N$. Then there exists $c > 0$ such that for all sufficiently large $N$, the event that $\|H\| \le 3$ and that some unit eigenvector $w$ of $H$ satisfies
\begin{equation}\label{e:llt-fewvalues}
N^{1/2} \|w\|_\infty \le K, \qquad \inf_{v \in \mathcal V_{\lfloor \Omega^{\mathfrak p} \rfloor}} \|N^{1/2} w - v\|_{2, N} \le \Omega^{-\mathfrak a}
\end{equation}
has probability at most $\exp(- c N \log \Omega)$.
\end{lemma}

\begin{proof}
Throughout the proof, we write $n = \lfloor \Omega^{\mathfrak p} \rfloor$, and we take $N$ large enough that $1 \le K \le \Omega$ and $4 \Omega^{-\mathfrak a} \le 1$. We first replace $w$ and its eigenvalue by elements of a deterministic finite set. Suppose that the event in the statement holds. Let $E \in [-3, 3]$ be the eigenvalue of $w$, and choose $v \in \mathcal V_n$ such that $\|N^{1/2} w - v\|_{2, N} \le \Omega^{-\mathfrak a}$. We obtain $\hat v \in \R^N$ from $v$ in two steps. We replace each coordinate $v(b)$ by its closest point in $[-K, K]$; since $|N^{1/2} w(b)| \le K$, this does not increase $|N^{1/2} w(b) - v(b)|$. We then replace the result by the smallest among its closest points in the grid $\Omega^{-\mathfrak a} \Z \cap [-K, K]$, which changes each coordinate by at most $\Omega^{-\mathfrak a}$. Both replacements act on each coordinate through a function of the value of that coordinate, so equal coordinates remain equal. Hence
\begin{equation}
\hat v \in \mathcal V_n, \qquad \|\hat v\|_\infty \le K, \qquad \|N^{1/2} w - \hat v\|_{2, N} \le 2 \Omega^{-\mathfrak a}.
\end{equation}

Set $y = N^{-1/2} \hat v$. Let $E'$ be a closest point to $E$ in $\Omega^{-\mathfrak a} \Z \cap [-3, 3]$. The previous paragraph gives
\begin{equation}\label{e:llt-netvector}
\|y - w\|_2 \le 2 \Omega^{-\mathfrak a}, \qquad \frac{1}{2} \le \|y\|_2 \le 2, \qquad \|y\|_\infty \le K N^{-1/2}.
\end{equation}
Using $(H - E) w = 0$, $\|H - E\| \le 6$, and $|E - E'| \le \Omega^{-\mathfrak a}$, we find
\begin{equation}\label{e:llt-netresidual}
\|(H - E') y\|_2 \le \|(H - E)(y - w)\|_2 + |E - E'| \, \|y\|_2 \le 14 \, \Omega^{-\mathfrak a}.
\end{equation}

Let $\mathcal Y$ denote the set of vectors $y = N^{-1/2} \hat v$ such that $\hat v \in \mathcal V_n$ has all coordinates in $\Omega^{-\mathfrak a} \Z \cap [-K, K]$ and $1/2 \le \|y\|_2 \le 2$. The grid $\Omega^{-\mathfrak a} \Z \cap [-K, K]$ has at most $2 K \Omega^{\mathfrak a} + 1 \le 3 \Omega^{\mathfrak a + 1}$ points. We choose a set of at most $n$ grid values, and we assign one of these values to each coordinate. Counting these choices, we obtain
\begin{equation}\label{e:llt-netcount}
|\mathcal Y| \le \bigl( 3 \Omega^{\mathfrak a + 1} + 1 \bigr)^{n} \, n^N \le \bigl( 4 \Omega^{\mathfrak a + 1} \bigr)^{n} \, n^N.
\end{equation}
The grid $\Omega^{-\mathfrak a} \Z \cap [-3, 3]$ has at most $7 \Omega^{\mathfrak a}$ points. By \eqref{e:llt-netresidual}, the event in the statement is a subset of
\begin{equation}
\bigcup_{y \in \mathcal Y} \, \bigcup_{E' \in \Omega^{-\mathfrak a} \Z \cap [-3, 3]} \bigl\{ \|(H - E') y\|_2 \le 14 \, \Omega^{-\mathfrak a} \bigr\}.
\end{equation}
These vectors and energies are deterministic.

We now fix $y \in \mathcal Y$ and $E' \in \Omega^{-\mathfrak a} \Z \cap [-3, 3]$, and we bound the probability that $\|(H - E') y\|_2 \le 14 \, \Omega^{-\mathfrak a}$. Let $\mathcal T \subset [N]$ be a set of $\lfloor N/2 \rfloor$ indices $b$ for which $|y(b)|$ is largest, with complement $\mathcal T^c = [N] \setminus \mathcal T$. Let $y_{\mathcal T} \in \R^N$ denote the vector with $y_{\mathcal T}(b) = y(b)$ for $b \in \mathcal T$ and $y_{\mathcal T}(b) = 0$ otherwise. The average of $y(b)^2$ over $b \in \mathcal T$ is at least its average over $[N]$, so
\begin{equation}\label{e:llt-topcoordinates}
\|y_{\mathcal T}\|_2^2 \ge \frac{\lfloor N/2 \rfloor}{N} \, \|y\|_2^2 \ge \frac{1}{12}.
\end{equation}
Suppose that $\|(H - E') y\|_2 \le 14 \, \Omega^{-\mathfrak a}$. Then fewer than $N/4$ indices $a \in [N]$ satisfy $|((H - E') y)(a)| > 28 \, \Omega^{-\mathfrak a} N^{-1/2}$. Since $|\mathcal T^c| \ge N/2$, at least $N/4$ indices $a \in \mathcal T^c$ satisfy
\begin{equation}\label{e:llt-smallrow}
\bigl| N^{1/2} \bigl( (H - E') y \bigr)(a) \bigr| \le 28 \, \Omega^{-\mathfrak a}.
\end{equation}

The rows indexed by $\mathcal T^c$ are conditionally independent once we fix the entries outside $\mathcal T^c \times \mathcal T$. Indeed, for $a \in \mathcal T^c$ we have
\begin{equation}\label{e:llt-rowsplit}
N^{1/2} \bigl( (H - E') y \bigr)(a) = \sum_{b \in \mathcal T} X_{ab} y(b) + \chi_a, \qquad \chi_a = \sum_{b \in \mathcal T^c} X_{ab} y(b) - N^{1/2} E' y(a).
\end{equation}
Let $\mathcal F_{\mathcal T}$ denote the $\sigma$-algebra generated by the entries $X_{ab}$, $a \le b$, for which $a$ and $b$ do not lie on opposite sides of the partition $\{\mathcal T, \mathcal T^c\}$. Each $\chi_a$ is $\mathcal F_{\mathcal T}$-measurable. The entries $X_{ab}$ with $a \in \mathcal T^c$ and $b \in \mathcal T$ are off-diagonal, and distinct pairs $(a, b)$ of this kind give distinct entries. Hence these entries are independent copies of $X$, independent of $\mathcal F_{\mathcal T}$. In particular, conditionally on $\mathcal F_{\mathcal T}$, the random variables $\sum_{b \in \mathcal T} X_{ab} y(b) + \chi_a$, $a \in \mathcal T^c$, are independent, because they are functions of disjoint families of these entries.

We bound the conditional probability of \eqref{e:llt-smallrow} for one row with the Berry--Esseen inequality for sums of independent, not necessarily identically distributed, random variables \cite[Chapter~V]{petrov1975sums}. Since $\E X = 0$ and $\E X^2 = 1$, it states that the Kolmogorov distance between the law of $\|y_{\mathcal T}\|_2^{-1} \sum_{b \in \mathcal T} X_{ab} y(b)$ and the standard Gaussian law is bounded by $C_{\mathrm{BE}} \|y_{\mathcal T}\|_2^{-3} \sum_{b \in \mathcal T} \E |X|^3 |y(b)|^3$, where $C_{\mathrm{BE}}$ is an absolute constant. The standard Gaussian probability of a closed interval is bounded by its length times $(2\pi)^{-1/2}$, and the probabilities of an interval under two laws differ by at most twice their Kolmogorov distance. Using \eqref{e:llt-netvector} and \eqref{e:llt-topcoordinates}, we therefore find for every $\chi \in \R$ that
\begin{equation}
\begin{split}
\Prob\Bigl( \Bigl| \sum_{b \in \mathcal T} X_{ab} y(b) + \chi \Bigr| \le 28 \, \Omega^{-\mathfrak a} \Bigr) &\le \frac{56 \, \Omega^{-\mathfrak a}}{(2\pi)^{1/2} \|y_{\mathcal T}\|_2} + \frac{2 C_{\mathrm{BE}} \E |X|^3 \, \|y\|_\infty \|y_{\mathcal T}\|_2^2}{\|y_{\mathcal T}\|_2^3} \\
&\le C \bigl( \Omega^{-\mathfrak a} + K N^{-1/2} \bigr).
\end{split}
\end{equation}
Recall that $K \le \Omega$ and $\Omega^{\mathfrak a + 1} N^{-1/2} \to 0$. Hence the right side is bounded by $C_2 \Omega^{-\mathfrak a}$ for some $C_2 > 0$ and all large $N$, and we take $N$ large enough that $C_2 \Omega^{-\mathfrak a} \le 1$.

We apply this bound with $\chi = \chi_a$, use the conditional independence of the rows, and take a union bound over the at most $2^N$ sets of $\lceil N/4 \rceil$ rows in $\mathcal T^c$. This gives
\begin{equation}
\Prob\bigl( \|(H - E') y\|_2 \le 14 \, \Omega^{-\mathfrak a} \bigm| \mathcal F_{\mathcal T} \bigr) \le 2^N \bigl( C_2 \Omega^{-\mathfrak a} \bigr)^{N/4}.
\end{equation}
The right side is deterministic, so the same bound holds for the unconditional probability.

Combining the last display with \eqref{e:llt-netcount} and the bound on the number of energies, we find that the logarithm of the probability of the event in the statement is bounded by
\begin{equation}\label{e:llt-fewvalues-exponent}
n \log\bigl( 4 \Omega^{\mathfrak a + 1} \bigr) + N \log n + \log\bigl( 7 \Omega^{\mathfrak a} \bigr) + N \log 2 + \frac{N}{4} \log C_2 - \frac{\mathfrak a}{4} N \log \Omega.
\end{equation}
We have $N \log n \le \mathfrak p N \log \Omega$. Since $n \le \Omega^{\mathfrak p} = o(N)$ and $\log \Omega \to \infty$, the first, third, fourth, and fifth terms are $o(N \log \Omega)$. Hence \eqref{e:llt-fewvalues-exponent} is bounded by $- (\mathfrak a/4 - \mathfrak p - o(1)) N \log \Omega$, and the lemma holds with $c = (\mathfrak a - 4 \mathfrak p)/8$.
\end{proof}

\begin{remark}\label{r:llt-fewvalues}
The vectors $y \in \mathcal Y$ and energies $E'$ in the union bound in the proof of \zcref{l:fewvalues} are deterministic, and the eigenvector $w$ enters only through the existence of a nearby pair $(y, E')$. This is why the lemma applies to the eigenvectors of $H$, which are functions of the entries of $H$. An argument that conditions on an eigenvector and treats the entries of $H$ as independent would not be valid.
\end{remark}

\section{A deterministic nonlattice estimate}\label{s:llt-nonlattice}

In \zcref{s:llt-nonlattice}, $U$ denotes a deterministic $N \times 2k$ matrix with $U^T U = \Id_{2k}$. We use the notation of \zcref{s:llt-moments} for such general $U$, so that $r_b$ denotes the $b$-th row of $N^{1/2} U$, and \eqref{e:llt-rows} holds. For $\xi \in \R^{2k}$, we define
\begin{equation}\label{e:llt-dfull}
\mathcal D_U(\xi) = \frac{1}{N^2} \sum_{a, b = 1}^N \bigl[ 1 - \cos\bigl( r_a^T \Gamma(\xi) r_b \bigr) \bigr].
\end{equation}
For $U = U_{\mathbf i}$, the identity \eqref{e:llt-phase} shows that $\mathcal D_U(\xi)$ is the average of $1 - \cos(\xi \cdot D^{(\mathbf i)}_{ab})$ over all $(a, b) \in [N]^2$. It is small exactly when most of the phases $\xi \cdot D^{(\mathbf i)}_{ab}$ are close to $2 \pi \Z$. We also define the exponents
\begin{equation}\label{e:llt-exponents}
\mathfrak p_k = 4k + 4, \qquad \mathfrak a_k = 100 (k + 1), \qquad \mathfrak q_k = 2 \mathfrak a_k + 2k + 10,
\end{equation}
and we note that $\mathfrak a_k > 4 \mathfrak p_k$.

\begin{lemma}\label{l:nonlattice}
There exists $\Omega_0(k) \ge 3$ such that the following holds. Let $K \ge 1$ and $\Omega \ge \max\{\Omega_0(k), K^2\}$. Suppose that $\max_{b} |r_b| \le K$ and that every column $u$ of $U$ satisfies
\begin{equation}\label{e:llt-nonlattice-hyp}
\inf_{v \in \mathcal V_{\lfloor \Omega^{\mathfrak p_k} \rfloor}} \|N^{1/2} u - v\|_{2, N} > \Omega^{-\mathfrak a_k}.
\end{equation}
Then $\mathcal D_U(\xi) \ge \Omega^{-\mathfrak q_k}$ for all $\xi \in \R^{2k}$ such that $\Omega^{-1} \le |\xi| \le \Omega K^{-2}$.
\end{lemma}

\begin{proof}
We argue by contradiction. Suppose that there exists $\xi$ with $\Omega^{-1} \le |\xi| \le \Omega K^{-2}$ and $\mathcal D_U(\xi) < \Omega^{-\mathfrak q_k}$, and abbreviate $\mathcal D = \mathcal D_U(\xi)$. For $a, b \in [N]$, let
\begin{equation}
\Theta_{ab} = \dist\bigl( r_a^T \Gamma(\xi) r_b, 2 \pi \Z \bigr) \in [0, \pi].
\end{equation}
For real $t'$ with $\dist(t', 2\pi\Z) = \Theta$, we have
\begin{equation}
1 - \cos t' = 2 \sin^2(\Theta/2) \ge \frac{2 \Theta^2}{\pi^2},
\end{equation}
where we used $\sin y' \ge 2y'/\pi$ for $y' \in [0, \pi/2]$. Summing over $a$ and $b$, we obtain
\begin{equation}\label{e:llt-thetasum}
\frac{1}{N^2} \sum_{a, b = 1}^N \Theta_{ab}^2 \le \frac{\pi^2}{2} \, \mathcal D.
\end{equation}

We first discard the rows with large errors. For $a \in [N]$, set
\begin{equation}
\bar \Theta_a = \frac{1}{N} \sum_{b = 1}^N \Theta_{ab}^2, \qquad \mathcal O = \bigl\{ a \in [N] : \bar \Theta_a \le 2 \pi^2 K^2 \mathcal D \bigr\}.
\end{equation}
When $\mathcal D > 0$, Markov's inequality and \eqref{e:llt-thetasum} give
\begin{equation}
|[N] \setminus \mathcal O| \le \frac{N}{4K^2},
\end{equation}
and when $\mathcal D = 0$, we have $\mathcal O = [N]$. Using \eqref{e:llt-rows} and $|r_a| \le K$, we find, in the sense of quadratic forms,
\begin{equation}\label{e:llt-retained}
\frac{1}{N} \sum_{a \in \mathcal O} r_a r_a^T = \Id_{2k} - \frac{1}{N} \sum_{a \notin \mathcal O} r_a r_a^T \ge \Bigl( 1 - \frac{K^2 \, |[N] \setminus \mathcal O|}{N} \Bigr) \Id_{2k} \ge \frac{3}{4} \Id_{2k}.
\end{equation}

Next, we select $2k$ rows that form a well-conditioned matrix. For a set $\mathcal O_0 \subset \mathcal O$ with $2k$ elements, let $Q(\mathcal O_0)$ denote the $2k \times 2k$ matrix with rows $r_a^T$, $a \in \mathcal O_0$, in increasing order of $a$. The Cauchy--Binet formula, applied to the matrix with rows $r_a^T$, $a \in \mathcal O$, gives
\begin{equation}
\det\Bigl( \sum_{a \in \mathcal O} r_a r_a^T \Bigr) = \sum_{\mathcal O_0 \subset \mathcal O, \, |\mathcal O_0| = 2k} \det\bigl( Q(\mathcal O_0) \bigr)^2.
\end{equation}
By \eqref{e:llt-retained}, the left side is at least $(3N/4)^{2k}$; in particular, $|\mathcal O| \ge 2k$. The sum has at most $\binom{N}{2k} \le N^{2k}/(2k)!$ terms, so there exists $\mathcal O_0$ such that $Q = Q(\mathcal O_0)$ satisfies
\begin{equation}
|\det Q| \ge (3/4)^k ((2k)!)^{1/2}.
\end{equation}

We now bound $\|Q^{-1}\|$. The rows of $Q$ have norm at most $K$, so $\|Q\| \le (2k)^{1/2} K$. The determinant is the product of the $2k$ singular values of $Q$, so the smallest singular value of $Q$ is at least $|\det Q| \, \|Q\|^{1 - 2k}$. Therefore
\begin{equation}\label{e:llt-qinverse}
\|Q^{-1}\| \le \frac{\|Q\|^{2k - 1}}{|\det Q|} \le C_k K^{2k - 1}.
\end{equation}

Next, we round the phases against the rows of $Q$. For $a \in \mathcal O_0$ and $b \in [N]$, choose $\mathbf n_b(a) \in \Z$ such that
\begin{equation}
|r_a^T \Gamma(\xi) r_b - 2\pi \mathbf n_b(a)| = \Theta_{ab}.
\end{equation}
We let $\mathbf n_b \in \Z^{2k}$ denote the vector with coordinates $\mathbf n_b(a)$, $a \in \mathcal O_0$, in increasing order of $a$. The coordinates of $Q \Gamma(\xi) r_b$ are the phases $r_a^T \Gamma(\xi) r_b$, $a \in \mathcal O_0$. Since $\mathcal O_0 \subset \mathcal O$, we find
\begin{equation}\label{e:llt-rounding}
\frac{1}{N} \sum_{b = 1}^N \bigl| Q \Gamma(\xi) r_b - 2\pi \mathbf n_b \bigr|^2 = \sum_{a \in \mathcal O_0} \bar \Theta_a \le 4 k \pi^2 K^2 \mathcal D.
\end{equation}
Further, the bound $|\xi| \le \Omega K^{-2}$ gives
\begin{equation}
|r_a^T \Gamma(\xi) r_b| \le \|\Gamma(\xi)\| K^2 \le |\xi| K^2 \le \Omega, \qquad \text{so} \qquad |\mathbf n_b(a)| \le \frac{\Omega}{2\pi} + \frac{1}{2} \le \Omega.
\end{equation}
Hence, as $b$ ranges over $[N]$, the vector $\mathbf n_b$ takes at most $(2 \Omega + 1)^{2k} \le (3 \Omega)^{2k}$ values.

We now reconstruct one block of the rows $r_b$ from the integer vectors $\mathbf n_b$. Choose $j \in [k]$ such that $|\xi_j| = \max_{j'} |\xi_{j'}|$, so that
\begin{equation}
|\xi_j| \ge k^{-1/2} |\xi| \ge k^{-1/2} \Omega^{-1}.
\end{equation}
Since $\Gamma(\xi)$ is block diagonal, the $j$-th block of $\Gamma(\xi) r_b$ is $\Gamma(\xi_j) r_{b, j}$. For $b \in [N]$, define
\begin{equation}
\hat r_b = \Gamma(\xi_j)^{-1} \bigl( Q^{-1} \, 2 \pi \mathbf n_b \bigr)_j \in \R^2.
\end{equation}
Then
\begin{equation}
r_{b, j} - \hat r_b = \Gamma(\xi_j)^{-1} \Bigl( Q^{-1} \bigl( Q \Gamma(\xi) r_b - 2\pi \mathbf n_b \bigr) \Bigr)_j.
\end{equation}
Using $\|\Gamma(\xi_j)^{-1}\| = |\xi_j|^{-1}$, \eqref{e:llt-qinverse}, and \eqref{e:llt-rounding}, we obtain
\begin{equation}\label{e:llt-reconstruction}
\begin{split}
\Bigl( \frac{1}{N} \sum_{b = 1}^N |r_{b, j} - \hat r_b|^2 \Bigr)^{1/2} &\le \frac{\|Q^{-1}\|}{|\xi_j|} \bigl( 4 k \pi^2 K^2 \mathcal D \bigr)^{1/2} \le C_k \Omega K^{2k} \mathcal D^{1/2} \\
&\le C_k \Omega^{k + 1 - \mathfrak q_k/2} = C_k \Omega^{-\mathfrak a_k - 4}.
\end{split}
\end{equation}
In the third inequality, we used $K^2 \le \Omega$ and $\mathcal D < \Omega^{-\mathfrak q_k}$, and the last equality follows from the definition of $\mathfrak q_k$ in \eqref{e:llt-exponents}.

It remains to derive the contradiction. Let $u$ be the $(2j - 1)$-th column of $U$, so that $N^{1/2} u(b)$ is the first coordinate of $r_{b, j}$. Let $v \in \R^N$ be the vector whose $b$-th coordinate is the first coordinate of $\hat r_b$. The vector $\hat r_b$ depends on $b$ only through $\mathbf n_b$, so $v$ has at most $(3 \Omega)^{2k}$ distinct coordinates. For $\Omega \ge 3$, we have $(3\Omega)^{2k} \le \lfloor \Omega^{\mathfrak p_k} \rfloor$, and hence $v \in \mathcal V_{\lfloor \Omega^{\mathfrak p_k} \rfloor}$. By \eqref{e:llt-reconstruction}, we have
\begin{equation}
\|N^{1/2} u - v\|_{2, N} \le C_k \Omega^{-\mathfrak a_k - 4} \le \Omega^{-\mathfrak a_k},
\end{equation}
where the second inequality holds when $\Omega^4 \ge C_k$. This contradicts \eqref{e:llt-nonlattice-hyp}, and the lemma follows with $\Omega_0(k) = \max\{3, C_k^{1/4}\}$, where $C_k$ is the constant in the last line of \eqref{e:llt-reconstruction}.
\end{proof}

\begin{remark}\label{r:offdiagonal}
The resampling selects only pairs $a < b$, so the characteristic function $\Phi_H$ involves the phases $r_a^T \Gamma(\xi) r_b$ only for $a < b$. We therefore need the following version of \zcref{l:nonlattice} without diagonal terms.
\end{remark}

For $\xi \in \R^{2k}$, we define
\begin{equation}\label{e:llt-doff}
\mathcal D^{\mathrm{off}}_U(\xi) = \binom{N}{2}^{-1} \sum_{a < b} \bigl[ 1 - \cos\bigl( r_a^T \Gamma(\xi) r_b \bigr) \bigr].
\end{equation}

\begin{corollary}\label{c:offdiagonal}
Let $K$, $\Omega$, and $U$ satisfy the hypotheses of \zcref{l:nonlattice}, and suppose in addition that $\Omega^{\mathfrak q_k} \le N/4$. Then $\mathcal D^{\mathrm{off}}_U(\xi) \ge \Omega^{-\mathfrak q_k}/2$ for all $\xi \in \R^{2k}$ such that $\Omega^{-1} \le |\xi| \le \Omega K^{-2}$.
\end{corollary}

\begin{proof}
The summand in \eqref{e:llt-dfull} is symmetric in $(a, b)$ and takes values in $[0, 2]$, so
\begin{equation}
\mathcal D_U(\xi) = \Bigl( 1 - \frac{1}{N} \Bigr) \mathcal D^{\mathrm{off}}_U(\xi) + \frac{1}{N^2} \sum_{a = 1}^N \bigl[ 1 - \cos\bigl( r_a^T \Gamma(\xi) r_a \bigr) \bigr] \le \mathcal D^{\mathrm{off}}_U(\xi) + \frac{2}{N}.
\end{equation}
For $\Omega^{-1} \le |\xi| \le \Omega K^{-2}$, \zcref{l:nonlattice} and the condition $\Omega^{\mathfrak q_k} \le N/4$ therefore give $\mathcal D^{\mathrm{off}}_U(\xi) \ge \Omega^{-\mathfrak q_k} - 2N^{-1} \ge \Omega^{-\mathfrak q_k}/2$.
\end{proof}

\section{The characteristic function of one increment}\label{s:llt-charfunction}

We now convert \zcref{l:nonlattice} into a bound on $|\Phi_H|$. Let $Y'$ be a copy of $Y$ independent of $Y$. Since $\E (Y - Y')^2 = 2$, we have $\Prob(Y \neq Y') > 0$, and we may choose constants $0 < c_- < c_+$, depending only on the law of $X$, such that
\begin{equation}\label{e:llt-py}
p_Y = \Prob\bigl( c_- \le |Y - Y'| \le c_+ \bigr) > 0.
\end{equation}

\begin{lemma}\label{l:charfunction}
Let $K \ge 1$ and $\Omega \ge \max\{\Omega_0(k), K^2\}$ with $\Omega^{\mathfrak q_k} \le N/4$. Let $\mathbf i$ be a $k$-tuple, and consider a realization of $H$ for which $U = U_{\mathbf i}$ satisfies the hypotheses of \zcref{l:nonlattice}. Then
\begin{equation}\label{e:llt-charbound}
1 - |\Phi_H(\xi)|^2 \ge \frac{p_Y}{2} \, \Omega^{-\mathfrak q_k} \qquad \text{for all } \xi \in \R^{2k} \text{ such that } \frac{1}{c_- \Omega} \le |\xi| \le \frac{\Omega}{c_+ K^2}.
\end{equation}
\end{lemma}

\begin{proof}
Conditioning on $(a, b)$ in \eqref{e:llt-charfunction} and using the independence of $Y$, we find
\begin{equation}
\Phi_H(\xi) = \binom{N}{2}^{-1} \sum_{a < b} e^{- \iu X_{ab} \, \xi \cdot D^{(\mathbf i)}_{ab}} \, \Phi_Y\bigl( \xi \cdot D^{(\mathbf i)}_{ab} \bigr).
\end{equation}
We symmetrize with the Cauchy--Schwarz inequality, which removes the phases $e^{-\iu X_{ab} \xi \cdot D^{(\mathbf i)}_{ab}}$. Using
\begin{equation}
|\Phi_Y(t')|^2 = \E e^{\iu t' (Y - Y')} = \E \cos\bigl( t' (Y - Y') \bigr), \qquad t' \in \R,
\end{equation}
we obtain
\begin{equation}\label{e:llt-symmetrization}
|\Phi_H(\xi)|^2 \le \binom{N}{2}^{-1} \sum_{a < b} \bigl| \Phi_Y\bigl( \xi \cdot D^{(\mathbf i)}_{ab} \bigr) \bigr|^2 = \E\Bigl[ \binom{N}{2}^{-1} \sum_{a < b} \cos\bigl( (Y - Y') \, \xi \cdot D^{(\mathbf i)}_{ab} \bigr) \Bigr].
\end{equation}
By \eqref{e:llt-phase} and the linearity of $\Gamma$, we have
\begin{equation}
(Y - Y') \, \xi \cdot D^{(\mathbf i)}_{ab} = r_a^T \Gamma\bigl( (Y - Y') \xi \bigr) r_b.
\end{equation}
Hence \eqref{e:llt-symmetrization} and \eqref{e:llt-doff} give
\begin{equation}
1 - |\Phi_H(\xi)|^2 \ge \E\bigl[ \mathcal D^{\mathrm{off}}_U\bigl( (Y - Y') \xi \bigr) \bigr] \ge \E\bigl[ \mathcal D^{\mathrm{off}}_U\bigl( (Y - Y') \xi \bigr) \1\{ c_- \le |Y - Y'| \le c_+ \} \bigr],
\end{equation}
where the second inequality holds because $\mathcal D^{\mathrm{off}}_U \ge 0$. For $\xi$ as in \eqref{e:llt-charbound} and every realization with $c_- \le |Y - Y'| \le c_+$, we have
\begin{equation}
\Omega^{-1} \le c_- |\xi| \le |(Y - Y') \xi| \le c_+ |\xi| \le \Omega K^{-2}.
\end{equation}
Therefore \zcref{c:offdiagonal} gives
\begin{equation}
\mathcal D^{\mathrm{off}}_U((Y - Y') \xi) \ge \Omega^{-\mathfrak q_k}/2
\end{equation}
on this event. Taking expectations and using \eqref{e:llt-py} completes the proof.
\end{proof}

\section{A local limit theorem for sums of increments}\label{s:llt-sums}

We now fix the parameters. Recall that $\tau = N^{1/100}$, and set
\begin{equation}\label{e:llt-parameters}
\eps_k = \frac{1}{4000 \, \mathfrak q_k}, \qquad \Omega = \tau^{1/(4 \mathfrak q_k)} = N^{10 \eps_k}, \qquad K = (2k)^{1/2} N^{\eps_k}.
\end{equation}
Let $C_{\mathrm{mom}} \ge 1$ denote the constant $C$ of \zcref{l:moments} for $\eps = \eps_k$, and set
\begin{equation}\label{e:llt-varrho}
\varrho_N = (12 C_{\mathrm{mom}})^{-1} N^{-9 \eps_k}.
\end{equation}
In the proof of \zcref{l:llt}, $\varrho_N$ will be the radius of the ball of frequencies on which a second-order Taylor expansion of $\Phi_H$ is effective. The exponent of $\Omega$ is chosen so that $\Omega^{-\mathfrak q_k} = \tau^{-1/4}$, which makes $m \Omega^{-\mathfrak q_k}$ a positive power of $\tau$. Since $\Omega$, $K^2$, and $\varrho_N^{-1}$ are constant multiples of $N^{10 \eps_k}$, $N^{2 \eps_k}$, and $N^{9 \eps_k}$, respectively, there exists $N_0$ such that for $N \ge N_0$,
\begin{equation}\label{e:llt-constraints}
\Omega \ge \max\{\Omega_0(k), K^2\}, \qquad \Omega^{\mathfrak q_k} \le \frac{N}{4}, \qquad c_+ K^2 \le \Omega^{1/2}, \qquad \frac{1}{c_- \Omega} \le \varrho_N.
\end{equation}
The last condition dictates the choice of $\eps_k$. Since $\Omega = N^{1/(400 \mathfrak q_k)}$ is determined by $\tau$, this condition can hold for large $N$ only if $9 \eps_k \le 1/(400 \mathfrak q_k)$, and our choice gives $9 \eps_k < 10 \eps_k = 1/(400 \mathfrak q_k)$. Further, we have $10 \eps_k \mathfrak p_k < 1$ and $10 \eps_k (\mathfrak a_k + 1) < 1/2$, so
\begin{equation}\label{e:llt-growth}
\Omega^{\mathfrak p_k} = o(N), \qquad \Omega^{\mathfrak a_k + 1} = o(N^{1/2}).
\end{equation}

\begin{definition}\label{d:llt-events}
We let $\mathcal A_{N, k}$ denote the event that $\mathcal A^{\mathrm{reg}}_N(\eps_k)$ holds and that every unit eigenvector $w$ of $H$ satisfies
\begin{equation}
\inf_{v \in \mathcal V_{\lfloor \Omega^{\mathfrak p_k} \rfloor}} \|N^{1/2} w - v\|_{2, N} > \Omega^{-\mathfrak a_k}.
\end{equation}
\end{definition}

The event $\mathcal A_{N, k}$ does not refer to any tuple $\mathbf i$. This is what makes the estimates below uniform over tuples, including tuples selected according to properties of $H$ such as small gaps.

\begin{lemma}\label{l:llt-events}
The event $\mathcal A_{N, k}$ holds with overwhelming probability. Moreover, for $N \ge N_0$, on $\mathcal A_{N, k}$ and for every $k$-tuple $\mathbf i$, we have
\begin{equation}\label{e:llt-intermediate}
1 - |\Phi_H(\xi)|^2 \ge \frac{p_Y}{2} \, \tau^{-1/4} \qquad \text{for all } \xi \in \R^{2k} \text{ such that } \varrho_N \le |\xi| \le \Omega^{1/2}.
\end{equation}
\end{lemma}

\begin{proof}
Recall that $\|H\| \le 3$ and that every unit eigenvector $w$ of $H$ satisfies $N^{1/2} \|w\|_\infty \le N^{\eps_k} \le K$ on $\mathcal A^{\mathrm{reg}}_N(\eps_k)$. Hence the complement of $\mathcal A_{N, k}$ is a subset of the union of the complement of $\mathcal A^{\mathrm{reg}}_N(\eps_k)$ and the event of \zcref{l:fewvalues} with $\mathfrak p = \mathfrak p_k$, $\mathfrak a = \mathfrak a_k$, and $\Omega$ and $K$ as in \eqref{e:llt-parameters}. The hypotheses of \zcref{l:fewvalues} hold by \eqref{e:llt-growth}, and $K \le \Omega$ for large $N$. \zcref{l:llt-regular} and \zcref{l:fewvalues} therefore show that $\mathcal A_{N, k}$ holds with overwhelming probability.

Now let $N \ge N_0$, fix a realization of $H$ in $\mathcal A_{N, k}$, and let $\mathbf i$ be a $k$-tuple. The rows of $N^{1/2} U_{\mathbf i}$ satisfy $|r_b| \le K$ by \eqref{e:llt-rowbound}. The columns of $U_{\mathbf i}$ are unit eigenvectors of $H$, so the definition of $\mathcal A_{N, k}$ gives \eqref{e:llt-nonlattice-hyp}. Together with the first two conditions in \eqref{e:llt-constraints}, this verifies the hypotheses of \zcref{l:charfunction}. The last two conditions in \eqref{e:llt-constraints} show that every $\xi$ with $\varrho_N \le |\xi| \le \Omega^{1/2}$ satisfies the condition in \eqref{e:llt-charbound}. Since $\Omega^{-\mathfrak q_k} = \tau^{-1/4}$, the bound \eqref{e:llt-charbound} gives \eqref{e:llt-intermediate}.
\end{proof}

For a positive definite $2k \times 2k$ matrix $\Sigma$, let $\mathfrak g_\Sigma$ denote the density of the centered Gaussian law on $\R^{2k}$ with covariance $\Sigma$,
\begin{equation}
\mathfrak g_\Sigma(y) = (2\pi)^{-k} (\det \Sigma)^{-1/2} \exp\Bigl( - \frac{1}{2} y^T \Sigma^{-1} y \Bigr), \qquad y \in \R^{2k}.
\end{equation}
This extends the notation \eqref{e:prelim-gaussian-density} on $\R^{2k}$, so that $\mathfrak g_v = \mathfrak g_{v \Id_{2k}}$ for $v > 0$. In particular, $\mathfrak g_{4n \Id_{2k}}(y) = (8 \pi n)^{-k} e^{-|y|^2/(8n)}$. We now state the local limit theorem. Its proof is the classical Fourier-analytic argument for local limit theorems (see \cite{bhattacharya2010normal}), made uniform in $H$, in the tuple $\mathbf i$, and in the number of summands. The input specific to our setting is the bound \eqref{e:llt-intermediate}.

\begin{lemma}\label{l:llt}
Let $\Psi \subset C_c^\infty(\R^{2k})$ be a family of functions such that there exists $R_\Psi > 0$ with $\supp \psi \subset \{y \in \R^{2k} : |y| \le R_\Psi\}$ for all $\psi \in \Psi$, and such that each partial derivative of each order is bounded uniformly over $\psi \in \Psi$. Then on $\mathcal A_{N, k}$, for every $k$-tuple $\mathbf i$, every integer $n$ with $\tau/10 \le n \le \tau/3$, every $x \in \R^{2k}$, and every $\psi \in \Psi$,
\begin{equation}\label{e:llt-main}
\E\bigl[ \psi\bigl( S^{(n)} + x \bigr) \bigm| H \bigr] = \mathfrak g_{4 n \Id_{2k}}(x) \int_{\R^{2k}} \psi(y) \dd y + o(\tau^{-k}),
\end{equation}
where the error term is bounded in absolute value by a deterministic quantity that is $o(\tau^{-k})$ and depends on $\Psi$, but not on $\mathbf i$, $n$, $x$, $\psi$, or the realization of $H$ in $\mathcal A_{N, k}$. Further, for every bounded Borel set $B \subset \R^{2k}$, there exists $C_B > 0$ such that on $\mathcal A_{N, k}$, for every $k$-tuple $\mathbf i$ and every integer $n$ with $\tau/10 \le n \le \tau/3$,
\begin{equation}\label{e:llt-smallball}
\sup_{x \in \R^{2k}} \Prob\bigl( S^{(n)} + x \in B \bigm| H \bigr) \le C_B \tau^{-k}.
\end{equation}
\end{lemma}

\begin{proof}
In this proof, constants may depend on $\Psi$ in addition to $k$ and the laws of $X$ and $Z$. We first record a trivial bound that holds for all $N$. By the hypothesis on the partial derivatives of order zero, the functions in $\Psi$ are bounded uniformly. They are also supported in the ball of radius $R_\Psi$ centered at the origin, and therefore
\begin{equation}\label{e:llt-psibound}
\sup_{\psi \in \Psi} \|\psi\|_\infty < \infty, \qquad \sup_{\psi \in \Psi} \int_{\R^{2k}} |\psi(y)| \dd y \le (2 R_\Psi)^{2k} \sup_{\psi \in \Psi} \|\psi\|_\infty < \infty.
\end{equation}
Every integer $n$ with $\tau/10 \le n \le \tau/3$ is positive, so $\mathfrak g_{4n \Id_{2k}}(x) \le (8 \pi n)^{-k} \le (8 \pi)^{-k}$ for all $x \in \R^{2k}$. Hence, for every realization of $H$ and all $\mathbf i$, $n$, $x$, and $\psi$ as in the statement, the error term in \eqref{e:llt-main} is bounded in absolute value by $\sup_{\psi \in \Psi} \|\psi\|_\infty + (8 \pi)^{-k} \sup_{\psi \in \Psi} \int |\psi|$, which is finite by \eqref{e:llt-psibound}. We take this number as the deterministic quantity in the statement when $N < N_0$, $\tau < 20$, or $C_{\mathrm{mom}} N^{3 \eps_k - 1/2} > 1$. Each of these conditions holds only for finitely many $N$, and the deterministic quantity only needs to be $o(\tau^{-k})$ as $N \to \infty$. We may therefore assume from now on that $N \ge N_0$, that $\tau \ge 20$, and that $C_{\mathrm{mom}} N^{3 \eps_k - 1/2} \le 1$. Fix a realization of $H$ in $\mathcal A_{N, k}$, a $k$-tuple $\mathbf i$, an integer $n$ with $\tau/10 \le n \le \tau/3$, a vector $x \in \R^{2k}$, and $\psi \in \Psi$. Then $n \ge \tau/10 \ge 2$.

We begin with bounds on the Fourier transform
\begin{equation}
\hat \psi(\xi) = \int_{\R^{2k}} e^{-\iu \xi \cdot y} \psi(y) \dd y, \qquad \xi \in \R^{2k}.
\end{equation}
Set
\begin{equation}
\mathfrak s_k = 4 k \mathfrak q_k + k + 1.
\end{equation}
Integrating by parts $2 \mathfrak s_k$ times, differentiating under the integral, and using that the functions in $\Psi$ are supported in a common ball and have uniformly bounded derivatives, we find
\begin{equation}\label{e:llt-psihat}
|\hat \psi(\xi)| \le \frac{C}{1 + |\xi|^{2 \mathfrak s_k}}, \qquad |\hat \psi(\xi) - \hat \psi(0)| \le C |\xi|, \qquad \xi \in \R^{2k}.
\end{equation}
Since $2 \mathfrak s_k > 2k$, the first bound implies
\begin{equation}\label{e:llt-psihat-l1}
\int_{\R^{2k}} |\hat \psi(\xi)| \dd \xi \le C.
\end{equation}

Next, we write both sides of \eqref{e:llt-main} as Fourier integrals. Since $\hat \psi$ is integrable, the inversion formula
\begin{equation}
\psi(y) = (2\pi)^{-2k} \int_{\R^{2k}} e^{\iu \xi \cdot y} \hat \psi(\xi) \dd \xi
\end{equation}
holds for all $y$. Inserting it into the conditional expectation, and using Fubini's theorem and \eqref{e:llt-charsum}, we obtain
\begin{equation}
\E\bigl[ \psi\bigl( S^{(n)} + x \bigr) \bigm| H \bigr] = (2\pi)^{-2k} \int_{\R^{2k}} e^{\iu \xi \cdot x} \hat \psi(\xi) \Phi_H(\xi)^n \dd \xi.
\end{equation}
Further, we have
\begin{equation}
\hat \psi(0) = \int \psi, \qquad \int_{\R^{2k}} e^{\iu \xi \cdot x} e^{-2n|\xi|^2} \dd \xi = (2\pi)^{2k} \mathfrak g_{4n \Id_{2k}}(x).
\end{equation}
Subtracting, we find
\begin{equation}\label{e:llt-fourierdiff}
\Bigl| \E\bigl[ \psi\bigl( S^{(n)} + x \bigr) \bigm| H \bigr] - \mathfrak g_{4n \Id_{2k}}(x) \int \psi \Bigr| \le (2\pi)^{-2k} \int_{\R^{2k}} \bigl| \hat \psi(\xi) \Phi_H(\xi)^n - \hat \psi(0) e^{-2n|\xi|^2} \bigr| \dd \xi.
\end{equation}
The right side of \eqref{e:llt-fourierdiff} does not involve $x$, which gives the uniformity in $x$.

We split the integral in \eqref{e:llt-fourierdiff} into three ranges of frequencies. Since $n \ge \tau/10$, the right side of \eqref{e:llt-fourierdiff} is bounded by $C \tau^{-k} (\mathcal I_1 + \mathcal I_2 + \mathcal I_3 + \mathcal I_4)$, where
\begin{equation}\label{e:llt-fourparts}
\begin{aligned}
\mathcal I_1 &= n^k \int_{|\xi| \le \varrho_N} \bigl| \hat \psi(\xi) \Phi_H(\xi)^n - \hat \psi(0) e^{-2n|\xi|^2} \bigr| \dd \xi, &
\mathcal I_2 &= n^k \int_{\varrho_N < |\xi| \le \Omega^{1/2}} |\hat \psi(\xi)| \, |\Phi_H(\xi)|^n \dd \xi, \\
\mathcal I_3 &= n^k \int_{|\xi| > \Omega^{1/2}} |\hat \psi(\xi)| \dd \xi, &
\mathcal I_4 &= n^k |\hat \psi(0)| \int_{|\xi| > \varrho_N} e^{-2n|\xi|^2} \dd \xi,
\end{aligned}
\end{equation}
and where we used $|\Phi_H| \le 1$ to define $\mathcal I_3$. All constants above depend on $\psi$ only through $R_\Psi$ and the uniform bounds on finitely many derivatives. It therefore suffices to show that $\mathcal I_1 + \mathcal I_2 + \mathcal I_3 + \mathcal I_4$ is bounded by a deterministic quantity that tends to zero.

We first treat small frequencies. Let
\begin{equation}
\Phi^\circ_H(\xi) = e^{-\iu \xi \cdot \bar J} \Phi_H(\xi) = \E\bigl[ e^{\iu \xi \cdot (J - \bar J)} \bigm| H \bigr], \qquad \xi \in \R^{2k}.
\end{equation}
By \zcref{l:moments} with $\eps = \eps_k$ and our assumption $C_{\mathrm{mom}} N^{3\eps_k - 1/2} \le 1$, we have
\begin{equation}
3 \Id_{2k} \le \Sigma_H \le 5 \Id_{2k}
\end{equation}
and
\begin{equation}
\E\bigl[ |J - \bar J|^3 \bigm| H \bigr] \le 4 \Bigl( \E\bigl[ |J|^3 \bigm| H \bigr] + |\bar J|^3 \Bigr) \le 8 \E\bigl[ |J|^3 \bigm| H \bigr] \le 8 C_{\mathrm{mom}} N^{9 \eps_k}.
\end{equation}
We apply the inequality $|e^{\iu t'} - 1 - \iu t' + t'^2/2| \le |t'|^3/6$, valid for real $t'$, with $t' = \xi \cdot (J - \bar J)$, and obtain
\begin{equation}\label{e:llt-taylor}
\Bigl| \Phi^\circ_H(\xi) - 1 + \frac{1}{2} \xi^T \Sigma_H \xi \Bigr| \le \frac{4}{3} C_{\mathrm{mom}} N^{9 \eps_k} |\xi|^3, \qquad \xi \in \R^{2k}.
\end{equation}
For $|\xi| \le \varrho_N$, the definition \eqref{e:llt-varrho} gives
\begin{equation}
\frac{3}{2} |\xi|^2 \le \frac{1}{2} \xi^T \Sigma_H \xi \le \frac{5}{2} |\xi|^2 \le 1, \qquad \frac{4}{3} C_{\mathrm{mom}} N^{9 \eps_k} |\xi|^3 \le \frac{1}{9} |\xi|^2.
\end{equation}
Hence \eqref{e:llt-taylor} implies
\begin{equation}\label{e:llt-smallmodulus}
|\Phi_H(\xi)| = |\Phi^\circ_H(\xi)| \le 1 - \frac{3}{2} |\xi|^2 + \frac{1}{9} |\xi|^2 \le e^{-|\xi|^2}, \qquad |\xi| \le \varrho_N.
\end{equation}

We now change variables $\xi = n^{-1/2} \xi'$ in $\mathcal I_1$, which gives
\begin{equation}
\mathcal I_1 = \int_{|\xi'| \le \varrho_N n^{1/2}} \bigl| \hat \psi(n^{-1/2} \xi') \Phi_H(n^{-1/2} \xi')^n - \hat \psi(0) e^{-2|\xi'|^2} \bigr| \dd \xi'.
\end{equation}
By \eqref{e:llt-psihat} and \eqref{e:llt-smallmodulus}, the integrand is bounded by
\begin{equation}\label{e:llt-integrand}
C n^{-1/2} |\xi'| e^{-|\xi'|^2} + C \bigl| \Phi_H(n^{-1/2} \xi')^n - e^{-2|\xi'|^2} \bigr|.
\end{equation}
We have $\Phi_H(\xi)^n = e^{\iu n \xi \cdot \bar J} \Phi^\circ_H(\xi)^n$, and therefore
\begin{equation}\label{e:llt-threeterms}
\begin{split}
\bigl| \Phi_H(n^{-1/2} \xi')^n - e^{-2|\xi'|^2} \bigr| \le {}& \bigl| e^{\iu n^{1/2} \xi' \cdot \bar J} - 1 \bigr| e^{-|\xi'|^2} + \bigl| \Phi^\circ_H(n^{-1/2} \xi')^n - e^{-\xi'^T \Sigma_H \xi'/2} \bigr| \\
&+ \bigl| e^{-\xi'^T \Sigma_H \xi'/2} - e^{-2|\xi'|^2} \bigr|.
\end{split}
\end{equation}
We bound the three terms on the right side in turn. By \zcref{l:moments}, the first term satisfies
\begin{equation}
\bigl| e^{\iu n^{1/2} \xi' \cdot \bar J} - 1 \bigr| e^{-|\xi'|^2} \le n^{1/2} |\xi'| |\bar J| e^{-|\xi'|^2} \le C \tau^{1/2} N^{-1/2} |\xi'| e^{-|\xi'|^2}.
\end{equation}
The two exponents in the third term are at least $3|\xi'|^2/2$, so the mean value theorem and \zcref{l:moments} give
\begin{equation}
\bigl| e^{-\xi'^T \Sigma_H \xi'/2} - e^{-2|\xi'|^2} \bigr| \le \frac{1}{2} \|\Sigma_H - 4 \Id_{2k}\| \, |\xi'|^2 e^{-3|\xi'|^2/2} \le C N^{3 \eps_k - 1/2} |\xi'|^2 e^{-3|\xi'|^2/2}.
\end{equation}

To bound the second term in \eqref{e:llt-threeterms}, we set
\begin{equation*}
z' = \Phi^\circ_H(n^{-1/2} \xi'), \qquad z'' = e^{-\xi'^T \Sigma_H \xi'/(2n)}.
\end{equation*}
The bound \eqref{e:llt-smallmodulus} and $\Sigma_H \ge 3 \Id_{2k}$ give
\begin{equation}
\max\{|z'|, |z''|\} \le e^{-|\xi'|^2/n}.
\end{equation}
Using \eqref{e:llt-taylor} and $|e^{-t'} - 1 + t'| \le t'^2/2$ for $t' \ge 0$, we find
\begin{equation}
|z' - z''| \le \frac{1}{2} \Bigl( \frac{5 |\xi'|^2}{2n} \Bigr)^2 + \frac{4}{3} C_{\mathrm{mom}} N^{9 \eps_k} \frac{|\xi'|^3}{n^{3/2}} \le \frac{4 |\xi'|^4}{n^2} + \frac{2 C_{\mathrm{mom}} N^{9 \eps_k} |\xi'|^3}{n^{3/2}}.
\end{equation}
We now use the elementary inequality
\begin{equation}
|z'^n - z''^n| \le n |z' - z''| \max\{|z'|, |z''|\}^{n - 1} \le n |z' - z''| e^{-|\xi'|^2 (n - 1)/n} \le n |z' - z''| e^{-|\xi'|^2/2},
\end{equation}
where we used $n \ge 2$ in the last step, and we obtain
\begin{equation}
\bigl| \Phi^\circ_H(n^{-1/2} \xi')^n - e^{-\xi'^T \Sigma_H \xi'/2} \bigr| \le \Bigl( \frac{4 |\xi'|^4}{n} + \frac{2 C_{\mathrm{mom}} N^{9 \eps_k} |\xi'|^3}{n^{1/2}} \Bigr) e^{-|\xi'|^2/2}.
\end{equation}

We now collect these bounds. Using $\tau/10 \le n \le \tau/3$, $\tau = N^{1/100}$, and $\tau^{1/2} N^{-1/2} + N^{3 \eps_k - 1/2} \le 2 \tau^{-1/2}$, we find that \eqref{e:llt-integrand} is bounded by
\begin{equation}
C N^{9 \eps_k} \tau^{-1/2} (1 + |\xi'|)^4 e^{-|\xi'|^2/2} = C N^{9 \eps_k - 1/200} (1 + |\xi'|)^4 e^{-|\xi'|^2/2}.
\end{equation}
Integrating over $\xi' \in \R^{2k}$, we conclude that
\begin{equation}
\mathcal I_1 \le C N^{9 \eps_k - 1/200},
\end{equation}
which tends to zero by \eqref{e:llt-parameters}.

Next, we bound $\mathcal I_2$ using \zcref{l:llt-events}. For $\varrho_N < |\xi| \le \Omega^{1/2}$, the bound \eqref{e:llt-intermediate} gives
\begin{equation}
|\Phi_H(\xi)|^n \le \Bigl( 1 - \frac{p_Y}{2} \tau^{-1/4} \Bigr)^{n/2} \le \exp\Bigl( - \frac{p_Y}{4} n \tau^{-1/4} \Bigr) \le \exp\Bigl( - \frac{p_Y}{40} \tau^{3/4} \Bigr).
\end{equation}
Using \eqref{e:llt-psihat-l1} and $n \le \tau$, we obtain
\begin{equation}
\mathcal I_2 \le C \tau^k \exp(- p_Y \tau^{3/4}/40).
\end{equation}

For large frequencies, we use the first bound in \eqref{e:llt-psihat} and $n \le \tau$, which give
\begin{equation}
\mathcal I_3 \le C \tau^k \int_{|\xi| > \Omega^{1/2}} |\xi|^{-2 \mathfrak s_k} \dd \xi = C \tau^k \Omega^{k - \mathfrak s_k} = C \tau^{k + (k - \mathfrak s_k)/(4 \mathfrak q_k)} = C \tau^{-1/(4 \mathfrak q_k)},
\end{equation}
where the last equality follows from the definition of $\mathfrak s_k$. Finally, changing variables as for $\mathcal I_1$, we find
\begin{equation}
\mathcal I_4 = |\hat \psi(0)| \int_{|\xi'| > \varrho_N n^{1/2}} e^{-2|\xi'|^2} \dd \xi' \le C e^{-\varrho_N^2 n} \le C \exp\bigl( - c N^{1/100 - 18 \eps_k} \bigr).
\end{equation}
The four bounds tend to zero, which proves \eqref{e:llt-main}.

It remains to prove \eqref{e:llt-smallball}. Since $B$ is bounded, there exists a nonnegative $\psi_B \in C_c^\infty(\R^{2k})$ with $\psi_B \ge 1$ on $B$. Applying \eqref{e:llt-main} with $\Psi = \{\psi_B\}$, we obtain
\begin{equation}
\Prob\bigl( S^{(n)} + x \in B \bigm| H \bigr) \le \E\bigl[ \psi_B\bigl( S^{(n)} + x \bigr) \bigm| H \bigr] \le (8 \pi n)^{-k} \int \psi_B + o(\tau^{-k}).
\end{equation}
The deterministic quantity that bounds the error term for the family $\{\psi_B\}$ is finite for every $N$ and $o(\tau^{-k})$, so it is bounded by $C \tau^{-k}$ for all $N$. Since $n \ge \tau/10$, the right side is therefore bounded by $C_B \tau^{-k}$.
\end{proof}

\section{Pairs with large gaps}\label{s:llt-largegap}

The second claim of \zcref{p:llt} concerns a single pair. In \zcref{l:largegap} and its proof, we apply the preceding results with $k = 1$. In particular, $\mathcal A_{N, 1}$ denotes the event of \zcref{d:llt-events} for $k = 1$, and for $i \in [N - 1]$ the objects $J$, $\bar J$, and $S^{(n)}$ refer to the $1$-tuple $\mathbf i = (i)$. Recall that $z_i = (-g_i/(2d), 0)$ and $\ell = d \tau^{1/2}$, so that
\begin{equation}\label{e:llt-zsize}
|z_i| = \frac{g_i}{2d} = \frac{g_i}{2\ell} \, \tau^{1/2}.
\end{equation}
When $g_i \ge \ell$, the vector $z_i$ lies at distance at least $\tau^{1/2}/2$ from the origin, so $z_i + S_i$ can be small only if $S_i$ makes a large deviation. The following lemma quantifies this.

\begin{lemma}\label{l:largegap}
There exists $c > 0$ such that for every $x_0 > 0$ there exists $C_{x_0} > 0$ with the following property. On $\mathcal A_{N, 1}$, for every $i \in [N - 1]$ such that $g_i \ge \ell$,
\begin{equation}\label{e:llt-largegap}
\Prob\bigl( |z_i + S_i| \le x_0 \bigm| H \bigr) \le C_{x_0} \tau^{-1} e^{- c g_i/\ell}.
\end{equation}
\end{lemma}

\begin{proof}
Let $N_1 \ge N_0$ be an integer depending on $x_0$, which will be chosen below; until the last paragraph of the proof, we assume that $N \ge N_1$. We begin with a bound on the moment generating function of one increment. The increment is unbounded because the fresh variable $Y$ is, so we restrict the parameter of the moment generating function to a range in which only $\E e^{|Y|/2} < \infty$ is needed. Set $\beta_0 = N^{-3 \eps_1}/4$, and let $\beta \in \R$ with $|\beta| \le \beta_0$. By \zcref{l:moments} with $k = 1$, we have on $\mathcal A_{N, 1}$ that, for $\eta \in \{1, 2\}$,
\begin{equation}
|J(\eta)| \le |J| \le 2 N^{2 \eps_1} \bigl( |Y| + N^{\eps_1} \bigr), \qquad \text{and hence} \qquad |\beta J(\eta)| \le \frac{|Y| + 1}{2}.
\end{equation}
Using $e^{t'} \le 1 + t' + t'^2 e^{|t'|}/2$ for real $t'$, we obtain
\begin{equation}\label{e:llt-mgf1}
\E\bigl[ e^{\beta J(\eta)} \bigm| H \bigr] \le 1 + \beta \bar J(\eta) + \frac{e^{1/2}}{2} \beta^2 \, \E\bigl[ J(\eta)^2 e^{|Y|/2} \bigm| H \bigr].
\end{equation}

To bound the last expectation, recall from \eqref{e:llt-secondmoment} that
\begin{equation}
\E\bigl[ J(\eta)^2 \bigm| H \bigr] = \binom{N}{2}^{-1} \sum_{a < b} (1 + X_{ab}^2) \bigl( D^{(i)}_{ab}(\eta) \bigr)^2,
\end{equation}
and that this quantity is bounded by $5$ by \zcref{l:moments}, provided $N_1$ is large enough. Conditioning on $(a, b)$ and using $(Y - X_{ab})^2 \le 2 Y^2 + 2 X_{ab}^2$, we find
\begin{equation}
\begin{split}
\E\bigl[ J(\eta)^2 e^{|Y|/2} \bigm| H \bigr] &\le 2 \binom{N}{2}^{-1} \sum_{a < b} \bigl( D^{(i)}_{ab}(\eta) \bigr)^2 \Bigl( \E\bigl[ Y^2 e^{|Y|/2} \bigr] + X_{ab}^2 \, \E\bigl[ e^{|Y|/2} \bigr] \Bigr) \\
&\le C \, \E\bigl[ J(\eta)^2 \bigm| H \bigr] \le C,
\end{split}
\end{equation}
where in the second inequality we used that $Y$ is sub-Gaussian. Inserting this into \eqref{e:llt-mgf1} and using $1 + t' \le e^{t'}$, we obtain, for some constant $C_* > 0$,
\begin{equation}\label{e:llt-mgf}
\E\bigl[ e^{\beta (J(\eta) - \bar J(\eta))} \bigm| H \bigr] \le e^{-\beta \bar J(\eta)} \bigl( 1 + \beta \bar J(\eta) + C_* \beta^2 \bigr) \le e^{C_* \beta^2}, \qquad |\beta| \le \beta_0.
\end{equation}

We next derive a tail bound for sums. Let $n \ge 1$ and $y > 0$. Conditionally on $H$, the vector $S^{(n)}$ is a sum of $n$ independent copies of $J$. Hence \eqref{e:llt-mgf} and Markov's inequality give for $0 < \beta \le \beta_0$, $\eta \in \{1, 2\}$, and either choice of sign,
\begin{equation}
\Prob\Bigl( \pm \bigl( S^{(n)} - n \bar J \bigr)(\eta) \ge \frac{y}{\sqrt 2} \Bigm| H \Bigr) \le \exp\Bigl( - \frac{\beta y}{\sqrt 2} + C_* n \beta^2 \Bigr).
\end{equation}
We choose
\begin{equation}
\beta =
\begin{cases}
y/(2\sqrt 2 C_* n) & \text{if } y/(2\sqrt 2 C_* n) \le \beta_0, \\
\beta_0 & \text{otherwise}.
\end{cases}
\end{equation}
In the second case, we have $C_* n \beta_0^2 \le \beta_0 y/(2\sqrt 2)$. Further, one of the two coordinates of $S^{(n)} - n \bar J$ has modulus at least $|S^{(n)} - n \bar J|/\sqrt 2$. Summing over the four cases, we conclude that
\begin{equation}\label{e:llt-chernoff}
\Prob\bigl( |S^{(n)} - n \bar J| \ge y \bigm| H \bigr) \le 4 \exp\Bigl( - \min\Bigl\{ \frac{y^2}{8 C_* n}, \frac{\beta_0 y}{2 \sqrt 2} \Bigr\} \Bigr).
\end{equation}

We now split the $m$ resampling steps into two halves. Recall that $m$ is even, and write $S_i = S' + S''$, where $S'$ is the sum of the first $m/2$ summands in \eqref{e:reduction-S} and $S''$ is the sum of the remaining $m/2$ summands. Conditionally on $H$, the vectors $S'$ and $S''$ are independent, and each has the conditional law of $S^{(m/2)}$. We also take $N_1$ large enough that for $N \ge N_1$ we have $\tau/10 \le m/2 \le \tau/3$, $m |\bar J| \le 1$ on $\mathcal A_{N, 1}$ (which is possible by \zcref{l:moments}), and $\tau^{1/2} \ge 4(x_0 + 1)$.

Suppose that $|z_i + S_i| \le x_0$. Using \eqref{e:llt-zsize} and $g_i \ge \ell$, we find $|z_i| \ge \tau^{1/2}/2$, and therefore
\begin{equation}
\Bigl| S' - \frac{m}{2} \bar J \Bigr| + \Bigl| S'' - \frac{m}{2} \bar J \Bigr| \ge |S' + S''| - m |\bar J| \ge |z_i| - x_0 - 1 \ge \frac{|z_i|}{2},
\end{equation}
where the last inequality follows from $|z_i| \ge \tau^{1/2}/2$ and $\tau^{1/2} \ge 4(x_0 + 1)$.
Hence
\begin{equation}
|S' - (m/2) \bar J| \ge |z_i|/4 \qquad \text{or} \qquad |S'' - (m/2) \bar J| \ge |z_i|/4.
\end{equation}
Let $B_{x_0} \subset \R^2$ be the closed disk of radius $x_0$ centered at $0$, and let $C_{B_{x_0}}$ be the constant of \eqref{e:llt-smallball} for $k = 1$. To bound the probability of the first event, we condition on $S'$ and use that $|z_i + S_i| \le x_0$ holds only if $S'' + z_i + S' \in B_{x_0}$. The vector $S''$ is conditionally independent of $S'$, so \eqref{e:llt-smallball} with $n = m/2$, followed by \eqref{e:llt-chernoff}, gives
\begin{equation}
\Prob\Bigl( |z_i + S_i| \le x_0, \ \Bigl| S' - \frac{m}{2} \bar J \Bigr| \ge \frac{|z_i|}{4} \Bigm| H \Bigr) \le \frac{C_{B_{x_0}}}{\tau} \, \Prob\Bigl( \Bigl| S^{(m/2)} - \frac{m}{2} \bar J \Bigr| \ge \frac{|z_i|}{4} \Bigm| H \Bigr).
\end{equation}
The second event is treated in the same way, with the roles of $S'$ and $S''$ exchanged.

We now evaluate \eqref{e:llt-chernoff} with $n = m/2 \le \tau/8$ and
\begin{equation}
y = \frac{|z_i|}{4} = \frac{g_i \tau^{1/2}}{8 \ell}.
\end{equation}
Our choice of $\eps_1$ in \eqref{e:llt-parameters} gives $\eps_1 \le 1/1200$, and hence $\tau^{1/2} N^{-3\eps_1} \ge 1$. Therefore
\begin{equation}
\frac{y^2}{8 C_* n} \ge \frac{1}{64 C_*} \Bigl( \frac{g_i}{\ell} \Bigr)^2, \qquad \frac{\beta_0 y}{2 \sqrt 2} = \frac{\tau^{1/2} N^{-3 \eps_1}}{64 \sqrt 2} \, \frac{g_i}{\ell} \ge \frac{1}{64 \sqrt 2} \, \frac{g_i}{\ell}.
\end{equation}
Since $g_i/\ell \ge 1$, the minimum in \eqref{e:llt-chernoff} is at least $c g_i/\ell$, where
\begin{equation}
c = \min\{(64 C_*)^{-1}, (64 \sqrt 2)^{-1}\}.
\end{equation}
Combining the two events, we conclude that
\begin{equation}
\Prob\bigl( |z_i + S_i| \le x_0 \bigm| H \bigr) \le \frac{8 C_{B_{x_0}}}{\tau} \, e^{-c g_i/\ell}, \qquad N \ge N_1.
\end{equation}

Finally, let $N < N_1$. On $\mathcal A_{N, 1}$, we have $g_i \le 2 \|H\| \le 6$ and $\ell \ge N^{-3/2} \ge N_1^{-3/2}$, so
\begin{equation}
\tau e^{c g_i/\ell} \le N_1 \exp(6 c N_1^{3/2}).
\end{equation}
Hence \eqref{e:llt-largegap} holds for all $N$ with $C_{x_0} = \max\{8 C_{B_{x_0}}, N_1 \exp(6 c N_1^{3/2})\}$.
\end{proof}

\begin{proof}[Proof of \zcref{p:llt}]
We show that the events $\mathcal A_{N, k}$ of \zcref{d:llt-events} have the properties stated in \zcref{p:llt}, with the constant $c$ of \zcref{l:largegap}. By \zcref{l:llt-events}, we have $\Prob(\mathcal A_{N, k}) \to 1$. These events are measurable with respect to $H$. Indeed, $\mathcal G_{\eps_k}$ is a Borel set, the other two conditions in \eqref{e:llt-regular} are closed conditions on $H$, and the set of matrices $A$ that have a unit eigenvector $w$ violating the inequality in \zcref{d:llt-events} is closed, as the projection along the compact unit sphere of the closed set of pairs $(A, w)$ such that $\|w\|_2 = 1$, $A w = (w^T A w) w$, and $w$ violates this inequality.

We now prove the local limit theorem. Let $\Psi$ be a family of test functions as in the statement of \zcref{p:llt}. The supports of its members lie in a common ball $\{y \in \R^{2k} : |y| \le R_\Psi\}$, so $\Psi$ satisfies the hypotheses of \zcref{l:llt}, and \eqref{e:llt-psibound} holds by the proof of that lemma. Let $\mathfrak e'_N$ denote the deterministic quantity of \zcref{l:llt} that bounds the error term in \eqref{e:llt-main} for this family $\Psi$. By \zcref{l:llt}, $\mathfrak e'_N$ is finite for every $N$, and $\tau^k \mathfrak e'_N \to 0$. We define
\begin{equation}\label{e:llt-eN}
\mathfrak e_N =
\begin{cases}
\tau^k \mathfrak e'_N + 16 (k + 1) \pi^{-k} \tau^{-1} \sup_{\psi \in \Psi} \int_{\R^{2k}} |\psi(y)| \dd y & \text{if } \tau \ge 16, \\
\sup_{\psi \in \Psi} \bigl( \tau^k \|\psi\|_\infty + (2\pi)^{-k} \int_{\R^{2k}} |\psi(y)| \dd y \bigr) & \text{if } \tau < 16.
\end{cases}
\end{equation}
Since $\mathfrak e'_N$ is finite, \eqref{e:llt-psibound} shows that the numbers $\mathfrak e_N$ are finite. They depend only on $k$ and $\Psi$, and they tend to zero because $\tau^k \mathfrak e'_N \to 0$. Next, we show that \eqref{e:reduction-llt} holds on $\mathcal A_{N, k}$.

If $\tau < 16$, then \eqref{e:reduction-llt} holds without any restriction on $H$, since $|\E[\psi(S_{\mathbf i} + x) \mid H]| \le \|\psi\|_\infty$ and $e^{-|x|^2/(2\tau)} \le 1$. Now suppose that $\tau \ge 16$. Recall from \zcref{s:llt-moments} that the conditional law of $S_{\mathbf i}$ given $H$ is that of $S^{(m)}$. Since $m = 2 \lfloor \tau/8 \rfloor$, we have $\tau - 8 < 4m \le \tau$, and hence $\tau/10 \le m \le \tau/3$ and $\tau/2 \le 4m \le \tau$. By \zcref{l:llt} with $n = m$, on $\mathcal A_{N, k}$, we have
\begin{equation}\label{e:llt-pllt1}
\Bigl| \E\bigl[ \psi(S_{\mathbf i} + x) \bigm| H \bigr] - \mathfrak g_{4 m \Id_{2k}}(x) \int \psi \Bigr| \le \mathfrak e'_N
\end{equation}
for all $k$-tuples $\mathbf i$, all $x \in \R^{2k}$, and all $\psi \in \Psi$. It remains to replace $4m$ by $\tau$. Differentiating $\mathfrak g_{r' \Id_{2k}}(x)$ with respect to $r' > 0$ and using $y' e^{-y'} \le 1$ for $y' \ge 0$, we find
\begin{equation*}
\bigl| \partial_{r'} \mathfrak g_{r' \Id_{2k}}(x) \bigr| \le \frac{k + 1}{r'} (2 \pi r')^{-k}, \qquad x \in \R^{2k}.
\end{equation*}
The numbers $4m$ and $\tau$ lie in $[\tau/2, \tau]$ and differ by at most $8$, so the mean value theorem gives
\begin{equation}
\sup_{x \in \R^{2k}} \bigl| \mathfrak g_{4m \Id_{2k}}(x) - \mathfrak g_{\tau \Id_{2k}}(x) \bigr| \le \frac{16 (k + 1)}{\tau} (\pi \tau)^{-k}.
\end{equation}
Inserting this into \eqref{e:llt-pllt1}, multiplying by $\tau^k$, and using $|\int \psi| \le \int |\psi|$ and
\begin{equation}
\tau^k \mathfrak g_{\tau \Id_{2k}}(x) = (2\pi)^{-k} e^{-|x|^2/(2\tau)},
\end{equation}
we obtain \eqref{e:reduction-llt} with $\mathfrak e_N$ as in \eqref{e:llt-eN}.

The second claim of \zcref{p:llt} concerns the events $\mathcal A_{N, 1}$. It follows from \zcref{l:largegap}, applied with $x_0/2$ in place of $x_0$. This completes the proof.
\end{proof}