Palindromic complexity of infinite words associated with simple Parry numbers

Petr Ambrož[1]; Zuzana Masáková[2]; Edita Pelantová[2]; Christiane Frougny[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

Annales de l’institut Fourier (2006)

  • Volume: 56, Issue: 7, page 2131-2160
  • ISSN: 0373-0956

Abstract

top
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.

How to cite

top

Ambrož, Petr, et al. "Palindromic complexity of infinite words associated with simple Parry numbers." Annales de l’institut Fourier 56.7 (2006): 2131-2160. <http://eudml.org/doc/10200>.

@article{Ambrož2006,
abstract = {A simple Parry number is a real number $\beta &gt;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.},
affiliation = {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; 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},
author = {Ambrož, Petr, Masáková, Zuzana, Pelantová, Edita, Frougny, Christiane},
journal = {Annales de l’institut Fourier},
keywords = {beta-expansions; palindromic complexity},
language = {eng},
number = {7},
pages = {2131-2160},
publisher = {Association des Annales de l’institut Fourier},
title = {Palindromic complexity of infinite words associated with simple Parry numbers},
url = {http://eudml.org/doc/10200},
volume = {56},
year = {2006},
}

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
PB - Association des Annales de l’institut Fourier
VL - 56
IS - 7
SP - 2131
EP - 2160
AB - A simple Parry number is a real number $\beta &gt;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.
LA - eng
KW - beta-expansions; palindromic complexity
UR - http://eudml.org/doc/10200
ER -

References

top
  1. Cyril Allauzen, Une caractérisation simple des nombres de Sturm, J. Théor. Nombres Bordeaux 10 (1998), 237-241 Zbl0930.11051MR1828243
  2. Jean-Paul Allouche, Michael Baake, Julien Cassaigne, David Damanik, Palindrome complexity, Theoret. Comput. Sci. 292 (2003), 9-31 Zbl1064.68074MR1964623
  3. Pierre Arnoux, Gérard Rauzy, Représentation géométrique de suites de complexité 2 n + 1 , Bull. Soc. Math. France 119 (1991), 199-215 Zbl0789.28011MR1116845
  4. Peter Baláži, Zuzana Masáková, Edita Pelantová, Complete characterization of substitution invariant Sturmian sequences, Integers 5 (2005) Zbl1121.11020MR2192233
  5. Peter Baláži, Zuzana Masáková, Edita Pelantová, Factor versus palindromic complexity of uniformly recurrent infinite words, (2006) Zbl1119.68137MR2192233
  6. Peter Baláži, Edita Pelantová, Palindromic complexity of infinite words coding interval exchange transformations, Words 2005, 5 International Conference on Words, actes 36 (2005), 113-118, BrlekS.S. 
  7. Ľubomíra Balková, Factor and palindromic complexity for infninite words associated with quadratic non-simple Parry numbers, (2006) 
  8. Damien Barache, Bernard Champagne, Jean-Pierre Gazeau, Pisot-cyclotomic quasilattices and their symmetry semigroups, Quasicrystals and discrete geometry (Toronto, ON, 1995) 10 (1998), 15-66, Amer. Math. Soc., Providence, RI Zbl0916.20025MR1636775
  9. Julien Bernat, Propriétés arithmétiques de la β -numération, (2005) 
  10. Jean Berstel, Recent results on extensions of Sturmian words, Internat. J. Algebra Comput. 12 (2002), 371-385 Zbl1007.68141MR1902372
  11. Jean Berstel, Luc Boasson, Olivier Carton, Isabelle Fagnot, Infinite words without palindrome, (2006) 
  12. Valérie Berthé, Hiromi Ei, Shunji Ito, Hui Rao, Invertible susbtitutions and Sturmian words: an application of Rauzy fractals, (2006) Zbl1140.11014
  13. Anne Bertrand, Développements en base de Pisot et répartition modulo 1 , C. R. Acad. Sci. Paris 285 (1977), 419-421 Zbl0362.10040MR447134
  14. Anne Bertrand-Mathis, Comment écrire les nombres entiers dans une base qui n’est pas entière, Acta Math. Hungar. 54 (1989), 237-241 Zbl0695.10005MR1029085
  15. S. Brlek, S. Hamel, M. Nivat, C. Reutenauer, On the palindromic complexity of infinite words, Internat. J. Found. Comput. Sci. 15 (2004), 293-306 Zbl1067.68113MR2071459
  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), 6449-6472 Zbl0941.52019MR1644115
  17. Julien Cassaigne, Complexité et facteurs spéciaux, Bull. Belg. Math. Soc. Simon Stevin 4 (1997), 67-88 Zbl0921.68065MR1440670
  18. D. Damanik, Luca Q. Zamboni, Combinatorial properties of Arnoux-Rauzy subshifts and applications to Schrödinger operators, Rev. Math. Phys. 15 (2003), 745-763 Zbl1081.81521MR2018286
  19. Xavier Droubay, Jacques Justin, Giuseppe Pirillo, Epi-Sturmian words and some constructions of de Luca and Rauzy, Theoret. Comput. Sci. 255 (2001), 539-553 Zbl0981.68126MR1819089
  20. Xavier Droubay, Giuseppe Pirillo, Palindromes and Sturmian words, Theoret. Comput. Sci. 223 (1999), 73-85 Zbl0930.68116MR1704637
  21. Stéphane Fabre, Substitutions et β -systèmes de numération, Theoret. Comput. Sci. 137 (1995), 219-236 Zbl0872.11017MR1311222
  22. Christiane Frougny, Confluent linear numeration systems, Theoret. Comput. Sci. 106 (1992), 183-219 Zbl0787.68057MR1192767
  23. Christiane Frougny, Zuzana Masáková, Edita Pelantová, Complexity of infinite words associated with beta-expansions, Theor. Inform. Appl. 38 (2004), 163-185 Zbl1104.11013MR2060775
  24. Christiane Frougny, Zuzana Masáková, Edita Pelantová, Infinite left special branches in words associated with beta expansions, (2005) Zbl1165.11012
  25. A. Hof, O. Knill, B. Simon, Singular continuous spectrum for palindromic Schrödinger operators, Comm. Math. Phys. 174 (1995), 149-159 Zbl0839.11009MR1372804
  26. Jacques Justin, Giuseppe Pirillo, Episturmian words and episturmian morphisms, Theoret. Comput. Sci. 276 (2002), 281-313 Zbl1002.68116MR1896357
  27. Michael Keane, Interval exchange transformations, Math. Z. 141 (1975), 25-31 Zbl0278.28010MR357739
  28. M. Lothaire, Algebraic Combinatorics on Words, 90 (2002), Cambridge University Press, Cambridge Zbl1001.68093MR1905123
  29. W. Parry, On the β -expansions of real numbers, Acta Math. Acad. Sci. Hungar. 11 (1960), 401-416 Zbl0099.28103MR142719
  30. Bruno Parvaix, Substitution invariant Sturmian bisequences, J. Théor. Nombres Bordeaux 11 (1999), 201-210 Zbl0978.11005MR1730440
  31. N. Pytheas Fogg, Substitutions in Dynamics, Arithmetics and Combinatorics, 1794 (2002), Springer Verlag Zbl1014.11015MR1970385
  32. Martine Queffélec, Substitution dynamical systems—spectral analysis, 1294 (1987), Springer-Verlag, Berlin Zbl0642.28013MR924156
  33. Gérard Rauzy, Échanges d’intervalles et transformations induites, Acta Arith. 34 (1979), 315-328 Zbl0414.28018MR543205
  34. Alfred Rényi, Representations for real numbers and their ergodic properties, Acta Math. Acad. Sci. Hungar 8 (1957), 477-493 Zbl0079.08901MR97374
  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), 477-498 Zbl0820.30007MR1262305
  36. Shin-Ichi Yasutomi, On Sturmian sequences which are invariant under some substitutions, Number theory and its applications (Kyoto, 1997) 2 (1999), 347-373, Kluwer Acad. Publ., Dordrecht Zbl0971.11007MR1738827

Citations in EuDML Documents

top
  1. L'ubomíra Balková, Zuzana Masáková, Palindromic complexity of infinite words associated with non-simple Parry numbers
  2. L'ubomíra Balková, Zuzana Masáková, Palindromic complexity of infinite words associated with non-simple Parry numbers
  3. Lubomíra Balková, Edita Pelantová, Ondřej Turek, Combinatorial and arithmetical properties of infinite words associated with non-simple quadratic Parry numbers
  4. Julien Bernat, Study of irreducible balanced pairs for substitutive languages
  5. L'ubomíra Balková, Edita Pelantová, Štěpán Starosta, Sturmian jungle (or garden?) on multiliteral alphabets
  6. L'ubomíra Balková, Edita Pelantová, Štěpán Starosta, Sturmian jungle (or garden?) on multiliteral alphabets
  7. Amy Glen, Jacques Justin, Episturmian words: a survey

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.