Quantum symmetries of Cayley graphs of abelian groups

Abstract

We study Cayley graphs of abelian groups from the perspective of quantum symmetries. We develop a general strategy for determining the quantum automorphism groups of such graphs. Applying this procedure, we find the quantum symmetries of the halved cube graph, the folded cube graph, and the Hamming graphs.

1. Introduction

The adjective quantum in the title of this article refers to non-commutative geometry. In 1987, Woronowicz introduced the notion of compact quantum groups [32] (following earlier work of Drinfeld and Jimbo) as the generalization of compact groups in the non-commutative geometry. This allowed to study symmetries of different objects not only in terms of the classical theory of symmetry groups but also in terms of quantum groups. A remarkable property of graphs is that although they are classical objects, they often possess not only classical symmetries but also the quantum ones. This was first noticed by Wang [30], who defined free quantum symmetric group $S_N^+$ as the quantum group of symmetries of a finite space of $N$ points. This quantum group is much larger than the classical group $S_N$ if $N\ge 4$ .

Studying quantum symmetries of graphs started with the work of Bichon [8] and later Banica [5], who gave the definition of the quantum automorphism group of a graph. Since then, many authors worked on determining the quantum automorphism groups of different graphs. Worth mentioning is the joint publication of the mentioned two authors [6] determining quantum symmetries of vertex-transitive graphs up to 11 vertices and a recent extensive work of Schmidt, which is summarized in his PhD thesis [26].

An important tool for studying compact quantum groups was introduced again by Woronowicz in [33]—the monoidal $*$ -category of representations and intertwiners. Woronowicz formulated a generalization of the so-called Tannaka–Krein duality: He proved that a compact quantum group is uniquely determined by its representation category. A very useful result then came with the work of Banica and Speicher [12], who showed how to model those intertwiners using combinatorial objects—partitions.

This formalism can also be used when working with quantum automorphisms of graphs. Given a graph $X$ , its quantum automorphism group can be defined as the unique compact matrix quantum group $G$ , whose representation category is generated by the intertwiners $T_{\sqcap }^{(N)}$ , and $A_X$ , where $A_X$ is the adjacency matrix of $X$ .

In this paper, we study Cayley graphs of abelian groups. We use the intertwiner formalism to formulate a general algorithm for determining the quantum automorphism groups of such graphs. The result is presented in Section 4 as Algorithm 1. It is based on the idea, which was already used in [7] to determine the quantum symmetries of the hypercube graph, namely that the Fourier transform on the underlying group $\Gamma$ diagonalizes the adjacency matrix of the Cayley graph of this group. The case of the hypercube graph is presented in Section 3 as a motivating example.

As a side remark, let us mention the work of Chassaniol [13], who uses the intertwiner approach to determine quantum symmetries of some circulant graphs, that is Cayley graphs of the cyclic groups. But apart from using the intertwiners, his techniques are different from ours.

Subsequently, we use our algorithm to determine the quantum automorphism groups of certain Cayley graphs, which were not known before. This constitutes the main result of this article, which can be summarized as follows:

Theorem. We determine the quantum automorphism groups of the following graphs.

1. (a) [Theorem 5.1 ] For $n\neq 1,3$ , the quantum symmetries of the halved hypercube graph $\frac{1}{2}Q_{n+1}$ are described by the anticommutative special orthogonal group $SO_{n+1}^{-1}$ .

2. (b) [Theorem 6.1 ] For $n\neq 1,3$ , the quantum symmetries of the folded hypercube graph $FQ_{n+1}$ are described by the projective anticommutative orthogonal group $PO_{n+1}^{-1}$ .

3. (c) [Theorem 7.1 ] For $m\neq 1,2$ , the quantum symmetries of the Hamming graph $H(n,m)$ are described by the wreath product $S_m^+\wr S_n$ .

Note that quantum symmetries of the folded hypercube and the Hamming graphs were already studied before [25, 27], but determining the quantum automorphism group for a general value of the parameters was left open.

2. Preliminaries

In this section, we recall the basic notions of compact matrix quantum groups and Tannaka–Krein duality. For a more detailed introduction, we refer to the monographs [28, 24].

2.1. Notation

In this work, we will often work with operators between some tensor powers of some vector spaces. Therefore, we adopt the “physics notation” with upper and lower indices for entries of these “tensors.” That is, given $T\;:\; V^{\otimes k}\to V^{\otimes l}$ for some $V={\mathbb{C}}^N$ , we denote

\begin{equation*}T(e_{i_1}\otimes \cdots \otimes e_{i_k})=\sum _{j_1,\ldots,j_l=1}^NT^{j_1\cdots j_l}_{i_1\cdots i_k}(e_{j_1}\otimes \cdots \otimes e_{j_l})\end{equation*}

We will sometimes shorten the notation and write $T_{\textbf{i}}^{\textbf{j}}$ using multi-indices $\textbf{i}=(i_1,\ldots,i_k)$ , $\textbf{j}=(j_1,\ldots,j_l)$ .

2.2. Compact matrix quantum groups

A compact matrix quantum group is a pair $G=(A,u)$ , where $A$ is a $*$ -algebra and $u=(u^i_j)\in M_N(A)$ is a matrix with values in $A$ such that

1. 1. the elements $u^i_j$ , $i,j=1,\ldots, N$ generate $A$ ,

2. 2. the matrices $u$ and $u^t$ ( $u$ transposed) are similar to unitary matrices,

3. 3. the map $\Delta \;:\; A\to A\otimes A$ defined as $\Delta (u^i_j)\;:\!=\;\sum _{k=1}^N u^i_k\otimes u^k_j$ extends to a $*$ -homomorphism.

Compact matrix quantum groups introduced by Woronowicz [32] are generalizations of compact matrix groups in the following sense. For a matrix group $G\subseteq M_N({\mathbb{C}})$ , we define $u^i_j\;:\; G\to{\mathbb{C}}$ to be the coordinate functions $u^i_j(g)\;:\!=\;g^i_j$ . Then we define the coordinate algebra $A\;:\!=\;\mathscr{O}(G)$ to be the algebra generated by $u^i_j$ . The pair $(A,u)$ then forms a compact matrix quantum group. The so-called comultiplication $\Delta \;:\; \mathscr{O}(G)\to \mathscr{O}(G)\otimes \mathscr{O}(G)$ dualizes matrix multiplication on $G$ : $\Delta (f)(g,h)=f(gh)$ for $f\in \mathscr{O}(G)$ and $g,h\in G$ .

Therefore, for a general compact matrix quantum group $G=(A,u)$ , the algebra $A$ should be seen as the algebra of non-commutative functions defined on some non-commutative compact underlying space. For this reason, we often denote $A=\mathscr{O}(G)$ even if $A$ is not commutative. Actually, $A$ also has the structure of a Hopf $*$ -algebra. In addition, we can also define the C^*-algebra $C(G)$ as the universal C^*-completion of $A$ , which can be interpreted as the algebra of continuous functions of $G$ . The matrix $u$ is called the fundamental representation of $G$ .

A compact matrix quantum group $H=(\mathscr{O}(H),v)$ is a quantum subgroup of $G=(\mathscr{O}(G),u)$ , denoted as $H\subseteq G$ , if $u$ and $v$ have the same size and there is a surjective $*$ -homomorphism $\varphi \;:\; \mathscr{O}(G)\to \mathscr{O}(H)$ sending $u^i_j\mapsto v^i_j$ . We say that $G$ and $H$ are equal if there exists such a $*$ -isomorphism (i.e. if $G\subset H$ and $H\subset G$ ). We say that $G$ and $H$ are isomorphic if there exists a $*$ -isomorphism $\varphi \;:\; \mathscr{O}(G)\to \mathscr{O}(H)$ such that $(\varphi \otimes \varphi )\circ \Delta _G=\Delta _H\circ \varphi$ . We will often use the notation $H\subseteq G$ also if $H$ is isomorphic to a quantum subgroup of $G$ .

One of the most important examples is the quantum generalization of the orthogonal group—the free orthogonal quantum group $O_N^+$ defined by Wang in [29] through the universal $*$ -algebra

\begin{equation*}\mathscr {O}(O_N^+)\;:\!=\;\mathop{\ast \textrm{-alg}}(u^i_j,\;i,j=1,\ldots,N\mid u^i_j=u^{i*}_j,uu^t=u^tu=\textrm {id}_{{\mathbb {C}}^N}).\end{equation*}

Note that this example was then further generalized by Banica [2] into the universal free orthogonal quantum group $O^+(F)$ , where $F\in M_N({\mathbb{C}})$ such that $F\bar F=\pm \textrm{id}_{{\mathbb{C}}^N}$ and

\begin{equation*}\mathscr {O}(O^+(F))\;:=\;\mathop{\ast\textrm{-alg}}(u^i_j,\;i,j=1,\ldots,N\mid \text {$u$ is unitary, }u=F\bar uF^{-1}),\end{equation*}

where $[\bar u]^i_j=u^{i*}_j$ .

2.3. Representation categories and Tannaka–Krein reconstruction

For a compact matrix quantum group $G=(\mathscr{O}(G),u)$ , we say that $v\in M_n(\mathscr{O}(G))$ is a representation of $G$ if $\Delta (v^i_j)=\sum _{k}v^i_k\otimes v^k_j$ , where $\Delta$ is the comultiplication. The representation $v$ is called unitary if it is unitary as a matrix, that is $\sum _k v^i_kv^{j*}_k=\sum _k v^{k*}_iv^k_j=\delta _{ij}$ . In particular, an element $a\in \mathscr{O}(G)$ is a one-dimensional representation if $\Delta (a)=a\otimes a$ . Another example of a quantum group representation is the fundamental representation $u$ .

We say that a representation $v$ of $G$ is non-degenerate if $v$ is invertible as a matrix (in the classical group theory, we typically consider only non-degenerate representations). It is faithful if $\mathscr{O}(G)$ is generated by the entries of $v$ . The meaning of this notion is the same as with classical groups: Given a non-degenerate faithful representation $v$ , the pair $G'=(\mathscr{O}(G),v)$ is also a compact matrix quantum group, which is isomorphic to the original $G$ .

A subspace $W\subset{\mathbb{C}}^n$ is called an invariant subspace of $v$ if the projection $P\;:\;{\mathbb{C}}^n\to{\mathbb{C}}^n$ onto $W$ commutes with $v$ , that is, $Pv=vP$ . This then defines the subrepresentation $w:=vP=Pv$ . However, $w$ as a representation is degenerate. If we need to express the subrepresentation as a non-degenerate representation, we had better consider a better consider a coisometry $U\;:\;{\mathbb{C}}^n\to{\mathbb{C}}^m$ with $P=U^*U$ and define $w'\;:\!=\;UvU^*$ . A representation $v$ is called irreducible if it has no non-trivial subrepresentations.

For two representations $v\in M_n(\mathscr{O}(G))$ , $w\in M_m(\mathscr{O}(G))$ of $G$ we define the space of intertwiners

\begin{equation*}\textrm {Mor}(v,w)=\{T\;:\; {\mathbb {C}}^n\to {\mathbb {C}}^m\mid Tv=wT\}.\end{equation*}

The set of all representations of a given quantum group together with those intertwiner spaces forms a rigid monoidal $*$ -category, which will be denoted by $\textrm{Rep}\; G$ .

Nevertheless, since we are working with compact matrix quantum groups, it is more convenient to restrict our attention only to certain representations related to the fundamental representation. If we work with orthogonal quantum groups $G\subset O_n^+$ (or $G\subset O^+(F)$ in general), then it is enough to focus on the tensor powers $u^{\otimes k}$ since the entries of those representations already linearly span the whole $\mathscr{O}(G)$ .

Considering $G=(\mathscr{O}(G),u)\subset O^+(F)$ , $F\in M_N({\mathbb{C}})$ , we define

\begin{equation*}\mathfrak {C}_G(k,l)\;:\!=\;\textrm {Mor}(u^{\otimes k},u^{\otimes l})=\{T\;:\; ({\mathbb {C}}^N)^{\otimes k}\to ({\mathbb {C}}^N)^{\otimes l}\mid Tu^{\otimes k}=u^{\otimes l}T\}.\end{equation*}

The collection of such linear spaces forms a rigid monoidal $*$ -category with the monoid of objects being the natural numbers with zero $\mathbb N_0$ .

Remark 2.1. The term rigidity means that there exists a duality morphism $R\in \mathfrak{C}(0,2)$ such that $(R^*\otimes \textrm{id}_{{\mathbb{C}}^N})(\textrm{id}_{{\mathbb{C}}^N}\otimes R)=\textrm{id}_{{\mathbb{C}}^N}$ . For quantum groups $G\subset O^+(F)$ , the duality morphism is given by $R^{ij}=F^j_i$ .

An important feature of rigidity is the so-called Frobenius reciprocity, which basically means that the whole category $\mathfrak{C}$ is determined by the spaces $\mathfrak{C}(0,k)$ , $k\in \mathbb N_0$ since $\mathfrak{C}$ is closed under certain rotations.

Conversely, we can reconstruct any compact matrix quantum group from its representation category [33, 22].

Theorem 2.2 (Woronowicz–Tannaka–Krein). Let $\mathfrak{C}$ be a rigid monoidal $*$ -category with $\mathbb N_0$ being the set of self-dual objects and $\mathfrak{C}(k,l)\subset \mathscr{L}(({\mathbb{C}}^N)^{\otimes k},({\mathbb{C}}^N)^{\otimes l})$ . Then there exists a unique orthogonal compact matrix quantum group $G$ such that $\mathfrak{C}=\mathfrak{C}_G$ . We have $G\subset O^+(F)$ with $F^j_i=R^{ij}$ , where $R$ is the duality morphism of $\mathfrak{C}$ .

We can write down the associated quantum group very concretely. The relations satisfied in the algebra $\mathscr{O}(G)$ will be exactly the intertwining relations:

\begin{equation*}\mathscr {O}(G)=\mathop{\ast\textrm{-}\textrm{alg}}(u^i_j,\;i,j=1,\ldots,N\mid u=F\bar uF^{-1},\; Tu^{\otimes k}=u^{\otimes l}T\;\forall T\in \mathfrak {C}(k,l)).\end{equation*}

We say that $S$ is a generating set for a representation category $\mathfrak{C}$ if $\mathfrak{C}$ is the smallest monoidal $*$ -category satisfying the assumptions of Theorem 2.2 that contains $S$ . We use the notation $\mathfrak{C}=\langle S\rangle _N$ (it is important to specify the dimension $N$ of the vector space $V={\mathbb{C}}^N$ associated to the object 1). If we know such a generating set, it is enough to use the generators for our relations:

\begin{equation*}\mathscr {O}(G)=\mathop{\ast\textrm{-}\textrm{alg}}(u^i_j,\;i,j=1,\ldots,N\mid u=F\bar uF^{-1},\; Tu^{\otimes k}=u^{\otimes l}T\;\forall T\in S(k,l)).\end{equation*}

2.4. Partitions

Representation categories of homogeneous orthogonal quantum groups, that is, those $G$ such that $S_N\subset G\subset O_N^+$ are conveniently described using partitions. A partition $p\in \mathscr{P}(k,l)$ is a decomposition of $k$ upper and $l$ lower points into non-empty disjoint subsets called blocks. For instance,

Given any partition $p\in \mathscr{P}(k,l)$ , we define a linear map $T_p^{(N)}\;:\; ({\mathbb{C}}^N)^{\otimes k}\rightarrow ({\mathbb{C}}^N)^{\otimes l}$ whose entries are given as “blockwise Kronecker delta”—we label the $k$ upper points by indices $i_1,\ldots,i_k$ and the $l$ lower points by indices $j_1,\ldots,j_l$ and define $[T_p^{(N)}]^{j_1,\ldots,j_l}_{i_1,\ldots,i_k}$ to be one if and only if for any given block of $p$ all the corresponding indices are equal. For instance, working with the example above, we may write

\begin{equation*}[T_p^{(N)}]^{j_1j_2j_3j_4}_{i_1i_2i_3}=\delta _{i_1i_2i_3j_2j_3},\quad [T_q^{(N)}]^{j_1j_2j_3j_4}_{i_1i_2i_3i_4}=\delta _{i_2j_3j_4}\delta _{i_3j_2}.\end{equation*}

Theorem 2.3 ([18]). It holds that $\mathfrak{C}_{S_N}(k,l)=\textrm{span}\{T_p^{(N)}\mid p\in \mathscr{P}(k,l)\}$ for every $N\in \mathbb N$ .

We define $\mathsf{Part}_N(k,l)\;:\!=\;\textrm{span}\mathscr{P}(k,l)$ the space of formal linear combinations of partitions. On this collection of linear spaces, we may define the structure of a monoidal $*$ -category in terms of simple pictorial manipulations (see e.g. [16] for details) such that they respect the category structure in $\mathfrak{C}_{S_n}$ . In other words, the mapping $T^{(N)}\;:\; \mathsf{Part}_n\to \mathfrak{C}_{S_n}$ is a monoidal unitary functor. (Note that passing to the linear spaces is often omitted, but in this article, we need them.)

As a consequence, any homogeneous quantum group $O_N^+\supset G\supset S_N$ can be described using some diagrammatic category of partitions. Thanks to the Tannaka–Krein duality, we also have the converse—any category of partitions defines a some homogeneous compact matrix quantum group [12]. For more information, see the survey [31] or the author’s PhD thesis [14].

Finally, let us mention that when working with anticommutative deformations of groups (see the next section), then it might (although sometimes might not) be convenient to use a deformed functor. Let $p\in \mathscr{P}(k,l)$ be a partition that does not contain any block of odd size. Then we define a linear operator $\breve{T}_p^{(N)}$ by

\begin{equation*}[\breve T_p^{(N)}]^{\textbf {j}}_{\textbf {i}}=\sigma _{\textbf {i}}\sigma _{\textbf {j}}[T_p^{(N)}]^{\textbf {j}}_{\textbf {i}},\end{equation*}

where $\sigma _{\textbf{i}}$ is a certain sign function: Given a multi-index $\textbf{i}=(i_1,\ldots,i_k)$ , we count the number of pairs $(k,l)$ such that $k<l$ , but $i_k>i_l$ . If this number is odd, then $\sigma _{\textbf{i}}=-1$ ; otherwise $\sigma _{\textbf{i}}=1$ . See [17, Section 7].

2.5. Anticommutative deformations

In this work, we will often work with certain anticommutative deformations of classical groups. We say that a matrix $u$ has anticommutative entries if the following relations hold

\begin{equation*}u^i_ku^j_k=-u^j_ku^i_k,\quad u^k_iu^k_j=-u^k_ju^k_i,\quad u^i_ku^j_l=u^j_lu^i_k\end{equation*}

assuming $i\neq j$ and $k\neq l$ .

As an example, let us mention the anticommutative orthogonal quantum group

\begin{equation*}\mathscr {O}(O_N^{-1})=\mathop{\ast\textrm{-alg}}(u^i_j\mid \text {$u=\bar u$, $u$ orthogonal, $u$ anticommutative}).\end{equation*}

There is a whole theory about $q$ -deformations of classical groups, where taking $q=1$ gives the classical case and $q=-1$ gives usually the anticommutative one, see [19] for more details.

2.6. Exterior products: classical case

In this section, we would like to recall the definition of exterior products in connection with the representation theory of classical groups.

Let $V$ be a vector space. We define the exterior product $V\wedge V$ and, more generally, the exterior powers $\Lambda _k(V)=V^{\wedge k}$ as follows. $V^{\wedge k}$ is the vector subspace of $V^{\otimes k}$ generated by the elements

\begin{equation*}v_1\wedge \cdots \wedge v_k={1\over k!}\sum _{\sigma \in S_k}\textrm {sgn}(\sigma )v_{\sigma (1)}\otimes \cdots \otimes v_{\sigma (k)}\end{equation*}

We denote by ${\mathcal{A}}_k\;:\; V^{\otimes k}\to V^{\wedge k}$ the coisometry mapping $v_1\otimes \cdots \otimes v_k\mapsto v_1\wedge \cdots \wedge v_k$ and call it the antisymmetrizer. (That is, ${\mathcal{A}}_k^*{\mathcal{A}}_k\;:\; V^{\otimes k}\to V^{\otimes k}$ is the projection onto $V^{\wedge k}$ taken as a subspace of $V^{\otimes k}$ .)

The motivation for such a definition is the following.

Proposition 2.4. Let $G$ be any group and $V$ some $G$ -module. Then $V^{\wedge k}$ is always a submodule of $V^{\otimes k}$ .

In particular, we can consider $G=O_n$ acting on $V={\mathbb{C}}^n$ by standard matrix multiplication. Let us prove this statement from a quantum group point of view.

Proof. Let $u\in C(G)\otimes GL(V)$ be the representation of $G$ on $V$ . We need to prove that $u^{\otimes k}{\mathcal{A}}_k^*{\mathcal{A}}_k={\mathcal{A}}_k^*{\mathcal{A}}_k u^{\otimes k}$ . Let us express both sides in coordinates.

\begin{align*} [u^{\otimes k}{\mathcal{A}}_k^*{\mathcal{A}}_k]^{\textbf{i}}_{\textbf{j}}&={1\over k!}\sum _{\sigma \in S_k}\textrm{sgn}(\sigma )u^{i_1}_{\sigma ^{-1}(j_1)}\cdots u^{i_k}_{\sigma ^{-1}(j_k)}\\[5pt] [{\mathcal{A}}_k^*{\mathcal{A}}_k u^{\otimes k}]^{\textbf{i}}_{\textbf{j}}&={1\over k!}\sum _{\sigma \in S_k}\textrm{sgn}(\sigma )u^{\sigma (i_1)}_{j_1}\cdots u^{\sigma (i_k)}_{j_k} \end{align*}

The terms $u^{i_1}_{\sigma ^{-1}(j_1)}\cdots u^{i_k}_{\sigma ^{-1}(j_k)}$ and $u^{\sigma (i_1)}_{j_1}\cdots u^{\sigma (i_k)}_{j_k}$ differ just by reordering of the factors. Since we assume that $G$ is a classical group, the entries of $u$ are commutative, so the terms must be equal.

We denote by

\begin{equation*}u^{\wedge k}\;:\!=\;{\mathcal {A}}_k u^{\otimes k}{\mathcal {A}}_k^*\end{equation*}

the corresponding subrepresentation.

The dimension of the $k$ th exterior power $V^{\wedge k}$ equals $\binom{n}{k}$ , where $n=\dim V$ . The highest non-zero power is therefore the $n$ th, which is one-dimensional. Given a representation $u$ of some group $G$ , the $n$ th exterior power of $u$ equals to the determinant $u^{\wedge n}=\mathop{\textrm{det}}\nolimits u$ .

2.7. Exterior products: anticommutative case

The concept of exterior product does not work in general for quantum groups. Let us revise it here for the case of anticommutative deformations.

For this purpose, we need to introduce some sort of “anticommutative antisymmetrization.” This should be basically the same thing as the usual symmetrization, but, in addition, we have to “throw out the diagonal” again. (Recall that classically we have $v_1\wedge \cdots \wedge v_k=0$ whenever $v_a=v_b$ for some $a,b$ .)

We define $V^{\mathop{\breve \wedge } k}$ to be the vector subspace of $V^{\otimes k}$ generated by the elements

\begin{equation*}v_1\mathop {\breve \wedge }\cdots \mathop {\breve \wedge } v_k= \begin {cases} 0&\text {if $v_a=v_b$ for some $a\neq b$}\\[5pt] \frac {1}{k!}\sum _{\sigma \in S_k}v_{\sigma (1)}\otimes \cdots \otimes v_{\sigma (k)}&\text {otherwise} \end {cases}\end{equation*}

We denote by $\breve{\mathcal{A}}_k\;:\; V^{\otimes k}\to V^{\mathop{\breve \wedge } k}$ the coisometry mapping $v_1\otimes \cdots \otimes v_k\mapsto v_1\mathop{\breve \wedge }\cdots \mathop{\breve \wedge } v_k$ .

Remark 2.5. If we view anticommutative deformations as 2-cocycle twists of usual groups, then this procedure amounts to twisting the intertwiner ${\mathcal{A}}_k^*{\mathcal{A}}_k$ of $u$ . In this sense, the rest of this subsection might be considered as obvious, but it does not harm to recall the facts explicitly.

Proposition 2.6. Consider $G\subset O_n^{-1}$ and denote by $u$ its fundamental representation. Then $u^{\otimes k}\breve{\mathcal{A}}_k^*\breve{\mathcal{A}}_k=\breve{\mathcal{A}}_k^*\breve{\mathcal{A}}_k u^{\otimes k}$ .

In other words, this means that $({\mathbb{C}}^n)^{\mathop{\breve \wedge } k}$ is an invariant space of the representation $u^{\otimes k}$ . We denote the corresponding subrepresentation by

\begin{equation*}u^{\mathop {\breve \wedge } k}\;:\!=\;\breve {\mathcal {A}}_k u^{\otimes k}\breve {\mathcal {A}}_k^*.\end{equation*}

Proof. Let us write both sides of the equation entrywise.

(2.1) \begin{align} [u^{\otimes k}\breve{\mathcal{A}}_k^*\breve{\mathcal{A}}_k]^{\textbf{i}}_{\textbf{j}}&= \begin{cases} 0&\textrm{if $j_a=j_b$ for some $a\neq b$}\\[5pt] \frac{1}{k!}\sum _{\sigma \in S_k}u^{i_1}_{\sigma ^{-1}(j_1)}\cdots u^{i_k}_{\sigma ^{-1}(j_k)}&\textrm{otherwise} \end{cases} \end{align}

(2.2) \begin{align} [\breve{\mathcal{A}}_k^*\breve{\mathcal{A}}_k u^{\otimes k}]^{\textbf{i}}_{\textbf{j}}&= \begin{cases} 0&\textrm{if $i_a=i_b$ for some $a\neq b$}\\[5pt] \frac{1}{k!}\sum _{\sigma \in S_k}u^{\sigma (i_1)}_{j_1}\cdots u^{\sigma (i_k)}_{j_k}&\textrm{otherwise} \end{cases} \end{align}

Notice again that $u^{i_1}_{\sigma ^{-1}(j_1)}\cdots u^{i_k}_{\sigma ^{-1}(j_k)}$ and $u^{\sigma (i_1)}_{j_1}\cdots u^{\sigma (i_k)}_{j_k}$ coincide up to ordering of the factors. If both $\textbf{i}$ and $\textbf{j}$ consist of mutually distinct indices, then the factors commute, and hence, the terms are equal. If $j_a=j_b$ for some $a\neq b$ , then the factors $u^{\sigma (i_a)}_{j_a}$ and $u^{\sigma (i_b)}_{j_b}$ mutually anticommute. Consequently, the symmetrization $\sum _{\sigma }u^{\sigma (i_1)}_{j_1}\cdots u^{\sigma (i_k)}_{j_k}$ equals to zero. The same applies in the case when $i_a=i_b$ for some $a\neq b$ .

The dimension of the anticommutative exterior powers is again given by the binomial coefficients. So, taking the $n$ th power, we can define the anticommutative determinant as follows

Since we assume the anticommutativity, all the factors of the terms always mutually commute. From this, the different ways to write down the determinant follow. The definition is very similar to the one of classical determinant—we are only missing the sign of the permutation in the sum. Such an object is sometimes considered also in the classical theory of matrices, where it is called the permanent. Since $u$ is a one-dimensional representation of $O_n^{-1}$ , it defines a quantum subgroup $SO_n^{-1}$ called the anticommutative special orthogonal quantum group

Note that the relation $u=1$ can be seen also as an intertwiner relation $\breve{\mathcal{A}}_nu^{\otimes n}=\breve{\mathcal{A}}_n$ . In other words $SO_n^{-1}$ is a quantum subgroup of $O_n^{-1}$ that was created by adding the intertwiner $\breve{\mathcal{A}}_n\in \textrm{Mor}(u^{\otimes n},1)$ to its representation category. Similarly, $SO_n$ can be created from $O_n$ by imposing the intertwiner ${\mathcal{A}}_n\in \textrm{Mor}(u^{\otimes n},1)$ .

2.8. Projective versions

Let $G\subset O_N^+$ be an orthogonal compact matrix quantum group and denote by $u$ its fundamental representation. Then $u\otimes u$ is surely its representation, but its matrix entries may not generate the whole algebra $\mathscr{O}(G)$ . Denote by $\mathscr{O}(PG)$ the $*$ -subalgebra of $\mathscr{O}(G)$ generated by entries of $u\otimes u$ , that is elements of the form $u^i_ju^k_l$ . Then $PG\;:\!=\;(\mathscr{O}(PG),u\otimes u)$ is a compact matrix quantum group called the projective version of $G$ .

Proposition 2.7. Consider $N\in \mathbb N$ odd. Then $PO_N^q\simeq SO_N^q$ .

For our work, we need only $q=+1$ (classical case) and $q=-1$ (anticommutative case). Nevertheless, the statement and its proof actually does not depend on $q$ and we could take any deformation of the orthogonal group here.

Proof. Denote by $u$ the fundamental representation of $O_N^q$ , so that $u\otimes u$ is the fundamental representation of $PO_N^q$ . Denote by $v$ the fundamental representation of $SO_N^q$ .

We claim that there is a $*$ -homomorphism $\alpha \;:\; \mathscr{O}(SO_N^q)\to \mathscr{O}(PO_N^q)$ mapping

\begin{equation*}v^i_j\mapsto u^i_j\mathop {\textrm {det}}\nolimits _q u\end{equation*}

First, note that $u^i_j\mathop{\textrm{det}}\nolimits _q u$ is a polynomial of even degree in the entries of $u$ (since $N$ is odd, so the determinant is of odd degree), and hence, $u^i_j\mathop{\textrm{det}}\nolimits _q u$ is indeed an element of $\mathscr{O}(PO_N^q)$ . Secondly, it is easy to check that all relations of $SO_N^q$ are satisfied by the image. In particular the determinant equals to one since $\mathop{\textrm{det}}\nolimits _q\!(u^i_j\mathop{\textrm{det}}\nolimits _q u)_{i,j}=(\!\mathop{\textrm{det}}\nolimits _q u)^2=1$ .

On the other hand, there is surely a $*$ -homomorphism $\beta \;:\; \mathscr{O}(PO_N^q)\to \mathscr{O}(SO_N^q)$ mapping $u^i_ju^k_l\mapsto v^i_jv^k_l$ since this is nothing but the restriction of the quotient map $\mathscr{O}(O_N^q)\to \mathscr{O}(SO_N^q)$ . Finally, it is easy to check that both $\beta \circ \alpha$ and $\alpha \circ \beta$ equal to the identity, so the maps must actually be isomorphisms.

3. Warm-up: quantum symmetries of the classical hypercube

In this section, we would like to revisit the result [7, Theorem 4.2] saying that the quantum automorphism group of the $n$ -dimensional hypercube graph is the anticommutative orthogonal group $O_n^{-1}$ . Our aim is to explain the proof in slightly more detail and provide more explicit computations to make everything clear.

Throughout the whole paper, we are going to rely heavily on the theory of representation categories and we will express everything in terms of intertwiners. This may seem a bit clumsy in this particular case (in comparison with the approach of [7] for instance), but it will become very handy in the following sections, where we are going to study quantum symmetries of some other graphs. Using intertwiners, we will be able to formulate our approach in a very general way for arbitrary Cayley graphs of abelian groups.

3.1. Quantum automorphism group of a graph

We define the free symmetric quantum group [30] $S_N^+=(C(S_N^+),u)$ , where

\begin{equation*}\mathscr {O}(S_N^+)=\mathop{\ast\textrm{-alg}}(u^i_j,\;i,j=1,\ldots,N\mid (u^i_j)^2=u^i_j=u^{i*}_j,\;\sum _k u^i_k=1).\end{equation*}

It holds that $S_N^+$ describes all quantum symmetries of the space of $N$ discrete points. What we mean by this is that $S_N^+$ is the largest quantum group that faithfully acts on the space of $N$ points. Let us look on this property in even more detail.

Denote by $X_N=\{1,\ldots,N\}$ the set of $N$ points. We can associate to $X_N$ the algebra of all functions $C(X_N)$ , which has a basis $\delta _1,\ldots,\delta _N$ of the canonical projections, that is, functions $\delta _i(j)=\delta _{ij}$ . An action of a quantum group $G$ on $X_N$ is described by a coaction of the associated Hopf $*$ -algebra, that is, a $*$ -homomorphism $C(X_N)\to C(X_N)\otimes \mathscr{O}(G)$ satisfying some axioms.

Now, note that since $(\delta _i)$ is a linear basis of $C(X_N)$ , the action of any compact quantum group on $X_N$ must be of the form $\delta _j\mapsto \sum _{i=1}^N \delta _i\otimes v^i_j$ . The axioms of a coaction are now equivalent to the fact that $v$ is a representation of the acting quantum group $G$ . The algebra $C(X_N)$ can be defined as the universal C^*-algebra generated by $\delta _i$ satisfying the relations $\delta _i^2=\delta _i=\delta _i^*$ and $\sum _i\delta _i=1$ . Now, it is easy to check that the requirement of the coaction being a $*$ -homomorphism exactly corresponds to the defining relations of $C(S_N^+)$ .

Alternatively, one can see the homomorphism condition also as some kind of an intertwiner relation. $S_N^+$ can be seen as a quantum subgroup of $O_N^+$ with respect to the relation , that is, requiring . Here is a tensor $C^N\to{\mathbb{C}}^N\otimes{\mathbb{C}}^N$ defined by . See also [3, 4].

Actually, it is easy to check that the partition $\sqcap$ defining $O_N^+$ together with defining $S_N^+\subset O_N^+$ generate all non-crossing partitions, that is, partitions where the strings do not cross. Let us denote by $NC(k,l)$ the set of all partitions $p\in \mathscr{P}(k,l)$ , which are non-crossing. This provides a “free quantum analogue” to Theorem 2.3 of Jones.

Proposition 3.1 ([12]). It holds that $\mathfrak{C}_{S_N^+}(k,l)=\textrm{span}\{T_p^{(N)}\mid p\in NC(k,l)\}$ for every $N\in \mathbb N$ .

Now let $X$ be a finite graph, so it has a finite set of vertices $V\;:\!=\;V(X)$ . Let us number those vertices, so we can write $V=\{1,\ldots,N\}$ . The adjacency matrix of $X$ is then an $N\times N$ matrix $A_X$ with entries consisting of zeros and ones such that $[A_X]^j_i=1$ if and only if $(i,j)$ is an edge in $X$ . If $X$ is undirected, then $A_X$ should be symmetric, otherwise it need not. If we have $[A_X]^i_i=1$ , we say that $X$ has a loop at the vertex $i$ . All concrete examples of graphs mentioned in this paper will be simple, that is undirected and without loops, but the general considerations will hold also for the directed case with loops.

We say that a quantum group $G$ acts on the graph $X$ through the coaction $\alpha \;:\; \delta _i\mapsto \sum _j\delta _j\otimes u^j_i$ if the coaction $\alpha$ commutes with the adjacency matrix, that is, $\alpha \circ A=(A\otimes \textrm{id})\circ \alpha$ . Equivalently, this means the $uA=Au$ . The quantum automorphism group of $X$ is defined to be the universal quantum group acting on $X$ .

Definition 3.2 ([5]). Let $X$ be a graph on $N$ vertices. We define the quantum automorphism group of $X$ to be the compact matrix quantum group ${\textrm{Aut}}^+X=(\mathscr{O}({\textrm{Aut}}^+X),u)$ with

\begin{equation*}\mathscr {O}(\mathop{\textrm{Aut}}\nolimits^+X)=\mathop{\ast\textrm{-alg}}(u^i_j,\;i,j=1,\ldots,N\mid (u^i_j)^2=u^i_j=u^{i*}_j,\;\sum _k u^i_k=1,\;Au=uA).\end{equation*}

Equivalently, it is determined by its representation category

where $\uparrow \in \mathscr{P}(0,1)$ is the singleton partition. The equivalence of the two generating sets can be easily seen by noticing that on one hand and on the other hand. See also [13].

3.2. The $n$ -dimensional hypercube

Consider a natural number $n\in \mathbb N$ . The $n$ -dimensional hypercube graph $Q_n$ is determined by the vertices and edges of an $n$ -dimensional hypercube. It can be parametrized as follows.

The set of $N\;:\!=\;2^n$ vertices can be identified with the elements of the group $\mathbb Z_2^n$ . We are going to denote these group elements by Greek letters $\alpha =(\alpha _1,\ldots,\alpha _n)\in \mathbb Z_2^n$ with $\alpha _i\in \{0,1\}\simeq \mathbb Z_2$ . We will denote the group operation as addition. We also denote the canonical generators by $\varepsilon _i=(0,\ldots,0,1,0,\ldots,0)$ .

Two vertices $\alpha,\beta \in V(Q_n)$ are connected by an edge if and only if they differ in exactly one of the $n$ indices, that is, if $\beta =\alpha +\varepsilon _i$ for some $i\in \{1,\ldots,n\}$ . Equivalently, we can say that $Q_n$ is the Cayley graph of $\mathbb Z_2^n$ with respect to the generating set $\varepsilon _1,\ldots,\varepsilon _n$ . We can also express the edges via the adjacency matrix

\begin{equation*}[A_{Q_n}]^\alpha _\beta = \begin {cases} 1&\text {if $\beta =\alpha +\varepsilon _i$ for some $i$,}\\[5pt] 0&\text {otherwise.} \end {cases}\end{equation*}

Example 3.3 ( $n=3$ ). We mention the example of the ordinary three-dimensional cube and its parametrization using triples of zero/one indices. Note that shifting the vertex by $\varepsilon _i$ , that is, flipping the $i$ th index, we move in the direction of the $i$ th dimension.

Below, we show the corresponding adjacency matrix. Since it is not clear, how the elements of $\mathbb Z_2^n$ should be ordered, we also labeled the rows with the corresponding tuples (the columns are ordered the same way). We also indicated the division of the matrix into blocks with respect to the number of ones in the tuple (essentially the distance from the $(0,0,0)$ -vertex).

3.3. Functions on the hypercube and Fourier transform

We denote by $C(Q_n)$ the algebra of functions on the vertex set $V(Q_n)=\mathbb Z_2^n$ . It has the canonical basis of $\delta$ -functions $\delta _\alpha$ defined by $\delta _\alpha (\beta )=\delta _{\alpha \beta }$ .

We can also define the structure of a Hilbert space $l^2(Q_n)$ on the vector space of functions simply by putting $\langle f,g\rangle =\sum _\alpha \overline{f(\alpha )}g(\alpha )$ . The basis $(\delta _\alpha )$ is then orthonormal with respect to this inner product.

There is another important basis on $l^2(Q_n)$ given by functions of the form

\begin{equation*}\tau _\mu =\tau _1^{\mu _1}\cdots \tau _n^{\mu _n},\qquad \hbox {where}\quad \mu =(\mu _1,\ldots,\mu _n)\in \mathbb Z_2^n\end{equation*}

and

\begin{equation*}\tau _i(\alpha )=(\!-\!1)^{\alpha _i},\end{equation*}

so

\begin{equation*}\tau _\mu (\alpha )=(\!-\!1)^{\alpha _1\mu _1+\cdots +\alpha _n\mu _n}=(\!-\!1)^{\alpha \cdot \mu }.\end{equation*}

First, note that the elements $\tau _\mu$ form a presentation of the group $\mathbb Z_2^n$ itself or, alternatively, of the group algebra ${\mathbb{C}}\mathbb Z_2^n$ . That is, we have $\tau _\mu \tau _\nu =\tau _{\mu +\nu }$ ; indeed,

\begin{equation*}(\tau _\mu \tau _\nu )(\alpha )=(\!-\!1)^{\alpha \cdot \mu }(\!-\!1)^{\alpha \cdot \nu }=(\!-\!1)^{\alpha \cdot (\mu +\nu )}=\tau _{\mu +\nu }.\end{equation*}

Secondly, note that the basis $(\tau _\mu )$ is orthogonal:

\begin{equation*}\langle \tau _\mu,\tau _\nu \rangle =\sum _\alpha (\!-\!1)^{\alpha \cdot (\mu +\nu )}= \begin {cases} 2^n&\text {if $\mu +\nu =0$, i.e. $\mu =\nu $,}\\[5pt] 0&\text {otherwise.} \end {cases}\end{equation*}

Let us explain more in detail the last equality, which will actually be useful also in subsequent computations.

Lemma 3.4. For $\beta \in \mathbb Z_2^n$ , it holds that

\begin{equation*}\sum _{\alpha \in \mathbb Z_2^n} (\!-\!1)^{\alpha \cdot \beta }= \begin {cases} 2^n&\textit {if $\beta =0$,}\\[5pt] 0&\textit{otherwise.} \end {cases}\end{equation*}

Proof. If $\beta =0$ , then $(\!-\!1)^{\alpha \cdot \beta }=(\!-\!1)^0=1$ , so in the sum we are summing over $2^n$ ones. Hence the result. If $\beta$ has some non-zero entry, say $\beta _i=1$ , then for every $\alpha$ , we can flip the $i$ th entry of $\alpha$ in order to flip the sign of $(\!-\!1)^{\alpha \cdot \beta }$ . Thus, there is an equal amount of $+1$ as $-1$ in the sum, so they cancel out.

We define the transformation matrix $\mathcal{F}\;:\; l^2(Q_n)\to l^2(Q_n)$ by $\mathcal{F}^\alpha _\mu =(\!-\!1)^{\alpha \cdot \mu }$ called the Fourier transform. It provides a transformation between the two bases: $\tau _\mu =\sum _\alpha \delta _\alpha \mathcal{F}^\alpha _\mu$ . Thanks to the orthogonality property above, we have that $\mathcal{F}$ is, up to scaling, orthogonal. More precisely $\mathcal{F}^{-1}={1\over 2^n}\mathcal{F}^*$ .

Example 3.5 ( $n=3$ ). Let us again look on the case $n=3$ . The matrix $\mathcal{F}$ consists only of $\pm 1$ elements. For easier reading, we write only $+$ or $-$ in the matrix instead of $+1$ and $-1$ . The order for the bases $(\delta _\alpha )$ and $(\tau _\mu )$ or, better to say, the order of the tuples $\alpha \in \mathbb Z_2^3$ are again indicated behind the matrix.

3.4. Applying Fourier transform to the intertwiners

Recall that the quantum automorphism group of the hypercube ${\textrm{Aut}}^+ Q_n$ should be the quantum subgroup of $S_N^+$ with respect to the intertwiner relation $uA=Au$ , where we denote for short $A\;:\!=\;A_{Q_n}$ . Equivalently, it is the quantum subgroup of $O_N^+$ with respect to relations and $uA=Au$ .

On the first sight, it is not clear, which quantum group these relations define. In order to see this, we first apply the Fourier transform to the intertwiners. (Recall that $\mathcal{F}$ is up to scaling orthogonal, so $O_N^+$ is invariant under $\mathcal{F}$ .) Let us look on an example first.

Example 3.6 ( $n=3$ ). The most important intertwiner seems to be the adjacency matrix of the graph as only this carries the data of the graph itself. A straightforward computation gives us a diagonal matrix

Writing some explicit matrices for would be slightly complicated, so we will get back to this tensor later. So, let us now do the computations for general $n$ . For the adjacency matrix, we have

\begin{align*} [\mathcal{F}^{-1}A\mathcal{F}]^\mu _\nu &={1\over 2^n}\sum _{\alpha,\beta }(\!-\!1)^{\alpha \cdot \mu }A^\alpha _\beta (\!-\!1)^{\beta \cdot \nu }={1\over 2^n}\sum _\alpha \sum _{i=1}^n(\!-\!1)^{\alpha \cdot \mu }(\!-\!1)^{(\alpha +\varepsilon _i)\cdot \nu }\\[5pt] &={1\over 2^n}\left (\sum _\alpha (\!-\!1)^{\alpha \cdot (\mu +\nu )}\right )\left (\sum _{i=1}^n(\!-\!1)^{\nu _i}\right )=\delta _{\mu \nu }(n-2\deg \nu ), \end{align*}

where $\deg \nu$ is the number of ones in $\nu$ , which we will subsequently call the degree of $\nu$ . So, we can say that the Fourier image of the adjacency matrix is a direct sum of identities with some scalar factors

(3.1) \begin{equation} \hat A\;:\!=\;\mathcal{F}^{-1}A\mathcal{F}=\bigoplus _{k=0}^n(n-2k)I_{\left(\substack{n\\[2pt] k}\right)} \end{equation}

Imposing $\hat A$ to be an intertwiner is equivalent to saying that every subspace of $l^2(Q_n)$ consisting of elements with a given degree $d$ (w.r.t. the basis $(\tau _\mu )$ ) is invariant. So, let us denote the invariant subspaces by

\begin{equation*}V_k\;:\!=\;\{f\in l^2(Q_n)\mid \deg f=k\}.\end{equation*}

Note that $\dim V_k={\left(\substack{n\\[2pt] k}\right)}$ . Note also that those spaces do not define a grading, but only a filtration on the algebra $C(Q_n)$ .

So, denote by $\hat u\;:\!=\;\mathcal{F}^{-1}u\mathcal{F}$ the Fourier transform of the fundamental representation of the quantum automorphism group of the hypercube and by $\hat u=\hat u^{(0)}\oplus \hat u^{(1)}\oplus \cdots \oplus \hat u^{(n)}$ the decomposition according to the invariant subspaces $V_k$ .

This was only how the adjacency matrix $A$ transforms under $\mathcal{F}$ . But we also need to transform the intertwiners defining the free symmetric quantum group $S_N^+$ . Let us consider the tensor defined by (This is indeed an intertwiner of $S_N^+$ since .)

Thanks to the fact that $u$ must be block diagonal (as we just derived), we can study such intertwiners restricted to such blocks. So, denote by $P_k$ the (Fourier transform composed with the) orthogonal projection $l^2(Q_n)\to V_k$ and define the tensor , which must be an intertwiner of $\hat u^{(1)}$ . We can compute its entries:

One can write down this result also using the partition notation as

This is well known to be the intertwiner defining the quantum group $O_n^{-1}$ . (See e.g. [17, Section 7]). Now, we may already see, where is this heading toward.

As a side remark, note that one might also want to directly compute the projection of to the subspace $V_1$ . This is of course possible by doing a very similar computation. However, this intertwiner turns out to be equal to zero (since one can never “pair” a triple of indices).

3.5. Quantum automorphism group of the hypercube

In this section, we prove that the quantum automorphism group of the hypercube graph is the $O_n^{-1}$ —a result originally obtained in [7, Theorem 4.2].

Theorem 3.7. The quantum automorphism group of the $n$ -dimensional hypercube graph is the anticommutative orthogonal quantum group $O_n^{-1}$ with the representation

\begin{equation*}\mathcal {F}\big (1\oplus v\oplus (v\mathop {\breve \wedge } v)\oplus \cdots \oplus v^{\mathop {\breve \wedge } n}\big )\mathcal {F}^{-1},\end{equation*}

where $v$ is the standard fundamental representation of $O_n^{-1}$ .

Proof. Denote by $u$ the fundamental representation of the quantum automorphism group of the hypercube ${\textrm{Aut}}^+Q_n$ . Denote by $\hat u\;:\!=\;\mathcal{F}^{-1}u\mathcal{F}$ the Fourier transform of $u$ . We prove the theorem by a series of lemmata. We start with results derived in the previous section.

Lemma 3.8. The representation $\hat u$ decomposes as $\hat u=\hat u^{(0)}\oplus \hat u^{(1)}\oplus \cdots \oplus \hat u^{(n)}$ .

Proof. Follows from the form of the Fourier transform of the adjacency matrix (3.1).

Lemma 3.9. The subrepresentation $\hat u^{(1)}$ satisfies the defining relation for $O_n^{-1}$ .

Proof. Follows from being an intertwiner of $\hat u^{(1)}$ .

Lemma 3.10. The subrepresentation $\hat u^{(1)}$ is a faithful representation of ${\textrm{Aut}}^+Q_n$ .

Proof. The representation $\hat u$ acts on $Q_n$ through the coaction $\tau _\mu \mapsto \sum _\nu \tau _\nu \otimes u^\nu _\mu$ . Since the algebra $C(Q_n)$ is generated by the invariant subspace $V_1=\textrm{span}\{\tau _i\}_{i=1}^n$ , this coaction is uniquely determined by the coaction of $\hat u^{(1)}$ on this invariant subspace. In particular, the entries of $\hat u$ must be generated by the entries of $\hat u^{(1)}$ .

Consequently, ${\textrm{Aut}}^+Q_n$ is a quantum subgroup of $O_n^{-1}$ . Now it remains to prove the opposite inclusion.

Lemma 3.11. The mapping $\tau _i\mapsto \sum _{j=1}^n\tau _j\otimes v^j_i$ extends to a $*$ -homomorphism $\alpha \;:\; C(Q_n)\to C(Q_n)\otimes \mathscr{O}(O_n^{-1})$ . The subspaces $V_l$ are invariant subspaces of this action for every $l=0,\ldots,n$ .

Proof. We have to check that the images of the generators $\tau _i$ satisfy the generating relations. That is:

\begin{equation*}\alpha (\tau _i)^*=\alpha (\tau _i),\qquad \alpha (\tau _i)^2=1,\qquad \alpha (\tau _i)\alpha (\tau _j)=\alpha (\tau _j)\alpha (\tau _i).\end{equation*}

The first one is obvious as both $\tau _i$ and $v^j_i$ are self-adjoint. For the second, we have $\alpha (\tau _i)^2=\sum _{j,k}\tau _j\tau _k\otimes u^j_iu^k_i$ . While $\tau _j$ commutes with $\tau _k$ , we have that $u^j_i$ anticommutes with $u^k_i$ unless $j=k$ . So, the entries for $j\neq k$ subtract to zero and we are left with $\sum _j \tau _j\tau _j\otimes u^j_iu^j_i=1$ . Finally, the last one (assuming $i\neq j$ ) is again easy as we have $\alpha (\tau _i)\alpha (\tau _j)=\sum _{k,l}\tau _k\tau _l\otimes u^k_iu^l_j$ , where everything commutes (unless $k=l$ , but for those summands we have $\sum _k \tau _k\tau _k\otimes u^k_iu^k_j=0$ ).

It remains to show that $V_l$ are invariant subspaces. Take arbitrary element $\tau _{i_1}\cdots \tau _{i_l}\in V_l$ (assuming $i_{1} < \cdots < i_{l}$ ) and write explicitly

(3.2) \begin{equation} \alpha (\tau _{i_1}\cdots \tau _{i_l})=\sum _{j_1,\ldots,j_l=1}^n\tau _{j_1}\cdots \tau _{j_l}\otimes u^{i_1}_{j_1}\cdots u^{i_l}_{j_l}. \end{equation}

In the cases, where $j_a=j_b$ for some $a,b$ , the contribution of the sum must equal to zero since the corresponding $\tau _{j_a}$ and $\tau _{j_b}$ commute, while $u^{i_a}_{j_a}$ and $u^{i_b}_{j_b}$ anticommute. So, we are actually summing over elements $\tau _{j_1}\cdots \tau _{j_l}\in V_l$ only, which is what we wanted to prove.

This means that $O_n^{-1}$ is a quantum subgroup of ${\textrm{Aut}}^+Q_n$ , which finishes the proof that ${\textrm{Aut}}^+Q_n\simeq O_n^{-1}$ . Finally, from the explicit expression (3.2), it is clear that $O_n^{-1}$ acts on the invariant subspaces $V_l$ indeed through the representations $\hat u^{(l)}=v^{\mathop{\breve \wedge } l}$ .

4. Cayley graphs of abelian groups: general picture

The fact that the Fourier transform diagonalizes the adjacency matrix of the hypercube graph is not a coincidence. In the graph theory, it is a well-known fact, which holds for any Cayley graph of an abelian group. (See [21] for a nice survey on the spectral theory of Cayley graphs.)

Let $\Gamma$ be a finite abelian group. We denote by $\textrm{Irr}\;\Gamma \subset C(\Gamma )$ the set of all irreducible characters (i.e. one-dimensional representations; since $\Gamma$ is abelian, all irreducible representations are in fact one-dimensional). Note that $\textrm{Irr}\;\Gamma$ forms a basis of $C(\Gamma )$ and expressing a function in this basis is exactly the Fourier transform on $\Gamma$ .

Let $S\subset \Gamma$ be a set of generators of $\Gamma$ . As in the last section, we are going to denote the elements of $\Gamma$ by Greek letters and the operation on $\Gamma$ as addition. The Cayley graph of the group $\Gamma$ with respect to the generating set $S$ denoted by $\textrm{Cay}(\Gamma,S)$ is a directed graph defined on the vertex set $\Gamma$ with an edge $(\alpha,\beta )$ for every pair of elements such that $\beta =\alpha +\vartheta$ for some $\vartheta \in S$ . If $S$ is closed under the group inversion, then the Cayley graph is actually undirected (for every edge, one also has the opposite one). So, the adjacency matrix of $\textrm{Cay}(\Gamma,S)$ is of the form

\begin{equation*}[A]^\beta _\alpha = \begin {cases} 1&\text {if $\beta =\alpha +\vartheta $ for some $\vartheta \in S$,}\\[5pt] 0&\text {otherwise.} \end {cases} \end{equation*}

Proposition 4.1 ([20, 1]). Let $\Gamma$ be a finite abelian group and $S$ its generating set. Denote by $A$ the adjacency matrix associated to the Cayley graph $\textrm{Cay}(\Gamma,S)$ . Then $\textrm{Irr}\;\Gamma$ forms the eigenbasis of $A$ . Given $\chi \in \textrm{Irr}\;\Gamma$ , its eigenvalue is given by

(4.1) \begin{equation} \lambda _\chi =\sum _{\vartheta \in S}\chi (\!-\!\vartheta ). \end{equation}

Proof. This is just a straightforward check. Take any $\chi \in \textrm{Irr}\;\Gamma$ then we have

\begin{equation*}[A\chi ]^\alpha =\sum _{\beta \in \Gamma }A^\alpha _\beta \chi (\beta )=\sum _{\vartheta \in S}\chi (\alpha -\vartheta )=\sum _{\vartheta \in S}\chi (\!-\!\vartheta )\chi (\alpha )=\lambda _\chi \chi (\alpha ).\end{equation*}

This result suggests the strategy for determining the quantum automorphism group for any Cayley graph corresponding to an abelian group: express everything in the basis of irreducible characters. Since this diagonalizes the adjacency matrix, the meaning of it as an intertwiner becomes obvious. On the other hand, it might be slightly more complicated to discover the meaning of the intertwiner

Algorithm 1. Determining Aut⁺Cay(Γ, S). Let $\Gamma$ be an abelian group and $S$ its generating set. We are trying to determine the quantum automorphism group ${\textrm{Aut}}^+\textrm{Cay}(\Gamma,S)$ with fundamental representation $u$ . In order to do so, we perform the following steps:

1. 1. Determine the irreducible characters of $\Gamma$ . Suppose that $\Gamma =\mathbb Z_{m_1}\times \cdots \times \mathbb Z_{m_n}$ . Then $\mathop{\textrm{Irr}}\Gamma =\{\tau _\mu \}_{\mu \in \Gamma }$ with $\tau _\mu (\alpha )=\prod _{i=1}^n\gamma _i^{\alpha _i\mu _i}$ , where $\gamma _i$ is some primitive $m_i$ -th root of unity for every $i$ .

2. 2. Determine the spectrum of $A_\Gamma$ using equation (4.1).

3. 3. Denoting by $\lambda _0>\lambda _1>\ldots >\lambda _d$ the mutually distinct eigenvalues of $A_\Gamma$ , determine the corresponding eigenspaces $V_0,V_1,\ldots,V_d$ . (Note that we will always have $V_0=\textrm{span}\{\tau _0\}$ , where 0 is the group identity.)

4. 4. The eigenspaces are invariant subspaces of $u$ . To formulate it slightly differently: We may define the Fourier transform $\mathcal{F}$ as the matrix corresponding to the change of basis $(\delta _\alpha )\mapsto (\tau _\mu )$ , that is $\mathcal{F}^\alpha _\mu =\tau _\mu (\alpha )$ . Then we can define $\hat u=\mathcal{F}^{-1}u\mathcal{F}$ , which decomposes as a direct sum $\hat u=\hat u^{(0)}\oplus \hat u^{(1)}\oplus \cdots \oplus \hat u^{(d)}$ .

5. 5. Choose some of the spaces and define $W\;:\!=\;V_{i_1}\oplus V_{i_2}\oplus \cdots$ in such a way that $W$ generates $C(\Gamma )$ as an algebra. (In our examples below, it will be enough to take $W\;:\!=\;V_1$ , but it does not always have to be like this.) This means that $v\;:\!=\;\hat u^{(i_1)}\oplus \hat u^{(i_2)}\oplus \cdots$ is a faithful representation of $\mathop{\textrm{Aut}}\nolimits^+\mathop{\textrm{Cay}}(\Gamma,S)$ . (Since the coaction of $u$ or $\hat u$ restricted to $W$ must then again uniquely extend to the whole space $C(X)$ and hence we can recover the whole $u$ this way.)

6. 6. Any non-crossing partition $p\in NC(k,l)$ defines an intertwiner $T_p^{(N)}\in \textrm{Mor}(u^{\otimes k},u^{\otimes l})$ , where $N=|\Gamma |$ . We define $\hat T_p^{(N)}\;:\!=\;\mathcal{F}^{-1\,\otimes l}T_p^{(N)}\mathcal{F}^{\otimes k}$ , which has to be an intertwiner $\hat T_p^{(N)}\in \textrm{Mor}(\hat u^{\otimes k},\hat u^{\otimes l})$ . It is actually enough to study the intertwiners corresponding to the block partitions $b_{k,l}\in \mathscr{P}(k,l)$ —partitions, where all the $k$ upper and $l$ lower points are in a single block, so $[T_{b_{k,l}}^{(N)}]^{\beta _1,\ldots,\beta _l}_{\alpha _1,\ldots,\alpha _k}=\delta _{\alpha _1,\ldots,\alpha _k,\beta _1,\ldots,\beta _l}$ . The entries of the Fourier transformed intertwiner are easily computed as

   (4.2) \begin{equation} [\hat T_{b_{k,l}}]^{\nu _1,\ldots,\nu _l}_{\mu _1,\ldots,\mu _k}=N^{1-l}\delta _{\mu _1+\cdots +\mu _k,\nu _1+\cdots +\nu _l}. \end{equation}
   In particular, we can focus on the subspace $W$ and study the relations $\hat T^{(W)}_pv^{\otimes k}=v^{\otimes l}\hat T^{(W)}_p$ , where $\hat T^{(W)}_p=U^{\otimes l}\hat T_p^{(N)}U^{*\otimes k}$ , where $U$ is the coisometry $V_0\oplus \cdots \oplus V_d\to W$ .

5. Halved hypercube

The hypercube graph is bipartite, and hence, we can create a new graph of it by the procedure of halving—taking one of the two components of the associated distance-two graph. Taking a natural number $n\in \mathbb N$ , we define the $(n+1)$ -dimensional halved hypercube graph $\frac{1}{2}Q_{n+1}$ obtained by halving the ordinary hypercube $Q_{n+1}$ . That is, we take all the even vertices in $Q_{n+1}$ (equivalently, all odd vertices) and connect by an edge every pair of vertices that were in the distance two in the original hypercube $Q_{n+1}$ .

There is also a simpler definition of $\frac{1}{2}Q_{n+1}$ . Take the $n$ -dimensional hypercube $Q_n$ and add an additional edge for every pair of vertices in distance two. This is also known as squaring the graph. It holds that $Q_n^2=\frac{1}{2}Q_{n+1}$ . Using this description, we can write the adjacency matrix as follows

\begin{equation*}[A]^\alpha _\beta = \begin {cases} 1&\text {if $\beta =\alpha +\varepsilon _i$ for some $i$}\\[5pt] 1&\text {$\beta =\alpha +\varepsilon _i+\varepsilon _j$ for some $i\neq j$}\\[5pt] 0&\text {otherwise} \end {cases}\end{equation*}

Consequently, we see that $\frac{1}{2}Q_{n+1}=Q_n^2$ is a Cayley graph corresponding to the group $\Gamma =\mathbb Z_2^n$ with respect to the generating set $S=\{\varepsilon _i\}_{i=1}^n\cup \{\varepsilon _i+\varepsilon _j\}_{i<j}$ . In particular, the number of vertices is $N\;:\!=\;2^n$ .

Now we would like to determine the quantum automorphism group of the halved hypercube graph $\frac{1}{2}Q_{n+1}$ . Let us first summarize some known results. For $n\le 2$ , the graph is actually the full graph on $N=2^n$ vertices, so the quantum automorphism group is the free symmetric quantum group $S_N^+$ (for $n=0,1$ , i.e. $N=1,2$ , this actually coincides with the classical one $S_N$ ). For $n=3$ , the graph is the complement of the graph consisting of four isolated segments. Hence, its quantum automorphism group is the free hyperoctahedral quantum group $H_4^+=\mathbb Z_2\wr _*S_4^+$ . (Here $\wr _*$ denotes the free wreath product, which describes the quantum automorphism group of $n$ copies of a given graph [9].)

So, the question is what is the quantum automorphism group of $\frac{1}{2}Q_{n+1}$ for $n>3$ . The classical automorphism group is known to be $\mathbb Z_2^n\rtimes S_{n+1}$ . More precisely, it is the index two subgroup of the hyperoctahedral group $H_{n+1}=\mathbb Z_2\wr S_{n+1}=\mathbb Z_2^{n+1}\rtimes S_{n+1}$ (the symmetry group of the hypercube) imposing that the product of all the $\mathbb Z_2$ -signs is equal to one. This group is also known as the Coxeter group of type $D$ . Since the quantum automorphism group of $Q_{n+1}$ is $O_{n+1}^{-1}$ , we may expect that the answer for the halved hypercube $\frac{1}{2}Q_{n+1}$ should be the anticommutative special orthogonal group $SO_{n+1}^{-1}$ .

5.1. Determining ${\textbf{Aut}}^+\frac{1}{2}\boldsymbol{Q}_{\boldsymbol{n}+1}$

We follow Algorithm 1. We start by computing the spectrum using equation (4.1):

\begin{equation*}\lambda _\mu =\sum _{i=1}^n\tau _\mu (\varepsilon _i)+\sum _{i < j}\tau _\mu (\varepsilon _i+\varepsilon _j)=\sum _i(\!-\!1)^{\mu _i}+\sum _{i < j}(\!-\!1)^{\mu _i+\mu _j}=l_\mu +\frac {1}{2}l_\mu ^2-\frac {n}{2},\end{equation*}

where $l_\mu =\sum _i(\!-\!1)^{\mu _i}=n-2\deg \mu$ . Note that the eigenvalue depends again only on the degree of $\mu$ (the number of non-zero entries). So, denote $\lambda _d\;:\!=\;\lambda _\mu$ for $d=\deg \mu$ . So, $\lambda _d=\frac{1}{2}(l_d^2+2l_d-n)$ with $l_d=n-2d$ . After some computation, one can find out that

\begin{equation*}\lambda _d=\frac {1}{2}\left ((2d-n-1)^2-n-1\right )\end{equation*}

In contrast with the computation for the hypercube $Q_n$ , the eigenvalues $\lambda _0,\ldots,\lambda _n$ are not distinct. Instead, $\lambda _d=\lambda _{n+1-d}$ . Consequently, the matrix $\hat A$ as an intertwiner does not imply that the subspaces $V_i\;:\!=\;\textrm{span}\{\tau _\mu \mid \deg \mu =i\}$ are invariant. Instead, we have the following invariant subspaces: $\tilde V_0\;:\!=\;V_0$ , $\tilde V_1\;:\!=\;V_1+ V_n$ , $\tilde V_2\;:\!=\;V_2+ V_{n+1}$ and so on. In general, $\tilde V_i=V_i+ V_{n+1-i}$ is an invariant subspace for every $i=0,\ldots,\lfloor \frac{n+1}{2}\rfloor$ (using the convention $V_{n+1}=\{0\}$ ).

In order to describe the invariant spaces, define $\tau _{n+1}\;:\!=\;\tau _1\cdots \tau _n$ . Then $\tau _1,\ldots,\tau _n$ , $\tau _{n+1}$ is the basis of $\tilde V_1$ . The basis of each $\tilde V_i$ is exactly the set $\{\tau _\alpha \}$ with $\alpha \in \mathbb Z_2^{n+1}$ , $\deg \alpha =i$ . Denote by $u$ the fundamental representation of ${\textrm{Aut}}^+\frac{1}{2}Q_{n+1}$ and by $\hat u^{(i)}$ the block of $\hat u=\mathcal{F}^{-1}u\mathcal{F}$ corresponding to the invariant subspace $\tilde V_i$ .

Obviously, $\tau _1,\ldots,\tau _{n+1}$ are also generators of $C(\frac{1}{2}Q_{n+1})=C(\mathbb Z_2^{n})$ (since already $\tau _1,\ldots,\tau _n$ are generators) and we can write the algebra by generators and relations as

\begin{equation*}C\!\left({ \dfrac {1}{2}}Q_{n+1}\right)=C^*(\tau _1,\ldots,\tau _{n+1}\mid \tau _i^2=1,\;\tau _i\tau _j=\tau _j\tau _i,\;\tau _i^*=\tau _i,\;\tau _1\cdots \tau _{n+1}=1).\end{equation*}

Theorem 5.1. Consider $n\in \mathbb N\setminus \{1,3\}$ . The quantum automorphism group of the halved hypercube graph $\frac{1}{2}Q_{n+1}$ is isomorphic to the anticommutative special orthogonal group $SO_{n+1}^{-1}$ . It acts through the fundamental representation $u$ with $\hat u^{(i)}=v^{\mathop{\breve \wedge } i}$ , where $v$ is the fundamental representation of $SO_{n+1}^{-1}$ .

Proof. We follow the proof of Theorem 3.7. Let us first prove that $SO_{n+1}^{-1}\subset{\textrm{Aut}}^+\frac{1}{2}Q_{n+1}$ , that is, $SO_{n+1}^{-1}$ really acts on the halved hypercube. To do this, we are going to show that the mapping

\begin{equation*}\tau _j\mapsto \sum _{i=1}^{n+1}\tau _i\otimes u^i_j\end{equation*}

extends to a $*$ -homomorphism. Most of the work was already done in Lemma 3.11. It only remains to prove that the extra relation we have here $\tau _1\cdots \tau _{n+1}=1$ is also preserved under this action. That is, we need to show that

\begin{equation*}1=\sum _{i_1,\ldots,i_{n+1}=1}^{n+1}\tau _{i_1}\cdots \tau _{i_{n+1}}\otimes u_{i_11}\cdots u_{i_{n+1},n+1}\end{equation*}

This is indeed true thanks to the anticommutative determinant relation $u= 1$ .

Now for the converse direction, consider again the intertwiner and compute its restriction to $\tilde V_1$ . It is easy to check that we obtain the same formula

even on the “extended” space $\tilde V_1=V_1\oplus V_n$ (this is the point, where the assumption $n\neq 1,3$ is needed). Consequently, we have proven that $O_{n+1}^{-1}\supset{\textrm{Aut}}^+\frac{1}{2}Q_{n+1}$ .

Finally, it remains to find some intertwiner that would push us to the $SO_{n+1}^{-1}$ . Consider the block partition . The corresponding intertwiner is then of the form . We are interested in restriction of its Fourier transform on $\tilde V_1$ (more precisely, $\tilde V_1^{\otimes (n+1)}$ ):

This is exactly the antisymmetrizer $\breve{\mathcal{A}}_n\in \textrm{Mor}((\hat u^{(1)})^{\otimes n},1)$ , which exactly corresponds to the relation $\hat u^{(1)}=1$ .

5.2. Open problem

Let us finish this section with links to some open questions and related research. Note that there are free quantum analogues of the Coxeter groups of series $A$ (i.e. the symmetric groups $S_n$ ) and series $B$ or $C$ (i.e. the hyperoctahedral groups $H_n$ ), but so far we do not have any really free analogue of the Coxeter series $D$ (recall that series $D$ consists exactly of the symmetry groups of halved hypercubes $\frac{1}{2}Q_n$ ). The series of the anticommutative special orthogonal groups $SO_n^{-1}$ is a liberation of the Coxeter groups of type $D$ , but we should not call them free as they obey some sort of commutativity laws (namely the anticommutativity).

Question 5.2. Is there a free analogue for the Coxeter groups of series $D$ ?

One particular candidate was recently discovered in [15] for $n=4$ . For general $n$ , the question is still open. If some candidates appear, then the natural follow-up question would be: Is there some graph, whose quantum symmetry is this?

6. Folded hypercube

Folded hypercube is another graph that can be derived from the hypercube graph. Consider again $n\in \mathbb N$ . The $(n+1)$ -dimensional folded hypercube graph $FQ_{n+1}$ is a quotient of the hypercube $Q_{n+1}$ obtained by identifying the opposite corners, so $\alpha \equiv \alpha +\iota$ , where $\iota =(1,\ldots,1)=\varepsilon _1+\cdots +\varepsilon _n$ . By this, we end up with a graph having only half of the vertices, that is, $N=2^n$ .

Also here, there is a more convenient description. The $(n+1)$ -dimensional folded hypercube can be obtained from the $n$ -dimensional ordinary hypercube by connecting all the opposite corners by an additional edge. So, the adjacency matrix can be written as

\begin{equation*}[A]^\alpha _\beta = \begin {cases} 1&\text {if $\beta =\alpha +\varepsilon _i$ for some $i$,}\\[5pt] 1&\text {if $\beta =\alpha +\iota $,}\\[5pt] 0&\text {otherwise.} \end {cases}\end{equation*}

In other words, it is the Cayley graph of $\mathbb Z_2^n$ with respect to the generating set $\{\varepsilon _1,\ldots,\varepsilon _n,\iota \}$ .

Now, let us again review, what is known about its classical and quantum symmetries. For $n\le 2$ , the folded hypercube $FQ_{n+1}$ is just the complete graph on $N=2^n$ vertices, so its quantum automorphism group is $S_N^+$ . For $n=3$ , it is the complete bipartite graph on $4+4$ vertices, which is the complement of the disjoint union $K_4\sqcup K_4$ , so its quantum automorphism group is $S_4^+\wr _*\mathbb Z_2$ (again, we refer to [9] for explanation of the free wreath product). So, the interesting area is $n>3$ .

The classical automorphism group of $FQ_{n+1}$ for $n>3$ is of the form $\mathbb Z_2^{n}\rtimes S_{n+1}$ [23], but it is a different semidirect product than in the case of the halved cube. Here, we take the quotient group of $H_{n+1}=\mathbb Z_2^{n+1}\rtimes S_{n+1}$ by identifying the $(n+1)$ -tuple of signs with the opposite ones. In other words, it is the projective version $PH_{n+1}$ . Therefore, we expect $PO_{n+1}^{-1}$ to be the quantum automorphism group.

In [27], it was proven for $n$ even that the quantum automorphism group is actually $SO_{n+1}^{-1}$ , which matches our guess since it is isomorphic with $PO_{n+1}^{-1}$ according to Proposition 2.7.

6.1. Determining ${\textbf{Aut}}^+\boldsymbol{FQ}_{\boldsymbol{n}+1}$

Let us now compute the eigenvalues of the adjacency matrix:

\begin{align*} \lambda _\mu &=\sum _{i=1}^n\tau _\mu (\varepsilon _i)+\tau _\mu (\iota )=\sum _{i=1}^n(\!-\!1)^{\mu _i}+(\!-\!1)^{\mu _1+\cdots +\mu _n}\\[5pt] &=n-2\deg \mu +(\!-\!1)^{\deg \mu }=n+1-4\lceil 1/2\,\deg \mu \rceil \end{align*}

Again, the eigenvalue depends only on the degree of $\mu$ , but again the values of $\lambda _d\;:\!=\;\lambda _\mu$ with $\deg \mu =d$ are not mutually distinct. In this case, we have $\lambda _{2d-1}=\lambda _{2d}$ . So, we have invariant subspaces $\tilde V_0\;:\!=\;V_0$ , $\tilde V_2\;:\!=\;V_1\oplus V_2$ and so on. That is, $\tilde V_{2i}=V_{2i-1}\oplus V_{2i}$ , $i=0,1,\ldots,\lceil n/2\rceil$ (with $\tilde V_{n+1}=V_n$ if $n$ is odd). Denoting by $u$ the fundamental representation of ${\textrm{Aut}}^+FQ_{n+1}$ , we denote by

\begin{equation*}\hat u=\hat u^{(0)}\oplus \hat u^{(2)}\oplus u^{(4)}\oplus \cdots \end{equation*}

the decomposition of its Fourier transform according to the invariant subspaces.

Denote $\tau _{n+1}\;:\!=\;1$ , so the elements $\tau _{ij}\;:\!=\;\tau _{ji}\;:\!=\;\tau _i\tau _j$ with $1\le i<j\le n+1$ form a basis of $\tilde V_2$ . In general, the basis of $\tilde V_{2i}$ is $(\tau _\alpha )$ with $\alpha \in \mathbb Z_2^{n+1}, \deg \alpha =2i$ . We can use the basis of $\tilde V_2$ as a generating set of $C(\mathbb Z_2^n)=C(FQ_{n+1})$ :

\begin{equation*}C(FQ_{n+1})=C^*\left (\tau _{ij},\;1\le i < j\le n+1\middle |\begin {matrix} \tau _{ij}^2=1,\;\tau _{ij}^*=\tau _{ij},\\[5pt] \tau _{ij}\tau _{kl}=\tau _{kl}\tau _{ij},\;\tau _{ij}\tau _{ik}=\tau _{jk}\end {matrix}\right ).\end{equation*}

Alternatively, one can view $C(FQ_{n+1})$ as the subalgebra of $C(\mathbb Z_2^{n+1})=C(Q_{n+1})$

\begin{equation*}C(Q_{n+1})=C^*(\tau _1,\ldots,\tau _{n+1}\mid \tau _i^2=1,\;\tau _i^*=\tau _i,\;\tau _i\tau _j=\tau _j\tau _i)\end{equation*}

generated by the elements $\tau _{ij}=\tau _{ji}=\tau _i\tau _j$ . This exactly corresponds to the fact that $FQ_{n+1}$ is a quotient graph of $Q_{n+1}$ .

Theorem 6.1. Consider $n\in \mathbb N\setminus \{1,3\}$ . The quantum automorphism group of the folded hypercube graph $FQ_{n+1}$ is isomorphic to the anticommutative projective orthogonal group $PO_{n+1}^{-1}$ . It acts through the fundamental representation $u$ with $\hat u^{(i)}=v^{\mathop{\breve \wedge } 2i}$ , where $v$ is the fundamental representation of $O_{n+1}^{-1}$ .

Before proving this theorem, we need to do some preparatory work first. At this point, it is not even clear whether the prescribed representation $\bigoplus v^{\mathop{\breve \wedge } 2i}$ is a faithful representation of $PO_{n+1}^{-1}$ . We are actually going to prove that $v\mathop{\breve \wedge } v$ is a faithful representation. As a second step, we need to characterize $\mathscr{O}(PO_{n+1}^{-1})$ by generators and relations in terms of this representation $v\mathop{\breve \wedge } v$ . Equivalently, we need to find suitable generators of the representation category $\mathfrak{C}$ associated to $v\mathop{\breve \wedge } v$ . Only this allows us to use our standard machinery and prove Theorem 6.1.

This preparatory work is done in Section 6.2. The proof of Theorem 6.1 itself is then formulated in Section 6.3.

6.2. Projective version represented by exterior product

In Section 2.8, we defined the projective version of a compact matrix quantum group again as a compact matrix quantum group with the fundamental representation of the form $u\otimes u$ . In the classical case, we have also another faithful representation at our disposal.

Proposition 6.2. Consider $G\subset O_n$ , $n>1$ . Denote by $u$ its fundamental representation. Then $u\wedge u$ is a faithful representation of $PG$ .

Before formulating the proof, let us clarify the definition of projective groups. Our definition from Section 2.8 works for orthogonal groups only. For a general matrix group $G\subset GL_n$ , one typically defines its projective version to be the quotient $PG=G/\lambda I$ , $\lambda \in{\mathbb{C}}\setminus \{0\}$ (thus, in particular, $PGL_n=GL_n/Z(GL_n)$ ). Note that if $G$ is orthogonal, then $\lambda I\in G$ only for $\lambda =\pm 1$ . Therefore, assuming $G\subset O_n$ , our definition $PG=\{A\otimes A\mid A\in G\}$ is compatible with the general one (since we can reconstruct $A$ from $A\otimes A$ up to a global sign).

Finally, let us mention that over $\mathbb{C}$ , we obviously have $PGL_n=PSL_n$ , which is known to be a simple group, that is, it has no non-trivial normal subgroups.

Proof. ¹ Denote $V\;:\!=\;{\mathbb{C}}^n$ , so that $GL_n=GL(V)$ . Consider the homomorphism $\varphi \;:\; GL(V)\to GL(V\wedge V)$ mapping $A\mapsto A\wedge A$ . Since it maps multiples of identity to multiples of identity, it induces a homomorphism $\tilde \varphi \;:\; PGL(V)\to PGL(V\wedge V)$ . Since the $PGL(V)$ is simple (and the mapping $\tilde \varphi$ is obviously non-trivial), we must have that $\tilde \varphi$ is injective. Consequently, the kernel of $\varphi$ is contained in scalar matrices.

Now, we can restrict $\varphi$ to any subgroup $G\subset GL_n$ . Note that we can factor $\varphi$ as $\varphi \;:\; G\overset{\varphi _1}{\to } G'\overset{\varphi _2}{\to } G''$ , where $G'=\{A\otimes A\mid A\in G\}$ and $G''=\{A\wedge A\mid A\in G\}$ . We need to prove that $\varphi _2\;:\; G'\to G''$ is an isomorphism for $G\subset O_n$ as we have $G'\simeq PG$ in this case. Recall that we have the property $\ker \varphi \subset \{\lambda I\}$ . If $G\subset O_n$ , we must actually have $\ker \varphi \subset \{\pm I\}$ . But we know that $\ker \varphi _1=\{\pm I\}$ , and hence, $\varphi _2$ must indeed be an isomorphism.

It is known that the anticommutative orthogonal group can be obtained from the ordinary one by a 2-cocycle twist. Consequently, the two quantum groups are monoidally equivalent. More precisely, there exists a monoidal isomorphism of the corresponding representation categories $\textrm{Rep}\; O_n\to \textrm{Rep}\; O_n^{-1}$ mapping the fundamental representations one to another (i.e. there is also a monoidal isomorphism $\mathfrak{C}_{O_n}\to \mathfrak{C}_{O_n^{-1}}$ ). See for example [7, 17]. This implies the following corollary.

Corollary 6.3. Denote by $\breve u$ the fundamental representation of $O_n^{-1}$ , $n>1$ . Then $\breve u\mathop{\breve \wedge }\breve u$ is a faithful representation of $PO_n^{-1}$ .

Proof. Denote by $u$ the fundamental representation of $O_n$ . As mentioned above, there is a monoidal equivalence $\textrm{Rep}\; O_n\to \textrm{Rep}\; O_n^{-1}$ mapping $u\mapsto \breve u$ . It is easy to check that this monoidal equivalence also maps ${\mathcal{A}}_2^*{\mathcal{A}}_2\in \textrm{Mor}(u\otimes u,u\otimes u)$ to $\breve{\mathcal{A}}_2^*\breve{\mathcal{A}}_2\in \textrm{Mor}(\breve u\otimes \breve u,\breve u\otimes \breve u)$ . Consequently, it must map $u\wedge u$ to $\breve u\mathop{\breve \wedge }\breve u$ . Since the former is a faithful representation of $PO_n$ , the latter must be a faithful representation of $PO_n^{-1}$ .

In the following text, we will denote the projective orthogonal group represented by the matrix $u\wedge u$ by $\hat PO_n=(\mathscr{O}(PO_n),u\wedge u)$ . (The hat should remind us about the wedge product $\wedge$ .) Expressing the representation category $\mathfrak{C}_{\hat PO_n}$ in terms of the representation category $\mathfrak{C}_{O_n}$ is easy: We only have to compose all the intertwiners with the antisymmetrizer ${\mathcal{A}}_{2}\;:\; x\otimes y\mapsto x\wedge y$ . That is,

\begin{align*} \mathfrak{C}_{\hat PO_n}(k,l)&=\{{\mathcal{A}}_{(2)}^{\otimes l}T{\mathcal{A}}_{(2)}^{*\otimes k}\mid T\in \mathfrak{C}_{O_n}(2k,2l)\}\\[5pt] &=\{{\mathcal{A}}_{(2)}^{\otimes l}T_p{\mathcal{A}}_{(2)}^{*\otimes k}\mid p\in \mathsf{Pair}_n(2k,2l)\}, \end{align*}

where . (Pairing is a partition, where all blocks have size two. By an old result of Brauer [11], this is exactly the category corresponding to the orthogonal group. See also e.g. [12, 31, 14].) However, the question is, what is the generating set of this category. Finding some small set of generators is actually not so easy as it may seem on the first sight.

In order to understand the following text, one needs to familiarize the category operations on linear categories of partitions (or at least the linear category of all pairings $\mathsf{Pair}_n$ ). The rough idea is that in order to perform the composition of two pairings, one should simply follow the lines and, if needed, replace all loops by the factor $n$ . We refer to [16, Section 3] for more details.

In the following computations, we are going to treat the antisymmetrizer as a projection rather than a coisometry, so ${\mathcal{A}}_2^*={\mathcal{A}}_2$ . In this sense, it can be expressed in terms of partitions as . However, we are going to use a more convenient notation: In the diagrams, we will denote the antisymmetrizer by . So, for example, the antisymmetrization of will be denoted by , the antisymmetrization of the identity is . For any partition $p\in \mathscr{P}(2k,2l)$ , we are going to denote its antisymmetrization by . Consequently, we can write

(6.1) \begin{equation} \mathfrak{C}_{\hat PO_n}(k,l)=\{T_{{p}^{^{\!\!\!\circ}}}\mid p\in \mathsf{Pair}_n(2k,2l)\}, \end{equation}

so $\mathfrak{C}_{\hat PO_n}$ is modeled by a diagrammatic category $\mathsf{Pair}_n^\circ \;:\!=\;\{{p}^{^{\!\!\!\circ}}\mid p\in \mathsf{Pair}_n\}$ .

Theorem 6.4. Consider $n\neq 2,4,6,8$ . Then the category $\mathsf{Pair}_n^\circ$ is generated by the set .

Before proving the theorem, let us mention two important Corollaries:

Corollary 6.5. Consider $n\neq 2,4,6,8$ . Then the representation category $\mathfrak{C}_{\hat PO_n}$ is generated by .

Proof. Follows directly from Theorem 6.4 and equation (6.1).

Corollary 6.6. Consider $n\neq 2,4,6,8$ . Then the representation category $\mathfrak{C}_{\hat PO_n^{-1}}$ is generated by .

Proof. As we mentioned earlier, $O_n$ is monoidally equivalent with $O_n^{-1}$ , the monoidal equivalence maps the fundamental representation $u$ of $O_n$ to the fundamental representation $\breve u$ of $O_n^{-1}$ . As for the intertwiners, it maps $T_p\in \textrm{Mor}(u^{\otimes k},u^{\otimes l})$ for $p\in \mathsf{Pair}_n$ to $\breve T_p\in \textrm{Mor}(\breve u^{\otimes k},\breve u^{\otimes l})$ defined at the end of Section 2.4. The Corollary then follows by restricting the monoidal equivalence to the full subcategory $\mathfrak{C}_{PO_n}\subset \mathfrak{C}_{O_n}$ and applying to Corollary 6.5.

Now, we focus on the proof of Theorem 6.4. To make it easier to follow, we split it into several lemmata.

First, let us do a small remark on rotations in the category $\mathsf{Pair}_n^\circ$ . This category (as well as the category $\mathfrak{C}_{PO_n}$ ) is rigid and the duality morphism looks like this: . This again allows to do rotations in the category, but those rotations look a bit different than in the original category $\mathsf{Pair}_n$ . Consider some $p\in \mathscr{P}(2k,2l)$ . Let us call each pair of some $(2i+1)$ -st and $(2i+2)$ -nd point on either lower or upper row in $p$ a two-point. When drawing ${p}^{^{\!\!\!\circ}}$ , those two points are highlighted by the ellipse The element then allows to rotate those two points in ${p}^{^{\!\!\!\circ}}$ as a whole, not separately. For instance, rotating , we may obtain , but we cannot obtain . (The latter would actually equal to zero due to the antisymmetrization:

Lemma 6.7. Consider $n\neq 2$ . Then the category $\mathsf{Pair}_n^\circ$ is generated by the set .

Proof. Denote by $\mathscr{C}$ the category generated by the given generators. Notice that we have the duality morphism among the generators, so $\mathscr{C}$ is a rigid category and we can consider everything up to rotation now. For instance, we could equivalently consider instead of or instead of in the generating set.

As the first step, we prove that ${p}^{^{\!\!\!\circ}}_k\in{\mathscr{C}}$ for every $k\in \mathbb N\setminus \{1\}$ , where . That is, $p_k$ is the rotation of $\sqcap ^{\otimes k}$ . We do this by induction. The ${p}^{^{\!\!\!\circ}}_k$ for $k=2,3,4,5$ are among the generators, so we have the initial step and a couple of others already by assumption. We construct any ${p}^{^{\!\!\!\circ}}_k$ by precomposing ${p}^{^{\!\!\!\circ}}_{k-1}$ with :

As the second step, we prove that ${p}^{^{\!\!\!\circ}}\in{\mathscr{C}}$ for every pairing $p\in \mathscr{P}_2(0,2k)$ . We use the element , which allows to permute the two points in ${p}^{^{\!\!\!\circ}}$ . We claim that any $p\in \mathscr{P}_2(0,2k)$ can be obtained by such two-point permutations from some ${p}^{^{\!\!\!\circ}}_{i_1}\otimes \cdots \otimes {p}^{^{\!\!\!\circ}}_{i_l}$ . Since we already proved that ${p}^{^{\!\!\!\circ}}_i\in{\mathscr{C}}$ for every $i>1$ and , this will finish the proof of the theorem. Note that thanks to the antisymmetrization, the order of the two points in a two-point is irrelevant (only affecting the $\pm$ sign).

So consider any $p\in \mathscr{P}_2(0,2k)$ . Take the first two-point and denote the corresponding points by $\textrm{pt}_1$ and $\textrm{pt}_2$ . Take the point which is paired with $\textrm{pt}_2$ and denote it by $\textrm{pt}_3$ . We denote by $\textrm{pt}_4$ its neighbor that form a two-point with $\textrm{pt}_3$ . Perform a two-point permutation of $p$ such that $(\textrm{pt}_3,\textrm{pt}_4)$ is the second two-point. Call $\textrm{pt}_5$ the point, which is paired with $\textrm{pt}_4$ and continue in this manner until we find some $\textrm{pt}_{2i_1}$ , which is paired with $\textrm{pt}_1$ . At this point, we have that ${p}^{^{\!\!\!\circ}}$ is a two-point permutation of ${p}^{^{\!\!\!\circ}}_{i_1}\otimes {q}^{^{\!\!\!\circ}}$ , where $q\in \mathscr{P}_2(0,2k-2i_1)$ . If we use mathematical induction, we may assume that $q$ is already a two-point permutation of $p_{i_2}\otimes \cdots \otimes p_{i_l}$ .

Lemma 6.8. Suppose $n\neq 4,6,8$ . Then both and are generated by .

Proof. Denote by $\mathscr{C}$ the category generated by . Recall that is a rotation of . So, we can do the following computation in $\mathscr{C}$ :

By rotation, this means that $\mathscr{C}$ contains the linear combinations and . Now, we can do the following (we leave out the detailed computation now):

Subtracting , , , —those all being elements of $\mathscr{C}$ —we get that $\mathscr{C}$ must contain . Finally, squaring this element, we get

Doing all the possible subtractions and multiplying by 4, we get that $\mathscr{C}$ contains , where

\begin{equation*}\alpha =(n-8)^2(n-2)+8(n-8)=(n-4)(n-6)(n-8)\end{equation*}

Consequently, unless $n=4,6,8$ . Since we also proved that , we now have that .

Lemma 6.9. Suppose $n\neq 4$ . Then is generated by .

Proof. First, we generate the following two elements of $\mathscr{C}$ :

(6.2)

(6.3)

Now, take the second element and permute the third and fourth two-point to obtain . Adding the element (6.2), we get

(6.4)

Now we go another way: Start with the element (6.2) and precompose it with . We obtain . Multiplying by four and adding (6.4), we finally get

Proof of Theorem 6.4 . Follows directly from the lemmata above. Lemma 6.8 tells us that and generate and . Lemma 6.9 shows that those together generate . Finally, Lemma 6.7 shows that all those together already generate the whole category $\mathsf{Pair}_n^\circ$ .

In the formulation of Theorem 6.4, we needed to make the assumption $n\neq 2,4,6,8$ . We can easily repair the formulation to include the cases $n=6,8$ as well. Notice that the only place, where we needed the assumption $n\neq 6,8$ was Lemma 6.8. So, we can modify the formulation of the theorem as follows:

Proposition 6.10. Consider $n\neq 2,4$ . Then the category $\mathsf{Pair}_n^\circ$ is generated by the set .

We will actually need a slightly more technical result in the sequel.

Proposition 6.11. Consider $n\neq 2,4$ . Then the category $\mathsf{Pair}_n^\circ$ is generated by the set , where

(6.5)

Proof. We only need to show that the given intertwiners generate and . We do this by modifying the proof of Lemma 6.8.

In Lemma 6.8, we showed that actually generate the following elements (for which we did not yet need the assumption $n\neq 6,8$ ): The element A rotation of this one is the element . We also construct the element , which can be rotated into .

Subtracting those together with , from the element (6.5), we get that $\mathscr{C}$ contains . Consequently, it must contain both and (For $n=7$ , we can use Lemma 6.8 directly.)

Finally, let us reveal the meaning of the mysterious linear combination $p$ from equation (6.5). One can easily check that given a tuple of indices $i_1$ , $j_1$ , $i_2$ , $j_2$ , $i_3$ , $j_3$ , $i_4$ , $j_4$ such that $i_k\neq j_k$ , we have

(6.6) \begin{equation} [\breve T_p^{(n)}]^{(i_1,j_1),(i_2,j_2),(i_3,j_3),(i_4,j_4)}=\begin{cases}1&\textrm{if the indices can be paired}\\[5pt] 0&\textrm{otherwise}\end{cases} \end{equation}

Indeed, the individual partitions just depict the ways of how the indices can be paired. (The minus signs are there because of the crossings to compensate the minus sign given by the deformed functor $\breve T^{(n)}$ .)

Thus, we have the following Corollary.

Corollary 6.12. Consider $n\neq 2,4$ . Then the representation category $\mathfrak{C}_{\hat PO_n^{-1}}$ is generated by , where $\breve T_p^{(n)}$ is given by equation ( 6.6 ).

6.3. Proof of Theorem 6.1

Denote by $v$ the fundamental representation of $O_{n+1}^{-1}$ . Theorem 6.1 says that ${\textrm{Aut}}^+FQ_n$ is isomorphic with $PO_{n+1}^{-1}$ acting through $u$ with $\hat u=\bigoplus v^{\mathop{\breve \wedge } 2i}$ . First step of the proof was provided by Corollary 6.3, where we showed that $v\mathop{\breve \wedge } v$ is a faithful representation of $PO_{n+1}^{-1}$ , and hence, the whole $\bigoplus v^{\mathop{\breve \wedge } 2i}$ must be a faithful representation.

Secondly, we show that $PO_{n+1}^{-1}$ acts on $FQ_{n+1}$ , which then implies that $PO_{n+1}^{-1}\subset{\textrm{Aut}}^+ FQ_{n+1}$ . But there is no work to be done here as this is just a restriction of the action of $O_{n+1}^{-1}$ on $Q_{n+1}$ . Indeed, recall that we have the coaction $\alpha \;:\; C(Q_{n+1})\to C(Q_{n+1})\otimes \mathscr{O}(O_{n+1}^{-1})$ by $\tau _j\mapsto \sum _{i=1}^n \tau _i v^i_j$ and that $C(FQ_{n+1})$ is the subalgebra of $C(Q_{n+1})$ generated by even polynomials in $\tau _j$ . Restricting to this subalgebra, we get exactly the desired coaction $C(FQ_{n+1})\to C(FQ_{n+1})\otimes \mathscr{O}(PO_{n+1}^{-1})$ .

Finally, we need to prove the converse inclusion ${\textrm{Aut}}^+ FQ_{n+1}\subset PO_{n+1}^{-1}$ . So, we need to show that $\hat u^{(2)}$ is a representation of $PO_{n+1}^{-1}$ . Assume for a moment that $n+1\neq 2,4,6,8$ . Thanks to Corollary 6.6, we only need to show that and are intertwiners of $\hat u^{(1)}$ . The first one is just the orthogonality, which is automatic as Fourier transform preserves orthogonality. The second one is easy to obtain by looking at the Fourier transform of projected to $\tilde V_2$ . Its entries are then

Note that due to the antisymetrization, we need to also assume $i_1\neq j_1$ , $i_2\neq j_2$ , and $i_3\neq j_3$ . We claim that this exactly matches the intertwiner . Indeed, the latter is just a symmetrization of . It is clear that the only way how to pair a tuple of indices $i_1\neq j_1$ , $i_2\neq j_2$ , $i_3\neq j_3$ is according to the partition (up to symmetrization, i.e. permuting neighboring pairs of points). This finishes the proof for the case $n\neq 6,8$ .

For the cases $n=6,8$ , consider the intertwiner of $\hat u^{(1)}$ induced by Again, the entries of are zeros and ones depending on whether the indices can be paired or not. That is, , where $\breve T^{(n+1)}_p$ is given by equation (6.6). Thus, the result follows from Corollary 6.12.

6.4. Open problem

Let us again finish with some open problem. The hyperoctahedral group $H_n$ can be seen not only as the symmetry group of the hypercube $Q_n$ but also as the symmetry group of $n$ copies of a segment $K_2\sqcup \cdots \sqcup K_2$ . While the quantum symmetry of the former is $O_n^{-1}$ , the quantum symmetry of the latter is $H_n^+$ , which are two distinct quantum groups. We have just proven that $PO_n^{-1}$ is the quantum symmetry of the folded hypercube $FQ_n$ . This result suggests the following question:

Question 6.13. Is there some graph, whose quantum symmetry is described by the quantum group $PH_n^+$ for some $n$ ? Does $PH_n^+$ act on the set of $N$ points for some $N$ at all? (That is, do we have $PH_n^+\subset S_N^+$ for some $N$ ?)

This is related to a big question on whether there is a quantum analogue of the Frucht theorem, which was discussed recently in [10].

7. Hamming graphs

Hamming graph $H(n,m)$ is the Cayley graph of the group $\Gamma =\mathbb Z_m^n$ with respect to the generating set $S=\{a\varepsilon _i\mid i=1,\ldots,n,\;a=1,\ldots,m-1\}$ , where $\varepsilon _i=(0,\ldots,0,1,0,\ldots,0)$ is the generator of the $i$ th copy of $\mathbb Z_m$ . In other words, vertices of $H(n,m)$ are $n$ -tuples of numbers $a=0,\ldots,m-1$ (i.e. indeed, $V=\mathbb Z_m^n$ ) and two such tuples are connected with an edge if and only if they differ in exactly one coordinate.

Another possible description is using the Cartesian product of graphs (see Section 7.3): Hamming graph $H(n,m)$ is the $n$ -fold Cartesian product of the full graph $K_m$ , that is, $H(n,m)=K_m\mathrel{\square }\cdots \mathrel{\square } K_m$ .

The classical automorphism group of $H(n,m)$ is known to be the wreath product $S_m\wr S_n$ . About the quantum automorphism group, only partial results are known so far:

• $n=1$ : $H(1,m)$ is the full graph $K_m$ , so ${\textrm{Aut}}^+H(1,m)=S_m^+$ .

• $m=1$ : $H(n,1)$ contains just a single vertex.

• $m=2$ : $H(n,2)$ is the hypercube $Q_n$ , so ${\textrm{Aut}}^+H(n,2)=O_n^{-1}$ .

• $m=3$ : $H(n,3)$ was proven to have no quantum symmetries [25], so ${\textrm{Aut}}^+H(n,3)={\textrm{Aut}}\; H(n,3)=S_3\wr S_n$ .

• $m>3$ : $H(n,m)$ was proven to have some quantum symmetries [25], but the explicit quantum group was not known.

We are going to answer the question about the quantum automorphism group of Hamming graphs in full generality in the following theorem (by which we also answer Question 8.2(i) of Simon Schmidt’s PhD thesis [26]):

Theorem 7.1. Consider $m\in \mathbb N\setminus \{1,2\}$ . Then ${\textrm{Aut}}^+H(n,m)\simeq S_m^+\wr S_n$ .

Before formulating the proof itself, we would like to explain some important ingredients more in detail.

7.1. Full graph

As we just mentioned, a special case for $n=1$ is the full graph $K_m$ . Of course, we know that the quantum symmetry group of the full graph is the free symmetric quantum group $S_m^+$ . Nevertheless, we would like to use this simple example to point out a certain subtlety that one needs to keep in mind when working with cyclic groups $\mathbb Z_m$ for $m\neq 2$ .

So, the full graph $K_m$ is the Cayley graph corresponding to the group $\mathbb Z_m$ and the generating set consisting of all elements of the group except for identity, so $K_m=\textrm{Cay}(\mathbb Z_m,\mathbb Z_m\setminus \{0\})$ . We denote simply by $a=0,\ldots,m-1$ the elements of $\mathbb Z_m$ and by $\tau _a\in \textrm{Irr}\;\mathbb Z_m$ the characters $\tau _a(b)=\gamma ^{ab}$ , where $\gamma$ is some primitive $m$ th root of unity. The spectrum of $K_m$ is hence computed as

\begin{equation*}\lambda _a=\sum _{b=1}^{m-1}\tau _a(b)=\sum _{b=1}^{m-1}\gamma ^{ab}= \begin {cases} m-1&a=0,\\[5pt] -1&\text {otherwise.} \end {cases}\end{equation*}

Now comes the important point we wanted to make in this subsection: The Fourier transform $\mathcal{F}$ on $\mathbb Z_m$ , that is, the transformation of the bases $(\delta _a) \to (\tau _a)$ is unitary, but not orthogonal! Its entries are $[\mathcal{F}]^a_b=\gamma ^{ab}$ , so they are obviously not real (unless $m=2$ ). To be more concrete, the basis elements $\tau _a$ , which are the columns of $\mathcal{F}$ are not self-adjoint, but satisfy $\tau _a^*=\tau _{m-a}$ .

Consequently, if we denote $\hat S_m\;:\!=\;\mathcal{F}^{-1}S_m\mathcal{F}$ and $\hat S_m^+\;:\!=\;\mathcal{F}^{-1}S_m^+\mathcal{F}$ the symmetric group and the free symmetric quantum group represented by the Fourier transform of the standard permutation matrices, then those matrix (quantum) groups are not orthogonal. Instead, they satisfy $\hat S_m\subset \hat S_m^+\subset O^+(F)\subset U_m^+$ with $F\in M_m({\mathbb{C}})$ defined by $F^a_b=\delta _{a+b,m}$ (indices modulo $m$ ). That is, $u^{a\,*}_b=u^{m-a}_{m-b}$ . (Here, $U_n^+$ denotes the free unitary quantum group [29].)

Therefore, if we study the intertwiners of $\hat S_m\simeq{\textrm{Aut}}^+ K_m$ in this basis, then instead of the familiar maps such as $T^{(m)}_{\sqcap }$ , , , we discover their Fourier transforms, which may look rather exotic.

Observation 7.2. The category $\mathfrak{C}_{\hat S_m}$ is generated by $\hat T^{(m)}_{\sqcap }$ and , where

7.2. Wreath product of quantum groups

We should also explain, what does the $\wr$ sign in the formulation of Theorem 7.1 means. It is not the free wreath product of quantum groups, but the classical one. Before specifying, what we mean by a classical wreath product of quantum groups, let us recall the free definition by Bichon [9].

Definition 7.3. Let $G\subset U_m^+$ be a quantum group with fundamental representation $v=(v^a_b)$ and let $H\subset S_n^+$ be a quantum permutation group with fundamental representation $w=(w^i_j)$ . Then we define the free wreath product of $G$ and $H$ to be the quantum group

\begin{equation*}G\wr _* H\;:\!=\;(\mathscr {O}(G)^{* n}* \mathscr {O}(H),u),\quad \text {where}\quad u^{ai}_{bj}=v^{ai}_bw^i_j,\end{equation*}

where we denote by $v^i=(v^{ai}_b)_{a,b}$ the fundamental representations of the $n$ copies of $G$ occurring in the definition of $G\wr _* H$ .

Remark 7.4. Let us state a few important remarks to this definition.

1. a. Although we defined the free wreath product $G\wr _* H$ for compact matrix quantum groups using their fundamental representations, the original definition of Bichon is formulated for arbitrary compact quantum group $G$ not depending on its particular fundamental representation (see [9] for details). In particular, if we take some other matrix realization $G'\simeq G$ of the quantum group $G$ , then $G'\wr _* H$ is isomorphic to $G\wr _* H$ .

2. b. As in the classical case, the free wreath product $G\wr _* H$ has a sort of a (free) semidirect product structure. What we mean by this is the following:

3. c. The matrix $w$ is a representation of $G\wr _* H$ . Therefore, $H$ can be seen as a quotient of $G\wr _* H$ .

4. d. On the other hand, the matrices $v^i$ are not representations of $G\wr _* H$ —the coproduct is mixing (quantum-permuting) the indices $i$ non-trivially:

   \begin{equation*} \Delta(v^{ai}_{b}) = \sum_{c,k} v^{ai}_{c} w^{i}_{k} \otimes v^{ck}_{b}. \end{equation*}

5. e. We can express

   \begin{equation*}w^i_j=\sum _b u^{ai*}_{bj}u^{ai}_{bj}=\sum _a u^{ai*}_{bj}u^{ai}_{bj},\qquad v^{ai}_b=\sum _j u^{ai}_{bj}\end{equation*}
   That is, the entries $u^{ai}_{bj}$ indeed generate the whole algebra $\mathscr{O}(G)^{\otimes n}\otimes \mathscr{O}(H)$ . This remark is essential to notice that the definition above is a good definition of $G\wr H$ as a compact matrix quantum group.

Now the classical wreath product is supposed to be given by passing from the free product to the tensor product. So, define $\mathscr{O}(G\wr H)\;:\!=\;\mathscr{O}(G)^{\otimes n}\otimes \mathscr{O}(H)$ .

Lemma 7.5. Consider a quantum group $G\subset U_m^+$ and a classical permutation group $H\subset S_n$ . Then the comultiplication $\Delta \;:\; \mathscr{O}(G\wr _*H)\to \mathscr{O}(G\wr _*H)\otimes \mathscr{O}(G\wr _*H)$ passes to the quotient $\mathscr{O}(G\wr H)$

Proof. Denote $\Delta '\;:\!=\;(q\otimes q)\circ \Delta$ , where $q$ is the projection $\mathscr{O}(G\wr _*H)\to \mathscr{O}(G\wr H)$ . We only need to prove that $\Delta '(v^{ai}_b)\Delta '(v^{cj}_d)=\Delta '(v^{cj}_d)\Delta '(v^{ai}_b)$ whenever $i\neq j$ and $\Delta '(v^{ai}_b)\Delta '(w^k_l)=\Delta '(w^k_l)\Delta '(v^{ai}_b)$ . Both are quite straightforward. Let’s have a look on the first one:

\begin{equation*}\Delta '(v^{ai}_b)\Delta '(v^{cj}_d)=\sum _{x,k,y,l}v^{ai}_xw^i_kv^{cj}_yw^j_l\otimes v^{xk}_bv^{yl}_d\end{equation*}

Now, notice that the factors in the left $\otimes$ -factor can be arbitrarily permuted. Assuming $k\neq l$ , the same holds for the right $\otimes$ -factor. For $k=l$ , we have $w^i_kw^j_l=0$ , so the left $\otimes$ -factor equals to zero. Consequently, we see that the coproducts indeed commute as we needed. The second condition is proven the same way using the fact that $\Delta (w^i_j)=\sum _k w^i_k\otimes w^k_j$ .

Definition 7.6. For a quantum group $G\subset U_m^+$ and a classical permutation group $H\subset S_n$ , we define their wreath product $G\wr H$ to be the quantum subgroup of $G\wr _*H$ corresponding to the quotient algebra $\mathscr{O}(G\wr H)=\mathscr{O}(G)^{\otimes n}\otimes \mathscr{O}(H)$ .

7.3. Cartesian product of graphs

Given two graphs $X_1$ and $X_2$ , we define their Cartesian product to be the graph $X_1\mathrel{\square } X_2$ with the vertex set $V(X_1\mathrel{\square } X_2)=V(X_1)\times V(X_2)$ and with an edge $((v_1,v_2),(w_1,w_2))\in E(X_1\mathrel{\square } X_2)$ if and only if $(v_1,w_1)\in E(X_1)$ and $v_2=w_2$ or if $(v_2,w_2)\in E(X_2)$ and $v_1=w_1$ . Alternatively, we can describe the Cartesian product by its adjacency matrix $A_{X_1\mathrel{\square } X_2}=A_{X_1}\otimes I_{X_2}+I_{X_1}\otimes A_{X_2}$ , where $I_{X_i}$ denotes the identity matrix.

The Cartesian product of graphs is associative and we can conveniently describe the product of $n$ given graphs by the adjacency matrix

\begin{equation*}A_{X_1\mathrel {\square }\cdots \mathrel {\square } X_n}=A_{X_1}\otimes I_{X_2}\otimes I_{X_3}\otimes \cdots \otimes I_{X_n}+I_{X_1}\otimes A_{X_2}\otimes I_{X_3}\otimes \cdots \otimes I_{X_n}+\cdots \end{equation*}

It is well known that if $G$ acts on a finite space or a graph $X$ by $\delta _a\mapsto \sum _b\delta _b\otimes v^b_a$ , then $G\wr S_n$ acts on the $n$ -fold disjoint union $X\sqcup \cdots \sqcup X$ by $\delta _{ai}\mapsto \sum _{b,j}\delta _{bj}\otimes u^{bj}_{ai}$ . (Notice that $C(X\sqcup \cdots \sqcup X)=C(X)\oplus \cdots \oplus C(X)$ ; the indices $i,j$ are indexing the $n$ copies of $X$ or $C(X)$ here.)

Now, consider the Cartesian product $X\mathrel{\square }\cdots \mathrel{\square } X$ . In this case, we have $C(X\mathrel{\square }\cdots \mathrel{\square } X)=C(X)\otimes \cdots \otimes C(X)$ . Consider a basis $(x_i)_{i=0}^{m-1}$ of $C(X)$ such that $x_0=1_{C(X)}$ (if $X$ is a regular graph, then we can consider the basis of eigenvectors of $A_X$ ). Denote by $\hat v^a_b$ the entries of the action of $G$ on $X$ in this basis, so $x_a\mapsto \sum _bx_b\otimes \hat v^b_a$ . Denote $x_{ai}\;:\!=\;1_{C(X)}\otimes \cdots \otimes 1_{C(X)}\otimes x_a\otimes 1_{C(X)}\otimes \cdots \otimes 1_{C(X)}$ , where the $x_a$ is on the $i$ th place. In the following we are going to prove that $x_{ai}\mapsto \sum _{b,j}x_{bj}\otimes \hat u^{bj}_{ai}$ extends to an action of $G\wr S_n$ on $X\mathrel{\square }\cdots \mathrel{\square } X$ , where $\hat u^{bj}_{ai}=\hat v^{bj}_aw^j_i$ .

First, assume for a moment that this action really exists. Then it is easy to determine, how it must act on the basis $x_{a_1,\ldots,a_n}\;:\!=\;x_{a_1}\otimes \cdots \otimes x_{a_n}$ of $C(X\mathrel{\square }\cdots \mathrel{\square } X)$ :

\begin{align*} x_{a_1,\ldots,a_n} &\mapsto \sum _{b_1,\ldots,b_n=0}^{m-1}\sum _{k_1,\ldots,k_n=1}^n x_{b_1k_1}\cdots x_{b_nk_n}\otimes \hat u^{b_1k_1}_{a_11}\cdots \hat u^{b_nk_n}_{a_nn}\\[5pt] &=\sum _{b_1,\ldots,b_n=0}^{m-1}\sum _{\sigma \in S_n} x_{b_1\sigma (1)}\cdots x_{b_n\sigma (n)}\otimes \hat u^{b_1\sigma (1)}_{a_11}\cdots \hat u^{b_n\sigma (n)}_{a_nn}\\[5pt] &=\sum _{b_1,\ldots,b_n=0}^{m-1}\sum _{\sigma \in S_n} x_{b_{\sigma ^{-1}(1)}1}\cdots x_{b_{\sigma ^{-1}(n)}n}\otimes \hat u^{b_1\sigma (1)}_{a_11}\cdots \hat u^{b_n\sigma (n)}_{a_nn}\\[5pt] &=\sum _{b_1,\ldots,b_n=0}^{m-1}\sum _{\sigma \in S_n} x_{b_11}\cdots x_{b_nn}\otimes \hat u^{b_{\sigma (1)}\sigma (1)}_{a_11}\cdots \hat u^{b_{\sigma (n)}\sigma (n)}_{a_nn}\\[5pt] &=\sum _{b_1,\ldots,b_n=0}^{m-1}x_{b_1,\ldots,b_n}\otimes \hat{\tilde u}^{b_1,\ldots,b_n}_{a_1,\ldots,a_n}, \end{align*}

where $\hat{\tilde u}^{b_1,\ldots,b_n}_{a_1,\ldots,a_n}=\sum _{\sigma \in S_n}\hat u^{b_{\sigma (1)}\sigma (1)}_{a_11}\cdots \hat u^{b_{\sigma (n)}\sigma (n)}_{a_nn}$ . We can also change the basis to the standard one and obtain $\delta _{a_1,\ldots,a_n}\mapsto \sum _{b_1,\ldots,b_n}\delta _{b_1,\ldots,b_n}\otimes \tilde u^{b_1,\ldots,b_n}_{a_1,\ldots,a_n}$ , where $\tilde u$ is given by a formula analogous to the one for $\hat{\tilde u}$ .

Lemma 7.7. Let $G$ be a compact matrix quantum group with fundamental representation $v$ . Then

\begin{equation*}\tilde u^{b_1,\ldots,b_n}_{a_1,\ldots,a_n} \;:\!=\;\sum _{\sigma \in S_n}u^{b_{\sigma (1)}\sigma (1)}_{a_11}\cdots u^{b_{\sigma (n)}\sigma (n)}_{a_nn} =\sum _{k_1,\ldots,k_n=1}^nu^{b_{k_1}k_1}_{a_11}\cdots u^{b_{k_n}k_n}_{a_nn}\end{equation*}

is a representation of $G\wr S_n$ . If $G\subset S_m^+$ , then $\tilde u$ is faithful.

Proof. First, we should prove the second equality in the formula. To see this, it is enough to notice that the product $u^{b_{k_1}k_1}_{a_11}\cdots u^{b_{k_n}k_n}_{a_nn}$ equals to zero whenever $k_i=k_j$ for some $i\neq j$ (since $w^{k_i}_iw^{k_j}_j=0$ ).

Proving that $\tilde u$ is a representation of $G\wr S_n$ is a straightforward computation:

\begin{align*} \Delta (u^{b_1,\ldots,b_n}_{a_1,\ldots,a_n}) &=\sum _{\sigma \in S_n}\Delta (u^{b_{\sigma (1)}\sigma (1)}_{a_11})\cdots \Delta (u^{b_{\sigma (n)}n}_{a_nn})\\[5pt] &=\sum _{\sigma \in S_n}\sum _{\substack{c_1,\ldots,c_n\\ k_1,\ldots,k_n}}u^{b_{\sigma (1)}\sigma (1)}_{c_1k_1}\cdots u^{b_{\sigma (n)}\sigma (n)}_{c_nk_n}\otimes u^{c_1k_1}_{a_11}\cdots u^{c_nk_n}_{a_nn}\\[5pt] &=\sum _{d_1,\ldots,d_n}\sum _{\pi,\rho \in S_n}u^{b_{\rho (1)}\rho (1)}_{d_11}\cdots u^{b_{\rho (n)}\rho (n)}_{d_nk_n}\otimes u^{d_1\pi (1)}_{a_11}\cdots u^{d_n\pi (n)}_{a_nn}\\[5pt] &=\sum _{d_1,\ldots,d_n}u^{b_1,\ldots,b_n}_{d_1,\ldots,d_n}\otimes u^{d_1,\ldots,d_n}_{a_1,\ldots,a_n} \end{align*}

To get from the second to the third line, we need to notice several things: First, as we already mentioned, the product $u^{c_1k_1}_{a_11}\cdots u^{c_nk_n}_{a_nn}$ equals to zero unless $k_1,\ldots,k_n$ is a permutation of $1,\ldots,n$ . Hence, we can denote this permutation by $\pi$ , so $k_i=\pi (i)$ . Secondly, the terms of the product mutually commute, so we can reorder the first product as $u^{b_{\sigma (1)}\sigma (1)}_{c_1k_1}\cdots u^{b_{\sigma (n)}\sigma (n)}_{c_nk_n}=u^{b_{\sigma (\pi ^{-1}(1))}\sigma (\pi ^{-1}(1))}_{c_{\pi ^{-1}(1)}1}\cdots u^{b_{\sigma (\pi ^{-1}(n))}\sigma (\pi ^{-1}(n))}_{c_{\pi ^{-1}(n)}n}$ . Finally, we denote $\rho \;:\!=\;\sigma \circ \pi ^{-1}$ and $d_i\;:\!=\;c_{\pi ^{-1}(i)}$ .

Assume now that $G\subset S_m$ for some $m$ . The proof of the last statement—that $\tilde u$ is faithful—gets a bit easier if we work in the basis $(x_a)_{a=0}^{m-1}$ of $C(X)$ such that $x_0=1_{C(X)}$ since $x_0$ is an invariant vector of $v$ . So denote by $\hat v^a_b$ the entries of $v$ in the basis $(x_a)$ and similarly $\hat u^{ai}_{bj}\;:\!=\;\hat v^{ai}_bw^i_j$ . We have then $\hat v^0_0=1$ and $\hat v^0_b=0=\hat v^a_0$ for every $a$ , $b$ . We need to show that the entries of $\hat{\tilde u}$ already generate the whole algebra $\mathscr{O}(G\wr S_n)$ . Of course, it is enough to show that it generates the generators $\hat v^{ai}_b$ and $w^i_j$ . We claim that $\hat{\tilde u}^{0,\ldots,0,a,0,\ldots,0}_{0,\ldots,0,b,0,\ldots,0}=\hat u^{ai}_{bj}$ , where the $a$ is on the $i$ th position and the $b$ is on the $j$ th position on the left-hand side. Indeed, we get

(7.1) \begin{equation} \hat{\tilde u}^{0,\ldots,0,a,0,\ldots,0}_{0,\ldots,0,b,0,\ldots,0}=\sum _{\substack{k_1,\ldots,k_n=1\\ \textrm{except for $k_j\;:\!=\;i$}}}^n \hat v^{ai}_b\,w^{k_1}_1\cdots w^{k_n}_n=\hat v^{ai}_bw^i_j=\hat u^{ai}_{bj}. \end{equation}

Proposition 7.8. Let $\Gamma$ be a graph. Then ${\textrm{Aut}}^+(\Gamma \mathrel{\square }\cdots \mathrel{\square }\Gamma )\supset ({\textrm{Aut}}^+\Gamma )\wr S_n$ . More precisely, $G\wr S_n$ acts faithfully on the $n$ -fold product $\Gamma \mathrel{\square }\cdots \mathrel{\square }\Gamma$ by $\delta _{a_1,\ldots,a_n}\mapsto \sum _{b_1,\ldots,b_n}\delta _{b_1,\ldots,b_n}\otimes \tilde u^{b_1,\ldots,b_n}_{a_1,\ldots,a_n}$ .

Proof. Notice that we can express $\tilde u$ in a more “matricial way”

\begin{equation*}\tilde u=\sum _{\sigma \in S_n}T_\sigma (v^{\sigma (1)}\otimes \cdots \otimes v^{\sigma (n)})\delta _\sigma,\end{equation*}

where $T_\sigma \;:\; ({\mathbb{C}}^m)^{\otimes n}\to ({\mathbb{C}}^m)^{\otimes n}$ is the linear operator permuting the tensor factors according to $\sigma$ and $\delta _{\sigma }\;:\!=\;w_1^{\sigma (1)}\cdots w_n^{\sigma (n)}$ (it is actually indeed the delta the delta function $S_n\to{\mathbb{C}}$ mapping $\delta _\sigma (\pi )=\delta _{\sigma \pi }$ ). We will use this matrix approach throughout the proof, but one could of course also rewrite the computation in terms of the matrix entries.

We want to show that $({\textrm{Aut}}^+\Gamma )\wr S_n$ represented by the faithful representation $\tilde u$ is a quantum subgroup of ${\textrm{Aut}}^+(\Gamma \mathrel{\square }\cdots \mathrel{\square }\Gamma )$ . To do this, we need to show that the representation category associated to $\tilde u$ contains the generators of the category $\mathfrak{C}_{{\textrm{Aut}}^+(\Gamma \mathrel{\square }\cdots \mathrel{\square }\Gamma )}$ , which are $T_{\uparrow }^{(m^n)}$ , , and $\tilde A$ , where $\tilde A$ is the adjacency matrix of $\Gamma \mathrel{\square }\cdots \mathrel{\square }\Gamma$ .

We start with the singleton $T^{(m^n)}_{\uparrow }$ , which is the easiest one. Notice first that $T_{\uparrow }^{(m^n)}=T_{\uparrow }^{(m)}\otimes \cdots \otimes T_{\uparrow }^{(m)}$ . Consequently,

\begin{align*} \tilde{u}T_{\uparrow }^{(m^n)} &=\sum _{\sigma \in S_n}T_\sigma (v^{\sigma (1)}\otimes \cdots \otimes v^{\sigma (n)})T_{\uparrow }^{(m^n)}\delta _\sigma \\[5pt] &=\sum _{\sigma \in S_n}T_\sigma (v^{\sigma (1)}T_{\uparrow }^{(m)}\otimes \cdots \otimes v^{\sigma (n)}T_{\uparrow }^{(m)})\delta _\sigma \\[5pt] &=\sum _{\sigma \in S_n}T_\sigma (T_{\uparrow }^{(m)}\otimes \cdots \otimes T_{\uparrow }^{(m)})\delta _\sigma =T_{\uparrow }^{(m^n)}, \end{align*}

where we used the fact that $\sum _{\sigma \in S_n}\delta _\sigma =1_{C(S_n)}$ .

To show the second intertwiner relation, denote by $R$ the natural “disentangling operator” $({\mathbb{C}}^m\otimes{\mathbb{C}}^m)^{\otimes n}\to ({\mathbb{C}}^m)^{\otimes n}\otimes ({\mathbb{C}}^m)^{\otimes n}$ mapping $(x_1\otimes y_1)\otimes \cdots \otimes (x_n\otimes y_n)\mapsto (x_1\otimes \cdots \otimes x_n)\otimes (y_1\otimes \cdots \otimes y_n)$ . Then we can write So,

Finally, we prove that $\tilde u$ commutes with $\tilde A\;:\!=\;\sum _{i=1}^n \textrm{id}\otimes \cdots \otimes \textrm{id}\otimes A\otimes \textrm{id}\otimes \cdots \otimes \textrm{id}$ , where $A$ is the adjacency matrix of $\Gamma$ and in each summand it appears at the $i$ th factor of the tensor product.

\begin{align*} \tilde u\tilde A &=\sum _{\sigma \in S_n}\sum _{i=1}^nT_\sigma (v^{\sigma (1)}\otimes \cdots \otimes v^{\sigma (i)}A\otimes \cdots \otimes v^{\sigma (n)})\\[5pt] &=\sum _{\sigma \in S_n}\sum _{i=1}^nT_\sigma (v^{\sigma (1)}\otimes \cdots \otimes Av^{\sigma (i)}\otimes \cdots \otimes v^{\sigma (n)}) =\tilde A\tilde u \end{align*}

Remark 7.9. The inclusion in Proposition 7.8 may and may not be strict. Hamming graphs $H(n,m)$ provide examples for both. Taking $m=2$ and $n\ge 2$ , we have ${\textrm{Aut}}^+(K_2\mathrel{\square }\cdots \mathrel{\square } K_2)=O_n^{-1}\supsetneq S_2\wr S_n=({\textrm{Aut}}^+K_2)\wr S_n$ . By [25], we have equality for $m=3$ : ${\textrm{Aut}}^+(K_3\mathrel{\square }\cdots \mathrel{\square } K_3)=S_3\wr S_n=({\textrm{Aut}}^+ K_3)\wr S_n$ . We are going to prove the equality for any $m>2$ in the case of Hamming graphs.

Remark 7.10. Let $(x_a)_{a=0}^{m-1}$ be a basis of $C(X)$ such that $x_0=1_{C(X)}$ and denote $x_{ai}=1_{C(X)}\otimes \cdots \otimes 1_{C(X)}\otimes x_a\otimes 1_{C(X)}\otimes \cdots \otimes 1_{C(X)}$ as we already did once. Equation ( 7.1 ) shows that the action from Proposition 7.8 indeed maps $x_{ai}\mapsto \sum _{b,j}x_{bj}\hat u^{bj}_{ai}$ .

7.4. Proof of Theorem 7.1

Recall that $H(n,m)$ is the Cayley graph of $\mathbb Z_m^n$ with respect to the generating set $\{a\varepsilon _i\mid i=1,\ldots,n,\;a=1,\ldots,m-1\}$ . We denote by $\tau _\mu$ , $\mu \in \mathbb Z_m^n$ the irreducible characters of $\mathbb Z_m^n$ defined by $\tau _\mu (\alpha )=\gamma ^{\alpha _1\mu _1+\cdots +\alpha _n\mu _n}$ , where $\gamma$ is some primitive $m$ th root of unity.

As usual, we start with determining the spectrum using Proposition 4.1:

\begin{equation*}\lambda _\mu =\sum _{i=1}^n\sum _{a=1}^{m-1}\gamma ^{\mu _ia}=ml_\mu -n,\end{equation*}

where $l_\mu =\#\{i\mid \mu _i=0\}$ . So, the spectrum contains $n+1$ distinct eigenvalues $n(m-1)$ , $n(m-2),\ldots,$ $-n$ . Denote by $V_0,\ldots,V_{n+1}$ the corresponding eigenspaces $V_i=\textrm{span}\{\tau _\mu \mid l_\mu =n-i\}$ . So, for instance $V_0=\textrm{span}\{\tau _{0,\ldots,0}\}$ , $V_1=\textrm{span}\{\tau _{ai}\mid i=1,\ldots,n,\;a=1,\ldots,m-1\}$ , where we denote $\tau _{ai}\;:\!=\;\tau _i^a=\tau _\mu$ for $\mu =(0,\ldots,0,a,0,\ldots,0)$ —the $a$ being on the $i$ th place. Those must be invariant subspaces of the fundamental representation of ${\textrm{Aut}}^+H(n,m)$ .

In Proposition 7.8, we showed that $S_m^+\wr S_n$ acts on $H(n,m)=K_m\mathrel{\square }\cdots \mathrel{\square } K_m$ via $\tau _{ai}\mapsto \sum _{b,j}\tau _{bj}\otimes \hat u^{bj}_{ai}$ (see Remark 7.10), so ${\textrm{Aut}}^+H(n,m)\supset S_m^+\wr S_n$ . It remains to show the opposite inclusion.

Denote by $u$ the fundamental representation of ${\textrm{Aut}}^+ H(n,m)$ . Denote by $\hat u\;:\!=\;\mathcal{F}^{-1}u\mathcal{F}$ the Fourier transform of $u$ , that is, the matrix $u$ expressed in the basis of $\tau _\mu$ . This matrix decomposes into a direct sum with respect to the invariant subspaces $V_0,V_1,\ldots,V_n$ as $\hat u=\hat u^{(0)}\oplus \hat u^{(1)}\oplus \cdots \oplus \hat u^{(n)}$ . We denote by $\hat u^{ai}_{bj}$ the entries of $\hat u^{(1)}$ . It is enough to show that this matrix $\hat u^{(1)}$ satisfies the relations of the fundamental representation of $\hat S_m^+\wr S_n$ . So let us study its intertwiners.

Recall the formula (4.2) for computing the Fourier transform of intertwiners corresponding to block partitions $[\hat T_{b_{k,l}}]^{\nu _1,\ldots,\nu _l}_{\mu _1,\ldots,\mu _k}=N^{1-k}\delta _{\mu _1+\cdots +\mu _k,\nu _1+\cdots +\nu _l}$ . We start by taking and focus on the entries of corresponding to the invariant subspace $V_1$ and see that . Let us denote the restriction/projection of onto $V_1$ . Let us also denote , so that .

Next, let us study the intertwiner . Its projection onto $V_1$ can be expressed as

Here, we use the following notation

where we use slightly more general notation for the deltas, which is hopefully self-descriptive: For instance, $\delta _{i_1=j_1\neq i_2=j_2}$ equals to one if $i_1=j_1\neq i_2=j_2$ and otherwise it equals to zero. The idea behind the diagrams is that the dashed and dotted blocks indicate the fact that the $i,j$ indices corresponding to the different blocks must not coincide.

We already know that the map is an intertwiner, which implies that also the sum must be an intertwiner. We are going to show that actually each term of this sum is an intertwiner:

First, compute the square of the sum. Obviously, , so it is actually quite easy: . Here, (both blocks are dashed so all of the $a_1,a_2,b_1,b_2$ do have to coincide). That was not very helpful actually, but in a similar manner, we can compute the third power: . Subtracting four times the original sum, we get is an intertwiner unless $m=2$ . But now is just a rotation of , so it must also be an intertwiner. Consequently, also must be an intertwiner and also must be an intertwiner.

Those are all intertwiners we need. Now, we just look at the relations they imply. First, the intertwiner implies the following relation:

(7.2) \begin{equation} \sum _{c=1}^{m-1}\hat u^{a_1i_1}_{cj_1}\hat u^{a_2i_2}_{m-c,j_2}\delta _{j_1j_2}\delta _{b_1+b_2,m}=\sum _{d=1}^{m-1}\hat u^{di_1}_{b_1j_1}\hat u^{m-d,i_2}_{b_2j_2}\delta _{i_1i_2}\delta _{a_1+a_2,m} \end{equation}

So, we can define $w^i_j\;:\!=\;\sum _c\hat u^{ai}_{cj}\hat u^{ai}_{m-c,j}=\sum _d \hat u^{di}_{bj}u^{m-d,i}_{bj}$ (thanks to the relation above, all the sums are equal regardless of the choice of $a,b$ ). Let us also define $\hat v^{ai}_b\;:\!=\;\sum _ju^{ai}_{bj}$ (compare with Remark 7.4(e)).

Now it remains to derive the following relations:

The twisted orthogonality relation corresponding to the intertwiner $\hat T^{(N)}_{\sqcap }$ looks as follows:

\begin{equation*}\sum _{b,j}u^{a_1i_1}_{bj}u^{a_2i_2}_{m-b,j}=\delta _{a_1+a_2,m}\delta _{i_1i_2}\end{equation*}

This, in particular, implies Relation (7.3).

We write down the relation corresponding to :

\begin{equation*}u^{a_1i_1}_{b_2j_2}u^{a_2i_2}_{b_1j_1}\delta _{j_1\neq j_2}=u^{a_2i_2}_{b_1j_1}u^{a_1i_1}_{b_2j_2}\delta _{i_1\neq i_2}\end{equation*}

This implies two things. First,

(7.10) \begin{equation} u^{ai}_{bj}u^{ck}_{dl}=u^{ck}_{dl}u^{ai}_{bj}\qquad \textrm{whenever $i\neq k$ or $j\neq l$.} \end{equation}

Secondly, (and for this we might as well use the relation corresponding to ),

(7.11) \begin{equation} u^{ai}_{bj}u^{ck}_{dj}=0\quad \textrm{for $i\neq k$,}\qquad u^{ai}_{bj}u^{ci}_{dl}=0\quad \textrm{for $j\neq l$.} \end{equation}

The latter remark allows us to check Relation (7.4). Assume $j\neq l$ , then

\begin{equation*}w^i_jw^i_l=\sum _{c,d}\hat u^{ai}_{cj}\hat u^{ai}_{m-c,j}\hat u^{ai}_{dl}\hat u^{ai}_{m-d,l}=0.\end{equation*}

Similarly, we derive that $w^i_jw^k_j=0$ for $i\neq k$ .

Relation (7.10) then implies Relation (7.5), that is the commutativity $w^i_jw^k_l=w^k_lw^i_j$ . Indeed, notice that $w^i_j$ obviously commutes with itself, so we can assume that $i\neq k$ or $j\neq l$ and then it is a direct application of (7.10).

We can also use Relation (7.11) to check (7.9):

\begin{equation*}v^{ai}_bw^i_j=\sum _ku^{ai}_{bk}\sum _cu^{ai}_{cj}u^{ai}_{m-c,j}=u^{ai}_{bj}\sum _{c,l}u^{ai}_{cl}u^{ai}_{m-c,l}=u^{ai}_{bj}.\end{equation*}

Similarly, we can derive $u^{ai}_{bj}=w^i_j v^{ai}_b$ , which proves part of Relation (7.6). To finish the proof of this relation, assume that $j\neq k$ and compute

\begin{equation*}v^{ak}_bw^i_j=\sum _lu^{ak}_{bl}\sum _cu^{ai}_{cj}u^{ai}_{m-c,j}=\sum _lu^{ak}_{bl}\sum _cu^{ai}_{cj}u^{ai}_{m-c,j}=w^i_jv^{ak}_b.\end{equation*}

Relation (7.8) goes the same way.

Finally, Relation (7.7) follows directly from the relation corresponding to , which reads

\begin{equation*}u^{a_1i_1}_{bj}u^{a_2i_2}_{bj}=u^{a_1+a_2,i_1}_{bj}\delta _{b_1b_2}.\end{equation*}