12 2.WIGNER MATRICES where we use the notation i=(i1,...,ix). The proof of Lemma 2.1.6 now proceeds by considering which terms contribute to (2.1.10).Let us provide first an informal sketch that explains the emergence of the Catalan numbers,followed by a formal proof.For the purpose of this sketch, assume that the variables Yi vanish,and that the law of Z12 is symmetric,so that all odd moments vanish (and in particular,(LN,)=0 for k odd). A first step in the sketch (that is fully justified in the actual proof below)is to check that the only terms in(2.1.10)that survive the passage to the limit involve only second moments of because there are order Nk/2+1 non-zero terms but only at most order Nk/2 terms that involve moments higher than or equal to 4.One then sees that 2内=1+0w- Tnh (2.1.11) p3≠r (pp+1)=+i)or+1d Considering the index j>I such that either (ij,)=(i2,i1)or (ij,ij+1)= (i1,i2),and recalling that ii since Y =0,one obtains 6的=1+ow这立主 (2.1.12) j=21≠i2=13-1 j+2.,2k=1 EXw(i2,i3)…Xw(6j-1,2)Xw(1,i+2)…Xw(i2k,ii） +EXN(i2,i3)...Xv(ij-1,i1)Xv(i2,ij+2)...Xv(izx,i1) Hence,ifwe could prove that E[(LN-LN,=O(N-2)and hence E[w,xw,x2k--2】=(亿，x(iw,x2k--2(1+0W-l), we would obtain 2(k-1 i=1+ow》(,ir-9 +瓜2-2） =+0-空a,r网 =0+0w-》2v,i2-y (2.1.13)
12 2. WIGNER MATRICES where we use the notation i = (i1,...,ik). The proof of Lemma 2.1.6 now proceeds by considering which terms contribute to (2.1.10). Let us provide first an informal sketch that explains the emergence of the Catalan numbers, followed by a formal proof. For the purpose of this sketch, assume that the variables Yi vanish, and that the law of Z1,2 is symmetric, so that all odd moments vanish (and in particular, hL¯N,x k i = 0 for k odd). A first step in the sketch (that is fully justified in the actual proof below) is to check that the only terms in (2.1.10) that survive the passage to the limit involve only second moments of Zi, j , because there are order N k/2+1 non-zero terms but only at most order N k/2 terms that involve moments higher than or equal to 4. One then sees that hL¯N,x 2k i = (1+O(N −1 )) 1 N ∑ ∀p,∃!j6=p: (ip,ip+1)=(ij ,ij+1)or(ij+1,ij) T¯N i1,...,i2k . (2.1.11) Considering the index j > 1 such that either (ij ,ij+1) = (i2,i1) or (ij ,ij+1) = (i1,i2), and recalling that i2 6= i1 since Yi1 = 0, one obtains hL¯N,x 2k i = (1+O(N −1 )) 1 N 2k ∑ j=2 N ∑ i16=i2=1 N ∑ i3 ,...,i j−1 , ij+2,...,i2k=1 (2.1.12) EXN(i2,i3)···XN(ij−1,i2)XN(i1,ij+2)···XN(i2k ,i1) +EXN(i2,i3)···XN(ij−1,i1)XN(i2,ij+2)···XN(i2k ,i1) . Hence, if we could prove that E[hLN −L¯N,x k i] 2 = O(N −2 ) and hence E[hLN,x j ihLN,x 2k−j−2 i] = hL¯N,x j ihL¯N,x 2k−j−2 i(1+O(N −1 )), we would obtain hL¯N,x 2k i = (1+O(N −1 )) 2(k−1) ∑ j=0 hL¯N,x j ihL¯N,x 2k−j−2 i + 1 N hL¯N,x 2k−2 i = (1+O(N −1 )) 2k−2 ∑ j=0 hL¯N,x j ihL¯N,x 2k−j−2 i = (1+O(N −1 )) k−1 ∑ j=0 hL¯N,x 2 j ihL¯N,x 2(k−j−1) i, (2.1.13)
2.1 TRACES,MOMENTS AND COMBINATORICS 13 where we have used that by induction(LN,x2-2)is uniformly bounded and also the fact that odd moments vanish.Further, a=含E6wP-1=G. (2.1.14) i= Thus,we conclude from(2.1.13)by induction that (LN,x2k)converges to a limit ak with ao =a=1,and further the family fak}satisfies the recursions ak= -1.Comparing with (2.1.7),we deduce that ag-Ck,as claimed. We turn next to the actual proof.To handle the summation in expressions like (2.1.10),it is convenient to introduce some combinatorial machinery that will serve us also in the sequel.We thus first digress and discuss the combinatorics intervening in the evaluation of the sum in(2.1.10).This is then followed by the actual proof of Lemma 2.1.6. In the following definition,the reader may think of.as a subset of the integers. Definition 2.1.8(.9-Words)Given a set.9,an.9-letter s is simply an element of..An.-word w is a finite sequence of letters s1...sn,at least one letter long. An.9-word w is closed if its first and last letters are the same.Two .9-words wi,w2 are called equivalent,denoted wi~w2,if there is a bijection on that maps one into the other. When={1,...,N)for some finite N,we use the term N-word.Otherwise,if the set is clear from the context,we refer to an-word simply as a word. For any .-word w=s1...sk,we use e(w)=k to denote the length of w,and define the weight wt(w)as the number of distinct elements of the set {s1,...,sk}, and the support of w,denoted suppw,as the set of letters appearing in w.To any word w we may associate an undirected graph,with wt(w)vertices and e(w)-I edges,as follows. Definition 2.1.9(Graph associated to an .9-word)Given a word w=s1..sk, we let G=(V,E)be the graph with set of vertices V suppw and (undi- rected)edges Ew={fsi,s+1,i=1,...,k-1}.We define the set of self edges as E=feE Ew e={u,uh,uEVw and the set of connecting edges as E =EwE The graph Ge is connected since the word w defines a path connecting all the vertices of G,which further starts and terminates at the same vertex if the word is closed.For eE,we use N to denote the number of times this path traverses
2.1 TRACES, MOMENTS AND COMBINATORICS 13 where we have used that by induction hL¯N,x 2k−2 i is uniformly bounded and also the fact that odd moments vanish. Further, hL¯N,x 2 i = 1 N N ∑ i, j=1 EXN(i, j) 2 →N→∞ 1 = C1 . (2.1.14) Thus, we conclude from (2.1.13) by induction that hL¯N,x 2k i converges to a limit ak with a0 = a1 = 1, and further the family {ak} satisfies the recursions ak = ∑ k j=1 ak−jaj−1. Comparing with (2.1.7), we deduce that ak = Ck , as claimed. We turn next to the actual proof. To handle the summation in expressions like (2.1.10), it is convenient to introduce some combinatorial machinery that will serve us also in the sequel. We thus first digress and discuss the combinatorics intervening in the evaluation of the sum in (2.1.10). This is then followed by the actual proof of Lemma 2.1.6. In the following definition, the reader may think of S as a subset of the integers. Definition 2.1.8 (S -Words) Given a set S , an S -letter s is simply an element of S . An S -word w is a finite sequence of letters s1 ···sn, at least one letter long. An S -word w is closed if its first and last letters are the same. Two S -words w1,w2 are called equivalent, denoted w1 ∼ w2, if there is a bijection on S that maps one into the other. When S = {1,...,N} for some finite N, we use the term N-word. Otherwise, if the set S is clear from the context, we refer to an S -word simply as a word. For any S -word w = s1 ···sk , we use ℓ(w) = k to denote the length of w, and define the weight wt(w) as the number of distinct elements of the set {s1,...,sk}, and the support of w, denoted suppw, as the set of letters appearing in w. To any word w we may associate an undirected graph, with wt(w) vertices and ℓ(w)− 1 edges, as follows. Definition 2.1.9 (Graph associated to an S -word) Given a word w = s1 ···sk , we let Gw = (Vw,Ew) be the graph with set of vertices Vw = suppw and (undirected) edges Ew = {{si ,si+1},i = 1,...,k−1}. We define the set of self edges as E s w = {e ∈Ew : e = {u,u},u∈Vw} and the set of connecting edges as E c w = Ew \E s w. The graph Gw is connected since the word w defines a path connecting all the vertices of Gw, which further starts and terminates at the same vertex if the word is closed. For e ∈ Ew, we use N w e to denote the number of times this path traverses
14 2.WIGNER MATRICES the edge e (in any direction).We note that equivalent words generate the same graphs G(up to graph isomorphism)and the same passage-counts Ne Coming back to the evaluation of T,see (2.1.10),note that any k-tuple of integers i defines a closed word wi=ii2...ixi of length k+1.We write wti= wt(wi),which is nothing but the number of distinct integers in i.Then, =Π)ΠE). (2.1.15) eEEw In particular,.T=0 unless N"≥2 for all e∈Er,which implies that wt≤ k/2+1.Also,(2.1.15)shows that if wi~wy then TV T.Further,if N >t then there are exactly Cw4=N(N-1)W-2)…(W-t+1) N-words that are equivalent to a given N-word of weightt.We make the following definition: denotes a set of representatives for equivalence classes of closed t-words w of length k+I and weight t with N>2 for each eE E. 2.1.16) One deduces from(2.1.10)and (2.1.15)that 亿w,x= k/2)+1 CNI N2本】 ΠE(Z)ΠE(), (2.1.17) Note that the cardinality of is bounded by the number of closed.-words of length k+I when the cardinality of,yist≤k,that is,lful≤tk≤kk.Thus (2.1.17)and the finiteness of r&,see(2.1.1),imply that lm亿w,xy=0,ifk is odd, while,for k even. mv,x9=∑ΠE(Z)ΠE() (2.1.18) we2+1eeE昭 We have now motivated the following definition.Note that for the purpose of this section,the case k=0 in definition 2.1.10 is not really needed.It is introduced in this way here in anticipation of the analysis in Section 2.1.6. Definition 2.1.10 A closed word w of length k+1>1 is called a Wigner word if either k=0 or k is even and w is equivalent to an element of+1
14 2. WIGNER MATRICES the edge e (in any direction). We note that equivalent words generate the same graphs Gw (up to graph isomorphism) and the same passage-counts N w e . Coming back to the evaluation of T¯N i , see (2.1.10), note that any k-tuple of integers i defines a closed word wi = i1i2 ···ik i1 of length k + 1. We write wti = wt(wi), which is nothing but the number of distinct integers in i. Then, T¯N i = 1 Nk/2 ∏e∈Ec wi E(Z N wi e 1,2 ) ∏e∈Es wi E(Y N wi e 1 ). (2.1.15) In particular, T¯N i = 0 unless N wi e ≥ 2 for all e ∈ Ewi , which implies that wti ≤ k/2+1. Also, (2.1.15) shows that if wi ∼ wi ′ then T¯N i = T¯N i ′ . Further, if N ≥ t then there are exactly CN,t := N(N −1)(N −2)···(N −t +1) N-words that are equivalent to a given N-word of weight t. We make the following definition: Wk,t denotes a set of representatives for equivalence classes of closed t-words w of length k +1 and weight t with N w e ≥ 2 for each e ∈ Ew . (2.1.16) One deduces from (2.1.10) and (2.1.15) that hL¯N,x k i = ⌊k/2⌋+1 ∑ t=1 CN,t Nk/2+1 ∑ w∈Wk,t ∏e∈Ec w E(Z N w e 1,2 ) ∏e∈Es w E(Y N w e 1 ). (2.1.17) Note that the cardinality of Wk,t is bounded by the number of closed S -words of length k + 1 when the cardinality of S is t ≤ k, that is, |Wk,t | ≤ t k ≤ k k . Thus, (2.1.17) and the finiteness of rk , see (2.1.1), imply that lim N→∞ hL¯N,x k i = 0, if k is odd, while, for k even, lim N→∞ hL¯N,x k i = ∑ w∈Wk,k/2+1 ∏e∈Ec w E(Z N w e 1,2 ) ∏e∈Es w E(Y N w e 1 ). (2.1.18) We have now motivated the following definition. Note that for the purpose of this section, the case k = 0 in definition 2.1.10 is not really needed. It is introduced in this way here in anticipation of the analysis in Section 2.1.6. Definition 2.1.10 A closed word w of length k +1 ≥ 1 is called a Wigner word if either k = 0 or k is even and w is equivalent to an element of Wk,k/2+1
2.1 TRACES,MOMENTS AND COMBINATORICS 15 We next note that if wE+then G is a tree:indeed,G is a connected graph with=k/2+1,hence Ek/2,while the condition N >2 for each e E Ew implies that Ew<k/2.Thus,Ew=Vw-1,implying that Gw is a tree, that is a connected graph with no loops.Further,the above implies that E is empty for w1,and thus, m亿v,个=2+l. (2.1.19) We may now complete the Proof of Lemma 2.1.6 Let k be even.It is convenient to choose the set of rep- resentatives+1 such that each word w-vi..vk+I in that set satisfies,for i=1,...,k+1,the condition that {v1,...,vi}is an interval in Z beginning at 1. (There is a unique choice of such representatives.)Each element wE+1 determines a path vi,v2,...,V&,v+I=vI of length k on the tree G.We refer to this path as the exploration process associated with w.Let d(v,)denote the distance between vertices v,v on the tree G,i.e.the length of the shortest path on the tree beginning at v and terminating at v.Setting x=d(v+,v),one sees that each word w+defines a Dyck path D(w)=(x1,x2,...,xx)of length k.Conversely,given a Dyck path x=(x1,...,x),one may construct a word w=T(x)E+by recursively constructing an increasing sequence w2,..., w&=w of words,as follows.Put w2 =(1,2).For i>2,ifxi1=x1-2+1,then wi is obtained by adjoining on the right of wi-1 the smallest positive integer not appearing in w1.Otherwise,w,is obtained by adjoining on the right of wi the next to last letter of w-1.Note that for all i,G is a tree (because is a tree and,inductively,at stage i,either a backtrack is added to the exploration process on Gor a leaf is added to G).Furthermore,the distance in G,between first and last letters of wi equals x-1,and therefore,D(w)=(x1,...,xx).With our choice of representatives,T(D(w))=w,because each uptick in the Dyck path D(w)starting at location i-2 corresponds to adjoinment on the right of wi-of a new letter,which is uniquely determined by suppw-1,whereas each downtick at location i-2 corresponds to the adjoinment of the next-to-last letter in wi-1. This establishes a bijection between Dyck paths of length k and1.Lemma 2.1.3 then establishes that |kM2+1=Ck/2 (2.1.20) This completes the proof of Lemma 2.1.6. 0 From the proof of Lemma 2.1.6 we extract as a further benefit a proof of a fact needed in Chapter 5.Let k be an even positive integer and let={1,...,k}. Recall the notion of non-crossing partition of,see Definition 2.1.4.We define
2.1 TRACES, MOMENTS AND COMBINATORICS 15 We next note that if w ∈ Wk,k/2+1 then Gw is a tree: indeed, Gw is a connected graph with |Vw| = k/2+1, hence |Ew| ≥ k/2, while the condition N w e ≥ 2 for each e ∈ Ew implies that |Ew| ≤ k/2. Thus, |Ew| = |Vw| −1, implying that Gw is a tree, that is a connected graph with no loops. Further, the above implies that E s w is empty for w ∈ Wk,k/2+1 , and thus, lim N→∞ hL¯N,x k i = |Wk,k/2+1 |. (2.1.19) We may now complete the Proof of Lemma 2.1.6 Let k be even. It is convenient to choose the set of representatives Wk,k/2+1 such that each word w = v1 ··· vk+1 in that set satisfies, for i = 1,...,k + 1, the condition that {v1,...,vi} is an interval in Z beginning at 1. (There is a unique choice of such representatives.) Each element w ∈ Wk,k/2+1 determines a path v1,v2,...,vk ,vk+1 = v1 of length k on the tree Gw. We refer to this path as the exploration process associated with w. Let d(v,v ′ ) denote the distance between vertices v,v ′ on the tree Gw, i.e. the length of the shortest path on the tree beginning at v and terminating at v ′ . Setting xi = d(vi+1,v1), one sees that each word w ∈ Wk,k/2+1 defines a Dyck path D(w) = (x1,x2,...,xk) of length k. Conversely, given a Dyck path x = (x1,...,xk), one may construct a word w = T(x) ∈ Wk,k/2+1 by recursively constructing an increasing sequence w2,..., wk = w of words, as follows. Put w2 = (1,2). For i > 2, if xi−1 = xi−2 + 1, then wi is obtained by adjoining on the right of wi−1 the smallest positive integer not appearing in wi−1. Otherwise, wi is obtained by adjoining on the right of wi−1 the next to last letter of wi−1. Note that for all i, Gwi is a tree (because Gw2 is a tree and, inductively, at stage i, either a backtrack is added to the exploration process on Gwi−1 or a leaf is added to Gwi−1 ). Furthermore, the distance in Gwi between first and last letters of wi equals xi−1, and therefore, D(w) = (x1,...,xk). With our choice of representatives, T(D(w)) = w, because each uptick in the Dyck path D(w) starting at location i − 2 corresponds to adjoinment on the right of wi−1 of a new letter, which is uniquely determined by suppwi−1, whereas each downtick at location i − 2 corresponds to the adjoinment of the next-to-last letter in wi−1. This establishes a bijection between Dyck paths of length k and Wk,k/2+1 . Lemma 2.1.3 then establishes that |Wk,k/2+1 | = Ck/2 . (2.1.20) This completes the proof of Lemma 2.1.6. ⊓⊔ From the proof of Lemma 2.1.6 we extract as a further benefit a proof of a fact needed in Chapter 5. Let k be an even positive integer and let Kk = {1,...,k}. Recall the notion of non-crossing partition of Kk , see Definition 2.1.4. We define
16 2.WIGNER MATRICES Fig.2.1.2.Coding of the word w=123242521 into a tree and a Dyck path of length 8. Note that e(w)=9 and wt(w)=5. a pair partition of to be a partition all of whose parts are two-element sets. The fact we need is that the equivalence classes of Wigner words of length k+1 and the non-crossing pair partitions of%are in canonical bijective correspon- dence.More precisely,we have the following result which describes the bijection in detail. Proposition 2.1.11 Given a Wigner word w =i...ik+of length k+1,let Iw be the partition generated by the function jijj:(1....,k)Ew.(Here, recall,Ew is the set ofedges of the graph Gw associated to w.)Then the following hold: (i)w is a non-crossing pair partition. (ii)Every non-crossing pair partition of.x is of the form Iw for some Wigner word w of length k+1. (iii)If two Wigner words w and w'of length k+1 satisfy I =IL,then w and w'are equivalent. Proof(i)Because a Wigner word w viewed as a walk on its graph Gw crosses every edge exactly twice,I is a pair partition.Because the graph G is a tree, the pair partition is non-crossing. (ii)The non-crossing pair partitions of correspond bijectively to Dyck paths. More precisely,given a non-crossing pair partition II of,associate to it a pathf=(f(1),...,f(k))by the rules that fn(1)=1,and,for i=2,...,k
16 2. WIGNER MATRICES 1 2 3 4 5 Fig. 2.1.2. Coding of the word w = 123242521 into a tree and a Dyck path of length 8. Note that ℓ(w) = 9 and wt(w) = 5. a pair partition of Kk to be a partition all of whose parts are two-element sets. The fact we need is that the equivalence classes of Wigner words of length k +1 and the non-crossing pair partitions of Kk are in canonical bijective correspondence. More precisely, we have the following result which describes the bijection in detail. Proposition 2.1.11 Given a Wigner word w = i1 ···ik+1 of length k +1, let Πw be the partition generated by the function j 7→ {ij ,ij+1} : {1,...,k} → Ew. (Here, recall, Ew is the set of edges of the graph Gw associated to w.) Then the following hold: (i) Πw is a non-crossing pair partition. (ii) Every non-crossing pair partition of Kk is of the form Πw for some Wigner word w of length k +1. (iii) If two Wigner words w and w′ of length k + 1 satisfy Πw = Πw′ , then w and w ′ are equivalent. Proof (i) Because a Wigner word w viewed as a walk on its graph Gw crosses every edge exactly twice, Πw is a pair partition. Because the graph Gw is a tree, the pair partition Πw is non-crossing. (ii) The non-crossing pair partitions of Kk correspond bijectively to Dyck paths. More precisely, given a non-crossing pair partition Π of Kk , associate to it a path fΠ = (fΠ(1),..., fΠ(k)) by the rules that fΠ(1) = 1, and, for i = 2,...,k