Substitutions, abstract number systems and the space filling property

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.

[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 $\left|F\right(x\left)\right|\le 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 $\beta$-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 $\beta$-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