Substitutions, abstract number systems and the space filling property
[Substitutions et propriété de remplissage de l’espace]
Annales de l'Institut Fourier, Tome 56 (2006) no. 7, pp. 2345-2389.

Dans cet article nous étudions des mots multidimensionnels engendrés par des points fixes de substitutions, et obtenus en projetant les points entiers sur la demi-droite brisée correspondante. Nous montrons que pour une grande classe de substitutions le mot correspondant est la restriction d’une fonction linéaire modulo 1 et qu’il est possible de décider si le mot résultant remplit l’espace. La preuve utilise des réseaux et le système de numération abstrait associé à la substitution.

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.

DOI : https://doi.org/10.5802/aif.2243
Classification : 11A63,  68R15,  37B10,  05A05,  05B25,  52C07,  52C22,  68Q45,  11K16
Mots clés : substitutions, mot limite, hyperplan discret, réseaux, automates, systèmes de numération abstraits
@article{AIF_2006__56_7_2345_0,
     author = {Fuchs, Clemens and Tijdeman, Robert},
     title = {Substitutions, abstract number systems and the space filling property},
     journal = {Annales de l'Institut Fourier},
     pages = {2345--2389},
     publisher = {Association des Annales de l{\textquoteright}institut Fourier},
     volume = {56},
     number = {7},
     year = {2006},
     doi = {10.5802/aif.2243},
     mrnumber = {2290784},
     language = {en},
     url = {http://archive.numdam.org/articles/10.5802/aif.2243/}
}
Fuchs, Clemens; Tijdeman, Robert. Substitutions, abstract number systems and the space filling property. Annales de l'Institut Fourier, Tome 56 (2006) no. 7, pp. 2345-2389. doi : 10.5802/aif.2243. http://archive.numdam.org/articles/10.5802/aif.2243/

[1] Akiyama, Shigeki Pisot numbers and greedy algorithm, Number theory (Eger, 1996), de Gruyter, Berlin, 1998, pp. 9-21 | MR 1628829 | Zbl 0919.11063

[2] Akiyama, Shigeki Self affine tiling and Pisot numeration system, Number theory and its applications (Kyoto, 1997) (Dev. Math.), Volume 2, Kluwer Acad. Publ., Dordrecht, 1999, pp. 7-17 | MR 1738803 | Zbl 0999.11065

[3] Akiyama, Shigeki Cubic Pisot units with finite beta expansions, Algebraic number theory and Diophantine analysis (Graz, 1998), de Gruyter, Berlin, 2000, pp. 11-26 | MR 1770451 | Zbl 1001.11038

[4] Akiyama, Shigeki; Thuswaldner, Jörg M. A survey on topological properties of tiles related to number systems, Geom. Dedicata, Volume 109 (2004), pp. 89-105 | Article | MR 2113188 | Zbl 1073.37017

[5] Arnoux, Pierre; Ito, Shunji Pisot substitutions and Rauzy fractals, Bull. Belg. Math. Soc. Simon Stevin, Volume 8 (2001) no. 2, pp. 181-207 Journées Montoises d’Informatique Théorique (Marne-la-Vallée, 2000) | MR 1838930 | Zbl 1007.37001

[6] Arnoux, Pierre; Rauzy, G. Représentation géométrique de suites de complexité 2n+1, Bull. Soc. Math. France, Volume 119 (1991), pp. 199-215 | Numdam | MR 1116845 | Zbl 0789.28011

[7] Baake, Michael; Moody, Robert V. Directions in mathematical quasicrystals, CRM Monograph Series, 13, American Mathematical Society, Providence, RI, 2000 | MR 1798986 | Zbl 0955.00025

[8] Bapat, R. B.; Raghavan, T. E. S. Nonnegative matrices and applications, Encyclopedia of Mathematics and its Applications, 64, Cambridge University Press, Cambridge, 1997 | MR 1449393 | Zbl 0879.15015

[9] Berthé, Valérie; Rigo, Michel Abstract numeration systems and tilings, Mathematical foundations of computer science 2005 (Lecture Notes in Comput. Sci.), Volume 3618, Springer, Berlin, 2005, pp. 131-143 | MR 2237364 | Zbl 1156.68443

[10] Berthé, Valérie; Siegel, Anne Tilings associated with beta-numeration and substitutions, Integers: Electronic Journal of Combinatorial Number Theory, Volume 5 (2005) no. 3, pp. A2 | MR 2191748 | Zbl 05014493

[11] Berthé, Valérie; Tijdeman, Robert Lattices and multi-dimensional words, Theoret. Comput. Sci., Volume 319 (2004) no. 1-3, pp. 177-202 | Article | MR 2074953 | Zbl 1068.37005

[12] Berthé, Valérie; Vuillon, Laurent Suites doubles de basse complexité, J. Théor. Nombres Bordeaux, Volume 12 (2000) no. 1, pp. 179-208 | Article | Numdam | MR 1827847 | Zbl 1018.37010

[13] Berthé, Valérie; Vuillon, Laurent Tilings and rotations on the torus: a two-dimensional generalization of Sturmian sequences, Discrete Math., Volume 223 (2000) no. 1-3, pp. 27-53 | Article | MR 1782038 | Zbl 0970.68124

[14] Berthé, Valérie; Vuillon, Laurent Palindromes and two-dimensional Sturmian sequences, J. Autom. Lang. Comb., Volume 6 (2001) no. 2, pp. 121-138 | MR 1828855 | Zbl 1002.11026

[15] Bertrand, Anne Développements en base de Pisot et répartition modulo 1, C. R. Acad. Sci. Paris Sér. A-B, Volume 285 (1977) no. 6, p. A419-A421 | MR 447134 | Zbl 0362.10040

[16] Canterini, V. Connectedness of geometric representation of substitutions of Pisot type, Bull. Belg. Math. Soc. Simon Stevin, Volume 10 (2003) no. 1, pp. 77-89 | MR 2032327 | Zbl 1031.37015

[17] Canterini, Vincent; Siegel, Anne Automate des préfixes-suffixes associé à une substitution primitive, J. Théor. Nombres Bordeaux, Volume 13 (2001) no. 2, pp. 353-369 | Article | Numdam | MR 1879663 | Zbl 1071.37011

[18] Canterini, Vincent; Siegel, Anne Geometric representation of substitutions of Pisot type, Trans. Amer. Math. Soc., Volume 353 (2001) no. 12, p. 5121-5144 (electronic) | Article | MR 1852097 | Zbl 01663181

[19] Dumont, Jean-Marie; Thomas, Alain Systemes de numeration et fonctions fractales relatifs aux substitutions, Theoret. Comput. Sci., Volume 65 (1989) no. 2, pp. 153-169 | Article | MR 1020484 | Zbl 0679.10010

[20] Ei, Hiromi; Ito, Shunji Tilings from some non-irreducible, Pisot substitutions, Discrete Math. Theor. Comput. Sci., Volume 7 (2005) no. 1, p. 81-121 (electronic) | MR 2164061 | Zbl 1153.37323

[21] Ei, Hiromi; Ito, Shunji; Rao, H. Atomic surfaces, tilings and coincidences II. Reducible case Ann. Inst. Fourier (Grenoble), to appear | Numdam

[22] Eilenberg, Samuel 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] Evertse, Jan-Hendrik On the norm form inequality |F(x)|h, Publ. Math. Debrecen, Volume 56 (2000) no. 3-4, pp. 337-374 (Dedicated to Professor Kálmán Győry on the occasion of his 60th birthday) | MR 1765986 | Zbl 0961.11009

[24] Frougny, Christiane; Solomyak, Boris Finite beta-expansions, Ergodic Theory Dynam. Systems, Volume 12 (1992) no. 4, pp. 713-723 | Article | MR 1200339 | Zbl 0814.68065

[25] Grabner, Peter J.; Rigo, Michel Additive functions with respect to numeration systems on regular languages, Monatsh. Math., Volume 139 (2003) no. 3, pp. 205-219 | Article | MR 1994380 | Zbl 01969578

[26] Ito, S.; Rao, H. Atomic surfaces, tilings and coincidence I. Irreducible case, Israel J. Math., Volume 153 (2006), pp. 129-156 | Article | MR 2254640 | Zbl 1143.37013

[27] Lagarias, Jeffrey C.; Wang, Yang Substitution Delone sets, Discrete Comput. Geom., Volume 29 (2003) no. 2, pp. 175-209 | MR 1957227 | Zbl 1037.52017

[28] Lecomte, P.; Rigo, M. On the representation of real numbers using regular languages, Theory Comput. Syst., Volume 35 (2002) no. 1, pp. 13-38 | MR 1879170 | Zbl 0993.68050

[29] Lecomte, P.; Rigo, M. Real numbers having ultimately periodic representations in abstract numeration systems, Inform. and Comput., Volume 192 (2004) no. 1, pp. 57-83 | Article | MR 2063624 | Zbl 1055.11005

[30] Lecomte, P. B. A.; Rigo, M. Numeration systems on a regular language, Theory Comput. Syst., Volume 34 (2001) no. 1, pp. 27-44 | Article | MR 1799066 | Zbl 0969.68095

[31] Lind, D. A. The entropies of topological Markov shifts and a related class of algebraic integers, Ergodic Theory Dynam. Systems, Volume 4 (1984) no. 2, pp. 283-300 | Article | MR 766106 | Zbl 0546.58035

[32] Lind, Douglas Matrices of Perron numbers, J. Number Theory, Volume 40 (1992) no. 2, pp. 211-217 | Article | MR 1149738 | Zbl 0748.11051

[33] Lothaire, M. Algebraic combinatorics on words, Encyclopedia of Mathematics and its Applications, 90, Cambridge University Press, Cambridge, 2002 | MR 1905123 | Zbl 1001.68093

[34] Morse, Marston; Hedlund, Gustav A. Symbolic Dynamics, Amer. J. Math., Volume 60 (1938) no. 4, pp. 815-866 | Article | MR 1507944 | Zbl 0019.33502

[35] Parry, W. On the β-expansions of real numbers, Acta Math. Acad. Sci. Hungar., Volume 11 (1960), pp. 401-416 | Article | MR 142719 | Zbl 0099.28103

[36] Rauzy, G. Nombres algébriques et substitutions, Bull. Soc. Math. France, Volume 110 (1982) no. 2, pp. 147-178 | Numdam | MR 667748 | Zbl 0522.10032

[37] Rényi, A. Representations for real numbers and their ergodic properties, Acta Math. Acad. Sci. Hungar, Volume 8 (1957), pp. 477-493 | Article | MR 97374 | Zbl 0079.08901

[38] Rigo, Michel; Steiner, Wolfgang Abstract β-expansions and ultimately periodic representations, J. Théor. Nombres Bordeaux, Volume 17 (2005) no. 1, pp. 283-299 | Article | Numdam | MR 2152225 | Zbl 02205446

[39] Rosema, S. W.; Tijdeman, R. The Tribonacci substitution, Integers: Electronic Journal of Combinatorial Number Theory, Volume 5 (2005) no. 3, pp. A13 | MR 2191759 | Zbl 05014504

[40] Salem, Raphaël Algebraic numbers and Fourier analysis, D. C. Heath and Co., Boston, Mass., 1963 | MR 157941 | Zbl 0505.00033

[41] Sano, Yuki; Arnoux, Pierre; Ito, Shunji Higher dimensional extensions of substitutions and their dual maps, J. Anal. Math., Volume 83 (2001), pp. 183-206 | Article | MR 1828491 | Zbl 0987.11013

[42] Schmidt, Klaus On periodic expansions of Pisot numbers and Salem numbers, Bull. London Math. Soc., Volume 12 (1980) no. 4, pp. 269-278 | Article | MR 576976 | Zbl 0494.10040

[43] Schmidt, Wolfgang M. Linearformen mit algebraischen Koeffizienten. II, Math. Ann., Volume 191 (1971), pp. 1-20 | Article | MR 308062 | Zbl 0198.07103

[44] Senechal, Marjorie Quasicrystals and geometry, Cambridge University Press, Cambridge, 1995 | MR 1340198 | Zbl 0828.52007

[45] Siegel, Anne Pure discrete spectrum dynamical system and periodic tiling associated with a substitution, Ann. Inst. Fourier (Grenoble), Volume 54 (2004) no. 2, pp. 341-381 | Article | Numdam | MR 2073838 | Zbl 1083.37009

[46] Simpson, R. J.; Tijdeman, R. Multi-dimensional versions of a theorem of Fine and Wilf and a formula of Sylvester, Proc. Amer. Math. Soc., Volume 131 (2003) no. 6, p. 1661-1671 (electronic) | Article | MR 1953570 | Zbl 1013.05087

[47] Sirvent, V. F.; Solomyak, B. Pure discrete spectrum for one-dimensional substitution systems of Pisot type, Canad. Math. Bull., Volume 45 (2002) no. 4, pp. 697-710 (Dedicated to Robert V. Moody) | Article | MR 1941235 | Zbl 1038.37008

[48] Thuswaldner, J.M. Unimodular substitions and their associated tiles (J. Théor. Nombres Bordeaux, to appear) | Numdam | Zbl 05135401

[49] Tijdeman, Robert Rauzy substitutions and multi-dimensional Sturmian words, Theoret. Comput. Sci., Volume 346 (2005) no. 2-3, pp. 469-489 | Article | MR 2187420 | Zbl 1081.68077