Isotropic Local Laws for Sample Covariance and Generalized Wigner Matrices

Introduction

In recent years there has been substantial progress in understanding the local versions of the semicircle and the Marchenko-Pastur laws (see EKYY4 ; ECDM for an overview and detailed references). This research was originally motivated by the Wigner-Dyson-Mehta universality conjecture for the local spectral statistics of random matrices. The celebrated sine kernel universality and related results for other symmetry classes concern higher-order correlation functions, and not just the eigenvalue density. Moreover, they pertain to scales of order $1/N$, smaller than the scales on which local laws hold. Nevertheless, local laws (with precise error bounds) are essential ingredients for proving universality. In particular, one of their consequences, the precise localization of the eigenvalues (called rigidity bounds), has played a fundamental role in the relaxation flow analysis of the Dyson Brownian Motion, which has led to the proof of the Wigner-Dyson-Mehta universality conjecture for all symmetry classes ESY4 ; ESYY .

The basic approach behind the proofs of local laws is the analysis of a self-consistent equation for the Stieltjes transform, a scalar equation which controls the trace of the resolvent (and hence the empirical eigenvalue density). A vector self-consistent equation for the diagonal resolvent matrix entries, $[(H-z)^{-1}]_{ii}$, was introduced in EYY1 . Later, a matrix self-consistent equation was derived in EKYY3 . Such self-consistent equations provide entrywise control of the resolvent and not only its trace. This latter fact has proved a key ingredient in the Green function comparison method (introduced in EYY1 and extended to the spectral edge in EYY3 ), which allows the comparison of local statistics via moment matching even below the scale of eigenvalue spacing.

The isotropic local laws established in this paper serve as a key input in establishing detailed results about the eigenvalues and eigenvectors of deformed matrix models. These include:

A complete picture of the distribution of outlier eigenvalues/eigenvectors, as well as the non-outlier eigenvalues/eigenvectors near the spectral edge.

An investigation of the BBP transition using that, thanks to the optimality of the high-probability bounds in the local laws, the results of (a) extend even to the case when some eigenvalues of $A$ are very close to the critical value.

This programme for the eigenvalues of deformed Wigner matrices was carried out in KY2 ; KY3 . In KYY , we carry it out for the eigenvectors of covariance matrices.

In this paper we prove the isotropic Marchenko-Pastur law for sample covariance matrices as well as the isotropic semicircle law for generalized Wigner matrices. Our proofs are based on a novel method, which is considerably more robust than that of KY2 . Both proofs (the one from KY2 and the one presented here) crucially rely on the entrywise local law as input, but follow completely different approaches to obtain the isotropic law from the entrywise one. The basic idea of the proof in KY2 is to use the Green function comparison method to compare the resolvent of a given Wigner matrix to the resolvent of a Gaussian random matrix, for which the isotropic law is a trivial corollary of the entrywise one (by basis transformation). Owing to various moment matching conditions imposed by the Green function comparison, the result of KY2 required the variances of all matrix entries to coincide and, for results in the bulk spectrum, the third moments to vanish. In contrast, our current approach does not rely on Green function comparison. Instead, it consists of a precise analysis of the cancellation of fluctuations in Green functions. We use a graphical expansion method inspired by techniques recently developed in EKY2 to control fluctuations in Green functions of random band matrices.

Our first main result is the isotropic local Marchenko-Pastur law for sample covariance matrices $H=X^{*}X$, where $X$ is an $M\times N$ matrix. We allow the dimensions of $X$ to differ wildly: we only assume that $\log N\asymp\log M$. In particular, the aspect ratio $\phi=M/N$ – a key parameter in the Marchenko-Pastur law – may scale as a power of $N$. Our entrywise law (required as input for the proof of the isotropic law) is a generalization of the one given in PY . In addition to generalizing the proof of PY , we simplify and streamline it, so as to obtain a short and self-contained proof.

Our second main result is the isotropic local semicircle law for generalized Wigner matrices. This extends the isotropic law of KY2 from Wigner matrices to generalized Wigner matrices, in which the variances of the matrix entries need not coincide. It also dispenses with the third moment assumption of KY2 mentioned previously. In fact, our proof applies to even more general matrix models, provided that an entrywise law has been established. As an application of the isotropic laws, we also prove a basis-independent version of eigenvector delocalization for both sample covariance and generalized Wigner matrices.

We conclude with an outline of the paper. In Section 2 we define our models and state our results, first for sample covariance matrices (Section 2.1) and then for generalized Wigner matrices (Section 2.2). The rest of the paper is devoted to the proofs. Since they are very similar for sample covariance matrices and generalized Wigner matrices, we only give the details for sample covariance matrices. Thus, Sections 3–6 are devoted to the proof of the isotropic Marchenko-Pastur law for sample covariance matrices; in Section 7, we describe how to modify the arguments to prove the isotropic semicircle law for generalized Wigner matrices. Section 3 collects some basic identities and estimates that we shall use throughout the proofs. In Section 4 we prove the entrywise local Marchenko-Pastur law, generalizing the results of PY . The main argument and the bulk of the proof, i.e. the proof of the isotropic law, is given in Section 5. For a sketch of the argument we refer to Section 5.3. Finally, in Section 6 we draw some simple consequences from the isotropic law: optimal control outside of the spectrum and isotropic delocalization bounds.

We use $C$ to denote a generic large positive constant, which may depend on some fixed parameters and whose value may change from one expression to the next. Similarly, we use $c$ to denote a generic small positive constant. For two positive quantities $A_{N}$ and $B_{N}$ depending on $N$ we use the notation $A_{N}\asymp B_{N}$ to mean $C^{-1}A_{N}\leqslant B_{N}\leqslant CA_{N}$ for some positive constant $C$.

Results

Let $X$ be an $M\times N$ matrix whose entries $X_{i\mu}$ are independent complex-valued random variables satisfying

We shall study the $N\times N$ matrix $X^{*}X$; hence we regard $N$ as the fundamental large parameter, and write $M\equiv M_{N}$. Our results also apply to the matrix $XX^{*}$ provided one replaces $N\leftrightarrow M$. See Remark 2.11 below for more details.

We always assume that $M$ and $N$ satisfy the bounds

for some positive constant $C$. We define the ratio

which may depend on $N$. Here, and throughout the following, in order to unclutter notation we omit the argument $N$ in quantities, such as $X$ and $\phi$, that depend on it.

It is well known that the empirical distribution of the eigenvalues of the $N\times N$ matrix $X^{*}X$ has the same asymptotics as the Marchenko-Pastur lawMP

to be the edges of the limiting spectrum. Note that (2.4) is normalized so that its integral is equal to one. The Stieltjes transform of the Marchenko-Pastur law (2.4) is

where the square root is chosen so that $m_{\phi}$ is holomorphic in the upper half-plane and satisfies $m_{\phi}(z)\to 0$ as $z\to\infty$. The function $m_{\phi}=m_{\phi}(z)$ is also characterized as the unique solution of the equation

satisfying $\operatorname{Im}m(z)>0$ for $\operatorname{Im}z>0$. The formulas (2.4)–(2.7) were originally derived for the case when $\phi=M/N$ is independent of $N$ (or, more precisely, when $\phi$ has a limit in $(0,\infty)$ as $N\to\infty$). Our results allow $\phi$ to depend on $N$ under the constraint (2.2), so that $m_{\phi}$ and $\varrho_{\phi}$ may also depend on $N$ through $\phi$.

Throughout the following we use a spectral parameter

with $\eta>0$, as the argument of Stieltjes transforms and resolvents. Define the resolvent

The following notion of a high-probability bound was introduced in EKY2 , and has been subsequently used in a number of works on random matrix theory. It provides a simple way of systematizing and making precise statements of the form “$\xi$ is bounded with high probability by $\zeta$ up to small powers of $N$”.

be two families of nonnegative random variables, where $U^{(N)}$ is a possibly $N$-dependent parameter set. We say that $\xi$ is stochastically dominated by $\zeta$, uniformly in $u$, if for all (small) $\varepsilon>0$ and (large) $D>0$ we have

for large enough $N\geqslant N_{0}(\varepsilon,D)$. Throughout this paper the stochastic domination will always be uniform in all parameters (such as matrix indices and the spectral parameter $z$) that are not explicitly fixed. Note that $N_{0}(\varepsilon,D)$ may depend on the constants from (2.2) and (2.3) as well as any constants fixed in the assumptions of our main results. If $\xi$ is stochastically dominated by $\zeta$, uniformly in $u$, we use the notation $\xi\prec\zeta$. Moreover, if for some complex family $\xi$ we have $\lvert\xi\rvert\prec\zeta$ we also write $\xi=O_{\prec}(\zeta)$.

Because of (2.2), all (or some) factors of $N$ in Definition (2.1) could be replaced with $M$ without changing the definition of stochastic domination.

Sometimes we shall need the following notion of high probability.

which is the number of nontrivial (i.e. nonzero) eigenvalues of $X^{*}X$; the remaining $N-K$ eigenvalues of $X^{*}X$ are zero. (Note that the $K$ nontrivial eigenvalues of $X^{*}X$ coincide with those of $XX^{*}$.) Fix a (small) $\omega\in(0,1)$ and define the domain

Throughout the following we regard $\omega$ as fixed once and for all, and do not track the dependence of constants on $\omega$.

Suppose that (2.1), (2.2), and (2.3) hold. Then

Beyond the support of the limiting spectrum, one has stronger control all the way down to the real axis. For fixed (small) $\omega\in(0,1)$ define the region

of spectral parameters separated from the asymptotic spectrum by $K^{-2/3+\omega}$, which may have an arbitrarily small positive imaginary part $\eta$.

Suppose that (2.1), (2.2), and (2.3) hold. Then

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

The right-hand side of (2.15) is stable under the limit $\eta\to 0$, and may therefore be extended to $\eta=0$. Recalling the previous remark, we conclude that (2.15) also holds for $\eta=0$.

Suppose that (2.1), (2.2), and (2.3) hold. Then for any $\varepsilon>0$ we have the bound

The following result is on the rigidity of the nontrivial eigenvalues of $X^{*}X$, which coincide with the nontrivial eigenvalues of $XX^{*}$. Let $\gamma_{1}\geqslant\gamma_{2}\geqslant\cdots\geqslant\gamma_{K}$ be the classical eigenvalue locations according to $\varrho_{\phi}$ (see (2.4)), defined through

Fix a (small) $\omega\in(0,1)$ and suppose that (2.1), (2.2), and (2.3) hold. Then

uniformly for all $\alpha\in\{1,\dots,[(1-\omega)K]\}$. If in addition $\lvert\phi-1\rvert\geqslant c$ for some constant $c>0$ then

uniformly for all $\alpha\in\{[K/2],\dots,K\}$.

2. Generalized Wigner matrix

its Stieltjes transform; here we chose the square root so that $m$ is holomorphic in the upper half-plane and satisfies $m(z)\to 0$ as $z\to\infty$. Note that $m=m(z)$ is also characterized as the unique solution of

that satisfies $\operatorname{Im}m>0$ for $\eta>0$. Let

Fix a (small) $\omega\in(0,1)$ and define

Suppose that (2.22) and (2.23) hold. Then

Theorem 2.12 is the isotropic generalization of the following result, proved in EKYY4 . A similar result first appeared in EYY3 .

Suppose that (2.22) and (2.23) hold. Then

The proof of Theorem 2.14 is the same as that of Theorem 2.12. Below we give the proof for Theorem 2.12, which can be trivially adapted to yield Theorem 2.14.

Combining Theorem 2.14 with the isotropic local semicircle law from EKYY4 , we may for instance obtain an isotropic local semicircle law for matrices where the lower bound of (2.22) is relaxed, so that some matrix entries may vanish.

Beyond the support of the limiting spectrum $$, the statement of Theorem 2.12 may be improved to a bound that is stable all the way down to the real axis. For fixed (small)$\omega\in(0,1)$ define the region

of spectral parameters separated from the asymptotic spectrum by $N^{-2/3+\omega}$, which may have an arbitrarily small positive imaginary part $\eta$.

Suppose that (2.22) and (2.23) hold. Then

Suppose that (2.22) and (2.23) hold. Then

Finally, in analogy to Theorem 2.10, we record the following rigidity result, which is a trivial consequence of (EKYY4, , Theorem 7.6) with $X=CN^{-2/3}$ and $Y=CN^{-1}$; see also (EYY3, , Theorem 2.2). Write $\lambda_{1}\geqslant\lambda_{2}\geqslant\cdots\geqslant\lambda_{N}$ for the eigenvalues of $H$, and let $\gamma_{1}\geqslant\gamma_{2}\geqslant\cdots\geqslant\gamma_{N}$ be their classical locations according to $\varrho$, defined through

Preliminaries

The rest of this paper is devoted to the proofs of our main results. They are similar for sample covariance matrices and generalized Wigner matrices, and in Sections 3–6 we give the argument for sample covariance matrices (hence proving the results of Section 2.1). How to modify these arguments to generalized Wigner matrices (and hence prove the results of Section 2.2) is explained in Section 7. We choose to present our method in the context of sample covariance matrices mainly for two reasons. First, we take this opportunity to give a version of the entrywise local law (Section 4) – required as input for the proof of the isotropic law – which is more general and has a simpler proof than the local law previously established in PY . Second, the proof of the isotropic law in the case of sample covariance matrices is conceptually slightly clearer due to a natural splitting of summation indices into two categories (which we distinguish by the use of Latin and Greek letters); this splitting is an essential structure behind our proof in Section 5, and is also used in the case of generalized Wigner matrices, in which case it is however purely artificial.

We now move on to the proofs. In order to unclutter notation, we shall often omit the argument $z$ from quantities that depend on it. Thus, we for instance often write $G$ instead of $G(z)$. We put the arguments $z$ back when needed, typically if we are working with several different spectral parameters $z$.

We begin by recording some basic large deviations estimates. We consider complex-valued random variables $\xi$ satisfying

If the coefficients $a_{ij}^{(N)}$ and $b_{i}^{(N)}$ depend on an additional parameter $u$, then all of these estimates are uniform in $u$ (see Definition 2.1), i.e. the threshold $N_{0}=N_{0}(\varepsilon,D)$ in the definition of $\prec$ depends only on the family $C_{p}$ from (3.1); in particular, $N_{0}$ does not depend on $u$.

These estimates are an immediate consequence of Lemmas B.2, B.3, and B.4 in EKYY3 . See also Theorem C.1 in EKYY4 . ∎

The following lemma collects basic algebraic properties of stochastic domination $\prec$. We shall use them tacitly throughout the following.

Suppose that $\xi(u,v)\prec\zeta(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 $\xi_{1}(u)\prec\zeta_{1}(u)$ uniformly in $u$ and $\xi_{2}(u)\prec\zeta_{2}(u)$ uniformly in $u$. Then

The claims (i) and (ii) follow from a simple union bound. For (iii), pick $\varepsilon>0$ and assume to simplify notation that $\xi$ and $\Psi$ do not depend on $u$. Then

for arbitrary $D>0$. The claim (iii) therefore follows by choosing $D\geqslant 3C$. ∎

Next, we give some basic facts about the Stieltjes transform $m_{\phi}$ of the Marchenko-Pastur law defined in (2.6). They have an especially simple form in the case $\phi\geqslant 1$; the complementary case $\phi<1$ can be easily handled using (2.20). Recall the definition (2.9) of $\kappa$. We record the following elementary properties of $m_{\phi}$, which may be proved e.g. by starting from the explicit form (2.6).

The basic object is the $M\times N$ matrix $X$. We use the indices $i,j=1,\dots,M$ to denote the rows of $X$ and $\mu,\nu=1,\dots,N$ to denote its columns. Unrestricted summations over Latin indices always run over the set $\{1,2,\ldots,M\}$ while Greek indices run over $\{1,2,\ldots,N\}$.

In addition to the resolvent $R$ from (2.8), we shall need another resolvent, $G$:

Although our main results only pertain to $R$, the resolvent $G$ will play a crucial role in the proofs, in which we consider both $X^{*}X$ and $XX^{*}$ in tandem. In the following formulas the spectral parameter $z$ plays no explicit role, and we therefore omit it from the notation, as explained at the beginning of this section.

More abstractly, we may introduce two sets of indices, $I_{\rm population}$ and $I_{\rm sample}$, such that $I_{\rm population}$ indexes the entries of $G$ and $I_{\rm sample}$ the entries of $R$. Elements of $I_{\rm population}$ are always denoted by Latin letters and elements of $I_{\rm sample}$ by Greek letters. These two sets are to be viewed as distinct. For convenience of notation, we shall always use the customary representations $I_{\rm population}\mathrel{\mathop{:}}=\{1,\dots,M\}$ and $I_{\rm sample}\mathrel{\mathop{:}}=\{1,\dots,N\}$, bearing in mind that neither should be viewed as a subset of the other. This terminology originates from the statistical application of sample covariance matrices. The idea is that we are observing the statistics of a population of size $M$ by making $N$ independent measurements (“samples”) of the population. Each observation is a column of $X$. Hence the population index $i$ labels the rows of $X$ and the sample index $\mu$ the columns of $X$.

Moreover, for $i,j\notin T$ we define the resolvents entries

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

We shall use the following expansion formulas for $G$. They are elementary consequences of Schur’s complement formula; see e.g. Lemma 4.2 of EYY1 and Lemma 6.10 of EKYY2 for proofs of similar identities.

For $i,j,k\notin T$ and $i,j\neq k$ we have

Moreover, for $i,j\notin T$ and $i\neq j$ we have

Definition 3.5 and Lemma 3.6 have the following analogues for removing columns and identities for $R$.

Moreover, for $\mu,\nu\notin T$ we define the resolvents entries

When $T=\{\mu\}$, we abbreviate $[\{\mu\}]$ by $[\mu]$ in the above definitions; similarly, we write $[\mu\nu]$ instead of $[\{\mu,\nu\}]$.

We use the following expansion formulas for $R$, which are analogoues to those of Lemma 3.6.

For $\mu,\nu,\rho\notin T$ and $\mu,\nu\neq\rho$ we have

Moreover, for $\mu,\nu\notin T$ and $\mu\neq\nu$ we have

Here we draw attention to a fine notational distinction. Parentheses $(\cdot)$ in $X^{(T)}$ indicate removal of rows (indexed by Latin letters), while square brackets $[\cdot]$ in $X^{[T]}$ indicate removal of columns (indexed by Greek letters). In particular, this notation makes it unambiguous whether $T$ is required to be a subset of $\{1,\dots,M\}$ or of $\{1,\dots,N\}$.

The following lemma is an immediate consequence of the fact that for $\phi\geqslant 1$ the spectrum of $XX^{*}$ is equal to the spectrum of $X^{*}X$ plus $M-N$ zero eigenvalues. (A similar result holds for for $\phi\leqslant 1$, and if $X$ is replaced with $X^{[T]}$ or $X^{(U)}$.)

Let $T\subset\{1,\dots,N\}$ and $U\subset\{1,\dots,M\}$. Then we have

in agreement with the relation (2.20) and the heuristics $M^{-1}\operatorname{Tr}G\sim m_{\phi^{-1}}$ and $N^{-1}\operatorname{Tr}R\sim m_{\phi}$.

The following lemma is an easy consequence of the well-known interlacing property of the eigenvalues of $XX^{*}$ and $X^{(i)}(X^{(i)})^{*}$, as well as the eigenvalues of $X^{*}X$ and $(X^{[\mu]})^{*}X^{[\mu]}$.

For any $T\subset\{1,\dots,N\}$ and $U\subset\{1,\dots,M\}$, there exists a constant $C$, depending only on $\lvert T\rvert$ and $\lvert U\rvert$, such that

Finally, we record the fundamental identity

which follows easily by spectral decomposition of $G^{[T]}$.

2. Reduction to the case ϕ⩾1italic-ϕ1\phi\geqslant 1

We shall prove Theorems 2.4 and 2.5 by restricting ourselves to the case $\phi\geqslant 1$ but considering both $X^{*}X$ and $XX^{*}$ simultaneously. In this short section we give the details of this reduction. Define the control parameter

Suppose that (2.1), (2.2), (2.3), and $\phi\geqslant 1$ hold. Then

Suppose that (2.1), (2.2), (2.3), and $\phi\geqslant 1$ hold. Then

Suppose that (2.1), (2.2), (2.3), and $\phi\geqslant 1$ hold. For any $\varepsilon>0$ we have the bounds

Theorems 2.4, 2.5, and 2.8 are easy consequences of Theorems 3.11, 3.12, and 3.13 respectively, combined with the observation that

What remains therefore is to prove Theorems 2.10, 3.11, 3.12, and 3.13. We shall prove Theorem 2.10 in Section 4.3, Theorem 3.11 in Section 5, and Theorems 3.12 and 3.13 in Section 6.

The entrywise local Marchenko-Pastur law

Suppose that (2.1), (2.2), (2.3), and $\phi\geqslant 1$ hold. Then

Theorem 4.1 differs from Theorem 3.1 in PY in the following two ways.

The restriction $1\leqslant\phi\leqslant C$ in PY is relaxed to $1\leqslant\phi\leqslant N^{C}$ (and hence, as explained in Section 3.2, to $N^{-C}\leqslant\phi\leqslant N^{C}$).

The uniform subexponential decay assumption of PY is relaxed to (2.3). On the other hand, thanks to the stronger subexponential decay assumption the statement of Theorem 3.1 of PY is slightly stronger than Theorem 4.1: in Theorem 3.1 of PY , the error bounds $N^{\varepsilon}$ in the definition of $\prec$ are replaced with $(\log N)^{C\log\log N}$.

The difference (ii) given above is technical and amounts to using Lemma 3.1, which is tailored for random variables satisfying (2.3), for the large deviation estimates. We remark that all of the arguments of the current paper may be translated to the setup of PY , explained in (ii) above, by modifying the definition of $\prec$. The essence of the proofs remains unchanged; the only nontrivial difference is that in Section 5 we have to control moments whose power depends weakly on $N$; this entails keeping track of some basic combinatorial bounds. We do not pursue this modification any further.

The difference (i) is more substantial, and requires to keep track of the $\phi$-dependence of all appropriately rescaled quantities throughout the proof. In addition, we take this opportunity to simplify and streamline the argument from PY . This provides a short and self-contained proof of Theorem 4.1, up to a fluctuation averaging result, Lemma 4.9 below, which was proved in the current simple and general form in EKYY4 .

We begin with the proof of (4.1) and (3.18). For the following it will be convenient to use the rescaled spectral parameters

Using $\widetilde{z}$ and $\widehat{z}$ we may write the the defining equation (2.7) of $m_{\phi}$ as

We define the $z$-dependent random control parameters

where we defined the Stieltjes transform of the empirical density of $X^{*}X$,

The goal of this subsection is to prove the following weaker variant of Theorem 4.1.

The rest of this subsection is devoted to the proof of Proposition 4.2. We begin by introducing the basic $z$-dependent event

The proof is a simple induction argument using (3.10) and the bound $\lvert m_{\phi}\rvert\geqslant c$ from (3.5). We omit the details. ∎

As in the works EYY3 ; PY , the main idea of the proof is to derive a self-consistent equation for $m_{R}=\frac{1}{N}\sum_{\mu}R_{\mu\mu}$ using the resolvent identity (3.11). To that end, we introduce the conditional expectation

i.e. the partial expectation in the randomness of the $\mu$-th column of $X$. We define

where in the last step we used (2.1) and (4.3). Using (3.11) with $T=\emptyset$, Lemma 3.9, and (4.3), we find

The following lemma contains the key estimates needed to control the error terms $Z_{\mu}$ and $\Lambda_{o}$. The errors are controlled using of the (random) control parameter

whose analogue in the context of Wigner matrices first appeared in EYY3 .

The proof is very similar to that of Theorems 6.8 and 6.9 of PY . We consequently only give the details for the estimate of $\Lambda_{o}$; the estimate of $Z_{\mu}$ is similar.

For $\mu\neq\nu$ we use (3.12) with $T=\emptyset$ to expand $R_{\mu\nu}$. Conditioning on $X^{[\mu\nu]}$ and invoking (3.3) yields

On the event $\Xi$, we estimate the right-hand side using

where the first step follows from (3.14), the second from Lemma 3.9, the third from $\operatorname{Im}z^{-1}=-\eta\lvert z\rvert^{-2}\geqslant-C\eta/\phi$ and (4.7), and the fourth from the fact that $\operatorname{Im}m_{\phi}\geqslant c\eta$ by (3.6).

Recalling (3.5), we have therefore proved that

which, together with the analogous bound for $Z_{\mu}$, concludes the proof of (4.13).

In order to prove the estimate $\Lambda_{o}\prec\Psi_{\Theta}$ from (4.14) for $\eta\geqslant(\log N)^{-1}$, we proceed similarly. From (4.15) and the trivial deterministic bound \bigl{\lvert}R_{\mu\mu}R_{\nu\nu}^{[\mu]}\bigr{\rvert}\leqslant\eta^{-2}\leqslant(\log N)^{2} we get

where the estimate is similar to (4.16), except that in the last step we use Lemma 3.10 to estimate $\operatorname{Tr}R^{\mu\nu}-\operatorname{Tr}R$. Since $\eta\geqslant(\log N)^{-1}$, we easily find that $\lvert R_{\mu\nu}\rvert\prec\Psi_{\Theta}$. This concludes the proof. ∎

Note that, by (4.4), the function $m_{\phi}$ satisfies $\mathcal{D}(m_{\phi})=0$.

Next, we derive a stability result for $\mathcal{D}^{-1}$. Roughly, we prove that if $\mathcal{D}(u)$ is small then $u$ is close to $m_{\phi}$. Note that this result is entirely deterministic. It relies on a discrete continuity argument, whose essence is the existence of a sufficiently large gap between the two solutions of $\mathcal{D}(\cdot)=0$. Once this gap is established, then, together with the fact that $u$ is close to $m_{\phi}$ for large $\eta$, we may conclude that $u$ is close to $m_{\phi}$ for smaller $\eta$ as well. We use a discrete version of a continuity argument (as opposed to a continuous one used e.g. in PY ), which allows us to bypass several technical issues when applying it to estimating the random quantity $\lvert m_{R}-m_{\phi}\rvert$. For more details of this application, see the explanation following (4.34).

Thus, if $\operatorname{Im}z\geqslant 1$ then $L(z)=\{z\}$ and if $\operatorname{Im}z\leqslant 1$ then $L(z)$ is a one-dimensional lattice with spacing $N^{-5}$ plus the point $z$. Clearly, we have the bound

for some constant $C$ independent of $z$ and $N$.

Let $u$ be as in Lemma 4.5, and abbreviate $\mathcal{R}\mathrel{\mathop{:}}=\mathcal{D}(u)$. Hence, by assumption on $u$, we have $\lvert\mathcal{R}\rvert\leqslant\delta$. We introduce $u_{1}\equiv u_{1}^{\mathcal{R}}$ and $u_{2}\equiv u_{2}^{\mathcal{R}}$ by setting $u_{1}\mathrel{\mathop{:}}=u$ and defining $u_{2}$ as the other solution of the quadratic equation $\mathcal{D}(u)=\mathcal{R}$. Note that each $u_{i}$ is continuous. Explicitly, for $\lvert\mathcal{R}\rvert\leqslant 1/2$ we get

for some constant $C_{0}\geqslant 2$. What remains is to show that (4.21) holds for $i=1$. We shall prove this using a continuity argument.

holds or not. If (4.24) does not hold, then we have $\kappa+\eta\leqslant 4C_{0}C_{1}\delta$, so that (4.21), $\lvert\mathcal{R}\rvert\leqslant\delta$, and the upper bound of (4.22) imply

What remains is the case where (4.24) holds. We use a continuity argument along the set $L(z)$, which we parametrize as $L(z)=\{z_{0},\dots,z_{L}\}$, where $\operatorname{Im}z_{0}=1$, $z_{L}=z$, and $\operatorname{Im}z_{l+1}<\operatorname{Im}z_{l}$. Note that $\lvert z_{l+1}-z_{l}\rvert\leqslant N^{-5}$. By assumption, $\lvert\mathcal{R}\rvert\leqslant\delta$ at each $z_{l}\in L(z)$, so that (4.21) and (4.22) yield

at each $z_{l}\in L(z)$. (Here the quantities $\kappa\equiv\kappa(z_{l})$, $\eta\equiv\eta(z_{l})$, and $\delta\equiv\delta(z_{l})$ are understood as functions of the spectral parameters $z_{l}$.) Moreover, since (4.24) holds at $z=z_{L}$, by the monotonicity assumption on $\delta$ we find that (4.24) holds for all $z_{l}\in L(z)$. We now prove that

for all $l=1,\dots,L$ by induction on $l$. For $l=0$ the bound (4.26) is simply (4.23) proved above. Suppose therefore that (4.26) holds for some $l$. Since $u_{1}$ and $m_{\phi}$ are Lipschitz continuous with Lipschitz constant $N$, we get

where in the second step we used the induction assumption, in the third step the Lipschitz continuity of $\delta$ and the bound $\eta\geqslant N^{-1}$, and in the last step the bounds $\delta\geqslant N^{-2}$ and $\kappa+\eta+\delta\leqslant C$. Next, recalling (4.24), it is easy to deduce (4.26) with $l$ replaced by $l+1$, using the bounds (4.25) and (4.27). This concludes the proof. ∎

We may now combine the probabilistic estimates from Lemma 4.4 with the stability of $\mathcal{D}^{-1}$ from Lemma 4.5 to get the following result for $\eta\geqslant 1$, which will be used as the starting estimate in the bootstrapping in $\eta$.

Next, we plug the estimates from Lemma 4.4 into (4.11) in order to obtain estimates on $m_{R}$. The summation in $m_{R}=\frac{1}{N}\sum_{\mu}R_{\mu\mu}$ will give rise to an error term of the form

For the proof of Proposition 4.2, it will be enough to estimate $\lvert[Z]\rvert\leqslant\max_{\mu}\lvert Z_{\mu}\rvert$, but for the eventual proof of Theorem 4.1, we shall need to exploit cancellation in the averaging in $[Z]$. Bearing this in mind, we state our estimates in terms of $[Z]$ to avoid repeating the following argument in Section 4.2.

where we absorbed the error term $N^{-1}$ on the right-hand side of (4.11) into $\Psi_{\Theta}^{2}$ using (3.6). Thus, using (4.13) we get

Hence (4.30) follows. Next, expanding $R_{\mu\mu}=m_{R}+(R_{\mu\mu}-m_{R})$ yields

After taking the average $[\cdot]=\frac{1}{N}\sum_{\mu}\cdot\,$ the second term on the right-hand side vanishes. Taking the average of (4.32) therefore yields, using (4.30) and (4.3),

Our goal is to prove that with high probability there is a gap in the range of $v$, i.e.

The basic idea behind the proof of (4.34) is to use the deterministic result from Lemma 4.5 to propagate smallness of the random variable $\Lambda(z)$ from large values of $\eta$ to smaller values of $\eta$. Since we are dealing with random variables, one has to keep track of probabilities of exceptional events. To that end, we only work on a discrete set of values of $\eta$, which allows us to control the exceptional probabilities by a simple union bound. We remark that the first instance of such a stochastic continuity argument combined with stability of a self-consistent equation was given in ESY2 in the context of Wigner matrices. Over the years it has been improved through several papers in the context of Wigner matrices EKYY4 ; EYY1 ; EYY3 as well as in the context of sample covariance matrices ESYY ; PY .

for large enough $N\geqslant N_{0}(\varepsilon,D)$ (independent of $z$ and $w$). Using (4.19) and a union bound, we therefore get

Next, we use Lemma 4.5 with $u=m_{R}$ and $\delta=N^{\varepsilon/2}(N\eta)^{-1/2}$ to get

(Here we used the trivial observation that the conclusion of Lemma 4.5 is valid not only at $z$ but in the whole set $L(z)$.) Using (4.13) and (4.30) we therefore get (4.34).

Since $\varepsilon$ can be made arbitrarily small and $D$ arbitrarily large, Proposition 4.2 follows from (4.38).

2. Fluctuation averaging and conclusion of the proof of Theorem 4.1

In order to improve the negative power of $(N\eta)$ in Proposition 4.2, and hence prove the optimal bound in Theorem 4.1, we shall use the following result iteratively. Recall the definition of $\Theta$ from (4.6) and definition of $[Z]$ from (4.29).

Let $\tau\in(0,1)$ and suppose that we have

This result was given in a slightly different context in Theorem 4.7 in EKYY4 . However, it is a triviality that the proof of Theorem 4.7 in EKYY4 carries over word for word, provided one replaces $G_{ij}^{(T)}$ there with $R_{\mu\nu}^{[T]}$; see Remark B.3 in EKYY4 . The proof relies only on the identity (3.10), which is the analogue of Equation (4.6) in EKYY4 . ∎

The conclusion of Lemma 4.9 remains true under somewhat more general hypotheses, whereby $\Lambda$ is not required to be small. Indeed, (4.41) holds provided that $\Phi_{o}$ is as in Lemma 4.9 and that

The proof is the same as that of Theorem 4.7 in EKYY4 .

Using (3.6), it is easy to check that these definitions of $\Phi_{o}$ and $\Phi$ satisfy the assumptions of Lemma 4.9. Hence the claim follows from Lemma 4.9 and (4.42). ∎

where in the second step we used (3.6). Summarizing, we have proved the self-improving estimate

From Proposition 4.2 we know that $\Theta\prec(N\eta)^{-1/4}$. Thus, for any $\varepsilon>0$, we iterate (4.43) an order $C_{\varepsilon}$ times to get $\Theta\prec(N\eta)^{-1+\varepsilon}$. This concludes the proof of the first bound of (3.18). The second bound of (3.18) follows from the first one and the identity (3.13).

Using Lemma 3.10, we rewrite the sum in the second term according to N^{-1}\sum_{\mu}R_{\mu\mu}^{(i)}=m_{R}+O\bigl{(}{(N\eta)^{-1}}\bigr{)}. Moreover, the third term is estimated exactly as $Z_{\mu}$ in Lemma 4.4, using Lemma 3.1. Putting everything together yields

In particular, $\lvert G_{ii}\rvert\prec\phi^{-1/2}$. The same argument applied to the matrix $X^{(j)}$ instead of $X$ yields $\lvert G_{ii}^{(j)}\rvert\prec\phi^{-1/2}$. Thus we get from (3.9) that for $i\neq j$ we have

where the last step follows using (3.3), exactly as in the proof of Lemma 4.4, and (4.1). This concludes the proof of (4.2), and hence of Theorem 4.1.

3. Proof of Theorem 2.10

The proof of Theorem 2.10 is similar to that of Theorem 2.2 in EYY3 and Theorem 3.3 in PY . We therefore only sketch the argument. First we observe that, since the nontrivial eigenvalues $\lambda_{1},\dots,\lambda_{K}$ of $X^{*}X$ and $XX^{*}$ coincide and

for all $\gamma>0$, it suffices to prove Theorem 2.10 for $\phi\geqslant 1$, i.e. $K=N$.

The proof relies on the following key estimates.

Finally, if $\phi\geqslant 1+c$ for some constant $c>0$, then

Starting from Lemma 4.11, the proof of Theorem 2.10 is elementary. (The details are given e.g. on the last page of Section 5 in EYY3 .)

The estimate (4.44) is a standard consequence of (3.18), using Helffer-Sjöstrand functional calculus; see e.g. (EYY3, , Section 5).

What remains is the proof of (4.45) and (4.46). Here the argument from (PY, , Section 8) applies with trivial modifications. The key inputs in our case are (4.44), Lemma 4.5, (4.40), and Lemma 4.9 combined with Remark 4.10. We omit further details. ∎

The isotropic law: proof of Theorem 3.11

In this section we complete the proof of Theorem 3.11. Since (3.18) was proved in Section 4, we only need to prove (3.16) and (3.17). For definiteness, we give the details of the proof of (3.16); the proof of (3.17) is very similar, and the required modifications are outlined at the end of Section 5.15 below.

It is convenient to introduce the rescaled quantities

The motivation behind this definition is that

2. Reduction to off-diagonal entries

By linearity and polarization, in order to prove (3.16) it suffices to prove that

The rest of this section is devoted to the proof of (5.7).

3. Sketch of the proof

The basic reason why (5.7) holds is that $G_{ab}$ can be expanded, to leading order, as a sum of independent random variables using the identity (3.9). To simplify the presentation in this sketch, we set $M=N$, so that $\phi=1$ and the rescalings from Section 5.1 indicated by a tilde are trivial. Hence we drop all tildes. From (3.9) we get

If we could replace the diagonal entries by the deterministic value $m_{\phi}$, it would suffice to estimate the sum $\sum_{a\neq b}\sum_{\mu,\nu}\overline{v}\!\,_{a}X_{a\mu}R^{(ab)}_{\mu\nu}X_{\nu b}^{*}v_{b}$. By the independence of the entries of $X$ we have, using (3.3),

The error made in the approximation $G_{aa}\approx m_{\phi}$ is of order $\Psi$ by (5.3), so that the corresponding error term on the right-hand side of (5.8) may be bounded using (3.3) by

We conclude that the simple replacement of $G_{aa}$ with its deterministic approximation in (5.8) is not affordable. Not only the leading term but also every error term has to be expanded in the entries of $X$. This expansion is most effectively controlled if performed within a high-moment estimate. Thus, for large and even $p$ we shall estimate

Before explaining the general strategy, we sketch a second moment calculation. First, we write

Using (3.7), we maximally expand all resolvent entries in the indices $a,b,c,d$. This means that we use (3.7) repeatedly until each term in the expansion is independent of all Latin indices that do not explicitly appear among its lower indices; here an entry is independent of an index if that index is an upper index of the entry. This generates a series of maximally expanded terms, whereby a resolvent entry is by definition maximally expanded if we cannot add to it upper indices from the set $a,b,c,d$ by using the identity (3.7). In other words, $G_{ij}^{(T)}$ is maximally expanded if and only if $T=\{a,b,c,d\}\setminus\{i,j\}$.

To illustrate this procedure, we assume temporarily that $a,b,c,d$ are all distinct, and write, using (3.7),

We get a similar expression for $G_{cd}^{*}$. We plug both of these expansions into (5.10) and multiply out the product. The leading term is

We now expand both resolvent entries using (3.9), which gives

The goal is to use the expectation to get a pairing (or a more general partition) of the entries of $X$. In order to do that, we shall require all terms that are not entries of $X$ to be independent of the randomness in the rows $a,b,c,d$ of $X$. While the entries of $R$ satisfy this condition, the entries of $G$ do not. We shall hence have to perform a further expansion on them using the identities (3.7) and (3.9). In fact, these two types of expansions will have to be performed in tandem, using a two-step recursive procedure. The main reason behind this is that even if all entries of $G$ are maximally expanded, each application of (3.9) produces a diagonal entry that is not maximally expanded; for such terms the expansion using (3.7) has to be repeated. For the purposes of this sketch, however, we omit the details of the further expansion of the entries of $G$, and replace them with their deterministic leading order, $m_{\phi}$ (see (5.3)). This approximation gives

Since all entries of $R$ are independent of all entries of $X$, we can compute the expectation with respect to the rows $a,b,c,d$. Note that the only possible pairing is $a=d$, $\mu=\beta$, $b=c$, and $\nu=\alpha$. This results in the expression

This calculation, while giving the right order, was in fact an oversimplification, since the expansion (5.11) required that $b\neq c$ and $d\neq a$. The correct argument requires first a decomposition of the summation over $a,b,c,d$ into a finite number of terms, indexed by the partitions of four elements, according to the coincidences among these four indices. Thus, we write

where a star over the summation indicates that all summation indices that are not explicitly equal to each other have to be distinct. The above calculation leading to (5.12) is valid for the first summation of (5.13), whose contribution (up to leading order) is zero, since the only possible pairing contradicts the condition that the indices $a,b,c,d$ be all distinct. It is not too hard to see that, among the sums in (5.13), only the last one gives a nonzero contribution (up to leading order), and it is, going back to (5.10), equal to

Next, we consider a subleading term from the first summation in (5.13), which has three off-diagonal entries:

We proceed as before, expanding all off-diagonal entries of $G$ using (3.9). Up to leading order, we get

The expectation again renders this term zero if $a,b,c,d$ are distinct.

Based on these preliminary heuristics, we outline the main steps in estimating a high moment of $\mathcal{Z}$.

Partition the indices in (5.9) according to their coincidence structure: indices in the same block of the partition are required to coincide and indices in different blocks are required to be distinct. This leads to a reduced family, $T$, of distinct indices.

Make all entries of $G$ maximally expanded by repeatedly applying the identity (3.7). Roughly, this entails adding upper indices from the family $T$ to each entry of $G$ using the identity (3.7). We stop the iteration if either (3.7) cannot be applied to any entry of $G$ or we have generated a sufficiently large number of off-diagonal entries of $G$.

Apply (3.9) to each maximally expanded off-diagonal entry of $G$. This yields factors of the form $\sum_{\mu,\nu}X_{a\mu}R^{(T)}_{\mu\nu}X_{\nu b}^{*}$ with $a,b\in T$ and $R^{(T)}$ is independent of all entries of $X$ by construction. In addition, this application of (3.9) produces new diagonal entries of $G$ that are not maximally expanded.

Repeat Steps 2 and 3 recursively in tandem until we only have a sum of terms whose factors consist of maximally expanded diagonal entries of $G$, entries of $R^{(T)}$, and entries of $X$ from the rows indexed by $T$.

Apply (3.8) to each maximally expanded diagonal entry of $G$. We end up with factors consisting only of entries of $R^{(T)}$ and entries of $X$ from the rows indexed by $T$.

Using the fact that all entries of $R$ are independent of all entries of $X$, take a partial expectation over the rows of $X$ indexed by the set $T$; this only involves the entries of $X$. Only those terms give a nonzero contribution whose Greek indices have substantial coincidences.

Steps 1–6 require a careful expansion algorithm and a meticulous bookkeeping of the resulting terms. We shall develop a graphical language that encodes the resulting monomials. Expansion steps will be recorded via operations on graphs such as merging certain vertices or replacing some vertex or edge by a small subgraph. Several ingredients of the graphical representation and the concept of graph operations are inspired by tools from EKY2 developed for random band matrices. Once the appropriate graphical language is in place and the expansion algorithm has been constructed, the observations in Steps 7 and 8 will yield the desired estimate by a power counting coupled with a parity argument.

4. The p𝑝p-th moment of 𝒵𝒵\mathcal{Z} and introduction of graphs

We shall estimate $\mathcal{Z}$ with high probability by estimating its $p$-th moment for a large but fixed $p$. It is convenient to rename the summation variables in the definition of $\mathcal{Z}$ as $(a,b)=(b_{1},b_{2})$. Let $p$ be an even integer and write

where we recall the definition of $\mathcal{Z}$ from (5.6).

We shall perform the summation by first fixing the partition $P\in\mathfrak{P}_{p}$ and by deriving an upper bound that is uniform in $P$; at the very end we shall sum trivially over $P\in\mathfrak{P}_{p}$.

In order to handle expressions of the form (5.15), as well as more complicated ones required in later stages of the proof, we shall need to develop a graphical notation. The basic idea is to associate matrix indices with vertices and resolvent entries with edges. The following definition introduces graphs suitable for our purposes.

By a graph we mean a finite, directed, edge-coloured, multigraph

Here $V$ is a finite set of vertices, $E$ a finite set of directed edges, and $\xi$ is a “colouring of $E$”, i.e. a mapping from $E$ to some finite set of colours. The graph $\Gamma$ may have multiple edges and loops. More precisely, $E$ is some finite set with maps $\alpha,\beta\mathrel{\mathop{:}}E\to V$; here $\alpha(e)$ and $\beta(e)$ represent the source and target vertices of the edge $e\in E$. We denote by $\deg_{\Gamma}(i)$ the degree of the vertex $i\in V(\Gamma)$.

We may now express the right-hand side of (5.15) using graphs. Fix the partition $P\in\mathfrak{P}_{p}$. We associate a graph $\Delta\equiv\Delta(P)$ with $P$ as follows. The vertex set $V(\Delta)$ is given by the blocks of $P$, i.e. $V(\Delta)=P$. The set of colours, i.e. the range of $\xi$, is $\{G,G^{*}\}$ (we emphasize that these two colours are simply formal symbols whose name is supposed to evoke their meaning). The set of edges $E(\Delta)$ is parametrized as follows by the resolvent entries on the right-hand side of (5.15). Each resolvent entry $G_{b_{k1}b_{k2}}^{\#}$ gives rise to an edge $e\in E(\Delta)$ with colour $\xi(e)=G$ if $\#$ is nothing and $\xi(e)=G^{*}$ if $\#$ is $*$. The source vertex $\alpha(e)$ of this edge is the unique block of $P$ satisfying $(k,1)\in\alpha(e)$, and its target vertex $\beta(e)$ the unique block of $P$ satisfying $(k,2)\in\beta(e)$. Figure 5.1 illustrates the construction of $\Delta(P)$, where the two different types of line correspond to the two colours $G,G^{*}$. The graph $\Delta$ has no loops.

We record the following basic properties of $\Delta$.

$\Delta$ has no loops, i.e. $\alpha(e)\neq\beta(e)$ for all $e\in E(\Delta)$.

$1\leqslant\lvert V(\Delta)\rvert\leqslant 2p$.

5. Generalized colours and encoding

We shall need to enlarge the set of colours of edges, so as to be able to encode entries of not only $\widetilde{G}$ and $\widetilde{G}^{*}$, but also entries of $R$, $R^{*}$, $X$, and $X^{*}$; in addition, we shall need to encode diagonal entries of $\widetilde{G}$ and $\widetilde{G}^{*}$ that are in the denominator, as in the formulas (3.7), as well as to keep track of upper indices. We need all of these factors, since our expansion relies on a repeated application of the identities (3.7), (3.8), and (3.9).

In order to define the graphs precisely, we consider graphs $\Gamma$ satisfying Definition 5.3 whose vertex set $V(\Gamma)=V_{b}(\Gamma)\cup V_{w}(\Gamma)$ is partitioned into black vertices $V_{b}(\Gamma)$ and white vertices $V_{w}(\Gamma)$. Informally, black vertices are incident to edges encoding entries of $\widetilde{G}$ and $\widetilde{G}^{*}$, and white vertices to edges encoding entries of $\widetilde{R}$ and $\widetilde{R}^{*}$. In other words, black vertices are associated with Latin summation indices in the population space $\{1,\dots,M\}$; white vertices are associated with Greek summation indices in the sample space $\{1,\dots,N\}$. See Remark 3.4. We shall only consider graphs $\Gamma$ satisfying

an assumption we make throughout the following. This means that only new Greek summation indices but no new Latin indices are generated, corresponding to the repeated applications of (3.8) and (3.9). In particular, the vertex colouring for our graph is very simple: the vertices of $\Delta$ are black and all other vertices are white.

We now list some properties of all graphs we shall consider. To that end, we call $e\in E(\Gamma)$ a $G$-edge if $\xi_{1}(e)\in\{G,G^{*}\}$, an $R$-edge if $\xi_{1}(e)\in\{R,R^{*}\}$, and an $X$-edge if $\xi_{1}(e)\in\{X,X^{*}\}$.

If $e$ is a $G$-edge then $\alpha(e),\beta(e)\in V_{b}(\Gamma)$.

If $e$ is an $R$-edge then $\alpha(e),\beta(e)\in V_{w}(\Gamma)$.

If $\xi_{1}(e)=X$ then $\alpha(e)\in V_{b}(\Gamma)$ and $\beta(e)\in V_{w}(\Gamma)$.

If $\xi_{1}(e)=X^{*}$ then $\alpha(e)\in V_{w}(\Gamma)$ and $\beta(e)\in V_{b}(\Gamma)$.

If $\xi_{2}(e)=-$ then $\xi_{1}(e)\in\{G,G^{*}\}$ and $\alpha(e)=\beta(e)$.

If $\xi_{3}(e)\neq\emptyset$ then $\xi_{1}(e)\in\{G,G^{*}\}$ and $\xi_{3}(e)\subset V_{b}(\Gamma)\setminus\{\alpha(e),\beta(e)\}$.

Properties (i)–(iv) are straightforward compatibility conditions which are obvious in light of the type of matrix entry that the edge $e$ encodes. Property (v) states that only diagonal entries of $\widetilde{G}$ and $\widetilde{G}^{*}$ may be in the denominator. Property (vi) states that only entries of $G$ or $\widetilde{G}$ may have a (nontrivial) upper index and the lower indices of an entry of $\widetilde{G}$ or $\widetilde{G}^{*}$ may not coincide with its upper indices (by definition of minors).

For $e\in E(\Gamma)$ with $\xi_{1}(e)\in\{G,G^{*}\}$ we define the resolvent entry encoded by $e$ in $\Gamma$ as

When drawing graphs, we represent a black vertex as a black dot and a white vertex as a white dot. An edge with $\xi_{1}=G$ is represented as a solid directed line joining two black dots, and an edge with $\xi_{1}=G^{*}$ as a dashed directed line joining two black dots. If $\xi_{2}=-$ we indicate this by decorating the edge with a white diamond (not to be confused with a white dot). Notice that such edges are always loops, according to property (v). Sometimes we also indicate the component $\xi_{3}(e)$ in our graphs, simply by writing it next to the edge $e$. See Figure 5.2 for our graphical conventions when depicting edges with $\xi_{1}\in\{G,G^{*}\}$.

For the other edges, $e\in E(\Gamma)$ with $\xi_{1}(e)\in\{R,R^{*},X,X^{*}\}$, we set

When drawing graphs, we represent an edge with $\xi_{1}=R$ as a solid directed line joining two white vertices, an edge with $\xi_{1}=R^{*}$ as a dashed directed line joining two white vertices, an edge with $\xi_{1}=X$ as a dotted directed line from a black to a white vertex, and an edge with $\xi_{1}=X^{*}$ as a dotted directed line from a white to a black vertex. Note that we use the same line style to draw $X$- and $X^{*}$-edges, since the orientation of the edge together with the vertex colouring distinguishes them uniquely. See Figure 5.3 for an illustration of these conventions, and Figure 5.6 for an illustration of (5.28).

6. R𝑅R-groups

We define an $R$-group to be an induced subgraph of $\Gamma$ consisting of three edges, $e_{1}$, $e_{2}$, $e_{3}$, such that $e_{1}$ and $e_{3}$ are $X$-edges and $e_{2}$ is an $R$-edge, and they form a chain in the sense that $\beta(e_{1})=\alpha(e_{2})$, $\beta(e_{2})=\alpha(e_{3})$, and both of these vertices have degree two. We call $e_{2}$ the centre of the $R$-group and define $A(e_{2})\mathrel{\mathop{:}}=\alpha(e_{1})$ and $B(e_{2})\mathrel{\mathop{:}}=\beta(e_{3})$. If $A(e_{2})=B(e_{2})$ we call the $R$-group diagonal; otherwise we call it off-diagonal. See Figure 5.4 for an illustration.

We require that our graphs $\Gamma$ satisfy the following property.

Each $X$-edge and $R$-edge of $\Gamma$ belongs to some $R$-group of $\Gamma$. In particular, all white vertices have degree two, and an $R$-group is uniquely determined by its centre.

The $R$-groups constitute graphical representations of the monomials on the right-hand sides of (3.8) and (3.9). It is important to stress that there is no restriction on possible coincidences among the white-vertex indices $(a_{i})_{i\in V_{w}}$; this means that even if two Greek summation indices arising from two different applications (3.8) or (3.9) coincide, they will nevertheless be encoded by distinct white vertices. This allows us to keep the graphical structure involving $R$ and $X$ edges very simple.

Note that the initial graph $\Delta=\Delta(P)$ trivially satisfies the properties (i)–(vii).

7. Maximally expanded edges and sketch of the expansion

The following definition introduces a notion that underlies our entire expansion. Note that it only applies to $G$-edges.

The expansion relies of three main operations:

make one of the $G$-entries maximally expanded by adding upper indices using the identity (3.7);

expand all off-diagonal maximally expanded $G$-entries of in terms of $X$ using the identity (3.9);

expand all diagonal maximally expanded $G$-entries in terms of $X$ using (3.8).

We shall implement each ingredient by a graph surgery procedure. Operation (a) is the subject of Section 5.8; it creates two new graphs, $\tau_{0}(\Gamma)$ and $\tau_{1}(\Gamma)$, from an initial graph $\Gamma$. Operation (b) is the subject of Section 5.9; it creates one new graph, $\rho(\Gamma)$, from an initial graph $\Gamma$. As it turns out, Operations (a) and (b) have to be performed in tandem using a coupled recursion, described by a tree $\mathcal{T}$, which is the subject of Section 5.10. Once this recursion has terminated, Operation (c) may be performed (see Section 5.11).

In order to avoid trivial ambiguities, we choose and fix an arbitrary ordering of the vertices $V(\Delta)$ and of the family of resolvent entries $({\widetilde{G}_{ab}^{(T)}\mathrel{\mathop{:}}a,b\notin T})$. Hence we may speak of the first vertex of $V(\Delta)$ and the first factor of a monomial in the entries $\widetilde{G}_{ab}^{(T)}$.

We now describe Operation (a) of the expansion. It relies on the identities

Moreover, it follows immediately that the maps $\tau_{0}$ and $\tau_{1}$ do not change the vertices, so that we have

The procedure $\Gamma\mapsto(\tau_{0}(\Gamma),\tau_{1}(\Gamma))$ may also be explicitly described on the level graphs alone, but we shall neither need nor do this. Instead, we give a graphical depiction of this process in Figure 5.5.

If $\Gamma$ satisfies the properties (i)–(vii) from Sections 5.5 and 5.6 then so do $\tau_{0}(\Gamma)$ and $\tau_{1}(\Gamma)$.

9. Operation (b): construction of the graph ρ​(Γ)𝜌Γ\rho(\Gamma)

In this section we give the second operation, (b), outlined in Section 5.7. The idea is that Operation (a) from Section 5.5 generates off-diagonal $G$-entries that are maximally expanded. They in turn will have to be expanded further using (3.9), so as to extract their explicit $X$-dependence. Roughly, the map $\rho$ replaces each maximally expanded off-diagonal $G$-edge by an off-diagonal $R$-group.

where $\widetilde{z}^{*}$ denotes the complex conjugate of $\widetilde{z}$. Note that the first diagonal term on the right-hand side is not maximally expanded (while the second one is).

Like $\tau_{0}$ and $\tau_{1}$, the map $\rho$ may be explicitly defined on the level of graphs, which we shall however not do in order to avoid unnecessary and heavy notation. See Figure 5.6 for an illustration of $\rho$.

The following result is an immediate corollary of the definition of $\rho$.

If $\Gamma$ satisfies the properties (i)–(vii) from Sections 5.5 and 5.6 then so does $\rho(\Gamma)$.

10. Constructing the tree 𝒯𝒯\mathcal{T}: recursion using (a) and (b)

The algorithm generates a family of graphs $\Theta_{\sigma}$ which are indexed by finite binary strings $\sigma$, or, equivalently, by vertices of a rooted binary tree $\mathcal{T}=(V(\mathcal{T}),E(\mathcal{T}))$. We start the algorithm with $\Theta_{\emptyset}\mathrel{\mathop{:}}=\Delta$, corresponding to the empty string or the root of the tree. The tree is constructed recursively according to

and so on, until a stopping rule is satisfied (see Definition 5.7 below). See Figure 5.7 for an illustration of the resulting tree.

The construction of the tree $\mathcal{T}$ relies on the following stopping rule.

The tree $\mathcal{T}$, along with the graphs $(\Theta_{\sigma})_{\sigma\in V(\mathcal{T})}$, is constructed recursively from the trivial tree, consistsing of the single vertex $\emptyset$ with $\Theta_{\emptyset}=\Delta$, as follows. Let $\sigma$ be a leaf of the tree such that $\Theta_{\sigma}$ does not satisfy the stopping rule. We add the children of $\sigma$, i.e. $0\sigma$ and $1\sigma$, to the tree, and set

We continue this recursion on each leaf until all leaves satisfy the stopping rule from Definition 5.7. By Lemma 5.9 below, the resulting tree $\mathcal{T}$ is finite, i.e. the recursion terminates after a finite number of steps.

The graphs $\Theta_{\sigma}$ have the following two properties. First,

In particular, the set of black vertices remains unchanged throughout the recursion: $V_{b}(\Theta_{\sigma})=V_{b}(\Delta)$. Second,

Moreover, each $\Theta_{\sigma}$ for $\sigma\in V(\mathcal{T})$ satisfies the properties (i)–(vii) from Sections 5.5 and 5.6.

The identity (5.32) follows immediately from (5.27) and (5.30). Similarly, (5.33) follows from (5.26) and (5.29). The final statement follows immediately from Lemmas 5.5 and 5.6. ∎

The interpretation of (5.33) is that the value of any graph $\Theta_{\sigma}$ is equal to the sum of the values of its two children, $\Theta_{0\sigma}$ and $\Theta_{1\sigma}$.

Next, we express $Y(\Delta)$ from (5.17) in terms of the graphs we just introduced. By Lemma 5.8 and the fact that $V_{b}(\Delta)=V(\Delta)$, we have for all $\sigma\in V(\mathcal{T})$ that

Let $L(\mathcal{T})\subset V(\mathcal{T})$ denote the leaves of $\mathcal{T}$. The identity (5.33) states that if $\sigma\in V(\mathcal{T})$ is not a leaf of $\mathcal{T}$, we may replace the value of $\Theta_{\sigma}$ by the sum of the values of its two children. Starting from the root $\emptyset$ and the graph $\Theta_{\emptyset}=\Delta$, we may propagate this identity recursively from the root down to the leaves. We conclude that

Recalling the definition (5.17) of $Y(\Delta)$, we get the following result.

The quantity $Y(\Delta)$ defined in (5.17) may be written in terms of the tree $\mathcal{T}$ as

By Definition 5.7, if $\sigma\in L_{1}(\mathcal{T})$ is a nontrivial leaf then all $G$-edges of $\Theta_{\sigma}$ are diagonal and maximally expanded. The estimate of the nontrivial leaves will be performed in Sections 5.12–5.14.

11. The trivial leaves

In this section we estimate the contribution of $\Theta_{\sigma}$ for a trivial leaf $\sigma\in L_{0}(\mathcal{T})$. Thus, fix $\sigma\in L_{0}(\mathcal{T})$. From (5.28) and Lemma 5.2 we get for $a\neq b$

We therefore conclude that each off-diagonal $R$-group of $\Gamma$ yields a contribution of size $O_{\prec}(\phi^{-1/2}\Psi)$ after summation over the indices associated with the vertices incident to its centre. Moreover, by definition of $\mathcal{T}$, each $R$-group of $\Theta_{\sigma}$ is off-diagonal. In addition, each off-diagonal $G$-edge yields a contribution of size $\phi^{-1/2}\Psi$ by Lemma 5.2. Thus we get, summing out all indices associated with white vertices (i.e. inner vertices of $R$-groups),

Hence the contribution of $\Theta_{\sigma}$ to the right-hand side of (5.36) may be bounded by

For any $p$ there exists a constant $C_{p}$ such that for any graph $\Gamma$ and any $e\in E(\Gamma)$ we have

The cases $\xi_{1}(e)\in\{G,G^{*},R,R^{*}\}$ and $\xi_{2}(e)=+$ are dealt with the deterministic estimates