Namespaces
Variants
Actions

Difference between revisions of "Symbolic dynamics"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(→‎References: isbn link)
 
(3 intermediate revisions by 2 users not shown)
Line 1: Line 1:
Symbolic dynamics in the narrow sense is the investigation of the topological [[Bernoulli automorphism|Bernoulli automorphism]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s0915801.png" /> defined below, its invariant closed subsets, its invariant measures, etc. The topological Bernoulli automorphism <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s0915802.png" /> acts in the space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s0915803.png" /> of infinite two-sided sequences of symbols from an alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s0915804.png" /> (usually finite), provided with the direct product topology as an infinite number of copies of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s0915805.png" /> (it is usual to take the discrete topology in each copy). Namely, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s0915806.png" /> takes a sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s0915807.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s0915808.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s0915809.png" /> ( "shift the sequence one place to the left" ). An obvious generalization is the action of a group (or semi-group) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158010.png" /> on the space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158011.png" /> of functions from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158012.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158013.png" />.
+
{{TEX|done}}
  
Let certain pairs <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158014.png" /> of symbols from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158015.png" /> be declared  "admissible" . All sequences <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158016.png" /> for which for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158017.png" /> the pair <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158018.png" /> is admissible form a closed (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158019.png" />-) invariant subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158020.png" />. This is the most important example of an invariant subset of the topological Bernoulli automorphism. The [[Dynamical system|dynamical system]] in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158021.png" /> generated by the shift <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158022.png" /> is called a topological Markov chain.
+
Symbolic dynamics in the narrow sense is the investigation of the topological [[Bernoulli automorphism]] $\sigma$ defined below, its invariant closed subsets, its invariant measures, etc. The topological Bernoulli automorphism $\sigma$ acts in the space $\Omega$ of infinite two-sided sequences of symbols from an alphabet $A$ (usually finite), provided with the direct product topology as an infinite number of copies of $A$ (it is usual to take the discrete topology in each copy). Namely, $\sigma$ takes a sequence $\omega = (\omega_i)$ to $\omega' = (\omega'_i)$, where $\omega_i' = \omega_{i+1}$ ( "shift the sequence one place to the left" ). An obvious generalization is the action of a group (or semi-group) $G$ on the space $A^G$ of functions from $G$ to $A$.
  
Symbolic dynamics in the broad sense is the application of symbolic dynamics in the narrow sense to the investigation of dynamical systems which themselves are defined completely independently of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158023.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158024.png" />.
+
Let certain pairs $(a,b)$ of symbols from $A$ be declared  "admissible" . All sequences $\omega_i$ for which for all $i$ the pair $(\omega_i,\omega_{i+1})$ is admissible form a closed ($\sigma$-) invariant subset $\Omega_1 \subset \Omega$. This is the most important example of an invariant subset of the topological Bernoulli automorphism. The [[dynamical system]] in $\Omega_1$ generated by the shift $\sigma{\downharpoonright}_{\Omega_1}$ is called a topological Markov chain.
 +
 
 +
Symbolic dynamics in the broad sense is the application of symbolic dynamics in the narrow sense to the investigation of dynamical systems which themselves are defined completely independently of $\Omega$ and $\sigma$.
  
 
====References====
 
====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  V.M. Alekseev,  "Symbolic dynamics. Eleventh Summer School in Math." , '''1''' , Kiev  (1976)  (In Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  R. Bowen,  "Equilibrium states and the ergodic theory of Anosov diffeomorphisms" , ''Lect. notes in math.'' , '''470''' , Springer  (1975)</TD></TR></table>
+
<table>
 
+
<TR><TD valign="top">[1]</TD> <TD valign="top">  V.M. Alekseev,  "Symbolic dynamics. Eleventh Summer School in Math." , '''1''' , Kiev  (1976)  (In Russian)</TD></TR>
 
+
<TR><TD valign="top">[2]</TD> <TD valign="top">  R. Bowen,  "Equilibrium states and the ergodic theory of Anosov diffeomorphisms" , ''Lect. notes in math.'' , '''470''' , Springer  (1975) {{ZBL|0308.28010}}; 2nd ed.
 +
(2008) {{ISBN|978-3-540-77605-5}} {{ZBL|1172.37001}}</TD></TR>
 +
</table>
  
 
====Comments====
 
====Comments====
 
A1) Instead of  "topological Bernoulli automorphism"  usually the term shift transformation (or simply shift) is employed. Shift systems and their closed invariant subspaces (usually called subshifts) form an important family of cascades with many applications, also outside of dynamical systems theory.
 
A1) Instead of  "topological Bernoulli automorphism"  usually the term shift transformation (or simply shift) is employed. Shift systems and their closed invariant subspaces (usually called subshifts) form an important family of cascades with many applications, also outside of dynamical systems theory.
  
Both in [[Ergodic theory|ergodic theory]] and in [[Topological dynamics|topological dynamics]] many important examples and counter-examples are defined by subshifts, which are often obtained as the closure of the orbit of a certain point in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158025.png" />, the point in question being an infinite two-sided sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158026.png" /> with special combinatorial properties. For instance, the Morse–Thue sequence is the two-sided sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158027.png" /> over the alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158028.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158029.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158030.png" />, and where the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158031.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158032.png" /> are given as follows: if the  "block"  of the first <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158033.png" /> entries is denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158034.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158035.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158036.png" /> is the concatenation of the blocks <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158037.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158038.png" />; here <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158039.png" /> is obtained from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158040.png" /> by interchanging all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158041.png" />'s and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158042.png" />'s. Thus, the sequence of non-negative coordinates of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158043.png" /> is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158044.png" />. An alternative definition is: Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158045.png" /> be the number of one's in the binary expansion of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158046.png" />; then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158047.png" /> (mod <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158048.png" />) for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158049.png" />. This sequence defines a point in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158050.png" /> which is almost periodic but not periodic; see [[#References|[a10]]], Chapt. 12. For general results on shift systems, consult [[#References|[a11]]], .
+
Both in [[ergodic theory]] and in [[topological dynamics]] many important examples and counter-examples are defined by subshifts, which are often obtained as the closure of the orbit of a certain point in $  \Omega $,  
 +
the point in question being an infinite two-sided sequence $  \omega = \{ \omega _{i} \} $
 +
with special combinatorial properties. For instance, the Morse–Thue sequence is the two-sided sequence $  \{ \mu _{i} \} $
 +
over the alphabet $  \{ 0,\  1 \} $
 +
such that $  \mu _ {-i} = \mu _ {i-1} $
 +
for all $  i \geq 1 $,  
 +
and where the $  \mu _{i} $
 +
for $  i \geq 0 $
 +
are given as follows: if the  "block"  of the first $  2 ^{n} $
 +
entries is denoted by $  Q _{n} $,  
 +
then $  Q _{0} = 0 $
 +
and $  Q _ {n+1} $
 +
is the concatenation of the blocks $  Q _{n} $
 +
and $  \overline{Q}\; _{n} $;  
 +
here $  \overline{Q}\; _{n} $
 +
is obtained from $  Q _{n} $
 +
by interchanging all 0 $'
 +
s and $  1 $'
 +
s. Thus, the sequence of non-negative coordinates of $  \mu $
 +
is $  0110 \  1001 \  1001 \  0110 \dots $.  
 +
An alternative definition is: Let $  \alpha _{n} $
 +
be the number of one's in the binary expansion of $  n $;  
 +
then $  \mu _{n} = \alpha _{n} $(
 +
mod $  2 $)  
 +
for $  n \geq 0 $.  
 +
This sequence defines a point in $  \Omega $
 +
which is almost periodic but not periodic; see [[#References|[a10]]], Chapt. 12. For general results on shift systems, consult [[#References|[a11]]], .
  
The topological Markov chains defined above are also called subshifts of finite type. Such a subshift can be characterized by an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158051.png" />-matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158052.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158053.png" /> is the number of elements in the alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158054.png" /> under consideration, as follows: Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158055.png" />; then a pair <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158056.png" /> is admissible if and only if the entry <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158057.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158058.png" /> is 1; the other entries of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158059.png" /> are <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158060.png" /> (the transition matrix of the topological Markov chain). Properties of the topological Markov chain can often be expressed in terms of the associated transition matrix. For example, the [[Topological entropy|topological entropy]] of a topological Markov chain equals <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158061.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158062.png" /> is the largest positive eigenvalue of the transition matrix. For the classification of topological Markov chains, see [[#References|[a2]]] and [[#References|[a8]]].
+
The topological Markov chains defined above are also called subshifts of finite type. Such a subshift can be characterized by an $  (m \times m) $-
 +
matrix $  M $,  
 +
where $  m $
 +
is the number of elements in the alphabet $  A $
 +
under consideration, as follows: Let $  A = \{ a _{1} \dots a _{m} \} $;  
 +
then a pair $  (a _{i} ,\  a _{j} ) $
 +
is admissible if and only if the entry $  M _ {ij} $
 +
of $  M $
 +
is 1; the other entries of $  M $
 +
are 0 $(
 +
the transition matrix of the topological Markov chain). Properties of the topological Markov chain can often be expressed in terms of the associated transition matrix. For example, the [[topological entropy]] of a topological Markov chain equals $  \mathop{\rm log}\nolimits \  \lambda $,  
 +
where $  \lambda $
 +
is the largest positive eigenvalue of the transition matrix. For the classification of topological Markov chains, see [[#References|[a2]]] and [[#References|[a8]]].
  
Related with the topological Markov chains are the sofic systems ([[#References|[a5]]], ). A sofic system is a subshift <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158063.png" /> for which there exist a topological Markov chain <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158064.png" /> and a continuous surjection <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158065.png" /> which commutes with the shift transformations in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158066.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158067.png" />. For problems related with the classification of sofic systems, see [[#References|[a7]]].
+
Related with the topological Markov chains are the sofic systems ([[#References|[a5]]], ). A sofic system is a subshift $  \Omega _{1} $
 +
for which there exist a topological Markov chain $  \Omega _{2} $
 +
and a continuous surjection $  \phi : \  \Omega _{2} \rightarrow \Omega _{1} $
 +
which commutes with the shift transformations in $  \Omega _{2} $
 +
and $  \Omega _{1} $.  
 +
For problems related with the classification of sofic systems, see [[#References|[a7]]].
  
 
For applications of topological Markov chains and sofic systems for the construction of codes in information theory, see [[#References|[a1]]], . As another example one should mention that the Morse–Thue sequence was used, among others, to prove the existence of recurrent non-closed geodesics on certain manifolds of negative curvature [[#References|[a21]]], but also to disprove Burnside's conjecture that a bounded group is finite ( cf. [[Burnside problem|Burnside problem]] 2).
 
For applications of topological Markov chains and sofic systems for the construction of codes in information theory, see [[#References|[a1]]], . As another example one should mention that the Morse–Thue sequence was used, among others, to prove the existence of recurrent non-closed geodesics on certain manifolds of negative curvature [[#References|[a21]]], but also to disprove Burnside's conjecture that a bounded group is finite ( cf. [[Burnside problem|Burnside problem]] 2).
Line 23: Line 70:
 
In ergodic theory shift systems play an almost  "universal"  role. An important class is formed by the Bernoulli shifts, also called Bernoulli automorphisms; see e.g. [[#References|[a24]]]. Many systems that are defined in another way turn out to be isomorphic to Bernoulli shifts (e.g., geodesic flows on surfaces of negative curvature, [[#References|[a22]]]). In this context also the Jewett–Krieger theorem (cf. [[Strong ergodicity|Strong ergodicity]]) should be mentioned. For the ergodic properties of the Morse (–Thue) system, see e.g. [[#References|[a15]]]; it is uniquely ergodic [[#References|[a16]]], [[#References|[a17]]]. Other publications dealing directly or indirectly with the ergodic theory of shift systems are [[#References|[a2]]], [[#References|[a3]]], [[#References|[a9]]], [[#References|[a13]]] [[#References|[a14]]], [[#References|[a23]]].
 
In ergodic theory shift systems play an almost  "universal"  role. An important class is formed by the Bernoulli shifts, also called Bernoulli automorphisms; see e.g. [[#References|[a24]]]. Many systems that are defined in another way turn out to be isomorphic to Bernoulli shifts (e.g., geodesic flows on surfaces of negative curvature, [[#References|[a22]]]). In this context also the Jewett–Krieger theorem (cf. [[Strong ergodicity|Strong ergodicity]]) should be mentioned. For the ergodic properties of the Morse (–Thue) system, see e.g. [[#References|[a15]]]; it is uniquely ergodic [[#References|[a16]]], [[#References|[a17]]]. Other publications dealing directly or indirectly with the ergodic theory of shift systems are [[#References|[a2]]], [[#References|[a3]]], [[#References|[a9]]], [[#References|[a13]]] [[#References|[a14]]], [[#References|[a23]]].
  
A2) Symbolic dynamics in the broad sense rests on the following principle. Suppose the phase space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158068.png" /> of a cascade <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158069.png" /> is partitioned into finitely many disjoint sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158070.png" />. Then for every <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158071.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158072.png" /> there is a unique <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158073.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158074.png" />. The sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158075.png" /> — also called the itinerary of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158076.png" /> — can be considered as an element of the shift system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158077.png" /> over the alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158078.png" />, and the mapping <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158079.png" /> satisfies the equality <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158080.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158081.png" />. In practice this description is too restrictive. Then one tries to construct a so-called Markov partition of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158082.png" />, which is not a partition at all, but a covering of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158083.png" /> by closed subsets with mutually disjoint interiors (subject to certain additional conditions which are too complicated to state here). Associated with such a Markov partition is a transition matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158084.png" />, defined as follows: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158085.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158086.png" /> according to whether <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158087.png" /> is empty or not. Under suitable conditions on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158088.png" /> (including that the phase space is a [[Hyperbolic set|hyperbolic set]]) this matrix defines a topological Markov chain <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158089.png" />, for which it is possible to define a continuous surjection <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158090.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158091.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158092.png" /> is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158093.png" />-<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158094.png" /> on a dense <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158095.png" />-set in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158096.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158097.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158098.png" /> and all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s09158099.png" />, i.e. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s091580100.png" /> is an itinerary of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s091580101.png" />. This mapping may be used to study the given cascade both from a topological and a measure-theoretic point of view, using the special properties of the topological Markov chain <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s091580102.png" />.
+
A2) Symbolic dynamics in the broad sense rests on the following principle. Suppose the phase space $  W $
 +
of a cascade $  f: \  W \rightarrow W $
 +
is partitioned into finitely many disjoint sets $  W _{1} \dots W _{n} $.  
 +
Then for every $  w \in W $
 +
and $  n \in \mathbf Z $
 +
there is a unique $  \phi (n,\  w) \in \{ 1 \dots n \} $
 +
such that $  f ^ {\  n} (w) \in W _ {\phi (n,w)} $.  
 +
The sequence $  \Phi (w) = \{ \phi (n,\  w) :\  n \in \mathbf Z \} $
 +
— also called the itinerary of $  w $
 +
— can be considered as an element of the shift system $  \Omega $
 +
over the alphabet $  A = \{ 1 \dots n \} $,  
 +
and the mapping $  \Phi : \  W \rightarrow \Omega $
 +
satisfies the equality $  \Phi (f(w) ) = \sigma ( \Phi (w) ) $
 +
for all $  w \in W $.  
 +
In practice this description is too restrictive. Then one tries to construct a so-called Markov partition of $  W $,  
 +
which is not a partition at all, but a covering of $  W $
 +
by closed subsets with mutually disjoint interiors (subject to certain additional conditions which are too complicated to state here). Associated with such a Markov partition is a transition matrix $  M $,  
 +
defined as follows: $  M _ {ij} = 0 $
 +
or $  1 $
 +
according to whether $  \mathop{\rm int}\nolimits \  W _{i} \cap f ^ {\  -1} (  \mathop{\rm int}\nolimits \  W _{j} ) $
 +
is empty or not. Under suitable conditions on $  f $(
 +
including that the phase space is a [[Hyperbolic set|hyperbolic set]]) this matrix defines a topological Markov chain $  \Omega _{M} $,  
 +
for which it is possible to define a continuous surjection $  pi: \  \Omega _{M} \rightarrow W $
 +
such that $  f\circ pi= pi\circ \sigma $,  
 +
$  \pi $
 +
is $  1 $-
 +
$  1 $
 +
on a dense $  G _ \delta  $-
 +
set in $  \Omega _{M} $
 +
and $  f ^ {\  n} ( \pi ( \omega ) ) \in W _ {\omega _ n} $
 +
for all $  \omega \in \Omega $
 +
and all $  n \in \mathbf Z $,  
 +
i.e. $  \omega = \{ \omega _{n} \} $
 +
is an itinerary of $  \pi ( \omega ) $.  
 +
This mapping may be used to study the given cascade both from a topological and a measure-theoretic point of view, using the special properties of the topological Markov chain $  \Omega _{M} $.
 +
 
  
Important instances of cascades for which this method has been successful are, e.g., hyperbolic automorphisms of the torus [[#References|[a3]]], Anosov diffeomorphisms (cf. [[Y-system|<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s091580103.png" />-system]]) [[#References|[a26]]], [[#References|[a27]]], and  "basic subsets"  in axiom-<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s091580105.png" /> diffeomorphisms [[#References|[a6]]] (see also [[#References|[2]]], [[#References|[a25]]] and [[#References|[a4]]]). (A diffeomorphism on a compact <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s091580106.png" />-manifold is said to satisfy Axiom <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091580/s091580108.png" /> whenever the set of non-wandering points is hyperbolic and is the closure of the set of periodic points, cf. [[Non-wandering point|Non-wandering point]].)
+
Important instances of cascades for which this method has been successful are, e.g., hyperbolic automorphisms of the torus [[#References|[a3]]], Anosov diffeomorphisms (cf. [[Y-system| $  Y $-
 +
system]]) [[#References|[a26]]], [[#References|[a27]]], and  "basic subsets"  in axiom- $  A $
 +
diffeomorphisms [[#References|[a6]]] (see also [[#References|[2]]], [[#References|[a25]]] and [[#References|[a4]]]). (A diffeomorphism on a compact $  C ^ \infty  $-
 +
manifold is said to satisfy Axiom $  A $
 +
whenever the set of non-wandering points is hyperbolic and is the closure of the set of periodic points, cf. [[Non-wandering point|Non-wandering point]].)
  
 
Symbolic dynamics is also used for the analysis of chaotic behaviour of dynamical systems (cf. [[Chaos|Chaos]]; [[Fractals|Fractals]]; [[Strange attractor|Strange attractor]]). Related with symbolic dynamics is the  "kneading calculus"  for mappings of the interval [[#References|[a20]]].
 
Symbolic dynamics is also used for the analysis of chaotic behaviour of dynamical systems (cf. [[Chaos|Chaos]]; [[Fractals|Fractals]]; [[Strange attractor|Strange attractor]]). Related with symbolic dynamics is the  "kneading calculus"  for mappings of the interval [[#References|[a20]]].

Latest revision as of 08:48, 29 April 2023


Symbolic dynamics in the narrow sense is the investigation of the topological Bernoulli automorphism $\sigma$ defined below, its invariant closed subsets, its invariant measures, etc. The topological Bernoulli automorphism $\sigma$ acts in the space $\Omega$ of infinite two-sided sequences of symbols from an alphabet $A$ (usually finite), provided with the direct product topology as an infinite number of copies of $A$ (it is usual to take the discrete topology in each copy). Namely, $\sigma$ takes a sequence $\omega = (\omega_i)$ to $\omega' = (\omega'_i)$, where $\omega_i' = \omega_{i+1}$ ( "shift the sequence one place to the left" ). An obvious generalization is the action of a group (or semi-group) $G$ on the space $A^G$ of functions from $G$ to $A$.

Let certain pairs $(a,b)$ of symbols from $A$ be declared "admissible" . All sequences $\omega_i$ for which for all $i$ the pair $(\omega_i,\omega_{i+1})$ is admissible form a closed ($\sigma$-) invariant subset $\Omega_1 \subset \Omega$. This is the most important example of an invariant subset of the topological Bernoulli automorphism. The dynamical system in $\Omega_1$ generated by the shift $\sigma{\downharpoonright}_{\Omega_1}$ is called a topological Markov chain.

Symbolic dynamics in the broad sense is the application of symbolic dynamics in the narrow sense to the investigation of dynamical systems which themselves are defined completely independently of $\Omega$ and $\sigma$.

References

[1] V.M. Alekseev, "Symbolic dynamics. Eleventh Summer School in Math." , 1 , Kiev (1976) (In Russian)
[2] R. Bowen, "Equilibrium states and the ergodic theory of Anosov diffeomorphisms" , Lect. notes in math. , 470 , Springer (1975) Zbl 0308.28010; 2nd ed. (2008) ISBN 978-3-540-77605-5 Zbl 1172.37001

Comments

A1) Instead of "topological Bernoulli automorphism" usually the term shift transformation (or simply shift) is employed. Shift systems and their closed invariant subspaces (usually called subshifts) form an important family of cascades with many applications, also outside of dynamical systems theory.

Both in ergodic theory and in topological dynamics many important examples and counter-examples are defined by subshifts, which are often obtained as the closure of the orbit of a certain point in $ \Omega $, the point in question being an infinite two-sided sequence $ \omega = \{ \omega _{i} \} $ with special combinatorial properties. For instance, the Morse–Thue sequence is the two-sided sequence $ \{ \mu _{i} \} $ over the alphabet $ \{ 0,\ 1 \} $ such that $ \mu _ {-i} = \mu _ {i-1} $ for all $ i \geq 1 $, and where the $ \mu _{i} $ for $ i \geq 0 $ are given as follows: if the "block" of the first $ 2 ^{n} $ entries is denoted by $ Q _{n} $, then $ Q _{0} = 0 $ and $ Q _ {n+1} $ is the concatenation of the blocks $ Q _{n} $ and $ \overline{Q}\; _{n} $; here $ \overline{Q}\; _{n} $ is obtained from $ Q _{n} $ by interchanging all $ 0 $' s and $ 1 $' s. Thus, the sequence of non-negative coordinates of $ \mu $ is $ 0110 \ 1001 \ 1001 \ 0110 \dots $. An alternative definition is: Let $ \alpha _{n} $ be the number of one's in the binary expansion of $ n $; then $ \mu _{n} = \alpha _{n} $( mod $ 2 $) for $ n \geq 0 $. This sequence defines a point in $ \Omega $ which is almost periodic but not periodic; see [a10], Chapt. 12. For general results on shift systems, consult [a11], .

The topological Markov chains defined above are also called subshifts of finite type. Such a subshift can be characterized by an $ (m \times m) $- matrix $ M $, where $ m $ is the number of elements in the alphabet $ A $ under consideration, as follows: Let $ A = \{ a _{1} \dots a _{m} \} $; then a pair $ (a _{i} ,\ a _{j} ) $ is admissible if and only if the entry $ M _ {ij} $ of $ M $ is 1; the other entries of $ M $ are $ 0 $( the transition matrix of the topological Markov chain). Properties of the topological Markov chain can often be expressed in terms of the associated transition matrix. For example, the topological entropy of a topological Markov chain equals $ \mathop{\rm log}\nolimits \ \lambda $, where $ \lambda $ is the largest positive eigenvalue of the transition matrix. For the classification of topological Markov chains, see [a2] and [a8].

Related with the topological Markov chains are the sofic systems ([a5], ). A sofic system is a subshift $ \Omega _{1} $ for which there exist a topological Markov chain $ \Omega _{2} $ and a continuous surjection $ \phi : \ \Omega _{2} \rightarrow \Omega _{1} $ which commutes with the shift transformations in $ \Omega _{2} $ and $ \Omega _{1} $. For problems related with the classification of sofic systems, see [a7].

For applications of topological Markov chains and sofic systems for the construction of codes in information theory, see [a1], . As another example one should mention that the Morse–Thue sequence was used, among others, to prove the existence of recurrent non-closed geodesics on certain manifolds of negative curvature [a21], but also to disprove Burnside's conjecture that a bounded group is finite ( cf. Burnside problem 2).

In ergodic theory shift systems play an almost "universal" role. An important class is formed by the Bernoulli shifts, also called Bernoulli automorphisms; see e.g. [a24]. Many systems that are defined in another way turn out to be isomorphic to Bernoulli shifts (e.g., geodesic flows on surfaces of negative curvature, [a22]). In this context also the Jewett–Krieger theorem (cf. Strong ergodicity) should be mentioned. For the ergodic properties of the Morse (–Thue) system, see e.g. [a15]; it is uniquely ergodic [a16], [a17]. Other publications dealing directly or indirectly with the ergodic theory of shift systems are [a2], [a3], [a9], [a13] [a14], [a23].

A2) Symbolic dynamics in the broad sense rests on the following principle. Suppose the phase space $ W $ of a cascade $ f: \ W \rightarrow W $ is partitioned into finitely many disjoint sets $ W _{1} \dots W _{n} $. Then for every $ w \in W $ and $ n \in \mathbf Z $ there is a unique $ \phi (n,\ w) \in \{ 1 \dots n \} $ such that $ f ^ {\ n} (w) \in W _ {\phi (n,w)} $. The sequence $ \Phi (w) = \{ \phi (n,\ w) :\ n \in \mathbf Z \} $ — also called the itinerary of $ w $ — can be considered as an element of the shift system $ \Omega $ over the alphabet $ A = \{ 1 \dots n \} $, and the mapping $ \Phi : \ W \rightarrow \Omega $ satisfies the equality $ \Phi (f(w) ) = \sigma ( \Phi (w) ) $ for all $ w \in W $. In practice this description is too restrictive. Then one tries to construct a so-called Markov partition of $ W $, which is not a partition at all, but a covering of $ W $ by closed subsets with mutually disjoint interiors (subject to certain additional conditions which are too complicated to state here). Associated with such a Markov partition is a transition matrix $ M $, defined as follows: $ M _ {ij} = 0 $ or $ 1 $ according to whether $ \mathop{\rm int}\nolimits \ W _{i} \cap f ^ {\ -1} ( \mathop{\rm int}\nolimits \ W _{j} ) $ is empty or not. Under suitable conditions on $ f $( including that the phase space is a hyperbolic set) this matrix defines a topological Markov chain $ \Omega _{M} $, for which it is possible to define a continuous surjection $ pi: \ \Omega _{M} \rightarrow W $ such that $ f\circ pi= pi\circ \sigma $, $ \pi $ is $ 1 $- $ 1 $ on a dense $ G _ \delta $- set in $ \Omega _{M} $ and $ f ^ {\ n} ( \pi ( \omega ) ) \in W _ {\omega _ n} $ for all $ \omega \in \Omega $ and all $ n \in \mathbf Z $, i.e. $ \omega = \{ \omega _{n} \} $ is an itinerary of $ \pi ( \omega ) $. This mapping may be used to study the given cascade both from a topological and a measure-theoretic point of view, using the special properties of the topological Markov chain $ \Omega _{M} $.


Important instances of cascades for which this method has been successful are, e.g., hyperbolic automorphisms of the torus [a3], Anosov diffeomorphisms (cf. $ Y $- system) [a26], [a27], and "basic subsets" in axiom- $ A $ diffeomorphisms [a6] (see also [2], [a25] and [a4]). (A diffeomorphism on a compact $ C ^ \infty $- manifold is said to satisfy Axiom $ A $ whenever the set of non-wandering points is hyperbolic and is the closure of the set of periodic points, cf. Non-wandering point.)

Symbolic dynamics is also used for the analysis of chaotic behaviour of dynamical systems (cf. Chaos; Fractals; Strange attractor). Related with symbolic dynamics is the "kneading calculus" for mappings of the interval [a20].

References

[a1] R.L. Adler, D. Coppersmith, M. Hassner, "Algorithms for sliding block codes" IEEE Trans. Inform. Theory , 219 (1983) pp. 5–22
[a2] R.L. Adler, B. Marcus, "Topological entropy and equivalence of dynamical systems" Mem. Amer. Math. Soc. , 219 (1979)
[a3] R.L. Adler, B. Weiss, "Similarity of automorphisms of the torus" Mem. Amer. Math. Soc. , 98 (1970)
[a4] V.M. Alekseev, M.V. Yakobson, "Symbolic dynamics and hyperbolic dynamic systems" Physics Reports , 75 : 5 (1981) pp. 287–325
[a5] B. Weiss, "Subshifts of finite type and sofic systems" Monatsh. Math. , 77 (1973) pp. 462–474
[a6] R. Bowen, "Markov partitions for Axiom A diffeomorphisms" Amer. J. Math. , 92 (1970) pp. 725–747
[a7] M. Boyle, W. Krieger, "Almost Markov and shift equivalent sofic systems" J.C. Alexander (ed.) , Dynamical Systems (Proc. Maryland, 1986–7) , Springer (1988) pp. 33–93
[a8] M. Boyle, B. Marcus, P. Trow, "Resolving maps and the dimension group for shifts of finite type" Mem. Amer. Math. Soc. , 377 (1987)
[a9] C. Grillenberger, "Ergodic theory on compact spaces" , Springer (1976)
[a10] G.H. Hedlund, "Topological dynamics" , Amer. Math. Soc. (1955)
[a11] G.H. Hedlund, "Endomorphisms and automorphisms of the shift dynamical system" Math. Systems Theory , 3 (1969) pp. 320–375
[a12a] G.H. Hedlund, M. Morse, "Symbolic dynamics I" Amer. J. Math. , 60 (1938) pp. 815–866
[a12b] G.H. Hedlund, M. Morse, "Symbolic dynamics II" Amer. J. Math. , 62 (1940) pp. 1–42
[a13] K. Jacobs, M. Keane, "0–1 sequences of Toeplitz type" Z. Warsch. verw. Geb. , 13 (1969) pp. 123–131
[a14] A. del Junco, M. Keane, B. Kitchens, B. Marcus, L. Swanson, "Continuous homomorphisms of Bernoulli schemes" A. Katok (ed.) , Ergodic Theory and Dynamical Systems , Birkhäuser (1981) pp. 91–111
[a15] S. Kakutani, "Ergodic theory of shift transformations" L. le Cam (ed.) J. Neyman (ed.) , Proc. 5-th Berkeley Symp. Math. Probab. Stat. II , Univ. California Press (1967) pp. 405–414
[a16] S. Kakutani, "Strictly ergodic symbolic dynamical systems" L. le Cam (ed.) J. Neyman (ed.) E.L. Scott (ed.) , Proc. 6-th Berkeley Symp. Math. Probab. Stat. II , Univ. California Press (1972) pp. 319–326
[a17] M.Keane, "Generalized Morse sequences" Z. Warsch. verw. Geb. , 10 (1968) pp. 335–353
[a18a] W. Krieger, "On sofic systems I" Israel J. Math. , 48 (1984) pp. 305–330
[a18b] W. Krieger, "On sofic systems II" Israel J. Math. , 60 (1987) pp. 167–176
[a19] B. Marcus, "Sofic systems and encoding data" IEEE Trans. Inform. Theory , 31 (1985) pp. 366–377
[a20] J.W. Milnor, R. Thurston, "On iterated maps of the interval" J.C. Alexander (ed.) , Dynamical Systems (Proc. Maryland, 1986–7) , Lect. notes in math. , 1342 , Springer (1988) pp. 465–563
[a21] M. Morse, "Recurrent geodesics on a surface of negative curvature" Amer. J. Math. , 43 (1921) pp. 33–51
[a22] D. Ornstein, B. Weiss, "Geodesic flows are Bernoullian" Israel J. Math. , 14 (1973) pp. 184–198
[a23] W.S. Parry, S. Tuncel, "Classification problems in ergodic theory" , Cambridge Univ. Press (1982)
[a24] P. Shields, "The theory of Bernoulli shifts" , Univ. Chicago Press (1973)
[a25] M. Shub, "Global stability of dynamical systems" , Springer (1987) (Translated from French)
[a26] Ya. Sinai, "Markov partitions and C-diffeomorphisms" Funct. Anal. Appl. , 2 : 1 (1968) pp. 64–89 Funkts. Anal. Prilozh. , 2 : 1 (1968) pp. 64–89
[a27] Ya. Sinai, "Construction of Markov partitions" Funct. Anal. Appl. , 2 : 2 (1968) pp. 70–80 Funkts. Anal. Prilozh. , 2 : 3 (1968) pp. 64–80
How to Cite This Entry:
Symbolic dynamics. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Symbolic_dynamics&oldid=14795
This article was adapted from an original article by D.V. Anosov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article