Small rules, large behaviour — page 3
Two chaotic orbits made to agree
Chaos means two copies of a system started a hair apart soon have nothing in common. Couple them — let each take a fraction ε of its next step from the other — and above a definite strength they agree to every digit for ever, while each stays exactly as chaotic as before. The strength needed is read off the same number that measured the chaos: the Lyapunov exponent.
Small Mandelbrot sets among the cubics
For most cubics Newton's method finds a root from almost every start. For some it does not: a whole region of starting points falls into a cycle and never finishes. Which cubics are the bad ones is decided by a single starting point — the one critical point that is not a root — and when the cubics are laid out in a plane and coloured by where that point goes, the bad ones form small, exact copies of the Mandelbrot set.
The diamond that freezes its corners
A square board's domino tilings grow like 1.3385 choices per square. Arrange the same squares in a staircase-edged diamond and the count is exactly 2 to the n(n+1)/2 — only 1.1892 choices per square, at every size. The boundary has reached into the middle. Pick one of the diamond's tilings at random and the reason is visible: outside the circle inscribed in the diamond the dominoes are frozen into solid brickwork, and only inside it is the tiling free.
One constant for each shape of top
Feigenbaum's 4.669 is the same for every smooth one-humped map — provided the hump is rounded like a parabola. Make the top flatter, like the graph of x to the fourth, and the doublings crowd together at 7.285; make it sharper, like x to the power 1.25, and they crowd at 3.260. Measured across twenty shapes of top, the constant is a smooth rising curve with 4.669 as one point on it, and the spatial constant falls as it rises.
One type up
A numeral is an iterator, and the formula it proves fixes what it may iterate. At the lowest type it can only repeat the successor, and every function it computes is a polynomial — no predecessor. Let the same numeral iterate a function on functions and 2ⁿ appears; let it iterate a function that takes a function and returns a value, and the predecessor appears at size 15; let it iterate a pair of values, and the predecessor, halving and parity all arrive at size 16. The trick is Kleene's, from 1932, and an exhaustive search finds it without being told.
When a press skips its own light
In Lights Out every board can be turned from all off to all on, because each press toggles its own light. Change the rule so a press toggles only the neighbours and the guarantee is gone: 310 of the 3,600 boards up to sixty by sixty cannot be lit. A single comparison of powers of two predicts every one of them, and on general graphs the answer depends on whether the number of vertices is odd or even, for a reason that is one line of algebra.
A crowd of clocks that falls into step
Give a thousand oscillators a thousand different natural rhythms and let each be pulled towards the average phase. Below a definite pull nothing happens; above it a cluster forms and grows, and Kuramoto's 1975 calculation says exactly where: at twice the spread of the frequencies, with the order growing as the square root of one minus the threshold over the pull. A simulation lands on that curve to the third decimal.
The caustics only an ellipse keeps
A billiard ball in an elliptical table touches the same confocal ellipse or hyperbola with every segment of its path, for ever. Bend the table by a percent and a half and most of those curves survive, but the one turning a quarter-turn per bounce breaks into a chain of four islands whose width grows like the square root of the bend. Birkhoff asked in the 1920s whether the ellipse is the only table that keeps them all; it is still not known.
The fraction written on every bulb
Round the edge of the Mandelbrot set's cardioid hangs one bulb for every fraction between nought and one. The fraction is the bulb's address, its period, and the turn its cycle makes round a fixed point, all at once, and it sets the bulb's size as well: sin(πp/q)/q², which 245 computed bulbs obey to within fourteen per cent.
A best reply to the past
Let two players each answer the whole history of the other's play as though it were a fixed plan. In a zero-sum game the history closes in on the equilibrium, as Julia Robinson proved in 1951. In Lloyd Shapley's three-by-three game it never does: play runs round six profiles for ever, each run the one before plus the one three before plus two, so the runs grow by the real root of x³ = x² + 1 and every run is a fixed share of all the history.
Three hundred thousand outputs of nearly nothing
Start the Mersenne twister from a state with a single 1 among its 19,937 bits and it puts out zeros, then sparse ones, and only after about 340,000 outputs anything that looks random. Every linear generator has such a zeroland around the all-zero state; xorshift128 crosses it in 37 outputs, WELL512 in 44, and the twister's three-word twist makes it the slowest of all by four orders of magnitude.
A ring of clocks settles into a twist
Put identical oscillators round a ring, each pulled only by its neighbours, and start them at random. They always lock — every one ends at the same frequency — but most of the time not in step: the angles wind round the ring a whole number of times and stay wound. The winding number a random start chooses is spread like a bell whose width grows like the square root of the ring, and only coupling to about a third of the ring makes full synchrony certain.
Resolving one letter away at a time
Davis and Putnam's procedure of 1960 decides a set of clauses by removing its letters one at a time, replacing every clause that mentions a letter by all the ways of resolving it away. On a cycle the clauses never multiply; on a grid they swell by a factor of three and a half for each extra row, and on the 4 × 4 grid each extra unit of the order's width doubles the peak exactly. The cost is not the size of the formula but how wide it is.
The zero of a sandpile
Pile grains of sand on a grid, and whenever a cell holds four, let it topple and pass one grain to each neighbour. The order in which cells topple turns out not to matter, and the piles that keep recurring when sand is dropped at random form a group — one whose size is the number of spanning trees of the grid. Its zero is not the empty grid but a fractal picture of nested squares, and sand dropped on a single cell spreads into a round pile with the same kind of pattern inside.
The order that keeps elimination narrow
Eliminating letters one at a time costs whatever the widest step costs, and the least width any order can achieve is the treewidth of the formula's graph. Finding it exactly is NP-hard, but a search over sets of letters instead of sequences finds it for small graphs, and a greedy rule that adds the fewest new edges finds it on 566 of 600 random graphs and misses by more than one only once. On Tseitin's 6 × 6 grid that rule forms twenty-four times fewer resolvents than sweeping row by row. What it cannot do is prove that its order is the best.
Two losing games that win together
Game A is a coin that wins 49.5% of the time. Game B tosses a bad coin when the capital is a multiple of three and a good one otherwise, and it loses too, because the capital spends more than a third of its time on multiples of three. Choose between the two games at random and the walk drifts upwards by 0.0157 a round; play A, B, B over and over and it gains 0.0574. Nothing is wrong with the arithmetic. The losing coin A wins by knocking the capital off the bad remainder.
A cluster grown by random walkers
Release a particle far away, let it wander until it touches a growing cluster, and freeze it there. Twenty thousand particles later the cluster is a branching tree whose mass grows like the radius to the power 1.7. Every simulation agrees on the number; the only theorem says it is at least 1.5.
An ant that builds a highway
Two rules: on a white cell turn right, on a black cell turn left, and flip the colour as you leave. From an empty grid the ant wanders for 9,975 steps without visible order, then falls into a cycle of 104 steps that carries it diagonally for ever. That it always escapes to infinity is proved; that it always ends on a highway is not.
The ash a random soup leaves
Fill a grid at random, apply Conway's rule — three neighbours give birth, two or three keep a cell alive — and the population collapses from half the cells to about three in a hundred, leaving scattered blocks and blinkers. Five cells in the shape of an R take 1,103 generations to do the same and peak at 319 on the way. The Game of Life is a universal computer, so nothing short of running it can say when a pattern will settle, and the figures run it.
Doubling without an attractor
Feigenbaum's 4.669 holds for every map that folds and loses area. A map that keeps area — a frictionless pendulum sampled once a swing — has no attractors at all, yet its periodic orbits double just the same: a period-1 orbit at a = 3, period 2 at a = 4, then 4.1205, 4.1344, 4.1360 and on. The intervals shrink by 8.721 each time, not 4.669, and the orbits by 4.018, not 2.503. Let the map leak a little area and the cascade starts with one constant and finishes with the other.
How high an orbit climbs
The Collatz orbit of 27 climbs to 9,232 before it falls, and below ten million the champion, 6,631,675, climbs to sixty trillion — almost exactly the square of where it started. That is not a coincidence of the two numbers but a law of the whole family: an orbit climbs to x times its start with a chance of about one in x, and the exponent is one because half of three-halves plus half of a half is exactly one. Among N starts the luckiest climbs about N-fold, and so the records grow like the square of the start.
The entropy in a single orbit
Topological entropy measures how fast all the orbits of a map come apart, which sounds like a property of every orbit at once. For a map with one fold it is decided by just one: the orbit of the turning point. Read that orbit as a string of signs, make a power series of it, and the entropy is minus the logarithm of the series' first zero — ln 2 at the top of the logistic family, ln φ in the window of three, and nought where the signs become the Thue–Morse sequence.
Running a computation backwards with little memory
The reverse sweep that gives a whole gradient for the price of a few evaluations needs the computation's intermediate states in reverse order, and storing them all can cost more memory than the machine has. Keep only a few and recompute the rest, and the cheapest schedule has an exact answer found by Andreas Griewank in 1992: with c stored states and no step run more than r times, the longest chain that can be reversed is the binomial coefficient C(c + r, c). Pascal's triangle is the table of what memory buys.
The silver mean at the flat point
At the golden-mean rotation number, the circle map with a flat point has two universal constants, 2.8336 and 1.2886. Repeat the measurement at the silver mean, √2 − 1, and two different numbers appear — 6.7992 and 1.5868 — shared by every map with the same kind of flat point. Below the critical line the silver gaps shrink by (1 + √2)², the square of the silver ratio, exactly as a rigid rotation predicts; on it they do not. Every rotation number with a repeating continued fraction carries its own pair, and a number whose expansion ends in ones inherits the golden pair, whatever came first.