To the right, you can see a picture of the Prime Number Theorem. It states that the number of primes up to a real number is asymptotically equal to .
And this was Pafnuty Lvovich Chebyshev who almost managed to prove it around the year 1850. His almost-proof resulted in a theorem named after him.
I was recently trying to understand the proof of Chebyshev’s theorem:
Theorem 1. There are constants such that, for all sufficiently large real numbers X, .Chebyshev’s Theorem
In this post, I will reproduce this proof from [Cheb] together with some comments and tables.
Ben Green’s introductory text on the Prime Number Theorem (PNT) [Green2016] introduces this theorem as a first estimate of the correctness of the PNT with elementary methods. The actual PNT states that and in Theorem 1 can be taken arbitrarily close to 1. For some reason, Green does not tell us the name/author of this theorem but Green tells us why this theorem is interesting:
- the upper bound is saying that
- the lower bound immediately implies the infinitude of primes (and with a much better bound than Euclid’s proof)
- the upper bound implies, in particular, that the density of the primes up to , that is to say , tends to zero as .
But, before one can understand the proof of Chebyshev’s theorem, one will definitely have to understand
Theorem 2: contains a prime factor exactly times. Or, in other words: is the largest power of that divides and is called the p-adic valuation of .Legendre’s Theorem
Now, before talking about a proof of Theorem 2, I would like to state the following
Fun Fact 3: Every prime factor of n! is less than or equal to n.
This follows from the fact that if a prime p divides a product, it must divide at least one of its factors, . In the case of Fun Fact 3 it implies that if a prime divides then it must divide one of the factors .
Now, let’s get back to the proof of Theorem 2: What we want to understand is “how often” a certain prime number divides . And this quantity will be called . Let’s look at an example first: The prime number 2 divides exactly 3 times. According to the formula that we want to prove . The reason why this works is because divides factors (2 divides 2 and 4 in the example). divides factors ( divides only 4 in the example). And so on. Thus, since all numbers that are divisible by are also divisble by , they contribute via both terms of the sum. In our example, the number 4 contributes once via the first term and once via the second term. In total it contributes 2 to which makes sense since it is equal to . This concludes our proof of Theorem 2.
Now that we know Legendre’s Theorem, we can prove the lower bound of Theorem 1: I will reproduce this proof from [Cheb] and add some comments and tables. We will first define a number . We can apply Theorem 2 to obtain . All the terms in this sum are either 0 or 1. This becomes evident by
Lemma 4: For all we have .
Proof: Write . If the fractional part , then , hence . If , then we get .
It is also clear that if this means that and therefore because both fractions (inside the floor brackets) are smaller than one. Now that we know the maximum value of that still contributes something to the sum in we can use this together with Lemma 4 (the fact that all terms in the sum are either zero or one) to obtain the bound .
At the less-or-equal signs we have used:
This yields the lower bound . We claim that this implies for all . This inequality can be checked directly for :
Hence it is sufficient to prove it for . Pick an integer with .
Then , hence . This concludes the proof of the lower bound of Theorem 1.
For the upper bound: Let’s first observe 2 facts about the binomial coefficient :
- : this comes from the binomial formula where we set : .
- N is not divisible by any primes . See Fun Fact 3.
These properties imply that .
Taking the log gives . Using induction we now easily see that .
In fact, this is checked directly for :
For we find .
Now we exploit the fact that is monotonely increasing for . Thus if , then .
In the last step we have only onsidered values of . But since for , the proof is now complete.
Here are some links that I’ve collected on this topic (the first two of which are referenced in this post):
- [Green2016] http://people.maths.ox.ac.uk/greenbj/papers/primenumbers.pdf
- [Cheb] www.fen.bilkent.edu.tr/~franz/nt/cheb.pdf