Erdős Problem #371
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: number theory.
Read this status correctly
The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.
The question in plain language
For an integer \(n>1\), let \(P(n)\) be its largest prime factor. For example, \(P(12)=3\) because \(12=2^2\cdot3\), while \(P(13)=13\). Erdős Problem #371 asks whether, among the positive integers, the set
has asymptotic density \(1/2\). In other words, if we count the integers \(n\leq x\) for which the largest prime factor increases when we move from \(n\) to \(n+1\), does that count divided by \(x\) tend to one half as \(x\) becomes large?
The phrase “density” here means the ordinary, or asymptotic, density. It is stronger than a statement about a logarithmic average, and stronger than a statement that holds only along most large cutoffs. The finite initial values also require a convention for \(P(1)\); they do not affect an asymptotic density, but they do matter when a formal statement quantifies over all natural numbers.
A small example
Here is an exact check for \(2\leq n\leq30\). Factoring each integer and taking its largest prime factor gives
and the remaining values \(n=17,\ldots,30\) contribute
Thus the exact count is \(17\) successes out of \(29\), namely \(17/29\). This was checked by trial division: for instance, \(P(20)=5<P(21)=7\), whereas \(P(19)=19>P(20)=5\). The calculation illustrates the predicate and is reproducible using only integer factorization. It does not establish a limiting density, let alone the value \(1/2\); a finite prefix can fluctuate substantially.
What is known
The frozen catalogue entry at commit 536408716724a2402bdfa7c1d764bf83d64a8c89, Git blob 4e60263a80af6207aca494d2e1388e44fa372889, records the informal status as open, last updated 2025-08-31. It records number-theory tags, no prize, and sequence A070089. The live Erdős Problems entry uses the same basic statement and currently presents the problem as open.
The foundational primary source is Paul Erdős and Carl Pomerance, “On the largest prime factors of \(n\) and \(n+1\),” Aequationes Mathematicae 17 (1978), 311–321, DOI 10.1007/BF01818569, with an openly readable source copy. On p. 312 the authors say that they cannot prove the expected density \(1/2\). Their Theorem 1 says that, for every \(\varepsilon>0\), the integers for which \(P(n)\) and \(P(n+1)\) are within a multiplicative factor \(x^{\delta}\) form fewer than \(\varepsilon x\) for sufficiently large \(x\), for a suitable \(\delta>0\). In §6 (p. 319) they deduce positive lower density for each direction of comparison, but not density \(1/2\).
Later results improve the interface without closing the ordinary-density conjecture. The maintained page reports that Teräväinen proved logarithmic density \(1/2\); Tao and Teräväinen proved ordinary density \(1/2\) at almost all scales; and Wang obtained the ordinary density value conditionally on an Elliott–Halberstam conjecture for friable integers. Those are different conclusions from an unconditional limit at every cutoff. The page also reports a 2025 lower bound of \(0.2017-o(1)\) for each direction, but this article treats that as maintained-page metadata unless the cited primary text is separately checked.
GCL's current state
The original GCL issue #1641 is the source-and-bounded-research-design assignment for this problem. Its pinned formal provider is google-deepmind/formal-conjectures at commit 85f863718beeec7b58a3a1926ee92e3472bc2020, file FormalConjectures/ErdosProblems/371.lean, blob d1b6ad23fa1d74081baafab05470fda722d307ed. It states the comparison using Nat.maxPrimeFac and asks for density \(1/2\), but its proof is by sorry. The source file has no explicit restriction \(n>1\) and no visible convention check for the values at \(0\) and \(1\). That is a formal semantic review point, not evidence of a proof or of equivalence with every natural-language convention.
The issue had no existing comments when audited, so there is no protected GCL result to summarize. The original SOURCE RESULT/1 citation is authenticated original RESULT/1. This article therefore reports the pinned evidence and the primary-source map, not a GCL certification. V2 ledger state alone decides accepted coverage.
What remains
The central unresolved claim is the unconditional ordinary density \(1/2\). A useful bounded successor should first reconcile the formal predicate with the source convention: state the ambient type, define the value at \(1\), and show that deleting finitely many boundary cases leaves the density unchanged. It can then formalize a finite exact-count lemma for a declared cutoff and compare it with a direct factorization computation.
That task would be valuable but deliberately modest. The 1978 theorem gives positive-density separation and the later results give weaker or conditional forms of the expected balance; neither supplies the missing all-scales unconditional limit. A finite computation can catch reversed inequalities, indexing errors, or an incorrect largest-prime-factor routine, but cannot resolve the analytic number-theory problem.
Any stronger successor must name the precise external theorem it uses, preserve its hypotheses, and stop when those hypotheses or the source text cannot be verified.
Sources and claim boundaries
- Original issue #1641: assignment, pinned source packet, and formal-file identity; no RESULT/1 comment was present at audit time.
- Frozen catalogue commit and blob
4e60263a80af6207aca494d2e1388e44fa372889: snapshot status and metadata, not theorem authority. - Erdős–Pomerance (1978): primary theorem and page locations cited above.
- Live Problem 371 page: maintained statement and reported later literature; live status may change.
- Pinned FormalConjectures file: a theorem statement with
sorry, not a replayed proof or mathematical certification.
No claim here promotes the conjecture to proved, claims independent formal verification, or treats a conditional theorem as an unconditional solution. The article is a source-bound explanation of the question and its evidence boundaries.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1641 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: PROTECTED_READY_BACKLOG.
- Formal-statement coverage: A provider statement was included in the pinned snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.