Skip to content

Erdős Problem #277

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.

Documentary explanation. This is an unaccepted local draft. Editorial prose does not certify the mathematics: publication acceptance is decided only by the protected publication ledger, after its exact source, review, and rendered-readback requirements are met.

The question in plain language

For a positive integer \(n\), write

\[ \sigma(n)=\sum_{d\mid n}d \]

for the sum of its positive divisors. A finite covering system is a finite list of congruences

\[ x\equiv r_i\pmod {m_i}\qquad (1\leq i\leq k) \]

such that every integer \(x\) satisfies at least one of them. The moduli are called distinct when the \(m_i\) are pairwise different. Erdős Problem 277 asks whether, for every real number \(c\), there is a positive integer \(n\) for which the divisor sum is unusually large compared with \(n\), but the divisors of \(n\) still cannot supply the moduli of a covering system. In quantifiers, the intended statement is

\[ \forall c\in\mathbb R\;\exists n\in\mathbb N:\quad \sigma(n)>cn\quad\text{and}\quad \text{no distinct covering system has every }m_i>1\text{ dividing }n. \]

“Every modulus divides \(n\)” means \(m_i\mid n\) for each congruence, not that every divisor must actually be used. The source return notes that this is equivalent, for existence, to requiring the complete set of nontrivial divisors: if a covering uses only some divisors, assign arbitrary residue classes to the unused divisors. The question is therefore a separation between two properties of the same integer: large abundancy ratio \(\sigma(n)/n\), and failure to be “covering” in this congruence sense.

A small example

The number \(12\) shows why the obstruction is not automatic. Its nontrivial divisors are \(2,3,4,6,12\), and the following five classes cover every residue modulo \(12\):

\[ 0\pmod 2,\qquad 0\pmod 3,\qquad 1\pmod 4,\qquad 1\pmod 6,\qquad 11\pmod {12}. \]

Because membership in a class modulo \(12\) depends only on the residue modulo \(12\), checking the twelve residues is a finite proof of coverage. The exact computation below searches the residue choices and then checks the displayed witness.

from fractions import Fraction
from itertools import product

n = 12
divisors = [d for d in range(2, n + 1) if n % d == 0]
witness = None
for residues in product(*[range(d) for d in divisors]):
    covered = {
        x for x in range(n)
        if any((x - r) % d == 0 for d, r in zip(divisors, residues))
    }
    if len(covered) == n:
        witness = list(zip(divisors, residues))
        break
assert witness == [(2, 0), (3, 0), (4, 1), (6, 1), (12, 11)]
assert all(any((x - r) % d == 0 for d, r in witness) for x in range(n))
sigma = sum(d for d in range(1, n + 1) if n % d == 0)
print("divisors =", divisors)
print("witness =", witness)
print("covered residues =", sorted({
    x for x in range(n)
    if any((x - r) % d == 0 for d, r in witness)
}))
print("sigma(12) =", sigma)
print("sigma(12)/12 =", Fraction(sigma, n))

Verified output is:

divisors = [2, 3, 4, 6, 12]
witness = [(2, 0), (3, 0), (4, 1), (6, 1), (12, 11)]
covered residues = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
sigma(12) = 28
sigma(12)/12 = 7/3

This is a finite example and a reproducibility check, not a proof of the universal statement. It illustrates that a large divisor sum alone does not force the desired non-covering property.

What is known

The original resolution is attributed to J. A. Haight, “Covering systems of congruences, a negative result,” Mathematika 26 (1979), 53–61. The authenticated source audit could verify the article-level primary reference, but could not obtain its full proof text or an exact theorem/page locator. That part of the provenance is therefore PARTIAL, not silently upgraded to a source-complete reading.

An accessible primary corroboration is Filaseta, Ford, Konyagin, Pomerance, and Yu, “Sieving by large integers and covering systems of congruences,” Journal of the American Mathematical Society 20 (2007), 495–517. Their introduction defines an integer \(H\) to be covering when a covering system with distinct moduli, each a divisor of \(H\) greater than \(1\), exists. On printed p. 500, Theorem 1 gives an infinite set of integers \(H\) satisfying

\[ \frac{\sigma(H)}{H} = (\log\log H)^{1/2}+O(\log\log\log H), \]

and says that every residue system using all nontrivial divisors of such an \(H\) leaves positive residual density for sufficiently large \(H\). Since the displayed ratio tends to infinity, for any fixed real \(c\) one may choose a sufficiently large member of this set with \(\sigma(H)>cH\). This supplies the affirmative mathematical interface needed for Problem 277, while also recording the stronger quantitative construction in the later paper.

The paper’s notation makes the mechanism concrete. If \(C\) is a finite residue system and \(\delta(C)\) is the density of integers left uncovered, then Theorem 1 gives \(\delta(C)\geq(1+o(1))\alpha(C)\) for the complete nontrivial divisor set, with \(\alpha(C)=\prod_{d\mid H,\,d>1}(1-1/d)\). Thus \(\delta(C)>0\) for large \(H\), so no choice of residues can cover all integers. This is a published external result, not a GCL certification.

GCL's current state

The protected catalogue snapshot is teorth/erdosproblems at commit 536408716724a2402bdfa7c1d764bf83d64a8c89, entry number: "277", Git blob 4e60263a80af6207aca494d2e1388e44fa372889. It records informal status proved (last update 2025-08-31), formal status Lean, formalized: yes, and proved (Lean) metadata. Those labels are evidence to reconcile, not certification.

The original MATH-PROGRAMME issue #1547 is specifically ERDOS-CATALOGUE-0277-S01. Its authenticated RESULT/1 comment exists, begins with the required marker, and explicitly identifies PROBLEM_ID: 277. It returns DISPOSITION: PARTIAL: Haight’s full proof was inaccessible, while the FFKPY theorem was checked as primary corroboration and the finite \(n=12\) witness was reproduced.

The pinned FormalConjectures file, blob a67df9975a318fe2d821f88ea780842af28bc960, states the theorem with \(\forall c:\mathbb R\), \(\exists n:\mathbb N\), the inequality \((\sigma 1\,n:\mathbb R)>c n\), and a quantifier over StrictCoveringSystem ℤ. Its body is by sorry. The structure encodes finite cosets of nonzero, non-top ideals with injective moduli; this is close to distinct nontrivial integer moduli, but the file does not itself prove the semantic equivalence with the paper’s divisor formulation. The formal statement is therefore present, but the formal proof and semantic bridge remain PARTIAL. An external proof artifact mentioned in the return was not built here and is not treated as Lean-checked or GCL-certified.

What remains

The mathematical result is resolved in the literature, but the documentary chain still has bounded gaps. First, an accessible copy of Haight’s 1979 paper is needed to record the exact theorem statement, hypotheses, and proof pages rather than relying on the later paper’s attribution. Second, the ideal-language formalization needs an explicit lemma connecting nonzero proper ideals of \(\mathbb Z\) with positive nontrivial divisors and connecting ideal membership with divisibility. Third, the pinned theorem needs a real build in its declared Lean environment with its sorry status removed before anyone can call it a Lean-checked proof.

A suitable successor task would take Haight’s text and the pinned Lean file as inputs, normalize both quantifier blocks, prove or refute the semantic bridge, and record a reproducible build plus axiom and sorry reports. Its stopping condition is a missing source, a material hypothesis mismatch, or an unreproducible external proof. None of these documentary tasks changes the published theorem, and none authorizes mathematical certification.

Sources and claim boundaries

The external paper, the formal statement, the finite computation, and this editorial explanation are different evidence classes. In particular, an original external proof is not a Lean-formalized statement; a Lean-formalized statement is not a Lean-checked proof; and neither is GCL mathematical certification. This manuscript is a documentary draft, not an accepted publication. The publication ledger alone decides acceptance.

Catalogue and evidence provenance

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