Skip to content

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

\[ 1<m_1<\cdots<m_k \]

such that

\[ \forall x\in\mathbb Z\;\exists i\in\{1,\ldots,k\}\quad x\equiv a_i\pmod{m_i}, \]

and, separately for each index \(i\),

\[ \exists p_i\text{ prime}\quad p_i\ge5\ \text{and}\ m_i=p_i-1. \]

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:

\[ 0\pmod 2,\quad 0\pmod 3,\quad 1\pmod 4,\quad 3\pmod 8,\quad 7\pmod{12},\quad 23\pmod{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

\[ L\le\sum_i\frac{L}{m_i},\qquad\text{hence}\qquad\sum_i\frac1{m_i}\ge1. \]

For the restricted primes \(p\le31\), the possible moduli are \(4,6,10,12,16,18,22,28,30\), and exact integer arithmetic gives

\[ \frac14+\frac16+\frac1{10}+\frac1{12}+\frac1{16}+\frac1{18}+\frac1{22}+\frac1{28}+\frac1{30}=\frac{46157}{55440}<1. \]

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

\[ \max_{L<55440}\sum_{m\in M(L)}\frac1m=\frac{12473}{12600}<1, \]

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

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.

Back to catalogue · Compendium introduction