Open problem
Named by 15 essays across 8 fields — each of them below, with the objects they name alongside it.
The question nobody can answer
Halve it if it is even, triple it and add one if it is odd. Every number anyone has tried comes down to one. Nobody can prove they all do, and the reason is not that the problem is hard to state.
Which infinitudes are proved
The primes never stop, and neither — apparently — do the twin pairs, the primes one more than a square, or the Mersenne primes. Three of those four statements are theorems and one is not, and counting the members of each family tells nobody which.
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 same question in space
Intersect four balls at the corners of a tetrahedron and the result is not of constant width — it misses by two and a half per cent, computed exactly. Repairing it gives a body that is, and whether that body is the smallest of its kind has been open for a century.
The sieve that cannot finish
Sifting out the composites is the oldest method in the subject and it has a ceiling nobody has raised. The reciprocals of the twin primes add to a finite number, so no argument that measures thickness can reach them — and the inclusion–exclusion every sieve truncates goes wildly wrong before it goes right.
The sum of the parts, taken again
Replace a number by the sum of its proper divisors and do it again. Most numbers fall to 1, a few land on a perfect number or a cycle, and some climb for hundreds of steps. Below a thousand there are twelve whose fate nobody knows — and the thing that keeps them climbing is a perfect number hiding in their factorisation.
A walk that may not step where it has been
Forbid a walk on the square grid from ever revisiting a site and the number of possible n-step walks grows like 2.638ⁿ instead of 4ⁿ — a number nobody can write down exactly. On the honeycomb it is exactly √(2 + √2), proved in 2010. And the walks spread out like n to the three-quarters, faster than any ordinary walk, which physicists have used since 1949 and mathematicians still cannot prove.
The area of the Mandelbrot set, from two sides
The Mandelbrot set has an area, and nobody knows it. Counting grid cells closes in on 1.5066 from both sides, but every count judges a cell by a single point, and points on the boundary never declare themselves. An exact formula exists — π times one minus a sum over the coefficients of the map onto the set's outside — and every partial sum is a guaranteed upper bound; after sixteen thousand coefficients the bound is still 1.786, and at the rate it falls it would need something like 10²⁵ more.
A third kind of member
Two sides always have a stable matching, and the proof is a procedure. Add a third kind of member — capitals who rank numbers, numbers who rank letters, letters who rank capitals — and every market small enough to check still has a stable grouping. Ten million markets of three have at least ten each. Nobody can prove it continues, because the structure the two-sided proof stands on is gone.
Abundant, and still not a sum of its parts
Seventy's proper divisors add to seventy-four, more than seventy itself — and yet no selection of them adds to exactly seventy. The reason is that the excess, four, cannot be made from the small divisors one, two and five. Numbers like seventy are called weird; there are thirty-six below twenty thousand, every one of them even, and nobody knows whether an odd one exists.
Euclid's proof run as a machine
Euclid proved there is no last prime by multiplying the primes on any list, adding one, and noting that the result has a prime factor not on the list. Run the proof as a machine — start from 2, and each time take the smallest prime factor of one more than the product so far — and it produces 2, 3, 7, 43, 13, 53, 5, 6221671, … a sequence that never repeats, that reaches small primes late and large ones early, and that nobody can prove reaches every prime.
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.
When Euclid's number is itself prime
Multiply the primes up to p and add one. Euclid needed only that the result has a prime factor beyond p; it is itself prime for p = 2, 3, 5, 7 and 11, and then not again until 31, and then not until 379. Up to 1,100 there are nine such primes of each sign, against thirteen that a careful estimate expects. The estimate predicts infinitely many and grows by about 1.8 every time x is multiplied by e; nobody can prove there is even one more.
The numbers that fool every base
561 = 3 · 11 · 17 passes Fermat's test for every base it shares no factor with, and so do 1,105, 1,729 and 102 more numbers below ten million. They were proved infinite only in 1994. Counted to 10²¹ there are about twenty million, growing like x to a power that has crept from 0.21 to 0.35 — just past the bound the proofs guarantee and nowhere near the power of one that Erdős's argument predicts.
What a formula keeps when letters are fixed
Fix half the letters of a formula at random and most of its leaves become irrelevant: on the sixteen-leaf formula for the parity of four letters, two fixings leave four. How fast formulas shrink under random fixings is the whole engine behind the best lower bounds anyone has proved for formula size — Subbotovskaya's 3/2 in 1961, Håstad's 2 in 1998 — and the reason that engine stops at n³.
Named alongside it
The objects these essays reach for when they reach for this one.
Exhaustive searchHeuristicConjectureParityPrimesAbundanceConvergence rateCounterexampleDivisor sumIterationLatticeOrbit