Smale’s horseshoe

Smale’s horseshoe, one of absolutely central notions of the modern theory of dynamical systems, was invented by Stephen Smale in 1960 in Rio de Janeiro, while Dr. Smale was receiving support from the National Science Foundation (NSF) of the United States as a postdoctoral fellow. Its fame notwithstanding, the construction of the horseshoe map is completely elementary and requires no university mathematics. My goal is to present this map in its simplest form (I am following the article by Ilyashenko and Kotova, published in the Soviet magazine “Kvant”).

1. The map

Let me start with a unit square (see Fig. 1). I divide this square into five equal vertical rectangles and also into five equal horizontal rectangles. I keep only the second and the fourth vertical rectangles and call them ${P_0}$ and ${P_1}$ respectively. Now I shrink ${P_0}$ five times vertically and stretch the results five times horizontally and place the result on ${P_0'}$ . The same is done for ${P_1}$ (see the figure).

fig1

In this way I define a map ${f}$ of the unit square into itself. I can continue my iterations and consider the dynamical system generated by ${f}$ . Moreover, since it should be clear that an inverse map ${f^{-1}}$ is defined, then I can consider the composition

$\displaystyle f^{n}=f\circ f\circ\ldots \circ f$

for any ${n\in\mathbb Z}$ . To see that this actually makes sense I must show that there are at least some points ${x}$ for which ${f^n(x)}$ is defined for all ${n}$ . Two such points are found immediately, they have coordinates ${x_0=(1/4,3/4)}$ and ${x_1=(3/4,1/4)}$ . These are fixed points of my map ${f}$ :

$\displaystyle f^n(x_0)=x_0,\quad f^{n}(x_1)=x_1,\quad n\in\mathbb Z.$

Exercise 1 Prove that these points are indeed fixed under the action of ${f}$ .

Are there any other points for which ${\{f^n(x)\}}$ is well defined? It turns out the answer is positive, but to concisely formulate it, I will need the notion of a Cantor set.

2. Cantor set

Take a unit interval ${[0,1]}$ and divide it into 5 equal parts. Drop the first, third and the fifth intervals. Next, each of the remaining intervals (these are ${[1/5,2/5]}$ and ${[3/5,4/5]}$ , I call them the intervals of the first rank) divide into five parts, drop three, and continue this process. You can define it rigorously by induction: if we have the intervals of the ${(n-1)}$ -st rank then to get the intervals of the ${n}$ -th rank divide each interval into five parts and drop first, third and fifth. Let ${W_n}$ be the union of all intervals of the ${n}$ -th rank.

Definition 1 The Cantor set ${K}$ is the intersection of all ${W_n}$ :

$\displaystyle K=\lim_{n\rightarrow\infty}\bigcap_n W_n.$

First thing is to show that this definition makes sense, that is set ${K}$ is not empty. For this I will use the base 5 numerical system. This simply means that if my point ${a\in[0,1]}$ can be written as

$\displaystyle a=a_15^{-1}+a_25^{-2}+a_35^{-4}+\ldots$

then I will use the notation ${a=0.a_1a_2a_3\ldots}$ , where all ${a_i\in\{0,1,2,3,4\}}$ . Using this convention I have that the first rank intervals can be written as

$\displaystyle [1/5,2/5]=[0.1,0.2],\quad [3/5,4/5]=[0.3,0.4].$

This means that all the points in the first rank intervals have the first number in the base 5 system either 1 or 3. Well, all except the right ends of the intervals 0.2 and 0.4, but I can always mend the situation as follows:

$\displaystyle 0.2=1\cdot5^{-1}+4\cdot 5^{-2}+4\cdot 5^{-3}+\ldots=0.14444\ldots$

and

$\displaystyle 0.4=3\cdot5^{-1}+4\cdot 5^{-2}+4\cdot 5^{-3}+\ldots=0.34444\ldots$

What about the second rank intervals? Clearly, I have four intervals for ${W_2}$

${[1/5+1/25,1/5+2/25]=[0.11,0.12]}$
${[1/5+3/25,1/5+4/25]=[0.13,0.14]}$
${[3/5+1/25,3/5+2/25]=[0.31,0.32]}$
${[3/5+3/25,3/5+4/25]=[0.33,0.34]}$

Or, in other words, all the numbers in these four intervals of the form ${0.k_1k_2\ldots}$ where ${k_1,k_2\in\{1,3\}}$ (again, if I properly take care of the right ends of the intervals). See the figure.

fig2

Exercise 2 Prove

Lemma 2 Let ${x=0.k_1k_2\ldots k_{n-1}k_n}$ be such that ${x\in W_n}$ and ${k_1,\ldots,k_{n-1}\in\{1,3\}}$ . Then ${k_n\in\{1,3\}}$ .

This lemma tells me that all the numbers from ${[0,1]}$ that are in ${K}$ have the representation in base 5 system as

$\displaystyle 0.k_1\ldots k_n\ldots,\quad k_j\in\{1,3\}.$

Exercise 3 To finish the construction prove

Lemma 3 Let ${x=0.k_1\ldots k_n\ldots}$ be such that ${k_n\in\{1,3\}}$ . Prove that ${x\in K}$ .

Now I can prove that there are “as many points in ${K}$ ” as in the whole interval ${[0,1]}$ .

Exercise 4 Build a bijection between the points from ${K}$ and points of the interval ${[0,1]}$ . Hint: Consider representation of points in ${[0,1]}$ in the base 2 numerical system.

Finally, prove

Exercise 5 Prove that the length of all dropped intervals in the construction of the Cantor set is 1, that is

$\displaystyle \mathrm{length}\{[0,1]\setminus K\}=1.$

3. Dynamics of ${f}$

For some points of my square I considered the map ${f}$ , which send the points of ${P_0}$ and ${P_1}$ into ${P_0'}$ and ${P_1'}$ . However, in the following I will not really care about the exact sequence of coordinates (which is called an orbit of my dynamical system), but only about the faith of my points, meaning that I will use 0 if the point belongs to ${P_0}$ and ${1}$ if the point belongs to ${P_1}$ . Again, I am interested into identifying the points with the infinite faith, but let me start with a simpler question: what are the points that have the faith of length 1. That is ${a_0=0}$ or ${a_0=1}$ ? Clearly, these are the points that under the zeroth iteration of ${f}$ (which is the identity map) lay into ${P_0}$ or ${P_1}$ . The points with the faith of length 2 must satisfy the fact that ${f^0(x)}$ is in ${P_0}$ or ${P_1}$ and ${f^1(x)}$ is in ${P_0}$ or ${P_1}$ . In other words, what is the set of points whose faith has the form ${00}$ , ${01}$ , ${10}$ , ${11}$ . To see this set look at the figure, where also one set with the faith ${000}$ is shown. Putting this observation into a rigorous statement I get

Lemma 4 The set of all points with the infinite future faith ${w^+=a_0a_1a_2\ldots}$ is the vertical interval with the ${x}$ -coordinate ${a(w^+)=0.\alpha_0\alpha_1\alpha_2\ldots}$ , where ${\alpha_i=1}$ if ${a_i=0}$ and ${\alpha_i=3}$ if ${a_i=1}$ , and the ${y}$ coordinates fill ${[0,1]}$ .

Exercise 6 Prove the previous lemma.

Similarly, I can look into the past.

Exercise 7 Prove

Lemma 5 The set of all points with the infinite past faith ${w^-=\ldots a_{-n}\ldots a_{-1}}$ is the horizontal interval with the ${y}$ -coordinate ${b(w^-)=0.\beta_0\beta_1\beta_2\ldots}$ , where ${\beta_i=1}$ if ${a_{-i}=0}$ and ${\beta_i=3}$ if ${a_{-i}=1}$ , and the ${x}$ coordinates fill ${[0,1]}$ .

Theorem 6 Consider a double infinite sequence ${w}$ composed of 0 and 1. This sequence can be realized as the infinite faith of one and only one point of the unit square under the action of ${f}$ . The set of all points with the infinite faith consists of only those points, whose ${x}$ -coordinates belong to the Cantor set ${K}$ , situated on the horizontal side of the square, and whose ${y}$ -coordinates belong to the Cantor set ${K}$ , situated on the vertical side of the square.

Proof: Consider ${w}$ . Denote ${a(w^+)}$ its subsequence staring with ${a_0}$ , the other subsequence denote ${b(w^-)}$ . Due to the previous two lemmas we found the set of all points with the future faith ${a(w^+)}$ and with the past faith ${b(w^-)}$ . The intersection of these sets, as the intersection of two intervals in the square, is unique. $\Box$

4. Corollaries

What is the faith of the left fixed point ${x_0}$ ? Clearly, this is

$\displaystyle \ldots0000\ldots$

The faith of the right fixed point ${x_1}$ ?

$\displaystyle \ldots1111\ldots$

But now we can say way more. The point ${x}$ is called periodic with period ${p}$ if ${f^p(x)=x}$ .

Corollary 7 There are infinitely many periodic points of ${f}$ .

Proof: It is obvious that each periodic point has a periodic faith. The opposite actually is also true: if the faith of the point is periodic then the point is periodic! Indeed, consider a periodic faith

$\displaystyle a_{n+p}=a_n$

for all ${n\in\mathbb Z}$ . I claim that ${f^p(x)=x}$ . I have that the points ${f^p(x)}$ and ${x}$ have the same faith. Therefore, by the previous theorem, they coincide. $\Box$

An orbit under an action of ${f}$ is called homoclinic if ${f^n(x)\rightarrow \hat{x}}$ for ${n\rightarrow\pm\infty}$ , where ${\hat{x}}$ is a fixed point, and heteroclinic if ${f^n(x)\rightarrow \hat{x}_1,\,n\rightarrow\infty}$ and ${f^n(x)\rightarrow \hat{x}_2,\,n\rightarrow-\infty}$ .

Corollary 8 The map ${f}$ has infinitely many homoclinic and heteroclinic orbits.

Exercise 8 Prove the corollary.

Exercise 9 Prove that for any two points ${x}$ and ${y}$ there is point ${z}$ whose orbit approaches in the future to the orbit of ${x}$ and in the past to the orbit of ${y}$ .

Exercise 10 Prove that each periodic point of period ${p}$ has a neighborhood that has no other periodic points of period ${p}$ .

5. Sensitive dependence on the initial conditions

Consider a point with a given infinite faith. Assume that someone also recorded a sequence of 0 and 1 by coin tosses. Now let me keep the first faith and also, after, say, ${a_1000}$ , drop the end and add the random sequence. By my construction above there are two points to which these two faiths correspond, moreover, since they are the same up to the 1000th iteration, they will be extremely close to each other (they are within ${1/5^{1000}}$ ), that is indistinguishable from the point of view of any experimental science. And yet one of them quite soon will be absolutely “random,” which puts significant restrictions on the length of predictions we can make.

Smale’s horseshoe

About Artem Novozhilov

Leave a Reply Cancel reply

Welcome!

CV and more

Smale’s horseshoe

Share this:

Like this:

Related

About Artem Novozhilov

Leave a Reply Cancel reply

Welcome!

CV and more