PaperlayerView exact revision on arXiv

Source-linked AI summary

Shuffle Squares in Differentiable Words

Michał Zwierzyński

arXiv:2610.07828v1math.COcs.FL

TL;DR

The paper investigates parity-based criteria for recognizing shuffle squares, motivated especially by the characterization of doubly binary words and Kolakoski prefixes. It combines finite-differentiability analysis with exhaustive computations and residual-state methods. It establishes sharp thresholds for C2 words and a precise Kolakoski-prefix characterization, while noting that the C2 result does not cover all doubly binary words.

  • Problem

    The motivating open problem asks for a characterization of shuffle squares among doubly binary words, and experiments raised the question of whether parity characterizes Kolakoski prefixes apart from short exceptions.

    Source: §1 · p. 2

  • Method

    The paper combines exhaustive searches of words avoiding shuffle-square prefixes with residual-state checks to derive bounded local lemmas and finite proofs.

    Source: §1 · p. 3, §5 · p. 11

  • Results

    C2-words longer than 48 satisfy the even-Parikh criterion, and the Kolakoski-prefix characterization excludes lengths 4 and 8 from EPK.

    Source: §1 · pp. 2–3

  • Takeaways & Limitations

    Parity gives an all-word criterion above the stated thresholds for C3 and C2, but no global parity threshold works throughout C1.

    Source: §1 · p. 3, §5.3 · p. 15

    The C2 result solves the doubly binary shuffle-square problem only on a proper subclass, since the odd-ABBA family lies outside C2.

    Source: §3 · p. 9

Abstract

from arXiv · show

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.

1. Introduction

The paper develops sharp shuffle-square criteria for finite differentiability classes and uses them to characterize Kolakoski prefixes. It also extends the structural results to morphisms, doubly binary words, and local repairs, with finite computations specified for reproducibility.

1. Introduction

  • Earlier results showed that almost all binary words with even Parikh vector are shuffle squares; this paper gives sharp criteria for every sufficiently long word in specified differentiability classes.The paper also derives bounded-block factorizations in Ck for k ≥ 3, including from every position in certain right-infinite words.Source: §1 · pp. 2–3
  • The motivating problem asks which doubly binary words are shuffle squares; the paper gives partial answers for subclasses and an exact characterization for Kolakoski prefixes.The initial experiments compared letter-count parities with exact recognition for finite Kolakoski prefixes.Source: §1 · p. 2
  • A nonempty Kolakoski prefix is a shuffle square exactly when its length belongs to EPK, except for lengths 4 and 8.The characterization is deduced from the finite-differentiability theorem together with short-word arguments.Source: §1 · pp. 2–3
  • For C3-words, the sharp threshold is 16, with 34 nonempty even-Parikh exceptions; for C2-words, the sharp threshold is 48, with 212 exceptions.All 34 C3 exceptions are smooth and therefore persist in every higher differentiability class.Source: §1 · p. 3
  • At C1, no global parity threshold exists, while the bad-prefix tree settles into 422 surviving words per level and yields 422 verified periodic rays.The paper uses residual loops and exits, rather than count stabilization alone, to establish eventual periodicity.Source: §1 · pp. 3–4
  • The paper classifies morphisms reflecting shuffle squares in specified settings and determines deletion distances, largest twins, and sharp windows for local repairs in doubly binary words.The local-repair results include windows of 10 and 11 positions for exceptions, a 15-position window for C1-preserving transpositions, and a bound of 6 for equal-pair insertion.Source: §1 · pp. 3–4
  • The finite computations are specified through recurrences, exact counts, and pseudocode, with separate executable implementations supplied for the recognizers.The C3 and C2 bad-prefix trees have 175 and 823 nodes, respectively; the C1 tree is described by 422 verified periodic rays.Source: §1 · p. 4

2. Shuffle squares and an exact residual-state test

A shuffle square partitions a word’s positions into two identical subsequences, so even letter multiplicities are necessary but not sufficient. The section gives exact residual-state and run-based procedures for recognizing shuffle squares.

2. Shuffle squares and an exact residual-state test

  • A shuffle square partitions positions into two sets whose induced subwords are identical; the common subword is its shuffle-square root.The same condition can be viewed as coloring positions red and blue so the two resulting subwords coincide.Source: §2 · p. 5
  • Every shuffle square has even multiplicity of each letter, but the converse fails: 1221 has even multiplicities and is not a shuffle square.Its possible roots are 12 and 21, and neither can be assigned to two copies respecting the word’s order.Source: §2 · p. 5
  • Shuffle squares are closed under concatenation, reversal, and binary complementation.These operations preserve a decomposition into two equal induced subwords.Source: §2 · p. 5

2.1. An exact recognizer.

  • The residual recurrence recognizes a nonempty word as a shuffle square exactly when the empty residual is reachable after its final letter.Each state records the unmatched suffix between two prefix-comparable partial copies; transitions either extend that suffix or cancel its first letter.Source: §2.1 · pp. 5–6
  • The decision procedure implements the residual recurrence and prunes states longer than the remaining input, which cannot reach the empty residual.The pruning is lossless because each subsequent transition changes residual length by exactly one.Source: §2.1 · p. 6
  • The run-capacity procedure is also exact, scanning each run by splitting its positions between the two copies and retaining feasible residuals.Canonical perfect twins permit each run’s first-copy positions to precede its second-copy positions.Source: §2.1 · pp. 6–7

3. Run-length encoding and differentiability classes

The finite derivative handles ambiguous endpoint runs in finite run-length encoding and defines the differentiability hierarchy. The section establishes closure properties and relates finite smooth words to factors of smooth infinite words.

3. Run-length encoding and differentiability classes

  • The finite derivative removes endpoint ambiguity by deleting boundary run-length symbols equal to 1 after run-length encoding, provided no run exceeds length 2.Ordinary run-length encoding alone does not faithfully record a run cut at either endpoint.Source: §3 · p. 8
  • A finite word is smooth when its finite derivatives remain defined until reaching the empty word; Ck-words are those with k defined derivative levels.The convention D(ε) = ε allows a derivative tower that reaches the empty word early to continue.Source: §3 · p. 8
  • The hierarchy has distinct levels: 11211211 belongs to C2 but not C3, and these words are the shortest such examples, together with their complements.The complete enumeration through length 8 establishes their minimality.Source: §3 · p. 8
  • Every factor of a Ck-word is Ck, and reversal and binary complementation preserve membership; the corresponding closure statements also hold for smooth words.The factor property follows by tracking how endpoint run fragments behave under the finite derivative.Source: §3 · p. 9
  • Every finite factor of a smooth right-infinite binary word is a finite smooth word, so every finite factor of the Kolakoski word is smooth.The result follows because the Kolakoski word is smooth as a right-infinite word.Source: §3 · pp. 9–10

4. Even prefixes of the Kolakoski word

The section studies lengths of Kolakoski prefixes with even letter counts. It proves there are infinitely many such lengths and bounds the gaps between consecutive ones.

4. Even prefixes of the Kolakoski word

  • Membership in EPK can be tested by requiring an even prefix length and an even number of 1s.Because the total length is even, the number of 2s is then even as well.Source: §4 · p. 10
  • The set EPK of lengths with even Parikh vector is infinite, and consecutive elements differ by at most 8.The proof groups the Kolakoski word into aligned pairs and tracks when the parity of the number of ones changes.Source: §4 · p. 10
  • After a mixed aligned pair, another mixed pair occurs within the next three aligned pairs, restoring even parity.Equal aligned pairs leave the parity unchanged, and three consecutive equal aligned pairs are impossible.Source: §4 · p. 10

5. Shuffle squares in finite differentiability classes

The section establishes sharp parity criteria for shuffle squares in C^k-words for k ≥ 2 and analyzes even-Parikh C^1 non-squares through exact residual-state recognition and finite enumeration. In C^1, it identifies a finite core of 230 words with no shuffle-square prefix and shows that sufficiently long even-Parikh non-squares have proper shuffle-square prefixes and suffixes, while greedy removal leaves a bounded terminal remainder despite there being no uniform bound on shuffle-square block lengths.

5. Shuffle squares in finite differentiability classes.

  • The finite checks use an exact residual-state test to enumerate C^k-words, even-Parikh words, and even-Parikh words rejected as non-squares.A separate recurrence enumerates words with no nonempty shuffle-square prefix, pruning extensions that are not C^k-words or are shuffle squares.Source: §5 · p. 11

5.1. Differentiability of order at least three.

  • For every k ≥ 3, an even-Parikh C^k-word of length greater than 16 is a shuffle square; exactly 34 nonempty exceptions remain, all smooth.The threshold and exception set are unchanged for smooth words and every higher differentiability class. Every C3-word of length 24 has nonempty shuffle-square prefixes and suffixes, and that local bound is optimal.Source: §5.1 · pp. 11–12

5.2. The class C2.

  • Exactly 212 nonempty even-Parikh C2-words are not shuffle squares; every C2-word of length greater than 48 is a shuffle square exactly when its Parikh vector is even.The bound 48 is sharp. Every finite C2-word can also be decomposed into C2 shuffle-square blocks of lengths 2–40 and a terminal remainder of length at most 39; both bounds are sharp.Source: §5.2 · pp. 13, 15

5.3. The class C1.

  • 230 nonempty even-Parikh C1-words lack a nonempty shuffle-square prefix; all have length at most 34, while non-squares of length at least 36 have proper square prefixes and suffixes.The threshold 36 is sharp among admissible even lengths. There is no global parity threshold in C1: odd-ABBA words (2112)^(2j+1) are even-Parikh non-squares of unbounded length [10].Source: §5.3 · pp. 15–16, Table 5 · p. 16
  • Exactly 230 even-Parikh C1-words have no nonempty shuffle-square prefix; the prefix-avoiding tree has 422 words at every level n ≥ 38, none with even Parikh vector.The bad continuations from each seed form periodic rays, with patterns (1122)^ω and (2211)^ω.Source: §5.3 · p. 17
  • Every even-Parikh C1-word of length at least 36 with no shuffle-square prefix is impossible, so every non-shuffle-square word under those conditions has proper shuffle-square prefixes and suffixes.The threshold is sharp: an even-Parikh exception with no such prefix has length 34.Source: §5.3 · p. 17
  • Every nonempty even-Parikh C1-word has a greedy factorization into shuffle squares and a terminal remainder that is empty or one of 230 exceptions, with length at most 34.The remainder is nonempty whenever the original word is not itself a shuffle square.Source: §5.3 · p. 18
  • When r ≠ ε, there is no uniform upper bound on the lengths of the blocks Si.Source: §5.3 · p. 18
  • For odd W_{2j+1}=(2112)^{2j+1}, greedy factorization removes the shortest shuffle-square prefix S exactly j times and leaves W_1=2112, although none of these words is a shuffle square [10].S is an ordinary square; prefixes of lengths 2 and 6 have odd letter multiplicities, and the length-4 prefix 2112 is an obstruction.Source: §5.3 · p. 18

6. Bounded local factorizations

Finite C3-words admit short shuffle-square factors with strong coverage guarantees, and the same bounded-block construction extends to locally differentiable infinite words. The corresponding C2 results use larger bounds.

6. Bounded local factorizations

  • At least n − 23 shuffle-square occurrences start at distinct positions in every C3-word of length n ≥ 24.Each possible starting position through n − 23 begins a shuffle-square factor of length 2, 4, …, or 24.Source: §6 · pp. 18–19
  • Every finite C3-word factors greedily into shuffle squares of lengths 2–24 followed by a remainder of length at most 23.The concatenation of the removed blocks is itself a shuffle square, and the remainder bound 23 is optimal even for smooth words.Source: §6 · p. 19
  • For every C3-word of length n ≥ 24, both a shuffle-square prefix and suffix have length at least n − 23.The greedy construction gives the prefix; applying it to the reversal gives the suffix.Source: §6 · p. 19
  • The greedy remainder does not determine whether the original word is a shuffle square: P20 is a shuffle square although its remainder 1221 has no shuffle-square prefix.Source: §6 · p. 19
  • From any starting position in a length-24 locally C3 right-infinite word, repeatedly taking the shortest shuffle-square prefix yields blocks of length at most 24 and shuffle-square cumulative factors.The recursion continues indefinitely.Source: §6 · p. 20
  • The infinite-word conclusions extend to length-40 locally C2 words, with block bound 40 and lower density bound 1/40.For bi-infinite locally C3 words, suitable cuts give shuffle-square blocks and factors of lengths 2–24 at each eligible start and end position.Source: §6 · pp. 18, 20

7. Characterization of all shuffle-square prefixes

The paper characterizes exactly which nonempty prefixes of the Kolakoski word are shuffle squares: precisely those with even letter multiplicities, except at lengths 4 and 8. A greedy block construction gives an infinite, proper subsequence of those prefix lengths.

7. Characterization of all shuffle-square prefixes

  • A nonempty Kolakoski prefix is a shuffle square exactly when both letter multiplicities are even, except at lengths 4 and 8.The characterization was also obtained independently by Kilpatrick [14, Theorem 1.3].Source: §7 · p. 21
  • The shuffle-square prefix-length sequence of K is infinite, and each pair of consecutive terms differs by 2, 4, 6, or 8.Source: §7 · p. 21
  • Greedily taking the shortest shuffle-square block at each step yields shuffle-square cumulative prefixes beginning at lengths 16, 34, 36, 48, and 56.These endpoints form an infinite proper subsequence of the shuffle-square prefix lengths; for example, 20 is a shuffle-square prefix but not a recursive endpoint.Source: §7 · p. 22
  • The first greedy block is P16, and the next two are K17…K34 and K35K36 = 22, giving cumulative endpoints 16, 34, and 36.The cited decompositions provide direct checks of the blocks.Source: §7 · pp. 21–22

8. Morphisms reflecting shuffle squares

This section gives criteria for morphisms that reflect shuffle squares, meaning that a word is a shuffle square whenever its image is one. It first characterizes the equal-alphabet-size case, then uses ordered-graph extraction for broader classes of morphisms.

8. Morphisms reflecting shuffle squares

  • A nonerasing morphism preserves shuffle squares, and it reflects them when the converse implication also holds.Source: §8 · p. 22

8.1. Odd powers and private symbols.

  • Any morphism mapping each letter a to an odd power a^k_a reflects shuffle squares.The proof selects matching positions so exactly one survives from each original letter block.Source: §8.1 · p. 23
  • If a nonerasing morphism reflects shuffle squares, each source letter must have a private target symbol, so the target alphabet is at least as large as the source alphabet.Source: §8.1 · p. 23
  • Private symbols with odd multiplicity suffice for reflection even when other target symbols occur in multiple images.The example h(a) = 2137 and h(b) = 4137 reflects shuffle squares; merely having private symbols is not sufficient in general.Source: §8.1 · pp. 23–24
  • When the finite source and target alphabets have equal size, reflection holds exactly for morphisms mapping each letter to a positive odd power of a distinct target letter.Source: §8.1 · p. 24

8.2. Extraction from ordered graphs.

  • For the structured images in Theorem 8.9, odd block counts and specified endpoint/interior parities guarantee reflection, using matching extraction from a nest-free ordered graph.A fixed matching keeps the selections for different source letters compatible in the original word.Source: §8.2 · p. 25
  • For three-run images with disjoint symbol pairs, reflection holds exactly when each source letter has at least one odd run exponent.If all three exponents for a letter are even, its image is a shuffle square although the one-letter source is not.Source: §8.2 · pp. 25–26
  • The ordered-graph extraction handles arbitrary arrangements of different-letter images; the obstruction can depend on their order even when separate projections are shuffle squares.The proofs use one fixed matching throughout, and require no finite computational check.Source: §8.2 · p. 26

9. Local repairs and largest twins in doubly binary words

Section 9 gives exact deletion-distance and largest-twin results for doubly binary words, then establishes sharp local repairs and balanced completions for even-Parikh words. The repair guarantees have precise endpoint windows and scope boundaries.

9.1. Deletion distance and largest twins. 

  • Every nonempty even-length word has deletion distance 2; every odd-length word has distance 1, except two words in (29), whose distance is 3.Source: §9.1 · p. 27
  • At length 2m+1, the largest twin length is m except for two words, each with maximum 4; at length 2m, it is m−1 for nonempty words.Twins are identical subwords on disjoint position sets; perfect twins together cover every position.Source: §9.1 · pp. 26–28

9.2. One repair near an endpoint.

  • For even-Parikh C1 words, an adjacent transposition within the last 10 positions or equal-pair deletion within the last 11 makes a shuffle square.Both locality constants are optimal, and corresponding left-endpoint guarantees follow by reversal.Source: §9.2 · p. 29
  • A transposition within the last 15 positions can preserve C1; inserting an equal pair before a suffix of length at most 6 also yields a C1 shuffle square.The constants 15 and 6 are optimal.Source: §9.2 · p. 29
  • Equal-pair deletion cannot always be required to preserve C1: deleting either available pair from 12211212 leaves that class.One resulting word is a shuffle square and the other is not, but neither is doubly binary.Source: §9.2 · p. 30

9.3. Completion at the endpoint and longer runs.

  • Every even-Parikh C1 word can be completed to a C1 shuffle square by appending at most four letters, and four are sometimes necessary.The completion construction chooses among six balanced four-letter suffixes for the terminal remainder.Source: §9.3 · p. 31
  • Every binary word with even Parikh vector can be reduced to a shuffle square using at most E(w)+1 adjacent equal-pair deletions.The bound is sharp for 122k1, which requires exactly k=E(w)+1 such deletions.Source: §9.3 · p. 31
  • The single-repair result does not extend unchanged to words with run lengths at most 3; 12221112 requires at least two equal-pair deletions.Whether two such deletions always suffice in that larger class remains open in the paper.Source: §9.3 · p. 32

10. Scope of the computer assistance

The finite computations are paired with arguments showing why their bounded checks establish the stated results for arbitrary lengths. Supplementary Python programs regenerate the inputs and reproduce the checks.

10. Scope of the computer assistance

  • Finite checks support arbitrary-length results through induction for C3, terminating extension layers for C2, and residual loops and exits for the 422 C1 rays.For deletion-distance results, residual cycles and absorption transitions cover every ray phase and long minimal shuffle-square prefix.Source: §10 · p. 33
  • The verification programs regenerate their input sets without external data and include the finite checks for differentiability classes, periodic rays, deletion bounds, local repairs, and completions.Separate programs verify C1/C2/C3 computations and local repairs; a shared module supplies recognition and residual-transition routines.Source: §10 · p. 33
  • The exact recognizers agree on every nonempty binary word through length 16, while run and letter recurrences are checked against literal support enumeration through length 12.The latter comparison covers all 8,191 binary words through length 12, including the empty word.Source: §10 · p. 33
  • No bounded testing of morphisms or additional enumeration of smooth words is used in these proofs; Kolakoski arguments also assume no letter or factor frequencies.The Kolakoski characterization follows from the C3 theorem and explicit short-word arguments.Source: §10 · p. 33
Loading 2610.07828v1…