logo ANNALES DE L'INSTITUT FOURIER

With cedram.org
Table of contents for this issue | Previous article | Next article
Petr Ambrož; Zuzana Masáková; Edita Pelantová; Christiane Frougny
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, 56 no. 7 (2006), p. 2131-2160, doi: 10.5802/aif.2236
Article PDF | Reviews MR 2290777 | Zbl 1121.68089
Class. Math.: 68R15, 11A63
Keywords: beta-expansions, palindromic complexity

Résumé - Abstract

A simple Parry number is a real number $\beta >1$ such that the Rényi expansion of $1$ is finite, of the form $d_\beta (1)=t_1 \cdots t_m$. We study the palindromic structure of infinite aperiodic words $u_\beta $ that are the fixed point of a substitution associated with a simple Parry number $\beta $. It is shown that the word $u_\beta $ contains infinitely many palindromes if and only if $t_1=t_2= \cdots =t_{m-1}\ge t_m$. Numbers $\beta $ satisfying this condition are the so-called confluent Pisot numbers. If $t_m=1$ then $u_\beta $ is an Arnoux-Rauzy word. We show that if $\beta $ is a confluent Pisot number then ${\mathcal{P}}(n+1)+ {\mathcal{P}}(n) = {\mathcal{C}}(n+1) - {\mathcal{C}}(n)+2$, where ${\mathcal{P}}(n)$ is the number of palindromes and ${\mathcal{C}}(n)$ is the number of factors of length $n$ in $u_\beta $. We then give a complete description of the set of palindromes, its structure and properties.

Bibliography

[1] Cyril Allauzen, “Une caractérisation simple des nombres de Sturm”, J. Théor. Nombres Bordeaux 10 (1998) no. 2, p. 237-241 Cedram |  MR 1828243 |  Zbl 0930.11051
[2] Jean-Paul Allouche, Michael Baake, Julien Cassaigne & David Damanik, “Palindrome complexity”, Theoret. Comput. Sci. 292 (2003) no. 1, p. 9-31, Selected papers in honor of Jean Berstel Article |  MR 1964623 |  Zbl 1064.68074
[3] Pierre Arnoux & Gérard Rauzy, “Représentation géométrique de suites de complexité $2n+1$”, Bull. Soc. Math. France 119 (1991) no. 2, p. 199-215 Numdam |  MR 1116845 |  Zbl 0789.28011
[4] Peter Baláži, Zuzana Masáková & Edita Pelantová, “Complete characterization of substitution invariant Sturmian sequences”, Integers 5 (2005) no. 1  MR 2192233 |  Zbl 02214413
[5] Peter Baláži, Zuzana Masáková & Edita Pelantová, “Factor versus palindromic complexity of uniformly recurrent infinite words”, To appear in Theor. Comp. Sci., 2006 arXiv |  MR 2192233 |  Zbl 1119.68137
[6] Peter Baláži & Edita Pelantová, Palindromic complexity of infinite words coding interval exchange transformations, in S. Brlek, C. Reutenauer, ed., Words 2005, 5$^{th}$ International Conference on Words, actes, Publications du LaCIM 36, UQÀM, 2005, p. 113–118
[7] Ľubomíra Balková, “Factor and palindromic complexity for infninite words associated with quadratic non-simple Parry numbers”, Preprint Doppler Institute, Prague, 2006
[8] Damien Barache, Bernard Champagne & Jean-Pierre Gazeau, Pisot-cyclotomic quasilattices and their symmetry semigroups, Quasicrystals and discrete geometry (Toronto, ON, 1995), Fields Inst. Monogr. 10, Amer. Math. Soc., 1998, p. 15–66  MR 1636775 |  Zbl 0916.20025
[9] Julien Bernat, Propriétés arithmétiques de la $\beta $-numération, Ph. D. Thesis, Univesité de la Méditeranée, 2005
[10] Jean Berstel, “Recent results on extensions of Sturmian words”, Internat. J. Algebra Comput. 12 (2002) no. 1-2, p. 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] Jean Berstel, Luc Boasson, Olivier Carton & Isabelle Fagnot, “Infinite words without palindrome”, Preprint, 2006
[12] Valérie Berthé, Hiromi Ei, Shunji Ito & Hui Rao, “Invertible susbtitutions and Sturmian words: an application of Rauzy fractals”, To appear in Theoret. Informatics Appl., 2006
[13] Anne Bertrand, “Développements en base de Pisot et répartition modulo $1$”, C. R. Acad. Sci. Paris 285 (1977), p. 419-421  MR 447134 |  Zbl 0362.10040
[14] Anne Bertrand-Mathis, “Comment écrire les nombres entiers dans une base qui n’est pas entière”, Acta Math. Hungar. 54 (1989) no. 3-4, p. 237-241 Article |  MR 1029085 |  Zbl 0695.10005
[15] S. Brlek, S. Hamel, M. Nivat & C. Reutenauer, “On the palindromic complexity of infinite words”, Internat. J. Found. Comput. Sci. 15 (2004) no. 2, p. 293-306 Article |  MR 2071459 |  Zbl 1067.68113
[16] Čestmír Burdík, Christiane Frougny, Jean-Pierre Gazeau & Rudolf Krejcar, “Beta-integers as natural counting systems for quasicrystals”, J. Phys. A 31 (1998) no. 30, p. 6449-6472 Article |  MR 1644115 |  Zbl 0941.52019
[17] Julien Cassaigne, “Complexité et facteurs spéciaux”, Bull. Belg. Math. Soc. Simon Stevin 4 (1997) no. 1, p. 67-88, Journées Montoises (Mons, 1994) Article |  MR 1440670 |  Zbl 0921.68065
[18] D. Damanik & Luca Q. Zamboni, “Combinatorial properties of Arnoux-Rauzy subshifts and applications to Schrödinger operators”, Rev. Math. Phys. 15 (2003) no. 7, p. 745-763 Article |  MR 2018286 |  Zbl 1081.81521
[19] Xavier Droubay, Jacques Justin & Giuseppe Pirillo, “Epi-Sturmian words and some constructions of de Luca and Rauzy”, Theoret. Comput. Sci. 255 (2001) no. 1-2, p. 539-553 Article |  MR 1819089 |  Zbl 0981.68126
[20] Xavier Droubay & Giuseppe Pirillo, “Palindromes and Sturmian words”, Theoret. Comput. Sci. 223 (1999) no. 1-2, p. 73-85 Article |  MR 1704637 |  Zbl 0930.68116
[21] Stéphane Fabre, “Substitutions et $\beta $-systèmes de numération”, Theoret. Comput. Sci. 137 (1995) no. 2, p. 219-236 Article |  MR 1311222 |  Zbl 0872.11017
[22] Christiane Frougny, “Confluent linear numeration systems”, Theoret. Comput. Sci. 106 (1992) no. 2, p. 183-219 Article |  MR 1192767 |  Zbl 0787.68057
[23] Christiane Frougny, Zuzana Masáková & Edita Pelantová, “Complexity of infinite words associated with beta-expansions”, Theor. Inform. Appl. 38 (2004) no. 2, p. 163-185, Corrigendum. Theor. Inform. Appl. 38 (2004), 269–271. Article |  MR 2060775 |  Zbl 1104.11013
[24] Christiane Frougny, Zuzana Masáková & Edita Pelantová, “Infinite left special branches in words associated with beta expansions”, To appear in J. Autom. Lang. Comb., 2005
[25] A. Hof, O. Knill & B. Simon, “Singular continuous spectrum for palindromic Schrödinger operators”, Comm. Math. Phys. 174 (1995) no. 1, p. 149-159 Article |  MR 1372804 |  Zbl 0839.11009
[26] Jacques Justin & Giuseppe Pirillo, “Episturmian words and episturmian morphisms”, Theoret. Comput. Sci. 276 (2002) no. 1-2, p. 281-313 Article |  MR 1896357 |  Zbl 1002.68116
[27] Michael Keane, “Interval exchange transformations”, Math. Z. 141 (1975), p. 25-31 Article |  MR 357739 |  Zbl 0278.28010
[28] M. Lothaire, Algebraic Combinatorics on Words, Encyclopedia of Mathematics and its Applications 90, Cambridge University Press, Cambridge, 2002  MR 1905123 |  Zbl 1001.68093
[29] W. Parry, “On the $\beta $-expansions of real numbers”, Acta Math. Acad. Sci. Hungar. 11 (1960), p. 401-416 Article |  MR 142719 |  Zbl 0099.28103
[30] Bruno Parvaix, “Substitution invariant Sturmian bisequences”, J. Théor. Nombres Bordeaux 11 (1999) no. 1, p. 201-210, Les XXèmes Journées Arithmétiques (Limoges, 1997) Cedram |  MR 1730440 |  Zbl 0978.11005
[31] N. Pytheas Fogg, Substitutions in Dynamics, Arithmetics and Combinatorics, Lecture Notes in Mathematics 1794, Springer Verlag, 2002, 402 pages  MR 1970385 |  Zbl 1014.11015
[32] Martine Queffélec, Substitution dynamical systems—spectral analysis, Lecture Notes in Mathematics 1294, Springer-Verlag, Berlin, 1987  MR 924156 |  Zbl 0642.28013
[33] Gérard Rauzy, “Échanges d’intervalles et transformations induites”, Acta Arith. 34 (1979) no. 4, p. 315-328 Article |  MR 543205 |  Zbl 0414.28018
[34] Alfred Rényi, “Representations for real numbers and their ergodic properties”, Acta Math. Acad. Sci. Hungar 8 (1957), p. 477-493 Article |  MR 97374 |  Zbl 0079.08901
[35] Boris Solomyak, “Conjugates of beta-numbers and the zero-free domain for a class of analytic functions”, Proc. London Math. Soc. (3) 68 (1994) no. 3, p. 477-498 Article |  MR 1262305 |  Zbl 0820.30007
[36] Shin-Ichi Yasutomi, On Sturmian sequences which are invariant under some substitutions, Number theory and its applications (Kyoto, 1997), Dev. Math. 2, Kluwer Acad. Publ., 1999, p. 347–373  MR 1738827 |  Zbl 0971.11007
top