Erdős Problem #253
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: disproved (not automatically the live result).
Subject areas: number theory.
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.
Documentary explanation. Editorial acceptance is determined by the protected V2 admissions ledger and the exact manuscript source hash. This article does not confer mathematical certification.
The question in plain language
Start with an increasing sequence of integers
whose relative gaps shrink: \(a_{i+1}/a_i\to1\). A distinct subset sum means adding each selected term at most once, with only finitely many terms selected. Erdős asked whether the following implication holds: if every infinite arithmetic progression contains infinitely many such subset sums, must every sufficiently large positive integer be a subset sum?
“Sufficiently large” means that all but finitely many positive integers are represented. The quantifiers matter. The hypothesis is not merely that each progression contains one represented number, and the conclusion is not merely that there are infinitely many represented numbers. In the printed 1961 source, Problem 17 on p. 230 continues onto p. 231. Its displayed condition is \(a_{i+1}/a_i\to1\); the scan does not separately state positivity, whereas the maintained page and the formal declaration use a positive sequence. That normalization is harmless for the positive counterexample below, but it should not be silently attributed to the original wording.
The answer is no. J. W. S. Cassels constructed a positive increasing sequence satisfying the progression hypothesis and the shrinking-gap condition while making its distinct subset sums arbitrarily sparse in the precise parameterized sense stated below. The maintained page summarizes this as “density 0”; the theorem’s printed quantifiers are the safer claim to use here. Thus this is a classically disproved problem, not an open conjecture.
A small example
Here is a reproducible finite sanity check for the kind of subset-sum calculation involved. It is an irrational-rotation toy slice, not Cassels’s infinite construction and not a proof of any asymptotic assertion.
from math import sqrt
alpha = (sqrt(5) - 1) / 2
epsilon = .5
C = [d for d in range(1, 20001)
if abs(d * alpha - round(d * alpha)) < d ** (-(1 + epsilon) / 2)]
reachable = {0}
for d in C[:18]:
reachable |= {x + d for x in tuple(reachable)}
print(len(C), C[:18], len(reachable), min(reachable), max(reachable))
print(all(n in reachable for n in range(201)))
The independently rerun output is 87 [1, 2, 3, 5, 8, 13, 16, 21, 26, 29, 34, 42, 47, 55, 68, 76, 89, 110] 646 0 645 followed by True. So these 18 distinct summands represent every integer from \(0\) through \(200\) in this finite computation. The result demonstrates how a reachable-set update works; it does not show that the displayed toy sequence meets every arithmetic progression infinitely often, has the required ratio limit, or has density-zero subset sums. Those are infinite claims supplied only by a mathematical source.
A simpler finite principle is also useful for orientation: if the available summands are \(1,2,\ldots,m\), their distinct subset sums include every integer from \(0\) through \(m(m+1)/2\) by induction. Even that exact finite coverage says nothing by itself about a prescribed infinite sequence or about eventual coverage.
What is known
The decisive result is Cassels, “On the representation of integers as the sums of distinct summands taken from a fixed set,” Acta Scientiarum Mathematicarum (Szeged) 21 (1960), 111–124. Theorem II is on p. 112; the construction is carried out in the proof on pp. 122–124. For each chosen \(\varepsilon>0\), Cassels constructs positive integers \(c_1<c_2<\cdots\) with
with infinitely many elements of the set \(C=\{c_1,c_2,\ldots\}\) in every arithmetic progression, and with \(S(n)<\varepsilon n\) for every \(n\), where \(S(n)\) counts integers at most \(n\) expressible as sums of distinct elements of \(C\). The first property implies \(c_{n+1}/c_n\to1\) (choose any \(\varepsilon<1/2\)), and every element of \(C\) is itself a one-term distinct sum. Hence the progression hypothesis holds for the subset sums. Taking, for example, \(\varepsilon<1/2\), the estimate \(S(n)<\varepsilon n\) is incompatible with cofinite representation, which would force \(S(n)/n\to1\).
This is a borrowed theorem, not a GCL reconstruction of Cassels’s proof. Erdős’s “Some Unsolved Problems,” Magyar Tud. Akad. Mat. Kutató Int. Közl. 6 (1961), 221–254, records Problem 17 on pp. 230–231 and explicitly says there that Cassels disproved it. The theorem statement above is deliberately not used to infer that one fixed \(C\) has density zero: \(C\) depends on the chosen \(\varepsilon\). It is already enough to refute cofinite representation by fixing one \(\varepsilon<1\). The 1999 booklet Some of Paul’s Favorite Problems, item 1.24, revisits a weaker-looking condition requiring at least one represented integer in each residue class or progression. That later formulation should not be called logically identical to Erdős’s “infinitely many” hypothesis without a separate normalization argument; Cassels’s stronger counterexample nevertheless defeats both.
GCL's current state
The protected catalogue registry in this checkout records problem 253 as disproved, with triage class OUTSIDE_STRICT_OPEN_TRIAGE, and binds it to GCL issue #1523. The authenticated RESULT/1 comment on that issue has disposition PARTIAL: it is source-audit evidence, not mathematical certification. It identifies the same Cassels theorem, source pages, finite check, and unresolved replay obligations.
The pinned catalogue packet is teorth/erdosproblems commit 536408716724a2402bdfa7c1d764bf83d64a8c89; its entry says informal status disproved, formal status Lean, and disproved (Lean). The live catalogue file has a different whole-file hash, but the read-back entry has the same status fields. This is file-level drift without observed entry-level status drift, not permission to replace the pinned source lock.
The pinned FormalConjectures file is 253.lean at commit 85f863718beeec7b58a3a1926ee92e3472bc2020. It defines RepresentsAPs using a strictly monotone map \(a:\mathbb N\to\mathbb N\) and infinite arithmetic-progression sets in \(\mathbb N\), assumes \(0<a(0)\) and the real limit of consecutive ratios, and concludes that subsetSums (Set.range a) is cofinite. Its theorem body is by sorry. The current live file adds a metadata pointer to an external Lean file at commit 1268917deaaaa0d674f651287027baa26cea9920. That is a reported formal-proof pointer, not a GCL replay or certification. The index shift from \(a_1\) to \(a(0)\), the domain restriction to \(\mathbb N\), and the exact meaning of IsAPOfLength ⊤ remain formalization details to check.
What remains
There is no remaining classical problem to solve: Cassels’s published counterexample settles the original implication. Remaining work is evidentiary and semantic. A careful formal audit should compare every hypothesis of Cassels Theorem II with the Lean witness, including positivity, strict monotonicity, the arithmetic-progression domain, the ratio-limit expression, and the cofinite conclusion. It should also replay the external Lean source in its declared toolchain and record the exact result. Until that occurs, “formalized” and “formal proof” remain upstream reports, not GCL certification.
The source wording deserves preservation rather than repair by paraphrase. Erdős’s scan says “integers” and does not visibly add \(a_1\ge1\); the current maintained page says “infinite arithmetic progression,” gives the \(1\le a_1\) normalization, and summarizes Cassels’s gap as \(a_{i+1}-a_i<a_i^{1/2+o(1)}\). The page was last edited 23 January 2026. The weaker 1999 formulation and any claim that it is equivalent require their own precise domain and quantifier proof.
Sources and claim boundaries
- Original statement: P. Erdős (1961), “Some Unsolved Problems,” pp. 221–254; Problem 17, pp. 230–231. Primary scan.
- Counterexample theorem: J. W. S. Cassels (1960), “On the representation of integers as the sums of distinct summands taken from a fixed set,” Acta Sci. Math. (Szeged) 21, 111–124; Theorem II, p. 112; construction, pp. 122–124. Repository record and scan.
- Maintained problem page: Erdős Problems #253, live page checked 12 October 2026; it reports
DISPROVEDand the 23 January 2026 edit. - Pinned source packet and authenticated audit: GCL issue #1523, its pinned catalogue entry at commit 536408716724a2402bdfa7c1d764bf83d64a8c89, and authenticated RESULT/1. The protected catalogue entry is documentary status, not a theorem certificate.
- Formal declaration: Pinned FormalConjectures file; current live file. The external Lean pointer is reported provenance only; no Lean build or kernel replay is claimed here.
- Later wording: Some of Paul’s Favorite Problems (Budapest, 1999), item 1.24. Scan. It is used only to record the weaker formulation and its boundary.
The finite program is independently reproducible arithmetic, not an infinite proof. Cassels’s theorem is the classical resolution, borrowed with its cited author, year, theorem, and pages. This article claims neither a new lemma nor a formal certification, and it does not turn an external Lean pointer, a maintained-page label, or a protected source return into GCL mathematical authority.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1523 — 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.