Speedups of linearly recurrent subshifts

This paper proves that the homeomorphic speedup of a linearly recurrent two-sided subshift preserves the property of linear recurrence, thereby demonstrating that this strong form of minimality is invariant under such time changes.

The Gist

Here is an explanation of Henk Bruin's paper, "Speedups of linearly recurrent subshifts," translated into everyday language using analogies.

The Big Picture: The "Fast-Forward" Button

Imagine you are watching a movie on a loop. This movie represents a dynamical system (a mathematical model of how things change over time). In this paper, the "movie" is a subshift, which is essentially an infinite sequence of symbols (like a never-ending string of letters or colors) that follows specific rules.

Now, imagine you have a remote control with a "Fast-Forward" button. But here's the catch: you can't just press it once for the whole movie. Instead, the button works differently depending on what scene you are currently watching.

• If the scene is a slow conversation, the button skips 1 frame.
• If the scene is an action sequence, the button skips 5 frames.
• If the scene is a car chase, it skips 10 frames.

This variable "skip" is called a speedup. The paper asks a simple but deep question: If the original movie has a very specific, orderly rhythm, does the "fast-forwarded" version keep that same rhythm?

The Key Concept: "Linear Recurrence"

To understand the answer, we need to understand what the author means by Linearly Recurrent.

Think of a Linearly Recurrent system like a well-organized library or a highly predictable train schedule.

• The Rule: If you see a specific book (or a specific word in the movie script) on the shelf, you are guaranteed to see that same book again very soon.
• The Guarantee: The time you have to wait to see it again is proportional to the size of the book. If the book is 10 pages long, you won't have to wait 1,000 pages to see it again; you'll see it within, say, 20 pages.
• Why it matters: This "orderliness" is a very strong form of stability. It means the system isn't chaotic; it's tightly knit. Examples include patterns found in nature (like the arrangement of seeds in a sunflower) or specific types of music rhythms.

The Problem: Does Speeding Up Break the Order?

The author, Henk Bruin, investigates what happens when you apply that variable "Fast-Forward" button to these orderly systems.

1. The Fear: When you skip frames unevenly, you might break the pattern. You might skip a crucial part of a sentence, making the story nonsensical. In math terms, you might destroy the "linear recurrence," turning a predictable system into a chaotic mess.
2. The Discovery: Bruin proves that for a specific type of system (called a two-sided subshift, which is like a movie that plays infinitely in both directions, past and future), the order survives.

The Main Result (Theorem 1.1):
If you take a perfectly orderly, linearly recurrent system and apply a continuous "Fast-Forward" button (where the skip amount changes smoothly based on the current scene), the resulting system is still linearly recurrent. The rhythm might change speed, but the type of rhythm remains the same.

How Did He Prove It? (The "Group Extension" Analogy)

Proving this wasn't easy. Bruin had to look under the hood of the "Fast-Forward" mechanism. Here is the analogy he used:

Imagine the original movie is a train moving on a track.

• The Track: The sequence of letters (the subshift).
• The Train: The movement along the track.

When you apply the speedup, you aren't just moving the train faster; you are effectively creating multiple parallel tracks that the train jumps between.

• Imagine the train has $c$ different "lanes" it can be in.
• When the train hits a specific "Fast-Forward" zone, it doesn't just jump forward; it might also switch lanes.
• The paper shows that these lane-switches follow a strict set of rules, like a dance choreography or a permutation puzzle.

Bruin realized that the whole system (the train + the lane switching) can be modeled as a Group Extension.

• Think of the "Group" as a set of dance moves (like "switch left," "switch right," "stay put").
• The "Extension" is the combination of the train moving forward plus the dancer switching moves.

He proved that because the original train schedule was so orderly (linearly recurrent), the "dance moves" (the lane switching) are also orderly. Since both the train and the dance are orderly, the whole combined system remains orderly.

Why Should You Care?

You might ask, "Who cares about infinite letter sequences?"

1. Predictability in Chaos: This research helps mathematicians understand which systems remain predictable even when you change the rules of time. It tells us that "order" is a robust property.
2. Real-World Applications: These mathematical models appear in:
   • Quasicrystals: Materials that have ordered structures but no repeating patterns (like the Fibonacci sequence).
   • Cryptography: Understanding how patterns repeat (or don't) is vital for encryption.
   • Computer Science: It relates to how data is compressed and how algorithms process streams of information.

The Takeaway

Henk Bruin's paper is a mathematical proof that order is resilient. Even if you speed up a highly structured, rhythmic system in a complex, variable way, you cannot destroy its fundamental predictability. The "Fast-Forward" button changes the tempo, but it doesn't break the song.

Technical Summary

Here is a detailed technical summary of the paper "Speedups of linearly recurrent subshifts" by Henk Bruin.

1. Problem Statement

The paper addresses the behavior of speedups in discrete-time dynamical systems, specifically within the context of subshifts (symbolic dynamical systems).

• Definition of Speedup: Given a dynamical system $(X, T)$, a speedup is a new system $(X, S)$ where $S(x) = T^{p(x)}(x)$, and $p: X \to \mathbb{N}$ is a continuous "jump function." This effectively moves the system forward along the $T$-orbits at a variable but bounded rate.
• The Core Question: Which dynamical properties are preserved under homeomorphic speedups? Specifically, the paper investigates linear recurrence, a strong form of minimality characterized by the property that every finite word $w$ appearing in a sequence reappears within a gap bounded by $L|w|$ (where $L$ is a constant).
• Context: While properties like minimality and unique ergodicity are known to be preserved under certain conditions, the preservation of linear recurrence (which implies low word complexity and specific structural rigidity) was an open question for general subshifts. The author focuses on two-sided subshifts where the speedup map $S$ is a homeomorphism (invertible).

2. Methodology

The proof strategy relies on decomposing the speedup dynamics into a group extension (skew-product) structure and analyzing the recurrence properties of this extension.

A. Preliminaries and Complexity Estimates

• The author first establishes that if a subshift has linear word complexity ($p(n) \leq Kn$), its speedup also has linear complexity. However, linear complexity alone does not imply linear recurrence (e.g., Sturmian shifts of unbounded type).
• The paper proves that for minimal systems, a transitive speedup is necessarily minimal.

B. Finite Non-Abelian Group Extensions

A significant portion of the methodology is dedicated to the theory of skew-products over Cantor sets with finite non-abelian groups.

• Essential Values: The author defines local essential value sets $G_x \subseteq G$ for a skew-product $F(x, g) = (T(x), g \cdot \phi(x))$.
• Piecewise Constancy: It is proven that the map $x \mapsto G_x$ is piecewise constant.
• Ergodicity and Minimality: Using results from Furstenberg and Lemma 3.2, the paper demonstrates that if the base system is uniquely ergodic and the skew-product is ergodic with respect to the product measure, the skew-product is uniquely ergodic and minimal. This is crucial for establishing recurrence in the fiber direction.

C. The Group Extension Construction for Speedups

The core technical innovation is the construction of a specific group extension to model the speedup:

1. Return Words: The original shift $(X, \sigma)$ is analyzed using return words relative to a long word $w$. The shift is viewed as a concatenation of these return words.
2. Orbit Splitting: Since the speedup $S$ jumps by $p(x)$, a single $T$-orbit splits into a finite number ($c \leq p_{\max}$) of $S$-orbits.
3. Permutation Group: The interaction between concatenated return words induces a permutation of these $c$ orbit entry positions. This defines a permutation group $S$ (a subgroup of $S_c$).
4. Skew-Product: The speedup dynamics are modeled as a skew-product $F: X_w \times S \to X_w \times S$, where $X_w$ is the derived shift (shift of return words) and $S$ acts on the fiber representing the relative ordering of the $S$-orbits.

3. Key Contributions and Results

Main Theorem (Theorem 1.1)

The central result of the paper is:

Theorem: Let $S = \sigma^p$ be a homeomorphic transitive speedup of a two-sided subshift $(X, \sigma)$. Then $\sigma$ is linearly recurrent if and only if $S$ is linearly recurrent.

This establishes that linear recurrence is an invariant property under homeomorphic speedups.

Supporting Lemmas and Propositions

• Proposition 2.1: A continuous homeomorphic transitive speedup of a minimal system is minimal.
• Proposition 2.2: Speedups of Subshifts of Finite Type (SFTs) are SFTs; speedups of sofic shifts are sofic.
• Proposition 2.3: Linear word complexity is preserved under speedups (i.e., if $p_\sigma(n) \leq Kn$, then $p_S(n) \leq K'n$).
• Lemma 4.1: The constructed skew-product (group extension) associated with the speedup of a linearly recurrent shift is itself linearly recurrent. This is the technical engine driving the main proof.

4. Proof Outline

1. Forward Direction ($\sigma$ linearly recurrent $\implies$ $S$ linearly recurrent):

   • Represent the shift $X$ using return words of a long word $w$.
   • Construct the skew-product $F$ over the derived shift $X_w$ with the permutation group $S$.
   • Use the fact that $X_w$ is linearly recurrent and the group extension is minimal/uniquely ergodic to show that the pair (return word, permutation state) recurs with a bounded gap.
   • Translate this back to the original speedup $S$, showing that any pattern in $S$ reappears within a gap proportional to its length.

2. Reverse Direction ($S$ linearly recurrent $\implies$ $\sigma$ linearly recurrent):

   • Assume $S$ is linearly recurrent.
   • Construct a "super-word" in the original shift $\sigma$ by concatenating segments of the $S$-orbit.
   • Show that the recurrence of these super-words in $S$ implies the recurrence of the underlying $\sigma$-words, utilizing the boundedness of the jump function $p(x)$.

5. Significance

• Structural Rigidity: The paper confirms that linear recurrence is a robust structural property. It is not destroyed by "time changes" (speedups), distinguishing it from weaker properties like minimality (which can be lost) or specific combinatorial structures like Toeplitz shifts (which are not preserved).
• Unification of Dynamics: It bridges the gap between symbolic dynamics (subshifts) and the theory of time changes in continuous flows. It shows that the "speed" at which one traverses an orbit does not alter the fundamental linear recurrence rate of the system, provided the speedup is a homeomorphism.
• Methodological Advance: The construction of the specific group extension using return words and permutation groups provides a powerful tool for analyzing non-abelian extensions in symbolic dynamics. This technique could be applicable to other problems involving orbit equivalence and structural stability in subshifts.
• Scope: The result applies to a broad class of systems, including primitive substitution shifts and Sturmian shifts with bounded type rotation numbers, confirming their stability under speedups.

In summary, Bruin provides a rigorous proof that the class of linearly recurrent subshifts is closed under homeomorphic speedups, utilizing a sophisticated analysis of return words and non-abelian group extensions to establish the necessary recurrence bounds.