No Tits alternative for cellular automata

DOI10.4171/GGD/529zbMATH Open1456.20048arXiv1709.00858MaRDI QIDQ2286358FDOQ2286358

Authors: Yanyan Li 

Publication date: 22 January 2020

Published in: Groups, Geometry, and Dynamics (Search for Journal in Brave)

Abstract: 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 $$) 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.

Full work available at URL: https://arxiv.org/abs/1709.00858

Recommendations

• Groups and Monoids of Cellular Automata
• A Tits alternative for topological full groups
• Universal groups of cellular automata
• Topological rigidity of linear cellular automaton shifts
• On the automorphism groups of multidimensional shifts of finite type

zbMATH Keywords

cellular automataautomorphism groupsTits alternative

Mathematics Subject Classification ID

Geometric group theory (20F65) Groups as automorphisms of other structures (22F50) Symbolic dynamics (37B10) Dynamical aspects of cellular automata (37B15)

Cites Work

• The Tits alternative for \(\text{Out}(F_n)\). I: Dynamics of exponentially-growing automorphisms
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• The group of reversible Turing machines
• The dynamics of complex polynomials and automorphisms of the shift
• Topological full groups of minimal subshifts with subgroups of intermediate growth
• Tits alternatives for graph products
• The classification of reversible bit operations

Cited In (5)

• Universal groups of cellular automata
• Cold dynamics in cellular automata: a tutorial
• Gate lattices and the stabilized automorphism group
• On pointwise periodicity in tilings, cellular automata, and subshifts
• Nilpotent endomorphisms of expansive group actions

This page was built for publication: No Tits alternative for cellular automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2286358)