# Show that $\pi(n) \geq \log_2\log_2 2n$

Doing some excercise on elementary number theory I have proved that for every $$n \in \Bbb{N}, p_{n+1} \leq p_1p_2...p_n + 1$$, based on this result I'm also was able to prove that for every $$n \in \Bbb{N}, p_{n} < 2^{2^n}$$. Based on this I have now to show that for every $$n \in \Bbb{N}, \pi(n) \geq \log_2\log_2 2n$$, where $$\pi$$ is prime counting function. Here is what I tried.

In order to $$r=\log_2\log_2 2n$$ be in $$\Bbb{N}$$, let $$n=2^m, m \in N$$. Then I got $$r=log_2\log_2 2(2^m)=\log_2\log_2 2^{m+1}=\log_2 m+1$$. Once again, let $$m=2^r - 1$$, then $$r=\log_2 {(2^r-1) + 1}=\log_2 2^r=r$$. Substituting $$m$$ to $$n$$ I have $$n=2^{2^r-1}$$, and initial inequality becomes $$\pi(2^{2^r-1}) \leq r=\log_2\log_2{2^{2^r}}$$.

From this point, If I consider prime $$p_r$$, it's true that $$\pi(2^{2^r}) \geq r$$, because it's already proven that $$p_{r} < 2^{2^r}$$, so there is an $$r_{th}$$ prime between $$1$$ and $$2^{2^r}$$. But I can't figure out why it's also true for $$\pi(2^{2^r-1})$$. And that's where I stuck and need some help.

• I don't think $p_n < 2^{2^n}$ is sufficient to show that $\pi(n) \ge \log_2(\log_2(2n))$. Consider $n = p_m$: The inequality to prove is $m \ge \log_2(\log_2(2p_m))$. Using $p_m < 2^{2^m}$ would yield $m > \log_2(2^m+1)$, which isn't true. – Varun Vejalla Aug 27 at 18:44
• Is the "Based on this" for showing $\pi(n) \geqslant \log_2 \log_2 (2n)$ explicitly the inequality $p_n < 2^{2^n}$, or is it the result $p_{n+1} \leqslant p_1p_2 \cdot\ldots\cdot p_n + 1$? – Daniel Fischer Aug 27 at 19:11
• @DanielFischer, well, the excercise itself consists of three sequential subtasks: A) prove that $p_{n+1} \leq p_1p_2...p_n + 1$; B) using A, prove that $p_n < 2^{2^n}$; C) using B show that $\pi(n) \geq \log_2\log_2 2n$ – Henadzi Matuts Aug 27 at 19:35
• That's unfortunate, since from B) alone you cannot reach C). It is compatible with B) that for some $k > 1$ you have $p_k = 2^{2^k} - 3$. Then take $n = 2^{2^k} - 3$, thus $\pi(n) = k$. But $2n > 2^{2^k}$, hence $\log_2 \log_2 (2n) > k = \pi(n)$. But from A) you can reach C) by proving a slightly stronger version of B). Are you interested in that? – Daniel Fischer Aug 27 at 19:44
• Because $\pi(n)\ge\log_2\log_2(2n)\iff2^{\pi(n)}\ge\log_2(2n)=1+\log_2n\iff2^{\pi(n)}>\log_2n$ for $n\ne2^k,k\in\Bbb N$. – TheSimpliFire Aug 28 at 6:05

If we choose $$n = p_{k+1} - 1$$, we see that for $$\pi(n) \geqslant \log_2 \log_2 (2n)$$ to hold for all $$n$$ we must have $$p_{k+1} \leqslant 1 + 2^{2^k-1}$$ for all $$k$$. Unfortunately I don't see a nice induction for that using $$p_{n+1} \leqslant p_1p_2\cdot \ldots \cdot p_n + 1\,, \tag{1}$$ thus I'll do something more ugly and prove $$p_k < 2^{2^{k-1} - 1} \tag{2}$$ for $$k \geqslant 3$$ using $$(1)$$ and $$p_1 = 2, p_2 = 3$$.
The base case is immediate, $$p_3 \leqslant 2\cdot 3 + 1 = 7 < 8 = 2^3 = 2^{2^2 - 1}\,.$$ Then in the induction step for $$n \geqslant 3$$ we have $$p_{n+1} \leqslant 1 + \prod_{k = 1}^{n} p_k < 1 + 2\cdot 3 \cdot \prod_{k = 3}^{n} 2^{2^{k-1} - 1} < 2^3\cdot 2^{2^{n} - 4 - (n-2)} < 2^{2^n-1}\,.$$
And then, for $$n \leqslant 8$$ we verify $$\pi(n) \geqslant \log_2 \log_2 (2n)$$ by inspection, for $$n > 8$$ we choose $$k$$ such that $$2^{2^{k-1} - 1} < n \leqslant 2^{2^k - 1}\,.$$ Then $$k \geqslant 3$$, and by $$(2)$$ we have $$\pi(n) \geqslant k = \log_2 \log_2 \bigl(2^{2^k}\bigr) \geqslant \log_2 \log_2 (2n)\,.$$
You can be able to obtain a stricter bound for $$\pi (x)$$ since the Prime Number Theorem states that: $$\lim_{x \to \infty} \frac{\pi (x)}{x/\log(x)}=1$$ But to obtain a lower bound different from this huge theorem is not so hard. You can use Bertrand's postulate to get a lower bound. There is an elementary proof for this postulate, you can get the "$$\textbf{idea}$$" of the proof on Wikipedia. Now by Bertrand's postualate: $$\pi (n) -\pi \left(\left\lfloor\frac{n}{2}\right\rfloor\right) \geq 1$$ $$\pi \left(\left\lfloor\frac{n}{2}\right\rfloor\right)-\pi \left(\left\lfloor\frac{n}{4}\right\rfloor\right) \geq 1$$ $$...$$ $$\pi (2) - \pi (1) \geq 1$$ Now since there are $$\left\lfloor \log_2 n\right\rfloor$$ terms, add them together, we obtain: $$\pi (n) \geq \log_2 n$$ The rest which is to prove $$\log_2 n \geq \log_2 \log_2 2n$$ is obvious since $$n \geq \log_2 2n$$ can be proved by induction and take logarithm to the desired inequality.
• Thanks for you answer. Here is one thing I concern about. Given $2^n \geq \log_2 2n$ and taking it's logarithm it becomes $n \geq \log_2\log_2 2n$, which is not yields $\log_2 n \geq \log_2\log_2 2n$ as $n \geq \log_2 n$ – Henadzi Matuts Aug 27 at 20:24