Skip to content

A Thanksgiving Treat

November 23, 2018
tags: , , , , , ,


Another proof that there are an infinite number of primes of a special form

Cropped from Packard Fellow src

Trevor Wooley is a professor of mathematics at the University of Bristol in the UK.

Today, Ken and I want to say our thanks and share some small amount of fun with you all.

Wooley, a number theorist, is the author of a neat short paper in the Math Monthly. It appeared a while ago, in 2017, but I only saw it today when I looked over some old copies of the Monthly. The copy of the journal was in my Atlanta home.

The Monthly is another item to be thankful for. Since it is a journal the proper style would be to italicize it as American Mathematical Monthly or abbreviate it similarly. But it is such an old and shared friend everyone knows it as the Monthly. It is a great gateway for reading about the essence of research old and new. We are thankful that Ken had a joint paper there earlier this year.

Some Motivations

Wooley’s paper starts out by addressing an open problem that has “officially” been open for about 50 years but may have been thought about by readers of Euclid 2,300 years ago—who knows? Everyone knows how Euclid’s proof of the infinitude of primes works:

  • Suppose {p_1,p_2,\dots,p_k} are all the primes we know.

  • Form {N_k = p_1 \cdot p_2 \cdots p_k + 1}.

  • Define {p_{k+1}} to be the least prime divisor of {N_k}.

  • Then {p_{k+1}} cannot equal any of {p_1,p_2,\dots,p_k} so it is a new prime.

The open problem is,

If we start with {p_1 = 2} and iterate, do we get every prime?

The sequence begins: {p_2 =} the least prime divisor of {2 + 1 = 3}, {p_3 = } the least prime divisor of {2\cdot 3 + 1}, which is {7}. We have hopped over {5}, and it takes awhile to get it:

  • {2\cdot 3 \cdot 7 + 1 = 43 = p_4};

  • {2 \cdot 3 \cdot 7 \cdot 43 + 1 = 1807 = 13 \cdot 139}, so {p_5 = 13};

  • {2 \cdot 3 \cdot 7 \cdot 43 \cdot 13 + 1 = 23479 = 53 \cdot 443}, so {p_6 = 53};

  • {2 \cdot 3 \cdot 7 \cdot 43 \cdot 13 \cdot 53 + 1 = 1244335}, so finally {p_7 = 5}.

As Wooley notes, this the opposite of a computationally efficient procedure for generating primes. Its motivation is really about the effectiveness of modeling aspects of the primes as random processes. Here the next prime to get is {11}, and we expect it to come eventually because each iteration is like a random trial with probability {1/11} of succeeding and we get infinitely many trials. This argument applies to getting every individual prime. But amazingly no one has proved it.

What Wooley does instead is give a different kind of “Euclid proof” in which the attainment of every prime is provable. Here “Euclid proof” means the above process but changing how {N_k} is defined. Here is his main theorem:

Theorem 1 Given {p_1,\dots,p_k}, take {n = p_1\cdots p_k} and instead of using {n+1}, define

\displaystyle N_k = n^{n^n} - 1.

Then the sequence {[p_k]} enumerates the primes in order.

To start off, we have {k = 1}, {p_1 = 2}, and {n = 2}. We get {N_2 = 2^4 - 1 = 15}, and the least prime divisor of {15} is {3}. Then we have {n = 6} and {N_3 = 6^{6^6} + 1}. This is already beastly to compute, but we can note that {6^{46,656}}—or {6} to any power—is always one more than a multiple of {5}, so we know we will get {p_3 = 5}. And so on with {p_4 = 7}, {p_5 = 11}…

Our motivation instead is to facilitate proofs of infinitely many primes that have other properties, such as being in a certain congruence class. We posted about this last July. We think there may be further uses of his theorem and ideas related to the lemma on which it is based.

Main Lemma

Wooley’s lemma works for any integer {n}:

Lemma 2 When {n} is a positive integer the least prime divisor of

\displaystyle n^{n^n}-1

is always the smallest prime not dividing {n}.

We can’t improve on the sprightliness of the proof in Wooley’s paper. Now to get the exhaustive generator, we want to change the words “smallest prime not dividing {n}” to “smallest prime larger than {n}.” This is achieved just by substituting {N = n!} for {n} in the body of the lemma. We get the smallest prime not dividing {n!} which is the same as the smallest prime larger than {n}.

As Wooley also remarks, other formulas besides making a triple power-tower of {n} and subtracting {1} can be made to work. He gives his own thanks to Andrew Booker and Andrew Granville for suggesting:

Lemma 3 When {N} is a positive integer, the least prime divisor of

\displaystyle N!^{N!}-1

is the smallest prime larger than {N}.

A Further Application

The following illustrates the intended use for congruences:

Theorem 4 There are infinitely many primes of the form {4k+3}.

Proof: Suppose there were only finitely many primes of the form {4k+3}. Let {n} be their product. Apply Lemma 3 with {N = n}. Then all prime divisors of {M = n!^{n!} - 1} must be {> n} and hence of the form {4k+1}. Thus {M} too must have the form {4k+1}, which means that {n!^{n!}} must have the form {4k+2}. But this is false for {n > 3}. \Box

Harking back to Wooley’s motivation, this still stops short of enumerating all the primes of the form {4k+3}. But it is a proof of their infinitude.

Open Problems

Can this proof idea be used prove something else? What about primes of the form {6k+1} and so on?

from → All Posts, Ideas, Oldies, primes, Proofs, Teaching
2 Comments leave one →
  1. Craig Alan permalink
    November 24, 2018 8:42 pm

    I found a paper here with an interesting approach to Goldbach’s conjecture:
    https://arxiv.org/abs/1811.02415

    I am curious what you think.

    Craig

    Sent from my Sprint Samsung Galaxy S® 6 edge.

    Reply
    • Luke permalink
      November 26, 2018 12:05 am

      I’m afraid that’s not a proof and there’s nothing in that writeup not already known. It’s using a technique mathematicians would identify as sieving (https://en.wikipedia.org/wiki/Sieve_theory). The problem is that it’s looking at the limit for large N and doesn’t handle the error terms. By “error term”, I’m referring to how (N-1)/3 goes to N/3 as N->inf, and -1/3 would be the error term. The error terms are exactly what makes Goldbach hard: we know on average they are small, but we don’t know how to prove they are always small. The author seems to realize it’s important to be conservative about the direction of the error terms, but he did not close all the gaps related to this. In fact his own chart of P(1-2W) shows his formula is not in fact conservative, and therefore the argument is not complete.

      Reply

Leave a Reply to LukeCancel reply

Discover more from Gödel's Lost Letter and P=NP

Subscribe now to keep reading and get access to the full archive.

Continue reading