# The Frucht property in the quantum group setting

T. Banica  T.B.: Department of Mathematics, University of Cergy-Pontoise,
Cergy-Pontoise, France<EMAIL_ADDRESS>and  J.P. McCarthy  J.P.M.:
Department of Mathematics, Munster Technological University, Cork, Ireland.
<EMAIL_ADDRESS>
###### Abstract.

A classical theorem of Frucht states that any finite group appears as the
automorphism group of a finite graph. In the quantum setting the problem is to
understand the structure of the compact quantum groups which can appear as
quantum automorphism groups of finite graphs. We discuss here this question,
notably with a number of negative results.

###### Key words and phrases:

Quantum permutation, Quantum automorphism

###### 2010 Mathematics Subject Classification:

46L65 (46L53, 81R50)

###### Contents

  1. 1 Quantum permutation groups
  2. 2 Orbits, group duals, and orbitals
  3. 3 Finite graphs and the Frucht property
  4. 4 Intermediate liberations of finite groups
  5. 5 Finite graphs and orbitals
  6. 6 Finite duals
  7. 7 The Kac–Paljutkin quantum group
  8. 8 Intermediate Embeddings

## Introduction

A natural question in group theory is whether or not a group can be realised
as the symmetry group of some object. There are various positive answers to
this question, but perhaps one of the easiest to parse is a 1939 theorem of
Frucht who showed that every finite group is the automorphism group of a
finite graph [18], a result that was subsequently extended to the infinite
setting independently by de Groot [15], and Sabidussi [28].

About half a century on from Frucht’s theorem, the Woronowicz school of
compact quantum groups was established with three seminal papers: first [37]
and later [38, 39]. It is difficult to succinctly chart the subsequent
investigation of these quantum groups, but the influential examples, including
the quantum permutation group $S_{N}^{+}$, constructed by Wang [35, 36] in the
1990s can be cited as providing much impetus for an intensive study of these
and other examples by various authors (including the first author here) in the
2000s, into the 2010s, and indeed to the present day.

One of the most natural urges in this programme is to direct to compact
quantum groups questions asked and answered in classical group theory. For
example, does a compact quantum group comprise the quantum symmetry group of
some object?

A finite graph $X$ with $N$ vertices has an automorphism group $G(X)\subset
S_{N}$, as well as a quantum automorphism group $G^{+}(X)\subset S_{N}^{+}$.
We have $G(X)\subset G^{+}(X)$, and if this inclusion is an equality, we say
that $X$ has no quantum symmetry. The contrary can happen as well, and in this
case the study of $G^{+}(X)$ is an interesting question. All this goes back to
old work from the mid 2000s, mainly by: the first author, Bichon, and their
collaborators [1, 2, 3, 4, 7, 6, 9].

The subject was reinvigorated in the mid to late 2010s, and in fact recovered
its full front-line status from the mid 2000s, on one hand due to solutions
found for some old questions, and on the other hand, due to a number of new
motivations, coming as a complement to some of the original motivations.

Lupini, Mančinska and Roberson did in their ground-breaking 2017 paper [22] a
number of unexpected things, namely: a key extension of Bichon’s work on
orbits [11] to orbitals; a counterexample to an old conjecture from [2],
stating that quantum transitivity implies transitivity; proved that the
probability that a random graph on $N$ vertices has quantum symmetry goes to
zero as $N\rightarrow\infty$; and, most importantly, found a connection with
quantum information theory and nonlocal games. Another important paper, with
some partly related results by Musto, Reutter, Verdon [25], appeared at the
same time.

Also at the same time, Schmidt managed to restart the computation work of
$G^{+}(X)$ for graphs with a small number of vertices, solving an old question
going back to [4] regarding the Petersen graph [29]. Later on, with [30, 31]
and other papers, he managed to turn the whole program into something that can
be labelled as “high level discrete mathematics”, which is interesting and
fruitful for both quantum permutations, and for advanced graph theory. Also a
number of interesting advances on a number of old open questions were made in
the PhD work of Chassaniol, done under the guidance of Bichon, published later
in [13, 14].

Finally there were big collaborations [12, 16], mixing operator algebra and
quantum group people, quantum physicists, pure algebraists, graph theorists,
and many more.

The present paper is somehow dual to previous studies of quantum automorphism
groups, which start with a finite graph and study:

$X\longrightarrow G^{+}(X).$

Instead we will start with a compact quantum group $G$, and study all the
(isomorphism classes of) finite graphs it acts on:

$G\longrightarrow\\{X_{a}\\}.$

Our big question, naturally leading on from Frucht’s theorem, is whether any
of these finite graphs has quantum automorphism group $G^{+}(X_{a})=G$?

Our study leans heavily both on the orbit theory of Bichon [11], as well as
ideas, notably orbital theory, from the paper of Lupini, Mančinska and
Roberson [22]. Key to the whole business is connecting an old observation of
Bichon [10] with orbital theory.

The paper is organised as follows: 1-3 are preliminary sections, on the
quantum permutation groups, and quantum automorphism groups of finite graphs,
in 4 we present some quantum permutation groups of possible interest in this
study, and in 5-8 we discuss the Frucht property, with a number of negative
results.

##  1\. Quantum permutation groups

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

######  Definition 1.1.

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

$\Delta:A\to A\otimes A,$ $\varepsilon:A\to\mathbb{C},$ $S:A\to A^{opp},$

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

$\Delta(u_{ij})=\sum_{k}u_{ik}\otimes u_{kj},$
$\varepsilon(u_{ij})=\delta_{ij},$ $S(u_{ij})=u_{ji}^{*},$

on the standard generators $u_{ij}$.

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

(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 [37].

(2) Given a finitely generated discrete group $\Gamma=\langle
g_{1},\ldots,g_{N}\rangle$, the full group $\mathrm{C}^{*}$-algebra
$A=\mathrm{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=\mathrm{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 $\mathrm{C}^{*}$-algebras that
$\Gamma$ might have, in the non-amenable case. See [37].

(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)=\mathrm{C}^{*}(\Gamma)$. See [37].

Based on these examples and observations, let us formulate:

######  Definition 1.2.

Given a Woronowicz algebra $(A,u)$, we write

$A=C(G)=\mathrm{C}^{*}(\Gamma),$

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

$G=\widehat{\Gamma}\quad,\quad\Gamma=\widehat{G},$

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

$(A,u)=(B,v)$

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 [37, 38], 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
$\mathrm{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

$\Delta_{1}(u_{ij})=\sum_{k=1}^{N_{1}}u_{ik}\otimes u_{kj}\text{ \quad
and\quad}\Delta_{2}(v_{ij})=\sum_{k=1}^{N_{2}}v_{ik}\otimes v_{kj},$

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 [39]. This
allows different Woronowicz algebra representations of a compact quantum
group.

Following Wang [36], 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 $\mathrm{C}^{*}$-algebra given by

$C(S_{N}^{+})=\mathrm{C}^{*}\left((u_{ij})_{i,j=1\ldots N}\Big{|}\,u={\rm
magic}\right),$

with “magic” meaning formed of projections, in the $\mathrm{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:

$U_{ij}=\sum_{k}u_{ik}\otimes u_{kj},$ $1_{ij}=\delta_{ij},$ $v_{ij}=u_{ji}.$

Thus we can define indeed morphisms $\Delta,\varepsilon,S$ as in Definition
1.1, by using the universality property of $C(S_{N}^{+})$. See [36].

######  Definition 1.5.

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

$G\subset S_{N}^{+},$

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 [36], as follows:

(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:

$v_{ij}=\chi\left(\sigma\in S_{N}\Big{|}\sigma(j)=i\right).$

(2) These characteristic functions $v_{ij}$ are abstract projections in the
$\mathrm{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:

$C(S_{N}^{+})\to C(S_{N}),$ $u_{ij}\to v_{ij}.$

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

$S_{N}\subset S_{N}^{+}.$

(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 $\mathrm{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:

$C(S_{N}^{+})=\mathrm{C}^{*}_{comm}\left((v_{ij})_{i,j=1\ldots
N}\Big{|}\,v={\rm magic}\right).$

(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) 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:

$\Phi:C(X)\to C(X)\otimes C(G),$ $e_{j}\to\sum e_{i}\otimes u_{ij}.$

(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
[36]:

######  Theorem 1.6.

The embedding $S_{N}\subset S_{N}^{+}$ is an isomorphism at $N=1,2,3$, but not
at $N\geq 4$, where $S_{N}^{+}$ is a non-classical, non-finite compact quantum
group.

###### Proof.

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

(1) Trivial.

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

$u=\begin{pmatrix}p&1-p\\\ 1-p&p\end{pmatrix}.$

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) At $N=3$ now, by using the same idea as in the $N=2$ case, we must prove
that the entries of any $3\times 3$ magic matrix commute. This is something
quite tricky, and there are 4 known proofs here [1], [22], [24], [35].
According to the proof in [24], which is the most recent, it suffices to show
that $u_{11}u_{22}=u_{22}u_{11}$, by showing:

$u_{11}u_{22}=u_{11}u_{33}=u_{22}u_{33}=u_{22}u_{11}.$

But these three equalities come respectively from:

$u_{11}(u_{21}+u_{22}+{u_{23}})=u_{11}(u_{13}+u_{23}+u_{33})$
$(u_{11}+u_{21}+u_{31})u_{33}=(u_{21}+u_{22}+u_{23})u_{33}$
$u_{22}(u_{31}+u_{32}+u_{33})=u_{22}(u_{11}+u_{21}+{u_{31}})$

(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$:

$u=\begin{pmatrix}p&1-p&0&0\\\ 1-p&p&0&0\\\ 0&0&q&1-q\\\
0&0&1-q&q\end{pmatrix}.$

Thus, if we choose $p,q$ as the generators of $\mathrm{C}^{*}(p,q)$, the
universal unital $\mathrm{C}^{*}$-algebra generated by two projections, we
obtain the result, due to the quotient map
$C(S_{4}^{+})\to\mathrm{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, $\mathrm{C}^{*}(p,q)\cong C(\widehat{D_{\infty}})$ via the isomorphism
$p\to(e+a)/2$ and $q\to(e+b)/2$.

(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 [11]:

######  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:

$i\sim j\iff u_{ij}\neq 0.$

We say that $G$ is transitive when we have only one orbit (i.e. $u_{ij}\neq 0$
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:

$u_{ij}=\chi\left(\sigma\in G\Big{|}\sigma(j)=i\right).$

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 [11] 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

$\widehat{\Gamma}\subset S_{N}^{+},$

with $N=N_{1}+\ldots+N_{k}$, as follows, using the Fourier identifications
$\widehat{\mathbb{Z}}_{N_{p}}\simeq\mathbb{Z}_{N_{p}}$,

$\displaystyle\widehat{\Gamma}$ $\displaystyle\subset$
$\displaystyle\widehat{\mathbb{Z}_{N_{1}}*\ldots*\mathbb{Z}_{N_{k}}}=\widehat{\mathbb{Z}}_{N_{1}}\,\hat{*}\,\ldots\,\hat{*}\,\widehat{\mathbb{Z}}_{N_{k}}$
$\displaystyle\cong$
$\displaystyle\mathbb{Z}_{N_{1}}\,\hat{*}\,\ldots\,\hat{*}\,\mathbb{Z}_{N_{k}}\subset
S_{N_{1}}^{+}\,\hat{*}\,\ldots\,\hat{*}\,S_{N_{k}}^{+}$ $\displaystyle\subset$
$\displaystyle S_{N}^{+},$

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:

$\mathbb{Z}_{N_{1}}*\ldots*\mathbb{Z}_{N_{k}}\to\Gamma.$

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 [35], defined by:

$C(G\,\hat{*}\,H)=C(G)*C(H).$

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) $u^{g_{p}}_{kl}=\frac{1}{N_{p}}\sum_{m=1}^{N_{p}}w^{(k-l)m}g_{p}^{m}.$

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

$u=\begin{pmatrix}u^{g_{1}}\\\ &\ddots\\\ &&u^{g_{k}}\end{pmatrix}.$

Finally, let us record the following useful inversion formula:

$g_{p}=\sum_{k=1}^{N_{p}}w^{1-k}u_{k1}^{g_{p}}.$

∎

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

######  Theorem 2.3.

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

$\mathbb{Z}_{N_{1}}*\ldots*\mathbb{Z}_{N_{k}}\to\Gamma$

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}$:

$u=U\begin{pmatrix}h_{1}\\\ &\ddots\\\ &&h_{N}\end{pmatrix}U^{*}.$

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

$N=N_{1}+\ldots+N_{k}.$

We conclude that $u$ has a $N=N_{1}+\ldots+N_{k}$ block-diagonal pattern, and
so that $U$ has as well this $N=N_{1}+\ldots+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 [11]. ∎

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

######  Definition 2.4.

Given a quantum permutation group $G$, a transitive magic representation of
$C(G)$ is a magic unitary $u^{p}\in M_{N_{p}}(C(G))$ such that:

  1. (1)

$u_{ij}^{p}\neq 0$,

  2. (2)

$\displaystyle\Delta(u_{ij}^{p})=\sum_{k=1}^{N_{p}}u_{ik}^{p}\otimes
u_{kj}^{p}$,

  3. (3)

$\varepsilon(u_{ij}^{p})=\delta_{ij}$,

  4. (4)

$S(u^{p}_{ij})=u_{ji}^{p}$.

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)$.

######  Proposition 2.5.

Let $G\subset S_{N}^{+}$. There exists a permutation matrix $P$ such that,
where $v=PuP^{-1}$:

  1. (1)

$v$ is block diagonal, with transitive magic representation blocks,

  2. (2)

the transitive magic representations that appear in $u$ are a finite subset
$A\subset M$, and can appear with multiplicity,

  3. (3)

the entries of the blocks generate $C(G)$.

###### Proof.

The orbit relation is an equivalence relation and so partitions:

$\\{1,\dots,N\\}=\bigsqcup_{p=1}^{k}X_{p}.$

Where $|X_{p}|=N_{p}$, let $P$ be a permutation of $\\{1,\dots,N\\}$ that maps

$X_{1}\rightarrow\\{1,\dots,N_{1}\\},\,X_{2}\rightarrow\\{N_{1}+1,\dots,N_{1}+N_{2}\\},\,\text{etc.}.$

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

$\langle u^{p}_{ij}\colon p\in A,\,i,j=1,\dots,N_{p}\rangle=C(G).$

  3. (3)

For $m_{p}\in\mathbb{N}_{+}$, solve:

$\sum_{p\in A}m_{p}N_{p}=N.$

  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:

$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|}}),$

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 [22], 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$:

$\int_{G}u_{ij}=\begin{cases}1/N_{p},&\mbox{if }i\sim j,\\\
0,&\mbox{otherwise}.\end{cases}$

In relation with above, we have as well the notion of orbitals, also from
[22]:

######  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:

$(i,k)\sim(j,l)\iff u_{ij}u_{kl}\neq 0.$

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}\neq 0$ 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 [22]. As explained in [24], 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:

$C(G(X))=C(S_{N})/\langle du=ud\rangle.$

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

######  Definition 3.1.

Given a graph $X$ having $N$ vertices, the construction

$C(G^{+}(X))=C(S_{N}^{+})/\langle du=ud\rangle,$

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

$G^{+}(X)\subset S_{N}^{+}$

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

######  Definition 3.2.

Let $X$ be a graph with adjacency matrix $d\in M_{N}(0,1)$. If $G\subset
S_{N}^{+}$ such that $du=ud$, we write $G\curvearrowright X$, and have
$G\subset G^{+}(X)$. On the other hand, where $X$ is a graph on $N$ vertices,
writing $G\curvearrowright X$ implies a fixed embedding $G\subset S_{N}^{+}$
such that $du=ud$.

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:

######  Definition 3.3.

Let $X$ be a finite graph with its classical and quantum automorphism groups
$G(X)\subset G^{+}(X)$. We say that:

  1. (1)

$X$ is vertex-transitive when $G(X)$ is transitive.

  2. (2)

$X$ is quantum vertex-transitive when $G^{+}(X)$ is transitive.

  3. (3)

$X$ has no quantum symmetry when $G^{+}(X)=G(X)$.

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

######  Theorem 3.4 (Frucht).

Every finite group is the automorphism group of a finite graph.

###### 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:

${\bullet}$${\bullet}$${\bullet}$${\underset{g_{i}}{\bullet}}$${\bullet}$${\bullet}$${\underset{g_{j}}{\bullet}}$

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

We note that the choice of graph to replace a directed edge of color $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 [23], and implicitly in [19].

######  Definition 3.5.

A compact quantum group $G$ has the Frucht property if there exists a finite
graph $X$ such that $G=G^{+}(X)$.

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

We have the following negative result, coming from [8]:

######  Theorem 3.6.

The following happen:

  1. (1)

Any finite group is a permutation group.

  2. (2)

There are finite quantum groups which are not quantum permutation groups.

  3. (3)

Thus there are finite quantum groups which do not have the Frucht property.

###### Proof.

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

(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) 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 [8]. To be more precise, the
quantum Cayley theorem holds at $N\leq 23$, but at $N=24$ we have a
counterexample, which occurs as a split abelian extension associated to the
exact factorisation $S_{4}=\mathbb{Z}_{4}S_{3}$. See [8].

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

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

######  Theorem 3.7.

The following happen:

  1. (1)

There are uncountably many quotients of $\mathbb{Z}_{2}*\mathbb{Z}_{3}$.

  2. (2)

Thus there are uncountably many quantum subgroups of $S_{5}^{+}$.

  3. (3)

Thus there are quantum permutation groups not of the form $G^{+}(X)$.

###### Proof.

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

(1) Conjectured to be the case by Neumann [27], Levin [21] 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 [26].

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

(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 [34], 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 [29, 30, 31], and their follow-ups:

######  Definition 4.1.

We call a finite group $G$ quantum-excluding when

$G(X)=G\implies G^{+}(X)=G$

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) 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) 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 $\mathrm{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:

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

This map was used by Woronowicz to show that commutative Woronowicz algebras
are algebras of continuous functions on compact groups $G\subset U_{N}$ [37].

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

$\Phi(\omega)=\jmath(\sigma),$

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

$\operatorname{ev}_{\sigma_{1}}\star\operatorname{ev}_{\sigma_{2}}=(\operatorname{ev}_{\sigma_{1}}\otimes\operatorname{ev}_{\sigma_{2}})\Delta,$

such that:

(2)
$\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}}).$

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 [24] for more.

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

$C(\widehat{G})=\bigoplus_{r\in\operatorname{Irr}(G)}M_{\dim(r)}(\mathbb{C}).$

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:

######  Proposition 4.2.

Assume that a finite group $G$ has $N$ one-dimensional representations. Then
the classical version $\widehat{G}_{\text{class}}$ is an abelian group of
order $N$.

###### 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. ∎

######  Theorem 4.3.

Any finite group $G$ has a liberation.

###### Proof.

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

$\mathbb{Z}_{1}\subset\widehat{A}_{5},$
$\mathbb{Z}_{2}\subset\widehat{S}_{3},$
$\mathbb{Z}_{3}\subset\widehat{A}_{4}.$

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:

$A_{5}=\langle(123),(345)\rangle$

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:

$M=\operatorname{ord}(h_{1})+\ldots+\operatorname{ord}(h_{k}).$

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

$C(G)\otimes C(\widehat{H})=C(G\times\widehat{H}).$

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

$u^{G\times\widehat{H}}=\begin{pmatrix}u^{G}\otimes 1_{\widehat{H}}&0\\\
0&1_{G}\otimes u^{\widehat{H}}\end{pmatrix}.$

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}$:

$\operatorname{ev}_{\sigma}:C(G)\rightarrow\mathbb{C},\qquad f\mapsto
f(\sigma).$

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

$\Phi(\operatorname{ev}_{\sigma}\otimes\operatorname{ev}_{e})=\begin{pmatrix}\jmath(\sigma)&0\\\
0&I_{M}\end{pmatrix},$

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:

$\\{(v_{1},v_{2}):v_{1},v_{2}\in V,v_{1}\neq v_{2}\\}.$

######  Proposition 5.1.

Suppose that $G\subset S_{N}^{+}$. If $X$ is a graph on $N$ vertices, $du=ud$
is equivalent to

$\displaystyle(i,k)\in E,\,(j,l)\in E^{c}$ $\displaystyle\implies
u_{ij}u_{kl}=0,\text{ and}$ $\displaystyle(i,k)\in E^{c},\,(j,l)\in E$
$\displaystyle\implies u_{ij}u_{kl}=0.$

###### Proof.

This goes back to Bichon [10]. A recent presentation is (Prop. 3.5, [13]). ∎

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

${\begin{subarray}{c}l\\\ \bullet\end{subarray}}$${\begin{subarray}{c}k\\\
\bullet\end{subarray}}$${\begin{subarray}{c}\bullet\\\
j\end{subarray}}$${\begin{subarray}{c}\bullet\\\ i\end{subarray}}$

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

$(j,l)\in E\implies(\sigma(j),\sigma(l))=(i,k)\in E.$

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

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

The following is contained in [22] 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

$o=\\{(i,k)\colon(i,k)\in o\\},$

its inverse

$o^{-1}=\\{(k,i)\colon(i,k)\in o\\}$

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)$,

$(i,k)\in E\implies(o\cup o^{-1})\subset E.$

Similarly

$(i,k)\in E^{c}\implies(o\cup o^{-1})\subset E^{c}.$

###### 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

$u_{ij}u_{kl}\neq 0\implies(j,l)\in E\implies o\subset E.$

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

$E_{A}:=\bigcup_{o\in A}(o\cup o^{-1}).$

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^{\prime}\in A$,
both $(i,k),\,(j,l)\in E_{A}$; and if $o^{\prime}\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$,

$(i,j)\in o\implies(\sigma_{p}(i),\sigma_{p}(j))\in o.$

Then each $\sigma_{p}\in G(X)$, and so where
$H=\langle\sigma_{1},\dots,\sigma_{k}\rangle$,

$H\subset G(X).$

Finally

$H\not\subset G_{\text{class}}\implies G\subsetneq G^{+}(X).$

###### Proof.

We have:

$G=G^{+}(X)\implies G_{\text{class}}=G(X),$

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 [6], is got from swapping labels two and
three):

$u=\begin{pmatrix}p_{11}&q_{11}&p_{12}&q_{12}\\\
q_{11}&p_{11}&q_{12}&p_{12}\\\ p_{21}&q_{21}&p_{22}&q_{22}\\\
q_{21}&p_{21}&q_{22}&p_{22}\end{pmatrix}$

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:

$\displaystyle o_{1}$
$\displaystyle=\\{(1,3),(1,4),(2,3),(2,4),(3,1),(3,2),(4,1),(4,2)\\},$
$\displaystyle o_{2}$ $\displaystyle=\\{(1,2),(2,1),(3,4),(4,3)\\}:$

${\begin{subarray}{c}1\\\ \bullet\end{subarray}}$${\begin{subarray}{c}2\\\
\bullet\end{subarray}}$${\begin{subarray}{c}1\\\
\bullet\end{subarray}}$${\begin{subarray}{c}2\\\
\bullet\end{subarray}}$${\begin{subarray}{c}\bullet\\\
4\end{subarray}}$${\begin{subarray}{c}\bullet\\\
3\end{subarray}}$${\begin{subarray}{c}\bullet\\\
4\end{subarray}}$${\begin{subarray}{c}\bullet\\\ 3\end{subarray}}$

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

$\sigma_{(b_{1},b_{2},b_{3})}=(34)^{b_{3}}(12)^{b_{2}}s^{b_{1}},$

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$,

$D_{4}\subset G(X).$

Theorem 5.5 gives all these graphs:

${\begin{subarray}{c}1\\\ \bullet\end{subarray}}$${\begin{subarray}{c}2\\\
\bullet\end{subarray}}$${\begin{subarray}{c}1\\\
\bullet\end{subarray}}$${\begin{subarray}{c}2\\\
\bullet\end{subarray}}$${\begin{subarray}{c}1\\\
\bullet\end{subarray}}$${\begin{subarray}{c}2\\\
\bullet\end{subarray}}$${\begin{subarray}{c}1\\\
\bullet\end{subarray}}$${\begin{subarray}{c}2\\\
\bullet\end{subarray}}$${\begin{subarray}{c}\bullet\\\
4\end{subarray}}$${\begin{subarray}{c}\bullet\\\
3\end{subarray}}$${\begin{subarray}{c}\bullet\\\
4\end{subarray}}$${\begin{subarray}{c}\bullet\\\
3\end{subarray}}$${\begin{subarray}{c}\bullet\\\
4\end{subarray}}$${\begin{subarray}{c}\bullet\\\
3\end{subarray}}$${\begin{subarray}{c}\bullet\\\
4\end{subarray}}$${\begin{subarray}{c}\bullet\\\ 3\end{subarray}}$ Indeed we
know from [10] 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

$u=\begin{pmatrix}u^{1}&&\\\ &\ddots&\\\ &&u^{k}\end{pmatrix}.$

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) We assume that an arbitrary embedding $G\subset S_{N}^{+}$ acts on a
finite graph $X$.

(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:

$u=\begin{pmatrix}u^{1}&&\\\ &\ddots&\\\ &&u^{k}\end{pmatrix}.$

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.

$\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})$

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

$V=\\{1,2,\dots,N\\}=\bigsqcup_{p,m}V_{p}^{(m)}.$

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

$V=\\{1,2\\}\sqcup\\{3,4\\}\sqcup\\{5,6,7\\},$

and we denote $V_{1}^{(1)}=\\{1,2\\}$, $V_{1}^{(2)}=\\{3,4\\}$, and
$V_{2}^{(1)}=\\{5,6,7\\}$.

(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) 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:

$G\curvearrowright X\implies H\curvearrowright X.$

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

$G^{+}(X)\neq G,$

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:

$\displaystyle o^{\prime}$ $\displaystyle:=\\{(i,j+nN_{p})\colon o\in
O,\,(i,j)\in o\\}$ $\displaystyle o_{d}$ $\displaystyle=\\{(i,i+nN_{p})\colon
i\in V_{p}^{(m)}\\}$

###### Proof.

Implicit here is that the labelling of $V$ has been chosen with all the
$V_{p}$ blocks together:

$u=\operatorname{diag}(\dots,u^{p},\dots,u^{p},\dots).$

This means that

$u_{ij}u_{kl}\neq 0\implies u_{ij}u_{k+nN_{p},l+nN_{p}}\neq 0.$

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:

$u_{ij}u_{i+nN_{p},j+nN_{p}}\neq 0.$

∎

######  Proposition 5.9.

Suppose $G\curvearrowright X$. If $\sigma\in S_{V}$ leaves all but one orbital
(disjoint of the diagonal relation) invariant, it is invariant for all of
them.

###### 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^{\prime}$ on $V_{p}\times V_{q}$:

$(i,j)\mapsto(\sigma(i),\sigma(j)).$

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

If $V_{p}=V_{q}$, there is a diagonal orbital, $o_{d}$, but the induced
permutation $\sigma^{\prime}$ 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
[11] 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

$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).$

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}$

$u^{g_{p}}_{ij}u^{g_{q}}_{kl}=0\implies u^{g_{p}},u^{g_{q}}\text{ are
equivalent transitive magic representations}.$

######  Proposition 6.2.

If total $\widehat{\Gamma}\curvearrowright X$, then the edge relation between
inequivalent blocks is total.

###### 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}$:

$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}.$

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}$,

$\mathbb{Z}_{N_{1}}\times\cdots\mathbb{Z}_{N_{k}}\curvearrowright X.$

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\\}$:

$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).$

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

$o_{l}=\\{(i,j)\,\colon\,j-i\mod N_{p}=l\\},$

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) $o_{l}^{(a,b)}=\\{(i^{(a)}+j_{1},i^{(b)}+j_{2})\,\colon\,j_{2}-j_{1}\mod
N_{p}=l\\}.$

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

$i^{(m)}_{p}+j\rightarrow i^{(m)}_{p}+(j+l_{p}\mod N_{p}).$

Note that

(4) $\sigma_{(l_{1},l_{2},\dots,l_{k})}(V_{p}^{(m)})=V_{p}^{(m)}.$

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

$(i^{(a)}_{p}+j_{1},i^{(b)}_{p}+j_{2})\in o^{(a,b)}_{l}\implies
j_{2}-j_{1}\mod N_{p}=l.$

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

$(i^{(a)}_{p}+(j_{1}+l_{p}\mod N_{p}),i^{(b)}_{p}+(j_{2}+l_{p}\mod N_{p})).$

If $j_{2}-j_{1}\mod N_{p}=l$ then

$((j_{2}+l_{p}\mod N_{p})-(j_{1}+l_{p}\mod N_{p}))\mod N_{p}=l$
$\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)}$

and so by Theorem 5.6 the abelian group

$\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}}$

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:

$\displaystyle o_{1}$ $\displaystyle=\\{(1,2),(2,1)\\}$ $\displaystyle o_{2}$
$\displaystyle=\\{1,2\\}\times\\{3,4,5\\}$ $\displaystyle o_{2}^{-1}$
$\displaystyle=\\{3,4,5\\}\times\\{1,2\\}$ $\displaystyle o_{3}$
$\displaystyle=\\{(3,4),(4,5),(5,3)\\}$ $\displaystyle o_{3}^{-1}$
$\displaystyle=\\{(3,5),(5,4),(4,3)\\}$

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:

${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$

${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$

######  Proposition 6.4.

Let $p$ be a prime. If $\Gamma$ is non-abelian, has $p$ one dimensional
representations, and $\widehat{\Gamma}$ is total, then $\widehat{\Gamma}$ does
not have the Frucht property.

###### 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. ∎

######  Theorem 6.5.

The finite duals $\widehat{S_{3}}$, $\widehat{A_{4}}$, and $\widehat{A_{5}}$
do not have the Frucht property.

###### 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)
$K(g_{p},g_{q}):=\left[g_{p}^{m}g_{q}^{n}\right]_{m=1,\dots,N_{p},\,n=1,\dots,N_{q}},$

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

$u_{ij}^{g_{p}}u_{kl}^{g_{q}},$

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

$K(f_{a},f_{b}),\,K(\sigma_{c},\sigma_{d}),\,K(\tau_{k},\tau_{l}).$

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}^{j}u_{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:

$s=\frac{1}{2}(1+i+j+k)\text{ and }t=\frac{1}{2}(\varphi 1+\varphi^{-1}i+j).$

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

$u^{s}_{11}u^{t}_{51}=0.$

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 [20], $G_{0}$, has algebra of
functions structure:

(6) $C(G_{0})=\mathbb{C}\oplus\mathbb{C}\oplus\mathbb{C}\oplus\mathbb{C}\oplus
M_{2}(\mathbb{C}).$

The choice to denote this finite quantum group by $G_{0}$ harks back to the
original notation of [20], 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 [17]. The Haar measure is given by:

$\int_{G_{0}}f_{i}=\frac{1}{8}\text{, and
}\int_{G_{0}}E_{kl}=\frac{\delta_{kl}}{4}.$

Where $I_{2}$ is the identity in the $M_{2}(\mathbb{C})$ summand, and the
projection

(7)
$p:=\left(0,0,0,0,\left(\begin{array}[]{cc}\frac{1}{2}&\frac{1}{2}e^{-i\pi/4}\\\
\frac{1}{2}e^{+i\pi/4}&\frac{1}{2}\end{array}\right)\right),$

a concrete exhibition of $G_{0}\subset S_{4}^{+}$ (Th. 1.1 (8), [5]) comes by
the fundamental magic representation:

(12) $\displaystyle
u^{G_{0}}:=\left[\begin{array}[]{cccc}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].$

Another transitive magic representation $w\in M_{4}(C(G_{0}))$, whose entries
do not generate $C(G_{0})$, is given by:

(13) $w=\begin{pmatrix}f_{1}+f_{4}&f_{2}+f_{3}&E_{11}&E_{22}\\\
f_{2}+f_{3}&f_{1}+f_{4}&E_{22}&E_{11}\\\
E_{11}&E_{22}&f_{1}+f_{4}&f_{2}+f_{3}\\\
E_{22}&E_{11}&f_{2}+f_{3}&f_{1}+f_{4}\end{pmatrix}.$

There are three transitive magic representations $x,y,z\in M_{2}(G_{0})$ given
by

(14) $\displaystyle x$
$\displaystyle=\begin{pmatrix}f_{1}+f_{2}+f_{3}+f_{4}&I_{2}\\\
I_{2}&f_{1}+f_{2}+f_{3}+f_{4}\end{pmatrix},$ (15) $\displaystyle y$
$\displaystyle=\begin{pmatrix}f_{1}+f_{4}+E_{11}&f_{2}+f_{3}+E_{22}\\\
f_{2}+f_{3}+E_{22}&f_{1}+f_{4}+E_{11}\end{pmatrix},$ (16) $\displaystyle z$
$\displaystyle=\begin{pmatrix}f_{1}+f_{4}+E_{22}&f_{2}+f_{3}+E_{11}\\\
f_{2}+f_{3}+E_{11}&f_{1}+f_{4}+E_{22}\end{pmatrix}.$

######  Proposition 7.1.

The full set of inequivalent transitive magic representations of $C(G_{0})$ is

$M=\\{u^{G_{0}},w,x,y,z,1_{G_{0}}\\}.$

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) The only magic unitary in $M_{1}(C(G_{0}))$ is $1_{\mathfrak{G_{0}}}$.

(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:

$q=\begin{pmatrix}q_{11}&q_{12}\\\
q_{21}&1-q_{11}\end{pmatrix}\implies\int_{G_{0}}q=\frac{1}{4}.$

Furthermore to satisfy $\int_{G_{0}}v_{11}=1/2$, we must have, where $i,j,k$
is a permutation of $\\{2,3,4\\}$:

$v=\begin{pmatrix}f_{1}+f_{i}+q&f_{j}+f_{k}+I_{2}-q\\\
f_{j}+f_{k}+I_{2}-q&f_{1}+f_{i}+q\end{pmatrix}.$

Suppose that $i\neq 4$. When we examine the comultiplication (see [17]), 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:

$\Delta(v_{11})=v_{11}\otimes v_{11}+v_{12}\otimes v_{21},$

we require therefore that the coefficient of $E_{11}\otimes E_{11}$ in

$q\otimes q+(I_{2}-q)\otimes(I_{2}-q)$

is also $1/2$. That is we require:

$q_{11}^{2}+(1-q_{11})^{2}=\frac{1}{2}\implies q_{11}=\frac{1}{2}.$

This implies further that

$q=\begin{pmatrix}\frac{1}{2}&\frac{1}{2}e^{i\theta}\\\
\frac{1}{2}e^{-i\theta}&\frac{1}{2}\end{pmatrix}.$

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:

(17)
$\frac{1}{2}e^{-i\theta}\frac{1}{2}e^{i\theta}+\left(-\frac{1}{2}e^{-i\theta}\right)\left(-\frac{1}{2}e^{i\theta}\right)=+\frac{1}{2}.$

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) 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) 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

$u=\begin{pmatrix}f_{1}+f_{i}&f_{j}+f_{k}&q&I_{2}-q\\\ *&*&*&*\\\ *&*&*&*\\\
*&*&*&*\end{pmatrix}.$

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:

$\Delta(A)\subset A\otimes A+B\otimes B\text{ and }\Delta(B)=A\otimes
B+B\otimes A.$

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 :

$u=\begin{pmatrix}f_{1}+f_{i}&f_{j}+f_{k}&q&I_{2}-q\\\
f_{j}+f_{k}&f_{1}+f_{i}&I_{2}-q&q\\\
q^{T}&I_{2}-q^{T}&f_{1}+f_{a}&f_{b}+f_{c}\\\
I_{2}-q^{T}&q^{T}&f_{b}+f_{c}&f_{1}+f_{a}\end{pmatrix}.$

(a) Suppose that $i=2$:

$u=\begin{pmatrix}f_{1}+f_{2}&f_{3}+f_{4}&q&I_{2}-q\\\
f_{3}+f_{4}&f_{1}+f_{2}&I_{2}-q&q\\\
q^{T}&I_{2}-q^{T}&f_{1}+f_{a}&f_{b}+f_{c}\\\
I_{2}-q^{T}&q^{T}&f_{b}+f_{c}&f_{1}+f_{a}\end{pmatrix}.$

By looking at the $E_{11}\otimes E_{11}$ term in $\Delta(u_{11})$ and in

$u_{13}\otimes u_{31}+u_{14}\otimes u_{41}=q\otimes
q^{T}+(I_{2}-q)\otimes(I_{2}-q^{T}),$

we find:

$q_{11}^{2}+(1-q_{11})^{2}=\frac{1}{2}\implies q_{11}=\frac{1}{2},$

and so

$q=\begin{pmatrix}\frac{1}{2}&\frac{1}{2}e^{i\theta}\\\
\frac{1}{2}e^{-i\theta}&\frac{1}{2}\end{pmatrix}\text{ and
}q^{T}=\begin{pmatrix}\frac{1}{2}&\frac{1}{2}e^{-i\theta}\\\
\frac{1}{2}e^{+i\theta}&\frac{1}{2}\end{pmatrix}.$

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

$\frac{1}{2}e^{-i\theta}\frac{1}{2}e^{-i\theta}+\left(-\frac{1}{2}e^{-i\theta}\right)\left(-\frac{1}{2}e^{-i\theta}\right)=\frac{i}{2}$
$\displaystyle\implies\theta$ $\displaystyle=-\pi/4$ $\displaystyle\implies q$
$\displaystyle=p,$

as in $p$ from (7). This implies that we have:

$u=\begin{pmatrix}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_{a}&f_{b}+f_{c}\\\
I_{2}-p^{T}&p^{T}&f_{b}+f_{c}&f_{1}+f_{a}\end{pmatrix}$

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}}$.

(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:

$u=\begin{pmatrix}f_{1}+f_{3}&f_{2}+f_{4}&p^{T}&I_{2}-p^{T}\\\
f_{2}+f_{4}&f_{1}+f_{3}&I_{2}-p^{T}&p^{T}\\\
p&I_{2}-p&f_{1}+f_{2}&f_{3}+f_{4}\\\
I_{2}-p&p&f_{3}+f_{4}&f_{1}+f_{2}\end{pmatrix}$

Where $P$ is the permutation matrix of $(13)(24)$:

$u^{G_{0}}=PuP^{-1},$

and $u$ is equivalent to $u^{G_{0}}$

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

$u=\begin{pmatrix}f_{1}+f_{4}&f_{2}+f_{3}&q&I_{2}-q\\\
f_{3}+f_{2}&f_{1}+f_{4}&I_{2}-q&q\\\
q^{T}&I_{2}-q^{T}&f_{1}+f_{a}&f_{b}+f_{c}\\\
I_{2}-q^{T}&q^{T}&f_{b}+f_{c}&f_{1}+f_{a}\end{pmatrix}$

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}$:

$u=\begin{pmatrix}f_{1}+f_{4}&f_{2}+f_{3}&E_{11}&E_{22}\\\
f_{3}+f_{2}&f_{1}+f_{4}&E_{22}&E_{11}\\\
E_{11}&E_{22}&f_{1}+f_{a}&f_{b}+f_{c}\\\
E_{22}&E_{11}&f_{b}+f_{c}&f_{1}+f_{a}\end{pmatrix}$

Examining $\Delta(u_{31})=\Delta(E_{11})$ we must have $a=4$ and so:

$u=\begin{pmatrix}f_{1}+f_{4}&f_{2}+f_{3}&E_{11}&E_{22}\\\
f_{3}+f_{2}&f_{1}+f_{4}&E_{22}&E_{11}\\\
E_{11}&E_{22}&f_{1}+f_{4}&f_{2}+f_{3}\\\
E_{22}&E_{11}&f_{2}+f_{3}&f_{1}+f_{4}\end{pmatrix}=w.$

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

$\displaystyle V$
$\displaystyle=\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).$

In terms of orbital types, there are twelve type $V_{p}\times V_{p}$ orbitals,
and fifteen 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:

$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)}.$

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

$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},$ $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)}.$

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:  ${\begin{subarray}{c}j\\\
\bullet\end{subarray}}$${\begin{subarray}{c}i\\\
\bullet\end{subarray}}$${\begin{subarray}{c}i+1\\\
\bullet\end{subarray}}$${\begin{subarray}{c}j+1\\\
\bullet\end{subarray}}$${\begin{subarray}{c}k\\\
\bullet\end{subarray}}$${\begin{subarray}{c}\bullet\\\
i+3\end{subarray}}$${\begin{subarray}{c}\bullet\\\
i+2\end{subarray}}$${\begin{subarray}{c}j+2\\\
\bullet\end{subarray}}$${\begin{subarray}{c}\bullet\\\
k+1\end{subarray}}$${\begin{subarray}{c}j+3\\\ \bullet\end{subarray}}$

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:
${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$

###### 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:

${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$

###### Proof.

Here are the $V_{0}^{(a)}\times V_{0}^{(b)}$ orbitals.

$\displaystyle o_{d}$ $\displaystyle=\\{(i^{(a)}+j,i^{(b)}+j)\colon
j\in\\{0,\dots,3\\}\\}$ $\displaystyle o_{b}$
$\displaystyle=\\{(i^{(a)},i^{(b)}+1),(i^{(a)}+1,i^{(b)}),(i^{(a)}+2,i^{(b)}+3),(i^{(a)}+3,i^{(b)}+2)\\}$
$\displaystyle o_{s}$
$\displaystyle=[\\{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\\}]$

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 (12)-(16).

######  Proposition 7.4.

Suppose $G_{0}\curvearrowright X$ with $m_{w}\geq 1$. Then the $V_{0}\times
V_{w}$ orbitals are:

${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$

######  Proposition 7.5.

Suppose $G_{0}\curvearrowright X$ with $m_{x}\geq 1$. Then the $V_{0}\times
V_{x}$ orbitals are:

${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$

######  Proposition 7.6.

Suppose $G_{0}\curvearrowright X$ with $m_{w}\geq 1$. Then the
$V_{w}^{(a)}\times V_{w}^{(a)}$ orbitals are:

${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$

###### Proof.

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

$\displaystyle o_{1}$ $\displaystyle=\\{(1,2),(2,1),(3,4),(4,3)\\}$
$\displaystyle o_{2}$ $\displaystyle=\\{(1,3),(2,4),(3,1),(4,2)\\}$
$\displaystyle o_{3}$ $\displaystyle=\\{(1,4),(2,3),(3,2),(4,1)\\}$

∎

######  Proposition 7.7.

Suppose $G_{0}\curvearrowright X$ with $m_{w}\geq 2$. There are four
$V_{w}^{(a)}\times V_{w}^{(b)}$ orbitals:

${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$

###### 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:

${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$

######  Proposition 7.10.

Suppose $G_{0}\curvearrowright X$ with $m_{w},m_{z}\geq 1$. There are two
$V_{w}\times V_{z}$ orbitals:

${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$

######  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:

${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$

###  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}$:

(18) $D_{4}=\\{e,(12),(34),(12)(34),(13)(24),(14)(23),(1324),(1423)\\}.$

Where $s=(14)(23)$, each $\omega\in D_{4}$ is of the form, for some
$b_{i}\in\\{0,1\\}$,

$\omega_{(b_{1},b_{2},b_{3})}=(34)^{b_{3}}(12)^{b_{2}}s^{b_{1}}.$

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:

$\displaystyle V_{0}\ni i+l$ $\displaystyle\quad\longmapsto\quad
i+\omega_{(b_{1},b_{2},b_{3})}(l+1)-1.$ (19) $\displaystyle V_{w}\ni i+l$
$\displaystyle\quad\longmapsto\quad i+[(13)(24)]^{b_{1}}(l+1)-1$ (20)
$\displaystyle V_{x}\ni j+l$ $\displaystyle\quad\longmapsto\quad
j+(l+b_{1}\mod 2)$ (21) $\displaystyle V_{y}^{m}\ni j+l$
$\displaystyle\quad\longmapsto\quad j+l$ (22) $\displaystyle V_{z}\ni j+l$
$\displaystyle\quad\longmapsto\quad j+(l+b_{1}\mod 2)$ $\displaystyle V_{1}\ni
k$ $\displaystyle\quad\longmapsto\quad k$

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 (18) 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

$\\{i,i+1\\},\,\\{i+2,i+3\\},\,\\{j,j+1\\},\,\\{j+2,j+3\\}$

are all invariant for $\sigma_{(0,b_{2},b_{3})}$. If $b_{1}=1$, then

$\\{i,i+1\\}\longleftrightarrow\\{i+2,i+3\\},$

and, by (19), we also have

$\\{j,j+1\\}\longleftrightarrow\\{j+2,j+3\\},$

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 (20), 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):

$(i,i+2)(i+1,i+3),$

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

$o_{1}=\\{(i,j),(i+1,j+1),(i+2,j),(i+3,j+1)\\}.$

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:

$\sigma_{1,b_{2},b_{3}}^{\prime}(o_{1})=\\{(i+2,j),(i+3,j+1),(i,j),(i+1,j+1)\\}=o_{1}.$

  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:

$D_{4}\not\subset G_{0,\text{class}}.$

The result follows from Theorem 5.6. ∎

##  8\. Intermediate Embeddings

In this section we consider the situation where an intermediate embedding

$G\subsetneq G^{\prime}\subset S_{N}^{+},$

can give an implication:

$G\curvearrowright X\implies G^{\prime}\curvearrowright X,$

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

$\widehat{\mathbb{Z}_{N_{1}}*\ldots*\mathbb{Z}_{N_{k}}}\curvearrowright X.$

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

$u=\operatorname{diag}(u^{g_{1}},\dots,u^{g_{1}},\dots,u^{g_{k}},\dots,u^{g_{k}}),$

with $g_{1},\dots,g_{k}$ of order $N_{1},\dots,N_{k}$. Consider the free
product $\Gamma^{\prime}:=\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^{\prime}})$ where each
instance of $u^{g_{i}}$ is replaced with $u^{h_{i}}$:

$u^{\prime}=\operatorname{diag}(u^{h_{1}},\dots,u^{h_{1}},\dots,u^{h_{k}},\dots,u^{h_{k}}).$

Note that as $\Gamma^{\prime}$ 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^{\prime}}\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.

######  Proposition 8.2.

If $G_{0}\curvearrowright X$ with only $u^{G_{0}}$, $x$, and $1_{G_{0}}$
appearing, then $H_{2}^{+}\curvearrowright X$.

###### Proof.

Suppose that $G_{0}\curvearrowright X$ with

$u=\operatorname{diag}(u^{G_{0}},\dots,u^{G_{0}},x,\dots,x,1_{G_{0}},\dots,1_{G_{0}}).$

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^{\prime}$ 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}^{+})$:

$u^{H_{2}^{+}}=\begin{pmatrix}p_{11}&q_{11}&p_{12}&q_{12}\\\
q_{11}&p_{11}&q_{12}&p_{12}\\\ p_{21}&q_{21}&p_{22}&q_{22}\\\
q_{21}&p_{21}&q_{22}&p_{22}\end{pmatrix}.$

With regard to the transitive magic representation $x\in M_{2}(C(G_{0}))$,
consider

$x^{\prime}=\begin{pmatrix}p_{11}+q_{11}&p_{12}+q_{12}\\\
p_{21}+q_{21}&p_{22}+q_{22}\end{pmatrix}.$

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

$u^{\prime}=\operatorname{diag}(u^{H_{2}^{+}},\dots,u^{H_{2}^{+}},x^{\prime},\dots,x^{\prime},1_{H_{2}^{+}},\dots,1_{H_{2}^{+}}).$

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^{\prime}$ also:

$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)}.$

There are four orbitals to check, namely:

$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)}.$

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

By looking at $u^{H_{2}^{+}}_{ij}x^{\prime}_{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^{\prime}$. ∎

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:

$w^{\prime}=\begin{pmatrix}p_{a}&p_{b}&p_{c}&p_{d}\\\
p_{b}&p_{a}&p_{d}&p_{c}\\\ p_{c}&p_{d}&p_{a}&p_{b}\\\
p_{d}&p_{c}&p_{b}&p_{a}\end{pmatrix}.$

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)})$:

${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$${\bullet}$

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^{\prime},y^{\prime},z^{\prime}$ 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:

${2}$${1}$${6}$${9}$${5}$${8}$${10}$${7}$${4}$${3}$

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 [11] 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 [33], 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:

$G\to X_{G}\quad\text{ such that }\quad G(X_{G})=G.$

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

## References

  * [1] T. Banica, Quantum automorphism groups of small metric spaces, Pacific J. Math. 219 (2005), 27–51.
  * [2] T. Banica, Quantum automorphism groups of homogeneous graphs, J. Funct. Anal. 224 (2005), 243–280.
  * [3] T. Banica and J. Bichon, Free product formulae for quantum permutation groups, J. Inst. Math. Jussieu 6 (2007), 381–414.
  * [4] T. Banica and J. Bichon, Quantum automorphism groups of vertex-transitive graphs of order $\leq$ 11, J. Algebraic Combin. 26 (2007), 83–105.
  * [5] T. Banica and J. Bichon, Quantum groups acting on 4 points, _J. Reine Angew. Math._ 626, 74–114, 2009.
  * [6] T. Banica, J. Bichon and B. Collins, The hyperoctahedral quantum group, J. Ramanujan Math. Soc. 22 (2007), 345–384.
  * [7] T. Banica, J. Bichon and G. Chenevier, Graphs having no quantum symmetry, Ann. Inst. Fourier 57 (2007), 955–971.
  * [8] T. Banica, J. Bichon and S. Natale, Finite quantum groups and quantum permutation groups, Adv. Math. 229 (2012), 3320–3338.
  * [9] J. Bichon, Quantum automorphism groups of finite graphs, Proc. Amer. Math. Soc. 131 (2003), 665–673.
  * [10] J. Bichon, Free wreath product by the quantum permutation group, Alg. Rep. Theory 7 (2004), 343-–362.
  * [11] J. Bichon, Algebraic quantum permutation groups, Asian-Eur. J. Math. 1 (2008), 1–13.
  * [12] M. Brannan, A. Chirvasitu, K. Eifler, S. Harris, V. Paulsen, X. Su and M. Wasilewski, Bigalois extensions and the graph isomorphism game, Comm. Math. Phys. 375 (2020), 1777–1809.
  * [13] A. Chassaniol, Quantum automorphism group of the lexicographic product of finite regular graphs, J. Algebra 456 (2016), 23–45.
  * [14] A. Chassaniol, Study of quantum symmetries for vertex-transitive graphs using intertwiner spaces (2019).
  * [15] J. de Groot, Groups represented by homeomorphism groups, Math. Ann., 138, (1959), 80–102.
  * [16] C. Eder, V. Levandovskyy, J. Schanz, S. Schmidt, S. Steenpass and M. Weber, Existence of quantum symmetries for graphs on up to seven vertices: a computer based approach (2019).
  * [17] U. Franz and R. Gohm, Random Walks on Finite Quantum Groups, Quantum Independent Increment Processes II, volume 1866 of Lecture Notes in Math., Springer, Berlin, (2006), 1–32.
  * [18] R. Frucht, Herstellung von Graphen mit vorgegebener abstrakter Gruppe, Compos. Math. 6 (1939), 239–250.
  * [19] D. Gromada, Free quantum analogue of Coxeter group $D_{4}$ (2020).
  * [20] GI Kac and V.G. Paljutkin, Finite Group Rings, _Trudy Moskov. Mat. Obšč_. 15:224–261, 1966. Translated in Trans. Moscow Math. Soc. (1967), 251–284, 1966.
  * [21] F. Levin, Factor groups of the modular group, J. London Math. Soc., 1 43 (1968), 195–203.
  * [22] M. Lupini, L. Mančinska and D.E. Roberson, Nonlocal games and quantum permutation groups, J. Funct. Anal. 279 (2020), 1–39.
  * [23] L. Mančinska and D.E. Roberson, Quantum isomorphism is equivalent to equality of homomorphism counts from planar graphs (2019).
  * [24] J.P. McCarthy, A state-space approach to quantum permutations (2021).
  * [25] B. Musto, D.J. Reutter and D. Verdon, A compositional approach to quantum functions, J. Math. Phys. 59 (2018), 1–57.
  * [26] B. H. Neumann, Some remarks on infinite groups, J. Lond. Math. Soc. 12 (1937) 120–127.
  * [27] B. H. Neumann, An essay on free products of groups with amalgamations, Philos. Trans. Roy. Soc. Lon. A 246, (1954), 503–554.
  * [28] G. Sabidussi, Graphs with given group and given graph-theoretical properties, Canad. J. Math. 9 (1960), 515–525.
  * [29] S. Schmidt, The Petersen graph has no quantum symmetry, Bull. Lond. Math. Soc. 50 (2018), 395–400.
  * [30] S. Schmidt, Quantum automorphisms of folded cube graphs, Ann. Inst. Fourier 70 (2020), 949–970.
  * [31] S. Schmidt, On the quantum symmetry groups of distance-transitive graphs, Adv. Math. 368 (2020), 1–43.
  * [32] S. Schmidt, Quantum automorphism groups of finite graphs, Saarland University, (2020), PhD Thesis.
  * [33] Y. Sekine, An example of finite-dimensional Kac algebras of Kac–Paljutkin type, Proc. Amer. Math. Soc. 124, no.4, (1996) 1139-1147.
  * [34] D. Ştefan, The set of types of $n$-dimensional semisimple and cosemisimple Hopf algebras is finite, J. Algebra 193 (1997), 571–580.
  * [35] S. Wang, Free products of compact quantum groups, Comm. Math. Phys. 167 (1995), 671–692.
  * [36] S. Wang, Quantum symmetry groups of finite spaces, Comm. Math. Phys. 195 (1998), 195–211.
  * [37] S.L. Woronowicz, Compact matrix pseudogroups, Comm. Math. Phys. 111 (1987), 613–665.
  * [38] S.L. Woronowicz, Tannaka-Krein duality for compact matrix pseudogroups. Twisted SU(N) groups, Invent. Math. 93 (1988), 35–76.
  * [39] S.L. Woronowicz, Compact quantum groups, in “Symétries quantiques” (Les Houches, 1995), North-Holland, Amsterdam (1998), 845–884.