🔄Ergodic Theory Unit 7 – Symbolic Dynamics and Finite Subshifts

Key Concepts and Definitions

• Symbolic dynamics studies dynamical systems by representing them as sequences of symbols from a finite alphabet
• An alphabet $\mathcal{A}$ is a finite set of symbols used to represent the states of a dynamical system
• A word is a finite sequence of symbols from the alphabet $\mathcal{A}$
  • The length of a word $w$, denoted by $|w|$, is the number of symbols it contains
  • The set of all words of length $n$ over the alphabet $\mathcal{A}$ is denoted by $\mathcal{A}^n$
• The full shift $\mathcal{A}^\mathbb{Z}$ is the set of all bi-infinite sequences of symbols from the alphabet $\mathcal{A}$
  • Elements of $\mathcal{A}^\mathbb{Z}$ are called configurations
• A subshift $X \subseteq \mathcal{A}^\mathbb{Z}$ is a closed, shift-invariant subset of the full shift
• The language of a subshift $X$, denoted by $\mathcal{L}(X)$, is the set of all words that appear as subwords of configurations in $X$

Symbolic Spaces and Shift Maps

• The shift map $\sigma: \mathcal{A}^\mathbb{Z} \to \mathcal{A}^\mathbb{Z}$ is defined by $(\sigma(x))_i = x_{i+1}$ for all $i \in \mathbb{Z}$
  • The shift map is a continuous, surjective, and measure-preserving transformation
• The pair $(\mathcal{A}^\mathbb{Z}, \sigma)$ forms a dynamical system called the full shift
• Subshifts are invariant under the shift map, i.e., if $X$ is a subshift, then $\sigma(X) = X$
• The one-sided shift $\mathcal{A}^\mathbb{N}$ consists of all one-sided infinite sequences of symbols from $\mathcal{A}$
  • The one-sided shift map $\sigma: \mathcal{A}^\mathbb{N} \to \mathcal{A}^\mathbb{N}$ is defined analogously to the two-sided case
• The cylinder set $[w]_i$ is the set of all configurations in $\mathcal{A}^\mathbb{Z}$ that contain the word $w$ starting at position $i$
  • Cylinder sets form a basis for the topology on $\mathcal{A}^\mathbb{Z}$

Finite State Machines and Subshifts

• A finite state machine (FSM) is a directed graph with labeled edges that generates a language
  • Vertices of the graph are called states, and edges are labeled with symbols from the alphabet
  • A path in the FSM corresponds to a word in the language generated by the FSM
• A sofic shift is a subshift that can be described by a finite state machine
  • The language of a sofic shift is a regular language
• A shift of finite type (SFT) is a subshift defined by a finite set of forbidden words
  • SFTs are a special case of sofic shifts and can be described by a finite state machine with no labels on the states
• The golden mean shift is an example of an SFT over the alphabet $\{0, 1\}$ with the forbidden word $11$
• The even shift is an example of a sofic shift that is not an SFT

Topological Properties of Subshifts

• Subshifts are compact metric spaces when equipped with the metric $d(x, y) = 2^{-\min\{|i| : x_i \neq y_i\}}$
• A subshift is minimal if it contains no proper non-empty closed shift-invariant subsets
  • Equivalently, a subshift is minimal if every word in its language appears with bounded gaps
• A subshift is mixing if for any two words $u, v$ in its language, there exists an $N$ such that for all $n \geq N$, there is a word $w$ of length $n$ such that $uwv$ is in the language
  • Mixing implies transitivity, which means that any two words can be connected by a third word
• A subshift is uniquely ergodic if it admits a unique shift-invariant probability measure
  • The Morse-Thue shift is an example of a uniquely ergodic subshift that is not an SFT or sofic shift

Entropy and Complexity in Symbolic Systems

• The topological entropy of a subshift $X$ is defined as $h_{top}(X) = \lim_{n \to \infty} \frac{1}{n} \log |\mathcal{L}_n(X)|$, where $\mathcal{L}_n(X)$ is the set of words of length $n$ in the language of $X$
  • Topological entropy measures the exponential growth rate of the number of words in the language
• The Kolmogorov-Sinai entropy of a shift-invariant measure $\mu$ on a subshift $X$ is defined as $h_{\mu}(X) = \lim_{n \to \infty} -\frac{1}{n} \sum_{w \in \mathcal{L}_n(X)} \mu([w]_0) \log \mu([w]_0)$
  • Kolmogorov-Sinai entropy measures the average information content per symbol with respect to the measure $\mu$
• The variational principle states that the topological entropy of a subshift is equal to the supremum of the Kolmogorov-Sinai entropies over all shift-invariant measures
• The complexity function of a subshift $X$ is defined as $p_X(n) = |\mathcal{L}_n(X)|$, the number of words of length $n$ in the language of $X$
  • The complexity function provides a more refined measure of the growth rate of the language compared to topological entropy

Applications in Coding Theory

• Symbolic dynamics has applications in coding theory, particularly in the design of constrained codes
• A constrained code is a set of words over an alphabet that satisfies certain constraints, such as avoiding certain forbidden patterns
  • Constrained codes are used in data storage systems to improve reliability and efficiency
• The capacity of a constrained code is the maximum achievable information rate, given by the topological entropy of the corresponding subshift
• The Shannon cover of a constrained code is the minimal deterministic finite state machine that generates the code
  • The Shannon cover can be used to encode and decode messages efficiently
• Run-length limited (RLL) codes are a class of constrained codes used in magnetic and optical recording systems
  • RLL codes limit the minimum and maximum number of consecutive identical symbols to ensure reliable clock recovery and data detection

Connections to Ergodic Theory

• Symbolic dynamics is closely related to ergodic theory, which studies the long-term behavior of measure-preserving transformations
• A subshift is a measure-preserving dynamical system when equipped with a shift-invariant probability measure
• The Kolmogorov-Sinai entropy of a measure-preserving transformation is equal to the Kolmogorov-Sinai entropy of the corresponding subshift
• The Poincaré recurrence theorem states that almost every point in a measure-preserving system returns to any neighborhood of itself infinitely often
  • In the context of subshifts, this means that almost every configuration contains every word in the language infinitely many times
• Ergodic theorems, such as the Birkhoff ergodic theorem and the Kingman subadditive ergodic theorem, have important applications in symbolic dynamics
  • These theorems provide a way to relate the time averages of observables to their space averages

Advanced Topics and Open Problems

• The conjugacy problem asks whether two subshifts are topologically conjugate, i.e., if there exists a homeomorphism between them that commutes with the shift map
  • The conjugacy problem is decidable for shifts of finite type but undecidable for sofic shifts
• The automorphism group of a subshift is the group of homeomorphisms of the subshift that commute with the shift map
  • The automorphism group of a shift of finite type is finitely generated, while the automorphism group of a sofic shift can be infinitely generated
• The Pisot conjecture states that if a subshift has a Pisot number as its topological entropy, then it must be a sofic shift
  • The conjecture has been proven for some special cases but remains open in general
• The Nivat conjecture states that if a subshift has a low complexity function, then it must be a periodic subshift
  • The conjecture has been proven for some special cases but remains open in general
• The Sarnak conjecture states that the Möbius function is orthogonal to any deterministic sequence, including those generated by subshifts
  • The conjecture has been proven for some classes of subshifts but remains open in general