The orbit written as a word

Take the map that doubles a number and throws away the whole part: $x \mapsto 2x \bmod 1$. Start somewhere and follow the orbit. Rather than record where each step lands, record only which half of the interval it lands in — L for the left half, R for the right.

The orbit becomes a word. And for this particular map the word is not merely related to the starting point; it is the starting point, written in binary.

That coincidence is the whole subject in one instance. A dynamical question has become a question about strings, and strings are things that can be counted.

Why the word is the expansion #

Doubling a number in binary moves the binary point one place right. If $x = 0.b_1b_2b_3\dots$ then $2x = b_1.b_2b_3\dots$, and taking the fractional part deletes $b_1$, leaving $0.b_2b_3\dots$.

So the map does exactly one thing to the expansion: it drops the first digit. And which half $x$ lands in is decided by $b_1$ — the number is at least a half exactly when its first binary digit is 1.

Reading the itinerary of an orbit therefore reads the digits of the starting point in order. Nothing about the argument is a coincidence of the doubling map’s shape; it is the statement that base-2 expansion is a coding of this dynamical system, and the coding was there in the notation before anybody looked for it.

The map, once the coding is made #

Under the coding the doubling map becomes the shift: the operation on infinite words that deletes the first letter. That is about as simple as a map can be, and everything difficult about the doubling map has been moved into the correspondence rather than removed.

What has been gained is that the shift’s orbits are transparent. A word is periodic exactly when it repeats; it is eventually periodic exactly when it repeats from some point on; and any word at all can be written down, so any behaviour that can be described in symbols occurs.

That last point is worth spelling out because it is the fastest route to several theorems.

A dense orbit exists. Write down a word containing every finite block: all blocks of length 1, then all of length 2, then all of length 3, and so on. The orbit of the corresponding point comes arbitrarily close to every point of the interval, because coming close means agreeing in many leading digits, and every block appears.

Points with any prescribed behaviour exist. An orbit that visits the left half a million times and then the right half once, and repeats — write the word. An orbit that is not periodic but never enters the middle third — write a word avoiding the blocks that would put it there.

Sensitive dependence is a triviality. Two points agreeing in their first $k$ digits and differing after are within $2^{-k}$ of each other, and after $k$ steps their orbits differ in the first digit — so they are on opposite sides of the interval. A difference too small to draw makes this point with a measurement; in symbols it is the observation that the shift moves a disagreement toward the front one place per step.

Counting the periodic orbits #

Here is the payoff that makes the coding worth setting up. How many points come back to themselves after $n$ doublings?

Under the coding a point is fixed by $n$ shifts exactly when its word is periodic with period dividing $n$ — which means the word is a block of length $n$ repeated for ever. There are $2^n$ blocks of length $n$, so there are $2^n$ such points.

The direct computation confirms it. A point fixed by $n$ doublings satisfies $2^n x \equiv x \pmod 1$, so $x = k/(2^n - 1)$ for a whole number $k$, and there are $2^n - 1$ such points plus the point 0 — which is $2^n$.

Two counts, one over words and one over congruences, agreeing at every length up to eight. That agreement is the kind of thing this site asserts rather than states, and it is asserted here on every word: for each block of length $n$, the point its repetition names is computed and its itinerary is read back and required to be the block.

Orbits against points, and a familiar count #

Points fixed by $n$ doublings come in orbits of size dividing $n$, so the count of orbits is smaller and less regular: 2, 3, 4, 6, 8, 14, 20, 36 for $n$ from 1 to 8.

Those numbers have been met before. Counting binary words of length $n$ up to rotation is counting binary necklaces, and necklaces that prove a theorem does exactly that — using the count to prove Fermat’s little theorem, by observing that when $n$ is prime every non-constant necklace has exactly $n$ rotations, so $2^n - 2$ is divisible by $n$.

So the periodic orbits of the doubling map are the necklaces, and a theorem in number theory is a theorem about how a dynamical system’s orbits are distributed among periods. Neither subject needs the other and each explains the other’s count.

Where the coding is exact, and where it is not #

The doubling map’s coding is a genuine equivalence: every infinite word corresponds to a point, every point to a word, and the shift corresponds to the map. The only blemish is that dyadic rationals have two expansions — 0.1000… and 0.0111… name the same point — which is the same blemish decimals have with 0.999…, and it affects countably many points.

For other maps the coding is coarser and still useful. The tent map at full height, $x \mapsto 2\min(x, 1-x)$, has the same two-letter coding with a twist: the right branch is decreasing, so the itinerary is a reflected binary code and the correspondence is a relabelling rather than the identity. The logistic map at $r = 4$ is conjugate to the tent map by a change of variable, so it inherits the same coding through a substitution.

Below full height the coding stops being onto: some words never occur, because the map’s image no longer covers the whole interval. What is left is a subshift — the set of words obeying some rule about which blocks may follow which — and describing that set is how the dynamics of the whole family is organised. The bifurcation diagram that the road paved with doublings draws is, read symbolically, a record of which words become available as $r$ rises.

Forbidding blocks, and counting what is left #

The doubling map allows every word. A more interesting system allows some and not others, and the standard way to specify which is by a list of forbidden blocks.

Forbid the block RR — no two consecutive steps in the right half. What is left is a set of words closed under the shift, and counting the allowed words of length $n$ is a small exercise: let $a_n$ be the number ending in L and $b_n$ the number ending in R. A word ending in L can be extended either way; one ending in R only by L. So $a_{n+1} = a_n + b_n$ and $b_{n+1} = a_n$, which is the Fibonacci recurrence, and the count of allowed words grows like $\varphi^n$ rather than $2^n$.

That growth rate has a name — the topological entropy of the system, defined as $\lim \frac{1}{n}\log(\text{words of length } n)$ — and it is the single most useful number attached to a symbolic system. The full shift on two letters has entropy $\log 2$; the RR-forbidden system has $\log \varphi \approx 0.481$; a system with only periodic words has entropy 0.

The recurrence generalises. A set of forbidden blocks of length 2 is a matrix of which letters may follow which, and the number of allowed words of length $n$ is the sum of the entries of the $n$-th power of that matrix — so the growth rate is its largest eigenvalue. Counting orbits has become an eigenvalue problem, which is the point at which the symbolic method stops being a description and starts being a computation.

What the coding gives up #

A coding is a lossy translation and it is worth being precise about the loss.

Distance is not preserved exactly. Two words agreeing in $k$ leading letters name points within $2^{-k}$, and points within $2^{-k}$ usually agree in about $k$ leading letters — but not always, since 0.0111 and 0.1000 are adjacent and share no digits. The correspondence is continuous except on a countable set, which is enough for topology and not enough for anything metric.

Smoothness is invisible. The shift has no derivative and needs none. Every statement provable about the doubling map by symbolic means is a statement that survives any conjugacy, so anything depending on the map being smooth — Lyapunov exponents, the exact rate at which orbits separate — has to be reintroduced afterwards. How fast two orbits part measures a quantity the coding cannot see.

And the coding has to be chosen. Cutting the interval at $1/2$ works because $1/2$ is where the map’s branches meet. Cutting anywhere else gives a partition whose itineraries do not determine the point, and the whole method collapses. A partition with that determining property is called generating, and finding one for a given system is the difficult step; for most systems of interest none is known.

The three questions the coding answers immediately #

A dynamical system is usually interrogated with three questions, and for the doubling map all three become one-line answers once the words are available.

How many periodic orbits, and how are they distributed? Counted above: $2^n$ points of period dividing $n$, falling into the necklace counts. The periodic points are dense, because any point’s expansion can be truncated at $k$ digits and repeated, giving a periodic point within $2^{-k}$ of it.

Is there an orbit that goes everywhere? Yes, and it is written down rather than proved to exist — the word listing every block in turn. Contrast the question nobody can answer, where the orbits of a map only a little different resist every attempt at description.

What does a typical orbit do? Almost every real number has a binary expansion in which each block of length $k$ appears with frequency $2^{-k}$ — Borel’s normal number theorem, 1909 — so almost every orbit spends half its time in each half, a quarter of its time in each quarter, and so on. That is equidistribution, and in symbolic terms it is a statement about digit frequencies rather than about dynamics at all.

The third answer carries the sharpest lesson of the coding. Borel’s theorem says almost every number is normal, and not one explicit number has ever been proved normal in base 2 by an argument that was not designed for it. It is not known whether $\sqrt 2$, $\pi$ or $e$ is. So the coding hands over a complete description of what almost every orbit does while leaving the behaviour of every orbit anybody can name entirely open — which is a distinctive way for a subject to be both settled and useless.

Where it came from #

Hadamard used symbol sequences in 1898 to describe geodesics on a surface of negative curvature, coding a path by which side of each of a set of curves it passed. That is the first appearance of the method and it was invented for exactly the reason it is used now: to replace a continuous object with a discrete one that can be enumerated.

Morse and Hedlund named the subject in 1938 and gave it its first systematic treatment, including the Thue–Morse sequence — a word with no block repeated three times in a row, built by a substitution rule.

Smale’s horseshoe, in the 1960s, made the method central. He showed that a map with a certain geometric configuration contains an invariant set on which the dynamics is exactly the shift on two symbols, and that the configuration arises whenever a system has a transverse homoclinic point. That converts a hypothesis about one orbit into a complete description of an uncountable invariant set, and it is the standard route by which chaos is proved rather than observed.

What the pictures cannot show #

Every orbit drawn here is finite and every word is a prefix. The statements are about infinite words, and an infinite word is exactly the thing a drawing cannot contain — the figures show five or six letters and assert the mechanism that produces the rest.

The starting points are dyadic rationals, chosen so that the arithmetic is exact and the orbit terminates. That makes every drawn orbit eventually fixed at 0, which is atypical: almost every point has an infinite non-repeating expansion and an orbit that never settles. A drawing of such an orbit would be a smear of points, which is what a difference too small to draw shows and what makes the symbolic description worth having.

And the dense orbit described above cannot be drawn at all. Its word is built by concatenating every block in turn, so its first few thousand letters are a listing rather than a pattern, and the point it names has no shorter description than the construction itself.

The ladder from here #

Below: the staircase that shows the whole orbit, the cobweb these figures are drawn on, and numbers that wrap, which supplies the arithmetic modulo $2^n - 1$. Sideways: necklaces that prove a theorem, the same count of periodic orbits used for a different purpose, and a difference too small to draw, the behaviour the coding makes obvious. Above: subshifts of finite type and their transfer matrices, topological entropy as the growth rate of the word count, Markov partitions, and Smale’s horseshoe.

What is worth carrying away #

Two systems are the same system if a relabelling turns one into the other, and the doubling map’s relabelling was sitting in ordinary binary notation the whole time. Once it is noticed, questions about where an orbit goes become questions about which blocks a word contains — and those are questions with answers, because words can be listed.

The general move is worth naming. Find a partition whose itineraries determine the point, and a continuous system becomes a discrete one with no loss. What is gained is counting; what is lost is everything metric. The trade is nearly always worth making first and undoing afterwards.