Monochromatic arithmetic progressions in the Fibonacci, Thue-Morse, and Rudin-Shapiro words
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913888849625088 |
|---|---|
| author | Joshi, Gandhar Rust, Dan |
| author_facet | Joshi, Gandhar Rust, Dan |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_05830 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Monochromatic arithmetic progressions in the Fibonacci, Thue-Morse, and Rudin-Shapiro words Joshi, Gandhar Rust, Dan Dynamical Systems Formal Languages and Automata Theory Combinatorics 52C23, 37B10, 11B85, 68Q45 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. |
| title | Monochromatic arithmetic progressions in the Fibonacci, Thue-Morse, and Rudin-Shapiro words |
| topic | Dynamical Systems Formal Languages and Automata Theory Combinatorics 52C23, 37B10, 11B85, 68Q45 |
| url | https://arxiv.org/abs/2501.05830 |