4
$\begingroup$

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.

Thank you in advance!

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Varun Vejalla Aug 27 at 18:44
  • $\begingroup$ 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$? $\endgroup$ – Daniel Fischer Aug 27 at 19:11
  • $\begingroup$ @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$ $\endgroup$ – Henadzi Matuts Aug 27 at 19:35
  • 1
    $\begingroup$ 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? $\endgroup$ – Daniel Fischer Aug 27 at 19:44
  • 1
    $\begingroup$ 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$. $\endgroup$ – TheSimpliFire Aug 28 at 6:05
1
$\begingroup$

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)\,.$$

Not pretty, and that for a ridiculously weak lower bound :(

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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$ $\endgroup$ – Henadzi Matuts Aug 27 at 20:24
  • $\begingroup$ Sorry, my typos. $\endgroup$ – Nguyễn Quân Aug 27 at 20:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.