Does Andrica's conjecture imply Legendre's conjecture? I have the following reasoning.

Let $p_n$ denote the $n$th prime. Recall that Andrica's conjecture is the following statement: $$ \sqrt{p_{n+1}}-\sqrt{p_n}<1, $$

for all positive nonzero integer $n$. On the other hand, Legendre's conjecture states that there is a prime number between $m^2$ and $(m+1)^2$ for every positive integer $m$. I then propose the following Theorem.

Theorem 1. Andrica's conjecture implies Legendre's conjecture.

Proof. Let $g_n$ denote the $n$th prime gap. Following Andrica's conjecture, we have $g_{n}<2{\sqrt {p_{n}}}+1$, or equivalently $p_{n+1}<2{\sqrt {p_{n}}}+1+p_{n}$.

Now let $N$ be a positive integer greater than $2$ and $p_{n}$ the greatest prime smaller than or equal to $(N-1)^2$. We then have:

\begin{align*} (N-1)^2 & < p_{n+1}\\ & < 2{\sqrt {p_{n}}}+1+p_{n} \\ & < (\sqrt {p_{n}} + 1)^2. \end{align*}

But since $p_{n}<(N-1)^2<p_{n+1}$, we have: \begin{align*} (N-1)^2 & < (\sqrt {p_{n}} + 1)^2 \\ & < (\sqrt {(N-1)^2} + 1)^2 \\ & < (N-1+1)^2 \\ & < N^2. \end{align*}

We have therefore shown that assuming Andrica's conjecture, $(N-1)^2<p_{n+1}<N^2$, i.e., that there is always a prime between $(N-1)^2$ and $N^2$ for all positive integer $N>2$. $$\tag*{$\square$}$$

I recall reading somewhere that one can not imply Legendre's conjecture from Andrica's, so I must be missing something here. What is it?

  • $\begingroup$ You have a typo, "But since $p_n < p_{n+1} < (N-1)^2$" ought to be "But since $p_n < (N-1)^2 < p_{n+1}$", and after that you forgot to mention $p_{n+1}$ so you just state $(N-1)^2 < N^2$. Should be $(N-1)^2 < p_{n+1} < (\sqrt{p_n} + 1)^2$ etc. Yes, Andrica's conjecture implies Legendre's conjecture. $\endgroup$ – Daniel Fischer Apr 10 '18 at 15:11
  • $\begingroup$ @DanielFischer Thank you, typos corrected. If you post an answer I will accept it. $\endgroup$ – Klangen Apr 17 '18 at 12:25
  • $\begingroup$ So that means Legendre's conjecture is true for twin primes. $\endgroup$ – Mr Pie Jan 21 at 9:57

Indeed, the truth of Andrica's conjecture implies the truth of Legendre's conjecture, and your proof is correct.

As a matter of style, it is not good that you switch from $m^2$ and $(m+1)^2$ used in the statement of Legendre's conjecture to using $(N-1)^2$ and $N^2$ in the proof, it would be better to use the same notation in both. And I would leave the prime gap $g_n$ out of it and write

\begin{align} (N-1)^2 &< p_{n+1} \\ &= (\sqrt{p_{n+1}})^2 \\ &< (\sqrt{p_n} + 1)^2 \tag{Andrica's conjecture}\\ &\leqslant \bigl((N-1) + 1\bigr)^2 \tag{$p_n \leqslant (N-1)^2$}\\ &= N^2\,. \end{align}

But the latter is a matter of taste.


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.