Substitutions, abstract number systems and the space filling property

Clemens Fuchs[1]; Robert Tijdeman[2]

  • [1] ETH Zürich Departement Mathematik Rämistrasse 101 8092 Zürich (Switzerland)
  • [2] Universiteit Leiden Mathematisch Instituut Niels Bohrweg 1 2300 RA Leiden (The Netherlands)

Annales de l’institut Fourier (2006)

  • Volume: 56, Issue: 7, page 2345-2389
  • ISSN: 0373-0956

Abstract

top
In this paper we study multi-dimensional words generated by fixed points of substitutions by projecting the integer points on the corresponding broken halfline. We show for a large class of substitutions that the resulting word is the restriction of a linear function modulo 1 and that it can be decided whether the resulting word is space filling or not. The proof uses lattices and the abstract number system associated with the substitution.

How to cite

top

Fuchs, Clemens, and Tijdeman, Robert. "Substitutions, abstract number systems and the space filling property." Annales de l’institut Fourier 56.7 (2006): 2345-2389. <http://eudml.org/doc/10207>.

@article{Fuchs2006,
abstract = {In this paper we study multi-dimensional words generated by fixed points of substitutions by projecting the integer points on the corresponding broken halfline. We show for a large class of substitutions that the resulting word is the restriction of a linear function modulo $1$ and that it can be decided whether the resulting word is space filling or not. The proof uses lattices and the abstract number system associated with the substitution.},
affiliation = {ETH Zürich Departement Mathematik Rämistrasse 101 8092 Zürich (Switzerland); Universiteit Leiden Mathematisch Instituut Niels Bohrweg 1 2300 RA Leiden (The Netherlands)},
author = {Fuchs, Clemens, Tijdeman, Robert},
journal = {Annales de l’institut Fourier},
keywords = {Substitutions; limit word; discretisation of the hyperplane; lattices; automata; abstract number systems; substitutions; discretization of the hyperplane; space filling},
language = {eng},
number = {7},
pages = {2345-2389},
publisher = {Association des Annales de l’institut Fourier},
title = {Substitutions, abstract number systems and the space filling property},
url = {http://eudml.org/doc/10207},
volume = {56},
year = {2006},
}

TY - JOUR
AU - Fuchs, Clemens
AU - Tijdeman, Robert
TI - Substitutions, abstract number systems and the space filling property
JO - Annales de l’institut Fourier
PY - 2006
PB - Association des Annales de l’institut Fourier
VL - 56
IS - 7
SP - 2345
EP - 2389
AB - In this paper we study multi-dimensional words generated by fixed points of substitutions by projecting the integer points on the corresponding broken halfline. We show for a large class of substitutions that the resulting word is the restriction of a linear function modulo $1$ and that it can be decided whether the resulting word is space filling or not. The proof uses lattices and the abstract number system associated with the substitution.
LA - eng
KW - Substitutions; limit word; discretisation of the hyperplane; lattices; automata; abstract number systems; substitutions; discretization of the hyperplane; space filling
UR - http://eudml.org/doc/10207
ER -

References

top
  1. Shigeki Akiyama, Pisot numbers and greedy algorithm, Number theory (Eger, 1996) (1998), 9-21, de Gruyter, Berlin Zbl0919.11063MR1628829
  2. Shigeki Akiyama, Self affine tiling and Pisot numeration system, Number theory and its applications (Kyoto, 1997) 2 (1999), 7-17, Kluwer Acad. Publ., Dordrecht Zbl0999.11065MR1738803
  3. Shigeki Akiyama, Cubic Pisot units with finite beta expansions, Algebraic number theory and Diophantine analysis (Graz, 1998) (2000), 11-26, de Gruyter, Berlin Zbl1001.11038MR1770451
  4. Shigeki Akiyama, Jörg M. Thuswaldner, A survey on topological properties of tiles related to number systems, Geom. Dedicata 109 (2004), 89-105 Zbl1073.37017MR2113188
  5. Pierre Arnoux, Shunji Ito, Pisot substitutions and Rauzy fractals, Bull. Belg. Math. Soc. Simon Stevin 8 (2001), 181-207 Zbl1007.37001MR1838930
  6. Pierre Arnoux, G. Rauzy, Représentation géométrique de suites de complexité 2 n + 1 , Bull. Soc. Math. France 119 (1991), 199-215 Zbl0789.28011MR1116845
  7. Directions in mathematical quasicrystals, 13 (2000), BaakeMichaelM., Providence, RI Zbl0955.00025MR1798986
  8. R. B. Bapat, T. E. S. Raghavan, Nonnegative matrices and applications, 64 (1997), Cambridge University Press, Cambridge Zbl0879.15015MR1449393
  9. Valérie Berthé, Michel Rigo, Abstract numeration systems and tilings, Mathematical foundations of computer science 2005 3618 (2005), 131-143, Springer, Berlin Zbl1156.68443MR2237364
  10. Valérie Berthé, Anne Siegel, Tilings associated with beta-numeration and substitutions, Integers: Electronic Journal of Combinatorial Number Theory 5 (2005) Zbl1139.37008MR2191748
  11. Valérie Berthé, Robert Tijdeman, Lattices and multi-dimensional words, Theoret. Comput. Sci. 319 (2004), 177-202 Zbl1068.37005MR2074953
  12. Valérie Berthé, Laurent Vuillon, Suites doubles de basse complexité, J. Théor. Nombres Bordeaux 12 (2000), 179-208 Zbl1018.37010MR1827847
  13. Valérie Berthé, Laurent Vuillon, Tilings and rotations on the torus: a two-dimensional generalization of Sturmian sequences, Discrete Math. 223 (2000), 27-53 Zbl0970.68124MR1782038
  14. Valérie Berthé, Laurent Vuillon, Palindromes and two-dimensional Sturmian sequences, J. Autom. Lang. Comb. 6 (2001), 121-138 Zbl1002.11026MR1828855
  15. Anne Bertrand, Développements en base de Pisot et répartition modulo 1 , C. R. Acad. Sci. Paris Sér. A-B 285 (1977), A419-A421 Zbl0362.10040MR447134
  16. V. Canterini, Connectedness of geometric representation of substitutions of Pisot type, Bull. Belg. Math. Soc. Simon Stevin 10 (2003), 77-89 Zbl1031.37015MR2032327
  17. Vincent Canterini, Anne Siegel, Automate des préfixes-suffixes associé à une substitution primitive, J. Théor. Nombres Bordeaux 13 (2001), 353-369 Zbl1071.37011MR1879663
  18. Vincent Canterini, Anne Siegel, Geometric representation of substitutions of Pisot type, Trans. Amer. Math. Soc. 353 (2001), 5121-5144 (electronic) Zbl1142.37302MR1852097
  19. Jean-Marie Dumont, Alain Thomas, Systemes de numeration et fonctions fractales relatifs aux substitutions, Theoret. Comput. Sci. 65 (1989), 153-169 Zbl0679.10010MR1020484
  20. Hiromi Ei, Shunji Ito, Tilings from some non-irreducible, Pisot substitutions, Discrete Math. Theor. Comput. Sci. 7 (2005), 81-121 (electronic) Zbl1153.37323MR2164061
  21. Hiromi Ei, Shunji Ito, H. Rao, Atomic surfaces, tilings and coincidences II. Reducible case Zbl1119.52013
  22. Samuel Eilenberg, Automata, languages, and machines. Vol. A, (1974), Academic Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], New York Zbl0317.94045MR530382
  23. Jan-Hendrik Evertse, On the norm form inequality | F ( x ) | h , Publ. Math. Debrecen 56 (2000), 337-374 Zbl0961.11009MR1765986
  24. Christiane Frougny, Boris Solomyak, Finite beta-expansions, Ergodic Theory Dynam. Systems 12 (1992), 713-723 Zbl0814.68065MR1200339
  25. Peter J. Grabner, Michel Rigo, Additive functions with respect to numeration systems on regular languages, Monatsh. Math. 139 (2003), 205-219 Zbl1125.11008MR1994380
  26. S. Ito, H. Rao, Atomic surfaces, tilings and coincidence I. Irreducible case, Israel J. Math. 153 (2006), 129-156 Zbl1143.37013MR2254640
  27. Jeffrey C. Lagarias, Yang Wang, Substitution Delone sets, Discrete Comput. Geom. 29 (2003), 175-209 Zbl1037.52017MR1957227
  28. P. Lecomte, M. Rigo, On the representation of real numbers using regular languages, Theory Comput. Syst. 35 (2002), 13-38 Zbl0993.68050MR1879170
  29. P. Lecomte, M. Rigo, Real numbers having ultimately periodic representations in abstract numeration systems, Inform. and Comput. 192 (2004), 57-83 Zbl1055.11005MR2063624
  30. P. B. A. Lecomte, M. Rigo, Numeration systems on a regular language, Theory Comput. Syst. 34 (2001), 27-44 Zbl0969.68095MR1799066
  31. D. A. Lind, The entropies of topological Markov shifts and a related class of algebraic integers, Ergodic Theory Dynam. Systems 4 (1984), 283-300 Zbl0546.58035MR766106
  32. Douglas Lind, Matrices of Perron numbers, J. Number Theory 40 (1992), 211-217 Zbl0748.11051MR1149738
  33. M. Lothaire, Algebraic combinatorics on words, 90 (2002), Cambridge University Press, Cambridge Zbl1001.68093MR1905123
  34. Marston Morse, Gustav A. Hedlund, Symbolic Dynamics, Amer. J. Math. 60 (1938), 815-866 Zbl0019.33502MR1507944
  35. W. Parry, On the β -expansions of real numbers, Acta Math. Acad. Sci. Hungar. 11 (1960), 401-416 Zbl0099.28103MR142719
  36. G. Rauzy, Nombres algébriques et substitutions, Bull. Soc. Math. France 110 (1982), 147-178 Zbl0522.10032MR667748
  37. A. Rényi, Representations for real numbers and their ergodic properties, Acta Math. Acad. Sci. Hungar 8 (1957), 477-493 Zbl0079.08901MR97374
  38. Michel Rigo, Wolfgang Steiner, Abstract β -expansions and ultimately periodic representations, J. Théor. Nombres Bordeaux 17 (2005), 283-299 Zbl1084.11059MR2152225
  39. S. W. Rosema, R. Tijdeman, The Tribonacci substitution, Integers: Electronic Journal of Combinatorial Number Theory 5 (2005) Zbl1099.11004MR2191759
  40. Raphaël Salem, Algebraic numbers and Fourier analysis, (1963), D. C. Heath and Co., Boston, Mass. Zbl0505.00033MR157941
  41. Yuki Sano, Pierre Arnoux, Shunji Ito, Higher dimensional extensions of substitutions and their dual maps, J. Anal. Math. 83 (2001), 183-206 Zbl0987.11013MR1828491
  42. Klaus Schmidt, On periodic expansions of Pisot numbers and Salem numbers, Bull. London Math. Soc. 12 (1980), 269-278 Zbl0494.10040MR576976
  43. Wolfgang M. Schmidt, Linearformen mit algebraischen Koeffizienten. II, Math. Ann. 191 (1971), 1-20 Zbl0198.07103MR308062
  44. Marjorie Senechal, Quasicrystals and geometry, (1995), Cambridge University Press, Cambridge Zbl0828.52007MR1340198
  45. Anne Siegel, Pure discrete spectrum dynamical system and periodic tiling associated with a substitution, Ann. Inst. Fourier (Grenoble) 54 (2004), 341-381 Zbl1083.37009MR2073838
  46. R. J. Simpson, R. Tijdeman, Multi-dimensional versions of a theorem of Fine and Wilf and a formula of Sylvester, Proc. Amer. Math. Soc. 131 (2003), 1661-1671 (electronic) Zbl1013.05087MR1953570
  47. V. F. Sirvent, B. Solomyak, Pure discrete spectrum for one-dimensional substitution systems of Pisot type, Canad. Math. Bull. 45 (2002), 697-710 Zbl1038.37008MR1941235
  48. J.M. Thuswaldner, Unimodular substitions and their associated tiles Zbl1161.37016
  49. Robert Tijdeman, Rauzy substitutions and multi-dimensional Sturmian words, Theoret. Comput. Sci. 346 (2005), 469-489 Zbl1081.68077MR2187420

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.