Skip to content

Erdős Problem #202

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: solved (not automatically the live result).
Subject areas: 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

Choose pairwise distinct integers \(1<n_1<\cdots<n_r\le N\), and a residue class \(a_i\bmod n_i\) for each modulus. Require these classes to be pairwise disjoint: no integer satisfies two of the chosen congruences. Write \(f(N)\) for the largest achievable number \(r\) of classes.

Erdős and Stein asked how large \(f(N)\) can be. It is a problem about disjoint classes, not a covering system in which every integer must belong to at least one class.

A small example

The classes \(0\bmod2\) and \(1\bmod2\) are disjoint, but their moduli repeat, violating the distinct-modulus requirement. The classes \(0\bmod2\) and \(1\bmod4\) are disjoint and use distinct moduli; however, adding \(1\bmod3\) intersects both. To check compatibility, the generalized Chinese remainder theorem says two classes have a common solution exactly when \(a_i\equiv a_j\pmod{\gcd(n_i,n_j)}\). A valid family must therefore have unequal residues modulo every pairwise gcd.

What is known

The principal asymptotic is reported SOLVED by a May 2026 AI-assisted proof. Define

\[ L(N)=\exp\bigl(\sqrt{\log N\,\log\log N}\bigr). \]

The maintained Erdős #202 gives

\[ f(N)=N L(N)^{-1+o(1)}. \]

Erdős–Szemerédi (1968) first proved \(f(N)=o(N)\). Croot and later de la Bretéche, Ford and Vandehey improved bounds; the latter obtained upper exponent \(\sqrt3/2\) and lower exponent one on the \(L(N)\) scale. The 2026 argument, attributed explicitly to GPT-5.4 Pro prompted by Ho Boon Suan, combines the de la Bretéche–Ford–Vandehey argument with Park and Pham's resolution of the Kahn–Kalai expectation-threshold conjecture.

This status is an external solution report. The maintained catalogue reports a Lean proof, but no exact Lean artifact, proof term, theorem-lock mapping or independent GCL kernel execution has been validated here. The dependence on the Park–Pham theorem remains a substantial external proof dependency.

GCL's current state

Pinned and live status: SOLVED. Source task #1471 is outside strict open-problem triage; the frozen formal provider has no #202 statement. A source proof and a third-party formalization cannot be treated as an admitted GCL theorem merely because the catalogue marks it solved.

The original issue contains an authenticated RESULT/1 source report. This is unadjudicated source evidence only, not independent mathematical certification or editorial admission.

What remains

A bounded task enumerates \(1<n_i\le20\), builds the incompatibility graph of candidate residue classes using the pairwise gcd test, and finds maximal compatible families with exact search. Acceptance: all selected moduli are distinct, pairwise intersections are absent, and small exact maxima are independently checked. A separate proof-replay obligation is to capture the exact May 2026 argument, name its Park–Pham theorem dependency, and verify its limit translation without claiming novelty.

Sources and claim boundaries

No new covering-system asymptotic, independent Park–Pham proof or GCL Lean certificate is claimed.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1471 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
  • Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider 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