Skip to content

Erdős Problem #696

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: solved (not automatically the live result).
Subject areas: number theory, divisors.

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 n≥1 define h(n) as the maximum length of an increasing chain of PRIME DIVISORS p_i|n satisfying p_{i+1}≡1 mod p_i; define H(n) similarly using ALL positive divisors d_i|n. Estimate their typical sizes and ask whether H(n)/h(n)→∞ for almost every integer n. The catalogue now calls this multi-part question SOLVED (externally LEAN-reported) because it attributes comparable upper and lower estimates on the scale of the iterated logarithm log_* n, which would preclude a ratio tending to infinity.

A small example

Let n=2·3·7·29=1218. The prime factors form the chain 2,3,7,29, since 3≡1 mod2, 7≡1 mod3 and 29≡1 mod7. Thus h(1218)≥4 and H(1218)≥4. Including divisor 1 gives a five-term divisor chain 1,2,3,7,29, so H(1218)≥5 under the usual convention that 1 counts as a positive divisor. The finite chain has no implications about almost-all growth.

What is known

The maintained May 2026 update attributes log_* n ≪ h(n)≤H(n)≪log_* n for almost all n to proofs generated by GPT-5.5, with comments involving Wouter van Doorn and others. Source status is SOLVED (LEAN), but no protected GCL pinned #696.lean statement exists; the exact external formal source, theorem target, dependencies and axioms were not independently replayed. If the two-sided asymptotic estimates really hold uniformly outside a density-zero exceptional set, they yield H(n)/h(n)=O(1) for almost all n, not divergence. The initial source claim h(n)→∞ a.a. is weaker. The original Erdős [Er79e,p.81] statement remains uninspected.

GCL's current state

The original authenticated RESULT/1 source return has historical disposition PARTIAL. This status and the original research exceptions are preserved, not silently converted into a theorem verdict. The maintained Erdős source and source-specific mathematical definitions were reviewed, and this article is editorially reviewed as a source-exception-annotated explanation under EC-BULK-005-R10, effective only after the exact-hash protected admission merges.

Source interpretation and unresolved mathematical qualification: The source reports model-assisted almost-all log-star bounds, but full primary proof and external formal certificate have not been independently replayed.

The explanation is accepted for publication of established background, examples, and explicitly attributed current claims. It does not establish or formally certify the disputed original theorem, external model-assisted proof, historical interpretation, or any unreplayed Lean kernel file. Original source-fidelity and proof-review research holds remain.

What remains

Recover and independently assess the exact external source proving h(n) lower and H(n) upper on log_* scale. Check 'almost all' measures and dependence of constants, then derive boundedness of H/h as a theorem corollary. For finite n=1218, compute exact chain lengths by divisor DAG dynamic programming rather than assume exhibited chains are maximal. No Lean certificate until dependencies and kernel are replayed.

Sources and claim boundaries

Maintained #696; https://www.erdosproblems.com/696 ; https://www.erdosproblems.com/history/696 ; original [Er79e,p.81] primary pages uninspected. Authenticated original source issue. Full historical source theorem pages and external compiled Lean dependencies not all independently inspected. No new result, protected publication, browser MathJax verification or V2 admission.

Qualified editorial critical review: R10 source-exception dossier. The source-semantic exception is visible and its original research hold remains. Publication classification: REVIEWED EXPLANATORY ARTICLE WITH UNRESOLVED SOURCE/PROOF QUALIFICATIONS. Independent theorem proof or Lean certification: NOT CLAIMED.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1967 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
  • Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
  • External mathematical status: consult current problem page and its dated bibliography.

Back to catalogue · Compendium introduction