Palindromic complexity of infinite words associated with simple Parry numbers

Ambrož, Petr; Masáková, Zuzana; Pelantová, Edita; Frougny, Christiane

Palindromic complexity of infinite words associated with simple Parry numbers
[Complexité palindromique des mots infinis associés aux nombres de Parry simples]

Ambrož, Petr ; Masáková, Zuzana ; Pelantová, Edita ; Frougny, Christiane

Annales de l'Institut Fourier, Tome 56 (2006), p. 2131-2160 / Harvested from Numdam

Access to full text
Full (PDF)
Full (DJVU)

Résumé
Abstract

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} \dots 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} = \dots = t_{m - 1} \geq 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.

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} \dots 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} = \dots = t_{m - 1} \geq 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.

Publié le : 2006-01-01

MR 2290777 | Zbl 1121.68089 | 5 citations dans Numdam

DOI : https://doi.org/10.5802/aif.2236
Classification: 68R15, 11A63
Mots clés: beta-développements, complexité palindromique

@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},
     volume = {56},
     year = {2006},
     pages = {2131-2160},
     doi = {10.5802/aif.2236},
     zbl = {1121.68089},
     mrnumber = {2290777},
     language = {en},
     url = {http://dml.mathdoc.fr/item/AIF_2006__56_7_2131_0}
}

Ambrož, Petr; Masáková, Zuzana; Pelantová, Edita; Frougny, Christiane. Palindromic complexity of infinite words associated with simple Parry numbers. Annales de l'Institut Fourier, Tome 56 (2006) pp. 2131-2160. doi : 10.5802/aif.2236. http://gdmltest.u-ga.fr/item/AIF_2006__56_7_2131_0/

Bibliographie

[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é $2 n + 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