Symbolic dynamics — orbits as sequences of symbols

Parent: orbit · Prereq: discrete-dynamical-systems

The move: replace a point by the itinerary of its orbit through finitely many regions, and study the space of itineraries as a dynamical system in its own right.

Full shift

Alphabet $A = \{0, 1, \dots, k-1\}$. The full $k$-shift is $\Sigma_k = A^{\mathbb{N}}$ (all one-sided symbol sequences) with the shift map $\sigma(x)_n = x_{n+1}$ — drop the first symbol. Metric: $d(x, y) = 2^{-\min\{n \,:\, x_n \neq y_n\}}$; two sequences are close iff they agree on a long prefix. $\Sigma_k$ is compact, $\sigma$ continuous.

Subshift of finite type (SFT)

Fix a $k \times k$ 0-1 transition matrix $M$. The SFT $\Sigma_M \subseteq \Sigma_k$ consists of sequences with every adjacent pair allowed: $M_{x_n, x_{n+1}} = 1$ for all $n$. (Equivalently: forbid finitely many words.)

Two exact counting facts make SFTs computable objects:

• Words: the number of allowed words of length $n$ is $\sum_{i,j} (M^{n-1})_{ij}$.
• Periodic orbits: $\#\{x : \sigma^n x = x\} = \operatorname{tr}(M^n)$.

Topological entropy

$h(\sigma) = \lim_{n \to \infty} \tfrac{1}{n} \log \# W_n$, where $W_n$ = allowed words of length $n$. For an SFT, $h = \log \lambda_{\max}(M)$ (Perron–Frobenius eigenvalue). Entropy is the conjugacy invariant measuring orbit diversity: how many distinguishable orbit segments of length $n$ exist.

Count along: the golden-mean shift

Alphabet $\{0,1\}$, forbidden word $11$ (no two consecutive ones): $M = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$.

Words of length $n$: $W_1 = \{0, 1\}$ so $\#W_1 = 2$; $\#W_2 = 3$ ($00, 01, 10$); $\#W_3 = 5$ ($000,001,010,100,101$); $\#W_4 = 8$. That is the Fibonacci sequence $F_{n+2}$ — and indeed $M$ is the Fibonacci matrix. Hence

the logarithm of the golden ratio. Periodic points: $\operatorname{tr}(M^2) = 3$ points of period dividing 2 — namely $\overline{00}$, $\overline{01}$, $\overline{10}$. ✓ ($\overline{11}$ is forbidden.)

Why this is the universal back end

Coding is a conjugacy (or semi-conjugacy) $h \circ f = \sigma \circ h$ from a concrete system to a shift:

• doubling map $\leftrightarrow$ full 2-shift via binary digits (ergodic-theory-of-orbits);
• interval maps with covering relations $\to$ SFT itineraries — the engine inside Sharkovskii/Li–Yorke (topological-dynamics);
• angle doubling on the Julia set of $z^2$ (complex-dynamics);
• the Collatz map on $\mathbb{Z}_2$ is the full 2-shift in disguise via parity vectors (collatz-orbit-statistics) — the cleanest statement of "the dynamics is understood, the integers are not."

Once coded, orbit questions become word-combinatorics questions — countable, checkable, often decidable; what is lost is exactly the arithmetic of which symbol sequences correspond to the points you care about.