Abstract
Let \({\mathcal {A}}\) be the adjacency matrix of a random d-regular graph on N vertices, and we denote its eigenvalues by \(\lambda _1\geqslant \lambda _2\cdots \geqslant \lambda _{N}\). For \(N^{2/3+o(1)}\leqslant d\leqslant N/2\), we prove optimal rigidity estimates of the extreme eigenvalues of \({\mathcal {A}}\), which in particular imply that
with very high probability. In the same regime of d, we also show that
where \(\textrm{TW}_1\) is the Tracy–Widom distribution for GOE; analogue results also hold for other non-trivial extreme eigenvalues.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
In this article, we consider a random d-regular graph on N vertices, under the uniform probability measure. Let \(\mathcal A \in \mathbb R^{N\times N}\) be the adjacency matrix of the graph, and we denote its eigenvalues by \(\lambda _1\geqslant \cdots \geqslant \lambda _N\). It is easy to see that \( \lambda _1=d\, \) with corresponding eigenvector \({{\textbf {e}}}{:}{=}N^{-1/2}(1,1,\ldots ,1)^*\). The behavior of nontrivial extreme eigenvalues of \(\mathcal {A}\) is of particular interest in graph theory and computer science. For instance, the gap between the first and second eigenvalues measures the expanding property of the graph. For a deterministic d-regular graph on N vertices, the Alon-Boppana bound [2] states that
for d fixed and N large enough. A Ramanujan graph is a d-regular graph whose nontrivial eigenvalues are bounded in absolute value by \(2\sqrt{d-1},\) i.e. it is a graph that essentially saturates the Alon-Boppana bound. Ramanujan graphs were first constructed by Lubotzky, Phillips and Sarnak [34], and by Margulis [37] for some values of d. The construction of Ramanujan graphs in the bipartite case for all degrees was given by Marcus, Spielman and Srivastava [35, 36]. For the random d-regular graph \(\mathcal {A}\), when d is fixed, Friedman [21] showed that, for sufficiently large N,
with high probability (the proof was later substantially simplified by Bordenave [8]). This means that a random d-regular graph is typically “almost Ramanujan". More recently, Huang, McKenzie and Yau [28] (following Huang and Yau [29]) extended this result by showing the near-optimal rate
with probability \(1-N^{-1+o(1)}\).
The case of \(d \leqslant N/2\) that tends to infinity with N was conjectured by Vu [43] to have
with high probability. The magnitude bound \(\lambda _2+|\lambda _N|=O(\sqrt{d})\) with high probability was proved by Broder, Frieze, Suen and Upfal [11] for \(d=o(\sqrt{N})\); by Cook, Goldstein and Johnson [12] for \(d=O(N^{2/3})\); by Tikhomirov and Youssef [42] for all \(d \leqslant N/2\). The eigenvalue locations were proved to satisfy \(\lambda _2, |\lambda _N| =2\sqrt{d-1}(1+o(1))\) in the regime \(N^{o(1)}\leqslant d \leqslant N^{2/3-o(1)}\), by Bauerschmidt, Huang, Knowles and Yau [4]. Very recently, Sarid [39] proved (1.1) for \(1\ll d\leqslant cN\), where c is a small constant.
Our first main result determines the extreme eigenvalue locations in the regime \(N^{2/3+o(1)}\leqslant d \leqslant N/2\), with optimal error bounds. Together with [4, 39], we settle the conjecture (1.1) in the whole regime \(1 \ll d \leqslant N/2\). We may now state our first main result.
Theorem 1.1
Fix \(\tau >0\), \(k\geqslant 2\), and assume \(N^{2/3+\tau }\leqslant d\leqslant N/2\). For any fixed \(\varepsilon ,D>0\), we have
as well as
with probability \(1-O(N^{-D})\).
The negative shift \(-d/N\) in Theorem 1.1 is only relevant if we want the optimal error bound \(O(N^{-2/3+\varepsilon })\). As \(\sqrt{d(N-d)/N}\asymp d^{1/2}\) for \(d\leqslant N/2\), Theorem 1.1 implies
with very high probability. In addition, Theorem 1.1 implies that for \(N^{2/3+o(1)} \leqslant d \leqslant N/2\), almost all d-regular graphs on N vertices are Ramanujan. Indeed, by (1.2) we have
with very high probability. As \(N^{2/3+o(1)} \leqslant d \leqslant N/2\), the above is negative with very high probability. The analogue also holds for \(-\lambda _N-2\sqrt{d-1}\). This yields the following result.
Corollary 1.2
Fix \(D,\tau >0\). For d large enough and \(2d \leqslant N \leqslant d^{3/2+\tau }\),
Beyond the law of large numbers, the distributions of the extreme eigenvalues of \(\mathcal {A}\) were conjectured in [38] to satisfy edge universality, i.e. after normalization, their joint distribution is the same as that of the extreme eigenvalues of the Gaussian Orthogonal Ensemble. Edge universality was proved by by Bauerschmidt, Huang, Knowles and Yau [4] for \(\mathcal {A}\) in the intermediate regime \(N^{2/9+o(1)} \leqslant d \ll N^{1/3-o(1)}\). The authors showed that
together with analogue results for other extreme eigenvalues. Recently, Huang and Yau [30] extended (1.4) to \(N^{o(1)}\leqslant d\leqslant N^{1/3-o(1)}\). Our second main result is the edge universality of \(\mathcal {A}\) in the dense regime \(N^{2/3+o(1)}\leqslant d \leqslant N/2\).
Theorem 1.3
Fix \(\tau >0\) and assume \(N^{2/3+\tau }\leqslant d\leqslant N/2\). Let \(\mu _1\geqslant \cdots \geqslant \mu _N\) denote the eigenvalues of a Gaussian Orthogonal Ensemble. Fix \(k \in \mathbb N_+\). We have
uniformly for all \(s_1,r_1,\ldots ,s_k,r_k \in \mathbb R\).
To prove the main results, we analysis the Stieltjes transform of \(\mathcal {A}\) near the spectral edge, on all mesoscopic spectral scales. This Green function method is widely used in the random matrix community. To start of, it was applied to Wigner matrices, in particular in [9, 16,17,18,19,20, 40, 41]. It was then applied in [10, 14, 15, 23, 24, 26, 27, 32, 33] to sparse matrices, which includes the adjacency matrix of sparse Erdős-Rényi graphs \(\mathcal G(N,p)\) for \(p \gg N^{-1}\). These works rely on the fact that the matrix entries are independent (subject to the symmetry constraint), which is not the case for \(\mathcal {A}\). In the work [6], the authors developed a technique through local switching, which opens the door of studying random regular graphs through the Green function method. For \(N^{o(1)} \leqslant d \leqslant N^{2/3-o(1)}\), they proved that the eigenvalues of \(\mathcal {A}\) satisfy the local semicircle law. The idea of switching was then applied to prove various results for \(\mathcal {A}\) in the regime \(N^{o(1)}\leqslant d \leqslant N^{2/3-o(1)}\) [3, 4], and d fixed [5, 29]. All these works require the degree upper bound \(d \ll N^{2/3}\), which is essentially due to the approximation \(1-\mathcal {A}_{ij} \approx 1\). In other words, due to the sparsity of the graph in the regime \(d \ll N^{2/3}\), in many situations, one can take two vertices of the graph, and with an affordable error assume that they are disconnected.
In order to deal with the dense case \(N^{2/3+o(1)}\leqslant d \leqslant N/2\), we develop an algorithm which is insensitive to the increasing density of the graph. Comparing to [4, 6], the integration by parts formula used in this paper (see Lemma 2.2) comes with an error term that does not explicitly depend on d. Another ingredient of the proof is a large deviation result on the powers of \(\mathcal {A}\) (see Proposition 3.1), which essentially counts the number of short cycles of the graph. This enables us to replace the entries of \(\mathcal {A}^r\) (\(r\geqslant 2\)) by their expectations, with affordable errors.
Our first step is to prove a weak local semicircle law for all \(N^{o(1)} \leqslant d \leqslant N/2\), which is stated in terms of Green functions (see Theorem 4.2). A standard consequence of Theorem 4.2 is the following complete eigenvector delocalization.
Corollary 1.4
Fix \(\tau >0\) and assume \(N^{\tau }\leqslant d \leqslant N/2\). Let \({{\textbf {u}}}_i\in {\mathbb {S}}^{N-1}\) denote the i-th eigenvector of \(\mathcal {A}\). For any fixed \(\varepsilon ,D>0\), we have
with probability \(1-O(N^{-D})\).
After obtaining the weak local law, we perform a refined analysis of the averaged self-consistent equations near the spectral edge (see Proposition 5.1). This leads to a strong estimate on the traces of the Green functions in the regime \(N^{2/3+o(1)}\leqslant d \leqslant N/2\) (see Proposition 6.1), and from which Theorem 1.1 follows. Providing optimal edge rigidity, the edge universality Theorem 1.3 is proved basing on the usual three-step approach of random matrix theory [13]. The same strategy was also used in [4].
From Theorems 1.1 and 1.3, we see a shift of \(-d/N\) on both spectral edges of \(\mathcal A\). This is due to the fact that the diagonal entries of the adjacency matrix are 0. More precisely, observe that
is the adjacency matrix of a random \((N-1-d)\)-regular graph on N vertices, and we denote its eigenvalues by \(N-1-d=\widehat{\lambda }_1\geqslant \cdots \geqslant \widehat{\lambda }_N\). Thus for \( 2\leqslant k \leqslant N\), we have the relation
Our main results suggest that the shift \(-1\) is shared between \(\lambda \) and \(\widehat{\lambda }\), with the amount proportional to the graph degree. The shift is essential to getting the Tracy–Widom limit, as
for \( N^{2/3}\ll d \leqslant N/2\).
Comparing the parameters of (1.4) and Theorem 1.3, together with the degree symmetry \(d \longleftrightarrow N-d-1\) for \(d-\)regular graphs, one could propose that edge universality holds for all non-trivial random d-regular graphs, in the following scaling.
Conjecture 1.5
Assume \(3 \leqslant d \leqslant N-4\). There exists a constant \(c_{N,d}\)Footnote 1 such that
where \(\textrm{TW}_1\) is the Tracy–Widom distribution for GOE. Analogues results also hold for other non-trivial extreme eigenvalues.
Although the proof of Conjecture 1.5 in the regime when d is fixed, is apparently difficult, it is probable that combining the techniques of [4, 30] and the current paper, one can prove optimal edge rigidity and universality for \(N^{o(1)}\leqslant d \leqslant N/2\). Providing this is the case, the following will also stand.
Conjecture 1.6
For d large enough and \(N \geqslant 2d\), (1.3) holds if and only if \(N \ll d^3\).
The rest of this paper is organized as follows. In Sect. 2 we recall the local switching, and prove an integration by parts formula which is insensitive to the degree d. In Sect. 3 we prove a large deviation result on the powers of \(\mathcal {A}\). In Sect. 4 we prove the weak local semicircle law for all \( N^{o(1)}\leqslant d \leqslant N/2\). In Sect. 5 we prove a strong self-consistent equation near the spectral edge. Finally in Sect. 6 we use the results in Sects. 4 and 5 to conclude the proof of our main results.
1.1 Conventions
Unless stated otherwise, all quantities depend on the fundamental large parameter N, and we omit this dependence from our notation. We use the usual big O notation \(O(\cdot )\), and if the implicit constant depends on a parameter \(\alpha \) we indicate it by writing \(O_\alpha (\cdot )\). Let
be two families of nonnegative random variables, where \(U^{(N)}\) is a possibly N-dependent parameter set, and \(Y\geqslant 0\). We say that X is stochastically dominated by Y, uniformly in u, if for any fixed \(\varepsilon ,D>0\),
We write \(X\asymp Y\) if \(X =O(Y)\) and \(Y=O(X)\). If X is stochastically dominated by Y, we use the notation \(X \prec Y\), or equivalently \(X=O_{\prec }(Y)\). We say an event \(\Omega \) holds with very high probability if for any \(D>0\), \(1-\mathbb P(\Omega )=O_D(N^{-D})\).
2 Local Switchings
As in [4, 6], we rely on switchings for regular graphs and the invariance under the permutation of vertices. For indices i, j, k, l, we define the signed adjacency matrices
In addition, we denote the indicator function that the edges ij and kl are switchable by
The following identity is a consequence of the uniform probability measure on \(\mathcal A\). The proof is given in [4, Proposition 3.1].
Lemma 2.1
Let i, j, k, l be distinct indices. Let F be a function which depends on the random graph \(\mathcal A\), and possibly on the indices i, j, k, l. We have
where \(\xi \) and \(\chi \) are defined in (2.1) and (2.2) respectively.
Let us abbreviate
The next result improves [4, Corollary 3.2] to adapt the dense graph setting. This is the main formula we use in generating non-trivial self-consistent equations.
Lemma 2.2
Let i, j be distinct indices. Let F be a function which depends on the random graph \(\mathcal A\), and possibly on the indices i, j. We have
We often refer the last term above as the remainder term.
Proof
Since \(\sum _{k} \mathcal A_{ik}=\sum _{l}\mathcal A_{kl}=d\), we have
where in the second step we used \(1=(1-\mathcal A_{jl})+\mathcal A_{jl}\). By Lemma 2.1 and \(\chi _{ij}^{kl}(\mathcal {A})\leqslant \mathcal {A}_{ij}\mathcal {A}_{kl}\),
Moreover, note that
where in the second and third steps we used \(\sum _{kl}(1-\mathcal {A}_{kl})\mathcal {A}_{jl}=\sum _{kl}(1-\mathcal {A}_{ik})\mathcal {A}_{jl}=(N-d)d\). Combining (2.4) - (2.6) we get
Applying \(\sum _{kl}(1-\mathcal A_{ik})\mathcal A_{kl}\mathcal A_{jl}=d^2-(\mathcal {A}^3)_{ij}\) to the second term on the RHS, we get the desired result. \(\square \)
3 Powers of \(\mathcal {A}\): Large Deviations
Let us abbreviate the discrete derivative for any indices i, j, k, l by
where \(\xi _{ij}^{kl}\) was defined as in (2.1). It satisfies the discrete product rule
and
We have the following result.
Proposition 3.1
Fix \(\tau >0\) and assume \(N^{\tau } \leqslant d \leqslant N/2\). We have
uniformly for \(i \ne j\), and
uniformly in i, j. For fixed integer \(r\geqslant 4\), we have
uniformly in i, j.
Proof
(i) Fixed an integer \(r \geqslant 2\). In this step we shall prove
uniformly in i. By \(\sum _{j}(\mathcal {A}^r)_{ij}=d^r\), we have
thus \(\mathcal R_r{:}{=}(\mathcal {A}^{2r})_{ii}-d^{2r}N^{-1}\geqslant 0\). Similarly, \(\mathcal R_{r+1}{:}{=}(\mathcal {A}^{2r+2})_{ii}-d^{2r+2}N^{-1}\geqslant 0\). Fix \(n \geqslant 1\). As \(A_{ii}=0\), we have
Applying Lemma 2.2 to the last term on RHS of (3.8), with \(F(\mathcal {A})=(\mathcal {A}^{2r-1})_{ji}\mathcal R_r^{n-1}\), we get
As \(\max _{ij}(\mathcal A^{r})_{ij}\leqslant \max _i \sum _k (\mathcal A^{r-1})_{ik}=d^{r-1}\) for all \(r \geqslant 2\), we can easily remove the restraint \(j\ne i\) in the third and fourth term on RHS of the above, by observing that
As a result,
where in the second step we used
and \(\mathcal R_r,\mathcal R_{r+1} \geqslant 0\), and in the third step we have a cancellation among the three terms involving \(\mathbb E \mathcal R_{r}^{n-1}\). To estimate the RHS of (3.9), note that
and together with the product rule (3.2) and \((N-d)^{-1}\leqslant 2N^{-1}\), the term \(R_1\) can be bounded (up to a constant factor) by
Note that
which implies
More over, by (3.2) and (3.10), it is easy to check that
Hence we have
Combining (3.9), (3.11) and (3.13), we get
which implies (3.6) as desired.
(ii) Fix an integer \(r\geqslant 4\). In this step we shall show that
uniformly in i, j. More precisely, by \(\sum _k (\mathcal {A}^2)_{ik}=d^2\) and \(\sum _k (\mathcal {A}^{r-2})_{kj}=d^{s-2}\) we get
and (3.14) follows from (3.6).
(iii) In this step we prove (3.3); the proof of (3.4) follows in a similar fashion. Let us denote \(\mathcal S{:}{=}(\mathcal {A}^2)_{ij}-d^2N^{-1}\) for some \(i \ne j\). Fix \(n \geqslant 1\). Using Lemma 2.2 with \(F(\mathcal A)=\mathcal {A}_{kj}\mathcal S^{2n-1}\), we have
Similar as in (3.9) and (3.12), we can remove the restriction \(k\ne i\) and estimate the error term in the above, and get
The second term on RHS of (3.15) can be bounded (up to a constant factor) by
Since \(i \ne j\), we have \(|\textrm{D}_{ik}^{lu}(\mathcal {A}_{kj})|=O( \delta _{uj}+\delta _{lj}+\delta _{lk}+\delta _{kj}\)). Together with the trivial bound \(\textrm{D}_{ik}^{ku}\mathcal S =O(1)\), we can get the estimate
Using (3.14) with \(r=4\), we get
Combining (3.15)–(3.17) we get
which implies the desired result.
(iv) The proof of (3.5) follows from the relation
and (3.3), (3.4), as well as the trivial bounds \(\max _{xy}(\mathcal {A}^2)_{xy}\leqslant d\), \(\max _{xy}(\mathcal {A}^{r-2})_{xy}\leqslant d^{r-3}\). \(\square \)
4 Green Function and Local Semicircle Law
For the rest of this paper, we shall use the parameter
Note that \(q\asymp \sqrt{d}\) for \(d \leqslant N/2\). Let us define the projection \(P_{\bot }{:}{=}I-{{\textbf {e}}} {{\textbf {e}}}^*\), where \({{\textbf {e}}}=N^{-1/2}(1,\ldots ,1)^*\). For \(z \in \mathbb C\) with \({{\,\textrm{Im}\,}}z>0\), we define the Green function by
The projection \(P_\bot \) was introduced in [4] to eliminate the large, though trivial impact of \(\lambda _1\) in the computations. As a result, the eigenvalues of G are \((q^{-1}\lambda _2-z)^{-1}\),\((q^{-1}\lambda _3-z)^{-1}\),...,\((q^{-1}\lambda _N-z)^{-1}\) and 0. It is easy to check that
For \(M \in \mathbb C^{N\times N}\), we denote its normalized trace by \(\underline{M} \!\,{:}{=}N^{-1}{{\,\textrm{Tr}\,}}M\). For \(x \in \mathbb R\) and \(z \in \mathbb C\) with \({{\,\textrm{Im}\,}}z>0\), we denote the semicircle law and its Stieltjes transform by
respectively. The quantity \(m\equiv m(z)\) satisfies \(1+zm+m^2=0\). In addition, we have the Ward identity
In the sequel, it is convenient to use the following continuous derivative for any indices i, j, k, l,
and by Taylor expansion we have
for some \(\theta \in [0,1]\). We have the differential rule
The following lemma will be useful in our estimates.
Lemma 4.1
Fix \(r \in {\mathbb {N}}_+\). Suppose \(z=O(1)\), then
Proof
The result follows by repeatedly applying the second relation of (4.2) r times, and estimating the result using the trivial bound \(\max _{ij}(\mathcal {A}^n)_{ij}=O(1+d^{n-1})\) and (4.1). \(\square \)
Fix \(\delta >0\), and we define the spectral domain
The random graph \(\mathcal {A}\) satisfies the following local semicircle law.
Theorem 4.2
Assume \(N^{\tau } \leqslant d \leqslant N/2\) for some fixed \(\tau >0\). Fix \(\delta \in (0,\tau /10)\). We have
uniformly for \(z \in {{\textbf {D}}}\).
For the rest of this section we prove the next result; Theorem 4.2 then follows through a standard stability analysis argument, see e.g. [25, Section 4].
Proposition 4.3
Assume \(N^{\tau } \leqslant d \leqslant N/2\) for some fixed \(\tau >0\). Fix \(\delta \in (0,\tau /10)\) and \(\nu \in (0,\delta /10)\). Let \(z\in {{\textbf {D}}}\), and suppose that \(\max _{ij}|G_{ij}-\delta _{ij}m|\prec \phi \) for some deterministic \(\phi \in [N^{-1},N^{\nu }]\) at z. Then at z we have
Suppose that
for some deterministic \(\Phi \in [\widetilde{\mathcal E},N^2]\). Fix \(n\in \mathbb N_+\). Fix indices i, j and denote \(P\equiv P_{ij}{:}{=}\delta _{ij}+zG_{ij}+\underline{G} \!\,G_{ij}\). Proposition 4.3 is an easy consequence of
More precisely, since n is an arbitrary fixed integer, we obtain from Markov’s inequality that \(P\prec (\Phi \widetilde{\mathcal E})^{1/2}\). Taking a union bound over indices i, j, we get
provided that (4.8) holds. Iterating the above, we get Proposition 4.3 as desired.
Let us look into the proof of (4.9). By (4.2), we get \(P=q^{-1}(\mathcal {A}G)_{ij}+\underline{G} \!\,G_{ij}+N^{-1}\), and thus
We denote \(\mathcal P{:}{=}(\mathbb E|P|^{2n})^{\frac{1}{2n}}\) and \(\mathcal E{:}{=}(\Phi \widetilde{\mathcal E})^{1/2}\). It suffices to show that
To simplify notation, we shall drop the complex conjugates in (I)+(II) (which play no role in the subsequent analysis), and prove
instead of (4.11). By triangle inequality and the fact that \(|m(z)|=O(1)\), we have
By Lemma 2.2, we have
By the last relation of (4.2), it is easy to see that \(T_2=0\). Applying Lemma 4.1 for \(r=3\), we have \((\mathcal {A}^3\,G)_{ij}\prec (1+\phi )\,d^{3/2}\). Thus
Let us estimate the remainder term \(T_4\). By (3.2), (4.5), (4.6) and (4.13), we see that
which implies
In the squeal, the remainder term from Lemma 2.2 will always be small enough for our purposes, and we shall omit their estimates. Moreover,
and
As a result, (4.14) simplifies to
To examine the terms in \(T_1\), we split according to (3.2)
4.1 Computation of \(T_{1,1}\)
Applying (4.5) with \(\ell =1\), we get
for some \(\theta \in [0,1]\). By (4.6), we get
The term \(T_{1,1,1,1}\) is the leading term in our computation. Recall the definition of \(\chi \) in (2.2). We have
Here in the second step we used (3.4), which implies
and similarly
For the first term on RHS of (4.20), we again apply Lemma 2.2, this time with \(F(\mathcal {A})=G_{kk}G_{ij}P^{2n-1}\), and get
By (4.6) and (4.13) one can check that
By (4.3), we have
and together with \(\sum _{kxy}\chi _{ix}^{ky}(\mathcal {A})\leqslant d^2N\) and \(q\asymp \sqrt{d}\), we get
Applying (3.4), we get
In addition, similar to (4.15), it can be shown that
Combing the above and (4.21)–(4.23), we get
Hence (4.1), (4.20) and (4.24) implies
Other terms on RHS of (4.19) are error terms, and let us estimate them one by one. By \(\chi _{il}^{kx}(\mathcal {A}) \leqslant \mathcal {A}_{il}\mathcal {A}_{kx}\), we have
where in the last step we used (4.3) and Jensen’s inequality. In addition,
Similarly, we can show that \(|T_{1,1,1,5}|+|T_{1,1,1,7}|\prec \mathcal E \mathcal P^{2n-1}\). Next, we have
where in the third step we used Lemma 4.1. Similarly, we can show that \(|T_{1,1,1,6}|+|T_{1,1,1,8}|\prec \mathcal E \mathcal P^{2n-1}\). As a result,
By resolvent identity and (4.13), it is easy to see that \(((\partial _{ik}^{lx})^2G_{kj}(\mathcal A+\theta \xi _{ik}^{lx})) \prec (1+\phi )^3\), and thus
where in the second step we used \(q\asymp \sqrt{d}\). Combining the above with (4.18), (4.19), (4.25) and (4.26), we finish the computation of \(T_{1,1}\) by getting
4.2 Estimate of \(T_{1,2}\)
Case 1. Let us first illustrate the steps on the dense regime \(d \asymp N\). In this case, \(q\asymp \sqrt{d}\asymp \sqrt{N}\). Trivially, we have \(\textrm{D}_{ik}^{lx}P \prec \mathcal E\). By (4.3), (4.6) and (4.13), we have
for \(s \geqslant 2\). Together with (3.2) and (4.5), it is not hard to see that
Together with the trivial bound \(\chi _{il}^{kx}(\mathcal {A})\leqslant 1\) and (4.3), we conclude that
Case 2. Now let us examine the general case. The growing complexity is largely due to the fact that we are including the sparse regime \(d \ll N\), and as a result we cannot estimate the entries of \(\mathcal {A}\) by 1: they have to be used in the summations. By (4.2), we can rewrite P by \(P=q^{-1}(\mathcal {A}G)_{ij}+\underline{G} \!\,G_{ij}+N^{-1}\). Using (3.2), (4.3), (4.5), (4.6) and (4.13), we get
Let us denote \(P_*{:}{=}\max _{ij}|\delta _{ij}+z\underline{G} \!\,_{ij}+\underline{G} \!\,G_{ij}|=\max _{ij}|q^{-1}(\mathcal {A}G)_{ij}+\underline{G} \!\,G_{ij}+N^{-1}|\). By (4.6) and (4.13), it is not hard to see that
where in the last step we also used our assumption (4.8). The above shows that heuristically, \(\textrm{D}_{ik}^{lx}\) on P generates some self-similar terms. Hence
Let us define \(X{:}{=}(2n-1)P^{2n-2}+(2n-2)P \textrm{D}_{ik}^{jl}(P^{2n-3})+(2n-3)P^2 \textrm{D}_{ik}^{jl}(P^{2n-4})+\cdots + 2P^{2n-3} \textrm{D}_{ik}^{jl}(P)\). Note that the trivial estimate \(\textrm{D}_{ik}^{lx}P \prec \mathcal E\) implies
By (4.1), (4.3) and (4.13), it is easy to see that
Inserting (4.29)–(4.31) into (4.17), we get
and combing the above with (4.32) yields
If we look at the term \(T_{1,2,1}\), it contains the factor \(\mathcal {A}_{il}G_{lj}\) so we cannot use the smallness of \(\sum _l \mathcal {A}_{il}\) and Ward identity at the same time. We (unfortunately) have to apply Lemma 2.2 again. Let us abbreviate \(F(\mathcal {A})=(1-\mathcal {A}_{ik})\mathcal {A}_{kx}(1-\mathcal {A}_{lx})G_{kj}G_{lj}X\). Lemma 2.2 implies
Note that the above estimate works because of the absence of \(\mathcal {A}_{il}\). Similarly, we can use (4.5) and resolvent identity to show that
With the help of (3.4), (4.3) and (4.13), we have
Combining (4.33)–(4.37) we get
4.3 Estimate of \(T_{1,3}\)
The estimates of \(T_{1,3}\) are very similar to those of \(T_{1,2}\). In \(T_{1,3}\), the factor \(G_{kj}\) is replaced by \(\textrm{D}_{ik}^{lx}G_{kj}\), which means we cannot use the Ward identity over summation index k. However, we are compensate by the fact that \(\textrm{D}_{ik}^{lx}G_{kj}\) generates at least one factor of \(q^{-1}\), which is equivalently good in our estimates. Thus by steps that are very similar to how we estimated \(T_{1,2}\), it can be shown that
Combining (4.16), (4.17), (4.27), (4.38) and (4.39) yields
and thus we have (4.12) as desired. This finishes the proof of Proposition 4.3.
5 Strong Self-Consistent Equation Near the Edge
To get a more precise description of the spectrum, let us define the shifted Stieltjes transform
We have
uniformly for \(z \in {{\textbf {D}}}\). Let us write \(z=E+\textrm{i}\eta \) and \(\kappa {:}{=}|(E+\frac{d}{Nq})^2-4|\). It is easy to see that
Having the weak local law at hand, we can relate the entrywise law to the average law in the following sense. A standard consequence of Theorem 4.2 is the eigenvector delocalization Corollary 1.4, which together with (4.3) implies
Comparing (5.2) with (4.3), we see that the improved Ward identity (5.2) contains the term \(|\underline{G} \!\,-\widehat{m}|\) instead of \(|G_{ii}-m|\), and \(|\underline{G} \!\,-\widehat{m}|\) is expected to fluctuate on a smaller scale. In addition, by Theorem 4.2, triangle inequality and the fact that \(m(z)=O(1)\), we have
for all \(z \in {{\textbf {D}}}\). Using (5.2) and (5.3), instead of (4.3) and (4.13), we can redo the proof of Proposition 4.3 and show that
and thus
The above and (5.1) imply
In this section we shall prove the following result.
Proposition 5.1
Assume \(N^{\tau } \leqslant d \leqslant N/2\) for some fixed \(\tau >0\). Fix \(\delta \in (0,\tau /10)\). Let \(z\in {{\textbf {D}}}\), and suppose that \(|\underline{G} \!\,-\widehat{m}|\prec \psi \) and \(\max _{ij}|G_{ij}-\delta _{ij}\widehat{m}|\prec \psi +\sqrt{\mathcal E_1}\) for some deterministic \(\psi \in [N^{-1},1]\) at z, where
Then at z we have
Fix \(n \geqslant 1\). Let us denote \(Q {:}{=}1+(z+d/(Nq))\underline{G} \!\,+\underline{G} \!\,^2\). By (4.2), \(Q=q^{-1}\underline{\mathcal {A}G} \!\,+d/(Nq) \cdot \underline{G} \!\,+\underline{G} \!\,^2+N^{-1}\) we have
We denote \(\mathcal Q{:}{=}(\mathbb E|Q|^{2n})^{\frac{1}{2n}}\), it suffices to show that
To simplify notation, we shall drop the complex conjugates in (III)+(IV) (which play no role in the subsequent analysis), and prove
instead of (5.5). By Lemma 2.2, we have
By the last relation of (4.2), it is easy to see that \(S_2=0\). Using Lemma 4.1 with \(r=3\), we have \(\sum _{ij}(\mathcal {A}^3)_{ij}G_{ij}={{\,\textrm{Tr}\,}}(\mathcal {A}^3G)\prec Nd^{3/2}\). Thus
Using resolvent identity and (5.3), it can be easily shown that \(S_4 \prec \sum _{r=1}^{2n} \widehat{\mathcal E}^{r}\mathcal Q^{2n-r}\). In addition, we have \( S_5\prec \sum _{r=1}^{2n} \widehat{\mathcal E}^{r}\mathcal Q^{2n-r}, \) and
where in the second step we used (3.3). Thus \(S_6+S_7=-d/(Nq)\mathbb E\underline{G} \!\,Q^{2n-1}\). As a result, (5.7) simplifies to
To examine the terms in \(S_1\), we split
5.1 Estimates of \(S_{1,2}\) and \(S_{1,3}\)
Let us first look at the interaction terms. As we shall see, the steps are much easier compared to those in Sect. 4.2, due to the smallness of \(\textrm{D}_{ij}^{kl}Q\). By (4.6) and (5.2), we have
and \(q^{-s}(\partial _{ij}^{kl})^sQ \prec q^{-s}\mathcal E_2\) for \(s \geqslant 2\). Together with (3.2), (4.5) and \(\textrm{D}_{ij}^{kl}Q \prec \widehat{\mathcal E}\) we get
By (5.10) and \(\chi _{ik}^{jl}(\mathcal {A})\leqslant \mathcal {A}_{ik}\mathcal {A}_{jl}\), we get
Here in the last step we used (5.2) and Jensen’s inequality. Similarly, by (5.10), \(\chi _{ik}^{jl}(\mathcal {A})\leqslant \mathcal {A}_{ik}\mathcal {A}_{jl}\) and \(\textrm{D}_{ij}^{kl}G_{ij}\prec q^{-1}\), we have
5.2 Computation of \(S_{1,1}\)
The computation of \(S_{1,1}\) is similar to that of \(T_{1,1}\) in Sect. 4.1. Applying (4.5) with \(\ell =2\), we get
for some \(\theta \in [0,1]\).
Let us first compute \(S_{1,1,1}\). By (4.6), we get
Recall the definition of \(\chi \) in (2.2). We have
Similar as in (4.20), using (3.4), we get
Here in the last step we used \(\sum _i(G_{ii}-\underline{G} \!\,)=0\). Let us denote \(\widetilde{F}(\mathcal {A}){:}{=}(G_{ii}-\underline{G} \!\,)(G_{jj}-\underline{G} \!\,)Q^{2n-1}\). Applying Lemma 2.2 to the first term on RHS of (5.15), we get
where in the second step we used \(\sum _{ij}\widetilde{F}(\mathcal {A})=0\). By (3.2), (4.5), (4.6), and \(\textrm{D}_{ij}^{kl}Q \prec q^{-1}\widehat{\mathcal E}\), we have
which implies
In addition, (3.4) and \(\sum _{ij}\widetilde{F}(\mathcal {A})=0\) imply
Combining (5.16)–(5.18) we get
Similarly to (5.15), we can show that
By first summing over j and then summing over i, the first term on RHS of the above vanishes, and thus
Similarly,
Moreover, applying (3.5) with \(r=4\), we have
Inserting (5.19)–(5.22) into (5.14), we get
When \(s=2,\ldots ,8\), the estimates of \(S_{1,1,1,s}\) are relatively simple. By \(\chi _{ik}^{jl}\leqslant \mathcal {A}_{ik}\mathcal {A}_{jl}\) and first summing over indices k, l, it is not hard to see that \(S_{1,1,1,2}\prec \widehat{\mathcal E}\mathcal Q^{2n-1}\). For the next term, we have
where in the second step we used Lemma 4.1 with \(r=1\). The first term on RHS of the above can be bounded by
Hence \(S_{1,1,1,3}\prec \widehat{\mathcal E}\mathcal Q^{2n-1}\). Similarly \(S_{1,1,1,4}\prec \widehat{\mathcal E}\mathcal Q^{2n-1}\). We have
By (5.2), the first term on RHS of above can be bounded by
the second term on RHS can be estimated by
Here in the first step we used \(\sum _{k}G_{kj}=0\) and Lemma 4.1, in the second step we used \(\sum _{k}G_{kj}=0\), and in the last step we used
which is a consequence of (3.5). Thus \(S_{1,1,1,5}\prec \widehat{\mathcal E}\mathcal Q^{2n-1}\), and similarly we have \(S_{1,1,1,8}\prec \widehat{\mathcal E}\mathcal Q^{2n-1}\). Next, we have
where in the second step we used \(\sum _j G_{ij}=0\), and in the third step we used Lemma 4.1. Similarly, we also have \(S_{1,1,1,7}\prec \widehat{\mathcal E}\mathcal Q^{2n-1}\).
Now we have finishes estimates of \(S_{1,1,1,s}\) for all \(s =2,\ldots ,8\). Together with (5.13) and (5.23) we get
The estimate of \(S_{1,1,2}\) is very similar to those of \(S_{1,1,1,2},\ldots ,S_{1,1,1,8}\): by (4.6), there is at least one off-diagonal factor of G in every term of \(S_{1,1,2}\). In addition, compared to \(S_{1,1,1,2},\ldots ,S_{1,1,1,8}\), there is an extra factor of \(q^{-1}\prec \widehat{\mathcal E}^{1/2}\) in \(S_{1,1,2}\). Thus we can show that
By resolvent identity, (4.6) and \(\max _{ij}|G_{ij}| \prec 1\), it is not hard to see that \((\partial _{ij}^{kl})^3G_{kj}(\mathcal A+\theta \xi _{ik}^{lx})\prec 1\), hence
Combining (5.24)–(5.26) we have
Inserting (5.9), (5.11), (5.12) and (5.27) into (5.8), we get
Since \(\hbox {(IV)'}{:}{=}\mathbb E (d/(Nq)\cdot \underline{G} \!\,+ \underline{G} \!\,^2)Q^{2n-1}\), we have finished the proof of (5.6). This concludes the proof of Proposition 5.1.
6 Edge Rigidity and Universality
Throughout this section we assume
for some fixed \(\tau >0\), and fix parameters
We abbreviate
We shall prove Theorems 1.1 and 1.3 at the right edge of the spectrum; the left edge case follows analogously.
6.1 Improved estimate of averaged Green function
Recall the notion of \({{\textbf {D}}}\) in (4.7). Let us define the regime
and we use \(\kappa \equiv \kappa (E){:}{=}|(E+d/(Nq))^2-4|\) to denote the distance to edge. We first prove the following consequence of Theorem 4.2 and Proposition 5.1.
Proposition 6.1
We have
for \(z \in {{\textbf {S}}}\), and
for all \(z \in {{\textbf {D}}}\). In addition, we have
for all \(z \in {{\textbf {D}}}\).
Proof
Since for each fixed E, the function \(\eta \mapsto \widehat{\mathcal E}(E+\textrm{i}\eta )\) is non-increasing for \(\eta >0\), a standard stability analysis (see e.g. [7, Lemma 5.4]) and Proposition 5.1 imply
for all \(z \in {{\textbf {D}}}\).
-
(i)
Let \(z \in {{\textbf {S}}}\). Recall the definition of \(\widehat{\mathcal E}\) in Proposition 5.1. Note that
$$\begin{aligned} \kappa \asymp E+d/(Nq)-2, \quad {{\,\textrm{Im}\,}}\widehat{m}\asymp \frac{\eta }{(\kappa +\eta )^{1/2}}\quad \hbox {and} \quad |z+d/(Nq)+2\widehat{m}|\asymp (\kappa +\eta )^{1/2}, \end{aligned}$$together with Young’s inequality we get
$$\begin{aligned} \widehat{\mathcal E}&\prec \mathcal E_1+\mathcal E_2^{2/3}(\psi +|z+d/(Nq) +2\widehat{m}|)^{2/3}+d^{-1/2}\psi \nonumber \\&\prec \frac{\psi }{N\eta }+\frac{1}{N(\kappa +\eta )^{1/2}}+\frac{1}{d} +\Big (\frac{\psi }{N\eta }+\frac{1}{N(\kappa +\eta )^{1/2}}\Big )^ {2/3}\nonumber \\&\quad \times (\psi +(\kappa +\eta )^{1/2})^{2/3}+\frac{\psi }{d^{1/2}} \nonumber \\&\prec \frac{\psi }{N\eta }+\frac{1}{N(\kappa +\eta )^{1/2}}+\frac{1}{d}+\frac{\psi ^{4/3}}{(N\eta )^{2/3}}+\frac{\psi ^{2/3}}{N^{2/3} (\kappa +\eta )^{1/3}}\nonumber \\&\quad +\frac{\psi ^{2/3}(\kappa +\eta )^{1/3}}{(N\eta )^{2/3}} +\frac{1}{N^{2/3}}+\frac{\psi }{d^{1/2}}\,. \end{aligned}$$(6.7)By (6.6) and the fact that \(x \mapsto x/\sqrt{x+\kappa +\eta }\) is increasing, we know that
$$\begin{aligned} |\underline{G} \!\,-\widehat{m} |&\prec \ \frac{\psi }{N\eta (\kappa +\eta )^{1/2}}+\frac{1}{N(\kappa +\eta )} +\frac{1}{d(\kappa +\eta )^{1/2}}\nonumber \\&\quad +\frac{\psi }{(N\eta )^{1/2}(\kappa +\eta )^{1/4}}+\frac{\psi ^{2/3}}{N^{2/3}(\kappa +\eta )^{5/6}} +\frac{\psi ^{2/3}}{(N\eta )^{2/3}(\kappa +\eta )^{1/6}}\nonumber \\&\quad +\frac{1}{N^{2/3}(\kappa +\eta )^{1/2}} +\frac{\psi }{d^{1/2}(\kappa +\eta )^{1/2}} \nonumber \\&\prec \ \frac{1}{N(\kappa +\eta )}+\frac{1}{d(\kappa +\eta )^{1/2}}+\frac{1}{N^2(\kappa +\eta )^{5/2}}\nonumber \\&\quad +\frac{1}{(N\eta )^2(\kappa +\eta )^{1/2}}+\frac{1}{N^{2/3}(\kappa +\eta )^{1/2}}+N^{-\nu }\psi \end{aligned}$$(6.8)provided that \(|\underline{G} \!\,-\widehat{m}|\prec \psi \). Here in the first step the fourth term is obtained through
$$\begin{aligned}{} & {} \frac{\psi ^{4/3}}{(N\eta )^{2/3}} \cdot (\widehat{\mathcal E}+\kappa +\eta )^{-1/2}\leqslant \frac{\psi ^{4/3}}{(N\eta )^{2/3}} \cdot \\{} & {} \bigg (\frac{\psi ^{4/3}}{(N\eta )^{2/3}}\bigg )^{-1/4} \cdot (\kappa +\eta )^{-1/4}=\frac{\psi }{(N\eta )^{1/2}(\kappa +\eta )^{1/4}}, \end{aligned}$$and in last step we used \(\kappa +\eta \geqslant N^{-2/3+\delta }\), \(\eta \geqslant N^{-2/3}\) and \(d \geqslant N^{2/3+\tau }\). Iterating (6.8), we obtain (6.3).
-
(ii)
Let \(z \in {{\textbf {D}}}\). We have
$$\begin{aligned} {{\,\textrm{Im}\,}}\widehat{m} =O(\sqrt{\kappa +\eta })\quad \hbox {and} \quad \quad |z+d/(Nq)+2\widehat{m}| \asymp (\kappa +\eta )^{1/2}. \end{aligned}$$Similar to (6.7), we get
$$\begin{aligned} \begin{aligned} \widehat{\mathcal E}&\prec \frac{\psi }{N\eta }+\frac{(\kappa +\eta )^{1/2}}{N\eta }+\frac{1}{d}+\Big (\frac{\psi }{N\eta }+\frac{(\kappa +\eta )^{1/2}}{N\eta }\Big )^{2/3}(\psi +(\kappa +\eta )^{1/2})^{2/3}+\frac{\psi }{d^{1/2}}\\&\prec \frac{\psi }{N\eta }+\frac{(\kappa +\eta )^{1/2}}{N\eta }+\frac{1}{d}+\frac{\psi ^{4/3}}{(N\eta )^{2/3}}+\frac{(\kappa +\eta )^{2/3}}{(N\eta )^{2/3}}+\frac{\psi }{d^{1/2}}. \end{aligned} \end{aligned}$$By (6.6) and the fact that \(x \mapsto x/\sqrt{x+\kappa +\eta }\) is increasing, we get
$$\begin{aligned} \begin{aligned} |\underline{G} \!\,-\widehat{m}|&\prec \Big (\frac{\psi }{N\eta }\Big )^{1/2}+\frac{1}{N\eta }+\frac{1}{d^{1/2}}+\frac{\psi ^{2/3}}{(N\eta )^{1/3}}+\frac{(\kappa +\eta )^{1/6}}{(N\eta )^{2/3}}+\frac{\psi ^{1/2}}{d^{1/4}} \end{aligned} \end{aligned}$$provided that \(|\underline{G} \!\,-\widehat{m}| \prec \psi \). Iterating the above yields (6.4) as desired.
-
(iii)
The estimate (6.5) is a direct consequence of (5.4) and (6.4).
\(\square \)
6.2 Proof of Theorem 1.1
We shall need the following bound on the magnitude of \(\lambda _2,\lambda _N\) as an input, which follows from [42, Theorem A].
Theorem 6.2
For any fixed \(D>0\), there exists a constant \(L\equiv L(D)>0\) such that
The upper bound. Let \(z=E+\textrm{i}N^{-2/3} \in {{\textbf {S}}}\). By (6.3) and \(\kappa (E) \geqslant N^{-2/3+\delta }\), we get
This implies that whenever \(E\in [2-d/(Nq)+N^{-2/3+\delta },\delta ^{-1}]\), with very high probability, there is no eigenvalue of A in the interval \([E-N^{-2/3},E+N^{-2/3}]\). Together with Theorem 6.2, we get
The lower bound. Let \(\widehat{{{\textbf {S}}}}{:}{=}\{z=E-d/(Nq)+\textrm{i}\eta :2- N^{-2/3+\delta }\leqslant E\leqslant 2+N^{-2/3+\delta }, N^{-2/3-\delta /3} \leqslant \eta \leqslant N^{-2/3} \}\subset {{\textbf {D}}}\), one can easily deduce from (6.1) and (6.4) that
for all \(z \in \widehat{{{\textbf {S}}}}\). Thus
Let \(f: \mathbb R \rightarrow [0,1]\) be a smooth function such that \(f(x)=1\) for \(|x+d/(Nq)-2|\leqslant N^{-2/3+\delta }-N^{-2/3}\), \(f(x)=0\) for \(|x+d/(Nq)-2|\geqslant N^{-2/3+\delta }\) and \(\Vert f^{(j)}\Vert _{\infty }=O(N^{2j/3})\) for all fixed \(j\in \mathbb N_+\). We see that
where in the last step we used (6.11). Now we compute \(N^{-1}{{\,\textrm{Tr}\,}}f(A)\). Set \(l {:}{=}\lceil {3\delta ^{-1}} \rceil \), and let \(\tilde{f}\) be the almost analytic extension of f, defined by
We define the regime \(D {:}{=}\{w=x+\textrm{i}y: x \in \mathbb R, |y|\leqslant N^{-2/3-\delta /3}\}\). Note that \(\lambda _1/q=d/q \notin {{\,\textrm{supp}\,}}f\). By [22, Lemma 3.5], we have
By the trivial bound \(|\underline{G} \!\,(w)| \leqslant |y|^{-1}\), we see that
By (6.10) and \(\Vert f\Vert _1=O(N^{2/3+\delta })\), we have
As a result, we get
Combining (6.12) and (6.13) yields
and thus \((2-d/(Nq)-\lambda _k/q)_+ \prec N^{-2/3+\delta }\) for any fixed k. Together with (6.9) we finished the proof of Theorem 1.1 on the right side of the spectrum.
Remark 6.3
In Theorem 1.1 we restrict ourselves on the regime \(N^{2/3+\tau }\leqslant d \leqslant N/2\), where we have the optimal rigidity estimate. It can be deduced from Theorem 4.2 and Proposition 5.1 that for all \(N^{\tau }\leqslant d \leqslant N/2\), we have
with very high probability. We do not pursuit it here.
6.3 Proof of Theorem 1.3
Let us define the spectral domain.
The next result follows from Theorem 1.1 and Proposition 6.1.
Corollary 6.4
For all \(z \in \widetilde{{{\textbf {D}}}}\), we have
and
In addition, we have
and
for all \(z=E+\textrm{i}\eta \) satisfying \(1\leqslant E \leqslant 4\) and \(N^{-2/3+\delta }\leqslant \eta \leqslant 1\).
With the help of Corollary 6.4, one can now obtain Theorem 1.3 (at the right spectral edge) using a strategy very similar to that of [4, Section 9].
More precisely, by [1, 31] and Corollary 6.4, one immediately gets that, near the right edge of the spectrum, a Dyson Brownian motion starting at A reaches local equilibrium at time \(t_*\gg N^{-1/3}\). Theorem 1.3 then follows by comparing the edge statistics of the Dyson Brownian motion at times 0 and \(t_*\). The main difference in the comparison argument is that one needs to use Lemma 2.2 instead of [4, Corollary 3.2]. We shall sketch the steps, with emphasis on this difference.
Let us adopt the conventions in [4], i.e. we consider the constrained GOE W satisfying
We have the integration by parts formula
The matrix-valued process is defined by
and we denote its eigenvalues by \(\xi _1(t)\geqslant \cdots \geqslant \xi _N(t)\). We define the parameter \(s{:}{=}1-\textrm{e}^{-t}\). The Green function is defined by \(G(t)\equiv G(t;z){:}{=}P_\bot (A(t)-z)^{-1}P_\bot \). Recall that we use \(\varrho (x)\) to denote the semicircle distribution on \([-2,2]\). As A and W have asymptotic eigenvalue densities \(\varrho (x+d/(Nq))\) and \(\varrho (x)\) respectively, A(t) has asymptotic eigenvalue density
and we define its Stieltjes transform by
As in [4, Sectiom 9.2], the next result follows from Corollary 6.4 and [1, 10, 31].
Lemma 6.5
-
(i)
Let \(0 \leqslant t \ll 1\). We have
$$\begin{aligned} |\xi _2(t)+d/(e^{t/2}Np)-2| \prec N^{-2/3}. \end{aligned}$$ -
(ii)
Let \(0 \leqslant t \ll 1\). Uniformly for any \(z \in \widetilde{{{\textbf {D}}}}\), we have
$$\begin{aligned} \big | \underline{G} \!\,(t;z)-m(t;z) \big |\prec \frac{1}{N\eta }+\frac{1}{d^{1/2}}+\frac{(\kappa +\eta )^{1/6}}{(N\eta )^{2/3}} \end{aligned}$$and
$$\begin{aligned} \max _{ij} |G_{ij}(t;z)-\delta _{ij}m(t;z)|\prec \frac{1}{(N\eta )^{1/2}}+\frac{1}{d^{1/2}}. \end{aligned}$$ -
(iii)
Recall the definition of \(\mu \) from (6.2) and set \(t_*=N^{-1/3+\mu }\). Fix \(s \in {\mathbb {R}}\). We have
$$\begin{aligned} \lim _{N \rightarrow \infty }{\mathbb {P}}_{A(t_*)}\big (N^{2/3}(\xi _2(t_*)+d/(e^{2/t}Nq)\!-\!2)\!\geqslant \! s\big )=\lim _{N \rightarrow \infty }{\mathbb {P}}_{GOE }\big (N^{2/3}(\mu _1\!-\!2)\!\geqslant \! s\big ). \end{aligned}$$
The limiting distribution of \(\lambda _2\) can be obtained through the following estimate.
Lemma 6.6
Let \(t_*=N^{-1/3+\mu }\), \(\eta =N^{-2/3-\mu }\). For \(\kappa \asymp N^{-2/3}\), we define
Let \(L: \mathbb R \rightarrow \mathbb R\) be a fixed smooth test function with bounded derivatives. We have
By Lemma 6.6 and an analogue of (9.33) in [4], we get
for any fixed \(s \in {\mathbb {R}}\). Together with Lemma 6.5 (iii) we conclude the universality of \(\lambda _2\). Analogue results for other non-trivial eigenvalues of \(\mathcal {A}\) can be proved in the same way. We omit the details.
Proof of Lemma 6.6
Let us abbreviate \(G\equiv G(t)\). We have
By Lemma 2.2, the first term on RHS of (6.17) can be computed by
By \(\sum _{i} G_{ij}=0\), we have \(Y_2=0\). By Lemma 6.5 (ii), one can deduce that
for \(\kappa \leqslant x\leqslant N^{-2/3+\mu }\). Since \(y {{\,\textrm{Im}\,}}[\underline{G} \!\,(2+x+\textrm{i}y)]\) is a monotone decreasing function of y, we get
for \(\kappa \leqslant x\leqslant N^{-2/3+\mu }\). From the above and (4.3) we can deduce that
Similar as in Lemma 4.1, we can apply the second relation of (4.2) and show that
where in the last step we used (6.18). This implies \(Y_3 \prec N^{1/3+3\mu }\). Similar to the estimates of \(S_5,S_6,S_7\) in (5.7), we can show that \(Y_5\prec N^{1/3+3\mu }\) and
Next, by (4.5), we get
Let us denote the first term on RHS of the above by \(Y_{1,1}\). Using Lemma 2.2 with \(F(\mathcal {A})=(1-\mathcal {A}_{ij})\mathcal {A}_{jl}(1-\mathcal {A}_{kl})\partial _{ij}^{kl}(L'(X_t)(G^2)_{ij})\), we get
where in the second step we used (3.4), (4.5) and (6.18). By Proposition 3.1, the second term on RHS of the above can be estimated by
Since \(N^{2/3+\tau }\leqslant d\leqslant N/2\), we have
Comparing to (6.19), we see that heuristically, the above replaces the factor \(\mathcal {A}_{ik}\) in \(Y_{1,1}\) by \(dN^{-1}\), with a small error. Repeating (6.20) three times we get
and together with (6.19) yields
Inserting the above results of \(Y_1,\dots ,Y_7\) to (6.17), we get
Together with (6.16) we conclude the proof. \(\square \)
References
Adhikari, A., Huang, J.: Dyson Brownian motion for general \(\beta \) and potential at the edge. Prob. Theor. Relat. Fields 178, 893–950
Alon, N.: Eigenvalues and expanders. Combinatorica 6(2), 83–96 (1986)
Bauerschmidt, R., Huang, J., Knowles, A., Yau, H.-T.: Bulk eigenvalue statistics for random regular graphs. Ann. Prob. 45, 3626–3663 (2017)
Bauerschmidt, R., Huang, J., Knowles, A., Yau, H.T.: Edge rigidity and universality of random regular graphs of intermediate degree. Geom. Funct. Anal. 30, 693–769 (2020)
Bauerschmidt, R., Huang, J., Yau, H.-T.: Local Kesten–Mckay law for random regular graphs. Commun. Math. Phys. 369, 523–636 (2019)
Bauerschmidt, R., Knowles, A., Yau, H.-T.: Local semicircle law for random regular graphs. Commun. Pure Appl. Math. 70, 1898–1960 (2017)
Bloemendal, A., Erdős, L., Knowles, A., Yau, H.-T., Yin, J.: Isotropic local laws for sample covariance and generalized Wigner matrices. Electron. J. Probab. 19, 1–53 (2014)
Bordenave, C.: A new proof of Friedman’s second eigenvalue theorem and its extension to random lifts. Ann. Sci. Éc. Norm. Sup\(\acute{r}\)r 53, 1393–1439 (2020)
Bourgade, P., Erdős, L., Yau, H.-T., Yin, J.: Fixed energy universality for generalized Wigner matrices. Commun. Pure Appl. Math. 69, 1815–1881 (2016)
Bourgade, P., Huang, J., Yau, H.-T.: Eigenvector statistics of sparse random matrices. Electron. J. Prob. 22(64) (2017)
Broder, A.Z., Frieze, A.M., Suen, S., Upfal, E.: Optimal construction of edge-disjoint paths in random graphs. SIAM J. Comput. 28, 541–573 (1998)
Cook, N.A., Goldstein, L., Johnson, T.: Size biased couplings and the spectral gap for random regular graphs. Ann. Prob. 46, 72–125 (2015)
Erdős, L., Yau, H.T.: A dynamical approach to random matrix theory. Courant Lecture Notes in Mathematics 28 (2017)
Erdős, L., Knowles, A., Yau, H.-T., Yin, J.: Spectral statistics of Erdős–Rényi graphs II: Eigenvalue spacing and the extreme eigenvalues. Commun. Math. Phys. 314, 587–640 (2012)
Erdős, L., Knowles, A., Yau, H.-T., Yin, J.: Spectral statistics of Erdős–Rényi graphs I: local semicircle law. Ann. Prob. 41, 2279–2375 (2013)
Erdős, L., Péché, S., Ramirez, J.A., Schlein, B., Yau, H.-T.: Bulk universality for Wigner matrices. Commun. Pure Appl. Math. 63, 895–925 (2010)
Erdős, L., Schlein, B., Yau, H.-T.: Local semicircle law and complete delocalization for Wigner random matrices. Commun. Math. Phys. 287, 641–655 (2009)
Erdős, L., Schlein, B., Yau, H.-T.: Semicircle law on short scales and delocalization of eigenvectors for Wigner random matrices. Ann. Prob. 37, 815–852 (2009)
Erdős, L., Yau, H.-T., Yin, J.: Bulk universality for generalized Wigner matrices. Prob. Theor. Relat. Fields 154, 341–407 (2012)
Erdős, L., Yau, H.-T., Yin, J.: Rigidity of eigenvalues of generalized Wigner matrices. Adv. Math. 229, 1435–1515 (2012)
Friedman, J.: A proof of Alon’s second eigenvalue conjecture and related problems. Mem. Amer. Math. Soc. 195 (2008)
He, Y.: Mesoscopic linear statistics of Wigner matrices of mixed symmetry class. J. Stat. Phys. 175, 932–959 (2019)
He, Y.: Bulk eigenvalue fluctuations of sparse random matrices. Ann. Appl. Probab. 30, 2846–2879 (2020)
He, Y., Knowles, A.: Fluctuations of extreme eigenvalues of sparse Erdős–Rényi graphs. Prob. Theor. Relat. Fields 180, 985–1056 (2021)
He, Y., Knowles, A., Rosenthal, R.: Isotropic self-consistent equations for mean-field random matrices. Prob. Theor. Relat. Fields 171, 203–249 (2018)
Huang, J., Landon, B., Yau, H.-T.: Bulk universality of sparse random matrices. J. Math. Phys. 56 (2015)
Huang, J., Landon, B., Yau, H.-T.: Transition from Tracy–Widom to Gaussian fluctuations of extremal eigenvalues of sparse Erdős–Rényi graphs. Ann. Probab. 48, 916–962 (2020)
Huang, J., McKenzie, T, Yau, H.T.: Optimal eigenvalue rigidity of random regular graphs. Preprint arXiv: 2405.12161
Huang, J., Yau, H.T.: Spectrum of random \(d\)-regular graphs up to the edge. Commun. Pure Appl. Math. 77, 1573–2179 (2023)
Huang, J., Yau. H.T.: Edge universality of random regular graphs of growing degrees. Preprint arXiv: 2305.01428 (2023)
Landon, B., Yau, H.T.: Edge statistics of Dyson Brownian motion. Electron. J. Probab. 175 (2020)
Lee, J.: Higher order fluctuations of extremal eigenvalues of sparse random matrices. Preprint arXiv: 2108.11634
Lee, J.O., Schnelli, K.: Local law and Tracy–Widom limit for sparse random matrices. Prob. Theor. Relat. Fields 171, 543–616 (2018)
Lubotzky, A., Phillips, R., Sarnak, P.: Ramanujan graphs. Combinatorica 8(3), 261–277 (1988)
Marcus, A., Spielman, D.A., Srivastava, N.: Interlacing families I: bipartite Ramanujan graphs of all degrees. Ann. Math. 182, 307–325 (2015)
Marcus, A., Spielman, D.A., Srivastava, N.: Interlacing families II: mixed characteristic polynomials and the Kadison–Singer problem. Ann. Math. 182, 327–350 (2015)
Margulis, G.A.: Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators. Probl. Inf. Transm. 24, 39–46 (1988)
Miller, S.J., Novikoff, T., Sabelli, A.: The distribution of the largest nontrivial eigenvalues in families of random regular graphs. Exp. Math. 17(2), 231–244 (2008)
Sarid, A.: The spectral gap of random regular graphs. Rand. Struct. Algorithm 63, 281–587 (2023)
Tao, T., Vu, V.: Random matrices: Universality of local eigenvalue statistics up to the edge. Commun. Math. Phys. 298, 549–572 (2010)
Tao, T., Vu, V.: Random matrices: Universality of local eigenvalue statistics. Acta Math. 206, 1–78 (2011)
Tikhomirov, K., Youssef, P.: The spectral gap for dense random regular graphs. Ann. Probab. 47, 362–419 (2019)
Vu, V.: Combinatorial problems in random matrix theory. Proc. ICM 4, 257–280 (2014)
Acknowledgements
The author would like to thank Zhigang Bao for helpful comments. The author is supported by NSFC No. 2023YFA1010400, NSFC No. 12322121, Hong Kong RGC Grant No. 21300223 and CityU Start-up Grant No. 7200727.
Funding
Open access publishing enabled by City University of Hong Kong Library’s agreement with Springer Nature.
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by L. Erdos.
To the memory of my waigong, Sun Wenya.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
About this article
Cite this article
He, Y. Spectral Gap and Edge Universality of Dense Random Regular Graphs. Commun. Math. Phys. 405, 181 (2024). https://doi.org/10.1007/s00220-024-05063-x
Received:
Accepted:
Published:
DOI: https://doi.org/10.1007/s00220-024-05063-x