# Is there a way to show that $\sqrt{p_{n}} < n$?

Is there a way to show that $\sqrt{p_{n}} < n$?

In this article, I show that $f_{2}(x)=\frac{x}{ln(x)} - \sqrt{x}$ is ascending, for $\forall x\geq e^{2}$. As a result, $\forall n \geq 3$ $$\frac{p_{n}}{ln(p_{n})} - \sqrt{p_{n}}\leq \frac{p_{n+1}}{ln(p_{n+1})} - \sqrt{p_{n+1}}$$ Also (and as a result), $\forall n \geq 3$ $$\frac{p_{n}}{ln(p_{n})} - \sqrt{p_{n}} > 0$$ Or $$\frac{\pi (p_{n})}{p_{n}/ln(p_{n})} < \frac{\pi (p_{n})}{\sqrt{p_{n}}}$$

According to PNT $$\displaystyle\smash{\lim_{n \to \infty }}\frac{\pi (p_{n})}{p_{n}/ln(p_{n})}=1$$ Or, $\forall \varepsilon >0$, $\exists N(\varepsilon )$: $\forall n>N(\varepsilon )$ $$1- \varepsilon < \frac{\pi (p_{n})}{p_{n}/ln(p_{n})} < 1+ \varepsilon$$ Or $$1- \varepsilon < \frac{\pi (p_{n})}{p_{n}/ln(p_{n})} < \frac{\pi (p_{n})}{\sqrt{p_{n}}}$$ As a result $\forall \varepsilon >0$, $\exists N(\varepsilon )$: $\forall n>N(\varepsilon )$ $$(1 - \varepsilon ) \cdot \sqrt{p_{n}} < \pi (p_{n}) = n$$

But this is not enough.

Interestingly, Andrica's conjecture is true iff function $f_{4}(x)=\pi (x) - \sqrt{x}$ is strictly ascending ($x < y \Rightarrow f(x) < f(y)$) for prime arguments.

If $f_{4}(p_{n}) < f_{4}(p_{n+1})$ then $$\pi (p_{n}) - \sqrt{p_{n}} < \pi (p_{n+1}) - \sqrt{p_{n+1}}$$ Or $$\sqrt{p_{n+1}} - \sqrt{p_{n}} < \pi (p_{n+1}) - \pi (p_{n}) =1$$

And vice-versa, if $$\sqrt{p_{n+1}} - \sqrt{p_{n}} < 1$$ Then $$-\sqrt{p_{n}} < -\sqrt{p_{n+1}} + 1$$ Or $$\pi (p_{n})-\sqrt{p_{n}} < \pi (p_{n}) + 1 -\sqrt{p_{n+1}} = \pi (p_{n+1}) -\sqrt{p_{n+1}}$$

So, if Andrica's conjecture is true then $\forall n \geq 3$ $$\pi (p_{n})-\sqrt{p_{n}} > 0$$ Or $$\sqrt{p_{n}} < \pi (p_{n})= n$$

• Even relatively crude bounds on $\pi(x)$, such as $\pi(x)\gt \frac{x}{\log x}$ are enough. Or are you looking for an elementary argument? – André Nicolas Oct 3 '12 at 22:43

The following upper bound for $p_{n}$ holds for $n\ge 6$: $$\frac{p_{n}}{n} < \ln n + \ln \ln n=\ln(n\ln n) < n,$$ so $p_n < n^2$ in those cases. It clearly also holds for $p_2=3<4$, $p_3=5<9$, $p_4=7<16$, and $p_5=11<25$ (though it fails for $p_1=2\not<1$).
This follows from Rosser's result that except at the beginning, $$\pi(x)\gt \frac{x}{\log x}.$$ Just put $x=p_n$. We need to do hand calculation until $\log x>\sqrt{x}$, which happens early.
Remark: We used Rosser's not so easy result only for convenience. The lower bound on $\pi(x)$ obtained by Chebyshev in the middle of the $19$th century, using an "elementary" argument, is already enough.
• I've missed this too en.wikipedia.org/wiki/…, the Vallée-Poussin proof's ... so, basically $\pi (x) > \frac{x}{ln(x) - (1-\varepsilon )} > \frac{x}{ln(x)} > \sqrt{x}$ from some $x$ onwards – rtybase Oct 3 '12 at 23:21