Topologically mixing cellular automata on groups

Question

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.

Answer 1

I think that now after a few years of daydreaming I see how to do this. It seems a little tricky to write down carefully, and maybe not worth the trouble (especially as I have no idea if anything this complicated is needed). So here's a sort of sci-fi novel version, sorry about the length, there's a lot of moving parts.

Theorem(-ish). Let $G$ be a finitely-generated torsion group. Then there exists a topologically mixing CA on the full shift $(G,A^G)$ for any finite non-trivial alphabet $A$.

Proof(-ish). Take $A$ any nontrivial alphabet and $G$ any finitely-generated torsion group. Suppose $0,1 \in A$. Our cellular automaton $f : A^G \to A^G$ will have two important properties: first, it is conserving, meaning it conserves the number of live/populated cells, that is, cells containing a nonzero symbol. In formula form $\forall x \in A^G: |\{g \in G \;|\; x_g \neq 0\}| = |\{g \in G \;|\; f(x)_g \neq 0\}|$. Second, it is reversible, and not just that, it is morally conjugate to its inverse by another cellular automaton (i.e. its inverse has a similar description, up to swapping the order of some steps that were arbitrary in the first place).

I will explain how to construct the CA that realizes the topological mixing property, step by step, interspersed between the ideas of how topological mixing is realized. But let's start by discussing some aspects of the behavior of the final CA immediately, assuming only the above properties.

First, observe that by conservation and torsionness of $G$, if we take a finite configuration (meaning $x \in A^G$ such that its support $|\{g \in G \;|\; x_g \neq 0\}|$ is finite), then its $f$-orbit is finite (and by reversibility $x$ is $f$-periodic). This can be proved by induction on the cardinality of the support: If you have only a single symbol in $x$ at $g$, then after at most $|A|$ time steps you see the same symbol again $gh$, and then use the period of $h$. If you have $n$ symbols, observe that if there exists $R$ such that at all times the symbols stay within distance $R$ from each other for all time, then we can think of them as a single symbol in a conserving cellular automaton. If there is no such $R$, then eventually the finitely many symbols split into at least two groups separated by a sufficient distance that by induction they become periodic separately.

The idea is to take a configuration $x \in U$ to have finite support, let's call this the blob, and observe it until the Poincaré recurrence time predicted by the previous paragraph (in the dynamics of the CA we of course have yet to describe). Let $K \subset G$ be the finite set of cells that become populated at some point during this time. Let $k \in K$ be a "corner" cell, meaning such that a geodesic path exists from $k$ to infinity. Such $k$ exists by a compactness argument.

Now, our CA will admit the construction of "worms" that can contract and expand at some "speed" (e.g. measured with word norm w.r.t. some finite generating set), which will be the maximal asymptotic speed at which you can populate empty areas or completely evacuate areas. There will be things that move faster, but they can only move inside already existing material, informally the "speed of sound is significantly greater than the speed of light". Namely, the worms will have nerves carrying signals governing their behavior. The idea is that we have our worms go pick up a symbol out of the blob (specifically at $k$), and then retreat at the speed of light so that the blob is now left on its own, and will have smaller support. We iterate this process to erase the blob, and then we will build another arbitrary blob in its place.

Before I can describe the worms, let me first describe a way to embed arbitrary one-dimensional cellular automata into cellular automata over arbitrary groups. For this I need the notion of an atom. An atom has a nucleus and a cloud. The nucleus simply consists of three $1$s in a specific constellation, more specifically there is a nucleus "at" $g$ and $g$ is specifically the proton of the nucleus (and the resulting atom), if these live cells are at positions $g, gh, gh'$, where $h, h'$ are some fixed elements such that $d(1,h) = 2, d(h,h') = 1, d(1, h') = 3$, and the radius $6$ ball around the proton contains no other live cells. Observe that such a pair $h, h'$ exists. We fix some large $R$ (specified later) and in the $R$-ball around the proton, we can have any other symbols, as long as they are pairwise separated by a distance of at least $3$. These form the cloud, and we call the cells in its support its electrons. (Obviously all this faux physics terminology is just for mnemonic purposes.)

We say an atom is active if there is no other atom at distance at most $2R$. Note that we can uniquely decompose any configuration in $A^G$ into atoms and other stuff. Now, in each cloud, we can code a large amount of information in the constellation of electrons. In particular, we can store two elements of some finite set $B$, and we can store a pointer to a "follower atom" (specifically its proton) and a "predecessor atom" which are at distance, say, at most $10 R$. This needs a little calculation because the group can have a strange growth rate, but note that there must be infinitely many possible choices of $R$ such that a quantity exponential in $R$ (the amount of data we can code in the cloud) is much larger than the size of the $10 R$ ball (the offset vectors we need to code), as otherwise the group's growth rate is a tower function (while it obviously has an exponential upper bound).

Now, we can use a standard conveyor belt trick. We think of atoms that are their follower's predecessor as connected to their follower, and then every configuration splits into polymers, namely atom chains. On each such chain, as each atom stores an element of $B^2$, we can interpret a conveyor belt: think of the two $B$s as being on top of each other, connect the top $B$-elements into a tape, and the bottom ones into an "upside down" tape, and at the ends of the polymer (if they exist), you join the top and bottom of the $B^2$-symbol. This way, every configuration actually splits into non-coding areas and encoded configurations of the form $B^{\mathbb{Z}}$ (polymers that have at most one end) and $B^{2n}$ (finite polymers).

It is straightforward to simulate any one-dimensional cellular automaton on these encoded tapes. Our starting point, the primordial worm, is obtained by simulating a very large power of the shift. The primordial worm does not move, and it does not eat, it only thinks shifty thoughts. We will slowly evolve it into a worm that can move around, and can eat (and... uneat) things, including other worms.

Let us call the cellular automaton corresponding to the primordial worm $f_{\mathrm{shift}}$. All the action is, so far, "inside" the support of the configuration, in the sense that the support does not essentially grow in the action of $f_{\mathrm{shift}}$. This will be what gives the speed of sound / nerve signal we referred to earlier. Observe that by using a suitable coding of $B^2$, this indeed is a conserving cellular automaton. Actually if we are specifically simulating a shift (or a conserving cellular automaton), one possibility is to have a certain subconstellation corresponding to each $b \in B$, and explicitly allocate a part of the atoms for storing this.

Now, we add to our worms the capability of extending themselves. For this, we will have two special symbols $1$ and $2$. We will construct an involutive cellular automaton that looks at the head of each worm, namely the end of the worm where the top track is moving symbols "out of" the track. Specifically, look at the three $B$-symbols coded on the top track at the head. If the symbols are not of the form $12b$ for any $b \in B$, or $b12$ for any $b \in B$, then nothing happens. If they are one of these, then the idea is to keep the $12$ in place, and possibly insert/remove the $b$ after it. Check that the distance from the head the tail end of the worm is vast enough. (Specifically, check the distance of the $12$ to the tail end is vast, so that the distance is not modified by what happens in the next paragraph.) If it is not vast, do nothing.

If it is indeed vast, then if we are in the case $b12$, read off the coding of a new atom on the top track (in the atoms preceding the $1$, starting with the $b$). Basically part of the $B$-symbols being carried have a position where they store symbols (or holes) that can be used for this purpose. Verify that the coded atom's predecessor arrow agrees with the forward arrow of the atom coding the $2$. If so, then we would like to put down the atom at the head of the worm, extending it (you should literally move the symbols from the special positions of the top track atoms to their positions, so as to keep the CA conservative). In the situation with $12b$ on the top track, you should snatch the atom containing the $b$ and store it in holes on the top track, so that this is an involution. Of course nothing happens if there are already atoms where we want to put something, or we are trying to contract an atom that's not there.

Of course, there's the issue that there may be other worms tring to extend themselves. We simply check that no other worms are nearby before we extend/contract. Note that we should make sure that when worms extend themselves they don't come closer to us, so that we don't e.g. extend two worms and then decide they are now too close to contract themselves back. The standard trick (which was already used when considering whether a polymer is "vast enough") is that the $2$ in a worm's head is its anchor, and we measure distance to the anchor primarily (cancel movement if another anchor is at distance at most $R'$, say), and only secondarily to other cells (cancel movement if a non-anchor cell is at distance at most $R'' \leq R'/10$, say). Let us call the CA that performs this extension/contraction $f_{\mathrm{e/c}}$.

At this point a worm that has one infinite end can extend themselves and contract itself quite freely: the speed of sound is very fast so if we apply $f_{\mathrm{shift}}$ and $f_{\mathrm{e/c}}$ alternately, the data at the head of the worm is completely different (locally), so the instructions to successive applications of $f_{\mathrm{e/c}}$ are independent.

At this point, remember that we have this "corner" cell $k$ where at some point in time (again, of course it depends on this CA we are developing, but whatever it will be at the end, there is a corner $k$...), a live cell appears in the evolution of the blob. What we can already do at this point is grow a worm along a geodesic from infinity so that it is near $k$ at a time when $k$ is populated.

We now want to evolve our worms even further, by allowing them to eat, and our plan is to eat up the cell at $k$ when it is populated, and move it onto our track. This is really a can of worms... For the sake of simplicity I prefer to think of the blob as adversarially as possible, so when I send a worm $w$ to remove a symbol from the blob I cannot discount the possibility that the blob becomes very angry, and uses all its might to shoot a bunch of worms at my worm $w$, eating it up and becoming even more powerful than before. And of course, it's also an issue that our cellular automaton rule couldn't possibly know which worm has "priority" when snatching, $w$ or the other worms.

The next evolution step, which helps with this a bit, is that we will have worms of two different colors, red and blue. This can be indicated by e.g. having a second kind of nucleus, or just something static in the cloud. We take our CA to be $\prod_{c \in \{\mathrm{red}, \mathrm{blue}\}} f_c \circ f_{\mathrm{shift}} \circ (f_{\mathrm{e/c}} \circ f_{\mathrm{shift}})^n$, where $n$ is absolutely humongous ($n = 1$ should work fine, but for the mental picture I prefer that we can contract/extend a lot between other things).

The action of $f_c$ is be similar to extension/contraction of worms: At the end of a worm (= end of a polymer), $f_c$ reads an instruction on the top track to move the symbol at offset $t$ (relative to the proton of the atom at the head) to some special part of the encoded $B$-symbol, or vice versa; we refer to this as eating or uneating a symbol. We have to be very careful here, as the CA may not be invertible if we eat a symbol on the tape of another worm that is about to eat something elsewhere (and that elsewhere could be far away, since the worms look at many atoms before their head, before making their decisions). So we now describe the many checks we perform before eating (or uneating) anything.

The idea is, when $f_c$ is applied, worms of color $c$ stake claims over some positions, again some this is guided by values that $f_{\mathrm{shift}}$ moves on the top track at their head. One may think of the worms as putting their fingers on these positions. First each worm will ask all worms near it for permission to make a change. More precisely, each worm carries some values on its top track, one primary value and several inhibitor values (these need not be directly at head, we can actually use any fixed amount of atoms of the worm leading up to the head to store them). If a worm find its primary value in the inhibitors of some other worm, then it does nothing. If after the inhibitions, two worms are still interested in the same coordinate, then neither will touch it. In fact, if two worms are interested in coordinates at distance at most $2R$, then both drop their claim. If after this, a worm is still interested in a particular coordinate, it checks that the modification does not affect any other $c$-colored atoms, i.e. we do not introduce any new $c$-colored atoms, and you do not modify the contents of any existing $c$-colored atoms. (Otherwise, again, the worm simply drops its claim.) Finally, if the change touches an atom from a worm of the other color $\bar{c}$ or it introduces such a worm, then in those worms (possibly the worms are different before and after the modification) we check all the inhibitor values seen locally, and check that our primary value is not among them.

Here there's some playing with numbers to see that this gives an involution, which I didn't do, but I think there isn't anything really nontrivial since we never modify the $c$-colored worms so the set of claims made by $c$-worms is exactly the same, and the only things that can both change in the configuration, and can affect cancellation of claims, are cells that are part of $\bar{c}$-colored worms, and we explicitly check for those both before and after the change.

Ok, so now clearly we can have our worm get close enough to the corner $k$ that we can stake a claim for the nonzero symbol in that position. If this position is part of a $\bar{c}$-colored atom at that point in time, our worm should be of color $c$. We choose the primary value so that no inhibitor values prevent this (including a possible new $\bar{c}$-colored atom that appears when we remove an atom), and we should conversely have among our own inhibitor values all the nearby worms' primary values. The only problem that could still prevent the change is that we actually introduce a $c$-colored atom when making this change. But clearly we can pick the encodings so that there is always at least one atom whose removal does not introduce a $c$-colored atom, and we can just eat this nearby cell instead of $k$. Indeed I think this is automatic if the atoms are sufficiently error correcting and unbordered. This is another point where I didn't work out the details, but I do not think there's anything subtle here that could go wrong.

Ok, so now we believe we can snatch a symbol into our worm, at least momentarily. Now we will begin contracting our worm at maximal speed, what I referred to as "light speed" above. As mentioned, things can actually move much faster in theory, namely information moves much faster in the "nerves" of worms. In any case, it should be an easy induction to show that no finite configuration can extend into empty space faster than the expansion/contraction rate of worms, even if it is guided by possible inhibition signals coming from the area into which it is expanding. I do not want to try to even state that carefully, but hopefully the claim is clear, and at least to me it seems obviously true.

Now at this point, for all we know, we are contracting and a bunch of other worms have gotten very angry and are chasing our worm, trying to snatch its head. (I don't see why something like this couldn't happen since we may actually bring a blue worm into existence. Of course we could probably first deactivate it by being careful about what we snatch, but I feel it's easier to think adversarially about the blob.) The other worms will not see very far into our snatcher worm, since we are contracting at the same speed (or faster) than they are extending, so all we need to do is pick our inhibitor signals so that they do not modify us. They may be angry, but they are very polite, and they will leave us alone if we do so.

Now the blob is smaller, and I said we continue by induction. But there are a couple of problems. First, possibly the angry worms chase us forever, this time I don't think it can happen because the only input they get from us is some inhibitor signals, and they should not be able to use this to guide them along the geodesic direction along which we are contracting. But I don't see a clean argument.

If I had infinitely many geodesic rays then I would be fine, as I could just drag those angry worms to infinity and would have made the blob smaller quicker, but it's not immediately clear to me how to get infinitely many geodesic rays in a group that eventually get separated from each other (maybe there is some variant of Halin's theorem that gives this, or even some simpler argument?) So while contracting, we should also keep snatching things from the chasers. That doesn't slow us down since the snatching steps are between, and not alternative to, contraction/extension, but there is the issue that some of the chasers may be the same color as us. We of course also need to snatch things that are red, so we need to send in both a red and a blue worm.

So it'd be great if we could have red and blue snakes travel sort of in the same place. We can in fact easily do precisely this: allow atoms to be offset by some vector, and store that vector in their nucleus, say. The distances are measured w.r.t. the "virtual position" the offset vector points to, so that we can still argue they are moving at the same geodesic rate, but now by growth rate considerations if we allow a sufficient offset vector size, we can easily have two worms travel along the same geodesic. Now, we can use a red and a blue worm in unison to eat up the chasers. And this also shows that we have a blue worm we can use to red cells in the blob.

At this point, the CA construction is finished, and on the way I have explained why it is able to erase a finite blob, i.e. how to eat its entire population into the internal memory of the red and blue snatcher worms. Now, we need to build an arbitrary blob. Well, just observe that the CA is morally conjugate to its inverse: the inverse is $\prod_{c \in \{\mathrm{blue}, \mathrm{red}\}} (f_{\mathrm{shift}}^{-1} \circ f_{\mathrm{e/c}})^n \circ f_{\mathrm{shift}}^{-1} \circ f_c$ (where we observe that $f_c$, $f_{\mathrm{e/c}}$ are involutions), and we see that the process works the exact same (actually looking at this formula maybe this is literally conjugate by a CA; anyway we don't need that).

We of course need yet another geodesic for the building process. One could use the same geodesic and offsets, and probably even the same worms with some thinking, but the easiest way is probably to take a two-way infinite geodesic (which exist by compactness because one-way geodesics exist and the graph is transitive), and use the geodesic "in the other direction" for building. This way, the building process doesn't even see the forward process in any way, as long as it's performed sufficiently late. And of course we can have any delay as long as it's big enough, so indeed we get topological mixing.

Square.

I believe that an easy modification to this construction shows that every infinite finitely-generated torsion group admits a physically universal cellular automaton in the sense of Janzing, namely instead of $f_{\mathrm{shift}}$, use a more complicated CA that allows the worms to think, and after the initial extraction process send the information about the pattern to the construction process using one-endedenss of torsion groups. (On non-torsion groups, physical universality should be much easier to exhibit, but of course hasn't been done either.)