Iteration
Named by 33 essays across 7 fields — each of them below, with the objects they name alongside it.
The staircase that shows the whole orbit
Take a number, feed it to a rule, feed the answer back in. There is a way of drawing that on the rule's own graph which turns the entire future of a starting point into a shape — and the shape is legible.
A point that pulls, and a point that pushes
Every crossing of a curve with the diagonal is a value the rule leaves alone. Whether anything ever arrives there is decided by one number — the slope at the crossing — and the picture makes the reason obvious.
A difference too small to draw
Two starting points a ten-thousandth apart, under the same rule, with nothing random anywhere. Within forty steps they have nothing in common — and the rule was not doing anything to them that it does not do to everything.
The shape in every picture of itself
One line of arithmetic, repeated, with a single complex number as its only input. Sort the numbers by whether the result stays bounded and the boundary between the two answers is the most complicated object anyone draws from a rule this short.
One c, one picture
The same iteration, with the parameter held still and the starting point varied instead. Every complex number gets its own picture, and moving the parameter a hair can shatter it into dust.
Where Newton's method goes instead
An algorithm designed to find roots, run from every starting point at once. Three roots, three basins, and a boundary at which all three are arbitrarily close — so a rule with no randomness in it has starting points whose answer cannot be predicted.
Eight rules and a triangle
A row of cells, each one deciding its next state from the three above it. Eight cases, one bit of output each — a rule that fits in a byte, and 256 of them in total. One of those bytes draws Pascal's triangle.
The rule that computes
One of the 256 elementary rules can run any program. Not simulate one, not approximate one — a machine that can compute anything computable, built from a lookup table with eight rows and nothing else.
Three gaps and no more
Turn a circle by the same irrational angle over and over. The points never repeat and never settle, and yet at every single stage the gaps they leave take at most three different lengths — never four, at any number of steps, for any angle.
The orbit that must come back
A system with finitely many states has to repeat itself. Poincaré showed the same thing holds when the states are a continuum — almost every starting point returns arbitrarily close to where it began, however complicated the rule, and the argument is the pigeonhole principle with volume in place of counting.
The question nobody can answer
Halve it if it is even, triple it and add one if it is odd. Every number anyone has tried comes down to one. Nobody can prove they all do, and the reason is not that the problem is hard to state.
A map that shrinks everything
One extra hypothesis — that every distance is shortened by at least a fixed factor — turns the existence of a fixed point into its uniqueness, an algorithm for finding it, and a bound on the error after any number of steps.
![The same map, written in the basis of its own eigenvectors. Three panels: the map [2, 1, 1, 2] on the standard grid, the diagonal stretch by 3 and 1 it becomes on the eigenvector grid, and the two put back together.](/f/the-same-map-written-in-the-basis-of-its-own-eigenvectors-fd61d7c3.svg)
The same map in a better basis
Measured along its own invariant directions, a linear map stops shearing and becomes two independent stretches. Nothing about the map has changed; the grid it is described against has.
How fast the staircase arrives
The slope at a crossing decides whether an orbit reaches it. The same number decides how fast — and when the slope is zero the arithmetic changes kind, from a fixed factor per step to a doubling of the correct digits.
The same map in different coordinates
The tent map and the logistic map at four look nothing alike and are the same map, carried onto each other by a change of variable. Everything either one does the other does, and the change of variable is a sine squared.
The histogram an orbit leaves
When no single step of an orbit is worth reporting, what is left is where it spends its time. That distribution is not uniform, it does not depend on where the orbit started, and it can be computed in closed form.
The orbit a computer draws
A chaotic orbit computed in floating point is not the orbit of the point it started from. Sometimes it is the true orbit of a nearby point, which is enough; sometimes the arithmetic simply runs out, and the picture is of the rounding.
An ordinal as a growth rate
Index a family of functions by the ordinals, each one iterating the last, and the index becomes a measure of how fast a function grows. The point where the index leaves what arithmetic can prove is exactly where the Goodstein sequence became unprovable.
Every flat graph is a pile of circles
A graph that can be drawn without crossings can be drawn in one particular way: as circles, one per vertex, touching exactly when their vertices are joined. The picture is not a choice — it is determined, up to the group two inversions generate.
Every site in the middle of its own cell
Move each point to the centre of mass of its own Voronoi cell, then redraw the diagram, then do it again. The rule is two lines long, it never mentions hexagons, and what it settles into is a honeycomb.
The flow that is really a map
A trajectory wandering through three dimensions is hard to reason about. Record only the successive maxima of one coordinate and the wandering collapses onto a curve — a map of an interval to itself, with a corner in the middle, which is a thing the theory can handle.
A closer start buys only time
Two trajectories from almost the same place separate exponentially, and the rate does not depend on how close they began. Halving the initial error buys one fixed interval of extra agreement, and no amount of precision buys more than a fixed number of those.
Stretch, fold, and what is left
A system that pushes every pair of nearby points apart and keeps them all inside a bounded region has only one option, and it is the one a baker uses. Stretching and folding is the mechanism, and what survives infinitely many folds is a Cantor set.
Almost every number comes down
The Collatz conjecture is open and a great deal about it is not. Whether a number falls below its own start in the first few steps is decided entirely by its remainder on division by a power of two, and the share of numbers for which it happens can be counted exactly.
The heuristic that cannot be a proof
There is a two-line argument that the Collatz conjecture is true, it is convincing, and everybody who works on the problem believes it. It also cannot be turned into a proof, and understanding exactly where it fails is more instructive than the argument itself.
How long until it forgets
The essays before this one settle where a chain ends up and how much time it spends there, and none of them asks how long the settling takes. That question has an exact answer, it is a single number, and it is the only thing any practical use of a chain depends on.
An area that never finishes
Newton's method's famous failure is a boundary, and a boundary has no area — a random start misses it with probability one. The real failure is different in kind: a polynomial with small whole-number coefficients whose method has a region of starting points, with area, from which it provably never terminates.
Covering rather than avoiding
Two arguments say no starting guess is safe: the boundary is fractal and some regions are permanently trapped. The repair is not a better guess. It is a fixed list of starting points, computed from the degree alone, from which every root of every polynomial of that degree is found.
A collision that finds a factor
A walk through the remainders modulo a number must eventually repeat, and it repeats modulo each hidden prime factor long before it repeats modulo the number. Pollard saw that the earlier repeat can be detected without knowing the prime — and that its timing is the birthday problem, so the cost is the square root of the factor.
The sum of the parts, taken again
Replace a number by the sum of its proper divisors and do it again. Most numbers fall to 1, a few land on a perfect number or a cycle, and some climb for hundreds of steps. Below a thousand there are twelve whose fate nobody knows — and the thing that keeps them climbing is a perfect number hiding in their factorisation.
A road where nobody overtakes
Rule 184 moves every 1 one cell to the right whenever the cell ahead is empty. It is one of only five elementary rules that never change the number of 1s, and that single property turns it into a model of traffic with an exact transition: below half density every jam dissolves, above it jams can never all clear and drift backwards against the flow.
A double root halves the error instead of squaring it
Near an ordinary root, Newton's method squares its error at every step and a handful of steps reach full precision. Near a double root it only halves the error — twenty steps where five would do, and a ceiling of about eight correct digits that no number of steps can break through. Doubling the step repairs the double root and ruins the simple one.
A cubic method that is Newton's in disguise
Halley's method, from 1694, uses the second derivative as well as the first and cubes the error at every step where Newton's squares it. It is also, exactly, Newton's method applied to a different function — p divided by the square root of p′ — and that single fact explains why its basins are calmer, why it walks out of the trap that holds Newton for ever, and why its boundaries are still fractal.
Named alongside it
The objects these essays reach for when they reach for this one.
OrbitFixed pointBasin of attractionNewtons methodConvergenceConvergence rateDerivativePeriodic orbitRoot-findingChaosComplex numbersFractal