More Variations on Shuffle Squares

NEW

Problem: Reconstructed statement: for every integer $k\ge 2$, fixing an alphabet $A$ with $|A|=k$, there is a constant $c_k<\infty$ such that every finite word $T\in A^*$ in which each letter occurs an even number of times satisfies

where $S_k$ is the set of shuffle squares over $A$, and $\operatorname{cut}(U,W)$ is the minimum number of cuts needed to factor $U$ into contiguous pieces and permute those pieces to obtain $W$. Also $\operatorname{cut}(U,S_k)=\min_{W\in S_k}\operatorname{cut}(U,W)$.

Result: The conjecture is false. In fact, for every $k\ge 5$ and every fixed $c$, there exist $k$-ary tangrams $T$ with

Proof. Fix $k\ge5$, and let $A$ be a $k$-letter alphabet. Consider words of length $2n$.

First count tangrams. The number of words in $A^{2n}$ in which every letter occurs an even number of times is

using the two sign choices $(+,\dots,+)$ and $(- ,\dots,-)$.

Next count shuffle squares. A shuffle square of length $2n$ is determined, non-uniquely, by a root word $X\in A^n$ and a choice of the $n$ positions occupied by one copy of $X$. Hence

Now fix $c$. If a word $T$ has $\operatorname{cut}(T,S_k)\le c$, then some shuffle square $W\in S_k\cap A^{2n}$ can be cut into at most $c+1$ contiguous blocks and permuted to obtain $T$. For each fixed $W$, the number of such block rearrangements is at most

a polynomial in $n$ depending only on $c$. Therefore the number of length-$2n$ words within cutting distance $c$ of $S_k$ is at most

For $k\ge5$, we have $4k<k^2$. Thus, for sufficiently large $n$,

So not all length-$2n$ tangrams can lie within cutting distance $c$ of $S_k$. Hence some $k$-ary tangram $T$ satisfies $\operatorname{cut}(T,S_k)>c$.

Since $c$ was arbitrary, no finite constant $c_k$ exists for any $k\ge5$. This disproves Conjecture 3.

Verification audit: the argument uses exactly the paper’s notions of tangram, shuffle square, and cutting distance; it introduces no extra structural assumptions. The counterexample is nonconstructive but rigorous by counting. It falsifies the universal claim already at $k=5$.

Citation: Definitions and conjecture source: Jarosław Grytczuk, Bartłomiej Pawlik, Mariusz Pleszczyński, “More Variations on Shuffle Squares,” Symmetry 15(11), 1982, 2023. The disproof above is the counting argument given here.