|
|
|
|
![[parent]](http://images.planetmath.org:8080/images/uparrow.png)
bounds on 
|
(Theorem)
|
|
|
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
Lemma 1 $$ ord_p(n!)=\sum_{i=1}^{\infty}\lfloor \frac{n}{p^i}\rfloo $$
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)- $$
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 $$ 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- $$ But $n^{\pi(n)}\geq 2$ since $n\geq 2$ , so $$ n^{\pi(n)+1}\geq 2^ $$ 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 \begin{eqnarray*} &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\\ &&\leq 2n\ln 2+2n\ln 2\\ &&=4n\ln 2 \end{eqnarray*}Then \begin{eqnarray*} &f(2^t)&=(f(2^t)-f(2^{t-1}))+(f(2^{t-1})-f(2^{t-2}))+\ldots+(f(2)-f(1))\\ &&\leq 4 \ln 2(2^{t-1}+2^{t-2}+\ldots+2^0)\\ &&\leq 4\ln 2\cdot 2^t \end{eqnarray*}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 $$
|
"bounds on  " is owned by rm50.
|
|
(view preamble | get metadata)
Cross-references: monotonically increasing, logs, denominator, numerator, occur ins, side, terms, finite, sum, multiples, number, proof, primes, integer, bounded, function
There is 1 reference to this entry.
This is version 1 of bounds on  , born on 2006-11-11.
Object id is 8545, canonical name is BoundsOnPin.
Accessed 1364 times total.
Classification:
| AMS MSC: | 11A41 (Number theory :: Elementary number theory :: Primes) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|
