Let $\pi(x)$ be a prime-counting function (the function counting the number of prime numbers less than or equal to some real number $x$. For example $\pi(5)=3$, $\pi(4)=2$). Prove by elementary (high school-level) methods that there is a function $f: \mathbb{N} \to \mathbb{R}$ and there is $N_0 \in \mathbb{N}$ such that for all $n \ge N_0$ the inequality $\pi(n) \ge f(n)$ holds and $\lim \limits_{n \to \infty} \frac{f(n)}{\sqrt{n}}=\infty$.

My work. Well known that $\pi(n) > \frac{n}{\ln n}$. But the proof of this inequality is not elementary (high school-level). I searched, but did not find other estimate. For example, it would be a good idea to prove that $\pi(n) \ge n^{0.6}$ for all $n \ge N_0$.

  • $\begingroup$ I ask about the argument which would be accessible to a high school student (olympiad problem). $\endgroup$ – Witold Jul 5 '19 at 21:18
  • 3
    $\begingroup$ @XanderHenderson I think for the OP "elementary" means "not advanced" and "school" means "not university". The former does not modify the latter. $\endgroup$ – Ethan Bolker Jul 5 '19 at 21:24
  • $\begingroup$ OK :) Not a university, but a very advanced school. $\endgroup$ – Witold Jul 5 '19 at 21:27
  • 3
    $\begingroup$ The Chebyshev bound mentioned here is both elementary and strong enough for your requirements. $\endgroup$ – Momo Jul 5 '19 at 21:47
  • $\begingroup$ @Momo thank you very much! $\endgroup$ – Witold Jul 6 '19 at 12:30

Here's a funny bound: $\forall m \geq 4 ,\pi(m) \geq \lfloor \log_2(\log_2(m)) \rfloor+1$. It's not a very good bound at all, but it does follow a very easy argument, akin to the usual proof of that there are infinitely many primes.

First, we use the easy-to-show fact that there must be another prime $p_2 < p_1^2 = 4$

Then, we generalize this, saying that there must be another prime $$p_{n+1} < \prod_{k=1}^np_k$$ And from our base cases $p_1=2$, $p_2<2^2$, we can apply this formula to get for that for $n \geq 1$, we have $$p_{n} < 2^{(2^{n-1})}\implies \log_2\log_2(p_n)+1<n$$ And finally this tells us that $\forall m\geq 4(>p_2)$, we have our funny bound!

If one proves/accepts Bertrand's postulate (that $\forall n>3, \exists p$ s.t. $p$ is prime and $n < p < 2n$), then one can use a similar argument to get a slightly less silly bound around $\log_2(n)$.

| cite | improve this answer | |

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.