The Kolakoski Sequence and Related Conjectures About Orbits

ABSTRACT

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]. 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, E_{m, n} and C_{m, 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]. We conjecture that a certain doubly infinite family of finite sequences $E_{1,n}(1^{2^j},1^{2j})$ has odd length for all j > 0 and even n > 0. We prove that this statement is equivalent to orbits of certain functions C_{1, 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.

KEYWORDS:

• Kolakoski sequence
• recurrence

2000 AMS Subject Classification:

• 05A99

Acknowledgments

The author originally researched this problem with Yongyi Chen and Michael Yan as a part of MIT’s class Math Project Lab in Spring 2016. Our main paper for this project is at [Chen et al. 2015]. Conjecture 3.1 was first observed by Yongyi Chen for n = 2.

Notes

1 We explicitly write the subscripts 1 and 2 because we generalize the construction to (m, n) other than (1, 2).

2 We will omit the details, but here is the reason. WLOG, (r₀, r₁, r₂) = (1/2, 0, 1/2). Then u⁽⁰⁾ has even length and odd sum, and E(u⁽⁰⁾, t₀) has odd length and sum congruent to $1-2r_3\left(\text{mod}2\right).$ Let b ≔ 1 − 2r₃. One can show that b has the same parity as either the sum of all terms if u⁽⁰⁾ with even index or the sum of all terms with odd index; this depends on the parity of t₀. Recall that we asked if this information determined the parity of b. The answer is no, as long as u⁽⁰⁾ is restricted to some constant even length (greater than 0). This is because knowing that the sum of all elements of u⁽⁰⁾ has odd parity and that u⁽⁰⁾ has even length tells us nothing about the parity of the sum of the elements of u⁽⁰⁾ with even indices, nor with odd indices. In fact, we know that one of these sums must be even, and the other sum must be odd, b = 0 one-half of the time.