Thomas Buc-D'alché

Topological expansion of unitary integrals and maps

Topological expansion of unitary integrals and maps

Introduction

In the breakthrough article [START_REF] Brézin | Planar diagrams[END_REF], Brézin and al. used random matrix theory to address the problem of enumeration of maps, graphs embedded in surfaces up to homeomorphisms. The topological properties of Feynman diagrams had previously been shown to be critical in the work of 't Hooft [START_REF] Hooft | A planar diagram theory for strong interactions[END_REF], thus relating the combinatorics of maps to field theory (see also the review article [START_REF] Bessis | Quantum field theory techniques in graphical enumeration[END_REF]). For instance, the planar diagrams give the leading order in the expansion of physically significant quantities.

The random matrix approach to the enumeration of maps pioneered by Brézin and al. subsequently found many applications. Harer and Zagier used the same approach to study the topological properties of the moduli space of curves [START_REF] Harer | The Euler characteristic of the moduli space of curves[END_REF]. In the celebrated article [START_REF] Kontsevich | Intersection theory on the moduli space of curves and the matrix Airy function[END_REF], Kontsevitch used matrix integrals to solve Witten's conjecture. See also [START_REF] Di Francesco | 2D Gravity and Random Matrices[END_REF] for a review of the application of random matrix theory to combinatorial problems appearing in 2D gravity. More generally, random matrices provide a powerful tool to address hard combinatorial problems such as the problem of the enumeration of Riemann surfaces, see the work of Eynard [START_REF] Eynard | Counting Surfaces[END_REF]. For another approach on the enumeration of maps, see for instance [START_REF] Bouttier | Census of Planar Maps: From the One-Matrix Model Solution to a Combinatorial Proof[END_REF].

In all the problems above, the matrix models used are related to the Gaussian Unitary Ensemble (GUE). Let dM = i dM ii i<j d Re(M ij )d Im(M ij ) be the Lebesgue measure on the space of Hermitian matrices H N and V be a polynomial called the potential. We consider the measure

µ N GUE,V = 1 Z N GUE,V e -N Tr V (M )-N 2 Tr M 2 dM,
where the normalization constant is the partition function

Z N GUE,V = H N e -N Tr V (M )-N 2 Tr M 2
dM. * UMPA UMR 5669, ENS de Lyon, CNRS; 46, allée d'Italie 69007, Lyon, France; email:thomas.buc-dalche@enslyon.fr 1 Many relevant quantities, such as the partition function can be expressed as a formal series of maps using Wick's formula (see [START_REF] Zvonkin | Matrix integrals and map enumeration: An accessible introduction[END_REF] for an introduction). For instance for V (M ) = tM 4 , we get

ln Z N GUE,tM 4 = g≥0 N 2-2g n≥0 (-t) n n! M (g) GUE,n (x 4 ) ,
where M (g) GUE,n (x 4 ) is the number of connected maps of genus g with n vertices, all of them of degree 4. Notice that the term of order N 2-2g in this expansion is a generating series of maps of genus g. We call such an expansion a (formal) topological expansion.

In general, the above equality holds in the sense of formal power series, see [START_REF] Eynard | Formal Matrix Integrals and Combinatorics of Maps[END_REF] for instance. By the above equality, we mean that the derivatives with respect to t at t = 0 of the left and right sides of the equation above coincide. In fact, the series of maps on the right side may not converge in general.

We can replace this divergent series with an asymptotic expansion as N → ∞, where the equality holds up to an error of order N -p , for some integer p. Ercolani and McLaughlin obtained such an expansion in a one-matrix model, for a potential whose coefficients are close to zero [START_REF] Ercolani | Asymptotics of the partition function for random matrices via Riemann-Hilbert techniques, and applications to graphical enumeration[END_REF]. The case with several random matrices was studied by Guionnet and Maurel-Segala [START_REF] Guionnet | Combinatorial aspects of matrix models[END_REF][START_REF] Guionnet | Second order asymptotics for matrix models[END_REF], and Maurel-Segala [START_REF] Maurel-Segala | High order expansion of matrix models and enumeration of maps[END_REF]. More complicated models involving not only a matrix from the GUE but also deterministic matrices, sometimes called models with external sources, have been studied, see [START_REF] Brézin | Random Matrix Theory with an External Source[END_REF].

The multi-matrix models display much more variety. As for the one-matrix models, they were first studied by physicists, see the reviews [START_REF] Gross | Two Dimensional Quantum Gravity And Random Surfaces -8th Jerusalem Winter School For Theoretical Physics[END_REF][START_REF] Di Francesco | 2D Gravity and Random Matrices[END_REF]. From an analytical point of view, they are harder to solve than one-matrix models, see for instance the works of Mehta [START_REF] Mehta | A method of integration over matrix variables[END_REF], and from a combinatorial point of view, they allow to address a wealth of combinatorial problems as they are related to the enumeration of colored maps, see for instance [START_REF] Guionnet | Combinatorial aspects of matrix models[END_REF].

In this article, we establish a similar link between integrals of unitary matrices and the combinatorics of some maps. More precisely, we introduce new maps, the maps of unitary type, that describe the topological expansion. These maps allow us to relate the Weingarten calculus and the Dyson-Schwinger equation -two important ways to study unitary integrals. In a particular case, the maps of unitary type are related to the Hurwitz numbers. In this way, we generalize part of the results obtained in [START_REF] Goulden | Monotone Hurwitz numbers and the HCIZ integral II[END_REF], that relate a particular integral, the HCIZ integral, to Hurwitz numbers.

We introduce some notation. We consider matrices of dimension N ∈ N * = {1, 2, 3, . . .}. We denote by Tr A = N i=1 A ii the trace of a matrix A. Notice that Tr depends on the dimension N . The conjugate transpose of a matrix M is denoted by M * . Let p ∈ N * . For all N ≥ 1, we fix p deterministic matrices A N 1 , . . . , A N p of size N × N . The matrix U N will be a unitary matrix of size N × N , i.e. an element of the unitary group U(N ), and (U N ) * = (U N ) -1 will be its conjugate transpose.

Let dU N be the Haar measure on the unitary group U(N ), and V be a non-commutative polynomial in several variables. The measure µ N V is given by

dµ N V (U N ) = 1 Z N V exp N Tr V U N , (U N ) * , A N 1 , (A N 1 ) * , . . . , A N p , (A N p ) * dU N , (1)
where the partition function Z N V is

Z N V = U(N )
exp N Tr V U N , (U N ) * , A N 1 , (A N 1 ) * , . . . , A N p , (A N p ) * dU N .

(2)

1 Z N V exp(N Tr V )dU N 1 • • • dU N n ,
where V is a noncommutative polynomial that depends on U N 1 , . . . , U N n , all independent and Haardistributed.

We will assume the two following hypotheses.

Hypothesis 1.1. For all N ≥ 1 and for all U 1 , . . . , U n ∈ U(N ) n , Tr V is real.

Hypothesis 1.2. For all N ≥ 1 and for all 1 ≤ i ≤ p, A N i ≤ 1, where • is the operator norm.

Hypothesis 1.1 implies that the measure µ N V is a probability measure, and in particular that Z N V ∈ (0, +∞).

We write the potential V as a sum of monomials q i with complex coefficients z i , V = i z i q i . Thus, we will sometimes consider the partition functions, cumulants, etc. as functions of z = (z 1 , z 2 , . . .). Notice that for generic q i 's, Tr V might be real for only specific values of z.

Notice that when considering the partition function with potential V = tAU N B(U N ) * , where t ∈ C and A, B are self-adjoint matrices, we recover the Harish-Chandra-Itzykson-Zuber (HCIZ) integral

Z N V = U(N )
exp tN Tr AU N B(U N ) * dU N , which was first studied by Harish-Chandra [START_REF] Harish-Chandra | Differential Operators on a Semisimple Lie Algebra[END_REF] and Itzykson and Zuber [START_REF] Itzykson | The planar approximation[END_REF], and whose asymptotics have been since investigated, see [ZJZ03, GGPN14, GN15, Nov20]. We will compute joint moments and cumulants (see Definition 2.1) of the random variables Tr(P 1 ), . . . , Tr(P l ) under µ N V (for V small), where the P i are non-commutative polynomials. In [START_REF] Collins | Asymptotics of unitary and othogonal matrix integrals[END_REF], the first-order asymptotics of partition functions was studied. In [START_REF] Guionnet | Asymptotics of unitary multimatrix models: The Schwinger-Dyson lattice and topological recursion[END_REF], it has been shown that the joint cumulants admit an asymptotic expansion as N → ∞, when the coefficients of the potential V are small enough.

The goal of this article is to give a combinatorial interpretation of the coefficients of this expansion. We show that unitary matrix integrals enumerate a particular family of maps, which we call maps of unitary type. They are introduced in Section 3.2. This interpretation links the Dyson-Schwinger equation, which is satisfied by sums of maps of unitary type, and the Weingarten calculus studied first by Weingarten [START_REF] Weingarten | Asymptotic behavior of group integrals in the limit of infinite rank[END_REF], and then by [START_REF] Samuel | U(N) Integrals, 1/N, and the De Wit-'t Hooft anomalies[END_REF], whose results were rediscovered and expanded upon by Collins [START_REF] Collins | Moments and cumulants of polynomial random variables on unitarygroups, the Itzykson-Zuber integral, and free probability[END_REF] and Collins and Śniady [START_REF] Collins | Integration with respect to the Haar measure on unitary, orthogonal and symplectic group[END_REF]. See [START_REF] Collins | The Weingarten Calculus[END_REF] for a review.

Expansions in terms of combinatorial objects have already been introduced for unitary matrices. For instance, in the case of the HCIZ integral, expansions for the free energy using double Hurwitz numbers are computed in [START_REF] Goulden | Monotone Hurwitz numbers and the HCIZ integral II[END_REF]. In [START_REF] Collins | Asymptotics of unitary and othogonal matrix integrals[END_REF], the leading order of the expansion of unitary integrals is expressed in terms of maps with "dotted edges". However, to our knowledge, no interpretation of these expansions using maps has been obtained at all orders for the unitary integrals we consider. As an interesting particular case, when considering alternated polynomials (see Definition 3.39), the combinatorics of maps of unitary type is related to triple Hurwitz numbers.

In the case of the GUE, integrals of random matrices and enumeration of maps are related by the Wick formula. In the case of unitary matrices, the Wick formula is replaced by Weingarten's formula.

In Section 2, we express joint moments of random variables Tr(P i ), for non-commutative polynomials P i , using the Weingarten formula. In the case where the potential V = 0, we can express such moments as weighted sums of permutations. In Section 3, we recall a few notions on maps and introduce the maps of unitary type, which are our main combinatorial tools. This allows us to deduce a topological expansion for the joint cumulants in the case of no potential (i.e. V = 0). To address the general case V = 0, we introduce generating series of maps of unitary type of the form

M (g),N V,l (P 1 , . . . , P l ) = n∈N k z n n! × w N (C, n, V, P 1 , . . . , P l ),
where the second sum is on a set of connected maps of unitary type C of genus g which depends on V, P 1 , . . . , P l , n. The term w N (C, n, V, P 1 , . . . , P l ) is a weight which depends on the size N , C, n and on the polynomials V, P 1 , . . . , P l . See Definition 3.38.

In Section 4, we describe a decomposition of maps of unitary type, which can be interpreted as a cutting procedure. It allows us to deduce induction relations -similar to the topological recursion of Eynard and Orantin, see [START_REF] Eynard | Algebraic methods in random matrices and enumerative geometry[END_REF] -on weighted sums M (g),N V,l of maps of unitary type of a given genus g. This decomposition is reminiscent of a procedure introduced by Tutte [START_REF] Tutte | On the enumeration of planar maps[END_REF]. In Section 5, we extend the results obtained so far to the case of integrals over several independent random unitary matrices U N 1 , . . . , U N n . It turns out that the induction relations obtained in Section 4 are related to the Dyson-Schwinger lattice. The Dyson-Schwinger lattice (see [START_REF] Guionnet | Asymptotics of unitary multimatrix models: The Schwinger-Dyson lattice and topological recursion[END_REF]) is a family of equations relating cumulants together, which generalize the Dyson-Schwinger equation (see Equation ( 25)). This equation admits under some hypotheses a unique solution [START_REF] Collins | Asymptotics of unitary and othogonal matrix integrals[END_REF]. Furthermore, in [START_REF] Guionnet | Asymptotics of unitary multimatrix models: The Schwinger-Dyson lattice and topological recursion[END_REF], the Dyson-Schwinger lattice has been used to establish the existence of an asymptotic expansion of the cumulants, when N → ∞. Let us assume Hypotheses 1.1 and 1.2, and that the joint law of the matrices A N i , tr admits an asymptotic expansion as N → ∞. For all h, we have an asympotic expansion for the renormalized joint cumulants N l-2 W N V,l (P 1 , . . . , P l ) (introduced in Definition 2.3) when the coefficients of the potential V are small enough

N l-2 W N V,l (P 1 , . . . , P l ) = h g=0 τ V l,g (P 1 , . . . , P l ) N 2g + o(N -2h ), (3)
where the coefficients τ V l,g (P 1 , . . . , P l ) are uniquely defined by some induction relations. In Section 6, we use the same techniques to express the terms of this expansion in terms of maps of unitary type. We thus obtain a topological expansion: the coefficient of 1 N 2g in the expansion is a generating series of weighted unitary type maps of genus g.

We thus improve on the result of [GN15, Theorem 25] by relaxing the hypotheses, showing that the convergence is uniform in g and l, and by giving a combinatorial interpretation to the coefficients τ V l,g (P 1 , . . . , P l ). Theorem 1.3 (Main theorem). Assume that for all N ≥ 1, Tr(V ) is real for all U 1 , . . . , U n ∈ U(N ) n and that

A N i ≤ 1 for all 1 ≤ i ≤ p. There exists > 0 such that if z ∞ < ,
then for all l ≥ 1, g ≥ 0, and P = (P 1 , . . . , P l ), we have the asymptotic expansion as N → ∞

N l-2 W N V,l (P 1 , . . . , P l ) = g h=0 1 N 2h M (h),N V,l (P 1 , . . . , P l ) + O N -2g-2 .
Notice that we do not require the trace Tr to have an asymptotic expansion as in [START_REF] Guionnet | Asymptotics of unitary multimatrix models: The Schwinger-Dyson lattice and topological recursion[END_REF]Theorem 25].

An interesting particular case described in Section 3.6 is when all the polynomial involved are alternated, see Definition 3.39, that is if they can be written as

P = B N 1 U N C N 1 (U N ) * • • • B N m U N C N m (U N ) * ,
where B N i and C N i for i = 1, . . . , m are square N × N matrices. This is the case of the HCIZ integral in particular.

In that case, our sums of maps are related to the triple Hurwitz numbers, which count ramified coverings of the sphere with at most three nonsimple ramification points. We thus generalize the link between the (double) Hurwitz numbers and the HCIZ integral, which had already been studied in [START_REF] Goulden | Monotone Hurwitz Numbers and the HCIZ Integral[END_REF]. See also [START_REF] Collins | The tensor Harish-Chandra-Itzykson-Zuber integral I: Weingarten calculus and a generalization of monotone Hurwitz numbers[END_REF] for a study of the HCIZ integral in the tensor setting.

In Section 2, we give definitions and recall important consequences of the Weingarten calculus. In Section 3, we introduce the maps of unitary types and show that they describe the topological expansion of cumulants with respect to the Haar mesure. When the polynomial are alternated, these maps are related to the triple Hurwitz numbers. In Section 4, we give a decomposition of maps of unitary type and deduce induction relations on sums of maps of a given genus and with prescribed vertices, in the spirit of the work of Tutte [START_REF] Tutte | On the enumeration of planar maps[END_REF]. In Section 6, we study the Dyson-Schwinger equation and give the proof of the main result.

Acknowledgement. I thank my PhD advisors, Alice Guionnet and Grégory Miermont for countless tips and advice during this project. This project was supported by ERC Project LDRAM : ERC-2019-ADG Project 884584.

Weingarten calculus

In this section, we first give a few definitions and introduce notation pertaining to moments and cumulants of traces of random matrices. Then, we give a short review of the Weingarten calculus. This allows us to give expression for the expectation of a product of traces of monomials in the matrices U N , (U N ) * , A N i , (A * ) N .

Moments and cumulants

Let us consider l ≥ 1 non-commutative polynomials P 1 , P 2 , . . . , P l in the variables u, u -1 , and a i , a * i for 1 ≤ i ≤ p, with p ∈ N. We define the involution * such that u * = u -1 , for 1 ≤ i ≤ p, (a i ) * = a * i , and for any letters X 1 , . . . , X k in {u, u * , a i , a * i : 1 ≤ i ≤ p} and z ∈ C, we have

(zX 1 • • • X k ) * = z * X * k • • • X * 1 .
We denote the unital * -algebra generated by such polynomials by

A = C u, u -1 , a i , a * i ; 1 ≤ i ≤ p .
The unital * -algebra generated by the non-commutative polynomials in a 1 , a * 1 , . . . , a p , a * p only is denoted by B. We will evaluate all polynomials P i at the matrices U N , (U N ) * , A N 1 , (A N 1 ) * , . . . , A N p , (A N p ) * and will omit writing this explicitly in the sequel, e.g. writing Tr(P ) to mean Tr P (U N , (U N ) * , A N 1 , . . . , A N p ) . Notice that there is no relation between the formal variables u and u -1 , or a i and a * i for i ∈ N * (except for those involving * ). We will denote by tr = 1 N Tr the normalized trace. In this article, we study the random variables Tr(P 1 ), . . . , Tr(P l ), seen as functions of U N , under the measure µ N V (see (1)). We will be interested in computing the joint moments and cumulants of these random variables defined as follows.

To state the definition, we introduce some notation about partitions. We denote by P(I) the set of partitions of a finite set I. In particular, for n ∈ N * , we denote the set {1, 2, . . . , n} by [n]. We denote the cardinality of a finite set I by |I|. Given a partition π ∈ P(I), |π| is the number of blocks of π.

Definition 2.1. Let k ∈ N * . The joint moment of the complex random variables X 1 , . . . , X k is m k (X 1 , . . . , X k ) = E [X 1 X 2 • • • X k ] .
The joint cumulant of the complex random variables X 1 , . . . , X k is c k (X 1 , . . . , X k ), defined recursively by

c k (X 1 , . . . , X k ) = m k (X 1 , . . . , X k ) - π∈P([k]) |π|≥2 B∈π c |B| (X i : i ∈ B) .
Notice that both the joint moments and cumulants are symmetric, multilinear functions. The symmetry, which can be proven inductively, makes the expression c |B| (X i : i ∈ B) above unambiguous.

Remark 2.2. The cumulants can also be defined as the coefficients of the series of the logarithm of the exponential generating series of the moments

n≥0 z n n! c n (X 1 , . . . , X 1 ) = ln n≥0 z n n! m n (X 1 , . . . , X 1 ) .
Definition 2.3. For P 1 , . . . , P l ∈ A, we write the joint moments of the traces of P i 's under µ N V as α N V,l (P 1 , . . . , P l ) = m l (Tr(P 1 ), . . . , Tr(P l )) = U(N )

Tr(P 1 ) • • • Tr(P l )dµ N V .
We write the joint cumulants under µ V N as W N V,l (P 1 , . . . , P l ) = c l (Tr(P 1 ), . . . , Tr(P l )) , and introduce the renormalized cumulants WN V,l (P 1 , . . . , P l ) = N l-2 c l (Tr(P 1 ), . . . , Tr(P l )) .

In Section 6, we will discuss an asymptotic expansion (as N → ∞) for the joint cumulants. For now, we study the moments for N fixed.

When V = 0, we can compute directly the moments using Weingarten's formula, see Subsection 2.2. When V = 0, we can compute the cumulants using the free energy F N V defined below. To this end, we consider the partition function Z N V . Recall that V = k i=1 z i q i is the potential, a sum of k polynomials q 1 , . . . , q k ∈ A with complex coefficients z 1 , . . . , z k . We have

Z N V = U(N ) exp(N Tr(V ))dU N ,
and we define the free energy as

F N V = 1 N 2 ln Z N V . (4)
The free energy is always well defined when Tr V is real.

In the expression of the partition function, we can develop the exponential as a series and exchange the sum and the integral:

Z N V = U(N ) n1,...,n k ≥0 k i=1 (N z i Tr(q i )) ni n i ! dU N = n1,...,n k ≥0 k i=1 (N z i ) ni n i ! U(N ) Tr(q 1 ) n1 • • • Tr(q k ) n k dU N ,
in the second line, we used that U(N ) is compact so that the Tr q i are bounded. Notice that this expression is valid for all z, even if Tr V is not real. We introduce the notation z = (z 1 , . . . , z k ), and for n = (n 1 , . . . ,

n k ) ∈ N k , z n = k i=1 z ni i and n! = k i=1 n i !. Then, Z N V = n≥0 N n n∈N k n1+•••n k =n z n n!
α N 0,n (q 1 , . . . , q 1 n1times , . . . , q k , . . . , q k n k times

),

and therefore the partition function is a generating series of the moments with respect to the Haar measure (i.e. with V = 0). Similarly, the free energy is a generating series of the renormalized cumulants for V = 0 (see [Bon15, Theorem 1.3.3, 4.])

F N V = n≥1 n∈N k n1+•••n k =n (N z) n n! 1 N 2 W N 0,n (q 1 , . . . , q 1 n1 times , . . . , q k , . . . , q k n k times ) = n≥1 n∈N k n1+•••n k =n z n n! WN 0,n (q 1 , . . . , q 1 n1 times , . . . , q k , . . . , q k n k times )
Notice that the free energy a priori exists only for z sufficiently small. Indeed, Z N V is defined for all z but is nonzero on a open neighborhood of 0 which depends on N . In particular, the radius of convergence of F N V a priori depends on N .

Notice that by modifying the potential V and differentiating, we have

∂ ∂t t=0 F N V +tP = 1 N U(N ) Tr(P )dµ N V (U N ) = 1 N α N V,1 (P ) = WN V,1 (P ).
In general, we can prove by induction the following lemma.

Lemma 2.4. The renormalized joint cumulants are given by WN V,l (P 1 , . . . , P l ) =

∂ l ∂t 1 ∂t 2 • • • ∂t l t1=...=t l =0 F N V + i tiPi .
Lemma 2.4 implies that for a fixed N , there exists a neighborhood

U 0 ∈ C k of 0 such that for z ∈ U 0 , WN V,l (P 1 , . . . , P l ) = n≥0 n∈N k n1+•••n k =n z n n! WN 0,n (q 1 , . . . , q 1 n1 times
, . . . , q k , . . . , q k n k times , P 1 , . . . , P l ).

(5)

In the next subsections, we compute the moments with respect to the Haar measure. From these moments and Definition 2.1, we can compute the cumulants with respect to the Haar measure. The expression (5) motivate the introduction in Section 3.5 of a formal sum. The first terms of this sum are shown to give the asymptotic expansion of the cumulants in Theorem 1.3.

The Weingarten formula

To compute the moments with respect to the Haar measure, the key tool is Weingarten's formula, first obtained in [START_REF] Weingarten | Asymptotic behavior of group integrals in the limit of infinite rank[END_REF], which expresses the average of coefficients of a unitary matrix in terms of the Weingarten function defined below (Definition 2.5). See [START_REF] Collins | The Weingarten Calculus[END_REF] for a review on the Weingarten calculus.

The Weingarten formula involves a sum over permutations. Let us fix some notation pertaining to permutations. For I a finite set, we denote by S(I) the set of permutations on this set. In particular, S n = S([n]) is the set of permutations on [n] = {1, 2, . . . , n}. A permutation σ admits a cycle decomposition whose set of cycles is denoted by Cycles(σ) and whose number of cycles is denoted by c(σ).

We also introduce the modified traces Tr σ (M ) and tr σ (M ) for σ ∈ S(I) and M = (M i , i ∈ I) a tuple of matrices, defined by

Tr σ (M ) = c∈Cycles(σ) Tr -→ i∈c M i , tr σ (M ) = c∈Cycles(σ) tr -→ i∈c M i = N -c(σ) Tr σ (M ), (6)
where, if c = (i 1 . . . i k ) is a cycle of the permutation σ, the notation

- → i∈c M i , stands for the non- commutative product M i1 M i2 • • • M i k .
Notice that such a non-commutative product is defined up to circular permutation. The trace property ensures that the quantity Tr σ (M ) is well defined. Definition 2.5. Let q ∈ N * . The Weingarten function Wg N : S q → C is defined for all π ∈ S q by

Wg N (π) = U(N ) (U N ) 11 • • • (U N ) qq (U N ) 1π(1) • • • (U N ) qπ(q) dU N .
This function can also be defined using characters of the symmetric group (see [START_REF] Collins | Integration with respect to the Haar measure on unitary, orthogonal and symplectic group[END_REF]). The invariance of the Haar measure by multiplication by permutation matrices implies that the Weingarten function is invariant by conjugation, i.e. for all σ, π ∈ S q we have Wg N (σπσ -1 ) = Wg N (π).

Theorem 2.6. (Weingarten's formula, see [START_REF] Collins | Moments and cumulants of polynomial random variables on unitarygroups, the Itzykson-Zuber integral, and free probability[END_REF] and [START_REF] Collins | Integration with respect to the Haar measure on unitary, orthogonal and symplectic group[END_REF])

Let U N be a Haar-distributed unitary matrix of size N ×N and i = (i 1 , i 2 , . . . , i q ), j = (j 1 , j 2 , . . . , j q ), i = (i 1 , i 2 , . . . , i q ) and j = (j 1 , j 2 , . . . , j q ) be elements of [N ] q or [N ] q for q, q ≥ 1.

U(N ) (U N ) i1j1 • • • (U N ) iqjq (U N ) i 1 j 1 • • • (U N ) i q j q dU N = δ q,q ρ,σ∈Sq q k=1 δ i k ,σ(i k ) δ j k ,ρ(j k ) Wg N (σρ -1 ). (7)
Before giving the expression for the moments with respect to the Haar measure α N 0,l (P 1 , . . . , P l ), let us make a simplifying assumptions on our polynomials P i .

We introduce the set Y of words in the letters a 1 , a * 1 , . . . , a p , a * p . We assume that for all i, P i can be written uniquely as

M i,1 u i,1 M i,2 u i,2 • • • M i,di u i,d i , (8)
where M i,j is either the empty word or an element of Y, d i ≥ 1, and i = ( i,1 , . . . , i,di ) ∈ {±1} di . We write X the set of such monomials.

We have Y ⊂ X . Notice that A is generated by the elements of X up to cyclic permutation of the factors in a monomial.

The integer d i , that we will sometime write deg P i , is the degree of the monomial P i . Notice that there is no relation between the formal variables, in particular between u and u -1 (except for those involving * ). Therefore, the degree of (8) is defined by counting the total number of letter u or u * in a word. In particular, deg(uu -1 ) = 2. Definition 2.7. With P 1 , . . . , P l ∈ X , and with the notation (8), we set • P = (P 1 , . . . , P l ),

• M P = (M i ) i∈[ i deg Pi] = (M 1,1 , . . . , M 1,d1 , . . . , M l,1 , . . . , M l,d l ), • P = ( (i)) i∈[ i deg Pi] = ( 1,1 , . . . , 1,d1 , . . . , l,1 , . . . , l,d l ).
Notice that we change the indices of the monomials M i,j and of i,j , by setting for all

1 ≤ i ≤ k, 1 ≤ j ≤ d i , M d1+•••+di-1+j = M i,j and (d 1 + • • • d i-1 + j) = i,j .
We set deg P = i deg P i . Furthermore, we define the permutation

γ P = (1 . . . d 1 )(d 1 + 1 . . . d 2 ) • • • (d l-1 + 1 . . . d l ). (9)
Remark 2.8. Notice that by fixing the notation M P , P , γ P , we fix a labelling of the factors of the polynomials of P . For any permutation σ ∈ S deg P , we can replace γ P , M P = (M i ), P = ( (i)) by γ = σ -1 γ P σ, M = (M i ) = (M σ(i) ), = ( (i)) = ( (σ(i))). This new data describes the same polynomials.

We can assume all the polynomials are of the form (8) without loss of generality as α N V,l is multilinear and satisfies the trace property α N V,l (P 1 , . . . , P i-1 , P i Q, P i+1 , . . . , P l ) = α N V,l (P 1 , . . . , P i-1 , QP i , P i+1 , . . . , P l ) ,

as

Tr(P i Q) = Tr(QP i ).
Furthermore, if there exists i such that P i contains no letter u nor u -1 , we can factor the term Tr(P i ) out of the moment.

The formula for the moments with respect to the Haar measure involves permutations belonging to the set S ( ) (I) ⊂ S(I) of permutations (introduced in [MSS07]), for ∈ {±1} I . Definition 2.9. Let ∈ {±1} I . The set S ( ) (I) ⊂ S(I) is the set of permutations π ∈ S(I) such that

π -1 (+1) = -1 (-1) . Furthermore, we define π ( ) = π 2 | -1 (+1) ∈ S( -1 (+1)). Notice that the set S ( ) (I) is empty if | -1 (+1)| = | -1 (-1)|. Example 2.10. For instance, if = (+1, +1, -1, +1, -1, -1), then π = (1 3 4 6)(2 5) ∈ S ( ) 6 , and π ( ) = (1 4)(2).
The notation of Definitions 2.7 and 2.9 allow us to express the moments in a compact way.

Proposition 2.11 ([MSS07, Proposition 3.4]). Let P = (P 1 , . . . , P l ) ∈ X l . We have

α N 0,l (P ) = α N 0,l (P 1 , . . . , P l ) = π∈S ( P ) deg P Tr γ P π -1 (M P )Wg N (π ( P ) ). (10)

Expansion of the Weingarten function

We wish to express the moments and cumulants uniquely in terms of combinatorial objects and traces. To this end, we now present a result of Novak [START_REF] Novak | Jucys-Murphy elements and the unitary Weingarten function[END_REF] expressing the Weingarten function in terms of walks on the Cayley graph of S n generated by the transpositions.

Definition 2.12. The value of a transposition τ = (i j) ∈ S(I), where I is a finite subset of N * , is val(τ ) = max{i, j}.

Definition 2.13. Let ρ and σ be in S(I), with I a finite subset of N * . A (weakly) monotone walk with r steps on S(I) from ρ to σ is a tuple (τ 1 , . . . , τ r ) of transpositions of S(I) such that

• τ r • • • τ 1 ρ = σ, and • val(τ 1 ) ≤ • • • ≤ val(τ r ).
We denote the set of such walks by -→ W r (ρ, σ), and we define -→ w r (ρ, σ) as the cardinality of the set -→ W r (ρ, σ).

Proposition 2.14 ([Nov10, Theorem 3.1]). Let π ∈ S q with N ≥ q. We have

Wg N (π) = r≥0 (-1) r N r+q - → w r (Id, π),
and the series is absolutely convergent.

This allows to prove the following lemma about monotone walks. This Lemma will be useful to prove Lemma 3.34.

Lemma 2.15. Let σ and ρ in S q . We have for all r ≥ 0,

- → w r (Id, ρ) = - → w r (Id, σ -1 ρσ).
Proof. Consider the generating series

G(z) = r≥0 - → w r (Id, ρ)z r , H(z) = r≥0 - → w r (Id, σ -1 ρσ)z r .
By Proposition 2.14, G and H are absolutely convergent and hence analytic functions of z, with radius of convergence greater than 1/q. Furthermore, we have for

N ≥ q that N q Wg N (ρ) = G( -1 N ) and N q Wg N (σ -1 ρσ) = H(-1 N ). Weingarten's function is invariant by conjugation, so H(-1 N ) = G(-1 N ) for all N ≥ q. Thus G(z) = H(z) for all |z| < 1
q by analyticity since {1/N } N ≥q has an accumulation point. Proposition 2.14 and Proposition 2.11 imply the following Proposition (recall notation from Definition 2.7).

Proposition 2.16. Let N ≥ 1 be an integer, P = (P 1 , . . . , P l ) ∈ (X ) l with m = deg P /2 ≤ N . The moments admits the expansion

α N 0,l (P 1 , . . . , P l ) = r≥0 (-1) r N r+m π∈S ( P ) 2m Tr γ(P )π -1 (M P ) - → w r (Id, π ( P ) ).
Moreover, the series is absolutely convergent.

Maps and maps of unitary type

In this section, we introduce combinatorial objects, the so-called maps of unitary type, that will be convenient to express the moments α N 0,l , and then the cumulants W N 0,l . These maps generalize the maps appearing in the Gaussian case.

Maps

First, we give a few definitions regarding maps. Definition 3.1. An embedded graph is a pair (Γ, S), where S is a compact topological surface and Γ is a graph (with possibly loops and multiple edges) embedded in S, so that we write Γ ⊂ S, such that

• the vertices of Γ are distinct points on the surface S,

• the edges of Γ are simple paths on S that can intersect only at their endpoints,

• the complement S \ Γ of the graph is a disjoint union of simply connected open sets. Each of these connected components is called a face.

The genus of an embedded graph is the genus of the surface S.

An embedded graph will be said to be oriented if Γ is an oriented graph.

We shall sometimes refer to Γ and S as the underlying graph and surface of an embedded graph.

Remark 3.2. In this article, the embedded graphs are in general disconnected. We will specify it when the maps we consider are connected.

Definition 3.3. Two (oriented or unoriented) embedded graphs (Γ 1 , S 1 ) and (Γ 2 , S 2 ) are said to be isomorphic if there is a orientation-preserving homeomorphism h : S 1 → S 2 such that h| Γ is an isomorphism of (oriented or unoriented) graphs.

Definition 3.4. A map (or oriented map) is an equivalence class of embedded graphs (or oriented embedded graphs) up to isomorphism.

As the genus of a surface is a topological invariant, the genus of a map is the genus of any of its representative.

Definition 3.5. A face will be said to be incident to a vertex or an edge if the vertex or the edge belongs to the boundary of the face.

It will be convenient to regard each edge of a map as being made of two half-edges. As a part of an embedded graph they can be described as follows. Each edge e = {v, v } (with possibly v = v ) can be parametrized by γ e : [0, 1] → S, with γ e (0) = v and γ e (1) = v . The two half-edges that compose e are h = γ e ([0, 1/2]) and h = γ e ([1/2, 1]). We will say that h (respectively h ) is connected to v (resp. v ). As we will be concerned only with combinatorial data, the choice of parametrization γ e will be unimportant. When going from the vertex of the half-edge to the other end of the half-edge (connected to another half-edge), we can distinguish a left side and a right side (see Figure 1). We label the half-edges of a map C from 1 to 2m, where m is the number of edges of C. By convention, we write each label at the left of its half-edge. See Figure 2.

In an oriented map with labelled half-edges, the edges can be represented as an ordered pair of two half-edges. The first half-edge is connected to the first vertex of the edge and is said to be outgoing. The second half-edge is connected to the second vertex of the edge and is said to be ingoing. These labels allow us to define three permutations that encode the labelled map, see [START_REF] Lando | Graphs on Surfaces and Their Applications[END_REF].

Definition 3.6. Let C be a map with 2m labelled half-edges. We define the three permutations σ C , α C , ϕ C ∈ S 2m as follows.

• Let i ∈ [2m].
The half-edge labelled by i is attached to a vertex v i . Starting from the half-edge i and turning in the counterclockwise direction around v i , the next half-edge we encounter is labelled j (possibly i = j). We set σ C (i) = j.

• Let i ∈ [2m].
The half-edge labelled by i is attached to another half-edge labelled j. We set α C (i) = j.

• Let i ∈ [2m]
. The half-edge labelled i has a face f i to its left. Starting from the half-edge i, we turn in the counterclockwise direction around the face f i . The next half-edge we encounter with f i to its left is labelled j. We set ϕ C (i) = j.

The three permutations σ C , α C , ϕ C constitute the permutational model of C.

The permutation σ C describes how the half-edges are arranged around a vertex (we call this data "the local structure of the map"), and α C describes how to attach them. The permutation α C only depends on the underlying graph of the map.

Notice that α C belongs to the set of involutions without fixed points

I 2m = {α ∈ S 2m : α 2 = Id, ∀i ∈ [2m], α(i) = i}.
Example 3.7. The map C of Figure 2 is described by For an oriented map, we must also describe the orientation of each half-edge.

σ C = (1 2 3)( 4
Definition 3.8. Let C be an oriented map with 2m labelled half-edges. We define C = ( 1 , . . . , 2m ) ∈ {±1} 2m as follows. For all i ∈ [2m], we set i = +1 if the half-edge labelled i is outgoing and i = -1 if the half-edge labelled i is ingoing.

Such an belongs to the set E 2m = { ∈ {±1} 2m :

2m i=1 i = 0}.
In the case of an oriented map, α is in the set I ( ) 2m of the permutations of I 2m such that for all i ∈ [2m], (α(i)) = -(i).

Lemma 3.9. [LZ04, Proposition 1.3.16] Let C be a map with labelled half-edges. We have

ϕασ = Id .
Conversely, we can reconstruct a map from two permutations σ ∈ S 2m , α ∈ I 2m . The following theorem is essentially a restatement of a result obtained in [START_REF] Edmonds | A combinatorial representation for polyhedral surfaces[END_REF].

Theorem 3.10. Let m ≥ 1, σ ∈ S 2m and C m,σ be the set of maps with labelled half-edges C such that σ C = σ. Then, the mapping

C m,σ → I 2m C → α C , is a bijection.
This theorem shows that once the local structure of the map (and a labelling of the half-edges) is fixed, the map only depends on the underlying graph.

We have the corresponding result for oriented maps.

Maps of unitary type

We have just seen how to describe a map with permutations. We now define a particular type of map, which we call map of unitary type, whose edge structure is described by a permutation π ∈ S ( ) 2m for some and m ≥ 1 and a monotone walk

(τ 1 , . . . , τ r ) ∈ -→ W r (Id, π ( ) ).
Definition 3.12. A vertex in an oriented map will be said to be alternated if when going around this vertex the half-edges connected to it are alternatively ingoing and outgoing.

Definition 3.13. Let I be a finite subset of N * and r ∈ N. A map of unitary type with labels in I with r black vertices is an oriented map with vertices colored in white or black such that 1. there are r black vertices, which are alternated of degree 4 and numbered from 1 to r;

2. there are |I| half-edges that are connected to white vertices. We call these half-edges white half-edges. Each element of I labels exactly one white half-edge;

3. if an oriented edge connects the black vertex numbered k to the black vertex numbered l, with the orientation from k to l, then k < l.

See Figure 3 for an example.

Remark 3.14. Notice that condition 3. in Definition 3.13 implies that each face is incident to at least one white vertex. Indeed, if it were not the case, there would be a face incident to only black vertices, numbered n 1 < n 2 < . . . < n k , with n k < n 1 , a contradiction. Remark 3.15. The maps of unitary type are very similar to the maps introduced in [CGMS09] to describe the leading term in the asymptotics of the cumulants when N → ∞. In fact, the two kinds of maps in genus 0 are related by a surgery that transforms black vertices of unitary maps into "dotted edges" of the maps from [START_REF] Collins | Asymptotics of unitary and othogonal matrix integrals[END_REF]. Here, we consider the non-planar cases as well.

We denote by w k (C) the white vertex in the unitary type map C connected to the half-edge labelled k. We will omit the notation C if there is no ambiguity.

Notice that in a map of unitary type, the half-edges connected to black vertices are not labelled. We now explain how to label them. Consider, in a map of unitary type, an unlabelled half-edge which we denote by h. This half-edge has a face f to its left (see Figure 1). Starting from h, we turn around the face in the clockwise direction until we encounter a labeled half-edge connected to a white vertex, which is labelled by i. We assign to h the label i. See Figures 3 and4.

Notice that by Remark 3.14, all faces are incident to at least one white vertex, so all unlabelled half-edges can be labelled by this procedure, in a unique way.

The following Lemma will be used to prove Lemma 3.22. Lemma 3.16. Let h be a half-edge labelled by i. There exists a unique white half-edge h labelled by i. If h is ingoing then h is ingoing. If h is outgoing then h is outgoing.

Proof. Consider an ingoing half-edge h. The existence and uniqueness of h is a consequence of the definition. If h is a white half-edge, the statement is obvious. If not, then consider the face f to its left. Starting from h we turn around f in the clockwise direction until we reach a white vertex w. All the vertices we encounter before w are black. The black vertices are alternated so all the half-edges such that f is at their left are ingoing as well, and so is the white half-edge h that we reach, whose label is the same as the label of h. We proceed similarly for outgoing half-edges.

The labels for the edges allow us to define the notion of value of a black vertex.

Definition 3.17. Consider a black vertex b. Let i and j be the labels of the two outgoing half-edges at b. The value of the black vertex b is val(b) = max(i, j).

Definition 3.18. A map of unitary type with r black vertices b 1 , . . . , b r numbered respectively 1, . . . , r is nondecreasing if

val(b 1 ) ≤ val(b 2 ) ≤ • • • ≤ val(b r ).
Example 3.19. Figure 3 displays an example. The labels of the black vertices are in red. The values of the black vertices s 1 and s 2 are val(s 1 ) = 2, val(s 2 ) = 6.

Permutational model

Similarly as in Section 3.1, we define a permutational model for the maps of unitary type.

Definition 3.20. Let I ⊂ N * be finite and r ∈ N. Let C be a map of unitary type with labels in I and r black vertices.

We define C = ( (i), i ∈ I) as follows. If the white half-edge labelled i ∈ I is outgoing, we set (i) = +1, else we set (i) = -1.

We define ρ C , π C , φ C ∈ S(I) and τ C = (τ 1 , . . . , τ r ) ∈ S( -1 C (+1)) r as follows. • Let i ∈ I. The white half-edge h i , labelled i, is connected to a white vertex w i . Starting from h i , we turn in the counterclockwise direction around w i . Let j be the label of the next half-edge connected to w i . We set ρ C (i) = j.

• Let i ∈ I. The white half-edge h i labelled i is connected to another half-edge h j , which is labelled by j. We set π C (i) = j.

• Let i ∈ I. The white half-edge labelled i has a face f i to its left. Starting from the half-edge i, we turn in the counterclockwise direction around the face f i . The next white half-edge with f i on its left we encounter is labelled j. We set φ C (i) = j.

• Let b l be the black vertex numbered l. The outgoing half-edges that are connected to it are labelled by i and j. We set τ l = (i j).

The permutations ρ C , π C , φ C are the counterparts for maps of unitary type of the permutations σ C , α C , ϕ C defined in Definition 3.6.

Example 3.21. For the map in Figure 3, we have r = 2 and

ρ C = (1 4 3 7)(5 6)(2 8), C = (+1, +1, -1, -1, +1, +1, -1, -1), τ 1 = (1 2), τ 2 = (2 6), π C = (1 7 6 8 2 4)(3 5), φ C = (1)(2)(3 6)(4 8 5)(7).
Lemma 3.22. The permutation π C belongs to S ( C ) (I).

Proof. An edge consists of an outgoing half-edge h attached to an ingoing half-edge h . Assume that h is white. Let i be the label of h and j be the label of h . We have π(i) = j. By Lemma 3.16, j is the label of a white ingoing half-edge. Thus, (i) = -1 and (j) = +1. We proceed similarly if h is white.

We have the following counterpart of Lemma 3.9 Lemma 3.23. For a unitary type map C, we have ρ -1 C π -1 C = φ C . Proof. Let i ∈ I be the label of a white outgoing half-edge, and f the face at the left of the halfedge. Starting from the half-edge labelled i, we follow the boundary of the face until we encounter a white vertex. The last half-edge we traversed, which was ingoing, was labelled by j. This half-edge is connected to a outgoing half-edge labelled i. By definition, we thus have π C (j) = i. The next labelled half-edge when going around f in the counterclockwise order is the half-edge following the half-edge j when turning in the clockwise direction around the white vertex. This next half-edge is thus labelled 5. The proof is identical if i if the label of an ingoing half-edge. Proposition 3.24. Let I be a finite subset of N * , r ∈ N * , ρ ∈ S(I), and ∈ {±1} I . Let C be a unitary type map with set of labels I and with r black vertices such that ρ C = ρ and C = , and let τ C = (τ 1 , . . . , τ r ).

f i i i i j = π -1 (i) ρ -1 π -1 (i)
ρ -1 C (j) = ρ -1 C π -1 C (i), see Figure
Then,

τ r • • • τ 1 = π ( )
C . Proof. Let k ∈ I be the label of a white outgoing half-edge connected to a vertex w k = u 0 . Let f be the face at its right. We construct a path starting from the half-edge labelled k as follows, see also Figure 6. Consider the edge e 1 = (u 0 , u 1 ) of which the half-edge labelled

k is part. If u 1 is white then for all 1 ≤ j ≤ r, τ j (k) = k = π ( ) C (k).
If u 1 is black, we can find vertices u 2 , u 3 , . . . , u p+1 such that u 2 , . . . , u p are black and u p+1 is white, and (u j , u j+1 ) follows (u j-1 , u j ) when going around the vertex u j in the counterclockwise order. Notice that these edges are all part of the boundary of f .

Let n 1 , n 2 , . . . , n p be the labels of the black vertices u 1 , . . . , u p , and k j , 1 ≤ j ≤ p + 1 be the labels of the outgoing half-edges edges (connected to u j-1 ) in (u j-1 , u j ). By construction, we have

τ nj (k j-1 ) = k j . k 1 = k k 2 k 3 k 4 n 1 n 2 n 3 l l l l
(k) = π -1 C (k p ). Thus τ np τ np-1 • • • τ n1 (k) = π ( ) (k). Assume now that τ r • • • τ 1 (k) = τ np τ np-1 • • • τ n1 (k). Let j be the minimal index such that τ j • • • τ 1 (k) = τ n p • • • τ n1 (k),
with n p ≤ j < n p +1 (with the convention n p+1 = r + 1). The index j is minimal so j > n p (else we would have a contradiction as

τ j-1 • • • τ 1 (k) = τ n p -1 • • • τ n1 (k)). We have k p = τ j-1 • • • τ 1 (k) = τ n p • • • τ n1 (k).
By construction, all the half-edges labelled by k p are on the boundary of a same face f , and they follow each other. We have just seen that there is such an half-edge in the edge between u p and u p +1 . The fact that τ j (k p ) = k p implies that there is an half-edge labelled k p that is connected to the j-th black vertex. However, this edge must be before (when going around the face f ) or after the edge (u p , u p +1 ) in the boundary of f . This contradicts the fact that if there is an edge going from a black vertex i to a black vertex labelled j we have i < j, as n p < j < n p +1 . Definition 3.25. We denote by C r I, ,ρ the set of nondecreasing unitary type maps C with set of labels I and with r black vertices such that ρ C = ρ and C = .

Similarly, we denote by C g,I, ,ρ the set of nondecreasing unitary type maps C with set of labels I and with genus g such that ρ C = ρ and C = .

Theorem 3.26. Let I be a finite subset of the positive integers, r ∈ N * , ∈ {±1} I and ρ ∈ S(I).

The mapping

C r I, ,ρ → π∈S ( ) (I) {π} × -→ W r (Id, π ( ) ) C → (π C , τ C )
is a bijection.

Proof. Lemma 3.22 and Proposition 3.24 show that this map has values in π∈S ( ) (I) {π}× -→ W r (Id, π ( ) ). We now construct an inverse mapping. To do so, we explicitely construct a map corresponding to permutations π and τ = (τ 1 , . . . , τ r ). By Theorem 3.10, it suffices to construct from π and τ the incidence relation of the underlying graph.

To this end, we introduce the set whose elements represent the half-edges Ĩ = {h i : i ∈ I} ∪ r j=1 {h j,1 , h j,2 , h j,3 , h j,4 }. We can split this set into the set of ingoing and outgoing edges Ĩ = Ĩin ∪ Ĩout . We have Ĩout = {h i : i ∈ I, (i) = +1} ∪ r j=1 {h j,2 , h j,4 }. The elements h j,k represent the half-edges of the black vertices of the map we are going to construct, and the elements h i represent the half-edges of the white vertices. We are going to define a labelling function L : Ĩ → I. We set for all i ∈ I, L(h i ) = i.

To construct a map, we use Theorem 3.10. We define two permutations σ, α ∈ S( Ĩ) as follows. We define ρ ∈ S( Ĩ) by ρ(h i ) = h ρ(i) and the identity otherwise. We set

σ = ρ(h 1,1 h 1,2 h 1,3 h 1,4 ) • • • (h r,1 h r,2 h r,3 h r,4 ) .
The permutation α is given by the following algorithm. Let π ∈ S ( ) (I), and τ = (τ 1 , . . . , τ r ) ∈ -→ W r (Id, π ( ) ). We consider first the permutation τ 1 = (i 1 , j 1 ), with i 1 < j 1 . We set α 1 = (h i1 h 1,1 )(h j1, h 1,3 ). We set L(h 1,2 ) = j 1 and L(h 1,4 ) = i 1 . In terms of maps, this procedure corresponds to connecting two edges to a same black vertex, see Figure 7.

We proceed similarly to construct the black vertices labelled 2, 3, . . . , r from the transpositions τ 2 , . . . , τ r . At the k-th step, we consider the transposition τ k = (i k j k ), with i k < j k . There is only one half-edge h (respectively h ) in Ĩout such that L(h The name of the half-edges are in red, and the labels are in black. Here, α1 = (h1 h1,1)(h3 h1,3).

) = i k and α k-1 (h) = h (respectively L(h ) = j k and α k-1 (h ) = h ). We set α k = α k-1 (h h k,1 )(h h k,3 ). 1 2 3 4 5 6 L(h 1,4 ) = 1 L(h 1,2 ) = 3 h 3 h 1 h 1,1 h 1,2 h 1,3 h 1,
Finally, we connect each remaining outgoing half-edge labelled i to the ingoing half-edge π -1 (i). For all i ∈ I, there is a unique h such that α r (h) = h and L(h) = i. We set α r+1,i = (h h π -1 (i) ) and define α = α r i∈I α r+1,i .

We define ˜ ∈ {±1} Ĩ by ˜ (i) = +1 if i ∈ Ĩout and ˜ (i) = -1 otherwise. Theorem 3.10 implies that given σ, α and ˜ , we construct a unique map C. By construction, the resulting map is of unitary type : the vertices attached to the half-edges h i are the white vertices and the other are the black vertices. The black vertex attached to the half-edges h j,k is numbered j. Furthermore, the map is constructed such that π C = π C and τ C = τ C .

We have constructed a right inverse, so the map C → (π C , τ C ) is surjective. This map is injective. Indeed, consider a map of unitary type described by π and τ = (τ 1 , . . . , τ r ), and an outgoing half-edge h i labelled i. There are four cases.

• If h i is a white half-edge such that for all j we have τ j (i) = i, then h i is necessarily attached to the white half-edge labelled π -1 (i).

• If h i is a white half-edge and there exists k, such that τ k (i) = i, then h i is necessarily connected to the k -th black vertex, where k is the smallest such integer.

• If h i is a half-edge connected to the k-th black vertex and for all l > k τ l (i) = i, then h i is necessarily attached to a white half-edge labelled π -1 (i)

• If h i is a half-edge connected to the k-th black vertex and l is the smallest integer such that l > k and τ l (i) = i, then h i is necessarily attached to the l-black vertex.

Thus two maps of unitary type in C r I, ,ρ described by the same permutations π and τ have necessarily the same edges, i.e. are identical.

We can associate to the triplet (ρ C , π C , τ C ) the group

G(C) = ρ C , π C , τ 1 , . . . , τ r , (11)
where τ C = (τ 1 , . . . , τ r ).

Proposition 3.27. A unitary type map C with set of labels I is connected if and only if the group G(C) defined by Equation (11) acts transitively on I.

Proof. First, assume that C is connected. Let i, j ∈ I. There is a path ρ (made up by vertices and edges) connecting the white vertices w i and w j . First, let us assume that ρ contains only black vertices, except for its boundary which is made up of w i and w j . The path encounters the black vertices n 1 , . . . , n p , the labels on the left of the edges that constitute ρ are k 1 , . . . , k p+1 . The first and last edges are connected to w i and w j so k 1 = ρ m1 (i) and k p+1 = ρ m2 π m3 (j) for some integers 8. Those are the only two possibilities as the half-edges connected to a black vertex labeled k, with τ k = (u v) can only be labeled by u or v.

m 1 , m 2 , m 3 . Let 1 ≤ i ≤ p. If k i = k i+1 , we set σ i = Id, and if τ ni (k i ) = k i+1 , we set σ i = τ ni , see Figure
n 1 n 2 n 3 k 1 k 2 k 3 k 4
Figure 8: Three situations for σ i .

We set σ1 = τn 1 , σ2 = Id, and σ3 = τn 3 .

Thus, we have proved that there is

σ ρ = π -m3 ρ -m2 σ p • • • σ 1 ρ -m1 ∈ G(C), such that σ ρ (i) = j.
In general, any path connecting w i and w j can be written as the concatenation of paths with only black vertices in their interiors, we can thus construct by composition a permutation in G(C) that sends i to j. Thus G(C) is transitive.

Conversely, if G(C) is transitive, for any k, l ∈ I, there exists σ ∈ G(C) such that σ(k) = l. We can write σ = σ p • • • σ 1 , with for all i, σ i is one of ρ C , π -1 C , τ 1 , . . . , τ r . We use this to construct a path connecting v k to v l . For all i, we attach to σ i a path ρ i starting from a half-edge labelled k i . We set k 1 = k, and we will show that k p+1 = l.

• If σ i = ρ C , ρ i is the empty path, and k i+1 = ρ(k i ).

• If σ i = π -1
C , ρ i is the path connecting the half-edge k i to the half-edge π -1 (k i ). Such a path exists by the propagation of labels procedure. We set k i+1 = π -1 (k i ).

• If σ i = τ ni , for some n i , and τ ni (k i ) = k i , then ρ i is the empty path and k i+1 = k i .

• If σ i = τ ni , for some n i , and

τ ni (k i ) = k i , then we set k i+1 = τ ni (k i ). Both k i and k i+1
are labels of outgoing half-edges. We set ρ i to be the path that starts from the half-edge k i , follows the half-edges labelled k i until it reaches the black vertex n i , and then follows the half-edges labelled k i+1 until the half-edge k i+1 , and the vertex w ki+1 .

We have constructed a path going from the half-edge i to the half-edge k p+1 = σ(i) = j, as wanted.

Expression of the moments in terms of maps of unitary type

Theorem 3.26 allows us to rewrite the expression for the moments given in Proposition 2.16 (see Definition 2.7 for relevant notation).

Corollary 3.28. Let N ≥ 1 be an integer, P = (P 1 , . . . , P l ) ∈ X l be monomials with m = 1 2 deg P ≤ N . The moments under the Haar measure µ N 0 (see Definition 2.3) admit the following expansion

α N 0,l (P 1 , . . . , P l ) = r≥0 (-1) r N r+m C∈C r [2m], P ,γ -1 P Tr φ C (M P ).
Furthermore, the series is absolutely convergent.

The weights Tr φ C (M P ) can be interpreted as product of weights given by the faces of the map C, see Figure 9. Figure 9: A map with its weights This weighted map gives (up to a sign) a contribution from the sum α

(0),N 0,4 (M 1 u -1 M 2 u -1 , M 3 uM 4 u, M 5 u -1 M 6 u, M 7 u -1 M 8 u).
Proof of Corollary 3.28. Recall that we proved in Proposition 2.16 that

α N 0,l (P 1 , . . . , P l ) = r≥0 (-1) r N r+m π∈S ( P ) 2m
Tr γ P π -1 (M P ) -→ w r (Id, π ( P ) ).

By definition of -→ w r (Id, π ( P ) ), we can rewrite this as

α N 0,l (P 1 , . . . , P l ) = r≥0 (-1) r N r+m π∈S ( P ) 2m (τ1,...,τr)∈ -→ W r (Id,π ( P ) ) Tr γ P π -1 (M P ) = r≥0 (-1) r N r+m C∈C r [2m], P ,γ -1 P Tr γ P π -1 C (M P ),
where we used Theorem 3.26 in the last line. We get the result by using Lemma 3.23, which gives

γ P π -1 C = ρ -1 C π -1 C = φ C .
Definition 2.1 and Corollary 3.28 allow us to express the cumulants in terms of maps of unitary types. We deduce the following Lemma.

Lemma 3.29. Let N ≥ 1 be an integer, P = (P 1 , . . . , P l ) ∈ X l be monomials with m = 1 2 deg P . The cumulants admit the expansion

W N 0,l (P 1 , . . . , P l ) = r≥0 (-1) r N r+m C∈C r [2m], P ,γ -1 P C is connected Tr φ C (M P ).
Furthermore, the series is absolutely convergent.

Proof. We show the formula by induction using Corollary 3.28. Notice first that when l = 1, α N 0,1 (P 1 ) = W N 0,1 (P 1 ) and the maps in C r

[2m], P ,γ -1 P are connected. Then, we notice that a map can be decomposed into its connected components. This decomposition gives a partition of the set of labels of half-edges. Each block contains the labels appearing in one connected component. Using Definitions 2.1 and Definition 2.3, we obtain that W N 0,l (P 1 , . . . , P l ) = α N 0,l (P 1 , . . . , P l ) -

Π∈P([l]) |Π|≥2 B∈Π W N 0,|B| (P i , i ∈ B) = r≥0 (-1) r N r+m C∈C r [2m], P ,γ -1 P Tr φ C (M P ) - r≥0 (-1) r N r+m C∈C r [2m], P ,γ -1 P C has at least 2 connected components Tr φ C (M P ).
Hence the result.

Remark 3.30. The formulae imply that we can express moments and cumulants with respect to the Haar measure as a weighted sum over maps. The maps are the nondecreasing maps of unitary type whose local structure (i.e. how the half-edges are attached to the vertices, but not how the half-edges are attached together) is determined by γ -1 P and P . To each face is associated a weight, which is the trace of a certain word in the matrices of M P , times a sign.

A topological expansion for the Haar measure. We now rewrite Lemma 3.29 as a sum over the genus g of the maps rather than on the number of black vertices r. We will see that this gives us an expansion in powers of 1 N 2 . We first recall Euler's formula

2 -2g(C) = V (C) -E(C) + F (C), (12)
where V (C), E(C) and F (C) are the number of vertices, edges and faces of a map C, and g(C) is its genus. In the case of a map of unitary type labelled by a set of 2m integers, and with r black vertices, we have

• c(γ C ) white and r black vertices,

• 2m white half-edges and 4r half-edges out of black vertices, for a total of m + 2r edges,

• c(φ C ) faces (see Definition 3.1).

Thus, we get

2 -2g(C) = (c(γ C ) + r) -(m + 2r) + c(φ C ) = c(γ C ) + c(φ C ) -m -r. (13)
A change of variable in the sum of Lemma 3.29 gives the following Proposition.

Proposition 3.31. Let N ≥ 1 be an integer, P = (P 1 , . . . , P l ) ∈ X l be monomials with m = 1 2 deg P . The cumulants admit the expansion

W N 0,l (P 1 , . . . , P l ) = N 2-l (-1) m+l g≥0 1 N 2g C∈C g,[2m], P ,γ -1 P C is connected (-1) c(φ C ) tr φ C (M P ).
Furthermore, the series is absolutely convergent.

Notice that this expansion is in terms of the normalized trace tr = 1 N Tr. The factors with the trace are bounded by 1 if we assume A N i ≤ 1 for all 1 ≤ i ≤ N and N ≥ 1. Remark 3.32. The sum in Proposition 3.31 is in general not finite. Indeed, even for l = 1 and P 1 = AU BU * , the sum contains terms of arbitrary genus. They appear for instance because of the factorization of the identity Id = (1 2) 2k , for all k ≥ 0. Definition 3.33. Let N ≥ 1 be an integer, P = (P 1 , . . . , P l ) ∈ X l be monomials with m = 1 2 deg P . The term of order 2g in the expansion of the cumulant is denoted by

M (g),N 0,l (P 1 , . . . , P l ) = (-1) m+l C∈C g,[2m], P ,γ -1 P C is connected (-1) c(φ C ) tr φ C (M P ).
We extend this definition to all monomials in A by setting for P 1 , . . . , P l ∈ X and M a word in a 1 , a * 1 , . . . , a p , a * p , M (g),N 0,l (P 1 , . . . , P i-1 , P i M, P i+1 , . . . , P l ) = M (g),N 0,l (P 1 , . . . , P i-1 , M P i , P i+1 , . . . , P l ), for all 1 ≤ i ≤ l.

The following Lemma will be useful in Section 4.1.

Lemma 3.34. With the notation and hypotheses of Proposition 3.31, for any σ ∈ S 2m , let

M σ = (M σ(i) , i ∈ [2m]) M (g),N 0,l (P 1 , . . . , P l ) = (-1) m+l C∈C g,[2m], P •σ,σ -1 γ -1 P σ C is connected (-1) c(φ C ) tr φ C (M σ ).
Proof. This is a consequence of the fact that the numbering of the elements of M P , P , ... is arbitrary (see Remark 2.8), and of the fact that the number of monotone walks is invariant by conjugation, by Lemma 2.15.

Remark 3.35. This Lemma implies in particular that M (g),N 0,l is symmetric in its arguments and that if, say, P l = QR with Q, R ∈ X , we have M (g),N 0,l (P 1 , . . . , P l-1 , QR) = M (g),N 0,l (P 1 , . . . , P l-1 , RQ).

Stationnary distribution of the (A

N i ) 1≤i≤p .
Let us consider sequences of matrices (A N i ) 1≤i≤p which have the same joint law as given matrices of fixed size M × M , A M i for 1 ≤ i ≤ p. For instance, we may consider the subsequence N = qM , with n ∈ N * and with A N i the block-diagonal matrix whose blocks are A M i . In that case, the traces tr φ (M ) no longer depend on N for N = qM . In the case of zero potential (V = 0), by Proposition 3.31, the renormalized cumulant WN 0,1 converges with limit lim

N →∞ WN 0,1 (P ) = M (0),M 0,1 (P ), for P ∈ A.
This fact allows us to prove the following Lemma.

Lemma 3.36.

Fix N ∈ N * . Assume that A N i ≤ 1 for all 1 ≤ i ≤ p. Let P ∈ X .
We have for all choices of (A N i ) 1≤i≤p that

|M (0),N 0,1 (P )| ≤ 1.
Proof. By the previous remark, we have for a choice of stationnary distribution as above

|M (0),M 0,1 (P )| = lim N →∞ | WN 0,1 (P )| = lim N →∞ E [tr(P )] ≤ 1, as P ≤ 1.
More generally, with the (A N i ) 1≤i≤p block diagonal as above, we have

WqM 0,l (P ) = (-1) m+l g≥0 1 (qM ) 2g C∈C g,[2m], P ,γ -1 P C is connected (-1) c(φ C ) tr φ C (M P ) ,
where tr φ C (M P ) does not depend on q. This implies the following Lemma.

Lemma 3.37. For all N ≥ 1, g ≥ 0, l ≥ 1, and P ∈ X l , we have the following properties.

(i) (Traciality) For all Q ∈ X , M (g),N 0,l (P 1 , . . . , P l-1 , P l Q) = M (g),N 0,l (P 1 , . . . , P l-1 , QP l ) .

(ii) (Symmetry) For all permutation σ ∈ S l , M (g),N 0,l (P 1 , . . . , P l ) = M (g),N 0,l (P σ(1) , . . . , P σ(l) ) .

(iii) (Simplification) We have

M (g),N 0,l (P 1 , . . . , P l-1 , u * P l u) = M (g),N 0,l
(P 1 , . . . , P l ) .

(iv) (Conjugation) We have

M (g),N 0,l (P * 1 , . . . , P * l ) = M (g),N 0,l
(P 1 , . . . , P l ) .

Proof. Consider the series

G( ) = (-1) m+l g≥0 2g C∈C g,[2m], P ,γ -1 P C is connected (-1) c(φ C ) tr φ C (M P ) ,
where the polynomials in the tuple P P are evaluated at the matrices A M 1 , (A M 1 ) * , . . . , A M 2m , (A M 2m ) * . Proposition 3.31 implies that G(1/qM ) = WN 0,l (P ). Thus, as the renormalized cumulant under the Haar measure WN 0,l = N l-2 W N 0,l satisfies all four properties, and the set {1/qM } q≥1 has an accumulation point, we get the result.

Formal topological expansion

When the potential V is not zero, we expect to have an expansion of the free energy as in Proposition 3.31. Let us now consider a potential of the form V = k i=1 z i q i , with z = (z 1 , . . . , z k ) ∈ C k and q = (q 1 , . . . , q k ) ∈ X k . Proposition 3.31 motivates the introduction of the formal series

F N,f V = g≥0 1 N 2g n∈N k z n n! (-1) deg qn C∈C g,[2 deg qn ], qn ,γ(qn ) -1 C is connected (-1) c(φ C ) tr φ C (M qn ) , ( 14
)
where we use the notation q n = (q 1 , . . . , q 1 n1 times , . . . , q k , . . . , q k n k times

) for n = (n 1 , . . . , n k ), as well as

z n = k i=1 z ni i and n! = k i=1 n i !.
Similarly, we introduce formal series corresponding to the cumulants. Definition 3.38. Let N ∈ N * , P = (P 1 , . . . , P l ) ∈ X l be monomials with m = 1 2 deg P . The formal cumulant of P is the formal series

M N V,l (P 1 , . . . , P l ) = g≥0 1 N 2g M (g),N
V,l (P 1 , . . . , P l ),

where the g-th term is

M (g),N V,l (P 1 , . . . , P l ) = n∈N k z n n! (-1) deg qn+deg P C∈C g,[deg qn +deg P ], qn P ,γ(qn P ) -1 C is connected (-1) c(φ C ) tr φ C (M qnP ),
where q n P is the concatenation of the two tuples q n and P .

At this point, it is not clear whether the series M (g),N

V,l (P 1 , . . . , P l ) converge. It will be shown in Section 4.3.

In Section 6, we will show that in the asymptotic regime, the cumulant W N V,l (P 1 , . . . , P l ) coincides with the formal cumulant up to an arbitrary order, for z small enough.

Alternated polynomials and Hurwitz numbers

In this section, we consider a particular case, that is we assume that all polynomials are alternated monomials (see Definition 3.39). In particular, this covers the case of a potential of the form V = zAU N B(U N ) * encountered in the HCIZ integral. In [START_REF] Goulden | Monotone Hurwitz Numbers and the HCIZ Integral[END_REF], the HCIZ integral had been expressed in terms of monotone double Hurwitz numbers. In the multimatrix case, results relating the more general tensor HCIZ integral to the Hurwitz numbers have been obtained in [START_REF] Collins | The tensor Harish-Chandra-Itzykson-Zuber integral I: Weingarten calculus and a generalization of monotone Hurwitz numbers[END_REF].

Here we consider only the case where we have a single unitary matrix.

Definition 3.39. A monomial P ∈ A is said to be alternated if it can be written

P = B 1 uC 1 u -1 • • • B m uC m u -1 , with B i , C i , 1 ≤ i ≤ m words in a 1 , a * 1 , .
. . , a p , a * p . In this section, we will assume that all the polynomials involved (P 1 , . . . , P l , q 1 , . . . , q k ) are alternated monomials. We write as before P = (P 1 , . . . , P l )

In this case, = (+1, -1, +1, -1, . . .), and we have γ P ( -1 (+1)) = -1 (-1) and γ P ( -1 (-1)) = -1 (+1). Thus, γ P ∈ S ( ) 2m . We define γ = γ 2 P | -1 (+1) . In particular, this implies that for all C ∈ C g,[2m], ,γ -1 P , we have φ C ( -1 (+1)) = -1 (+1) and φ C ( -1 (-1)) = -1 (-1). That is, we can write φ C as a product of two permutations, one, ρ C , having its support in -1 (+1), and the other, σ C , having its support in -1 (-1).

Write τ C = (τ 1 , . . . , τ r ). We thus notice that the group generated by γ P , φ C , τ 1 , . . . τ r , satisfies the following equations.

γ P , π C , τ 1 , . . . , τ r = γ P , φ C , τ 1 , . . . , τ r = γ P , σ C , ρ C , τ 1 , . . . , τ r = γ P , γ -1 P σ C γ P , ρ C , τ 1 , . . . , τ r .
Now, we remark that this subgroup of S 2m is transitive if and only if the subgroup γ, γ -1 P σγ P , ρ, τ 1 , . . . , τ r of S( -1 (+1)) is transitive.

This remark allows us to rewrite the sum of Definition 3.33,

W (g),N 0,l (P 1 , . . . , P l ) = (-1) m C∈C g,[2m], P γ -1 P C connected (-1) c(φ C ) tr φ C (M P ) = (-1) m σ,ρ∈Sm τ ∈ -→
Wg(Id,ρ -1 γσ) γ,σ,ρ,τ1,...,τr transitive (-1) c(σ)+c(ρ) tr ρ (B P ) tr σ (C P ) . Definition 3.40. Let ρ, γ, σ ∈ S m . The r-th monotone triple Hurwitz number associated to ρ, γ, σ, denoted by

- → h r (ρ, γ, σ), is the number of r-uple of transpositions (τ 1 , . . . , τ r ) ∈ S r m such that • τ r • • • τ 1 = ργσ; • val(τ 1 ) ≤ val(τ 2 ) ≤ • • • ≤ val(τ r );
• the group γ, ρ, σ, τ 1 , . . . , τ r ⊂ S m is transitive.

When g satisfies the Euler equation

2 -2g = c(γ) + c(ρ) + c(σ) -r -m, we set - → h g (γ, σ, ρ) = - → h r (γ, σ, ρ).
This gives us the following Proposition.

Proposition 3.41. Let P = (P 1 , . . . , P l ) be alternated monomials. We have

W (g),N 0,l (P 1 , . . . , P l ) = (-1) m σ,ρ∈Sm (-1) c(σ)+c(ρ) tr ρ (B P ) tr σ (C P ) - → h g (ρ -1 , γ, σ). ( 15
)
Remark 3.42. In the case of the HCIZ integral, we have γ = Id, thus the monotone triple Hurwitz numbers reduce to the monotone double Hurwitz numbers.

Remark 3.43. Notice that when all the polynomials are alternated, all the white vertices in the unitary type maps involved are alternated vertices (see Definition 3.12).

Tutte-like equations

We will now state induction relations that applies to the sums of maps M (g),N 0,l defined in Definition 3.33. They are obtained by a procedure very similar to the one used by Tutte in [START_REF] Tutte | On the enumeration of planar maps[END_REF]. These induction relations are the analog of the topological recursion for matrices of the GUE [START_REF] Eynard | Algebraic methods in random matrices and enumerative geometry[END_REF].

Similar induction relations have been obtained for maps related to the Gaussian case in [GMS07] and [START_REF] Maurel-Segala | High order expansion of matrix models and enumeration of maps[END_REF], and for maps with "dotted edges" in the unitary case for g = 0 in [START_REF] Collins | Asymptotics of unitary and othogonal matrix integrals[END_REF].

More precisely, we will prove the following theorem. 0,l-1 (P 1 , . . . , P j-1 , P j+1 , . . . , P l-1 , RQuP l u)

+ P l =Qu * R M (g-1),N 0,l+1 (P 1 , . . . , P l-1 , Q, R) + g1+g2=g I [l-1] M (g1),N 0,|I|+1 (P | I , Q)M (g2),N 0,l-|I| (P | I c , R) + l-1 j=1 Pj =Qu * R M (g),N
0,l-1 (P 1 , . . . , P j-1 , P j+1 , . . . , P l-1 , RQP l ),

where we use the notation P | I = (P i ) i∈I and we set by convention, M (-1),N 0,l = 0 and M (g),N 0,0 = 0.

With a similar proof, we can state a similar theorem for P = (P 1 , . . . , P l u * ). Equivalently, this is a consequence of the invariance by conjugation of the sums of maps, see Lemma 3.37.

In the Section 4.1, we will describe a procedure to cut maps of unitary type into one or more maps of unitary types, or equivalently to decompose the permutations describing a particular map, in order to prove Theorem 4.1.

First, we show how to rewrite these equation in a compact way. We extend by linearity M (g),N 0,l to the tensor space

A ⊗l = A⊗ C • • •⊗ C A.
Recall that A is the algebra of noncommutative polynomials in the variables u, u * , a 1 , a * 1 , . . .. We can then rewrite Theorem 4.1 using the notion of non-commutative derivative.

Let P = (P 1 , . . . , P l ) be a k-tuple of polynomials, and

I = {i 1 < i 2 < • • • < i p } be a non-empty subset of [l]
, then we define

P I = P i1 ⊗ P i2 ⊗ • • • ⊗ P ip .
We define the operation as follows. Let P ∈ A l , I ⊂ [l -1], and

Q = Q 1 ⊗ Q 2 ∈ A ⊗2
, then we set

P I ⊗ P I c Q = P I ⊗ Q 1 ⊗ P I c ⊗ Q 2 .
We extend this definition by linearity to any tensor Q ∈ A ⊗ C A.

Definition 4.2. The non-commutative derivative ∂ : A → A ⊗2 with respect to u of a monomial P ∈ A is defined by

∂P = P =QuR Qu ⊗ R - P =Qu -1 R Q ⊗ u -1 R ∈ A ⊗2 .
The definition extends by linearity to any polynomial in A.

Definition 4.3. The cyclic derivative D : A → A with respect to u of a monomial P ∈ A is defined by

DP = P =QuR RQu - P =Qu -1 R u -1 RQ.
The definition extends by linearity to any polynomial in A.

Theorem 4.1 allows us to rewrite the induction relations as follows.

Corollary 4.4. For m ≥ 2, g ≥ 1, and P 1 , . . . , P l ∈ A, we have the following equation

I⊂[l-1] g=g1+g2 M (g1),N 0,|I|+1 ⊗ M (g2),N 0,|I c |+1 (P I ⊗ P I c ∂P l ) = -M (g-1),N 0,l+1 (P 1 ⊗ • • • ⊗ P l-1 ⊗ ∂P l ) - l-1 i=1 M (g),N 0,l-1 (P 1 ⊗ • • • ⊗ Pj ⊗ • • • ⊗ (DP i )P l ), (16)
where Pj means that the factor P j is omitted.

How to cut maps

In this section, we fix two integers m ≥ 2 and g ≥ 0, a permutation ρ ∈ S 2m and

∈ E 2m = { = ( (i)) i∈[2m] ∈ {±1} 2m : 2m i=1 (i) = 0}
. By Lemma 3.34, we can assume that (2m) = +1. We consider a map of unitary type C ∈ C g,m,ρ, , with r black vertices. Let S denote the underlying surface of the map C.

By Theorem 3.26, this map is described by the permutation π := π C and the tuple of transpositions τ C = (τ 1 , . . . , τ r ) ∈ -→ W r (π ( ) ), with r related to g, π and ρ by Euler's formula, see (13). We will consider two ways of cutting this map, depending on whether τ r (2m) = 2m or not.

Remark 4.5. We can also see vertices as "holes" in the surface, that is, we take the underlying surface S to be a surface with boundaries. A vertex is then a boundary component (homeomorphic to a circle) of the surface S. An edge is then a path connecting two boundary components. See Figure 10 for an example. We will see white vertices as boundary components of the underlying surface, as explained in Remark 4.5.

First case: τ r (2m) = 2m

In this case, the half-edge 2m is connected to another white half-edge, say the j-th one. Note that by our assumption that (2m) = +1, (j) = -1. Notice that because C is non-decreasing, τ r (2m) = 2m implies that for all i, τ i (2m) = 2m.

We construct a map of unitary type C from C using the following procedure, depicted in Figure 11.

1. We choose a path η in the face f at the right of the half-edge 2m. This path is chosen to start from the white vertex w 2m , attached after the half-edge 2m, and end at w j , attached after the half-edge j. As faces are homeomorphic to disks, there is only one way to choose η up to homotopy.

2. We remove the edge containing the half-edges j and 2m.

3. We cut the surface along η. Depending on the cases we connect two distinct boundary components of S, or we connect one boundary component to itself.

Remark 4.6. Notice that if w j and w 2m are distinct vertices, this surgery is the usual contraction of an edge. Furthermore, if C is non-decreasing, then so is C .

Proof. We need to check that each face of C is homeomorphic to a disk. We only modify the faces f left and f right at the left and the right of the edge (w 2m , w j ). At step 2, when we remove the edge, we connect f left and f right . However, at step 3, we cut along a path homotopic to the edge, thus separating the two faces. All the faces of C thus remain disks. Furthermore, these two faces are incident to a white vertex, the one composed by the cut for instance.

The map C has 2m -2 labelled half-edges (maybe 0 if m = 1). The black vertices have not been modified when transforming C into C . As we have seen that all faces are incident to a white vertex, C is of unitary type, with labelling set as in the statement of the Lemma.

As the black vertices are not modified, a non-decreasing map remain non-decreasing.

Let us now compute the permutations that represent C . Let

I j = [2m -1] \ {j}.
Lemma 4.9. Let π := Tr(π; I j ). We have π C = π = π| Ij .

Proof. We have assumed that the half-edges 2m and j are connected to form an edge. This imply π(2m) = j and π(j) = 2m. Thus, π = π| Ij . When removing the edge at step 2, it is clear that the map we obtain is still described by π C , with a cycle removed. When cutting the map at step 3, we do not modify the further.

Lemma 4.10. Let ρ := Tr(ρ(j 2m); I j ). We have ρ C = ρ .

Proof. Assume first that w j and w 2m are two distinct vertices. Let c = (u 1 . . . u p j) and c = (u 1 . . . u p 2m) be the cycles that represent them. After cutting the map at step 3, the vertices are replaced by a vertex with structure (u 1 . . . u p u 1 . . . u p ) = Tr(cc (j 2m); I j ).

If w j = w 2m , this vertex is represented by a cycle c = (u 1 . . . u p j u 1 . . . u p 2m), which we cut using the transposition (j 2m). We obtain two vertices represented by the two cycles Tr(c(j 2m); I j ).

Lemma 4.11. We have φ C = Tr(φ C ; I j ).

Proof. By Lemmas 3.23, 4.9 and 4.10,

φ C = ρ -1 π -1 = Tr(ρ(j 2m); I j ) -1 π| -1 Ij = Tr (j 2m)ρ -1 ; I j -1 π| -1 Ij .
Notice first that Tr ρ -1 π -1 ; I j = Tr (j 2m)ρ -1 π -1 (j 2m); I j = Tr (j 2m)ρ -1 π -1 ; I j . Then, as π (j) = j and π (2m) = 2m, we have Tr (j 2m)ρ -1 π -1 ; I j = Tr (j 2m)ρ -1 ;

I j π -1 = φ C .
Lemma 4.12. If the map of unitary type C is connected, then the map C has one or two connected components.

Furthermore, if j and 2m do not belong to the same cycle in ρ, C is connected.

Proof. Assume first that j and 2m belong to the same cycle in ρ. This means that w j = w 2m . If we erase the edge containing the half-edges 2m and j, C stays connected. However, when we cut the map along the path η, we may separate the map into two connected components. More precisely, we separate the map into two connected components if and only if η is homologically trivial, that is, the boundary of a surface embedded in S.

If j and 2m belong to different cycles, that is w j = w 2m , then when removing the edge we may disconnect the two vertices but we then merge them. Consequently, the map C is connected.

Using the permutations ρ = ρ C and φ C , and Lemma 4.12, we can now compute the genus of C . We recall Euler's formula for a map of genus g C with C C connected components

2C C -2g C = c(ρ C ) + c(φ C ) -m -r.
Notice first that c(φ C ) = c(φ C ) if and only if both j and 2m are not fixed points of φ C . The integer j (respectively 2m) is a fixed point of φ C if and only if ρ(2m) = j (respectively ρ(j) = 2m). In this case, (j 2m)ρ(j) = j (respectively (j 2m)ρ(2m) = 2m) and when taking the trace on I j we remove one (or two) cycles of (j 2m)ρ. Furthermore, C is connected.

In particular, if both j and 2m are fixed points of φ C then it means that C is reduced to a vertex with 2 half-edges. We will assume in what follows that m ≥ 2 It gives us one particular case:

1. if j or 2m is a fixed point of φ C , then c(φ C ) = c(φ C ) -1 and c(ρ ) = c(ρ). Thus, g C = g C .

If both j and 2m are not fixed points of φ C , we have the three cases.

2. If j and 2m belong to the same cycle of ρ, and C is connected, then g = g -1.

3. If j and 2m belong to the same cycle of ρ, and has two connected components, then g = g.

4. If j and 2m belong to two different cycles of ρ, then g = g.

4.1.2 Second case: τ r (2m) = 2m

In this case, the white half-edge labelled 2m is connected to a black vertex. Let j = τ r (2m) ∈ -1 (+1). In that case, the last black vertex has an ingoing edge labelled on the left by 2m.

We construct a unitary map C from C using the following procedure, depicted in Figure 12.

1. We choose two paths η 1 and η 2 contained respectively in the face f 2m at the left of the half-edge 2m, and f j at the left of the half-edge j. The path η 1 (respectively η 2 ) is chosen to start from the white vertex w 2m (respectively w j ), attached just after the half-edge 2m (respectively j), and end at the r-th black vertex, attached just after the ingoing edge labelled 2m (respectively j) on the left.

2. We remove the r-th black vertex, and attach each ingoing edge to the outgoing edge that follows it in the counterclockwise order.

3. We cut the surface

S along η = η 1 ∪ η 2 . 2m j r r -1 η 2 η 1 1. 2m j r -1 η 2 η 1 2. 2m j r -1 3.
Figure 12: Second way to cut the map.

Lemma 4.13. If C is a map of unitary type with labelling set I and with r black vertices, then C is a map of unitary type with labelling set I and with r -1 black vertices. Furthermore, if C is non-decreasing, then so is C .

Proof. First, notice that when removing the black vertex, at step 2, we may have connected two faces together, or may have connected a face to itself, thus creating a "face" homeomorphic to an annulus. However, when we cut the map, at step 3, we recover one or two faces homeomorphic to disks. Thus, C is a map.

Notice that C has r -1 black vertices. We removed the last black vertex and did not create any new edge linking two black vertices, furthermore the faces we modified are incident to a white vertex (for instance the one corresponding to the cut η). Thus, C is of unitary type.

Let us now compute the permutations that represent C . Lemma 4.14. Let π = (j 2m)π = τ r π.

We have π C = π .

Proof. We only modify the edges during step 2, when we remove the black vertex. The outgoing half-edges of the r-th black vertex in C are labelled on the left by j and 2m. These half-edges are part of edges connected at their other end to white vertices, because the black vertex we remove is the last. These edges are connected respectively to the half edge π -1 (j) and π -1 (2m).

Consider the white half-edge labelled by π -1 (j). After the surgery, it is connected to the halfedge labelled 2m.

Similarly, the white half-edge labelled π -1 (2m) is attached to the half-edge labelled j. This corresponds to having π C (π -1 (j)) = 2m and π C (π -1 (2m)) = j, and π C = π for all other values. We can write this π C = (j 2m)π.

Note that we have π ( ) = (τ r πτ r π)| -1 (+1) = τ r π ( ) = τ r-1 • • • τ 1 . Thus, τ C = (τ 1 , . . . , τ r-1 ).

Lemma 4.15. Let ρ = ρ(j 2m) = ρτ r .

We have ρ C = ρ

Proof. The white vertices are only modified when we cut the map, at step 3. The proof is similar to the one of Lemma 4.10. We consider the two cases of j and 2m in the same cycle in ρ or not, and we compute ρ C = ρτ r .

It follows from Lemmas 3.23, 4.14, and 4.15, that φ C = τ r φ C τ r . In particular, c(φ C ) = c(φ C ).

We can now state the counterpart of Lemma 4.12.

Lemma 4.16. If the unitary type map C is connected, then the map C has one or two connected components. Furthermore, if j and 2m do not belong to the same cycle in ρ, C is connected.

Proof. The proof is almost the same as for Lemma 4.12. Alternatively, we can prove this lemma using Proposition 3.27. We assume that the action of G(ρ , π , τ ) on [2m] has k ≥ 1 orbits. We notice that G(ρ, π, τ C ) = ρ , π , τ 1 , . . . , τ r . The transposition τ r may connect two orbits of the action of G(ρ , π , τ ) if j and 2m do not belong in the same orbit. Thus, G(ρ, π, τ C ) has k or k -1 orbits.

In particular, if j and 2m belong to the same cycle of ρ (or different cycles of ρ), they belong to the same orbit and the action of G(ρ, π, τ C ) has k orbits.

As we assumed that C is connected, by Proposition 3.27, the action of G(γ, π, τ C ) has one orbit, so k may be 1 or 2.

Using Lemmas 4.16, 4.15 and the remark on φ C , we can compute the genus g of C using Euler's formula. There are three cases.

• If j and 2m belong to the same cycle in γ (i.e. c(γ ) = c(γ) + 1) and C has two connected components, then g = g.

• If j and 2m belong to the same cycle in γ and C is connected, then g = g -1.

• If j and 2m belong to two different cycles in γ (i.e. c(γ ) = c(γ) -1), then g = g .

Proof of Theorem 4.1

We can now turn to the proof of Theorem 4.1.

Proof. Fix γ = γ P ∈ S 2m , = P , and M = M P . Assume first that m = 1 2 deg P ≥ 2. We decompose the sum

M (g),N 0,l (P 1 , . . . , P l ) = (-1) m C∈C g,[2m], ,γ -1 C connected (-1) c(φ C ) tr φ C (M )
in two sums, each corresponding to one of the two cases of the previous construction. We introduce the set W f 2m , of monotone walks whose last step τ satisfy τ (2m) = 2m, and the set W c 2m of monotone walks whose last step τ satisfy τ (2m) = 2m. The sum corresponding to the first case, is thus by the previous surgery of Section 4.1

(-1) m C∈Cg,m,γ, C connected (-1) c(φ C ) tr φ C (M )1 W f 2m (τ C ) = (-1) m π∈S ( ) 2m τ ∈ -→ W r(g,m,γ,π) (π ( ) ) G(γ,π,τ ) is transitive (-1) c(γπ -1 ) tr γπ -1 (M )1 W f 2m (τ ) = (-1) m j∈ -1 (-1) π ∈S ( ) (Ij ) π=(j 2m)π τ ∈ -→ W r(g,m,γ,π) (π ( ) ) G(γ,π,τ ) is transitive (-1) c(γπ -1 ) tr γπ -1 (M ),
where r(g, m, γ, π) = c(γ) + c(γ -1 π -1 ) -m + 2g -2 according to (13), and we used the fact that in the first case π can be rewritten π (j 2m) for some j ∈ -1 (-1).

We rewrite this as a sum of four terms, corresponding to the different ways of computing the genus, as explained in the last section. We interpret the new sums as series M N g ,l ,0 (Q 1 , . . . , Q l ), with Q 1 , . . . , Q l monomials either in X or of degree 0. We introduce the notation Q = (Q 1 , . . . , Q l ). These monomials are chosen so that the combinatorial data γ , and described in the last section, and the tuple M of appropriate monomials of degree 0 is such that γ Q = γ , q = , and M Q = M . The tuple M is chosen differently depending on the subcase, but always so that tr φ C (M ) = tr C (M ) (except for subcase 1., see below).

There are four cases. Let us consider first the terms corresponding to subcases 1. and 3., which are 1. j or 2m is a fixed point of φ C ; 3. j and 2m are not fixed points of φ C , both belong to the same cycle of η C = γ -1 , and C has two connected components.

In those two cases, the map C is cut into two maps, with total genus equal to g. The case 1. corresponds to the degenerate case where one of the two maps has no edges, and is reduced to a vertex. We associate to it the weigth tr(M j ) or tr(M 2m ).

Together, these cases account for the term

- P l =Qu -1 Ru g1+g2=g I⊂[l-1] M (g1),N 0,|I|+1 (P | I , Q)M (g2),N 0,|I c |+1 (P | I c , R).
The subcase 1. corresponds to the term for which Q or R in the sum is reduced to a monomial of degree 0, and the subcase 3. to the other terms. When cutting the map, we obtain two connected components, each containing a vertex corresponding to part of P l . This correspond to the fact that in the argument of the series, P l is replaced by two monomials Q and R such that Qu -1 Ru, and one u and one u -1 are removed, corresponding to the two removed half-edges. Similarly, the subcase 2. j and 2m are not fixed points of φ C , both belong to the same cycle of ρ C = γ -1 , and C is connected corresponds to the term

- P l =Qu -1 Ru M (g-1),N 0,l+1 (P 1 , . . . , P l-1 , Q, R).
The subcase 4. j and 2m are not fixed points of φ C , and they belong to different cycles of ρ C = γ -1 , corresponds to the term

- l-1 i=1 Pi=Qu -1 R P l =P l u M (g),N
0,l-1 (P 1 , . . . , P i-1 , P i+1 , . . . , P l-1 , RQP l ).

Here, two vertices are glued together, corresponding to replacing two polynomials in the argument of the series by one: RQP l . We proceed similarly for the terms that correspond to the second case where τ (2m) = 2m. The corresponding sum is

(-1) m C∈C g,[2m], ,γ -1 C connected (-1) c(φ C ) tr φ C (M )1 W c 2m (τ C ) = (-1) m π∈S ( ) 2m τ ∈ -→ W r(g,m,γ,π) (π ( ) ) G(γ,π,τ ) is transitive (-1) c(γπ -1 ) tr γπ -1 (M )1 W c 2m (τ ) = (-1) m j∈ -1 (+1) j =2m π ∈S ( ) 2m (τ1,...,τr-1)∈ -→ W r-1 (π ( ) ) G(γ ,π ,τ ) is transitive (-1) c(γ π -1 ) tr γ π -1 (M (j 2m) ),
where γ = (j 2m)γ, M (j 2m) = (M (j 2m)(1) , M (j 2m)(2) , . . . , M (j 2m)(2m) ), τ = (τ 1 , . . . , τ r-1 , (j 2m)), and r = r(g, m, γ, (j 2m)π ). To go from the second to the third line, we replaced π by π = (j 2m)π.

Following the construction from last section, we get three kinds of terms corresponding to the three subcases from last section.

The first subcase is 1. j and 2m belong to the same cycle in ρ C = γ -1 , and C has two connected components.

It corresponds to the sum

P l =QuRu g1+g2=g I⊂[2m] M (g1),N 0,|I|+1 (P | I , Qu)M (g2),N 0,|I c |+1 (P | I c , Ru).
The second subcase 2. j and 2m belong to the same cycle in ρ C = γ -1 , and C is connected, corresponds to

P l =QuRu M (g-1),N 0,l+1
(P 1 , . . . , P l-1 , Qu, Ru).

Finally, the subcase 3. j and 2m belong to different cycles in ρ

C = γ -1 , corresponds to l-1 i=1 Pi=QuR M (g),N
0,l-1 (P 1 , . . . , P i-1 , P i+1 , . . . , P l-1 , RQuP l ).

Putting all the terms together, we get the induction relation of Theorem 4.1.

Induction relation for the series M

(g),N V,l
We first prove that the series M (g),N

V,l (P ) exist with a radius of convergence that depend on g, l, and V . To that end, we show bounds on the series of maps for V = 0 that are a consequence of Theorem 4.1. Similar bounds have been obtained in the Gaussian case in [MS06, Lemma 4.3].

Proposition 4.17. Assume that for all N ≥ 1 and all 1 ≤ i ≤ p we have A N i ≤ 1. Let q = (q 1 , . . . , q k ) ∈ X k n be monomials, and ν = max 1≤i≤k deg q i . We introduce the n-th Catalan number c n = 1 n+1 2n n . There exists constants A k > 1, B k > 1, and C k > 1 that depend on k, and D k,ν > 1 that depends on k and ν such that for all P = P 1 , . . . , P l ∈ X l n , and all n = (n 1 , . . . , n k ) ∈ N k , we have the bound

1 n! |M (g),N 0, i ni+l (q 1 , . . . , q 1 n1 times , . . . , q k , . . . , q k n k times , P 1 , . . . , P l )| ≤ A l(m+νn) k B -l k C g(m+νn) D n i c deg P i k j=1 c nj , (17)
where m = deg P . The constants can be chosen to be

A k = C k = √ 6π 1/4 2 k+3 B k = 3 • 4 k+1 D k,ν = 4k(4e 1/e ) ν .
The proof is given in Appendix A. The value of the constants can be improved. These bounds allow us to prove immediately that the series M (g),N V,l (see Definition 3.38) converge.

Corollary 4.18. Let P = (P 1 , . . . , P l ) ∈ X l n , q = (q 1 , . . . , q k ) ∈ X k n and z = (z 1 , . . . , z k ), and let V = k i=1 z i q i be a potential. As a series in z, M (g),N

V,l (P 1 , . . . , P l ) converges absolutely with radius of convergence R l,g,V ≥ (4A l+g k D k,ν ) -1 .

We can now turn to the induction relations. The induction relation from Theorem 4.1 translates to an induction relation on the series M (g),N V,l . Proposition 4.19. Let P = (P 1 , . . . , P l ) ∈ (X n ) l , q = (q 1 , . . . , q k ) ∈ (X n ) k and z = (z 1 , . . . , z k ), and let V = k i=1 z i q i be a potential. Assume that for all

1 ≤ i ≤ k, |z i | < R l,g,V . For all 1 ≤ i ≤ n, we have the equation g1+g2=g I⊂[l-1] M (g1),N V,|I|+1 ⊗ M (g2),N V,|I c |+1 (P I ⊗ P I c ∂P l ) + M (g),N V,l (P 1 ⊗ • • • ⊗ P l-1 ⊗ (DV )P l ) = -M (g-1),N V,l+1 (P 1 ⊗ • • • ⊗ P l-1 ⊗ ∂P l ) - l-1 j=1 M (g),N V,l-1 (P 1 ⊗ • • • ⊗ P j-1 ⊗ P j+1 ⊗ • • • ⊗ P l-1 ⊗ (DP j )P l ) . (18)
• each half-edges connected to a white vertex is colored in one of the n colors;

• each edge is composed of two half-edges of the same color;

• if an oriented edge connects the vertex of color i numbered l 1 to the vertex of color i numbered l 2 then l 1 < l 2 . Notice that if we "erase" the colors of a multicolored unitary map, that is, if we turn each edge and vertex of color i ∈ [n] into black, we obtain a (monocolored) map of unitary type. In particular, we define similarly labels of all the half-edges.

As in Section 3.2, we define for a multicolored map of unitary type C, with n colors, the following permutations.

We construct permutations ρ C , π C , and φ C , and the tuple C , as for a monocolored map of unitary type. If the i-th labelled half-edge is of color j, we set t C (i) = j. We then define J C,i = t -1 C (i). We set C,i = C | J C,i for all 1 ≤ i ≤ k.

For each color i ∈ [n], we consider the edges of this color. We then define as previously a permutation π C,i ∈ S ( C,i ) (J C,i ) describing these edges and the vertices of color i. Finally, if we consider the vertices of color i, we can associate to the j-th vertex of color i the transposition τ i,j as previously. We set τ

C = (τ i,j , i ∈ [n], j ∈ [r i ]).
Notice that by construction, we have π

C = π C,1 π C,2 • • • π C,n .
Definition 5.6. Let n ≥ 1 and g ≥ 0 be integers, and I be a finite subset of the positive integers. Let r = (r 1 , . . . , r n ) ∈ N n , γ ∈ S(I), t : I → [n] and : I → {±1}. We denote by C r I, ,ρ,t the set of multicolored maps of unitary type C with n colors, with label set I, and with r i vertices of color i, for 1 ≤ i ≤ n, such that ρ C = ρ, C = , and t C = t.

We denote by C g,I, ,ρ,t the set of multicolored maps of unitary type C with n colors, with label set I, and of genus g, such that ρ C = ρ, C = , and t C = t.

We then have the analog of Theorem 3.26 Theorem 5.7. Let n ≥ 1 be an integer, and I be a finite subset of the positive integers. Let r = (r 1 , . . . , r n ) ∈ N n , ρ ∈ S(I), t : I → [n] and :

I → {±1}. Define J i = t -1 (i) and i = | Ji for 1 ≤ i ≤ n.
The previous construction gives a bijection between C r I, ,ρ,t and

π1∈S ( 1 ) (J1),...,πn∈S ( n) (Jn) n i=1 {π i } × -→ W ri (π ( i) i
).

Proof. The proof is very similar to the one of Theorem 3.26. By considering each color, we prove that the construction does give a map C r I, ,ρ,t → π1∈S ( 1 ) (J1),...,πn∈S ( n ) (Jn)

n i=1 {π i }× -→ W ri (π ( i) i
). We can construct its inverse exactly as in the proof for the case with one unitary matrix, by constructing the edges for the color 1, then for the color 2, etc.

It follows directly by erasing the colors and Proposition 3.27 that we have the following proposition.

Proposition 5.8. Let C be a multicolored map of unitary type with n colors. The map C is connected if and only if the group ρ

C , π C,1 , . . . , π C,n , τ i,j , 1 ≤ i ≤ n, 1 ≤ j ≤ r i is transitive, with τ C = (τ i,j , i ∈ [n], j ∈ [r i ]).
Using Proposition 2.14, 5.3, and 5.7, we can compute the moments with no potential (for N ≥ m = 1 2 deg P ). Let P = (P 1 , . . . , P l ) ∈ (X n ) l , we have α N U ,0,l (P 1 , . . . , P l ) = N -m π1∈S ( P ,1 ) (J1) π2∈S ( P ,2 ) (J2)

••• πn∈S ( P ,n ) (Jn) r1,...,rn≥0 -1 N r n i=1 - → w ri (π ( i) i ) Tr γ P π -1 1 •••π -1 n (M P ) = N -m r∈N k C∈C r [2m], P ,γ -1 P ,t -1 N r Tr γπ -1 1 •••π -1 n (M P ), (21)
where we use the notation x r = x i ri , for any x ∈ R.

We then compute the cumulants for no potential, when N ≥ m, W N U N ,0,l (P 1 , . . . , P l ) = N -m r∈N n C∈C r

We now rewrite this sum using the genus of the maps rather than the number of colored vertices. In this context, the Euler formula becomes

2 -2g C = c(γ C ) + c(φ C ) -m - k i=1 r i .
We thus get the renormalized cumulant WN (23)

Scalar product and parametric norms on A n

Following [START_REF] Guionnet | Asymptotics of unitary multimatrix models: The Schwinger-Dyson lattice and topological recursion[END_REF], we introduce some useful notions. The vector space A -the algebra of noncommutative polynomials -admits a countable basis, which is the set of all monomials. Let • , • be the scalar product that makes this basis orthonormal. In particular, B ⊥ is the algebra generated by the polynomials with no constant term, i.e. without factors u i or u * i . Definition 6.1. Let ξ ≥ 1. The ξ-norm is • ξ defined by

P ξ = Q∈A monomial | P, Q |ξ deg Q , for P ∈ A.
Example 6.2. An important case is the 1-norm. For instance the 1-norm of the potential we consider is

V 1 = k i=1 |z i |.
We write B ⊥ ξ the completion of the algebra B ⊥ in the ξ-norm • ξ . This notion of norm allows us to define the parametric ξ-norm of a linear operator or form. A particularly important sort of linear forms are tracial states.

Definition 6.4. Let C be a unital * -algebra. A tracial state on C is a linear form τ : C → C such that for any P, Q ∈ C, we have

• τ (Id) = 1;

• τ (P Q) = τ (QP );

• τ (P P * ) ≥ 0.

We say a tracial state on A n or B is bounded if for any 1 ≤ i ≤ p, and any j ≥ 0, we have τ (a i a * i ) j ≤ 1.

Remark 6.5. The normalized trace tr is a tracial state on B. Under Hypothesis 1.2, it is bounded. In that case, the Cauchy-Schwarz inequality implies that tr 1 = 1.

Assuming Hypothesis 1.1, we thus have that WN V,1 is a tracial state on A n , with WN V,1 1 = 1. In the third line we used the recurrence formula for Catalan numbers c n+1 = n i=0 c i c n-i and in the fourth line we used that c n+1 ≤ 4c n for all n ∈ N. We choose A and C so that A/C ≤ 1 and B ≥ 12. C -m1 -C -m2 ≤ C gm .

2.

I⊂[l-1] n1+n2=n

Similarly, we have

I⊂[l-1] A m1(|I|+1)+m2(|I c |+1) = A ml I⊂[l-1] A -m1|I c |-m2|I| ≤ A ml l-1 i=0 l -1 i 1 A deg P u-m i 1 A m l-i-i = A ml ( 1 A deg P u-m + 1 A m ) l-1 ≤ A ml .
We finally get It implies that for p, q ∈ N * , c p+q c p c q ≤ π 1/2 (p + 1)(q + 1) p + q As we can assume that m ≥ 2 (else this term could be bounded by 0 as one of the P i , 1 ≤ i ≤ l -1 would be of degree 0), it suffices to choose A ≤ 2B 1/2 π 1/4 2 3/2 . Notice that for all n ≥ 1, (n + 1) 3/2 ≤ 2 3n/2 . 4. We choose D = 4k(4e 1/e ) ν to get the result. Notice that we can thus choose

I⊂[l-1] n1+n2=n g1+g2=g 1 n 1 ! 1 n 2 ! |M (
A = C = 2 k+3 √ 6π 1/4 B = 3 • 4 k+1 D = 4k(4e 1/e ) ν .

B The gradient trick

We use several times the gradient trick, previously introduced in [START_REF] Guionnet | Asymptotics of unitary multimatrix models: The Schwinger-Dyson lattice and topological recursion[END_REF].

The main idea of the gradient trick is to replace the polynomial P (or P l ) the equations of Proposition 6.6 (or in the Dyson-Schwinger problem (25), see Section 6) by its cyclic derivative D i P . An operator -the master operator introduced below -naturally appears in the equations. When the potential V is small enough, this operator is invertible. The gradient trick was introduced in [START_REF] Guionnet | Asymptotics of unitary multimatrix models: The Schwinger-Dyson lattice and topological recursion[END_REF] to study the Dyson-Schwinger lattice of equations.

We use a slightly modified version of [GN15, Proposition 17].

Proposition B.4. Let 1 ≤ ξ 1 < ξ 2 , and τ a linear form A n → C. We have Tτ ξ2 ≤ 2 τ ξ1 ξ 1 ξ 2 -ξ 1 .

Proof. We proceed as in [START_REF] Guionnet | Asymptotics of unitary multimatrix models: The Schwinger-Dyson lattice and topological recursion[END_REF]. Let P be a monomial of degree d ≥ 1. We have

T τ P = n i=1 P =P1uiP2   P2P1ui=Q1uiQ2ui (Q 1 u i τ (Q 2 u i ) + τ (Q 1 u i )Q 2 u i )   - n i=1 P =P1uiP2   P2P1ui=Q1u -1 i Q2ui (Q 1 τ (Q 2 ) + τ (Q 1 )Q 2 )   - n i=1 P =P1u -1 i P2   u -1 i P2P1=u -1 i Q1uiQ2 (Q 1 τ (Q 2 ) + τ (Q 1 )Q 2 )   + n i=1 P =P1u -1 i P2   u -1 i P2P1=u -1 i Q1u -1 i Q2 (u -1 i Q 1 τ (u -1 i Q 2 ) + τ (u -1 i Q 1 )u -1 i Q 2 )   .
Using the triangle inequality and |τ (P )| ≤ τ ξ1 ξ deg P 1 , we get

T τ P ξ2 τ ξ1 ≤ n i=1 P =P1uiP2   P2P1ui=Q1uiQ2ui (ξ deg i Q1ui 2 ξ deg i Q2ui 1 + ξ deg i Q1ui 1 ξ deg i q2ui 2 )   + n i=1 P =P1uiP2   P2P1ui=Q1u -1 i Q2ui
(ξ

deg i Q1 2 ξ deg i Q2 1 + ξ deg i Q1 1 ξ deg i Q2 2 )   + n i=1 P =P1u -1 i P2   u -1 i P2P1=u -1 i Q1uiQ2
(ξ

deg i Q1 2 ξ deg i Q2 1 + ξ deg i Q1 1 ξ deg i Q2 2 )   + n i=1 P =P1u -1 i P2   u -1 i P2P1=u -1 i Q1u -1 i Q2
(ξ

deg i u -1 i Q1 2 ξ deg i u -1 i Q2 1 + ξ deg i u -1 i Q1 1 ξ deg i u -1 i q2 2 )   ≤ 2 n i=1 deg i P   deg i P -1 k=1 ξ k 2 ξ deg i P -k 1   ≤ 2d ξ 1 ξ 2 deg i P P ξ2 ≤ 2d ξ 1 ξ 2 -ξ 1 P ξ2 .

Figure 1 :

 1 Figure 1: The left and right side of a half-edge, and of an ingoing half-edge.

Figure 2 :

 2 Figure 2: A map with labelled half-edges.

  Theorem 3.11. Let m ≥ 1, σ ∈ S 2m , ∈ E 2m and C m, ,σ be the set of oriented maps with 2m labelled half-edge C such that σ C = σ and C = . Then, C m, ,σ → I ( ) 2m C → α C , is a bijection.

Figure 3 :

 3 Figure 3: A unitary type map. The numbers in red are the numbers of the black vertices, the labels in black are the labels of the white half-edges.

Figure 4 :

 4 Figure 4: Procedure to assign labels to half-edgesThe newly labelled half-edges are in blue.

Figure 5 :

 5 Figure 5: Proof of Lemma 3.23.

Figure 6 :

 6 Figure 6: Chain of edges around the face f .We haveτ np τ np-1 • • • τ n1 (k) = k p , and by construction of π C , we have π C (k) = π -1 C (k p ). Thus τ np τ np-1 • • • τ n1 (k) = π ( ) (k).

Figure 7 :

 7 Figure 7: First step of the construction of the permutation α from one transposition τ 1 = (1 3), represented as a map.

Theorem 4. 1 .(

 1 Let N ∈ N * , P = (P 1 , . . . , P l u) ∈ X l be monomials. Then, for g ≥ 0 and m = 1 2 deg P ≥ 2, we have the induction relationM P 1 , . . . , P l-1 , Qu, Ru) + g1+g2=g I⊆[l-1] M(g1),N 0,|I|+1 (P | I , Qu)M (g2),N 0,l-|I| (P | I c , Ru) -

Figure 10 :

 10 Figure 10: (a) An oriented map of genus 0 with two vertices (b) The corresponding map where vertices are seen as boundary components. The underlying surface is a cylinder.

Figure 11 :

 11 Figure 11: First way to cut the map.

Definition 4. 8 .

 8 The trace of a permutation σ ∈ S(A) on B ⊂ A, denoted by Tr(σ; B), is the permutation in S(B) defined for each x ∈ B by Tr(σ; B)(x) = σ px (x), with p x ≥ 1 the smallest integer so that σ p (x) ∈ B.

Figure 13 :

 13 Figure 13: A muticolored map of unitary type with two colors.

r

  Tr φ C (M P ).

U

  N ,0,l WN U N ,0,l (P 1 , . . . , P l ) = N l-2 W N U N ,0,l (P 1 , . . . , P l ) c(φ C ) tr φ C (M P ).

Definition 6. 3 .

 3 Let T be an operator on A and ξ, ξ ≥ 1. Its (ξ, ξ )-norm isT ξ,ξ = sup P ∈A T P ξ P ξ .When ξ = ξ we write T ξ = T ξ,ξ . Similarly, let τ : A → C be a linear form. Its ξ-norm is τ ξ = sup P ∈A |τ (P )| P ξ .

≤

  (P 1 , . . . , P l-1 , (∂P ) × 1 ⊗ u)| ≤ deg P u m =1 A (l+1)(m+νn) B -l-1 C (g-1)(m+νn) D n c m c deg P uA (l+1)(m+νn) B -l-1 C (g-1)(m+νn) D n (c deg P u+1 -c deg P u ) m+νn) B -l C g(m+νn) D n

cC=

  c |+1 |(P I ⊗ P I c #(∂P ) × 1 ⊗ u) ≤ deg P u m =1 I⊂[l-1] g1+g2=g A m1(|I|+1)+m2(|I c |+1) B -l-1 C g1m1+g2m2 c m c deg P u-m × n1+n2=n A lνn C gνn D n n1,i c n2,i ,where we used the notation m 1 = i∈I deg P i + m and m 2 = i∈I c deg P i + deg P u -m . With this notation, we get g1+g2=g C gm C -m1(g+1) -C -m2(g+1)

  c |+1 |(P I ⊗ P I c #(∂P ) × 1 ⊗ u) ≤ 3 • 4 k B A l(m+νn) B -l C g(m+νn) D n -1 (P 1 , . . . , Pj , . . . , P l-1 , (DP j )P u)| ≤ l-1 j=1 (deg P j )A (l-1)(m+νn) B -l+1 C g(m+νn) D n c deg Pj +deg P u j ) c deg Pj +deg P u c deg Pj c deg P u   A l(m+νn) B -l C g(m+νn) D nTo bound this term, we use the following estimate for the Catalan numbers, a consequence of the Stirling bound

  j ) c deg Pj +deg P u c deg Pj c deg P u   ≤ π 1/2 B A m+νn (deg P u + 1) 3/2 (m -deg P u).

(4

  ,l (P 1 , . . . , P l-1 , (Dqj )P u) deg q k )A l(m+νn) B -l C g(m+νn) D n c deg P u+deg qj c nj -1 c deg P u c deg q k (deg q k )A l(m+νn) B -l C g(m+νn) D n e ) deg q k A l(m+νn) B -l C g(m+νn) D n

Proof. We sum on n ∈ N k the induction relations of Proposition 5.9 for M (g),N 0, i ni+l (q 1 , . . . , q 1 n1 times , . . . , q k , . . . , q k n k times , P 1 , . . . , P l ), times z n n! .

The multimatrix case

Up to now, we have only considered integrals involving one Haar-distributed matrix U N . The results obtained so far can be extended in a straightforward way to the case where we have n ≥ 1 independent Haar-distributed matrices U N 1 , . . . , U N n . The polynomials we consider in the sequel are the non-commutative polynomials in u i , u -1 i , for 1 ≤ i ≤ n and a j , a * j for 1 ≤ j ≤ p. We denote this * -algebra by A n . Notice that A = A 1 .

Weingarten calculus

As previously, we will consider a subset of monomials of A n , as the quantity we consider are multilinear functions which are tracial in each of their arguments. We define X n the set of monomials of A n of the form

where

, and M = (M 1 , . . . , M d ) is a d-uple of monomials M i ∈ A n , each of them being empty or a word in a i , a * i . We define for a tuple P = (P 1 , . . . , P l ) the tuples P , t P , M P obtained by concatenating the tuples corresponding to each polynomial P i . We also define P ,i = | t -1 P (i) , i.e. the tuple which encodes the exponents of the variables U N i only. We define the degree with respect to u i of a monomial P , deg i P as the number of occurrence of u i or u -1 i in P . The total degree of a tuple is deg i P = Definition 5.1. Let P = (P 1 , . . . , P l ) ∈ (X n ) l . We define the permutation

Definition 5.2. We introduce the moment with respect to the Haar measure in the multimatrix case

where the expectation is under the product Haar measure

Proposition 5.3. Let P = (P 1 , . . . , P l ) ∈ (X n ) l and J i = t -1 P (i). We have α N U ,0,l (P 1 , . . . , P l ) =

Wg N (π

This Proposition is obtained by applying the following Lemma n times.

Lemma 5.4.

ti otherwise. Then, we have the expectation with respect to U N 1 only

Wg N (π

Proof. of Lemma 5.4 We can assume that the last factor of each polynomial P i is a u 1 or a u * 1 . Let J 1 = t -1 (1) = {p 1 < p 2 < . . . < p q }. We let γ = Tr(γ P ; J 1 ). Proposition 2.11, shows that

Wg N (π

This is equal to

Wg N (π

) Tr γ P π -1 1 ( M ).

Multicolored maps of unitary type

We now generalize the notion of a map of unitary type to address the multimatrix case.

Definition 5.5. Let I be a finite subset of N * . A multicolored map of unitary type with n colors, with labels in I, and with r i vertices of color i for 1 ≤ i ≤ n, is an oriented map with vertices colored in white or in one of n colors, and colored half-edges which can be of any of the n colors such that

• there are r i vertices of color i for 1 ≤ i ≤ n, which are alternated of degree 4 and numbered from 1 to r i ;

• the half-edges connected to a vertex of color i (which is not white) are of color i as well;

• there are |I| half-edges that are connected to white vertices. Each element of I labels exactly one of these half-edges;

The term of order 2g is then

We then define the formal cumulant as

V,l (P 1 , . . . , P l ) =

(q 1 , . . . , q 1 n1 times , . . . , q k , . . . , q k n k times , P 1 , . . . , P l ), as previously.

Induction relation

We will now deduce from the relations obtained in Section 4 similar relations in the multimatrix case.

Proposition 5.9. Let P = (P 1 , . . . , P l ) ∈ (X n ) l , i ∈ [n] and g ≥ 1.

If 1 2 deg i P ≥ 2, then we have the equation

Here ∂ i and D i are the non-commutative and cyclic derivative with respect to u i , for i ∈

This Proposition is proved as in Section 4. If no polynomial of P contains a u i then the equation is trivial.

Thus we can assume by symmetry that deg i P l ≥ 1. We cut the maps from the sum W (g),N 0,l (P ) as in Section 4.1. Notice that in this construction, we only modify edges of the color i so we can use the exact same arguments. We thus obtain the wanted equation.

The Dyson-Schwinger equation and the topological expansion

The induction equations obtained in Section 4 are related to the Dyson-Schwinger equations for unitary matrices. In this section, we introduce the Dyson-Schwinger lattice of equations for the renormalzed cumulants WN V,l = N l-2 W N V,l . Together with the induction relations derived in Section 4, they allow us to show that the renormalized cumulants WN V,l admit an asymptotic topological expansion as N → ∞. The methods used in this section are heavily inspired from [START_REF] Guionnet | Asymptotics of unitary multimatrix models: The Schwinger-Dyson lattice and topological recursion[END_REF].

The Dyson-Schwinger equations for the unitary matrices

Let σ be a tracial state on B. A tracial state µ on A is a solution to the Dyson-Schwinger problem with initial value σ if for all P ∈ A,

It has been shown in [START_REF] Collins | Asymptotics of unitary and othogonal matrix integrals[END_REF] that there exists a solution to this problem when Tr V = Tr V * (which implies that Tr V is real), and that the solution is unique for a potential V small enough (i.e.

is a solution to (25) with σ = tr N .

In [START_REF] Guionnet | Asymptotics of unitary multimatrix models: The Schwinger-Dyson lattice and topological recursion[END_REF], a family of equations that generalize (25) was studied. The renormalized cumulants WN V,l are solution to these equations. We reproduce them here. Proposition 6.6 ([GN15, Proposition 20]). Assume Hypothesis 1.1. The renormalized cumulants { WN V,l } l≥1 satisfy the equation

The series of maps M (g),N V,l satisfy similar equations (see ( 18)).

Radius of convergence of the series

Before giving the proof of the main Theorem, we show that all the terms M (g),N V,l have a radius of convergence greater than some R V > 0. We can apply the gradient trick from [GN15] that we explain in Appendix B to the equations from Proposition 5.9 and obtain for (g, l) = (0, 1),

V,l (P ) depends only on k and q 1 , . . . , q k , and is greater than

V,1 (P ) can be bounded as follows

where as before ν = max 1≤i≤k deg q i . Choose ξ = 4A k + 2 k+2 B k . Then, assuming than

We then proceed by induction. Assume that for all (g , l ) < (g, l) (with the lexicographic order), and for all P ∈ X l n , the series M (g ),N V,l

(P ) has a radius of convergence greater than R V . Then, the right side of (26) is a holomorphic function that is defined on a polydisc of radius R V . The left side is a holomorphic function defined on a polydisc of radius R l,g,V which coincide with the right side. Thus, it can be extended to a holomorphic function on a polydisc of radius R V .

The fact that Ξ V

is invertible allows us to conclude.

The topological expansion: proof of Theorem 1.3

We introduce the truncated formal cumulant (cf. Definition 3.38)

V,l .

We will show that the cumulants WN V,l admit a topological expansion by bounding the errors

.

When z ∞ < R V , the truncated formal cumulants satisfy the equation

that is a direct consequence of (18). Together with Proposition 6.6, these equations imply the following equations on the errors.

Using the gradient trick (see Section B), these equations can be rewritten as follows

The bounds derived in the previous subsections imply the following results.

Lemma 6.8. Assume that for all N ≥ 1, Tr V is real and A N i ≤ 1 for all i (Hypotheses 1.1 and 1.2). There exists ξ > 1 and > 0, such that if z ∞ < , then, that for all g ≥ 0 and l ≥ 1, we have

Proof. Consider the secondary equations for the errors with g = 0, l = 1

First, notice that the series

A k and B k the constants from Proposition 4.17. Proposition B.4 implies that

In that case, the operator

where we used that there exists a constant C > 0 such that WN V,2 ξ/2 ≤ C by [GN15, Theorem 22]. Note that for this Theorem 22 to be applicable, one must show that the sequence of cumulants is ξ-uniformly bounded in the sense of [START_REF] Guionnet | Asymptotics of unitary multimatrix models: The Schwinger-Dyson lattice and topological recursion[END_REF]Definition 21]. This is shown assuming Assumption 1.1 in [GN15, Corollary 32] for all ξ ≥ 12.

The bound on

This fact and Proposition B.4 give

With this result and [GN15, Proposition 19], we finally get that

Proposition 6.9. Assume that for all N ≥ 1, Tr V is real and A N i ≤ 1 for all i (Hypotheses 1.1 and 1.2). There exists ξ > 1 and > 0, such that if z ∞ < , then for all g ≥ 0 and l ≥ 1, we have

Proof. We proceed by induction on (g, l), with lexicographic order. For l = 1, g = 0, the result is given by Lemma 6.8.

Assume now that for all (g , l ) < (g, l), we have

Then, in the secondary equations for the errors, all the terms on the right side of the equation are of order N -2g . Note that terms δ (-1) l = WN V,l are bounded using [START_REF] Guionnet | Asymptotics of unitary multimatrix models: The Schwinger-Dyson lattice and topological recursion[END_REF]Theorem 22]. This gives the result. Proposition 6.9 directly implies Theorem 1.3. Remark 6.10. Notice that for N big enough, the series

is well defined for all V with z small enough, even if Hypothesis 1.1 is not satisfied.

In fact, for any V with z small, provided the cumulants exist, are bounded, and satisfy the Dyson-Schwinger equations, the same method applies and the asymptotic topological expansion holds.

The complex asymptotics of the HCIZ and BGW partition functions were studied with a different method in [START_REF] Novak | On the Complex Asymptotics of the HCIZ and BGW Integrals[END_REF].

A Bounds for the sum of maps M (g),V 0,l This appendix gives a detailed proof of Proposition 4.17.

We assume that ν ≥ 1 and that up to cyclic permutation of its factors we can write P l as P u. If P l has no term u, a similar argument holds with P l = u * P .

Furthermore, to make notation less cumbersome, we write

n,l (P 1 , . . . , P l ) = M (g),N 0, i ni+l (q 1 , . . . , q 1 n1 times , . . . , q k , . . . , q k n k times , P 1 , . . . , P l ), and omit the indices k and ν in the constants.

To prove the result, we do an induction on N k+3 , where we endow a tuple (g, l, n 1 , . . . , n k , m) with the lexicographic order.

Notice that the result is obvious when n 1 = . . . = n k = 0, g = 0, l = 1 when m = 1 (as M (0),N 0,1 (M U ±1 ) = 0 for all M ∈ Y), and when m = 2 (as M (0),N 0,1 (M 1 U M 2 U -1 ) = tr M 1 tr M 2 ), as soon as M ≥ 1. In fact, by Lemma 3.36, |M (0),N 0,1 (P )| ≤ 1 for all P ∈ X .

Assuming that m ≥ 2 or n = 0, Theorem 4.1 yields

n,l (P 1 , . . . , P l-1 , P u) = -

n,l-1 (P 1 , . . . , Pj , . . . , P l-1 , (DP j )P u)

n-1j ,l (P 1 , . . . , P l-1 , (Dq j )P u),

where Pj means that P j is removed. Now assuming that the bound holds for (g , l , n 1 , . . . , n k , m ) < (g, l, n 1 , . . . , n k , m), we get four terms.

1.

B.1 The trick

The gradient trick allows us to simplify quadratic terms. We take as an example the equation for the sums of maps for g = 0, l = 2

We can rewrite it as

We now replace P 2 by its cyclic derivative D i P 2 , and obtain

be a bilinear form, tracial in each of its variables. For a monomial P ∈ X n , write deg + i (P ) for the number of factors u i in P and deg - i (P ) for the number of factors u * i in P . We have for any monomial

with the operator ∆ i defined by

In particular, if µ 2 is symmetric, we get

This Lemma allows us to rewrite the above expression as

Introducing the operator

for 1 ≤ i ≤ n.

We now introduce sums of operators on 1 ≤ i ≤ n. for all P 1 , P 2 ∈ A n . This will be called the secondary form of the equation (24). Notice that in this particular case V = 0. In the sequel, we will derive secondary equation with a potential.

53

B.2 Operator norm estimates

We now give some bounds on the norms of the different operators. These bounds and more were derived in [GN15, Section 3.2]. In particular, it was shown that under some hypotheses the master operator is invertible.

Proposition B.3 ([GN15, Section 3.3]). Let ξ ≥ 1, V ∈ A and τ a tracial state satisfying τ ≤ 1. Introduce

and assume that K(ξ, V ) < 1. Then, the operator Ξ V τ extends to an operator B ⊥ ξ → B ⊥ ξ which is invertible, with inverse satisfying

.