Second Order Freeness and

Fluctuations of Random Matrices III.

Higher order freeness and free cumulants

Benoît Collins^{1}, James A. Mingo^{2}, Piotr Śniady^{3}, Roland Speicher^{2,4}

Received: January 15, 2007

Communicated by Joachim Cuntz

Abstract. We extend the relation between random matrices and free probability theory from the level of expectations to the level of all correlation functions (which are classical cumulants of traces of products of the matrices). We introduce the notion of “higher order freeness” and develop a theory of corresponding free cumulants. We show that two independent random matrix ensembles are free of arbitrary order if one of them is unitarily invariant. We prove R-transform formulas for second order freeness. Much of the presented theory relies on a detailed study of the properties of “partitioned permutations”.

2000 Mathematics Subject Classification: 46L54 (Primary), 15A52, 60F05 Keywords and Phrases: free cumulants, random matrices, planar diagrams

1Research supported by JSPS and COE postdoctoral fellowships 2Research supported by Discovery Grants and a Leadership Support Initiative Award from the Natural Sciences and Engineering Research Council of Canada

3Research supported by MNiSW (project 1 P03A 013 30), EU Research Training Network “QP-Applications”, (HPRN-CT-2002-00279) and by European Commission Marie Curie Host Fellowship for the Transfer of Knowledge “Harmonic Analysis, Nonlinear Analysis and Probability” (MTKD-CT-2004-013389)

4Research supported by a Premier’s Research Excellence Award from the Province of Ontario and a Killam Fellowship from the Canada Council for the Arts

1. Introduction

Random matrix models and their large dimension behavior have been an important subject of study in Mathematical Physics and Statistics since Wishart and Wigner. Global fluctuations of the eigenvalues (that is, linear functionals of the eigenvalues) of random matrices have been widely investigated in the last decade; see, e.g., [Joh98, Dia03, Rad06, AZ06, MN04, MŚS07]. Roughly speaking, the trend of these investigations is that for a wide class of converging random matrix models, the non-normalized trace asymptotically behaves like a Gaussian variable whose variance only depends on macroscopic parameters such as moments. The philosophy of these results, together with the freeness results of Voiculescu served as a motivation for our series of papers on second order freeness. One of the main achievements of the free probability theory of Voiculescu [Voi91, VDN92] was an abstract description via the notion of “freeness” of the expectation of these Gaussian variables for a large class of non-commuting tuples of random matrices. In the previous articles of this series [MS06, MŚS07] we showed that for many interesting ensembles of random matrices an analogue of the results of Voiculescu for expectations holds also true on the level of variances as well; thus pointing in the direction that the structure of random matrices and the fine structure of their eigenvalues can be studied in much more detail by using the new concept of “second order freeness”. One of the main obstacles for such a detailed study was the absence of an effective machinery for doing concrete calculations in this framework. Within free probability theory of first order, such a machinery was provided by Voiculescu with the concept of the R-transform, and by Speicher with the concept of free cumulants; see, e.g., [VDN92, NSp06]. One of the main achievements of the present article is to develop a theory of second order cumulants (and show that the original definition of second order freeness from Part I of this series [MS06] is equivalent to the vanishing of mixed second order cumulants) and provide the corresponding R-transform machinery. In Section 2 we will give a more detailed (but still quite condensed) survey of the connection between Voiculescu’s free probability theory and random matrix theory. We will there also provide the main motivation, notions and concepts for our extension of this theory to the level of fluctuations (second order), as well as the statement of our main results concerning second order cumulants and R-transforms. Having first and second order freeness it is, of course, a natural question whether this theory can be generalized to higher orders. It turns out that this is the case, most of the general theory is the same for all orders. So we will in this paper consider freeness of all orders from the very beginning and develop a general theory of higher order freeness and higher order cumulants. Let us, however, emphasize that first and second order freeness seem to be more important than the higher order ones. Actually, we can prove some of the most important results (e.g. the R-transform machinery) only for first and second order, mainly because of the complexity of the underlying combinatorial objects. The basic combinatorial notion behind the (usual) free cumulants are noncrossing partitions. Basically, passage to higher order free cumulants corresponds to a change to multi-annular non-crossing permutations [MN04], or more general objects which we call “partitioned permutations”. For much of the conceptual framework there is no difference between different levels of freeness, however for many concrete questions it seems that increasing the order makes some calculations much harder. This relates to the fact that n-th order freeness is described in terms of planar permutations which connect points on n different circles. Whereas enumeration of all non-crossing permutations in the case of one circle is quite easy, the case of two circles gets more complicated, but is still feasible; for the case of three or more circles, however, the answer does not seem to be of a nice compact form. In the present paper we develop the notion and combinatorial machinery for freeness of all orders by a careful analysis of the main example: unitarily invariant random matrices. We start with the calculation of mixed correlation functions for random matrices and use the structure which we observe there as a motivation for our combinatorial setup. In this way the concept of partitioned permutations and the moment–cumulant relations appear quite canonically. We want to point out that even though our notion of second and higher order freeness is modeled on the situation found for correlation functions of random matrices, this notion and theory also have some far-reaching applications. Let us mention in this respect two points. Firstly, recently one of us [Śni06] developed a quite general theory for fluctuations of characters and shapes of random Young diagrams contributing to many natural representations of symmetric groups. The results presented there are closely (though, not explicitly) related to combinatorics of higher order cumulants. This connection will be studied in detail in the part IV of this series where we prove that under some mild technical conditions Jucys-Murphy elements, which arise naturally in the study of symmetric groups, are examples of free random variables of higher order. In another direction, the description of subfactors in von Neumann algebras via planar algebras [Jon99] relies very much on the notions of annular non-crossing partitions and thus resembles the combinatorial objects lying at the basis of our theory of second order freeness. This indicates that our results could have some relevance for subfactors.

Overview of the article. In Section 2 we will give a compact survey of the connection between Voiculescu’s free probability theory and random matrix theory, provide the main motivation, notions and concepts for our extension of this theory to the level of fluctuations (second order), as well as the statement of our main results concerning second order cumulants and R-transforms. We will also make a few general remarks about higher order freeness.

In Section 3 we will introduce the basic notions and relevant results on permutations, partitions, classical cumulants, Haar unitary random matrices, and the Weingarten function. In Section 4 we study the correlation functions (classical cumulants of traces) of random matrix models. We will see how those are related to cumulants of entries of the matrices for unitarily invariant random matrices and we will in particular look on the correlation functions for products of two independent ensembles of random matrices, one of which is unitarily invariant. The limit of those formulas if the size N of the matrices goes to infinity will be the essence of what we are going to call “higher order freeness”. Also our main combinatorial objects, “partitioned permutations”, will arise very naturally in these calculations. In Section 5 we will forget for a while random variables and just look on the combinatorial essence of our formulas, thus dealing with multiplicative functions on partitioned permutations and their convolution. The Zeta and Möbius functions on partitioned permutations will play an important role in these considerations. In Section 6 we will derive, for the case of second order, the analogue of the R-transform formulas. In Section 7 we will finally come back to a (non-commutative) probabilistic context, give the definition and work out the basic properties of “higher order freeness”. In Section 8 we introduce the notion of “asymptotic higher order freeness” and show the relevance of our work for Itzykson-Zuber integrals. In an appendix, Section 9, we provide a graphical interpretation of partitioned permutations as a special case of “surfaced permutations”.

2. Motivation and Statement of our Main Results Concerning Second Order Freeness and Cumulants

In this section we will first recall in a quite compact form the main connection between Voiculescu’s free probability theory and questions about random matrices. Then we want to motivate our notion of second order freeness by extending these questions from the level of expectations to the level of fluctuations. We will recall the relevant results from the papers [MS06, MŚS07] and state the main new results of the present paper. Even though in the later parts of the paper our treatment will include freeness of arbitrarily high order, we restrict ourselves in this section mainly to the second order. The reason for this is that (apart from first order) second order freeness seems to be the most important order for applications, so that it seems worthwhile to spell out our general results for this case more explicitly. Furthermore, it is only there that we have an analogue of R-transform formulas. We will make a few general remarks about higher order freeness at the end of this section.

2.1. Moments of random matrices and asymptotic freeness. Assume we know the eigenvalue distribution of two matrices A and B. What can we say about the eigenvalue distribution of the sum A + B of the matrices? Of course, the latter is not just determined by the eigenvalues of A and the eigenvalues of B, but also by the relation between the eigenspaces of A and of B. Actually, it is quite a hard problem (Horn’s conjecture) — which was only solved recently — to characterize all possible eigenvalue distributions of A + B. However, if one is asking this question in the context of N × N-random matrices, then in many situations the answer becomes deterministic in the limit N → ∞.

Definition 2.1. Let A = (A_{N})_{N∈ℕ} be a sequence of N × N-random matrices. We say that A has a first order limit distribution if the limit of all moments

α_{n} := lim_{N→∞} E[tr(A_{N}^{n})] (n ∈ ℕ)

exists and for all r > 1 and all n_{1}, …, n_{r} ∈ ℕ

lim_{N→∞} k_{r}(tr(A_{N}^{n_{1}}), tr(A_{N}^{n_{2}}), …, tr(A_{N}^{n_{r}})) = 0,

where E denotes the expectation, tr the normalized trace, and k_{r} the r^{th} classical cumulant.

In this language, our question becomes: Given two random matrix ensembles of N × N-random matrices, A = (A_{N})_{N∈ℕ} and B = (B_{N})_{N∈ℕ}, with first order limit distribution, does also their sum C = (C_{N})_{N∈ℕ}, with C_{N} = A_{N} + B_{N}, have a first order limit distribution, and furthermore, can we calculate the limit moments α_{n}^{C} of C out of the limit moments (α_{k}^{A})_{k≥1} of A and the limit moments (α_{k}^{B})_{k≥1} of B in a deterministic way. It turns out that this is the case if the two ensembles are in generic position, and then the rule for calculating the limit moments of C are given by Voiculescu’s concept of “freeness”. Let us recall this fundamental result of Voiculescu.

Theorem 2.2 (Voiculescu [Voi91]). Let A and B be two random matrix ensembles of N × N-random matrices, A = (A_{N})_{N∈ℕ} and B = (B_{N})_{N∈ℕ}, each of them with a first order limit distribution. Assume that A and B are independent (i.e., for each N ∈ ℕ, all entries of A_{N} are independent from all entries of B_{N}), and that at least one of them is unitarily invariant (i.e., for each N, the joint distribution of the entries does not change if we conjugate the random matrix with an arbitrary unitary N × N matrix). Then A and B are asymptotically free in the sense of the following definition.

Definition 2.3 (Voiculescu [Voi85]). Two random matrix ensembles A = (A_{N})_{N∈ℕ} and B = (B_{N})_{N∈ℕ} with limit eigenvalue distributions are asymptotically free if we have for all p ≥ 1 and all n(1), m(1), …, n(p), m(p) ≥ 1 that

lim_{N→∞} E[tr{(A_{N}^{n(1)} − α_{n(1)}^{A}1) · (B_{N}^{m(1)} − α_{m(1)}^{B}1) ⋯

⋯ (A^{n(p)} − α_{n(p)}^{A}1) · (B^{m(p)} − α_{m(p)}^{B}1)}] = 0 One should realize that asymptotic freeness is actually a rule which allows to calculate all mixed moments in A and B, i.e. all expressions

lim_{N→∞} E[tr(A^{n(1)}B^{m(1)}A^{n(2)}B^{m(2)} ⋯ A^{n(p)}B^{m(p)})]

out of the limit moments of A and the limit moments of B. In particular, this means that all limit moments of A + B (which are sums of mixed moments) exist and are actually determined in terms of the limit moments of A and the limit moments of B. The actual calculation rule is not directly clear from the above definition but a basic result of Voiculescu shows how this can be achieved by going over from the moments α_{n} to new quantities κ_{n}. In [Spe94], the combinatorial structure behind these κ_{n} was revealed and the name “free cumulants” was coined for them. Whereas in the later parts of this paper we will have to rely crucially on the combinatorial description and their extensions to higher orders, as well as on the definition of more general “mixed” cumulants, we will here state the results in the simplest possible form in terms of generating power series, which avoids the use of combinatorial objects.

Definition 2.4 (Voiculescu [Voi86], Speicher [Spe94]). Given the moments (α_{n})_{n≥1} of some distribution (or limit moments of some random matrix ensemble), we define the corresponding free cumulants (κ_{n})_{n≥1} by the following relation between their generating power series: If we put

M(x) := 1 + ∑_{n≥1} α_{n}x^{n}  and  C(x) := 1 + ∑_{n≥1} κ_{n}x^{n},

then we require as a relation between these formal power series that

C(xM(x)) = M(x).

Voiculescu actually formulated the relation above in a slightly different way using the so-called R-transform R(x), which is related to C(x) by the relation

C(x) = 1 + xR(x)

and in terms of the Cauchy transform G(x) corresponding to a measure with moments α_{n}, which is related to M(x) by

G(x) = \frac{M(\frac{1}{x})}{x}.

In these terms the equation C(xM(x)) = M(x) says that

(1)  \frac{1}{G(x)} + R(G(x)) = x,

i.e., that G(x) and K(x) := \frac{1}{x} + R(x) are inverses of each other under composition. One should also note that the relation C(xM(x)) = M(x) determines the moments uniquely in terms of the cumulants and the other way around. The relevance of the κ_{n} and the R-transform for our problem comes from the following result of Voiculescu, which provides, together with (1), a very efficient way for calculating eigenvalue distributions of the sum of asymptotically free random matrices.

Theorem 2.5 (Voiculescu [Voi86]). Let A and B be two random matrix ensembles which are asymptotically free. Denote by κ_{n}^{A}, κ_{n}^{B}, κ_{n}^{A+B} the free cumulants of A, B, A + B, respectively. Then one has for all n ≥ 1 that

κ_{n}^{A+B} = κ_{n}^{A} + κ_{n}^{B}.

Alternatively,

R^{A+B}(x) = R^{A}(x) + R^{B}(x).

This theorem is one reason for calling the κ_{n} cumulants, but there is also another justification for this, namely they are also the limit of classical cumulants of the entries of our random matrix, in the case that this is unitarily invariant. This description will follow from our formulas (28) and (30). We denote the classical cumulants by k_{n}, considered as multi-linear functionals in n arguments.

Theorem 2.6. Let A = (A_{N})_{N∈ℕ} be a unitarily invariant random matrix ensemble of N ×N random matrices A_{N} whose first order limit distribution exists. Then the free cumulants of this matrix ensemble can also be expressed as the limit of special classical cumulants of the entries of the random matrices: If A_{N} = (a_{ij}^{(N)})_{i,j=1}^{N}, then

κ_{n}^{A} = lim_{N→∞} N^{n−1}k_{n}(a_{i(1)i(2)}^{(N)}, a_{i(2)i(3)}^{(N)}, …, a_{i(n),i(1)}^{(N)})

for any choice of distinct i(1), …, i(n).

2.2. Fluctuations of random matrices and asymptotic second order freeness. There are many more refined questions about the limiting eigenvalue distribution of random matrices. In particular, questions around fluctuations have received a lot of interest in the last decade or so. The main motivation for introducing the concept of “second order freeness” was to understand the global fluctuations of the eigenvalues, which means that we look at the probabilistic behavior of traces of powers of our matrices. The limiting eigenvalue distribution, as considered in the last section, gives us the limit of the average of this traces. However, one can make more refined statements about their distributions. Consider a random matrix A = (A_{N})_{N∈ℕ} and look on the normalized traces tr(A_{N}^{k}). Our assumption of a limit eigenvalue distribution means that the limits α_{k} := lim_{N→∞} E[tr(A_{N}^{k})] exist. It turned out that in many cases the fluctuation around this limit,

tr(A_{N}^{k}) − α_{k}

is asymptotically Gaussian of order 1/N; i.e., the random variable

N · (tr(A_{N}^{k}) − α_{k}) = Tr(A_{N}^{k}) − Nα_{k} = Tr(A_{N}^{k} − α_{k}1)

(where Tr denotes the unnormalized trace) converges for N → ∞ to a normal variable. Actually, the whole family of centered unnormalized traces (Tr(A_{N}^{k})− Nα_{k})_{k≥1} converges to a centered Gaussian family. (One should note that we restrict all our considerations to complex random matrices; in the case of real random matrices there are additional complications, which will be addressed in some future investigations.) Thus the main information about fluctuations of our considered ensemble is contained in the covariance matrix of the limiting Gaussian family, i.e., in the quantities

α_{m,n} := lim_{N→∞} cov(Tr(A_{N}^{m}), Tr(A_{N}^{n})).

Let us emphasize that the α_{n} and the α_{m,n} are actually limits of classical cumulants of traces; for the first and second order, with expectation as first and variance as second cumulant, this might not be so visible, but it will become evident when we go over to higher orders. Nevertheless, the α’s will behave and will also be treated like moments; accordingly we will call the α_{m,n} ‘fluctuation moments’. We will later define some other quantities κ_{m,n}, which take the role of cumulants in this context. This kind of convergence to a Gaussian family was formalized in [MS06] as follows. Note that convergence to Gaussian means that all higher order classical cumulants converge to zero. As before, we denote the classical cumulants by k_{n}; so k_{1} is just the expectation, and k_{2} the covariance.

Definition 2.7. Let A = (A_{N})_{N∈ℕ} be an ensemble of N ×N random matrices A_{N}. We say that it has a second order limit distribution if for all m, n ≥ 1 the limits

α_{n} := lim_{N→∞} k_{1}(tr(A_{N}^{n}))

and

α_{m,n} := lim_{N→∞} k_{2}(Tr(A_{N}^{m}), Tr(A_{N}^{n}))

exist and if

lim_{N→∞} k_{r}(Tr(A_{N}^{n(1)}), …, Tr(A_{N}^{n(r)})) = 0

for all r ≥ 3 and all n(1), …, n(r) ≥ 1.

We can now ask the same kind of question for the limit fluctuations as for the limit moments; namely, if we have two random matrix ensembles A and B and we know the second order limit distribution of A and the second order limit distribution of B, does this imply that we have a second order limit distribution for A + B, and, if so, is there an effective way for calculating it. Again, we can only hope for a positive solution to this if A and B are in a kind of generic position. As it turned out, the same requirements as before are sufficient for this. The rule for calculating mixed fluctuations constitutes the essence of the definition of the concept of second order freeness.

Theorem 2.8 (Mingo, Śniady, Speicher [MŚS07]). Let A and B be two random matrix ensembles of N × N-random matrices, A = (A_{N})_{N∈ℕ} and B = (B_{N})_{N∈ℕ}, each of them having a second order limit distribution. Assume that A and B are independent and that at least one of them is unitarily invariant. Then A and B are asymptotically free of second order in the sense of the following definition.

Definition 2.9 (Mingo, Speicher [MS06]). Consider two random matrix ensembles A = (A_{N})_{N∈ℕ} and B = (B_{N})_{N∈ℕ}, each of them with a second order limit distribution. Denote by

Y_{N}(n(1), m(1), …, n(p), m(p))

the random variable

Tr((A_{N}^{n(1)} − α_{n(1)}^{A}1)(B_{N}^{m(1)} − α_{m(1)}^{B}1) ⋯ (A_{N}^{n(p)} − α_{n(p)}^{A}1)(B_{N}^{m(p)} − α_{m(p)}^{B}1)).

The random matrices A = (A_{N})_{N∈ℕ} and B = (B_{N})_{N∈ℕ} are asymptotically free of second order if for all n, m ≥ 1

lim_{N→∞} k_{2}(Tr(A_{N}^{n} − α_{n}^{A}1), Tr(B_{N}^{m} − α_{m}^{B}1)) = 0

and for all p, q ≥ 1 and n(1), …, n(p),m(1), …, m(p),ñ(1), …, ñ(q), m̃(1), …, m̃(q) ≥ 1 we have

lim_{N→∞} k_{2}(Y_{N}(n(1), m(1), …, n(p), m(p)), Y_{N}(ñ(1), m̃(2), …, ñ(q), m̃(q))) = 0

if p ≠ q, and otherwise (where we count modulo p for the arguments of the indices, i.e., n(i + p) = n(i))

lim_{N→∞} k_{2}(Y_{N}(n(1), m(1), …, n(p), m(p)), Y_{N}(ñ(p), m̃(p), …, ñ(1), m̃(1)))

= ∑_{k=1}^{p} ∏_{i=1}^{p}(α_{n(i+k)+ñ(i)}^{A} − α_{n(i+k)}^{A}α_{ñ(i)}^{A})(α_{m(i+k)+m̃(i+1)}^{B} − α_{m(i+k)}^{B}α_{m̃(i+1)}^{B}).

Again, it is crucial to realize that this definition allows one (albeit in a complicated way) to express every second order mixed moment, i.e., a limit of the form

lim_{N→∞} k_{2}(Tr(A_{N}^{n(1)}B_{N}^{m(1)} ⋯ A_{N}^{n(p)}B_{N}^{m(p)}), Tr(A_{N}^{ñ(1)}B_{N}^{m̃(1)} ⋯ A_{N}^{ñ(q)}B_{N}^{m̃(q)}))

in terms of the second order limits of A and the second order limits of B. In particular, asymptotic freeness of second order also implies that the sum A + B of our random matrix ensembles has a second order limit distribution and allows one to express them in principle in terms of the second order limit distribution of A and the second order limit distribution of B. As in the case of first order freeness, it is not clear at all how this calculation of the fluctuations of A+B out of the fluctuations of A and the fluctuations of B can be performed effectively. It is one of the main results of the present paper to achieve such an effective description. We are able to solve this problem by providing a second order cumulant machinery, similar to the first order case. Again, the idea is to go over to quantities which behave like cumulants in this setting. The actual description of those relies on combinatorial objects (annular non-crossing permutations), but as before this can be reformulated in terms of formal power series. Let us spell out the definition here in this form. (That this is equivalent to our actual definition of the cumulants will follow from Theorem 6.3.)

Definition 2.10. Let (α_{n})_{n≥1} and (α_{m,n})_{m,n≥1} describe the first and second order limit moments of a random matrix ensemble. We define the corresponding first and second order free cumulants (κ_{n})_{n≥1} and (κ_{m,n})_{m,n≥1} by the following requirement in terms of the corresponding generating power series. Put

C(x) := 1 + ∑_{n≥1} κ_{n}x^{n}, C(x, y) := ∑_{m,n≥1} κ_{m,n}x^{m}y^{n}

and

M(x) := 1 + ∑_{n≥1} α_{n}x^{n}, M(x, y) := ∑_{m,n≥1} α_{m,n}x^{m}y^{n}.

Then we require as relations between these formal power series that

(2)  C(xM(x)) = M(x)

and for the second order

(3)  M(x, y) = H(xM(x), yM(y)) · \frac{\frac{d}{dx}(xM(x))}{M(x)} · \frac{\frac{d}{dy} (yM(y))}{M(y)},

where

(4)  H(x, y) := C(x, y) − xy \frac{∂^{2}}{∂x∂y} log(\frac{xC(y) − yC(x)}{x − y}),

or equivalently,

(5) M(x, y) = C(xM(x), yM(y)) · \frac{\frac{d}{dx}(xM(x))}{M(x)} · \frac{\frac{d}{dy} (yM(y))}{M(y)}

+ xy( \frac{\frac{d}{dx}(xM(x)) · \frac{d}{dy} (yM(y))}{(xM(x) − yM(y))^{2}} − \frac{1}{(x − y)^{2}} ).

From equation (5) one can calculate the second order version of momentcumulant relations.

α_{1,1} = κ_{1,1} + κ_{2}
α_{2,1} = κ_{1,2} + 2κ_{1}κ_{1,1} + 2κ_{3} + 2κ_{1}κ_{2}
α_{2,2} = κ_{2,2} + 4κ_{1}κ_{2,1} + 4κ_{1}^{2}κ_{1,1} + 4κ_{4} + 8κ_{1}κ_{3} + 2κ_{2}^{2} + 4κ_{1}^{2}κ_{2}

α_{1,3} = κ_{1,3} + 3κ_{1}κ_{2,1} + 3κ_{2}κ_{1,1} + 3κ_{1}^{2}κ_{1,1} + 3κ_{4} + 6κ_{1}κ_{3} + 3κ_{2}^{2} + 3κ_{1}^{2}κ_{2} α_{2,3} = κ_{2,3} + 2κ_{1}κ_{1,3} + 3κ_{1}κ_{2,2} + 3κ_{2}κ_{1,2} + 9κ_{1}^{2}κ_{1,2} + 6κ_{1}κ_{2}κ_{1,1} + 6κ_{1}^{3}κ_{1,1}

+ 6κ_{5} + 18κ_{1}κ_{4} + 12κ_{2}κ_{3} + 18κ_{1}^{2}κ_{3} + 12κ_{1}κ_{2}^{2} + 6κ_{1}^{3}κ_{2}

α_{3,3} = κ_{3,3} + 6κ_{1}κ_{2,3} + 6κ_{2}κ_{1,3} + 6κ_{1}^{2}κ_{1,3} + 9κ_{1}^{2}κ_{2,2} + 18κ_{1}κ_{2}κ_{1,2} + 18κ_{1}^{3}κ_{1,2}

+ 9κ_{2}^{2}κ_{1,1} + 18κ_{1}^{2}κ_{2}κ_{1,1} + 9κ_{1}^{4}κ_{1,1} + 9κ_{6} + 36κ_{1}κ_{5} + 27κ_{2}κ_{4} + 54κ_{1}^{2}κ_{4}

+ 9κ_{3}^{2} + 72κ_{1}κ_{2}κ_{3} + 36κ_{1}^{3}κ_{3} + 12κ_{2}^{3} + 36κ_{1}^{2}κ_{2}^{2} + 9κ_{1}^{4}κ_{2}
κ_{1,1} = α_{1}^{2} − α_{2} + α_{1,1}

κ_{1,2} = −4α_{1}^{3} + 6α_{1}α_{2} − 2α_{3} − 2α_{1}α_{1,1} + α_{1,2}

κ_{2,2} = 18α_{1}^{4} − 36α_{1}^{2}α_{2} + 6α_{2}^{2} + 16α_{1}α_{3} − 4α_{4} + 4α_{1}^{2}α_{1,1} − 4α_{1}α_{1,2} + α_{2,2}

κ_{1,3} = 15α_{1}^{4} −30α_{1}^{2}α_{2} +6α_{2}^{2} +12α_{1}α_{3} −3α_{4} +6α_{1}^{2}α_{1,1} −3α_{2}α_{1,1} −3α_{1}α_{1,2} +α_{1,3}

κ_{2,3} = −72α_{1}^{5} + 180 α_{1}^{3} α_{2} − 72α_{1}α_{2}^{2} − 84 α_{1}^{2}α_{3} + 24α_{2}α_{3} + 30α_{1}α_{4} − 6α_{5}

− 12α_{1}^{3}α_{1,1} + 6α_{1}α_{2}α_{1,1} + 12α_{1}^{2}α_{1,2} − 3α_{2}α_{1,2} − 2α_{1}α_{1,3} − 3α_{1}α_{2,2} + α_{2,3}

κ_{3,3} = 300α_{1}^{6} − 900α_{1}^{4}α_{2} + 576α_{1}^{2}α_{2}^{2} − 48α_{2}^{3} + 432α_{1}^{3}α_{3} − 288α_{1}α_{2}α_{3} + 18α_{3}^{2}

− 180α_{1}^{2}α_{4} + 45α_{2}α_{4} + 54α_{1}α_{5} − 9α_{6} + 36α_{1}^{4}α_{1,1} − 36α_{1}^{2}α_{2}α_{1,1} + 9α_{2}^{2}α_{1,1}

− 36α_{1}^{3}α_{1,2} + 18α_{1}α_{2}α_{1,2} + 12α_{1}^{2}α_{1,3} − 6α_{2}α_{1,3} + 9α_{1}^{2}α_{2,2} − 6α_{1}α_{2,3} + α_{3,3}

As in the first order case, instead of the moment power series M(x, y) one can consider a kind of second order Cauchy transform, defined by

G(x, y) := \frac{M(\frac{1}{x}, \frac{1}{y})}{xy}.

If we also define a kind of second order R transform R(x, y) by

R(x, y) := \frac{1}{xy} C(x, y),

then the formula (5) takes on a particularly nice form:

(6) G(x, y) = G′(x)G′(y)\{R(G(x), G(y)) + \frac{1}{(G(x) − G(y))^{2}} \}−\frac{1}{(x − y)^{2}} .

G(x) is here, as before, the first order Cauchy transform, G(x) = \frac{1}{x}M(1/x). The κ_{m,n} defined above deserve the name “cumulants” as they linearize the problem of adding random matrices which are asymptotically free of second order. Namely, as will follow from our Theorem 7.15, we have the following theorem, which provides, together with (6), an effective machinery for calculating the fluctuations of the sum of asymptotically free random matrices.

Theorem 2.11. Let A and B be two random matrix ensembles which are asymptotically free. Then one has for all m, n ≥ 1 that

κ_{n}^{A+B} = κ_{n}^{A} + κ_{n}^{B}  and  κ_{m,n}^{A+B} = κ_{m,n}^{A} + κ_{m,n}^{B}.

Alternatively,

R^{A+B}(x) = R^{A}(x) + R^{B}(x)

and

R^{A+B}(x, y) = R^{A}(x, y) + R^{B}(x, y).

Again, one can express the second order cumulants as limits of classical cumulants of entries of a unitarily invariant matrix. In contrast to the first order case, we have now to run over two disjoint cycles in the indices of the matrix entries. This theorem will follow from our formulas (28) and (30).

Theorem 2.12. Let A = (A_{N})_{N∈ℕ} be a unitarily invariant random matrix ensemble which has a second order limit distribution. Then the second order free cumulants of this matrix ensemble can also be expressed as the limit of classical cumulants of the entries of the random matrices: If A_{N} = (a_{ij}^{(N)})_{i,j=1}^{N}, then

κ_{m,n}^{A} = lim_{N→∞} N^{m+n}k_{m+n}(a_{i(1)i(2)}^{(N)}, a_{i(2)i(3)}^{(N)}, …, a_{i(m),i(1)}^{(N)},

a_{j(1)j(2)}^{(N)}, a_{j(2)j(3)}^{(N)}, …, a_{j(n),j(1)}^{(N)})

for any choice of distinct i(1), …, i(m), j(1), …, j(n).

This latter theorem makes it quite obvious that the second order cumulants for Gaussian as well as for Wishart matrices vanish identically, i.e., R(x, y) = 0 and thus we obtain in these cases that the second order Cauchy transform is totally determined in terms of the first order Cauchy transform (i.e., in terms of the limiting eigenvalue distribution) via

(7)  G(x, y) = \frac{G′(x)G′(y)}{(G(x) − G(y))^{2}} − \frac{1}{(x − y)^{2}} .

This formula for fluctuations of Wishart matrices was also derived by Bai and Silverstein in [BS04].

2.3. Higher order freeness. The idea for higher order freeness is the same as for second order one. For a random matrix ensemble A = (A_{N})_{N∈ℕ} we define r-th order limit moments as the scaled limit of classical cumulants of r traces of powers of our matrices,

α_{n_{1},...,n_{r}} := lim_{N→∞} N^{r−2}k_{r}(Tr(A_{N}^{n(1)}), …, Tr(A_{N}^{n(r)})).

(The choice of N^{r−2} is motivated by the fact that this is the leading order for many interesting random matrix ensembles, e.g. Gaussian or Wishart. Thus our theory of higher order freeness captures the features of random matrix ensembles whose cumulants of traces decay in the same way as Gaussian random matrices.) Then we look at two random matrix ensembles A and B which are independent, and one of them unitarily invariant. The mixed moments in A and B of order r are, in leading order in the limit N → ∞, determined by the limit moments of A up to order r and the limit moments of B up to order r. The structure of these formulas motivates directly the definition of cumulants of the considered order. The definition of those is in terms of a moment-cumulant formula, which gives a moment in terms of cumulants by summing over special combinatorial objects, which we call “partitioned permutations”. Most of the theory we develop relies on an in depth analysis of properties of these partitioned permutations and the corresponding convolution of multiplicative functions on partitioned permutations. Our definition of “higher order freeness” is then in terms of the vanishing of mixed cumulants. It follows quite easily that in the first and second order case this gives the same as the relations in Definitions 2.3 and 2.9, respectively. For higher orders, however, we are not able to find an explicit relation of that type. This reflects somehow the observation that our general formulas in terms of sums over partitioned permutations are the same for all orders, but that evaluating or simplifying these sums (by doing partial summations) is beyond our abilities for orders greater than 2. Reformulating the combinatorial relation between moments and cumulants in terms of generating power series is one prominent example for this. Whereas this is quite easy for first order, the complexity of the arguments and the solution (given in Definition 2.10) is much higher for second order, and out of reach for higher order. One should note that an effective (analytic or symbolic) calculation of higher order moments of a sum A+B for A and B free of higher order relies usually on the presence of such generating power series formulas. In this sense, we have succeeded in providing an effective machinery for dealing with fluctuations (second order), but we were not able to do so for higher order. Our results for higher orders are more of a theoretical nature. One of the main problems we have to address there is the associativity of the notion of higher order freeness. Namely, in order to be an interesting concept, our definition that A and B are free of higher order should of course imply that any function of A is also free of higher order from any function of B. Whereas for first and second order this follows quite easily from the equivalent characterization of freeness in terms of moments as in Definitions 2.3 and 2.9, the absence of such a characterization for higher orders makes this a more complicated matter. Namely, what we have to see is that the vanishing of mixed cumulants in random variables implies also the vanishing of mixed cumulants in elements from the generated algebras. This is quite a non-trivial fact and requires a careful analysis, see section 7.

3. Preliminaries

3.1. Some general notation. For natural numbers m, n ∈ ℕ with m < n, we denote by [m, n] the interval of natural numbers between m and n, i.e.,

[m, n] := {m, m + 1, m + 2, …, n − 1, n}.

For a matrix A = (a_{ij})_{i,j=1}^{N}, we denote by Tr the unnormalized and by tr the normalized trace,

Tr(A) := ∑_{i=1}^{N} a_{ii}, tr(A) := \frac{1}{N} Tr(A).

3.2. Permutations. We will denote the set of permutations on n elements by S_{n}. We will quite often use the cycle notation for such permutations, i.e., π = (i_{1}, i_{2}, …, i_{r}) is a cycle which sends i_{k} to i_{k+1} (k = 1, …, r), where i_{r+1} = i_{1}.

3.2.1. Length function. For a permutation π ∈ S_{n} we denote by #π the number of cycles of π and by |π| the minimal number of transpositions needed to write π as a product of transpositions. Note that one has

|π| + #π = n for all π ∈ S_{n}.

3.2.2. Non-crossing permutations. Let us denote by γ_{n} ∈ S_{n} the cycle

γ_{n} = (1, 2, …, n).

For all π ∈ S_{n} one has that

|π| + |γ_{n}π^{−1}| ≤ n − 1.

If we have equality then we call π non-crossing. Note that this is equivalent to

#π + #(γ_{n}π^{−1}) = n + 1.

If π is non-crossing, then so are γ_{n}π^{−1} and π^{−1}γ_{n}; the latter is called the (Kreweras) complement of π. We will denote the set of non-crossing permutations in S_{n} by NC(n). Note that such a non-crossing permutation can be identified with a non-crossing partition, by forgetting the order on the cycles. There is exactly one cyclic order on the blocks of a non-crossing partition which makes it into a noncrossing permutation.

3.2.3. Annular non-crossing permutations. Fix m, n ∈ ℕ and denote by γ_{m,n} the product of the two cycles

γ_{m,n} = (1, 2, …, m)(m + 1, m + 2, …, m + n).

More generally, we shall denote by γ_{m_{1},...,m_{k}} the product of the corresponding k cycles. We call a π ∈ S_{m+n} connected if the pair π and γ_{m,n} generates a transitive subgroup in S_{m+n}. A connected permutation π ∈ S_{m+n} always satisfies

(8)  |π| + |γ_{m,n}π^{−1}| ≤ m + n.

If π is connected and if we have equality in that equation then we call π annular non-crossing. Note that if π is annular non-crossing then γ_{m,n}π^{−1} is also annular non-crossing. Again, we call the latter the complement of π. Of course, all the above notations depend on the pair (m, n); if we want to emphasize this dependency we will also speak about (m, n)-connected permutations and (m, n)-annular non-crossing permutations. We will denote the set of (m, n)-annular non-crossing permutations by S_{NC}(m, n). A cycle of a π ∈ S_{NC}(m, n) is called a through-cycle if it contains points on both cycles. Each π ∈ S_{NC}(m, n) is connected and must thus have at least one through-cycle. The subset of S_{NC}(m, n) where all cycles are through-cycles will be denoted by S_{NC}^{all}(m, n). Again one can go over from annular non-crossing permutations to annular noncrossing partitions by forgetting the cyclic orders on cycles; however, in the annular case, the relation between non-crossing permutation and non-crossing partition is not one-to-one. Since we will not use the language of annular partitions in the present paper, this is of no relevance here. Annular non-crossing permutations and partitions were introduced in [MN04]; there, many different characterizations—in particular, the one (8) above in terms of the length function—were given.

3.3. Partitions. We say that V = {V_{1}, …, V_{k}} is a partition of a set [1, n] if the sets V_{i} are disjoint and non–empty and their union is equal to [1, n]. We call V_{1}, …, V_{k} the blocks of partition V. If V = {V_{1}, …, V_{k}} and W = {W_{1}, …, W_{l}} are partitions of the same set, we say that V ≤ W if for every block V_{i} there exists some block W_{j} such that V_{i} ⊆ W_{j}. For a pair of partitions V, W we denote by V ∨ W the smallest partition U such that V ≤ U and W ≤ U. We denote by 1_{n} = {[1, n]} the biggest partition of the set [1, n]. If π ∈ S_{n} is a permutation, then we can associate to π in a natural way a partition whose blocks consist exactly of the cycles of π; we will denote this partition either by 0_{π} ∈ P(n) or, if the context makes the meaning clear, just by π ∈ P(n). For a permutation π ∈ S_{n} we say that a partition V is π-invariant if π preserves each block of V. This means that 0_{π} ≤ V (which we will usually write just as π ≤ V). If V = {V_{1}, …, V_{k}} is a partition of the set [1, n] and if, for 1 ≤ i ≤ k, π_{i} is a permutation of the set V_{i} we denote by π_{1} × ⋯ × π_{k} ∈ S_{n} the concatenation of these permutations. We say that π = π_{1} × ⋯ × π_{k} is a cycle decomposition if additionally every factor π_{i} is a cycle.

3.4. Classical cumulants. Given some classical probability space (Ω, P) we denote by E the expectation with respect to the corresponding probability measure,

E(a) := ∫_{Ω} a(ω)dP (ω)

and by L^{∞−}(Ω, P) the algebra of random variables for which all moments exist. Let us for the following put A := L^{∞−}(Ω, P). We extend the linear functional E : A → ℂ to a corresponding multiplicative functional on all partitions by (V ∈ P(n), a_{1}, …, a_{n} ∈ A)

(9)  E_{V}[a_{1}, …, a_{n}] := ∏_{V ∈V} E[a_{1}, …, a_{n}|_{V}],

where we use the notation

E[a_{1}, …, a_{n}|_{V}] := E(a_{i_{1}} ⋯ a_{i_{s}})  for  V = (i_{1} < ⋯ < i_{s}) ∈ V.

Then, for V ∈ P(n), we define the classical cumulants k_{V} as multilinear functionals on A by

(10)  k_{V}[a_{1}, …, a_{n}] = ∑_{{W∈P(n) \atop W≤V}} E_{W}[a_{1}, …, a_{n}] · Möb_{P(n)}(W, V),

where Möb_{P(n)} denotes the Möbius function on P(n) (see [Rot64]). The above definition is, by Möbius inversion on P(n), equivalent to

E(a_{1} ⋯ a_{n}) = ∑_{π∈P(n)} k_{π}[a_{1}, …, a_{n}].

The k_{π} are also multiplicative with respect to the blocks of V and thus determined by the values of

k_{n}(a_{1}, …, a_{n}) := k_{1_{n}}[a_{1}, …, a_{n}].

Note that we have in particular

k_{1}(a) = E(a)  and  k_{2}(a_{1}, a_{2}) = E(a_{1}a_{2}) − E(a_{1})E(a_{2}).

An important property of classical cumulants is the following formula of Leonov and Shiryaev [LS59] for cumulants with products as arguments. Let m, n ∈ ℕ and 1 ≤ i(1) < i(2) < ⋯ < i(m) = n. Define U ∈ P(n) by

U = {(1, …, i(1)), (i(1) + 1, …, i(2)), …, (i(m − 1) + 1, …, i(m))}.

Consider now random variables a_{1}, …, a_{n} ∈ A and define

A_{1} : = a_{1} ⋯ a_{i(1)}
A_{2} : = a_{i(1)+1} ⋯ a_{i(2)}
⋮
A_{m} : = a_{i(m−1)+1} ⋯ a_{i(m)}.

Then we have

(11)  k_{m}(A_{1}, A_{2}, …, A_{m}) = ∑_{{V∈P(n) \atop V∨U=1n}} k_{V}[a_{1}, …, a_{n}].

The sum on the right-hand side is running over those partitions of n elements which satisfy V ∨U = 1_{n}, which are, informally speaking, those partitions which connect all the arguments of the cumulant k_{m}, when written in terms of the a_{i}. Here is an example for this formula; for k_{2}(a_{1}a_{2}, a_{3}a_{4}). In order to reduce the number of involved terms we will restrict to the special case where E(a_{i}) = 0 (and thus also k_{1}(a_{i}) = 0) for all i = 1, 2, 3, 4. There are three partitions π ∈ P(4) without singletons which satisfy

π ∨ {(1, 2), (3, 4)} = 1_{4},

namely

a_{1} a_{2} a_{3} a_{4}

Documenta Mathematica 12 (2007) 1–70

and thus formula (11) gives in this case

k_{2}(a_{1}a_{2}, a_{3}a_{4}) = k_{4}(a_{1}, a_{2}, a_{3}, a_{4})

+ k_{2}(a_{1}, a_{4})k_{2}(a_{2}, a_{3}) + k_{2}(a_{1}, a_{3})k_{2}(a_{2}, a_{4}).

As a consequence of (11) one has the following important corollary: If {a_{1}, …, a_{n}} and {b_{1}, …, b_{n}} are independent then

(12)  k_{W}[a_{1}b_{1}, …, a_{n}b_{n}] = ∑_{{V,V′∈P(n) \atop V∨V′=W}} k_{V}[a_{1}, …, a_{n}] · k_{V′}[b_{1}, …, b_{n}].

3.5. Haar distributed unitary random matrices and the Weingarten function. In the following we will be interested in the asymptotics of special matrix integrals over the group U(N) of unitary N × N-matrices. We always equip the compact group U(N) with its Haar probability measure. A random matrix whose distribution is this measure will be called a Haar distributed unitary random matrix. Thus the expectation E over this ensemble is given by integrating with respect to the Haar measure. The expectation of products of entries of Haar distributed unitary random matrices can be described in terms of a special function on the permutation group. Since such considerations go back to Weingarten [Wei78], Collins [Col03] calls this function the Weingarten function and denotes it by Wg. We will follow his notation. In the following we just recall the relevant information about this Weingarten function, for more details we refer to [Col03, CŚ06]. We use the following definition of the Weingarten function. For π ∈ S_{n} and N ≥ n we put

Wg(N, π) = E[u_{11} ⋯ u_{nn}\overline{u_{1π(1)}} ⋯ \overline{u_{nπ(n)}}],

where U = (u_{ij})_{i,j=1}^{N} is an N × N Haar distributed unitary random matrix. Sometimes we will suppress the dependency on N and just write Wg(π). This Wg(N, π) depends only on the conjugacy class of π. General matrix integrals over the unitary group can be calculated as follows:

(13) E[u_{i′_{1}j′_{1}} ⋯ u_{i′_{n}j′_{n}} \overline{u_{i_{1}j_{1}}} ⋯ \overline{u_{i_{n}j_{n}}}]

= ∑_{α,β∈S_{n}} δ_{i_{1}i′_{α(1)}} ⋯ δ_{i_{n}i′_{α(n)}}δ_{j_{1}j′_{β(1)}} ⋯ δ_{j_{n}j′_{β(n)}}Wg(βα^{−1}).

This formula for the calculation of moments of the entries of a Haar unitary random matrix bears some resemblance to the Wick formula for the joint moments of the entries of Gaussian random matrices; thus we will call (13) the Wick formula for Haar unitary matrices. The Weingarten function is quite a complicated object, and its full understanding is at the basis of questions around Itzykson-Zuber integrals. One knows (see, e.g., [Col03, CŚ06]) that the leading order in 1/N is given by |π| + n and increases in steps of 2.

3.6. Cumulants of the Weingarten function. We will also need some (classical) relative cumulants of the Weingarten function, which were introduced in [Col03, §2.3]. As before, let Möb_{P(n)} be the Möbius function on the partially ordered set of partitions of [1, n] ordered by inclusion. Let us first extend the Weingarten function by multiplicative extension, for V ≥ π, by

Wg(V, π) := ∏_{V ∈V} Wg(π|_{V}),

where π|_{V} denotes the restriction of π to the block V ∈ V (which is invariant under π since π ≤ V). The relative cumulant of the Weingarten function is now, for σ ≤ V ≤ W, defined by

(14)  C_{V,W}(σ) = ∑_{{U∈P(n) \atop V≤U≤W}} Möb(U, W) · Wg(U, σ).

Note that, by Möbius inversion, this is, for any σ ≤ V ≤ W, equivalent to

(15)  Wg(W, σ) = ∑_{{U∈P(n) \atop V≤U≤W}} C_{V,U}(σ).

In [Col03, Cor. 2.9] it was shown that the order of C_{V,W}(σ) is at most

(16)  N^{−2n+#σ+2#W−2#V}.

4. Correlation functions for random matrices

4.1. Correlation functions and partitioned permutations. Let us consider N × N-random matrices B_{1}, …, B_{n} : Ω → M_{N}(ℂ). The main information we are interested in are the “correlation functions” φ_{n} of these matrices, given by classical cumulants of their traces, i.e.,

φ_{n}(B_{1}, …, B_{n}) := k_{n}(Tr(B_{1}), …, Tr(B_{n})).

Even though these correlation functions are cumulants, it is more adequate to consider them as a kind of moments for our random matrices. Thus, we will also call them sometimes correlation moments. We will also need to consider traces of products which are best encoded via permutations. Thus, for π ∈ S_{n}, φ(π)[B_{1}, …, B_{n}] shall mean that we take cumulants of traces of products along the cycles of π. For an n-tuple B = (B_{1}, …, B_{n}) of random matrices and a cycle c = (i_{1}, i_{2}, …, i_{k}) with k ≤ n we denote

B|_{c} := B_{i_{1}}B_{i_{2}} ⋯ B_{i_{k}}.

(We do not distinguish between products which differ by a cyclic rotation of the factors; however, in order to make this definition well-defined we could normalize our cycle c = (i_{1}, i_{2}, …, i_{k}) by the requirement that i_{1} is the smallest among the appearing numbers.) For any π ∈ S(n) and any n-tuple B = (B_{1}, …, B_{n}) of random matrices we put

φ(π)[B_{1}, …, B_{n}] := φ_{r}(B|_{c_{1}}, …, B|_{c_{r}}), where π consists of the cycles c_{1}, …, c_{r}. Example:

φ((1, 3)(2, 5, 4))[B_{1}, B_{2}, B_{3}, B_{4}, B_{5}] = φ_{2}(B_{1}B_{3}, B_{2}B_{5}B_{4})
= k_{2}(Tr(B_{1}B_{3}), Tr(B_{2}B_{5}B_{4}))

Furthermore, we also need to consider more general products of such φ(π)’s. In order to index such products we will use pairs (V, π) where π is, as above, an element in S_{n}, and V ∈ P(n) is a partition which is compatible with the cycle structure of π, i.e., each block of V is fixed under π, or to put it another way, V ≥ π. In the latter inequality we use the convention that we identify a permutation with the partition corresponding to its cycles if this identification is obvious from the structure of the formula; we will write this partition 0_{π} or just 0 if no confusion will result.

Notation 4.1. A partitioned permutation is a pair (V, π) consisting of π ∈ S_{n} and V ∈ P(n) with V ≥ π. We will denote the set of partitioned permutations of n elements by PS(n). We will also put

PS := ⋃_{n∈ℕ} PS(n).

For such a (V, π) ∈ PS we denote finally

φ(V, π)[B_{1}, …, B_{n}] := ∏_{V ∈V} φ(π|_{V})[B_{1}, …, B_{n}|_{V}].

Example:

φ({1, 3, 4}{2}, (1, 3)(2)(4))[B_{1}, B_{2}, B_{3}, B_{4}]
= φ_{2}(B_{1}B_{3}, B_{4}) · φ_{1}(B_{2})
= k_{2}(Tr(B_{1}B_{3}), Tr(B_{4})) · k_{1}(Tr(B_{2}))

Let us denote by Tr_{σ} as usual a product of traces along the cycles of σ. Then we have the relation

E\{Tr_{σ}[A_{1}, …, A_{n}]\} = ∑_{{W∈P(n) \atop W≥σ}} φ(W, σ)[A_{1}, …, A_{n}].

By using the formula (11) of Leonov and Shiryaev one sees that in terms of the entries of our matrices B_{k} = (b_{ij}^{(k)})_{i,j=1}^{N} our φ(U, γ) can also be written as

(17) φ(U, γ)[B_{1}, …, B_{n}] = ∑_{{V≤U \atop V∨γ=U}} ∑_{i(1),...,i(n)=1}^{N} k_{V}[b_{i(1)i(γ(1))}^{(1)}, …, b_{i(n)i(γ(n))}^{(n)}].

4.2. Moments of unitarily invariant random matrices. For unitarily invariant random matrices there exists a definite relation between cumulants of traces and cumulants of entries. We want to work out this connection in this section. Related considerations were presented by Capitaine and Casalis in [CC06].

Definition 4.2. Random matrices A_{1}, …, A_{n} are called unitarily invariant if the joint distribution of all their entries does not change by global conjugation with any unitary matrix, i.e., if, for any unitary matrix U, the matrix-valued random variables A_{1}, …, A_{n} : Ω → M_{N}(ℂ) have the same joint distribution as the matrix-valued random variables UA_{1}U^{∗}, …, UA_{n}U^{∗} : Ω → M_{N}(ℂ).

Let A_{1}, …, A_{n} be unitarily invariant random matrices. We will now try expressing the microscopic quantities “cumulants of entries of the A_{i}” in terms of the macroscopic quantities “cumulants of traces of products of the A_{i}”. In order to make this connection we have to use the unitary invariance of our ensemble. By definition, this means that A_{1}, …, A_{n} has the same distribution as Ã_{1}, …, Ã_{n} where Ã_{i} := UA_{i}U^{∗}. Since this holds for any unitary U, the same is true after averaging over such U, i.e., we can take in the definition of the Ã_{i} the U as Haar distributed unitary random matrices, independent from A_{1}, …, A_{n}. This reduces calculations for unitarily invariant ensembles essentially to properties of Haar unitary random matrices; in particular, the Wick formula for the U’s implies that we have an analogous Wick formula for joint moments in the entries of the A_{i}. Let us write A_{k} = (a_{ij}^{(k)})_{i,j=1}^{N} and Ã_{k} = (ã_{ij}^{(k)})_{i,j=1}^{N}. Then we can calculate:

E{a_{p_{1}r_{1}}^{(1)} ⋯ a_{p_{n}r_{n}}^{(n)}} = E{ã_{p_{1}r_{1}}^{(1)} ⋯ ã_{p_{n}r_{n}}^{(n)}}

= ∑_{i,j} E\{u_{p_{1}i_{1}}a_{i_{1}j_{1}}^{(1)} \overline{u_{r_{1}j_{1}}} ⋯ u_{p_{n}i_{n}}a_{i_{n}j_{n}}^{(n)} \overline{u_{r_{n}j_{n}}}\}

= ∑_{i,j} E\{u_{p_{1}i_{1}} \overline{u_{r_{1}j_{1}}} ⋯ u_{p_{n}i_{n}} \overline{u_{r_{n}j_{n}}}\} · E\{a_{i_{1}j_{1}}^{(1)} ⋯ a_{i_{n}j_{n}}^{(n)}\}

= ∑_{i,j} ∑_{π,σ∈S_{n}} δ_{r,p∘π}δ_{j,i∘σ}Wg(σπ^{−1}) · E{a_{i_{1}j_{1}}^{(1)} ⋯ a_{i_{n}j_{n}}^{(n)}}

= ∑_{π∈S_{n}} δ_{r,p∘π} · G(π)[A_{1}, …, A_{n}],

where

(18) G(π)[A_{1}, …, A_{n}] : = ∑_{σ∈S_{n}} Wg(σπ^{−1}) · ∑_{i} E{a_{i_{1}i_{σ(1)}}^{(1)} ⋯ a_{i_{n}i_{σ(n)}}^{(n)}}

= ∑_{σ∈S_{n}} Wg(σπ^{−1}) · E{Tr_{σ}[A_{1}, …, A_{n}]}.

= ∑_{σ∈S_{n}} Wg(σπ^{−1}) · ∑_{{W∈P(n) \atop W≥σ}} φ(W, σ)[A_{1}, …, A_{n}]

= ∑_{(W,σ)∈PS(n)} Wg(σπ^{−1}) · φ(W, σ)[A_{1}, …, A_{n}].

The important point here is that G(π)[A_{1}, …, A_{n}] depends only on the macroscopic correlation moments of A.

We can extend the above to products of expectations by

E_{V}[a_{p_{1}r_{1}}, … a_{p_{n}r_{n}}] = ∑_{{π∈Sn \atop π≤V}} δ_{r,p∘π} · G(V, π)[A_{1}, …, A_{n}],

where G(V, π) is given by multiplicative extension:

G(V, π)[A_{1}, …, A_{n}] : = ∏_{V ∈V} G(π|_{V})[A_{1}, …, A_{n}|_{V}]

= ∑_{{(W,σ)∈PS(n) \atop W≤V}} Wg(V, σπ^{−1}) · φ(W, σ)[A_{1}, …, A_{n}]. (19)

Now we can look on the cumulants of the entries of our unitarily invariant matrices A_{i}; they are given by

k_{V}\{a_{p_{1}r_{1}}^{(1)}, …, a_{p_{n}r_{n}}^{(n)}\} = ∑_{{U∈P(n) \atop U≤V}} Möb_{P(n)}(U, V) · E_{U}[a_{p_{1}r_{1}}^{(1)}, … a_{p_{n}r_{n}}^{(n)}]

= ∑_{U≤V} ∑_{{π∈Sn \atop π≤U}} δ_{r,p∘π} · Möb_{P(n)}(U, V) · G(U, π)[A_{1}, …, A_{n}]

= ∑_{{π∈Sn \atop π≤V}} δ_{r,p∘π} ∑_{{U∈P(n) \atop V≥U≥π}} Möb_{P(n)}(U, V) · G(U, π)[A_{1}, …, A_{n}].

With the definition

(20) κ(V, π)[A_{1}, …, A_{n}] := ∑_{{U∈P(n) \atop V≥U≥π}} Möb_{P(n)}(U, V) · G(U, π)[A_{1}, …, A_{n}].

we thereby get

(21)  k_{V}\{a_{p_{1}r_{1}}^{(1)}, …, a_{p_{n}r_{n}}^{(n)}\} = ∑_{{π∈Sn \atop π≤V}} δ_{r,p∘π} · κ(V, π)[A_{1}, …, A_{n}].

It follows that

φ(U, γ)[A_{1}, …, A_{n}] = ∑_{{V≤U \atop V∨γ=U}} ∑_{i(1),...,i(n)=1}^{N} k_{V}[a_{i(1)i(γ(1))}^{(1)}, …, a_{i(n)i(γ(n))}^{(n)}]

= ∑_{{V≤U \atop V∨γ=U}} ∑_{i(1),...,i(n)=1}^{N} ∑_{{π∈Sn \atop π≤V}} δ_{i∘γ,i∘π} · κ(V, π)[A_{1}, …, A_{n}]

= ∑_{{V≤U \atop V∨γ=U}} ∑_{{π∈Sn \atop π≤V}} κ(V, π)[A_{1}, …, A_{n}] · N^{#(γπ^{−1})}.

Since V ∨ γ = U is, under the assumption π ≤ V, equivalent to V ∨ γπ^{−1} = U we can write this also as

(22)  φ(U, γ)[A_{1}, …, A_{n}] = ∑_{{(V,π)∈PS(n) \atop V∨γπ^{−1}=U}} κ(V, π)[A_{1}, …, A_{n}] · N^{#(γπ^{−1})}.

Remark 4.3. 1) Note that although the quantity κ is defined by (20) in terms of the macroscopic moments of the A_{i}, they have also a very concrete meaning in terms of cumulants of entries of the A_{i}. Namely, if we choose π ∈ S_{n} and distinct 1 ≤ i(1), …, i(n) ≤ N then equation (21) becomes, when we set V = 1_{n},

(23)  κ(1_{n}, π)[A_{1}, …, A_{n}] = k_{n}(a_{i(1)i(π(1))}^{(1)}, …, a_{i(n)i(π(n))}^{(n)})

as the the only term in the sum that survives is the one for π.

2) Equation (22) should be considered as a kind of moment-cumulant formula in our context, thus it should contain all information for defining the “cumulants” κ in terms of the moments φ. Actually, we can solve this linear system of equations for κ in terms of φ, by using equation (20) to define κ and equation (19) for G.

κ(V, π)[A_{1}, …, A_{n}]

= ∑_{{U∈P(n) \atop V≥U≥π}} Möb_{P(n)}(U, V) · ∑_{{(W,σ)∈PS(n) \atop W≤U}} Wg(U, σπ^{−1}) · φ(W, σ)[A_{1}, …, A_{n}]

= ∑_{(W,σ)∈PS(n)} φ(W, σ)[A_{1}, …, A_{n}] · ∑_{{U∈P(n) \atop V≥U≥π∨W}} Möb_{P(n)}(U, V) · Wg(U, σπ^{−1}).

Thus, by using the relative cumulants of the Weingarten function from (14), we get finally

(24) κ(V, π)[A_{1}, …, A_{n}] = ∑_{{(W,σ)∈PS(n) \atop W ≤V}} φ(W, σ)[A_{1}, …, A_{n}] · C_{π∨W,V}(σπ^{−1}).

3) One should also note that we have defined the Weingarten function only for N ≥ n; thus in the above formulas we should always consider sufficiently large N. This is consistent with the observation that the system of equations (22) might not be invertible for N too small; the matrix (N^{#(σπ^{−1})})_{σ,π∈S_{n}} is invertible for N ≥ n, however, in general not for all N < n (e.g, clearly not for N = 1). One can make sense of some formulas involving the Weingarten function also for N < n (see [CŚ06]). However, since we are mainly interested in the asymptotic behavior of our formulas for N → ∞, we will not elaborate on this.

4.3. Product of two independent ensembles. Let us now calculate the correlation functions for a product of two independent ensembles A_{1}, …, A_{n} and B_{1}, …, B_{n} of random matrices, where we assume that one of them, let’s say the B_{i}’s, is unitarily invariant. We have, by using (17) and the special version (12) of the formula of Leonov and Shiryaev, the following: φ(U, γ)[A_{1}B_{1}, …, A_{n}B_{n}]

= ∑_{i(1),··· ,i(n)} ; j(1),··· ,j(n) ∑_{{V,V′≤U \atop V∨V′∨γ=U}} k_{V}[a_{j(1)i(1)}^{(1)}, …, a_{j(n)i(n)}^{(n)}] · k_{V′}[b_{i(1)j(γ(1))}^{(1)}, …, b_{i(n)j(γ(n))}^{(n)}]

=^{(20)} ∑_{i,j} ∑_{{V,V′≤U \atop V∨V′∨γ=U}} ∑_{{π∈Sn \atop π≤V}} δ_{i,j∘π} · κ(V, π)[A_{1}, …, A_{n}] · k_{V′}[b_{i(1)j(γ(1))}^{(1)}, …, b_{i(n)j(γ(n))}^{(n)}]

= ∑_{π∈S_{n}} ∑_{{V∈P(n) \atop U≥V≥π}} κ(V, π)[A_{1}, …, A_{n}]·

· ( ∑_{{V′≤U \atop V′∨V∨γ=U}} ∑_{i} k_{V′}[b_{i(1)i(π^{−1}γ(1))}^{(1)}, …, b_{i(n)i(π^{−1}γ(n))}^{(n)}]).

In order to evaluate the second factor we note first that, under the assumption π ≤ V, the condition V′ ∨ V ∨ γ = U is equivalent to V′ ∨ V ∨ π^{−1}γ = U. Next, we rewrite the sum over all V′ ∈ P(n) with V′ ≤ U and V′ ∨ V ∨ π^{−1}γ = U as a double sum over all W ∈ P(n) with V ∨ W = U and all V′ ∈ P(n) with V′ ≤ W and V′ ∨ π^{−1}γ = W.

∑_{{V′∈P(n) \atop V′≤U,V′∨V∨γ=U}} ∑_{i} k_{V′}[b_{i(1)i(π^{−1}γ(1))}^{(1)}, …, b_{i(n)i(π^{−1}γ(n))}^{(n)}]

= ∑_{{W∈P(n) \atop V∨W=U}} ∑_{{V′≤W \atop V′∨π^{−1}γ=W}} ∑_{i} k_{V′}[b_{i(1)i(π^{−1}γ(1))}^{(1)}, …, b_{i(n)i(π^{−1}γ(n))}^{(n)}]

= ∑_{{W∈P(n) \atop W≥π^{−1}γ,V∨W=U}} φ(W, π^{−1}γ)[B_{1}, …, B_{n}].

Thus we finally get

φ(U, γ)[A_{1}B_{1}, …, A_{n}B_{n}]

= ∑_{π∈S_{n}} ∑_{{V∈P(n) \atop U≥V≥π}} ∑_{{W∈P(n) \atop W≥π^{−1}γ,V∨W=U}} κ(V, π)[A_{1}, …, A_{n}] · φ(W, π^{−1}γ)[B_{1}, …, B_{n}]

= ∑_{{(V,π),(W,σ)∈PS(n) \atop V∨W=U,πσ=γ}} κ(V, π)[A_{1}, …, A_{n}] · φ(W, π^{−1}γ)[B_{1}, …, B_{n}].

Let us summarize the result of our calculations in the following theorem. In order to indicate that our main formulas are valid for any fixed N, we will decorate the relevant quantities with a superscript ^{(N)}. Note that up to now we have not made any asymptotic consideration.

Theorem 4.4. Let M_{N} := M_{N} ⊗ L^{∞}(Ω) be an ensemble of N × N-random matrices. Define correlation functions φ_{n}^{(N)} on M_{N} by (n ∈ ℕ, D_{1}, …, D_{n} ∈ M_{N})

(25)  φ_{n}^{(N)}(D_{1}, …, D_{n}) := k_{n}(Tr(D_{1}), …, Tr(D_{n}))

and corresponding “cumulant functions” κ^{(N)} (for n ≤ N) by (26)

κ^{(N)}(V, π)[D_{1}, …, D_{n}] = ∑_{W∈P(n), σ∈S_{n}} ; W ≤V φ^{(N)}(W, σ)[D_{1}, …, D_{n}] · C_{π∨W,V}^{(N)}(σπ^{−1}),

or equivalently by the implicit system of equations

(27)  φ^{(N)}(U, γ)[D_{1}, …, D_{n}] = ∑_{V,π} κ^{(N)}(V, π)[D_{1}, …, D_{n}] · N^{#(γπ^{−1})},

where the sum is over all V ∈ P(n) all π ∈ S_{n} such that π ≤ V and V ∨γπ^{−1} = U.

1) Let A_{N} be an algebra of unitarily invariant random matrices in M_{N}. Then we have for all n ≤ N, all distinct i(1), …, i(n), all A_{k} = (a_{ij}^{(k)})_{i,j=1}^{N} ∈ A_{N}, and all π ∈ S_{n} that

(28)  κ^{(N)}(1_{n}, π)[A_{1}, …, A_{n}] = k_{n}(a_{i(1)i(π(1))}^{(1)}, …, a_{i(n)i(π(n))}^{(n)}).

2) Assume that we have two subalgebras A_{N} and B_{N} of M_{N} such that ⋄ A_{N} is a unitarily invariant ensemble, ⋄ A_{N} and B_{N} are independent.

Then we have for all n ∈ ℕ with n ≤ N and all A_{1}, …, A_{n} ∈ A_{N} and B_{1}, …, B_{n} ∈ B_{N}:

(29) φ^{(N)}(U, γ)[A_{1}B_{1}, …, A_{n}B_{n}]

= ∑_{V,π,W,σ} κ^{(N)}(V, π)[A_{1}, …, A_{n}] · φ^{(N)}(W, σ)[B_{1}, …, B_{n}],

where the sum is over all V, W ∈ P(n) and all π, σ ∈ S_{n} such that π ≤ V, σ ≤ W, V ∨ W = U, and γ = πσ.

4.4. Large N asymptotics for moments and cumulants. Our main interest in this paper will be the large N limit of formula (29). This structure in leading order between independent ensembles of random matrices which are randomly rotated against each other will be captured in our abstract notion of higher order freeness. Of course, now we must make an assumption about the asymptotic behavior in N of our correlation functions. We will require that the cumulants of traces of our random matrices decays in N with the same order as in the case of Gaussian or Wishart random matrices. In these cases one has very detailed “genus expansions” for those cumulants; see, e.g. [Oko00, MN04] and one knows that the n-th cumulant of unnormalized traces in polynomials of those random matrices decays like N^{2−n} (see e.g. [MS06, Thm. 3.1 and Thm. 3.5]).

Definition 4.5. Let, for each N ∈ ℕ, B_{1}^{(N)}, …, B_{r}^{(N)} ⊂ M_{N} ⊗ L^{∞−}(Ω) be N × N-random matrices. Suppose that the leading term of the correlation moments of B_{1}^{(N)}, …, B_{r}^{(N)} are of order 2 − n, i.e., that for all n ∈ ℕ and all polynomials p_{1}, …, p_{t} in r non-commuting variables the limits

lim_{N→∞} φ_{n}^{(N)}(p_{1}(B_{1}^{(N)}, …, B_{r}^{(N)}), …, p_{t}(B_{1}^{(N)}, …, B_{r}^{(N)})) · N^{n−2}

exist. Then we will say that {B_{1}^{(N)}, …, B_{r}^{(N)}} has limit distributions of all orders. Let B be the free algebra generated by generators b_{1}, …, b_{r}. Then we define the limit correlation functions of B by

φ_{n}(p_{1}(b_{1}, …, b_{r}), …, p_{t}(b_{1}, …, b_{r}))

= lim_{N→∞} φ_{n}^{(N)}(p_{1}(B_{1}^{(N)}, …, B_{r}^{(N)}), …, p_{t}(B_{1}^{(N)}, …, B_{r}^{(N)})) · N^{n−2}

Note that this assumption implies that the leading term for the quantities φ^{(N)}(V, π) is of order 2#(V) − #(π). Indeed, if V has k blocks and the i^{th} block of V contains r_{i} cycles of π then φ^{(N)}(V, π) = φ_{r_{1}} ⋯ φ_{r_{k}} and each φ_{r_{i}} has order 2 − r_{i}. Then the order of φ^{(N)}(V, π) is (2 − r_{1}) + ⋯ + (2 − r_{k}) = 2k − (r_{1} + ⋯ + r_{k}) = 2 #(V) − #(π). Thus

φ(V, π)(p_{1}(b_{1}, …, b_{r}), …, p_{t}(b_{1}, …, b_{r}))

= lim_{N→∞} φ^{(N)}(V, π)(p_{1}(B_{1}^{(N)}, …, B_{r}^{(N)}), …, p_{t}(B_{1}^{(N)}, …, B_{r}^{(N)}))

· N^{−2#(V)+#(π)}

From formula (27) one can deduce that the leading order of κ^{(N)}(V, π) is given by the term (U, γ) = (V, π) and thus must be of order

N^{−n+2#V−#π}.

(Indeed, this also follows from equation (24) and the leading order of the relative cumulant of the Weingarten function given in equation (16).) Thus we can define the limiting cumulant functions to be the limit of the leading order of the cumulants by the equation

(30) κ(V, π)[b_{1}, …, b_{n}] := lim_{N→∞} N^{n−2#V+#π} · κ^{(N)}(V, π)[B_{1}^{(N)}, …, B_{n}^{(N)}]

When (V, π) = (1_{n}, γ_{n}) and B_{1} = B_{2} = ⋯ = B_{n} = B equation (28) becomes

κ^{(N)}(1_{n}, γ_{n})[B, …, B] = k_{n}(b_{i(1)i(2)}^{(N)}, …, b_{i(n)i(1)}^{(N)})

Thus to prove Theorem 2.6 we must show that κ^{(N)}(1_{n}, γ_{n})[B, …, B] · N^{n−1} converges to κ_{n}^{b} the n^{th} free cumulant of the limiting eigenvalue distribution of B^{(N)}. When (V, π) = (1_{m+n}, γ_{m,n}) equation (28) becomes

κ^{(N)}(1_{m+n}, γ_{m,n})[B, …, B] = k_{m+n}(b_{i(1)i(2)}^{(N)}, …, b_{i(m)i(1)}^{(N)}, b_{j(1)j(2)}^{(N)}, …, b_{j(n),j(1)}^{(N)})

Thus to prove Theorem 2.12 we must show that κ^{(N)}(1_{m+n}, γ_{m,n})[B, …, B] · N^{m+n} converges to κ_{m,n}^{b} the (m, n)^{th} free cumulant of second order of the limiting second order distribution of B^{(N)}.

4.5. Length functions. We want to understand the asymptotic behavior of formula (29). The leading order in N of the right hand side is given by

−n + 2#V − #π + 2#W − #σ = n + (|π| − 2|V|) + (|σ| − 2|W|),

whereas the leading order of the left hand side is given by

2#U − #γ = 2#(V ∨ W) − #(σπ) = n + (|πσ| − 2|V ∨ W|).

This suggests the introducing of the following “length functions” for permutations, partitions, and partitioned permutations.

Notation 4.6.

(1) For V ∈ P(n) and π ∈ S_{n} we put

|V| := n − #V
|π| := n − #π.
(2) For any (V, π) ∈ PS(n) we put
|(V, π)| := 2|V| − |π| = n − (2#V − #π).

Let us first observe that these quantities behave actually like a length. It is clear from the definition that they are always non-negative; that they also obey a triangle inequality is the content of the next lemma.

Lemma 4.7.

(1) For all π, σ ∈ S_{n} we have

|πσ| ≤ |π| + |σ|.

(2) For all V, W ∈ P(n) we have

|V ∨ W| ≤ |V| + |W|.

(3) For all partitioned permutations (V, π), (W, σ) ∈ PS(n) we have

|(V ∨ W, πσ)| ≤ |(V, π)| + |(W, σ)|.

Proof. (1) This is well-known, since |π| is the minimal number of factors needed to write π as a product of transpositions.

(2) Each block B of W can glue at most #B − 1 many blocks of V together, i.e., W can glue at most n−#W many blocks of V together, thus the difference between |V| and |V ∨ W| cannot exceed n − #W and hence

#V − #(V ∨ W) ≤ n − #W.

This is equivalent to our assertion.

(3) We prove this, for fixed π and σ by induction over |V| + |W|. The smallest possible value of the latter appears for |V| = |π| and |W| = |σ| (i.e., V = 0_{π} and W = 0_{σ}). But then we have (since V ∨ W ≥ πσ)

2|V ∨ W| − |πσ| ≤ |V ∨ W| ≤ |V| + |W|, which is exactly our assertion for this case. For the induction step, on the other side, one only has to observe that if one increases |V| (or |W|) by one then |V ∨ W| can also increase by at most 1. □

Remark 4.8. 1) Note that the triangle inequality for partitioned permutations together with (29) implies the following. Given random matrices A = (A_{N})_{N∈ℕ} and B = (B_{N})_{N∈ℕ} which have limit distributions of all orders. If A and B are independent and at least one of them is unitarily invariant, then C = (C_{N})_{N∈ℕ} with C_{N} := A_{N}B_{N} also has limit distributions of all orders.

2) Since we know that Gaussian and Wishart random matrices have limit distributions of all orders (see e.g. [MS06, Thm. 3.1 and Thm. 3.5]), and since they are unitarily invariant, it follows by induction from the previous part that any polynomial in independent Gaussian and Wishart matrices has limit distributions of all orders.

4.6. Multiplication of partitioned permutations. Suppose {B_{1}^{(N)}, …, B_{n}^{(N)}} has limit distributions of all orders. Then the left hand side of equation (27) has order N^{2#(U)−#(γ)} and the right hand side of equation (27) has order N^{−n+2#(V)−#(π)+|γπ^{−1}|}. Thus the only terms of the right hand side that have order N^{2#(U)−#(γ)} are those for which

2#(U) − #(γ) = −n + 2#(V) − #(π) + |γπ^{−1}|

i.e. for which |(U, γ)| = |(V, π)| + |γπ^{−1}|. Hence

φ^{(N)}(U, γ)[B_{1}^{(N)}, …, B_{n}^{(N)}]
= ∑_{(V,π)∈PS(n) ; {V∨γπ^{−1}=U \atop |(U,γ)|=|(V,π)|+|γπ^{−1}|}} κ^{(N)}(V, π)[B_{1}^{(N)}, …, B_{n}^{(N)}] · N^{|γπ^{−1}|}

+ O(N^{2#(U)−#(γ)−2})

Thus after taking limits we have

(31)  φ(U, γ)[b_{1}, …, b_{n}] = ∑_{(V,π)∈PS(n)}κ(V, π)[b_{1}, …, b_{n}]

where the sum is over all (V, π) in PS(n) such that V ∨γπ^{−1} = U and |(U, γ)| = |(V, π)| + |γπ^{−1}|. A similar analysis of equation (29) gives that for independent {A_{1}^{(N)}, …, A_{n}^{(N)}} and {B_{1}^{(N)}, …, B_{n}^{(N)}} with the A_{i}^{(N)}’s unitarily invariant and both having limit distributions of all orders we have φ^{(N)}(U, γ)[A_{1}^{(N)}B_{1}^{(N)}, …, A_{n}^{(N)}B_{n}^{(N)}]

= ∑_{(V,π),(W,σ)∈PS(n) ; {V∨W=U, πσ=γ \atop |(V,π)|+|(W,σ)|=|(V∨W,πσ)|}} κ^{(N)}(V, π)[A_{1}^{(N)}, …, A_{n}^{(N)}] · φ^{(N)}(W, σ)[B_{1}^{(N)}, …, B_{n}^{(N)}]

+ O(N^{2#(U)−#(γ)−2})

and again after taking limits

(32) φ(U, γ)[a_{1}b_{1}, …, a_{n}b_{n}]

= ∑_{(V,π),(W,σ)∈PS(n)} κ(V, π)[a_{1}, …, a_{n}] · φ(W, σ)[b_{1}, …, b_{n}]

where the sum is over all (V, π), (W, σ) ∈ PS(n) such that ⋄ V ∨ W = U

⋄ πσ = γ
⋄ |(V, π)| + |(W, σ)| = |(U, γ)|

In order to write this in a more compact form it is convenient to define a multiplication for partitioned permutations (in ℂPS(n)) as follows.

Definition 4.9. For (V, π), (W, σ) ∈ PS(n) we define their product as follows.

(33) (V, π) · (W, σ) :=

= \begin{cases}(V ∨ W, πσ) & if |(V, π)| + |(W, σ)| = |(V ∨ W, πσ)|, \\ 0 & otherwise. \end{cases}

Proposition 4.10. The multiplication defined in Definition 4.9 is associative.

Proof. We have to check that

(34)  ((V, π) · (W, σ)) · (U, τ) = (V, π) · ((W, σ) · (U, τ)).

Since both sides are equal to (V ∨ W ∨ U, πστ) in case they do not vanish, we have to see that the conditions for non-vanishing are for both sides the same. The conditions for the left hand side are

|(V, π)| + |(W, σ)| = |(V ∨ W, πσ)|

and

|(V ∨ W, πσ)| + |(U, τ)| = |(V ∨ W ∨ U, πστ)|.

These imply

|(V, π)| + |(W, σ)| + |(U, τ)| = |(U ∨ W ∨ U, πστ)|
≤ |(V, π)| + |(W ∨ U, στ)|,

However, the triangle inequality

|(W ∨ U, στ)| ≤ |(W, σ)| + |(U, τ)| yields that we have actually equality in the above inequality, thus leading to

|(W, σ)| + |(U, τ)| = |(W ∨ U, στ)|

and

|(V, π)| + |(W ∨ U, στ)| = |(V ∨ W ∨ U, πστ)|.

These are exactly the two conditions for the vanishing of the right hand side of (34). The other direction goes analogously. □

Now we can write formulas (31) and (32) in convolution form

(35)  φ(U, γ)[b_{1}, …, b_{n}] = ∑_{{(V,π)∈PS(n) \atop (V,π)·(0,γπ^{−1})=(U,γ)}} κ(V, π)[b_{1}, …, b_{n}]

and

(36) φ(U, γ)[a_{1}b_{1}, …, a_{n}b_{n}]

= ∑_{{(V,π),(W,σ)∈PS(n) \atop (V,π)·(W,σ)=(U,γ)}} κ(V, π)[a_{1}, …, a_{n}] · φ(W, σ)[b_{1}, …, b_{n}].

Note that both φ(V, π) and κ(V, π) are multiplicative in the sense that they factor according to the decomposition of V into blocks. The philosophy for our definition of higher order freeness will be that equation (35) is the analogue of the moment-cumulant formula and shall be used to define the quantities κ, which will thus take on the role of cumulants in our theory – whereas the φ are the moments (see Definition 7.4). We shall define higher order freeness by requiring the vanishing of mixed cumulants, see Definition 7.6. On the other hand, equation (36) would be another way of expressing the fact that the a’s are free from the b’s. Of course, we will have to prove that those two possibilities are actually equivalent (see Theorem 7.9).

5. Multiplicative functions on partitioned permutations and their convolution

5.1. Convolution of multiplicative functions. Formulas (35) and (36) above are a generalization of the formulas describing first order freeness in terms of cumulants and convolution of multiplicative functions on non-crossing partitions. Since the dependence on the random matrices is irrelevant for this structure we will free ourselves in this section from the random matrices and look on the combinatorial heart of the observed formulas. In Section 7, we will return to the more general situation involving multiplicative functions which depend also on random matrices or more generally elements from an algebra.

Definition 5.1.

(1) We denote by PS the set of partitioned permutations on an arbitrary number of elements, i.e.,

PS = ⋃_{n∈ℕ} PS(n).

(2) For two functions

f, g : PS → ℂ

we define their convolution

f ∗ g : PS → ℂ

by

(f ∗ g)(U, γ) := ∑_{{(V,π),(W,σ)∈PS(n) \atop (V,π)·(W,σ)=(U,γ)}} f(V, π) g(W, σ)

for any (U, γ) ∈ PS(n).

Definition 5.2. A function f : PS → ℂ is called multiplicative if f(1_{n}, π) depends only on the conjugacy class of π and we have

f(V, π) = ∏_{V ∈V} f(1_{V} , π|_{V}).

Our main interest will be in multiplicative functions. It is easy to see that the convolution of two multiplicative functions is again multiplicative. It is clear that a multiplicative function is determined by the values of f(1_{n}, π) for all n ∈ ℕ and all π ∈ S_{n}. An important example of a multiplicative function is the δ-function presented below.

Notation 5.3. The δ-function on PS is the multiplicative function determined by

δ(1_{n}, π) = \begin{cases}1 & if n = 1, \\ 0 & otherwise. \end{cases}

Thus for (U, π) ∈ PS(n)

δ(U, π) = \begin{cases}1 & if (U, π) = (0_{n}, (1)(2) … (n)) for some n, \\ 0 & otherwise. \end{cases}

Proposition 5.4. The convolution of multiplicative functions on PS is commutative and δ is the unit element.

Proof. It is clear that δ is the unit element. For commutativity, we note that for multiplicative functions we have

f(V, π) = f(V, π^{−1}),

and thus

(g ∗ f)(U, γ) = (g ∗ f)(U, γ^{−1}) = ∑_{{(V,π),(W,σ)∈PS(n) \atop (V,π)·(W,σ)=(U,γ^{−1})}} g(V, π)f(W, σ).

Since the condition (V, π) · (W, σ) = (U, γ^{−1}) is equivalent to the condition (W, σ^{−1}) · (V, π^{−1}) = (U, γ) we can continue with

(g ∗ f)(U, γ) = ∑_{{(V,π),(W,σ)∈PS(n) \atop (W,σ^{−1})·(V,π^{−1})=(U,γ)}} f(W, σ^{−1})g(V, π^{−1}) = (f ∗ g)(U, γ).

□

5.2. Factorizations. Let us now try to characterize the non-trivial factorizations (U, γ) = (V, π) · (W, σ) appearing in the definition of our convolution. Let us first observe some simple general inequalities.

Lemma 5.5.

(1) For permutations π, σ ∈ S(n) we have

|π| + |σ| + |πσ| ≥ 2|π ∨ σ|.

(2) For partitions V_{2} ≤ V_{1} and W_{2} ≤ W_{1} we have

|W_{1}| + |V_{1}| + |V_{2} ∨ W_{2}| ≥ |V_{1} ∨ W_{1}| + |W_{2}| + |V_{2}|

and

|V_{1} ∨ W_{2}| + |V_{2} ∨ W_{1}| ≥ |V_{1} ∨ W_{1}| + |V_{2} ∨ W_{2}|.

Proof. (1) By the triangle inequality for partitioned permutations we have

|(0_{π} ∨ 0_{σ}, πσ)| ≤ |(0_{π}, π)| + |(0_{σ}, σ)|,

i.e.,

(37)  2|π ∨ σ| − |πσ| ≤ |π| + |σ|.

(2) Consider first the special case W_{1} = W_{2} = W. Then we clearly have

#(V_{2} ∨ W) − #(V_{1} ∨ W) ≤ #V_{2} − #V_{1},

which leads to

|V_{1} ∨ W| − |V_{2} ∨ W| ≤ |V_{1}| − |V_{2}|.

From this the general case follows by

|V_{1} ∨ W_{1}| − |V_{2} ∨ W_{2}| = |V_{1} ∨ W_{1}| − |V_{1} ∨ W_{2}| + |V_{1} ∨ W_{2}| − |V_{2} ∨ W_{2}|
≤ |W_{1}| − |W_{2}| + |V_{1}| − |V_{2}|.

The second inequality follows from this as follows:

|V_{1} ∨ W_{1}| − |V_{1} ∨ W_{2}| = |V_{1} ∨ (V_{2} ∨ W_{1})| − |V_{1} ∨ (V_{2} ∨ W_{2})|
≤ |V_{2} ∨ W_{1}| − |V_{2} ∨ W_{2}|.
□

Theorem 5.6. For (V, π), (W, σ) ∈ PS(n) the equation

(V, π) · (W, σ) = (V ∨ W, πσ)

is equivalent to the conjunction of the following four conditions:

|π| + |σ| + |πσ| = 2|π ∨ σ|,
|V| + |π ∨ σ| = |π| + |V ∨ σ|,
|W| + |π ∨ σ| = |σ| + |π ∨ W|,
|V ∨ σ| + |π ∨ W| = |V ∨ W| + |π ∨ σ|.

Proof. Adding the four inequalities given by Lemma 5.5

|π| + |σ| + |πσ| ≥ 2|π ∨ σ|,
2|V| + 2|π ∨ σ| ≥ 2|π| + 2|V ∨ σ|,
2|W| + 2|π ∨ σ| ≥ 2|σ| + 2|π ∨ W|,
2|V ∨ σ| + 2|π ∨ W| ≥ 2|V ∨ W| + 2|π ∨ σ|

gives

2|V| − |π| + 2|W| − |σ| ≥ 2|V ∨ W| − |πσ|,

i.e.,

|(V, π)| + |(W, σ)| ≥ |(V ∨ W, πσ).

Since (V, π) · (W, σ) = (V ∨ W, πσ) means that we require equality in the last inequality, this is equivalent to having equality in all the four inequalities. □

The conditions describing our factorizations have a quite geometrical meaning. Let us elaborate on this in the following.

Definition 5.7. Let γ ∈ S(n) be a fixed permutation.

(1) A permutation π ∈ S(n) is called γ-planar if

|π| + |π^{−1}γ| + |γ| = 2|π ∨ γ|.

(2) A partitioned permutation (V, π) ∈ PS(n) is called γ-minimal if

|V ∨ γ| − |π ∨ γ| = |V| − |π|.

Remark 5.8. i ) It is easy to check (for example, by calculating the Euler characteristic) that γ-planarity of π corresponds indeed to a planar diagram, i.e. one can draw a planar graph representing permutations γ and π without any crossings. The most important cases are when γ consists of a single cycle [Bia97] and when γ consists of two cycles [MN04]. ii ) The notion of γ-minimality of (V, π) means that V connects only blocks of π which are not already connected by γ. iii ) If (V, π) satisfies both (1) and (2) of Definition 5.7 then (V, π)(0, π^{−1}γ) = (1, γ), by Theorem 5.6.

Corollary 5.9. Assume that we have the equation

(U, γ) = (V, π) · (W, σ).

Then π and σ must be γ-planar and (V, π) and (W, σ) must be γ-minimal.

5.3. Factorizations of disc and tunnel permutations.

Notation 5.10. i ) We call (V, π) ∈ PS_{n} a disc permutation if V = 0_{π}; the latter is equivalent to the condition |V| = |σ|. For π ∈ S_{n}, by (0, π) we will always mean the disc permutation

(0, π) := (0_{π}, π) ∈ PS(n).

ii ) We call (V, π) ∈ PS_{n} a tunnel permutation if |V| = |π|+1. This means that V is obtained from π by joining a pair of cycles; i.e. one block of V contains exactly two cycles of π and all other blocks contain only one cycle of π.

A motivation for those names comes from the identification between partitioned permutations and so-called surfaced permutations; see the Appendix for more information on this. Our goal is now to understand more explicitly the factorizations of disc and tunnel permutations. (It will turn out that those are the relevant ones for first and second order freeness). For this, note that we can rewrite the crucial condition for our product of partitioned permutations,

2|V| − |π| + 2|W| − |σ| = 2|V ∨ W| − |πσ|,

in the form

(|V| − |π|) + (|W| − |σ|) + (|V| + |W| − |V ∨ W|) = (|V ∨ W| − |πσ|).

Since all terms in brackets are non-negative integers this formula can be used to obtain explicit solutions to our factorization problem for small values of the right hand side. Essentially, this tells us that factorizations of a disc permutation can only be of the form disc × disc; and factorizations of a tunnel permutation can only be of the form disc×disc, disc×tunnel, and tunnel×disc. Of course, one can generalize the following arguments to higher order type permutations, however, the number of possibilities grows quite quickly.

Proposition 5.11.

(1) The solutions to the equation

(1_{n}, γ_{n}) = (0, γ_{n}) = (V, π) · (W, σ)

are exactly of the form

(1_{n}, γ_{n}) = (0, π) · (0, π^{−1}γ_{n}),

for some π ∈ NC(n).

(2) The solutions to the equation

(1_{m+n}, γ_{m,n}) = (V, π) · (W, σ)

are exactly of the following three forms:

(a)

(1_{m+n}, γ_{m,n}) = (0, π) · (0, π^{−1}γ_{m,n}),
where π ∈ S_{NC}(m, n);

(b)

(1_{m+n}, γ_{m,n}) = (0, π) · (W, π^{−1}γ_{m,n}),

where π ∈ NC(m)×NC(n), |W| = |π^{−1}γ_{m,n}|+1, and W connects

a cycle of π^{−1}γ_{m,n} in NC(m) with a cycle in NC(n);

(c)

(1_{m+n}, γ_{m,n}) = (V, π) · (0, π^{−1}γ_{m,n}),

where π ∈ NC(m)×NC(n), |V| = |π|+1, and |W| = |π^{−1}γ_{m,n}|+ 1, and V connects a cycle of π in NC(m) with a cycle in NC(n).

Proof. (1) The correspondence between non-crossing partitions and permutations was studied in detail by Biane [Bia97]. In this case we have

(|V| − |π|) + (|W| − |σ|) + (|V| + |W| − |V ∨ W|) = |1_{n}| − |γ_{n}| = 0.

Since all three terms in brackets are greater or equal to zero, all of them must vanish, i.e.,

|V| = |π|,  thus  V = 0_{π}
|W| = |σ|,  thus  W = 0_{σ}

and

|π| + |σ| = |V| + |W| = |V ∨ W| = |γ| = n − 1.

(2) Now we have

(|V| − |π|) + (|W| − |σ|) + (|V| + |W| − |V ∨ W|) = (|V ∨ W| − |πσ|) = 1,

which means that two of the terms on the left-hand side must be equal to 0, and the other term must be equal to 1. Thus we have the following three possibilities.

(a)

|V| =|π|,  thus  V = 0_{π},
|W| =|σ|,  thus  W = 0_{σ}

and

|π| + |σ| = |V| + |W| = |V ∨ W| + 1 = m + n.

Note that

π ∨ σ = V ∨ W = 1_{m+n},

and thus π connects the two cycles of γ_{m,n}. This means that π is a non-crossing (m, n)-permutation.

(b)

|V| = |π|,  thus  V = 0_{π},
|W| = |σ| + 1,

and

|V| + |W| = |V ∨ W| = m + n − 1.

This implies

|π| + |γ_{m,n}π^{−1}| = m + n − 2,

which means that π must be a disconnected non-crossing (m, n)- annular permutation, i.e.,

π = π_{1} × π_{2}  with  π_{1} ∈ NC(m), π_{2} ∈ NC(n).

(c)

|V| = |π| + 1,
|W| = |σ| + 1, ,  thus  W = 0_{σ}

and

|V| + |W| = |V ∨ W| = m + n − 1.

This implies

|π| + |γ_{m,n}π^{−1}| = m + n − 2,

which means that π must be a disconnected non-crossing (m, n)- annular permutation, i.e.,

π = π_{1} × π_{2}  with  π_{1} ∈ NC(m), π_{2} ∈ NC(n).
□

Example 5.12. We can now use the previous description of factorizations of disc and tunnel permutations to write down explicit first and second order formulas for our convolution of multiplicative functions.

1) In the first order case we have

(38)  (f ∗ g)(1_{n}, γ_{n}) = (f ∗ g)(0, γ_{n}) = ∑_{π∈NC(n)} f(0, π)g(0, π^{−1}γ_{n}).

This equation is exactly the formula for the convolution of multiplicative functions on non-crossing partitions, which is the cornerstone of the combinatorial description of first order freeness [NSp97]. (Note that π^{−1}γ_{n} is in this case the Kreweras complement of π.)

2) In the second order case we have

(f ∗ g)(1_{m+n}, γ_{m,n}) = ∑_{π∈S_{NC}(m,n)} f(0, π)g(0, π^{−1}γ_{m,n})

+ ∑_{{π∈NC(m)×NC(n) \atop |V|=|π|+1}}(f(0, γ_{m,n}π^{−1})g(V, π) + f(V, π)g(0, π^{−1}γ_{m,n})).

We should expect that this formula is the combinatorial key for the understanding of second order freeness. However, in this form it does not match exactly the formulas appearing in [MŚS07]. Let us, however, for a multiplicative function f put, for π ∈ NC(n),

(39)  f̃_{1}(π) := f(1_{n}, π)  (π ∈ NC(n))

and, for π_{1} ∈ NC(m) and π_{2} ∈ NC(n),

(40)  f̃_{2}(π_{1}, π_{2}) =  ∑_{\begin{matrix}V≥π_{1}×π_{2}, \\ |V|=|π|+1, \\ V∨(π_{1}×π_{2})=1_{m+n} \end{matrix}}f(V, π_{1} × π_{2}).

Note that in the definition of f̃_{2} the sum is running over all V which connect exactly one cycle of π_{1} with one cycle of π_{2}.

Then, with h = f ∗ g, we have

h̃_{2}(1_{m}, 1_{n}) = ∑_{π∈S_{NC}(m,n)} f̃_{1}(π)g̃_{1}(π^{−1}γ_{m,n})

+ ∑_{π_{1},π_{2}∈NC(m)×NC(n)}(f̃_{2}(π_{1}, π_{2})g̃_{1}(π_{1}^{−1} × π_{2}^{−1}γ_{m.n})

+ f̃_{1}(π_{1} × π_{2})g̃_{2}(π_{1}^{−1}γ_{m}, π_{2}^{−1}γ_{n})).

In this form we recover exactly the structure of the formula (10) from [MŚS07], which describes second order freeness. The descriptions in terms of f and in terms of f̃_{2} are equivalent. Whereas f is multiplicative, f̃_{2} satisfies a kind of cocycle property. From our present perspective the description of second (and higher) order freeness in terms of multiplicative functions seems more natural. In any case, we see that our convolution of multiplicative functions on partitioned permutations is a generalization of the structure underlying first and second order freeness.

5.4. Zeta and Möbius function. In the definition of our convolution we are running over factorizations of (U, γ) into products (V, π) · (W, σ). In the first order case the second factor is determined if the first factor is given. In the general case, however, we do not have such a uniqueness of the decomposition; if we fix (V, π) there might be different choices for (W, σ). For example, this situation was considered in Proposition 5.11 in the case (2b). However, in the case when (W, σ) is a disc permutation, it must be of the form (0_{π^{−1}γ}, π^{−1}γ) and is thus uniquely determined. Note that factorizations of such a special form appear in our formula (35) and thus deserve special attention.

Notation 5.13. Let (U, γ) ∈ PS be a fixed partitioned permutation. We say that (V, π) ∈ PS is (U, γ)–non-crossing if

(V, π) · (0_{π^{−1}γ}, π^{−1}γ) = (U, γ).

The set of (U, γ)–non-crossing partitioned permutations will be denoted by PS_{NC}(U, γ), see Remark 5.8.

To justify this notation we point out that (1_{n}, γ_{n})–non-crossing partitioned permutations can be identified with non-crossing permutations; to be precise

PS_{NC}(1_{n}, γ_{n}) = {(0_{π}, π) | π ∈ NC(n)}.

Furthermore,

PS_{NC}(1_{m+n}, γ_{m,n}) = {(0_{π}, π) | π ∈ S_{NC}(m, n)}∪

∪ {(V, π_{1} × π_{2}) | π_{1} ∈ NC(m), π_{2} ∈ NC(n), V ≥ π, |V| = |π| + 1

and V connects one cycle of π_{1} to a cycle of π_{2}}.

We can now also use a special multiplicative function, which we will call Zetafunction ζ, to single out such factorizations. It will be useful to be able to invert formula (35), which means we need also the inverse of ζ under our convolution.

This inverse, called the Möbius-function μ, is a key object in the theory and contains a lot of important information.

Notation 5.14.

(1) The Zeta-function ζ is the multiplicative function on PS which is determined by

ζ(1_{n}, π) = \begin{cases}1 & if (1_{n}, π) is a disc permutation, i.e., if 1_{n} = 0_{π}, \\ 0 & otherwise. \end{cases}

(2) The Möbius function μ is the inverse of ζ under convolution, i.e., it is

determined by

ζ ∗ μ = δ = μ ∗ ζ.

Note that in general

ζ(V, π) = \begin{cases}1, & if V = 0_{π} \\ 0, & if V > 0_{π}. \end{cases}

It is also quite easy to see that the Möbius function exists and is uniquely determined as the inverse of the Zeta-function — the determining equations can be solved recursively. Indeed letting μ_{n} = μ(1_{n}, γ_{n}) and μ_{m,n} = μ(1_{m+n}, γ_{m,n}) we have

0 = μ_{1,1} + μ_{2}
0 = μ_{1,2} + 2μ_{1}μ_{1,1} + 2μ_{3} + 2μ_{1}μ_{2}
0 = μ_{2,2} + 4μ_{1}μ_{2,1} + 4μ_{1}^{2}μ_{1,1} + 4μ_{4} + 8μ_{1}μ_{3} + 2μ_{2}^{2} + 4μ_{1}^{2}μ_{2}
0 = μ_{1,3} + 3μ_{1}μ_{2,1} + 3μ_{2}μ_{1,1} + 3μ_{4} + 6μ_{1}μ_{3} + 3μ_{2}^{2} + 3μ_{1}^{2}μ_{2}

0 = μ_{2,3} + 2μ_{1}μ_{1,3} + 3μ_{1}μ_{2,2} + 3μ_{2}μ_{1,2} + 9μ_{1}^{2}μ_{1,2} + 6μ_{1}μ_{2}μ_{1,1} + 6μ_{1}^{3}μ_{1,1}

+ 6μ_{5} + 18μ_{1}μ_{4} + 12μ_{2}μ_{3} + 18μ_{1}^{2}μ_{3} + 12μ_{1}μ_{2}^{2} + 6μ_{1}^{3}μ_{2}

0 = μ_{3,3} + 6μ_{1}μ_{2,3} + 6μ_{2}μ_{1,3} + 6μ_{1}^{2}μ_{1,3} + 9μ_{1}^{2}μ_{2,2} + 18μ_{1}μ_{2}μ_{1,2} + 18μ_{1}^{3}μ_{1,2}

+ 9μ_{2}^{2}μ_{1,1} + 18μ_{1}^{2}μ_{2}μ_{1,1} + 9μ_{1}^{4}μ_{1,1} + 9μ_{6} + 36μ_{1}μ_{5} + 27μ_{2}μ_{4} + 54μ_{1}^{2}μ_{4}

+ 9μ_{3}^{2} + 72μ_{1}μ_{2}μ_{3} + 36μ_{1}^{3}μ_{3} + 12μ_{2}^{3} + 36μ_{1}^{2}μ_{2}^{2} + 9μ_{1}^{4}μ_{2}

This shows how, knowing the first order Möbius function μ_{n}, the second order Möbius function μ_{m,n} can be calculated recursively. One should observe that with these notations we have

(f ∗ ζ)(U, γ) = ∑_{(V,π)∈PS_{NC}(U,γ)} f(V, π).

In the following we will use the notation

ζ^{∗p} = \underbrace{ζ ∗ ⋯ ∗ ζ}_{p-times} .

It is clear, by definition, that ζ^{∗p} counts factorizations into the product of p disc permutations, thus we have the following result.

Proposition 5.15. For (U, γ) ∈ PS and p ≥ 1 we have

ζ^{∗p}(U, γ) := #{(π_{1}, …, π_{p}) | (U, γ) = (0, π_{1}) ⋯ (0, π_{p})}.

Of special interest for us is the case p = 2.

Proposition 5.16. We have for all r ≥ 1 and n(1), …, n(r) ∈ ℕ, n := n(1) + ⋯ + n(r) that

(ζ ∗ ζ)(1_{n}, γ_{n(1),...,n(r)}) = #S_{NC}(n(1), …, n(r)).

Proof. As noted above, (ζ ∗ ζ)(1_{n}, γ_{n(1),··· ,n(r)}) counts the number of factorizations of (1_{n}, γ_{n(1),...,n(r)}) into a product of two disc permutations, i.e., the number of factorizations of the form

(1_{n}, γ_{n(1),...,n(r)}) = (0, π) · (0, π^{−1}γ_{n(1),...,n(r)}),

with

|π| + |π^{−1}γ| = |γ| = n − r

and π ∨ γ = 1_{n}. But this describes exactly connected (n(1), …, n(r))-annular permutations π ∈ S_{NC}(n(1), …, n(r)). □

Notation 5.17. We put

c_{n(1),...,n(r)} := #S_{NC}(n(1), …, n(r)).

Note in particular that c_{n} counts the number of non-crossing partitions of n elements and thus is the Catalan number

c_{n} = \frac{1}{n + 1}\binom{2n}{n},

and that c_{m,n} counts the number of non-crossing (m, n)-annular permutations, and thus [MN04]

c_{m,n} = \frac{2mn}{m + n}\binom{2m − 1}{m}\binom{2n − 1}{n}.

More generally, an explicit formula for the number of factorizations into p factors was derived by Bousquet-Mélou and Schaeffer [BMS00], namely one has (with n := n(1) + ⋯ + n(r))

ζ^{∗p}(1_{n}, γ_{n(1),··· ,n(r)}) = p\frac{[(p − 1)n − 1]!}{[(p − 1)n − r + 2]!} ∏_{i=1}^{r} [n(i)\binom{pn(i) − 1}{n(i)}] ,

and thus in particular

c_{n(1),...,n(r)} = 2\frac{(n − 1)!}{(n − r + 2)!} ∏_{i=1}^{r} [n(i)\binom{2n(i) − 1}{n(i)}] .

For our purposes, however, the following recursive formula for the number of factorizations is more interesting. In the next theorem we will show how to reduce the problem of counting the number of disc factorizations on [n] to counting the factorizations on [n − 1]. This will enable of to obtain a recursive formula for c_{n_{1},...,n_{r}}.

Notation 5.18. Let (U, γ) be a partitioned permutation of [n] with γ(1) ≠ 1. Let γ̂_{k} be the restriction of (1, k)γ(1, γ^{−1}(k)) to the invariant subset [2, n] := {2, 3, 4, …, n}. Then

|γ̂_{k}| = \begin{cases}|γ| & if 1 and k are in different cycles of γ, \\ |γ| − 1 & if k = 1 or γ(1) \\ |γ| − 2 & if 1 and k are in the same cycle of γ, \\ & but k ≠ 1 and k ≠ γ(1), \end{cases}

Let \overline{U} = U|_{[2,n]} be the restriction of U to [2, n], i.e. if the blocks of U are U_{1}, …, U_{r} and 1 ∈ U_{1}, then the blocks of \overline{U} are \overline{U}_{1}, U_{2}, …, U_{r} where \overline{U}_{1} = U_{1} ∩ [2, n]. In the theorem below we sum over a set of partitions P_{k} of [2, n] described as follows. For k = 1, γ(1) or k not in the γ-orbit of 1, P_{k} = \{ \overline{U} \} i.e. P_{k} consists of the single partition \overline{U}. For k in the γ-orbit of 1 but k ≠ 1, γ(1), P_{k} = {Û | γ̂_{k} ≤ Û, |Û| = |U| − 2, and \overline{U} = Û ∨ (k, γ^{−1}(k))\}. In words this means \overline{U}_{1} is split into two blocks: ∘ the first containing the cycle of γ̂_{k} containing γ^{−1}(k) and some (possibly none) of the other cycles of γ contained in U_{1} ∘ the second containing the cycle of γ̂_{k} containing k and the remaining (possibly none) cycles of γ contained in U_{1}.

More explicitly, in the case k is in the γ-orbit of 1 but k ≠ 1, γ(1), let us write γ as as a product of cycles d_{1} ⋯ d_{s} where d_{1} = (1, γ(1), …, γ^{t}(1)) is the cycle that contains 1. Let d′_{1} = (γ(1), γ^{2}(1), …, γ^{−1}(k)) and d′′_{1} = (k, …, γ^{t}(1)). Then γ̂_{k} = d′_{1}d′′_{1}d_{2} ⋯ d_{s}. P_{k} consists of all partitions Û of [2, n] such that Û = \{U′_{1}, U′′_{1}, U_{2}, …, U_{r}\} where U′_{1} ∪ U′′_{1} = \overline{U}_{1}, U′_{1} ∩ U′′_{1} = ∅, U′_{1} contains d′_{1}, U′′_{1} contains d′′_{1}, and each cycle of γ that was in U_{1} is now in either U′_{1} or U′′_{1}, i.e. γ̂_{k} ≤ Û and |Û| = |U| − 2.

Theorem 5.19.

(41)  ζ^{∗^{2}}(U, γ) = ∑_{k=1}^{n} ∑_{Û∈P_{k}} ζ^{∗^{2}}(Û, γ̂_{k})

Proof. We must show that for each factorization (0, π)·(0, σ) of (U, γ) there are k := π(1), Û ∈ P_{k}, and permutations of [2, n], π̂ and σ̂ such that (0, π̂)·(0, σ̂) = (Û, γ̂_{k}). Conversely we must show that given k, Û ∈ P_{k} and a factorization (0, π̂) · (0, σ̂) of (Û, γ̂_{k}) there are π and σ such that (0, π) · (0, σ) = (U, γ) and π(1) = k. Moreover we must show that these two maps are inverses of each other. The relation between π, σ and π̂, σ̂ is given by π̂ = (1, k)π|_{[2,n]}, σ̂ = σ(1, γ^{−1}(k))|_{[2,n]}. So on the level of permutations we have a bijection. The main work of the proof is to show that starting with π and σ we have Û := π̂ ∨ σ̂ ∈ P_{k} and 2|Û| − |γ̂_{k}| = |π̂| + |σ̂|; and then conversely starting with Û ∈ P_{k} and a factorization (0, π̂) · (0, σ̂) of (Û, γ̂_{k}) then 2|U| − |γ| = |π| + |σ| and π ∨ σ = U.

Note that we have for all k

|π̂| = \begin{cases}|π| − 1 & k ≠ 1 \\ |π| & k = 1 \end{cases}

|σ̂| = \begin{cases}|σ| − 1 & k ≠ γ(1) \\ |σ| & k = γ(1) \end{cases}

It is necessary to break the proof into four cases: k is not in the γ-orbit of 1; k is in the γ-orbit of 1 but k ≠ 1, γ(1); k = 1; and k = γ(1). Suppose we have a factorization

(U, γ) = (0, π) · (0, σ),

i.e., γ = πσ, U = π ∨ σ, and

2|U| − |γ| = |π| + |σ|

with k := π(1) not in the γ-orbit of 1. Then|γ̂_{k}| = |γ| and P_{k} contains only the partition of [2, n] which results from U by removing 1, i.e. Û = \overline{U}. Then we have |Û| = |U| − 1. Hence |π̂| + |σ̂| = |π| + |σ| − 2 = 2|U| − |γ| − 2 = |Û| − |γ| = |Û| − |γ̂_{k}|. Also 0_{π}|_{[2,n]} = 0π̂ and 0_{γ}|_{[2,n]} ≤ 0γ̂_{k}. Thus Û = (π ∨ γ)|_{[2,n]} ≤ π̂ ∨ γ̂_{k}. On the other hand the difference between 0_{γ}|_{[2,n]} and 0γ̂_{k} is that the blocks containing 1 and k have been joined. However these points were already connected by π. Thus π̂ ∨ γ̂_{k} ≤ Û, and so Û = π̂ ∨ σ̂, and thus

(Û, γ̂) = (0, π̂) · (0, σ̂).

Conversely, given a factorization (0, π̂) · (0, σ̂) of (Û, γ̂_{k}), let π = (1, k)π̂ and σ = σ̂(1, γ^{−1}(k)). Then π ∨ σ = U because 1 has been connected to the block of Û containing k. Also #(π) = #(π̂) and #(σ) = #(σ̂); thus |π| = |π̂| − 1 and |σ| = |σ̂| − 1, and so |π| + |σ| = 2|U| − |γ|. This establishes the bijection when k is not in the γ-orbit of 1. Let us now consider the case that 1 and k are in the same cycle of γ, but k ≠ 1, γ(1). Again suppose that (0, π) · (0, σ) is a factorization of (U, γ) with π(1) = k. In this case we have that |γ̂_{k}| = |γ| − 2 and so by the triangle inequality, Lemma 4.7

2|π̂ ∨ σ̂| − |γ| + 2 = 2|π̂ ∨ σ̂| − |γ̂|
= |(π̂ ∨ σ̂, π̂σ̂)|
≤ |(0, π̂)| + |(0, σ̂)|
= |π̂| + |σ̂|
= |π| + |σ| − 2
= 2|U| − |γ| − 2,

and thus

|π̂ ∨ σ̂| ≤ |U| − 2.

On the other hand, let us compare

π̂ ∨ σ̂ = π̂ ∨ γ̂  with  U = π ∨ γ.

Note that all our changes of the permutations affected only what happens on the first cycle of γ. Since the transition from γ to γ̂ consists in removing the point 1 and splitting the first cycle of γ into two cycles, we can lose at most one block by going over from π̂ ∨ γ̂ to π ∨ γ. Thus

|π̂ ∨ σ̂| = (n − 1) − #(π̂ ∨ σ̂) ≥ (n − 1) − (#U + 1) = |U| − 2,

so that we necessarily have the equality

|π̂ ∨ σ̂| = |U| − 2.

Thus Û := π̂ ∨ σ̂ ∈ P_{k} and 2|π̂ ∨ σ̂| − |γ̂_{k}| = |π̂| + |σ̂|. Hence (0, π̂) · (0, σ̂) is a factorization of (Û, γ̂_{k}). Conversely let us suppose that k is in the γ-orbit of 1 but k ≠ 1 or γ(1) and Û ∈ P_{k} and (0, π̂) · (0, σ̂) is a factorization of (Û, γ̂_{k}). We must show that π ∨ σ = U and that |π| + |σ| = 2|U| − |γ|. 1 and k are in the same orbit of π and 1 and γ^{−1}(k) are in the same orbit of σ. So the blocks of Û containing d′_{1} and d′′_{1} are joined in π ∨ σ. Thus π ∨ σ = U. Also |Û| = |U| − 2, so |π| + |σ| = |π̂| + |σ̂| + 2 = 2|Û| − |γ̂_{k}| + 2 = |U| − |γ̂_{k}| − 2 = 2|U| − |γ|. Thus (0, π) · (0, σ) is a factorization of (U, γ). This establishes the bijection in the case k is in the γ-orbit of 1 but k ≠ 1 or γ(1). Next suppose that k = 1 and (0, π) · (0, σ) is a factorization of (U, γ) with π(1) = 1. Then |π̂|+|σ̂| = |π|+|σ|−1 = 2|U|−|γ|−1 = 2|Û|−|γ|+1 = 2|Û|−|γ̂_{k}|. Let U_{1} be the block of U containing 1 and \overline{U}_{1} = U_{1} ∩[2, n]. We must show that \overline{U}_{1} is a block of π̂ ∨ γ̂_{k}. Since π ∨ γ = U we know that if d_{i} and d_{j} are cycles of γ contained in U_{1} then π must connect them. Since π|_{\overline{U}_{1}} = π̂|_{\overline{U}_{1}} we see that π̂ connects the corresponding cycles of γ̂_{k} (which are unchanged except for the cycle containing 1). Similarly if f_{1} and f_{2} are cycles of π contained in U_{1} and neither is a singleton then they are connected by γ and thus by γ̂_{k}. Thus (0, π̂) · (0, σ̂) is a factorization of (Û, γ̂_{k}). Conversely suppose that k = 1, Û ∈ P_{k}, and (0, π̂) · (0, σ̂) is a factorization of (Û, γ̂_{k}). We must show that π(1) = 1 and (0, π) · (0, σ) is a factorization of (U, γ). Since π̂∨γ̂_{k} = Û and γ connects 1 to γ(1) ∈ \overline{U}_{1}, we have that π∨γ = U. Also |π| + |σ| = |π̂| + |σ̂| + 1 = 2|Û| − |γ̂_{k}| + 1 = 2|U| − |γ̂_{1}| − 1 = 2|U| − |γ|. Thus (0, π) · (0, σ) is a factorization of (U, γ). This completes the case when k = 1. The proof in the case k = γ(1) is exactly the same except that the roles of π and σ are reversed. □

Let us take a closer look at the meaning of Theorem 5.19 for the case (U, γ) = (1_{n}, γ_{n(1),...,n(r)}). To reduce the depth of subscripts we shall write c(n_{1}, …, n_{r}) for c_{n(1),...,n(r)}.

Proposition 5.20. We have for all r, n_{1}, …, n_{r} ∈ ℕ the recursion

(42) c(n_{1}, …, n_{r}) = ∑_{l=2}^{r} n_{l} · c(n_{1} + n_{l} − 1, n_{2}, …, n_{l−1}, n_{l+1}, …, n_{r})

+ ∑_{k=1}^{n_{1}} ∑_{A={i_{1},...,i_{s}}} ; B={j_{1},...,j_{t}} c(k − 1, n_{i_{1}}, …, n_{i_{s}})c(n_{1} − k, n_{j_{1}}, …, n_{j_{t}})

where the sum is over all pairs of subsets A, B ⊂ [2, r] such that A ∩ B = ∅ and A ∪ B = [2, r] including the possibility that either A or B could be empty. We have for all m, n ≥ 1

c_{n} = ∑_{1≤k≤n} c_{k−1}c_{n−k},

and

(43)  c_{m,n} = ∑_{1≤k≤n} (c_{k−1}c_{m,n−k} + c_{m,k−1}c_{n−k}) + mc_{m+n−1},

where we use the convention that c_{0} = 1 but c(n_{1}, …, n_{r}) = 0 if r > 1 and for some i, n_{i} = 0.

Proof. Let n = n_{1} + ⋯ + n_{r}. By Proposition 5.16 c(n_{1}, …, n_{r}) = ζ^{∗^{2}}(1_{n}, γ_{n_{1},...,n_{r}}). So we must give the correspondence between the terms on the right hand side of (41) and the right hand side of (42). In this case U = 1_{n} and \overline{U} = 1_{n−1} (in the notation of 5.18). Thus P_{k} = {1_{n−1}}. Also for n_{1} + ⋯ + n_{l−1} < k ≤ n_{1}+⋯+n_{l}, ζ^{∗^{2}}(1_{n−1}, γ̂_{k}) = c(n_{1}+n_{l} −1, n_{2}, …, n_{l−1}, n_{l+1}, …, n_{r}). Thus

∑_{k=n_{1}+1}^{n} ∑_{Û∈P_{k}} ζ^{∗^{2}}(Û, γ̂_{k}) = ∑_{k=n_{1}+1}^{n} ζ^{∗^{2}}(1_{n−1}, γ̂_{k}) (44)

= ∑_{l=2}^{r} ∑_{k=n_{1}+···+n_{l−1}+1}^{n_{1}+···+n_{l}} c(n_{1} + n_{l} − 1, n_{2}, …, n_{l−1}, n_{l+1}, …, n_{r})

= ∑_{l=2}^{r} n_{l} · c(n_{1} + n_{l} − 1, n_{2}, …, n_{l−1}, n_{l+1}, …, n_{r})

For k ≤ n_{1}, γ̂_{k} = d′_{1}d′′_{1}d_{2} ⋯ d_{r}, with d′_{1} a cycle of length k − 1 and d′′_{1} a cycle of length n_{1} − k. P_{k} is the set of all partitions of the cycles of γ̂_{k} into two blocks such that d′_{1} and d′′_{1} are in different blocks. Hence

∑_{Û∈P_{k}} ζ^{∗^{2}}(Û, γ̂_{k}) = ∑_{A={i_{1},...,i_{s}}} ; B={j_{1},...,j_{t}} c(n_{1} − k, n_{i_{1}}, …, n_{i_{s}})c(k − 1, n_{j_{1}}, …, n_{j_{t}})

where the sum is over all pairs of subsets A, B ⊂ [2, r] such that A ∩ B = ∅ and A ∪ B = [2, r] including the possibility that either A or B could be empty.

Thus

(45) ∑_{k=1}^{n_{1}} ∑_{Û∈P_{k}} ζ^{∗^{2}}(Û, γ̂_{k})

= ∑_{k=1}^{n_{1}} ∑_{A={i_{1},...,i_{s}}} ; B={j_{1},...,j_{t}} c(n_{1} − k, n_{i_{1}}, …, n_{i_{s}})c(k − 1, n_{j_{1}}, …, n_{j_{t}})

Assembling equations (44) and (45) gives the result. □

In [OZ84], O’Brien and Zuber used a similar formula of this kind in order to compute the asymptotics of, so called, external field matrix integral. See also [BMS00] and Theorem 5.22. Clearly, our notions around the convolution of functions on PS are analogous to (and motivated by) the convolution of functions on posets. Even though we are not able to put the above theory into the framework of posets, it seems that this analogy goes quite far. The following description of the Möbius functions is an instance of this—its poset analogue is due to Hall (see [Rot64]). It is essentially the simple observation that one can expand the Möbius function in terms of a geometric series as

μ = ζ^{∗−1} = (δ + (ζ − δ))^{∗−1} = ∑_{k=0}^{∞}(−1)^{k}(ζ − δ)^{∗k}.

Proposition 5.21. We have for any (U, γ) ∈ PS that

μ(U, γ) = δ(U, γ) + ∑_{k=1}^{∞} ∑_{{(U,γ)=(0,π_{1})···(0,π_{k}) \atop π_{i}≠e ∀i}}(−1)^{k}.

Proof. As noted above this is just the geometric series for

(δ + (ζ − δ))^{∗−1}.

(Note that we are working for this in the algebra of functions on PS with the pointwise sum and the convolution as sum and product—we are not bothering about multiplicativity.) The only thing to check is that the sum is finite, and this is the case because the number of factors k is bounded by |(U, γ)|, since |(0, π)| ≥ 1 for any π ≠ e. □

This description of the Möbius function allows us now to derive a recursive formula for μ.

Theorem 5.22. Consider (U, γ) ∈ PS such that γ(1) ≠ 1. Then we have

(46)  μ(U, γ) = (−1) ∑_{{(0,(1,k))·(V,π)=(U,γ) \atop k≠1}} μ(V, π),

where the sum runs over all decompositions of (U, γ) into a product of a disc transposition (0, (1, k)) (with k ≥ 2) and a (V, π) ∈ PS.

The proof of this theorem will rely on the following lemma.

Lemma 5.23. Let (U, γ) ∈ PS such that γ(1) ≠ 1. For p ∈ ℕ, we denote by S_{p} the set consisting of all tuples (π_{1}, …, π_{p}) of permutations such that π_{i} ≠ e for all i = 1, …, p and

(0, π_{1}) ⋯ (0, π_{p}) = (U, γ).

We consider now the two sums

(47)  S_{1} := ∑_{p=1}^{∞} ∑_{(π_{1},...,π_{p})∈S_{p}}(−1)^{p}

and

(48)  S_{2} := ∑_{p=1}^{∞} ∑_{{(π_{1},...,πp)∈Sp \atop π_{1} = (1, k) for k ≠ 1}}(−1)^{p}

where the second sum S_{2} is over all tuples (π_{1}, …, π_{p}) as for the first sum S_{1}, but now with the additional property that π_{1} is a transposition interchanging the element 1 with some other element. Then the two sums (47) and (48) are equal,

S_{1} = S_{2}.

Proof. Let π = (π_{1}, …, π_{p}) ∈ S_{p}. Let 1 ≤ q ≤ p denote the smallest index for which 1 is not a fixed point of π_{q}; note that such a q necessarily exists since γ(1) ≠ 1. We shall group all factorizations into three classes: 1a), 1b) and 2). Class 1) consists of factorizations for which π_{q} is a transposition interchanging 1 with some other element. The subclass 1a) consists of factorizations for which q = 1 and subclass 1b) of those for which q ≥ 2. Class 2) consists of all other factorizations. Let Π = (π_{1}, …, π_{p}) be a factorization from the class 1b). We define

Π′ = (π′_{1}, …, π′_{p−1}) = (π_{1}, …, π_{q−2}, π_{q−1}π_{q}, π_{q+1}, …, π_{p}).

In the following we shall prove that f : Π ↦ Π′ is a bijection between factorizations of class 1b) and factorizations of class 2). Firstly, we prove that Π′ ∈ S_{p} and is of class 2). Clearly, π′_{q−1} = π_{q−1}π_{q} is a permutation which does not fix 1, it is not a transposition interchanging 1 with some other element, and we have

(0, π_{q−1}) · (0, π_{q}) = (0, π′_{q−1}).

In order to show that f is a bijection we shall describe its inverse. If Π′ = (π′_{1}, …, π′_{p−1}) ∈ S_{p} and is of class 2), we define 1 ≤ q ≤ p − 1 to be the smallest number for which π′_{q−1} does not fix 1. There is a unique decomposition π′_{q−1} = π_{q−1}π_{q} such that 1 is a fixed point of π_{q−1} and π_{q} is a transposition interchanging 1 with some other element. Thus |π_{q−1}| + |π_{q}| = |π′_{q−1}|. The assumption that the factorization Π′ is of class 2) implies that π_{q−1} ≠ e. For 1 ≤ i ≤ q − 2 we set π_{i} = π′_{i} and for q + 1 ≤ i ≤ p we set π_{i} = π′_{i−1}. In this way we defined Π = (π_{1}, …, π_{p}). Now it is easy to check that g : Π′ ↦ Π is a left and right inverse of f. Since the factorization Π and the corresponding Π′ contribute to (47) with the opposite signs, the contribution of all factorizations of class 1b) cancels with the contribution of factorizations of class 2). □

Proof of 5.22. In the proof we will consider all factorizations (0, π_{1}) · (0, π_{2}) ⋯ (0, π_{p}) = (U, γ) with the requirement that π_{i} ≠ e for all i, i.e. (π_{1}, …, π_{p}) ∈ S_{p}, as in the proof of Lemma 5.23. Sometimes we will require in addition that π_{1} = (1, k) with k ≠ 1. To simplify the notation we will not explicitly state every time that π_{i} ≠ e. Since γ(1) ≠ 1 we have δ(U, γ) = 0. When γ is a transposition the right hand side of equation (46) is −1; so we can assume that γ is not a transposition. So by Proposition 5.21 we have

μ(U, γ) = ∑_{p=1}^{∞} ∑_{(0,π_{1})···(0,π_{p})} ; =(U,γ)(−1)^{p} =^{(5.23)} ∑_{p=1}^{∞} ∑_{(0,(1,k))···(0,π_{p})} ; =(U,γ)(−1)^{p}

= ∑_{p=2}^{∞} ∑_{(0,(1,k)),(V,π)} ; (0,(1,k))·(V,π)=(U,γ) ∑_{(0,π_{2})···(0,π_{p})} ; =(V,π)(−1)^{p}

= − ∑_{(0,(1,k)),(V,π)} ; (0,(1,k))·(V,π)=(U,γ) ∑_{p=2}^{∞} ∑_{(0,π_{2})···(0,π_{p})} ; =(V,π)(−1)^{p−1}

= − ∑_{(0,(1,k)),(V,π)} ; (0,(1,k))·(V,π)=(U,γ) ∑_{p=2}^{∞} ∑_{(0,π_{2})···(0,π_{p})} ; =(V,π)(−1)^{p−1}

= − ∑_{(0,(1,k)),(V,π)} ; (0,(1,k))·(V,π)=(U,γ) μ(V, π)

□

One observes that the recursion formulas for the Möbius function and for ζ^{∗2} look very similar. However, there are some significant differences. The recursion for ζ^{∗2} effectively expresses ζ^{∗2} for n points in terms of ζ^{∗2} for n − 1 points. The recursion for the Möbius function does not reduce the number of points. Nevertheless, at least for first and second order one can match the two recursions and connect the values of the Möbius function with the values of the function ζ^{∗2} (i.e., with the number of non-crossing partitions and non-crossing annular permutations). In order to see this let us first specify the meaning of Theorem 5.22 for first and second order. In first order we get

μ(1_{n}, γ_{n}) = − ∑_{1≤k≤n−1} μ(1_{k}, γ_{k})μ(1_{n−k}, γ_{n−k}),

which shows that (−1)^{n}μ(1_{n+1}, γ_{n+1}) and ζ^{∗2}(1_{n}, γ_{n}) satisfy the same recursion (namely the one for the Catalan numbers). This is, of course, just the well-known fact [Kre72, Spe94] that the Möbius function on non-crossing partitions is given by the signed and shifted Catalan numbers. In second order our recursion reads

(−1)μ(1_{m+n}, γ_{m,n}) = m · μ(1_{m+n}, γ_{m+n})

+ ∑_{1≤k≤n−1} (μ(1_{m+k}, γ_{m,k})μ(1_{n−k}, γ_{n−k}) + μ(1_{m+n−k}, γ_{m,n−k})μ(1_{k}, γ_{k})),

which we recognize — by taking into account the shifted relation between μ and ζ^{∗2} on the first level — as the recursion for (−1)^{m+n}ζ^{∗2}(1_{m+n}, γ_{m,n}). Let us collect these explicit results about the Möbius function in the following theorem.

Theorem 5.24. We have for m, n ∈ ℕ that

μ(1_{n}, γ_{n}) = (−1)^{n−1} · #NC(n − 1) = (−1)^{n−1} · c_{n−1}

and

μ(1_{m+n}, γ_{m,n}) = (−1)^{m+n} · #S_{NC}(m, n) = (−1)^{m+n} · c_{m,n}.

For higher orders we were not able to match the values of μ with those of ζ^{∗2}.

6. R-transform formulas

Let us consider the situation that two multiplicative functions f and h on PS are related by h = f ∗ ζ. We want to understand what this means for the relations between the numbers κ_{n} := f(1_{n}, γ_{n}) and κ_{m,n} := f(1_{m+n}, γ_{m,n}) on one side and the numbers α_{n} := h(1_{n}, γ_{n}) and α_{m,n} := h(1_{m+n}, γ_{m,n}) on the other side. In particular, we want to express this in terms of the generating power series of these numbers,

C(x) := 1 + ∑_{n≥1} κ_{n}x^{n}, C(x, y) := ∑_{m,n≥1} κ_{m,n}x^{m}y^{n}

and

M(x) := 1 + ∑_{n≥1} α_{n}x^{n}, M(x, y) := ∑_{m,n≥1} α_{m,n}x^{m}y^{n}.

(Note that the above summation corresponds to putting formally

f(1_{0}, γ_{0}) := 1  and  f(1_{0}, γ_{0,0}) := 0

for a multiplicative f. Our notation is motivated by the fact that the most important realization of the relation h = f ∗ ζ will be the situation where the α’s are the correlation moments and the κ’s the corresponding cumulants, thus M is a moment series and C is a cumulant series.) On the first order level we have

α_{n} = ∑_{π∈NC(n)} f(0_{π}, π),

which is the usual moment-cumulant formula of free probability theory, and it is well-known [Spe94] that this is equivalent to

C(xM(x)) = M(x).

Our main goal now is to derive the analogue of this for the second order level. There we have

α_{m,n} = ∑_{π∈S_{NC}(m,n)} f(0_{π}, π) + ∑_{{π_{1}×π_{2}∈NC(m)×NC(n) \atop |V|=|π_{1}×π_{2}|+1}} f(V, π_{1} × π_{2}).

It turns out that the second term, the sum over disconnected partitions, is quite easy to deal with. The first term, the sum over connected annular permutations, looks much more involved, however, one can handle this also if one realizes that one can reduce this first term to the second one. Namely, one can sum over all connected annular permutations by first bundling all throughcycles into one through-cycle and secondly decomposing this through-cycle into sub-cycles all of which are through-cycles. In this way one can reduce the problem of dealing with all annular non-crossing permutations to the problem of considering permutations with exactly one through-cycle and the problem of considering permutations where all cycles are through-cycles. The first problem corresponds exactly to the above sum over disconnected partitions. So we can write

∑_{π∈S_{NC}(m,n)} f(0_{π}, π) = ∑_{{π_{1}×π_{2}∈NC(m)×NC(n) \atop |V|=|π_{1}×π_{2}|+1}} f̃(V, π_{1} × π_{2}),

where f̃ is now the multiplicative function corresponding to

f̃(1_{n}, γ_{n}) = κ̃_{n},  f̃(1_{m+n}, γ_{m,n}) = κ̃_{m,n}

with

κ̃_{n} := κ_{n}

and

κ̃_{m,n} := ∑_{π∈S_{NC}^{all}(m,n)} f(0_{π}, π).

Thus we can combine this to get finally

α_{m,n} = ∑_{{π_{1}×π_{2}∈NC(m)×NC(n) \atop |V|=|π_{1}×π_{2}|+1}}(f(V, π_{1} × π_{2}) + f̃(V, π_{1} × π_{2}))

= ∑_{{π_{1}×π_{2}∈NC(m)×NC(n) \atop |V|=|π_{1}×π_{2}|+1}} g(V, π_{1} × π_{2}),

where g is the multiplicative function corresponding to

g(1_{n}, γ_{n}) = α̃_{n}, g(1_{m+n}, γ_{m,n}) = α̃_{m,n}

with

α̃_{n} = κ̃_{n} = κ_{n}

and

α̃_{m,n} = κ_{m,n} + κ̃_{m,n}.

So we have to translate the relation between κ̃_{m,n} and f and the relation between α_{m,n} and g into relations between the corresponding formal power series.

Proposition 6.1. Let f be a multiplicative function on PS with

f(1_{n}, γ_{n}) =: κ_{n}  and  C(x) := 1 + ∑_{n≥1} κ_{n}x^{n}.

Put

κ̃_{m,n} := ∑_{π∈S_{NC}^{all}(m,n)} f(0_{π}, π),

where S_{NC}^{all}(m, n) denotes the permutations in S_{NC}(m, n) for which all cycles are through-cycles. Consider the corresponding generating power series

C̃(x, y) := ∑_{m,n≥1} κ̃_{m,n}x^{m}y^{n}.

Then we have

C̃(x, y) = −xy \frac{∂^{2}}{∂x∂y} log(\frac{xC(y) − yC(x)}{x − y}),

or equivalently

C̃(x, y) = −xy(\frac{(C(x) − xC′(x))(C(y) − yC′(y))}{(xC(y) − yC(x))^{2}} − \frac{1}{(x − y)^{2}} ).

Proof. Note that we can parameterize an element π ∈ S_{NC}^{all}(m, n) in a bijective way by specifying the number of cycles, the number of elements on each circle for all cycles, the position of a fixed element (let’s say 1) in its cycle and the first element on the other circle of this cycle. Let us denote the number of cycles by r, the number of elements of the cycles on the first circle by i_{1}, …, i_{r} and the number of elements of those cycles on the other circle by j_{1}, …, j_{r}. Thus the l-th cycle contains i_{l} + j_{l} elements and makes the contribution κ_{i_{l}+j_{l}} in the calculation of κ̃_{m,n}. We normalize things so that the first cycle contains the element 1. Fixing i_{1}, …, i_{r} and j_{1}, …, j_{r} we thus have i_{1} possibilities for where 1 sits in the first cycle and n possibilities for the first element of this cycle on the other circle. This means we have

κ̃_{m,n} = ∑_{r≥1} ∑_{{i_{1},...,ir ≥1 \atop i_{1}+···+ir =m}} ∑_{{j_{1},...,jr ≥1 \atop j_{1}+···+jr =n}} i_{1}nκ_{i_{1}+j_{1}} ⋯ κ_{i_{r}+j_{r}}

Fluctuations of Random Matrices 49

and thus

C̃(x, y) = ∑_{r≥1} ∑_{i_{1},...,i_{r}≥1} ∑_{j_{1},...,j_{r}≥1} i_{1}(j_{1} + ⋯ j_{r})κ_{i_{1}+j_{1}} ⋯ κ_{i_{r}+j_{r}}x^{i_{1}} ⋯ x^{i_{r}}y^{j_{1}} ⋯ y^{j_{r}}

= ∑_{r≥1} ∑_{i_{1},...,i_{r}≥1} ∑_{j_{1},...,j_{r}≥1} i_{1}y \frac{∂}{∂y} (κ_{i_{1}gb+j_{1}} ⋯ κ_{i_{r}+j_{r}}x^{i_{1}} ⋯ x^{i_{r}}y^{j_{1}} ⋯ y^{j_{r}})

= ∑_{r≥1} y \frac{∂}{∂y} (( ∑_{i_{1},j_{1}≥1} i_{1}κ_{i_{1}+j_{1}}x^{i_{1}}y^{j_{1}}) · ( ∑_{i_{2},j_{2}≥1} κ_{i_{2}+j_{2}}x^{i_{2}}y^{j_{2}}) ⋯ ( ∑_{i_{r},j_{r}≥1} κ_{i_{r}+j_{r}}x^{i_{r}}y^{j_{r}}))

Let us now use the notation

Ĉ(x, y) := ∑_{i,j≥1} κ_{i+j}x^{i}y^{j}.

Then we can continue with

C̃(x, y) = ∑_{r≥1} y \frac{∂}{∂y} ((x\frac{∂}{∂x}Ĉ(x, y)) · Ĉ(x, y)^{r−1})

= ∑_{r≥1} xy \frac{∂}{∂y} (\frac{1}{r} \frac{∂}{∂x}(Ĉ(x, y)^{r}))

= xy \frac{∂}{∂y} \frac{∂}{∂x}(∑_{r≥1} \frac{1}{r}Ĉ(x, y)^{r})

= −xy \frac{∂}{∂y} \frac{∂}{∂x} log(1 − Ĉ(x, y))

The assertions follow now by noting that

Ĉ(x, y) = 1 − \frac{xC(y) − yC(x)}{x − y}

and by working out the partial derivatives. □ Proposition 6.2. Let g be a multiplicative function on PS. Put

α̃_{m,n} := g(1_{m+n}, γ_{m,n})

and denote its generating power series of second order by

H(x, y) := ∑_{m,n≥1} α̃_{m,n}x^{m}y^{n}.

Put

α_{n} := (g ∗ ζ)(1_{n}, γ_{n})

and

α_{m,n} := ∑_{{(V,π_{1}×π_{2}) \atop |V|=|π_{1}×π_{2}|+1}} g(V, π)

and denote the corresponding generating functions by

M(x) := 1 + ∑_{n≥1} α_{n}x^{n}  and  M(x, y) := ∑_{m,n≥1} α_{m,n}x^{m}y^{n}.

Documenta Mathematica 12 (2007) 1–70

Then we have the relation

M(x, y) = H(xM(x), yM(y)) · (1 + x\frac{M′(x)}{M(x)}) · (1 + y \frac{M′(y)}{M(y)}).

Proof. Let us do the summation in the definition of α_{m,n} in the way that we first fix the two cycles V_{1} ∈ π_{1} and V_{2} ∈ π_{2} which are connected by V and sum over all possibilities for fixed V_{1}, V_{2}. If V_{1} has k elements and V_{2} has l elements then this contributes the factor α̃_{k,l}. Furthermore, π_{1}\V_{1} decomposes into k independent non-crossing partitions and the summations over them (for fixed V_{1}) gives the α_{i} for the intervals between consecutive elements from V_{1}. (Of course, we are counting here modulo m.) For the final summation over V_{1} we have to notice that there are two different possibilities: either a fixed number (let’s say 1) is an element of V_{1} - in which case we can specify the situation by prescribing the number k of elements of V_{1} and the differences i_{1}, …, i_{k} between consecutive elements in V_{1} - or 1 is not an element of V_{1}, — in which case we need an extra factor i_{1}, because we have now i_{1} different possibilities how 1 can lie between two consecutive elements of V_{1}. Since we have the same situation for V_{2} we can thus write α_{m,n} in the form

α_{m,n} = ∑_{k,l≥1} ∑_{{i_{1},...,i_{k}≥0 \atop k+i_{1}+···+i_{k}=m}} ∑_{{j_{1},...,j_{l}≥0 \atop l+j_{1}+···+j_{l}=n}} α̃_{k,l}α_{i_{1}} ⋯ α_{i_{k}}α_{j_{1}} ⋯ α_{j_{l}}(1 + i_{1} + j_{1} + i_{1}j_{1}).

Translating this into generating power series gives the assertion. □

The combination of the previous two propositions, with

H(x, y) = C(x, y) + C̃(x, y),

gives now our main result.

Theorem 6.3. Let f and h be multiplicative functions on PS which are related by

h = f ∗ ζ.

Denote

κ_{n} := f(1_{n}, γ_{n}), κ_{m,n} := f(1_{m+n}, γ_{m,n})

and

α_{n} := h(1_{n}, γ_{n}), α_{m,n} := h(1_{m+n}, γ_{m,n})

and define the corresponding generating power series

C(x) := 1 + ∑_{n≥1} κ_{n}x^{n}, C(x, y) := ∑_{m,n≥1} κ_{m,n}x^{m}y^{n}

and

M(x) := 1 + ∑_{n≥1} α_{n}x^{n}, M(x, y) := ∑_{m,n≥1} α_{m,n}x^{m}y^{n}.

Then we have as formal power series the first order relation

(49)  C(xM(x)) = M(x)

and for the second order

(50)  M(x, y) = H(xM(x), yM(y)) · \frac{\frac{d}{dx}(xM(x))}{M(x)} · \frac{\frac{d}{dy} (yM(y))}{M(y)},

where

(51)  H(x, y) := C(x, y) − xy \frac{∂^{2}}{∂x∂y} log(\frac{xC(y) − yC(x)}{x − y}),

or equivalently,

(52) M(x, y) = C(xM(x), yM(y)) · \frac{\frac{d}{dx}(xM(x))}{M(x)} · \frac{\frac{d}{dy} (yM(y))}{M(y)}

+ xy( \frac{\frac{d}{dx}(xM(x)) · \frac{d}{dy} (yM(y))}{(xM(x) − yM(y))^{2}} − \frac{1}{(x − y)^{2}} ).

Proof. The formulation (50) and (51) follows directly from a combination of Propositions 6.1 and 6.2. In order to reformulate this to (52) one uses the equivalence of the two formulas in Proposition 6.1 and the fact that C(xM(x)) = M(x) yields

1 − xC′(xM(x)) = \frac{M(x)}{\frac{d}{dx}(xM(x))}.

□

If we go over from the moment generating series M to a kind of Cauchy transform like quantity G, then these formulas take on a particularly nice form.

Corollary 6.4. Consider the same situation and notations as in Theorem 6.3. In terms of

G(x) := \frac{1}{x}M(1/x), G(x, y) := \frac{1}{xy} M(1/x, 1/y), R(x, y) := \frac{1}{xy} C(x, y)

the Equation (52) can be written as

(53) G(x, y) = G′(x)G′(y)\{R(G(x), G(y)) + \frac{1}{(G(x) − G(y))^{2}} \}−\frac{1}{(x − y)^{2}} .

R(x, y) is the second order R-transform. Note that Voiculescu’s first order R-transform R is defined by the relation C(x) = 1 + xR(x), and equation (49) says for this

\frac{1}{G(x)} + R(G(x)) = x,

i.e., that G(x) and K(x) := \frac{1}{x} + R(x) are inverses of each other under composition.

Example 6.5. Let us apply our formulas to some examples.

1) If we put f to be the multiplicative function with κ_{2} = 1 and all other κ_{n} and all κ_{m,n} vanishing, then h = f ∗ ζ counts the non-crossing pairings, i.e., in this case M(x) is the generating function of the number of non-crossing pairings (on one circle) and M(x, y) is the generating function of the number of non-crossing annular pairings (on two circles). Let us calculate it by using the above theorem. We have

C(x) = 1 + x^{2}, C(x, y) = 0

and we know that M is the generating function of number of non-crossing pairings on a circle. In this case

Ĉ(x, y) = xy,

and thus

H(x, y) = −xy \frac{∂^{2}}{∂x∂y} log(1 − xy) = \frac{xy}{(1 − xy)^{2}} ,

which yields the result

M(x, y) = xy · \frac{\frac{d}{dx}(xM(x)) · \frac{d}{dy} (yM(y))}{(1 − xyM(x)M(y))^{2}}.

Related formulas are known in the physical literature, see, e.g, [FMP78], [AJM90], [ACKM93] and also [BZ93], [KKP95].

2) If we put f = ζ then h = ζ ∗ ζ counts the non-crossing permutations, i.e., in this case M(x) is the generating function of the number of non-crossing permutations (which is the same as non-crossing partition) on one circle and M(x, y) is the generating function of the number of annular non-crossing permutations (on two circles). We have

C(x) = \frac{1}{1 − x}, C(x, y) = 0.

In this case

Ĉ(x, y) = \frac{1 − x − y}{(1 − x)(1 − y)},

and thus

H(x, y) = −xy \frac{∂^{2}}{∂x∂y} log(1 − xy) = \frac{xy}{(1 − x − y)^{2}} ,

which yields

M(x, y) = xy · \frac{\frac{d}{dx}(xM(x)) · \frac{d}{dy} (yM(y))}{(1 − xM(x) − yM(y))^{2}}.

3) Let us finally see whether we can extract the value of the Möbius function from our formula. Since we have δ = μ ∗ ζ, our formula with

M(x) = 1 + x, M(x, y) = 0

should allow to solve for C(x, y) which is then the generating function for the annular Möbius function. Note that we already know M(x) in this case to be the generating function of the disc Möbius function.

If M(x, y) vanishes identically this implies that H(x, y) vanishes identically, leading to the identity

C(x, y) = xy \frac{∂^{2}}{∂x∂y} log(\frac{xC(y) − yC(x)}{x − y})

= xy(\frac{(C(x) − xC′(x)) · (C(y) − yC′(y))}{(xC(y) − yC(x))^{2}} − \frac{1}{(x − y)^{2}} )

7. Higher order freeness and corresponding cumulants

7.1. Abstract framework.

Definition 7.1. A higher-order (non-commutative) probability space, or briefly HOPS, (A, φ) consists of a unital algebra A and a collection φ = (φ_{n})_{n∈ℕ} of maps (n ∈ ℕ)

φ_{n} : \underbrace{A × ⋯ × A}_{n times} → ℂ,

which are linear and tracial in each of its n arguments and which are symmetric under exchange of its n arguments and which satisfy

φ_{1}(1) = 1

and

φ_{n}(1, a_{2}, …, a_{n}) = 0

for all n ≥ 2 and all a_{2}, …, a_{n} ∈ A.

Of course, we can include the usual (first order) non-commutative probability space (A, φ_{1}) into this framework by putting all higher φ_{n} equal to zero. In the same way we recover a second order non-commutative probability space (A, φ_{1}, φ_{2}) by putting φ_{n} = 0 for all n ≥ 3.

Definition 7.2. 1) We denote by PS(A) the set of partitioned permutations decorated with elements from A, i.e.,

PS = ⋃_{n∈ℕ}(PS(n) × A^{n}).

2) For a function

f : PS(A) → ℂ
(V, π) × (a_{1}, …, a_{n}) ↦ f(V, π)[a_{1}, …, a_{n}]

and a function

g : PS → ℂ

we define their convolution

f ∗ g : PS(A) → ℂ

by

(f ∗ g)(U, γ)[a_{1}, …, a_{n}] := ∑_{{(V,π),(W,σ)∈PS(n) \atop (V,π)·(W,σ)=(U,γ)}} f(V, π)[a_{1}, …, a_{n}] · g(W, σ)

for all (U, γ) ∈ PS(n) and all a_{1}, …, a_{n} ∈ A.

Definition 7.3. A function f : PS(A) → ℂ is called multiplicative if we have

f(V, π)[a_{1}, …, a_{n}] = ∏_{B∈V} f(1_{B}, π|_{B})[(a_{1}, …, a_{n})_{B}]

and

f(1_{n}, σ^{−1}πσ)[a_{σ(1)}, …, a_{σ(n)}] = f(1_{n}, π)[a_{1}, …, a_{n}]

for all a_{1}, …, a_{n} ∈ A and all π, σ ∈ S(n).

Note that this extension of our formalism on multiplicative functions on PS and their convolution from the last section is not changing the results from the last section. The structure of all formulas remains the same; one just has to insert the a_{1}, …, a_{n} as dummy variables at the right positions. Thus, in particular, δ is still the unit for this extended convolution and f = g ∗ ζ is equivalent to g = f ∗ μ for multiplicative f, g on PS(A). And again, the convolution of a multiplicative function on PS(A) with a multiplicative function on PS gives a multiplicative function on PS(A). It is clear that a multiplicative function f on PS(A) is uniquely determined by the values of f(1_{n}, γ_{n(1),...,n(r)})[a_{1}, …, a_{n}] (where we put n := n(1)+⋯+n(r)) for all r ∈ ℕ, all n(1), …, n(r) ∈ ℕ and all a_{1}, …, a_{n} ∈ A.

7.2. Moment and cumulant functions. Let us now apply this formalism to get moment and cumulant functions for higher order probability spaces. So let a HOPS (A, φ) be given. We will use the φ_{n} to produce a multiplicative “moment” function on PS(A), which we will also denote by φ. Namely, we put

φ(1_{n}, γ_{n(1),...,n(r)})[a_{1}, …, a_{n}]

:= φ_{r}(a_{1} ⋯ a_{n(1)}; …; a_{n(1)+···n(r−1)+1} ⋯ a_{n})

and extend this by multiplicativity. (Note that we need the φ_{n} to be tracial in their arguments for this extension.) Here is an example for our function φ.

φ({1, 3, 4}{2}, (1, 3)(2)(4))[a_{1}, a_{2}, a_{3}, a_{4}] = φ_{2}(a_{1}a_{3}, a_{4}) · φ_{1}(a_{2})

Definition 7.4. For a given HOPS (A, φ) we define the corresponding (higher order) free cumulants as a function on PS(A) by

κ = φ ∗ μ,

or more explicitly

κ(U, γ)[a_{1}, …, a_{n}] := ∑_{{(V,π),(W,σ)∈PS(n) \atop (V,π)·(W,σ)=(U,γ)}} φ(V, π)[a_{1}, …, a_{n}] · μ(W, σ),

for all n ∈ ℕ, (U, γ) ∈ PS(n), a_{1}, …, a_{n} ∈ A.

As we noted before the definition above is equivalent to the statement φ = κ∗ζ, i.e.,

φ(U, γ)[a_{1}, …, a_{n}] = ∑_{(V,π)∈PS_{NC}(U,γ)} κ(V, π)[a_{1}, …, a_{n}]

for all (U, γ)[a_{1}, …, a_{n}] ∈ PS(A). Furthermore, as with φ, κ is also a multiplicative function on PS(A). Thus in the same way as all φ(U, γ) are determined by the knowledge of all

φ(1_{n}, γ_{n(1),...,n(r)})[a_{1}, …, a_{n}]

= φ_{r}(a_{1} ⋯ a_{n(1)}; …; a_{n(1)+···+n(r−1)+1} ⋯ a_{n(1)+···+n(r)})

the free cumulants κ(U, γ) are determined by the values of

κ(1_{n}, γ_{n(1),...,n(r)})[a_{1}, …, a_{n}]

=: κ_{n(1),...,n(r)}(a_{1}, …, a_{n(1)}; …; a_{n(1)+···+n(r−1)+1}, …, a_{n(1)+···+n(r)}).

Remark 7.5. Note that whereas on the level of φ we also know (by definition) that we can multiply elements along the cycles of π (and thus we do not need a comma as separator for those elements along a cycle), this is not true for κ. Thus we have, e.g.,

φ(1_{3}, (1, 2)(3))[a_{1}, a_{2}, a_{3}] = φ_{2}(a_{1}a_{2}; a_{3}) = φ(1_{2}, (1), (2))[a_{1}a_{2}; a_{3}],

but no clear relation exists among

κ(1_{3}, (1, 2)(3))[a_{1}, a_{2}, a_{3}] = κ_{2,1}(a_{1}, a_{2}; a_{3})

and

κ(1_{2}, (1), (2))[a_{1}a_{2}; a_{3}] = κ_{1,1}[a_{1}a_{2}; a_{3}].

Note also that since our convolution on PS coincides on the first level with the usual convolution of multiplicative functions on non-crossing partitions, the above definition of cumulants reduces on the first level to the usual free cumulants.

7.3. Higher order freeness. Equipped with the notion of cumulants we can now define “freeness” by the requirement of vanishing of mixed cumulants.

Definition 7.6. We say that a family (X_{i})_{i∈I} of subsets of A is free (of all orders) if we have the following vanishing of mixed cumulants: For all n ≥ 2 and all a_{k} ∈ X_{i(k)} (1 ≤ k ≤ n) such that i(p) ≠ i(q) for some 1 ≤ p, q ≤ n we have

κ(1_{n}, π)[a_{1}, …, a_{n}] = 0

for all π ∈ S(n).

Example 7.7. Let us see that this definition includes the definition of Voiculescu [VDN92] for (first order) freeness and the definition of Mingo and Speicher [MS06] for second order freeness.

1) On the first level this follows from the fact that our cumulants reduce then to the usual free cumulants and it is well-known that freeness is equivalent to the vanishing of mixed cumulants. One can see it directly as follows: Let us consider a_{k} ∈ X_{i(k)} with i(k) ≠ i(k + 1) and φ_{1}(a_{k}) = 0 for all k = 1, …, n. Then we have

φ_{1}(a_{1} ⋯ a_{n}) = φ(1_{n}, γ_{n})[a_{1}, …, a_{n}] = ∑_{π∈NC(n)} κ(0_{π}, π)[a_{1}, …, a_{n}].

However the vanishing of mixed moments means now that the only π which contribute are those which do not connect elements from different sets. Furthermore, the fact that all our variables are centered excludes singletons. But then it is easy to see that there are no such π at all, so the sum is zero.

2) Now we have to consider two cyclically alternating and centered tuples a_{1}, …, a_{m} and b_{1}, …, b_{n}. Then we have

φ_{2}(a_{1} ⋯ a_{m}; b_{1} ⋯ b_{n}) = φ(1_{m+n}, γ_{m,n})[a_{1}, …, a_{m}, b_{1}, …, b_{n}]

= ∑_{(V,π)∈PS_{NC}(m,n)} κ(V, π)[a_{1}, …, a_{m}, b_{1}, …, b_{n}].

Again, the vanishing of mixed moments requires that (V, π) connects only elements from the same set and the centeredness of the elements excludes singletons. It is then easy to see that, for n ≥ 2, the only possibilities for such (V, π) arise for m = n and they have to be disc permutations (0_{π}, π) which are pairings (a_{1}, b_{1+s})(a_{2}, b_{2+s}) ⋯ (a_{n}, b_{n+s}) for some s. The factors k(1_{2}, (...))[a_{k}, b_{k+s}] are just φ_{1}(a_{2}b_{2+s}), so that one finally gets, for n ≥ 2, the formula

φ_{2}(a_{1} ⋯ a_{m}; b_{1} ⋯ b_{n}) = δ_{mn} ∑_{k=1}^{n} φ_{1}(a_{1}b_{1+s}) ⋯ φ_{1}(a_{n}b_{n+s}).

For n = m = 1 one gets with

φ_{2}(a_{1}; b_{1}) = k_{2}(a_{1}, a_{2}) + k_{1,1}(a_{1}; b_{1})

the conclusion that φ_{2}(a_{1}; b_{1}) has to vanish if a_{1} and b_{1} are from different sets. Nothing is required if both are from the same set. We see that we get exactly the defining properties for second order freeness from [MS06].

3) It would be nice to be able to reformulate in a similar way the definition of higher order freeness in terms of the φ instead of the cumulants. However, the situation with more than two circles is getting much more involved and we are not aware of such a reformulation for third and higher order freeness.

As in the case of the first order freeness, one sees immediately that constants are free from everything.

Proposition 7.8. Let (A, φ) be a HOPS. Then {1} is free of all orders from every subset X ⊂ A.

Proof. We have to prove that

κ(1_{n}, γ_{n(1),...,n(r)})[1, a_{2}, …, a_{n}] = 0, unless n = 1. We will do this by induction on n. The case n = 2 is clear because

κ(1_{2}, (12))[1, a_{2}] = φ_{1}(1 · a_{2}) − φ_{1}(1) · φ_{1}(a_{2}) = 0

and

κ(1_{2}, (1)(2))[1, a_{2}] = φ_{2}(1; a_{2}) = 0.

In general, one has

φ(1_{n}, γ_{n(1),...,n(r)})[1, a_{2}, …, a_{n}]

= ∑_{(V,π)∈PS_{NC}(n(1),...,n(r))} κ(V, π)[1, a_{2}, …, a_{n}]

= κ(1_{n}, γ_{n(1),...,n(r)})[1, a_{2}, …, a_{n}]

+ ∑_{{(V,π)∈PS_{NC} (n(1),...,n(r)) \atop |(V,π)|<|(1n,γ_{n(1),...,n(r)})|}} κ(V, π)[1, a_{2}, …, a_{n}]

By induction hypothesis, in the later sum exactly terms of the form ({1} ∪ Ṽ, (1) ∪ π̃) with

(Ṽ, π̃) ∈ PS_{NC}(n(1) − 1, n(2), …, n(r))

contribute. In the case n(1) > 1 the sum over those yields

φ(1_{n−1}, γ_{n(1)−1,n(2),...,n(r)}[a_{2}, …, a_{n}].

In this case, also

φ(1_{n}, γ_{n(1),...,n(r)})[1, a_{2}, …, a_{n}] = φ(1_{n−1}, γ_{n(1)−1,n(2),...,n(r)}[a_{2}, …, a_{n}],

and thus κ(1_{n}, γ_{n(1),...,n(r)})[1, a_{2}, …, a_{n}] = 0. If, on the other side, n(1) = 1 (i.e., 1 is the only element on its circle), then we have to set

PS_{NC}(0, n(2), …, n(r)) = ∅,

because then the first circle cannot be connected to the others if we ask 1 to be a cycle of its own. But this means that in this case

κ(1_{n}, γ_{n(1),...,n(r)})[1, a_{2}, …, a_{n}] = φ(1_{n}, γ_{n(1),...,n(r)})[1, a_{2}, …, a_{n}]

However, for n(1) = 1 and n > 1 we have

φ(1_{n}, γ_{1,...,n(r)})[1, a_{2}, …, a_{n}] = 0.
□

Note that our definition of freeness behaves clearly very nicely with respect to decompositions of our sets. For example, we have that X_{1}, X_{2}, X_{3} are free if and only if X_{1} and X_{2} ∪X_{3} are free and X_{2} and X_{3} are free. Thus we can reduce the investigation of freeness to the understanding of freeness for the case of two sets. A characterization for this is given in the next theorem.

Theorem 7.9. Let (A, φ) be a higher order probability space and consider two subsets of X_{1}, X_{2} ⊂ A. Then the following are equivalent.

(1) The sets X_{1}, X_{2} are free of all orders.

(2) The sets X_{1} ∪ {1}, X_{2} ∪ {1} are free of all orders.

(3) We have

φ(U, γ)[a_{1}b_{1}, …, a_{n}b_{n}]

= ∑_{(V,π)·(W,σ)=(U,γ)} κ(V, π)[a_{1}, …, a_{n}] · φ(W, σ)[b_{1}, …, b_{n}]

for all n ∈ ℕ, all (U, γ) ∈ PS(n) and all a_{1}, …, a_{n} ∈ X_{1} ∪ {1}, b_{1}, …, b_{n} ∈ X_{2} ∪ {1}.

(4) We have

φ(U, γ)[a_{1}b_{1}, …, a_{n}b_{n}]

= ∑_{(V,π)·(W,σ)=(U,γ)} φ(V, π)[a_{1}, …, a_{n}] · κ(W, σ)[b_{1}, …, b_{n}]

for all n ∈ ℕ, all (U, γ) ∈ PS(n) and all a_{1}, …, a_{n} ∈ X_{1} ∪ {1}, b_{1}, …, b_{n} ∈ X_{2} ∪ {1}.

(5) We have

κ(U, γ)[a_{1}b_{1}, …, a_{n}b_{n}]

= ∑_{(V,π)·(W,σ)=(U,γ)} κ(V, π)[a_{1}, …, a_{n}] · κ(W, σ)[b_{1}, …, b_{n}]

for all n ∈ ℕ, all (U, γ) ∈ PS(n) and all a_{1}, …, a_{n} ∈ X_{1} ∪ {1},

b_{1}, …, b_{n} ∈ X_{2} ∪ {1}.

In order to prove this we would like to write φ(U, γ)[a_{1}b_{1}, …, a_{n}b_{n}] in the form φ(Û, γ̂)[a_{1}, b_{1}, …, a_{n}, b_{n}]. Let us introduce the following formalism for this. Let (U, γ) ∈ PS(n) be a partitioned permutation of the numbers 1, 2, 3, …, n. Double now this set of numbers by introducing a copy ¯1, ¯2, ¯3, …, n̄ and interleave the new and old numbers as follows:

1, ¯1, 2, ¯2, 3, ¯3, …, n, n̄.

If we induce now (U, γ) on 1, 2, …, n to (Û, γ̂) on 1, ¯1, …, n, n̄ by putting

γ̂(k) = k̄  and  γ̂(k̄) = γ(k),

then this has exactly the desired property. The vanishing of mixed cumulants means that in the factorizations of (Û, γ̂) in (V, π) times a disc permutation we are only interested in (V, π) which have the property that each block of V contains either only unbarred numbers or only barred numbers, i.e., (V, π) must be of the form (V_{a} ∪ V_{b}, π_{a} ∪ π_{b}) with

(V_{a}, π_{a}) ∈ PS(1, …, n)  and  (V_{b}, π_{b}) ∈ PS(¯1, …, n̄).

Let us first observe some simple relations between the quantities on 1, …, n and their relatives on 1, ¯1, …, n, n̄.

Lemma 7.10. 1) We have

|γ̂| = n + |γ|, |Û| = n + |U|,

and thus

|(Û, γ̂)| = n + |(U, γ)|.

2) We have

|π_{a} ∪ π_{b}| = |π_{a}| + |π_{b}|, |V_{a} ∪ V_{b}| = |V_{a}| + |V_{b}|,

and thus

|(V_{a} ∪ V_{b}, π_{a} ∪ π_{b})| = |(V_{a}, π_{a})| + |(V_{b}, π_{b})|.

3) We have that (π_{a} ∪ π_{b})γ̂ maps unbarred to barred and barred to unbarred elements and, for all k = 1, …, n,

[(π_{a} ∪ π_{b})γ̂]^{2}(k̄) = π_{b}π_{a}γ(k),

thus

|(π_{a} ∪ π_{b})γ̂| = n + |π_{b}π_{a}γ|

Proof. Only the third part is non-trivial. To see this observe

(π_{a} ∪ π_{b})γ̂(k̄) = π_{a}(γ(k))

and thus

[(π_{a} ∪ π_{b})γ̂]^{2}(k̄) = π_{b}\overline{π_{a}(γ(k))},

which is our first equation, with the identification of π_{b} ∈ S(¯1, …, ¯1) with the corresponding permutation in S(1, …, n). Since the mapping between barred and unbarred elements is clear, this yields that (π_{a} ∪ π_{b})γ̂ and π_{b}π_{a}γ have the same number of orbits which gives the last equation. □

This lemma allows us to characterize the contributing factorizations in (Û, γ̂) in terms of special factorizations of (U, γ).

Proposition 7.11. The statement

(V_{a} ∪ V_{b}, π_{a} ∪ π_{b}) ∈ PS_{NC}(Û, γ̂)

is equivalent to the statement

(V_{a}, π_{a}) · (V_{b}, π_{b}) ∈ PS_{NC}(U, γ),

where in the last product we identify (V_{b}, π) ∈ PS(¯1, …, n̄) with the corresponding element in PS(1, …, n).

Proof. Note that (V_{a} ∪ V_{b}, π_{a} ∪ π_{b}) ∈ PS_{NC}(Û, γ̂) is equivalent to

(54)  |(V_{a} ∪ V_{b}, π_{a} ∪ π_{b})| + |(π_{a} ∪ π_{b})^{−1}γ̂| = |(Û, γ̂)|

and

(55)  Û = (V_{a} ∪ V_{b}) ∨ γ̂.

On the other hand, (V_{a}, π_{a}) · (V_{b}, π_{b}) ∈ PS_{NC}(U, γ), means

(V_{a}, π_{a}) · (V_{b}, π_{b}) · (0_{π_{b}^{−1}π_{a}^{−1}γ}, π_{b}^{−1}π_{a}^{−1}γ) = (U, γ),

which is equivalent to

(56)  |(V_{a}, π_{a})| + |(V_{b}, π_{b})| + |π_{b}^{−1}π_{a}^{−1}γ| = |(U, γ)|

and

(57)  U = V_{a} ∨ V_{b} ∨ γ.

Equations (54) and (56) are, by Lemma 7.10, equivalent. The equivalence between (55) and (57) is also easily checked. □

Equipped with these tools we can now prove our main Theorem 7.9.

Proof. The equivalences between (3), (4), and (5) follow by convolving with the ζ or the μ function. That (2) is actually the same as (1) follows from Prop. 7.8.

(1) ⟹ (3): We have

φ(U, γ)[a_{1}b_{1}, …, a_{n}b_{n}] = φ(Û, γ̂)[a_{1}, b_{1}, …, a_{n}, b_{n}]

= ∑_{(V,π)·(W,σ)=(Û,γ̂)} κ(V, π)[a_{1}, b_{1}, …, a_{n}, b_{n}] · ζ(W, σ)

= ∑_{(V,π)∈PS_{NC}(Û,γ̂)} κ(V, π)[a_{1}, b_{1}, …, a_{n}, b_{n}]

By our assumption on the vanishing of mixed cumulants, only (V, π) of the form (V_{1} ∪ V_{2}, π_{a} ∪ π_{b}) with

(V_{a}, π_{a}) ∈ PS(1, …, n)  and  (V_{b}, π_{b}) ∈ PS(¯1, …, n̄)

contribute and, by the above Proposition 7.11,

(V_{a} ∪ V_{b}, π_{a} ∪ π_{b}) ∈ PS_{NC}(Û, γ̂)

is equivalent to

(V_{a}, π_{a}) · (V_{b}, π_{b}) ∈ PS_{NC}(U, γ).

Thus we can continue with

φ(U, γ)[a_{1}b_{1}, …, a_{n}b_{n}]

= ∑_{(V_{a}∪V_{b},π_{a}∪π_{b})∈PS_{NC}(Û,γ̂)} κ(V_{a}, π_{a})[a_{1}, a_{2}, …, a_{n}] · κ(V_{b}, π_{b})[b_{1}, b_{2}, …, b_{n}]

= ∑_{(V_{a},π_{a})·(V_{b},π_{b})∈PS_{NC}(U,γ)} κ(V_{a}, π_{a})[a_{1}, a_{2}, …, a_{n}] · κ(V_{b}, π_{b})[b_{1}, b_{2}, …, b_{n}]

= ∑_{(V_{a},π_{a})·(V_{b},π_{b})·(W,σ)=(U,γ)} κ(V_{a}, π_{a})[a_{1}, a_{2}, …, a_{n}]·

· κ(V_{b}, π_{b})[b_{1}, b_{2}, …, b_{n}] · ζ(W, σ)

= ∑_{(V_{a},π_{a})·(V,π)=(U,γ)} κ(V_{a}, π_{a})[a_{1}, …, a_{n}] · φ(V, π)[b_{1}, …, b_{n}].

(3) ⟹ (1): Note that (3) allows us to calculate all moments of elements from X_{1} ∪ X_{2} out of the moments of elements from X_{1} and the moments of elements from X_{2}. (In order to do so, we also have to allow some of the a’s or b’s to be equal to the unit 1.) Since this calculation rule is the same as for free sets, this shows that the sets X_{1} and X_{2} must be free. □

This theorem is now the key ingredient to transfer freeness from sets to their generated algebras.

Theorem 7.12. Let (A, φ) be a HOPS and consider subsets (X_{i})_{i∈I}. For each i ∈ I, let A_{i} be the unital algebra generated by elements from X_{i}. Then the following are equivalent.

(1) The subsets (X_{i})_{i∈I} are free of all orders.

(2) The subalgebras (A_{i})_{i∈I} are free of all orders.

Proof. Since the cumulant κ(V, π)[a_{1}, …, a_{n}] is a multi-linear functional in the n variables a_{1}, …, a_{n}, it is clear that taking sums of elements within the sets X_{i} preserves freeness. What we have to see is that also taking products preserves freeness. Since we can iterate our arguments, it suffices to see the following: if X_{1} and X_{2} are free, then also X_{1} ∪{a_{0}a_{1} | a_{0}, a_{1} ∈ X_{1}} and X_{2} are free. Adding one product after the other to X_{1} and by Theorem 7.9 it is enough to show that

φ(U, γ)[a_{0}a_{1}b_{1}, a_{2}b_{2} …, a_{n}b_{n}]

= ∑_{(V,π)·(W,σ)=(U,γ)} φ(V, π)[a_{0}a_{1}, a_{2} …, a_{n}] · κ(W, σ)[b_{1}, …, b_{n}]

for all n ∈ ℕ, all (U, γ) ∈ PS(n) and all a_{0}, a_{1}, …, a_{n} ∈ X_{1} ∪ {1}, b_{1}, …, b_{n} ∈ X_{2} ∪ {1}. Let us induce (U, π) ∈ PS(1, …, n) to (Û, π̂) ∈ PS(0, 1, …, n) by requiring that Ŵ and π̂ restricted to 1, …, n agree with W and π, respectively, and that 0 and 1 are in the same block of Ŵ and π̂(0) = 1. Then we can calculate

φ(U, γ)[a_{0}a_{1}b_{1}, a_{2}b_{2} …, a_{n}b_{n}] = φ(Û, π̂)[a_{0}1, a_{1}b_{1}, a_{2}b_{2}, …, a_{n}b_{n}]

= ∑_{(V,π)·(W,σ)=(Û,γ̂)} φ(V, π)[a_{0}, a_{1}, a_{2} …, a_{n}] · κ(W, σ)[1, b_{1}, …, b_{n}].

By Proposition 7.8 we know that κ(W, σ)[1, b_{1}, …, b_{n}] is only different from zero if W has 0 as a singleton, i.e., (W, σ) has to be of the form

W = {0} ∪ W̃, σ = (0)σ̃,

with

(W̃, σ̃) ∈ PS(1, …, n).

But then we must have that π(0) = 1 and 0 and 1 must be in the same block of V. Thus there is a unique (V′, π′) so that (V, π) = (V̂′, π̂′) and

(V, π) · (W, σ) = (Û, γ̂)

is equivalent to

(V′, π′) · (W̃, σ̃) = (U, γ).

Note also that in this situation

κ(W, σ)[a_{0}, a_{1}, , …, a_{n}] = κ(W̃, σ̃)[b_{1}, b_{2}, …, b_{n}].

and

φ(V̂′, π̂′)[a_{0}, a_{1}, , …, a_{n}] = φ(V′, π′)[a_{0}a_{1}, a_{2}, …, a_{n}].

So we can continue the above calculation as follows

φ(U, γ)[a_{0}a_{1}b_{1}, a_{2}b_{2} …, a_{n}b_{n}]

= ∑_{(V′,π′)·(W̃,σ̃)=(U,γ)} φ(V′, π′)[a_{0}a_{1}, a_{2} …, a_{n}] · κ(W̃, σ̃)[b_{1}, …, b_{n}],

which is exactly what we had to show. □

7.4. Distribution of one random variable. For the case where we restrict our attention to just one random variable a ∈ A we introduce the following notation.

Notation 7.13. Let (A, φ) be a HOPS and let a ∈ A.

1) For, (V, π) ∈ PS(n), we will write

φ^{a}(V, π) := φ(V, π) \underbrace{[a, …, a]}_{n-times}

and

κ^{a}(V, π) := κ(V, π) \underbrace{[a, …, a]}_{n-times} .

2) A Young diagram is a λ = (λ_{1}, …, λ_{l}) for some l ∈ ℕ and λ_{1}, …, λ_{l} ∈ ℕ with λ_{1} ≥ λ_{2} ≥ ⋯ ≥ λ_{l}. We put |λ| := λ_{1} + ⋯ + λ_{l} (the total number of boxes of the Young diagram λ). The set of all Young diagrams will be denoted by Y.

3) The information about the higher order moments of a can also be parameterized by Young diagrams as follows: for λ = (λ_{1}, …, λ_{l}) we put

φ^{a}(λ) := φ(1_{|λ|}, π) \underbrace{[a, …, a]}_{n-times} = φ_{l}(a^{λ_{1}}, …, a^{λ_{l}})

where π is any permutation whose conjugacy class corresponds to λ (i.e., π ∈ S_{|λ|} has cycles of length λ_{1}, …, λ_{l}. The collection of all higher order moments (φ^{a}(λ))_{λ∈Y} is called the (higher order) distribution of a.

4) Similarly as for moments, we put

κ^{a}(λ) := κ(1_{|λ|}, π) \underbrace{[a, …, a]}_{n-times},

where π is any permutation whose conjugacy class corresponds to λ.

Remark 7.14. For first and second order moments and cumulants, we used in Section 2 also the following notations:

α_{n} := φ^{a}(1_{n}, γ_{n}) α_{m,n}^{a} := φ^{a}(1_{m+n}, γ_{m,n}), and

κ_{n}^{a} := κ^{a}(1_{n}, γ_{n}) κ_{m,n} := κ^{a}(1_{m+n}, γ_{m,n}),

where γ_{n} and γ_{m,n} are permutations with one cycle and two cycles, respectively.

The vanishing of mixed cumulants translates in this framework into the additivity of the cumulants for sums of free variables.

Theorem 7.15. Let (A, φ) be a HOPS and a, b ∈ A free of all orders. Then we have

κ^{a+b}(λ) = κ^{a}(λ) + κ^{b}(λ)

for all λ ∈ Y.

Proof. By the multilinearity of the cumulants and the vanishing of mixed cumulants for free variable, we have for any n ∈ ℕ and π ∈ S_{n}:

κ^{a+b}(1_{n}, π) = κ(1_{n}, π)[a + b, …, a + b]
= κ(1_{n}, π)[a, …, a] + κ(1_{n}, π)[b, …, b]
= κ^{a}(1_{n}, π) + κ^{b}(1_{n}, π).
□

8. Random matrices, Itzykson-Zuber integrals and higher order freeness

8.1. Asymptotic higher order freeness of random matrices. Let us now come back to our original motivation for our theory – the asymptotic behavior of random matrices. In order to reformulate our calculations from Section 4 in our language of higher order freeness we still need to define the notion of “asymptotic freeness”.

Definition 8.1. 1) Let (A, φ) and, for each N ∈ ℕ, (A_{N}, φ^{(N)}) be HOPSs. Let I be an index set and for each i ∈ I, a_{i} ∈ A and a_{i}^{(N)} ∈ A_{N} (N ∈ ℕ). We say that the family (a_{i}^{(N)} | i ∈ I) converges, for N → ∞, to (a_{i} | i ∈ I), denoted by

(a_{i}^{(N)})_{i∈I} → (a_{i})_{i∈I},

if we have for all n ∈ ℕ and all polynomials p_{1}, …, p_{n} in |I|-many noncommuting indeterminates that

(58) lim_{N→∞} φ_{n}^{(N)} (p_{1}((a_{i}^{(N)})_{i∈I}), …, p_{n}((a_{i}^{(N)})_{i∈I}))

= φ_{n} (p_{1}((a_{i})_{i∈I}), …, p_{n}((a_{i})_{i∈I})) .

2) Let, for each N ∈ ℕ, (A_{N}, φ^{(N)}) be HOPSs. Let I be an index set and, for each i ∈ I and N ∈ ℕ, a_{i}^{(N)} ∈ A_{N}. We say that the sequence of families (a_{i}^{(N)})_{i∈I} has a limit distribution of all orders if there exists a HOPS (A, φ) such that

(a_{i}^{(N)})_{i∈I} → (a_{i})_{i∈I},

for some a_{i} ∈ A (i ∈ I)

3) Let, for each N ∈ ℕ, (A_{N}, φ^{(N)}) be HOPSs. Let I be an index set and, for each i ∈ I and N ∈ ℕ, a_{i}^{(N)} ∈ A_{N}. Let I = I_{1} ∪⋯∪I_{k} be a decomposition of I into k disjoint subsets. We say that the sets {a_{i}^{(N)} | i ∈ I_{1}}, …, {a_{i}^{(N)} | i ∈ I_{k}} are asymptotically free of all orders if there exists a HOPS (A, φ) such that

(a_{i}^{(N)})_{i∈I} → (a_{i})_{i∈I},

for some a_{i} ∈ A (i ∈ I) and such that the sets {a_{i} | i ∈ I_{1}}, …, {a_{i} | i ∈ I_{k}} are free of all orders in (A, φ).

With this notation and by invoking Theorem 7.9 we can reformulate our main result on random matrices, Theorem 4.4, in the following form.

Theorem 8.2. Let M_{N} := M_{N} ⊗ L^{∞−}(Ω) be an ensemble of N × N-random matrices. Define rescaled correlation functions φ̃^{(N)} = (φ̃_{n}^{(N)})_{n∈ℕ} on M_{N} by (n ∈ ℕ, D_{1}, …, D_{n} ∈ M_{N})

(59)  φ̃_{n}^{(N)}(D_{1}, …, D_{n}) := k_{n}(Tr(D_{1}), …, Tr(D_{n})) · N^{2−n}.

Assume that we have, for each N ∈ ℕ, subalgebras A_{N}, B_{N} ∈ M_{N} such that (1) A_{N} is a unitarily invariant ensemble,

(2) A_{N} and B_{N} are independent.

Let (A_{i}^{(N)})_{i∈I} be a family of elements in (A_{N}, φ̃^{(N)}) which has a higher order limit distribution and let (B_{j}^{(N)})_{j∈J} (N ∈ ℕ) be a family of elements in (B_{N}, φ̃^{(N)}) which has a higher order limit distribution. Then the families {A_{i}^{(N)} | i ∈ I} and {B_{j}^{(N)} | j ∈ J} are asymptotically free of all orders.

8.2. Itzykson-Zuber integrals.

Definition 8.3. For N × N matrices A_{N}, B_{N} their Itzykson-Zuber integral is defined as the following function in z ∈ ℂ:

IZ(z, A_{N}, B_{N}) := N^{−2} log E(e^{zNTr(A_{N} UB_{N} U^{∗})}),

where U denotes a Haar unitary N × N-random matrix.

Consider now a sequence of such matrices A_{N} and B_{N}. Note that A_{N} and B_{N} are non-random, thus all distributions of order higher than 1 vanish identically. If we assume that A_{N} and B_{N} have a first order (eigenvalue) limit distribution for N → ∞, then it is known (see [Col03]) that each Taylor coefficient about zero of z → IZ(z, A_{N}, B_{N}) admits a limit as N → ∞. Note that the effect of the Haar unitary random matrix in the above Itzykson-Zuber integral was to make A_{N} and UB_{N}U^{∗} asymptotically free of all orders. We show now that this kind of result extends also to the case of random matrices A_{N} and B_{N}, and that our theory allows to identify the limit of the Taylor coefficients very precisely.

Theorem 8.4. Let A = (A_{N})_{N∈ℕ} and B = (B_{N})_{N∈ℕ} be two ensembles of N × N-random matrices which are asymptotically free of all orders with respect to the rescaled correlation functions φ̃^{(N)}. Denote the corresponding limiting distribution of (A_{N})_{N∈ℕ} by φ^{a} and the corresponding limit distribution of (B_{N})_{N∈ℕ} by φ^{b}. Then, as formal power series in z, we have (60)

lim_{N→∞} N^{−2} log E[e^{zNTr(A_{N} B_{N})}] = ∑_{n=1}^{∞} \frac{z^{n}}{n!} ∑_{{(V,π),(W,σ)∈PS(n) \atop (V,π)·(W,σ)=(1n,e)}} κ^{a}(V, π) · φ^{b}(W, σ).

Proof. Recall that the logarithm of the exponential generating series of the moments of a random variable is the exponential generating series of the classical cumulants of that variable. Thus we have

N^{−2} · logE[e^{zNA_{N} B_{N}}]

= N^{−2} ∑_{n=1}^{∞} k_{n}(NTr(A_{N}B_{N}), …, NTr(A_{N}B_{N})) · \frac{z^{n}}{n!}

= ∑_{n=1}^{∞} N^{n−2} · φ^{(N)}(1_{n}, e)[A_{N}B_{N}, …, A_{N}B_{N}] · \frac{z^{n}}{n!} .

By our assumption that A_{N} and B_{N} are asymptotically free with respect to φ̃_{n}^{(N)} = N^{n−2}φ_{n}^{N}, this converges to

∑_{n=1}^{∞} φ(1_{n}, e)[ab, …, ab] · \frac{z^{n}}{n!} ,

where a and b are free of all orders with respect to φ. Theorem 7.9 yields then the assertion. □

In a forthcoming work we will investigate the relevance of higher order freeness for Itzykson-Zuber integrals more detailed, in particular, in comparison with and extension of results of Zinn-Justin [ZJ99], Collins [Col03], and Guionnet and Maida [GM05].

9. Appendix: Surfaced permutations

In this appendix we will present a more geometrical view on partitioned permutations. As we shall see in the following, partitioned permutations are just special cases of “surfaced permutations”; in particular the results of this article can be equivalently formulated in the language of surfaced permutations. On the other hand, for the purpose of this article we do not need anything more than just partitioned permutations and the Reader not interested in surfaced permutations may skip this Section without much harm.

9.1. Motivations. Our goal is to study factorizations of permutations, i.e. solutions (π_{1}, …, π_{k}) of the equation

γ = π_{1} ⋯ π_{k},

where γ ∈ S_{n} is some fixed permutation and π_{1}, …, π_{k} ∈ S_{n} are subject to some additional constraints, depending on a particular context. Typically, one Figure 1. Example of a surfaced permutation. Its support is equal to (1, 3)(2)(4) ∈ S_{4}. This surfaced permutation corresponds to a partitioned permutation ({1, 3, 4}{2}, (1, 3)(2)(4)) .

of these constrains concerns |π_{1}| + ⋯ + |π_{k}|, the other one concerns the orbits of the action of π_{1}, …, π_{k}. It would be very useful to equip permutations π_{1}, …, π_{k} with some additional structure in such a way that the product π̃_{1} ⋯ π̃_{k} of the resulting enriched permutations π̃_{1}, …, π̃_{k} would carry both the information about the product π_{1} ⋯ π_{k} of permutations and the information about |π_{1}| + ⋯ + |π_{k}|. As we shall see in the following, surfaced permutations provide an appropriate tool.

9.2. Definition. We say that σ = (S, j) is a surfaced permutation of some finite set A if S is a two–dimensional surface with a fixed orientation and with a boundary ∂S and if j : A → ∂S is a injection. We can think about the information carried by j as follows: some of the points on the boundary ∂S are distinguished and carry different labels from the set A. We also require that every connected component of ∂S carries at least one distinguished point. An example of a surfaced permutation is presented on Figure 1. We identify surfaced permutations (S_{1}, j_{1}), (S_{2}, j_{2}) of the same set A if there exists a orientation preserving homeomorphism f : S_{1} → S_{2} such that f ∘ j_{1} = j_{2}. The set of surfaced permutations of set {1, …, n} will be denoted by SS_{n}.

9.3. Surfaced permutations and the usual permutations. Let (S, j) ∈ SS_{n}; the boundary ∂S with the inherited orientation from S is just a collection of oriented circles with some distinguished points labeled 1, …, n marked on them. In this way we can define a permutation σ ∈ S_{n}, called the support of (S, j), the cycles of which correspond to connected components of ∂S, as it can

Figure 2. Convention for splitting labels.

be seen on Figure 1. It is therefore a good idea to think that a surfaced permutation is just a (usual) permutation σ ∈ S_{n} equipped with some additional information carried by the surface S. A surfaced permutation (S, j) ∈ SS_{n} can be uniquely specified (up to the equivalence relation) by its support σ ∈ S_{n} and by specifying the shape of the connected components of S. The latter information is given by an equivalence relation on cycles of σ (each class corresponds to a connected component of S) and furthermore for each class of this relation we should specify the genus of the corresponding connected component of S. Above it should be understood that the genus of a surface S with a boundary is by definition equal to the genus of a surface S′ without boundary obtained from S by gluing a disc to every connected component of ∂S; for example both a disc and the lateral surface of a cylinder have genus zero.

9.4. Surfaced permutations and partitioned permutations. Among surfaced permutations a special class will be very important for our purposes, namely surfaced permutations (S, j) such that each connected component of S has genus zero. It is easy to see that there is a bijection between such surfaced permutations (S, j) and partitioned permutations (V, σ) given as follows: σ is the support of (S, j) and V is the partition given by connected components of S.

9.5. Products of surfaced permutations. Let surfaced permutations (S_{1}, j_{1}), (S_{2}, j_{2}) ∈ SS_{n} be given. On the boundary of S_{2} there are marked points labeled by numbers 1, …, n; let us split every marked point k into a consecutive pair of points k and k′, as it is presented on the example from Figure 2. In the second step, for each k ∈ {1, …, n} we glue a small neighborhood of the vertex k ∈ ∂S_{1} to a small neighborhood of the vertex k′ ∈ ∂S_{2} in such a way that the orientations of S_{1} and S_{2} coincide. In this way we obtain a new surface S which has marked points on its boundary ∂S and these are exactly the vertices from ∂S_{2} labeled 1, …, n; we denote the resulting surfaced permutation by (S, j) and we call it a product (S_{1}, j_{1})(S_{2}, j_{2}) of the original surfaced permutations. This choice of gluing surfaces S_{1} and S_{2} implies that the support of (S_{1}, j_{1})(S_{2}, j_{2}) is equal to the product of the support of (S_{1}, j_{1}) and the support of (S_{2}, j_{2}). It is not difficult to explain now the definition of the product of partitioned permutations (Definition 4.9): we treat partitioned permutations as surfaced permutations and compute their product; if the genus of the resulting surface is zero we can identify it with another partitioned permutation, otherwise we set the product to be zero. It is not difficult to show that for surfaced permutations the product is associative and the associativity of the product of partitioned permutations is a simple corollary.

References

[AJM90] J. Ambjørn, J. Jurkiewicz, and Yu. M. Makeenko: Multiloop correlators for two-dimensional quantum gravity. Physics Letters B. 251: 517–524, 1990.

[ACKM93] J. Ambjørn, L. Chekhov, C. F. Kristjansen, and Yu. M. Makeenko: Matrix model calculations beyond the spherical limit. Nuclear Physics B 404: 127–172, 1993.

[AZ06] G. W. Anderson, O. Zeitouni: A CLT for a band matrix model. Probab. Theory Relat. Fields, 134: 283–338, 2006.

[BS04] Z. D. Bai and J. Silverstein: CLT for linear spectral statistics of large-dimensional sample covariance matrices. Ann. Prob., 32: 533– 605, 2004.

[Bia97] P. Biane: Some properties of crossings and partitions. Discrete Math., 175(1-3):41–53, 1997.

[BMS00] M. Bousquet-Mélou and G. Schaeffer: Enumeration of planar constellations. Adv. in Appl. Math., 24(4):337–368, 2000.

[BZ93] É. Brézin, A. Zee: Universality of the correlations between eigenvalues of large random matrices. Nuclear Phys. B 402 (1993), no. 3, 613–627.

[CC06] M. Capitaine and M. Casalis: Cumulants for random matrices as convolutions over the symmetric group. Probab. Theory Relat. Fields, 136 (2006), 19-36.

[Col03] B. Collins: Moments and cumulants of polynomial random variables on unitary groups, the Itzykson-Zuber integral, and free probability. Int. Math. Res. Not., (17):953–982, 2003.

[CŚ06] B. Collins and P. Śniady: Integration with respect to the Haar measure on unitary, orthogonal and symplectic groups. Comm. Math. Phy., 264, (2006), 773 - 795.

[Dia03] P. Diaconis: Patterns in Eigenvalues: The 70th Josiah Willard Gibbs Lecture. Bulletin of the AMS, 40: 155-178, 2003.

[FMP78] J. B. French, P. A. Mello, A. Pandey: Statistical properties of manyparticle spectra. II. Two-point correlations and fluctuations. Ann. of Physics, 113 (1978), no. 2, 277–293.

[GM05] A. Guionnet and M. Maïda: A Fourier view on the R-transform and related asymptotics of spherical integrals. J. Funct. Anal., 222(2):435– 490, 2005.

[Joh98] K. Johansson: On fluctuations of eigenvalues of random Hermitian matrices. Duke Math. J., 91(1):151–204, 1998.

[Jon99] V. F. R. Jones: Planar algebras. I. math.QA/9909027, 1999, 122 pp.

[KKP95] A. Khorunzhy, B. Khoruzhenko, L. Pastur: On the 1/N corrections to the Green functions of random matrices with independent entries. J. Phys. A 28 (1995), L31–L35.

[Kre72] G. Kreweras: Sur les partitions non croisées d’un cycle. Discrete Math., 1(4):333–350, 1972.

[LS59] V. P. Leonov and A. N. Shiryaev: On a method of semi-invariants. Theory of Probability and its Applications, 4, 319–329, 1959.

[MN04] J. Mingo and A. Nica: Annular noncrossing permutations and partitions, and second-order asymptotics for random matrices. Int. Math. Res. Not., (28):1413–1460, 2004.

[MŚS07] J. Mingo, P. Śniady, and R. Speicher. Second order freeness and fluctuations of random matrices: II. Unitary random matrices. Adv. in Math. 209: 212 – 240, (2007).

[MS06] J. Mingo and R. Speicher: Second Order Freeness and Fluctuations of Random Matrices: I. Gaussian and Wishart matrices and Cyclic Fock spaces. J. Funct. Anal., 235, 2006, pp. 226-270.

[NSp97] A. Nica and R. Speicher: A “Fourier transform” for multiplicative functions on non-crossing partitions. J. Algebraic Combin., 6(2):141– 160, 1997.

[NSp06] A. Nica and R. Speicher: Lectures on the Combinatorics of Free Probability, London Mathematical Society Lecture Note Series, New York: Cambridge University Press, 2006.

[OZ84] K. H. O’Brien and J.-B. Zuber: A note on U(N) integrals in the large N limit. Phys. Lett. B, 144(5-6):407–408, 1984.

[Oko00] A. Okounkov: Random matrices and random permutations. Int. Math. Res. Not., 2000, no. 20: 1043–1095, 2000.

[Rad06] F. Radulescu: Combinatorial aspects of Connes’s embedding conjecture and asymptotic distribution of traces of products of unitaries, Operator theory 20, 197–205, Theta Ser. Adv. Math., 6, Theta, Bucharest, 2006

[Rot64] G.-C. Rota: On the foundations of combinatorial theory. I. Theory of Möbius functions. Z. Wahrscheinlichkeitstheorie und Verw. Gebiete, 2: 340–368, 1964.

[Śni06] P. Śniady: Gaussian fluctuations of characters of symmetric groups and of Young diagrams. Probab. Theory Related Fields 136: 263–297, 2006.

[Spe94] R. Speicher: Multiplicative functions on the lattice of noncrossing partitions and free convolution. Math. Ann., 298(4):611–628, 1994.

[VDN92] D. V. Voiculescu, K. J. Dykema, and A. Nica: Free random variables. American Mathematical Society, Providence, RI, 1992.

[Voi85] D. Voiculescu: Symmetries of some reduced free product C^{∗}-algebras. In Operator Algebras and their Connections with Topology and Ergodic Theory (Lecture Notes in Mathematics, vol. 1132, Springer-Verlag): 556-588, 1985.

[Voi86] D. Voiculescu: Addition of certain non-commuting random variables. J. Funct. Anal., 66: 323–346, 1986.

[Voi91] D. Voiculescu: Limit laws for random matrices and free products. Invent. Math., 104(1):201–220, 1991.

[Wei78] D. Weingarten: Asymptotic behavior of group integrals in the limit of infinite rank. J. Mathematical Phys., 19(5):999–1001, 1978.

[ZJ99] P. Zinn-Justin. Adding and multiplying random matrices: a generalization of Voiculescu’s formulas. Phys. Rev. E (3), 59(5, part A):4884– 4888, 1999.

Benoît Collins University of Ottawa 585 King Edward Ave. Ottawa, ON, K1N 6N5, Canada and CNRS, Institut Camille Jordan Université Claude Bernard Lyon 1 43 boulevard du 11 novembre 1918 69622 Villeurbanne Cedex, France bcollins@uottawa.ca James A. Mingo Queen’s University, Department of Mathematics

and Statistics Jeffery Hall, Kingston, ON K7L 3N6, Canada mingo@mast.queensu.ca

Piotr Śniady Instytut Matematyczny Uniwersytet Wroclawski pl Grunwaldzki 2/4 50-384 Wroclaw Poland Piotr.Sniady@math.uni.wroc.pl Roland Speicher Queen’s University, Department of Mathematics

and Statistics Jeffery Hall, Kingston, ON, K7L 3N6, Canada speicher@mast.queensu.ca