The Kolakoski Sequence and Related Conjectures About Orbits
Bobby Shen · Experimental Mathematics · 2018
The Kolakoski sequence is the unique infinite sequence with values in {1, 2} and first two term 1, 2, … which equals the sequence of run-lengths of itself; we call this K(1, 2). Following Sing and several others, we define K(m, n) similarly for m + n odd [Sing 10 [Sing 10] B. Sing. “More Kolakoski Sequences.” INTEGERS Vol. 11B (2011): Proceedings of the Leiden Numeration Conference, 2010. Available online https://arxiv.org/abs/1009.4061 [Google Scholar]]. The focus of this paper is not on well-known conjectures about limiting densities but rather on conjectures which are more discrete in nature. We define two functions, Em, n and Cm, n, which are naturally encountered when studying iterated run-length encoding and expansion. For the case (m, n) = (1, 2), functions with roughly equivalent concepts were introduced by [Chvatal 1993 [Chvatal 1993] V. Chvatal. “Notes on the Kolakoski Sequence.” Technical Report 93-84. DIMACS. Available online https://users.encs.concordia.ca/∼chvatal/publ.html. [Google Scholar]]. We conjecture that a certain doubly infinite family of finite sequences E1,n(12j,12j) has odd length for all j > 0 and even n > 0. We prove that this statement is equivalent to orbits of certain functions C1, n(1, −) being as large as possible. We empirically verify this for all even n and j ⩽ 13. Our conjecture is different from more common density-type conjectures about the Kolakoski sequence in that our conjecture makes a precise combinatorial statement about infinitely many objects, and our conjecture is far less intuitive.