The entropy in a single orbit

The folds that measure chaos measured the topological entropy of the logistic map by counting folds: the $n$-th iterate of $x \mapsto rx(1 - x)$ goes up and down some number of times, that number grows like $e^{hn}$, and the rate $h$ is the entropy — nought through the cascade of period doublings, $\ln\varphi$ in the window of three, $\ln 2$ at $r = 4$. Counting folds means following the whole map, every point of the interval, through every iterate. A matrix that counts the returns found another route for special maps, reading the entropy off a matrix of transitions between pieces; but only maps with a finite set of pieces that map onto each other cleanly have such a matrix.

This essay follows a third route, which needs neither the whole map nor a matrix. For a map with a single fold, John Milnor and William Thurston showed in work circulated in 1977 that everything about its symbolic dynamics — which itineraries its orbits can have, how many periodic orbits of each period it has, and its entropy — is determined by the itinerary of one orbit, the orbit of the turning point itself. Stretch, fold, and what is left named this kneading theory as a debt and set it aside. The figures here compute it: one orbit, one power series, and the entropy read off where the series first reaches zero.

One orbit, written as signs #

The logistic map rises on $[0, \tfrac12]$ and falls on $[\tfrac12, 1]$, and the turning point $\tfrac12$ is where the fold is. Follow its orbit: $f(\tfrac12) = r/4$, then $f$ of that, and so on, and at each step write L if the point is left of $\tfrac12$ and R if it is right — the itinerary of the orbit written as a word, applied to the one orbit that matters most. At $r = 3.7$ the hero’s cobweb starts at $\tfrac12$, rises to $0.925$ on the right, falls to $0.2567$ on the left, and continues, and the itinerary begins RLRRRRRRLRRRRRRL.

Now turn letters into signs. On the left branch the map is increasing, so it preserves order, and an L contributes $+1$; on the right branch it is decreasing and reverses order, so an R contributes $-1$. Let $\theta_k$ be the product of the signs of the first $k$ letters — whether the $k$-th iterate preserves or reverses order near the turning point’s orbit — and form the kneading series

$$D(t) = 1 + \theta_1 t + \theta_2 t^2 + \theta_3 t^3 + \cdots.$$

Milnor and Thurston proved that if the entropy $h$ is positive, $D$ has a zero at $t = e^{-h}$, and no smaller positive zero; if $h = 0$ it has no zero in $(0, 1)$. The hero draws $D$ for $r = 3.7$ from 160 terms and finds the first zero at $0.68269$, so $h = 0.38172$. A quantity defined by counting every fold of every iterate has been computed from the itinerary of a single point.

The orbit is computed in 400-digit fixed-point arithmetic. That matters, because the orbit is chaotic: each step can multiply an error by as much as $r$, so floating point loses the itinerary after about fifty steps, and a wrong letter changes every $\theta$ after it. With 400 digits, 160 steps lose at most a hundred digits and the itinerary is exact.

Why one orbit is enough #

The theorem can look like magic until the folds are counted the way the fold essay counted them. A fold of the $n$-th iterate is a point where $f^n$ turns round, and it turns round exactly where some earlier iterate passes through the turning point: the turning points of $f^n$ are the points $x$ with $f^k(x) = \tfrac12$ for some $k < n$. So counting folds means counting preimages of $\tfrac12$, and whether $f$ has two preimages of a point $y$, or none, depends only on whether $y$ lies below the maximum value $f(\tfrac12) = r/4$. The maximum is the first point of the turning point’s orbit.

Follow that one step further. The preimages of preimages exist or not according to how the iterated images of the interval sit relative to $\tfrac12$, and the images of the interval are bounded by the points of the turning point’s orbit: $f([0, 1])$ ends at $f(\tfrac12)$, $f^2([0, 1])$ ends at $f^2(\tfrac12)$ or at $f(\tfrac12)$, and so on. Every count of folds is therefore decided by the positions of $f(\tfrac12), f^2(\tfrac12), \ldots$ relative to $\tfrac12$ and to each other — by the itinerary, which records which side each lies on, and by the signs, which record whether each step reverses the order of the points it carries. The kneading series is the bookkeeping that turns this into a generating function for the fold counts, and the first zero of a generating function is the reciprocal of its growth rate.

The orbit of every other point is constrained by the same comparisons. A point’s itinerary must, at every stage, stay on the correct side of the turning point’s, in the order the signs prescribe; Milnor and Thurston’s admissibility condition says exactly which strings of L and R can occur as itineraries of some point, and it is stated entirely in terms of the turning point’s itinerary. The turning point’s orbit is the boundary of the possible, and every count of possibilities — periodic points, folds, words of each length — is a count of strings that stay inside it.

The series against the folds #

The theorem can be checked against the fold count, and the table does it at seven values of $r$. For each, the kneading entropy comes from the series; the fold estimate comes from counting, on a grid of a million points, the monotone pieces of the 13th and 14th iterates and taking the logarithm of their ratio. At $r = 3.7$ the two give $0.3817$ and $0.3747$; at $3.8$, $0.4681$ and $0.4634$; at $3.9$, $0.5400$ and $0.5374$. Where the entropy is small they part — at $r = 3.6$ the series says $0.1974$ and the laps $0.2415$ — because the number of folds grows slowly there and two iterates cannot yet measure its rate; and at $r = 3.5$, inside the cascade, the series has no zero at all and the entropy is nought, while the lap ratio is still well above it.

Two rows are exact. At $r = 4$ the turning point goes to 1 and then to 0, which is fixed, so the itinerary is RLLLL… and every $\theta_k$ after the first is $-1$:

$$D(t) = 1 - t - t^2 - t^3 - \cdots = \frac{1 - 2t}{1 - t},$$

whose zero is $t = \tfrac12$, giving $h = \ln 2$. At $r = 3.83$, inside the window of three, the turning point’s orbit is captured by the attracting cycle of period three, its signs repeat with that period, and the series becomes a ratio of polynomials whose first zero is $1/\varphi$: the entropy is $\ln\varphi = 0.4812$ to every digit printed, the same value the fold count found growing by a Fibonacci recurrence.

The whole family from one point each #

Because each value of $r$ needs only one orbit, the whole family is cheap. The figure computes the kneading entropy at 401 values of $r$ between 3.5 and 4, each from 160 terms in 400-digit arithmetic. It is nought up to the end of the period-doubling cascade near $3.5699$, where it begins to rise; it rises without ever falling; it sits flat at $\ln\varphi$ across the window of three near $3.83$, and on smaller plateaus across the smaller windows; and it reaches $\ln 2$ only at $r = 4$.

That the curve never falls is the deepest fact in the picture, and it is not a fact about kneading series. Milnor and Thurston’s kneading theory shows that the entropy is determined by the itinerary, and that itineraries can be ordered so that a larger itinerary means more entropy; but whether the itinerary of the logistic map’s turning point increases with $r$ is a question about this particular family, and its answer — yes, monotonically — needed complex dynamics. Milnor and Thurston proved it using Thurston’s rigidity theorem for postcritically finite maps, with Adrien Douady, John Hubbard and Dennis Sullivan supplying other proofs. For a family of one-fold maps chosen at random, entropy need not be monotone at all.

Where the doublings end, the Thue–Morse sequence #

The point where the entropy leaves nought is the end of the cascade, $r_\infty = 3.5699456718\ldots$, the accumulation point of the period doublings whose spacing a constant that does not care which map measured. Its turning-point orbit never repeats, and its itinerary is the limit of the itineraries of the cycles of period $2, 4, 8, \ldots$ — each obtained from the last by a doubling rule. The figure computes the signs $\theta_k$ for the first 256 steps and draws the first 128, light for $+1$ and dark for $-1$.

They are the Thue–Morse signs: $\theta_k$ is $+1$ when $k$ has an even number of 1s in binary and $-1$ when it has an odd number, at every one of the 256 steps. The pattern is the one a machine that carries one bit built from binary digit sums, and here it falls out of the logistic map at a single irrational parameter. It has a closed form as a series, because the Thue–Morse signs are exactly the coefficients of an infinite product:

$$\sum_{k \ge 0} (-1)^{s_2(k)}\, t^k = (1 - t)(1 - t^2)(1 - t^4)(1 - t^8)\cdots,$$

where $s_2(k)$ counts the 1s in $k$: expanding the product, each power $t^k$ arises once, from the binary digits of $k$, with one minus sign for each digit. So the kneading series at $r_\infty$ is this product, and every factor is positive on $(0, 1)$, so the product has no zero there and the entropy is nought. The figure draws the series and the product together; they coincide to the width of the line, and both creep down towards nought as $t$ approaches 1 without reaching it.

The entropy is therefore zero at the end of the cascade and positive at every $r$ beyond it — the curve’s corner in the previous figure. Just past $r_\infty$, the signs agree with the Thue–Morse signs for a long stretch and then depart, and the departure makes the series cross zero somewhere very close to 1, giving a small positive entropy; the closer $r$ is to $r_\infty$, the later the departure and the smaller the entropy.

The tent hidden inside #

Why should a single orbit know the entropy? The figure checks the theorem on the maps where the answer is transparent. The tent map of slope $s$ stretches each of its two pieces by $s$, so the $n$-th iterate has pieces stretched by $s^n$ and the number of folds grows like $s^n$: the entropy is $\ln s$. For seven slopes from $1.25$ to 2, each turning-point orbit computed exactly for the fraction $s$, the first zero of the kneading series sits at $1/s$, and every dot lies on the curve $\ln s$.

The tent maps are not a special case but the model for all of them. William Parry showed in 1966, and Milnor and Thurston again in the one-fold case, that every such map with positive entropy $h$ is a tent map of slope $e^h$ in disguise: there is a continuous, monotone change of coordinates — not always one-to-one — that carries its orbits onto the tent map’s, squeezing the parts of the interval where orbits linger and stretching the parts they pass through quickly. That is the general form of the same map in different coordinates, where the logistic map at 4 and the tent map of slope 2 were found to be one map. The kneading series computes $1/s$ for the hidden tent, and it can do so from one orbit because the turning point is the one place where the change of coordinates is forced: the fold of the original map must go to the fold of the tent.

Counting periodic orbits from the same series #

The kneading series does more than give the entropy. Milnor and Thurston’s main theorem expresses the zeta function of the map — the generating function that counts its periodic points of every period, which the matrix that counts the returns computed for Markov maps as $1/\det(I - tA)$ — in terms of the kneading series, roughly as its reciprocal with corrections for the turning point’s own behaviour. So the number of periodic points of each period, for every one-fold map, is determined by the turning point’s itinerary as well. A matrix is not needed, and neither is a finite partition: the single orbit plays the role the matrix played, and when the map happens to be Markov the two computations agree.

That also explains the plateaus of the curve. Inside the window of three, as $r$ increases, the turning point’s orbit is captured by the attracting three-cycle and then by the cycles of period 6, 12, 24 that double from it. Those cycles change the itinerary only in a way the kneading theory calls renormalisation — the itinerary is the window’s base pattern RLR with a doubling cascade substituted into it — and the substituted part contributes a factor to the series with no zero in $(0, 1)$, the same Thue–Morse-like product as at $r_\infty$. The first zero, from the base pattern, does not move, and the entropy stays at $\ln\varphi$ across the whole cascade inside the window, even while new periodic orbits appear. Windows counted like necklaces counted those windows; here each one is a plateau of the entropy for the same reason the entropy is nought at the end of the main cascade.

160 terms check Milnor and Thurston; they do not prove them #

Every orbit is computed in 400-digit arithmetic for 160 steps, and every itinerary is therefore exact for the decimal value of $r$ used. The kneading series is truncated at 160 terms, which locates its first zero to high accuracy when the entropy is not small; near $r_\infty$, where the zero approaches 1 and the series converges slowly there, truncation can create or hide a zero, which is why the curve’s corner is drawn from the theory rather than read from the dots. The fold counts are counted on a grid and miss a few pieces at the edges — the grid finds 16,312 pieces of the 14th iterate at $r = 4$, where there are exactly 16,384 — and the comparison uses ratios, which are less sensitive to the loss.

The figures check the theorem; they do not prove it. That the first zero of $D$ gives the entropy is Milnor and Thurston’s theorem, and the agreement in the table is evidence that the computation implements it correctly. The Thue–Morse identity at $r_\infty$ is checked for 256 signs, and it holds for all of them by the renormalisation argument, not by the check; the monotonicity of the curve is likewise a theorem about the quadratic family, which the 401 dots are consistent with and cannot establish.

Still open: one orbit for maps that fold more than once #

For maps with several turning points, kneading theory generalises: each turning point has an itinerary, the kneading series become a matrix of series, and the entropy is read from the zeros of its determinant. But the monotonicity of entropy in families of such maps is a much harder question. For the cubic maps, with two folds, monotonicity along suitable curves in the two-parameter family was proved only in the 2000s, and for polynomial families of higher degree the statement that entropy is monotone along the natural “isentropes” — the sets where it is constant — was the subject of work by Sebastian van Strien, Henk Bruin and others, completed in its full generality only recently.

And there is a question about the entropy curve itself. It is continuous, monotone and constant on every window, and the windows are dense; so the curve is a devil’s staircase, flat almost everywhere it can be. How the measure of the set of parameters where it is strictly increasing compares with the measure of the windows, and what the curve’s local behaviour is at a typical point of growth, are known only in part — the complement of the windows has positive measure, by Jakobson’s theorem, but the fine structure of the staircase there is still being mapped.

A fold, a point, and a series #

For a map with one fold, the topological entropy is decided by the orbit of the turning point alone: write its itinerary as signs, $+1$ on the rising branch and $-1$ on the falling one, form the power series of their running products, and the entropy is minus the logarithm of the series’ first zero. Computed exactly, that gives $0.38172$ at $r = 3.7$, $\ln\varphi$ across the window of three and $\ln 2$ at $r = 4$, matching the growth of the folds wherever both can be measured. At the end of the period doublings the signs are the Thue–Morse signs, the series is the product $(1 - t)(1 - t^2)(1 - t^4)\cdots$ with no zero to give, and the entropy is nought — and every such map is a tent of slope $e^h$ seen through a change of coordinates that the one orbit is enough to pin down.