A complete classification of shuffle groups (Q6652250)

Given a deck of \(2n\) cards, one can perfectly shuffle them by first cutting the deck into two piles, and then interleaving the two piles in either order. The \textit{out-shuffle} leaves the original top card at the top, while the \textit{in-shuffle} moves the original top card to second. One defines \(G_{2,2n}\) to be the subgroup of \(\mathrm{Sym}(2n)\) generated by the out-shuffle and in-shuffle.\N\N\textit{P. Diaconis} et al. [Adv. Appl. Math. 4, 175--196 (1983; Zbl 0521.05005)] completely determined the structure of \(G_{2,2n}\) (also see Theorem 1.1 of the paper under review). They also proposed a more general problem that can be phrased for any natural number \(k\geq 2\), as follows.\N\NGiven a deck of \(kn\) cards, one can perfectly shuffle them by first dividing the deck into \(k\) piles, and then interleaving the \(k\) piles in any of the \(k!\) possible orders. One defines \(G_{k,kn}\) to be the subgroup of \(\mathrm{Sym}(kn)\) generated by these shuffles.\N\NSince the structure of \(G_{k,kn}\) was known for \(k=2\), it is natural to ask what happens for \(k\geq 3\). This problem has been investigated in the literature, and there was a conjecture that \(G_{k,kn}\) contains \(A_{kn}\) whenever \(k\geq 3\), \(n\) is not a power of \(k\), and \((k,n)\neq (4,2^f)\) for any \(f\in \mathbb{N}\).\N\NThe paper under review confirmed this conjecture by reducing the problem to checking that \(G_{k,kn}\) is \(2\)-transitive whenever \(k\geq 3\) and \(n\) is not a power of \(k\). The proof requires some deep results in group theory that rely on the classification of finite simple groups. As a consequence, together with previous work in the literature, the structure of \(G_{k,kn}\) is now completely known for \(k\geq 3\) as well.\N\NHere is the classification of shuffle groups as stated in Theorem 1.5 of the paper.\N\N\noindent\textbf{Theorem.} For \(k\geq 3\), the following hold.\N\begin{itemize}\N\item[(a)] If \(kn=k^m\), then \(G_{k,kn}\) is the primitive wreath product \(S_k \wr C_m\).\N\item[(b)] If \(k=4\) and \(kn=2^m\) with \(m\) odd, then \(G_{k,kn}\) is the affine group \(\mathrm{AGL}(m,2)\).\N\item[(c)] If \(n\) is not a power of \(k\) and either \(n\) is odd or both \(n/2\) and \(k(k-1)/2\) are odd integers, then \(G_{k,kn} = S_{kn}\).\N\item[(d)] In all other cases \(G_{k,kn}=A_{kn}\).\N\end{itemize}