On evolving chains of cube-free binary sequences

Jacek M. Kowalski and Andrzej Pękalski
Notes on Number Theory and Discrete Mathematics
Print ISSN 1310–5132, Online ISSN 2367–8275
Volume 27, 2021, Number 3, Pages 79–94
DOI: 10.7546/nntdm.2021.27.3.79-94
Full paper (PDF, 217 Kb)

Details

Authors and affiliations

Jacek M. Kowalski
Department of Physics, University of North Texas
Denton TX 76293, United States

Andrzej Pękalski
Institute of Theoretical Physics, University of Wrocław
50-203 Wrocław, Poland

Abstract

Chains of concatenated finite binary words are considered, where each word, except possibly the very first one, is composed of alternating blocks of zeroes and ones with block lengths not exceeding two. These chains are formed following two evolution schemes. The first scheme is standard, where alternating blocks are visited at random. In the second approach, proposed by us in this paper, each subsequent word of the chain is uniquely determined by its immediate predecessor, being formed as a specifically inflated version of that word. Famous Kolakoski sequence is then just one, very special example of such deterministic evolution when one starts from its third element. We present heuristic arguments supported by simulations indicating that all such deterministic infinite chains should have the asymptotic density of digit equal and that the subsequent word lengths asymptotically scale with factor of and hence the density of ’s in subsequent finite words may also tend to .

Keywords

• Automatic sequences
• Random and deterministic evolution of binary words
• Algorithmic combinatorics
• Kolakoski and related sequences
• Scaling law

2020 Mathematics Subject Classification

• 11B83
• 11B85
• 11R45
• 11Y55
• 65B10
• 68R15

References

1. Allouche, J.-P., & Shallit, J. (2003). Automatic Sequences, Cambridge University Press.
2. Allouche, J.-P., & Shallit, J. (2003). The ubiquitous Prouhet–Thue–Morse sequence. In: Ding, C., Helleseth, T., & Niederreiter, H. (eds) Sequences and Their Applications. Proceedings of SETA ’98. Discrete Mathematics and Theoretical Computer Science Series. Springer, London. DOI: 10.1007/978-1-4471-0551-0 1. Available online at: http://ciencias.uis.edu.co/lenguajes/doc/ubiq.pdf.
3. Bernini, A. (2017). Restricted binary strings and generalized Fibonacci numbers. In: Proceedings of 23th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), Springer, Vol. 10248, 32–43.
4. Blanchet-Sadri, F. (2007). Algorithmic Combinatorics on Partial Words. Chapmann & Hall/CRC.
5. Bordellès, O., & Cloitre, B. (2011). Bounds for the Kolakoski sequence. Journal of Integer Sequences, 14, Article 11.2.1.
6. Capri, A. (1993). Repetitions in the Kolakoski sequence. EATCS Bulletin, 50, 194–196.
7. Christandl, M., Datta, N., Ekert, A., & Landhal, A. J. (2004). Perfect state transfer in quantum spin networks. Physical Review Letters, 92(18), Art. No. 187902.
8. Chvátal, V. (1993). Notes on the Kolakoski Sequence. DIMACS Technical Report 93-84. Available online at: https://users.encs.concordia.ca/~chvatal/93-84.pdf.
9. Culik, K., & Karhumäki, J. (1992). Iterative devices generating infinite words. Lecture Notes in Computer Science, 577, 531–544.
10. Culik, K., Karhumäki, J., & Lepisto, A. (1992). Alternating iteration of morphisms and the Kolakoski sequence. In: Rozenberg, G., & Salomaa, A. (eds.), Lindenmayer Systems, Springer, Berlin, 93–106.
11. Currie, J., & Rampersad, N. (2010). Cubefree words with many squares. Discrete Mathematics and Theoretical Computer Science, 12(3), 29–34. Available online at: https://hal.inria.fr/hal-00990439/document.
12. Dekking, M. (1997). What is the long range order in the Kolakoski sequence? In: Moody, R. V. (ed). The Mathematics of Long-Range Aperiodic Order, Kluwer, Dordrecht, 115–125.
13. Haeseler, von F. (2008). Automatic Sequences, Berlin, New York: De Gruyter. DOI: 10.1515/9783110197969.
14. Huang, Y B., & Weakley, W. D. (2010). A note on the complexity of C1-words. Theoretical Computer Science, 411(40–42), 3731–3735.
15. Keane, M. S. (1991). Ergodic theory and subshifts of finite type. In: Bedford, T., Keane, M., & Series, C. (eds.), Ergodic Theory, Symbolic Dynamics and Hyperbolic Spaces, Oxford University Press, 35–70.
16. Kolakoski, W. (1965). Self generating runs, Problem 5304. American Mathematical Monthly, 72, 674.
17. Kuprin, E. J., & Rowland, E. S. (2008). Bounds on the frequency of 1 in the Kolakoski word. Preprint. Available online at: arXiv:08809.2777v2 [mathCP].
18. Lucas, A. (2014). Ising formulation of many NP problems. Frontiers in Physics, 2, 5. DOI: 10.3389/fphy.2014.00005.
19. Oldenburger, R. (1939). Exponent trajectories in symbolic dynamics. Transactions of the American Mathematical Society, 46(3), 453–466.
20. Paun, G., & Salomaa, A. (1966). Self-reading sequences. American Mathematical Monthly, 103(2), 166–168. DOI:10.2307/2975113
21. Sing, B. (2011). More Kolakoski sequences. Integers, 11B, Article No. A14.
22. Sloane, N. J. A. A000002. The On-Line Encyclopedia of Integer Sequences. Available online at: https://oeis.org/A000002.
23. Stanley, R. P. (2013). Algebraic Combinatorics. Undergraduate Texts in Mathematics, Springer, New York.
24. Weisstein, E. W. Kolakoski Sequence. MathWorld–A Wolfram Web Resource. Available online at: https://mathworld.wolfram.com/KolakoskiSequence.html.
25. Wikipedia contributors. (2021). Kolakoski sequence. In: Wikipedia, The Free
    Encyclopedia. Available online at: https://en.wikipedia.org/w/index.php?title=Kolakoski_sequence&oldid=1006035333 .