The folds that measure chaos

A matrix that counts the returns measured how complicated a map is by counting the words its orbits can spell, and found the growth rate as the largest eigenvalue of a matrix. That worked because the map was drawn so that its pieces covered one another exactly. The logistic map, $x \mapsto rx(1 - x)$, has no such pieces at almost any parameter, and there is no matrix to write down.

The growth rate survives anyway, in a form that can be read off a graph. Apply the map $n$ times and count how often the graph of the result turns from rising to falling or back. That count of monotone pieces — the folds — grows at the same exponential rate the words would, and it can be counted exactly.

Why folds count words #

The logistic map rises on the left half of the interval and falls on the right, with its peak at $x = 1/2$. Each application folds the interval over once at that peak. Apply it twice and each half is folded again wherever the first step carried a point to 1/2, and so on: every fold in the graph of $f^n$ sits at a point that some earlier step sends to the top of the hump.

A fold is a place where two different itineraries meet. Points just left of a fold and just right of it agree on the other steps, but at the step that takes them to the peak one lands on the rising side and one on the falling side. So the monotone pieces of $f^n$ are the itineraries of $n$ steps that actually occur, and counting folds counts words without ever choosing a partition. For the map of the previous essay the folds were the straight pieces, 2, 3, 5, 8, the Fibonacci numbers; for the doubling map of the orbit written as a word, which is not continuous, the analogue is the $2^n$ binary words.

Michał Misiurewicz and Władysław Szlenk proved in 1980 that for any continuous map of an interval made of finitely many monotone pieces, the topological entropy — the growth rate of distinguishable orbits, however it is defined — is

$$h = \lim_{n \to \infty} \frac{1}{n} \log(\text{folds of } f^n).$$

Chaos, in the sense of entropy, is the rate at which the graph of the iterates wrinkles.

Counting folds without drawing them #

The figure counts each graph’s folds by sampling it, which works for six steps and fails soon after: at $r = 4$ the twentieth iterate has over a million folds, many narrower than any sampling could resolve. So the counts in the tables below are made differently, from the definition of a fold.

The folds of $f^n$ are the points that the first, second, …, $(n-1)$-th iterates carry to 1/2, together with 1/2 itself. Those can be found backwards. A value $y$ has two preimages under the logistic map when $y < r/4$, the height of the peak, and none when $y > r/4$:

$$x = \frac{1 \pm \sqrt{1 - 4y/r}}{2}.$$

Start from 1/2, take its preimages, then their preimages, and so on; add up how many points each level has. That total plus one is the number of folds, exactly, with no curve drawn. At $r = 4$ every level doubles, because every value lies below the peak’s height of 1, so the $n$-th iterate has $2^n$ folds. The counting fails only at parameters where 1/2 is itself periodic, where two levels share a point, and none of the parameters drawn is one.

Folds in a table #

The six columns behave in three different ways. At $r = 3.2$, where orbits settle onto a cycle of two, the folds grow by two at every step, reaching 40 at step 20 — growth by a fixed amount, not by a fixed factor. At $r = 3.5$ they grow faster, to 1,270, but the ratio from one step to the next is still falling, 1.167 at the last step and lower beyond it.

At $r = 3.7$, $3.83$ and $3.9$ the ratio holds nearly steady instead: 1.461, 1.618 and 1.716. At $r = 4$ it is exactly 2, and the twentieth iterate has 1,048,576 folds. A ratio that holds steady is exponential growth, and its logarithm is the entropy: $\log 1.461 \approx 0.379$, $\log 1.618 \approx 0.481$, $\log 1.716 \approx 0.540$ and $\log 2 \approx 0.693$.

Straight lines on a logarithmic axis #

On an axis where equal steps are equal multiples, exponential growth is a straight line and its slope is the growth rate. The lines for $r = 3.7$ and above are straight after the first few steps, each with its own slope. The line for $r = 3.2$ bends flat, because growth by a fixed amount is growth by a smaller and smaller factor. The line for $r = 3.5$ bends more slowly: its folds grow like a power of $n$, faster than any fixed amount per step and slower than any fixed factor.

The distinction matters because a finite table cannot always tell the two apart. Twenty steps of polynomial growth can pass for exponential growth at a modest rate, and the only way to see the difference is to look at the trend: whether the ratio from step to step is still falling, or has settled. An entropy estimate from a finite depth is a guess that has to be watched settle.

Why the top of the range doubles exactly #

The column for $r = 4$ is exact powers of two, and the reason is a change of coordinates. Write $x = \sin^2(\pi\theta/2)$ with $\theta$ between 0 and 1. Then $4x(1 - x) = \sin^2(\pi\theta)$, which is $\sin^2(\pi T(\theta)/2)$ for the tent map $T(\theta) = 2\min(\theta, 1 - \theta)$. In the $\theta$ coordinate the logistic map at $r = 4$ is the full tent map: two straight pieces of slope 2, each carried across the whole interval.

A straight-piece map whose pieces cover everything has the whole of the doubling map’s word structure, so $T^n$ has $2^n$ folds of equal width in $\theta$, and so does $f^n$ in $x$. The change of coordinates bends the picture — folds crowd towards the ends of the interval, where $\sin^2$ is flat — but it cannot create or destroy a fold. That is also why the sampled count in the first figure spaces its samples by $\sin^2$: it samples the tent map’s evenly spaced folds evenly.

Entropy does not care about coordinates. Any continuous change of variable that carries one map to another carries folds to folds and words to words, so the two maps have the same entropy. The logistic map at $r = 4$ and the tent map at full height are one system, as the orbit written as a word already found for their itineraries, and both sit at $\log 2$.

A tent for every entropy #

The tent map need not be at full height. With slope $s$ between 1 and 2, $\theta \mapsto s\min(\theta, 1 - \theta)$ stretches everything by $s$ at every step, its folds multiply by roughly $s$ each time, and its entropy is $\log s$. So the tent maps run through every entropy from 0 to $\log 2$, one for each slope, and they do it in the simplest possible way: uniform stretching, the same at every point.

Milnor and Thurston proved that this family is a complete catalogue in one sense. Every map with a single hump and positive entropy $h$ can be squeezed onto the tent map of slope $e^h$ by a continuous map of the interval onto itself that respects the dynamics — possibly collapsing some intervals to points, but never tearing. At $r = 3.83$ the logistic map collapses onto the tent map of slope $\varphi$: its attracting cycle of three and the intervals that fall into it are squeezed away, and what remains is uniform stretching by the golden ratio.

That gives the entropy a geometric meaning for every parameter at once. The number read off the folds is the logarithm of the one constant stretch that the map’s complicated, uneven stretching is equivalent to, once everything that settles down has been discarded.

Entropy across the family #

Repeat the estimate at 121 parameters and at two depths, and the shape of the entropy across the logistic family appears. To the left of $r_\infty \approx 3.5699456$, where the period doublings of the road paved with doublings accumulate, the two estimates disagree, and the deeper one is smaller at every parameter. That is the signature of an estimate converging to zero. Through the whole cascade the entropy is exactly zero, however complicated the picture of periods 16, 32 and 64 looks.

To the right of $r_\infty$ the estimates draw together and climb, from near zero to $\log 2$ at $r = 4$. The deeper estimate never decreases as $r$ rises, at any of the 121 parameters, and that is not an accident of this computation. Milnor and Thurston proved, in work circulated in 1977 and published in 1988, that the topological entropy of the logistic map is a non-decreasing function of $r$: the map can only become more complicated as the hump grows taller. The proof runs through the dynamics of polynomials on the complex plane, so a statement about a hump on a real interval is proved with complex numbers.

Along the way the curve pauses. The longest flat stretch sits near $r = 3.83$, at 0.481, and it is not the only one.

The window of three #

At $r = 1 + \sqrt 8 \approx 3.8284$ the logistic map acquires a cycle of three, and for a short range of parameters above that the cycle attracts almost every orbit. The cobweb drawn on the left settles onto it within a few dozen steps, exactly as the staircase that shows the whole orbit settles onto any attracting cycle, and the bifurcation diagram shows three points there. A reader of either picture would call the behaviour periodic. The fold counts say otherwise: at $r = 3.83$ they grow by 1.6181 at step 20, and the entropy is $\log\varphi$.

The counts do more than approach the golden ratio. From step 12 they run 752, 1,218, 1,972, 3,192, 5,166, 8,360, 13,528, 21,890 and 35,420, and each is the sum of the two before it, plus 2: $13{,}528 + 21{,}890 + 2 = 35{,}420$. That is the Fibonacci recurrence of the previous essay’s straight-line map, surfacing inside a quadratic map where no straight line was drawn.

The reason is the argument that closed that essay. A continuous map with a cycle of three has intervals that cover each other in the pattern L to R, R to both, whatever the map looks like between the cycle’s points, so its words include all the walks on that graph and its entropy is at least $\log\varphi$. Block, Guckenheimer, Misiurewicz and Young showed in 1980 that no interval map with a cycle of three has less entropy than that. The logistic map in its window of three sits exactly on that lower bound. The attracting cycle takes almost every orbit, and the chaos the cycle forces lives on a set of starting points of zero length, invisible in any drawing of orbits and fully visible in the folds.

Where the doublings end #

The diagram and the entropy curve describe the same parameter range from two sides. The diagram shows what typical orbits do; the entropy measures everything the map does, including on sets of starting points too thin to show. They agree at the point where the doublings end, and the reason is Sharkovskii’s order of periods. A continuous interval map has positive entropy exactly when it has a cycle whose period is not a power of two — a theorem of Misiurewicz — and the cascade is precisely the stretch of parameters where every cycle has period 1, 2, 4, 8 and so on.

So the left end of the entropy curve is flat at zero because the only periods present are powers of two, and it begins to rise at $r_\infty$ because the first cycle of some other period appears immediately beyond it. A constant that does not care which map measures how fast the doublings approach that point; the entropy says what lies on the other side.

Plateaus that are everywhere #

Every window in the diagram — every range of parameters with an attracting cycle — is a flat stretch of the entropy curve. The window of three is the widest, but there are windows of every period, and between any two parameters with chaotic behaviour there is a window. Graczyk and Świątek, and independently Lyubich, proved in 1997 that the parameters with an attracting cycle are dense in the logistic family.

That makes the entropy a strange function. It is continuous, it never decreases, it rises from 0 to $\log 2$, and it is constant on a collection of intervals that is dense in the chaotic range. Yet it is not the kind of staircase that is flat almost everywhere, rising only on a set of zero length. Jakobson proved in 1981 that the parameters where orbits are genuinely chaotic, with no attracting cycle, have positive total length. The entropy climbs on a set with no intervals in it, and that set is not negligible.

Twenty folds deep, and in floating point #

Every estimate stops at step 20. The entropy is a limit, and a finite depth always overestimates where the growth is slower than exponential. The two depths drawn show the direction of the error; they do not reach the limit. At the window of three and at $r = 4$ the estimates have settled to three decimal places, and near $r_\infty$ they have not settled at all.

The folds are counted in floating point. Each level of preimages is computed with square roots, and a preimage close to the peak’s height could in principle be lost or doubled by rounding — the hazard the orbit a computer draws measures on orbits, met here on preimages instead. The sampled and exact counts agree wherever sampling is reliable, and at $r = 4$ the exact counts are exactly $2^n$, but deep iterates near special parameters are where such an error would hide.

And entropy is not what a typical orbit does. How fast two orbits part measures the Lyapunov exponent, the stretching experienced along typical orbits, and the histogram an orbit leaves shows where they spend their time. In the window of three the Lyapunov exponent is negative and the histogram is three spikes, while the entropy is $\log\varphi$. The two measure different things, and the window is where they disagree most plainly.

Still open: whether the windows are dense in the complex plane #

The density of windows is a theorem about real parameters. The logistic family is equivalent to the quadratic family $z \mapsto z^2 + c$, and for complex values of $c$ the corresponding question is whether the parameters with an attracting cycle are dense among all complex parameters — whether every quadratic map of the complex plane can be turned into one with an attracting cycle by an arbitrarily small change of $c$. That is not known. It would follow from the conjecture that the Mandelbrot set is locally connected, which Douady and Hubbard showed has this consequence in the 1980s, and which has been proved at many individual parameters and never in general.

Measuring chaos with a ruler #

The entropy of a map sounds like a quantity that needs a theory of orbits to define and a computer to estimate. For a map of an interval it needs neither: draw the graph of the map applied $n$ times, count its folds, and watch how fast the count multiplies. The logistic family then reads as one curve — zero through the doublings, rising after them, pausing at every window, and reaching $\log 2$ at the top.

When a system’s complexity is hard to define, look for something that can be counted and see how fast it grows. For interval maps that something is the folds, and the growth rate they give is the same number the words, the returns and the matrices gave on the maps where those could be counted.