No Tits alternative for cellular automata

arXiv:1709.00858v3 [math.DS] 11 Jan 2018

Ville Salo
vosalo@utu.fi
January 12, 2018
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 (acting group Z) and
the one-sided case (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 twosided 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.

1

Introduction

In [49] Jacques Tits proved that if F is a field (with no restrictions on characteristic), then a finitely generated subgroup of GL(n, F ) either contains a free
group on two generators or contains a solvable subgroup of finite index. We say
that a group G satisfies the Tits alternative if whenever H is a finitely generated
subgroup of G, either H is virtually solvable or H contains a free group with
two generators. Whether an infinite group satisfies the Tits alternative is one
of the natural first questions to ask.
The fact that GL(n, F ) satisfies the Tits alternative implies several things:
• The ‘Von Neumann conjecture’, that a group is amenable if and only if it
contains no nonabelian free subgroup, is true for linear groups.1
• Linear groups cannot have intermediate growth. Generally known as the
Milnor problem [41].
• Linear groups have no infinite finitely generated periodic2 subgroups. Generally known as the Burnside problem [14].
1 Mentioned
2A

open by Day in [23].
group G is periodic, or torsion, if ∀g ∈ G : ∃n ≥ 1 : g n = 1.

1

The first item is true because solvable groups are amenable. The second
is true by the theorem of Milnor [41] and Wolf [52], which states that if G is
finitely generated and solvable then either G is virtually nilpotent or G has
exponential growth rate. The third is true because free groups are not periodic,
and solvable groups cannot have finitely generated infinite periodic subgroups
because locally finite groups are closed under group extensions.
These three properties (or lack thereof) are of much interest in group theory,
since in each case whether groups can have these ‘pathological properties’ was
open for a long time. It seems that none of the three have been answered for
automorphism groups of full shifts (equivalently, groups of reversible cellular
automata). We show that the classical Tits alternative is not enough to solve
the three questions listed – it is not true. Concretely, we show that there is a
residually finite variant of A5 ≀ Z which does not satisfy the Tits alternative and
embeds in the automorphism group of a full shift.
A (two-sided) full shift is ΣZ where Σ is a finite alphabet, with dynamics
of Z given by the shift σ : ΣZ → ΣZ defined by σ(x)i = xi+1 . A subshift is a
topologically closed shift-invariant subsystem of a full shift. A special case is a
sofic shift, a subsystem of a full shift obtained by forbidding a regular language
of words, and SFTs (subshift of finite type) are obtained by forbidding a finite
language. An endomorphism of a subshift is a continuous self-map of it, which
commutes with the shift. The automorphism group of a subshift X, denoted
by Aut(X), is the group of endomorphisms having (left and right) inverses, and
the automorphism group of a full shift is also known as the group of reversible
cellular automata. See [38] for precise definitions, [34] for definitions in the
multidimensional case, and [16] for subshifts on general groups. All these notions
have one-sided versions where N is used in place of Z. In the case of one-sided
subshifts we will only discuss full shifts ΣN .
As far as symbolic dynamics goes, automorphism groups of subshifts are a
classical topic [33, 19], with lots of progress in the 80’s and 90’s [12, 13, 37, 10]
especially in sofic settings, but also in others [35, 27]. In the last few (half a
dozen) years there has been a lot of interest in these groups [43, 48, 44, 21, 18,
22, 26, 25, 20] especially in settings where the automorphism group is, for one
reason or another, more restricted. Also the full shift/sofic setting, which we
concentrate on in this paper, has been studied in recent works [28, 45, 46, 3].
The popular opinion is that the automorphism group of a full shift is a
complicated and intractable object. However, with the Tits alternative (or the
three questions listed above) in mind, looking at known (published) finitely
generated subgroups as purely abstract groups does not really support this
belief. As far as the author knows, all that is known about the set of subgroups of
Aut(ΣZ ) for a nontrivial alphabet Σ follow from the facts that it is independent
of the alphabet, contains the right-angled Artin groups (graph groups) and
is closed under direct and free products (‘cograph products’) and finite group
extensions. See [13, 37, 45]. The author does not know whether all groups
generated by these facts satisfy the Tits alternative,3 but believes that if finite
group extensions are replaced with just containment of finite groups, this does
follow from the results of [2].
Some of the known (families of) groups which satisfy the Tits alternative are
3 More precisely, I do not know how finite extensions play together with graph products,
when the operations are alternated.

2

hyperbolic groups [31], outer automorphism groups of free groups [5], finitelygenerated Coxeter groups [42], and right-angled Artin groups and more generally groups obtained by graph products from other groups satisfying the Tits
alternative, under minor restrictions [2]. In particular, we obtain that the automorphism group of a full shift contains a finitely-generated subgroup which is
not embeddable in any such group.
Two particularly famous concrete examples of groups that do not satisfy
the Tits alternative are the Grigorchuk group [30] and Thompson’s group F
[15]. These groups also have many other interesting properties, so it would be
more interesting to embed them instead of inventing a new group for the task.
The Grigorchuk group can indeed be embedded in the automorphism group of
a subshift, by adapting the construction in [7], but the author does not know
whether it embeds in the automorphism group of a sofic shift. Thompson’s group
F embeds in the automorphism group of an SFT [47], but is not residually finite,
and thus does not embed in the automorphism group of a full shift. We mention
also that there are solvable groups of derived length three whose automorphism
groups do not satisfy the alternative [32].
The variant of A5 ≀ Z we describe is not a very complex group, and it is
plausible that some weaker variant of the Tits alternative holds in automorphism
groups of full shifts, and allows this type of groups in place of ‘virtually solvable
groups’. In particular, our group is elementarily amenable [17], and one could
ask whether every finitely generated subgroup of the automorphism group of
a mixing SFT is either elementarily amenable or contains a free nonabelian
subgroup. If this were the case, it would solve the Von Neumann, Milnor and
Burnside problems for automorphism groups of mixing SFTs.
The group we construct satisfies the law [g, h]30 , and is thus an example
of a residually finite group which satisfies a law, but does not satisfy the Tits
alternative. It turns out that such an example has been found previously [24,
Theorem 1], and we were delighted to find that indeed our example sits precisely
in the variety used in their theorem. However, our example is rather based on
an answer4 of Ian Agol on the mathoverflow website [36]. The idea behind
the embedding is based on Turing machines [3] in the two-sided case. In the
one-sided case we use a commutator trick applied to subshifts acting on finite
sets.

2

Results and corollaries

In the two-sided case, we obtain several results, all based on the same construction (Lemma 3) and the fact the automorphism group of the full shift embeds
quite universally into automorphism groups of subshifts.
In the statements, Σ and A are arbitrary finite alphabets.
Theorem 1. For any alphabet Σ, the group Aut(ΣZ ) of reversible cellular automata on the alphabet Σ does not satisfy the Tits alternative.
The following summarizes the (well-known) embeddings listed in Section 5,
and the corollaries for the Tits alternative.
4 The

answer reads ‘A5 ≀ Z’.

3

Theorem 3. Let G be an infinite finitely-generated group, and X ⊂ ΣG a
subshift. Then we have Aut(AZ ) ≤ Aut(X), and thus Aut(X) does not satisfy
the Tits alternative, if one of the following holds:
• G = Z and X is an uncountable sofic shift,
• G = Zd and X is a subshift of finite type with positive entropy and dense
minimal points.
• G is not periodic and X is a nontrivial full shift.
The first embedding is from [37, 45], the second is from [34].
The mapping class group of a subshift is defined in [9]. Combining the embedding theorem of [37, 45] and results of [9] (and a short additional argument)
gives the following.
Theorem 2. If X ⊂ ΣZ is a nontrivial transitive SFT, then Aut(AZ ) ≤ MX ,
and thus MX does not satisfy the Tits alternative.
Automorphisms of two-sided full shifts also appear in some less obviously
symbolic dynamical context, in particular the rational group Q of [29] contains
the automorphism group of a full shift, [51] constructs its classifying space
(more generally those of mixing SFTs), implementing it as the fundamental
group of a simplicial complex built out of integer matrices, and [50] ‘realizes’5
automorphisms of full shifts in the centralizer of a particular homeomorphism
of a sphere of any dimension at least 5.
In the case of one-sided SFTs, there are nontrivial restrictions on finite subgroups, and the group is generated by elements of finite order. The automorphism group of ΣN is not finitely generated if |Σ| ≥ 3, while |Aut({0, 1})N | = 2
[33, 11]. We prove that the Tits alternative also fails in the one-sided case.
Theorem 4. Let |Σ| ≥ 8. Then Aut(ΣN ) does not satisfy the Tits alternative.
Of course, this group embeds in Aut(ΣZ ), so Theorem 1 follows from Theorem 4. While Aut(ΣZ ) embeds in many situations where we have a symbolic
group action, Aut(ΣN ) embeds more generally in many monoid and (non-vertextransitive) graph contexts, though unlike in the case of Z, we are not aware of
anything concrete to cite.
The group Aut(ΣN ) also arises in a less obviously symbolic context: It is
shown in [6] that if Sd denotes the set of centered (coefficient of xd−1 is zero)
monic polynomials p of degree d over the complex numbers, such that the filledin Julia set (points whose iteration stays bounded) of p does not contain any
critical point, then π1 (Sd ) (the fundamental group of Sd as a subspace of Cd )
factors onto Aut({0, . . . , d − 1}N ). Unfortunately, the Tits alternative is not
closed under quotients (since free groups satisfy the Tits alternative trivially by
the Nielsen-Schreier theorem), so we do not directly get a corollary for π1 (Sd ).
5 While the precise statement in [50] is natural and interesting, it seems hard to get a nontrivial group-theoretic interepretation of this result just from the statement of the theorem: it
does follow that the automorphism group of a full shift is a subquotient of the homeomorphism
group of the sphere but since this group contains free groups, so is any other countable group.

4

3

Residually finite wreath product

Grigorchuk group and Thompson’s group F are presumably particularly famous
examples of groups not satisfying the Tits alternative mostly because they are
particularly famous for other reasons, and happen not to satisfy the Tits alternative – one can construct such examples directly by group extensions: A5 ≀ Z
does not satisfy the alternative by a similar proof as that of Lemma 2.
The group A5 ≀ Z is not residually finite since A5 is non-abelian, and thus
cannot be embedded in the automorphism group of a full shift. Informally, there
is an obvious way to ‘embed’ it, but this embedding is not quite a homomorphism, because the relations only hold on some ‘well-formed’ configurations. In
this section, we describe the abstract group obtained through this ‘embedding’
– a kind of broken wreath product. Luckily for us, it turns out not to satisfy
the Tits alternative either.
Let N ⊂ N be an infinite6 set, let G be a finite group and write G +N Z for
the group generated by the elements of G and a new element , which act on
S
n
n∈N G by
a · (g1 , g2 , . . . , gn ) = (ag1 , g2 , . . . , gn )
for a ∈ G and n ∈ N , and
· (g1 , g2 , . . . , gn ) = (g2 , g3 , . . . , gn , g1 ).
S
More precisely, the formulas attach a bijection on n∈N Gn to each a ∈ G and
to
(by the above formulas), and G +N Z is (up to isomorphism) the group
of bijections they generate. This is a variant of the usual wreath product of G
and Z, but G +N Z is obviously residually finite for any finite group G, since it
is defined by its action on the finite sets Gn . Note that
simply rotates (the
coordinates of) Gn for n ∈ N , and generates a copy of Z.
A subquotient of a group is a factor of a subgroup.
Lemma 1. Let G be a finitely generated group which has An5 as a subquotient
for infinitely many n. Then G is not virtually solvable.
Proof. Suppose it is. Then there is an index k solvable subgroup K ≤ G. Let
G1 ≤ G be a subgroup. Then [G1 : K ∩ G1 ] ≤ k and K is solvable. Let
h : G1 → G2 be a surjective homomorphism. Then for K ′ = h(K ∩ G1 ), we
have [G2 : K ′ ] ≤ [G1 : K ∩ G1 ] ≤ k. Because K ′ is a subquotient of the solvable
group K, it is solvable, and we obtain that any subquotient of G has a solvable
subgroup of index at most k.
The group An5 is now a subquotient of G for arbitrarily large (thus all) n,
so An5 has a solvable subgroup K ′ of index at most k. We claim that if n is
sufficiently large with respect to k, this is a contradiction. A simple argument for
n ≥ k being enough is that if there is some coordinate i such that K ′ projected
to that coordinate is surjective, then the non-solvable group A5 is a quotient of
K ′ , contradicting solvability of K ′ . If on the other hand in every coordinate the
projection of K ′ is a proper subgroup of A5 , then there are at least n + 1 cosets
of K ′ in An5 . (Actually there are exponentially many cosets in n.)
6 The definition works fine if N is a finite set, but then the group we define is finite, and
thus satisfies the alternative.

5

Lemma 2. If N ⊂ N is infinite, then the group A5 +N Z is not virtually solvable
and does not contain a free nonabelian group.
Proof. First observe that φ(a) = 0 for a ∈ G and φ( ) = 1 extends to a welldefined homomorphism φ : A5 +N Z → Z (where we use that N is infinite).
Suppose first that the free group F2 ≤ A5 +N Z is generated freely by g, h,
and N ⊂ N is arbitrary. Clearly on any An5 , [g, h] performs zero total rotation,
that is, φ([g, h]) = 0. Thus independently of n, we have [g, h]30 · ~v = ~v for any
n and ~v ∈ An5 , since the exponent of A5 is 30. This implies that g and h satisfy
a nontrivial relation, contradicting the assumption.7
So show that A5 +N Z is not virtually solvable, we need to show that it has
n
A5 as a subquotient for arbitrarily large n. We show it is a subgroup of a factor
(thus also a factor of a subgroup). Pick n ∈ N . Then A5 +N Z acts on An5 and
a momen’ts reflection shows that this induces a surjective homomorphism from
A5 ≀ Z/nZ to A5 ≀ Z/nZ. We have An5 ≤ A5 ≀ Z/nZ.
Since A5 acts faithfully on {1, 2, 3, 4, 5}, it is easy to see that the following
N
group (again defined
S by its action) nis isomorphic to A5 + Z: Let elements of
A5 and act on n∈N {1, 2, 3, 4, 5} by
a · (m1 , m2 , . . . , mn ) = (a(m1 ), m2 , . . . , mn )
for a ∈ A5 , and
· (m1 , m2 , . . . , mn ) = (m2 , m3 , . . . , mn , m1 ).

4

The construction in the two-sided case

If Σ is a finite alphabet, write Σ∗ for the set of words over Σ (including the
empty word).
Lemma 3. There exists an alphabet Σ such that we have A5 +2N Z ≤ Aut(ΣZ ).
Proof. Let A = {1, 2, 3, 4, 5} and choose Σ = {#} ∪ A2 . Before describing
the automorphism, we define an auxiliary faithful action of A5 +2N Z on finite
words. Think of a word w ∈ (A2 )n as two words u, v ∈ An on top of each
other, the topmost one defined by ui = (wi )1 and the second vi = (wi )2 , for
i = 1, 2, . . . , n. We use the notation w = [ uv ] = ([ uv11 ] , [ uv22 ] , . . . , [ uvnn ]). Define
a bijection ψ : (A2 )n → A2n by ψ([ uv ]) = uv R where v R is the reversal of v
defined by aR = a for a ∈ A and (va)R = a(v R ).
Now, conjugate the defining action of A5 +2N Z on A2n to (A2 )n through ψ
to obtain the action
i m 
h
 mn 
 m1   m2 
 mn 
a·m1
2
a · ( m′1 , m′2 , . . . , m′n ) = ( m′1 , m′2 , . . . , m′n )
for a ∈ A5 , and for

the following counter-clockwise ‘conveyor belt’ rotation
h ′ i
 m3   m4 
 mn 
 m1   m2 
mn
2
).
· ( m′1 , m′2 , . . . , m′n ) = ([ m
m1 ] , m′1 , m′2 , . . . , m′
n−1

7 Indeed

we have shown that the group satisfies a law, similarly as in [24, Theorem 1].

6

Now, we define our automorphisms. To a ∈ A5 we associate the automorphism fa : ΣZ → ΣZ defined by fa (x)i = Fa (xi−1 , xi ) where Fa : Σ2 → Σ is
defined by Fa (b, c) = c if b 6= #, Fa (#, #) = # and
Fa (#, [ cb ]) = [ a·b
c ]
where a · b, is the action of a ∈ A5 by permutation on b ∈ A. It is easy to see
that fa is an endomorphism of ΣZ , and xi = # ⇐⇒ fa (x)i = #.
To , we associate f : ΣZ → ΣZ defined by f (x)i = F (xi−1 , xi , xi+1 )i
where F : Σ3 → Σ is defined by F (a, #, b) = # for all a, b ∈ A2 and
F (#, [ dc ] , #) = [ dc ] ,
F (#, [ dc ] , [ fe ]) = [ ec ] ,
 
F ([ ab ] , [ dc ] , #) = db ,
F ([ ab ] , [ dc ] , [ fe ]) = [ eb ]

for all a, b, c, d, e, f ∈ A. It is easy to see that F is also an endomorphism of
ΣZ , and xi = # ⇐⇒ F (x)i = #.
Now, let Y ⊂ ΣZ be the set of points x where both the left tail x(−∞,−1] and
the right tail x[0,∞) contain infinitely many #-symbols, and consider any point
x ∈ Y . Then x splits uniquely into an infinite concatenation of words
x = . . . w−2 #w−1 #w0 #w1 #w2 . . .
where wi ∈ (A2 )∗ for all i ∈ Z. If f is either f or one of the fa for a ∈ A5 ,
then the decomposition of f (x) contains #s in the same positions as that of x,
in the sense that (up to shifting indices)
f (x) = . . . u−2 #u−1 #u0 #u1 #u2 . . .
where |ui | = |wi | for all i and the words begin in the same coordinates. Thus
f (x) ∈ Y . It is easy to see that between two #s, the mapping wi 7→ ui performed
by f is precisely the one we defined for words in (A2 )∗ described above for the
corresponding generator of A5 +2N Z.
It follows that a 7→ fa |Y ,
7→ f |Y extends uniquely to an embedding of
A5 +2N Z into the group of self-homeomorphisms of Y . Since Y is dense in ΣZ and
fa and f are endomorphisms of ΣZ , a 7→ fa , 7→ f extends to an embedding
of A5 +2N Z into Aut(ΣZ ).

5

Embedding results

In this section we list some embeddings from the literature. We start with
uncountable sofic shifts, where uncountable refers to the cardinality of the set
of points. Note that full shifts are uncountable sofic shifts (ΣN is uncountable,
and the empty language is regular).
The following is [45, Lemma 7].
Lemma 4. If X ⊂ ΣZ is an uncountable sofic shift, then Aut(AZ ) ≤ Aut(X)
for any alphabet A.

7

Proposition 1. If X is an uncountable sofic shift, then A5 +N Z ≤ Aut(X).
Proof. By Lemma 4, we have Aut(ΣZ ) ≤ Aut(X) where Σ is the alphabet of
Lemma 3. We have A5 +2N Z ≤ Aut(ΣZ ) by Lemma 3, so it is enough to check
that A5 +N Z ≤ A5 +2N Z. One can check that such an embedding is induced by
a 7→ a for a ∈ A5 , and 7→ 2 .
As for countable sofic shifts, we do not have a characterization of the situations when the automorphism group satisfies the Tits alternative. However, in
that setting, there are stronger methods for studying the three embeddability
questions listed in the introduction and we refer to [47].
The following is [34, Theorem 3].
d

Lemma 5. If X ⊂ ΣZ is an SFT with positive entropy and dense minimal
points, then Aut(AZ ) ≤ Aut(X) for any alphabet A.
Below, minimal points are points whose orbit-closure is minimal as a dynamical system.
Theorem 3. Let G be an infinite finitely-generated group, and X ⊂ ΣG a
subshift. Then we have Aut(AZ ) ≤ Aut(X), and thus Aut(X) does not satisfy
the Tits alternative, if one of the following holds:
• G = Z, X is an uncountable sofic shift,
• G = Zd , X is an SFT with positive entropy and dense minimal points, or
• G is not periodic, X is a nontrivial full shift.
Proof. The first two were proved above. The third item is true, because if
Z ≤ G by n 7→ g n and X = AG for A ⊂ Σ, then if K is a set of left cosets
representatives for hgi then f ∈ Aut(AZ ) directly turns into an automorphism
of AG by fˆ(x)kgn = f (y)n where yi = xkgi and k ∈ K.
The first item generalizes to sofic H × Z-shifts where H is finite by [46],
and could presumably be generalized to virtually-cyclic groups with the same
idea. By symmetry-breaking arguments, we believe the third item generalizes to
SFTs with a nontrivial point of finite support, on any group which is not locally
finite, and also to cellular automata acting on sets of colorings of undirected
graphs, but this is beyond the scope of the present paper. A generalization of
the second item seems worth conjecturing more explicitly.
Conjecture 1. Let G be an amenable group which is not locally finite and X
a subshift of finite type with positive entropy and dense minimal points. Then
we have Aut(AZ ) ≤ Aut(X) for any finite alphabet A.
Next, we deal with the mapping class group. By definition, the group hσi
is contained in the center of Aut(X) for any subshift X, in particular this is a
normal subgroup.
Lemma 6. Let X be any uncountable sofic shift. Then Aut(AZ ) ≤ Aut(X)/hσi
for every finite alphabet A.

8

Proof. Let φ : Aut(AZ ) ≤ Aut(X) be the embedding given by Lemma 4. From
its proof in [45], it is easy to see that there exists an infinite subshift Y ≤ X
such that φ(f ) fixes every point in Y for every f ∈ Aut(AZ ); namely the maps
φ(f ) only act nontrivially at a bounded distance from an unbordered word w
which can taken to be arbitrarily long.
We show that based on only this, φ is automatically also an embedding of
Aut(AZ ) into Aut(X)/hσi. Suppose not, and that φ(f ) ◦ σ k = φ(g) for some
f, g ∈ Aut(AZ ). Then in particular φ(f ) ◦ σ k (y) = φ(g)(y) =⇒ σ k (y) = y
for every y ∈ Y . If k 6= 0 this is a contradiction since Y is an infinite subshift.
If k = 0, then φ(f ) = φ(g) implies f = g since φ : Aut(AZ ) → Aut(X) is an
embedding.
The following is now a straightforward corollary of [9]. See [9] for the definition of the mapping class group MX of a subshift X (which is not needed in
the proof).
Lemma 7. Let X be any transitive SFT. Then Aut(AZ ) ≤ MX for every
alphabet A.
Proof. In [9, Theorem 5.6], it is shown in particular that if X is a transitive
SFT, then its mapping class group contains an isomorphic copy of Aut(X)/hσi,
which then contains a copy of Aut(AZ ) by the above lemma.
In [29, Corollary 5.5], it is shown that the automorphism group of every
full shift embeds in the group Q that they define, sometimes called the rational group. Thus we also obtain a new proof that Q does not satisfy the Tits
alternative.

6

One-sided automorphism groups

The automorphism group of the full shift {0, 1}N is isomorphic to Z2 . For large
enough alphabets, however, we show that Aut(ΣN ) does not satisfy the Tits
alternative. This gives another proof of Theorem 1.
The high-level idea of the proof is that we can associate to a subshift a
kind of action of it on a finite set, in a natural way. Mapping n 7→ (0n−1 1)Z ,
the action of the subshift generated by the image of N ⊂ N corresponds to the
group A5 +N Z defined previously. It turns out that Lemma 2 generalizes to such
actions, and any infinite subshift can be used in place of this (almost) periodic
subshift. The generalization is based on a commutator trick from [4, 40, 1, 8, 3].
The trick to adapting the construction to cellular automata on N is to consider
‘actions of the trace of another cellular automaton’.
We only give the definitions in the special case of A5 and binary subshifts.
Let X ⊂ {0, 1}Z be a subshift and let Y = {1, 2, 3, 4, 5}. For each g ∈ A5 and
j ∈ {0, 1} define a bijection gj : Y × X → Y × X by gj (y, x) = (g · y, x) for
x0 = j and gj (y, x) = (y, x) for x0 6= j. Define a bijection
y Y × X by
(y, x) = (y, σ(x)). Denote the group generated by these maps by A5 +X Z.
Lemma 8. Let X ⊂ {0, 1}Z be infinite. Then the group A5 +X Z is not virtually
solvable and does not contain a free nonabelian group.

9

Proof. Observe that φ(g) = 0 for g ∈ A5 and φ( ) = 1 extends to a welldefined homomorphism φ : A5 +X Z → Z (since X is infinite). Suppose first
that F2 ≤ A5 +N Z is generated freely by g, h. Then as in Lemma 2, we get
φ([g, h]) = 0, and again we have [g, h]30 · (y, x) = (y, x).
We now show that An5 is a subgroup of A5 +X Z for arbitrarily large n, and
the claim follows from Lemma 1.
Consider the cylinder sets [w]i = {x ∈ {0, 1}Z | x[i,i+|w|−1] = w} and for
g ∈ A5 , w ∈ {0, 1}∗ and i ∈ Z define
πg,i,w (y, x) = (gy, x) if x ∈ [w]i , and πg,i,w (y, x) = (y, x) otherwise.
We claim that πg,i,w ∈ A5 +X Z for all g, i, w. To see this, observe that by the
definition of how g0 , g1 ∈ A5 act on Y × X, and by conjugating with , we have
πg,w,i ∈ A5 +X Z for all g ∈ A5 , i ∈ Z and w ∈ {0, 1}. We proceed inductively
on |w|: Let w = uv where u, v ∈ {0, 1}+ are nonempty words, and let a ∈ A5
be any commutator, that is, a = [b, c]. Then one sees easily that
[πb,i,u , πc,i+|u|,v ] = π[b,c],i,w .
Because A5 is perfect (that is, A5 = [A5 , A5 ]), we get that πg,i,w ∈ A5 +X Z for
every g ∈ A5 . This proves the claim.
Now, let w be an unbordered word8 of length n [39] that occurs in some point
of X. Then the elements πg,i,w for 0 ≤ i < |w| generate a group isomorphic to
An5 (because the fact w is unbordered implies the supports of their actions are
disjoint), and we conclude.
Theorem 4. Let |Σ| ≥ 8. Then Aut(ΣN ) does not satisfy the Tits alternative.
Proof. Let Σ = Y ⊔ A ⊔ B where A, B are finite sets, |A| ≥ 3 and |Y | = 5.
Let f : ΣN → ΣN be any reversible cellular automaton of infinite order such
that xi ∈ A ⇐⇒ f (x)i ∈ A and xi ∈
/ A =⇒ f (x)i = xi . One construction is
the following: for a, b ∈ A, a 6= b, define Fa,b : Σ2 → Σ by
for all c ∈
/ {a, b} : Fa,b (a, c) = b and Fa,b (b, c) = a
and Fa,b (c, d) = c otherwise. Define fa,b ∈ Aut(ΣN ) by fa,b (x)0 = Fa,b (x0 , x1 ).
This is an involution, so it is an automorphism. Now it is easy to check that for
any distinct elements a, b, c ∈ A, fa,b ◦ fb,c is of infinite order, by considering its
action on any point that begins with the word bk a.
The trace of f is the subshift of ΣZ consisting of y such that for some x ∈ ΣN ,
n
f (x)0 = yn for all n. Since f is of infinite order on ΣN and fixes all symbols
not in A, its trace Tf intersected with AZ is infinite. Let π : A → {0, 1} be a
function, and extend it to π : AZ → {0, 1}Z in the obvious way. Pick π so that
the subshift X = π(Tf ∩ AZ ) is infinite. This is possible because if the indicator
function of some symbol gives a finite subshift, then this symbol appears with
a fixed period in every point, so if all indicator functions give finite subshifts,
every point can be described by a finite amount of data.
For each permutation p ∈ A5 and i ∈ {0, 1}, take the fp,i to be the automorphism defined by fp,i (x)0 = p(x0 ) if x0 ∈ Y , x1 ∈ A and π(x1 ) = i, and by
fp,i (x)0 = x0 otherwise.
8 Alternatively,

one can use the Marker Lemma [38] for X.

10

One can now check that f and fp,i for p ∈ A5 , i ∈ {0, 1} together generate a
group isomorphic to A5 +X Z, and by the previous lemma, this group does not
satisfy the Tits alternative.
Question 1. For which one-dimensional transitive SFTs does the Tits alternative hold? Is it always false when the automorphism group is infinite?
Unlike in the two-sided case, automorphism groups of one-sided full shifts
do not in general embed into each other, due to restrictions on finite subgroups,
see [11].

7

Tits alternative for linear cellular automata

We show that linear cellular automata, with a suitable definition, satisfy the
assumptions of Tits’ theorem directly.
Let K be a finite field and let V be a finite-dimensional vector space over
K. Then the full shift V Z is also a vector space over K with cellwise addition
(x + y)i = xi + yi and cellwise scalar multiplication (a · x)i = a · xi . Consider the
semigroup LEnd(V Z ) of endomorphisms f of the full shift V Z which are also
linear maps, i.e. f (x + y) = f (x) + f (y), a · f (x) = f (a · x), and the group
LAut(V Z ) ≤ LEnd(V Z ) of such maps which are also automorphisms (in which
case the automorphism is automatically
linear as well).
P
The (formal) Laurent series i∈Z ci xi , where ci ∈ K for all i and ci = 0 for
all small enough i, form a field that we denote by K((x)). By GL(n, K((x)))
we denote the group of linear automorphisms of the vector space K((x))n over
K((x)). A Laurent polynomial is a Laurent series with finitely many nonzero
coefficients ci , and we write K[x, x−1 ] for this subring of K((x)). In addition
to being a vector space over K((x)), K((x))n is a module over K[x, x−1 ] and
a vector space over K (by simply restricting the scalar field).
Lemma 9. If V is an n-dimensional vector space over the finite field K, the
semigroup LEnd(V Z ) is isomorphic to the semigroup Mn (K[x, x−1 ]) of n-byn matrices over the ring K[x, x−1 ]. The group LAut(V Z ) corresponds to the
invertible matrices in this isomorphism.
Proof. We may assume V = K n . Let X be the set of points x ∈ (K n )Z such that
n Z
x−i = 0n for all but finitely many i. Note that this is a subspace of (K
P ) for the
−1 n
K-linear structure. Define a map φ : X → K[x, x ] by φ(x)j = i∈Z (xi )j xi ,
and observe that this is an isomorphism of the vector spaces X and K[x, x−1 ]n
over K.
Suppose first that f : (K n )Z → (K n )Z is a linear CA, i.e. K-linear, continuous and shift-commuting. Then we see that the images of ei ∈ (K n )Z defined
by ((ei )0 )j = δij (where δab = 1 if a = b, δab = 0 otherwise) determine f completely. If some f (ei ) has infinitely many nonzero coordinates, then it is easy
to see that f is not continuous at (0n )Z . One can then directly work out the
matrix representation for φ ◦ f |X ◦ φ−1 from the images f (ei ), observing that
applying the left shift σ corresponds to scalar multiplication by x−1 . Since X
is dense in (K n )Z , f is completely determined by f |X , so this representation as
a matrix semigroup is faithful.
By inverting the construction, every matrix arises from the local rule of some
cellular automaton. The claim about invertible matrices is straightforward.
11

The following is obvious.
Lemma 10. The group of invertible matrices in Mn (K[x, x−1 ]) embeds in
GL(n, K((x))).
Combining the lemmas, we get that LAut(V Z ) is a linear group over a finitedimensional vector space. The result of [49] now directly applies.
Theorem 5. Let V be a finite-dimensional vector space over a finite field K.
Then the group LAut(V Z ) satisfies the Tits alternative.
The author does not know if the group of (algebraic) automorphisms of a
one-dimensional group shift always satisfies the Tits alternative.

Acknowledgements
The author thanks Ilkka Törmä for his comments on the paper, and especially
for suggesting a much simpler embedding in the two-sided case. The author
thanks Johan Kopra for pointing out several typos in the first public draft. The
last section arose from discussions with Pierre Guillon and Guillaume Theyssier.
The question of Tits alternative for cellular automata was proposed by Tom
Meyerovitch.

References
[1] Scott Aaronson, Daniel Grier, and Luke Schaeffer. The classification of
reversible bit operations. Electronic Colloquium on Computational Complexity, (66), 2015.
[2] Yago Antolı́n. Tits Alternatives for Graph Products, pages 1–5. Springer
International Publishing, Cham, 2014.
[3] Sebastián Barbieri, Jarkko Kari, and Ville Salo. The Group of Reversible
Turing Machines, pages 49–62. Springer International Publishing, Cham,
2016.
[4] David A. Barrington. Bounded-width polynomial-size branching programs
recognize exactly those languages in NC1. Journal of Computer and System
Sciences, 38(1):150 – 164.
[5] Mladen Bestvina, Mark Feighn, and Michael Handel. The Tits alternative
for out(Fn ) I: Dynamics of exponentially-growing automorphisms. Annals
of Mathematics, 151(2):517–623, 2000.
[6] Paul Blanchard, Robert L. Devaney, and Linda Keen. The dynamics of
complex polynomials and automorphisms of the shift. Inventiones mathematicae, 104(1):545–580, Dec 1991.
[7] Nicols Matte Bon. Topological full groups of minimal subshifts with subgroups of intermediate growth. Journal of Modern Dynamics, 9(01):67–80,
2015.

12

[8] Tim Boykett, Jarkko Kari, and Ville Salo. Strongly Universal Reversible
Gate Sets, pages 239–254. Springer International Publishing, Cham, 2016.
[9] M. Boyle and S. Chuysurichay.
The Mapping Class Group of a
Shift of Finite Type.
ArXiv e-prints, April 2017.
Available at
https://arxiv.org/abs/1704.03916.
[10] Mike Boyle and Ulf-Rainer Fiebig. The action of inert finite-order automorphisms on finite subsystems of the shift. Ergodic Theory and Dynamical
Systems, 11(03):413–425, 1991.
[11] Mike Boyle, John Franks, and Bruce Kitchens. Automorphisms of one-sided
subshifts of finite type. Ergodic Theory Dynam. Systems, 10(3):421–449,
1990.
[12] Mike Boyle and Wolfgang Krieger. Periodic points and automorphisms of
the shift. Transactions of the American Mathematical Society, 302(1):pp.
125–149, 1987.
[13] Mike Boyle, Douglas Lind, and Daniel Rudolph. The automorphism group
of a shift of finite type. Transactions of the American Mathematical Society,
306(1):pp. 71–114, 1988.
[14] William Burnside. On an unsettled question in the theory of discontinuous
groups. Quart. J. Pure Appl. Math, 33(2):230–238, 1902.
[15] James W. Cannon, William J. Floyd, and Walter R. Parry. Introductory notes on Richard Thompson’s groups. Enseignement Mathématique,
42:215–256, 1996.
[16] T. Ceccherini-Silberstein and M. Coornaert. Cellular Automata and
Groups. Springer Monographs in Mathematics. Springer-Verlag Berlin Heidelberg, 2010.
[17] Ching Chou. Elementary amenable groups. Illinois J. Math., 24(3):396–
407, 09 1980.
[18] E. Coven and R. Yassawi. Endomorphisms and automorphisms of minimal
symbolic systems with sublinear complexity. ArXiv e-prints, November
2014. Available at https://arxiv.org/abs/1412.0080.
[19] Ethan M Coven. Endomorphisms of substitution minimal sets. Probability
Theory and Related Fields, 20(2):129–133, 1971.
[20] V. Cyr, J. Franks, B. Kra, and S. Petite. Distortion and the automorphism
group of a shift. ArXiv e-prints, November 2016.
[21] V. Cyr and B. Kra.
The automorphism group of a shift of
subquadratic growth.
ArXiv e-prints, March 2014.
Available at
https://arxiv.org/abs/1403.0238.
[22] V. Cyr and B. Kra. The automorphism group of a minimal shift of stretched
exponential growth. ArXiv e-prints, September 2015.

13

[23] Mahlon M. Day. Amenable semigroups. Illinois J. Math., 1(4):509–544, 12
1957.
[24] Yves de Cornulier and Avinoam Mann. Some Residually Finite Groups
Satisfying Laws, pages 45–50. Birkhäuser Basel, Basel, 2007.
[25] S. Donoso, F. Durand, A. Maass, and S. Petite. On automorphism groups
of Toeplitz subshifts. ArXiv e-prints, January 2017.
[26] Sebastian Donoso, Fabien Durand, Alejandro Maass, and Samuel Petite.
On automorphism groups of low complexity subshifts. Ergodic Theory and
Dynamical Systems, 36(01):64–95, 2016.
[27] Doris Fiebig and Ulf-Rainer Fiebig. The automorphism group of a coded
system. Transactions of the American Mathematical Society, 348(8):3173–
3191, 1996.
[28] J. Frisch, T. Schlank, and O. Tamuz. Normal amenable subgroups of the
automorphism group of the full shift. ArXiv e-prints, December 2015.
Available at https://arxiv.org/abs/1512.00587.
[29] Rostislav I Grigorchuk, Volodymyr V Nekrashevich, and Vitali I Sushchanskii. Automata, dynamical systems and groups. In Proc. Steklov Inst. Math,
volume 231, pages 128–203, 2000.
[30] R. I. Grigorčuk. On Burnside’s problem on periodic groups. Funktsional.
Anal. i Prilozhen., 14(1):53–54, 1980.
[31] Mikhael Gromov. Hyperbolic groups. Essays in group theory, 8(75-263):2,
1987.
[32] Brian Hartley. A conjecture of Bachmuth and Mochizuki on automorphisms
of soluble groups. Canad. J. Math, 28:1302–1310, 1976.
[33] Gustav A. Hedlund. Endomorphisms and automorphisms of the shift dynamical system. Math. Systems Theory, 3:320–375, 1969.
[34] Michael Hochman. On the automorphism groups of multidimensional shifts
of finite type. Ergodic Theory Dynam. Systems, 30(3):809–840, 2010.
[35] B. Host and F. Parreau. Homomorphismes entre systèmes dynamiques
définis par substitutions. Ergodic Theory and Dynamical Systems, 9:469–
477, 8 1989.
[36] Ian Agol (https://mathoverflow.net/users/1345/ian agol).
Which
group does not satisfy the tits alternative?
MathOverflow.
URL:https://mathoverflow.net/q/38775 (version: 2010-09-16).
[37] K. H. Kim and F. W. Roush. On the automorphism groups of subshifts.
Pure Mathematics and Applications, 1(4):203–230, 1990.
[38] Douglas Lind and Brian Marcus. An introduction to symbolic dynamics
and coding. Cambridge University Press, Cambridge, 1995.

14

[39] M. Lothaire. Algebraic combinatorics on words, volume 90 of Encyclopedia
of Mathematics and its Applications. Cambridge University Press, Cambridge, 2002.
[40] Hiroki Matui. Some remarks on topological full groups of cantor minimal
systems. International Journal of Mathematics, 17(02):231–251, 2006.
[41] John Milnor. Growth of finitely generated solvable groups. J. Differential
Geom., 2(4):447–449, 1968.
[42] Guennadi A. Noskov and Èrnest B. Vinberg. Strong Tits alternative for
subgroups of Coxeter groups. Journal of Lie Theory, 12(1):259–264, 2002.
[43] Jeanette Olli. Endomorphisms of sturmian systems and the discrete chair
substitution tiling system. Dynamical Systems, 33(9):4173–4186, 2013.
[44] Ville Salo.
Toeplitz subshift whose automorphism group is not
finitely generated.
ArXiv e-prints, November 2014.
Available at
https://arxiv.org/abs/1411.3299.
[45] Ville Salo. A note on subgroups of automorphism groups of full shifts.
ArXiv e-prints, July 2015.
[46] Ville Salo. Transitive action on finite points of a full shift and a finitary
Ryan’s theorem. ArXiv e-prints, October 2016. Accepted in Ergodic Theory
and Dynamical Systems.
[47] Ville Salo and Michael Schraudner. Automorphism groups of subshifts
through group extensions. Preprint.
[48] Ville Salo and Ilkka Törmä. Block Maps between Primitive Uniform and
Pisot Substitutions. ArXiv e-prints, June 2013.
[49] Jacques Tits. Free subgroups in linear groups. Journal of Algebra, 20(2):250
– 270, 1972.
[50] J. B. Wagoner. Realizing symmetries of a subshift of finite type by homeomorphisms of spheres. Bull. Amer. Math. Soc. (N.S.), 14(2):301–303, 04
1986.
[51] J. B. Wagoner. Triangle identities and symmetries of a subshift of finite
type. Pacific J. Math., 144(1):181–205, 1990.
[52] Joseph A. Wolf. Growth of finitely generated solvable groups and curvature
of Riemanniann manifolds. J. Differential Geom., 2(4):421–446, 1968.

15

