2
$\begingroup$

It is conjectured that for every intever $n\geq1$ there is a prime $p$ with $n^2<p<(n+1)^2$. Show that if this conjecture is true then $\pi(x)\geq\lfloor\sqrt{x}\rfloor$ for all $x\geq2$.

I understand that the conjecture is true since in every interval there must be a prime in between. And I understand that $\pi(x)$ is the number of primes less than $x$ with $x\geq2$. I am just very confused on how to setup the proof to get the desired result. Can anyone give me a hint into the direction??

$\endgroup$
11
  • 3
    $\begingroup$ The conjecture is open. The exercise is to show that it implies the given inequality. $\endgroup$ – Peter Jul 6 '20 at 20:40
  • 3
    $\begingroup$ Your reasoning does not show that the conjecture must be true. Not every interval in the natural numbers contains a prime. $\endgroup$ – D. Brogan Jul 6 '20 at 20:40
  • 1
    $\begingroup$ Assuming the conjecture, there's a prime in the interval $(1,4)$ another in the interval $(4,9)$, yet another in the interval $(9,16)$, and so on. How many such intervals are there that are $\leq x$? $\endgroup$ – saulspatz Jul 6 '20 at 20:45
  • 1
    $\begingroup$ @Peter: It was proved today?! $\endgroup$ – Brian Tung Jul 6 '20 at 20:48
  • 1
    $\begingroup$ That'd be pretty big news. $\endgroup$ – Brian Tung Jul 6 '20 at 20:51
1
$\begingroup$

Hint: At least one prime from $1^2$ to $2^2$, at least one from $2^2$ to $3^2$, ..., at least one from $(m-1)^2$ to $m^2$. How many is that?

$\endgroup$
4
  • 1
    $\begingroup$ You only get $m-1<m$ primes. $\endgroup$ – Mark Sapir Jul 6 '20 at 20:52
  • $\begingroup$ I am sorry I just don't understand where the x comes into play here?? $\endgroup$ – user287133 Jul 6 '20 at 21:15
  • $\begingroup$ @JCAA There are two primes from $1^2$ to $2^2$, so that takes care of the extra $1$. $\endgroup$ – Robert Israel Jul 7 '20 at 2:37
  • $\begingroup$ Yes, you can apply the conjecture starting with $2$. I did it starting with $3$ to be of the safe side. $\endgroup$ – Mark Sapir Jul 7 '20 at 2:52
1
$\begingroup$

4 primes between 1 and 9 plus at least one prime between every $t^2$ and $(t+1)^2$ for every $3\le t\le \lfloor \sqrt{x}\rfloor-1$. Altogether gives you $>\lfloor \sqrt{x}\rfloor$ primes smaller than $x$.

$\endgroup$
7
  • $\begingroup$ Can you elaborate on the inequality? $\endgroup$ – user287133 Jul 6 '20 at 20:53
  • $\begingroup$ Which inequality? $\endgroup$ – Mark Sapir Jul 6 '20 at 20:54
  • $\begingroup$ I fixed the answer replacing 4 by 9. $\endgroup$ – Mark Sapir Jul 6 '20 at 20:55
  • $\begingroup$ Why are you comparing between 1 and 9 since it should only be between n and n+1 which would actually be 1 and 4 for the first interval correct? And I am confused how you set up the inequality... $\endgroup$ – user287133 Jul 6 '20 at 20:58
  • $\begingroup$ If you start with $1^2$ and not $3^2$ you will get fewer than needed primes. What inequality did I set up? $\endgroup$ – Mark Sapir Jul 6 '20 at 21:02
1
$\begingroup$

Just a general remark, in fact $\pi(x)>\frac{x}{\ln{x}}>\sqrt{x}$ holds without assuming the conjecture. But let's use it, i.e. Legendre's conjecture to prove the inequality.


P1. Legendre's conjecture $\iff \pi\left((n+1)^2\right)-\pi\left(n^2\right)\geq 1$ for any integer $n\geq 1$

It's obvious.

If $\pi\left((n+1)^2\right)-\pi\left(n^2\right)\geq 1$, then $\{1,2,...,(n+1)^2\}$ contains more primes than $\{1,2,...,n^2\}$. Thus, there is at least one prime between $n^2$ and $(n+1)^2$.

If there is at least one prime between $n^2$ and $(n+1)^2$, then $\{1,2,...,(n+1)^2\}$ contains more primes than $\{1,2,...,n^2\}$. Thus $\pi\left((n+1)^2\right)-\pi\left(n^2\right)\geq 1$.


P2. $\pi(n^2)\geq n$, for any integer $n\geq 2$.

By induction:

  • it's true for $\pi(2^2)=2\geq 2$.
  • from the induction hypotheses $\pi(n^2)\geq n$ we have $$\pi\left((n+1)^2\right)=\pi\left((n+1)^2\right)-\pi\left(n^2\right)+\pi\left(n^2\right)\overset{P1}{\geq} 1+\pi\left(n^2\right)\geq 1+n$$

Finally for all $x\geq2$ $$\pi\left(x\right)\geq \pi\left(\lfloor\sqrt{x}\rfloor^2\right)\overset{P2}{\geq}\lfloor\sqrt{x}\rfloor$$

simply because

  • $\pi(x)$ is ascending ($x\geq y \Rightarrow \pi(x)\geq \pi(y)$) and
  • $x\geq \lfloor\sqrt{x}\rfloor^2$ for $x\geq 0$, from $$\sqrt{x}=\lfloor\sqrt{x}\rfloor + \{x\}\Rightarrow x = \lfloor\sqrt{x}\rfloor^2 + 2 \lfloor\sqrt{x}\rfloor \{x\} +\{x\}^2 \geq \lfloor\sqrt{x}\rfloor^2$$
$\endgroup$

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.