Figure 1.
An example of applying a rectangular substitution to a pattern
-
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 |
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.
Keywords:
Symbolic dynamics,
automorphism groups,
extended symmetries,
substitutions,
Robinson tiling.
Mathematics Subject Classification:
37B10, 37B51, 20B27, 52C23.
Citation:
Álvaro Bustos. Extended symmetry groups of multidimensional subshifts with hierarchical structure. Discrete and Continuous Dynamical Systems,
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. |
| [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. |
| [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. |
| [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. |
| [5] |
M. M. Boyle, Topological Orbit Equivalence and Factor Maps in Symbolic Dynamics, PhD thesis, University of Washington, 1983. |
| [6] |
M. Boyle, D. 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. |
| [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. |
| [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. |
| [9] |
E. M. Coven,
Endomorphisms of substitution minimal sets, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete, 20 (1971), 129-133.
doi: 10.1007/BF00536290. |
| [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. |
| [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. |
| [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. |
| [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. |
| [14] |
N. P. Frank,
Multidimensional constant-length substitution sequences, Topology Appl., 152 (2005), 44-69.
doi: 10.1016/j.topol.2004.08.014. |
| [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. |
| [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. |
| [17] |
G. R. Goodson,
Inverse conjugacies and reversing symmetry groups, Amer. Math. Monthly, 106 (1999), 19-26.
doi: 10.1080/00029890.1999.12005002. |
| [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. |
| [19] |
J. Kellendonk and R. Yassawi, The Ellis semigroup of bijective substitutions, preprint, arXiv: 1908.05690. |
| [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. |
| [21] |
B. Kitchens and K. Schmidt,
Isomorphism rigidity of irreducible algebraic Zd-actions, Invent. Math., 142 (2000), 559-577.
doi: 10.1007/PL00005793. |
| [22] |
P. Kůrka, Topological and Symbolic Dynamics, Société mathématique de France, Paris, 2003. |
| [23] |
M. Lemańczyk and M. K. Mentzen,
On metric properties of substitutions, Compositio Math, 65 (1988), 241-263.
|
| [24] |
D. Lind and B. Marcus, An Introduction to Symbolic Dynamics and Coding, Cambridge University Press, Cambridge, 1995.
doi: 10.1017/CBO9780511626302.
|
| [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. |
| [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. |
| [27] |
B. Mossé,
Reconnaissabilité des substitutions et complexité des suites automatiques, Bull. Soc. Math. France, 124 (1996), 329-346.
doi: 10.24033/bsmf.2283. |
| [28] |
A. G. O'Farrell and I. Short, Reversibility in Dynamics and Group Theory, Cambridge University Press, Cambridge, 2015.
doi: 10.1017/CBO9781139998321.
|
| [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. |
| [30] |
N. P. Fogg (ed.), Substitutions in Dynamics, Arithmetics and Combinatorics, Lecture Notes in Mathematics, 1794. Springer-Verlag, Berlin, 2002.
doi: 10.1007/b13861. |
| [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. |
| [32] |
R. M. Robinson,
Undecidability and nonperiodicity for tilings of the plane, Invent. Math., 12 (1971), 177-209.
doi: 10.1007/BF01418780. |
| [33] |
K. Schmidt, Dynamical Systems of Algebraic Origin, Modern Birkhäuser Classics. Birkhäuser/Springer Basel AG, Basel, 1995. |
| [34] |
B. Solomyak,
Nonperiodicity implies unique composition for self-similar translationally finite tilings, Discrete Comput. Geom., 20 (1998), 265-279.
doi: 10.1007/PL00009386. |
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. |
| [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. |
| [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. |
| [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. |
| [5] |
M. M. Boyle, Topological Orbit Equivalence and Factor Maps in Symbolic Dynamics, PhD thesis, University of Washington, 1983. |
| [6] |
M. Boyle, D. 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. |
| [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. |
| [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. |
| [9] |
E. M. Coven,
Endomorphisms of substitution minimal sets, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete, 20 (1971), 129-133.
doi: 10.1007/BF00536290. |
| [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. |
| [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. |
| [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. |
| [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. |
| [14] |
N. P. Frank,
Multidimensional constant-length substitution sequences, Topology Appl., 152 (2005), 44-69.
doi: 10.1016/j.topol.2004.08.014. |
| [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. |
| [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. |
| [17] |
G. R. Goodson,
Inverse conjugacies and reversing symmetry groups, Amer. Math. Monthly, 106 (1999), 19-26.
doi: 10.1080/00029890.1999.12005002. |
| [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. |
| [19] |
J. Kellendonk and R. Yassawi, The Ellis semigroup of bijective substitutions, preprint, arXiv: 1908.05690. |
| [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. |
| [21] |
B. Kitchens and K. Schmidt,
Isomorphism rigidity of irreducible algebraic Zd-actions, Invent. Math., 142 (2000), 559-577.
doi: 10.1007/PL00005793. |
| [22] |
P. Kůrka, Topological and Symbolic Dynamics, Société mathématique de France, Paris, 2003. |
| [23] |
M. Lemańczyk and M. K. Mentzen,
On metric properties of substitutions, Compositio Math, 65 (1988), 241-263.
|
| [24] |
D. Lind and B. Marcus, An Introduction to Symbolic Dynamics and Coding, Cambridge University Press, Cambridge, 1995.
doi: 10.1017/CBO9780511626302.
|
| [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. |
| [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. |
| [27] |
B. Mossé,
Reconnaissabilité des substitutions et complexité des suites automatiques, Bull. Soc. Math. France, 124 (1996), 329-346.
doi: 10.24033/bsmf.2283. |
| [28] |
A. G. O'Farrell and I. Short, Reversibility in Dynamics and Group Theory, Cambridge University Press, Cambridge, 2015.
doi: 10.1017/CBO9781139998321.
|
| [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. |
| [30] |
N. P. Fogg (ed.), Substitutions in Dynamics, Arithmetics and Combinatorics, Lecture Notes in Mathematics, 1794. Springer-Verlag, Berlin, 2002.
doi: 10.1007/b13861. |
| [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. |
| [32] |
R. M. Robinson,
Undecidability and nonperiodicity for tilings of the plane, Invent. Math., 12 (1971), 177-209.
doi: 10.1007/BF01418780. |
| [33] |
K. Schmidt, Dynamical Systems of Algebraic Origin, Modern Birkhäuser Classics. Birkhäuser/Springer Basel AG, Basel, 1995. |
| [34] |
B. Solomyak,
Nonperiodicity implies unique composition for self-similar translationally finite tilings, Discrete Comput. Geom., 20 (1998), 265-279.
doi: 10.1007/PL00009386. |
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 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 and Continuous Dynamical Systems, 2008, 20 (3) : 725-738. doi: 10.3934/dcds.2008.20.725 |
| [2] |
Yunping Wang, Ercai Chen, Xiaoyao Zhou. Mean dimension theory in symbolic dynamics for finitely generated amenable groups. Discrete and Continuous Dynamical Systems, 2022 doi: 10.3934/dcds.2022050 |
| [3] |
Younghwan Son. Substitutions, tiling dynamical systems and minimal self-joinings. Discrete and Continuous Dynamical Systems, 2014, 34 (11) : 4855-4874. doi: 10.3934/dcds.2014.34.4855 |
| [4] |
S. Eigen, V. S. Prasad. Tiling Abelian groups with a single tile. Discrete and Continuous Dynamical Systems, 2006, 16 (2) : 361-365. doi: 10.3934/dcds.2006.16.361 |
| [5] |
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 |
| [6] |
Michael Baake, John A. G. Roberts, Reem Yassawi. Reversing and extended symmetries of shift spaces. Discrete and Continuous Dynamical Systems, 2018, 38 (2) : 835-866. doi: 10.3934/dcds.2018036 |
| [7] |
Benjamin Hellouin de Menibus, Hugo Maturana Cornejo. Necessary conditions for tiling finitely generated amenable groups. Discrete and Continuous Dynamical Systems, 2020, 40 (4) : 2335-2346. doi: 10.3934/dcds.2020116 |
| [8] |
Heide Gluesing-Luerssen, Hunter Lehmann. Automorphism groups and isometries for cyclic orbit codes. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021040 |
| [9] |
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 |
| [10] |
Nicola Pace, Angelo Sonnino. On the existence of PD-sets: Algorithms arising from automorphism groups of codes. Advances in Mathematics of Communications, 2021, 15 (2) : 267-277. doi: 10.3934/amc.2020065 |
| [11] |
Jim Wiseman. Symbolic dynamics from signed matrices. Discrete and Continuous Dynamical Systems, 2004, 11 (2&3) : 621-638. doi: 10.3934/dcds.2004.11.621 |
| [12] |
George Osipenko, Stephen Campbell. Applied symbolic dynamics: attractors and filtrations. Discrete and Continuous Dynamical Systems, 1999, 5 (1) : 43-60. doi: 10.3934/dcds.1999.5.43 |
| [13] |
Michael Hochman. A note on universality in multidimensional symbolic dynamics. Discrete and Continuous Dynamical Systems - S, 2009, 2 (2) : 301-314. doi: 10.3934/dcdss.2009.2.301 |
| [14] |
Jose S. Cánovas, Tönu Puu, Manuel Ruiz Marín. Detecting chaos in a duopoly model via symbolic dynamics. Discrete and Continuous Dynamical Systems - B, 2010, 13 (2) : 269-278. doi: 10.3934/dcdsb.2010.13.269 |
| [15] |
Nicola Soave, Susanna Terracini. Symbolic dynamics for the $N$-centre problem at negative energies. Discrete and Continuous Dynamical Systems, 2012, 32 (9) : 3245-3301. doi: 10.3934/dcds.2012.32.3245 |
| [16] |
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 |
| [17] |
Frédéric Naud. Birkhoff cones, symbolic dynamics and spectrum of transfer operators. Discrete and Continuous Dynamical Systems, 2004, 11 (2&3) : 581-598. doi: 10.3934/dcds.2004.11.581 |
| [18] |
Fryderyk Falniowski, Marcin Kulczycki, Dominik Kwietniak, Jian Li. Two results on entropy, chaos and independence in symbolic dynamics. Discrete and Continuous Dynamical Systems - B, 2015, 20 (10) : 3487-3505. doi: 10.3934/dcdsb.2015.20.3487 |
| [19] |
David Ralston. Heaviness in symbolic dynamics: Substitution and Sturmian systems. Discrete and Continuous Dynamical Systems - S, 2009, 2 (2) : 287-300. doi: 10.3934/dcdss.2009.2.287 |
| [20] |
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 |
2021 Impact Factor: 1.588
Tools
Metrics
Other articles
by authors
[Back to Top]