About the paper

coauthors Benoît Loridant
Ali Messaoudi
Jörg M. Thuswaldner
language English
published in Theoretical Computer Science 477 (2013)
pages 6 to 31
DOI 10.1016/j.tcs.2012.12.019
supported by FAPESP, process 2009/07744-0


We study aperiodic and periodic tilings induced by the Rauzy fractal and its subtiles asso- ciated with beta-substitutions related to the polynomial x3 - ax2 - bx -1 for a ≥ b ≥ 1. In particular, we compute the corresponding boundary graphs, describing the adjacencies in the tilings. These graphs are a valuable tool for more advanced studies of the topological properties of the Rauzy fractals. As an example, we show that the Rauzy fractals are not homeomorphic to a closed disc as soon as a ≤ 2b - 4. The methods presented in this paper may be used to obtain similar results for other classes of substitutions.


  1. S. Akiyama, On the boundary of self affine tilings generated by Pisot numbers, J. Math. Soc. Japan 54 (2002) 283—308.
  2. S. Akiyama, H. Rao, W. Steiner, A certain finiteness property of Pisot number systems, J. Number Theory 107 (2004) 135—160.
  3. P. Arnoux, S. Ito, Pisot substitutions and Rauzy fractals, Bull. Belg. Math. Soc. Simon Stevin 8 (2001) 181—207. Journées Montoises d’Informatique Théorique (Marne-la-Vallée, 2000).
  4. C. Bandt, G. Gelbrich, Classification of self-affine lattice tilings, J. Lond. Math. Soc. (2) 50 (1994) 581—593.
  5. M. Barge, B. Diamond, Coincidence for substitutions of Pisot type, Bull. Soc. Math. France 130 (2002) 619—626.
  6. M. Barge, J. Kwapisz, Geometric theory of unimodular substitutions, Amer. J. Math. 128 (5) (2006) 1219—1282.
  7. V. Berthé, M. Rigo, Combinatorics, automata, and number theory, in: Encyclopedia of Mathematics and its Applications, vol. 135, Cambridge University Press, Cambridge, 2010.
  8. V. Berthé, A. Siegel, Tilings associated with beta-numeration and substitutions, Integers 5 (2005) (electronic).
  9. V. Berthé, A. Siegel, W. Steiner, P. Surer, J.M. Thuswaldner, Fractal tiles associated with shift radix systems, Adv. Math. 226 (2011) 139—175.
  10. V. Canterini, Connectedness of geometric representation of substitutions of Pisot type, Bull. Belg. Math. Soc. Simon Stevin 10 (2003) 77—89.
  11. V. Canterini, A. Siegel, Automate des préfixes-suffixes associé à une substitution primitive, J. Théor. Nombres Bordeaux 13 (2001) 353—369.
  12. V. Canterini, A. Siegel, Geometric representation of substitutions of Pisot type, Trans. Amer. Math. Soc. 353 (2001) 5121—5144 (electronic).
  13. H. Ei, S. Ito, Tilings from some non-irreducible, Pisot substitutions, Discrete Math. Theor. Comput. Sci. 7 (2005) 81—121 (electronic).
  14. H. Ei, S. Ito, H. Rao, Atomic surfaces, tilings and coincidences. II. Reducible case, Ann. Inst. Fourier (Grenoble) 56 (2006) 2285—2313. Numération, pavages, substitutions.
  15. B. Grünbaum, G.C. Shephard, Tilings and Patterns, W. H. Freeman and Company, New York, 1987.
  16. P. Hubert, A. Messaoudi, Best simultaneous Diophantine approximations of Pisot numbers and Rauzy fractals, Acta Arith. 124 (2006) 1—15.
  17. S. Ito, M. Kimura, On the Rauzy fractal, Japan J. Ind. Appl. Math. 8 (1991) 461—486.
  18. S. Ito, H. Rao, Atomic surfaces, tilings and coincidence. I. Irreducible case, Israel J. Math. 153 (2006) 129—155.
  19. A. Messaoudi, Propriétés arithmétiques et dynamiques du fractal de Rauzy, J. Théor. Nombres Bordeaux 10 (1998) 135—162.
  20. A. Messaoudi, Frontière du fractal de Rauzy et système de numération complexe, Acta Arith. 95 (2000) 195—224.
  21. A. Messaoudi, Arithmetic and topological properties of a class of fractal sets (Propriétés arithmétiques et topologiques d’une classe d’ensembles fractales.), Acta Arith. 121 (2006) 341—366.
  22. G. Rauzy, Nombres algébriques et substitutions, Bull. Soc. Math. France 110 (1982) 147—178.
  23. A. Siegel, J.M. Thuswaldner, Topological properties of Rauzy fractals, Mém. Soc. Math. Fr. (N.S.) (2009).
  24. V.F. Sirvent, Y. Wang, Self-affine tiling via substitution dynamical systems and Rauzy fractals, Pacific J. Math. 206 (2002) 465—485.
  25. B. Solomyak, Substitutions, adic transformations, and beta-expansions, in: Symbolic Dynamics and Its Applications, (New Haven, CT, 1991), in: Contemp. Math., vol. 135, Amer. Math. Soc, Providence, RI, 1992, pp. 361—372.
  26. J.M. Thuswaldner, Unimodular Pisot substitutions and their associated tiles, J. Théor. Nombres Bordeaux 18 (2006) 487—536.


Theoretical Computer Science
Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)