Monochromatic arithmetic progressions in the Fibonacci, Thue-Morse, and Rudin-Shapiro words
arXiv:2501.05830 · doi:10.1016/j.tcs.2025.115391
Abstract
We investigate the lengths and starting positions of the longest monochromatic arithmetic progressions for a fixed difference in the Fibonacci word. We provide a complete classification for their lengths in terms of a simple formula. Our strongest results are proved using methods from dynamical systems, especially the dynamics of circle rotations. We also employ computer-based methods in the form of the automatic theorem-proving software Walnut. This allows us to extend recent results concerning similar questions for the Thue-Morse word and the Rudin-Shapiro word. This also allows us to obtain some results for the Fibonacci word that do not seem to be amenable to dynamical methods.
arXiv commentChanges made to address feedback from anonymous referee. Accepted for publication in Theoretical Computer Science