Kernel-Checked Frontier Certificates for Erdős Problem 414
Ibrahim Mian, Shayaan Siddique
math.GM
Sep 14, 2026 · v1
TL;DR
Formalizes elementary lemmas and a certificate-soundness theorem in Lean 4 with Mathlib, then kernel-checks coalescence certificates for Erdős Problem 414 up to 10^8.
Abstract
Let $h(n) = n + τ(n)$, where $τ$ counts divisors. Erdős and Graham asked, after Spiro, whether the orbits of any two positive integers under $h$ eventually share a point (Problem 414 on Bloom's list). The problem is open, and a finite computation cannot close it; nothing about it has been checked by a proof kernel, and the statement in the formal-conjectures repository carries a sorry. We replay what can be certified through the Lean 4 kernel under an axiom gate (axioms exactly propext, Classical.choice, Quot.sound; no sorry; no native_decide). Three elementary facts recorded by Li, namely that coalescence is an equivalence relation, $τ(n)$ is odd exactly for squares, and $τ(n)$ is bounded by $2\sqrt{n}$ so that orbits skip no square annulus $[k^2, (k+1)^2)$, are formalized, and his frontier lemma is formalized in a window form: every orbit started below a level $N$ has a point within $\lceil 2\sqrt{N} \rceil$ below $N$. The frontier lemma becomes a certificate: the $\lceil 2\sqrt{N} \rceil$ values $τ(m)$ just below $N$ and the orbit points above $N$ until the orbits through the crossing points have merged. Its soundness is a kernel-checked theorem, and the certified rungs state that every pair of positive integers below $N$ coalesces for $N = 10^5, 10^6, 10^7, 10^8$; the certificate at $10^8$ has 44,530 entries rather than $10^8$. Every ledger and every quoted count was produced by two programs sharing no code that agree by hash. We record what is known about a non-coalescing pair and measure the exit-set sizes Li bounds. Nothing here is a proof of the conjecture.
Problem
Erdős Problem 414 asks whether the orbits of any two positive integers under h(n)=n+τ(n) eventually meet. The problem is open, and its statement in the formal-conjectures repository is left as sorry.
Approach
Li's elementary facts are formalized in Lean 4 against Mathlib under an axiom gate of propext, Classical.choice and Quot.sound only, with no sorry and no native_decide. The facts are that coalescence is an equivalence relation, that τ(n) is odd exactly for squares, and that τ(n) ≤ 2√n. Li's frontier lemma is formalized in a window form and turned into a certificate format whose checker (certOk) has a kernel-checked soundness theorem. τ values in the certificates are established from factorization certificates, and the ledgers are generated by independent programs that agree by hash.
Results
Kernel-checked theorems show that every pair of positive integers below N coalesces, for N = 10^5, 10^6, 10^7 and 10^8. The 10^8 certificate needs only 44,530 entries. Exit-set measurements for k ≤ 5000 are reported as data, not theorems.
| N | W | nodes above N | F_N | target |
|---|
| 10^5 | 633 | 903 | 11 | 104494 |
| 10^6 | 2000 | 410 | 11 | 1002242 |
| 10^7 | 6325 | 2844 | 12 | 10018018 |
| 10^8 | 20000 | 24530 | 13 | 100180126 |
Certificate sizes per certified level