Chebyshev

Note that log means the natural logarithm

According to Gauss he conjectured this about the distribution of prime numbers when he was a teenager:

${\displaystyle \lim _{x\to \infty }{\frac {\pi (x)}{x/\log(x)}}=1,}$

Definition of ${\displaystyle \pi (x)}$: ${\displaystyle \pi (x)}$ is the function that counts the number of primes less than x.

It is often stated using asymptotic notation:

${\displaystyle \pi (x)\sim {\frac {x}{\log x}}.\!}$

Before getting anywhere near a proof of this we will need a tool called Abel's summation formula.

Abel's summation formula

Let ${\displaystyle (a_{n})_{n\in \mathbb {N} }}$ be a sequence and let ${\displaystyle f:\mathbb {R} \to \mathbb {R} }$ be a differentiable function such that ${\displaystyle f'}$ is Riemann integrable. If we define

${\displaystyle A(x):=\sum _{1\leq n\leq x}a_{n}}$,

then we have

${\displaystyle \sum _{1\leq n\leq x}a_{n}f(n)=A(x)f(x)-\int _{1}^{x}A(t)f'(t)dt}$.

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:

${\displaystyle \sum _{1\leq n\leq x}a_{n}f(n)=\sum _{1\leq n\leq x}(A(n)-A(n-1))f(n)}$

We can write this as two separate sums:

${\displaystyle =\sum _{1\leq n\leq x}A(n)f(n)-\sum _{0\leq n\leq x-1}A(n)f(n+1)=\sum _{1\leq n\leq x}A(n)f(n)-\sum _{1\leq n\leq x-1}A(n)f(n+1)}$

Now we change it back into one sum and separate the last term of the first sum:

${\displaystyle =\sum _{1\leq n\leq x-1}A(n)(f(n)-f(n+1))+A(x)f(x)}$

The difference between two function values is the same as the integral of the derivative for the same interval:

${\displaystyle =\sum _{1\leq n\leq x-1}A(n)\left(-\int _{n}^{n+1}f'(t)dt\right)+A(x)f(x)}$

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:

${\displaystyle \sum _{1\leq n\leq x}a_{n}f(n)=A(x)f(x)-\int _{1}^{x}A(t)f'(t)dt}$

Big O notation

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. ${\displaystyle f(x)=O(g(x))}$ because there exist ${\displaystyle c}$ and ${\displaystyle x_{0}}$ such that ${\displaystyle |f(x)|\leq |cg(x)|}$ whenever ${\displaystyle x\leq x_{0}}$. We say ${\displaystyle f(x)}$ is bounded by ${\displaystyle g(x)}$.

Chebyshev

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

Definition of ${\displaystyle \Lambda (x)}$: ${\displaystyle \Lambda (n)}$ is known as the von Mangoldt function. It is defined as :

${\displaystyle \Lambda (n)={\begin{cases}\log p&{\text{if }}n=p^{k}{\text{ for some prime }}p{\text{ and integer }}k\geq 1,\\0&{\text{otherwise.}}\end{cases}}}$

One important property of this function follows from the fundamental theorem of arithmetic:

${\displaystyle \log(n)=\sum _{d\mid n}\Lambda (d)}$

The summatory function is called the Chebyshev function it is denoted by ${\displaystyle \psi (x)}$

Applying Abel's lemma

We are going to apply Abel's lemma to ${\displaystyle \sum _{n\leq x}\log(n)}$. 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:

${\displaystyle \sum _{n\leq x}\log(n)=[x]*\log(x)-\int _{1}^{x}{\frac {[t]}{t}}dt}$

[x] is the greatest integer function of x. The difference between [x] and x is less than 1 We therefore have:

${\displaystyle \sum _{n\leq x}\log(n)=(x+O(1))*\log(x)-\int _{1}^{x}{\frac {t+O(1)}{t}}dt}$

${\displaystyle \sum _{n\leq x}\log(n)=x\log(x)+O(\log(x))-x+1-\int _{1}^{x}{\frac {O(1)}{t}}dt}$

${\displaystyle \sum _{n\leq x}\log(n)=x\log(x)+O(\log(x))-x+1+O(\log(x))}$

As 1 and O(log(x)) are bounded by log(x) we finally have:

${\displaystyle \sum _{n\leq x}\log(n)=x\log(x)-x+O(\log(x))}$

Returning to the von Mangoldt funtion

The connection to the von Mangoldt function goes as follows:

${\displaystyle \sum _{n\leq x}\log(n)=\sum _{n\leq x}\sum _{d\mid n}\Lambda (d)=\sum _{d\leq x}\Lambda (d)\sum _{n\leq x;d\mid n}1=\sum _{d\leq x}\Lambda (d)*({\frac {x}{d}}+O(1))}$

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 ${\displaystyle {\frac {x}{d}}}$ or ${\displaystyle {\frac {x}{d}}+O(1)}$. We can also write this using the Chebyshev function:

${\displaystyle \sum _{d\leq x}\Lambda (d)*{\frac {x}{d}}+\psi (x)*O(1)}$

Finding a bound for the Chebyshev function

But before finding a bound for ${\displaystyle \psi (x)}$, we find a bound for a related function ${\displaystyle \Theta (x)}$ which is defined as:

${\displaystyle \Theta (x)=\sum _{p\leq x}\log(p)}$

For this he had a really brilliant idea. Recall the binomial coefficient. Here is a formula for the binomial coefficient:

${\displaystyle {\binom {n}{k}}={\frac {n!}{k!\,(n-k)!}}\quad {\text{for }}\ 0\leq k\leq n,}$

Regarding prime numbers we see that ${\displaystyle {\binom {n}{k}}}$ devides every prime number between and n-k. We therefore know:

${\displaystyle \prod _{n

Because of the binomial expansion of ${\displaystyle (1+1)^{2}n}$ we know:

${\displaystyle {\binom {2n}{n}}\leq (1+1)^{2n}}$

${\displaystyle \prod _{n

Taking the logarithm we get:

${\displaystyle \sum _{n

${\displaystyle \Theta (2n)-\Theta (n)\leq 2n*\log(2)}$

${\displaystyle \Theta (n)-\Theta (n/2)\leq n*\log(2)}$

${\displaystyle \Theta (n/2)-\Theta (n/4)\leq n/2*\log(2)}$

If we continue adding the ever smaller thetas together we get:

${\displaystyle \Theta (2n)\leq 4n*\log(2)}$

This shows that Theta is bounded by x, ${\displaystyle \Theta (x)=O(x)}$. But it doesn't show anything about ${\displaystyle \psi (x)}$ of which we know that it is bigger than ${\displaystyle \Theta (x)}$. We can however define ${\displaystyle \psi (x)}$ in terms of ${\displaystyle \Theta (x)}$:

${\displaystyle \psi (x)=\sum \Theta ({\sqrt[{n}]{x}})}$

${\displaystyle \psi (x)=\Theta (x)+\sum _{n\geq 2}\Theta ({\sqrt[{n}]{x}})}$

${\displaystyle \psi (x)\leq \Theta (x)+\sum _{n\geq 2}{\sqrt[{n}]{x}}*\log({\sqrt[{n}]{x}})}$

${\displaystyle \psi (x)\leq \Theta (x)+\sum _{n\geq 2}{\frac {1}{n}}*{\sqrt[{n}]{x}}*\log(x)}$

As we do not have an infinite sum ( ${\displaystyle \Theta (x)}$ is 0 for arguments smaller than 2 ) we can say the sum is bounded by the largest term:

${\displaystyle \psi (x)=\Theta (x)+O({\sqrt {x}}*\log(x))}$

As the bounding function of the difference is smaller than x we know:

${\displaystyle \psi (x)=O(x)}$

Plugging this into the our equation for the logarithm sum we have:

${\displaystyle \sum _{n\leq x}\log(n)=\sum _{d\leq x}\Lambda (d)*{\frac {x}{d}}+O(x)=x\log(x)-x+O(\log(x))}$

Dividing this by x removing the bounded terms we end up having:

${\displaystyle \sum _{d\leq x}{\frac {\Lambda (d)}{d}}=\log(x)+O(1)}$

Implications for the distribution of primes

We know that ${\displaystyle \Theta (x)}$ is bounded by x which is equivalent to:

${\displaystyle \Theta (x)\leq Kx}$

${\displaystyle \sum _{p\leq {\sqrt {x}}}\log(p)+\sum _{{\sqrt {x}}\leq p\leq x}\log(p)\leq Kx}$

We know that as ${\displaystyle \Theta (x)}$ is bounded by x the first of these to sums will be bounded by ${\displaystyle {\sqrt {(}}x)}$:

${\displaystyle \sum _{{\sqrt {x}}\leq p\leq x}\log(p)\leq Kx+O({\sqrt {x}})}$

Each of the logarithms is at least ${\displaystyle {\frac {1}{2}}\log(x)}$:

${\displaystyle {\frac {1}{2}}\log(x)*(\pi (x)-\pi ({\sqrt {x}}))\leq Kx+O({\sqrt {x}})}$

${\displaystyle {\frac {1}{2}}\log(x)*(\pi (x)-O({\sqrt {x}}))\leq Kx+O({\sqrt {x}})}$

${\displaystyle {\frac {1}{2}}\log(x)*(\pi (x))\leq Kx+O({\sqrt {x}}*\log(x))}$

${\displaystyle \pi (x)\leq {\frac {Kx}{\log(x)}}+O({\sqrt {x}})}$

${\displaystyle \pi (x)\leq {\frac {Kx}{\log(x)}}}$

We also know that:

${\displaystyle \sum _{p\leq x}{\frac {\Lambda (p)}{p}}={\frac {\log(x)}{x}}+O(1)}$

Since the prime power components of the sum are bounded by a constant we know:

${\displaystyle \sum _{p\leq x}{\frac {\log(p)}{p}}={\frac {\log(x)}{x}}+O(1)}$

Now we choose a large number C so that there is a positive constant B so:

${\displaystyle \sum _{{\frac {x}{C}}

${\displaystyle {\frac {\log({\frac {x}{C}})}{\frac {x}{C}}}*(\pi (x)-\pi ({\frac {x}{C}}))\geq B}$

${\displaystyle \pi (x)-\pi ({\frac {x}{C}})\geq {\frac {\frac {Bx}{C}}{\log({\frac {x}{C}})}}}$

${\displaystyle \pi (x)\geq {\frac {\frac {Bx}{C}}{\log({\frac {x}{C}})}}}$

${\displaystyle \pi (x)\geq {\frac {Bx}{\log(x)}}}$