Almost no number is one

The first few sums of two squares are $1, 2, 4, 5, 8, 9, 10, 13, 16, 17, 18, 20$. That is twelve of the first twenty, which suggests a property most numbers have.

Count further and the impression survives for a long time. Below a hundred there are forty-three; below a thousand, three hundred and thirty; below a million, a hundred and fifty-five thousand or so — still more than one in seven. The fraction is going to nought, and the going is slow enough that no range anyone can count over shows it convincingly.

Landau proved in 1908 that the count below $x$ behaves like

$$B(x) \;\sim\; K\,\frac{x}{\sqrt{\log x}},$$

with $K \approx 0.76422365$, and Ramanujan had the same statement, unproved, in his first letter to Hardy. Dividing by $x$ gives a density of $K/\sqrt{\log x}$, which goes to nought — and at $x = 10^6$ is still $0.206$, and at $x = 10^{100}$ is still $0.05$.

What the condition is #

The count is of numbers, not of primes, so the first thing needed is which numbers qualify. The condition is a statement about factorisation: a number is a sum of two squares exactly when every prime congruent to $3$ modulo $4$ in its factorisation appears to an even power.

The reason is that the quantity $a^2 + b^2$ is a norm in the Gaussian integers and norms multiply. A prime $\equiv 1$ splits into two conjugate Gaussian primes and contributes freely; $2$ ramifies and contributes freely; a prime $\equiv 3$ stays prime in $\mathbb{Z}[i]$ and can only appear as the norm of a power of itself, which costs two of it at a time. So the condition is a parity constraint, one prime at a time, and it is a condition on the factorisation rather than on the number — which is why no congruence on $n$ decides it, unlike the three-square case.

That is what makes the counting hard. Asking how many numbers below $x$ have a property of their factorisation is asking a question that the sieve was built for, and the answer is never a clean fraction.

Where the square root of the logarithm comes from #

The exponent is a half, and it is a half for a reason that is worth following, because the same shape of argument fixes the exponent in a whole family of counting problems.

Think of building a qualifying number by choosing its primes. The primes $\equiv 1 \pmod 4$ may be used freely; the primes $\equiv 3$ must be used in pairs, which is a severe restriction; and the two classes each contain half the primes, a fact of Dirichlet’s, which is the theorem that the primes do not favour a residue class in its smallest interesting case.

Being forbidden from using half the primes at all costs a factor of $\sqrt{\log x}$, and here is the shape of why. The count of numbers below $x$ built only from an allowed set of primes is governed by a product $\prod_{p \le x, \text{allowed}} (1 - 1/p)^{-1}$; over all primes that product behaves like $\log x$, by Mertens; and over a set of density one half in the primes it behaves like $\sqrt{\log x}$, because the density appears in the exponent. A number formed with a free choice over half the primes therefore has $\sqrt{\log x}$ rather than $\log x$ worth of freedom, and the count comes out smaller by the missing factor.

So the exponent $\tfrac12$ in $\sqrt{\log x}$ is the density of the allowed primes, and nothing else. Change the condition so that a third of the primes are free and the exponent becomes a third; that is the general theorem, due to Landau in the same paper and sharpened by Selberg and Delange, and it says the count of numbers whose prime factors are restricted to a set of density $\delta$ behaves like $x(\log x)^{\delta - 1}$ up to a constant.

The pairing of the forbidden primes contributes only to the constant. That is worth separating, because it is the counterintuitive half: the requirement that primes $\equiv 3$ appear to even powers is what makes the arithmetic of the constant complicated, and the shape $x/\sqrt{\log x}$ would be the same if they were forbidden outright.

The constant, computed and unidentified #

$K$ has an exact expression, and looking at it explains why nobody has a closed form.

$$K \;=\; \frac{1}{\sqrt 2}\prod_{p \equiv 3 \ (4)} \left(1 - \frac{1}{p^2}\right)^{-1/2}$$

The product runs over the primes $\equiv 3 \pmod 4$ — $3, 7, 11, 19, 23, \ldots$ — and it converges, because $\sum 1/p^2$ does. But it converges slowly, and worse, it converges over a set defined by a congruence, which is exactly the kind of set whose products do not simplify.

The computation is nonetheless routine, and it is worth knowing how. Taking logarithms turns the product into $-\tfrac12\sum \log(1 - p^{-2})$, and expanding the logarithm turns that into a sum of $\sum_{p \equiv 3} p^{-2k}$ over $k$. Each of those prime sums over a congruence class is expressible in terms of the Riemann zeta function and the Dirichlet $L$-function for the character mod $4$ — and that $L$-function at even arguments is a rational multiple of a power of $\pi$, while at odd arguments it is Catalan’s constant and its relatives. So $K$ is built from $\zeta$ and $L$ at integer points, and the series converges fast enough that Flajolet and Vardi computed thirty digits in 1996 with a few lines.

$K = 0.764223653589220662990698731250\ldots$, and it is not known to be irrational.

That is the state of affairs worth dwelling on. A constant can be computed to any accuracy wanted and still be unidentified, and the two are genuinely separate achievements — the second requires knowing that it equals something, and no candidate has been found. It sits with Catalan’s constant, the Euler–Mascheroni constant of the collector’s wait, and the Brun constant in a class of numbers that arithmetic produces routinely and about which almost nothing is known.

How rare is rare #

At $x = 10^6$ the density is about $0.206$; it takes $x = 10^{28}$ to halve that, and $x = 10^{112}$ to halve it again. The function $1/\sqrt{\log x}$ is one of the slowest decays a natural counting problem produces, and there are two consequences.

It is worth putting one comparison beside that. The primes themselves have density $1/\log x$, which at a million is about $0.072$ — so a random number below a million is about three times more likely to be a sum of two squares than to be prime, and both densities are heading to nought. The one that gets there faster is the primes’, by a factor of $\sqrt{\log x}$, which at any size a person deals with is a single-digit multiplier.

Nobody would guess the answer from data. A table of counts to a billion is compatible with a density tending to a positive limit, with a density tending to zero like $1/\log x$, and with a density tending to zero like $1/\sqrt{\log x}$. The three differ by factors nobody could distinguish over any computable range, and the theorem is the only way to know.

And the qualitative statement is the surprising one. Almost no number is a sum of two squares is true and is not what any amount of counting suggests. The reason to trust it is the structure of the last section rather than the arithmetic: half the primes are forbidden, and forbidding half the primes has a cost that accumulates without bound, however slowly.

That contrast — a theorem whose content is invisible at every scale that can be examined — is the same shape as the harmonic series passing every bound, which was doubted for centuries for exactly the reason. Slow is not small, and the two are confused whenever the evidence is a table.

Multiplicity, and the difference between a number and a circle #

There is a distinction the counting quietly makes and it is worth pulling out, because the two questions are often run together and have completely different answers.

How many $n$ below $x$ are sums of two squares at all is $B(x) \sim Kx/\sqrt{\log x}$ — this essay’s subject, a count of numbers.

How many lattice points lie inside a circle of radius $R$ is $\pi R^2$ plus an error — a count of points, which is the route to the Leibniz series and a problem open since 1837.

The two are the same sum organised differently: adding $r_2(n)$ over $n \le R^2$ gives the point count, and counting the $n$ with $r_2(n) > 0$ gives $B$. So the point count is a total over a rapidly-varying function and the number count is a count of its support, and the first has a smooth answer while the second has a logarithm in it.

What separates them is that $r_2$ is very unevenly spread. The numbers that qualify are rarer and rarer, and the ones that qualify carry more and more representations to compensate — a number with $k$ distinct prime factors $\equiv 1 \pmod 4$ has at least $2^k$ points on its circle. So the average of $r_2$ is $\pi$, exactly, for ever; the median is nought and stays nought; and the whole difference between the two counting problems is the gap between those two statements.

Where the same question has a different answer #

Putting three neighbours beside it is the fastest way to see what is special.

Sums of four squares: every number. Density one, no condition at all, Lagrange 1770. Four squares is enough room that no obstruction survives.

Sums of three squares: all but $4^a(8b+7)$. Density $5/6$, and the excluded set is defined by a congruence — so this is a positive density and the count is a fraction of $x$ rather than $x$ over anything.

Sums of two squares: density nought. The condition is on the factorisation, and no congruence describes it.

Numbers that are themselves squares: density nought too, and for a reason nothing like this one — there are $\sqrt x$ of them below $x$, which is a power smaller rather than a logarithm smaller. Being a square is rare in a way that is easy to see; being a sum of two squares is rare in a way that no amount of looking reveals.

Sums of two cubes, or of two fourth powers: a count of order $x^{2/3}$ and $x^{1/2}$ respectively, which is a power of $x$ smaller rather than a logarithm smaller — a completely different regime, because there are only about $x^{1/2}$ squares below $x$ but their sums fill a positive-density-looking set, while there are $x^{1/3}$ cubes and their sums cannot.

So two squares sits at the boundary of two regimes, and it is the only one of the five whose answer is neither a constant fraction nor a power of $x$. The logarithm in it is the signature of a condition that is about factorisation rather than about size, and it is what makes this the interesting case.

Four decades of data, and a claim about the limit #

The falling curve is drawn over four orders of magnitude and the claim is about the limit. Over the range drawn the density moves from about a third to about a fifth, which is a fall and is equally compatible with a limit of a sixth. The figure establishes only that the density is falling, which is true and is not the theorem; the theorem is about behaviour no plot reaches.

The flat curve is flat because the theorem is true, and its flatness is not evidence of the constant. What is drawn is $B(x)\sqrt{\log x}/x$ against $x$, and it sits near $0.764$ over the range. A wrong constant would show as a curve near a different value, but a wrong exponent — $\log x$ in place of $\sqrt{\log x}$ — would show as a slowly drifting curve that over four decades is hard to distinguish from a flat one. The figure cannot separate the theorem from its near neighbours.

The sieve is exact and the range is small. Every count here is made by testing every number’s factorisation up to twenty thousand, checked against the circle count for the first two hundred. That is a measurement and it is not an approximation; what it is not is large, and the asymptotic statement is about a region no exact sieve reaches.

And the constant is quoted, not computed. $0.76422365$ appears in the figure as a horizontal line taken from the literature, since evaluating the product over primes $\equiv 3 \pmod 4$ to that accuracy needs the $L$-function machinery of the section above and is not a page-build’s business. Everything else on the page is computed from the numbers; that line is not, and it is the one number a reader should check elsewhere.

The theorem’s other half, which is about the primes #

Landau’s argument has an ingredient this essay has used without naming, and naming it says where the difficulty actually is.

The count is over numbers built from a set of primes, and what makes the sum computable is knowing how many primes there are in each residue class below $x$. Dirichlet’s theorem says the two classes mod $4$ are equally populated; the quantitative version, which is what the counting needs, says each has about $\tfrac12 \cdot x/\log x$ members below $x$, with an error term.

That error term is where the subject’s hard questions live. How evenly the primes distribute between $1$ and $3$ modulo $4$ is a question about the zeros of an $L$-function, exactly as the overall prime count is a question about the zeros of $\zeta$; and the small persistent excess of primes $\equiv 3$ over primes $\equiv 1$ — Chebyshev’s bias, which holds for most $x$ and not all — is a phenomenon nobody had a clean account of until the 1990s.

None of that disturbs the leading term here. Landau’s result needs the classes to have density a half and nothing finer, and the density is a nineteenth-century theorem. What it means is that sharpening this essay’s answer past its leading term runs into the same wall every counting problem about primes runs into, one layer down and from an unexpected direction: a question about which numbers are sums of two squares turns out to be a question about where a certain function’s zeros are.

Still open here: what the constant is, and how well it approximates #

$K$ is computed to thirty digits, has an exact product formula, and is not known to be irrational — nor is Catalan’s constant, which appears in its evaluation. There is no reason to expect any of them to be anything nameable, and no method that would settle it.

The other open direction is sharper and more interesting: how good is the approximation? Landau’s theorem gives the leading term, and there is a full asymptotic expansion in descending powers of $\log x$ — the error after the leading term is of order $x/(\log x)^{3/2}$, with a computable constant, and so on down. What that expansion does not have is an error term of the kind the prime number theorem has, tied to the zeros of the zeta function, and obtaining one is the analogue here of the questions the prime count leaves open.

Density nought, at a human scale #

The habit is about what almost none means and how badly it can be misread.

A property held by a fifth of the numbers below a million, and by a twentieth of those below $10^{100}$, is a property that a person examining numbers will meet constantly and that almost no number has. Both halves are true and they describe the same fact. A density tending to zero says nothing about any particular range, and a density in a particular range says nothing about the limit.

The arithmetic that produces this is the same arithmetic in every case where a logarithm appears in a density: the restriction accumulates across scales, each scale contributes a little, and the total passes any bound while never being visible at any one scale. When a count is off by a logarithm, the honest statement is about a limit and the honest picture is of a range — and the two will not agree, which is not a defect of either.