# bounds on $\pi(n)$

 $\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; 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, 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$
Title bounds on $\pi(n)$ BoundsOnpin 2013-03-22 16:23:51 2013-03-22 16:23:51 rm50 (10146) rm50 (10146) 4 rm50 (10146) Theorem msc 11A41