Cantor-Bendixson ranks of one-dimensional subshifts

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

SHIFT HAPPENS

Cantor-Bendixson ranks of one-dimensional subshifts

Like this:

Leave a Reply Cancel reply

Cantor-Bendixson ranks of one-dimensional subshifts

Share this:

Like this:

Leave a Reply Cancel reply