2021/07/13 by Ronnie Pavlov, Pavlov, Ronnie, Scott Schmieding +1 · 1 citation
Computer Science · #Cellular Automata and Applications #semigroups and automata theory #Coding theory and cryptography
paper · pdf · doi:10.48550/arxiv.2107.06062
We prove that for any transitive subshift X with word complexity function cn(X), if \liminf (log (cn(X)/n))/(log log log n) = 0, then the quotient group \textrmAut(X,σ) / ⟨ σ⟩ of the automorphism group of X by the subgroup generated by the shift σ is locally finite. We prove that significantly weaker upper bounds on cn(X) imply the same conclusion if the Gap Conjecture from geometric group theory is true. Our proofs rely on a general upper bound for the number of automorphisms of X of range n in terms of word complexity, which may be of independent interest. As an application, we are also able to prove that for any subshift X, if \fraccn(X)n2 (log n)-1 → 0, then \textrmAut(X,σ) is amenable, improving a result of Cyr and Kra. In the opposite direction, we show that for any countable infinite locally finite group G and any unbounded increasing f: ℕ → ℕ, there exists a minimal subshift X with \textrmAut(X,σ) / ⟨ σ⟩ isomorphic to G and (cn(X))/(nf(n)) → 0.