Skip to content

Erdős Problem #248

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

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.

Documentary explanation. Editorial acceptance is determined by the protected V2 admissions ledger and the exact manuscript source hash. This article does not confer mathematical certification.

The question in plain language

For a positive integer \(m\), let \(\omega(m)\) be the number of different primes dividing \(m\). Thus \(\omega(12)=2\), because only \(2\) and \(3\) occur. Let \(\Omega(m)\) count prime factors with multiplicity: \(\Omega(12)=3\), since \(12=2^2\cdot3\). The original problem asks whether there is one absolute constant \(C>0\) and infinitely many positive integers \(n\) for which every positive shift \(k\) obeys

\[ \omega(n+k)\leq Ck. \]

The quantifiers matter. The same \(C\) must work for every \(k\geq1\) and for all members of one infinite set of \(n\); it is not a constant chosen afresh for each shift or each \(n\). The notation \(\omega(n+k)\ll k\) is shorthand for precisely this kind of absolute-constant bound.

The printed source is P. Erdős and R. L. Graham, Old and New Problems and Results in Combinatorial Number Theory (1980), p. 61, where the notation for the prime-factor count is not defined in the local problem sentence. The maintained page Erdős Problem 248 also cites P. Erdős, “Remarks on some problems in number theory” (1974), pp. 197–202, as [Er74b]. The authenticated GCL source audit found the exact printed formulation on Erdős–Graham p. 61 and did not find this exact statement in the cited 1974 scan. That is a provenance conflict, not a mathematical contradiction.

A small example

The finite calculation below is an illustration, not evidence for infinitude. Take \(n=1\), \(C=1\), and inspect \(1\leq k\leq8\). The values of \(n+k\) are \(2,3,4,5,6,7,8,9\), and their distinct-prime counts are \(1,1,1,1,2,1,1,1\). Each is at most \(k\), so this finite prefix passes the required inequality; the largest observed ratio \(\omega(n+k)/k\) is \(1\).

from collections import Counter

def factor_counts(m):
    f, p = Counter(), 2
    while p * p <= m:
        while m % p == 0:
            f[p] += 1
            m //= p
        p += 1
    if m > 1:
        f[m] += 1
    return f

def omega(m): return len(factor_counts(m))
def Omega(m): return sum(factor_counts(m).values())

rows = [(k, omega(1+k), Omega(1+k), omega(1+k) <= k)
        for k in range(1, 9)]
print(rows)
print(all(row[-1] for row in rows), max(w/k for k, w, _, _ in rows))
print(omega(12), Omega(12))

Running this gives [(1,1,1,True), (2,1,1,True), (3,1,2,True), (4,1,1,True), (5,2,2,True), (6,1,1,True), (7,1,3,True), (8,1,2,True)], followed by True 1.0 and 2 3. This independently checks both the example arithmetic and the elementary inequality \(\omega(m)\leq\Omega(m)\) on the displayed inputs. It does not test the unbounded quantifier or establish a second suitable \(n\).

What is known

The original question is a solved literature problem, not an open conjecture. T. Tao and J. Teräväinen, “Quantitative correlations and some problems on prime factors of consecutive integers,” arXiv:2512.01739v2 (25 April 2026), prove the stronger statement in Theorem 1.1, printed p. 2:

\[ \exists C>0\;\text{such that}\;\left\{n\in\mathbb N_{>0}:\forall k\in\mathbb N_{>0},\ \omega(n+k)\leq\Omega(n+k)\leq Ck\right\}\text{ is infinite}. \]

Here \(\Omega\) is the multiplicity-counting function. The first inequality is elementary, while the second is the deep sieve theorem. In §2, printed pp. 11–24, Tao and Teräväinen construct a random \(n\) in a large interval and arrange a tail estimate of the form

\[ \mathbb P\bigl(\Omega(\mathbf n+k)>Ck\bigr)\leq\frac{1}{10k^{3/2}}. \]

Because \(\sum_{k\geq1}(10k^{3/2})^{-1}<1\), the union bound leaves positive probability that all positive shifts satisfy the bound simultaneously. The construction uses a growing-dimensional Maynard-type/Selberg sieve and moment estimates; those are borrowed results from the named paper, not a proof supplied by this article. The implication to Erdős Problem 248 is therefore exact once their theorem is accepted, but I have not independently reproduced their full sieve argument.

There is a later improvement in C. F. Lau, “On the Number of Prime Factors of Consecutive Integers,” arXiv:2604.15042v2 (24 June 2026), Theorem 1.1, printed p. 3: infinitely many positive \(n\) satisfy \(\omega(n+k)\leq\Omega(n+k)\leq C\log k\) for every \(k\geq2\). The missing \(k=1\) is why this should be reported as a related stronger bound, not silently substituted for Tao–Teräväinen’s exact all-positive-shifts theorem. The official page reports both results.

GCL's current state

The protected catalogue snapshot records problem 248 as informal proved (last update 2025-12-02), formal status Lean (2026-08-23), overall status proved (Lean), and formalized: yes (2025-08-31). The live teorth/erdosproblems entry at the pinned commit 536408716724a2402bdfa7c1d764bf83d64a8c89 and the current main entry retain those fields. The live problem page was last edited 17 April 2026, says the statement is resolved, and marks the statement formalised. These are catalogue and website statuses, not GCL mathematical certification.

The original cohort intake snapshot predated the source audit. A subsequent authenticated source return is recorded for issue #1517 is open and now has one comment, RESULT/1, created 13 October 2026 UTC. It is marked STATUS_CONFLICT, not a certification disposition. The audit’s original zero-comment preflight preceded its authenticated submission; these are observations at different times, not conflicting source evidence.

The pinned Google DeepMind file at commit 85f8637 ends the theorem with by sorry. The live formal file still has by sorry but adds a formal_proof using lean4 link to plby/lean-proofs at commit 8822f7d. That external file delegates to erdos248_resolved; I did not compile it or audit its complete imports. A pointer to an external Lean development is therefore reported formal-work evidence, never GCL certification.

The formal proposition itself is over natural-number \(n\) and \(k\): it asks for a real \(C>0\) such that the set of \(n\) satisfying \(\forall k\geq1\), \(\omega(n+k)\leq Ck\), is infinite. It does not write \(n>0\) explicitly. That is semantically harmless for an infinitude claim, since at most one natural number is zero, but it is still a statement-level difference that any replay must record rather than silently erase.

What remains

For the original mathematical claim, the remaining work is documentary and formalization-sensitive rather than an open conjecture: preserve the exact Tao–Teräväinen source lock, verify any replay against the precise quantified proposition, and record whether the external development compiles without hidden axioms or sorry dependencies. The elementary bridge \(\omega(m)\leq\Omega(m)\) is straightforward, but it does not reconstruct the weighted-sieve proof.

There are also nearby open or only partially improved questions. Lau’s paper discusses bounds for backward shifts, sharpness heuristics, and other Erdős problems; those must not be folded into Problem 248. In particular, an \(O(\log k)\) result for \(k\geq2\) does not assert the best possible constant, nor does a finite search establish infinitely many \(n\). The finite check and the bridge \(\omega\leq\Omega\) are source-limited partial deductions, not a fresh solution. The official page’s “resolved” label, the catalogue’s proved (Lean) label, Tao–Teräväinen’s published/preprint theorem, and an independently replayed formal proof are four different claim types.

Sources and claim boundaries

  • Original statement and page reference: Erdős–Graham scan, p. 61; maintained problem page, which also links [Er74b], [ErGr80,p.61], and the formal file. The cited Erdős 1974 scan is pp. 197–202, but the GCL audit did not find the exact prime-factor statement there. The Erdős–Graham scan is the source for the historical wording; it does not by itself define whether the original \(v\) counts distinct factors or multiplicity.
  • Resolution: Tao–Teräväinen arXiv record and v2 PDF, Theorem 1.1 p. 2 and proof §2, pp. 11–24. I attribute the deep sieve and moment arguments to these authors and make no original-proof claim.
  • Later refinement: Lau arXiv record and v2 PDF, Theorem 1.1 p. 3; its \(k\geq2\) quantifier is retained.
  • Status and formal boundaries: pinned catalogue bytes, live catalogue bytes, and GCL editorial protocol. The catalogue and external formal pointers are evidence to reconcile, not certification. The current editorial acceptance state must be read from the protected admissions ledger; no mathematical certification is implied.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1517 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
  • Formal-statement coverage: A provider statement was included in the pinned 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