On automorphism groups of Toeplitz subshifts

On automorphism groups of Toeplitz subshifts, Discrete Analysis 2017:11, 19 pp.

A discrete dynamical system is a space $X$ with some kind of structure, together with a map $\sigma\colon X\to X$ that preserves the structure. (For instance, if $X$ is a topological space, then one asks for $\sigma$ to be continuous, and if $X$ is a differentiable manifold, then one asks for it to be a diffeomorphism.) Given such a system, one studies the structure of the orbits $x, \sigma x, \sigma^2x, \dots$ that are obtained by iterating the map $\sigma$. A particularly interesting subfield of dynamics is symbolic dynamics, where $X$ is a space of bi-infinite sequences over a finite alphabet $A$, $X$ is closed under the left shift, and $\sigma$ is that left shift. One also asks for $X$ to be closed in the topological sense: we take the discrete topology on $A$ and the product topology on $A^{\mathbb Z}$, of which $X$ is a subset. A system $(X,\sigma)$ is called a shift space. Such spaces can encode interesting combinatorial information, and that has led to a very fruitful interplay between combinatorics and dynamical systems.

An automorphism of the system $(X, \sigma)$ is a homeomorphism $\phi\colon X\to X$ that commutes with $\sigma$, and ${\rm Aut}(X, \sigma)$ denotes the group (under composition) of automorphisms of the system. The complexity of a shift system ${\rm Aut}(X, \sigma)$ is the map $p\colon\mathbb N\to \mathbb N$ that counts the number of blocks of length $n$ appearing in the sequences $x\in X$. If the complexity is linear, then the automorphism group is understood for any shift ${\rm Aut}(X, \sigma)$, but beyond linear, the problem becomes complicated. For example, under mild assumptions on the shift ${\rm Aut}(X, \sigma)$, the automorphism group is not finitely generated and it contains isomorphic copies of all finite groups, countably many copies of $\mathbb Z$, and the free group on any finite number of generators. Thus while ${\rm Aut}(X, \sigma)$ is always countable, in general it can be quite complicated and difficult to compute. However, for several reasons it is desirable to do so: for example, it gives a useful invariant.

This paper continues recent work on automorphism groups for various classes of shift spaces, computing the automorphism group for the class of Toeplitz shifts, a large class of shift systems frequently used to provide counterexamples in symbolic dynamics. A sequence $x\in A^{\mathbb Z}$ is Toeplitz if every finite block in $x$ appears periodically, and a shift space $(X, \sigma)$ is a Toeplitz shift if $X$ is the orbit closure of some Toeplitz sequence. (It is not hard to construct Toeplitz sequences that are not periodic. For one example, take $x_n$ to be the parity of $k$, where $k$ is maximal such that $2^k|n$.) This rigid structure on $X$ implies that ${\rm Aut}(X, \sigma)$ is Abelian, and this is the starting point for the classification of the automorphism groups of Toeplitz shifts.

The authors start with Toeplitz shifts of subquadratic complexity, showing that the automorphism group is spanned by the roots of the shift map $\sigma$ modulo the torsion subgroup $T$ of ${\rm Aut}(X, \sigma)$. More generally, they show that if ${\rm Aut}(X, \sigma)/\langle\sigma\rangle$ is a periodic group, then the automorphism group is spanned by $T$ and the roots of the shift $\sigma$ (that is, the automorphisms $\phi$ such that $\phi^n=\sigma$ for some $n$). Under the further assumption that $T$ is trivial, they show that the automorphism group is either infinite cyclic or is not finitely generated. This method leads to examples of Toeplitz shifts whose complexity is arbitrarily close to linear, in the sense that for every $\varepsilon > 0$ the complexity satisfies the inequality $p(n)\leq Cn^{1+\varepsilon}$ for some constant $C=C_\varepsilon > 0$, such that the automorphism group is not finitely generated. Note that this result cannot be extended to linear complexity, where it is known that the automorphism group is always finitely generated.

In the opposite regime, that of high complexity, the authors show that the automorphism group need not be large. Given any infinite and finitely generated Abelian group $G$ with cyclic torsion, they construct a Toeplitz shift with positive entropy (meaning that the complexity function grows exponentially) whose automorphism group is exactly $G$.