\documentstyle[12pt,amssymb]{amsart}
\newtheorem{thm}{Theorem} \renewcommand{\thethm}{}
\newtheorem{prop}{Proposition} \renewcommand{\theprop}{}
\newtheorem{cor}{Corollary} \renewcommand{\thecor}{}
\theoremstyle{definition}
\newtheorem{defs}{Definition} \renewcommand{\thedefs}{}
\def\EE{\text{{\bf E}}}
\def\tr{\text{{\bf tr}}}
\def\rb{\rbrack}
\def\lb{\lbrack}
\def\id{\text{id}}
\def\cA{{\cal A}}
\def\cB{{\cal B}}
\def\cF{{\cal F}}
\def\cP{{\cal P}}
\def\HH{{\cal H}}
\def\CC{{\Bbb C}}
\def\NN{{\Bbb N}}
\def\RR{{\Bbb R}}
\def\ZZ{{\Bbb Z}}
\def\ff{\varphi}
\def\bplus{\boxplus}
\def\btimes{\boxtimes}
\def\reli{\leftrightsquigarrow}
\def\chstar{\check\star}
\begin{document}
\phantom{.}
\vspace*{-2.5cm}
\hspace*{-.3cm}{\sc S\'eminaire Lotharingien de Combinatoire, B39c(1997), 38pp.}
\vspace*{2cm}
\title{Free Probability Theory and Non-Crossing Partitions}
\author[Roland Speicher]{Roland Speicher $^*$}
\address{Institut f\"ur Angewandte Mathematik, Im
Neuenheimer Feld 294, D-69120 Heidelberg, Germany}
\email{roland.speicher@@urz.uni-heidelberg.de}
\thanks{$^*$ supported by a Heisenberg fellowship of the DFG}
\thanks{I want to thank the organizers of the
39e S\'eminaire Lotharingien de Combinatoire for
the opportunity to give this talk}
\begin{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.
\end{abstract}
\maketitle
\section{{\bf Introduction}}
The notion of \lq 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 \lq 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.
\section{{\bf 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
$\ff$ which is given by integration with respect to the given
probability measure $P$, i.e. we have
\begin{equation}
\ff\lb f(X,Y)\rb=\int f(X(\omega),Y(\omega))dP(\omega)
\end{equation}
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 $\ff\lb X^{n_1}Y^{m_1}X^{n_2}Y^{m_2}\dots\rb$
for all $n_i,m_i\geq 0$ --
out of the moments of
$X$ -- i.e. $\ff\lb X^n\rb$ for all $n$ -- and the moments of $Y$ --
i.e. $\ff\lb Y^n\rb$ for all $n$. Namely, independence of $X$ and $Y$ just
means:
\begin{equation}
\ff\lb X^{n_1}Y^{m_1}\dots X^{n_k}Y^{m_k}\rb=\ff\lb
X^{n_1+\dots+n_k}\rb\cdot
\ff\lb Y^{m_1+\dots+m_k}\rb.
\end{equation}
For example, if $X$ and $Y$ are independent we have
\begin{equation}
\ff\lb XY\rb=\ff\lb X\rb \ff\lb Y\rb
\end{equation}
and
\begin{equation}
\ff\lb XXYY\rb=\ff\lb XYXY\rb=\ff\lb XX\rb\ff\lb YY\rb.
\end{equation}
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 $\cA$ (in general non-commutative) equipped with
a unital linear functional $\ff:\cA\to\CC$, $\ff(1)=1$. (For a lot
of questions it is important that the free theory is consistent if
our $\ff$'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
$\cA$ and we define freeness for such random variables as follows.
\begin{defs}
The non-commutative random variables $X,Y\in\cA$ are called {\it free}
(with respect of $\ff$), if
\begin{equation}
\ff\lb p_1(X)q_1(Y)p_2(X)q_2(Y)\dots\rb=0
\end{equation}
(finitely many factors),
whenever the $p_i$ and the $q_j$ are polynomials such that
\begin{equation}
\ff\lb p_i(X)\rb=0=\ff\lb q_j(Y)\rb
\end{equation}
for all $i,j$.
\end{defs}
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 $\ff\lb XY\rb$. Our above definition
tells us immediately that
\begin{equation}\ff\lb XY\rb=0\qquad\text{if $\ff\lb X\rb=0=\ff\lb Y\rb$.}
\end{equation}
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-\ff\lb X\rb 1$ and $q(Y)=Y-\ff\lb Y\rb1$ and our
definition of freeness yields
\begin{equation} \begin{split}
0=\ff\lb p(X)q(Y)\rb&=\ff\lb(X-\ff\lb X\rb 1)(Y-\ff\lb Y\rb 1)\rb\\
&=\ff\lb XY\rb-\ff\lb X\rb \ff\lb Y\rb,
\end{split} \end{equation}
which implies that we have in general
\begin{equation}
\ff\lb XY\rb=\ff\lb X\rb \ff\lb Y\rb.
\end{equation}
In the same way one can deal with more complicated mixed moments.
E.g. by looking at
\begin{equation}
\ff\lb (X^2-\ff\lb X^2\rb 1)(Y^2-\ff\lb Y^2\rb 1)\rb=0 \end{equation}
we get
\begin{equation}
\ff\lb XXYY\rb=\ff\lb XX\rb\ff\lb YY\rb. \label{A}
\end{equation}
Up to now there is no difference to the results for independent random
variables.
But consider next the mixed moment $\ff\lb XYXY\rb$. Again we can calculate
this moment by using
\begin{equation}
\ff\lb(X-\ff\lb X\rb 1)(Y-\ff\lb Y\rb
1)(X-\ff\lb X\rb 1)(Y-\ff\lb Y\rb 1)\rb=0.
\end{equation}
Resolving this for $\ff\lb XYXY\rb$ (and using induction for the other
appearing mixed moments, which are of smaller order) we obtain
\begin{multline}
\ff\lb XYXY\rb=\ff\lb XX\rb \ff\lb Y\rb \ff\lb Y\rb\\
+\ff\lb X\rb \ff\lb X\rb \ff\lb YY\rb
-\ff\lb X\rb \ff\lb Y\rb \ff\lb X\rb\ff\lb Y\rb. \label{B}
\end{multline}
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
$\ff\lb XXYY\rb$ must be the same as $\ff\lb XYXY\rb$, which gives, by
comparision between
(\ref{A}) and (\ref{B}) 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).
\section{{\bf Additive free convolution}}
Let us state again the problem: We are given $X$ and $Y$, i.e. we
know their moments $\ff\lb X^n\rb$ and $\ff\lb Y^n\rb$
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 $\ff\lb (X+Y)^n\rb$. 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 self-adjoint 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 $\mu_X$
of $X$ which is
a probability measure on $\RR$ whose moments are just the moments of $X$, i.e.
\begin{equation}
\ff\lb X^n\rb=\int t^nd\mu_X(t).
\end{equation}
Let us first take a look at the classical situation before we deal
with the free counterpart.
\subsection{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
$\mu_{X+Y}$ of $X+Y$ can be calculated
somehow out of the distribution $\mu_X$ of $X$ and the distribution
$\mu_Y$ of $Y$. Of course, this \lq somehow' is nothing else than the
convolution of probability measures,
\begin{equation}
\mu_{X+Y}=\mu_X*\mu_Y,
\end{equation}
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 $\mu$ or to each random variable $X$ with
distribution $\mu$ (i.e. $\mu_X=\mu$) we assign a function $\cF_{\mu}$
on $\RR$ given by
\begin{equation}
\cF_{\mu}(t):=\int e^{itx}d\mu(x)=\ff\lb e^{itX}\rb.
\end{equation}
From our combinatorial point of view it is the best to view $\cF_{\mu}$
just as a formal power series in the indeterminate $t$. If we
expand
\begin{equation}
\cF_{\mu}(t)=\sum_{n=0}^\infty \frac{(it)^n}{n!}\ff\lb X^n\rb
\end{equation}
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
\begin{equation}
\cF_{\mu*\nu}(t)=\cF_{\mu}(t)\cdot\cF_{\nu}(t).
\end{equation}
If we take the logarithm of this equation then we get
\begin{equation}
\log\cF_{\mu*\nu}(t)=\log\cF_{\mu}(t)+\log\cF_{\nu}(t),
\end{equation}
i.e. the logarithm of the Fourier transform linearizes the classical
convolution.
\subsection{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
$\mu_{X+Y}$ of
$X+Y$ depends somehow on the distribution $\mu_X$
of $X$ and the distribution $\mu_Y$
of $Y$. Following Voiculescu \cite{V2},
we denote this \lq somehow' by $\boxplus$,
\begin{equation}
\mu_{X+Y}=\mu_X\boxplus\mu_Y,
\end{equation}
and call this operation {\it (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 $\bplus$.
This question was solved by Voiculescu
\cite{V2} in the affirmative: He provided
an analogue of the logarithm of the Fourier transform which he called
$R$-transform. Thus, to each probability measure $\mu$ he assigned an
$R$-transform $R_\mu(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.
\begin{equation}
R_{\mu\boxplus\nu}(z)=R_\mu(z)+R_\nu(z).
\end{equation}
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_\mu$ which is defined by
\begin{equation}
G_\mu(z)=\int\frac 1{z-x}d\mu(x)=\ff\lb \frac 1{z-X}\rb.
\end{equation}
This Cauchy-transform determines the $R$-transform uniquely by the
prescription that $G_\mu(z)$ and $R_\mu(z)+1/z$ are inverses of each other
with respect to composition:
\begin{equation}
G_\mu\lb R_\mu(z)+1/z\rb=z.
\end{equation}
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 $\boxplus$ becomes much more similar (and, indeed, we can
understand the above formulas as translations of combinatorial
identities into generating power series).
\subsection{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 Fourier-transform 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
{\it cumulants} of the distribution. In analogy we will call
the coefficients of the $R$-transform the {\it free cumulants}. The
fact that $\log\cF$ 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
\begin{equation}
m_1=c_1
\end{equation}
and
\begin{equation}
m_2=c_2+c_1^2
\end{equation}
(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,\dots,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.
\section{{\bf 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 \cite{R,DRS}.
Let me briefly recall these well-known notions.
\subsection{Lattice of all partitions and their incidence algebra}
Let $n$ be a natural number. A {\it partition} $\pi=
\{V_1,\dots,V_k\}$ of the set
$\{1,\dots,n\}$ is a decomposition of $\{1,\dots,n\}$ into disjoint
and non-empty sets $V_i$, i.e. $V_i\not=\emptyset$, $V_i\cap V_j=
\emptyset$ ($i\not=j$) and $\bigcup_{i=1}^k V_i=\{1,\dots,n\}$.
The elements $V_i$ are called the {\it blocks} of the partition $\pi$.
We will denote the set of all partitions of $\{1,\dots,n\}$ by
$\cP(n)$. This set becomes a lattice if we introduce the following
partial order (called {\it refinement order}): $\pi\leq \sigma$ if
each block of $\sigma$ is a union of blocks of $\pi$. We will denote
the smallest and the biggest element of $\cP(n)$
-- consisting of $n$ blocks and one block, respectively -- by special symbols,
namely
\begin{equation}
0_n:=\{(1),(2),\dots,(n)\},\qquad 1_n:=\{(1,2,\dots,n)\}.
\end{equation}
An example for the refinement order is the following:
\begin{equation}\{(1,3),(2),(4)\}\leq \{(1,3),(2,4)\}.\end{equation}
Of course, there is no need to consider only partitions of the
sets $\{1,\dots,n\}$, the same definitions apply for arbitrary sets
$S$ and we have a natural isomorphism $\cP(S)\cong\cP(\vert S
\vert)$.
We consider now the collection of all partition lattices $\cP(n)$
for all $n$,
\begin{equation}
\cP:=\bigcup_{n\in\NN}\cP(n),
\end{equation}
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 {\it incidence algebra} consists of all functions
\begin{equation}
f:\bigcup_{n\in\NN}(\cP(n)\times\cP(n))\to\CC
\end{equation}
subject to the following condition:
\begin{equation}
f(\pi,\sigma)=0,\qquad\text{whenever $\pi\not\leq \sigma$}
\end{equation}
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.
\begin{equation}
f(\pi)=f(0_n,\pi)\qquad\text{for $\pi\in\cP(n)$.}
\end{equation}
On this incidence algebra we have a canonical
{\it (combinatorial) convolution} $\star$: For $f$ and $g$
functions as above, we define $f\star g$ by
\begin{equation}
(f\star g)(\pi,\sigma):=\sum
\Sb \tau \in \cP(n)\\ \pi\leq\tau\leq\sigma\endSb f(\pi,\tau)
g(\tau,\sigma)\qquad\text{for $\pi\leq\sigma\in\cP(n).$}
\end{equation}
One should note that apriori this combinatorial convolution $\star$ 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 $\delta$ for the
combinatorial convolution is given by
\begin{equation}
\delta(\pi,\sigma)=\begin{cases}
1,&\pi=\sigma\\
0,&\text{otherwise.}
\end{cases}
\end{equation}
The {\it zeta function} is defined by
\begin{equation}
Zeta(\pi,\sigma)=\begin{cases}
1,& \pi\leq \sigma\\
0,&\text{otherwise.}
\end{cases}
\end{equation}
It is an easy exercise to check that the zeta function possesses an
inverse; this is called the {\it M\"obius function} of our
lattice:
$Moeb$ is defined by
\begin{equation}
Moeb\star Zeta=Zeta\star Moeb=\delta.
\end{equation}
\subsection{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 $\cP(n)$ for different
$n$ -- this subclass consists of the so-called
multiplicative functions.
Our functions $f$ of the incidence algebra have two arguments --
$f(\pi,\sigma)$ -- but since non-trivial things
only happen for $\pi\leq\sigma$ we can also
think of $f$ as a function of the intervals in $\cP$, i.e. of the sets
$\lb \pi,\sigma\rb:=\{\tau\in\cP(n)
\mid \pi\leq\tau\leq\sigma\}$ for $\pi,\sigma
\in\cP(n)$ ($n\in\NN$) and $\pi\leq\sigma$.
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 $\pi,\sigma\in\cP(n)$ with $\pi\leq\sigma$ there
are canonical natural numbers $k_1,k_2,\dots$ such that
\begin{equation}
\lb\pi,\sigma\rb\cong \cP(1)^{k_1}\times \cP(2)^{k_2}\times\cdots.
\end{equation}
(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,\dots)$ of complex numbers we define
the corresponding {\it multiplicative function} $f$
(we denote the dependence of $f$ on this sequence by $f\reli (a_1,a_2,\dots)$)
by the
requirement
\begin{equation}
f(\pi,\sigma):=a_1^{k_1}a_2^{k_2}\dots\qquad\text{if}\qquad
\lb\pi,\sigma\rb\cong \cP(1)^{k_1}\times \cP(2)^{k_2}\times\cdots.
\end{equation}
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{equation} \begin{split}
\lb \{(1,3),(2),(4)\},\{(1,2,3,4)\}\rb&\cong
\lb\{(1),(2),(4)\},\{(1,2,4)\}\rb\\&\cong\cP(3),
\end{split} \end{equation}
thus
\begin{equation}
f(\{(1,3),(2),(4)\},\{(1,2,3,4)\})=a_3.
\end{equation}
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
\begin{multline}
\lb\{(1),(2),(3),(4),(5),(6),(7),(8)\},\{(1,3,5),(2,4),(6),(7,8)\}\rb
\cong\\ \lb\{(1),(3),(5)\},\{(1,3,5)
\}\rb\times\lb \{(2),(4)\},\{(2,4)\}\rb\times\\
\times \lb\{(6)\},\{(6)\}\rb\times \lb\{(7),(8)\},\{(7,8)\}\rb,
\end{multline}
and hence for the multiplicative function of one argument
\begin{multline}
f(\{(1,3,5),(2,4),(6),(7,8)\})=\\ f(\{(1,3,5)\}) \cdot f(\{(2,4)\})
\cdot
f(\{(6)\}) \cdot f(\{(7,8)\})=a_3a_2a_1a_2.
\end{multline}
The special functions $\delta$, $Zeta$, and $Moeb$ are all
multiplicative with determining sequences as follows:
\begin{align}
\delta&\reli (1,0,0,\dots)\\
Zeta&\reli (1,1,1,\dots)\\
Moeb&\reli ((-1)^{n-1}(n-1)!)_{n\geq 1}
\end{align}
\subsection{Connection between probabilistic and combinatorial
convolution}
Recall our strategy for describing classical convolution combinatorially:
Out of the moments $m_n=\ff(X^n)$ ($n\geq 1$) of a random variable $X$ we want
to calculate some new quantities $c_n$ ($n\geq 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) \cite{R,Sh} that
the relation between these two multiplicative funtions
is just given by taking the combinatorial convolution with
the zeta function or with the M\"obius function.
\begin{thm}
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.
\begin{equation}
M\reli (m_1,m_2,\dots),\qquad C\reli (c_1,c_2,\dots).
\end{equation}
Then the relation between $M$ and $C$ is given by
\begin{equation}
M=C\star Zeta,
\end{equation}
or equivalently by
\begin{equation}
C=M\star Moeb.\end{equation}
\end{thm}
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
\begin{equation}
A(z):=1+\sum_{n=1}^\infty \frac{m_n}{n!}z^n,\qquad
B(z):=\sum_{n=1}^\infty \frac {c_n}{n!}z^n\end{equation}
the exponential power series of the moment and cumulant sequences,
respectively, then it is a well known fact
\cite{R} that the statement
of the above theorem translates in terms of these series into
\begin{equation}
A(z)=\exp B(z)\qquad\text{or} \qquad B(z)=\log A(z).
\end{equation}
But since the Fourier transform $\cF_{\mu}$ of the random variable $X$
(with $\mu=\mu_X$) is
connected with $A$ by
\begin{equation}
\cF_{\mu}(t)=A(it),
\end{equation}
this means that
\begin{equation}
B(it)=\log \cF_{\mu}(t),\end{equation}
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.
\section{{\bf Combinatorial aspects of free convolution}}
Now we switch from classical convolution to free convolution. Where\-as
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.
\subsection{Lattice of non-crossing partitions and their incidence algebra}
We call a partition $\pi\in \cP(n)$ {\it crossing} if there
exist four numbers $1\leq i},
\end{equation}
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 $\bplus$ and the multiplicative convolution $\btimes$,
and he could solve both of them by introducing the
$R$-transform and the $S$-transform, 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 $R$-transform.
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.
\subsection{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,
\begin{equation}
f\reli (a_1,a_2,\dots),\qquad g\reli (b_1,b_2,\dots),\end{equation}
their convolution
\begin{equation}
h:=f\star g\end{equation}
must, as a multiplicative function, also be determined by some
sequence of numbers
\begin{equation}
h\reli (c_1,c_2,\dots).\end{equation}
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\star zeta$, and the relation between
the two series $f$ and $h=f\star zeta$ is more or less Voiculescu's
formula for the $R$-transform:
If
\begin{equation}
f\reli (a_1,a_2,\dots)
\qquad\text{and}\qquad
h=f\star zeta\reli (c_1,c_2,\dots)
\end{equation}
then in terms of the generating power series
\begin{equation}
C(z):=1+\sum_{n=1}^\infty c_nz^n \qquad\text{and}\qquad
D(z):=1+\sum_{n=1}^\infty a_nz^n
\end{equation}
the relation is given by
\begin{equation}
C(z)=D\lb zC(z)\rb.\end{equation}
Now we ask for an analogue treatment of the general case
$h=f\star g$.
The corresponding problem for all partitions was
solved by Doubilet, Rota, and Stanley in \cite{DRS}:
The multiplicative functions on $\cP$ correspond to
exponential power series of their determining sequences and
under this correspondence the convolution $\star$ 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 $\cP$): all $NC(n)$ are self-dual
and there exists a nice mapping, the
{\it (Kreweras) complementation map}
\begin{equation}
K:NC(n)\to NC(n),\end{equation}
which implements this self-duality.
This complementation map is a lattice anti-isomorhism, i.e.
\begin{equation}
\pi\leq \sigma\Leftrightarrow K(\pi)\geq K(\sigma),
\end{equation}
and it is defined as follows:
If we have a partition $\pi\in NC(n)$ then we insert between
the points $1,2,\dots,n$ new points $\bar 1,\bar 2,\dots,\bar n$
(linearly or circularly), such that we have
$1,\bar 1,2,\bar 2,\dots,n,\bar n$. We draw now the partition
$\pi$ by connecting the blocks of $\pi$ and we define $K(\pi)$
as the biggest non-crossing partition of $\{\bar 1,\bar 2,\dots,
\bar n\}$ which does not have crossings with the partition
$\pi$: $K(\pi)$ is the maximal element of the set
$\{\sigma\in NC(\bar 1,\dots,\bar n)\mid \pi\cup\sigma
\in NC(1,\bar 1,\dots,n,\bar 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
\cite{K}. 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
\cite{SU} modified the
complementation map to make it involutive, but the
original map of Kreweras is more adequate for our
investigations. Biane \cite{Bia1} 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:
\begin{equation}
K(\{(1,4,8),(2,3),(5,6),(7)\})=\{(1,3),(2),(4,6,7),(5),(8)\}.
\end{equation}
\setlength{\unitlength}{0.5cm}
\begin{picture}(16,5)
\thicklines
\put(1,0){\line(0,1){4}}
\put(1,0){\line(1,0){14}}
\put(7,0){\line(0,1){4}}
\put(15,0){\line(0,1){4}}
\put(3,2){\line(0,1){2}}
\put(3,2){\line(1,0){2}}
\put(5,2){\line(0,1){2}}
\put(9,2){\line(0,1){2}}
\put(9,2){\line(1,0){2}}
\put(11,2){\line(0,1){2}}
\put(13,2){\line(0,1){2}}
\linethickness{0.6mm}
\put(2,1){\line(0,1){3}}
\put(2,1){\line(1,0){4}}
\put(6,1){\line(0,1){3}}
\put(4,3){\line(0,1){1}}
\put(8,1){\line(0,1){3}}
\put(8,1){\line(1,0){6}}
\put(12,1){\line(0,1){3}}
\put(14,1){\line(0,1){3}}
\put(10,3){\line(0,1){1}}
\put(16,1){\line(0,1){3}}
\put(0.8,4.5){1}
\put(1.8,4.5){$\bar 1$}
\put(2.8,4.5){2}
\put(3.8,4.5){$\bar 2$}
\put(4.8,4.5){3}
\put(5.8,4.5){$\bar 3$}
\put(6.8,4.5){4}
\put(7.8,4.5){$\bar 4$}
\put(8.8,4.5){5}
\put(9.8,4.5){$\bar 5$}
\put(10.8,4.5){6}
\put(11.8,4.5){$\bar 6$}
\put(12.8,4.5){7}
\put(13.8,4.5){$\bar 7$}
\put(14.8,4.5){8}
\put(15.8,4.5){$\bar 8$}
\end{picture}
\vskip1cm
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\star g$, and the sequence determining $h$ is denoted
by $(c_1,c_2,\dots)$, then we have by definition of our
convolution
\begin{equation}
c_n=h(0_n,1_n)=\sum_{\pi\in NC(n)} f(0_n,\pi)g(\pi,1_n),
\end{equation}
which looks quite unsymmetric in $f$ and $g$. But the
complementation map allows us to replace
\begin{equation}
\lb \pi,1_n\rb\cong \lb K(1_n),K(\pi)\rb=\lb 0_n,K(\pi)\rb
\end{equation}
and thus we obtain
\begin{equation}
c_n=\sum_{\pi\in NC(n)} f(0_n,\pi)g(0_n,K(\pi))=
\sum_{\pi\in NC(n)} f(\pi) g(K(\pi)). \label{V}
\end{equation}
An immediate corollary of that observation is the
commutativity of the combinatorial convolution on non-crossing
partitions.
\begin{cor}[Nica+Speicher \cite{NS1}]
The combinatorial convolution $\star$ on non-crossing
partitions is commutative:
\begin{equation}
f\star g=g\star f.\end{equation}
\end{cor}
\begin{pf}
\begin{equation}
\begin{split}
(f\star g)(0_n,1_n)&=\sum_{\pi\in NC(n)} f(\pi)g(K(\pi))\\
&=\sum_{\sigma=K^{-1}(\pi)}f(K(\sigma))g(\sigma)\\
&=(g\star f)( 0_n,1_n).
\end{split}
\end{equation}
\end{pf}
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.
\subsection{Connection between $\star$ and $\btimes$}
Before I am going on to present the solution to the problem of
describing the full structure of the combinatorial convolution
$\star$, 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
\begin{equation}
\ff\lb(XY)^n\rb=\sum_{\pi\in NC(2n)}
k(\pi)\lb X,Y,X,Y,\dots ,X,Y\rb,
\end{equation}
where $k(\pi)\lb X,Y,X,Y,\dots ,X,Y\rb$
denotes a product of cumulants which
factorizes according to the block structure of the
partition $\pi$. The vanishing of mixed cumulants
in free variables implies that only such partitions $\pi$
contribute where all blocks connect either only $X$ or only $Y$.
Such a $\pi\in NC(2n)$ splits into the union $\pi=
\pi_1\cup \pi_2$, where $\pi_1\in NC(1,3,5,\dots)$
(the positions of the $X$) and
$\pi_2\in NC(2,4,6,\dots)$ (the positions of the $Y$),
and we can continue the above equation with
\begin{equation} \begin{split}
&\ff\lb(XY)^n\rb=\\ &=
\sum\Sb \pi=\pi_1\cup \pi_2\in NC(2n)\\
\pi_1\in NC(1,3,5,\dots)\\
\pi_2\in NC(2,4,6,\dots)\endSb
k(\pi_1)\lb X,X,\dots ,X\rb \cdot k(\pi_2)\lb Y,Y,\dots ,Y\rb\\
&=\sum_{\pi_1\in NC(n)}\Bigl( k(\pi_1)\lb X,X,\dots ,X\rb\cdot
\sum\Sb \pi_2\in NC(n)\\ \pi_1\cup \pi_2\in NC(2n)\endSb k(\pi_2)
\lb Y,Y,\dots ,Y\rb\Bigr).
\end{split} \end{equation}
Now note that the condition
\begin{equation}
\pi_2\in NC(n)\qquad\text{with}\qquad \pi_1\cup \pi_2\in NC(2n)
\end{equation}
is equivalent to
\begin{equation}
\pi_2\leq K(\pi_1)\end{equation}
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\star zeta$ just means explicitely
\begin{equation}
m_Y(\sigma_1)=\sum_{\sigma_2\leq\sigma_1}k_Y(\sigma_2).
\end{equation}
Taking this into account we can continue our calculation of the
moments of $XY$ as follows:
\begin{equation} \begin{split}
\ff\lb(XY)^n\rb&=\sum_{\pi_1\in NC(n)}
\Bigl( k_X(\pi_1)
\cdot\sum_{\pi_2\leq K(\pi_1)} k_Y(\pi_2)\Bigr)\\
&=\sum_{\pi_1\in NC(n)}k_X(\pi_1)\cdot m_Y(K(\pi_1)).
\end{split} \end{equation}
According to our
formulation of the combinatorial convolution
in terms of the complementation map,
cf.~(\ref{V}), this is nothing but the
following relation
\begin{equation}
m_{XY}=k_X\star m_Y. \label{F}
\end{equation}
Hence we can express multiplicative free
convolution $\btimes$ in terms of the
combinatorial convolution $\star$. This becomes even more striking
if we remove the above unsymmetry in moments and cumulants.
By applying the M\"obius function on (\ref{F}) we end up with
\begin{equation}
k_{XY}=m_{XY}\star moeb=k_X\star m_Y\star moeb=k_X\star k_Y,
\end{equation}
and we have the beautiful result
\begin{equation}
k_{XY}=k_X\star k_Y\qquad\text{for $X$ and $Y$ free.}
\end{equation}
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 $\btimes$ is
equivalent to understanding the general structure of the
combinatorial convolution $h=f\star g$.
\subsection{Description of $\star$}
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\star g$.
This insight was the starting point of my joint work
\cite{NS1} with
A. Nica on the combinatorial convolution $\star$. 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.
\begin{thm}[Nica+Speicher \cite{NS1}]
For a multiplicative function $f$ on NC with
\begin{equation}
f\reli (a_1,a_2,\dots)\qquad\text{where}\qquad a_1=1
\end{equation}
we define its \lq Fourier transform' $\cF(f)$ by
\begin{equation}
\cF(f)(z):=\frac 1z\bigl(\sum_{n=1}^\infty a_nz^n\bigr)^{<-1>}.
\end{equation}
Then we have
\begin{equation}
\cF(f\star g)(z)=\cF(f)(z)\cdot \cF(g)(z).\end{equation}
\end{thm}
Hence multiplicative functions on $NC$ correspond to formal
power series (but now this correspondence $\cF$ is not as direct as in
the case of all partitions), and under this correspondence the
combinatorial convolution $\star$ is mapped onto multiplication of
power series. This is of course consistent with the commutativity
of $\star$.
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.
\begin{pf}
Let us denote for a multiplicative function $f$ determined
by a sequence $(a_1,a_2,\dots)$ its generating power series by
\begin{equation}
\Phi_f(z):=\sum_{n=1}^\infty a_nz^n.\end{equation}
Then we do the summation in
\begin{equation}
c_n=\sum_{\pi\in NC(n)} f(\pi)g(K(\pi))\end{equation}
in such a way that we fix the first block of $\pi$ and then
sum over the remaining possibilities. A careful look
reveals that this results in a relation
\begin{equation}
\Phi_{f\star g}=\Phi_f\circ \Phi_{f \check\star g},
\label{G}
\end{equation}
where $f\check\star g$ is defined by
\begin{equation}
(f\check\star g)(0_n,1_n):=\sum_{\pi\in NC'(n)} f(\pi)g(K(\pi));
\end{equation}
the summation does not run over all of $NC(n)$ but only
over
\begin{equation}
NC'(n):=\{\pi\in NC(n)\mid \text{$(1)$ is a block of $\pi$}\}.
\end{equation}
This relation comes from the fact that if we fix the first block of
$\pi$, 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
(\ref{G}) alone does not help very much, since it
involves also the new
quantitiy $f\chstar g$.
In order to proceed further
we need one more relation.
This is given by the following symmetrization lemma
(in contrast to $\star$ the operation $\chstar$ is not commutative)
\begin{equation}
z\cdot \Phi_{f\star g}(z)=\Phi_{f\chstar g}(z)\cdot
\Phi_{g\check\star f}(z), \label{H}
\end{equation}
which just encodes a nice bijection between
\begin{equation}
NC(n) \qquad\longleftrightarrow \qquad
\bigcup_{1\leq j\leq n} NC'(j)\times NC'(n+1-j).
\end{equation}
The two relations
(\ref{G}) and (\ref{H}) are all we need, the rest is just
playing around with formal power series: (\ref{G}) implies
\begin{align}
\Phi^{<-1>}_f&=\Phi_{f\chstar g}\circ \Phi^{<-1>}_{f\star g}
\label{I}\\
\Phi^{<-1>}_g&=\Phi_{g\chstar f}\circ \Phi^{<-1>}_{g\star f},
\label{J}
\end{align}
where in the last expression we can replace $g\star f$ by
$f\star g$.
Putting now $z=\Phi_{f\star g}^{<-1>}(w)$ in
(\ref{H}) we obtain
\begin{equation}
\Phi^{<-1>}_{f\star g}(w)\cdot w=
\Phi_{f\chstar g}\bigl(\Phi^{<-1>}_{f\star g}(w)\bigr)\cdot
\Phi_{g\chstar f}\bigl(\Phi^{<-1>}_{f\star g}(w)\bigr).
\end{equation}
If we replace the quantities on the right hand side according to
(\ref{I}), (\ref{J}) and divide by $w^2$ we end up with
\begin{equation}
\frac{\Phi^{<-1>}_{f\star g}(w)}w=
\frac{\Phi^{<-1>}_{f}(w)}w \cdot\frac{\Phi^{<-1>}_{g}(w)}w.
\end{equation}
Since, by definition, the Fourier transform is nothing but
\begin{equation}
\cF(f)(w)=\frac{\Phi^{<-1>}_{f}(w)}w,
\end{equation}
this yields exactly the assertion.
\end{pf}
Biane \cite{Bia2} 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.
\subsection{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
(\ref{K}) of the $S$-transform.
Let me point out this connection and show that everything
fits together nicely.
If we denote by $k(\mu)$ the cumulant function of the
distribution $\mu$ (i.e. the multiplicative function on non-crossing
partitions determined by the free cumulants of $\mu$), then I have
shown, in Sect.~7.3, that the connection between probability and
combinatorics is given by
\begin{equation}
k(\mu\btimes \nu)=k(\mu)\star k(\nu). \label{P}
\end{equation}
If one compares the definition of the $S$-transform and of the
Fourier transform $\cF$ 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
\begin{equation}
S_\mu=\cF(k(\mu)). \label{Q}
\end{equation}
It is then clear that our theorem on the description of $\star$
via the Fourier transform together with the two equations
(\ref{P})
and (\ref{Q}) yields
directly the behaviour of the $S$-transform under
multiplicative free convolution:
\begin{equation} \begin{split}
S_{\mu\btimes\nu}&=\cF\bigl(k(\mu\btimes\nu)\bigr)\\
&=\cF\bigl(k(\mu)\star k(\nu)\bigr)\\
&=\cF(k(\mu))\cdot\cF(k(\nu))\\
&=S_\mu\cdot S_\nu.
\end{split} \end{equation}
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.
\section{{\bf 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 \cite{NS2,NS3,NS4}.
For illustration, I want to present some of these results.
\subsection{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 {\it 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.
\begin{thm}[Nica+Speicher \cite{NS2}]
Let $a$ and $b$ be random variables which are free. If $b$
is semi-circular, then $a$ and $bab$ are also free.
\end{thm}
The proof of this theorem relies mainly on the fact that
there exists a canonical bijection between $NC(n)$ and the
set
\begin{multline}
NCP(2n):=\{\pi\in NC(2n)\mid\text{each block of $\pi$
contains} \\ \text{exactly two elements}\}.
\end{multline}
\subsection{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
\begin{equation}
\vert\pi\vert+\vert K(\pi)\vert=n+1\qquad\text{for all
$\pi\in NC(n)$.}
\end{equation}
\begin{thm}[Nica+Speicher \cite{NS2}]
Let $\mu$ be a (compactly supported) probability measure
on $\RR$. Then there exists, for each $\alpha\geq 1$, a
probability measure $\mu^{\bplus \alpha}$ such that
\begin{equation}
\mu^{\bplus 1}=\mu\end{equation}
and
\begin{equation}
\mu^{\bplus\alpha}\bplus\mu^{\bplus\beta}=
\mu^{\bplus(\alpha+\beta)}\qquad\text{for all $\alpha,\beta\geq
1$.}
\end{equation}
\end{thm}
Note that here positivity is the main assertion, it is crucial that
we require the fractional powers to be {\it probability measures}.
The corresponding statement on the level of linear functionals
would be trivially true for arbitrary $\alpha$.
To get an idea of the assertion consider the following example:
If $\mu$ is a probability measure then we claim that there
exists another probability measure $\nu=\mu^{\bplus 3/2}$
such that
\begin{equation}
\nu\bplus\nu=\mu\bplus\mu\bplus\mu.
\end{equation}
The analogous statement for classical convolution is of
course totally wrong, as one can see, e.g., from the above example
by taking $\mu$ to be the symmetric
Bernoulli distribution with mass on
$+1$ and $-1$.
\subsection{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
\cite{NS4}.
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-YX$, 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,YX$).
\subsection{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
$\cB$ and all appearing algebras are with amalgamation
over this $\cB$. Again, the combinatorial point of view using
non-crossing partitions gives a natural and beautiful description
for this theory. This approach was developed in \cite{Sp3}.
\section{{\bf 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 \lq free
entropy' -- at present one of the most
exciting directions in free probability theory .)
For
a more exhaustive survey I suggest to consult \cite{VDN,V5,V6}.
In particular, \cite{V6} contains a collection of articles
on quite different aspects of freeness.
\subsection{Origin of freeness: the free group factors}
Voiculescu introduced \lq 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
\begin{equation}
l_2(G):=\{\sum_{g\in G} \alpha_g g\mid \sum_g\vert \alpha_g
\vert^2<\infty\}
\end{equation}
with the scalar product
\begin{equation}
\langle g_1,g_2\rangle:=\delta_{g_1,g_2}
\end{equation}
one has a natural unitary representation $\lambda$ of the
group $G$, which is given by left multiplication, i.e.
\begin{equation}
\lambda(g)h=gh.
\end{equation}
The von Neumann algebra $L(G)$ associated to $G$ is by
definition the closure in the weak topology of the
group ring $\CC(G)$ in this representation:
\begin{equation}
L(G):=\overline{\lambda(\CC(G))}^{weak}=
vN(\lambda(g)\mid g\in G)\subset B(l_2(G)).
\end{equation}
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
\begin{equation}
\ff(\cdot):=\langle e,\cdot e\rangle,\qquad\text{i.e.}\qquad
\ff(\sum_g \alpha_g g)=\alpha_e,
\end{equation}
then it is easy to check that $\ff$ is a trace, i.e. it
fulfills
\begin{equation}
\ff(ab)=\ff(ba)\qquad\text{for all $a,b\in L(G)$.}
\end{equation}
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(\HH)$ for some
Hilbert space $\HH$; 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$,
\begin{equation}
L(G)=R\qquad\text{for all amenable groups $G$.}
\end{equation}
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.
\begin{equation}
L(G_1)\cong L(G_2)\Longleftrightarrow G_1\cong G_2
\qquad\text{$G_1,G_2$ Kazhdan groups}.
\end{equation}
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\not=m$, is still open.
Voiculescu introduced the notion of \lq 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)
\begin{equation}
F_n=\ZZ*\dots*\ZZ,
\end{equation}
thus one might expect that the corresponding free
group factor can also be decomposed as a free product
(of von Neumann algebras) like
\begin{equation}
L(F_n)=L(\ZZ)*\dots* L(\ZZ).
\end{equation}
$L(\ZZ)$ 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(\ZZ)$ 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 \cite{Dyk} and Radulescu \cite{Rad},
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
\cite{V4} that freeness has
also a canonical realization in terms of random matrices.
\subsection{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
\begin{thm}[Voiculescu \cite{V4}, cf.~\cite{Sp4}]
1) Let
\begin{equation}
X^{(N)}=(a_{ij}^{(N)})_{i,j=1}^N\qquad\text{and}\qquad
Y^{(N)}=(b_{ij}^{(N)})_{i,j=1}^N
\end{equation}
be symmetric $N\times N$-random matrices with
\newline
i)
$a_{ij}^{(N)}$ ($1\leq i\leq j\leq N$) are independent and
normally distributed (mean zero, variance $1/N$)
\newline
ii)
$b_{ij}^{(N)}$ ($1\leq i\leq j\leq N$) are independent and
normally distributed (mean zero, variance $1/N$)
\newline
iii) all $a_{ij}^{(N)}$ are independent from all
$b_{kl}^{(N)}$
\newline
Then $X^{(N)}$ and $Y^{(N)}$ become free in the limit
$N\to\infty$ with respect to
\begin{equation}
\ff(\cdot):=\frac 1N\langle \tr(\cdot)\rangle_{ensemble}.
\end{equation}
2) Let $A^{(N)}$ and $B^{(N)}$
be symmetric deterministic (e.g. diagonal) $N\times N$-matrices
whose eigenvalue distribtutions tend to some fixed
probability measures $\mu$ and $\nu$, respectively, in
the limit $N\to\infty$.
Consider now
\begin{equation}
X^{(N)}:=A^{(N)}\qquad\text{and}\qquad
Y^{(N)}:=UB^{(N)}U^*,
\end{equation}
where $U$ is a random unitary $N\times N$-matrix from
the ensemble
\begin{equation}
U\in\Omega_N=(U(N), \,Haar\, measure).
\end{equation}
Then $X^{(N)}$ and $Y^{(N)}$ become free
in the limit $N\to\infty$
with respect to
\begin{equation}
\ff(\cdot):=\frac 1N \langle \tr(\cdot)\rangle_{\Omega_N}.
\end{equation}
\end{thm}
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\to\infty$,
towards the so-called semi-circle distribution.
We can also say that (in the sense of convergence of all
moments)
\begin{equation}
\lim_{N\to\infty} (X^{(N)},Y^{(N)})=(X,Y),
\end{equation}
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
semi-circular distributions, but we can prescribe in the limit any
distribution we want. In this case we can
rephrase the statement in the form
\begin{equation}
\lim_{N\to\infty} (X^{(N)},Y^{(N)})=(X,Y),
\end{equation}
where $X$ and $Y$ are free and have the prescribed
distributions
\begin{equation}
\mu_X=\mu\qquad\text{and}\qquad \mu_Y=\nu.
\end{equation}
As a conclusion one can say that \lq freeness' can
also be considered as the mathematical structure of
$N\times N$-random matrices which survives in the
limit $N\to\infty$, or that \lq freeness' is the right concept for
the description of $\infty\times\infty$-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
\lq freeness' in physical applications. Random matrices
are quite frequently introduced in physics, usually in connection
with some approximations. In such a context,
the concept \lq 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 \cite{Sp5}.
\bibliographystyle{amsplain}
\providecommand{\bysame}{\leavevmode\hbox to3em{\hrulefill}\thinspace}
\begin{thebibliography}{99}
\bibitem{B}
H.W.~Becker, \emph{Planar rhyme schemes}, Bull. Amer. Math.
Soc.~\textbf{58} (1952), 39.
\bibitem{Bia1}
P.~Biane, \emph{Some properties of crossings and partitions},
to appear in Discrete Math.
\bibitem{Bia2}
P.~Biane, \emph{Minimal factorizations of a cycle and central
multiplicative functions on the infinite symmetric group},
J.~Combin.~Th.~A \textbf{76} (1996), 197--212.
\bibitem{DRS}
P.~Doubilet, G.-C.~Rota, and R.~Stanley,
\emph{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.
\bibitem{Dyk}
K.~Dykema,
\emph{Interpolated free group factors},
Pac. J. Math.
\textbf{163} (1994), 123--135.
\bibitem{E1}
P.H.~Edelman, \emph{Chain enumeration and non-crossing partitions},
Discrete Math.~\textbf{31} (1980), 171--180.
\bibitem{E2}
P.H.~Edelman, \emph{Multichains, non-crossing partitions and trees},
Discrete Math.~\textbf{40} (1982), 171--179.
\bibitem{K}
G.~Kreweras, \emph{Sur les partitions non-croisees d'un cycle},
Discrete Math. \textbf{1} (1972), 333--350.
\bibitem{N}
A.~Nica, \emph{$R$-transforms of free joint distributions, and
non-crossing partitions}, J. Funct. Anal.~\textbf{135} (1996),
271--296.
\bibitem{NS1}
A.~Nica and R.~Speicher, \emph{A "Fourier Transform" for
Multiplicative Functions on Non-Crossing Partitions}, Journal
of Algebraic Combinatorics \textbf{6} (1997), 141--160.
\bibitem{NS2}
A.~Nica and R.~Speicher, \emph{On the multiplication of free
$n$-tuples of non-commutative random variables}
(with an appendix by D. Voiculescu), Amer. J. Math. \textbf{118}
(1996), 799--837.
\bibitem{NS3}
A.~Nica and R.~Speicher, \emph{{$R$}-diagonal pairs---a common approach to
{Haar} unitaries and circular elements}, Free Probability
Theory (D.-V. Voiculescu,
ed.), AMS, 1997, pp.~149--188.
\bibitem{NS4}
A.~Nica and R.~Speicher, \emph{Commutators of free random
variables}, to appear in Duke Math. J.;
also available under\newline
{\tt http://www.rzuser.uni-heidelberg.de/$\sptilde$L95}
\bibitem{P}
Y.~Poupard, \emph{Etude et denombrement paralleles des partitions
non croisees d'un cycle et des coupage d'un polygone convexe},
Discrete Math. \textbf{2} (1972), 279--288.
\bibitem{Rad}
F.~Radulescu,
\emph{Random matrices, amalgamated free products and
subfactors of the von Neumann algebra of a free group, of noninteger
index}, Invent. math.~\textbf{115} (1994), 347--389.
\bibitem{R}
G.-C.~Rota, \emph{On the foundations of combinatorial theory I:
Theory of M\"obius functions}, Z. Wahrscheinlichkeitstheorie Verw.
Geb.~\textbf{2} (1964), 340--368.
\bibitem{Sh}
A.N.~Shiryayev, \emph{Probability} (Grad. Texts Math., vol.~95),
Springer, 1984.
\bibitem{SU}
R.~Simion and D. Ullman, \emph{On the structure of the lattice of
non-crossing partitions}, Discrete Math.~\textbf{98} (1991),
193--206.
\bibitem{Sp1}
R.~Speicher, \emph{A new example of \lq independence' and
\lq white noise'}, Probab. Theory Rel. Fields \textbf{84}
(1990), 141--159.
\bibitem{Sp2}
R. Speicher, \emph{Multiplicative functions on the lattice of
non-crossing partitions and free convolution},
Math. Ann.~\textbf{298} (1994), 611--628.
\bibitem{Sp3}
R.~Speicher, \emph{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 \newline
{\tt http://www.rzuser.uni-heidelberg.de/$\sptilde$L95}
\bibitem{Sp4}
R.~Speicher, \emph{Free Convolution and the Random
Sum of Matrices}, Publ. RIMS~\textbf{29} (1993), 731--744.
\bibitem{Sp5}
R.~Speicher, \emph{Physical applications of freeness},
to appear in the Proceedings of the International Congress
on Mathematical Physics, Brisbane, 1997;
also available under \newline
{\tt http://www.rzuser.uni-heidelberg.de/$\sptilde$L95}
\bibitem{V1}
D. Voiculescu, \emph{Symmetries of some reduced free product
$C^*$-algebras}, Operator Algebras and Their Connection with
Topology and Ergodic Theory (Lecture Notes in Mathematics
\textbf{1132}), Springer, 1985, pp.~556--588.
\bibitem{V2}
D. Voiculescu, \emph{Addition of certain non-commuting
random variables}, J. Funct. Anal.~\textbf{66} (1986),
323--346.
\bibitem{V3}
D. Voiculescu, \emph{Multiplication of certain non-commuting random
variables}, J. Operator Theory~\textbf{18} (1987), 223--235.
\bibitem{V4}
D. Voiculescu, \emph{Limit laws for random matrices and free
products}, Invent. math.~\textbf{104} (1991), 201--220.
\bibitem{V5}
D. Voiculescu, \emph{Free probability theory: random matrices and
von Neumann algebras} Proceedings of the ICM 1994,
Birkh\"auser, 1995, pp.~227--241.
\bibitem{V6}
D. Voiculescu (ed.), \emph{Free Probability Theory} (Fields
Institute Communications, vol.~12), AMS, 1997
\bibitem{VDN}
D.V.~Voiculescu, K.J.~Dykema, and A.~Nica, \emph{Free
Random Variables} (CRM Monograph Series, vol.~1), AMS, 1993.
\end{thebibliography}
\end{document}