For which group-alphabet pairs $(G, A)$ does $(G, A^G)$ admit a topologically mixing cellular automaton?


Let $G$ be a (discrete) group. An alphabet is a finite set of cardinality at least two. The full shift on the group $G$ and alphabet $A$ is the group action $(G, A^G)$, where $A^G$ has its product topology and $G$ acts by $gx_h = x_{g^{-1}h}$. A cellular automaton or CA is a continuous function $f : A^G \to A^G$ that commutes with the action, i.e. $g \cdot f(x) = f(g \cdot x)$ for all $g \in G$ and $x \in A^G$. Let's say a dynamical $\mathbb{N}$-system is a pair $(f, X)$ where $f : X \to X$ is continuous and $X$ is a compact metrizable space. If $f$ is a CA, then $(f, A^G)$ is a dynamical $\mathbb{N}$-system. A dynamical $\mathbb{N}$-system $(f,X)$ is topologically mixing if $$ \forall \mbox{ open sets } U, V \subset X: \exists n_0 \in \mathbb{N}: \forall n \geq n_0: f^{-n}(V) \cap U \neq \emptyset. $$

Some things out of the way:

  • If $G$ contains a finitely-generated infinite group $H$ and $(H, A^H)$ admits a topologically mixing CA $f$, so does $(G, A^G)$.

Proof: By acting as $f$ separately on each left coset of $H$ we obtain a CA $f' : A^G \to A^G$ whose action is isomorphic (as a dynamical $\mathbb{N}$-system) to the (possibly infinite) product system $\prod_{i \in G/H} (f, A^H)$, and a product of topologically mixing systems is clearly topologically mixing.

  • In particular, if $\mathbb{Z} \leq G$ then $(G,A^G)$ admits a topologically mixing CA.

Proof: On $A^{\mathbb{Z}}$, the shift by $1 \in \mathbb{Z}$ is itself a CA (since $\mathbb{Z}$ is abelian), and obviously it is topologically mixing. Now apply the previous item.

  • If $G$ is finite, then topological mixing cannot happen for any alphabet $A$.

Proof: Fixed points of the $G$-action stay fixed, and every set is open.

  • If $G$ is infinite and locally finite, then topological mixing cannot happen for any alphabet $A$.

Proof: A cellular automaton has a finite neighborhood $N \subset G$ such that $x \mapsto f(x)_g$ factors through $x \mapsto x|_{gN}$. The CA $f$ acts separately on the left cosets of $\langle N \rangle$, and we can apply the previous item to conclude it is not topologically mixing when $\langle N \rangle$ is finite.

Now, I am expecting that the answer to the above question is "Exactly the pairs $(G, A)$ such that $G$ is not locally finite." If I am correct in this, in light of the previous items, the following is the gist of the problem.

Let $G$ be a finitely-generated torsion group. Find a topologically mixing CA on the full shift $(G, A^G)$ (for some alphabet $A$, preferably for all).

Of course $f$ has to be surjective, and I would be especially interested in a bijective example (on some groups, e.g. the Grigorchuk group, injective implies bijective). If you can do just topological transitivity, that's also interesting. If you prefer ergodicity or measure-theoretic mixing notions (for the uniform Bernoulli measure on $A^G$), that's also interesting but presumably harder to do.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.