- A bit of history on the Prime Number Theorem
One of the most fundamental results in mathematics is the Prime Number Theorem, which describes the asymptotic law of the distribution of prime numbers in the integers.
Theorem 1 Let denote the number of primes smaller or equal to a positive integer . Then we have
Roughly speaking, Theorem 1 states that any natural number, taken at random, has probability of being prime and of being composite.
A stronger form of Theorem 1 is the following.
Theorem 2 There exists a constant such that for any we have
Conditionally on the well-known Riemann Hypothesis we have instead that for any ,
Roughly speaking, the above conjecture suggests that the prime numbers should behave as randomly as possible, indeed as a simple random walk process would behave. We will justify better this behaviour later on.
The Prime Number Theorem was conjectured independently by Gauss and Legendre towards the end of the 18 century and was proved independently by Hadamard and de la Vallee Poussin in the year 1896. Their proofs are similar and rely on sophisticated analytic machinery involving complex analysis, which was developed throughout the 19 century by the combined effort of many great mathematicians of that era, including Euler, Chebyshev, and Riemann (to name a few). Historically, this method became known as analytic.
Even though it was believed for a long time not to be possible, more than 50 years after the analytic proof of the Prime Number Theorem was discovered, an elementary proof was found by Erdos and Selberg. In this context, elementary refers to methods that avoid using complex analysis (and the study of the distribution of the zeros of meromorphic extensions of some complex functions) and instead rely only on rudimentary facts from calculus and basic arithmetic identities and inequalities.
- Reformulation of the Prime Number Theorem
Let us now rephrase the statement of the Prime Number Theorem in a way more feasible to an elementary approach. To this aim, we define the function
where when is squarefree and otherwise, where is called the Mobius function and we define to be the number of prime factors of and finally we say that is squarefree when it is not divided by any square of a positive integer number.
We can now rewrite Theorem 1 and Theorem 2 in the following equivalent forms.
Theorem 3 We have
Theorem 4 There exists a constant such that for any we have
Also the previous conjecture on can be restated in the following (almost) equivalent form: for any we have
The above reflects better the aforementioned random walk behaviour of the primes. If we consider as a simple random walk on the integers, with probability to be (when has an even number of prime factors) and probability to be (when has an odd number of prime factors), we have that the discrepancy between the empirical average of and its mean value (the limit being ) is at most the square root of the variance. Indeed, one can show that
for a certain constant .
Let us write to abbreviate the set . Given a finite set and a function , define the Cesaro of over and the logarithmic average of over respectively by
Thus, we would like to show that:
- The distribution law of the number of prime factors
Our final aim is to count the number of prime numbers up to a certain large threshold . Let us first see what we can say about the number of primes up to dividing a fixed integer , i.e.
where we will always indicate a prime number with the letter .
On average over we have
which is efficient only when is much larger than . Thus by dividing through by and considering as tending to infinity, we could conclude that, for a large and “almost all” we have:
A more precise and technical statement is the following. For all there exists such that if we have
where is the set of prime numbers.
- The main idea behind this new proof
The new idea is to compare the average of the Mobius function with dilated averages of the Mobius function itself with primes or almost primes. Those dilated averages are generally defined as the average:
over a finite non-empty set , which will be mainly taken as the set of all multiples of a fixed prime or a fixed almost prime, which in turn is defined as the product of distinct primes.
More specifically, we are looking to estimate the following quantity:
where is a finite set containing either prime numbers or -almost prime numbers. To this aim we can rewrite the last average as
where we used that is finite and that of course
Plugging this in (8) gives
To conclude from here we will need to find suitable sets for which an opportune variation of (7) holds.
- The distribution of the number of divisors of a fixed integer
An important role in this proof of the Prime Number Theorem will be played by a variant of (7), which is provided in the following result.
Theorem 5 Let be finite and non-empty. Then
where is the function .
Proof: Using the Cauchy-Schwarz inequality and expanding the square gives
Since every -th number is divisible by , we have
Similarly, one can verify that
Substituting and into (10) finishes the proof of (9).
In layman’s terms, the previous result says that is good for a variation of (7) to hold if two integers and chosen at random from have a “high likelihood” of being coprime.
The usefulness of the Theorem 5 is to reduce the task of finding sets for which a variation of (7) holds to the easier task of exhibiting sets for which is small.
For example, the initial segment of the set of -almost primes
has this property.
Also note that , as Therefore, we really need to use the logarithmic average to hope to realize variations of (7).
As we already said above, another important task is to find suitable choices of sets for which the right hand side of (9) is small. Those are provided in the following result.
Theorem 6 For all there exist and such that for all and all there exist two finite, non-empty sets with the following properties:
-all elements in are primes larger than and all elements in are a product of distinct primes larger than ;
-the sets and have the same cardinality when restricted to -adic intervals, by which we mean for all ;
– for , where is as in Theorem 5.
We do not insert here the proof of the above result, because it is quite technical. Despite this, it should be remarked that it is a beautiful combinatorial argument, which basically relies on the so called “Chebyshev-type estimates” on the number of prime numbers in long intervals. Those are usually deducted form Stirling’s formula and some double counting-type argument and are employed in the proof of the Theorem 6 to estimate the number of primes in exponentially short intervals, by means of some applications of the pigeon-hole principle.
- The main proof
Fix an arbitrary . Let and be as guaranteed by Theorem 6. Let be an arbitrary even number bigger or equal to and let be any number which the reader should think of as being much larger than . By Theorem 6, we can find two finite and non-empty sets satisfying the properties in Theorem 6. In particular, for , thanks to the last property in Theorem 6, (4) becomes
Since any element has at most prime factors, each of which is bigger than , the asymptotic density of numbers that are not coprime to is very small; in fact it is smaller than . Indeed,
Combining this observation with the multiplicativity of the Mobius function, i.e. whenever and are coprime, we deduce that
Note that for all because consists only of primes, whereas for all because any element in is a product of distinct primes and we choose to be even. Thus, (11) becomes
in the case and
in the case . Finally, using that and have the same size within -adic intervals and that is very close to , we conclude that the expressions and are approximately the same; in fact,
Indeed, observe that if and lie in the same -adic interval, that is , then the averages and differ by a factor of at most . This implies that the logarithmic average of as ranges over differs from the logarithmic average of as ranges over by a factor of at most , because and have the same size within every -adic interval. Since , we deduce (14).
From (12), (13) and (14) it follows that
Since and can be made arbitrarily small, this completes the proof of the Theorem 1.
- Final considerations
The above proof has been taken from the F.K.Richter’s paper “A new elementary proof of the Prime Number Theorem”.
The proof is inspired by recent developments towards the well-known Chowla’s conjecture, which is a sort of high-dimensional generalization of the Prime Number Theorem. It states that for any -tuple of distinct positive integers we have
as . Recently, some advances in its direction have been made by proving some cases of the related Chowla’s logarithmic conjecture. In particular, for certain it was proved that
Some of the ideas, techniques and results contained in this new proof of the Prime Number Theorem have been expanded further in other works of Richter and some of his collaborators to analyse and prove other results in number theory via a dynamical and ergodic point of view.
The main aim of their work is indeed to recast Sarnak’s Mobius disjointness conjecture in a new dynamical framework and provide proofs of several special cases to one of its natural extensions, i.e. to the disjointness of additive and multiplicative semigroup actions.
We remind here that Sarnak’s conjecture states that for a dynamical system , with a compact metric topological space with topological entropy, we need to have
for any , continuous function and considering as tending to infinity. The above is sometimes considered as the property of the Mobius function to being orthogonal to any arithmetic function of low complexity.