\chapter{Preliminaries}\label{s:prelim}

In this section, we collect the facts about eigenvalues and eigenvectors that are used in the rest of the paper. \zcref[S]{s:prelim-estimates} contains regularity and rigidity estimates for $H$, $H_t$, and $G$, a level repulsion estimate for $H$, a coupling of the gaps of $H_t$ with those of the GOE, and the pair statistics of the GOE. \zcref[S]{s:prelim-perturbation} contains a deterministic lemma on the eigenvalues of a diagonal matrix perturbed by a Hermitian matrix with small entries, which we apply in \zcref{s:pairs}, \zcref{s:linearization}, and \zcref{s:hermitian}. \zcref[S]{s:prelim-gaussian} contains an elementary Gaussian estimate used in \zcref{s:pairs} and \zcref{s:hermitian}.

We first fix some notation for the rest of the paper. We write $\sigma_Z^2 = \E Z^2$, which is positive by \zcref{d:wigner}, and we set $X_{aa} = Z_a$ for $a \in [N]$, so that $X_{ab} = N^{1/2} H_{ab}$ for all $a \le b$. We define the real symmetric $N \times N$ matrices
\begin{equation}\label{e:prelim-V}
V^{ab} = e_a e_b^T + e_b e_a^T \quad (1 \le a < b \le N), \qquad V^{aa} = e_a e_a^T \quad (a \in [N]),
\end{equation}
so that every real symmetric $N \times N$ matrix $A$ satisfies $A = \sum_{a \le b} A_{ab} V^{ab}$. Throughout the paper, $G$ denotes a GOE matrix independent of $H$, whose upper-triangular entries are independent centered Gaussian random variables with variance $N^{-1}$ off the diagonal and $2 N^{-1}$ on the diagonal, and we set
\begin{equation}\label{e:prelim-Ht}
H_t = e^{-t/2} H + (1 - e^{-t})^{1/2} G, \qquad t \in [0, 1].
\end{equation}
For $i \in [N]$, we let $\gamma_i$ denote the classical location defined by $\int_{-2}^{\gamma_i} \rhosc(E) \dd E = i/N$. For events indexed by a parameter, we say that they hold with overwhelming probability \emph{uniformly} in the parameter if the constant $C_D$ in the definition of overwhelming probability can be chosen independent of the parameter.

\section{Estimates for eigenvalues and eigenvectors}\label{s:prelim-estimates}

We begin with the set of matrices on which our deterministic arguments take place.

\begin{definition}\label{d:regular}
Let $\eps > 0$. We define $\mathcal G_\eps$ to be the set of $N \times N$ real symmetric matrices $A$ with the following three properties.
\begin{enumerate}[label=(\roman*)]
\item $\|A\| \le 3$.
\item Every unit eigenvector $v \in \R^N$ of $A$ satisfies $\|v\|_\infty \le N^{-1/2 + \eps}$.
\item For all $E \in \R$, we have $\#\{ i \in [N] : \lambda_i(A) \in [E, E + N^{-1}] \} \le N^{\eps}$.
\end{enumerate}
We call the elements of $\mathcal G_\eps$ \emph{regular matrices}.
\end{definition}

Each of the three conditions becomes weaker as $\eps$ increases, so $\mathcal G_\eps \subset \mathcal G_{\eps'}$ for $\eps < \eps'$. (Using the continuity of eigenvalues and of total eigenprojections \cite{kato1995perturbation}, one checks that $\mathcal G_\eps$ is a Borel set.)

\begin{proposition}\label{p:regularity}
The following statements hold.
\begin{enumerate}[label=(\alph*)]
\item For all $\eps > 0$ and $D > 0$, there exists $C_{\eps, D} > 0$ such that $\Prob(H_t \notin \mathcal G_\eps) \le C_{\eps, D} N^{-D}$ for all $N \ge 2$ and $t \in [0, 1]$.
\item For all $c_* \in (0, 1/2)$, $\eps > 0$, and $D > 0$, there exists $C > 0$ such that for all $N \ge 2$ and $t \in [0, 1]$,
\begin{equation}\label{e:prelim-bulk-rigidity}
\Prob\Big( \max_{c_* N \le i \le (1 - c_*) N} |\lambda_i(H_t) - \gamma_i| > N^{-1 + \eps} \Big) \le C N^{-D}.
\end{equation}
\item For every integer $n \ge 1$, there exists $C_n > 0$ such that $\E \|H_t\|^n \le C_n$ for all $N \ge 2$ and $t \in [0, 1]$.
\end{enumerate}
The same statements hold with $H_t$ replaced by $G$.
\end{proposition}

The next lemma is an edge-inclusive rigidity estimate with subpolynomial precision, due to Erd\H{o}s, Yau, and Yin \cite{erdos2012rigidity}. It is used only for the coupling, in the proof of \zcref{p:coupling} and of its Hermitian analogue in \zcref{s:hermitian}.

\begin{lemma}\label{l:prelim-rigidity}
There exists $A_0 > 0$ such that, uniformly in $t \in [0, 1]$, with overwhelming probability,
\begin{equation}\label{e:prelim-edge-rigidity}
|\lambda_i(H_t) - \gamma_i| \le e^{A_0 (\log \log N)^2} N^{-2/3} \min(i, N + 1 - i)^{-1/3} \qquad \text{for all } i \in [N].
\end{equation}
The same statement holds with $H_t$ replaced by $G$.
\end{lemma}

\begin{proof}[Proof of \zcref{p:regularity}]
We deduce the proposition from the results of Benaych-Georges and Knowles \cite{benaychgeorges2016lectures}. Their Definition~2.2 concerns a sequence $A = A^{(N)}$ of $N \times N$ Hermitian random matrices with the following three properties.
\begin{enumerate}[label=(\arabic*)]
\item The entries $A_{ab}$ with $a \le b$ are independent.
\item We have $\E A_{ab} = 0$ for all $a, b$, $\E |A_{ab}|^2 = N^{-1}$ for $a \neq b$, and $\E |A_{aa}|^2 \le C N^{-1}$ for all $a$.
\item For every integer $n \ge 1$, there exists $C_n > 0$ such that $\E |N^{1/2} A_{ab}|^n \le C_n$ for all $N$, $a$, and $b$.
\end{enumerate}

We first check that (1)--(3) hold for $(H_{t_N})_{N \ge 2}$, for every sequence $(t_N)$ in $[0, 1]$, with constants independent of the sequence. The upper-triangular entries of $H_t$ are independent and centered, since $H$ and $G$ are independent and each has independent centered upper-triangular entries. For $a \le b$, we have
\begin{equation}\label{e:prelim-standardized}
N^{1/2} (H_t)_{ab} = e^{-t/2} X_{ab} + (1 - e^{-t})^{1/2} N^{1/2} G_{ab},
\end{equation}
and therefore
\begin{equation*}
\E (H_t)_{ab}^2 = \frac{1}{N} \quad (a \neq b), \qquad \E (H_t)_{aa}^2 = \frac{e^{-t} \sigma_Z^2 + 2 (1 - e^{-t})}{N} \le \frac{\max(\sigma_Z^2, 2)}{N}.
\end{equation*}
Using \eqref{e:prelim-standardized}, Minkowski's inequality, and the sub-Gaussian tails of $X$, $Z$, and $N^{1/2} G_{ab}$, we see that the moments of $N^{1/2} (H_t)_{ab}$ are bounded uniformly in $t$, $N$, $a$, and $b$. The GOE matrix $G$ satisfies (1)--(3) by \cite[Example~2.3]{benaychgeorges2016lectures}.

Next, let $A$ be a sequence with the properties (1)--(3). We claim that for all $\eps \in (0, 1/4]$, $c_* \in (0, 1/2)$, and $D > 0$, there exists $N_0$ such that for all $N \ge N_0$,
\begin{equation}\label{e:prelim-bgk-claim}
\Prob(A \notin \mathcal G_\eps) + \Prob\Big( \max_{c_* N \le i \le (1 - c_*) N} |\lambda_i(A) - \gamma_i| > N^{-1 + \eps} \Big) \le N^{-D}.
\end{equation}

We first show that the claim implies (a) and (b). The events in (a) and (b) decrease as $\eps$ increases, so it suffices to consider $\eps \le 1/4$. Suppose that (a) or (b) fails for some $\eps$, $c_*$, and $D$. Then for infinitely many $N$, there exists $t_N \in [0, 1]$ such that the left side of \eqref{e:prelim-bgk-claim} with $A = H_{t_N}$ is larger than $N^{-D}$, since otherwise a suitable constant would give the bounds in (a) and (b) for all $N$ and $t$. Setting $t_N = 0$ for all other $N$, we obtain a sequence $(H_{t_N})$ with the properties (1)--(3) for which \eqref{e:prelim-bgk-claim} fails, which is a contradiction. Applying \eqref{e:prelim-bgk-claim} to $A = G$, we also obtain (a) and (b) for $G$.

We now prove the claim, and we begin with the norm and the diagonal resolvent entries. By \cite[Theorem~G.1]{benaychgeorges2016lectures}, we have $\|A\| \le 3$ with overwhelming probability. For $w = E + \iu \eta$ with $\eta > 0$, let
\begin{equation*}
m_{\mathrm{sc}}(w) = \int_{-2}^{2} \frac{\rhosc(E')}{E' - w} \dd E', \qquad \mathfrak r(w) = \Big( \frac{\Im m_{\mathrm{sc}}(w)}{N \eta} \Big)^{1/2} + \frac{1}{N \eta}
\end{equation*}
denote the Stieltjes transform of the semicircle law and the error parameter of \cite[(2.16)]{benaychgeorges2016lectures}, and recall that $|m_{\mathrm{sc}}(w)| \le 1$. We also set
\begin{equation*}
\mathcal W_\eps = \{ E + \iu \eta : |E| \le 4/\eps, \ N^{-1 + \eps/4} \le \eta \le 4/\eps \}.
\end{equation*}
The local semicircle law \cite[Theorem~2.6]{benaychgeorges2016lectures}, in the form \cite[(2.17)]{benaychgeorges2016lectures} that holds simultaneously for all spectral parameters, applied with the spectral domain $\mathcal W_\eps$, shows that with overwhelming probability
\begin{equation*}
|((A - w)^{-1})_{aa} - m_{\mathrm{sc}}(w)| \le N^{\eps/4} \mathfrak r(w) \qquad \text{for all } a \in [N] \text{ and } w \in \mathcal W_\eps.
\end{equation*}

We have $\mathfrak r \le 2$ on $\mathcal W_\eps$, as $\Im m_{\mathrm{sc}} \le 1$ and $N \eta \ge 1$ there. Therefore, with overwhelming probability,
\begin{equation}\label{e:prelim-resolvent}
\max_{a \in [N]} \sup_{w \in \mathcal W_\eps} |((A - w)^{-1})_{aa}| \le 3 N^{\eps/4}.
\end{equation}

Let $\mathcal U$ denote the event that $\|A\| \le 3$ and \eqref{e:prelim-resolvent} hold. We will show that conditions (ii) and (iii) of \zcref{d:regular} hold on $\mathcal U$ for $N \ge N_0(\eps)$. These deductions from the local law are standard (compare the proof of \cite[Theorem~2.10]{benaychgeorges2016lectures}). We write them out because condition (ii) concerns every unit eigenvector, including the eigenvectors of multiple eigenvalues.

We first derive (ii). For an eigenvalue $\lambda$ of $A$, let $\Pi_\lambda$ denote the orthogonal projection onto its eigenspace, so that
\begin{equation*}
(A - w)^{-1} = \sum_{\lambda'} \frac{\Pi_{\lambda'}}{\lambda' - w}, \qquad w \in \C \setminus \R,
\end{equation*}
where the sum runs over the distinct eigenvalues of $A$. Let $v$ be a unit eigenvector of $A$ with eigenvalue $\lambda$, and let $a \in [N]$. For all $\eta > 0$, we have
\begin{equation}\label{e:prelim-projection}
|v(a)|^2 = |(\Pi_\lambda e_a) \cdot v|^2 \le (\Pi_\lambda)_{aa} \le \eta \sum_{\lambda'} \frac{\eta \, (\Pi_{\lambda'})_{aa}}{(\lambda' - \lambda)^2 + \eta^2} = \eta \Im \big( (A - \lambda - \iu \eta)^{-1} \big)_{aa}.
\end{equation}
Here the first equality follows from $v = \Pi_\lambda v$, the first inequality follows from the Cauchy--Schwarz inequality and $\|\Pi_\lambda e_a\|_2^2 = (\Pi_\lambda)_{aa}$, and the second inequality follows from the fact that $(\Pi_{\lambda'})_{aa} \ge 0$ for every eigenvalue $\lambda'$.

We now use \eqref{e:prelim-projection} on $\mathcal U$. There we have $|\lambda| \le 3 \le 4/\eps$, so $\lambda + \iu N^{-1 + \eps/4} \in \mathcal W_\eps$. Using \eqref{e:prelim-projection} with $\eta = N^{-1 + \eps/4}$ and \eqref{e:prelim-resolvent}, we obtain
\begin{equation*}
|v(a)|^2 \le 3 N^{-1 + \eps/2} \le N^{-1 + 2\eps}
\end{equation*}
for $N \ge N_0(\eps)$, which gives (ii).

Next, we derive (iii). Fix $E \in \R$, and note that the set in (iii) is empty on $\mathcal U$ unless $[E, E + N^{-1}]$ intersects $[-3, 3]$, so we may assume this. Then $E' = E + (2N)^{-1}$ satisfies $|E'| \le 4$. We set $\eta = N^{-1 + \eps/4}$, so that $E' + \iu \eta \in \mathcal W_\eps$. Every $i$ with $\lambda_i(A) \in [E, E + N^{-1}]$ satisfies
\begin{equation*}
|\lambda_i(A) - E'| \le (2N)^{-1} \le \eta, \qquad \text{and hence} \qquad \frac{\eta}{(\lambda_i(A) - E')^2 + \eta^2} \ge \frac{1}{2\eta}.
\end{equation*}

Summing over these $i$, we obtain
\begin{equation*}
\begin{aligned}
\#\{ i : \lambda_i(A) \in [E, E + N^{-1}] \} &\le 2 \eta \sum_{i = 1}^N \frac{\eta}{(\lambda_i(A) - E')^2 + \eta^2} \\
&= 2 \eta \sum_{a = 1}^N \Im \big( (A - E' - \iu \eta)^{-1} \big)_{aa} \le 6 N^{\eps/2},
\end{aligned}
\end{equation*}
where we used \eqref{e:prelim-resolvent} in the last step. The right side is bounded by $N^\eps$ for $N \ge N_0(\eps)$, which gives (iii).

As $\|A\| \le 3$ on $\mathcal U$, we conclude that the first term in \eqref{e:prelim-bgk-claim} is bounded by $\Prob(\mathcal U^c) \le N^{-D}/2$ for $N \ge N_0$.

We now prove the rigidity estimate in \eqref{e:prelim-bgk-claim}. The eigenvalues in \cite{benaychgeorges2016lectures} are labeled in decreasing order, and the typical location $\gamma_i^{\mathrm{BK}}$ of the $i$-th largest eigenvalue is defined there by the first relation in
\begin{equation*}
N \int_{\gamma_i^{\mathrm{BK}}}^2 \rhosc(E) \dd E = i - \frac12, \qquad N \int_{-2}^{\gamma_i'} \rhosc(E) \dd E = i - \frac12.
\end{equation*}
The second relation holds for $\gamma_i' = \gamma_{N + 1 - i}^{\mathrm{BK}}$. After relabeling, \cite[Theorem~2.9]{benaychgeorges2016lectures} and a union bound over $i$ show that with overwhelming probability
\begin{equation*}
|\lambda_i(A) - \gamma_i'| \le N^{\eps/2} N^{-2/3} \min(i, N + 1 - i)^{-1/3} \qquad \text{for all } i \in [N].
\end{equation*}
Let $c_* N \le i \le (1 - c_*) N$ and $N \ge 2/c_*$. Then $i/N$ and $(i - 1/2)/N$ belong to $[c_*/2, 1 - c_*/2]$, and $\rhosc$ is bounded below on the energies whose quantiles lie in this interval, so the mean value theorem gives $|\gamma_i - \gamma_i'| \le C N^{-1}$. Since $\min(i, N + 1 - i) \ge c_* N$, we conclude that with overwhelming probability
\begin{equation*}
|\lambda_i(A) - \gamma_i| \le |\lambda_i(A) - \gamma_i'| + |\gamma_i' - \gamma_i| \le N^{\eps/2} c_*^{-1/3} N^{-1} + C N^{-1} \le N^{-1 + \eps}
\end{equation*}
for all such $i$ and all $N \ge N_0$. This completes the proof of the claim.

Finally, we prove (c). By \cite[Theorem~H.1]{benaychgeorges2016lectures}, if an $N \times N$ Hermitian matrix $A$ with independent centered upper-triangular entries satisfies $\E \exp(c' N |A_{ab}|^2) \le 1/c'$ for all $a, b$ and some $c' > 0$, then
\begin{equation*}
\Prob(\|A\| \ge x) \le \exp\big( -c (x^2 - C) N \big) \qquad \text{for all } x > 0,
\end{equation*}
where $c, C > 0$ depend only on $c'$. By \eqref{e:prelim-standardized}, we have
\begin{equation*}
N |(H_t)_{ab}|^2 \le 2 X_{ab}^2 + 2 N G_{ab}^2,
\end{equation*}
so the independence of $H$ and $G$ and the sub-Gaussian tails of $X$, $Z$, and $N^{1/2} G_{ab}$ show that this hypothesis holds for $H_t$ with some $c' > 0$ independent of $t$, and also for $G$. Setting $x_0 = (2C)^{1/2}$, we find
\begin{equation*}
\E \|H_t\|^n = \int_0^\infty n x^{n - 1} \Prob(\|H_t\| \ge x) \dd x \le x_0^n + \int_{x_0}^\infty n x^{n - 1} e^{-c x^2 N/2} \dd x \le C_n,
\end{equation*}
where we used that $x^2 - C \ge x^2/2$ for $x \ge x_0$. The same computation applies to $G$.
\end{proof}

\begin{proof}[Proof of \zcref{l:prelim-rigidity}]
We use \cite[Theorem~2.2]{erdos2012rigidity}. It concerns an $N \times N$ real symmetric matrix $A$ with independent centered upper-triangular entries whose variances $\sigma_{ab}^2 = \E A_{ab}^2$ satisfy the following three conditions.
\begin{enumerate}[label=(\arabic*)]
\item The variances in each column sum to one, which is \cite[(2.2)]{erdos2012rigidity}.
\item There exist constants $0 < C_- \le C_+$ with $C_- \le N \sigma_{ab}^2$ and $N \sigma_{ab}^2 \le C_+$ for all $a, b \in [N]$. By \cite[Example~1]{erdos2012rigidity}, this implies the assumption \cite[(2.3)]{erdos2012rigidity}. Further, it implies \cite[(2.4)]{erdos2012rigidity} directly.
\item The variables $A_{ab}/\sigma_{ab}$ have uniformly subexponential tails in the sense of \cite[(2.17)]{erdos2012rigidity}.
\end{enumerate}

The classical locations in \cite{erdos2012rigidity} coincide with our $\gamma_i$, and the eigenvalues there are labeled in increasing order. Let $A_1 > 1$ be the constant in the lower bound on the parameter $L$ in \cite[(2.18)]{erdos2012rigidity}. Under the three conditions above, \cite[(2.25)]{erdos2012rigidity} with $L = A_1 \log \log N$ states that
\begin{equation}\label{e:prelim-eyy}
\begin{aligned}
&\Prob\Big( \exists \, i \in [N] : |\lambda_i(A) - \gamma_i| \ge e^{A_1 (\log \log N)^2} N^{-2/3} \min(i, N + 1 - i)^{-1/3} \Big) \\
&\qquad \le C \exp\big( - c \, e^{c_1 A_1 (\log \log N)^2} \big)
\end{aligned}
\end{equation}
for $N \ge N_0$, where $c_1 \in (0, 1)$, and where $A_1$, $c$, $c_1$, $C$, and $N_0$ depend only on $C_\pm$ and on the constants in \cite[(2.17)]{erdos2012rigidity}. Here we used that $(\log N)^{L} = e^{A_1 (\log \log N)^2}$, and that the upper bound on $L$ in \cite[(2.18)]{erdos2012rigidity} holds for $N$ large. Since $e^{c_1 A_1 (\log \log N)^2}$ grows faster than every multiple of $\log N$, the right side of \eqref{e:prelim-eyy} is bounded by $C_D N^{-D}$ for every $D > 0$.

The matrix $H_t$ violates the first condition by a term of order $N^{-1}$, and we correct this by a scalar factor. Let
\begin{equation*}
\sigma_t^2 = e^{-t} \sigma_Z^2 + 2 (1 - e^{-t}), \qquad r_{N, t} = 1 + \frac{\sigma_t^2 - 1}{N},
\end{equation*}
so that $\sigma_t^2$ is the variance of $N^{1/2} (H_t)_{aa}$. By the computation of the variances in the proof of \zcref{p:regularity}, we have
\begin{equation*}
\sum_{a = 1}^N \E (H_t)_{ab}^2 = \frac{N - 1}{N} + \frac{\sigma_t^2}{N} = r_{N, t} \qquad \text{for all } b \in [N],
\end{equation*}
so the matrix $A = r_{N, t}^{-1/2} H_t$ satisfies the first condition.

Recall that $\sigma_Z^2 > 0$ (this is needed for the lower bound below). It follows that for $N \ge 2$,
\begin{equation*}
0 < \min(\sigma_Z^2, 2) \le \sigma_t^2 \le \max(\sigma_Z^2, 2), \qquad \frac12 \le r_{N, t} \le 1 + \max(\sigma_Z^2, 2).
\end{equation*}
The variances of the entries of $A$ satisfy
\begin{equation*}
N \sigma_{ab}^2 = r_{N, t}^{-1} \quad (a \neq b), \qquad N \sigma_{aa}^2 = \sigma_t^2 r_{N, t}^{-1},
\end{equation*}
so we obtain the second condition in the form
\begin{equation*}
\frac{\min(\sigma_Z^2, 1)}{1 + \max(\sigma_Z^2, 2)} \le N \sigma_{ab}^2 \le 2 \max(\sigma_Z^2, 2) \qquad \text{for all } a, b \in [N].
\end{equation*}

We next check the third condition. By \eqref{e:prelim-standardized}, we have
\begin{equation*}
\frac{A_{ab}}{\sigma_{ab}} = e^{-t/2} X_{ab} + (1 - e^{-t})^{\frac12} N^{\frac12} G_{ab} \ \ (a \neq b), \qquad \frac{A_{aa}}{\sigma_{aa}} = \frac{e^{-t/2} Z_a + (1 - e^{-t})^{\frac12} N^{\frac12} G_{aa}}{\sigma_t}.
\end{equation*}
These variables have sub-Gaussian tails with constants independent of $t$, $N$, $a$, and $b$, as $\sigma_t^2 \ge \min(\sigma_Z^2, 2)$. This implies \cite[(2.17)]{erdos2012rigidity} with constants independent of $t$. Hence \eqref{e:prelim-eyy} holds for $A = r_{N, t}^{-1/2} H_t$, with constants independent of $t$.

We now return to $H_t$. For $N \ge N_0$, we have $|\lambda_i(A)| \le 3$ for all $i$ on the complement of the event in \eqref{e:prelim-eyy}. Since $\lambda_i(H_t) = r_{N, t}^{1/2} \lambda_i(A)$, we find on this complement that
\begin{equation*}
\begin{aligned}
|\lambda_i(H_t) - \lambda_i(A)| &= |r_{N, t}^{1/2} - 1| \, |\lambda_i(A)| \le 3 |r_{N, t} - 1| \\
&\le C N^{-1} \le C N^{-2/3} \min(i, N + 1 - i)^{-1/3}, \qquad i \in [N],
\end{aligned}
\end{equation*}
where we used $|r_{N, t}^{1/2} - 1| \le |r_{N, t} - 1|$. Combining this with \eqref{e:prelim-eyy}, we obtain on the same complement that, for $N$ large and all $i \in [N]$,
\begin{equation*}
\begin{aligned}
|\lambda_i(H_t) - \gamma_i| &\le \big( e^{A_1 (\log \log N)^2} + C \big) N^{-2/3} \min(i, N + 1 - i)^{-1/3} \\
&\le e^{(A_1 + 1)(\log \log N)^2} N^{-2/3} \min(i, N + 1 - i)^{-1/3}.
\end{aligned}
\end{equation*}
This is \eqref{e:prelim-edge-rigidity} with $A_0 = A_1 + 1$. For $G$, the same argument applies with $\sigma_t^2$ replaced by $2$.
\end{proof}

We next record the tail bound of Nguyen, Tao, and Vu \cite{nguyen2017random} for the distance between eigenvalues whose labels differ by two.

\begin{proposition}\label{p:three}
For every $C_1 > 0$, there exists $C > 0$ such that
\begin{equation}\label{e:prelim-three}
\sup_{1 \le i \le N - 2} \Prob\big( \lambda_{i + 2} - \lambda_i \le \delta/N \big) \le C \delta^3 \qquad \text{for all } \delta \ge N^{-C_1}.
\end{equation}
Further, for $r > 0$, let $\mathcal N_3(r)$ denote the number of $i \in [N - 2]$ such that $\lambda_{i + 2} - \lambda_i \le r$. Then $\E \mathcal N_3(r) \le C N (N r)^3$ for all $r \ge N^{-1 - C_1}$.
\end{proposition}

\begin{proof}
This is \cite[Corollary~2.5]{nguyen2017random} with $l = 2$, for which the exponent $c_l$ there equals $3$, translated to our normalization. That corollary concerns real symmetric Wigner matrices in the sense of \cite[Section~1]{nguyen2017random}, whose strictly upper-triangular entries are independent and identically distributed sub-Gaussian random variables with mean zero and variance one, and whose diagonal entries are independent sub-Gaussian random variables with mean zero and variance at most $N^{1 - o(1)}$, independent of the strictly upper-triangular entries. These hypotheses allow atomic entry distributions. The matrix $N^{1/2} H$, whose entries are the $X_{ab}$ and the $Z_a$, is of this form, since $Z_a$ has variance $\sigma_Z^2$.

For every $C_1 > 0$, \cite[Corollary~2.5]{nguyen2017random} gives $C > 0$ such that
\begin{equation*}
\sup_{1 \le i \le N - 2} \Prob\big( \lambda_{i + 2}(N^{1/2} H) - \lambda_i(N^{1/2} H) \le \delta N^{-1/2} \big) \le C \delta^3 \qquad \text{for all } \delta \ge N^{-C_1}.
\end{equation*}
As $\lambda_i(N^{1/2} H) = N^{1/2} \lambda_i$, this is \eqref{e:prelim-three}. Applying \eqref{e:prelim-three} with $\delta = N r$, we obtain
\begin{equation*}
\E \mathcal N_3(r) = \sum_{i = 1}^{N - 2} \Prob(\lambda_{i + 2} - \lambda_i \le r) \le C N (N r)^3, \qquad r \ge N^{-1 - C_1}.
\end{equation*}
\end{proof}

We next describe the coupling of the gaps of $H_t$ with those of the GOE, which is due to Bourgade \cite{bourgade2022extreme}. Let $\mathsf B = (\mathsf B(t))_{t \ge 0}$ be an $N \times N$ real symmetric matrix of Brownian motions, independent of $H$ and $G$, such that the processes $\mathsf B_{ab}$ with $a < b$ and $2^{-1/2} \mathsf B_{aa}$ with $a \in [N]$ are independent standard Brownian motions. Let $(H^{\mathrm{dyn}}_t)_{t \ge 0}$ denote the matrix Ornstein--Uhlenbeck process
\begin{equation}\label{e:prelim-ou}
H^{\mathrm{dyn}}_t = e^{-t/2} H + N^{-1/2} \int_0^t e^{-(t - t')/2} \dd \mathsf B(t'),
\end{equation}
which is the solution of $\dd H^{\mathrm{dyn}}_t = N^{-1/2} \dd \mathsf B(t) - 2^{-1} H^{\mathrm{dyn}}_t \dd t$ with $H^{\mathrm{dyn}}_0 = H$. For each $t \ge 0$, the stochastic integral in \eqref{e:prelim-ou} is a centered Gaussian real symmetric matrix, independent of $H$, whose upper-triangular entries are independent with variance $(1 - e^{-t}) N^{-1}$ off the diagonal and $2 (1 - e^{-t}) N^{-1}$ on the diagonal. Hence $H^{\mathrm{dyn}}_t$ has the law of $H_t$ for $t \in [0, 1]$. We write $\lambda_i(t) = \lambda_i(H^{\mathrm{dyn}}_t)$.

Let $\mathcal E_0$ denote the event that the eigenvalues of $H$ are distinct. As recalled in \cite[Section~1.4]{bourgade2022extreme}, the eigenvalues of $H^{\mathrm{dyn}}_t$ form, on $\mathcal E_0$, the unique strong solution of the system
\begin{equation}\label{e:prelim-dbm}
\dd \lambda_i(t) = \frac{\dd \beta_i(t)}{N^{1/2}} + \Big( \frac{1}{N} \sum_{j \neq i} \frac{1}{\lambda_i(t) - \lambda_j(t)} - \frac{\lambda_i(t)}{2} \Big) \dd t, \qquad i \in [N],
\end{equation}
where $\beta_1, \dots, \beta_N$ are independent Brownian motions with $\E \beta_i(t)^2 = 2t$. We extend this definition to the complement of $\mathcal E_0$ by letting $\beta_1, \dots, \beta_N$ be independent Brownian motions with the same variance there, independent of all other random variables. We let $\mu(t) = (\mu_1(t), \dots, \mu_N(t))$ denote the solution of \eqref{e:prelim-dbm} driven by the same $\beta_i$, with initial condition $\mu_i(0) = \lambda_i(G)$. The spectrum of $G$ is simple almost surely, and the $\beta_i$ are independent of $G$, since $\mathsf B$ is independent of $(H, G)$. The law of the spectrum of $G$ is invariant for \eqref{e:prelim-dbm} (see the discussion of \cite[(2.2)]{bourgade2022extreme}), so $\mu(t)$ has the law of the spectrum of $G$ for every $t \ge 0$. This is the coupling of \cite[(1.7)--(1.8)]{bourgade2022extreme}, with $\lambda(t)$ and $\mu(t)$ corresponding to the parameter values $0$ and $1$ of the interpolation there.

\begin{proposition}\label{p:coupling}
For all $c_* \in (0, 1/2)$, $\eps > 0$, and $D > 0$, there exists $N_0$ such that for all $N \ge N_0$ and $N^{-1 + \eps} \le t < 1$,
\begin{equation}\label{e:prelim-coupling}
\Prob\Big( \max_{c_* N \le i \le (1 - c_*) N} \big| (\lambda_{i + 1}(t) - \lambda_i(t)) - (\mu_{i + 1}(t) - \mu_i(t)) \big| > \frac{N^\eps}{N^2 t} \Big) \le N^{-D}.
\end{equation}
In particular, for every such $t$, the spectrum of $H_t$ and that of a GOE matrix can be coupled so that the event in \eqref{e:prelim-coupling} has probability at most $N^{-D}$.
\end{proposition}

\begin{proof}
This follows from \cite[Corollary~3.3]{bourgade2022extreme} and a union bound, and we now check its hypotheses. That corollary states the following. For all $c_*, \eps, D > 0$, there exist $C, N_0 > 0$ such that for all $N \ge N_0$, all $t$ with $e^{C (\log \log N)^2} N^{-1} < t < 1$, and all $i$ with $c_* N \le i \le (1 - c_*) N$,
\begin{equation}\label{e:prelim-bourgade}
\Prob\Big( \big| (\lambda_{i + 1}(t) - \lambda_i(t)) - (\mu_{i + 1}(t) - \mu_i(t)) \big| > \frac{N^\eps}{N^2 t} \Big) \le N^{-D}.
\end{equation}
In \cite{bourgade2022extreme}, the initial condition $\lambda(0)$ is the spectrum of a generalized Wigner matrix in the sense of \cite[Definition~1.1]{bourgade2022extreme}, $\mu(0)$ is the spectrum of a GOE matrix, and the initial points are distinct.

First, the variances of the entries of a generalized Wigner matrix in \cite[Definition~1.1]{bourgade2022extreme} have row sums exactly one, whereas those of $H$ have row sums $1 + (\sigma_Z^2 - 1)/N$. However, \cite[Remarks~2.9 and~3.2]{bourgade2022extreme} state that the results hold, for every value of the symmetry parameter in \cite[(2.2)]{bourgade2022extreme} that is at least one, whenever the initial conditions satisfy optimal rigidity estimates. Indeed, the proofs of \cite[Theorem~3.1 and Corollary~3.3]{bourgade2022extreme} use the initial spectra only through the rigidity event of \cite[(2.7)]{bourgade2022extreme} and the lower bound $1 - N^{-D}$ on its probability in \cite[Lemma~2.3]{bourgade2022extreme}. (The GOE initial condition used there also has row sums $1 + N^{-1}$.) This event requires that for every initial condition on the segment between $\lambda(0)$ and $\mu(0)$, the solution $x$ of \eqref{e:prelim-dbm} with this initial condition satisfies
\begin{equation*}
|x_i(t') - \gamma_i| < e^{C' (\log \log N)^2/2} N^{-2/3} \min(i, N + 1 - i)^{-1/3}
\end{equation*}
for all $i \in [N]$ and $t' \in [0, 1]$, where $C'$ is a sufficiently large constant.

As explained before \cite[Lemma~2.3]{bourgade2022extreme}, the lower bound on the probability of this event follows from rigidity estimates at fixed times for the spectra of $H^{\mathrm{dyn}}_{t'}$ with $t' \in [0, 1]$ and of a GOE matrix (the solutions started at the endpoints $\lambda(0)$ and $\mu(0)$). The passage to all times and to the whole segment uses a discretization in time and along the segment, Weyl's inequality, and a maximum principle for the derivative of the solution along the segment. Recall that $H^{\mathrm{dyn}}_{t'}$ has the law of $H_{t'}$. For our initial data, the fixed-time estimates are therefore given by \zcref{l:prelim-rigidity}, applied to $H_{t'}$ and to $G$, since
\begin{equation*}
e^{A_0 (\log \log N)^2} \le \frac12 e^{C' (\log \log N)^2/2}
\end{equation*}
for $C' > 2 A_0$ and $N$ large. The remaining steps use only \eqref{e:prelim-ou}, \eqref{e:prelim-dbm}, and bounds on $\|H^{\mathrm{dyn}}_{t'}\|$, which follow from \zcref{p:regularity}, so the conclusion of \cite[Lemma~2.3]{bourgade2022extreme} holds for our initial data as well.

Second, the system \eqref{e:prelim-dbm} is set up in \cite{bourgade2022extreme} for distinct initial points, which holds on $\mathcal E_0$. By \cite[Corollary~2.2]{nguyen2017random}, applied to $N^{1/2} H$ as in the proof of \zcref{p:three}, for every $C_1 > 0$ there exists $C_{\mathrm{NTV}} > 0$ such that
\begin{equation*}
\Prob(\lambda_{i + 1} - \lambda_i \le N^{-1 - C_1}) \le C_{\mathrm{NTV}} N^{-C_1} \qquad \text{for all } i \in [N - 1].
\end{equation*}
A union bound over $i$ gives
\begin{equation*}
\Prob(\mathcal E_0^c) \le \sum_{i = 1}^{N - 1} \Prob(\lambda_{i + 1} - \lambda_i \le N^{-1 - C_1}) \le C_{\mathrm{NTV}} N^{1 - C_1},
\end{equation*}
and since $C_1$ is arbitrary, $\mathcal E_0$ holds with overwhelming probability. (See also \cite{tao2017random}.) We apply \cite[Corollary~3.3]{bourgade2022extreme} on $\mathcal E_0$ and include $\mathcal E_0^c$ in the exceptional event.

Third, \eqref{e:prelim-bourgade} concerns a single index $i$. We apply it with $D + 2$ in place of $D$ and take a union bound over the at most $N$ indices $i$ with $c_* N \le i \le (1 - c_*) N$. Together with $\Prob(\mathcal E_0^c) \le N^{-D - 1}$ for large $N$, this bounds the probability in \eqref{e:prelim-coupling} by
\begin{equation*}
N \cdot N^{-D - 2} + \Prob(\mathcal E_0^c) \le 2 N^{-D - 1} \le N^{-D}.
\end{equation*}
Finally, $e^{C (\log \log N)^2} N^{-1} < N^{-1 + \eps}$ for $N$ large, so every $t \in [N^{-1 + \eps}, 1)$ belongs to the range of \cite[Corollary~3.3]{bourgade2022extreme}; the upper limit $t < 1$ is strict there. The last statement of the proposition holds because $\lambda(t)$ has the law of the spectrum of $H_t$ and $\mu(t)$ has the law of the spectrum of $G$.
\end{proof}

For $\alpha \in (0, 1/2)$, we set
\begin{equation}\label{e:prelim-scales}
\ell_\alpha = N^{-1 - \alpha}, \qquad M_\alpha = N^{1 - 2\alpha} = N^3 \ell_\alpha^2.
\end{equation}
The next proposition gives the pair statistics of the GOE at the scale $\ell_\alpha$ for $\alpha < 1/4$. We use it for the base case in \zcref{s:pairs}, and we prove it in \zcref{s:goe}.

\begin{proposition}\label{p:goepairs}
Let $\alpha \in (0, 1/4)$ and $p > 1$. Let $f \colon [0, \infty) \times \R \to \R$ be a continuous function for which there exist a bulk interval $I$ and a constant $C_f > 0$ such that $f(r, E) = 0$ for $E \notin I$ and $|f(r, E)| \le C_f (1 + r^2)^{-p}$ for all $(r, E)$. Then, in $L^1$ and hence in probability,
\begin{equation}\label{e:prelim-goepairs}
\frac{1}{M_\alpha} \sum_{1 \le i < j \le N} f\Big( \frac{\lambda_j(G) - \lambda_i(G)}{\ell_\alpha}, \frac{\lambda_i(G) + \lambda_j(G)}{2} \Big) \longrightarrow \int_{-2}^{2} \int_0^\infty c(E) \, r f(r, E) \dd r \dd E.
\end{equation}
\end{proposition}

\section{Eigenvalues of entrywise small perturbations}\label{s:prelim-perturbation}

We now consider a diagonal matrix perturbed by a Hermitian matrix with small entries. We group the diagonal entries into clusters of nearby points, and we compare the eigenvalues near each cluster with those of the corresponding diagonal block of the perturbed matrix. In \zcref{s:pairs}, \zcref{s:linearization}, and \zcref{s:hermitian}, the diagonal matrix contains the eigenvalues of $H$ (multiplied by $e^{-t/2}$ in \zcref{s:pairs} and \zcref{s:hermitian}), and the perturbation is a Gaussian matrix or the resampling perturbation $\Delta$, written in the eigenbasis of $H$.

We use the following notation in this section. For an $N \times N$ matrix $A$ and nonempty sets $\mathcal K, \mathcal K' \subset [N]$, we let $A_{\mathcal K \mathcal K'} = (A_{ij})_{i \in \mathcal K, j \in \mathcal K'}$ denote the corresponding submatrix, with rows and columns in increasing order, and we set $\mathcal K^c = [N] \setminus \mathcal K$. For a Hermitian matrix $A$, we let $n_-(A)$ denote the number of negative eigenvalues of $A$, counted with multiplicity. For a matrix $M$, we let $\|M\|_{\infty \to \infty} = \max_i \sum_j |M_{ij}|$ denote its operator norm on $\ell^\infty$.

We will use the inertia additivity formula of Haynsworth \cite{haynsworth1968determination}. Let $M$ be an $N \times N$ Hermitian matrix and let $\mathcal K \subset [N]$ be a nonempty proper subset such that $M_{\mathcal K^c \mathcal K^c}$ is invertible. Let
\begin{equation*}
M / M_{\mathcal K^c \mathcal K^c} = M_{\mathcal K \mathcal K} - M_{\mathcal K \mathcal K^c} M_{\mathcal K^c \mathcal K^c}^{-1} M_{\mathcal K^c \mathcal K}
\end{equation*}
denote the Schur complement. After a permutation of coordinates, $M$ is congruent to the block diagonal matrix with blocks $M / M_{\mathcal K^c \mathcal K^c}$ and $M_{\mathcal K^c \mathcal K^c}$. Hence Sylvester's law of inertia \cite{horn2013matrix} and the multiplicativity of the determinant give
\begin{equation}\label{e:prelim-haynsworth}
n_-(M) = n_-(M_{\mathcal K^c \mathcal K^c}) + n_-(M / M_{\mathcal K^c \mathcal K^c}), \qquad \det M = \det M_{\mathcal K^c \mathcal K^c} \cdot \det(M / M_{\mathcal K^c \mathcal K^c}).
\end{equation}

The following lemma compares the eigenvalues of $\Lambda_0 + W$ near a group of eigenvalues of $\Lambda_0$ with those of the compression $(\Lambda_0 + W)_{\mathcal K \mathcal K}$, in order and with multiplicity. It is related to the quadratic residual bounds of \cite{mathias1998quadratic,li2005note}, and its proof is elementary.

\begin{lemma}\label{l:schur}
Let $\Lambda_0$ and $W$ be $N \times N$ Hermitian matrices, and let $\mathcal K \subset [N]$ be a nonempty proper subset such that $(\Lambda_0)_{\mathcal K \mathcal K^c} = 0$. Let $E_- \le E_+$ be real numbers such that every eigenvalue of $(\Lambda_0)_{\mathcal K \mathcal K}$ belongs to $[E_-, E_+]$, let $\vartheta > 0$, and set $\mathcal R = [E_- - \vartheta, E_+ + \vartheta]$. Suppose that $(\Lambda_0)_{\mathcal K^c \mathcal K^c} + W_{\mathcal K^c \mathcal K^c} - x$ is invertible for all $x \in \mathcal R$, and that there exists $\chi \ge 0$ such that
\begin{equation}\label{e:prelim-schur-hyp}
\big\| W_{\mathcal K \mathcal K^c} \big( (\Lambda_0)_{\mathcal K^c \mathcal K^c} + W_{\mathcal K^c \mathcal K^c} - x \big)^{-1} W_{\mathcal K^c \mathcal K} \big\| \le \chi \quad \text{for all } x \in \mathcal R, \qquad \|W_{\mathcal K \mathcal K}\| + \chi < \vartheta.
\end{equation}
Let $i_0$ denote the number of eigenvalues of $\Lambda_0 + W$ smaller than $E_- - \vartheta$, counted with multiplicity. Then the eigenvalues of $\Lambda_0 + W$ in $\mathcal R$, counted with multiplicity, are $\lambda_{i_0 + 1}(\Lambda_0 + W), \dots, \lambda_{i_0 + |\mathcal K|}(\Lambda_0 + W)$. Moreover,
\begin{equation}\label{e:prelim-schur-ordered}
\big| \lambda_{i_0 + i}(\Lambda_0 + W) - \lambda_i\big( (\Lambda_0 + W)_{\mathcal K \mathcal K} \big) \big| \le \chi \qquad \text{for all } i \in [|\mathcal K|],
\end{equation}
and these eigenvalues belong to $[E_- - \|W_{\mathcal K \mathcal K}\| - \chi, E_+ + \|W_{\mathcal K \mathcal K}\| + \chi]$.
\end{lemma}

\begin{proof}
We abbreviate $B = (\Lambda_0 + W)_{\mathcal K \mathcal K}$, and for $x \in \mathcal R$, we set
\begin{equation*}
\mathcal S(x) = W_{\mathcal K \mathcal K^c} \big( (\Lambda_0)_{\mathcal K^c \mathcal K^c} + W_{\mathcal K^c \mathcal K^c} - x \big)^{-1} W_{\mathcal K^c \mathcal K}, \qquad \mathcal F(x) = B - x - \mathcal S(x).
\end{equation*}
Observe that $\mathcal S(x)$ and $\mathcal F(x)$ are Hermitian, since $x$ is real and $W_{\mathcal K^c \mathcal K} = (W_{\mathcal K \mathcal K^c})^*$. As $(\Lambda_0)_{\mathcal K \mathcal K^c} = 0$, the matrix $M = \Lambda_0 + W - x$ satisfies $M_{\mathcal K \mathcal K^c} = W_{\mathcal K \mathcal K^c}$, and $\mathcal F(x)$ is its Schur complement. By \eqref{e:prelim-haynsworth}, we have
\begin{equation}\label{e:prelim-schur-count}
\begin{aligned}
\#\{ j \in [N] : \lambda_j(\Lambda_0 + W) < x \} &= n_-(\Lambda_0 + W - x) \\
&= n_-\big( (\Lambda_0)_{\mathcal K^c \mathcal K^c} + W_{\mathcal K^c \mathcal K^c} - x \big) + n_-(\mathcal F(x))
\end{aligned}
\end{equation}
for all $x \in \mathcal R$.

The matrix $(\Lambda_0)_{\mathcal K^c \mathcal K^c} + W_{\mathcal K^c \mathcal K^c}$ has no eigenvalue in the interval $\mathcal R$, so the first term on the right side of \eqref{e:prelim-schur-count} is constant on $\mathcal R$. We denote this constant by $i_1$.

We next compare $\mathcal F(x)$ with $B - x$. The bound $\|\mathcal S(x)\| \le \chi$ gives
\begin{equation*}
B - x - \chi \le \mathcal F(x) \le B - x + \chi
\end{equation*}
in the sense of quadratic forms. By the Courant--Fischer minimax principle \cite{horn2013matrix}, an inequality $A \le A'$ between Hermitian matrices implies $\lambda_i(A) \le \lambda_i(A')$ for all $i$, and hence $n_-(A) \ge n_-(A')$. Therefore
\begin{equation}\label{e:prelim-schur-sandwich}
\#\{ i : \lambda_i(B) < x - \chi \} \le n_-(\mathcal F(x)) \le \#\{ i : \lambda_i(B) < x + \chi \} \qquad \text{for all } x \in \mathcal R.
\end{equation}
Using Weyl's inequality \cite{horn2013matrix}, the assumption on the spectrum of $(\Lambda_0)_{\mathcal K \mathcal K}$, and \eqref{e:prelim-schur-hyp}, we see that every eigenvalue of $B$ satisfies
\begin{equation}\label{e:prelim-schur-B}
E_- - \vartheta + \chi < E_- - \|W_{\mathcal K \mathcal K}\| \le \lambda_i(B) \le E_+ + \|W_{\mathcal K \mathcal K}\| < E_+ + \vartheta - \chi.
\end{equation}

We now identify the eigenvalues of $\Lambda_0 + W$ in $\mathcal R$. Taking $x = E_- - \vartheta$, we see from \eqref{e:prelim-schur-B} that the right side of \eqref{e:prelim-schur-sandwich} vanishes, so \eqref{e:prelim-schur-count} gives $i_0 = i_1$. Taking $x = E_+ + \vartheta$ instead, we see that the left side of \eqref{e:prelim-schur-sandwich} is $|\mathcal K|$. As $\mathcal F(x)$ is a $|\mathcal K| \times |\mathcal K|$ matrix, this gives $n_-(\mathcal F(E_+ + \vartheta)) = |\mathcal K|$, and $\Lambda_0 + W$ has exactly $i_0 + |\mathcal K|$ eigenvalues smaller than $E_+ + \vartheta$. Moreover, \eqref{e:prelim-schur-B} gives
\begin{equation*}
\mathcal F(E_+ + \vartheta) \le B - E_+ - \vartheta + \chi < 0
\end{equation*}
in the sense of quadratic forms, so the determinant formula in \eqref{e:prelim-haynsworth} shows that $E_+ + \vartheta$ is not an eigenvalue of $\Lambda_0 + W$. Hence the eigenvalues of $\Lambda_0 + W$ in $\mathcal R$ are $\lambda_{i_0 + 1}(\Lambda_0 + W), \dots, \lambda_{i_0 + |\mathcal K|}(\Lambda_0 + W)$.

It remains to prove \eqref{e:prelim-schur-ordered}. For brevity, we write $\lambda_i' = \lambda_{i_0 + i}(\Lambda_0 + W)$ and $\lambda_i'' = \lambda_i(B)$ for $i \in [|\mathcal K|]$. For $x \in \mathcal R$, the eigenvalues of $\Lambda_0 + W$ smaller than $x$ are the $i_0$ eigenvalues smaller than $E_- - \vartheta$ and the $\lambda_i'$ with $\lambda_i' < x$. Inserting this into \eqref{e:prelim-schur-count} and using \eqref{e:prelim-schur-sandwich}, we find
\begin{equation}\label{e:prelim-schur-counting}
\#\{ i : \lambda_i'' < x - \chi \} \le \#\{ i : \lambda_i' < x \} \le \#\{ i : \lambda_i'' < x + \chi \} \qquad \text{for all } x \in \mathcal R.
\end{equation}

Fix $i \in [|\mathcal K|]$, and suppose that $\lambda_i' < \lambda_i'' - \chi$. Every $x \in (\lambda_i', \lambda_i'' - \chi)$ belongs to $\mathcal R$ by \eqref{e:prelim-schur-B}, since $\lambda_i' \ge E_- - \vartheta$. For such $x$, the middle term in \eqref{e:prelim-schur-counting} is at least $i$, since $\lambda_1' \le \dots \le \lambda_i' < x$, while the right term is smaller than $i$, since $x + \chi < \lambda_i'' \le \dots \le \lambda_{|\mathcal K|}''$. This contradicts \eqref{e:prelim-schur-counting}. If $\lambda_i' > \lambda_i'' + \chi$, then the same reasoning with $x \in (\lambda_i'' + \chi, \lambda_i')$ shows that the left term in \eqref{e:prelim-schur-counting} is at least $i$ and the middle term is smaller than $i$, again a contradiction. This proves \eqref{e:prelim-schur-ordered}, and the final statement follows from \eqref{e:prelim-schur-ordered} and \eqref{e:prelim-schur-B}.
\end{proof}

We now apply \zcref{l:schur} to a diagonal matrix with clustered entries. Let $y_1 \le \dots \le y_N$ be real numbers, and let $D_y = \diag(y_1, \dots, y_N)$. We call a partition $\mathfrak K$ of $[N]$ into nonempty sets of consecutive integers a \emph{family of clusters}, and we call its elements \emph{clusters}. For a cluster $\mathcal K$ and $\vartheta > 0$, we let
\begin{equation}\label{e:prelim-rectangle}
\mathcal R_{\mathcal K} = \Big\{ w \in \C : \min_{i \in \mathcal K} y_i - \vartheta \le \Re w \le \max_{i \in \mathcal K} y_i + \vartheta, \ |\Im w| \le \vartheta \Big\}
\end{equation}
denote the closed rectangle obtained by enlarging the interval $[\min_{i \in \mathcal K} y_i, \max_{i \in \mathcal K} y_i]$ by $\vartheta$ in each direction. We call $\vartheta$ the \emph{margin} of the rectangles.

\begin{lemma}\label{l:cluster}
Let $y_1 \le \dots \le y_N$ be real numbers, let $\mathfrak K$ be a family of clusters, and let $k_0 \ge 1$ be such that $|\mathcal K| \le k_0$ for all $\mathcal K \in \mathfrak K$. Let $\vartheta > 0$, and suppose that the rectangles $\mathcal R_{\mathcal K}$ with $\mathcal K \in \mathfrak K$ are pairwise disjoint and that there exists $\mathscr L \in [0, \infty)$ such that
\begin{equation}\label{e:prelim-cluster-harmonic}
\sup_{\mathcal K \in \mathfrak K} \sup_{w \in \mathcal R_{\mathcal K}} \sum_{j \in [N] \setminus \mathcal K} \frac{1}{|y_j - w|} \le \mathscr L,
\end{equation}
with the convention $1/0 = \infty$. Let $W$ be an $N \times N$ Hermitian matrix such that $\max_{i, j} |W_{ij}| \le w_0$, where
\begin{equation}\label{e:prelim-cluster-smallness}
w_0 \mathscr L \le 1/2, \qquad k_0 w_0 + 2 k_0 w_0^2 \mathscr L < \vartheta.
\end{equation}
Let $\mathcal K \in \mathfrak K$, and write $\mathcal K = \{ i_0 + 1, \dots, i_0 + |\mathcal K| \}$. Then the eigenvalues of $D_y + W$ in $\mathcal R_{\mathcal K}$, counted with multiplicity, are $\lambda_{i_0 + 1}(D_y + W), \dots, \lambda_{i_0 + |\mathcal K|}(D_y + W)$. Moreover,
\begin{equation}\label{e:prelim-cluster-ordered}
\big| \lambda_{i_0 + i}(D_y + W) - \lambda_i\big( (D_y + W)_{\mathcal K \mathcal K} \big) \big| \le 2 k_0 w_0^2 \mathscr L \qquad \text{for all } i \in [|\mathcal K|],
\end{equation}
and each of these eigenvalues is within distance $k_0 w_0 + 2 k_0 w_0^2 \mathscr L$ of the interval $[\min_{i \in \mathcal K} y_i, \max_{i \in \mathcal K} y_i]$.
\end{lemma}

Since $|y_j - w| \ge |y_j - \Re w|$, the supremum in \eqref{e:prelim-cluster-harmonic} may be taken over the real points of the rectangles, and since $D_y + W$ is Hermitian, its eigenvalues in $\mathcal R_{\mathcal K}$ are those in $\mathcal R_{\mathcal K} \cap \R$. In applications, the main condition to verify is \eqref{e:prelim-cluster-harmonic}, which requires that the points outside each cluster are not too dense near it.

\begin{proof}
Fix $\mathcal K \in \mathfrak K$, and set $E_- = \min_{i \in \mathcal K} y_i$ and $E_+ = \max_{i \in \mathcal K} y_i$. We first treat the case $\mathcal K = [N]$, in which $N \le k_0$. Bounding the operator norm by the Frobenius norm and using Weyl's inequality, we find
\begin{equation*}
|\lambda_i(D_y + W) - y_i| \le \|W\| \le N w_0 \le k_0 w_0 < \vartheta \qquad \text{for all } i \in [N],
\end{equation*}
and the lemma follows, since $(D_y + W)_{\mathcal K \mathcal K} = D_y + W$.

Now suppose that $\mathcal K^c$ is nonempty. We will apply \zcref{l:schur} with $\Lambda_0 = D_y$, $\chi = 2 k_0 w_0^2 \mathscr L$, and the interval
\begin{equation*}
\mathcal R = \mathcal R_{\mathcal K} \cap \R = [E_- - \vartheta, E_+ + \vartheta].
\end{equation*}
The matrix $D_y$ is diagonal, so $(D_y)_{\mathcal K \mathcal K^c} = 0$, and the eigenvalues of $(D_y)_{\mathcal K \mathcal K}$ are the $y_i$ with $i \in \mathcal K$, which belong to $[E_-, E_+]$.

We now check the invertibility hypothesis of \zcref{l:schur}. Fix $x \in \mathcal R$. The matrix $(D_y - x)_{\mathcal K^c \mathcal K^c}$ is diagonal with entries $y_j - x$, $j \in \mathcal K^c$. These entries are nonzero by \eqref{e:prelim-cluster-harmonic}, and
\begin{equation*}
\big\| W_{\mathcal K^c \mathcal K^c} (D_y - x)_{\mathcal K^c \mathcal K^c}^{-1} \big\|_{\infty \to \infty} = \max_{i \in \mathcal K^c} \sum_{j \in \mathcal K^c} \frac{|W_{ij}|}{|y_j - x|} \le w_0 \mathscr L \le \frac{1}{2}.
\end{equation*}

Hence the Neumann series shows that $\Id + W_{\mathcal K^c \mathcal K^c} (D_y - x)_{\mathcal K^c \mathcal K^c}^{-1}$ is invertible. We denote its inverse by $\Theta(x)$, and the Neumann series also gives $\|\Theta(x)\|_{\infty \to \infty} \le 2$. Using the factorization
\begin{equation*}
(D_y + W)_{\mathcal K^c \mathcal K^c} - x = \big( \Id + W_{\mathcal K^c \mathcal K^c} (D_y - x)_{\mathcal K^c \mathcal K^c}^{-1} \big) (D_y - x)_{\mathcal K^c \mathcal K^c},
\end{equation*}
we see that this matrix is invertible, and that
\begin{equation}\label{e:prelim-cluster-inverse}
\big( (D_y + W)_{\mathcal K^c \mathcal K^c} - x \big)^{-1} = (D_y - x)_{\mathcal K^c \mathcal K^c}^{-1} \, \Theta(x).
\end{equation}

We next bound the Schur remainder
\begin{equation*}
\mathcal S(x) = W_{\mathcal K \mathcal K^c} ((D_y + W)_{\mathcal K^c \mathcal K^c} - x)^{-1} W_{\mathcal K^c \mathcal K}
\end{equation*}
entrywise. Every entry of $W_{\mathcal K^c \mathcal K}$ is bounded by $w_0$, so
\begin{equation*}
\big| \big( \Theta(x) W_{\mathcal K^c \mathcal K} \big)_{j i'} \big| \le \|\Theta(x)\|_{\infty \to \infty} w_0 \le 2 w_0, \qquad j \in \mathcal K^c, \ i' \in \mathcal K.
\end{equation*}
By \eqref{e:prelim-cluster-inverse}, for $i, i' \in \mathcal K$ we have
\begin{equation*}
|\mathcal S(x)_{i i'}| = \Big| \sum_{j \in \mathcal K^c} \frac{W_{ij}}{y_j - x} \big( \Theta(x) W_{\mathcal K^c \mathcal K} \big)_{j i'} \Big| \le 2 w_0^2 \sum_{j \in \mathcal K^c} \frac{1}{|y_j - x|} \le 2 w_0^2 \mathscr L.
\end{equation*}

Bounding the operator norms by the Frobenius norms, we obtain
\begin{equation*}
\|\mathcal S(x)\| \le |\mathcal K| \cdot 2 w_0^2 \mathscr L \le \chi, \qquad \|W_{\mathcal K \mathcal K}\| \le |\mathcal K| w_0 \le k_0 w_0.
\end{equation*}
By \eqref{e:prelim-cluster-smallness}, we have $\|W_{\mathcal K \mathcal K}\| + \chi < \vartheta$, so the hypotheses of \zcref{l:schur} hold. It gives \eqref{e:prelim-cluster-ordered} and the location of the eigenvalues, with $i_0$ replaced by the number $i_0'$ of eigenvalues of $D_y + W$ smaller than $E_- - \vartheta$. Moreover, $\mathcal R_{\mathcal K} \cap \R$ contains exactly $|\mathcal K|$ eigenvalues of $D_y + W$.

It remains to show that $i_0' = i_0$. The preceding argument applies to every cluster $\mathcal K'$ with $(\mathcal K')^c$ nonempty, and the case $\mathcal K' = [N]$ was treated above, so each interval $\mathcal R_{\mathcal K'} \cap \R$ with $\mathcal K' \in \mathfrak K$ contains exactly $|\mathcal K'|$ eigenvalues of $D_y + W$.

Let $\mathcal K', \mathcal K'' \in \mathfrak K$ with $\max \mathcal K' < \min \mathcal K''$. Then $\max_{i \in \mathcal K'} y_i \le \min_{i \in \mathcal K''} y_i$, and since the two intervals are disjoint, every point of $\mathcal R_{\mathcal K'} \cap \R$ is smaller than every point of $\mathcal R_{\mathcal K''} \cap \R$. As the cluster sizes add up to $N$, every eigenvalue of $D_y + W$ belongs to one of these intervals. Therefore the eigenvalues smaller than $E_- - \vartheta$ are those in the intervals of the clusters $\mathcal K'$ with $\max \mathcal K' < \min \mathcal K$, and their number is $\min \mathcal K - 1 = i_0$. This completes the proof.
\end{proof}

In \zcref{s:pairs} and \zcref{s:hermitian}, the clusters are formed by joining consecutive points at distance smaller than a threshold, and the number of points in intervals of length $N^{-1}$ is controlled by condition (iii) of \zcref{d:regular}. (In \zcref{d:lin-clusters}, consecutive eigenvalues are joined when their distance is at most the threshold, while in \zcref{c:threshold} below, consecutive points are joined when their distance is less than the threshold. Each section uses one of the two conventions throughout, and \zcref{l:cluster} applies to both.) The next corollary records the parameters of \zcref{l:cluster} in this situation. \zcref[S]{f:prelim-clusters} illustrates its proof.

\begin{corollary}\label{c:threshold}
Let $N \ge 2$, $\eps > 0$, and $q > 0$ satisfy $2 N^\eps q < N^{-1}$. Let $y_1 \le \dots \le y_N$ be real numbers in $[-4, 4]$ such that $\#\{ i \in [N] : y_i \in [E, E + N^{-1}] \} \le N^\eps$ for all $E \in \R$. Let $\mathfrak K$ be the family of clusters whose elements are the maximal sets $\mathcal K$ of consecutive integers such that $y_{i + 1} - y_i < q$ for all $i$ with $i, i + 1 \in \mathcal K$. Then every $\mathcal K \in \mathfrak K$ satisfies $|\mathcal K| \le N^\eps$, and the hypotheses of \zcref{l:cluster} on $y$ and $\mathfrak K$ hold with
\begin{equation}\label{e:prelim-threshold-parameters}
k_0 = N^\eps, \qquad \vartheta = q/3, \qquad \mathscr L = 12 N^\eps (q^{-1} + N \log N).
\end{equation}
Let $W$ be an $N \times N$ Hermitian matrix with $\max_{i, j} |W_{ij}| \le w_0$, where
\begin{equation}\label{e:prelim-threshold-smallness}
N^\eps w_0 (q^{-1} + N \log N) \le 1/48.
\end{equation}
Then for every $\mathcal K = \{ i_0 + 1, \dots, i_0 + |\mathcal K| \} \in \mathfrak K$ and every $i \in [|\mathcal K|]$,
\begin{equation}\label{e:prelim-threshold-error}
\big| \lambda_{i_0 + i}(D_y + W) - \lambda_i\big( (D_y + W)_{\mathcal K \mathcal K} \big) \big| \le 24 N^{2\eps} w_0^2 (q^{-1} + N \log N),
\end{equation}
and $\min_{j \in \mathcal K} y_j - q/32 \le \lambda_{i_0 + i}(D_y + W) \le \max_{j \in \mathcal K} y_j + q/32$. In particular, if $i \in [N - 1]$ and $i$ and $i + 1$ belong to different clusters, then $\lambda_{i + 1}(D_y + W) - \lambda_i(D_y + W) \ge q/2$.
\end{corollary}

\begin{figure}[t]
\centering
\begin{tikzpicture}[x=1.05cm, y=1.05cm]
\foreach \a/\b in {0.5/1.5, 3.5/5.1, 6.7/8.8, 10.4/11.4} {
  \fill[gray!18] (\a, -0.5) rectangle (\b, 0.5);
  \draw[gray!70] (\a, -0.5) rectangle (\b, 0.5);
}
\draw[->] (-0.2, 0) -- (12.2, 0) node[right] {$\Re w$};
\foreach \x in {1.0, 4.0, 4.6, 7.2, 7.7, 8.3, 10.9} {
  \fill (\x, 0) circle (1.8pt);
}
\draw[decorate, decoration={brace, amplitude=4pt, mirror}] (4.6, -0.65) -- (7.2, -0.65) node[midway, below=5pt] {$\ge q$};
\draw[<->] (8.3, 0.7) -- (8.8, 0.7) node[midway, above] {$\vartheta$};
\draw[<->] (11.6, 0) -- (11.6, 0.5) node[midway, right] {$\vartheta$};
\node at (1.0, -0.8) {$\mathcal R_{\mathcal K}$};
\end{tikzpicture}
\caption{The points $y_i$ (dots), the clusters obtained with the threshold $q$, and the rectangles $\mathcal R_{\mathcal K}$ (shaded) with margin $\vartheta = q/3$, as in \zcref{c:threshold}. Consecutive points in different clusters are at distance at least $q$, so the rectangles are disjoint, and every point outside a cluster is at distance at least $2q/3$ from the rectangle of that cluster.}
\label{f:prelim-clusters}
\end{figure}

\begin{proof}
We first bound the size of the clusters. Let $\mathcal K = \{ i_0 + 1, \dots, i_0 + |\mathcal K| \} \in \mathfrak K$, and suppose that $|\mathcal K| > N^\eps$. Set $i_1 = i_0 + \lfloor N^\eps \rfloor + 1$, so that $i_1 \in \mathcal K$. Consecutive points in $\mathcal K$ are at distance smaller than $q$, so
\begin{equation*}
y_{i_1} - y_{i_0 + 1} < (i_1 - i_0 - 1) q \le N^\eps q < N^{-1}.
\end{equation*}
Thus the interval $[y_{i_0 + 1}, y_{i_0 + 1} + N^{-1}]$ contains the $\lfloor N^\eps \rfloor + 1 > N^\eps$ points $y_{i_0 + 1}, \dots, y_{i_1}$, which contradicts the assumption. Hence $|\mathcal K| \le N^\eps = k_0$.

We next bound the distances from a rectangle to the points outside its cluster. Let $\mathcal K \in \mathfrak K$, set $E_- = \min_{i \in \mathcal K} y_i$ and $E_+ = \max_{i \in \mathcal K} y_i$, and fix $j \notin \mathcal K$. By the definition of $\mathfrak K$, we have $y_{i + 1} - y_i \ge q$ whenever $i$ and $i + 1$ belong to different clusters. For $j < \min \mathcal K$, the labels $\min \mathcal K - 1$ and $\min \mathcal K$ belong to different clusters, and similarly for $j > \max \mathcal K$ and the labels $\max \mathcal K$ and $\max \mathcal K + 1$. Since $E_- = y_{\min \mathcal K}$ and $E_+ = y_{\max \mathcal K}$, we obtain
\begin{equation*}
y_j \le y_{\min \mathcal K - 1} \le E_- - q \quad (j < \min \mathcal K), \qquad y_j \ge y_{\max \mathcal K + 1} \ge E_+ + q \quad (j > \max \mathcal K).
\end{equation*}
Consequently, for every $w \in \mathcal R_{\mathcal K}$,
\begin{equation}\label{e:prelim-threshold-exterior}
|y_j - w| \ge |y_j - \Re w| \ge q - q/3 = 2q/3 \qquad \text{for all } j \notin \mathcal K.
\end{equation}

We next check that the rectangles are disjoint. Recall that $\vartheta = q/3$. Let $\mathcal K' \in \mathfrak K$ with $\min \mathcal K' > \max \mathcal K$. Then $\min_{i \in \mathcal K'} y_i \ge E_+ + q$, so every point of $\mathcal R_{\mathcal K'}$ has real part at least $E_+ + 2q/3$, while every point of $\mathcal R_{\mathcal K}$ has real part at most $E_+ + q/3$. Hence the rectangles are pairwise disjoint.

We now bound the harmonic sum. Fix $\mathcal K \in \mathfrak K$ and $w \in \mathcal R_{\mathcal K}$, and set $x = \Re w$. We have $|x| < 5$, since $|y_i| \le 4$ for all $i$ and $q < N^{-1} \le 1$, and therefore $|y_j - x| < 9$ for all $j$. For each integer $n \ge 0$, let
\begin{equation*}
\mathcal M_n = \{ j \in [N] \setminus \mathcal K : n/N \le |y_j - x| < (n + 1)/N \}.
\end{equation*}
The points $y_j$ with $j \in \mathcal M_n$ belong to the union of the two intervals $[x - (n + 1)/N, x - n/N]$ and $[x + n/N, x + (n + 1)/N]$ of length $N^{-1}$, so $|\mathcal M_n| \le 2 N^\eps$ by assumption.

The labels $j \in \mathcal M_0$ satisfy $|y_j - x| \ge 2q/3$ by \eqref{e:prelim-threshold-exterior}, and the labels $j \in \mathcal M_n$ with $n \ge 1$ satisfy $|y_j - x| \ge n/N$. Further, $\mathcal M_n$ is empty for $n \ge 9N$. Therefore
\begin{equation*}
\sum_{j \notin \mathcal K} \frac{1}{|y_j - w|} \le \sum_{n \ge 0} \sum_{j \in \mathcal M_n} \frac{1}{|y_j - x|} \le 2 N^\eps \cdot \frac{3}{2q} + \sum_{n = 1}^{9N} 2 N^\eps \cdot \frac{N}{n} \le \frac{3 N^\eps}{q} + 12 N^{1 + \eps} \log N \le \mathscr L.
\end{equation*}
In the third inequality, we used the bound
\begin{equation*}
\sum_{n = 1}^{9N} \frac{1}{n} \le 1 + \log(9N) \le 6 \log N \qquad (N \ge 2).
\end{equation*}
Hence the hypotheses of \zcref{l:cluster} on $y$ and $\mathfrak K$ hold with the parameters \eqref{e:prelim-threshold-parameters}.

We now verify \eqref{e:prelim-cluster-smallness}. By \eqref{e:prelim-threshold-parameters} and \eqref{e:prelim-threshold-smallness}, we have
\begin{equation*}
\begin{gathered}
w_0 \mathscr L = 12 N^\eps w_0 (q^{-1} + N \log N) \le \frac14, \qquad k_0 w_0 = q \cdot N^\eps w_0 q^{-1} \le \frac{q}{48}, \\
2 k_0 w_0^2 \mathscr L = 2 (k_0 w_0)(w_0 \mathscr L) \le \frac{q}{96},
\end{gathered}
\end{equation*}
and hence
\begin{equation*}
k_0 w_0 + 2 k_0 w_0^2 \mathscr L \le \frac{q}{32} < \vartheta.
\end{equation*}
Therefore \zcref{l:cluster} applies. By \eqref{e:prelim-threshold-parameters}, we have
\begin{equation*}
2 k_0 w_0^2 \mathscr L = 24 N^{2\eps} w_0^2 (q^{-1} + N \log N),
\end{equation*}
so the lemma gives \eqref{e:prelim-threshold-error} and the location of the eigenvalues within distance $q/32$ of $[\min_{j \in \mathcal K} y_j, \max_{j \in \mathcal K} y_j]$.

Finally, if $i$ and $i + 1$ belong to different clusters, then $y_{i + 1} - y_i \ge q$, and the location of the eigenvalues gives
\begin{equation*}
\lambda_{i + 1}(D_y + W) - \lambda_i(D_y + W) \ge (y_{i + 1} - q/32) - (y_i + q/32) \ge q - q/16 \ge q/2.
\end{equation*}
This completes the proof.
\end{proof}

\section{A Gaussian kernel estimate}\label{s:prelim-gaussian}

We will use the following functions throughout the paper. For every integer $p \ge 1$, we define $f_p \colon \R \to (0, 1]$ by
\begin{equation}\label{e:prelim-fp}
f_p(y) = (1 + y^2)^{-p}, \qquad y \in \R.
\end{equation}

In \zcref{s:pairs}, the gap of a $2 \times 2$ block of a matrix with a small Gaussian component is the norm of a Gaussian vector in $\R^2$ with nonzero mean. The following lemma computes the expectation of a function of this norm at a small scale $\delta$, for functions bounded in absolute value by $f_p$, uniformly in the mean and with an error that decays in the mean. The case $n = 3$ is used for Hermitian matrices in \zcref{s:hermitian}. For an integer $n \ge 1$ and $v > 0$, we let
\begin{equation}\label{e:prelim-gaussian-density}
\mathfrak g_v(z) = (2 \pi v)^{-n/2} \exp\big( - |z|^2/(2v) \big), \qquad z \in \R^n,
\end{equation}
denote the density of the centered Gaussian distribution on $\R^n$ with covariance $v \Id_n$; the dimension $n$ will be clear from the context.

\begin{lemma}\label{l:gaussian}
Let $n \in \{2, 3\}$, and let $p > (n + 1)/2$ be an integer. There exists $C > 0$, depending only on $n$ and $p$, such that the following holds. Let $x \ge 0$, $\varrho \in [1/2, 2]$, $v, v_0 \in [1/8, 8]$, and $\delta \in (0, 1]$, and let $\mathsf G_x$ be a Gaussian vector in $\R^n$ with mean $(\varrho x, 0) \in \R \times \R^{n - 1}$ and covariance $v \Id_n$. Then for every Borel function $f \colon [0, \infty) \to \R$ such that $|f| \le f_p$,
\begin{equation}\label{e:prelim-gaussian}
\Big| \delta^{-n} \E f(|\mathsf G_x|/\delta) - \mathfrak g_{v_0}(x, 0) \int_{\R^n} f(|y|) \dd y \Big| \le C f_p(x) \big( \delta + |\varrho - 1| + |v - v_0| \big).
\end{equation}
In particular, $\E f_p(|\mathsf G_x|/\delta) \le C \delta^n f_p(x)$.
\end{lemma}

\begin{proof}
Throughout the proof, $C$ denotes a constant that may depend on $n$ and $p$, and we write $\hat x = (x, 0)$, with $0 \in \R^{n - 1}$. We will use the bounds
\begin{equation}\label{e:prelim-gaussian-elementary}
\mathfrak g_v(\varrho \hat x) \le C e^{-x^2/64}, \qquad |\nabla \mathfrak g_v(z)| = \frac{|z|}{v} \mathfrak g_v(z) \le C e^{-|z|^2/32} \qquad (z \in \R^n),
\end{equation}
which hold for $\varrho \in [1/2, 2]$ and $v \in [1/8, 8]$, together with the fact that $e^{-c x^2} \le C_c f_p(x)$ for every $c > 0$. As $2p - 1 > n$, we also have
\begin{equation}\label{e:prelim-gaussian-integrals}
\int_{\R^n} f_p(|y|) \dd y + \int_{\R^n} |y| f_p(|y|) \dd y \le C.
\end{equation}
(The assumption $p > (n + 1)/2$, which is equivalent to $2p - n > 1$, is used here and again in the bound for the second term below.)

Recall that $\mathsf G_x$ has mean $\varrho \hat x$ and covariance $v \Id_n$, so that its density is $z \mapsto \mathfrak g_v(z - \varrho \hat x)$. Changing variables $z = \delta y$ in the integral defining $\E f(|\mathsf G_x|/\delta)$, we have
\begin{equation*}
\delta^{-n} \E f(|\mathsf G_x|/\delta) = \delta^{-n} \int_{\R^n} f(|z|/\delta) \, \mathfrak g_v(z - \varrho \hat x) \dd z = \int_{\R^n} f(|y|) \, \mathfrak g_v(\delta y - \varrho \hat x) \dd y.
\end{equation*}
Using $\mathfrak g_v(-\varrho \hat x) = \mathfrak g_v(\varrho \hat x)$ and $|f| \le f_p$, we find that the left side of \eqref{e:prelim-gaussian} is bounded by
\begin{equation}\label{e:prelim-gaussian-split}
\begin{aligned}
&\int_{|y| \le \delta^{-1}} f_p(|y|) \, \big| \mathfrak g_v(\delta y - \varrho \hat x) - \mathfrak g_v(-\varrho \hat x) \big| \dd y + \int_{|y| > \delta^{-1}} f_p(|y|) \big( \mathfrak g_v(\delta y - \varrho \hat x) + \mathfrak g_v(\varrho \hat x) \big) \dd y \\
&\qquad + \big| \mathfrak g_v(\varrho \hat x) - \mathfrak g_{v_0}(\hat x) \big| \int_{\R^n} f_p(|y|) \dd y.
\end{aligned}
\end{equation}
We bound the three terms in turn.

We begin with the first term. Let $|y| \le \delta^{-1}$, and let $[-\varrho \hat x, \delta y - \varrho \hat x]$ denote the segment between these two points. Every point $z'$ of this segment satisfies
\begin{equation*}
|z'| \ge \max(\varrho x - 1, 0) \ge \max(x/2 - 1, 0), \qquad \text{and hence} \qquad |z'|^2 \ge \frac{x^2}{8} - 1,
\end{equation*}
where we used $(a - b)^2 \ge a^2/2 - b^2$. By the mean value theorem and \eqref{e:prelim-gaussian-elementary},
\begin{equation*}
\big| \mathfrak g_v(\delta y - \varrho \hat x) - \mathfrak g_v(-\varrho \hat x) \big| \le \delta |y| \sup_{z' \in [-\varrho \hat x, \delta y - \varrho \hat x]} |\nabla \mathfrak g_v(z')| \le C \delta |y| e^{-x^2/256}.
\end{equation*}
Integrating against $f_p(|y|)$ and using \eqref{e:prelim-gaussian-integrals}, we find that the first term in \eqref{e:prelim-gaussian-split} is bounded by
\begin{equation*}
C \delta e^{-x^2/256} \int_{\R^n} |y| f_p(|y|) \dd y \le C \delta e^{-x^2/256} \le C \delta f_p(x).
\end{equation*}

The second term requires more care, since $\mathfrak g_v(\delta y - \varrho \hat x)$ is of order one when $\delta y$ is close to $\varrho \hat x$; there, the decay in $x$ comes from the factor $f_p(|y|)$. The part with $\mathfrak g_v(\varrho \hat x)$ is simpler. By \eqref{e:prelim-gaussian-elementary} and $f_p(|y|) \le |y|^{-2p}$, we have
\begin{equation*}
\mathfrak g_v(\varrho \hat x) \int_{|y| > \delta^{-1}} f_p(|y|) \dd y \le C e^{-x^2/64} \int_{|y| > \delta^{-1}} |y|^{-2p} \dd y \le C e^{-x^2/64} \delta^{2p - n} \le C \delta f_p(x),
\end{equation*}
where we used $2p - n > 1$ and $\delta \le 1$ in the last step. For the part with $\mathfrak g_v(\delta y - \varrho \hat x)$, we change variables back to $z = \delta y$ and use that
\begin{equation*}
f_p(|z|/\delta) \le (\delta/|z|)^{2p} \le 2^p \delta^{2p} (1 + |z|^2)^{-p} \qquad \text{for } |z| > 1.
\end{equation*}
This gives
\begin{equation*}
\begin{aligned}
\int_{|y| > \delta^{-1}} f_p(|y|) \, \mathfrak g_v(\delta y - \varrho \hat x) \dd y &= \delta^{-n} \int_{|z| > 1} f_p(|z|/\delta) \, \mathfrak g_v(z - \varrho \hat x) \dd z \\
&\le 2^p \delta^{2p - n} \int_{\R^n} \frac{\mathfrak g_v(z - \varrho \hat x)}{(1 + |z|^2)^p} \dd z.
\end{aligned}
\end{equation*}

To bound the last integral uniformly in $x$, we use the inequality
\begin{equation*}
1 + |a|^2 \le 1 + (|a - b| + |b|)^2 \le 2 (1 + |a - b|^2)(1 + |b|^2), \qquad a, b \in \R^n,
\end{equation*}
with $a = \varrho \hat x$ and $b = z$, together with $1 + \varrho^2 x^2 \ge (1 + x^2)/4$. We obtain
\begin{equation*}
(1 + |z|^2)^{-p} \le 2^p (1 + |z - \varrho \hat x|^2)^p (1 + \varrho^2 x^2)^{-p} \le 8^p (1 + |z - \varrho \hat x|^2)^p f_p(x),
\end{equation*}
and therefore
\begin{equation*}
\int_{\R^n} \frac{\mathfrak g_v(z - \varrho \hat x)}{(1 + |z|^2)^p} \dd z \le 8^p f_p(x) \int_{\R^n} (1 + |z'|^2)^p \, \mathfrak g_v(z') \dd z' \le C f_p(x).
\end{equation*}
Using $\delta^{2p - n} \le \delta$, we conclude that the second term in \eqref{e:prelim-gaussian-split} is bounded by $C \delta f_p(x)$.

Next, we bound the third term. We consider
\begin{equation*}
\mathfrak g_{v'}(\varrho' \hat x) = (2 \pi v')^{-n/2} \exp\Big( - \frac{\varrho'^2 x^2}{2 v'} \Big)
\end{equation*}
as a function of $(\varrho', v')$ in the rectangle $[1/2, 2] \times [1/8, 8]$, with partial derivatives
\begin{equation*}
\partial_{\varrho'} \mathfrak g_{v'}(\varrho' \hat x) = - \frac{\varrho' x^2}{v'} \mathfrak g_{v'}(\varrho' \hat x), \qquad \partial_{v'} \mathfrak g_{v'}(\varrho' \hat x) = \Big( - \frac{n}{2 v'} + \frac{\varrho'^2 x^2}{2 v'^2} \Big) \mathfrak g_{v'}(\varrho' \hat x).
\end{equation*}
Using \eqref{e:prelim-gaussian-elementary}, we see that on this rectangle
\begin{equation*}
|\partial_{\varrho'} \mathfrak g_{v'}(\varrho' \hat x)| + |\partial_{v'} \mathfrak g_{v'}(\varrho' \hat x)| \le C (1 + x^2) e^{-x^2/64} \le C f_p(x).
\end{equation*}
The rectangle is convex, so the mean value theorem along the segment from $(1, v_0)$ to $(\varrho, v)$ gives
\begin{equation*}
\big| \mathfrak g_v(\varrho \hat x) - \mathfrak g_{v_0}(\hat x) \big| \le C f_p(x) \big( |\varrho - 1| + |v - v_0| \big).
\end{equation*}
By \eqref{e:prelim-gaussian-integrals}, the third term in \eqref{e:prelim-gaussian-split} is therefore bounded by $C f_p(x)(|\varrho - 1| + |v - v_0|)$.

Combining the bounds for the three terms in \eqref{e:prelim-gaussian-split}, we obtain \eqref{e:prelim-gaussian}. For the final claim, we apply \eqref{e:prelim-gaussian} with $f = f_p$, and we obtain
\begin{equation*}
\delta^{-n} \E f_p(|\mathsf G_x|/\delta) \le \mathfrak g_{v_0}(\hat x) \int_{\R^n} f_p(|y|) \dd y + C f_p(x) \big( \delta + |\varrho - 1| + |v - v_0| \big) \le C f_p(x).
\end{equation*}
In the last step, we used \eqref{e:prelim-gaussian-integrals}, the bound $\mathfrak g_{v_0}(\hat x) \le C f_p(x)$, which holds as $v_0 \in [1/8, 8]$, and $\delta + |\varrho - 1| + |v - v_0| \le 10$.
\end{proof}