Random matrices: Universality of local eigenvalue statistics

Introduction

The goal of this paper is to establish a universality property for the local eigenvalue statistics for random matrices. To simplify the presentation, we are going to focus on Wigner Hermitian matrices, which are perhaps the most prominent model in the field. We emphasize however that our main theorem (Theorem 15) is stated in a much more general setting, and can be applied to various other models of random matrices (such as random real symmetric matrices, for example).

Let $n$ be a large number. A Wigner Hermitian matrix (of size $n$) is defined as a random Hermitian $n\times n$ matrix $M_{n}$ with upper triangular complex entries $\zeta_{ij}:=\xi_{ij}+\sqrt{-1}\tau_{ij}$ ($1\leq i<j\leq n$) and diagonal real entries $\xi_{ii}$ ($1\leq i\leq n$) where

For $1\leq i<j\leq n$, $\xi_{ij},\tau_{ij}$ are iid copies of a real random variable $\xi$ with mean zero and variance $1/2$.

Given an $n\times n$ Hermitian matrix $A$, we denote its $n$ eigenvalues as

The study of the eigenvalues $\lambda_{i}(W_{n})$ of (normalized) Wigner Hermitian matrices has been one of the major topics of study in random matrix theory. The properties of these eigenvalues are not only interesting in their own right, but also have been playing essential roles in many other areas of mathematics, such as mathematical physics, probability, combinatorics, and the theory of computing.

It will be convenient to introduce the following notation for frequent events depending on $n$, in increasing order of likelihood:

$E$ holds asymptotically almost surely ifSee Section 1.7 for our conventions on asymptotic notation. ${\mathbf{P}}(E)=1-o(1)$.

$E$ holds with high probability if ${\mathbf{P}}(E)\geq 1-O(n^{-c})$ for some constant $c>0$.

$E$ holds with overwhelming probability if ${\mathbf{P}}(E)\geq 1-O_{C}(n^{-C})$ for every constant $C>0$ (or equivalently, that ${\mathbf{P}}(E)\geq 1-\exp(-\omega(\log n))$).

$E$ holds almost surely if ${\mathbf{P}}(E)=1$.

Note from the union bound that the intersection of $O(n^{O(1)})$ many events with uniformly overwhelming probability, still has overwhelming probability. Unfortunately, the same is not true for events which are merely of high probability, which will cause some technical difficulties in our arguments.

A cornerstone of this theory is the Wigner semicircular law. Denote by $\rho_{sc}$ the semi-circle density function with support on $$,

Let $M_{n}$ be a Wigner Hermitian matrix. Then for any real number $x$,

in the sense of probability (and also in the almost sure sense, if the $M_{n}$ are all minors of the same infinite Wigner Hermitian matrix), where we use $|I|$ to denote the cardinality of a finite set $I$.

Wigner proved this theorem for special ensembles. The general version above is due to Pastur (see for a detailed discussion). The semi-circular law in fact holds under substantially more general hypotheses than those given in Definition 1, but we will not discuss this matter further here. One consequence of Theorem 5 is that we expect most of the eigenvalues of $W_{n}$ to lie in the interval $(-2+{\varepsilon},2+{\varepsilon})$ for ${\varepsilon}>0$ small; we shall thus informally refer to this region as the bulk of the spectrum.

Several stronger versions of Theorem 5 are known. For instance, it is known (see e.g. , ) that asymptotically almost surely, one has

for all $1\leq j\leq n$ and some absolute constant $\delta>0$, where $-2\leq t(a)\leq 2$ is defined by the formula

asymptotically almost surely (see for further discussion).

Theorem 5 addressed the global behavior of the eigenvalues. The local properties are much harder and their studies require much more sophisticated tools. Most of the precise theorems have been obtained for the GUE, defined in Example 2. In the next few paragraphs, we mention some of the most famous results concerning this model.

2. Distribution of the spacings (gaps) of the eigenvalues of GUE

In this section $M_{n}$ is understood to have the GUE distribution.

For a vector $x=(x_{1},\dots,x_{n})$ where $x_{1}<x_{2}\dots<x_{n}$, define the normalized gap distribution $S_{n}(s;x)$ by the formula

where $A_{n}:=\sqrt{n}M_{n}$ is the fine-scale normalization of $M_{n}$, and $p(\sigma)$ is the Gaudin distribution, given by the formula

where $K$ is the integral operator on $L^{2}((0,s))$ with the Dyson sine kernel

In fact a stronger result is known in the bulk of the spectrum. Let $l_{n}$ be any sequence of numbers tending to infinity such that $l_{n}/n$ tends to zero. Define

It is proved in that for any fixed $-2<u<2$, we have

The eigenvalue gap distribution has received much attention in the mathematics community, partially thanks to the fascinating (numerical) coincidence with the gap distribution of the zeros of the zeta functions. For more discussions, we refer to and the references therein.

3. k𝑘k-point correlation for GUE

In the GUE case, one has an explicit formula for $\rho_{n}^{(n)}$, obtained by Ginibre :

where $Z_{n}^{(2)}>0$ is a normalizing constant, known as the partition function. From this formula, one can compute $\rho_{n}^{(k)}$ explicitly. Indeed, it was established by Gaudin and Mehta that

where the kernel $K_{n}(x,y)$ is given by the formula

and $h_{0},\ldots,h_{n-1}$ are the first $n$ Hermite polynomials, normalized to be orthonormal with respect to $e^{-x^{2}}\ dx$. From this and the asymptotics of Hermite polynomials, it was shown by Dyson that

for any fixed $-2<u<2$ and real numbers $t_{1},\dots,t_{k}$, where the Dyson sine kernel $K$ was defined in (6).

4. The universality conjecture and previous results

It has been conjectured, since the 1960s, by Wigner, Dyson, Mehta, and many others, that the local statistics (such as the above limiting distributions) are universal, in the sense that they hold not only for the GUE, but for any other Wigner random matrix also. This conjecture was motivated by similar phenomena in physics, such as the same laws of thermodynamics, which should emerge no matter what the details of atomic interaction.

The universality conjecture is one of the central questions in the theory of random matrices. In many cases, it is stated for a specific local statistics (such as the gap distribution or the $k$-point correlation, see [33, page 9] for example). These problems have been discussed in numerous books and surveys (see ).

Despite the conjecture’s long and distinguished history and the overwhelming supporting numerical evidence, rigorous results on this problem for general Wigner random matrices have only begun to emerge recently. At the edge of the spectrum, Soshnikov proved the universality of the joint distribution of the largest $k$ eigenvalues (for any fixed $k$), under the extra assumption that the atom distribution is symmetric:

Let $k$ be a fixed integer and $M_{n}$ be a Wigner Hermitian matrix, whose atom distribution is symmetric. Set $W_{n}:=\frac{1}{\sqrt{n}}M_{n}$. Then the joint distribution of the $k$ dimensional random vector

has a weak limit as $n\rightarrow\infty$, which coincides with that in the GUE case. The result also holds for the smallest eigenvalues $\lambda_{1},\dots,\lambda_{k}$.

Note that this significantly strengthens (4) in the symmetric case. (For the non-symmetric case, see , for some recent results).

Returning to the bulk of the spectrum, Johansson proved (11) and (8) for random Hermitian matrices whose entries are gauss divisible. (See also the paper of Ben Arous and Péché where they discussed the removal of a technical condition in .) More precisely, Johansson considered the model $M_{n}=(1-t)^{1/2}M^{1}_{n}+t^{1/2}M^{2}_{n}$, where $0<t\leq 1$ is fixed (i.e. independent of $n$), $M^{1}_{n}$ is a Wigner Hermitian matrix and $M^{2}_{n}$ is a GUE matrix independent of $M^{1}_{n}$. We will refer to such matrices as Johansson matrices.

(11) (in the weak sense) and (8) (and hence (5)) hold for Johansson matrices, as $n\rightarrow\infty$. By “weak sense”, we mean that

The property of being gauss divisible can be viewed as a strong regularity assumption on the atom distribution. Very recently, Erdős, Peche, Ramirez, Schlein and Yau , have relaxed this regularity assumption significantly. In particular in an analogue of Theorem 8 (with $k=2$ for the correlation and $l_{n}$ polynomial in $n$ for the gap distribution) is proven assuming that the atom distribution is of the form

where $V(x)\in C^{6}$ and $\sum_{i=1}^{6}|V^{j}(x)|\leq C(1+x^{2})^{k}$ and $\nu(x)\leq C^{\prime}\exp(-\delta x^{2})$, for some fixed $k,\delta,C,C^{\prime}$. It was remarked in that the last (exponential decay) assumption can be weakened somewhat.

We note that both Erdős et al and our approach make important, but different use of the ideas and results by Erdos,Schlein and Yau () concerning the rate of convergence to the semi-circle law. (See page 24 and Section 5 for a detailed description.)

Finally, let us mention that in a different direction, universality was established by Deift, Kriecherbauer, McLaughlin, Venakides and Zhou, , Pastur and Shcherbina , Bleher and Its for a different model of random matrices, where the joint distribution of the eigenvalues is given explicitly by the formula

where $V$ is a general function and $c_{n}>0$ is a normalization factor. The case $V=x^{2}$ corresponds to (9). For a general $V$, the entries of the matrix are correlated, and so this model differs from the Wigner model. (See for some recent developments concerning these models, which are studied using the machinery of orthogonal polynomials.)

One of the main difficulties in establishing universality for general matrix ensembles lies in the fact that most of the results obtained in the GUE case (and the case in Johansson’s theorem and those in ) came from heavy use of the explicit joint distribution of the eigenvalues such as (9) and (13). The desired limiting distributions were proved using estimates on integrals with respect to these measures. Very powerful tools have been developed to handle this task (see for example), but they cannot be applied for general Wigner matrices where an explicit measure is not available.

Nevertheless, some methods have been developed which do not require the explicit joint distribution. For instance, Soshnikov’s result was obtained using the (combinatorial) trace method rather than from an explicit formula from the distribution, although it is well understood that this method, while efficient for the studying of the edge, is of much less use in the study of the spacing distribution in the bulk of the spectrum. The recent argument in also avoid explicit formulae, relying instead on an analysis of the Dyson Brownian motion, which describes the stochastic dynamics of the spectrum of Johansson matrices $M_{n}=(1-t)^{1/2}M^{1}_{n}+t^{1/2}M^{2}_{n}$ in the $t$ variable. (On the other hand, the argument in uses explicit formulae for the joint distribution.) However, it appears that their method still requires a high degree of regularity on the atom distribution, whereas here we shall be interested in methods that do not require any regularity hypotheses at all (and in particular will be applicable to discrete atom distributionsSubsequently to the release of this paper, we have realized that the two methods can in fact be combined to address the gap distribution problem and the $k$-point correlation problem even for discrete distributions without requiring moment conditions; see for details..

5. Universality theorems

In this paper, we introduce a new method to study the local statistics. This method is based on the Lindeberg strategy of replacing non-gaussian random variables with gaussian ones. (For more modern discussions about Lindeberg’s method, see .) Using this method, we are able to prove universality for general Wigner matrices under very mild assumptions. For instance, we have

The limiting gap distribution (5) holds for Wigner Hermitian matrices whose atom distribution $\xi$ has support on at least 3 points. The stronger version (8) holds for Wigner Hermitian matrices whose atom distribution $\xi$ has support on at least 3 points and the third moment ${\mathbf{E}}\xi^{3}$ vanishes.

Our method also enables us to prove the universality of the variance and higher moments. Thus, the whole distribution of $S_{n}(s,\lambda)$ is universal, not only its expectation. See Remark 31.

The $k$-point correlation (11) (in the weak sense) holds for Wigner Hermitian matrices whose atom distribution $\xi$ has support on at least 3 points and the third moment ${\mathbf{E}}\xi^{3}$ vanishes.

These theorems (and several others, see Section 1.6) are consequences of our more general main theorem below (Theorem 15). Roughly speaking, Theorem 15 states that the local statistics of the eigenvalues of a random matrix is determined by the first four moments of the atom distributions.

Theorem 15 applies in a very general setting. We will consider random Hermitian matrix $M_{n}$ with entries $\xi_{ij}$ obeying the following condition.

A random Hermitian matrix $A_{n}=(\zeta_{ij})_{1\leq i,j\leq n}$ is said to obey condition C0 if

The $\zeta_{ij}$ are independent (but not necessarily identically distributed) for $1\leq i\leq j\leq n$, and have mean zero and variance $1$.

(Uniform exponential decay) There exist constants $C,C^{\prime}>0$ such that

for all $t\geq C^{\prime}$ and $1\leq i,j\leq n$.

Clearly, all Wigner Hermitian matrices obey condition C0. However, the class of matrices obeying condition C0 is much richer. For instance the gaussian orthogonal ensemble (GOE), in which $\zeta_{ij}\equiv N(0,1)$ independently for all $i<j$ and $\zeta_{ii}\equiv N(0,2)$, is also essentially of this formNote that for GOE an diagonal entry has variance $2$ rather than $1$. We thank Sean O’Rourke for pointing out this issue. On the other hand, Theorem 15 still holds if we change the variances of the diagonal entries, see Remark 16, and so are all Wigner real symmetric matrices (the definition of which is given at the end of this section).

We say that two complex random variables $\zeta$ and $\zeta^{\prime}$ match to order $k$ if

for all $m,l\geq 0$ such that $m+l\leq k$.

Given two random matrices $A_{n}=(\zeta_{ij})_{1\leq i,j\leq n}$ and $A^{\prime}_{n}=(\zeta^{\prime}_{ij})_{1\leq i,j\leq n}$ obeying condition C0, $\zeta_{ij}$ and $\zeta^{\prime}_{ij}$ automatically match to order $1$. If they are both Wigner Hermitian matrices, then they automatically match to order $2$. If furthermore they are also symmetric (i.e. $A_{n}$ has the same distribution as $-A_{n}$, and similarly for $A^{\prime}_{n}$ and $-A^{\prime}_{n}$) then $\zeta_{ij}$ and $\zeta^{\prime}_{ij}$ automatically match to order $3$.

If $\zeta_{ij}$ and $\zeta^{\prime}_{ij}$ only match to order $3$ rather than $4$, then there is a positive constant $C$ independent of $c_{0}$ such that the conclusion (16) still holds provided that one strengthens (15) to

The proof of this theorem begins at Section 3.3. As mentioned earlier, Theorem 15 asserts (roughly speaking) that the fine spacing statistics of a random Hermitian matrix in the bulk of the spectrum are only sensitive to the first four moments of the entries. It may be possible to reduce the number of matching moments in this theorem, but this seems to require a refinement to the method; see Section 3.2 for further discussion.

Theorem 15 still holds if we assume that the diagonal entries $\zeta_{ii}$ and $\zeta_{ii}^{\prime}$ have the same mean and variance, for all $1\leq i\leq n$, but these means and variances can be different at different $i$. The proof is essentially the same. In our analysis, we consider the random vector formed by non-diagonal entries of a row, and it is important that these entries have mean zero and the same variance, but the mean and variance of the diagonal entry never plays a role. Details will appear elsewhere.

In a subsequent paper , we show that the condition ${\varepsilon}n\leq i_{1}<i_{2}\dots<i_{k}\leq(1-{\varepsilon})n$ can be omitted. In other words, Theorem 15 also holds for eigenvalues at the edge of the spectrum.

Applying Theorem 15 for the special case when $M^{\prime}_{n}$ is GUE, we obtain

Let $M_{n}$ be a Wigner Hermitian matrix whose atom distribution $\xi$ satisfies ${\mathbf{E}}\xi^{3}=0$ and $E\xi^{4}=\frac{3}{4}$ and $M_{n}^{\prime}$ be a random matrix sampled from GUE. Then with $G$, $A_{n}$, $A^{\prime}_{n}$ as in the previous theorem, and $n$ sufficiently large, one has

In the proof of Theorem 15, the following lower tail estimate on the consecutive spacings plays an important role. This theorem is of independent interest, and will also help in applications of Theorem 15.

Let $0<{\varepsilon}<1$ be a constant, and let $M_{n}$ be a random matrix obeying Condition C0. Set $A_{n}:=\sqrt{n}M_{n}$. Then for every $c_{0}>0$, and for $n$ sufficiently large depending on ${\varepsilon}$, $c_{0}$ and the constants $C,C^{\prime}$ in Definition 12, and for each ${\varepsilon}n\leq i\leq(1-{\varepsilon})n$, one has $\lambda_{i+1}(A_{n})-\lambda_{i}(A_{n})\geq n^{-c_{0}}$ with high probability. In fact, one has

for some $c_{1}>0$ depending on $c_{0}$ (and independent of ${\varepsilon}$).

The proof of this theorem begins at Section 3.5.

6. Applications

By using Theorem 15 and Theorem 19 in combination with existing results in the literature for GUE (or other special random matrix ensembles) one can establish universal asymptotic statistics for a wide range of random matrices. For instance, consider the $i^{th}$ eigenvalue $\lambda_{i}(M_{n})$ of a Wigner Hermitian matrices. In the GUE case, Gustavsson, based on , proved that $\lambda_{i}$ has gaussian fluctuation:

Let $i=i(n)$ be such that $i/n\to c$ as $n\to\infty$ for some $0<c<1$. Let $M_{n}$ be drawn from the GUE. Set $A_{n}:=\sqrt{n}M_{n}$. Then

in the sense of distributions, where $t()$ is defined in (3). (More informally, we have $\lambda_{i}(M_{n})\approx t(i/n)\sqrt{n}+N(0,\frac{2\log n}{(4-t(i/n)^{2})n})$.)

As an application of our main results, we have

The conclusion of Theorem 20 also holds for any other Wigner Hermitian matrix $M_{n}$ whose atom distribution $\xi$ satisfies ${\mathbf{E}}\xi^{3}=0$ and ${\mathbf{E}}\xi^{4}=\frac{3}{4}$.

Let $M_{n}$ be a Wigner Hermitian matrix, and let $M^{\prime}_{n}$ be drawn from GUE. Let $i,c,t$ be as in Theorem 20, and let $c_{0}$ be as in Theorem 19. In view of Theorem 20, it suffices to show that

for all intervals $I=[a,b]$, and $n$ sufficiently large depending on $i$ and the constants $C,C^{\prime}$ in Definition 1, where $I_{+}:=[a-n^{-c_{0}/10},b+n^{-c_{0}/10}]$ and $I_{-}:=[a+n^{-c_{0}/10},b-n^{-c_{0}/10}]$.

On the other hand, one can choose $G$ to obey (15). Thus by Corollary 18 we have

and the second inequality in (18) follows from the triangle inequality. The first inequality is similarly proven using a smooth function that equals $1$ on $I_{-}$ and vanishes outside of $I$. ∎

The same argument lets one establish the universality of the asymptotic joint distribution law for any $k$ eigenvalues $\lambda_{i_{1}}(M_{n}),\ldots,\lambda_{i_{k}}(M_{n})$ in the bulk of the spectrum of a Wigner Hermitian matrix for any fixed $k$ (the GUE case is treated in ). In particular, we have the generalization

for all $i_{1},\ldots,i_{k}$ between ${\varepsilon}n$ and $(1-{\varepsilon})n$ for some fixed ${\varepsilon}>0$, and all intervals $I_{1},\ldots,I_{k}$, assuming $n$ is sufficiently large depending on ${\varepsilon}$ and $k$, and $I_{j,-}\subset I_{j}\subset I_{j,+}$ are defined as in the proof of Corollary 21. The details are left as an exercise to the interested reader.

Another quantity of interest is the least singular value

of a Wigner Hermitian matrix. In the GUE case, we have the following asymptotic distribution:

[1, Theorem 3.1.2], For any fixed $t>0$, and $M_{n}$ drawn from GUE, one has

with the asymptotics $f(t)=\frac{-t}{\pi}-\frac{t^{2}}{\pi^{2}}-\frac{t^{3}}{\pi^{3}}+O(t^{4})$ as $t\to 0$.

Using our theorems, we can extend this result to more general ensembles:

The conclusions of Theorem 23 also hold for any other Wigner Hermitian matrix $M_{n}$ whose atom distribution $\xi$ has ${\mathbf{E}}\xi^{3}=0$ and ${\mathbf{E}}\xi^{4}=\frac{3}{4}$.

Let $M_{n}$ be a Wigner Hermitian matrix, and let $M^{\prime}_{n}$ be drawn from GUE. Let $N_{I}$ be the number of eigenvalues of $W^{\prime}_{n}$ in an interval $I$. It is well known (see [1, Chapter 4]) that

asymptotically almost surely (cf. (2) and Theorem 20). Applying this fact to the two intervals $I=[-\infty,\pm\frac{t}{2\sqrt{n}}]$, we conclude that

for either choice of sign $\pm$. Using (18) (or (19)) (and modifying $t$ slightly), we conclude that the same statement is true for $M_{n}$. In particular, we have

and similarly for $M^{\prime}_{n}$. Using (19), we see that

for some $c>0$. Putting this together, we conclude that

A similar universality result for the least singular value of non-Hermitian matrices was recently established by the authors in . Our arguments in also used the Lindeberg strategy, but were rather different in many other respects (in particular, they proceeded by analyzing random submatrices of the inverse matrix $M_{n}^{-1}$). One consequence of Corollary 24 is that $M_{n}$ is asymptotically almost surely invertible. For discrete random matrices, this is already a non-trivial fact, first proven in . If Theorem 23 can be extended to the Johansson matrices considered in , then the arguments below would allow one to remove the fourth moment hypothesis in Corollary 24 (assuming that $\xi$ is supported on at least three points).

The above corollary still holds under a weaker assumption that the first three moments of $\xi$ match those of the gaussian variable; in other words, we can omit the last assumption that ${\mathbf{E}}\xi^{4}=3/4$. Details will appear else where.

By combining this result with (4) one also obtains a universal distribution for the condition number $\sigma_{1}(M_{n})/\sigma_{n}(M_{n})$ of Wigner Hermitian matrices (note that the non-independent nature of $\sigma_{1}(M_{n})$ and $\sigma_{n}(M_{n})$ is not relevant, because (4) gives enough concentration of $\sigma_{1}(M_{n})$ that it can effectively be replaced with $2\sqrt{n}$). We omit the details.

Now we are going to prove the first part of Theorem 9. Note that in contrast to previous applications, we are making no assumptions on the third and fourth moments of the atom distribution $\xi$. The extra observation here is that we do not always need to compare $M_{n}$ with GUE. It is sufficient to compare it with any model where the desired statistics have been computed. In this case, we are going to compare $M_{n}$ with a Johansson matrix. The definition of Johansson matrices provides more degrees of freedom via the parameters $t$ and $M_{n}^{1}$, and we can use this to remove the condition of the third and fourth moments.

Let $\xi$ be a real random variable with mean zero, variance $1$, third moment ${\mathbf{E}}\xi^{3}=\alpha_{3}$, and fourth moment ${\mathbf{E}}\xi^{4}=\alpha_{4}<\infty$. Then $\alpha_{4}-\alpha_{3}^{2}-1\geq 0$, with equality if and only if $\xi$ is supported on exactly two points. Conversely, if $\alpha_{4}-\alpha_{3}^{2}-1\geq 0$, then there exists a real random variable with the specified moments.

setting $b:=-1$ and $a:=-\alpha_{3}$ we obtain the inequality $\alpha_{4}-\alpha_{3}^{2}-1\geq 0$. Equality only occurs when ${\mathbf{E}}(\xi^{2}-\alpha_{3}\xi-1)^{2}=0$, which by the quadratic formula implies that $\xi$ is supported on at most two points.

Now we show that every pair $(\alpha_{3},\alpha_{4})$ with $\alpha_{4}-\alpha_{3}^{2}-1\geq 0$ arises as the moments of a random variable with mean zero and variance $1$. The set of all such moments is clearly convex, so it suffices to check the case when $\alpha_{4}-\alpha_{3}^{2}-1=0$. But if one considers the random variable $\xi$ which equals $\tan\theta$ with probability $\cos^{2}\theta$ and $-\cot\theta$ with probability $\sin^{2}\theta$ for some $-\pi/2<\theta<\pi/2$, one easily computes that $\xi$ has mean zero, variance $1$, third moment $-2\cot(2\theta)$, and fourth moment $4\operatorname{cosec}(2\theta)-3$, and the claim follows from the trigonometric identity $\operatorname{cosec}(2\theta)^{2}=\cot(2\theta)^{2}+1$. ∎

The more general truncated moment problem (i.e., the truncated version of the classical Hamburger moment sequence problem, see ) was solved by Curto and Fialkow .

Let $\xi$ be a real random variable with mean zero and variance $1$, which is supported on at least three points. Then $\xi$ matches to order $4$ with $(1-t)^{1/2}\xi^{\prime}+t^{1/2}\xi_{G}$ for some $0<t<1$ and some independent $\xi^{\prime},\xi_{G}$ of mean zero and variance $1$, where $\xi_{G}\equiv N(0,1)$ is Gaussian.

The formal characteristic function ${\mathbf{E}}e^{s\xi}:=\sum_{j=0}^{\infty}\frac{s^{j}}{j!}{\mathbf{E}}\xi^{j}$ has the expansion $1+\frac{1}{2}s^{2}+\frac{1}{6}\alpha_{3}s^{3}+\frac{1}{24}\alpha_{4}s^{4}+O(s^{5})$; by Lemma 28, we have $\alpha_{4}-\alpha_{3}^{2}-1>0$. Observe that $\xi$ will match to order $4$ with $(1-t)^{1/2}\xi^{\prime}+t^{1/2}\xi_{G}$ if and only if one has the identity

where $\alpha^{\prime}_{3},\alpha^{\prime}_{4}$ are the moments of $\xi^{\prime}$. Formally dividing out by $1+\frac{t}{2}s^{2}+\frac{t}{8}s^{4}$, one can thus solve for $\alpha^{\prime}_{3},\alpha^{\prime}_{4}$ in terms of $\alpha_{3},\alpha_{4}$. Observe that as $t\to 0$, $\alpha^{\prime}_{3},\alpha^{\prime}_{4}$ must converge to $\alpha_{3},\alpha_{4}$ respectively. Thus, for $t$ sufficiently small, we will have $\alpha^{\prime}_{4}-(\alpha^{\prime}_{3})^{2}-1>0$. The claim now follows from Lemma 28. ∎

(Proof of the first part of Theorem 9) Let $M_{n}$ be as in this theorem and consider (5). By Corollary 30, we can find a Johansson matrix $M^{\prime}_{n}$ which matches $M_{n}$ to order $4$. By Theorem 8, (5) already holds for $M^{\prime}_{n}$. Thus it will suffice to show that

By (7) and linearity of expectation, it suffices to show that

uniformly for all ${\varepsilon}n\leq i\leq(1-{\varepsilon})n$, for each fixed ${\varepsilon}>0$. But this follows by a modification of the argument used to prove (18) (or (19)), using a function $G(x,y)$ of two variables which is a smooth approximant to the indicator function of the half-space $\{y-x\leq s\}$ (and using Theorem 19 to errors caused by shifting $s$); we omit the details. The second part of the theorem will be treated together with Theorem 11. ∎

By considering ${\mathbf{P}}(\{\lambda_{i+1}(A_{n})-\lambda_{i}(A_{n})\leq s\}\wedge\{\lambda_{j+1}(A_{n})-\lambda_{j}(A_{n})\leq s\})$ we can prove the universality of the variance of $S_{n}(s,\lambda)$. The same applies for higher moments.

The proof of Theorem 11 is a little more complicated. We first need a strengthening of (2) which may be of independent interest.

Let $M_{n}$ be a Wigner Hermitian matrix whose atom distribution $\xi$ has vanishing third moment. Then for any fixed $c>0$ and ${\varepsilon}>0$, and any ${\varepsilon}n\leq j\leq(1-{\varepsilon})n$, one has

asymptotically almost surely, where $t()$ was defined in (3).

asymptotically almost surely. Let $M^{\prime}_{n}$ be drawn from GUE, thus the off-diagonal entries of $M_{n}$ and $M^{\prime}_{n}$ match to third order. From (20) we have

asymptotically almost surely. The claim now follows from the last part of Theorem 15, letting $G=G(\lambda_{j})$ be a smooth cutoff equal to $1$ on $\left[t\left(\frac{j}{n}\right)n-n^{+c}/2,t\left(\frac{j}{n}\right)n+n^{+c}/2\right]$ and vanishing outside of $\left[t\left(\frac{j}{n}\right)n-n^{+c},t\left(\frac{j}{n}\right)n+n^{c}\right]$. ∎

Fix $k,u$, and let $M_{n}$ be as in Theorem 11. By Corollary 30, we can find a Johansson matrix $M^{\prime}_{n}$ whose entries match $M_{n}$ to fourth order. By Theorem 8 (and a slight rescaling), it suffices to show that the quantity

only changes by $o(1)$ when the matrix $M_{n}$ is replaced with $M^{\prime}_{n}$, for any fixed test function $f$. By an approximation argument we can take $f$ to be smooth.

for each individual $i_{1},\ldots,i_{k}$ and some absolute constant $c_{0}>0$. Meanwhile, by Theorem 32, we see that asymptotically almost surely, the only $i_{1},\ldots,i_{k}$ which contribute to (22) lie within $O(n^{c})$ of $t^{-1}(u)n$, where $c>0$ can be made arbitrarily small. The claim then follows from the triangle inequality (choosing $c$ small enough compared to $c_{0}$). ∎

This proof is similar to the one above. We already know that ${\mathbf{P}}(\lambda_{i+1}-\lambda_{i}\leq s)$ is basically the same in the two models ($M_{n}$ and $M^{\prime}_{n}$). Theorem 32 now shows that after fixing a small neighborhood of $u$, the interval of indices $i$ that involve fluctuates by at most $n^{c}$, where $c$ can be made arbitrarily small. ∎

In fact, in the above applications, we only need Theorem 32 to hold for Johansson matrices. Thus, in order to remove the third moment assumption, it suffices to have this theorem for Johansson matrices (without the third moment assumption). We believe this is within the power of the determinant process method, but do not pursue this direction here.

As another application, we can prove the following asymptotic for the determinant (and more generally, the characteristic polynomial) of a Wigner Hermitian matrix. The detailed proof is deferred to Appendix A.

Let $M_{n}$ be a Wigner Hermitian matrix whose atom distribution $\xi$ has vanishing third moment and is supported on at least three points. Then there is a constant $c>0$ such that

More generally, for fixed any complex number $z$, one has

where the decay rate of $o(1)$ is allowed to depend on $z$.

A similar result was established for iid random matrices in (see also for a refinement), based on controlling the distance from a random vector to a subspace. That method relied heavily on the joint independence of all entries and does not seem to extend easily to the Hermitian case. We also remark that a universality result for correlations of the characteristic polynomial has recently been established in .

Let us now go beyond the model of Wigner Hermitian matrices. As already mentioned, our main theorem also applies for real symmetric matrices. In the next paragraphs, we formulate a few results one can obtain in this direction.

Let $n$ be a large number. A Wigner symmetric matrix (of size $n$) is a random symmetric matrix $M_{n}=(\xi_{ij})_{1\leq i,j\leq n}$ where for $1\leq i<j\leq n$, $\xi_{ij}$ are iid copies of a real random variable $\xi$ with mean zero, variance $1$, and exponential decay (as in Definition 1), while for $1\leq i=j\leq n$, $\xi_{ii}$ are iid copies of a real random variable $\xi^{\prime}$ with mean zero, variance $2$, and exponential decay. We set $W_{n}:=\frac{1}{\sqrt{n}}M_{n}$ and $A_{n}:=\sqrt{n}M_{n}$ as before.

The Gaussian orthogonal ensemble (GOE) is the Wigner symmetric matrix in which the off-diagonal atom distribution $\xi$ is the Gaussian $N(0,1)$, and the diagonal atom distribution $\xi^{\prime}$ is $N(0,2)$.

As remarked earlier, while the Wigner symmetric matrices do not, strictly speaking, obey Condition C0 due to the diagonal variance being $2$ instead of $1$, it is not hard to verify that all the results in this paper continue to hold after changing the diagonal variance to $2$. As a consequence, we can easily deduce the following analogue of Theorems 9 and 11.

The limiting gap distribution and $k$-correlation function of Wigner symmetric real matrices with atom variable $\sigma$ satisfying ${\mathbf{E}}\sigma^{3}=0$ and ${\mathbf{E}}\sigma^{4}=3$ are the same as those for GOE. (The explicit formulae for the limiting gap distribution and $k$-correlation function for GOE can be found in . The limit of the $k$-correlation function is again in the weak sense.)

The proof of Theorem 38 is similar to that of Theorems 9, 11 and is omitted. The reason that we need to match the moments to order $4$ here (compared to lower orders in Theorems 9 and 11) is that there is currently no analogue of Theorem 8 for the GOE. Once such a result becomes available, the order automatically reduces to those in Theorems 9 and 11, respectively.

Finally let us mention that our results can be refined and extended in several directions. For instance, we can handle Hermitian matrices whose upper triangular entries are still independent, but having a non-trivial covariance matrix (the real and imaginary parts need not be independent). The diagonal entries can have mean different from zero (which, in the case the off-diagonal entries are gaussian, corresponds to gaussian matrices with external field and has been studied in ) and we can obtain universality results in this case as well. We can also refine our argument to prove universality near the edge of the spectrum. These extensions and many others will be discussed in a subsequent paper.

7. Notation

We consider $n$ as an asymptotic parameter tending to infinity. We use $X\ll Y$, $Y\gg X$, $Y=\Omega(X)$, or $X=O(Y)$ to denote the bound $X\leq CY$ for all sufficiently large $n$ and for some constant $C$. Notations such as $X\ll_{k}Y,X=O_{k}(Y)$ mean that the hidden constant $C$ depend on another constant $k$. $X=o(Y)$ or $Y=\omega(X)$ means that $X/Y\rightarrow 0$ as $n\rightarrow\infty$; the rate of decay here will be allowed to depend on other parameters. The eigenvalues are always ordered increasingly.

Preliminaries: Tools from linear algebra and probability

It is useful to keep in mind the (Courant-Fisher) minimax characterization of the eigenvalues

From this, one easily obtain Weyl’s inequality

Another consequence of the minimax formula is the Cauchy interlacing inequality

for all $1\leq i<n$, whenever $A_{n}$ is an $n\times n$ Hermitian matrix and $A_{n-1}$ is the top $n-1\times n-1$ minor. In a similar spirit, one has

for all $1\leq i<n$, whenever $A,B$ are $n\times n$ Hermitian matrices with $B$ being positive semi-definite and rank $1$. If $B$ is instead negative semi-definite, one has

Let $A,B$ be Hermitian matrices of the same size where $B$ has rank one. Then for any interval $I$,

where $N_{I}(M)$ is the number of eigenvalues of $M$ in $I$.

One also has the following more precise version of the Cauchy interlacing inequality:

By diagonalising $A_{n-1}$ (noting that this does not affect either side of (25)), we may assume that $A_{n-1}=\operatorname{diag}(\lambda_{1}(A_{n-1}),\ldots,\lambda_{n-1}(A_{n-1}))$ and $u_{j}(A_{n-1})=e_{j}$ for $j=1,\ldots,n-1$. One then easily verifies that the characteristic polynomial $\det(A_{n}-\lambda I)$ of $A_{n}$ is equal to

when $\lambda$ is distinct from $\lambda_{1}(A_{n-1}),\ldots,\lambda_{n-1}(A_{n-1})$. Since $u_{j}(A_{n-1})^{*}X$ is non-zero by hypothesis, we see that this polynomial does not vanish at any of the $\lambda_{j}(A_{n-1})$. Substituting $\lambda_{i}(A_{n})$ for $\lambda$, we obtain (25). ∎

The following lemma will be useful to control the coordinates of eigenvectors.

where $u_{j}(A_{n-1})$ is a unit eigenvector corresponding to the eigenvalue $\lambda_{j}(A_{n-1})$.

By subtracting $\lambda_{i}(A)I$ from $A$ we may assume $\lambda_{i}(A)=0$. The eigenvector equation then gives

Since $\|v^{\prime}\|^{2}+|x|^{2}=1$, we conclude

Since $\|A_{n-1}^{-1}X\|^{2}=\sum_{j=1}^{n-1}(\lambda_{j}(A_{n-1}))^{-2}|u_{j}(A_{n-1})^{*}X|^{2}$, the claim follows. ∎

The Stieltjes transform $s_{n}(z)$ of a Hermitian matrix $W$ is defined for complex $z$ by the formula

It has the following alternate representation (see e.g. [2, Chapter 11]):

Let $W=(\zeta_{ij})_{1\leq i,j\leq n}$ be a Hermitian matrix, and let $z$ be a complex number not in the spectrum of $W$. Then we have

By Schur’s complement, $\frac{1}{\zeta_{kk}-z-a_{k}^{*}(W_{k}-zI)^{-1}a_{k}}$ is the $k^{th}$ diagonal entry of $(W-zI)^{-1}$. Taking traces, one obtains the claim. ∎

2. Tools from Probability

We will make frequent use of the following lemma, whose proof is presented in Appendix B. This lemma is a generalization of a result in .

Another useful tool is the following theorem, which is a corollary of a more general theorem proved in Appendix D.

for some $\sigma>0$. Let $\zeta_{1},\ldots,\zeta_{n}$ be independent complex random variables with mean zero, variance ${\mathbf{E}}|\zeta_{j}|^{2}$ equal to $1$, and obeying ${\mathbf{E}}|\zeta_{i}|^{3}\leq C$ for some $C\geq 1$. For each $1\leq i\leq N$, let $S_{i}$ be the complex random variable

(Upper tail bound on $S_{i}$) For $t\geq 1$, we have ${\mathbf{P}}(|S_{i}|\geq t)\ll\exp(-ct^{2})+C\sigma$ for some absolute constant $c>0$.

(Lower tail bound on $\vec{S}$) For any $t\leq\sqrt{N}$, one has ${\mathbf{P}}(|\vec{S}|\leq t)\ll O(t/\sqrt{N})^{\lfloor N/4\rfloor}+CN^{4}t^{-3}\sigma$.

Overview of argument

We now give a high-level proof of our main results, Theorem 15 and Theorem 19, contingent on several technical propositions that we prove in later sections.

In the hypotheses of Theorem 15 and Theorem 19, it is assumed that one has the uniform exponential decay property (14) on the coefficients $\zeta_{ij}$ on the random matrix $M_{n}$. From this and the union bound, we thus see that

with overwhelming probability. Since events of probability less than, say, $O(n^{-100})$ are negligible for the conclusion of either Theorem 15 or Theorem 19, we may thus apply a standard truncation argument (see e.g. ) and redefine the atom variables $\zeta_{ij}$ on the events where their magnitude exceeds $\log^{C+1}n$, so that one in fact has

almost surely. (This modification may affect the first, second, third, and fourth moments on the real and imaginary parts of the $\zeta_{ij}$ by a very small factor (e.g. $O(n^{-10})$), but one can easily compensate for this by further adjustment of the $\zeta_{ij}$, using the Weyl inequalities (23) if necessary; we omit the details.) Thus we will henceforth assume that (27) holds for proving both Theorem 15 and Theorem 19.

If one only assumed some finite number of moment conditions on $\zeta_{ij}$, rather than the exponential condition (14), then one could only truncate the $|\zeta_{ij}|$ to be of size $n^{1/C_{0}}$ for some constant $C_{0}$ rather than polylogarithmic in $n$. While several of our arguments extend to this setting, there is a key induction on $n$ argument in Section 3.5 that seems to require $|\zeta_{ij}|$ to be of size $n^{o(1)}$ or better, which is the main reason why our results are restricted to random variables of exponential decay. However, this appears to be a largely technical restriction, and it seems very plausible that the results of this paper can be extended to atom distributions that are only assumed to have a finite number of moments bounded.

For technical reasons, it is also convenient to make the qualitative assumption that the $\zeta_{ij}$ have an (absolutely) continuous distribution in the complex plane, rather than a discrete one. This is so that pathological events such as eigenvalue collision will only occur with probability zero and can thus be ignored (though one of course still must deal with the event that two eigenvalues have an extremely small but non-zero separation). None of our bounds will depend on any quantitative measure of how continuous the $\zeta_{ij}$ are, so one can recover the discrete case from the continuous one by a standard limiting argument (approximating a discrete distribution by a smooth one while holding $n$ fixed, and using the Weyl inequalities (23) to justify the limiting process); we omit the details.

2. Proof strategy for Theorem 15

For sake of exposition let us restrict attention to the case $k=1$, thus we wish to show that the expectation ${\mathbf{E}}G(\lambda_{i}(A_{n}))$ of the random variable $G(\lambda_{i}(A_{n}))$ only changes by $O(n^{-c_{0}})$ if one replaces $A_{n}$ with another random matrix $A^{\prime}_{n}$ with moments matching up to fourth order off the diagonal (and up to second order on the diagonal). To further simplify the exposition, let us suppose that the coefficients $\zeta_{pq}$ of $A_{n}$ (or $A^{\prime}_{n}$) are real-valued rather than complex-valued.

Let us freeze (or condition on) all the entries of $A_{n}$ except for the $pq$ and $qp$ entries. For any complex number $z$, let $A(z)$ denote the matrix which equals $A_{n}$ except at the $pq$, $qp$, entries, where it equals $z$ and $\overline{z}$ respectively. (Actually, with our hypotheses, we only need to consider real-valued $z$.) Thus it would suffice to show that

for all (or at least most) choices of the frozen entries of $A_{n}$, where $F(z):=G(\lambda_{i}(A(z)))$. Note from (27) that we only care about values of $z$ of size $O(n^{1/2+o(1)})$.

Suppose we could show the derivative estimates

for $l=1,2,3,4,5$. (If $z$ were complex-valued rather than real, we would need to differentiate in the real and imaginary parts of $z$ separately, as $F$ is not holomorphic, but let us ignore this technicality for now.) Then by Taylor’s theorem with remainder, we would have

and similarly for $F(\sqrt{n}\zeta^{\prime}_{pq})$. Since $n^{-5/2+O(c_{0})+o(1)}=O(n^{-2-c_{0}})$ for $n$ large enough and $c_{0}$ small enough, we thus obtain the claim (28) thanks to the hypothesis that the first four moments of $\zeta_{pq}$ and $\zeta^{\prime}_{pq}$ match. (Note how this argument barely fails if only three moments are assumed to match, though it is possible that some refinement of this argument might still succeed by exploiting further cancellations in the fourth order term $\frac{1}{4!}F^{(4)}(0)\sqrt{n}^{4}\zeta_{pq}^{4}$.)

Now we discuss why one would expect an estimate such as (29) to be plausible. For simplicity we first focus attention on the easiest case $l=1$, thus we now wish to show that $F^{\prime}(z)=O(n^{-1+O(c_{0})+o(1)})$. By (15) and the chain rule, it suffices to show that

A crude application of the Weyl bound (23) gives $\frac{d}{dz}\lambda_{i}(A(z))=O(1)$, which is not good enough for what we want (although in the actual proof, we will take advantage of a variant of this crude bound to round $z$ off to the nearest multiple of $n^{-100}$, which is useful for technical reasons relating to the union bound). But we can do better by recalling the Hadamard first variation formula

Now suppose we wish to establish the $l=2$ version of (29). Again applying the chain rule, we would now seek to establish the bound

For this, we apply the Hadamard second variation formula

where $\pi_{u_{i}(A(z))^{\perp}}$ is the orthogonal projection to the orthogonal complement $u_{i}(A(z))^{\perp}$ of $u_{i}(A(z))$, and $(A(z)-\lambda_{i}(A(z))I)^{-1}$ is the inverse of $A(z)-\lambda_{i}(A(z))$ on that orthogonal complement. (This formula is valid as long as the eigenvalues $\lambda_{j}(A(z))$ are simple, which is almost surely the case due to the hypothesis of continuous distribution.) One can expand out the right-hand side in terms of the other (unit-normalized) eigenvectors $u_{j}(A(z))$, $j\neq i$ as

By using Erdős-Schlein-Yau type estimates one expects $|u_{j}(A(z))^{*}A^{\prime}(z)u_{i}(A(z))|$ to be of size about $O(n^{-1+o(1)})$, while from Theorem 19 we expect $|\lambda_{j}(z)-\lambda_{i}(z)|$ to be bounded below by $n^{-c_{0}}$ with high probability, and so the claim (30) is plausible (one still needs to sum over $j$, of course, but one expects $\lambda_{j}(z)-\lambda_{i}(z)$ to grow roughly linearly in $j$ and so this should only contribute a logarithmic factor $O(\log n)=O(n^{o(1)})$ at worst). So we see for the first time how Theorem 19 is going to be an essential component in the proof of Theorem 15. Similar considerations also apply to the third, fourth, and fifth derivatives of $\lambda_{i}(A(z))$, though as one might imagine the formulae become more complicated.

There is however a technical difficulty that arises, namely that the lower bound

holds with high probability, but not with overwhelming probability (see Definition 3 for definitions). Indeed, given that eigenvalue collision is a codimension two event for real symmetric matrices and codimension three for Hermitian ones, one expects the failure probability to be about $n^{-2c_{0}}$ in the real case and $n^{-3c_{0}}$ in the complex case (this heuristic is also supported by the gap statistics for GOE and GUE). As one needs to take the union bound over many values of $z$ (about $n^{100}$ or so), this presents a significant problem. However, this difficulty can be avoided by going back to the start of the argument and replacing the quantity $G(\lambda_{i}(z))$ with a “regularized” variant which vanishes whenever $\lambda_{i}(z)$ gets too close to another eigenvalue. To do this, it is convenient to introduce the quantity

this quantity is normally of size $O(1)$, but becomes large precisely when the gap between $\lambda_{i}(A(z))$ and other eigenvalues becomes small. The strategy is then to replace $G(\lambda_{i}(A(z)))$ by a truncated variant $G(\lambda_{i}(A(z)),Q_{i}(A(z)))$ which is supported on the region where $Q_{i}$ is not too large (e.g. of size at most $n^{c_{0}}$), and apply the swapping strategy to the latter quantity instead. (For this, one needs control on derivatives of $Q_{i}(A(z))$ as well as on $\lambda_{i}(A(z))$, but it turns out that such bounds are available; this smoothness of $Q_{i}$ is one reason why we work with $Q_{i}$ in the first place, rather than more obvious alternatives such as $\inf_{j\neq i}|\lambda_{j}(A(z))-\lambda_{i}(A(z))|$.) Finally, to remove the truncation at the beginning and end of the iterated swapping process, one appeals to Theorem 19. Notice that this result is now only used twice, rather than $O(n^{2})$ or $O(n^{100})$ times, and so the total error probability remains acceptably bounded.

One way to interpret this truncation trick is that while the “bad event” that $Q_{i}$ is large has reasonably large probability (of order about $n^{-c_{0}}$), which makes the union bound ineffective, the $Q_{i}$ does not change too violently when swapping one or more of the entries of the random matrix, and so one is essentially faced with the same bad event throughout the $O(n^{2})$ different swaps (or throughout the $O(n^{100})$ or so different values of $z$). So the union bound is actually far from the truth in this case.

3. High-level proof of Theorem 15

We now begin the rigorous proof of Theorem 15, breaking it down into simpler propositions which will be proven in subsequent sections.

The heart of the argument consists of two key propositions. The first proposition asserts that one can swap a single coefficient (or more precisely, two coefficients) of a (deterministic) matrix $A$ as long as $A$ obeys a certain “good configuration condition”:

There exists a positive constant $C_{1}$ such that the following holds. Let $k\geq 1$ and ${\varepsilon}_{1}>0$, and assume $n$ sufficiently large depending on these parameters. Let $1\leq i_{1}<\ldots<i_{k}\leq n$. For a complex parameter $z$, let $A(z)$ be a (deterministic) family of $n\times n$ Hermitian matrices of the form

where $e_{p},e_{q}$ are unit vectors. We assume that for every $1\leq j\leq k$ and every $|z|\leq n^{1/2+{\varepsilon}_{1}}$ whose real and imaginary parts are multiples of $n^{-C_{1}}$, we have

(Eigenvalue separation) For any $1\leq i\leq n$ with $|i-i_{j}|\geq n^{{\varepsilon}_{1}}$, we have

(Delocalization at $i_{j}$) If $P_{i_{j}}(A(z))$ is the orthogonal projection to the eigenspace associated to $\lambda_{i_{j}}(A(z))$, then

whenever $P_{i_{j},\alpha}$ is the orthogonal projection to the eigenspaces corresponding to eigenvalues $\lambda_{i}(A(z))$ with $2^{\alpha}\leq|i-i_{j}|<2^{\alpha+1}$.

We say that $A(0),e_{p},e_{q}$ are a good configuration for $i_{1},\ldots,i_{k}$ if the above properties hold. Assuming this good configuration, then we have

for all $0\leq j\leq 5$, and $\zeta,\zeta^{\prime}$ are random variables with $|\zeta|,|\zeta^{\prime}|\leq n^{1/2+{\varepsilon}_{1}}$ almost surely, which match to order $r$ for some $r=2,3,4$.

If $G$ obeys the improved derivative bounds

for $0\leq j\leq 5$ and some sufficiently large absolute constant $C$, then we can strengthen $n^{-(r+1)/2+O({\varepsilon}_{1})}$ in (34) to $n^{-(r+1)/2-{\varepsilon}_{1}}$.

The need to restrict $z$ to multiples of $n^{-C_{1}}$, as opposed to all complex $z$ in the disk of radius $n^{1/2+\varepsilon_{1}}$, is so that we can verify the hypotheses in the next proposition using the union bound (so long as the events involved hold with overwhelming probability). For $C_{1}$ large enough, we will be able to use rounding methods to pass from the discrete setting of multiples of $n^{-C_{1}}$ to the continuous setting of arbitrary complex numbers in the disk without difficulty.

We prove this proposition in Section 4. To use this proposition, we of course need to have the good configuration property hold often. This leads to the second key proposition:

We will prove this proposition in Section 5.

Given these two propositions (and Theorem 19) we can now prove Theorem 15. As discussed at the beginning of the section, we may assume that the $\zeta_{ij}$ are continuously distributed in the complex plane and obey the bound (27).

Let $0<{\varepsilon}<1$ and $k\geq 1$, and assume $c_{0}$ is sufficiently small and $C_{1}$ sufficiently large. Let $M_{n},M^{\prime}_{n},\zeta_{ij},\zeta^{\prime}_{ij},A_{n},A^{\prime}_{n},G$, $i_{1},\ldots,i_{k}$ be as in Theorem 15.

For each $1\leq j\leq k$, one has $Q_{i_{j}}(A_{n})\leq n^{c_{0}}$ with high probability.

For brevity we omit the $A_{n}$ variable. Fix $j$. Suppose that $Q_{i_{j}}>n^{c_{0}}$, then

and so by the pigeonhole principle there exists an integer $0\leq m\ll\log n$ such that

uniformly in $m$ (and similarly for $\lambda_{i_{j}-2^{m}}$), since the $\log n$ loss caused by the number of $m$’s can easily be absorbed into the right-hand side.

Fix $m$. Suppose that $|\lambda_{i_{j}+2^{m}}-\lambda_{i_{j}}|\ll 2^{\frac{3}{4}m}n^{-c_{0}/2}$; then expressing the left-hand side as $\sum_{k=0}^{2^{m}-1}\lambda_{i_{j}+k+1}-\lambda_{i_{j}+k}$ and using Markov’s inequality we see that

The claim now follows from Theorem 19. (There is a slight issue when $2^{m}\sim n$, so that the index $i_{j}+k$ may leave the bulk; but then one works with, say, $\lambda_{i_{j}+2^{m-1}}-\lambda_{i_{j}}$ instead of $\lambda_{i_{j}+2^{m}}-\lambda_{i_{j}}$). ∎

One can also use Theorem 60 below to control all terms in the sum with $|i-i_{j}|\gg\log^{C^{\prime}}n$ for some $C^{\prime}$, leading to a simpler proof of Lemma 49.

Of course, Lemma 49 also applies with $A_{n}$ replaced by $A^{\prime}_{n}$.