Séminaire Lotharingien de Combinatoire, B39c(1997), 38pp.

FREE PROBABILITY THEORY AND NON-CROSSING PARTITIONS

ROLAND SPEICHER ^{∗}

Abstract. Voiculescu’s free probability theory – which was introduced in an operator algebraic context, but has since then developed into an exciting theory with a lot of links to other fields – has an interesting combinatorial facet: it can be described by the combinatorial concept of multiplicative functions on the lattice of non-crossing partitions. In this survey I want to explain this connection – without assuming any knowledge neither on free probability theory nor on non-crossing partitions.

1. Introduction

The notion of ‘freeness’ was introduced by Voiculescu around 1985 in connection with some old questions in the theory of operator algebras. But Voiculescu separated freeness from this special context and emphasized it as a concept being worth to be investigated on its own sake. Furthermore, he advocated the point of view that freeness behaves in some respects like an analogue of the classical probabilistic concept ‘independence’ - but an analogue for non-commutative random variables.

This point of view turned out to be very succesful. Up to now there has evolved a free probability theory with a lot of links to quite different parts of mathematics and physics. In this survey, I want to present some introduction into this lively field; my main emphasis will be on the combinatorial aspects of freeness – namely, it has turned out that in the same way as classical probability theory is linked with all partitions of sets, free probability theory is linked with the so-called non-crossing partitions. These partitions have a lot of nice properties, reflecting features of freeness.

∗ supported by a Heisenberg fellowship of the DFG.

I want to thank the organizers of the 39e Séminaire Lotharingien de Combinatoire for the opportunity to give this talk.

2. Independence and Freeness

Let me first recall the classical notion of independence for random variables. Consider two real-valued random variables X and Y living on some probability space. In particular, we have an expectation φ which is given by integration with respect to the given probability measure P, i.e. we have

φ[f(X, Y)] = ∫ f(X(ω), Y (ω))dP (ω)  (1)

for all bounded functions of two variables. To simplify things and getting contact with a combinatorial point of view, let us assume that X and Y are bounded, so that all their moments exist (and furthermore, their distribution is determined by their moments). Then we can describe independence as a concrete rule for calculating mixed moments in X and Y – i.e. the collection of all expectations of the form φ[X^{n_{1}}Y^{m_{1}}X^{n_{2}}Y^{m_{2}} …] for all n_{i}, m_{i} ≥ 0 – out of the moments of X – i.e. φ[X^{n}] for all n – and the moments of Y – i.e. φ[Y^{n}] for all n. Namely, independence of X and Y just means:

φ[X^{n_{1}}Y^{m_{1}} … X^{n_{k}}Y^{m_{k}}] = φ[X^{n_{1}+···+n_{k}}] · φ[Y^{m_{1}+···+m_{k}}].  (2)

For example, if X and Y are independent we have

φ[XY] = φ[X]φ[Y]  (3)

and

φ[XXY Y] = φ[XY XY] = φ[XX]φ[Y Y].  (4)

Let us now come to the notion of freeness. This is an analogue for independence in the sense that it provides also a rule for calculating mixed moments of X and Y out of the single moments of X and the single moments of Y. But freeness is a non-commutative concept: X and Y are not classical random variables any more, but non-commutative random variables. This just means that we are dealing with a unital algebra A (in general non-commutative) equipped with a unital linear functional φ : A → ℂ, φ(1) = 1. (For a lot of questions it is important that the free theory is consistent if our φ’s are also positive, i.e. states; but for our more combinatorial considerations this does not play any role). Non-commutative random variables are elements in the given algebra A and we define freeness for such random variables as follows.

Definition . The non-commutative random variables X, Y ∈ A are called free (with respect of φ), if

φ[p_{1}(X)q_{1}(Y)p_{2}(X)q_{2}(Y) …] = 0  (5)

(finitely many factors), whenever the p_{i} and the q_{j} are polynomials such that

φ[p_{i}(X)] = 0 = φ[q_{j}(Y)]  (6)

for all i, j.

As mentioned above, this should be seen as a rule for calculating mixed moments in X and Y out of moments of X and moments of Y. In contrary to the case of independence, this is not so obvious from the definition. So let us look at some examples to get an idea of that concept. In the following X and Y are assumed to be free and we will look at some mixed moments.

The simplest mixed moment is φ[XY]. Our above definition tells us immediately that

φ[XY] = 0 if φ[X] = 0 = φ[Y].  (7)

But what about the general case when X and Y are not centered. Then we do the following trick: Since our definition allows us to use polynomials in X and Y – we should perhaps state explicitely that polynomials with constant terms are allowed – we just look at the centered variables p(X) = X − φ[X]1 and q(Y) = Y − φ[Y]1 and our definition of freeness yields

\begin{aligned}0 = φ[p(X)q(Y)] & = φ[(X − φ[X]1)(Y − φ[Y]1)] \\ & = φ[XY] − φ[X]φ[Y], \end{aligned}  (8)

which implies that we have in general

φ[XY] = φ[X]φ[Y].  (9)

In the same way one can deal with more complicated mixed moments. E.g. by looking at

φ[(X^{2} − φ[X^{2}]1)(Y^{2} − φ[Y^{2}]1)] = 0  (10)

we get

φ[XXY Y] = φ[XX]φ[Y Y].  (11)

Up to now there is no difference to the results for independent random variables. But consider next the mixed moment φ[XY XY]. Again we can calculate this moment by using

φ[(X − φ[X]1)(Y − φ[Y]1)(X − φ[X]1)(Y − φ[Y]1)] = 0. (12)

Resolving this for φ[XY XY] (and using induction for the other appearing mixed moments, which are of smaller order) we obtain

φ[XY XY] = φ[XX]φ[Y]φ[Y] + φ[X]φ[X]φ[Y Y] − φ[X]φ[Y]φ[X]φ[Y]. (13)

From this we see that freeness is something different from independence; indeed it seems to be more complicated: in the independent case we only get a product of moments of X and Y, whereas here in the free case we have a sum of such product. Furthermore, from the above examples one sees that variables which are free cannot commute in general: if X and Y commute then φ[XXY Y] must be the same as φ[XY XY], which gives, by comparision between (11) and (13) very special relations between different moments of X and of Y. Taking the analogous relations for higher mixed moments into account it turns out that commuting variables can only be free if at least one of them is a constant. This means that freeness is a real non-commutative concept; it cannot be considered as a special kind of dependence between classical random variables.

The main problem (at least from a combinatorial point of view) with the definition of freeness is to understand the combinatorial structure behind this concept. Freeness is a rule for calculating mixed moments, and although we know in principle how to calculate these mixed moments, this rule is not very explicit. Up to this point, it is not clear how one can really work with this concept.

Two basic problems in free probability theory are the investigation of the sum and of the product of two free random variables. Let X and Y be free, then we want to understand X + Y and XY. Both these problems were solved by Voiculescu by some operator algebraic methods, but the main message of my survey will be that there is a beautiful combinatorial structure behind these operations. First, we will concentrate on the problem of the sum, which results in the notion of the additive free convolution. Later, we will also consider the problem of the product (multiplicative free convolution).

3. Additive free convolution

Let us state again the problem: We are given X and Y, i.e. we know their moments φ[X^{n}] and φ[Y^{n}] for all n. We assume X and Y are free and we want to understand X + Y, i.e. we want to calculate all moments φ[(X + Y)^{n}]. Since the moments of X + Y are just sums of mixed moments in X and Y, we know for sure that there must be a rule to express the moments of X + Y in terms of the moments of X and the moments of Y. But how can we describe this rule explicitely?

Again it is a good point of view to consider this problem in analogy with the classical problem of taking the sum of independent random variables. This classical problem is of course intimately connected with the classical notion of convolution of probability measures. By analogy, we are thus dealing with (additive) free convolution.

Usually these operations are operations on the level of probability measures, not on the level of moments, but (at least in the case of selfadjoint bounded random variables) these two points of view determine each other uniquely. So, instead of talking about the collection of all moments of some random variable X we can also consider the distribution μ_{X} of X which is a probability measure on ℝ whose moments are just the moments of X, i.e.

φ[X^{n}] = ∫ t^{n}dμ_{X}(t).  (14)

Let us first take a look at the classical situation before we deal with the free counterpart.

3.1. Classical convolution. Assume X and Y are independent, then we know that the moments of X + Y can be written in terms of the moments of X and the moments of Y or, equivalently, the distribution μ_{X+Y} of X + Y can be calculated somehow out of the distribution μ_{X} of X and the distribution μ_{Y} of Y. Of course, this ‘somehow’ is nothing else than the convolution of probability measures,

μ_{X+Y} = μ_{X} ∗ μ_{Y} ,  (15)

a well-understood operation.

The main analytical tool for handling this convolution is the concept of the Fourier transform (or characteristic function of the random variable). To each probability measure μ or to each random variable X with distribution μ (i.e. μ_{X} = μ) we assign a function F_{μ} on ℝ given by

F_{μ}(t) := ∫ e^{itx}dμ(x) = φ[e^{itX}].  (16)

From our combinatorial point of view it is the best to view F_{μ} just as a formal power series in the indeterminate t. If we expand

F_{μ}(t) = ∑_{n=0}^{∞} \frac{(it)^{n}}{n!} φ[X^{n}]  (17)

then we see that the Fourier transform is essentially the exponential generating series in the moments of the considered random variable.

The importance of the Fourier transform in the context of the classical convolution comes from the fact that it behaves very nicely with respect to convolution, namely

F_{μ∗ν}(t) = F_{μ}(t) · F_{ν}(t).  (18)

If we take the logarithm of this equation then we get

log F_{μ∗ν}(t) = log F_{μ}(t) + log F_{ν}(t),  (19)

i.e. the logarithm of the Fourier transform linearizes the classical convolution.

3.2. Free convolution. Now consider X and Y which are free. Then freeness ensures that the moments of X +Y can be expressed somehow in terms of the moments of X and the moments of Y, or, equivalently, the distribution μ_{X+Y} of X + Y depends somehow on the distribution μ_{X} of X and the distribution μ_{Y} of Y. Following Voiculescu [25], we denote this ‘somehow’ by ⊞,

μ_{X+Y} = μ_{X} ⊞ μ_{Y} ,  (20)

and call this operation (additive) free convolution. This is of course just a notation for the object which we want to understand and the main question is whether we can find some analogue of the Fourier transform which allows us to deal effectively with ⊞. This question was solved by Voiculescu [25] in the affirmative: He provided an analogue of the logarithm of the Fourier transform which he called R-transform. Thus, to each probability measure μ he assigned an R-transform R_{μ}(z) – which is in an analytic function on the upper half-plane, but which we will view again as a formal power series in the indeterminate z – in such a way that this R-transform behaves linear with respect to free convolution, i.e.

R_{μ⊞ν}(z) = R_{μ}(z) + R_{ν}(z).  (21)

Up to now I have just described what properties the R-transform should have for being useful in our context. The main point is that Voiculescu could also provide an algorithm for calculating such an object. Namely, the R-transform has to be calculated from the Cauchy-transform G_{μ} which is defined by

G_{μ}(z) = ∫ \frac{1}{z − x}dμ(x) = φ[\frac{1}{z − X}].  (22)

This Cauchy-transform determines the R-transform uniquely by the prescription that G_{μ}(z) and R_{μ}(z)+1/z are inverses of each other with respect to composition:

G_{μ}[R_{μ}(z) + 1/z] = z.  (23)

Although the logarithm of the Fourier transform and the R-transform have analogous properties with respect to classical and free convolution, the above analytical description looks quite different for both objects.

My aim is now to show that if we go over to a combinatorial level then the description of classical convolution ∗ and free convolution ⊞ becomes much more similar (and, indeed, we can understand the above formulas as translations of combinatorial identities into generating power series).

3.3. Cumulants. The connection of the above transforms with combinatorics comes from the following observation. The Fourier-transform and the Cauchy-transform are both formal power series in the moments of the considered distribution. If we write the logarithm of the Fouriertransform and the R-transform also as formal power series then their coefficients must be some functions of the moments. In the classical case this coefficients are essentially the so-called cumulants of the distribution. In analogy we will call the coefficients of the R-transform the free cumulants. The fact that log F and R behave additively under classical and free convolution, respectively, implies of course for the coefficients of these series that they, too, are additive with respect to the respective convolution. This means the whole problem of describing the structure of the corresponding convolution has been shifted to the understanding of the connection between moments and cumulants.

Let us state this shift of the problem again more explicitely – for definiteness in the case of the classical convolution. We have random variables X and Y which are independent and we want to calculate the moments of X + Y out of the moments of X and the moments of Y. But it is advantegous (in the free case even much more than in the classical case) to go over from the moments to new quantities c_{n}, which we call cumulants, and which behave additively with repect to the convolution, i.e. we have c_{n}(X + Y) = c_{n}(X) + c_{n}(Y). The whole problem has thus been shifted to the connection between moments and cumulants. Out of the moments we must calculate cumulants and the other way round. The connection for the first two moments is quite easy, namely

m_{1} = c_{1}  (24)

and

m_{2} = c_{2} + c_{1}^{2}  (25)

(i.e. the second cumulant c_{2} = m_{2} − m_{1}^{2} is just the variance of the measure). In general, the n-th moment is a polynomial in the cumulants c_{1}, …, c_{n}, but it is very hard to write down a concrete formula for this. Nevertheless there is a very nice way to understand the combinatorics behind this connection, and this is given by the concept of multiplicative functions on the lattice of all partitions.

So let me first recall this connection between classical probability theory and multiplicative functions before I am going to convince you that the description of free probability theory can be done in a very analogous way.

4. Combinatorial aspects of classical convolution

On a combinatorial level classical convolution can be described quite nicely with the help of multiplicative functions on the lattice of all partitions. I extracted my knowledge on this point of view from the fundamental work of Rota [16, 4]. Let me briefly recall these wellknown notions.

4.1. Lattice of all partitions and their incidence algebra. Let n be a natural number. A partition π = {V_{1}, …, V_{k}} of the set {1, …, n} is a decomposition of {1, …, n} into disjoint and non-empty sets V_{i}, i.e. V_{i} ≠ ∅, V_{i} ∩ V_{j} = ∅ (i ≠ j) and ⋃_{i=1}^{k} V_{i} = {1, …, n}. The elements V_{i} are called the blocks of the partition π. We will denote the set of all partitions of {1, …, n} by P(n). This set becomes a lattice if we introduce the following partial order (called refinement order): π ≤ σ if each block of σ is a union of blocks of π. We will denote the smallest and the biggest element of P(n) – consisting of n blocks and one block, respectively – by special symbols, namely

0_{n} := {(1), (2), …, (n)},  1_{n} := {(1, 2, …, n)}.  (26)

An example for the refinement order is the following:

{(1, 3), (2), (4)} ≤ {(1, 3), (2, 4)}.  (27)

Of course, there is no need to consider only partitions of the sets {1, …, n}, the same definitions apply for arbitrary sets S and we have a natural isomorphism P(S) ≅ P(|S|).

We consider now the collection of all partition lattices P(n) for all n,

P := ⋃_{n∈ℕ}P(n),  (28)

and in such a frame (of a locally finite poset) there exists the combinatorial notion of an incidence algebra, which is just the set of special functions with two arguments from these partition lattices: The incidence algebra consists of all functions

f : ⋃_{n∈ℕ}(P(n) × P(n)) → ℂ  (29)

subject to the following condition:

f(π, σ) = 0,  whenever π ≰ σ  (30)

Sometimes we will also consider functions of one element; these are restrictions of functions of two variables as above to the case where the first argument is equal to some 0_{n}, i.e.

f(π) = f(0_{n}, π) for π ∈ P(n).  (31)

On this incidence algebra we have a canonical (combinatorial) convolution ⋆: For f and g functions as above, we define f ⋆ g by

(f ⋆ g)(π, σ) := ∑_{\begin{matrix}τ∈P(n) \\ π≤τ≤σ \end{matrix}} f(π, τ)g(τ, σ) for π ≤ σ ∈ P(n). (32)

One should note that apriori this combinatorial convolution ⋆ has nothing to do with our probabilistic convolution ∗ for probability measures; but of course we will establish a connection between these two concepts later on.

The following special functions from the incidence algebra are of prominent interest: The neutral element δ for the combinatorial convolution is given by

δ(π, σ) = \begin{cases}1, & π = σ \\ 0, & otherwise. \end{cases}  (33)

The zeta function is defined by

Zeta(π, σ) = \begin{cases}1, & π ≤ σ \\ 0, & otherwise. \end{cases}  (34)

It is an easy exercise to check that the zeta function possesses an inverse; this is called the Möbius function of our lattice: Moeb is defined by

Moeb ⋆ Zeta = Zeta ⋆ Moeb = δ.  (35)

4.2. Multiplicative functions. The whole incidence algebra is a quite big object which is in general not so interesting; in particular, one should note that up to now, although we have taken the union over all n, there was no real connection between the involved lattices for different n. But now we concentrate on a subclass of the incidence algebra which only makes sense if there exists a special kind of relation between the P(n) for different n – this subclass consists of the so-called multiplicative functions.

Our functions f of the incidence algebra have two arguments – f(π, σ) – but since non-trivial things only happen for π ≤ σ we can also think of f as a function of the intervals in P, i.e. of the sets [π, σ] := {τ ∈ P(n) | π ≤ τ ≤ σ} for π, σ ∈ P(n) (n ∈ ℕ) and π ≤ σ. One can now easily check that for our partition lattices such intervals decompose always in a canonical way in a product of full partition lattices, i.e. for π, σ ∈ P(n) with π ≤ σ there are canonical natural numbers k_{1}, k_{2}, … such that

[π, σ] ≅ P(1)^{k_{1}} × P(2)^{k_{2}} × · · · .  (36)

(Of course, only finitely many factors are involved.) A multiplicative function factorizes by definition in an analogous way according to this factorization of intervals: For each sequence (a_{1}, a_{2}, …) of complex numbers we define the corresponding multiplicative function f (we denote the dependence of f on this sequence by f ↭ (a_{1}, a_{2}, …)) by the requirement

f(π, σ) := a_{1}^{k_{1}}a_{2}^{k_{2}} …  if [π, σ] ≅ P(1)^{k_{1}} × P(2)^{k_{2}} × · · · .(37)

Thus we have in particular that f(0_{n}, 1_{n}) = a_{n}, everything else can be reduced to this by factorization. It can be seen directly that the combinatorial convolution of two multiplicative functions is again multiplicative.

Let us look at some examples for the calculation of multiplicative functions.

\begin{aligned}[\{(1, 3), (2), (4)\}, \{(1, 2, 3, 4)\}] & ≅ [\{(1), (2), (4)\}, \{(1, 2, 4)\}] \\ & ≅ P(3), \end{aligned} (38)

thus

f({(1, 3), (2), (4)}, {(1, 2, 3, 4)}) = a_{3}.  (39)

Note in particular that if the first argument is equal to some 0_{n}, then the factorization is according to the block structure of the second argument, and hence multiplicative functions of one variable are really multiplicative with respect to the blocks. E. g., we have

[{(1), (2), (3), (4), (5), (6), (7), (8)}, {(1, 3, 5), (2, 4), (6), (7, 8)}] ≅ [{(1), (3), (5)}, {(1, 3, 5)}] × [{(2), (4)}, {(2, 4)}] ×

× [{(6)}, {(6)}] × [{(7), (8)}, {(7, 8)}], (40)

and hence for the multiplicative function of one argument

f({(1, 3, 5), (2, 4), (6), (7, 8)}) = f({(1, 3, 5)}) · f({(2, 4)}) · f({(6)}) · f({(7, 8)}) = a_{3}a_{2}a_{1}a_{2}. (41)

The special functions δ, Zeta, and Moeb are all multiplicative with determining sequences as follows:

δ ↭ (1, 0, 0, …)  (42)
Zeta ↭ (1, 1, 1, …)  (43)
Moeb ↭ ((−1)^{n−1}(n − 1)!)_{n≥1}  (44)

4.3. Connection between probabilistic and combinatorial convolution. Recall our strategy for describing classical convolution combinatorially: Out of the moments m_{n} = φ(X^{n}) (n ≥ 1) of a random variable X we want to calculate some new quantities c_{n} (n ≥ 1) – which we call cumulants – that behave additively with respect to convolution. The problem is to describe the relation between the moments and the cumulants. This relation can be formulated in a nice way by using the concept of multiplicative functions on all partitions. Since such functions are determined by a sequence of complex numbers, we can use the sequence of moments to define a multiplicative function M (moment function) and the sequence of cumulants to define another multiplicative function C (cumulant function). It is a well known fact (although not to localize easily in this form in the literature) [16, 17] that the relation between these two multiplicative funtions is just given by taking the combinatorial convolution with the zeta function or with the Möbius function.

Theorem . Let m_{n} and c_{n} be the moments and the classical cumulants, respectively, of a random variable X. Let M and C be the corresponding multiplicative functions on the lattice of all partitions, i.e.

M ↭ (m_{1}, m_{2}, …),  C ↭ (c_{1}, c_{2}, …).  (45)

Then the relation between M and C is given by

M = C ⋆ Zeta,  (46)

or equivalently by

C = M ⋆ Moeb.  (47)

Let me also point out that this combinatorial description is essentially equivalent to the previously mentioned analytical description of classical convolution via the Fourier transform. Namely, if we denote by

A(z) := 1 + ∑_{n=1}^{∞} \frac{m_{n}}{n!} z^{n},  B(z) := ∑_{n=1}^{∞} \frac{c_{n}}{n!}z^{n}  (48)

the exponential power series of the moment and cumulant sequences, respectively, then it is a well known fact [16] that the statement of the above theorem translates in terms of these series into

A(z) = exp B(z) or B(z) = log A(z).  (49)

But since the Fourier transform F_{μ} of the random variable X (with μ = μ_{X}) is connected with A by

F_{μ}(t) = A(it),  (50)

this means that

B(it) = log F_{μ}(t),  (51)

which is exactly the usual description of the classical cumulants – that they are given by the coefficents of the logarithm of the Fourier transform; the additivity of the logarithm of the Fourier transform under classical convolution is of course equivalent to the same property for the cumulants.

5. Combinatorial aspects of free convolution

Now we switch from classical convolution to free convolution. Whereas on the analytical level the analogy between the logarithm of the Fourier transform and the R-transform is not so obvious, on the combinatorial level things become very clear: The description of free convolution is the same as the description of classical convolution, the only difference is that one has to replace all partitions by the so-called non-crossing partitions.

5.1. Lattice of non-crossing partitions and their incidence algebra. We call a partition π ∈ P(n) crossing if there exist four numbers 1 ≤ i < k < j < l ≤ n such that i and j are in the same block, k and l are in the same block, but i, j and k, l belong to two different blocks. If this situation does not happen, then we call π non-crossing. The set of all non-crossing partitions in P(n) is dentoted by NC(n), i.e.

NC(n) := {π ∈ P(n) | π non-crossing.}  (52)

Again, this set becomes a lattice with respect to the refinement order. Of course, 0_{n} and 1_{n} are non-crossing and they are the smallest and the biggest element of NC(n), respectively.

The name ‘non-crossing’ becomes quite clear in a graphical representation of partitions: The partition

π = {(1, 3, 5), (2), (4)}  =  ^{1 2 3 4 5}

is non-crossing, whereas

π = {(1, 3, 5), (2, 4)}  =  ^{1 2 3 4 5}

is crossing.

One should note, that the linear order of the set {1, …, n} is of course important for deciding whether a partition is crossing or noncrossing. Thus, in contrast to the case of all partitions, non-crossing partitions only make sense for a set with a linear order. However, one should also note that instead of the linear order of {1, …, n} we could also put the points 1, …, n on a circle and consider them with circular order. The concept ‘non-crossing’ is also compatible with this.

For n = 1, n = 2, and n = 3 all partitions are non-crossing, for n = 4 only {(1, 3), (2, 4)} is crossing. The following figure shows NC(4). Note the high symmetry of that lattice compared to P(4).

Non-crossing partitions were introduced by Kreweras [8] in 1972 (but see also [1]) and since then there have been some combinatorial investigations on this lattice, e.g. [14, 6, 7, 18]. But it seems that the concept of incidence algebra and multiplicative functions for this lattice have not received any interest so far. Motivated by my investigations [19] on freeness I introduced these concepts in [20]. It is quite clear that this goes totally in parallel to the case of all partitions: We consider the collection of the lattices of non-crossing partitions for all n,

NC := ⋃_{n∈ℕ}NC(n),  (53)

and the incidence algebra is as before the set of special functions with two arguments from these lattices: The incidence algebra of noncrossing partitions consists of all functions

f : ⋃_{n∈ℕ}(NC(n) × NC(n)) → ℂ  (54)

subject to the following condition:

f(π, σ) = 0,  whenever π ≰ σ.  (55)

Again, sometimes we will also consider functions of one element; these are restrictions of functions of two variables as above to the case where the first element is equal to some 0_{n}, i.e.

f(π) = f(0_{n}, π) for π ∈ NC(n).  (56)

Again, we have a canonical (combinatorial) convolution ⋆ on this incidence algebra: For functions f and g as above, we define f ⋆ g by

(f ⋆ g)(π, σ) := ∑_{\begin{matrix}τ∈NC(n) \\ π≤τ≤σ \end{matrix}} f(π, τ)g(τ, σ) for π ≤ σ ∈ NC(n). (57)

As before we have the following important special functions: The neutral element δ for the combinatorial convolution ⋆ is given by

δ(π, σ) = \begin{cases}1, & π = σ \\ 0, & otherwise. \end{cases}  (58)

The zeta function is defined by

zeta(π, σ) = \begin{cases}1, & π ≤ σ \\ 0, & otherwise. \end{cases}  (59)

Again, the zeta function possesses an inverse, which we call Möbius function: moeb is defined by

moeb ⋆ zeta = zeta ⋆ moeb = δ.  (60)

5.2. Multiplicative functions on non-crossing partitions. Whereas the notion of an incidence algebra and the corresponding combinatorial convolution is a very general notion (which can be defined on any locally finite poset), the concept of a multiplicative function requires a very special property of the considered lattices, namely that each interval can be decomposed into a product of full lattices. This was fulfilled in the case of all partitions and it is not hard to see that we have the same property also for non-crossing partitions [20, 10]: For all π, σ ∈ NC(n) with π ≤ σ there exist canonical natural numbers k_{1}, k_{2}, … such that

[π, σ] ≅ NC(1)^{k_{1}} × NC(2)^{k_{2}} × ….  (61)

Having this factorization property at hand it is quite natural to define a multiplicative function f (for non-crossing partitions) corresponding to a sequence (a_{1}, a_{2}, …) of complex numbers by the requirement that

f(π, σ) := a_{1}^{k_{1}}a_{2}^{k_{2}} …  (62)

if [π, σ] has a factorization as above. Again we use the notation f ↭ (a_{1}, a_{2} …) to denote the dependence of f on the sequence (a_{1}, a_{2}, …).

As before, the special functions δ, zeta, and moeb are all multiplicative with the following determining sequences:

δ ↭ (1, 0, 0, …)  (63)
zeta ↭ (1, 1, 1, …)  (64)
moeb ↭ ((−1)^{n−1}c_{n−1})_{n≥1},  (65)

where c_{n} are the Catalan numbers.

Let me stress the following: Consider π ∈ NC(n) ⊂ P(n). Then the factorization for intervals of the form [0_{n}, π] is the same in P(n) and in NC(n), i.e. we have the same k_{i} in both decompositions:

[0_{n}, π]_{P(n)} ≅ P(1)^{k_{1}} × P(2)^{k_{2}} × …

⟺ [0_{n}, π]_{NC(n)} ≅ NC(1)^{k_{1}} × NC(2)^{k_{2}} × …. (66)

For intervals of the form [π, 1_{n}], however, the factorization might be quite different – reflecting the different structure of both lattices. For example, for π = {(1, 3), (2), (4)} ∈ NC(4) ⊂ P(4) we have

[{(1, 3), (2), (4)}, {(1, 2, 3, 4)}]_{P(4)} ≅ P(3),  (67)

but

[{(1, 3), (2), (4)}, {(1, 2, 3, 4)}]_{NC(4)} ≅ NC(2) × NC(2). (68)

The latter factorization comes from the fact that, by the non-crossing property, the block (1, 3) separates the blocks (2) and (4) from each other.

5.3. Connection between free convolution and combinatorial convolution. As in the case of classical convolution we want to describe free convolution by quantities k_{n} (n ≥ 1) which behave additively unter free convolution. These k_{n} are calculated somehow out of the moments m_{n} of a random variable X – they should essentially be the coefficients of the R-transform – and they will be called the free cumulants of X. The question is how we calculate the cumulants out of the moments and vice versa. The answer is very simple: it works as in the classical case, just replace all partitions by non-crossing partitions.

Theorem (Speicher [20]). Let m_{n} and k_{n} be the moments and the free cumulants, respectively, of a random variable X. Let m and k be the corresponding multiplicative functions on the lattice of non-crossing partitions, i.e.

m ↭ (m_{1}, m_{2}, …),  k ↭ (k_{1}, k_{2}, …).  (69)

Then the relation between m and k is given by

m = k ⋆ zeta,  (70)

or equivalently

k = m ⋆ moeb.  (71)

The important point that I want to emphasize is that this combinatorial relation between moments and free cumulants can again be translated into a relation between the corresponding formal power series; these series are essentially the Cauchy transform and the Rtransform and their relation is nothing but Voiculescu’s formula for the R-transform.

Let us look at this more closely: By taking into account the noncrossing character of the involved partitions, the relation m = k ⋆ zeta can be written more concretely in a recursive way as (where m_{0} = 1)

m_{n} = ∑_{r=1}^{n} ∑_{\begin{matrix}i_{1},...,i_{r}≥0 \\ i_{1}+...i_{r}+r=n \end{matrix}} k_{r}m_{i_{1}} … m_{i_{r}}.  (72)

Multiplying this by z^{n}, distributing the powers of z and summing over all n this gives

∑_{n=0}^{∞} m_{n}z^{n} = 1 + ∑_{n=1}^{∞} ∑_{r=1}^{∞} ∑_{\begin{matrix}i_{1},...,i_{r}≥0 \\ i_{1}+...i_{r}+r=n \end{matrix}} k_{r}z^{r}m_{i_{1}}z^{i_{1}} … m_{i_{r}}z^{i_{r}}, (73)

which is easily recognized as a relation between the formal power series

C(z) := 1 + ∑_{n=1}^{∞} m_{n}z^{n} and D(z) := 1 + ∑_{n=1}^{∞} k_{n}z^{n} (74)

of the momens and of the free cumulants. The above formula reads in terms of these power series as

C(z) = D[zC(z)],  (75)

and the simple redefinitions

G(z) := \frac{C(1/z)}{z}  and R(z) = \frac{D(z) − 1}{z}  (76)

change this into

G[R(z) + 1/z] = z.  (77)

But – by noticing that the above defined function G is nothing but the Cauchy transform – this is exactly Voiculescu’s formula for the R-transform.

Thus we see: The analytical descriptions of the classical and the free convolution via the logarithm of the Fourier transform and via the Rtransform are nothing but translations of the combinatorial relations between moments and cumulants into formal power series. Whereas the analytical descriptions look quite different for both cases the underlying combinatorial relations are very similar. They have the same structure, the only difference is the replacement of all partitions by non-crossing partitions.

6. Freeness and generalized cumulants

Whereas up to now I have described free cumulants as a good object to deal with additive free convolution I will now show that cumulants have a much more general meaning: they are the right concept to deal with the notion of freeness itself. From this more general point of view we will also get a very simple proof of the main property of free cumulants, that they linearize free convolution. (In Sect. 5.3, we have presented the connection between moments and cumulants, but we have not yet given any idea why the cumulants from that theorem are additive unter free convolution.)

6.1. Generalized cumulants. Whereas I defined freeness in Sect. 2 only for two random variables, I will now present the general case.

Again, we are working on a unital algebra A equipped with a fixed unital linear functional φ. Usually one calls the pair (A, φ) a (noncommutative) probability space.

We consider elements a_{1}, …, a_{l} ∈ A of our algebra (called random variables) and the only information we use about these random variables is the collection of all mixed moments, i.e. all quantities

φ[a_{i(1)} … a_{i(n)}] for all n ∈ ℕ and all 1 ≤ i(1), …, i(n) ≤ l.(78)

Definition . The random variables a_{1}, …, a_{l} ∈ A are called free (with respect to φ) if

φ[p_{1}(a_{i(1)})p_{2}(a_{i(2)}) … p_{n}(a_{i(n)})] = 0  (79)

whenever the p_{j} (n ∈ ℕ, j = 1, …, n) are polynomials such that

φ[p_{j}(a_{i(j)})] = 0 (j = 1, …, n)  (80)

and

i(1) ≠ i(2) ≠ ⋯ ≠ i(n).  (81)

Note that the last condition in the definition requires only that consecutive indices are different; it might happen, e.g., that i(1) = i(3).

As said before, this definition provides a rule for calculating mixed moments, but it is far from being explicit. Thus freeness is difficult to handle in terms of moments. The cumulant philosophy presented so far can be generalized to this more general setting by trying to find some other quantities in terms of which freeness is much easier to describe. I will now show that there are indeed such (generalized) free cumulants and that the transition between moments and cumulants is given as before with the help of non-crossing partitions.

Similarly as our general moments are of the form

φ[a_{i(1)} … a_{i(n)}],  (82)

our general cumulants (k_{n})_{n∈ℕ} will be n-linear functionals k_{n} with arguments of the form

k_{n}(a_{i(1)}, …, a_{i(n)}) (n ∈ ℕ, 1 ≤ i(1), …, i(n) ≤ l).  (83)

In the one-dimensional case, as treated up to now, we had only one random variable a and the previously considered numbers k_{n} are related with the above functionals by k_{n} = k_{n}(a, …, a).

The rule for calculating the cumulants out of the moments is the same as before, formally it is given by φ = k ⋆ zeta. This means that for calculating a moment φ[a_{i(1)} … a_{i(n)}] in terms of cumulants we have to sum over all non-crossing partitions, each such partition gives a contribution in terms of cumulants which is calculated according to the factorization of that partition into its blocks:

φ[a_{i(1)} … a_{i(n)}] = ∑_{π∈NC(n)} k(π)[a_{i(1)}, …, a_{i(n)}];

here k(π)[a_{i(1)}, …, a_{i(n)}] denotes a product of cumulants where the a_{i(1)}, …, a_{i(n)} are distributed as arguments to these cumulants according to the block structure of π.

The best way to get the idea is to look at some examples:

φ[a_{1}] = k_{1}(a_{1})  (84)
φ[a_{1}a_{2}] = k_{2}(a_{1}, a_{2}) + k_{1}(a_{1})k_{1}(a_{2})  (85)

\begin{matrix}φ[a_{1}a_{2}a_{3}] = & k_{3}(a_{1}, a_{2}, a_{3}) + k_{2}(a_{1}, a_{2})k_{1}(a_{3}) \\ + k_{2}(a_{2}, a_{3})k_{1}(a_{1}) + k_{2}(a_{1}, a_{3})k_{1}(a_{2}) \\ + k_{1}(a_{1})k_{1}(a_{2})k_{1}(a_{3}) \end{matrix}  (86)

\begin{matrix}φ[a_{1}a_{2}a_{3}a_{4}] = & k_{4}(a_{1}, a_{2}, a_{3}, a_{4}) + k_{3}(a_{1}, a_{2}, a_{3})k_{1}(a_{4}) \\ + k_{3}(a_{1}, a_{2}, a_{4})k_{1}(a_{3}) + k_{3}(a_{1}, a_{3}, a_{4})k_{1}(a_{2}) \\ + k_{3}(a_{2}, a_{3}, a_{4})k_{1}(a_{1}) + k_{2}(a_{1}, a_{2})k_{2}(a_{3}, a_{4}) \\ + k_{2}(a_{1}, a_{4})k_{2}(a_{2}, a_{3}) + k_{2}(a_{1}, a_{2})k_{1}(a_{3})k_{1}(a_{4}) \\ + k_{2}(a_{1}, a_{3})k_{1}(a_{2})k_{1}(a_{4}) + k_{2}(a_{1}, a_{4})k_{1}(a_{2})k_{1}(a_{3}) \\ + k_{2}(a_{2}, a_{3})k_{1}(a_{1})k_{1}(a_{4}) + k_{2}(a_{2}, a_{4})k_{1}(a_{1})k_{1}(a_{3}) \\ + k_{2}(a_{3}, a_{4})k_{1}(a_{1})k_{1}(a_{2}) + k_{1}(a_{1})k_{1}(a_{2})k_{1}(a_{3})k_{1}(a_{4}). \end{matrix} (87)

Note that in the last example the summation is only over the 14 noncrossing partitions, the crossing {(1, 3), (2, 4)} makes no contribution.

Of course, on can also invert the above expressions in order to get the cumulants in terms of moments; formally we can write this as k = φ ⋆ moeb.

The justification for the introduction of these quantities comes from the following theorem, which shows that these free cumulants behave very nicely with respect to freeness.

Theorem (Speicher [20], cf. [9]). In terms of cumulants, freeness can be characterized by the vanishing of mixed cumulants, i.e. the following two statements are equivalent:

i) a_{1}, …, a_{l} are free ii) k_{n}(a_{i(1)}, …, a_{i(n)}) = 0 (n ∈ ℕ) whenever there are 1 ≤ p, q ≤ n with: i(p) ≠ i(q).

This characterization of freeness is nothing but a translation of the original definition in terms of moments to cumulants, by using the relation φ = k ⋆ zeta. However, it should be clear that this characterization in terms of cumulants is much easier to handle than the original definition.

Let me indicate the main step in the proof of the theorem.

Proof. In terms of moments freeness is characterized by the vanishing of very special moments, namely mixed, alternating and centered ones. Because of the relation φ = k ⋆ zeta it is clear that, by induction, this should also translate to the vanishing of special cumulants. However, what we claim is that on the level of cumulants the assumptions are much less restrictive, namely the arguments only have to be mixed. Thus by the transition from moments to cumulants (via non-crossing partitions) we get somehow rid of the conditions ‘alternating’ and ‘centered’. The essential point is centeredness. (It is also this condition that is not so easy to handle in concrete calculations with moments.) That we can get rid of this is essentially equivalent to the fact that

k_{n}(…, 1, …) = 0 for all n ≥ 2.  (88)

That this removes the centeredness condition for cumulants is clear, since with the help of this we can go over from non-centered to centered arguments without changing the cumulants:

k_{n}(a_{i(1)}, …, a_{i(n)}) = k_{n}(a_{i(1)} − φ[a_{i(1)}]1, …, a_{i(n)} − φ[a_{i(n)}]1). (89)

So it only remains to see the validity of (88). But this follows from the fact that the calculation rule φ = k ⋆ zeta – which is indeed a system of rules, one for each n – is consistent for different n’s. This can again be seen best by an example. Let us see why k_{4}(a_{1}, a_{2}, a_{3}, 1) = 0. By induction, we can assume that we know the vanishing of k_{2} and k_{3} if one of their arguments is equal to 1. Now we take formula (87) and put there a_{4} = 1. According to our induction hypothesis some of the terms will vanish and we remain with

\begin{aligned}φ[a_{1}a_{2}a_{3}] & = φ[a_{1}a_{2}a_{3}1] \\ & = k_{4}(a_{1}, a_{2}, a_{3}, 1) + k_{3}(a_{1}, a_{2}, a_{3})k_{1}(1) \\ & + k_{2}(a_{1}, a_{2})k_{1}(a_{3})k_{1}(1) + k_{2}(a_{1}, a_{3})k_{1}(a_{2})k_{1}(1) \\ & + k_{2}(a_{2}, a_{3})k_{1}(a_{1})k_{1}(1) + k_{1}(a_{1})k_{1}(a_{2})k_{1}(a_{3})k_{1}(1). \end{aligned} (90)

Note that we have k_{1}(1) = φ[1] = 1 and thus the right hand side of the above is, by (86), exactly equal to

k_{4}(a_{1}, a_{2}, a_{3}, 1) + φ[a_{1}a_{2}a_{3}].  (91)

But this implies k_{4}(a_{1}, a_{2}, a_{3}, 1) = 0.

6.2. Additive free convolution. Having the characterization of freeness by the vanishing of mixed cumulants, it is now quite easy to give a selfcontained combinatorial (i.e. without using the results of Voiculescu on the R-transform) proof of the linearity of free cumulants under additive free convolution. Recall that the problem of describing additive free convolution consists in calculating, for X and Y being free, the moments of X + Y in terms of moments of X and moments of Y. As a symbolic notation for this we have introduced the concept of (additive) free convolution,

μ_{X+Y} = μ_{X} ⊞ μ_{Y} .  (92)

As described before, this problem can be treated by going over to the free cumulants according to

m_{X} = k_{X} ⋆ zeta or k_{X} = m_{X} ⋆ moeb,  (93)

where m_{X} and k_{X} are the multiplicative functions on the lattice of noncrossing partitions determined by the sequence of moments (m_{n}^{X})_{n≥1} of X and the sequence of free cumulants (k_{n}^{X})_{n≥1} of X, respectively. In the last section I have shown that the above relation (93) is essentially equivalent to Voiculescu’s formula for the calculation of the R-transform. So it only remains to recognize the additivity of the free cumulants (and thus of the R-transform) under free convolution. But since the one-dimensional cumulants of the last section are just special cases of the above defined more general cumulants according to

k_{n}^{X} = k_{n}(X, …, X),  (94)

this additivity is a simple corollary of the vanishing of mixed cumulants in free variables:

\begin{aligned}k_{n}^{X+Y} & = k_{n}(X + Y, …, X + Y) \\ & = k_{n}(X, …, X) + k_{n}(Y, …, Y) \\ & = k_{n}^{X} + k_{n}^{Y} . \end{aligned}  (95)

Thus we have recovered, by our combinatorial approach, the full content of Voiculescu’s results on additive free convolution.

7. Multiplicative free convolution and the general structure of the combinatorial convolution on NC

7.1. Multiplicative free convolution. Voiculescu considered also the problem of the product of free random variables: if X and Y are free, how can we calculate moments of XY out of moments of X and moments of Y?

Note that in the classical case we can make a transition from the additive to the multiplicative problem just by exponentiating; thus in this case the multiplicative problem reduces to the additive one, there is no need to investigate something like multiplicative classical convolution as a new operation.

In the free case, however, this reduction does not work, because for non-commuting random variables we have in general

exp(X + Y) ≠ exp X · exp Y.  (96)

Hence it is by no means clear whether the multiplicative problem is somehow related to the additive problem.

We know that freeness results in some rule for calculating the moments of XY out of the moments of X and the moments of Y, thus the distribution of XY depends somehow on the distribution of X and the distribution of Y. As in the additive case, Voiculescu [26] introduced a special symbol, ⊠, for this ‘somehow’ and named the corresponding operation on probability measures multiplicative free convolution:

μ_{XY} = μ_{X} ⊠ μ_{Y} .  (97)

And, more importantly, he could solve the problem of describing this operation in analytic terms. In the same way as the additive problem was dealt with by introducing the R-transform, he defined now a new formal power series, called S-transform, which behaves nicely with respect to multiplicative convolution,

S_{μ⊠ν}(z) = S_{μ}(z) · S_{ν}(z).  (98)

Again he was able (by quite involved arguments) to derive a formula for the calculation of this S_{μ}-transform out of the distribution μ:

S_{μ}(z) := \frac{1 + z}{z} (∑_{n=1}^{∞} φ(X^{n})z^{n})^{<−1>},  (99)

where < −1 > denotes the operation of taking the inverse with respect to composition of formal power series.

Voiculescu dealt with two problems in connection with freeness, the additive convolution ⊞ and the multiplicative convolution ⊠, and he could solve both of them by introducing the R-transform and the Stransform, respectively. I want to emphasize that in his treatment there is no connection between both problems, he solved them independently.

One of the big advantages of our combinatorial approach is that we shall see a connection between both problems. Up to now, I have described how we can understand the R-transform combinatorially in terms of cumulants – the latter were just the coefficients in the Rtransform. My next aim is to show that also the multiplicative convolution (and the S-transform) can be described very nicely in combinatorial terms with the help of the free cumulants.

But before I come to this, let me again switch to the purely combinatorial side by recognizing that there is also still some canonical problem open.

7.2. General structure of the combinatorial convolution on NC. Recall that, in Sect. 5, we have introduced a combinatorial convolution on the incidence algebra of non-crossing partitions. We are particulary interested in multiplicative functions on non-crossing partitions and it is quite easy to check that the combinatorial convolution of multiplicative functions is again multiplicative. This means that for two multiplicative functions f and g, given by their corresponding sequences,

f ↭ (a_{1}, a_{2}, …),  g ↭ (b_{1}, b_{2}, …),  (100)

their convolution

h := f ⋆ g  (101)

must, as a multiplicative function, also be determined by some sequence of numbers

h ↭ (c_{1}, c_{2}, …).  (102)

These c_{i} are some functions of the a_{i} and b_{i} and it is an obvious question to ask for the concrete form of this connection. The answer, however, is not so obvious.

Note that in Sect. 5 we dealt with a special case of this problem, namely the case where g = zeta. This was exactly what was needed for describing additive free convolution in the form m = k ⋆ zeta, and the relation between the two series f and h = f ⋆ zeta is more or less Voiculescu’s formula for the R-transform: If

f ↭ (a_{1}, a_{2}, …) and h = f ⋆ zeta ↭ (c_{1}, c_{2}, …) (103)

then in terms of the generating power series

C(z) := 1 + ∑_{n=1}^{∞} c_{n}z^{n} and D(z) := 1 + ∑_{n=1}^{∞} a_{n}z^{n} (104)

the relation is given by

C(z) = D[zC(z)].  (105)

Now we ask for an analogue treatment of the general case h = f ⋆ g. The corresponding problem for all partitions was solved by Doubilet, Rota, and Stanley in [4]: The multiplicative functions on P correspond to exponential power series of their determining sequences and under this correspondence the convolution ⋆ goes over to composition of power series.

What is the corresponding result for non-crossing partitions? The answer to this is more involved than in the case of all partitions, but it will turn out that this is also intimately connected with the problem of multiplicative free convolution and the S-transform. In the case of all partitions there is no connection between the above mentioned result of Doubilet, Rota, and Stanley and some classical probabilistic convolution.

The answer for the case of non-crossing partitions depends on a special property of NC (which has no analogue in P): all NC(n) are self-dual and there exists a nice mapping, the (Kreweras) complementation map

K : NC(n) → NC(n),  (106)

which implements this self-duality. This complementation map is a lattice anti-isomorhism, i.e.

π ≤ σ ⇔ K(π) ≥ K(σ),  (107)

and it is defined as follows: If we have a partition π ∈ NC(n) then we insert between the points 1, 2, …, n new points ¯1, ¯2, …, n̄ (linearly or circularly), such that we have 1, ¯1, 2, ¯2, …, n, n̄. We draw now the partition π by connecting the blocks of π and we define K(π) as the biggest non-crossing partition of {¯1, ¯2, …, n̄} which does not have crossings with the partition π: K(π) is the maximal element of the set {σ ∈ NC(¯1, …, n̄) | π ∪ σ ∈ NC(1, ¯1, …, n, n̄)}. (The union of two partitions on different sets is of course just given by the union of all blocks.)

This complementation map was introduced by Kreweras [8]. Note that K^{2} is not equal to the identity but it shifts the points by one (mod n) (corresponding to a rotation in the circular picture). Simion and Ullman [18] modified the complementation map to make it involutive, but the original map of Kreweras is more adequate for our investigations. Biane [2] showed that the complementation map of Kreweras and the modification of Simion and Ullman generate together the group of all skew-automorphisms (i.e., automorphisms or anti-automorphisms) of NC(n), which is the dihedral group with 4n elements.

As an example for K we have:

K({(1, 4, 8), (2, 3), (5, 6), (7)}) = {(1, 3), (2), (4, 6, 7), (5), (8)}.(108)

1 ¯1 2 ¯2 3 ¯3 4 ¯4 5 ¯5 6 ¯6 7 ¯7 8 ¯8

With the help of this complementation map K we can rewrite our combinatorial convolution in the following way: If we have multiplicative functions connected by h = f ⋆ g, and the sequence determining h is denoted by (c_{1}, c_{2}, …), then we have by definition of our convolution

c_{n} = h(0_{n}, 1_{n}) = ∑_{π∈NC(n)} f(0_{n}, π)g(π, 1_{n}),  (109)

which looks quite unsymmetric in f and g. But the complementation map allows us to replace

[π, 1_{n}] ≅ [K(1_{n}), K(π)] = [0_{n}, K(π)]  (110)

and thus we obtain

c_{n} = ∑_{π∈NC(n)} f(0_{n}, π)g(0_{n}, K(π)) = ∑_{π∈NC(n)} f(π)g(K(π)). (111)

An immediate corollary of that observation is the commutativity of the combinatorial convolution on non-crossing partitions.

Corollary (Nica+Speicher [10]). The combinatorial convolution ⋆ on non-crossing partitions is commutative:

f ⋆ g = g ⋆ f.  (112)

Proof.

\begin{aligned}(f ⋆ g)(0_{n}, 1_{n}) & = ∑_{π∈NC(n)} f(π)g(K(π)) \\ & = ∑_{σ=K^{−1}(π)} f(K(σ))g(σ) \\ & = (g ⋆ f)(0_{n}, 1_{n}). \end{aligned}  (113)

The corresponding statement for the convolution on all partitions is not true – this is obvious from the fact that under the above stated correspondence with exponential power series this convolution goes over to composition, which is clearly not commutative. This indicates that the description of the combinatorial convolution on non-crossing partitions should differ substantially from the result for all partitions. Of course, this corresponds to the fact that the lattice of all partitions is not self-dual, there exist no analogue of the complementation map for arbitrary partitions.

7.3. Connection between ⋆ and ⊠. Before I am going on to present the solution to the problem of describing the full structure of the combinatorial convolution ⋆, I want to establish the connection between this combinatorial problem and the problem of the multiplicative free convolution.

Let X and Y be free. Then multiplicative free convolution asks for the moments of XY. In terms of cumulants we can write them as

φ[(XY)^{n}] = ∑_{π∈NC(2n)} k(π)[X, Y, X, Y, …, X, Y],  (114)

where k(π)[X, Y, X, Y, …, X, Y] denotes a product of cumulants which factorizes according to the block structure of the partition π. The vanishing of mixed cumulants in free variables implies that only such partitions π contribute where all blocks connect either only X or only Y. Such a π ∈ NC(2n) splits into the union π = π_{1} ∪ π_{2}, where π_{1} ∈ NC(1, 3, 5, …) (the positions of the X) and π_{2} ∈ NC(2, 4, 6, …) (the positions of the Y), and we can continue the above equation with

\begin{matrix}φ[(XY)^{n}] = \\ = ∑_{\begin{matrix}π=π_{1}∪π_{2}∈NC(2n) \\ π_{1}∈NC(1,3,5,...) \\ π_{2}∈NC(2,4,6,...) \end{matrix}} k(π_{1})[X, X, …, X] · k(π_{2})[Y, Y, …, Y] \\ = ∑_{π_{1}∈NC(n)}(k(π_{1})[X, X, …, X] · ∑_{\begin{matrix}π_{2}∈NC(n) \\ π_{1}∪π_{2}∈NC(2n) \end{matrix}} k(π_{2})[Y, Y, …, Y]). \end{matrix} (115)

Now note that the condition

π_{2} ∈ NC(n) with π_{1} ∪ π_{2} ∈ NC(2n)  (116)

is equivalent to

π_{2} ≤ K(π_{1})  (117)

and that with k_{Y} and m_{Y} being the multiplicative functions determined by the cumulants and the moments of Y, respectively, the relation m_{Y} = k_{Y} ⋆ zeta just means explicitely

m_{Y} (σ_{1}) = ∑_{σ_{2}≤σ_{1}} k_{Y} (σ_{2}).  (118)

Taking this into account we can continue our calculation of the moments of XY as follows:

\begin{aligned}φ[(XY)^{n}] & = ∑_{π_{1}∈NC(n)}(k_{X}(π_{1}) · ∑_{π_{2}≤K(π_{1})} k_{Y} (π_{2})) \\ & = ∑_{π_{1}∈NC(n)} k_{X}(π_{1}) · m_{Y} (K(π_{1})). \end{aligned}  (119)

According to our formulation of the combinatorial convolution in terms of the complementation map, cf. (111), this is nothing but the following relation

m_{XY} = k_{X} ⋆ m_{Y} .  (120)

Hence we can express multiplicative free convolution ⊠ in terms of the combinatorial convolution ⋆. This becomes even more striking if we remove the above unsymmetry in moments and cumulants. By applying the Möbius function on (120) we end up with

k_{XY} = m_{XY} ⋆ moeb = k_{X} ⋆ m_{Y} ⋆ moeb = k_{X} ⋆ k_{Y} ,  (121)

and we have the beautiful result

k_{XY} = k_{X} ⋆ k_{Y}  for X and Y free.  (122)

One sees that we can describe also multiplicative free convolution in terms of cumulants, just by taking the combinatorial convolution of the corresponding cumulant functions. Thus the problem of describing multiplicative free convolution ⊠ is equivalent to understanding the general structure of the combinatorial convolution h = f ⋆ g.

7.4. Description of ⋆. The above connection means in particular that Voiculescu’s description of the multiplicative free convolution, via the S-transform, must also contain (although not in an explicit form) the solution for the description of h = f ⋆ g.

This insight was the starting point of my joint work [10] with A. Nica on the combinatorial convolution ⋆. From Voiculescu’s result on the S-transform and the above connection we got an idea how the solution should look like and then we tried to derive this by purely combinatorial means.

Theorem (Nica+Speicher [10]). For a multiplicative function f on NC with

f ↭ (a_{1}, a_{2}, …)  where  a_{1} = 1  (123)

we define its ‘Fourier transform’ F(f) by

F(f)(z) := \frac{1}{z}(∑_{n=1}^{∞} a_{n}z^{n})^{<−1>}.  (124)

Then we have

F(f ⋆ g)(z) = F(f)(z) · F(g)(z).  (125)

Hence multiplicative functions on NC correspond to formal power series (but now this correspondence F is not as direct as in the case of all partitions), and under this correspondence the combinatorial convolution ⋆ is mapped onto multiplication of power series. This is of course consistent with the commutativity of ⋆.

This result is not obvious on the first look, but its proof does not require more than some clever manipulations with non-crossing partitions. Let me present you the main steps of the proof.

Proof. Let us denote for a multiplicative function f determined by a sequence (a_{1}, a_{2}, …) its generating power series by

Φ_{f}(z) := ∑_{n=1}^{∞} a_{n}z^{n}.  (126)

Then we do the summation in

c_{n} = ∑_{π∈NC(n)} f(π)g(K(π))  (127)

in such a way that we fix the first block of π and then sum over the remaining possibilities. A careful look reveals that this results in a relation

Φ_{f⋆g} = Φ_{f} ∘ Φ_{fˇ⋆g},  (128)

where fˇ⋆g is defined by

(fˇ⋆g)(0_{n}, 1_{n}) := ∑_{π∈NC′(n)} f(π)g(K(π));  (129)

the summation does not run over all of NC(n) but only over

NC′(n) := {π ∈ NC(n) | (1) is a block of π}.  (130)

This relation comes from the fact that if we fix the first block of π, then the remaining blocks are all separated from each other, but each one of them has to be considered in connection with one point of the first block.

The relation (128) alone does not help very much, since it involves also the new quantitiy fˇ⋆g. In order to proceed further we need one more relation. This is given by the following symmetrization lemma (in contrast to ⋆ the operation ˇ⋆ is not commutative)

z · Φ_{f⋆g}(z) = Φ_{fˇ⋆g}(z) · Φ_{gˇ⋆f}(z),  (131)

which just encodes a nice bijection between

NC(n)  ⟷  ⋃_{1≤j≤n} NC′(j) × NC′(n + 1 − j). (132)

The two relations (128) and (131) are all we need, the rest is just playing around with formal power series: (128) implies

Φ_{f}^{<−1>} = Φ_{fˇ⋆g} ∘ Φ_{f⋆g}^{<−1>}  (133)
Φ_{g}^{<−1>} = Φ_{gˇ⋆f} ∘ Φ_{g⋆f}^{<−1>},  (134)

where in the last expression we can replace g ⋆ f by f ⋆ g. Putting now z = Φ_{f⋆g}^{<−1>}(w) in (131) we obtain

Φ_{f⋆g}^{<−1>}(w) · w = Φ_{fˇ⋆g}(Φ_{f⋆g}^{<−1>}(w)) · Φ_{gˇ⋆f}(Φ_{f⋆g}^{<−1>}(w)). (135)

If we replace the quantities on the right hand side according to (133),

(134) and divide by w^{2} we end up with

\frac{Φ_{f⋆g}^{<−1>}(w)}{w} = \frac{Φ_{f}^{<−1>}(w)}{w} · \frac{Φ_{g}^{<−1>}(w)}{w}.  (136)

Since, by definition, the Fourier transform is nothing but

F(f)(w) = \frac{Φ_{f}^{<−1>}(w)}{w},  (137)

this yields exactly the assertion.

Biane [3] related the above theorem to the concept of central multiplicative functions on the infinite symmetric group and gave another proof of the theorem in that context.

7.5. Connection between S-transform and Fourier transform. According to Sect. 7.3, the problem of the general structure of the combinatorial convolution is essentially the same as the problem of multiplicative free convolution. So the above theorem should also be connected with the crucial property (98) of the S-transform. Let me point out this connection and show that everything fits together nicely.

If we denote by k(μ) the cumulant function of the distribution μ (i.e. the multiplicative function on non-crossing partitions determined by the free cumulants of μ), then I have shown, in Sect. 7.3, that the connection between probability and combinatorics is given by

k(μ ⊠ ν) = k(μ) ⋆ k(ν).  (138)

If one compares the definition of the S-transform and of the Fourier transform F and takes into account the relation which exists between moments and cumulants then one sees that the definitions are made in such a way that we have the relation

S_{μ} = F(k(μ)).  (139)

It is then clear that our theorem on the description of ⋆ via the Fourier transform together with the two equations (138) and (139) yields directly the behaviour of the S-transform under multiplicative free convolution:

\begin{aligned}S_{μ⊠ν} & = F(k(μ ⊠ ν)) \\ & = F(k(μ) ⋆ k(ν)) \\ & = F(k(μ)) · F(k(ν)) \\ & = S_{μ} · S_{ν}. \end{aligned}  (140)

Thus we get a purely combinatorial proof of Voiculescu’s theorem on the S-transform. Furthermore, our approach reveals a much closer relationship between additive and multiplicative free convolution than one would expect at a first look.

Let me close this section by emphasizing again that these considerations on the multiplicative free convolution possess no classical counterpart; combinatorially all this relies on the existence of the Kreweras complementation map for non-crossing partitions – some extra structure which is absent in the case of all partitions. Freeness and non-crossing partitions behave in many respects analogous to independence and all partitions, respectively, but in the free case there exists also some extra structure which makes this theory even richer than the classical one.

8. Applications of the combinatorial description of freeness

Up to now I have essentially shown how one can use freeness as a motivation for developing a lot of nice mathematics on non-crossing partitions. Note that the combinatorial problems are canonical for themselves – I hope you find them interesting even without taking into account the connection with free probability.

But of course this relation between freeness and non-crossing partitions can also be reversed; we can use the combinatorial description of freeness to derive some new results in free probability theory (up to now I have only shown how to rederive some known results of Voiculescu). This programme was pursued in a couple of joint papers with A. Nica [11, 12, 13]. For illustration, I want to present some of these results.

8.1. Construction of free random variables. One class of results are those were one starts with some variables that are free and constructs out of them new variables; then one asks whether one can say something about the freeness of the new variables. It is quite astonishing that there are a lot of constructions which preserve freeness – usually constructions which have no classical counterpart. In a sense freeness is much more rigid than classical independence – on a combinatorial level this corresponds to the fact that there exist a lot of special bijections between non-crossing partitions.

Let me just state one theorem of that type. It involves a so-called semi-circular distribution; this is the free analogue of the classical Gauss distribution and a semi-circular variable can be characterized by the fact that only its second free cumulant is different from zero.

Theorem (Nica+Speicher [11]). Let a and b be random variables which are free. If b is semi-circular, then a and bab are also free.

The proof of this theorem relies mainly on the fact that there exists a canonical bijection between NC(n) and the set

NCP (2n) := {π ∈ NC(2n) | each block of π contains exactly two elements}. (141)

8.2. Unexpected results. Surprises are to be expected from investigations which involve the Kreweras complementation map – since there is no classical analogy it might happen that one can derive properties which are totally opposite to what one knows from the classical case. One striking example of that kind is the following theorem, whose proof can be finally traced back to the property

|π| + |K(π)| = n + 1 for all π ∈ NC(n).  (142)

Theorem (Nica+Speicher [11]). Let μ be a (compactly supported) probability measure on ℝ. Then there exists, for each α ≥ 1, a probability measure μ^{⊞α} such that

μ^{⊞1} = μ  (143)

and

μ^{⊞α} ⊞ μ^{⊞β} = μ^{⊞(α+β)}  for all α, β ≥ 1.  (144)

Note that here positivity is the main assertion, it is crucial that we require the fractional powers to be probability measures. The corresponding statement on the level of linear functionals would be trivially true for arbitrary α.

To get an idea of the assertion consider the following example: If μ is a probability measure then we claim that there exists another probability measure ν = μ^{⊞3/2} such that

ν ⊞ ν = μ ⊞ μ ⊞ μ.  (145)

The analogous statement for classical convolution is of course totally wrong, as one can see, e.g., from the above example by taking μ to be the symmetric Bernoulli distribution with mass on +1 and −1.

8.3. Free commutator. An important advantage of our combinatorial description over the original analytical approach of Voiculescu is the possibility to extend the combinatorial treatment without any extra effort from the one-dimensional to the more-dimensional case. This opens the possibility to attack problems which are not treatable from the analytic side. The most considerable result of that kind is our analysis of the free commutator in [13]. Voiculescu solved the problem of the sum X + Y and the product XY of two free random variables X and Y. The next canonical problem, the free commutator XY − Y X, could be treated, for the first time, by our combinatorial machinery – the description of the commutator relies heavily on an understanding of the two-dimensional distribution of the pair (XY, Y X).

8.4. Generalization to the case with amalgamation. I want to indicate that one can generalize free probability theory also to an operator-valued frame; linear functionals are replaced by conditional expectations onto some fixed algebra B and all appearing algebras are with amalgamation over this B. Again, the combinatorial point of view using non-crossing partitions gives a natural and beautiful description for this theory. This approach was developed in [21].

9. Relations between freeness and other fields

Up to now I have concentrated on presenting the connection between free probability theory and non-crossing partitions. In a sense, freeness can be regarded as an abstract concept which is more or less equivalent to the combinatorics of non-crossing partitions. The most exciting feature of freeness, however, is that this is only one facet, there exist much more connections to various fields. Freeness is an abstract concept with a lot of concrete manifestations in quite different contextes.

In the following I want to give a slight idea of some of these connections. Whereas my presentation of the combinatorial part has covered most of the essential aspects, the following remarks will be very brief and selective. (In particular, I will say nothing about ‘free entropy’ – at present one of the most exciting directions in free probability theory .) For a more exhaustive survey I suggest to consult [30, 28, 29]. In particular, [29] contains a collection of articles on quite different aspects of freeness.

9.1. Origin of freeness: the free group factors. Voiculescu introduced ‘freeness’ in a context which is quite different from the topics I have treated up to now: namely in the theory of operator algebras, in connection with some old problems on special von Neumann algebras.

Let me give a very brief idea of that context. To a discrete group G one can associate in a canoncial way a von Neumann algebra L(G), which is the closure in some topology of the group ring of G: On the Hilbert space

l_{2}(G) := {∑_{g∈G} α_{g}g | ∑_{g} |α_{g}|^{2} < ∞}  (146)

with the scalar product

⟨g_{1}, g_{2}⟩ := δ_{g_{1},g_{2}}  (147)

one has a natural unitary representation λ of the group G, which is given by left multiplication, i.e.

λ(g)h = gh.  (148)

The von Neumann algebra L(G) associated to G is by definition the closure in the weak topology of the group ring ℂ(G) in this representation:

L(G) := \overline{λ(ℂ(G))}^{weak} = vN(λ(g) | g ∈ G) ⊂ B(l_{2}(G)). (149)

If the considered group is i.c.c. (i.e. all its non-trivial conjugacy classes contain infinitely many elements) then the von Neumann algebra L(G) is a so-called factor; factors are in a sense the simplest building blocks of general von Neumann algebras. Furthermore, there exists a canonical trace on L(G), which is given by the identity element e of G: define

φ(·) := ⟨e, ·e⟩,  i.e. φ(∑_{g} α_{g}g) = α_{e},  (150)

then it is easy to check that φ is a trace, i.e. it fulfills

φ(ab) = φ(ba) for all a, b ∈ L(G).  (151)

Factors having such a trace are called II_{1}-factors – they are the simplest class of non-trivial von Neumann algebras. (Trivial are the von Neumann algebras B(H) for some Hilbert space H; and there exist also type III factors, which possess no trace and which are much harder to analyze.)

Almost all known constructions of von Neumann algebras rely on the above construction of group factors and one has to face the following canonical question: What is the structure of L(G) for different G, in particular, how much of the structure of G survives within L(G).

For some classes of groups this is quite well understood. If the group G is amenable, then one gets always the same factor, the so-called hyperfinite factor R,

L(G) = R for all amenable groups G.  (152)

This hyperfinite II_{1}-factor (and its type III counterparts) has a lot of nice properties and the class of hyperfinite factors is regarded as the nicest class of von Neumann algebras.

On the other extreme there is a treatable class of groups which are considered as the bad guys: if G has the so-called Kazhdan property then L(G) has some exotic properties (usually used for constructing counter-examples); but for this class there is some evidence (i.e. it is an open conjecture) that the von Neumann algebra contains the full information on the group, i.e.

L(G_{1}) ≅ L(G_{2}) ⟺ G_{1} ≅ G_{2} G_{1}, G_{2} Kazhdan groups. (153)

There is a canonical class of groups lying between amenable and Kazhdan groups: the free groups F_{n} on n generators. Voiculescu advocates the philosophy that the free group factors L(F_{n}) are the nicest class of von Neumann algebras after the hyperfinite case. However, since the early days of Murray-von Neumann there has been no progress on this class – only the most basic things are know, like that they are different from the hyperfinite factor. But even the most canonical question, namely whether L(F_{n}) is isomorphic to L(F_{m}) for n ≠ m, is still open.

Voiculescu introduced the notion of ‘freeness’ exactly in order to investigate the structure of the free group factors. His idea was the following: The free group F_{n} is the free product (of groups)

F_{n} = ℤ ∗ ⋯ ∗ ℤ,  (154)

thus one might expect that the corresponding free group factor can also be decomposed as a free product (of von Neumann algebras) like

L(F_{n}) = L(ℤ) ∗ ⋯ ∗ L(ℤ).  (155)

L(ℤ) are commutative von Neumann algebras, thus well-understood; the main problem consists in understanding the operation of taking the free product of von Neumann algebras. But this amounts to understanding freeness: It is easy to see that with respect to the canonical trace in L(F_{n}) the different copies of L(ℤ) are free in L(F_{n}). The first main step of Voiculescu was to separate freeness as an abstract concept from that concrete problem and to develop it as a theory on its own sake. The second main point was to consider freeness as a non-commutative analogue of independence and thus to develop a free probability theory.

One should emphasize that for a couple of years there was no real progress on the problem of free group factors, it was absolutey unclear whether this approach via free probability theory would in the end yield something for the original operator algebraic problem. But slowly connections between freeness and other fields emerged and these really had a big impact on the operator algebraic side: Although the problem of the isomorhpism of the free group factors is still open, there has been a lot of progress on the structure of these algebras. Let me just mention as one result in this direction the following (according to Dykema [5] and Radulescu [15], building on results of Voiculescu): Either all L(F_{n}) are isomorhpic or all of them are different. (One can even extend the definition of L(F_{n}) in a consistent way to non-integer n.)

This progress on the original problem relied essentially on the discovery of Voiculescu [27] that freeness has also a canonical realization in terms of random matrices.

9.2. Freeness and random matrices. Probably the most important link of freeness with another, apriori totally unrelated, context is the connection with random matrices. Let me just state the basic version of this theorem

Theorem (Voiculescu [27], cf. [22]). 1) Let

X^{(N)} = (a_{ij}^{(N)})_{i,j=1}^{N}  and  Y^{(N)} = (b_{ij}^{(N)})_{i,j=1}^{N}  (156)

be symmetric N × N-random matrices with

i) a_{ij}^{(N)} (1 ≤ i ≤ j ≤ N) are independent and normally distributed (mean zero, variance 1/N) ii) b_{ij}^{(N)} (1 ≤ i ≤ j ≤ N) are independent and normally distributed (mean zero, variance 1/N) iii) all a_{ij}^{(N)} are independent from all b_{kl}^{(N)} Then X^{(N)} and Y^{(N)} become free in the limit N → ∞ with respect to

φ(·) := \frac{1}{N} ⟨tr(·)⟩_{ensemble}.  (157)

2) Let A^{(N)} and B^{(N)} be symmetric deterministic (e.g. diagonal) N × N-matrices whose eigenvalue distribtutions tend to some fixed probability measures μ and ν, respectively, in the limit N → ∞. Consider now

X^{(N)} := A^{(N)}  and  Y^{(N)} := UB^{(N)}U^{∗},  (158)

where U is a random unitary N × N-matrix from the ensemble

U ∈ Ω_{N} = (U(N), Haar measure).  (159)

Then X^{(N)} and Y^{(N)} become free in the limit N → ∞ with respect to

φ(·) := \frac{1}{N} ⟨tr(·)⟩_{Ω_{N}} .  (160)

Note that part 2 of this theorem is much more general than part 1. In the first part, X^{(N)} and Y^{(N)} are Gaussian random matrices and thus, by a celebrated result of Wigner, their eigenvalue distributions tend, for N → ∞, towards the so-called semi-circle distribution. We can also say that (in the sense of convergence of all moments)

lim_{N→∞}(X^{(N)}, Y^{(N)}) = (X, Y),  (161)

where X and Y are free and both have a semi-circular distribution (cf. Sect. 8.1).

In part 2 of the theorem, however, we are not restricted to semicircular distributions, but we can prescribe in the limit any distribution we want. In this case we can rephrase the statement in the form

lim_{N→∞}(X^{(N)}, Y^{(N)}) = (X, Y),  (162)

where X and Y are free and have the prescribed distributions

μ_{X} = μ and μ_{Y} = ν.  (163)

As a conclusion one can say that ‘freeness’ can also be considered as the mathematical structure of N × N-random matrices which survives in the limit N → ∞, or that ‘freeness’ is the right concept for the description of ∞ × ∞-random matrices.

As mentioned before, this connection resulted in some deep results on the von Neumann algebras of the free groups. But it opens also the possibility for using the concept ‘freeness’ in physical applications. Random matrices are quite frequently introduced in physics, usually in connection with some approximations. In such a context, the concept ‘freeness’ promises to give a mathematical rigorous frame for otherwise ad hoc approximations.

One example for such results is my joint work with P. Neu, where we could show that a physically well-established approximation – called CPA – consists in replacing independent by free random variables in the underlying Hamiltonian. This did not only clarify the mathematical structure of this approximation but explained also the hitherto badly understood connection between CPA and so-called Wegner models. For more information in this direction one might consult my survey [23].

References

1. H.W. Becker, Planar rhyme schemes, Bull. Amer. Math. Soc. 58 (1952), 39.

2. P. Biane, Some properties of crossings and partitions, to appear in Discrete Math.

3. P. Biane, Minimal factorizations of a cycle and central multiplicative functions on the infinite symmetric group, J. Combin. Th. A 76 (1996), 197–212.

4. P. Doubilet, G.-C. Rota, and R. Stanley, On the foundations of combinatorial theory VI: The idea of generating function, Proceedings of the Sixth Berkely Symposium on Mathematical Statistics and Probability, Lucien M. Le Cam et al. (Ed.), University of California Press, 1972, pp. 267–318.

5. K. Dykema, Interpolated free group factors, Pac. J. Math. 163 (1994), 123–135.

6. P.H. Edelman, Chain enumeration and non-crossing partitions, Discrete Math. 31 (1980), 171–180.

7. P.H. Edelman, Multichains, non-crossing partitions and trees, Discrete Math. 40 (1982), 171–179.

8. G. Kreweras, Sur les partitions non-croisees d’un cycle, Discrete Math. 1 (1972), 333–350.

9. A. Nica, R-transforms of free joint distributions, and non-crossing partitions, J. Funct. Anal. 135 (1996), 271–296.

10. A. Nica and R. Speicher, A ”Fourier Transform” for Multiplicative Functions on Non-Crossing Partitions, Journal of Algebraic Combinatorics 6 (1997), 141– 160.

11. A. Nica and R. Speicher, On the multiplication of free n-tuples of noncommutative random variables (with an appendix by D. Voiculescu), Amer. J. Math. 118 (1996), 799–837.

12. A. Nica and R. Speicher, R-diagonal pairs—a common approach to Haar unitaries and circular elements, Free Probability Theory (D.-V. Voiculescu, ed.), AMS, 1997, pp. 149–188.

13. A. Nica and R. Speicher, Commutators of free random variables, to appear in Duke Math. J.; also available under

http://www.rzuser.uni-heidelberg.de/^{∼}L95

14. Y. Poupard, Etude et denombrement paralleles des partitions non croisees d’un cycle et des coupage d’un polygone convexe, Discrete Math. 2 (1972), 279–288.

15. F. Radulescu, Random matrices, amalgamated free products and subfactors of the von Neumann algebra of a free group, of noninteger index, Invent. math. 115 (1994), 347–389.

16. G.-C. Rota, On the foundations of combinatorial theory I: Theory of Möbius functions, Z. Wahrscheinlichkeitstheorie Verw. Geb. 2 (1964), 340–368.

17. A.N. Shiryayev, Probability (Grad. Texts Math., vol. 95), Springer, 1984.

18. R. Simion and D. Ullman, On the structure of the lattice of non-crossing partitions, Discrete Math. 98 (1991), 193–206.

19. R. Speicher, A new example of ‘independence’ and ‘white noise’, Probab. Theory Rel. Fields 84 (1990), 141–159.

20. R. Speicher, Multiplicative functions on the lattice of non-crossing partitions and free convolution, Math. Ann. 298 (1994), 611–628.

21. R. Speicher, Combinatorial theory of the free product with amalgamation and operator-valued free probability theory (Habilitationsschrift), to appear as Memoir of the AMS; also available under

http://www.rzuser.uni-heidelberg.de/^{∼}L95

22. R. Speicher, Free Convolution and the Random Sum of Matrices, Publ. RIMS 29 (1993), 731–744.

23. R. Speicher, Physical applications of freeness, to appear in the Proceedings of the International Congress on Mathematical Physics, Brisbane, 1997; also available under

http://www.rzuser.uni-heidelberg.de/^{∼}L95

24. D. Voiculescu, Symmetries of some reduced free product C^{∗}-algebras, Operator Algebras and Their Connection with Topology and Ergodic Theory (Lecture Notes in Mathematics 1132), Springer, 1985, pp. 556–588.

25. D. Voiculescu, Addition of certain non-commuting random variables, J. Funct. Anal. 66 (1986), 323–346.

26. D. Voiculescu, Multiplication of certain non-commuting random variables, J. Operator Theory 18 (1987), 223–235.

27. D. Voiculescu, Limit laws for random matrices and free products, Invent. math. 104 (1991), 201–220.

28. D. Voiculescu, Free probability theory: random matrices and von Neumann algebras Proceedings of the ICM 1994, Birkhäuser, 1995, pp. 227–241.

29. D. Voiculescu (ed.), Free Probability Theory (Fields Institute Communications, vol. 12), AMS, 1997

30. D.V. Voiculescu, K.J. Dykema, and A. Nica, Free Random Variables (CRM Monograph Series, vol. 1), AMS, 1993.

Institut für Angewandte Mathematik, Im Neuenheimer Feld 294, D-69120 Heidelberg, Germany

E-mail address: roland.speicher@urz.uni-heidelberg.de