Consecutive Power Occurrences in Sturmian Words

Bell, Jason; Schulz, Chris; Shallit, Jeffrey

Comptes Rendus. Mathématique, Tome 362 (2024) no. G10, pp. 1273-1278

We show that every Sturmian word has the property that the distance between consecutive ending positions of cubes occurring in the word is always bounded by $10$ and this bound is optimal, extending a result of Rampersad, who proved that the bound $9$ holds for the Fibonacci word. We then give a general result showing that for every $e\in [1,(5+\sqrt{5})/2)$ there is a natural number $N$, depending only on $e$, such that every Sturmian word has the property that the distance between consecutive ending positions of $e$-powers occurring in the word is uniformly bounded by $N$.

Nous montrons que la distance entre deux positions finales consécutives de cubes apparaissant dans un mot sturmien est toujours inférieure ou égale à $10$ et que cette valeur est optimale, étendant ainsi un résultat de Rampersad, qui a démontré que cette distance est majorée par $9$ pour le mot de Fibonacci. Nous donnons ensuite un résultat général montrant que pour tout $e\in [1,(5+\sqrt{5})/2)$ il existe un entier naturel $N$, dépendant uniquement de $e$, tel que la distance entre deux positions finales consécutives de puissances $e$ apparaissant dans un mot sturmien est uniformément majorée par $N$.

Classification : 68R15
Keywords: Sturmian word, cube, periodicity, balanced word
Mots-clés : Mot Sturmien, cube, périodicité, mot équilibré

[1] Baranwal, Aseem R. Decision Algorithms for Ostrowski-automatic Sequences, Memoir, University of Waterloo, School of Computer Science (2020)

[2] Berstel, Jean Fibonacci words—a survey, The Book of L (Rozenberg, G.; Salomaa, A., eds.), Springer, 1986, pp. 13-27 | Zbl | DOI

[3] Baranwal, Aseem R.; Shallit, Jeffrey Critical exponent of infinite balanced words via the Pell number system, Combinatorics on words (Lecture Notes in Computer Science), Volume 11682, Springer, 2019, pp. 80-92 | DOI | MR | Zbl

[4] Baranwal, Aseem R.; Schaeffer, Luke; Shallit, Jeffrey Ostrowski-automatic sequences: theory and applications, Theor. Comput. Sci., Volume 858 (2021), pp. 122-142 | DOI | MR | Zbl

[5] Damanik, David; Lenz, Daniel The index of Sturmian sequences, Eur. J. Comb., Volume 23 (2002) no. 1, pp. 23-29 | DOI | MR | Zbl

[6] Furstenberg, H. Recurrence in ergodic theory and combinatorial number theory, M. B. Porter Lectures, Princeton University Press, 1981, xi+203 pages | MR | Zbl | DOI

[7] Knuth, Donald E. The art of computer programming. Vol. 1. Fundamental algorithms, Addison-Wesley Publishing Group, 1997, xx+650 pages | MR | Zbl

[8] König, Denes Über eine Schlußweise aus dem Endlichen ins Unendliche, Acta Litt. Sci. Szeged, Volume 3 (1927), pp. 121-130 | Zbl

[9] Lothaire, M. Algebraic combinatorics on words, Encyclopedia of Mathematics and Its Applications, 90, Cambridge University Press, 2002, xiv+504 pages | DOI | MR | Zbl

[10] Mousavi, Hamoon Automatic theorem proving in Walnut (2016) (https://arxiv.org/abs/1603.06017)

[11] Mignosi, Filippo; Restivo, Antonio; Salemi, Sergio Periodicity and the golden ratio, Theor. Comput. Sci., Volume 204 (1998) no. 1-2, pp. 153-167 | DOI | MR | Zbl

[12] Rampersad, Narad Prefixes of the Fibonacci word that end with a cube, C. R. Math. Acad. Sci. Paris, Volume 361 (2023), pp. 323-332 | DOI | MR | Zbl

[13] Shallit, Jeffrey Prefixes of the Fibonacci word (2023) (https://arxiv.org/abs/2302.04640)

[14] Shallit, Jeffrey The logical approach to automatic sequences – exploring combinatorics on words with Walnut, London Mathematical Society Lecture Note Series, 482, Cambridge University Press, 2023, xv+358 pages | DOI | MR | Zbl