\documentclass[11pt]{amsart} \usepackage[margin=2.5cm]{geometry} \usepackage{amsmath,amssymb,amsthm,mathtools} \usepackage{booktabs} \usepackage{enumitem} \usepackage[dvipsnames]{xcolor} \usepackage[colorlinks=true,linkcolor=magenta,urlcolor=magenta,citecolor=magenta,filecolor=magenta,menucolor=magenta,runcolor=magenta]{hyperref} \hypersetup{pdftitle={On the maximality conjecture for quantum permutation groups},pdfauthor={Claude and Teo}} \setlist{itemsep=2pt,topsep=4pt} \newtheorem{theorem}{Theorem}[section] \newtheorem{proposition}[theorem]{Proposition} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{question}[theorem]{Question} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{fact}[theorem]{Computational fact} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \theoremstyle{plain} \newtheorem{introtheorem}{Theorem} \renewcommand{\theintrotheorem}{\Alph{introtheorem}} \numberwithin{equation}{section} \numberwithin{table}{section} \setcounter{tocdepth}{1} \emergencystretch=3em \raggedbottom \makeatletter \renewcommand{\tocsection}[3]{\indentlabel{\@ifnotempty{#2}{\makebox[1.8em][l]{#2.}}}#3} \makeatother \newcommand{\C}{\mathbb C} \newcommand{\Q}{\mathbb Q} \newcommand{\Z}{\mathbb Z} \newcommand{\F}{\mathbb F} \newcommand{\T}{\mathbb T} \newcommand{\TL}{\mathrm{TL}} \newcommand{\HL}{\mathrm{HL}} \newcommand{\Br}{\mathrm{Br}} \newcommand{\Fix}{\mathrm{Fix}} \newcommand{\NC}{\mathcal{NC}} \newcommand{\Pp}{\mathcal{P}} \DeclareMathOperator{\Aut}{Aut} \DeclareMathOperator{\spn}{span} \DeclareMathOperator{\supp}{supp} \DeclareMathOperator{\Proj}{Proj} \begin{document} \title[Maximality conjecture]{On the maximality conjecture for quantum permutation groups} \author{Claude and Teo} \subjclass[2020]{46L65 (20G42, 05A18)} \keywords{Quantum permutation group, maximality conjecture, noncrossing partition} \begin{abstract} A well-known conjecture, central in quantum permutation group theory, and going back to around 2006, states that $S_N\subset S_N^+$ is maximal. We revisit here this conjecture, and related questions, 20 years after, with 2026 knowledge and tools. \end{abstract} \maketitle \tableofcontents \section*{Introduction} The quantum permutation group $S_N^+$ was introduced by Wang in 1998~\cite{wa}, as the universal compact quantum group acting on $N$ points. The algebra of functions on $S_N^+$ is generated by the entries of an $N\times N$ magic unitary, and its quotient by the commutator ideal is the algebra of functions on $S_N$, so that we have an inclusion $S_N\subset S_N^+$. This inclusion is an equality for $N\le3$, while for $N\ge4$ the quantum group $S_N^+$ is infinite, and for $N\ge5$ it is not even coamenable. Its representation theory is that of $SO_3$, with intertwiners given by the noncrossing partitions~\cite{ba}, instead of all partitions for $S_N$. When classifying the quantum subgroups of $S_4^+$, Banica and Bichon~\cite{bb} found nothing between $S_4$ and $S_4^+$, and this led, around 2006, to the following statement. \smallskip \noindent\textbf{Maximality conjecture.} \emph{For every $N$, the inclusion $S_N\subset S_N^+$ is maximal, in the sense that there is no intermediate quantum group $S_N\subsetneq G\subsetneq S_N^+$.} \smallskip The conjecture holds trivially for $N\le3$, it holds for $N=4$ by~\cite{bb}, and for $N=5$ by~\cite{bah}, the proof there relying on the classification of subfactors of index $\le5$~\cite{imps,jms}. For $N\ge6$ it is open. Since there is no easy quantum group strictly between $S_N$ and $S_N^+$~\cite{bcs}, the conjecture lies beyond easiness, and it is a natural first test case for the classification of compact quantum groups beyond easiness. We revisit here this conjecture, and some related questions, twenty years after, with 2026 knowledge and tools. After preliminaries in Section~\ref{sec:maximality}, the paper is organized around three approaches: \smallskip (1) \emph{Subgroups.} Given a quantum subgroup $G\subset S_N^+$ with $G\not\subset S_N$, the conjecture predicts $\langle S_N,G\rangle=S_N^+$. This is the natural source of counterexamples. It is also of independent interest, the equality $\langle S_N,G\rangle=S_N^+$ being a non-trivial result about $G$ itself. We test in this way group duals, which by a theorem of Bichon~\cite{bi} act through ``Fourier families'' of abelian groups, and reduce to just-non-abelian groups (Section~\ref{sec:duals}), quantum automorphism groups of graphs (Section~\ref{sec:graphs}), twists of $S_N$ and of $PU_n$ (Section~\ref{sec:twists}), and the quantum groups coming from complex Hadamard matrices (Section~\ref{sec:hadamard}). No counterexample appears. \smallskip (2) \emph{Exotic quantum groups.} Assume that $S_N\subsetneq G\subsetneq S_N^+$ exists, and develop the algebraic and analytic theory of $G$: representations and moments, orbitals, diagonal algebras, coamenability, and the finite case. The aim is twofold: having this theory available, should such a $G$ exist, and finding a contradiction coming from it. This is done in Section~\ref{sec:exotic}. \smallskip (3) \emph{Partitions.} By Tannakian duality, the intermediate quantum groups $S_N\subset G\subset S_N^+$ correspond to tensor categories $\spn(NC)\subset\mathcal C\subset\spn(P)$, made of linear combinations of partitions. Given such a $\mathcal C$, we look at the first level $k$ where it differs from $\spn(NC)$, and we write down linear, quadratic and cubic necessary conditions on the new vectors at level $k$, which we then solve by exact computer algebra, uniformly in $N$ whenever possible. This is our main contribution, developed in Sections~\ref{sec:method}, \ref{sec:six} and~\ref{sec:higher}. \smallskip The maximality conjecture has some interesting ramifications, which we discuss as well: \smallskip (A) \emph{Orthogonal case.} Inside Wang's free orthogonal group $O_N^+$ we have the half-liberation $O_N\subset O_N^*\subset O_N^+$, given by the relations $abc=cba$, and $O_N\subset O_N^*$ is known to be maximal~\cite{bbcc}. The conjecture here is that this chain is complete, in the sense that $O_N^*$ is the only intermediate quantum group $O_N\subsetneq G\subsetneq O_N^+$. We discuss this in Sections~\ref{sec:orthproblem} and~\ref{sec:pairings}, by adapting the above approaches (1) and (3), with group duals and twists as seeds, and with pairings in place of partitions. \smallskip (B) \emph{Projective versions.} For the projective versions $PO_N\subset H\subset(PO_N^+=PU_N^+)$, it is known that $PO_N^*=PU_N$ is the unique intermediate projectively easy quantum group~\cite{bme}, and conjecturally it is the unique intermediate quantum group. The new feature here is that $H$ is not necessarily the projective version of a quantum group $O_N\subset G\subset O_N^+$, and the level method must be adapted to this, with fewer symmetries. We discuss these questions in Section~\ref{sec:related}. \smallskip Our main results concern approach (3). The computations behind them are exact, and organized as certificates which can be checked independently, as explained in Section~\ref{sec:method}. First, the conjecture holds up to level $7$: \begin{introtheorem} Let $N\ge6$, and $S_N\subsetneq G\subset S_N^+$. Then for any $k\le7$ we have \[ \Fix_G(u^{\otimes k})=\spn\big\{\xi_\pi:\pi\in NC(k)\big\}. \] Thus the first seven moments of the main character of $G$ are the Catalan numbers, as for $S_N^+$. \end{introtheorem} The study of the conjecture level by level goes back to~\cite{bah}, where the notion of easiness level was introduced, and was substantially developed by McCarthy, whose state-space approach to quantum permutations~\cite{mc0} led him to the program in~\cite{mc1,mc2}, with a number of results at levels $\le6$. Levels $k\le5$ were also announced by Freslon and Speicher~\cite{fs}, and we reprove them. Levels $6$ and $7$ are new, with a proof uniform in $N$. At level $8$ the method meets real resistance, but still gives a strong structural result: \begin{introtheorem} Let $7\le N\le37$, and let $S_N\subsetneq G\subset S_N^+$ first differ from $S_N^+$ at level $8$. Then the elements of $\Fix_G(u^{\otimes8})$ are, modulo $\spn(NC(8))$, invariant under the rotation of the $8$ legs by $4$ positions. \end{introtheorem} Pushing the rotation symmetry further, we can close level $8$ computationally, modulo primes, at each $8\le N\le37$: for these $N$ the conjecture holds up to level $8$ (Section~\ref{sec:higher}). Level $9$ is harder, with a kernel of dimension $307$ against $66$, and no half-turn. There a different tool, imported from the orthogonal problem of Section~\ref{sec:pairings}, does the job: the candidates split into nine rotation blocks, each of them has a real form, and a positive definite combination of the quadratic constraints on each real form excludes the whole block, by a certificate. This closes level $9$, numerically, at $N=9,\dots,13$ and $N=17,19,23$, so that at these $N$ the conjecture holds through level $9$ (Theorem~\ref{thm:nine}), the highest level reached so far. Regarding approach (1), among our results is the following statement about graphs, where $G^+(X)$ denotes the quantum automorphism group of a graph $X$, and where the repetition lemma states that $\langle S_{4m},S_4^+\rangle=S_{4m}^+$, with $S_4^+$ acting on $4m$ points via $u\mapsto u\otimes1_m$: \begin{introtheorem} Let $X$ be a vertex-transitive graph with $N\le13$ vertices. Then \[ \langle S_N,G^+(X)\rangle\in\{S_N,S_N^+\}, \] except possibly for the cube, its complement, and four complementary pairs of graphs with $12$ vertices, where this holds provided that the repetition lemma mentioned above holds at $m=2,3$. \end{introtheorem} In the orthogonal case, a generation result of Brannan, Collins and Vergnioux~\cite{bcv}, namely $\langle O_N,O_{N-1}^+\rangle=O_N^+$ for $N\ge4$, allows an induction on $N$ which stops at $N=3$, where their method breaks down. Our main results concern the anticommutative twist $O_N^{-1}$, and the levels of $O_N^*\subset G\subset O_N^+$: \begin{introtheorem} $\langle O_N,O_N^{-1}\rangle$ agrees with $O_N^+$ up to level $\max(20,2N)$, and equals $O_N^+$ for all $N$, provided that $\langle O_3,O_2^+\rangle=O_3^+$. \end{introtheorem} So the twist problem reduces to the single generation statement at $N=3$ left open in~\cite{bcv}, which we verify up to level $20$. As for the levels themselves, the orthogonal version of approach (3), with uncappable vectors and positivity certificates, gives: \begin{introtheorem} Let $N\ge3$, and $O_N^*\subset G\subsetneq O_N^+$. If the fixed vectors of $G$ differ from those of $O_N^+$ at some level $\le10$, then $G=O_N^*$. \end{introtheorem} Many questions remain open, and they are stated along the way, at their natural places. The main problem, of course, is that of going beyond level $9$ in approach (3), and beyond level $7$ uniformly in $N$, and here the main difficulty is computational. \smallskip \noindent\emph{Acknowledgments.} We would like to thank JP McCarthy for useful discussions. %====================================================================== % Section: maximality %====================================================================== \section{Maximality and three approaches}\label{sec:maximality} \subsection{Quantum permutation groups} Let $N\in\mathbb N$. A \emph{magic unitary} is a square matrix $u=(u_{ij})\in M_N(A)$ over a $C^*$-algebra $A$ whose entries are projections summing to $1$ on each row and each column. Wang showed~\cite{wa} that the universal $C^*$-algebra \[ C(S_N^+)=C^*\Big((u_{ij})_{i,j=1,\dots,N}\ \Big|\ u=\text{magic}\Big), \] with comultiplication $\Delta(u_{ij})=\sum_ku_{ik}\otimes u_{kj}$, counit $\varepsilon(u_{ij})=\delta_{ij}$ and antipode $S(u_{ij})=u_{ji}$, defines a compact quantum group $S_N^+$ in the sense of Woronowicz~\cite{wo1}, the \emph{quantum permutation group}. It is the universal compact quantum group acting on the set $\{1,\dots,N\}$, in the sense that it is the quantum automorphism group of the algebra $\C^N$ endowed with its uniform trace. The commutative quotient of $C(S_N^+)$ is $C(S_N)$, with $u_{ij}$ mapping to the characteristic function of $\{\sigma:\sigma(j)=i\}$. So we have an inclusion of compact quantum groups \[ S_N\subset S_N^+ . \] \emph{Small $N$.} For $N=1,2,3$ the entries of a magic unitary automatically commute, and $S_N^+=S_N$~\cite{wa}. At $N=4$ things change: $C(S_4^+)$ is infinite-dimensional. A good model comes from the Pauli matrices. The magic unitary whose entries are the rank-one projections onto $c_ix c_j$, with $x\in SU_2$ and $c_1,\dots,c_4$ the Pauli matrices, gives a faithful representation $C(S_4^+)\to M_4(C(SU_2))$. This can be used to integrate over $S_4^+$ \cite{bc}. In fact $S_4^+=SO_3^{-1}$, a twist of $SO_3$, and all the quantum subgroups of $S_4^+$ can be classified this way~\cite{bb}. For $N\ge5$, $S_N^+$ is not coamenable. One way to see it is that it contains the dual of $\Z_2*\Z_3$, which is a non-amenable group, acting by Fourier matrices on $2+3$ of the $N$ points. The liberation operation $S_N\to S_N^+$ is best understood in representation theory terms, and more specifically in the context of the easy quantum groups introduced in~\cite{bsp}. In order to explain this, let us start with: \emph{Conventions.} We write $P(k)$ and $NC(k)$ for the sets of partitions and noncrossing partitions of $\{1,\dots,k\}$, and \[ B_k=|P(k)|,\qquad C_k=|NC(k)|=\frac{1}{k+1}\binom{2k}{k} \] for the Bell and Catalan numbers. Thus $B_0,B_1,B_2,\dots$ are 1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, \dots, and $C_0,C_1,C_2,\dots$ are 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, \dots, the two sequences starting to differ at $k=4$, because of the basic crossing. Scalar products are linear in the first variable: $\langle x,y\rangle=\sum_ix_i\bar y_i$ on $\C^N$, $\langle a,b\rangle=\mathrm{tr}(ab^*)$ on matrix algebras, and $\langle a,b\rangle=h(b^*a)$ on $L^2(G)$, with $h$ the Haar state. Thus the matrix of an operator $T$ in an orthonormal basis is $T_{ij}=\langle Te_j,e_i\rangle$, and $\Proj(\xi)=\langle\cdot,\xi\rangle\xi/\|\xi\|^2$ is the orthogonal projection onto $\C\xi$. A dimension sequence is called ``Catalan'' through level $k$ when it agrees with $C_l$ for all $l\le k$. Statements resting on computer calculations are marked as such in their headers (\emph{exact}, \emph{computational}, \emph{numerical}), and Section~\ref{sec:certify} explains how the exact ones are certified. \medskip \emph{Representation theory.} For any $N\ge4$, the irreducible representations of $S_N^+$ follow the same fusion rules as those of $SO_3$~\cite{ba}. Their intertwiners are described by partitions, as follows. Let $P(k,l)$ be the set of partitions of $k$ upper legs and $l$ lower legs, and $NC(k,l)\subset P(k,l)$ the set of noncrossing ones. Each $\pi\in P(k,l)$ gives a linear map $T_\pi:(\C^N)^{\otimes k}\to(\C^N)^{\otimes l}$, defined by \[ T_\pi(e_{i_1}\otimes\dots\otimes e_{i_k})=\sum_{j_1,\dots,j_l}\delta_\pi\binom{i_1\dots i_k}{j_1\dots j_l}\,e_{j_1}\otimes\dots\otimes e_{j_l}, \] where $e_1,\dots,e_N$ is the standard basis of $\C^N$, and where $\delta_\pi=1$ if $\pi\le\ker\binom{i}{j}$, and $\delta_\pi=0$ otherwise. Here $\ker\binom{i}{j}$ is the partition of the $k+l$ legs obtained by joining two legs when they carry the same index, and $\pi\le\ker\binom{i}{j}$ means that each block of $\pi$ is contained in a block of $\ker\binom{i}{j}$, that is, the indices are constant on the blocks of $\pi$. With this notation, we have \[ \mathrm{Hom}_{S_N^+}(u^{\otimes k},u^{\otimes l})=\mathrm{span}\big\{T_\pi:\pi\in NC(k,l)\big\}, \] while for $S_N$ one gets the span of all the $T_\pi$ with $\pi\in P(k,l)$. By Woronowicz's Tannaka--Krein duality~\cite{wo2}, the intermediate quantum groups $S_N\subset G\subset S_N^+$ therefore correspond to the tensor categories $\mathcal C$ with \[ \mathrm{span}(NC)\subset\mathcal C\subset\mathrm{span}(P). \] Here $\mathcal C$ is allowed to contain arbitrary \emph{linear combinations} of partitions, not just partitions themselves. \emph{Easiness.} A closed subgroup $S_N\subset G\subset O_N^+$ is called \emph{easy} when its intertwiner spaces are spanned by partitions, in the sense that there are sets $D(k,l)\subset P(k,l)$ such that \[ \mathrm{Hom}_G(u^{\otimes k},u^{\otimes l})=\mathrm{span}\big\{T_\pi:\pi\in D(k,l)\big\}. \] The axioms of tensor categories translate into the fact that $D$ is a \emph{category of partitions}: it is stable under horizontal and vertical concatenation and under upside-down turning, and it contains the identity and the semicircle~\cite{bsp}. The basic examples are $O_N\subset O_N^+$, coming from all pairings and noncrossing pairings, $S_N\subset S_N^+$, coming from all partitions and noncrossing partitions, and the hyperoctahedral and bistochastic versions $H_N\subset H_N^+$ and $B_N\subset B_N^+$, coming from partitions with blocks of even size, and from singletons and pairings. In each case the liberation operation simply removes the crossings. See~\cite{bcs,rw} for the orthogonal classification, and~\cite{tw} for the unitary case. The easy quantum groups $S_N\subset G\subset S_N^+$ correspond to the categories of partitions $NC\subset D\subset P$, and these are easy to classify: a crossing partition, together with $NC$, generates all of $P$, so $D\in\{NC,P\}$. Thus $S_N^+$ is the only easy quantum group strictly containing $S_N$ inside $S_N^+$~\cite{bcs}. \subsection{The conjecture} The classification of the quantum subgroups of $S_4^+$ in~\cite{bb} contains no quantum group strictly between $S_4$ and $S_4^+$. This led Banica and Bichon to the following statement. \begin{conjecture}[maximality]\label{conj:max} For every $N$, the inclusion $S_N\subset S_N^+$ is maximal: there is no compact quantum group $G$ with $S_N\subsetneq G\subsetneq S_N^+$. \end{conjecture} \emph{Status.} The conjecture holds trivially for $N\le3$, and it holds for $N=4$ by~\cite{bb}. The case $N=5$ was settled in~\cite{bah}, using Jones' theory of subfactors~\cite{jo1} and the classification of subfactors of index at most $5$ and exactly $5$~\cite{imps,jms}. For $N\ge6$ it is open. \emph{Three approaches.} As explained in the introduction, there are three natural approaches to the conjecture. The first one is via subgroups: given a non-classical $G\subset S_N^+$, decide whether $\langle S_N,G\rangle=S_N^+$. This is the natural source of counterexamples, and it is the subject of Sections~\ref{sec:duals}--\ref{sec:hadamard}. The second one is via exotic quantum groups: develop the theory of a hypothetical $S_N\subsetneq G\subsetneq S_N^+$, with the hope of reaching a contradiction, as in Section~\ref{sec:exotic}. The third one is via partitions: work directly with the categories $\spn(NC)\subset\mathcal C\subset\spn(P)$, level by level, as in~\cite{bah,mc2}. This is our main approach, developed in Sections~\ref{sec:method}--\ref{sec:higher}. \emph{Ramifications.} The same question makes sense in the orthogonal case. Inside Wang's free orthogonal group $O_N^+$~\cite{wa95}, the half-liberated orthogonal group $O_N^*$, defined by the relations $abc=cba$, fits into \[ O_N\subset O_N^*\subset O_N^+ , \] and $O_N\subset O_N^*$ is known to be maximal~\cite{bbcc}. The conjecture is that $O_N^*$ is the only intermediate object, i.e.\ that this chain is complete. There are unitary and projective versions as well. As in the permutation case, all of this lies beyond easiness. These questions are discussed in Sections~\ref{sec:orthproblem}--\ref{sec:related}. %====================================================================== % Section: groupduals %====================================================================== \section{Group duals and Fourier families}\label{sec:duals} \subsection{Group duals in $S_N^+$, after Bichon}\label{sec:bichon} \paragraph{Conventions.} A closed subgroup $G\subset S_N^+$ acts on $C(X)=\C^N$ by $\alpha(e_j)=\sum_ie_i\otimes u_{ij}$, and its fixed vectors at level $k$ are \[ \Fix_G(u^{\otimes k})=\{\xi:u^{\otimes k}(\xi\otimes1)=\xi\otimes1\},\qquad (u^{\otimes k})_{i_1\dots i_k,j_1\dots j_k}=u_{i_1j_1}\cdots u_{i_kj_k}. \] For $\pi\in P(k)$ we use the vector $\xi_\pi=T_\pi$, with $\pi$ viewed as an element of $P(0,k)$, having no upper legs. In practice, this means \[ \xi_\pi=\sum_{i:\,\pi\le\ker i}e_{i_1}\otimes\dots\otimes e_{i_k}, \] where $\ker i$ is the partition of $\{1,\dots,k\}$ obtained by joining two legs when they carry the same index, so that the sum is over the multi-indices $i$ which are constant on the blocks of $\pi$. We have $\Fix_{S_N}(u^{\otimes k})=\spn\{\xi_\pi:\pi\in P(k)\}$, and, for $N\ge4$, $\Fix_{S_N^+}(u^{\otimes k})=\spn\{\xi_\pi:\pi\in NC(k)\}$, of dimension $C_k$. Given two closed subgroups $H,K\subset S_N^+$, we denote by $\langle H,K\rangle$ the smallest closed subgroup of $S_N^+$ containing both. In Tannakian terms, $G=\langle H,K\rangle$ corresponds to the intersection of the categories, \[ \mathcal C_G=\mathcal C_H\cap\mathcal C_K, \] where $\mathcal C_G$ denotes the tensor category of intertwiners of $G$. Since $u$ is self-conjugate, the intertwiner spaces are determined by the fixed vectors, and so the quantity to compute, for a given $G\subset S_N^+$, is \[ \Fix_{\langle S_N,G\rangle}(u^{\otimes k})=\Fix_G(u^{\otimes k})\cap\spn\{\xi_\pi:\pi\in P(k)\}. \] This space contains $\Fix_{S_N^+}(u^{\otimes k})$, and for $N\ge4$ we have $\langle S_N,G\rangle=S_N^+$ if and only if its dimension is $C_k$ for every $k$. For a group dual, $C(\widehat\Gamma)=C^*(\Gamma)$ with $\Delta(g)=g\otimes g$. An embedding $\widehat\Gamma\subset S_N^+$ is given by a magic unitary $u$ with coefficients $u_{ij}\in C^*(\Gamma)$, satisfying $\Delta(u_{ij})=\sum_ku_{ik}\otimes u_{kj}$. We always assume that the coefficients $u_{ij}$ generate $C^*(\Gamma)$, which means that the morphism $C(S_N^+)\to C^*(\Gamma)$ is surjective, so that $\widehat\Gamma$ is a closed quantum subgroup of $S_N^+$. This is no loss of generality: in general, the $u_{ij}$ generate $C^*(\Gamma_0)$ for a subgroup $\Gamma_0\subset\Gamma$, and we can replace $\Gamma$ by $\Gamma_0$. The quantum subgroups of $\widehat\Gamma$ are the $\widehat\Lambda$ for quotients $\Gamma\to\Lambda$, and $\widehat\Gamma$ is classical iff $\Gamma$ is abelian. \paragraph{Bichon's theorem.} A coaction of $\C[\Gamma]$ on $\C^N$ is the same thing as a $\Gamma$-grading $\C^N=\bigoplus_gA_g$, where $A_g=\{a:\alpha(a)=a\otimes g\}$. In this language, Bichon proved the following~\cite[Prop.~5.2, Cor.~5.3]{bi}: \begin{itemize} \item an ergodic grading of $\C^m$ comes from a transitive abelian permutation group; \item consequently, $\widehat\Gamma\subset S_N^+$ iff $\Gamma$ is a quotient of $G_1*\dots*G_k$, where the $G_i\subset S_{m_i}$ are transitive abelian groups and $\sum m_i=N$. \end{itemize} Since transitive abelian groups act regularly, $G_i$ can be any finite abelian group, with $m_i=|G_i|$. We restate Bichon's result in the form used below, with explicit matrices. \begin{definition}[Fourier families]\label{def:family} A \emph{Fourier family} for $\Gamma$ is a family $\mathcal H=(H_1,\dots,H_k)$ of finite abelian subgroups of $\Gamma$ that generate $\Gamma$. Repetitions and trivial subgroups are allowed. Its size is $N=\sum_i|H_i|$. The family acts on the points \[ X_{\mathcal H}=\widehat H_1\sqcup\dots\sqcup\widehat H_k \] through the magic unitary $u^{\mathcal H}=\bigoplus_iu^{(i)}$, where \[ u^{(i)}_{\chi\psi}=P^{(i)}_{\chi\bar\psi},\qquad P^{(i)}_\rho=\frac1{|H_i|}\sum_{h\in H_i}\rho(h)\,h\qquad(\chi,\psi,\rho\in\widehat H_i). \] Equivalently, $u^{(i)}=F_i\,\mathrm{diag}(h)_{h\in H_i}\,F_i^*$, where $F_i$ is the normalized Fourier matrix of $H_i$, given by $(F_i)_{\chi h}=\chi(h)/\sqrt{|H_i|}$. \end{definition} \begin{theorem}[Bichon, restated]\label{thm:bichon} For a Fourier family $\mathcal H$, the matrix $u^{\mathcal H}$ defines a closed quantum subgroup $\widehat\Gamma\subset S_N^+$. Conversely, every closed quantum subgroup $\widehat\Gamma\subset S_N^+$ is conjugate by a permutation to $u^{\mathcal H}$, for a unique unordered family $\mathcal H$. Here $H_i$ is the support of the grading restricted to the $i$-th orbit. \end{theorem} \begin{proof}[Comments] The direct statement is a short computation. The $P_\rho$ are the minimal projections of $\C[H_i]$, rows and columns of $u^{(i)}$ are permutations of $\{P_\rho\}_\rho$, and $\Delta(u_{\chi\psi})=\sum_\eta u_{\chi\eta}\otimes u_{\eta\psi}$ follows from orthogonality of characters. The converse is in~\cite{bi}. The only point to add is the explicit identification. On an orbit $O$ with grading support $H$, each $A_h\cap C(O)$ is spanned by a nowhere-vanishing function $v_h$. Normalizing $v_h(x_0)=1$ at a base point gives $v_hv_k=v_{hk}$. Then $x\mapsto(h\mapsto v_h(x))$ is a bijection $O\simeq\widehat H$ which turns the action into the Fourier block. The $H_i$ are intrinsic, being the supports of the grading, so they are invariants under conjugation by $S_N$. A change of base point translates $\widehat H_i$. \end{proof} \begin{remark} Up to relabeling the points, \emph{actions of $\widehat\Gamma$ on $N$ points are exactly Fourier families of size $N$}. This is the right parametrization for our purposes, since $\langle S_N,G\rangle$ is invariant under conjugation by $S_N$. \end{remark} \begin{example}\label{ex:blocks} \begin{itemize} \item $H=\Z_2=\langle g\rangle$: $u=M(p)=\begin{pmatrix}p&1-p\\1-p&p\end{pmatrix}$ with $p=\frac{1+g}2$. \item $H=\Z_n=\langle g\rangle$: $u$ is the circulant matrix built on the spectral projections of $g$. This is the cyclic case. \item $H=\{e,a,b,c\}\simeq\Z_2^2$, the Klein block. Writing $P_x$ for the projection of the character with kernel $\{e,x\}$ (and $P_e=\frac14(e+a+b+c)$), we get \[ u=\begin{pmatrix}P_e&P_a&P_b&P_c\\P_a&P_e&P_c&P_b\\P_b&P_c&P_e&P_a\\P_c&P_b&P_a&P_e\end{pmatrix}. \] In general, the pattern of $u^{(i)}$ is the division table $(\chi,\psi)\mapsto\chi\psi^{-1}$ of $\widehat H_i$, which is circulant for $\Z_n$, and is not circulant here. \end{itemize} \end{example} \paragraph{Notation used throughout.} \begin{itemize} \item \emph{Fourier basis.} $f_{(i,h)}\in C(X_{\mathcal H})$, for $h\in H_i$, is the function $\chi\mapsto\chi(h)$ on $\widehat H_i$, extended by $0$. These are orthogonal, $\|f_{(i,h)}\|^2=|H_i|$, and $u(f_{(i,h)}\otimes1)=f_{(i,h)}\otimes h$. \item \emph{Labelings.} A labeling of $k$ legs is $a=((i_1,h_1),\dots,(i_k,h_k))$ with $h_l\in H_{i_l}$. Write $f_a=\bigotimes_lf_{(i_l,h_l)}$, and $w(a)=h_1\cdots h_k\in\Gamma$ for its \emph{word} (ordered product). \item \emph{Standard tori.} For finite abelian groups $\mathcal H=(H_1,\dots,H_k)$, the standard torus is $T_{\mathcal H}=\widehat{H_1*\dots*H_k}$ with its tautological family. \end{itemize} \begin{lemma}[quotients]\label{lem:quotient} Let $q:\Gamma\to\Lambda$ be a quotient. Then $\widehat\Lambda\subset\widehat\Gamma$ acts on the same points, and its family is obtained as follows. Each orbit $\widehat H_i$ splits into $|\ker(q_{|H_i})|$ orbits, namely the cosets of $q(H_i)^\wedge\subset\widehat H_i$. Each of the new orbits carries the subgroup $q(H_i)$. \end{lemma} \begin{proof} The $\Lambda$-grading is $f_{(i,h)}\mapsto q(h)$. Its identity component on $\widehat H_i$ consists of the functions constant on cosets of $\ker(q_{|H_i})^\perp=q(H_i)^\wedge$. \end{proof} \begin{example} Sending $\Z_4\to\Z_2$ in $\Z_4*\Z_2$ turns the $4$-point orbit into two $2$-point orbits with the same subgroup, i.e.\ $u=\mathrm{diag}(M(p),M(p),M(q))$. \end{example} %===================================================================== \subsection{Reduction to just-non-abelian groups}\label{sec:jna} We first record two simple principles, valid for arbitrary closed subgroups $G\subset S_N^+$. We say that $G$ \emph{moves at most $M$ points} if, up to a permutation of the coordinates, its magic unitary has the form $u=v\oplus1_{N-M}$, with $v$ of size $M$. \begin{proposition}[monotonicity and locality]\label{prop:monloc} Let $G\subset S_N^+$ be a closed subgroup, with $N\ge4$. \begin{enumerate} \item If $K\subset G$ is a closed subgroup, then $\langle S_N,K\rangle\subset\langle S_N,G\rangle$. In particular, if $\langle S_N,K\rangle=S_N^+$, then $\langle S_N,G\rangle=S_N^+$. \item If $G$ has a non-classical closed subgroup $K$ which moves at most $5$ points, then $\langle S_N,G\rangle=S_N^+$. \end{enumerate} \end{proposition} \begin{proof} (1) This is clear from the definition of $\langle\,\cdot\,,\cdot\,\rangle$. (2) Since $\langle S_N,\sigma G\sigma^{-1}\rangle=\sigma\langle S_N,G\rangle\sigma^{-1}$ for $\sigma\in S_N$, we can assume that $K$ moves only the first $M\le5$ points, so that $K\subset S_M^+$, embedded in $S_N^+$ by fixing the last $N-M$ points. As $K$ is not classical and $S_M^+=S_M$ for $M\le3$, we have $M\in\{4,5\}$. The maximality of $S_M\subset S_M^+$ for $M=4,5$, from~\cite{bah,bb}, gives $\langle S_M,K\rangle=S_M^+$. Since $S_M\subset S_N$, we obtain $S_M^+\subset\langle S_N,G\rangle$, and so $\langle S_N,G\rangle\supset\langle S_N,S_M^+\rangle=S_N^+$, by~\cite[Cor.~3.4]{bcf} for $N\ge5$, and trivially for $N=4$. \end{proof} For a group dual $\widehat\Gamma\subset S_N^+$, given by a Fourier family $\mathcal H=(H_1,\dots,H_k)$, the closed quantum subgroups are the duals $\widehat\Lambda$ of the quotients $q:\Gamma\to\Lambda$. By Lemma~\ref{lem:quotient}, $\widehat\Lambda$ moves exactly the points of the orbits $\widehat H_i$ with $q(H_i)\ne1$, so their number is $\sum_{q(H_i)\ne1}|H_i|$. Thus, by monotonicity, we are led to look for small quotients of $\Gamma$ which are still non-abelian. This suggests the following notion. \begin{definition} A group $\Gamma$ is called \emph{just-non-abelian} (JNA) if it is non-abelian, and all its proper quotients are abelian. Equivalently, since $\Gamma/K$ is abelian if and only if $K\supset\Gamma'$, where $\Gamma'=[\Gamma,\Gamma]$ is the derived subgroup, $\Gamma$ is JNA when $\Gamma'\ne1$, and every nontrivial normal subgroup of $\Gamma$ contains $\Gamma'$. \end{definition} \begin{lemma}\label{lem:zorn} Every non-abelian finitely generated group has a JNA quotient. \end{lemma} \begin{proof} Let $\Gamma=\langle g_1,\dots,g_n\rangle$. A normal subgroup $K\subset\Gamma$ gives a non-abelian quotient $\Gamma/K$ if and only if $[g_a,g_b]\notin K$ for some pair $(a,b)$. The set of such normal subgroups contains $\{1\}$, and is inductive. Indeed, given a chain $(K_t)$ of such subgroups, since there are finitely many pairs, there is a pair $(a,b)$ with $[g_a,g_b]\notin K_t$ for cofinally many $t$, and hence for all $t$, so that $[g_a,g_b]\notin\bigcup_tK_t$. By Zorn's lemma we obtain a maximal such $K$, and then $\Gamma/K$ is JNA. \end{proof} \begin{proposition}\label{prop:reduction} Let $N\ge4$. If $\langle S_N,\widehat\Lambda\rangle=S_N^+$ for all JNA groups $\Lambda$ and all their Fourier families of size $N$, then $\langle S_N,\widehat\Gamma\rangle=S_N^+$ for all non-classical group duals $\widehat\Gamma\subset S_N^+$. Moreover, when $\Gamma$ is residually finite, for instance a free product of finite abelian groups, as for the standard tori $T_{\mathcal H}$, the JNA quotient $\Lambda$ used for $\widehat\Gamma$ can be chosen finite. \end{proposition} \begin{proof} Let $\widehat\Gamma\subset S_N^+$ be non-classical, given by a Fourier family $\mathcal H=(H_1,\dots,H_k)$. Then $\Gamma$ is non-abelian, and finitely generated, by the finite subgroups $H_i$. By Lemma~\ref{lem:zorn}, it has a JNA quotient $q:\Gamma\to\Lambda$. The quantum group $\widehat\Lambda\subset\widehat\Gamma$ acts on the same $N$ points, through the family $(q(H_1),\dots,q(H_k))$ split as in Lemma~\ref{lem:quotient}, which generates $\Lambda$. By assumption $\langle S_N,\widehat\Lambda\rangle=S_N^+$, and so $\langle S_N,\widehat\Gamma\rangle=S_N^+$, by monotonicity. If $\Gamma$ is residually finite, pick generators $g_a,g_b$ with $[g_a,g_b]\ne1$, and a normal subgroup $K_0$ of finite index not containing $[g_a,g_b]$. Then $\Gamma/K_0$ is finite and non-abelian, and applying Lemma~\ref{lem:zorn} to it gives a finite JNA quotient of $\Gamma$. Finally, free products of finite groups are residually finite. \end{proof} The finite JNA groups are well known, and can be described as follows. \begin{proposition}\label{prop:jna} A finite group $\Gamma$ is JNA if and only if $\Gamma'\ne1$ is its unique minimal normal subgroup. This happens if and only if $\Gamma$ belongs to one of the following three classes, which are mutually exclusive: \begin{enumerate}[label=(\alph*)] \item \emph{Central type:} $\Gamma$ is a $p$-group with $|\Gamma'|=p$ and cyclic center. \item \emph{Affine type:} $\Gamma=\F_p^m\rtimes A$, with $A\subset\F_{p^m}^\times$ a nontrivial subgroup not contained in a proper subfield, acting by multiplication. \item \emph{Non-abelian type:} $\Gamma'\simeq T^m$ with $T$ non-abelian simple, $\Gamma'$ is a minimal normal subgroup of $\Gamma$, and its centralizer is trivial, $C_\Gamma(\Gamma')=1$. \end{enumerate} \end{proposition} \begin{proof} If $\Gamma$ is JNA, every minimal normal subgroup contains $\Gamma'\ne1$, hence equals it. Conversely, if $\Gamma'\ne1$ is the unique minimal normal subgroup, every nontrivial normal subgroup contains it. As for the classification, the solvable case goes back to Newman~\cite{ne1,ne2}, and the general case, including the non-solvable one, is treated by Jain and Shukla~\cite{js}, who also review Newman's results. In any case the argument is short. $V=\Gamma'$ is a minimal normal subgroup, so $V\simeq T^m$ with $T$ simple. If $V$ is central, all subgroups of $Z(\Gamma)$ contain $V$, and $\Gamma$ is nilpotent, which leads to (a). If $V=\F_p^m$ is not central, the abelian group $\Gamma/C_\Gamma(V)$ acts faithfully and irreducibly on $V$, so it embeds in $\F_{p^m}^\times$ by Schur's lemma, and a coprime action argument gives $C_\Gamma(V)=V$, which leads to (b). If $V$ is non-abelian, $C_\Gamma(V)$ is normal and meets $V$ trivially, so it is trivial, which is (c). The converse is a direct check. \end{proof} \begin{example}\label{ex:jna} Here are some examples of finite JNA groups. \begin{enumerate}[label=(\alph*)] \item The dihedral group $D_4$ of order $8$, the quaternion group $Q_8$, the extraspecial groups $p^{1+2n}_\pm$, and the Pauli groups $\Z_4\circ2^{1+2n}$. \item The groups $S_3$, $A_4=\F_2^2\rtimes\Z_3$, the dihedral groups $D_p=\F_p\rtimes\Z_2$ with $p$ odd prime, and $\F_7\rtimes\Z_3$, $\F_5\rtimes\Z_4$. \item The non-abelian simple groups, the symmetric groups $S_n$ with $n\ge5$, the groups $PGL_2(q)$ with $q\ge4$, and the wreath products $T\wr\Z_m$, with $T$ non-abelian simple. \end{enumerate} In case (c), the minimality of $\Gamma'$ cannot be dropped. For instance $\Gamma=A_5\times A_5$ satisfies $\Gamma'\simeq A_5^2$ and $C_\Gamma(\Gamma')=1$, but it is not JNA, having $A_5$ as a quotient. \end{example} For group duals, being JNA has the following consequence. Given a Fourier family $\mathcal H=(H_1,\dots,H_k)$, we denote by $n(\mathcal H)=\sum_{H_i\ne1}|H_i|$ the number of points moved by the corresponding action. \begin{corollary}[locality for JNA groups]\label{cor:jnaloc} Let $\Gamma$ be JNA, and $\widehat\Gamma\subset S_N^+$ be given by a Fourier family $\mathcal H$. Then $\widehat\Gamma$ is its only non-classical closed quantum subgroup. Thus Proposition~\ref{prop:monloc}~(2) applies to $\widehat\Gamma$ if and only if $n(\mathcal H)\le5$. \end{corollary} \begin{proof} The closed quantum subgroups of $\widehat\Gamma$ are the duals of the quotients of $\Gamma$, and the proper quotients are abelian, with classical duals. The second assertion follows, the number of points moved by $\widehat\Gamma$ being $n(\mathcal H)$. \end{proof} Observe that $n(\mathcal H)$ counts all the nontrivial blocks of $\mathcal H$, even when some of them already generate $\Gamma$: the family $(\langle(12)\rangle,\langle(23)\rangle,\langle(13)\rangle)$ of $S_3$ has $n(\mathcal H)=6$, and is not covered by locality. So what remains to be tested are the JNA groups with Fourier families having $n(\mathcal H)\ge6$, and all three classes occur below. In class (a) we will meet $D_4$, $Q_8$, $3^{1+2}_+$, and the magic square group $2^{1+4}_+$ of Proposition~\ref{prop:magic}. In class (b) we will meet $S_3$, $A_4$, $D_5$ and $\F_7\rtimes\Z_3$, see Example~\ref{ex:table}. In class (c) we will meet $A_7$, as the JNA quotient of the solution group $3.A_7$ of~\cite{drs}, acting on $210$ points, see Proposition~\ref{prop:a7}. Class (c) has much smaller actions as well, for instance $A_5$ acting on $6$ points through the family $(\langle(123)\rangle,\langle(345)\rangle)$, see Proposition~\ref{prop:classc}. %===================================================================== \subsection{The laws lemma for abelian blocks}\label{sec:laws} Fix a Fourier family $\mathcal H$ for $\Gamma$, and use the notation of Section~\ref{sec:bichon}. \begin{proposition}\label{prop:coords} \begin{enumerate} \item $\Fix_{\widehat\Gamma}(u^{\otimes k})=\spn\{f_a:w(a)=e\}$. \item Write $\xi_\pi=\sum_ac_\pi(a)f_a$. Then $c_\pi(a)\ne0$ iff each block $b$ of $\pi$ carries a single orbit index $i_b$ and satisfies $\prod_{l\in b}h_l=e$ in $H_{i_b}$. In that case $c_\pi(a)=\prod_{b\in\pi}|H_{i_b}|^{1-|b|}$. \end{enumerate} \end{proposition} \begin{proof} (1) $u^{\otimes k}(f_a\otimes1)=f_a\otimes w(a)$, and distinct group elements are linearly independent. (2) Use $e_{(i,\chi)}=|H_i|^{-1}\sum_h\overline{\chi(h)}f_{(i,h)}$ in $\sum_xe_x^{\otimes b}$, block by block, and then $\sum_\chi\chi(h)=|H_i|\delta_{h,e}$. \end{proof} \begin{definition} Two labelings are \emph{equivalent} if they differ by a bijection $\sigma$ of orbit indices together with isomorphisms $\theta_i:H_i\to H_{\sigma(i)}$ applied to the labels. A \emph{pattern} is an equivalence class. Concretely, a pattern consists of: \begin{itemize} \item the partition $\kappa$ of the legs by orbit; \item for each block of $\kappa$, an abelian isomorphism type with labels in it, up to automorphisms. \end{itemize} A pattern is \emph{balanced} if the labels multiply to $e$ in each block of $\kappa$. It is \emph{active} if some realization has $w(a)\ne e$. A balanced inactive pattern is a \emph{law}: an identity holding for all choices of distinct orbit subgroups of the given types, and all identifications. A pattern is \emph{freely trivial} if its words are trivial in the free product $H_1*\dots*H_k$, for all its realizations. For instance, on a single orbit, the labels $(h,h^{-1})$ give a freely trivial pattern. Freely trivial patterns are laws for every $\Gamma$, and we call the other laws \emph{nontrivial}. \end{definition} \begin{lemma}[laws lemma]\label{lem:laws} For $\xi\in\spn\{\xi_\pi\}$: \begin{enumerate} \item $c_\xi$ is constant on patterns and vanishes off balanced ones; \item $\xi\in\Fix_{\langle S_N,\widehat\Gamma\rangle}$ iff $c_\xi$ vanishes on all active patterns. \end{enumerate} Hence the joint intertwiner spaces depend only on the multiset of types of the $H_i$ and on the set of active patterns. \end{lemma} \begin{proof} The vectors $\xi_\pi$ are invariant under $S_N$. Three kinds of permutations act diagonally, up to phases, on the Fourier basis: \begin{itemize} \item translations of $\widehat H_i$, which multiply $f_{(i,h)}$ by $\overline{\psi(h)}$; these give balancedness; \item automorphisms of $H_i$; \item swaps of isomorphic orbits. \end{itemize} The last two generate the equivalence of labelings. Then apply Proposition~\ref{prop:coords}(1). \end{proof} \begin{corollary}\label{cor:laws} If $(\Gamma,\mathcal H)$ has no nontrivial laws with $\le k$ legs, then up to level $k$ the joint quantum group $\langle S_N,\widehat\Gamma\rangle$ has the same intertwiners as $\langle S_N,T_{\mathcal H}\rangle$. Indeed, in the torus $T_{\mathcal H}$ the laws are exactly the freely trivial patterns. \end{corollary} \begin{remark}\label{rem:laws} Thus, for group duals, the question becomes that of knowing \emph{which short balanced patterns are nontrivial laws}. If there are no nontrivial laws with $\le k$ legs, then $\widehat\Gamma$ behaves up to level $k$ like the standard torus, which is free in the relevant sense. So a counterexample to the conjecture should be looked for among JNA groups having many short nontrivial laws. \end{remark} %===================================================================== \subsection{First candidates}\label{sec:examples} \begin{example}\label{ex:table} The following are JNA groups with Fourier families of size $N\ge6$, so none of them is killed by locality. The list is illustrative, not exhaustive. \begin{center} \begin{tabular}{@{}llll@{}}\toprule $\Gamma$ & class & family & $N$\\\midrule $S_3$ & (b) & $\langle(12)\rangle,\langle(23)\rangle,\langle(13)\rangle$ & 6\\ $D_4$ & (a) & $\langle s\rangle,\ \langle r\rangle\simeq\Z_4$ & 6\\ $D_4$ & (a) & $\langle sr\rangle,\ \{1,r^2,s,sr^2\}$ (Klein) & 6\\ $A_4$ & (b) & $\langle(123)\rangle,\langle(234)\rangle$ & 6\\ $3^{1+2}_+$ & (a) & $\langle x\rangle,\langle y\rangle\simeq\Z_3$ & 6\\ $\F_7\rtimes\Z_3$ & (b) & two complements $\Z_3$ & 6\\ $D_5$ & (b) & $\langle s\rangle,\langle sr\rangle,\langle sr^2\rangle$ & 6\\ $A_4$ & (b) & $\langle(123)\rangle,\ V_4$ (Klein) & 7\\ $D_5$ & (b) & $\langle s\rangle,\ \langle r\rangle\simeq\Z_5$ & 7\\ $Q_8$ & (a) & $\langle i\rangle,\langle j\rangle\simeq\Z_4$ & 8\\ $D_4$ & (a) & $\{1,r^2,s,sr^2\},\ \{1,r^2,sr,sr^3\}$ (two Klein) & 8\\ $2^{1+4}_+$ & (a) & nine $\Z_2$'s (magic square) & 18\\\bottomrule \end{tabular} \end{center} \end{example} \subsection{Computations} \begin{remark}[method] The program \texttt{duals.py} works as follows. \begin{itemize} \item Input: a finite group $\Gamma$, given by permutations or matrices, together with a Fourier family. \item It enumerates the labelings that are balanced on each orbit and have nontrivial word. \item For each of them it computes the row $(c_\pi(a))_{\pi\in P(k)}$ given by Proposition~\ref{prop:coords}. \item It returns \[ \dim\Fix_{\langle S_N,\widehat\Gamma\rangle}(k)=\dim\spn\{\xi_\pi\}-\mathrm{rank}\,(c_\pi(a))_{a\ \mathrm{bad},\,\pi}, \] with the rank computed exactly modulo the prime $p=1048573$. Only the crossing columns are kept, the noncrossing ones vanishing identically, and the rank is computed after a random compression $M=RC$, which can only lower it. \end{itemize} \end{remark} \begin{remark}[validation] This computation was checked in several ways. \begin{itemize} \item It agrees with an independent dense computation, using the Haar projection in the regular representation, on four small cases at $k\le4$. These include a Klein block for $D_4$ at $N=6$ and for $A_4$ at $N=7$. \item It gives Bell numbers $2,5,15$ for the classical Klein group acting regularly on $4$ points, as it should. \item It reproduces $14,42$ for the magic square at $k=4,5$. \end{itemize} \end{remark} \begin{proposition}[exact]\label{prop:dualcomp} For the $11$ actions of Example~\ref{ex:table} other than the magic square, and for $k=4,5,6,7,8$, \[ \dim\Fix_{\langle S_N,\widehat\Gamma\rangle}(u^{\otimes k})=14,\ 42,\ 132,\ 429,\ 1430, \] the Catalan numbers. So none of them is a counterexample through level $8$. This covers classes (a) and (b), cyclic and Klein blocks, and families with three blocks on $6$ points. \end{proposition} Each run takes about a second for $k\le7$, and between $20$ and $40$ seconds for $k=8$. Although the ranks are computed modulo $p$, after a random compression, the result is exact. Indeed, the coefficients $c_\pi(a)$ are rational, with denominators products of the orders $|H_i|$, which are prime to $p$. Thus the rank modulo $p$, and a fortiori that of the compressed matrix, is at most the rank over $\Q$, so the computed dimension is an upper bound for the true one. On the other hand, the true dimension is at least $C_k$, because $\Fix_{S_N^+}(u^{\otimes k})$ is contained in it. So a Catalan output proves equality. Here $\dim\spn\{\xi_\pi\}$ must be taken exactly; for $k>N$ it is the number of partitions of $\{1,\dots,k\}$ with at most $N$ blocks. \subsection{Conclusions}\label{sec:dualsconcl} As a conclusion, in this section we used the group duals $\widehat\Gamma\subset S_N^+$ as seeds, in the search for a counterexample to the maximality conjecture of the form $S_N\subsetneq\langle S_N,\widehat\Gamma\rangle\subsetneq S_N^+$. Here is what we found. \emph{Structure.} By Bichon's theorem, the group duals in $S_N^+$ are exactly the Fourier families of finite abelian subgroups generating $\Gamma$. Non-cyclic orbits do occur, the simplest being the Klein block. \emph{Reductions.} By monotonicity and locality, it is enough to consider JNA groups, and their Fourier families moving at least $6$ points. These groups are well known, and come in three classes: central type (a), affine type (b), and non-abelian type (c). Moreover, by the laws lemma, the joint intertwiners only depend on which short balanced patterns are nontrivial laws, and a group dual with no nontrivial laws up to $k$ legs behaves up to level $k$ like the corresponding free torus. \emph{Computations.} The $11$ actions of Example~\ref{ex:table} from classes (a) and (b), with $N=6,7,8$ and including non-cyclic orbits, all give the Catalan numbers through level $8$. Thus, in all the cases we tested, $\widehat\Gamma$ is absorbed by $S_N$, as far as we can see, and no counterexample appears. Further group duals, coming from graphs, will appear in Section~\ref{sec:graphs}, with the same outcome. \emph{Outlook.} All this suggests the following statement, which would be of independent interest, independently of the maximality conjecture. \begin{conjecture}\label{conj:duals} For every non-classical group dual $\widehat\Gamma\subset S_N^+$ we have $\langle S_N,\widehat\Gamma\rangle=S_N^+$. \end{conjecture} By Proposition~\ref{prop:reduction}, it is enough to prove this for the JNA groups $\Gamma$, and their Fourier families with $n(\mathcal H)\ge6$. The evidence consists of the $11$ actions of Example~\ref{ex:table}, of the magic square group (class (a), $N=18$), of the four class (c) actions at $N=6$ of Proposition~\ref{prop:classc} below, and of $A_7$ (class (c), $N=210$, no laws of length $\le8$), all Catalan through level $8$. The natural tool is the laws lemma, which reduces everything to the question of which short balanced patterns are laws. Class by class the laws are known, being central of order $p$ for (a), and metabelian for (b). So a strategy would be to find, for classes (a) and (b) and at each level $k$, enough active patterns to kill all the crossing combinations, using the explicit coefficients $c_\pi(a)=\prod_b|H_{i_b}|^{1-|b|}$ of Proposition~\ref{prop:coords}. A first target is the case where all the blocks are $\Z_2$. On the computational side, the smallest actions of class (c) occur at $N=6$, and we have tested them as well. \begin{proposition}[exact]\label{prop:classc} For the following actions of class (c), with $N=6$, and for $k=4,5,6,7,8$, the dimensions $\dim\Fix_{\langle S_N,\widehat\Gamma\rangle}(u^{\otimes k})$ are the Catalan numbers $14,42,132,429,1430$: \begin{itemize} \item $A_5$ with $(\langle(123)\rangle,\langle(345)\rangle)\simeq(\Z_3,\Z_3)$; \item $A_5$ with three $\Z_2$'s, generated by $(23)(45)$, $(14)(25)$, $(12)(45)$; \item $A_5$ with $(\Z_2,\Z_2^2)$, given by $\langle(15)(23)\rangle$ and the Klein group on $\{1,2,3,4\}$; \item $S_5$ with $(\langle(1234)\rangle,\langle(45)\rangle)\simeq(\Z_4,\Z_2)$. \end{itemize} \end{proposition} This was computed with \texttt{duals.py}, as in Proposition~\ref{prop:dualcomp}, in about $20$ seconds per action at $k=8$. Class (c) groups have the fewest short laws, so by the laws lemma they should be the ``most free'', and this is what we find. As a continuation, it would be interesting to test $A_5$ at $N=7,8$, for instance with $(\Z_2,\Z_5)$, then $PSL_2(7)$, and so on. Note that $A_5$, being $(2,3)$-generated, also acts on $2+3=5$ points, but this action is absorbed by maximality at $N=5$, and says nothing about the actions on $6$ points. The computation is cheap, of the same size as those of Proposition~\ref{prop:dualcomp}. Finally, Proposition~\ref{prop:reduction} reduces the problem to the finite JNA groups only when $\Gamma$ is residually finite. This leads to the following question. \begin{question}\label{qu:infjna} Does every non-abelian group generated by finitely many finite abelian subgroups have a finite non-abelian quotient? If not, which infinite JNA groups occur as group duals in $S_N^+$, with $n(\mathcal H)\ge6$? \end{question} The standard tori $T_{\mathcal H}$ are free products of finite groups, hence residually finite, but their quotients need not be. An infinite simple group generated by finitely many finite abelian subgroups would be JNA, with no finite JNA quotient, and if such groups exist with only two or three small blocks, then their duals are test cases that no finite computation of the above type sees. Note, however, that an infinite simple quotient of $\Z_2*\Z_3$ would act on $5$ points only, and be absorbed. So the question really concerns the case $n(\mathcal H)\ge6$, and is mostly one of group theory. %====================================================================== % Section: graphs %====================================================================== \section{Quantum automorphisms of graphs}\label{sec:graphs} Recall that we are looking for seeds: non-classical quantum subgroups $K\subset S_N^+$, as small as possible, such that $\langle S_N,K\rangle$ might fail to be $S_N^+$. The group duals were the first natural family. The second one consists of the quantum automorphism groups of graphs, and of their quantum subgroups. \subsection{Quantum automorphism groups of graphs} Let $X$ be a finite graph with vertex set $\{1,\dots,N\}$ and adjacency matrix $A=A_X$. Its quantum automorphism group $G^+(X)\subset S_N^+$ is given by the relations $uA=Au$ on the fundamental magic unitary. Equivalently, it is the largest quantum subgroup of $S_N^+$ whose coaction on $C(X)=\C^N$ commutes with $A$, viewed as an operator on $C(X)$. Its classical version is the automorphism group $G(X)=G^+(X)\cap S_N$. The graph is said to have \emph{quantum symmetry} when $G^+(X)\ne G(X)$. For many examples and computations of $G^+(X)$ see~\cite{sz,sch2} and the references there. For each such graph, $\langle S_N,G^+(X)\rangle$ is a candidate for an exotic intermediate quantum group. Monotonicity and locality (Proposition~\ref{prop:monloc}) reduce the question to the quantum subgroups of $G^+(X)$. The natural ones are group duals. \subsection{Disjoint automorphisms} Schmidt's criterion~\cite{sch} says that a graph with two non-trivial automorphisms of disjoint supports has quantum symmetry. In the language of Section~\ref{sec:duals}, this becomes an explicit group dual inside $G^+(X)$. \begin{proposition}\label{prop:disjoint} Let $C_1,\dots,C_r\subset G(X)$ be abelian groups of automorphisms whose supports $\supp C_i$ are pairwise disjoint. Let \[ \Gamma=\widehat{C_1}*\dots*\widehat{C_r}. \] Then $\widehat\Gamma\subset G^+(X)$, acting by the Fourier family with the following blocks: \begin{itemize} \item one block for each $C_i$-orbit $O\subset\supp C_i$, with subgroup $H_O=\mathrm{Stab}_{C_i}(O)^\perp\subset\widehat{C_i}$; \item trivial blocks at the points outside $\bigcup_i\supp C_i$. \end{itemize} This group dual is non-classical as soon as two of the $C_i$ are nontrivial. \end{proposition} \begin{proof} On $C(\supp C_i)$, consider the $\widehat{C_i}$-grading coming from the classical action of $C_i$: the component of degree $\chi$ consists of the functions $f$ with $f\circ c^{-1}=\chi(c)f$ for all $c\in C_i$. Extend this by the trivial grading on the functions supported outside $\bigcup_i\supp C_i$. Since the supports are disjoint, the result is a $\Gamma$-grading of $C(X)$: \begin{itemize} \item products of functions with different supports vanish; \item the unit is a sum of degree-$e$ indicator functions. \end{itemize} So by Theorem~\ref{thm:bichon} it is a coaction of $\widehat\Gamma$, with the stated orbits. Recall that an abelian group acts on each of its orbits regularly, through $C_i/\mathrm{Stab}(O)$. It remains to check that $A$ preserves every graded component. \begin{itemize} \item For $\chi\ne1$ in $\widehat{C_i}$, the component of degree $\chi$ is the $\chi$-eigenspace of $C_i$ acting on all of $C(X)$. Indeed, an eigenfunction for a nontrivial character vanishes at the fixed points of $C_i$. This eigenspace is preserved by $A$, since $A$ commutes with $C_i$. \item The component of degree $e$ is the space of functions invariant under all the $C_i$, which is also preserved by $A$. \item All other components are zero. \end{itemize} Hence the coaction commutes with $A$, and $\widehat\Gamma\subset G^+(X)$. If two of the $C_i$ are nontrivial, then $\Gamma$ is non-abelian. \end{proof} \begin{remark} Some comments on this result. \begin{itemize} \item With $r=2$ and $C_1=\langle\sigma\rangle$, $C_2=\langle\tau\rangle$, this recovers Schmidt's criterion, and identifies the quantum symmetry that the criterion detects. \item Replacing $\sigma,\tau$ by suitable powers, we may assume that they have prime orders $\ell,\ell'$. Then $\Gamma=\Z_\ell*\Z_{\ell'}$, acting through one $\Z_\ell$-block for each $\ell$-cycle of $\sigma$ and one $\Z_{\ell'}$-block for each $\ell'$-cycle of $\tau$. A smaller support only helps. \end{itemize} \end{remark} \begin{corollary}\label{cor:small} If $X$ has two non-trivial automorphisms $\sigma,\tau$ with disjoint supports and $|\supp\sigma|+|\supp\tau|\le5$, then $\langle S_N,G^+(X)\rangle=S_N^+$. This applies, for instance, to any graph containing two disjoint pairs of twins, i.e.\ pairs of vertices with the same neighborhood. \end{corollary} \begin{proof} By Proposition~\ref{prop:disjoint} and monotonicity, it is enough to treat the group dual. It moves at most $5$ points and is non-classical. So locality applies (Proposition~\ref{prop:monloc}): maximality for $N\le5$, together with~\cite[Cor.~3.4]{bcf}. \end{proof} When $|\supp\sigma|+|\supp\tau|\ge6$, locality does not apply. The group dual of Proposition~\ref{prop:disjoint} then has \emph{repeated} blocks. For instance, $\sigma=(12)(34)$ and $\tau=(56)$ give the family $(\langle x\rangle,\langle x\rangle,\langle y\rangle)$ of $\Z_2*\Z_2$, i.e.\ $u=\mathrm{diag}(M(p),M(p),M(q))$. Such actions have no quantum subgroups with smaller support. By Proposition~\ref{prop:reduction} we pass to JNA quotients of $\Z_\ell*\Z_{\ell'}$, and test them. The smallest cases are those where the two supports have total size $6$, $7$ or $8$, so that $N\le9$, and where the quotients are the smallest JNA groups of Example~\ref{ex:table}, namely $S_3$, $D_4$, $D_5$ and $A_4$. The test itself is the one of Section~\ref{sec:duals}, with the same program, a family with repeated blocks being just a family with repetitions, and the outcome is the same as before. \begin{proposition}[computational]\label{prop:repeated} For the following group duals with repeated blocks, the joint dimensions with $S_N$ are Catalan for $4\le k\le7$ (for $4\le k\le6$ when $N=9$): \begin{center} \begin{tabular}{@{}llll@{}}\toprule $\Gamma$ & family (blocks) & from $(\sigma,\tau)$ & $N$\\\midrule $S_3$ & $\langle(12)\rangle^2,\ \langle(23)\rangle$ & $(12)(34)$, $(56)$ & 6\\ $D_4$ & $\langle s\rangle^2,\ \langle sr\rangle$ & $(12)(34)$, $(56)$ & 6\\ $D_5$ & $\langle s\rangle^2,\ \langle sr\rangle$ & $(12)(34)$, $(56)$ & 6\\ $S_3$ & $\langle(12)\rangle^2,\ \langle(123)\rangle$ & $(12)(34)$, $3$-cycle & 7\\ $S_3$ & $\langle(12)\rangle^2,\ \langle(23)\rangle^2$ & $(12)(34)$, $(56)(78)$ & 8\\ $S_3$ & $\langle(12)\rangle^3,\ \langle(23)\rangle$ & $(12)(34)(56)$, $(78)$ & 8\\ $A_4$ & $\langle(123)\rangle^2,\ \langle(234)\rangle$ & two $3$-cycles, one $3$-cycle & 9\\\bottomrule \end{tabular} \end{center} Here $H^m$ means the subgroup $H$ repeated $m$ times. \end{proposition} So no counterexample arises from disjoint automorphisms in these ranges. A general proof that repeated blocks are always absorbed is open. It would follow from the general statement suggested in Section~\ref{sec:dualsconcl}. \subsection{Global quantum symmetry: solution groups} The graphs that escape Proposition~\ref{prop:disjoint} are those whose quantum symmetry is \emph{global}. The main known examples come from binary linear systems~\cite{drs,rs}. \begin{itemize} \item A system $Mx=b$ over $\Z_2$, with $n$ variables, has a solution group $\Gamma$ generated by involutions $x_1,\dots,x_n$ (and a central involution $J$). Variables occurring in a common equation commute, and each equation $i$ gives the relation $\prod_{j}x_j^{M_{ij}}=J^{b_i}$. \item In the graphs of~\cite{drs,rs}, $\Gamma$ (or a quotient of it) acts on the $2n$ variable vertices by \[ u=\mathrm{diag}\big(M(p_1),\dots,M(p_n)\big),\qquad p_j=\tfrac{1+x_j}2 . \] In the language of Section~\ref{sec:duals}, this is the Fourier family $(\langle x_1\rangle,\dots,\langle x_n\rangle)$, with all blocks of type $\Z_2$. \end{itemize} We test this action of $\widehat\Gamma$ on $2n$ points as a candidate in its own right. When all the blocks are of type $\Z_2$, the notions of Section~\ref{sec:laws} simplify, as follows. Since $\mathrm{Aut}(\Z_2)$ is trivial, a label is either trivial or not. So a pattern on $k$ legs is simply a pair $(\kappa,M)$, where $\kappa\in P(k)$ records which legs lie on the same orbit, that is, carry the same generator, and $M\subset\{1,\dots,k\}$ is the set of legs carrying the nontrivial element. Such a pattern is balanced when each block of $\kappa$ contains an even number of legs of $M$, and it is active when some assignment of \emph{distinct} generators to the blocks of $\kappa$ makes the ordered word along $M$ nontrivial in $\Gamma$. \begin{corollary}[laws lemma, $\Z_2$-blocks]\label{cor:z2laws} Let $\widehat\Gamma\subset S_{2n}^+$ act through a Fourier family of $\Z_2$-blocks $\langle x_1\rangle,\dots,\langle x_n\rangle$. \begin{enumerate} \item The spaces $\Fix_{\langle S_{2n},\widehat\Gamma\rangle}(u^{\otimes k})$ depend only on the set of active patterns $(\kappa,M)$ with $k$ legs. \item If $\Gamma$ has no nontrivial laws with $\le k$ legs, then $\Fix_{\langle S_{2n},\widehat\Gamma\rangle}(u^{\otimes l})=\Fix_{S_{2n}^+}(u^{\otimes l})$ for all $l\le k$. \end{enumerate} \end{corollary} \begin{proof} (1) This is Lemma~\ref{lem:laws}, with all $H_i\simeq\Z_2$. (2) By Corollary~\ref{cor:laws}, up to level $k$ the quantum group $\langle S_{2n},\widehat\Gamma\rangle$ has the same intertwiners as $\langle S_{2n},T\rangle$, where $T$ is the dual of $\Z_2^{*n}$, with its tautological family. By killing all but two generators, $T$ contains the dual of $\Z_2*\Z_2$, which is non-classical and moves $4$ points. So, by locality, Proposition~\ref{prop:monloc}, we have \[ \langle S_{2n},\widehat\Gamma\rangle=\langle S_{2n},T\rangle=S_{2n}^+ \] at all levels $l\le k$, as claimed. \end{proof} \begin{proposition}[Mermin--Peres magic square~\cite{me}, $N=18$]\label{prop:magic} Here the magic square system has $9$ variables and $6$ equations. Its realization by real $2$-qubit Pauli operators has image $2^{1+4}_+$, of class~(a) in Proposition~\ref{prop:jna}. The dual of this image is a quantum subgroup of $\widehat\Gamma$. For it, the joint dimensions at $k=4,\dots,8$ are \[ 14,\ 42,\ 132,\ 429,\ 1430 , \] which are Catalan, compared with the Bell numbers $15,52,203,877,4140$. This is despite the short law $(ab)^4=1$, which comes from exponent $4$. \end{proposition} The computation was done by exact linear algebra modulo a prime, with the patterns $(\kappa,M)$ of Corollary~\ref{cor:z2laws} (\texttt{sol.py}, $41$ seconds at $k=8$). The values at $k=4,5$ were confirmed independently by \texttt{duals.py}. At $k=8$, exactly one of the $17284$ balanced patterns which are not freely trivial is a law, namely $(ab)^4$. \begin{proposition}[the $A_7$ system, $N=210$]\label{prop:a7} The system of~\cite{drs} has $105$ variables, namely the double transpositions of $A_7$ (the edges of the Kneser graph $K(7,2)$), and $140$ equations. Its solution group is $3.A_7$. Up to relabeling, there are $291$ words of length $\le8$ in which every letter occurs an even number of times and which are not freely trivial, and each of them admits distinct double transpositions with nontrivial product in $A_7$ (\texttt{sol.py}). So there are no nontrivial laws of length $\le8$, already in the JNA quotient $A_7$. By Corollary~\ref{cor:z2laws}, $\langle S_{210},\widehat\Gamma\rangle$ agrees with $S_{210}^+$ through level $8$. \end{proposition} \subsection{Vertex-transitive graphs on at most $13$ vertices} For small vertex-transitive graphs, the existence of quantum symmetry is completely known: \begin{itemize} \item $N\le11$ by Banica and Bichon (see~\cite{sch2}), except the Petersen graph, which was settled by Schmidt~\cite{sch}; \item $N=12$ by Schanz~\cite{sz}; \item $N=13$ by Chassaniol~\cite{cha1,cha2}. \end{itemize} In this range, a graph has quantum symmetry iff it has two disjoint automorphisms~\cite[Observation~1]{sz}. We combine this with Proposition~\ref{prop:disjoint}. \begin{proposition}[computational]\label{prop:vtcount} We generated all vertex-transitive graphs on $N\le13$ vertices, as the Cayley graphs of all groups of order $N$ together with the Petersen graph and its complement. The numbers obtained agree with the known counts. For each graph we determined the minimal total support $s=|\supp\sigma|+|\supp\tau|$ of two automorphisms of prime order with disjoint supports: \begin{center} \begin{tabular}{@{}lcccccccccc@{}}\toprule $N$ & 4&5&6&7&8&9&10&11&12&13\\\midrule vertex-transitive graphs & 4&3&8&4&14&9&22&8&74&14\\ no disjoint automorphisms & 0&1&2&2&4&5&10&6&32&12\\ $s=4$ (two pairs of twins) & 4&2&6&2&8&4&8&2&20&2\\ $s=8$, $\sigma,\tau$ of type $(2,2)$ & &&&&2&&4&&14&\\ $s=12$, $\sigma,\tau$ of type $(2,2,2)$ & &&&&&&&&8&\\\bottomrule \end{tabular} \end{center} At $N=12$, the $42$ graphs with disjoint automorphisms form the $21$ complementary pairs with quantum symmetry found in~\cite{sz}. At $N=8$ the $s=8$ graphs are the cube and its complement. At $N=10$ they are $2C_5$, $K_5\times K_2$ and their complements. \end{proposition} So every remaining case has $\sigma$ and $\tau$ both products of $m\in\{2,3\}$ disjoint transpositions. By Proposition~\ref{prop:disjoint}, the corresponding group dual is the dual of $\Z_2*\Z_2$ acting with blocks $(\langle x\rangle^m,\langle y\rangle^m)$. This is the $4$-point action $\mathrm{diag}(M(p),M(q))$ with every point repeated $m$ times. We now exploit this structure. \begin{definition} The \emph{$m$-fold repetition} is the morphism $\varphi_m:S_n^+\to S_{nm}^+$ given by $u\mapsto u\otimes1_m$. Here the point set is $\{1,\dots,n\}\times\{1,\dots,m\}$, and $(u\otimes1_m)_{(i,c),(j,c')}=u_{ij}\delta_{cc'}$, which is magic. \end{definition} \begin{lemma}\label{lem:rep} For quantum subgroups $A,B\subset S_n^+$, we have $\varphi_m(\langle A,B\rangle)=\langle\varphi_m(A),\varphi_m(B)\rangle$. \end{lemma} \begin{proof} For $L\subset S_n^+$, the fundamental representation of $\varphi_m(L)$ is $u_L\otimes1_m$ on $\C^n\otimes\C^m$, so \[ \mathrm{Hom}_{\varphi_m(L)}(k,l)=\mathrm{Hom}_L(k,l)\otimes B\big((\C^m)^{\otimes k},(\C^m)^{\otimes l}\big). \] The intertwiners of a generated quantum group are the intersections of the intertwiners. Since $(U\otimes W)\cap(V\otimes W)=(U\cap V)\otimes W$ for subspaces $U,V$, we get \[ \mathrm{Hom}_{\langle\varphi_m(A),\varphi_m(B)\rangle}=\big(\mathrm{Hom}_A\cap\mathrm{Hom}_B\big)\otimes B(\cdot,\cdot)=\mathrm{Hom}_{\varphi_m(\langle A,B\rangle)} . \] Thus the two quantum groups in the statement have the same intertwiners, and so they are equal, by Tannakian duality. \end{proof} In order to deal with the remaining cases, we would need to know that repeated copies of $S_4^+$, together with the symmetric group, generate the whole quantum permutation group. This is a topological generation question, of the type studied by Chirvasitu~\cite{ch2} and by Brannan, Chirvasitu and Freslon~\cite{bcf}. Their methods work well in large dimensions, but usually lead to difficult generation questions in small dimensions, and here we are precisely in the smallest dimension, $4$, where $S_4^+$ is still coamenable, and has a rather special representation theory. For our purposes, we would need the following statement. \begin{conjecture}[repetition lemma]\label{conj:rep} $\langle S_{4m},\varphi_m(S_4^+)\rangle=S_{4m}^+$ for $m\ge1$. \end{conjecture} For $m=1$ there is nothing to prove. For $m=2,3$ the joint dimensions are Catalan for $k\le7$ (exact, \texttt{doubling.py}). The computation uses the fact that a vector $\sum_\pi a_\pi\xi_\pi$ is fixed by $\varphi_m(S_4^+)$ if and only if, for every partition $\kappa$ of the legs with at most $m$ blocks, $\sum_{\pi\le\kappa}a_\pi\xi_\pi^{(4)}$ lies in the span of the noncrossing partition vectors at $N=4$. With the Gram matrix of the vectors $\xi_\pi^{(4)}$, this becomes a rank computation, done modulo a prime, so that a Catalan output is a proof, as in Section~\ref{sec:duals}. \begin{theorem}\label{thm:vt} Let $X$ be a vertex-transitive graph on $N\le13$ vertices. \begin{enumerate} \item If $X$ has no quantum symmetry, then $\langle S_N,G^+(X)\rangle=S_N$. \item If $X$ has two pairs of twins with disjoint supports, then $\langle S_N,G^+(X)\rangle=S_N^+$. This covers all graphs with quantum symmetry except the $14$ complementary pairs of Proposition~\ref{prop:vtcount} with $s\in\{8,12\}$. \item If $s=8$ and $N\ge10$ (the $2+7$ pairs at $N=10,12$), then $\langle S_N,G^+(X)\rangle=S_N^+$. \item For the remaining $5$ pairs (the cube at $N=8$, and the $s=12$ graphs at $N=12$), $\langle S_N,G^+(X)\rangle$ contains a copy of $\varphi_m(S_4^+)$, with $m=2$ or $3$, acting on $4m$ of the points. Hence $\langle S_N,G^+(X)\rangle=S_N^+$, provided that Conjecture~\ref{conj:rep} holds for that $m$. \end{enumerate} In particular, no vertex-transitive graph on at most $13$ vertices gives an exotic quantum group $S_N\subsetneq\langle S_N,G^+(X)\rangle\subsetneq S_N^+$, except possibly the cube and the four $s=12$ pairs, and those only if the repetition lemma fails. \end{theorem} \begin{proof} (1) is clear. (2) is Corollary~\ref{cor:small}. (3) Here $m=2$, and there are $N-8\ge2$ fixed points. Let $G_5=G_4\oplus1$ be the $4$-point action of the dual of $\Z_2*\Z_2$ with one extra fixed point. Then $\langle S_5,G_5\rangle=S_5^+$, by the maximality of $S_5\subset S_5^+$~\cite{bah}. By Proposition~\ref{prop:disjoint}, $G^+(X)$ contains, up to relabeling, $\varphi_2(G_5)$, and by Lemma~\ref{lem:rep}, $\langle S_{10},\varphi_2(G_5)\rangle\supset\varphi_2(S_5^+)$, the diagonal embedding of $S_5^+$ in $S_{10}^+$. Then~\cite[Prop.~3.10 and Ex.~3.9]{bcf} gives $\langle S_{10},\varphi_2(S_5^+)\rangle=S_{10}^+$, and finally $\langle S_N,S_{10}^+\rangle=S_N^+$ by~\cite[Cor.~3.4]{bcf}. (4) By Proposition~\ref{prop:disjoint}, $G^+(X)$ contains $\varphi_m(G_4)$, extended by the identity on the remaining $N-4m$ points, with $G_4$ the dual of $\Z_2*\Z_2$ on $4$ points. Since $S_4\subset S_4^+$ is maximal, $\langle S_4,G_4\rangle=S_4^+$, so by Lemma~\ref{lem:rep} the quantum group $\langle S_{4m},\varphi_m(G_4)\rangle$, acting on the support, contains $\varphi_m(S_4^+)$. Given the conjecture, it contains $S_{4m}^+$, and $\langle S_N,S_{4m}^+\rangle=S_N^+$ by~\cite[Cor.~3.4]{bcf}. \end{proof} \begin{remark} For $S_M^+$ with $M\ge5$ in place of $S_4^+$, the repetition statement is known: diagonal embeddings are $(M,N)$-large, so $\langle S_{KM},\mathrm{diag}(S_M^+)\rangle=S_{KM}^+$~\cite[Ex.~3.9, Prop.~3.10]{bcf}. Their proof uses the linear independence of noncrossing partitions on a space of dimension $M-1\ge4$, which fails for $M=4$. So Conjecture~\ref{conj:rep} is exactly the missing case $M=4$. Note also that Lemma~\ref{lem:rep} applies to any repetition of a locally absorbed action. So the conjecture, for general $m$, would settle every group dual whose blocks are those of a $\le5$-point action repeated uniformly. \end{remark} \subsection{Lessons} \begin{remark} We draw the following lessons from this section. \begin{itemize} \item \emph{Locality.} Quantum symmetry living on a few points (disjoint automorphisms with small supports) is absorbed by $S_N$. This follows from~\cite{bcf}. \item \emph{Repeated blocks.} Disjoint automorphisms with larger supports give group duals with repeated blocks. These are absorbed in every case computed (Proposition~\ref{prop:repeated}). For uniform repetitions they reduce to the repetition lemma (Conjecture~\ref{conj:rep}), and this covers all vertex-transitive graphs on $\le13$ vertices (Theorem~\ref{thm:vt}). \item \emph{Freeness.} Global quantum symmetry coming from large perfect groups ($A_7$, class~(c)) has no short nontrivial laws. Such groups look free at every computable level, and are absorbed. \item \emph{Short laws are not enough.} The magic square group ($2^{1+4}_+$, class~(a)) has short nontrivial laws, and is still absorbed through level~$8$. \end{itemize} So graphs, as far as they can be tested, reduce to group duals, and add nothing beyond Section~\ref{sec:duals}. Whether a graph with global quantum symmetry could ever give an exotic $\langle S_N,G^+(X)\rangle$ is the same question as for group duals: whether some JNA group has enough short laws. \end{remark} %====================================================================== % Section: twists %====================================================================== \section{Cocycle twists of \texorpdfstring{$S_N$}{SN} and \texorpdfstring{$PU_n$}{PUn}}\label{sec:twists} We continue our search for seeds $K\subset S_N^+$. The group duals and the quantum automorphism groups of graphs are absorbed by $S_N$, as far as we can compute, so we turn to a third family, the cocycle twists of $S_N$ and of its subgroups, and then to the twists of the projective unitary groups $PU_n$, acting on $N=n^2$ points. \subsection{Twists of $S_N$}\label{sec:twsn} Let $A\subset S_N$ be an abelian subgroup, and let $\sigma$ be a $2$-cocycle on the dual group $\widehat A$ with values in roots of unity. The restriction map $C(S_N)\to C(A)=\C[\widehat A]$ allows us to view $\sigma$ as a Hopf $2$-cocycle on $C(S_N)$. Twisting by it, in the sense of Drinfeld~\cite{dr}, Doi~\cite{doi} and Enock--Vainerman~\cite{ev,va}, gives a finite quantum group $S_N^\sigma$: \begin{itemize} \item its tensor category is equivalent to that of $S_N$; \item its coaction is a twisted version of the coaction of $S_N$ on $\C^N$. \end{itemize} Twists of this type, with $A\simeq\Z_2^n$ generated by the disjoint transpositions $(2i-1,2i)$ of $S_{2n}$, and $\sigma$ with values $\pm1$, go back to Nikshych~\cite{ni} and Bichon~\cite{bi00}. Bichon constructed in this way a family of noncommutative and noncocommutative Kac algebras $\mathcal O_{\mathbf p}(S_{2n})$, whose representation categories are monoidally equivalent to that of $S_{2n}$, and whose defining relations contain the magic unitary relations, so that they are quantum permutation groups~\cite[Def.~1, Thm.~2]{bi00}. Banica, Bichon and Natale give a sufficient condition for a twist of a quantum permutation algebra to be a quantum permutation algebra, and observe that Bichon's twistings satisfy it~\cite[Prop.~8.1, Ex.~8.2]{bbn}. Proposition~\ref{prop:comm} below is our own formulation of what is needed in the setting of $S_N$. The twisted coaction lives on the algebra $\C^N_\sigma$. This is $\C^N$ with the product deformed along the $\widehat A$-grading coming from the action of $A$: for homogeneous $f,g$ of degrees $\chi,\psi$, \[ f*g=\sigma(\chi,\psi)\,fg . \] For $S_N^\sigma$ to be a quantum \emph{permutation} group, this algebra must be commutative. \begin{proposition}\label{prop:comm} For an orbit $O$ of $A$, write $A_O$ for the stabilizer of a point of $O$, and $A_O^\perp\subset\widehat A$ for the characters trivial on $A_O$. Then $\C^N_\sigma$ is commutative iff, for every orbit $O$, the restriction of $\sigma$ to $A_O^\perp$ is symmetric, i.e.\ cohomologically trivial. In that case $\C^N_\sigma\simeq\C^N$ and $S_N^\sigma\subset S_N^+$. \end{proposition} \begin{proof} The functions supported on different orbits multiply to zero, so it suffices to look at one orbit $O$. The degrees occurring in $C(O)$ are exactly the characters in $A_O^\perp\simeq\widehat{A/A_O}$, since $A$ acts on $O$ regularly through $A/A_O$. So $C(O)$ is commutative iff $\sigma(\chi,\psi)=\sigma(\psi,\chi)$ on $A_O^\perp$. For abelian groups and $\C^\times$ coefficients, this is equivalent to $\sigma|_{A_O^\perp}$ being a coboundary. In that case $\C^N_\sigma$ is a commutative finite-dimensional $C^*$-algebra of dimension $N$, hence isomorphic to $\C^N$, and the twisted coaction becomes a coaction of $S_N^\sigma$ on $\C^N$. Since $S_N^+$ is the universal compact quantum group acting on $\C^N$~\cite{wa}, we obtain $S_N^\sigma\subset S_N^+$. See also~\cite[Prop.~8.1, Ex.~8.2]{bbn}, and~\cite{bi00} for Bichon's twists. \end{proof} \begin{remark}\label{rem:twcases} Two special cases: \begin{itemize} \item If every orbit group $A/A_O$ is cyclic, the condition holds automatically, since $2$-cocycles on cyclic groups are trivial. This covers the twists of Proposition~\ref{prop:twres} below. \item If $A$ acts \emph{regularly} and $\sigma$ is non-degenerate, then $\C^N_\sigma$ is a matrix algebra, and $S_N^\sigma$ is not a quantum permutation group: it acts on $M_n$, with $N=n^2$. In this case the dimension count of Proposition~\ref{prop:J} below can give joint dimensions below Catalan, which is impossible inside $S_N^+$. This case reappears in Section~\ref{sec:twalg}, read backwards. \end{itemize} Proposition~\ref{prop:comm} allows more than the cyclic case: non-cyclic orbits, such as Klein orbits, are fine as long as $\sigma$ only couples \emph{different} orbits. This mirrors the role of non-cyclic orbits in Section~\ref{sec:duals}. \end{remark} \subsection{Twisted intertwiners in the Fourier basis} Take $A=\Z_m^n$ acting on $N=mn$ points through $n$ disjoint $m$-cycles. Take the bicharacter \[ \sigma(e_i,e_j)=\omega^{b_{ij}}\quad(i0$, the Haar state being faithful on $C(G)$. So $h(P)=1/\dim C(G)$. \end{proof} So an exotic $G$ is either finite, and then coamenable, with $\dim C(G)>N!$ since $C(G)$ maps onto $C(S_N)$, or infinite, with no atom of $\mu_G$ at $N$. In the infinite case, coamenability means that $N$ is an accumulation point of the support of $\mu_G$. \begin{question}\label{qu:coam} Is an exotic $G$ coamenable? Can an exotic $G$ be finite? \end{question} Our feeling is that an exotic $G$, if any, should rather not be coamenable. Indeed, the results of McCarthy on the Haar state and the orbitals (Proposition~\ref{prop:mc} and Theorem~\ref{thm:orbitals}) suggest that such a $G$ is ``closer'' to $S_N^+$ than to $S_N$, and the level computations of Sections~\ref{sec:method}--\ref{sec:higher} point in the same direction: for $8\le N\le37$, the first $8$ moments of $\mu_G$ are the Catalan numbers, as for $S_N^+$. This does not decide the question, since the moment bounds $C_k\le\dim\Fix_G(k)\le\dim\Fix_{S_N}(k)$ say nothing about the growth rate, and a non-amenable witness inside $G$ would have to be global, for instance a non-amenable group dual with all its non-trivial pieces on $\ge6$ points, such as $\widehat{\Z_3*\Z_3}$ acting through two $\Z_3$-blocks. \subsection{Finite exotic quantum permutations}\label{sec:finite} Let us try to exclude an exotic $G$ which is finite, $\dim C(G)<\infty$, as in Question~\ref{qu:coam}. Finiteness produces a Lagrange theorem, and lower bounds on the size of $G$ growing with the number of settled levels, but no contradiction. We write $D=\dim C(G)$, $m_k=\dim\Fix_G(k)$ and $s_k=\dim\Fix_{S_N}(k)$. \begin{proposition}\label{prop:finstructure} Let $G$ be a finite exotic quantum permutation group. \begin{enumerate} \item The characters of $C(G)$ are the evaluations $ev_\sigma$, $\sigma\in S_N$. So $C(G)=\C^{N!}\oplus A_{nc}$, where $A_{nc}$ is a sum of matrix blocks $M_{n_b}$ with $n_b\ge2$. \item \emph{(Lagrange)} $D=q\cdot N!$, for an integer $q\ge2$, the index of $S_N$ in $G$. \item \emph{(Cosets)} The algebra $C(G/S_N)$ of right $S_N$-invariant elements has dimension $q$, and $C(G/S_N)\simeq\bigoplus_\alpha f_\alpha V_\alpha$ as a $G$-module, where $f_\alpha=\dim V_\alpha^{S_N}$. So \[ q=\sum_\alpha d_\alpha f_\alpha. \] \item The law of $\chi$ splits as $\mu_G=\frac1q\,\mu_{S_N}+\left(1-\frac1q\right)\nu$, where $\nu$ is the normalized law of $\chi$ on $A_{nc}$, a probability measure on $[0,N)$. \end{enumerate} \end{proposition} \begin{proof} (1) A character maps $u$ to a permutation matrix, so the classical version of $G$ is $S_N$, and the characters of a finite dimensional C$^*$-algebra are its $1$-dimensional blocks. (2) Dually, $\C[S_N]$ is a Hopf subalgebra of $C(G)^*$, and $N!\mid D$ by the Nichols--Zoeller theorem~\cite{nz}. (3) $C(G)$ is free over its quotient $C(S_N)$, which gives the dimension, and by Peter--Weyl the right $S_N$-invariant part of $C(G)=\bigoplus_\alpha V_\alpha\otimes\bar V_\alpha$ is $\bigoplus_\alpha V_\alpha\otimes\bar V_\alpha^{S_N}$. (4) The Haar state is the normalized regular trace, $h=\frac1D\sum_bn_b\mathrm{Tr}_b$, so the classical part has weight $N!/D=1/q$, and on it $\chi$ counts the fixed points. On a block of size $\ge2$, an eigenvector of $\chi$ at $N$ would satisfy $u_{ij}\xi=\delta_{ij}\xi$, and give a $1$-dimensional subrepresentation of an irreducible block. \end{proof} By (4), with $t=1/(q-1)$, the moments of $\nu$ are $\nu_k=C_k+t\,(C_k-s_k)$ for all $k$ at which $G$ agrees with $S_N^+$. For $t\to0$ these are the moments of the free Poisson law, but positivity fails quickly as $t$ grows. \begin{theorem}[exact]\label{thm:finiteindex} A finite exotic $G$ has index $q=\dim C(G)/N!\ge31$, and $q\ge32$ for $N\ge7$. \end{theorem} \begin{proof} By Theorem~\ref{thm:levelseven}, $m_k=C_k$ for $k\le7$. Since $\nu$ lives on $[0,\infty)$, the Hankel matrix $H=(\nu_{i+j+1})_{0\le i,j\le3}$ is positive semidefinite. For $N\ge7$ we have $s_k=B_k$, the Bell numbers, for $k\le7$, and a direct computation gives $\det H=1-30t-14t^2+6t^3+t^4$. With $x=q-1=1/t$, this is $x^{-4}(x^4-30x^3-14x^2+6x+1)$, which is negative for the integers $1\le x\le30$. So $x\ge31$. For $N=6$ we have $s_7=B_7-1$, and the determinant is $1-29t-16t^2+5t^3+t^4$, which gives $x\ge30$. \end{proof} With the level-$8$ result of Corollary~\ref{cor:closeeight}, the Hankel matrix $(\nu_{i+j})_{0\le i,j\le4}$ gives $q\ge123$ for $8\le N\le37$. The thresholds for $t$ obtained from the levels $4,\dots,8$ are $1$, $0.414$, $0.116$, $0.0328$, $0.0082$, decreasing by a factor of about $4$ per level. Representation theory does better. \begin{proposition}[computational, $8\le N\le37$]\label{prop:finfrob} A finite exotic $G$ has index $q\ge1+d_4$, where $d_0=1$, $d_1=N-1$ and $d_{k+1}=(N-2)d_k-d_{k-1}$. For instance $q\ge1394$ at $N=8$. \end{proposition} \begin{proof} By Corollary~\ref{cor:closeeight}, $G$ has the intertwiners of $S_N^+$ through level $8$. So $u^{\otimes k}$, $k\le4$, decomposes into irreducible representations $r_0,\dots,r_4$ of dimensions $d_0,\dots,d_4$, with the multiplicities $m_{kj}$ of $S_N^+$, and $m_{44}=1$. Counting $S_N$-fixed vectors gives $s_k=\sum_jm_{kj}f_j$. For $k\le3$ we have $s_k=C_k=m_{k0}$, so $f_1=f_2=f_3=0$, and for $k=4$ we get $15=14+f_4$, so $f_4=1$. Now Proposition~\ref{prop:finstructure}(3) gives $q\ge d_0f_0+d_4f_4$. \end{proof} The same argument shows that the more levels are settled, the larger a finite exotic $G$ must be. If $G$ agrees with $S_N^+$ through level $2m$, then $q\ge\sum_{j\le m}d_jf_j$, where the multiplicities $f_j$ are those of $S_N^+$, namely $1,0,0,0,1,1,6,20,86,393,\dots$ for $N$ large. So $q\ge d_m$ for $m\ge4$, and $d_m$ grows roughly like $(N-2)^m$. All these are lower bounds. To exclude a finite exotic $G$, one needs an upper bound on $q$, or a contradiction between finiteness and the long initial agreement with $S_N^+$, and there are several possible sources for this: the coset algebra $C(G/S_N)$, a $q$-dimensional C$^*$-algebra with an ergodic action of $G$, whose ``double coset'' algebra has dimension $\sum_\alpha f_\alpha^2$; the fusion graph of $r_1$, a finite connected graph with Perron--Frobenius eigenvalue $N-1$ and integer Perron--Frobenius vector $(d_\alpha)$, starting with the chain $r_0-r_1-r_2-r_3$, and satisfying $\sum_\alpha d_\alpha^2=N!\sum_\alpha d_\alpha f_\alpha$; the fixed-point subfactor of the action of $G$ on $\C^N$, of index $N$ and finite depth, whose planar algebra lies between Temperley--Lieb and the spin model planar algebra of $S_N$; and integrality, the spectrum of $\chi$ consisting of totally real algebraic integers in $[0,N]$, with $\sum_km_kz^k$ a rational function with integer coefficients, by Proposition~\ref{prop:atom}. None of these gives an upper bound, as far as we can see: each of them is satisfied by a ``fake'' finite $G$ which looks like $S_N^+$ up to a high level, and then closes up. So the finite case does not seem to be easier than the maximality conjecture itself, or at least we do not know how to properly exploit the finiteness assumption. %====================================================================== % Section: method %====================================================================== \section{Partitions, levels and the method}\label{sec:method} This section and the next two form the core of the paper. They attack the maximality conjecture head-on, through the Tannakian category of a hypothetical intermediate quantum group $S_N\subsetneq G\subsetneq S_N^+$. The idea is simple. The category of $G$ sits between the noncrossing partitions and all partitions, and it must be closed under the usual categorical operations. So we look for the first ``level'' $k$ at which it could contain a vector outside the noncrossing span, and we write down enough necessary conditions to show that no such vector exists. At each level the conditions come in three layers: linear, quadratic and cubic. What makes the approach work in practice is that every layer can be reduced to finite, exact linear algebra, uniformly in $N$ wherever possible. Such computations cannot be checked by hand, so we put some care into making them \emph{certificates}: objects that can be verified independently, rather than numerical evidence. This section sets up the framework and the tools. Section~\ref{sec:six} settles level $6$ for all $N\ge6$. Section~\ref{sec:higher} settles level $7$ for all $N\ge6$, and proves a structural theorem at level $8$ for $7\le N\le37$. \subsection{Partition vectors and the two categories} Let $N\ge1$, and let $e_1,\dots,e_N$ be the standard basis of $\C^N$. For a partition $\pi$ of $\{1,\dots,k\}$ we use the vector \[ \xi_\pi=\sum_{i_1,\dots,i_k}\delta_\pi(i)\,e_{i_1}\otimes\dots\otimes e_{i_k}\ \in(\C^N)^{\otimes k}, \] where $\delta_\pi(i)=1$ if the multi-index $i$ is constant on each block of $\pi$, and $\delta_\pi(i)=0$ otherwise. We write $\Pp(k)$ for the set of all partitions of $k$ points, and $\NC(k)\subset\Pp(k)$ for the noncrossing ones. Recall that \[ \Fix_{S_N}(u^{\otimes k})=\spn\{\xi_\pi:\pi\in\Pp(k)\},\quad \Fix_{S_N^+}(u^{\otimes k})=\spn\{\xi_\pi:\pi\in\NC(k)\}. \] More generally, partitions with $k$ upper and $l$ lower points act as linear maps $T_\pi:(\C^N)^{\otimes k}\to(\C^N)^{\otimes l}$, and composing or tensoring such maps corresponds to composing or juxtaposing partitions. Each closed loop created by a composition contributes a factor $N$, see~\cite{bsp}. \begin{lemma}\label{lem:indep} The vectors $\xi_\pi$, $\pi\in\Pp(k)$, are linearly independent if and only if $k\le N$. For $k=N+1$ there is exactly one linear relation, namely \[ \sum_{\pi\in\Pp(k)}\mu(0_k,\pi)\,\xi_\pi=0, \] where $\mu$ is the M{\"o}bius function of the partition lattice, so that $\mu(0_k,\pi)=\prod_{B\in\pi}(-1)^{|B|-1}(|B|-1)!$. \end{lemma} \begin{proof} By M{\"o}bius inversion, the vector $\sum_\pi\mu(0_k,\pi)\xi_\pi$ is the sum of all $e_{i_1}\otimes\dots\otimes e_{i_k}$ with pairwise distinct indices. The vectors $\delta_{\ker=\pi}$, sums over the multi-indices whose kernel is exactly $\pi$, are related to the $\xi_\pi$ by a unitriangular change of basis. They are nonzero, with disjoint supports, exactly when $\pi$ has at most $N$ blocks. For $k=N+1$, only the partition into singletons has more than $N$ blocks. \end{proof} The noncrossing vectors behave better: for $N\ge4$ the $\xi_\pi$, $\pi\in\NC(k)$, are linearly independent for every $k$. This is the nondegeneracy of the Temperley--Lieb Gram matrices at parameter $N\ge4$. \subsection{Levels} Let $S_N\subset G\subset S_N^+$, and write $\mathcal C(k)=\Fix_G(u^{\otimes k})$. Then \[ \spn\{\xi_\pi:\pi\in\NC(k)\}\ \subset\ \mathcal C(k)\ \subset\ \spn\{\xi_\pi:\pi\in\Pp(k)\}, \] and the family $\mathcal C=(\mathcal C(k))_k$, together with the corresponding spaces of intertwiners, is a tensor category containing all the noncrossing partitions. We abbreviate $\NC(k)$ for the span of the noncrossing partition vectors, when no confusion can arise. \begin{definition} The category $\mathcal C$ \emph{first differs at level $k$} if $\mathcal C(l)=\NC(l)$ for all $l2$ are allowed. \begin{proposition}\label{prop:gdbasic} \leavevmode \begin{enumerate} \item $\mathcal C_{\widehat\Gamma}(k)=\spn\{f_w:w\in A^k,\ w_1\cdots w_k=1\text{ in }\Gamma\}$. \item In the basis $(f_w)$, $\xi_\pi=\sum f_w$, summed over the words $w$ \emph{compatible} with $\pi$: for each pair $(s,t)$ of $\pi$, $w_t=\overline{w_s}$. Hence the category of $\langle O_N,\widehat\Gamma\rangle$ is \[ C(k)=\{x\in\Br(k):x\text{ is supported on trivial words}\}, \] and it only depends on the laws of $\Gamma$ of length $k$. \item $\widehat\Gamma\subset O_N$ iff $\Gamma$ is abelian. $\widehat\Gamma\subset O_N^*$ iff $\Gamma$ is \emph{half-abelian}, meaning $xyz=zyx$ for all letters $x,y,z\in A$. \end{enumerate} \end{proposition} \begin{proof} (1) and (2) are direct; for example, $\sum_ie_i\otimes e_i=\sum_rf_r\otimes f_{\bar r}$ on each block. For (3), $O_N$ and $O_N^*$ are generated over $\TL$ by the crossings $(13)(24)$ and $\kappa=(14)(25)(36)$, and their compatible words are $xy\bar x\bar y$ and $xyz\bar x\bar y\bar z$. \end{proof} \begin{proposition}[reduction]\label{prop:jnha} If group duals give a counterexample, then some \emph{just non-half-abelian} group gives one: a non-half-abelian $\Gamma$ all of whose proper quotients are half-abelian. Equivalently, the normal closure of the elements $xyz(zyx)^{-1}$ is the unique minimal normal subgroup of $\Gamma$. \end{proposition} \begin{proof} If $\Gamma\to\Gamma'$ is a quotient preserving the letters, then $\Gamma'$ has more laws, so $\langle O_N,\widehat{\Gamma'}\rangle\subset\langle O_N,\widehat\Gamma\rangle$, and $\widehat{\Gamma'}$ is still a seed when $\Gamma'$ is not half-abelian. Half-abelianity is a finite set of relations, so Zorn's lemma applies, as in the just-non-abelian reduction of Section~\ref{sec:duals}. \end{proof} Let $D(\Gamma)=\{\pi\in P_2:\ \xi_\pi\in\mathcal C_{\widehat\Gamma}\}$ be the set of pairings whose vectors are fixed by $\widehat\Gamma$. By Proposition~\ref{prop:gdbasic}, the category of $\langle O_N,\widehat\Gamma\rangle$ is $\Br\cap\mathcal C_{\widehat\Gamma}$, and it contains $\spn\{\xi_\pi:\pi\in D(\Gamma)\}$. \begin{definition}\label{def:easygd} We say that $\widehat\Gamma\subset O_N^+$ is \emph{easy over $O_N$} if \[ \Br\cap\mathcal C_{\widehat\Gamma}=\spn\{\xi_\pi:\pi\in D(\Gamma)\}, \] that is, if the category of $\langle O_N,\widehat\Gamma\rangle$ is spanned by pairings. \end{definition} This is a strong condition: a priori, $\Br\cap\mathcal C_{\widehat\Gamma}$ could contain linear combinations of pairing vectors supported on trivial words, without any of the pairings in it being in $D(\Gamma)$. \begin{theorem}[trichotomy]\label{thm:gdtri} \begin{enumerate} \item $D(\Gamma)$ is a category of pairings containing $NC_2$. So it is $NC_2$, $P_2^*$ or $P_2$, according to whether $\Gamma$ is not half-abelian, half-abelian but not abelian, or abelian. \item If $\widehat\Gamma$ is easy over $O_N$, then $\langle O_N,\widehat\Gamma\rangle$ is $O_N^+$, $O_N^*$ or $O_N$, in the three cases above. \end{enumerate} \end{theorem} \begin{proof} (1) Composites of pairing maps are multiples $N^{\ell}\ne0$ of pairing maps, so $D(\Gamma)$ is closed under the category operations. The classification of categories of pairings~\cite{bcs,bsp} and Proposition~\ref{prop:gdbasic}(3) give the rest. (2) is then immediate from Definition~\ref{def:easygd}. \end{proof} \begin{proposition}[computational]\label{prop:gdcomp} The group duals below are easy over $O_N$ at the levels shown. That is, for every generating tuple of permutations listed, taken up to simultaneous conjugation and grouped by their sets of trivial words, the joint dimensions are exactly those of $O_N$, $O_N^*$ or $O_N^+$, according to whether $\Gamma$ is abelian, half-abelian or neither: \begin{center} \begin{tabular}{@{}ccccc@{}} \toprule letters & $N$ & permutations in & distinct law sets & levels \\ \midrule $1$ involution, $1$ rotation pair & $3$ & $S_2,\dots,S_6$ & $31$ (in $S_6$) & $4,6,8$ \\ $2$ rotation pairs & $4$ & $S_2,\dots,S_6$ & $305$ (in $S_6$) & $4,6,8$ \\ $2$ involutions, $1$ rotation pair & $4$ & $S_2,\dots,S_5$ & $595$ (in $S_5$) & $4,6,8$ \\ $1$ involution, $2$ rotation pairs & $5$ & $S_2,\dots,S_5$ & $2339$ (in $S_5$) & $4,6$ \\ $3$ involutions, $1$ rotation pair & $5$ & $S_2,\dots,S_4$ & $917$ (in $S_4$) & $4,6$ \\ \bottomrule \end{tabular} \end{center} About $4500$ law sets in all, with no exception. For residually finite $\Gamma$, such as $\Z_3*\Z_3$, $\mathrm{SL}_2(\Z)$ or free groups, the laws of a given length are seen by finite quotients, so these searches cover such groups level by level. \end{proposition} \begin{conjecture}\label{conj:easiness} Every group dual $\widehat\Gamma\subset O_N^+$ is easy over $O_N$. Hence, by Theorem~\ref{thm:gdtri}, group duals are never seeds of counterexamples. \end{conjecture} A natural approach to Conjecture~\ref{conj:easiness} would be a M\"obius-type argument, as in the classification of the orthogonal easy quantum groups by Raum and Weber~\cite{rw}. A special case is Conjecture~\ref{conj:torus} below, coming from $\Gamma=\Z_2*\Z_2$. \begin{remark}[unitary group duals] Seeds need not live in $O_N^+$: any $G\subset U_N^+$ gives $PG\subset PU_N^+=PO_N^+$, and one asks whether $\langle PO_N,PG\rangle=PU_N^+$. For $G=U\widehat\Gamma U^*$ the data is a pair $(\Gamma,M)$ with $M=U^tU$ symmetric unitary, a continuous family. We checked (computational) all $119$ law sets at $N=3$ with generators in $S_2,\dots,S_5$ and all $611$ law sets at $N=4$ with generators in $S_2,S_3,S_4$, at levels $4,6,8$ and several positions $M$. In all cases $\langle PO_N,PG\rangle=PU_N^+$ when $PG$ is non-classical, and it is $PO_N$ or $PU_N=PO_N^*$ otherwise. These questions are taken up in Section~\ref{sec:related}. \end{remark} \subsection{The anticommutative twist}\label{sec:twist} Let $O_N^{-1}$ be the twist of $O_N$ in which $u_{ij}$ and $u_{kl}$ anticommute for $i\ne k$, $j\ne l$ and commute otherwise. It is the quantum automorphism group of the $N$-hypercube~\cite{bbc}. It is not half-commutative for $N\ge3$, so it is a seed. For a multi-index $i\in[N]^k$ let \[ c(i)=(-1)^{\#\{sa$, count the pairs ``$a$-position before $b$-position''. The six relative orders $aabb,abba,bbaa,baab,abab,baba$ give $4,2,0,2,3,1$, which is odd exactly in the two crossing cases. \end{proof} We write $G_N=\langle O_N,O_N^{-1}\rangle$. The most direct use of Lemma~\ref{lem:signs} gives the low levels. \begin{proposition}[exact]\label{prop:twoN} For every $k\le2N$ we have $\mathcal C_{G_N}(k)=\TL_N(k)$. \end{proposition} \begin{proof} Let $x=\sum a_\pi\xi_\pi=\Theta\sum b_\pi\xi_\pi$. As $k/2\le N$, the coefficients are well defined. On $i$ with $\ker i=\pi$ and distinct labels, Lemma~\ref{lem:signs} gives $a_\pi=(-1)^{cr(\pi)}b_\pi$. Now let $\pi$ be crossing, pick two crossing blocks with union $Q$, and evaluate on $i$ whose kernel merges them, with distinct labels elsewhere. The pairings below $\ker i$ are the three $\sigma$ that agree with $\pi$ outside $Q$, and $\pi$ is the only one with crossing chords inside $Q$. A block outside $Q$ crosses the two chords of $\sigma$ in $Q$ with a total parity independent of $\sigma$, and the two chords inside $Q$ carry equal labels. So $c(i)(-1)^{cr(\sigma)}=(-1)^{[\sigma=\pi]}$, and the equation at $i$ reads $\sum_\sigma a_\sigma=\sum_\sigma(-1)^{[\sigma=\pi]}a_\sigma$, i.e.\ $a_\pi=0$. \end{proof} To go beyond $2N$ we induct on $N$, through corners. For a closed subgroup $H\subset O_{N-1}^+$ with fundamental representation $v$, its \emph{corner} is the closed subgroup of $O_N^+$ with fundamental representation $\mathrm{diag}(v,1)$. For $x\in(\C^N)^{\otimes k}$ and $S\subset\{1,\dots,k\}$, the \emph{slice} $x_S\in(\C^{N-1})^{\otimes(k-|S|)}$ collects the coordinates of $x$ with label $N$ exactly on $S$. Since $\mathrm{diag}(v,1)^{\otimes k}=\bigoplus_Sv^{\otimes(k-|S|)}$, \begin{equation}\label{eq:corner} x\text{ is fixed by the corner of }H\iff x_S\in C_H(k-|S|)\text{ for all }S. \end{equation} \begin{lemma}[corners]\label{lem:corner} For $N\ge3$, $G_N$ contains the corner of $G_{N-1}$. More precisely, if $x\in \mathcal C_{G_N}(k)$, then $x_S\in \mathcal C_{G_{N-1}}(k-|S|)$ for every $S$. \end{lemma} \begin{proof} The slice of $\xi_\pi$ is $\xi_{\pi\setminus S}$ (in dimension $N-1$) if $S$ is a union of blocks of $\pi$, and $0$ otherwise. So slices map $\Br_N$ to $\Br_{N-1}$. If the label $N$ sits exactly on $S$, the pairs of positions involving it contribute $\#\{p\notin S,\ q\in S,\ p