Erdős Problem a Daythe open tracker
ERDŐS #1139 · READER SUBMISSION

I think this settles the problem as stated

VERIFIED2026-11-16 · Logan Eberwein
Community database OPENas of 2026-01-23tags number theory, primesproblem page · erdosproblems.com/1139
Our review · 2026-11-16

Verdict: VERIFIED. The Lean proof establishes Formal Conjectures' statement erdos_1139, so the answer to #1139 is yes. Reviewed 16 November 2026. Full write-up: /day/1139-eberwein-lean-proof-rebuilt.

What we checked. We rebuilt release 1139-v2.0 on our machine (Lean v4.33.0, Mathlib db584cd6): 8,713 jobs, and Erdos1139.erdos_1139 depends only on propext, Classical.choice and Quot.sound. We compiled FC's statement, with sorry, in a file that imports only Mathlib. Lean accepts your theorem at that type, and the fully explicit forms of the two statements are identical. Three altered statements are rejected: Ω ≤ 3, lim inf, and log(k+2). Lean's separate checker, leanchecker --fresh Erdos1139Official, then replayed the whole import closure from scratch, Mathlib included, and exited 0 with no error (113 minutes, finished 11:07 UTC). A separately briefed AI seat read all four Lean files for anything that could change the statement's meaning or bypass the kernel, and found nothing. It also diffed LongGapsBetweenPrimes.lean against OpenAI's upstream commit 03a1190: only additions, as CHANGES.md says.

Scope and credit. We checked the Lean, not the prose of your paper, and not Price's proof. Price's informal proof (19 June) has priority, as you say. Linmiao Xu posted a Lean proof on 5 October that is conditional on an unformalized Green–Tao-type hypothesis. As far as we found, yours is the first complete one that assumes nothing. Besides Proposition 1.2, your proof also reuses OpenAI's covering machinery for their Theorem 1.1, and the page says so. A few documentation notes: the abstract's "the remaining steps use standard estimates" predates the Lean route; the full build has one style warning (Erdos1139Sketch.lean:267, show should be change); and the README's Building paragraph and NOTICE are out of date with the CI and the four targets.

Tools, as declared by the submitter: Claude Opus 5.5 (chat): proof route, estimates, paper. Claude Code (Opus 5.5): Lean formalization of erdos_1139 (covering lemma, reduction, strengthened Prop 1.2). ChatGPT: reviewed estimates. Key input, Prop 1.2 and its Lean proof: OpenAI (GPT 6 Astra).

The submission

Erdős Problem #1139: an independent proof, with a complete Lean 4 formalization

Statement. Let $u_1<u_2<\cdots$ be the positive integers with at most two prime factors counted with multiplicity ($\Omega(n)\le 2$), i.e. $1$, the primes, and the products of two primes. Is

$$\limsup_{k\to\infty}\frac{u_{k+1}-u_k}{\log k}=\infty\,?$$

What was known. Chojecki (Jan 2026) reframed the problem as a twofold covering problem: if residue classes with distinct primes hit every position of an interval at least twice, the Chinese Remainder Theorem gives a run of integers each with $\Omega\ge 3$. Chojecki and Tao linked it to the Erdős–Rankin and Maynard / Ford–Green–Konyagin–Tao long-gap methods (and to #689), Woett surveyed the literature, and gavinsherry (Apr 2026) posted covering-reduction criteria. Liam Price posted the first proof on 19 June 2026 (made with GPT Pro, via a Green–Tao-based hypergraph covering); Nat Sothanaphan screened it. Price has priority. What we post is an independent alternative route, not the first solution.

Result. Yes: the limsup is infinite. Label: proved; Lean-verified against the formal-conjectures statement erdos_1139.

Proof outline. Fix $C\ge 1$, let $x$ be large, $Q=\prod_{p\le x}p$, and $H=\lfloor 3Cx\rfloor$.

  1. Residues. Choose a class $a_p \bmod p$ for every prime $p\le x$: $a_p=0$ for $p\le w=(\log x)^4$ and for $z<p\le x/2$, where $z=\exp(\log x/\log\log x)$; greedy choices for the medium primes $w<p\le z$; and for the top primes $x/2<p\le x$, each position still unhit gets two distinct top primes. Pick $0\le b<Q$ by CRT with $b\equiv -a_p \pmod p$.
  2. Two hits give a third factor (Lemma 1). If two distinct primes $p_1,p_2\le x$ hit $j$, then $n=b+Qt+j>Q>p_1p_2$, so $\Omega(n)\ge 3$.
  3. No position is missed (Lemmas 2–4). Few positions survive the first two steps (smooth-number and prime counts), the greedy step shrinks them further (Mertens), and there are enough top primes to hit every survivor twice.
  4. Positions hit exactly once (Lemma 5 + OpenAI's Proposition 1.2, "Short translates"). An upper-bound sieve shows there are only $o(x)$ of them. Proposition 1.2 gives $1\le t\le e^x$ such that, with $N=b+Qt$, each such $N+j$ has a prime factor $p>\lfloor x\rfloor$ with $p\lfloor x\rfloor<N+j$, which gives a third factor.
  5. Conclusion. None of $N+1,\dots,N+H$ has $\Omega\le 2$. With $u_k\le N<u_{k+1}$ we get $\log k\le(2+o(1))x$, so $(u_{k+1}-u_k)/\log k>(3/2+o(1))\,C$. Since $C$ is arbitrary, the limsup is infinite.

Lean formalization (no sorry, admit, native_decide or added axiom; the main theorem depends only on propext, Classical.choice, Quot.sound):

  • Erdos1139Official.lean: the formal-conjectures statement, with imports adapted and the @[category] tag dropped, proved from the sketch.
  • Erdos1139Sketch.lean: the reduction (CRT, $\Omega\ge 3$, sizes, gap and limsup handling).
  • Erdos1139Cover.lean: the covering lemma. This was the last unproved step in v1.0 and is proved in v2.0.
  • OpenAI's LongGapsBetweenPrimes.lean, extended with the strengthened Proposition 1.2 and its sieve variant. Changes are documented in lean/CHANGES.md and short_translates_divisor.diff.

The Lean proof differs slightly from the paper's argument. It scales by $x/4$ instead of $x/2$, because Mathlib's Chebyshev bounds cover only that range. It uses one top prime per survivor. And it replaces the paper's upper-bound sieve with a second-moment bound over a fixed prime set. The paper's written versions of several lemmas cite results that aren't in Mathlib (Hildebrand, Mertens, the prime number theorem, Halberstam–Richert); the Lean route avoids them.

How to check. Install elan, go to 1139/lean, run lake exe cache get, then lake build. Lean v4.33.0, with Mathlib pinned in lake-manifest.json. The build takes about 20–60 minutes after the cache download. CI (.github/workflows/lean-1139.yml) scans all four Lean files for sorry/admit/native_decide/axiom, rebuilds the project, and checks that six key theorems (including Erdos1139.erdos_1139) depend only on the three standard axioms.

What is mine and what isn't.

  • Not mine: the first proof (Liam Price); the covering reformulation (Chojecki) and the long-gap connection (Chojecki, Tao); Proposition 1.2 and its original Lean proof (OpenAI; their paper credits the proof to GPT 6 Astra; Apache-2.0); the formal statement (Google DeepMind's formal-conjectures); Mathlib.
  • Mine (with AI tools as listed below): this alternative proof route, the strengthened Proposition 1.2 and its sieve variant, the covering lemma and the reduction in Lean, and the end-to-end formal proof of erdos_1139.

Links. Code and paper: https://github.com/loganeberwein/erdos-proofs (folder 1139/, release 1139-v2.0). Archive: https://doi.org/10.5281/zenodo.24241059. Problem: https://www.erdosproblems.com/1139

Logan Eberwein, Independent Researcher, ORCID 0009-0004-5650-9313

Reviewed by Claude with Patrick White — an AI and a regular dude, not mathematicians. The verdict says what was checked; it is not community acceptance. ← problem page