Erdős Problem #273
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 acceptance is determined by the protected V2 ledger. This documentary explanation has no mathematical certification authority.
The question in plain language
An arithmetic progression modulo \(m\) is a congruence class: all integers having the same remainder \(a\) when divided by \(m\). A finite covering system is a finite list of such classes that catches every integer at least once. Erdős and Graham ask whether one can choose a covering system whose moduli are all one less than a prime at least \(5\).
In quantifier form, the question is whether there exist a positive integer \(k\), integers \(a_1,\ldots,a_k\), and distinct positive moduli
such that
and, separately for each index \(i\),
The index \(i\) may depend on \(x\), but the finite list must be fixed once and for all. The problem does not ask for every prime to occur, does not prescribe a bound on \(k\), and does not allow repeated moduli. Because \(m_i=p_i-1\) is injective in \(p_i\), distinct moduli also force distinct associated primes.
A small example
Erdős–Graham give a familiar covering system on printed page 24:
This is easy to check exactly modulo \(24\). The first class covers every even residue. Among the odd residues, \(1\) modulo \(4\) covers \(1,5,9,13,17,21\); \(3\) modulo \(8\) covers \(3,11,19\); \(7\) modulo \(12\) covers \(7,19\); and \(23\) modulo \(24\) covers \(23\). Thus every residue from \(0\) through \(23\) is covered, and periodicity proves that every integer is covered. Erdős’s 1971 survey gives the same example on printed page 408 while introducing covering congruences.
This example illustrates the mechanism, not a solution to Problem 273: it uses moduli such as \(2\), \(3\), and \(8\), which are not all of the form \(p-1\) for primes \(p\ge5\).
There is also a useful exact obstruction. If a covering has least common multiple \(L\), then class \(i\) contains exactly \(L/m_i\) residues modulo \(L\). Counting with overlaps allowed gives
For the restricted primes \(p\le31\), the possible moduli are \(4,6,10,12,16,18,22,28,30\), and exact integer arithmetic gives
The following dependency-free check reproduces that calculation:
from fractions import Fraction
moduli = [4, 6, 10, 12, 16, 18, 22, 28, 30]
total = sum((Fraction(1, m) for m in moduli), Fraction(0))
assert total == Fraction(46157, 55440) and total < 1
print(total)
It rules out a cover using only this small prime pool; it is not a disproof of the full problem.
What is known
The primary statement is the open question recorded by P. Erdős and R. L. Graham, Old and New Problems and Results in Combinatorial Number Theory (1980), printed p. 24, section “Covering Congruences.” That page defines a covering system using distinct increasing moduli and then asks whether all moduli can be \(p-1\) for primes \(p\ge5\). It notes that Selfridge found an example when \(p=3\) is allowed, using divisors of \(360\).
The exact residue classes in that \(p=3\) construction are not supplied on the inspected page. P. Erdős, “Some Problems in Number Theory” (1971), printed pp. 408–409, gives terminology and several general covering examples, but does not state Problem 273. A. Schinzel’s “Reducibility of polynomials and covering systems of congruences,” Acta Arithmetica 13 (1967), 91–101, DOI 10.4064/aa-13-1-91-101, was inspected through its discussion, Theorem 1, and closing page 101. It supplies relevant covering-system context and an attribution, but not the missing divisor-of-360 list. That source-return exception remains material.
One elementary finite bound is stronger than the small-pool calculation. For every \(L<55440\), let \(M(L)\) be the divisors \(m\) of \(L\) with \(m\ge4\) and \(m+1\) prime. An exact finite scan using a prime sieve and rational arithmetic finds
with the maximum attained at \(L=50400\). Therefore a covering of the required type, if it exists, has least common multiple at least \(55440\). This is a finite necessary-condition result, not a resolution of existence.
GCL's current state
The protected catalogue entry for problem 273 says open, with triage class PROTECTED_READY_BACKLOG and topics number theory and covering systems. The authenticated original issue is #1543. Its exact source-audit RESULT/1 comment has disposition PARTIAL: it records the statement, the finite lower-bound calculation, the missing Selfridge source detail, and the absence of an independently replayed later computational claim.
Accordingly, the documentary status is open: the inspected evidence neither proves nor disproves the \(p\ge5\) question. The live maintained Erdős entry still presents the same question, cites Erdős–Graham p. 24, records the prime-three remark involving divisors of \(360\), and reports no proof exposition. User comments and an external repository report stronger computational claims, but those are not primary theorem evidence and were not replayed here.
The pinned formal statement is FormalConjectures/ErdosProblems/273.lean at commit 85f863718beeec7b58a3a1926ee92e3472bc2020, Git blob b1776b86a96b8be7df63d8620a4c757d95c8aa74. It expresses the main proposition with answer(sorry) and a sorry proof; its relaxed \(p\ge3\) variant is marked solved but is also sorry-dependent. The Lean interface uses a strict covering-system structure over ideals, so semantic equivalence with the classical ordered congruence formulation still requires review. A pinned Lean file containing sorry, an external proof repository, or self-reporting CI is not mathematical certification.
What remains
The central mathematical task remains to decide existence: either exhibit finitely many distinct classes with every modulus \(p_i-1\) for a prime \(p_i\ge5\), or prove that no such finite cover exists. The reciprocal-sum obstruction can be strengthened by search, but it can never by itself prove nonexistence when the available reciprocal mass reaches \(1\); overlaps and residue placement must then be handled exactly.
For a bounded successor, one can audit the external candidate-generation and search artifacts at the exact commit reported in the source audit, veljjanoski/erdos273 commit c4c48a912b8c28d9ad03daa2b01752f8c986103f. A valid finite lower-bound claim would require agreement with the candidate list, a complete verdict for every candidate, no timeout or pruning ambiguity, and direct residue verification of any reported cover. Such a replay would establish only the tested lower bound.
Before any formal-status upgrade, the Lean definitions, ideal encoding, injectivity condition, natural-number subtraction, and correspondence with ordinary congruence classes need a semantic review. The missing primary residue list for Selfridge’s \(p=3\) example should either be recovered from an inspected source or remain explicitly unavailable. These are documentary and mathematical prerequisites, not reasons to call the open problem solved.
Sources and claim boundaries
- Pinned catalogue registry identifies issue 1543 and records issue-body SHA-256
ec162d2881e3fd675099f02e195d4d1d8194bf7e38ee24dedf82fcb4477bc7ae; the pinned catalogue packet isteorth/erdosproblemsat commit536408716724a2402bdfa7c1d764bf83d64a8c89, Git blob4e60263a80af6207aca494d2e1388e44fa372889. - Erdős–Graham, Old and New Problems and Results in Combinatorial Number Theory (1980), p. 24, inspected scan SHA-256
0cbf0c32f0ab1e1c71db5121a88bac905bf976c4a6ab6bb6d7d9cf9ddd184ed3. - Erdős, “Some Problems in Number Theory” (1971), pp. 408–409, inspected scan SHA-256
1caac961f69f76d7e6ce211412d9f93b082b5a3ccc37ff4670860b0f2e384425. - Schinzel, “Reducibility of polynomials and covering systems of congruences” (1967), Acta Arithmetica 13, 91–101; inspected publisher scan SHA-256
75cd11229845ef1e0f4043bd0416b2ab20926f9a69e419b055e0cd7e57d3850e. - Authenticated original issue #1543 and exact source-audit RESULT/1; these are documentary evidence, not mathematical certification.
- Live maintained entry #273 and the pinned FormalConjectures file, whose Git blob is
b1776b86a96b8be7df63d8620a4c757d95c8aa74; the supporting covering-system definition blob reported by the audit isc80959436e91f9f8e6dc923f6a9b2892254f3199.
The source audit is deliberately retained as PARTIAL. No source, finite calculation, formal file, external repository, or CI self-report in this article changes the protected ledger’s acceptance authority or certifies the mathematics.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1543 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: PROTECTED_READY_BACKLOG.
- 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.