Erdős Problem #254
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (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 distinct positive integers \(a_1<a_2<\cdots\), and let \(A(x)\) count how many of its terms are at most \(x\). Erdős asked whether two kinds of largeness force the sequence to make almost all large integers from distinct terms.
As \(x\to\infty\), the first condition says that every interval from \(x\) to \(2x\) eventually contains more and more members:
The second tests the sequence against every real number \(\theta\) with \(0<\theta<1\). Write \(\|y\|\) for the distance from \(y\) to the nearest integer. Erdős required
for every such \(\theta\). The proposed conclusion is exact: there is a threshold \(M\) such that every integer \(m\ge M\) is a sum of distinct elements of \(A\). The same element cannot be used twice, and the claim is eventual rather than a claim about every small integer.
This is Problem 254 on the modern site, but it is Problem 17 in Erdős's 1961 paper, where the relevant formulas are numbered (1.17.1) and (1.17.2). The notation is compact, but the quantifiers matter: one density condition and one divergent-series condition must hold for the same set \(A\), with the latter holding for every allowed \(\theta\).
A small example
Take the finite set \(A=\{1,2,\ldots,12\}\). It is not an example satisfying Erdős's asymptotic hypotheses: it is finite, so it is useful only for seeing what “sum of distinct elements” means at a small scale.
There are \(2^{12}=4096\) choices of a subset, but different subsets can have the same sum. An exhaustive integer check over all subsets nevertheless finds exactly the interval from \(0\) to \(78\), where \(78=1+2+\cdots+12\):
Thus every integer in that finite interval has a distinct-element representation. For instance, \(37=12+11+10+4\). The check is independently reproducible with the following short computation:
from itertools import combinations
A = tuple(range(1, 13))
S = {sum(c) for r in range(len(A) + 1) for c in combinations(A, r)}
assert S == set(range(sum(A) + 1))
The audit recorded 79 sums, minimum 0, maximum 78, and complete coverage of \(0\) through \(78\); a fresh replay gave the same result. This finite certificate says nothing about divergence, infinitely many terms, or the eventual assertion in Problem 254. Its value is narrower: it checks the finite-sum interface without pretending to test the open theorem.
What is known
The original Erdős implication remains unresolved in the sources checked here. No classical proof of the displayed hypotheses-to-conclusion statement was found in the source audit, and the official problem page continues to present it as a conjectural statement without a displayed solved status.
There is, however, a classical theorem that proves a stronger sufficient condition. Cassels's Theorem I assumes
and, for every \(0<\theta<1\),
Under these stronger assumptions, every sufficiently large integer is a sum of distinct elements of \(A\). Cassels proves this using the Hardy–Littlewood circle method. The first hypothesis is stronger because it requires the number of terms in each doubling interval to grow faster than \(\log\log x\). The squared condition is stronger as well: since \(0\le\|\theta a\|\le 1/2\), divergence of the sum of squares forces divergence of the sum of first powers. Cassels's result is therefore a proved subcase, not a solution of Problem 254.
The live Erdős Problems page also displays two proof-claim entries. Those are externally reported claims, not a classical theorem newly verified by this audit. The page shows no proof exposition and no displayed solved status; the claims must not be promoted to a proof or to a change in the problem's status without primary-source verification.
GCL's current state
The authenticated RESULT/1 audit on MATH-PROGRAMME issue #1524 is the current GCL source-audit record used for this draft. It identifies the exact statement, confirms Cassels's stronger theorem, and reports the finite certificate above. It also records the semantic gap between the original positive-integer sequence and the formal encoding over Set ℕ, including the use of natural-number subtraction in the counting expression.
The pinned catalogue registry binds Problem 254 to issue #1524, records status open, and identifies teorth/erdosproblems commit 536408716724a2402bdfa7c1d764bf83d64a8c89, file data/problems.yaml, blob 4e60263a80af6207aca494d2e1388e44fa372889. The registry's issue-body SHA-256 is eebf5ab5a52cd19fc93da0c8ac90737881f734c624cd2d5b68b5c007b8ec19c2; these identifiers preserve provenance, not mathematical truth.
The pinned Formal Conjectures file is at commit 85f863718beeec7b58a3a1926ee92e3472bc2020, blob fb9296b9d02d0e88c708370ec3d60936c0936c88. It contains the main statement and Cassels variant, but both theorem bodies are by sorry. Its presence, category label, and formalized metadata are not a checked Lean proof or a semantic-equivalence certificate.
What remains
A solution would need to bridge the gap between Erdős's weaker density and first-power divergence hypotheses and the stronger conditions used by Cassels, or find a genuinely different argument. In particular, it is not enough to verify a finite interval, restate the formal definition, or prove a local estimate for selected sets. One must establish the quantified implication for every admissible infinite set \(A\) and every relevant \(\theta\), with the eventual threshold for represented integers following from those hypotheses.
The immediate documentary tasks are more modest: reconcile the positive-integer wording with the ℕ formalization, decide how the natural-number count difference is intended to model the source, and verify whether the live page's post-pinned edits alter only metadata or also mathematical content. None of these tasks settles the problem. A future mathematical campaign would need a pinned source, explicit hypotheses, a falsifiable acceptance test, and a separate certification route for any claimed theorem.
Sources and claim boundaries
- Erdős, “Some Unsolved Problems,” Magyar Tud. Akad. Mat. Kutat. Int. Közl. 6 (1961), 221–254, Problem 17 p. 231, formulas (1.17.1)–(1.17.2): repository record and PDF.
- Cassels, “On the representation of integers as the sums of distinct summands taken from a fixed set,” Acta Scientiarum Mathematicarum 21 (1960), 111–124, Theorem I p. 111: repository record and PDF.
- Official Problem 254 page, which currently presents the conjectural statement and reports the Cassels variant; its displayed proof claims are not treated here as verified proofs.
- Pinned catalogue entry, pinned formal statement, and the complete RESULT/1 audit.
The article distinguishes three boundaries: Cassels's stronger theorem is classically proved; Erdős's original statement is currently unresolved in the checked evidence; and the page's proof claims are external reports awaiting verification. GCL has not independently certified either the open theorem or a formal proof. The manuscript becomes editorially accepted only by a protected admission matching its exact bytes, sources, and publicly verified mathematics.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1524 — 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.