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

Collin Bleak ; Peter J. Cameron ; Feyishayo Olukoya

Discrete analysis (2021)

Résumé

Let $1 \le r n$ be integers. We give a proof that the group $\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{N}}, σ_{n}})$ of automorphisms of the one-sided shift on $n$ letters embeds naturally as a subgroup $\mathcal{H}_{n}$ of the outer automorphism group $\mathop{\mathrm{Out}}({G_{n,r}})$ of the Higman-Thompson group $G_{n,r}$. From this, we can represent the elements of $\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{N}}, σ_{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 $\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{N}}, σ_{n}})$.

Détail

Publié le : 2021-09-20