Substitutions, abstract number systems and the space filling property

Fuchs, Clemens; Tijdeman, Robert

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

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.

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

[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 | Zbl

[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 | Zbl

[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 | DOI | MR | Zbl

[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 | Zbl

[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 | Zbl

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

[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 | Zbl

[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 | Zbl

[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 | Zbl

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

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

[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 | DOI | MR | Zbl

[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 | Zbl

[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 | Zbl

[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 | Zbl

[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 | DOI | Numdam | MR | Zbl

[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) | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[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 | Zbl

[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 | Zbl

[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 | Zbl

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

[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 | DOI | MR | Zbl

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

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

[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 | Zbl

[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 | DOI | MR | Zbl

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

[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 | DOI | MR | Zbl

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

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

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

[35] Parry, W. On the $\beta$-expansions of real numbers, Acta Math. Acad. Sci. Hungar., Volume 11 (1960), pp. 401-416 | DOI | MR | Zbl

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

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

[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 | DOI | Numdam | MR | Zbl

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

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

[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 | DOI | MR | Zbl

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

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

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

[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 | DOI | Numdam | MR | Zbl

[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) | DOI | MR | Zbl

[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) | DOI | MR | Zbl

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

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