Palindromic complexity of infinite words associated with simple Parry numbers

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

doi:10.5802/aif.2236

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 ³

¹ Czech Technical University Doppler Institute for Mathematical Physics and Applied Mathematics Department of Mathematics, FNSPE Trojanova 13, 120 00 Praha 2 (Czech Republic)
² Doppler Institute for Mathematical Physics and Applied Mathematics and Department of Mathematics, FNSPE, Czech Technical University, Trojanova 13, 120 00 Praha 2 Czech Republic
³ Université Paris 7 LIAFA, UMR 7089 CNRS 2 place Jussieu 75251 Paris Cedex 05 (France) and Université Paris 8

Annales de l'Institut Fourier, Tome 56 (2006) no. 7, pp. 2131-2160.

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.

MR Zbl | 5 citations dans Numdam

DOI : 10.5802/aif.2236

Classification : 68R15, 11A63
Keywords: beta-expansions, palindromic complexity
Mot clés : beta-développements, complexité palindromique

Affiliations des auteurs :

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

@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/

Bibliographie
Cité par

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