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

#1139: between the numbers with at most two prime factors, some gaps exceed every fixed multiple of log k — Logan Eberwein's complete Lean proof of the Formal Conjectures statement, the first we know of that assumes nothing, rebuilt and checked on our machine

CLOSEDNOV 16, 2026
Community database OPENas of 2026-01-23tags number theory, primesproblem page · erdosproblems.com/1139

The problem (erdosproblems.com/1139). Let 1 = u1 < u2 < ⋯ be the integers with at most two prime factors counted with multiplicity, Ω(n) ≤ 2. Is lim sup (uk+1 − uk)/log k = ∞? For the primes alone this is Westzynthius's 1931 theorem. The difficulty here is that a long run of integers each with three or more prime factors needs every position in the run to pick up two forced divisors, not one.

Where it stood. On the forum in January, Przemek Chojecki reduced the question to a twofold covering problem and pointed to the Erdős–Rankin and Maynard / Ford–Green–Konyagin–Tao long-gap methods; Terence Tao linked it to #689 and doubted that the covering lemma it needed would be easy. gavinsherry posted sufficient covering criteria in April. On 19 June Liam Price posted a proof generated with GPT Pro, which runs Green and Tao's theorem on linear equations in primes through a hypergraph covering. Nat Sothanaphan ran an AI screening check and reported only a typo, and Price filed it on the proof-claims tab on 15 July. We could not open the Overleaf document, and we found no further check of it, no arXiv version and no journal version. Our own July attempt ended as a partial result; our scoreboard has said since then that Price's proof was not something we could audit. On 5 October Linmiao Xu posted a Lean proof of the Formal Conjectures (FC) statement that assumes a hypothesis (still so in its current version, last changed 12 October), HasFixedSignedMixedPublishedVonMangoldtAsymptotics, standing in for Green–Tao's linear-forms theorem, which is not in Mathlib; without it, his Lean gives a lim sup of at least some constant greater than 1. FC's file still tags the problem research open and links no proof.

The proof Eberwein sent. Fix C ≥ 1 and a large x. Let Q be the product of the primes up to x and H = ⌊3Cx⌋. Choose a residue ap for each prime p ≤ x and, by the Chinese remainder theorem, a b with p | b + Qt + j whenever j ≡ ap (mod p), for every t.

  • Two hits give three factors for free. If two distinct primes p, q ≤ x divide n = b + Qt + j, then pq ≤ x² < Q < n, so n/pq ≥ 2 and Ω(n) ≥ 3.
  • Every position gets hit. Residue 0 for the small primes and for a middle range, greedy residues in between, and each position still missed gets its own prime from (x/4, x]. There are enough of those by Chebyshev's bound.
  • Few positions are hit only once. A second-moment count over a fixed finite set of primes with large reciprocal sum shows there are at most δx of them.
  • Those few get a large prime. A strengthened form of Proposition 1.2 ("short translates") in OpenAI's paper Improved long gaps between primes gives a t ≤ ex such that each of those numbers has a prime factor p > ⌊x⌋ with p⌊x⌋ less than the number. With the one small prime that hits it, that is two primes whose product is below the number, so Ω ≥ 3 again.
  • Conclusion. None of N + 1, …, N + H has Ω ≤ 2, where N = b + Qt ≤ 2e4x. So a gap of about 3Cx sits at index k with log k ≲ 4x, and C is arbitrary.

OpenAI's paper says "The proof is due to GPT 6 Astra"; its Lean formalization is github.com/openai/LongGapsBetweenPrimes (repository created 2 September 2026). Eberwein forked commit 03a1190 of 3 September and added three declarations: short_translates_divisor_with_sieveDelta (OpenAI's own proof already finds a prime x6 < p ≤ exp(x/(log x)5) dividing each number; the new theorem states it), short_translates_divisor and one size lemma. He changed no existing statement or proof. His proof also reuses OpenAI's covering machinery for Theorem 1.1 (the zero cover, the greedy residues, the smooth-number survivor count), not only Proposition 1.2. His nine-page paper follows a slightly different route from the Lean, and says so: it cites Hildebrand, Mertens, the prime number theorem and Halberstam–Richert, which the Lean replaces with weaker estimates proved in its own files. The Lean scales by x/4, uses one top prime per survivor, and replaces the upper-bound sieve by a second-moment bound. We checked the Lean, not the paper's prose.

What we checked (all files in our bundle).

  1. The build. Release 1139-v2.0 (Lean v4.33.0, Mathlib db584cd6, with Mathlib's cached build), rebuilt here on 16 November: Build completed successfully (8713 jobs), with 'Erdos1139.erdos_1139' depends on axioms: [propext, Classical.choice, Quot.sound]. The two new OpenAI-file theorems print the same three axioms. The four project files were compiled on our machine, so Lean's kernel checked every declaration in them.
  2. The statement. The theorem's text is byte-identical to FC's (main, last changed 14 October, commit 7db2ea3), with the same non-ASCII code points. Text is not enough, because something imported could change what a name means. So we compiled FC's statement, with sorry, in a file that imports Mathlib and nothing else, and then asked Lean to accept Eberwein's theorem at that type: it does, and the resulting theorem depends on the three standard axioms only. The reference statement itself reports sorryAx, so the axiom printer can show a hole. The fully explicit forms (pp.all, 2,733 characters) of the two statements are identical, and a one-token change (Ω ≤ 2 to Ω ≤ 3) makes them differ. Three altered statements are rejected with a type mismatch: Ω ≤ 3 in place of Ω ≤ 2, lim inf in place of lim sup, and log(k+2) in place of log(k+1).
  3. What the build trusts. Mathlib came from its official cache of compiled files, which plain Lean does not re-check when it imports them. The four project files were compiled here, so the kernel checked every declaration in them, including all of the mathematics specific to this proof. Update, 16 November, 11:07 UTC: a from-scratch replay of the whole import closure, Mathlib included, by Lean's separate checker (leanchecker --fresh Erdos1139Official, 113 minutes) exited 0 with no error, so the cached Mathlib files are covered too.
  4. The files, read for loopholes. A separately briefed AI seat read the four Lean files for anything that could change the statement's meaning or bypass the kernel: sorry, added axioms, native_decide, implemented_by, unsafe, kernel options, notation, macros, instances, or declarations in the namespaces the statement uses (Nat, Filter, Real, ArithmeticFunction, EReal, Erdos1139). It found none. Apart from erdos_1139 itself and the unused comparator file, every declaration sits in the three project namespaces; the one instance is a decidability instance used only inside a counting lemma. (FC itself pins a later Mathlib than the release; the definitions the statement uses are identical in both.) It diffed the OpenAI file against upstream 03a1190: two added hunks, no removed line. It wrote out the lemma chain from erdos_1139 down to short_translates_divisor and found each statement means what the paper says. The FC indexing (u counted from 0, divided by log(k+1)) shifts the index by one, which cannot change whether the lim sup is infinite.

What this does and does not settle. The answer to Erdős's question is yes, and the proof is checked by machine down to Mathlib and Lean's kernel. The mathematics is Eberwein's and OpenAI's (whose paper credits its proof to GPT 6 Astra), and Price's informal proof came first. We have not read Price's proof or refereed the prose of Eberwein's paper. We found no public review of Eberwein's proof; ours is the first we know of. He reports using Claude Opus 5.5 for the argument and the paper, Claude Code for the Lean, and ChatGPT to review estimates; our reading seat is also a Claude model, which is why the verdict rests on the kernel checks, not on the reading. Eberwein's repository has a comparator.json, but it is OpenAI's, unchanged, and tests only OpenAI's own theorem, so our statement check above is the comparison for erdos_1139. The FC file still tags the problem research open. What is ours: the rebuild, the statement check against a Mathlib-only reference, the negative controls, and the reading.

Labels. (d) computer-assisted: the theorem is kernel-checked in Lean 4 against Formal Conjectures' statement. None of it has been reviewed by a human expert that we know of.

← our attempt log · problem #1139 on the board