Sensitivity comes free

Two starting points a ten-thousandth apart, under a rule with nothing random in it, have nothing in common within forty steps. That is sensitive dependence, and the rate at which such orbits part can be measured and given a number. What has not yet been asked is where the sensitivity comes from — whether it is an extra property a map may or may not have, or a consequence of something more basic.

The definition of chaos that most textbooks use, due to Robert Devaney in 1986, lists three conditions for a map on a bounded space. There must be an orbit that comes arbitrarily close to every point. The periodic points — the ones that return exactly to themselves after some number of steps — must also come arbitrarily close to every point. And the map must have sensitive dependence: arbitrarily close to any point there must be another whose orbit eventually moves a fixed distance away.

In 1992 five mathematicians at La Trobe University — John Banks, Jeff Brooks, Grant Cairns, Gary Davis and Peter Stacey — published a two-page note in the American Mathematical Monthly showing that the third condition is redundant.

The figure is the argument in miniature, on the doubling map. Two points start inside the same tiny interval: one periodic, whose orbit is a finite set of three points it cycles round for ever, and one taken from an orbit that goes everywhere. The periodic point is confined to its three places. The wanderer is not — it must eventually go near any point at all, including a point far from all three of the periodic orbit’s places. At that moment the two orbits are far apart, although they started close. Sensitivity has been produced from the other two conditions without any stretching being assumed.

An orbit that goes everywhere #

The doubling map sends $x$ to $2x$ with the whole part discarded, and in binary it simply deletes the first digit after the point. An orbit that comes close to every point is therefore a number whose binary digits contain every finite string somewhere, since coming within $2^{-k}$ of a point means agreeing with it in the first $k$ digits at some step.

Such a number is easy to write down: list the binary numerals $1, 10, 11, 100, 101, \ldots$ one after another. This is the binary form of the number David Champernowne studied in 1933, and every finite string of digits appears in it, because every string is the numeral of some whole number. The figure follows its orbit for four hundred steps. By step 50 it has visited every one of sixteen strips; for strips of width $1/64$ it would need longer, and for every finite width it gets there eventually.

The orbit is computed on the digits themselves, dropping one at each step and reading the next thirty as the position. Iterating the doubling map on ordinary floating-point numbers would be meaningless here: a double carries 53 binary digits, and the doubling map discards one per step, so after 53 steps the computed orbit is zero whatever the starting point was. The orbit shown is the true orbit of the true starting point.

A map with an orbit that comes close to everything is called topologically transitive, or, in the equivalent form usually proved, one under which every open interval is eventually carried to overlap every other.

Periodic points everywhere #

The second condition asks for periodic points near every point, and for the doubling map they are fractions.

A point returns to itself after $p$ doublings exactly when $2^p x$ and $x$ differ by a whole number — when $(2^p - 1)x$ is a whole number, which is to say when $x$ is a fraction with denominator $2^p - 1$. In binary these are the numbers whose digits repeat with period $p$: $1/3$ is $0.010101\ldots$, $2/7$ is $0.010010\ldots$. The figure checks the arithmetic for every point it draws — doubling $k/(2^p - 1)$ $p$ times returns to $k/(2^p - 1)$.

As $p$ grows the spacing $1/(2^p - 1)$ shrinks to nothing, so every interval eventually contains one. The doubling map has periodic points arbitrarily close to every point: they are dense. This is the structure the sequence of doublings builds on the way into chaos, now present at every scale at once.

The count is worth noticing too. There are $2^p - 1$ points of period dividing $p$, so the number of periodic points grows exponentially with the period, at the rate $2^p$. That exponential rate is not a coincidence of this map. For a large class of chaotic maps the number of periodic points of period $p$ grows like $e^{hp}$, where $h$ is the map’s entropy — the same quantity that the Lyapunov exponent measures for the doubling map, one bit per step. The periodic points are not merely dense; they are plentiful at exactly the rate at which the map generates information.

Why the two conditions force the third #

The argument has a small amount of bookkeeping and one idea. The bookkeeping is a fixed distance $\delta$ to separate orbits by. Since there are infinitely many periodic points, there are two whose orbits are disjoint finite sets; let $\delta_0$ be the least distance between a point of one and a point of the other. Any point $x$ is then at least $\delta_0/2$ from one of those two orbits, since it cannot be close to both.

Now take any point $x$ and any small interval $U$ around it. Pick a periodic point $p$ inside $U$, which exists because periodic points are dense. Pick also a point $q$ from whichever of the two fixed orbits is far from $x$; its whole orbit stays at least about $\delta_0/2$ from $x$ — and, by continuity, from anything that stays near $x$. The transitive point supplies a point $z$ in $U$ whose orbit eventually passes close to $q$’s orbit, at some step $n$.

At step $n$, the orbit of $z$ is near $q$’s orbit, while the orbit of $p$ — which returns to $p$ every period, and so stays near $x$ at the right steps — is far from it. So $z$ and $p$, both in $U$, are far apart at some step. One of them is at least a quarter of that distance from the orbit of $x$ itself, since if both were close to it they would be close to each other. The theorem’s constant comes out as $\delta_0/8$, and it does not depend on $x$ or on $U$: sensitive dependence, with a uniform separation, from two conditions that never mention separation.

The figure shows the core of it with actual numbers: $p = 2/7$ and $z$ both within $0.02$ of $0.3$, the far point at distance $0.286$ from $p$’s orbit, and $z$ reaching it at step 4, when the two are $0.264$ apart.

The same argument, on a map that is not doubling #

The doubling map is the easiest example because its orbits can be read off binary digits, but the theorem is about any continuous map, and the logistic map at its top parameter shows it working where nothing is written in digits.

The logistic map $x \mapsto 4x(1-x)$ is the doubling map in a different coordinate: substituting $x = \sin^2(\pi\theta)$ turns it into $\theta \mapsto 2\theta$ with the whole part discarded. So it inherits a dense orbit and dense periodic points from the doubling map, point for point, and the theorem then says it is sensitive. The two orbits in the figure confirm it the direct way — a gap of a ten-thousandth becomes a gap of order one in eleven steps — but the theorem did not need the confirmation, and it would say the same for any map carried to the doubling map by a continuous change of coordinates, however distorted.

That is the practical value of the result. Sensitivity is a statement about every point and every neighbourhood, and checking it directly means controlling how orbits separate everywhere at once. The two conditions that imply it are often easier: a dense orbit can sometimes be written down, as the Champernowne orbit was, and periodic points can often be found by solving an equation. Proving chaos then needs no estimate of stretching at all.

What the argument does not use #

The proof uses no derivative, no rate of stretching, no measure and no number. It works on any space where distance makes sense, with any continuous map, because it only ever asks where points go, not how fast they get there. That generality is the surprise. The quantity measured as a Lyapunov exponent — how fast nearby orbits separate — is absent from the argument, and yet the conclusion is that nearby orbits do separate.

What it says, in effect, is that sensitivity is a combinatorial consequence of the orbit structure. If orbits go everywhere and periodic orbits are everywhere, then near every point there are orbits of both kinds, and they cannot stay together, because one of them is confined and the other is not.

It also says something about the definition. Devaney’s list was assembled by hand to capture what “chaos” should mean, and the property most people associate with the word — the butterfly, the forecast that fails — turns out to be a consequence of the other two. On an interval, Michel Vellekoop and Raoul Berglund showed in 1994 that more is true: transitivity alone implies that periodic points are dense, so a single condition, an orbit that goes everywhere, gives all three.

Four maps, three conditions #

The theorem says one implication holds. Every other one fails, and simple maps show it.

Turning a circle by an irrational fraction of a full turn — the golden fraction, say — has an orbit that goes everywhere, as the gaps a turning circle leaves show. It has no periodic points at all, since no whole number of irrational turns is a whole turn. And it is not sensitive: a turn moves every point by the same amount, so two points a millionth apart are a millionth apart for ever.

Turning by a fifth is the opposite. Every point returns after five turns, so periodic points are everywhere; no orbit visits more than five places, so nothing goes everywhere; and again distances never change.

Doubling on the whole line, $x \mapsto 2x$ with nothing discarded, is sensitive — two points a millionth apart are a tenth apart after seventeen steps — and has neither of the other properties: every orbit except zero runs off to infinity, and zero is the only periodic point. That is the case a difference too small to draw called predictable despite sensitivity: nothing comes back, so nothing mixes.

The doubling map on the interval has all three. And no map has transitivity and dense periodic points without sensitivity, since that is what the theorem forbids — the one empty row that could have been in the table.

Sensitive and transitive, with no periodic points #

The table has one more combination worth knowing, which no map on it shows. An orbit that goes everywhere, together with sensitivity, does not force periodic points. The standard examples are built from infinite words rather than numbers: take the Sturmian words, the sequences of two letters obtained by cutting a line of irrational slope across a grid and recording whether it crosses a horizontal or a vertical grid line at each step. The set of all such sequences, with the shift that drops the first letter as the map, is transitive and sensitive, and it contains no periodic sequence, because a periodic cutting sequence would come from a line of rational slope.

So the three conditions are logically tangled in exactly one way. Periodic points and transitivity together give sensitivity. No other two give the third: sensitivity and transitivity do not give periodic points, and sensitivity and periodic points do not give transitivity — a map made of two separate chaotic pieces has both and cannot move points from one piece to the other. Devaney’s definition asks for all three, and on a general space only one of them is redundant.

What the figures cannot show #

The figures compute on one map, the doubling map, where everything can be done exactly on binary digits, and the theorem is about every continuous map on every space with a distance and infinitely many points. The strip test for transitivity uses strips of width $1/32$ and a few thousand steps; transitivity is a statement about every width and unlimited time, and a map could pass the test and fail the property at a finer scale.

The separation figure uses a periodic point of period three and a far point chosen as the one most distant from its orbit. The proof chooses its far point from one of two fixed orbits, so that the constant is the same for every $x$; the figure’s choice gives a larger separation at this $x$ but not a uniform one. It shows how the argument works, not the constant it produces.

And the table’s “sensitive” column is measured with one pair of starts. Sensitivity requires a separating neighbour near every point; the test checks one point. For the four maps chosen the answer is the same at every point, which is why one test suffices for them, and not a reason to trust it for maps in general.

The question it leaves: chaos with nowhere to settle #

Every map here sends a bounded space into itself, so its orbits have nowhere to go but round. Devaney’s conditions describe what happens on such a space when the dynamics mixes. Many systems are not like that. A chaotic region can be open: most starting points wander irregularly for a while and then leave it, never to return, and the points that stay for ever form a set of no length at all.

On such a set all three of Devaney’s conditions can hold exactly — the map restricted to it is transitive, has dense periodic points and is sensitive — while almost every point that anyone could actually start from escapes. How long the wandering lasts, how thin the surviving set is, and how those two are tied to the rate of stretching is the subject of the essay on chaos on a set nobody lands on.

The argument of this page applies there without change. On the surviving set, orbits go everywhere and periodic orbits are everywhere, so sensitivity follows; what changes is that the set has no length, and a randomly chosen start almost surely lies off it. The chaos is exact and invisible at once — which is the situation in a great many physical systems that look chaotic for a while and then settle.

Confined and unconfined #

The whole argument is a comparison between two kinds of orbit that live side by side. A periodic orbit is confined to a finite set of places, visited in rotation for ever. A transitive orbit is unconfined, and must eventually go near every point, including every point the periodic orbit avoids. Put one of each in any small interval, as the two conditions guarantee can be done, and they must part, because one of them has to go where the other cannot.

The butterfly, on this reading, is not an ingredient of chaos but a symptom of it. Once orbits go everywhere and periodic orbits are everywhere, a small difference in starting point is enough to put two orbits on different sides of that dichotomy — and no precision of measurement can keep them together, because the separation was never about precision. It was about where the orbits are allowed to go.

There is a lesson in that for how definitions get made. Devaney’s list was written to capture a phenomenon that had been seen in computer experiments — orbits that looked random, forecasts that failed — and it included the property that seemed most characteristic. The analysis then showed that the characteristic property was the least independent of the three. That is common: the most visible feature of a phenomenon is often a consequence of less visible ones, and a definition that lists it separately is describing the phenomenon rather than its causes. The two-page proof moved sensitivity from the list of causes to the list of effects, and the definition of chaos has been taught with that footnote ever since.