| Popis: |
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 |
