Skip to content

Erdős Problem #822

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.

The question in plain language

Let V_f={n+f(n):n>=1}, with f the Euler totient, sum of divisors, divisor count, or number of distinct prime factors. The question is whether V_phi has POSITIVE LOWER NATURAL DENSITY, not whether f itself has positive mean or the number of representations of a fixed target is large. The analogous sigma case must be separately tracked as printed.

A small example

Exact first values of n+phi(n): n=1..6 yields 2,3,5,6,9,8. These include a collision-free sample but no quantitative asymptotic density. For n+sigma(n), n=1..6 yields 2,5,7,11,11,18, showing collisions may occur.

The example can be checked exactly. A finite witness does not replace the universal, asymptotic, or infinitely-often quantifiers in the original question.

What is known

Live maintained https://www.erdosproblems.com/latex/822 read 2026-10-14: Gabdullin–Iudelevich–Luca [GIL24], Numbers of the form k+f(k), J. Number Theory (2024) 58–85, credited PROVED positive lower density for phi, also tau and omega. Wording 'similar question' for sigma is present; inspect [GIL24] Theorem specifically before declaring sigma proven. Full printed proof not independently read.

The lower natural density of a set of positive integers \(S\) is

$$

\underline{d}(S)=\liminf_{x\to\infty}\frac{|S\cap[1,x]|}{x}.

$$

Positive lower density is a statement about DISTINCT values of \(n+f(n)\) rather than the number of input integers. Collisions between input images reduce the distinct-value count. The maintained catalogue credits Gabdullin, Iudelevich and Luca for the positive result, and the precise scope for the \(\sigma\) analogue remains a primary-paper check.

GCL's current state

The original authenticated RESULT/1 source return has historical disposition SOURCE_LOCK_READY. This status and the original research exceptions are preserved, not silently converted into a theorem verdict. The maintained Erdős source and source-specific mathematical definitions were reviewed, and this article is editorially reviewed as a source-exception-annotated explanation under EC-BULK-005-R10, effective only after the exact-hash protected admission merges.

Source interpretation and unresolved mathematical qualification: GIL24 lower positive density for n+phi(n), tau and omega is source-attributed; sigma-analogue theorem scope remains unverified in the original paper.

The explanation is accepted for publication of established background, examples, and explicitly attributed current claims. It does not establish or formally certify the disputed original theorem, external model-assisted proof, historical interpretation, or any unreplayed Lean kernel file. Original source-fidelity and proof-review research holds remain.

What remains

Independently check the four individual GIL24 theorem hypotheses; enumerate n+phi(n),n+sigma(n),n+tau(n),n+omega(n) up to N=100 and compute unique images. Preserve natural lower-density liminf and do not infer sigma theorem from nearby catalogue prose.

Independent critical review must compare the historical primary theorem to the written quantifiers, inspect the exact finite fixture, determine whether a claimed status refers to the whole question or a subcase, and validate the actual rendered mathematical output. No protected admission or formal theorem certification is claimed.

Sources and claim boundaries

  • Maintained Erdős problem #822 and its LaTeX/bibliography, read 14 October 2026.
  • Authenticated original GitHub source-return record. All original historical bibliography, quantified status limitations and exact source observations are recorded in that return.
  • Pinned teorth/erdosproblems revision 536408716724a2402bdfa7c1d764bf83d64a8c89, data/problems.yaml. no newly certified theorem proof source-lock alteration is claimed.
  • Source theorem proof: PARTIAL and identified where unread. Independent mathematical acceptance: PENDING. Protected merge: NONE. Deployed MathJax: NOT VERIFIED. External Lean certification by GCL: NONE.

Qualified editorial critical review: R10 source-exception dossier. The source-semantic exception is visible and its original research hold remains. Publication classification: REVIEWED EXPLANATORY ARTICLE WITH UNRESOLVED SOURCE/PROOF QUALIFICATIONS. Independent theorem proof or Lean certification: NOT CLAIMED.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #2093 — 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