Skip to content

Erdős Problem #280

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

The question in plain language

Erdős Problem #280 is about how efficiently congruence classes can cover the integers. A congruence class \(a_i\pmod {n_i}\) consists of the integers whose remainder on division by \(n_i\) is \(a_i\). Choose strictly increasing positive moduli

\[ n_1<n_2<\cdots \]

and one residue \(a_i\) for each modulus. After the first \(k\) classes have been chosen, look below \(n_k\) and count the integers that lie in none of those classes. The registered question asks whether this count can be as small as \(o(k)\) when the moduli grow faster than \((1+\epsilon)k\log k\) for some fixed \(\epsilon>0\).

Here \(f(k)=o(k)\) means precisely that \(f(k)/k\to0\) as \(k\to\infty\). Thus the original claim is a universal one: for every pair of sequences satisfying the hypotheses, the normalized uncovered count should not tend to zero. The finite range is normalized here as positive integers; the pinned Lean encoding instead counts \(m\in\{0,\ldots,n_k-1\}\). This harmless-looking convention must be stated: with all integers allowed, infinitely many negative integers would make the finite count meaningless. The explicit counterexample also covers \(0\), so it works with the Lean boundary.

The original source, Erdős and Graham, Old and New Problems and Results in Combinatorial Number Theory (1980), p. 29, presents this as a covering-system question and says that the proposed implication was not known. The later evidence says the proposal is false.

A small example

Take

\[ n_i=2^i, \qquad a_1=0, \qquad a_i=2^{i-1}+1\quad(i\ge2). \]

The first classes are \(0\pmod 2\), \(3\pmod4\), \(5\pmod8\), and \(9\pmod {16}\). For every \(k\ge1\), the only uncovered integer in the half-open interval \(0\le m<2^k\) is \(m=1\).

Indeed, every even \(m\) is in \(0\pmod2\). If \(m>1\) is odd, let \(v=v_2(m-1)\), the largest exponent for which \(2^v\) divides \(m-1\). Then \(v\ge1\), and if \(m<2^k\) one has \(v+1\le k\). The definition of \(v\) gives

\[ m\equiv 2^v+1=a_{v+1}\pmod {2^{v+1}}, \]

so \(m\) is covered. On the other hand, \(1\) is not congruent to \(0\) modulo \(2\), and it is not congruent to \(2^{i-1}+1\) modulo \(2^i\) for any \(i\ge2\).

This is a reproducible finite check of the exact boundary and indexing. With \(\epsilon=1\), the following code checks \(n_k>2k\log k\) and enumerates the uncovered set for \(1\le k\le12\):

from math import log

def n(i): return 2**i
def a(i): return 0 if i == 1 else 2**(i-1) + 1
def uncovered(k):
    return [m for m in range(n(k))
            if all(m % n(i) != a(i) for i in range(1, k + 1))]

for k in range(1, 13):
    u = uncovered(k)
    assert u == [1]
    assert n(k) > 2 * k * log(k)
    print(k, u)

The verified output was [1] for every \(k\) from \(1\) through \(12\), and every growth assertion passed. The finite run is evidence about those twelve cases; the 2-adic argument above explains the general construction.

What is known

The construction just given makes the uncovered count exactly \(1\) for every \(k\). Consequently its ratio to \(k\) is \(1/k\), which tends to zero. It therefore directly contradicts the universal lower-bound claim, while satisfying strict monotonicity, the residue normalization \(0\le a_i<n_i\), and the growth condition with \(\epsilon=1\).

The source and attribution need separate treatment. The live Erdős Problems #280 page, retrieved on 2026-10-12/13 UTC, attributes the counterexample to Stijn Cambie and says that the count is actually \(1\). The page cites Erdős–Graham for the original problem, but no primary mathematical paper by Cambie publishing this counterexample was found in the source audit. The attribution is therefore reported as website/discussion evidence, not as a primary-publication claim.

The pinned catalogue record at teorth/erdosproblems commit 536408716724a2402bdfa7c1d764bf83d64a8c89 identifies blob 4e60263a80af6207aca494d2e1388e44fa372889, with informal status disproved, formal status Lean, and overall status disproved (Lean). Those are catalogue fields, not themselves a proof. The live page’s neutral-looking problem panel and its later counterexample prose also show presentation/status drift that should not be silently collapsed.

GCL's current state

The authenticated original issue #1550 RESULT/1 exists as comment 6135326898, begins with RESULT/1, names ERDOS-CATALOGUE-0280-S01, names problem 280, and has disposition PARTIAL. It records the same witness, the finite checks, the original page-29 source, and the unresolved provenance limitation. This article reuses that evidence; it does not turn the worker return into certification.

The pinned FormalConjectures file is locked to commit 85f863718beeec7b58a3a1926ee92e3472bc2020, blob 4273eb5ce85f32f4faa054e9cc0de99b2208948f. It defines isCoveredBy using Finset.Icc 1 k, counts Finset.range (n k), and states the universal negation of convergence to zero. Its theorem ends in by sorry: this is a formalized statement, not a Lean-checked proof.

A separate public Lean proof artifact at commit a1e60a3655e0f919588fe03694f9961830bf9a41 is reported by the source return to contain the construction and exact uncovered-set argument. It was not independently recompiled for this article. External formal proof evidence, even if it compiles, is not the same thing as a GCL mathematical certification.

What remains

The mathematical direction indicated by the available evidence is that the original claim is disproved by the explicit construction. What remains is documentary and formalization work, not an invitation to relabel the problem as open. A bounded successor task is to compile a proof with the pinned definitions, explicitly instantiate \(n_i=2^i\), \(a_1=0\), \(a_i=2^{i-1}+1\), and \(\epsilon=1\), and prove strict monotonicity, residue validity, the growth inequality, exact uncovered count \(1\), and convergence of \(1/k\) to zero.

That task must first compare the exact quantifiers and boundaries: positive integers versus Finset.range, indexing from \(1\) versus natural-number functions, and the use of the real logarithm at \(k=1\). If those definitions differ materially from the external proof artifact, the result remains PARTIAL until the mismatch is resolved. Independent recompilation and the missing primary publication provenance likewise remain explicit exceptions.

Neither this finite calculation nor the external Lean file establishes a new theorem for GCL. The original external mathematical counterexample, a Lean-formalized statement, a Lean-checked proof, and GCL mathematical certification are four different claims.

Sources and claim boundaries

Catalogue and evidence provenance

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