There are infinitely many primes

Introduction

The first few prime numbers are

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, …

They're defined as the positive integers that have exactly two positive integer factors (which are themselves and one, of course).

One of the oldest significant mathematical results is that there's an infinite number of primes. It was first proved by Euclid in about 300 BC, in his Elements (book IX, proposition 20).

Over the years, many different proofs of the result have been found. Six of them can be found in Chapter 1 of the third edition of "Proofs from THE BOOK". Three can be found in Chapter 2 of Hardy and Wright's "An Introduction to the Theory of Numbers" (in sections 2.1, 2.4, and 2.6). Three can be found in Chapter 2 of Chaitin's "Meta Math!". Several can be found in the wikipedia primes entry.

For quite a while, I knew of only one proof of the "infinitude of primes", namely Euclid's proof. Over the years, I've come across others, and I've noticed that several of them are really relying on deriving a contradiction from a particular consequence of assuming that there are finitely many primes. That consequence, and various ways of disproving it, are the subject of this essay. I might deal with some of the other proofs in the future.

Starting point

Assume there are only finitely many primes. Call them

2, 3, 5, … p_k

Since every positive integer, other than one, is either itself prime, or a product of primes, we can conclude that every positive integer N can be written in the form

N = 2^n₁ 3^n₂ 5^n₃ … p_k^n_k

where each of n₁, n₂, n₃, … n_k is a non-negative integer.

All of the proofs discussed here will show, in one way or another, that this is impossible.

Euclid's counter example

Euclid's proof that not every integer is of the form

2^n₁ 3^n₂ 5^n₃ … p_k^n_k

is very direct. He simply pointed out that the number

N = 2 • 3 • 5 • … • p_k + 1

can't be of the required form.

Kummer's counter example

In 1878, Kummer pointed out that the number

N = 2 • 3 • 5 • … • p_k − 1

can't be of the required form either.

Other counter examples

And, of course, there's an infinite number of related counter examples. All numbers of the form

N = n • 2 • 3 • 5 • … • p_k ± 1

where n is any positive integer, provide a counter example also.

Unlike Euclid's (and Kummer's) proof, all the remaining proofs won't produce an explicit counter example.

Euler's analytic proof

What I really like about the following proof is that it uses techniques from another area of mathematics, real analysis, to give a short and sweet proof involving infinite sums and convergence. It is true that the proof could be reformulated in terms of inequalities involving finite sums of rational numbers (and from there could be restated purely in terms of finite operations on integers) but it would lose its conceptual simplicity in the process.

Euler's great insight, in my opinion, was to realize that if every number is of the given form, then it would follow that a finite product of convergent geometric series would be equal to the harmonic series. This is impossible because the harmonic series diverges.

Here's some details. By considering all terms resulting from expanding the following product, we have:

(1 + 1/2 + 1/2² + 1/2³ + … )
(1 + 1/3 + 1/3² + 1/3³ + … )
(1 + 1/5 + 1/5² + 1/5³ + … )
…
(1 + 1/p_k + 1/p_k² + 1/p_k³ + … )

≥ (1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + 1/7 + 1/8 + … )

We only need inequality, which is just as well, since proving equality would require proving that prime factorization is unique, which is something we don't need for any of the proofs.

Now, since every prime is ≥ 2, we have that every geometric series in the above product is bounded above by

(1 + 1/2 + 1/2² + 1/2³ + … ) = 2

This immediately implies the inequality

2^k ≥ (1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + 1/7 + 1/8 + … )

Since (1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + 1/7 + 1/8 + … ) = ∞ , we're done.

Another way to think of the result is that Euler showed that the sum of the reciprocals of all numbers of the form

2^n₁ 3^n₂ 5^n₃ … p_k^n_k

is finite, while the sum of the reciprocals of all positive integers is infinite. This can be interpreted to mean that for any collection of primes, "most" positive integers are not products of only those primes.

Thue's counting proof

Like Euler's proof, this proof shows that there must be positive integers that are not of the required form. But, we don't leave the realm of the integers.

This proof starts by looking at the set of integers ranging from 1 up to 2ⁿ. The cardinality of this set is 2ⁿ.

On the other hand, by the finiteness assumption, every integer from 1 to 2ⁿ can be written in the form

2^n₁ 3^n₂ 5^n₃ … p_k^n_k

where each of n₁, n₂, n₃, … n_k ranges from 0 to n.

The cardinality of this set is (n+1)^k.

This means that we must have the inequality

2ⁿ ≤ (n+1)^k for all n.

But this is known to be false for sufficiently large n.

This proof shows that the infinitude of primes follows from the fact that exponential growth out paces polynomial growth.

Chaitin's algorithmic complexity proof

The informal version of Gregory Chaitin's proof can be found in his book "Meta Math!". In short, it takes log N bits of information to represent a "random" integer N, but it only takes k log log N bits to represent N if it's of the form

2^n₁ 3^n₂ 5^n₃ … p_k^n_k

Since log N grows faster than log log N we're done.

When I read this, I thought it would be amusing to restate it as a simple counting argument, and quickly did so: just write N as 2ⁿ, so that log N is log(2ⁿ), and k log log N is log(n^k), and follow your nose. You'll get Thue's proof.

After that, I thought I'd look at Chaitin's original published proof. It appeared as "Appendix 2: An Information-Theoretic Proof That There Are Infinitely Many Primes" in his 1979 paper Toward a mathematical definition of "life". In that paper, Chaitin defines algorithmic entropy H of a positive integer N, and uses various properties, such as "subadditivity of algorithmic entropy" to show that

H(N) ≤ Sum( H(n_j) ) + O(1), from which it follows that

log N + O(log log N) ≤ k[log log N + O(log log log N)];

which gives the the contradiction log N = O(log log N).

The final paragraph of the paper reads as follows "This proof is merely a formalization of the observation that if there were only finitely many primes, the prime factorization of a number would usually be a much more compact representation for it than its base-two numeral, which is absurd. This proof appears, formulated as a counting argument, in Section 2.6 of the 1938 edition of Hardy and Wright [20]; we believe that it is also quite natural to present it in an information-theoretic setting." (italics mine).

I looked in Hardy and Wright, expecting to see Thue's proof, and was pleasantly surprised to find that Chaitin referenced a different counting argument, due to Erdos.

Erdos' counting proof

Look at the set of integers ranging from 1 up to 2²ⁿ. The cardinality of this set is 2²ⁿ.

By the finiteness assumption, every integer from 1 to 2²ⁿ can be written in the form

2^n₁ 3^n₂ 5^n₃ … p_k^n_k

Erdos used the fact that n_i=2m_i+e_i where e_i is 0 or 1 (so that p_i^n_i=(p_i^m_i)²p_i^e_i) to conclude that every integer from 1 to 2²ⁿ can be written as

M² 2^e₁ 3^e₂ 5^e₃ … p_k^e_k

where M ranges from 1 to 2ⁿ, and each of e₁, e₂, e₃, … e_k ranges from 0 to 1.

The cardinality of this set is 2ⁿ 2^k.

This means that we must have the inequality 2²ⁿ ≤ 2ⁿ2^k, ie

2ⁿ ≤ 2^k for all n.

But this is clearly false: just take n=k+1.

Incidentally, there's nothing special about the 2 in either the base or exponent of 2²ⁿ: any integers greater that 1 would also work. Here's how the argument would go with a base of 42 and with a factor of 1729 in the exponent.

Look at the set of integers ranging from 1 up to 42¹⁷²⁹ⁿ. The cardinality of this set is 42¹⁷²⁹ⁿ.

By the finiteness assumption, every integer from 1 to 42¹⁷²⁹ⁿ can be written in the form

2^n₁ 3^n₂ 5^n₃ … p_k^n_k

Use the fact that n_i=1729m_i+e_i where e_i is 0 or 1 or ... or 1728 (so that p_i^n_i=(p_i^m_i)¹⁷²⁹p_i^e_i) to conclude that every integer from 1 to 42¹⁷²⁹ⁿ can be written as

M¹⁷²⁹ 2^e₁ 3^e₂ 5^e₃ … p_k^e_k

where M ranges from 1 to 42ⁿ, and each of e₁, e₂, e₃, … e_k ranges from 0 to 1728.

The cardinality of this set is 42ⁿ 1729^k.

This means that we must have the inequality 42¹⁷²⁹ⁿ ≤ 42ⁿ1729^k, ie

42¹⁷²⁸ⁿ ≤ 1729^k for all n.

But this is clearly false: just take n large enough.

On the other hand, the 2 in the base of 2ⁿ in Thue's proof has to be 2. We're relying on the fact that every prime is greater than or equal to 2.

Concluding words

We've looked at only one approach to proving that there are infinitely many primes. There are several others, including yet another proof due to Euler, in which he showed that the sum of the reciprocals of the primes is infinite.

It turns out that the idea behind Erdos' counting proof can be used to give an alternative proof of Euler's sum of the reciprocals of primes result, and this is just what Erdos did. If you're curious, you can read about it in either Proofs from THE BOOK or in Hardy and Wright's classic number theory book.

Feedback

John Stillwell sent me an email asking "Have you looked at Ribenboim's Little Book of Bigger Primes ?". Err, no, I hadn't. I checked it out, and found out that Thue's name is associated with the counting version of Chaitin's proof, and that Kummer's name was associated with a variation of Euclid's proof. No mention of Erdos' counting argument though. I've modified this essay accordingly.

If you have corrections, additions, modifications, etc please let me know mailto:walterv@gbbservices.com