Monday, May 01, 2023

There are an infinite number of proofs that there are an infinite number of primes

In the last few years there have been four papers that prove the primes are infinite using some number theory and some Ramsey Theory. The papers are:

Van der Waerden and the primes by Alpoge. See here or here.

Squares in arithmetic progression and infinitely many primes by Granville. See here or here.

Fermat's last theorem implies the infinitude of primes by Elsholtz. See here or here.

Fermat's last theorem, Schur's theorem (in Ramsey Theory), and the infinitude of the primes by Gasarch See here and here.

(I included the arxiv version and the doi pointer.)

We also note that

1) Mestrovic has collected up 183 proofs that the primes are infinite, see here. Some of them are similar so if you mod out by similarity you would get fewer proofs. How many you get depends on your criteria for similarity. This comment applies to other theorems that have many proofs. 

2) Quanta recently published an article about the fact that there are an so many proofs, though highlighting the four mentioned above. See here. (This might be behind a paywall.) 

This raises the obvious question:

Why are there so many proofs that the primes are infinite? 

Some thoughts

1) Which other theorems have many proofs?

a) The Pythagorean Theorem. See here for the claim that there are 371 proofs. There is a recent claim of a proof using trigonometry here (this was thought to be impossible since it would involve a circular argument). 

b) According to Wikipedia (see here) The law of quadratic reciprocity has 240  proofs.  This paper here has some of them. That paper also shows 

QR IMPLIES primes infinite.

 Actually more: QR IMPLIES  primes \(\equiv 4 \pmod 5\) is infinite.

c) \(\sqrt 2\) is irrational has many proofs. I can't find a clean reference that states there are many proofs---if you know one, leave a comment. Wikipedia (see here) has five proofs, though there are many more. 

d) There is a mathoverflow post about theorems with many proofs here. I had thought only easy theorems had many proofs; however, there are several hard ones on this list. 

2) Primes are so basic that many parts of math can be used to proof they are infinite.

3) WHY do people do these proofs? For the four papers listed above, and likely for many of the other proofs,  the proof that primes are infinite is  a springboard to other questions or concepts. We look at those four papers: 

a) Alpoge's showed Van Der Waerden's theorem and Unique factorization IMPLIES primes infinite. Alpoge didn't use this as a springboard to other questions, but is amused that VDW can be used to prove primes infinite. I will note that the proof made me realize (a)  the proof of Unique Factorization does NOT use that primes are infinite, and (b) ANY integral domain with Unique Factorization has an infinite number of primes. 

b) Granville's showed VDW's Theorem and also a result of Fermat that there cannot be four squares in arithmetic progression IMPLIES primes infinite. He then uses this as a springboard to talk  about other interactions between Ramsey Theory and Number Theory.  Let Q(N) be the max number of squares in arithmetic sequence of length N. Find upper and lower asy bounds on Q(N). From Szemeredi's theorem (which is part of Ramsey theory) Szemeredi himself showed that for all \(\delta>0, Q(N) < \delta N\). Granville's paper shows how to get this result from a corollary to Faltings theorem. He also notes that better is known: \(Q(N) < N^{3/5 + \epsilon}\). 

c) Elsholtz showed Schur's theorem (for all c there is an S=S(c) such that for all c-colorings of {1,...,S} there exists x,y,z the same color such that x+y=z) and FLT (the n=3 case or n=4 case) IMPLIES primes infinite. He then looks at various INFINITE Ramsey Theorems that imply the primes are infinite.

d) Gasarch's proof is identical to Elsholtz. He then looks at (1) for domains with a finite number of primes, what goes wrong? (2) when does the proof apply to other integral domains? The last question involves looking at variants of FLT some of which are open questions. 

4) Gasarch also wondered about the following (though its not in his paper). The four papers above, and also other proofs that the primes are infinite, are of the form 

IMPLIES Primes are infinite

Are we really using A? How to pin this down? Find a logical system L such that 

1) From L one can show A IMPLIES Primes are infinite

2) From L one CANNOT prove Primes are infinite. (You may need some hardness assumption)

One can also examine this kind of question for other theorems like sqrt(2) is irrational. 

I have shown this to several people and am told its not doable. Oh well. 

I had a prior blog on this, after I saw Alpoge's proof,  see here.

ADDED LATER: a commenter left a link to a math overflow page that has information on the reverse mathematics of Euclid's theorem that the primes are infinite. The link is here.


5) USUALLY mathematicians want to (or should want to) find EASIER proofs of HARD theorems. 

For some of the proofs that primes are infinite, QR, \(\sqrt 2\) irrational, some other theorems that have many proofs, mathematicians want to find HARD proofs of EASY theorems. 





9 comments:

  1. reverse mathematics and complexity theory version of it.

    ReplyDelete
  2. I am not sure what this comment means. I think you are saying that my goal with L is in the realm of Reverse Mathematics. The classes RCA_0 etc defined in Reverse Mathematics are WAY ABOVE the level I am talking about. I've asked people in Rev. Math. and they tell me that any system strong enough to prove the implication is likely strong enough to prove Primes Infinite outright. I've also thought about complexity versions like a proof that there are \ge n primes requires say 2^n steps where the relevant implication takes poly(n) steps. I suspect that that is also not doable. ANYWAY, please clarify your comment.

    ReplyDelete
  3. https://mathoverflow.net/questions/319686/reverse-mathematics-of-euclids-theorem

    ReplyDelete
  4. There are many proofs, but how many of them are the same or based on the same idea? For example, Keith Conrad argued in his write-up that Furstenberg's proof is based on the same idea as Euclid's proof: https://kconrad.math.uconn.edu/blurbs/ugradnumthy/primestopology.pdf

    ReplyDelete
  5. Re: "ANY integral domain with Unique Factorization has an infinite number of primes." An integral domain is either a field, in which case the zero ideal is the only prime ideal, or it has infinitely many prime ideals.
    I wonder if unique factorization can be relaxed in that proof since in general rings of integers, we don't have unique factorization, only unique factorization of ideals into prime ideals.

    ReplyDelete
  6. Proofs are only a path between the axioms and the theorem to be proved on a "proof system digraph"; as in real life it is not surprising that there are arbitrarily long paths to get to the goal :-))

    ReplyDelete
  7. When I was an undergrad, I misremembered Euclid's proof as "Let N be the product of all primes p_i. Then for all i, N is congruent to 1 (mod p_i). So N is prime." (Which is wrong; N is only guaranteed to have a new prime factor.)

    I then thought, huh, for all i, N is congruent to -1 (mod p_i), and so it sort of seemed like N and N-2 must be twin primes.

    I asked a TA about this, who reminded me of the actual Euclid proof. D'oh!

    ReplyDelete
  8. Quanta Magazine is funded by the Simons Foundation and has no paywall.

    ReplyDelete