Note that log means the natural logarithm
According to Gauss he conjectured this about the distribution of prime numbers when he was a teenager:
Definition of : is the function that counts the number of primes less than x.
It is often stated using asymptotic notation:
Before getting anywhere near a proof of this we will need a tool called Abel's summation formula.
Let be a sequence and let be a differentiable function such that is Riemann integrable. If we define
then we have
Don't worry about the Riemann integral. It is simply a formal definition of the integral concept.
Proof: We will prove this by manipulating the left hand side.
By definition we know:
We can write this as two separate sums:
Now we change it back into one sum and separate the last term of the first sum:
The difference between two function values is the same as the integral of the derivative for the same interval:
Because A(n) equals to A(t) in the interval n to n+1(not considering the end points which do not change the value of the integral) we can write it as part of the integral:
The German mathematician Paul Bachmann introduced this notation in the second volume of his work Analytische Zahlentheorie. Edmund Landau who was also a number theorist adopted the notation and introduced related notations which are known as Landau symbols.
We can understand the notation by using an example. because there exist and such that whenever . We say is bounded by .
Pafnuty Chebyshev, a 19th century russian mathematician, used these two concepts in order to prove important theorems on the distribution of prime numbers.
Definition of : is known as the von Mangoldt function. It is defined as :
One important property of this function follows from the fundamental theorem of arithmetic:
The summatory function is called the Chebyshev function it is denoted by
We are going to apply Abel's lemma to . The reason we apply it to this particular function is it is a differentiable function that has got a relationship to prime numbers via the von Mangoldt function. Applying Abel's lemma for a_n = 1 and f(x) = \log(x) we get:
[x] is the greatest integer function of x. The difference between [x] and x is less than 1 We therefore have:
As 1 and O(log(x)) are bounded by log(x) we finally have:
Returning to the von Mangoldt funtion[edit | edit source]
The connection to the von Mangoldt function goes as follows:
The first step should be pretty obvious. In the second step we rearrange the sums. The number of n less or equal to x dividing d is the greatest integer of or . We can also write this using the Chebyshev function:
Finding a bound for the Chebyshev function[edit | edit source]
But before finding a bound for , we find a bound for a related function which is defined as:
For this he had a really brilliant idea. Recall the binomial coefficient. Here is a formula for the binomial coefficient:
Regarding prime numbers we see that devides every prime number between and n-k. We therefore know:
Because of the binomial expansion of we know:
Taking the logarithm we get:
If we continue adding the ever smaller thetas together we get:
This shows that Theta is bounded by x, . But it doesn't show anything about of which we know that it is bigger than . We can however define in terms of :
As we do not have an infinite sum ( is 0 for arguments smaller than 2 ) we can say the sum is bounded by the largest term:
As the bounding function of the difference is smaller than x we know:
Plugging this into the our equation for the logarithm sum we have:
Dividing this by x removing the bounded terms we end up having:
Implications for the distribution of primes[edit | edit source]
We know that is bounded by x which is equivalent to:
We know that as is bounded by x the first of these to sums will be bounded by :
Each of the logarithms is at least :
We also know that:
Since the prime power components of the sum are bounded by a constant we know:
Now we choose a large number C so that there is a positive constant B so: