bounds on $\pi (n)$

This article shows that

$$\ln 2\left(\frac{n}{\ln n}\right)-1\le \pi (n)\le 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\mathrm{=}\mathrm{\prod }{p}_i^{r_i}$ where the $p_i$ are distinct primes. Then

Lemma 1

$$or{d}_p(n!)=\sum _{i=1}^{\mathrm{\infty }}\lfloor \frac{n}{p^i}\rfloor$$

Proof.Note that the number of multiples of $p\le n$ is simply $\lfloor \frac{n}{p}\rfloor$. But that does not result in $or{d}_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

$$or{d}_p(n!)=\lfloor \frac{n}{p}\rfloor +or{d}_p(\lfloor \frac{n}{p}\rfloor !)$$

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

Lemma 2

If $\mathrm{\left(}\genfrac{}{}{0pt}{}{m\mathrm{+}n}{n}\mathrm{\right)}\mathrm{=}\mathrm{\prod }{q}_i\mathrm{,}{q}_i\mathrm{=}{p}_i^{r_i}$, all $p_i$ distinct, then $\mathrm{\forall }i\mathrm{,}{q}_i\mathrm{\le }m\mathrm{+}n$.

Proof.Consider $q_1=p^c$. Choose $a$ such that ; it suffices to show $c\le a$.

$$c=or{d}_p(\left(\genfrac{}{}{0pt}{}{m+n}{n}\right))=or{d}_p((m+n)!)-or{d}_p(m!)-or{d}_p(n!)=\sum _1^{\mathrm{\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\le a$.

Theorem 1

(Chebyshev) If $n\mathrm{\ge }\mathrm{2}$

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

Proof.Choose $r$ such that , and write $\left(\genfrac{}{}{0pt}{}{n}{r}\right)=\prod p_i^{{\lambda }_i}$. Each $p_i^{{\lambda }_i}\le n$ by the preceding lemma, and there are at most $\pi (n)$ terms on the right-hand side. Thus

$$n^{\pi (n)}\ge \left(\genfrac{}{}{0pt}{}{n}{r}\right)\forall r$$

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

$$(n-1)n^{\pi (n)}\ge \sum _{r=1}^{n-1}\left(\genfrac{}{}{0pt}{}{n}{r}\right)=2^n-2$$

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

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

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

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

Theorem 2

(Chebyshev)

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

Proof.Note that if $p$ is prime, $n\le p\le 2n$, then $p$ divides $\left(\genfrac{}{}{0pt}{}{2n}{n}\right)$ since $p$ occurs in the numerator but not in the denominator. Thus ${\prod }_{n\le p\le 2n}p$ divides $\left(\genfrac{}{}{0pt}{}{2n}{n}\right)$ as well, and thus

$$\prod _{n\le p\le 2n}p\le \left(\genfrac{}{}{0pt}{}{2n}{n}\right)\le 2^{2n}$$

and therefore

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

Taking logs, we get

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

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

$f(2n)-f(n)$$=\pi (2n)\ln 2n-\pi (n)\ln n$

$=(\pi (2n)-\pi (n))\ln n+\pi (2n)(\ln 2n-\ln n)$

$=(\pi (2n)-\pi (n))\ln n+\pi (2n)\ln 2$

$\le 2n\ln 2+2n\ln 2$

$=4n\ln 2$

Then

$f(2^t)$$=(f(2^t)-f(2^{t-1}))+(f(2^{t-1})-f(2^{t-2}))+\mathrm{\dots }+(f(2)-f(1))$

$\le 4\ln 2(2^{t-1}+2^{t-2}+\mathrm{\dots }+2^0)$

$\le 4\ln 2\cdot 2^t$

Note that $f$ is monotonically increasing, so if we choose $t$ with , then

$$f(n)\le f(2^t)\le 4\ln 2\cdot 2^t\le 4\ln 2\cdot 2n=8n\ln 2$$