Matpic
mathematics, in pictures
Concept

Recurrence

The return of a system arbitrarily close to a state it has already been in. For a fair walk on the line it happens with certainty, and in three dimensions it does not, which is a fact about dimension rather than about walks.

Named by 14 essays across 7 fields — each of them below, with the objects they name alongside it.

Nine walks, and the square root. 9 independent walks of 400 steps, each step one place left or right. The dashed curves are ±√n: the walks stay near them, spill past them, and come back — which is what a typical distance means as opposed to a limit.

A walk that always comes home, until it does not

Step left or right at random, forever, and the walk returns to where it started with certainty. On a grid it also returns. In space it does not, and about a third of walks leave and never come back.

probability · Random walk Rotating by √2 − 1 of a turn, 40 times. Points on a circle produced by repeatedly turning through the same 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.

dynamics · Pigeonhole All 24 arrangements of 4 objects, and the 9 that move every one. Every permutation of 4 objects drawn as a grid of cells, with the diagonal — where an object stays where it began — shaded, and the arrangements that avoid it entirely marked.

Nobody gets their own hat

Hand back a pile of hats at random and ask for the chance that not one person gets their own. The answer barely moves as the crowd grows — it is a third and a bit at four people, and a third and a bit at four thousand.

probability · Inclusion exclusion Waiting for all 6 kinds. One bar per new kind: the expected number of draws needed to see a kind not yet seen, rising as fewer of them are left, and adding to 14.70 draws in total.

How long until every one turns up

Draw at random from six equally likely kinds until all six have appeared. The wait is not six draws, and it is not sixty; it is fourteen point seven, and the number is a harmonic sum wearing a hat.

probability · Expectation The tree of Pythagorean triples. A tree rooted at 3-4-5. Each triple has three children, obtained by three fixed integer matrices, and every primitive triple appears exactly once somewhere in it.

A tree that holds every triple

Three fixed matrices, applied to 3-4-5 over and over, produce every primitive Pythagorean triple there is — each of them once, none of them twice, and with no test for common factors anywhere in the procedure.

number · Pythagoras 256 consecutive pairs from xₙ₊₁ = 137xₙ + 187 mod 256. Consecutive outputs of a linear congruential generator plotted as points of a square, falling on a small family of evenly spaced parallel lines.

The planes a recurrence cannot leave

One multiplication and one addition, taken modulo a fixed number, produce a sequence that passes for random one value at a time. Taken two or three at a time it does not, and the reason is a whole-number relation that pins every point onto one of a small family of parallel lines.

computation · Pseudorandomness A 4-bit register that visits all 15 nonzero states. The first 15 states of a 4-bit linear feedback shift register with taps at 4 and 1, with the bit that leaves the register at each step; the output shows every nonzero window of 4 bits exactly once.

A memory of four bits

A register holding four bits, shifting them along and adding two of them back, runs through all fifteen nonzero states before it repeats. Which two are added back is a question about a polynomial, and getting it wrong costs fourteen of the fifteen.

computation · De bruijn One walk on the whole numbers, three chances, three different fates. The relative weight of each state for three step-up chances, drawn as bars, with the running total of those weights and what each case means beneath.

Where the shares have nowhere to go

On finitely many states, a chain that can reach everywhere and is not forced into a rhythm settles down. Give it infinitely many and both conditions can hold while the walk leaves and never returns — or returns with certainty and takes an unbounded average time about it.

probability · Markov chains Permutations of n things, by how many pairs they put in the wrong order. A table whose row n and column k hold the number of permutations of size n whose inversions is k, with each row's total beside it — the plain count the one-variable series gives.

The coefficient that is a polynomial

Add a second variable to track a statistic and each coefficient stops being a number. Set the new variable to one and the old count comes back untouched; leave it in and the mean of the statistic is a derivative rather than an average.

discrete · Generating functions How long 4 equally likely patterns take to appear. A bar for each of 4 patterns of 3 coin tosses giving the expected number of tosses before it first appears, with the lengths at which each pattern overlaps itself listed.

Two patterns, one chance, different waits

HTH and HTT are equally likely in any given window of three tosses. Waiting for HTH takes ten tosses on average and waiting for HTT takes eight, and the difference is not about probability at all — it is about what a failed attempt leaves behind.

probability · Expectation Integration by parts is a rectangle. The increasing curve v = u²/4 between u = 1 and u = 3. The region under it is shaded one way and the region between it and the vertical axis another; together they fill the rectangle from the origin to (3, 2.25) minus the rectangle to (1, 0.25).

A rectangle cut by a curve

Integration by parts is taught as the product rule run backwards. It is also a picture: an increasing curve cuts a rectangle into two pieces, one of them the area under the curve and the other the area beside it, and the formula says only that the pieces fill the rectangle. Run repeatedly, the same cut produces the factorials and Wallis's product for π.

analysis · The integral The continued fraction of e. Bars for the first 30 continued-fraction terms of e: mostly ones, with every third bar rising in a straight staircase, 2, 1, 2, 1, 1, 4, 1, 1, 6, ….

The pattern in e's continued fraction

Written as a continued fraction, e is 2; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8 — two ones, then the next even number, for ever. Euler found the pattern and proved it with a differential equation. A proof from 2006 needs only three integrals, each of which turns out to be exactly the error of one of e's own convergents.

number · Irrationality Every way to pair the edges of a hexagon. Chord diagrams of all 15 pairings of a 6-gon's edges, shaded by the surface each gluing makes: 5 spheres, 10 tori.

Every way to pair a polygon's edges

A hexagon's six edges can be paired in fifteen ways. Glue each pair head to tail and five of the fifteen give a sphere and ten give a torus; an octagon's 105 pairings give 14 spheres, 70 tori and 21 surfaces with two handles. The spheres are exactly the pairings whose chords never cross, and the whole table obeys one recurrence found in 1986.

topology · Surface classification The ground a 1,500-step walk covers. A random walk on a square grid drawn as a path, with every grid square it visited shaded and its start and end marked.

The ground a walk covers

A random walk of a thousand steps visits far fewer than a thousand places: in one dimension about fifty, in the plane about four hundred, in space about six hundred and sixty. The share of steps that land on new ground is exactly the chance of never coming home — so the number that decides whether a walker returns also decides how much of the world it sees.

probability · Random walk

Named alongside it

The objects these essays reach for when they reach for this one.

ExpectationPermutationRandom walkSample spaceApproximationCatalan numbersCounting argumentCounting two wayse, the numberIntegralLimitLinearity

All concepts