A Kernel-Checked Exclusion Certificate for Erdős Problem 647
Ibrahim Mian, Shayaan Siddique
cs.LO
Aug 18, 2026 · v1
math.NT
TL;DR
Formalizes in Lean 4 with Mathlib an exclusion certificate replaying 6.6M factorization witnesses to rule out Erdős problem 647 solutions in (24,10^9], using only standard axioms.
Abstract
Erdős problem 647 asks whether any $n > 24$ satisfies $\max_{m<n}(m + τ(m)) \le n + 2$, where $τ$ is the divisor-count function. Computational searches have excluded solutions up to $10^{12}$ by direct sieve and up to roughly $9.17 \times 10^{18}$ within a modular reduction whose Lean component relies on native_decide; those computations sit outside any proof kernel. We give the first exclusion checked end to end by one: no solution exists with $24 < n \le 10^9$, proved in Lean 4 with axiom closure exactly {propext, Classical.choice, Quot.sound} – no sorry, no native_decide, no problem-specific axiom. The proof replays a chain of 6,685,922 factorization witnesses whose excluded intervals concatenate across $(24, 10^9]$; it needs no primality facts beyond primes below 1024, and it is the finite, fully proved form of a domination-interval argument whose asymptotic step was the identified gap in a withdrawn January 2026 claim on this problem. The generation pipeline is cross-checked by two further independent implementations, the compiled development replays through the standalone lean4checker, and two from-source verification legs – Lean toolchains compiled from source by gcc and by clang, mathlib rebuilt with no cache – reproduce the committed certificates byte for byte, with olean digests identical across three builds on two architectures. Our range is three to ten orders of magnitude below the computational frontiers we cite; the contribution is the trust base, not the range.
Problem
Erdős problem 647 asks whether any n>24 satisfies max_{m<n}(m+τ(m)) ≤ n+2. Prior computational exclusions relied on untrusted code or Lean's native_decide plus problem-specific axioms, outside any proof kernel.
Approach
A witness-chain certificate stores, for each kill witness m, the maximal prime powers below 1024 dividing it, from which the kernel recomputes a divisor-count lower bound with a doubling rule licensed by maximality. A small trusted soundness layer proves that a passing Boolean checker (chainOk) yields, for every covered n, a witness refuting the inequality, bridged to the pinned formal-conjectures predicate. Bulk certificate data is checked by structural recursion via decide, with no native_decide, sorry, or extra axioms. Generation is cross-validated by two independent replay implementations and reproduced byte-for-byte from source-built toolchains.
Results
Proved in Lean 4 that no n with 24<n≤10^9 satisfies the inequality, with axiom closure exactly {propext, Classical.choice, Quot.sound}. The 10^7 and 10^8 rungs run in CI and reproduce on two machines; the 10^9 rung was kernel-checked once. The certified range sits within a factor of a thousand of the uncertified sieve frontier.