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

Abstract

Let $1\le r<n$ be integers. We give a proof that the group $\mathrm{Aut}(X_n^{\mathbb{N}},{\sigma }_n)$ of automorphisms of the one-sided shift on $n$ letters embeds naturally as a subgroup ${\mathcal{H}}_n$ of the outer automorphism group $\mathrm{Out}(G_{n,r})$ of the Higman-Thompson group $G_{n,r}$. From this, we can represent the elements of $\mathrm{Aut}(X_n^{\mathbb{N}},{\sigma }_n)$ by finite state non-initial transducers admitting a very strong synchronizing condition. Let $H\in {\mathcal{H}}_n$ and write $|H|$ for the number of states of the minimal transducer representing $H$. We show that $H$ can be written as a product of at most $|H|$ torsion elements. This result strengthens a similar result of Boyle, Franks and Kitchens, where the decomposition involves more complex torsion elements and also does not support practical \textit{a priori} estimates of the length of the resulting product. We also explore the number of foldings of de Bruijn graphs and give a counting result for these for word length $2$ and alphabet size $n$. Finally, we offer new proofs of some known results about $\mathrm{Aut}(X_n^{\mathbb{N}},{\sigma }_n)$.

35 pages; corrected some minor typos

References in corpus (2)

• The growth rates of automaton groups generated by reset automata
• Presentations of generalisations of Thompson's group $V$