The first number that is not a square

Modulo an odd prime $p$, exactly half of the numbers $1, 2, \ldots, p - 1$ are perfect squares — quadratic residues — and the other half are not. Reciprocity says whether one prime is a square modulo another, and its supplements settle −1 and 2. Those laws decide whether a particular number is a square. This essay asks about the first number that is not.

For half of all primes the answer is 2. For most of the rest it is 3 or 5. But there are primes for which the squares run on for a long time: modulo 366,791, every number from 1 to 42 is a square, and 43 is the first that is not.

Write $n(p)$ for the least quadratic non-residue modulo $p$. How large can it be? The truth, as far as any computation shows, is tiny — a small multiple of $\log p$. The best theorem allows about $p^{0.152}$. The Riemann hypothesis, if true, would bring the bound down to $2(\ln p)^2$, and the gap between the conjecture and what is proved has stood since 1957.

Why anyone needs a non-square #

The question is not idle, because several of the most-used algorithms in number theory need a non-square before they can start, and the only general way to find one is to try $2, 3, 4, \ldots$ until one fails. Taking a square root modulo a prime is the standard example. When $p$ leaves 3 on division by 4 the root of a square $a$ is simply $a^{(p+1)/4}$, but when $p - 1$ is divisible by a high power of 2 the Tonelli–Shanks method has to climb through the 2-power part of the group of remainders, and it does so by the powers of a single known non-square. Every step after that one is deterministic and fast. The first step is a search, and its length is $n(p)$.

Primality testing has the same shape. A test to base $a$ catches a composite $n$ unless $a$ happens to be one of its liars, and for the Euler form of the test the liars of a composite make up a proper subgroup of the remainders prime to $n$ — at most half of them. The quadratic residues modulo a prime are a proper subgroup too, of exactly half, and $n(p)$ is the first number outside it. So whether testing every base up to some small bound is enough to certify a prime is the same question one level up — how long can a run of numbers stay inside a proper subgroup? — and it has the same answer: under the generalised Riemann hypothesis, testing every base up to $2(\ln n)^2$ suffices, a result of exactly the kind this essay is about, and running the test backwards is how a prime is certified without it. Unconditionally the guarantees are far weaker, and in practice nobody has ever met a case where they matter.

So the gap between what is true and what is proved is not only a gap in understanding. It is the difference between an algorithm whose running time is known and one whose running time is merely observed.

Why the first non-square is a prime #

The least non-residue is always a prime, and the reason is the multiplicativity of squares. A product of two squares modulo $p$ is a square, so a number all of whose prime factors are squares is itself a square. The first number that is not a square therefore has a prime factor that is not a square, and that prime factor is no larger than the number — so it is the number. The walk in the figure keeps climbing long after 43 for the same reason: every number built only from the primes below 43, like 44 or 45 or 48, is still a square.

Euler’s criterion makes the test concrete: $a$ is a square modulo $p$ exactly when $a^{(p-1)/2}$ leaves 1, and is not when it leaves $p - 1$. For $p = 366{,}791$ that power of 2 leaves 1, and so does that power of 3, of 5, and of every prime up to 41; the power of 43 leaves $366{,}790$. Then the walk climbs again through 44, 45 and 46, because each factors into primes already shown to be squares; it turns down at 47, the second non-square prime, and then climbs straight through 48 to 52 for the same reason as before. It turns down only at a number with an odd count of non-square prime factors. By 200 it has taken 166 steps up and 34 down. The first non-square fixes the pattern of everything after it to a remarkable extent: a single multiplicative choice at each prime determines the whole walk.

So $n(p)$ is the first prime $q$ that is not a square modulo $p$, and reciprocity decides each prime separately. Whether 2 is a square depends on $p$ modulo 8; whether 3 is depends on $p$ modulo 12; whether 5 is depends on $p$ modulo 5; and in general whether $q$ is depends on $p$ modulo $4q$. Those conditions are independent across different $q$, and each holds for half of all primes, so the chance that 2, 3, 5, …, up to the $(k-1)$-th prime are all squares and the $k$-th is not is $2^{-k}$.

The shares match: 50.0 per cent of primes below ten million have $n(p) = 2$, 25.0 per cent have $n(p) = 3$, 12.5 per cent $n(p) = 5$, and so on down to a fifth of a per cent for 23. The prediction is exact in the limit, by Dirichlet’s theorem on primes in progressions applied to all the moduli at once, and ten million is enough to see it to three significant figures for the first several primes.

The independence is the Chinese remainder theorem at work in disguise. The conditions on $p$ modulo 8, modulo 12, modulo 20, modulo 28 combine into one condition modulo their least common multiple, and the remainders allowed by each combine freely; Dirichlet’s theorem then says the primes spread evenly across all the allowed remainders. Nothing in that argument is probabilistic. The primes are not random, and the $2^{-k}$ law is a statement about how they fill arithmetic progressions, but the arithmetic makes them behave exactly as a sequence of fair coins would — heads at each small prime until the first tails.

That picture is accurate for any fixed $k$, and it is precisely what fails at the extremes. For a coin, a run of $k$ heads has probability $2^{-k}$ whatever $k$ is; for primes, a run of $k$ squares needs $p$ to sit in one of a set of progressions whose modulus is the product of the first $k$ primes, and there are not enough primes below $x$ to fill progressions with a modulus far beyond $x$. So the coin model predicts a longest run of order $\log_2$ of the number of primes, about $\log p$ — which is roughly where the records sit — but it cannot be turned into a proof, because the uniform spread of primes across progressions is only known for moduli much smaller than the primes themselves.

Reciprocity decides the first steps #

The first two cases are decided by the remainder of $p$ on division by 24.

The number 2 is a square modulo $p$ exactly when $p$ leaves 1 or 7 on division by 8, and 3 exactly when $p$ leaves 1 or 11 on division by 12. Combined, the eight possible remainders modulo 24 split as four where 2 is not a square and $n(p) = 2$, two where 2 is but 3 is not and $n(p) = 3$, and two — the remainders 1 and 23 — where both are squares and $n(p)$ is at least 5. Every prime below ten million obeys the table; it is a theorem, and the check is that the arithmetic was done right. Deciding further needs remainders modulo 5, 7 and beyond, and every additional prime doubles the number of classes, which is why a prime with $n(p) = 43$ has to satisfy fourteen independent conditions at once and is correspondingly rare.

An average of 3.6746 #

Since $n(p)$ is the $k$-th prime with probability $2^{-k}$, its average over primes should be $\tfrac22 + \tfrac34 + \tfrac58 + \tfrac7{16} + \cdots$, the primes weighted by powers of a half. Paul Erdős proved in 1961 that it is.

The first term contributes 1, the first two 1.75, the first three 2.375, the first five 3.156; by the ninth prime, 23, the partial sum is 3.611, and it takes twenty terms to get within a thousandth of the limit. So the average is dominated by the small primes, as the distribution says it must be, but the tail matters at the second decimal place. The sum is $3.674643966\ldots$ and the average over primes below ten million is 3.6634, still creeping upward. The approach is slow because the large values of $n(p)$ — which contribute to the average in proportion to their size — are rare among small primes and only begin to appear in their limiting proportion when the primes are large enough to accommodate long runs of squares. A prime with $n(p)$ equal to the $k$-th prime has to lie in a particular residue class modulo the product of $4q$ over the first $k$ primes, and below ten million there is not room for most of those classes to be filled.

Records far below every bound #

The averages describe typical primes. The extreme primes are what the theorems are about.

The records come at 3, 7, 23, 71, 311, 479 and on through the figure, reaching 43 at 366,791, 47 at 3,818,929 and 53 at 9,257,329. Divided by $\ln p$, they run 1.5 to 1.6 for the first few, 2.0 to 2.5 for records between 311 and 10,559, and 3.0 to 3.4 for the last four. So they grow faster than $\ln p$, but only by a factor that has roughly doubled while $p$ has grown by five orders of magnitude. Against $2(\ln p)^2$ — which is 328 at 366,791 and 515 at 9,257,329 — they are a tenth of the allowance or less, and the ratio is falling. Between records the gaps are irregular: no new record arrives between 31 at 31,391 and 43 at 366,791, and 37 and 41 are skipped altogether, because the first prime with a given least non-residue need not come before the first prime with a larger one. Every one lies under $2(\ln p)^2$, the explicit bound Eric Bach proved in 1990 would follow from the generalised Riemann hypothesis — Nesmith Ankeny had shown in 1952 that the hypothesis implies some bound of that shape.

Without the hypothesis the best result is David Burgess’s of 1957: $n(p)$ is at most about $p^{1/(4\sqrt e)} \approx p^{0.152}$ for large $p$, up to factors smaller than any power. It is a deep theorem — the exponent comes from combining a careful estimate of how evenly squares are spread in short intervals with an old trick of Vinogradov’s — and it is enormously weaker than the truth seems to be: at $p = 10^{100}$ it allows a first non-square around $10^{15}$, where the Riemann-hypothesis bound allows about a hundred thousand and the records suggest a few hundred. Ivan Vinogradov conjectured that $n(p)$ grows more slowly than every power of $p$, and that conjecture is still open.

These are statements about the limit, and at the sizes in the figure they say almost nothing numeric. At $p = 9{,}257{,}329$ the power $p^{0.152}$ is only about 11, below the true value of 53; Burgess’s theorem carries an arbitrarily small extra power and an unstated constant, and it is the growth rate that is being compared, not the value. Explicit versions exist, with constants worked out, and they begin to bite only for primes with dozens of digits.

There is a lower bound too. Sidney Graham and Cecil Ringrose proved in 1990 that $n(p)$ exceeds a constant times $\ln p \cdot \ln\ln\ln p$ for infinitely many primes, so the records cannot stay bounded by a fixed multiple of $\ln p$ — and under the Riemann hypothesis Hugh Montgomery had shown that $\ln p \cdot \ln\ln p$ is reached infinitely often. The true growth of the records is somewhere between those lower bounds and $2(\ln p)^2$.

A walk that stays near the axis #

Burgess’s proof, like every bound on $n(p)$, begins by controlling the walk of Legendre symbols: if the first $x$ numbers were all squares, the walk would climb $x$ steps straight up, and a theorem that the walk never climbs that far rules it out.

George Pólya and Ivan Vinogradov proved independently in 1918 that the walk never strays more than about $\sqrt p \ln p$ from nought. The proof expands the indicator of an interval into sums of roots of unity weighted by the symbol — Gauss sums, whose size is exactly $\sqrt p$ — and the logarithm comes from adding the contributions of all the frequencies. In practice the excursions are far smaller than the theorem allows: between about half of $\sqrt p$ and twice it for every prime sampled. The walk looks like a random walk of $\pm 1$ steps, whose excursions over $p$ steps are of order $\sqrt p$, and the extra logarithm in the theorem is the price of proving it for every prime rather than typical ones.

A climb of $x$ straight steps at the start of the walk would be an excursion of $x$, so the Pólya–Vinogradov bound alone gives $n(p) \le \sqrt p \ln p$. That is a genuine theorem — it is smaller than $p$ — but only barely, and it uses nothing about the first numbers in particular. The improvement comes from using what the first non-square forces on everything after it.

Where the square root of e comes from #

Suppose every prime up to $y$ is a square modulo $p$. Then so is every number up to $x$ whose prime factors are all at most $y$ — every $y$-smooth number — and the share of numbers up to $x$ that are smooth is Dickman’s function $\rho(u)$, where $y = x^{1/u}$. On the range from 1 to 2 that function is exactly $1 - \ln u$.

Now count the non-squares up to $x$ another way. Each has a prime factor above $y$ that is a non-square, so there are at most as many as there are numbers up to $x$ with some prime factor between $y$ and $x$, which is about $x \sum 1/q$ over primes $q$ in that range — and by Mertens’s theorem that sum is $\ln(\ln x / \ln y) = \ln u$. So at most a share $\ln u$ of the numbers up to $x$ are non-squares.

The Pólya–Vinogradov bound says the other thing: once $x$ is a little larger than $\sqrt p \ln p$, the walk has not strayed far from nought, so very nearly half of the numbers up to $x$ are non-squares. Half cannot be at most $\ln u$ unless $\ln u \ge \tfrac12$, which is $u \ge \sqrt e$. With $x$ just above $\sqrt p$, the least non-residue is at most $y = x^{1/\sqrt e}$, about $p^{1/(2\sqrt e)} \approx p^{0.303}$.

That is Vinogradov’s argument from the 1920s, and the $\sqrt e$ is nothing more mysterious than the point where the smooth numbers make up exactly half: $\rho(\sqrt e) = 1 - \tfrac12 = \tfrac12$. Burgess’s contribution was to make the walk’s bound work on intervals of length $p^{1/4 + \varepsilon}$ instead of $\sqrt p$, by an argument that raises the character sum to a high even power and counts solutions of a congruence; feeding that into the same smooth-number count halves the exponent to $1/(4\sqrt e) \approx 0.152$. Nobody has improved the $1/4$ in nearly seventy years, and a bound for the walk on shorter intervals is exactly what any further progress would need.

What the computations cannot settle #

Every figure is exact for the primes it covers, and none says anything about larger primes. The records below ten million fit comfortably under $2(\ln p)^2$, but that bound is conditional on an unproved hypothesis, and no finite computation tests it; a prime with an enormous least non-residue, if one existed, would be a counterexample to the generalised Riemann hypothesis and could be anywhere. The distribution’s agreement with $2^{-k}$ is a theorem in the limit, and the figure shows only how close ten million comes.

There is also a quieter limitation. The records are computed by testing $2, 3, 5, \ldots$ in turn with the Jacobi symbol, which is exact; but listing the first prime with each value of $n(p)$ beyond 53 needs searching far beyond ten million, where the next records lie, and the figure shows only the ones in range.

Still open: Vinogradov’s conjecture #

Is $n(p) < p^\varepsilon$ for every $\varepsilon > 0$ and every large enough prime $p$? That is Vinogradov’s conjecture, and it is open; even the much weaker statement that the exponent $1/(4\sqrt e)$ can be lowered at all has resisted every attempt since Burgess. The generalised Riemann hypothesis would give far more — a bound by a power of $\log p$ — and the same hypothesis would settle a whole family of related questions, like how small the least primitive root can be, the first number whose powers run through every non-zero remainder. That the least non-residue is in practice a small multiple of $\log p$, while what can be proved is a fractional power of $p$, makes it one of the cleanest examples of the distance between what primes evidently do and what can be shown about them.

Squares in a row #

Modulo a prime, the first number that is not a square is itself a prime, and it is the $k$-th prime for a fraction $2^{-k}$ of all primes — so its average is Erdős’s $\sum p_k/2^k = 3.6746$. Its largest values grow like a small multiple of $\ln p$: 43 at 366,791, 53 at 9,257,329, all beneath the bound $2(\ln p)^2$ the Riemann hypothesis would give. Unconditionally the best bound is Burgess’s $p^{0.152}$, built on the Pólya–Vinogradov estimate that the walk of Legendre symbols stays within $\sqrt p \ln p$ of nought — a walk that in practice never strays much beyond $\sqrt p$.