Lectures on the local semicircle law for Wigner matrices

Introduction

These notes are based on lectures given by Antti Knowles at the conference États de la recherche en matrices aléatoires at the Institut Henri Poincaré in December 2014. In them, we state and prove the local semicircle law and give several applications to the distribution of eigenvalues and eigenvectors. We favour simplicity and transparency of arguments over generality of results. In particular, we focus on one of the simplest ensembles of random matrix theory: Wigner matrices.

A Wigner matrix is a Hermitian random matrix whose entries are independent up to the symmetry constraint, and have zero expectation and constant variance. This definition goes back to the seminal work of Wigner Wig , where he also proved the semicircle law, which states that the asymptotic eigenvalue distribution of a Wigner matrix is given with high probability by the semicircle distribution. Wigner matrices occupy a central place in random matrix theory, as a simple yet nontrivial ensemble on which many of the fundamental features of random matrices, such as universality of the local eigenvalue statistics and eigenvector delocalization, may be analysed. Moreover, many of the techniques developed for Wigner matrices, such as the ones presented in these notes, extend to other random matrix ensembles or serve as a starting point for more sophisticated methods.

The local semicircle law is a far-reaching generalization of Wigner’s original semicircle law, and constitutes the key tool for analysing the local distribution of eigenvalues and eigenvectors of Wigner matrices, and in particular in the study of the universality of Wigner matrices. Roughly, it states that the eigenvalue distribution is well approximated by the semicircle distribution down to scales containing only slightly more than one eigenvalue. The first instance of the local semicircle law down to optimal spectral scales was obtained by Erdős, Schlein, and Yau in ESY3 , following several previous results on larger spectral scales ESY2 ; Khor . Since then, the local semicircle law has been improved and generalized in a series of works ESY4 ; ESRY ; MR2981427 ; EYY2 ; EYYrigi ; EKYY1 ; EKYY4 ; CMS . The proof presented in these notes is modelled on the argument of Erdős, Knowles, Yau, and Yin from EKYY4 , which builds on the works ESY2 ; ESY3 ; ESY4 ; MR2981427 ; EYY2 ; EYYrigi of Erdős, Schlein, Yau, and Yin.

In order to keep these notes focused, for the applications we restrict ourselves to relatively simple consequences of the semicircle law: eigenvalue rigidity, eigenvector delocalization, and a four-moment comparison theorem for the local eigenvalue statistics. Further topics and applications, such as distribution of eigenvalues near the spectral edges, Dyson Brownian motion and its local relaxation time, distribution of eigenvectors, and spectral statistics of deformed matrix ensembles, are not covered here. For further reading on Wigner matrices, we recommend the books Mehta ; agz . Additional applications of the local semicircle law, in particular in the analysis of the local relaxation time of Dyson Brownian motion, are given in the survey Erd1 . In Section 11.4, we briefly outline applications of the local semicircle law to the analysis of eigenvectors and eigenvalues near the spectral edge.

In Section 2 we define Wigner matrices and state the local semicircle law, or local law for short. We also give two simple consequences of the local law: eigenvalue rigidity and complete eigenvector delocalization. Sections 3–7 are devoted to the proof of the local law. Section 3 collects some basic tools from linear algebra and probability theory that are used throughout the proof. Section LABEL:Sec:local_law_proof_abstract gives a detailed outline of the proof. In Section 5 we perform the first of two major steps of the proof: the weak local law, which yields control down to optimal scales but with non-optimal error bounds. In Section 6 we perform the second major step of the proof, which yields optimal error bounds and concludes the proof of the local law. The key estimate used to obtain the optimal error bounds is a fluctuation averaging result, whose proof is given in Section 7.

Having concluded the proof of the local law, in Sections LABEL:sec:local_law_small_scales–LABEL:sec:extension we draw some simple consequences. In Section LABEL:sec:local_law_small_scales we prove the semicircle law on small scales, which provides large deviation bounds on the number of eigenvalues in small intervals. In Section LABEL:sec:rig we prove eigenvalue rigidity, which provides large deviation bounds on the locations of individual eigenvalues. In Section LABEL:sec:extension we extend the estimates from the local law to arbitrary scales and distances from the spectrum.

In Section 11 we illustrate how to use the local law to obtain a four-moment comparison theorem for the local eigenvalue statistics, using the Green function comparison method from MR2981427 . We also sketch how to extend such comparison methods to the edge of the spectrum and to eigenvectors. Finally, in Section 12 we discuss further generalizations of the local law, and also other random matrix models for which local laws have been established.

The appendices contain some basic tools from linear algebra, spectral theory, and probability that are used throughout the notes, as well as some standard results on the semicircle distribution and the norm of Wigner matrices.

Pedagogical aspirations aside, in these notes we also give a coherent summary of the different guises of the local semicircle law that have proved useful in random matrix theory. They have all appeared, at least implicitly, previously in the literature; we take this opportunity to summarize them explicitly in Sections 2 and LABEL:sec:extension.

Conventions

The local law

The main tool in the study of the eigenvalues and eigenvectors of $H$ is the Green function or resolvent

Since we are ultimately interested in the eigenvalues and eigenvectors, it might seem that the Green function is an unnecessary distraction. In fact, however, the Green function is a much simpler and more stable object than the eigenvalues and eigenvectors. Using the Green function as the central object instead of eigenvalues and eigenvectors allows one to establish results whose direct proof (i.e. working directly on the eigenvalues and eigenvectors) is not feasible or at least much more complicated. We give an informal summary of the key features of the Green function that make it such a powerful tool.

The Green function contains the complete information about the eigenvalues and eigenvectors. Indeed, by spectral decomposition we have

Green functions form a basis of a powerful functional calculus: every “reasonable” function $f(H)$ of $H$ may be expressed as a superposition of Green functions. For instance, if $f$ is holomorphic in an open domain containing the spectrum of $H$, we have

where $\Gamma$ is a contour encircling the spectrum of $H$.

A more general and powerful functional calculus is provided by the Helffer-Sjöstrand functional calculus given in Appendix C.

The Green function is trivial to differentiate in $H$. For instance,

and higher order derivatives have analogous simple expressions. This is in stark contrast to the eigenvalues and eigenvectors, whose derivatives in the entries of $H$, while explicit, are notoriously unwieldy in higher orders.

A related observation is that the perturbation theory of Green functions is trivial. Let $\widetilde{H}=H+\Delta$ be a perturbation of $H$, and write $\widetilde{G}(z)\mathrel{\vbox{\hbox{.}\hbox{.}}}=(\widetilde{H}-z)^{-1}$. Then by iterating the resolvent identity $\widetilde{G}=G-G\Delta\widetilde{G}$ we get the resolvent expansion

Analogous perturbation series for the eigenvalues and eigenvectors are thoroughly unpleasant.

The Green function satisfies a host of very useful identities. One example is the resolvent expansion from (2.3). More sophisticated identities can be derived from Schur’s complement formula; see Lemma 3.5 below.

Finally, in the context of random matrix theory we take $\mathcal{X}=\{1,\dots,N\}$, $L=H$, and write $G_{ij}$ instead of $G(x,y)$. The spectral parameter $z$ plays a central role and is therefore often kept in the notation. Moreover, we do not distinguish the resolvent $(H-z)^{-1}$ from its entries $G_{ij}=(H-z)^{-1}_{ij}$, and refer to both as the Green function.

2 Local and global laws

We define the empirical eigenvalue distribution

For many matrix models $H$ one has $\mu\to\varrho$ as $N\to\infty$ (in some sense to be made precise), where $\varrho$ is a deterministic probability measure that does not depend on $N$. (For instance, for the Wigner matrices defined in Definition 2.2 below, $\varrho$ is the semicircle distribution (LABEL:defscl).) This convergence is best formulated in terms of Stieltjes transforms.

of the probability measures $\mu$ and $\varrho$. Note that $s(z)$ is random while $m(z)$ is deterministic.

The function $\theta_{\eta}$ is an approximate delta function as $\eta\downarrow 0$, with breadth $\eta$. We conclude that control of $\pi^{-1}\operatorname{Im}s(z)$ is tantamount to control of the empirical distribution $\mu$ smoothed out on the scale $\eta$. Hence, $\eta$ is called the spectral resolution.

Stieltjes transforms in particular provide a convenient way of studying convergence of (random) probability measures in distribution. The following lemma is proved in Appendix E.

Let $\mu\equiv\mu_{N}$ be a random probability measure, and $\varrho$ a deterministic probability measure. Let $s\equiv s_{N}$ and $m$ denote the Stieltjes transforms of $\mu$ and $\varrho$ respectively. Then

Note that in Lemma 2.1 the spectral parameter $z$ does not depend on $N$. Hence, recalling the discussion following (LABEL:6121414h44), we see that the convergence $s(z)\to m(z)$ has a spectral resolution of order one. A result of the form

(for instance in probability) is therefore called a global law.

A local law is a result that controls the error $s(z)-m(z)$ for all $z$ satisfying $\eta\gg N^{-1}$. In other words, a local law admits arguments $z$ that depend on $N$, so that the spectral resolution $\eta$ may be much smaller than the global scale $1$. We always require the spectral resolution to be bigger than $N^{-1}$. This restriction is necessary and its origin easy to understand. Since we assumed that $\lVert H\rVert\asymp 1$ and $H$ has $N$ eigenvalues, the typical separation of eigenvalues is of order $N^{-1}$. Individual eigenvalues are expected to fluctuate about their mean locations, so that the random quantity $s(z)$ can only be expected to be close to the deterministic quantity $m(z)$ if some averaging mechanism ensures that $s(z)$ depends strongly on a large number of eigenvalues. This means that the spectral resolution $\eta$ has to be larger than the typical eigenvalue spacing $N^{-1}$. See Figure LABEL:Fig:Spectral_Resolution for an illustration of the spectral scale $\eta$ and the approximation from (LABEL:6121414h44).

For most applications to the distribution of the eigenvalues and eigenvectors, control of just $s(z)=N^{-1}\operatorname{Tr}G(z)$ is not enough, and one needs control of the Green function $G(z)$ regarded as a matrix. The need for such a stronger control is obvious if we are interested in the eigenvectors of $H$ (recall the spectral decomposition from (2.1)). However, perhaps surprisingly, to understand the distribution of individual eigenvalues we also need to control the individual entries of $G$; see Section 11 for more details.

We shall see that, at least for Wigner matrices, the matrix $G(z)$ is close (in some sense to be made precise) to $m(z)$, a multiple of the identity matrix.

3 The local law for Wigner matrices

From now we focus on the case where $H$ is a Wigner matrix.

A Wigner matrix, or Wigner ensemble, is a Hermitian $N\times N$ matrix $H=H^{*}$ whose entries $H_{ij}$ satisfy the following conditions.

The upper-triangular entries $(H_{ij}\mathrel{\vbox{\hbox{.}\hbox{.}}}1\leqslant i\leqslant j\leqslant N)$ are independent.

The random variables $\sqrt{N}H_{ij}$ are bounded in any $L^{p}$ space, uniformly in $N,i,j$.

In the literature, various other conditions on the tails of the entries $\sqrt{N}H_{ij}$ have been used, ranging from sub-Gaussian tails to merely the existence of the second moment in (ii). The assumption (iii) can be relaxed (for instance by truncation), but we shall not pursue this direction in these notes.

This choice of the normalization $N^{-1}$ in (ii) ensures that $\lVert H\rVert\asymp 1$ as required above. A simple heuristic way to convince ourselves that this is the right normalization is to compute the average square distance of an eigenvalue from the origin:

Let $X$ be an $N\times N$ matrix with i.i.d. real standard normal entries. Then the Gaussian orthogonal ensemble (GOE) is defined as

Similarly, let $Y$ be an $N\times N$ matrix with i.i.d. complex standard normal entries. (This means that $\operatorname{Re}Y_{ij}$ and $\operatorname{Im}Y_{ij}$ are independent standard normals.) Then the Gaussian unitary ensemble (GUE) is defined as

Next, we define the semicircle distribution

It is not hard to check (see Lemma LABEL:lem:stieltjessclformula) that the Stieltjes transform (2.6) of the semicircle distribution $\varrho$ is

The following global law, illustrated by Figure LABEL:Fig:Global_Law, is well known (see e.g. bai-silver-book ; agz ). (It will also follow from the local law, Theorem LABEL:Th3 below.)

In order to state the local law, we use the following notion of high-probability bounds that was introduced in EKYfluc . It provides a simple way of systematizing and making precise statements of the form “$X$ is bounded with high probability by $Y$ up to small powers of $N$”. As we shall see, it is a very convenient way of wrapping various details of convergence in high probability, such as the low-probability exceptional events, into an object that very rarely needs to be unwrapped.

be two families of nonnegative random variables, where $U^{(N)}$ is a possibly $N$-dependent parameter set.

We say that $X$ is stochastically dominated by $Y$, uniformly in $u$, if for all (small) $\varepsilon>0$ and (large) $D>0$ we have

for large enough $N\geqslant N_{0}(\varepsilon,D)$. The stochastic domination is always uniform in all parameters (such as matrix indices and spectral parameters $z$) that are not explicitly fixed.

If $X$ is stochastically dominated by $Y$, uniformly in $u$, we use the notation $X\prec Y$. Moreover, if for some complex family $X$ we have $\lvert X\rvert\prec Y$ we also write $X=O_{\prec}(Y)$.

For example, it is easy to check that $|H_{ij}|\prec N^{-1/2}$. Note that this notation implicitly means that $\prec$ is uniform in the indices $i,j$.

We may now state the main result of these notes.

≲Th3 Let $H$ be a Wigner matrix. Fix $\tau>0$ and define the domain

For $\lvert E\rvert\leqslant 2$, both estimates (2.14) and (2.15), as encapsulated by the respective error parameters $(N\eta)^{-1}$ and $\Psi$, are optimal up to the details in the definition of $\prec$. For $\lvert E\rvert>2$ the optimal bounds are better than those of Theorem LABEL:Th3. Remarkably, these optimal bounds for $\lvert E\rvert>2$ are essentially a consequence of the weaker ones from Theorem LABEL:Th3; see Theorems LABEL:thm:ext1 and 10.3 below for the precise statements.

To help the interpretation of the error parameter $\Psi$, we consider the cases where $E$ is in the bulk $(-2,2)$ of the spectrum and at the edge $\{-2,2\}$ of the spectrum. Suppose first that $E\in(-2,2)$ is fixed in the bulk. Then we easily find $\operatorname{Im}m(z)\asymp 1$ for $\eta\in[N^{-1},1]$. Hence, the first term of (2.16) dominates and we have $\Psi(z)\asymp(N\eta)^{-1/2}$, which is much smaller than $\operatorname{Im}m(z)$ for $\eta\gg N^{-1}$. Note that the scale $N^{-1}$ is the typical separation of the eigenvalues in the bulk, as can be seen for instance by choosing $i\in[cN,(1-c)N]$ in (2.19) below, for some constant $c>0$.

On the other hand, if $E=2$ is at the edge, we find $\operatorname{Im}m(z)\asymp\sqrt{\eta}$. We conclude that the first term of (2.16) dominates over the second if $\eta\gg N^{-2/3}$ and the second over the first if $\eta\ll N^{-2/3}$. Note that the threshold $N^{-2/3}$ is precisely the typical separation of the eigenvalues near the edge, as can be seen for instance by choosing $i\leqslant C$ in (2.19) below, for some constant $C>0$. Hence, we conclude that at the edge $\Psi(z)$ is much smaller than $\operatorname{Im}m(z)$ provided that $\eta\gg N^{-2/3}$. See Figure LABEL:Fig:Local_Law.

4 Applications of Theorem LABEL:Th3

We now state some important consequences of Theorem LABEL:Th3. The first one gives the semicircle law on small scales. In Lemma 2.1 we saw that control of $s(z)-m(z)$ for fixed $z$ yields control of $\mu-\varrho$ on large scales. Using the strong local control on $s(z)-m(z)$ from Theorem LABEL:Th3, we may correspondingly obtain strong bounds on the local convergence of $\mu$ to $\varrho$.

We postpone the proof of Theorem LABEL:thm:llsc to Section LABEL:sec:local_law_small_scales. The second consequence of Theorem LABEL:Th3 is an eigenvalue rigidity estimate, which gives large deviation bounds on the locations of the eigenvalues. Eigenvalue rigidity for Wigner matrices was first established in EYYrigi , using the optimal error bound from (2.14) that was first obtained there.

For $i=1,\dots,N$ we define the typical location of $\lambda_{i}$ as the quantile $\ga_{i}$ satisfying

It is easy to see that the typical eigenvalue locations $\gamma_{i}$ satisfy

and by symmetry a similar estimate holds for $i\geqslant N/2$. Note that the right-hand side of (2.19) is characteristic of the square root decay of the density of $\varrho$ near the boundary of its support.

In particular, the extreme eigenvalues $\lambda_{1}$ and $\lambda_{N}$ are with high probability located at a distance of order at most $N^{-2/3}$ from their typical locations. Moreover, the bulk eigenvalues, $\lambda_{i}$ satisfying $\lvert i\rvert\asymp\lvert N-i\rvert\asymp N$, are with high probability located at a distance of order at most $N^{-1}$ from their typical locations. The eigenvalue rigidity is a manifestation of a strong repulsion between the eigenvalues, which tend to form a rather rigid “jelly” where neighbouring eigenvalues avoid getting too close and are therefore pinned down by the influence of their neighbours. In contrast, if $\lambda_{1},\dots,\lambda_{N}$ were i.i.d. random variables distributed according to the semicircle distribution, the global semicircle law for $s-m$ would remain true, but a standard exercise in order statistics shows that in this case $\lambda_{i}$ would typically fluctuate on the scale $N^{-1/2}$. This is much larger than the scale $N^{-1}$ from Theorem 2.9. Correspondingly, for this i.i.d. model we would expect to find gaps of order $N^{-1/2}$, and the error term in Theorem LABEL:thm:llsc would have to be replaced with $O_{\prec}(N^{-1/2})$. See Figures LABEL:Fig:llsc and LABEL:Fig:Rigidity for an illustration of this rigidity.

We postpone the proof of Theorem 2.9 to Section LABEL:sec:rig. A very easy corollary of Theorems LABEL:Th3 and 2.9 is the complete delocalization of eigenvectors, illustrated in Figure LABEL:Fig:Eigenvectors. The complete delocalization of eigenvectors of Wigner matrices was first obtained in ESY2 as a corollary of the local law on optimal scales proved there.

Since $\tau>0$ was arbitrary, the conclusion follows. ∎

The notion of stochastic domination from Definition 2.5 greatly simplifies many statements and arguments. On the other hand, the specific notion of high-probability bounds that it yields is not as sharp as possible: the factors of $N^{\varepsilon}$ can be improved to powers of $\log N$ and the polynomial error probabilities $N^{-D}$ can be improved to exponential error probabilities. Such extensions may in fact be obtained by a routine but tedious extension of the arguments presented in these notes. We do not pursue this further.

The local law has many further applications, for instance to the universality of the local eigenvalue statistics and the distribution of eigenvectors; see Section 11 below for more details.

5 Sketch of the proof of Theorem LABEL:Th3

We conclude this section with a sketch of the proof of Theorem LABEL:Th3, which is the main content of these notes. A more detailed presentation of the main steps of the proof is given in Section LABEL:Sec:local_law_proof_abstract.

The starting point of the proof is Schur’s complement formula

where $G^{(i)}$ denotes the Green function of the matrix obtained from $H$ by removing the $i$-th row and column. The coefficients $G_{kl}^{(i)}$ are independent of the family $(H_{ik})_{k=1}^{N}$, so that we may apply large deviation estimates to the sum, finding that it is in fact close with high probability to its expectation with respect to the randomness in the $i$-th column, which is in turn close to $\frac{1}{N}\sum_{k}G_{kk}=s$.

We split the right-hand side of (LABEL:SPSFintroShort) into a leading term and a random error term, which yields after multiplication of both sides by $G_{ii}$

Taking $\eta\geqslant 1$, averaging over $i$, and estimating the random error term, we get

As $m(z)$ is a solution of (LABEL:3121417h382Short) with the right-hand side set to zero, a stability analysis of (LABEL:3121417h382Short) yields an estimate of $s(z)-m(z)$ for $\eta\geqslant 1$. This is the global semicircle law. Going back to (LABEL:SPSFintroShort) and using further analogous formulas for the off-diagonal entries, we obtain weak control of the entries $G_{ij}-m\delta_{ij}$ on the global scale $\eta\geqslant 1$.

In order to obtain (2.15) with the optimal error bound $\Psi$, we use a fluctuation averaging argument. Roughly, it says that the random variables $1/G_{ii}$, when centred with respect to the randomness of the $i$-th column of $H$, are not too strongly dependent, and hence their average is typically much smaller than any one of them.

Proof of Theorem LABEL:Th3 (a): preliminaries

In this preliminary section we collect the main tools of the proof.

We consider general matrices whose indices lie in subsets of $\{1,\dots,N\}$. For $T\subset\{1,\dots,N\}$ we define $H^{(T)}$ as the $(N-\lvert T\rvert)\times(N-\lvert T\rvert)$ matrix

Moreover, we define the Green function of $H^{(T)}$ through

When $T=\{a\}$, we abbreviate $(\{a\})$ by $(a)$ in the above definitions; similarly, we write $(ab)$ instead of $(\{a,b\})$.

Note that in the minor $H^{(T)}$ it is important to keep the original values of the matrix indices, and not to identify $\{1,\dots,N\}\setminus T$ with $\{1,\dots,N-\lvert T\rvert\}$.

Let $X\equiv X(H)$ be a random variable. For $i\in\{1,\dots,N\}$ we define the operations $P_{i}$ and $Q_{i}$ through

The following lemma collects basic bounds on $m$. In order to state it, we define the distance to the spectral edge

The proof is an elementary exercise using (2.11) and (2.12). ∎

The following lemma collects properties of stochastic domination $\prec$. Roughly, it states that $\prec$ satisfies the usual arithmetic properties of order relations. We shall use it tacitly throughout the following.

Suppose that $X(u,v)\prec Y(u,v)$ uniformly in $u\in U$ and $v\in V$. If $\lvert V\rvert\leqslant N^{C}$ for some constant $C$ then

Suppose that $X_{1}(u)\prec Y_{1}(u)$ uniformly in $u$ and $X_{2}(u)\prec Y_{2}(u)$ uniformly in $u$. Then $X_{1}(u)X_{2}(u)\prec Y_{1}(u)Y_{2}(u)$ uniformly in $u$.

The following resolvent identities form the backbone of all of our calculations. The idea behind them is that a Green function entry $G_{ij}$ depends strongly on the $i$-th and $j$-th columns of $H$, but weakly on all other columns. The first identity determines how to make a Green function entry $G_{ij}$ independent of the randomness in the $k$-th row, where $k\neq i,j$. The second identity expresses the dependence of a Green function entry $G_{ij}$ on the matrix elements in the $i$-th or in the $j$-th column of $H$.

For any Hermitian matrix $H$ and $T\subset\{1,\dots,N\}$ the following identities hold. If $i,j,k\notin T$ and $i,j\neq k$ then

It may be proved by applying the resolvent identity to $G-G^{*}$, or, alternatively, by spectral decomposition:

Finally, we record the following large deviation bounds.

for all $p$ with some constants $\mu_{p}$.

Suppose that \bigl{(}{\sum_{i}\lvert b_{i}\rvert^{2}}\bigr{)}^{1/2}\prec\Psi. Then $\sum_{i}b_{i}X_{i}\prec\Psi$.

Suppose that \bigl{(}{\sum_{i\neq j}\lvert a_{ij}\rvert^{2}}\bigr{)}^{1/2}\prec\Psi. Then $\sum_{i\neq j}a_{ij}X_{i}X_{j}\prec\Psi$.

Suppose that \bigl{(}{\sum_{i,j}\lvert a_{ij}\rvert^{2}}\bigr{)}^{1/2}\prec\Psi. Then $\sum_{i,j}a_{ij}X_{i}Y_{j}\prec\Psi$.

If all of the above random variables depend on an index $u$ and the hypotheses of (i) – (iii) are uniform in $u$, then so are the conclusions.

Outline of the proof of Theorem LABEL:Th3

The diagonal entries of $G$ can be written using Schur’s complement formula as

Since the coefficients $G^{(i)}_{kl}$ in (LABEL:SPSFintro) are independent of the entries $(H_{ik})_{k=1}^{N}$, we can condition on $H^{(i)}$ and apply Lemma 3.6 to find that the sum on the right-hand side of (LABEL:SPSFintro) is with high probability close to its $P_{i}$-expectation, $\frac{1}{N}\sum_{k}^{(i)}G_{kk}^{(i)}$. Using Lemma 3.5 we can get rid of the upper index $(i)$ up to a small error term, and find that the sum on the right-hand side of (LABEL:SPSFintro) is with high probability close to $s$.

In order to quantify these errors, we introduce the random $z$-dependent error parameter

Then using large deviation estimates as outlined above as well as the Ward identity (3.6), we find that if either $\eta\geqslant 1$ or $\Lambda\leqslant N^{-\tau/10}$, then (LABEL:SPSFintro) reads

Combined with analogous arguments applied to the off-diagonal entries starting from (3.5), we obtain the estimate

on the individual entries of $G$. Note that the diagonal entries are compared to the empirical quantity $s$ instead of the deterministic quantity $m$.

In the next step, we compare $s$ to $m$. Rewriting (LABEL:SPSFintrobis) as

Recall from (2.12) that $m$ solves the same equation as (4.5) without the error term on the right-hand side. Thus, concluding estimating $s-m$ from (4.5) in terms of the error $O_{\prec}(\Psi_{\Theta})$ involves a stability analysis of the quadratic equation (4.5).

If $\eta\geqslant 1$ we have $\Psi_{\Theta}\leqslant CN^{-1/2}$, and it is then not hard to deduce that $\lvert s-m\rvert\prec N^{-1/2}$, so that (4.3) implies $\Lambda\prec N^{-1/2}$. Here the stability analysis of (4.5) is simple because the two solutions of (4.5) are well separated.

The bootstrapping is started at $z_{0}$ for which the simple analysis of (c) applies.

To explain the bootstrapping, suppose that $\Lambda(z_{k})\prec(N\eta)^{-1/4}$ holds at $z_{k}$. Then we use the trivial Lipschitz continuity of $\Lambda$ with Lipschitz constant $N^{2}$ and the estimate $\lvert z_{k+1}-z_{k}\rvert=N^{-3}$ to deduce that with high probability $\Lambda\leqslant N^{-\tau/10}$ at $z_{k+1}$. This is the a priori assumption needed to obtain the estimates (LABEL:SPSFintrobis) and (4.3) at $z_{k+1}$. Hence, we also obtain (4.5) at $z_{k+1}$. In order to obtain a bound on $\lvert s-m\rvert$ from (4.5) and hence complete the induction step, we need to perform a stability analysis of (4.5). For small $\eta$ and $E$ near the spectral edge, this stability analysis requires some care, because the two solutions of (4.5) can be close. This completes the induction step.

The key tool behind the proof of the optimal error bound is a fluctuation averaging argument, which states that the error term in (LABEL:3121417h38) becomes much smaller after averaging over $i$. Thus, the optimal error in (9.2) is in fact much smaller than in (LABEL:3121417h38). The main work behind this improvement is to estimate averages of the form $\sum_{i=1}^{N}X_{i}$ where $X_{i}\mathrel{\vbox{\hbox{.}\hbox{.}}}=Q_{i}\frac{1}{G_{ii}}$ has (by definition) expectation zero. Clearly, if the variables $X_{i}$ were all equal then the averaging would not change anything, and if they were all independent we would gain a factor $N^{-1/2}$ from the averaging. In fact, with the choice $X_{i}=Q_{i}\frac{1}{G_{ii}}$ neither is true, as the variables $X_{i}$ are obviously not equal but they are nevertheless strongly correlated. As it turns out, the averaging yields a gain of order $(N\eta)^{-1/2}$, so that the variables $X_{i}$ are almost uncorrelated for $\eta=1$ and almost equal for $\eta\approx N^{-1}$.

Proof of Theorem LABEL:Th3 (b): weak local law

The conclusion of Theorem LABEL:Th3 may be regarded as consisting of two separate achievements on the quantities $G_{ij}-m\delta_{ij}$ and $s-m$: first, control for small values of $\eta$; second, optimal error bounds. These two achievements in fact entail separate difficulties in the proof, and we correspondingly separate the proof into two parts. The weak local law presented in this section pertains to the first achievement.

In this section we state and prove the weak law. The central quantity is the random $z$-dependent error parameter

The rest of this section is devoted to the proof of Proposition LABEL:prop1. In addition to $\Lambda$, we shall need the additional error parameters

Our starting point is Schur’s complement formula (see Lemma A.1), which we write as

The claim now follows using (LABEL:SPSF). ∎

The strategy behind the proof of Proposition LABEL:prop1 is a self-consistent multiscale approach, which involves a bootstrapping from the large scale $\eta\geqslant 1$ down to the small scale $\eta=N^{-1+\tau}$. The bootstrapping hypothesis will be the event $\phi=1$, where we defined the $z$-dependent indicator function

The following result gives trivial bounds on entries of $G$ on the event $\phi=1$.

uniformly for $i,j\notin T\subset\{1,\dots,N\}$ satisfying $\lvert T\rvert\leqslant p$.

The proof follows using (3.2) and a repeated application of (3.4), whose details we leave to the reader. ∎

The following lemma contains the key a priori estimates used to perform the bootstrapping. Note that the assumptions for the estimates are either $\eta\geqslant 1$ (start of bootstrapping) or $\phi=1$ (bootstrapping assumption used for iteration).

We begin with $Z_{i}$ under the bootstrapping assumption $\phi=1$. We split

Using Lemmas 3.6 and 5.3 we estimate the first term of (5.6) as

where in the last step we used (3.3) to estimate $\Psi_{\Theta}\geqslant cN^{-1/2}$.

Next, using Lemma 3.6 we estimate the second term of (5.6) as

Here the second step follows from the Ward identity (3.6) applied to the matrix $H^{(i)}$. Using (3.4) and Lemma 5.3 we therefore conclude

Next, from Lemma 5.3 we get the trivial bound

In order to estimate $\Lambda_{*}$, we take $i\neq j$ and use (3.5) twice to get

We estimate the second term using Lemma 3.6 and the identity (3.6) (applied to $H^{(ij)}$) according to

Using the definition of $\prec$, we deduce that

Plugging (5.10) into (5.7) and (5.8) concludes the proof of the term $\phi$ in (LABEL:7).

What remains is the estimate (LABEL:8). From Lemma LABEL:lem11 and (LABEL:7) we get

We emphasize here the essential role played by the identity (3.6) in the proof. It is the source of the factors $(N\eta)^{-1}$ in our error bounds. Using it, we can estimate the sum over $N$ Green function entries by $\eta^{-1}$ times a Green function entry. Since $\eta^{-1}\ll N$, this is a nontrivial gain. This gain is responsible not only for the optimal error bounds for $\Lambda$ but also for the self-improving mechanism in the estimation of $\Lambda$ that allows us to bootstrap in $\eta$.

The following elementary lemma is used to estimate $s-m$. It may be regarded as a quantitative stability result for the equation (2.12).

The following lemma starts the bootstrapping at $\eta\geqslant 1$.

Let $\eta\geqslant 1$. From (LABEL:7) an Lemma 3.3 we get $\Lambda_{*}\prec N^{-1/2}$. What remains therefore is the estimate of $G_{ii}-m$. By Lemmas LABEL:lem11 and LABEL:lem12, we have

We may now come to heart of the proof of Proposition LABEL:prop1: the self-consistent multiscale bootstrapping from large to small $\eta$. If all error estimates were deterministic, we could do a standard continuity argument by choosing a continuous path $\eta(t)=1-t$. However, owing to the stochastic nature of our estimates, the bootstrapping has to be done in a finite number of steps. At each step we lose some probability, which imposes an upper bound on the number of allowed steps. On the other hand, the steps have to be small enough to be able to carry over information from one step to the next using continuity. At each step, the deterioration of the error probabilities has to be tracked carefully. Roughly, at each step we lose an additive factor $N^{-D}$ in the error probabilities, which means that we can perform an order $N^{C}$ steps for any fixed constant $C$. Using the Lipschitz continuity of all error parameters, it turns out to be enough to perform steps of size $N^{-3}$. Hence, for the stochastic continuity argument that underlies the self-consistent multiscale approach, we replace the purely topological notions of a continuous path and continuous error parameters with the quantitative notions of a lattice and Lipschitz continuous error parameters.

Fix $\varepsilon\in(0,\tau/16)$ and $D>0$. Set $\delta_{k}\mathrel{\vbox{\hbox{.}\hbox{.}}}=(N\eta_{k})^{-1/2}$ and define the events

Note that, as $k$ increases, $\eta_{k}$ decreases and $\delta_{k}$ increases. Hence, $\delta_{k}<N^{-2\varepsilon}(\kappa+\eta_{k})$ for all $k<K$.

where we also used that $\operatorname{Im}m+\phi\Theta\leqslant C$. Plugging this into Lemma LABEL:lem11, averaging over $i$, and invoking Lemma LABEL:lem13 yields

On the other hand, by Lipschitz continuity, on $\Omega_{k-1}$ we have

where in the last step we used that $\delta_{k}\leqslant N^{-2\varepsilon}(\kappa+\eta_{k})$. Therefore, on $\Omega_{k-1}$ we have

Moreover, using Lemma LABEL:lem12 we find

where in the first step we used that $\phi(z_{k})=1$ on $\Xi_{k-1}$ and the general estimate $\Lambda\leqslant\Lambda_{*}+\max_{i}\lvert G_{ii}-s\rvert+\Theta$, and in the second step we used the definitions of $\Omega_{k}$ and $\delta_{k}$. We conclude that

Summarizing, defining $B_{k}\mathrel{\vbox{\hbox{.}\hbox{.}}}=\Omega_{k}\cap\Xi_{k}$, we get from (5.15) and (5.16) that

Case 2: k⩾K𝑘𝐾k\geqslant K

In this case the argument is similar but somewhat easier, since there is no need to use the assumption $\Omega_{k-1}$. Then the argument is similar, but easier: there is no need to track $\Theta$ (so that we do not need the events $\Omega_{k}$). If

where we used Lemma LABEL:lem13. Using (5.14) and Lemma LABEL:lem12 we therefore deduce that

for all $k$. Since $\varepsilon>0$ and $D$ were arbitrary, the claim follows. ∎

Proof of Theorem LABEL:Th3 (c): optimal error bounds

In this section we complete the proof of Theorem LABEL:Th3 by improving the error bounds from Proposition LABEL:prop1 to optimal ones. The main observation is that the equation for $s$ of the form (5.13) arises from an averaging over $i$. When deriving (5.13) (and its analogue for smaller $\eta$), we simply estimated the average $\frac{1}{N}\sum_{i}Y_{i}$ by $\max_{i}\lvert Y_{i}\rvert$. (Recall the definition (5.2).) In fact, the random variables $Y_{i}$ have a small expectation, so that their average should be smaller than the typical size of each individual variable. If they were independent, we would gain a factor $N^{-1/2}$ by a trivial concentration result. However, they are not independent. In fact, for small $\eta$ different $Y_{i}$ are strongly correlated, and one typically has

The upper bound corresponds to fully correlated variables, and the lower bound to uncorrelated variables. For general $\eta$, the variables $Y_{i}$ are in between these two extremes. The extreme cases are reached for $\eta\approx N^{-1}$ (almost fully correlated) and $\eta\approx 1$ (almost uncorrelated, in fact almost independent); see Remark 6.3 below for more details.

The key result that allows us to obtain optimal bounds on the average $\frac{1}{N}\sum_{i}Y_{i}$ is the following fluctuation averaging result. Recall the definitions of $P_{i}$ and $Q_{i}$ from Definition 3.2.

≲lem17 Under the assumptions of Proposition LABEL:prop16, the error terms $Y_{i}$ defined in Lemma LABEL:lem11 satisfy

From Schur’s complement formula (LABEL:SPSF) we get

so that $Y_{i}=A_{i}+Q_{i}1/G_{ii}$. From the definition of $A_{i}$ in Lemma LABEL:lem11 we obtain $A_{i}=O_{\prec}(\Phi^{2})$, where we used Proposition LABEL:prop1 and (3.2). The claim now follows from Proposition LABEL:prop16. ∎

Since $A_{i}=O_{\prec}(\Phi^{2})$ even without averaging, we find that the important part of $Y_{i}$ is $X_{i}\mathrel{\vbox{\hbox{.}\hbox{.}}}=Q_{i}\frac{1}{G_{ii}}$. Suppose for simplicity that we are in the bulk, i.e. $E\in[-2+c,2-c]$ for some constant $c>0$. As evidenced by Theorem LABEL:Th3, $X_{i}$ is typically of size $(N\eta)^{-1/2}$ in the bulk. Moreover, again by Theorem LABEL:Th3, we have the bound $\Lambda_{*}\prec\Phi$ with $\Phi\mathrel{\vbox{\hbox{.}\hbox{.}}}=(N\eta)^{-1/2}$. Thus, we find that the effect of the averaging on $X_{i}$ is to multiply it by a factor $(N\eta)^{-1/2}$. We conclude that for $\eta\approx 1$, the average $\frac{1}{N}\sum_{i}X_{i}$ is smaller than $X_{i}$ by a factor $N^{-1/2}$, which corresponds to the behaviour of independent random variables $X_{1},\dots,X_{N}$. In contrast, for $\eta\approx N^{-1}$, the average $\frac{1}{N}\sum_{i}X_{i}$ is of the same size as $X_{i}$, which corresponds to the behaviour of fully correlated random variables $X_{1}=\cdots=X_{N}$.

Averaging over $i$ and using that $\lvert s^{2}G_{ii}\rvert^{-1}\prec 1$, we get

This is the desired perturbed quadratic equation for $s$.

Using the initial bound $\lvert s(z_{0})-m(z_{0})\rvert\leqslant\mathcal{E}_{\sigma}(z_{0})$ and the estimates

where in the last step we used Lemma 3.3. Note that the second estimate is in general wasteful. It turns out to be optimal for $E\in$, but if $E$ is away from the limiting spectrum $$, it can be improved. We shall return to this point in Lemma 9.2 below.

In conclusion, we have shown for any $\sigma\in[1/4,1]$ that

Starting from $\sigma=1/4$ from Proposition LABEL:prop1 and iterating (6.7) a bounded number of times, we get $\Theta\prec(N\eta)^{-1}$. (Note that the number of iterations is independent of $N$; it depends only on the constant $\varepsilon$ in the definition of $\prec$, which is arbitrary but fixed.) This concludes the proof of (2.14). Finally, (2.15) follows from (2.14) and the estimates (LABEL:7) and (LABEL:8). This concludes the proof of Theorem LABEL:Th3.

Fluctuation averaging: proof of Proposition LABEL:prop16

The first instance of the fluctuation averaging mechanism appeared in EYY2 for the Wigner case. A different proof (with a better bound on the constants) was given in EYYrigi . A conceptually streamlined version of the original proof was extended to sparse matrices EKYY1 and to sample covariance matrices PY1 . Finally, an extensive analysis in EKYfluc treated the fluctuation averaging of general polynomials of Green function entries and identified the order of cancellations depending on the algebraic structure of the polynomial. Moreover, in EKYfluc an additional cancellation effect was found for the quantity $Q_{i}|G_{ij}|^{2}$. These improvements played a key role in obtaining the diffusion profile for the Green function of band matrices. The version we present here is based on the greatly simplified proof given in EKYY4 .

We start with a simple lemma which summarizes the key properties of $\prec$ when combined with expectation. Note that if $X$ and $Y$ are deterministic, $X\,\prec\,Y$ from Definition 2.5 simply means that for each $\varepsilon>0$, we have for large enough $N$ and all $u$ that $X^{(N)}(u)\,\leqslant\,N^{\varepsilon}Y^{(N)}(u)$.

Moreover, with $P_{i}$ and $Q_{i}$ as in Definition 3.2, we have

Finally, if $X\equiv X(u)$ and $\Phi\equiv\Phi(u)$ depend on some parameter $u$ and any of the above hypothesis is uniform in $u$, then so is the corresponding conclusion.

Choosing $n$ large enough (depending on $\varepsilon$) proves the implication “$\Longleftarrow$” of (LABEL:eq:stoch_domination). Conversely, if $X\prec\Phi$ then for any $D>0$ we get

Using $\Phi\geqslant N^{-C}$ and choosing $D$ large enough, we obtain the implication “$\Longrightarrow$” of (LABEL:eq:stoch_domination) for $n=1$. The same implicitation for arbitrary $n$ follows from the fact that $X\prec\Phi$ implies $X^{n}\prec\Phi^{n}$ for any fixed $n$. Moreover, (7.2) follows using (LABEL:eq:stoch_domination) and Jensen’s inequality for conditional expectations. The final claim about uniformity is trivial. ∎

We shall apply Lemma 7.1 to the entries of $G$. In order to verify its assumptions, we record the following bounds.

Moreover, we have the rough bounds \bigl{\lvert}G_{ij}^{(T)}\bigr{\rvert}\leqslant N and

for any $\varepsilon>0$ and $N\geqslant N_{0}(n,\varepsilon)$.

The bounds (7.3) follow easily by a repeated application of (3.4), the estimate $\Lambda\prec N^{-c}$ from Proposition LABEL:prop1, and the lower bound in (3.2). The deterministic bound \bigl{\lvert}G_{ij}^{(T)}\bigr{\rvert}\leqslant N follows immediately from $\eta\geqslant N^{-1}$ by definition of a spectral domain.

In order to prove (7.4), we use Schur’s complement formula (LABEL:SPSF) applied to $1/G_{ii}^{(T)}$, where the expectation is estimated using (iii) of Definition 2.2 and \bigl{\lvert}G_{ij}^{(T)}\bigr{\rvert}\leqslant N. This gives

where in the second step we used Lemma 7.2. This concludes the proof of (7.5).

Abbreviate $X_{k}\mathrel{\vbox{\hbox{.}\hbox{.}}}=Q_{k}(G_{kk})^{-1}$. We shall estimate $N^{-1}\sum_{k}X_{k}$ in probability by estimating its $p$-th moment by $\Phi^{2p}$, from which the claim will easily follow using Markov’s inequality. Before embarking on the estimate for arbitrary $p$, we illustrate its idea by estimating the variance

Using Lemma 7.1, we find that the first term on the right-hand side of (7.6) is $O_{\prec}(N^{-1}\Phi^{2})=O_{\prec}(\Phi^{4})$, where we used the estimate (6.2). Let us therefore focus on the second term of (7.6). Using the fact that $k\neq l$, we apply (3.4) to $X_{k}$ and $X_{l}$ to get

We multiply out the parentheses on the right-hand side. The crucial observation is that if the random variable $Y$ is $H^{(i)}$-measurable then

Hence out of the four terms obtained from the right-hand side of (7.7), the only nonvanishing one is

After this pedagogical interlude we move on to the full proof. Fix some even integer $p$ and write

The idea behind this splitting is to use (3.4) on one entry of $A$; the first term on the right-hand side of (3.4) gives rise to $w_{0}(A)$ and the second to $w_{1}(A)$. The precise definition of the algorithm applied to $A\in\mathcal{A}$ is as follows.

If all factors of $A$ are maximally expanded or $d(A)\geqslant p+1$ then stop the expansion of $A$. In other words, the algorithm cannot be applied to $A$ in the future.

Otherwise choose some (arbitrary) factor of $A$ that is not maximally expanded. If this entry is off-diagonal, $G^{(T)}_{xy}$, write

(This algorithm contains some arbitrariness in the choice of the factor of $A$ to be expanded. It may be removed for instance by first fixing some ordering of all Green function entries $G_{ij}^{(T)}$. Then in (2) we choose the first factor of $A$ that is not maximally expanded.) Note that (7.11) and (7.12) follow from (3.4). It is clear that (7.10) holds with the algorithm just defined.

and so on, at each iteration performing the steps (1) and (2) on each new monomial independently of the others. Note that the lower indices are binary sequences that describe the recursive application of the operations $w_{0}$ and $w_{1}$. In this manner we generate a binary tree whose vertices are given by finite binary strings $\sigma$. The associated monomials satisfy $A_{\sigma i}^{r}\mathrel{\vbox{\hbox{.}\hbox{.}}}=w_{i}(A_{\sigma}^{r})$ for $i=0,1$, where $\sigma i$ denotes the binary string obtained by appending $i$ to the right end of $\sigma$. See Figure 7.1 for an illustration of the tree.

We stop the recursion of a tree vertex whenever the associated monomial satisfies the stopping rule of step (1). In other words, the set of leaves of the tree is the set of binary strings $\sigma$ such that either all factors of $A^{r}_{\sigma}$ are maximally expanded or $d(A^{r}_{\sigma})\geqslant p+1$. We claim that the resulting binary tree is finite, i.e. that the algorithm always reaches step (1) after a finite number of iterations. Indeed, by the stopping rule in (1), we have $d(A^{r}_{\sigma})\leqslant p+1$ for any vertex $\sigma$ of the tree. Since each application of $w_{1}$ increases $d(\cdot)$ by at least one, and in the first step (i.e. when applied to $A^{r}$) by two, we conclude that the number of ones in any $\sigma$ is at most $p$. Since each application of $w_{1}$ increases the number of Green function entries by at most four, and the application of $w_{0}$ does not change this number, we find that the number of Green function entries in $A^{r}_{\sigma}$ is bounded by $4p+1$. Hence the maximal number of upper indices in $A^{r}_{\sigma}$ for any tree vertex $\sigma$ is $(4p+1)p$. Since each application of $w_{0}$ increases the total number of upper indices by one, we find that $\sigma$ contains at most $(4p+1)p$ zeros. We conclude that the maximal length of the string $\sigma$ (i.e. the depth of the tree) is at most $(4p+1)p+p=4p^{2}+2p$. A string $\sigma$ encoding a tree vertex contains at most $p$ ones. Denoting by $k$ the number of ones in a string encoding a leaf of the tree, we find that the number of leaves is bounded by $\sum_{k=0}^{p}\binom{4p^{2}+2p}{k}\leqslant(Cp^{2})^{p}$. Therefore, denoting by $\mathcal{L}_{r}$ the set of leaves of the binary tree generated from $A^{r}$, we have $\lvert\mathcal{L}_{r}\rvert\leqslant(Cp^{2})^{p}$.

By definition of the tree and $w_{0}$ and $w_{1}$, we have the decomposition

Moreover, each monomial $A_{\sigma}^{r}$ for $\sigma\in\mathcal{L}_{r}$ either consists entirely of maximally expanded Green function entries or satisfies $d(A_{\sigma}^{r})=p+1$. (This is an immediate consequence of the stopping rule in (1)).

Next, we observe that for any string $\sigma$ we have

where $b(\sigma)$ is the number ones in the string $\sigma$. Indeed, if $b(\sigma)=0$ then this follows from (7.5); if $b(\sigma)\geqslant 1$ this follows from the last statement in (7.10) and (7.3).

Using (7.9) and (7.13) we have the representation

We now claim that any nonzero term on the right-hand side of (7.15) satisfies

Before embarking on the proof, we explain its idea. By (7.14), the naive size of the left-hand side of (7.16) is $\Phi^{p}$. The key observation is that each lone label $s\in L$ yields one extra factor $\Phi$ to the estimate. This is because by (7.8), the expectation in (7.15) would vanish if all other factors \bigl{(}{Q_{k_{r}}A_{\sigma_{r}}^{r}}\bigr{)}, $r\neq s$, were $H^{(k_{s})}$-measurable. The expansion of the binary tree makes this dependence explicit by exhibiting $k_{s}$ as a lower index. But this requires performing an operation $w_{1}$ with the choice $u=k_{s}$ in (7.11) or (7.12). However, $w_{1}$ increases the number of off-diagonal element by at least one. In other words, every index associated with a lone label must have a “partner” index in a different Green function entry which arose by application of $w_{1}$. Such a partner index may only be obtained through the creation of at least one off-diagonal Green function entry. The actual proof below shows that this effect applies cumulatively for all lone labels.

In order to prove (7.16), we consider two cases. Consider first the case where for some $r=1,\dots,p$ the monomial $A_{\sigma_{r}}^{r}$ on the left-hand side of (7.16) is not maximally expanded. Then $d(A_{\sigma_{r}}^{r})=p+1$, so that (7.3) yields $A_{\sigma_{r}}^{r}\prec\Phi^{p+1}$. Therefore the observation that $A_{\sigma_{s}}^{s}\prec\Phi$ for all $s\neq r$, together with (7.2) implies that the left-hand side of (7.16) is O_{\prec}\bigl{(}{\Phi^{2p}}\bigr{)}. Since $\lvert L\rvert\leqslant p$, (7.16) follows.

Consider now the case where $A_{\sigma_{r}}^{r}$ on the left-hand side of (7.16) is maximally expanded for all $r=1,\dots,p$. The key observation is the following claim about the left-hand side of (7.16) with a nonzero expectation.

For each $s\in L$ there exists $r=\tau(s)\in\{1,\dots,p\}\setminus\{s\}$ such that the monomial $A_{\sigma_{r}}^{r}$ contains a Green function entry with lower index $k_{s}$.

In other words, after expansion, the lone label $s$ has a “partner” label $r=\tau(s)$, such that the index $k_{s}$ appears also in the expansion of $A^{r}$ (note that there may be several such partner labels $r$). To prove $(*)$, suppose by contradiction that there exists an $s\in L$ such that for all $r\in\{1,\dots,p\}\setminus\{s\}$ the lower index $k_{s}$ does not appear in the monomial $A_{\sigma_{r}}^{r}$. To simplify notation, we assume that $s=1$. Then, for all $r=2,\dots,p$, since $A_{\sigma_{r}}^{r}$ is maximally expanded, we find that $A_{\sigma_{r}}^{r}$ is $H^{(k_{1})}$-measurable. Therefore we have

where in the last step we used (7.8). This concludes the proof of $(*)$.

To prove (7.17), fix $r\in\{1,\dots,p\}$. By definition, for each $s\in\tau^{-1}(\{r\})$ the index $k_{s}$ appears as a lower index in the monomial $A_{\sigma_{r}}^{r}$. Since $s\in L$ is by definition a lone label and $s\neq r$, we know that $k_{s}$ does not appear as an index in $A^{r}$. By definition of the monomials associated with the tree vertex $\sigma_{r}$, it follows that $b(\sigma_{r})$, the number of ones in $\sigma_{r}$, is at least \bigl{\lvert}\tau^{-1}(\{r\})\bigr{\rvert}=l(r) since each application of $w_{1}$ adds precisely one new (lower) index. Note that in this step it is crucial that $s\in\tau^{-1}(\{r\})$ was a lone label. Recalling (7.14), we therefore get (7.17).

Summing over the binary trees in (7.15) and using Lemma 7.1, we get from (7.16)

We now return to the sum (7.9). We perform the summation by first fixing $P\in\mathfrak{P}_{p}$, with associated lone labels $L=L(P)$. We find

in the first step we used that the summation is performed over $\lvert P\rvert$ free indices, the remaining $p-\lvert P\rvert$ being estimated by $N^{-1}$; in the second step we used that each block of $P$ that is not contained in $L$ consists of at least two labels, so that $p-\lvert P\rvert\geqslant(p-\lvert L\rvert)/2$. From (7.9) and (7.18) we get

where in the last step we used the lower bound from (6.2) and estimated the summation over $\mathfrak{P}_{p}$ with a constant $C_{p}$ (which is bounded by $(Cp^{2})^{p}$). Summarizing, we have proved that

We conclude the proof of Proposition LABEL:prop16 with a simple application of Markov’s inequality. Fix $\varepsilon>0$ and $D>0$. Using (7.19) and Markov’s inequality we find

for large enough $N\geqslant N_{0}(\varepsilon,p)$. Choosing $p\geqslant\varepsilon^{-1}(1+D)$ concludes the proof of Proposition LABEL:prop16. ∎

We conclude this section with an alternative proof of Proposition LABEL:prop16. While the underlying argument remains similar, the following proof makes use of an additional decomposition of the space of random variables, which avoids the use of the stopping rule from Step (1) in the above proof of Proposition LABEL:prop16. This decomposition may be regarded as an abstract reformulation of the stopping rule.

As before, we set $X_{k}\mathrel{\vbox{\hbox{.}\hbox{.}}}=Q_{k}(G_{kk})^{-1}$. The decomposition is defined using the operations $P_{i}$ and $Q_{i}$, introduced in Definition 3.2. It is immediate that $P_{i}$ and $Q_{i}$ are projections, that $P_{i}+Q_{i}=1$, and that all of these projections commute with each other (by Fubini’s theorem). For a set $A\subset\{1,\dots,N\}$ we use the notations $P_{A}\mathrel{\vbox{\hbox{.}\hbox{.}}}=\prod_{i\in A}P_{i}$ and $Q_{A}\mathrel{\vbox{\hbox{.}\hbox{.}}}=\prod_{i\in A}Q_{i}$.

Let $p$ be even and introduce the shorthand $\widetilde{X}_{k_{s}}\mathrel{\vbox{\hbox{.}\hbox{.}}}=X_{k_{s}}$ for $s\leqslant p/2$ and $\widetilde{X}_{k_{s}}\mathrel{\vbox{\hbox{.}\hbox{.}}}=\overline{X}\!\,_{k_{s}}$ for $s>p/2$. Then we get

Next, by definition of $\widetilde{X}_{k_{s}}$, we have that $\widetilde{X}_{k_{s}}=Q_{k_{s}}\widetilde{X}_{k_{s}}$, which implies that $P_{A^{c}_{s}}\widetilde{X}_{k_{s}}=0$ if $k_{s}\notin A_{s}$. Hence may restrict the summation to $A_{s}$ satisfying

for all $s$. Moreover, we claim that the right-hand side of (7.20) vanishes unless

for all $s$. Indeed, suppose that $k_{s}\in\bigcap_{q\neq s}A_{q}^{c}$ for some $s$, say $s=1$. In this case, for each $s=2,\dots,p$, the factor $P_{A_{s}^{c}}Q_{A_{s}}\widetilde{X}_{k_{s}}$ is $H^{(k_{1})}$-measurable. Thus we get

We conclude that the summation on the right-hand side of (7.20) is restricted to indices satisfying (7.21) and (7.22). Under these two conditions we have

since each index $k_{s}$ must belong to at least two different sets $A_{q}$: to $A_{s}$ (by (7.21)) as well as to some $A_{q}$ with $q\neq s$ (by (7.22)).

Before proving (7.24), we show it may be used to complete the proof. Using (7.20), (7.24), and Lemma 7.1, we find

where in the first step we estimated the summation over the sets $A_{1},\dots,A_{p}$ by a combinatorial factor $C_{p}$ depending on $p$, in the fourth step we used the elementary inequality $a^{n}b^{m}\leqslant(a+b)^{n+m}$ for positive $a,b$, and in the last step we used (6.2). Thus we have proved (7.19), from which the claim follows exactly as in the first proof of Proposition LABEL:prop16.

What remains is the proof of (7.24). The case $\lvert A\rvert=1$ (corresponding to $A=\{k\}$) follows from (7.5), exactly as in the first proof of Proposition LABEL:prop16. To simplify notation, for the case $\lvert A\rvert\geqslant 2$ we assume that $k=1$ and $A=\{1,2,\dots,t\}$ with $t\geqslant 2$. It suffices to prove that

where the first term vanishes since $G_{11}^{(2)}$ is $H^{(2)}$-measurable. We now consider

and apply (3.4) with $k=3$ to each Green function entry on the right-hand side, and multiply everything out. The result is a sum of fractions of entries of $G$, whereby all entries in the numerator are off-diagonal and all entries in the denominator are diagonal. The leading order term vanishes,

so that the surviving terms have at least three (off-diagonal) Green function entries in the numerator. We may now continue in this manner; at each step the number of (off-diagonal) Green function entries in the numerator increases by at least one.

More formally, we obtain a sequence $A_{2},A_{3},\dots,A_{t}$, where $A_{2}\mathrel{\vbox{\hbox{.}\hbox{.}}}=Q_{2}\frac{G_{12}G_{21}}{G_{11}G_{11}^{(2)}G_{22}}$ and $A_{i}$ is obtained by applying (3.4) with $k=i$ to each entry of $Q_{i}A_{i-1}$, and keeping only the nonvanishing terms. The following properties are easy to check by induction.

$A_{i}$ consists of the projection $Q_{2}\cdots Q_{i}$ applied to a sum of fractions such that all entries in the numerator are off-diagonal and all entries in the denominator are diagonal.

The number of (off-diagonal) entries in the numerator of each term of $A_{i}$ is at least $i$.

By Lemma 7.1 combined with (ii) and (iii) we conclude that $\lvert A_{i}\rvert\prec\Phi^{i}$. From (i) we therefore get

This is (7.25). Hence the proof is complete. ∎

Semicircle law on small scales: proof of Theorem LABEL:thm:llsc

≲sec:local_law_small_scales We define the signed measure $\hat{\mu}$ and its Stieltjes transform $\hat{s}$ through

The basic idea behind the proof of Theorem LABEL:thm:llsc is to estimate $\hat{\mu}(I)$ using the Helffer-Sjöstrand formula from Appendix C in terms of its Stieltjes transfrom, $\hat{s}$, which is controlled by Theorem LABEL:Th3.

Now using the Helffer-Sjöstrand formula from Proposition C.1 with $n=1$, we get

Since the left-hand side is real, we obtain

Note the crucial cancellation of the terms proportional to $f^{\prime}(x)\chi(y)$.

Using Lemma 8.1, we may now estimate (8.2)–(8.4). First, using that $\chi^{\prime}$ is supported in $\setminus(-1,1)$, we easily find

with high probability, where in the third step we used Lemma 8.1. We conclude that

As above, using Lemma 8.1 we easily find that the second line of (8.7) is bounded by $C\eta$ with high probability. Moreover, the first term on the right-hand side of (8.7) is bounded by

Recalling (8.5) and (8.6), we have therefore proved that

In order to conclude the proof of Theorem LABEL:thm:llsc, we have to return from the smoothed indicator function $f$ to the sharp indicator function of $I$. To that end, we note that if $I\subset$ we have the upper bound

with high probability. Since $\varepsilon>0$ was arbitrary, we conclude that for any $I\subset$ we have $\hat{\mu}(I)=O_{\prec}(N^{-1})$.

Eigenvalue rigidity: proof of Theorem 2.9

≲sec:rig The first key input of the proof is the following estimate of the norm of $H$. (Note that the exponent of $N^{-2/3}$ is optimal.)

For a Wigner matrix $H$ we have $\lVert H\rVert\leqslant 2+O_{\prec}(N^{-2/3})$.

The main tool in the proof of Proposition 9.1 is the following improved version of the local semicircle law (2.14) outside of the spectrum.

We use (6.6) with the a priori bound $\Theta\prec(N\eta)^{-1}$ from (2.14), which yields

where $\Phi_{\sigma}$ was defined in (6.3). The claim follows. ∎

Note that the bound from Lemma 9.2 is better than (2.14) when $E$ is sufficiently far outside of the spectrum, for large enough $\kappa$ and small enough $\eta$, since in that case $\operatorname{Im}m$ is small by (3.3).

For definiteness, we prove that the largest eigenvalue $\lambda_{1}$ of $H$ satisfies $\lambda_{1}\leqslant 2+O_{\prec}(N^{-2/3})$; the smallest eigenvalue $\lambda_{N}$ is handled similarly. From the Füredi-Komlós argument in Theorem LABEL:Th:Furedi_Komlos, we know that $\lambda_{1}\leqslant 3$ with high probability. It therefore remains to show that, for any fixed $\varepsilon>0$, there is no eigenvalue of $H$ in

By an argument analogous to Remark 2.7, we find from Lemma 9.2 and (3.3) that, with high probability,

Moreover, from (9.2) we find that, with high probability,

for all $E\in I$. From (9.4) and (9.5) we conclude that, with high probability,

Now suppose that there is an eigenvalue, say $\lambda_{i}$, of $H$ in $I$. Then we find

Since (9.6) and (9.7) with $E=\lambda_{i}\in I$ are mutually exclusive, we conclude that, with high probability, there is no eigenvalue of $H$ in $I$. Since $\varepsilon>0$ was arbitrary, the claim follows. ∎

Armed with Proposition 9.1, we may now complete the proof of Theorem 2.9. We only consider $i\leqslant N/2$; the indices $i>N/2$ are dealt with analogously. From Theorem LABEL:thm:llsc we get $\mu([-1,\infty))\geqslant 1/2$ with high probability, which implies that $\lambda_{i}\geqslant-1$ for all $i\leqslant N/2$ with high probability; we shall use this fact tacitly in the following.

Fix $\varepsilon>0$. Then from the definitions (2.4) and (2.18), we find