Tag Archives: Prime Counting Function

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}}\]