Substitutions, abstract number systems and the space filling property

Fuchs, Clemens; Tijdeman, Robert

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.

Classification : 11A63, 68R15, 37B10, 05A05, 05B25, 52C07, 52C22, 68Q45, 11K16
Keywords: Substitutions, limit word, discretisation of the hyperplane, lattices, automata, abstract number systems
Mot clés : substitutions, mot limite, hyperplan discret, réseaux, automates, systèmes de numération abstraits

[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