On November 30th 1889 the French mathematician Henri Poincaré had a problem. He had been awarded a mathematical prize, offered by no lesser person than King Oscar II of Sweden, for his work on a question that was bothering mathematicians. Using Newton's laws of motion and gravitation you can in theory work out how a number of objects (say stars, planets and moons) should move due to the gravitational pull they exert on each other. If there are only two bodies involved the answer is straight-forward: they move along curves that are easy to describe (ellipses in the case of a planet orbiting a star). The problem was, what happens if you throw a third object into the mix?
Stephen Smale talks about the horseshoe at a (somewhat noisy) press conference at the Heidelberg Laureate forum 2017. Click here to see a video of Smale talking about other aspects of his work, and his career in general.
Things get tricky in this case, but Poincaré did some outstanding work trying to characterise motions that could result in a system with three bodies. The problem he had in November 1889 was that the work contained a mistake. Poincaré did the right thing. He owned up and even paid for the copies of his work that had already been printed. He revised his competition entry, still got the prize, and later wrote more extensively about what the mistake had revealed to him. What it had revealed was the existence of chaos.
Fast forward to 1960 and the beaches of Rio, where the mathematician Stephen Smale was thinking about a problem inspired by the maths of radio waves. The complexity of the problem worried him, especially since he had previously conjectured that there was no such thing as chaos. "I made some pretty bad predictions," he says. "[Norman] Levinson at MIT pointed out that there were these old papers by a pair of English mathematicians [Mary Cartwright and J. L. Littlewood]. They had interesting results which contradicted what I had predicted, and I wanted to understand what they did. So I put what I did in a very geometric context so I could understand it."
The result is now know as Smale's horseshoe map. It beautifully encapsulates how chaotic dynamics can arise in mathematics and goes straight to the heart of the problems Poincaré had encountered when thinking about his three-body problem. "Poincaré got a big mess, and [the horseshoe] put order in the mess."
Look at the region shown below, made up of a square with two rounded-off ends stuck on at the top and at the bottom. Imagine picking this region up, squeezing it in the horizontal direction and stretching it into the vertical direction so that it becomes long and thin, and then bending it round to the right to form a horseshoe. Now place it back down into the original region as shown. (We could describe this operation using mathematical formulae, but the beautiful thing is that we don’t need to — as you’ll see, the essence of the dynamics can be captured conceptually.)
The horseshoe map.
Since the horseshoe is part of the original region we can ask what happens to it when we perform the squeezing, stretching and bending operation on again. This squeezes and stretches the horseshoe and then folds it into a "four-stranded" horseshoe sitting within the simple horseshoe.
Applying the horseshoe map twice to the region D gives a folded horseshoe.
Performing the operation on again turns the four-stranded, once-folded horseshoe into a horseshoe that’s folded over twice and has eight strands. You can imagine how this continues as you perform the operation again and again: you get ever more snaky horseshoes with ever more strands. The simple horseshoe operation leads to quite a bit of complexity when you apply it repeatedly.
The operation gives a dynamical system: as you apply the operation repeatedly, points in the region are moved around . A point in is moved by the operation (which we’ll call ) to another point in the horseshoe, which in turn is moved to a point in the folded horseshoe when you apply again, and so on. You can continue like this indefinitely to get an infinite sequence of points. That sequence is called the forward orbit of .
The point x-1maps to the point x0 under f, which in turn maps to x1.
We can also go the other way around. Rather than asking where a point goes to under you can ask where it comes from. Is there a point in that goes to when you apply to it? There may not be such a point, but if there is we call it . Similar we write for the point that goes to under (if it exists), for the point that goes to under (if it exists), and so in. The sequence is called the backward orbit of .
All the exciting things happen on the Square that forms the body of the shape . If is in , then there’s no guarantee that is also in — it could lie in the U-bend above or in the two ends sticking out from its bottom edge. However, for some points , the point does lie in : if that’s the case then lies in one of the two vertical strips in which the horseshoe intersects the square .
If x0 is in S and x1 is also in S, then x1 lies in one of these two vertical strips.
A bit of thought will convince you that must therefore lie in one of two horizontal strips, and . As you apply to the square, these horizontal strips get squeezed horizontally and stretched vertically, and after the horseshoe has been formed, get put down on our two vertical strips. Points in that are not within these horizontal strips get mapped to the U-bend, or the two ends sticking out from the bottom edge.
If x0 is in S and x1 is also in S, then x0 lies in one of the two horizontal strips.
What can we say about points whose entire forward and backward orbits lie in ? You can start drawing pictures of where horseshoes with increasing number of folds go to or come from as you apply , or backwards, repeatedly. It’ll give you a headache after a while, but it’s worth it, as the structure you’ll find is very interesting. However, we won’t do this here: there’s a neater way to figure out the dynamics of on the collection of points whose orbits never leave .
First, write for this collection of points whose forward and backward orbits don’t leave . Given a point in think of any other point in the orbit of , where can be positive or negative. The point is the next point along the orbit. And since the entire forward and backward orbit of lie in , we know that and both lie in . By exactly the same reasoning as above, this means that lies in one of the two vertical strips, which in turn means that lies in one of the two horizontal strips or . That’s true for any , in other words, it’s true for every point in the forward and backward orbits of . As you move through the orbits, the points bounce around between and .
This means we can write down a sequence for each in . First, write down a if in and a if in . Now look at and write down a if in and a if it’s in . Then look at and write down a if in and a if it’s in . And so on. For each point in the forward orbit of you write down a or a . This gives you an infinite sequence of s and s.
We can write down a sequence for the backward orbit of in a similar way, only now we write it from right to left. The first entry (on the right) is if is in and if is in . The second entry (from the right) is if is in and if is in . And so on. This gives a sequence of s and s, infinite in the left.
Now glue the two sequences together, with a dot between the sequence to separate them. For example the sequence
denotes the point whose entire backward and forward orbits lie in .
The point p whose sequence consists entirely of 1s.
It turns out that the correspondence between these bi-infinite sequences and points in whose orbits never leave the square is exact. You can prove that for every point in there is a unique bi-infinite sequence with a dot, and for every bi-infinite sequence with a dot there is a unique point in . If two points in are close to each other, then their corresponding sequences agree to a large number of places to the left and right of the dot, and vice versa — the closer they are, the more places agree. And best of all, applying the map to a point in corresponds to shifting the dot in its sequence to the right by one place, and applying backwards corresponds to shifting it along to the right by one place. This kind of symbolic dynamics is used a lot in the theory of dynamical systems and it often makes things marvellously transparent, as we will see next.