Symbolic dynamics

Symbolic dynamics studies dynamical systems whose points are sequences of symbols from an alphabet and whose evolution is a shift. A finite alphabet with the discrete topology gives its sequence space a product topology.

A subshift of finite type is a closed subset of a finite-alphabet full shift defined by finitely many forbidden finite words, with the restricted left shift. After replacing symbols by sufficiently long blocks, its constraints can be described by a zero-one symbolic transition matrix. In this presentation, membership means that every consecutive pair follows an allowed transition. The resulting sequence space is a compact metric space and the restricted left shift is a homeomorphism.

A fixed point of the $n$th iteration of a map of a subshift of finite type is determined uniquely by its length-$n$ block with a permitted closing transition. Summing the counts of length-$n$ closed walks over their starting symbols gives the displayed trace. This counts points whose least period divides $n$. If $P_n$ counts points of least period exactly $n$, then $\mathrm{tr}(A^n)={\sum }_{d\mid n}{P}_d$, and Möbius inversion gives $P_n={\sum }_{d\mid n}{\mu }_{\mathrm{M}}(n/d)\mathrm{tr}(A^d)$. The number of distinct least-period-$n$ periodic orbits is $P_n/n$.

The adjacency matrix of a directed graph whose vertices are symbols and whose directed edges are the permitted consecutive pairs. Its entries indicate permission. In comparison, the transition matrix of a Markov chain records transition probabilities.

A finite word over an alphabet is locally admissible for a zero-one symbolic transition matrix if every consecutive pair is permitted. Its length counts symbols, so length $n+1$ corresponds to $n$ transitions. The number with endpoints $i,j$ is $(A^n{)}_{ij}$ by matrix multiplication. Local admissibility does not always imply occurrence in a two-sided subshift of finite type: the matrix $\left(\begin{array}{cc}0& 1\\ 0& 0\end{array}\right)$ permits the word $(1,2)$ but admits no two-sided sequence. If every row and column has a nonzero entry, every locally admissible word extends in both directions.

A two-sided sequence over a finite alphabet is uniformly recurrent if every finite word over an alphabet occurring in it occurs with bounded gaps. More precisely, for each such word some $M$ ensures that every length-$M$ interval contains a complete occurrence. This is equivalent to being a minimal point of the full shift: a finite cover of the orbit closure by preimages of a word's cylinder set bounds its return gaps; conversely, bounded gaps pass to all points of the orbit closure and make every forward orbit dense there. The property concerns finite words, not infinite integer intervals.

The two-sided full shift on a finite alphabet $[k]$ consists of all functions $z:\mathbb{Z}\to [k]$, with the product topology and the left shift. It is a compact metric space. A compatible metric isAgreement on increasingly large finite coordinate sets is equivalent to convergence in this topology. The metric above is compatible but is not invariant under the left shift.

On a two-sided full shift, the left shift is the homeomorphismIts inverse sends $z(j)$ to $z(j-1)$. On a one-sided sequence space, the same forward shift is generally not invertible.