Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

Request Permissions   Purchase Content 


The automorphism group of a shift of subquadratic growth

Authors: Van Cyr and Bryna Kra
Journal: Proc. Amer. Math. Soc. 144 (2016), 613-621
MSC (2010): Primary 37B50; Secondary 68R15, 37B10
Published electronically: June 9, 2015
MathSciNet review: 3430839
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: For a subshift over a finite alphabet, a measure of the complexity of the system is obtained by counting the number of nonempty cylinder sets of length $ n$. When this complexity grows exponentially, the automorphism group has been shown to be large for various classes of subshifts. In contrast, we show that subquadratic growth of the complexity implies that for a topologically transitive shift $ X$, the automorphism group $ \operatorname {Aut}(X)$ is small: if $ H$ is the subgroup of $ \operatorname {Aut}(X)$ generated by the shift, then $ \operatorname {Aut}(X)/H$ is periodic. For linear growth, we show the stronger result that $ \operatorname {Aut}(X)/H$ is a group of finite exponent.

References [Enhancements On Off] (What's this?)

  • [1] Pierre Arnoux and Gérard Rauzy, Représentation géométrique de suites de complexité $ 2n+1$, Bull. Soc. Math. France 119 (1991), no. 2, 199-215 (French, with English summary). MR 1116845 (92k:58072)
  • [2] Mike Boyle, Douglas Lind, and Daniel Rudolph, The automorphism group of a shift of finite type, Trans. Amer. Math. Soc. 306 (1988), no. 1, 71-114. MR 927684 (89m:54051),
  • [3] F. Durand, B. Host, and C. Skau, Substitutional dynamical systems, Bratteli diagrams and dimension groups, Ergodic Theory Dynam. Systems 19 (1999), no. 4, 953-993. MR 1709427 (2000i:46062),
  • [4] S. Donoso, F. Durand, A. Maass and S. Petite. On the automorphism group of minimal subshifts. arXiv:1501.00510.
  • [5] B. Host and F. Parreau, Homomorphismes entre systèmes dynamiques définis par substitutions, Ergodic Theory Dynam. Systems 9 (1989), no. 3, 469-477 (French). MR 1016665 (91g:28022),
  • [6] N. Pytheas Fogg, Substitutions in dynamics, arithmetics and combinatorics, Lecture Notes in Mathematics, vol. 1794, Springer-Verlag, Berlin, 2002. Edited by V. Berthé, S. Ferenczi, C. Mauduit and A. Siegel. MR 1970385 (2004c:37005)
  • [7] G. A. Hedlund, Endomorphisms and automorphisms of the shift dynamical system, Math. Systems Theory 3 (1969), 320-375. MR 0259881 (41 #4510)
  • [8] Douglas Lind and Brian Marcus, An introduction to symbolic dynamics and coding, Cambridge University Press, Cambridge, 1995. MR 1369092 (97a:58050)
  • [9] Marston Morse and Gustav A. Hedlund, Symbolic dynamics II. Sturmian trajectories, Amer. J. Math. 62 (1940), 1-42. MR 0000745 (1,123d)
  • [10] Tom Meyerovitch, Growth-type invariants for $ \mathbb{Z}^d$ subshifts of finite type and arithmetical classes of real numbers, Invent. Math. 184 (2011), no. 3, 567-589. MR 2800695 (2012d:37042),
  • [11] Jeanette Olli, Endomorphisms of Sturmian systems and the discrete chair substitution tiling system, Discrete Contin. Dyn. Syst. 33 (2013), no. 9, 4173-4186. MR 3038057,
  • [12] Jean-Jacques Pansiot, Complexité des facteurs des mots infinis engendrés par morphismes itérés, Automata, languages and programming (Antwerp, 1984) Lecture Notes in Comput. Sci., vol. 172, Springer, Berlin, 1984, pp. 380-389 (French, with English summary). MR 784265,
  • [13] Anthony Quas and Luca Zamboni, Periodicity and local complexity, Theoret. Comput. Sci. 319 (2004), no. 1-3, 229-240. MR 2074955 (2005e:68204),
  • [14] V. Salo, Toeplitz subshift whose automorphism group is not finitely generated, arXiv:1411.3299.
  • [15] V. Salo and I. Törmä, Block Maps between Primitive Uniform and Pisot Substitutions, arXiv:1306.3777.
  • [16] J. W. Sander and R. Tijdeman, The rectangle complexity of functions on two-dimensional lattices, Theoret. Comput. Sci. 270 (2002), no. 1-2, 857-863. MR 1871099 (2002j:68080),

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 37B50, 68R15, 37B10

Retrieve articles in all journals with MSC (2010): 37B50, 68R15, 37B10

Additional Information

Van Cyr
Affiliation: Department of Mathematics, Bucknell University, Lewisburg, Pennsylvania 17837

Bryna Kra
Affiliation: Department of Mathematics, Northwestern University, Evanston, Illinois 60208

Keywords: Subshift, automorphism, block complexity
Received by editor(s): March 2, 2014
Received by editor(s) in revised form: January 8, 2015
Published electronically: June 9, 2015
Additional Notes: The second author was partially supported by NSF grant $1200971$.
Communicated by: Nimish Shah
Article copyright: © Copyright 2015 American Mathematical Society

American Mathematical Society