Problem understanding Legendre's conjecture

"Legendre's conjecture, proposed by Adrien-Marie Legendre, states that there is a prime between $$n^2$$ and $$(n + 1)^2$$ for every positive integer $$n$$" (https://en.m.wikipedia.org/wiki/Legendre%27s_conjecture)

But there is also the proofed Bertrand's postulate:
"Bertrand's postulate is a theorem stating that for any integer $$n > 1$$, there always exists at least one prime number $$p$$ with $$n < p < 2n$$"
(https://en.m.wikipedia.org/wiki/Bertrand%27s_postulate)

My problem is that, with Bertrand's postulate, it seems logical that the Legendre's conjecture is also true, because the range from $$k$$ to $$2k$$ is smaller then the range from $$n^2$$ to $$(n+1)^2 = n^2 + 2n + 1$$. So if you choose $$k = n^2$$ there will always be a prime.

But until now the conjecture of Legendre is unproved, that's why I probably made a thinking error. But I don't know where the mistake in my logic is.

2 Answers

Actually$$\frac{(n+1)^2}{n^2}=1+\frac2n+\frac1{n^2}<2$$if $$n>2$$. In other words, $$(n+1)^2<2n^2$$ if $$n>2$$. So, in fact, the gap is smaller.

• Okay thank you ! But what is if you choose $k = n^2$. You have the range $k$ to $2k$ and the range $n^2 = k$ to $(n+1)^2$. Will there be necessarily a prime in the last interval ? Jul 30, 2019 at 10:33
• If I knew the to this question, I would have proved Legendre's conjecture, right?! Jul 30, 2019 at 10:36

Your confusion is that $$2n+1$$ means less and less as $$n$$ increases by $$n=201$$ it adds under 1 percent. By the time you hit 20001, you get it means under 1 part in 10000, compared to $$n^2$$ . Asymptotically, it means nothing. By $$n=4$$ you've surpassed the more accurate restatement of Bertrand's postulate of, there's always a prime between $$x$$ and $$2x-2$$ for $$x>3$$

• in fact Legendre's conjecture can be restated as there's always a prime between $d$ and $d+4\lfloor\sqrt{d}\rfloor+3$ if $d$ is nearby a square number.
– user645636
Oct 13, 2019 at 15:34