The Conjugacy Relation on One-sided Subshifts is Non-treeable

This paper demonstrates that the conjugacy relation on one-sided subshifts over the binary alphabet is neither treeable nor amenable from the perspective of descriptive set theory.

The Gist

Here is an explanation of the paper "The Conjugacy Relation on One-Sided Subshifts is Non-Treeable" using simple language, analogies, and metaphors.

The Big Picture: Sorting Infinite Patterns

Imagine you have a giant, infinite library. Inside this library are millions of books, but these aren't normal books. They are infinite tapes of symbols (like a long string of 0s and 1s: 0100110...).

In mathematics, these tapes represent dynamical systems. Think of a tape as a movie that never ends. Every time you press "play" (apply a shift), the movie moves forward one frame.

The Problem:
Mathematicians want to organize this library. They want to know: When are two of these infinite tapes essentially the same?

If you can take Tape A, run it through a specific "translator" machine, and it turns perfectly into Tape B, then they are considered conjugate (or isomorphic). They are just different versions of the same underlying story.

The question the paper answers is: How hard is it to sort these tapes into groups of "the same"?

The "Tree" Metaphor: How We Sort Things

To understand the paper's main discovery, we need to understand what it means for a sorting problem to be "Treeable."

Imagine you are trying to sort a pile of mixed-up socks.

• Treeable (Easy-ish): Imagine you have a flowchart (a tree). You ask a simple question: "Is it red?" If yes, go left. "Is it wool?" If yes, go right. Eventually, you reach a leaf on the tree, and that leaf tells you exactly which pile the sock belongs to. If you can sort everything using a flowchart where every path is finite and simple, the problem is "treeable." It's structured and manageable.
• Non-Treeable (Chaotic): Now, imagine the socks are so weirdly connected that no flowchart works. To know if Sock A matches Sock B, you might have to check a path that loops back on itself, or requires checking an infinite number of weird conditions that don't fit into a neat hierarchy. The connections are too tangled to be drawn as a simple tree.

The Paper's Conclusion:
The author, Ruiwen Li, proves that sorting these specific infinite tapes (called one-sided subshifts) is Non-Treeable.

In plain English: The rules for deciding if two of these infinite patterns are the same are so incredibly complex and tangled that you cannot organize them using a simple, step-by-step flowchart.

The "Two-Sided" vs. "One-Sided" Twist

The paper focuses on a specific type of tape: One-sided.

• Two-sided tapes go infinitely in both directions: ...010101... (like a never-ending road).
• One-sided tapes start at the beginning and go infinitely forward: 010101... (like a movie starting at time zero).

Mathematicians already knew that sorting the "Two-sided" tapes was messy. But the "One-sided" tapes were a mystery. Some thought they might be simpler, maybe even "Treeable" (sortable with a flowchart).

Li proves that even the One-sided tapes are just as messy as the Two-sided ones. You cannot simplify the sorting process just because the tape has a starting point.

The "Magic Alphabet" Analogy

To prove this, Li had to build a special "test case."

1. The Setup: He created a special alphabet with 13 symbols (like a, b, #, etc.).
2. The Rules: He defined a set of "forbidden words." If a tape contains a specific forbidden combination, it's not allowed in the library.
3. The Group of Transformations: He invented a group of "magic machines" (mathematical functions) that could swap symbols around in very specific ways.
   • Imagine a machine that says: "If you see an a followed by a b, turn the a into a b."
   • He created 6 of these machines.
4. The Chaos: He showed that when you combine these machines, they create a structure so complex (mathematically, a group containing a "free product" of smaller groups) that it generates infinite loops and tangled connections.
5. The Translation: Finally, he built a "decoder ring" (a mathematical map) that translates these complex, multi-symbol tapes into simple binary tapes (just 0s and 1s).

The Result: Because the complex machines create a tangled mess that cannot be sorted by a tree, and because this mess can be perfectly translated into simple 0s and 1s, the simple 0s and 1s tapes must also be unsortable by a tree.

Why Does This Matter?

You might ask, "Who cares about sorting infinite tapes?"

1. Complexity Theory: This paper helps us understand the "difficulty" of mathematical problems. It tells us that some problems in nature (which can be modeled by these systems) are fundamentally chaotic. There is no "easy button" or simple algorithm to solve them.
2. Limits of Classification: It tells us that for certain types of dynamical systems, we can never hope to create a perfect, simple catalog. No matter how smart our computer or flowchart is, the relationships between these systems are too deep and twisted to be fully captured by a simple hierarchy.
3. The "Tree" Metaphor in Real Life: Think of it like trying to sort a massive social network where everyone is connected in weird, looping ways. If the network is "treeable," you can find a clear leader for every group. If it's "non-treeable," the connections are so circular and complex that you can't find a clear hierarchy. Li proved that these mathematical systems are the latter.

Summary

• The Goal: Sort infinite patterns of 0s and 1s to see which ones are "the same."
• The Question: Can we sort them using a simple, step-by-step flowchart (a tree)?
• The Answer: No.
• The Proof: The author built a complex mathematical machine that creates tangled connections. He showed that even when you simplify this machine down to just 0s and 1s, the tangled connections remain.
• The Takeaway: The universe of these one-sided patterns is wildly complex. It resists simple organization, proving that some mathematical structures are inherently chaotic and cannot be tamed by simple rules.

Technical Summary

Here is a detailed technical summary of the paper "The Conjugacy Relation on One-Sided Subshifts is Non-Treeable" by Ruiwen Li.

1. Problem Statement

The paper addresses a fundamental question in descriptive set theory regarding the complexity of classifying dynamical systems. Specifically, it investigates the conjugacy relation on one-sided subshifts (dynamical systems defined on the space $A^{\mathbb{N}}$ where $A$ is a finite alphabet).

• Context: The complexity of equivalence relations is measured using Borel reducibility ($\leq_B$). A relation is smooth if it is reducible to the identity on $\mathbb{R}$, hyperfinite if it is reducible to $E_0$, and universal for countable Borel equivalence relations if it is equivalent to $E_\infty$.
• Known Results:
  • For two-sided subshifts (invertible systems on $A^{\mathbb{Z}}$), Clemens [5] proved the conjugacy relation is Borel bireducible with $E_\infty$ (universal).
  • Deka et al. [7] recently showed that for two-sided subshifts with the specification property, the relation is non-treeable and non-amenable.
• The Gap: While the two-sided case is well-understood, the complexity of the conjugacy relation on one-sided subshifts (non-invertible systems) remained an open question. Specifically, Clemens [5] asked for the exact complexity of isomorphism for one-sided shifts on $\{0, 1\}^{\mathbb{N}}$.
• Objective: To determine if the conjugacy relation on transitive one-sided subshifts with alphabet $\{0, 1\}$ is treeable or amenable. If it is neither, it implies a high level of complexity, distinct from hyperfinite relations.

2. Methodology

The author employs a reduction strategy, constructing a specific countable group action that induces a non-treeable, non-amenable equivalence relation, and then embedding this structure into the space of one-sided subshifts.

A. Construction of a "Hard" Equivalence Relation

1. Alphabet Expansion: The author defines a large alphabet $A$ containing symbols $\{a_i, \tilde{a}_i, \# \mid 1 \leq i \leq 6\}$.
2. Forbidden Words Subshifts: A class of subshifts $S(A)$ is defined on $A^{\mathbb{Z}}$ by forbidding words of the form $\#w\#$ where $w$ belongs to a subset $R \subset (A \setminus \{\#\})^*_{odd}$.
3. Group Action:
   • A subgroup $\Gamma \subset \text{Aut}(A^{\mathbb{Z}})$ is constructed, generated by six specific automorphisms $\{f_1, \dots, f_6\}$.
   • These automorphisms are defined via block codes $g_i$ that swap $a_i$ and $\tilde{a}_i$ based on the following symbol, preserving the structure of the forbidden words.
   • Key Group Property: The group $\Gamma$ is isomorphic to $(\mathbb{Z}_2 * \mathbb{Z}_2 * \mathbb{Z}_2)^2$. Crucially, this group contains a copy of $F_2 \times F_2$ (the direct product of two free groups on two generators) and has no "almost trivial" non-identity elements.
4. Induced Action: The group $\Gamma$ acts on the space $S(A)$ by mapping a subshift $X(R)$ to $X(f^*(R))$. The induced equivalence relation $E$ (where $X_1 E X_2$ if they are in the same orbit) is proven to be non-treeable and non-amenable based on the properties of $\Gamma$ (referencing Pemantle–Peres [19] and Kechris [10]).

B. Reduction to One-Sided Subshifts

To apply these results to one-sided subshifts on the binary alphabet $\{0, 1\}$, the author constructs a Borel reduction (specifically, a Borel injection preserving the equivalence relation):

1. Encoding Map ($\rho$): A map $\rho: A \to \{0, 1\}^{22}$ is defined. Each symbol in the large alphabet $A$ is mapped to a unique binary word of length 22.
   • The encoding is designed to be uniquely readable (synchronization property), ensuring that the boundaries of the encoded symbols can be recovered from the binary sequence.
2. Transformation ($\phi$): For a two-sided subshift $X \in S(A)$, the map $\phi(X)$ generates a one-sided subshift on $\{0, 1\}^{\mathbb{N}}$ by concatenating the codes of the sequences in $X$ and taking the orbit closure under the shift.
3. Conjugacy Preservation: The author proves that if $X_1$ and $X_2$ are conjugate via an element of $\Gamma$ (i.e., $X_1 E X_2$), then their images $\phi(X_1)$ and $\phi(X_2)$ are conjugate as one-sided subshifts.
   • This is achieved by constructing a specific conjugacy map $h$ on the binary space that mimics the action of the automorphisms $f_i$ on the encoded sequences.

3. Key Contributions

• Resolution of Clemens' Question: The paper provides a partial answer to Clemens' question regarding the complexity of one-sided shifts. It establishes that the relation is not "simple" (i.e., not treeable or amenable).
• Extension to Non-Invertible Systems: It successfully adapts techniques previously used for two-sided (invertible) subshifts to the one-sided (non-invertible) setting, overcoming the difficulty that the shift map is not a homeomorphism in the one-sided case.
• Explicit Construction: The paper provides an explicit construction of the reduction map $\phi$ and the group $\Gamma$, demonstrating that even with the minimal alphabet $\{0, 1\}$, the complexity is high.

4. Main Results

Theorem 1.2: The conjugacy relation on transitive one-sided subshifts with the alphabet set $\{0, 1\}$ is a non-treeable and non-amenable countable Borel equivalence relation.

• Non-treeable: The relation cannot be represented by a Borel acyclic graph where connected components correspond to equivalence classes.
• Non-amenable: The relation does not admit an invariant mean (it is not hyperfinite).
• Implication: Since every hyperfinite equivalence relation is both treeable and amenable, this result implies that the conjugacy relation on one-sided subshifts is strictly more complex than any hyperfinite relation. It sits at a higher level in the hierarchy of countable Borel equivalence relations.

5. Significance

• Descriptive Dynamics: This work bridges a gap in the classification of dynamical systems. It confirms that the complexity of classifying one-sided subshifts is comparable to the most complex countable equivalence relations known (like $E_\infty$), rather than being simpler due to the lack of invertibility.
• Methodological Advancement: The technique of encoding a complex group action into a binary one-sided shift via a uniquely readable code provides a robust tool for future investigations into the complexity of other non-invertible dynamical systems.
• Theoretical Boundary: It clarifies the boundary between "classifiable" (hyperfinite) and "non-classifiable" systems in topological dynamics, showing that even for the simplest alphabet, the conjugacy problem is inherently difficult.

In summary, Ruiwen Li proves that the problem of determining if two one-sided subshifts on $\{0, 1\}$ are conjugate is computationally and structurally very complex, ruling out the possibility of a "simple" classification scheme based on countable structures.