PlanetMath: bounds on $\pi(n)$

(more info)

Math for the people, by the people.

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (232)
Orphanage
Unclass'd
Unproven (519)
Corrections (23)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

bounds on $\pi(n)$

(Theorem)

This article shows that

$\displaystyle \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

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

is bounded above and below.

Definition 1 If is an integer, write $n=\prod p_i^{r_i}$ where the are distinct primes. Then

$\displaystyle ord_p(n)=\begin{cases} r_i&\text{if } p=p_i\ 0&\text{otherwise} \end{cases}$

Lemma 1

$\displaystyle 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

since some of those $\lfloor \frac{n}{p}\rfloor$ numbers may have additional factors of

. So divide each by

; then clearly

$\displaystyle 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 distinct, then $\forall i, q_i\leq m+n$ .

Proof. Consider

. Choose

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

$\displaystyle c=ord_p(\binom{m+n}{n})=ord_p((m+n)!)-ord_p(m!)-ord_p(n!)=\sum_1^... ...\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

. So the sum above has at most

terms (since $p^{a+1}>m+n$ ), each of which is either 0 or

, and thus $c\leq a$ .

Theorem 1 (Chebyshev) If $n\geq 2$

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

Proof. Choose

such that

, 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

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

Summing from

, we get

$\displaystyle (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

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

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

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

Theorem 2 (Chebyshev)

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

Proof. Note that if

is prime, $n\leq p\leq 2n$ , then

divides $\binom{2n}{n}$ since

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

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

and therefore

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

Taking logs, we get

$\displaystyle \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$