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:

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

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

It is often stated using asymptotic notation:

$\pi (x)\sim {\frac {x}{\log x}}.\!$$\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 $(a_{n})_{n\in \mathbb {N} }$$(a_{n})_{n\in \mathbb {N} }$ be a sequence and let $f:\mathbb {R} \to \mathbb {R}$$f:\mathbb {R} \to \mathbb {R}$ be a differentiable function such that $f'$$f'$ is Riemann integrable. If we define

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

then we have

$\sum _{1\leq n\leq x}a_{n}f(n)=A(x)f(x)-\int _{1}^{x}A(t)f'(t)dt$$\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:

$\sum _{1\leq n\leq x}a_{n}f(n)=\sum _{1\leq n\leq x}(A(n)-A(n-1))f(n)$$\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:

$=\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)$$=\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:

$=\sum _{1\leq n\leq x-1}A(n)(f(n)-f(n+1))+A(x)f(x)$$=\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:

$=\sum _{1\leq n\leq x-1}A(n)\left(-\int _{n}^{n+1}f'(t)dt\right)+A(x)f(x)$$=\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:

$\sum _{1\leq n\leq x}a_{n}f(n)=A(x)f(x)-\int _{1}^{x}A(t)f'(t)dt$$\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. $f(x)=O(g(x))$$f(x)=O(g(x))$ because there exist $c$$c$ and $x_{0}$$x_{0}$ such that $|f(x)|\leq |cg(x)|$$|f(x)|\leq |cg(x)|$ whenever $x\leq x_{0}$$x\leq x_{0}$. We say $f(x)$$f(x)$ is bounded by $g(x)$$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 $\Lambda (x)$$\Lambda (x)$: $\Lambda (n)$$\Lambda (n)$ is known as the von Mangoldt function. It is defined as :

$\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}}$$\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:

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

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

Applying Abel's lemma

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

$\sum _{n\leq x}\log(n)=[x]*\log(x)-\int _{1}^{x}{\frac {[t]}{t}}dt$$\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:

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

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

$\sum _{n\leq x}\log(n)=x\log(x)+O(\log(x))-x+1+O(\log(x))$$\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:

$\sum _{n\leq x}\log(n)=x\log(x)-x+O(\log(x))$$\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:

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

$\sum _{d\leq x}\Lambda (d)*{\frac {x}{d}}+\psi (x)*O(1)$$\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 $\psi (x)$$\psi (x)$, we find a bound for a related function $\Theta (x)$$\Theta (x)$ which is defined as:

$\Theta (x)=\sum _{p\leq x}\log(p)$$\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:

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

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

$\prod _{n<p\leq 2n}p\mid {\binom {2}{n}}{n}$$\prod _{n<p\leq 2n}p\mid {\binom {2}{n}}{n}$

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

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

$\prod _{n<p\leq 2n}p\leq (1+1)^{2}n$$\prod _{n<p\leq 2n}p\leq (1+1)^{2}n$

Taking the logarithm we get:

$\sum _{n<p\leq 2n}\log(p)\leq 2n*\log(2)$$\sum _{n<p\leq 2n}\log(p)\leq 2n*\log(2)$

$\Theta (2n)-\Theta (n)\leq 2n*\log(2)$$\Theta (2n)-\Theta (n)\leq 2n*\log(2)$

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

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

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

$\Theta (2n)\leq 4n*\log(2)$$\Theta (2n)\leq 4n*\log(2)$

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

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

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

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

$\psi (x)\leq \Theta (x)+\sum _{n\geq 2}{\frac {1}{n}}*{\sqrt[{n}]{x}}*\log(x)$$\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 ( $\Theta (x)$$\Theta (x)$ is 0 for arguments smaller than 2 ) we can say the sum is bounded by the largest term:

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

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

$\psi (x)=O(x)$$\psi (x)=O(x)$

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

$\sum _{n\leq x}\log(n)=\sum _{d\leq x}\Lambda (d)*{\frac {x}{d}}+O(x)=x\log(x)-x+O(\log(x))$$\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:

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

Implications for the distribution of primes

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

$\Theta (x)\leq Kx$$\Theta (x)\leq Kx$

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

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

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

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

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

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

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

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

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

We also know that:

$\sum _{p\leq x}{\frac {\Lambda (p)}{p}}={\frac {\log(x)}{x}}+O(1)$$\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:

$\sum _{p\leq x}{\frac {\log(p)}{p}}={\frac {\log(x)}{x}}+O(1)$$\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:

$\sum _{{\frac {x}{C}}<p\leq x}{\frac {\log(p)}{p}}={\frac {\log(C)}{x}}+O(1)\geq B$$\sum _{{\frac {x}{C}}<p\leq x}{\frac {\log(p)}{p}}={\frac {\log(C)}{x}}+O(1)\geq B$

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

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

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

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