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 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 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
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://www.numdam.org/articles/10.5802/aif.2243/} }
TY - JOUR AU - Fuchs, Clemens AU - Tijdeman, Robert TI - Substitutions, abstract number systems and the space filling property JO - Annales de l'Institut Fourier PY - 2006 DA - 2006/// SP - 2345 EP - 2389 VL - 56 IS - 7 PB - Association des Annales de l’institut Fourier UR - http://www.numdam.org/articles/10.5802/aif.2243/ UR - https://www.ams.org/mathscinet-getitem?mr=2290784 UR - https://doi.org/10.5802/aif.2243 DO - 10.5802/aif.2243 LA - en ID - AIF_2006__56_7_2345_0 ER -
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://www.numdam.org/articles/10.5802/aif.2243/
[1] Pisot numbers and greedy algorithm, Number theory (Eger, 1996), de Gruyter, Berlin, 1998, pp. 9-21 | MR 1628829 | Zbl 0919.11063
[2] 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] 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] 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] 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] Représentation géométrique de suites de complexité , Bull. Soc. Math. France, Volume 119 (1991), pp. 199-215 | Numdam | MR 1116845 | Zbl 0789.28011
[7] Directions in mathematical quasicrystals, CRM Monograph Series, 13, American Mathematical Society, Providence, RI, 2000 | MR 1798986 | Zbl 0955.00025
[8] Nonnegative matrices and applications, Encyclopedia of Mathematics and its Applications, 64, Cambridge University Press, Cambridge, 1997 | MR 1449393 | Zbl 0879.15015
[9] 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] 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] Lattices and multi-dimensional words, Theoret. Comput. Sci., Volume 319 (2004) no. 1-3, pp. 177-202 | Article | MR 2074953 | Zbl 1068.37005
[12] 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] 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] Palindromes and two-dimensional Sturmian sequences, J. Autom. Lang. Comb., Volume 6 (2001) no. 2, pp. 121-138 | MR 1828855 | Zbl 1002.11026
[15] Développements en base de Pisot et répartition modulo , C. R. Acad. Sci. Paris Sér. A-B, Volume 285 (1977) no. 6, p. A419-A421 | MR 447134 | Zbl 0362.10040
[16] 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] 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] 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] 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] 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] Atomic surfaces, tilings and coincidences II. Reducible case Ann. Inst. Fourier (Grenoble), to appear | Numdam
[22] 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] On the norm form inequality , 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] Finite beta-expansions, Ergodic Theory Dynam. Systems, Volume 12 (1992) no. 4, pp. 713-723 | Article | MR 1200339 | Zbl 0814.68065
[25] 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] Atomic surfaces, tilings and coincidence I. Irreducible case, Israel J. Math., Volume 153 (2006), pp. 129-156 | Article | MR 2254640 | Zbl 1143.37013
[27] Substitution Delone sets, Discrete Comput. Geom., Volume 29 (2003) no. 2, pp. 175-209 | MR 1957227 | Zbl 1037.52017
[28] 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] 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] Numeration systems on a regular language, Theory Comput. Syst., Volume 34 (2001) no. 1, pp. 27-44 | Article | MR 1799066 | Zbl 0969.68095
[31] 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] Matrices of Perron numbers, J. Number Theory, Volume 40 (1992) no. 2, pp. 211-217 | Article | MR 1149738 | Zbl 0748.11051
[33] Algebraic combinatorics on words, Encyclopedia of Mathematics and its Applications, 90, Cambridge University Press, Cambridge, 2002 | MR 1905123 | Zbl 1001.68093
[34] Symbolic Dynamics, Amer. J. Math., Volume 60 (1938) no. 4, pp. 815-866 | Article | MR 1507944 | Zbl 0019.33502
[35] On the -expansions of real numbers, Acta Math. Acad. Sci. Hungar., Volume 11 (1960), pp. 401-416 | Article | MR 142719 | Zbl 0099.28103
[36] Nombres algébriques et substitutions, Bull. Soc. Math. France, Volume 110 (1982) no. 2, pp. 147-178 | Numdam | MR 667748 | Zbl 0522.10032
[37] 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] 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] The Tribonacci substitution, Integers: Electronic Journal of Combinatorial Number Theory, Volume 5 (2005) no. 3, pp. A13 | MR 2191759 | Zbl 05014504
[40] Algebraic numbers and Fourier analysis, D. C. Heath and Co., Boston, Mass., 1963 | MR 157941 | Zbl 0505.00033
[41] 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] 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] Linearformen mit algebraischen Koeffizienten. II, Math. Ann., Volume 191 (1971), pp. 1-20 | Article | MR 308062 | Zbl 0198.07103
[44] Quasicrystals and geometry, Cambridge University Press, Cambridge, 1995 | MR 1340198 | Zbl 0828.52007
[45] 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] 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] 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] Unimodular substitions and their associated tiles (J. Théor. Nombres Bordeaux, to appear) | Numdam | Zbl 05135401
[49] 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
Cité par Sources :