Shuffle-Exchange Conjecture

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

Let $A$ be an alphabet of $k\geq2$ letters and $E=A^n$ the words of length $n\geq2$. Write $\mathfrak S(E)$ for all permutations of $E$, acting on the right, so $x(\alpha\beta)=(x\alpha)\beta$. The shuffle is $(x_1\cdots x_n)\sigma=x_2\cdots x_nx_1$. The exchange subgroup $G$ consists of all permutations preserving the first $n-1$ letters of every word. For subsets $P,Q$ of this permutation group, $PQ=\{pq:p\in P,q\in Q\}$. Define \[ d(k,n)=\min\{d\geq2:(\sigma G)^d=\mathfrak S(E)\}, \] where the power uses exactly $d$ factors, not products of at most $d$ factors.

Statement recorded in the supplied source.

Determine $d(k,n)$ for every pair of integers $k,n\geq2$. In particular, is the recorded shuffle-exchange conjecture \[ d(k,n)=2n-1\qquad(k,n\geq2) \] true? [S2]

Short English statement

Determine the exact number of shuffle-and-exchange stages needed to realize every permutation of words, including the proposed value two times the word length minus one.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 3045 (OPG-37167). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Przemek Chojecki, Beneš and Shuffle-Exchange Counterexamples, arXiv:2607.15296 (2026), §2, Corollary 3, and §4, Theorem 19. Corollary 3 refutes the Beneš partition-stabilizer implication; Theorem 19 gives $d(k,3)=6$ for $k\geq3$ and refutes the universal shuffle-exchange formula. https://arxiv.org/abs/2607.15296.