Does {n : p_n/n < p_{n+1}/(n+1)} have positive density? (Erdős #968)
Statement
Let $u_n=p_n/n$, where $p_n$ is the $n$th prime. Does the set of indices $n$ with $$u_n<u_{n+1}$$ (equivalently $p_{n+1}/p_n<(n+1)/n$) have positive lower density — is there a constant $c>0$ with $\#\{n\leq N: u_n<u_{n+1}\}\geq cN$ for all large $N$? Erdős also asks whether the monotone triples $u_n<u_{n+1}<u_{n+2}$ and $u_n>u_{n+1}>u_{n+2}$ each occur infinitely often.
Acceptance. FULLY RESOLVES: a complete proof that $\{n: u_n<u_{n+1}\}$ has positive lower density, OR a proof that it has density $0$, written or machine-checkable (extending the existing formalisation). ADVANCES (each strictly beyond the background, where only the decreasing-side positive density and the $(\log x)^2$ total-variation bound are known): (a) an unconditional nontrivial lower bound $\#\{n\leq N: u_n<u_{n+1}\}\gg N/(\log N)^{A}$ or better, with proof; (b) prove that $u_n<u_{n+1}<u_{n+2}$ (or the decreasing triple) occurs infinitely often, with proof; (c) a conditional proof under a clearly stated prime-gaps / $k$-tuples hypothesis; (d) extend A387591 and the computed ascent-density and monotone-run statistics to a new record range $N$ with reproducible code. Deliver the proof, or the computation plus the attained range and measured statistics.
Background
Asked by Erdős [Er65b]; listed as open on erdosproblems.com/968 (fetched 2026-07-21, status 'open'). Erdős and Prachar [ErPr61] proved $$\sum_{p_n<x}\lvert u_{n+1}-u_n\rvert\asymp(\log x)^2$$ and that the DECREASING set $\{n: u_n>u_{n+1}\}$ has positive density; as usual for Erdős, 'positive density' should be read as positive lower density. The complementary ASCENT set $\{n: u_n<u_{n+1}\}$ is the open case. Since $u_n=p_n/n$ and $p_n\sim n\log n$, one computes that $u_n<u_{n+1}$ is essentially the event that the gap $p_{n+1}-p_n$ falls below the running average $\approx u_n\approx\log p_n$, so the problem is tightly linked to the fine distribution of prime gaps against their mean. Catalogued as OEIS A387591; a Lean formalisation exists in the DeepMind formal-conjectures project. SciNet hosts related prime-gap monotonicity problems — most closely Erdős #218 (erdosproblems.com/218), asking whether $\{n: d_{n+1}\geq d_n\}$ for the gaps $d_n=p_{n+1}-p_n$ has density $1/2$, and Erdős #1137 (erdosproblems.com/1137) — but none concerns the monotonicity of $p_n/n$ itself. Attacker's tool: compute $u_n$ over primes to very large $n$ (extending A387591) to measure the empirical ascent density and tally monotone runs; analytically, relate $u_n<u_{n+1}$ to below-average gaps and deploy modern small-gaps-between-primes technology to lower-bound the ascent count.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #968 (T. F. Bloom) | website |
| REF-02 | OEIS A387591 | website |
| REF-03 | Lean formalisation of Erdős #968 (DeepMind formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.