The primes on a spiral, and a pattern nobody ordered

The story is that Stanisław Ulam was bored in a meeting in 1963. He began doodling the whole numbers in a square spiral on a scrap of paper, then circled the primes.

There is nothing special about the spiral. It is not a construction with a theory behind it, in the way that winding a circle out into a wave is. It is simply a way of laying the integers out on a grid so that consecutive numbers are adjacent, and it is the layout most people would produce if asked to do that on squared paper.

Now do it for nine hundred numbers and drop the labels.

That is not what the primes are supposed to look like. Primes are the standard example of a sequence with no pattern — irregularly spaced, thinning out slowly, resistant to formula. Scattered points arranged at random do not fall on diagonals.

Ulam and his colleagues ran the same computation on a MANIAC II at Los Alamos out to 65,000 and the effect only became clearer. That machine was there for the Monte Carlo work; the spiral was a side effect of having it.

Half of the explanation is easy #

Some of what is visible has an immediate cause, and it is worth clearing away first.

Look at the horizontal and vertical lines through the centre: they are almost empty. That is because half of all integers are even, and the spiral’s geometry puts long runs of alternating parity along the axes. Any line through the grid on which every entry is even can contain at most one prime, namely 2.

More generally, walking along any straight line in the spiral steps through numbers with a constant second difference — the same signature that makes odd numbers the differences of squares —, which means the values on that line are given by a quadratic polynomial in the step number. The diagonals, in particular, produce polynomials of the form $4n^2 + bn + c$.

So a diagonal line dense with primes corresponds to a quadratic polynomial that produces an unusual number of primes. The picture is not showing something new about the primes; it is showing which quadratics are prime-rich.

The most famous of these is Euler’s, found in 1772:

$$n^2 + n + 41$$

which is prime for every $n$ from 0 to 39 — forty consecutive prime values before it finally fails at $n = 40$, where it gives $41^2$. On the spiral, that polynomial is a diagonal, and it is one of the visibly darker streaks.

Why should some quadratics beat others? Partly for a reason that is easy to state: a polynomial that is always divisible by a small prime is useless, so the good ones are those that dodge divisibility by 2, 3, 5, 7 and so on for as long as possible. There are only so many residues to avoid, and a polynomial whose discriminant has the right relationship to the small primes avoids more of them. This is real, provable, and connected to deep facts about class numbers of imaginary quadratic fields. Euler’s $41$ is not a lucky number; it is the last of a very short list, and the list is short for a reason that takes an entire theory to state.

The other half is not explained #

Here is what is not settled.

Hardy and Littlewood’s Conjecture F, from 1923, gives a precise prediction of how many primes a given quadratic should produce, and the predictions match observation very well. It is a conjecture. It has not been proved.

Nor has anything much weaker. It is not known whether $n^2 + 1$ is prime infinitely often. It is not known whether any quadratic polynomial produces infinitely many primes. The diagonals in Ulam’s picture are visibly there, they have been counted, they behave as predicted — and the prediction has no proof.

There is something worth sitting with in that. A pattern is plainly visible in a picture a child could draw, has been visible for sixty years, is generated by an object studied for two and a half thousand years, and the basic quantitative statement about it remains open.

One more piece of the easy explanation, because it is often left out. The spiral’s diagonals are not all equal: a diagonal running one way steps through values of $4n^2 + bn + c$ with one parity behaviour, and the perpendicular diagonal through another. Roughly half of all diagonals consist entirely of even numbers and are therefore empty of primes above 2, which doubles the apparent contrast of the remainder. Some of the visual drama is a parity artefact of the layout rather than a fact about primes — and separating the artefact from the phenomenon is most of the work in reading any picture of this kind. A diagonal that is half empty because half its entries are even says something about the number 2, not about the primes. What is left after that subtraction is still real, still striking, and still unexplained.

How big is the effect, actually #

A pattern that is visible is not thereby large, and the spiral is a case where the eye badly overstates the size of what it has found. The honest question is how much denser a good diagonal is than an ordinary one, and it has an answer.

Hardy and Littlewood’s prediction gives each quadratic a constant of its own, and the constant says by what factor that polynomial beats a generic one of the same size. Euler’s $n^2 + n + 41$ has a constant of about $3.3$. That is the whole of the effect: the best-known prime-rich polynomial in the subject produces roughly three and a bit times as many primes as an unremarkable one, over the range anyone has drawn.

Three-and-a-bit is not nothing, and it is a long way from what the picture suggests. Streaks in a field of dots read as present or absent, because the eye is built to find edges, and a diagonal three times denser than its neighbours reads as a line drawn on a background of noise rather than as a modest excess. Meanwhile the axes really are empty — a genuine factor of infinity, from parity — so the picture contains one effect that is absolute and another that is a factor of three, drawn in the same ink and at the same weight.

That factor is quotable, and it is also checkable, which is the better way to hold a number. Take the first hundred thousand values of each polynomial, count how many are prime, and set that against what a number of the same size would give if primality were a coin flip with probability $1/\ln v$. Euler’s $n^2+n+41$ produces $31{,}985$ primes against $4{,}814$ expected — a factor of $6.64$. Then $n^2+n+17$ gives $20{,}127$, a factor of $4.18$; $n^2+n+1$ gives $10{,}751$, a factor of $2.23$; and $n^2+1$ gives $6{,}656$, a factor of $1.38$. The ordering is the expected one and the spread is real.

The $6.64$ and the $3.3$ are the same quantity counted against different baselines, and it is worth resolving rather than leaving. $n^2 + n + 41$ is $n(n+1) + 41$, and $n(n+1)$ is always even, so the polynomial is always odd. It never spends any of its luck avoiding the factor $2$ — that was free. Comparing it against all integers therefore credits it with a doubling that has nothing to do with the interesting part. Halve $6.64$ and it is $3.32$, which is the constant as it is normally quoted, measured against odd numbers of the same size.

So the honest form of the sentence above is that Euler’s polynomial is about three times better than a comparable odd number and about six and a half times denser than the integers around it. Which of the two the eye is responding to when it picks out a dark diagonal is not something the picture discloses — and half of that visible contrast is the polynomial being odd, which is the same parity artefact that empties the axes, arriving in a costume that is harder to recognise.

None of the density figures survive scale, either. All of them shrink toward each other as the numbers grow, because every quadratic eventually thins out like $1/\ln n$ just as the integers do. The ratios persist; the visible contrast does not. A spiral drawn out to a million would have the same multiplicative structure and almost nothing to look at, which is a peculiar property for a piece of evidence to have.

Forty primes in a row prove nothing #

Euler’s polynomial gives a prime for $n = 0$ through $39$ and then fails. Forty in a row is enough to convince almost anyone that something has been found, and what has been found is a polynomial that fails on its forty-first attempt.

That number is small enough to be reassuring. The genuinely unsettling examples are the ones where a pattern survives every case that could ever be checked by hand, or by machine, and is false anyway.

Pólya conjectured in 1919 that among the numbers up to any given point, at least half have an odd number of prime factors. It holds for every $n$ up to about $906$ million. It is false, and the smallest counterexample is $906{,}150{,}257$ — a number reachable now and utterly unreachable in 1919, so the conjecture stood for four decades on evidence that was entirely consistent with it and entirely worthless.

Mertens’ conjecture is worse. It survives every direct check ever made, and it is false: Odlyzko and te Riele proved so in 1985 without exhibiting a single counterexample, and the smallest one is known only to lie somewhere below $10^{40}$ or so. There is no prospect of ever seeing one. The statement is settled and the witness is permanently out of reach.

Worst is the prime-counting race. Every count anyone has performed shows $\pi(x)$ falling below $\mathrm{Li}(x)$, and Littlewood proved in 1914 that the two swap places infinitely often. The first crossing is bounded above by numbers with hundreds of digits and has never been located. The pattern holds on every case that will ever be examined, and is wrong infinitely often.

Set against those, forty consecutive primes is a very small amount of evidence. The relevant question is never how many cases have been checked; it is whether there is any reason the checked cases should resemble the unchecked ones — and for the primes, whose behaviour is governed by quantities that change only logarithmically, the cases within reach are a hopelessly biased sample of the cases.

When a picture is evidence and when it is not #

This essay sits deliberately next to Pascal’s triangle in two colours, because the two are the same kind of observation with opposite outcomes.

In both cases, a simple rule is applied to a well-known object and an unexpected pattern appears. In Pascal’s case the pattern has a complete explanation — Lucas’ theorem, two lines, no loose ends. In Ulam’s case it has a partial explanation and an unproved conjecture where the rest should be.

From the pictures alone there is no way to tell which is which. Both look equally structured; both look equally like they must have a reason. The Pascal picture happens to be explicable and the Ulam picture happens not to be, and nothing in either drawing signals the difference.

This is the honest limitation of figure-led mathematics, and it is worth stating plainly rather than working around. A picture can show that something is happening. It cannot show why, and it certainly cannot show that the why is known. The Ulam spiral has probably launched more crank manuscripts than any other single image in number theory — the same trap Kepler fell into with five solids and six planets, which is a reassuring precedent about the calibre of person it catches, mostly by people who saw the diagonals, correctly concluded that the primes were not random, and incorrectly concluded that they had discovered this.

They are not random. That has never been in dispute — the primes are entirely determined, and there is nothing probabilistic about them. What the diagonals show is that a specific deterministic structure, quadratic residues, leaves a visible trace when the integers are laid out in a spiral. It is a real effect with a partial theory.

What the picture cannot show #

The spiral shows a pattern and can say nothing whatever about why it is there, or whether it persists. Both of those are the actual questions.

Worse, it cannot show the one thing that would settle the matter: behaviour at infinity. Every spiral ever drawn is finite, the density of primes falls away like $1/\ln n$, and the diagonals thin out along with everything else. Whether a given diagonal contains infinitely many primes is invisible at any scale — the picture at a million looks like the picture at nine hundred, and neither is evidence about the limit.

That is the practical form of the limitation. Extending the picture is the obvious response to an unproved pattern and it is not a response at all: each larger drawing is consistent with the conjecture and consistent with its failure somewhere further out, and the two are indistinguishable at every finite size.

This is the honest difference between this essay and the one about Pascal’s triangle. Both show a striking pattern in a familiar object. One has a two-line explanation; the other has a conjecture from 1923 and no proof. Nothing in either picture indicates which is which, and a reader who trusts pictures to signal their own explicability will be badly served by exactly one of them.

The ladder from here #

Rungs above: the sieve of Eratosthenes, drawn. Euclid’s proof of infinitude, and two others with quite different pictures. The prime number theorem as a staircase closing on $x / \ln x$. Prime gaps, twin primes, and the bounded-gaps breakthrough. Euler’s polynomial explained, via the class number of $\mathbb{Q}(\sqrt{-163})$. Quadratic residues as a pattern. Dirichlet’s theorem on primes in arithmetic progressions — the one case where the analogous question is settled. The Cramér model made precise, and where it fails. And the Riemann zeta function, where the distribution of primes turns into a question about the zeros of a complex function.

Randomness that is not random #

The primes are a strange object in this respect. They are completely determined and yet, statistically, they behave very much as though they had been chosen at random with probability $1/\ln n$ — the Cramér model, which is wrong in detail and startlingly accurate in aggregate. Compare a spiral of actually random points at the same density and it looks quite different: no diagonals, no axes, just noise.

The primes are the opposite of random in exactly one visible way — they avoid the residues they must avoid — and indistinguishable from random in most others.

Balls falling through a peg board is the mirror image of this situation: genuinely random inputs producing a shape so reliable it can be predicted precisely. Here the inputs are entirely determined and the output looks like noise with a few streaks in it.

Ulam had a talent for this. The same instinct — try it and see what the picture does — produced the Monte Carlo method a decade and a half earlier, from a game of solitaire.

He drew his spiral on scrap paper during a talk. The talk is not recorded as having been memorable.