The function $\pi(n)$ counts the number of primes $p$ in the range $1\leq p\leq n$. One of the most spectacular theorems in mathematics is the so-called prime number theorem, which states that

\[ \lim_{n\to\infty}\Bigl(\pi(n)\Bigm/\frac{n}{\ln n}\Bigr) = 1 . \]

This is a strong condition on the asymptotic behaviour of $\pi(n)$ as $n$ increases without bound—unlike some asymptotic results, even the base of the logarithm is significant here.

Last year I worked through a proof of the prime number theorem. Two of the main results used were Euler’s product and Cauchy’s residue theorem—it was breathtaking. It still hasn’t completely “coalesced” in my head, but I periodically revisit it. Today I want to prove a weaker form of the prime number theorem, namely that

\[ \pi(n) = \Theta\Bigl(\frac{n}{\ln n}\Bigr) . \]

This uses asymptotic notation, and says that the growth rate of $\pi(n)$ is eventually within a constant factor of $n/\ln n$.

The proof is by Chebyshev and proceeds by finding the following bounds on the central binomial coefficient $\binom{2n}{n}$:

\begin{align}
2^n \leq \binom{2n}{n} &\leq 4^n \tag{1} \\
n^{\pi(2n)-\pi(n)} \leq \binom{2n}{n} &\leq (2n)^{\pi(2n)} \tag{2}
\end{align}

Upper bound of (1)

Using the binomial theorem to expand $(1+1)^{2n}$ gives

\[ 4^n = 2^{2n} = (1+1)^{2n} = \sum_{i=0}^{2n}\binom{2n}{i} \geq \binom{2n}{n} \]

since all the terms in the sum are positive.

Lower bound of (1)

However, note that the central term ($i=n$) in the sum is the largest (to go from term $i$ to term $i+1$ you multiply by $\frac{2n-i}{i+1}$, which is greater than $1$ until $i\geq n$), so we have:

\[ 4^n = 2^{2n} = (1+1)^{2n} = \sum_{i=0}^{2n}\binom{2n}{i} \leq (2n+1)\binom{2n}{n} \]

The required inequality follows after dividing by $2^n$ and using the fact that $2n+1\leq2^n$ (which holds for $n\geq3$, however the required inequality may explicitly be checked to hold for $n<3$).

Lower bound of (2)

Examining the prime factorization of $\binom{2n}{n}=(2n)!/(n!)^2$, we see that it contains all the primes $p$ in the range $n<p\leq 2n$, since they appear in the numerator but not in the denominator. There are $\pi(2n)-\pi(n)$ primes in this range, and they are all larger than $n$, so it follows that:

\[ \binom{2n}{n} \geq \prod_{n<p\leq 2n} p \geq n^{\pi(2n)-\pi(n)} \]

Upper bound of (2)

Note that there are $\lfloor n/p\rfloor$ multiples of $p$ in the range $1\leq p\leq n$. We can use this fact to determine the exponent on $p$ in the prime factorization of $n!$. There will be $\lfloor n/p\rfloor$ factors of $p$ in $n!$, but we also need to count the additional $\lfloor n/p^2\rfloor$ factors of $p$ which are contributed by multiples of $p^2$, and in general an additional $\lfloor n/p^k\rfloor$ factors of $p$ contributed by multiples of $p^k$. The exponent of $p$ in the prime factorization of $n!$ is thus

\[ \sum_{k=1}^\infty \biggl\lfloor\frac{n}{p^k}\biggr\rfloor , \]

where the sum is zero for $k>\log_p n$. It follows that the exponent of $p$ in the prime factorization of $(2n)!/(n!)^2$ is

\[ \sum_{k=1}^{\lfloor\log_p(2n)\rfloor} \biggl(\biggl\lfloor\frac{2n}{p^k}\biggr\rfloor – 2\biggl\lfloor\frac{n}{p^k}\biggr\rfloor\biggr) . \]

An interesting fact about the function $\lfloor 2x\rfloor-2\lfloor x\rfloor$ is that it is either $0$ or $1$ (plot it and you’ll see why), so this sum is actually at most $\lfloor\log_p(2n)\rfloor$. Since $\binom{2n}{n}$ only contains primes $p$ in the range $1\leq p\leq 2n$, it follows that:

\[ \binom{2n}{n} \leq \prod_{1\leq p\leq 2n}p^{\log_p(2n)} = \prod_{1\leq p\leq 2n} 2n = (2n)^{\pi(2n)} \]

Using the bounds

Putting both (1) and (2) together and taking logarithms yields the following bounds:

\begin{gather}
n\ln 2 \leq \pi(2n)\ln(2n) \tag{3} \\
(\pi(2n)-\pi(n))\ln n \leq n\ln 4 \tag{4}
\end{gather}

The lower bound on $\pi(n)$

From (3) we have that

\[ \pi(2n) \geq \frac{\ln2}{2}\frac{2n}{\ln(2n)} , \]

which is shows the required lower bound for even numbers. But it can be slightly modified to work for odd numbers as well (note that $\ln(2n)\leq\ln(2n+1)$):

\[ \pi(2n+1) \geq \pi(2n) \geq \frac{2n+1}{2n+1}\frac{\ln2}{2}\frac{2n}{\ln(2n)} \geq \frac{2n}{2n+1}\frac{\ln2}{2}\frac{2n+1}{\ln(2n+1)} \]

Since $2n/(2n+1)$ is lower bounded by a constant (e.g., $2/3$) for all positive $n$, this shows that $\pi(n)=\Omega(n/\ln n)$.

The upper bound on $\pi(n)$

First we will show the required upper bound for powers of two. That way we will be able to apply (4) not only on $n$ but also recursively on half of $n$ until $n=1$ is reached. However, to get a nice telescoping sum we modify (4) by subtracting $\pi(n)\ln(n/2)$ from both sides. After rearranging and simplifying with $\ln n-\ln(n/2)=\ln2$, we find

\[ \pi(2n)\ln n – \pi(n)\ln(n/2) \leq n\ln4 + \pi(n)\ln 2 \leq (3\ln 2)n \tag{5} \]

since $\pi(n)\leq n$ and $\ln4+\ln2=3\ln2$.

We now sum together (5) used on $n{,}~n/2{,}~\dotsc{,}~1$ to get

\[ \sum_{i=0}^{\log_2 n}\biggl(\pi\Bigl(\frac{n}{2^{i-1}}\Bigr)\ln\Bigl(\frac{n}{2^i}\Bigr)-\pi\Bigl(\frac{n}{2^i}\Bigr)\ln\Bigl(\frac{n}{2^{i+1}}\Bigr)\biggr) \leq (3\ln 2)\sum_{i=0}^{\log_2 n}\frac{n}{2^i} . \]

However, by telescoping the left sum is equal to $\pi(2n)\ln n$ and by the formula for the summation of a geometric series the right sum is at most $(3\ln2)2n$. In other words, when $n$ is a power of two we have

\[ \pi(2n) \leq (6\ln2)\frac{n}{\ln n} , \]

and the required bound follows using $\frac{n}{\ln n}<\frac{2n}{\ln(2n)}$, a consequence of the fact that $\frac{n}{\ln n}$ is an increasing function (for $n\geq3$, although the required bound still holds for $n<3$).

As before, a slight modification shows the bound holds for all numbers, not just powers of two. Let $m$ be an arbitrary integer in the range $n\leq m<2n$ where $n$ is a power of two. Then

\[ \pi(m) \leq \pi(2n) \leq (6\ln 2)\frac{n}{\ln n} \leq (6\ln 2)\frac{m}{\ln m} \]

which shows that $\pi(n)=O(n/\ln n)$.