×

Transitive action on finite points of a full shift and a finitary Ryan’s theorem. (English) Zbl 1410.37020

Summary: We show that on the four-symbol full shift, there is a finitely generated subgroup of the automorphism group whose action is (set-theoretically) transitive of all orders on the points of finite support, up to the necessary caveats due to shift-commutation. As a corollary, we obtain that there is a finite set of automorphisms whose centralizer is \(\mathbb{Z}\) (the shift group), giving a finitary version of Ryan’s theorem (on the four-symbol full shift), suggesting an automorphism group invariant for mixing subshifts of finite type (SFTs). We show that any such set of automorphisms must generate an infinite group, and also show that there is also a group with this transitivity property that is a subgroup of the commutator subgroup and whose elements can be written as compositions of involutions. We ask many related questions and prove some easy transitivity results for the group of reversible Turing machines, topological full groups and Thompson’s \(V\).

MSC:

37B50 Multi-dimensional shifts of finite type, tiling dynamics (MSC2010)
37B10 Symbolic dynamics
37B20 Notions of recurrence and recurrent behavior in topological dynamical systems
37B05 Dynamical systems involving transformations and group actions with special properties (minimality, distality, proximality, expansivity, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Barbieri, S., Kari, J. and Salo, V.. The Group of Reversible Turing Machines. Springer International Publishing, Cham, 2016, pp. 49-62. · Zbl 1350.68101
[2] Boykett, T.. Closed systems of invertible maps. Preprint, 2015, https://arxiv.org/abs/1512.06813.
[3] Boykett, T., Kari, J. and Salo, V.. Strongly Universal Reversible Gate Sets. Springer International Publishing, Cham, 2016, pp. 239-254. · Zbl 1384.94143
[4] Boyle, M., Some sofic shifts cannot commute with nonwandering shifts of finite type, Illinois J. Math., 48, 4, 1267-1277, (2004) · Zbl 1063.37011
[5] Boyle, M.. Open problems in symbolic dynamics. Geometric and Probabilistic Structures in Dynamics. American Mathematical Society, Providence, RI, 2008, pp. 69-118. · Zbl 1158.37007
[6] Boyle, M. and Chuysurichay, S.. The mapping class group of a shift of finite type. Preprint, 2017, https://arxiv.org/abs/1704.03916. · Zbl 1407.37020
[7] Boyle, M. and Fiebig, U.-R.. The action of inert finite-order automorphisms on finite subsystems of the shift. Ergod. Th. & Dynam. Sys.11(03) (1991), 413-425. · Zbl 0712.54027
[8] Boyle, M., Lind, D. and Rudolph, D.. The automorphism group of a shift of finite type. Trans. Amer. Math. Soc.306(1) (1988), 71-114. · Zbl 0664.28006
[9] Boyle, M., Meier Carlsen, T. and Eilers, S.. Flow equivalence of G-SFTs. Preprint, 2015, https://arxiv.org/abs/1512.05238. · Zbl 1440.37019
[10] Boyle, M. and Tuncel, S.. Infinite-to-one codes and Markov measures. Trans. Amer. Math. Soc.285(2) (1984), 657-684. · Zbl 0515.28011
[11] Cannon, J. W., Floyd, W. J. and Parry, W. R.. Introductory notes on Richard Thompson’s groups. Enseign. Math.42 (1996), 215-256. · Zbl 0880.20027
[12] Ceccherini-Silberstein, T. and Coornaert, M.. Cellular Automata and Groups. Springer, Berlin, 2010. · Zbl 1218.37004
[13] Charney, R., An introduction to right-angled artin groups, Geom. Dedicata, 125, 1, 141-158, (2007) · Zbl 1152.20031
[14] Coven, E. and Yassawi, R.. Endomorphisms and automorphisms of minimal symbolic systems with sublinear complexity. Preprint, 2014, https://arxiv.org/abs/1412.0080.
[15] Cyr, V. and Kra, B.. The automorphism group of a shift of subquadratic growth. Preprint, 2014, https://arxiv.org/abs/1403.0238. · Zbl 1365.37019
[16] Dixon, J. D. and Mortimer, B.. Permutation Groups. Vol. 163. Springer, New York, 1996. · Zbl 0951.20001
[17] Donoso, S., Durand, F., Maass, A. and Petite, S.. On automorphism groups of low complexity subshifts. Ergod. Th. & Dynam. Sys.36(01) (2016), 64-95. · Zbl 1354.37024
[18] Frisch, J., Schlank, T. and Tamuz, O.. Normal amenable subgroups of the automorphism group of the full shift. Ergod. Th. & Dynam. Sys. doi:10.1017/etds.2017.72, Published online 7 September 2017, pp. 1-9. · Zbl 1512.37021
[19] Hedlund, G. A., Endomorphisms and automorphisms of the shift dynamical system, Math. Syst. Theory, 3, 320-375, (1969) · Zbl 0182.56901
[20] Host, B. and Parreau, F.. Homomorphismes entre systèmes dynamiques définis par substitutions. Ergod. Th. & Dynam. Sys.9(8) (1989), 469-477. · Zbl 0662.58027
[21] Kari, J., Representation of reversible cellular automata with block permutations, Theory Comput. Syst., 29, 47-61, (1996) · Zbl 0840.68081
[22] Kari, J., Theory of cellular automata: a survey, Theoret. Comput. Sci., 334, 1-3, 3-33, (2005) · Zbl 1080.68070
[23] Kari, J., Universal pattern generation by cellular automata, Theoret. Comput. Sci., 429, 180-184, (2012) · Zbl 1238.68089
[24] Kari, J. and Ollinger, N.. Periodicity and immortality in reversible computing. Proceedings of the 33rd International Symposium on Mathematical Foundations of Computer Science, MFCS ’08. Springer, Berlin, 2008, pp. 419-430. · Zbl 1173.68521
[25] Kim, K. H. and Roush, F. W.. On the automorphism groups of subshifts. Pure Math. Appl.1(4) (1990), 203-230. · Zbl 0734.54027
[26] Kim, K. H., Roush, F. W. and Wagoner, J. B.. Characterization of inert actions on periodic points. Part I. Forum Math.12 (2000), 565-602. · Zbl 0997.37005
[27] Kim, K. H., Roush, F. W. and Wagoner, J. B.. Characterization of inert actions on periodic points. Part II. Forum Math.12 (2000), 671-712. · Zbl 0984.37010
[28] Lafont, Y., Towards an algebraic theory of boolean circuits, J. Pure Appl. Algebra, 184, (2003) · Zbl 1037.94015
[29] Lind, D. A., The entropies of topological Markov shifts and a related class of algebraic integers, Ergod. Th. & Dynam. Sys., 4, 6, 283-300, (1984) · Zbl 0546.58035
[30] Lind, D. and Marcus, B.. An Introduction to Symbolic Dynamics and Coding. Cambridge University Press, Cambridge, 1995. · Zbl 1106.37301
[31] Lind, D. and Schmidt, K.. Homoclinic points of algebraic ℤd-actions. J. Amer. Math. Soc.12(4) (1999), 953-980. · Zbl 0940.22004
[32] Lukkarila, V., Sensitivity and topological mixing are undecidable for reversible one-dimensional cellular automata, J. Cell. Autom., 5, 3, 241-272, (2010) · Zbl 1203.68108
[33] Matui, H., Some remarks on topological full groups of cantor minimal systems, Internat. J. Math., 17, 2, 231-251, (2006) · Zbl 1109.37008
[34] Mcgoff, K., Random subshifts of finite type, Ann. Probab., 40, 2, 648-694, (2012) · Zbl 1269.37009
[35] Nasu, M.. Textile systems for endomorphisms and automorphisms of the shift. Mem. Amer. Math. Soc.114(546) (1995), viii + 215. · Zbl 0845.54031
[36] Nasu, M., Textile systems and one-sided resolving automorphisms and endomorphisms of the shift, Ergod. Th. & Dynam. Sys., 28, 167-209, (2008) · Zbl 1171.37308
[37] Olli, J., Endomorphisms of sturmian systems and the discrete chair substitution tiling system, Dyn. Syst., 33, 9, 4173-4186, (2013) · Zbl 1316.37011
[38] Patrick Ryan, J., The shift and commutativity, Math. Syst. Theory, 6, 1-2, 82-85, (1972) · Zbl 0227.54037
[39] Salo, V.. Subshifts with simple cellular automata. PhD Thesis, University of Turku, 2014.
[40] Salo, V., Toeplitz subshift whose automorphism group is not finitely generated, Colloquium Math., 146, 53-76, (2017) · Zbl 1377.37021
[41] Salo, V.. A note on subgroups of automorphism groups of full shifts. Ergod. Th. & Dynam. Sys. doi:10.1017/etds.2016.95, Published online 8 November 2016, pp. 1-13.
[42] Salo, V.. Transitive action on finite points of a full shift and a finitary Ryan’s theorem. Preprint, 2016, https://arxiv.org/abs/1610.05487v1.
[43] Salo, V. and Törmä, I.. Color blind cellular automata. J. Cell. Autom.9(5-6) (2014), 477-509. · Zbl 1338.68194
[44] Selinger, P.. Reversible \(k\)-valued logic circuits are finitely generated for odd \(k\). Preprint, 2016, https://arxiv.org/abs/1604.01646.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.