Every class, and in equal shares

The rung about residue classes aims Euclid’s construction at a class — build a number that must have a prime factor of the right shape — and finds that it works for some classes and not for others. For primes 3 mod 4 it works; for primes 1 mod 4 it needs a different construction; for primes 1 mod 5 nothing elementary is known.

The general theorem covers every case at once. Dirichlet, 1837: if $a$ and $q$ share no factor, the progression $a, a+q, a+2q, \dots$ contains infinitely many primes. No exceptions, no cases, and no elementary proof in the two centuries since.

What the theorem proves is more than infinitude, and the extra is where this rung spends its time.

What the theorem actually says #

Dirichlet’s proof does not produce a prime, exhibit a construction or extend Euclid in any recognisable way. It shows that a certain sum diverges.

Specifically: for $a$ coprime to $q$, the sum of $1/p$ over primes $p \equiv a \pmod q$ diverges. A sum over a finite set is finite, so the set is infinite — and the argument has, along the way, said how thick the set is.

That is the same shape as Euler’s proof that the sum of reciprocals of all primes diverges, and Dirichlet’s contribution is a way of isolating one residue class from the rest. The tool is a character: a function on the residues that multiplies correctly and takes complex values, used to build a weighted sum in which every class but the wanted one cancels.

The characters are the same objects as the one-dimensional representations of a group, applied to the group of units modulo $q$, and the cancellation is their orthogonality. A theorem about primes is proved by decomposing a function on a finite abelian group into frequencies, which is why the proof is not elementary and why nobody has made it so.

The character trick, done small #

The step that isolates one class is worth doing on the smallest case, because it is two lines and it is the entire reason the proof is analytic.

Modulo 4 there are two admissible classes and two characters on them: the trivial one, sending both 1 and 3 to $+1$, and the non-trivial one, sending 1 to $+1$ and 3 to $-1$. That second character is the Legendre symbol read as a sign and it takes exactly two values.

Now form two sums over the odd primes: one with every term $1/p$, and one with $1/p$ weighted by the character’s value. Adding them doubles the contribution of the class 1 and cancels the class 3 entirely; subtracting them does the reverse. Two sums, one linear combination, and a single class isolated.

The first sum diverges, since it is Euler’s up to the prime 2. So each class’s sum diverges provided the second sum stays bounded — and that is the whole difficulty. The weighted sum is $L(1, \chi)$ in the standard notation, and showing it is neither infinite nor zero is where the work is. It is the step that has never been made elementary, and for characters taking more than two values it is genuinely hard.

That is why the proof produces equal densities rather than merely infinitude. The trivial character contributes the whole count, every other character contributes a bounded amount, and dividing by the number of characters shares the count out evenly. The equality is not an extra theorem; it is what the cancellation leaves behind.

The densities, measured #

The proof gives more than divergence. It gives the rate: the sum over one class behaves like $1/\varphi(q)$ times the sum over all primes, where $\varphi(q)$ counts the classes coprime to $q$.

So the primes are shared equally among the admissible classes, and the counts should be near-equal at every bound.

The word equally is doing exact work. Modulo 4 there are two admissible classes, so each gets a half; modulo 10 there are four, so each gets a quarter; modulo 12 there are four again, since 1, 5, 7 and 11 are the residues coprime to twelve. The share is one over the count of admissible classes and never anything else, so a modulus with many admissible classes spreads the primes thinly and a modulus with few concentrates them, and neither affects any class’s infinitude.

That is worth stating because the obvious alternative guess is wrong. One might expect a class to get a share proportional to something about it — its size as a number, its own arithmetic — and it gets exactly the same as every other, whatever it is.

The inadmissible classes are worth a sentence because they are the whole of the coprimality hypothesis. A prime in the class 2 modulo 4 would be an even number greater than 2, and there are none; a prime in the class 0 would be a multiple of 4. Coprimality is not a technical condition; it is the statement that the class is not obviously empty, and the theorem says that being not obviously empty is enough.

The bias, which is real and is not a counterexample #

The equality is a statement about the limit and it is contradicted, apparently, at every bound anybody checks.

Chebyshev noticed in 1853 that primes 3 mod 4 outnumber primes 1 mod 4 — persistently, over every range then computable. The hero figure measures it: over bounds up to thirty thousand the class 3 leads at 99.8 per cent of them.

It is not a counterexample and the reason is worth stating precisely. The two counts are equal to leading order and differ in a lower-order term, and the lower-order term has a systematic sign. The lead grows like $\sqrt{x}/\log x$ while the counts themselves grow like $x/\log x$ — so the ratio of the counts tends to one, exactly as the theorem says, while the difference stays positive.

A density statement is compatible with a permanent-looking lead, and this is the cleanest example of it anywhere.

Where the bias comes from #

The explanation is one of the more satisfying in the subject and it fits in a paragraph.

The class 1 mod 4 contains the squares of primes: $3^2 = 9$ is 1 mod 4, and so is every odd square. Counting prime powers rather than primes gives two classes that really are equal, with an error term that has no bias at all. Removing the prime squares from the class 1 mod 4 then removes about $\sqrt{x}/\log x$ numbers from one side and nothing from the other.

The count of prime squares below $x$ is the count of primes below $\sqrt{x}$, which is about $2\sqrt{x}/\log x$ — and that is the size of the observed lead, which is the check that the explanation is the right one rather than a plausible story.

So the bias is the prime squares, subtracted. The class 3 mod 4 leads because the class 1 mod 4 has had its squares taken away, and the deficit is exactly the size the bias is observed to be.

That also predicts which races are biased and which are not: a class containing squares is at a disadvantage. Modulo 4 the class 1 contains them; modulo 3 the class 1 does; modulo 5 the classes 1 and 4 do. The bias is towards the non-square classes in every case, and it is measured to be.

How often the lead changes hands #

The complete answer is stranger than either the bias or the equality.

Littlewood proved in 1914 that the lead changes hands infinitely often. The proof is of the same non-constructive kind as the argument that a colouring exists: it shows that an average would be impossible if the sign never changed, and produces no bound at all on where a change occurs. So the bias is not permanent, the sign changes are unbounded in both directions, and the first one — at 26,861 for the modulus 4 — is the first of infinitely many.

The proportion of the time each side leads is a third question with a third answer, and the answer is not a half. Under a standard hypothesis, the class 3 mod 4 leads about 99.59 per cent of the time in a suitably weighted sense, which is remarkably close to the crude proportion the figure measures over a small range. The bias is a real quantity with a real value, not an artefact of a short computation. The weighting matters and is not a technicality: the ordinary proportion of bounds at which one side leads does not converge, so the quantity that has a value is a logarithmic average, which weights each bound by one over itself and therefore treats each decade equally.

Two things are worth separating here. The counts are equal in the limit; the lead changes hands infinitely often; and the proportion of time one side leads is a definite number near one. Three statements, all true, and each of the first two is regularly quoted as though it contradicted another.

What the elementary methods reach #

Set against the analytic theorem, the elementary constructions of the rung below look meagre, and it is worth saying exactly how meagre.

A Euclid-style argument is known for the class $a$ modulo $q$ exactly when $a^2 \equiv 1 \pmod q$ — that is, for the classes that are their own inverse. Modulo 4 that is both classes, which is why the elementary approach looks promising there. Modulo 5 it is 1 and 4 only, and the classes 2 and 3 have no such proof.

The involution condition has a clean reading. A Euclid-style argument works by building a number whose prime factors are constrained, and the constraint available is that a product of primes in a class lands in the product class. To force a factor into the class $a$, the argument needs the class $a$ to be recoverable from the fact that a product of things not in it lands somewhere — and that recovery works only when the class is its own inverse, because then “not in $a$” is closed under multiplication.

The theorem covers every class; the elementary methods cover the involutions. The gap is not a matter of ingenuity: there is a theorem of Murty’s that a Euclid-style argument of the standard shape exists only in the involution case, so the elementary route provably stops where it appears to.

Reading the two figures together #

The bias figure and the class figure are measuring the same primes and they look like they disagree, which is worth resolving explicitly.

At a hundred thousand the class 1 mod 4 holds 4783 primes and the class 3 holds 4808 — a difference of 25 out of 9591, which is a quarter of one per cent. Drawn as two bars they are indistinguishable, and the class figure is right to show them as equal.

Drawn as a difference against the bound, the same 25 is a curve that has been positive nearly the whole way and has wandered as high as forty. The bias figure is right to show a persistent lead.

Nothing has changed but the vertical scale, and the two pictures are the two orders of magnitude the previous sections separate: a bar chart shows the leading term and a difference plot shows the next one. A reader who has both is in a position to hold the theorem and the bias at once; a reader with only one of them will believe whichever it shows.

That is a general hazard with a measured quantity that has a main term. Subtracting the main term is the only way to see the rest, and the moment it is subtracted the picture stops being to scale — so the honest presentation is both, side by side, with the sizes stated.

What the pictures cannot show #

The races are measured to thirty thousand. The first sign change modulo 4 is inside that range and the first modulo 3 is at about $6 \times 10^{11}$, so the second figure shows a bias with no end in sight rather than a bias with no end.

The equal densities are measured to a hundred thousand and agree to within a few per cent. That is consistent with the theorem and is not evidence for it; the theorem is about a limit and any finite count is compatible with a great many limits.

And Dirichlet’s proof is described in one sentence and performed nowhere. It needs the non-vanishing of a family of analytic functions at a point, which is the hard technical step and has no picture at all.

Where the ladder goes next #

Named here as a debt: Chebotarev’s theorem, which is Dirichlet’s with the residue classes replaced by conjugacy classes in a Galois group, and which is the correct general statement this rung is a special case of.

Sideways, the elementary constructions are the rung below, the status of the families nobody can settle is the rung below that, the count the classes divide up is the prime number theorem’s, and the characters the proof runs on are the one-dimensional representations of a commutative group.

Why nobody expects an elementary proof #

It is reasonable to ask whether the analytic proof is merely the one that was found first, and the evidence says otherwise.

There is an elementary proof of the prime number theorem — Selberg and Erdős, 1949 — which was a surprise and which is genuinely elementary in the technical sense of avoiding complex analysis. It is also long, and it does not extend to Dirichlet’s theorem in any useful way.

What is known about the obstruction is this. The analytic proof’s hard step is that a certain function is non-zero at a point, and for characters taking real values only that step is a delicate argument of its own — the possibility being excluded is an exceptional zero, which would correspond to an arithmetic progression genuinely poorer in primes than the others. Nobody can rule that out cheaply, and a cheap argument ruling it out would be the elementary proof.

So the absence is not the absence of a clever rearrangement. It is that the theorem’s content includes ruling out a specific kind of conspiracy among the residue classes, and the only known way to rule it out is analytic.

That is the same shape as the situation on the rung above, where a sieve cannot distinguish two conspiracies it has no data about, and it is worth noticing that both obstructions are about ruling something out rather than about proving something exists.

What is worth carrying away #

A statement about densities and a statement about counts are different statements, and a computation can support one while appearing to refute the other.

The primes are shared equally among the admissible classes and one class leads at almost every bound anybody checks. Both are true, the first is about a ratio and the second about a difference, and the second is a lower-order effect with a cause that can be named.

The habit worth taking is to ask which order of magnitude a claim lives at. Equality in the limit constrains the leading term and says nothing about the next one, so a persistent-looking lead in the data is not evidence against it — and looking for the mechanism behind the lead is more productive than doubting the theorem.

The corollary is about elementary proofs. Euclid’s argument extends to the classes that are their own inverse and provably no further, so the two-century absence of an elementary proof of Dirichlet’s theorem is a fact about the method rather than about anybody’s cleverness. When a method has been characterised, its failure stops being a challenge and becomes information.