Erdős Problem #1
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: disproved (not automatically the live result).
Subject areas: number theory, additive combinatorics.
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
Can a set of positive integers be unusually small while giving every selection of its members a different sum? A set with \(n\) members produces \(2^n\) possible subsets. Erdős proposed that if all those sums differ and the largest selected integer is \(N\), then \(N\) must remain at least a fixed positive fraction of \(2^n\), regardless of how large \(n\) becomes.
The original question was about a universal constant, not simply whether the necessary numbers grow exponentially.
A small example
The numbers \(1,2,4,8\) give the ordinary four-bit binary system: all 16 subset sums are distinct. But the set \(\{3,5,6,7\}\) also has 16 distinct subset sums, with largest number only 7 rather than 8. Clever arrangements can save space.
The delicate question is whether an improvement can become arbitrarily large relative to \(2^n\) as the number of elements increases.
What is known
The original conjecture is disproved. A 2026 computer-assisted formal development demonstrates that for every \(\varepsilon>0\), some sum-distinct sets satisfy \(N\leq\varepsilon 2^n\). Thus no fixed positive constant works as Erdős proposed.
The disproof is attributed to AI-generated work in the FrontierMath Erdős benchmark, preserved in the author-maintained Lean proof repository. The contemporary Formal Conjectures statement now records the negation. A local proof placeholder in that particular source file is not itself a checked proof.
This says no constant-factor lower bound exists. It does not say arbitrarily long sum-distinct sets can be made polynomially small.
GCL's current state
GCL's source investigation reconciled the original conjecture with the later disproof. A mathematical verification record independently reconstructed the conditional binary-block lemma: if a family of positive integer weights has no nonzero integer relation with each coefficient of absolute value below \(2^k\), replacing each weight by its \(k\) binary blocks produces \(dk\) distinct weights with distinct subset sums and a controlled upper bound. This statement assumes a relation-free family exists; it does not construct the large families needed for the full disproof.
GCL subsequently performed an actual source-pinned Lean replay of the author's Lean 4.28.0 development, using the author's exact source revision and Mathlib lock. The build succeeded, and both the conditional lemma and the final declaration disproving the original universal-constant conjecture passed type and axiom checks. The compiler reported only the standard axioms propext, Classical.choice and Quot.sound; a deliberately altered test removing the relation-freedom hypothesis was rejected. The preserved compiler receipt and critical review are publicly inspectable.
These are different levels of verification. GCL has reconstructed and critically tested the bounded lemma, and has independently run Lean's checker on the source author's development. GCL has not independently reconstructed and mathematically adjudicated every deep lattice and cube-gadget construction in the full disproof; it has not obtained independent human referee endorsement or MATHCERT certification. An accepted Lean kernel replay validates the specified formal claims under their recorded axioms; it does not by itself establish that every informal scientific interpretation has been independently verified.
What remains
The original yes/no conjecture has been disproved. Follow-up mathematics concerns the sharp quantitative constructions and bounds, the independent mathematical auditing of the source's deeper argument, and any separately authorized certification. The bounded binary-block transfer lemma is a verified component, not a substitute for this wider audit.
Sources and claim boundaries
- Erdős Problems #1 — original question and historical references; cached versions can predate the 2026 disproof.
- 2026 author-maintained Lean disproof — primary machine-readable proof source.
- Current Formal Conjectures definition — statement and proof attribution, not GCL certification.
- GCL source evidence #1270, bounded verification #3225, Lean and adversarial review #3238, and pinned replay run #43541084973 — source, mathematics, kernel and critical-review evidence; none grants MATHCERT certification.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1270 — 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.