Palindromic complexity of infinite words associated with simple Parry numbers
[Complexité palindromique des mots infinis associés aux nombres de Parry simples]
Annales de l'Institut Fourier, Tome 56 (2006) no. 7, pp. 2131-2160.

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.

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.

DOI : 10.5802/aif.2236
Classification : 68R15, 11A63
Keywords: beta-expansions, palindromic complexity
Mot clés : beta-développements, complexité palindromique
Ambrož, Petr 1 ; Masáková, Zuzana 2 ; Pelantová, Edita 2 ; Frougny, Christiane 3

1 Czech Technical University Doppler Institute for Mathematical Physics and Applied Mathematics Department of Mathematics, FNSPE Trojanova 13, 120 00 Praha 2 (Czech Republic)
2 Doppler Institute for Mathematical Physics and Applied Mathematics and Department of Mathematics, FNSPE, Czech Technical University, Trojanova 13, 120 00 Praha 2 Czech Republic
3 Université Paris 7 LIAFA, UMR 7089 CNRS 2 place Jussieu 75251 Paris Cedex 05 (France) and Université Paris 8
@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},
     pages = {2131--2160},
     publisher = {Association des Annales de l{\textquoteright}institut Fourier},
     volume = {56},
     number = {7},
     year = {2006},
     doi = {10.5802/aif.2236},
     zbl = {1121.68089},
     mrnumber = {2290777},
     language = {en},
     url = {http://www.numdam.org/articles/10.5802/aif.2236/}
}
TY  - JOUR
AU  - Ambrož, Petr
AU  - Masáková, Zuzana
AU  - Pelantová, Edita
AU  - Frougny, Christiane
TI  - Palindromic complexity of infinite words associated with simple Parry numbers
JO  - Annales de l'Institut Fourier
PY  - 2006
SP  - 2131
EP  - 2160
VL  - 56
IS  - 7
PB  - Association des Annales de l’institut Fourier
UR  - http://www.numdam.org/articles/10.5802/aif.2236/
DO  - 10.5802/aif.2236
LA  - en
ID  - AIF_2006__56_7_2131_0
ER  - 
%0 Journal Article
%A Ambrož, Petr
%A Masáková, Zuzana
%A Pelantová, Edita
%A Frougny, Christiane
%T Palindromic complexity of infinite words associated with simple Parry numbers
%J Annales de l'Institut Fourier
%D 2006
%P 2131-2160
%V 56
%N 7
%I Association des Annales de l’institut Fourier
%U http://www.numdam.org/articles/10.5802/aif.2236/
%R 10.5802/aif.2236
%G en
%F 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) no. 7, pp. 2131-2160. doi : 10.5802/aif.2236. http://www.numdam.org/articles/10.5802/aif.2236/

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

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

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

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

[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 | Zbl

[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 (Publications du LaCIM), Volume 36, UQÀM, 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) (Fields Inst. Monogr.), Volume 10, Amer. Math. Soc., Providence, RI, 1998, pp. 15-66 | MR | Zbl

[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., Volume 12 (2002) no. 1-2, pp. 371-385 International Conference on Geometric and Combinatorial Methods in Group Theory and Semigroup Theory (Lincoln, NE, 2000) | DOI | MR | Zbl

[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, Volume 285 (1977), pp. 419-421 | MR | Zbl

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

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

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

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

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

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

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

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

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

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

[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., Volume 174 (1995) no. 1, pp. 149-159 | DOI | MR | Zbl

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

[27] Keane, Michael Interval exchange transformations, Math. Z., Volume 141 (1975), pp. 25-31 | DOI | MR | Zbl

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

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

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

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

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

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

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

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

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

Cité par Sources :