2000 Mathematics Subject Classification. 16W30 (46L37, 46L54).
<ph f="cmbx">Free product formulae for quantum permutation groups</ph>

Teodor Banica

Julien Bichon

Departement de Mathematiques, Universite Paul Sabatier, 118 route de Narbonne, 31062 Toulouse, France E-mail address : banica@picard.ups-tlse.fr Laboratoire de Mathematiques Appliquees, Universite de Pau et des Pays de l'Adour, IPRA, Avenue de l'universite, 64000 Pau, France E-mail address : bichon@univ-pau.fr

Introduction

A quantum group is an abstract object, dual to a Hopf algebra. Finite quantum groups are those which are dual to finite dimensional Hopf algebras.
A surprising fact, first noticed by Wang in [24] , is that the quantum group corresponding to the Hopf algebra C * ( Z 2 * Z 2 )   has a faithful action on the set { 1 , 2 , 3 , 4 }   . This quantum group, which is of course not finite, is a so-called quantum permutation group.
In general, a quantum permutation group G   is described by a special type of Hopf C *   -algebra A   , according to the heuristic formula A = C ( G )   . See [2] , [24] .
The simplest case is when A   is commutative. Here G   is a subgroup of the symmetric group S n   . This situation is studied by using finite group techniques.
In general A   is not commutative, and infinite dimensional. In this case G   is a non-classical, non-finite compact quantum group. There is no analogue of a Lie algebra in this situation, but several representation theory methods, due to Woronowicz, are available ([25] , [26] ).
A useful point of view comes from the heuristic formula A = C * ( Γ )   . Here Γ   is a discrete quantum group, obtained as a kind of Pontrjagin dual of G   . Number of discrete group techniques are known to apply to this situation. See e.g. [18] , [19] .
It is also known from [2] that quantum permutation groups are in one-to-one correspondence with subalgebras of spin planar algebras constructed in [11] , [12] .
Summarizing, a quantum permutation group should be regarded as a mixture of finite, compact and discrete groups, with a flavor of statistical mechanics, knot invariants and planar algebras. Several results are obtained along these lines in [1] , [2] , [3] , [4] , [5] .
The aim of this work is to bring into the picture some free probability techniques.
The starting point is the classical formula G ( X … X ) = G ( X ) × w G ( X n )   for usual symmetry groups. Here X   is a finite connected graph, X n   is a set having n   elements, X … X   is the disjoint union of n   copies of X   , and × w   is a wreath product. A series of free quantum analogues and generalisations, started in [5] and continued here, leads to a general formula of type A ( X * Y ) = A ( X ) * w A ( Y )   . Here X , Y   are colored graphs, and * w   is a free wreath product.
The corepresentation theory of free wreath products is worked out in two particular situations in [2] , [5] . Our key remark here is that a formula of type μ ( A * w B ) = μ ( A ) ⊠ μ ( B )   holds in both cases, where μ   is the associated spectral measure. We conjecture that this formula holds in general, and under mild assumptions on A   and B   .
This is to be related to a planar algebra formula of type μ ( P * Q ) = μ ( P ) ⊠ μ ( Q )   , known to Bisch and Jones ([10] ). In fact, a general formula of type A ( X * Y ) = A ( X ) * w A ( Y )   , with colored graphs replaced by planar algebras, would be equivalent to the conjecture.
Of particular interest is the case B = A ( X n )   . Here the conjecture, together with Voiculescu's S   -transform technique ([21] ) reduces computation of μ ( X )   with X   homogeneous to that of μ ( X )   with X   connected and homogeneous. For n = 2   the conjecture is actually a theorem, and, as an application, we compute μ   for the graph which looks like 2 rectangles. This completes previous classification work for graphs having at most 8   vertices ([1] , [2] ).
The paper is organised as follows. 1 is a preliminary section. In 2 and 3 we rearrange some previously known results, with the main improvement that we use spectral measures insteadof Poincaré series. Among key remarks here is that the passage from classical to quantum permutation groups corresponds to the passage from a Poisson law to a free Poisson law.
In 4 we present a first verification of the conjecture, using free probability tools. In 5 and 6 we prove the formula for graphs, and we deduce from it a second verification of the conjecture, using planar algebra methods. In 7 and 8 we discuss disconnected graphs.

Acknowledgments

We are grateful to Philippe Biane, Dietmar Bisch and Mireille Capitaine for several useful discussions.

1 Formalism

Let A   be a unital C *   -algebra. That is, we have an associative algebra with unit A   over the field of complex numbers C   , with an antilinear antimultiplicative map a → a *   satisfying a * * = a   , and with a Banach space norm satisfying | | a * a | | = | | a | | 2   .
A projection is an element satisfying p 2 = p * = p   . Two projections are said to be orthogonal when p q = 0   . A partition of the unity is a finite set of projections, which are mutually orthogonal, and sum up to 1   .
Definition 1.1. A magic biunitary matrix is a square matrix v ∈ M n ( A )   , all whose rows and columns are partitions of the unity of A   .
A magic biunitary is indeed a biunitary, in the sense that both v   and its transpose v t   are unitaries. The other word – magic – comes from a vague similarity with magic squares.
The basic example comes from the symmetric group S n   . Consider the following sets.
S i j = { g ∈ S n | g ( j ) = i }   When i   is fixed and j   varies, or vice versa, these sets form partitions of S n   . Thus their characteristic functions s i j ∈ C ( S n )   form a magic biunitary.
At n = 4   we have the following key example.
d = ( p 1 − p 0 0 1 − p p 0 0 0 0 q 1 − q 0 0 1 − q q )   Here p , q   are projections, say on some Hilbert space H   . If p , q   are chosen to be free, the algebra they generate is isomorphic to C * ( Z 2 * Z 2 )   . This shows that entries of a magic biunitary matrix can generate a non commutative, infinite dimensional algebra.
The universal magic biunitary matrix is constructed by Wang in [24] .
Definition 1.2. A ( X n )   is the universal C *   -algebra generated by n 2   elements u i j   , with the relations making ( u i j )   a magic biunitary matrix.
In other words, we have the following universal property. For any magic biunitary matrix v ∈ M n ( A )   there is a morphism of C *   -algebras A ( X n ) → A   mapping u i j → v i j   .
The matrix s   produces a quotient map A ( X n ) → C ( S n )   . This is an isomorphism for n = 1 , 2   , both algebras involved having dimension 1 , 2   . A similar result holds for n = 3   , because entries of a 3 × 3   magic biunitary matrix can be shown to commute with each other.
The matrix d   produces a quotient map A ( X 4 ) → C * ( Z 2 * Z 2 )   , which shows that A ( X 4 )   is not commutative, and infinite dimensional. The same holds for A ( X n )   with n ≥ 4   .
The algebra A ( X n )   has a comultiplication map Δ   , making u   a corepresentation. Δ ( u i j ) = ∑ u i k ⊗ u k j   There is also a counit given by ɛ ( u i j ) = δ i j   , and an antipode given by S ( u i j ) = u j i   . All three maps are constructed by using the universal property of A ( X n )   . For instance the counit comes from the fact that the unit matrix ( δ i j )   is a magic biunitary in M n ( C )   .
Thus A ( X n )   is a Hopf C *   -algebra in the sense of Woronowicz [25] . Associated to it are a compact and a discrete quantum group, according to the following heuristic formula.
A ( X n ) = C ( G n ) = C * ( Γ n )   With this formalism, we have an inclusion S n ⊂ G n   , which for n = 1 , 2 , 3   is an isomorphism.
Also, we have a quotient map Γ 4 → Z 2 * Z 2   , which shows that Γ 4   is not abelian, nor finite.
Thus its Pontrjagin dual G 4   is not a compact group, nor a finite quantum group. The same is true for any G n   with n ≥ 4   , because G n   contains G 4   as a quantum subgroup.
The following fundamental result is due to Wang ([24] ).
Theorem 1.1. A ( X n )   is the universal Hopf C *   -algebra coacting on X n = { 1 , … , n }   .
In general, a coaction of a Hopf C *   -algebra A   on the set X n   is a morphism of C *   -algebras of the following type, satisfying a coassociativity condition.
α : C ( X n ) → C ( X n ) ⊗ A   The universal coaction can be defined as a linear map, by the following formula.
α ( δ i ) = ∑ δ j ⊗ u j i   Since u   is a magic biunitary, α   is a morphism of C *   -algebras, and since u   is a corepresentation, α   is coassociative. Universality comes from the fact that a linear map of type α ( δ i ) = ∑ δ j ⊗ v j i   is a morphism of C *   -algebras if and only if all rows of v   are partitions of unity. By applying the antipode the same must hold for the transpose matrix v t   , and this leads to the result.
The coaction α   should be interpreted as coming from an action a ( i , σ ) = σ ( i )   of the quantum group G n   on the set X n   , via the transposition formula α φ = φ a   .
a : X n × G n → X n   Since α   is universal, a   is universal as well, so G n   is a kind of quantum analogue of S n   .
In what follows, we will be interested in quantum subgroups of G n   .
Definition 1.3. A quantum permutation group of X n   corresponds to a pair ( A , v )   , where A   is a Hopf C *   -algebra quotient of A ( X n )   , and v i j ∈ A   is the image of u i j ∈ A ( X n )   .
In other words, we have a Hopf C *   -algebra A   , and a magic biunitary matrix v ∈ M n ( A )   . We assume that v   is a corepresentation of A   , meaning that Δ ( v i j ) = ∑ v i k ⊗ v k j   and ɛ ( v i j ) = δ i j   , and that entries of v   generate A   . Observe that the antipode is given by S ( v i j ) = v j i   .
As with any Hopf C *   -algebra, a main problem regarding A   is to find its irreducible corepresentations, and their fusion rules. Since coefficients of v   generate A   , each such corepresentation appears in a tensor power of v   . So, a first problem is to decompose these tensor powers.
v ⊗ k = c k ⋅ 1 + ∑ r ≠ 1 m k r ⋅ r   The trivial corepresentation 1   plays here a distinguished role, because computing its multiplicity c k   is the very first question to be asked. By taking characters and by applying the Haar functional we obtain the following formula, where χ = v 11 + … + v n n   is the character of v   .
∫ χ k = c k   Consider now a polynomial φ ( x ) = a 0 + a 1 x + … + a k x k   . By applying it to χ   we get an element φ ( χ ) ∈ A   , then we can apply the Haar functional to this element.
∫ φ ( χ ) = a 0 + a 1 c 1 + … + a k c k   We have here a linear map C [ X ] → C   , which extends by density to continuous functions, and is given by integration with respect to a real measure, called spectral measure of χ   .
Definition 1.4. The spectral measure of the character of the fundamental corepresentation χ = v 11 + … + v n n   with respect to the Haar functional is given by ∫ φ ( χ ) = ∫ φ ( x ) d μ ( x )   for any continuous function φ : R → C   . This is a probability measure on [ 0 , n ]   .
We will regard μ   as an invariant of A   , encoding the sequence of numbers c k   .As a first motivating fact, a Kesten type criterion shows that A   is amenable in the discrete quantum group sense if and only if n   is the upper bound of the support of μ   . Also, in certain situations, fusion rules for A   can be recovered from μ   . See [2] , [3] .
Another invariant, equivalent to μ   , is the Poincaré series of the planar algebra associated to A   . This planar algebra is the graded union of spaces P k   of fixed points of v ⊗ k   , and its Poincaré series, or dimension function, is given by the following formula.
f ( z ) = ∑ k = 0 ∞ c k z k = ∫ 1 1 − z χ = ∫ 1 1 − z x d μ ( x )   The Poincaré series is the invariant used by Bisch and Jones in their classification program [8] , [9] . Also, the following related series appears in Jones' fundamental work [13] .
Θ ( q ) = q + 1 − q 1 + q f ( q ( 1 + q ) 2 )   This is the generating series of the decomposition of P   as sum of planar modules over T L ( n )   .
Its coefficients a k   being multiplicities, they satisfy a k ≥ 0   . These inequalities give a number of conditions on the numbers c k   , which can be regarded as fine algebraic properties of A   .

2 Poisson laws

There are a few known computations of spectral measures. These are direct computations of type A → μ ( A )   , or decomposition results of type μ ( A × B ) = μ ( A ) × μ ( B )   .
In this paper we rearrange most of what is known, in the form of two computations, three basic decomposition results, and a conjectural decomposition result.
The two computations are presented in this section. One conclusion will be that, at an asymptotic level, the passage from the classical algebra C ( S n )   to the quantum algebra A ( X n )   corresponds to the passage from a Poisson law to a free Poisson law.
Consider first a subgroup G ⊂ S n   . The algebra of complex functions C ( G )   is a Hopf C *   -algebra, with comultiplication given by Δ ( φ ) : ( g , h ) → φ ( g h )   . The corresponding coaction on X n   has as coefficients the characteristic functions of the sets { g ∈ G | g ( j ) = i }   .
Proposition 2.1. For a subgroup G ⊂ S n   the spectral measure of C ( G )   is μ = 1 | G | ∑ s = 0 n m s δ s   where m s   is the number of permutations in G   having exactly s   fixed points.
  • Proof. We have χ ( g ) = s   , where s   is the number of fixed points of g   . This gives the following formula for the Poincaré series, see [2] for details.
    f ( z ) = 1 | G | ∑ s = 0 n m s 1 − s z   Since coefficients of f   are moments of μ   , we conclude that μ   is the spectral measure. □
The Poisson law of parameter 1   is the following probability measure on the real line.
ν = 1 e ∑ s = 0 ∞ 1 s ! δ s   We can apply Proposition 2.1 to the symmetric group G = S n   . The spectral measure appears to be a kind of truncated exponential of δ 1 − δ 0   , converging to ν   .
Theorem 2.1. The spectral measure of C ( S n )   is given by ν n = ∑ t = 0 n 1 t ! ( δ 1 − δ 0 ) * t   where *   is the convolution of real measures. In particular we have ν n → ν   .
  • Proof. Permutations having exactly s   fixed points are obtained by choosing these s   points, then by permuting the remaining l = n − s   ones in such a way that there is no fixed point. These latter permutations are counted as follows: we start with all permutations, then we substract those having one fixed point, we add those having two fixed points, and so on. m s = ( n s ) ( l ! − ( l 1 ) ( l − 1 ) ! + ( l 2 ) ( l − 2 ) ! − … )   This allows us to compute the spectral measure.
    ν n = 1 n ! ∑ s = 0 n ( n s ) ( ∑ k = 0 n − s ( − 1 ) k ( n − s ) ! k ! ) δ s
    = ∑ s = 0 n ∑ k = 0 n − s ( − 1 ) k 1 n ! ⋅ n ! s ! ( n − s ) ! ⋅ ( n − s ) ! k ! δ s
    = ∑ s = 0 n ∑ k = 0 n − s ( − 1 ) k s ! k ! δ s
    We can further improve this formula, by summing over k   and over t = k + s   .
    ν n = ∑ t = 0 n ∑ k = 0 t ( − 1 ) k ( t − k ) ! k ! δ t − k
    = ∑ t = 0 n 1 t ! ∑ k = 0 t ( − 1 ) k ( t k ) δ t − k
    = ∑ t = 0 n 1 t ! ( δ 1 − δ 0 ) * t
    The last assertion follows by considering the Fourier transform of ν n   .
    F n ( y ) = ∑ t = 0 n 1 t ! ( e i y − 1 ) t   With n → ∞   we get the following function.
    F ( y ) = e ( e i y − 1 )   This is the Fourier transform of the Poisson law, and we are done. □
Another known computation is for the universal algebra A ( X n )   . Recall first that the normalised semicircular law is the following probability measure on [ − 2 , 2 ]   .
γ = 1 2 π 4 − x 2 d x   A variable s   having this spectral measure is called semicircular. The spectral measure of s 2   is called free Poisson law of parameter 1   , and is given by the following formula.
η = 1 2 π 4 x − 1 − 1 d x   The terminology comes from the fact that in the central limit theorem, the Gaussian law from classical probability gets replaced by the semicircular law in free probability. In other words, semicircular means free Gaussian, so square of semicircular means free Poisson. The measure η   is also called Marchenko-Pastur law of parameter 1   . See [16] , [22] , [23] .
Theorem 2.2. The spectral measure of A ( X n )   is given by η 1 = δ 1   and η 2 = 1 2 ( δ 0 + δ 2 )   η 3 = 1 6 ( 2 δ 0 + 3 δ 1 + δ 3 )   η 4 + = 1 2 π 4 x − 1 − 1 d x   where 4 +   denotes any positive integer n ≥ 4   . In particular we have η n → η   .
  • Proof. It is known from [2] that A ( X n )   corresponds to the Temperley-Lieb algebra T L ( n )   , whose Poincaré series is computed by counting diagrams, and is given by the following formulae.
    f 2 ( z ) = 1 2 ( 1 + 1 1 − 2 z )   f 3 ( z ) = 1 6 ( 2 + 3 1 − z + 1 1 − 3 z )   f 4 + ( z ) = 1 − 1 − 4 z 2 z   The corresponding measures can be recaptured by using the Stieltjes formula.
    d μ ( x ) = lim t ↘ 0 − 1 π Im ( G ( x + i t ) ) ⋅ d x   Here G   is the Cauchy transform of a real measure μ   . This is given by G ( ξ ) = ξ − 1 f ( ξ − 1 )   , where f   is the generating series of the moments of μ   . In our situation f   is the Poincaré series, and we get the following formulae of Cauchy transforms. G 2 ( ξ ) = 1 2 ( 1 ξ + 1 ξ − 2 )   G 3 ( ξ ) = 1 6 ( 2 ξ + 3 ξ − 1 + 1 ξ − 3 )   G 4 + ( ξ ) = 1 − 1 − 4 ξ − 1 2   The Stieltjes formula applies, and gives the measures in the statement. □
This proof, based on counting diagrams, doesn't quite tell us why η 4 +   is a free Poisson law, or a Marchenko-Pastur law. In order to get a more enlightening explanation here, some kind of matrix model for A ( X 4 + )   seems to be needed. So far, the only result in this sense is the one in [3] , where an explicit realisation of A ( X 4 )   is found. The model there uses a 4 × 4   matrix constructed using quaternions, which shows that η 4   is indeed the law of the square of a semicircle, appearing as a meridian on the real sphere S 3   .

3 Decomposition results

We discuss now decomposition results of type μ ( A × B ) = μ ( A ) × μ ( B )   . We have here three basic results, plus a conjecture, unifying two previously known computations from [2] , [5] .
If A , B   are given with linear forms h , k   , the tensor product A ⊗ B   has a canonical linear form, namely the tensor product h ⊗ k   . Also, the free product A * B   has a canonical linear form h * k   , called free product of h   and k   . See [23] .
We regard A   and B   as being subalgebras of A ⊗ B   and of A * B   .
For x ∈ A   and y ∈ B   the spectral measures of x + y   and of x y   in A ⊗ B   and in A * B   depend only on the spectral measures of x , y   . The corresponding four operations on real measures are called additive convolution, multiplicative convolution, free additive convolution, and free multiplicative convolution, and are denoted * , × , ⊞ , ⊠   .
Definition 3.1. Assume that x ∈ A   and y ∈ B   have spectral measures μ   and ν   .
(i) The spectral measure of x + y ∈ A ⊗ B   is denoted μ * ν   .
(ii) The spectral measure of x y ∈ A ⊗ B   is denoted μ × ν   .
(iii) The spectral measure of x + y ∈ A * B   is denoted μ ⊞ ν   .
(iv) The spectral measure of x y ∈ A * B   is denoted μ ⊠ ν   .
Consider now two pairs ( A , u )   and ( B , v )   as in Definition 1.3. Denote by A × B   the tensor product, or the free product of A   and B   . This is a Hopf C *   -algebra, and the matrices u   and v   can be regarded as corepresentations of it. We can form their direct sum and tensor product.
u ⊕ v = ( u 0 0 v )   ( u ⊗ v ) i a , j b = u i j v a b   The direct sum is a magic biunitary matrix, whose coefficients generate A × B   . As for the tensor product, its coefficients generate as well A × B   , but they do not form a magic biunitary matrix, unless ×   is the tensor product.
Proposition 3.1. We have the formulae μ ( A ⊗ B , u ⊕ v ) = μ ( A , u ) * μ ( B , v )   μ ( A ⊗ B , u ⊗ v ) = μ ( A , u ) × μ ( B , v )   μ ( A * B , u ⊕ v ) = μ ( A , u ) ⊞ μ ( B , v )   where * , × , ⊞   are the additive, multiplicative, and free additive convolutions.
  • Proof. The corresponding characters are given by the following formulae.
    χ ( u ⊕ v ) = χ ( u ) + χ ( v )   χ ( u ⊗ v ) = χ ( u ) χ ( v )   The Haar functional of A × B   being the ×   product of those of A   and B   , the variables χ ( u ) ∈ A × B   and χ ( v ) ∈ A × B   are independent or free, and have same spectral measures as χ ( u ) ∈ A   and χ ( v ) ∈ B   . The result follows from the definition of convolutions. □
The free wreath product A * w B   is constructed in [4] . This is the algebra generated by n   copies of A   and a copy of B   , with the a   -th copy of A   commuting with the a   -th row of v   , for any a   .
The maps Δ   and ɛ   are constructed by using the universal property of A * w B   .
Definition 3.2. The free wreath product of ( A , u )   and ( B , v )   is given by A * w B = ( A * n * B ) / < [ u i j ( a ) , v a b ] = 0 >   where n × n   is the size of v   . This has fundamental magic biunitary matrix w i a , j b = u i j ( a ) v a b   and Hopf algebra structure making w   a corepresentation.
There are several approaches to free wreath products, to be discussed in what follows. A very first thing to be noticed is the following diagram.
A * n * B → A * w B ↓ ↓ A * B → A ⊗ B
Here all maps are surjective morphisms of C *   -algebras, coming from definitions. Vertical maps are obtained by collapsing the n   copies of A   to a single one, and horizontal maps correspond to certain commutation relations with rows of v   .
This diagram gives different ways of mixing diagonal elements u i i   and v a a   .
∑ u i i ( a ) v a a → ∑ u i i ( a ) v a a ↓ ↓ ∑ u i i v a a → ∑ u i i ⊗ v a a
Here in the upper right corner we have the unknown, namely the character of w   .
In the lower left corner we have a familiar object, namely the character of u ⊗ v   . This corepresentation u ⊗ v   is not a magic biunitary, but the corresponding spectral measure can be constructed as in Definition 1.4, and is given by the missing formula in Proposition 3.1.
The spectral measures of these two elements can be computed in several cases of interest, and turn to be equal. However, equality doesn't hold in general, and a quite natural assumption here is that all diagonal elements u i i   , as well as all diagonal elements v a a   , should have same spectral measure. In terms of Hopf algebras, this leads to the following statement.
Conjecture 3.1. If A   and B   have homogeneous skeletons we have the formula μ ( A * w B , w ) = μ ( A , u ) ⊠ μ ( B , v )   where ⊠   is the free multiplicative convolution.
The notion of skeleton is introduced as follows. The idea is to regard each pair ( B , v )   as corresponding to the quantum symmetry group of a graph-like object X = ( X n , D )   . This is definitely possible for all known examples of ( B , v )   , because they appear naturally in this way.
In the general case one can take for instance the combinatorial data D   to be the planar algebra associated to ( B , v )   , by using the Tannaka-Galois type correspondence in [2] .
A skeleton X = ( X n , D )   is called homogeneous if for any i , j ∈ X n   there is a permutation g ∈ S n   preserving the combinatorial data D   , such that g ( i ) = j   .
All this is probably a bit too heuristic, but finding the precise assumptions in Conjecture 3.1 is rather a matter of proving the conjecture, and this is not among purposes of this paper.
We should mention here that finding a truly delinearised definition for skeletons is quite a subtle problem, beyond the state-of-art of the subject. At level of general planar algebras this is known to be possible, as shown by Kodiyalam and Sunder in [14] .
In the rest of this section we will just explain why some assumptions are needed, and why these should correspond to homogeneity of skeletons of A   and B   .
Our first task is to construct a counterexample. We use the following simple fact.
Proposition 3.2. We have a canonical isomorphism ( A , u ) * w ( B 1 * B 2 , v 1 ⊕ v 2 ) = ( A * w B 1 ) * ( A * w B 2 )   for any three pairs ( A , u )   , ( B 1 , v 1 )   and ( B 2 , v 2 )   .
  • Proof. The algebra on the left is generated by n 1 + n 2   copies of A   and a copy of B 1 * B 2   , subject to certain commutation relations. These relations say that the first n 1   copies of A   commute with corresponding rows of the matrix v 1   , and that the remaining n 2   copies of A   commute with corresponding rows of the matrix v 2   . In other words, when moving the copy of B 2   from the n 1 + n 2 + 2   -th position to the n 1 + 1   -th position, we get the algebra on the right. □
Now if we assume that Conjecture 3.1 holds without assumptions on ( B , v )   , we would get from Propositions 3.1 and 3.2 a kind of distributivity formula for ⊠   with respect to ⊞   .
μ ⊠ ( μ 1 ⊞ μ 2 ) = ( μ ⊠ μ 1 ) ⊞ ( μ ⊠ μ 2 )   This formula is known to be wrong, so some assumptions on ( B , v )   are needed in Conjecture 3.1. We believe that homogeneity of the skeleton, not satisfied by ( B 1 * B 2 , v 1 ⊕ v 2 )   , but satisfied in the two cases where we know how to prove the conjecture, is the good one.
As for the assumption on ( A , u )   , we are less confident about it. Let us mention here that Conjecture 3.1 should be regarded as an analogue of the planar algebra formula μ ( P * Q ) = μ ( P ) ⊠ μ ( Q )   of Bisch and Jones ([10] ). In fact, we have the following computation.
μ ( A * w B ) = μ ( P ( A * w B ) )
= μ ( P ( A ) * P ( B ) )
= μ ( P ( A ) ) ⊠ μ ( P ( B ) )
= μ ( A ) ⊠ μ ( B )
Here the first and fourth equality come from the Tannaka-Galois type correspondence A → P ( A )   from [2] . The third equality comes from the formula of Bisch and Jones. The second equality comes from the following conjectural formula.
P ( A * w B ) = P ( A ) * P ( B )   This formula should be regarded as a version of Conjecture 3.1. The above computation shows that the formula is stronger than the conjecture, but one can probably go in the other sense as well, by using the following basic lemma.
Lemma 3.1. Assume that ( A , u )   and ( B , v )   correspond to quantum permutation groups of X n   , and let f : A → B   be a morphism of C *   -algebras such that f ( u i j ) = v i j   .
(i) f   is a surjective morphism of Hopf C *   -algebras.
(ii) The k   -th moment of μ ( A )   is smaller than the k   -th moment of μ ( B )   , for any k   .
(iii) f   is an isomorphism if and only if μ ( A ) = μ ( B )   .
  • Proof. The first two assertions follows from definitions. The third one is well-known, and follows by taking a basis of coefficients of irreducible corepresentations, as in [26] . □
As a conclusion, what is behind the conjecture is that the free wreath product operation * w   should correspond to a kind of free product operation *   at level of skeletons. This approach suggests that ( A , u )   and ( B , v )   will have to play at some point symmetric roles, and this is why homogeneity of the skeleton of ( A , u )   is included in Conjecture 3.1.

4 Finite groups

The simplest example of a free wreath product is with B = C ( G )   , where G   is a finite group acting on itself. That is, we consider G   as being a subgroup of S n   , where n   is the order of G   .
The matrix v   has a particularly simple form.
v = ( δ 1 δ 12 . . . δ 1 n δ 21 δ 1 . . . δ 2 n . . . . . . . . . . . . δ n 1 δ n 2 . . . δ 1 )   Here δ 1   is the Dirac mass at the unit element 1 ∈ G   , and for i , j ∈ X n   we denote by δ i j   the Dirac mass at the unique element g ∈ G   satisfying g ( j ) = i   . We see that each row of v   consists of Dirac masses at elements of G   , so in particular its entries generate C ( G )   . This shows that a free wreath product by C ( G )   has the following decomposition.
A * w C ( G ) = A * n ⊗ C ( G )   This is pointed out in [5] , where the case of G = Z 2   is worked out explicitely, with a complete discussion of corepresentations of the free wreath product. The fusion rules found there allow one to compute the spectral measure of the free wreath product. In what follows we present this computation of spectral measure, along with a generalisation to arbitrary groups G   .
We use Voiculescu's S   -transform, whose log linearises ⊠   .
S ( μ ⊠ ν ) = S ( μ ) S ( ν )   The S   -transform of a measure μ   is constructed by introducing series ψ , χ   as follows ([21] ).
ψ ( z ) = f ( z ) − 1 χ ∘ ψ = ψ ∘ χ = i d S ( z ) = 1 + z z χ ( z )   Here f   is the series having as coefficients the moments of μ   . In case μ   is the spectral measure associated to a Hopf C *   -algebra A   , this series f   is the Poincaré series of A   .
It is useful to compute both the spectral measure of C ( G )   , and its S   -transform.
Proposition 4.1. For a group G   acting on itself the corresponding spectral measure of C ( G )   and its S   -transform are given by μ = n − 1 n δ 0 + 1 n δ n   S ( z ) = 1 + z 1 + n z   where n   is the number of elements of G   .
  • Proof. The identity of G   has n   fixed points, and the other n − 1   elements, none. Together with Proposition 2.1 this gives the formula of μ   , then we get f , ψ , χ   .
    μ = n − 1 n δ 0 + 1 n δ n ⇒ f ( z ) = 1 + z 1 − n z
    ⇒ ψ ( z ) = z 1 − n z
    ⇒ z = χ ( z ) 1 − n χ ( z )
    ⇒ χ ( z ) = z 1 + n z
    Multiplying by 1 + z − 1   gives the formula in the statement. □
Theorem 4.1. If G   is a finite group acting on itself then μ ( A * w C ( G ) ) = μ ( A ) ⊠ μ ( C ( G ) )   where ⊠   is the free multiplicative convolution.
  • Proof. We denote by χ , χ l   the characters of u , w   , and by μ , μ l   the associated spectral measures.
    The tensor product decomposition of the free wreath product gives the following formula.
    χ l = ( χ ( 1 ) + … + χ ( n ) ) ⊗ δ 1   We raise both terms to the power k ≥ 1   .
    χ l k = ( χ ( 1 ) + … + χ ( n ) ) k ⊗ δ 1   The Haar functional of the tensor product being the tensor product of Haar functionals, we get the following formula.
    ∫ χ l k = 1 n ∫ ( χ ( 1 ) + … + χ ( n ) ) k   We get a formula which is valid for any polynomial φ   . ∫ φ ( χ l ) = n − 1 n φ ( 0 ) + 1 n ∫ φ ( χ ( 1 ) + … + χ ( n ) )   Now remember that elements χ ( a )   are free, and each of them has spectral measure μ   . This gives the following identity.
    ∫ φ ( x ) d μ l ( x ) = n − 1 n φ ( 0 ) + 1 n ∫ φ ( x ) d μ ⊞ n ( x )   This finishes computation of the spectral measure on the left.
    μ l = n − 1 n δ 0 + 1 n μ ⊞ n   The spectral measure on the right is given by the following formula.
    μ r = μ ⊠ ( n − 1 n δ 0 + 1 n δ n )   We can use here the following general formula, discussed below.
    n − 1 n δ 0 + 1 n μ ⊞ n = μ ⊠ ( n − 1 n δ 0 + 1 n δ n )   Together with the above descriptions of μ l   and μ r   , this finishes the proof. □
The free probability formula used in the end of proof of Theorem 4.1 is proved by Nica and Speicher in [17] by using non-crossing partitions. A second proof is given by Voiculescu in the appendix of [17] , by using random matrices.
The proof below was already written when we learned about [17] , and this is the main reason why we include it. The other reason is that we hope that a suitable analytic function procedure can be used in order to simplify the operation A → μ ( A )   , so a complete proof of Theorem 4.1 using analytic functions is probably useful.
We use Voiculescu's R   -transform, which linearises ⊞   .
R ( μ ⊞ ν ) = R ( μ ) + R ( ν )   The R   -transform of a measure μ   is defined by introducing series G , K   as follows ([20] ).
G ( ξ ) = ξ − 1 f ( ξ − 1 ) K ∘ G = G ∘ K = i d R ( z ) = K ( z ) − 1 z   Here, as usual, f   denotes the series having as coefficients the moments of μ   .
A first remark is that both R   and S   are given, up to some normalisations, by an inversion of series. We have the following formulae connecting R   and S   .
Lemma 4.1. We have the formulae R ( z S ( z ) ) = 1 S ( z ) S ( z R ( z ) ) = 1 R ( z )   where R   and S   are the R   and S   transforms of the same measure μ   .
  • Proof. The starting point is the following formula, relating G   to ψ   .
    G ( ξ ) = 1 ξ f ( 1 ξ ) = 1 ξ + 1 ξ ψ ( 1 ξ )   We make the replacement ξ → 1 / χ ( z )   .
    G ( 1 χ ( z ) ) = χ ( z ) + χ ( z ) z   By applying K   we get a formula relating K   and χ   .
    1 χ ( z ) = K ( χ ( z ) ( 1 + z ) )   In terms of R   and S   , we get the following equality.
    1 + z z ⋅ 1 S ( z ) = K ( z S ( z ) ) = R ( z S ( z ) ) + 1 z S ( z )   This gives the first formula. For the second one, we start again with the equality relating G   to ψ   , and we make the replacement ξ → K ( z )   .
    z = 1 K ( z ) + 1 K ( z ) ψ ( 1 K ( z ) )   This can be written in the following way.
    ψ ( 1 K ( z ) ) = z K ( z ) − 1   By applying χ   we get a second formula relating K   and χ   .
    1 K ( z ) = χ ( z K ( z ) − 1 )   On the other hand, we have the following equality.
    S ( z R ( z ) ) = 1 + z R ( z ) z R ( z ) ⋅ χ ( z R ( z ) ) = K ( z ) R ( z ) ⋅ χ ( z R ( z ) )   Together with z R ( z ) = z K ( z ) − 1   , this gives the second formula. □
Theorem 4.2. We have the Nica-Speicher-Voiculescu formula n − 1 n δ 0 + 1 n μ ⊞ n = μ ⊠ ( n − 1 n δ 0 + 1 n δ n )   for any probability measure μ   on the real line.
  • Proof. We denote by μ l   and μ r   the measures on the left and on the right. Let also μ +   be the measure μ ⊞ n   , and μ δ   be the measure in the bracket.
    For any measure of type μ x   we denote by f x , G x , K x , R x , ψ x , χ x , S x   the series involved in the construction of R   and S   transforms.
    The starting point is the following equality, coming from the fact that R   linearises ⊞   .
    R + ( z ) = n R ( z )   Together with the above lemma, this gives the following formula.
    S + ( n z ) = S + ( n z S ( z ) R ( z S ( z ) ) )
    = S + ( z S ( z ) R + ( z S ( z ) ) )
    = 1 R + ( z S ( z ) )
    = 1 n R ( z S ( z ) )
    = S ( z ) n
    We use now the following identity.
    ψ + ( z ) = f + ( z ) − 1 = n ( f l ( z ) − 1 ) = n ψ l ( z )   At level of χ   functions, this translates as follows.
    χ l ( z ) = χ + ψ + χ l ( z ) = χ + ( n ψ l χ l ( z ) ) = χ + ( n z )   We have now all ingredients for computing S l   .
    S l ( z ) = 1 + z z χ l ( z )
    = 1 + z z χ + ( n z )
    = 1 + z z ⋅ n z 1 + n z S + ( n z )
    = ( 1 + z ) n 1 + n z ⋅ S ( z ) n
    = 1 + z 1 + n z S ( z )
    Proposition 4.1 shows that the right term is S δ ( z ) S ( z ) = S r ( z )   , and we are done. □

5 Colored graphs

Just as in the classical case, a natural way to get quantum permutation groups is to consider simple algebraic structures like graphs and construct their quantum automorphism groups.
Given a finite graph X   , the idea is to label its vertices 1 , … , n   , then to consider an algebra of form A ( X ) = A ( X n ) / J   , where J   is an ideal expressing preservation of edges.
This will be explained later on. For the moment we have to fix some notations regarding X   .
In previous papers [1] , [2] , [4] , [5] we use several kinds of finite graphs with edges oriented or not, colored or not plus finite metric spaces.
For the purposes of this paper, most convenient is to start with the following definition.
Definition 5.1. In this paper a colored graph X = ( V , E )   is a finite set V = X n   together with a partition E   of the form ( V × V ) − Δ V = E 1 ⊔ … ⊔ E p   where Δ V   is the diagonal of V × V   .
The terminology is of course not standard, we just use it in order to simplify presentation.
In fact colors are obviously missing, so X   should be rather called “colorable” graph. We use “colored” because most interesting examples come along with a natural coloring.
In general, we can use a color set C   , and an injective map c   assigning colors to edges.
c : { 1 , … , p } → C   We get a picture of X   in the following way. We call points elements of V   , we draw them in the plane, then we draw an oriented edge i ⃗ j   between any two points i ≠ j   and we color it c ( k )   , with k   given by ( i , j ) ∈ E k   . This kind of picture is to be called colored graph as well.
As a first example, consider a finite metric space X   . This can be regarded as a colored graph, with edges colored by their lenghts. For instance when all distances are equal, say to a ∈ ( 0 , ∞ )   , we get a monocolored graph, called simplex and denoted X n a   .
It is convenient to call simplex any monocolored graph. In case the unique color is already specified, say it is the color a   , the simplex is denoted X n a   . In case the unique color is not specified, our favorite choice will be the real number a = 0   .
The second example is with an oriented graph X = ( V , E )   . Here V = X n   is a finite set, called set of vertices, and E   is a set of oriented edges between pairs of distinct vertices.
E ⊂ V × V − Δ V   We get a partition in the following way, where E ¯   is the set of missing edges.
V × V − Δ V = E ⊔ E ¯   We can regard X   as a colored graph, with color 1   assigned to edges, and color 0   assigned to missing edges. For instance E = ∅   gives the simplex X n 0   and E ¯ = ∅   gives the simplex X n 1   .
In both the metric space and the graph example colors are complex numbers, and the matrix d i j = c ( k )   is the Laplacian of X   . This suggests the following definition.
Definition 5.2. The Laplacian of X   is the matrix given by d i i = 0   and d i j = c ( k )   with k   given by ( i , j ) ∈ E k   , where c : { 1 , … , p } → C   is a fixed injective map.
If X   comes from a metric space or from an oriented graph, or more generally if X   comes along with a natural complex coloring map c   , this map will be the one used for constructing the Laplacian, unless otherwise specified.
The fact that the Laplacian depends on the choice of the complex coloring map c   is not a problem, because all constructions in this paper do not depend on this choice. Actually, one of the reasons of presenting things this way is that we want to use independence from the choice of colors, for instance by using our favorite color a = 0   , whenever needed.
We will be interested in commutation relations of type v d = d v   , with v   magic biunitary matrix. The Stone-Weierstrass theorem shows that validity of such a commutation relation doesn't depend on the choice of c   . See Theorem 2.2 in [2] .
In other words, we can consider the ideal J m i n ⊂ A ( X n )   generated by the relations v d = d v   .
Consider also the ideal J c o m   generated by all commutation relations between v i j   's.
Proposition 5.1. We have a canonical isomorphism A ( X n ) / J m a x ≃ C ( G )   where J m a x = < J m i n , J c o m >   , and where G   is the symmetry group of X   .
  • Proof. The quotient A ( X n ) / J c o m   is canonically isomorphic to C ( S n )   , then further quotienting by relations [ v , d ] = 0   gives C ( G )   . See [2] for details. □
This result suggests to define A ( X )   to be the quotient of A ( X n )   by an ideal J   satisfying J m i n ⊂ J ⊂ J m a x   . The choice J = J m a x   is of course not very interesting. Another natural choice is J = J m i n   , used in [1] , [2] . An intermediate choice is made in [4] , [5] .
In this paper we extend and generalise results in [5] to algebras defined using J m i n   , in order to get a general formula of type A ( X * Y ) = A ( X ) * w A ( Y )   . Together with results in [2] , this will lead to a second verification of Conjecture 3.1.
Definition 5.3. The algebra A ( X )   is the quotient of A ( X n )   by the relations v d = d v   .
The pair ( A ( X ) , v )   satisfies conditions in Definition 1.3. In view of Proposition 5.1, the underlying quantum permutation group is an analogue of the automorphism group of X   .
As an example, for a simplex we can take the Laplacian to be d = 0   , so we get A ( X n )   itself.
We can see here the difference with the formalism in [4] , [5] , where the graph having n   vertices and no edges gives a different A   algebra from that of the graph having n   vertices and all possible edges. In fact, all definitions in this section are motivated by the present choice of A ( X )   .
An interesting situation is when X   is the n   -gon. For any n ≠ 4   we have A ( X ) = C ( D n )   , but for n = 4   the algebra A ( X )   is not commutative, and infinite dimensional. See [2] .
The relations defining A ( X )   might be rewritten in several convenient manners.
Proposition 5.2. The algebra A ( X )   is the quotient of A ( X n )   by the relations ∑ k , ( k , j ) ∈ E r v i k = ∑ k , ( i , k ) ∈ E r v k j   with the number r   ranging over the set { 1 , … , p }   .
  • Proof. We choose a Laplacian d   , corresponding to a complex coloring map c   . If d r   denotes the Laplacian of the oriented graph X r = ( V , E r )   , we have the following formula.
    d = ∑ r = 1 p c ( r ) d r   The matrix d r   multiplies by v   in the following way.
    ( v d r ) i j = ∑ k v i k ( d r ) k j = ∑ k , ( k , j ) ∈ E r v i k   ( d r v ) i j = ∑ k ( d r ) i k v k j = ∑ k , ( i , k ) ∈ E r v k j   This shows that the r   -th relation in the statement is equivalent to the commutation relation v d r = d r v   . On the other hand independence of A ( X )   from the choice of the Laplacian shows that v d = d v   is equivalent to v d r = d r v   for any r   , and this gives the result. □
Given two colored graphs X , Y   , we can consider the colored graph X * Y   obtained by putting a copy of X   at each vertex of Y   . In other words, we have the following definition.
Definition 5.4. Let X = ( T , E )   and Y = ( Z , F )   be two colored graphs, with E = { E 1 , … , E p }   and F = { F 1 … , F q }   . We define subsets of T × Z   times itself in the following way.
E r ∘ = { ( i α , j α ) | ( i , j ) ∈ E r , α ∈ Z }   F s ∘ = { ( i α , j β ) | i , j ∈ T , ( α , β ) ∈ F s }   These determine a colored graph X * Y   , called free product of X   and Y   .
The terminology is of course not standard, the free product of colored graphs not being a coproduct in a categorical sense. We call it like this because it is expected to be compatible with the planar algebra free product *   of Bisch and Jones [10] .
As a first example, consider a free product of s   simplices.
Z = Y 1 ɛ 1 * … * Y s ɛ s   As pointed out in [2] , we have a nice interpretation of Z   if we choose the corresponding s   colors to be an increasing sequence of infinitesimals.
ɛ 1 < < ɛ 2 < < … < < ɛ s   The free product is obtained by starting with Y s   , then putting a copy of Y s − 1   at each vertex of Y s   , a copy of Y s − 2   at each vertex of Y s − 1   , and so on until Y 1   . What we get is a kind of metric space, by using the infinitesimal summing conventions ɛ i + ɛ j = ɛ i   for i > j   .
A simplex is called generic if it has n ≥ 4   vertices. The terminology comes from the proof below, where numbers n   become Jones indices, called generic when bigger than 4   .
Theorem 5.1. If Z   is a free product of s   generic simplices then μ ( A ( Z ) ) = η ⊠ s   where η   is the free Poisson law of parameter 1   .
  • Proof. It is shown in [2] that the corresponding s   Laplacians satisfy Landau's exchange relations in [15] . This shows that the planar algebra associated to A ( Z )   is a Fuss-Catalan algebra on s   colors, whose Poincaré series is computed in the generic case by Bisch and Jones in [6] .
    f ( z ) = ∑ k = 0 ∞ 1 s k + 1 ( ( s + 1 ) k k ) z k   As pointed out in [7] , this series is a solution of the following equation.
    f ( z ) = 1 + z f ( z ) s + 1   This can be used for computing the S   -transform of the corresponding spectral measure.
    f ( z ) = 1 + z f ( z ) s + 1 ⇒ ψ ( z ) = z ( 1 + ψ ( z ) ) s + 1
    ⇒ z = χ ( z ) ( 1 + z ) s + 1
    ⇒ χ ( z ) = z ( 1 + z ) s + 1
    ⇒ S ( z ) = 1 ( 1 + z ) s
    With s = 1   this gives the S   -transform of η 4 + = η   . Now back to arbitrary s   , we get the following equality.
    S ( z ) = ( 1 1 + z ) s = ( S η ( z ) ) s   The result follows from the fact that log S   linearises ⊠   . □

6 Free products

The purpose of this section is to establish the formula A ( X * Y ) = A ( X ) * w A ( Y )   . This will be done via a modification plus generalisation of a proof in [5] , where free wreath products are constructed, and where a first such decomposition result is found.
The idea is to construct a pair of inverse morphisms, by using universal properties of various algebras involved. The morphism from left to right is easy to construct, and this is done in proof of Theorem 6.1 below. In the other sense, we have first to construct inside A ( X * Y )   analogues U , V   of matrices u , v   , and this is the purpose of next two lemmas.
The magic biunitary matrix associated to A ( X * Y )   is denoted W i α , j β   . Here double indices i α , j β ∈ T × Z   are produced by indices i , j ∈ T   and α , β ∈ Z   , coming from Definition 5.4.
Lemma 6.1. We can define an element V α β   by the formula V α β = ∑ k W i α , k β = ∑ k W k α , j β   for any i , j   , and the resulting matrix V   is a magic biunitary.
  • Proof. The relations in Proposition 5.2 are written in the following way.
    ∑ k , ( k , j ) ∈ E r W i α , k β = ∑ k , ( i , k ) ∈ E r W k α , j β   ∑ k , γ , ( γ , β ) ∈ F s W i α , k γ = ∑ k , γ , ( α , γ ) ∈ F s W k γ , j β   The equality in the statement is obtained from these relations.
    ∑ k W i α , k β = ∑ r ∑ k , ( k , j ) ∈ E r W i α , k β = ∑ r ∑ k , ( i , k ) ∈ E r W k α , j β = ∑ k W k α , j β   The entries of V   are easily seen to be self-adjoint.
    V α β * = ∑ i ( W i α , j β ) * = ∑ i W i α , j β = V α β   We check now the conditions regarding sums on rows and columns. ∑ α V α β = ∑ i α W i α , j β = 1   ∑ β V α β = ∑ j β W i α , j β = 1   The fact that rows of V   are partitions of unity is proved as follows.
    V α β V α γ = ( ∑ j W i α , j β ) ( ∑ k W i α , k γ )
    = ∑ j k W i α , j β W i α , k γ
    = δ β γ ∑ j W i α , j β
    = δ β γ V α β
    A similar computation gives the following formula, valid for any α ≠ γ   .
    V α β V γ β = ( ∑ i W i α , j β ) ( ∑ k W k γ , j β ) = ∑ i k W i α , j β W k γ , j β = 0   Thus entries of V   are orthogonal on each column, and this finishes the proof. □
Lemma 6.2. For any α   the matrix U i j α = ∑ β W i α , j β   is a magic biunitary.
  • Proof. The entries of U   are easily seen to be self-adjoint.
    ( U i j α ) * = ∑ β ( W i α , j β ) * = ∑ β W i α , j β = U i j α   We check now the conditions regarding sums on rows and columns.
    ∑ j U i j α = ∑ j β W i α , j β = 1   ∑ i U i j α = ∑ i β W i α , j β = ∑ β V α β = 1   From the fact that W   is magic we get that all rows of U   are partitions of unity. U i j α U i k α = ∑ β γ W i α , j β W i α , k γ = δ j k ∑ β W i α , j β = δ j k U i j α   Also, since V   is magic we get the following identity, valid for any β ≠ γ   .
    W i α , j β W k α , j γ = W i α , j β ( ∑ r W r α , j β ) ( ∑ s W s α , j γ ) W k α , j γ
    = W i α , j β V α β V α γ W k α , j γ
    = 0
    This gives the following formula, valid for any i ≠ k   .
    U i j α U k j α = ∑ β γ W i α , j β W k α , j γ = ∑ β W i α , j β W k α , j β = 0   Thus entries of U   are orthogonal on each column, and this finishes the proof. □
Theorem 6.1. We have a canonical isomorphism A ( X * Y ) = A ( X ) * w A ( Y )   for any two colored graphs X   and Y   .
  • Proof. We use the first assertion in Lemma 3.1. What is left to do is to construct morphisms of C *   -algebras from left to right and from right to left, making W i α , j β   correspond to w i α , j β   . These two morphisms will be inverse Hopf C *   -algebra isomorphisms.
    “ →   ”. The matrix w   being a magic biunitary, we just have to prove that it commutes with the Laplacian of X * Y   . For, we use relations in Proposition 5.4, which for X * Y   correspond to the first two formulae in proof of Lemma 6.1. The first one is checked as follows.
    ∑ k , ( k , j ) ∈ E r w i α , k β = ∑ k , ( k , j ) ∈ E r u i k ( α ) v α β = ∑ k , ( i , k ) ∈ E r u k j ( α ) v α β = ∑ k , ( i , k ) ∈ E r w k α , j β   As for the second relation, this is checked as follows.
    ∑ k , γ , ( γ , β ) ∈ F s w i α , k γ = ∑ k , γ , ( γ , β ) ∈ F s u i k ( α ) v α γ = ∑ γ , ( γ , β ) ∈ F s v α γ   = ∑ γ , ( α , γ ) ∈ F s v γ β = ∑ k , γ , ( α , γ ) ∈ F s u k j ( γ ) v γ β = ∑ k , γ , ( α , γ ) ∈ F s w k γ , j β   “ ←   ” The matrices U , V   being magic biunitaries, we just have to prove that they satisfy the same relations as u , v   . First is commutation of U   with the Laplacian of X   . ∑ k , ( k , j ) ∈ E r U i k α = ∑ β , k , ( k , j ) ∈ E r W i α , k β = ∑ β , k , ( i , k ) ∈ E r W k α , j β = ∑ k , ( i , k ) ∈ E r U k j α   Second comes commutation of V   with the Laplacian of Y   .
    ∑ γ , ( γ , β ) ∈ F s V α γ = ∑ k ∑ γ , ( γ , β ) ∈ F s W i α , k γ
    = ∑ k ∑ γ , ( α , γ ) ∈ F s W k γ , j β
    = ∑ γ , ( α , γ ) ∈ F s V γ β
    Finally, the commutation condition defining free wreath products is checked as follows.
    U i j α V α β = ∑ γ W i α , j γ V α β = ∑ γ k W i α , j γ W i α , k β = W i α , j β   V α β U i j α = V α β ∑ γ W i α , j γ = ∑ γ k W i α , k β W i α , j γ = W i α , j β   Thus we have an arrow from right to left, and this finishes the proof. □
As a first application, we get a second verification of Conjecture 3.1.
Corollary 6.1. We have the formula μ ( A ( X ) * w A ( Y ) ) = μ ( A ( X ) ) ⊠ μ ( A ( Y ) )   for any two free products of generic simplices X   and Y   .
  • Proof. This follows by combining Theorems 5.1 and 6.1. □
The genericity assumption in this statement can actually be removed. One way is by using the above proof, with the formulae for generic indices in Theorem 5.1 and its proof replaced by formulae for arbitrary indices, coming from [6] , [7] . The other way is by using the computation in the end of section 3, together with the fact that a free product of arbitrary Fuss-Catalan planar algebras is a Fuss-Catalan planar algebra ([10] ).

7 Disconnected graphs

In order to include the disjoint sum operation in the framework of previous section, we work here with slightly more general graphs.
Definition 7.1. A precolored graph X = ( V , E )   is a finite set V = X n   together with a set E = { E 1 , … , E p }   of disjoint subsets of V × V − Δ V   .
Any colored graph can be regarded as a precolored graph. Conversely, for a precolored graph X = ( V , E )   with E = { E 1 , … , E p }   , let E p + 1   be the set of of missing edges.
V × V − Δ V = E 1 ⊔ … ⊔ E p ⊔ E p + 1   This partition is denoted E ¯   , and defines a colored graph X ¯ = ( V , E ¯ )   . We define the Laplacian of X   to be that of X ¯   , and the Hopf algebra associated to X   to be that associated to X ¯   .
A ( X ) = A ( X ¯ )   The construction of free products makes sense for precolored graphs, with the same definition, and the resulting objects are precolored graphs. However, we cannot expect Theorem 6.1 to hold in general. For instance this not the case when X = X n ∅   is the graph without edge. On the other hand, for Y = X n ∅   the free product X * Y   is the disjoint union of n   copies of X   .
X * Y = X ⊔ … ⊔ X   When X   is connected a free wreath product decomposition of type A ( X * Y ) = A ( X ) * w A ( Y )   is found in [5] . We extend now this result to algebras A ( X )   defined as in this paper.
Definition 7.2. A precolored graph X = ( V , E )   with E = { E 1 , … , E p }   is called connected if the oriented graph Y = ( V , F )   given by F = p ⋃ i = 1 E i   is a connected in the usual sense.
In this definition connectedness of a usual oriented graph Y   means that any two vertices i , j   can be joined by a path of oriented edges, regardless of edge orientations.
We use the following simple fact regarding connectedness.
Lemma 7.1. If X = ( V , E )   with V = X m   is a connected oriented graph, the *   -algebra generated by its Laplacian d ∈ M m ( C )   contains a matrix having nonzero entries.
  • Proof. For any i , j   consider a sequence of vertices realising a path from i   to j   .
    i = k 0 , k 1 , … , k n , k n + 1 = j   For any t   we have ( k t , k t + 1 ) ∈ F   or ( k t + 1 , k t ) ∈ F   . This means that we have d k t k t + 1 = 1   or d k t + 1 k t = 1   , so the ( k t , k t + 1 )   entry of the matrix d   or of the matrix d *   is equal to 1   .
    d k t k t + 1 e t = 1   Here each exponent e t   is either 1   or *   . We multiply now all these equalities.
    d k 0 k 1 e 0 … d k n k n + 1 e n = 1   This term contributes to the ( i j )   entry of d e 0 … d e n   , so we get the following inequality.
    ( d e 0 … d e n ) i j ≥ 1   Consider now a sum of such matrices d e 0 … d e n   , one for each choice of i , j   . This is a matrix in the *   -algebra generated by d   , having all entries bigger than 1   . □
Proposition 7.1. If X   is a connected precolored graph we have the equality A ( X ¯ * Y ) = A ( X * Y )   for any precolored graph Y   .
  • Proof. We use the notations X = ( X m , E )   and Y = ( X n , F )   with E = { E 1 , … , E p }   and F = { F 1 … , F q }   , as in Definition 5.4. For any r   the Laplacian of the oriented graph ( X m × X n , E r ∘ )   is d r ⊗ 1 n   , where d r   is the Laplacian of ( X m , E r )   and 1 n ∈ M n ( C )   is the identity matrix. Also for any s   the Laplacian of the oriented graph ( X n × X n , F s ∘ )   is I m ⊗ δ s   , where I m ∈ M m ( C )   is the matrix having 1   as entries and δ s   is the Laplacian of ( X n , F s )   .Consider the universal magic biunitary matrix w ∈ M m n ( A ( X m n ) )   . Then w   commutes with the Laplacian of X * Y   if and only if it commutes with the following matrices.
    d r ⊗ 1 n , I m ⊗ δ s , r = 1 , … , p , s = 1 … q ( ◆ )   Also w   commutes with the Laplacian of X ¯ * Y   if only if it commutes with matrices ( ◆ )   and with the following matrix.
    ( I m − ∑ i = 1 r d i ) ⊗ 1 n   So assume that w   commutes with the family ( ◆   ) of matrices, and put d = ∑ i = 1 r d i   . Then w   commutes with d ⊗ 1 n   , and being unitary, it also commutes with d * ⊗ 1 n   . By the previous lemma, there exists a non-commutative polynomial P ( x , y )   such that a = P ( d , d * ) ∈ M m ( C )   is a matrix having nonzero entries. Consider now the following matrix.
    P ( d ⊗ 1 n , d * ⊗ 1 n ) = P ( d , d * ) ⊗ 1 n = a ⊗ 1 n   Then w   commutes with a ⊗ 1 n   . We can regard the matrix a ⊗ 1 n   as being the Laplacian of a colored graph. By identifying all nonzero colors in this graph, we the following implication.
    [ w , a ⊗ 1 n ] = 0 ⇒ [ w , I m ⊗ 1 n ] = 0   Therefore w   commutes with ( I m − d ) ⊗ 1 n   , and we get the result. □
Theorem 7.1. If X   is a connected precolored graph we have an isomorphism A ( X * Y ) = A ( X ) * w A ( Y )   for any precolored graph Y   .
  • Proof. In proof of Theorem 6.1 we have used the fact that X   is a colored graph (in the proof of Lemma 6.1) but we have never used the fact that Y   is colored. So we have A ( X ¯ * Y ) = A ( X ) * w A ( Y )   , and therefore Proposition 7.1 applies and concludes the proof. □
With a little more work one can verify that the general formula A ( X * Y ) = A ( X ) * w A ( Y )   holds as well for algebras A ( X )   constructed as in [4] , so we have a generalisation of Theorem 4.2 in [4] . On the other hand, the algebra A ( X )   from [4] is expected to be of form A ( X ~ )   , with A   constructed in the spirit of this paper, and with X ~   being a higher combinatorial structure associated to X   , having same symmetry group as X   . Thus we have evidence for more general decomposition results of type A ( X * Y ) = A ( X ) * w A ( Y )   .
As explained in section 3, useful here would be such a formula with X , Y   subalgebras of spin planar algebras, because this would imply Conjecture 3.1.
Corollary 7.1. If Z   is an homogeneous precolored graph we have the equality A ( Z ) = A ( X ) * w A ( X n )   where X   is a connected component of Z   , and n   is the number of components.
  • Proof. We have Z = X ⊔ … ⊔ X   , and Theorem 7.1 applies. □
Together with Conjecture 3.1 and with Voiculescu's S   -transform technique, this result reduces computation of μ ( A ( Z ) )   for arbitrary homogeneous graphs to that of μ ( A ( Z ) )   for connected homogeneous graphs. Indeed, we have the following computation.
μ ( A ( Z ) ) = μ ( A ( X ) * w A ( X n ) )
= μ ( A ( X ) ) ⊠ μ ( A ( X n ) )
= μ ( A ( X ) ) ⊠ η n
Here all equalities are true, except maybe for the second one, which follows from Theorem 4.1 for n = 2   , and from Conjecture 3.1 for n ≥ 3   .
It is probably useful here to compute the S   -transform of η n   .
Proposition 7.2. The S   -transform of η n   is given by S 2 ( z ) = 1 + z 1 + 2 z   S 3 ( z ) = 2 + 2 z 1 + 4 z + 1 + 4 z 2   S 4 + ( z ) = 1 1 + z   where 4 +   denotes any number n ≥ 4   .
  • Proof. The first formula follows the equality A ( X 2 ) = C ( S 2 )   and from Proposition 4.1. For A ( X 3 ) = C ( S 3 )   we use the Poincaré series in proof of Theorem 2.2. Substacting 1   gives ψ   .
    ψ ( z ) = 1 6 ( 2 + 3 1 − z + 1 1 − 3 z ) − 1
    = 1 6 ( ( 3 1 − z − 4 ) + 1 1 − 3 z )
    = 1 6 ( 4 z − 1 1 − z + 1 1 − 3 z )
    = 1 6 ⋅ 4 z − 1 − 12 z 2 + 3 z + 1 − z ( 1 − z ) ( 1 − 3 z )
    = z − 2 z 2 1 − 4 z + 3 z 2
    Thus χ = χ ( z )   satisfies the following equation.
    z = χ − 2 χ 2 1 − 4 χ + 3 χ 2   z − 4 z χ + 3 z χ 2 = χ − 2 χ 2   ( 2 + 3 z ) χ 2 − ( 1 + 4 z ) χ + z = 0   Together with χ ( 0 ) = 0   , this equation gives the formula of χ   .
    Δ = 1 + 16 z 2 + 8 z − 8 z − 12 z 2   χ ( z ) = 1 + 4 z − 1 + 4 z 2 2 ( 2 + 3 z )   This gives the formula in the statement.
    S ( z ) = 1 + z z ⋅ 1 + 4 z − 1 + 4 z 2 2 ( 2 + 3 z )
    = 1 + z 4 z + 6 z 2 ⋅ 1 + 16 z 2 + 8 z − 1 − 4 z 2 1 + 4 z + 1 + 4 z 2
    = 1 + z 4 z + 6 z 2 ⋅ 8 z + 12 z 2 1 + 4 z + 1 + 4 z 2
    = 2 + 2 z 1 + 4 z + 1 + 4 z 2
    The last formula follows from proof of Theorem 5.1. □
The formula of S 3   looks quite complicated, when compared to those of S 2   and S 4 +   . It is tempting to get rid of the square root, with the following change of variables.
Proposition 7.3. The S   -transform of η n   is given by S 2 ( q 1 − q 2 ) = 1 + q − q 2 1 + 2 q − q 2   S 3 ( q 1 − q 2 ) = 1 + q − q 2 1 + 2 q   S 4 + ( q 1 − q 2 ) = 1 − q 2 1 + q − q 2   where 4 +   denotes any number n ≥ 4   .
  • Proof. The first and third formula are obtained as follows.
    S 2 ( q 1 − q 2 ) = 1 + q 1 − q 2 1 + 2 q 1 − q 2 = 1 + q − q 2 1 + 2 q − q 2   S 4 + ( q 1 − q 2 ) = 1 1 + q 1 − q 2 = 1 − q 2 1 + q − q 2   For the second one, we compute first the square root.
    1 + 4 ( q 1 − q 2 ) 2 = 1 1 − q 2 1 + q 4 − 2 q 2 + 4 q 2 = 1 + q 2 1 − q 2   This gives the following formula.
    S 3 ( q 1 − q 2 ) = 2 + 2 q 1 − q 2 1 + 4 q 1 − q 2 + 1 + q 2 1 − q 2 = 2 − 2 q 2 + 2 q 1 − q 2 + 4 q + 1 + q 2   After simplification we get the formula in the statement. □

8 Small graphs

This is a technical section, using terminology and results from [1] , [2] . We will be concerned with unoriented colored graphs X = ( V , E )   . Such a graph corresponds to an oriented colored graph, when replacing each edge ( i j )   by the pair of oriented edges i ⃗ j   and j ⃗ i   .
The classification of homogeneous unoriented colored graphs with small number of vertices was started in [1] , with a complete result for graphs having n ≤ 7   vertices. The next step was to investigate the case n = 8   . A complete result is obtained in [2] in the bicolored case, with the remark that in the arbitrary case there is just one graph left. This is the graph formed by two rectangles, which can be investigated by using techniques in this paper.
In other words, we have now complete results for all homogeneous unoriented colored graphs with n ≤ 8   vertices. We provide here the list of all measures appearing from such graphs.
First is the dihedral series of graphs, corresponding to the case A ( X ) = C ( D m )   . This is known to contain all n   -gons with n ≠ 4   , a certain tricolored octogon corresponding to the missing group D 4   , plus some other graphs, like the 8   -spoke wheel. See [1] , [2] .
Proposition 8.1. The spectral measure of C ( D m )   is given by d 2 k = 1 4 k ( ( 3 k − 1 ) δ 0 + k δ 2 + δ 2 k )   d 2 k + 1 = 1 4 k + 2 ( 2 k δ 0 + ( 2 k + 1 ) δ 1 + δ 2 k + 1 )   where k   is such that m = 2 k   or m = 2 k + 1   .
  • Proof. This follows from Proposition 2.1, see [2] for details. □
The other series is the Fuss-Catalan one. This contains many graphs, see [1] , [2] . The spectral measures here appear as free multiplicative convolutions between Temperley-Lieb measures in Theorem 2.2, and can be written in the following way.
η a b c = η 2 ⊠ a ⊠ η 3 ⊠ b ⊠ η 4 + ⊠ c   We don't know how to compute this measure in the general case. We just have the following formula for the corresponding S   -transform.
Proposition 8.2. The S   -transform of the Fuss-Catalan measure η a b c   is given by S a b c ( q 1 − q 2 ) = ( 1 − q 2 ) c ( 1 + 2 q ) b ⋅ ( 1 + q − q 2 ) d ( 1 + 2 q − q 2 ) a   where d   is such that a + b = c + d   .
  • Proof. We use Proposition 7.3, and the fact that log S   linearises ⊠   .
    S a b c ( q 1 − q 2 ) = S 2 ( q 1 − q 2 ) a S 3 ( q 1 − q 2 ) b S 4 + ( q 1 − q 2 ) c
    = ( 1 + q − q 2 1 + 2 q − q 2 ) a ( 1 + q − q 2 1 + 2 q ) b ( 1 − q 2 1 + q − q 2 ) c
    After rearranging terms, we get the formula in the statement. □
After removing all dihedral and Fuss-Catalan graphs, there are just three graphs left. These are the cube, the rectangle, and the two rectangles. See [1] , [2] .
Proposition 8.3. The spectral measure of the cube is given by d μ ( x ) = 1 8 π 8 x − x 2 d x   on [ 0 , 8 ]   , and d μ ( x ) = 0   elsewhere.
  • Proof. The Poincaré series of the cube is computed in [2] . The series is expressed there as a sum, which is summed as follows.
    f ( z ) = 1 + ∑ k = 1 ∞ 2 k − 1 k + 1 ( 2 k k ) z k
    = 1 + 1 2 ∑ k = 1 ∞ 1 k + 1 ( 2 k k ) ( 2 z ) k
    = 1 2 ( 1 + ∑ k = 0 ∞ 1 k + 1 ( 2 k k ) ( 2 z ) k )
    = 1 2 ( 1 + 1 − 1 − 8 z 4 z )
    = 1 + 4 z − 1 − 8 z 8 z
    In this computation the fourth equality is easy to check, and corresponds to a well-known property of the Poincaré series of T L ( 4 + )   . We can compute now G ( ξ ) = ξ − 1 f ( ξ − 1 )   .
    G ( ξ ) = ξ + 4 − ξ 2 − 8 ξ 8   The Stieltjes formula applies, and gives the measure in the statement. □
Proposition 8.4. The spectral measure of a rectangle is given by μ = 1 4 ( 3 δ 0 + δ 4 )   and the associated universal Hopf algebra is A = C ( Z 2 × Z 2 )   .
  • Proof. The second assertion is from [1] , and the first one follows from Proposition 4.1. □
Proposition 8.5. The spectral measure of the graph formed by two rectangles is given by d μ ( x ) = 1 2 δ 0 + 1 π ⋅ − 4 + 8 x − x 2 8 x − x 2 d x   on [ 4 − 12 , 4 + 12 ]   , and d μ ( x ) = 0   elsewhere.
  • Proof. The graph R ⊔ R   formed by two rectangles can be investigated by using Corollary 7.1, Theorem 4.1 and Proposition 8.4. We get the following spectral measure.
    μ = μ ( A ( R ⊔ R ) )
    = μ ( A ( R ) * w A ( X 2 ) )
    = μ ( C ( Z 2 × Z 2 ) * w μ ( C ( Z 2 ) ) )
    = μ ( C ( Z 2 × Z 2 ) ) ⊠ μ ( C ( Z 2 ) )
    Now both Z 2 × Z 2   and Z 2   being groups acting on themselves, the corresponding S   -transforms are given by the formula in Proposition 4.1. This gives the S   -transform of μ   .
    S ( z ) = 1 + z 1 + 4 z ⋅ 1 + z 1 + 2 z   We can compute the χ   -transform, then the Poincaré series.
    χ ( z ) = z ( 1 + z ) ( 1 + 4 z ) ( 1 + 2 z )   z = ( f − 1 ) f ( 1 + 4 f − 4 ) ( 1 + 2 f − 2 )   f 2 − f = z ( 4 f − 3 ) ( 2 f − 1 )   ( 8 z − 1 ) f 2 − ( 10 z − 1 ) f + 3 z = 0   Together with f ( 0 ) = 1   , this equation gives the formula of f   .
    Δ = 100 z 2 − 20 z + 1 − 96 z 2 + 12 z   f ( z ) = 10 z − 1 − 4 z 2 − 8 z + 1 16 z − 2   We compute now the Cauchy transform G ( ξ ) = ξ − 1 f ( ξ − 1 )   .
    G ( ξ ) = 10 ξ − 1 − 1 − 4 ξ − 2 − 8 ξ − 1 + 1 ξ ( 16 ξ − 1 − 2 )
    = 10 − ξ − 4 − 8 ξ + ξ 2 16 ξ − 2 ξ 2
    = 10 − ξ − ( ξ − 4 ) 2 − 12 2 ξ ( 8 − ξ )
    This function has a pole at ξ = 0   with residue 1 / 2   , and the square root is imaginary for ξ ∈ [ 4 − 12 , 4 + 12 ]   . The Stieltjes formula applies, and gives the following measure.
    d μ ( x ) = 1 2 δ 0 + 1 π ⋅ 12 − ( x − 4 ) 2 2 x ( 8 − x ) d x   This gives the formula in the statement. □
The next challenging graph, mentioned in [2] , is the discrete torus at n = 9   .
References

  1. T. Banica, Quantum automorphism groups of small metric spaces, math.QA/0304025.
  2. T. Banica, Quantum automorphism groups of homogeneous graphs, math.QA/0311402.
  3. T. Banica and S. Moroianu, On the structure of quantum permutation groups, math.QA/0411576.
  4. J. Bichon, Quantum automorphism groups of finite graphs, Proc. Amer. Math. Soc. 131 (2003), 665–673.
  5. J. Bichon, Free wreath product by the quantum permutation group, Alg. Rep. Theory 7 (2004), 343–362.
  6. D. Bisch and V.F.R. Jones, Algebras associated to intermediate subfactors, Invent. Math. 128 (1997), 89–157.
  7. D. Bisch and V.F.R. Jones, A note on free composition of subfactors, in “Geometry and Physics”, Aarhus, 1995, Lecture Notes in Pure and Appl. Math. 184 (1997), 339–361.
  8. D. Bisch and V.F.R. Jones, Singly generated planar algebras of small dimension, Duke Math. J. 101 (2000), 41–75.
  9. D. Bisch and V.F.R. Jones, Singly generated planar algebras of small dimension II, Adv. Math. 175 (2003), 297–318.
  10. D. Bisch and V.F.R. Jones, In preparation.
  11. V.F.R. Jones, Planar algebras I, math.QA/9909027.
  12. V.F.R. Jones, The planar algebra of a bipartite graph, in “Knots in Hellas '98”, World Sci. Publishing (2000), 94–117.
  13. V.F.R. Jones, The annular structure of subfactors, in “Essays on geometry and related topics”, Monogr. Enseign. Math. 38 (2001), 401–463.
  14. V. Kodiyalam and V.S. Sunder, A complete set of numerical invariants for a subfactor, J. Funct. Anal. 212 (2004), 1–27.
  15. Z. Landau, Exchange relation planar algebras, Geometriae Dedicata 95 (2002), 183–214.
  16. V.A. Marchenko and L.A. Pastur, Distribution of eigenvalues in certain sets of random matrices, Mat. Sb. 72 (1967), 507–536.
  17. A. Nica and R. Speicher, On the multiplication of free N-tuples of noncommutative random variables, Amer. J. Math. 118 (1996), 799–837.
  18. R. Vergnioux, K-amenability for amalgamated free products of amenable discrete quantum groups, J. Funct. Anal. 212 (2004), 206–221.
  19. R. Vergnioux, The property of rapid decay for discrete quantum groups, preprint.
  20. D. Voiculescu, Addition of certain noncommuting random variables, J. Funct. Anal. 66 (1986), 323–346.
  21. D. Voiculescu, Multiplication of certain noncommuting random variables, J. Operator Theory 18 (1987), 223–235.
  22. D. Voiculescu, Lectures on free probability theory, in “Lectures on probability theory and statistics”, Saint-Flour 1998, Lecture Notes in Math. 1738 (2000), 279–349.
  23. D. Voiculescu, K. Dykema and A. Nica, Free random variables, CRM Monograph Series 1, AMS (1993).
  24. S. Wang, Quantum symmetry groups of finite spaces, Comm. Math. Phys. 195 (1998), 195–211.
  25. S.L. Woronowicz, Compact matrix pseudogroups, Comm. Math. Phys. 111 (1987), 613–665.
  26. S.L. Woronowicz, Tannaka-Krein duality for compact matrix pseudogroups. Twisted SU(N) groups, Invent. Math. 93 (1988), 35–76.

Departement de Mathematiques, Universite Paul Sabatier, 118 route de Narbonne, 31062 Toulouse, France E-mail address : banica@picard.ups-tlse.fr Laboratoire de Mathematiques Appliquees, Universite de Pau et des Pays de l'Adour, IPRA, Avenue de l'universite, 64000 Pau, France E-mail address : bichon@univ-pau.fr