Theme

Small rules, large behaviour — page 3

Rules short enough to write on one line, producing behaviour nobody can summarise — and the finding that the size of a rule predicts nothing about the difficulty of the questions it raises.
Two chaotic maps, coupled weakly and strongly. The gap between two coupled copies of the logistic map at full chaos: at ε = 0.15 it stays large; at ε = 0.3 it falls to nothing. Dynamics

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.

Where the free critical point goes, for every cubic in a family. The parameter plane of the cubics (z − 1)(z² + z + a) from −2 to 3 across and −2.5i to 2.5i up, coloured by the root Newton's method takes 0 to, with small dark regions where 0 is trapped in a cycle. Dynamics

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.

A random tiling of the Aztec diamond, frozen outside a circle. A uniformly random domino tiling of the order-40 Aztec diamond (1640 dominoes) with the inscribed circle drawn. Discrete

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.

Three cascades, a sharp top, a round top and a flat top. z = 1.25: δ ≈ 3.2596; z = 2: δ ≈ 4.6692; z = 6: δ ≈ 9.2963. Dynamics

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.

Raising the input's type, and what becomes computable. N[o]: 299 functions, 0 not extended polynomials; N[o → o]: 163 functions, 42 not extended polynomials; N[(o → o) → o]: 128 functions, 46 not extended polynomials; N[o → o → o]: 72 functions, 33 not extended polynomials. Logic

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: one board lit, one proved impossible. 4 by 4: solved with 10 presses; 5 by 5: unsolvable, witness set of 5 lights each seeing an even number of the set. Computation

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.

Oscillators scattered below the threshold and gathered above it. N = 240, Lorentzian width 0.5: K = 0.5 gives r = 0.068; K = 2.5 gives r = 0.775. Dynamics

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.

Billiards in an ellipse: every path keeps touching one confocal conic. Two billiard trajectories in the ellipse x² + y²/0.49 = 1, one tangent to a confocal ellipse and one to a confocal hyperbola. Geometry

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.

Every fraction has a bulb. The cardioid with 277 computed bulbs of period 2 to 30; the bulbs of period up to five labelled 1/2, 1/3, 2/3, 1/4, 3/4, 1/5, 2/5, 3/5, 4/5. Algebra

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.

Fictitious play that never settles. Shapley's 3 × 3 game, 34 runs in 2,000,000 rounds; final mixtures row 0.371, 0.456, 0.173, column 0.253, 0.544, 0.203. Applied

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.

Four generators climbing out of zeroland. Output ones-density from a one-bit start reaches 0.45 after: MT19937 374000, TT800 4500, WELL512 44, xorshift128 37. Computation

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 identical clocks locked into a twist. Ring of 40, nearest-neighbour coupling, settled into a 2-twisted state; largest deviation 2.6e-11; order parameter 2.5e-16. Dynamics

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.

Eliminating a letter by resolving it away. Tseitin triangle: 6 clauses; eliminating x: 4 resolvents, 2 tautologies, 4 clauses left; clause counts 6 → 4 → 2 → 1 ending with the empty clause. Logic

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. Identity of the sandpile group on 128×128: cells with 0,1,2,3 grains: 1664, 568, 5368, 8784; checked by adding it to the all-3 pile. Dynamics

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.

An elimination order is a tree of bags. 3 × 3 grid, optimal order a, c, g, i, b, d, f, h, e; bags abd, bcf, dgh, fhi, bdef, defh, efh, eh, e; treewidth 3. Logic

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. A alone: -3.000 after 300; B alone: -3.131 after 300; A or B at random: 4.428 after 300; A A B B repeated: 4.322 after 300. Probability

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. Diffusion-limited aggregation, 20000 particles, radius 303.0; particles coloured by arrival in fifths. Dynamics

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.

Ten thousand steps of disorder, then a highway. Langton's ant from an empty grid: highway from step 9976, moving (-2, -2) every 104 steps; position after 12000 steps (-56, -32). Dynamics

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.

Five cells that take 1,103 generations to settle. R-pentomino: population 5 → 319 max (generation 821) → 116 from generation 1103; 80 cells within 60 of the centre at 1103. Dynamics

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.

Period doubling with nothing attracting. doubling parameters 3.0000000000, 4.0000000000, 4.1204524973, 4.1343639125, 4.1359600588, 4.1361430974, 4.1361640856. Dynamics

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. 1:1 2:2 3:16 7:52 15:160 27:9232 255:13120 447:39364 639:41524 703:250504 1819:1276936 4255:6810136 4591:8153620 9663:27114424 20895:50143264 26623:106358020 31911:121012864 60975:593279152 77671:1570824736 113383:2482111348 138367:2798323360 159487:17202377752 270271:24648077896 665215:52483285312 704511:56991483520 1042431:90239155648 1212415:139646736808 1441407:151629574372 1875711:155904349696 1988859:156914378224 2643183:190459818484 2684647:352617812944 3041127:622717901620 3873535:858555169576 4637979:1318802294932 5656191:2412493616608 6416623:4799996945368 6631675:60342610919632 Dynamics

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 of a map, read off one orbit. r=3.7: itinerary RLRRRRRRLRRRRRRLRRRLRRRRRRLRLRRRRRRLRRRR; t0=0.6826882822002793; h=0.38171692. Dynamics

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.

The cost of running a computation backwards with a few stored states. Minimal recomputation to reverse chains of length up to 200 with 1, 2, 3, 4, 6 slots; at length 200: 1: 19900, 2: 2470, 3: 1305, 4: 948, 6: 680. Analysis

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 parameters close in, on and below the critical line. Superstable parameters of the circle map for convergents of the silver mean: limit at K=1 0.41886498636462, gap ratio -6.79916; at K=0.5 0.41642638493704, gap ratio -5.82844. Dynamics

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.

All themes