# 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,$ Definition of $\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}}.\!$ 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} }$ be a sequence and let $f:\mathbb {R} \to \mathbb {R}$ be a differentiable function such that $f'$ is Riemann integrable. If we define

$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$ .

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)$ 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)$ 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)$ 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)$ 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$ ## 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))$ because there exist $c$ and $x_{0}$ such that $|f(x)|\leq |cg(x)|$ whenever $x\leq x_{0}$ . We say $f(x)$ is bounded by $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 (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}}$ One important property of this function follows from the fundamental theorem of arithmetic:

$\log(n)=\sum _{d\mid n}\Lambda (d)$ The summatory function is called the Chebyshev function it is denoted by $\psi (x)$ ### Applying Abel's lemma

We are going to apply Abel's lemma to $\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$ [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\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))$ 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))$ ### 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))$ 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}}$ or ${\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)$ ### Finding a bound for the Chebyshev function

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

$\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,$ Regarding prime numbers we see that ${\binom {n}{k}}$ devides every prime number between and n-k. We therefore know:

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

${\binom {2n}{n}}\leq (1+1)^{2n}$ $\prod _{n Taking the logarithm we get:

$\sum _{n $\Theta (2n)-\Theta (n)\leq 2n*\log(2)$ $\Theta (n)-\Theta (n/2)\leq n*\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)$ This shows that Theta is bounded by x, $\Theta (x)=O(x)$ . But it doesn't show anything about $\psi (x)$ of which we know that it is bigger than $\Theta (x)$ . We can however define $\psi (x)$ in terms of $\Theta (x)$ :

$\psi (x)=\sum \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}{\frac {1}{n}}*{\sqrt[{n}]{x}}*\log(x)$ As we do not have an infinite sum ( $\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))$ As the bounding function of the difference is smaller than x we know:

$\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))$ Dividing this by x removing the bounded terms we end up having:

$\sum _{d\leq x}{\frac {\Lambda (d)}{d}}=\log(x)+O(1)$ ## Implications for the distribution of primes

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

$\Theta (x)\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)$ is bounded by x the first of these to sums will be bounded by ${\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)*(\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))\leq Kx+O({\sqrt {x}}*\log(x))$ $\pi (x)\leq {\frac {Kx}{\log(x)}}+O({\sqrt {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)$ 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)$ Now we choose a large number C so that there is a positive constant B so:

$\sum _{{\frac {x}{C}} ${\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)\geq {\frac {\frac {Bx}{C}}{\log({\frac {x}{C}})}}$ $\pi (x)\geq {\frac {Bx}{\log(x)}}$ 