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 and respectively. Now I shrink five times vertically and stretch the results five times horizontally and place the result on . The same is done for (see the figure).
In this way I define a map of the unit square into itself. I can continue my iterations and consider the dynamical system generated by . Moreover, since it should be clear that an inverse map is defined, then I can consider the composition
for any . To see that this actually makes sense I must show that there are at least some points for which is defined for all . Two such points are found immediately, they have coordinates and . These are fixed points of my map :
Exercise 1 Prove that these points are indeed fixed under the action of .
Are there any other points for which 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 and divide it into 5 equal parts. Drop the first, third and the fifth intervals. Next, each of the remaining intervals (these are and , 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 -st rank then to get the intervals of the -th rank divide each interval into five parts and drop first, third and fifth. Let be the union of all intervals of the -th rank.
Definition 1 The Cantor set is the intersection of all :
First thing is to show that this definition makes sense, that is set is not empty. For this I will use the base 5 numerical system. This simply means that if my point can be written as
then I will use the notation , where all . Using this convention I have that the first rank intervals can be written as
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:
What about the second rank intervals? Clearly, I have four intervals for
Or, in other words, all the numbers in these four intervals of the form where (again, if I properly take care of the right ends of the intervals). See the figure.
Exercise 2 Prove
Lemma 2 Let be such that and . Then .
This lemma tells me that all the numbers from that are in have the representation in base 5 system as
Exercise 3 To finish the construction prove
Lemma 3 Let be such that . Prove that .
Now I can prove that there are “as many points in ” as in the whole interval .
Exercise 4 Build a bijection between the points from and points of the interval . Hint: Consider representation of points in in the base 2 numerical system.
Exercise 5 Prove that the length of all dropped intervals in the construction of the Cantor set is 1, that is
3. Dynamics of
For some points of my square I considered the map , which send the points of and into and . 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 and if the point belongs to . 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 or ? Clearly, these are the points that under the zeroth iteration of (which is the identity map) lay into or . The points with the faith of length 2 must satisfy the fact that is in or and is in or . In other words, what is the set of points whose faith has the form , , , . To see this set look at the figure, where also one set with the faith is shown. Putting this observation into a rigorous statement I get
Lemma 4 The set of all points with the infinite future faith is the vertical interval with the -coordinate , where if and if , and the coordinates fill .
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 is the horizontal interval with the -coordinate , where if and if , and the coordinates fill .
Theorem 6 Consider a double infinite sequence 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 . The set of all points with the infinite faith consists of only those points, whose -coordinates belong to the Cantor set , situated on the horizontal side of the square, and whose -coordinates belong to the Cantor set , situated on the vertical side of the square.
Proof: Consider . Denote its subsequence staring with , the other subsequence denote . Due to the previous two lemmas we found the set of all points with the future faith and with the past faith . The intersection of these sets, as the intersection of two intervals in the square, is unique.
What is the faith of the left fixed point ? Clearly, this is
The faith of the right fixed point ?
But now we can say way more. The point is called periodic with period if .
Corollary 7 There are infinitely many periodic points of .
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
for all . I claim that . I have that the points and have the same faith. Therefore, by the previous theorem, they coincide.
An orbit under an action of is called homoclinic if for , where is a fixed point, and heteroclinic if and .
Corollary 8 The map has infinitely many homoclinic and heteroclinic orbits.
Exercise 8 Prove the corollary.
Exercise 9 Prove that for any two points and there is point whose orbit approaches in the future to the orbit of and in the past to the orbit of .
Exercise 10 Prove that each periodic point of period has a neighborhood that has no other periodic points of period .
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, , 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 ), 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.