Skip to content

Erdős Problem #204

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: disproved (not automatically the live result).
Subject areas: covering systems, divisors.

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 positive integer \(n\) and assign a residue class \(a_d\bmod d\) to every divisor \(d>1\) of \(n\). Can these classes cover every integer while satisfying a special restriction on intersections? Namely, whenever the classes for two distinct moduli \(d,d'\) have a common integer, require \(\gcd(d,d')=1\).

The condition does not demand that every pair of classes be disjoint. It permits overlaps only when their moduli are coprime, a much weaker-looking requirement than complete disjointness but still too strong for full coverage.

A small example

The classes \(0\bmod2\) and \(0\bmod4\) intersect at every multiple of four, while their moduli have gcd two. Such a pair violates the overlap rule. The classes \(0\bmod2\) and \(0\bmod3\) also intersect, but their moduli are coprime, so that overlap is allowed.

For each \(d\) the residue is chosen independently. Checking only adjacent divisors, or excluding prime-power divisors, does not verify the full question.

What is known

DISPROVED. Sarosh Adenwalla, A Question of Erdős and Graham on Covering Systems, 2025, proves that no positive integer \(n\) admits this full covering with the prescribed intersection constraint. The paper also defines nice integers, whose divisors support congruence assignments with the restricted-overlap condition without requiring coverage, and obtains necessary conditions for niceness.

Zhengkun Jia and Huixi Li, Resolving Adenwalla's conjecture related to a question of Erdős and Graham about covering systems, develop the subsequent characterization of nice integers. It is a different existence question: being nice does not produce the forbidden full covering.

The maintained Erdős #204 identifies the original question as disproved and notes a residual optimization problem: how large a density can congruence classes cover subject to the restricted-overlap rule? That density problem survives the impossibility of density one.

GCL's current state

Pinned and live status: DISPROVED. Original issue: #1473. A frozen formal statement is available, but its proof was not independently reconstructed in GCL's Lean toolchain. The 2025 primary paper and separate niceness theorem have been identified.

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 successor computes all divisors for \(2\le n\le24\), enumerates residue assignments, tests pairwise overlap by the Chinese remainder theorem, and calculates the fraction of a least-common-multiple period covered. Acceptance: overlap is forbidden only when gcd exceeds one; the full-covering predicate is separately tested and no candidate is claimed to resolve the universal theorem. Preserve the all-divisors quantifier.

Sources and claim boundaries

No new covering-system theorem, independent Lean certificate or editorial admission is claimed.

Catalogue and evidence provenance

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