Tuesday, 6 April 2021

Chebyshev's Estimates For $\pi(x)$

Pafnuty Chebyshev proved Bertrand's Postulate that there is at least one prime between a number and its double, $n \leq p \leq 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} = {2n \choose 0}  +  \ldots + \ldots {2n \choose n} + \ldots + {2n \choose 2n}$$

Because ${2n \choose n}$ is only one of those terms we can say:

$$ \begin{align} 2^{2n} &> {2n \choose n} = \frac{(2n)!}{n!n!} \\ \\ &= \frac{(2n)\cdot(2n-1)\cdot \ldots \cdot (n+1)}{n\cdot(n-1)\cdot(n-2)\ldots \cdot 2 \cdot 1} \end{align}$$

Looking at that fraction, we can say that the numerator contains primes $n<p \leq 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 \leq 2n} p \text{ divides } {2n \choose n} $$

How many primes are there $n<p \leq 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 \leq 2n}$. This is because each of those primes is greater than $n$.

$$ n^{\pi(2n) - \pi(n)} < \prod_{n<p \leq 2n} p  \leq  {2n \choose n} < 2^{2n}$$

We can take logs and simplify:

$$ \boxed{ \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) \leq 3 \cdot \frac{2^k}{k} $$

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

$$ \begin{align} \pi(2^{k+1}) & \leq \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{align}$$

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

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

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\leq5$ confirms it is true for all $k$.

We've shown that if $\pi(2^k) \leq 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 \leq 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 \leq 2^{k+1}$ we can say

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

That least step requires $x \geq e$, but we can numerically verify that $\pi(x) \leq 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{ \pi(x) \leq 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} = {2n \choose 0}  +  \ldots  + {2n \choose n} + \ldots + {2n \choose 2n}$$

we can see that ${2n \choose n}$ is the largest element, which means it must be $\geq$ 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} \leq {2n \choose n}$$

Taking logs gives us

$$ 2n\ln2 - \ln(2n) \leq \ln {2n \choose n} $$

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


We know that  ${2n \choose 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{v_p(n!) = \sum_m \left \lfloor \frac{n}{p^m} \right \rfloor }$$

This is because in the set of numbers $\{ 1,2,3,\ldots,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 ${2n \choose n}$ is $\frac{(2n)!}{n!n!}$, and because $v_p(a/b) = v_p(a)-v_p(b)$, we can say

$$ v_p{2n \choose n} = \sum_m \left( \left \lfloor \frac{2n}{p^m} \right \rfloor - 2\left \lfloor \frac{n}{p^m} \right \rfloor \right)$$

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{align} \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{cases} 0 \text { for } b<\frac12 \\ 1 \text{ for } b>\frac12 \end{cases} \end{align}$$

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{align} v_p{2n \choose n} &= \sum_{1\leq m \leq \lfloor \frac{\ln(2n)}{\ln p} \rfloor} \left( \left \lfloor \frac{2n}{p^m} \right \rfloor - 2\left \lfloor \frac{n}{p^m} \right \rfloor \right) \\ \\ &\leq \sum_{1\leq m \leq \lfloor \frac{\ln(2n)}{\ln p} \rfloor} 1 \\ \\ v_p{2n \choose n} &\leq  \left \lfloor \frac{\ln(2n)}{\ln p} \right \rfloor \end{align} $$

Knowing how ${2n \choose n}$ factorises into primes $p$ will be helpful.


We can now proceed:

$$\begin{align} 2n\ln2 - \ln(2n) &\leq \ln {2n \choose n} \\ \\ &\leq \sum_{p\leq 2n} \left \lfloor \frac{\ln(2n)}{\ln p}\right \rfloor \ln p  \\ \\ &\leq \sum_{p \leq 2n} \ln(2n)\\ \\  &= \ln(2n)\cdot \pi(2n)  \end{align}$$

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

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

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


We can use induction again to prove that

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

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

$$ \pi(x) \geq \pi(2n) \geq \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)} \geq \frac{7}{4\ln2} \geq \frac{1}{\ln2} $$

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

This gives us:

$$\begin{align} \pi(x) \geq \pi(2n) & \geq \ln(2) \cdot \frac{2n}{\ln(2n)} -1 \\ \\  &\geq \ln(2)\left(\frac{1}{\ln2} + \frac{n+1}{\ln(2n)}\right) -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 \\ \\ &\geq \frac{(n+1)\ln(2)}{\ln(x)} \text{ because } x > 2n \\ \\ &\geq \frac{(x/2)\ln(2)}{\ln(x)} \text{ because } x \leq 2n+2 \\ \\ \end{align}$$

So we finally have 

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


The following illustrates these lower and upper bounds for $x\leq 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{align} 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{align} $$

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

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

In our case, the bounds $c_1 = \frac12 \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$. 

No comments:

Post a Comment