Erdős Problem #278
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: number theory, covering systems.
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.
Editorial authority: The protected GCL V2 admissions ledger alone determines publication status. This source-bounded explanation is not mathematical certification.
The question in plain language
Choose distinct positive integers
and, for each modulus \(n_i\), choose one residue class \(a_i+n_i\mathbb Z\). The question asks how much of the integer line these classes can cover. Write
If \(L=\mathrm{lcm}(n_1,\ldots,n_r)\), then \(U\) repeats every \(L\) integers. Its density is therefore the exact fraction of residues covered in one period:
The main question is to minimize \(\mu\), or equivalently maximize the covered density, over all residue choices. The companion question asks whether the worst choice, the one with the smallest covered density, is always obtained from one common integer \(c\), meaning \(a_i\equiv c\pmod {n_i}\) for every \(i\). “All \(a_i\) equal” does not mean that canonical representatives in different modulus ranges are literally the same number.
The quantifiers matter: the moduli are fixed first, exactly one class is chosen for each, and only then is the periodic density evaluated. The problem is about a finite optimization for each input, not about choosing residues after inspecting individual integers one at a time.
A small example
Take \(A=\{3,6,10\}\). The period is \(L=30\), and there are \(3\cdot6\cdot10=180\) residue vectors. The following exact calculation checks every one using integer counting and rational arithmetic:
from fractions import Fraction
from itertools import product
from math import lcm
ns = (3, 6, 10)
L = lcm(*ns)
def covered_density(residues):
covered = sum(
any((x - a) % n == 0 for n, a in zip(ns, residues))
for x in range(L)
)
return Fraction(covered, L)
values = [(covered_density(a), a)
for a in product(*(range(n) for n in ns))]
print("L", L, "choices", len(values),
"min", min(values), "max", max(values),
"common", covered_density((0, 0, 0)))
The reproducible output is L 30 choices 180 min (2/5, (0, 0, 0)) max (17/30, (2, 4, 9)) common 2/5. Thus the common-residue choice is worst in this example, while another choice covers \(17/30\) of the integers. For the common choice, inclusion–exclusion gives
This is a checked finite illustration of periodic reduction, not evidence for the general theorem.
What is known
The original source is Erdős and Graham, Old and New Problems and Results in Combinatorial Number Theory (1980), p. 28, lines 4–6 of the scanned page. It asks for the minimum density missed by suitable congruences and asks whether the worst choice has all residues equal. The source is a book statement, not a proof of the optimization problem.
The all-equal companion assertion is attributed to R. J. Simpson, “Exact coverings of the integers by arithmetic progressions,” Discrete Mathematics 59 (1986), 181–190, DOI 10.1016/0012-365X(86)90079-8, Lemma 2.3 as cited by later work. The bibliographic record and attribution are verified, but the publisher’s full text was not accessible in this audit; it is therefore reported as a published result cited by the source packet, not as a replayed proof here. Halberstam and Roth, Sequences (1983), §5.3, first theorem, is another cited source for a related covering fact; only the publisher’s metadata and chapter description were accessible, so its theorem is likewise not independently verified here.
Stijn Cambie’s accessible arXiv v2, “Proving it is impossible; on Erdős problem #278”, directly proves a useful structured interface. For the pairwise-distinct moduli \(\{3\}\cup\{3p:p\in P\}\), the missed density is claimed and proved there to be
The proof partitions the two nonzero residue fibers modulo \(3\) and applies the Chinese remainder theorem inside each fiber. Cambie also proves NP-hardness of zero missed density for binary-encoded lists of moduli, where repetitions are allowed, via Exact Pinwheel Covering. That is not a theorem for the literal pairwise-distinct set version: repeated moduli can choose complementary classes, and deleting repetitions can change the answer.
GCL's current state
MANDATORY SOURCE EXCEPTION — PARTIAL / STATUS_CONFLICT-type drift. The complete authenticated source audit is RESULT/1 on original issue #1548. It records DISPOSITION: PARTIAL, not SOURCE_LOCK_READY, proof certification, or a solved status. Its status/provenance drift is a STATUS_CONFLICT-type documentary exception, not a second disposition. It reports that the live page remained open, had later explanatory material than the catalogue snapshot, and contained unreviewed external proof claims. Those claims are leads only; they do not silently change the official status. The fidelity exception is equally important: the original pairwise-distinct finite-set problem is not the same as Cambie’s repeated-modulus list problem, and covered density is the complement of missed density.
The pinned catalogue is teorth/erdosproblems at commit 536408716724a2402bdfa7c1d764bf83d64a8c89, entry number: "278", catalogue blob 4e60263a80af6207aca494d2e1388e44fa372889. It reports open, formal_status: unformalized, and formalized: no, with the catalogue status dated 2025-08-31. This pinned metadata is kept distinct from later page text reported by the source return.
The admitted FormalConjectures provider snapshot is google-deepmind/formal-conjectures@85f863718beeec7b58a3a1926ee92e3472bc2020. There is no FormalConjectures/ErdosProblems/278.lean at that SHA, and no such file was found on current provider main during this audit. Consequently #278 has no pinned Lean quantifier, theorem body, sorry, or external Lean proof claim to certify or compare. The absence of a file is evidence about the provider snapshot only; it is not evidence that the mathematical problem is false.
The return names public Onishi and Schroeder proof submissions as unreviewed external claims. I did not verify those claims, and none is treated as a proof of #278. The same boundary applies to the Exact Pinwheel Covering input: Cambie cites Kawamura, Kobayashi, and Kusano, “Pinwheel Covering,” CIAC 2025, pp. 185–199, DOI 10.1007/978-3-031-92935-9_12, Theorem 3; that cited theorem was not independently replayed here.
What remains
The general maximum-covered-density problem remains open in the checked evidence. The structured Cambie formula and the list-version NP-hardness theorem are genuine mathematical interfaces, but neither gives a closed formula for every pairwise-distinct finite set. The all-equal worst-choice statement is a cited published result whose full proof was unavailable for direct replay in this audit.
The bounded successor proposed by the authenticated return is the fixed set \(A=\{3,15,21,33\}\). Its period is \(3465\), and the structured formula predicts missed density \(608/1155\). A responsible next step would derive that formula, check all eight partitions of \(\{5,7,11\}\) exactly, and exhaustively enumerate residues modulo \(3465\) or provide an exact bitset certificate. A counterexample residue vector with missed density below \(608/1155\) would falsify that bounded target. This is a proposed finite check, not a result claimed by this article.
For scope control, this article imports no mathematical conclusion from neighboring catalogue entries. In particular, #276’s weak gcd-seed condition is not automatically equivalent to the stronger pinned Lean condition \(\forall d>1\ \exists k\ \gcd(d,a_k)=1\); that equivalence remains unresolved. In #285, the Lean Fin k.succ indexing shifts by one relative to the prose’s \(f(k)\) and the declaration includes sorry. In #284, a Croot claim for infinitely many \(k\) does not by itself supply the bridge to a statement for all sufficiently large \(k\). These are explicit unresolved boundaries, not evidence about #278.
Sources and claim boundaries
- Original source-audit issue #1548 and its exact authenticated RESULT/1 comment: source packet, live-status report, finite check, and
PARTIALdisposition. - Erdős and Graham, Old and New Problems and Results in Combinatorial Number Theory (1980), p. 28, lines 4–6: original scan. This verifies the historical problem statement; no proof is claimed from that page.
- Simpson, “Exact coverings of the integers by arithmetic progressions,” Discrete Mathematics 59 (1986), 181–190, DOI 10.1016/0012-365X(86)90079-8: published citation for the all-equal result, with full proof unavailable here.
- Halberstam and Roth, Sequences (1983), §5.3, DOI 10.1007/978-1-4613-8227-0: cited book source; the relevant theorem text was unavailable here.
- Cambie, arXiv:2508.18270v2: directly inspectable preprint proof of the structured formula and the repeated-modulus list hardness result, not GCL certification.
- Kawamura, Kobayashi, and Kusano, “Pinwheel Covering,” CIAC 2025, pp. 185–199, DOI 10.1007/978-3-031-92935-9_12: cited by Cambie for the hardness input; its theorem was not independently replayed.
- Pinned catalogue entry, entry
278, and pinned FormalConjectures tree: catalogue reports and provider-snapshot boundaries, not proofs.
Published source results, an accessible preprint, catalogue metadata, and an authenticated GCL audit have different authority. No external Lean proof claim is verified for #278, and no source return, formal declaration, finite computation, or editorial manuscript is GCL internal mathematical certification. The protected V2 ledger alone controls documentary acceptance.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1548 — 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.