2.1 TRACES,MOMENTS AND COMBINATORICS 27 6 5 5 Fig.2.1.3.Two inequivalent FK sentences xx2 corresponding to (solid line)b 141252363 and (dashed line)c=1712 (in left)~3732 (in right). sentence a with graph Ga,let G=(V,E)be the graph with vertex set Va=Vl and edge set Ed=fe E Ea:Na =1).Clearly,when a is an FK sentence,Ga is always a forest,that is a disjoint union of trees. Lemma 2.1.25 Suppose b is an FK sentence with n-1 words and c is an FK word with skeleton s...sr such that s E supp(b).Let e be the largest index such that st∈supp b,and set d=s1…st.Then a=(b,c）is an FK sentence only if suppbnsuppc=suppd and d is a geodesic in G (A geodesic connecting x,yEG is a path of minimal length starting at x and terminating at y.)A consequence of Lemma 2.1.25 is that there exist at most (wt(b))2equivalence classes of FK sentences x1,....such that bx1,... and cxn.See Figure 2.1.6 for an example of two such equivalence classes and their pictorial description. Before providing the proof of Lemma 2.1.25,we explain how it leads to Completion of proof of Lemma 2.1.23 Let r(t,C,m)denote the set of equiva- lence classes of FK sentences a=(w1,...,wm)consisting of m words,with total length (wi)=e and wt(a)=t.An immediate corollary of Lemma 2.1.25 is that (2.1.34) Indeed,there are ce.m : e-1 m-1 m-tuples of positive integers summing to e, and thus at most 2-mcm equivalence classes of sentences consisting of m pair- wise disjoint FK words with sum of lengths equal to e.Lemma 2.1.25 then shows
2.1 TRACES, MOMENTS AND COMBINATORICS 27 1 2 3 4 5 6 7 1 2 3 4 5 7 6 Fig. 2.1.3. Two inequivalent FK sentences [x1,x2] corresponding to (solid line) b = 141252363 and (dashed line) c = 1712 (in left) ∼ 3732 (in right). sentence a with graph Ga, let G 1 a = (V 1 a ,E 1 a ) be the graph with vertex set Va = V 1 a and edge set E 1 a = {e ∈ Ea : N a e = 1}. Clearly, when a is an FK sentence, G 1 a is always a forest, that is a disjoint union of trees. Lemma 2.1.25 Suppose b is an FK sentence with n − 1 words and c is an FK word with skeleton s1 ···sr such that s1 ∈ supp(b). Let ℓ be the largest index such that sℓ ∈ suppb, and set d = s1 ···sℓ . Then a = (b,c) is an FK sentence only if suppb∩suppc = suppd and d is a geodesic in G1 b . (A geodesic connecting x,y ∈ G 1 b is a path of minimal length starting at x and terminating at y.) A consequence of Lemma 2.1.25 is that there exist at most (wt(b))2 equivalence classes of FK sentences x1,...,xn such that b ∼ x1,...,xn−1 and c ∼ xn. See Figure 2.1.6 for an example of two such equivalence classes and their pictorial description. Before providing the proof of Lemma 2.1.25, we explain how it leads to Completion of proof of Lemma 2.1.23 Let Γ(t,ℓ,m) denote the set of equivalence classes of FK sentences a = (w1,...,wm) consisting of m words, with total length ∑ m i=1 ℓ(wi) = ℓ and wt(a) = t. An immediate corollary of Lemma 2.1.25 is that |Γ(t,ℓ,m)| ≤ 2 ℓ−m t 2(m−1) ℓ−1 m−1 . (2.1.34) Indeed, there are cℓ,m := ℓ−1 m−1 m-tuples of positive integers summing to ℓ, and thus at most 2ℓ−mcℓ,m equivalence classes of sentences consisting of m pairwise disjoint FK words with sum of lengths equal to ℓ. Lemma 2.1.25 then shows
28 2.WIGNER MATRICES that there are at most 2(m-1)ways to "glue these words into an FK sentence", whence(2.1.34)follows. For any FK sentence a consisting of m words with total length e,we have that m=Eal-2wt(a)+2+e. (2.1.35) Indeed,the word obtained by concatenating the words of a generates a list ofe-I (not necessarily distinct)unordered pairs of adjoining letters,out of which m-I correspond to commas in the FK sentence a and 2Ea-E correspond to edges of Ga.Using that |Eal =Va-1,(2.1.35)follows. Consider a word wE that is parsed into an FK sentence w'consisting of m words.Note that if an edge e is retained in Gw,then no comma is inserted at e at the first and second passage on e(but is introduced if there are further passages on e).Therefore,E=0.By (2.1.35),this implies that for such words, m-1 =k+2-2t.Inequality (2.1.34)then allows one to conclude the proof of Lemma 2.1.23. 0 Proof of Lemma 2.1.25 Assume a is an FK sentence.Then,Ga is a tree,and since the Wigner words composing c are disjoint,d is the unique geodesic in Ge C Ga connecting si to se.Hence,it is also the unique geodesic in GC Ga connecting sI to se.But d visits only edges of G that have been visited exactly once by the constituent words of b,for otherwise(b,c)would not be an FK sentence (that is,a comma would need to be inserted to split c).Thus,EdC E.Since c is an FK word,E=Ess..Since a is an FK sentence,EnEe=EnE.Thus, EnEc=Ed.But,recall that Ga,Go,Ge,Gd are trees,and hence Val 1+Eal =1+Epl+Ecl-EpnEcl =1+Ebl+Ecl-Eal 1+Ebl+1+Ecl-1-Eal=Vl+Vel-Val. Since IVol+Vel-vnVel Val,it follows that IVal =VinVel.Since Va c VonVe,one concludes that Va=vonve,as claimed. Remark 2.1.26 The result described in Theorem 2.1.22 is not optimal,in the sense that even with uniform bounds on the(rescaled)entries,i.e.rk uniformly bounded, the estimate one gets on the displacement of the maximal eigenvalue to the right of2 is(og),whereas the true displacement is known to be oforder3 (see Section 2.7 for more details,and,in the context of complex Gaussian Wigner matrices,see Theorems 3.1.4 and 3.1.5). Exercise 2.1.27 Prove that the conclusion of Theorem 2.1.22 holds with conver- gence in probability replaced by either almost sure convergence or LP conver- gence
28 2. WIGNER MATRICES that there are at most t 2(m−1) ways to “glue these words into an FK sentence”, whence (2.1.34) follows. For any FK sentence a consisting of m words with total length ℓ, we have that m = |E 1 a | −2wt(a)+2+ℓ. (2.1.35) Indeed, the word obtained by concatenating the words of a generates a list of ℓ−1 (not necessarily distinct) unordered pairs of adjoining letters, out of which m−1 correspond to commas in the FK sentence a and 2|Ea| − |E 1 a | correspond to edges of Ga. Using that |Ea| = |Va| −1, (2.1.35) follows. Consider a word w ∈ Wk,t that is parsed into an FK sentence w ′ consisting of m words. Note that if an edge e is retained in Gw′ , then no comma is inserted at e at the first and second passage on e (but is introduced if there are further passages on e). Therefore, E 1 w′ = /0. By (2.1.35), this implies that for such words, m − 1 = k + 2 − 2t. Inequality (2.1.34) then allows one to conclude the proof of Lemma 2.1.23. ⊓⊔ Proof of Lemma 2.1.25 Assume a is an FK sentence. Then, Ga is a tree, and since the Wigner words composing c are disjoint, d is the unique geodesic in Gc ⊂ Ga connecting s1 to sℓ . Hence, it is also the unique geodesic in Gb ⊂ Ga connecting s1 to sℓ . But d visits only edges of Gb that have been visited exactly once by the constituent words of b, for otherwise (b,c) would not be an FK sentence (that is, a comma would need to be inserted to split c). Thus, Ed ⊂ E 1 b . Since c is an FK word, E 1 c = Es1···sr . Since a is an FK sentence, Eb ∩Ec = E 1 b ∩E 1 c . Thus, Eb ∩Ec = Ed. But, recall that Ga, Gb, Gc, Gd are trees, and hence |Va| = 1+|Ea| = 1+|Eb|+|Ec| − |Eb ∩Ec| = 1+|Eb|+|Ec| − |Ed| = 1+|Eb|+1+|Ec| −1− |Ed| = |Vb|+|Vc| − |Vd|. Since |Vb| + |Vc| − |Vb ∩Vc| = |Va|, it follows that |Vd| = |Vb ∩Vc|. Since Vd ⊂ Vb ∩Vc, one concludes that Vd = Vb ∩Vc, as claimed. ⊓⊔ Remark 2.1.26 The result described in Theorem 2.1.22 is not optimal, in the sense that even with uniform bounds on the (rescaled) entries, i.e. rk uniformly bounded, the estimate one gets on the displacement of the maximal eigenvalue to the right of 2 is O(n −1/6 logn), whereas the true displacement is known to be of order n −2/3 (see Section 2.7 for more details, and, in the context of complex Gaussian Wigner matrices, see Theorems 3.1.4 and 3.1.5). Exercise 2.1.27 Prove that the conclusion of Theorem 2.1.22 holds with convergence in probability replaced by either almost sure convergence or L p convergence
2.1 TRACES,MOMENTS AND COMBINATORICS 29 Exercise 2.1.28 Prove that the statement of Theorem 2.1.22 can be strengthened to yield that for some constant 6=(C)>0,N (-2)converges to 0,almost surely. Exercise 2.1.29 Assume that for some constants >0,C,the independent (but not necessarily identically distributed)entries [XN(i,)N of the symmetric matrices Xy satisfy supE(e2wl≤C. I.NV Prove that there exists a constant c=c(C)such that limsup<c,almost surely,and lim supNE<c1. Exercise 2.1.30 We develop in this exercise an alternative proof,that avoids mo- ment computations,to the conclusion of Exercise 2.1.29,under the stronger as- sumption that for some>0, supE(e2ww')≤C. i.iN a)Prove(using Chebyshev's inequality and the assumption)that there exists a con- stant co independent of N such that for any fixed=RN,and all C large enough, P(ll=TXvll2 >C)<e-cocN. (2.1.36) b)Let be a minimal deterministic net in the unit ball of R,that is1,supinf,and Ns is the minimal integer with the property that such a net can be found.Check that (1-82)sup XN=<supXN+2sup sup X=i. (2.1.37) l2=1 =∈5 i=:le-l2≤8 c)Combine steps a)and b)and the estimate N<c,valid for some c>0,to conclude that there exists a constant c2 independent of N such that for all C large enough.independently of N. P(AN>C)=P(sup TXN=>C)<e-acN. l2=1 2.1.7 Central limit theorems for moments Our goal here is to derive a simple version of a central limit theorem (CLT) for linear statistics of the eigenvalues of Wigner matrices.With XN a Wigner
2.1 TRACES, MOMENTS AND COMBINATORICS 29 Exercise 2.1.28 Prove that the statement of Theorem 2.1.22 can be strengthened to yield that for some constant δ = δ(C) > 0, N δ (λ N N −2) converges to 0, almost surely. Exercise 2.1.29 Assume that for some constants λ > 0, C, the independent (but not necessarily identically distributed) entries {XN(i, j)}1≤i≤j≤N of the symmetric matrices XN satisfy sup i, j,N E(e λ √ N|XN(i, j)| ) ≤ C. Prove that there exists a constant c1 = c1(C) such that limsupN→∞ λ N N ≤ c1, almost surely, and limsupN→∞ Eλ N N ≤ c1. Exercise 2.1.30 We develop in this exercise an alternative proof, that avoids moment computations, to the conclusion of Exercise 2.1.29, under the stronger assumption that for some λ > 0, sup i, j,N E(e λ( √ N|XN(i, j)|) 2 ) ≤ C. a) Prove (using Chebyshev’s inequality and the assumption) that there exists a constant c0 independent of N such that for any fixed z ∈ R N, and all C large enough, P(kz TXNk2 > C) ≤ e −c0C 2N . (2.1.36) b) Let Nδ = {zi} Nδ i=1 be a minimal deterministic net in the unit ball of R N, that is kzik2 = 1, supz:kzk2=1 infi kz−zik2 ≤ δ, and Nδ is the minimal integer with the property that such a net can be found. Check that (1−δ 2 ) sup z:kzk2=1 z TXNz ≤ sup zi∈Nδ z T i XNzi +2sup i sup z:kz−zik2≤δ z TXNzi . (2.1.37) c) Combine steps a) and b) and the estimate Nδ ≤ c N δ , valid for some cδ > 0, to conclude that there exists a constant c2 independent of N such that for all C large enough, independently of N, P(λ N N > C) = P( sup z:kzk2=1 z TXNz > C) ≤ e −c2C 2N . 2.1.7 Central limit theorems for moments Our goal here is to derive a simple version of a central limit theorem (CLT) for linear statistics of the eigenvalues of Wigner matrices. With XN a Wigner
30 2.WIGNER MATRICES matrix and Ly the associated empirical measure of its eigenvalues,set W.:= N[Lw,x)-(亿w,rI.Let =J- e-rPdu denote the Gaussian distribution.We set o as in(2.1.44)below,and prove the following. Theorem 2.1.31 The law of the sequence of random variables WN.k/Ok converges weakly to the standard Gaussian distribution.More precisely. lim P sx=(, (2.1.38) N-t0o Proof of Theorem 2.1.31 Most of the proof consists of a variance computation. The reader interested only in a proof of convergence to a Gaussian distribution (without worrying about the actual variance)can skip to the text following equa- tion(2.1.45) Recall the notationc.f.(2.1.24).Using (2.126).we have imE(保k) (2.1.39) =m2E(Lw,2)-(亿w,x2 ∑[Π(Z9)ΠE() a=(w1,w2)e因 -E(Z)L')ΠEZ)ΠE()] We note next that if a=()then G is connected and possesses vertices and at most k edges,each visited at least twice by the paths generated by a.Hence,with k vertices,G possesses eitherorkedges.Letdenote the subset ofsuch that k(that is,a is uicyclic,i.e."possesses one edge too many to be a tree")and letdenote the subset ofsuch that Eal=k-1. Suppose first aThen,Ga is a tree,,and necessarily is a subtree of Ga.This implies that k is even and that E<k/2.In this case,for EE one must have =k/2,which implies that all edges of G,are visited twice by the walk generated by wi,and exactly one edge is visited twice by both w and w2.In particular,wi are both closed Wigner words of length k+1
30 2. WIGNER MATRICES matrix and LN the associated empirical measure of its eigenvalues, set WN,k := N[hLN,x k i − hL¯N,x k i]. Let Φ(x) = 1 √ 2π Z x −∞ e −u 2/2 du denote the Gaussian distribution. We set σ 2 k as in (2.1.44) below, and prove the following. Theorem 2.1.31 The law of the sequence of random variables WN,k/σk converges weakly to the standard Gaussian distribution. More precisely, lim N→∞ P WN,k σk ≤ x = Φ(x). (2.1.38) Proof of Theorem 2.1.31 Most of the proof consists of a variance computation. The reader interested only in a proof of convergence to a Gaussian distribution (without worrying about the actual variance) can skip to the text following equation (2.1.45). Recall the notation W (2) k,t , c.f. (2.1.24). Using (2.1.26), we have lim N→∞ E(W2 N,k ) (2.1.39) = lim N→∞ N 2 h E(hLN,x k i 2 )− hL¯N,x k i 2 i = ∑ a=(w1,w2)∈W (2) k,k h ∏e∈Ec a E(Z N a e 1,2 ) ∏e∈Es a E(Y N a e 1 ) − ∏e∈Ec w1 E(Z N w1 e 1,2 ) ∏e∈Es w1 E(Y N w1 e 1 ) ∏e∈Ec w2 E(Z N w2 e 1,2 ) ∏e∈Es w2 E(Y N w2 e 1 ) i . We note next that if a = (w1,w2) ∈ W (2) k,k then Ga is connected and possesses k vertices and at most k edges, each visited at least twice by the paths generated by a. Hence, with k vertices, Ga possesses either k −1 or k edges. Let W (2) k,k,+ denote the subset of W (2) k,k such that |Ea| = k (that is, Ga is unicyclic, i.e. “possesses one edge too many to be a tree”) and let W (2) k,k,− denote the subset of W (2) k,k such that |Ea| = k −1. Suppose first a ∈ W (2) k,k,− . Then, Ga is a tree, E s a = /0, and necessarily Gwi is a subtree of Ga. This implies that k is even and that |Ewi | ≤ k/2. In this case, for Ew1 ∩Ew2 6= /0 one must have |Ewi | = k/2, which implies that all edges of Gwi are visited twice by the walk generated by wi , and exactly one edge is visited twice by both w1 and w2. In particular, wi are both closed Wigner words of length k+1
2.1 TRACES,MOMENTS AND COMBINATORICS 31 The emerging picture is of two trees with k/2 edges each"glued together"at one edge.Since there are C/2 ways to chose each of the trees,k/2 ways of choosing (in each tree)the edge to be glued together,and 2 possible orientations for the gluing,we deduce that w1=2()' (2.1.40) Further,for each a (Z3)ΠE) e4$)盟0黑e)盟0】 E(Z2)E(Z2-2-[E(Z2 =E(Z2)-1. (2.1.41) Wenext um to coniderIn orderto swe need to understand the structure of unicyclic graphs. Definition 2.1.32 A graph G=(V,E)is called a bracelet if there exists an enu- meration ,,...,o of/such that {{,o}ifr=1, {1,2}ifr=2, {,2},{2,g},{3,a}ifr=3, {4,2,{2,},{,4},{4,0}ifr=4, and so on.We call r the circuit length of the bracelet G. We need the following elementary lemma,allowing one to decompose a uni- cyclic graph as a bracelet and its associated pendant trees.Recall that a graph G=(V,E)is unicyclic if it is connected and E=V. Lemma 2.1.33 Let G=(V,E)be a unicyclic graph.Let Z be the subgraph of G consisting of all e EE such that Ge is connected,along with all attached vertices.Let r be the number of edges of Z.Let F be the graph obtained from G by deleting all edges of Z.Then.Z is a bracelet of circuit length r.F is a forest with exactly r connected components,and Z meets each connected component of F in exactly one vertex.Further,r=I if Es #0while r>3 otherwise
2.1 TRACES, MOMENTS AND COMBINATORICS 31 The emerging picture is of two trees with k/2 edges each “glued together” at one edge. Since there are Ck/2 ways to chose each of the trees, k/2 ways of choosing (in each tree) the edge to be glued together, and 2 possible orientations for the gluing, we deduce that |W (2) k,k,− | = 2 k 2 2 C 2 k/2 . (2.1.40) Further, for each a ∈ W (2) k,k,− , h ∏e∈Ec a E(Z N a e 1,2 ) ∏e∈Es a E(Y N a e 1 ) − ∏e∈Ec w1 E(Z N w1 e 1,2 ) ∏e∈Es w1 E(Y N w1 e 1 ) ∏e∈Ec w2 E(Z N w2 e 1,2 ) ∏e∈Es w2 E(Y N w2 e 1 ) i = E(Z 4 1,2 )[E(Z 2 1,2 )]k−2 −[E(Z 2 1,2 )]k = E(Z 4 1,2 )−1. (2.1.41) We next turn to consider W (2) k,k,+ . In order to do so, we need to understand the structure of unicyclic graphs. Definition 2.1.32 A graph G = (V,E) is called a bracelet if there exists an enumeration α1,α2,...,αr of V such that E = {{α1,α1}} if r = 1, {{α1,α2}} if r = 2, {{α1,α2},{α2,α3},{α3,α1}} if r = 3, {{α1,α2},{α2,α3},{α3,α4},{α4,α1}} if r = 4, and so on. We call r the circuit length of the bracelet G. We need the following elementary lemma, allowing one to decompose a unicyclic graph as a bracelet and its associated pendant trees. Recall that a graph G = (V,E) is unicyclic if it is connected and |E| = |V|. Lemma 2.1.33 Let G = (V,E) be a unicyclic graph. Let Z be the subgraph of G consisting of all e ∈ E such that G \ e is connected, along with all attached vertices. Let r be the number of edges of Z. Let F be the graph obtained from G by deleting all edges of Z. Then, Z is a bracelet of circuit length r, F is a forest with exactly r connected components, and Z meets each connected component of F in exactly one vertex. Further, r = 1 if Es 6= /0 while r ≥ 3 otherwise