Automorphisms of shift spaces and the Higman–Thompson groups: the one-sided case

Automorphisms of shift spaces and the Higman–Thompson groups: the one-sided case, Discrete Analysis 2021:15, 35 pp.

Symbolic dynamics is the study of dynamical systems of the following kind, known as shift spaces. One takes an alphabet $\Sigma$ of “symbols” and a closed (in the product topology) shift-invariant subset $X$ of $\Sigma^{\mathbb Z}$ or $\Sigma^{\mathbb N}$ and looks at iterations of the shift applied to $X$. An important particular case is to take a single infinite sequence $x$ and to let $X$ be the closure of the orbit of $x$. Another case, more relevant to this paper, is the full shift, where one takes $X$ to consist of all sequences.

An automorphism of a shift space is a shift-invariant homeomorphism of $X$ to itself. Typically, such homeomorphisms are quite hard to construct, so the automorphism groups of shift spaces tend to be “small” in some sense. For example, the automorphism group of the space $\{0,1\}^{\mathbb N}$ is the cyclic group of order 2, with the two shift-invariant automorphisms being the identity and the map that interchanges 0s and 1s. (That said, once the alphabet is larger than this, the groups contain free groups, but they are nevertheless much smaller than the group of all homeomorphisms of $\{0,1\}^{\mathbb N}$. For example, they have to be countable.)

However, determining the automorphism groups is quite hard (even the result just mentioned is a genuine theorem and not simply an exercise), and this has led to an active research area. This paper concerns automorphims of the full shift in the one-sided case (the authors have a companion paper that deals with the two-sided case, which is genuinely different in various ways).

Something of the flavour of the paper is conveyed by the following non-trivial example of a shift-invariant automorphism of the space $\{0,1,2\}^{\mathbb N}$, which it is more convenient to think of as $\{0,1,2\}^{-\mathbb N}$ – that is, as the space of sequences $(\dots,x_{-2},x_{-1},x_0)$. To any such sequence one applies a synchronous transducer, which is a finite-state automaton that works as follows. At any one moment it is looking at some term $x_{-n}$ and is in some state $q$ that belongs to a set $Q=\{q_1,\dots,q_r\}$. It then sets $y_{-n}$ to be equal to $\phi(x_{-n},q)$, changes to a new state $\pi(x_{-n},q)$, and turns its attention to the next term $x_{-(n-1)}$.

As soon as one tries to imagine using this idea, one runs into a problem: how does the process start? Or rather, since it doesn’t really start – it has always been going on – how do we ever know what state it is in? The answer is that some transducers have a special property, one that is definitely not shared by an arbitrary transducer, which is that for some $k$ the state that they are in by the time they reach $x_{-n}$ depends only on the terms $x_{-n-1},x_{-n-2},\dots,x_{-n-k}$ and not on the state they were in when they were looking at $x_{-n-k}$. Such transducers are called strongly synchronizing. Given a strongly synchronizing transducer, one obtains a well-defined map, and if its inverse is also strongly synchronizing, in which case it is called bi-synchronizing, then it is then easy to see that it is a shift-invariant homeomorphism.

A concrete example of such a transducer is the following. Write $(q,a)\to (r,b)$ to mean that if the transducer is in state $q$ and sees $a$, then it will change state to $r$ and write $b$ (and then move to the next term). Then the instructions are
$(q_0,0)\to(q_0,0)$
$(q_0,1)\to(q_2,1)$
$(q_0,2)\to(q_1,2)$
$(q_1,0)\to(q_0,1)$
$(q_1,1)\to(q_2,0)$
$(q_1,2)\to(q_1,2)$
$(q_2,0)\to(q_1,2)$
$(q_2,1)\to(q_2,1)$
$(q_2,2)\to(q_0,0)$
One can check that this is strongly synchronizing. For instance, if it ever encounters a 1, it will go into state $q_2$. Less trivially, if it encounters 00 then it will go into state $q_0$ and if it encounters 02, then it will go into state $q_1$.

One of the main results of this paper is to show that the group of automorphisms of the one-sided shift on $X_n^{\mathbb N}$ (where $X_n$ is a set of size $n$) embeds naturally into the outer automorphism group of any one of the Higman-Thompson groups $G_{n,r}$, which can be defined as follows. Let $1\leq r<n$. The Cantor space $\mathcal C_{n,r}$ is the space of sequences $ca_0a_1\dots$ such that $c$ belongs to a set of size $r$ and all the $a_i$ belong to $X_n$. A cone in the Cantor space is a set of sequences that agree on some non-trivial initial segment. Given two cones, there is an obvious homeomorphism between them that maps a sequence that begins with one initial segment and continues in a certain way to the sequence that begins with the other initial segment and continues in the same way. The group $G_{n,r}$ consists of all homeomorphisms that are obtained by decomposing $\mathcal C_{n,r}$ into some finite number $m$ of cones in two ways, picking a bijection between the cones from the two decompositions, and mapping the cones from the first decomposition to the cones from the second decomposition in the manner just described. One can check that these maps do indeed form a group. Note that $G_{n,r}$ embeds in an obvious way into $G_{n,r+1}$, and also that $G_{n,n}$ is isomorphic to $G_{n,1}$. Corresponding statements can also be shown for the outer automorphism groups, which explains why the theorem above is not sensitive to the chosen value of $r$. (One could for instance set $r$ to be 1.)

The Higman-Thompson groups were defined by Higman, who generalized in a straightforward way a construction of Thompson (the logician Richard Thompson rather than the group theorist John Thompson), which was the first known example of a finitely presented infinite simple group. The groups $G_{n,r}$ are also infinite and finitely presented; they are simple when $n$ is even and have a simple subgroup of index 2 when $n$ is odd. Thus, this paper demonstrates a very satisfying connection between groups arising in dynamics and groups arising for more purely group-theoretic reasons.

The elements of the outer automorphism group of $G_{n,r}$ can be described as transducers of a particular kind, and those that correspond to synchronous transducers then define automorphisms of the shift. To prove the theorem, it is necessary to show that all automorphisms of the shift arise in this way.

As a by-product of their approach, the authors obtain a detailed description of the automorphisms. A transducer can be represented as a labelled directed multigraph (with loops), where the vertices are the states, with an edge from state $q$ to state $r$ labelled $x|y$ if the transducer moves to state $r$ and writes $y$ if it sees $x$ in state $q$. The authors show that a transducer with $r$ states that belongs to the automorphism group of the shift can be decomposed into at most $r$ arising in a way they explain from automorphisms of quotients of the directed graph. In particular, it is a product of at most $r$ torsion elements. This simplifies earlier results in a similar direction, from which it had also been hard to extract bounds on the number of torsion elements needed.