No Tits alternative for cellular automata
Ville Salo
https://urn.fi/URN:NBN:fi-fe2021042822649
Tiivistelmä
We show that the automorphism group of a one-dimensional full shift (the
group of reversible cellular automata) does not satisfy the Tits alternative.
That is, we construct a finitely-generated subgroup which is not virtually
solvable yet does not contain a free group on two generators. We give
constructions both in the two-sided case (spatially acting group Z) and the
one-sided case (spatially acting monoid N, alphabet size at least eight).
Lack of Tits alternative follows for several groups of symbolic (dynamical)
origin: automorphism groups of two-sided one-dimensional uncountable sofic
shifts, automorphism groups of multidimensional subshifts of finite type with
positive entropy and dense minimal points, automorphism groups of full shifts
over non-periodic groups, and the mapping class groups of two-sided
one-dimensional transitive SFTs. We also show that the classical Tits
alternative applies to one-dimensional (multi-track) reversible linear cellular
automata over a finite field.
Kokoelmat
- Rinnakkaistallenteet [19207]