Palindromic complexity of infinite words associated with simple Parry numbers
Annales de l'Institut Fourier, Volume 56 (2006) no. 7, p. 2131-2160
A simple Parry number is a real number β>1 such that the Rényi expansion of 1 is finite, of the form d β (1)=t 1 t m . We study the palindromic structure of infinite aperiodic words u β that are the fixed point of a substitution associated with a simple Parry number β. It is shown that the word u β contains infinitely many palindromes if and only if t 1 =t 2 ==t m-1 t m . Numbers β satisfying this condition are the so-called confluent Pisot numbers. If t m =1 then u β is an Arnoux-Rauzy word. We show that if β is a confluent Pisot number then 𝒫(n+1)+𝒫(n)=𝒞(n+1)-𝒞(n)+2, where 𝒫(n) is the number of palindromes and 𝒞(n) is the number of factors of length n in u β . We then give a complete description of the set of palindromes, its structure and properties.
Un nombre de Parry simple est un nombre réel β>1 tel que le développement de Rényi de 1 est fini, de la forme d β (1)=t 1 t m . Nous étudions la structure palindromique des mots infinis apériodiques u β qui sont point fixe d’une substitution associée à un nombre de Parry simple β. Nous montrons que le mot u β contient un nombre infini de palindromes si et seulement si t 1 =t 2 ==t m-1 t m . Les nombres β satisfaisant cette condition sont connus sous le nom de nombres de Pisot confluents. Si de plus t m =1 alors u β est un mot d’Arnoux-Rauzy. Nous montrons que si β est un nombre de Pisot confluent alors 𝒫(n+1)+𝒫(n)=𝒞(n+1)-𝒞(n)+2, où 𝒫(n) est le nombre de facteurs de longueur n de u β . Nous donnons aussi une description complète de l’ensemble des palindromes, de sa structure et de ses propriétés.
DOI : https://doi.org/10.5802/aif.2236
Classification:  68R15,  11A63
Keywords: beta-expansions, palindromic complexity
@article{AIF_2006__56_7_2131_0,
     author = {Ambro\v z, Petr and Mas\'akov\'a, Zuzana and Pelantov\'a, Edita and Frougny, Christiane},
     title = {Palindromic complexity of infinite words associated with simple Parry numbers},
     journal = {Annales de l'Institut Fourier},
     publisher = {Association des Annales de l'institut Fourier},
     volume = {56},
     number = {7},
     year = {2006},
     pages = {2131-2160},
     doi = {10.5802/aif.2236},
     zbl = {1121.68089},
     mrnumber = {2290777},
     language = {en},
     url = {https://aif.centre-mersenne.org/item/AIF_2006__56_7_2131_0}
}
Palindromic complexity of infinite words associated with simple Parry numbers. Annales de l'Institut Fourier, Volume 56 (2006) no. 7, pp. 2131-2160. doi : 10.5802/aif.2236. https://aif.centre-mersenne.org/item/AIF_2006__56_7_2131_0/

[1] Allauzen, Cyril Une caractérisation simple des nombres de Sturm, J. Théor. Nombres Bordeaux, Tome 10 (1998) no. 2, pp. 237-241 | Article | Numdam | MR 1828243 | Zbl 0930.11051

[2] Allouche, Jean-Paul; Baake, Michael; Cassaigne, Julien; Damanik, David Palindrome complexity, Theoret. Comput. Sci., Tome 292 (2003) no. 1, pp. 9-31 (Selected papers in honor of Jean Berstel) | Article | MR 1964623 | Zbl 1064.68074

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

[4] Baláži, Peter; Masáková, Zuzana; Pelantová, Edita Complete characterization of substitution invariant Sturmian sequences, Integers, Tome 5 (2005) no. 1, pp. A14, 23 pp. (electronic) | MR 2192233 | Zbl 02214413

[5] Baláži, Peter; Masáková, Zuzana; Pelantová, Edita Factor versus palindromic complexity of uniformly recurrent infinite words (2006) (To appear in Theor. Comp. Sci.) | MR 2192233 | Zbl 1119.68137

[6] Baláži, Peter; Pelantová, Edita; Brlek, S.; Reutenauer, C. Palindromic complexity of infinite words coding interval exchange transformations, Words 2005, 5 t h International Conference on Words, actes, UQÀM (Publications du LaCIM) Tome 36 (2005), pp. 113-118

[7] Balková, Ľubomíra Factor and palindromic complexity for infninite words associated with quadratic non-simple Parry numbers (2006) (Preprint Doppler Institute, Prague)

[8] Barache, Damien; Champagne, Bernard; Gazeau, Jean-Pierre Pisot-cyclotomic quasilattices and their symmetry semigroups, Quasicrystals and discrete geometry (Toronto, ON, 1995), Amer. Math. Soc., Providence, RI (Fields Inst. Monogr.) Tome 10 (1998), pp. 15-66 | MR 1636775 | Zbl 0916.20025

[9] Bernat, Julien Propriétés arithmétiques de la β -numération, Univesité de la Méditeranée (2005) (Ph. D. Thesis)

[10] Berstel, Jean Recent results on extensions of Sturmian words, Internat. J. Algebra Comput., Tome 12 (2002) no. 1-2, pp. 371-385 (International Conference on Geometric and Combinatorial Methods in Group Theory and Semigroup Theory (Lincoln, NE, 2000)) | Article | MR 1902372 | Zbl 1007.68141

[11] Berstel, Jean; Boasson, Luc; Carton, Olivier; Fagnot, Isabelle Infinite words without palindrome (2006) (Preprint)

[12] Berthé, Valérie; Ei, Hiromi; Ito, Shunji; Rao, Hui Invertible susbtitutions and Sturmian words: an application of Rauzy fractals (2006) (To appear in Theoret. Informatics Appl.)

[13] Bertrand, Anne Développements en base de Pisot et répartition modulo 1, C. R. Acad. Sci. Paris, Tome 285 (1977), pp. 419-421 | MR 447134 | Zbl 0362.10040

[14] Bertrand-Mathis, Anne Comment écrire les nombres entiers dans une base qui n’est pas entière, Acta Math. Hungar., Tome 54 (1989) no. 3-4, pp. 237-241 | Article | MR 1029085 | Zbl 0695.10005

[15] Brlek, S.; Hamel, S.; Nivat, M.; Reutenauer, C. On the palindromic complexity of infinite words, Internat. J. Found. Comput. Sci., Tome 15 (2004) no. 2, pp. 293-306 | Article | MR 2071459 | Zbl 1067.68113

[16] Burdík, Čestmír; Frougny, Christiane; Gazeau, Jean-Pierre; Krejcar, Rudolf Beta-integers as natural counting systems for quasicrystals, J. Phys. A, Tome 31 (1998) no. 30, pp. 6449-6472 | Article | MR 1644115 | Zbl 0941.52019

[17] Cassaigne, Julien Complexité et facteurs spéciaux, Bull. Belg. Math. Soc. Simon Stevin, Tome 4 (1997) no. 1, pp. 67-88 (Journées Montoises (Mons, 1994)) | MR 1440670 | Zbl 0921.68065

[18] Damanik, D.; Zamboni, Luca Q. Combinatorial properties of Arnoux-Rauzy subshifts and applications to Schrödinger operators, Rev. Math. Phys., Tome 15 (2003) no. 7, pp. 745-763 | Article | MR 2018286 | Zbl 1081.81521

[19] Droubay, Xavier; Justin, Jacques; Pirillo, Giuseppe Epi-Sturmian words and some constructions of de Luca and Rauzy, Theoret. Comput. Sci., Tome 255 (2001) no. 1-2, pp. 539-553 | Article | MR 1819089 | Zbl 0981.68126

[20] Droubay, Xavier; Pirillo, Giuseppe Palindromes and Sturmian words, Theoret. Comput. Sci., Tome 223 (1999) no. 1-2, pp. 73-85 | Article | MR 1704637 | Zbl 0930.68116

[21] Fabre, Stéphane Substitutions et β-systèmes de numération, Theoret. Comput. Sci., Tome 137 (1995) no. 2, pp. 219-236 | Article | MR 1311222 | Zbl 0872.11017

[22] Frougny, Christiane Confluent linear numeration systems, Theoret. Comput. Sci., Tome 106 (1992) no. 2, pp. 183-219 | Article | MR 1192767 | Zbl 0787.68057

[23] Frougny, Christiane; Masáková, Zuzana; Pelantová, Edita Complexity of infinite words associated with beta-expansions, Theor. Inform. Appl., Tome 38 (2004) no. 2, pp. 163-185 (Corrigendum. Theor. Inform. Appl. 38 (2004), 269–271.) | Article | Numdam | Numdam | MR 2060775 | Zbl 1104.11013

[24] Frougny, Christiane; Masáková, Zuzana; Pelantová, Edita Infinite left special branches in words associated with beta expansions (2005) (To appear in J. Autom. Lang. Comb.)

[25] Hof, A.; Knill, O.; Simon, B. Singular continuous spectrum for palindromic Schrödinger operators, Comm. Math. Phys., Tome 174 (1995) no. 1, pp. 149-159 | Article | MR 1372804 | Zbl 0839.11009

[26] Justin, Jacques; Pirillo, Giuseppe Episturmian words and episturmian morphisms, Theoret. Comput. Sci., Tome 276 (2002) no. 1-2, pp. 281-313 | Article | MR 1896357 | Zbl 1002.68116

[27] Keane, Michael Interval exchange transformations, Math. Z., Tome 141 (1975), pp. 25-31 | Article | MR 357739 | Zbl 0278.28010

[28] Lothaire, M. Algebraic Combinatorics on Words, Cambridge University Press, Cambridge, Encyclopedia of Mathematics and its Applications, Tome 90 (2002) | MR 1905123 | Zbl 1001.68093

[29] Parry, W. On the β-expansions of real numbers, Acta Math. Acad. Sci. Hungar., Tome 11 (1960), pp. 401-416 | Article | MR 142719 | Zbl 0099.28103

[30] Parvaix, Bruno Substitution invariant Sturmian bisequences, J. Théor. Nombres Bordeaux, Tome 11 (1999) no. 1, pp. 201-210 (Les XXèmes Journées Arithmétiques (Limoges, 1997)) | Article | Numdam | MR 1730440 | Zbl 0978.11005

[31] Pytheas Fogg, N. Substitutions in Dynamics, Arithmetics and Combinatorics, Springer Verlag, Lecture Notes in Mathematics, Tome 1794 (2002) (402 pages) | MR 1970385 | Zbl 1014.11015

[32] Queffélec, Martine Substitution dynamical systems—spectral analysis, Springer-Verlag, Berlin, Lecture Notes in Mathematics, Tome 1294 (1987) | MR 924156 | Zbl 0642.28013

[33] Rauzy, Gérard Échanges d’intervalles et transformations induites, Acta Arith., Tome 34 (1979) no. 4, pp. 315-328 | MR 543205 | Zbl 0414.28018

[34] Rényi, Alfred Representations for real numbers and their ergodic properties, Acta Math. Acad. Sci. Hungar, Tome 8 (1957), pp. 477-493 | Article | MR 97374 | Zbl 0079.08901

[35] Solomyak, Boris Conjugates of beta-numbers and the zero-free domain for a class of analytic functions, Proc. London Math. Soc. (3), Tome 68 (1994) no. 3, pp. 477-498 | Article | MR 1262305 | Zbl 0820.30007

[36] Yasutomi, Shin-Ichi On Sturmian sequences which are invariant under some substitutions, Number theory and its applications (Kyoto, 1997), Kluwer Acad. Publ., Dordrecht (Dev. Math.) Tome 2 (1999), pp. 347-373 | MR 1738827 | Zbl 0971.11007