The sieve written as a product

Every whole number greater than one is a product of primes in exactly one way. That is a statement about individual numbers, proved by descent, and it is the foundation of the subject. Written as an identity between two infinite expressions, it becomes something else entirely: a statement about convergence, to which the whole of analysis can be applied.

The left panel is the identity in miniature and it is checked rather than asserted: the generator multiplies the three series, enumerates the numbers they build, adds their reciprocals, and refuses to draw unless the two agree to twelve decimal places.

Multiplying out #

Take one geometric series for each prime:

$$\left(1 + \frac{1}{2} + \frac{1}{4} + \cdots\right)\left(1 + \frac{1}{3} + \frac{1}{9} + \cdots\right)\left(1 + \frac{1}{5} + \frac{1}{25} + \cdots\right)\cdots$$

Expanding means choosing one term from each bracket and multiplying, then adding over all choices. A choice is a set of exponents — a power of two, a power of three, a power of five, and so on, all but finitely many of them the zeroth — and the product of the chosen terms is $1/n$ where $n$ is the number those exponents build.

So the expansion is a sum of $1/n$ over some collection of $n$, and two questions decide the identity. Does every $n$ appear? Yes, because every number has a factorisation. Does any $n$ appear twice? No, because the factorisation is unique. The identity

$$\prod_{p} \left(1 - \frac{1}{p}\right)^{-1} = \sum_{n=1}^{\infty} \frac{1}{n}$$

is therefore not a computation but a restatement: the left side is a product over primes, the right a sum over integers, and the equality is unique factorisation.

Each bracket sums to $(1 - 1/p)^{-1}$, which is why the product is usually written that way. The form with the reciprocals is the one that makes the sieve visible: $1 - 1/p$ is the fraction of numbers that survive striking out the multiples of $p$, and the whole product is the fraction surviving every strike-out — which is where the density heuristic for the primes comes from, and where it goes wrong by a factor.

What truncating does, and does not do #

The identity is between infinite expressions, and every drawable version cuts it down. It is worth being precise about what the cut version says, because it is an exact statement rather than an approximate one.

Keeping only the primes up to some bound and only the exponents up to some power gives a finite product, and multiplying it out gives a finite sum — over precisely those numbers whose prime factors are within the bound and whose exponents are within the power. Nothing has been approximated. The identity has been restricted to a subset of the integers, and it holds exactly on that subset.

This is the useful way to think about every sieve argument. Striking out the multiples of the primes up to $\sqrt{x}$ leaves the primes; keeping only the brackets for those primes keeps the numbers those primes build; and the two operations are the same operation seen from either side of the identity.

The numbers left out by a truncation are the ones with a large prime factor, and there are a great many of them: most numbers have a prime factor larger than their own square root. That is why the finite version, though exact, converges to the infinite one so slowly, and it is the practical difficulty every sieve method has to manage.

Euler’s proof that the primes do not run out #

The identity gives an argument for the infinitude of the primes that has nothing in common with Euclid’s.

Suppose there were finitely many primes. Then the product has finitely many brackets, each of them a convergent geometric series with a finite sum, so the product is a finite number. But the product equals the harmonic series, which diverges. A finite number cannot equal an infinite one, so there are infinitely many primes.

Compared with Euclid’s proof this is heavy machinery for a result already known — and it proves considerably more, which is the reason to have it. Euclid’s argument shows that no finite list is complete and gives no idea how the primes are distributed. Euler’s shows that they are numerous enough for the sum of their reciprocals to misbehave, and that quantity is the next question.

How numerous, exactly #

Take logarithms of the product identity and the sum over primes appears directly, which is the step that converts the identity into information.

$$\ln \sum_{n \le x} \frac{1}{n} \approx \sum_{p \le x} \frac{1}{p} + \text{a bounded amount},$$

because $-\ln(1 - 1/p)$ is $1/p$ plus something of size $1/p^2$, and the sum of $1/p^2$ over all primes converges. The harmonic sum is about $\ln x$, so its logarithm is about $\ln \ln x$, and

$$\sum_{p \le x} \frac{1}{p} \approx \ln \ln x + M$$

with $M = 0.2615$, the Mertens constant. That is the right-hand panel of the first figure, and the generator checks the curve against that estimate at every point it draws, never letting the two differ by more than a twelfth.

Two consequences are worth extracting.

The primes are denser than the squares. The sum of the reciprocals of the squares converges — famously to $\pi^2/6$ — and the sum over primes does not. Any set whose reciprocals sum to infinity is, in this precise sense, a large set, and the primes are large while the squares are not.

The divergence is unbelievably slow. The sum passes 3 at about five million, passes 4 at about $1.8 \times 10^{18}$, and passes 5 somewhere past $10^{49}$. The growth is the logarithm of a logarithm, which is the slowest divergence anybody has cause to write down, and a quantity that grows without bound while staying under 5 for every number that will ever be examined is a useful corrective to the intuition that divergence means growth.

The factor the sieve heuristic is out by #

A section above says the product is the fraction of numbers surviving every strike-out, and that the density heuristic built on it goes wrong by a factor. The factor is computable, it is famous, and it is the same constant the harmonic series produced.

Mertens’ third theorem, from 1874, evaluates the product directly: the product of $1 - 1/p$ over the primes up to $x$ behaves like

$$\frac{e^{-\gamma}}{\ln x},$$

where $\gamma$ is the Euler–Mascheroni constant, the gap between the harmonic sum and the logarithm. It is not obvious that a product over primes should know about that constant, and the reason it does is the logarithm step of the previous section: taking logarithms turns the product into the sum of reciprocal primes, whose own constant is Mertens’ $M$, and $M$ and $\gamma$ differ by a sum over primes that evaluates in closed form.

Now run the sieve heuristic and watch it miss. To find the primes up to $x$, strike out the multiples of every prime up to $\sqrt{x}$. If the strike-outs behaved independently, the surviving fraction would be the product over those primes, which by Mertens is about $e^{-\gamma}/\ln\sqrt{x}$ — and since the logarithm of a square root is half the logarithm, that is about $2e^{-\gamma}/\ln x$, a little over $1.12$ divided by $\ln x$.

The truth, from the counting theorem, is $1/\ln x$. So the naive sieve overestimates the primes by about twelve per cent, forever, and the discrepancy does not shrink as $x$ grows — it is a constant factor of $2e^{-\gamma}$, sitting there permanently.

That is worth dwelling on, because the heuristic is not slightly wrong in a way more care would fix. The strike-outs are not independent, and the dependence accumulates to exactly this constant. Any argument that treats divisibility by distinct primes as independent events inherits the error, and the error is not an error of estimation but of model.

The consequence for the subject is large. Sieve methods are the main elementary tool for counting primes and almost-primes, and this constant is the shape of their limitation: a sieve can bound a count from above and below and generally cannot pin it, because a factor of this kind survives every refinement. That obstruction has a name — the parity problem — and it is why sieve methods have never proved the twin prime conjecture despite coming close enough to prove that infinitely many pairs differ by a bounded amount.

So the identity at the top of this page is exact and the intuition built on it is not. The product counts what survives; it does not count independently, and $e^{-\gamma}$ is the price of the difference.

Where pi comes in #

Replacing the exponent $1$ by a variable $s$ turns the identity into the one Riemann used:

$$\zeta(s) = \sum_{n=1}^{\infty} \frac{1}{n^s} = \prod_p \left(1 - \frac{1}{p^s}\right)^{-1},$$

valid whenever the sum converges, which is for $s$ greater than one. The proof is the same expansion; the exponent changes nothing about the bookkeeping.

At $s = 2$ the sum is $\pi^2/6$, which Euler found in 1735 and which has no business containing a circle constant. Combining that with the product gives a fact about integers that is worth stating on its own: the probability that two whole numbers chosen at random have no common factor is $6/\pi^2$, or about $0.6079$. The derivation is one line from the product — the chance that neither is divisible by $p$ is $1 - 1/p^2$, these are independent across primes, and the product of those is $1/\zeta(2)$.

That is the appearance of $\pi$ in a question with no circle in it, and here the mechanism is completely visible: the circle constant enters through the value of the sum, the sum equals the product by unique factorisation, and the product is about divisibility. Nothing is mysterious; the two sides of an identity simply belong to different subjects.

What the identity is really for #

Euler’s product is the door through which analysis enters number theory, and the reason is that it converts a multiplicative statement into an additive one.

Facts about primes are facts about multiplication: which numbers divide which. Facts about convergence are additive: whether a sum of small things is finite. The product identity translates between the two registers, and once the translation exists, every tool for studying functions — differentiating, integrating, continuing into the complex plane, locating zeros — becomes a tool for studying primes.

The specific payoff is the counting theorem. Riemann’s route to it is to extend $\zeta$ beyond the region where the sum converges, take the logarithmic derivative of the product — which converts the product over primes into a sum over prime powers — and read off a formula for the count of primes in terms of where $\zeta$ vanishes. Every step of that depends on having both descriptions of the same function, and the identity is what supplies them.

The zeros are where the difficulty lives, and it is worth being clear that the identity itself says nothing about them: it holds only where the sum converges, and the zeros are all elsewhere. What the identity does is guarantee that $\zeta$ has no zeros at all in the region it covers, because a convergent product of non-zero factors cannot vanish — which is a small fact and the first step of every proof in the subject.

Where the product stops working #

The identity holds for $s$ greater than one and fails at $s = 1$, and the failure is the whole subject rather than a technicality.

At $s = 1$ both sides are infinite, which is the infinitude proof above. Just to the right of $1$ both sides are finite and enormous: $\zeta(s)$ behaves like $1/(s-1)$ as $s$ comes down to one, so the sum has a pole there. The primes’ influence on the function is entirely a matter of how that pole is approached, and every quantitative statement about the primes is a statement about the function near that point.

Extending $\zeta$ to the left of $s = 1$ cannot be done with either the sum or the product — both diverge — and requires an entirely different formula that agrees with the sum where both are defined. That extension is Riemann’s, and it is where the zeros are: none of them lies in the region the product covers, because the product cannot vanish there, so the interesting behaviour is by construction outside the reach of the identity that started it.

The situation is a good illustration of what analytic continuation is for. A function is defined by a formula on part of its domain; the formula is not the function, and the parts of the domain where the formula is silent are where the answers turn out to be. The geometric series is the small model of this — the sum $1 + r + r^2 + \cdots$ means nothing for $r$ past one, and the function $1/(1-r)$ it equals is perfectly well behaved there.

The other products #

Once the expansion is understood, it produces an identity for every function that respects multiplication, and the resulting catalogue is most of elementary number theory rewritten.

A function $f$ with $f(mn) = f(m)f(n)$ for coprime $m$ and $n$ has

$$\sum_{n=1}^{\infty} \frac{f(n)}{n^s} = \prod_p \left(1 + \frac{f(p)}{p^s} + \frac{f(p^2)}{p^{2s}} + \cdots\right),$$

by exactly the argument above: expanding the product picks one prime power from each bracket, and unique factorisation says each $n$ arises once.

Taking $f = 1$ gives $\zeta$. Taking $f(n)$ to be the number of divisors of $n$ gives $\zeta(s)^2$. Taking the Möbius function — which is $\pm 1$ on numbers with distinct prime factors and zero otherwise — gives $1/\zeta(s)$, and that reciprocal is where the coprimality probability above comes from. Taking Euler’s totient gives $\zeta(s-1)/\zeta(s)$.

The pattern is that arithmetic facts about these functions — that the divisor counts of coprime numbers multiply, that the Möbius sums over divisors vanish — become algebraic facts about products of $\zeta$, which are far easier to manipulate. That translation is the standard working method of the subject, and it is entirely a consequence of the expansion drawn in the first figure.

What the picture cannot show #

The left panel truncates twice over: three primes rather than all of them, and exponents capped at the third power. Both truncations are necessary to draw anything and both change the object — the identity is between two infinite expressions, and the finite version is an exact statement about a smaller set of numbers rather than an approximation to the infinite one.

The right panel is worse off. It draws the sum of reciprocal primes to a hundred thousand, where it has reached 2.71, and the claim is that it grows without bound. Nothing in the drawn range distinguishes that curve from one that is levelling off at 3, and no extension of the axis would help: the divergence is so slow that a picture reaching the age of the universe in computing time would show a curve that had crept up by less than one.

The proof is therefore doing all of the work here, and the picture is doing something more modest — showing that a quantity people expect to converge does not, and showing at what rate, which is a rate a picture can display even where the divergence cannot.

The ladder from here #

Below: unique factorisation, which the identity restates, and the harmonic series, which it leans on. Sideways: Euclid’s proof, the same conclusion from nothing at all, and the sieve, which the product is a rewriting of. Above: the counting theorem and the guaranteed prime before the double — the first of which this identity leads to, and the second of which it has nothing to say about.

The bookkeeping the identity depends on #

The expansion above is an infinite product of infinite sums, and rearranging such a thing is not always legal, so it is worth naming what makes it legal here.

Every term is positive. For a sum of positive terms the total does not depend on the order they are added in, and the same holds for the expansion of a product of positive series: whatever order the choices are made in, the total is the same. That is what licenses the argument, and it is the reason the identity is stated for real exponents above one rather than for the whole complex plane.

Where terms have signs, none of this is automatic. A series whose terms change sign can be rearranged to any total whatever, and the corresponding manipulations of products need their own justification — which is precisely why the extension of the identity into the region where the sum does not converge cannot be done by rearranging anything.

An identity that changed the subject #

The lasting point is what happens when a fact is rewritten in a language it was not stated in. Unique factorisation is a theorem about individual integers with a short proof; written as an identity between a sum and a product it becomes a statement about analytic functions, and every question about primes becomes a question about where a function is large, small or zero.

The move is worth recognising because it is one of the most productive in mathematics and one of the least obvious in advance. A geometric series drawn as a dissection of a square, a counting problem rewritten as a walk on a graph and a question about permutations rewritten as one about a group of symmetries are all the same manoeuvre, and in each case the new language brought with it a set of tools that had no visible relationship to the original question.