Spectral Statistics of Erd{\H o}s-Rényi Graphs II: Eigenvalue Spacing and the Extreme Eigenvalues

Introduction

The Erdős-Rényi ensemble ER1 ; ER2 is a law of a random graph on $N$ vertices, in which each edge is chosen independently with probability $p\equiv p(N)$. The corresponding adjacency matrix is called the Erdős-Rényi matrix. Since each row and column has typically $pN$ nonzero entries, the matrix is sparse as long as $p\ll 1$. We shall refer to $pN$ as the sparseness parameter of the matrix. In the companion paper EKYY , we established the local semicircle law for the Erdős-Rényi matrix for $pN\geqslant(\log N)^{C}$, i.e. we showed that, assuming $pN\geqslant(\log N)^{C}$, the eigenvalue density is given by the Wigner semicircle law in any spectral window containing on average at least $(\log N)^{C^{\prime}}$ eigenvalues. In this paper, we use this result to prove both the bulk and edge universalities for the Erdős-Rényi matrix under the restriction that the sparseness parameter satisfies

More precisely, assuming that $p$ satisfies (1.1), we prove that the eigenvalue spacing of the Erdős-Rényi graph in the bulk of the spectrum has the same distribution as that of the Gaussian orthogonal ensemble (GOE). In order to outline the statement of the edge universality for the Erdős-Rényi graph, we observe that, since the matrix elements of the Erdős-Rényi ensemble are either or $1$, they do not satisfy the mean zero condition which typically appears in the random matrix literature. In particular, the largest eigenvalue of the Erdős-Rényi matrix is very large and lies far away from the rest of the spectrum. We normalize the Erdős-Rényi matrix so that the bulk of its spectrum lies in the interval $$. By the edge universality of the Erdős-Rényi ensemble, we therefore mean that its second largest eigenvalue has the same distribution as the largest eigenvalue of the GOE, which is the well-known Tracy-Widom distribution. We prove the edge universality under the assumption (1.1).

Neglecting the mean zero condition, the Erdős-Rényi matrix becomes a Wigner random matrix with a Bernoulli distribution when $0<p<1$ is a constant independent of $N$. Thus for $p\ll 1$ we can view the Erdős-Rényi matrix, up to a shift in the expectation of the matrix entries, as a singular Wigner matrix for which the probability distributions of the matrix elements are highly concentrated at zero. Indeed, the probability for a single entry to be zero is $1-p$. Alternatively, we can express the singular nature of the Erdős-Rényi ensemble by the fact that the $k$-th moment of a matrix entry is bounded by

For $p\ll 1$ this decay in $k$ is much slower than in the case of Wigner matrices.

There has been spectacular progress in the understanding of the universality of eigenvalue distributions for invariant random matrix ensembles BI ; DKMVZ1 ; DKMVZ2 ; PS2 ; PS . The Wigner and Erdős-Rényi matrices are not invariant ensembles, however. The moment method SS ; Sosh ; So2 is a powerful means for establishing edge universality. In the context of sparse matrices, it was applied in So2 to prove edge universality for the zero mean version of the $d$-regular graph, where the matrix entries take on the values $-1$ and $1$ instead of and $1$. The need for this restriction can be ascribed to the two following facts. First, the moment method is suitable for treating the largest and smallest eigenvalues. But in the case of the Erdős-Rényi matrix, it is the second largest eigenvalue, not the largest one, which behaves like the largest eigenvalue of the GOE. Second, the modification of the moment method to matrices with non-symmetric distributions poses a serious technical challenge.

A general approach to proving the universality of Wigner matrices was recently developed in the series of papers ESY1 ; ESY2 ; ESY3 ; ESY4 ; ESYY ; EYY ; EYY2 ; EYYrigidity . In this paper, we further extend this method to cover sparse matrices such as the Erdős-Rényi matrix in the range (1.1). Our approach is based on the following three ingredients. (1) A local semicircle law – a precise estimate of the local eigenvalue density down to energy scales containing around $(\log N)^{C}$ eigenvalues. (2) Establishing universality of the eigenvalue distribution of Gaussian divisible ensembles, via an estimate on the rate of decay to local equilibrium of the Dyson Brownian motion Dy . (3) A density argument which shows that for any probability distribution of the matrix entries there exists a Gaussian divisible distribution such that the two associated Wigner ensembles have identical local eigenvalue statistics down to the scale $1/N$. In the case of Wigner matrices, the edge universality can also be obtained by a modification of (1) and (3) EYYrigidity . The class of ensembles to which this method applies is extremely general. So far it includes all (generalized) Wigner matrices under the sole assumption that the distributions of the matrix elements have a uniform subexponential decay. In this paper we extend this method to the Erdős-Rényi matrix, which in fact represents a generalization in two unrelated directions: (a) the law of the matrix entries is much more singular, and (b) the matrix elements have nonzero mean.

As an application of the local semicircle law for sparse matrices proved in EKYY , we also prove the bulk universality for generalized Wigner matrices under the sole assumption that the matrix entries have $4+\varepsilon$ moments. This relaxes the subexponential decay condition on the tail of the distributions assumed in EYY ; EYY2 ; EYYrigidity . Moreover, we prove the edge universality of Wigner matrices under the assumption that the matrix entries have $12+\varepsilon$ moments. These results on Wigner matrices are stated and proved in Section 7 below. We note that in ABAP it was proved that the distributions of the largest eigenvalues are Poisson if the entries have at most $4-{\varepsilon}$ moments. Numerical results BBP predict that the existence of four moments corresponds to a sharp transition point, where the transition is from the Poisson process to the determinantal point process with Airy kernel.

We remark that the bulk universality for Hermitian Wigner matrices was also obtained in TV , partly by using the result of J and the local semicircle law from Step (1). For real symmetric Wigner matrices, the bulk universality in TV requires that the first four moments of every matrix element coincide with those of the standard Gaussian random variable. In particular, this restriction rules out the real Bernoulli Wigner matrices, which may be regarded as the simplest kind of an Erdős-Rényi matrix (again neglecting additional difficulties arising from the nonzero mean of the entries).

As a first step in our general strategy to prove universality, we proved, in the companion paper EKYY , a local semicircle law stating that the eigenvalue distribution of the Erdős-Rényi ensemble in any spectral window which on average contains at least $(\log N)^{C}$ eigenvalues is given by the Wigner semicircle law. As a corollary, we proved that the eigenvalue locations are equal to those predicted by the semicircle law, up to an error of order $(pN)^{-1}$. The second step of the strategy outlined above for Wigner matrices is to estimate the local relaxation time of the Dyson Brownian motion ESY4 ; ESYY . This is achieved by constructing a pseudo-equilibrium measure and estimating the global relaxation time to this measure. For models with nonzero mean, such as the Erdős-Rényi matrix, the largest eigenvalue is located very far from its equilibrium position, and moves rapidly under the Dyson Brownian motion. Hence a uniform approach to equilibrium is impossible. We overcome this problem by integrating out the largest eigenvalue from the joint probability distribution of the eigenvalues, and consider the flow of the marginal distribution of the remaining $N-1$ eigenvalues. This enables us to establish bulk universality for sparse matrices with nonzero mean under the restriction (1.1). This approach trivially also applies to Wigner matrices whose entries have nonzero mean.

Since the eigenvalue locations are only established with accuracy $(pN)^{-1}$, the local relaxation time for the Dyson Brownian motion with the initial data given by the Erdős-Rényi ensemble is only shown to be less than $1/(p^{2}N)\gg 1/N$. For Wigner ensembles, it was proved in EYYrigidity that the local relaxation time is of order $1/N$. Moreover, the slow decay of the third moment of the Erdős-Rényi matrix entries, as given in (1.2), makes the approximation in Step (3) above less effective. These two effects impose the restriction (1.1) in our proof of bulk universality. At the end of Section 2 we give a more detailed account of how this restriction arises. The reason for the same restriction’s being needed for the edge universality is different; see Section 6.3. We note, however, that both the bulk and edge universalities are expected to hold without this restriction, as long as the graphs are not too sparse in the sense that $pN\gg\log N$; for $d$-regular graphs this condition is conjectured to be the weaker $pN\gg 1$ Sa . A discussion of related problems on $d$-regular graphs can be found in MNS .

Acknowledgement. We thank P. Sarnak for bringing the problem of universality of sparse matrices to our attention.

Definitions and results

We begin this section by introducing a class of $N\times N$ sparse random matrices $A\equiv A_{N}$. Here $N$ is a large parameter. (Throughout the following we shall often refrain from explicitly indicating $N$-dependence.)

The motivating example is the Erdős-Rényi matrix, or the adjacency matrix of the Erdős-Rényi random graph. Its entries are independent (up to the constraint that the matrix be symmetric), and equal to $1$ with probability $p$ and with probability $1-p$. For our purposes it is convenient to replace $p$ with the new parameter $q\equiv q(N)$, defined through $p=q^{2}/N$. Moreover, we rescale the matrix in such a way that its bulk eigenvalues typically lie in an interval of size of order one.

Thus we are led to the following definition. Let $A=(a_{ij})$ be the symmetric $N\times N$ matrix whose entries $a_{ij}$ are independent (up to the symmetry constraint $a_{ij}=a_{ji}$) and each element is distributed according to

Here $\gamma\mathrel{\vbox{\hbox{.}\hbox{.}}}=(1-q^{2}/N)^{-1/2}$ is a scaling introduced for convenience. The parameter $q\leqslant N^{1/2}$ expresses the sparseness of the matrix; it may depend on $N$. Since $A$ typically has $q^{2}N$ nonvanishing entries, we find that if $q\ll N^{1/2}$ then the matrix is sparse.

We extract the mean of each matrix entry and write

where the entries of $H$ (given by $h_{ij}=a_{ij}-\gamma q/N$) have mean zero, and we defined the vector

One readily finds that the matrix elements of $H$ satisfy the moment bounds

More generally, we consider the following class of random matrices with non-centred entries characterized by two parameters $q$ and $f$, which may be $N$-dependent. The parameter $q$ expresses how singular the distribution of $h_{ij}$ is; in particular, it expresses the sparseness of $A$ for the special case (2.1). The parameter $f$ determines the nonzero expectation value of the matrix elements.

We consider $N\times N$ random matrices $H=(h_{ij})$ whose entries are real and independent up to the symmetry constraint $h_{ij}=h_{ji}$. We assume that the elements of $H$ satisfy the moment conditions

for $1\leqslant i,j\leqslant N$ and $2\leqslant p\leqslant(\log N)^{10\log\log N}$, where $C$ is a positive constant. Here $q\equiv q(N)$ satisfies

Let $H$ satisfy Definition 2.1. Define the matrix $A=(a_{ij})$ through

where $f\equiv f(N)$ is a deterministic number that satisfies

for some constants $\varepsilon_{0}>0$ and $C$.

For definiteness, and bearing the Erdős-Rényi matrix in mind, we restrict ourselves to real symmetric matrices satisfying Definition 2.2. However, our proof applies equally to complex Hermitian sparse matrices.

We shall use $C$ and $c$ to denote generic positive constants which may only depend on the constants in assumptions such as (2.4). Typically, $C$ denotes a large constant and $c$ a small constant. Note that the fundamental large parameter of our model is $N$, and the notations $\gg,\ll,O(\cdot),o(\cdot)$ always refer to the limit $N\to\infty$. Here $a\ll b$ means $a=o(b)$. We write $a\sim b$ for $C^{-1}a\leqslant b\leqslant Ca$.

After these preparations, we may now state our results. They concern the distribution of the eigenvalues of $A$, which we order in a nondecreasing fashion and denote by $\mu_{1}\leqslant\cdots\leqslant\mu_{N}$. We shall only consider the distribution of the $N-1$ first eigenvalues $\mu_{1},\dots,\mu_{N-1}$. The largest eigenvalue $\mu_{N}$ lies far removed from the others, and its distribution is known to be normal with mean $f+f^{-1}$ and variance $N^{-1/2}$; see EKYY , Theorem 6.2, for more details.

First, we establish the bulk universality of eigenvalue correlations. Let $p(\mu_{1},\dots,\mu_{N})$ be the probability densityNote that we use the density of the law of the eigenvalue density for simplicity of notation, but our results remain valid when no such density exists. of the ordered eigenvalues $\mu_{1}\leqslant\cdots\leqslant\mu_{N}$ of $A$. Introduce the marginal density

In other words, $p_{N}^{(N-1)}$ is the symmetrized probability density of the first $N-1$ eigenvalues of $H$. For $n\leqslant N-1$ we define the $n$-point correlation function (marginal) through

Similarly, we denote by $p_{{\rm GOE},N}^{(n)}$ the $n$-point correlation function of the symmetrized eigenvalue density of an $N\times N$ GOE matrix.

Suppose that $A$ satisfies Definition 2.2 with $q\geqslant N^{\phi}$ for some $\phi$ satisfying $0<\phi\leqslant 1/2$, and that $f$ additionally satisfies $f\leqslant CN^{1/2}$ for some $C>0$. Let $\beta>0$ and assume that

Theorem 2.5 implies bulk universality for sparse matrices provided that $1/3<\phi\leqslant 1/2$. See the end of this section for an account on the origin of the condition (2.9).

We also prove the universality of the extreme eigenvalues.

Suppose that $A$ satisfies Definition 2.2 with $q\geqslant N^{\phi}$ for some $\phi$ satisfying $1/3<\phi\leqslant 1/2$. Let $V$ be an $N\times N$ GOE matrix whose eigenvalues we denote by $\lambda_{1}^{V}\leqslant\cdots\leqslant\lambda_{N}^{V}$. Then there is a $\delta>0$ such that for any $s$ we have

Theorem 6.4 can be easily extended to correlation functions of a finite collection of extreme eigenvalues.

A result analogous to Theorem 2.7 holds for the extreme eigenvalues of the centred sparse matrix $H$; see (6.15) below.

We conclude this section by giving a sketch of the origin of the restriction $\phi>1/3$ in Theorem 2.5. To simplify the outline of the argument, we set $\beta=0$ in Theorem 2.5 and ignore any powers of $N^{\varepsilon}$. The proof of Theorem 2.5 is based on an analysis of the local relaxation properties of the marginal Dyson Brownian motion, obtained from the usual Dyson Brownian motion by integrating out the largest eigenvalue $\mu_{N}$. As an input, we need the bound

where $\gamma_{\alpha}$ denotes the classical location of the $\alpha$-th eigenvalue (see (3.15) below). The bound (2.13) was proved in EKYY . In that paper we prove, roughly, that $\lvert\mu_{\alpha}-\gamma_{\alpha}\rvert\leqslant q^{-2}\leqslant N^{-2\phi}$, from which (2.13) follows. The precise form is given in (3.16). We then take an arbitrary initial sparse matrix ensemble $A_{0}$ and evolve it according to the Dyson Brownian motion up to a time $\tau=N^{-\rho}$, for some $\rho>0$. We prove that the local spectral statistics, in the first $N-1$ eigenvalues, of the evolved ensemble $A_{\tau}$ at time $\tau$ coincide with those of a GOE matrix $V$, provided that

The precise statement is given in (4.9). This gives us the condition

Next, we compare the local spectral statistics of a given Erdős-Rényi matrix $A$ with those of the time-evolved ensemble $A_{\tau}$ by constructing an appropriate initial $A_{0}$, chosen so that the first four moments of $A$ and $A_{\tau}$ are close. More precisely, by comparing Green functions, we prove that the local spectral statistics of $A$ and $A_{\tau}$ coincide if the first three moments of the entries of $A$ and $A_{\tau}$ coincide and their fourth moments differ by at most $N^{-2-\delta}$ for some $\delta>0$. (See Proposition 5.2.) Given $A$ we find, by explicit construction, a sparse matrix $A_{0}$ such that the first three moments of the entries of $A_{\tau}$ are equal to those of $A$, and their fourth moments differ by at most $N^{-1-2\phi}\tau=N^{-1-2\phi-\rho}$; see (5.6). Thus the local spectral statistics of $A$ and $A_{\tau}$ coincide provided that

From the two conditions (2.15) and (2.16) we find that the local spectral statistics of $A$ and $V$ coincide provided that $\phi>1/3$.

The strong local semicircle law and eigenvalue locations

In this preliminary section we collect the main notations and tools from the companion paper EKYY that we shall need for the proofs. Throughout this paper we shall make use of the parameter

which will keep track of powers of $\log N$ and probabilities of high-probability events. Note that in EKYY , $\xi$ was a free parameter. In this paper we choose the special form (3.1) for simplicity.

with a parameter $L\equiv L(N)$ that always satisfies

For $\operatorname{Im}z>0$ we define the Stieltjes transform of the local semicircle law

where the density $\varrho_{sc}$ was defined in (2.10). The Stieltjes transform $m_{sc}(z)\equiv m_{sc}$ may also be characterized as the unique solution of

satisfying $\operatorname{Im}m_{sc}(z)>0$ for $\operatorname{Im}z>0$. This implies that

where the square root is chosen so that $m_{sc}(z)\sim-z^{-1}$ as $z\to\infty$. We define the resolvent of $A$ through

as well as the Stieltjes transform of the empirical eigenvalue density

At this point we warn the reader that we depart from our conventions in EKYY . In that paper, the quantities $G(z)$ and $m(z)$ defined above in terms of $A$ bore a tilde to distinguish them from the same quantities defined in terms of $H$. In this paper we drop the tilde, as we shall not need resolvents defined in terms of $H$.

We shall frequently have to deal with events of very high probability, for which the following definition is useful. It is characterized by two positive parameters, $\xi$ and $\nu$, where $\xi$ is given by (3.1).

We say that an $N$-dependent event $\Omega$ holds with $(\xi,\nu)$-high probability if

Similarly, for a given event $\Omega_{0}$, we say that $\Omega$ holds with $(\xi,\nu)$-high probability on $\Omega_{0}$ if

In the following we shall not keep track of the explicit value of $\nu$; in fact we allow $\nu$ to decrease from one line to another without introducing a new notation. All of our results will hold for $\nu\leqslant\nu_{0}$, where $\nu_{0}$ depends only on the constants $C$ in Definition 2.1 and the parameter $\Sigma$ in (3.2).

Suppose that $A$ satisfies Definition 2.2 with the condition (2.7) replaced with

Then there is a constant $\nu>0$, depending on $\Sigma$ and the constants $C$ in (2.4) and (2.5), such that the following holds.

We have the local semicircle law: the event

holds with $(\xi,\nu)$-high probability. Moreover, we have the following estimate on the individual matrix elements of $G$. If instead of (3.9) $f$ satisfies

for some constant $C_{0}$, then the event

The following theorem compares the locations of the eigenvalues $\mu_{1},\dots,\mu_{N-1}$ to their classical locations $\gamma_{1},\dots,\gamma_{N-1}$.

Suppose that $A$ satisfies Definition 2.2, and let $\phi$ be an exponent satisfying $0<\phi\leqslant 1/2$, and set $q=N^{\phi}$. Then there is a constant $\nu>0$ – depending on $\Sigma$ and the constants $C$ in (2.4), (2.5), and (2.7) – as well as a constant $C>0$ such that the following holds.

We have with $(\xi,\nu)$-high probability that

Moreover, for all $\alpha=1,\dots,N-1$ we have with $(\xi,\nu)$-high probability that

where we abbreviated $\widehat{\alpha}\mathrel{\vbox{\hbox{.}\hbox{.}}}=\min\{{\alpha,N-\alpha}\}$.

Under the assumption $\phi\geqslant 1/3$ the estimate (3.17) simplifies to

which holds with $(\xi,\nu)$-high probability.

Finally, we record two basic results from EKYY for later reference. From EKYY , Lemmas 4.4 and 6.1, we get, with $(\xi,\nu)$-high probability,

Moreover, from EKYY , Theorem 6.2, we get, with $(\xi,\nu)$-high probability,

In particular, using (2.7) we get, with $(\xi,\nu)$-high probability,

where $\sigma>0$ is a constant spectral gap depending only on the constant $\varepsilon_{0}$ from (2.7).

Local ergodicity of the marginal Dyson Brownian motion

Let $A_{0}=(a_{ij,0})_{ij}$ be a matrix satisfying Definition 2.2 with constants $q_{0}\geqslant N^{\phi}$ and $f_{0}\geqslant 1+\varepsilon_{0}$. Let $(B_{ij,t})_{ij}$ be a symmetric matrix of independent Brownian motions, whose off-diagonal entries have variance $t$ and diagonal entries variance $2t$. Let the matrix $A_{t}=(a_{ij,t})_{ij}$ satisfy the stochastic differential equation

It is easy to check that the distribution of $A_{t}$ is equal to the distribution of

where $V$ is a GOE matrix independent of $A_{0}$.

Let $\rho$ be a constant satisfying $0<\rho<1$ to be chosen later. In the following we shall consider times $t$ in the interval $[t_{0},\tau]$, where

One readily checks that, for any fixed $\rho$ as above, the matrix $A_{t}$ satisfies Definition 2.2, with constants

where all estimates are uniform for $t\in[t_{0},\tau]$. Denoting by $x_{N,t}$ the largest eigenvalue of $A_{t}$, we get in particular from (3.21) that

From now on we shall never use the symbols $f_{t}$ and $q_{t}$ in their above sense. The only information we shall need about $x_{N}$ is (4.3). In this section we shall not use any information about $q_{t}$, and in Section 5 we shall only need that $q_{t}\geqslant cN^{\phi}$ uniformly in $t$. Throughout this section $f_{t}$ will denote the joint eigenvalue density evolved under the Dyson Brownian motion. (See Definition 4.1 below.)

where $B_{1},\dots,B_{N}$ is a family of independent standard Brownian motions.

In order to describe the law of $V$, we define the equilibrium Hamiltonian

and denote the associated probability measure by

where $Z$ is a normalization. We shall always consider the restriction of $\mu$ to the domain

Define the Dirichlet form $D_{\mu}$ and the associated generator $L$ through

where $f$ is a smooth function of compact support on $\Sigma_{N}$. One may easily check that

Let $f_{t}$ to denote the solution of $\partial_{t}f_{t}=Lf_{t}$ satisfying $f_{t}|_{t=0}=f_{0}$. It is well known that this solution exists and is unique, and that $\Sigma_{N}$ is invariant under the Dyson Brownian motion, i.e. if $f_{0}$ is supported in $\Sigma_{N}$, so is $f_{t}$ for all $t\geqslant 0$. For a precise formulation of these statements and their proofs, see e.g. Appendices A and B in ESYY . In Appendix A, we present a new, simpler and more general, proof.

Let $\gamma_{1},\dots,\gamma_{N-1}$ denote the classical locations of the first $N-1$ eigenvalues, as defined in (3.15), and set

Choose an $\varepsilon>0$. Then for any $\rho$ satisfying $0<\rho<1$ there exists a $\bar{\tau}\in[\tau/2,\tau]$ such that, for any $J\subset\{1,2,\dots,N-m_{n}-1\}$, we have

for all $N\geqslant N_{0}(\rho)$. Here $\mu^{(N-1)}$ is the equilibrium measure of $(N-1)$ eigenvalues (GOE).

The rest of this section is devoted to the proof of Theorem 4.2. We begin by introducing a pseudo equilibrium measure. Abbreviate

Here we set $\gamma_{N}\mathrel{\vbox{\hbox{.}\hbox{.}}}=2+\sigma$ for convenience, but one may easily check that the proof remains valid for any larger choice of $\gamma_{N}$. Define the probability measure

Next, we consider marginal quantities obtained by integrating out the largest eigenvalue $x_{N}$. To that end we write

Throughout the following, we write $g_{t}\mathrel{\vbox{\hbox{.}\hbox{.}}}=f_{t}/\psi$. In order to avoid pathological behaviour of the extreme eigenvalues, we introduce cutoffs. Let $\sigma$ be the spectral gap from (4.3), and choose $\theta_{1},\theta_{2},\theta_{3}\in$ to be smooth functions that satisfy

Define $\theta\equiv\theta(x_{1},x_{N-1},x_{N})=\theta_{1}(x_{1})\,\theta_{2}(x_{N-1})\,\theta_{3}(x_{N})$. One easily finds that

where the left-hand side is understood to vanish outside the support of $\theta$.

If $\nu$ is a probability measure and $q$ a density such that $q\nu$ is also a probability measure, we define the entropy

The following result is our main tool for controlling the local ergodicity of the marginal Dyson Brownian motion.

uniformly for $t\in[t_{0},\tau]$, by (4.12). Dropping the time index to avoid cluttering the notation, we find

Bounding the Dirichlet form in terms of the entropy (see e.g. Enotes , Theorem 3.2), we find that

by (4.11). Using (4.10) we therefore find

Next, we estimate the error terms $\mathcal{E}_{1}$ and $\mathcal{E}_{2}$. Using (4.10) we get

Using (4.10), (4.13), and (4.16) we therefore get

Having dealt with the error terms $\mathcal{E}_{1}$ and $\mathcal{E}_{2}$, we compute the first term on the right-hand side of (4.21),

Using the Cauchy-Schwarz inequality $\langle ab\rangle^{2}\leqslant\langle a^{2}\rangle\,\langle b^{2}\rangle$ we find that the second term is bounded by

Since $x_{N}-x_{i}\geqslant\sigma/5$ on the support of $\theta f\mu$, one easily gets from (3.19) that

In order to estimate $\mathcal{E}_{4}$, we write

We now claim that on the support of $\theta$, in particular for $-4\leqslant x_{1}<x_{N-1}\leqslant 2+2\sigma/5$, we have

uniformly for $\widehat{x}\in\Sigma_{N-1}$. Indeed, writing $\widetilde{\gamma}_{N}\mathrel{\vbox{\hbox{.}\hbox{.}}}=\gamma_{N}(1+R^{-2})$, we have on the support of $\theta$

Moreover, the second term is nonnegative:

where $C_{N}(\widehat{x})$ is nonnegative. This proves (4.23). Using (4.23) we get

Choosing $\eta$ small enough completes the proof. ∎

Next, we derive a logarithmic convexity bound for the marginal measure $\widehat{\omega}$.

and $\nabla^{2}V(\widehat{x})\geqslant R^{-2}$.

Write $\mathcal{H}(\widehat{x},x_{N})=\mathcal{H}^{\prime}(\widehat{x})+\mathcal{H}^{\prime\prime}(\widehat{x},x_{N})$ where

Thus we find that $V_{\delta}\in C^{2}(\Sigma_{N-1})$ and that we have the pointwise convergence, for all $\widehat{x}\in\Sigma_{N-1}$,

where $V\in C^{2}(\Sigma_{N-1})$ satisfies (4.24).

Next, we claim that if $\varphi=\varphi(x,y)$ satisfies $\nabla^{2}\varphi(x,y)\geqslant K$ then $\psi(x)$, defined by

Using this claim, we find that $\nabla^{2}V_{\delta}(\widehat{x})\geqslant R^{-2}$ for all $\widehat{x}\in\Sigma_{N-1}$. In order to prove that $\nabla^{2}V(\widehat{x})\geqslant R^{-2}$ – and hence complete the proof – it suffices to consider directional derivatives and prove the following claim. If $(\zeta_{\delta})_{\delta>0}$ is a family of functions on a neighbourhood $U$ that converges pointwise to a $C^{2}$-function $\zeta$ as $\delta\to 0$, and if $\zeta_{\delta}^{\prime\prime}(x)\geqslant K$ for all $\delta>0$ and $x\in U$, then $\zeta^{\prime\prime}(x)\geqslant K$ for all $x\in U$. Indeed, taking $\delta\to 0$ in

yields \bigl{(}{\zeta(x+h)+\zeta(x-h)-2\zeta(x)}\bigr{)}h^{-2}\geqslant K, from which the claim follows by taking the limit $h\to 0$. ∎

As a first consequence of Lemma 4.4, we derive an estimate on the expectation of observables depending only on eigenvalue differences.

Using Lemma 4.4, the proof of Theorem 4.3 in ESYY applies with merely cosmetic changes. ∎

Another, standard, consequence of Lemma 4.4 is the logarithmic Sobolev inequality

Using (4.25) and Proposition 4.3, we get the following estimate on the Dirichlet form.

Under the assumptions of Proposition 4.3, there exists a $\bar{\tau}\in[\tau/2,\tau]$ such that

which we integrate from $t_{0}$ to $t$ to get

where the second inequality follows from the fact that taking marginals reduces the relative entropy; see the proof of Lemma 4.7 below for more details. Thus we get

for $t\in[t_{0},\tau]$. Integrating (4.14) from $\tau/2$ to $\tau$ therefore gives

We may finally complete the proof of Theorem 4.2.

The assumptions of Proposition 4.3 are verified in Subsection 4.1 below. Hence Propositions 4.5 and 4.6 yield

In order to compare the measures $\widehat{\omega}$ and $\mu^{(N-1)}$, we define the density

The estimate (4.11) is an immediate consequence of the following lemma.

Let the entries of $A_{0}$ have the distribution $\zeta_{0}$. Then for any $t>0$ we have

where $m_{2}(\zeta_{0})$ is the second moment of $\zeta_{0}$.

The estimate (4.12) follows from (4.3) and (3.19). It only remains to verify (4.13).

Let $\zeta_{t}$ be the law of an off-diagonal entry $a$ of $A_{t}$ (the diagonal entries are treated similarly). From (4.2) we find

Therefore, the density $F_{t}(A)$ of the law of $A$ with respect to the GOE measure satisfies

Using (4.32) we may now derive an upper bound on $\langle\theta_{3}g_{t}\rangle$:

We now derive a lower bound on $\langle\theta_{3}g_{t}\rangle$. Using (4.32) and (4.31) we find

by a calculation similar to (4.33). The claim follows from

Bulk universality: proof of Theorem 2.5

We begin with a universality result for sparse matrices with a small Gaussian convolution.

Let $E\in[-2+\kappa,2-\kappa]$ for some $\kappa>0$ and let $b\equiv b_{N}$ satisfy $\lvert b\rvert\leqslant\kappa/2$. Pick $\varepsilon,\beta>0$, and set $\tau\mathrel{\vbox{\hbox{.}\hbox{.}}}=N^{-2\alpha+\beta}$, where

Let $A^{(1)}=(a_{ij}^{(1)})$ and $A^{(2)}=(a_{ij}^{(2)})$ be sparse random matrices, both satisfying Definition 2.2 with

(in self-explanatory notation). Suppose that, for each $i,j$, the first three moments of $a_{ij}^{(1)}$ and $a_{ij}^{(2)}$ are the same, and that the fourth moments satisfy

Then, abbreviating $G^{(l)}(z)\mathrel{\vbox{\hbox{.}\hbox{.}}}=(A^{(l)}-z)^{-1}$, we have

As in EYY (Theorem 6.4), Proposition 5.2 readily implies the following correlation function comparison theorem.

We may now complete the proof of Theorem 2.5.

In order to invoke Theorems 5.1 and 5.3, we construct a sparse matrix $A_{0}$, satisfying Definition 2.2, such that its time evolution $A_{\bar{\tau}}$ is close to $A$ in the sense of the assumptions of Proposition 5.2. For definiteness, we concentrate on off-diagonal elements (the diagonal elements are dealt with similarly).

where $g$ is a centred Gaussian with variance $1/N$, independent of $\xi_{0}$. We shall construct a random variable $\xi_{0}$, supported on at most three points, such that $A_{0}$ satisfies Definition 2.2 and the first four moments of $\xi^{\prime}$ are sufficiently close to those of $\xi$. For $k=1,2,\dots$ we denote by $m_{k}(X)$ the $k$-th moment of a random variable $X$. We set

where $m_{1}(\widetilde{\xi}_{0})=0$ and $m_{2}(\widetilde{\xi}_{0})=N^{-1}$. It is easy to see that $m_{k}(\xi)=m_{k}(\xi^{\prime})$ for $k=1,2$.

We take the law of $\widetilde{\xi}_{0}$ to be of the form

where $a,b,p,q\geqslant 0$ are parameters satisfying $p+q\leqslant 1$. The conditions $m_{1}(\widetilde{\xi}_{0})=0$ and $m_{2}(\widetilde{\xi}_{0})=N^{-1}$ imply

Thus, we parametrize $\xi_{0}$ using $a$ and $b$; the condition $p+q\leqslant 1$ reads $ab\geqslant N^{-1}$. Our aim is to determine $a$ and $b$ so that $\xi_{0}$ satisfies (2.4), and so that the third and fourth moments of $\xi^{\prime}$ and $\xi$ are close. By explicit computation we find

Now we require that $a$ and $b$ be chosen so that $ab\geqslant N^{-1}$ and

Using (5.5), it is easy to see that such a pair $(a,b)$ exists provided that $m_{4}(\widetilde{\xi})-Nm_{3}(\widetilde{\xi})^{2}\geqslant N^{-2}$. This latter estimate is generally valid for any random variable with $m_{1}=0$; it follows from the elementary inequality $m_{4}m_{2}-m_{3}^{2}\geqslant m_{2}^{3}$ valid whenever $m_{1}=0$.

Next, using (5.5) and the estimates $m_{3}(\widetilde{\xi})=O(N^{-1-\phi})$, $m_{4}(\widetilde{\xi})=O(N^{-1-2\phi})$, we find

which implies $a,b=O(N^{-\phi})$. We have hence proved that $A_{0}$ satisfies Definition 2.2.

One readily finds that $m_{3}(\xi^{\prime})=m_{3}(\xi)$. Moreover, using

The claim follows now by setting $\delta=2\alpha(\phi)+2\phi-1-\beta$ in (5.3), and invoking Theorems 5.1 and 5.3. ∎

Edge universality: proof of Theorem 2.7

Let $H$ be a symmetric $N\times N$ matrix. For $f\geqslant 0$ we set

Denote by $\lambda_{1}\leqslant\cdots\leqslant\lambda_{N}$ the eigenvalues of $H$, and by $\mu_{1}(f)\leqslant\cdots\leqslant\mu_{N}(f)$ the eigenvalues of $A(f)$. Then for all $\alpha=1,\dots,N-1$ and $f\geqslant 0$ the function $\mu_{\alpha}(f)$ is nondecreasing, satisfies $\mu_{\alpha}(0)=\lambda_{\alpha}$, and has the interlacing property

Let $V$ be an $N\times N$ GOE matrix. Suppose moreover that $\xi$ satisfies (3.10) and that $f$ satisfies $f\geqslant 1+\varepsilon_{0}$. Then there is a $\delta\equiv\delta(\varepsilon_{0})>0$ such that for all $\alpha$ satisfying $N(1-\delta)\leqslant\alpha\leqslant N-1$ we have with $(\xi,\nu)$-high probability

Similarly, if $\alpha$ instead satisfies $\alpha\leqslant N\delta$ we have with $(\xi,\nu)$-high probability

For the proof of Lemma 6.2 we shall need the following result about Wigner matrices, proved in EYYrigidity .

Moreover, let $L$ satisfy (3.11) and write G^{H}_{ij}(z)\mathrel{\vbox{\hbox{.}\hbox{.}}}=\bigl{[}{(H-z)^{-1}}\bigr{]}_{ij}. Then we have, with $(\xi,\nu)$-high probability,

with $(\xi,\nu)$-high probability. Now from we (6.2) we get

We estimate from below, introducing an arbitrary $\eta>0$,

where in the third step we used that $\lambda_{\alpha+1}\geqslant\mu_{\alpha}$ by (6.1).

From (6.6) and (6.1) we get that $\lvert\mu_{\alpha}-\gamma_{\alpha}\rvert\leqslant(\log N)^{C\xi}N^{-2/3}$ with $(\xi,\nu)$-high probability. Moreover, the definition (3.15) and $\alpha\geqslant N(1-\delta)$ imply $\lvert\gamma_{\alpha}-2\rvert\leqslant C\delta^{2/3}$. Thus we get, with $(\xi,\nu)$-high probability, that $\lvert 2-\mu_{\alpha}\rvert=o(1)+C\delta^{2/3}$. Therefore (6.11) yields, with $(\xi,\nu)$-high probability,

Recalling (6.8), we therefore get from (6.10), with $(\xi,\nu)$-high probability,

Next, from (6.6) we find that, provided $C_{2}$ is large enough, $m\mathrel{\vbox{\hbox{.}\hbox{.}}}=(\log N)^{C_{2}\xi}$, and $\beta>\alpha+m$, then we have with $(\xi,\nu)$-high probability

Then for $C_{2}$ large enough we have, with $(\xi,\nu)$-high probability,

Thus we get from (6.12), with $(\xi,\nu)$-high probability,

Plugging this into (6.9) and recalling that $f\geqslant 1+\varepsilon_{0}>1$ yields, with $(\xi,\nu)$-high probability,

2. Proof of Theorem 2.7

In this section we prove Theorem 2.7 by establishing the following comparison result for sparse matrices. Throughout the following we shall abbreviate the lower bound in (2.7) by

for $N\geqslant N_{0}$ sufficiently large, where $N_{0}$ is independent of $s$.

Assuming Proposition 6.4 is proved, we may easily complete the proof of Theorem 2.7 using the results of Section 6.1.

For the following we write $\mu_{\alpha}(f)\equiv\mu_{\alpha}$ to emphasize the $f$-dependence of the eigenvalues of $A(f)$. Using first (6.1) and then (6.15) we get

for some $\delta>0$. Next, using first the monotonicity of $\mu_{\alpha}(f)$ from Lemma 6.1, then (6.16), and finally (6.3), we get

for some $\delta>0$. This concludes the proof of (2.11), after a renaming of $\delta$. ∎

The rest of this section is devoted to the proof of Proposition 6.4. We shall only prove (6.16). The proof of (6.15) is similar (in fact easier), and relies on the local semicircle law, Theorem 3.3, with $f=0$; if $f=0$ some of the following analysis simplifies (e.g. the proof of Lemma 6.8 below may be completed without the estimate from Lemma 6.9.)

From now on we always assume the setup of Proposition 6.4. In particular, $f$ will always be equal to $f_{*}$.

We begin by outlining the proof of Proposition 6.4. The basic strategy is similar to the one used for Wigner matrices in EYYrigidity and KY . For any $E_{1}\leqslant E_{2}$, let

denote the number of eigenvalues of $A$ in the interval $[E_{1},E_{2}]$. In the first step, we express the distribution function in terms of Green functions according to

for some $C_{0}$ large enough. The first approximate identity in (6.17) follows from Theorem 3.4 which guarantees that $\mu_{N-1}\leqslant E_{*}$ with $(\xi,\nu)$-high probability, and from (3.21) which guarantees that $\mu_{N}\geqslant 2+\sigma$ with $(\xi,\nu)$-high probability. The second approximate identity in (6.17) follows from the approximation

which is valid for $E_{1}$ and $E_{2}$ near the spectral edge, where the typical eigenvalue separation is $N^{-2/3}\gg\eta$.

Therefore in (6.16) we can assume that $s$ satisfies

Recall the definition (6.19) of $E_{*}$ and and introduce, for any $E\leqslant E_{*}$, the characteristic function on the interval $[E,E_{*}]$,

to be an approximate delta function on scale $\eta$.

The following result allows us to replace the sharp counting function ${\mathcal{N}}(E,E_{*})=\operatorname{Tr}\chi_{E}(H)$ with its approximation smoothed on scale $\eta$.

hold with $(\xi,\nu)$-high probability. Furthermore, we have

for sufficiently large $N$ independent of $E$, as long as (6.24) holds.

The proof of Corollary 6.2 in EYYrigidity can be reproduced almost verbatim. In the estimate (6.17) of EYYrigidity , we need the bound, with $(\xi,\nu)$-high probability,

Note that, when compared to Corollary 6.2 in EYYrigidity , the quantity $\mathcal{N}(E,\infty)$ has been incremented by one; the culprit is the single eigenvalue $\mu_{N}\geqslant 2+\sigma$. ∎

For the following it is convenient to introduce the shorthand

with some constant $C_{1}>0$. Then there exists a constant $\widetilde{\varepsilon}>0$, depending only on $C_{1}$, such that for any ${\varepsilon}<\widetilde{\varepsilon}$ and for any real numbers $E,E_{1},E_{2}\in I_{\varepsilon}$, and setting $\eta\mathrel{\vbox{\hbox{.}\hbox{.}}}=N^{-2/3-{\varepsilon}}$, we have

for some constant $C$ and large enough $N$.

We postpone the proof of Proposition 6.6 to the next section. Assuming it proved, we now have all the ingredients needed to complete the proof of Proposition 6.4.

As observed after (6.20) and (6.21), we may assume that (6.22) holds. We define $E:=2+sN^{-2/3}$ that satisfies (6.24). We define $E_{*}$ as in (6.19) with the $C_{0}$ such that (6.20) and (6.21) hold. From (6.26) we get, for any sufficiently small ${\varepsilon}>0$,

(note that here $9{\varepsilon}$ plays the role of ${\varepsilon}$ in the Proposition 6.6). Next, the second bound of (6.26) yields

for sufficiently small ${\varepsilon}>0$ and sufficiently large $N$. Setting $E=2+sN^{-2/3}$ proves the first inequality of (6.16). Switching the roles of ${\bf{v}}$ and ${\bf{w}}$ in (6.34) yields the second inequality of (6.16). ∎

3. Proof of Proposition 6.6

All that remains is the proof of Proposition 6.6, to which this section is devoted. Throughout this section we suppose that the assumptions of Proposition 6.4 hold, and in particular that $f=1+\varepsilon_{0}$.

We now set up notations to replace the matrix elements one by one. This step is identical for the proof of both (6.29) and (6.30); we use the notations of the case (6.29), for which they are less involved.

Fix a bijective ordering map on the index set of the independent matrix elements,

and denote by $A_{\gamma}$ the generalized Wigner matrix whose matrix elements $a_{ij}$ follow the $v$-distribution if $\phi(i,j)\leqslant\gamma$ and they follow the $w$-distribution otherwise; in particular $A_{0}=A^{\bf{v}}$ and $A_{\gamma_{\rm max}}=A^{\bf{w}}$.

Next, set $\eta\mathrel{\vbox{\hbox{.}\hbox{.}}}=N^{-2/3-\varepsilon}$. We use the identity

Therefore Theorem 2.9 of EKYY yields, with $(\xi,\nu)$-high probability,

we find, as in (6.36) of EYYrigidity , that in order to prove (6.29) it is enough to prove

Let $E^{(ij)}$ denote the matrix whose matrix elements are zero everywhere except at the $(i,j)$ position, where it is 1, i.e. $E^{(ij)}_{kl}\mathrel{\vbox{\hbox{.}\hbox{.}}}=\delta_{ik}\delta_{jl}$. Fix $\gamma\geqslant 1$ and let $(b,d)$ be determined by $\phi(b,d)=\gamma$. For definiteness, we assume the off-diagonal case $b\neq d$; the case $b=d$ can be treated similarly. Note that the number of diagonal terms is $N$ and the number of off-diagonal terms is $O(N^{2})$. We shall compare $A_{\gamma-1}$ with $A_{\gamma}$ for each $\gamma$ and then sum up the differences in (6.39).

Note that these two matrices differ only in the entries $(b,d)$ and $(b,d)$, and they can be written as

where, we recall $f=1+\varepsilon_{0}$. It is easy to see that

with $(\xi,\nu)$-high probability, and that

We now claim that the estimate (6.36) holds for the Green function $R$ as well, i.e.

holds with $(\xi,\nu)$-high probability. To see this, we use the resolvent expansion

Since $V$ has only at most two nonzero elements, when computing the entry $(k,l)$ of this matrix identity, each term is a sum of finitely many terms (i.e. the number of summands is independent of $N$) that involve matrix elements of $S$ or $R$ and $v_{ij}$, e.g. of the form $(SVS)_{kl}=S_{ki}v_{ij}S_{jl}+S_{kj}v_{ji}S_{il}$. Using the bound (6.36) for the $S$ matrix elements, the bound (6.41) for $v_{ij}$ and the trivial bound $|R_{ij}|\leqslant\eta^{-1}\leqslant N$, we get (6.44).

the random variable $y^{R}$ is defined similarly. We shall show that

for some deterministic $B$ which depends only on the law of $Q$ and the first two moments of $v_{bd}$. From (6.47) we immediately conclude that (6.29) holds. In order to prove (6.47), we expand

where $\zeta$ lies between $y^{S}$ and $y^{R}$. Next, we apply the resolvent expansion

which is much smaller than $N^{-2}$ provided that $q\geqslant N^{\phi}$ for $\phi>1/3$ and $\varepsilon$ is small enough.

The key step to the proof of Proposition 6.6 is the following lemma.

Fix an index $\gamma=\phi(b,d)$ and recall the definitions of $Q$, $R$ and $S$ from (6.43). For any small enough ${\varepsilon}>0$ and under the assumptions in Proposition 6.6, there exists a constant $C$ depending on $F$ (but independent of $\gamma$) and constants $B_{N}$ and $D_{N}$, depending on the law $\operatorname{law}(Q)$ of the Green function $Q$ and on the second moments $m_{2}(v_{bd})$ of $v_{bd}$, such that, for large enough $N$ (independent of $\gamma$) we have

where, we recall, $\eta=N^{-2/3-{\varepsilon}}$, as well as

Assuming Lemma 6.7, we now complete the proof of Proposition 6.6.

Clearly, Lemma 6.7 also holds if $S$ is replaced by $T$. Since $Q$ is independent of $v_{bd}$ and $w_{bd}$, and $m_{2}(v_{bd})=m_{2}(w_{bd})=1/N$, we have D_{N}\big{(}m_{2}(v_{bd}),\operatorname{law}(Q)\big{)}=D_{N}\big{(}m_{2}(w_{bd}),\operatorname{law}(Q)\big{)}. Thus we get from Lemma 6.7 that

Recalling the definitions of $S$ and $T$ from (6.43), the bound (6.53) compares the expectation of a function of the resolvent of $A_{\gamma}$ and that of $A_{\gamma-1}$. The telescopic summation in (6.39) then implies (6.38), since the number of summands with $b\neq d$ is of order $N^{2}$ but the number of summands with $b=d$ is only $N$. Similarly, (6.51) implies (6.30). This completes the proof. ∎

Throughout the proof we abbreviate $A_{\gamma-1}=A=(a_{ij})$ where $a_{ij}=h_{ij}+f/N$. We shall only prove the more complicated case (6.51); the proof of (6.52) is similar. In fact, we shall prove the bound

with $(\xi,\nu)$-high probability. Define $\Omega$ as the event on which (6.55), (6.44), and (6.41) hold. We have proved that $\Omega$ holds with $(\xi,\nu)$-high probability. Since the arguments of $F$ in (6.54) are bounded by $CN^{2+2{\varepsilon}}$ and $F(x)$ increases at most polynomially, it is easy to see that the contribution of the event $\Omega^{c}$ to the expectations in (6.54) is negligible.

$x^{R}_{k}$ is defined similarly. Here $k=|\{i,j\}\cap\{b,d\}|$ is the number of times the indices $b$ and $d$ appear among the summation indices $i,j$. Clearly $k=0$, $1$ or $2$. The number of the terms in the sum of the definition of $x^{S}_{k}$ is $O(N^{2-k})$. A resolvent expansion yields

If $|\{i,j\}\cap\{b,d\}|=k$, recalling that $i\neq j$ we find that there are at least $2-k$ off-diagonal resolvent elements in \big{[}(RV)^{m}R\big{]}_{ij}, so that (6.36) yields in $\Omega$

and keeping only the terms larger than $O(N^{-1/3+C{\varepsilon}}p^{-4}q^{-1})$, we obtain

where we used the remark after (6.55) to treat the contribution on the event $\Omega$. Since there is no $x_{2}$ appearing in (6.63), we can focus on the cases $k=0$ and $k=1$.

Then using (6.59) and the estimate $\max_{i\neq j}|R_{ij}|\leqslant p^{-1}$ we get

Now we decompose the sum $x^{S}_{k}-x^{R}_{k}$ according to the number of matrix elements $h_{bd}$ and $h_{db}$. To that end, for $k\in\{0,1\}$ and $s,t\in\{0,1,2,3,4\}$ and $s+t\geqslant 1$, we define

Using (6.65) we get the estimates, valid on $\Omega$,

where $s$ and $t$ are non-negative. By (6.68) and (6.44) we have for $s+t\geqslant 1$

Similarly, for $s+t\geqslant 1$ and $u+v\geqslant 1$ we have

Inserting (6.71) and (6.73) into the second term of the left-hand side of (6.63), and using the assumption $F$ as well as (6.62), we find

Note that $B$ depends on $h_{bd}$ only through its expectation (which is zero) and on its second moment. Thus, $B$ will be $B_{N}(m_{2}(v_{bd}),\operatorname{law}(Q))$ from (6.51).

Recalling (6.64), we introduce the notation $R_{ij}^{(m,s)}$ to denote the sum of the terms in the definition (6.64) of $R_{ij}^{(m)}$ in which the number of the off-diagonal elements of $R$ is $s$. For example,

As above, it is easy to see that for $s\geqslant 3$ we have

By symmetry, it only remains to prove that

Using the definition (6.79) and the estimate (6.44) to replace some diagonal resolvent matrix elements with $m_{sc}$, we find

where we used the trivial bounds on $F^{\prime}$ and $\lvert m_{sc}\rvert$, and that every estimate is uniform in $y$.

where $B$ was defined in (6.75). This completes the proof of Lemma 6.7. ∎

Under the assumptions of Lemma 6.7, in particular fixing $f=f_{*}$, and assuming that $a,b,i,j$ are all distinct, we have

The same estimate holds for the other three terms on the right-hand side of (6.85).

For any fixed $i$ we have, with $(\xi,\nu)$-high probability,

The claim is an immediate consequence of Proposition 7.11 in EKYY and the observation that, for $E\in I_{\varepsilon}$, $\eta=N^{-2/3-\varepsilon}$, and $q\geqslant N^{\phi}$ we have

Another ingredient necessary for the proof of Lemma 6.8 is the following resolvent identity.

Let $A=(a_{ij})$ be a square matrix and set $S=(S_{ij})=(A-z)^{-1}$. Then for $i\neq j$ we have

We prove the first identity in (6.88); the second one is proved analogously. We use the resolvent identity

Armed with Lemmas 6.9 and 6.10, we may now prove Lemma 6.8.

With the relation between $R$ and $S$ in (6.45) and (6.59), we find that (6.87) is implied by

under the assumption that $b,d,i,j$ are all distinct. This replacement is only a technical convenience when we apply a large deviation estimate below.

Recalling the definition of $\Omega$ after (6.55), we get using (6.89)

Since $(x^{S})^{(b)}$ and $S_{dj}^{(b)}\overline{S_{ji}^{(b)}}\!\,$ are independent of the $b$-th row of $A$, we find from (6.94) that (6.90), and hence (6.87), is proved if we can show that

What remains therefore is to prove (6.95). Using (6.55) and (6.91) we find in $\Omega$ that

In order to estimate the right-hand side of (6.98), we introduce the quantity

Note that $X$ depends on the index $i$, which is omitted from the notation as it is fixed. Using (6.88), (6.96), and (6.89) as above, we find with $(\xi,\nu)$-high probability

We now return to (6.98), and estimate, with $(\xi,\nu)$-high probability

Together with (6.99) this yields, with $(\xi,\nu)$-high probability,

Using the large deviation estimate (3.15) in EKYY , (6.96), and the bound $\lvert h_{lk}\rvert\leqslant p^{-1}$ which holds with $(\xi,\nu)$-high probability (see Lemma 3.7 in EKYY ), we find that the second term is bounded by $O(p^{-2})$ with $(\xi,\nu)$-high probability. Thus we get

with $(\xi,\nu)$-high probability. Therefore (6.100) and Lemma 6.9 imply (6.95), and the proof is complete. ∎

Universality of generalized Wigner matrices with finite moments

This section is an application of our results to the problem of universality of generalized Wigner matrices (see Definition 7.1 below) whose entries have heavy tails. We prove the bulk universality of generalized Wigner matrices under the assumption that the matrix entries have a finite $m$-th moment for some $m>4$. We also prove the edge universality of Wigner matrices under the assumption that $m>12$. (This lower bound can in fact be improved to $m\geqslant 7$; see Remark 7.5 below.) The Tracy-Widom law for the largest eigenvalue of Wigner matrices was first proved in Sosh under a Gaussian decay assumption, and was proved later in Ruz ; TV2 ; EYYrigidity ; Kho under various weaker restrictions on the distributions of the matrix elements. In particular, in Kho the Tracy-Widom law was proved for entries with symmetric distribution and $m>12$. In J2 similar results were derived for complex Hermitian Gaussian divisible matrices, where the GUE component is of order one. For this case it is proved in J2 that bulk universality holds provided the entries of the Wigner component have finite second moments, and edge universality holds provided they have finite fourth moments.

We call a Hermitian or real symmetric random matrix $H=(h_{ij})$ a generalized Wigner matrix if the two following conditions hold. First, the family of upper-triangluar entries $(h_{ij}:i\leqslant j)$ is independent. Second, we have