Article Contents
Article Contents

# Rauzy induction of polygon partitions and toral $\mathbb{Z}^2$-rotations

The author acknowledges financial support from the Laboratoire International FrancoQuébécois de Recherche en Combinatoire (LIRCO), the Agence Nationale de la Recherche through the project CODYS (ANR-18-CE40-0007) and the Horizon 2020 European Research Infrastructure project OpenDreamKit (676541)

• We extend the notion of Rauzy induction of interval exchange transformations to the case of toral $\mathbb{Z}^2$-rotation, i.e., $\mathbb{Z}^2$-action defined by rotations on a 2-torus. If $\mathscr{X}_{\mathscr{P}, R}$ denotes the symbolic dynamical system corresponding to a partition $\mathscr{P}$ and $\mathbb{Z}^2$-action $R$ such that $R$ is Cartesian on a sub-domain $W$, we express the 2-dimensional configurations in $\mathscr{X}_{\mathscr{P}, R}$ as the image under a $2$-dimensional morphism (up to a shift) of a configuration in $\mathscr{X}_{\widehat{\mathscr{P}}|_W, \widehat{R}|_W}$ where $\widehat{\mathscr{P}}|_W$ is the induced partition and $\widehat{R}|_W$ is the induced $\mathbb{Z}^2$-action on $W$.

We focus on one example, $\mathscr{X}_{\mathscr{P}_0, R_0}$, for which we obtain an eventually periodic sequence of 2-dimensional morphisms. We prove that it is the same as the substitutive structure of the minimal subshift $X_0$ of the Jeandel–Rao Wang shift computed in an earlier work by the author. As a consequence, ${\mathscr{P}}_0$ is a Markov partition for the associated toral $\mathbb{Z}^2$-rotation $R_0$. It also implies that the subshift $X_0$ is uniquely ergodic and is isomorphic to the toral $\mathbb{Z}^2$-rotation $R_0$ which can be seen as a generalization for 2-dimensional subshifts of the relation between Sturmian sequences and irrational rotations on a circle. Batteries included: the algorithms and code to reproduce the proofs are provided.

Mathematics Subject Classification: 37A05.

 Citation:

• Figure 1.  The shifted lattice $p+ \mathbb{Z}$ is coded as a bi-infinite binary sequence $w\in\{L, R\}^ \mathbb{Z}$ which is a symbolic representation of $p$

Figure 2.  The automorphism of $\mathbb{R}^2/ \mathbb{Z}^2$ defined as $v\mapsto Mv$ admits a Markov partition

Figure 3.  For every starting point $p\in \mathbb{R}^2$, the coding of the shifted lattice $p+ \mathbb{Z}^2$ under the polygon partition ${\mathscr{P}}_0$ yields a configuration which is a symbolic representation of $p$. We show that the set of such configurations is a shift of finite type (SFT) and hence that ${\mathscr{P}}_0$ is a Markov partition for the toral $\mathbb{Z}^2$-rotation $R_0$

Figure 4.  We prove that the subshifts $X_0\subset\Omega_0$ and ${\mathscr{X}}_{ {\mathscr{P}}_0, R_0}$ are equal since they have a common substitutive structure. The substitutive structure of $X_0$ computed in [36] and the substitutive structure of ${\mathscr{X}}_{ {\mathscr{P}}_0, R_0}$ satisfy $\beta_0 = \omega_0\omega_1\omega_2\omega_3$, $\beta_1\beta_2 = \jmath\, \eta\, \omega_6$, $\beta_3 \beta_4 \beta_5 \beta_6 \beta_7 = \omega_7 \omega_8 \omega_9 \omega_{10} \omega_{11}$, $\zeta = \rho$ and $\beta_8\, \beta_9\, \tau = \rho\, \omega_ {\mathscr{U}}\, \rho^{-1}$. We deduce that ${\mathscr{X}}_{ {\mathscr{P}}_8, R_8} = \Omega_{12}$, ${\mathscr{X}}_{ {\mathscr{P}}_3, R_3} = \Omega_{7}$, ${\mathscr{X}}_{ {\mathscr{P}}_1, R_1} = X_{4}$ and finally ${\mathscr{X}}_{ {\mathscr{P}}_0, R_0} = X_{0}$

Figure 5.  The polygon exchange transformation $T$ of the rectangle $[0, \ell_1)\times[0, \ell_2)$ as defined on the figure can be seen as a toral translation by the vector $(\alpha_1, \alpha_2)$ on the torus $\mathbb{R}^2/(\ell_1 \mathbb{Z}\times\ell_2 \mathbb{Z})$

Figure 6.  The partition ${\mathscr{P}}_0$ of $\mathbb{R}^2/\Gamma_0$ into atoms associated to letters in ${\mathscr{A}}_0$ illustrated on a rectangular fundamental domain

Figure 7.  The set $\{A, B, C, D\}$ forms a partition of the rectangle $W = (0, \varphi)\times(0, 1)$. The return time to $W$ under the map $R_0^{ {\boldsymbol{e}}_2}$ is 4 or 5. The orbit of $A$, $B$, $C$ and $D$ under $R_0^{ {\boldsymbol{e}}_2}$ before it returns to $W$ yields a partitions of $\mathbb{R}^2/\Gamma_0$. The first return map $\widehat{R_0^{ {\boldsymbol{e}}_2}}|_W$ is equivalent to a toral translation by the vector $(\frac{1}{\varphi}, \frac{1}{\varphi^2})$ on $\mathbb{R}^2/\Gamma_1$

Figure 8.  The return time to $W$ under map $R_0^{ {\boldsymbol{e}}_1}$ is always 1. The first return map $\widehat{R_0^{ {\boldsymbol{e}}_1}}|_W$ is equivalent to a toral translation by the vector $(1, 0)$ on $\mathbb{R}^2/\Gamma_1$

Figure 9.  The partition ${\mathscr{P}}_1: = \widehat{ {\mathscr{P}}_0}|_W$ of $\mathbb{R}^2/\Gamma_1$ into 30 convex atoms each associated to one of the 28 letters in ${\mathscr{A}}_1$ (indices 19 and 22 are both used twice)

Figure 10.  The partition ${\mathscr{P}}_2$ of $\mathbb{R}^2/\Gamma_2$ into atoms associated to letters in ${\mathscr{A}}_2$

Figure 11.  The substitutive structure of ${\mathscr{X}}_{ {\mathscr{P}}_2, R_2}$

Figure 12.  The topological partition ${\mathscr{P}}_ {\mathscr{U}}$ of $\mathbb{T}^2$ using alphabet $\left[\!\left[ {0, {18}} \right]\!\right]$ for the atoms

•  [1] R. L. Adler, Symbolic dynamics and Markov partitions, Bull. Amer. Math. Soc. (N.S.), 35 (1998), 1-56.  doi: 10.1090/S0273-0979-98-00737-X. [2] R. L. Adler and B. Weiss, Similarity of Automorphisms of the Torus, Memoirs of the American Mathematical Society, 98, American Mathematical Society, Providence, R.I., 1970. [3] S. Akiyama, M. Barge, V. Berthé, J.-Y. Lee and A. Siegel, On the Pisot substitution conjecture, in Mathematics of Aperiodic Order, Progr. Math., 309, Birkhäuser/Springer, Basel, 2015, 33–72. doi: 10.1007/978-3-0348-0903-0_2. [4] I. Alevy, R. Kenyon and R. Yi, A family of minimal and renormalizable rectangle exchange maps, Ergodic Theory Dynam. Systems, 41 (2021), 790-817.  doi: 10.1017/etds.2019.77. [5] P. Arnoux, Sturmian sequences, in Substitutions in Dynamics, Arithmetics and Combinatorics, Lecture Notes in Math., 1794, Springer, Berlin, 2002,143–198. doi: 10.1007/3-540-45714-3_6. [6] P. Arnoux, V. Berthé and S. Ito, Discrete planes, $\Bbb Z^2$-actions, Jacobi-Perron algorithm and substitutions, Ann. Inst. Fourier (Grenoble), 52 (2002), 305-349.  doi: 10.5802/aif.1889. [7] P. Arnoux, V. Berthé, H. Ei and S. Ito, Tilings, quasicrystals, discrete planes, generalized substitutions, and multidimensional continued fractions, in Discrete Models: Combinatorics, Computation, and Geometry (Paris, 2001), Discrete Math. Theor. Comput. Sci. Proc., AA, Maison Inform. Math. Discrèt. (MIMD), Paris, 2001, 59–78. [8] A. Avila and G. Forni, Weak mixing for interval exchange transformations and translation flows, Ann. of Math. (2), 165 (2007), 637-664.  doi: 10.4007/annals.2007.165.637. [9] M. Baake, J. A. G. Roberts and R. Yassawi, Reversing and extended symmetries of shift spaces, Discrete Contin. Dyn. Syst., 38 (2018), 835-866.  doi: 10.3934/dcds.2018036. [10] R. Berger, The undecidability of the domino problem, Mem. Amer. Math. Soc., 66 (1966), 72 pp. [11] V. Berthé, Arithmetic discrete planes are quasicrystals, in Discrete Geometry for Computer Imagery, Lecture Notes in Comput. Sci., 5810, Springer, Berlin, 2009, 1–12. doi: 10.1007/978-3-642-04397-0_1. [12] V. Berthé, J. Bourdon, T. Jolivet and A. Siegel, Generating discrete planes with substitutions, in Combinatorics on Words, Lecture Notes in Comput. Sci., 8079, Springer, Heidelberg, 2013, 58–70. doi: 10.1007/978-3-642-40579-2_9. [13] V. Berthé and V. Delecroix, Beyond substitutive dynamical systems: $S$-adic expansions, in Numeration and Substitution 2012, RIMS Kôkyûroku Bessatsu, B46, Res. Inst. Math. Sci. (RIMS), Kyoto, 2014, 81–123. [14] V. Berthé, S. Ferenczi, and L. Q. Zamboni, Interactions between dynamics, arithmetics and combinatorics: The good, the bad, and the ugly, in Algebraic and Topological Dynamics, Contemp. Math., 385, Amer. Math. Soc., Providence, RI, 2005,333–364. doi: 10.1090/conm/385. [15] V. Berthé and M. Rigo, editors, Combinatorics, automata and number theory, Encyclopedia of Mathematics and its Applications, 135, Cambridge University Press, Cambridge, 2010. doi: 10.1017/CBO9780511777653. [16] V. Berthé, W. Steiner and J. M. Thuswaldner, Geometry, dynamics, and arithmetic of $S$-adic shifts, Ann. Inst. Fourier (Grenoble), 69 (2019), 1347-1409.  doi: 10.5802/aif.3273. [17] R. Bowen, Markov partitions for Axiom A diffeomorphisms, Amer. J. Math., 92 (1970), 725-747.  doi: 10.2307/2373370. [18] R. Bowen, Equilibrium states and the ergodic theory of Anosov diffeomorphisms, Lecture Notes in Mathematics, 470, Springer-Verlag, Berlin-New York, 1975. [19] R. Bowen, Markov partitions are not smooth, Proc. Amer. Math. Soc., 71 (1978), 130-132.  doi: 10.2307/2042234. [20] M. Boyle and J. Tomiyama, Bounded topological orbit equivalence and $C^*$-algebras, J. Math. Soc. Japan, 50 (1998), 317-329.  doi: 10.2969/jmsj/05020317. [21] V. Brun, Algorithmes euclidiens pour trois et quatre nombres, in Treizième Congrès des Mathématiciens Scandinaves, tenu à Helsinki 18-23 aoşt 1957, Mercators Tryckeri, Helsinki, 1958, 45–64. [22] E. Cawley, Smooth Markov partitions and toral automorphisms, Ergodic Theory Dynam. Systems, 11 (1991), 633-651.  doi: 10.1017/S0143385700006404. [23] E. Charlier, T. Kärki and M. Rigo, Multidimensional generalized automatic sequences and shape-symmetric morphic words, Discrete Math., 310 (2010), 1238-1252.  doi: 10.1016/j.disc.2009.12.002. [24] E. M. Coven and G. A. Hedlund, Sequences with minimal block growth, Math. Systems Theory, 7 (1973), 138-153.  doi: 10.1007/BF01762232. [25] M. Einsiedler and K. Schmidt, Markov partitions and homoclinic points of algebraic $\mathbf{Z}^d$-actions, Tr. Mat. Inst. Steklova, 216 (1997), 265-284. [26] N. P. Fogg, Substitutions in dynamics, arithmetics and combinatorics, Lecture Notes in Mathematics, 1794, Springer-Verlag, Berlin, 2002., Edited by V. Berthé, S. Ferenczi, C. Mauduit and A. Siegel. doi: 10.1007/b13861. [27] M. Hochman, Multidimensional shifts of finite type and sofic shifts, in Combinatorics, Words and Symbolic Dynamics, Encyclopedia Math. Appl., 159, Cambridge Univ. Press, Cambridge, 2016,296–358. doi: 10.1017/CBO9781139924733.010. [28] M. Hochman and T. Meyerovitch, A characterization of the entropies of multidimensional shifts of finite type, Ann. of Math. (2), 171 (2010), 2011-2038.  doi: 10.4007/annals.2010.171.2011. [29] W. P. Hooper, Renormalization of polygon exchange maps arising from corner percolation, Invent. Math., 191 (2013), 255-320.  doi: 10.1007/s00222-012-0393-4. [30] E. Jeandel and M. Rao, An aperiodic set of 11 Wang tiles, Adv. Comb., (2021), 37 pp. doi: 10.19086/aic.18614. [31] R. Kenyon and A. Vershik, Arithmetic construction of sofic partitions of hyperbolic toral automorphisms, Ergodic Theory Dynam. Systems, 18 (1998), 357-372.  doi: 10.1017/S0143385798100445. [32] B. Kitchens, Symbolic dynamics, group automorphisms and Markov partitions, in Real and Complex Dynamical Systems (Hillerød, 1993), NATO Adv. Sci. Inst. Ser. C: Math. Phys. Sci., 464, Kluwer Acad. Publ., Dordrecht, 1995,133–163. [33] B. P. Kitchens, Symbolic Dynamics. One-sided, two-sided and countable state Markov shifts, Universitext, Springer-Verlag, Berlin, 1998. doi: 10.1007/978-3-642-58822-8. [34] S. Labbé, A self-similar aperiodic set of 19 Wang tiles, Geom. Dedicata, 201 (2019), 81-109.  doi: 10.1007/s10711-018-0384-8. [35] S. Labbé, Markov partitions for toral $\mathbb{Z}^2$-rotations featuring Jeandel–Rao Wang shift and model sets, Annales Henri Lebesgue, 4 (2021), 283-324.  doi: 10.5802/ahl.73. [36] S. Labbé, Substitutive structure of Jeandel-Rao aperiodic tilings, Discrete Comput. Geom., 65 (2021), 800-855.  doi: 10.1007/s00454-019-00153-3. [37] S. Labbé, Optional SageMath Package $\texttt{slabbe}$ (Version 0.6.2), https://pypi.python.org/pypi/slabbe/, 2020. [38] D. Lind, Multi-dimensional symbolic dynamics, in Symbolic Dynamics and its Applications, Proc. Sympos. Appl. Math., 60, Amer. Math. Soc., Providence, RI, 2004, 61–79. doi: 10.1090/psapm/060/2078846. [39] D. Lind and  B. Marcus,  An Introduction to Symbolic Dynamics and Coding, Cambridge University Press, Cambridge, 1995.  doi: 10.1017/CBO9780511626302. [40] M. Lothaire, Combinatorics on Words, Encyclopedia of Mathematics and its Applications, Cambridge University Press, Cambridge, 1997. [41] M. Morse and G. A. Hedlund, Symbolic dynamics II. Sturmian trajectories, Amer. J. Math., 62 (1940), 1-42.  doi: 10.2307/2371431. [42] M. Queffélec, Substitution dynamical systems—spectral analysis, 2$^{nd}$ edition, Lecture Notes in Mathematics, 1294, Springer-Verlag, Berlin, 2010. doi: 10.1007/978-3-642-11212-6. [43] G. Rauzy, Une généralisation du développement en fraction continue, in Séminaire Delange-Pisot-Poitou, 18e année: 1976/77, Théorie des Nombres, Fasc. 1, Secrétariat Math., Paris, 1977, 16 pp. [44] G. Rauzy, Échanges d'intervalles et transformations induites, Acta Arith., 34 (1979), 315-328.  doi: 10.4064/aa-34-4-315-328. [45] G. Rauzy, Nombres algébriques et substitutions, Bull. Soc. Math. France, 110 (1982), 147-178.  doi: 10.24033/bsmf.1957. [46] Sage Developers, SageMath, the Sage Mathematics Software System (Version 9.2), http://www.sagemath.org, 2020. [47] K. Schmidt, Multi–dimensional symbolic dynamical systems, in Codes, Systems, and Graphical Models (Minneapolis, MN, 1999), IMA Vol. Math. Appl., 123, Springer, New York, 2001, 67–82. doi: 10.1007/978-1-4613-0165-3_3. [48] R. E. Schwartz, Outer billiards, quarter turn compositions, and polytope exchange transformations, (2011). Available from: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.716.1778&rep=rep1&type=pdf. [49] R. E. Schwartz, The Octogonal PETs, Mathematical Surveys and Monographs, 197, American Mathematical Society, Providence, RI, 2014. doi: 10.1090/surv/197. [50] J. G. Sinaĭ, Markov partitions and Y-diffeomorphisms, Funkcional. Anal. i Priložen, 2 (1968), 64-89. [51] J. M. Thuswaldner, $S$-adic sequences: A bridge between dynamics, arithmetic, and geometry, in Substitution and Tiling Dynamics: Introduction to Self-Inducing Structures, Lecture notes in Math., 2273, Springer, Cham, 2020, 97–191. doi: 10.1007/978-3-030-57666-0_3. [52] W. A. Veech, Gauss measures for transformations on the space of interval exchange maps, Ann. of Math. (2), 115 (1982), 201-242.  doi: 10.2307/1971391. [53] P. Walters, An Introduction to Ergodic Theory, Graduate Texts in Mathematics, 79, Springer-Verlag, New York-Berlin, 1982. [54] J.-C. Yoccoz, Continued fraction algorithms for interval exchange maps: An introduction, in Frontiers in Number Theory, Physics, and Geometry. I, Springer, Berlin, 2006,401–435.

Figures(12)