# Prime number logic

It is conjectured that for every intever $$n\geq1$$ there is a prime $$p$$ with $$n^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??

• The conjecture is open. The exercise is to show that it implies the given inequality. – Peter Jul 6 '20 at 20:40
• Your reasoning does not show that the conjecture must be true. Not every interval in the natural numbers contains a prime. – D. Brogan Jul 6 '20 at 20:40
• 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$? – saulspatz Jul 6 '20 at 20:45
• @Peter: It was proved today?! – Brian Tung Jul 6 '20 at 20:48
• That'd be pretty big news. – Brian Tung Jul 6 '20 at 20:51

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?

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

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$$.

• Can you elaborate on the inequality? – user287133 Jul 6 '20 at 20:53
• Which inequality? – Mark Sapir Jul 6 '20 at 20:54
• I fixed the answer replacing 4 by 9. – Mark Sapir Jul 6 '20 at 20:55
• 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... – user287133 Jul 6 '20 at 20:58
• If you start with $1^2$ and not $3^2$ you will get fewer than needed primes. What inequality did I set up? – Mark Sapir Jul 6 '20 at 21:02

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$$