\documentclass[11pt]{amsart}

\usepackage{amssymb,amsmath}
\usepackage{booktabs}
\usepackage[dvipsnames]{xcolor}
\usepackage[colorlinks=true,linkcolor=magenta,citecolor=magenta,urlcolor=magenta]{hyperref}

\textwidth=140mm
\textheight=215mm
\oddsidemargin=10mm
\evensidemargin=10mm
\topmargin=0mm

\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{definition}[theorem]{Definition}

\newcommand{\A}{\mathcal A}
\newcommand{\C}{\mathcal C}
\newcommand{\Z}{\mathbb Z}
\newcommand{\CC}{\mathbb C}
\newcommand{\hA}{\widehat A}
\newcommand{\hu}{\widehat u}
\newcommand{\bchi}{\bar\chi}
\newcommand{\bpsi}{\bar\psi}
\newcommand{\blackarxiv}[1]{{\hypersetup{urlcolor=black}\href{https://arxiv.org/pdf/#1}{arXiv:#1}}}

\begin{document}

\title[Cayley graphs of abelian groups]{Cayley graphs of abelian groups and their quantum symmetries}

\author{Teo Banica}
\author{Claude Fable}

\subjclass[2020]{46L67 (05C25, 05E30)}
\keywords{Quantum permutation group, Cayley graph, Circulant graph, Coherent algebra}

\begin{abstract}
Building on the recent work of Marashdeh on the circulant graphs of prime order, we study the quantum symmetries of the Cayley graphs of the finite abelian groups $A$. Our main result states that if the coherent algebra is the orbital algebra of $A\rtimes E$, with $|E|=k$ and with the non-trivial elements of $E$ having at most $m$ fixed points, then the graph has no quantum symmetry when $|A|\geq k^2m$. We also settle the case of the circulant graphs with $p^n$ vertices.
\end{abstract}

\maketitle

{\hypersetup{linkcolor=magenta}\tableofcontents}

\section*{Introduction}

The quantum permutation group $S_N^+$ was introduced by Wang in \cite{wan}, as the biggest compact quantum group acting on a set with $N$ points. Its algebra of functions $C(S_N^+)$ is the universal $C^*$-algebra generated by the entries of a $N\times N$ magic matrix $u=(u_{ij})$, meaning a matrix whose entries are projections, which sum up to $1$ on each row and each column. Given a finite graph $X$ having $N$ vertices, with adjacency matrix $d$, its quantum automorphism group $G^+(X)$ is constructed in \cite{ba2}, by imposing the relation $du=ud$. We have inclusions as follows, with $G(X)$ being the usual automorphism group of $X$:
$$G(X)\subset G^+(X)\subset S_N^+$$

The graph $X$ is said to have no quantum symmetry when the inclusion on the left is an equality. Deciding whether this is the case or not is a subtle question, going back to \cite{wan}, where it was shown that the graph having $N$ vertices and no edges, whose quantum automorphism group is $S_N^+$ itself, has no quantum symmetry precisely when $N\leq3$.

For the circulant graphs having a prime number $p$ of vertices, an asymptotic result was obtained in \cite{bbc}. Any such graph has a type $k$, which is the order of the group $E\subset\Z_p^*$ leaving invariant the set $S\subset\Z_p$ which describes the edges, and the result is that for $p>6^{\varphi(k)}$ the graph has no quantum symmetry. This was substantially improved by Chassaniol \cite{cha}, and then by Marashdeh \cite{mar}, by using intertwiner space methods. The current threshold, obtained in \cite{mar}, is $p>(k-1)(k-2)+2$. It is also expected, see \cite{mar}, that the only circulant graphs with $p$ vertices having quantum symmetry are the empty and the complete ones.

The question of what happens when the number of vertices is not prime was raised in \cite{bbc}, and again in \cite{mar}, and is open. Our purpose here is to investigate it, by building on the above-mentioned work, in the more general setting of the Cayley graphs of the finite abelian groups $A$. In this setting the Fourier transform over $A$ diagonalizes the adjacency matrix, and so can be applied to the magic matrix of $G^+(X)$. This idea, which is implicit in \cite{bbc}, was axiomatized and used by Gromada in \cite{gro}, for computing the quantum symmetry groups of several remarkable graphs.

In the non-prime case the eigenspaces of the adjacency matrix $d$ no longer suffice, and must be replaced by those of the coherent algebra $\C(X)$ generated by $d$, which commutes with the magic matrix, by a result of Lupini, Man\v{c}inska and Roberson \cite{lmr}. We are led in this way to the notion of type of $X$, which is now a group $E\subset Aut(A)$, such that $\C(X)$ is the orbital algebra of $A\rtimes E$. This is closely related to the notions used in \cite{cha}, \cite{mn}.

Our main result is as follows, with the precise bound that we obtain being in fact $|A|>mk(k-1)-2(k-2)$, which at $m=1$ and $|A|=p$ is the above-mentioned bound from \cite{mar}:

\medskip

\noindent {\bf Theorem A.} {\em Let $X$ be a Cayley graph of a finite abelian group $A$, of type $E$, with $E\subset Aut(A)$ having order $k$, and with the non-trivial elements of $E$ having at most $m$ fixed points. If
$$|A|\geq k^2m$$
then $X$ has no quantum symmetry. Moreover, if $|A|\geq2k^2m$ then $G^+(X)=G(X)=A\rtimes E$.}

\medskip

Here the fixed points are counted inside $A$, so that $m=1$ means that $E$ acts without fixed points on $A-\{0\}$. The proof of the second assertion is based on a simple criterion, involving pairs of characters $\chi,\psi$ of $A$ for which $(\chi\circ a)(\psi\circ b)=(\chi\psi)\circ c$ with $a,b,c\in E$ can only happen when $a=b$. For the groups $\Z_{p^n}$ with $n\geq2$ and $p\geq3$ such pairs exist whenever $p$ does not divide $k$, regardless of the size of $k$. By combining this with the classification of Schur rings over cyclic groups, due to Leung and Man \cite{lm1}, \cite{lm2}, and with the criterion of Schmidt \cite{sch}, we obtain a complete answer in the prime power case:

\medskip

\noindent {\bf Theorem B.} {\em A circulant graph $X=Cay(\Z_N,S)$ with $N=p^n$, $n\geq2$ has quantum symmetry if and only if $S\cap\Z_N^*$ is a union of cosets of the subgroup of order $p$ of $\Z_N$.}

\medskip

In the case $E=\{\pm1\}$ we have $k=2$ and $m=|A|/|2A|$, and the above-mentioned precise bound reads $|2A|\geq3$. A separate study shows that this is sharp, the result being as follows:

\medskip

\noindent {\bf Theorem C.} {\em A Cayley graph $X$ of a finite abelian group $A$, which is of type $E=\{\pm1\}$, has quantum symmetry if and only if $A=\Z_4\times\Z_2^n$, for some $n\geq0$.}

\medskip

For the cyclic groups this is known from \cite{ba2}, \cite{bb}, \cite{lmr}. As a consequence, a vertex-transitive graph having $N\neq4$ vertices, with $G(X)\simeq D_N$, has no quantum symmetry, which answers a question from \cite{bb}, and proves an observation of Schanz \cite{scz}, made for $N\leq13$. Also, almost all circulant graphs have no quantum symmetry.

The first assertion in Theorem A is proved by using a different method, on the vertex side, which applies as well to graphs which are not necessarily Cayley. We call rigid a triangle in which each vertex is determined by its relations with the other two, with respect to the coherent algebra, and we show that the corresponding entries of the magic matrix must commute. This is based on a coherent algebra version of some results of Schmidt \cite{scd}, \cite{sc2}, and leads to:

\medskip

\noindent {\bf Theorem D.} {\em A vertex-transitive graph $X$ whose coherent algebra has valencies $1,2$ has quantum symmetry if and only if $G(X)$ contains two non-trivial automorphisms having disjoint supports. Also, a graph $X$ with $N$ vertices whose coherent algebra is the commutant of a transitive permutation group, with stabilizers of order $k$, and with the non-trivial elements having at most $m$ fixed points, has no quantum symmetry when $N\geq2k^2m$.}

\medskip

An interesting feature of the above results is that the graphs having quantum symmetry are exactly those to which the criterion of Schmidt \cite{sch} applies, namely those having two non-trivial automorphisms with disjoint supports. This is in sharp contrast with the general situation, where van Dobben de Bruyn, Roberson and Schmidt \cite{drs} have shown that there are graphs with trivial automorphism group having quantum symmetry, and that the usual automorphism group never determines the quantum one. The question of finding the families of graphs for which the criterion of Schmidt is an equivalence was raised by Schanz \cite{scz}, and such families are said to satisfy the Schmidt alternative, in the terminology of Meunier \cite{meu}. We conjecture that the circulant graphs satisfy the Schmidt alternative, and we verify this for the graphs having at most $43$ vertices, by computer, and by using the results in \cite{mar}.

We discuss as well the quantum automorphism group $G^*(X)$ constructed by Bichon in \cite{bi1}, which sits between $G(X)$ and $G^+(X)$, and is obtained by assuming that the entries of the magic matrix commute along the edges, recently studied in \cite{hkm}. We show that for the graphs in Theorem C we have $G^*(X)=G(X)$, with one exception, so that their quantum symmetries are not seen by this quantum group. For the circulant graphs having $p^2$ vertices all the possible situations appear, and we are led to an analogue of the above conjecture.

Finally, our results have consequences in connection with the notion of quantum isomorphism of graphs, from \cite{amr}, \cite{lmr}. By using a result of Musto, Reutter and Verdon \cite{mrv}, we show that for the graphs in the second part of Theorem A, with $m=1$, and for the graphs in Theorems B and C having no quantum symmetry, any graph which is quantum isomorphic to $X$ must be isomorphic to $X$.

The paper is organized as follows: in section 1 we discuss the Fourier transform, in sections 2-3 we prove the second part of Theorem A, in sections 4-5 we prove Theorems C and B, in section 6 we prove the first part of Theorem D, in section 7 we discuss the quantum group of Bichon, and section 8 contains the results on the transitive groups, which include the first part of Theorem A, and open questions.

\section{Fourier transform, coherent algebras}

Let us first recall the construction of the quantum automorphism groups. A square matrix $u=(u_{ij})$ over a $C^*$-algebra is called magic when its entries are projections, in the sense that $u_{ij}=u_{ij}^*=u_{ij}^2$, which sum up to $1$ on each row and each column. In particular, any two distinct entries on the same row, or column, are orthogonal.

Following Wang \cite{wan}, we denote by $C(S_N^+)$ the universal $C^*$-algebra generated by the entries of a $N\times N$ magic matrix. This is a Hopf algebra in the sense of Woronowicz, with comultiplication $\Delta(u_{ij})=\sum_ku_{ik}\otimes u_{kj}$, whose abelianization is the algebra $C(S_N)$. Now given a graph $X$ with $N$ vertices, and adjacency matrix $d$, we set, as in \cite{ba2}:
$$C(G^+(X))=C(S_N^+)\Big/\Big<du=ud\Big>$$

The abelianization of this algebra is $C(G(X))$, because a permutation is an automorphism of $X$ precisely when its matrix commutes with $d$. Thus, $X$ has no quantum symmetry precisely when the algebra $C(G^+(X))$ is commutative.

We are interested here in the following graphs. Let $A$ be a finite abelian group, written additively, with $|A|=N$, and let $S\subset A-\{0\}$ be a subset satisfying $S=-S$. The Cayley graph $X=Cay(A,S)$ has vertex set $A$, with edges $x-y$ when $y-x\in S$. Its adjacency matrix $d\in M_N(\CC)$ acts on the functions $f\in C(A)$ by $(df)(x)=\sum_{s\in S}f(x+s)$. When $A=\Z_N$ is cyclic, the graph is called circulant. We denote by $\hA$ the dual group, written multiplicatively. The characters $\chi\in\hA$ form a basis of $C(A)$, and are eigenvectors of $d$, the eigenvalue of $\chi$ being $\sum_{s\in S}\chi(s)$.

Let $\A=C(G^+(X))$ be the above algebra, with magic matrix $u$. As in \cite{bbc}, we use the coaction $\alpha:C(A)\to C(A)\otimes\A$ given by $\alpha(\delta_x)=\sum_y\delta_y\otimes u_{yx}$, which is a morphism of $*$-algebras, due to the fact that $u$ is magic. A matrix $T\in M_N(\CC)$ commutes with $u$ precisely when $\alpha T=(T\otimes id)\alpha$.

\begin{definition}
The Fourier transform of $u$ is the matrix $\hu=(\hu_{\psi\chi})_{\psi,\chi\in\hA}$ given by
$$\alpha(\chi)=\sum_{\psi\in\hA}\psi\otimes\hu_{\psi\chi}$$
for any character $\chi\in\hA$.
\end{definition}

Here are the basic properties of this matrix, that we will use in what follows:

\begin{lemma}
The Fourier transform $\hu$ has the following properties:
\begin{enumerate}
\item $\hu$ is unitary, and its entries generate $\A$.
\item $\hu_{\psi,\chi\chi'}=\sum_{\psi_1\psi_2=\psi}\hu_{\psi_1\chi}\hu_{\psi_2\chi'}$, for any $\psi,\chi,\chi'\in\hA$.
\item $\hu_{\psi\chi}^*=\hu_{\bpsi\bchi}$, for any $\psi,\chi\in\hA$.
\item If $T\in M_N(\CC)$ commutes with $u$, and $T\chi=t_\chi\chi$ for any $\chi\in\hA$, then $\hu_{\psi\chi}=0$ unless $t_\psi=t_\chi$.
\end{enumerate}
\end{lemma}

\begin{proof}
(1) From $\chi=\sum_x\chi(x)\delta_x$ and $\delta_y=\frac{1}{N}\sum_\psi\overline{\psi(y)}\psi$ we get $\hu=F^*uF$, where $F$ is the unitary matrix $F_{x\chi}=\chi(x)/\sqrt{N}$. Since $u$ is unitary, so is $\hu$, and we have $u=F\hu F^*$.

(2,3) These follow from $\alpha(\chi\chi')=\alpha(\chi)\alpha(\chi')$ and $\alpha(\bchi)=\alpha(\chi)^*$, by identifying coefficients.

(4) By applying $\alpha T=(T\otimes id)\alpha$ to $\chi$ we obtain $\sum_\psi\psi\otimes t_\chi\hu_{\psi\chi}=\sum_\psi\psi\otimes t_\psi\hu_{\psi\chi}$, as desired.
\end{proof}

In order to use (4) above, the point is that many matrices commute with $u$. Recall that a coherent algebra is a subalgebra of $M_N(\CC)$ which is stable under the adjoint and under the Schur product, which is the entrywise product of matrices, and contains the identity and the all-1 matrix. Such an algebra has a unique basis formed by $0$-$1$ matrices which sum up to the all-1 matrix, and so corresponds to a partition of the set of pairs of vertices. The basic example is the orbital algebra of a permutation group $G\subset S_N$, which is the commutant $G'$ of the corresponding permutation matrices, the partition being the one into the orbits of $G$ on the pairs of vertices. The coherent algebras of this type are called Schurian.

The intersection of coherent algebras being coherent, we can talk about the coherent algebra $\C(X)$ generated by $d$. This is the algebra computed by the Weisfeiler-Leman algorithm, which starts with the partition of the pairs of vertices into equal pairs, edges, and non-edges, and refines it until the span of the corresponding matrices is closed under multiplication. Since the permutations commuting with $d$ are those commuting with $\C(X)$, we have $\C(X)\subset G(X)'$, and the equality holds when $\C(X)$ is Schurian.

\begin{proposition}
The magic matrix $u$ commutes with all the elements of $\C(X)$.
\end{proposition}

\begin{proof}
This is well-known, see \cite{ba2}, \cite{lmr}. Indeed, the commutant of $u$ is an algebra, which is stable under the adjoint, and contains $d$, the identity and the all-1 matrix. Regarding the Schur product, the multiplication map $m:C(A)\otimes C(A)\to C(A)$ intertwines $u^{\otimes 2}$ and $u$, because $u$ is magic. Thus if $T,T'$ commute with $u$, so does their Schur product, which is $m(T\otimes T')m^*$.
\end{proof}

In our case, let $\tau_x$ be the translation $(\tau_xf)(y)=f(x+y)$, so that $d=\sum_{s\in S}\tau_s$. The algebra spanned by the translations is coherent, so it contains $\C(X)$. Thus $\C(X)$ consists of the matrices $\sum_xc_x\tau_x$ with $c$ being constant on the sets of a certain partition of $A$, called basic sets, with $\{0\}$ being a basic set, and with $S$ being a union of basic sets. Such a partition is called a Schur ring over $A$, and we refer to \cite{ep}, \cite{lm1}, \cite{lm2} for more on this notion.

Consider now a group $E\subset Aut(A)$, acting on $\hA$ by $\chi\to\chi^a=\chi\circ a$, and let $\C_E\subset M_N(\CC)$ be the orbital algebra of the permutation group $A\rtimes E$, with $A$ acting on itself by translations. The basic sets are here the orbits of $E$ on $A$, and so we have:
$$\C_E=\left\{\sum_{x\in A}c_x\tau_x\ \Big|\ c_{a(x)}=c_x,\,\forall a\in E\right\}$$

Since $d=\sum_{s\in S}\tau_s$ commutes with $A\rtimes\{\pm1\}$, we have $\C(X)\subset\C_{\{\pm1\}}$, for any $X$.

\begin{definition}
We say that $X=Cay(A,S)$ is of type $E\subset Aut(A)$ when $\C(X)=\C_E$.
\end{definition}

When $X$ is of type $E$ we have $d\in\C_E$, so the set $S$ is invariant under $E$, and so $A\rtimes E\subset G(X)$. Also, the basic sets being symmetric, we have $-x\in Ex$ for any $x\in A$, and so $-1\in E$ when $A$ is cyclic. In general $E$ is not unique, and does not necessarily contain $-1$, as shown by the complete graph $Cay(\Z_3^3,\Z_3^3-\{0\})$, which is of type $SL_3(\Z_3)$. For $A=\Z_p$ with $p$ prime, any $X$ is of type $E=\{a\in\Z_p^*|aS=S\}$, by \cite{bbc}, and our type is the type from there. In general a type does not always exist, a basic example being the graph $K_{3,3}=Cay(\Z_6,\{1,3,5\})$, whose coherent algebra has dimension $3$, while the algebra $\C_E$ with $E=\Z_6^*=\{\pm1\}$ has dimension $4$. The existence of the type is related to the condition $\C(X)=G(X)'$, studied in \cite{cha}. In the circulant case, where $Aut(\Z_N)=\Z_N^*$, we have the following classical criterion:

\begin{proposition}
If $X=Cay(\Z_N,S)$ satisfies $G(X)=\Z_N\rtimes E$, then $X$ is of type $E$.
\end{proposition}

\begin{proof}
If $\Z_N$ is normal in $G(X)$, the Schur ring corresponding to $\C(X)$ is normal in the sense of Evdokimov and Ponomarenko \cite{ep}, and so is Schurian, by the results there. This means $\C(X)=G(X)'$, and so $\C(X)=\C_E$, as claimed.
\end{proof}

With these notions in hand, we can now formulate our main tool, as follows:

\begin{theorem}
If $X=Cay(A,S)$ is of type $E$, then
$$\hu_{\psi\chi}=0\quad{\rm unless}\quad\psi\in\{\chi^a|a\in E\}$$
for any two characters $\psi,\chi\in\hA$.
\end{theorem}

\begin{proof}
The matrix $T=\sum_xc_x\tau_x$ is diagonal with respect to the characters, with eigenvalues $t_\chi=\sum_xc_x\chi(x)$. The correspondence $c\to t$ being the Fourier transform, the families $c$ which are $E$-invariant correspond to the functions $t:\hA\to\CC$ which are $E$-invariant. Thus, we can find $T\in\C_E$ whose eigenvalue function is the indicator of the orbit of $\chi$, and the result follows from Lemma 1.2 (4) and Proposition 1.3.
\end{proof}

Summarizing, when $X$ is of type $E$ the unitary matrix $\hu$ is block-diagonal, with respect to the partition of $\hA$ into orbits of $E$. More generally, let us say that a coherent algebra $\C\subset M_N(\CC)$ has no quantum symmetry when the universal $C^*$-algebra generated by the entries of a $N\times N$ magic matrix commuting with $\C$ is commutative. Thus $X$ has no quantum symmetry precisely when $\C(X)$ has no quantum symmetry, by Proposition 1.3. The above proof shows that, for any group $E\subset Aut(A)$, not necessarily containing $-1$, a magic matrix $u$ commutes with $\C_E$ precisely when its Fourier transform satisfies $\hu_{\psi\chi}=0$ unless $\psi\in\{\chi^a|a\in E\}$.

In the simplest case, where $E$ is trivial, the matrix $\hu$ is diagonal, and it follows from Lemma 1.2 that its diagonal entries $g_\chi=\hu_{\chi\chi}$ are unitaries satisfying $g_\chi g_{\chi'}=g_{\chi\chi'}$. Thus the algebra $A'$ spanned by the translations has no quantum symmetry, and we recover a particular case of the result in \cite{mn}, stating that the Cayley graphs of a group $A$ which satisfy $\C(X)=A'$ have no quantum symmetry. Our aim in what follows will be that of extending this to the case where $E$ is small, compared to $A$.

\section{Linked characters, the criterion}

In this section we assume that $X=Cay(A,S)$ is of type $E$, and we set $k=|E|$. We say that a character $\chi\in\hA$ is regular when the characters $\chi^a$ with $a\in E$ are distinct. For such a character we set $r^\chi_a=\hu_{\chi^a\chi}$, so that by Theorem 1.6 we have:
$$\alpha(\chi)=\sum_{a\in E}\chi^a\otimes r^\chi_a$$

\begin{lemma}
Let $\chi\in\hA$ be regular. Then $(r^\chi_a)^*=r^{\bchi}_a$ for any $a\in E$, and the elements
$$Q^\chi_a=(r^\chi_a)^*r^\chi_a$$
sum up to $1$. Also, we have $r^\chi_a(r^\chi_a)^*=Q^{\bchi}_a$.
\end{lemma}

\begin{proof}
The first assertion follows from Lemma 1.2 (3). The second assertion follows from the unitarity of $\hu$, because the entries of the $\chi$-th column of $\hu$ are the elements $r^\chi_a$, and zeroes. The third assertion follows from the first one.
\end{proof}

In the classical case, where $\A=C(G)$ with $G=A\rtimes E$, the element $r^\chi_a$ is a function of modulus $1$ on the set of elements of $G$ whose component in $E$ is $a^{-1}$, and vanishes elsewhere. Thus, what we would like to prove is that the elements $Q^\chi_a$ are projections, which do not depend on $\chi$. The idea will be that of finding pairs of characters $\chi,\psi$ for which the multiplicativity of $\alpha$ can be fully exploited. These are as follows:

\begin{definition}
Two characters $\chi,\psi\in\hA$ are called linked when $\chi,\psi,\chi\psi$ are regular, and
$$\chi^a\psi^b=(\chi\psi)^c\implies a=b$$
for any $a,b,c\in E$.
\end{definition}

Observe that this relation is symmetric, and that a character can be linked to itself. As a basic example, let $A=\Z_p$ with $p\geq5$ prime, and $E=\{\pm1\}$. Any character $\chi\neq1$ is then linked to itself, because $\chi^a\chi^b=\chi^{2c}$ with $a\neq b$ would give $\chi^{2c}=1$. The point with this notion comes from the following result:

\begin{lemma}
If $\chi,\psi$ are linked then $r^{\chi\psi}_a=r^\chi_ar^\psi_a=r^\psi_ar^\chi_a$ for any $a\in E$, and
$$Q^\chi_a=Q^\psi_a=Q^{\bchi}_a=Q^{\bpsi}_a$$
with these elements being pairwise orthogonal projections. Thus $r^\chi_a,r^\psi_a$ are partial isometries, whose initial and final projections are both equal to $Q^\chi_a$.
\end{lemma}

\begin{proof}
By multiplying the formulae of $\alpha(\chi),\alpha(\psi)$ we obtain:
$$\sum_{c\in E}(\chi\psi)^c\otimes r^{\chi\psi}_c=\sum_{a,b\in E}\chi^a\psi^b\otimes r^\chi_ar^\psi_b$$

The characters on the left being distinct, the coefficient of $(\chi\psi)^c$ on the right is the sum of the elements $r^\chi_ar^\psi_b$ with $\chi^a\psi^b=(\chi\psi)^c$. But this latter condition implies $a=b$, and then $a=c$, by regularity. Thus $r^{\chi\psi}_c=r^\chi_cr^\psi_c$, and by symmetry, $r^{\chi\psi}_c=r^\psi_cr^\chi_c$ too.

By applying now Lemma 2.1 to the characters $\chi\psi$ and $\psi$, we obtain:
$$\sum_{c\in E}(r^\psi_c)^*Q^\chi_cr^\psi_c=1=\sum_{c\in E}(r^\psi_c)^*r^\psi_c$$

Since $0\leq Q^\chi_c\leq1$, the elements $(r^\psi_c)^*(1-Q^\chi_c)r^\psi_c$ are positive, and their sum is $0$. Thus they all vanish, and so $Q^\chi_cr^\psi_c=r^\psi_c$. With $R_c=r^\psi_c(r^\psi_c)^*=Q^{\bpsi}_c$ we obtain $Q^\chi_cR_c=R_c=R_cQ^\chi_c$. Thus the element $Q^\chi_c-R_c=Q^\chi_c(1-R_c)$ is positive, being a product of commuting positive elements. But both families sum up to $1$, so we must have $Q^\chi_c=R_c$ for any $c$, and then $Q^\chi_cR_c=R_c$ shows that $Q^\chi_c$ is a projection. Summarizing, we have proved that $Q^\chi_c=Q^{\bpsi}_c$ is a projection, with $Q^\chi_cr^\psi_c=r^\psi_c$, and by symmetry, $Q^\psi_c=Q^{\bchi}_c$ is a projection too, with $Q^\psi_cr^\chi_c=r^\chi_c$.

Finally, let us compute $T=(r^{\chi\psi}_c)^*r^{\chi\psi}_c$. By using $r^{\chi\psi}_c=r^\chi_cr^\psi_c$ we obtain $T=(r^\psi_c)^*Q^\chi_cr^\psi_c=Q^\psi_c$, and by using $r^{\chi\psi}_c=r^\psi_cr^\chi_c$ we obtain $T=(r^\chi_c)^*Q^\psi_cr^\chi_c=Q^\chi_c$. Thus $Q^\chi_c=Q^\psi_c$, and we are done, the orthogonality coming from the fact that our projections sum up to $1$.
\end{proof}

We can now formulate our criterion for the lack of quantum symmetry:

\begin{theorem}
Let $X=Cay(A,S)$ be of type $E$. Assume that there is a set of characters $F\subset\hA$ which generates $\hA$, such that any element of $F$ is linked to an element of $F$, and such that $F$ is connected with respect to the linking relation. Then $X$ has no quantum symmetry, and $G^+(X)=G(X)=A\rtimes E$.
\end{theorem}

\begin{proof}
By Lemma 2.3 and by connectedness the projections $P_a=Q^\chi_a$ do not depend on the choice of $\chi\in F\cup\bar{F}$, and each $r^\chi_a$ with $\chi\in F\cup\bar{F}$ is a partial isometry, having $P_a$ as initial and final projection. Since the projections $P_a$ are pairwise orthogonal, we obtain:
$$r^\chi_ar^{\chi'}_b=0\quad,\quad\forall\chi,\chi'\in F\cup\bar{F},\ \forall a\neq b$$

By using this, we obtain by recurrence that for any $\chi_1,\ldots,\chi_s\in F\cup\bar{F}$ we have:
$$\alpha(\chi_1\ldots\chi_s)=\sum_{a\in E}(\chi_1\ldots\chi_s)^a\otimes r^{\chi_1}_a\ldots r^{\chi_s}_a$$

Let us prove now that the elements $r^\chi_a$ with $\chi\in F\cup\bar{F}$ commute. By the above we just have to prove that $r^\chi_a,r^{\chi'}_a$ commute. But, since $\chi\chi'=\chi'\chi$, the above formula gives:
$$\sum_{a\in E}(\chi\chi')^a\otimes r^\chi_ar^{\chi'}_a=\sum_{a\in E}(\chi\chi')^a\otimes r^{\chi'}_ar^\chi_a$$

By multiplying this equality at left by $1\otimes P_b$, and by using $P_br^\chi_a=\delta_{ab}r^\chi_a$, all the terms with $a\neq b$ vanish, and we obtain $r^\chi_br^{\chi'}_b=r^{\chi'}_br^\chi_b$, as desired.

Summarizing, the elements $r^\chi_a$ with $\chi\in F\cup\bar{F}$ form a commuting family, which is stable under the adjoint. Since $F$ generates $\hA$, the above formula of $\alpha(\chi_1\ldots\chi_s)$ shows that all the entries of $\hu$ belong to the algebra generated by this family. Thus $\A$ is commutative, by Lemma 1.2 (1), and so $X$ has no quantum symmetry.

Finally, let $g\in G(X)$, and recall that $\alpha(f)(x,g)=f(g^{-1}(x))$. Since the projections $P_a$ sum up to $1$, there is exactly one $a\in E$ with $P_a(g)=1$, and we obtain $\chi(g^{-1}(x))=\chi(a(x))c_\chi$ for any $\chi\in\hA$, with $c_\chi\in\CC$. Thus $g^{-1}(x)-a(x)$ does not depend on $x$, so $g\in A\rtimes E$.
\end{proof}

\section{Asymptotic results, cyclic groups}

In order to apply Theorem 2.4, we need to count the pairs of characters which are not linked. Let $X=Cay(A,S)$ be of type $E$, with $|E|=k\geq2$, and consider the following number, which is the maximal number of fixed points of the non-trivial elements of $E$:
$$m=\max_{a\in E-\{1\}}\big|\{x\in A\,|\,a(x)=x\}\big|$$

The simplest case is $m=1$, which means that $E$ acts without fixed points, in the sense that $a(x)=x$ with $a\in E$, $x\in A$ implies $a=1$ or $x=0$. This is the same as saying that $A\rtimes E$ is a Frobenius group, or that all the characters $\chi\neq1$ are regular. In general, we have:

\begin{lemma}
The number of characters which are not regular is at most $(k-1)(m-1)+1$. Also, if $\chi\in\hA$ is regular, the number of characters $\psi\in\hA$ which are not linked to $\chi$ is at most
$$mk(k-1)-2(k-2)$$
which at $m=1$ is the number $(k-1)(k-2)+2$.
\end{lemma}

\begin{proof}
Let $a\in E$ with $a\neq1$. A character $\psi$ satisfies $\psi^a=\psi$ precisely when it is trivial on the image of the endomorphism $a-1$ of $A$, so the number of such characters is:
$$\frac{|A|}{|Im(a-1)|}=|\ker(a-1)|\leq m$$

Now since a character is not regular precisely when it is fixed by some $a\neq1$, and since the trivial character is fixed by any $a$, we obtain the first assertion.

Assume now that $\psi$ is not linked to $\chi$. The number of characters $\psi$ such that $\psi$ or $\chi\psi$ is not regular is at most $2(k-1)(m-1)+2$, by the above. In the remaining case we must have $\chi^a\psi^b=(\chi\psi)^c$ for some $a,b,c\in E$ with $a\neq b$. By regularity $a,b,c$ must be distinct, and our equation reads, inside the abelian group formed by the maps $A\to\mathbb T$:
$$\psi\circ(b-c)=\chi\circ(c-a)$$

The solutions $\psi$ of this equation, if any, form a coset of the group of characters which are trivial on the image of $b-c$. By the above, the order of this group is:
$$|\ker(b-c)|=|\ker(c^{-1}b-1)|\leq m$$

Moreover, our equation is invariant if we replace $(a,b,c)$ by $(ae,be,ce)$, with $e\in E$. Since there are $k(k-1)(k-2)$ triples of distinct elements, the number of characters $\psi$ which appear in this way is at most $(k-1)(k-2)m$. We conclude that the number of characters which are not linked to $\chi$ is at most $(k-1)(k-2)m+2(k-1)(m-1)+2$, which is the number in the statement.
\end{proof}

We can now formulate our main result, as follows:

\begin{theorem}
Let $X=Cay(A,S)$ be of type $E$, with $|E|=k\geq2$, and with the non-trivial elements of $E$ having at most $m$ fixed points. If $|A|\geq2k^2m$ then $X$ has no quantum symmetry, and
$$G^+(X)=G(X)=A\rtimes E$$
with $A$ acting by translations.
\end{theorem}

\begin{proof}
Let $F\subset\hA$ be the set of regular characters. Given $\chi,\chi'\in F$, the number of characters which are not linked to $\chi$, or not linked to $\chi'$, is at most, by Lemma 3.1:
$$2mk(k-1)-4(k-2)<2k^2m\leq|A|$$

Thus $\chi,\chi'$ are linked to a common character, which belongs to $F$. Also by Lemma 3.1, the complement of $F$ has at most $(k-1)(m-1)+1<k^2m$ elements, so $F$ contains more than half of the elements of $\hA$, and so generates $\hA$. Thus Theorem 2.4 applies.
\end{proof}

We will see in section 8 that, as far as the lack of quantum symmetry is concerned, the above bound can be improved to $|A|>mk(k-1)-2(k-2)$, by using a different method. At $m=1$ the above result applies to the Frobenius groups $A\rtimes E$ with $|A|\geq2k^2$. In general, the examples that we will meet in what follows, coming from the groups $A=\Z_4\times\Z_2^n$ with $E=\{\pm1\}$, and from the groups $A=\Z_{p^n}$, show that some assumption on the size of $m$ is needed. Indeed, in these examples we have $m=|A|/2$ and $m=|A|/p$, with $p$ dividing $k$, and the corresponding graphs have quantum symmetry, regardless of the size of $A$.

In the cyclic case we write $\xi^x(y)=w^{xy}$ with $w=e^{2\pi i/N}$, for $x\in\Z_N$. A group $E\subset\Z_N^*$ acts on these characters by $\xi^x\to\xi^{ax}$, and the characters $\xi^y,\xi^z$ are linked when $y,z,y+z$ have trivial stabilizers in $E$, and when $ay+bz=c(y+z)$ with $a,b,c\in E$ implies $a=b$. Also, the number of fixed points of $a\in E$ is the greatest common divisor of $a-1$ and $N$.

As a first result, in the composite case, we have a reduction to smaller groups:

\begin{proposition}
Let $N=N_1N_2$ with $N_1,N_2$ coprime, so that $\Z_N=\Z_{N_1}\times\Z_{N_2}$, let $X=Cay(\Z_N,S)$ be of type $E$, and consider the following groups:
$$K_1=\left\{a\in\Z_{N_1}^*\big|(a,1)\in E\right\}\quad,\quad K_2=\left\{b\in\Z_{N_2}^*\big|(1,b)\in E\right\}$$
Then $X$ has quantum symmetry if and only if one of the coherent algebras $\C_{K_1},\C_{K_2}$ has quantum symmetry. In particular, if the maps $E\to\Z_{N_1}^*$ and $E\to\Z_{N_2}^*$ are both injective, then $X$ has no quantum symmetry.
\end{proposition}

\begin{proof}
We write the vertices as pairs $(x,x')$, and the characters as products $\chi_1\chi_2$, with $\chi_i$ being a character of $\Z_{N_i}$. Since the subgroups $\Z_{N_1},\Z_{N_2}\subset\Z_N$ are invariant under $E$, the matrices $1\otimes J$ and $J\otimes1$, with $J$ being the all-$1$ matrix, belong to $\C_E$. By using the fact that $u$ commutes with these matrices, we obtain, in a standard way, that the elements $v_{xy}=\sum_{y'}u_{(x,x')(y,y')}$ and $w_{x'y'}=\sum_yu_{(x,x')(y,y')}$ do not depend on $x'$ and $x$, and form magic matrices $v,w$. Since the entries on each row of $u$ are pairwise orthogonal, we have:
$$u_{(x,x')(y,y')}=v_{xy}w_{x'y'}=w_{x'y'}v_{xy}$$

Thus $\A$ is generated by the algebras $\A_1,\A_2$ generated by the entries of $v,w$, and these algebras commute. In terms of the Fourier transforms $\widehat{v},\widehat{w}$ of the matrices $v,w$, we have $\hu_{\psi_1\psi_2,\chi_1\chi_2}=\widehat{v}_{\psi_1\chi_1}\widehat{w}_{\psi_2\chi_2}$, and Theorem 1.6 gives:
$$\widehat{v}_{\psi_1\chi_1}\widehat{w}_{\psi_2\chi_2}=0\quad{\rm unless}\quad(\psi_1,\psi_2)=(\chi_1^a,\chi_2^b)\ {\rm with}\ (a,b)\in E$$

Let $E_i\subset\Z_{N_i}^*$ be the image of $E$. If $(a,b)$ and $(a',b)$ belong to $E$ then $a'a^{-1}\in K_1$, and similarly for the second component. Thus the cosets of $K_1$ in $E_1$ correspond to the cosets of $K_2$ in $E_2$, with $(a,b)\in E$ precisely when $a\in q$ and $b\in q'$, for a pair of corresponding cosets $(q,q')$. Let $\xi_i$ be a generator of the group of characters of $\Z_{N_i}$, so that the characters $\xi_i^a$ with $a\in\Z_{N_i}^*$ are distinct, and for any pair $(q,q')$ as above, set:
$$R_q=\sum_{a\in q}\widehat{v}_{\xi_1^a\xi_1}^{\,*}\widehat{v}_{\xi_1^a\xi_1}\quad,\quad T_q=\sum_{b\in q'}\widehat{w}_{\xi_2^b\xi_2}\widehat{w}_{\xi_2^b\xi_2}^{\,*}$$

By unitarity, as in Lemma 2.1, these elements sum up to $1$. Also, by the above formula we have $\widehat{v}_{\xi_1^a\xi_1}\widehat{w}_{\xi_2^b\xi_2}=0$ when $(a,b)\notin E$, so $R_qT_p=0$ for $q\neq p$, and so $R_q=R_qT_q=T_q$. We conclude that $P_q=R_q=T_q$ belongs to $\A_1\cap\A_2$, so is central, and that the elements $P_q$ are pairwise orthogonal projections, summing up to $1$.

We claim now that $\widehat{v}_{\psi_1\chi_1}P_q=0$, unless $\psi_1=\chi_1^a$ with $a\in q$. Indeed, if $\widehat{v}_{\psi_1\chi_1}\widehat{w}_{\xi_2^b\xi_2}\neq0$ with $b\in q'$, then by the above formula we have $\psi_1=\chi_1^a$ with $(a,b)\in E$, so $a\in q$, and the claim follows by multiplying by $\widehat{w}_{\xi_2^b\xi_2}^{\,*}$, and then by summing over $b\in q'$.

Now fix $q$, and an element $a\in q$. By the above, the matrix $\widehat{v}'_{\psi_1\chi_1}=\widehat{v}_{\psi_1^a\chi_1}P_q$ vanishes unless $\psi_1\in\{\chi_1^c|c\in K_1\}$. But this is the Fourier transform of the matrix $v'$ obtained from $vP_q$ by permuting the rows, via the multiplication by $a$, which is magic, over the algebra $P_q\A$. Thus $v'$ commutes with $\C_{K_1}$, as explained at the end of section 1. If $\C_{K_1}$ has no quantum symmetry, the entries of $v'$ commute, for any $q$, and so $\A_1$ is commutative. The same holds for $\A_2$, and we conclude that if $\C_{K_1},\C_{K_2}$ have no quantum symmetry, then $\A$ is commutative.

Conversely, let $v'$ be a magic matrix commuting with $\C_{K_1}$, whose entries do not commute. Then $u=v'\otimes1$ is magic, and $\hu_{\psi_1\psi_2,\chi_1\chi_2}=\widehat{v}'_{\psi_1\chi_1}\delta_{\psi_2\chi_2}$ vanishes unless $\psi_1=\chi_1^c$ with $c\in K_1$ and $\psi_2=\chi_2$. Since $(c,1)\in E$ for any $c\in K_1$, the matrix $u$ commutes with $\C_E=\C(X)$, and so $X$ has quantum symmetry. Finally, the last assertion holds because when $K_1,K_2$ are trivial, the algebras $\C_{K_1},\C_{K_2}$ are spanned by translations, and so have no quantum symmetry.
\end{proof}

As an example, the graph $Cay(\Z_{65},\{\pm1,\pm8\})$ is of type $E=\{\pm1,\pm8\}$, as one can check by computer, and so has no quantum symmetry. We will see in section 8 some examples where the groups $K_1,K_2$ are not trivial. Observe that these groups do not necessarily contain $-1$, so the algebras $\C_{K_1},\C_{K_2}$ do not necessarily come from graphs. In general now, in the cyclic case, we have the following improvement of Theorem 3.2:

\begin{theorem}
Let $X=Cay(\Z_N,S)$ be of type $E$, with $|E|=k\geq2$, and let $m$ be the biggest of the numbers $\gcd(a-1,N)$, with $a\neq1$ in $E$. If
$$N>mk(k-1)-2(k-2)$$
then $X$ has no quantum symmetry, and $G^+(X)=G(X)=\Z_N\rtimes E$.
\end{theorem}

\begin{proof}
The character $\xi$ is regular, because $1\in\Z_N$ has trivial stabilizer in $E$. By Lemma 3.1 and by our assumption there is a character $\psi$, which can be $\xi$ itself, which is linked to $\xi$. Thus Theorem 2.4 applies, with $F=\{\xi,\psi\}$.
\end{proof}

As an example with $m>1$, the graph $Cay(\Z_{93},\{\pm1,\pm25,\pm26\})$ is of type $E=\{\pm1,\pm25,\pm26\}$, as one can check by computer. Here $k=6$ and $m=3$, the bound in Theorem 3.4 is $N>82$, and so this graph has no quantum symmetry.

At $m=1$, which means that $a-1\in\Z_N^*$ for any $a\neq1$ in $E$, the bound is $N>(k-1)(k-2)+2$. In the case where $N=p$ is prime, where any $X$ has a type, and where we have $m=1$, this result was obtained by Marashdeh in \cite{mar}, building on the work of Chassaniol \cite{cha}, and improves the main result in \cite{bbc}. In fact, the existence of a character linked to $\xi$ can be shown to be equivalent to the singleton condition from \cite{cha}, used in \cite{mar}, so at $N=p$ we obtain here a new proof of this result, via the Fourier transform. Let us mention too that the results in \cite{cha}, \cite{mar} at $N=p$ go beyond the above bound, with all the types $k\leq10$, and all the primes $p\leq250$, being covered there.

\section{Dihedral type, generic graphs}

In this section we assume that $X=Cay(A,S)$ is of type $E=\{\pm1\}$, and we call such a graph of dihedral type. Since we always have $\C(X)\subset\C_{\{\pm1\}}$, this is the case where the coherent algebra is the biggest possible one. The fixed points of $-1$ being the elements satisfying $2x=0$, the number $m$ from the previous section is here $m=|A|/|2A|$, so Theorem 3.2 applies when $|2A|\geq8$. In order to obtain a complete result, we must deal with the characters satisfying $\chi^2=1$, which are not regular. Consider the set $\hA'=\{\chi\in\hA|\chi^2\neq1\}$. With $r_\chi=r^\chi_1$ and $s_\chi=r^\chi_{-1}$, in the notations of section 2, for $\chi\in\hA'$ we have:
$$\alpha(\chi)=\chi\otimes r_\chi+\bchi\otimes s_\chi$$

As for the characters satisfying $\chi^2=1$, here we have $\alpha(\chi)=\chi\otimes g_\chi$, with $g_\chi=\hu_{\chi\chi}$.

\begin{lemma}
For $\chi\in\hA'$ the elements $r_\chi,s_\chi$ are normal, and $r_\chi r_\chi^*+s_\chi s_\chi^*=1$. If $\chi,\chi'\in\hA'$ satisfy $\chi^2\neq\chi'^2$ then $r_\chi s_{\chi'}=s_\chi r_{\chi'}=0$, and $P_\chi=r_\chi r_\chi^*$ is a projection, equal to $P_{\chi'}$.
\end{lemma}

\begin{proof}
The $\chi$-th column of $\hu$ has entries $r_\chi,s_\chi$, and the $\chi$-th row has entries $r_\chi,s_\chi^*$, by Lemma 2.1. Thus we have $r_\chi^*r_\chi+s_\chi^*s_\chi=1$ and $r_\chi r_\chi^*+s_\chi^*s_\chi=1$, so $r_\chi$ is normal. Now the first formula, written for $\bchi$, reads $r_\chi r_\chi^*+s_\chi s_\chi^*=1$, so $s_\chi$ is normal too.

Regarding the second assertion, by multiplying $\alpha(\chi),\alpha(\chi')$ we obtain:
$$\alpha(\chi\chi')=\chi\chi'\otimes r_\chi r_{\chi'}+\chi\bchi'\otimes r_\chi s_{\chi'}+\bchi\chi'\otimes s_\chi r_{\chi'}+\bchi\bchi'\otimes s_\chi s_{\chi'}$$

The left term is supported by $\chi\chi'$ and $\bchi\bchi'$. Since $\chi^2,\chi'^2\neq1$, the character $\chi\bchi'$ is different from these, and since $\chi^2\neq\chi'^2$, it is different from $\bchi\chi'$ too. Thus $r_\chi s_{\chi'}=0$, and similarly $s_\chi r_{\chi'}=0$. By multiplying by $r_\chi^*$ at left and by $s_{\chi'}^*$ at right we obtain $P_\chi(1-P_{\chi'})=0$, and so $P_\chi=P_\chi P_{\chi'}$. By symmetry we have as well $P_{\chi'}=P_{\chi'}P_\chi$, and by taking adjoints in the first formula we conclude that $P_\chi=P_{\chi'}$, and that this element is a projection.
\end{proof}

The above lemma is useful when $\hA'$ contains characters having different squares. Since $|\{\chi^2|\chi\in\hA\}|=|2A|$, this happens when $|2A|\geq3$. As for the remaining groups, these are $A=\Z_2^n$, where $|2A|=1$, and $A=\Z_4\times\Z_2^n$, where $|2A|=2$. Regarding these latter groups, where the method fails, we have the following result:

\begin{proposition}
Any Cayley graph of $A=\Z_4\times\Z_2^n$ has quantum symmetry.
\end{proposition}

\begin{proof}
We use the criterion of Schmidt \cite{sch}, stating that if $G(X)$ contains 2 non-trivial automorphisms $\sigma,\tau$ having disjoint supports, then $X$ has quantum symmetry. Here the support of a permutation is the set of points which are not fixed. Let us recall the proof. Given 2 non-commuting projections $p,q$, the following matrices are magic, and commute with $d$, with $P_\sigma,P_\tau$ being the permutation matrices of $\sigma,\tau$:
$$v=P_\sigma\otimes p+1\otimes(1-p)\quad,\quad w=P_\tau\otimes q+1\otimes(1-q)$$

The matrix $vw$ is then unitary, and commutes with $d$. Since the supports are disjoint, the columns of $vw$ indexed by the support of $\tau$ are those of $w$, and the other columns are those of $v$. Thus $vw$ is a unitary whose entries are projections, hence is magic, and since its entries include $p,q$, the algebra $\A$ is not commutative.

In our case, let $c$ be the non-zero element of $2A$, and set $\sigma(x)=-x$ and $\tau(x)=c-x$. These are automorphisms of $X$, because $S=-S$. The support of $\sigma$ is $\{x|2x=c\}$, and the support of $\tau$ is $\{x|2x=0\}$, so these supports are disjoint, and non-empty.
\end{proof}

We can now formulate our main result about the graphs of dihedral type:

\begin{theorem}
Let $X=Cay(A,S)$ be of dihedral type.
\begin{enumerate}
\item If $A\neq\Z_4\times\Z_2^n$ then $X$ has no quantum symmetry, and $G^+(X)=G(X)$ is the group generated by the translations of $A$, and by the inversion $x\to-x$.
\item If $A=\Z_4\times\Z_2^n$, then $X$ has quantum symmetry.
\end{enumerate}
\end{theorem}

\begin{proof}
(1) Assume first $A=\Z_2^n$. Then $\alpha(\chi)=\chi\otimes g_\chi$ for any $\chi$, and from Lemma 1.2 (2) we get $g_\chi g_{\chi'}=g_{\chi\chi'}=g_{\chi'}g_\chi$. Thus $\A$ is commutative, by Lemma 1.2 (1).

Assume now $|2A|\geq3$. Any 2 characters in $\hA'$ either have different squares, or have the same square, different from the square of a third character in $\hA'$. Thus Lemma 4.1 shows that $P_\chi=P$ is a projection, not depending on $\chi\in\hA'$. Since $r_\chi$ is normal with $r_\chi r_\chi^*=P$, we have $r_\chi=Pr_\chi=r_\chi P$, and in the same way, $s_\chi=(1-P)s_\chi=s_\chi(1-P)$. In particular we have $r_\chi s_{\chi'}=s_{\chi'}r_\chi=0$, for any $\chi,\chi'\in\hA'$.

Let us prove now that the elements $r_\chi$ commute. With $\rho=\chi\chi'$, the formula of $\alpha(\chi\chi')$ in the proof of Lemma 4.1 shows that the coefficient of $\rho$ in $\alpha(\rho)$ is $r_\chi r_{\chi'}+\varepsilon s_\chi s_{\chi'}$, with $\varepsilon=1$ if $\rho^2=1$, and $\varepsilon=0$ otherwise. But $A$ being abelian, we have $\chi\chi'=\chi'\chi$, so:
$$r_\chi r_{\chi'}+\varepsilon s_\chi s_{\chi'}=r_{\chi'}r_\chi+\varepsilon s_{\chi'}s_\chi$$

By multiplying by $P$ we obtain $r_\chi r_{\chi'}=r_{\chi'}r_\chi$. Similarly, by using the coefficient of $\bar\rho$ and then by multiplying by $1-P$, we obtain $s_\chi s_{\chi'}=s_{\chi'}s_\chi$. Thus the elements $r_\chi,s_\chi$ with $\chi\in\hA'$ form a commuting family, which is stable under the adjoint.

Finally, let $\chi\neq1$ with $\chi^2=1$. We can write $\chi=\chi_1\chi_2$ with $\chi_1,\chi_2\in\hA'$, and since $\chi_1\bchi_2\neq\chi$, the coefficient of $\chi$ in $\alpha(\chi_1)\alpha(\chi_2)$ gives $g_\chi=r_{\chi_1}r_{\chi_2}+s_{\chi_1}s_{\chi_2}$. Thus all the entries of $\hu$ belong to a commutative algebra, and so $\A$ is commutative. The assertion regarding $G(X)$ follows as in the proof of Theorem 2.4, by using the projection $P$.

(2) This follows from Proposition 4.2.
\end{proof}

In the cyclic case $A=\Z_N$ the above result is known, and goes back to \cite{ba2}, \cite{bb}, where it was proved under the assumption that $d$ has $[N/2]+1$ distinct eigenvalues, which is the maximal possible number, and which implies that $X$ is of dihedral type, and then to \cite{lmr}, where the coherent algebra formulation was found. Here is a consequence, which answers a question from \cite{bb}, and which was observed by Schanz in \cite{scz} to hold for the vertex-transitive graphs having $N\leq13$ vertices:

\begin{proposition}
A vertex-transitive graph $X$ having $N\neq4$ vertices, and satisfying
$$G(X)\simeq D_N$$
has no quantum symmetry.
\end{proposition}

\begin{proof}
We have $N\geq3$, and the stabilizers of the vertices are subgroups of order $2$ of $D_N=\Z_N\rtimes\Z_2$, which are conjugate, and intersect trivially. Thus these subgroups are not central, so they are generated by reflections, and so $\Z_N$ acts without fixed points. We conclude that $X$ is a circulant graph, with $G(X)=\Z_N\rtimes\{\pm1\}$. Thus by Proposition 1.5 our graph is of dihedral type, and Theorem 4.3 applies.
\end{proof}

In relation with this, a question raised in \cite{scz} is that of finding families of graphs, and groups $G$, such that any graph $X$ in the family satisfying $G(X)\simeq G$ has no quantum symmetry. Thus, the above result provides a first answer to this question.

Regarding now the genericity of the dihedral type, the situation is as follows. For the Cayley graphs of arbitrary finite groups, the analogous problem, with the coherent algebra being the commutant of the group itself, was investigated in \cite{mn}, where it was conjectured that this situation is generic. For the abelian groups, we know from Dobson, Spiga and Verret \cite{dsv} that almost all the Cayley graphs of $A$ have the smallest possible automorphism group, namely $G(X)=A\rtimes\{\pm1\}$. In the cyclic case this implies that $X$ is of dihedral type, by Proposition 1.5. In general, however, this is not clear, because $\C(X)$ might be smaller than $G(X)'$.

Here is some numerical data, obtained by using the Weisfeiler-Leman algorithm, with the percentage of graphs of dihedral type, among the graphs $Cay(A,S)$, with $S=-S$ being random, distinct from $\emptyset$ and $A-\{0\}$, with $40$ to $300$ samples for each group, except for $\Z_{12},\Z_{16},\Z_3^2$, where all such sets $S$ were used:
\begin{center}
\begin{tabular}{lr@{\qquad\qquad}lr@{\qquad\qquad}lr}
\toprule
$A$&\%&$A$&\%&$A$&\%\\
\midrule
$\Z_{12}$&52&$\Z_3^2$&0&$\Z_2^4$&0\\
$\Z_{16}$&76&$\Z_3^3$&0&$\Z_2^5$&10\\
$\Z_{24}$&73&$\Z_3^4$&85&$\Z_2^6$&96\\
$\Z_{36}$&91&$\Z_5^2$&23&$\Z_2^7$&100\\
$\Z_{60}$&99&$\Z_5^3$&100&$\Z_4\times\Z_2^2$&0\\
$\Z_{81}$&100&$\Z_7^2$&94&$\Z_4\times\Z_2^3$&14\\
$\Z_{100}$&100&$\Z_9^2$&100&$\Z_4\times\Z_2^4$&83\\
$\Z_{128}$&100&$\Z_{11}^2$&100&$\Z_4^3$&74\\
\bottomrule
\end{tabular}
\end{center}

This suggests the following statement, which would imply, via Theorem 4.3, that almost all the Cayley graphs of $A$ have no quantum symmetry, unless $A=\Z_4\times\Z_2^n$:

\begin{conjecture}
For any sequence of finite abelian groups $A$ with $|A|\to\infty$, the proportion of graphs of dihedral type, among the Cayley graphs of $A$, tends to $1$.
\end{conjecture}

In the cyclic case this conjecture holds, because by a result of Verbitsky and Zhukovskii \cite{vz}, with probability $1-N^{-1/2+o(1)}$ the matrix $d$ has $[N/2]+1$ distinct eigenvalues, which gives $\C(X)=\C_{\{\pm1\}}$. The result in \cite{dsv} gives a better estimate, as follows:

\begin{theorem}
A circulant graph $Cay(\Z_N,S)$, with $S=-S$ being uniformly random, has no quantum symmetry with probability at least $1-2^{-N/24+2(\log_2N)^2+2}$.
\end{theorem}

\begin{proof}
We can assume $N\geq5$, the estimate being trivial otherwise. Let $m\in\{1,2\}$ be the number of solutions of $2x=0$ in $\Z_N$. It is shown in \cite{dsv} that among the $2^{(N+m)/2}$ sets $S=-S$, with $0\in S$ being allowed, there are at most $2^{m/2+11N/24+2(\log_2N)^2+2}$ sets for which $G(X)\neq\Z_N\rtimes\{\pm1\}$. Since adding or removing $0$ does not change $G(X)$, the same proportion holds for the sets $S\subset\Z_N-\{0\}$. But when $G(X)=\Z_N\rtimes\{\pm1\}$ the graph $X$ is of dihedral type, by Proposition 1.5, and so has no quantum symmetry, by Theorem 4.3.
\end{proof}

\section{Prime powers, the classification}

We discuss now the circulant graphs $X=Cay(\Z_N,S)$ with $N=p^n$, where $p$ is prime, and $n\geq2$. We denote by $H\subset\Z_N$ the subgroup of order $p$, generated by $h=p^{n-1}$. Observe that the group of units $\Z_N^*$ is a union of cosets of $H$. We have:

\begin{proposition}
If $S\cap\Z_N^*$ is a union of cosets of $H$, then $X$ has quantum symmetry.
\end{proposition}

\begin{proof}
Given $c\in\Z_N$, consider the permutation $\sigma_c$ given by $\sigma_c(x)=x+h$ for $x\in c+p\Z_N$, and by $\sigma_c(x)=x$ otherwise. If $x,y$ are both inside or both outside $c+p\Z_N$ then $\sigma_c(y)-\sigma_c(x)=y-x$. Otherwise $y-x$ is a unit, and $\sigma_c(y)-\sigma_c(x)=y-x\pm h$ belongs to $S$ if and only if $y-x$ does, by our assumption. Thus $\sigma_c\in G(X)$. Now since $\sigma_0,\sigma_1$ are non-trivial, and have disjoint supports, the criterion of Schmidt \cite{sch}, recalled in the proof of Proposition 4.2, applies.
\end{proof}

As an illustration, at $n=2$ we have $H=p\Z_N$, and the assumption means that $S\cap\Z_N^*$ is the preimage of a subset of $\Z_p^*$. At $N=9$ this subset can only be empty, or $\Z_3^*$ itself, and we obtain $4$ graphs, namely the empty graph, the graph formed by $3$ triangles, and their complements. In the other sense now, we have:

\begin{proposition}
If $X$ is of type $E$, with $1+h\notin E$, then $X$ has no quantum symmetry, and we have $G^+(X)=G(X)=\Z_N\rtimes E$.
\end{proposition}

\begin{proof}
Assume first $p=2$. At $N=4$ we have $1+h=-1\in E$, so we must have $N\geq8$. We have then $\Z_N^*=\{\pm1\}\times\langle5\rangle$, with $1+h$ being the unique element of order $2$ of the cyclic group $\langle5\rangle$. Since $-1\in E$ we have $E=\{\pm1\}\times E'$ with $E'\subset\langle5\rangle$, and our assumption gives $E'=\{1\}$. Thus $X$ is of dihedral type, and Theorem 4.3 applies.

Assume now $p\geq3$. The group $\Z_N^*$ being cyclic, with $1+h$ generating its subgroup of order $p$, our assumption means that $p$ does not divide $|E|$. Thus the reduction map $E\to\Z_p^*$ is injective, its kernel being a $p$-group. We claim that the characters $\xi$ and $\xi^p$ are linked. Indeed, the elements $1,p,1+p$ have trivial stabilizers in $E$, and with $a,b,c\in E$, we have:
$$a+pb=c(1+p)\implies a=c\implies pb=pc\implies b=c$$

Here we have used the above injectivity property, first modulo $p$, and then for the equality $pb=pc$, which gives $b=c$ modulo $p^{n-1}$, with $n\geq2$. Thus Theorem 2.4 applies, with $F=\{\xi,\xi^p\}$, and gives the result.
\end{proof}

Observe that, in contrast with Theorem 3.4, there is no assumption here on the order of $E$. In order to show that the above two results cover all the circulant graphs, we use the theory of Schur rings. We recall from section 1 that $\C(X)$ consists of the matrices $\sum_xc_x\tau_x$ with $c$ being constant on the sets of a certain partition of $\Z_N$, called basic sets, and with $S$ being a union of basic sets. By a result of Leung and Man \cite{lm1}, \cite{lm2}, we have 3 cases:
\begin{enumerate}
\item Trivial case: the basic sets are $\{0\}$ and $\Z_N-\{0\}$.
\item Cyclotomic case: the basic sets are the orbits of a group $E\subset\Z_N^*$.
\item Wedge product case: there are subgroups $0\neq K\subset L\neq\Z_N$ such that any basic set which is not contained in $L$ is a union of cosets of $K$.
\end{enumerate}

To be more precise, this result holds for any cyclic group, with a fourth case, that of the tensor products, which cannot appear when $N$ is a prime power. In the trivial case the graph is empty or complete, in the cyclotomic case the graph has a type, in our sense, and the wedge product case corresponds to the graphs which, far away from $0$, are insensitive to the translations by the elements of $K$. We are led in this way to:

\begin{theorem}
For a circulant graph $X=Cay(\Z_N,S)$ with $N=p^n$, $n\geq2$, the following conditions are equivalent:
\begin{enumerate}
\item $X$ has quantum symmetry.
\item $S\cap\Z_N^*$ is a union of cosets of the subgroup of order $p$.
\end{enumerate}
When these conditions are not satisfied, $X$ is of type $E=\{a|aS=S\}$, with $E$ having order dividing $p-1$ at $p\geq3$, and $E=\{\pm1\}$ at $p=2$, and we have $G^+(X)=G(X)=\Z_N\rtimes E$.
\end{theorem}

\begin{proof}
By Propositions 5.1 and 5.2, it is enough to prove that if $(2)$ fails, then $X$ is of type $E$, with $1+h\notin E$. We use the above result of Leung and Man. In the trivial case we have $S\cap\Z_N^*=\emptyset$ or $S\cap\Z_N^*=\Z_N^*$, so $(2)$ holds. In the wedge product case we have $H\subset K$ and $L\subset p\Z_N$, because the subgroups of $\Z_N$ form a chain. Thus any basic set containing units is a union of cosets of $H$, and so is its intersection with $\Z_N^*$, so $(2)$ holds again.

Finally, in the cyclotomic case $X$ is of type $E$. If $1+h\in E$ then $S$ is invariant under the multiplication by $1+h$, and since for $s\in\Z_N^*$ the elements $s(1+th)$ with $t\in\Z$ form the coset $s+H$, we conclude that $(2)$ holds. Thus, if $(2)$ fails, we must have $1+h\notin E$. The last assertion follows from Proposition 5.2, and from the fact that for $X$ of type $E$ we have $E=\{a|aS=S\}$.
\end{proof}

As an illustration, here is the number of sets $S=-S$ for which $Cay(\Z_N,S)$ has, or has not, quantum symmetry, the trivial cases $S=\emptyset$ and $S=\Z_N-\{0\}$ being included:
\begin{center}
\begin{tabular}{lrrrrrr}
\toprule
$N$&4&8&9&16&25&27\\
\midrule
Quantum symmetry&4&8&4&64&16&128\\
No quantum symmetry&0&8&12&192&4080&8064\\
\bottomrule
\end{tabular}
\end{center}

We have checked by computer, for these values of $N$, that the graphs in the second row are indeed those which are of type $E$, with $1+h\notin E$. Among the $4080$ graphs at $N=25$, there are $60$ graphs of type $E=\{\pm1,\pm7\}$, such as the $4$-valent graph $Cay(\Z_{25},\{\pm1,\pm7\})$.

As a conclusion to our study, the graphs having quantum symmetry are those to which the criterion of Schmidt \cite{sch} applies, as shown below. In particular, for these graphs, the group $G(X)$, viewed as permutation group, determines whether $X$ has quantum symmetry or not, which in general is not the case, as shown in \cite{drs}, where a question from \cite{bm}, \cite{sc2} was answered. Observe also that, in analogy with Proposition 4.4, any graph $X$ having $N$ vertices, whose automorphism group is $\Z_N\rtimes E\subset S_N$, has no quantum symmetry, under the assumptions of Theorem 3.4.

In the terminology of Meunier \cite{meu}, the result is as follows, with the Schmidt alternative for a family of graphs meaning that the criterion of Schmidt is an equivalence, for the graphs in that family:

\begin{theorem}
The circulant graphs having $p^n$ vertices, with $n\geq2$, and the Cayley graphs of the finite abelian groups which are of dihedral type, satisfy the Schmidt alternative: such a graph $X$ has quantum symmetry if and only if $G(X)$ contains two non-trivial automorphisms having disjoint supports.
\end{theorem}

\begin{proof}
In one sense, this is the criterion from \cite{sch}. Conversely, if $X$ has quantum symmetry, in the prime power case the condition (2) in Theorem 5.3 holds, and the automorphisms constructed in the proof of Proposition 5.1 have disjoint supports. As for the dihedral case, here we have $A=\Z_4\times\Z_2^n$ by Theorem 4.3, and the automorphisms constructed in the proof of Proposition 4.2 have disjoint supports.
\end{proof}

\section{Rigid triangles, quasi-thin case}

In this section and in the next ones we go beyond the Cayley graphs of the abelian groups, by using a different method, on the vertex side. Let $X$ be a graph with vertex set $V$, and consider the basis of $\C(X)$ formed by $0$-$1$ matrices. As explained in section 1, these matrices correspond to a partition of $V\times V$ into subsets, called relations, and we denote by $\rho(i,k)$ the relation containing the pair $(i,k)$. For a Cayley graph of an abelian group, $\rho(i,k)$ is given by the basic set containing $k-i$.

We assume that $\C(X)$ is homogeneous, in the sense that its diagonal matrices are the scalars. This is the same as saying that the relations form an association scheme, not necessarily commutative, and is automatic when $X$ is vertex-transitive. The results below hold in fact for any homogeneous coherent algebra, with the relations being not necessarily symmetric. Each relation has then a valency, which is the common row and column sum of its matrix. In this language, Proposition 1.3 reformulates as follows, see \cite{lmr}:
$$u_{ij}u_{kl}=0\quad{\rm unless}\quad\rho(i,k)=\rho(j,l)$$

Given a quantum subgroup $G'\subset G^+(X)$, we say that a relation is commutative for $G'$ when the images of $u_{ij},u_{kl}$ in $C(G')$ commute, for any $2$ pairs $(i,k),(j,l)$ in this relation. By the above formula, $G'$ is classical precisely when all the relations are commutative.

We say that a vertex $i$ is determined by its relations with two other vertices $k,m$ when $i$ is the unique vertex $i'$ satisfying $\rho(i',k)=\rho(i,k)$ and $\rho(i',m)=\rho(i,m)$, and we use a similar convention for more than $2$ vertices.

\begin{definition}
A triple of distinct vertices $(i,k,m)$ is called rigid when each of these vertices is determined by its relations with the other two.
\end{definition}

Observe that, $\C(X)$ being an algebra, these notions depend only on the relations between $i,k,m$. That is, if $\rho(j,l)=\rho(i,k)$, then there is at least one vertex $n$ satisfying $\rho(j,n)=\rho(i,m)$ and $\rho(l,n)=\rho(k,m)$, and $j$ is determined by its relations with $l,n$ precisely when $i$ is determined by its relations with $k,m$.

The following result is our main tool. It is a version of two lemmas of Schmidt, from \cite{scd}, \cite{sc2}, which were obtained there in terms of the distances in an undirected graph, instead of the relations of the coherent algebra:

\begin{lemma}
Let $G'\subset G^+(X)$ be a quantum subgroup, let $(i,k)$ and $(j,l)$ be two pairs of vertices in the same relation, and let $j'\neq j$. Then, inside $C(G')$, we have
$$u_{ij}u_{kl}u_{ij'}=0$$
in each of the following two situations:
\begin{enumerate}
\item When there is a vertex $n$ with $\rho(n,j')\neq\rho(n,j)$, such that the relation $\rho(l,n)$ is commutative for $G'$.
\item When there is a vertex $n$ with $\rho(n,j')\neq\rho(n,j)$, such that $l$ is determined by its relations with $j,j',n$.
\end{enumerate}
\end{lemma}

\begin{proof}
We can assume $\rho(l,j')=\rho(l,j)$, because otherwise $u_{kl}u_{ij'}=0$. Consider the set $A$ of vertices $a$ satisfying $\rho(i,a)=\rho(j,n)$ and $\rho(k,a)=\rho(l,n)$. By inserting $\sum_au_{an}=1$ in the middle of the product $u_{ij}u_{kl}$, the terms which survive are those with $a\in A$. Also, for $a\in A$ we have $\rho(a,i)=\rho(n,j)\neq\rho(n,j')$, and so $u_{an}u_{ij'}=0$. Thus, with $c=\sum_{a\in A}u_{an}$, we have $u_{ij}u_{kl}=u_{ij}cu_{kl}$ and $cu_{ij'}=0$.

(1) Here $u_{kl}$ commutes with $u_{an}$ for any $a\in A$, by our assumption, and so:
$$u_{ij}u_{kl}u_{ij'}=u_{ij}cu_{kl}u_{ij'}=u_{ij}u_{kl}cu_{ij'}=0$$

(2) Let $b\neq l$. We claim that $u_{ij}cu_{kb}u_{ij'}=0$. Indeed, this is clear when $\rho(b,n)\neq\rho(l,n)$, where $cu_{kb}=0$, and when $\rho(b,j')\neq\rho(l,j')$, where $u_{kb}u_{ij'}=0$. In the remaining case, since $l$ is determined by its relations with $j,j',n$, we have $\rho(b,j)\neq\rho(l,j)$, and so $u_{ij}u_{kb}=0$. But inserting $\sum_au_{an}=1$ in the middle of this latter product amounts to inserting $c$, and we obtain $u_{ij}cu_{kb}=0$. This proves our claim, and by summing over $b$ we obtain:
$$u_{ij}u_{kl}u_{ij'}=u_{ij}cu_{kl}u_{ij'}=u_{ij}c\Big(\sum_bu_{kb}\Big)u_{ij'}=u_{ij}cu_{ij'}=0$$

Thus, we are led to the conclusion in the statement.
\end{proof}

As a consequence, we have the following commutation criteria:

\begin{lemma}
Let $G'\subset G^+(X)$ be a quantum subgroup. A relation $\rho(i,k)$ is commutative for $G'$, in each of the following situations:
\begin{enumerate}
\item When this relation has valency $1$.
\item When there is a vertex $m$ such that $i$ is determined by its relations with $k,m$, and $k$ is determined by its relations with $i,m$. In particular, this is the case when $i,k$ are part of a rigid triple.
\item When there is a vertex $m$ such that the relation $\rho(k,m)$ is commutative for $G'$, and $i$ is determined by its relations with $k,m$.
\item More generally, when for any pair $(j,l)$ in this relation, and any $j'\neq j$ with $\rho(l,j')=\rho(l,j)$, one of the conditions in Lemma 6.2 is satisfied.
\end{enumerate}
\end{lemma}

\begin{proof}
Let $(i,k)$ and $(j,l)$ be two pairs in our relation, and set $x=u_{ij}$, $y=u_{kl}$.

(1) Since $l$ is the unique vertex $l'$ satisfying $\rho(j,l')=\rho(i,k)$, we have $x=x\sum_{l'}u_{kl'}=xy$. Similarly we have $y=yx$, and by taking adjoints we obtain $x=y$.

(4) We have $xyu_{ij'}=0$ for any $j'\neq j$, by Lemma 6.2 when $\rho(l,j')=\rho(l,j)$, and trivially otherwise. Thus, we obtain:
$$xy=xy\sum_{j'}u_{ij'}=xyx$$

Thus $xy$ is self-adjoint, and so $xy=yx$.

(2) Let $n$ be a vertex satisfying $\rho(j,n)=\rho(i,m)$ and $\rho(l,n)=\rho(k,m)$, and let $j'\neq j$ with $\rho(l,j')=\rho(l,j)$. Since $j$ is determined by its relations with $l,n$, we have $\rho(n,j')\neq\rho(n,j)$. Also, $l$ is determined by its relations with $j,n$. Thus the condition (2) in Lemma 6.2 is satisfied, and so (4) applies.

(3) With $n,j'$ as above, we have again $\rho(n,j')\neq\rho(n,j)$, and the relation $\rho(l,n)=\rho(k,m)$ is commutative. Thus the condition (1) in Lemma 6.2 is satisfied, and so (4) applies.
\end{proof}

As a first consequence, we have the following criterion, which is in the spirit of the methods of Chassaniol \cite{cha} and Schmidt \cite{sc2} too:

\begin{theorem}
Assume that $\C(X)$ is homogeneous, and that any two vertices $i,k$ with $\rho(i,k)$ having valency at least $2$ are part of a rigid triple. Then $X$ has no quantum symmetry.
\end{theorem}

\begin{proof}
This follows from Lemma 6.3, which shows that $\A$ is commutative. More generally, the same conclusion holds when all the relations can be shown to be commutative, by using Lemma 6.3.
\end{proof}

As a basic example, when all the valencies are $1$, the relations are the graphs of the elements of a group acting simply transitively on $V$, and we recover the result in \cite{mn}.

As a main application, let us go back to the graphs of dihedral type, from section 4. We say that $\C(X)$ is quasi-thin when its valencies are $1$ and $2$. Assume that this is the case, and that $X$ is vertex-transitive. By a result of Muzychuk and Ponomarenko \cite{mp2}, stating that a quasi-thin scheme whose automorphism group is transitive is Schurian, we have then $\C(X)=G(X)'$, so the relations are the orbits of $G=G(X)$ on $V\times V$. Thus the stabilizer $H\subset G$ of a vertex has orbits of size at most $2$, and so $H\simeq\Z_2^r$, for some $r\geq0$.

\begin{lemma}
If $r\geq2$, then $H$ contains two non-trivial elements with disjoint supports.
\end{lemma}

\begin{proof}
Let $0$ be the vertex fixed by $H$, and consider two orbits of size $2$ of $H$, say $\Delta=\{k,k'\}$ and $\Delta'=\{m,m'\}$. By using elements of $H$ which interchange $k,k'$, and $m,m'$, we see that we have either $\rho(k,m)=\rho(k',m')\neq\rho(k,m')=\rho(k',m)$, in which case we say that $\Delta,\Delta'$ are locked, or the $4$ relations between $\Delta,\Delta'$ coincide.

Now let $U$ be a connected component of the graph formed by the locked pairs, and consider the permutation $h_U$ which interchanges the $2$ elements of each $\Delta\in U$, and fixes the other vertices. It follows from the above that $h_U$ preserves all the relations, and so that $h_U\in H$. Also, an element of $H$ cannot interchange the elements of $\Delta$ and fix those of $\Delta'$, when $\Delta,\Delta'$ are locked. Thus $H$ is generated by the elements $h_U$, whose supports are disjoint, and $r$ is the number of components.
\end{proof}

We can now state our main result on the quasi-thin case, as follows:

\begin{theorem}
Let $X$ be a vertex-transitive graph, whose coherent algebra is quasi-thin, and let $H\simeq\Z_2^r$ be the stabilizer of a vertex, inside $G(X)$.
\begin{enumerate}
\item If $r=0$, then $X$ has no quantum symmetry.
\item If $r=1$, then $X$ has quantum symmetry precisely when the non-trivial element of $H$ has exactly $2$ conjugates in $G(X)$.
\item If $r\geq2$, then $X$ has quantum symmetry.
\end{enumerate}
In particular these graphs satisfy the Schmidt alternative: $X$ has quantum symmetry if and only if $G(X)$ contains two non-trivial automorphisms having disjoint supports.
\end{theorem}

\begin{proof}
(1) Here all the valencies are $1$, and Theorem 6.4 applies. See also \cite{mn}.

(2) For any vertex $i$ let $a_i$ be the non-trivial element of the stabilizer of $i$. These elements are the conjugates of the element in the statement, and their fixed point sets form a partition of $V$. If there are only $2$ such conjugates, their supports are disjoint, and $X$ has quantum symmetry, by \cite{sch}. Observe also that there are at least $2$ conjugates, because $a_i$ cannot be central.

Assume now that there are at least $3$ conjugates, and let $i,k$ be vertices with $\rho(i,k)$ having valency $2$, so that $\alpha=a_i$, $\beta=a_k$ are distinct. Given a third vertex $m$, with $\gamma=a_m$, the vertices having the same relations as $m$ with respect to $i,k$ are those in $\{m,\alpha m\}\cap\{m,\beta m\}$. If this set has $2$ elements then $\beta\alpha$ fixes $m$, so $\beta\alpha=\gamma$, and so $\alpha,\beta$ commute, and $\gamma=\alpha\beta$. By doing the same for the other $2$ vertices, we conclude that the triple $(i,k,m)$ is rigid, provided that $\gamma\neq\alpha,\beta,\alpha\beta$. If such a conjugate $\gamma$ exists, for any $\alpha\neq\beta$, then Theorem 6.4 applies.

Otherwise, there are exactly $3$ conjugates $\alpha,\beta,\gamma$, which commute and satisfy $\alpha\beta=\gamma$. But in this case, the permutation which is equal to $\beta$ on the fixed points of $\alpha$, and to the identity elsewhere, preserves all the relations. Indeed, $\beta$ and $\gamma$ coincide on the fixed points of $\alpha$, so a pair of vertices, exactly one of which is fixed by $\alpha$, is mapped as by $\beta$ when the other vertex is fixed by $\beta$, and as by $\gamma$ when it is fixed by $\gamma$. This permutation, which is different from $1$ and $\beta$, belongs then to $G(X)$, and to the stabilizer of any fixed point of $\beta$, which contradicts $r=1$.

(3) This follows from Lemma 6.5, and from \cite{sch}. Finally, the last assertion follows from the above, by using again the criterion in \cite{sch}.
\end{proof}

Observe that Theorem 4.3 appears as a particular case, with $G(X)=A\rtimes\{\pm1\}$, and with the conjugates of the inversion $x\to-x$ being the maps $x\to c-x$ with $c\in2A$.

\section{Edge commutation, a trichotomy}

Besides $G(X)$ and $G^+(X)$, there is a third object which can be associated to a graph $X$, namely the quantum automorphism group $G^*(X)$ constructed by Bichon in \cite{bi1}. This is the quantum subgroup of $G^+(X)$ obtained by assuming that the entries of the magic matrix satisfy $u_{ij}u_{kl}=u_{kl}u_{ij}$, whenever $i-k$ and $j-l$ are edges of $X$. We have inclusions as follows:
$$G(X)\subset G^*(X)\subset G^+(X)$$

This quantum group is related to the quantum symmetries of the graph $C^*$-algebra of $X$, by a result of Schmidt and Weber \cite{sw}, and is a useful tool in the study of $G^+(X)$, see \cite{scp}, \cite{sc2}. Unlike $G^+(X)$, it is not invariant under complementation, because for the complete graph with $N$ vertices we obtain $S_N$, and for the empty graph we obtain $S_N^+$. Thus, when $X$ has quantum symmetry, the question is that of deciding which of the above $2$ inclusions are proper, for $X$, and for its complement too. We say that $X$ has quantum symmetry in the sense of Bichon when $G^*(X)\neq G(X)$.

We use the language of section 6, with $\C(X)$ being assumed to be homogeneous. Since $d\in\C(X)$, the set of edges is a union of relations, and $G^*(X)$ is the biggest quantum subgroup of $G^+(X)$ for which the relations contained in the set of edges are commutative.

In order to detect the quantum symmetry in the sense of Bichon, we can use the following version of the criterion of Schmidt \cite{sch}, due to Haque, Karmakar and Mandal \cite{hkm}:

\begin{proposition}
Assume that $G(X)$ contains two non-trivial automorphisms $\sigma,\tau$ having disjoint supports, with no edges of $X$ between these supports. Then $G^*(X)\neq G(X)$.
\end{proposition}

\begin{proof}
This is proved in \cite{hkm}, by an argument similar to the following one. Consider the magic matrix $vw$ from the proof of Proposition 4.2. Its non-zero entries are $p,1-p$, at positions $(i,j)$ with $i,j$ in the support of $\sigma$, then $q,1-q$, at positions $(k,l)$ with $k,l$ in the support of $\tau$, and $1$, on the diagonal. Thus if two entries $(vw)_{ij},(vw)_{kl}$ do not commute, then $i,k$ belong to different supports, up to a permutation, and so are not joined by an edge. We conclude that $vw$ satisfies the relations of Bichon, and since its entries do not commute, $C(G^*(X))$ is not commutative.
\end{proof}

In the other sense, the commutation can be propagated from the edges to the other relations, by using Lemma 6.3. As a first application, let us go back to the graphs of dihedral type, from section 4. We denote by $2K_2$ the graph $Cay(\Z_4,\{2\})$, formed by $2$ disjoint edges.

\begin{theorem}
Let $X=Cay(A,S)$ be of dihedral type. Then $G^*(X)=G(X)$, unless $X$ is the graph $2K_2$, where we have $G^*(X)=G^+(X)\neq G(X)$.
\end{theorem}

\begin{proof}
By Theorem 4.3 we can assume $A=\Z_4\times\Z_2^n$. The relations correspond to the sets $\{x,-x\}$, and have valency $1$ when $x$ belongs to the subgroup $T=\{x|2x=0\}$, which has index $2$, and valency $2$ otherwise. Assume first $S\subset T$. Then $\C(X)$ is contained in the coherent algebra spanned by the translations $\tau_x$ with $x\in T$, and by the sum of the other translations, which has dimension $|T|+1$. Since $\C_{\{\pm1\}}$ has dimension $3|T|/2$, we obtain $|T|=2$, so $A=\Z_4$ and $S=\{2\}$. Thus $X=2K_2$, and since the edges form a relation of valency $1$, which is commutative for $G^+(X)$ by Lemma 6.3 (1), we have $G^*(X)=G^+(X)$, and Theorem 4.3 applies.

Assume now that there is $s\in S-T$. The relation corresponding to $s$ is commutative for $G^*(X)$, and for any $y\notin T$ with $y\neq s$ we have $y-s\in T$. Thus Lemma 6.3 (3) applies to the vertices $y,0,s$, and shows that the relation corresponding to $y$ is commutative for $G^*(X)$. Since the relations of valency $1$ are commutative as well, $G^*(X)$ is classical.
\end{proof}

As a conclusion, the quantum symmetries of the graphs coming from $A=\Z_4\times\Z_2^n$, found in Theorem 4.3, are not seen by the quantum group of Bichon, with one exception. At $n=0$ the graphs are $2K_2$ and its complement, which is the square, and we recover in this way the computations for these $2$ graphs from \cite{sw}.

As a second result, let us recall that given a quantum permutation group $G$, and a number $n\geq2$, we can form the usual wreath product $G\wr S_n$, and the free wreath product $G\wr_*S_n^+$, constructed by Bichon in \cite{bi2}. The corresponding algebras are generated by the entries of $n$ copies $w^1,\ldots,w^n$ of the magic matrix of $G$, and by those of a $n\times n$ magic matrix $v$, with the following relations, in the free case:
$$[w^a_{ij},v_{ab}]=0$$

As for the usual wreath product, here all the entries of $w^a,w^c$ with $a\neq c$ commute, and the entries of $v$ commute with each other, and with those of each $w^a$. In both cases, the magic matrix is given by the formula $u_{(a,i)(b,j)}=w^a_{ij}v_{ab}$. The main result in \cite{bi2}, which holds as well for $G^+$, as shown in \cite{bbf}, is the formula $G^*(nW)=G^*(W)\wr_*S_n^+$, valid for any connected graph $W$, with $nW$ being the disjoint union of $n$ copies of $W$. We have:

\begin{proposition}
Let $W$ be a connected graph, let $n\geq2$, and let $X$ be the complement of the graph $nW$, obtained by joining $n$ copies of the graph $Z=W^c$. Then
$$G^*(X)=G^*(Z)\wr S_n$$
with a usual wreath product. In particular, $G^*(X)=G(X)$ precisely when $G^*(Z)=G(Z)$.
\end{proposition}

\begin{proof}
By \cite{bbf}, \cite{bi2} we have $G^+(X)=G^+(nW)=G^+(W)\wr_*S_n^+$. With the vertices of $X$ written $(a,i)$, where $a\in\{1,\ldots,n\}$ and $i$ is a vertex of $W$, this means that $\A$ is the universal $C^*$-algebra generated by the entries of $n$ magic matrices $w^a$, each commuting with the adjacency matrix of $W$, and by those of a $n\times n$ magic matrix $v$, with the relations $[w^a_{ij},v_{ab}]=0$, and that the magic matrix of $X$ is given by $u_{(a,i)(b,j)}=w^a_{ij}v_{ab}$.

The edges of $X$ are the pairs $(a,i)-(c,k)$ with $a\neq c$, and those with $a=c$, and with $i-k$ being an edge of $Z$. The relations of Bichon coming from the edges of the first type are as follows, with $a\neq c$ and $b\neq d$:
$$w^a_{ij}v_{ab}w^c_{kl}v_{cd}=w^c_{kl}v_{cd}w^a_{ij}v_{ab}$$

By summing over $j,l$ we obtain $v_{ab}v_{cd}=v_{cd}v_{ab}$, so the entries of $v$ commute. By summing over $j$ only we obtain the following formula:
$$v_{ab}w^c_{kl}v_{cd}=w^c_{kl}v_{ab}v_{cd}$$

This formula holds at $b=d$ too, where both terms vanish, so by summing over $d$ we conclude that $v_{ab}$ commutes with $w^c_{kl}$. Thus our relations read $v_{ab}v_{cd}[w^a_{ij},w^c_{kl}]=0$, and by summing over $b,d$ we obtain $[w^a_{ij},w^c_{kl}]=0$, for $a\neq c$.

As for the edges of the second type, here the relations are $v_{ab}[w^a_{ij},w^a_{kl}]=0$, with $i-k$ and $j-l$ being edges of $Z$, and by summing over $b$ we conclude that each $w^a$ satisfies the relations of Bichon for the graph $Z$. Conversely, all these relations imply those of Bichon for $X$, and so $C(G^*(X))=C(G^*(Z))^{\otimes n}\otimes C(S_n)$, with maximal tensor products, as claimed.
\end{proof}

Let us go back now to the circulant graphs. At $N=9$ the graph $Cay(\Z_9,\Z_9^*)$, obtained by joining $3$ empty graphs with $3$ vertices, satisfies $G(X)=G^*(X)\neq G^+(X)$, by Proposition 7.3. Its complement consists of $3$ triangles, which are rigid, so the edges form a relation which is commutative for $G^+(X)$, by Lemma 6.3, and we obtain $G(X)\neq G^*(X)=G^+(X)$. As for the third possible situation, this appears at $N=25$, where the graph $Cay(\Z_{25},\Z_{25}^*)$ satisfies $G(X)\neq G^*(X)\neq G^+(X)$, the quantum groups being $S_5\wr S_5\subset S_5^+\wr S_5\subset S_5^+\wr_*S_5^+$.

In all the above results, the graphs having quantum symmetry in the sense of Bichon are those to which Proposition 7.1 applies. The question of whether this criterion is an equivalence was discussed in \cite{hkm}, where this was shown to be the case for the forests. In analogy with the conjecture mentioned in the introduction, regarding the Schmidt alternative, that we will discuss in section 8, we are led to the following statement:

\begin{conjecture}
A circulant graph $X$ satisfies $G^*(X)\neq G(X)$ if and only if $G(X)$ contains two non-trivial automorphisms having disjoint supports, with no edges between these supports.
\end{conjecture}

When the number of vertices is a prime $p$, and $X$ is not complete or empty, we have $G(X)\subset\Z_p\rtimes\Z_p^*$, and the non-trivial elements of this group have at most $1$ fixed point. Thus, the conjecture states that any non-empty circulant graph with $p$ vertices satisfies $G^*(X)=G(X)$. This is weaker than the conjecture in \cite{mar}, and holds under the assumptions of Theorem 3.4, and for $p\leq250$, by the results in \cite{cha}, \cite{mar}. For the Cayley graphs of dihedral type the same statement holds, by Theorems 5.4 and 7.2, because for $A=\Z_4\times\Z_2^n$ the non-trivial automorphisms having fixed points are those in the proof of Proposition 4.2, as explained after Theorem 6.6, and their supports are $T$ and its complement.

We have checked by computer that for the circulant graphs with $N\leq20$ vertices the above criteria, namely Propositions 7.1 and 7.3, and Lemma 6.3, decide whether $G^*(X)=G(X)$ holds or not, for all the $3068$ sets $S=-S$. Thus, Conjecture 7.4 holds for $N\leq20$. Finally, when the number of vertices is $p^2$, we have:

\begin{theorem}
Let $X=Cay(\Z_N,S)$ with $N=p^2$ be a circulant graph having quantum symmetry, which is not complete, and consider the graph $Z=Cay(p\Z_N,S\cap p\Z_N)$.
\begin{enumerate}
\item If $S$ does not contain $\Z_N^*$, then $G^*(X)\neq G(X)$.
\item If $S$ contains $\Z_N^*$, then $G^*(X)=G^*(Z)\wr S_p$, so $G^*(X)=G(X)$ if and only if $G^*(Z)=G(Z)$.
\end{enumerate}
In particular, Conjecture 7.4 holds for the circulant graphs having $p^2$ vertices if and only if it holds for the circulant graphs having $p$ vertices.
\end{theorem}

\begin{proof}
(1) By Theorem 5.3 the set $S\cap\Z_N^*$ is a union of cosets of $H=p\Z_N$, so there is a unit $c$ such that $S$ does not intersect the cosets $\pm c+p\Z_N$. The automorphisms $\sigma_0,\sigma_c$ from the proof of Proposition 5.1 have supports $p\Z_N$ and $c+p\Z_N$, there are no edges between these supports, and so Proposition 7.1 applies.

(2) The complement of $X$ is the graph $Cay(\Z_N,S')$, with $S'=p\Z_N-(S\cup\{0\})$ being non-empty. Thus this complement consists of $p$ copies of the graph $W=Cay(p\Z_N,S')$, which is connected, and whose complement is $Z$, and Proposition 7.3 applies.

Regarding now the last assertion, let $X$ be a circulant graph with $p^2$ vertices. If $X$ has no quantum symmetry, or is complete, then $G^*(X)=G(X)$, and $G(X)$ contains no automorphisms as in Conjecture 7.4, by Theorem 5.4, and by the fact that any $2$ vertices of a complete graph are adjacent. In the situation (1) such automorphisms exist.

In the situation (2) any $2$ vertices in different cosets of $p\Z_N$ are adjacent, so the supports of two automorphisms as in Conjecture 7.4 must be contained in the same coset, and these automorphisms come then from automorphisms of $Z$, having the same property. Thus the conjecture holds for $X$ if and only if it holds for $Z$, and since any non-complete circulant graph with $p$ vertices appears in this way, and the complete graphs satisfy the conjecture, we are done.
\end{proof}

\section{Transitive groups, open questions}

We discuss now the asymptotic results which can be obtained by using the method of rigid triangles, from section 6. Let $G\subset S_N$ be a transitive permutation group, acting on a set $V$. We denote by $G_i\subset G$ the stabilizer of a vertex $i\in V$, by $k$ the common order of these stabilizers, and by $m$ the maximal number of fixed points of the non-trivial elements of $G$. As a basic example, for the group $G=A\rtimes E$ acting on $A$, with $A$ being abelian and $E\subset Aut(A)$, we have $k=|E|$, and $m$ is the number from section 3. Another class of examples comes from the Frobenius groups. These are the groups of type $G=K\rtimes H$, with $H\subset Aut(K)$ acting without fixed points on $K-\{1\}$, acting on $K$, and here we have $m=1$.

\begin{theorem}
Let $X$ be a graph whose coherent algebra is the commutant of a transitive group $G\subset S_N$, whose stabilizers have order $k\geq2$, and whose non-trivial elements have at most $m$ fixed points. If
$$N>2(k-1)(km-1)+2$$
then $X$ has no quantum symmetry. In particular, this is the case when $N\geq2k^2m$.
\end{theorem}

\begin{proof}
The relations are the orbits of $G$ on $V\times V$, so given distinct vertices $i,j,v$, the vertices having the same relations as $i$ with respect to $j,v$ are those in $G_ji\cap G_vi$. Given $i\neq j$, we look for a vertex $v\neq i,j$ such that $i$ is determined by its relations with $j,v$, and $j$ is determined by its relations with $i,v$.

Assume that $i$ is not determined by its relations with $j,v$. Then $h(i)=s(i)\neq i$ for some $h\in G_j$ and $s\in G_v$. We have $h\neq1$, and with $g=s^{-1}h\in G_i$, the element $s=hg^{-1}$, which is non-trivial, fixes $v$. When $g=1$ the vertex $v\neq j$ is fixed by $h\in G_j$, and there are at most $(k-1)(m-1)$ such vertices. When $g\neq1$, since there are $(k-1)^2$ pairs $(h,g)$, there are at most $(k-1)^2m$ such vertices. The same holds when $j$ is not determined by its relations with $i,v$, and so the number of vertices $v\neq i,j$ which are not as needed is at most:
$$2(k-1)^2m+2(k-1)(m-1)=2(k-1)(km-1)$$

By our assumption this number is smaller than $N-2$, so there is a vertex $v$ as needed. Thus Lemma 6.3 (2) applies, and shows that the relation $\rho(i,j)$ is commutative for $G^+(X)$. We conclude that all the relations are commutative, and so $X$ has no quantum symmetry.
\end{proof}

As an example, for the group $PSL_2(7)$ acting on the $84$ cosets of a subgroup of order $2$ we have $k=2$ and $m=4$, and the above bound is $N>16$. One can check by computer that there are graphs whose coherent algebra is the commutant of this group, and so these graphs have no quantum symmetry. For the Frobenius groups, where $m=1$, the bound is $N>2(k-1)^2+2$.

In the case of the groups $G=A\rtimes E$, with $A$ being abelian, the above result applies to the graphs of type $E$, with a bound which is weaker than the one in Theorem 3.2. However, in this case the counting in the above proof can be refined, and we obtain:

\begin{theorem}
Let $X=Cay(A,S)$ be of type $E$, with $|E|=k\geq2$, and with the non-trivial elements of $E$ having at most $m$ fixed points. If
$$|A|>mk(k-1)-2(k-2)$$
then $X$ has no quantum symmetry. In particular, this is the case when $|A|\geq k^2m$.
\end{theorem}

\begin{proof}
We follow the proof of Theorem 8.1, with the vertices being now $0,x,y\in A$, and with the relation of a pair $(z,z')$ being given by the orbit of $z'-z$ under $E$. Given $x\neq0$, consider the following set, which will play a key role in what follows:
$$D_x=\left\{y\in A\,\Big|\,(c-b)y=(a-b)x\ {\rm for\ some\ distinct}\ a,b,c\in E\right\}$$

The equation $(c-b)y=(a-b)x$ is invariant under the transformations $(a,b,c)\to(ea,eb,ec)$ with $e\in E$, and its solutions $y$, if any, form a coset of the kernel of $c-b$, which has at most $m$ elements. Since there are $k(k-1)(k-2)$ triples of distinct elements, we obtain:
$$|D_x|\leq(k-1)(k-2)m$$

With this done, we look for an element $y\neq0,x$ such that $0$ is determined by its relations with $x,y$, and $x$ is determined by its relations with $0,y$.

Assume that $0$ is not determined by its relations with $x,y$. Then there is $z\neq0$ such that $x-z=h(x)$ and $y-z=h'(y)$ for some $h,h'\in E$, so $(1-h')y=(1-h)x$, and $h,h'\neq1$. When $h=h'$ we have $y-x\in\ker(1-h)$, and there are at most $(k-1)(m-1)$ such elements $y\neq x$. When $h\neq h'$ we have $y\in D_x$.

Assume now that $x$ is not determined by its relations with $0,y$. Then we have $h(x)\neq x$ and $h(x)-y=h'(x-y)$ for some $h,h'\in E$, so $(1-h')y=(h-h')x$, and $h,h'\neq1$. When $h=h'$ we have $y\in\ker(1-h)$, and there are at most $(k-1)(m-1)$ such elements $y\neq0$. When $h\neq h'$ we have $y\in D_x$.

Summing up, the number of elements $y\neq0,x$ which are not as needed is at most:
$$(k-1)(k-2)m+2(k-1)(m-1)=mk(k-1)-2(k-1)$$

By our assumption this number is smaller than $|A|-2$, so there is an element $y$ as needed. Thus Lemma 6.3 (2) applies, and shows that the relation of $(0,x)$ is commutative for $G^+(X)$. We conclude that all the relations are commutative, and so $X$ has no quantum symmetry.
\end{proof}

At $m=1$ the above bound is $|A|>(k-1)(k-2)+2$, so we obtain the bound of Marashdeh \cite{mar}, for all the finite abelian groups. At $E=\{\pm1\}$, where $k=2$ and $m=|A|/|2A|$, the bound reads $|2A|\geq3$. Thus we recover the first part of Theorem 4.3, as far as the lack of quantum symmetry is concerned, and the second part of that theorem shows that our bound is sharp, in this case. Observe also that, compared to Theorems 3.2 and 3.4, where the bound is the same in the cyclic case, the above result does not compute the group $G(X)$.

The interest in the above results, at $m=1$, comes as well from the work of Muzychuk and Ponomarenko in \cite{mp1}, on the pseudocyclic association schemes. These are schemes whose non-trivial relations all have the same valency $k$, and which satisfy a similar condition on the multiplicities, see \cite{mp1}, the basic examples being the schemes of the Frobenius groups. It is shown in \cite{mp1} that a scheme whose non-trivial relations all have valency $k$ is pseudocyclic precisely when, for any distinct vertices $i,i'$, there are exactly $k-1$ vertices $v$ satisfying $\rho(i,v)=\rho(i',v)$, and also that a pseudocyclic scheme of valency $k\geq2$ and rank at least $f(k)$, with $f(k)=O(k^4)$, must come from a Frobenius group. Here the rank is the dimension of the coherent algebra. We have:

\begin{theorem}
Let $X$ be a graph with $N$ vertices, whose coherent algebra is a pseudocyclic association scheme of valency $k\geq2$. If
$$N>2(k-1)(k-2)+2$$
then $X$ has no quantum symmetry. In particular, this is the case when the rank is at least $2k-2$.
\end{theorem}

\begin{proof}
Let $i\neq j$, and let $v\neq i,j$. If $i$ is not determined by its relations with $j,v$, we have $\rho(i',j)=\rho(i,j)$ and $\rho(i',v)=\rho(i,v)$, for some $i'\neq i$. There are $k-1$ choices for $i'$, and for each of them, $k-2$ choices for $v$, because $j$ is one of the $k-1$ vertices $v$ satisfying $\rho(i',v)=\rho(i,v)$. The same holds when $j$ is not determined by its relations with $i,v$, so the number of vertices $v$ which are not as needed is at most $2(k-1)(k-2)<N-2$. Thus Lemma 6.3 (2) applies, all the relations are commutative, and so $X$ has no quantum symmetry. Finally, with $r$ being the rank we have $N=1+k(r-1)$, and at $r\geq2k-2$ we obtain $N\geq2k^2-3k+1>2(k-1)(k-2)+2$.
\end{proof}

For the Frobenius groups, whose schemes are pseudocyclic by \cite{mp1}, this improves the bound $N>2(k-1)^2+2$ coming from Theorem 8.1. In view of the above, we have the following questions:

\medskip

(1) Graphs with valencies $k$. The above results suggest that the lack of quantum symmetry should hold for any graph having enough vertices, whose coherent algebra is homogeneous, with all the non-trivial valencies equal to $k$. The proof of Theorem 8.3 shows that this is the case when $N>2(k-1)(c-1)+2$, with $c$ being the maximal number of vertices $v$ satisfying $\rho(i,v)=\rho(i',v)$, over all the pairs of distinct vertices $i,i'$.

\medskip

(2) Dense case. In Theorems 8.1 and 8.2 the bounds are not optimal in general, and the question is that of finding the Frobenius groups for which the corresponding graphs have quantum symmetry. In the case $K=\Z_p$ this is the question investigated in \cite{mar}, the conjecture there being that $H=\Z_p^*$ is the only such group. A first test case, beyond the cyclic groups, is that of the groups $K=\Z_p^n$, with $H$ being a group of roots of unity of the field with $p^n$ elements, which includes the Paley graphs.

\medskip

(3) Composite case. For the circulant graphs with $N$ vertices, with $N$ arbitrary, the result of Leung and Man \cite{lm1}, \cite{lm2} suggests a recursive approach. In the wedge product case the proof of Proposition 5.1 applies, and the graph has quantum symmetry. In the cyclotomic case, Theorems 2.4, 3.4 and 8.2 provide some partial results, and Proposition 3.3 provides a reduction to the case where $N$ is a prime power, with coherent algebras which do not necessarily come from graphs. The tensor product case is related to the product operations for graphs, studied in \cite{bb}. In view of Theorems 5.4 and 6.6, of the results in \cite{cha}, \cite{mar}, and of the observation of Schanz in \cite{scz}, that the criterion of Schmidt is an equivalence for the vertex-transitive graphs having at most $13$ vertices, we are led to the following statement, which provides a conjectural answer to the question raised in \cite{scz}:

\begin{conjecture}
The circulant graphs satisfy the Schmidt alternative: a circulant graph $X$ has quantum symmetry if and only if $G(X)$ contains two non-trivial automorphisms having disjoint supports.
\end{conjecture}

We have tested this conjecture by computer for $N\leq43$, as follows. For each set $S=-S$ we compute the coherent algebra $\C(X)$, and we say that the graph $X=Cay(\Z_N,S)$ is of type Q when $G(X)$ contains $2$ non-trivial automorphisms having disjoint supports, so that $X$ has quantum symmetry, by the criterion of Schmidt, and of type R when all the relations are commutative by Lemma 6.3, so that $X$ has no quantum symmetry.

Among the $8388604$ sets $S$ with $N\leq43$, there are $109630$ sets of type Q, and all the other sets are of type R, with $6$ exceptions. These exceptions correspond to the Paley graphs with $29,37,41$ vertices and their complements, which have no quantum symmetry, by the results of Marashdeh \cite{mar}. Thus Conjecture 8.4 holds for $N\leq43$. Observe that, in particular, we recover in this way the fact that the Paley graphs with $13$ and $17$ vertices have no quantum symmetry, known from \cite{cha}, \cite{scd}. Here is the number of sets $S$, and the number of sets of type Q, for each $N$:
\begin{center}
\begin{tabular}{rrr@{\qquad\quad}rrr@{\qquad\quad}rrr}
\toprule
$N$&sets&Q&$N$&sets&Q&$N$&sets&Q\\
\midrule
2&2&0&16&256&64&30&32768&2640\\
3&2&0&17&256&2&31&32768&2\\
4&4&4&18&512&128&32&65536&4096\\
5&4&2&19&512&2&33&65536&128\\
6&8&6&20&1024&256&34&131072&1024\\
7&8&2&21&1024&32&35&131072&176\\
8&16&8&22&2048&128&36&262144&20992\\
9&16&4&23&2048&2&37&262144&2\\
10&32&16&24&4096&768&38&524288&2048\\
11&32&2&25&4096&16&39&524288&256\\
12&64&32&26&8192&256&40&1048576&37120\\
13&64&2&27&8192&128&41&1048576&2\\
14&128&32&28&16384&2048&42&2097152&37184\\
15&128&16&29&16384&2&43&2097152&2\\
\bottomrule
\end{tabular}
\end{center}

As an illustration for Proposition 3.3, at $N=28$ there are $32$ sets of type $E=\{\pm1,\pm3,\pm9\}$. Here $K_1\subset\Z_4^*$ is trivial, and we have $K_2=\{1,2,4\}\subset\Z_7^*$, whose coherent algebra is that of the Paley tournament with $7$ vertices, which has no quantum symmetry, by Lemma 6.3. Thus these graphs have no quantum symmetry, although the images of $E$ are $\Z_4^*$ and $\Z_7^*$, whose coherent algebras, which are those of the square and of the complete graph, have quantum symmetry. A similar situation appears at $N=33$, with $E=\langle2\rangle$ and with the Paley tournament with $11$ vertices, to which Lemma 6.3 (4) applies.

\medskip

(4) Higher valencies. By Theorem 6.6 the criterion of Schmidt is an equivalence for the vertex-transitive graphs with valencies $1,2$. The same holds for the Hamming graphs \cite{sc2}, and for several other families of graphs \cite{meu}. This is not the case in general, as shown by the Higman-Sims graph and by a graph coming from a linear system, both found in \cite{sc2}, and by the graphs having trivial automorphism group constructed in \cite{drs}, whose quantum symmetry comes from the perfect solution groups of certain linear systems. The question is that of finding the smallest valencies for which this phenomenon appears, in the vertex-transitive case.

\medskip

Finally, let us discuss the notion of quantum isomorphism, from \cite{amr}, \cite{lmr}. Two graphs $X,Y$ having the same number of vertices are called quantum isomorphic when there is a magic matrix $u$, whose entries are projections on a non-zero finite dimensional Hilbert space, satisfying $d_Xu=ud_Y$, with $d_X,d_Y$ being the adjacency matrices. Two isomorphic graphs are quantum isomorphic, and the converse does not hold, as shown in \cite{amr}.

The graphs which are quantum isomorphic to a given graph $X$ were classified by Musto, Reutter and Verdon in \cite{mrv}. When $X$ has no quantum symmetry, which is the case that we are interested in, the result involves only the group $G(X)$, as follows. Let us call group of central type a finite group $L$, given with a $2$-cocycle $\psi:L\times L\to\mathbb T$ which is non-degenerate, in the sense that the corresponding twisted group algebra is a matrix algebra. For any two commuting elements $g,a\in L$ we set:
$$\rho(g,a)=\psi(g,a)\overline{\psi(a,g)}$$

We have then $\rho(g,1)=1$ and $\rho(a,g)=\rho(g,a)^{-1}$, and for any $a\in L$ the map $g\to\rho(g,a)$ is a character of the centralizer of $a$. A subgroup $S\subset L$ is called coisotropic when it contains the following set, with $Z_g\subset L$ being the centralizer of $g$:
$$S^\perp=\left\{g\in L\,\Big|\,\rho(g,a)=1,\,\forall a\in Z_g\cap S\right\}$$

With these notions in hand, the result in \cite{mrv} is that, when $X$ has no quantum symmetry, the isomorphism classes of graphs which are quantum isomorphic to $X$ correspond to the central type subgroups $L\subset G(X)$ for which the stabilizer of any vertex of $X$, inside $L$, is coisotropic, taken up to a certain equivalence relation. As an application, it was shown in \cite{mrv} that the vertex-transitive graphs having at most $11$ vertices and no quantum symmetry are not quantum isomorphic to other graphs. In our setting, we have:

\begin{theorem}
Let $X=Cay(A,S)$ be of type $E$, having no quantum symmetry, with $G(X)=A\rtimes E$, and assume that $E$ acts without fixed points, or that $E=\{\pm1\}$. Then any graph which is quantum isomorphic to $X$ is isomorphic to $X$. In particular, this is the case for the graphs in Theorems 3.2 and 3.4 with $m=1$, and for the graphs having no quantum symmetry in Theorems 4.3 and 5.3.
\end{theorem}

\begin{proof}
By the above we must prove that any central type subgroup $L\subset G(X)$ having coisotropic stabilizers is trivial. So, assume $L\neq\{1\}$, let $g\in L-\{1\}$, let $v$ be a vertex, and let $S\subset L$ be the stabilizer of $v$. If no element of $S-\{1\}$ commutes with $g$ then $g\in S^\perp$, because $\rho(g,1)=1$. Thus $g\in S$, and so $g$ is an element of $S-\{1\}$ commuting with $g$, contradiction. We conclude that there is an element $a\in L-\{1\}$ satisfying $a(v)=v$ and $ag=ga$.

Assume first that $E$ acts without fixed points. Then the non-trivial elements of $A\rtimes E$ have at most $1$ fixed point. Since the above element $a$ fixes both $v$ and $g(v)$, we obtain $g(v)=v$, for any vertex $v$. Thus $g=1$, contradiction.

Assume now $E=\{\pm1\}$. By Theorem 4.3 we can assume $|2A|\geq3$, the case $A=\Z_2^n$, where $E$ is trivial, being covered by the above. The non-trivial elements of $G(X)$ having fixed points are the maps $r_c(x)=c-x$ with $c\in2A$, and $r_c$ fixes $v$ precisely when $c=2v$. Thus, by the above, we have $r_{2v}\in L$ for any $v$, and these elements commute with any element of $L-\{1\}$, and so commute with each other. But $r_0,r_c$ commute precisely when $2c=0$, so $2A$ is a group of exponent $2$, having at least $4$ elements. We conclude that the elements $r_c$ with $c\in2A$, together with the translations by the elements of $2A$, form an abelian group $M\subset L$, having at least $8$ elements.

Consider now the stabilizer $S=\{1,r_0\}$ of the vertex $0$, and the centralizer $Z$ of $r_0$ inside $L$, which contains $M$. The map $g\to\rho(g,r_0)$ is a character of $Z$, with values $\pm1$, because $r_0^2=1$, whose kernel is contained in $S^\perp$, and so in $S$. Thus $|Z|\leq4$, contradiction.

Finally, the last assertion is clear for the graphs in Theorems 3.2, 3.4 and 4.3. As for the graphs having no quantum symmetry in Theorem 5.3, here at $p=2$ we have $E=\{\pm1\}$, and at $p\geq3$ the reduction map $E\to\Z_p^*$ is injective, so $E$ acts without fixed points.
\end{proof}

\begin{thebibliography}{99}

\bibitem{amr}A. Atserias, L. Man\v{c}inska, D.E. Roberson, R. \v{S}\'amal, S. Severini and A. Varvitsiotis, Quantum and non-signalling graph isomorphisms, {\em J. Combin. Theory Ser. B} {\bf 136} (2019), 289--328.

\bibitem{ba2}T. Banica, Quantum automorphism groups of homogeneous graphs, {\em J. Funct. Anal.} {\bf 224} (2005), 243--280.

\bibitem{bbf}T. Banica and J. Bichon, Free product formulae for quantum permutation groups, {\em J. Inst. Math. Jussieu} {\bf 6} (2007), 381--414.

\bibitem{bb}T. Banica and J. Bichon, Quantum automorphism groups of vertex-transitive graphs of order $\leq11$, {\em J. Algebraic Combin.} {\bf 26} (2007), 83--105.

\bibitem{bbc}T. Banica, J. Bichon and G. Chenevier, Graphs having no quantum symmetry, {\em Ann. Inst. Fourier} {\bf 57} (2007), 955--971.

\bibitem{bm}T. Banica and J.P. McCarthy, The Frucht property in the quantum group setting, {\em Glasg. Math. J.} {\bf 64} (2022), 603--633.

\bibitem{bi1}J. Bichon, Quantum automorphism groups of finite graphs, {\em Proc. Amer. Math. Soc.} {\bf 131} (2003), 665--673.

\bibitem{bi2}J. Bichon, Free wreath product by the quantum permutation group, {\em Algebr. Represent. Theory} {\bf 7} (2004), 343--362.

\bibitem{cha}A. Chassaniol, Study of quantum symmetries for vertex-transitive graphs using intertwiner spaces, \blackarxiv{1904.00455}.

\bibitem{drs}J. van Dobben de Bruyn, D.E. Roberson and S. Schmidt, Asymmetric graphs with quantum symmetry, {\em Proc. Lond. Math. Soc.} {\bf 131} (2025), e70098.

\bibitem{dsv}E. Dobson, P. Spiga and G. Verret, Cayley graphs on abelian groups, {\em Combinatorica} {\bf 36} (2016), 371--393.

\bibitem{ep}S. Evdokimov and I. Ponomarenko, Characterization of cyclotomic schemes and normal Schur rings over a cyclic group, {\em St. Petersburg Math. J.} {\bf 14} (2003), 189--221.

\bibitem{gro}D. Gromada, Quantum symmetries of Cayley graphs of abelian groups, {\em Glasg. Math. J.} {\bf 65} (2023), 655--686.

\bibitem{hkm}R. Haque, U. Karmakar and A. Mandal, Some results on Bichon's quantum automorphism group of graphs, \blackarxiv{2511.15334}.

\bibitem{lm1}K.H. Leung and S.H. Man, On Schur rings over cyclic groups, II, {\em J. Algebra} {\bf 183} (1996), 273--285.

\bibitem{lm2}K.H. Leung and S.H. Man, On Schur rings over cyclic groups, {\em Israel J. Math.} {\bf 106} (1998), 251--267.

\bibitem{lmr}M. Lupini, L. Man\v{c}inska and D.E. Roberson, Nonlocal games and quantum permutation groups, {\em J. Funct. Anal.} {\bf 279} (2020), 108592.

\bibitem{mar}M.F. Marashdeh, Two-basepoint Terwilliger algebras and the quantum symmetry of prime-order circulants, \blackarxiv{2609.00462}.

\bibitem{meu}P. Meunier, Quantum properties of $\mathcal F$-cographs, \blackarxiv{2312.01516}.

\bibitem{mn}S.R. Mondal and J. Nisar, Quantum rigidity of Cayley graphs: an algebraic approach via Schur ring, {\em Mathematics} {\bf 14} (2026), 3513.

\bibitem{mrv}B. Musto, D. Reutter and D. Verdon, The Morita theory of quantum graph isomorphisms, {\em Comm. Math. Phys.} {\bf 365} (2019), 797--845.

\bibitem{mp1}M. Muzychuk and I. Ponomarenko, On pseudocyclic association schemes, {\em Ars Math. Contemp.} {\bf 5} (2012), 1--25.

\bibitem{mp2}M. Muzychuk and I. Ponomarenko, On quasi-thin association schemes, {\em J. Algebra} {\bf 351} (2012), 467--489.

\bibitem{scz}J. Schanz, Quantum symmetries of combinatorial structures: a computer assisted approach, PhD Thesis, Saarland University (2025).

\bibitem{scp}S. Schmidt, The Petersen graph has no quantum symmetry, {\em Bull. Lond. Math. Soc.} {\bf 50} (2018), 395--400.

\bibitem{sch}S. Schmidt, Quantum automorphisms of folded cube graphs, {\em Ann. Inst. Fourier} {\bf 70} (2020), 949--970.

\bibitem{scd}S. Schmidt, On the quantum symmetry of distance-transitive graphs, {\em Adv. Math.} {\bf 368} (2020), 107150.

\bibitem{sc2}S. Schmidt, Quantum automorphism groups of finite graphs, PhD Thesis, Saarland University (2020).

\bibitem{sw}S. Schmidt and M. Weber, Quantum symmetries of graph $C^*$-algebras, {\em Canad. Math. Bull.} {\bf 61} (2018), 848--864.

\bibitem{vz}O. Verbitsky and M. Zhukovskii, Canonization of a random circulant graph by counting walks, {\em Combin. Probab. Comput.} (2025), 1--29.

\bibitem{wan}S. Wang, Quantum symmetry groups of finite spaces, {\em Comm. Math. Phys.} {\bf 195} (1998), 195--211.

\end{thebibliography}

\end{document}