• Previous Article
    Continuous orbit equivalence of topological Markov shifts and KMS states on Cuntz–Krieger algebras
  • DCDS Home
  • This Issue
  • Next Article
    Analysis of a spatial memory model with nonlocal maturation delay and hostile boundary condition
October  2020, 40(10): 5869-5895. doi: 10.3934/dcds.2020250

Extended symmetry groups of multidimensional subshifts with hierarchical structure

Departamento de Ingeniería Matemática, Facultad de Ciencias Físicas y Matemáticas, Universidad de Chile, Beauchef 851 (Of. 415), 8370456 Santiago, Región Metropolitana, Chile

Received  October 2019 Revised  April 2020 Published  June 2020

Fund Project: The author is supported by ANID-PFCHA/Doctorado Nacional/2017-21171061 (formerly CONICYT). Please check the Acknowledgments section below for further details

The centralizer (automorphism group) and normalizer (extended symmetry group) of the shift action inside the group of self-homeomorphisms are studied, in the context of certain $ \mathbb{Z}^d $ subshifts with a hierarchical supertile structure, such as bijective substitutive subshifts and the Robinson tiling. Restrictions on these groups via geometrical considerations are used to characterize explicitly their structure: nontrivial extended symmetries can always be described via relabeling maps and rigid transformations of the Euclidean plane permuting the coordinate axes. The techniques used also carry over to the well-known Robinson tiling, both in its minimal and non-minimal versions.

Citation: Álvaro Bustos. Extended symmetry groups of multidimensional subshifts with hierarchical structure. Discrete & Continuous Dynamical Systems - A, 2020, 40 (10) : 5869-5895. doi: 10.3934/dcds.2020250
References:
[1]

M. Baake, Structure and representations of the hyperoctahedral group, J. Math. Phys., 25 (1984), 3171-3182.  doi: 10.1063/1.526087.  Google Scholar

[2]

M. Baake and U. Grimm, Aperiodic Order, vol. 1. A Mathematical Invitation, With a foreword by Roger Penrose. Encyclopedia of Mathematics and its Applications, 149. Cambridge University Press, Cambridge, 2013. doi: 10.1017/CBO9781139025256.  Google Scholar

[3]

M. Baake and U. Grimm, Squirals and beyond: Substitution tilings with singular continuous spectrum, Ergodic Theory Dynam. Systems, 34 (2014), 1077–1102, arXiv: 1205.1384. doi: 10.1017/etds.2012.191.  Google Scholar

[4]

M. Baake, J. A. G. Roberts and R. Yassawi, Reversing and extended symmetries of shift spaces, Discrete Cont. Dyn. Syst., 38 (2018), 835–866, arXiv: 1611.05756. doi: 10.3934/dcds.2018036.  Google Scholar

[5]

M. M. Boyle, Topological Orbit Equivalence and Factor Maps in Symbolic Dynamics, PhD thesis, University of Washington, 1983.  Google Scholar

[6]

M. BoyleD. Lind and D. Rudolph, The automorphism group of a shift of finite type, Trans. Amer. Math. Soc., 306 (1988), 71-114.  doi: 10.1090/S0002-9947-1988-0927684-2.  Google Scholar

[7]

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.  Google Scholar

[8]

T. Ceccherini-Silberstein and M. Coornaert, Cellular automata and groups, Computational Complexity, Springer, New York, 1 (2012), 336–349. doi: 10.1007/978-1-4614-1800-9_23.  Google Scholar

[9]

E. M. Coven, Endomorphisms of substitution minimal sets, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete, 20 (1971), 129-133.  doi: 10.1007/BF00536290.  Google Scholar

[10]

E. M. Coven, A. Quas and R. Yassawi, Computing automorphism groups of shifts using atypical equivalence classes, Discrete Anal., 2016 (2016), 28 pp, arXiv: 1505.02482. doi: 10.19086/da.611.  Google Scholar

[11]

V. Cyr and B. Kra, The automorphism group of a shift of linear growth: Beyond transitivity, Forum Math. Sigma, 3 (2015), e5, 27 pp, arXiv: 1411.0180. doi: 10.1017/fms.2015.3.  Google Scholar

[12]

S. Donoso, F. Durand, A. Maass and S. Petite, On automorphism groups of low complexity subshifts, Ergodic Theory Dynam. Systems, 36 (2016), 64–95. arXiv: 1501.00510. doi: 10.1017/etds.2015.70.  Google Scholar

[13]

S. Donoso and W. Sun, Dynamical cubes and a criteria for systems having product extensions, J. Mod. Dyn., 9 (2015), 365–405. arXiv: 1406.1220. doi: 10.3934/jmd.2015.9.365.  Google Scholar

[14]

N. P. Frank, Multidimensional constant-length substitution sequences, Topology Appl., 152 (2005), 44-69.  doi: 10.1016/j.topol.2004.08.014.  Google Scholar

[15]

F. Gähler, Substitution rules and topological properties of the Robinson tilings, in Aperiodic Crystals (eds. S. Schmid, R. L. Withers and R. Lifshitz), Springer, Dordrecht, (2013), 67–73. arXiv: 1210.6468. Google Scholar

[16]

F. Gähler, A. Julien and J. Savinien, Combinatorics and topology of the Robinson tiling, C. R. Math. Acad. Sci. Paris, 350 (2012), 627–631. arXiv: 1203.1387 doi: 10.1016/j.crma.2012.06.007.  Google Scholar

[17]

G. R. Goodson, Inverse conjugacies and reversing symmetry groups, Amer. Math. Monthly, 106 (1999), 19-26.  doi: 10.1080/00029890.1999.12005002.  Google Scholar

[18]

G. James and A. Kerber, The Representation Theory of the Symmetric Group, Encyclopedia of Mathematics and its Applications, 16. Addison-Wesley Publishing Co., Reading, Mass., 1981.  Google Scholar

[19]

J. Kellendonk and R. Yassawi, The Ellis semigroup of bijective substitutions, preprint, arXiv: 1908.05690. Google Scholar

[20]

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.  Google Scholar

[21]

B. Kitchens and K. Schmidt, Isomorphism rigidity of irreducible algebraic Zd-actions, Invent. Math., 142 (2000), 559-577.  doi: 10.1007/PL00005793.  Google Scholar

[22]

P. Kůrka, Topological and Symbolic Dynamics, Société mathématique de France, Paris, 2003.  Google Scholar

[23]

M. Lemańczyk and M. K. Mentzen, On metric properties of substitutions, Compositio Math, 65 (1988), 241-263.   Google Scholar

[24] D. Lind and B. Marcus, An Introduction to Symbolic Dynamics and Coding, Cambridge University Press, Cambridge, 1995.  doi: 10.1017/CBO9780511626302.  Google Scholar
[25]

G. R. Maloney and D. Rust, Beyond primitivity for one-dimensional substitution subshifts and tiling spaces, Ergodic Theory Dynam. Systems, 38 (2018), 1086–1117, arXiv: 1604.01246 doi: 10.1017/etds.2016.58.  Google Scholar

[26]

G. A. Miller, Groups formed by special matrices, Bull. Am. Math. Soc., 24 (1918), 203-206.  doi: 10.1090/S0002-9904-1918-03043-7.  Google Scholar

[27]

B. Mossé, Reconnaissabilité des substitutions et complexité des suites automatiques, Bull. Soc. Math. France, 124 (1996), 329-346.  doi: 10.24033/bsmf.2283.  Google Scholar

[28] A. G. O'Farrell and I. Short, Reversibility in Dynamics and Group Theory, Cambridge University Press, Cambridge, 2015.  doi: 10.1017/CBO9781139998321.  Google Scholar
[29]

J. Olli, Endomorphisms of Sturmian systems and the discrete chair substitution tiling system, Discrete Cont. Dyn. Syst., 33 (2013), 4173-4186.  doi: 10.3934/dcds.2013.33.4173.  Google Scholar

[30]

N. P. Fogg (ed.), Substitutions in Dynamics, Arithmetics and Combinatorics, Lecture Notes in Mathematics, 1794. Springer-Verlag, Berlin, 2002. doi: 10.1007/b13861.  Google Scholar

[31]

A. M. Robert, A Course in p-adic Analysis, Graduate Texts in Mathematics, 198. Springer-Verlag, New York, 2000. doi: 10.1007/978-1-4757-3254-2.  Google Scholar

[32]

R. M. Robinson, Undecidability and nonperiodicity for tilings of the plane, Invent. Math., 12 (1971), 177-209.  doi: 10.1007/BF01418780.  Google Scholar

[33]

K. Schmidt, Dynamical Systems of Algebraic Origin, Modern Birkhäuser Classics. Birkhäuser/Springer Basel AG, Basel, 1995.  Google Scholar

[34]

B. Solomyak, Nonperiodicity implies unique composition for self-similar translationally finite tilings, Discrete Comput. Geom., 20 (1998), 265-279.  doi: 10.1007/PL00009386.  Google Scholar

show all references

References:
[1]

M. Baake, Structure and representations of the hyperoctahedral group, J. Math. Phys., 25 (1984), 3171-3182.  doi: 10.1063/1.526087.  Google Scholar

[2]

M. Baake and U. Grimm, Aperiodic Order, vol. 1. A Mathematical Invitation, With a foreword by Roger Penrose. Encyclopedia of Mathematics and its Applications, 149. Cambridge University Press, Cambridge, 2013. doi: 10.1017/CBO9781139025256.  Google Scholar

[3]

M. Baake and U. Grimm, Squirals and beyond: Substitution tilings with singular continuous spectrum, Ergodic Theory Dynam. Systems, 34 (2014), 1077–1102, arXiv: 1205.1384. doi: 10.1017/etds.2012.191.  Google Scholar

[4]

M. Baake, J. A. G. Roberts and R. Yassawi, Reversing and extended symmetries of shift spaces, Discrete Cont. Dyn. Syst., 38 (2018), 835–866, arXiv: 1611.05756. doi: 10.3934/dcds.2018036.  Google Scholar

[5]

M. M. Boyle, Topological Orbit Equivalence and Factor Maps in Symbolic Dynamics, PhD thesis, University of Washington, 1983.  Google Scholar

[6]

M. BoyleD. Lind and D. Rudolph, The automorphism group of a shift of finite type, Trans. Amer. Math. Soc., 306 (1988), 71-114.  doi: 10.1090/S0002-9947-1988-0927684-2.  Google Scholar

[7]

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.  Google Scholar

[8]

T. Ceccherini-Silberstein and M. Coornaert, Cellular automata and groups, Computational Complexity, Springer, New York, 1 (2012), 336–349. doi: 10.1007/978-1-4614-1800-9_23.  Google Scholar

[9]

E. M. Coven, Endomorphisms of substitution minimal sets, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete, 20 (1971), 129-133.  doi: 10.1007/BF00536290.  Google Scholar

[10]

E. M. Coven, A. Quas and R. Yassawi, Computing automorphism groups of shifts using atypical equivalence classes, Discrete Anal., 2016 (2016), 28 pp, arXiv: 1505.02482. doi: 10.19086/da.611.  Google Scholar

[11]

V. Cyr and B. Kra, The automorphism group of a shift of linear growth: Beyond transitivity, Forum Math. Sigma, 3 (2015), e5, 27 pp, arXiv: 1411.0180. doi: 10.1017/fms.2015.3.  Google Scholar

[12]

S. Donoso, F. Durand, A. Maass and S. Petite, On automorphism groups of low complexity subshifts, Ergodic Theory Dynam. Systems, 36 (2016), 64–95. arXiv: 1501.00510. doi: 10.1017/etds.2015.70.  Google Scholar

[13]

S. Donoso and W. Sun, Dynamical cubes and a criteria for systems having product extensions, J. Mod. Dyn., 9 (2015), 365–405. arXiv: 1406.1220. doi: 10.3934/jmd.2015.9.365.  Google Scholar

[14]

N. P. Frank, Multidimensional constant-length substitution sequences, Topology Appl., 152 (2005), 44-69.  doi: 10.1016/j.topol.2004.08.014.  Google Scholar

[15]

F. Gähler, Substitution rules and topological properties of the Robinson tilings, in Aperiodic Crystals (eds. S. Schmid, R. L. Withers and R. Lifshitz), Springer, Dordrecht, (2013), 67–73. arXiv: 1210.6468. Google Scholar

[16]

F. Gähler, A. Julien and J. Savinien, Combinatorics and topology of the Robinson tiling, C. R. Math. Acad. Sci. Paris, 350 (2012), 627–631. arXiv: 1203.1387 doi: 10.1016/j.crma.2012.06.007.  Google Scholar

[17]

G. R. Goodson, Inverse conjugacies and reversing symmetry groups, Amer. Math. Monthly, 106 (1999), 19-26.  doi: 10.1080/00029890.1999.12005002.  Google Scholar

[18]

G. James and A. Kerber, The Representation Theory of the Symmetric Group, Encyclopedia of Mathematics and its Applications, 16. Addison-Wesley Publishing Co., Reading, Mass., 1981.  Google Scholar

[19]

J. Kellendonk and R. Yassawi, The Ellis semigroup of bijective substitutions, preprint, arXiv: 1908.05690. Google Scholar

[20]

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.  Google Scholar

[21]

B. Kitchens and K. Schmidt, Isomorphism rigidity of irreducible algebraic Zd-actions, Invent. Math., 142 (2000), 559-577.  doi: 10.1007/PL00005793.  Google Scholar

[22]

P. Kůrka, Topological and Symbolic Dynamics, Société mathématique de France, Paris, 2003.  Google Scholar

[23]

M. Lemańczyk and M. K. Mentzen, On metric properties of substitutions, Compositio Math, 65 (1988), 241-263.   Google Scholar

[24] D. Lind and B. Marcus, An Introduction to Symbolic Dynamics and Coding, Cambridge University Press, Cambridge, 1995.  doi: 10.1017/CBO9780511626302.  Google Scholar
[25]

G. R. Maloney and D. Rust, Beyond primitivity for one-dimensional substitution subshifts and tiling spaces, Ergodic Theory Dynam. Systems, 38 (2018), 1086–1117, arXiv: 1604.01246 doi: 10.1017/etds.2016.58.  Google Scholar

[26]

G. A. Miller, Groups formed by special matrices, Bull. Am. Math. Soc., 24 (1918), 203-206.  doi: 10.1090/S0002-9904-1918-03043-7.  Google Scholar

[27]

B. Mossé, Reconnaissabilité des substitutions et complexité des suites automatiques, Bull. Soc. Math. France, 124 (1996), 329-346.  doi: 10.24033/bsmf.2283.  Google Scholar

[28] A. G. O'Farrell and I. Short, Reversibility in Dynamics and Group Theory, Cambridge University Press, Cambridge, 2015.  doi: 10.1017/CBO9781139998321.  Google Scholar
[29]

J. Olli, Endomorphisms of Sturmian systems and the discrete chair substitution tiling system, Discrete Cont. Dyn. Syst., 33 (2013), 4173-4186.  doi: 10.3934/dcds.2013.33.4173.  Google Scholar

[30]

N. P. Fogg (ed.), Substitutions in Dynamics, Arithmetics and Combinatorics, Lecture Notes in Mathematics, 1794. Springer-Verlag, Berlin, 2002. doi: 10.1007/b13861.  Google Scholar

[31]

A. M. Robert, A Course in p-adic Analysis, Graduate Texts in Mathematics, 198. Springer-Verlag, New York, 2000. doi: 10.1007/978-1-4757-3254-2.  Google Scholar

[32]

R. M. Robinson, Undecidability and nonperiodicity for tilings of the plane, Invent. Math., 12 (1971), 177-209.  doi: 10.1007/BF01418780.  Google Scholar

[33]

K. Schmidt, Dynamical Systems of Algebraic Origin, Modern Birkhäuser Classics. Birkhäuser/Springer Basel AG, Basel, 1995.  Google Scholar

[34]

B. Solomyak, Nonperiodicity implies unique composition for self-similar translationally finite tilings, Discrete Comput. Geom., 20 (1998), 265-279.  doi: 10.1007/PL00009386.  Google Scholar

Figure 1.  An example of applying a rectangular substitution to a pattern
Figure 4.  Points from the two-dimensional Thue-Morse substitution. The first two configurations correspond to (the central pattern of) two points $ x, y\in\mathsf{X}_{\theta_{\text TM}} $ matching exactly in one half-plane, as in Lemma 4.4. The third configuration is an "illegal" point $ z\in\mathsf{X}_{\theta_{\text TM}}^*\setminus\mathsf{X}_{\theta_{\text TM}} $ from the extended substitutive subshift. The associated seeds and substitution rule are shown below
Figure 2.  $ 2^n\times 2^n $ grids associated with the iterates of a primitive substitution $ \theta $ in a point from a substitutive subshift. The corresponding substitution is indicated on the right
Figure 3.  In the figure, we see how $ x|_{K_{\boldsymbol{p}}} = \theta^m(a) $ (for some $ a\in\mathcal{A} $) determines $ f(x)|_{K_{\boldsymbol{p}}^{\circ r}} $ and, in particular, $ f(x)|_{I_{\boldsymbol{p}}} $. Since the substitution is bijective, this forces $ f(x)|_{L_{\boldsymbol{p}}} $ to equal $ \theta^m(b) $ for some $ b\in\mathcal{A} $ which depends solely on $ a $
Figure 5.  The situation in the proof of Lemma 4.6. As the side length of the rectangles associated with the substitution increases exponentially, the inner product $ \langle\boldsymbol{v}, \boldsymbol{w}\rangle $ which determines whether $ \boldsymbol{w} $ belongs to $ S $ or $ S' $ (or neither) takes sufficiently many different (integer) values inside any of these rectangles to ensure that at least one such rectangle intersects both $ S $ and $ S' $
Figure 6.  The five types of Robinson tiles, resulting in an alphabet of $ 28 $ symbols after applying all possible rotations and reflections. The third tile is usually called a cross
Figure 7.  The formation of a second order supertile of size $ 3\times 3 $
Figure 8.  A fragment of a point from the Robinson shift, distinguishing the four supertiles involved, the vertical and horizontal strips of tiles separating each supertile and the $ 2\mathbb{Z}\times 2\mathbb{Z} $ sublattice that contains only crosses. Note that the tiles in the vertical strip separating the supertiles are copies of the first tile of Figure 6 with the same orientation
Figure 9.  Two possible ways in which the tiling from Figure 8 exhibits fracture-like behavior, resulting in valid points from $ X_{\text Rob} $
Figure 10.  The substructure of a point of $ X_{\text Rob} $ in terms of $ n $-th order supertiles. Note how all supertiles overlap either $ S^+ $ or $ S^- $
Figure 11.  How a shift by $ k_1\boldsymbol{q} $ makes the arrangement of supertiles in $ S^+ $ not match with the corresponding tiles in $ S^- $
Figure 12.  The relabeling map $ \mathfrak{R} $ which replaces each tile with its corresponding rotation by $ \frac{1}{2}\pi $
[1]

Steven T. Piantadosi. Symbolic dynamics on free groups. Discrete & Continuous Dynamical Systems - A, 2008, 20 (3) : 725-738. doi: 10.3934/dcds.2008.20.725

[2]

Younghwan Son. Substitutions, tiling dynamical systems and minimal self-joinings. Discrete & Continuous Dynamical Systems - A, 2014, 34 (11) : 4855-4874. doi: 10.3934/dcds.2014.34.4855

[3]

S. Eigen, V. S. Prasad. Tiling Abelian groups with a single tile. Discrete & Continuous Dynamical Systems - A, 2006, 16 (2) : 361-365. doi: 10.3934/dcds.2006.16.361

[4]

François Gay-Balmaz, Cesare Tronci, Cornelia Vizman. Geometric dynamics on the automorphism group of principal bundles: Geodesic flows, dual pairs and chromomorphism groups. Journal of Geometric Mechanics, 2013, 5 (1) : 39-84. doi: 10.3934/jgm.2013.5.39

[5]

Michael Baake, John A. G. Roberts, Reem Yassawi. Reversing and extended symmetries of shift spaces. Discrete & Continuous Dynamical Systems - A, 2018, 38 (2) : 835-866. doi: 10.3934/dcds.2018036

[6]

Benjamin Hellouin de Menibus, Hugo Maturana Cornejo. Necessary conditions for tiling finitely generated amenable groups. Discrete & Continuous Dynamical Systems - A, 2020, 40 (4) : 2335-2346. doi: 10.3934/dcds.2020116

[7]

Jim Wiseman. Symbolic dynamics from signed matrices. Discrete & Continuous Dynamical Systems - A, 2004, 11 (2&3) : 621-638. doi: 10.3934/dcds.2004.11.621

[8]

George Osipenko, Stephen Campbell. Applied symbolic dynamics: attractors and filtrations. Discrete & Continuous Dynamical Systems - A, 1999, 5 (1) : 43-60. doi: 10.3934/dcds.1999.5.43

[9]

Michael Hochman. A note on universality in multidimensional symbolic dynamics. Discrete & Continuous Dynamical Systems - S, 2009, 2 (2) : 301-314. doi: 10.3934/dcdss.2009.2.301

[10]

Thomas Feulner. The automorphism groups of linear codes and canonical representatives of their semilinear isometry classes. Advances in Mathematics of Communications, 2009, 3 (4) : 363-383. doi: 10.3934/amc.2009.3.363

[11]

Nicola Pace, Angelo Sonnino. On the existence of PD-sets: Algorithms arising from automorphism groups of codes. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020065

[12]

Jose S. Cánovas, Tönu Puu, Manuel Ruiz Marín. Detecting chaos in a duopoly model via symbolic dynamics. Discrete & Continuous Dynamical Systems - B, 2010, 13 (2) : 269-278. doi: 10.3934/dcdsb.2010.13.269

[13]

Nicola Soave, Susanna Terracini. Symbolic dynamics for the $N$-centre problem at negative energies. Discrete & Continuous Dynamical Systems - A, 2012, 32 (9) : 3245-3301. doi: 10.3934/dcds.2012.32.3245

[14]

Dieter Mayer, Fredrik Strömberg. Symbolic dynamics for the geodesic flow on Hecke surfaces. Journal of Modern Dynamics, 2008, 2 (4) : 581-627. doi: 10.3934/jmd.2008.2.581

[15]

Frédéric Naud. Birkhoff cones, symbolic dynamics and spectrum of transfer operators. Discrete & Continuous Dynamical Systems - A, 2004, 11 (2&3) : 581-598. doi: 10.3934/dcds.2004.11.581

[16]

Fryderyk Falniowski, Marcin Kulczycki, Dominik Kwietniak, Jian Li. Two results on entropy, chaos and independence in symbolic dynamics. Discrete & Continuous Dynamical Systems - B, 2015, 20 (10) : 3487-3505. doi: 10.3934/dcdsb.2015.20.3487

[17]

David Ralston. Heaviness in symbolic dynamics: Substitution and Sturmian systems. Discrete & Continuous Dynamical Systems - S, 2009, 2 (2) : 287-300. doi: 10.3934/dcdss.2009.2.287

[18]

Ben Niu, Weihua Jiang. Dynamics of a limit cycle oscillator with extended delay feedback. Discrete & Continuous Dynamical Systems - B, 2013, 18 (5) : 1439-1458. doi: 10.3934/dcdsb.2013.18.1439

[19]

Mike Boyle. The work of Mike Hochman on multidimensional symbolic dynamics and Borel dynamics. Journal of Modern Dynamics, 2019, 15: 427-435. doi: 10.3934/jmd.2019026

[20]

Anke D. Pohl. Symbolic dynamics for the geodesic flow on two-dimensional hyperbolic good orbifolds. Discrete & Continuous Dynamical Systems - A, 2014, 34 (5) : 2173-2241. doi: 10.3934/dcds.2014.34.2173

2019 Impact Factor: 1.338

Metrics

  • PDF downloads (9)
  • HTML views (24)
  • Cited by (0)

Other articles
by authors

[Back to Top]