Chebyshev's Estimates For π(x)

Pafnuty Chebyshev proved Bertrand's Postulate that there is at least one prime between a number and its double, $n\le p\le 2n$, and came close to proving the Prime Number Theorem. 

In this post we'll recreate his estimates for the prime counting function $\pi (x)$ which came close to the actual PNT. The approach is inspired by a note by Franz Lemmermeyer [pdf].

A Bit Of History

We've previously discussed how Gauss and Legendre used experimental evidence to suggest that the prime counting function $\pi (x)$ is of the form $\frac{x}{\ln (x)}$, and that this approximation gets better for larger $x$ - in the sense that the ratio between the true count and this approximation gets ever closer to 1.

$$\pi (x)\sim \frac{x}{\ln (x)}$$

This is the Prime Number Theorem (PNT), which took another 100 years to be proved by Hadamard and de la Vallee-Poussin in 1896.  

Before that final proof, around 1850, Chebyshev got  close to proving the PNT by showing that $\pi (x)$ can be bounded as follows, where $c_1,c_2$ are constants $>0$.

$$c_1\frac{x}{\ln (x)}<\pi (x)<c_2\frac{x}{\ln (x)}$$

This is a remarkable result, and in fact was strong enough to prove Bertrand's Postulate that there is a prime between a number and its double, $n<p<2n$.

Starting With Combinations

We start with an observation about binomial coefficients:

$$2^{2n}=(1+1{)}^{2n}=(\genfrac{}{}{0ex}{}{2n}{0})+\dots +\dots (\genfrac{}{}{0ex}{}{2n}{n})+\dots +(\genfrac{}{}{0ex}{}{2n}{2n})$$

Because $(\genfrac{}{}{0ex}{}{2n}{n})$ is only one of those terms we can say:

$$\begin{array}{rl}{2}^{2n}& >(\genfrac{}{}{0ex}{}{2n}{n})=\frac{(2n)!}{n!n!}\\ \\ & =\frac{(2n)\cdot (2n-1)\cdot \dots \cdot (n+1)}{n\cdot (n-1)\cdot (n-2)\dots \cdot 2\cdot 1}\end{array}$$

Looking at that fraction, we can say that the numerator contains primes $n<p\le 2n$, and these primes don't appear in the denominator. This means each of those primes divides the  whole fraction without remainder, and so does the product of those primes.

$$\prod _{n<p\le 2n}p\text{ divides }(\genfrac{}{}{0ex}{}{2n}{n})$$

How many primes are there $n<p\le 2n$? The answer is of course $\pi (2n)-\pi (n)$.

If we raised $n$ to this number, it would be smaller than the actual product of those primes $\prod _{n<p\le 2n}$. This is because each of those primes is greater than $n$.

$$n^{\pi (2n)-\pi (n)}<\prod _{n<p\le 2n}p\le (\genfrac{}{}{0ex}{}{2n}{n})<2^{2n}$$

We can take logs and simplify:

$$\boxed{{\displaystyle \pi (2n)-\pi (n)<2\ln (2)\cdot \frac{n}{\ln (n)}}}$$

We now have a relation relating $\pi (n)$ to $n$. Intuitively it hints at $\pi (n)$ being of the form $n/\ln (n)$.

To find a form for $\pi (n)$ not involving $\pi (2n)$ we use induction.

Upper Bound

Let's try the following form for $\pi (n)$:

$$\pi (2^k)\le 3\cdot \frac{2^k}{k}$$

We can examine our inequality with $n=2^k$:

$$\begin{array}{rl}\pi (2^{k+1})& \le \pi (2^k)+2\ln (2)\cdot \frac{2^k}{\ln (2^k)}\\ & =\pi (2^k)+2\cancel{\ln (2)}\cdot \frac{2^k}{k\cancel{\ln (2)}}\\ & =\pi (2^k)+\frac{2^{k+1}}{k}\end{array}$$

Our proposed form for $\pi (n)$ gives us

$$\begin{array}{rl}\pi (2^{k+1})& \le 3\cdot \frac{2^k}{k}+2\cdot \frac{2^k}{k}\\ & =5\cdot \frac{2^k}{k}\\ \pi (2^{k+1})& \le 3\cdot \frac{2^{k+1}}{k+1}\end{array}$$

That last inequality appears to be only true for $k>5$ because $5\cdot \frac{2^k}{k}<3\cdot \frac{2^{k+1}}{k+1}$ is only true for $k>5$. However, numerically checking $\pi (2^{k+1})$ for $k\le 5$ confirms it is true for all $k$.

We've shown that if $\pi (2^k)\le 3\cdot \frac{2^k}{k}$ is true for $k$ it is also true for $k+1$. We've also shown it is true for some $k$, for example, $k=1$ because $\pi (2^1)=1\le 3\cdot \frac{2^1}{1}=6$. This completes the induction proof for this form of $\pi (2^k)$.

Now, if we set $2^k<x\le 2^{k+1}$ we can say

$$\begin{array}{rl}\pi (x)& \le \pi (2^{k+1})\\ & \le 3\cdot \frac{2^{k+1}}{k+1}=6\cdot \frac{2^k}{k+1}\\ & \le 6\cdot \frac{2^k}{k}=6\ln (2)\cdot \frac{2^k}{\ln (2^k)}\\ \pi (x)& \le 6\ln (2)\cdot \frac{x}{\ln (x)}\end{array}$$

That least step requires $x\ge e$, but we can numerically verify that $\pi (x)\le 6\ln (2)\frac{x}{\ln (x)}$ is true for $x<e$.

And so finally we have an upper bound for the prime counting function $\pi (x)$, 

$$\boxed{{\displaystyle \pi (x)\le 6\ln (2)\frac{x}{\ln (x)}}}$$

On its own, the upper bound isn't enough to tell us about the true form of $\pi (x)$. We need the lower bound to be of a similar form, and fairly tight too.

Lower Bound

Going back to the binomial coefficients

$$2^{2n}=(1+1{)}^{2n}=(\genfrac{}{}{0ex}{}{2n}{0})+\dots +(\genfrac{}{}{0ex}{}{2n}{n})+\dots +(\genfrac{}{}{0ex}{}{2n}{2n})$$

we can see that $(\genfrac{}{}{0ex}{}{2n}{n})$ is the largest element, which means it must be $\ge$ than the average of these $2n$ terms (we have $2n+1$ terms but we can combine the first and last which each have a value of 1), so

$$\frac{2^{2n}}{2n}\le (\genfrac{}{}{0ex}{}{2n}{n})$$

Taking logs gives us

$$2n\ln 2-\ln (2n)\le \ln (\genfrac{}{}{0ex}{}{2n}{n})$$

We now need to think about the prime factorisation of $(\genfrac{}{}{0ex}{}{2n}{n})$. To do this we need to take a short diversion.

We know that  $(\genfrac{}{}{0ex}{}{2n}{n})$ is $\frac{(2n)!}{n!n!}$, so we need to think about the prime factorisation of $n!$. Luckily this is not too difficult. If $v_p(n)$ is the highest power of a prime $p$ dividing $n$, then $$\boxed{{\displaystyle v_p(n!)=\sum _m\lfloor \frac{n}{p^m}\rfloor }}$$ This is because in the set of numbers $\{1,2,3,\dots ,n\}$ there are $\lfloor \frac{n}{p}\rfloor$ multiples of $p$, $\lfloor \frac{n}{p^2}\rfloor$ multiples of $p^2$, $\lfloor \frac{n}{p^3}\rfloor$ multiples of $p^3$, and so on, each contributing 1 to $v_p(n!)$. Now, because $(\genfrac{}{}{0ex}{}{2n}{n})$ is $\frac{(2n)!}{n!n!}$, and because $v_p(a/b)=v_p(a)-v_p(b)$, we can say $$v_p(\genfrac{}{}{0ex}{}{2n}{n})=\sum _m(\lfloor \frac{2n}{p^m}\rfloor -2\lfloor \frac{n}{p^m}\rfloor )$$ Let's focus on that form $\lfloor 2x\rfloor -2\lfloor x\rfloor$. It only takes values 0 or 1. This is easy to see if we write $x=a+b$ where $a$ is the integer part of $x$, and $b$ is the fraction. $$\begin{array}{rl}\lfloor 2x\rfloor -2\lfloor x\rfloor & =\lfloor 2a+2b\rfloor -2\lfloor a+b\rfloor \\ \\ & =\cancel{2a}+\lfloor 2b\rfloor \cancel{-2a}-2\lfloor b\rfloor \\ \\ & =\{\begin{array}{l}0\text{ for }b<\frac{1}{2}\\ 1\text{ for }b>\frac{1}{2}\end{array}\end{array}$$ The largest $m$ is $\lfloor \frac{\ln (2n)}{\ln p}\rfloor$ because a larger $m$ would give $p^m>2n$ which isn't possible. So $v_p$ reduces as follows: $$\begin{array}{rl}{v}_p(\genfrac{}{}{0ex}{}{2n}{n})& =\sum _{1\le m\le \lfloor \frac{\ln (2n)}{\ln p}\rfloor }(\lfloor \frac{2n}{p^m}\rfloor -2\lfloor \frac{n}{p^m}\rfloor )\\ \\ & \le \sum _{1\le m\le \lfloor \frac{\ln (2n)}{\ln p}\rfloor }1\\ \\ v_p(\genfrac{}{}{0ex}{}{2n}{n})& \le \lfloor \frac{\ln (2n)}{\ln p}\rfloor \end{array}$$ Knowing how $(\genfrac{}{}{0ex}{}{2n}{n})$ factorises into primes $p$ will be helpful.

We can now proceed:

$$\begin{array}{rl}2n\ln 2-\ln (2n)& \le \ln (\genfrac{}{}{0ex}{}{2n}{n})\\ \\ & \le \sum _{p\le 2n}\lfloor \frac{\ln (2n)}{\ln p}\rfloor \ln p\\ \\ & \le \sum _{p\le 2n}\ln (2n)\\ \\ & =\ln (2n)\cdot \pi (2n)\end{array}$$

Re-arranging gives us a lower bound for $\pi (2n)$:

$$\pi (2n)\ge \ln (2)\cdot \frac{2n}{\ln (2n)}-1$$

This is almost of the form we want $\pi (n)\ge c_1\cdot \frac{x}{\ln x}$. 

We can use induction again to prove that

$$\pi (x)\ge \frac{\ln (2)}{2}\cdot \frac{x}{\ln x}$$

Let's start with $2n<x\le 2n+2$, so

$$\pi (x)\ge \pi (2n)\ge \ln (2)\cdot \frac{2n}{\ln (2n)}-1$$

We're going to replace that $2n/\ln (2n)$ with an expression for $n$, and by assuming $x>16$:

$$\frac{2n}{\ln (2n)}-\frac{n+1}{\ln (2n)}=\frac{n-1}{\ln (2n)}\ge \frac{7}{4\ln 2}\ge \frac{1}{\ln 2}$$

We can manually show that the desired expression $\pi (x)\ge \frac{\ln 2}{2}\cdot \frac{x}{\ln x}$ is valid for $x\le 16$

This gives us:

$$\begin{array}{rl}\pi (x)\ge \pi (2n)& \ge \ln (2)\cdot \frac{2n}{\ln (2n)}-1\\ \\ & \ge \ln (2)(\frac{1}{\ln 2}+\frac{n+1}{\ln (2n)})-1\\ \\ & =\cancel{\ln (2)}\left(\frac{\ln (2n)+(n+1)\ln (2)}{\cancel{\ln (2)}\ln (2n)}\right)-1\\ \\ & =1+\frac{(n+1)\ln (2)}{\ln (2n)}-1\\ \\ & \ge \frac{(n+1)\ln (2)}{\ln (x)}\text{ because }x>2n\\ \\ & \ge \frac{(x/2)\ln (2)}{\ln (x)}\text{ because }x\le 2n+2\\ \end{array}$$

So we finally have 

$$\boxed{{\displaystyle \pi (x)\ge \frac{\ln (2)}{2}\cdot \frac{x}{\ln x}}}$$

The following illustrates these lower and upper bounds for $x\le 500$.

Bertrand's Postulate

Can Chebyshev's estimates be used to prove Bertrand's Postulate that there is a prime $p$ between $n$ and $2n$? Let's find out. 

Bertrand's postulate is the same as saying $\pi (2x)-\pi (x)>0$.

The smallest difference is when we take the lower bound for $\pi (2x)$, and the upper bound for $\pi (x)$:

$$\begin{array}{rl}{c}_1\frac{2x}{\ln (2x)}-c_2\frac{x}{\ln (x)}& >0\\ \\ 2c_1\cdot \ln (x)& >c_2\cdot (\ln (x)+\ln (2))\\ \\ (2c_1-c_2)\cdot \ln (x)& >c_2\cdot \ln (2)\end{array}$$

We can see that $(2c_1-c_2)$ must be positive, and so 

$$\boxed{{\displaystyle 2c_1>c_2}}$$

In our case, the bounds $c_1=\frac{1}{2}\ln (2)$ and $c_2=6\ln (2)$ aren't tight enough to prove Bertrand's Postulate. 

Chebyshev and others actually developed tighter bounds for $\pi (x)$ which do meet this requirement, $c_1=0.92$ and $c_2=1.11$, but those tighter bounds require much more work.

Thoughts

It is interesting that 

• Chebyshev's estimates for the prime counting function $\pi (x)$ are derived from the binomial coefficients of the expansion $(1+1{)}^{2n}$, a rather surprising source of useful inequalities. 

• the estimates are intimately linked to the prime factorisation of factorials. 

• the trail, albeit with some algebra work, can lead to a form for $\pi (x)$ that is $x/\ln (x)$, a form which hints at the Prime Number Theorem.

Additional work by Chebyshev showed that $c_1$ and $c_2$ can be as close to 1 as desired for large enough $x$.