15b. Dual formalism

[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.

As another application of the orbit theory developed above, following Bichon , let us discuss now the group duals [math]\widehat{\Gamma}\subset S_N^+[/math]. We first have the following result:

Theorem

Given a quotient group [math]\mathbb Z_{N_1}*\ldots*\mathbb Z_{N_k}\to\Gamma[/math], we have an embedding [math]\widehat{\Gamma}\subset S_N^+[/math], with [math]N=N_1+\ldots+N_k[/math], having the following properties:

• This embedding appears by diagonally joining the embeddings [math]\widehat{\mathbb Z_{N_k}}\subset S_{N_k}^+[/math], and the corresponding magic matrix has blocks of sizes [math]N_1,\ldots,N_k[/math].
• The equivalence relation on [math]X=\{1,\ldots,N\}[/math] coming from the orbits of the action [math]\widehat{\Gamma}\curvearrowright X[/math] appears by refining the partition [math]N=N_1+\ldots+N_k[/math].

Show Proof

This is something elementary, the idea being as follows:

(1) Given a quotient group [math]\mathbb Z_{N_1}*\ldots*\mathbb Z_{N_k}\to\Gamma[/math], we have indeed a standard embedding as follows, with [math]N=N_1+\ldots+N_k[/math], that we actually know well since chapter 13:

[[math]] \begin{eqnarray*} \widehat{\Gamma} &\subset&\widehat{\mathbb Z_{N_1}*\ldots*\mathbb Z_{N_k}} =\widehat{\mathbb Z_{N_1}}\,\hat{*}\,\ldots\,\hat{*}\,\widehat{\mathbb Z_{N_k}}\\ &\simeq&\mathbb Z_{N_1}\,\hat{*}\,\ldots\,\hat{*}\,\mathbb Z_{N_k} \subset S_{N_1}\,\hat{*}\,\ldots\,\hat{*}\,S_{N_k}\\ &\subset&S_{N_1}^+\,\hat{*}\,\ldots\,\hat{*}\,S_{N_k}^+ \subset S_N^+ \end{eqnarray*} [[/math]]

(2) Regarding the magic matrix, our claim is that this is as follows, [math]F_N=\frac{1}{\sqrt{N}}(w_N^{ij})[/math] with [math]w_N=e^{2\pi i/N}[/math] being Fourier matrices, and [math]g_l[/math] being the standard generator of [math]\mathbb Z_{N_l}[/math]:

[[math]] u=\begin{pmatrix} F_{N_1}I_1F_{N_1}^*\\ &\ddots\\ &&F_{N_k}I_kF_{N_k}^* \end{pmatrix} \quad,\quad I_l=\begin{pmatrix} 1\\ &g_l\\ &&\ddots\\ &&&g_l^{N_l-1} \end{pmatrix} [[/math]]

(3) Indeed, let us recall that the magic matrix for [math]\mathbb Z_N\subset S_N\subset S_N^+[/math] is given by:

[[math]] v_{ij} =\chi\left(\sigma\in\mathbb Z_N\Big|\sigma(j)=i\right) =\delta_{i-j} [[/math]]

Let us apply now the Fourier transform. According to our usual Pontrjagin duality conventions, we have a pair of inverse isomorphisms, as follows:

[[math]] \Phi:C(\mathbb Z_N)\to C^*(\mathbb Z_N)\quad,\quad\delta_i\to\frac{1}{N}\sum_kw^{ik}g^k [[/math]]

[[math]] \Psi:C^*(\mathbb Z_N)\to C(\mathbb Z_N)\quad,\quad g^i\to\sum_kw^{-ik}\delta_k [[/math]]

Here [math]w=e^{2\pi i/N}[/math], and we use the standard Fourier analysis convention that the indices are [math]0,1,\ldots,N-1[/math]. With [math]F=\frac{1}{\sqrt{N}}(w^{ij})[/math] and [math]I=diag(g^i)[/math] as above, we have:

[[math]] \begin{eqnarray*} u_{ij} &=&\Phi(v_{ij})\\ &=&\frac{1}{N}\sum_kw^{(i-j)k}g^k\\ &=&\frac{1}{N}\sum_kw^{ik}g^kw^{-jk}\\ &=&(FIF^*)_{ij} \end{eqnarray*} [[/math]]

Thus, the magic matrix that we are looking for is [math]u=FIF^*[/math], as claimed.

(4) Finally, the second assertion in the statement is clear from the fact that [math]u[/math] is block-diagonal, with blocks corresponding to the partition [math]N=N_1+\ldots+N_k[/math].

■

As a first comment on the above result, not all group dual subgroups [math]\widehat{\Gamma}\subset S_N^+[/math] appear as above, a well-known counterexample here being the Klein group:

[[math]] K=\mathbb Z_2\times\mathbb Z_2\subset S_4\subset S_4^+ [[/math]]

Indeed, with [math]K=\{1,a,b,c\}[/math], where [math]c=ab[/math], consider the embedding [math]K\subset S_4[/math] given by [math]a=(12)(34)[/math], [math]b=(13)(24)[/math], [math]c=(14)(23)[/math]. The corresponding magic matrix is:

[[math]] u=\begin{pmatrix} \delta_1&\delta_a&\delta_b&\delta_c\\ \delta_a&\delta_1&\delta_c&\delta_b\\ \delta_b&\delta_c&\delta_1&\delta_a\\ \delta_c&\delta_b&\delta_a&\delta_1 \end{pmatrix}\in M_4(C(K)) [[/math]]

Now since this matrix is not block-diagonal, the only choice for [math]K=\widehat{K}[/math] to appear as in Theorem 15.12 would be via a quotient map [math]\mathbb Z_4\to K[/math], which is impossible. As a second comment now on Theorem 15.12, in the second assertion there we really have a possible refining operation, as shown by the example provided by the trivial group, namely:

[[math]] \mathbb Z_{N_1}*\ldots*\mathbb Z_{N_k}\to\{1\} [[/math]]

In order to further discuss all this, let us first enlarge the attention to the group dual subgroups [math]\widehat{\Gamma}\subset G[/math] of an arbitrary closed subgroup [math]G\subset U_N^+[/math]. We have here:

Theorem

Given a closed subgroup [math]G\subset U_N^+[/math] and a matrix [math]Q\in U_N[/math], we let [math]T_Q\subset G[/math] be the diagonal torus of [math]G[/math], with fundamental representation spinned by [math]Q[/math]:

[[math]] C(T_Q)=C(G)\Big/\left \lt (QuQ^*)_{ij}=0\Big|\forall i\neq j\right \gt [[/math]]

This torus is then a group dual, [math]T_Q=\widehat{\Lambda}_Q[/math], where [math]\Lambda_Q= \lt g_1,\ldots,g_N \gt [/math] is the discrete group generated by the elements [math]g_i=(QuQ^*)_{ii}[/math], which are unitaries inside [math]C(T_Q)[/math].

Show Proof

Since [math]v=QuQ^*[/math] is a unitary corepresentation, its diagonal entries [math]g_i=v_{ii}[/math], when regarded inside [math]C(T_Q)[/math], are unitaries, and satisfy:

[[math]] \Delta(g_i)=g_i\otimes g_i [[/math]]

Thus [math]C(T_Q)[/math] is a group algebra, and more specifically we have [math]C(T_Q)=C^*(\Lambda_Q)[/math], where [math]\Lambda_Q= \lt g_1,\ldots,g_N \gt [/math] is the group in the statement, and this gives the result.

■

Generally speaking, the above family [math]\{T_Q|Q\in U_N\}[/math] can be thought of as being a kind of “maximal torus” for [math]G\subset U_N^+[/math]. Now back to quantum permutations, we have:

Theorem

For the quantum permutation group [math]S_N^+[/math], the discrete group quotient [math]F_N\to\Lambda_Q[/math] with [math]Q\in U_N[/math] comes from the following relations:

[[math]] \begin{cases} g_i=1&{\rm if}\ \sum_lQ_{il}\neq 0\\ g_ig_j=1&{\rm if}\ \sum_lQ_{il}Q_{jl}\neq 0\\ g_ig_jg_k=1&{\rm if}\ \sum_lQ_{il}Q_{jl}Q_{kl}\neq 0 \end{cases} [[/math]]

Also, given a decomposition [math]N=N_1+\ldots+N_k[/math], for the matrix [math]Q=diag(F_{N_1},\ldots,F_{N_k})[/math], where [math]F_N=\frac{1}{\sqrt{N}}(\xi^{ij})_{ij}[/math] with [math]\xi=e^{2\pi i/N}[/math] is the Fourier matrix, we obtain

[[math]] \Lambda_Q=\mathbb Z_{N_1}*\ldots*\mathbb Z_{N_k} [[/math]]

with dual embedded into [math]S_N^+[/math] in a standard way, as in Theorem 15.12.

Show Proof

This can be proved by a direct computation, as follows:

(1) Fix a unitary matrix [math]Q\in U_N[/math], and consider the following quantities:

[[math]] \begin{cases} c_i=\sum_lQ_{il}\\ c_{ij}=\sum_lQ_{il}Q_{jl}\\ d_{ijk}=\sum_l\bar{Q}_{il}\bar{Q}_{jl}Q_{kl} \end{cases} [[/math]]

We write [math]w=QvQ^*[/math], where [math]v[/math] is the fundamental corepresentation of [math]C(S_N^+)[/math]. Assume [math]X\simeq\{1,\ldots,N\}[/math], and let [math]\alpha[/math] be the coaction of [math]C(S_N^+)[/math] on [math]C(X)[/math]. Let us set:

[[math]] \varphi_i=\sum_l\bar{Q}_{il}\delta_l\in C(X) [[/math]]

Also, let [math]g_i=(QvQ^*)_{ii}\in C^*(\Lambda_Q)[/math]. If [math]\beta[/math] is the restriction of [math]\alpha[/math] to [math]C^*(\Lambda_Q)[/math], then:

[[math]] \beta(\varphi_i)=\varphi_i\otimes g_i [[/math]]

(2) Now recall that [math]C(X)[/math] is the universal [math]C^*[/math]-algebra generated by elements [math]\delta_1,\ldots,\delta_N[/math] which are pairwise orthogonal projections. Writing these conditions in terms of the linearly independent elements [math]\varphi_i[/math] by means of the formulae [math]\delta_i=\sum_lQ_{il}\varphi_l[/math], we find that the universal relations for [math]C(X)[/math] in terms of the elements [math]\varphi_i[/math] are as follows:

[[math]] \begin{cases} \sum_ic_i\varphi_i=1\\ \varphi_i^*=\sum_jc_{ij}\varphi_j\\ \varphi_i\varphi_j=\sum_kd_{ijk}\varphi_k \end{cases} [[/math]]

(3) Let [math]\widetilde{\Lambda}_Q[/math] be the group in the statement. Since [math]\beta[/math] preserves these relations, we get:

[[math]] \begin{cases} c_i(g_i-1)=0\\ c_{ij}(g_ig_j-1)=0\\ d_{ijk}(g_ig_j-g_k)=0 \end{cases} [[/math]]

We conclude from this that [math]\Lambda_Q[/math] is a quotient of [math]\widetilde{\Lambda}_Q[/math]. On the other hand, it is immediate that we have a coaction map as follows:

[[math]] C(X)\to C(X)\otimes C^*(\widetilde{\Lambda}_Q) [[/math]]

Thus [math]C(\widetilde{\Lambda}_Q)[/math] is a quotient of [math]C(S_N^+)[/math]. Since [math]w[/math] is the fundamental corepresentation of [math]S_N^+[/math] with respect to the basis [math]\{\varphi_i\}[/math], it follows that the generator [math]w_{ii}[/math] is sent to [math]\widetilde{g}_i\in\widetilde{\Lambda}_Q[/math], while [math]w_{ij}[/math] is sent to zero. We conclude that [math]\widetilde{\Lambda}_Q[/math] is a quotient of [math]\Lambda_Q[/math]. Since the above quotient maps send generators on generators, we conclude that [math]\Lambda_Q=\widetilde{\Lambda}_Q[/math], as desired.

(4) We apply the result found in (3), with the [math]N[/math]-element set [math]X[/math] there being:

[[math]] X=\mathbb Z_{N_1}\sqcup\ldots\sqcup\mathbb Z_{N_k} [[/math]]

With this choice, we have [math]c_i=\delta_{i0}[/math] for any [math]i[/math]. Also, we have [math]c_{ij}=0[/math], unless [math]i,j,k[/math] belong to the same block to [math]Q[/math], in which case [math]c_{ij}=\delta_{i+j,0}[/math], and also [math]d_{ijk} =0[/math], unless [math]i,j,k[/math] belong to the same block of [math]Q[/math], in which case [math]d_{ijk}=\delta_{i+j,k}[/math]. We conclude from this that [math]\Lambda_Q[/math] is the free product of [math]k[/math] groups which have generating relations as follows:

[[math]] g_ig_j=g_{i+j}\quad,\quad g_i^{-1}=g_{-i} [[/math]]

But this shows that our group is [math]\Lambda_Q=\mathbb Z_{N_1}*\ldots*\mathbb Z_{N_k}[/math], as stated.

■

In relation now with actions on graphs, let us start with the following simple fact:

Proposition

In order for a closed subgroup [math]G\subset U_K^+[/math] to appear as [math]G=G^+(X)[/math], for a certain graph [math]X[/math] having [math]N[/math] vertices, the following must happen:

• We must have a representation [math]G\subset U_N^+[/math].
• This representation must be magic, [math]G\subset S_N^+[/math].
• We must have a graph [math]X[/math] having [math]N[/math] vertices, such that [math]d\in End(u)[/math].
• [math]X[/math] must be in fact such that the Tannakian category of [math]G[/math] is precisely [math] \lt d \gt [/math].

Show Proof

This is more of an empty statement, coming from the definition of the quantum automorphism group [math]G^+(X)[/math], as formulated in chapter 14.

■

The above result remains something quite philosophical. In the group dual case, that we will be interested in now, we can combine it with the following result:

Proposition

Given a discrete group [math]\Gamma= \lt g_1,\ldots,g_N \gt [/math], embed diagonally [math]\widehat{\Gamma}\subset U_N^+[/math], via the unitary matrix [math]u=diag(g_1,\ldots,g_N)[/math]. We have then the formula

[[math]] Hom(u^{\otimes k},u^{\otimes l})=\left\{T=(T_{j_1\ldots j_l,i_1\ldots i_k})\Big|g_{i_1}\ldots g_{i_k}\neq g_{j_1}\ldots g_{j_l}\implies T_{j_1\ldots j_l,i_1\ldots i_k}=0\right\} [[/math]]

and in particular, with [math]k=l=1[/math], we have the formula

[[math]] End(u)=\left\{T=(T_{ji})\Big|g_i\neq g_j\implies T_{ji}=0\right\} [[/math]]

with the linear maps being identified with the corresponding scalar matrices.

Show Proof

This is indeed elementary, with the first assertion coming from:

[[math]] \begin{eqnarray*} T\in Hom(u^{\otimes k},u^{\otimes l}) &\iff&Tu^{\otimes k}=u^{\otimes l}T\\ &\iff&(Tu^{\otimes k})_{j_1\ldots j_l,i_1\ldots i_k}=(u^{\otimes l}T)_{j_1\ldots j_l,i_1\ldots i_k}\\ &\iff&T_{j_1\ldots j_l,i_1\ldots i_k}g_{i_1}\ldots g_{i_k}=g_{j_1}\ldots g_{j_l}T_{j_1\ldots j_l,i_1\ldots i_k}\\ &\iff&T_{j_1\ldots j_l,i_1\ldots i_k}(g_{i_1}\ldots g_{i_k}-g_{j_1}\ldots g_{j_l})=0 \end{eqnarray*} [[/math]]

As for the second assertion, this follows from the first one.

■

Still in the group dual setting, we have now, refining Proposition 15.15:

Theorem

In order for a group dual [math]\widehat{\Gamma}[/math] as above to appear as [math]G=G^+(X)[/math], for a certain graph [math]X[/math] having [math]N[/math] vertices, the following must happen:

• First, we need a quotient map [math]\mathbb Z_{N_1}*\ldots*\mathbb Z_{N_k}\to\Gamma[/math].
• Let [math]u=diag(I_1,\ldots,I_k)[/math], with [math]I_l=diag(\mathbb Z_{N_l})[/math], for any [math]l[/math].
• Consider also the matrix [math]F=diag(F_{N_1},\ldots,F_{N_k})[/math].
• We must then have a graph [math]X[/math] having [math]N[/math] vertices.
• This graph must be such that [math]F^*dF\neq0\implies I_i=I_j[/math].
• In fact, [math] \lt F^*dF \gt [/math] must be the category in Proposition 15.16.

Show Proof

This is something rather informal, which follows from the above.

■

Going ahead, in connection with the Fourier tori from Theorem 15.14, we have:

Proposition

The Fourier tori of [math]G^+(X)[/math] are the biggest quotients

[[math]] \mathbb Z_{N_1}*\ldots*\mathbb Z_{N_k}\to\Gamma [[/math]]

whose duals act on the graph, [math]\widehat{\Gamma}\curvearrowright X[/math].

Show Proof

We have indeed the following computation, at [math]F=1[/math]:

[[math]] \begin{eqnarray*} C(T_1(G^+(X))) &=&C(G^+(X))/ \lt u_{ij}=0,\forall i\neq j \gt \\ &=&[C(S_N^+)/ \lt [d,u]=0 \gt ]/ \lt u_{ij}=0,\forall i\neq j \gt \\ &=&[C(S_N^+)/ \lt u_{ij}=0,\forall i\neq j \gt ]/ \lt [d,u]=0 \gt \\ &=&C(T_1(S_N^+))/ \lt [d,u]=0 \gt \end{eqnarray*} [[/math]]

Thus, we obtain the result, with the remark that the quotient that we are interested in appears via relations of type [math]d_{ij}=1\implies g_i=g_j[/math]. The proof in general is similar.

■

In order to formulate our main result, let us call [math]G\subset G^+[/math] a Fourier liberation when [math]G^+[/math] is generated by [math]G[/math], and its Fourier tori. With this convention, we have:

Theorem

Consider the following conditions:

• We have [math]G(X)=G^+(X)[/math].
• [math]G(X)\subset G^+(X)[/math] is a Fourier liberation.
• [math]\widehat{\Gamma}\curvearrowright X[/math] implies that [math]\Gamma[/math] is abelian.

We have then the equivalence [math](1)\iff(2)+(3)[/math].

Show Proof

This is something elementary. Indeed, the implications [math](1)\implies(2,3)[/math] are trivial. As for [math](2,3)\implies(1)[/math], assuming [math]G(X)\neq G^+(X)[/math], from (2) we know that [math]G^+(X)[/math] has at least one non-classical Fourier torus, and this contradicts (3), as desired.

■

As an application of this, we have the following elementary result, which is a particular case of more general and advanced results regarding the random graphs, from :

Theorem

For a finite graph [math]X[/math], the probability for having an action

[[math]] \widehat{\Gamma}\curvearrowright X [[/math]]

with [math]\Gamma[/math] being a non-abelian group goes to [math]0[/math] with [math]|X|\to\infty[/math].

Show Proof

Observe first that in the cyclic case, where [math]F=F_N[/math] is a usual Fourier matrix, associated to a cyclic group [math]\mathbb Z_N[/math], we have the following formula, with [math]w=e^{2\pi i/N}[/math]:

[[math]] (F^*dF)_{ij} =\sum_{kl}(F^*)_{ik}d_{kl}F_{lj} =\sum_{kl}w^{lj-ik}d_{kl} =\sum_{k\sim l}w^{lj-ik} [[/math]]

In the general setting now, where we have a quotient map [math]\mathbb Z_{N_1}*\ldots*\mathbb Z_{N_k}\to\Gamma[/math], with [math]N_1+\ldots+N_k=N[/math], the computation is similar, as follows, with [math]w_i=e^{2\pi i/N_i}[/math]:

[[math]] (F^*dF)_{ij} =\sum_{kl}(F^*)_{ik}d_{kl}F_{lj} =\sum_{k\sim l}(F^*)_{ik}F_{lj} =\sum_{k:i,l:j,k\sim l}(w_{N_i})^{-ik}(w_{N_j})^{lj} [[/math]]

The point now is that with the partition [math]N_1+\ldots+N_k=N[/math] fixed, and with [math]d\in M_N(0,1)[/math] being random, we have [math](F^*dF)_{ij}\neq 0[/math] almost everywhere in the [math]N\to\infty[/math] limit, and so we obtain [math]I_i=I_j[/math] almost everywhere, and so abelianity of [math]\Gamma[/math], with [math]N\to\infty[/math].

■

Many other things can be said, as a continuation of the above, and we refer here to , for an introduction, and to the recent literature on the subject, for more.

General references

Banica, Teo (2024). "Graphs and their symmetries". arXiv:2406.03664 [math.CO].