Discrete planes, ${\mathbb{Z}}^2$-actions, Jacobi-Perron algorithm and substitutions

Arnoux, Pierre; Berthé, Valérie; Ito, Shunji

Annales de l'Institut Fourier, Tome 52 (2002) no. 2, pp. 305-349.

Nous définissons des substitutions bi-dimensionnelles; ces substitutions engendrent des suites doubles reliées à des approximations discrètes de plans irrationnels. Elles sont obtenues au moyen de l’algorithme classique de Jacobi Perron, en définissant l’induction d’une action de ${\mathbb{Z}}^2$ par rotations sur le cercle. On donne ainsi une interprétation géométrique nouvelle de l’algorithme de Jacobi-Perron, comme application opérant sur l’espace des paramètres des actions de ${\mathbb{Z}}^2$ par rotations.

We introduce two-dimensional substitutions generating two-dimensional sequences related to discrete approximations of irrational planes. These two-dimensional substitutions are produced by the classical Jacobi-Perron continued fraction algorithm, by the way of induction of a ${\mathbb{Z}}^2$-action by rotations on the circle. This gives a new geometric interpretation of the Jacobi-Perron algorithm, as a map operating on the parameter space of ${\mathbb{Z}}^2$-actions by rotations.

Classification : 11A55, 11J70, 40A15, 68R15
Keywords: substitutions, generalized continued fractions, discrete plans, tilings, Jacobi-Perron algorithm, induction, ${\mathbb {Z}}^2$-actions, two-dimensional sequences
Mot clés : substitutions, fractions continues généralisées, plans discrets, pavages, algorithme de Jacobi-Perron, induction, actions de ${\mathbb {Z}}^2$, suites doubles

[1] P. Arnoux; E. Goles and S. Martinez (eds.) Chaos from order, a worked out example, Complex Systems (2001), pp. 1-67

[2] P. Arnoux; V. Berthé, S. Ferenczi Sturmian sequences, Substitutions in Dynamics, Arithmetics and Combinatorics (To appear in Lecture Notes in Math.)

[3] P. Arnoux; S. Ito Pisot substitutions and Rauzy fractals, Bull. Belg. Math. Soc. Simon Stevin, Volume 8 (2001), pp. 181-207 | MR | Zbl

[4] P. Arnoux; S. Ferenczi; P. Hubert Trajectories of rotations, Acta Arith., Volume 87 (1999), pp. 209-217 | MR | Zbl

[5] P. Arnoux; S. Ito; Y. Sano Higher dimensional extensions of substitutions and their dual maps, J. Anal. Math., Volume 83 (2001), pp. 183-206 | DOI | MR | Zbl

[6] P. Arnoux; G. Rauzy 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] J. Berstel Tracé de droites, fractions continues et morphismes itérés, Mots, Lang. Raison. Calc. (1990), pp. 298-309

[8] J. Berstel; Dassow, Rozenberg Recent results in Sturmian words, Developments in Language Theory II (1996), pp. 13-24 | Zbl

[9] J. Berstel; P. Séébold Chapter 2: Sturmian words in M. Lothaire, Algebraic Combinatorics on Words (To appear)

[10] V. Berthé; L. Vuillon Tilings and rotations on the torus: a two-dimensional generalization of Sturmian sequences, Discrete Math., Volume 223 (2000), pp. 27-53 | DOI | MR | Zbl

[11] V. Berthé; L. Vuillon Suites doubles de basse complexité, J. Th. Nombres Bordeaux, Volume 12 (2000), pp. 179-208 | DOI | Numdam | MR | Zbl

[12] V. Berthé; L. Vuillon Palindromes and two-dimensional Sturmian sequences, J. Auto. Lang. Comp., Volume 6 (2001), pp. 121-138 | MR | Zbl

[13] A.J. Brentjes Multi-dimensional continued fraction algorithms, Mathematical Centre Tracts, 145, Matematisch Centrum, Amsterdam, 1981 | Zbl

[14] A. Broise Fractions continues multidimensionnelles et lois stables, Bull. Soc. Math. France, Volume 124 (1999), pp. 97-139 | Numdam | MR | Zbl

[15] A. Broise-Alamichei; Y. Guivarc'h Exposants caratéristiques de l'algorithme de Jacobi-Perron et la transformation associée, Ann. Inst. Fourier, Volume 51 (2001) no. 3, pp. 565-686 | DOI | Numdam | MR | Zbl

[16] T.C. Brown Descriptions of the characteristic sequence of an irrational, Canad. Math. Bull., Volume 36 (1993), pp. 15-21 | DOI | MR | Zbl

[17] V. Canterini; A. Siegel Geometric representations of primitive substitutions of Pisot type (To appear in Trans. Amer. Math. Soc.) | MR | Zbl

[18] J.H. Conway; C. Radin Quaquaversal tilings and rotations, Inventiones Math., Volume 132 (1998), pp. 179-188 | DOI | MR | Zbl

[19] F. Durand A characterization of substitutive sequences using return words, Discrete Math., Volume 179 (1998), pp. 89-101 | DOI | MR | Zbl

[20] J. Françon Sur la topologie d'un plan arithmétique, Th. Comput. Sci., Volume 156 (1996), pp. 159-176 | DOI | MR | Zbl

[21] D. Giammarresi; A. Restivo; A. Salomaa, G. Rozenberg Two-dimensional Languages, Handbook of Formal languages, Volume vol. 3 (1997)

[22] C. Goodman-Strauss Matching rules and substitution tilings, Annals of Math., Volume 147 (1998), pp. 181-223 | DOI | MR | Zbl

[23] S. Ito; M. Kimura On Rauzy fractal, Japan J. Indust. Appl. Math., Volume 8 (1991), pp. 461-486 | DOI | MR | Zbl

[24] S. Ito; M. Ohtsuki Modified Jacobi-Perron algorithm and generating Markov partitions for special hyperbolic toral automorphisms, Tokyo J. Math., Volume 16 (1993), pp. 441-472 | DOI | MR | Zbl

[25] S. Ito; M. Ohtsuki Parallelogram tilings and Jacobi-Perron algorithm, Tokyo J. Math., Volume 17 (1994), pp. 33-58 | DOI | MR | Zbl

[26] A.B. Katok; A.M. Stepin Approximations in ergodic theory, Usp. Math. Nauk. (in Russian), Volume 22 (1967), pp. 81-106 | MR | Zbl

[26] A.B. Katok; A.M. Stepin Approximations in ergodic theory, Russian Math. Surveys, Volume 22 (1967), pp. 76-102 | MR | Zbl

[27] A. Messaoudi Propriétés arithmétiques et dynamiques du fractal de Rauzy, J. Th. Nombres Bordeaux, Volume 10 (1998), pp. 135-162 | DOI | Numdam | MR | Zbl

[28] A. Messaoudi Frontière du fractal de Rauzy et système de numération complexe, Acta Arith., Volume 95 (2000), pp. 195-224 | MR | Zbl

[29] M. Morse; G.A. Hedlund Symbolic dynamics II: Sturmian trajectories, Amer. J. Math., Volume 62 (1940), pp. 1-42 | DOI | JFM | MR | Zbl

[30] N. Priebe Towards a characterization of self-similar tilings in terms of derived Voronoï tessellations, Geom. Dedicata, Volume 79 (2000), pp. 239-265 | DOI | MR | Zbl

[31] M. Queffélec Substitution dynamical systems, Spectral analysis (Lecture Notes in Math.), Volume 1294 (1987) | Zbl

[32] C. Radin Space tilings and substitutions, Geom. Dedicata, Volume 55 (1995), pp. 257-264 | DOI | MR | Zbl

[33] C. Radin Miles of tiles, Student Mathematical Library, Vol. 1, Amer. Math. Soc., Providence, 1999 | MR | Zbl

[34] C. Radin A homeomorphism invariant for substitution tiling spaces (To appear in Geom. Dedicata) | MR | Zbl

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

[36] J.-P. Reveillès Combinatorial pieces in digital lines and planes, Vision geometry IV (San Diego, CA, 1995) (Proc. SPIE), Volume 2573, pp. 23-24

[37] O. Salon Suites automatiques à multi-indices, Sém. Th. Nombres Bordeaux, Volume exp. no 4 (1986-1987) | Zbl

[38] O. Salon Suites automatiques à multi-indices et algébricité, C. R. Acad. Sci. Paris, Sér. I Math., Volume 305 (1987), pp. 501-504 | MR | Zbl

[39] M. Senechal Quasicrystals and geometry, Cambridge University Press, 1995 | MR | Zbl

[40] F. Schweiger The metrical theory of Jacobi-Perron algorithm, Lecture Notes in Math., 334, Springer-Verlag, 1973 | MR | Zbl

[41] J.-L. Verger-Gaugry; J.-P. Gazeau Geometric study of the set ${\mathbb{Z}}_{\beta }$ of beta-integers with $\beta$ a Perron number, a $\beta$-number and a Pisot number and mathematical quasicrystals (2000) (Prépublication de l'Institut Fourier, 513)

[42] L. Vuillon Combinatoire des motifs d'une suite sturmienne bidimensionnelle, Th. Comput. Sci., Volume 209 (1998), pp. 261-285 | DOI | MR | Zbl