Conjectured by Erdős and Pomerance [ErPo78], who proved that this set and its complement both have positive upper density. The best unconditional lower bound available is due to Lü and Wang [LuWa25], who prove that\[\#\{ n<x :P(n)<P(n+1)\} > (0.2017-o(1))x,\]and the same lower bound for the complement.

In [Er79e] Erdős also asks whether, for every $\alpha$, the density of the set of $n$ where\[P(n+1)>P(n)n^\alpha\]exists.

Teräväinen [Te18] has proved that the logarithmic density of the set of $n$ for which $P(n)<P(n+1)$ is $1/2$. Tao and Teräväinen [TaTe19] have proved that the asymptotic density is $1/2$ at 'almost all scales'.

More generally, for any $0\leq \alpha \leq1$, Teräväinen [Te18] proved that the logarithmic density of the set of $n$ for which $P(n+1)>P(n)n^\alpha$ exists and is equal to\[\int_{[0,1]^2}1_{y\geq x+\alpha}u(x)u(y)\mathrm{d}x\mathrm{d}y\]where $u(x)=x^{-1}\rho(x^{-1}-1)$ and $\rho$ is the Dickman function. Wang [Wa21] has proved the same value holds for the asymptotic density (and in particular provided an affirmative answer to the original question) conditional on the Elliott-Halberstam conjecture for friable integers.

The sequence of such $n$ is A070089 in the OEIS.

See also [372] and [928].

View the LaTeX source

This page was last edited 08 December 2025.