Substitutions, abstract number systems and the space filling property

Fuchs, Clemens; Tijdeman, Robert

Fuchs, Clemens; Tijdeman, Robert

Annales de l'Institut Fourier, Volume 56 (2006) no. 7, p. 2345-2389

Abstract
Résumé

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.

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.

MR 2290784 | Zbl pre05176572 | 3 citations in Numdam

DOI : https://doi.org/10.5802/aif.2243
Classification: 11A63, 68R15, 37B10, 05A05, 05B25, 52C07, 52C22, 68Q45, 11K16
Keywords: Substitutions, limit word, discretisation of the hyperplane, lattices, automata, abstract number systems

@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},
     publisher = {Association des Annales de l'institut Fourier},
     volume = {56},
     number = {7},
     year = {2006},
     pages = {2345-2389},
     doi = {10.5802/aif.2243},
     mrnumber = {2290784},
     zbl = {pre05176572},
     language = {en},
     url = {http://www.numdam.org/item/AIF_2006__56_7_2345_0}
}

Fuchs, Clemens; Tijdeman, Robert. Substitutions, abstract number systems and the space filling property. Annales de l'Institut Fourier, Volume 56 (2006) no. 7, pp. 2345-2389. doi : 10.5802/aif.2243. http://www.numdam.org/item/AIF_2006__56_7_2345_0/

References

[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), Kluwer Acad. Publ., Dordrecht (Dev. Math.) Tome 2 (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, Tome 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, Tome 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é $2 n + 1$ , Bull. Soc. Math. France, Tome 119 (1991), pp. 199-215 | Numdam | MR 1116845 | Zbl 0789.28011

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

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

[9] Berthé, Valérie; Rigo, Michel Abstract numeration systems and tilings, Mathematical foundations of computer science 2005, Springer, Berlin (Lecture Notes in Comput. Sci.) Tome 3618 (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, Tome 5 (2005) no. 3, pp. A2 | MR 2191748 | Zbl 05014493

[11] Berthé, Valérie; Tijdeman, Robert Lattices and multi-dimensional words, Theoret. Comput. Sci., Tome 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, Tome 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., Tome 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., Tome 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, Tome 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, Tome 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, Tome 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., Tome 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., Tome 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., Tome 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) | \leq h$ , Publ. Math. Debrecen, Tome 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, Tome 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., Tome 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., Tome 153 (2006), pp. 129-156 | Article | MR 2254640 | Zbl 1143.37013

[27] Lagarias, Jeffrey C.; Wang, Yang Substitution Delone sets, Discrete Comput. Geom., Tome 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., Tome 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., Tome 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., Tome 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, Tome 4 (1984) no. 2, pp. 283-300 | Article | MR 766106 | Zbl 0546.58035

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

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

[34] Morse, Marston; Hedlund, Gustav A. Symbolic Dynamics, Amer. J. Math., Tome 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., Tome 11 (1960), pp. 401-416 | Article | MR 142719 | Zbl 0099.28103

[36] Rauzy, G. Nombres algébriques et substitutions, Bull. Soc. Math. France, Tome 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, Tome 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, Tome 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, Tome 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., Tome 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., Tome 12 (1980) no. 4, pp. 269-278 | Article | MR 576976 | Zbl 0494.10040

[43] Schmidt, Wolfgang M. Linearformen mit algebraischen Koeffizienten. II, Math. Ann., Tome 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), Tome 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., Tome 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., Tome 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., Tome 346 (2005) no. 2-3, pp. 469-489 | Article | MR 2187420 | Zbl 1081.68077