SHIFT HAPPENS

Cantor-Bendixson ranks of one-dimensional subshifts

April 26th, 2023
Nicolás Matte Bon asked me if I have a reference for which Cantor-Bendixson ranks of subshifts can be realized. I do not have a reference, but I always assumed I know the answer (countable $\lambda+2$ and finite ordinals in the countable case, and any countable ordinal in general), and that the constructions are easy. Trying to explain this to him, I realized I do not actually know a construction in the general case.

I’ll attempt a proof from scratch, but first a brief discussion of literature: First, this result may well be in the literature directly. I would not be surprised if e.g. the result can be obtained directly by relativizing the known results for effective $\mathbb{Z}$ -subshifts, see [1]. Unfortunately I never read this paper in much detail, and don’t know the exact construction.

I can’t help to also tell the “fascinating” story of the ranks of $\mathbb{Z}^2$ -SFTs, which are now fully understood. The final answer is $\lambda + 3$ for computable $\lambda$ (and of course the finite ordinals), see [2] (by Törmä). The problem arose from [3], and was “almost” solved in Jeandel and Vanier [4], who obtained all computable ordinals $\lambda + c$ with a finite (and not too large) constant $c$ . We optimized the constant $c$ to 5 in [5] by using counter machines instead of Turing machines, and in his thesis Törmä used one-counter machines to get it down to 4. He finally used a result from [6] to get the final answer $c = 3$ in [2]. The optimality in turn is from [7], and is also a non-trivial result.

Ok, onto the results. We’ll use the Von Neumann model for ordinals, so $\alpha < \lambda$ and $\alpha \in \lambda$ are synonymous. Here we define the Cantor-Bendixson rank of a subshift (shift-invariant compact subset) $X \subset A^{\mathbb{Z}}$ to be the smallest ordinal $\lambda$ such that $X^{(\lambda)} = X^{(\lambda+1)}$ , where $X^{(\alpha)}$ for ordinal $\alpha$ is defined by removing isolated points transfinitely.

The final set $X^{(\lambda)}$ is perfect. Since a perfect set with at least two points is uncountable, if the original subshift $X$ is countable (i.e. has countably many points), the final set $X^{(\lambda)}$ is empty; otherwise it is still uncountable (the rank must be countable since subshifts are second-countable, and thus we remove only countably many countable sets in the derivation process).

For countable subshifts the characterization is easy to prove:

Theorem. The Cantor-Bendixson ranks of countable $\mathbb{Z}$ -subshifts are precisely the finite ordinals, and $\lambda + 2$ for limit ordinals $\lambda$ .

Suppose $X$ is a countable subshift with rank $\alpha$ . If $\alpha$ is a limit ordinal, then $X^{(\alpha)} = \emptyset$ is a decreasing intersection of closed sets. That’s impossible by the descending chain condition for compact sets (note that each $X^{(\lambda)}$ is compact).

If $\alpha = \lambda+1$ where $\lambda$ is a limit ordinal, then $X^{\lambda}$ is a finite subshift, thus of finite type, and a finite type subshift cannot be the decreasing intersection of subshifts (note that each $X^{(\lambda)}$ is compact), since at some point you already forbid a set of forbidden patterns.

So an infinite rank is of the form $\lambda+2$ for some $\lambda$ , and since the topology is second-countable, $\lambda$ is a countable ordinal.

For the construction (for the case of infinite or large ranks), consider a closed subset of Cantor space $X \subset \{0,1,2\}^{\mathbb{N}}$ . Let $\alpha = \lambda+1$ be the Cantor-Bendixson rank (again it’s clear it cannot be a limit ordinal), and $Z = X^{(\lambda)}$ the last nonempty step.

Since $Z$ is finite, we can homeomorph $Z$ to a set of points of finite support (meaning finitely many $1$ s), and all other points to points of infinite support. (To do this, first observe that in any clopen set we can clearly move any single point to a finite-support point by adding a constant configuration cellwise mod $2$ to the tail, and then we can do this separately in a clopen partition separating the points of $Z$ . Then to make other points infinite support, first intersperse $0$ s between coordinates of all points, and then have a homeomorphism start flipping all $0$ s to $1$ as soon as the prefix differs from all points of $Z$ .)

We may also suppose that $Z$ has at least two elements (by possibly replacing $X$ by a direct union $X \sqcup X$ initially) and then we may assume two of the points in $X$ are $1000\ldots$ and $2000\ldots$ .

After this preprocessing, code each $x \in X$ as
$y_x = \ldots 0000 x_1 0 x_2 00 x_3 000 x_4 0000 x_5 00000 x_6 \ldots$ ,
take $Y$ the smallest subshift containing all these points. This is just the orbits of the $y_x$ , and the point of all zeroes (the limit points $\ldots 0001000\ldots$ , $\ldots0002000\ldots$ are directly of the form $y_x$ by our preprocessing). Now it’s easy to see that points $y_x$ disappear exactly according to the derivative process of $X$ . So $Y^{(\lambda)}$ contains no points of the form $y_x$ , thus $Y^{(\lambda+1)} = \emptyset$ . On the other hand $Y^{(\lambda)}$ contains the all-zero point.

For any $\lambda+1$ , we can take as $X$ take the ordinal $\omega^{\lambda} + 1$ with the order topology. By one standard definition of countable ordinals this $X$ embeds in the interval $[0, 1]$ and by topology it embeds in Cantor space. Its CB-rank is $\lambda+1$ , so the previous construction gives rank $\lambda+2$ .

For finite $\lambda$ , the above construction gives all $\lambda \geq 2$ , and $0, 1$ are trivial to obtain. Square.

For the general (and the uncountable) case, I didn’t find a simple construction, and can only supply a proof sketch which I found convincing enough. If you know a simpler proof, or another proof, or a reference, or of a mistake in this argument, or other, I’d be interested in hearing it. I may make another attempt at a more detailed proof at some later point.

Theorem. The Cantor-Bendixson ranks of uncountable $\mathbb{Z}$ -subshifts are precisely the countable ordinals.

Proof sketch. The rank must be countable for the same reason as in the previous theorem.

For the construction, take any countable ordinal $\lambda$ . Biject $\pi : \lambda \to \mathbb{N}$ , and if $\alpha \in \lambda$ has $\pi(\alpha) = n$ , then pick a word $w_\alpha$ which is not in the Fibonacci subshift but is in its $n$ th SFT approximation.

We can furthermore ensure, by picking very long such words, that the words $w_\alpha$ for distinct ordinals $\alpha$ look very different. Concretely, we want to be able to find a point where $w_\alpha$ appears in the center, which is in the $n$ th SFT approximation, and which quickly converges to the Fibonacci subshift on both sides, e.g. the tails are literally Fibonacci; and we want that in these points no other $w_{\beta}$ appears. This is easy to achieve by picking the words very long and random and in increasing order of $\pi(\alpha)$ deliberately avoiding previous ones.

Now pick $y$ some point in the Fibonacci subshift. Note that the SFT approximations of the Fibonacci subshift are transitive. Now construct a point $y_\alpha$ for each $\alpha \in \lambda$ in a dovetailing fashion: to construct $y_\alpha$ , put a single $w_\alpha$ at the origin, continue it to the left by a Fibonacci tail, and continue it to the right by transitioning it arbitrarily close to each $y_{\beta}$ for $\beta > \alpha$ infinitely many times, in arbitrary order.

The crucial points are that
- $w_\alpha$ appears exactly once in this point, and
- between the “dives” into approximating points $y_{\beta}$ we quickly transition into words from the Fibonacci subshift.
- between these dives, we have longer and longer Fibonacci words in between,
  The first point is easy to achieve by how we chose the words $w_{\alpha}$ , and the second and third are easy as well since the points $y_{\beta}$ have arbitrarily long words from the Fibonacci subshift in both tails, which we can continue with their natural continuations in the Fibonacci subshift, when we want to transition from one approximation to another.
Now the Cantor-Bendixson derivative removes points $y_\alpha$ precisely after all smaller points have been removed, so you remove all of them precisely at the $\lambda$ th step. At that step, what you have left is the Fibonacci subshift, which no longer changes (a Fibonacci subshift is going to be there automatically, or you can just stick it in there explicitly if you don’t believe me). Square.

References:

[1] Douglas Cenzer, Ali Dashti, Ferit Toska & Sebastian Wyman. Computability of Countable Subshifts in One Dimension. Theory Comput Syst 51, 352–371 (2012). https://doi.org/10.1007/s00224-011-9358-z

[2] Ilkka Törmä: Cantor-Bendixson ranks of countable SFTs. CoRR abs/1803.03605 (2018).

[3] Alexis Ballier, Bruno Durand, Emmanuel Jeandel: Structural aspects of tilings. STACS 2008.

[4] Emmanuel Jeandel, Pascal Vanier: $\Pi^0_1$ -sets and tilings. Theory and Applications of Models of Computation, 2011, Springer.

[5] Ville Salo, Ilkka Törmä: Constructions with countable subshifts of finite type. Fundamenta Informaticae, 2013.

[6] Peter Cholak and Rod Downey. On the Cantor-Bendixon rank of recursively enumerable sets. J. Symbolic Logic, 58(2):629–640, 1993.

[7] Alexis Ballier and Emmanuel Jeandel. Structuring multi-dimensional subshifts. ArXiv e-prints, September 2013

Advertisement
On a theorem of Ore

April 4th, 2023

Theorem A (Ore, 1951). The commutator width of the alternating group on five or more points is one.

In other words, every element of the alternating group on at least $5$ elements is a commutator (of elements in that group).

For our work on distortion with Antonin Callard I decided to actually implement the so-called “commutator trick” (which maybe I’ll discuss in another post), and it felt natural to use Ore’s theorem since it the formulas that appear in the commutator trick are shorter by a multiplicative constant if we use it. For this, I of course needed a “constructive” proof of Ore’s theorem, i.e. I needed an algorithm that takes an even permutation $a$ on a finite set $S$ , and produces two even permutations $b, c$ on the same set, such that $a = [b, c] = bcb^{-1}c^{-1}$ .

Here’s Ore’s argument:

“A more thorough investigation whose details we shall omit here makes it possible to establish the stronger form of Theorem 1 [= Theorem B below].”

Although this is quite convincing, and far from the worst proof I have seen in terms of proof value, this is not very helpful when you need to actually explain the formulas to your computer. There has been quite a bit of further research into the topic of commutator width of simple groups (spoiler alert, it’s at most one), but the papers I found cite Ore’s paper for the alternating group, so they are not very helpful either.

In this post, I give a simple algorithmic proof of Theorem A. This is not exactly the actual algorithm I implemented, as there were some simplifications I came up with while writing this post (my program actually did one special case by brute force). Maybe I will test this later if I get around to revisiting my implementation, to see if it holds up in practice.

First, let us recall what Ore explicitly proves.

Theorem B (Ore, 1951). The commutator width of the symmetric group on five or more points is one.

In other words, any even permutation can be written as a commutator of two permutations (which may not be even themselves). In what follows, I act right-to-left with my permutations, and commutators are $a b a^{-1} \cdot b^{-1}$ , following Ore’s conventions.

Proof. It is well known that two permutations are conjugate (in the symmetric group) if and only if they have the same cycle structure. We first observe that a permutation is a commutator if and only if it can be written as a product of two conjugate permutations. Namely, a commutator $a b a^{-1} \cdot b^{-1}$ is such a product, since $a^{-1}$ has the same cycle structure as $a$ , and conjugating by $b$ preserves the conjugacy class. Conversely, if $a, c$ are conjugate permutations, then so are $a^{-1}$ and $c$ so $c = ba^{-1}b^{-1}$ and thus $ac = aba^{-1}b^{-1}$ is a commutator.

Back to the problem at hand, it now suffices to show that odd cycles and pairs of even cycles are commutators (on the same domain), as we can then represent the individual odd cycles and even-cycle-pairs of the cycle decomposition of an even permutation $g$ as commutators $[a_n, b_n]$ , and then we get $g = [A, B] = [\prod a_n, \prod b_n]$ because $a_m$ and $b_n$ commute for $m \neq n$ since they are on disjoint domains. Note that an even permutation is precisely one where there is an even number of even cycles in the cycle decomposition, so indeed we can go through the even cycles in pairs.

Representations as products of conjugate permutations are obtained as follows:
$(1, 2, \ldots, 2i + 1) = (1, 2, \ldots, i + 1)(i + 1, i + 2, \ldots, 2i + 1)$ (a product of two $(i+1)$ -cycles), and
$(1, \ldots, 2i) (2i+1,\ldots, 2i+2j) = (1, \ldots, i+j+1)(2i, i+j+1, \ldots, 2i+2j)$ (a product of two $(i+j+1)$ -cycles) when $j \geq i$ . Square.

Let $A = \prod a_n$ , $B = \prod b_n$ be obtained from the above (as described, taking $a_n, b_n$ the “commutatorands” obtained from the argument, for odd cycles and pairs of even cycles).

Our plan is to simply massage these permutations to get even permutations $A', B'$ such that $[A', B'] = [A, B] = g$ , by using the special form of the permutations obtained from Ore’s argument. One could presumably instead directly give formulas for the permutations $A', B'$ , but we couldn’t find simple formulas that do not involve a complicated case distinction. Let’s now restate Ore’s theorem and prove it.

Theorem A’. The commutator width of the alternating group on five or more points is one. Furthermore, there is a polynomial time algorithm that, given an even permutation $g$ (in cycle notation or two-line notation) constructs two even permutations $A, B$ such that $g = [A, B]$ .

Proof. Let’s first work out the concrete commutator representations for the products of conjugate permutations that were used in the previous proof. Concretely, recall that the idea is to write $aba^{-1}b^{-1}$ as $a \cdot ba^{-1}b^{-1}$ and note that in $ba^{-1}b^{-1}$ we act by $b$ on the entries in the cycle representation of $a^{-1}$ . So when writing a product $ac$ of two cycles this way, it is easy to write down $b$ in two-line notation (i.e. as a function): $b$ should map the entries of the cycle $a^{-1}$ to the entries of $c$ , in order, and it does not matter where other points are mapped.

So for an odd cycle $(1, 2, \ldots, 2i + 1) = (i+1, i+2, \ldots, 2i+1)(1, 2, \ldots, i + 1)$ with $i \geq 1$ (we will discuss fixed points separately, let’s not count them as odd cycles), we take $a = (i+1, i+2, \ldots, 2i+1)$ . Then $a^{-1} = (2i+1, 2i, \ldots, i+1)$ so to map this to $(1, 2, \ldots, i + 1)$ we should take
$b = \begin{pmatrix}1 & 2 & \cdots & i & i+1 & \ldots & 2i-1 & 2i & 2i+1 \\ * & * & \cdots & * & i+1 & \ldots & 3 & 2 & 1\end{pmatrix}$
where $*$ s indicate that it does not matter where these points are mapped (other than the fact we must get a permutation). For example, we can (and later will) pick $b$ to be just the reversal map.

For a pair of two-cycles $(1, \ldots, 2i) (2i+1, \ldots, 2i+2j) = (1, \ldots, i+j+1) (2i, i+j+1, \ldots, 2i+2j)$ , with $j \geq i$ , we take $a = (1, \ldots, i+j+1)$ and $b = \begin{pmatrix}1 & 2 & \ldots & i+j & i+j+1 & i+j+2 & i+j+3 & \ldots & 2i+2j \\ 2i+2j & 2i+2j-1 & \ldots & i+j+1 & 2i & * & * & \ldots & * \end{pmatrix}$ where $*$ s again indicate that we don’t care where the points are mapped.

We could now pick the images of $b$ that we do not care about suitably to get the correct parity, and use the symmetry of the situation for $a$ to do the same for $a$ , but the number of special cases this leads to seems to be long, so we use a slightly different approach which is also easy implement (and has no special cases).

We observe that for odd cycles of length $2i+1$ , in the choice above $a$ has $i$ fixed points since it is an $(i+1)$ -cycle, and if we pick $b$ to be the reversal, then it has one fixed point and $i$ two-cycles.

For a pair of even cycles of lengths $2i, 2j$ , $a$ has $i+j-1$ fixed points since it is an $(i+j+1)$ -cycle, and we can ensure $b$ has at least $i+j-2$ two-cycles: In the above formula for $b$ , we have determined the images of $1, \ldots, i+j+1$ only; all but two of them have images in $i+j+2, \ldots, 2i+2j$ so we can map them back to their starting points, except for $2i$ which already has a preimage.

Concretely, we can make the choice $b = \begin{pmatrix} 1& \ldots & i+j & i+j+1 & i+j+2 \;\; \ldots & 2j & 2j+1 & 2j+2 \;\; \ldots & 2i+2j \\ 2i+2j & \ldots & i+j+1 & 2i & i+j-1 \;\; \ldots & 2i+1 & i+j & 2i-1 \;\; \ldots & 1 \end{pmatrix}$
where we understand that if $i = j$ then the images of $i+j+1, i+j+2 \ldots, 2j$ are omitted and $b$ is just the reversal. Thus, in the case $i = j$ , $B$ in fact gains $i+j$ two-cycles.

Now we consider the final commutator $[A, B]$ where again $A$ is the product of the $a$ s and $B$ that of the $b$ s. To summarize the above discussion, in the odd case $2i+1$ , $A$ always gains $i$ fixed points and $B$ gains $i$ two-cycles. In the even case $2i \leq 2j$ : $A$ gains $i+j-1$ fixed points and $B$ gains $i+j-2$ two-cycles, except if $i = j$ then $B$ gains $i+j$ two-cycles. In particular, in each construction step (where we consider an odd cycle or a pair of even cycles) we gain at least one fixed point in $A$ , and at least one two-cycle in $B$ . Of course, each fixed point of the original permutation will be a fixed point of both $A$ and $B$ .

We will try to fix the parities of $A, B$ in two steps. First, we fix the parity of $A$ without changing the commutator. So suppose $A$ is odd (otherwise skip this step). Write $[A, B] = A B A^{-1} \cdot B^{-1}$ , and suppose $B$ has at least one two-cycle $c$ . Then we can pick $A' = Ac$ and $[A', B] = A c B c A^{-1} \cdot B^{-1} = [A, B]$ because the cycles in the cycle representation of $B$ commute and $c^3 = c$ .

Note that in this modification, $A$ (we rename $A'$ back to $A$ ) may lose one or two fixed points (the ones that touch the cycle $c$ ), but if it loses two fixed points then it gains the new two-cycle $c$ .

We can do the same if $B$ has at least two fixed points, namely in the above we can pick $A' = Ac$ where $c$ exchanges the two fixed points.

Next, suppose that $B$ is odd. We will do the exact same thing. Write $[A, B] = A \cdot B A^{-1} B^{-1}$ . If $A^{-1}$ has at least two fixed points (equivalently, $A$ does), pick $c$ to be the two-cycle that swaps them. Alternatively, if $A^{-1}$ (equivalently $A$ ) has at least one two-cycle $d$ , pick $c = d$ . Then take $B' = Bc$ . This permutation is even, and $A \cdot B' A^{-1} B'^{-1} = A \cdot B c A^{-1} c B'^{-1} = A \cdot B A^{-1} B'^{-1} = [A, B]$ again because $c$ commutes with $A^{-1}$ .

All in all, these steps manage to fix the parity (at least) if $A$ has at least two fixed points, and $B$ has at least one two-cycle, or has at least two fixed points. Note that if our initial permutation has at least two fixed points, then in particular $A, B$ both have two fixed points, so the fixing steps go through. Note also that if we perform at least two construction steps (again, this refers to a step where we consider an odd cycle or a pair of even cycles and construct a commutator presentation) in the proof, then since each construction step gives at least one fixed point for $A$ and at least one two-cycle for $B$ , again the fixing steps go through.

We show that this covers all cases: Suppose that there is at most one fixed point (as discussed, otherwise we are done). As discussed, we are done if there are at least two construction steps, so suppose there is only one. If the unique construction step is with an odd cycle, then this odd cycle is of length at least $2i+1 \geq 5$ (since there is at most one fixed point and there are at least five points in total). Then in the construction $A$ gains at least $i \geq 2$ fixed points, and $B$ gains at least $i \geq 2$ two-cycles, so we are done, since at the end $A$ will indeed have at least two fixed points, and $B$ at least one two-cycle, as required.

Suppose then that the only construction step is with a pair of even cycles of lengths $2i, 2j$ . If $i+j \geq 3$ , then $A$ gains at least $i+j-1 \geq 2$ fixed points, and $B$ gains at least $i+j-2 \geq 1$ two-cycle, so we are done. If $i+j = 2$ , we get one fixed point for $A$ from the construction step, and since $i = j$ we gain $i+j \geq 2$ two-cycles for $B$ . In this case, there must indeed be a fixed point for the original permutation (i.e. the cycle structure is precisely $(1, 2, 2)$ ), again since there are at least five points in total. Thus, in this case, $A$ also has the global fixed point, thus at least two in total, so again we are done. Square.
SFT tools for undecidable problems

March 14th, 2023
Last fall, me and Ilkka were asked to contribute to a secret volume dedicated to Iiro Honkala’s 60th birthday. (It is not out yet, but I assume he won’t see this post, and this is sort of spoiled anyway by Fundamenta Informaticae’s policy of taking submissions through arXiv.)

We decided to try out the methods we’ve developed for Game of Life to some problems in coding theory, and had at least some success: we managed to drop the known minimal density of an identifying code on the hexagonal grid from the long-standing record 3/7 (established here by Cohen, Honkala, Lobstein and Zémor) to 53/126. Our paper can be found here. Sorry about all the ergodic theory, density is just annoying to discuss without it.

The way we found codes was to simply write a finite-state automaton for periodic configurations of an SFT, and then apply Karp’s algorithm, I won’t explain this here, just look at the paper. While the codes in our paper were found by ad hoc programs, we also began writing a general toolbox, under the working name Diddy, which can be found in this Git repository.

What I want to write about here is the other half of the tool, which is not (at the time of writing) available anywhere, but already works well-enough that I can give a short demo. Specifically, what we are making is a programming language for making SFTs (subshifts of finite type), which here means shift-invariant (Cantor-)topologically closed subsets of $A^{\mathbb{Z}^d}$ for some finite alphabet $A$ and some dimension $d$ .

The idea is that you specify
- a dimension
- a topology (a graph where $\mathbb{Z}^d$ acts freely and almost transitively),
- an alphabet (of a subshift)
- a first-order formula (with bounded quantifiers) with variables ranging over positions
From this data, a subshift of finite type is computed. The idea is to evolve this into a general tool box for symbolic dynamics, or at least for the parts of it we work on. In particular, we are currently working on integrating density calculation into this framework.

For now, the main thing that has been implemented is comparison of SFTs, i.e. you can define two SFTs and ask whether they are equal as sets. The equality of SFTs is literally an impossible (undecidable) problem. Specifically it is $\Sigma^0_1$ -complete, i.e. in a sense exactly as hard as the halting problem. Nevertheless, the program seems to work well on simple examples that arise in practice.

Here’s a first example:
```
%alphabet 0 1
%SFT fullshift Ao 0=0
%SFT fullshift2 Ao o=o
%SFT not_fullshift Ao o=0
%compare_SFT_pairs
```
Let’s go through what this says. Each line starting with % is a command. The first command sets the alphabet to $\{0, 1\}$ (it’s the default alphabet, so this is mainly for the reader’s benefit). The next three lines define subshifts of finite type, by default in two dimensions, on the standard grid. The %SFT command takes two arguments, the name of the SFT, and a formula defining it, so we are defining three SFTs here. The last command compares all 6 ordered pairs of SFTs for inclusions.

Before we look at the output, let’s try to make sense of the formulas, and explain what these SFTs are supposed to be. First we have the formula Ao 0=0. The symbol A stands for $\forall$ (just like in Walnut). 0=0 simply stands for “true”, as there is no keyword for this yet (we compare the element 0 of the alphabet to itself). We should read this formula as $\forall o \in \mathbb{Z}^2: 0 = 0$ , and the SFT it defines is

$X_1 = \{x \in \{0,1\}^{\mathbb{Z}^2}\;|\; \forall o \in \mathbb{Z}^2: 0 = 0\}$

This, of course, is a full shift, as the name suggests it is intended to be.
The next formula can be interpreted similarly, but now instead of comparing 0 and 0 for equality, we are comparing o to itself. This is interpreted as comparing the values in position o, thus the SFT defined is

$X_2 = \{x \in \{0,1\}^{\mathbb{Z}^2}\;|\; \forall o \in \mathbb{Z}^2: x_o = x_o \}$

Finally, the third formula compares the value in position o to the symbol 0, and defines

$X_3 = \{x \in \{0,1\}^{\mathbb{Z}^2}\;|\; \forall o \in \mathbb{Z}^2: x_o = 0 \}$

This, of course, is the one-point subshift $\{0^{\mathbb{Z}^2}\}$ .

The output of %compare_SFT_pairs, then, should indicate that the two full shifts are equal, and the one-point subshift is strictly smaller than the them. This is indeed what happens:
```
Testing whether fullshift contains fullshift2.
fullshift CONTAINS fullshift2 (radius 1, time 0.0)

Testing whether fullshift contains not_fullshift.
fullshift CONTAINS not_fullshift (radius 1, time 0.002385377883911133)

Testing whether fullshift2 contains fullshift.
fullshift2 CONTAINS fullshift (radius 1, time 0.0)

Testing whether fullshift2 contains not_fullshift.
fullshift2 CONTAINS not_fullshift (radius 1, time 0.0020220279693603516)

Testing whether not_fullshift contains fullshift.
not_fullshift DOES NOT CONTAIN fullshift (radius 1, time 0.0009927749633789062)

Testing whether not_fullshift contains fullshift2.
not_fullshift DOES NOT CONTAIN fullshift2 (radius 1, time 0.0020012855529785156)
```
The time is in seconds, and radius refers to how large blocks we need to look at in the proof. As mentioned, the question of whether $X \subset Y$ holds is literally impossible to solve in general. The way this is checked is basically Wang’s classical partial algorithm for the tiling problem, i.e. for the impossible direction we rely on periodic points.

Specifically, to prove the inclusion $X \subset Y$ , we check that for some $r$ , there is no tiling an $r \times r$ box under the constraints of $X$ such that a forbidden pattern of $Y$ appears. This we check with a SAT solver. For non-inclusion (which is the generally impossible direction), we show that $X$ has a periodic point that contains a forbidden pattern for $Y$ . This works at least if $X$ has dense periodic points, and sometimes works even if it doesn’t. Again, we check this using a SAT solver.

Now let’s look at a more advanced example.
```
%topology hex
%SFT idcode Ao let c u v := v = 1 & u ~ v in
(Ed[o1] c o d) & (Ap[o2] p !@ o -> Eq[o1p1] (c o q & ! c p q) | (c p q & !c o q))
%SFT idcode2
(0,0,0):0 (0,0,1):0 (1,0,0):0 (0,-1,0):0;
(0,0,1):0 (1,1,1):0 (2,0,0):0 (1,-1,0):0;
(0,0,1):0 (1,1,0):0 (1,0,1):0 (2,1,0):0;
(0,0,0):0 (0,0,1):0 (0,-1,0):0 (1,1,0):0 (1,1,1):0 (2,1,0):0;
(0,0,0):0 (0,0,1):0 (1,0,0):0 (0,-1,1):0 (1,-1,0):0 (0,-2,0):0;
(0,0,0):0 (0,0,1):0 (0,-1,0):0 (1,0,1):0 (2,0,0):0 (1,-1,0):0;
(0,0,1):0 (1,0,0):0 (1,0,1):0 (1,1,1):0;
(0,0,0):0 (0,-1,0):0 (1,0,1):0 (1,1,1):0;
(0,0,1):0 (1,0,0):0 (1,1,1):0 (0,-1,1):0 (1,-1,0):0 (1,-1,1):0;
(0,0,1):0 (1,0,0):0 (1,0,1):0 (2,1,0):0 (2,1,1):0 (2,2,1):0;
(0,0,1):0 (1,0,0):0 (1,1,1):0 (2,0,0):0 (2,0,1):0 (2,1,1):0;
%compare_SFT_pairs
```
Here, the topology is the hexagonal one (also known as the honeycomb grid), which looks like this:

The code defines the SFT of identifying codes on this grid in two ways. Let’s recall what an identifying code is: and identifying code on a graph $G = (V, E)$ is a set $C \subset V$ such that, if we write $N[v] = \{u \in V \;|\; \{u, v\} \in E\}$ for $v\in V$ (this is the closed neighborhood of $v$ ), then
- for each $v \in V$ , $N[v] \cap C \neq \emptyset$ , and
- for each $u, v \in V$ , $N[u] \cap C \neq N[v] \cap C$ .
The standard way of thinking about this, and the rationale for the term “identifying code”, is that $C$ is a set of error-detecting nodes, which can detect “defects” in the grid, by reporting an error if their closed neighborhood contains a node with a defect, but the report does not tell which node has the defect.

Assuming at most one defect occurs in the grid, an identifying code precisely allows you to tell, just by looking at the reports of all the error-detecting nodes, whether there is a defect in the grid (due to the first item above) and also identify which node has the defect (by the second item). This explains the word identifying. The word “code” is used simply because all sets studied in coding theory are called codes; accordingly, the elements of $C$ are called codewords.

Of course, a subshift, being a subset of $A^{\mathbb{Z}^d}$ , is not literally a set of codes, but we simply identify a code $C \subset \mathbb{Z}^d$ with its characteristic function, so $A = \{0,1\}$ and $1$ denotes a codeword.

Now let’s look at the formula Ao let c u v := v = 1 & u ~ v in (Ed[o1] c o d) & (Ap[o2] p !@ o -> Eq[o1p1] (c o q & ! c p q) | (c p q & !c o q)) defining the first SFT idcode. We claim that this simply states the definition of an identifying code.

First, as in our first example, Ao quantifies over all positions. The subformula let c u v := v = 1 & u ~ v in defines a predicate that holds in the formula after in. The predicate c u v being defined has two parameters u and v (by default, all variables denote positions on the grid). The predicate says v = 1 & u ~ v, i.e. the position v in the grid holds the symbol 1, and ~ denotes that u and v are adjacent or equal positions. In other words, this predicate says that v is a codeword neighbor of u, or in math notation $v \in N[u] \cap C$ .

After this definition, we have (Ed[o1] c o d) & (Ap[o2] p !@ o -> Eq[o1p1] (c o q & ! c p q) | (c p q & !c o q)). The symbols &, |, ! refer to Boolean operations AND, OR and NOT, so this is the conjunction of two fomulas Ed[o1] c o d and (Ap[o2] p !@ o -> Eq[o1p1] (c o q & ! c p q) | (c p q & !c o q)). The first formula Ed[o1] c o d corresponds to the first item of the definition of an identifying code, and says o must have at least one codeword neighbor d. The symbol E means $\exists$ .

The main thing to explain is in the first formula Ed[o1] c o d is [o1]. This is a technical limitation: all quantifiers except the first one must be bounded in the defining formula. In the definition of an identifying code, we simply say that a set (namely $N[v] \cap C$ ) is nonempty, so when translating to a first-order formula, a natural way would be to say there is some element in the graph which is in this intersection (which could be anywhere), but we must explicitly indicate that we only look at the immediate neighborhood of o. There is much to say about bounded quantifiers, and I may write about this in the future, but not here. In any case, here this is not a real limitation since of course, a codeword neighbor is in particular a neighbor.

Next, we have Ap[o2] p !@ o -> Eq[o1p1] (c o q & ! c p q) | (c p q & !c o q) which is supposed to correspond to the second item. To read this, one must know that our convention is that quantifiers see everything after them unless prevented by parentheses, i.e. (c o q & ! c p q) | (c p q & !c o q) is seen by Eq. The operator a !@ b means “a and b do not denote the same position”.

We can now read the formula in plain English: “for all positions p at most two steps away from o, if p and o are not the same position, there must exist some position q (next to p or o which is a codeword neighbor of exactly one of them”. Apart from the quantifier bounds, this is quite literally the definition of an identifying code, except here we remembered to be careful and not require distinct codeword neighborhoods when the nodes are literally the same; in the official definition above I accidentally left this out; a human reader will presumably read this as a typo (do I guess correctly?), while our program will happily let the identifying codes form an empty SFT, and I certainly did this mistake many times also during testing.

As for the quantifier bounds, we simply gave it a moment of thought to see how big they must be. If in doubt, one can make them larger and check that the SFT does not change.

Ok so that’s all about the definition of idcode. Next let’s look at idcode2. This is simply a long list of forbidden patterns, which we worked out on the blackboard. I won’t try to explain them in this post, because they deal directly with the internal representation of the hexagonal grid, maybe I’ll write about that later. In any case, we can now check that indeed the forbidden patterns are correct, by inspecting the output of our code:
```
Testing whether idcode contains idcode2.
idcode CONTAINS idcode2 (radius 2, time 0.9418075084686279)

Testing whether idcode2 contains idcode.
idcode2 CONTAINS idcode (radius 1, time 0.1818685531616211)
```
Pretty cool, right?
Jónsson-Tarski algebraic subshifts

November 29th, 2022

A big theme in my research is looking at internal algebras in the category of all subshifts and block-maps between them. In this post, we study subshifts in a not-very-well-known variety and prove a little theorem.

Here, a subshift is a shift-invariant closed subset of $A^G$ where $A$ is a finite alphabet (discrete set) and $G$ is some discrete group (which stays fixed during the discussion). It is a dynamical system under the shift-action of $G$ . The category of subshifts has subshifts as objects, and shift-commuting continuous functions between them as morphisms.

Concretely an internal algebra in this category just means that the set of elements of the algebra is a subshift, the operations are given by shift-commuting continuous function, and the algebra axioms hold in the usual set-theoretic sense.

A Jónsson-Tarski algebra is an algebra with a binary operation $w$ and unary operations $p_1, p_2$ , with identities $p_1(w(a, b)) = a$ , $p_2(w(a, b)) = b, w(p_1(a), p_2(a)) = a$ .

The axioms essentially say that if $A$ is a Jónsson-Tarski algebra, then $w$ is an isomorphism from $A \times A$ to $A$ . In particular, a Jónsson-Tarski algebra is either empty, a singleton, or infinite. Conversely, in the category Set, in classical mathematics, any infinite set has the structure of a Jónsson-Tarski algebra.

It is a theme in symbolic dynamics to try to understand various types of finiteness in the category of subshifts (e.g. surjunctivity, amenability and soficity are finiteness properties of groups that have links to cellular automata). Thus, it is of interest to try to understand whether a subshift can be infinite in the Jónsson-Tarski sense, i.e. whether the category of subshifts has internal Jónsson-Tarski algebras.

Another reason why Jónsson-Tarski algebras are interesting from a symbolic dynamical point of view is that the automorphism group of a Jónsson-Tarski algebraic object contains a copy of Thompson’s $V$ . It is known that Thompson’s $V$ embeds in the automorphism group of a one-dimensional SFT, so it is an interesting question whether one can even have a “natural” copy of it.

We show that there are no Jónsson-Tarski algebraic subshifts when the spatially acting group $G$ has subexponential growth, i.e. when the size of balls grows at subexponential rate. This covers e.g. virtually nilpotent groups and the Grigorchuk group.

Theorem. Let $G$ be a finitely-generated group with subexponential growth, and let $X \subset A^G$ be a Jónsson-Tarski algebraic subshift. Then $X$ has at most one point.

Proof. The map $w : X \times X \to X$ is a topological conjugacy between the $G$ -subshift $Y = X \times X$ (under the diagonal action; we can see it as a subshift over alphabet $B = A^2$ ) and $X$ , with inverse $p = p_1 \times p_2 : X \to X \times X$ . These maps are shift-commuting and continuous, thus they are block maps.

Let us recall what this means. Fix a shift-convention, say the action of $G$ is defined by the formula $g \cdot x_h = x_{g^{-1} h}$ . Then $f : X \to Y$ is a block map if there exists $r \geq 0$ such that $f(x)_g$ is determined by the contents of $x|_{g B_r}$ , where $B_r$ is the ball of radius $r$ with respect to some finite generating set, by some uniform local rule. More precisely, there exists $F : A^{B_r} \to B$ such that $f(x)_g = F(P)$ where $P(h) = x_{g h}$ .

Now if $r$ is a radius for our operation $p : X \to Y$ , then for $x \in X$ , $p$ determines from the contents $x_{B_{R+r}}$ the contents of $p(x)_{B_R}$ .

Let $Y = X \times X$ , and observe that in particular since $p$ is a conjugacy, it is surjective. Thus, for a subshift $Z$ writing $c_n(Z) = |{z_{B_n} \;|\; z \in Z}|$ , we must have $c_{R+r}(X) \geq c_R(Y) = c_R(X)^2$ .

In particular $c_{R+kr}(X) \geq c_R(X)^{2^k}$ . But $c_{R+kr}(X) \leq |A|^{B_{R+kr}}$ (this is how many patterns there are in the full shift $A^G$ ), so $|A|^{|B_{R+kr}}| \geq c_R(X)^{2^k}$ , from which we solve $|B_{R+kr}| \geq 2^k \log_2 c_R(X) / \log_2(|A|)$ and get that the group has exponential growth, as soon as $c_R(X) \geq 2$ for any radius $R$ . Square.

The proof does not work for general amenable groups, let alone a general group. I don’t know if there is a smarter version of the proof that uses Følner sequences in place of balls somehow. On the other hand I don’t have an example of a Jónsson Tarski algebraic subshift on any group.
Adventures in OpenAI and (very) basic theory of cellular automata

October 17th, 2022
I decided to try OpenAI out. Having seen some examples of what it can do, I figured a reasonable test case is to see if the AI is able to prove that the composition of two cellular automata is a cellular automaton, with some hints. I used the abstract definition of a cellular automaton — a cellular automaton is a shift-commuting continuous map — because it makes the proof trivial if you know basic topology and basic algebra. Also, I wanted a proof that talks about two very different things to see if the AI can keep up with the context.

Getting OpenAI going took me only a few minutes, which surprised me as I’m not very good with computers. I just made an account and ran “python -m pip install openai” in random folders until I found the correct Python installation. Then I just copied the Q&A example from the website:
```
import os
import openai

openai.api_key = os.getenv("OPENAI_API_KEY")

response = openai.Completion.create(
  model="text-davinci-002",
  prompt="...",
  temperature=0,
  max_tokens=100,
  top_p=1,
  frequency_penalty=0.0,
  presence_penalty=0.0,
  stop=["\n"]
)
```
and tried various prompts in place of “…”. I have no idea what all the other parameters mean. Below, I write some prompt-answer pairs in the following format:

My prompt, i.e. what I sent to OpenAI, is written in normal font, and
the AI then continues as it sees fit, and the response is shown in bold.

Often the AI produced its answer in many pieces, and I appended the response of the AI to my prompt and sent it again, and iterated until fixed point: if the AI thinks the prompt needs no additions, it gives an empty answer, and usually it satisfies itself eventually. A technical detail here is that my prompts were cut by newlines after about 80 characters, and the AI mimicked these cuts, usually sending about 80 characters back. I don’t know if it would have produced better results if I had fed in everything as one paragraph, it was just easier to edit things in the Python IDLE with the newlines. I.e. if it thinks it just needs to think 80 characters ahead, does it still think about what’ll come after? I have no idea.

My general strategy for the experiment was to write a proof, and then remove lines at the end and see if the AI can continue. I then try to humansplain what’s going on, and on some occasions try to make it explain what it’s thinking.

Let’s start by checking if the AI can finish off the proof if I give it the
shift-commutation part and leave out just the very end of the topology part.

A cellular automaton is a shift-commuting continuous function on the full shift $S^{\mathbb{Z}}$ consisting two-way infinite sequences over a finite alphabet $S$. Here is the proof that the function composition of two cellular automata is itself a cellular automaton: First, we check shift-commutation: if $f$ and $g$ are cellular automata, we of course have $f \circ g \circ \sigma = f \circ sigma \circ g = \sigma \circ f \circ g$. Second, for continuity we simply recall from basic topology that the composition of two continuous functions is continuous.

Some variations on multiple runs were “is again continuous.” and “is itself continuous.”

A technical note here: Above, I left the LaTeX uncompiled, to show how the AI sees the prompt. Once it turned out that the AI makes fewer LaTeX errors than me, I decided to compile most of the LaTeX in later examples. Unfortunately, WordPress does not allow LaTeX in bold, so you cannot tell which formulas are part of the prompt and which are written by the AI. This should always be clear from context, or I’ve added [formula by AI] before the formula.

The AI’s answer here is perfect. Does this show an understanding of topology, or even basic logic? I asked a human who’s taken some basic math courses if they could fill in the prompt. They said no, but once I told them the answer they said they definitely should’ve been able to deduce it.

I then tried spoonfeeding the AI little less:

A cellular automaton is […] Second, for continuity we need to show that for any $x \in S^{\mathbb{Z}}$ and any $\epsilon > 0$ , there is a neighborhood $U$ of $x$ such that for all $y \in U$ , $d(f \circ g(x), f \circ g(y)) < \epsilon$ . But this is true because $f$ and $g$ are continuous.

I have omitted the definition and proof of shift-commutation and written […] instead, but I of course fed in the same stuff to the AI. It wrote out the definition correctly, but then realized it can’t easily do the math, so it just wrote that we’re done.

Let’s explore this, and try feeding it a proof, and see if it even recognizes we’re done if I write the entire proof. I hope I didn’t screw up the proof too bad, it’s a little hard to write with the mixed open sets and epsilons, but I went with the AI’s artistic choice.

A cellular automaton is […] Second, for continuity we need to show that for any $x \in S^{\mathbb{Z}}$ and any $\epsilon > 0$ , there is a neighborhood $U$ of $x$ such that for all $y \in U$ , $d(f \circ g(x), f \circ g(y)) < \epsilon$ . To explain in more detail, suppose the $\epsilon$ – $U$ claim is true for $f$ and $g$ separately. We first use the continuity of $f$ to find an open set $U'$ containing $g(x)$ such that if $y \in U'$ then $d(f(g(x)), f(y)) < \epsilon$ . We of course have some $\epsilon'$ such that the $\epsilon'$ -ball around $g(x)$ is contained in $U'$ . Now we use the continuity of $g$ to find open $U$ containing $x$ such that whenever $y \in U$ we have $d(g(x), g(y)) < \epsilon'$ . Namely, then whenever $y \in U$ , we have $g(y) \in U'$ so $d(f(g(x)), f(g(y))) < \epsilon$ which implies $d(f \circ g(x), f \circ g(y)) < \epsilon$ .

Great. But let’s start stripping sentences from the end.

A cellular automaton is […] Second, for continuity we need to show that for any $x \in S^{\mathbb{Z}}$ and any $\epsilon > 0$ ,
there is a neighborhood $U$ of $x$ such that for all $y \in U$ , $d(f \circ g(x), f \circ g(y)) < \epsilon$ . To explain in more detail, suppose the $\epsilon$ – $U$ claim is true for $f$ and $g$ separately. We first use the continuity of $f$ to find an open set $V$ containing $g(x)$ such that if $y \in V$ then $d(f(g(x)), f(y)) < \epsilon$ . We of course have some $\epsilon'$ such that the $\epsilon'$ -ball around $g(x)$ is contained in $V$ . Now we use the continuity of $g$ to find open $U$ containing $x$ such that whenever $y \in U$ we have $d(g(x), g(y)) \epsilon'$ . Namely, then [formula by AI] $y \in U$ we have $g(y) \in U'$ and hence $d(f(g(x)), f(g(y))) < \epsilon$ . So $d(f \circ g(x), f \circ g(y)) < \epsilon$ as desired.

The AI was happy after finishing the first sentence, and I had to add “So” to make it finish the proof. Other than that, still going great. Let’s strip more:

A cellular automaton is […] Second, for continuity we need to show that for any $x \in S^{\mathbb{Z}}$ and any $\epsilon > 0$ , there is a neighborhood $U$ of $x$ such that for all $y \in U$ , $d(f \circ g(x), f \circ g(y)) < \epsilon$ . To explain in more detail, suppose the $\epsilon$ – $U$ claim is true for $f$ and $g$ separately. We first use the continuity of $f$ to find an open set $U'$ containing $g(x)$ such that if $y \in U'$ then $d(f(g(x)), f(y)) < \epsilon$ . We of course have some $\epsilon'$ such that the $\epsilon'$ -ball around $g(x)$ is contained in $U'$ . Now we use the continuity of $g$ to find open $U$ containing $x$ such that if $y \in U$ then $d(g(x), g(y)) < \epsilon'$ . We then have $f \circ g(y) \in U'$ for all $y \in U$ , so $d(f \circ g(x), f \circ g(y)) < \epsilon$ for all $y \in U$ .

Here it writes the incorrect “ $f \circ g(y) \in U'$ ” instead of “ $g(y) \in U'$ ” (and I tried it a few times so it seems to mean it :P). If written by a human I would probably just assume it is a typo. Let’s strip more.

A cellular automaton is […] Second, for continuity we need to show that for any $x \in S^{\mathbb{Z}}$ and any $\epsilon > 0$ , there is a neighborhood $U$ of $x$ such that for all $y \in U$ , $d(f \circ g(x), f \circ g(y)) < \epsilon$ . To explain in more detail, suppose the $\epsilon$ – $U$ claim is true for $f$ and $g$ separately. We first use the continuity of $f$ to find an open set $U'$ containing $g(x)$ such that if $y \in U'$ then $d(f(g(x)), f(y)) < \epsilon$ . We of course have some $\epsilon'$ such that the $\epsilon'$ -ball around $g(x)$ is contained in $U'$ . Now we use the continuity of $g$ to find an open set $U''$ containing $x$ such that if $y \in U''$ then $d(g(x), g(y)) < \epsilon'$ . We then have $f \circ g(y) \in f(U')$ for all $y \in U''$ , so $d(f \circ g(x), f \circ g(y)) < \epsilon$ for all $y \in U''$ .

Instead of “ $f \circ g(y) \in f(U')$ for all $y \in U''$ ” it should of course write $g(y) \in U'$ for all $y \in U''$ . Again it looks like a typo. If $f$ were a homeomorphism this would be basically correct… Let’s strip more:

A cellular automaton is […] Second, for continuity we need to show that for any $x \in S^{\mathbb{Z}}$ and any $\epsilon > 0$ , there is a neighborhood $U$ of $x$ such that for all $y \in U$ , $d(f \circ g(x), f \circ g(y)) < \epsilon$ . To explain in more detail, suppose the $\epsilon$ – $U$ claim is true for $f$ and $g$ separately. We first use the continuity of $f$ to find an open set $U'$ containing $g(x)$ such that if $y \in U'$ then $d(f(g(x)), f(y)) < \epsilon$ . We of course have some open set $U''$ containing $x$ such that if $y \in U''$ then $d(g(x), g(y)) < \epsilon$ . Now we can take $U = U' \cap U''$ to be the desired open set containing $x$ such that if $y \in U$ then $d(f \circ g(x), f \circ g(y)) < \epsilon$ .

This no longer looks meaningful. But let’s remove even more:

A cellular automaton is […] Second, for continuity we need to show that for any $x \in S^\mathbb{Z}$ and any $\epsilon > 0$ , there is a neighborhood $U$ of $x$ such that for all $y \in U$ , $d(f \circ g(x), f \circ g(y)) < \epsilon$ . To explain in more detail, suppose the $\epsilon$ – $U$ claim is true for $f$ and $g$ separately. We first use the continuity of $f$ to find an open set $U'$ containing $g(x)$ such that for all $y \in U'$ , $d(f(g(x)), f(g(y))) < \epsilon/2$ . Then we use the continuity of $g$ to find an open set $U''$ containing $x$ such that for all $y \in U''$ , $d(g(x), g(y)) < \epsilon/2$ . Finally, we set $U = U' \cap U''$ . Then for all $y \in U$ , we have $d(f(g(x)), f(g(y))) < \epsilon/2$ and $d(g(x), g(y)) < \epsilon/2$ , so $d(f \circ g(x), f \circ g(y)) < \epsilon$ .

Suddenly, we see what appears to be some triangle inequality pattern, which indeed can appear when you are considering two functions. It doesn’t make sense here though. This is starting to feel like abuse, but let’s force it to tell us the entire proof of continuity of composition from scratch, using the definition the AI chose.

A cellular automaton is […] Second, for continuity we need to show that for any $x \in S^{\mathbb{Z}}$ and any $\epsilon > 0$ , there is a neighborhood $U$ of $x$ such that for all $y \in U$ , $d(f \circ g(x), f \circ g(y)) < \epsilon$ . To explain in more detail, suppose the $\epsilon$ – $U$ claim is true for $f$ and $g$ separately. We first show that it is true for $g$ :

Errr… we show what is true for $g$ ? Reminds one of the famous “Show that $G = H$ are isomorphic.” joke/story. The AI thinks it’s done at this point, but I add “We” at the end to prompt it to continue, and it continues as follows:

[…] show that it is true for $g$ : We have $d(g(x), g(y)) = d(g(x), g(x)) + d(g(x), g(y)) - d(g(x), g(y)) = d(g(x), g(y))$ because $g$ is continuous. So, if $d(g(x), g(y)) < \epsilon$ , then $d(f \circ g(x), f \circ g(y)) < \epsilon$ because $f$ is continuous. So, it is enough to show that for any $x \in S^{\mathbb{Z}}$ and any $\epsilon > 0$ , there is a neighborhood $U$ of $x$ such that for all $y \in U$ , $d(g(x), g(y)) < \epsilon$ .

Ok buddy, you tried your best.

I think the AI may been kind of unlucky here. It’s perhaps outputting line by line due to my ~80 character splitting, and it definitely makes sense that when it is asked to show continuity it writes out the epsilon-delta definition, or rather the epsilon-U definition.

And then, once you write the epsilon-U definition, you have put yourself in a position where you have to start doing basic topology. The AI clearly knows a lot of the relevant things but it doesn’t know how to do this hard a proof, so you just get a lot of nonsense out. A quite human interaction in a way…

<tangent> Side note: why does the AI write an epsilon-U definition? Well, using $U$ kind of makes sense because $S^{\mathbb{Z}}$ is not obviously a metric space. Indeed, I haven’t defined its topology to the AI, and in fact the proof goes through even if we use a non-metrizable topology, just that our cellular automata would not be the standard ones. But then why isn’t it using a $U$ – $V$ definition? Maybe the AI sometimes “thinks” cellular automata are functions from $S^{\mathbb{Z}}$ to real numbers (given what happens in some of the wilder examples below). By the way, if you ask directly, it definitely knows the type signature of a cellular automaton, and more:

A cellular automaton is a shift-commuting continuous function on the full
shift $S^{\mathbb{Z}}$ consisting two-way infinite sequences over a finite alphabet $S$ . The image of a two-way infinite sequence under a cellular automaton is of course also a two-way infinite sequence. Or in notation, [formula by AI] $\varphi:S^\mathbb{Z}\to S^\mathbb{Z}$ . In even more detail, this means that if $x \in S^\mathbb{Z}$ then [formula by AI] $\varphi(x)_i=\varphi(x_{i-r},\ldots,x_i,\ldots,x_{i+r})$ for some $r \in \mathbb{Z}_{\geq 0}$ (see \cite{L}). Here, \cite{L} is the reference for the definition of cellular automata.

Note that I did not actually say what the type of a cellular automaton is: “a function on $S^{\mathbb{Z}}$ ” really only specifies the domain. In fact, human referees have complained to me sometimes that the codomain of a cellular automaton is not given, as I always forget this. I’m therefore glad to see it’s obvious even to OpenAI… Of course as the end of the paragraph shows, it even knows the combinatorial characterization of cellular automata (and even abuses notation like a champ). Of course it’s not deducing the characterization, even better, it cites the standard reference “\cite{L}“, which we of course all love, cherish, and have in our bookshelf.</tangent>

Anyway as mentioned, I think the AI was a little unlucky. At the outset (right after stating what we need to prove), we can simply add “simply” to clarify we just want a quick proof, and the AI delivers:

A cellular automaton is […] Second, for continuity we simply note that the composition of two continuous functions is continuous.

This is perfect. But let’s try to get it to somehow indicate that this is something non-trivial that we simply know. I added “We” at the end, and get:

A cellular automaton is […] Second, for continuity we simply note that the composition of two continuous functions is continuous.
We conclude that the composition of two cellular automata is a cellular automaton.

Well, yes, but not what I was looking for. Another attempt:

A cellular automaton is […] Second, for continuity we simply note that the composition of two continuous functions is continuous. In more detail, let $f$ and $g$ be cellular automata. Let $x \in S^{\mathbb{Z}}$ and $\varepsilon > 0$ . Since $f$ is continuous, there is a $\delta > 0$ such that $d(f(x),f(y)) < \varepsilon$ whenever $d(x,y) < \delta$ . Since $g$ is continuous, there is a $\delta' > 0$ such that $d(g(x),g(y)) < \delta$ whenever $d(x,y) < \delta'$ . Then $d(f \circ g(x),f \circ g(y)) < \varepsilon$ whenever $d(x,y) < \delta'$ .
\end{proof}

This is pretty much perfect. At the end the “\end{proof}” is kind of funny since it didn’t start a proof, but it’s doing this line by line so kind of makes sense: at some point it realizes it’s a long proof so it should be in a proof environment. It just didn’t realize it would be long when it started… Great stuff, though here it’s not clear to me that this is not simply plagiarized from somewhere. I mean, “composition of two continuous functions is continuous” is proved in many places, and the proof that was written is very textbook.

So let’s try renaming our cellular automata:

A cellular automaton is […] Second, for continuity we simply note that the composition of two continuous functions is continuous. In more detail, let $p$ and $a$ be cellular automata. Let $x \in S^{\mathbb{Z}}$ and $y \in S^{\mathbb{Z}}$ be two-way infinite sequences over a finite alphabet $S$ . Let $\varepsilon > 0$ . Since $p$ is continuous, there exists $\delta > 0$ such that for all $z \in S^\mathbb{Z}$ with $d(x,z) < \delta$ , we have $d(p(x),p(z)) < \epsilon$ . Since $a$ is continuous, there exists $\gamma > 0$ such that for all $w \in S^{\mathbb{Z}}$ with $d(y,w) <\gamma$ , we have $d(a(y),a(w)) < \delta$ . Now, for all $v \in S^{\mathbb{Z}}$ with $d(v,y) < \gamma$ , we have $d(p(a(v)),p(a(y))) < \epsilon$ . Since $p \circ a$ is continuous, we have $p \circ a \circ \sigma = p \circ \sigma \circ a = \sigma \circ p \circ a$ .

Looks great, apart from the last sentence, where the AI suddenly starts talking about shift-commutation again. Probably it’s just getting fed up with me.

Ok, what about the algebra half of the proof? I switch the order of the defining properties and now drop the algebra part:

A cellular automaton is a continuous shift-commuting function on
the full shift $S^{\mathbb{Z}}$ consisting two-way infinite sequences over a finite alphabet $S$ . Here is the proof that the function composition of two cellular automata is itself a cellular automaton: First, we check continuity: if $f$ and $g$ are cellular automata, we simply recall from basic topology that the composition of two continuous functions is continuous. For shift-commutation, writing $\sigma$ for the shift, we combine $\sigma \circ f = f \circ \sigma$ and $\sigma \circ g = g \circ \sigma$ to move the shift over $f$ and $g$ separately as follows: $\sigma \circ f \circ g = \sigma \circ (g \circ f) = (\sigma \circ g) \circ (\sigma \circ f) = g \circ (\sigma \circ f) = g \circ (f \circ \sigma) = (g \circ f) \circ \sigma = f \circ g \circ \sigma$.

As you can see, the response is ok except it randomly writes the formula
for distributivity in there. (I’ve left the LaTeX uncompiled here to show where my prompt ends and the answer starts, but it should compile fine.) Another attempt gives “ $\sigma \circ (f \circ g) = (\sigma \circ f) \circ g = (f \circ \sigma) \circ g = f \circ (\sigma \circ g) = f \circ (g \circ \sigma) = f \circ g \circ \sigma$ .” which is perfect.

Let’s start stripping.

A cellular automaton is […] For shift-commutation, writing
$\sigma$ for the shift, we combine $\sigma \circ f = f \circ \sigma$ and $\sigma \circ g = g \circ \sigma$ to move the shift over $f$ and [formula by AI] $g$ .

It thinks it’s done. Very funny. Let’s ask for details:

A cellular automaton is […] For shift-commutation, writing
$\sigma$ for the shift, we combine $\sigma \circ f = f \circ \sigma$ and $\sigma \circ g = g \circ \sigma$ to move the shift over $f$ and $g$ . Explicitly, [formula by AI] $\sigma \circ (f \circ g) = (\sigma \circ f) \circ g = (f \circ \sigma) \circ g = f \circ (\sigma \circ g) = f \circ (g \circ \sigma) = (f \circ g) \circ \sigma$

Looks perfect. Let’s try again:

A cellular automaton is […] For shift-commutation, writing
$\sigma$ for the shift, we combine $\sigma \circ f = f \circ \sigma$ and $\sigma \circ g = g \circ \sigma$ to move the shift over $f$ and $g$ . More explicitly, we calculate
\begin{align*}
\sigma \circ (f \circ g) &= (\sigma \circ f) \circ g \
\text{(by definition of composition)} \
(f \circ \sigma) \circ g \
\text{(by shift-commutation of $f$)} \
f \circ (\sigma \circ g) \
\text{(by definition of composition)} \
f \circ (g \circ \sigma) \
\text{(by shift-commutation of $g$)} \
(f \circ g) \circ \sigma \
\text{(by definition of composition)} \
(f \circ g) \circ \sigma \
\text{(by definition of composition)} \
(f \circ g) \circ \sigma \
…

The AI seems to go into an infinite loop, but the proof is basically correct otherwise. If you add the \end, it compiles and even looks remotely reasonable when compiled (yet unreasonable enough that I can’t imagine it’s directly copied from anywhere). So this is also quite nice.

Let’s remove even more:

A cellular automaton is […] For shift-commutation, writing
$\sigma$ for the shift, we combine $\sigma \circ f =
f \circ \sigma$ with $\sigma \circ g = g \circ \sigma$ to get
$\sigma \circ (f \circ g) = (f \circ g) \circ \sigma$.

Note that it produces from a word description of shift-commutation
the correct formulas, and then states the correct conclusion.
Now it did not do the actual algebra, but this argument is again quite passable.

A cellular automaton is […] For shift-commutation, writing
$\sigma$ for the shift, we have
$\sigma(f\circ g)(x)=f(\sigma(g(x)))=f(g(\sigma(x)))=f(g(x))=\sigma(f(g(x)))=\sigma(f\circ g)(x)$
where the first and third equalities are by definition of cellular
automaton, the second and fourth equalities are by shift-commutation of $g$ and $f$ , respectively, and the last equality is by definition of composition.

This one is amazing. It writes the full computation, and at the end also explains all the steps. But it seems to be mostly garbage. Let’s ask it to explain
shift-commutation from scratch, and see if it does better.

A cellular automaton is […] For shift-commutation, we have to show that $g(f(x))$ is shift-equivalent to $f(g(x))$ for all $x\in S^\mathbb{Z}$ . This is a simple consequence of the fact that $f$ and $g$ are shift-commuting: $g(f(x))_n = g(f(x_{n-k})) = g(f(x)_{n-k}) = f(g(x))_n$ for all $n\in\mathbb{Z}$ and $k\in\mathbb{Z}$ .

This is of course nonsense, but interesting. Of course “ $g(f(x))$ is shift-equivalent to $f(g(x))$ ” is not what we should show. It would have been quite striking if it had named the shift and given an algebraic proof, and I did not expect that to happen. Instead it just writes a commutation type formula, which is really the only simple thing you can do without naming the shift, if you want to write something where the “types” are correct. And of course we need to show commutation of some kind, making this even more understandable.

The rest of the proof is just sort of random formulas. There is certainly some structure: the AI starts using subscripts with a $k$ , and it remembers to quantify $k$ afterward, and the formulas are indeed very shifty, although they do not quite parse.

Of course, the AI also uses the strange word “shift-equivalent“. This is a technical term in symbolic dynamics, and if the OpenAI is widely-read in this field, it would’ve seen “shift-equivalent” near objects like $S^{\mathbb{Z}}$ . Is it using this term because it knows symbolic dynamics, or is it pure chance that it guessed a term like this? I am guessing the latter, but who knows. This term doesn’t really come up in the rest of the proof. Let’s press on this term, and ask what this means:

A cellular automaton is […] For shift-commutation, we have to show that $g(f(x))$ is shift-equivalent to $f(g(x))$ , where we recall that shift-equivalent means that there is a homeomorphism of $S^\mathbb{Z}$ that maps $g(f(x))$ to $f(g(x))$ and commutes with the shift. To show this, we define the homeomorphism $h$ by $h(y)_i = g(f(y))_{i+1}$ . Then $h$ is a homeomorphism of $S^{\mathbb{Z}}$ that maps $g(f(x))$ to $f(g(x))$ and commutes with the shift. Thus, the composition of two cellular automata is a cellular automaton.

Wow. So a shift-equivalence between two points $x$ , $y$ means that a reversible CA maps $x$ to $y$ . Well, why not…

This is probably a good point to end the post. In conclusion, the AI seems to understand language and basic logic, i.e. what it’s supposed to prove at each point. It is also pretty good at remembering the context, knows basic algebra, and is good at LaTeX. It has also clearly read some cellular automata and topology literature. However, it is not able to make a nontrivial proof, and there are frequent hints that it does not really understand what’s going on. I don’t know what the takeaway is.