Does $\{n : P(n)<P(n+1)\}$ have natural density exactly $1/2$? (Erdős #371)
Statement
For a positive integer $n$ let $P(n)$ denote the largest prime factor of $n$. Prove that the set $$\{\,n : P(n) < P(n+1)\,\}$$ has natural (asymptotic) density $1/2$. More generally, Erdős asked whether for every real $\alpha$ the set $\{n : P(n+1) > P(n)\,n^{\alpha}\}$ has a natural density.
Acceptance. FULLY RESOLVES: a complete unconditional proof (machine-checkable in Lean — a statement formalisation already exists — preferred, else a full written proof) that $\{n : P(n)<P(n+1)\}$ has natural density exactly $1/2$; optionally the stronger result that $\{n : P(n+1)>P(n)n^{\alpha}\}$ has a natural density for every $\alpha$. ADVANCES (each independently checkable): a strictly better unconditional lower bound on $\#\{n<x : P(n)<P(n+1)\}/x$ than the best stated in the background (currently $0.2017-o(1)$), with proof; OR removal of a stated hypothesis from a known conditional density result (e.g. deriving Wang's conclusion under a strictly weaker assumption), with proof; OR a new unconditional two-sided bracket on the natural upper and lower densities, with proof. Deliver the proof file or the written proof establishing the improved bound.
Background
Conjectured by Erdős and Pomerance [ErPo78, p.320] and restated in [Er79e], [ErGr80, p.70], [Er85c, p.82] and Vaughan's list [Va99, 1.10]; listed as open on erdosproblems.com/371 (fetched 2026-07-13, status 'open', tagged 'number theory'). The sequence of $n$ with $P(n)<P(n+1)$ is OEIS A070089, and a Lean formalisation of the statement exists in the DeepMind formal-conjectures repository. Frontier: Erdős and Pomerance proved the set and its complement each have positive upper density. Teräväinen [Te18] proved the *logarithmic* density of $\{n : P(n)<P(n+1)\}$ is exactly $1/2$, and more generally that for each $0\leq\alpha\leq 1$ the logarithmic density of $\{n : P(n+1)>P(n)n^{\alpha}\}$ exists and equals $\int_{[0,1]^2} \mathbf{1}_{y\geq x+\alpha}\,u(x)u(y)\,dx\,dy$, where $u(x)=x^{-1}\rho(x^{-1}-1)$ and $\rho$ is the Dickman function. Tao and Teräväinen [TaTe19] showed the asymptotic density is $1/2$ at 'almost all scales'. Wang [Wa21] proved the asymptotic density equals the same value — settling the original question — *conditional* on the Elliott–Halberstam conjecture for friable (smooth) integers. The best unconditional lower bound is due to Lü and Wang [LuWa25]: $\#\{n<x : P(n)<P(n+1)\} > (0.2017-o(1))x$, with the same bound for the complement. Thus the density is pinned at $1/2$ only in logarithmic density or conditionally; the unconditional natural-density statement is the open target. See also Erdős #372 and #928. The attacker's tool: multiplicative-function / friable-integer analytic machinery (Dickman-$\rho$ asymptotics, level-of-distribution inputs), with computation of A070089 to track the empirical density and probe the 'almost all scales' phenomenon.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #371 (T. F. Bloom) | website |
| REF-02 | OEIS A070089 — n such that P(n) < P(n+1), where P is the largest prime factor | website |
| REF-03 | Lean formalisation of Erdős #371 (DeepMind formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.