Skip to content

Erdős Problem #25

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

Choose a strictly increasing sequence of positive moduli \(m_0<m_1<\cdots\) and a residue \(a_i\) for each modulus. Start with the nonnegative integers and, for each \(i\), remove those \(x\) that have reached the threshold \(x\ge m_i\) and satisfy \(x\equiv a_i\pmod{m_i}\). Erdős Problem #25 asks whether the surviving set necessarily has a logarithmic density.

Logarithmic density weights each positive survivor \(x\) by \(1/x\) and normalizes by the harmonic growth \(\log X\). It is a different existence question from ordinary natural density.

A small example

Use just the first two moduli \(2\) and \(3\), with excluded residues \(0\) and \(1\). Once both thresholds have been passed, the survivors are precisely integers congruent to 3 or 5 modulo 6. Their ordinary and logarithmic densities are both \(2/6=1/3\).

The initial point \(x=1\) nevertheless survives both restrictions, since \(1<2\) and \(1<3\), even though its residue modulo 3 is 1. The threshold is part of the rule. At \(x=2\), the first exclusion already applies.

What is known

Any finite truncation of the congruence list is eventually periodic with period equal to the least common multiple of its moduli. Consequently each finite truncation has both ordinary and logarithmic density; the finite initial threshold exceptions have no effect on either limiting density.

It does not follow that imposing infinitely many conditions yields a logarithmic density. As \(X\) grows, new constraints become active; exchanging the limit over the number of constraints with the limit in \(X\) requires uniform control. Overlapping moduli also defeat an unqualified independence-product argument.

GCL's current state

Source audit #1294 proves an exact local-finiteness observation: because the increasing positive integers satisfy \(m_i\ge i+1\), checking membership at any finite \(x\le X\) only requires indices smaller than \(X\). It also checks the finite-periodic truncation theorem and gives examples where naive products of survival fractions fail. The source record remains OPEN; the formal provider has an unfilled proof.

What remains

Proving the global result needs a uniform bound on the logarithmic contribution of newly activated exclusions, or a different argument handling infinitely many dependent moduli. Neither computability of finite membership nor existence of densities for all finite truncations is enough.

Sources and claim boundaries

  • Erdős Problems #25: current statement, historical source leads and logarithmic-density question.
  • GCL source audit #1294: threshold semantics, finite proofs and source-access limits. No global density theorem is claimed.

Catalogue and evidence provenance

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