Design a site like this with WordPress.com

SHIFT HAPPENS

Month: April 2023

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.