Asymptotics
Named by 14 essays across 6 fields — each of them below, with the objects they name alongside it.
Nine thousand four hundred and eight
There are four Latin squares of order four once the first row and column are fixed, fifty-six of order five, and nine thousand four hundred and eight of order six. The exact answer is known for eleven orders and for no more — and yet a half-finished square can always be finished.
The size of a number with no formula
There is no closed expression for the number of partitions of n. There is an expression for how large it is — with a square root in the exponent and a π in front — and it is accurate enough that rounding a few terms of its refinement gives the exact count.
The equation a sequence satisfies
Write the whole sequence as the coefficients of one series, and the recursion becomes an equation with a square in it. Solving the equation by the ordinary quadratic formula produces the closed form, the growth rate and the correction term, none of which the recursion offers.
The dots a circle catches
Pick's theorem gives a lattice polygon's area exactly, with no error term anywhere. Ask a circle the same question and the exactness is gone: the count is the area plus something, the something has been measured for two centuries, and nobody knows how big it is.
The shape a random partition takes
There are about twenty-four thousand billion billion billion ways to write 1,000 as a sum of whole numbers. Pick one at random, draw its Ferrers diagram, shrink it by the square root of a thousand, and it is almost exactly the curve e^(−cx) + e^(−cy) = 1 with c = π/√6. So is the next one, and the next. A random partition of a large number has a shape, and the shape is known exactly.
Divisors that make every amount
Twelve's divisors — 1, 2, 3, 4, 6, 12 — can be chosen to add to every whole number from one to twenty-eight. Numbers like that are called practical, a test on their primes decides them, and they turn out to be counted like the primes: about 1.336 x / log x of them below x. For practical numbers Goldbach's conjecture and the twin conjecture are theorems.
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.
A partition piled into a corner
A partition is a row of numbers that never increases. Let it never increase down the columns too, and it becomes a pile of cubes pushed into the corner of a room. MacMahon counted the piles with one change to Euler's product — each part size k in k colours — and in a box with a product over its cells. The second direction moves the growth from e^(√n) to e^(n^(2/3)), puts ζ(3) where π was, and makes a count that grows with a box's area. One direction further, his guess fails at six.
Which knots a random loop ties
Long random loops are almost always knotted, but knotted as what? Sorting 14,000 closed random polygons by two values of the Alexander polynomial answers it. The trefoil leads at every length, five times as common as the figure-eight at 400 sticks. Each knot's share, divided by the unknotted share, grows like a power of the length, and the trefoil tied twice grows about twice as fast as the trefoil — what a loop carrying independent small tangles would do. Up to 300 sticks the double trefoil turns up exactly as often as two independent trefoils should.
The corners of a random hull
Drop ten thousand points at random into a triangle and stretch a band round them: about twenty points touch it. Drop them into a disc and about seventy-three do. The count grows like a logarithm in one shape and like a cube root in the other, and the reason is where the boundary bends.
The dots a ball catches
Count the lattice points inside a ball and compare with its volume. In five dimensions the error is about the size of one spherical shell, and that is a theorem; in four a logarithm sneaks in; in three and two the true size of the error is unknown. The difficulty runs backwards because the arithmetic of sums of squares is most erratic when there are fewest squares to add.
Triangle-free, and two-sided eventually
Every graph with no triangle and the most edges possible is bipartite. Erdős, Kleitman and Rothschild proved that almost every triangle-free graph is bipartite too — and yet among the 246,348,115 triangle-free graphs on nine labelled vertices, fewer than half are. The share falls before it rises, and the reason is that small graphs are sparse.
Truth tables up to renaming
There are 256 truth functions of three letters, but many differ only in which letter is called what, or whether a letter or the answer is negated. Counted up to such renamings there are fourteen. For four letters there are 222, for five 616,126 — and almost every function of many letters is changed by every renaming, so the count settles into a simple division.
How many shapes a tree can take
There are 262,144 labelled trees on eight points and only twenty-three shapes. Labels make counting easy — Cayley's nⁿ⁻² — and shapes make it hard, because a symmetric shape absorbs labellings. The count of shapes comes instead from a recurrence for trees with a root and a theorem of Richard Otter's for taking the root away: in every tree there is exactly one more class of points than of edges. Run to two hundred points, the counts grow like 0.535 × 2.9558ⁿ ÷ n^(5/2), and the same arithmetic counts the alkanes.
Named alongside it
The objects these essays reach for when they reach for this one.
Exhaustive searchGenerating functionPartitionBijectionBurnside lemmaCountingDivisor functionError termPermutationPiSymmetryAlexander polynomial