Skip to content

Erdős Problem #413

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

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.

The question in plain language

Erdős Problem #413 studies when adding a small arithmetic function to every smaller integer still stays below a chosen integer. Write \(ω(m)\) for the number of distinct prime divisors of \(m\). An integer \(n\) is an \(ω\) barrier when

\[ m+ω(m) ≤ n \]

for every integer \(m<n\). The first question asks whether infinitely many such barriers exist. The second asks for a constant \(ε>0\) for which infinitely many \(n\) satisfy the weaker inequality \(m+εω(m)≤n\) for every \(m<n\). These are global questions: a candidate \(n\) must dominate every earlier \(m\), not merely most of them.

The same language also compares nearby functions. \(Ω(m)\) counts prime factors with multiplicity, while the exponent-product function \(d_0(m)\) is defined by \(d_0(m)=∏_i a_i\) when \(m=∏_i p_i^{a_i}\). A barrier for \(d_0\) is therefore a related but different object from a barrier for \(ω\).

The original issue is MATH-PROGRAMME #1683. Its source packet fixes the catalogue and formal-source identities used here; this article does not turn a source audit into a mathematical certification.

A small example

The number \(5\) is an \(ω\) barrier. For \(m=1,2,3,4\), the values of \(m+ω(m)\) are \(1,3,4,5\), respectively, so their maximum is exactly \(5\). By contrast, \(7\) is not an \(ω\) barrier: \(6=2· 3\) has \(ω(6)=2\), and \(6+ω(6)=8>7\).

I also reran an exact integer sieve, using trial division by the smallest prime factor for every integer through \(99999\). For each \(n\), I maintained the maximum of \(m+Ω(m)\) over \(1≤m<n\) and tested whether it was at most \(n\). The resulting list had last element \(99840\); the direct checks were

\[ 99840=2^9·3·5·13,    Ω(99840)=12,    max_{m<99840}(m+Ω(m))=99840, \]

and \(99841\) fails because \(99840+Ω(99840)=99852>99841\). Thus the finite computation reproduces the reported largest \(Ω\) barrier below \(10^5\). It says nothing about infinitely many \(Ω\) barriers, still less about infinitely many \(ω\) barriers. It is a check of a finite range, not a proof of an asymptotic statement.

What is known

In Some unconventional problems in number theory, Acta Mathematica Academiae Scientiarum Hungaricae 33 (1979), 71–80, Erdős defines a barrier by the same universal inequality and states Theorem 1 on printed page 71: for \(d_0(n)=∏_i a_i\), there are infinitely many barriers, and the set of such integers has positive density. His proof outline on printed pages 79–80 uses an averaging argument over multiples of a product of small primes. At the end he additionally says that the density of \(d_0\) barriers exists, with a stronger family of density assertions. This is an external theorem about \(d_0\), not a solution of the \(ω\) question.

The same paper says that infinitely many \(ω\) barriers seemed difficult and that even the existence of some fixed positive coefficient in front of \(ω\) was not proved there. It records the computational fact, attributed to Selfridge, that \(99840\) is the largest \(Ω\) barrier below \(10^5\).

A modern primary source changes the second question. Lau, On the Number of Prime Factors of Consecutive Integers, arXiv:2604.15042 (2026), Theorem 1.3, proves that there is a constant \(C>0\) and infinitely many positive integers \(N\) such that \(ω(N-k)≤Ω(N-k)≤C\log k\) for every integer \(1<k<N\). Setting \(n=N-1\) and \(ε=1/C\), and using \(\log k≤k-1\), gives \(m+εω(m)≤n\) for the corresponding earlier \(m=N-k\). This establishes the weak, positive \(ε\) question, subject to the ordinary source interpretation of the theorem; it does not establish infinitely many exact \(ω\) barriers.

GCL's current state

The pinned catalogue snapshot is teorth/erdosproblems commit 536408716724a2402bdfa7c1d764bf83d64a8c89, data/problems.yaml, blob 4e60263a80af6207aca494d2e1388e44fa372889. Entry 413 says open, with formal status unformalized, a formalized statement, and last catalogue update 2025-08-31. The live catalogue commit 503d0a58ff3b6a12d7ff1665aa37fb953416d85f has blob 97ae243a7fc056bb9c6413ce665b575eadd27ff3 and retains those entry fields.

The live problem page, last edited 17 April 2026, presents the exact two-question statement, the \(d_0\) and \(Ω\) context, and Lau's positive answer to the second question plus a weaker result for the first. Its page-level prose and the catalogue's aggregate open status are compatible: one component is solved while the original exact barrier question remains open in the ledger.

The issue-pinned FormalConjectures file is at commit 85f863718beeec7b58a3a1926ee92e3472bc2020, blob 4e16f7c9b04583bc6c413092559f19eadae9e778. It defines IsBarrier, formalizes the two parts and variants, but every theorem body is by sorry; presence is not proof. A later commit d238426d3e5e506d50eda743a0c12ff658604eb7 marks only the weak part as solved and cites Lau, while retaining sorry. That is live formal-source drift, not GCL certification.

What remains

The principal mathematical remainder is the exact first question: decide whether there are infinitely many positive \(n\) satisfying \(m+\omega(m)\le n\) for all \(m<n\). A bounded successor should first normalize the domain convention at \(m=0\), then reproduce Lau's implication for the weak part and separately investigate exact \(ω\) barriers. A useful finite phase can enumerate barrier candidates and record the first violating \(m\) for each failure, but it must stop at a declared bound and cannot be presented as evidence of infinitude.

The formal file also needs semantic review: its real-valued definition quantifies over natural \(m<n\), whereas the printed source uses arithmetic-function notation and does not spell out the zero convention in the theorem sentence. The variants for \(d_0\), \(Ω\), and the finite maximum must remain distinct. Any stronger formal claim requires a proof source and specialist mathematical review; a sorry theorem is only a statement interface.

Sources and claim boundaries

Primary evidence: Erdős's Acta paper PDF, Theorem 1 on printed p. 71 and proof outline pp. 79–80; Lau's arXiv paper, Theorem 1.3. Catalogue evidence is the pinned and live commit/blob pair recorded above. Formal evidence is the pinned commit/blob and the later live commit recorded above. The independent finite check described here was run with exact integer arithmetic.

The original issue's source return is authenticated original RESULT/1. No future comment URL is invented here. V2 ledger state, not this article, decides accepted coverage. This record reports established external statements, current formal interfaces, and finite checks; it supplies no Lean replay, no GCL mathematical certification, and no publication or acceptance claim.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1683 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: PROTECTED_READY_BACKLOG.
  • 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