Shuffle squares in smooth binary words and the Kolakoski sequence
Abstract
A binary word is a shuffle square if its positions can be partitioned into two identical subsequences. A finite word over {1,2} is smooth if repeated finite run-length differentiation remains binary until the empty word is reached. This paper proves that every smooth binary word in which both letters have even multiplicity is a shuffle square once its length is at least $18$. There are exactly $34$ exceptions, all of length at most $16$. The infinite part of the proof is a parity-return atom induction: a smooth even-Parikh word factors uniquely into smooth parity atoms, and every such atom has length at most $8$. A finite, independently checkable certificate handles lengths $18$ through $40$. As a consequence, a nonempty prefix of the classical Kolakoski sequence is a shuffle square if and only if both symbols occur an even number of times and its length is not $4$ or $8$. There are infinitely many such prefixes. In fact, the entire infinite Kolakoski sequence can be partitioned into two identical infinite subsequences with monochromatic blocks of uniformly bounded length.
Related
- Shuffle Squares in Differentiable Words
- A family of spectral conjugate gradient algorithms derived by least-squares approximations based on a modified quasi--Newton update with application to a revised robust binary classification model
- Cross-validated feature selection using least-squares support vector machines for binary classification
- Inverse powers and 2-adic properties of binary 3 x 3 matrices associated with the Tribonacci sequence
- The full Kolakoski shift is topologically transitive
BibTeX
@misc{kilpatrick2026shuffle,
title = {{Shuffle squares in smooth binary words and the Kolakoski sequence}},
author = {Kory Kilpatrick},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.02262},
eprint = {2610.02262},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.02262},
}
RIS
TY - UNPB
TI - Shuffle squares in smooth binary words and the Kolakoski sequence
AU - Kory Kilpatrick
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2610.02262
UR - https://arxiv.org/abs/2610.02262
AB - A binary word is a shuffle square if its positions can be partitioned into two identical subsequences. A finite word over {1,2} is smooth if repeated finite run-length differentiation remains binary until the empty word is reached. This paper proves that every smooth binary word in which both letters have even multiplicity is a shuffle square once its length is at least $18$. There are exactly $34$ exceptions, all of length at most $16$. The infinite part of the proof is a parity-return atom induction: a smooth even-Parikh word factors uniquely into smooth parity atoms, and every such atom has length at most $8$. A finite, independently checkable certificate handles lengths $18$ through $40$. As a consequence, a nonempty prefix of the classical Kolakoski sequence is a shuffle square if and only if both symbols occur an even number of times and its length is not $4$ or $8$. There are infinitely many such prefixes. In fact, the entire infinite Kolakoski sequence can be partitioned into two identical infinite subsequences with monochromatic blocks of uniformly bounded length.
ER -