Advanced Search
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)

Abstract Full Text(HTML) Figure(12) Related Papers Cited by
  • 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.


    \begin{equation} \\ \end{equation}
  • 加载中
  • 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. AlevyR. 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. ArnouxV. 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. BaakeJ. 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. CharlierT. 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. MarcusAn 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=
    [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.
  • 加载中



Article Metrics

HTML views(159) PDF downloads(82) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint