Order out of noise — page 5
Algebra
The shape a random ball grows into
Give every road of the square grid a random travel time and ask what can be reached from one point in time t. The region is ragged, and rescaled it converges to a fixed convex shape — but which shape is unknown for every natural law. Computing it shows a curve within a few per cent of a circle for continuous travel times, a flat side where fast roads percolate along a diagonal, a time per step that is still drifting at a hundred and twenty-eight steps, and fluctuations that grow like the distance to the power one third rather than one half.
Discrete
Coins hidden in the roots
The polynomial that counts permutations by their descents has no product formula, and nothing in the definition of a descent is a coin toss. But every root of the polynomial is real and negative, and a polynomial like that is a product of coins in disguise: each root r is a coin landing heads with chance 1/(1 − r). The descent count of a random permutation is exactly a sum of independent coins nobody can point to — which is why it is bell-shaped, and why its coefficients obey inequalities the inversion count breaks.
Discrete
The longest wait for a prime
Near a number x the primes are on average log x apart, and the longest stretch without one below x is much longer: about the square of log x, if the primes behave like random numbers with the right density. Sieving to thirty million finds twenty-four record gaps, all climbing in the shape of that square and all below it. A random model of the primes gets the scale right and the details wrong, and the correction for what it gets wrong predicts gaps larger still — larger than any anyone has found.
Dynamics
A growth rate no step contains
Start with 1, 1 and at every step either add the last two numbers or subtract them, choosing by a coin. The sequence wanders, shrinks, even returns near zero — and grows, almost surely, like 1.13198824 to the power of the step. That number is a Lyapunov exponent of a product of random matrices, and it cannot be found by averaging anything about a single step: the two steps do not commute, and the rate depends on which way the vector is pointing when each one is applied.
Dynamics
Fractions repeat and roots look random
Almost every number between 0 and 1 has base-φ digits with the frequencies Parry's measure predicts. Which particular numbers do? Every fraction, provably, does not: its expansion repeats from the first digit, with a period equal to the period of the Fibonacci numbers modulo its denominator. And √2 − 1 and 1/π, computed exactly to twelve thousand digits, match every predicted frequency to within sampling error — which proves nothing about them at all.
Logic
The squares that answer every request
Rado's graph has, for any finite sets U and V, a vertex joined to all of U and none of V. A finite graph can only answer the small requests, and the Paley graphs — residues modulo a prime, joined when their difference is a square — are the classic way to build one. Checking every request exactly finds the thresholds: 13 residues answer every request of two, 29 every request of three, 89 every request of four. The theorem that guarantees it asks for 64, 576 and 4,096. Coin-toss graphs of the same sizes almost never manage it.
Number
Class groups drawn at random
The class number of an imaginary quadratic field measures how badly unique factorisation fails there, and it looks arbitrary: 1, 2, 4, 3, 5, 12, 1. Count how often 3 divides it and the answer is not one time in three but noticeably more — heading, by a conjecture of Cohen and Lenstra, for 44 per cent. The reason is that class groups behave like finite groups chosen at random with each group weighted by one over its number of symmetries, so groups with few symmetries, like the cyclic group of order 3, turn up more often than the naive count suggests.