Random matrices: The Universality phenomenon for Wigner ensembles

Introduction

Random matrix theory is a central topic in probability and mathematical physics, with many connections to various areas such as statistics, number theory, combinatorics, numerical analysis and theoretical computer science.

One of the primary goal of random matrix theory is to derive limiting laws for the eigenvalues and eigenvectors of ensembles of large ($n\times n$) Hermitian random matricesOne can of course also study non-Hermitian or non-square random matrices, though in the latter case the concept of an eigenvalue needs to be replaced with that of a singular value. In this survey we will focus almost exclusively on the square Hermitian case., in the asymptotic limit $n\to\infty$. There are many random matrix ensembles of interest, but to focus the discussion and to simplify the exposition we shall restrict attention to an important model class of ensembles, the Wigner matrix ensembles.

Let $n\geq 1$ be an integer (which we view as a parameter going off to infinity). An $n\times n$ Wigner Hermitian matrix $M_{n}$ is defined to be a random Hermitian $n\times n$ matrix $M_{n}=(\xi_{ij})_{1\leq i,j\leq n}$, in which the $\xi_{ij}$ for $1\leq i\leq j\leq n$ are jointly independent with $\xi_{ji}=\overline{\xi_{ij}}$ (in particular, the $\xi_{ii}$ are real-valued). For $1\leq i<j\leq n$, we require that the $\xi_{ij}$ have mean zero and variance one, while for $1\leq i=j\leq n$ we require that the $\xi_{ij}$ (which are necessarily real) have mean zero and variance $\sigma^{2}$ for some $\sigma^{2}>0$ independent of $i,j,n$. To simplify some of the statements of the results here, we will also assume that the $\xi_{ij}\equiv\xi$ are identically distributed for $i<j$, and the $\xi_{ii}\equiv\xi^{\prime}$ are also identically distributed for $i=j$, and furthermore that the real and imaginary parts of $\xi$ are independent. We refer to the distributions ${\operatorname{Re}}\xi$, ${\operatorname{Im}}\xi$, and $\xi^{\prime}$ as the atom distributions of $M_{n}$.

We say that the Wigner matrix ensemble obeys Condition C0 if we have the exponential decay condition

for all $1\leq i,j\leq n$ and $t\geq C^{\prime}$, and some constants $C,C^{\prime}$ (independent of $i,j,n$). We say that the Wigner matrix ensemble obeys condition C1 with constant $C_{0}$ if one has

for some constant $C$ (independent of $n$).

Of course, Condition C0 implies Condition C1 for any $C_{0}$, but not conversely.

We refer to the matrix $W_{n}:=\frac{1}{\sqrt{n}}M_{n}$ as the coarse-scale normalised Wigner Hermitian matrix, and $A_{n}:=\sqrt{n}M_{n}$ as the fine-scale normalised Wigner Hermitian matrix.

for some quantity $Z_{n}>0$ depending only on $n$, where $dM_{n}$ is Haar measure on the vector space of $n\times n$ Hermitian matrices (in the case of GUE) or real symmetric matrices (in the case of GOE), and $c$ is equal to $1/2$ (for GUE) or $1/4$ (for GOE). From (1) we easily conclude that the probability distribution of GUE is invariant with respect to conjugations by unitary matrices, and similarly the probability distribution of GOE is invariant with respect to conjugations by orthogonal matrices. However, a general Wigner matrix ensemble will not enjoy invariances with respect to such large classes of matrices. (For instance, the Bernoulli ensembles described below are only invariant with respect to conjugation by a discrete group of matrices, which include permutation matrices and reflections around the coordinate axes.)

At the opposite extreme from the invariant ensembles are the Bernoulli ensembles, which are discrete instead of continuous. In the real Bernoulli ensemble (also known as symmetric random sign matrices), each of the $\xi_{ij}$ are equal to $+1$ with probability $1/2$ and $-1$ with probability $1/2$. In the complex Bernoulli ensemble, the diagonal entries $\xi_{ii}$ still have this distribution, but the off-diagonal entries now take valuesWe use $\sqrt{-1}$ to denote the imaginary unit, in order to free up the symbol $i$ as an index variable. $\pm\frac{1}{\sqrt{2}}\pm\frac{\sqrt{-1}}{\sqrt{2}}$, with each of these four complex numbers occuring with probability $1/4$.

Many of the results given here have been extended to somewhat broader classes of matrices. For instance, one can consider generalised Wigner ensembles in which entries are not identically distributed; for instance, one can allow the variances $\sigma_{ij}^{2}$ of each entry $\xi_{ij}$ to vary in $i,j$, and even vanish for some $i,j$; the latter situation occurs for instance in band-limited random matrices; one can also consider allowing the mean $\mu_{ij}$ of the entries $\xi_{ij}$ to be non-zero (this is for instance the situation with the adjacency matrices of Erdős-Renyi random graphs). One can also consider sparse Wigner random matrices, in which only a small (randomly selected) number of entries are non-zero. For simplicity, though, we shall mostly restrict attention in this survey to ordinary Wigner ensembles. We do remark, however, that in all of these generalisations, it remains crucial that the entries $\xi_{ij}$ for $1\leq i\leq j\leq n$ are jointly independent, as many of the techniques currently available to control the fine-scale spectral structure of Wigner matrices rely heavily on joint independence.

Given an $n\times n$ Hermitian matrix $A$, we denote its $n$ eigenvalues in increasing orderIt is also common in the literature to arrange eigenvalues in decreasing order instead of increasing. Of course, the results remain the same under this convention except for minor notational changes. as

We also introduce the eigenvalue counting function

Global and local semi-circular laws

We first discuss the coarse-scale spectral structure of Wigner matrices, that is to say the structure of the eigenvalues of $W_{n}$ at unit scales (or equivalently, the eigenvalues of $M_{n}$ at scale $\sqrt{n}$, or $A_{n}$ at scale $n$). The fundamental result in this topic is the (global) Wigner semi-circular law. Denote by $\rho_{sc}$ the semi-circle density function with support on $$,

Let $M_{n}$ be a Wigner Hermitian matrix. Then for any interval $I$ (independent of $n$), one has

in the sense of probability (and also in the almost sure sense, if the $M_{n}$ are all minors of the same infinite Wigner Hermitian matrix).

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

An essentially equivalentThis formulation is slightly stronger because it also incorporates the upper bound $\|W_{n}\|_{op}\leq 2+o(1)$ on the operator norm of $W_{n}$, which is consistent with, but not implied by, the semi-circular law, and follows from the work of Bai and Yin . formulation of the semi-circular law is as follows: if $1\leq i\leq n$, then one hasWe use the asymptotic notation $o(1)$ to denote any quantity that goes to zero as $n\to\infty$, and $O(X)$ to denote any quantity bounded in magnitude by $CX$, where $C$ is a constant independent of $n$.

with probability $1-o(1)$ (and also almost surely, if the $M_{n}$ are minors of an infinite matrix), where the classical location $\lambda_{i}^{{\operatorname{cl}}}(W_{n})$ of the $i^{th}$ eigenvalue is the element of $$ defined by the formula

A remarkable feature of the semi-circular law is its universality: the precise distribution of the atom variables $\xi_{ij}$ are irrelevant for the conclusion of the law, so long as they are normalised to have mean zero and variance one (or variance $\sigma^{2}$, on the diagonal), and are jointly independent on the upper-triangular portion of the matrix. In particular, continuous matrix ensembles such as GUE or GUE, and discrete matrix ensembles such as the Bernoulli ensembles, have the same asymptotic spectral distribution when viewed at the coarse scale (i.e. by considering eigenvalue ranges of size $\sim 1$ for $W_{n}$, or equivalently of size $\sim\sqrt{n}$ for $M_{n}$ or $\sim n$ for $A_{n}$).

However, as stated, the semi-circular law does not give good control on the fine-scale behaviour of the eigenvalues, for instance in controlling $N_{I}(W_{n})$ when $I$ is a very short interval (of length closer to $1/n$ than to $1$). The fine-scale theory for Wigner matrices is much more recent than the coarse-scale theory given by the semi-circular law, and is the main focus of this survey.

There are several ways to establish the semi-circular law. For invariant ensembles such as GUE or GOE, one can use explicit formulae for the probability distribution of $N_{I}$ coming from the theory of determinantal processes, giving precise estimates all the way down to infinitesimally small scales; see e.g. or Section 3 below. However, these techniques rely heavily on the invariance of the ensemble, and do not directly extend to more general Wigner ensembles. Another popular technique is the moment method, based on the basic moment identities

for all $k\geq 0$. The moment method already is instructive for revealing at least one explanation for the universality phenomenon. If one takes expectations in the above formula, one obtains

For those terms for which each edge $\{i_{j},i_{j+1}\}$ appears at most twice, the summand can be explicitly computed purely in terms of the mean and variances of the $\xi_{ij}$, and are thus universal. Terms for which an edge appears three or more times are sensitive to higher moments of the atom distribution, but can be computed to give a contribution of $o(1)$ (at least assuming a decay condition such as Condition C0). This already explains universality for quantities such as ${\mathbf{E}}N_{I}(W_{n})$ for intervals $I$ of fixed size (independent of $n$), at least if one assumes a suitable decay condition on the entries (and one can use standard truncation arguments to relax such hypotheses substantially).

At the edges $\pm 2$ of the spectrum, the moment method can be pushed further, to give quite precise control on the most extreme eigenvalues of $W_{n}$ (which dominate the sum in (5)) if $k$ is sufficiently large; see and the references therein. However, the moment method is quite poor at controlling the spectrum in the bulk. To improve the understanding of the bulk spectrum of Wigner matrices, Bai (see also [6, Chapter 8]) used the Stieltjes transform method (building upon the earlier work of Pastur ) to show that the speed of convergence to the semi-circle was $O(n^{-1/2})$. Instead of working with moments, one instead studied the Stieltjes transform

is the Stieltjes transform of the semi-circular distribution $\rho_{\operatorname{sc}}$. The key to the argument is to establish a self-consistent equation for $s_{n}$, which roughly speaking takes the form

One can explicitly compute by contour integration that

for $z\neq$, where $\sqrt{z^{2}-4}$ is the branch of the square root that is asymptotic to $z$ at infinity, and in particular that

From a stability analysis of the elementary equation (7) and a continuity argument, one can then use (6) to show that

which then implies convergence to the semi-circular law. If one can obtain quantitative control on the approximation in (6), one can then deduce quantitative versions of the semi-circular law that are valid for certain short intervals.

We briefly sketch why one expects the self-consistent equation to hold. One can expand

where $((W_{n}-zI)^{-1})_{ii}$ denotes the $ii^{{\operatorname{th}}}$ entry of the matrix $(W_{n}-zI)^{-1}$. Let us consider the $i=n$ term for sake of concreteness. If one expands $W_{n}$ as a block matrix

property between the eigenvalues of $M_{n-1}$ and the eigenvalues of $M_{n}$ (which easily follows from the Courant-Fisher minimax formula

for the eigenvalues), one easily obtains an approximation of the form

Similarly for the other diagonal entries $((W_{n}-zI)^{-1})_{ii}$. Inserting this approximation back into (9) gives the desired approximation (6), heuristically at least.

The above argument was optimizedThere are further refinements to this method in Erdős, Yau, and Yin , and Erdős-Knowles-Yau-Yin , that took advantage of some additional cancellation between the error terms in (11) (generalised to indices $i=1,\ldots,n$) that could be obtained (via the moment method in , , and via decoupling arguments in , ), to improve the error estimates further. These refinements are not needed for the application to Wigner matrices assuming a strong decay condition such as Condition C0, but is useful in generalised Wigner matrix models, such as sparse Wigner matrices in which most of the entries are zero, or in models where one only has a weak amount of decay (e.g. Condition C1 with $C_{0}=4+{\varepsilon}$). These refinements also lead to the very useful eigenvalue rigidity bound (15). in a sequence of papers by Erdős, Schlein, and Yau (see also [104, Section 5.2] for a slightly simplified proof). As a consequence, one was able to obtain good estimates of the form (8) even when $z$ was quite close to the spectrum $$(e.g. at distance$O(n^{-1+{\varepsilon}})$for some small${\varepsilon}>0$, which in turn leads (by standard arguments) to good control on the eigenvalue counting function$N_{I}(W_{n})$for intervals$I$of length as short as$n^{-1+{\varepsilon}}$. (Note that as there are only$n$eigenvalues in all, such intervals are expected to only have about$O(n^{\varepsilon})$ eigenvalues in them.) Such results are known as local semi-circular laws. A typical such law (though not the strongest such law known) is as follows:

See e.g. [98, Theorem 1.10]. For the most precise estimates currently known of this type (and with the weakest decay hypotheses on the entries), see . ∎

A variant of Theorem 7, which was establishedThe result in actually proves a more precise result that also gives sharp results in the edge of the spectrum, though due to the sparser nature of the $\lambda_{i}^{\operatorname{cl}}(W_{n})$ in that case, the error term $O_{\varepsilon}(n^{-1+{\varepsilon}})$ must be enlarged. in the subsequent paper , is the extremely useful eigenvalue rigidity property

valid with overwhelming probability in the bulk range $\delta n\leq i\leq(1-\delta)n$ for any fixed $\delta>0$ (and assuming Condition C0), and which significantly improves upon (4). This result is key in some of the strongest applications of the theory. See Section 7.7 for the precise form of this result and recent developments.

Roughly speaking, results such as Theorem 7 and (15) control the spectrum of $W_{n}$ at scales $n^{-1+{\varepsilon}}$ and above. However, they break down at the fine scale $n^{-1}$; indeed, for intervals $I$ of length $|I|=O(1/n)$, one has $n\int_{I}\rho_{{\operatorname{sc}}}(x)\ dx=O(1)$, while $N_{I}(W_{n})$ is clearly a natural number, so that one can no longer expect an asymptotic of the form (14). Nevertheless, local semicircle laws are an essential part of the fine-scale theory. One particularly useful consequence of these laws is that of eigenvector delocalisation:

Let $M_{n}$ be a Wigner matrix obeying Condition C0, and let ${\varepsilon}>0$. Then with overwhelming probability, one has $u_{i}(W_{n})^{*}e_{j}=O(n^{-1/2+{\varepsilon}})$ for all $1\leq i,j\leq n$.

Note from Pythagoras’ theorem that $\sum_{j=1}^{n}|u_{i}(M_{n})^{*}e_{j}|^{2}=\|u_{i}(M_{n})\|^{2}=1$; thus Corollary 8 asserts, roughly speaking, that the coefficients of each eigenvector are as spread out (or delocalised) as possible.

(Sketch) By symmetry we may take $e_{j}=n$. Fix $i$, and set $\lambda:=\lambda_{i}(W_{n})$; then the eigenvector equation $(W_{n}-\lambda)u_{i}(W_{n})=0$ can be expressed using (10) as

and by using concentration of measure tools such as Talagrand’s concentration inequality (see e.g. ), one can then conclude that $\|\pi_{V}(X_{n})\|\gg 1$ with overwhelming probability. This concludes the claim of the Corollary in the bulk case.

The edge case is more delicate, due to the sparser spectrum near $\lambda$. Here, one takes advantage of the identity

In the edge case, the right-hand side is close to $\pm 2$, and this can be used (together with the local semicircle law) to obtain the lower bound

with overwhelming probability, which gives the claim. See for details. ∎

A slicker approach to eigenvalue delocalisation proceeds via control of the resolvent (or Green’s function) $(W_{n}-zI)^{-1}$, taking advantage of the identity

for $z=E+i\eta$; see for instance for details of this approach. Note from (11) that the Stieltjes transform arguments used to establish the local semicircle law already yield control on quantities such as $((W_{n}-zI)^{-1})_{jj}$ as a byproduct.

Fine-scale spectral statistics: the case of GUE

We now turn to the question of the fine-scale behavior of eigenvalues of Wigner matrices, starting with the model case of GUE. Here, it is convenient to work with the fine-scale normalisation $A_{n}:=\sqrt{n}M_{n}$. For simplicity we will restrict attention to the bulk region of the spectrum, which in the fine-scale normalisation corresponds to eigenvalues $\lambda_{i}(A_{n})$ of $A_{n}$ that are near $nu$ for some fixed $-2<u<2$ independent of $n$.

There are several quantities at the fine scale that are of interest to study. For instance, one can directly study the distribution of individual (fine-scale normalised) eigenvalues $\lambda_{i}(A_{n})$ for a single index $1\leq i\leq n$, or more generally study the joint distribution of a $k$-tuple $\lambda_{i_{1}}(A_{n}),\ldots,\lambda_{i_{k}}(A_{n})$ of such eigenvalues for some $1\leq i_{1}<\ldots<i_{k}\leq n$. Equivalently, one can obtain estimates for expressions of the form

where $E_{{\varepsilon},x_{1},\ldots,x_{k}}$ is the event that there is an eigenvalue of $A_{n}$ in each of the intervals $[x_{i},x_{i}+{\varepsilon}]$ for $i=1,\ldots,k$. Alternatively, one can write

where $\rho_{n}:=\frac{1}{n!}R_{n}^{(n)}$ is the symmetrized joint probability distribution of all $n$ eigenvalues of $A_{n}$.

Note from (18) that control on the expressions (17) implies (in principle, at least) control on the $k$-point correlation function by summing over the relevant indices $i_{1},\ldots,i_{k}$; and from eigenvalue rigidity estimates such as (17) we see that (for fixed $k$, at least) there are only $n^{o(1)}$ choices for the $k$-tuple $(i_{1},\ldots,i_{k})$ that contribute to this sum.

Informally, for infinitesimal ${\varepsilon}>0$, ${\varepsilon}^{k}\rho^{(k)}_{n,u}(x_{1},\ldots,x_{k})$ is approximately equal to the probability that there is an eigenvalue in each of the intervals $[nu+\frac{x_{i}}{\rho_{\operatorname{sc}}(u)},nu+\frac{x_{i}+{\varepsilon}}{\rho_{\operatorname{sc}}(u)}]$ for

The Stieltjes transform $s_{n}(z)=\operatorname{trace}((W_{n}-z)^{-1})$ introduced previously is related to the fine-scale normalised eigenvalues by the formula

More generally, one can consider the random variables

The joint distribution of such random variables can be expressed in terms of the $k$-point correlations; for instance, one has

Conversely, it is possible (with some combinatorial effort) to control the $k$-point correlation function in terms of the joint distribution of such random variables; see [41, §8].

The distribution of the eigenvalue counting functions $N_{I}(A_{n})=N_{I/n}(W_{n})$ can be expressed in terms of the distribution of the individual eigenvalues or from the correlation function. For instance, one has (for continuous ensembles, at least) the formula

for any $k\geq 0$ (with the convention that $\binom{n}{k}=0$ whenever $n<k$).

Finally, to close the circle of relationships, by coupling the eigenvalue counting function $N_{I}(W_{n})$ for intervals such as $I=[-2,x]$ with previously mentioned quantities such as the Stieltjes transforms, as well as additional level repulsion estimates that prevent two consecutive eigenvalues from getting too close to each other too often, one can recover control of individual eigenvalues; see .

It has been generally believed (and in many cases explicitly conjectured; see e.g. [77, page 9]) that the asymptotic statistics for the quantities mentioned above are universal, in the sense that the limiting laws do not depend on the distribution of the atom variables (assuming of course that they have been normalised as stated in Definition 1). This phenomenon was motivated by examples of similarly universal laws in physics, such as the laws of thermodynamics or of critical percolation; see e.g. for further discussion.

It is clear that if one is able to prove the universality of a limiting law, then it suffices to compute this law for one specific model in order to describe the asymptotic behaviour for all other models. A natural choice for the specific model is GUE, as for this model, many limiting laws can be computed directly thanks to the availability of an explicit formula for the joint distribution of the eigenvalues, as well as the useful identities of determinantal processes. For instance, one has Ginibre’s formula

for the joint eigenvalue distribution, as can be verified from (1) and a change of variables; see . From (21) and a downwards induction on $k$ one can then obtain the Gaudin-Mehta formula

for all $0\leq k\leq n$, where $K_{n}$ is the kernel

and $P_{0},P_{1},\ldots$ are the Hermite polynomials (thus each $P_{n}$ is a degree $n$ polynomial, with the $P_{n}$ being orthonormal with respect to the measure $e^{-x^{2}/2}\ dx$). This formula, combined with the classical Plancherel-Rotach asymptotics for Hermite polynomials, gives the limiting law

locally uniformly in $x_{1},\ldots,x_{k}$ where

and $K_{{\operatorname{Sine}}}$ is the Dyson sine kernel

(with the usual convention that $\frac{\sin x}{x}$ equals $1$ at the origin); see . Standard determinantal process identities then give an asymptotic

for any fixed real numbers $a<b$ and $-2<u<2$, where the $\xi_{j}\in\{0,1\}$ are independent Bernoulli variables with ${\mathbf{E}}(\xi_{j})=\lambda_{j}$, the $\lambda_{j}$ are the eigenvalues of the integral operator $T_{[a,b]}:L^{2}([a,b])\to L^{2}([a,b])$ defined by

and the convergence is in the sense of probability distributions; see e.g. . Thus, for instance, the probability that the interval $[nu+a/\rho_{\operatorname{sc}}(u),nu+b/\rho_{\operatorname{sc}}(u)]$ is devoid of eigenvalues converges as $n\to\infty$ to the Fredholm determinantSee for a more explicit description of this determinant in terms of a solution to an ODE.

Using this formula one can obtain a limiting law for an (averaged) eigenvalue spacing. More precisely, given an intermediate scale parameter $t_{n}$ such that $t_{n},n/t_{n}\to\infty$ as $n\to\infty$, define the quantity

Then one can establish for fixed $-2<u<2$ that

see . Informally, $\rho$ is the asymptotic distribution of the normalised gap $\rho_{\operatorname{sc}}(u)(\lambda_{i+1}(A_{n})-\lambda_{i}(A_{n}))$ for typical $\lambda_{i}(A_{n})$ near $nu$.

A variant of the computations that lead to (24) (and more precisely, a general central limit theorem for determinantal processes due to Costin-Leibowitz and Soshnikov ) can give a limiting law for $N_{I}(A_{n})$ in the case of the macroscopic intervals $I=[nu,+\infty)$. More precisely, one has the central limit theorem

in the sense of probability distributions, for any $-2<u<2$; see . By using the counting functions $N_{[nu,+\infty)}$ to solve for the location of individual eigenvalues $\lambda_{i}(A_{n})$, one can then conclude the central limit theorem

whenever $\lambda_{i}^{\operatorname{cl}}(A_{n}):=n\lambda_{i}^{\operatorname{cl}}(W_{n})$ is equal to $n(u+o(1))$ for some fixed $-2<u<2$; see . Informally, this asserts (in the GUE case, at least) that each eigenvalue $\lambda_{i}(A_{n})$ typically deviates by $O(\sqrt{\log n}/\rho_{\operatorname{sc}}(u))$ around its classical location; this result should be compared with (15), which has a slightly worse bound on the deviation (of shape $O_{\varepsilon}(n^{\varepsilon})$ instead of $O(\sqrt{\log n})$) but which holds with overwhelming probability (and for general Wigner ensembles).

The above analysis extends to many other classes of invariant ensembles (such as GOEThere are some further direct relationships between the GOE and GUE eigenvalue distributions that can be used to deduce control of the former from that of the latter; see ., for which the joint eigenvalue distribution has a form similar to (21) (namely, an exponential factor and a power of a Vandermonde determinant). However, the Hermite polynomials are usually replaced by some other family of orthogonal polynomials, and one needs additional tools (such as the theory of Riemann-Hilbert problems) to obtain enough asymptotic control on those polynomials to recover the other results of the type given here. See for further discussion. However, we will not pursue this important aspect of the universality phenomenon for random matrices here, as our focus is instead on the Wigner matrix models.

Extending beyond the GUE case I. Heat flow methods

The arguments used to establish the results in the previous section relied heavily on the special structure of the GUE ensemble, and in particular the fact that the joint probability distribution had a determinantal structure (cf. (22)). To go significantly beyond the GUE case, there are two families of techniques used. One family are the heat flow methods, based on applying an Ornstein-Uhlenbeck process to a Wigner ensemble $M_{n}^{0}$ to obtain a gauss divisible ensemble $M_{n}^{t}$ that is closer to the GUE, and showing that the latter obeys approximately the same statistics as the GUE. The other family of methods are the swapping methods, in which one replaces the entries of one Wigner ensemble $M_{n}$ with another ensemble $M^{\prime}_{n}$ which are close in some suitable sense (e.g. in the sense of matching moments), and shows that the statistics for both ensembles are close to each other. The two methods are complementary, and many of the strongest results known about universality for Wigner matrices use a combination of both methods.

Our focus shall largely be on the swapping methods (and in particular on the four moment theorem), but in this section we will briefly survey the heat flow techniques. (For a more detailed survey of these methods, see or .)

Let $M_{n}^{0}$ be a Wigner matrix. One can then define the matrix Ornstein-Uhlenbeck process $M_{n}^{t}$ for times $t\in[0,+\infty)$ by the stochastic differential equationOne can omit the normalising term $-\frac{1}{2}M_{n}^{t}\ dt$ in this process to obtain a Brownian process rather than an Ornstein-Uhlenbeck process, but we retain the normalising term in order to keep the variance of each (off-diagonal) entry of the matrix $M_{n}^{t}$ fixed.

with initial data $M_{n}^{t}|_{t=0}=M_{n}^{0}$, where $\beta_{t}$ is a Hermitian matrix process whose entries are standard real Brownian motions on the diagonal and standard complex Brownian motions off the diagonal, with the $\beta_{t}$ being independent of $M_{n}^{0}$, and with the upper-triangular entries of $\beta_{t}$ being jointly independent. A standard stochastic calculus computation shows that $M_{n}^{t}$ is distributed according to the law

where $G_{n}$ is a GUE matrix independent of $M_{n}^{0}$. In particular, the random matrix $M_{n}^{t}$ is distributed as $M_{n}^{0}$ for $t=0$ and then continuously deforms towards the GUE distribution as $t\to+\infty$. We say that a Wigner matrix is gauss divisible (also known as a Johansson matrix) with parameter $t$ if it has the distribution of $e^{-t/2}M_{n}^{0}+(1-e^{-t})^{1/2}G_{n}$ for some Wigner matrix $M_{n}^{0}$; thus $M_{n}^{t}$ is gauss divisible with parameter $t$. Note that not every Wigner matrix is gauss divisible; among other things, gauss divisible matrices necessarily have a continuous (and in fact smooth) distribution rather than a discrete one. The larger one makes $t$, the more restrictive the requirement of gauss divisibility becomes, until in the asymptotic limit $t=+\infty$ the only gauss divisible ensemble remaining is GUE.

The dynamics of the (fine-scale normalised) eigenvalues $\lambda_{i}(A_{n}^{t})=\sqrt{n}\lambda_{i}(M_{n}^{t})$ were famously established by Dyson to be governed by the (normalised) Dyson Brownian motion equations

where $B_{1},\ldots,B_{n}$ are independent standard real Brownian motions.

and we write $\partial_{j}$ as shorthand for the partial derivative $\frac{\partial}{\partial x_{j}}$. Observe that the Ginibre distribution $\rho_{n}^{\infty}$ defined by (21) is annihilated by $D$ and is thus an equilibrium state of the Dyson Fokker-Planck equation; this is of course consistent with the convergence of the distribution of $M_{n}^{t}$ to the distribution of GUE.

The Dyson Fokker-Planck equation (28) can in fact be solved explicitly by observing the identity

where $\Delta_{n}(x):=\prod_{1\leq i<j\leq n}(x_{i}-x_{j})$ is the Vandermonde determinant, and $L$ is the Ornstein-Uhlenbeck operator

This allows one to reduce the Dyson Fokker-Planck equation by a change of variables to the Ornstein-Uhlenbeck Fokker-Planck equation $\frac{\partial}{\partial t}u=Lu$, which has an explicit fundamental solution. Using thisThe derivation of these formulae in is somewhat different, proceeding via the Harish-Chandra/Itzykson-Zuber formula ; however, as noted in that paper, one can also use Dyson Brownian motion to derive the formula, which is the approach taken here. one can obtain an explicit formula for $\rho_{n}^{t}$ in terms of $\rho_{n}^{0}$, and with a bit more effort one can also obtain a (slightly messy) determinantal formula for the associated correlation functions $(R_{n}^{(k)})^{t}$; see , . By exploiting these explicit formulae, Johansson was ableSome additional technical hypotheses were assumed in , namely that the diagonal variance $\sigma^{2}$ was equal to $1$, that the real and imaginary parts of each entry of $M^{\prime}_{n}$ were independent, and that Condition C1held for some $C_{0}>6$. to extend the asymptotic (23) for the $k$-point correlation function from GUE to the more general class of gauss divisible matrices with fixed parameter $t>0$ (independent of $n$).

It is of interest to extend this analysis to as small a value of $t$ as possible, since if one could set $t=0$ then one would obtain universality for all Wigner ensembles. By optimising Johansson’s method (and taking advantage of the local semi-circle law), Erdős, Peche, Ramirez, Schlein, and Yau were able to extend the universality of (23) (interpreted in a suitably weak convergence topology, such as vague convergence) to gauss divisible ensembles for $t$ as small as $n^{-1+{\varepsilon}}$ for any fixed ${\varepsilon}>0$.

An alternate approach to these results was developed by Erdős, Ramirez, Schlein, Yau, and Yin , , . The details are too technical to be given here, but the main idea is to use standard tools such as log-Sobolev inequalities to control the rate of convergence of the Dyson Fokker-Planck equation to the equilibrium measure $\rho_{n}^{\infty}$, starting from the initial data $\rho_{n}^{0}$; informally, if one has a good convergence to this equilibrium measure by time $t$, then one can obtain universality results for gauss divisible ensembles with this parameter $t$. A simple model to gain heuristic intuition on the time needed to converge to equilibrium is given by the one-dimensional Ornstein-Uhlenbeck process

As was already observed implicity by Dyson, the difficulty with the Dyson Fokker-Planck equation (28) (or equivalently, the Dyson Brownian motion (27)) is that different components of the evolution converge to equilibrium at different rates. Consider for instance the trace variable $T:=\lambda_{1}(A_{n}^{t})+\ldots+\lambda_{n}(A_{n}^{t})$. Summing up (27) we see that this variable evolves by the Ornstein-Uhlenbeck process

for some standard Brownian motion $\beta_{t}$, and so we expect convergence to equilibrium for this variable in time $O(1)$. At the other extreme, consider an eigenvalue gap $s_{i}:=\lambda_{i+1}(A_{n}^{t})-\lambda_{i}(A_{n}^{t})$ somewhere in the bulk of the spectrum. Subtracting two consecutive cases of (27), we see that

Using the heuristic $\lambda_{j}(A_{n})\approx\lambda_{j}^{\operatorname{cl}}(A_{n})$, we expect $\theta_{i}$ to be of size comparable to $n$ and $s_{i}$ to be of size comparable to $1$; comparing (30) with (29) we thus expect $s_{i}$ to converge to equilibrium in time $O(1/n)$.

One can use a standard log-Sobolev argument of Bakry and Emery (exploiting the fact that the equilibrium measure $\rho_{n}^{\infty}$ is the negative exponential of a strictly convex function $H$) to show (roughly speaking) that the Dyson Brownian motion converges to global equilibrium in time $O(1)$; see e.g. . Thus the trace variable $T$ is among the slowest of the components of the motion to converge to equilibrium. However, for the purposes of controlling local statistics such as the normalised $k$-point correlation function

and particularly the averaged normalised $k$-point correlation function

Extending beyond the GUE case II. Swapping and the Four Moment Theorem

The heat flow methods discussed in the previous section enlarge the class of Wigner matrices to which GUE-type statistics are known to hold, but do not cover all such matrices, and in particular leave out discrete ensembles such as the Bernoulli ensembles, which are not gauss divisible for any $t>0$. To complement these methods, we have a family of swapping methods to extend spectral asymptotics from one ensemble to another, based on individual replacement of each coefficient of a Wigner matrix, as opposed to deforming all of the coefficients simultaneously via heat flow.

The simplest (but rather crude) example of a swapping method is based on the total variation distance $d(X,Y)$ between two random variables $X,Y$ taking values in the same range $R$, defined by the formula

where the supremum is over all measurable subsets $E$ of $R$ Clearly one has

and thus from (18) we have the somewhat crude bound

for any test function $F$. On the other hand, by swapping the entries of $M_{n}$ with $M^{\prime}_{n}$ one at a time, we see that

We thus see that if $d(\xi_{ij},\xi^{\prime}_{ij})\leq n^{-C}$ for a sufficiently large constant $C$ (depending on $k$), then the $k$-point correlation functions of $M_{n}$ and $M^{\prime}_{n}$ are asymptotically equivalent. This argument was quite crude, costing many more powers of $n$ than is strictly necessary, and by arguing more carefully one can reduce this power; see . However, it does not seem possible to eliminate the factors of $n$ entirely from this type of argument.

Another fundamental example of a swapping method is the Lindeberg exchange strategy We would like to thank S. Chatterjee and M. Krisnapur for introducing this method to us, introduced in Lindeberg’s classic proof of the central limit theorem, and first applied to Wigner ensembles in . We quickly sketch that proof here. Suppose that $X_{1},\ldots,X_{n}$ are iid real random variables with mean zero and variance one, and let $Y_{1},\ldots,Y_{n}$ be another set of iid real random variables and mean zero and variance one (which we may assume to be independent of $X_{1},\ldots,X_{n}$). We would like to show that the averages $\frac{X_{1}+\ldots+X_{n}}{\sqrt{n}}$ and $\frac{Y_{1}+\ldots+Y_{n}}{\sqrt{n}}$ have asymptotically the same distribution, thus

for any smooth, compactly supported function $F$. The idea is to swap the entries $X_{1},\ldots,X_{n}$ with $Y_{1},\ldots,Y_{n}$ one at a time and obtain an error of $o(1/n)$ on each such swap. For sake of illustration we shall just establish this for the first swap:

We write $\frac{X_{1}+\ldots+X_{n}}{\sqrt{n}}=S+n^{-1/2}X_{n}$, where $S:=\frac{X_{1}+\ldots+X_{n-1}}{\sqrt{n}}$. From Taylor expansion we see (for fixed smooth, compactly supported $F$) that

We then make the crucial observation that $S$ and $X_{n}$ are independent. On taking expectations (and assuming that $X_{n}$ has a bounded third moment) we conclude that

But by hypothesis, $X_{n}$ and $Y_{n}$ have matching moments to second order, in the sense that ${\mathbf{E}}X_{n}^{i}={\mathbf{E}}Y_{n}^{i}$ for $i=0,1,2$. Thus, on subtracting, we obtain (31) (with about a factor of $n^{-1/2}$ to spare; cf. the Berry-Esséen theorem , ).

Note how the argument relied on the matching moments of the two atom variables $X_{i},Y_{i}$; if one had more matching moments, one could continue the Taylor expansion and obtain further improvements to the error term in (31), with an additional gain of $n^{-1/2}$ for each further matching moment.

We can apply the same strategy to control expressions such as ${\mathbf{E}}F(M_{n})-F(M^{\prime}_{n})$, where $M_{n},M^{\prime}_{n}$ are two (independent) Wigner matrices. If one can obtain bounds such as

As it turns out, the numerology of swapping for matrices is similar to that for the central limit theorem, in that each matching moment leads to an additional factor of $O(n^{-1/2})$ in the error estimates. From this, one can expect to obtain asymptotics of the form (32) when the entries of $M_{n},M^{\prime}_{n}$ match to second order on the diagonal and to fourth order off the diagonal; informally, this would mean that ${\mathbf{E}}F(M_{n})$ depends only on the first four moments of the entries (and the first two moments of the diagonal entries). In the case of statistics arising from eigenvalues or eigenvectors, this is indeed the case, and the precise statement is known as the Four Moment Theorem.

We first state the Four Moment Theorem for eigenvalues.

Let $k\geq 1$. Two complex random variables $\xi,\xi^{\prime}$ are said to match to order $k$ if one has ${\mathbf{E}}{\operatorname{Re}}(\xi)^{a}{\operatorname{Im}}(\xi)^{b}={\mathbf{E}}{\operatorname{Re}}(\xi^{\prime})^{a}{\operatorname{Im}}(\xi^{\prime})^{b}$ whenever $a,b\geq 0$ are integers such that $a+b\leq k$.

In the model case when the real and imaginary parts of $\xi$ or of $\xi^{\prime}$ are independent, the matching moment condition simplifies to the assertion that ${\mathbf{E}}{\operatorname{Re}}(\xi)^{a}={\mathbf{E}}{\operatorname{Re}}(\xi^{\prime})^{a}$ and ${\mathbf{E}}{\operatorname{Im}}(\xi)^{b}={\mathbf{E}}{\operatorname{Im}}(\xi^{\prime})^{b}$ for all $0\leq a,b\leq k$.

We remark that in the papers , , , a variant of the above result, which we called the three moment theorem, was asserted, in which the hypothesis of four matching moments off the diagonal was relaxed to three matching moments (and no moment matching was required on the diagonal), but for which the bound (33) was improved to $|\nabla^{j}G(x)|\leq n^{-Cjc_{0}}$ for some sufficiently large absolute constant $C>0$. Unfortunately, the proof given of the three moment theorem in these papers was not correct as stated, although the claim can still be proven in most cases by other means; see Appendix A.

A preliminary version of Theorem 11 was first established by the authors in , in the caseIn the paper, $k$ was held fixed, but an inspection of the argument reveals that it extends without difficulty to the case when $k$ is as large as $n^{c_{0}}$, for $c_{0}$ small enough. of bulk eigenvalues (thus $\delta n\leq i_{1},\ldots,i_{k}\leq(1-\delta)n$ for some absolute constant $\delta>0$) and assuming Condition C0 instead of Condition C1. In , the restriction to the bulk was removed; and in , Condition C0 was relaxed to Condition C1 for a sufficiently large value of $C_{0}$. We will discuss the proof of this theorem in Section 6.

The following technical generalization of the Four Moment Theorem, in which the entries of $M_{n},M^{\prime}_{n}$ only match approximately rather than exactly, is useful for some applications.

The conclusions of Theorem 11 continue to hold if the requirement that $\xi_{ij}$ and $\xi^{\prime}_{ij}$ match to order $4$ is relaxed to the conditions

whenever $a,b\geq 0$ and $a+b\leq 4$, where

This proposition follows from an inspection of the proof of Theorem 11: see Section 6.

A key technical result used in the proof of the Four Moment Theorem, which is also of independent interest, is the gap theorem:

Let $M_{n}$ be a Wigner matrix obeying Condition C1 for a sufficiently large absolute constant $C_{0}$. Then for every $c_{0}>0$ there exists a $c_{1}>0$ (depending only on $c_{0}$) such that

We discuss this theorem in Section 6. Among other things, the gap theorem tells us that eigenvalues of a Wigner matrix are usually simple. Closely related level repulsion estimates were established (under an additional smoothness hypothesis on the atom distributions) in .

Another variant of the Four Moment Theorem was subsequently introduced in , in which the eigenvalues $\lambda_{i_{j}}(A_{n})$ appearing in Theorem 11 were replaced by expressions such as (20) that are derived from the resolvent (or Green’s function) $(W_{n}-z)^{-1}$, but with slightly different technical hypotheses on the matrices $M_{n},M^{\prime}_{n}$; see for full details. As the resolvent-based quantities (20) are averaged statistics that sum over many eigenvalues, they are far less sensitive to the eigenvalue repulsion phenomenon than the individual eigenvalues, and as such the version of the Four Moment Theorem for Green’s function has a somewhat simpler proof (based on resolvent expansions rather than the Hadamard variation formulae and Taylor expansion). Conversely, though, to use the Four Moment Theorem for Green’s function to control individual eigenvalues, while possible, requires a significant amount of additional argument; see .

Unfortunately, the eigenvectors $u_{i}(M_{n})$ are not unique in either the Hermitian or real symmetric cases; even if one assumes that the spectrum of $M_{n}$ is simple, in the sense that

one has the freedom to rotate each $u_{i}(M_{n})$ by a unit phase $e^{\sqrt{-1}\theta}\in U(1)$. In the real symmetric case, in which we force the eigenvectors to have real coefficients, one only has the freedom to multiply each $u_{i}(M_{n})$ by a sign $\pm\in O(1)$. There are a variety of ways to eliminate this ambiguity. For sake of concreteness we will remove the ambiguity by working with the orthogonal projections $P_{i}(M_{n})$ to the eigenspace at eigenvalue $\lambda_{i}(M_{n})$; if this eigenvalue is simple, we simply have $P_{i}(M_{n}):=u_{i}(M_{n})u_{i}(M_{n})^{*}$.

and $P_{i,p,q}(M)$ is the $pq$ coefficient of the projection $P_{i}(M)$. The bounds are uniform in the choice of $i_{1},\ldots,i_{k},p_{1},\ldots,p_{k},q_{1},\ldots,q_{k}$.

We also remark that the Four Moment Theorem for eigenvectors (in conjunction with the eigenvalue rigidity bound (15)) can be used to establish a variant of the Four Moment Theorem for Green’s function, which has the advantage of being applicable all the way up to the real axis (assuming a level repulsion hypothesis); see .

It is a natural question to ask whether the requirement of four matching moments (or four approximately matching moments, as in Proposition 12) is genuinely necessary. As far as the distribution of individual eigenvalues $\lambda_{i}(A_{n})$ are concerned, the answer is essentially “yes”, even in the identically distributed case, as the following result from shows.

Let $M_{n},M^{\prime}_{n}$ be real symmetric Wigner matrices whose atom variables $\xi,\xi^{\prime}$ have vanishing third moment ${\mathbf{E}}\xi^{3}={\mathbf{E}}(\xi^{\prime})^{3}=0$ but with distinct fourth moments ${\mathbf{E}}\xi^{4}\neq{\mathbf{E}}(\xi^{\prime})^{4}$. Then for all sufficiently large $n$, one has

for some $\kappa$ depending only on the atom distributions.

This result is established by combining a computation of the fourth moment $\sum_{i=1}^{n}\lambda_{i}(A_{n})^{4}$ with eigenvalue rigidity estimates such as (15). Informally, it asserts that on average, the mean value of $\lambda_{i}(A_{n})$ is sensitive to the fourth moment of the atom distributions at the scale of the mean eigenvalue spacing (which is comparable to $1$ in the bulk at least). In contrast, the Four Moment Theorem morallyThis is not quite true as stated, because of the various error terms in the Four Moment Theorem, and the requirement that the function $G$ in that theorem is smooth. A more accurate statement (cf. the proof of Theorem 18 below) is that if the median of $\lambda_{i}(A_{n})$ is $M$ (thus ${\mathbf{P}}(\lambda_{i}(A_{n})\leq M)=1/2$, in the continuous case at least), then one has ${\mathbf{P}}(\lambda_{i}(A^{\prime}_{n})\leq M+n^{-c_{0}}),{\mathbf{P}}(\lambda_{i}(A^{\prime}_{n})\geq M-n^{-c_{0}})\geq 1/2-n^{-c_{0}},$ which almost places the median of $\lambda_{i}(A^{\prime}_{n})$ within $O(n^{-c_{0}})$ of $M$. asserts that when the atom variables of $M_{n}$ and $M^{\prime}_{n}$ match to fourth order, then the median of $\lambda_{i}(A_{n})$ and of $\lambda_{i}(A^{\prime}_{n})$ only differ by $O(n^{-c_{0}})$. Thus, Theorem 15 and Theorem 11 are not directly comparable to each other. Nevertheless it is expected that the mean and median of $\lambda_{i}(A_{n})$ should be asymptotically equal at the level of the mean eigenvalue spacing, although this is just beyond the known results (such as (15)) on the distribution of these eigenvalues. As such, Theorem 15 provides substantial evidence that the Four Moment Theorem breaks down if one does not have any sort of matching at the fourth moment.

By computing higher moments of $\lambda_{i}(A_{n})$, it was conjectured in that one has an asymptotic of the form

for all $i$ in the bulk region $\delta n\leq i\leq(1-\delta)n$, where $C_{i,n}$ is a quantity independent of the atom distribution $\xi$. (At the edge, the dependence on the fourth moment is weaker, at least when compared against the (now much wider) mean eigenvalue spacing; see Section 7.1.)

We remark that while the statistics of individual eigenvalues are sensitive to the fourth moment, averaged statistics such as the $k$-point correlation functions $\rho_{n,u}^{(k)}$ are much less sensitive to this moment (or the third moment). Indeed, this is already visible from the results in Section 4, as gauss divisible matrices can have a variety of possible third or fourth moments for their atom distributions (see Lemma 23).

Sketch of proof of four moment theorem

In this section we discuss the proof of Theorem 11 and Theorem 13, following the arguments that originated in and refined in . To simplify the exposition, we will just discuss the four moment theorem; the proof of the approximate four moment theorem in Proposition 12 is established by a routine modification of the argument.

For technical reasons, the two theorems need to be proven together. Let us say that a Wigner matrix $M_{n}$ has the gap property if it obeys the conclusion of Theorem 13; thus Theorem 13 asserts that all Wigner matrices obeying Condition C1 for sufficiently large $C_{0}$ have the gap property. We do not know of a direct proof of this result that does not go through the Four Moment Theorem; however, it is possible to establish an independent proof of a more restrictive result:

Any Wigner matrix obeying Condition C0 has the gap property.

We discuss this theorem (which is [104, Theorem 19]) later in this section. Another key ingredient is the following truncated version of the Four Moment Theorem, in which one removes the event that two consecutive eigenvalues are too close to each other. For technical reasons, we need to introduce quantities

for $i=1,\ldots,n$, which is a regularised measure of extent to which $\lambda_{i}(A_{n})$ is close to any other eigenvalue of $A_{n}$.

Let $c_{0}>0$ be a sufficiently small constant. Let $M_{n}=(\xi_{ij})_{1\leq i,j\leq n}$ and $M^{\prime}_{n}=(\xi^{\prime}_{ij})_{1\leq i,j\leq n}$ be two Wigner matrices obeying Condition C1for some sufficiently large absolute constant $C_{0}$. Assume furthermore that for any $1\leq i<j\leq n$, $\xi_{ij}$ and $\xi^{\prime}_{ij}$ match to order $4$ and for any $1\leq i\leq n$, $\xi_{ii}$ and $\xi^{\prime}_{ii}$ match to order $2$. Set $A_{n}:=\sqrt{n}M_{n}$ and $A^{\prime}_{n}:=\sqrt{n}M^{\prime}_{n}$, let $1\leq k\leq n^{c_{0}}$ be an integer, and let

We will discuss the proof of this theorem shortly. Applying Theorem 17 with $k=1$ and a function $G$ that depends only a single variable $Q_{i}$, and using the gap property to bound $Q_{i}$ (cf. [104, Lemma 49]), one can show a four moment property for the gap theorem: if $M_{n},M^{\prime}_{n}$ are Wigner matrices obeying Condition C1 for a sufficiently large $C_{0}$ which match to fourth order, and $M_{n}$ obeys the gap property, then $M^{\prime}_{n}$ also obeys the gap property. Using this and Theorem 16, one can then obtain Theorem 13 in full generality. Using Theorem 13, one can then deduce Theorem 11 from Theorem 17 by smoothly truncating in the $Q$ variables: see [104, §3.3].

It remains to establish Theorem 16 and Theorem 17. We begin with Theorem 17. To simplify the exposition slightly, let us assume that the matrices $M_{n},M^{\prime}_{n}$ are real symmetric rather than Hermitian. To reduce the number of parameters, we will also set $C_{0}:=1/c_{0}$.

by telescoping together $O(n^{2})$ estimates of this sort one can establish (40). (For swaps on the diagonal, one only needs an error term of $O(n^{-3/2+O(c_{0})})$, since there are only $O(n)$ swaps to be made here rather than $O(n^{2})$. This is ultimately why there are two fewer moment conditions on the diagonal than off it.)

is a (random) Hermitian matrix depending linearlyIf we were working with Hermitian matrices rather than real symmetric matrices, then one could either swap the real and imaginary parts of the $\xi_{ij}$ separately (exploiting the hypotheses that these parts were independent), or else repeat the above analysis with $t$ now being a complex parameter (or equivalently, two real parameters) rather than a real one. In the latter case, one needs to replace all instances of single variable calculus below (such as Taylor expansion) with double variable calculus, but aside from notational difficulties, it is a routine matter to perform this modification. on a real parameter $t$, with $A(0)$ being a Wigner matrix with one entry (and its adjoint) zeroed out, and $A^{\prime}(0)$ is the explicit elementary Hermitian matrix

We note the crucial fact that the random matrix $A(0)$ is independent of both $\xi_{pq}$ and $\xi^{\prime}_{pq}$. Note from Condition C1 that we expect $\xi_{pq},\xi^{\prime}_{pq}$ to have size $O(n^{O(c_{0})})$ most of the time, so we should (heuristically at least) be able to restrict attention to the regime $t=O(n^{O(c_{0})})$. If we then set

Suppose that we have Taylor expansions of the form

for all $t=O(n^{O(c_{0})})$ and $l=1,\ldots,k$, where the Taylor coefficients $c_{l,j}$ have size $c_{l,j}=O(n^{-j/2+O(c_{0})}$, and similarly for the quantities $Q_{i_{l}}(A(t))$. Then by using the hypothesis (39) and further Taylor expansion, we can obtain a Taylor expansion

for the function $F(t)$ defined in (42), where the Taylor coefficients $f_{j}$ have size $f_{j}=O(n^{-j/2+O(c_{0})})$. Setting $t$ equal to $\xi_{pq}$ and taking expectations, and noting that the Taylor coefficients $f_{j}$ depend only on $F$ and $A(0)$ and is thus independent of $\xi_{ij}$, we conclude that

and similarly for ${\mathbf{E}}F(\xi^{\prime}_{pq})$. If $\xi_{pq}$ and $\xi^{\prime}_{pq}$ have matching moments to fourth order, this gives (43). (Note that a similar argument also would give the Three Moment Theorem, as well as Proposition 12.)

It remains to establish (44) (as well as the analogue for $Q_{i_{l}}(A(t))$, which turns out to be analogous). We abbreviate $i_{l}$ simply as $i$. By Taylor’s theorem with remainder, it would suffice to show that

In particular, the eigenvalue $\lambda_{i}(A(t))$ is simple, which ensures that all quantities depend smoothly on $t$ (locally, at least).

To prove (45), one can use the classical Hadamard variation formulae for the derivatives of $\lambda_{i}(A(t))$, which can be derived for instance by repeatedly differentiating the eigenvector equation $A(t)u_{i}(A(t))=\lambda_{i}(A(t))u_{i}(A(t))$. The formula for the first derivative is

But recall from eigenvalue delocalisation (Corollary 8) that with overwhelming probability, all coefficients of $u_{i}(A(t))$ have size $O(n^{-1/2+o(1)})$; given the nature of the matrix (41), we can then obtain (45) in the $j=1$ case.

Now consider the $j=2$ case. The second derivative formula reads

(compare with the formula (27) for Dyson Brownian motion). Using eigenvalue delocalisation as before, we see with overwhelming probability that the numerator is $O(n^{-1+o(1)})$. To deal with the denominator, one has to exploit the hypothesis (46) and the local semicircle law (Theorem 7). Using these tools, one can conclude (45) in the $j=2$ case with overwhelming probability.

It turns out that one can continue this process for higher values of $j$, although the formulae for the derivatives for $\lambda_{i}(A(t))$ (and related quantities, such as $P_{i}(A(t))$ and $Q_{i}(A(t))$) become increasingly complicated, being given by a certain recursive formula in $j$. See for details.

Now we briefly discuss the proofThe argument here is taken from . In the case when the atom distributions are sufficiently smooth, one can also deduce this result from the level repulsion argument in [37, Theorem 3.5] and the eigenvalue rigidity estimate (15), and by using Theorem 17 one can extend the gap property to several other Wigner ensembles. However, this argument does not cover the case of Bernoulli ensembles, which is perhaps the most difficult case of Theorem 13 or Theorem 16. of Theorem 16. For sake of discussion we restrict attention to the bulk case ${\varepsilon}n\leq i\leq(1-{\varepsilon})n$; the changes needed to deal with the edge case are relatively minor and are discussed in . The objective here is to limit the probability of the event that the quantity $\lambda_{i+1}(A_{n})-\lambda_{i}(A_{n})$ is unexpectedly small. The main difficulty here is the fact that one is comparing two adjacent eigenvalues. If instead one was bounding $\lambda_{i+k}(A_{n})-\lambda_{i}(A_{n})$ for a larger value of $k$, say $k\geq\log^{C}n$ for a large value of $C$, then one could obtain such a bound from the local semicircle law (Theorem 7) without much difficulty. To reduce $k$ all the way down to $1$, the idea is to exploit the following phenomenon:

If $\lambda_{i+1}(A_{n})-\lambda_{i}(A_{n})$ is small, then $\lambda_{i+1}(A_{n-1})-\lambda_{i-1}(A_{n-1})$ is also likely to be small.

Here $A_{n-1}$ denotesStrictly speaking, one has to multiply $A_{n-1}$ also by $\frac{\sqrt{n-1}}{\sqrt{n}}$ to be consistent with our conventions for $M_{n}$ and $M_{n-1}$, although this factor turns out to make very little difference to the analysis. the top left $n-1\times n-1$ minor of $A_{n}$. This phenomenon can be viewed as a sort of converse to the classical Cauchy interlacing law

(cf. (12)), since this law clearly shows that $\lambda_{i+1}(A_{n})-\lambda_{i}(A_{n})$ will be small whenever $\lambda_{i+1}(A_{n-1})-\lambda_{i-1}(A_{n-1})$ is. In principle, if one iterates (generalisations of) the above principle $k=\log^{C}n$ times, one eventually reaches an event that can be shown to be highly unlikely by the local semicircle law.

To explain why we expect such a phenomenon to be true, let us expand $A_{n}$ as

that relates $\lambda_{i}(A_{n})$ to the various eigenvalues $\lambda_{j}(A_{n-1})$ of $A_{n-1}$ (ignoring for sake of discussion the non-generic case when one or more of the denominators in (48) vanish); compare with (16). Using concentration of measure tools (such as Talagrand’s inequality, see e.g. ), one expects $|u_{j}(A_{n-1})^{*}X|^{2}$ to concentrate around its mean, which can be computed to be $n(n-1)$. In view of this and, one expects the largest (and thus, presumably, the most dominant) terms in (48) to be the summands on the left-hand side when $j$ is equal to either $i-1$ or $i$. In particular, if $\lambda_{i+1}(A_{n})-\lambda_{i}(A_{n})$ is unexpectedly small (e.g. smaller than $n^{-c_{0}}$), then by (47) $\lambda_{i}(A_{n-1})-\lambda_{i}(A_{n})$ is also small. This causes the $j=i$ summand in (48) to (usually) be large and positive; to counterbalance this, one then typically expects the $j=i-1$ summand to be large and negative, so that $\lambda_{i}(A_{n})-\lambda_{i-1}(A_{n-1})$ is small; in particular, $\lambda_{i}(A_{n-1})-\lambda_{i-1}(A_{n-1})$ is small. A similar heuristic argument (based on (48) but with $\lambda_{i}(A_{n})$ replaced by $\lambda_{i+1}(A_{n})$ predicts that $\lambda_{i+1}(A_{n-1})-\lambda_{i}(A_{n-1})$ is also small; summing, we conclude that $\lambda_{i+1}(A_{n-1})-\lambda_{i-1}(A_{n-1})$ is also small, thus giving heuristic support to the above phenomenon.

One can make the above arguments more rigorous, but the details are rather complicated. One of the complications arises from the slow decay of the term $\frac{1}{\lambda_{j}(A_{n-1})-\lambda_{i}(A_{n})}$ as $i$ moves away from $j$. Because of this, a large positive term (such as the $j=i$ summand) in (48) need not be balanced primarily by the negative $j=i-1$ summand, but instead by a dyadic block $i-2^{k}\leq j<i-2^{k-1}$ of such summands; but this can be addressed by replacing the gap $\lambda_{i+1}(A_{n})-\lambda_{i}(A_{n})$ by a more complicated quantity (called the regularized gap in ) that is an infimum of a moderately large number of (normalised) gaps $\lambda_{i_{+}}(A_{n})-\lambda_{i_{-}}(A_{n})$. A more serious issue is that the numerators $|u_{j}(A_{n-1})^{*}X|$ can sometimes be much smaller than their expected value of $\sim n$, which can cause the gap at $A_{n-1}$ to be significantly larger than that at $A_{n}$. By carefully counting all the possible cases and estimating all the error probabilities, one can still keep the net error of this situation to be of the form $O(n^{-c})$ for some $c>0$. It is in this delicate analysis that one must rely rather heavily on the exponential decay hypothesis in Condition C0, as opposed to the polynomial decay hypothesis in Condition C1.

This concludes the sketch of Theorem 16. We remarked earlier that the extension to the edge case is fairly routine. In part, this is because the expected eigenvalue gap $\lambda_{i+1}(A_{n})-\lambda_{i}(A_{n})$ becomes much wider at the edge (as large as $n^{1/3}$, for instance, when $i=1$ or $i=n-1$), and so Theorem 16 and Theorem 13 becomes a weaker statement. There is however an interesting “bias” phenomenon that is worth pointing out at the edge, for instance with regard with the interlacing

of the very largest eigenvalues. On the one hand, the gap $\lambda_{n}(A_{n})-\lambda_{n-1}(A_{n})$ between the top two eigenvalues of $A_{n}$ is expected (and known, in many cases) to be comparable to $n^{1/3}$ on the average; see (51) below. On the other hand, from the semi-circular law one expects $\lambda_{n}(A_{n})$ to grow like $2n$, which suggests that $\lambda_{n}(A_{n})-\lambda_{n-1}(A_{n-1})$ should be comparable to $1$, rather than to $n^{1/3}$. In other words, the interlacing (49) is biased; the intermediate quantity $\lambda_{n-1}(A_{n-1})$ should be far closer to the right-most quantity $\lambda_{n}(A_{n})$ than the left-most quantity $\lambda_{n-1}(A_{n})$. This bias can in fact be demonstrated by using the fundamental equation (48); the point is that in the edge case (when $i$ is close to $n$) the term $-\lambda_{i}(A_{n})$ on the right-hand side plays a major role, and has to be balanced by $\lambda_{i}(A_{n})-\lambda_{i}(A_{n-1})$ being as small as $O(1)$.