Bulk universality of sparse random matrices

Introduction

The universality of the spectral statistics of random matrices has been a central subject since the pioneering works of Wigner , Gaudin , Mehta and Dyson . The first such universality result is the global semicircle law of Wigner which states that under some weak moment conditions, the empirical eigenvalue distribution of a matrix with i.i.d. entries converges weakly to the deterministic semicircle law

The Wigner-Dyson-Gaudin-Mehta conjecture, or ‘bulk universality’ conjecture, states that the local statistics of the eigenvalues of random matrix ensembles should be universal in the sense that they depend only on the symmetry class of the random matrix ensemble but are otherwise independent of the law of the matrix entries. Here, local statistics refers to the behaviour of the eigenvalues in the scaling in which their typical distance is order $1$.

A prominent class of random matrices are Wigner matrices. These matrices have independent centered entries with a uniform subexponential decay condition and identical variances. The Wigner-Dyson-Gaudin-Mehta conjecture for Wigner matrices was recently established in a series of papers for all symmetry classes. Parallel results in various cases were obtained in .

The conclusion of the papers was that Wigner matrices, and even the wider class of generalized Wigner matrices in which the variances of the entries may differ, exhibit bulk universality in the following two forms. The first is that the $n$-point correlation functions are universal after averaging over a small energy window. The second is that the distribution of the eigenvalue gaps with a fixed label are universal. For Wigner matrices, the universality of the averaged $n$-point correlaton functions is equivalent to the universality of a local average of eigenvalue gaps. However, there is no rigorous mathematical relation between the universality of the eigenvalue gaps with a fixed label and the universality of the $n$-point correlation functions at a fixed energy. Universality at a fixed energy has recently been established for all symmetry classes in , but we will not be concerned with this type of convergence in this work.

Wigner matrices were orginally introduced in by Wigner to model the spectra of heavy atoms, and are widely used to model systems in which all elements strongly interact with one another. However, for systems in which the links between different elements are broken, a better description is offered by the so-called sparse (or dilute) random matrices which have an average of $pN$ nonzero elements per row, for $p\ll 1$.

Aside from theoretical physics models, sparse random matrices also arise in graph theory in the study of sparse random graphs. Perhaps the simplest example is the Erdős-Rényi ensemble which consists of a random graph on $N$ vertices in which each edge is chosen independently with probability $p$. The adjacency matrix of this graph is called the Erdős-Rényi matrix. The Erdős-Rényi matrix has typically $pN$ nonzero entries in each column and is sparse if $p\ll 1$. As the matrix entries take values or $1$, the mean of the entries is not . Ignoring the nonzero mean for the moment, the Erdős-Rényi matrix can be viewed as a singular Wigner matrix, as the probability distribution of the matrix elements is highly concentrated around . The singular nature of this ensemble can be expressed by the fact that the $k$-th moment of a matrix entry is bounded by

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

It was conjectured in that for sparse random matrices there exists a critical value $p_{c}>1$, such that for $pN>p_{c}$, the bulk eigenvalues are strongly correlated and are characterized by GOE/GUE random matrix statistics; for $pN<p_{c}$, the eigenvalues remain uncorrelated and follow Poisson statistics. This conjecture is supported by a wealth of numerical simulations and a nonrigorous supersymmetric approach . The best rigorous result in this direction was obtained in the works and asserts that if

then the averaged $n$-point correlation functions of the Erdős-Rényi ensemble coincide with the GOE.

In the present work we prove that in the regime

the local statistics of the Erdős-Rényi ensemble exhibit bulk universality. In addition to proving that the averaged $n$-point correlation functions coincide with the GOE, we also prove the universality of the eigenvalue gaps with a fixed label. To further place the present work in context we recall the three-step strategy developed in for proving universality for Wigner matrices:

Establish a local semicircle law controlling the number of eigenvalues in windows of size $\log(N)^{C}/N$.

Analyze the local ergodicity of Dyson Brownian motion (DBM) to obtain universality for Wigner ensembles with a small Gaussian component.

A density argument comparing a general Wigner matrix to one with a small Gaussian component.

For an overview of this three-step strategy and more details we refer the reader to . The local semicircle law for sparse random matrices in the regime (1.4) was established in . However, in Steps (2) and (3) were only completed for sparse random matrices in the regime (1.3).

The key input from Step (1) into Step (2) is a high-probability a-priori bound on the eigenvalue locations which is a corollary of the strong semicircle law. In the case of Wigner matrices, this bound is optimal and it allows one to conclude that local equilibrium is reached by DBM in times $t=N^{\epsilon}/N$. Sparse random matrices do not obey as strong a semicircle law and so the time to equilibrium found in the work was much longer. Moreover, due to the slow decay of the third moment, the approximation in Step (3) is not as strong in the case of Wigner matrices and so could not be used for the large times required by Step (2). These two factors led to the condition (1.3) of .

In the recent work , the optimal time of Dyson Brownian motion to local equilibrium was established for a wide class of initial data (see for related results on DBM with general initial data). Using this as an input we will prove that DBM reaches local equilibrium in the optimal time $t=N^{\epsilon}/N$ when the initial data is a sparse random matrix. For the comparison of correlation functions, Step (3) was obtained in via a Green function comparison theorem. In this paper, we will use a lemma of which asserts continuity of DBM when viewed as a matrix Ornstein-Uhlenbeck process. It is interesting to note that this continuity lemma provides a very convenient tool for Step (3) in the sparse setting whenever a “weak local semicircle law” is valid – and in the case of sparse random matrices this is provided by a result of .

The universality of a single gap was established in for Wigner matrices, i.e., for $p\sim O(1)$. The work also yields gap universality for DBM after the optimal time $t=N^{\epsilon-1}$ and so our task is similar to the proof of the correlation function universality in that we must establish Step (3) and compare the gap distributions. However, the completion of Step (3) presents a major difficulty. Previously, for gap universality this step was based on results of or which states that the gap distribution of two Wigner ensembles coincide provided that the first four moments of these two ensembles match. However, these results were based on two inputs: firstly, certain level repulsion estimates; secondly, an optimal eigenvalue rigidity estimate.

Optimal eigenvalue rigidity estimates for Wigner ensembles were proven in . This estimate states that for any eigenvalue $\lambda_{i}$ in the bulk we have that $|\lambda_{i}-\gamma_{i}|\leq N^{-1+\delta}$ with overwhelming probability, where $\gamma_{i}$ is the deterministic classical location of the $i$-th eigenvalue. The best known rigidity result for sparse random matrices is from , where it was shown that the bulk eigenvalues satisfy $|\lambda_{i}-\gamma_{i}|\leq p^{-1}N^{-1+\delta}$ with overwhelming probability.

Moreover, we do not expect that optimal rigidity holds for sparse random matrices. In fact in , it was shown that for sparse random matrices the linear statistics

converges to a normal random variable with variance $O((N^{2}p)^{-1})$, for $\phi$ satisfying some regularity conditions. This implies that the fluctuations of the eigenvalues are at least of order $O((N\sqrt{p})^{-1})$ on average, and so we do not expect optimal rigidity to hold if $p\ll 1$.

As mentioned above, the lack of rigidity for sparse ensembles resulted in the longer time to equilibrium for DBM being found in , and it again causes difficulty in trying to compare gap statistics. Rigidity results are a crucial input in establishing level repulsion estimates for Wigner matrices which are needed in order to compare the gap statistics of two ensembles. It was proven in that a level repulsion estimate will hold for DBM after a short time. We show that one can combine the delocalization of eigenvectors together with the Ornstein-Uhlenbeck continuity lemma of to pass this level repulsion from DBM to the initial sparse random matrix. This level repulsion estimate then gives us a key input for Step (3) and we are able to conclude universality of the gap statistics.

Previous level repulsion estimates were obtained in for Wigner ensembles whose entries have a smooth distribution. Estimates without a smoothness condition were obtained in and also in the very recent work . A weak level repulsion estimate for Wigner matrices also follows from the results of .

In fact, our strategy outlined above applies to a wider class of random matrices than sparse or Wigner random matrices alone. We will prove that bulk universality holds for a class of random matrices obeying only a weak estimate on the distribution of its eigenvalues, a weak decay condition on the third moment of the entries and an eigenvector delocalization estimate.

The remainder of the paper is outlined as follows. In Section 2 we introduce the random matrix models under consideration, which we will call ‘stable’ random matrices, and state our main results. In Section 3 we obtain bulk universality for Gaussian divisible ensembles. In Section 4 we state and prove our level repulsion results for stable random matrices. In Section 5 we complete Step (3) outlined above and compare the bulk statistics of a general stable random matrix and a Gaussian divisible ensemble. In Section 6 we prove that sparse random matrices are stable and conclude universality for sparse random matrices.

Definition of model and main results

In our paper we will only state and prove our results for real symmetric random matrix ensembles. All of our methods extend with only notational changes to complex Hermitian ensembles.

In this section we introduce the class of sparse random matrices that we study. We follow the notations and definitions of . The motivating example is the Erdős-Rényi matrix whose entries are independent up to the constraint that the matrix is symmetric, and equal to $1$ with probability $p$ and with probability $1-p$. It is notationally convenient to replace the parameter $p$ with $q$ defined through

We allow $q$ to depend on $N$. We also rescale the matrix so that the bulk of its spectrum lies in an interval of order $1$. For the Erdős-Rényi matrix we define $H$ to be the $N\times N$ symmetric matrix whose entries $h_{ij}$ are independent up $h_{ij}=h_{ji}$ and each element is distributed according to

We further extract the mean of each entry and write

where $\boldsymbol{e}$ is the unit vector

Note that the matrix elements of $B$ are centered. It is easy to check that the matrix elements of $B$ satisfy the moment bounds

We are prompted to make the following definition. We introduce two parameters $q$ and $f$ which may be $N$-dependent.

$H$ is a sparse random matrix with sparsity parameter $q$ and mean $f$ if it is of the form

where $f$ is a deterministic number satisfying

and $B$ is a matrix with real and independent entries up to the symmetry constraint $b_{ij}=b_{ji}$ which satisfy

for $1\leq i\leq j\leq N$ and $2\leq k\leq\log(N)^{10\log\log N}$ where $C$ is a positive constant. We assume that $q$ satisfies

2 Universality of sparse random matrices

Our main result is the bulk universality of sparse random matrices as defined above.

Let $H$ be a sparse random matrix as defined in Definition 2.1, with sparsity parameter $q$ satisfying

for some number $\alpha>0$. Then $H$ exhibits bulk universality in the following two forms. Firstly, $H$ has the single gap universality in the bulk. For any $\kappa>0$ and index $i\in[[\kappa N,(1-\kappa)N]]$

Secondly, the averaged $n$-point correlation functions of $H$ are universal in the bulk. We denote the $n$-point correlation function functions of $H$ and $GOE$ by $\rho_{H}^{(n)}$ and $\rho_{GOE}^{(n)}$ respectively, then for any $\delta>0$ and $E\in(-2,2)$, and $b\geq N^{-1+\delta}$

3 Stable random matrices

and the mean $0\leq f\leq N^{C}$ may depend on $N$.

We define the following matrix stochastic differential equation which is an Ornstein-Uhlenbeck version of the Dyson Brownian motion. The dynamics of the matrix entries are given by the stochastic differential equations

where $B$ is symmetric with $(B_{ij}(t))_{1\leq i\leq j\leq N}$ a family of independent Brownian motions. We denote $H_{t}=(h_{ij}(t))_{1\leq i,j\leq N}$, and so $H_{0}=H$ is our original matrix. More explicitly, for the entries of $H_{t}$, we have

where $r=\min_{i\leq j}\{Ns_{ij}\}$, $G$ denotes a standard gaussian orthogonal ensemble, which is independent of $H_{t}^{(1)}$. The entries of the matrix $H_{t}^{(1)}$ is given by

We define the deformed matrix $\theta^{ab}H_{t}$ by

where $\theta_{kl}^{ab}=1$ unless $\{k,l\}=\{a,b\}$ in which case $\theta_{ab}^{ab}=\theta_{ba}^{ab}$ will be a number satisfying $0\leq\theta_{ab}^{ab}=\theta_{ba}^{ab}\leq 1$.

Let $A$ be an $N\times N$ deterministic real symmetric matrix. We denote the eigenvalues of $A$ as $\{\lambda_{1},\lambda_{2},\cdots,\lambda_{N}\}$ and corresponding eigenvectors $\{u_{1},u_{2},\cdots,u_{N}\}$. For any (small) number $\delta>0$, we call the matrix $M$ $\delta$-general if:

The eigenvectors of $A$ are completely delocalized: $\sup_{i,j}|u_{i}(j)|^{2}\leq CN^{-1+\delta}$.

The eigenvalues of $A$ do not accumulate: there is an universal constant $C$, such that for any interval $I$ with length $|I|\geq N^{-1+\delta}$, we have $\#\{i:\lambda_{i}\in I\}\leq C|I|N$.

The entries of $H$ are independent up to symmetry.

For any time $t=N^{-1+\epsilon}$, where $\epsilon>0$ can be arbitrarily small, the random matrix $H_{t}^{(1)}$ defined in (2.17) satisfies the weak local semicircle law, i.e. for any (large) number $D>0$, and (small) number $\delta>0$, the following holds with probability larger than $1-N^{-D}$,

For any time $0\leq s\leq t$, any (large) number $D>0$, and (small) number $\delta>0$, $\theta^{ab}H_{s}$ is $\delta$-general with probability larger than $1-N^{-D}$, with the constants in Definition 2.3 uniformly in $s$.

The second condition (2) implies that for any $\kappa>0$, the eigenvalues $\lambda_{i}(H_{t}^{(1)})\in(-2+\kappa^{2/3},2-\kappa^{2/3})$ for $i\in[[2\kappa N,(1-2\kappa)N]]$ with overwhelming probability.

In order to simplify our proof we have assumed that the matrix elements are independent. Independence is mainly used in the comparison Lemma 4.3, which will still hold if the matrix entries of $H$ are weakly correlated.

The motivating example of our paper is the sparse random matrix, and we have therefore assumed that the Stieltjes transform of the empirical eigenvalue distribution of $H_{t}^{(1)}$ is close to $m_{sc}$, i.e., the semicircle law. The semicircle law, however, does not play an active role and our methods can be applied to the case in which the semicircle law is replaced by other densities. We will not pursue this direction and refer the interested reader to and for examples in which the limiting eigenvalue density differs from the semicircle law.

In this paper we will prove that the local statistics of stable random matrices are universal.

Let $H$ be a stable random matrix as defined in Definition 2.4. The local statistics of $H$ in the bulk are universal. Firstly, $H$ has gap universality with a fixed label in the bulk. For any $\kappa>0$ and index $i\in[[\kappa N,(1-\kappa)N]]$, we have

The averaged $n$-point correlation functions of $H$ are universal in the bulk. We denote the $n$-point correlation function functions of $H$ and $GOE$ by $\rho_{H}^{(n)}$ and $\rho_{GOE}^{(n)}$ respectively, then for any $\delta>0$ and $E\in(-2,2)$, and $b\geq N^{-1+\delta}$

The goal of this section is to establish bulk universality for the matrix valued stochastic process $H_{t}$ defined as in (2.17) after a short time $t=N^{-1+\epsilon}$.

Let $H$ be a stable random matrix, and let $H_{t}$ be defined as in (2.17). For any small $\epsilon,\kappa>0$ there is a constant $c>0$, which depends on $\epsilon$, such that the following holds for $t=N^{-1+\epsilon}$. and any index $i\in[[\kappa N,(1-\kappa)N]]$

Moreover, for any $\delta,\kappa>0$, $E\in(-2+\kappa,2-\kappa)$ and $b\geq N^{-1+\delta}$, we have

For the proof we shall first restate the main result of in a form convenient for our proof. For this we will introduce some notation. For a deterministic matrix $A$ we define

where $G$ is a GOE matrix and $r$ is the constant from (2.17). We denote by $m_{t}$ the Stieltjes transform of the free convolution of the empirical eigenvalue distribution of $A$ and the semicircle law of $\vartheta_{t}G$, and so $m_{0}$ is the Stieltjes transform of empirical eigenvalue distribution of $A$. More explicitly, $m_{t}$ is defined as the unique solution to the functional equation

The free convolution is well-studied, see, e.g, . It is known that $m_{t}$ is the Stieltjes transform of a measure with a density which we denote by $\rho_{t}$ which is analytic on the interior of its support, for any $t>0$. Denote the classical eigenvalue locations of the density $\rho_{sc}$ and $\rho_{t}$ by $\gamma_{i}$ and $\gamma_{i,t}$, respectively,

The following follows from Theorem 2.5 of .

Fix $\epsilon>0$ and suppose that there are constants $c_{1}>0$ and $C_{1}>0$ such that

for all large enough $N\geq N(\epsilon)$. Above $j$ is any index satisfying $j\in[[\kappa_{1}N,(1-\kappa_{1})N]]$ where $\kappa_{1}>0$.

and the set of real symmetric $N\times N$ matrices

and $c(\epsilon/3)$ is from the constant in (2.19) of Definition 2.4.

Let $\kappa,\omega>0$ and $A\in\mathcal{D}$ as above. Then, for any $\epsilon>0$ and $t=N^{-1+\epsilon}$,

Therefore we have $|\vartheta_{t}^{2}m_{t}|\leq\vartheta_{t}=O(t^{1/2})$. Since $A\in\mathcal{D}$, for any $z=E+i\eta$, such that $E\in(-4,4)$ and $N^{-1+\epsilon/3}\leq\eta\leq 9$, we have that $z+\vartheta_{t}^{2}m_{t}\in\mathcal{F}$. The defining relation (3.8) leads to

To control $m_{sc}(z+\vartheta_{t}^{2}m_{t})$ we have the following stability estimate of $m_{sc}$: for any $z,\Delta z$ with non-negative imaginary part, and $|\Delta z|\leq 1$, then

From this lemma we conclude the following.

For any $\epsilon,\kappa>0$, time $t=N^{-1+\epsilon}$, any real symmetric matrix $A\in\mathcal{D}$, and $E\in(-2+\kappa,2-\kappa)$ we have

Moreover for any index $i$ such that $\lambda_{i}(A)\in(-2+\kappa,2-\kappa)$, we have

where the constant $\omega$ is from the definition (3.8) of the set $\mathcal{D}$.

where we have used $|\rho_{t}(x)|\leq C$ on $I_{1}\cup I_{2}$. Moreover, we have

given $\omega\leq(1-\epsilon)/2$. (3.15) and (3.16) together lead to (3.13).

This follows from [25, Lemma 7.17], using Lemma 3.3 as input. Therefore,

By the hypotheses of stability of $H$ we have that $H_{t}^{(1)}\in\mathcal{D}$ with probability greater than $1-N^{-D}$ for any large $D$. We denote the density of free convolution of $H_{t}^{(1)}$ and $\vartheta_{t}G$ as $\rho_{t}^{H}$, and its $i$-th classical eigenvalue location as $\gamma_{i,t}^{H}$. From Theorem 3.2 we have

But then by Lemma 3.4 we have that $|\rho_{t}^{H}(\gamma_{i,t}^{H})-\rho_{sc}(\gamma_{i})|\leq N^{-\omega/2}$, therefore

for some $C>0$ depending on first derivative and the support of the test function $O$. We therefore obtain that for $H_{t}^{(1)}\in\mathcal{D}$ that

if we choose $c$ small enough, such that $c<\omega/2$. And if we take expectation over $H_{t}^{(1)}$, (3.1) follows.

for $b=N^{-1+\delta}$ for any $\delta>0$. For this argument, we refer the reader to, e.g., [14, Theorem 2.1]. We conclude (3.1) by integrating over $H_{t}^{(1)}$. ∎

Level repulsion for stable random matrices

In this section we prove the following level repulsion estimate for stable random matrices. It will be used for the comparison of the single gap statistics between $H$ and $H_{t}$ in Section 5.

Let $H$ be a stable random matrix as defined in Section 2.3. Given any $0<\tau<\alpha/8$, any (small) number $\kappa>0$, and any index $i\in[[\kappa N,(1-\kappa)N]]$, we have

The above estimate suffices for the comparison of the single gap statistics of $H$ and $H_{t}$. We have not tried to optimize the exponent $-\tau/2$, which is far from optimal. The proof below is easily modified to give $-\tau+\delta$ for any $\delta>0$.

It was proven in that a level repulsion estimate holds for the matrix $H_{t}$ for $t=N^{-1+\epsilon}$. To obtain the level repulsion estimate for $H$, we need to prove that the change of eigenvalues up to time $t=N^{-1+\epsilon}$ is negligible. For this we will repeatedly use the following lemma which asserts continuity of DBM when viewed as a matrix Ornstein-Uhlenbeck process. It is a minor modification of [6, Lemma A.2].

Define $H_{t}$ as in (2.15). Let $F$ be a smooth function on the space of real symmetric matrices satisfying

Above, the deformed matrix $\theta^{ab}H_{s}$ is defined by $(\theta^{ab}H)_{kl}=f+\theta^{ab}_{kl}\left(h_{kl}-f\right)$, where $\theta_{kl}^{ab}=1$ unless $\{k,l\}=\{a,b\}$ and $\theta_{ab}^{ab}=\theta_{ba}^{ab}$ is a number satisfying $0\leq\theta_{ab}^{ab}=\theta_{ba}^{ab}\leq 1$. Then

Given a real symmetric matrix $A$, we denote its eigenvalues by $\{\lambda_{1},\lambda_{2},\cdots,\lambda_{N}\}$, and corresponding eigenvectors $\{u_{1},u_{2},\cdots,u_{N}\}$. If $\lambda_{i}$ is a simple eigenvalue of $A$, we define $P_{i}$ to be the orthogonal projection to the one-dimensional eigenspace corresponding to $\lambda_{i}$, and the resolvent $R_{i}(A)$ the unique real symmetric matrix inverting $\lambda_{i}-A$ on the range of $I-P_{i}(A)$, and vanishing on the range of $P_{i}(A)$. $R_{i}(A)$ can be written explicitly as

Moreover $R_{i}(A)$ can be written as the following contour integral,

where we pick the contour $\omega$ to enclose only $\lambda_{i}$. From the above formula it is clear that $R_{i}(A)$ is a smooth function on a neighbourhood of $A$ if $\lambda_{i}$ is a single eigenvalue. We refer the reader to the book [29, Chapter XII] for related properties.

If $\lambda_{i}$ is a single eigenvalue of $A$, we define the quantity

This quantity plays an important role in , where it was observed that it captures quantitatively the derivatives of $\lambda_{i}(A)$. Here we write it in terms of the Green function, and prove it is stable under the DBM (2.15). As a result, based on the idea of Green function comparison, it can be used to derive the weak level repulsion estimate Theorem 4.1, once we know such an estimate for larger times, see Theorem 4.4.

Since $Q_{i}(A)$ is not well-defined on the space of real symmetric matrices (it will blow up when $\lambda_{i}(A)$ is not a single eigenvalue), we have to compose it with a cutoff function $\chi_{M}$, where $M:=N^{2\tau}$ and the (small) constant $\tau>0$ will be chosen later. We choose the cutoff function $\chi_{M}(x)$ which satisfies the following two properties: (1) $\chi_{M}$ is smooth, and the first three derivatives are bounded by some constant $C$, i.e. $|\chi_{M}^{\prime}(x)|,|\chi_{M}^{\prime\prime}(x)|,|\chi_{M}^{\prime\prime\prime}(x)|\leq C$. (2) On the interval $[0,M]$, $|\chi_{M}(x)-x|\leq 1$, and for $x\geq M$, $\chi_{M}(x)=M$.

If $\lambda_{i}$ is a single eigenvalue of $A$, then in a neighborhood of $A$, $\chi_{M}(Q_{i}(A))$ is smooth; if $\lambda_{i}$ is not a single eigenvalue of $A$, then in a neighborhood of $A$, $\chi_{M}(Q_{i}(A))$ is constant, which is also smooth. Therefore $\chi_{M}(Q_{i}(A))$ is a well defined smooth function on the space of real symmetric matrices.

Our proof of Theorem 4.1 consists of three steps:

In the remainder of this section we denote the eigenvalues of $H_{t}$ by $\lambda_{1}(t)\leq\lambda_{2}(t)\leq\cdots\leq\lambda_{N}(t)$, and so the eigenvalues of $H$ are $\lambda_{1}(0)\leq\lambda_{2}(0)\leq\cdots\leq\lambda_{N}(0)$.

The following level repulsion estimate is an immediate consequence of [25, Theorem 3.6].

Let $H$ be a stable random matrix as defined in Section 2.3. Given any (small) number $\omega>0$, and (large) number $D>0$, we have that

for any $i\in[[\kappa N,(1-\kappa)N]]$ and $t\geq N^{-1+\epsilon}$.

From this we derive the following estimate.

for $t=N^{-1+\epsilon}$ for any $\epsilon>0$ and all small $\tau>0$.

By our assumption with probability larger than $1-N^{-D}$, the matrix $H_{t}$ is $\delta$-general in the sense of Definition 2.3. Combining this with Theorem 4.4, we have

For those $H_{t}$ which are $\delta$-general in the sense of Definition 2.3, $|U_{n}|\leq C2^{n}N^{\delta}$, for $0\leq n\leq\lceil\log_{2}N\rceil$. On the event that $H_{t}$ is $\delta$-general and $|\lambda_{i}(t)-\lambda_{i\pm 1}(t)|\geq\theta N^{-1}$, we derive the estimate,

where $\omega>0$ can be any small number. Therefore

This finishes the proof of the first step. In order to apply Lemma 4.3 for the second step, we need to control the third derivative of $\chi_{M}(Q_{i}(\theta^{ab}H_{s}))$.

Let $A$ be an $N\times N$ deterministic real symmetric matrix. If $A$ is $\delta$-general in the sense of Definition 2.3 and

We denote $G=(A-z)^{-1}$ the resolvent of $A$ and by $\lambda_{j}$ and $u_{j}$ the eigenvalues and eigenvectors of $A$. Notice that (4.9) implies $|\lambda_{i}-\lambda_{i\pm 1}|\geq N^{-1-\tau}$. The same dyadic argument leading to (4.8) yields

Also we have the trivial bound for higher moments

We denote by $V$ the matrix whose matrix elements are zero everywhere except at the $(a,b)$ and $(b,a)$ position, where it equals one. From the formula (4.3),

Notice that $\partial_{ab}^{(k)}G=(-1)^{k}k!(GV)^{k}G$. By the Leibniz rule, (4.13) can be written as a sum of terms in the following form

where $k_{1}+k_{2}+k_{3}+k_{4}=k$. We will only prove (4.10) for $k=3$; that is, we will prove

The computations for $k=1,2$ are much easier. To evaluate (4.14), we need to compute the first three derivatives of $\lambda_{i}(A)$ with respect to the $(a,b)$-th entry of $A$. We use the following formula to compute the derivatives of $\lambda_{i}$,

where the contour encloses only $\lambda_{i}$. The $k$-th derivative with respect to $(a,b)$-th entry is

Some straightforward but tedious integration similar to (4.16), (4.17),(4.18) reveals that $\partial_{ab}^{(3)}Q_{i}(A)$ is a sum of the following terms (for simplicity of notation we write $V_{jk}:=u_{j}^{*}Vu_{k}$):

Indeed, if one takes a close look at the expression (4.14), the only singularity enclosed by our contour is $\lambda_{i}$. Therefore by Cauchy’s formula, the integral is sum of terms with denominators: $\prod_{j}(\lambda_{i}-\lambda_{j})$, as appearing in the above expressions.

Since the eigenvectors of $A$ are completely delocalized we see that

This, together with the bounds (4.11) and (4.12) yields (4.15) ∎

Notice that the right hand side of (4.20) vanishes unless $Q_{i}(\theta^{ab}H_{s})\leq M$. Since $H$ is stable, $\theta^{ab}H_{s}$ satisfies all the assumptions in Lemma 4.10, with probability larger than $1-N^{-D}$ for any large number $D$. Therefore

On the complement of the above event we will use the following deterministic bound

We want to apply Lemma 4.3 with $F=\chi_{M}\circ Q_{i}$. For this choice of $F$ we can take $B$ to satisfy

where the last factor $N^{-\alpha}$ is from the third moment of $h_{ij}(s)$. We conclude that

Since the two numbers $\epsilon,\delta>0$ can be arbitrarily small, therefore we can choose $\tau=(\alpha-\epsilon-12\delta)/8$ and (4.21) simplifies to

and the proof is easily concluded by the Markov inequality. ∎

Bulk universality of stable random matrices

In this section we prove bulk universality for stable random matrices $H$, i.e., Theorem 2.8 by comparing the local statistics between $H$ and $H_{t}$. This will yield the theorem as Theorem 3.1 shows that the latter ensemble exhibits bulk universality. In the following of this section we denote the eigenvalues of $H_{t}$ by $\lambda_{1}(t)\leq\lambda_{2}(t)\leq\cdots\leq\lambda_{N}(t)$. And so the eigenvalues of $H$ are $\lambda_{1}(0)\leq\lambda_{2}(0)\leq\cdots\leq\lambda_{N}(0)$.

We will obtain the gap universality of $H$ from the more general comparison result below.

Let $H$ be a stable random matrix and let $H_{t}$ be defined as in (2.15). Take $t=N^{-1+\epsilon}$. Then for $\epsilon>0$ small enough we have

For simplicity of notation, we only state the proof for $n=1$ case, i.e. for any $i\in[[\kappa N,(1-\kappa)N]]$

Take a cutoff function $\rho_{M}$ such that $\rho_{M}(x)=1$ for $x\leq M$ and $\rho_{M}(x)=0$ for $x\geq 2M$, where $M=N^{2\tau}$ and $\tau>0$ is a small constant. By the level repulsion of $H$ and $H_{t}$ from the previous section, we know that

Notice that $O(N\lambda_{i}(A))\rho_{M}(Q_{i}(A))$ is a well defined smooth function on the space of symmetric functions. Moreover, if the matrix $A$ is $\delta$-general in the sense of Definition 2.3 the same argument as in Proposition 4.6 implies

where $c$ and $C$ are constants. Therefore by Lemma 4.3, we have

if we take $c(\delta+\tau)+\epsilon<\alpha/2$. ∎

For the universality of the correlation functions, due to the lack of optimal rigidity, one can not directly deduce universality from (5.1). We need to prove the following Green function comparison lemma:

Let $H$ be a stable random matrix as defined in Section 2.3, and let $H_{t}$ be defined as in (2.15). Let $\delta>0$ be arbitrary and choose an $\eta$ with $N^{-1-\delta}\leq\eta\leq N^{-1}$. For any sequence of positive integers $k_{1},k_{2},\dots,k_{n}$, any set of complex parameters $z_{j}^{m}=E_{j}^{m}\pm\eta$, where $1\leq j\leq k_{m}$, $1\leq m\leq n$, $|E_{j}^{m}|\leq 2-\kappa$, and the $\pm$ signs are arbitrary, we have the following. Let $G_{t}(z)=(H_{t}-z)^{-1}$ be the resolvent and let $F(x_{1},x_{2},\cdots,x_{n})$ be a test function such that for any multi-index $\alpha=(\alpha_{1},\cdots,\alpha_{n})$ with $1\leq|\alpha|\leq 4$ and for any $\omega>0$ sufficiently small, we have

for some constant $C_{0}$. Then the following holds:

where $c$ and $C$ are constants depending on $\kappa$, $n$, $k_{1},k_{2},\cdots,k_{n}$ and $C_{0}$. The second term above is the same as the first term, but with $G_{0}$ replacing $G_{t}$ everywhere.

For simplicity of notation, we state the proof only for $n=1$ and $k_{1}=1$ case, i.e.

We will prove this lemma using Lemma 4.3. We must compute derivatives of the trace of the Green’s function of the deformed matrix $\theta^{ab}H_{s}$. We denote the resolvent of $\theta^{ab}H_{s}$ by $G(z)=(\theta^{ab}H_{s}-z)^{-1}$. For the derivatives of $G(z)$, we have $|\operatorname{Tr}\partial_{ab}^{(k)}G|=|(-1)^{k}k!\operatorname{Tr}(GV)^{k}G|$, where $V$ is the matrix whose matrix elements are zero everywhere except at the $(a,b)$ and $(b,a)$ position, where it equals one. Since $V$ has at most two nonzero elements, the trace $(GV)^{k}G$ contains at most $2^{k}N$ terms. Furthermore, each term is a product of $k+1$ entries of $G$, e.g. $\operatorname{Tr}GVG=\sum_{k}(G_{kb}G_{ab}+G_{ka}G_{bk})$. We first derive a bound on the resolvent entries $G_{jk}(E+i\eta)$ down to $\eta\geq N^{-1-\delta}$ when $\theta^{ab}H_{s}$ is $\delta$-general. Using the delocalization of the eigenvectors we have,

For $\delta$-general $\theta^{ab}H_{s}$ we have $|U_{n}|\leq C2^{n}N^{\delta}$, for $0\leq n\leq\lceil\log_{2}N\rceil$. We can divide the summation over $i$ into $\cup_{n}U_{n}$,

When $\theta^{ab}H_{s}$ is not $\delta$-general we still have the deterministic upper bound

Therefore we can take $F(A)=N^{-1}\operatorname{Tr}(A-E-i\eta)^{-1}$ for $N^{-1-\delta}\leq\eta$ in Lemma 4.3. For $B$ we have the upper bound

Once we have the above lemma, the following theorem from [15, Theorem 2.1] transforms the information of the Green function to the correlation functions of $H$ and will complete the proof of Theorem 2.8.

provided that $t$ is chosen so that $CtN^{1+c\delta-\alpha}\leq N^{-\alpha/2}$.

The universality of the gap statistics follows from Theorem 3.1 and Lemma 5.1. The universality of the correlation functions follows from Theorem 3.1, Lemma 5.2 and Theorem 5.3. ∎

Universality of sparse random matrices

In this section we prove Theorem 2.2, the bulk universality of sparse matrices, by checking that sparse matrices satisfy the hypotheses of Definition 2.4 of stable random matrices. In the following we collect some facts about sparse matrices proved in .

Let $H$ be a sparse Wigner matrix as in Definition 2.1. We denote the eigenvalues of $H$ as $\lambda_{1}\leq\lambda_{2}\leq\cdots\leq\lambda_{N}$, the corresponding eigenvectors $u_{1},u_{2},\cdots,u_{N}$, and the resolvent $G(E+i\eta)=(H-E-i\eta)^{-1}$. Then for all (small) $\omega,\delta>0$, (large) $D>0$ and large enough $N\geq N(\omega,\delta,D)$ the following holds with probability larger than $1-N^{-D}$.

All eigenvalues of $H$ are in the interval $$, i.e.$-3\leq\lambda_{1}\leq\lambda_{2}\cdots\leq\lambda_{N-1}\leq 3$, except for the largest eigenvalue$\lambda_{N}$.

We have the weak local semi-circle law for individual resolvent entries: there exists a constant $C$ such that $|G_{jk}(E+i\eta)|\leq C$, for $\eta\geq N^{-1+\delta}$

We have the local semi-circle law for the Stieltjes transform of eigenvalues of $H$:

Sparse random matrices in the sense of Definition 2.1 are stable. Therefore, Theorem 2.2 holds.

Conditions (1) and (3) of Definition 2.4, i.e., the independent entries and moment conditions, follow from the definition of a sparse matrix. The fact that $\theta^{ab}H_{s}$ is $\delta$-general, i.e., condition (4), will follow from the bounds (ii) in Theorem 6.1. If the resolvent elements of $\theta^{ab}H_{s}$ are bounded down to the scale $\eta\geq N^{-1+\delta}$ then by taking $E=\lambda_{i}$ and $\eta=N^{-1+\delta}$ in the following identity

we see that $|u_{i}(j)|^{2}\leq CN^{-1+\delta}$ and so the eigenvectors of $\theta^{ab}H_{s}$ are completely delocalized. For any interval $I=[E-\eta,E+\eta]$, such that $N^{-1+\delta}\leq\eta$, we have

Therefore, we get that $\#\{i:\lambda_{i}\in I\}\leq C|I|N$ by rearranging the above expression.

It therefore suffices to prove that the resolvent entries of the deformed matrix $\theta^{ab}H_{s}$ are bounded down to the scale $\eta=N^{-1+\delta}$. For each $s$, $H_{s}$ is a sparse matrix and so by Theorem 6.1 we know that its resolvent entries are bounded with probability greater than $1-N^{-D}$ for any large $D$.

The deformed matrix $\theta^{ab}H_{s}$ is a rank two perturbation of $H_{s}$, i.e. $\theta^{ab}H_{s}=H_{s}-V$, where $V$ is the matrix whose matrix elements are zero everywhere except at the $(a,b)$ and $(b,a)$ position, where it equals $(1-\theta^{ab}_{ab})h_{ab}(s)$. By our assumption on the moments of sparse Wigner matrix (2.9), we have that

for any large $D$. We denote the resolvent of $H_{s}$ as $G=(H_{s}-z)^{-1}$. The resolvent elements of $\theta^{ab}H_{s}$ are given by the formula

with probability greater than $1-N^{-D}$, for $N$ sufficiently large. We get $\max_{j,k}|(\theta^{ab}H_{s}-z)_{jk}^{-1}|\leq 2C$, by taking maximum over $j$ and $k$ in above estimate, and rearranging it. This finishes the proof that with probability larger than $1-N^{-D}$ for any (large) number $D$, $\theta^{ab}H_{s}$ is general.

For the local semi-circle law of $H_{t}^{(1)}$, i.e., condition (2), the variance of the diagonal terms and off-diagonal terms of $H_{t}^{(1)}$ are $e^{-t}N^{-1}$ and $(1+e^{-t})/2N$ respectively. Therefore after normalizing by $(1-(1-e^{-t})\frac{N+1}{2N})^{-1}=1+O(t)$, it is a generalized sparse matrix. By (3.12), the normalization factor gives us an error of order at most $O(\sqrt{t})$: with probability larger than $1-N^{-D}$,

where $m_{N}^{(1)}(z)$ is the Stieltjes transform of the empirical eigenvalue distribution of $H_{t}^{(1)}$. Therefore we can take $c(\delta)=\frac{1}{2}\min\{\alpha,\delta,\frac{1-\epsilon}{2}\}$ in (2.19).

We have checked that sparse random matrices are stable, and so Theorem 2.2 now follows from Theorem 2.8. ∎

References