1. Quantum permutation groups

We use the compact matrix quantum group formalism of Woronowicz [Reference Woronowicz37, Reference Woronowicz38], under the supplementary assumption $S^2=\operatorname{id}$ . The axioms are as follows:

Definition 1.1 A Woronowicz algebra is a $\textrm{C}^*$ -algebra A, given with a fundamental unitary representation $u\in M_N(A)$ whose entries generate A, such that there exist morphisms

\begin{equation*}\Delta\,{:}\,A\to A\otimes A,\end{equation*}

\begin{equation*}\varepsilon\,{:}\,A\to\mathbb C,\end{equation*}

\begin{equation*}S\,{:}\,A\to A^{opp},\end{equation*}

called comultiplication, counit, and antipode, given by the formulae

\begin{equation*}\Delta(u_{ij})=\sum_ku_{ik}\otimes u_{kj},\end{equation*}

\begin{equation*}\varepsilon(u_{ij})=\delta_{ij},\end{equation*}

\begin{equation*}S(u_{ij})=u_{ji}^*,\end{equation*}

on the standard generators $u_{ij}$ .

Here, $\otimes$ is the minimal tensor product of $\textrm{C}^*$ -algebras, and $A^{opp}$ is the opposite $\textrm{C}^*$ -algebra, with multiplication $a\cdot b=ba$ . The basic examples are as follows:

1. (1) Given a compact Lie group, $G\subset U_N$ , the algebra $A=C(G)$ of continuous functions $f\,{:}\,G\to\mathbb C$ , together with the matrix formed by the standard coordinates, $u_{ij}\,{:}\,g\to g_{ij}$ , is a Woronowicz algebra. This algebra is commutative, and the Gelfand theorem shows that any commutative Woronowicz algebra is of this form. See [Reference Woronowicz37].

2. (2) Given a finitely generated discrete group $\Gamma=\langle g_1,\ldots,g_N\rangle $ , the full group $\textrm{C}^*$ -algebra $A=\textrm{C}^*(\Gamma)$ is a Woronowicz algebra too, with the diagonal matrix formed by the generators, $u=\operatorname{diag}(g_1,\ldots,g_N)$ . This algebra $A=\textrm{C}^*(\Gamma)$ is cocommutative, in the sense that $\Sigma\Delta=\Delta$ , where $\Sigma(a\otimes b)=b\otimes a$ is the flip. Conversely, any cocommutative Woronowicz algebra can be shown to be of this form, up to identifying the different group $\textrm{C}^*$ -algebras that $\Gamma$ might have, in the non-amenable case. See [Reference Woronowicz37].

3. (3) The most basic examples appear by intersecting (1,2). Indeed, the compact abelian Lie groups $G\subset U_N$ are in Pontrjagin duality, $G=\widehat{\Gamma}$ and $\Gamma=\widehat{G}$ , with the finitely generated discrete abelian groups $\Gamma=\langle g_1,\ldots,g_N\rangle $ , and in this situation, the Fourier transform gives an identification of Woronowicz algebras $C(G)=\textrm{C}^*(\Gamma)$ . See [Reference Woronowicz37].

Based on these examples and observations, let us formulate:

Definition 1.2 Given a Woronowicz algebra (A,u), we write

\begin{equation*}A=C(G)=\textrm{C}^*(\Gamma),\end{equation*}

and call $G,\Gamma$ compact and discrete quantum groups. Also, we write

\begin{equation*}G=\widehat{\Gamma}\quad,\quad \Gamma=\widehat{G},\end{equation*}

and call $G,\Gamma$ dual to each other. We say that G is a finite quantum group if C(G) is finite dimensional. Finally, we identify two Woronowicz algebras

\begin{equation*}(A,u)=(B,v)\end{equation*}

when the $*$ -algebras $\mathcal A=\langle u_{ij}\rangle $ and $\mathcal B=\langle v_{ij}\rangle $ are isomorphic, via $u_{ij}\to v_{ij}$ .

The basic theory of the compact and discrete quantum groups, developed by Woronowicz in [Reference Woronowicz37, Reference Woronowicz38], consists in an existence result for the Haar measure, an extension of the classical Peter–Weyl theory, and an extension of Tannakian duality as well.

Definition 1.3 Let (C(G),u) and (C(G),v) be Woronowicz algebras with the same underlying $\textrm{C}^*$ -algebra C(G), but different fundamental unitary matrices, $u\in M_{N_1}(C(G))$ and $v\in M_{N_2}(C(G))$ . Where

\begin{equation*}\Delta_1(u_{ij})=\sum_{k=1}^{N_1}u_{ik}\otimes u_{kj} \quad \text{and} \quad \Delta_2(v_{ij})=\sum_{k=1}^{N_2} v_{ik}\otimes v_{kj},\end{equation*}

if $\Delta_1=\Delta_2$ , we consider (C(G),u) and (C(G),v) as representations of the same “abstract” compact quantum group G.

This definition is justified by the fact that if (C(G),u) is a Woronowicz algebra, then C(G) and $\Delta\,{:}\,C(G)\rightarrow C(G)\otimes C(G)$ also satisfy the axioms of an “abstract” compact quantum group, as in [Reference Woronowicz39]. This allows different Woronowicz algebra representations of a compact quantum group.

Following Wang [Reference Wang36], the quantum permutation groups are constructed as follows:

Definition 1.4 The quantum permutation group $S_N^+$ is the compact quantum group whose Woronowicz algebra is the universal $\textrm{C}^*$ -algebra given by

\begin{equation*}C(S_N^+)=\textrm{C}^*\left((u_{ij})_{i,j=1\ldots N}\Big|\,u=\textrm{magic}\right),\end{equation*}

with “magic” meaning formed of projections, in the $\textrm{C}^*$ -algebra sense $(p^2=p=p^*)$ , which must sum up to 1 on each row and each column.

Here the fact that $C(S_N^+)$ is indeed a Woronowicz algebra is standard, coming from the fact that if $(u_{ij})$ is magic, then so are the following matrices:

\begin{equation*}U_{ij}=\sum_ku_{ik}\otimes u_{kj},\end{equation*}

\begin{equation*}1_{ij}=\delta_{ij},\end{equation*}

\begin{align*}v_{ij}=u_{ji}.\\[-8pt]\end{align*}

Thus we can define indeed morphisms $\Delta,\varepsilon,S$ as in Definition 1.1, by using the universality property of $C(S_N^+)$ . See [Reference Wang36].

Definition 1.5 A quantum permutation group is a compact quantum group that admits a fundamental magic representation. When we write

\begin{equation*}G\subset S_N^+,\end{equation*}

we assume a fixed fundamental magic representation $u\in M_N(C(G))$ , and subsequently $u_{ij}$ referring to a generator of C(G) rather than of $C(S_N^+)$ .

The definitions and terminology of Definition 1.4 are motivated by a series of key observations and results from [Reference Wang36], as follows:

1. (1) The symmetric group $S_N$ , when regarded as the group of permutations of the N coordinate axes of $\mathbb R^N$ , becomes a matrix group, $S_N\subset O_N$ . In this picture, the standard coordinates $v_{ij}:S_N\to\mathbb R$ are the entries of the permutation matrices, given by:

   \begin{equation*}v_{ij}=\chi\left(\sigma\in S_N\Big|\sigma(j)=i\right).\end{equation*}

2. (2) These characteristic functions $v_{ij}$ are abstract projections in the $\textrm{C}^*$ -algebra sense, $v_{ij}^2=v_{ij}=v_{ij}^*$ , summing to 1 on each row and column of $v=(v_{ij})$ . Thus the matrix v is magic, and so we have a quotient map as follows:

   \begin{equation*}C(S_N^+)\to C(S_N),\end{equation*}
   \begin{align*}u_{ij}\to v_{ij}.\\[-8pt]\end{align*}

3. (3) This quotient map is a morphism of Woronowicz algebras, and so corresponds to an embedding of compact quantum groups, as follows:

   \begin{equation*}S_N\subset S_N^+.\end{equation*}

4. (4) The classical version, $G_{\text{class}}\subset G$ , of a compact quantum group G is the Gelfand spectrum of the abelianisation of C(G). Recall the abelianisation of C(G) is the commutative $\textrm{C}^*$ -algebra $C(G)/I$ , with $I\subset C(G)$ being the commutator ideal. In turn G is said to be a “liberation” of $G_{\text{class}}$ . The embedding $S_N\subset S_N^+$ is a “liberation”. This comes indeed from the following presentation result for the algebra $C(S_N)$ , which is standard:

   \begin{equation*}C(S_N^+)=\textrm{C}^*_{comm}\left((v_{ij})_{i,j=1\ldots N}\Big|\,v=\textrm{magic}\right).\end{equation*}

5. (5) Now since we have a liberation $S_N\subset S_N^+$ , it makes sense to say that $S_N^+$ is a ‘quantum permutation group’. Moreover, a quick comparison between the formula in Definition 1.4 for $C(S_N^+)$ and the one above for $C(S_N)$ suggests that $S_N^+$ should be the ‘biggest’ such liberation, and so is ‘the’ quantum permutation group.

6. (6) These latter considerations are confirmed by a precise result, stating that $S_N^+$ is the biggest compact quantum group acting on $X=\{1,\ldots,N\}$ . To be more precise, $C(S_N^+)$ is the biggest Woronowicz algebra coacting on C(X), in the following sense:

   \begin{equation*}\Phi:C(X)\to C(X)\otimes C(G),\end{equation*}
   \begin{equation*}e_j\to\sum e_i\otimes u_{ij}.\end{equation*}

7. (7) The proof of this latter fact is based on the observation, coming from some elementary computations, that $\Phi$ defined as above is a coaction precisely when $u=(u_{ij})$ is magic. Technically speaking, one must assume in all this that the action $G\curvearrowright X$ preserves the counting measure on X, with this being not automatic in the quantum case.

As an extremely important question now, is this abstract object $S_N^+$ that we just introduced really bigger than $S_N$ ? And also, if bigger, is it really non-finite, needing the ‘compact’ formalism? The answers here, which add to the above, and fully justify Definition 1.4, are as follows, also from [Reference Wang36]:

Proof. This can be proved by a case-by-case analysis, as follows:

1. (1) Trivial.

2. (2) The $N=2$ statement is clear, because a $2\times2$ magic matrix must be as follows, with p being a projection:

   \begin{equation*}u=\begin{pmatrix}p&\quad 1-p\\ 1-p&\quad p\end{pmatrix}.\end{equation*}
   Now since the entries of u commute, it follows that $C(S_2^+)$ is commutative, and so $S_2^+$ collapses to its classical version, which is $S_2$ .

3. (3) At $N=3$ now, by using the same idea as in the $N=2$ case, we must prove that the entries of any $3\times3$ magic matrix commute. This is something quite tricky, and there are 4 known proofs here [Reference Banica1, Reference Lupini, Mančinska and Roberson22, Reference McCarthy24, Reference Wang35]. According to the proof in [Reference McCarthy24], which is the most recent, it suffices to show that $u_{11}u_{22}=u_{22}u_{11}$ , by showing:

   \begin{equation*}u_{11}u_{22}=u_{11}u_{33}=u_{22}u_{33}=u_{22}u_{11}.\end{equation*}
   But these three equalities come respectively from:
   \begin{equation*}u_{11}(u_{21}+u_{22}+{u_{23}})=u_{11}(u_{13}+u_{23}+u_{33})\end{equation*}
   \begin{equation*}(u_{11}+u_{21}+u_{31})u_{33}=(u_{21}+u_{22}+u_{23})u_{33}\end{equation*}
   \begin{equation*}u_{22}(u_{31}+u_{32}+u_{33})=u_{22}(u_{11}+u_{21}+{u_{31}}).\end{equation*}

4. (4) At $N=4$ , we must prove that the algebra $C(S_4^+)$ is noncommutative and infinite dimensional, and this comes from the fact that the following matrix is magic, for any choice of two projections p, q on a Hilbert space H:

   \begin{equation*}u=\begin{pmatrix}p&\quad 1-p&\quad 0&\quad 0\\1-p&\quad p&\quad 0&\quad 0\\0&\quad 0&\quad q&\quad 1-q\\0&\quad 0&\quad 1-q&\quad q\end{pmatrix}.\end{equation*}
   Thus, if we choose p, q as the generators of $\textrm{C}^*(p,q)$ , the universal unital $\textrm{C}^*$ -algebra generated by two projections, we obtain the result, due to the quotient map $C(S_4^+)\to\textrm{C}^*(p,q)$ . It is worth noting that where $D_\infty=\langle a,b \,|\,a^2=b^2=1\rangle$ is the infinite dihedral group, $\textrm{C}^*(p,q)\cong C(\widehat{D_\infty})$ via the isomorphism $p\to (e+a)/2$ and $q\to (e+b)/2$ .

5. (5) For $N\geq 5$ , let v be the magic unitary of $C(S_4^+)$ , and $1_{N-4}\in M_{N-4}(C(S_4^+))$ the diagonal matrix with the unit of $C(S_4^+)$ along the diagonal. The magic unitary $u=\operatorname{diag}(v,1_{N-4})$ shows that we have an embedding $S_4^+\subset S_N^+$ .

2. Orbits, group duals, and orbitals

We have the following notion, due to Bichon [Reference Bichon11]:

Definition 2.1 Given a quantum permutation group $G\subset S_N^+$ , we define its orbits as being the equivalence classes under the following relation:

\begin{equation*}i\sim j\iff u_{ij}\neq0.\end{equation*}

We say that G is transitive when we have only one orbit (i.e. $u_{ij}\neq0$ for any i,j).

Observe that in the classical case, $G\subset S_N$ , we obtain indeed the classical notation of an orbit, because here the standard coordinates $u_{ij}$ are the following characteristic functions:

\begin{equation*}u_{ij}=\chi\left(\sigma\in G\Big|\sigma(j)=i\right).\end{equation*}

In general, the fact that $\sim$ defined as above is transitive, reflexive and symmetric comes by examining the formulae of $\Delta,\varepsilon,S$ on the standard generators $u_{ij}$ . We refer to [Reference Bichon11] for full details here. Bichon introduced the orbits mainly in order to solve a key problem, namely the classification of the group dual embeddings $\widehat{\Gamma}\subset S_N^+$ . In one sense, we have the following construction, which is elementary:

Proposition 2.2 Given a finitely generated group $\Gamma=\langle g_1,\ldots,g_k\rangle $ , with the generators having finite order, $g_i^{N_i}=1$ , we have a quantum group embedding

\begin{equation*}\widehat{\Gamma}\subset S_N^+,\end{equation*}

with $N=N_1+\ldots+N_k$ , as follows, using the Fourier identifications $\widehat{\mathbb Z}_{N_p}\simeq\mathbb Z_{N_p}$ ,

\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}\\[3pt]&\cong&\mathbb Z_{N_1}\,\hat{*}\,\ldots\,\hat{*}\,\mathbb Z_{N_k}\subset S_{N_1}^+\,\hat{*}\,\ldots\,\hat{*}\,S_{N_k}^+\\[3pt] &\subset&S_N^+,\end{eqnarray*}

and with $\hat{*}$ being the dual free product operation for compact quantum groups.

Proof. Our assumption $\Gamma=\langle g_1,\ldots,g_k\rangle $ , with the generators satisfying $g_p^{N_p}=1$ , means that $\Gamma$ appears as a quotient of a free product of cyclic groups, as follows:

\begin{equation*}\mathbb Z_{N_1}*\ldots*\mathbb Z_{N_k}\to\Gamma.\end{equation*}

Thus the dual $\widehat{\Gamma}$ appears as a closed subgroup of the dual $\widehat{\mathbb Z_{N_1}*\ldots*\mathbb Z_{N_k}}$ , and the continuation is standard, by using Wang’s operation $\hat{*}$ from [Reference Wang35], defined by:

\begin{equation*}C(G\,\hat{*}\,H)=C(G)*C(H).\end{equation*}

Let us record as well the explicit formula of the embedding. For each $g_p$ the magic unitary $u^{g_p}=(u^{g_p}_{kl})$ of the corresponding dual $\widehat{\mathbb Z}_{N_p}$ is as follows, with $w=e^{2\pi i/N_p}$ :

(1) \begin{equation}u^{g_p}_{kl}=\frac{1}{N_p}\sum_{m=1}^{N_p}w^{(k-l)m}g_p^m.\end{equation}

A magic unitary for $\widehat{\Gamma}$ is then given by the following formula:

\begin{equation*}u=\begin{pmatrix}u^{g_1}\\&\quad \ddots\\&&\quad u^{g_k}\end{pmatrix}.\end{equation*}

Finally, let us record the following useful inversion formula:

\begin{equation*}g_p=\sum_{k=1}^{N_p}w^{1-k}u_{k1}^{g_p}.\end{equation*}

We have the following converse of the above result, from [Reference Bichon11]:

Theorem 2.3 Any group dual subgroup $\widehat{\Gamma}\subset S_N^+$ appears as above, from a quotient

\begin{equation*}\mathbb Z_{N_1}*\ldots*\mathbb Z_{N_k}\to\Gamma,\end{equation*}

with the numbers $N_1,\ldots,N_k$ summing up to N.

Proof. Assume that we have a group dual subgroup $\widehat{\Gamma}\subset S_N^+$ . The corresponding magic unitary must be of the following form, with $h_p\in\Gamma$ and $U\in U_N$ :

\begin{equation*}u=U\begin{pmatrix}h_1\\&\quad\ddots\\&&\quad h_N\end{pmatrix}U^*.\end{equation*}

Consider now the orbit decomposition for $\widehat{\Gamma}\subset S_N^+$ , coming from Definition 2.1:

\begin{equation*}N=N_1+\cdots+N_k.\end{equation*}

We conclude that u has a $N=N_1+\cdots+N_k$ block-diagonal pattern, and so that U has as well this $N=N_1+\cdots+N_k$ block-diagonal pattern. But this discussion reduces our problem to its $k=1$ particular case, with the statement here being that the cyclic group $\mathbb Z_N$ is the only transitive group dual $\widehat{\Gamma}\subset S_N^+$ . The proof of this latter fact being elementary, we obtain the result. For full details here, we refer to [Reference Bichon11].

In fact, the orbit theory of Bichon tells us something about all embeddings $G\subset S_N^+$ .

Say that a transitive magic representation $u^{p}$ is equivalent to a transitive magic representation $u^{q}$ if there exists a permutation matrix P such that $u^{q}=Pu^{p}P^{-1}$ .

Let $M=\{u^p\}_{p\in M}$ be the set of equivalence classes of transitive magic representations of C(G).

Proof. The orbit relation is an equivalence relation and so partitions:

\begin{equation*}\{1,\dots,N\}=\bigsqcup_{p=1}^k X_p.\end{equation*}

Where $|X_p|=N_p$ , let P be a permutation of $\{1,\dots,N\}$ that maps

\begin{equation*}X_1\rightarrow \{1,\dots,N_1\},\,X_2\rightarrow \{N_1+1,\dots,N_1+N_2\},\, \text{etc.}.\end{equation*}

Then $v=P^{-1}uP$ is a block diagonal fundamental magic representation. The rest follows immediately.

This gives a theoretical but quickly impractical way of classifying all embeddings $G\subset S_N^+$ up to equivalence.

1. (1) Find all the subsets $A\subset M$ of size $|A|\leq N$ .

2. (2) From these find the subsets A such that

   \begin{equation*}\langle u^p_{ij}\colon p\in A,\,i,j=1,\dots,N_p\rangle= C(G).\end{equation*}

3. (3) For $m_p\in \mathbb{N}_{+}$ , solve:

   \begin{equation*}\sum_{p\in A}m_pN_p=N.\end{equation*}

4. (4) Each solution $(m_p)_{p\in A}\in \mathbb{N}_+^{|A|}$ gives, where each $u^{p_l}$ appears with multiplicity $m_{p_l}$ , an embedding:

   \begin{equation*}u=\operatorname{diag}(u^{p_1},\dots,u^{p_1},u^{p_2},\dots,u^{p_2},\dots,u^{p_{|A|}},\dots,u^{p_{|A|}}),\end{equation*}
   and, up to equivalence, all embeddings $G\subset S_N^+$ are of this form.

This is doable for small finite quantum groups but quickly becomes difficult.

Beyond finding the set of equivalence classes M of transitive magic representations, this is slightly oblique to the Frucht problematics of Sections 6–8, where we will have to consider arbitrary embeddings.

As was observed in [Reference Lupini, Mančinska and Roberson22], the orbit theory of Bichon also has something to say regarding the Haar measure:

Proposition 2.6 If $G\subset S_N^+$ , then where $N_p$ is the size of the orbit of j:

\begin{equation*}\int_G u_{ij}=\begin{cases} 1/N_p, & \mbox{if } i\sim j, \\[3pt] 0, & \mbox{otherwise}. \end{cases}\end{equation*}

In relation with above, we have as well the notion of orbitals, also from [Reference Lupini, Mančinska and Roberson22]:

Definition 2.7 Given a quantum permutation group $G\subset S_N^+$ , we define its orbitals as being the equivalence classes under the following relation:

\begin{equation*}(i,k)\sim(j,l)\iff u_{ij}u_{kl}\neq0.\end{equation*}

We say that G is doubly transitive when we have only two orbitals, which amounts to saying that we must have $u_{ij}u_{kl}\neq0$ for any $i\neq k$ and $j\neq l$ .

In what regards the higher orbitals, things do not seem to work here, as noticed in [Reference Lupini, Mančinska and Roberson22]. As explained in [Reference McCarthy24], with examples, the 3-orbital can fail to be transitive when the diagonal elements of the magic unitary generate a commutative algebra.

3. Finite graphs and the Frucht property

Let $X=(V,E)$ be a finite graph, with vertex set V of size N, and edge set E a symmetric, irreflexive relation on V. When $(i,j)\in E$ then $(j,i)\in E$ also, but we draw only a single, undirected edge between vertices i and j. That X has no loops is accounted for by the edge relation assumed irreflexive.

A permutation $\sigma\in S_N$ leaves invariant the edges precisely when it commutes with the adjacency matrix $d\in M_N(0,1)$ . Thus, the algebra of functions on the automorphism group $G(X)\subset S_N$ is given by:

\begin{equation*}C(G(X))=C(S_N)/\langle du=ud\rangle.\end{equation*}

By dropping the assumption that this algebra commutes, we are led to the following construction, going back to [Reference Banica1]:

Definition 3.1 Given a graph X having N vertices, the construction

\begin{equation*}C(G^+(X))=C(S_N^+)/\langle du=ud\rangle, \end{equation*}

where $d\in M_N(0,1)$ is the adjacency matrix of X, produces a closed subgroup

\begin{equation*}G^+(X)\subset S_N^+,\end{equation*}

called the quantum automorphism group of X.

Observe that we have an inclusion $G(X)\subset G^+(X)$ , which is a liberation, in the sense that the classical version of $G^+(X)$ is the group G(X). This follows indeed from the fact that $S_N\subset S_N^+$ itself is a liberation, explained in section 1 above.

In the sequel we will be interested in quantum subgroups of $G^+(X)$ acting on X.

As a first observation, quantum automorphisms do exist, for instance because the graph having $N\geq 4$ vertices and no edges has $S_N^+\neq S_N$ as quantum automorphism group. There are many other examples, and all this suggests the following definition:

We are interested in determining how the following result from graph theory, established by Frucht in the 1930s, extends to the quantum group setting:

Proof. Given a finite group G, let $S=\{s_1,\dots,s_m\}$ be a generating set that doesn’t contain the identity nor both a non-involution and its inverse. Consider the Cayley graph $X_0=(G,E_0)$ with respect to S. The edge set $E_0\subset G\times G\times\{1,\dots,m\}$ consists of directed edges $(s_k^{-1}g_j,g_j,k)$ of colour k between $s_k^{-1}g_{j}$ and $g_j$ . It can be shown that the group of colour-preserving automorphisms of $X_0$ is isomorphic to G. Where the vertical path graphs below contain k and $k+1$ vertices respectively, replace each directed edge from $g_i$ to $g_j$ of colour k in $X_0$ , with a copy of the following asymmetric, undirected graph:

It can be shown that the resulting finite graph has automorphism group G. See [Reference Frucht18] for full details.

We note that the choice of graph to replace a directed edge of colour k is non-canonical, and, being suitably careful, it is possible to instead use different sets of asymmetric graphs.

The question of whether this result extends to the quantum group setting is a natural one, and was posed explicitly in [Reference Mančinska and Roberson23], and implicitly in [Reference Gromada19].

The tables in Schmidt’s thesis [Reference Schmidt32] comprise a collection of some of the compact quantum groups known to have the Frucht property.

We have the following negative result, coming from [Reference Banica, Bichon and Natale8]:

Proof. This is well-known, the idea being as follows:

1. (1) This is Cayley’s theorem, with the regular representation of a finite group G producing an embedding $G\subset S_N$ , with $N=|G|$ .

2. (2) The regular representation still exists for any finite quantum group G, but does not produce an embedding $G\subset S_N^+$ . And the point is that the quantum Cayley theorem itself fails, with the simplest counterexample being something non-trivial, constructed in [Reference Banica, Bichon and Natale8]. To be more precise, the quantum Cayley theorem holds at $N\leq23$ , but at $N=24$ we have a counterexample, which occurs as a split abelian extension associated to the exact factorisation $S_4 = \mathbb Z_4S_3$ . See [Reference Banica, Bichon and Natale8].

3. (3) This is a trivial consequence of (2).

Here is another negative result, coming this time from [Reference Levin21]:

Proof. Once again this is well-known, the idea being as follows:

1. (1) Conjectured to be the case by Neumann [Reference Neumann27], Levin [Reference Levin21] showed that the modular group $\operatorname{PSL}(2,\mathbb{Z})\cong \mathbb{Z}_2*\mathbb{Z}_3$ is SQ-universal. This means that every countable group can be embedded in a quotient of $\mathbb{Z}_2*\mathbb{Z}_3$ , and this implies that $\mathbb Z_2*\mathbb Z_3$ has uncountably many quotients [Reference Neumann26].

2. (2) This follows from (1), by taking group dual subgroups.

3. (3) This follows from (2), the set of finite graphs being countable.

This non-constructive proof is unsatisfying, and suggests looking at special classes of quantum permutation groups to which the arguments in the proof will not apply, such as:

1. (1) The finite quantum permutation groups. By [Reference Stefan34], at each value of $|G|=\dim C(G)$ there are finitely many such quantum groups.

2. (2) The duals of finite groups.

We will investigate in what follows such questions.

4. Intermediate liberations of finite groups

We discuss in what follows the following notion, mainly coming from Schmidt’s series of papers [Reference Schmidt29, Reference Schmidt30, Reference Schmidt31], and their follow-ups:

Definition 4.1 We call a finite group G quantum-excluding when

\begin{equation*}G(X)=G\implies G^+(X)=G,\end{equation*}

holds for any finite graph X.

It is an open question whether there is a quantum excluding group. Groups known not to be quantum-excluding include $S_N$ ( $N\geq 4$ ), $D_4$ , and $\mathbb{Z}_2\times \mathbb{Z}_2$ . The question is open for cyclic groups, $S_3$ , and $A_N$ .

In relation with our Frucht type questions, discussed in section 3 above, assume that a finite group G has a liberation $G\subset G^\times$ , genuine in the sense that $C(G^\times)$ is noncommutative. Then:

1. (1) If G is known to be quantum-excluding in the sense of Definition 4.1, then $G^\times$ does not have the Frucht property.

2. (2) Equivalently, if $G^\times$ is known to be of the form $G^\times=G^+(X)$ , then the existence of this graph X shows that G cannot be quantum-excluding.

In view of this, the construction of liberations of finite groups $G\subset G^\times$ is an interesting question, that can be useful in the study of quantum automorphism groups, and perhaps more generally.

For a liberation of a compact group $G\subset G^\times \subset U_N^+$ , the standard reconstruction of the commutative $\textrm{C}^*$ -algebra C(G) from its liberation $C(G^\times)$ is via the abelianisation $C(G^\times)/I$ , with $I\subset C(G^\times)$ being the commutator ideal.

When $G^\times\subset S_N^+$ , there is an arguably more transparent approach to finding G, the classical version of $G^\times$ . Consider a map $\Phi$ from the state space of $C(G^\times)$ to the Birkhoff polytope of $N\times N$ doubly stochastic matrices:

\begin{equation*}\Phi(\varphi)=\left[\varphi(u_{ij})\right]_{i,j=1}^N.\end{equation*}

This map was used by Woronowicz to show that commutative Woronowicz algebras are algebras of continuous functions on compact groups $G\subset U_N$ [Reference Woronowicz37].

Where $\jmath$ maps a permutation in $S_N$ to its permutation matrix in $M_N(\mathbb{C})$ , each character $\omega:C(G^\times)\rightarrow \mathbb{C}$ is associated bijectively with some $\sigma\in S_N$ such that

\begin{equation*}\Phi(\omega)=\jmath(\sigma),\end{equation*}

in which case we write $\omega=\operatorname{ev}_{\sigma}$ . These characters form a group with identity $\varepsilon$ and group law given by the convolution:

\begin{equation*}\operatorname{ev}_{\sigma_1}\star \operatorname{ev}_{\sigma_2}=(\operatorname{ev}_{\sigma_1}\otimes \operatorname{ev}_{\sigma_2})\Delta,\end{equation*}

such that:

(2) \begin{equation}\Phi(\operatorname{ev}_{\sigma_1}\star \operatorname{ev}_{\sigma_2})=\Phi(\operatorname{ev}_{\sigma_1})\Phi(\operatorname{ev}_{\sigma_2})=\Phi(\operatorname{ev}_{\sigma_1\sigma_2}).\end{equation}

This finite group is the same as the classical version $G_{\text{class}}$ coming from the abelianisation $C(G^\times)/I$ . When $G^\times$ is finite and so $C(G^\times)$ is a multi-matrix algebra, the one-dimensional summands correspond precisely to the characters. See [Reference McCarthy24] for more.

We recall that for any finite group G we have a Peter–Weyl decomposition, as follows:

\begin{equation*}C(\widehat{G})=\bigoplus_{r\in \operatorname{Irr}(G)}M_{\dim(r)}(\mathbb C).\end{equation*}

We are interested in what follows in the one-dimensional representations, of which there is of course at least the trivial representation $G\to\{1\}$ , corresponding to the counit $\varepsilon:C(\widehat{G})\rightarrow \mathbb{C}$ .

Using these ideas, we have the following elementary result:

Proof. The classical version $\widehat{G}_{\text{class}}$ is indeed abelian because $C(\widehat{G})^*\simeq C(G)$ , and therefore the convolution of characters on $C(\widehat{G})$ is commutative.

Proof. For small cyclic groups, by looking at the relevant degrees of the representations, we obtain liberations as follows:

\begin{equation*}\mathbb Z_1\subset\widehat{A}_5,\end{equation*}

\begin{equation*}\mathbb Z_2\subset\widehat{S}_3,\end{equation*}

\begin{equation*}\mathbb Z_3\subset\widehat{A}_4.\end{equation*}

In general, we will make use of a perfect group, which is by definition a group that equals its commutator subgroup. Such a group has a unique representation of degree one, and therefore the classical version of its dual is trivial.

In practice we can take $A_5$ , which is the smallest perfect group which will produce liberations, via our procedure. If we take:

\begin{equation*}A_5=\langle(123),(345)\rangle,\end{equation*}

we have an embedding $\widehat{A}_5\subset S_6^+$ .

We embed $G\subset S_N$ , say via the Cayley theorem, and we consider a non-trivial finite perfect group $H=\langle h_1,\ldots,h_k\rangle $ . Let us set:

\begin{equation*}M=\operatorname{ord}(h_1)+\ldots+\operatorname{ord}(h_k).\end{equation*}

Consider the tensor product of C(G) and $C(\widehat{H})$ , which is given by:

\begin{equation*}C(G)\otimes C(\widehat{H})=C(G\times \widehat{H}).\end{equation*}

This construction gives a quantum permutation group $G\times\widehat{H}\subset S_{N+M}^+$ , with fundamental magic representation as follows:

\begin{equation*}u^{G\times \widehat{H}}=\begin{pmatrix}u^G\otimes1_{\widehat{H}}&\quad 0 \\0&\quad 1_G\otimes u^{\widehat{H}}\end{pmatrix}.\end{equation*}

Using $M_{N_1}(\mathbb{C})\otimes M_{N_2}(\mathbb{C})\simeq M_{N_1\times N_2}(\mathbb{C})$ , note that as C(G) has $|G|$ one-dimensional factors, and $C(\widehat{H})$ has a single one-dimensional factor, $C(G\times \widehat{H})$ has $|G|$ one-dimensional factors, and thus $|G|$ characters.

It remains to show the group of characters coincides with G. Characters on C(G) are of the form $\operatorname{ev}_\sigma$ :

\begin{equation*}\operatorname{ev}_\sigma:C(G)\rightarrow \mathbb{C},\qquad f\mapsto f(\sigma).\end{equation*}

There is a single character on $C(\widehat{H})$ , necessarily the counit, $\operatorname{ev}_e$ .

The tensor product of $\operatorname{ev}_{\sigma}$ on C(G) and $\operatorname{ev}_e$ on $C(\widehat{H})$ is a character on $C(G\times\widehat{H})$ , and we have

\begin{equation*}\Phi(\operatorname{ev}_{\sigma}\otimes \operatorname{ev}_e)=\begin{pmatrix}\jmath(\sigma)&\quad 0\\0&\quad I_M\end{pmatrix},\end{equation*}

and via (2) we see that the group law on the classical version of $G\times \widehat{H}$ is the same as that of G, as desired.

The above argument is deliberately ad-hoc for $N\leq 3$ as $\widehat{A}_5$ , $\widehat{S}_3$ , $\widehat{A}_4$ provide small finite quantum groups to study in the context of quantum automorphisms.

5. Finite graphs and orbitals

In this section we connect the theory of orbitals with an old observation of Bichon. The complement of E is taken with respect to $V\times V$ minus the diagonal elements:

\begin{equation*}\{(v_1,v_2):v_1,v_2\in V,v_1\neq v_2\}.\end{equation*}

Proposition 5.1 Suppose that $G\subset S_N^+$ . If X is a graph on N vertices, $du=ud$ is equivalent to

\begin{align*}(i,k)\in E,\,(j,l)\in E^c &\implies u_{ij}u_{kl}=0,\text{ and}\\ (i,k)\in E^c,\,(j,l)\in E& \implies u_{ij}u_{kl}=0.\end{align*}

Proof. This goes back to Bichon [Reference Bichon10]. A recent presentation is (Prop. 3.5, [Reference Chassaniol13]).

Classically this can be understood as follows: suppose that $(j,l)\in E$ and $(i,k)\in E^c$ :

If a graph automorphism $\sigma:V\rightarrow V$ maps $l\rightarrow k$ , it cannot also map $j\rightarrow i$ as this would violate

\begin{equation*}(j,l)\in E\implies (\sigma(j),\sigma(l))=(i,k)\in E.\end{equation*}

We will make great use of the contrapositive:

Proposition 5.2 Suppose that $G\subset S_N^+$ . If X is a graph on N vertices, $du=ud$ is equivalent to

\begin{equation*}u_{ij}u_{kl}\neq 0\quad \implies \quad (i,k),(j,l)\in E\text{ or }(i,k),(j,l)\in E^c.\end{equation*}

The following is contained in [Reference Lupini, Mančinska and Roberson22] and is related to the notion of a coherent configuration. The diagonal relation is on $\{1,\dots,N\}$ :

Theorem 5.3 Orbitals of $G\subset S_N^+$ are either subsets of the diagonal relation (corresponding to orbits), or disjoint of the diagonal relation. For each orbital

\begin{equation*}o=\{(i,k)\colon (i,k)\in o\},\end{equation*}

its inverse

\begin{equation*}o^{-1}=\{(k,i)\colon (i,k)\in o\}\end{equation*}

is also an orbital (and it can happen that $o=o^{-1}$ ).

By labelling the vertices $V=\{1,2,\dots,N\}$ , if $G\curvearrowright X$ , the orbitals of $G\subset S_N^+$ are subsets of $V\times V$ .

Proposition 5.4 Suppose that $G\curvearrowright X$ . We have, where $o\subset V\times V$ is the orbital of (i, k),

\begin{equation*}(i,k)\in E\implies (o\cup o^{-1})\subset E.\end{equation*}

Similarly

\begin{equation*}(i,k)\in E^c\implies (o\cup o^{-1})\subset E^c.\end{equation*}

Proof. This follows from the definition of an orbital and Proposition 5.2: suppose that $(i,k)\in E$ and $(j,l)\in o$ . Then

\begin{equation*}u_{ij}u_{kl}\neq 0\implies (j,l)\in E\implies o\subset E.\end{equation*}

With finite graphs assumed symmetric, $o\subset E\implies o^{-1}\subset E$ . The argument is the same if we suppose $(i,k)\in E^c$ and $(j,l)\in o$ .

As the edge relation is irreflexive, the diagonal orbitals are subsets of $E^c$ . The next result provides us with a complete list of the finite graphs on N vertices that $G\subset S_N^+$ acts on:

Theorem 5.5 Let O be the set of orbitals of $G\subset S_N^+$ disjoint of the diagonal relation. For each $A\subset O$ define a graph $X_A=(\{1,\dots,N\},E_A)$ where

\begin{equation*}E_A\,{:\!=}\,\bigcup_{o\in A}(o\cup o^{-1}).\end{equation*}

Then $G\curvearrowright X_A$ . Furthermore, if $G\curvearrowright X$ for X a graph on N vertices, then $X=X_A$ for some $A\subset O$ .

Proof. Suppose that $u_{ij}u_{kl}\neq 0$ , so that $(i,k)\sim (j,l)$ are in the same orbital, say o $^{\prime}$ . By construction of $X_A$ , if $o'\in A$ , both $(i,k),\,(j,l)\in E_A$ ; and if $o'\in A^c$ , then both $(i,k),\,(j,l)\in E_A^c$ . Thus by Proposition 5.2, $G\curvearrowright X_A$ .

That the set of graphs $\{X_A:A\subset O\}$ exhausts the graphs on N vertices that $G\subset S_N^+$ acts on is Proposition 5.4.

Theorem 5.6 Suppose $G\curvearrowright X$ with O the set of orbitals disjoint of the diagonal relation. Suppose $\sigma_1,\dots,\sigma_k\in S_V$ leave the orbitals invariant: for all $\sigma_p\in S_V$ and $o\in O$ ,

\begin{equation*}(i,j)\in o\implies (\sigma_p(i),\sigma_p(j))\in o.\end{equation*}

Then each $\sigma_p\in G(X)$ , and so where $H=\langle\sigma_1,\dots,\sigma_k\rangle$ ,

\begin{equation*}H\subset G(X).\end{equation*}

Finally

\begin{equation*}H \not\subset G_{\text{class}}\implies G\subsetneq G^+(X).\end{equation*}

Proof. We have:

\begin{equation*}G= G^+(X)\implies G_{\text{class}}=G(X),\end{equation*}

and so if $H \not\subset G_{\text{class}}$ , we cannot have $G=G^+(X)$ . The rest follows immediately from Theorem 5.5.

As an illustration, consider the quantum hyperoctahedral group $H_2^+\subset S_4^+$ freely generated by the magic unitary (the conventional presentation, from [Reference Banica, Bichon and Collins6], is got from swapping labels two and three):

\begin{equation*}u=\begin{pmatrix} p_{11} &\quad q_{11} &\quad p_{12} &\quad q_{12} \\ q_{11} &\quad p_{11} &\quad q_{12} &\quad p_{12} \\ p_{21} &\quad q_{21} &\quad p_{22} &\quad q_{22} \\ q_{21} &\quad p_{21} &\quad q_{22} &\quad p_{22} \end{pmatrix}.\end{equation*}

Suppose $H_2^+\subset S_4^+$ acts on a finite graph X. By finding all $u_{ij}u_{kl}\neq 0$ we see that the orbitals disjoint of the diagonal relation are:

\begin{align*} o_1 & =\{(1,3),(1,4),(2,3),(2,4),(3,1),(3,2),(4,1),(4,2)\}, \\[3pt] o_2 & =\{(1,2),(2,1),(3,4),(4,3)\}:\\[-20pt]\end{align*}

Where $s=(14)(23)$ is the ‘switch’, and $b_i\in \{0,1\}$ , each

\begin{equation*}\sigma_{(b_1,b_2,b_3)}=(34)^{b_3}(12)^{b_2}s^{b_1},\end{equation*}

leaves the orbitals invariant. It is the case that $\langle\sigma_{(b_1,b_2,b_3)}\rangle\cong D_4$ , and it follows that for all graphs X on four vertices such that $H_2^+\curvearrowright X$ ,

\begin{equation*}D_4\subset G(X).\end{equation*}

Theorem 5.5 gives all these graphs:

Indeed we know from [Reference Bichon10] that $H_{2,\text{class}}^+=D_4$ , $G^+(\Box)=H_2^+$ , and so $H_2^+$ has the Frucht property.

Proposition 5.7 Suppose that $G\curvearrowright X$ is given by a block magic unitary

\begin{equation*}u=\begin{pmatrix} u^1 & & \\ &\quad \ddots & \\ & &\quad u^k \end{pmatrix}.\end{equation*}

with associated blocks $V_1,\dots,V_k$ forming a partition of V. Each orbital is a subset of some $V_p\times V_q$ .

Proof. This follows from the fact that the orbits of G are blocks, $V_p$ .

We will use the following argument to show that a quantum permutation group G does not have the Frucht property:

1. (1) We assume that an arbitrary embedding $G\subset S_N^+$ acts on a finite graph X.

2. (2) With $G\curvearrowright X$ , the permutation P from Proposition 2.5 can be taken to be a relabelling of V so that u is block diagonal with transitive magic representations:

   \begin{equation*}u=\begin{pmatrix} u^1 & & \\ &\quad \ddots & \\ & &\quad u^k \end{pmatrix}.\end{equation*}
   Furthermore, this relabelling of V can be chosen so that, up to multiplicity, at most one representative from each equivalence class of transitive magic representations appears. We can assume furthermore that transitive magic representations of the same type occurring with multiplicity appear consecutively along the diagonal, i.e.
   \begin{equation*}\operatorname{diag}(u^1,u^1,u^2,u^3,u^{3})\text{ rather than e.g. }\operatorname{diag}(u^3,u^2,u^1,u^1,u^{3}).\end{equation*}
   The m-th appearance of $u^p$ along the diagonal is associated with a block of vertices $V_p^{(m)}\subset \{1,2,\dots,N\}=V$ , and we have a partition
   \begin{equation*}V=\{1,2,\dots,N\}=\bigsqcup_{p,m}V_p^{(m)}.\end{equation*}
   To illustrate the notation, suppose that $G\subset S_7^+$ acts on a graph. Suppose $u^1\in M_{2}(C(G))$ , $u^2\in M_{3}(C(G))$ , and $u=\operatorname{diag}(u^1,u^1,u^2)$ . This partitions
   \begin{equation*}V=\{1,2\}\sqcup\{3,4\}\sqcup\{5,6,7\},\end{equation*}
   and we denote $V_1^{(1)}=\{1,2\}$ , $V_1^{(2)}=\{3,4\}$ , and $V_2^{(1)}=\{5,6,7\}$ .

3. (3) We find, for each $(p,q)\in \{1,\dots,k\}^2$ , the $V_p\times V_q$ orbitals of $G\subset S_N^+$ .

4. (4) We find a large (classical) group of H of permutations of V that leaves both the blocks, and moreover, the orbitals invariant. Using Theorem 5.6, this is an implication:

   \begin{equation*}G\curvearrowright X\implies H \curvearrowright X.\end{equation*}

5. (5) If $H \not\subset G_{\text{class}}$ , by Theorem 5.6,

   \begin{equation*}G^+(X)\neq G,\end{equation*}
   and as X was chosen arbitrarily from all graphs such that $G\curvearrowright X$ , we conclude that G does not have the Frucht property.

With the notation explained, two helpful propositions:

Proposition 5.8 Where $G\subset S_N^+$ with blocks of type $V_p$ of size $N_p$ , and O the set of orbitals disjoint of the diagonal relation, the orbitals of $V_{p}^{(m)}\times V_{p}^{(m+n)}$ are of the form:

\begin{align*} o' &\,{:\!=}\,\{(i,j+nN_p)\colon o\in O,\,(i,j)\in o\} \\[3pt] o_d &=\{(i,i+nN_p)\colon i\in V_{p}^{(m)}\}. \end{align*}

Proof. Implicit here is that the labelling of V has been chosen with all the $V_p$ blocks together:

\begin{equation*}u=\operatorname{diag}(\dots,u^p,\dots,u^p,\dots).\end{equation*}

This means that

\begin{equation*}u_{ij}u_{kl}\neq 0\implies u_{ij}u_{k+nN_p,l+nN_p}\neq 0.\end{equation*}

Finally the diagonal orbital in $V_p^{(m)}\times V_p^{(m)}$ , ordinarily not in play with finite graphs assumed without loops, comes into play via:

\begin{equation*}u_{ij}u_{i+nN_p,j+nN_p}\neq 0.\end{equation*}

Proof. If $V_p\neq V_q$ there is no diagonal relation. Orbitals form a partition of $V_p\times V_q$ and permutations $\sigma\in S_{V}$ induce a permutation $\sigma'$ on $V_p\times V_q$ :

\begin{equation*}(i,j)\mapsto (\sigma(i),\sigma(j)).\end{equation*}

If there are n orbitals $o_1,\dots,o_n$ , and $o_1,\dots,o_{n-1}$ are invariant under $\sigma'$ , then it follows as $\sigma'$ is a permutation that $\sigma'(o_n)=o_n$ .

If $V_p=V_q$ , there is a diagonal orbital, $o_d$ , but the induced permutation $\sigma'$ leaves the diagonal relation invariant.

6. Finite duals

If a group dual $\widehat{\Gamma}\subset S_N^+$ acts on a finite graph X, with appropriate vertex labelling, Bichon’s representation results from [Reference Bichon11] implies that u is a block diagonal matrix of Fourier-type transitive magic representations $u^g$ . Where each $g_p\in\Gamma$ occurs in u with multiplicity $m_p\geq 0$ , and $N_p\,{:\!=}\,\operatorname{ord}(g_p)$ , the group dual action $\widehat{\Gamma}\curvearrowright X$ partitions

\begin{equation*}V\,{:\!=}\,\bigsqcup_{g_p\in\Gamma}\left(\bigsqcup_{m=0}^{m_{p}}V_{p}^{(m)}\right)=\bigsqcup_{g_p\in \Gamma}\left(\bigsqcup_{m=0}^{m_p}\{i^{(m)}_{p},i^{(m)}_{p}+1,\dots,i^{(m)}_p+N_p-1\}\right).\end{equation*}

As explained above, $V_p^{(m)}=\{i^{(m)}_{p},i^{(m)}_{p}+1,\dots,i^{(m)}_p+N_p-1\}$ corresponds to the vertices given by the m-th copy of $u^{g_p}$ in the block diagonal magic unitary u.

Definition 6.1 If $V_p,V_q\subset V$ , and $V_p\times V_q\subset E$ or $V_p\times V_q\subset E^c$ , say that the edge relation between $V_p$ and $V_q$ is total. If $V_p=V_q$ , say that the edge relation is total if for all $i\neq j$ , $(i,j)\in E$ or $(i,j)\in E^c$ .

Furthermore say that a finite group dual $\widehat{\Gamma}$ is total if for all $g_p,g_q\in \Gamma$ , $1\leq i,j\leq N_p$ , and $1\leq k,l\leq N_q$

\begin{equation*}u^{g_p}_{ij}u^{g_q}_{kl}=0\implies u^{g_p},u^{g_q} \text{ are equivalent transitive magic representations}.\end{equation*}

Proof. Let $g_p$ of order $N_p$ and $g_q$ of order $N_q$ give inequivalent transitive magic representations. Let $i,j\in V_{p}$ and $k,l\in V_{q}$ :

\begin{equation*}u_{ij}^{g_p}u_{kl}^{g_q}\neq 0\implies (i,k)\sim (j,l)\implies V_{p}\times V_{q}\text{ is an orbital}.\end{equation*}

This implies via Theorem 5.5 that the relations between inequivalent blocks are total.

This theorem breaks the convention that k denotes the number of blocks in $G\subset S_N^+$ . By Proposition 2.5, we can assume that at most one representative from each equivalence class of transitive magic representations of $C(\widehat{\Gamma})$ appears in $\widehat{\Gamma}\subset S_N^+$ , and k here represents the number of equivalence classes appearing:

Theorem 6.3 Suppose that total $\widehat{\Gamma}\curvearrowright X$ . Let $\Gamma_u=\{g_1,\dots,g_k\}$ be the set of elements of $\Gamma$ appearing as Fourier-type transitive magic representations in the fundamental representation. Then, where $g_1,\dots,g_k$ are of order $N_1,\dots,N_k$ ,

\begin{equation*}\mathbb{Z}_{N_1}\times\cdots \mathbb{Z}_{N_k}\curvearrowright X.\end{equation*}

If $N_p=3$ and $m_{p}=1$ , the copy of $\mathbb{Z}_{N_p}$ can be replaced by $S_3$ .

Proof. Let $g_p\in\Gamma_u$ . Due to the circulant nature of $u^{g_p}$ , with the (lower) index $N_p$ identified with 0 in the (lower) indices of $u^{g_p}$ , for any $i,j\in \{1,\dots,N_p\}$ and $l\in\{0,\dots,N_p-1\}$ :

\begin{equation*}u^{g_p}_{ij}=u^{g_p}_{i+l,j+l}\implies u^{g_p}_{ij}u^{g_p}_{i+l,j+l}\neq 0\implies (i,i+l)\sim (j,j+l).\end{equation*}

This gives a $V_{p}^{(a)}\times V_{p}^{(a)}$ orbital of the form

\begin{equation*}o_l=\{(i,j)\,\colon\, j-i\mod N_p=l\},\end{equation*}

with $o_0$ giving the diagonal relation.

Let us consider now $V_{p}^{(a)}\times V_{p}^{(b)}$ orbitals. Proposition 5.8 gives, for $l\in\{0,\dots,N_p-1\}$ , $V_{p}^{(a)}\times V_{p}^{(b)}$ orbitals of the form:

(3) \begin{equation}o_l^{(a,b)}=\{(i^{(a)}+j_1,i^{(b)}+j_2)\,\colon\, j_2-j_1\mod N_p=l\}.\end{equation}

By Proposition 6.2, for blocks of $V_{p}$ and $V_{q}$ of different type, the unique $V_{p}\times V_{q}$ orbital is $V_{p}\times V_{q}$ itself.

For each $g_p\in \Gamma_u$ , fix $l_p\in \{0,\dots,N_p-1\}$ . Consider the permutation $\sigma_{(l_1,l_2,\dots,l_{k})}$ that maps

\begin{equation*}i^{(m)}_{p}+j\rightarrow i^{(m)}_{p}+(j+l_p\mod N_p).\end{equation*}

Note that

(4) \begin{equation}\sigma_{(l_1,l_2,\dots,l_{k})}(V_{p}^{(m)})=V_{p}^{(m)}.\end{equation}

The edge relation between a $V_{p}^{(m)}$ and an inequivalent block is total, so any permutation of $V_{p}$ will leave the relations there invariant. It remains to show that the permutation above leaves invariant the orbitals between a pair of possibly equal equivalent blocks $V^{(a)}_{g_p},\,V^{(b)}_{g_p}$ .

Let

\begin{equation*}(i^{(a)}_{p}+j_1,i^{(b)}_{p}+j_2)\in o^{(a,b)}_l\implies j_2-j_1\mod N_p=l.\end{equation*}

Then $(\sigma_{(l_1,l_2,\dots,l_{k})}(i^{(a)}_{p}+j_1),\sigma_{(l_1,l_2,\dots,l_{k})}(i^{(b)}_{p}+j_2))$ is equal to

\begin{equation*}(i^{(a)}_{p}+(j_1+l_p\mod N_p),i^{(b)}_{p}+(j_2+l_p\mod N_p)).\end{equation*}

If $j_2-j_1\mod N_p=l$ then

\begin{equation*}((j_2+l_p\mod N_p)-(j_1+l_p\mod N_p))\mod N_p=l\end{equation*}

\begin{align*}\implies (\sigma_{(l_1,l_2,\dots,l_{k})}(i^{(a)}_{p}+j_1),\sigma_{(l_1,l_2,\dots,l_{k})}(i^{(b)}_{p}+j_2))\in o_l^{(a,b)}\\[-6pt]\end{align*}

and so by Theorem 5.6 the abelian group

\begin{equation*}\langle\sigma_{(l_1,l_2,\dots,l_k)} \colon l_p\in \{0,\dots, N_p-1\}\rangle\cong \mathbb{Z}_{N_1}\times\cdots \mathbb{Z}_{N_k}\end{equation*}

is a subgroup of G(X).

If $N_p=3$ and $m_{p}=1$ , then the induced subgraph of $V_{p}=\{i^{(1)}_{p},i_{p}^{(1)}+1,i_{p}^{(1)}+2\}$ is complete or edgeless, and it follows that the copy of $\mathbb{Z}_{N_p}$ can be taken to be $S_3$ .

As an illustration of Theorem 6.3, consider the total finite dual $\widehat{S_3}$ with $\widehat{S_3}\subset S_5^+$ given by $u=\operatorname{diag}(u^{(12)},u^{(123)})$ . There are five orbitals disjoint of the diagonal relation:

\begin{align*} o_1 & =\{(1,2),(2,1)\} \\[3pt] o_2 & =\{1,2\}\times\{3,4,5\} \\[3pt] o_2^{-1}&=\{3,4,5\}\times\{1,2\} \\[3pt] o_3&=\{(3,4),(4,5),(5,3)\} \\[3pt] o_3^{-1}&=\{(3,5),(5,4),(4,3)\}\end{align*}

Theorem 5.5 thus gives eight graphs on five vertices that $\widehat{S_3}$ acts on, and each admits a $\mathbb{Z}_2\times S_3$ action:

Proof. If $\Gamma$ is non-abelian it is not cyclic, and so any generating set has more than two elements. If $\widehat{\Gamma}$ is total, then by Theorem 6.3, a non-trivial abelian group with a composite number of elements is a subgroup of G(X). However if $G^+(X)=\widehat{\Gamma}$ , then $G(X)=\widehat{\Gamma}_{\text{class}}\cong \mathbb{Z}_p$ which has no non-trivial subgroups.

Proof. We observed in Proposition 4.3 that $S_3$ , $A_4$ , $A_5$ have, respectively, two, three, and one, one-dimensional representations.

We claim that each of these finite duals is total. A sufficient condition for totality of $\widehat{\Gamma}$ is that for inequivalent transitive magic representations $u^{g_p},\,u^{g_q}$ the $N_p\cdot N_q$ matrix with entries in $C(\widehat{\Gamma})$ :

(5) \begin{equation}K(g_p,g_q)\,{:\!=}\,\left[g_p^mg_q^n\right]_{m=1,\dots,N_p,\,n=1,\dots,N_q},\end{equation}

contains a unique entry, say $g^*$ . This implies that

\begin{equation*}u_{ij}^{g_p}u_{kl}^{g_q},\end{equation*}

a formal sum in $\Gamma$ , contains a single non-zero multiple of $g^*$ , and so cannot be zero. Note that by writing down the Fourier-type transitive magic representation $u^{g_p}$ , we can see that if $g_p,\,g_q\in \Gamma$ are of both of order three or both of order five, and $\langle g_p\rangle=\langle g_q\rangle$ , then the Fourier-type transitive magic representations $u^{g_p}$ and $u^{g_q}$ are equivalent.

In $\widehat{S_3}$ the only pair of equivalent transitive magic representations are those given by (123) and (132). It follows quickly that $\widehat{S_3}$ is total.

In $A_4$ there are eight three-cycles, three disjoint two-cycles, and the identity, giving eight inequivalent representations. If $\tau_1,\, \tau_2$ are inequivalent disjoint two-cycles, then both are unique entries in $K(\tau_1,\tau_2)$ . Given inequivalent three-cycles $\sigma_1,\,\sigma_2$ , as $\sigma_1^{-1}=\sigma_1^2$ and $(\sigma_1^2)^{-1}=\sigma_1$ , the identity is a unique entry in $K(\sigma_1,\sigma_2)$ with a similar situation for $K(\tau_1,\sigma_1)$ .

In $A_5$ there are 24 five-cycles (six equivalence classes $f_1,\dots f_6$ ), 20 three-cycles (10 equivalence classes $\sigma_1,\dots,\sigma_{10}$ ), 15 disjoint two-cycles $\tau_1,\dots,\tau_{15}$ and the identity. Assuming inequivalent representations, similarly to $A_4$ , the identity is a unique entry in each of

\begin{equation*}K(f_a,f_b),\,K(\sigma_c,\sigma_d),\,K(\tau_k,\tau_l).\end{equation*}

For the mixed cases note that the inverse of any k-cycle is a k-cycle, and the inverse of the disjoint two-cycle is itself. It follows that for any K with inputs of inequivalent type the identity is a unique entry.

The smallest examples of non-total non-abelian group duals are the duals of the dihedral group, where for example, $u^{r}_{11}u^{r^2}_{21}=0$ , and the quaternion group, where, for example, $u_{11}^ju_{21}^k=0$ . Both these finite duals have classical version $\mathbb{Z}_2\times\mathbb{Z}_2$ .

Perfect groups $\Gamma$ provide intermediate liberations $\mathbb{Z}_1\subset \widehat{\Gamma}$ that are potential counterexamples to $\mathbb{Z}_1$ is quantum-excluding. The previous results show that if perfect and total $\widehat{\Gamma}\curvearrowright X$ , then $G(X)\neq \mathbb{Z}_1$ . The binary icosahedral group 2I is an example of a perfect group which is not total. It is an order 120 subgroup of the unit quaternions, and has order six and order 10 generators:

\begin{equation*}s=\frac12(1+i+j+k)\text{ and }t=\frac12(\varphi1+\varphi^{-1}i+j).\end{equation*}

Here $\varphi=\frac{1+\sqrt{5}}{2}$ is the golden ratio. Direct calculation shows that, for example:

\begin{equation*}u^{s}_{11}u^t_{51}=0.\end{equation*}

Perhaps speculatively, such a dual is deserving of further study. With it being non-total, Theorem 6.3 is not a barrier to $\widehat{2I}$ having the Frucht property. If $\widehat{2I}$ does have the Frucht property, a graph X such that $G^+(X)=\widehat{2I}$ is a graph with quantum symmetries but with trivial (classical) automorphism group. Furthermore, such a graph will have quantum symmetries with a finite quantum automorphism group.

Even if $\widehat{2I}$ does not have the Frucht property, if $\widehat{2I}\curvearrowright X$ such that $G(X)=\mathbb{Z}_1$ , then X is a graph with quantum symmetries but with trivial (classical) automorphism group.

7. The Kac–Paljutkin quantum group

7.1 Magic Representation Theory

The Kac–Paljutkin quantum group of order eight [Reference Kac and Paljutkin20], $G_0$ , has algebra of functions structure:

(6) \begin{equation}C(G_0)=\mathbb{C}\oplus\mathbb{C}\oplus\mathbb{C}\oplus\mathbb{C}\oplus M_2(\mathbb{C}).\end{equation}

The choice to denote this finite quantum group by $G_0$ harks back to the original notation of [Reference Kac and Paljutkin20], and the zero reminds this is a ‘ground zero’ for compact quantum groups, the smallest one neither commutative nor cocommutative. Let us denote by $f_1,f_2,f_3,f_4$ the generators of the four copies of $\mathbb{C}$ and by $E_{ij}$ , $1\leq i,j\leq 2$ the standard generators of $M_2(\mathbb{C})$ .

The counit is given by $\varepsilon(f_1)=1$ (and zero elsewhere). The antipode is given by $S(f_i)=f_i$ , and, where $E_{kl}$ are matrix units in the two dimensional summand, $S(E_{kl})=E_{lk}$ . The comultiplication is well presented in [Reference Franz and Gohm17]. The Haar measure is given by:

\begin{equation*}\int_{G_0}f_i=\frac{1}{8}\text{, and }\int_{G_0}E_{kl}=\frac{\delta_{kl}}{4}.\end{equation*}

Where $I_2$ is the identity in the $M_2(\mathbb{C})$ summand, and the projection

(7) \begin{equation}p\,{:\!=}\,\left(0,0,0,0,\left(\begin{array}{c@{\quad}c} \frac12 & \frac12 e^{-i\pi/4} \\ \frac12 e^{+i\pi/4} & \frac12 \end{array}\right)\right),\end{equation}

a concrete exhibition of $G_0\subset S_4^+$ (Th. 1.1 (8), [Reference Banica and Bichon5]) comes by the fundamental magic representation:

(8) \begin{align}u^{G_0}\,{:\!=}\,\left[\begin{array}{c@{\quad}c@{\quad}c@{\quad}c} f_1+f_2 & f_3+f_4 & p & I_2-p \\ f_3+f_4 & f_1+f_2 & I_2-p & p \\ p^T & I_2-p^T & f_1+f_3 & f_2+f_4 \\ I_2-p^T & p^T & f_2+f_4 & f_1+f_3 \end{array}\right]. \end{align}

Another transitive magic representation $w\in M_4(C(G_0))$ , whose entries do not generate $C(G_0)$ , is given by:

(9) \begin{equation}w=\begin{pmatrix} f_1+f_4 &\quad f_2+f_3 &\quad E_{11} &\quad E_{22} \\ \\[-7pt] f_2+f_3 &\quad f_1+f_4 &\quad E_{22} &\quad E_{11} \\ \\[-7pt] E_{11} &\quad E_{22} &\quad f_1+f_4 &\quad f_2+f_3 \\ \\[-7pt] E_{22} &\quad E_{11} &\quad f_2+f_3 &\quad f_1+f_4 \end{pmatrix}.\end{equation}

There are three transitive magic representations $x,y,z\in M_2(G_0)$ given by

(10) \begin{align}x& =\begin{pmatrix} f_1+f_2+f_3+f_4 &\quad I_2 \\ \\[-7pt] I_2 &\quad f_1+f_2+f_3+f_4 \end{pmatrix},\end{align}

(11) \begin{align}y& =\begin{pmatrix} f_1+f_4+E_{11} &\quad f_2+f_3+E_{22}\\ \\[-7pt] f_{2}+f_3+E_{22} &\quad f_1+f_4+E_{11} \end{pmatrix},\end{align}

(12) \begin{align} z& =\begin{pmatrix} f_1+f_4+E_{22} &\quad f_2+f_3+E_{11} \\ \\[-7pt] f_{2}+f_3+E_{11} &\quad f_1+f_4+E_{22} \end{pmatrix}. \\[-10pt]\nonumber\end{align}

Proposition 7.1 The full set of inequivalent transitive magic representations of $C(G_0)$ is

\begin{equation*}M=\{u^{G_0},w,x,y,z,1_{G_0}\}.\end{equation*}

If $G_0\subset S_N^+$ , then u can be taken to be block diagonal, with blocks from M, with $u^{G_0}$ necessarily appearing.

Proof. We have to show in the first instance that there are, up to equivalence, only six transitive magic representations.

1. (1) The only magic unitary in $M_1(C(G_0))$ is $1_{\mathfrak{G_0}}$ .

2. (2) Suppose v is a transitive magic representation in $M_2(C(G_0))$ . Suppose the $M_2(\mathbb{C})$ factor of $v_{11}$ is zero. As we must have by Proposition 2.6 $\int_{G_0} v_{11}=1/2$ , it follows that $v_{11}=x_{11}$ and so $v=x$ .

   We cannot have $v_{11}=I_2$ , as we must have $\varepsilon(v_{11})=1$ . Therefore assume we split $I_2=q+(I_2-q)$ into rank one projections:

   \begin{equation*}q=\begin{pmatrix} q_{11} &\quad q_{12} \\ \\ \\[-7pt] q_{21} &\quad 1-q_{11} \end{pmatrix}\implies \int_{G_0}q=\frac14.\end{equation*}
   Furthermore to satisfy $\int_{G_0} v_{11}=1/2$ , we must have, where i, j, k is a permutation of $\{2,3,4\}$ :
   \begin{equation*}v=\begin{pmatrix} f_1+f_i+q &\quad f_j+f_k+I_2-q \\ \\ \\[-7pt] f_j+f_k+I_2-q &\quad f_1+f_i+q \end{pmatrix}.\end{equation*}
   Suppose that $i\neq 4$ . When we examine the comultiplication (see [Reference Franz and Gohm17]), we note that the coefficient of $E_{11}\otimes E_{11}$ in $\Delta(f_1)$ and $\Delta(f_4)$ is $1/2$ , and they are the only basis elements to have such a term in their comultiplication. To have:
   \begin{equation*}\Delta(v_{11})=v_{11}\otimes v_{11}+v_{12}\otimes v_{21},\end{equation*}
   we require therefore that the coefficient of $E_{11}\otimes E_{11}$ in
   \begin{equation*}q\otimes q+(I_2-q)\otimes(I_2-q),\end{equation*}
   is also $1/2$ . That is we require:
   \begin{equation*}q_{11}^2+(1-q_{11})^2=\frac12 \implies q_{11}=\frac12.\end{equation*}
   This implies further that
   \begin{equation*}q=\begin{pmatrix} \frac12 &\quad \frac12 e^{i\theta} \\ \\[-7pt] \frac12 e^{-i\theta} &\quad \frac12 \end{pmatrix}.\end{equation*}
   Now we examine the coefficient of $E_{21}\otimes E_{12}$ in $\Delta(v)=v_{11}\otimes v_{11}+v_{12}\otimes v_{21}$ . This is:
   (13) \begin{equation}\frac12 e^{-i\theta}\frac12 e^{i\theta}+\left(-\frac12 e^{-i\theta}\right)\left(-\frac12 e^{i\theta}\right)=+\frac12.\end{equation}
   However the coefficients of $E_{21}\otimes E_{12}$ in $\Delta(f_2)$ and $\Delta(f_3)$ are $\pm i/2$ . We conclude we cannot have $i\neq 4$ .

   Now suppose that $i=4$ . The coefficient of $E_{11}\otimes E_{11}$ in $\Delta(f_1+f_4+q)$ is one, implying that $q=E_{11}$ or $E_{22}$ . With $q=E_{11}$ we get y, and with $q=E_{22}$ we get z.

3. (3) We cannot have a transitive magic representation $u\in M_3(C(G_0))$ as we cannot achieve $\int_G u_{ij}=1/3$ . Similar considerations rule out transitive magic representations of size greater than four.

4. (4) It remains to show that, up to relabelling, w and $u^{G_0}$ are the unique transitive magic representations in $M_4(C(G_0))$ . Suppose u is a transitive magic representation in $M_4(C(G_0))$ . From the arguments above concerning the Haar measure and the counit, we know that the first row must be $f_1+f_i$ followed by a permutation of $\{f_j+f_k,q,I_2-q\}$ , for some rank one projection $q\in M_2(\mathbb{C})$ . We can assume without loss of generality that

   \begin{equation*}u=\begin{pmatrix} f_1+f_i &\quad f_j+f_k &\quad q &\quad I_2-q \\ \\[-7pt] * &\quad * &\quad * &\quad * \\ \\[-7pt] * &\quad * &\quad * &\quad * \\ \\[-7pt] * &\quad * &\quad * &\quad * \end{pmatrix}.\end{equation*}
   Inspection of the comultiplication shows that where A is the direct sum of the one dimensional summands in $C(G_0)$ , and B the two dimensional summand:
   \begin{equation*}\Delta(A)\subset A\otimes A+B\otimes B\text{ and }\Delta(B)=A\otimes B+B\otimes A.\end{equation*}
   In addition, with the antipode on B given by the transpose, $S(u_{ij})=u_{ji}$ , and with a, b, c another permutation of $\{2,3,4\}$ , this implies that u must be of the form :
   \begin{equation*}u=\begin{pmatrix} f_1+f_i &\quad f_j+f_k &\quad q &\quad I_2-q \\ \\[-7pt] f_j+f_k &\quad f_1+f_i &\quad I_2-q &\quad q \\ \\[-7pt] q^T &\quad I_2-q^T &\quad f_1+f_a &\quad f_b+f_c \\ \\[-7pt] I_2-q^T &\quad q^T &\quad f_b+f_c &\quad f_1+f_a \end{pmatrix}.\end{equation*}

5. (a) Suppose that $i=2$ :

   \begin{equation*}u=\begin{pmatrix} f_1+f_2 &\quad f_3+f_4 &\quad q &\quad I_2-q \\ \\[-7pt] f_3+f_4 &\quad f_1+f_2 &\quad I_2-q &\quad q \\ \\[-7pt] q^T &\quad I_2-q^T &\quad f_1+f_a &\quad f_b+f_c \\ \\[-7pt] I_2-q^T &\quad q^T &\quad f_b+f_c &\quad f_1+f_a \end{pmatrix}.\end{equation*}
   By looking at the $E_{11}\otimes E_{11}$ term in $\Delta(u_{11})$ and in
   \begin{equation*}u_{13}\otimes u_{31}+u_{14}\otimes u_{41}= q\otimes q^T+(I_2-q)\otimes (I_2-q^T),\end{equation*}
   we find:
   \begin{equation*}q_{11}^2+(1-q_{11})^2=\frac{1}{2}\implies q_{11}=\frac{1}{2},\end{equation*}
   and so
   \begin{equation*}q=\begin{pmatrix} \frac12 &\quad \frac12 e^{i\theta} \\ \\[-7pt] \frac{1}{2}e^{-i\theta} &\quad \frac12 \end{pmatrix}\text{ and }q^T=\begin{pmatrix} \frac12 & \frac12 e^{-i\theta} \\ \frac{1}{2}e^{+i\theta} & \frac12 \end{pmatrix}.\end{equation*}
   Examining now the $E_{21}\otimes E_{12}$ terms in $\Delta(u_{11})$ and in $u_{13}\otimes u_{31}+u_{14}\otimes u_{41}$ we find
   \begin{equation*} \frac12 e^{-i\theta}\frac12 e^{-i\theta}+\left(-\frac12 e^{-i\theta}\right)\left(-\frac12 e^{-i\theta}\right)=\frac{i}{2}\end{equation*}
   \begin{align*} \implies \theta&= -\pi/4 \\ \implies q&=p, \end{align*}
   as in p from (7). This implies that we have:
   \begin{equation*}u=\begin{pmatrix} f_1+f_2 &\quad f_3+f_4 &\quad p &\quad I_2-p \\ \\[-7pt] f_3+f_4 &\quad f_1+f_2 &\quad I_2-p &\quad p \\ \\[-7pt] p^T &\quad I_2-p^T &\quad f_1+f_a &\quad f_b+f_c \\ \\[-7pt] I_2-p^T &\quad p^T &\quad f_b+f_c &\quad f_1+f_a \end{pmatrix}.\end{equation*}
   The coefficient of $E_{12}\otimes E_{21}$ in $\Delta(u_{33})$ here is $+i/2$ but only $\Delta(f_3)$ contains such a term and we conclude that $a=3$ , and $u=u^{G_0}$ .

6. (b) Carrying out the same analysis for $i=3$ we find the rank one projection $q=p^T$ . Subsequently looking at the $E_{21}\otimes E_{12}$ coefficient of $\Delta(u_{33})$ gives:

   \begin{equation*}u=\begin{pmatrix} f_1+f_3 &\quad f_2+f_4 &\quad p^T &\quad I_2-p^T \\ \\[-7pt] f_2+f_4 &\quad f_1+f_3 &\quad I_2-p^T &\quad p^T \\ \\[-7pt] p &\quad I_2-p & f_1+f_2 &\quad f_3+f_4 \\ \\[-7pt] I_2-p &\quad p &\quad f_3+f_4 &\quad f_1+f_2 \end{pmatrix}.\end{equation*}
   Where P is the permutation matrix of (13)(24):
   \begin{equation*}u^{G_0}=PuP^{-1},\end{equation*}
   and u is equivalent to $u^{G_0}$

7. (c) If $i=4$ then we have

   \begin{equation*}u=\begin{pmatrix} f_1+f_4 &\quad f_2+f_3 &\quad q &\quad I_2-q \\ \\[-7pt] f_3+f_2 &\quad f_1+f_4 &\quad I_2-q &\quad q \\ \\[-7pt] q^T &\quad I_2-q^T &\quad f_1+f_a &\quad f_b+f_c \\ \\[-7pt] I_2-q^T &\quad q^T &\quad f_b+f_c &\quad f_1+f_a \end{pmatrix}.\end{equation*}
   Examining the coefficient of $E_{11}\otimes E_{11}$ in $\Delta(u_{11})$ we require $q=E_{11}$ or $E_{22}$ . If $q=E_{11}$ :
   \begin{equation*}u=\begin{pmatrix} f_1+f_4 &\quad f_2+f_3 &\quad E_{11} &\quad E_{22} \\ \\[-7pt] f_3+f_2 &\quad f_1+f_4 &\quad E_{22} &\quad E_{11} \\ \\[-7pt] E_{11} &\quad E_{22} &\quad f_1+f_a &\quad f_b+f_c \\ \\[-7pt] E_{22} &\quad E_{11} &\quad f_b+f_c &\quad f_1+f_a \end{pmatrix}.\end{equation*}
   Examining $\Delta(u_{31})=\Delta(E_{11})$ we must have $a=4$ and so:
   \begin{equation*}u=\begin{pmatrix} f_1+f_4 &\quad f_2+f_3 &\quad E_{11} &\quad E_{22} \\ \\[-7pt] f_3+f_2 &\quad f_1+f_4 &\quad E_{22} &\quad E_{11} \\ \\[-7pt] E_{11} &\quad E_{22} &\quad f_1+f_4 &\quad f_2+f_3 \\ \\[-7pt] E_{22} &\quad E_{11} &\quad f_2+f_3 &\quad f_1+f_4 \end{pmatrix}=w.\end{equation*}
   If we go back and let $q=E_{22}$ , we get a transitive magic representation equivalent to w by the permutation matrix P corresponding to (34).

Note finally that we cannot generate $C(G_0)$ without including $u^{G_0}$ . Proposition 2.5 gives the rest.

7.2 Orbitals

Where $u^{G_0}$ occurs with multiplicity $m_0\geq 1$ , $r\in\{w,x,y,z\}$ appears with multiplicity $m_r\geq 0$ , and $1_{G_0}$ occurs with multiplicity $m_1\geq 0$ , the action $G_0\curvearrowright X$ partitions

\begin{align*}V&=\left(\bigsqcup_{m=1}^{m_0}V_0^{(m)}\right)\sqcup \left(\bigsqcup_{r\in \{w,x,y,z\}}\left(\bigsqcup_{m=0}^{m_r}V_r^{(m)}\right)\right)\sqcup\left(\bigsqcup_{m=0}^{m_1} V_{1}^{(m)}\right). \end{align*}

In terms of orbital types, there are 12 type $V_p\times V_p$ orbitals, and 15 type $V_p\times V_q$ orbitals to study. Where $r,t\in\{x,y,z\}$ , $r\neq t$ , and $s\in\{y,z\}$ , the following 15 edge relations are total:

\begin{equation*}V_0\times V_s,\quad V_0\times V_1,\quad V_w\times V_1,\quad V_r^{(a)}\times V_r^{(a)},\quad V_r\times V_t, \quad V_r\times V_1,\quad V_1^{(a)}\times V_1^{(a)},\quad V_1^{(a)}\times V_1^{(b)}.\end{equation*}

Here with $r\in\{x,y,z\}$ , 12 orbital types remain:

\begin{equation*} V_0^{(a)}\times V_0^{(a)},\quad V_{0}^{(a)}\times V_{0}^{(b)},\quad V_0\times V_w,\quad V_0\times V_x,\end{equation*}

\begin{equation*}V_w^{(a)}\times V_w^{(a)},\quad V_w^{(a)}\times V_w^{(b)},\quad V_w\times V_r,\quad V_r^{(a)}\times V_{r}^{(b)}.\end{equation*}

We will determine these in a series of propositions.

The choice to label V according to Proposition 7.1 means that blocks are consecutive integers, and to use only the six transitive magic representations listed, and not the other transitive magic representations equivalent to $u^{G_0}$ and respectively w, confers a fixed orientation to any four block $\{i,i+1,i+2,i+3\}$ of type $V_0$ or $V_w$ . When we draw a four block as a square we assume a clockwise orientation, and when we draw a block $\{j,j+1,j+2,j+3\}$ or $\{k,k+1\}$ as a vertical line, we assume an orientation where ‘down’ is the positive direction:

This first proposition implicitly describes the $V_0^{(a)}\times V_0^{(a)}$ orbitals:

Proposition 7.2 If $G_0\curvearrowright X$ , we have that the induced subgraph $X(V_0^{(m)})$ is one of:

Proof. This follows in the same manner to that of $H_2^+\subset S_4^+$ acting on a graph (worked out as an illustration of Theorem 5.6). Of most importance are the middle graphs which are the $V_0^{(a)}\times V_0^{(a)}$ orbitals.

Proposition 7.3 Suppose $G_0\curvearrowright X$ with $m_0\geq 2$ . Then the $V_0^{(a)}\times V_0^{(b)}$ orbitals are:

Proof. Here are the $V_0^{(a)}\times V_0^{(b)}$ orbitals.

\begin{align*}o_d&=\{(i^{(a)}+j,i^{(b)}+j)\colon j\in\{0,\dots,3\}\}\\[3pt] o_b&=\{(i^{(a)},i^{(b)}+1),(i^{(a)}+1,i^{(b)}),(i^{(a)}+2,i^{(b)}+3),(i^{(a)}+3,i^{(b)}+2)\}\\[3pt] o_s&=[\{i^{(a)},i^{(a)}+1\}\times\{i^{(b)}+2,i^{(b)}+3\}]\cup [\{i^{(a)}+2,i^{(a)}+3\}\times\{i^{(b)},i^{(b)}+1\}]\end{align*}

From Proposition 7.2, there are two orbitals disjoint of the diagonal relation with $G_0\subset S_4^+$ , and $o_b$ and $o_s$ correspond to these relations. As per Proposition 5.8, the third orbital $o_d$ comes from the relations of the diagonal orbital.

The following propositions are proven by routine calculations based on the defining formulas (8)–(12).

Proposition 7.4 Suppose $G_0\curvearrowright X$ with $m_w\geq 1$ . Then the $V_0\times V_w$ orbitals are:

Proposition 7.5 Suppose $G_0\curvearrowright X$ with $m_x\geq 1$ . Then the $V_0\times V_x$ orbitals are:

Proposition 7.6 Suppose $G_0\curvearrowright X$ with $m_w\geq 1$ . Then the $V_w^{(a)}\times V_w^{(a)}$ orbitals are:

Proof. By looking for $w_{ij}w_{kl}\neq 0$ we find three $V_w\times V_w$ orbitals disjoint of the diagonal:

\begin{align*} o_1 & =\{(1,2),(2,1),(3,4),(4,3)\} \\[7pt] o_2 & =\{(1,3),(2,4),(3,1),(4,2)\} \\[7pt] o_3 & =\{(1,4),(2,3),(3,2),(4,1)\} \\[-40pt] \end{align*}

Proposition 7.7 Suppose $G_0\curvearrowright X$ with $m_w\geq 2$ . There are four $V_w^{(a)}\times V_{w}^{(b)}$ orbitals:

Proof. By Proposition 5.8, we have three orbitals from Proposition 7.6 as well as another coming from the diagonal relation.

Proposition 7.8 Suppose $G_0\curvearrowright X$ with $m_w,m_{x}\geq 1$ . The $V_w\times V_x$ orbitals are the same as the $V_0\times V_x$ orbitals.

Proposition 7.9 Suppose $G_0\curvearrowright X$ with $m_w,m_{y}\geq 1$ . There are two $V_w\times V_y$ orbitals:

Proposition 7.10 Suppose $G_0\curvearrowright X$ with $m_w,m_{z}\geq 1$ . There are two $V_w\times V_z$ orbitals:

Proposition 7.11 Let $r\in\{x,y,z\}$ . Suppose $G_0\curvearrowright X$ with $m_r\geq 2$ . The $V_r^{(a)}\times V_r^{(b)}$ orbitals are:

7.3 The Frucht property

Theorem 7.12 The Kac–Paljutkin quantum group does not have the Frucht property.

Proof. Assume that $G_0\curvearrowright X$ . Consider the following copy of $D_4$ in $S_4$ :

(14) \begin{equation}D_4=\{e,(12),(34),(12)(34),(13)(24),(14)(23),(1324),(1423)\}.\end{equation}

Where $s=(14)(23)$ , each $\omega\in D_4$ is of the form, for some $b_i\in \{0,1\}$ ,

\begin{equation*}\omega_{(b_1,b_2,b_3)}=(34)^{b_3}(12)^{b_2}s^{b_1}.\end{equation*}

Let $\omega_{(b_1,b_2,b_3)}\in D_4$ and define a permutation $\sigma_{(b_1,b_2,b_3)}$ of V as follows:

(15) \begin{align} V_{0}\ni i+l & \quad\longmapsto\quad i+\omega_{(b_1,b_2,b_3)}(l+1)-1.\nonumber \\[3pt] V_{w}\ni i+l & \quad\longmapsto\quad i+[(13)(24)]^{b_1}(l+1)-1 \end{align}

(16) \begin{align} V_{x}\ni j+l & \quad\longmapsto\quad j+(l+b_1\mod 2) \end{align}

(17) \begin{align} V_{y}^{m}\ni j+l&\quad\longmapsto\quad j+l\end{align}

(18) \begin{align} V_{z}\ni j+l & \quad\longmapsto\quad j+(l+b_1\mod 2) \end{align}

\begin{align*} V_{1}\ni k & \quad\longmapsto\quad k\nonumber \end{align*}

More succinctly:

1. (1) $V_0$ blocks take a full $D_4$ action.

2. (2) $V_w$ blocks only take a $\mathbb{Z}_2$ action.

3. (3) $V_x$ and $V_y$ blocks take a $\mathbb{Z}_2$ action.

4. (4) $V_y$ and $V_1$ blocks are fixed.

Note in all cases that $\sigma_{(b_1,b_2,b_3)}(V_p)=V_p$ .

We are going to show that each $\sigma_{(b_1,b_2,b_3)}$ leaves the orbitals invariant, and therefore by Theorem 5.6, they are each automorphisms of X.

We do not have to worry about the 15 orbitals that yield total edge relations: any $V_p^{(m)}$ -invariant permutation of V will leave these edges invariant.

By Proposition 5.9, we can check that $\sigma_{(b_1,b_2,b_3)}$ leaves invariant all but one orbital to show that it leaves all orbitals invariant.

1. (1) $V_0^{(a)}\times V_{0}^{(a)}$ : one of two orbitals is $\Box$ , which admits a $D_4$ action. We just note that the permutations given by (14) are the correct ones.

2. (2) $V_0^{(a)}\times V_{0}^{(b)}$ : the two orbitals are given in Proposition 7.3. By Proposition 5.9, we need only check the first two orbitals, and a quick inspection shows they are invariant under $\sigma_{(b_1,b_2,b_3)}$ .

3. (3) $V_0\times V_w=\{i,i+1,i+2,i+3\}\times\{j,j+1,j+2,j+3\}$ : for the first orbital the relation between $\{i,i+1\}$ and $\{j,j+1\}$ , and the relation between $\{i+2,i+3\}$ and $\{j+2,j+3\}$ are total. Therefore, permutations that leave these four subsets invariant will leave the orbital invariant. If $b_1=0$ then

   \begin{equation*}\{i,i+1\},\,\{i+2,i+3\},\,\{j,j+1\},\,\{j+2,j+3\}\end{equation*}
   are all invariant for $\sigma_{(0,b_2,b_3)}$ . If $b_1=1$ , then
   \begin{equation*}\{i,i+1\}\longleftrightarrow \{i+2,i+3\},\end{equation*}
   and, by (15), we also have
   \begin{equation*}\{j,j+1\}\longleftrightarrow \{j+2,j+3\},\end{equation*}
   and it follows that the first orbital (and therefore both orbitals) are invariant for all $\sigma_{(b_1,b_2,b_3)}$ .

4. (4) $V_0\times V_x=\{i,i+1,i+2,i+3\}\times\{j,j+1\}$ : note that by Proposition 7.5, for the first orbital, the edge relations between $\{i,i+1\}$ and $\{j\}$ , and between $\{i+2,i+3\}$ and $\{j+1\}$ are total. If $b_1=0$ , then $\{i,i+1\}$ and $\{i+2,i+3\}$ are invariant, but $V_x$ is fixed and so the orbitals are invariant. By (16), if $b_1=1$ , then $\{j\}\longleftrightarrow \{j+1\}$ switches with $\{i,i+1\}\longleftrightarrow \{i+2,i+3\}$ , and the therefore the first orbital is invariant (and therefore all are invariant).

5. (5) $V_w^{(a)}\times V_{w}^{(a)}=\{i,i+1,i+2,i+3\}\times\{i,i+1,i+2,i+3\}$ : there are only two possible actions: the $b_1=0$ identity action, that leaves everything invariant, and the $b_1=1$ action (cyclic notation):

   \begin{equation*}(i,i+2)(i+1,i+3),\end{equation*}
   which leaves invariant the first two orbitals in Proposition 7.6, and hence all such orbitals.

6. (6) $V_w^{(a)}\times V_w^{(b)}$ : similarly to (5), the action is either the identity or an involution, both leaving all orbitals invariant.

7. (7) $V_w\times V_x$ : looking at the first orbital, and $V_w$ and $V_x$ either both fixed, or both taking an involution, we see that the orbitals are left invariant.

8. (8) $V_w\times V_y=\{i,i+1,i+2,i+3\}\times\{j,j+1\}$ : the first of two orbitals is

   \begin{equation*}o_1=\{(i,j),(i+1,j+1),(i+2,j),(i+3,j+1)\}.\end{equation*}
   If $b_1=0$ everything is fixed and $o_1$ invariant. If $b_1=1$ the induced permutation $\sigma_{1,b_2,b_3}^{\prime}$ maps:
   \begin{equation*}\sigma_{1,b_2,b_3}'(o_1)=\{(i+2,j),(i+3,j+1),(i,j),(i+1,j+1)\}=o_1.\end{equation*}

9. (9) $V_w\times V_z=\{i,i+1,i+2,i+3\}\times \{j,j+1\}$ : if $b_1=0$ everything is fixed, and any orbital invariant. If $b_1=1$ , $\{i,i+1\}\longleftrightarrow\{i+2,i+3\}$ , and (transposition) $(j,j+1)$ , preserving the first and hence all orbitals.

10. (10) $V_r^{(a)}\times V_r^{(b)}$ : for $r\in\{x,y,z\}$ immediate as the actions on equivalent $V_r$ are the same.

Finally because $u^{G_0}$ must appear in the fundamental magic representation, and because such blocks must have $D_4$ symmetry, each $\sigma_{(b_1,b_2,b_3)}$ is a distinct (classical) automorphism of X. However, $G_{0,\text{class}}=\mathbb{Z}_2\times\mathbb{Z}_2$ and we have shown that:

\begin{equation*} D_4\not\subset G_{0,\text{class}}.\end{equation*}

The result follows from Theorem 5.6.

8. Intermediate embeddings

In this section, we consider the situation where an intermediate embedding

\begin{equation*}G\subsetneq G'\subset S_N^+,\end{equation*}

can give an implication:

\begin{equation*}G\curvearrowright X\implies G'\curvearrowright X,\end{equation*}

that allows us conclude that G does not have the Frucht property. In this first proposition, we see that the totality property of a group dual reminds of freeness.

We recall that if $\widehat{\Gamma}\curvearrowright X$ , then $\Gamma_u=\{g_1,\dots,g_k\}$ is the set of elements of $\Gamma$ whose Fourier-type transitive magic representations appear in the fundamental magic representation.

Proposition 8.1 If a non-abelian total discrete group dual $\widehat{\Gamma}\curvearrowright X$ , then the dual of a free product

\begin{equation*}\widehat{\mathbb Z_{N_1}*\ldots*\mathbb Z_{N_k}}\curvearrowright X.\end{equation*}

Therefore no finite non-abelian total group dual has the Frucht property.

Proof. Suppose that $\Gamma$ is non-abelian and total $\widehat{\Gamma}\curvearrowright X$ by

\begin{equation*}u=\operatorname{diag}(u^{g_1},\dots,u^{g_1},\dots,u^{g_k},\dots,u^{g_k}),\end{equation*}

with $g_1,\dots,g_k$ of order $N_1,\dots,N_k$ . Consider the free product $\Gamma'\,{:\!=}\,\mathbb{Z}_{N_1}*\ldots*\mathbb Z_{N_k}$ with respective generators $h_1,\dots,h_k$ . Consider a fundamental magic representation u $^{\prime}$ of $C(\widehat{\Gamma'})$ where each instance of $u^{g_i}$ is replaced with $u^{h_i}$ :

\begin{equation*}u'=\operatorname{diag}(u^{h_1},\dots,u^{h_1},\dots,u^{h_k},\dots,u^{h_k}).\end{equation*}

Note that as $\Gamma'$ is freely generated, its dual is total, and so the orbitals between blocks of inequivalent type are full $V_p\times V_q$ . The circulant nature of the $u^{h_i}$ implies that the orbitals both within and between blocks of equivalent type are the same as $\widehat{\Gamma}\curvearrowright X$ . Hence by Theorem 5.5, we have $\widehat{\Gamma'}\curvearrowright X$ , and therefore finite $\widehat{\Gamma}$ does not have the Frucht property.

This result appears to render section 6 obsolete, but in the absence of an intermediate embedding Theorem 5.6 might still be needed to show that a quantum permutation group does not have the Frucht property. Here is a partial result for the Kac–Paljutkin quantum group.

Proof. Suppose that $G_0\curvearrowright X$ with

\begin{equation*}u=\operatorname{diag}(u^{G_0},\dots,u^{G_0},x,\dots,x,1_{G_0},\dots,1_{G_0}).\end{equation*}

The task is to replace each of these transitive magic representations with transitive magic representations of $C(H_2^+)$ , and show that this new fundamental magic representation u’ of $C(H_2^+)$ has the same orbitals as u.

We can replace the trivial representations $1_{G_0}$ with trivial representations $1_{H_2^+}$ . Recall the fundamental magic representation of $C(H_2^+)$ :

\begin{equation*}u^{H_2^+}=\begin{pmatrix} p_{11} &\quad q_{11} &\quad p_{12} &\quad q_{12} \\ q_{11} &\quad p_{11} &\quad q_{12} &\quad p_{12} \\ p_{21} &\quad q_{21} &\quad p_{22} &\quad q_{22} \\ q_{21} &\quad p_{21} &\quad q_{22} &\quad p_{22} \end{pmatrix}.\end{equation*}

With regard to the transitive magic representation $x\in M_2(C(G_0))$ , consider

\begin{equation*}x'=\begin{pmatrix} p_{11}+q_{11} &\quad p_{12}+q_{12} \\ p_{21}+q_{21} &\quad p_{22}+q_{22} \end{pmatrix}.\end{equation*}

By comparing column one and row four of $u^{H_2^+}$ , we see that this is a magic unitary, and direct calculation shows it is a representation. Consider therefore

\begin{equation*}u'=\operatorname{diag}(u^{H_2^+},\dots,u^{H_2^+},x',\dots,x',1_{H_2^+},\dots,1_{H_2^+}).\end{equation*}

With the assumption on u, there are only nine $G\curvearrowright X$ orbitals to check, five of which are total, and easily seen to be total for u’ also:

\begin{equation*}V_0\times V_1,\,V_x^{(a)}\times V_x^{(a)},\,V_x\times V_1,\,V_1^{(a)}\times V_1^{(a)},\,V_1^{(a)}\times V_1^{(b)}.\end{equation*}

There are four orbitals to check, namely:

\begin{equation*}V_0^{(a)}\times V_0^{(a)},\,V_0^{(a)}\times V_{0}^{(b)},\,V_0\times V_x,\,V_x^{(a)}\times V_x^{(b)}.\end{equation*}

We know from our illustration of Theorem 5.6 that the $V_0^{(a)}\times V_0^{(a)}$ orbitals of u’ are the same as of u. Furthermore by Proposition 5.8, the $V_0^{(a)}\times V_0^{(b)}$ orbitals of u’ are the same as of u.

By looking at $u^{H_2^+}_{ij}x'_{kl}\neq 0$ , we find that the $V_0\times V_x$ orbitals are the same as those given in Proposition 7.5, and finally the $V_x^{(a)}\times V_x^{(b)}$ orbitals of u are also orbitals of u’.

As well as analogues of the two dimensional $y,z\in M_2(C(G_0))$ , what is missing from a full $G_0\subsetneq H_2^+\subset S_N^+$ intermediate embedding result for $G_0$ is a transitive magic representation of $C(H_2^+)$ of the form:

\begin{equation*}w'=\begin{pmatrix} p_a &\quad p_b &\quad p_c &\quad p_d \\ \\[-7pt] p_b &\quad p_a &\quad p_d &\quad p_c \\ \\[-7pt] p_c &\quad p_d &\quad p_a &\quad p_b \\ \\[-7pt] p_d &\quad p_c &\quad p_b &\quad p_a \end{pmatrix}.\end{equation*}

Consider a type-w block $V_w^{(a)}$ of $G_0\curvearrowright X$ . There are three $V_w^{(a)}\times V_w^{(a)}$ orbitals, and, by Theorem 5.5, this gives eight possibilities for the induced subgraph $X(V_w^{(a)})$ :

We know that the first column of graphs admits an $H_2^+$ action. We know from our illustration of Theorem 5.6 that the second column of graphs are the orbitals of $u^{H_2^+}$ and so admit an $H_2^+$ action. If we relabel the third column by (23), and the fourth column by (24), we see that these graphs also admit $H_2^+$ actions. Unfortunately such a relabelling does not leave invariant the $V_w\times V_x$ orbitals coming from $G_0\curvearrowright X$ , and hence why we have only a partial result here. We do not believe there are analogous transitive magic representations w’,y’,z’ of $C(H_2^+)$ to complete the result in the obvious manner.

Through $u=\operatorname{diag}(u^{G_0},w,x)$ , the following graph admits a $G_0$ action:

Does $H_2^+$ act on this graph too? Or is it an explicit counterexample to $G_0\curvearrowright X\Rightarrow H_2^+\curvearrowright X$ ?

The results of this section are slightly frustrating because while we see that certain actions $G\curvearrowright X$ are not ‘sufficiently quantum’ to encompass all the quantum symmetries of X, and we can identify a strictly larger quantum permutation group of quantum symmetries, generalising these results seems challenging. In the first instance, the application of our theory requires knowing all of the transitive magic representations of C(G). We leaned heavily on the results of Bichon [Reference Bichon11] for group duals, while the Kac–Paljutkin quantum group was sufficiently small for the classification to be straightforward. As we look at further examples, say for example the finite quantum groups of Sekine [Reference Sekine33], it is not clear how easy this classification question is. Indeed we do not even know if the Sekine quantum groups for parameter $k>3$ are quantum permutation groups at all.

We have already mentioned that the dual of the binary icosahedral group, $\widehat{2I}$ , is ripe for further study. Distillation of our methods might suggest good finite dual candidates for the Frucht property. Such a candidate would give a finite graph with quantum symmetries but with finite quantum automorphism group, answering an open question of whether such a finite graph exists.

Finally, the non-canonical proof of Frucht of Theorem 3.4 constructs for each finite group a graph:

\begin{equation*}G\to X_G\quad\text{ such that }\quad G(X_G)=G.\end{equation*}

For small finite groups not known to be not quantum-excluding, it might be worth studying the quantum automorphism group $G^+(X_G)$ of these ‘Frucht graphs’.