Thierry L Évy

SCHUR-WEYL DUALITY AND THE HEAT KERNEL MEASURE ON THE UNITARY GROUP

Schur-Weyl duality and the heat kernel measure on the unitary group.

Introduction

In this paper, we are concerned with the asymptotics of large random unitary matrices distributed according to the heat kernel measure. This problem has been studied first about ten years ago by P. Biane [START_REF] Biane | Free Brownian motion, free stochastic calculus and random matrices[END_REF] and F. Xu [START_REF] Xu | A random matrix model from two-dimensional Yang-Mills theory[END_REF]. It shares some similarities with the case of unitary matrices distributed under the Haar measure, studied by B. Collins and P. Śniady [START_REF] Collins | Moments and cumulants of polynomial random variables on unitary groups, the Itzykson-Zuber integral, and free probability[END_REF][START_REF] Collins | Integration with respect to the Haar measure on unitary, orthogonal and symplectic group[END_REF]. The origin of our interest in this problem is the hypothetical existence of a large N limit to the two-dimensional U (N ) Yang-Mills theory. This limit has been investigated by physicists, in particular by V. Kazakov and V. Kostov [START_REF] Kazakov | Nonlinear strings in two-dimensional U(∞) gauge theory[END_REF] and by D. Gross, in collaboration with W. Taylor [START_REF] Gross | Twists and Wilson loops in the string theory of two dimensional QCD[END_REF], A. Matytsin [START_REF] Gross | Some properties of large-N two-dimensional Yang-Mills theory[END_REF] and R. Gopakumar [START_REF] Gopakumar | Mastering the master field[END_REF]. In [START_REF] Singer | On the master field in two dimensions[END_REF], I. Singer has given the name of "Master field" to this limit, which still has to be constructed. A. Sengupta has described in [START_REF] Sengupta | Traces in two-dimensional QCD: the large-N limit[END_REF] the relationship between Yang-Mills theory and large unitary matrices. We refer the interested reader to this paper and will not develop this motivation further. Sengupta's work also contains some results whose study was at the origin of this paper (see Proposition 2.2 and the discussion thereafter).

Our approach relies on the fact that the Schur-Weyl duality determines a (non-bijective) correspondence between conjugation-invariant objects on the unitary group on one hand and on the symmetric group on the other hand. To be specific, let n, N ≥ 1 be integers. Let ρ n,N : S n × U (N ) -→ GL((C N ) ⊗n ) be the classical representation. The set P n,N of partitions of n with at most N parts indexes irreducible representations of both S n and U (N ). If λ is such a partition, let χ λ (resp. χ λ ) denote the corresponding character on S n (resp. U (N )). Let Z be an element of the centre of C[S n ]. Let D be a conjugation-invariant distribution on U (N ). Then the equalities [START_REF] Biane | Free Brownian motion, free stochastic calculus and random matrices[END_REF] ∀λ ∈ P n,N , χ λ (Z)

χ λ (id) = χ λ (D) χ λ (I N ) ,
where χ λ (D) = Dχ λ , imply ρ n,N (Z ⊗ 1) = ρ n,N (1 ⊗ D). The main observation, implicit in [START_REF] Gross | Twists and Wilson loops in the string theory of two dimensional QCD[END_REF], is the following: the element Z = -N n 2 -1≤k<l≤n (kl) ∈ C[S n ] and the distribution D on U (N ) defined by Dϕ = 1 2 ∆ U (N ) ϕ(I N ), where ∆ U (N ) is the Laplace operator, satisfy [START_REF] Biane | Free Brownian motion, free stochastic calculus and random matrices[END_REF]. Now Z is, up to an additive constant, the generator of the most natural random walk on S n and it follows from this discussion that this random walk is closely related to the Brownian motion on Date: January 2008. the unitary group. This relation is stated precisely and proved in Section 2. It is also partially generalized to the orthogonal and symplectic groups.

In Section 3, we prove our main result, which is the following.

Theorem 1.1 (see also Thm 3.3). Let N, n ≥ 1 be integers. Let (B t ) t≥0 be a Brownian motion on U (N ) starting at the identity and corresponding to the scalar product (X, Y ) → -Tr(XY ) on u(N ). Let σ be an element of S n . Let m 1 , . . . , m r denote the lengths of the cycles of σ. Then, for all t ≥ 0, we have the following series expansion:

(2)

E[Tr N (B m 1 t N ) . . . Tr N (B mr t N )] = e -nt 2 +∞ k,d=0 (-1) k t k k!N 2d S(σ, k, d).
For all T ≥ 0, this expansion converges uniformly on (N, t) ∈ N * × [0, T ].

The coefficients S(σ, k, d) count paths in the Cayley graph of the symmetric group S n . More specifically, we consider the Cayley graph of S n generated by all transpositions. For all π ∈ S n , we denote by |π| the graph distance between |π| and the identity. Then S(σ, k, d) is the number of paths starting at σ of length k and finishing at a point π such that |π| = |σ| -(k -2d). In particular, S(σ, k, d) = 0 if |k -2d| ≥ n : for each d ≥ 0, the contribution of order N -2d is a polynomial in t.

The coefficients S(σ, k, d) depend on σ only through its conjugacy class and can be expressed in terms of the representations of the symmetric group. In fact, Theorem 1.1 can be proved directly using the representation theory of the unitary and symmetric groups. We present this proof in Section 4. It is more systematical than the proof presented in Section 3 and should be easier to generalize, as also suggested by the work of Gross and Taylor [START_REF] Gross | Twists and Wilson loops in the string theory of two dimensional QCD[END_REF].

The tools of representation theory allow us, in Section 5, to compute S(σ, k, d) when σ is a cycle of length n. The expression involves Stirling numbers and it could hardly be called simple. Nevertheless, it allows us to count for all integer p the number of ways to write the cycle (1 . . . n) in S n as a product of p transpositions.

In Section 6, we use our expansion to describe the asymptotic distribution of unitary matrices under the heat kernel measure as their size tends to infinity, thus recovering a result of P. Biane [START_REF] Biane | Free Brownian motion, free stochastic calculus and random matrices[END_REF]. We also recover a result of F. Xu [START_REF] Xu | A random matrix model from two-dimensional Yang-Mills theory[END_REF] on the asymptotic factorization of the expected values of products of traces. In order to describe the asymptotic distribution, we must compute the coefficients S(σ, k, 0). The factorization result mentioned above reduces the problem to the case where σ is an n-cycle. Unfortunately, the expression of S((1 . . . n), k, 0) obtained in Section 5 is not obviously equal to what it should be according to Biane's results. Thus, we compute this coefficient in a different way by using the relations between the geometry of the Cayley graph of the symmetric group and the lattice of non-crossing partitions. Then, in Section 7, we apply the same ideas related to non-crossing partitions and use Speicher's criterion of freeness to prove the asymptotic freeness of independent unitary matrices under the heat kernel measure.

Finally, in Section 8, we give an interpretation of our formula in terms of random ramified coverings over a disk, thus proving a formula described by Gross and Taylor [START_REF] Gross | Twists and Wilson loops in the string theory of two dimensional QCD[END_REF]. We define a probability measure on a certain set of ramified coverings over the disk and prove that the expectation computed in Theorem 1.1 is the integral of a simple function -essentially N raised to a power equal to the Euler characteristic of the total space of the covering -against this measure. From this point of view, our expansion deserves to be called a genus expansion.

It is a pleasure to thank Philippe Biane for several enlightening conversations.

Probabilistic aspects of Schur-Weyl duality

In this first section, we establish formulae which relate the heat kernel measures on U (N ), SU (N ), SO(N ) and Sp(N ), to natural random walks in the symmetric group and the Brauer monoid.

2.1. The unitary group. Let n and N be two positive integers. There is a natural action of each of the groups U (N ) and S n on the vector space (C N ) ⊗n , defined as follows: for all U ∈ U (N ), σ ∈ S n and x 1 , . . . , x n ∈ C N , we set

U • (x 1 ⊗ . . . ⊗ x n ) = U x 1 ⊗ . . . ⊗ U x n , σ • (x 1 ⊗ . . . ⊗ x n ) = x σ -1 (1) ⊗ . . . ⊗ x σ -1 (n) . (3)
It is a basic observation that these actions commute to each other. In particular, they determine an action ρ n,N of S n × U (N ) on (C N ) ⊗n by

ρ n,N (σ, U )(x 1 ⊗ . . . ⊗ x n ) = U x σ -1 (1) ⊗ . . . ⊗ U x σ -1 (n) .
Definition 2.1. Let M 1 , . . . , M n be N × N complex matrices. Let σ be an element of S n . We denote by p st σ (M 1 , . . . , M n ) the complex number

p st σ (M 1 , . . . , M n ) = Tr (C N ) ⊗n ((M 1 ⊗ . . . ⊗ M n ) • ρ n,N (σ, I N )) = c=(i 1 ...ir) cycle of σ Tr(M i 1 . . . M ir ).
We set p st σ (M ) = p st σ (M, . . . , M ). The upper index st indicates that we use the standard trace rather than the normalized one in the definition. The letter p stand for "power sums", since p st σ (M ), as a symmetric function of the eigenvalues of M , is the product of power sums corresponding to the partition determined by σ. Observe that, by definition, the character of the representation ρ n,N is the function χ ρ n,N (σ, U ) = p st σ (U ). The core result of Schur-Weyl duality is that the two subalgebras of End((C N ) ⊗n ) generated respectively by the actions of U (N ) and S n are each other's commutant. Let us explain why this makes a relation between the Brownian motion on U (N ) and some element of the centre of the group algebra of S n unavoidable.

Let u(N ) denote the Lie algebra of U (N ), which consists of the N ×N anti-Hermitian complex matrices. Let U(u(N )) denote the enveloping algebra of u(N ), which is canonically isomorphic to the algebra of left-invariant differential operators on U (N ). Let also C[S n ] denote the group algebra of S n . The representation ρ n,N determines a homomorphism of associative algebras

C[S n ] ⊗ U(u(N )) -→ End((C N ) ⊗n ). The centre Z(u(N )) of U(u(N )) is the space of bi-invariant differential operators on U (N ). Since ρ n,N (1 ⊗ Z(u(N ))) commutes with ρ n,N (1, U ) for every U ∈ U (N ), the Schur-Weyl duality asserts in particular that ρ n,N (1 ⊗ Z(u(N ))) ⊂ ρ n,N (C[S n ] ⊗ 1).
We are primarily interested in the Laplace operator, which is defined as follows. The R-bilinear form X, Y = Tr(X * Y ) = -Tr(XY ) is a scalar product on u(N ). Let (X 1 , . . . , X N 2 ) be an orthonormal basis of u(N ). Identifying the elements of u(N ) with left-invariant vector fields on U (N ), thus with first-order differential operators on U (N ), the Laplace operator ∆ U (N ) is the differential operator N 2 i=1 X 2 i . It corresponds to the Casimir element N 2 i=1 X i ⊗ X i of the enveloping algebra of u(N ). This element is central and does not depend on the choice of the orthonormal basis. Hence, ∆ U (N ) is well defined and bi-invariant. The discussion above shows that, in the representation ρ n,N , the Laplace operator of U (N ) can be expressed as an element of C[S n ]. This is exactly what the main formula of this section does, in an explicit way.

Let T n be the subset of S n consisting of all transpositions. We set ∆ Sn = -n(n-1)

2

+ τ ∈Tn τ . The formula for the unitary group is the following. Proposition 2.2. For all integers, n, N ≥ 1, one has

(4) ρ n,N ∆ Sn ⊗ 1 + 1 ⊗ 1 2 ∆ U (N ) = - N n + n(n -1) 2 .
Before we prove this formula, let us derive some of its consequences.

Proposition 2.3. For each σ ∈ S n , the function p st σ : U (N ) -→ C satisfies the following relation:

(5) 1 2 ∆ U (N ) p st σ = - N n 2 p st σ - τ ∈Tn p st στ .
More generally, let M 1 , . . . , M n be arbitrary N ×N matrices. Then, regarding p st σ (M 1 U, . . . , M n U ) as a function of U ∈ U (N ), one has

(6) 1 2 ∆ U (N ) p st σ (M 1 U, . . . , M n U ) = - N n 2 p st σ (M 1 U, . . . , M n U ) - τ ∈Tn p st στ (M 1 U, . . . , M n U ). Proof -Recall that p st σ (M 1 U, . . . , M n U ) = Tr ((M 1 ⊗ . . . ⊗ M n ) • ρ n,N (σ, U )). Let us use the shorthand notation M = M 1 ⊗ . . . ⊗ M n . We have 1 2 ∆ U (N ) p st σ (M 1 U, . . . , M n U ) = Tr(M • ρ n,N (σ, U ) • ρ n,N (1 ⊗ 1 2 ∆ U (N ) )) = - N n + n(n -1) 2 p st σ (M 1 U, . . . , M n U ) -Tr(M • ρ n,N (σ, U ) • ρ n,N (∆ Sn ⊗ 1)
). The result follows immediately from the definition of ∆ Sn .

The function p st σ depends only on the cycle structure of σ. In concrete terms, if the lengths of the cycles of σ are m 1 , . . . , m r , then p st σ (U ) = Tr(U m 1 ) . . . Tr(U mr ). This redundant labelling is however nicely adapted to our problem, as equation [START_REF] Kazakov | Nonlinear strings in two-dimensional U(∞) gauge theory[END_REF] shows. Let us spell out the right hand side of this equality. The permutation σ being fixed, the cycle structure of στ depends on the two points exchanged by the transposition τ . If they belong to the same cycle of σ, then this cycle is split into two cycles. A cycle of length m can be split into a cycle of length s and a cycle of length m -s by m distinct transpositions, unless m = 2s, in which case only m 2 of these transpositions are distinct. If on the contrary the points exchanged by τ belong to two distinct cycles of σ, these two cycles are merged into a single cycle. Two cycles of lengths m and m ′ can be merged by mm ′ distinct permutations. Altogether, we find the following equation, which was already present in papers of Xu [START_REF] Xu | A random matrix model from two-dimensional Yang-Mills theory[END_REF] and Sengupta [START_REF] Sengupta | Traces in two-dimensional QCD: the large-N limit[END_REF].

∆ U (N ) (Tr(U m 1 ) . . . Tr(U mr )) = -N nTr(U m 1 ) . . . Tr(U mr ) + r i=1 m i Tr(U m 1 ) . . . Tr(U m i ) . . . Tr(U mr ) m i -1 s=1 Tr(U s )Tr(U m i -s ) + r i,j=1,i =j m i m j Tr(U m 1 ) . . . Tr(U m i ) . . . Tr(U m j ) . . . Tr(U mr ) Tr(U m i +m j ).
A remarkable feature of ( 4) is the fact that the element of C[S n ] which appears has coefficients of the same sign on the elements which are not the identity. Hence, up to an additive constant, it can be interpreted as the generator of a Markov chain on S n . This leads us to the following simple probabilistic interpretation of (4).

Let us introduce the standard random walk on the Cayley graph of the symmetric group generated by the set of transpositions. It is the continuous-time Markov chain on S n with generator ∆ Sn , that is, the chain which jumps at rate n 2 from its current position σ to στ , where τ is chosen uniformly at random among the n 2 transpositions of S n . If σ is a permutation, we denote by ℓ(σ) the number of cycles of σ. For example, τ is a transposition if and only if ℓ(τ ) = n -1.

Proposition 2.4. Let N, n ≥ 1 be integers. Let (B t ) t≥0 be a Brownian motion on U (N ) starting at the identity and corresponding to the scalar product (X, Y ) → -Tr(XY ) on u(N ). Let (π t ) t≥0 be a standard random walk on the Cayley graph of the symmetric group S n , independent of (B t ) t≥0 . Then the process e Nn+n(n-1)

2 t p st πt (B t )
t≥0 is a martingale. In particular,

(7) E p st πt (B t ) = e -Nn+n(n-1) 2 t E N ℓ(π 0 ) .
More generally, let M 1 , . . . , M n be arbitrary N ×N complex matrices. Then the stochastic process e

Nn+n(n-1)

2 t p st πt (M 1 B t , . . . , M n B t ) t≥0
is a martingale and

(8) E p st πt (M 1 B t , . . . , M n B t ) = e -Nn+n(n-1) 2 t E p st π 0 (M 1 , . . . , M n ) .
Proof -The process (π, B) is a Markov process on S n × U (N ) with generator ∆ Sn ⊗ 1 + 1 ⊗

∆ Sn ⊗ 1 + 1 ⊗ 1 2 ∆ U (N ) p = - N n + n(n -1) 2 p.
The fact that e Nn+n(n-1)

2 t p st πt (M 1 B t , . . . , M n B t ) t≥0
is a martingale follows immediately. The last assertion follows from the fact that B 0 = I N a.s.

Let us turn to the proof of Proposition 2.2.

Proof of Proposition 2.2 -The action of u(N ) on (C N ) ⊗n extends by complexification to gl(N, C) = u(N ) ⊕ iu(N ). Let (X 1 , . . . , X N 2 ) be a real basis of u(N ). It is also a complex basis of gl(N, C). Define a N × N matrix g by g ij = -Tr(X i X j ). Since -Tr(• •) is non-degenerate on gl N (C), the matrix g has an inverse g -1 , the entries of which we denote by g ij . Then it is easy to check that the element N 2 i,j=1 g ij X i ⊗ X j of the enveloping algebra is independent of the choice of the basis. Of course, by choosing our original basis of u(N ) orthonormal, we find that this element is simply ∆ U (N ) .

In order to compute ρ n,N (1 ⊗ ∆ U (N ) ), we prefer to use another complex basis of gl(N, C) = M N (C), namely the canonical basis (E ij ) i,j∈{1,...,N } . For this basis, g ij,kl = -δ jk δ il and g = g -1 . Hence, in the enveloping algebra of gl(N, C),

∆ U (N ) = -N i,j=1 E ij ⊗ E ji . First, notice that ρ n,N (1 ⊗ E ij )(x 1 ⊗ . . . ⊗ x n ) = n k=1 x 1 ⊗ . . . ⊗ E ij (x k ) ⊗ . . . ⊗ x n . Hence, ρ n,N   1 ⊗ N i,j=1 E ij ⊗ E ji   = 2 N i,j=1 1≤k<l≤n Id ⊗k-1 ⊗ E ij ⊗ Id ⊗l-k-1 ⊗ E ji ⊗ Id ⊗n-l-1 + + N i,j=1 n k=1 Id ⊗k-1 ⊗ E ii ⊗ Id ⊗n-k-1 .
The last term is simply N n times the identity. For the first part of the right hand side, observe

that N i,j=1 E ij ⊗ E ji ∈ End((C N ) ⊗2
) is the transposition operator x ⊗ y → y ⊗ x, that is, the operator ρ 2,N ((12), I N ). Finally, we have found that

-ρ n,N (1 ⊗ ∆ U (N ) ) = N n Id + 1≤k =l≤n ρ n,N ((kl), I N ).
The result follows.

The results of this section still hold, after a minor modification, when U (N ) is replaced by SU (N ). Indeed, the orthogonal complement of su(N ) in u(N ) is the line generated by i

√ N I N . Since ρ n,N (1 ⊗ (I N ⊗ I N )) = n 2
Id, the Casimir operator of su(N ) satisfies the relation

ρ n,N (1 ⊗ ∆ SU (N ) ) = ρ n,N (1 ⊗ ∆ U (N ) ) + n 2 N Id.
This modifies only the exponential factors in [START_REF] Gross | Some properties of large-N two-dimensional Yang-Mills theory[END_REF] and ( 8). We will explore further consequences of Proposition 2.4 in the rest of the paper. For the moment, we derive similar results for the orthogonal and symplectic group.

2.2. The orthogonal group. Let us consider the action of SO(N ) on (C N ) ⊗n defined by analogy with [START_REF] Collins | Moments and cumulants of polynomial random variables on unitary groups, the Itzykson-Zuber integral, and free probability[END_REF]. The action of S n still commutes to that of SO(N ), but, unless n = 1, the subalgebra of End((C N ) ⊗n ) generated by the image of C[S n ] is strictly smaller than the commutant of the image of SO(N ). Let us review briefly the operators which are classically used to describe this commutant. We denote by {e 1 , . . . , e N } the canonical basis of C N . Definition 2.5. Let β be a partition of {1, . . . , 2n} into pairs. Define ρ n,N (β) ∈ End((C N ) ⊗n ) by setting, for all i 1 , . . . , i n ∈ {1, . . . , N },

ρ n,N (β)(e i 1 ⊗ . . . ⊗ e in ) = i n+1 ,...,i 2n ∈{1,...,N } {k,l}∈β δ i k i l e i n+1 ⊗ . . . ⊗ e i 2n .
Observe that the partition {{1, n + 1}, . . . , {n, 2n}} is sent to the identity operator by ρ n,N . Let B n denote the set of partitions of {1, . . . , 2n} into pairs. The composition of the operators ρ n,N (β) corresponds to a monoid structure on B n which is easiest to understand on a picture. An element of B n is represented in a box with n dots on its top edge and n dots on its bottom edge. The dots on the top are labelled from 1 to n, from the left to the right. The dots on the bottom are labelled from n + 1 to 2n, from the left to the right too. A pairing is then simply represented by n chords which join the appropriate dots. Multiplication of pairings is done in the intuitive topological way by superposing boxes and, if necessary, removing the closed loops which have appeared. The monoid B n is called the Brauer monoid and its elements are called Brauer diagrams. The group S n is naturally a submonoid 1 of B n , by the identification of a permutation σ with the pairing {{1, σ(1) + n}, . . . , {n, σ(n) + n}}. The identification of S n with a subset of B n is compatible with our previous definition of ρ n,N in the sense that ρ n,N (σ) is the same if we consider σ as a permutation or as a Brauer diagram.

The correct statement of Schur-Weyl duality in the present context is that the subalgebras of End((C N ) ⊗n ) generated by SO(N ) and B n are each other's commutant (see [START_REF] Goodman | Representations and invariants of the classical groups[END_REF]). Let ρ n,N denote the morphism of monoids

ρ n,N : B n × SO(N ) -→ GL((C N ) ⊗n ).
Just as in the unitary case, this action determines a morphism of associative algebras ρ n,N :

C[B n ] ⊗ U(so(N )) -→ End((C N ) ⊗n ).
By analogy to the unitary case, let us define "power sums" functions associated to Brauer diagrams. Given β ∈ B n and M 1 , . . . , M n ∈ M N (C), set

p st β (M 1 , . . . , M n ) = Tr((M 1 ⊗ . . . ⊗ M n ) • ρ n,N (β)).
In particular, the character of ρ n,N is given by χ ρ n,N (β, R) = p st β (R). The number p st β (M 1 , . . . , M n ) is a product of traces of words in the matrices M 1 , t M 1 , . . . , M n , t M n . Let us describe in more detail how to compute p st β (I N ). Let β be a Brauer diagram. Consider the graph with vertices {1, . . . , n} and unoriented edges {k, l}, where k and l are such that there exist k ′ ∈ {k, k + n} and l ′ ∈ {l, l + n} with {k ′ , l ′ } ∈ β. This is the graph obtained by identifying the top edge with the bottom edge in the graphical representation of β. Then each vertex has degree 2 in this graph. Hence, it is a union of disjoint unoriented cycles. If β belongs to S n ⊂ B n , this cycle structure is of course that of β as a permutation, apart from the orientation which is lost. In general, let ℓ(β) denote the number of cycles in this graph. Then

p st β (I N ) = N ℓ(β) .
Let us define an element of C[B n ] as follows. Given k and l two integers such that 1 ≤ k < l ≤ n, we define the element kl of B n as the following pairing:

kl = {{k, l}, {n + k, n + l}} ∪ i∈{1,...,n}-{k,l} {{i, n + i}}.
1 In fact, Sn ⊂ Bn is exactly the subset of invertible elements. Indeed, for β ∈ Bn, let T (β) be the set of pairs {k, l} ∈ β such that 1 ≤ k, l ≤ n. In words, T (β) is the set of chords in the diagram of β which join two dots on the top edge of the box. It is clear that T (β1β2) ⊃ T (β1) for all β1, β2 ∈ Bn. Hence, T (β) must be empty for β to be invertible. More generally, it is not difficult to check that, given β and β ′ in Bn, there exists Proposition 2.6. For all integers, n, N ≥ 1, one has

β ′′ ∈ Bn such that ββ ′′ = β ′ if and only if T (β) ⊂ T (β ′ ).
(9) ρ n,N ∆ Sn ⊗ 1 + 1 ⊗ ∆ SO(N ) = - (N -1)n 2 + ρ n,N (∆ Bn ⊗ 1) .
Proof -The computation is very similar to that we made in the unitary case. Endow so(N ) with the scalar product X, Y = -Tr(XY ). The basis (A ij ) 1≤i<j≤N , with

A ij = E ij -E ji , is orthogonal and A ij , A ij = 2 for all i < j. Hence, ∆ SO(N ) = 1 2 1≤i<j≤N A ij ⊗ A ij . We have ρ n,N (1 ⊗ ∆ SO(N ) ) = 1≤k<l≤n 1≤i<j≤N Id ⊗k-1 ⊗ A ij ⊗ Id ⊗l-k-1 ⊗ A ij ⊗ Id ⊗n-l + + 1 2 n k=1 1≤i<j≤N Id ⊗k-1 ⊗ A 2 ij ⊗ Id ⊗n-k = 1≤k<l≤n N i,j=1 Id ⊗k-1 ⊗ E ij ⊗ Id ⊗l-k-1 ⊗ E ij ⊗ Id ⊗n-l - 1≤k<l≤n N i,j=1 Id ⊗k-1 ⊗ E ij ⊗ Id l-k-1 ⊗ E ji ⊗ Id n-l - (N -1)n 2 Id = 1≤k<l≤n ρ n,N (( kl -(kl)) ⊗ 1) - (N -1)n 2 Id.
The result follows.

The following proposition is proved just as Proposition 2.3.

Proposition 2.7. For all β ∈ B n , the following relation holds:

(10) ∆ SO(N ) p st β = - (N -1)n 2 p st β - τ ∈Tn p st βτ + α∈Cn p st βα .
More generally, let M 1 , . . . , M n be arbitrary N ×N matrices. Then, regarding

p st β (M 1 R, . . . , M n R) as a function of R ∈ SO(N ), ∆ SO(N ) p st β (M 1 R, . . . , M n R) = - (N -1)n 2 p st β (M 1 R, . . . , M n R) - τ ∈Tn p st βτ (M 1 R, . . . , M n R) + α∈Cn p st βα (M 1 R, . . . , M n R). (11)
It seems more difficult to find a probabilistic interpretation of (9) than in the unitary case, because the element of C[B n ] which appears does not have coefficients of the same sign on all elements not equal to 1.

2.3.

The symplectic group. Nothing really new is needed to treat the case of the symplectic group. Let us describe briefly the results.

Let J ∈ M 2N (C) denote the matrix 0 I N -I N 0
. The symplectic group is defined by

Sp(N ) = {S ∈ U (2N ) : t SJS = J}.
It acts naturally on ((C 2N ) ⊗n ). The action of the Brauer monoid needs to be slightly modified to fit the symplectic case. If β belongs to B n , we define the operator ρ n,2N (β) by setting, for all i 1 , . . . , i n ∈ {1, . . . , 2N },

ρ n,2N (β)(e i 1 ⊗ . . . ⊗ e in ) = i n+1 ,...,i 2n ∈{1,...,n} {k,l}∈β J i k i l e i n+1 ⊗ . . . ⊗ e i 2n .
Then we have an action ρ n,2N : B n ×Sp(N ) -→ End((C 2N ) ⊗n ) and the images of B n and Sp(N ) generate two algebras which are each other's commutant. The Lie algebra sp(N ) is endowed with the scalar product X, Y = -Tr(XY ) and we denote by ∆ Sp(N ) the corresponding Laplace operator. The main formula is the following. Proposition 2.8. For all integers, n, N ≥ 1, one has

(12) ρ n,2N ∆ Sn ⊗ 1 + 1 ⊗ 2∆ Sp(N ) = -(2N + 1)n + ρ n,2N (∆ Bn ⊗ 1) .
Proof -Just as in the unitary case, it is more convenient to use complexification. The Lie algebra sp(N, C) = sp(N ) ⊕ isp(N ) is the Lie subalgebra of gl(2N, C) defined by the relation

t XJ = -JX. It consists of the matrices A B C -t A
, where A is an arbitrary N × N matrix and B, C are two symmetric N × N matrices. We use the following basis of sp(N, C):

A ij = E ij -E j+N,i+N 1 ≤ i, j ≤ N B ij = E i,j+N + E j,i+N 1 ≤ i < j ≤ N C ij = E i+N,j + E j+N,i 1 ≤ i < j ≤ N D i = E i,i+N 1 ≤ i ≤ N D i+N = E i+N,i 1 ≤ i ≤ N.
The bilinear form •, • takes the following values on this basis:

A ij , A ji = -2 1 ≤ i, j ≤ N B ij , C ij = -2 1 ≤ i < j ≤ N D i , D i+N = -1 1 ≤ i ≤ N.
The other values are zero. It follows that the Casimir element of sp(N, C) is equal to

∆ sp(N,C) = - 1 2 1≤i,j≤N A ij ⊗ A ji - 1 2 1≤i<j≤N (B ij ⊗ C ij + C ij ⊗ B ij ) - 1≤i≤N (D i ⊗ D i+N + D i+N ⊗ D i ).
The formula follows now by a direct computation. In order to recognize operators of the form kl and (kl), observe that, when n = 2 for example,

ρ 2,2N ((12), I N ) = 2N i,j=1 E ij ⊗ E ji , ρ 2,2N ( 12 , I N ) = N i,j=1 (E ij ⊗ E i+N,j+N + E i+N,j+N ⊗ E ij -E i,j+N ⊗ E i+N,j -E i+N,j ⊗ E i,j+N ) .
Proposition 2.9. For all β ∈ B n , the following relation holds:

(13) 2∆ Sp(N ) p st β = -(2N + 1)n p st β - τ ∈Tn p st βτ + α∈Cn p st βα .
More generally, let M 1 , . . . , M n be arbitrary 2N ×2N matrices. Then, regarding

p st β (M 1 S, . . . , M n S) as a function of R ∈ Sp(N ), one has 2∆ Sp(N ) p st β (M 1 S, . . . , M n S) = -(2N + 1)n p st β (M 1 S, . . . , M n S) - τ ∈Tn p st βτ (M 1 S, . . . , M n S) + α∈Cn p st βα (M 1 S, . . . , M n S). (14)

The power series expansion

Let us denote by Tr

N = 1 N Tr the normalized trace on M N (C). Let M 1 , . . . , M n be N × N matrices. Let σ be an element of S n . We denote by p σ (M 1 , . . . , M n ) the number p σ (M 1 , . . . , M n ) = c=(i 1 ...ir) cycle of σ Tr N (M i 1 . . . M ir ).
We denote by ℓ(σ) the number of cycles of σ, so that p σ = N -ℓ(σ) p st σ . In this section, we exploit the result of Proposition 2.4 and derive a convergent power series expansion of E p σ (B t N ) when B is a Brownian motion on U (N ). This expansion involves combinatorial coefficients, which count paths in the Cayley graph of S n . We start by discussing these paths and introducing some notation.

3.1. The Cayley graph of the symmetric group. Fix n ≥ 1. The Cayley graph of S n generated by T n can be described as follows: the vertices of this graph are the elements of S n and two permutations σ 1 and σ 2 are joined by an edge if and only if σ 1 σ -1 2 is a transposition. It is a fundamental observation that, if σ 1 and σ 2 are joined by an edge, then ℓ(σ 1 ) and ℓ(σ 2 ) differ exactly by 1. Indeed, multiplying a permutation by a transposition splits a cycle into two shorter cycles if the points exchanged by the transposition belong originally to the same cycle, and otherwise combines together the two cycles which contain the points exchanged by the transposition.

A finite sequence (σ 0 , . . . , σ k ) of permutations such that σ i is joined to σ i+1 by an edge for each i ∈ {0, . . . , k -1} is called a path of length k. The distance between two permutations is the smallest length of a path which joins them. This distance can be computed explicitly as follows.

Let us introduce the notation |σ| = n -ℓ(σ). We have |σ| ∈ {0, . . . , n -1} and |σ| = 0 (resp. 1, resp. n -1) if and only if σ is the identity (resp. a transposition, resp. a n-cycle). Other values of |σ| do not characterize uniquely the conjugacy class of σ. It is well-known and easy to check that |σ| is the minimal number of transpositions required to write σ. In other words, the graph distance between two permutations σ 1 and σ 2 in the Cayley graph is given by |σ -1 1 σ 2 |.

It turns out that the paths which play the most important role in our problem are those which tend to get closer to the identity. Let γ = (σ 0 , . . . , σ k ) be a path. Recall that, for all i ∈ {0, . . . , k -1}, one has ℓ(σ i+1 ) = ℓ(σ i ) ± 1. We call defect of γ and denote by d(γ) the number of steps which increase the distance to the identity. In symbols,

d(γ) = #{i ∈ {0, . . . , k -1} : |σ i+1 | = |σ i | + 1} = #{i ∈ {0, . . . , k -1} : ℓ(σ i+1 ) = ℓ(σ i ) -1}.
The following lemma is straightforward.

Lemma 3.1. Let γ = (σ 0 , . . . , σ k ) be a path. Then 2d(γ) = k -(ℓ(σ k ) -ℓ(σ 0 )).
For σ, σ ′ in S n and k ≥ 0, let us denote by Π k (σ → σ ′ ) the set of paths of length k which start at σ and finish at σ ′ . Let us also denote by Π k (σ) the set of all paths of length k starting at σ and by Π(σ → σ ′ ) the set of all paths from σ to σ ′ . Notice that the cardinality of Π k (σ) is equal to n 2 k . Let us finally define the coefficients which appear in the expansion. Definition 3.2. Consider σ ∈ S n and two integers k, d ≥ 0. We set

S(σ, k, d) = #{γ ∈ Π k (σ) : d(γ) = d}.
In words, S(σ, k, d) is the number of paths in the Cayley graph of S n starting at σ, of length k and with defect d.

Observe that the adjoint action of S n on itself determines an action of S n on its Cayley graph by automorphisms. Thus, S(σ, k, d) depends only on the conjugacy class of σ.

The main expansion.

Theorem 3.3. Let N, n ≥ 1 be integers. Let (B t ) t≥0 be a Brownian motion on U (N ) starting at the identity and corresponding to the scalar product (X, Y ) → -Tr(XY ) on u(N ). Let M 1 , . . . , M n be arbitrary N × N complex matrices. Let σ be an element of S n . Then, for all t ≥ 0, we have the following series expansions: (15)

E p σ (M 1 B t N , . . . , M n B t N ) = e -nt 2 +∞ k,d=0 (-1) k t k k!N 2d |σ ′ |=|σ|-k+2d #Π k (σ → σ ′ ) p σ ′ (M 1 , . . . , M n ).
In particular, if m 1 , . . . , m r denote the lengths of the cycles of σ, then

(16) E[Tr N (B m 1 t N ) . . . Tr N (B mr t N )] = e -nt 2 +∞ k,d=0 (-1) k t k k!N 2d S(σ, k, d).
For all T ≥ 0, both expansions converge uniformly on (N, t)

∈ N * × [0, T ].
In order to understand the role of the defect of a path in our problem, let us write down the result corresponding to Proposition 2.3 for the functions p σ . As explained earlier, the number of cycles of στ can be either ℓ(σ) + 1 or ℓ(σ) -1, respectively when the two points exchanged by τ belong to the same cycle of σ or to two distinct cycles. For each permutation σ ∈ S n , we are led to partition T n into two classes F (σ) and C(σ), those which fragment a cycle of σ and those which coagulate two cycles. More precisely,

F (σ) = {τ ∈ T (n) : ℓ(στ ) = ℓ(σ) + 1} and C(σ) = {τ ∈ T (n) : ℓ(στ ) = ℓ(σ) -1}.
The following result is now a straightforward consequence of Proposition 2.3. Proposition 3.4. Let σ be a permutation in S n . Let M 1 , . . . , M n be N × N matrices. Then the following relation holds:

1 2N ∆ U (N ) p σ (M 1 U, . . . , M n U ) = - n 2 p σ (M 1 U, . . . , M n U ) + τ ∈F (σ) p στ (M 1 U, . . . , M n U ) + 1 N 2 τ ∈C(σ) p στ (M 1 U, . . . , M n U ).
According to this result, each step which increases the distance to the identity is penalized by a weight N -2 . In the proof of the power series expansion, we use the following lemma. Lemma 3.5. Let t ≥ 0 and N > 0 be real numbers. For all σ, σ ′ ∈ S n and ε ∈ {-1, 1}, define

M ε σ,σ ′ = +∞ k=0 ε k t k k! #Π k (σ → σ ′ ) N k-(ℓ(σ ′ )-ℓ(σ)) .
Then the matrices

(M 1 σ,σ ′ ) σ,σ ′ ∈Sn and (M -1 σ,σ ′ ) σ,σ ′ ∈Sn are each other's inverse. Proof -Let us define an endomorphism L of C[S n ] by setting, for all f ∈ C[S n ], (Lf )(σ) = τ ∈F (σ) f (στ ) + 1 N 2 τ ∈C(σ) f (στ ).
One checks easily that the matrix M ε σ,σ ′ is the matrix of the operator e εtL on C[S n ] and the result follows.

Proof of Theorem 3.3 -Consider T ≥ 0. We claim that the right-hand side of ( 15) is a normally convergent series on (N, t)

∈ N * ×[0, T ]. Indeed, let us define K = max{|p σ (M 1 , . . . , M n )| : σ ∈ S n }.
Then, for all N ≥ 1 and all t ∈ [0, T ], the sum of the absolute values of the terms of the series is smaller than

Ke -nt 2 +∞ k=0 T k k! +∞ d=0 S(σ, k, d) = Ke n(n-2) 2
T .

The assertion on the uniform convergence of the expansions follows.

In order to prove [START_REF] Lando | Graphs on surfaces and their applications[END_REF], we start from the expression given by Proposition 2.4, at time t N and with an arbitrary deterministic initial condition π 0 = σ. It reads [START_REF] Kreweras | Sur les partitions non croisées d'un cycle[END_REF] ∀σ ∈ S n , E p st

π t N (M 1 B t N , . . . , M n B t N ) π 0 = σ = e -nt 2 -n(n-1)t 2N p st σ (M 1 , . . . , M n ).
We expand the left hand side by using the properties of (π t ) t≥0 . This chain jumps at rate n 2 and its jump chain is a standard discrete-time random walk on the Cayley graph of S n , independent of the jump times. Thus, the left-hand side of ( 17) is equal to

∞ k=0 e -( n 2 ) t N n 2 k t k k!N k 1 n 2 k σ ′ ∈Sn γ∈Π k (σ→σ ′ ) E p st σ ′ (M 1 B t N , . . . , M n B t N ) ,
where the expectation is now only with respect to the Brownian motion. After simplification and switching to normalized traces, [START_REF] Kreweras | Sur les partitions non croisées d'un cycle[END_REF] becomes

∀σ ∈ S n , σ ′ ∈Sn E p σ ′ (M 1 B t N , . . . , M n B t N ) ∞ k=0 t k k! #Π k (σ → σ ′ ) N k-(ℓ(σ ′ )-ℓ(σ)) = e -nt 2 p σ (M 1 , . . . , M n ).
We recognize the expression of M 1 σ,σ ′ and, by Lemma 3.5, we conclude that for all σ ∈ S n ,

E p σ (M 1 B t N , . . . , M n B t N ) = e -nt 2 ∞ k=0 (-1) k t k k! σ ′ ∈Sn #Π k (σ → σ ′ ) N k-(ℓ(σ ′ )-ℓ(σ)) p σ ′ (M 1 , . . . , M n ).
The first formula follows from the fact that |σ| = n -ℓ(σ). Setting M 1 , . . . , M N equal to I N yields the second formula.

Most of the coefficients which appear in the expansion ( 16) are zero. More precisely, the situation is the following. Lemma 3.6. Let γ be a path of length k and defect d starting at σ. Then the following inequalities hold:

0 ≤ d ≤ k and 2d -(ℓ(σ) -1) ≤ k ≤ 2d + (n -ℓ(σ)). In particular, |k -2d| ≤ n -1.
Moreover, let d ≥ 0 be given. Then S(σ, 2d

+ (n -ℓ(σ)), d) > 0 and, if d ≥ ℓ(σ) -1, then S(σ, 2d -(ℓ(σ) -1), d) > 0. Finally, if d ≤ ℓ(σ) -1, then S(σ, d, d) > 0.
Proof -Assume that the path finishes at σ k . Then the first two inequalities reflect simply the fact that 1 ≤ ℓ(σ k ) ≤ n.

To prove the second part of the statement, consider d ≥ 0. Recall that σ is fixed. Let us construct a longest possible path starting at σ with defect d. For this, we minimize the defect at each step. First, we build a path by going from σ down to the identity through a geodesic. This takes n -ℓ(σ) steps and the defect of the path is still zero. Then the path must make one step up. Immediately after this, it can go down to the identity again. It can repeat this at most d times without its defect becoming larger than d. By then it has length 2d + (n -ℓ(σ)). Thus we have constructed a path of length 2d + (n -ℓ(σ)) with defect d. A similar argument works for a shortest path of given defect.

In particular, for all d ≥ 0, the contribution of order N -2d to E[p σ (B t N )] is a polynomial function of t of degree 2d + (n -ℓ(σ)) and in which the smallest exponent of t is max(d, 2d -(ℓ(σ) -1)).

Examples. Let us work out explicitly a few examples.

For n = 1: there is a single path in the Cayley graph of S 1 . It has length and defect 0. Thus, we recover the well-known formula

E Tr N (B t N ) = e -t 2 .
For n = 2: for each k ≥ 0 there is a unique path of length k starting at the identity. It has defect ⌊ k+1 2 ⌋. Thus,

E Tr N (B t N ) 2 = e -t ∞ k=0 (-1) k t k k!N 2⌊ k+1 2 ⌋ = e -t cosh t N - 1 N sinh t N .
Similarly, for each k ≥ 0, there is a unique path of length k starting at [START_REF] Macdonald | Symmetric functions and Hall polynomials, 2nd Edition, Oxford Mathematical Monographs[END_REF]. It has defect ⌊ k 2 ⌋. Thus,

E Tr N (B 2 t N ) = e -t ∞ k=0 (-1) k t k k!N 2⌊ k 2 ⌋ = e -t cosh t N -N sinh t N .
For n = 3: the situation is a bit more complicated but it is still possible to compute everything by hand. For a path starting at the identity of length k and defect d, we must have 2d-2 ≤ k ≤ 2d.

Hence, if k is odd, it must be equal to 2d -1. So, for all l ≥ 1, S(id, 2l -1, l) = 3 2l-1 . If k is even, then two situations are possible. We leave it as an exercise to check that, for all l ≥ 1, S(id, 2l, l) = 3 2l-1 and S(id, 2l, l + 1) = 2.3 2l-1 . Finally, S(id, 0, 0) = 1. We find

E Tr N (B t N ) 3 = e -3t 2 1 + N 2 + 2 3N 2 cosh 3t N -1 - 1 N sinh 3t N .
Similarly, we find

E Tr N (B 2 t N )Tr N (B t N ) = e -3t 2 cosh 3t N - N 2 + 2 3N sinh 3t N , E Tr N (B 3 t N ) = e -3t 2 1 + N 2 + 2 3 cosh 3t N -1 -N sinh 3t N .
For n ≥ 4, it seems difficult to determine all the coefficients at once and by hand. Nevertheless, the following diagram, which indicates how many edges join the various conjugacy classes of S 4 in the Cayley graph allows one to compute specific values of S(σ, k, d).

( For instance, one can use it to prove the following formulae :

) 3 % % K K K K K K K K K 3 z z u u u u u u u u u 123
e 2t E Tr N (B t N ) 4 = 1 + 1 N 2 (-6t + 3t 2 ) + 1 N 4 (15t 2 -20t 3 + 5t 4 ) + O( 1 N 6
),

e 2t E Tr N (B 4 t N ) = (1 -6t + 8t 2 - 8 3 t 3 ) + 1 N 2 (10t 2 - 58 3 t 3 + 71 4 t 4 - 16 3 t 5 ) + O( 1 N 4 ).
3.4. The case of SU (N ). Let us conclude this section by stating without proof the following analogue of Theorem 3.3 in the case of the the special unitary group. This theorem is proved exactly like its unitary version, by using the observation made at the end of Section 2.1.

Theorem 3.7. Let N, n ≥ 1 be integers. Let (B t ) t≥0 be a Brownian motion on SU (N ) starting at the identity and corresponding to the scalar product (X, Y ) → -Tr(XY ) on su(N ). Let M 1 , . . . , M n be arbitrary N × N complex matrices. Let σ be an element of S n . Then, for all t ≥ 0, we have the following series expansion:

E p σ (M 1 B t N , . . . , M n B t N ) = e -nt 2 + n 2 t 2N 2 +∞ k,d=0 (-1) k t k k!N 2d × |σ ′ |=|σ|-k+2d #Π k (σ → σ ′ ) p σ ′ (M 1 , . . . , M n ). ( 18
)
In particular, if m 1 , . . . , m r denote the lengths of the cycles of σ, then

(19) E[Tr N (B m 1 t N ) . . . Tr N (B mr t N )] = e -nt 2 + n 2 t 2N 2 +∞ k,d=0 (-1) k t k k!N 2d S(σ, k, d).
For all T ≥ 0, both expansions converge uniformly on (N, t) ∈ N * × [0, T ].

A representation-theoretic derivation of the power series expansions

In this section, we give an alternative derivation of the expansions ( 16) and ( 19), based on the representation theory of the unitary and symmetric groups and the relations between symmetric functions. This approach is less elementary than the one adopted in the previous sections but we believe that it is more likely to allow generalizations. In Section 5, we will use it to compute some of the coefficients S(σ, k, d).

4.1.

Expansion for the unitary group. The integers N, n ≥ 1 are fixed throughout this section. We write λ ⊢ n if λ = (λ 1 ≥ . . . ≥ λ r > 0) is a partition of n. The integer r is called the length of λ and we denote it by ℓ(λ). We denote the set of all partitions by P.

Let λ be a partition of n. We denote by s λ the Schur function associated to the partition λ, whose definition is given in [12, I.3]. For all U ∈ U (N ), the number s λ (U ) is defined as the value of s λ on the eigenvalues of U . We will use the fact that, if ℓ(λ) > N , then the symmetric polynomial in N variables determined by s λ is the zero polynomial. This follows for example from the expression of s λ as a determinant in the elementary symmetric functions [12, I.3, (3.5)].

Recall the definition of the power sums, that is, the functions p st σ : U (N ) -→ C for σ ∈ S n (see Definition 2.1).

The Schur functions and the power sums are related as follows. Let χ λ : S n -→ C denote the character of the irreducible representation of S n associated with λ. Then one has the following pair of relations [12, I.7,(7.7)]:

(20) ∀λ ⊢ n, s λ = 1 n! σ∈Sn χ λ (σ)p st σ , (21)
∀σ ∈ S n , p st σ = λ⊢n χ λ (σ)s λ .

The set U (N ) of isomorphism classes of irreducible representations (irreps) of U (N ) is in one-to-one correspondence with the set Z N ↓ of non-increasing sequences α = (α 1 ≥ . . . ≥ α N ) of elements of Z. Even when some of the α i 's are negative, the Schur function s α is well-defined and the character of the irrep α is χ α (U ) = s α (U ).

Let (B t ) t≥0 be the Brownian motion on U (N ) of Theorem 3.3. Let dU denote the normalized Haar measure on U (N ). For each t > 0, let Q t denote the heat kernel at time t on U (N ), that is, the density of the distribution of B t with respect to the Haar measure. Our main result is the following reformulation of ( 16). Theorem 4.1. Let N, n ≥ 1 be integers. Let σ be an element of S n . Then, for all t ≥ 0, ( 22)

N -ℓ(σ) U (N ) p st σ (U )Q t N (U ) dU = e -nt 2 +∞ k,d=0 (-1) k t k k!N 2d S(σ, k, d).
In the course of the proof, we admit two lemmas which we prove afterwards. We have preferred this order to the strict logical order to make the proof easier to follow.

Proof -If t = 0, the result is clearly true. When t > 0, the proof consists in expanding Q t into the sum of its Fourier series and turning all quantities related to U (N ) into quantities related to S n . For all t > 0, the function Q t is smooth on U (N ) and invariant by conjugation. It admits the following uniformly convergent Fourier expansion [13, Thm 4.4]:

(23) Q t (U ) = α∈Z N ↓ e -c 2 (α)t 2 s α (I N )s α (U ),
where the number c 2 (α) is characterized by the equality ∆ U (N ) χ α = -c 2 (α)χ α . Using the relation [START_REF] Voiculescu | Free random variables[END_REF] to expand p st σ (U ), we find the following expression for the left-hand side of ( 22):

U (N ) p st σ (U )Q t N (U ) dU = α∈Z N ↓ ,µ⊢n e -c 2 (α)t 2N s α (I N )χ µ (σ) U (N ) s α (U )s µ (U ) dU.
By the orthogonality properties of the characters of irreps, the integral in the right-hand side is zero unless α = µ. Hence, we can replace the sum over α and µ by a sum over the partitions µ such that µ ⊢ n and ℓ(µ) ≤ N :

(24)

U (N ) p st σ (U )Q t N (U ) dU = µ⊢n,ℓ(µ)≤N e -c 2 (µ)t 2N s µ (I N )χ µ (σ).
We still need to express s µ (I N ) and c 2 (µ) in terms of quantities related to the symmetric group.

In order to compute s µ (I N ), we use the relation [START_REF] Biane | On the free convolution with a semi-circular distribution[END_REF]. Let us define Ω = σ∈Sn N ℓ(σ) σ. This notation is borrowed from [START_REF] Gross | Twists and Wilson loops in the string theory of two dimensional QCD[END_REF]. Then [START_REF] Biane | On the free convolution with a semi-circular distribution[END_REF] implies the equality

(25) s µ (I N ) = 1 n! χ µ (Ω).
In Lemma 4.3, we will prove that χ µ (Ω) = 0 if ℓ(µ) > N . This allows us to drop the restriction ℓ(µ) ≤ N in the summation. Let us compute c 2 (µ), the eigenvalue of ∆ U (N ) associated to s µ . Thanks to (5), we know the value of ∆ U (N ) p st σ for all σ and (20) expresses s µ as a linear combination of power sums. Combining these two equations, we find

(26) ∆ U (N ) s µ = -N ns µ - 2 n! σ∈Sn τ ∈Tn χ µ (στ )p st σ ,
where T n is the set of the transpositions of S n . We now use the following consequence of Schur's lemma: whenever x belongs to the group algebra C[S n ] and y to the centre of the group algebra,

(27) ∀µ ⊢ n, χ µ (xy) = χ µ (x)χ µ (y) χ µ (1)
.

This relation implies that the last term of ( 26) is equal to n(n -1) χ µ (( 12)) χ µ (1) s µ . Hence,

(28) c 2 (µ) = nN + n(n -1) χ µ (( 12
)) χ µ (1) .
Combining (24), ( 25) and (28), we find

U (N ) p st σ (U )Q t N (U ) dU = e -nt 2 k≥0 (-t) k k! µ⊢n χ µ (Ω)χ µ (σ) n! n(n -1) 2N χ µ (( 12
)) χ µ (1) k .
By Lemma 4.2 below, the sum over µ is equal to N ℓ(σ) d≥0 N -2d S(σ, k, d). The result follows immediately.

Lemma 4.2. Let σ be an element of S n . Let k ≥ 0 be an integer. Then

(29) d≥0 S(σ, k, d) N 2d = N -ℓ(σ)-k µ⊢n χ µ (Ω)χ µ (σ) n! n(n -1) 2 χ µ ((12)) χ µ (1) k .
Proof -There is no issue of convergence, since the sum on the left-hand side is finite. Let γ = (σ 0 , . . . , σ k ) be a path of defect d.

By Lemma 3.1, ℓ(σ k ) = ℓ(σ 0 ) + k -2d. Hence, d≥0 S(σ, k, d) N 2d = N -ℓ(σ)-k σ ′ ∈Sn #Π k (σ → σ ′ )N ℓ(σ ′ ) . Now, #Π k (σ → σ ′ ) is the number of k-tuples (τ 1 , . . . , τ k ) ∈ T k n such that στ 1 . . . τ k = σ ′ .
A standard computation based on the fact that µ⊢n χ µ (1)χ µ (σ) = n!δ σ,id and on (27) leads to

#Π k (σ → σ ′ ) = µ⊢n χ µ (1)χ µ (σ -1 σ ′ ) n! n(n -1) 2 χ µ (( 12
)) χ µ (1) k .
The result follows by summing over σ ′ and applying (27) again. 1. For all µ ⊢ n such that ℓ(µ) ≤ N , χ µ (Ω) = n!s µ (I N ).

2. For all µ ⊢ n such that ℓ(µ) > N , χ µ (Ω) = 0.

Proof -The first assertion follows immediately from [START_REF] Biane | On the free convolution with a semi-circular distribution[END_REF].

In order to prove the second assertion, let us introduce the Jucys-Murphy elements X 1 , . . . , X n of C[S n ], defined by X 1 = 0 and X i = (1 i) + (2 i) + . . . + (i -1 i) for i ∈ {2, . . . , n}. They generate a maximal Abelian subalgebra of C[S n ]. In particular, they can be simultaneously diagonalized in every irreducible representation of S n . We borrow the following statements from [START_REF] Okounkov | A new approach to representation theory of symmetric groups[END_REF].

Let µ = (µ 1 , . . . , µ r ) be a partition of n. The subset D µ = {(i, j) ∈ (N * ) 2 : j ≤ µ i } of Z 2 is called the diagram of µ. An element (i, j) of D µ is called a box and its content is defined as the integer c(i, j) = j -i.

The space of the irreducible representation of S n associated to µ admits a basis which diagonalizes the Jucys-Murphy elements and is indexed by the bijections t : D µ -→ {1, . . . , n} which are increasing in each variable. These bijections are usually called tableaux. The eigenvalue of the Jucys-Murphy element X k on the vector associated to the tableau t is the content of the box t -1 (k).

We need also the following well-known fact: for every k ∈ {0, . . . , n -1}, the k-th elementary symmetric function of the Jucys-Murphy elements is equal to σ∈Sn 1 |σ|=k σ, where |σ| = n -ℓ(σ). This can be proved as follows. For each m ∈ {1, . . . , n}, let us imbed S m into S n as the subgroup which leaves {m+1, . . . , n} invariant. For all m ∈ {1, . . . , n} and k ∈ {0, . . . , m-1}, set Σ m,k = σ∈Sm 1 |σ|=k σ. Let us also define e m,k = i 1 <...<i k ≤m X i 1 . . . X i k . We need to prove that e m,k = Σ m,k . This is clearly true if k ∈ {0, 1}. The general case follows by induction on m, each inductive step being proved by induction on k, thanks to the relations

Σ m,k = Σ m-1,k + Σ m-1,k-1 X k and e m,k = e m-1,k + e m-1,k-1 X k .
From the equality proved in the last paragraph and the relation |σ| = n -ℓ(σ), we deduce the following equality in the polynomial ring C[S n ][z]:

(30) n i=1 (z + X i ) = σ∈Sn z ℓ(σ) σ.
Evaluating at z = N and applying χ µ , we find

χ µ (Ω) = χ µ n i=1 (N + X i ) = t tableau n i=1 (N + c(t -1 (i))) = χ µ (1) ℓ(µ) i=1 µ i j=1 (N + j -i).
If ℓ(µ) ≥ N +1, then (N +1, 1) is a box of D µ , whose content is -N . It follows that χ µ (Ω) = 0 in this case. 4.2. Expansion for the special unitary group. Let us apply a similar analysis to the special unitary group in order to derive [START_REF] Biane | Segal-Bargmann transform, functional calculus on matrix spaces and the theory of semi-circular and circular systems[END_REF] in another way.

By restriction, any irrep of U (N ) determines an irrep of SU (N ) and the restrictions of α, α ′ ∈ Z N ↓ are isomorphic if and only if there exists k ∈ Z such that α ′ = (α 1 + k, . . . , α N + k). Hence, the set of irreps of SU (N ) is in one-to-one correspondence with the set of partitions of length at most N -1 and the character of the irreducible representation corresponding to a partition λ is given by the Schur function s λ .

Let (B t ) t≥0 be the Brownian motion on SU (N ) of Theorem 19. Let dU denote the Haar measure on SU (N ). For each t > 0, let Q t denote the heat kernel at time t on SU (N ), that is, the density of the distribution of B t with respect to the Haar measure. We reformulate [START_REF] Biane | Segal-Bargmann transform, functional calculus on matrix spaces and the theory of semi-circular and circular systems[END_REF] as follows.

Theorem 4.4. Let N, n ≥ 1 be integers. Let σ be an element of S n . Then, for all t ≥ 0, (31)

N -ℓ(σ) SU (N ) p st σ (U )Q t N (U ) dU = e -nt 2 + tn 2 2N 2 +∞ k,d=0 (-1) k t k k!N 2d S(σ, k, d).
Proof -If t = 0, both sides are equal to 1. Assume that t > 0. The Fourier expansion of Q t is then the following:

(32) Q t (U ) = λ∈P ℓ(λ)≤N -1 e -c ′ 2 (λ)t 2 s λ (I N )s λ (U ),
where now c ′ 2 (λ) is defined by the equality ∆ SU (N ) χ λ = -c ′ 2 (λ)χ λ . Combined with the relation [START_REF] Voiculescu | Free random variables[END_REF], it implies

SU (N ) p st σ (U )Q t N (U ) dU = λ∈P,µ⊢n ℓ(λ)≤N -1 e -c ′ 2 (λ)t 2N s λ (I N )χ µ (σ) SU (N ) s λ (U )s µ (U ) dU.
When ℓ(µ) > N , s µ is identically zero on SU (N ). When ℓ(µ) ≤ N -1, then the integral in the right-hand side of the last equation is equal to δ λ,µ . Let us consider the terms of the sum for which ℓ(µ) = N . In this case, let us write µ = µ ′ +(µ N , . . . , µ N ), so that ℓ(µ ′ ) ≤ N -1. Then the integral is equal to δ λ,µ ′ and we may assume that λ = µ ′ . In this case,

s λ (I N ) = s µ ′ (I N ) = s µ (I N ) and c ′ 2 (λ) = c ′ 2 (µ ′ ). Hence, SU (N ) p st σ (U )Q t N (U ) dU = µ⊢n,ℓ(µ)≤N -1 e -c ′ 2 (µ)t 2N s µ (I N )χ µ (σ) + µ⊢n,ℓ(µ)=N e -c ′ 2 (µ ′ )t 2N s µ (I N )χ µ (σ).
Let us first compute c ′ 2 (µ) when ℓ(µ) ≤ N -1. For this, we use the fact that s µ is an eigenvector of ∆ U (N ) whose restriction to SU (N ) is s µ . Since ∆ SU (N ) p st σ = ∆ U (N ) + n 2 N p st σ whenever σ ∈ S n , we find, thanks to (27),

∆ SU (N ) s µ = -N n -n(n -1) χ µ ((12)) χ µ (1) + n 2 N s µ .
When ℓ(µ) = N , we are interested in s µ ′ but s µ is still an eigenvector of ∆ U (N ) whose restriction to SU (N ) is s µ ′ . Hence,

∆ SU (N ) s µ ′ = ∆ SU (N ) s µ = -N n -n(n -1) χ µ (( 12
)) χ µ (1) + n 2 N s µ = -c ′ 2 (µ ′ )s µ ′ .
Thus, in both sums, the argument of the exponential is

-nt 2 + n 2 t 2N 2 -t n(n-1)

2N

χ µ (( 12))

χ µ [START_REF] Biane | Free Brownian motion, free stochastic calculus and random matrices[END_REF] . Using this fact and the first assertion of Lemma 4.3, we find

SU (N ) p st σ (U )Q t N (U ) dU = e -nt 2 + n 2 t 2N 2 µ⊢n,ℓ(µ)≤N e -t n(n-1) 2N χ µ (( 12
)) χ µ (1) χ µ (Ω)χ µ (σ) n! .
The second assertion of Lemma 4.3 tells us that we can remove the restriction ℓ(µ) ≤ N , since the other terms are zero. After expanding the exponential, Lemma 4.2 allows us to finish the proof just as in the unitary case.

Computation of S((1 . . . n), k, d).

In this section, we apply the methods of representation theory to the computation of some of the coefficients which appear in our main expansions, namely the coefficients S((1 . . . n), k, d) for all n, k, d ≥ 0.

Let us recall the definition of the Stirling cycle numbers, or Stirling numbers of the first kind s(n, k), also denoted by n k . They are characterized by the identities in C[x]

x(x -1) . . .

(x -n + 1) = n k=0 n k x k ,
valid for all n ≥ 0. In other words,

n k = (-1) n-k e n-k (1, . . . , n -1) = (-1) n-k 1≤i 1 <...<i n-k ≤n-1 i 1 . . . i n-k ,
where e n-k denotes the (n -k)-th elementary symmetric function.

By applying the alternating character to the identity (30), we find the relation

σ∈Sn ε(σ)x ℓ(σ) = x(x -1) . . . (x -n + 1) = n k=0 n k x k ,
from which we deduce that n k is the number of elements of S n with exactly k cycles, or in other words at distance n -k from the identity. In particular, n 0 = 0. Let us make the convention that n k = 0 if k < 0. The main result of this section is the following. Proposition 5.1. For all n, k, d ≥ 0,

S((1 . . . n), k, d) = 1 n r,s,l,m≥0 r+s=n-1 l+m=n-1-k+2d (-1) l+r r!s! n 2 (s -r) k s + 1 s + 1 -l r + 1 r + 1 -m .
. n), k, d) = 1 (n -1)! σ∈Sn,|σ|=n-1 S(σ, k, d) = 1 (n -1)! σ,π∈Sn,|σ|=n-1,|π|=n-1-k+2d #Π k (σ → π) = 1 (n -1)! λ⊢n χ λ (Σ n-1 )χ λ (Σ n-1-k+2d ) n! χ λ (Σ 1 ) χ λ (id) k . ( 33
)
Now we use the following fact, which is a consequence of the description of the representations of S n given by Okounkov and Vershik [START_REF] Okounkov | A new approach to representation theory of symmetric groups[END_REF] and recalled briefly in the proof of Lemma 4.3:

(34) ∀r ∈ {0, . . . , n -1} , χ λ (Σ r ) χ λ (id) = e r ({c( ) : ∈ λ}) .
In words, the right-hand side of this equation is the r-th elementary symmetric function of the contents of the boxes of the diagram of λ. In particular, if the diagram of λ has at least two boxes of content 0, then χ λ (Σ n-1 ) = 0. Hence, the non-zero terms of the sum (33) arise from the partitions which are hooks, that is, of the form η r = (n -r 1 r ) for some r ∈ {0, . . . , n -1}. This fact is well known (see for example the appendix of [START_REF] Lando | Graphs on surfaces and their applications[END_REF]), and η r is the representation r St, where St is the restriction of the natural representation of S n on C n to the hyperplane of equation {z 1 + . . . + z n = 0}. This representation is of degree n-1 r and χ ηr ((1 . . . n)) = (-1) r . Let us introduce the notation s = n -1 -r. It follows easily from (34) that (35) ∀r ∈ {0, . . . , n -1} , χ ηr (Σ 1 )

χ ηr (id) = n(n -1) 2 -nr = n 2 (s -r).
The contents of the boxes of η r are {-r, . . . , 0, . . . , s}. Hence, by the definition of the Stirling numbers and (34), we have for all r ∈ {0, . . . , n -1}

χ ηr (Σ n-1-k+2d ) χ ηr (id) = e n-1-k+2d (-r, . . . , 0, . . . , s) = l,m≥0 l+m=n-1-k+2d e l (1, . . . , s)(-1) m e m (1, . . . , r) = l,m≥0 l+m=n-1-k+2d (-1) l s + 1 s + 1 -l r + 1 r + 1 -m . (36)
Finally, combining (35) and (36), we find the expected result.

It seems that Proposition 5.1 should allow one to find a simple generating function for the numbers S((1 . . . n), k, d). Our best result in this direction is the following. We use the notation (x) n = x(x -1) . . . (x -n + 1). Proposition 5.2. For all n, N ≥ 0, one has

k,d≥0 (-1) k t k d!N 2d S((1 . . . n), k, d) = (-1) n n r,s≥0 r+s=n-1 1 r!s! e 1 4N 2 (s-r) 2 n 2 t 2 nt 2 (s -r) s+1 - nt 2 (s -r) r+1 .
We emphasize that this generating function is, unfortunately, exponential with respect to d instead of k.

In Proposition 5.1, when k takes the largest possible value given n and d, namely n -1 + 2d, then l and m must be equal to 0 and the identity n n = 1 simplifies greatly the expression. This leads us to the following corollary.

Corollary 5.3. Let n ≥ 1 be an integer. For each p ≥ 0, let c n,p denote the number of distinct ways in which the cycle (1 . . . n) ∈ S n can be written as a product of p transpositions. The number c n,p is non-zero if and only if p = n -1 + 2d for some d ≥ 0. In this case,

c n,p = S((1 . . . n), n -1 + 2d, d) = n p n! n-1 r=0 (-1) r n -1 r n -1 2 -r p .
For each n ≥ 1, one has the equality

p≥0 c n,p x p p! = 1 n! e n(n-1) 2
x 1 -e -nx n-1 .

In particular, c n,n-1 = n n-2 , c n,n+1 = 1 24 (n 2 -1)n n+1 and

c n,n+3 = 1 5760 (5n -7)(n + 3)(n + 2)(n 2 -1)n n+3 .
Remark 5.4. The value of c n,n-1 is classical. The sequence (c n,n+1 ) n≥1 is known as A060603 in the Online Encyclopedia of Integer Sequences [START_REF] Sloane | The On-Line Encyclopedia of Integer Sequences[END_REF].

Asymptotic distribution

One of the consequences of Theorem 3.3 is that the limit as N tends to infinity of E[p σ (B t N )] exists. Using Lemma 3.6, we get the following result. Proposition 6.1. Consider σ ∈ S n . The limit of E[p σ (B t N )] as N tends to infinity exists and it is equal to

lim N →∞ E p σ (B t N ) = e -nt 2 |σ| k=0 (-1) k S(σ, k, 0) k! t k .
Unfortunately, Proposition 5.1 does not seem to lead easily to a simple expression for S(σ, k, 0) nor even S((1 . . . n), k, 0). In this section, we determine a simple expression of S(σ, k, 0) for all σ and k ≥ 0. For this, we prove a factorization property and use the relation between the metric geometry of the Cayley graph of S n and the lattice of non-crossing partitions of the cycle (1 . . . n). The fact that the two expressions of S((1 . . . n), k, 0) given by Propositions 5.1 and 6.6 agree is not obvious, at least for the author.

6.1. The factorization property. The factorization property is the following result. It reduces the problem of the determination of S(σ, k, 0) to the case where σ is a cycle. Proposition 6.2. Let m 1 , . . . , m r be positive integers. Then

lim N →∞ E Tr N (B m 1 t N ) . . . Tr N (B mr t N ) = lim N →∞ E Tr N (B m 1 t N ) . . . lim N →∞ E Tr N (B mr t N
) .

More precisely,

(37) E Tr N (B m 1 t N ) . . . Tr N (B mr t N ) -E Tr N (B m 1 t N ) . . . E Tr N (B mr t N ) = O(N -2 ),
uniformly in t on bounded intervals.

We start by proving the following property of the numbers S(σ, k, 0). It is in fact equivalent to the proposition. Proposition 6.3. Consider σ ∈ S n . Assume that σ = c 1 . . . c ℓ(σ) is the decomposition of σ as a product of cycles with disjoint support. Then

(38) ∀k ≥ 0 , S(σ, k, 0) = l 1 +...+l ℓ(σ) =k k! l 1 ! . . . l ℓ(σ) ! S(c 1 , l 1 , 0) . . . S(c ℓ(σ) , l ℓ(σ) , 0).
Proof -The number S(σ, k, 0) is the number of paths of length k starting at σ and which at each step move towards a permutation with one more cycle than their current position. As we already observed several times, each step of such a path corresponds to the multiplication by a transposition which exchanges two points which belong to the same cycle of σ. There is thus a natural partition of the set of all steps of such a path, according to the cycle of σ in which their support is contained. Let us introduce some notation. Let (σ 0 = σ, σ 1 , . . . , σ k ) be a path with defect zero. For each i ∈ {1, . . . , k}, set τ i = σ -1 i-1 σ i . Let (C 1 , . . . , C ℓ(σ) ) be the partition of {1, . . . , k} determined by the fact that i ∈ C j if and only if the support of τ i is contained in the support of c j . Then it is clear that, for all j ∈ {1, . . . , ℓ(σ)}, the transpositions (τ i , i ∈ C j ) are the steps of a path with defect zero starting from c j .

Hence, constructing a path of length k starting at σ and with defect zero is equivalent to constructing a collection of ℓ(σ) paths with defect zero starting at c 1 , . . . , c ℓ(σ) respectively, whose lengths l 1 , . . . , l ℓ(σ) add up to k, and a shuffling of the steps of these paths, that is, a sequence (C 1 , . . . , C ℓ(σ) ) of subsets of {1, . . . , k} which partition {1, . . . , k} and whose cardinals are l 1 , . . . , l ℓ(σ) respectively. The equation ( 38) is just the translation in symbols of the last sentence.

Proof of Proposition 6.2 -By Theorem 3.3 and Proposition 6.3, the terms of degree N 0 of the difference on the left hand side of (37) vanish. Hence, this difference is of the form N -2 F (t, N -2 ) for some entire function F . The result follows.

We have observed after Definition 3.2 that S(σ, k, d) depends only on the conjugacy class of σ. Hence, we need to compute S((1 . . . m), k, 0). The arguments of the proof of Proposition 6.3 show that the paths of defect 0 starting at (1 . . . m) stay in S m if we identify S m with the subgroup of S n which leaves {m+1, . . . , n} invariant. Hence, we are reduced to the computation of S((1 . . . n), k, 0) for all n ≥ 1 and k ∈ {0, . . . , n -1}. This computations involves non-crossing partitions. For the sake of being self-contained, we give a brief review of the properties of non-crossing partitions that we use. 6.2. Non-crossing partitions. Let P = {P 1 , . . . , P ℓ } be a partition of {1, . . . , n}. The partition P is said to be non-crossing if there does not exist i, j, k, l ∈ {1, . . . , n} such that i < j < k < l and r, s ∈ {1, . . . , ℓ} with r = s such that i, k ∈ P r and j, l ∈ P s . Another way to formulate the fact that P is non-crossing is the following. For each class P j of the partition, let H j denote the convex hull in C of {e 2ikπ n

: k ∈ P j }. Then P is non-crossing if and only if for all i, j ∈ {1, . . . , ℓ}, i = j ⇒ H i ∩ H j = ∅. This notion is relative to the cyclic order on {1, . . . , n} determined by (1 . . . n). We denote by N C(n) the set of non-crossing partitions of the cycle (1 . . . n). This set has been first considered by Kreweras in [START_REF] Kreweras | Sur les partitions non croisées d'un cycle[END_REF].

The fineness relation between partitions restricted to N C(n) makes N C(n) a poset. More precisely, we say that P 1 P 2 if every class of P 1 is contained in a class of P 2 . The poset (N C(n), ) is in fact a lattice, which means that suprema and infima exist. There is in particular a maximum, {{1, . . . , n}}, which we denote by 1 n , and a minimum, {{1}, . . . , {n}}, which we denote by 0 n . The poset N C(n) can be made into a graph by joining two partitions P and Q if they are distinct and comparable, say P ≺ Q, and the interval [P, Q] = {R ∈ N C(n) : P R Q} is reduced to {P, Q}.

A non-crossing partition P = (P 1 , . . . , P ℓ ) of the cycle (1 . . . n) determines an element σ P of S n as follows: take the cycles of σ P to be the classes of P with the cyclic order induced by (1 . . . n). In symbols, if i ∈ P j , then

σ P (i) = (1 . . . n) k (i) , where k = min{l ≥ 1 : (1 . . . n) l (i) ∈ P j }.
In particular, σ 0n = id and σ 1n = (1 . . . n). The partial order on N C(n) corresponds via the mapping P → σ P to the following partial order on S n .

Consider

σ 1 , σ 2 ∈ S n . Recall that |σ 1 | = n -ℓ(σ 1 )
, the minimal number of terms of a decomposition of σ 1 in a product of transpositions, is the distance from id to σ 1 in the Cayley graph of S n generated by T n . By definition, we say that σ 1

σ 2 if |σ 2 | = |σ 1 | + |σ -1 1 σ 2 |.
In words, σ 1 σ 2 if and only if there exists a geodesic path from id to σ 2 through σ 1 . The identity is the minimum of S n for this partial order, and the n-cycles the (pairwise incomparable) maximal elements. The next lemma is well known and its proof is left to the reader. As a consequence of this Lemma, S((1 . . . n), k, 0) is the number of decreasing paths of length k starting at 1 n in N C(n). It turns out to be easier to count increasing paths in N C(n) starting at 0 n . They are in one-to-one correspondence by the following duality property of N C(n) discovered by Kreweras. For σ ∈ [id, (1 . . . n)], let us introduce K(σ) = σ -1 (1 . . . n). It is readily checked that K is a decreasing bijection of [id, (1 . . . n)]. The corresponding decreasing bijection of N C(n) is called the Kreweras complementation. It can be described combinatorially at the level of non-crossing partitions as follows.

Given a partition R of {1, . . . , n} and a partition S of {1, . . . , n} ≃ { 1, . . . , n}, let R ∪ S denote the partition of {1, 1, 2, 2, . . . , n, n} obtained by merging R and S. Even if R and S are non-crossing, R ∪ S may be crossing with respect to the cyclic order (1, 1, 2, 2, . . . , n, n). Now let P be a non-crossing partition of {1, . . . , n}. The partition K(P ) is by definition the largest element of N C(n) such that P ∪ K(P ) is non-crossing.

The following result summarizes this discussion of non-crossing partitions in relation to our problem. Proposition 6.5. For all n ≥ 1 and k ≥ 0, S((1 . . . n), k, 0) is the number of increasing paths of length k starting at {{1}, . . . , {n}} in the lattice of non-crossing partitions of (1 . . . n). It remains to count these paths. To do this, we use the fact that S((1 . . . n), n -1, 0) = n n-2 . This is a classical result of combinatorics, since S((1 . . . n), n -1, 0) is the number of ways to write a n-cycle as a product of n -1 transpositions. It is also a special case of Corollary 5.3. Proposition 6.6. For all n ≥ 1 and k ≥ 0,

S((1 . . . n), k, 0) = n k + 1 n k-1 .
It is understood that this number is zero if k ≥ n.

Proof -We count the increasing paths of length k in N C(n) starting at {{1}, . . . , {n}} by first regrouping them according to their terminal point. The possible terminal points of these paths are exactly the non-crossing partitions of (1 . . . n) into n -k classes. Such partitions may be classified according to the number of singletons they contain, the number of pairs, and so on. Let s 1 , . . . , s n be non-negative integers such that s 1 +. . .+s n = n-k and s 1 +2s 2 +. . .+ns n = n. We say that a partition is of type (s 1 , . . . , s n ) if it contains exactly s i classes of cardinal i for each i ∈ {1, . . . , n}. The number of non-crossing partitions of type (s 1 , . . . , s n ) has been computed by Kreweras [START_REF] Kreweras | Sur les partitions non croisées d'un cycle[END_REF]. It is equal to n! (k + 1)!s 1 ! . . . s n ! .

Let P be a non-crossing partition of type (s 1 , . . . , s n ). An increasing path from {{1}, . . . , {n}} to P looked at in the reverse direction is a decreasing path from P to {{1}, . . . , {n}}. There are as many such paths as there are geodesic paths from the permutation σ P induced by P to the identity, that is, S(σ P , k, 0). Let us apply Lemma 6.3 to compute this number. The only non-zero term in the sum corresponds to the situation where l i = |c i | for each i ∈ {1, . . . , ℓ(σ P )}. Since S(c, |c|, 0) = m m-2 for every cycle c of size m, we find the formula

S((1 . . . n), k, 0) = (s 1 ,...,sn) n! (k + 1)!s 1 ! . . . s n ! k! 1! s 2 . . . (n -1)! sn 2 0s 2 3 1s 3 . . . n (n-2)sn ,
where the sum is extended to all possible types of partitions of {1, . . . , n} into n -k classes. Let us enumerate the possible types by enumerating the partitions themselves. If we do this, each type will appear as many times as the number of partitions of this specific type. The number of partitions of type (s

1 , . . . , s n ) is n! 1! s 1 s 1 ! . . . n! sn s n ! .
Hence, we find the following expression:

S((1 . . . n), k, 0) = 1 k + 1 P 1 (1-1)s 1 2 (2-1)s 2 . . . n (n-1)sn ,
where the sum runs over all partitions of {1, . . . , n} into n -k classes. Now the right hand side has been computed by Kreweras in [START_REF] Kreweras | Une famille d'identités mettant en jeu toutes les partitions d'un ensemble fini de variables en un nombre donné de classes[END_REF] and it is equal to

S((1 . . . n), k, 0) = 1 k + 1 n -1 n -k -1 n k = n k + 1 n k-1 .
This is the expected result.

Let us state separately the following result which has been used in the course of this proof.

Lemma 6.7. Let P ∈ N C(n) be a partition of type (s 1 , . . . , s n ). There are exactly

(s 2 + . . . + (n -1)s n )! 1! s 2 . . . (n -1)! sn 2 0s 2 . . . n (n-2)sn
increasing paths from 0 n to P .

Remark 6.8. The explicit expression of the large N limit of the moments of B t N obtained in this section has been stated by Singer in [START_REF] Singer | On the master field in two dimensions[END_REF] and proved by Biane in [START_REF] Biane | Free Brownian motion, free stochastic calculus and random matrices[END_REF].

The asymptotic distribution of B t N as N tends to infinity is the unique probability measure µ t on the group U of complex numbers of modulus 1 such that, for all n ∈ N, U z n µ(dz)

= U z -n µ t (dz) = e -nt 2 n-1 k=0 (-nt) k nk! n k+1
. This expression of the moments of µ t is not very easy to handle, if only numerically, because it is an alternated sum of large numbers. Let us point out two analytical ways of studying µ t .

The S-transform of µ t is its moment generating function, defined by

S t (z) = U ξz 1-ξz dµ t (ξ) = ∞ n=1 m n,t z n
, where m n,t is the n-th moment of µ t . Since |m n,t | ≤ 1 for all n and t, the function S t is holomorphic on the unit disk D = {z : |z| < 1}. Moreover, since S t (z) = z + O(z 2 ), there exist a reciprocal function to S t in a neighbourhood of 0, which we denote by χ t . It turns out that χ t is much simpler than S t : χ t (z) = z z+1 e t(z+ 1 2 ) , as one can easily check by using Lagrange's inversion formula. To put it more concisely, the measure µ t is fully characterized by the following relation, valid for z in a neighbourhood of 0: By studying χ t , Biane proved in [START_REF] Biane | Segal-Bargmann transform, functional calculus on matrix spaces and the theory of semi-circular and circular systems[END_REF] the following facts. For each t > 0, the measure µ t has a continuous density with respect to the uniform measure on U. For t ∈ (0, 4], this density is zero exactly on the set

e iθ : |θ -π| ≤ 2 arctan 4 -t t - 1 2 t(4 -t) .
For t > 4, the density of µ t is positive. Finally, for all t > 0, the density of µ t at e iθ is a real analytic function of θ on the relative interior of its support.

Another way of studying µ t is to observe that m n,t = e -nt 2 2inπ e -ntz 1 + 1 z n dz, the integral being along any contour of index 1 with respect to 0. In [START_REF] Gross | Some properties of large-N two-dimensional Yang-Mills theory[END_REF], Gross and Matytsin use this expression and the saddle point method to exhibit the following phase transition with respect to t: if t ∈ (0, 4), m n,t decays with n like n -3 2 , whereas for t ∈ (4, +∞), it decays exponentially. Along the same lines, one can check that for t = 4, m n,4 decays like n -4 3 . This indicates that the density of µ 4 is less regular than the density of µ t for t ∈ (0, 4). This behaviour is consistent at a heuristical level with a general result of Biane about additive convolution with the semi-circle law [START_REF] Biane | On the free convolution with a semi-circular distribution[END_REF].

Let us use the notation k n = k (1...n) . It is an elementary property of the free cumulants that they are multiplicative, in that k σ = k m 1 . . . k m ℓ(σ) when (m 1 , . . . , m ℓ(σ) ) are the cycle lengths of σ.

Proposition 7.2. The free cumulants of u t are given by

(46) k n (u t ) = e -nt 2 (-nt) n-1 n(n -1)! . More generally, if σ ∈ S n , then (
47) k σ (u t ) = e -nt 2 (-t) |σ| |σ|! #Π |σ| (id → σ).
Proof -Let us put ϕ(u n t ) under the form of the right hand side of (45). Applying Theorem 3.3, using Kreweras complementation and using Lemma 6.7, we find

ϕ(u n t ) = e -nt 2 σ (1...n) (-t) |σ(1...n) -1 | |σ(1 . . . n) -1 |! #Π |σ(1...n) -1 | ((1 . . . n) → σ) = e -nt 2 σ (1...n) (-t) |σ| |σ|! #Π |σ| (id → σ) = σ (1...n) (e -1t 2 (-t) 0 1 -1 ) s 1 (e -2t 2 (-t) 1 2 0 ) s 2 . . . (e -nt 2 (-t) n-1 n n-2 ) sn 0! s 1 1! s 2 . . . (n -1)! sn ,
where s 1 , . . . , s n are respectively the number of fixed points of σ, and the numbers of transpositions, 3-cycles, . . ., n-cycles in the decomposition of σ. By comparing this expression with (45), we find the desired expression for the cumulants of u t .

Let us recall briefly Speicher's characterization of freeness by the vanishing of mixed free cumulants [START_REF] Speicher | Free probability theory and non-crossing partitions[END_REF]. Let a 1 , . . . , a n be non-commutative random variables on a space (A, ϕ), where ϕ is a tracial state. For σ ∈ S n , the number m σ (a 1 , . . . , a n ) is defined by

m σ (a 1 , . . . , a n ) = c cycle of σ c=(i 1 ...ir) ϕ(a i 1 . . . a ir ).
It is well defined thanks to the fact that ϕ is tracial. The numbers m σ (a 1 , . . . , a n ) are the mixed moments of a 1 , . . . , a n . The relation

m σ (a 1 , . . . , a n ) = σ ′ σ k σ ′ (a 1 , . . . , a n )
characterizes the family of numbers k σ (a 1 , . . . , a n ), the mixed free cumulants of a 1 , . . . , a n .

Speicher's characterization of freeness is the following. Let (a k ) k≥1 be a family of elements of A. Then this family is free if and only if, for all n ≥ 2 and all i 1 , . . . , i n ≥ 1 such that i r = i s for some r, s ∈ {1, . . . , n}, k (1...n) (a i 1 , . . . , a in ) = 0. Theorem 7.3. Let (B (N,k) ) N,k≥1 be a family of Brownian motions, such that, for all N, k ≥ 1, B (N,k) is a Brownian motion on U (N ) and, for all N ≥ 1, the Brownian motions (B (N,k) ) k≥1 are independent. Let (t k ) k≥1 be a sequence of non-negative real numbers. ).

This is exactly what we expected.

Large N Yang-Mills theory on a disk and branching covers

In this section, we explain how our main expansion relates the Brownian motion on the unitary group to a natural model of random branching covers on this disk. In doing this, we give a rigorous proof of results which are stated in [START_REF] Gross | Twists and Wilson loops in the string theory of two dimensional QCD[END_REF].

Let D be the closed disk of radius 1 centred at the origin O of R 2 . Let n ≥ 1 be an integer. Let λ be a partition of n. We define the set R n,λ as the set of isomorphism classes of ramified coverings π : R -→ D which satisfy the following properties. 1. R is a ramified covering of degree n. 2. For each ramification point x ∈ D of R which is not the origin O, R has a generic ramification type at x, in that #π -1 (x) = n -1. 3. The monodromy of R along the boundary of D belongs to the conjugacy class of S n corresponding to λ. An element of R n,λ is allowed to be ramified over O, with any kind of ramification. The set of its ramification points distinct from O is called its locus of generic ramification. It is contained in the interior of D -{0}, which we denote by D * .

Let X be a finite subset of D * . We define R n,λ,X as the subset of R n,λ formed by the coverings whose locus of generic ramification is X.

The set R n,λ,X is in natural one-to-one correspondence with a set of equivalence classes of paths in the Cayley graph of S n as follows. Assume that X = {x 1 , . . . , x k }. Choose a point b on the boundary of D. By the interior of a simple closed continuous curve based at b, we mean the bounded connected component of the complement of its range. Let C, C 1 , . . . , C k be simple closed curves in D based at b with pairwise disjoint interiors such that the interior of C contains O and, for each i ∈ {1, . . . , k}, the interior of C i contains x i . We assume that this is done in such a way that the curve CC k . . . C 1 is homotopic to the boundary of D in D -(X ∪ {O}). Then the monodromies σ O , τ 1 , . . . , τ k of an element R ∈ R n,λ,X along the curves C, C 1 , . . . , C k are defined in S n up to simultaneous conjugation and their orbit characterizes R. The assumptions made on R imply that τ 1 , . . . , τ k are transpositions and σ O τ 1 . . . τ k belongs to λ.

Let P n,λ,k be the set of paths in the Cayley graph of S n which start at an element of the conjugacy class determined by λ. The symmetric group acts on P n,λ,k by conjugation. The mapping from R n,λ,X which associates to R the orbit of the path (σ O τ k . . . τ 1 , σ O τ k . . . τ 2 , . . . , σ O τ k , σ O ) is a bijection. Moreover, the cardinal of the stabilizer of this orbit is equal to the cardinal of the automorphism group Aut(R) of R. Hence, the image on R n,λ,X of the counting measure on P n,λ,k by the mapping P n,λ,k -→ P n,λ,k /S n ≃ R n,λ,X is the measure

ρ n,λ,X = R∈R n,λ (X) n! #Aut(R) δ R .
This measure is finite and satisfies ρ n,λ,X (1) = n 2 k .

There is a natural topology on R n,λ , which is generated by the sets

O(R, U ) = {R ′ ∈ R n,λ : R |D-U ≃ R ′ |D-U },
where R spans R n,λ and U the set of neighbourhoods of the locus of generic ramification of R. This is a fairly coarse topology: for example, the cardinal of the locus of generic ramification is not continuous, but only lower semi-continuous in this topology. However, the ramification type at O is continuous. On the set X of finite subsets of D * , we put the topology which makes the bijection X ≃ n≥0 ((D * ) n -∆ n )/S n a homeomorphism, where ∆ n is the subset of (D * ) n where at least two components coincide. These topologies do not make the ramification locus a continuous function of the ramified covering. Nevertheless, let M(R n,λ ) denote the space of finite Borel measures on R n,λ endowed with the topology of weak convergence.

Lemma 8.1. The mapping X -→ M(R n,λ ) which sends X to ρ n,λ,X is continuous.

Proof -By definition of the topology on X , it suffices to prove that the mapping is continuous on (D * ) k -∆ k for all k ≥ 0. Consider k ≥ 0, X = {x 1 , . . . , x k } and a bounded continuous function f : R n,λ,X -→ R. Choose ε > 0. Since R n,λ,X is finite, the continuity of f implies the existence of r > 0 such that the balls B(x i , r) are contained in D * , pairwise disjoint for i ∈ {1, . . . , k} and the neighbourhood U = B(x 1 , r) × . . . × B(x k , r) of X in (D * ) k -∆ k satisfies

∀R ∈ R n,λ,X , ∀R ′ ∈ O(R, U ), |f (R ′ ) -f (R)| < ε n 2 -k
.

Let X ′ = {x ′ 1 , . . . , x ′ k } be an element of U . Let φ be a homeomorphism of D such that φ |D-U = id D-U and φ(x i ) = x ′ i for all i ∈ {1, . . . , k}. For each ramified covering π : R -→ D belonging to R n,λ,X , the covering Φ(R) = (φ • π : R -→ D) belongs to R n,λ,X ′ . Replacing φ by its inverse in the definition of Φ : R n,λ,X -→ R n,λ,X ′ yields the inverse mapping, hence Φ is a bijection. Moreover, the conjugation by φ determines an isomorphism between Aut(R) and Aut(Φ(R)). Finally, R and Φ(R) are isomorphic outside U . Altogether, ρ n,λ,X ′ (f ) -ρ n,λ,X (f )

≤ R∈R n,λ,X n! #Aut(R) |f (Φ(R)) -f (R)| < ε.
Since k, X, f and ε were arbitrary, the result follows.

Let t ≥ 0 be a real number. Let Ξ t be the distribution of a Poisson point process on D of intensity t π times the Lebesgue measure on D. Under Ξ t , a random subset of D is contained in D * with probability 1 and the average number of points of such a random set is t. Thinking of Ξ t as a Borel probability measure on X , we define a measure on R n,λ by setting ρ t n,λ = X ρ n,λ,X Ξ t (dX).

The measure ρ t n,λ is finite and satisfies ρ t n,λ (1) = e t( n 2 )-t . We define a probability measure µ t n,λ on R n,λ by normalizing ρ t n,λ . Let us define two functions on R n,λ . Firstly, given R ∈ R n,λ , let us define k(R) as the number of ramification points of R distinct from O. We have observed that this is a lower semi-continuous, hence measurable function of R. Secondly, let χ(R) be the Euler characteristic of R. Lemma 8.2. Let X be a subset of cardinal k of D * . Let R be an element of R n,λ,X and γ = (σ 0 , . . . , σ k ) a representative of the associated orbit of P n,λ,k . Then

χ(R) = ℓ(σ k ) -k = ℓ(λ) -2d(γ).
In particular, χ : R n,λ -→ Z is upper semi-continuous and measurable.

1 2 ∆

 2 U (N ) . Consider the function p : S n × U (N ) → C defined by p(σ, U ) = p st σ (M 1 U, . . . , M n U ). By Proposition 2.3, this function satisfies the relation

Figure 1 .

 1 Figure 1. Multiplication of two diagrams in the Brauer monoid.

Figure 2 .

 2 Figure 2. The elements 24 and (24) of B 6 .

id 6 / 4 e 2 y y s s s s s s s s s ( 12 Figure 3 .

 642123 Figure 3. The Cayley graph of S 4 modulo conjugation.

Lemma 4 . 3 .

 43 Define Ω ∈ C[S n ] by Ω = σ∈Sn N ℓ(σ) σ. Then the following relations hold.

Proof-

  Instead of computing S((1 . . . n), k, d) we compute the sum of S(σ, k, d) when σ spans the set of all n-cycles. Dividing the result by (n -1)! yields S((1 . . . n), k, d). Now, a path of length k starting at an n-cycle has defect d if and only if it ends at a distance n -1 -k + 2d from the identity. Let us recall some of the notation used in the proof of Lemma 4.3. The integer n being fixed, we set Σ r = |σ|=r σ. Hence, S((1 . .

Lemma 6 . 4 .

 64 The mapping from N C(n) to S n which sends a partition P to the permutation σ P is an isomorphism of posets from N C(n) onto [id, (1 . . . n)] = {σ ∈ S n : σ (1 . . . n)}.

Figure 4 .

 4 Figure 4. The Kreweras complement of {{1, 3, 12}, {2}, {4, 8, 9}, {5, 6, 7}, {10, 11}} is {{1, 2}, {3, 9, 11}, {4, 7}, {5}, {6}, {8}, {10}, {12}}.

  such cumulants appear that remain non-crossing when they are merged with σ. In symbols, ..n) ∀k∈{1,...,n}, i k =i σ(k)

6.3. Almost sure convergence. The material gathered so far allows us to prove very easily the following result. Proposition 6.9. Consider σ ∈ S n . Then, uniformly in t on bounded intervals,

In particular, on any probability space on which a Brownian motion on U (N ) is defined for N large enough, the following convergence holds almost surely and in L 2 :

Proof -Let us denote by σ × σ the element of S 2n which sends i on σ(i) and n + i on n + σ(i) for each i ∈ {1, . . . , n}. With this notation, p 2 σ = p σ×σ , so that

where the last expression follows after simplification from Theorem 3.3. In the term corresponding to d = 0, both d 1 and d 2 must be equal to 0. By the same argument of support as in the proof of Proposition 6.3, we find

The result follows immediately.

Asymptotic freeness

In this section, we prove that independent Brownian motions on U (N ) converge in distribution, as N tends to infinity, towards free non-commutative random variables. We do not consider * -freeness, that is, we do not consider products involving B -1 t N . In fact, the asymptotic * -freeness of independent Brownian motions follows from a general result of Voiculescu (see [START_REF] Voiculescu | Free random variables[END_REF] and [START_REF] Biane | Free Brownian motion, free stochastic calculus and random matrices[END_REF]Lemma 6] for details). Here we use Speicher's characterization of freeness by the vanishing of mixed free cumulants. This combinatorial characterization is very well suited to the approach we have adopted in this paper. Assume that this sequence converges in distribution. Consider σ ∈ S n . Write σ as a product of cycles : σ = (i 1,1 . . . i 1,m 1 ) . . . (i ℓ(σ),1 . . . i ℓ(σ),m ℓ(σ) ). Then (39) lim

More precisely,

uniformly in t on bounded intervals. It is understood that all limits exist.

Proof -According to Theorem 3.3, the left hand side of (39) is equal to

This last limit exists for all σ ′ by the assumption that the family (M

Hence, only permutations σ ′ such that σ ′ σ contribute and (41) can be rewritten as

Let c 1 , . . . , c ℓ(σ) denote the cycles of σ. It is not difficult to check that the interval [id, σ] in the poset S n is isomorphic to the product of intervals

Hence, (42) can be written as ( 43)

ir,m r ), and this is just the right-hand side of (39). The equation (40) follows from (39) just as in Proposition 6.2.

7.2. Free cumulants. As a preliminary to the proof of the asymptotic freeness, we compute the free cumulants of the limiting distribution of B t N . Let (A, ϕ) be a non-commutative probability space and u t an element of A such that B t N converges in distribution to u t as N tends to infinity. We have spent a substantial part of this paper proving that the moments of u t are given by ( 44)

Given a ∈ A and σ ∈ S n with cycle lengths (m 1 , . . . , m ℓ(σ) ), let us use the notation ϕ σ (a) = ϕ(a m 1 ) . . . ϕ(a m ℓ(σ) ). The free cumulants of u t form a family of complex numbers (k π (u t )) π∈ n≥1 Sn and they are characterized by the identity

Then, as N tends to infinity, the family of non-commutative random variables (B

converges in distribution towards a free family (b (k) ) k≥1 of non-commutative random variables such that, for all k ≥ 1, b (k) has the distribution of u t k .

Proof -We prove the result for finite families (B (N,k) ) N ≥1,k∈{1,...,K} for some finite K, by induction on K. The case K = 1 is settled by our computation of the asymptotic distribution of

, that is, Propositions 6.1 and 6.6.

Let K ≥ 2 be an integer and let us assume that the property is proved for K -1 independent Brownian motions. We need to prove that the mixed free cumulants of B What we need to prove is that, for all n ≥ 2, all σ ∈ S n , all i 1 , . . . , i n ∈ {1, . . . , K} not all equal, lim

By the factorization property (39) and Fubini's theorem, the left hand side is multiplicative with respect to the cycle decomposition of σ. The right hand side is also clearly multiplicative, hence, it suffices to consider the case where σ = (1 . . . n). In this case, we are looking at the expected trace of a product B (N,i 1 )

where at least two factors are distinct. Of course, the case where one of the K possible factors does not appear is treated by the induction hypothesis. Let us assume that the K factors appear, in particular B (N,1) . Up to cyclic permutation, which does not affect its trace, the product above can be put under the form

, for some r ≥ 1 and some products W (N ) 1 , . . . , W (N ) r of factors among B (N,2) , . . . , B (N,K) . Our previous results show that lim

where we have changed σ in K(σ) = σ -1 (1 . . . r) between the first and the second line.

The term lim N →∞ m K(σ) (W

) is equal to a sum of limits of free cumulants of the factors appearing in W (N ) 1

, . . . , W

(N ) r in this order. By induction, only pure free cumulants appear, those which do not involve more than one Brownian motion in each cycle of the permutation. Moreover, by the combinatorial description of K(σ) as a non-crossing partition, only Proof -The first equality follows from the Riemann-Hurwitz formula, the second from the definition of the defect of a path. The last assertion follows from the lower semi-continuity of k and the fact that ℓ(σ k ), which depends only on the ramification type at O, is a continuous function of R.

The main result is the following. Theorem 8.3. Let N, n ≥ 1 be two integers. Let (B t ) t≥0 be the Brownian motion on U (N ) defined in Theorem 3.3. Let λ be a partition of n and σ an element of S n which belongs to the conjugacy class determined by λ. Let t ≥ 0 be a real number. Then

We could have avoided the unpleasant exponential factor in the statement of this theorem if we had considered the signed measure ρt n,λ = X (-1) #X ρ n,λ,X Ξ t (dX) instead of ρ n,λ .

Proof -Let X be a finite subset of D * . The set R n,λ,X is in bijection with the set of orbits of Π k (σ) under the action of S n by conjugation. Let R be an element of R n,λ,X and γ = (σ, σ 1 , . . . , σ k ) a representative of the corresponding orbit. By Lemma 8.2, R n,λ (-1) k(R) N χ(R) ρ n,λ,X (dR) = γ∈Π k (σ)

(-1) k(X) N ℓ(λ)-2d(γ)

= N ℓ(λ) d≥0 (-1) k(X) N 2d S(σ, k(X), d).

Integrating with respect to Ξ t (dX), we find ) . The result follows after normalizing ρ t n,λ .