REVIEW
Shuffle Squares in Differentiable Words
Combinatorics · Submitted 6 Oct 2026 · 21 references
Pith's verdict: Sharp computer-assisted shuffle-square thresholds across the C3/C2/C1 hierarchy; the reductions are sound, and the honest residual risk is the finite base enumerations, which the paper ships code to rerun.
T0 · AI review
Why Pith says this
Highlight any text to comment on it.
Referee report
The paper
The paper claims
Every $C^3$-word longer than 16 letters is a shuffle square exactly when both letter multiplicities are even, a sharp parity law that also characterizes every Kolakoski prefix apart from lengths 4 and 8.
The reading
What carries the argument
Three mechanisms carry the argument. The first is an exact recognizer for shuffle squares: recurrence (4) maintains, after each letter, the set of residual words $q$ recording how far the longer of the two partial copies of the root exceeds the shorter, with $\varepsilon \in Q_{|w|}(w)$ equivalent to being a shuffle square (Proposition 2.8); residual words longer than the remaining letters can be discarded without loss (Remark 2.9), and Listing 2 gives a run-at-a-time variant. The second is the finite derivative $D$ of Definition 3.1 — run-length encoding with one-letter endpoint runs deleted — which grades words into $C^1 \supseteq C^2 \supseteq C^3 \supseteq \cdots \supseteq C^\infty$, with closure under factors, reversal, and complement (Lemma 3.5) making induction over suffixes legitimate. The third is the bad-prefix tree of recurrence (6), enumerating all $C^k$-words with no nonempty shuffle-square prefix: its termination at length 24 for $C^3$ (175 nodes) and at length 40 for $C^2$ (823 nodes) is the finite heart of the sharp-threshold theorems, while for $C^1$ the level counts stabilize at 422 and the residual transitions (19)–(20), with pumping blocks 1122 and 2211, convert that stabilization into a proof of eventual periodicity.
Extended reading notes
Core claim
On the paper's own terms, the discovery is Theorem 1.2: let $w$ be a $C^3$-word over $\{1,2\}$ with $|w|>16$; then $w$ is a shuffle square if and only if $|w|_1 \equiv |w|_2 \equiv 0 \pmod 2$. The constant 16 is sharp, and the exceptional set is exhaustive and permanent: exactly 34 nonempty even-Parikh $C^3$-words are not shuffle squares, all of them smooth, so they are the exceptions in every class $C^k$ with $k \ge 3$ and in the smooth class. The same method yields Theorem 5.7 for $C^2$ (sharp threshold 48, exactly 212 exceptions, the longest sitting at lengths 46 and 48), Theorem 5.8 for $C^1$ (no global parity threshold, but a sharp reduction: every even-Parikh non-shuffle-square of length at least 36 has a proper nonempty shuffle-square prefix and suffix, exactly 230 words have no such prefix, and the bad-prefix tree is eventually the union of 422 periodic rays with periods 1122 and 2211), and Theorem 1.1 for the Kolakoski word (a prefix $P_m$ is a shuffle square if and only if $m$ is an even-Parikh length other than 4 and 8). The paper also characterizes morphisms that reflect shuffle squares in terms of odd powers of private symbols and run-length parity, and, for doubly binary (that is, $C^1$) words, gives the exact deletion distance to a shuffle square, the largest-twin size, and sharp windows for single repairs near an endpoint.
Load-bearing premise
The load-bearing premise is that the finite enumerations behind the sharp thresholds are complete and correctly executed: the text prints the recurrences, pseudocode, and exact counts (46,600 even-Parikh $C^3$-words tested with zero rejections, 175-node and 823-node trees, 34, 212, and 230 exceptions, 422 periodic rays), but the executable verification itself lives in separate Python programs described in Section 10 rather than printed, so a single bug in any enumeration could shift a threshold or hide an exception.
Editorial extensions
If this is right
- Every factor of length greater than 16 in any $C^k$-word with $k \ge 3$, and every factor of any smooth right-infinite binary word, is a shuffle square exactly when its letter multiplicities are even (Corollary 5.3).
- Every finite $C^3$-word admits a greedy factorization into shuffle-square blocks of lengths 2 through 24 with a terminal remainder of length at most 23, and every length-24-locally-$C^3$ right-infinite word has shuffle-square prefix density between $1/24$ and $1/2$ (Theorems 6.2 and 6.6, Corollary 6.7).
- The Kolakoski prefix lengths that are shuffle squares are exactly the even-Parikh lengths except 4 and 8, with consecutive such lengths differing by 2, 4, 6, or 8 and lower density at least $1/8$ (Theorem 1.1, Corollary 7.1).
- A nonerasing morphism between equal-size alphabets reflects shuffle squares if and only if each letter maps to an odd power of a private symbol, and a three-run image criterion gives reflection exactly when, for each letter, at least one of the three run lengths is odd (Corollary 8.5, Theorem 8.10).
- For every doubly binary word the deletion distance to a shuffle square is exactly 0, 1, 2, or 3, with only two exceptional words at distance 3, and every even-Parikh exception can be repaired by one transposition within its last 10 positions or one equal-pair deletion within its last 11, while four balanced appended letters always suffice (Theorems 9.3, 9.4, 9.6).
Reading between the lines
- Editorial inference: the recipe of this paper — a bounded local lemma plus an exhaustively checked finite base — is portable, so the same parity question could be tested on classes defined by forbidding runs longer than some fixed $r$, starting with the runs-of-length-at-most-3 case the paper leaves open in Remark 9.8.
- Editorial inference: the 422-ray terminal description of the $C^1$ bad-prefix tree reads as an explicit finite automaton of infinite words avoiding shuffle-square prefixes; extracting exact level counts and density laws from it, analogous to the $1/24$–$1/2$ bounds proved for locally $C^3$ words, is a natural next step not taken in the paper.
- Editorial inference: because only lengths 4 and 8 fail among Kolakoski prefixes, the paper implies that letter-count parity — computable in linear time — is an exact predictor of shuffle-square status throughout an infinite family of words for which general binary recognition is NP-complete (noted in the paper's introduction); one could test whether the other self-generating run-length sequences o
- Editorial inference: the residual-state recognizer with its pruning bound suggests a practical algorithm whose working memory is controlled by the residual queue length; benchmarking it on long Kolakoski prefixes would test whether the sharp theoretical threshold also gives fast decisions in practice.
Original abstract
Experiments on binary run-length differentiability lead to sharp computer-assisted criteria for shuffle squares. Every $C^3$-word of length greater than $16$ is a shuffle square exactly when both letter multiplicities are even. All $34$ nonempty even-Parikh exceptions are smooth and persist in every higher differentiability class. For $C^2$ the sharp threshold is $48$, with $212$ nonempty exceptions. At level $C^1$ no global parity threshold exists, but every even-Parikh non-shuffle-square of length at least $36$ has proper nonempty shuffle-square prefixes and suffixes. Exactly $230$ nonempty even-Parikh $C^1$-words have no nonempty shuffle-square prefix. The full tree avoiding such prefixes eventually consists of $422$ periodic rays. Consequently, a nonempty Kolakoski prefix is a shuffle square exactly when both multiplicities are even, apart from lengths $4$ and $8$. We also characterize classes of morphisms reflecting shuffle squares. For doubly binary words, we determine the exact deletion distance and largest twins, and prove sharp bounds for single local repairs. Exact recurrences, residual-state checks, and separate Python programs make the finite computations reproducible.
The compiled record
The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
The abstract, sentence by sentence
Experiments on binary run-length differentiability lead to sharp computer-assisted criteria for shuffle squares. Every $C^3$-word of length greater than $16$ is a shuffle square exactly when both letter multiplicities are even. All $34$ nonempty even-Parikh exceptions are smooth and persist in every higher differentiability class. For $C^2$ the sharp threshold is $48$, with $212$ nonempty exceptions. At level $C^1$ no global parity threshold exists, but every even-Parikh non-shuffle-square of length at least $36$ has proper nonempty shuffle-square prefixes and suffixes. Exactly $230$ nonempty even-Parikh $C^1$-words have no nonempty shuffle-square prefix. The full tree avoiding such prefixes eventually consists of $422$ periodic rays. Consequently, a nonempty Kolakoski prefix is a shuffle square exactly when both multiplicities are even, apart from lengths $4$ and $8$. We also characterize classes of morphisms reflecting shuffle squares. For doubly binary words, we determine the exact deletion distance and largest twins, and prove sharp bounds for single local repairs. Exact recurrences, residual-state checks, and separate Python programs make the finite computations reproducible.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | Experiments on binary run-length differentiability lead to sharp computer-assisted criteria for shuffle squares. | contribution 0.46 | 0.88 | 0.09 | asserted 1.00 |
| s1 | Every $C^3$-word of length greater than $16$ is a shuffle square exactly when both letter multiplicities are even. | result 1.00 | 0.82 | 0.50 | asserted 1.00 |
| s2 | All $34$ nonempty even-Parikh exceptions are smooth and persist in every higher differentiability class. | result 1.00 | 0.83 | 0.07 | asserted 1.00 |
| s3 | For $C^2$ the sharp threshold is $48$, with $212$ nonempty exceptions. | result 1.00 | 0.87 | 0.07 | asserted 1.00 |
| s4 | At level $C^1$ no global parity threshold exists, but every even-Parikh non-shuffle-square of length at least $36$ has proper nonempty shuffle-square prefixes and suffixes. | result 1.00 | 0.85 | 0.07 | asserted 1.00 |
| s5 | Exactly $230$ nonempty even-Parikh $C^1$-words have no nonempty shuffle-square prefix. | result 1.00 | 0.88 | 0.06 | asserted 1.00 |
| s6 | The full tree avoiding such prefixes eventually consists of $422$ periodic rays. | result 1.00 | 0.85 | 0.06 | asserted 1.00 |
| s7 | Consequently, a nonempty Kolakoski prefix is a shuffle square exactly when both multiplicities are even, apart from lengths $4$ and $8$. | result 0.84 | 0.82 | 0.36 | asserted 1.00 |
| s8 | We also characterize classes of morphisms reflecting shuffle squares. | contribution 0.95 | 0.88 | 0.04 | asserted 0.99 |
| s9 | For doubly binary words, we determine the exact deletion distance and largest twins, and prove sharp bounds for single local repairs. | result 0.69 | 0.91 | 0.05 | asserted 1.00 |
| s10 | Exact recurrences, residual-state checks, and separate Python programs make the finite computations reproducible. | method 0.99 | 0.90 | 0.02 | asserted 0.99 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
References
Discussion
Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.