Fonctions de récurrence des suites d’Arnoux-Rauzy et réponse à une question de Morse et Hedlund
Annales de l'Institut Fourier, Tome 56 (2006) no. 7, pp. 2249-2270.

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.

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.

DOI : https://doi.org/10.5802/aif.2239
Classification : 37B20,  37B10,  68R15
Mots clés: dynamique symbolique, combinatoire des mots, mot infini, fonction de récurrence, suite d’Arnoux-Rauzy, graphe de Rauzy, facteur bispécial, mot singulier, mot de retour
@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},
     zbl = {1138.68045},
     mrnumber = {2290780},
     language = {fr},
     url = {aif.centre-mersenne.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, Tome 56 (2006) no. 7, pp. 2249-2270. doi : 10.5802/aif.2239. https://aif.centre-mersenne.org/item/AIF_2006__56_7_2249_0/

[1] ALESSANDRI, P. Codages de rotations et basses complexités (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 (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