Kolakoski Sequence Analysis

A structural Analysis of the Kolakoski density limit via Graph Isomorphism.

ConceptManifold Theory

Result

\rho \approx 0.5

ToolsPython / NetworkX

The Kolakoski sequence is the unique sequence over $\{1, 2\}$ that describes its own run lengths. A central open problem asks whether the density of 1s converges to exactly 0.5.

Analysis through an 8-bit sliding window reveals the sequence is confined to a manifold of 34 states rather than exploring the full 256-state space. This closed loop exhibits perfect bitwise symmetry, suggesting the density is structurally constrained to 0.5.

Reading index 2 (2) → Appending 2 x 1s

Variant Analysis: (1, 3) Sequence

To challenge the Random Walk hypothesis, we analyzed the sequence over $\{1, 3\}$ . If density were universal, it should balance. Instead, we observed a collapse:

Kolakoski (1, 2)50.00%Unbiased Feedback

Variant (1, 3)39.72%Narcissism Coeff > 0

The Problem

The Kolakoski Sequence is the unique sequence of 1s and 2s starting with 1, 2, 2... that is its own Run Length Encoding.

K = 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 2, 2, 1, 1...

Despite its simple definition, the asymptotic density of 1s ( $\rho$ ) remains an open problem. Keane (1991) conjectured $\rho = 0.5$ .

The 34-State Loop

It turns out the chaos is an illusion. The sequence is actually walking along a rigid, 34-node cycle hidden inside the 256-node space.

State ID	Pattern	Next State
0x1A	00011010	0x35
0x35	00110101	0x6A
0x6A	01101010	0xD5
0xD5	11010101	0xAB

Kolakoski 34-State Manifold - Closed Loop Graph

Current Limitations

While the graph isomorphism is compelling, we have not formally established that the sequence must traverse the entire graph uniformly. It remains theoretically possible (though unlikely) for the sequence to get trapped in a non-symmetric sub-cycle, although we have found no such cycle up to $N=10^{10}$ .

Observation: Traffic Symmetry

The State Transition Graph $G$ appears isomorphic to its complement $\bar{G}$ under the mapping $f(x) = \text{NOT}(x)$ .

This implies that for every path leading to an excess of 1s, there exists an identical mirror path leading to an excess of 2s. The sequence likely complies with this symmetry, rendering the 0.5 density a structural necessity.

References

[1] Kolakoski, W. (1965). Self-generating runs, Problem 5304. American Mathematical Monthly, 72, 674.

[2] Keane, M. (1991). "Ergodic theory and subshifts of finite type." In Ergodic Theory, Symbolic Dynamics, and Hyperbolic Spaces (pp. 35-70). Oxford University Press.

[3] Dekking, F. M. (1997). "What is the long range order in the Kolakoski sequence?" In The Mathematics of Long-Range Aperiodic Order (pp. 115-125). Springer.

[4] Nilsson, J. (2013). "On the entropy of a family of random substitutions." Monatshefte für Mathematik, 166(1), 1-15.

[5] OEIS Foundation. (2024). "The On-Line Encyclopedia of Integer Sequences." Sequence A000002. oeis.org/A000002