logo ANNALES DE L'INSTITUT FOURIER

With cedram.org
Table of contents for this issue | Previous article | Next article
Clemens Fuchs; Robert Tijdeman
Substitutions, abstract number systems and the space filling property
(Substitutions et propriété de remplissage de l’espace)
Annales de l'institut Fourier, 56 no. 7 (2006), p. 2345-2389, doi: 10.5802/aif.2243
Article PDF | Reviews MR 2290784 | Zbl pre05176572 | 2 citations in Cedram
Class. Math.: 11A63, 68R15, 37B10, 05A05, 05B25, 52C07, 52C22, 68Q45, 11K16
Keywords: Substitutions, limit word, discretisation of the hyperplane, lattices, automata, abstract number systems

Résumé - 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.

Bibliography

[1] Shigeki Akiyama, Pisot numbers and greedy algorithm, Number theory (Eger, 1996), de Gruyter, 1998, p. 9–21  MR 1628829 |  Zbl 0919.11063
[2] Shigeki Akiyama, Self affine tiling and Pisot numeration system, Number theory and its applications (Kyoto, 1997), Dev. Math. 2, Kluwer Acad. Publ., 1999, p. 7–17  MR 1738803 |  Zbl 0999.11065
[3] Shigeki Akiyama, Cubic Pisot units with finite beta expansions, Algebraic number theory and Diophantine analysis (Graz, 1998), de Gruyter, 2000, p. 11–26  MR 1770451 |  Zbl 1001.11038
[4] Shigeki Akiyama & Jörg M. Thuswaldner, “A survey on topological properties of tiles related to number systems”, Geom. Dedicata 109 (2004), p. 89-105 Article |  MR 2113188 |  Zbl 1073.37017
[5] Pierre Arnoux & Shunji Ito, “Pisot substitutions and Rauzy fractals”, Bull. Belg. Math. Soc. Simon Stevin 8 (2001) no. 2, p. 181-207, Journées Montoises d’Informatique Théorique (Marne-la-Vallée, 2000) Article |  MR 1838930 |  Zbl 1007.37001
[6] Pierre Arnoux & G. Rauzy, “Représentation géométrique de suites de complexité $2n+1$”, Bull. Soc. Math. France 119 (1991), p. 199-215 Numdam |  MR 1116845 |  Zbl 0789.28011
[7] Michael Baake & Robert V. Moody (ed.), Directions in mathematical quasicrystals, CRM Monograph Series 13, American Mathematical Society, Providence, RI, 2000  MR 1798986 |  Zbl 0955.00025
[8] R. B. Bapat & T. E. S. Raghavan, Nonnegative matrices and applications, Encyclopedia of Mathematics and its Applications 64, Cambridge University Press, Cambridge, 1997  MR 1449393 |  Zbl 0879.15015
[9] Valérie Berthé & Michel Rigo, Abstract numeration systems and tilings, Mathematical foundations of computer science 2005, Lecture Notes in Comput. Sci. 3618, Springer, 2005, p. 131–143  MR 2237364 |  Zbl 1156.68443
[10] Valérie Berthé & Anne Siegel, “Tilings associated with beta-numeration and substitutions”, Integers: Electronic Journal of Combinatorial Number Theory 5 (2005) no. 3  MR 2191748 |  Zbl 05014493
[11] Valérie Berthé & Robert Tijdeman, “Lattices and multi-dimensional words”, Theoret. Comput. Sci. 319 (2004) no. 1-3, p. 177-202 Article |  MR 2074953 |  Zbl 1068.37005
[12] Valérie Berthé & Laurent Vuillon, “Suites doubles de basse complexité”, J. Théor. Nombres Bordeaux 12 (2000) no. 1, p. 179-208 Cedram |  MR 1827847 |  Zbl 1018.37010
[13] Valérie Berthé & Laurent Vuillon, “Tilings and rotations on the torus: a two-dimensional generalization of Sturmian sequences”, Discrete Math. 223 (2000) no. 1-3, p. 27-53 Article |  MR 1782038 |  Zbl 0970.68124
[14] Valérie Berthé & Laurent Vuillon, “Palindromes and two-dimensional Sturmian sequences”, J. Autom. Lang. Comb. 6 (2001) no. 2, p. 121-138  MR 1828855 |  Zbl 1002.11026
[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) no. 6, p. A419-A421  MR 447134 |  Zbl 0362.10040
[16] V. Canterini, “Connectedness of geometric representation of substitutions of Pisot type”, Bull. Belg. Math. Soc. Simon Stevin 10 (2003) no. 1, p. 77-89 Article |  MR 2032327 |  Zbl 1031.37015
[17] Vincent Canterini & Anne Siegel, “Automate des préfixes-suffixes associé à une substitution primitive”, J. Théor. Nombres Bordeaux 13 (2001) no. 2, p. 353-369 Cedram |  MR 1879663 |  Zbl 1071.37011
[18] Vincent Canterini & Anne Siegel, “Geometric representation of substitutions of Pisot type”, Trans. Amer. Math. Soc. 353 (2001) no. 12, p. 5121-5144 (electronic) Article |  MR 1852097 |  Zbl 01663181
[19] Jean-Marie Dumont & Alain Thomas, “Systemes de numeration et fonctions fractales relatifs aux substitutions”, Theoret. Comput. Sci. 65 (1989) no. 2, p. 153-169 Article |  MR 1020484 |  Zbl 0679.10010
[20] Hiromi Ei & Shunji Ito, “Tilings from some non-irreducible, Pisot substitutions”, Discrete Math. Theor. Comput. Sci. 7 (2005) no. 1, p. 81-121 (electronic)  MR 2164061 |  Zbl 1153.37323
[21] Hiromi Ei, Shunji Ito & H. Rao, “Atomic surfaces, tilings and coincidences II. Reducible case”, Ann. Inst. Fourier (Grenoble), to appear Cedram
[22] Samuel Eilenberg, Automata, languages, and machines. Vol. A, Academic Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], New York, 1974, Pure and Applied Mathematics, Vol. 58  MR 530382 |  Zbl 0317.94045
[23] Jan-Hendrik Evertse, “On the norm form inequality $\vert F(x)\vert \le h$”, Publ. Math. Debrecen 56 (2000) no. 3-4, p. 337-374, Dedicated to Professor Kálmán Győry on the occasion of his 60th birthday  MR 1765986 |  Zbl 0961.11009
[24] Christiane Frougny & Boris Solomyak, “Finite beta-expansions”, Ergodic Theory Dynam. Systems 12 (1992) no. 4, p. 713-723 Article |  MR 1200339 |  Zbl 0814.68065
[25] Peter J. Grabner & Michel Rigo, “Additive functions with respect to numeration systems on regular languages”, Monatsh. Math. 139 (2003) no. 3, p. 205-219 Article |  MR 1994380 |  Zbl 01969578
[26] S. Ito & H. Rao, “Atomic surfaces, tilings and coincidence I. Irreducible case”, Israel J. Math. 153 (2006), p. 129-156 Article |  MR 2254640 |  Zbl 1143.37013
[27] Jeffrey C. Lagarias & Yang Wang, “Substitution Delone sets”, Discrete Comput. Geom. 29 (2003) no. 2, p. 175-209  MR 1957227 |  Zbl 1037.52017
[28] P. Lecomte & M. Rigo, “On the representation of real numbers using regular languages”, Theory Comput. Syst. 35 (2002) no. 1, p. 13-38  MR 1879170 |  Zbl 0993.68050
[29] P. Lecomte & M. Rigo, “Real numbers having ultimately periodic representations in abstract numeration systems”, Inform. and Comput. 192 (2004) no. 1, p. 57-83 Article |  MR 2063624 |  Zbl 1055.11005
[30] P. B. A. Lecomte & M. Rigo, “Numeration systems on a regular language”, Theory Comput. Syst. 34 (2001) no. 1, p. 27-44 Article |  MR 1799066 |  Zbl 0969.68095
[31] D. A. Lind, “The entropies of topological Markov shifts and a related class of algebraic integers”, Ergodic Theory Dynam. Systems 4 (1984) no. 2, p. 283-300 Article |  MR 766106 |  Zbl 0546.58035
[32] Douglas Lind, “Matrices of Perron numbers”, J. Number Theory 40 (1992) no. 2, p. 211-217 Article |  MR 1149738 |  Zbl 0748.11051
[33] M. Lothaire, Algebraic combinatorics on words, Encyclopedia of Mathematics and its Applications 90, Cambridge University Press, Cambridge, 2002  MR 1905123 |  Zbl 1001.68093
[34] Marston Morse & Gustav A. Hedlund, “Symbolic Dynamics”, Amer. J. Math. 60 (1938) no. 4, p. 815-866 Article |  MR 1507944 |  Zbl 0019.33502
[35] 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
[36] G. Rauzy, “Nombres algébriques et substitutions”, Bull. Soc. Math. France 110 (1982) no. 2, p. 147-178 Numdam |  MR 667748 |  Zbl 0522.10032
[37] A. 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
[38] Michel Rigo & Wolfgang Steiner, “Abstract $\beta $-expansions and ultimately periodic representations”, J. Théor. Nombres Bordeaux 17 (2005) no. 1, p. 283-299 Cedram |  MR 2152225 |  Zbl 02205446
[39] S. W. Rosema & R. Tijdeman, “The Tribonacci substitution”, Integers: Electronic Journal of Combinatorial Number Theory 5 (2005) no. 3  MR 2191759 |  Zbl 05014504
[40] Raphaël Salem, Algebraic numbers and Fourier analysis, D. C. Heath and Co., Boston, Mass., 1963  MR 157941 |  Zbl 0505.00033
[41] Yuki Sano, Pierre Arnoux & Shunji Ito, “Higher dimensional extensions of substitutions and their dual maps”, J. Anal. Math. 83 (2001), p. 183-206 Article |  MR 1828491 |  Zbl 0987.11013
[42] Klaus Schmidt, “On periodic expansions of Pisot numbers and Salem numbers”, Bull. London Math. Soc. 12 (1980) no. 4, p. 269-278 Article |  MR 576976 |  Zbl 0494.10040
[43] Wolfgang M. Schmidt, “Linearformen mit algebraischen Koeffizienten. II”, Math. Ann. 191 (1971), p. 1-20 Article |  MR 308062 |  Zbl 0198.07103
[44] Marjorie Senechal, Quasicrystals and geometry, Cambridge University Press, Cambridge, 1995  MR 1340198 |  Zbl 0828.52007
[45] Anne Siegel, “Pure discrete spectrum dynamical system and periodic tiling associated with a substitution”, Ann. Inst. Fourier (Grenoble) 54 (2004) no. 2, p. 341-381 Cedram |  MR 2073838 |  Zbl 1083.37009
[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) no. 6, p. 1661-1671 (electronic) Article |  MR 1953570 |  Zbl 1013.05087
[47] V. F. Sirvent & B. Solomyak, “Pure discrete spectrum for one-dimensional substitution systems of Pisot type”, Canad. Math. Bull. 45 (2002) no. 4, p. 697-710, Dedicated to Robert V. Moody Article |  MR 1941235 |  Zbl 1038.37008
[48] J.M. Thuswaldner, “Unimodular substitions and their associated tiles”, J. Théor. Nombres Bordeaux, to appear Cedram |  Zbl 05135401
[49] Robert Tijdeman, “Rauzy substitutions and multi-dimensional Sturmian words”, Theoret. Comput. Sci. 346 (2005) no. 2-3, p. 469-489 Article |  MR 2187420 |  Zbl 1081.68077
top