3
$\begingroup$

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

Definitions:

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.

$\endgroup$

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.