Chebyshev prime number estimates

 In my previous post, I promised that I would show how to prove that the prime counting function $\pi(n)$ is sandwiched in between two functions of the form $c_1\frac{n}{\log n}$ and $c_2\frac{n}{\log n}$ for some constants $c_1$ and $c_2$. Chebyshev was a pioneer in this area and after a lot of hard work was able to determine in an 1854 paper that this inequality is true for large $n$ and with

$$c_1=0.922\ldots\text{ and }c_2=1.105\ldots.$$

The Prime Number theorem says we should be able to get these constants arbitrarily close to $1$.

Following Lemmermeyer's exposition, we will content ourselves with getting some much cruder estimates, but for far less work! We will show you can take 

$$c_1=\frac{\log 2}{2}\approx 0.347\text{ and }c_2=6\log 2\approx 4.159$$

These are poor estimates but you can get them for some surprisingly little work.

As before the number $N=\binom{2n}{n}$ will play a critical role in the proofs. Let $\nu_p$ be the exponent of $p$ in $N$. In the second proposition of the previous post we showed

$$p^{\nu_p}\leq 2n,$$

which implies $$\nu_p\leq \lfloor\frac{\log 2n}{\log p}\rfloor.$$

Also recall the estimate $\binom{2n}{n}\geq \frac{2^{2n}}{2n}$. Taking logs, we have

$$2n\log 2-\log 2n \leq \log\binom{2n}{n}=\log\left(\prod p^{\nu_p}\right)$$

$$\leq \sum_{p\leq 2n} \left\lfloor\frac{\log 2n}{\log p}\right\rfloor \log p $$

$$\leq \sum_{p\leq 2n} \log 2n=\pi(2n)\log 2n$$

Putting these all together, we get

$$2n\log 2-\log 2n\leq \pi(2n)\log 2n,$$

and rearranging

$$\pi(2n)\geq \log 2\frac{2n}{\log 2n}-1$$

It is not difficult to see that $\log 2\frac{2n}{\log 2n}-1>\frac{\log 2}{2}\frac{2n}{\log 2n}$. This shows $\pi(2n)<\frac{\log 2}{2}\frac{2n}{\log 2n}$. In fact, for general $x$, we need a slightly stronger inequality. Assume $2n\leq x<2n+2$. Then

$$\pi(x)\geq\pi(2n)\geq \log 2\frac{2n}{\log 2n}-1$$

and in order to complete the argument showing $c_1=\frac{\log 2}{2}$, we need to show that

$$\log 2\frac{2n}{\log 2n}-1\geq \frac{(n+1)\log 2}{\log (2n+2)},$$ since this is clearly $\geq \frac{\log 2}{2}\frac{x}{\log x}$.

Lemma: $\log 2\frac{2n}{\log 2n}-1\geq \frac{(n+1)\log 2}{\log (2n+2)}$

Proof:

It suffices to show $\log 2\frac{2n}{\log (2n+2)}-1\geq \frac{(n+1)\log 2}{\log (2n+2)}$. Multiplying both sides by $\log(2n+2)$ we get the following equivalent inequalities:

$$(\log 2)(2n)-\log(2n+2)\geq (n+1)\log 2$$

$$(\log 2)(n-1)\geq \log 2+\log(n+1)$$

$$n\log 2\geq \log(n+1)$$

$$\log 2^n\geq \log (n+1)$$

which is satisfied for all $n\geq 1$. $\Box$

So we have shown $c_1=\frac{\log 2}{2}$. Let us return to the lower bound, which we talked about in the last post. We were zeroing in on Bertrand's Postulate, so the resulting estimate was not the greatest. 

Consider $\prod_{n<p \leq 2n}p.$ This is less than $4^n$ (which follows from the last post.) If we replace each $p$ in this expression with $n$, we get the inequality $n^{\pi(2n)-\pi(n)}\leq\prod_{n<p \leq 2n}p$. So we can conclude

$$n^{\pi(2n)-\pi(n)}<4^n$$

$$\pi(2n)-\pi(n)<\frac{n\log 4}{\log n}$$

Lemma: $\pi(2^k)\leq \frac{3}{k}2^k$.

Proof:

Check it directly for $k\leq 5.$ Now

$$\pi(2^{k+1})-\pi(2^k)<\frac{2^k\log 4}{\log 2^k}=\frac{2^{k+1}}{k},$$

so inductively $$\pi(2^{k+1})=\pi(2^k)+\frac{2^{k+1}}{k}\leq \frac{3}{k}2^k+\frac{2^{k+1}}{k}=\frac{5\cdot 2^k}{k}.$$ It is a simple exercise to show that $\frac{5\cdot 2^k}{k}\leq \frac{3}{k+1}2^{k+1}$, for $k\geq 5$, which will complete the proof. $\Box$.

Now suppose $2^k<x\leq 2^{k+1}$. Then we have

$$\pi(x)\leq \pi(2^{k+1})\leq \frac{6\cdot 2^k}{k+1}\leq \frac{6\cdot 2^k}{k}=6\log 2\frac{2^k}{\log 2^k}\leq 6\log 2\frac{x}{\log x}.$$ So we can take $c_2=6\log 2$.