Ville Salo
email: vosalo@utu.fi

Groups and monoids of cellular automata

Keywords: automorphism groups, cellular automata, subshifts

We discuss groups and monoids defined by cellular automata on full shifts, sofic shifts, minimal subshifts, countable subshifts and coded and synchronized systems. Both purely group-theoretic properties and issues of decidability are considered.

Motivation

1.1 From CA to monoid actions Consider a system (X, f ) with a (discrete) time-evolution rule f : X → X. The set X is thought of as the set of all possible states of the system, and f tells us how the system evolves as time progresses. If the system is currently in state x ∈ X, it will be in state f (x) after one time step. Systems that fit this general picture are studied in physics as models of the real world, in computer science as models of computation, and in mathematics for their intrinsic interest. In the world of cellular automata (CA), X is typically the set of bi-infinite sequences over a finite alphabet, and f is a cellular automaton on this space. 1Questions we ask about such systems can be both dynamical and computational (or a combination of the two). When X has a topological or measurable structure, often the motivating question on the side of dynamics is how 'chaotic' the system is. Trying to understand what is chaotic about a system leads to the study of properties such as transitivity, mixing and entropy. The study of what is not chaotic about it leads to the study of periodicity, almost periodicity, equicontinuous factors and spectral theory. For cellular automata, a range of different behaviors are known to be possible. Another common motivating question on the side of both dynamics and computation is whether the system is 'universal'. We wish to understand which other systems our system can simulate, in one sense or another.

A particularly interesting case in all these considerations is when f is reversible, that is, no information is lost when f is applied. Typically, we are interested in a strong, structural kind of reversibility where there is a concrete inverse time-evolution rule g : X → X such that f • g and g • f are identity maps on X. The importance of reversibility in physics is that the laws of nature seem to be reversible, and thus it makes sense to make such an assumption on our models. In computer science, reversible computation is an interesting programming paradigm promising challenges for theoreticians, but also allows more energy-efficient computation. In mathematics, reversibility often makes systems more malleable to the development of theory.

Now, what happens if we have two rules? Suppose f : X → X and g : X → X are two evolution rules on X, that is, we have two transformations on X which we be applied in any order. This can model many situations. For example, we can apply f and g at random, so that X has two ways to evolve at each time step, and we want to understand what the limit behavior is likely to be. This is a very simple example of a (discrete) random dynamical system. In parallel computing, we can think of f and g as two computations that are happening in parallel, and we need to understand their interaction to know the good or legal orders to apply them in. In this case, the order in which the maps are applied might be chosen by an adversary. The reversibility of a system with two evolution rules can be defined as simply f and g being reversible: it automatically follows that every finite composition of f and g is reversible, as one can apply the inverses of f and g in the reverse order to undo their actions. 2Abstracting from this, in the not necessarily reversible case we obtain the mathematical concept of a monoid action, where instead of a single function on X, we have a countable discrete monoid M acting on X by functions. More precisely, we associate to each m ∈ M a function φ m : X → X, and write m • x = φ m (x) for short. We require that the obvious compatibility conditions m • m • x = mm • x and 1 • x = x hold. The systems (X, f ) with a single timeevolution rule are modeled by setting M = N, and n • x = f n (x) for all n ∈ N. The systems with two evolution rules are most generally modeled by setting M to be the free monoid3 with two generators a, b and defining the action of M on X by a • x = f (x) and b • x = g(x).

When the operations are reversible, we usually consider group actions instead, 4 that is, we choose the monoid M to have multiplicative inverses (so that it is a group). A group action should of course have the additional compatibility condition that the inverse g -1 of g ∈ G undoes the action of g on every element. This is automatic: if a ∈ M and a -1 ∈ M is its inverse (that is, aa -1 = a -1 a = 1), then the action of a -1 ∈ M is automatically the inverse of the action a ∈ M by the compatibility condition for the monoid action:

a • (a -1 • x) = aa -1 • x = 1 • x = x = a -1 a • x = a -1 • (a • x).
Thus, the natural compatibility conditions for a group action are the same as for a monoid action. If we have a single reversible time-evolution rule f , we obtain a natural action of Z by the same formula as in the non-reversible case, but extending to negative powers in the obvious way. In the case of two reversible actions, we obtain an action of the free group on two generators (see Section 2), again by the same formula. Considering the element 1 ∈ N or 1 ∈ Z, the same formula shows that actions of N and Z are in one-to-one correspondence with systems with a time-evolution rule, and ones with a reversible time-evolution rule, respectively.

For most of the notions for N-actions and Z-actions, such as expansivity, transitivity, entropy and almost equicontinuity, there exist one or more corresponding notions that apply more generally to monoid or group actions. For example, one-dimensional expansivity for Z-actions is defined by the formula ∃ > 0 : ∀x, y ∈ X : ∃n ∈ Z : d(f n (x), f n (y)) > . The formula defining expansivity for a general monoid is obtained by replacing Z by the monoid and f n by the action of n. Sometimes additional conditions are needed on the monoid for the definition to work. For example, the entropy of a group action is measured along a Følner sequence, and thus requires amenability. 5The generalization allows us to ask what the dynamics of a finite (or even infinite) set of cellular automata looks like. We can choose a set of cellular automata F , let them generate a free monoid or group, and investigate the properties of the corresponding action. We can also fix the monoid to be M , and ask what M -actions of cellular automata look like. For example, it is known that the entropies of N-actions by cellular automata on one-dimensional full shifts are precisely the class Π 1 of positive real numbers [START_REF] Guillon | Densities and entropies in cellular automata[END_REF]. What is the corresponding class for N 2 -actions of cellular automata (given by two CA f and g satisfying f • g = g • f )? For Z-actions? 6 1.2 From monoid actions to the endomorphism monoid Now, let us return to the simple systems (X, σ) with a single time-evolution rule and suppose now that X is a compact Hausdorff space, and σ : X → X is continuous. It turns out that there is a monoid that one can attach to any such system: let End(X) 7 be the set of all continuous functions f : X → X such that σ • f = f • σ (as functions). Then End(X) becomes a monoid, called the endomorphism monoid, under function composition. We define Aut(X), the automorphism group, as the restriction of End(X) to the elements which are bijective. From the assumption that X is compact and Hausdorff, it follows that every bijective continuous function on X has a continuous inverse. Since the inverse is easily seen to also commute with σ, Aut(X) is indeed a group under function composition. The endomorphism monoid and the automorphism group act on X in the obvious way:

f • x = f (x).
This gives another way to see the set of cellular automata on a full shift: Let X = S Z and let σ : X → X be the left shift map defined by σ(x) i = x i+1 . Then End(X) is precisely the set of cellular automata on X: the continuous shift-commuting maps are precisely the ones admitting a spatially uniform local rule. Thinking of cellular automata as elements of the endomorphism monoid, and considering its action on X, we get a more global way to look at cellular automata, as this point of view encompasses not only the possible dynamics and computational power of individual cellular automata, but also their possible interactions.

In this paper we take a very simplified approach to this interaction, by forgetting the action of End(X) on X. Thus, we are interested in the abstract structure of the monoid End(X), and in particular the group Aut(X). This omits many interesting questions -for example, chaoticity or universality of a cellular automaton or a family of cellular automata does not (to our knowledge) in any way differentiate it among the other elements of End(X).8 All that matters is which equalities

f n • f n-1 • • • • • f 1 = g m • g m-1 • • • • • g 1 hold,
when f i and g i are cellular automata. In the case of groups, it only matters which compositions of cellular automata are equal to the identity map on X.

While dynamical properties are out of the question, there are many things we can ask: For any property of groups (of which there are many), we can ask if Aut(X) has this property. Is it abelian? Is it amenable? For many group-theoretic decidability questions (of which there are many) we can ask if the question is decidable for Aut(X). Is the word problem decidable? What about the torsion problem? We can also ask if there are alternative descriptions of Aut(X), or connections with previously known groups.

It turns out that many interesting things can be said when X is a full shift over an alphabet S of size at least 2: For example, every finite group can be embedded in Aut(X), as can Z and free groups with a countable number of generators [START_REF] Hedlund | Endomorphisms and automorphisms of the shift dynamical system[END_REF][START_REF] Boyle | The automorphism group of a shift of finite type[END_REF]. On the other hand, this group is residually finite and has a decidable word problem.

Fixing the action σ on S Z makes it natural to consider also subshifts X ⊂ S Z , where we forbid a possibly infinite set of finite words from appearing in points of S Z . There are uncountably many subshifts X, and to each we associate the monoid End(X) and the group Aut(X), which act on X by function application. On each subshift X, End(X) still corresponds to the usual cellular automata, defined by a local rule; of course, it may be hard or impossible to tell which local rules give a well-defined map on X.

It turns out that the known constructions on full shifts can be carried out in many subshift X under some chaoticity assumptions on the action of the shift map on X. In fact, we show in Section 3 that we can embed the automorphism group of a full shift in many subshifts, such as all positive entropy sofic shifts [START_REF] Boyle | The automorphism group of a shift of finite type[END_REF]. In Section 6, we show that similar constructions, and much more, can be carried out on the larger classes of synchronized and coded systems -in particular on coded systems we obtain a large set of groups as automorphism groups [START_REF] Fiebig | The automorphism group of a coded system[END_REF].

We also show examples of subshifts on which the automorphism group is essentially smaller, and some ways to control this. In Section 5 we discuss some interesting recent results in the case where either the word complexity grows slowly or recurrence times are short. In particular, in the case of subshifts with linear word complexity (for example, ones generated by primitive substitutions), we seem to be very close to a full understanding of the set of automorphism groups. In the case of countable sofic shifts, the author is working on the characterization of the automorphism groups, and we give an example of such a computation in Section 4.

Remark 1. Since, on the full shift, Ryan's theorem guarantees that there is an algebraic way to separate the shift map from the others (as it is the center of the group), we have no need to carry it in the structure Aut(X) explicitly. However, this is not true in general, as for example in minimal and coded systems we can have large abelian automorphism groups (so the group is its own center). In this case, it makes sense to think of σ as part of the algebraic structure, and consider for example the group Aut(X)/ σ instead of Aut(X). This simplifies many problems, as for example the characterization of these groups is known in the linear word complexity case.

Definitions and basic results

We give basic definitions of dynamical systems. In particular for the case of subshifts with Z-actions, some standard references are [START_REF] Kůrka | Topological and symbolic dynamics[END_REF][START_REF] Lind | An introduction to symbolic dynamics and coding[END_REF][START_REF] Bruce | Symbolic dynamics -One-sided, two-sided and countable state Markov shifts[END_REF].

By a dynamical (M -)system we mean a pair (X, M, φ) where X is a compact metric zero-dimensional space, M is a countable discrete monoid, and M acts on X by φ m : X → X for m ∈ M , that is,

φ 1 (x) = x and ∀m, m ∈ M : φ m•m (x) = φ m (φ m (x)).
Usually, the action is left implicit, and we write simply (X, M ) for the system and m • x for φ m (x). Of particular interest to us are the subshifts (X, Z d , σ), topologically closed sets X ⊂ S Z d which are invariant under the shifts σ v defined by σ v (x) w = x w+v , where S is some finite alphabet. The subshift S Z d is called the full shift (over S). A subshift X ⊂ S Z d is a dynamical system with a Z daction given by the shifts. If d is not specified, we by default study the onedimensional setting where d = 1, that is, the set S Z of two-way infinite sequences, and explicitly state when studying the multidimensional case d > 1.

In the one-dimensional case,9 subshifts are characterized as sets of sequences in a full shift where none of a (possibly infinity) set of forbidden words occurs. Yet another characterization is the following: Let L ⊂ S * be a set of words over S. We say L is extendable if ∀w ∈ L : ∃a, b ∈ S : awb ∈ L. The factor-closure of L is the set F (L) = {u ∈ S * | ∃v, v ∈ S * : vuv ∈ L}. Subshifts are precisely the sets of infinite words whose finite subwords belong to the factor-closure of a fixed extendable language. Thus, if L is extendable, we define

L -1 (L) = {x ∈ S Z | ∀a, b : x [a,b] ∈ F (L)}.
We write L(X) for the language of X, that is, the set of words occurring in X. It is always factor closed, and L(L -1 (L)) = F (L) and L -1 (L(X)) = X for an extendable language L and a subshift X. We write L n (X) = L(X) ∩ S n .

A sofic shift is a subshift that can be defined by a regular language of forbidden words, or alternatively as L -1 (L) for an extendable regular language L. An SFT is a subshift that can be defined by a finite set of forbidden words.

The endomorphism monoid of a subshift consists of the continuous functions on X which commute with the translations:

End(X) = {f : X → X | f continuous and ∀v ∈ Z k : σ v • f = f • σ v }.
We give End(X) the structure of a monoid by function composition (f, g) → f • g. The monoid End(X) acts on X from the left by f • x = f (x), and thus (X, End(X)) is itself a dynamical system. We are interested in the following family of questions:

Question 1. What can we say about End(X) as a monoid and Aut(X) as a group by looking at properties of X? What can we say about X by looking at properties of End(X) (or Aut(X))?

We emphasize in particular the automorphism group, since it is often easier to understand than the endomorphism monoid, and since there is more literature on it. For any property of groups, and any subshift X, we can ask if Aut(X) has the property. Some notions we need, mainly for Z-subshifts, are the following: (X, σ) is transitive if there exists a transitive point, that is, a point x ∈ X such that n∈Z σ n (x) = X. If every point is transitive, the system is minimal, equivalently, it has no proper subsystems except the empty one.

In terms of words, a minimal subshift is one where every word occurs with bounded gaps, that is, in every long enough word that occurs in a point of the subshift. Transitivity means ∀u, v ∈ L(X) :

∃w : uwv ∈ L(X). A subshift X ⊂ S Z is mixing if ∀u, v ∈ L(X) : ∃n : ∀m ≥ n : ∃w ∈ L m (X) : uwv ∈ L(X).
The entropy of a subshift X is lim n→∞ log |Ln(X)| n .

Properties and examples of groups

For a group G, we can ask which kind of subshifts (if any) can have it as an automorphism group, or can have an embedded copy of it in the automorphism group. Similarly, each property of groups gives a family of questions about automorphism groups subshifts: Does there exist a subshift whose automorphism group has that property? Does one exist in a particular class such as the class of SFTs or minimal subshifts? What closure properties do automorphism groups have when restricting to particular classes of subshifts? Can we characterize the automorphism groups of some families of subshifts? A group is not determined by its subgroups, and thus it is also interesting to ask what kind of subgroups automorphism groups have. In this section, we give basic group theoretical definitions needed in later sections. The notation and definitions in this section are mostly standard, but we give them for completeness. For more details, the reader may consult any standard reference [START_REF] Rotman | An introduction to the theory of groups[END_REF].

In this section, and usually also in other sections a 'group' is a countable (discrete) group. Thus, a group is a countable set of objects called elements, where a mapping (•) : G × G → G satisfying a particular set of axioms is defined. The axioms are associativity a • (b • c) = (a • b) • c, the existence of an identity element ∃1 ∈ G : a•1 = 1•a = a (which is automatically unique) and the existence of inverses ∀a : ∃a -1 : a • a -1 = a -1 • a = 1 (which are automatically unique), where a, b, c are arbitrary elements of the group. We often drop the symbol '•' and write ab = a • b. Groups are usually denoted by G and H. If g 1 , g 2 , • • • , g k ∈ G, the products of g i and g -1 i generate a subgroup of G, and we write this group as g 1 , g 2 , • • • , g k . This is the subgroup of G generated by g 1 , g 2 , • • • , g k . This naturally generalizes to infinite sets of generators.

A group that has a finite set of generators is finitely generated. A group is cyclic if it has only one generator, that is, G = g for some g ∈ G. The only infinite cyclic group is the additive group of integers Z with the operation a • b = a + b. 10 The finite cyclic groups are the groups Z n with elements [0, n -1] and group operation a • b = ((a + b) mod n).11 A group is locally finite if its finitely generated subgroups are finite.

There are many ways to build new groups from existing ones.

If G is a group, a subgroup H ≤ G of G is a subset of G which is closed under products and inverses, that is, g, h ∈ H =⇒ gh ∈ H ∧ g -1 ∈ H. When H is a subgroup, the sets gH = {gh | h ∈ H} for g ∈ G are called cosets, and they form a partition of G (that is, gH ∩ g H = ∅ =⇒ gH = g H).
The set of cosets is denoted by G/H. We say H is normal and write H G if gH = Hg for all g ∈ G, and then the cosets G/H have a natural group structure given by gH • g H = gg H. The cardinality of G/H is denoted by [G : H], and is called the index of H in G. If the index is finite, H is called a finite-index subgroup. If H has a particular group property P and H is a finite-index subgroup of G, then we say G is virtually P.

A function π : G → H satisfying π(gh) = π(g)π(h) is called a group homomorphism from G to H. We say H is a quotient of the group G if there is a surjective group homomorphism π : G → H. A bijective group homomorphism is called an isomorphism, and we write G ∼ = H if there is an isomorphism between G and H. We say G and H are isomorphic, and consider them the same group for most purposes. The kernel ker(π) ⊂ G of a homomorphism π consists of the elements g ∈ G such that π(g) = 1 H . It is always a normal subgroup, and G/ker(f ) ∼ = π(G). The group G is residually finite if for all g ∈ G with g = 1 there exists a finite group H and a homomorphism φ :

G → H such that φ(g) = 1 H .
Given two groups G, H, one can construct larger groups in multiple ways. The direct product of G and H is the group G × H whose elements are the elements of the Cartesian product G × H and the operation is (g, h) • (g , h ) = (gg , hh ). Generalizing this, we define the semidirect product of G and H as follows. Write Aut(G) for the group of bijective group homomorphisms from G to itself. Let ψ : H → Aut(G) be a group homomorphism, and define G ψ H (or just G H) as the group with the Cartesian product G × H as elements, and (g, h)(g , h ) = (gψ h (g ), hh ) as the operation. The idea is that H is 'acting' on G. We show only associativity:

(a, b)((c, d)(e, f )) = (a, b)(cψ d (e), df ) = (aψ b (cψ d (e)), bdf ) = (aψ b (c)ψ bd (e)), bdf )) = (aψ b (c), bd)(e, f ) = ((a, b)(c, d))(e, f ).
Both the direct and semidirect product have G and H as subgroups in a natural way:

G ∼ = G × {1} and H ∼ = {1} × H. Both subgroups are normal in G × H, but (a priori) only G is normal in G H.
A more general 'construction' is the following: suppose N G, and φ : G → H is a homomorphism with ker(φ) = N . Then G is a group extension of H by N . If G is a direct product of N and H, then it can be seen as a group extension of N by H, and of H by N . The semidirect product N H is a group extension of H by N . However, there are not the only possible extensions, and even among finite groups, there is no full understanding of group extensions: the problem of characterizing them is called the extension problem, and it is still a major open problem in group theory. Nevertheless, many properties of groups are closed under group extensions, in the sense that if N and H have the property, then also every group extension of H by N has this property.

We can also construct groups by combining infinitely many smaller groups. We present (simplified versions of) two of the most basic constructions.

If G 1 ⊂ G 2 ⊂ G 3 ⊂ • •
• is an increasing sequence of groups (by which we mean that the elements of G i are elements of G i+1 for all i and the group operations are compatible), then G i has an obvious group structure by g • h = g • i h, where • i is the group operation of any G i with g, h ∈ G i . This is called the direct union of the groups G i . For an arbitrary countable family of groups

G 1 , G 2 , G 3 , • • • , their direct sum is the group i G i whose elements are functions f : N → i G i with f (i) ∈ G i
for all i and f (i) = 1 Gi for all but finitely many i, and whose group operation is pointwise product:

(f • g)(i) = f (i) • i g(i).
We say G is abelian if ab = ba for all a, b ∈ G. The finitely generated abelian groups are of the form

Z d × Z k1 × • • • × Z kn for some k 1 , . . . , k n ∈ N.
General countable abelian groups are not obtained by extending this to infinite products of this -in fact there is no full characterization of them. The best-known example of a non-finitely generated abelian group is probably the additive group of rational numbers Q with operation a • b = a + b. 12A notion generalizing abelianity is nilpotency. For a group G and g, h ∈ G, define the commutator of g and h as

[g, h] = ghg -1 h -1 and the commutator subgroup [A, B] generated by A, B ⊂ G as the one genenerated by [a, b] where a ∈ A, b ∈ B. The lower central series of G is defined inductively by G 1 = G and G i+1 = [G i , G]. If G i
is the trivial group {1} for some i ∈ N, then G is said to be nilpotent, and the smallest i such that G i = {1} is the step of G. Every abelian group is nilpotent, but the converse does not hold.

For a set S, the free group F S generated by S is defined as the group whose elements are all words over the alphabet {s, s -1 | s ∈ S} where the subwords of the form ss -1 and s -1 s do not occur, and u • v is the word obtained from uv by repeatedly erasing subwords of the form ss -1 and s -1 s until none occur. For n ∈ N, we write F n for the free group with any n generators, as they are all isomorphic. The free group F ∞ with countably many generators is defined in the obvious way, as a direct union of the F n .

Generalizing the definition of the free group, a group presentation is a combinatorial way to describe a group. Given a list of generators g 1 , g 2 , g 3 , . . . (considered as formal symbols) and a list of words

w 1 , w 2 , w 3 , . . . ∈ {g 1 , g -1 1 , g 2 , g -1 2 , g 3 , g -1 3 , • • • } *
(either list of may also be finite), we define the group g 1 , g 2 , g 3 . . . | w 1 , w 2 , w 3 , . . . as the group whose elements are equivalence classes of words over the symbols g i and g -1 i under the equivalence relation ∼ generated as follows: λ ∼ 1, gg -1 ∼ g -1 g = λ where λ is the empty word, and

uw i v ∼ uv for all i ∈ N. If G ∼ = {g 1 , g 2 , . . . | w 1 , w 2 , . . .}, then {g 1 , g 2 , . . . | w 1 , w 2 , . . .} is a group presen- tation of G. A group presentation for F n is a 1 , a 2 , • • • , a n | ∅ and one for Z d is a 1 , a 2 , • • • , a d | {a i a j a -1 i a -1 j | 1 ≤ i, j ≤ d} . Every (countable) group G has a group presentation {g 1 , g 2 , . . . | w 1 , w 2 , . . .}
where the g i are an enumeration of elements of G and w i are all words in {g 1 , g -1 , g 2 , g -2 , g 3 , g -1 3 , • • • } * which present the identity element of G. Using group presentations, we can define another product of G and H, namely their free product. Choose presentations for the groups G and

H, G ∼ = g 1 , g 2 , . . . | w 1 , w 2 , . . . and H ∼ = h 1 , h 2 , . . . | u 1 , u 2 , . . . ,

and define

G * H = g 1 , h 1 , g 2 , h 2 , g 3 , h 3 , • • • | w 1 , u 1 , w 2 , u 2 , w 3 , u 3 , . . . .
This group is defined by G and H up to isomorphism, no matter which presentations are chosen. Its elements can be thought of as words w ∈ (G∪H) * such that w i ∈ G ⇐⇒ w i+1 ∈ H, that is, elements of G and H alternate, where neither 1 G nor 1 H occurs in w. The product of u, v ∈ G * H is obtained from the word uv by repeatedly combining two adjancent elements of G into a single element of G using the group operation of G, and symmetrically for H, and removing 1 G and 1 H whenever they occur. The free product of finite groups can be infinite. For example, the

Z 2 * Z 2 is virtually Z and Z 2 * Z 2 * Z 2 is virtually F 2 .
A group G acts on a set X as explained already in the introduction, for each

g ∈ G, x → g • x is a bijection on X satisfying 1 • x = x and g • h • x = gh • x. The orbit of x under the action is the set G • x = {g • x | g ∈ G}, and the stabilizer of x is the subgroup G x ≤ G of elements g ∈ G such that g • x = x.
The group S n is the one acting maximally transitively on the set [1, n], that is, it contains exactly the permutations of [1, n]. For f, g ∈ S n , we define f • g by (f • g)(a) = f (g(a)) where a ∈ [1, n]. The direct union of all such groups is called S ∞ . Every finite group embeds in S n for some n ∈ N by Cayley's theorem.

Amenability, Cayley graphs and growth

Amenability is a notion which is extremely important in group theory. 13 We say G is amenable if it admits a Følner sequence, that is, a sequence

A 1 ⊂ A 2 ⊂ A 3 ⊂ • • • such that each A i ⊂ G is finite, G = i A i and ∀g ∈ G : |gA i ∆A i | |A i | -→ i→∞ 0.
Amenability is equivalent to (and often defined as) the existence of a leftinvariant mean on G, that is, a functional ν :

∞ (G) → R (where ∞ (G) are the bounded real-valued functions on G) satisfying ν(1 G ) = 1 (where 1 G is the constant-1 function on G) and ∀f ∈ ∞ (G) : (∀g ∈ G : f (g) ≥ 0) =⇒ ν(f ) ≥ 0.
All finite groups are amenable, as we can choose A i = G for all i, and Z d is amenable because we can choose A i = [-i, i] d as a Følner sequence.14 More generally, every abelian group is amenable. Amenable groups also have various closure properties: they are closed under subgroups, quotients, group extensions and direct unions. Thus, it is natural to define elementary amenable groups as the smallest class of groups which contains the finite and abelian ones, and is closed under subgroups, quotients, group extensions and direct unions (and isomorphism, naturally).

We usually explicitly discuss neither Følner sequences nor means: the following theorem summarizes our typical way to prove amenability or non-amenability.

Theorem 1. An elementary amenability group is amenable, and a group containing a free group on two or more generators is not amenable.

In general, an amenable group need not be elementary amenable [START_REF] Grigorchuk | Degrees of growth of finitely generated groups, and the theory of invariant means[END_REF], and a non-amenable group need not contain a free group [START_REF] Yu | On a geometric method in the combinatorial group theory[END_REF].

Let A = {g 1 , g 2 , . . . , g k } be a finite set of elements generating a group G, where A -1 = A. The Cayley graph of G with respect to the generators A is the directed edge-labeled countable graph with nodes G and for each a ∈ A an edge (g, ga, a), where by (a, b, c) we mean an edge from a to b with label c. In a graph, a natural notion of distance between nodes is the length of the shortest path between them. We write d G,A for the distance function of G in its Cayley graph with respect to generators A. We write B G,A (n) for the corresponding Cayley ball of radius n, defined as

B G,A (n) = {g ∈ G | d G,A (1, g) ≤ n}.
Changing the generators of G only changes distances by a multiplicative constant, that is, if

A = B = G then ∃C > 1 : ∀g, h ∈ G : d G,B (g, h)/C ≤ d G,A (g, h) ≤ Cd G,B (g, h).
Thus, the growth rate of balls in all Cayley graphs of G is similar. For finitely generated groups, we define some notions giving a rough classification of this growth rate. We say a (finitely generated) group G has polynomial growth rate

if ∃k ∈ N : ∀n : |B G,A (n)| ≤ n k + k
for some -and thus any -set of generators A. We say it has exponential growth rate if ∃a > 1 :

∀n : |B G,A (n)| ≥ a n
and say it is subexponential growth rate if it does not have exponential growth rate. By Gromov's theorem, a group with polynomial growth is virtually nilpotent. A group of subexponential growth is amenable.

Decidability

Definitional issues In this section, we discuss mainly decidability questions regarding the relationship between a CA and its local rule, for example the decidability of reversibility. See [START_REF] Kari | Decidability and undecidability in cellular automata[END_REF] for a survey of decidability in the theory of cellular automata.

To ask decidability questions about a group or a monoid, we need to fix a computational presentation of the elements. Let us choose such presentations for endomorphisms of subshifts: A cellular automaton on a subshift X ⊂ S Z k is a function f : X → X which has a radius r ∈ N and a local rule

F : S [-r,r] k → S such that f (x) v = F (x v+[-r,r] k ).
It is well-known that cellular automata are precisely the functions End(X). The local rule of a cellular automaton gives a computational presentation of the function, and thus a way to give a finite list of elements of the endomorphism monoid to an algorithm. This allows us to ask algorithmic questions about the monoid End(X), on any subshift X, even a highly uncomputable one. Note that from the local rules of f, g : X → X, we can easily form a local rule for the composition of two cellular automata by composing the local rules in an obvious way, again no matter what the subshift is.

We make a few (mostly obvious) remarks about the canonicality and caveats of this presentation of cellular automata. Every cellular automaton, on every subshift, has an infinite family of presentations by local rules, as we can always increase its radius. However, there is always a smallest possible radius. 15 By also using a local rule F : L 2r+1 (X) → S instead of F : S [-r,r] k → S (so that we only define the cellular automaton on the words it actually sees), we obtain a unique presentation. If the language of X is decidable, that is, given w ∈ S * we can algorithmically check whether w ∈ L(X), then this minimization process can be done algorithmically: Lemma 1. Let X ⊂ S Z be a subshift such that L(X) is a decidable language. Then, given F : S [-r,r] → S defining a CA f : X → X, we can compute r ≤ r and G : L → S where L ⊂ S [-r ,r ] such that G defines the same CA f and both r and L are minimal.

We mainly study decidability questions on subshifts with decidable languages, so the presentations can be thought of as unique, but when the subshift is not a priori decidable, we feel it is more natural to assume the local rule given as input is not minimized.

A more subtle issue is which local rules are actually endomorphisms or automorphisms of a particular subshift X. More precisely, given a rule F : S [-r,r] k → S, a CA f : S Z → S Z is defined, and we call the well-definedness problem the question of whether f (X) ⊂ X holds (that is, whether f restricts to a CA on X), and the reversibility problem the question of whether f |X ∈ Aut(X), where f |X is the restriction of f to X. The following simple example shows that neither problem is in general decidable even if the language of X is decidable, for somewhat uninteresting reasons.

Example 1. Define the CA f n on the full shift {0, 1, 1 , 2, 3} Z which exhanges 10 n 2 and 1 0 n 2 and otherwise behaves as the identity map. Take the subshift X of L -1 (0 * 10 * 20 * 30 * +0 * 1 0 * 20 * 30 * ) where additionally 1 0 n 20 k 3 is forbidden if the nth Turing machine halts on the kth step. Then f n restricts to an automorphism on X if the nth Turing machine never halts, and otherwise it is not well-defined on X -thus, both the well-definedness problem and the reversibility problem are undecidable. The language of X is clearly decidable.

We mainly study decidability questions for cellular automata on sofic shifts in dimension one, and in this case both the well-definedness problem and the reversibility problem are decidable by basic automata theory [START_REF] Lind | An introduction to symbolic dynamics and coding[END_REF][START_REF] Hopcroft | Introduction to Automata Theory, Languages, and Computation[END_REF]. We note that the picture is different in the case of multidimensional full shifts, as checking whether a local rule corresponds to a reversible cellular automaton is undecidable [START_REF] Kari | Reversibility of 2d cellular automata is undecidable[END_REF]. Since every effective subshift -in particular the example above -is a sofic shift in the next dimension [AS13,DRS12], checking welldefinedness of a CA on a multidimensional sofic shift with a decidable language is undecidable. On multidimensional SFTs, a simple construction based on the undecidability of the domino problem with a seed tile, or an application of the result of [START_REF] Guillon | Projective subdynamics and universal shifts[END_REF], shows that the well-definedness problem is undecidable on general SFTs. We do not know if the language can be made decidable.

Question 2. Is there a two-dimensional SFT with a decidable language where the well-definedness problem is undecidable? Another basic issue is whether two given local rules are the same. As mentioned above, if the language of X is decidable, we can compute a canonical local rule for each CA from any given local rule. Thus, to check whether two CA are the same, we can simply compute their minimal local rules and compare them. In particular the word problem of Aut(X) -the problem of checking whether the product of a given list of automorphisms is the identity map, is decidable for all subshifts X with a decidable language.

Again, this applies in particular to one-dimensional sofic shifts. In two dimensions, SFTs need not have a decidable language, and indeed, using the undecidability of the domino problem with a seed tile, one can easily build a two-dimensional SFT X where the problem of deciding whether a given local rule represents the identity element is undecidable, even when restricted to local rules that represent reversible CA. Nevertheless we do not know whether there are two-dimensional SFTs on which the word problem of a finitely generated subgroup of the automorphism group is undecidable. See [START_REF] Hochman | On the automorphism groups of multidimensional shifts of finite type[END_REF] for a related discussion.

Group-related issues Sofar, we have mainly discussed definitional issues, which, while necessary background information, have little to do with the actual automorphism groups. The list of possible group-theoretical questions about automorphism groups is pretty much endless: for any subshift X and any family of groups G, we can ask whether a given finitely generated subgroup G of Aut(X) is in G. For example, we are interested in the decidability of abelianity, cyclicity, finiteness and freeness of such groups. We can also ask whether the subgroup generated by them has a particular property in the larger group, such as normality or centrality.

There are also many well-known computational problems in pure group theory, which we also discuss. We already discussed the word problem.

Remark 2. Note that we defined the word problem of the automorphism group of a subshift in terms of local rules. For a finitely generated group, one can define the word problem can be defined without actually knowing what the elements of the group are: We choose a set of generators, and ask for the decidability of the word problem over those generators. The decidability of the word problem will be independent of the generators. Usually, it will be clear from context which problem we mean, and in fact they are equivalent in the situations we consider.

A question related to the word problem is the geodesics problem, where given a word w over a finite set of generators, we want to find the minimal word u over the same generators which represents the same group element. While the geodesics problem may take an exponentially longer time to solve than the word problem, in the sense of decidability the questions are equivalent. There are many variants of this problem, but as we do not address computational complexity in this paper, all of these questions may be thought of as restatements of the word problem. The conjugacy problem is the problem of, given two elements g, g of the group, deciding whether g = hg h -1 for some group element h.

A common question to ask about a group, and one that turns out quite interesting in the case of automorphism groups, is the torsion problem of deciding, given an element of the group, whether it generates an infinite group. For example, it is known that the two-dimensional generalization 2V of Thompson's group V has an undecidable torsion problem [START_REF] Belk | Some undecidability results for asynchronous transducers and the Brin-Thompson group 2V[END_REF], while Thompson's group V itself has a decidable torsion problem [START_REF] Belk | Some undecidability results for asynchronous transducers and the Brin-Thompson group 2V[END_REF][START_REF] Belk | Conjugacy and dynamics in thompson's groups[END_REF].

As noted in the introduction, many of the existing algorithmic questions about cellular automata do not fit into our framework. Namely, the usual approach to cellular automata is the study of the dynamics of the N-action (or Z-action) of a CA f given by n • x = f n (x). A variety of dynamical and computational behaviors is observed in these systems, yet the groups and monoids generated by a single cellular automaton are not particularly interesting: they are cyclic, and thus the groups obtained are isomorphic to either Z or Z n for some n ∈ N (and the monoids are equally simple).

Showing finiteness of a group of CA

It is useful to note that a group of cellular automata is finite if and only if the orbits under its action are finite (even bounded). We will use this result in Section 3 to prove some undecidability results for the automorphism group of a full shift.

Lemma 2. Let X be a transitive subshift, and let x ∈ X be a transitive point. Then the stabilizer of x in the action of Aut(X) is trivial, that is, if f, g ∈ Aut(X) and f (x) = g(x), then f = g.

Proof. If f = g, then f (y) 0 = g(y) 0 for some y ∈ X. Since x is transitive, f (y) 0 = f (σ n (x)) 0 = g(σ n (x)) 0 = g(y) 0 for some n ∈ Z.

In other words:

Theorem 2. Let X be a transitive subshift and let G be any subgroup of Aut(X). Then the following are equivalent:

-G is infinite, -G • x is infinite for some x ∈ X, -G • x can be arbitrarily large for x ∈ X.
In particular, it follows that if G is an infinite subgroup of Aut(X) for a transitive subshift X, then G is infinite if and only if it has an infinite orbit. In our main application, X is a full shift, and thus certainly transitive. The result is true in much more generality, but we omit the discussion of this.

Full shifts and transitive sofic shifts

We now look at full shifts and transitive sofic shifts, perhaps the most natural habitat of cellular automata. If the alphabet S is not explicitly specified, we assume |S| > 1.

One of the main tools in the positive entropy case is Lemma 3 below. It shows that it is usually enough to prove undecidability results and to perform constructions of subgroups on full shifts. A proof in the mixing SFT case, and restricted to automorphisms, appeared in [START_REF] Kim | On the automorphism groups of subshifts[END_REF]. The general proof for X a positive entropy (equivalently, uncountable) sofic shift is also easy, and outlines the idea of marker constructions (our version of the marker being the word u in the proof). We sketch a proof.

An unbordered word u is one that does not overlap itself, that is, uw = vu =⇒ |v| ≥ |u|.

Lemma 3 (essentially [KR90]

). If X is a positive entropy sofic shift, then End(X) contains a copy of End(S Z ) for any alphabet S.

Proof (Proof sketch). Every infinite aperiodic word contains arbitrarily long unbordered words, by Theorem 8.3.9 in [START_REF] Lothaire | Algebraic combinatorics on words[END_REF]. 16 Choose a positive entropy transitive sofic Y subshift inside the X, and a long unbordered word u that occurs in Y . If u is taken long enough, there are many words uvu where v is of length |u|/2 , 17 and by the pigeonhole principle (and long enough u), many such words which correspond to the same element of the syntactic monoid18 of L(X). Since u is unbordered, a local rule can safely change the word v between two occurrences of u, that is, compute a local transformation uvu → uv u.

More precisely, let V with |V | = |S| 2 be the a set of words v of length |u|/2 such that uvu is a word of X, and the words uvu for v ∈ V correspond to the same element of the syntactic monoid. Choose a bijection π : V → S 2 . Now, we map each f ∈ End(S Z ) to a CA g ∈ End(X) with the following behavior: on the points

• • • uv -2 uv -1 uv 0 uv 1 uv 2 u • • • where v i ∈ V for all i, we apply f × f R to the point • • • π(v -2 )π(v -1 )π(v 0 )π(v 1 )π(v 2 ) • • • ∈ (S 2
) Z (which we think of as two separate tracks each containing a point over the full shift S Z ), where

y R = • • • y 2 y 1 .y 0 y -1 y -2 • • • and f R (y) = f (y R ) R .
On points where no such sequence appears, g is the identity map. When a partial such sequence occurs, we glue the two tracks together like a conveyor belt at the end of the sequence, and think of the first track turning 180 degrees and continuing backwards on the second track. It is easy to check that this gives a consistent embedding of the endomorphism monoid End(S Z ) to End(X).

We note that we do not claim that Aut(X) embeds in Aut(Y ) when X and Y are general mixing SFTs. We suspect this to be the case, but subtle problems seem to arise when attempting to generalize the proof above. See [START_REF] Kim | On the automorphism groups of subshifts[END_REF] for an example of this.

Subgroups of Aut(X) for a transitive sofic shift X

In this section, we give some examples of what kind of subgroups can be created with the marker construction, and end the section with a complete characterization of the locally finite subgroups that appear in the automorphism group [START_REF] Kim | On the automorphism groups of subshifts[END_REF]. Most of the results in this section were essentially proved in [START_REF] Boyle | The automorphism group of a shift of finite type[END_REF] or [START_REF] Kim | On the automorphism groups of subshifts[END_REF].

While we know no restrictions on the groups Aut(X) for general subshifts X, there are some restrictions when X has suitable dynamical properties.

Lemma 4 ([BLR88]

). Let X be a subshift where periodic points are dense (for example, a transitive sofic shift). Then Aut(X) is residually finite.

Since the class of residually finite groups is closed under taking subgroups, we obtain nontrivial restrictions on the possible subgroups that can occur in Aut(X) when X has periodic points dense. For example, Aut(X) cannot contain a nontrivial divisible subgroup such as (Q, +), and cannot contain the infinite permutation group S ∞ .

The decidability of the word problem restricts the possible subgroups further, as we have already seen: Lemma 5. If X is a subshift with a decidable language (for example, a sofic shift), then every finitely generated subgroup of Aut(X) has a decidable word problem.

Note that in the proof of Lemma 3, the CA in the image of the embedding only change the points in subwords of the form • • • uv -1 uv 0 uv 1 u • • • . Since u can be taken arbitrarily long, the CA thus change only points in a subshift of strictly smaller entropy. Using standard techniques, we can make sure that the complement of this subshift still contains a positive entropy sofic shift. Using this idea, we obtain the following generalization.

Lemma 6 (Essentially Theorem 2.6 in [START_REF] Boyle | The automorphism group of a shift of finite type[END_REF]). If X is a positive entropy sofic shift (equivalently, uncountable), then End(X) contains a copy of the countable direct sum i∈N End(S Z ) for any alphabet S.

Equivalently, we can have countably many distinct alphabets, by Lemma 3. As a direct corollary, we obtain two closure properties for subgroups of automorphism groups of full shifts. Theorem 3. The set of subgroups of Aut(S Z ) is closed under countable direct sums for any alphabet S.

Of course, for this to be interesting, we need to have some subgroups to begin with. A trivial observation is that σ generates a copy of Z on any infinite subshift. Another observation, essentially Theorem 6.13 in [START_REF] Hedlund | Endomorphisms and automorphisms of the shift dynamical system[END_REF], is that every finite group embeds in Aut(X) for a positive entropy sofic shift. Using Lemma 3, this is very easy to show: a finite group G embeds in the permutation group S k for some k, and thus into Aut([1, k] Z ) by symbol permutations.

Proposition 1. If X is a positive entropy sofic shift, then Aut(X) contains every countable direct sum of finite groups and copies of Z.

In [START_REF] Boyle | The automorphism group of a shift of finite type[END_REF], it is shown that the free group with infinitely many generators embeds in the automorphism group of a mixing SFT. Applying Lemma 3, we obtain the same result for the automorphism group of a positive entropy sofic shift.

Theorem 4. If X is a positive entropy sofic shift, then Aut(X) contains F ∞ .

Corollary 1. If X is a positive entropy sofic shift, then Aut(X) is not amenable.

To prove Theorem 4, one embeds the free group Z 2 * Z 2 * Z 2 in the automorphism group using a marker construction. In [START_REF] Kim | On the automorphism groups of subshifts[END_REF], it is attributed to R. C. Alperin that more generally any free product of finitely many finite groups embeds in the automorphism groups. We make a slightly bolder conjecture: Conjecture 1. If X is a positive entropy sofic shift, End(X) contains the copy of the free product of countably many copies of End(S Z ) for any alphabet S.

Restricted to locally finite groups G, a full characterization of the subgroups of Aut(X) is known. As observed in the beginning of this section, the automorphism group of a transitive sofic shift is residually finite. This is the only requirement:

Theorem 5 ( [START_REF] Kim | On the automorphism groups of subshifts[END_REF]). Let X be a positive entropy sofic shift. Then a locally finite group G is isomorphic to a subgroup of the automorphism group of X if and only if G is residually finite and countable.

The paper [START_REF] Kim | On the automorphism groups of subshifts[END_REF] contains many more examples of subgroups that can be embedded (for example, fundamental groups of 2-manifolds), and proves that the set of subgroups of Aut(X) is closed under finite extensions when X is a full shift. That is, if H ≤ Aut(X) where X is a full shift, and

[G : H] < ∞, then G ≤ Aut(X).
Note that by Lemma 3, the groups Aut({0, 1} Z ) and Aut({0, 1, 2} Z ) embed into each other, and thus have the same subgroups. However, we do not know whether there is an isomorphism between them.19 This is one of the open problems in symbolic dynamics listed in [START_REF] Boyle | Open problems in symbolic dynamics[END_REF].

Question 3. Are Aut({0, 1} Z ) and Aut({0, 1, 2} Z ) isomorphic? It follows from Ryan's theorem that Aut({0, 1} Z ) and Aut({0, 1, 2, 3} Z ) are not isomorphic, because in Aut({0, 1, 2, 3} Z ) that shift map has a square root, while it does not have one in Aut({0, 1} Z ).

Decidability on positive entropy sofic shifts

Most decidability problems for cellular automata are about their dynamical properties, such as mixing, transitivity, sensitivity and expansivity. These questions are, at least a priori, outside our scope, as there is no known algebraic property satisfied by, for example, the mixing CA, but not the rest.

However, the dynamical notion of equicontinuity turns out to be equivalent to eventual periodicity on all subshifts. For automorphisms f ∈ Aut(S Z ), this is the question of whether f k = id X for some k ≥ 1, that is, the torsion problem. Though the result is not stated in group-theoretic terms, in [START_REF] Kari | Periodicity and immortality in reversible computing[END_REF], this problem is shown undecidable on full shifts. Using Lemma 3, 20 we obtain the result for all positive entropy sofic shifts.

Theorem 6 ([KO08]

). Let X be a positive entropy sofic shift. Then the group Aut(X) has an undecidable torsion problem.

This trivially implies many undecidability problems, such as whether a given finite set of elements generates an infinite group, or whether it generates a torsion group. We now prove some slightly more interesting corollaries.

The notion of time-symmetry was introduced for cellular automata in [START_REF] Gajardo | On time-symmetry in cellular automata[END_REF]. We give this definition for an arbitrary subshift: a CA is time-symmetric if it is the composition of two involutions, where an involution is a CA g ∈ Aut(X) satisfying g 2 = id X . That is, f ∈ Aut(X) is time-symmetric f = g • h for some g, h ∈ Aut(X) satisfying f 2 = g 2 = id X . The name comes from the equivalent condition that g • f • g = f -1 for some involution g ∈ Aut(X). It is shown in [START_REF] Gajardo | On time-symmetry in cellular automata[END_REF] that time-symmetric CA are intrinsically universal among the reversible cellular automata, that is, every reversible automaton can be simulated by a time-symmetric one. The proof of this claim gives the following theorem:21 Theorem 7. Given a finite set of finite order automorphisms of a positive entropy sofic shift X, it is undecidable whether they generate a finite group.

Proof. Again, it is enough to prove the result for full shifts by Lemma 3. We show that an algorithm for this problem would give an algorithm for the torsion problem as well. Let f ∈ Aut(S Z ) be given. Consider the full shift (S × S) Z , and define g, h ∈ Aut((S × S) Z ) by g(x, y) = (f (y), f -1 (x)) and h(x, y) = (y, x). Then (g • h)(x, y) = (f (x), f -1 (y)). If f is infinite, then the orbit of some point x is infinite by Theorem 2, and thus the orbit of (x, y) is of infinite order by Theorem 2 for any y ∈ S Z . Let then | f | = k, and consider a point (x, y). Clearly the orbit of (x, y) under the action of g, h is contained in the finite set {(f i (x), f j (y)), (f i (y), f j (x)) | i, j ∈ Z}. Since every orbit is finite, g, h is finite, again by Theorem 2.

The proof shows more precisely that given two automorphisms of order 2, it is undecidable whether they generate a finite or an infinite group. More precisely, in the construction, depending on whether f halts, we obtain either a finite dihedral group D n , or the infinite dihedral group D ∞ = Z 2 * Z 2 . One can easily perform a similar proof to for example show that the finiteness of a group generated by automorphisms of order 3 is undecidable. We prove a more general result of this form.

Theorem 8. Let X be a positive entropy sofic, and let G be an arbitrary nonempty finite group. Then, given two finite subgroups F, F ≤ Aut(X) with F ∼ = F ∼ = G, it is undecidable whether F ∪ F is finite.

Proof. Again, we only need to prove the claim on full shifts. Let f ∈ Aut(S Z ) be arbitrary. We again show that an algorithm for the problem in the statement also decides whether f is finite. Without loss of generality, we may assume G is a subgroup of a symmetric group S k , so that G acts nontrivially on [1, k]. Let F = {f g | g ∈ G} be the subgroup of Aut((S k ) Z ) permuting the tracks according to this embedding:

f g (x 1 , . . . , x k ) = (x g -1 (1) , x g -1 (2) , . . . , x g -1 (k) ).
We now give another embedding, F , where in addition to permuting the tracks, we apply a power of f to the tracks when they are moved. For this, choose a function c : [1, k] → Z. The idea is that if track i is moved to track j by a permutation g ∈ G, the corresponding CA f g will apply f c(j)-c(i) to the ith track x i before moving it. Thus, the jth track will always be c(j) -c(i) steps ahead in time compared to the track i. This gives another embedding of G to Aut((S k ) Z ), since if

g 1 • g 2 • • • g = 1 for g i ∈ G, then f g1 • f g2 • • • • • f g
permutes every track to its starting position, and naturally the movements in time cancel out, so that

f g1 • f g2 • • • • • f g k = id (S k ) Z .
More precisely, take a function c : G → Z and define

C : G × [1, k] → Z by C(g, i) = c(g • i) -c(i). Define F = {f g | g ∈ G} by f g (x 1 , . . . , x k ) = (f C(g,g -1 •1) (x g -1 •1 ), . . . , f C(g,g -1 •k) (x g -1 •k )).
It is easy to check that g → f g gives an embedding of G into Aut((S k ) Z ). 22We claim that if c is injective, then F ∪ F is finite if and only if f is. Consider thus an arbitrary point (x 1 , x 2 , . . . , x k ) ∈ (S k ) Z . First, if f is finite, we are done: every point in the orbit of (x 1 , x 2 , . . . , x k ) has a point from the orbit of one of the points x i on each track, which gives a finite upper bound on the size of orbits. Conversely, suppose x has an infinite orbit in the action of f . Let g • i = j for g ∈ G and i, j ∈ [1, k] with i = j (the action of G is nontrivial on [1, k]). Since c is injective, C(g, i) = c(g • i) -c(i) = n = 0. For notational simplicity, suppose i = 1 and j = 2. Then (x, y, • • • )

f g → (y , f n (x), • • • ) f g -1 → (f n (x), y , • • • )
for some points y, y , y ∈ S Z . Clearly, this shows that the orbit of any point (x, • • • ) is infinite.

Again, the alphabet S k can be changed by applying Lemma 3.

There are many open questions about automorphism groups, even on full shifts. For example, the decidability of time-symmetry is open in one dimension (in two dimensions, it is undecidable [START_REF] Gajardo | On time-symmetry in cellular automata[END_REF]).

Question 4. Is it decidable whether a given CA f ∈ Aut(S Z ) is time-symmetric? More generally, we do not know whether it is decidable if a given CA is generated by involutions, or elements of finite order. For a more general question in the same spirit, see the FOG conjecture (not true in general [START_REF] Kim | Solution of two conjectures in symbolic dynamics[END_REF]) and virtual FOG conjecture in [START_REF] Boyle | Open problems in symbolic dynamics[END_REF]. Another question whose solution we do not know is the conjugacy problem: is it decidable in Aut(S Z ) whether two given elements f, g are conjugate?

More in line with Theorem 8 and our constructions in this section, we state the following conjecture.

Conjecture 2. It is undecidable whether two given automata generate a (nonabelian) free group.

If Conjecture 1 is true, and the embedding is computable, then the previous conjecture is true as well: given f ∈ Aut(S Z ), consider the CA g, h ∈ Aut(S Z ) given by the embedding of Aut(S Z ) * Aut(S Z ) into Aut(S Z ), so that f ∼ = g ∼ = h and g and h generate the product g * h in Aut(S Z ). Then clearly g and h generate a group isomorphic to F 2 if and only if f has infinite order.

A simple decidable property is abelianness: to check whether a finite set F of cellular automata generate an abelian group, we only need to check whether the identity f • g = g • f holds for all pairs f, g ∈ F .

Countable subshifts

The simplest countable subshifts (and the simplest subshifts in general) are probably the finite ones. A finite subshift is always an SFT, and the automorhism groups of such SFTs are simply the centralizers of permutations on finite sets. The following characterization was given in [START_REF] Cyr | The automorphism group of a shift of subquadratic growth[END_REF]: Let S n act on Z n m by φ(g)(i 1 , i 2 , . . . , i n ) = (i g -1 (1) , i g -1 (2) , . . . , i g -1 (n) ) for g ∈ S n . 23 Define the semidirect product S(m, n) = Z n m S n with respect to the action φ. For future purposes, similarly define S(∞, n) = Z n S n . Theorem 9. A group G is the automorphism group of some finite subshift if and only if

G ∼ = S(m 1 , n 1 ) × S(m 2 , n 2 ) × • • • × S(m s , n s ) for some m 1 < m 2 < • • • < m s and n 1 < n 2 < • • • < n s .
Equivalently, these are precisely the finite groups that occur as automorphism groups of subshifts, since σ generates an infinite subgroup of Aut(X) if X is infinite.

In [START_REF] Salo | Computational aspects of cellular automata on countable sofic shifts[END_REF], cellular automata on countable sofic shifts were discussed from the point of view of computability. Unlike in the case of full shifts, many dynamical behaviors (though not all!) of such automata are decidable. In particular, the following is proved:

Theorem 10 ([ST12]
). Let X be a countable sofic shift. Then the torsion problem is decidable for Aut(X).

While undecidability results about the dynamics of cellular automata on countable sofic shifts are shown in [START_REF] Salo | Computational aspects of cellular automata on countable sofic shifts[END_REF], we do not know any interesting undecidability results about the automorphism group in the countable case.

This suggests that the automorphism group might be essentially simpler in the countable case, and in a way it is: While Corollary 1 shows that the automorphism group of an uncountable sofic shift is never amenable, the author and Michael Schraudner are working on the proof that the automorphism group of a countable sofic shift always is. We prove this for a simple example.

Proposition 2. For k ∈ N, let X k ⊂ {0, 1} Z be the (countable sofic) subshift whose forbidden words form the regular language (10 * ) k 1. Then Aut(X k ) is elementarily amenable.

Proof. We prove this by induction on k. The base case is the one-point subshift X 0 whose automorphism group is the trivial group, which is certainly elementary amenable. Now, let k > 0. The isolated points of X k are exactly the ones containing k 1-symbols. A homeomorphism must map isolated points to isolated points, so if f ∈ Aut(X k ), then the restriction f |X k-1 is well-defined. The map φ : f → f |X k-1 is a homomorphism from Aut(X k ) to Aut(X k-1 ). Its image is elementary amenable by induction, so we only need to show that ker(φ) is as well.

For this, let r be the common radius of f, f -1 ∈ ker(φ). Let Y r be the set of points y in X that contain k 1-symbols, which all occur in a single subword of y of length 2r + 1. We claim that if x / ∈ Y r , then f (x) = x. Otherwise, x i = f (x) i for some i. If x contains less than k 1-symbols, then f is not in the kernel of φ. Otherwise, because x / ∈ Y r , x [i-r,i+r] cannot contain all the 1-symbols. In particular,the point y with y [i-r,i+r] = x [i-r,i+r] and y j = 0 for j / ∈ [i -r, i + r] is in X k-1 . But f (y) i = y i , so again f cannot be in the kernel. This contradiction shows that only points in Y r can be changed. The same reasoning applies to f -1 , so the set Y r is invariant under the action of f . In other words, the action of f permutes Y r and leaves every point in X \ Y r invariant. 24Now, let F r be the subgroup of ker(φ) that only permutes the points in Y r . This is clearly a subgroup, and ker(φ) = r∈N F r . Thus, it is enough to show that F r is elementary amenable. For this, observe that the set Y r consists of finitely many orbits:

Y r = O(x 1 ) ∪ O(x 2 ) ∪ • • • O(x n ) for some n and x i ∈ X.
A permutation of Y r can, by shift-commutation, only permute the tracks and shift them around. It is then easy to show that F r embeds in the group Z n S n , which is elementary amenable as a semidirect product of amenable groups.

On the other hand, unlike the automorphism group of a transitive sofic shift, the automorphism group of a countable one need not be residually finite: Proposition 3. There exists a countable sofic shift X with S ∞ ≤ Aut(X). In particular, Aut(X) is not be residually finite.

Proof. An example is X

2 = L -1 (0 * 10 * 10 * ). If g ∈ S ∞ , define f g : X 2 → X 2 by f g ( ∞ 0.10 n 10 ∞ ) = ∞ 0.10 g(n) 10 ∞ .
Since g has finite support, f g simply permutes finitely many (orbits of) isolated points and leaves everything else invariant. Continuity and shift-commutation are clear, and it is easily verified that g → f g embeds S ∞ into Aut(X 2 ).

Every countable subshift has zero entropy, and it seems likely that this puts severe restrictions on the automorphism group. For example, the only ways to embed free groups into automorphism groups that the author is aware of generate entropy. Nevertheless, from just the assumption that X is countable, we are not able to prove any properties for Aut(X).

Question 5. If G is the automorphism group of a subshift, is it also the automorphism group of a countable subshift? Are automorphism groups of countable subshifts amenable? Can they contain a copy of F 2 ?

Minimal subshifts and subshifts of low complexity

A substitution is a function τ : S → S + . We can apply such a map τ also to finite words by τ

(w) = τ (w 0 )τ (w 1 ) • • • τ (w |w|-1 ). Suppose τ is primitive, that is, ∃n : ∀a, b ∈ S : ∃i : τ n (b) i = a. For a ∈ S let L a = {τ n (a) | n ∈ N}. Then X τ = L -1 (L a ),
for any a, is the subshift generated by τ . The substitution τ is binary if S = {0, 1} and constant-length if ∃n : ∀a ∈ S : |τ (a)| = n. We say τ has a coincidence if ∃i : τ (a) i = τ (b) i for all a, b ∈ S.

The subshifts X τ for primitive τ are always minimal. Due to their rigid selfsimilar structure, one can often precisely compute their automorphism groups. To our knowledge, the first explicit result was the following.

Theorem 11 [START_REF] Coven | Endomorphisms of substitution minimal sets[END_REF]). Let τ be a binary primitive constant-length substitution. If τ has a coincidence, then Aut(X τ ) = σ . Otherwise, Aut(X τ ) = σ ×f , where f is the binary flip CA defined by f (x) i = 1 -x i .

This was generalized in [START_REF] Host | Homomorphismes entre systèmes dynamiques définis par substitutions[END_REF] to the non-binary case. We state only a weak form of the theorem.

Theorem 12 ([HP89]

). Let τ be a primitive constant-length substitution. Then Aut(X τ ) is virtually Z.

It is also shown in [START_REF] Host | Homomorphismes entre systèmes dynamiques définis par substitutions[END_REF] that this is close to optimal, as Aut(X τ ) can be of the form G × Z for any finite group G. (This construction can also be found in [START_REF] Donoso | On automorphism groups of low complexity minimal subshifts[END_REF].) In [START_REF] Salo | Constructions with countable subshifts of finite type[END_REF], we generalized this result to all balanced substitutionsones where |τ n (a)| = a n + d(n) where a > 1 and d is a bounded function.

A further generalization is the class of linearly recurrent minimal subshifts, and even more general are the minimal subshifts with linear (factor) complexity: the word complexity of X is the function n → p n (X) = |L n (X)|, and X has linear factor complexity if ∃C : ∀n : p n (X) ≤ Cn + C. We asked in [START_REF] Salo | Block maps between primitive uniform and pisot substitutions. Ergodic Theory and Dynamical Systems[END_REF] whether it is true in general that linear factor complexity on a minimal subshift implies virtually Z. It quickly turned out that the answer is 'yes':

Theorem 13 ([CY14,CK14,DDMP14]). The automorphism group of an infinite minimal subshift with linear factor complexity is virtually Z.

In fact the result turned out to be, in some sense, folklore, though not explicitly published before. It can be proved quite quickly by using known properties of the fibers of the maximal equicontinuous factor in the linear complexity case.

The result of [START_REF] Cyr | The automorphism group of a shift of subquadratic growth[END_REF] is stated more generally for transitive subshifts, and all papers show more general results, in different directions. For cellular automata, we obtain in particular that for some k, every reversible CA f : X → X on an infinite minimal subshift with linear factor complexity satisfies f k = σ n for some n ∈ Z. It is quite easy to see that a virtually Z group has a decidable word problem and a decidable torsion problem in the purely group-theoretical sense. Using the folklore result that a Π 0 1 minimal subshift has a decidable language (see [START_REF] Salo | Subshifts with Simple Cellular Automata[END_REF]), we see that these problems are even uniformly decidable in the following sense.

Theorem 14. Given a Turing machine T enumerating the forbidden patterns of an infinite minimal subshift X and a cellular automaton f : X → X, we can decide whether f = id X . If X has linear factor complexity, whether ∃n ≥ 1 : f n = id X is decidable as well.

Proof. An algorithm for checking f = id X follows directly from the decidability of the language of x, so in particular the word problem is decidable. As for the torsion problem, iterating f , we obtain local rules for f n for all n. By the assumption, f n = σ m for some n, m. Since the word problem is decidable, it is easy to find such n and m algorithmically. 25 If m = 0, the answer is 'yes'. Otherwise it is 'no'.

A result analogous to Theorem 13 can be shown for the endomorphism monoid when the subshift is also linearly recurrent, that is, there exists n such that every word u ∈ L(X) that appears in every word of L n|u| (X) (see [START_REF] Durand | Substitutional dynamical systems, Bratteli diagrams and dimension groups[END_REF] for more on this concept). Namely, it is known that in this case the subshift is coalescent, that is, Aut(X) = End(X) [START_REF] Durand | Linearly recurrent subshifts have a finite number of nonperiodic subshift factors[END_REF].

We note that while it is known that the automorphism group is virtually Z for a linear growth minimal subshift (in fact [START_REF] Cyr | The automorphism group of a shift of subquadratic growth[END_REF] shows the subtly stronger result, that it is a semidirect product of a finite group and Z), and groups of the form G × Z all occur as automorphism groups, we do not know what the precise class of automorphism groups is even in the linear growth case. The answer is presumably right around the corner, but we don't know it: Question 6. Which groups appear as Aut(X) for minimal subshifts X with linear factor complexity? Another class of subshifts that has been studied are the ones with subquadratic factor complexity (for all C > 0, we have p n (X) < Cn 2 for large enough n):

Theorem 15 ( [START_REF] Cyr | The automorphism group of a shift of subquadratic growth[END_REF]). Every cellular automaton on a transitive subshift of subquadratic complexity is a root of a shift map.

In other words, if f : X → X is a CA and X is transitive and of subquadratic complexity, then f k = σ n for some k > 0, n ∈ Z. Unlike in the case of linear complexity, there is no uniform bound on the k, that is, for a transitive subshift X of subquadratic complexity, if k(f ) is the least positive integer such that f k(f ) ∈ {σ n | n ∈ Z}, then k : End(X) → N may be unbounded. An explicit example of such a subshift is given in [START_REF] Salo | Toeplitz subshift whose automorphism group is not finitely generated[END_REF].

Theorem 16 ([Sal14a]

). There exists a minimal Toeplitz subshift X with subquadratic complexity whose automorphism group is not finitely generated:

Aut(X) ∼ = 2 5 i | i ∈ N ≤ (Q, +).
Of course, Theorem 14 extends to the subquadratic minimal case by the same proof. Presumably it does not generalize to all minimal subshifts, but we have no examples. Question 7. Is there a minimal subshift with a decidable language whose automorphism group does not have a decidable word problem? Can the automorphism group have a finitely generated subgroup whose word problem is undecidable?

In [START_REF] Boyle | The automorphism group of a shift of finite type[END_REF], a minimal subshift is constructed whose automorphism group contains a copy of Q. There is much freedom in the construction, and they explain how the group could be made precisely Q.

Theorem 17 ([BLR88]

). There is a minimal subshift X with Aut(X) ∼ = Q.

It seems likely that one can also modify the construction so that the subshift has subquadratic factor complexity. With a similar construction, it seems that one can also obtain for example S ∞ as the automorphism group of a subquadratic growth. Nevertheless, we have no conjecture what the characterization is.

All the examples above are locally virtually cyclic: every finitely generated subgroup is virtually cyclic. This is not always the case on minimal subshifts, as shown by the following example (although the group is still locally virtually abelian): Proposition 4. [START_REF] Donoso | On automorphism groups of low complexity minimal subshifts[END_REF] For any d ∈ N, there exists a minimal subshift X with lim n→∞ p X (n)/n d+1 = 0 and Aut(X) ∼ = Z d .

The following limitation is shown in [START_REF] Donoso | On automorphism groups of low complexity minimal subshifts[END_REF] in the case that recurrence times of words are polynomial (which is a stronger assumption than polynomial complexity). For a subshift X, define N X (n) = inf{m | w ∈ L m (X) =⇒ ∀u ∈ L n (X) : u occurs in w}. Like in the case of countable subshifts, we are not aware of any general results about the possible automorphism groups of minimal subshifts.

Question 8. Which groups occur as automorphism groups of minimal subshifts? In particular, if G is the automorphism group of a subshift, is it also the automorphism group of a minimal subshift? Can F 2 occur as a subgroup? Are the automorphism groups of minimal subshifts amenable? Let G M (resp. G M ) be the family of groups Aut(X) (resp. Aut(X)/ σ ) for minimal subshifts X. Especially in conjunction with the case of coded subshifts, the following question is particularly interesting: We briefly describe two of the results shown in [START_REF] Fiebig | The automorphism group of a coded system[END_REF] about automorphism groups of two families of transitive subshifts, namely the coded and synchronized systems. A word w X is synchronizing if uw, wv X =⇒ uwv X. This means, in some sense, that no information travels over w. A synchronized system is a transitive subshift with a synchronizing word. The following construction of synchronized systems is shown in [START_REF] Fiebig | The automorphism group of a coded system[END_REF]:

Theorem 19 ( [START_REF] Fiebig | The automorphism group of a coded system[END_REF]). Given any subshift X with periodic points dense, there is a synchronized system Y such that Aut(Y ) contains a copy of Aut(X).

A coded system is a subshift X of the form X = L -1 (W * ), where W is any countable set of words over a finite alphabet. In other words, points of X are the limit points of infinite concatenations of words in W . Every synchronized system is coded, but the converse does not hold.

There is much freedom in the construction of automorphism groups of coded systems, as shown by the following strong result.

Theorem 20 ([FF96]

). If X has dense periodic points and G ≤ Aut(X), then there is a coded system Y with Aut(Y ) ∼ = G × Z, where the isomorphism maps σ to (1 G , 1).

We note that this allows the exact construction of automorphism groups, not only subgroups of them, which separates coded systems from the families discussed in the previous sections (at least when it comes to known results). In particular, all finitely generated abelian groups can be obtained exactly as automorphism groups of coded systems. Since coded systems themselves have periodic points dense, the theorem also gives a kind of closure property for their automorphism groups.

Corollary 2. Let G C be the set of groups G such that Aut(X) ∼ = G×Z for some coded subshift X. Then G C is closed under taking subgroups.

We are not aware of a similar closure property for any other natural class of subshifts.

The family of coded systems contains only subshifts with periodic points dense, and thus they have only residually finite automorphism groups. There are some additional restrictions: Lemma 7 ( [START_REF] Fiebig | The automorphism group of a coded system[END_REF]). The residually finite group Z[1/2] is not the automorphism group of any coded system. Again, we do not know what the precise class of groups that occur is.

  Theorem 18 ([START_REF] Donoso | On automorphism groups of low complexity minimal subshifts[END_REF]). Let X be a transitive subshift such thatsup n≥1 N X (n)/n d < ∞ for d ≥ 1.Then, there is a constant C depending only on d, such that any finitely generated subgroup of Aut(X) is virtually nilpotent of step at most C.

Question 9 .

 9 Is G M closed under subgroups? Is G M ? More generally, what closure properties do they have? 6 Coded and synchronized systems

Later, we will instead fix f to be the left shift map on X, and see cellular automata in another way.

Note that if f and g have been applied to x, the resulting state does not carry information in which order, and how many times, f and g have been applied. We can only reverse their action if we know in which order they have been applied.

This is just the set of all words over the alphabet {a, b} with concatenation as the multiplication operation

However, no-one forces us to: for example, from a reversible CA, we obtain both an

Sofic entropy applies more generally to sofic groups.[START_REF] Bowen | Measure conjugacy invariants for actions of countable sofic groups[END_REF]

The entropies of Z-actions are just the entropies of reversible cellular automata. Characterizing the set of entropies in this case (on full shifts) seems to be essentially harder than in the non-reversible case.

We omit σ from the notation End(X) since we consider it an intrinsic part of X.

It is a very interesting question which properties have such algebraic definitions. Equicontinuity corresponds to eventual periodicity and by Ryan's theorem the shift maps are precisely the center of Aut(X)[START_REF] Ryan | The shift and commutativity[END_REF] and more generally of End(X)[START_REF] Salo | Subshifts with Simple Cellular Automata[END_REF] on mixing SFTs, but we don't know much more.

And in more dimensions with an obvious generalization.

Of course, Z has a natural multiplication operation as well, the multiplication of integers, but it does not yield a group.

Again, multiplication could be defined on Zn by integer multiplication modulo n, but this does not form a group. However, if 0 is omitted, we do obtain a group when n is a prime.

The usual multiplication of Q is again not a group, but if 0 is omitted we obtain another non-finitely generated group, namely the free abelian group on countably many generators, by the unique factorization theorem of rational numbers.

It is also very important in dynamics: as noted in the introduction, it is needed in the direct generalization of entropy to group actions.

That is, the Cayley balls are a Følner sequence in the abelian case -we note that this is not how Følner sequences look in general. For example, if the size of balls grows exponentially, then the balls are never a Følner sequence.

We note that, except on full shifts, there is in general no minimal neighborhood, as easy examples show -nevertheless, there must be a minimal radius simply because the natural numbers are well-ordered.

A stronger version of this is shown in Lemma 2.2 of[START_REF] Boyle | The automorphism group of a shift of finite type[END_REF].

This follows because every transitive sofic shift has a uniform distance k such that if u and v occur in the language, then uwv occurs for some w of length at most k. This is a direct application of the pigeonhole principle.

We omit the definition, but u and v corresponding to the same element of this monoid means exactly that they occur in the same contexts, so we may exchange them. See[START_REF] Hopcroft | Introduction to Automata Theory, Languages, and Computation[END_REF].

There certainly are non-isomorphic groups that embed into each other, for example the free groups F2 and F3 are such a pair.

In fact, the CA constructed in[START_REF] Kari | Periodicity and immortality in reversible computing[END_REF] are already time-symmetric, but the idea on permuting tracks illustrates Theorem 2 better.

Readers familiar with cohomology will notice that c is just an arbitrary 0-cochain c ∈ Hom(C(G, [1, k]), Z) for the action of G on [1, k] and C is the corresponding 1-coboundary -in particular, C is a 1-cocycle, from which it follows that the action of F is well-defined.

In[START_REF] Cyr | The automorphism group of a shift of subquadratic growth[END_REF], the dual definition is used. Our definition must be used to obtain a homomorphism when the composition of permutations is defined by (π • π )(a) = π(π (a)) (but also the dual definition is used by some authors).

It is a general fact that if a group action on A maps B ⊂ A to C ⊂ B, then it maps B exactly onto itself, and also A \ B onto itself.

For this, the assumption that f is indeed a cellular automaton on X is crucial. Given a local rule not defining such a CA, it is not clear what can be said.