Growth of pi(x)

Proposition 1

Prove $\pi(x)\geq \log(\log(x))$ for $x>2$, where $\pi(x)$ is the number of positive primes less than x.

Proof:

It is obvious that $p_{n+1}\leq p_1p_2...p_n+1$. Consider $p_i<2^{2^i}$, so $p_{n+1}\leq 2^{2^{n+1}-2} \leq 2^{2^{n+1}}$.

So $\pi(x)\geq \pi(e^{e^{n-1}}) \geq \pi(e^{2^n}) \geq \pi(2^{2^n}) \geq n \geq \log(\log(x))$

Proposition 2

Prove $\pi(x)\geq \log{x/2}\log{2}$

Proof:

For a set of primes $S$, define $f_S(x)$ as the number of integers n that $1 \leq n\leq x$ and $\gamma(n)\subset S$, where $\gamma(n)$ is the prime set that dividing $n$.

Consider $n=s^2t$, where $t$ is square free.

The number of choice of t shall be $t=p_1^{\{0,1\}}p_2^{\{0,1\}}...p_l^{\{0,1\}}$ that is $2^{\pi(x)}$.

For $n \leq x$, we have $s\leq\sqrt{x}$.

That is $f_S(x)\leq 2^{\pi(x)}\sqrt{x}$.

So $f_S(x)=x\leq2^{\pi(x)}\sqrt{x}$.

Proposition 3

Prove $\vartheta(x) < (4\log2)x$, where $\vartheta(x) = \sum_{p\leq x}\log{p}$ (Chebyshev function).

Proof:

Consider: $$2^{2n} > {2n \choose n} = \prod_{n+1}^{2n}a > \prod_{n}^{2n}p$$ Where p is prime that $n<p<2n$.

Therefore: $$2n\log{2}>\vartheta(2n) - \vartheta(n)$$ By summing up all this formula by $n=1,2,4,...,2^{m-1}$. $$2^{m+1}\log2 > 2^{m+1}-2\log{2} > \vartheta(2^m)$$ Let $2^{m-1} < x < 2^m$: $$\vartheta(x) < \vartheta(2^m) < 2^{m+1}\log{2} = 4\log(2)2^{m-1} < 4\log(2)x$$

Corollary 1

$\pi(x) < C \frac{x}{\log{x}}$, where C is some positive constant.

Proof:

By proposition 3: $$\vartheta(x) \geq \sum_{p>\sqrt{x}}^{p\leq x}\log{p}$$ So we have $$\vartheta(x) \geq \log(\sqrt{x})(\pi(x)-\pi(\sqrt{x}))$$ So: $$\pi(x) \leq \frac{2}{\log{x}}\vartheta(x) + \sqrt{x} \leq 2\frac{x}{\log{x}}$$

Corollary 2

Prove that $\frac{\pi(x)}{x}\to 0$ as $x\to\infin$

Proof:

Consider: $$\lim_{x\to\infin}\frac{\pi(x)}{x} \leq \frac{\phi(n)}{n}$$ Since the given primes are always fall into relatively prime of n, for all positive n.

Remind that: $$\phi(n) = n\prod_{p|n}(1-\frac{1}{p})$$

$$\frac{\phi(n)}{n} = \prod_{p|n}(1-\frac{1}{p})$$

When $n\to \infin$, each term of product is smaller than 1. $$\lim_{x\to\infin}\frac{\pi(x)}{x} = 0$$

Proposition 4

$\pi(x) > C \frac{x}{\log{x}}$ when C is some positive constant.

Proof:

First prove a little proposition: $$\text{ord}_pn! =\sum_{i=1}^n \text{ord}_pi = \sum_{i=1}^{\infin}\lfloor\frac{n}{p^i}\rfloor$$ Now consider: $${2n \choose n} \geq 2^n$$

$$\text{ord}_p {2n \choose n} = \text{ord}_p \frac{(2n)!}{(n!)^2} = \text{ord}_p (2n)! -2\text{ord}_p(n!)$$

$$\text{ord}_p {2n \choose n} = \sum_{i=1}^{t}(\lfloor\frac{2n}{p^i}\rfloor-2\lfloor\frac{n}{p^i}\rfloor)$$

Since $\lfloor\frac{2n}{p^i}\rfloor-2\lfloor\frac{n}{p^i}\rfloor$ is always 0 or 1. $$\text{ord}_p {2n \choose n} \leq t$$ Here t is the largest integer that $p^t\leq 2n$ and $t =\lfloor \frac{\log{2n}}{\log{p}} \rfloor$ $$\text{ord}_p {2n \choose n} \leq \frac{\log{2n}}{\log{p}}$$ So: $$2^n \leq {2n \choose n} \leq \prod_{p<2n}p^{\lfloor\frac{\log{2n}}{\log{p}} \rfloor}$$

$$n\log2 \leq \sum_{p<2n} \lfloor\frac{\log{2n}}{\log{p}} \rfloor \log{p}$$

For those $p > \log{\sqrt{2n}}$, $ \lfloor\frac{\log{2n}}{\log{p}} \rfloor = 1$ $$n\log2 \leq \sum_{p<\sqrt{2n}} \lfloor\frac{\log{2n}}{\log{p}} \rfloor \log{p} + \sum_{p>\sqrt{2n}}^{p<2n}\log{p}$$

$$n\log2 \leq \sqrt{2n}\log{2n} + \vartheta(2n)$$

Now we have: $$\vartheta(2n) > n\log2 - \sqrt{2n}\log{2n}$$ The second part is relatively small when $n\to \infin$

So when n is large enough: $$\vartheta(2n) > Cn$$ That is: $$\vartheta(x) > C x$$ Now bound with $\pi(x)$； $$\pi(x) \geq \frac{\vartheta(x)}{\log{x}} > c \frac{x}{\log{x}}$$ So $\pi(x)$ is bound by $\vartheta(x)$ on both side, that means $$\pi(x) \frac{\log{x}}{x} \to 1\ \text{as}\ x\to \infin$$ Which is Prime Number Theorem