# Small ball probability for multiple singular values of symmetric random
matrices

Yi HAN  Department of Pure Mathematics and Mathematical Statistics, University
of Cambridge<EMAIL_ADDRESS>
###### Abstract.

Let $A_{n}$ be an $n\times n$ random symmetric matrix with $(A_{ij})_{i<j}$
i.i.d. mean $0$, variance 1, following a subGaussian distribution and diagonal
elements i.i.d. following a subGaussian distribution with a fixed variance. We
investigate the joint small ball probability that $A_{n}$ has eigenvalues near
two fixed locations $\lambda_{1}$ and $\lambda_{2}$, where $\lambda_{1}$ and
$\lambda_{2}$ are sufficiently separated and in the bulk of the semicircle
law. More precisely we prove that for a wide class of entry distributions of
$A_{ij}$ that involve all Gaussian convolutions (where $\sigma_{min}(\cdot)$
denotes the least singular value of a square matrix),

$\mathbb{P}(\sigma_{min}(A_{n}-\lambda_{1}I_{n})\leq\delta_{1}n^{-1/2},\sigma_{min}(A_{n}-\lambda_{2}I_{n})\leq\delta_{2}n^{-1/2})\leq
c\delta_{1}\delta_{2}+e^{-cn}.$

The given estimate approximately factorizes as the product of the estimates
for the two individual events, which is an indication of quantitative
independence. The estimate readily generalizes to $d$ distinct locations. As
an application, we upper bound the probability that there exist $d$
eigenvalues of $A_{n}$ asymptotically satisfying any fixed linear equation,
which in particular gives a lower bound of the distance to this linear
relation from any possible eigenvalue pair that holds with probability
$1-o(1)$, and rules out the existence of two equal singular values in generic
regions of the spectrum.

Supported by EPSRC grant EP/W524141/1.

##  1\. Introduction

Let $A_{n}$ be an $n\times n$ symmetric random matrix with entries above the
diagonal $(A_{i,j})_{i<j}$ being identically distributed and having mean $0$
and variance $1$, and diagonal entries having a fixed variance. Wigner proved
in his seminal work [40] in the 1950s that the eigenvalue distribution of
$A_{n}$ converges to the semicircle law on the real line.

In this work we investigate the following question: given two real numbers
$\lambda_{1}\neq\lambda_{2}$ in the bulk of the semicircle law, what can be
said about the dependence between the following two events: (a) $A_{n}$ has an
eigenvalue near $\lambda_{1}$; and (b) $A_{n}$ has an eigenvalue near
$\lambda_{2}$? As the spectra of $A_{n}$ at different locations are
correlated, one cannot argue from elementary probability theory that the
events (a) and (b) are asymptotically independent in some quantitative sense.

This question is related to the study of asymptotic independence in spatial
point processes, especially determinantal point process (DPP). The GUE matrix
ensemble and complex Ginibre ensemble are both determinantal point processes,
and GOE matrices have instead a Pfaffian structure; see for example [1]. For
DPPs, the fact that a positive definite matrix satisfies the Hadamard–Fischer
inequality can be used to show that its $k$-fold correlation function
approximately factorizes as the product of each individual factor when we take
the limit, which is used in [2] for the study of smallest gap of GUE. This
fact is a strong indication of asymptotic independence, though restricted to
DPPs and the GUE matrix. From the perspective of universality in random matrix
theory, we should expect that the events (a) and (b) are approximately
independent, in a certain quantitative sense, for a general class of Wigner
matrices $A_{n}$ without a determinantal point process structure and do not
match to fourth moments with the GUE. Another related notion is negative
dependence in determinantal point processes, see for example the works [29],
[24], [17], [3].

Another closely related topic concerns the log correlated structure in Wigner
matrices. This log correlated structure can be derived in the large $n$ limit
for the log determinant [33] [6] and the log characteristic polynomial [4]
[7]. Owing to this structure, we can explicitly compute the correlation of the
log characteristic functions and eigenvalue fluctuations at two different
locations $\lambda_{1},\lambda_{2}$. The limiting covariance of observable at
these two locations is less than one when $\lambda_{1}$ and $\lambda_{2}$ are
distant at mesoscopic scales, and is zero when they are distant at macroscopic
scales, see [25]. Therefore we should expect that the events (a) and (b) are
approximately independent in a very strong sense, modulo numerical constants.

In this work we derive quantitative, non-asymptotic estimates to highlight the
asymptotic independence of (a) and (b), for $A_{n}$ having a wide class of
entry distributions (and therefore not assuming a DPP structure and not
assuming $A_{n}$ is invariant under orthogonal or unitary transform). More
precisely, we prove that when the entry distribution of $A_{ij}$ is
subGaussian and has a small (but non-vanishing) Gaussian component, and when
$|\lambda_{1}-\lambda_{2}|\geq\Delta\sqrt{n}$ and both lie in the bulk
$[-(2-\kappa)\sqrt{n},(2-\kappa)\sqrt{n}]$ for any $\Delta,\kappa>0$, then

$\mathbb{P}(\sigma_{min}(A_{n}-\lambda_{1}I_{n})\leq\delta_{1}n^{-1/2},\sigma_{min}(A_{n}-\lambda_{2}I_{n})\leq\delta_{2}n^{-1/2})\leq
c\delta_{1}\delta_{2}+e^{-cn}$ (1.1)

for any $\delta_{1},\delta_{2}>0$, where $c$ is a fixed constant. Here for any
square matrix $M$ we use the notation $\sigma_{min}(M)$ to denote the smallest
singular value of $M$. We will further prove this result for $d$ locations
$\lambda_{1},\cdots,\lambda_{d}$ for any $d$, and a similar result for
$\lambda_{1},\lambda_{2}$ with distance $|\lambda_{1}-\lambda_{2}|\geq\Delta
n^{-\frac{1}{2}+\sigma}$ and any $\sigma\in(0,1]$. Moreover, we do not use the
explicit density function of Gaussian distribution (but only use its Fourier
decay) so that our assumption covers many other distributions.

The main estimate (1.1) of this paper is a multilocation generalization of the
main result in Campos, Jenssen, Michelen and Sahasrabudhe [10] which proves
that, for any symmetric random matrix $A_{n}$ with subGaussian entries, we
have for any $\epsilon>0$,

$\mathbb{P}(\sigma_{min}(A_{n})\leq\epsilon n^{-1/2})\leq c\epsilon+e^{-cn}.$
(1.2)

It is not hard to check that the same estimate holds for
$\sigma_{min}(A_{n}-\lambda_{i}I_{n})$ for any $\lambda_{i}$ in the bulk of
the semicircle law, so one can interpret (1.1) as an approximate independence
property thanks to (1.2). Estimate (1.2) was previously proven fir $c=1$ and
$\epsilon\geq n^{-d}$ for some sufficiently small $d>0$ via fixed energy
universality results and comparison to the GOE matrix, obtaining the correct
dependence in $\epsilon$, see [8] and also [35] where a moment matching
condition was imposed.

To the best of our knowledge, the simultaneous small ball probability estimate
for several distinct singular values (1.1) is quite new in the literature.
Similar results do not exist even for random matrices with i.i.d. entries
where it is usually simpler, though still very challenging, to derive least
singular value estimates; see [32], [22], [36].

We briefly elaborate how our estimate (1.1) compares to the log correlated
structure interpretation. In (1.1) the numerical constants are not explicitly
computed; thus the covariance is not computed and we can say only that the two
events are approximately independent. The advantage is that we can consider
the event where $A_{n}$ has an eigenvalue in an $\epsilon$-neighborhood of
$\lambda_{1}$ for any $\epsilon>e^{-cn}$, which is much smaller than the
typical eigenvalue spacing $n^{-1/2}$. Additionally, our estimate holds with
probability $1-e^{-\Omega(n)}$. These two advantages appear to be inaccessible
from the log correlated field structure in [7], [25]. The estimate we prove
here mostly relies on the anti-concentration property of random matrix entries
rather than comparison to the GOE matrix, and it appears that our results are
new for the GOE matrix as well. Allowing $\epsilon$ to be much smaller than
$n^{-1/2}$ is of primary importance to our application, as this permits us to
take an $\epsilon$ net and deduce that the possibility that some $d$
eigenvalues of $A_{n}$ satisfy any fixed linear structure is exponentially
small (Theorem 1.7).

###  1.1. Statement of main estimates

Now we state the standing assumptions and the main estimates of our paper.
Although some conditions listed as follows seem technical, the reader can
simply take $A_{ij}$ to be any subGaussian random variable having a
nonvanishing Gaussian component; under this assumption all the results of this
paper hold.

Recall that for a random variable $\zeta$ with mean 0 and variance one, we
define its subGaussian moment via

$\|\zeta\|_{\psi_{2}}:=\sup_{p\geq
1}p^{-1/2}(\mathbb{E}|\zeta|^{p})^{\frac{1}{p}}.$

For any $B>0$, let $\Gamma_{B}$ denote the set of random variables $\xi$ with
mean 0, variance one that satisfies $\|\xi\|_{\psi_{2}}\leq B$.

######  Definition 1.1.

Fix a parameter $\sigma_{0}\in(0,1)$ throughout the paper, and fix three real
numbers $G>0,$ $K>0$, $B>0$.

Let $\Gamma_{1}(G,B,\sigma_{0})$ denote the collection of mean zero real
random variables $\zeta_{1}$ with variance $\sigma$, which also satisfies a
subGaussian estimate $\|\sigma_{0}^{-1/2}\zeta_{1}\|_{\psi_{2}}\leq G$ and
also satisfies the following Fourier decay estimate:

$|\mathbb{E}e^{2\pi i\theta\xi_{1}}|\leq\exp(-B|\theta|^{2}),\quad\text{ for
all }\theta\in\mathbb{R}.$ (1.3)

Let $\Gamma_{2}(G,K,\sigma_{0})$ denote the collection of mean zero real
random variables $\zeta_{2}$ with variance $1-\sigma_{0}$, which also
satisfies sub-Gaussian estimate
$\|(1-\sigma_{0})^{-1/2}\zeta_{2}\|_{\psi_{2}}\leq G$, and have a bounded
density function $\mu_{\zeta_{2}}(x)$ with respect to the Lebesgue measure
that satisfies

$|\mu_{\zeta_{2}}(x)|\leq K,\quad\text{ for all }x\in\mathbb{R}.$ (1.4)

The main result of this paper is the following estimate:

######  Theorem 1.2.

Fix some positive constants $G,K,B$ and $\sigma_{0}\in(0,1)$. Consider two
random variables $\zeta_{1}\in\Gamma_{1}(G,B,\sigma_{0})$ and
$\zeta_{2}\in(G,K,\sigma_{0})$, such that $\zeta_{1}$ and $\zeta_{2}$ are
independent. Moreover, assume that

$(\mathbf{LSI})$ The random variable $\zeta_{1}+\zeta_{2}$ satisfies a
logarithmic Sobolev inequality with the log Sobolev constant finite and
independent of $n$.

Let $A_{n}$ be an $n\times n$ symmetric random matrix with upper-diagonal
$\\{A_{i,j}\\}_{1\leq i<j\leq n}$ being independent and identically
distributed, having distribution $\zeta_{1}+\zeta_{2}$.

Additionally, assume that the diagonal entries $(A_{ii})_{1\leq i\leq n}$ are
i.i.d. having distribution $\bar{\sigma}(\zeta_{1}+\zeta_{2})$ for some
$\bar{\sigma_{0}}>0$, and independent of $\\{A_{i,j}\\}_{1\leq i<j\leq n}$.

Consider any fixed $\kappa>0$, $\Delta>0$ and $d\in\mathbb{N}_{+}$, and
consider any fixed locations
$\lambda_{1},\cdots,\lambda_{d}\in[(-(2-\kappa)\sqrt{n},(2-\kappa)\sqrt{n}]$
such that $|\lambda_{i}-\lambda_{j}|\geq\Delta n^{1/2}$ for any $i\neq
j\in\\{1,\cdots,d\\}$. Then there exists $c>0$ depending on
$G,K,B,\sigma_{0},\bar{\sigma}_{0},\Delta,\kappa$ such that for any
$\delta_{1},\cdots,\delta_{d}\geq 0$,

$\mathbb{P}\left(\sigma_{min}(A_{n}-\lambda_{i}I_{n})\leq\delta_{i}n^{-1/2},\quad\text{
for all }i=1,\cdots,d\right)\leq c\prod_{i=1}^{d}\delta_{i}+e^{-cn}.$ (1.5)

Informally, this theorem implies that the eigenvalues of $A_{n}$ satisfy
strong asymptotic independence properties and is, to some extent, similar to a
Poisson point process.

######  Example 1.3.

(Gaussian divisible ensemble) A class of symmetric random matrices that
satisfy the assumptions in Theorem 1.2 are matrices with a Gaussian component,
including in particular the GOE matrix. That is, we take $\zeta_{1}$ to be a
Gaussian random variable with mean $0$ and variance $\sigma_{0}$, and
$\zeta_{2}$ any mean $0$ subGaussian random variable with variance
$1-\sigma_{0}$. By properties of Gaussian distributions, $\zeta_{1}+\zeta_{2}$
has the same distribution as the independent sum of a $N(0,\sigma_{0}/2)$
random variable and another mean $0$ random variable with bounded density and
variance $1-\sigma_{0}/2$. The $\mathbf{(LSI)}$ condition is also satisfied:
indeed, by [11], Theorem 2, the convolution of a subGaussian random variable
with a Gaussian variable always satisfies the log Sobolev inequality. Thus
Theorem 1.2 covers all subGaussian random matrices with a small Gaussian
perturbation. To the best of our knowledge, Theorem 1.2 is new for the GOE
matrix as well.

######  Remark 1.4.

Theorem 1.2 can be generalized without much difficulty to generalized Wigner
matrices (see [13]) where each entry $A_{ij}$ has different variance
$\frac{\sigma_{ij}}{n}$, and $C_{1}\leq\sigma_{ij}\leq C_{2}$ for some
$C_{1},C_{2}>0$. This is because we assume a continuous distribution, and the
place where this assumption is used does not strictly require i.i.d. entries.
For discrete entries, the use of Littlewood-Offord type arguments generally
requires i.i.d. entries, but see [22] for a non-i.i.d. extension.

We also formulate a variant of Theorem 1.2 that considers locations
$\lambda_{i}$’s that are distant only on mesoscopic scales.

######  Theorem 1.5.

(Mesoscopic distance) Fix some positive constants $G,K,B$ and
$\sigma_{0}\in(0,1)$. Consider two random variables
$\zeta_{1}\in\Gamma_{1}(G,B,\sigma_{0})$ and $\zeta_{2}\in(G,K,\sigma_{0})$,
such that $\zeta_{1}$ and $\zeta_{2}$ are independent.

Let $A_{n}$ be an $n\times n$ symmetric random matrix with
$\\{A_{i,j}\\}_{1\leq i<j\leq n}$ being independent and identically
distributed, with the distribution $\zeta_{1}+\zeta_{2}$.

Additionally assume that the diagonal entries $(A_{ii})_{1\leq i\leq n}$ are
i.i.d. with the distribution $\bar{\sigma_{0}}(\zeta_{1}+\zeta_{2})$ for some
$\bar{\sigma_{0}}>0$, and independent of $\\{A_{i,j}\\}_{1\leq i<j\leq n}$.

Fix some $\sigma\in(0,1)$. Consider any fixed $\kappa>0$, $\Delta>0$ and
$d\in\mathbb{N}_{+}$, and consider any fixed locations
$\lambda_{1},\cdots,\lambda_{d}\in[(-(2-\kappa)\sqrt{n},(2-\kappa)\sqrt{n}]$
such that $|\lambda_{i}-\lambda_{j}|\geq\Delta n^{\sigma-1/2}$ for any $i\neq
j\in\\{1,\cdots,d\\}$. Then there exists $c>0$ depending on
$G,K,B,\sigma_{0},\bar{\sigma}_{0},\sigma,\Delta,\kappa$ such that for any
$\delta_{1},\cdots,\delta_{d}\geq 0$,

$\mathbb{P}\left(\sigma_{min}(A_{n}-\lambda_{i}I_{n})\leq\delta_{i}n^{-1/2},\quad\text{
for all }i=1,\cdots,d\right)\leq
c\prod_{i=1}^{d}\delta_{i}+e^{-cn^{\sigma/2}}.$ (1.6)

In light of the log correlated structure of Wigner matrices (see for example
[25]), the distance $|\lambda_{i}-\lambda_{j}|\geq n^{\sigma-1/2}$ for any
$\sigma>0$ is almost the shortest distance at which we can prove approximate
independence without too much difficulty. At scale $n^{-1/2}$ or on some even
smaller scales, we believe the bounds in Theorem 1.2 and 1.5 still hold true,
but this range is not accessible by the techniques presented in this paper.

###  1.2. Applications of the main estimate: anticoncentration and equal
singular values

We now discuss an application of the main estimate. In Conjecture 8.5 of the
survey article [39], Vu posed the following question:

######  Conjecture 1.6.

let $M_{n}^{sym}$ be a symmetric random matrix, whose entry distributions are
Rademacher variables. Prove that with probability $1-o(1)$, all the singular
values of $M_{n}^{sym}$ are distinct.

This conjecture is equivalent to proving that there does not exist any two
eigenvalues of $M_{n}^{sym}$ that sum up to zero, as singular values of
$M_{n}^{sym}$ are the absolute values of eigenvalues of $M_{n}^{sym}$. To the
best of our knowledge, this conjecture remains open up to now.

This conjecture shares some formal similarity to a related problem: proving
that $M_{n}^{sym}$ has distinct eigenvalues with probability $1-o(1)$. Much
more progress has been made in solving the latter problem: it was positively
solved in [34], and then in [10] the authors provided an exponential bound
$1-e^{-cn}$ for subGaussian entries. (The analogous problem for i.i.d. random
matrices has also been solved, see [16] and [23]). The difference between
these two problems is as follows: the problem of distinct eigenvalues only
requires singular value estimates at one location, whereas Conjecture (1.6)
requires singular value estimates at different locations.

We prove the following theorem, which considers a much more general problem
than that posed in Conjecture (1.6).

######  Theorem 1.7.

Let $A_{n}$ be an $n\times n$ symmetric random matrix satisfying the
assumptions of Theorem 1.2. Fix any $\kappa>0$, $d>0$ and $\Delta>0$.

We say that the eigenvalues $x_{1},\cdots,x_{d}$ are distant if
$|x_{i}-x_{j}|\geq\Delta n^{1/2}$ for any $i\neq j$. Let
$I_{\kappa}:=[-(2-\kappa)\sqrt{n},(2-\kappa)\sqrt{n}]$. Then for any
$a_{1},\cdots,a_{d}\in\mathbb{R}$ and $c\in\mathbb{R}$, and any
$\epsilon>0$,111In this paper we use the symbol $a\lesssim b$ to mean that
$a\leq Cb$ for some constant $C$ that depends only on the density of matrix
entries of $A_{n}$ and other given parameters $d$, $\sigma$ and $\Delta$.

$\displaystyle\mathbb{P}(A_{n}\text{ has }d\text{ distant eigenvalues
}x_{1},\cdots,x_{d}\in I_{\kappa}\text{ satisfying
}|\sum_{i=1}^{d}a_{i}x_{i}-c|\leq\epsilon)$ (1.7) $\displaystyle\lesssim
n^{(2d-1)/2}\epsilon+e^{-\Omega(n)}.$

More generally, for any $\sigma\in(0,1)$, we say that the eigenvalues
$x_{1},\cdots,x_{d}$ are $\sigma$-distant if $|x_{i}-x_{j}|\geq\Delta
n^{\sigma-\frac{1}{2}}$ for any $j\neq i$. Then for any
$a_{1},\cdots,a_{d}\in\mathbb{R}$ and $c\in\mathbb{R}$, and any $\epsilon>0$,

$\displaystyle\mathbb{P}(A_{n}\text{ has }d\quad\sigma-\text{distant
eigenvalues }x_{1},\cdots,x_{d}\in I_{\kappa}\text{ satisfying
}|\sum_{i=1}^{d}a_{i}x_{i}-c|\leq\epsilon)$ (1.8) $\displaystyle\lesssim
n^{(2d-1)/2}\epsilon+e^{-\Omega(n^{\sigma/2})}.$

This theorem implies that the minimal value attained in the quantity
$|\sum_{i=1}^{d}a_{i}x_{i}-c|$ where $x_{1},\cdots,x_{d}$ range from distant
bulk eigenvalues of $A_{n}$, is typically at least $n^{-(2d-1)/2}$ with
probability $1-o(1)$. In the case $d=2$, this distance is consistent with the
fact that the minimal gap in a Poisson distribution on $[0,1]$ with $n$
particles is typically $n^{-2}$.

###### Proof of Theorem 1.7.

Consider the first claim. Let $\epsilon>0$ and consider the question of
bounding $|\sum_{i=1}^{d}a_{i}x_{i}-c|\leq\epsilon$. We find an $\epsilon$ net
of $I_{\kappa}$ and choose any $d-1$ points $p_{1},\cdots,p_{d-1}$ from this
net. Then there are only finitely many points $p_{d}$ in this net such that
$|\sum_{i=1}^{d}a_{i}p_{i}-c|\leq C\epsilon$ for some very large $C>0$. Then
the possibility that $A_{n}$ has $d$ distant eigenvalues in $I_{\kappa}$
satisfying the assumption is upper bounded by

$C(\frac{2\sqrt{n}}{\epsilon})^{d-1}(\epsilon^{d}n^{d/2}+e^{-\Omega(n)})$

where the first factor is the number of all possible choice of
$p_{1},\cdots,p_{d-1}$ from the net and the second term comes from

$\mathbb{P}(\sigma_{min}(A_{n}-p_{i}I_{n})\leq\epsilon,i=1,\cdots,d)\lesssim\epsilon^{d}n^{d/2}+e^{-cn}.$

As we only consider distant eigenvalues, we can assume that
$|p_{i}-p_{j}|\geq\Delta$ for any $i\neq j$. Then applying Theorem 1.2
completes the proof. For the second claim, it suffices to use Theorem 1.5
instead. ∎

Compared to Conjecture 1.6, we have shown that Conjecture 1.6 holds with
possibility $1-e^{-\Omega(n)}$ for singular values in
$[\kappa\sqrt{n},(2-\kappa)\sqrt{n}]$ (and any $\kappa>0$) and for any entry
distribution specified in Theorem 1.2. To the best of our knowledge, Theorem
1.7 is the first time that we can estimate the probability that the
eigenvalues of $A_{n}$ may approximately satisfy any fixed linear or nonlinear
structure; moreover this theorem is new even for the GOE matrix, and all prior
results consider only eigenvalue gap or eigenvalue overcrowding estimates, see
[28], [26], [15] and [5], and these works correspond to the special case
$x_{1}-x_{2}=0$ of Theorem 1.7. That is, we are now able to estimate the long-
range dependence between eigenvalues and prove they are asymptotically
independent, at the precision of small ball probability bounds.

Prior to this work, there appear to be very few papers investigating the
independence, or anti-concentration property of the spectrum of a quantum
system, beyond exactly integrable models such as the GUE matrix. In this work
we rigorously justify the anti-concentration and approximate independence
properties of the spectrum of a wide family of Wigner matrices. We hope this
will initiate a new direction of research.

In Theorems 1.2, 1.5 and 1.7, we have assumed the locations
$\lambda_{1},\cdots,\lambda_{d}$ are separated by some distance
$n^{\sigma-1/2}$. We believe that the same estimate should also work if such a
distance separation assumption is removed. When some $\lambda_{i}^{\prime}s$
are very close to each other, the eigenvalue repulsion phenomena dominates so
the minimal eigenvalue gap is larger than that in a Poisson point process (see
[15] and [2]) while the bound in Theorem 1.7 does not take into account this
repulsion effect. Under our assumption that $\lambda_{i}$’s are distant,
however, we believe the estimate in Theorem 1.7 is sharp modulo constants.

Given the strength of Theorem 1.7, there is still much to do before our
theorem can be turned to a solution to Conjecture 1.6. First, we have made
additional density assumptions on matrix entries, excluding the Rademacher
variables; second, we only work with eigenvalues in the bulk $I_{\kappa}$; and
third, the estimate breaks down when eigenvalues are very close: in the
context of Conjecture 1.6 this accounts for the region where two eigenvalues
in $[-\epsilon,\epsilon]$ sum up to zero for $\epsilon\sim n^{-1/2}$. A
different treatment is needed in this region, and we leave this topic for
future work.

We should also mention that the phenomena revealed in Theorem 1.7 apply to far
more general nonlinear relations than the one stated here. Although Theorem
1.7 is stated for linear relations only, it will be clear from the proof that
the same result holds for a wide variety of nonlinear relations on $d$
variables. Namely, consider a function $F(x_{1},\cdots,x_{d})$ which is
Lipschitz continuous in $x_{1},\cdots,x_{d-1}$, that for any
$x_{1},\cdots,x_{d-1}$ there are only finitely many $x_{d}$ such that
$F(x_{1},\cdots,x_{d})=0$ (we denote the collection of such points as
$Z_{x_{1},\cdots,x_{d-1}}$), and for a fixed $x_{1},\cdots,x_{d-1}$,
$|F(x_{1},\cdots,x_{d})|\leq\epsilon\implies\operatorname{dist}(x_{d},Z_{x_{1},\cdots,x_{d-1}})\leq
C\epsilon$. Then the conclusion of Theorem 1.7 holds for any such function $F$
as well, with identical proofs.

###  1.3. Proof techniques and major challenges

The main result Theorem 1.2 of this paper is a multilocation generalization of
the singular value estimate in [10], which is the culmination of many prior
works on the singularity of symmetric random matrices, see [12], [27], [20],
[38], [9].

From a broad perspective, we follow Rudelson and Vershynin’s geometric method
of invertibility, see [32]. However, this seems to be the first time that the
method has been generalized to multiple matrices. Recall that in the approach
of [32], we first show that the matrix is well invertible on the set of
compressible vectors via a net argument. Since incompressible vectors have at
least $\rho n$ coordinates with an absolute value of at least $cn^{-1/2}$, we
can reduce the singular value lower bound to bounding the possibility that one
column of this matrix is very close to the linear span of the other columns.

Now we have several matrices and would like to derive joint lower tail
estimates for singular values. We may still heuristically expect the above
reasoning to hold, so that we bound the possibility that a fixed column of
each matrix is very close to the linear span of the other columns of the same
matrix. However, there is a flaw: each incompressible vector has only $\rho n$
coordinates that are not too small, and if we take two such vectors, their
location of large coordinates may not even intersect if $\rho$ is small.

Fortunately, this flaw can be resolved by the following fact: the minimal
singular values of $A_{n}$ are achieved by the eigenvectors of $A_{n}$, and
the eigenvectors of $A_{n}$ satisfy a much stronger property than being
incompressible: the no-gap delocalization result of [30] (see Theorem 6.3)
guarantees that with a very high possibility, all eigenvectors have
$(1-c_{1})n$ coordinates that are at least $(c_{1}c_{2})^{6}n^{-1/2}$ in
absolute value, for any $c_{1}>0$. This allows us to take the union of the
large locations of $d$ different eigenvectors, justifying the heuristic
reduction. The multi-matrix version of the invertibility via the distance
approach is quite nontrivial even from the first step.

A second, more serious issue emerges when we consider discrete entry
distributions (i.e. entry distribution without a continuous density). It is
not so difficult to prove that any eigenvector of $A_{n}$ should have a large
least common denominator (LCD) with very high possibility (for example see
[32], [38] and [10] for definitions and proofs). This is because each
eigenvector $v$ satisfies $(A_{n}-\lambda I_{n})v=0$ for some $\lambda$, and
this matrix $A_{n}$ has a large portion of independent components, permitting
the use of the tensorization lemma (see [32], [38]) to obtain an exponential
bound. Now we consider multiple locations, and thus we have to consider the
least common denominator of vectors of the form $v=\cos\theta v_{1}+\sin\theta
v_{2}$ where $v_{1}$ and $v_{2}$ are two eigenvectors of $A_{n}$. This time
$v$ is only annihilated by $A_{n}^{2}+\alpha A_{n}+\beta$ for some $\alpha$
and $\beta$, and the matrix $A_{n}^{2}$ has a complete loss of independence:
every other element is strongly dependent. We are not aware of any method that
can effectively solve this issue, so we consider only entries with a
continuous distribution, completely avoiding the arithmetic conditions based
on LCD. It would be very fortunate to overcome this barrier in the future.
Note that when $d=2$, we can still prove that $v$ is incompressible for any
$\theta$ with very high probability, but this information is not strong enough
to complete the proof. When $d\geq 3$ the argument completely breaks down for
the linear span of three different eigenvectors, so we do not pursue this
approach any further.

We should also note that in addition to assuming that the entry distributions
of $A_{n}$ have a continuous density, we also assume that the density has a
component whose Fourier transform decays like a Gaussian (1.3). This
assumption will be used in Section 2 and significantly simplifies the
reasoning. It might be possible to remove this assumption with some effort,
but we believe that removing all the density assumptions is pretty challenging
at the current stage.

There are several other remaining technical difficulties. First, when
analyzing the function $I(\theta)$ defined in (2.2) for different values of
$\theta$, it appears that we need some care to where $\theta$ lies in the
integration region. We divide the region into an essentially lower dimensional
region and a genuinely full dimensional region, and for the latter we have to
rely on our induction hypothesis, that is, we prove Theorem 1.2 inductively
from $d=2$ upward. For the full dimensional region, it is very natural to hope
for a probability bound on $I(\theta)$ that is good enough to tame the
singularity of integration (see for example (5.13)). This leads to the
estimate in Lemma 4.1. We have been slightly careless in the power of $s$ in
Lemma 4.1: one would expect the estimate to be $s^{d}e^{-k}$ so as to tame the
singularity in (5.13). Unfortunately this approach is neither feasible nor
helpful: it seems that raising to power $s^{d}$ in Lemma 4.1is extremely
difficult and may not be possible at all, and more importantly, our decoupling
estimate in Theorem 2.1 causes us to eventually lose half of the power of $s$.

To address the last difficulty, we take special care and integrate to
$(\prod_{i=1}^{d}\frac{\mu_{1}(\lambda_{i})}{\sqrt{n}})^{1-\frac{1}{4d}}$ at
the end (where $\mu_{1}(\lambda_{i})$ is the largest singular value of
$(A_{n}-\lambda_{i}I_{n})^{-1}$). There are several considerations when we
choose the product: it would also be possible to integrate to, say,
$(\frac{\mu_{1}(\lambda_{i})}{\sqrt{n}})^{d-1/4}$, but the expectation of this
term diverges as the power becomes too high. One may also consider controlling
$\prod_{i=1}^{d}\mu_{1}(\lambda_{i})$ via Hölder inequality to decouple one
another, but this would again lead to a very high power. The correct idea here
is to treat the product $\prod_{i=1}^{d}\mu_{1}(\lambda_{i})$ as a whole and
perform a bootstrapping procedure, whose details are outlined in Section 7.
Indeed, we are somewhat using the intuition that $\mu_{1}(\lambda_{i})$ are
mutually independent, so that once the power of each of them is less than one,
the expectation is still finite. This is not a proof by circulation: we just
regard $\prod\mu_{1}(\lambda_{i})$ as a whole and bootstrap, ultimately
showing that they are somewhat asymptotically independent. By these
considerations, we choose to use
$\prod_{i=1}^{d}|\theta_{i}|,\theta\in\mathbb{R}^{d}$ as a measure to
partition the region of integration, rather than using the standard Euclidean
norm.

###  1.4. Notation conventions and some preliminary facts

Recall that $\Gamma$ denotes all the mean zero, variance one, subGaussian
random variables.

For any $\zeta\in\Gamma$ we denote by $\operatorname{Sym}_{n}(\zeta)$ the
probability space of symmetric $n\times n$ random matrices with entries
$(A_{ij})_{i<j}$ independent and identically distributed with distribution
$\zeta$, and entries $(A_{ii})_{1\leq i\leq n}$ i.i.d. with distribution
$\bar{\sigma_{0}}\zeta$ and independent of $(A_{ij})_{i<j}$. Strictly speaking
this definition also depends on $\bar{\sigma_{0}}$, but we fix this parameter
in the sequel and omit it in the notation. We also write
$X\in\operatorname{Col}_{n}(\zeta)$ if $X\in\mathbb{R}^{n}$ has independent
coordinates following the distribution $\zeta$.

The spaces $(\operatorname{Sym}_{n}(\zeta))_{n\geq 1}$ are coupled as follows:
we sample $A_{n+1}\sim\operatorname{Sym}_{n+1}(\zeta)$ via first sampling
$A_{n}\sim\operatorname{Sym}_{n}(\zeta)$ and put it in the $[2,\cdots,n+1]$
principal minor in $\operatorname{Sym}_{n+1}(\zeta)$, then independently
sample a random vector $X\in\operatorname{Col}_{n}(\zeta)$ as the first row
and column (with the first entry removed), and finally sample the (1,1)-th
entry of $A_{n+1}$ independently from $\zeta$.

Different sets of assumptions are used to state the main estimates in this
paper. In some of these lemmas, we only assume an entry distribution
$\zeta\in\Gamma_{B}$ for some $B$. In other lemmas we assume moreover that
$\zeta$ satisfies the assumptions in Theorem 1.2. In other words, in the
former case the estimate depends only on $B$ but in the latter case the
estimate also depends on the constants $G$,$K$ and $\sigma_{0}$ in the
definitions of $\zeta_{1}$ and $\zeta_{2}$.

Here we collect some basic facts that will be useful throughout the paper.

Let $Y\sim\operatorname{Col}_{n}(\zeta)$ with $\zeta\in\Gamma_{B}$, then for
any fixed $u\in\mathbb{R}^{n}$,

$\mathbb{E}_{Y}e^{\langle Y,u\rangle}\leq\exp(2B^{2}\|u\|_{2}^{2}).$ (1.9)

Before we start the proof we recall the following two useful properties from
Vershynin [38].

######  Lemma 1.8.

Given $B>0$, $\zeta\in\Gamma_{B}$ and $A_{n}\sim\operatorname{Sym}_{n}(\xi)$.
Then for any $t>0$ we have

$\mathbb{P}\left(\|A_{n}\|_{op}\geq(3+t)\sqrt{n}\right)\leq e^{-ct^{3/2}n}$
(1.10)

for some constant $c>0$ depending only on $B$.

We also need the following linear algebra fact from Vershynin [38]:

######  Fact 1.9.

For $A=(a_{ij})$ an $n\times n$ matrix, let $A_{1}$ be the first column of $A$
and $H_{1}$ the span of the other $n-1$ columns. Additionally, let $B$ be the
$(n-1)\times(n-1)$ minor from removing the first row and first column of $A$.
Let $X\in\mathbb{R}^{n-1}$ be the first column of $A$ with the first element
removed. Then

$\operatorname{dist}(A_{1},H_{1})=\frac{\left|\langle B^{-1}X,X\rangle-
a_{11}\right|}{\sqrt{1+\|B^{-1}X\|_{2}^{2}}}.$

###  1.5. Plan of the paper

The main body of this paper, until Section 8, is devoted to proving Theorem
1.2. We will follow an inductive approach on $d\in\mathbb{N}_{+}$. We feel it
would be better to perform the $d=2$ case first in full detail, and return to
the general $d$ case later via an induction argument. We prove the $d=2$ case
of Theorem 1.2 in Sections 7 and outline the main modifications for the
general $d$ case in Section 8. The contents in sections 2, 3 and 4 work for
general $d$, where Section 3 is only about eigenvalue spacing estimates.
Finally, in Section 9 we prove Theorem 1.5 as a modification of the proof of
Theorem 1.2.

##  2\. Small ball probability of quadratic forms

The main result of this section is the following lemma, which provides a means
to effectively estimate the quantities appearing in the numerator of the
distance function in Fact 1.9.

######  Theorem 2.1.

Given $B,\sigma,K>0$, $\zeta_{1}\in\Gamma_{1}(G,B,\sigma)$ and
$\zeta_{2}\in\Gamma_{2}(G,K,\sigma)$ be independent. Let $A_{n}$ be any
$n\times n$ matrix and $X\sim\operatorname{Col}_{n}(\zeta_{1}+\zeta_{2})$ be a
random vector independent of $A_{n}$. Let
$\lambda_{1},\cdots,\lambda_{d}\in\mathbb{R}$ be fixed real numbers and
$\delta_{1},\cdots,\delta_{d}>0$. For each $i=1,\cdots,d$ denote by
$\mu_{1}(\lambda_{i}):=\sigma_{\operatorname{max}}\left((A_{n}-\lambda_{i}I_{n})^{-1}\right)$.
Then, for any $(t_{1},\cdots,t_{d})\in\mathbb{R}^{d}$, and any
$u\in\mathbb{R}^{n}$ with $\|u\|_{2}\leq d$,

$\displaystyle\mathbb{P}_{X}\left(\bigcap_{i=1}^{d}\left\\{\left\langle(A_{n}-\lambda_{i}I_{n})^{-1}X,X\rangle-
t_{i}|\leq\delta_{i}\mu_{1}(\lambda_{i})\right\\},\langle X,u\right\rangle\geq
s\right)$ (2.1) $\displaystyle\lesssim\prod_{i=1}^{d}\delta_{i}\cdot
e^{-s}\cdot\int_{\\{\sum_{i=1}^{d}|\theta_{i}\delta_{i}|^{2}\leq
d\\}\subset\mathbb{R}^{d}}I(\theta)^{\frac{1}{2}}d\theta,$

where $I(\theta)$ is defined as follows: for two independent random vectors
$X_{2},X_{2}^{\prime}\sim\operatorname{Col}_{n}(\zeta_{2})$, we define
$I(\theta)$ for each $\theta\in\mathbb{R}^{d}$ via

$I(\theta)=\mathbb{E}_{X_{2},X_{2}^{\prime}}\exp\left(\langle
X_{2}+X_{2}^{\prime},u\rangle-c\left\|\sum_{i=1}^{d}\frac{\theta_{i}}{\mu_{1}(\lambda_{i})}(A_{n}-\lambda_{i}I_{n})^{-1}(X_{2}-X_{2}^{\prime})\right\|_{2}^{2}\right),$
(2.2)

where $c>0$ depends only on $G,B,\sigma$ and $K$.

We first prove a version of the quadratic form decoupling estimate, which is
adapted from [10], Lemma 5.3.

######  Lemma 2.2.

Given $\xi_{1}\in\Gamma_{1}(G,B,\sigma)$ and
$\xi_{2}\in\Gamma_{2}(G,K,\sigma)$. Let
$X_{1},X_{1}^{\prime}\sim\operatorname{Col}_{n}(\xi_{1})$ be independent
vectors and let let $X_{2},X_{2}^{\prime}\sim\operatorname{Col}_{n}(\xi_{2})$
be independent vectors. We use the symbol $\mathbb{E}_{X}$ to denote the
expectation with respect to both $X_{1}$ and $X_{2}$, and we use
$\mathbb{E}_{X_{i}}$ to denote the expectation with respect to $X_{i}$ for
each $i$. Then for any $n\times n$ symmetric matrix $M$ and
$u\in\mathbb{R}^{n}$, we have

$\displaystyle\left|\mathbb{E}_{X}e^{2\pi i\theta\langle
M(X_{1}+X_{2}),(X_{1}+X_{2})\rangle+\langle X_{1}+X_{2},u\rangle}\right|^{2}$
$\displaystyle\quad\leq\mathbb{E}_{X_{2},X_{2}^{\prime}}e^{\langle(X_{2}+X_{2}^{\prime}),u\rangle}\cdot\left|\mathbb{E}_{X_{1}}e^{4\pi
i\theta\langle M(X_{2}-X_{2}^{\prime}),X_{1}\rangle+2\langle
X_{1},u\rangle}\right|.$

###### Proof.

Writing $\mathbb{E}_{X}=\mathbb{E}_{X_{1}}\mathbb{E}_{X_{2}}$ and applying
Jensen’s inequality, we deduce

$\displaystyle E:=|\mathbb{E}_{X}e^{2\pi i\theta\langle
M(X_{1}+X_{2}),X_{1}+X_{2}\rangle+\langle X_{1}+X_{2},u\rangle}|^{2}$
$\displaystyle\leq\mathbb{E}_{X_{1}}|\mathbb{E}_{X_{2}}e^{2\pi i\theta\langle
M(X_{1}+X_{2}),X_{1}+X_{2}\rangle+\langle X_{1}+X_{2},u\rangle}|^{2}.$

Expanding the square $|\mathbb{E}_{X_{2}}e^{2\pi i\theta\langle
M(X_{1}+X_{2}),X_{1}+X_{2}\rangle+\langle X_{1}+X_{2},u\rangle}|^{2}$, we
obtain

$\displaystyle\mathbb{E}_{X_{2},X_{2}^{\prime}}e^{2\pi i\theta\langle
M(X_{1}+X_{2}),(X_{1}+X_{2})\rangle+\langle(X_{1}+X_{2}),u\rangle-2\pi
i\theta\langle M(X_{1}+X_{2}^{\prime}),(X_{1}+X_{2}^{\prime})\rangle+\langle
X_{1}+X_{2}^{\prime},u\rangle}$
$\displaystyle\quad=\mathbb{E}_{X_{2},X_{2}^{\prime}}e^{4\pi i\theta\langle
M(X_{2}-X_{2}^{\prime}),X_{1}\rangle+\langle
X_{2}+X_{2}^{\prime},u\rangle+2\langle X_{1},u\rangle+2\pi i\theta\langle
MX_{2},X_{2}\rangle-2\pi i\theta\langle
MX_{2}^{\prime},X_{2}^{\prime}\rangle}.$

Swapping expectations, we obtain

$\displaystyle E$
$\displaystyle\leq\mathbb{E}_{X_{2},X_{2}^{\prime}}|\mathbb{E}_{X_{1}}e^{4\pi
i\theta\langle M(X_{2}-X_{2}^{\prime}),X_{1}\rangle+\langle
X_{2}+X_{2}^{\prime},u\rangle+2\langle X_{1},u\rangle+2\pi i\theta\langle
MX_{2},X_{2}\rangle-2\pi i\theta\langle
MX_{2}^{\prime},X_{2}^{\prime}\rangle}|.$

Swapping the $X_{1}$-independent terms out completes the proof. ∎

Now we prove a lemma that makes use of the Fourier decay of $X_{1}$ and
decouples the inner product $\langle X_{1},u\rangle$.

######  Lemma 2.3.

Let $X_{1}\sim\operatorname{Col}_{n}(\zeta_{1})$ where
$\zeta_{1}\in\Gamma_{1}(G,B,\sigma)$, and let $u,v\in\mathbb{R}^{n}$ be two
fixed vectors. Then

$|\mathbb{E}_{X}e^{2\pi i\langle X,v\rangle+\langle X,u\rangle}|\leq
c^{-1}\exp\left(-c\|v\|_{2}^{2}+c^{-1}\|u\|_{2}^{2}\right)$ (2.3)

where $c\in(0,1)$ is a fixed constant depending only on $G,B,\sigma$.

###### Proof.

Consider $\zeta_{1}^{\prime}$ an independent copy of $\zeta_{1}$. We compute

$|\mathbb{E}_{\zeta_{1}}e^{2\pi
i\zeta_{1}v_{j}+\zeta_{1}u_{j}}|^{2}=\mathbb{E}_{\zeta_{1},\zeta_{1}^{\prime}}e^{2\pi
i(\zeta_{1}-\zeta_{1}^{\prime})v_{j}+(\zeta_{1}+\zeta_{1}^{\prime})u_{j}}=\mathbb{E}_{\zeta_{1},\zeta_{1}^{\prime}}[e^{(\zeta_{1}+\zeta_{1}^{\prime})u_{j}}\cos(2\pi(\zeta_{1}-\zeta_{1}^{\prime})v_{j})].$

Consider $\widetilde{X}=(\widetilde{X}_{i})_{i=1}^{n},$
$\widetilde{Y}=(\widetilde{Y}_{i})_{i=1}^{n}$ two given vectors with i.i.d.
coordinates having the distribution $\xi:=\zeta_{1}-\zeta_{1}^{\prime}$ and
$\zeta_{1}+\zeta_{1}^{\prime}$. Then by Cauchy-Schwartz and the bound
$|\cos(x)|^{2}\leq|\cos(x)|$,

$|\mathbb{E}_{X}e^{2\pi i\langle X,v\rangle+\langle
X,u\rangle}|^{2}\leq\mathbb{E}e^{\langle\widetilde{Y},u\rangle}\prod_{j}\cos(2\pi\widetilde{X}_{j}v_{j})\leq(\mathbb{E}_{\widetilde{Y}}e^{2\langle\widetilde{Y},u})^{\frac{1}{2}}\left(\prod_{j}\mathbb{E}_{\xi}|\cos(2\pi\xi
v_{j})|\right)^{\frac{1}{2}}.$ (2.4)

By (1.9), we have
$\mathbb{E}_{\widetilde{Y}}e^{2\langle\widetilde{Y},u\rangle}$ is bounded by
$\exp(\mathcal{O}(\|u\|_{2}^{2}))$. Applying the Fourier decay assumptions on
$\zeta_{1}$ (1.3) finally completes the proof. ∎

Note: the Fourier decay assumption (1.3) is essential here. Without this
assumption we can only obtain $\|v\|_{\mathbb{T}}$ in the estimate (see [10],
Fact 5.4), which measures the closeness of $v$ to the integer lattice.
Unfortunately we do not have good control of this quantity in this paper where
we have multiple locations $\lambda_{i}\neq\lambda_{j}$.

We also need the following multidimensional Esseen inequality [14]:

######  Lemma 2.4.

Let $Z$ be a random vector in $\mathbb{R}^{m}$, then

$\sup_{v\in\mathbb{R}^{m}}\mathbb{P}(\|Z-v\|_{2}\leq\sqrt{m})\leq
C^{m}\int_{B(0,\sqrt{m})}|\phi_{Z}(\theta)|d\theta,$

with $\phi_{Z}(\theta)=\mathbb{E}\exp(2\pi i\langle\theta,Z\rangle)$.

Via a simple rescaling argument, we deduce that

######  Corollary 2.5.

Let $Z_{1},Z_{2},\cdots Z_{d}$ be real-valued random variables (not
necessarily independent) and let $\delta_{1},\delta_{2},\cdots,\delta_{d}>0$
be fixed constants. Then

$\sup_{\\{v_{i}\\}_{i=1}^{d}\in\mathbb{R}^{d}}\mathbb{P}\left(\cap_{i=1}^{d}\\{\|Z_{i}-v_{i}\|\leq\delta_{i}\\}\right)\lesssim\prod_{i=1}^{d}\delta_{i}\int_{\\{\sum_{i=1}^{d}|\theta_{i}\delta_{i}|^{2}\leq
d\\}}|\phi_{\\{Z_{i}\\}_{i=1}^{d}}(\theta)|d\theta,$ (2.5)

where $\theta\in\mathbb{R}^{d}$ and
$\phi_{\\{Z_{i}\\}_{i=1}^{d}}(\theta)=\mathbb{E}\left(2\pi
i(\sum_{i}\theta_{i}Z_{i})\right)$.

We prove the following lemma, which is a multidimensional version of [10],
Lemma 5.1:

######  Lemma 2.6.

Let $X\sim\operatorname{Col}_{n}(\zeta_{1}+\zeta_{2})$, where
$(\zeta_{1},\zeta_{2})\in\Gamma_{1}(G,B,\sigma)\times\Gamma_{2}(G,K,\sigma)$
and $\zeta_{1},\zeta_{2}$ are independent. Let $M_{i}$, $i=1,\cdots,d$ be $d$
$n\times n$ real symmetric matrices, $u\in\mathbb{R}^{n}$,
$t_{1},\cdots,t_{d}\in\mathbb{R}$ and $s,\delta_{1},\cdots,\delta_{d}\geq 0$.
Then we have

$\displaystyle\mathbb{P}\left(\bigcap_{i=1}^{d}\\{|\langle M_{i}X,X\rangle-
t_{i}|<\delta_{i}\\},\langle X,u\rangle\geq s\right)$ (2.6)
$\displaystyle\lesssim\prod_{i=1}^{d}\delta_{i}\cdot
e^{-s}\cdot\int_{\\{\sum_{i=1}^{d}|\theta_{i}\delta_{i}|^{2}\leq
d\\}}|\mathbb{E}^{2\pi i\sum_{i=1}^{d}\theta_{i}\langle
M_{i}X,X\rangle+\langle X,u\rangle}|d\theta.$

###### Proof.

Using $1\\{x\geq s\\}\leq e^{x-s}$ we bound the left hand side of the equation
from above by

$e^{-s}\mathbb{E}\left[\prod_{i=1}^{d}\mathbf{1}\\{|\langle M_{i}X,X\rangle-
t_{i}|<\delta_{i}\\}\cdot e^{X,u}\right].$ (2.7)

Consider the auxiliary random variable $Y\in\mathbb{R}^{n}$ that satisfies,
for all open $U\subseteq\mathbb{R}^{n}$,

$\mathbb{P}(Y\in U)=(\mathbb{E}e^{\langle
X,u\rangle})^{-1}\mathbb{E}[\mathbf{1}_{U}e^{\langle X,u\rangle}].$ (2.8)

Then we rewrite (2.7) as

$\eqref{equation2.41}=e^{-s}(\mathbb{E}e^{\langle
X,u\rangle})\mathbb{P}_{Y}\left(\cap_{i=1}^{d}\\{|\langle M_{i}Y,Y\rangle-
t_{i}|\leq\delta_{i}\\}\right).$ (2.9)

Then we apply Corollary 2.5 to $Y$ and obtain

$\displaystyle\mathbb{P}_{Y}\left(\cap_{i=1}^{d}\\{|\langle M_{i}Y,Y\rangle-
t_{i}|\leq\delta_{i}\\}\right)$
$\displaystyle\quad\lesssim\prod_{i=1}^{d}\delta_{i}\cdot\int_{\\{\sum_{i=1}^{d}|\theta_{i}\delta_{i}|^{2}\leq
d\\}}|\mathbb{E}_{Y}e^{2\pi i\sum_{i=1}^{d}\theta_{i}\langle
M_{i}Y,Y\rangle}|d\theta.$

Finally, by definition of $Y$,

$\mathbb{E}_{Y}e^{2\pi i\sum_{i=1}^{d}\theta_{i}\langle
M_{i}Y,Y\rangle}=(\mathbb{E}_{X}e^{\langle X,u\rangle})^{-1}\mathbb{E}e^{2\pi
i\sum_{i=1}^{d}\theta_{i}\langle M_{i}X,X\rangle+\langle X,u\rangle},$

and the proof is completed. ∎

Now we are ready to prove Theorem 2.1.

###### Proof of Theorem 2.1.

Throughout the proof we write $X=X_{1}+X_{2}$ where
$X_{1}\sim\operatorname{Col}_{n}(\zeta_{1})$ and
$X_{2}\sim\operatorname{Col}_{n}(\zeta_{2})$ are independent random vectors.

We first apply Corollary 2.5 to write

$\displaystyle\mathbb{P}_{X}\left(\cap_{i=1}^{d}\left\\{\left|\langle(A_{n}-\lambda_{i}I_{n})^{-1}X,X\rangle-
t_{i}\right|\leq\delta_{i}\cdot\mu_{1}(\lambda_{i})\right\\},\quad\langle
X,u\rangle\geq s\right)$ (2.10)
$\displaystyle\lesssim\prod_{i=1}^{d}\delta_{i}\cdot
e^{-s}\int_{\\{\sum_{i=1}^{d}|\theta_{i}\delta_{i}|^{2}\leq
d\\}}\left|\mathbb{E}_{X}e^{2\pi
i\left\langle\left(\sum_{i=1}^{d}\frac{\theta_{i}(A_{n}-\lambda_{i}I_{n})^{-1}X}{\mu_{1}(\lambda_{i})}\right),X\right\rangle+\langle
X,u\rangle}\right|d\theta.$

Then we apply the decoupling lemma (Lemma 2.2) to deduce that

$\displaystyle\left|\mathbb{E}_{X}e^{2\pi
i\left\langle\left(\sum_{i=1}^{d}\frac{\theta_{i}(A_{n}-\lambda_{i}I_{n})^{-1}X}{\mu_{1}(\lambda_{i})}\right),X\right\rangle+\langle
X,u\rangle}\right|^{2}$ (2.11)
$\displaystyle\leq\mathbb{E}_{X_{2},X_{2}^{\prime}}e^{\langle(X_{2}+X_{2}^{\prime}),u\rangle}\cdot\left|\mathbb{E}_{X_{1}}e^{4\pi
i\left\langle\left(\sum_{i=1}^{d}\frac{\theta_{i}(A_{n}-\lambda_{i}I_{n})^{-1}\widetilde{X}_{2}}{\mu_{1}(\lambda_{i})}\right),X_{1}\right\rangle+2\langle
X_{1},u\rangle}\right|,$

where $\widetilde{X}:=X_{2}-X_{2}^{\prime}$.

Finally, we apply Lemma 2.3 to the $\mathbb{E}_{X_{1}}$ term and complete the
proof.

∎

##  3\. Eigenvalue spacing estimates

The main objective of this section is to establish eigenvalue rigidity
estimates for Wigner matrices. We make crucial use of the local semicircle
law, as well as the super-exponential concentration of the empirical measure
guaranteed by a finite log-Sobolev constant on the entries. Informally
speaking, the main results are that with probability $1-e^{-\Omega(n)}$, we
have very well control on $\mu_{k}(\lambda_{i})$ from both sides, for $k\geq
cn$ and $\lambda_{i}$ in the bulk. We also have very good control of
$\sqrt{n}/(k\mu_{k}(\lambda_{i}))$ from above, for any $k$ and any
$\lambda_{i}$ in the bulk. This section is mostly technical and readers can
skip to the next section and turn back once the results here are needed.

Throughout this section we will use a simple yet crucial property of symmetric
matrices $A_{n}$: for any $\lambda_{i}\in\mathbb{R}$,
$(A_{n}-\lambda_{i}I_{n})^{-1}$ has the same set of eigenvectors as
$(A_{n}-\lambda_{i}I_{n})$, thus it has the same set of eigenvectors as
$A_{n}$. Moreover, the singular values of $(A_{n}-\lambda_{i}I_{n})^{-1}$ and
that of $A_{n}$ have very simple relationships.

Recall that for any $\lambda_{i}\in\mathbb{R}$, we denote by
$\mu_{1}(\lambda_{i})\geq\mu_{2}(\lambda_{i})\cdots\geq\mu_{n}(\lambda_{i})\geq
0$ the singular values of $(A_{n}-\lambda_{i}I)^{-1}$ in decreasing order.
Additionally, we define a modified function $\|\cdot\|_{*}$ for
$(A-\lambda_{i}I)^{-1}$ via

$\left\|(A_{n}-\lambda_{i}I_{n})^{-1}\right\|_{*}^{2}=\sum_{k=1}^{n}\mu_{k}(\lambda_{i})^{2}(\log(1+k))^{2}.$
(3.1)

###  3.1. Single location estimate

We first prove the following two lemmas that generalize Lemmas 8.1 and 8.2 of
[10] to nonzero eigenvalues in the bulk.

######  Lemma 3.1.

For any $p>1$, $B>0$, $\kappa>0$ and $\zeta\in\Gamma_{B}$, let
$A\sim\operatorname{Sym}_{n}(\zeta)$. Then we can find a constant $C_{p}$
depending on $B$, $p$ and $\kappa$ such that for any
$\lambda_{i}\in[-(2-\kappa)\sqrt{n},(2-\kappa)\sqrt{n}]$ we have

$\mathbb{E}\left[\left(\frac{\sqrt{n}}{\mu_{k}(\lambda_{i})\cdot
k}\right)^{p}\right]\leq C_{p}.$

We will also need the following corollary:

######  Corollary 3.2.

For a given $p>1$, $B>0$, $\kappa>0$ and $\zeta\in\Gamma_{B}$,
$A\in\operatorname{Sym}_{n}(\zeta)$. Then we can find a constant $C_{P}>0$
depending on $B$, $p$, $\kappa$ such that for any
$\lambda_{i}\in[(-(2-\kappa)\sqrt{n},(2-\kappa)\sqrt{n}]$, we have

$\mathbb{E}\left[\left(\frac{\|(A_{n}-\lambda_{i}I_{n})^{-1}\|_{*}}{\mu_{1}(\lambda_{i})}\right)^{p}\right]\leq
C_{p}.$ (3.2)

The proofs of both results are modifications of those in [10] to nonzero bulk
values. For this proof we need the following local semicircular law estimates
of Erdös, Schlein and Yau on Wigner matrices from [13], Theorem 1.11. The
Wigner semicircle law $\rho_{sc}$ is defined as

$\rho_{sc}(x):=\frac{1}{2\pi}\sqrt{(4-x^{2})_{+}},\quad x\in\mathbb{R}.$ (3.3)

######  Theorem 3.3.

([13], Theorem 1.11.) Let $H\in\operatorname{Sym}_{n}(\zeta)$ where
$\zeta\in\Gamma_{B}$ for some $B>0$. Let $\kappa>0$ and consider
$E\in[-2+\kappa,2-\kappa]$. Denote by
$\mathcal{N}_{\eta^{*}}(E)=\mathcal{N}_{I^{*}}$ the number of eigenvalues of
$n^{-\frac{1}{2}}H$ in $I^{*}:=[E-\eta^{*}/2,E+\eta^{*}/2]$. Then we can find
a universal constant $c_{1}$ and two constants $C$, $c$ depending only on
$\kappa$ such that for any $\delta\leq c_{1}\kappa$ we can find a constant
$K_{\delta}$ depending only on $\delta$ such that

$\mathbb{P}\left\\{\left|\frac{\mathcal{N}_{\eta^{*}}(E)}{n\eta^{*}}-\rho_{sc}(E)\right|\geq\delta\right\\}\leq
Ce^{-c\delta^{2}\sqrt{n\eta^{*}}},$ (3.4)

for all $\eta^{*}$ satisfying $K_{\delta}/n\leq\eta^{*}\leq 1$ and all $n\geq
2$.

Since $\rho_{sc}(x)$ is maximal at $x=0$ and decreases as $|x|$ increases, we
deduce the following user-friendly corollary:

######  Corollary 3.4.

In the setting of Theorem 3.3, for any $\kappa>0$ we have the following two
estimates uniform in all $E\in[-2+\kappa,2-\kappa]$: for any
$\eta^{*}\in[Cn^{-1},1]$,

$\mathbb{P}\left\\{\frac{\mathcal{N}_{\eta^{*}}(E)}{n\eta^{*}}\geq\pi\right\\}\lesssim\exp(-c_{1}\sqrt{n\eta^{*}}),$
(3.5)

and

$\mathbb{P}\left\\{\frac{\mathcal{N}_{\eta^{*}}(E)}{n\eta^{*}}\leq\frac{1}{4}\rho_{sc}(2-\kappa)\right\\}\lesssim\exp(-c_{1}\sqrt{n\eta^{*}}),$
(3.6)

where $C$ and $c_{1}$ are constants that depend only on $\kappa>0$.

From this estimate we deduce two immediate corollaries.

######  Corollary 3.5.

Fix $B>0$, $\zeta\in\Gamma_{B}$ and $A_{n}\sim\operatorname{Sym}_{n}(\zeta)$.
Fixing $\kappa>0$, then we can find positive constants $C$ and $c$ depending
only on $\kappa$ such that, for all $s\geq C$ and $k\in\mathbb{N}$ that
satisfy $sk\leq n$, uniformly for all
$\lambda_{i}\in[-(2-\kappa)\sqrt{n},(2-\kappa)\sqrt{n}]$,

$\mathbb{P}\left(\frac{\sqrt{n}}{\mu_{k}(\lambda_{i})\cdot k}\geq
s\right)\lesssim\exp(-c(sk)^{\frac{1}{2}}).$

We also have, uniformly for all
$\lambda_{i}\in[-(2-\kappa)\sqrt{n},(2-\kappa)\sqrt{n}]$, for all
$k\in\mathbb{N}_{+},$

$\mathbb{P}\left(\mu_{k}(\lambda_{i})\geq\frac{\sqrt{n}}{Ck}\right)\lesssim\exp(-ck^{\frac{1}{2}}).$

###### Proof.

Let $C$ be the larger one of $\pi$, $\frac{4}{\rho_{sc}(2-\kappa)}$ and the
constant $C$ in the statement of Corollary 3.4. If
$\frac{\sqrt{n}}{\mu_{k}(\lambda_{i})\cdot k}\geq s$, then
$N_{n^{-\frac{1}{2}}A}(-skn^{-1}+\lambda_{i}n^{-}\frac{1}{2},skn^{-1}+\lambda_{k}n^{-}\frac{1}{2})\leq
k$, where we use the symbol $N_{H}(I)$ to denote the number of eigenvalues of
$H$ in the interval $I$.

Then the first claim follows by applying estimate 3.6 with
$\eta_{*}=skn^{-1}\geq sn^{-1}\geq Cn^{-1}$ and noticing
$s^{-1}\leq\frac{\rho_{sc}(2-\kappa)}{4}$. The second claim follows from
applying the estimate 3.5 with $\eta_{*}=Ckn^{-1}\geq Cn^{-1}$ and noticing
$C\geq\pi$. ∎

Now we are in the place to prove Lemma 3.1 and Corollary 3.2.

###### Proof of Lemma 3.1.

Let $C$ be the constant determined in Corollary 3.5. From the tail estimate on
$\|A_{n}\|_{op}$ in Lemma 1.8, we deduce that for any $k\geq n/c$ and any
$\lambda_{i}\in[-(2-\kappa)\sqrt{n},(2-\kappa)\sqrt{n}]$,

$\mathbb{E}\left(\frac{\sqrt{n}}{\mu_{k}(\lambda_{i})\cdot
k}\right)^{p}\leq\mathbb{E}_{A_{n}}\left(\frac{\sigma_{1}(A_{n}+\lambda_{i}I_{n})\sqrt{n}}{k}\right)^{p}=O_{p}((n/k))^{p}=O_{p}(1).$

Then for $k\leq n/c$, we consider separately the following three events

$E_{1}^{i}=\left\\{\frac{\sqrt{n}}{\mu_{k}(\lambda_{i})\cdot k}\leq
C\right\\},\quad E_{2}^{i}=\left\\{\frac{\sqrt{n}}{\mu_{k}(\lambda_{i})\cdot
k}\in[C,\frac{n}{k}]\right\\},\quad
E_{3}^{i}=\left\\{\frac{\sqrt{n}}{\mu_{k}(\lambda_{i})\cdot
k}\geq\frac{n}{k}\right\\}$

and bound

$\mathbb{E}\left(\frac{\sqrt{n}}{\mu_{k}(\lambda_{i})\cdot k}\right)^{p}\leq
C^{p}+\mathbb{E}\left(\frac{\sqrt{n}}{\mu_{k}(\lambda_{i})\cdot
k}\right)^{p}\mathbf{1}_{E_{2}^{i}}+\mathbb{E}\left(\frac{\sqrt{n}}{\mu_{k}(\lambda_{i})\cdot
k}\right)^{p}\mathbf{1}_{E_{3}^{i}}.$ (3.7)

For the second term, we apply Corollary 3.5 to bound

$\mathbb{E}\left(\frac{\sqrt{n}}{\mu_{k}(\lambda_{i})\cdot
k}\right)^{p}\lesssim\int_{C}^{n/k}ps^{p-1}e^{-c\sqrt{sk}}ds=O_{p}(1).$

For the third term, since $n/k\geq C$, we apply Corollary 3.5 with $s=n/k$ and
deduce that $\mathbb{P}(E_{3}^{i})\lesssim e^{-c\sqrt{n}}$. Then applying the
Cauchy-Schwartz inequality,

$\displaystyle\mathbb{E}$
$\displaystyle\left(\frac{\sqrt{n}}{\mu_{k}(\lambda_{i})\cdot
k}\right)^{p}\mathbf{1}_{E_{3}^{i}}\leq\left(\mathbb{E}(\frac{\sigma_{1}(A_{n}-\lambda_{i}I_{n})\sqrt{n}}{k})^{2p}\right)^{1/2}\mathbb{P}(E_{3}^{i})^{1/2}$
$\displaystyle\leq O_{p}(1)n^{p}e^{-c\sqrt{n}}=O_{p}(1).$

The bound on $\sigma_{1}$ follows from Lemma 1.8. This completes the proof. ∎

###### Proof of Corollary 3.2.

Recall from definition that

$\|(A_{n}-\lambda_{i}I_{n})_{*}^{2}=\sum_{k=1}^{n}\mu_{k}^{2}(\lambda_{i})(\log(1+k))^{2}.$

We may take without loss of generality $p\geq 2$ thanks to Hölder’s
inequality, and apply the triangle inequality to obtain

$\left[\mathbb{E}\left(\sum_{k=1}^{n}\frac{\mu_{k}^{2}(\lambda_{i})(\log(1+k))^{2}}{\mu_{1}^{2}(\lambda_{i})}\right)^{p/2}\right]^{2/p}\leq\sum_{k=1}^{n}(\log(1+k))^{2}\mathbb{E}\left[\frac{\mu_{k}^{p}(\lambda_{i})}{\mu_{1}^{p}(\lambda_{i})}\right]^{2/p}.$

Now, taking $C$ as the constant given in Corollary 3.5, we apply Lemma 3.1 and
Corollary 3.5 to the upper bound

$\mathbb{E}\left[\frac{\mu_{k}^{p}(\lambda_{i})}{\mu_{1}^{p}(\lambda_{i})}\right]\leq(Ck)^{-p}\mathbb{E}\left[\left(\frac{\sqrt{n}}{\mu_{1}(\lambda_{i})}\right)^{p}\right]+\mathbb{P}(\mu_{k}\geq\frac{\sqrt{n}}{Ck})\lesssim
C_{p}^{p}k^{-p}$

for some other constant $C_{P}$. Then the corollary follows by plugging this
estimate into the previous one. ∎

###  3.2. Multiple location decay estimates

The main objective of this paper is to study singular values of $A_{n}$ at $d$
distinct values $\lambda_{1},\cdots,\lambda_{d}$ that are separated from one
another. For this reason, more refined decaying estimates of eigenvalues are
needed.

The following corollary follows from reformulating Corollary 3.5 and taking a
union bound over all $k\in[n]$. This tells us that we can have a rather strong
control of $\mu_{k}(\lambda_{i})$ as long as $k=\Omega(n^{\sigma})$ and
$\sigma>0$.

######  Corollary 3.6.

Let $B>0$, $\zeta\in\Gamma_{B}$ and $A_{n}\in\operatorname{Sym}_{n}(\zeta)$.
Fix any $\kappa>0$. Fix any
$\lambda_{i}\in[-(2-\kappa)\sqrt{n},(2-\kappa)\sqrt{n}]$ and any
$\sigma\in(0,1)$. Then for any $c_{0}>0$ we can find $c,C_{1}$ and $C_{2}$
depending only on $B$, $\kappa$ (and not on $c_{0}$) such that

$\mathbb{P}\left(\frac{C_{1}\sqrt{n}}{k}\leq\mu_{k}(\lambda_{i})\leq\frac{C_{2}\sqrt{n}}{k}\text{
for all }c_{0}n^{\sigma}\leq k\leq n/c\right)\geq
1-\exp(-\Omega(n^{\frac{\sigma}{2}})).$ (3.8)

###### Proof.

This follows from taking a union bound over $k$ in the conclusion of the
Corollary 3.5. ∎

When $\sigma=1$, this estimate (3.8) has the disadvantage that it only gives
an error of order $e^{-c\sqrt{n}}$, falling short of the desired $e^{-cn}$
error. To remedy this, we invoke the following stronger concentration
estimate, which relies on the fact that $\zeta$ has a finite log-Sobolev
constant.

######  Proposition 3.7.

[[18], Lemma 6.1] Let $B>0$, and $\zeta\in\Gamma_{B}$ be a random variable
having a finite, $n$-independent log-Sobolev constant. Consider
$A_{n}\sim\operatorname{Sym}_{n}(\zeta)$, and denote by
$\sigma_{1},\cdots,\sigma_{n}$ the eigenvalues of $A_{n}$. Define the
empirical measure $\rho_{A_{n}}^{n}$ via

$\rho_{A_{n}}^{n}:=\frac{1}{n}\sum_{i=1}^{n}\delta_{\frac{\sigma_{i}}{\sqrt{n}}}.$

where $\delta_{\cdot}$ is the delta measure. Then there exists
$\kappa\in(0,\frac{1}{10})$ such that

$\lim_{n\to\infty}\frac{1}{n}\ln\mathbb{P}[d(\rho_{A_{n}}^{n},\rho_{sc})>n^{-\kappa}]=-\infty,$
(3.9)

where $\rho_{sc}$ is the semicircle law (3.3) and the distance $d$ is the
Dudley (i.e., bounded Lipschitz) distance defined as follows: for two
probability measures $\mu$ and $\nu$,

$d(\mu,\nu)=\sup_{\|f\|_{L}\leq 1}\left|\int f(x)d\mu(x)-\int
f(x)d\nu(x)\right|,$

where $\|f\|_{L}:=\sup_{x\neq y}\frac{|f(x)-f(y)|}{|x-y|}+\sup_{x}|f(x)|$.

Via this refined concentration estimate (3.9), we can prove that on any
macroscopic interval of length $x\sqrt{n}$ centered at $\lambda_{i}$, there
cannot be too few eigenvalues or too many eigenvalues of $A_{n}$. We also
derive the speed at which $\mu_{k}(\lambda_{i})$ decreases as $k$ increases.
We formulate this idea as follows:

######  Corollary 3.8.

Given any $B>0$, a random variable $\zeta\in\Gamma_{B}$ that has a finite,
$n$-independent log-Sobolev constant, and a random matrix
$A_{n}\sim\operatorname{Sym}_{n}(\zeta)$. Then for any $\kappa>0$ we can find
some $C_{1},C_{2},C_{3}>0$ depending only on $\kappa$, $B$ and the log-Sobolev
constant (and not on $c_{0}$) such that, for any $c_{0}>0$ and
$\lambda_{i}\in[-(2-\kappa)\sqrt{n},(2-\kappa)\sqrt{n}]$,

$\mathbb{P}\left(\frac{C_{1}\sqrt{n}}{k}\leq\mu_{k}(\lambda_{i})\leq\frac{C_{2}\sqrt{n}}{k}\text{
for any }c_{0}n\leq k\leq C_{3}n\right)\geq 1-e^{-\Omega(n)}.$ (3.10)

In particular, we can find $C_{4}>1$ depending only on $\kappa$, $B$ and the
log-Sobolev constant such that for any $c_{0}>0$ and for each $\lambda_{i}$ in
the given interval,

$\left(\mu_{\frac{k}{C_{4}}}(\lambda_{i})\geq{4}\mu_{k}(\lambda_{i})\text{ for
any }c_{0}n\leq k\leq C_{3}n\right)\geq 1-e^{-\Omega(n)}.$

###### Proof.

In the proof, the constants $C_{1}$ and $C_{2}$ will not be determined until
the end of the proof. The fact that
$\mu_{k}(\lambda_{i})\geq\frac{C_{2}\sqrt{n}}{k}$ implies that on the interval
$[\lambda_{i}-\frac{k}{C_{2}\sqrt{n}},\lambda_{i}+\frac{k}{C_{2}\sqrt{n}}]$,
there are more than $k$ eigenvalues of $A_{n}$. Likewise,
$\mu_{k}(\lambda_{i})\leq\frac{C_{1}\sqrt{n}}{k}$ implies that on the interval
$[\lambda_{i}-\frac{k}{C_{1}\sqrt{n}},\lambda_{i}+\frac{k}{C_{1}\sqrt{n}}]$,
there are fewer than $k$ eigenvalues of $A_{n}$.

We now normalize by dividing the interval by $\sqrt{n}$ and consider
$I_{2}:=[\frac{\lambda_{i}}{\sqrt{n}}-\frac{k}{C_{2}n},\frac{\lambda_{i}}{\sqrt{n}}+\frac{k}{C_{2}n}]$.
Since the semicircle law $\rho_{sc}(E)$ has bounded density, this would imply
that $\rho_{sc}(I_{2})\leq\rho_{sc}(0)|I_{2}|=\rho_{sc}(0)\frac{2k}{C_{2}n}$.
Moreover, $\mu_{k}(\lambda_{i})\geq\frac{C_{2}\sqrt{n}}{k}$ implies that
$\rho_{A_{n}}^{n}(I_{2})\geq\frac{k}{n}$. Therefore, if we choose
$\rho_{sc}(0)\frac{2}{C_{2}}<1$, we must have
$|\rho_{A_{n}}^{n}(I_{2})-\rho_{sc}(I_{2})|\geq
c_{0}(1-\rho_{sc}(0)\frac{2}{C_{2}})>0$. Since $|I_{2}|\geq c_{0}>0$, this
event is super-exponentially unlikely according to Proposition 3.7.

Likewise, we consider
$I_{1}:=[\frac{\lambda_{i}}{\sqrt{n}}-\frac{k}{C_{1}n},\frac{\lambda_{i}}{\sqrt{n}}+\frac{k}{C_{1}n}]$.
Assume without loss of generality that $\lambda_{i}\geq 0$. If
$\frac{k}{{C_{1}n}}\leq 2$, then
$\mu_{sc}(I_{1})\geq\frac{k}{C_{1}n}\rho_{sc}(2-\kappa)$. However the
assumption that $\mu_{k}(\lambda_{i})\leq\frac{C_{1}\sqrt{n}}{k}$ tells us
that $\mu_{A_{n}}^{n}(I_{1})\leq\frac{k}{n}$. Therefore, if we choose
$C_{1}=\frac{1}{2}\rho_{sc}(2-\kappa)$, this event is superexponentially
unlikely by Proposition 3.7. The proof is completed by taking $C_{3}=2C_{1}$.

To check the last claim, we choose $C_{4}=4C_{2}/C_{1}$. We apply the first
claim and obtain
$\mu_{\frac{k}{C_{4}}}(\lambda_{i})\geq\frac{C_{1}C_{4}\sqrt{n}}{k}=4\frac{C_{2}\sqrt{n}}{k}\geq
4\mu_{k}(\lambda_{i})$ on an event with probability $1-e^{-\Omega(n)}$. ∎

We derive one more estimate, showing that it is very unlikely for
$\frac{\mu_{k}(\lambda_{i})}{\mu_{1}(\lambda_{i})}$ to be $\Omega(1)$ when $k$
is large enough.

######  Corollary 3.9.

In the setting of Corollary 3.8, for any
$\lambda_{i}\in[(-(2-\kappa)\sqrt{n},(2-\kappa)\sqrt{n}]$, any $c_{0}>0$,

$\mathbb{P}\left(\frac{\mu_{k}(\lambda_{i})}{\mu_{1}(\lambda_{i})}\geq
10^{-2}\text{ for any }k\geq c_{0}n\right)\leq e^{-\Omega(n)}.$ (3.11)

###### Proof.

By corollary 3.8, we only need to prove the following claim: for any fixed
constant $D>0$,

$\mathbb{P}(\mu_{1}(\lambda_{i})\leq Dn^{-1/2})=e^{-\Omega(n)}.$ (3.12)

To see this, observe that $\mu_{1}(\lambda_{i})\leq Dn^{-1/2}$ implies that
there is an interval of length $2D^{-1}\sqrt{n}$ around $\lambda_{i}$ on which
$A_{n}$ has no eigenvalue. By the convergence in Proposition 3.7, this event
is superexponentially unlikely. ∎

##  4\. Small ball probability estimates

In this section we estimate a crucial term in $I(\theta)$, the function
defined in (2.2) whose computations lead to the desired singular value bounds.
The following lemma is the main result of this section. The reasoning in its
formulation and proof are far more complicated than that in the one location
case ($d=1$ and $\lambda_{1}$=0) as we need to balance $\mu_{k}(\lambda_{j})$
for various $k$ and $j$. The eigenvalue rigidity estimates developed in the
previous section are crucial here.

######  Lemma 4.1.

Assume that $A_{n}$ satisfies the assumptions in Theorem 1.2 and assume the
random vector $X_{2}\sim\operatorname{Col}_{n}(\zeta_{2})$ and
$\zeta_{2}\in\Gamma_{2}(G,K,\sigma_{0})$. Fix any $\kappa>0$ and $\Delta>0$
that are sufficiently small. Then there exists an event $\mathcal{E}_{1}$ with
$\mathbb{P}(\mathcal{E}_{1})\geq 1-\exp(-\Omega(n))$ such that for any
$A_{n}\in\mathcal{E}_{1}$, the following holds:

Fix any given $(\theta_{1},\cdots,\theta_{d})\in\mathbb{R}^{d}$ with
$\prod_{i=1}^{d}|\theta_{i}|=1$ , and fix any given
$\lambda_{1},\cdots,\lambda_{d}\in[-(2-\kappa)\sqrt{n},(2-\kappa)\sqrt{n}]$
with $|\lambda_{i}-\lambda_{j}|\geq\Delta\sqrt{n}$ whenever $i\neq j$.

Then there exists some $J\in\\{1,\cdots,d\\}$ (depending on $A_{n}$ and
$(\theta_{1},\cdots,\theta_{d})$ but not on
$\widetilde{X}:=X_{2}-X_{2}^{\prime}$, where $X_{2}^{\prime}$ is an
independent copy of $X_{2}$) such that, for any

$s\in\left(0,\frac{C\cdot\mu_{k}(\lambda_{J})}{{\left(\prod_{i=1}^{d}\mu_{1}(\lambda_{i})\right)^{1/d}}}\right)$

and for any $k\leq c_{0}n$, we have

$\mathbb{P}_{\widetilde{X}}\left(\left\|\sum_{i=1}^{d}\frac{\theta_{i}}{\mu_{1}(\lambda_{i})}(A_{n}-\lambda_{i}I_{n})^{-1}\widetilde{X}\right\|_{2}\leq
s\right)\lesssim se^{-k},$ (4.1)

where $c_{0}$ and $C$ are universal constants that depend only on the various
parameters $G$,$B$,$\sigma_{0}$ and $K$.

Before providing the proof we provide several essential explanations. First,
the label $J$ in $\mu_{k}(\lambda_{J})$ is not truly important to us and we
will have very good control of it for any $J$, at any high power. However, the
appearance of the $d$-th square root of the product of $\mu_{1}(\lambda_{i})$
is of fundamental importance and our proof breaks down if we replace it by
$\mu_{1}(\lambda_{i})$ for some fixed $i$. Second, we find it convenient to
normalize the $(\theta_{1},\cdots,\theta_{d})$ via $\prod_{i}|\theta_{i}|=1$
rather than the more standard one of $\|\theta\|_{2}=1$, as our choice
captures information from all coordinates whereas the latter one loses
information when some $\theta_{i}$ is very small. Last, we are not very
careful in the power of $s$. One might expect a $s^{d}$ power, but this is
very hard to prove (and may not be true) and, more importantly, our decoupling
procedure loses a power $1/2$ so that even getting a $d$-th power is not
useful. We will use a different method to tame the singularity in $s$ in a
forthcoming integration (5.13).

To illustrate the main ideas, we first recall how to compute this expectation
with only one term $\lambda_{1}=0$. This is the content of [10], Chapter 9.
Rephrased in the setting here, we first prove that for any
$s\in(e^{-cn},\mu_{k}/\mu_{1})$ (where we abbreviate $\mu_{k}:=\mu_{k}(0)$),

$\mathbb{P}_{\widetilde{X}}\left(\|A^{-1}\widetilde{X}\|_{2}\leq
s\mu_{1}\right)\lesssim se^{-ck}.$

The idea is to expand

$\|A^{-1}\widetilde{X}|_{2}^{2}=\sum_{j=1}^{n}\mu_{j}^{2}\langle
v_{j},\widetilde{X}\rangle^{2}$

where $v_{j}$ is the eigenvector of $A^{-1}$ corresponding to $\mu_{j}$.

Then

$\mathbb{P}_{\widetilde{X}}(\|A^{-1}\widetilde{X}\|_{2}\mu_{1}^{-1}\leq
s)\leq\mathbb{P}_{\widetilde{X}}\left(|\langle v_{1},\widetilde{X}\rangle|\leq
s,\quad\sum_{j=2}^{k}\frac{\mu_{j}^{2}}{\mu_{1}^{2}}\langle
v_{j},\widetilde{X}\rangle^{2}\leq s^{2}\right).$

By the assumption on $\mu_{k}/\mu_{1}$, we further deduce that

$\mathbb{P}_{\widetilde{X}}(\|A^{-1}\widetilde{X}\|_{2}\mu_{1}^{-1}\leq
s)\leq\mathbb{P}_{\widetilde{X}}\left(|\langle v_{1},\widetilde{X}\rangle|\leq
s,\quad\sum_{j=2}^{k}\langle v_{j},\widetilde{X}\rangle^{2}\leq 1\right).$

The last term can be estimated via the novel inverse Littlewood-Offord
inequality in [10].

We face new challenges as we have $d$ different $\lambda_{i}$’s. We introduce
the following notation:

######  Definition 4.2.

Fix any distinct $\lambda_{1},\cdots,\lambda_{d}\in\mathbb{R}$. For any $i\neq
j\in\\{1,\cdots,d\\}$ and any $k\geq 1$ we denote by

$\mu_{c_{j}(i;k)}(\lambda_{j})$

the $c_{j}(i,k)$-th largest singular value of $(A_{n}-\lambda_{j}I_{n})^{-1}$
whose corresponding singular vector coincides with the singular vector of
$\mu_{k}(\lambda_{i})$, the $k$-th largest singular value of
$(A_{n}-\lambda_{i}I_{n})^{-1}.$

This definition makes sense because $(A_{n}-\lambda_{i}I_{n})^{-1}$ and
$(A_{n}-\lambda_{j}I_{n})^{-1}$ share the same set of singular vectors.

We need this notation to record how singular values labeled with respect to
$\lambda_{j}$ will affect the calculation of singular values labeled with
respect to $\lambda_{i}$.

The proof of Lemma 4.1 makes crucial use of the assumption that the random
vector $X_{2}$ has a bounded density with respect to the Lebesgue measure. We
will use this property via the following lemma taken from [21], Theorem 1.1.

######  Lemma 4.3.

Let $X_{1},\cdots,X_{n}$ be a family of independent real valued random
variables having densities bounded by $K$ with respect to the Lebesgue
measure. Denote by $X=(X_{1},\cdots,X_{n})$. For any $\ell\leq n$ and any
$V\in\mathbb{R}^{\ell\times n}$, $VX$ is an $\mathbb{R}^{\ell}$-valued random
variable with density bounded by

$\frac{e^{\ell/2}K^{\ell}}{\det(VV^{T})^{1/2}}.$

In our application we will take the $\ell$-rows of $V$ to be the $\ell$
orthonormal eigenvectors of $A_{n}$. This lemma replaces the much more
delicate Littlewood-Offord type arguments that work for discrete random
variables.

Now we are ready to prove Lemma 4.1.

###### Proof of Lemma 4.1.

We first expand the inner product in the following form, where
$v_{k}(\lambda_{i})$ denotes the singular vector associated with the singular
value $\mu_{k}(\lambda_{i}):$

$\begin{aligned}
&\left\|\sum_{i=1}^{d}\frac{\theta_{i}}{\mu_{1}(\lambda_{i})}(A_{n}-\lambda_{i}I_{n})^{-1}\widetilde{X}\right\|_{2}=\sum_{i=1}^{d}\left|\theta_{i}+\sum_{j\neq
i}\theta_{j}\frac{\mu_{c_{j}(i;1)(\lambda_{j})}}{\mu_{1}(\lambda_{j})}\right|^{2}\langle\widetilde{X},v_{1}(\lambda_{i})\rangle^{2}\\\
&+\sum_{i=1}^{d}\sum_{k\in\mathcal{A}(i),k\geq
2}\left|\theta_{i}\frac{\mu_{k}(\lambda_{i})}{\mu_{1}(\lambda_{i})}+\sum_{j\neq
i}\theta_{j}\frac{\mu_{c_{j}(i;k)(\lambda_{j})}}{\mu_{1}(\lambda_{j})}\right|^{2}\langle\widetilde{X},v_{k}(\lambda_{i})\rangle^{2}\end{aligned}.$
(4.2)

Here $\mathcal{A}(i)\subset\\{1,\cdots,n\\}$ are index sets for which we give
a descriptive construction as follows. We arrange without loss of generality
that $\lambda_{1}<\lambda_{2}<\cdots<\lambda_{d}$ on the real line, then
expand the inner product and write the corresponding weights on the site of
the eigenvector. The right hand sides of the first line of (4.2) are the hard
constraints, corresponding to singular vectors that are associated with the
least singular value of $A_{n}-\lambda_{i}I_{n}$ for some $i$. This will be
our major focus. The second line of (4.2) are the soft constraints, involving
singular vectors that do not correspond to the least singular values of any
$A_{n}-\lambda_{i}I_{n}$. For eigenvectors of $A_{n}$ whose eigenvalues are
close to $\lambda_{i}$222Recall again that $A_{n}$ and
$A_{n}-\lambda_{i}I_{n}$ share the same eigenvectors and singular vectors, we
collect these sums into the sum over $i$ part on the second line of (4.2) and
define $\mathcal{A}(i)\subset[2,cn]\cap\mathbb{Z}$ for some $c>0$ and each
$i$. This procedure can exhaust all eigenvectors of $A_{n}$ into $d$ disjoint
sums: those close to $\lambda_{i}$ are taken into the $i$-th sum, and we take
an arbitrary separation between $\lambda_{i}$ and $\lambda_{i+1}$ deciding on
which terms will be sent to the $i$-th sum and which will be sent to the
$i+1$-th sum. The size of $\mathcal{A}(i)$ is now very flexible.

As can be seen from the expression (4.2), the major complication is that there
will be many cancellations and we need to know which term is dominant and what
is left after all the additions and taking the absolute value.

For this purpose, we single out two special indices. Let
$I\in\\{1,\cdots,d\\}$ be such that

$|\theta_{I}|=\max\\{|\theta_{1}|,\cdots,|\theta_{d}|\\}$

and let $J\in\\{1,\cdots,d\\}$ be such that

$\frac{|\theta_{J}|}{\mu_{1}(\lambda_{J})}=\max\left\\{\frac{|\theta_{1}|}{\mu_{1}(\lambda_{1})},\cdots,\frac{|\theta_{d}|}{\mu_{1}(\lambda_{d})}\right\\}.$

First, by Corollary 3.9, we may assume that on an event with probability
$1-e^{-\Omega(n)}$, we have

$\frac{\mu_{c(I;1)(\lambda_{j})}}{\mu_{1}(\lambda_{j})}\leq 10^{-2}d^{-1}$

for any $j\neq I$, so that by definition of $I$,

$\left|\theta_{I}+\sum_{j\neq
I}\theta_{j}\frac{\mu_{c_{j}(i;1)(\lambda_{j})}}{\mu_{1}(\lambda_{j})}\right|\geq
0.9|\theta_{I}|\geq 0.9.$

Second, according to the second part of Corollary 3.8, in an event with
probability $1-e^{-\Omega(n)}$, we may find some $c_{0}>0$ depending only on
$\kappa$, $B$ and the log-Sobolev constant; thus, for any $k\leq c_{0}n$, we
have for any $j\neq J$,

$\mu_{k}(\lambda_{J})\geq 10d\mu_{c_{j}(J;k)}(\lambda_{j}).$

By definition of $J$, this implies that for any $k\leq c_{0}n$ and any $j\neq
J$,

$\theta_{J}\frac{\mu_{k}(\lambda_{J})}{\mu_{1}(\lambda_{J})}\geq
10d\theta_{j}\frac{\mu_{c_{j}(J,k)}(\lambda_{j})}{\mu_{1}(\lambda_{j})}.$

That is, for any $k\leq c_{0}n$,

$\left|\theta_{J}\frac{\mu_{k}(\lambda_{J})}{\mu_{1}(\lambda_{J})}+\sum_{j\neq
J}\theta_{j}\frac{\mu_{c_{j}(J,k)}(\lambda_{j})}{\mu_{1}(\lambda_{j})}\right|\geq
0.9\left|\theta_{J}\frac{\mu_{k}(\lambda_{J})}{\mu_{1}(\lambda_{J})}\right|.$

Applying both bounds to (4.2), we obtain

$\displaystyle\left\|\sum_{i=1}^{d}\frac{\theta_{i}}{\mu_{1}(\lambda_{i})}(A_{n}-\lambda_{i}I_{n})^{-1}\widetilde{X}\right\|_{2}\geq
0.9\langle\widetilde{X},v_{1}(\lambda_{I})\rangle^{2}+0.9\sum_{j=2}^{c_{0}n}\left|\theta_{J}\frac{\mu_{j}(\lambda_{J})}{\mu_{1}(\lambda_{J})}\right|^{2}\langle\widetilde{X},v_{j}(\lambda_{J})\rangle^{2}.$
(4.3)

We are now in the position to apply Lemma 4.3. By assumption $\widetilde{X}$
has bounded density. In the setting of Lemma 4.3, let $V$ be a matrix with
(orthogonal) rows given by $v_{1}(\lambda_{I})$ and $v_{k}(\lambda_{J})$,
$k=2,\cdots,c_{0}n$.

Then we have

$\mathbb{P}_{\widetilde{X}}\left(\left\|\sum_{i=1}^{d}\frac{\theta_{i}}{\mu_{1}(\lambda_{i})}(A_{n}-\lambda_{i}I_{n})^{-1}\widetilde{X}\right\|_{2}\leq
s\right)\lesssim se^{-k},$ (4.4)

for any $0\leq s\leq C|\theta_{J}|\mu_{k}(\lambda_{J})/\mu_{1}(\lambda_{J})$
and any $k\leq c_{0}n$, where $C$ is a constant depending on the density of
$X_{2}$. This is because the event in (4.4) can be decomposed as requiring

$\langle\widetilde{X},v_{1}(\lambda_{i})\rangle\lesssim s,\quad\text{ and
}\sum_{j=2}^{k}\left\|\theta_{J}\frac{\mu_{j}(\lambda_{J})}{\mu_{1}(\lambda_{J})}\right|^{2}\langle\widetilde{X},v_{j}(\lambda_{J})\rangle^{2}\lesssim
s^{2}$

for some appropriate $k\leq c_{0}n$.

The constant $C$ in the restriction on $s$ appears because we need a
sufficiently small constant factor depending on the density of $X$ to overcome
the $e^{{}^{\ell}/2}K^{\ell}$ factor in Lemma 4.3 and obtain the exponentially
small factor $e^{-k}$. We may typically take $C\leq\frac{1}{4\sqrt{e}K}$ where
$K$ is an upper bound on the density of $\widetilde{X}_{2}$.

Finally, by definition of $J$ and our normalization on $\theta$, we have

$|\theta_{J}|\frac{\mu_{k}(\lambda_{J})}{\mu_{1}(\lambda_{J})}\geq\mu_{k}(\lambda_{J})\left(\prod_{j=1}^{d}|\theta_{j}|\frac{1}{\mu_{1}(\lambda_{j})}\right)^{1/d}=\frac{\mu_{k}(\lambda_{J})}{\left(\prod_{j=1}^{d}\mu_{1}(\lambda_{j})\right)^{1/d}}.$

This completes the proof, and remarkably, our final bound does not depend on
$\theta$ saved for the label $J$ in $\mu_{k}(\lambda_{J})$.

Checking the whole proof, there are two instances where we consider an event
on $A_{n}$ that holds with probability $1-e^{-\Omega(n)}$. It suffices to take
$\mathcal{E}_{1}$ the intersection of these two events.

∎

We will also need the following lemma which is very similar to Lemma 4.1, but
addresses a different geometric configuration.

######  Lemma 4.4.

Assume that $A_{n}$ satisfies assumptions in Theorem 1.2 and
$X_{2}\sim\operatorname{Col}_{n}(\zeta_{2})$,
$\zeta_{2}\in\Gamma_{2}(G,K,\sigma_{0})$. Fix any $\kappa>0$ and $\Delta>0$
that are sufficiently small. Then there exists an event $\mathcal{E}_{2}$ with
$\mathbb{P}(\mathcal{E}_{2})\geq 1-\exp(-\Omega(n))$ such that for any
$A\in\mathcal{E}_{2}$, the following holds:

Fix any given $(\theta_{1},\cdots,\theta_{d})\in\mathbb{R}^{d}$, assume that
we can find some $\mathcal{A}\subset\\{1,\cdots,d\\}$ satisfying:
$|\mathcal{A}|=\ell$ for some $1\leq\ell\leq d-1$, that
$\prod_{i\in\mathcal{A}}|\theta_{i}|=1$ and for any $j\notin\mathcal{A}$,
$|\theta_{j}|<1$. Fix any given
$\lambda_{1},\cdots,\lambda_{d}\in[-(2-\kappa)\sqrt{n},(2-\kappa)\sqrt{n}]$
satisfying $|\lambda_{i}-\lambda_{j}|\geq\Delta\sqrt{n}$ whenever $i\neq j$.

Then there exist some $J\in\\{1,\cdots,d\\}$ (depending on $A_{n}$ and
$(\theta_{1},\cdots,\theta_{d})$ but not on $\widetilde{X}$) such that, for
any

$s\in\left(0,\frac{C\cdot\mu_{k}(\lambda_{J})}{{\left(\prod_{i\in\mathcal{A}}\mu_{1}(\lambda_{i})\right)^{1/\ell}}}\right)$

and for any $k\leq c_{0}n$, we have

$\mathbb{P}_{\widetilde{X}}\left(\left\|\sum_{i=1}^{d}\frac{\theta_{i}}{\mu_{1}(\lambda_{i})}(A_{n}-\lambda_{i}I_{n})^{-1}\widetilde{X}\right\|_{2}\leq
s\right)\lesssim se^{-k},$ (4.5)

where $c_{0}$ and $C$ are universal constants that depend only on the various
parameters $G$,$B$,$\sigma_{0}$ and $K$.

###### Proof.

We follow exactly the same line of proof as Lemma 4.1 (defining $I$ and $J$ in
the same way and performing the same estimates). The only places to change are
at the end: we use $|\theta_{I}|\geq 1$ and that

$|\theta_{J}|\frac{\mu_{k}(\lambda_{J})}{\mu_{1}(\lambda_{J})}\geq\mu_{k}(\lambda_{J})\left(\prod_{j\in\mathcal{A}}|\theta_{j}|\frac{1}{\mu_{1}(\lambda_{j})}\right)^{1/\ell}\geq\frac{\mu_{k}(\lambda_{J})}{\left(\prod_{j\in\mathcal{A}}\mu_{1}(\lambda_{j})\right)^{1/\ell}}.$

∎

##  5\. Initial estimate: two locations

In the next three sections we assume for the sake of simplicity that $d=2$,
i.e. we have only two locations $\lambda_{1}\neq\lambda_{2}$. This approach
will greatly simplify the computations and make the main ideas more
transparent. The main result of this chapter is the following lemma:

######  Lemma 5.1.

Let $A_{n}$ satisfy the assumptions of Theorem 1.2. Fix any $\kappa>0$,
$\Delta>0,$ and any two
$\lambda_{1},\lambda_{2}\in[(-(2-\kappa)\sqrt{n},(2-\kappa)\sqrt{n}]$ with
$|\lambda_{1}-\lambda_{2}|\geq\Delta\sqrt{n}$. Then for any
$\delta_{1},\delta_{2}\geq e^{-cn}$, any $u\in\mathbb{R}^{n}$ with
$\|u\|_{2}\leq 2$, and any $p>0$,

$\displaystyle\mathbb{E}_{A_{n}}\sup_{r_{1},r_{2}}\mathbb{P}_{X}\left(\frac{|\langle(A_{n}-\lambda_{i}I_{n})^{-1}X,X\rangle-
r_{i}|}{\|(A_{n}-\lambda_{i}I_{n})^{-1}\|_{*}}\leq\delta_{i},\langle
X,u\rangle\geq
s,\frac{\mu_{1}(\lambda_{1})\mu_{1}(\lambda_{2})}{n}\leq(\delta_{1}\delta_{2})^{-p}\right)$
(5.1) $\displaystyle\lesssim
e^{-s}\delta_{1}\delta_{2}+e^{-s}\delta_{1}\delta_{2}\mathbb{E}\left[\left(\frac{\mu_{1}(\lambda_{1})\mu_{1}(\lambda_{2})}{n}\right)^{9/10}\bigm{|}\frac{\mu_{1}(\lambda_{1})\mu_{1}(\lambda_{2})}{n}\leq(\delta_{1}\delta_{2})^{-p}\right]^{80/81}+e^{-\Omega(n)},$

where $c$ depends on various constants in the assumption of Theorem 1.2, on
$\kappa$ and $\Delta$.

In future applications we will set $p>1$ to be a constant sufficiently close
to 1.

###  5.1. Initial decomposition

We now explicitly compute the integral of $I(\theta)$ over the specified
region. Thanks to Theorem 2.1, this is the major step in estimating the least
singular values of $A_{n}$.

We first apply Hölder’s inequality and get

$I(\theta)\lesssim\left(\mathbb{E}_{X_{2},X_{2}^{\prime}}e^{9\langle
X_{2}+X_{2}^{\prime},u\rangle}\right)^{1/9}\left(\mathbb{E}_{\widetilde{X}}e^{-c^{\prime\prime}\|\sum_{i=1}^{2}\frac{\theta_{i}}{\mu_{1}(\lambda_{i})}(A_{n}-\lambda_{i}I_{n})^{-1}\widetilde{X}\|_{2}^{2}}\right)^{\frac{8}{9}}.$
(5.2)

The first term on the right is $O(1)$. We can deduce the remaining estimates
as follows:

$\displaystyle
I(\theta)^{9/8}\lesssim_{B}\mathbb{E}_{\widetilde{X}}e^{-c^{\prime\prime}\|\sum_{i=1}^{2}\frac{\theta_{i}}{\mu_{1}(\lambda_{i})}(A_{n}-\lambda_{i}I_{n})^{-1}\widetilde{X}\|_{2}^{2}}$
$\displaystyle\lesssim\begin{cases}1&|\theta_{1}|<1,|\theta_{2}|<1,\\\
e^{-c^{\prime\prime}|\theta_{1}|^{1/5}}+\mathbb{P}_{\widetilde{X}}\left(\left\|\sum_{i=1}^{2}\frac{\theta_{i}}{\mu_{1}(\lambda_{i})}(A_{n}-\lambda_{i}I_{n})^{-1}\widetilde{X}\right\|_{2}\leq|\theta_{1}|^{\frac{1}{10}}\right),&|\theta_{1}|\geq
1,|\theta_{2}|<1\\\
e^{-c^{\prime\prime}|\theta_{2}|^{1/5}}+\mathbb{P}_{\widetilde{X}}\left(\left\|\sum_{i=1}^{2}\frac{\theta_{i}}{\mu_{1}(\lambda_{i})}(A_{n}-\lambda_{i}I_{n})^{-1}\widetilde{X}\right\|_{2}\leq|\theta_{2}|^{\frac{1}{10}}\right),&|\theta_{1}|<1,|\theta_{2}|\geq
1\\\
e^{-c^{\prime\prime}|\theta_{1}\theta_{2}|^{1/11}}+\mathbb{P}_{\widetilde{X}}\left(\left\|\sum_{i=1}^{2}\frac{\theta_{i}}{\mu_{1}(\lambda_{i})}(A_{n}-\lambda_{i}I_{n})^{-1}\widetilde{X}\right\|_{2}\leq|\theta_{1}\theta_{2}|^{\frac{1}{22}}\right)&|\theta_{1}|\geq
1,|\theta_{2}|\geq 1\end{cases}$

We split the integration of $I(\theta)^{1/2}$ over the specified region into
three terms, noticing that the four functions $1$,
$e^{-c^{\prime\prime}|\theta_{1}|^{1/5}}$,
$e^{-c^{\prime\prime}|\theta_{2}|^{1/5}}$ and
$e^{-c^{\prime\prime}|\theta_{1}\theta_{2}|^{1/11}}$ integrate into $O(1)$ on
the respective regions:

$\displaystyle\int_{\sum_{i}|\theta_{i}\delta_{i}|^{2}\leq
1}I(\theta)^{1/2}d\theta$ (5.3) $\displaystyle\lesssim
1+\int_{|\theta_{1}|\leq
1,1\leq|\theta_{2}|\leq\delta_{2}^{-1}}\mathbb{P}_{\widetilde{X}}(\|\sum_{i=1}^{2}\frac{\theta_{i}}{\mu_{1}(\lambda_{i})}(A_{n}-\lambda_{i}I_{n})^{-1}\widetilde{X}\|\leq|\theta_{2}|^{\frac{1}{10}})^{4/9}d\theta$
$\displaystyle+\int_{1\leq|\theta_{1}|\leq\delta_{1}^{-1},|\theta_{2}|\leq
1}\mathbb{P}_{\widetilde{X}}(\|\sum_{i=1}^{2}\frac{\theta_{i}}{\mu_{1}(\lambda_{i})}(A_{n}-\lambda_{i}I_{n})^{-1}\widetilde{X}\|\leq|\theta_{1}|^{\frac{1}{10}})^{4/9}d\theta$
$\displaystyle+\int_{1\leq|\theta_{1}|\leq\delta_{1}^{-1},1\leq|\theta_{2}|\leq\delta_{2}^{-1}}\mathbb{P}_{\widetilde{X}}(\|\sum_{i=1}^{d}\frac{\theta_{i}}{\mu_{1}(\lambda_{i})}(A_{n}-\lambda_{i}I_{n})^{-1}\widetilde{X}\|\leq(\theta_{1}\theta_{2})^{\frac{1}{22}})^{4/9}d\theta$
$\displaystyle:=1+I_{1}+I_{2}+I_{3}.$

Informally speaking, the integrals $I_{1}$ and $I_{2}$ represent terms that
rely essentially on one location $\lambda_{i}$, and the integral $I_{3}$
consists of terms that rely genuinely on both locations.

To estimate $I_{1}$ and $I_{2}$ we can simply reduce ourselves to the $d=1$
setting, while estimating $I_{3}$ requires fundamentally different ideas and
will be the major technical difficulty.

###  5.2. Two preparatory results

We recall the following simple linear algebra property: for any $n\times n$
matrix $M_{1},\cdots,M_{d}$,

$\sigma_{min}(M_{1}\cdots
M_{d})\geq\sigma_{min}(M_{1})\cdots\sigma_{min}(M_{d}).$ (5.4)

Thanks to this lemma, we prove the following:

######  Lemma 5.2.

Given any $\sigma>0$ and any $\tau\in(0,1],$ let $M_{1},\cdots,M_{d}$ be
$n\times n$ random matrices (not necessarily independent) that satisfy, for
any $\delta_{1},\cdots,\delta_{d}>0$,

$\mathbb{P}(\sigma_{min}(M_{1})\leq\delta_{1}n^{-1/2},\cdots,\sigma_{min}(M_{d})\leq\delta_{d}n^{-1/2})\leq(C\delta_{1}\cdots\delta_{d})^{\tau}+e^{-cn^{\sigma}},$
(5.5)

and more generally for any $k=1,2,\cdots,d-1$ and any $1\leq
i_{1}<i_{2}<\cdots<i_{k}\leq d$, we have

$\mathbb{P}(\sigma_{min}(M_{i_{1}})\leq\delta_{i_{1}}n^{-1/2},\cdots,\sigma_{min}(M_{i_{k}})\leq\delta_{i_{k}}n^{-1/2})\leq
C(\delta_{i_{1}}\cdots\delta_{i_{k}})^{\tau}+e^{-cn^{\sigma}}.$ (5.6)

Then for any $\delta>0$, we have

$\mathbb{P}\left((\sigma_{min}(M_{1}\cdots M_{d}))^{1/d}\leq\delta
n^{-1/2}\right)\leq C(\delta^{\tau}\log(\delta^{-1}))^{d}+e^{-cn^{\sigma}},$
(5.7)

and we have

$\mathbb{P}\left((\sigma_{min}(M_{1})\cdots\sigma_{min}(M_{d}))^{1/d}\leq\delta
n^{-1/2}\right)\leq C(\delta^{\tau}\log(\delta^{-1}))^{d}+e^{-cn^{\sigma}},$

where $C$ and $c$ are universal constants.

###### Proof.

Assume that $\frac{1}{2}\geq\delta\geq e^{-cn^{\sigma}}$; otherwise, the claim
is trivial.

We decompose $[\delta^{d},1]$ into dyadic intervals

$[\delta^{d},1]=\cup_{j=1}^{L_{\delta}}[I_{j,S},I_{j,L}]$

where for each $j\geq 2$, we assume $I_{j,L}/I_{j,S}=2$ and we assume $1\leq
I_{1,L}/I_{1,S}\leq 2$. Then it is elementary to check that $L_{\delta}\leq
C_{d}\log\delta^{-1}$.

We consider three separate cases: (a) either for some $i$,
$\sigma_{min}(M_{i})\geq n^{-1/2}$, then the event $\sigma_{min}(M_{1}\cdots
M_{d})\leq\delta^{d}n^{-d/2}$ implies
$\sigma_{min}(M_{1})\cdots\sigma_{min}(M_{d})\leq\delta^{d}n^{-d/2}$, so that
$\prod_{j\neq i}\sigma_{min}(M_{j})\leq\delta^{d}n^{-(d-1)/2}$. Thus we can
safely discard all subscripts $i$ such that $\sigma_{min}(M_{i})\geq
n^{-1/2}$, and we get to one of the following two cases.

Then consider case (b): for some $i$ we have
$\sigma_{min}(\lambda_{i})\leq\delta^{d}$. The possibility of this event can
be bounded via assumption (5.6), which directly completes the proof.

Then, we consider cases (c), where case (a) and (b) do not occur.

The event $\sigma_{min}(M_{1}\cdots M_{d})\leq\delta^{d}n^{-d/2}$ implies
$\sigma_{min}(M_{1})\cdots\sigma_{min}(M_{d})\leq\delta^{d}n^{-d/2}$ by (5.4),
which is contained in the union of $L_{\delta}^{d}$ many events, each given by

$\sigma_{min}(M_{1})\leq I_{j_{1},L}n^{-1/2},\cdots\sigma_{min}(M_{1})\leq
I_{j_{d},L}n^{-1/2},\quad\prod_{i=1}^{d}I_{j_{i},L}\leq 2^{d}\delta^{d}.$

This can be checked via considering all events $\sigma_{min}(M_{i})\leq
x_{i}n^{-1/2},\cdots,$ $i=1,\cdots,d$, and finding the interval
$[I_{j_{i},s},I_{j_{i},L}]$ where $x_{i}$ lies. By assumption of case (c),
$x_{i}$ must lie in one of these events for each $i$, so the claim holds. Then
the lemma follows from taking a union bound and applying assumption 5.5. ∎

In our initial iteration, we will make direct use of the optimal singular
value estimates of subGaussian symmetric matrices in [10]. We will need a
version of such estimates at any location in the bulk, while [10] states the
singular value estimate at $0$. Indeed, it is not difficult to generalize the
main result of [10] to these locations, and we state it as follows:

######  Proposition 5.3.

Consider random matrix $A_{n}$ satisfying the assumption of Theorem 1.2, Fix
any $\kappa>0$, then the following estimate holds uniformly for all
$\lambda\in[-(2-\kappa)\sqrt{n},(2-\kappa)\sqrt{n}]$: for any $\epsilon>0$,

$\mathbb{P}(\sigma_{min}(A_{n}-\lambda I_{n})\leq\epsilon n^{-1/2})\leq
c\epsilon+e^{-cn},$ (5.8)

where $c$ only depends on $B$ and $\kappa$.

We believe this generalization is very straightforward and that there is no
need to write out a proof. Essentially, one only needs to repeat every step of
the proof in [10] and one needs only to use the local law estimate at generic
locations (see Section 3.1) to replace the one at $0$. A subtlety is that we
assume that the diagonal elements $A_{ii}$ have a different variance but this
causes no harm as we assume entries have a continuous distribution and do not
invoke the Littlewood-Offord theorem. Alternatively, the rest of this paper,
taking only one location $d=1$, can be regarded as a proof of this
proposition, so we do not bother to write it out again.

###  5.3. Estimating essentially 1-d terms

The computations in this section are very similar to those in [10], Section 9
and Section 10, reflecting that $I_{1}$ and $I_{2}$ are essentially 1-d
objects.

We begin with the $I_{1}$ term, recall that

$I_{1}=\int_{|\theta_{1}|\leq
1,1\leq|\theta_{2}|\leq\delta_{2}^{-1}}\mathbb{P}_{\widetilde{X}}(\|\sum_{i=1}^{2}\frac{\theta_{i}}{\mu_{1}(\lambda_{i})}(A_{n}-\lambda_{i}I_{n})^{-1}\widetilde{X}\|\leq|\theta_{2}|^{\frac{1}{10}})^{4/9}d\theta.$

We bound

$\displaystyle I_{1}$ $\displaystyle=\int_{|\theta_{1}|\leq
1,1\leq|\theta_{2}|\leq\delta_{2}^{-1}}\mathbb{P}_{\widetilde{X}}\left(\|\sum_{i=1}^{2}\frac{\theta_{i}/\theta_{2}}{\mu_{1}(\lambda_{i})}(A_{n}-\lambda_{i}I_{n})^{-1}\widetilde{X}\|\leq|\theta_{2}|^{-\frac{9}{10}}\right)^{4/9}d\theta$
$\displaystyle\lesssim\int_{1}^{\delta_{2}^{-1}}\sup_{|\theta_{1}|\leq
1,|\theta_{2}|=1}\mathbb{P}_{\widetilde{X}}\left(\|\sum_{i=1}^{2}\frac{\theta_{i}}{\mu_{1}(\lambda_{i})}(A_{n}-\lambda_{i}I_{n})^{-1}\widetilde{X}\|\leq
s^{-\frac{9}{10}}\right)^{4/9}ds$
$\displaystyle\leq\int_{\delta_{2}}^{1}s^{-19/9}\sup_{|\theta_{1}|\leq
1,|\theta_{2}|=1}\mathbb{P}_{\widetilde{X}}\left(\|\sum_{i=1}^{2}\frac{\theta_{i}}{\mu_{1}(\lambda_{i})}(A_{n}-\lambda_{i}I_{n})^{-1}\widetilde{X}\|\leq
s\right)^{4/9}ds.$

Now we are ready to apply Lemma 4.4. First, we note that the conclusion of 4.4
is independent of $\theta$, except for the subscript $J\in\\{1,2\\}$ which
depends only on $A_{n}$ and the relative ratios of $\theta_{1}$ and
$\theta_{2}$. To remedy this, in the following we take both cases into
account, i.e. we decompose the range of $s$ both by taking $J=1$ and $J=2$. To
put things on a more concrete ground, let $\sum_{1}$ and $\sum_{2}$ be subsets
of the parameter space $(\theta_{1},\theta_{2})$, $|\theta_{1}|\leq 1$ and
$|\theta_{2}|=1$, such that on $\sum_{\ell}$, Lemma 4.4 yields $J=\ell$. Then,
we write

$I_{1}\lesssim\sum_{\ell=1}^{2}\int_{\delta_{2}}^{1}s^{-19/9}\sup_{(\theta_{1},\theta_{2})\in\sum_{\ell}}\mathbb{P}_{\widetilde{X}}\left(\|\sum_{i=1}^{2}\frac{\theta_{i}}{\mu_{1}(\lambda_{i})}(A_{n}-\lambda_{i}I_{n})^{-1}\widetilde{X}\|\leq
s\right)^{4/9}ds.$

We decompose
$[\delta_{2},1]=[\delta_{2},\frac{\mu_{c_{0}n}(\lambda_{2})}{\mu_{1}(\lambda_{2})}]\cup\cup_{k=2}^{cn}[\frac{\mu_{k}(\lambda_{2})}{\mu_{1}(\lambda_{2})},\frac{\mu_{k-1}(\lambda_{2})}{\mu_{1}(\lambda_{2})}]$
when $(\theta_{1},\theta_{2})\in\sum_{2}$ and we decompose
$[\delta_{2},1]=[\delta_{2},\frac{\mu_{c_{0}n}(\lambda_{1})}{\mu_{1}(\lambda_{2})}]\cup\cup_{k=2}^{cn}[\frac{\mu_{k}(\lambda_{1})}{\mu_{1}(\lambda_{2})},\frac{\mu_{k-1}(\lambda_{1})}{\mu_{1}(\lambda_{2})}]$
when $(\theta_{1},\theta_{2})\in\sum_{1}$. (When $\delta_{2}$ is not small
enough so that some of these intervals are not well-defined, we simply neglect
these intervals: this approach will create no loss as shown in the forthcoming
proofs. Additionally, when $\mu_{k}(\lambda_{1})/\mu_{1}(\lambda_{2})>1$ for
some $k$, we also neglect such intervals without loss). Then by Lemma 4.4, we
have

$\displaystyle I_{1}$
$\displaystyle\lesssim\sum_{\ell=1}^{2}\sum_{k=1}^{cn}\int_{\mu_{k}(\lambda_{\ell})/\mu_{1}(\lambda_{2})}^{\mu_{k-1}(\lambda_{\ell})/\mu_{1}(\lambda_{2})}e^{-cn}s^{-19/9+4/9}ds+\int_{\delta}^{\mu_{cn}(\lambda_{\ell})/\mu_{1}(\lambda_{2})}e^{-cn}s^{-19/9+4/9}ds$
(5.9)
$\displaystyle\leq\sum_{\ell=1}^{2}\sum_{k=1}^{cn}e^{-k}(\mu_{1}(\lambda_{2})/\mu_{k}(\lambda_{\ell}))^{2/3}+2e^{-cn}\delta^{-3/2}$

where the last term is $e^{-\Omega(n)}$ when $\delta>e^{-cn}$. Similarly, we
have

$I_{2}\lesssim\sum_{\ell=1}^{2}\sum_{k=1}^{cn}e^{-k}(\mu_{1}(\lambda_{1})/\mu_{k}(\lambda_{\ell}))^{2/3}+e^{-\Omega(n)}.$
(5.10)

Before concluding, we prove the following very important estimate, whose
utility will be clear afterwards. The proof incorporates both the eigenvalue
rigidity estimates in Section 3.1 and the one-location singular value estimate
in Proposition 5.3, essentially proven in [10].

######  Lemma 5.4.

For any $B>0,$ let $\zeta\in\Gamma_{B}$ have a finite log-Sobolev constant,
and $A_{n}\sim\operatorname{Sym}_{n}(\zeta)$. For any
$\delta_{1},\delta_{2}\geq e^{-cn}$, define

$\mathcal{E}(\delta_{1}\delta_{2}):=\left\\{\frac{\mu_{1}(\lambda_{1})}{\sqrt{n}}\leq(\delta_{1}\delta_{2})^{-1},\quad\frac{\mu_{1}(\lambda_{2})}{\sqrt{n}}\leq(\delta_{1}\delta_{2})^{-1}\right\\}.$

Then for any $p>0$,

$\mathbb{E}_{A_{n}}^{\mathcal{E}(\delta_{1}^{p}\delta_{2}^{p})}\left[\prod_{r=1}^{2}\frac{\|(A_{n}-\lambda_{r}I_{n})^{-1}\|_{*}}{\mu_{1}(\lambda_{r})}\sum_{\ell_{1}=1}^{2}\sum_{\ell_{2}=1}^{2}\sum_{k=1}^{cn}e^{-k}\left(\frac{\mu_{1}(\lambda_{\ell_{1}})}{\mu_{k}(\lambda_{\ell_{2}})}\right)^{2/3}+e^{-\Omega(n)}\right]\lesssim
1.$ (5.11)

###### Proof.

Let
$\mathcal{E}_{0}:=\mathcal{E}_{1}\cap\mathcal{E}_{2}\cap\mathcal{E}(\delta_{1}^{p}\delta_{2}^{p})$,
where $\mathcal{E}_{1}$ and $\mathcal{E}_{2}$ are defined in Lemma 4.1 and
4.4. We may safely work with $\mathcal{E}_{0}$ since the two events added have
a probability being $1-e^{-\Omega(n)}$. For any fixed $\ell_{1},\ell_{2}$ we
first estimate via Hölder’s inequality

$\displaystyle\mathbb{E}_{A_{n}}^{\mathcal{E}_{0}}\prod_{r=1}^{2}\frac{\|(A_{n}-\lambda_{r}I_{n})^{-1}\|_{*}}{\mu_{1}(\lambda_{r})}\left(\frac{\mu_{1}(\lambda_{\ell_{1}})}{\mu_{k}(\lambda_{\ell_{2}})}\right)^{2/3}$
$\displaystyle\leq\prod_{r=1}^{2}\mathbb{E}_{A_{n}}^{\mathcal{E}_{0}}\left[\left(\frac{\|(A_{n}-\lambda_{r}I_{n})^{-1}\|_{*}}{\mu_{1}(\lambda_{r})}\right)^{28}\right]^{1/28}$
$\displaystyle\quad\cdot\mathbb{E}_{A_{n}}^{\mathcal{E}_{0}}\left[(\frac{\sqrt{n}}{k\mu_{k}(\lambda_{\ell_{1}})})^{28/3}\right]^{1/14}\mathbb{E}_{A_{n}}^{\mathcal{E}_{0}}\left[(\frac{\mu_{1}(\lambda_{\ell_{2}})}{\sqrt{n}})^{7/9}\right]^{6/7}\cdot
k^{2/3}$ $\displaystyle\lesssim
k\mathbb{E}_{A_{n}}^{\mathcal{E}_{0}}\left[(\frac{\mu_{1}(\lambda_{\ell_{2}})}{\sqrt{n}})^{7/9}\right]^{6/7}$

where we use Lemma 3.1 and Lemma 3.2 to show that the first two terms are
$O(1)$.

Therefore we have shown that

$\text{The left hand side of
}\eqref{6.3wowsog}\lesssim\mathbb{E}_{A_{n}}^{\mathcal{E}_{0}}\left[(\frac{\mu_{1}(\lambda_{1})}{\sqrt{n}})^{7/9}+(\frac{\mu_{1}(\lambda_{2})}{\sqrt{n}})^{7/9}\right]+e^{-\Omega(n)}.$
(5.12)

The final estimate is performed using Proposition 5.3. We bound

$\displaystyle\mathbb{E}_{A_{n}}^{\mathcal{E}_{0}}[(\frac{\mu_{1}(\lambda_{1})}{\sqrt{n}})^{7/9}]$
$\displaystyle\lesssim
1+\int_{1}^{(\delta_{1}\delta_{2})^{-7p/9}}\mathbb{P}(\mu_{1}(\lambda_{1}\leq
s^{9/7}\sqrt{n})ds$ $\displaystyle\lesssim
1+\int_{1}^{(\delta_{1}\delta_{2})^{-7p/9}}(s^{-9/7}+e^{-cn})ds\lesssim 1,$

where the second line follows from Proposition 5.3. The same computation holds
for $\mu_{1}(\lambda_{2})$, thus completing the proof of the lemma. ∎

###  5.4. Estimating genuinely 2-d terms

In this section we bound $I_{3}$. Recall that

$I_{3}=\int_{1\leq|\theta_{1}|\leq\delta_{1}^{-1},1\leq|\theta_{2}|\leq\delta_{2}^{-1}}\mathbb{P}_{\widetilde{X}}\left(\|\sum_{i=1}^{2}\frac{\theta_{i}}{\mu_{1}(\lambda_{i})}(A_{n}-\lambda_{i}I_{n})^{-1}\widetilde{X}\|\leq(\theta_{1}\theta_{2})^{\frac{1}{22}}\right)^{4/9}d\theta.$

First we normalize the probability inside so that $\theta_{1}\theta_{2}=1$.
That is,

$I_{3}=\int_{1}^{1/\sqrt{\delta_{1}\delta_{2}}}\int_{|\theta_{1}\theta_{2}|=s^{2},1\leq|\theta_{i}|}\mathbb{P}_{\widetilde{X}}\left(\|\sum_{i=1}^{2}\frac{\theta_{i}(A_{n}-\lambda_{i}I_{n})^{-1}\widetilde{X}}{\mu_{1}(\lambda_{i})\sqrt{\theta_{1}\theta_{2}}}\|\leq
s^{-\frac{10}{11}}\right)^{4/9}ds.$

We will use Lemma 4.1 to estimate the probability inside. Again, the bound
therein is independent of the precise ratio of $\theta_{1},\theta_{2}$ (after
normalizing $\theta_{1}\theta_{2}=1$) saved for the subscript $J$. We again
define $\sum_{1}$, $\sum_{2}$ the complementary subsets of the hyperplane
$|\theta_{1}\theta_{2}|=1$ so that on $\sum_{1}$, Lemma 4.1 yields $J=1$ and
on $\sum_{2}$, Lemma 4.1 yields $J=2$ (note that $\sum_{1},\sum_{2}$ are also
determined by $A_{n}$). Then we further bound, noting that we now normalize
$|\theta_{1}\theta_{2}|=1:$

$I_{3}\lesssim\int_{1}^{1/\sqrt{\delta_{1}\delta_{2}}}s\ln
s\sum_{\ell=1}^{2}\sup_{(\theta_{1},\theta_{2})\in\sum_{\ell}}\mathbb{P}_{\widetilde{X}}\left(\|\sum_{i=1}^{2}\frac{\theta_{i}}{\mu_{1}(\lambda_{i})}(A_{n}-\lambda_{i}I_{n})^{-1}\widetilde{X}\|\leq
s^{-\frac{10}{11}}\right)^{4/9}ds.$

We explain the factor $s\ln s$ here: for any $s>1$ the area of the region

$(\theta_{1},\theta_{2})\in\mathbb{R}^{2}:|\theta_{1}\theta_{2}|\leq
s^{2},|\theta_{1}|\geq 1,|\theta_{2}|\geq 1$

can be computed via
$A_{2}(s):=4\int_{1}^{s^{2}}(\frac{s^{2}}{y}-1)dy=4(s^{2}\ln s^{2}-s^{2}+1),$
and $\frac{d}{ds}A_{2}(s)=16s\ln s$. Thus we obtain an additional $16s\ln s$
factor after we change the coordinates $(\theta_{1},\theta_{2})\to
s=\sqrt{\theta_{1}\theta_{2}}$.

Changing the coordinates the second time, we obtain

$I_{3}\lesssim\sum_{\ell=1}^{2}\int_{\sqrt{\delta_{1}\delta_{2}}}^{1}s^{-32/10}\ln
s^{-1}\sup_{(\theta_{1},\theta_{2})\in\sum_{i}}\mathbb{P}_{\widetilde{X}}\left(\|\sum_{i=1}^{2}\frac{\theta_{i}}{\mu_{1}(\lambda_{i})}(A_{n}-\lambda_{i}I_{n})^{-1}\widetilde{X}\|\leq
s\right)^{4/9}ds.$ (5.13)

Now we use lemma 4.1 and decompose, taking $J=1$ on $\sum_{1}$ and $J=2$ on
$\sum_{2}$:

$[\sqrt{\delta_{1}\delta_{2}},1]=\left[\sqrt{\delta_{1}\delta_{2}},\frac{\mu_{cn}(\lambda_{J})}{\sqrt{\mu_{1}(\lambda_{1})\mu_{1}(\lambda_{2}})}\right]\cup\bigcup_{k=2}^{cn}\left[\frac{\mu_{k}(\lambda_{J})}{\sqrt{\mu_{1}(\lambda_{1})\mu_{1}(\lambda_{2})}},\frac{\mu_{k-1}(\lambda_{J})}{\sqrt{\mu_{1}(\lambda_{1})\mu_{1}(\lambda_{2}})}\right].$
(5.14)

Note: if we already have
$\frac{\mu_{k-1}(\lambda_{J})}{\sqrt{\mu_{1}(\lambda_{1})\mu_{1}(\lambda_{2}})}\geq
1$, then we terminate the right end of the interval at 1; if the whole
interval lies on the right hand side of 1 then we discard that interval.

Applying Lemma 4.1, and using $s^{-3.2+4/9}\log s^{-1}\leq s^{-25/9}$ for
$s\leq 1$, we obtain

$I_{3}\lesssim\sum_{\ell=1}^{2}\sum_{k=2}^{cn}e^{-k}\int_{\frac{\mu_{k}(\lambda_{\ell})}{\sqrt{\mu_{1}(\lambda_{1})\mu_{1}(\lambda_{2}})}}^{\frac{\mu_{k-1}(\lambda_{\ell})}{\sqrt{\mu_{1}(\lambda_{1})\mu_{1}(\lambda_{2}})}}s^{-25/9}ds+\sum_{\ell=1}^{2}e^{-cn}\int_{\sqrt{\delta_{1}\delta_{2}}}^{\frac{\mu_{k-1}(\lambda_{\ell})}{\sqrt{\mu_{1}(\lambda_{1})\mu_{1}(\lambda_{2}})}}s^{-25/9}ds.$

The second term on the right hand side evaluates to
$e^{-cn}(\sqrt{\delta_{1}\delta_{2}})^{-16/9},$ which is $e^{-\Omega(n)}$ if
we assume $\delta\delta_{2}\geq e^{-c^{\prime}n}$ for some $c^{\prime}>0$. For
the first term, we integrate and obtain

$I_{3}\lesssim\sum_{\ell=1}^{2}\sum_{k=2}^{cn}e^{-k}\left(\frac{\sqrt{\mu_{1}(\lambda_{1})\mu_{1}(\lambda_{2})}}{\mu_{k}(\lambda_{\ell})}\right)^{16/9}+e^{-\Omega(n)}.$
(5.15)

At this point notice that each individual $\mu_{i}(\lambda_{1}),i=1,2$ has a
power of $\frac{8}{9}<1$, but the overall power is greater than one. In the
next section we will use a much finer estimate than simply applying Hölder’s
inequality, to obtain an effective bound of $I_{3}$.

In the next lemma we eliminate the $\mu_{k}(\lambda_{\ell})$ term.

######  Lemma 5.5.

For any $B>0$, and any $\zeta\in\Gamma_{B}$ having a finite log-Sobolev
constant, consider the random matrix $A_{n}\sim\operatorname{Sym}_{n}(\zeta)$.
For any $\delta_{1},\delta_{2}\geq e^{-c^{\prime\prime}n}$ and any $p>0$
define

$\mathcal{E}(p,\delta_{1}\delta_{2}):=\left\\{\frac{\mu_{1}(\lambda_{1})\mu_{1}(\lambda_{2})}{n}\leq(\delta_{1}\delta_{2})^{-p}\right\\}.$

Then

$\displaystyle\mathbb{E}_{A_{n}}^{\mathcal{E}(p,\delta_{1}\delta_{2})}$
$\displaystyle\left[\prod_{r=1}^{2}\frac{\|(A_{n}-\lambda_{r}I_{n})^{-1}\|_{*}}{\mu_{1}(\lambda_{r})}\sum_{\ell=1}^{2}\sum_{k=2}^{cn}e^{-k}\left(\frac{\sqrt{\mu_{1}(\lambda_{1})\mu_{1}(\lambda_{2})}}{\mu_{k}(\lambda_{\ell})}\right)^{16/9}\right]$
(5.16) $\displaystyle\lesssim
1+\mathbb{E}_{A_{n}}^{\mathcal{E}(p,\delta_{1}\delta_{2})}\left[\left(\frac{\mu_{1}(\lambda_{1})\mu_{1}(\lambda_{2})}{n}\right)^{9/10}\right]^{80/81}.$

###### Proof.

Let
$\mathcal{E}_{0,p}:=\mathcal{E}_{1}\cap\mathcal{E}_{2}\cap\mathcal{E}(p,\delta_{1}\delta_{2})$,
and it suffices to take expectation on $\mathcal{E}_{0,p}$ as both
$\mathcal{E}_{1},\mathcal{E}_{2}$ have probability $1-e^{-\Omega(n)}$. The
desired claim again follows from computing

$\displaystyle\mathbb{E}_{A_{n}}^{\mathcal{E}_{0},p}$
$\displaystyle\left[\prod_{r=1}^{2}\frac{\|(A_{n}-\lambda_{r}I_{n})^{-1}\|_{*}}{\mu_{1}(\lambda_{r})}\cdot\frac{\mu_{1}(\lambda_{1})^{8/9}\mu_{1}(\lambda_{2})^{8/9}}{\mu_{k}(\lambda_{\ell})^{16/9}}\right]$
$\displaystyle\leq\prod_{r=1}^{2}\mathbb{E}_{A_{n}}^{\mathcal{E}_{0,p}}\left[\left(\frac{\|A_{n}-\lambda_{r}I_{n}\|_{*}}{\mu_{1}(\lambda_{r})}\right)^{324}\right]^{1/324}\cdot\mathbb{E}_{A_{n}}^{\mathcal{E}_{0,p}}\left[\left(\frac{\sqrt{n}}{k\mu_{k}(\lambda_{\ell_{1}})}\right)^{288}\right]^{1/162}$
$\displaystyle\quad\quad\cdot\mathbb{E}_{A_{n}}^{\mathcal{E}_{0,p}}\left[\left(\frac{\mu_{1}(\lambda_{1})\mu_{1}(\lambda_{2})}{n}\right)^{9/10}\right]^{80/81}\cdot
k^{16/9}$ $\displaystyle\lesssim
k^{2}\mathbb{E}_{A_{n}}^{\mathcal{E}_{0,p}}\left[\left(\frac{\mu_{1}(\lambda_{1})\mu_{1}(\lambda_{2})}{n}\right)^{9/10}\right]^{80/81}$

where we use Lemma 3.1 and Lemma 3.2 to show that the two terms on the second
line are $O(1)$. Recalling that $\sum_{k\geq 1}k^{2}e^{-k}<+\infty,$ the proof
is complete. ∎

###  5.5. Conclusion

Now we are ready to prove Lemma 5.1.

###### Proof of Lemma 5.1.

We make a further conditioning and write

$\displaystyle\mathbb{E}_{A_{n}}\sup_{r_{1},r_{2}}\mathbb{P}_{X}\left(\frac{|\langle(A_{n}-\lambda_{i}I_{n})^{-1}X,X\rangle-
r_{i}|}{\|(A_{n}-\lambda_{i}I_{n})^{-1}\|_{*}}\leq\delta_{i},\langle
X,u\rangle\geq
s,\frac{\mu_{1}(\lambda_{1})\mu_{1}(\lambda_{2})}{n}\leq(\delta_{1}\delta_{2})^{-p}\right)$
$\displaystyle\leq\mathbb{P}(\sigma_{min}(A_{n}-\lambda_{1}I_{n})\leq\delta_{1}\delta_{2}n^{-1/2})+\mathbb{P}(\sigma_{min}(A_{n}-\lambda_{2}I_{n})\leq\delta_{1}\delta_{2}n^{-1/2})$
$\displaystyle+\mathbb{E}_{A_{n}}\sup_{r_{1},r_{2}}\mathbb{P}_{X}\left(\bigcap_{i=1}^{2}\left\\{\left\|\frac{\langle(A_{n}-\lambda_{i}I_{n})^{-1}X,X\rangle-
r_{i}}{\|(A_{n}-\lambda_{i}I_{n})^{-1}X\|}\right\|\leq\delta_{i}\right\\}\wedge\mathcal{E}\right),$

where we define

$\mathcal{E}:=\\{\sigma_{min}(A_{n}-\lambda_{i}I_{n})\geq\delta_{1}\delta_{2}n^{-1/2},i=1,2;\quad\frac{\mu_{1}(\lambda_{1})\mu_{1}(\lambda_{2})}{n}\leq(\delta_{1}\delta_{2})^{-p}\\}.$

The probability
$\mathbb{P}(\sigma_{min}(A_{n}-\lambda_{1}I_{n})\leq\delta_{1}\delta_{2}n^{-1/2})$
is easily bounded by $C\delta_{1}\delta_{2}+e^{-\Omega(n)}$ by an application
of Proposition 5.3.

To compute the last term, we use Theorem 2.1 to write the probability in
question as the integral of $I(\theta)^{1/2}$ over the given region. Then we
use the Hölder inequality estimate (5.2) combined with decomposition (5.3),
and the computations in (5.9), (5.10) and (5.15), as well as estimates in
Lemma 5.4 and Lemma 5.5 to obtain the desired result.

∎

##  6\. Reduction to generic events: two locations

Before we come to the proof of the main theorem, we need another preprocessing
of the probability in question, to eliminate another pathological event. We
will take $d=2$ in this section, and return to the general $d$ case later.

For any $p\geq 1$, define

$\mathcal{P}^{p}:=\left\\{\prod_{i=1}^{2}\sigma_{min}(A^{(j)}_{n+1}-\lambda_{i}I_{n})\leq(\delta_{1}\delta_{2})^{p}n^{-1}\text{
for at least }\frac{1}{4}n\text{ values }j\in[n+1]\right\\},$

where we recall that $A_{n+1}^{(j)}$ is the principal submatrix of $A_{n+1}$
with the $j$-th row and column removed.

We shall prove in this section that

######  Proposition 6.1.

Fix $B>0$ and $\zeta\in\Gamma_{B}$, consider
$A_{n+1}\sim\operatorname{Sym}_{n+1}(\zeta)$. Then for any $p>1$,

$\mathbb{P}(\sigma_{min}(A_{n+1}-\lambda_{i}I_{n+1})\leq\delta_{i}n^{-1/2},i=1,2,\quad\mathcal{P}^{p})\lesssim\delta_{1}\delta_{2}+e^{-\Omega(n)}.$

The proof of Theorem 1.2 can therefore be reduced to the following:

######  Proposition 6.2.

Let $A_{n+1}$ satisfy the assumptions of Theorem 1.2 and
$\lambda_{1},\lambda_{2}\in\mathbb{R}$ . For any $p>1$,

$\displaystyle\mathbb{P}(\sigma_{min}(A_{n+1}-\lambda_{i}I_{n+1})\leq\delta_{i}n^{-1/2},i=1,2)\lesssim\delta_{1}\delta_{2}+e^{-\Omega(n)}$
$\displaystyle+\mathbb{E}_{A_{n}}\sup_{r_{1},r_{2}}\mathbb{P}_{X}\left(\frac{|\langle(A_{n}-\lambda_{i}I_{n})^{-1}X,X\rangle-
r_{i}|}{\|(A_{n}-\lambda_{i}I_{n})^{-1}X\|_{2}}\leq\delta_{i},i=1,2,\frac{\mu_{1}(\lambda_{1})\mu_{1}(\lambda_{2})}{n}\leq(\delta_{1}\delta_{2})^{-p}\right).$

###  6.1. Eliminating pathological events.

We first prove Proposition 6.1. To complete the proof we need two auxiliary
results. The first concerns the eigenvector delocalization of Wigner matrices,
taken from Rudelson and Vershynin [30], Theorem 1.3. This result is
fundamental to the validity of the proof of this paper. Note that thanks to
the continuous density assumption in Theorem 1.2, we do not need to assume
that the entries of $A_{ij}$ have the same variance, so the result holds for
GOE type matrices as well where the diagonal entries have a different
variance.

######  Theorem 6.3.

Fix $B>0$ and let $\zeta\in\Gamma_{B}$ have a continuous density. Consider
$A_{n}\sim\operatorname{Sym}_{n}(\zeta)$ and let $v$ be any eigenvector of
$A_{n}$. Then there is some $c_{2}>0$ such that for any sufficiently small
$c_{1}>0$, for $n$ sufficiently large,

$\mathbb{P}(|v_{j}|\geq(c_{2}c_{1})^{6}n^{-1/2}\text{ for at least
}(1-c_{1})n\text{ indices }j)\geq 1-e^{-c_{1}n}.$

The estimate is independent of the chosen eigenvector.

We also need the following geometric fact from [10], Fact 6.7, whose first
version appeared in Tao-Vu [34].

######  Fact 6.4.

Given any $n\times n$ real symmetric matrix $M$ and $\lambda$ as an
eigenvector of $M$ with associated eigenvector $u$. Let $j\in[n]$ and assume
$\lambda^{\prime}$ is an eigenvector of the principal minor $M^{(j)}$
corresponding to a unit eigenvector $v$. Then we have

$|\langle v,X^{(j)}\rangle|\leq|\lambda-\lambda^{\prime}|/|u_{j}|,$

where $X^{(j)}$ denotes the $j$-th column of $M$ having removed the $j$-th
entry.

###### Proof of Proposition 6.1.

We first find some value $j$ such that the event in $\mathcal{P}^{p}$ holds
for the subscript $j$ and the unit eigenvectors (denoted $u_{1}$ and $u_{2}$)
of $A_{n+1}$ corresponding to the least singular values of
$A_{n+1}-\lambda_{1}I_{n+1}$ and $A_{n+1}-\lambda_{2}I_{n+1}$ respectively,
satisfy $|(u_{1})_{j}|,|(u_{2})_{j}|\geq(c_{2}c_{1})^{6}n^{-1/2}$ for some
fixed $c_{1}$. The fact that such $j$ exists among the given $\frac{1}{4}n$
values of $j$ specified in $\mathcal{P}^{p}$ are guaranteed by Theorem 6.3
with probability $1-e^{-\Omega(n)}$.

Now we would like to find a dyadic decomposition of
$[(\delta_{1}\delta_{2})^{p},1]=\cup_{j=1}^{I_{n}}I_{j}$ into $I_{n}$
intervals, where we denote by $I_{j}=[I_{j,S},I_{j,L}]$ such that
$I_{j,L}=2I_{j,S}$ and $I_{j,S}=I_{j+1,L}$ (except for $I_{1}$, where we do
slightly differently). Then we have $I_{n}=O(\log(\delta_{1}\delta_{2})^{-1})$
and we can classify the condition
$\prod_{i=1}^{2}\sigma_{min}(A_{n}-\lambda_{i}I_{n})\leq(\delta_{1}\delta_{2})^{p}n^{-1}$
into $(I_{n})^{2}$ sub-events, each given by the form
$\sigma_{min}(A_{n}-\lambda_{i}I_{n})\leq x_{i}n^{-1/2}$,
$\sigma_{min}(A_{n}-\lambda_{i}I_{n})\leq x_{j}n^{-1/2}$ and $x_{i}x_{j}\leq
4(\delta_{1}\delta_{2})^{p}$. (Note that if for some $i$ we already have
$\sigma_{min}(A_{n}-\lambda_{i}I_{n})\leq(\delta_{1}\delta_{2})^{p}n^{-1/2}$
we may directly apply Proposition 5.3, or if for some $i$ we have
$\sigma_{min}(A_{n}-\lambda_{i}I_{n})\geq n^{-1/2}$ then for the other
$\ell\neq i$ we must have
$\sigma_{min}(A_{n}-\lambda_{\ell}I_{n})\leq(\delta_{1}\delta_{2})^{p}n^{-1/2}$,
and we are also done).

Now we analyze each of these $(I_{n})^{2}$ events. We first assume that for at
least one $i$ we must have $x_{i}\geq\delta_{i}$. Let us take $i=1$ without
loss of generality, that is,
$\sigma_{min}(A_{n+1}^{(j)}-\lambda_{1}I_{n})\geq\delta_{1}$. We first
consider the other event $\sigma_{min}(A_{n+1}^{(j)}-\lambda_{2}I_{n})\leq
x_{2}n^{-1/2}$. By Proposition 5.3, we have the bound

$\mathbb{P}\left(\sigma_{min}(A_{n+1}^{(j)}-\lambda_{2}I_{n})\leq
x_{2}n^{-1/2}\right)\lesssim x_{2}+e^{-\Omega(n)}.$ (6.1)

Now we return to $\lambda_{1}$. By assumption that $x_{1}\geq\delta_{1}$, we
need only to bound

$\mathbb{P}\left(\sigma_{min}(A_{n+1}-\lambda_{1}I_{n+1})\leq
x_{1}n^{-1/2},\sigma_{min}(A_{n+1}^{(j)}-\lambda_{1}I_{n})\leq
x_{1}n^{-1/2}\mid\mathcal{E}_{2,p}\right)$ (6.2)

where we are conditioning on the event

$\mathcal{E}_{2,p}:=\\{\sigma_{min}(A_{n+1}^{(j)}-\lambda_{2}I_{n})\leq
x_{2}n^{-1/2}\\}.$

We use Fact 6.4, where we make the crucial observation that $X^{(j)}$ is
independent of $A_{n+1}^{(j)}$, so we may assume that the vector $v$ is any
fixed vector of unit length in Fact 6.4 and apply the randomness of $X^{(j)}$.
Since $X^{(j)}$ has a bounded density and $v$ has unit length, we apply Lemma
4.3 and conclude that

$\eqref{conditionone}\lesssim x_{1}+e^{-\Omega(n)}.$ (6.3)

Then we can combine this with (6.1) to obtain

$\displaystyle\mathbb{P}\left(\sigma_{min}(A_{n+1}-\lambda_{i}I_{n+1})\leq\delta_{i}n^{-1/2},\sigma_{min}(A_{n+1}^{(j)}-\lambda_{i}I_{n})\leq
x_{i}n^{1/2},i=1,.2\right)$ $\displaystyle\quad\quad\lesssim
x_{1}x_{2}+e^{-\Omega(n)}\lesssim(\delta_{1}\delta_{2})^{p}+e^{-\Omega(n)}.$

Then we are left with the remaining case where $x_{1}<\delta_{1}$ and
$x_{2}<\delta_{2}$. Our assumption that
$x_{1}x_{2}<(\delta_{1}\delta_{2})^{p}$ implies that for some $i=1,2$ we have
$x_{i}\leq\delta_{i}(\delta_{1}\delta_{2})^{(p-1)/2}$. Let us say we have
$i=2$ ($i=1$ is analogous), so
$x_{2}\leq\delta_{2}(\delta_{1}\delta_{2})^{(p-1)/2}$.

We first apply Proposition 5.3 and obtain the same estimate as in (6.1). We
then apply fact 6.4 and Lemma 4.3 to obtain

$\displaystyle\mathbb{P}\left(\sigma_{min}(A_{n+1}-\lambda_{1}I_{n+1})\leq\delta_{1}n^{-1/2},\sigma_{min}(A_{n+1}^{(j)}-\lambda_{1}I_{n})\leq\delta_{1}n^{-1/2}\mid\mathcal{E}_{2,p}\right)$
(6.4) $\displaystyle\lesssim\delta_{1}+e^{-\Omega(n)}$

Combining these two estimates, we have

$\displaystyle\mathbb{P}\left(\sigma_{min}(A_{n+1}-\lambda_{i}I_{n+1})\leq\delta_{i}n^{-1/2},\sigma_{min}(A_{n+1}^{(j)}-\lambda_{i}I_{n})\leq
x_{i}n^{1/2},i=1,.2\right)$
$\displaystyle\quad\quad\lesssim\delta_{1}x_{2}+e^{-\Omega(n)}\lesssim(\delta_{1}\delta_{2})^{(p+1)/2}+e^{-\Omega(n)}.$

Then we complete the proof by considering all the $(I_{n})^{2}$ events, which
leads to an entropy cost of $\log((\delta_{1}\delta_{2})^{-1})^{C_{d}}$. ∎

We note that in the proof we have repeatedly applied Lemma 4.3 to deduce small
ball probabilities assuming that $X^{(j)}$ has a continuous density. This can
well be replaced by applying the inverse Littlewood-Offord lemmas (see [32])
and we do not need to assume a continuous density. However, in other parts of
the paper, such Littlewood-Offord lemmas are not effective enough to address
the joint LCD of many different eigenvectors (see [31] for the use of joint
LCD for bounding singular values); therefore, we do not use this approach and
maintain the continuous density assumption throughout.

###  6.2. Refinement of invertibility via distance

Now we have shown that in order to prove

$\mathbb{P}(\sigma_{min}(A_{n+1}-\lambda_{i}I_{n+1})\leq\delta_{i}n^{-1/2},i=1,2)\lesssim\delta_{1}\delta_{2}+e^{-\Omega(n)},$

it suffices to prove, for any $p>1$,

$\mathbb{P}(\sigma_{min}(A_{n+1}-\lambda_{i}I_{n+1})\leq\delta_{i}n^{-1/2},i=1,2,\quad\wedge\quad(\mathcal{P}^{p})^{c})\lesssim\delta_{1}\delta_{2}+e^{-\Omega(n)}.$
(6.5)

We now investigate how to determine this quantity. First recall the
fundamental fact (see [32])

######  Fact 6.5.

For any $n\times n$ symmetric matrix, let $v$ be the unit vector corresponding
to the least singular value of $M$, that is, $\|Mv\|_{2}=\sigma_{min}(M)$ and
$\|v\|_{2}=1$. Then we have

$\sigma_{min}(M)\geq|v_{j}|\cdot d_{j}(M)\quad\text{ for each }j\in[n],$

where $d_{j}(M)$ is the distance of the $j$-th column of $M$ to the subspace
spanned by the other $n-1$ columns of $M$.

###### Proof of Proposition 6.2.

Let the eigenvalues associated with the least singular value of
$A_{n+1}-\lambda_{i}I_{n+1}$ be denoted by $u_{i}$ for each $i=1,2$. Let
$\mathcal{C}$ be the rare event that, for some $i=1,2$, $u_{i}$ does not
satisfy the conclusion of Theorem 6.3 where we take $c_{1}=\frac{1}{4}$. Then
$\mathbb{P}(\mathcal{C})=e^{-\Omega(n)}$. On $\mathcal{C}^{c}$, we have that

$\sigma_{min}(A_{n+1}-\lambda_{i}I_{n+1})\geq c_{3}n^{-1/2}\cdot
d_{j}(A_{n+1}-\lambda_{i}I_{n+1})\text{ for both }i=1,2$ (6.6)

for at least $\frac{1}{2}n$ choices of $j\in[n+1]$, where $c_{3}$ is a
universal constant.

Furthermore, by assumption of $(\mathcal{P}^{p})^{c}$, there are at least
$\frac{1}{4}n$ values of $j\in[n+1]$ such that (6.6) holds for such $j$ and
moreover,

$\prod_{i=1}^{2}\sigma_{min}(A_{n+1}^{(j)}-\lambda_{i}I_{n})\geq(\delta_{1}\delta_{2})^{p}n^{-1}.$

Now let $S\subset\\{1,2,\cdots,n+1\\}$ denote the collection of subscripts
$j\in[n+1]$ such that the following event $\mathcal{H}_{j}$ holds (for some
universal constant $C$)

$\mathcal{H}_{j}:=\left\\{d_{j}(A_{n+1}-\lambda_{i}I_{n+1})\leq
C\delta_{i}\text{ for
}i=1,2,\prod_{i=1}^{2}\sigma_{min}(A_{n+1}^{(j)}-\lambda_{i}I_{n})\geq(\delta_{1}\delta_{2})^{p}n^{-1}\right\\}.$

Our previous discussions imply that

$\left\\{\sigma_{min}(A_{n+1}-\lambda_{i}I_{n+1})\leq\delta_{i}n^{-1/2},i=1,2\right\\}\bigcap(\mathcal{P}^{p})^{c}\bigcap\mathcal{C}^{c}\Rightarrow|S|>\frac{1}{4}n.$

By a classical first moment method,

$\mathbb{P}(|S|>\frac{1}{4}n)\leq\frac{4}{n}\sum_{j=1}^{n+1}\mathbb{P}(\mathcal{H}_{j}),$

therefore, for some specific $j_{*}\in[n+1]$ we have
$\mathbb{P}(|S|\geq\frac{1}{4}n)\leq 5\mathbb{P}(\mathcal{H}_{j_{*}})$ when
$n$ is large.

In the final step, we use Fact 1.9 to rewrite
$d_{j}(A_{n+1}-\lambda_{i}I_{n+1})$ in the form of distance and complete the
proof. ∎

Note that in contrast to the usual proofs via invertibility by distance (see
[32] and [10], Lemma 6.3) where one only uses the fact that the test vector is
incompressible, here we use the much stronger result from [30] that both
eigenvectors have $(1-c_{1}n)$ coordinates that are not too small, so that we
can find many coordinates that are not too small for both vectors. This
stronger property is fundamental in this multimatrix setting.

##  7\. Bootstrap and proof completion: two locations

In this section we complete the proof of our main Theorem, theorem 1.2 for the
$d=2$ case. We will first use an initial estimate
$(\delta_{1}\delta_{2})^{1/10}$ and bootstrap to obtain an estimate
$\delta_{1}\delta_{2}(\log(\delta_{1}\delta_{2})^{-1})^{1/2}$, and
subsequently eliminate the log factor and obtain the optimal bound.

###  7.1. Initial estimate and bootstrapping

First recall the well-known concentration inequality from Hanson and Wright
[41] [19], see also [37], Theorem 6.2.1.

######  Theorem 7.1 (Hanson-Wright).

Given $B>0$, $\zeta\in\Gamma_{B}$ and consider
$X\sim\operatorname{Sym}_{n}(\zeta)$. Let $M$ be an $n\times n$ matrix. Then
given any $t>0$,

$\mathbb{P}_{X}(|\|MX\|_{2}-\|M\|_{HS}|>t)\leq
4\exp(-\frac{ct^{2}}{B^{4}\|M\|_{2}})$

for a universal constant $c>0$.

We can then perform the initial estimate as follows:

######  Lemma 7.2.

Let the random matrix $A_{n}$ satisfy the assumptions of Theorem 1.2. For any
fixed $\kappa>0$ and $\Delta>0$, and any
$\lambda_{1},\lambda_{2}\in[-(2-\kappa)\sqrt{n},(2-\kappa)\sqrt{n}]$ with
$|\lambda_{1}-\lambda_{2}|\geq\Delta\sqrt{n}$, we have the following initial
estimate: for any $\delta_{1},\delta_{2}>0$,

$\mathbb{P}\left(\sigma_{min}(A_{n+1}-\lambda_{i}I_{n+1})\leq\delta_{i}n^{-1/2},\quad
i=1,2\right)\lesssim(\delta_{1}\delta_{2})^{1/10}+e^{-\Omega(n)}.$

The rate $\epsilon^{1/10}$ is rather weak, but we will bootstrap it to the
optimal rate later.

###### Proof.

By Proposition 6.2, it suffices to prove that for any
$(r_{1},r_{2})\in\mathbb{R}^{2}$ and some $p>1$,

$\displaystyle\mathbb{P}_{A_{n},X}\left(\frac{|\langle(A_{n}-\lambda_{i}I_{n})^{-1}X,X\rangle-
r_{i}|}{\|(A_{n}-\lambda_{i}I_{n})^{-1}X\|_{2}}\leq
C\delta_{i},i=1,2,\prod_{i=1}^{2}\sigma_{min}(A_{n}-\lambda_{i}I_{n})\geq(\delta_{1}\delta_{2})^{p}n^{-1}\right)$
(7.1) $\displaystyle\lesssim(\delta_{1}\delta_{2})^{1/10}+e^{-\Omega(n)}.$

Applying Hanson-Wright (Theorem 7.1), there is a $C^{\prime}>0$ satisfying,
for $i=1,2$,

$\mathbb{P}_{X}(\|(A_{n}-\lambda_{i}I_{n})^{-1}X\|_{2}\geq
C^{\prime}(\log(\delta_{1}\delta_{2})^{-1})^{1/2}\cdot\|(A_{n}-\lambda_{i}I_{n})^{-1}\|_{HS})\leq\delta_{1}\delta_{2},$
(7.2)

so it suffices to bound, for any $(\theta_{1},\theta_{2})\in\mathbb{R}^{2}$,

$\mathbb{P}_{A_{n},X}\left(\frac{|\langle(A_{n}-\lambda_{i}I_{n})^{-1}X,X\rangle-
r_{i}|}{\|(A_{n}-\lambda_{i}I_{n})\|_{HS}}\leq\bar{\delta}_{i},i=1,2,\prod_{i=1}^{2}\sigma_{n}(A_{n}-\lambda_{i}I_{n})\geq\delta_{i}n^{-1/2}\right),$
(7.3)

where we set
$\bar{\delta}_{i}:=C^{{}^{\prime\prime}}\delta_{i}(\log(\delta_{1}\delta_{2})^{-1})^{1/2}$
for $i=1,2$, and we used the fact that $\|M\|_{*}\geq\|M\|_{HS}$ for any
square matrix $M$.

Then we apply Proposition 6.2 (with $p=1.01$) and conclude with

$\eqref{sufficestobound}\lesssim\bar{\delta}_{1}\bar{\delta_{2}}(\delta_{1}\delta_{2})^{-8p/9}+e^{-\Omega(n)}\leq(\delta_{1}\delta_{2})^{1/10}+e^{-\Omega(n)}.$
(7.4)

∎

Now we set up our bootstrapping estimate.

######  Lemma 7.3.

Let $A_{n+1}$ and $\lambda_{1},\lambda_{2}$ satisfy the assumptions of Theorem
1.2. Suppose that for any $\delta_{1},\delta_{2}>0$ and all $n$ we already
have

$\mathbb{P}\left(\sigma_{min}(A_{n+1}-\lambda_{i}I_{n+1})\leq\delta_{i}n^{-1/2},i=1,2\right)\lesssim(\delta_{1}\delta_{2})^{\tau}+e^{-\Omega(n)}.$
(7.5)

Then for all all $\delta_{1},\delta_{2}>0$, all $n$ and any $p>1$, and
$\omega>0$ that is sufficiently small, we have

$\displaystyle\mathbb{P}(\sigma_{min}(A_{n+1}-\lambda_{i}I_{n+1})\leq\delta_{i}n^{-1/2},i=1,2)$
(7.6)
$\displaystyle\lesssim(\delta_{1}\delta_{2})^{\min(1,\frac{80}{81}(1-\omega)\tau
p-\frac{8}{9}p+1)}(\log(\delta_{1}\delta_{2})^{-1})^{1/2}+e^{-\Omega(n)}.$

###### Proof.

Assume $\delta_{1},\delta_{2}\geq e^{-cn}$, otherwise the claim is trivial. We
first apply Lemma 5.2 to obtain the following: for any $\epsilon>0$, and any
sufficiently small $\omega>0$,

$\displaystyle\mathbb{P}(\sigma_{min}(A_{n+1}-\lambda_{1}I_{n+1})\cdot\sigma_{min}(A_{n+1}-\lambda_{2}I_{n+1})$
$\displaystyle\quad\leq\epsilon
n^{-1})\lesssim\epsilon(\log\epsilon^{-1})^{d}+e^{-\Omega(n)}\lesssim\epsilon^{1-\omega}+e^{-\Omega(n)}.$

Following the same lines as in the proof of the base step, we evaluate (using
Lemma 5.1 with parameter $p$, with $u=0$, $s=0$ and take
$\epsilon=\delta_{1}\delta_{2}$):

$\displaystyle\mathbb{E}_{A_{n}}\left[\left(\frac{\mu_{1}(\lambda_{1})\mu_{1}(\lambda_{2})}{n}\right)^{9/10}\mathbf{1}\left\\{\frac{\mu_{1}(\lambda_{1})\mu_{1}(\lambda_{2})}{n}\leq\epsilon^{-p}\right\\}\right]$
$\displaystyle\lesssim\int_{0}^{\epsilon^{-9p/10}}\mathbb{P}\left(\sigma_{min}(A_{n}-\lambda_{1}I_{n})\cdot\sigma_{min}(A_{n}-\lambda_{2}I_{n})\leq
x^{-10/9}n^{-1}\right)dx,$ $\displaystyle\lesssim
1+\int_{1}^{\epsilon^{-9p/10}}(x^{-(1-\omega)10\tau/9}+e^{-cn})dx\lesssim\max\\{1,\epsilon^{(1-\omega)\tau
p-9p/10}\\}.$

Then we apply Lemma 5.1 with $s=0$, $u=0$ and get: for any
$(r_{1},r_{2})\in\mathbb{R}^{2}$,

$\displaystyle\mathbb{P}_{A_{n},X}$
$\displaystyle\left(\prod_{i=1}^{2}\frac{|\langle(A_{n}-\lambda_{i}I_{n})^{-1}X,X\rangle-
r_{i}|}{\|A_{n}-\lambda_{i}I_{n}\|_{HS}}\leq\delta_{1}\delta_{2},\frac{\mu_{1}(\lambda_{1})\mu_{1}(\lambda_{2})}{n}\leq\epsilon^{-p}\right)$
(7.7)
$\displaystyle\lesssim\max\\{\delta_{1}\delta_{2},(\delta_{1}\delta_{2})^{\frac{80}{81}(1-\omega)\tau
p-\frac{8}{9}p+1}\\}\cdot(\log\epsilon^{-1})^{1/2}+e^{-\Omega(n)},$

where we have used the fact that
$\|A_{n}-\lambda_{i}I_{n}\|_{HS}\leq\|A_{n}-\lambda_{i}I_{n}\|_{*}$.

Finally, applying Hanson-Wright (Theorem 7.1), for $i=1,2$, we obtain

$\mathbb{P}_{X}\left(\|(A_{n}-\lambda_{i}I_{n})^{-1}X\|_{2}\geq
C^{\prime}\|(A_{n}-\lambda_{i}I_{n})^{-1}\|_{HS}\cdot(\log(\delta_{1}\delta_{2})^{-1})^{1/2}\right)\leq\delta_{1}\delta_{2}.$

∎

Now we can finish the bootstrap procedure. We need to first fix $p$, bootstrap
to increase $\tau$, then increase $p$ and bootstrap $\tau$ again. We will
prove that only finitely many steps are needed.

######  Lemma 7.4.

In the setting of Lemma 7.2, for any $\delta_{1},\delta_{2}>0$,

$\mathbb{P}\left(\sigma_{min}(A_{n+1}-\lambda_{i}I_{n+1})\leq\delta_{i}n^{-1/2},\quad
i=1,2\right)\lesssim\delta_{1}\delta_{2}(\log(\delta_{1}\delta_{2})^{-1})^{1/2}+e^{-\Omega(n)}.$

###### Proof.

By lemma 7.2, we start with the initial value $\tau=0.1$. We take $\omega$
arbitrarily small (say $10^{-10}$) and take $p=\frac{81}{80(1-\omega)}$ such
that Lemma 7.2 yields the bootstrapping step $\tau\to\tau+0.09$ (we upper
bound $\epsilon^{\tau+1-0.9/(1-\omega)}(\log\epsilon^{-1})^{1/2}$ by
$\epsilon^{\tau+0.09}$) until $\tau=1$. Then after ten applications of Lemma
7.2 to bootstrap $\tau$ from 0.1 to $0.19,0.28,\cdots,0.91,1$, we finish the
proof. ∎

###  7.2. Completing the proof: eliminating the log factor

By Lemma 6.2, to conclude the proof of Theorem 1.2 it suffices to prove that
we can find some $C>0$ so that for any $\delta_{1},\delta_{2}>0$ and any
$p>1$,

$\displaystyle\mathbb{P}$
$\displaystyle\left(\frac{\langle(A_{n}-\lambda_{i}I_{n})^{-1}X,X\rangle}{\|(A_{n}-\lambda_{i}I_{n})^{-1}X\|_{2}}\leq
C\delta_{i},i=1,2,\prod_{i=1}^{2}\sigma_{min}(A_{n}-\lambda_{i}I_{n})\geq(\delta_{1}\delta_{2})^{p}n^{-1}\right)$
(7.8) $\displaystyle\lesssim\delta_{1}\delta_{2}+e^{-\Omega(n)}.$

For any fixed $(r_{1},r_{2})\in\mathbb{R}^{2}$ We introduce the following
notations (we do not make explicit the dependence on $r_{i}$ in the symbols
introduced, as they are not essential)

$Q(A,X,\lambda_{i}):=\frac{|\langle(A_{n}-\lambda_{i}I_{n})^{-1}X,X\rangle-
r_{i}|}{\|(A_{n}-\lambda_{i}I_{n})^{-1}X\|_{2}},$
$Q_{*}(A,\lambda_{i},X):=\frac{|\langle(A_{n}-\lambda_{i}I_{n})^{-1}X,X\rangle-
r_{i}|}{\|(A_{n}-\lambda_{i}I_{n})^{-1}\|_{*}},$

recalling that

$\|(A_{n}-\lambda_{i}I_{n})^{-1}\|_{*}^{2}:=\sum_{k=1}^{n}\mu_{k}^{2}(\lambda_{i})(\log(1+k))^{2}.$

Let
$\mathcal{E}:=\left\\{\prod_{i=1}^{2}\sigma_{min}(A_{n}-\lambda_{i}I_{n})\geq(\delta_{1}\delta_{2})^{p}n^{-1}\right\\}.$
We now decompose the left hand side of (7.8):

$\displaystyle\mathbb{P}^{\mathcal{E}}\left(Q(A,X,\lambda_{i})\leq
C\delta_{i},i=1,2\right)\leq\mathbb{P}^{\mathcal{E}}(Q_{*}(A,X,\lambda_{i})\leq
C\delta_{i},i=1,2)$ (7.9)
$\displaystyle+\mathbb{P}^{\mathcal{E}}\left(Q(A,X,\lambda_{i})\leq
C\delta_{i},\quad
i=1,2;\quad\frac{\|(A_{n}-\lambda_{i}I_{n})^{-1}X\|_{2}}{\|(A_{n}-\lambda_{i}I_{n})^{-1}\|_{*}}\geq
2,i=1,2.\right)$
$\displaystyle+\mathbb{P}^{\mathcal{E}}\left(Q(A,X,\lambda_{i})\leq
C\delta_{i},i=1,2;\quad\frac{\|(A_{n}-\lambda_{i}I_{n})^{-1}X\|_{2}}{\|(A_{n}-\lambda_{i}I_{n})^{-1}\|_{*}}\geq
2,\text{for only one }i\in\\{1,2\\}\right).$

Applying Lemma 7.4 together with Lemma 5.1 (taking $u=0$, $s=0$) we can easily
prove the following Lemma, which bounds the right hand side of the first line
of (7.9).

######  Lemma 7.5.

Let $A_{n}$ and $\lambda_{1},\lambda_{2}$ satisfy the assumptions in Theorem
1.2. Then there exists some $p_{0}>1$ such that for any $p\in(1,p_{0})$ we
have

$\mathbb{P}^{\mathcal{E}}(Q_{*}(A,X,\lambda_{i})\leq
C\delta_{i},i=1,2)\lesssim\delta_{1}\delta_{2}+e^{-\Omega(n)}.$

In the following we evaluate the probability in the second line of (7.9), i.e.

$\mathbb{P}^{\mathcal{E}}\left(Q(A,X,\lambda_{i})\leq C\delta_{i},\quad
i=1,2;\quad\frac{\|(A_{n}-\lambda_{i}I_{n})^{-1}X\|_{2}}{\|(A_{n}-\lambda_{i}I_{n})^{-1}\|_{*}}\geq
2,\quad i=1,2.\right).$ (7.10)

Here we consider the direct product of two dyadic partitions

$2^{j_{i}}\leq\|(A_{n}-\lambda_{i}I_{n})^{-1}X\|_{2}/\|(A_{n}-\lambda_{i}I_{n})^{-1}\|_{*}\leq
2^{j_{i}+1},\quad i=1,2,$

and upper bound (7.10) by

$\sum_{j_{1}=1}^{\log n}\sum_{j_{2}=1}^{\log
n}\mathbb{P}^{\mathcal{E}}\left(Q_{*}(A,X,\lambda_{i})\leq
2^{j_{i}+1}C\delta_{i},\quad\frac{\|(A_{n}-\lambda_{i}I_{n})^{-1}X\|_{2}}{\|(A_{n}-\lambda_{i}I_{n})^{-1}\|_{*}}\geq
2^{j_{i}},\quad i=1,2\right)+e^{-\Omega(n)}.$ (7.11)

Note that we can terminate the summation at $\log n$ because, by Hanson-Wright
(Theorem 7.1) and $\|M\|_{*}\geq\|M\|_{HS}$ for any square matrix $M$, we have
for both $i=1,2$,

$\mathbb{P}_{X}(\|(A_{n}-\lambda_{i}I_{n})^{-1}X\|_{2}\geq\sqrt{n}\|(A_{n}-\lambda_{i}I_{n})^{-1}\|_{*})\lesssim
e^{-\Omega(n)}.$

Now we estimate each individual probability via

######  Lemma 7.6.

For any $t_{i},\delta_{i}>0,i=1,2$ we have the following bound

$\displaystyle\mathbb{P}_{X}\left(Q_{*}(A,X,\lambda_{i})\leq
2Ct_{i}\delta_{i},\quad\frac{\|(A_{n}-\lambda_{i}I_{n})^{-1}X\|_{2}}{\|(A_{n}-\lambda_{i}I_{n})^{-1}\|_{*}}\geq
t_{i},\quad\text{ for each }i=1,2\right)$ $\displaystyle\leq
4\sum_{k_{1},k_{2}=1}^{n}\mathbb{P}_{X}(Q_{*}(A,X,\lambda_{i})\leq
2Ct_{i}\delta_{i},\langle X,v_{k_{i}}(\lambda_{i})\rangle\geq
t_{i}\log(1+k_{i}),\text{ for each }i=1,2),$

where $v_{k}(\lambda_{i})$ is the singular vector associated with the $k$-th
largest singular value of $A_{n}-\lambda_{i}I_{n}$. Since each
$v_{k}(\lambda_{i})$ is an eigenvector of $A_{n}$, we assume moreover that all
the $v_{k}(\lambda_{i})$ are chosen from an orthonormal basis of eigenvectors
of $A_{n}$.

###### Proof.

We apply singular value decomposition to
$\|(A_{n}-\lambda_{i}I_{n})^{-1}X\|_{2}\geq
t_{i}\|(A_{n}-\lambda_{i}I_{n})^{-1}\|_{*}$ and obtain

$t_{i}^{2}\sum_{k}\mu_{k}^{2}(\lambda_{i})(\log(k+1))^{2}\leq\sum_{k}\mu_{k}^{2}(\lambda_{i})\langle
v_{k}(\lambda_{i}),X\rangle^{2}.$

That is,

$\\{\|(A_{n}-\lambda_{i}I_{n})^{-1}X\|_{2}\geq
t_{i}\|(A_{n}-\lambda_{i}I_{n})^{-1}\|_{*}\\}\subset\bigcup_{k}\\{|\langle
X,v_{k}(\lambda_{i})\rangle|\geq t_{i}\log(k+1)\\}.$

We apply this decomposition to both $i=1$ and $i=2$. That is, there exists
$k_{1},k_{2}\in[1,n]$ such that $|\langle X,v_{k_{i}}(\lambda_{i})\rangle|\geq
t_{i}\log(k_{i}+1)$. In the generic case where $v_{k_{1}}(\lambda_{1})$ and
$v_{k_{2}}(\lambda_{2})$ are orthogonal, we may consider flipping the sign of
$v_{k_{i}}(\lambda_{i})$ so that for both $i=1,2$ we have $\langle
X,v_{k_{i}}(\lambda_{i})\rangle\geq t_{i}\log(k_{i}+1).$ This leads to a
leading power 4. It is also possible that $v_{k_{1}}(\lambda_{1})$ and
$v_{k_{2}}(\lambda_{2})$ are colinear, and that we take
$v_{k_{1}}(\lambda_{1})=v_{k_{2}}(\lambda_{2})$ without loss of generality. In
this case we are also finished by simultaneously flipping the sign of
$v_{k_{i}}(\lambda_{i})$. ∎

Finally, to estimate the third line of (7.9), it suffices to consider

$\mathbb{P}^{\mathcal{E}}\left(Q_{*}(A,X,\lambda_{1})\leq
C\delta_{1},Q(A,X,\lambda_{2})\leq
C\delta_{2};\quad\frac{\|(A_{n}-\lambda_{2}I_{n})^{-1}X\|_{2}}{\|(A_{n}-\lambda_{2}I_{n})^{-1}\|_{*}}\geq
2\right),$

(the case when we swap subscripts 1 and 2 is exactly the same). This
possibility in question is bounded by $e^{-cn}$ plus the following:

$\sum_{j=1}^{\log n}\mathbb{P}^{\mathcal{E}}\left(Q_{*}(A,X,\lambda_{1})\leq
2C\delta_{1},Q_{*}(A,X,\lambda_{2})\leq
2^{j+1}C\delta_{2},\frac{\|(A_{n}-\lambda_{2}I_{n})^{-1}X\|_{2}}{\|(A_{n}-\lambda_{2}I_{n})^{-1}\|_{*}}\geq
2^{j}\right).$

As in the argument of Lemma 7.6, this possibility is bounded by $e^{-cn}$ plus
the following:

$\sum_{j=1}^{\log
n}\sum_{k=1}^{n}\mathbb{P}^{\mathcal{E}}\left(Q_{*}(A,X,\lambda_{1})\leq
2C\delta_{1},Q_{*}(A,X,\lambda_{2})\leq 2^{j+1}C\delta_{2},\langle
X,v_{k}\rangle\geq 2^{j}\log(1+k)\right)$ (7.12)

where $\\{v_{i}\\}_{i=1}^{n}$ is an orthonormal base of the eigenvectors of
$A_{n}$.

Now we can finish the proof of Theorem 1.2.

###### Proof of Theorem 1.2 for $d=2$ locations.

We combine (7.9), Lemma 7.5 with equation (7.11), Lemma 7.6 and the deduction
of (7.12) to obtain

$\displaystyle\mathbb{P}^{\mathcal{E}}(Q(A,X,\lambda_{i})\leq
C\delta_{i},i=1,2)\lesssim e^{-\Omega(n)}+\delta_{1}\delta_{2}$
$\displaystyle+\sum_{j_{1},j_{2}=1}^{\log
n}\sum_{k_{1},k_{2}=1}^{n}\mathbb{P}^{\mathcal{E}_{0}}\left(Q_{*}(A,X,\lambda_{i})\leq
2^{j_{i}+1}C\delta_{i};\langle X,v_{k_{i}}(\lambda_{i})\rangle\geq
2^{j_{i}}\log((1+k_{i}))\right)$ $\displaystyle+\sum_{j_{1}=1,j_{2}\equiv
0}^{j_{1}=\log n}\sum_{k_{1}=1,k_{2}\equiv
0}^{k_{1}=n}\mathbb{P}^{\mathcal{E}_{0}}\left(Q_{*}(A,X,\lambda_{i})\leq
2^{j_{i}+1}C\delta_{i};\langle X,v_{k_{i}}(\lambda_{i})\rangle\geq
2^{j_{i}}\log((1+k_{i}))\right)$ $\displaystyle+\sum_{j_{1}\equiv
0,j_{2}=1}^{j_{2}=\log n}\sum_{k_{1}\equiv
0,k_{2}=1}^{k_{2}=n}\mathbb{P}^{\mathcal{E}_{0}}\left(Q_{*}(A,X,\lambda_{i})\leq
2^{j_{i}+1}C\delta_{i};\langle X,v_{k_{i}}(\lambda_{i})\rangle\geq
2^{j_{i}}\log((1+k_{i}))\right).$

We can combine the two conditions $\langle X,v_{k_{i}}(\lambda_{i})\rangle\geq
2^{j_{i}}\log(1+k_{i})$, $i=1,2$ into $\langle X,v_{k_{1}k_{2}}\rangle\geq
2^{j_{1}}\log(1+k_{1})+2^{j_{2}}\log(1+k_{2})$, where we set
$u_{k_{1}k_{2}}=v_{k_{1}}(\lambda_{1})+v_{k_{2}}(\lambda_{2})$. Note that
$v_{k_{1}}(\lambda_{1})$ and $v_{k_{2}}(\lambda_{2})$ are both eigenvectors of
$A_{n}$, so either we have $\|u_{k_{1}k_{2}}\|=\sqrt{2}$ if they correspond to
two orthogonal eigenvectors, or if they correspond to co-linear vectors we
must have that $v_{k_{1}}(\lambda_{1})=v_{k_{2}}(\lambda_{2})$ (by assumption
of Lemma 7.6 they are either co-linear or orthogonal) so that
$\|u_{k_{1}k_{2}}\|=2$. We can now apply Lemma 5.1 for all $t_{i}>0$ where we
choose $\delta_{i}$ to be $2Ct_{i}\delta_{i}$,
$s=t_{1}\log(k_{1}+1)+t_{2}\log(k_{2}+1)$ and $u=u_{k_{1}k_{2}}$. Then Lemma
5.1 implies

$\displaystyle\mathbb{P}^{\mathcal{E}_{0}}(Q_{*}(A,X,\lambda_{i})\leq
2Ct_{i}\delta_{i},\langle X,u_{k_{1}k_{2}}\rangle\geq
t_{1}\log(1+k_{1})+t_{2}\log(1+k_{2}))$ (7.13)
$\displaystyle\lesssim\delta_{1}\delta_{2}t_{1}t_{2}(k_{1}+1)^{-t_{1}/2}(k_{2}+1)^{-t_{2}/2}\cdot
I^{81/80}+e^{-\Omega(n)},$

where

$I:=\mathbb{E}_{A_{n}}\left[\left(\frac{\mu_{1}(\lambda_{1})\mu_{1}(\lambda_{2})}{n}\right)^{9/10}\mathbf{1}\left\\{\frac{\mu_{1}(\lambda_{1})\mu_{1}(\lambda_{2})}{n}\leq(\delta_{1}\delta_{2})^{-p}\right\\}\right]$

and $p>1$ can be chosen to be arbitrarily close to 1. Applying Lemma 7.4
combined with Lemma 5.2 and a suitable choice of parameters (i.e. setting $p$
sufficiently close to 1 and when applying Lemma 5.2, setting $\tau$
sufficiently close to 1), we can show that

$I\lesssim 1.$

Combining all the above, we obtain

$\displaystyle\mathbb{P}^{\mathcal{E}_{0}}(Q(A,X,\lambda_{i})\leq
C\delta_{i},i=1,2)$
$\displaystyle\lesssim\delta_{1}\delta_{2}\sum_{j_{1},j_{2}=1}^{\log
n}\sum_{k_{1},k_{2}=1}^{n}2^{j_{1}+j_{2}}(k_{1}+1)^{-2^{j_{1}}}(k_{2}+1)^{-2^{j_{2}}}$
$\displaystyle+2\delta_{1}\delta_{2}\sum_{j=1}^{\log
n}\sum_{k=1}^{n}2^{j}(k+1)^{-2^{j}}+e^{-\Omega(n)}.$

Now the proof is completed by the elementary computation

$\sum_{j_{1}=1}^{\infty}\sum_{j_{2}=1}^{\infty}\sum_{k_{1}=1}^{\infty}\sum_{k_{2}=1}^{\infty}2^{j_{1}+j_{2}}(k_{1}+1)^{-2^{j_{1}}}(k_{2}+1)^{-2^{j_{2}}}=O(1),$

and $\sum_{j=1}^{\infty}\sum_{k=1}^{\infty}2^{j}(k+1)^{-2^{j}}=O(1)$. ∎

##  8\. The multilocation case

In the previous four sections we have invested considerable effort in proving
Theorem 1.2 in the $d=2$ case, and now we do so for general
$d\in\mathbb{N}_{+}$. We will use an inductive argument, assuming that Theorem
1.2 has been proven for all $1,2,\cdots,d-1$ different locations
$\lambda_{i}$’s, and then prove it for $d$ different $\lambda_{i}$’s. All the
essential difficulties are contained in the $d=2$ case, and we outline in this
section how to adapt the proof to general $d$. Some proofs are given in
detail, while the others are sketched and referred to those in the previous
sections.

We first state the induction hypothesis that will be in effect throughout the
whole section:

######  Induction hypothesis.

Fix some $\kappa>0$ and $\Delta>0$, and let $A_{n}$ satisfy the assumptions of
Theorem 1.2. Fix any $d$ real numbers
$\lambda_{1},\cdots,\lambda_{d}\in[-(2-\kappa)\sqrt{n},(2-\kappa)\sqrt{n}]$
such that for any $i\neq j$, $|\lambda_{i}-\lambda_{j}|\geq\Delta\sqrt{n}$.

Then we have proven that, for any $k\in\\{1,2,\cdots,d-1\\}$, $k$ distinct
subscripts $i_{1},\cdots,i_{k}\in\\{1,2,\cdots,d\\}$ and for any
$\delta_{i_{1}},\cdots,\delta_{i_{k}}>0$, we have