Computing automorphism groups of shifts using atypical equivalence classes

Computing automorphism groups of shifts, using atypical equivalence classes, Discrete Analysis 2016:3, 24 pp.

Symbolic dynamics is about dynamical systems of the following type. Let \(A\) be an alphabet, and let \(\sigma\) be the left shift map from \(A^{\mathbb Z}\) to itself. Giving \(A\) the discrete topology and \(A^{\mathbb Z}\) the product topology, if \(X\) is a closed \(\sigma\)-invariant subset of \(A^{\mathbb Z}\), then \((X,\sigma)\) is a dynamical system. Of particular interest are minimal systems of this type: that is, systems where \(X\) is the closure of the set of all shifts of a single doubly infinite word \((a_n)_{n\in\mathbb{Z}}\) in \(A\). The properties of the word turn out to be interestingly related to properties of the dynamical system.

A key parameter for such a system is the complexity function \(p:\mathbb{N}\to\mathbb{N}\), where for each positive integer \(n\), \(p(n)\) is defined to be the number of distinct subwords of the form \((a_m,a_{m+1},\dots,a_{m+n-1})\). In particular, the rate of growth of this function is important.

An automorphism of a dynamical system \((X,\sigma)\) is a continuous bijection from \(X\) to \(X\) that commutes with \(\sigma\). A trivial example of an automorphism is \(\sigma\) itself, or indeed any power of \(\sigma\). In the past few years, there has been a lot of work on showing that dynamical systems \((X,\sigma)\) for which the complexity function grows slowly have automorphism groups that are in some sense small. However, even in the lowest nontrivial complexity (that of nonconstant, sublinear complexity), we do not have a complete understanding of the automorphism group, and in general there is no method that gives a complete characterization of this group.

In this paper, the authors focus on the particular class of substitution systems of constant length, which are the systems whose infinite words are obtained by iterating a substitution infinitely many times on some letter in the alphabet. An interesting result in the paper is an algorithm to compute the automorphism group in this situation, along with the use of this algorithm to compute all conjugacies between two shifts generated by constant length substitutions. The proof uses dynamical methods to reduce the problem to combinatorial arguments. Another result is that for a minimal system with complexity that grows at most linearly the quotient of the automorphism group by the group generated by \(\sigma\) is finite.

It is not clear whether the techniques used in this paper can be generalized to a significantly wider class of systems. However, the difficulty of computing the automorphism group in general is such that any new non-trivial examples are useful and instructive.