PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: High Entry average rating: Very high
[parent] 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 $ n$ is an integer, write $ n=\prod p_i^{r_i}$ where the $ p_i$ 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 $ 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
$\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 $ 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$.
$\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 $ 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$
$\displaystyle \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
$\displaystyle n^{\pi(n)}\geq\binom{n}{r}\ \forall r$
Summing from $ r=1$ to $ r=n-1$, 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 $ 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
$\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$  

Note that $ f$ is monotonically increasing, so if we choose $ t$ with $ 2^{t-1}\leq n<2^t$, then
$\displaystyle f(n)\leq f(2^t)\leq 4\ln 2\cdot 2^t\leq 4\ln 2\cdot 2n=8n\ln 2 $



"bounds on $\pi(n)$" is owned by rm50.
(view preamble | get metadata)

View style:


This object's parent.
Log in to rate this entry.
(view current ratings)

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 $\pi(n)$, born on 2006-11-11.
Object id is 8545, canonical name is BoundsOnPin.
Accessed 925 times total.

Classification:
AMS MSC11A41 (Number theory :: Elementary number theory :: Primes)

Pending Errata and Addenda
None.
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | prove | add result | add corollary | add example | add (any)