Lecture 6: Symbolic Dynamics

18.091 Lecture 6 Symbolic Dynamics 1 Introduction This is a very interesting topic in the study of chaotic dynamical systems, which includes ”bits and pieces” from areas such as Analysis, Topology and Group Theory. The main purpose of today’s lecture is to gain a deeper understanding of the chaotic behaviour of the family of functions Qc when c < −2. As we will see, there is a simple space which is homeomorphic to the space of non­divergent orbits of Qc , and it is much easier to understand the dynamics of this new space. 2 Itineraries and the sequence space Σ Recall that for the family of functions Qc , when c < −2, all the interesting dynamics occur on a single interval I = [−p+ , p+ ], where √ 1 + 1 − 4c p+ = . 2 Moreover, the interval I has a subinterval A1 in which all points leave I in a single iteration. The set Λ of points in I who’s orbits never leave I therefore lies in the set I − A1 . This set A1 partitions I into two closed sets, I0 and I1 , and Λ ∈ I0 ∪ I1 . Now we can define what an itinerary of a point in Λ is. Definition. Let x ∈ Λ. let Σ be the infinitely­dimensional space {0, 1}ω , that is, the space of points with an infinite number of coordinates, each of which only take on the values 0 or 1. The itinerary of x is a function from Λ to Σ S(x) = (s0 , s1 , s2 , ...) such that ∀j ∈ N, sj = k if Qjc (x) ∈ Ik . We will introduce a metric for Σ to better understand its topology. Let s = (s0 , s1 , s2 , ...) and t = (t0 , t1 , t2 , ...). The book defines a metric on Σ as d(s, t) = ∞ � |si − ti | i=0 1 2i , but we can easily come up with others. For example, a metric that looks more similar to the familiar Euclidean norm for finite­dimensional spaces is � �∞ �� (si − ti )2 � d (s, t) = � . 2i i=0 The topology induced by both of these metrics on Σ is equivalent, but we will not prove this. The proof that d is in fact a metric is farely trivial and we will omit it. Do note that for each i the possible values |si − ti | can take are only 0 or 1, so that the infinite sum that defines d is bounded above by ∞ � 1 1 = i 2 1− i=1 1 2 = 2, so the metric d is well defined (i.e. does not diverge) ∀s, t ∈ Σ. There is an important theorem, the Proximity Theorem, which states that for s, t defined as before, d(t, s) < 1/2n iff si = ti for i ≤ n. Proof. If si = ti for i ≤ n, then d(s, t) = ∞ ∞ � � |si − ti | 1 1 ≤ = n. i i 2 2 2 i=n+1 i=n+1 � tj for some j ≤ n, then we must have For the converse, if sj = d(s, t) ≥ 1 1 ≥ n, 2j 2 so it must be the case that si = ti for i ≤ n if we require d(t, s) < 1/2n . We can identify certain special subsets of Σ, like M0 = {s ∈ Σ|s0 = 0}, and M1 = {s ∈ Σ|s0 = 1}, which partition Σ. We can further partition M0 into M00 = {s ∈ Σ|s0 = 0, s1 = 0} and M01 = {s ∈ Σ|s0 = 0, s1 = 1}, and analogously define M10 and M11 , which partition M1 . Note that the Proximity Theorem tells us that the minimum distance between any point in M0 and any other point in M1 has to be 1, and the minimum distance between any point in M0 0 and any point in M0 1 is 1/2, so that these subsets are totally disconnected. In fact Σ is totally disconnected, which we can notice by inductively defining M000 , M001 , M100 , M101 , ... and showing that these subsets of Σ are always separated by a non­zero minimum distance by the Proximity Theorem. Recall that the Cantor Set is also totally disconnected, which hints the existence of a homeomorphism between the Cantor Set Λ and our itinerary space Σ. 3 The Shift Map σ Definition. The shift map σ, from Σ to Σ is defined by σ(s0 , s1 , s2 , ...) = (s1 , s2 , s3 , ...). 2 It is easy to find iterates of σ, σ n (s0 , s1 , s2 , ...) = (sn , sn+1 , sn+2 , ...). It is also easy to find the periodic points of σ. For example, the periodic points of period n have the form (s0 , s1 , s2 , ..., sn−1 , s0 , s1 , ...). Theorem. The shift map σ is a continuous map. Proof. Suppose we are given s = (s0 , s1 , s2 , ...) and � > 0. Choose a value of n such that 1/2n < �, and let δ = 1/2n+1 . Let t ∈ Σ be such that d(s, t) < δ. Then, by the Proximity Theorem we must have that si = ti for i < n + 1. This implies that σ(s) and σ(t) agree in their first n coordinates, so a second application of the Proximity Theorem yields that d(σ(s), σ(t)) < �, as desired. Theorem. For every x ∈ Λ it holds that S(Qc (x)) = σ(S(x)). Proof. It suffices to note that the itinerary of Qc (x) is the same as the itinerary of x except the first entry got deleted and the rest were shifted a coordinate back, but this is the same effect σ has on the itinerary of x. 4 The Homeomorphism Theorem We have arrived to the main theorem of this lecture, which states that the topology of both Λ and Σ is essentially the same, so that analyzing the effects of σ on the points of Σ is the same as analyzing the effects of Qc on the points of Λ, considering the last theorem. It is clearly easier to understand the former, so the goal of the lecture is complete. Theorem. Λ and Σ are homeomorphic. Proof. We need to show that the itinerary map S is one­to­one onto Σ, and that √ both the maps S and S −1 are continuous. We will only prove this for 5+2 5 c < − 4 , although it holds for all c < −2. One­to­one. Suppose x, y ∈ Λ, x �= y, and S(x) = S(y). This means x and y are always located in the same interval I0 or I1 for each iteration of Qc . We know Qc maps one­to­one into I0 ∪ I1 , and for the given values of c we also know that |Q�c (x)| > µ > 1, ∀x ∈ I0 ∪ I1 . For each n, Qnc takes the interval [x, y] in a one­to­one fashion onto [Qnc (x), Qnc (y)]. Then the mean value theorem implies that Qnc (y) − Qcn (x) ≥ µn (y − x), but µn → ∞ as n → ∞, implying that the distance between the n­th iterates of x and y diverges to infinity, even though they are always in the same interval I0 or I1 . This contradiction establishes the proof that S maps into Σ one­to­one. n Onto. Let Q−n c (J) denote the preimage of J under Qc , and let s = (s0 , s1 , ...) be given. Define Is0 ,s1 ,...,sn = {x ∈ I |x ∈ Is0 , Qc (x) ∈ Is1 , ..., Qnc (x) ∈ Isn }. 3 This is the set of all the points in I who’s itinerary coincides with that of x in the first n places. Rewriting Is0 ,s1 ,...,sn in terms of preimages of other sets, and using identities of preimages, we can deduce that −n −1 −(n−1) Is0 ,s1 ,...,sn = Is0 ∩Q−1 (Isn )), c (Is1 )∩... ∩Qc (Isn ) = Is0 ∩Qc ((Is1 )∩... ∩Qc Is0 ,s1 ,...,sn = Is0 ∩ Q−1 c (Is1 ,s2 ,...,sn ). This implies that for every n the set Is0 ,s1 ,...,sn is closed. We show this by induction. The set Is0 is clearly closed, namely because it is I0 or I1 . Suppose Is1 ,s2 ,...,sn is closed. Then the preimage of Is1 ,s2 ,...,sn is a pair of closed intervals, one in I0 and the other in I1 . Hence, Is0 ,s1 ,...,sn = Is0 ∩ Q−1 c (Is1 ,s2 ,...,sn ) is closed. These sets are also nested, for Is0 ,s1 ,...,sn = Is0 ,s1 ,...,sn−1 ∩ Q−n c (Isn ) ⊂ Is0 ,s1 ,...,sn−1 holds. This implies that Is0 ,s1 ,... = � Is0 ,s1 ,...,sn n≥0 is non­empty (recall from your Analysis class that the intersection of arbitrary closed and nested sets is not empty). Hence, there is an x ∈ Is0 ,s1 ,... and it is such that S(x) = s = (s0 , s1 , ...). This implies every point in Σ is in the image of Λ under S, which proves the onto requirement. Continuity. Let x ∈ Λ, S(x) = (x0 , x1 , ...) and � > 0 be given. Choose a value of n such that 1/2n < �. Consider Ix0 ,x1 ,...,xn , which is a closed interval as discussed earlier. Given the finite length of Ix0 ,x1 ,...,xn , there clearly exists a δ such that if |x − y | < δ and y ∈ Λ then y ∈ Ix0 ,x1 ,...,xn . This implies that S(y) and S(x) have xi = yi for i ≤ n. The proximity theorem implies that d(S(x), S(y)) ≤ �, which implies S is continuous. The proof that S −1 is continuous is very similar, so we omit it, and we are done proving the theorem. 4