Order out of noise — page 6
Which way a prime's two squares point
A prime one more than a multiple of four is a sum of two squares in exactly one way, and the two squares make a point on a circle. Draw that point for every such prime and ask which way it faces. It faces every way equally — the angles spread evenly over the sector, which Hecke proved by giving each angle a remainder and copying Dirichlet. Measured over seventy-four thousand primes, they are even more evenly spread than random angles would be.
Every loop of the butterfly links every other
The Lorenz equations have infinitely many periodic orbits, each a closed loop winding round the two lobes in its own order. Name each loop by that order — LR, LLR, LLRLR — and the linking number of any two can be read off the names, without solving anything: it is half the number of times a left-going strand passes a right-going one. Every such crossing has the same sign, so every pair of loops links, positively. Computing forty-five pairs from the equations themselves, the Gauss integral lands on the predicted whole number every time.
Two random shuffles reach every shuffle
Pick two ways of rearranging n letters at random and allow them to be repeated in any order. Almost always the two together reach every rearrangement there is, or every even one — and when they fail, the usual reason is a coincidence about a single letter that both happen to leave alone. Eugen Netto guessed it in 1882 and John Dixon proved it in 1969.
A market too large to bargain in
Two traders swapping goods can settle anywhere along a stretch of possible deals; nothing forces a price. Bring in a second pair of the same traders and some of those deals can be refused by a group of three. With thirty of each, the only deals no group can refuse lie within a few thousandths of the one a price would produce. Edgeworth guessed in 1881 that competition shrinks bargaining to prices; Debreu and Scarf proved it, and the shrinking can be computed.
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.
The same bell on thinner sets
A typical whole number has about log log N prime factors, spread in a bell curve. That was a theorem about all numbers, built on the picture of each prime dividing independently. The numbers one less than a prime, and the numbers n² + 1, are far too thin for that picture to have any obvious claim on them, and on both the same bell appears — with means shifted by constants that come straight from how often each small prime divides them. The squares plus one that are prime, the case of a single factor, number 102,205 up to n = two million against 102,302 predicted; whether there are infinitely many is open.
Sectors that shrink with the primes
Hecke proved that the angles of the primes a² + b² are evenly spread, so every fixed sector eventually gets its share. Let the sector shrink as the primes grow, to width X^(−α), and the question is open beyond small α. Measured on the 581,517 such primes between twenty and forty million, wide shrinking sectors fluctuate far less than chance and thin ones as much as chance — and the thin sectors that go empty are not scattered: they gather beside the directions of small rational slope, most of all slopes like 1/3 and 1/1 whose two terms are both odd.
The longest run has no limit
Toss a fair coin n times and the longest run of heads is about log₂ n. The average settles: it is log₂ n − 0.667 to within a few millionths by a million tosses. The distribution does not. Because the run is a whole number and log₂ n is not, the chance of each value swings round the same cycle once every doubling of n, for ever, and computing it exactly to a million tosses shows the swing as large at the end as at the start.
The pieces no formula counts
A random vibration of a large membrane splits the surface into regions where it bulges up and regions where it dips down. Pieces minus holes has an exact average; the number of pieces has none. Nazarov and Sodin proved it is proportional to the area, Bogomolny and Schmit predicted the constant from percolation, 0.0624, and counting the pieces of 51 random waves gives 0.0599 — below the prediction by several standard errors. The sizes of the pieces follow percolation's law; their number does not.
A third of random games have no pure equilibrium
Fill a game's payoff table with random numbers and ask whether some cell is each player's best reply to the other. Exactly one cell is expected to be, at every size, and the chance that none is climbs from one in eight to 1/e — the same constant that counts the shuffles in which nobody gets their own hat back, and for the same reason.
A grid of bits whose rank stops at the state
Fill a square grid with a generator's output bits and compute its rank over the field of two elements. Random bits give full rank or one short, in fixed proportions. A generator built from shifts and exclusive-ors gives full rank up to its number of state bits and then never one more — 32 for a 32-bit xorshift, 128 for the lowest bit of xorshift128+ — however large the grid. The test that catches it is decided by a line of linear algebra.
Edges that crowd each other out
Pick a spanning tree of a graph uniformly at random, and the presence of one edge makes every other edge less likely — a theorem of Kirchhoff's electricity. Pick a forest instead, or a connected subgraph, and the same is believed and unproved. Checking every pair of edges in every labelled graph up to six vertices, 871,926 pairs for forests alone, finds no exception, and comes as close as 0.9994 to one.
The longest thread between two random strings
Write down two random strings of a thousand bits each and find the longest sequence that can be read in both, skipping freely. It is about 81% of each, and the exact share — the Chvátal–Sankoff constant — has resisted computation for fifty years. Its fluctuations are a smaller mystery with a sharper edge: the variance is known to be at most n/2, and over every length that can be computed it grows like n to the power 0.7, with nobody able to say what it does after that.
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.
Where a random walk leaves the snowflake
Start a random walk at the centre of the Koch snowflake and record where it first touches the edge. The edge has dimension 1.26, but the places the walks arrive form a set of dimension one: 60,000 walks spread their entropy by ln 3 a level, not ln 4, and the busiest fifth of the edge takes nine tenths of them. Makarov proved in 1985 that it must be so for every simply connected region in the plane.
One, plus a quarter, plus a ninth
Give n workers n jobs with every cost drawn at random, average one, and find the cheapest way to pair them. However large n is, the cheapest total averages less than π²/6, and for every n it is exactly 1 + 1/4 + 1/9 + … + 1/n². Parisi guessed the formula in 1998 from n = 1, 2 and 3; thirteen sizes of random tables, solved exactly, land on it within sampling error.
Half the chance for every silent set
In the lights game where a press toggles only the neighbours, a random network can be lit about 56 times in a hundred when it has an even number of vertices and 44 when odd. The numbers are 0.560562 and 0.439438, they add to one, and they come from a chain: each new vertex raises or lowers the dimension of the silent sets by one, and each dimension halves the chance.
A long enough chain never locks
Line oscillators with different natural rhythms up in a row and let each feel only its two neighbours. The chain locks into one frequency exactly when the coupling exceeds the largest running total of their frequency differences — a random walk tied down at both ends — so the coupling needed grows like √N, and its law is Kolmogorov's, the same distribution that tests whether a sample fits a curve.
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.
The shape of a cell around a random point
Scatter points at random and give each the region nearer to it than to any other. The cells come in every shape from triangles to twelve-sided polygons, and almost nothing about them is fixed by a formula — except one thing: on a closed surface they have exactly six sides on average, every time, because three cells meet at every corner. Two hundred thousand cells measure the rest: 29.5 per cent hexagons, Lewis's law, and small cells surrounded by large ones.
A walk on Gaussian primes stopped by a moat
Start at 1 + i and step from Gaussian prime to Gaussian prime, never more than 2 at a time: the walk reaches 720 primes and stops at 17 + 42i, surrounded by a moat. Allow steps of √10 and it reaches a quarter of a million primes before stopping at distance 1,024; steps of 4 carry it to 4,313. Whether some fixed step lets a walker reach infinity is a question Basil Gordon asked in 1962, and it is open.
The largest prime in a typical number
Count a number's prime factors and the answer is about log log n. Ask instead how big the largest one is, and the answer is a power of n with a law of its own: half of all large numbers have a prime factor above n^0.6065, and the share whose primes all stay below n^(1/u) is Dickman's ρ(u), a function defined by its own past. The same law governs the longest cycle of a random shuffle, and there it arrives at once; for the numbers themselves, at ten million, it is still visibly on its way.
How many new kinds the next sample will show
Count how many kinds were seen once, twice, three times. Good and Toulmin's alternating sum f₁t − f₂t² + f₃t³ − … then predicts, with no bias at all, how many new kinds a further sample t times as large will reveal. It works perfectly up to t = 1 and is worthless just beyond: past that point the kinds seen most often are multiplied by t to a high power, and the spread of the estimate passes 10⁴⁰ by t = 1.5. Truncating the sum at a random point rescues it, and each fourfold increase in the first sample buys about half a unit more of future.
How a random path winds round a point
A path in the plane with one point removed has a class in the punctured plane's fundamental group: how many times it has wound round the point. For a random path the class grows like the logarithm of time, and its spread has a law. Brownian motion follows Spitzer's Cauchy law, so heavy-tailed that the mean winding does not exist; a walk on a grid follows the hyperbolic secant law instead, with tails that fall exponentially. The difference is made entirely by close passes, which a grid forbids. With two points removed the class becomes a word, and some loops wind round neither point and still cannot be shrunk.