Shuffle squares in smooth binary words and the Kolakoski sequence

• GPT-5.6 Sol and GPT-6-Astra performed the mathematical research and proof development, wrote and executed the computational code, and drafted and revised the manuscript.Source: Research contributions and AI disclosure · p. 1
• Kory Kilpatrick supervised the project and takes responsibility for the content as submitting author, but does not claim to have personally derived the proofs or written the code or text.Source: Research contributions and AI disclosure · p. 1
• Verification included exact computational checks and separate AI-agent reviews, but not independent human peer review or proof-assistant formalization.Source: Research contributions and AI disclosure · p. 1

1 Introduction

• The result addresses whether even one Kolakoski prefix is a shuffle square, within the factorial language of smooth words, a more tractable envelope for Kolakoski factors.Source: §1 · p. 2
• Every smooth binary tangram of length at least 18 is a shuffle square.Source: §1 · p. 2
• Exactly 34 smooth binary tangrams are not shuffle squares, and all have length at most 16.Source: §1 · p. 2
• A nonempty Kolakoski prefix is a shuffle square exactly when both letter counts are even and its length is neither 4 nor 8; infinitely many prefixes qualify.Source: §1 · p. 2
• Independent work by Zwierzyński obtained the parity theorem, the same 34 exceptions, and the prefix characterization by a different method, with extensions to finitely differentiable words.Source: §1 · p. 2
• A standalone checker replays positive witnesses and exhausts negative support partitions using a canonical certificate, verifying the finite base through length 40.Source: §1 · p. 2

2.1 Finite differentiation

• A word is smooth when repeated finite differentiation reaches the empty word while every intermediate word remains binary.Source: §2.1 · p. 2
• Every factor of a smooth word is smooth, using the fact that differentiation of a factor remains a factor of the derivative.Source: §2.1 · pp. 2–3

2.2 Two elementary shuffle facts

• Concatenating two shuffle squares produces another shuffle square by joining their corresponding supports.Source: §2.2 · p. 3
• An empty-to-empty FIFO control certifies a shuffle square by matching the symbol streams at the control’s U and D positions.Source: §2.2 · p. 3

3 Parity-return atoms

• Every tangram has a unique factorization into nonempty tangrams with no proper nonempty tangram prefix, cut at returns of prefix parity to zero.These factors are the parity atoms.Source: §3 · p. 3
• The smooth parity atoms include 11 and the four forms 121121, 212212, 12112212, and 21221121, so each has length at most 8.Atoms beginning with 2 are complements of those beginning with 1.Source: §3 · p. 3
• A smooth atom beginning with 1 is either 11 or has form 12(11 | 22)*(12 | 21), with alternating internal double blocks.A differentiable word cannot contain 111 or 222; the first internal double block is 11.Source: §3 · pp. 3–4
• For k ≥1, the derivative of the candidate atom forms contains 222, ruling them out as smooth; at k = 0, two remaining forms and their complements survive.Those forms are 121121 and 12112212.Source: §3 · p. 4

4 Proof of the smooth-word theorem

• The finite-base proposition asserts that every smooth tangram at its stated lengths is a shuffle square, with a certificate providing an empty-to-empty FIFO control for every such word.The standalone checker independently regenerates the complete set of smooth words at these lengths and replays each control.Source: §4 · p. 4
• For n ≥42, strong induction factors a smooth tangram into parity atoms, each smooth and at most 8 letters long.The atoms are smooth because they are factors of the original smooth word.Source: §4 · p. 4
• The proof chooses the first atom boundary c ≥18; because the preceding boundary is at most 16 and the next atom is at most 8 letters, c is at most 24.The boundaries are even.Source: §4 · p. 4

5 Exact finite verification

• Complete primitive expansion generates the smooth words, with induction justified by the derivative's strict contraction of nonempty words.For a fixed nonempty derivative parent, primitives are obtained by choosing the first run symbol and allowed optional singleton boundary runs.Source: §5 · pp. 4–5
• The standalone checker regenerates 16,146 smooth words, covers 4,204 smooth tangrams, replays 4,170 positive controls, and exhausts all 34 negatives.The canonical certificate records each positive control; negative cases are checked by exhausting equal-size support partitions.Source: §5 · p. 5
• The canonical certificate is 291,550 bytes, and a standalone checker regenerates the complete smooth language through length 40.The accompanying README gives a direct command for Python 3.10 or later, and the checker uses only the standard library.Source: §5 · p. 5
• The 34 exceptions are organized into ten orbits under reversal and binary complementation, and every orbit member was checked directly.The orbit sizes sum to 34.Source: §5 · p. 5, Table 2 · p. 6

6 Kolakoski prefixes

• Every finite prefix of the classical Kolakoski sequence is smooth because run-length differentiation of a factor yields a factor of the infinite derivative after boundary trimming.Every infinite derivative of K is again K.Source: §6 · p. 6
• A prefix P_n is a tangram exactly when n and S(n) are both even.The proof obtains infinitely many such tangram boundaries, yielding infinitely many shuffle-square prefixes after the short exceptions.Source: §6 · pp. 6–7
• Infinitely many Kolakoski prefixes have even multiplicities for both letters.The proof rules out finitely many mixed aligned pairs, which would force all sufficiently late run lengths to equal 2.Source: §6 · p. 6
• The only tangram prefixes below length 18 are P4=1221, P8=12211212, and P16=1221121221221121; exhaustive checks show the first two are not shuffle squares, while P16 is.Source: §6 · pp. 6–7
• The infinite Kolakoski sequence is a uniform shuffle square with a coloring whose monochromatic intervals have length at most 48.Each resulting block has length 18–24, and a monochromatic interval can meet at most two consecutive blocks.Source: §6 · p. 7
• The construction groups consecutive parity atoms until each block has length at least 18; atom lengths are even and at most 8.Each resulting block is a smooth tangram and therefore a shuffle square.Source: §6 · p. 7
• Concatenating a shuffle-square coloring for each block makes the two infinite subsequences equal to the concatenation of the blocks' finite roots.The choices of finite roots, and thus the resulting infinite root, need not be unique.Source: §6 · p. 7

7 Concluding remarks

• The general mechanism combines uniformly bounded parity atoms, finite verification above a threshold, and closure under concatenation to obtain an eventual theorem.For binary smooth words, the atom bound is 8 and the threshold is 18.Source: §7 · p. 7
• For binary smooth words, the obstruction set has 34 words.The stated atom bound is 8 and the threshold is 18.Source: §7 · p. 7
• Whether analogous finite-obstruction results hold for generalized smooth languages, larger alphabets, or shuffle powers above two remains an open question.Source: §7 · p. 7