Can one prove this is false if we replace $k^2+1$ by $e^{(1+\epsilon)\sqrt{k}}+C_\epsilon$, for all $\epsilon>0$, where $C_\epsilon>0$ is some constant?
Can one prove this is false if we replace $k^2+1$ by $e^{(1+\epsilon)\sqrt{k}}+C_\epsilon$, for all $\epsilon>0$, where $C_\epsilon>0$ is some constant?
Erdős observed that Cramer's conjecture \[\limsup_{k\to \infty} \frac{p_{k+1}-p_k}{(\log k)^2}=1\] implies that for all $\epsilon>0$ and all sufficiently large $n$ there exists some $k$ such that \[p(n+k)>e^{(1-\epsilon)\sqrt{k}}.\] There is now evidence, however, that Cramer's conjecture is false; a more refined heuristic by Granville [Gr95] suggests this $\limsup$ is $2e^{-\gamma}\approx 1.119\cdots$, and so perhaps the $1+\epsilon$ in the second question should be replaced by $2e^{-\gamma}+\epsilon$.