Consecutive Power Occurrences in Sturmian Words

Jason Bell; Chris Schulz; Jeffrey Shallit

doi:10.5802/crmath.644

Article de recherche - Informatique théorique

Consecutive Power Occurrences in Sturmian Words
[Occurrences consécutives de puissance dans les mots sturmiens]

Jason Bell ¹ ; Chris Schulz ¹ ; Jeffrey Shallit ²

¹ University of Waterloo, Department of Pure Mathematics, 200 University Avenue West, Waterloo, Ontario N2L 3G1, Canada
² University of Waterloo, School of Computer Science, 200 University Avenue West, Waterloo, Ontario N2L 3G1, Canada

Comptes Rendus. Mathématique, Volume 362 (2024), pp. 1273-1278.

Résumé
Abstract

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$ .

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$ .

Reçu le : 2024-02-19
Révisé le : 2024-03-26
Accepté le : 2024-04-21
Publié le : 2024-11-05

Zbl

DOI : 10.5802/crmath.644

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

Affiliations des auteurs :

Jason Bell ¹ ; Chris Schulz ¹ ; Jeffrey Shallit ²

¹ University of Waterloo, Department of Pure Mathematics, 200 University Avenue West, Waterloo, Ontario N2L 3G1, Canada
² University of Waterloo, School of Computer Science, 200 University Avenue West, Waterloo, Ontario N2L 3G1, Canada

Licence :

CC-BY 4.0

Droits d'auteur : Les auteurs conservent leurs droits

@article{CRMATH_2024__362_G10_1273_0,
     author = {Jason Bell and Chris Schulz and Jeffrey Shallit},
     title = {Consecutive {Power} {Occurrences} in {Sturmian} {Words}},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {1273--1278},
     publisher = {Acad\'emie des sciences, Paris},
     volume = {362},
     year = {2024},
     doi = {10.5802/crmath.644},
     zbl = {07939458},
     language = {en},
}

TY  - JOUR
AU  - Jason Bell
AU  - Chris Schulz
AU  - Jeffrey Shallit
TI  - Consecutive Power Occurrences in Sturmian Words
JO  - Comptes Rendus. Mathématique
PY  - 2024
SP  - 1273
EP  - 1278
VL  - 362
PB  - Académie des sciences, Paris
DO  - 10.5802/crmath.644
LA  - en
ID  - CRMATH_2024__362_G10_1273_0
ER  -

%0 Journal Article
%A Jason Bell
%A Chris Schulz
%A Jeffrey Shallit
%T Consecutive Power Occurrences in Sturmian Words
%J Comptes Rendus. Mathématique
%D 2024
%P 1273-1278
%V 362
%I Académie des sciences, Paris
%R 10.5802/crmath.644
%G en
%F CRMATH_2024__362_G10_1273_0

Jason Bell; Chris Schulz; Jeffrey Shallit. Consecutive Power Occurrences in Sturmian Words. Comptes Rendus. Mathématique, Volume 362 (2024), pp. 1273-1278. doi : 10.5802/crmath.644. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.5802/crmath.644/

Bibliographie
Cité par

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

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

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

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

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

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

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

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

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

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

[12] Narad Rampersad 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] Jeffrey Shallit Prefixes of the Fibonacci word (2023) (https://arxiv.org/abs/2302.04640)

[14] Jeffrey Shallit 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

Cité par Sources :

Commentaires - Politique