What is the best unconditional upper bound for $p_{n^2}-p_{(n-1)^2}$ such that $p_n$ is the $n$-th prime number?

Asymptotics suggest it's somewhere near $4 n \ln n$, but how to prove this?

Edit: it's known that there is a prime between $[x,x+x^{13/23}]$, so one can bound $p_{n^2}-p_{(n-1)^2} \leq 2 n n^{13/23}$, but are there any better bounds?

  • 3
    $\begingroup$ The best unconditional upper bound is $p_{n^2}-p_{(n-1)^2}$. $\endgroup$
    – YCor
    Aug 11, 2017 at 14:31
  • 3
    $\begingroup$ OK, then, what is the best unconditional upper bound restricted to the class of Hardy's lograithmico-exponential functions (G.H. Hardy, Orders of Infinity: Cambriddge Univ. Press, 1910; a good definition is in Concrete Mathematics section 9.1) which include all the iterated logs and exponentials, powers, and so forth but no blatantly number-theoretic functions? $\endgroup$ Aug 11, 2017 at 23:13

2 Answers 2


By the results of

Baker, R.C.; Harman, G.; Pintz, J., The difference between consecutive primes. II, Proc. Lond. Math. Soc., III. Ser. 83, No.3, 532-562 (2001). ZBL1016.11037.

the number of primes in the interval $[x, x+x^{0.525}]$ is $\gg x^{0.525}/\log x$ for $x$ large enough (see the final inequality of the paper); in particular, $p_{(n-1)^2} + p_{(n-1)^2}^{0.525} \geq p_{n^2}$ for $n$ large enough. This gives a bound of the form $O( n^{1.05} \log^{0.525} n )$. Any improvement on this bound would likely improve the Baker-Harman-Pintz bound on large prime gaps, so I doubt one can do much better using what is in the literature. Of course, the situation is much better on RH or even on LH (the Lindelöf Hypothesis). (Also, one can show the expected bound of $O(n \log n)$ for almost all $n$, with a fairly small exceptional set, using the known results on primes in short intervals on average.)


Using unconditional results cited by Dusart in this paper in their simple versions obtained by Robin and Salvy which are of the form $$ p_k \leq k\left( \log k+\log\log k-1+\frac{\log\log k-2}{\log k}\right), $$ and $$ p_k \geq k\left( \log k+\log\log k-1+\frac{\log\log k-2.1}{\log k}\right), $$ for $n$ large enough (the first holds after $k\geq 688 383$, the second after $k\geq 3$) if my arithmetic is correct we have the inequality $$ p_{n^2}-p_{(n-1)^2} \leq (1+\varepsilon)~4n^2 \log n $$ for any $\varepsilon>0$ for $n$ large enough.

Edit: This answer is quite weak, it turns out.

  • 2
    $\begingroup$ The bound here will be more like $n^2 / \log n$, I think. (The difference between 2 and 2.1 is actually quite significant!) $\endgroup$
    – Terry Tao
    Aug 11, 2017 at 23:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.