You Cannot Do That

Gödel’s Lost Letter and P=NP 2018-08-02

How hard is it to prove certain theorems?

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 ${k}$ modulo ${m}$ if and only if
$\displaystyle k^{2} \equiv 1 \pmod m.$

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 ${k}$ modulo ${m}$ is abundant provided there are infinitely many primes congruent to ${k}$ modulo ${m}$ . Then ${k}$ must be relatively prime to ${m}$ , so at most ${\phi(m)}$ residues can be abundant. Gustav Dirichlet proved in 1837 that all of those are:

Theorem 2 For all ${m}$ the number of residue classes that are abundant is ${\phi(m)}$ .

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 ${m \geq 2}$ , the residue class ${1}$ modulo ${m}$ is abundant.

Proof Sketch: Take ${\Phi_m}$ to be the ${m}$ -th cyclotomic polynomial. The CT theorems we lean on are that for every ${n \geq 1}$ , ${\Phi_m(n) \equiv 1 \pmod{n}}$ and every divisor of ${\Phi_m(n)}$ either divides ${m}$ or is congruent to ${1}$ modulo ${m}$ . This first gives us the fact of having some prime in that residue class. Now suppose ${p_1,p_2,\dots,p_r}$ were all such primes and consider some prime divisor ${p}$ of ${N = \Phi_m(n)}$ where ${n = m p_1 p_2 \cdots p_r}$ . Then ${p}$ cannot be a divisor of ${m}$ nor any of ${p_1,p_2,\dots,p_r}$ because ${N \equiv 1 \pmod{n}}$ by the first fact. This is the echo of Euclid’s proof. The echo is focused by the second fact giving ${p \equiv 1 \pmod{m}}$ . So ${p}$ must be a prime in the residue class other than ${p_1,p_2,\dots,p_r}$ , which gives us the “Euclidean” conclusion that the class is abundant. $\Box$

Theorem 4 The residue classes ${k = 3,5,7}$ modulo ${8}$ are all abundant.

Proof Sketch: For ${k = 5}$ we note that ${5}$ is prime and suppose ${p_1 p_2 \cdots p_r}$ is the product of all primes in that class. We use the cyclotomic polynomial ${\Phi_4(n) = n^2 + 1}$ with ${n = 2 p_1 \cdots p_r}$ giving ${N}$ . Divisors of ${N}$ are ${\equiv 1 \pmod 4}$ hence either ${\equiv 1}$ or ${\equiv 5}$ modulo ${8}$ . However, ${N}$ itself is ${\equiv 5 \pmod{8}}$ so it cannot have all its prime divisors ${p}$ be ${\equiv 1}$ , so some ${p}$ dividing ${N}$ must be ${\equiv 5 \pmod{8}}$ , but it cannot be any of the ${p_1,\dots,p_r}$ , so again we have the “Euclidean” contradiction to those being all the primes in that class.

For ${k = 3}$ or ${7}$ we note that again the residue class is immediately populated and suppose ${n = p_1 p_2 \cdots p_r}$ is the product of all its prime members. We use the polynomial value ${N = n^2 - k + 5}$ instead. If ${p}$ divides ${N}$ then ${n^2 \equiv (5 - k) \pmod{p}}$ , so ${(5 - k)}$ is a quadratic residue modulo ${p}$ . This is either ${+2}$ or ${-2}$ , and QR theory (noting ${k \equiv 3 \pmod{4}}$ ) tells us in either case that ${p}$ must be ${\equiv 1}$ or ${\equiv k}$ modulo ${8}$ . The final observation is that since ${3^2}$ and ${7^2}$ are both ${\equiv 1 \pmod{8}}$ , we have ${n^2 \equiv 1 \pmod{8}}$ , so ${N \equiv (6-k) \equiv k \not\equiv 1 \pmod{8}}$ . Thus ${N}$ needs to have a prime divisor ${p}$ that is ${\not\equiv 1 \pmod{8}}$ but then by QR we must have ${p \equiv k \pmod{8}}$ without being any of the ${p_1,\dots,p_r}$ . Once again this is the Euclidean contradiction. $\Box$

That “final observation” is what Murty showed—perhaps surprisingly—to be necessary in order to find a suitable polynomial in ${n}$ to begin with. For ${m = 8}$ we get all classes but for ${m = 12}$ , for instance, only ${5}$ , ${7}$ , and ${11}$ (besides ${1}$ ) 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 ${1/4}$ 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 ${O(x^{2/3})}$ of the even integers up to ${x}$ are exceptions, though its author, János Pintz, has only recently released a long proof of ${O(x^{0.72})}$ as a stepping-stone. Conditioned on the Generalized Riemann Hypothesis, Daniel Goldston improved the bound of Godfrey Hardy and John Littlewood to ${\tilde{O}(x^{1/2})}$ .

There are however explicitness issues with the constants involved in all unconditional estimates sharper than ${x}$ divided by a polynomial in ${\log x}$ . None of the proofs is “short.” Hence we’ll say “most” to mean an intuitively provable bound ${f(x)}$ on the number of Goldbach exceptions such that ${\tilde{O}(f(x))}$ is ${o(x)}$ . 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 ${\approx \sqrt{m}}$ 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 ${a2^r}$ where ${r}$ is the number of distinct prime factors of ${m}$ and ${a}$ is ${0.5}$ or ${1}$ or ${2}$ depending on the power of ${2}$ dividing ${m}$ —in all events this number is ${m^{o(1)}}$ . 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 ${d}$ be the number of residue classes modulo ${m}$ that are abundant. Then
$\displaystyle d + \binom{d}{2} \ge \frac{m-1}{2}.$

Proof: Suppose for contradiction that ${d + \binom{d}{2} < \frac{m-1}{2}}$ . Then there is some even residue ${k < m}$ that is not of the form ${i+j}$ for abundant residues ${i}$ and ${j}$ ( ${i=j}$ included). Let ${B}$ bound the size of any prime in the non-abundant residues. Then for any even number ${e}$ and primes ${p,q}$ ( ${p = q}$ ) allowed such that

$\displaystyle e > 2B, \qquad e \equiv k \pmod{m}, \qquad e = p + q,$

at least one of ${p}$ or ${q}$ must come from a non-abundant residue class and hence be ${\leq B}$ . Thus as ${x \rightarrow \infty}$ , the set

$\displaystyle S_x = \{e: 2B < e < x, e \equiv k \pmod{m}\}$

has at most ${O(Bm x/\log(x))}$ members that can be expressed as sums of primes. Hence the density of Goldbach exceptions up to ${x}$ is bounded below by ${(1/m) - o(x)}$ , in violation of the most-Goldbach theorem. Thus ${d + \binom{d}{2} \geq \frac{m-1}{2}}$ . $\Box$

For ${m = 6}$ we get that the minimum ${d}$ is ${d = 2}$ so we get both ${k = 1}$ and ${k = 5}$ without needing QR. For ${m = 8}$ and ${m = 10}$ however we only get ${d = 3}$ 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 ${m}$ that are prime. By Murty’s theorem it follows that for a ${m}$ prime there are only two residue classes that are provable via the Euclidean method: these are ${\pm 1}$ . From estimates noted above, our bounds are better as ${m}$ grows for any kind of ${m}$ .

Further Elementary Inferences

In some special cases we can make further inferences from the “most” property of Goldbach. Let’s look at ${m=12}$ . Then there are four residue classes but we still only get ${d=3}$ . So we miss one. But we can do better. The residue classes are ${1,5,7,11}$ . The only way to get ${4 \pmod 12}$ by summing two of them is ${5 + 11}$ . The only way to get ${8}$ is summing the other two, ${1 + 7}$ . Hence if, say, were not abundant, say ${11}$ , then only finitely many even numbers ${\equiv 4 \pmod{12}}$ could be sums of two primes, violating the “most Goldbach” property.

The case ${m = 30}$ uses the symmetry ${(m,a) = 1 \iff (m,m-a) = 1}$ . Taking ${d = 5}$ gives ${5 + \binom{5}{2} = 15}$ which just satisfies Theorem 5. However, a set ${R}$ of ${5}$ residues will yield two pairs summing to the same value—meaning not enough pairs to cover the ${15}$ congruences of even numbers modulo ${30}$ —unless the three excluded values hit each of the following eight equations viewed as triples:

$\displaystyle \begin{array}{rclcrcl} 1 + 1 &=& 13 + 19 & ~ & 29 + 29 &=& 11 + 17 \\ 7 + 7 &=& 1 + 13 & ~ & 23 + 23 &=& 17 + 29 \\ 11 + 11 &=& 23 + 29 & ~ & 19 + 19 &=& 1 + 7\\ 13 + 13 &=& 7 + 19 & ~ & 17 + 17 &=& 11 + 23 \end{array}$

An inspection shows that there is no hitting set of size 3, so we get that at least ${d \geq 6}$ classes are abundant. We could try further to argue the way we did with ${m = 12}$ but it does not work: if ${R}$ excludes, say, ${7}$ and ${23}$ (or any of the other three pairs summing to ${30}$ ) then the remaining six residues cover all even-number congruences. Thus getting ${6}$ 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 ${k \pmod{m}}$ and could always guarantee constructing one prime ${p}$ in some other residue ${k' \pmod{m'}}$ then we could construct infinitely many in ${k \pmod{m}}$ . Namely, suppose we had constructed ${p_1,\dots,p_r}$ so far. Choose ${\ell}$ such that ${m^\ell > p_i}$ for each ${i}$ , ${1 \leq i \leq r}$ . Now take ${a' = a + m^{\ell}}$ and ${m' = m^{\ell+1}}$ . The ${p}$ we construct from our assumption is bigger than any ${p_i}$ but still congruent to ${a}$ modulo ${m}$ , 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 ${p}$ 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.