You Cannot Do That

Maruti Ram Murty is a famous number theorist at Queen’s University in Kingston, Canada. He is a prolific author of books. His webpage has thumbnails of over a dozen. He has an Erdős number of 1 from two papers—very impressive.

Today Ken and I want to talk about a not-so-recent result of his that is also a “lower bound” type result.

Murty’s theorem in question is referenced in his 2006 paper with Nithum Thain:

Theorem 1 A ‘Euclidean’ proof exists to show there are infinitely many primes congruent to modulo if and only if

What he proves essentially is a “lower bound proof.” This theorem gives a limit to the famous Euclidean proof method showing an infinite number of primes. Let’s take a look at it.

Dirichlet’s Theorem and Euclidean Proofs

Say that a residue modulo is abundant provided there are infinitely many primes congruent to modulo . Then must be relatively prime to , so at most residues can be abundant. Gustav Dirichlet proved in 1837 that all of those are:

Theorem 2 For all the number of residue classes that are abundant is .

So why do we care about “Euclidean” proofs? Dirichlet’s proof uses complex analysis—see this for example. As with the Prime Number Theorem there has long been a feeling that the natural numbers should divulge their secrets by more “elementary” means. Atle Selberg found analysis-free proofs of both theorems—see our discussion here. Opinions remain that the structures involved in these and similar proofs do not shed more light on the structure of the primes.

What is an appropriate level of proof complexity? This is subjective. What we can do is enumerate techniques that everyone agrees convey numerical beauty. Among them are quadratic reciprocity (QR) and cyclotomic theory (CT), albeit they hail from the time of Leonhard Euler and Adrien-Marie Legendre and Carl Gauss rather than Euclid. Indeed, what Gauss considered his nicest proof of QR used CT. With that in mind, the following arguments are considered “Euclidean” (we follow these notes by Keith Conrad):

Theorem 3 For every , the residue class modulo is abundant.

Proof Sketch: Take to be the -th cyclotomic polynomial. The CT theorems we lean on are that for every , and every divisor of either divides or is congruent to modulo . This first gives us the fact of having some prime in that residue class. Now suppose were all such primes and consider some prime divisor of where . Then cannot be a divisor of nor any of because by the first fact. This is the echo of Euclid’s proof. The echo is focused by the second fact giving . So must be a prime in the residue class other than , which gives us the “Euclidean” conclusion that the class is abundant.

Theorem 4 The residue classes modulo are all abundant.

Proof Sketch: For we note that is prime and suppose is the product of all primes in that class. We use the cyclotomic polynomial with giving . Divisors of are hence either or modulo . However, itself is so it cannot have all its prime divisors be , so some dividing must be , but it cannot be any of the , so again we have the “Euclidean” contradiction to those being all the primes in that class.

For or we note that again the residue class is immediately populated and suppose is the product of all its prime members. We use the polynomial value instead. If divides then , so is a quadratic residue modulo . This is either or , and QR theory (noting ) tells us in either case that must be or modulo . The final observation is that since and are both , we have , so . Thus needs to have a prime divisor that is but then by QR we must have without being any of the . Once again this is the Euclidean contradiction.

That “final observation” is what Murty showed—perhaps surprisingly—to be necessary in order to find a suitable polynomial in to begin with. For we get all classes but for , for instance, only , , and (besides ) obey Murty’s criterion. To prove more classes abundant we want to widen the scope of the proofs.

A Weak Version Of Dirichlet’s Theorem

We connect Dirichlet’s Theorem to the famous conjecture by Christian Goldbach that every even number from 4 onward is the sum of two primes. A straightforward sieve argument implies that at least of the even integers can be written as the sum of two primes, but much stronger is known. This 2007 paper by Andrew Granville cites a claim to show that at most of the even integers up to are exceptions, though its author, János Pintz, has only recently released a long proof of as a stepping-stone. Conditioned on the Generalized Riemann Hypothesis, Daniel Goldston improved the bound of Godfrey Hardy and John Littlewood to .

There are however explicitness issues with the constants involved in all unconditional estimates sharper than divided by a polynomial in . None of the proofs is “short.” Hence we’ll say “most” to mean an intuitively provable bound on the number of Goldbach exceptions such that is . Here is our main observation:

Suppose that most even numbers are the sum of two primes. Then there is a short proof that at least residues are abundant.

Let’s explain this statement. First it is not exactly a theorem. Why not? Even granting our meaning of (a short proof of) “most” the conclusion is still subjective. But we can turn the subjectivity to advantage by viewing the statement this way:

Any simple proof of “most” for Goldbach must show that many residue classes contain an infinite number of primes.

Our first point is that we get more than the number of abundant classes from Murty’s criterion. The latter is where is the number of distinct prime factors of and is or or depending on the power of dividing —in all events this number is . We pay a price of explicitness, however: we may not know which classes are abundant.

Theorem 5 Suppose that most even numbers are the sum of two primes. Let be the number of residue classes modulo that are abundant. Then

Proof: Suppose for contradiction that . Then there is some even residue that is not of the form for abundant residues and ( included). Let bound the size of any prime in the non-abundant residues. Then for any even number and primes () allowed such that

at least one of or must come from a non-abundant residue class and hence be . Thus as , the set

has at most members that can be expressed as sums of primes. Hence the density of Goldbach exceptions up to is bounded below by , in violation of the most-Goldbach theorem. Thus .

For we get that the minimum is so we get both and without needing QR. For and however we only get so all but one the possible residue classes again are abundant. Clearly the bound gets worse as we more along. Oh well. But we can still try to improve it.

We do note, however, that the bound we get from our approach is better than any from Euclidean methods for modulo that are prime. By Murty’s theorem it follows that for a prime there are only two residue classes that are provable via the Euclidean method: these are . From estimates noted above, our bounds are better as grows for any kind of .

Further Elementary Inferences

In some special cases we can make further inferences from the “most” property of Goldbach. Let’s look at . Then there are four residue classes but we still only get . So we miss one. But we can do better. The residue classes are . The only way to get by summing two of them is . The only way to get is summing the other two, . Hence if, say, were not abundant, say , then only finitely many even numbers could be sums of two primes, violating the “most Goldbach” property.

The case uses the symmetry . Taking gives which just satisfies Theorem 5. However, a set of residues will yield two pairs summing to the same value—meaning not enough pairs to cover the congruences of even numbers modulo —unless the three excluded values hit each of the following eight equations viewed as triples:

An inspection shows that there is no hitting set of size 3, so we get that at least classes are abundant. We could try further to argue the way we did with but it does not work: if excludes, say, and (or any of the other three pairs summing to ) then the remaining six residues cover all even-number congruences. Thus getting abundant residues is the most for our style of argument thus far.

Are there possible further improvements? Perhaps a way to leverage the tighter bounds on the density of the Goldbach exception set?

We close by noting one other quirk of Dirichlet’s Theorem. If we are given a residue and could always guarantee constructing one prime in some other residue then we could construct infinitely many in . Namely, suppose we had constructed so far. Choose such that for each , . Now take and . The we construct from our assumption is bigger than any but still congruent to modulo , so we can add it to our set and continue.

Thus if what one might call “Dirichlet-one” is constructive then the full Dirichlet Theorem becomes elementary in a clear sense. Indeed, we get the next prime explicitly, not as an unspecified divisor. This connection raises some hope of sharper estimates that play off certain residues having zero primes rather than finitely many, though they are not immediately to hand.

Open Problems

Can we improve the above method to prove more than a square-root bound? It would be neat if we could show that more is true. There are further ideas that Ken and I are thinking about—more in the future.