Fonctions de récurrence des suites d’Arnoux-Rauzy et réponse à une question de Morse et Hedlund  [ Recurrence functions of Arnoux-Rauzy sequences, and answer to a question of Morse and Hedlund ]
Annales de l'Institut Fourier, Volume 56 (2006) no. 7, p. 2249-2270

The recurrence function R(n) of a symbolic sequence counts how long one has to wait to see every word of length n. We compute it explicitly for the Arnoux-Rauzy sequences, which are defined by combinatorial conditions making them a natural generalization of the Sturmian sequences. We then answer a question of Morse and Hedlund (1940) by showing that R(n) n cannot have a finite limit for any non-eventually periodic sequence.

La fonction de récurrence R(n) d’une suite symbolique compte au bout de combien de temps on voit tous les mots de longueur n. Nous la calculons explicitement pour les suites d’Arnoux-Rauzy, définies par des conditions combinatoires qui en font une généralisation naturelle des suites sturmiennes. Puis nous répondons à une question de Morse et Hedlund (1940) en montrant que R(n) n ne peut avoir une limite finie pour aucune suite non ultimement périodique.

DOI : https://doi.org/10.5802/aif.2239
Classification:  37B20,  37B10,  68R15
Keywords: symbolic dynamics, combinatorics on words, infinite word, recurrence function, Arnoux-Rauzy sequence, Rauzy graph, bispecial factor, singular word, return word 
@article{AIF_2006__56_7_2249_0,
     author = {Cassaigne, Julien and Chekhova, Nataliya},
     title = {Fonctions de r\'ecurrence des suites d'Arnoux-Rauzy et r\'eponse \`a une question de Morse et Hedlund},
     journal = {Annales de l'Institut Fourier},
     publisher = {Association des Annales de l'institut Fourier},
     volume = {56},
     number = {7},
     year = {2006},
     pages = {2249-2270},
     doi = {10.5802/aif.2239},
     mrnumber = {2290780},
     zbl = {1138.68045},
     language = {fr},
     url = {http://www.numdam.org/item/AIF_2006__56_7_2249_0}
}

Cassaigne, Julien; Chekhova, Nataliya. Fonctions de récurrence des suites d’Arnoux-Rauzy et réponse à une question de Morse et Hedlund. Annales de l'Institut Fourier, Volume 56 (2006) no. 7, pp. 2249-2270. doi : 10.5802/aif.2239. http://www.numdam.org/item/AIF_2006__56_7_2249_0/

[1] Alessandri, P. Codages de rotations et basses complexités, Université Aix-Marseille II (1996) (Ph. D. Thesis)

[2] Arnoux, P.; Rauzy, G. Représentation géométrique de suites de complexité 2n+1, Bull. Soc. Math. France, Tome 119 (1991), pp. 199-215 | Numdam | MR 1116845 | Zbl 0789.28011

[3] Cassaigne, J. Special factors of sequences with linear subword complexity, Developments in Language Theory (Magdeburg, 1995) (1996), pp. 25-34 (World Scientific) | MR 1466182 | Zbl 1096.68690

[4] Cassaigne, J. Complexité et facteurs spéciaux, Bull. Belg. Math. Soc., Tome 4 (1997), pp. 67-88 | MR 1440670 | Zbl 0921.68065

[5] Cassaigne, J. Limit values of the recurrence quotient of Sturmian sequences, Theoret. Comp. Sci., Tome 218 (1999), pp. 3-12 | Article | MR 1687748 | Zbl 0916.68115

[6] Chekhova, N.; Hubert, P.; Messaoudi, A. Propriétés combinatoires, ergodiques et arithmétiques de la substitution de Tribonacci, J. Théorie Nombres Bordeaux, Tome 13 (2001), pp. 371-394 | Article | Numdam | MR 1879664 | Zbl 1038.37010

[7] Durand, F.; Host, B.; Skau, C. Substitutional dynamical Bratteli diagrams and dimension groups, Ergodic Theory Dynam. Systems, Tome 19 (1999), pp. 953-993 | Article | MR 1709427 | Zbl 1044.46543

[8] Morse, M.; Hedlund, G. A. Symbolic dynamics II. Sturmian trajectories, Amer. J. Math., Tome 62 (1940), pp. 1-42 | Article | MR 745 | Zbl 0022.34003

[9] Mouline, J. Contribution à l’étude de la complexité des suites substitutives, Université de Provence (1989) (Ph. D. Thesis)

[10] Rauzy, G. Nombres algébriques et substitutions, Bull. Soc. Math. France, Tome 110 (1982), pp. 147-178 | Numdam | MR 667748 | Zbl 0522.10032