bounds on $\pi(n)$

This article shows that

$\ln 2\left(\frac{n}{\ln n}\right)-1\leq\pi(n)\leq 8\ln 2\left(\frac{n}{\ln n}\right)$

and thus that the function

$\pi(n)/\frac{n}{\ln n}$

is bounded above and below.

Definition 1

If $n$ is an integer, write $n=\prod p_{i}^{r_{i}}$ where the $p_{i}$ are distinct primes. Then

$ord_{p}(n)=\begin{cases}r_{i}&\text{if }p=p_{i}\\ 0&\text{otherwise}\end{cases}$

Lemma 1

$ord_{p}(n!)=\sum_{i=1}^{\infty}\lfloor\frac{n}{p^{i}}\rfloor$

Proof. Note that the number of multiples of $p\leq n$ is simply $\lfloor\frac{n}{p}\rfloor$ . But that does not result in $ord_{p}(n!)$ since some of those $\lfloor\frac{n}{p}\rfloor$ numbers may have additional factors of $p$ . So divide each by $p$ ; then clearly

$ord_{p}(n!)=\lfloor\frac{n}{p}\rfloor+ord_{p}(\lfloor\frac{n}{p}\rfloor!)$

The result follows inductively. Note that the sum is actually finite.

Lemma 2

If $\binom{m+n}{n}=\prod q_{i},q_{i}=p_{i}^{r_{i}}$ , all $p_{i}$ distinct, then $\forall i,q_{i}\leq m+n$ .

Proof. Consider $q_{1}=p^{c}$ . Choose $a$ such that $p^{a}\leq m+n<p^{a+1}$ ; it suffices to show $c\leq a$ .

$c=ord_{p}(\binom{m+n}{n})=ord_{p}((m+n)!)-ord_{p}(m!)-ord_{p}(n!)=\sum_{1}^{% \infty}(\lfloor\frac{m+n}{p^{i}}\rfloor-\lfloor\frac{m}{p^{i}}\rfloor-\lfloor% \frac{n}{p^{i}}\rfloor)$

Now, in general, if $\lfloor x\rfloor=r,\lfloor y\rfloor=s$ , then $\lfloor x+y\rfloor=r+s$ or $r+s+1$ . So the sum above has at most $a$ terms (since $p^{a+1}>m+n$ ), each of which is either $0$ or $1$ , and thus $c\leq a$ .

Theorem 1

(Chebyshev) If $n\geq 2$

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

Proof. Choose $r$ such that $0<r<n$ , and write $\binom{n}{r}=\prod p_{i}\!^{\lambda_{i}}$ . Each $p_{i}^{\lambda_{i}}\leq n$ by the preceding lemma, and there are at most $\pi(n)$ terms on the right-hand side. Thus

$n^{\pi(n)}\geq\binom{n}{r}\ \forall r$

Summing from $r=1$ to $r=n-1$ , we get

$(n-1)n^{\pi(n)}\geq\sum_{r=1}^{n-1}\binom{n}{r}=2^{n}-2$

But $n^{\pi(n)}\geq 2$ since $n\geq 2$ , so

$n^{\pi(n)+1}\geq 2^{n}$

so $(\pi(n)+1)\ln n\geq n\ln 2$ and thus

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

Theorem 2

(Chebyshev)

$\pi(n)\leq 8\ln 2\left(\frac{n}{\ln n}\right)$

Proof. Note that if $p$ is prime, $n\leq p\leq 2n$ , then $p$ divides $\binom{2n}{n}$ since $p$ occurs in the numerator but not in the denominator. Thus $\prod_{n\leq p\leq 2n}p$ divides $\binom{2n}{n}$ as well, and thus

$\prod_{n\leq p\leq 2n}p\leq\binom{2n}{n}\leq 2^{2n}$

and therefore

$n^{\pi(2n)-\pi(n)}\leq 2^{2n}$

Taking logs, we get

$\pi(2n)-\pi(n)\leq\frac{2n\ln 2}{\ln n}=2\ln 2\frac{n}{\ln n}$

Let $f(n)=\pi(n)\ln n$ . Then

		$\displaystyle f(2n)-f(n)$	$\displaystyle=\pi(2n)\ln 2n-\pi(n)\ln n$
			$\displaystyle=(\pi(2n)-\pi(n))\ln n+\pi(2n)(\ln 2n-\ln n)$
			$\displaystyle=(\pi(2n)-\pi(n))\ln n+\pi(2n)\ln 2$
			$\displaystyle\leq 2n\ln 2+2n\ln 2$
			$\displaystyle=4n\ln 2$

Then

		$\displaystyle f(2^{t})$	$\displaystyle=(f(2^{t})-f(2^{t-1}))+(f(2^{t-1})-f(2^{t-2}))+\ldots+(f(2)-f(1))$
			$\displaystyle\leq 4\ln 2(2^{t-1}+2^{t-2}+\ldots+2^{0})$
			$\displaystyle\leq 4\ln 2\cdot 2^{t}$

Note that $f$ is monotonically increasing, so if we choose $t$ with $2^{t-1}\leq n<2^{t}$ , then

$f(n)\leq f(2^{t})\leq 4\ln 2\cdot 2^{t}\leq 4\ln 2\cdot 2n=8n\ln 2$