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.

Abel's summation formula[edit | edit source]

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:

Big O notation[edit | edit source]

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.Big-O-notation.png We can understand the notation by using an example. because there exist and such that whenever . We say is bounded by .

Chebyshev[edit | edit source]


Pafnuty Chebyshev, a 19th century russian mathematician, used these two concepts in order to prove important theorems on the distribution of prime numbers.

von Mangoldt function[edit | edit source]

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

Applying Abel's lemma[edit | edit source]

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: