Skip to content

Erdős Problem #281

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: proved (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

Take a strictly increasing sequence of positive integers

\[ n_1<n_2<n_3<\cdots. \]

For each \(n_i\), choose one residue \(a_i\) modulo \(n_i\) to forbid. The integers that escape every forbidden class are

\[ A(a)=\{m\in\mathbb Z: m\not\equiv a_i\pmod {n_i}\text{ for every }i\}. \]

The hypothesis is a strong one: for every possible infinite choice of residues, \(A(a)\) has natural density zero. In plain language, every way of placing one forbidden congruence class at each modulus eventually covers almost all integers.

The question asks whether this covering can always be witnessed by a finite prefix, uniformly over the placements. Formally, is it true that

\[ \forall\epsilon>0\ \exists k\ \forall(a_i),\quad \mathrm{dens}\{m\in\mathbb Z:m\not\equiv a_i\pmod {n_i}\text{ for }1\leq i\leq k\}<\epsilon? \]

The order of the quantifiers matters. One \(k\) must work for every residue choice; it is not enough that each choice has its own good prefix. The original statement appears in Erdős and Graham, Old and New Problems and Results in Combinatorial Number Theory (1980), p. 29 of the scan.

The pinned Lean statement uses zero-based functions, StrictMono n, positive moduli, and two-sided integer density through Set.HasIntDensity. Its prefix condition is i < k. Those conventions are close to the printed problem, but the source audit correctly treats the passage between the printed density convention and the formal one as a semantic comparison to be checked, not as an automatic equivalence.

A small example

For a finite prefix with moduli \((2,3,4,5,7)\), every residue choice is periodic with period

\[ L=\mathrm{lcm}(2,3,4,5,7)=420. \]

There are \(2\cdot3\cdot4\cdot5\cdot7=840\) choices. The following exact enumeration counts the integers in one period that avoid all five forbidden classes.

from itertools import product
from math import lcm

q = (2, 3, 4, 5, 7)
L = lcm(*q)
counts = []
for residues in product(*(range(n) for n in q)):
    count = sum(all(x % n != a for n, a in zip(q, residues))
                for x in range(L))
    counts.append((count, residues))

maximum = max(count for count, _ in counts)
zero_count = next(count for count, a in counts
                  if a == (0, 0, 0, 0, 0))
print(L, len(counts), maximum, zero_count)

It prints 420 840 96 96. Thus the largest uncovered density in this finite experiment is \(96/420=8/35\), and the all-zero residues attain that maximum. They are not the only maximizers: the calculation finds 420 tied choices. This is a checked instance of the finite sieving interface, not a proof for every collection of moduli.

What is known

The standard affirmative strategy has two ingredients. First choose all residues to be zero. The uncovered set is then the set of integers divisible by none of \(n_1,n_2,\ldots\). The hypothesis says its density is zero, so the union of the multiples has density one.

Davenport and Erdős prove the needed finite-stage density statement in “On sequences of positive integers,” Acta Arithmetica 2 (1936), 147–151, DOI 10.4064/aa-2-1-147-151. Their Theorem 1(a,b), on pp. 149–150, identifies the relevant limiting density of the union of multiples with the increasing limit of the finite unions. Consequently, for some finite \(k\), the all-zero prefix leaves density below any prescribed \(epsilon\).

The second ingredient is the finite sieving assertion usually attributed to Rogers: for fixed positive moduli, the uncovered density is largest when every forbidden residue is zero. If this inequality is available in exactly the required form, then every arbitrary residue choice on the same prefix has uncovered density no larger than the all-zero choice. The two ingredients give the desired uniform quantifier order.

This is the classical proof interface reported by the source audit. The original Erdős–Graham page is a problem statement, not the proof of the resolution. The exact Halberstam and Roth, Sequences, Vol. I (1966), Chapter V.3, pp. 242–244, pages cited for Rogers' result were not obtained in this audit. Tao's exposition points to the same result, but it is secondary evidence and does not repair the missing primary-source fidelity check. The full affirmative resolution therefore remains an externally reported argument whose final source bridge is not independently verified here.

GCL's current state

The authenticated RESULT/1 source return on original issue #1551 is explicitly DISPOSITION: PARTIAL. It records the exact quantifiers, the accessible Erdős–Graham scan, the Davenport–Erdős reduction, the finite computation above, and the unresolved Rogers-source dependency. It also records that the live problem page says “This is true” and describes a Davenport–Erdős-plus-Rogers reduction. That is status evidence, not a GCL proof readback.

The pinned catalogue at teorth/erdosproblems commit 536408716724a2402bdfa7c1d764bf83d64a8c89 reports status proved for entry 281 (file blob 4e60263a80af6207aca494d2e1388e44fa372889). The pinned FormalConjectures file is at commit 85f863718beeec7b58a3a1926ee92e3472bc2020, blob c3f976a500953fefe49a547893f9475c90784428. It gives a useful formal statement and labels the result as a Lean formal proof, but its theorem body is by sorry; it is not a checked proof artifact.

The audit also reports an external plby/lean-proofs development with a theorem named Erdos_281 and a #print axioms result, but that repository revision is not pinned by the issue and was not independently compiled here. It must be described as an unsupported external formal-proof claim, not as a published proof and not as GCL internal certification. The PARTIAL/STATUS_CONFLICT exception boundary is retained: this actual return is PARTIAL, and no later status label is silently substituted for its unresolved source and semantic discrepancies.

What remains

A source-complete resolution needs the exact Rogers statement and proof pages, followed by a semantic comparison of its hypotheses with the printed problem and with the two-sided integer-density Lean encoding. It also needs a reproducible compile of the external Lean development at a pinned revision, with its indexing, density definitions, imports, and axioms inspected. Until then, the careful summary is: a published Davenport–Erdős finite-stage theorem is verified; the Rogers step and the complete reduction are reported but not fully source-verified here; the catalogue reports proved; and GCL has issued no mathematical certification.

The article does not import claims from neighboring problems. In particular, the weak gcd-seed condition reported for #276 is not automatically equivalent to the stronger pinned Lean condition

\[ \forall d>1\ \exists k\ \gcd(d,a_k)=1. \]

That equivalence remains unresolved. Likewise, #285's Fin k.succ indexing shifts by one relative to f(k) and its formal file contains sorry; and #284's claim of infinitely many \(k\) still requires scrutiny before it can be bridged to a statement for all large \(k\). These are explicit neighboring exceptions, not evidence that changes the status of #281.

Sources and claim boundaries

Catalogue and evidence provenance

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