Erdős Problem #122
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (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.
The question in plain language
For a number-theoretic function \(f\), consider the shifted map \(n\mapsto n+f(n)\). Erdős #122 asks which functions force this map to send many more inputs than the length of a short target interval into that interval. If \(F\) is small compared with the normal order of \(f\), the intended quantity is
and the question asks whether this ratio is unbounded along large \(x\). The precise admissibility conditions on \(F\), and the source's use of “almost all \(n\),” must be specified to make the quantifiers mathematically rigorous.
A small example
The number-of-divisors function satisfies \(\tau(12)=6\) and \(\tau(13)=2\), so \(12+\tau(12)=18\) but \(13+\tau(13)=15\). The shifted map need not be monotone, and a short output interval can receive many inputs. Counting preimages means counting each input separately, even when shifted outputs coincide.
The function \(\omega(n)\) counts distinct prime divisors, not all prime factors with multiplicity. For example \(\omega(12)=2\) while \(\tau(12)=6\).
What is known
The general classification remains OPEN. The maintained Erdős #122, edited 1 April 2026, cites Erdős, Pomerance and Sárközy [EPS97]. They established, in particular, that for all large \(x\) there are intervals \(I,J\subset[1,x]\) with
and \(n+\omega(n)\in J\) for every \(n\in I\). Their ratio \(|I|/|J|\) tends to infinity. Erdős also reported positive results for the divisor function \(\tau\), while expecting failure for Euler's \(\varphi\) and the divisor-sum \(\sigma\).
There is a statement-capture defect: the maintained page says “infinitely many \(x\) such that [the ratio] tends to infinity,” although a single value of \(x\) cannot be the variable in a limit. One must consult [Er97] and [EPS97] to fix the precise limsup or sequence quantifiers rather than silently formalizing ambiguous prose. The original paper's exact pages were not independently inspected in this audit.
GCL's current state
The pinned status is OPEN. The source task is #1391; no admitted protected Formal Conjectures statement exists for #122. Its original statement-capture prerequisite is preserved. The displayed published special-case estimate is source-attributed, not a newly proved lemma.
The original issue contains an authenticated RESULT/1 source report. This is unadjudicated source evidence only, not independent mathematical certification or editorial admission.
What remains
A bounded two-stage successor first transcribes the 1997 original statement and explicitly defines allowed positive functions \(F\), their smallness condition, and a correct asymptotic \(x\) quantifier. It then enumerates \(\tau(n)\) and \(\omega(n)\) exactly for \(1\le n\le1000\) and counts shifted preimages of integer intervals of lengths 2 to 8. Acceptance: independently factored counts agree, collisions are not deduplicated, and no asymptotic claim is inferred from finite data. Stop before investigating new families of functions.
Sources and claim boundaries
- Erdős #122, primary leads [Er97], [Er97e], [EPS97] and dated statement.
- Original GCL issue #1391.
No new concentration theorem, original primary-proof certification, or editorial admission is claimed.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1391 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: STATEMENT_CAPTURE_REQUIRED.
- Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.