13d. Partitions, easiness

[math] \newcommand{\mathds}{\mathbb}[/math]

This article was automatically generated from a tex file and may contain conversion errors. If permitted, you may login and edit this article to improve the conversion.

In order to study the quantum permutation group [math]S_N^+[/math], we use representation theory. Things here are quite long and advanced, and for full details on what follows, you can check my book . We will need the following version of Tannakian duality:

Theorem

The following operations are inverse to each other:

• The construction [math]A\to C[/math], which associates to any Woronowicz algebra [math]A[/math] the tensor category formed by the intertwiner spaces [math]C_{kl}=Hom(u^{\otimes k},u^{\otimes l})[/math].
• The construction [math]C\to A[/math], which associates to a tensor category [math]C[/math] the Woronowicz algebra [math]A[/math] presented by the relations [math]T\in Hom(u^{\otimes k},u^{\otimes l})[/math], with [math]T\in C_{kl}[/math].

Show Proof

This is something quite deep, going back to Woronowicz's paper in a slightly different form, with the idea being as follows:

(1) We have indeed a construction [math]A\to C[/math] as above, whose output is a tensor [math]C^*[/math]-subcategory with duals of the tensor [math]C^*[/math]-category of Hilbert spaces.

(2) We have as well a construction [math]C\to A[/math] as above, simply by dividing the free [math]*[/math]-algebra on [math]N^2[/math] variables by the relations in the statement.

Regarding now the bijection claim, some elementary algebra shows that [math]C=C_{A_C}[/math] implies [math]A=A_{C_A}[/math], and also that [math]C\subset C_{A_C}[/math] is automatic. Thus we are left with proving [math]C_{A_C}\subset C[/math]. But this latter inclusion can be proved indeed, by doing some algebra, and using von Neumann's bicommutant theorem, in finite dimensions. See .

■

We will need as well, following the classical work of Weyl, Brauer and many others, the notion of “easiness”. Let us start with the following definition:

Definition

Let [math]P(k,l)[/math] be the set of partitions between an upper row of [math]k[/math] points, and a lower row of [math]l[/math] points. A set [math]D=\bigsqcup_{k,l}D(k,l)[/math] with [math]D(k,l)\subset P(k,l)[/math] is called a category of partitions when it has the following properties:

• Stability under the horizontal concatenation, [math](\pi,\sigma)\to[\pi\sigma][/math].
• Stability under the vertical concatenation, [math](\pi,\sigma)\to[^\sigma_\pi][/math].
• Stability under the upside-down turning, [math]\pi\to\pi^*[/math].
• Each set [math]P(k,k)[/math] contains the identity partition [math]||\ldots||[/math].
• The set [math]P(0,2)[/math] contains the semicircle partition [math]\cap[/math].

As a basic example, we have the category of all partitions [math]P[/math] itself. Other basic examples include the category of pairings [math]P_2[/math], or the categories [math]NC,NC_2[/math] of noncrossing partitions, and pairings. There are many other examples, and we will be back to this.

The relation with the Tannakian categories and duality comes from:

Proposition

Each [math]\pi\in P(k,l)[/math] produces a linear map [math]T_\pi:(\mathbb C^N)^{\otimes k}\to(\mathbb C^N)^{\otimes l}[/math],

[[math]] T_\pi(e_{i_1}\otimes\ldots\otimes e_{i_k})=\sum_{j_1\ldots j_l}\delta_\pi\begin{pmatrix}i_1&\ldots&i_k\\ j_1&\ldots&j_l\end{pmatrix}e_{j_1}\otimes\ldots\otimes e_{j_l} [[/math]]

with the Kronecker type symbols [math]\delta_\pi\in\{0,1\}[/math] depending on whether the indices fit or not. The assignement [math]\pi\to T_\pi[/math] is categorical, in the sense that we have

[[math]] T_\pi\otimes T_\sigma=T_{[\pi\sigma]}\quad,\quad T_\pi T_\sigma=N^{c(\pi,\sigma)}T_{[^\sigma_\pi]}\quad,\quad T_\pi^*=T_{\pi^*} [[/math]]

where [math]c(\pi,\sigma)[/math] are certain integers, coming from the erased components in the middle.

Show Proof

The concatenation axiom follows from the following computation:

[[math]] \begin{eqnarray*} &&(T_\pi\otimes T_\sigma)(e_{i_1}\otimes\ldots\otimes e_{i_p}\otimes e_{k_1}\otimes\ldots\otimes e_{k_r})\\ &=&\sum_{j_1\ldots j_q}\sum_{l_1\ldots l_s}\delta_\pi\begin{pmatrix}i_1&\ldots&i_p\\j_1&\ldots&j_q\end{pmatrix}\delta_\sigma\begin{pmatrix}k_1&\ldots&k_r\\l_1&\ldots&l_s\end{pmatrix}e_{j_1}\otimes\ldots\otimes e_{j_q}\otimes e_{l_1}\otimes\ldots\otimes e_{l_s}\\ &=&\sum_{j_1\ldots j_q}\sum_{l_1\ldots l_s}\delta_{[\pi\sigma]}\begin{pmatrix}i_1&\ldots&i_p&k_1&\ldots&k_r\\j_1&\ldots&j_q&l_1&\ldots&l_s\end{pmatrix}e_{j_1}\otimes\ldots\otimes e_{j_q}\otimes e_{l_1}\otimes\ldots\otimes e_{l_s}\\ &=&T_{[\pi\sigma]}(e_{i_1}\otimes\ldots\otimes e_{i_p}\otimes e_{k_1}\otimes\ldots\otimes e_{k_r}) \end{eqnarray*} [[/math]]

The composition axiom follows from the following computation:

[[math]] \begin{eqnarray*} &&T_\pi T_\sigma(e_{i_1}\otimes\ldots\otimes e_{i_p})\\ &=&\sum_{j_1\ldots j_q}\delta_\sigma\begin{pmatrix}i_1&\ldots&i_p\\j_1&\ldots&j_q\end{pmatrix} \sum_{k_1\ldots k_r}\delta_\pi\begin{pmatrix}j_1&\ldots&j_q\\k_1&\ldots&k_r\end{pmatrix}e_{k_1}\otimes\ldots\otimes e_{k_r}\\ &=&\sum_{k_1\ldots k_r}N^{c(\pi,\sigma)}\delta_{[^\sigma_\pi]}\begin{pmatrix}i_1&\ldots&i_p\\k_1&\ldots&k_r\end{pmatrix}e_{k_1}\otimes\ldots\otimes e_{k_r}\\ &=&N^{c(\pi,\sigma)}T_{[^\sigma_\pi]}(e_{i_1}\otimes\ldots\otimes e_{i_p}) \end{eqnarray*} [[/math]]

Finally, the involution axiom follows from the following computation:

[[math]] \begin{eqnarray*} &&T_\pi^*(e_{j_1}\otimes\ldots\otimes e_{j_q})\\ &=&\sum_{i_1\ldots i_p} \lt T_\pi^*(e_{j_1}\otimes\ldots\otimes e_{j_q}),e_{i_1}\otimes\ldots\otimes e_{i_p} \gt e_{i_1}\otimes\ldots\otimes e_{i_p}\\ &=&\sum_{i_1\ldots i_p}\delta_\pi\begin{pmatrix}i_1&\ldots&i_p\\ j_1&\ldots& j_q\end{pmatrix}e_{i_1}\otimes\ldots\otimes e_{i_p}\\ &=&T_{\pi^*}(e_{j_1}\otimes\ldots\otimes e_{j_q}) \end{eqnarray*} [[/math]]

Summarizing, our correspondence is indeed categorical.

■

In relation with the quantum groups, we have the following notion:

Definition

A compact quantum matrix group [math]G[/math] is called easy when

[[math]] Hom(u^{\otimes k},u^{\otimes l})=span\left(T_\pi\Big|\pi\in D(k,l)\right) [[/math]]

for any colored integers [math]k,l[/math], for certain sets of partitions [math]D(k,l)\subset P(k,l)[/math], where

[[math]] T_\pi(e_{i_1}\otimes\ldots\otimes e_{i_k})=\sum_{j_1\ldots j_l}\delta_\pi\begin{pmatrix}i_1&\ldots&i_k\\ j_1&\ldots&j_l\end{pmatrix}e_{j_1}\otimes\ldots\otimes e_{j_l} [[/math]]

with the Kronecker type symbols [math]\delta_\pi\in\{0,1\}[/math] depending on whether the indices fit or not.

This is something very classical, coming from old results of Brauer, which state that the groups [math]O_N,U_N[/math] are easy, coming respectively from the categories [math]P_2,\mathcal P_2[/math] of pairings, and of matching pairings. We refer to for the story, and details. In what follows we will only need such Brauer theorems for [math]S_N,S_N^+[/math], the statements here being as follows:

Theorem

We have the following results:

• [math]S_N[/math] is easy, coming from the category of all partitions [math]P[/math].
• [math]S_N^+[/math] is easy, coming from the category of all noncrossing partitions [math]NC[/math].

Show Proof

This is something quite fundamental, with the proof, using the above Tannakian results and subsequent easiness theory, being as follows:

(1) [math]S_N^+[/math]. We know that this quantum group comes from the magic condition. In order to interpret this magic condition, consider the fork partition:

[[math]] Y\in P(2,1) [[/math]]

The linear map associated to this fork partition [math]Y[/math] is then given by:

[[math]] T_Y(e_i\otimes e_j)=\delta_{ij}e_i [[/math]]

Thus, in usual matrix notation, this linear map is given by:

[[math]] T_Y=(\delta_{ijk})_{i,jk} [[/math]]

Now given a corepresentation [math]u[/math], we have the following formula:

[[math]] (T_Yu^{\otimes 2})_{i,jk} =\sum_{lm}(T_Y)_{i,lm}(u^{\otimes 2})_{lm,jk} =u_{ij}u_{ik} [[/math]]

On the other hand, we have as well the following formula:

[[math]] (uT_Y)_{i,jk} =\sum_lu_{il}(T_Y)_{l,jk} =\delta_{jk}u_{ij} [[/math]]

We conclude that we have the following equivalence:

[[math]] T_Y\in Hom(u^{\otimes 2},u)\iff u_{ij}u_{ik}=\delta_{jk}u_{ij},\forall i,j,k [[/math]]

The condition on the right being equivalent to the magic condition, we obtain that [math]S_N^+[/math] is indeed easy, the corresponding category of partitions being, as desired:

[[math]] D = \lt Y \gt =NC [[/math]]

(2) [math]S_N[/math]. Here there is no need for new computations, because we have:

[[math]] S_N=S_N^+\cap O_N [[/math]]

At the categorical level means that [math]S_N[/math] is easy, coming from:

[[math]] \lt NC,\slash\hskip-2.2mm\backslash \gt =P [[/math]]

Alternatively, if you prefer, we can rewrite the above proof for [math]S_N^+[/math], by adding at each step the basic crossing [math]\slash\hskip-2.2mm\backslash[/math] next to the fork partition [math]Y[/math].

■

Let us discuss now the computation of the law of the main character. This computation is the main problem regarding any compact quantum group, as shown by the following result, which summarizes the various motivations for doing this computation:

Theorem

Given a Woronowicz algebra [math](A,u)[/math], the law of the main character

[[math]] \chi=\sum_{i=1}^Nu_{ii} [[/math]]

with respect to the Haar integration has the following properties:

• The moments of [math]\chi[/math] are the numbers [math]M_k=\dim(Fix(u^{\otimes k}))[/math].
• [math]M_k[/math] counts as well the lenght [math]p[/math] loops at [math]1[/math], on the Cayley graph of [math]A[/math].
• [math]law(\chi)[/math] is the Kesten measure of the associated discrete quantum group.
• When [math]u\sim\bar{u}[/math] the law of [math]\chi[/math] is a usual measure, supported on [math][-N,N][/math].
• The algebra [math]A[/math] is amenable precisely when [math]N\in supp(law(Re(\chi)))[/math].
• Any morphism [math]f:(A,u)\to (B,v)[/math] must increase the numbers [math]M_k[/math].
• Such a morphism [math]f[/math] is an isomorphism when [math]law(\chi_u)=law(\chi_v)[/math].

Show Proof

All this is quite advanced, the idea being as follows:

(1) This comes from the Peter-Weyl type theory in , which tells us the number of fixed points of [math]v=u^{\otimes k}[/math] can be recovered by integrating the character [math]\chi_v=\chi_u^k[/math].

(2) This is something true, and well-known, for [math]A=C^*(\Gamma)[/math], with [math]\Gamma= \lt g_1,\ldots,g_N \gt [/math] being a discrete group. In general, the proof is quite similar.

(3) This is actually the definition of the Kesten measure, in the case [math]A=C^*(\Gamma)[/math], with [math]\Gamma= \lt g_1,\ldots,g_N \gt [/math] being a discrete group. In general, this follows from (2).

(4) The equivalence [math]u\sim\bar{u}[/math] translates into [math]\chi_u=\chi_u^*[/math], and this gives the first assertion. As for the support claim, this follows from [math]uu^*=1\implies||u_{ii}||\leq1[/math], for any [math]i[/math].

(5) This is the Kesten amenability criterion, which can be established as in the classical case, [math]A=C^*(\Gamma)[/math], with [math]\Gamma= \lt g_1,\ldots,g_N \gt [/math] being a discrete group.

(6) This is something elementary, which follows from (1) above, and from the fact that the morphisms of Woronowicz algebras increase the spaces of fixed points.

(7) This follows by using (6), and the Peter-Weyl type theory from , the idea being that if [math]f[/math] is not injective, then it must strictly increase one of the spaces [math]Fix(u^{\otimes k})[/math].

■

In the case of the symmetric group [math]S_N[/math], the character result is as follows:

Theorem

For the symmetric group [math]S_N[/math] the main character counts fixed points,

[[math]] \chi(\sigma)=\#\left\{i\in\{1,\ldots,N\}\Big|\sigma(i)=i\right\} [[/math]]

and its law becomes Poisson [math](1)[/math], in the [math]N\to\infty[/math] limit.

Show Proof

This is something very classical, which can be done in 3 steps, as follows:

(1) The trace of the permutation matrices [math]\sigma\in S_N\subset O_N[/math] being the number of 1 entries, which correspond to fixed points, we have:

[[math]] Tr(\sigma)=\#\left\{i\in\{1,\ldots,N\}\Big|\sigma(i)=i\right\} [[/math]]

If we denote by [math]F_i\subset S_N[/math] the set of permutations satisfying [math]\sigma(i)=i[/math], the number of permutations [math]\sigma\in S_N[/math] having no fixed point at all, called derangements, is:

[[math]] \begin{eqnarray*} F_\emptyset &=&|S_N|-\sum_i|F_i|+\sum_{i \lt j}|F_i\cap F_j|-\ldots\ldots+(-1)^N|F_1\cap\ldots\cap F_N|\\ &=&N!-N\cdot(N-1)!+\binom{N}{2}(N-2)!-\ldots\ldots+(-1)^N\binom{N}{N}1!\\ &=&N!-\frac{N!}{1}+\frac{N!}{2}-\frac{N!}{6}+\ldots\ldots+(-1)^N\frac{N!}{N!} \end{eqnarray*} [[/math]]

(2) Thus, when dividing by [math]N![/math], and letting [math]N\to\infty[/math], we obtain:

[[math]] P(\chi=0)\simeq\frac{1}{e} [[/math]]

(3) In fact, the same method gives the following formula, valid for any [math]k\in\mathbb N[/math]:

[[math]] P(\chi=k)\simeq\frac{1}{ek!} [[/math]]

But this shows that [math]\chi[/math] becomes Poisson (1) with [math]N\to\infty[/math], as claimed.

■

Summarizing, we have here some interesting results regarding the classical permutation group [math]S_N[/math]. In what follows we will present some similar results regarding the quantum permutation group [math]S_N^+[/math], and we will discuss the relation between the classical results and the free results, which will complement the easiness theory developed above. In order to include as well [math]S_N^+[/math] in our discussion, we will need the following result, with [math]*[/math] being the classical convolution, and [math]\boxplus[/math] being Voiculescu's free convolution operation :

Theorem

The following Poisson type limits converge, for any [math]t \gt 0[/math],

[[math]] p_t=\lim_{n\to\infty}\left(\left(1-\frac{1}{n}\right)\delta_0+\frac{1}{n}\delta_t\right)^{*n} [[/math]]

[[math]] \pi_t=\lim_{n\to\infty}\left(\left(1-\frac{1}{n}\right)\delta_0+\frac{1}{n}\delta_t\right)^{\boxplus n} [[/math]]

the limiting measures being the Poisson law [math]p_t[/math], and the Marchenko-Pastur law [math]\pi_t[/math],

[[math]] p_t=\frac{1}{e^t}\sum_{k=0}^\infty\frac{t^k\delta_k}{k!} [[/math]]

[[math]] \pi_t=\max(1-t,0)\delta_0+\frac{\sqrt{4t-(x-1-t)^2}}{2\pi x}\,dx [[/math]]

whose moments are given by the following formulae:

[[math]] M_k(p_t)=\sum_{\pi\in P(k)}t^{|\pi|}\quad,\quad M_k(\pi_t)=\sum_{\pi\in NC(k)}t^{|\pi|} [[/math]]

The Marchenko-Pastur measure [math]\pi_t[/math] is also called free Poisson law.

Show Proof

This is something quite advanced, related to probability theory, free probability theory, and random matrices, the idea being as follows:

(1) The first step is that of finding suitable functional transforms, which linearize the convolution operations in the statement. In the classical case this is the logarithm of the Fourier transform [math]\log F[/math], and in the free case this is Voiculescu's [math]R[/math]-transform.

(2) With these tools in hand, the above limiting theorems can be proved in a standard way, a bit as when proving the Central Limit Theorem. The computations give the moment formulae in the statement, and the density computations are standard as well.

(3) Finally, in order for the discussion to be complete, what still remains to be explained is the precise nature of the “liberation” operation [math]p_t\to\pi_t[/math], as well as the random matrix occurrence of [math]\pi_t[/math]. This is more technical, and we refer here to , , .

■

Getting back now to quantum permutations, the results here are as follows:

Theorem

The law of the main character, given by

[[math]] \chi=\sum_iu_{ii} [[/math]]

for [math]S_N/S_N^+[/math] becomes [math]p_1/\pi_1[/math] with [math]N\to\infty[/math]. As for the truncated character

[[math]] \chi_t=\sum_{i=1}^{[tN]}u_{ii} [[/math]]

for [math]S_N/S_N^+[/math], with [math]t\in(0,1][/math], this becomes [math]p_t/\pi_t[/math] with [math]N\to\infty[/math].

Show Proof

This is again something quite technical, the idea being as follows:

(1) In the classical case this is well-known, and follows by using the inclusion-exclusion principle, and then letting [math]N\to\infty[/math], as in the proof of Theorem 13.23, at [math]t=1[/math].

(2) In the free case there is no such simple argument, and we must use what we know about [math]S_N^+[/math], namely its easiness property. We know from easiness that we have:

[[math]] Fix(u^{\otimes k})=span(NC(k)) [[/math]]

On the other hand, a direct computation shows that the partitions in [math]P(k)[/math], and in particular those in [math]NC(k)[/math], implemented as linear maps via the operation [math]\pi\to T_\pi[/math] from Proposition 13.19, become linearly independent with [math]N\geq k[/math]. Thus, we have:

[[math]] \begin{eqnarray*} \int_{S_N^+}\chi^k &=&\dim\left(Fix(u^{\otimes k})\right)\\ &=&\dim\left(span\left(T_\pi\Big|\pi\in NC(k)\right)\right)\\ &\simeq&|NC(k)|\\ &=&\sum_{\pi\in NC(k)}1^{|\pi|} \end{eqnarray*} [[/math]]

In the general case now, where our parameter is an arbitrary number [math]t\in(0,1][/math], the above computation does not apply, but we can still get away with Peter-Weyl theory. Indeed, we know from Theorem 13.10 above how to compute the Haar integration of [math]S_N^+[/math], out of the knowledge of the fixed point spaces [math]Fix(u^{\otimes k})[/math], and in practice, by using easiness, this leads to the following formula, called Weingarten integration formula:

[[math]] \int_{S_N^+}u_{i_1j_1}\ldots u_{i_kj_k}=\sum_{\pi,\sigma\in NC(k)}\delta_\pi(i)\delta_\sigma(j)W_{kN}(\pi,\sigma) [[/math]]

Here the [math]\delta[/math] symbols are Kronecker type symbols, checking whether the indices fit or not with the partitions, and [math]W_{kN}=G_{kN}^{-1}[/math], with [math]G_{kN}(\pi,\sigma)=N^{|\pi\vee\sigma|}[/math], where [math]|.|[/math] is the number of blocks. Now by using this formula for computing the moments of [math]\chi_t[/math], we obtain:

[[math]] \begin{eqnarray*} \int_{S_N^+}\chi_t^k &=&\sum_{i_1=1}^{[tN]}\ldots\sum_{i_k=1}^{[tN]}\int u_{i_1i_1}\ldots u_{i_ki_k}\\ &=&\sum_{\pi,\sigma\in NC(k)}W_{kN}(\pi,\sigma)\sum_{i_1=1}^{[tN]}\ldots\sum_{i_k=1}^{[tN]}\delta_\pi(i)\delta_\sigma(i)\\ &=&\sum_{\pi,\sigma\in NC(k)}W_{kN}(\pi,\sigma)G_{k[tN]}(\sigma,\pi)\\ &=&Tr(W_{kN}G_{k[tN]}) \end{eqnarray*} [[/math]]

The point now is that with [math]N\to\infty[/math] the Gram matrix [math]G_{kN}[/math], and so the Weingarten matrix [math]W_{kN}[/math] too, becomes asymptotically diagonal. We therefore obtain:

[[math]] \int_{S_N^+}\chi_t^k\simeq\sum_{\pi\in NC(k)}t^{|\pi|} [[/math]]

Thus, we are led to the conclusion in the statement. For details, see .

■

As a conclusion to all this, the usual symmetric group [math]S_N[/math] has a free analogue [math]S_N^+[/math], which is infinite at [math]N\geq4[/math]. The best way to understand the liberation operation [math]S_N\to S_N^+[/math] is via Brauer theorems and easiness. An even better way, which is more advanced, is via probability theory, for the asymptotic law of the main character. All this might seem quite heavy, but hey, we are probably into some kind of quantum mechanics here.

General references

Banica, Teo (2024). "Invitation to Hadamard matrices". arXiv:1910.06911 [math.CO].