# Prime Counting Function and Chebyshev Bounds

The distribution of primes plays a central role in number theory. The famous mathematician Gauss had conjectured that the number of primes between $$1$$ and $$n$$ is roughly $$n/\log n$$. This estimation gets more and more accurate as $$n\to \infty$$. We use $$\pi(n)$$ to denote the number of primes between $$1$$ and $$n$$. So, mathematically, Gauss’s conjecture is equivalent to the claim

$\lim_{n\to\infty}\frac{\pi(n)}{n/\log n}=1$

This conjecture (currently known as the Prime Number Theorem) is notoriously difficult to prove. The first proof appeared almost a century after it was stated.

However, there are much simpler methods to bound $$\pi(n)$$ above and below. Today I shall show such a bound that gives the correct order of magnitude for $$\pi(n)$$ up to some constants. In particular, I shall prove that

$(1+2\log 4)\frac{n}{\log n}\ge \pi(n)\ge \frac{\log 2}{2}\frac{n}{\log n}$

for $$n\ge 12$$. This proof technique is originally due to nineteenth century mathematician Pafnuty Chebyshev. He used a more complicated version of this technique to show that

$1.1\frac{n}{\log n}\ge \pi(n)\ge 0.92\frac{n}{\log n}$

for sufficiently large $$n$$s.

### The Lower Bound

Suppose $$n$$ is even, ie. $$n=2k$$. Let us consider the prime factorization of $$\binom{2k}{k}$$. All of its prime factors are between $$1$$ and $$2k$$. Therefore,

$\binom{2k}{k}=p_1^{a_1}\cdots p_{\pi(2k)}^{a_{\pi(2k)}}$

Claim: For every prime $$p_i$$, $$p_i^{a_i}\leq 2k$$

Proof: We shall use this very simple identity $\lfloor a+b\rfloor-\lfloor a\rfloor-\lfloor b\rfloor\leq1$

It is well-known that the largest exponent of a prime dividing $$r!$$ is

$\left\lfloor\frac{r}{p_i}\right\rfloor+\left\lfloor\frac{r}{p_i^2}\right\rfloor+\cdots$

Since $$\binom{2k}{k}=\frac{(2k)!}{(k!)^2}$$, we have the following relationship

\begin{align}
a_i=&\left\lfloor\frac{2k}{p_i}\right\rfloor-2\left\lfloor\frac{k}{p_i}\right\rfloor+\left\lfloor\frac{2k}{p_i^2}\right\rfloor-2\left\lfloor\frac{k}{p_i^2}\right\rfloor+\cdots \\
&\leq 1+1+\cdots
\end{align}

Now there are as many $$1$$s as there are powers of $$p_i\leq 2k$$. Hence, $$p_i^{a_i}\leq 2k$$.

(Q.E.D)

So, we can conclude,

$\binom{2k}{k}=p_1^{a_1}\cdots p_{\pi(2k)}^{a_{\pi(2k)}}\leq (2k)^{\pi(2k)}$

It is easy to prove $$\binom{2k}{k}\ge 2^k$$, hence

$(2k)^{\pi(2k)}\ge 2^k\implies \pi(2k)\ge \frac{\log 2}{2}\cdot\frac{2k}{\log 2k}$

The same bound can be derived for $$n=2k+1$$ using $$\binom{2k+1}{k+1}$$.  Therefore, the lower bound is

$\boxed{\pi(n)\ge \frac{\log 2}{2}\cdot\frac{n}{\log n}}$

### The Upper Bound

Claim: For all $$n\ge 2$$, $\prod_{p\leq n\\ p\ \text{prime}}p\leq 4^n$

Proof: We induct on $$n$$. The base case trivially holds. $$n=2k-1\to 2k$$ also holds because the product on the left hand side does not increment. So, we only need to prove $$n=2k\to 2k+1$$
\begin{align}
\prod_{p \leq 2k+1\\ p\ \text{prime}}p &= \prod_{p \leq k+1\\ p\ \text{prime}}p \cdot\prod_{k+2\leq p \leq 2k+1\\ p\ \text{prime}}p\\
&\leq 4^{k+1}\cdot \binom{2k+1}{k}\quad (1)
\end{align}
The first part of the product is $$\leq 4^{k+1}$$ because of the inductive hypothesis. The second part is just the product of all the primes in between $$k+2$$ and $$2k+1$$. It’s easy to see that they all divide $$\binom{2k+1}{k}$$, hence their product is $$\leq \binom{2k+1}{k}$$.

It’s easy to show $$\binom{2k+1}{k}<4^k$$. Substituting this bound back to (1) gives us

$\prod_{p \leq 2k+1\\ p\ \text{prime}}p \leq 4^{k+1}\cdot 4^k=4^{2k+1}\quad (\text{Q.E.D.})$

Now take a number $$2\leq m\leq n$$. Consider the primes that are between $$m$$ and $$n$$. There are $$\pi(n)-\pi(m)$$ of them, each of which is $$\ge m$$. Consequently,

$m^{\pi(n)-\pi(m)}\leq \prod_{m\leq p \leq n\\ p\ \text{prime}}p\leq \prod_{1\leq p \leq n\\ p\ \text{prime}}p\leq 4^n$

Now take log of both sides

$(\pi(n)-\pi(m))\log m\leq n\log 4$

Rewrite this as

$\pi(n)\leq \pi(m)+\frac{n\log 4}{\log m}\leq m+\frac{n\log 4}{\log m}$

Set $$m=\frac{n}{\log n}$$ and simplify the expression

$\pi(n)\leq \frac{n}{\log n}\left(1+\frac{\log 4\cdot\log n}{\log(n/\log n)}\right)$

Easy to show $$\frac{\log n}{\log(n/\log n)}\leq 2$$ for $$n\ge 12$$. (In fact you can show much tighter bound for sufficiently large $$n$$.) Hence, the upper bound is

$\boxed{\pi(n)\leq \left(1+2\log 4\right)\frac{n}{\log n}}$