Skip to content

Erdős Problem #350

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: proved (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

Take a finite set \(A\) of positive integers. Form every sum obtained by choosing each member either zero times or one time. The set is called dissociated, or subset-sum-distinct, when two different choices never give the same sum. Erdős Problem 350 asks whether this strong additive separation forces the reciprocal total

\[ \sum_{n\in A}\frac{1}{n}<2. \]

The point is not that the elements are individually large. A dissociated set may begin with \(1\), but adding many small integers creates collisions among subset sums. The question asks for a uniform bound on the total reciprocal mass of every finite set that avoids those collisions.

The issue-specific source packet is original issue #1620, assignment ERDOS-CATALOGUE-0350-S01. The original SOURCE RESULT/1 citation is authenticated original RESULT/1. This article records the source inquiry only; the V2 ledger, rather than this article, decides accepted coverage.

A small example

Let \(A=\{1,2,4\}\). Its subsets have sums

\[ 0,1,2,3,4,5,6,7, \]

so all eight sums are different. Exact rational arithmetic gives

\[ \frac11+\frac12+\frac14=\frac74<2. \]

This example also reaches the sharper finite bound reported for the original proof: with \(|A|=3\), \(2-2^{1-|A|}=2-2^{-2}=7/4\). The same pattern is the power-of-two set \(\{1,2,4,\ldots,2^{n-1}\}\), whose subset sums are all integers from \(0\) through \(2^n-1\) and whose reciprocal sum is \(2-2^{1-n}\).

The check was performed with exact, not floating-point, arithmetic. A reproducible core is:

from fractions import Fraction
from itertools import combinations

A = (1, 2, 4)
sums = [sum(c) for r in range(4) for c in combinations(A, r)]
assert sorted(sums) == list(range(8))
total = sum((Fraction(1, n) for n in A), Fraction(0))
assert total == Fraction(7, 4) and total < 2

This verifies one finite instance and illustrates equality in the stronger finite estimate. It does not prove the universal statement, the equality classification, or any Lean theorem.

What is known

The maintained Erdős Problems entry, read on 2026-10-12, states the finite positive-integer problem and describes it as proved. It attributes the proof to C. Ryavec, says that Ryavec did not appear to publish it, and says that the proof is reproduced in S. J. Benkoski and P. Erdős, “On weird and pseudoperfect numbers,” Mathematics of Computation 28 (1974), 617–623. The linked primary source copy is the 1974 paper. The entry also reports the sharper inequality \(\sum 1/n\leq 2-2^{1-|A|}\), with equality for the power-of-two initial segment.

The primary paper by F. Hanson, J. M. Steele, and F. Stenger, “Distinct sums over subsets,” Proceedings of the American Mathematical Society 66 (1977), 179–180, gives a strengthening. Its opening statement assumes \(1\leq a_1<a_2<\cdots<a_n\) and all \(0\)–\(1\) subset sums distinct, then proves for every real \(s>0\) that

\[ \sum_{i=1}^{n}\left(\frac{1}{a_i}\right)^s<\frac{1}{1-2^{-s}}. \]

At \(s=1\) this implies the original strict inequality. The paper’s proof uses the generating-function inequality forced by distinct subset sums and an integral substitution; this is external mathematical evidence, not a GCL certification.

GCL's current state

The frozen catalogue input is teorth/erdosproblems commit 536408716724a2402bdfa7c1d764bf83d64a8c89, with the exact data/problems.yaml blob 4e60263a80af6207aca494d2e1388e44fa372889 . Entry 350 records informal status proved, formal status Lean, statement formalized yes, and last updates dated 2025-11-25 or 2025-08-31. The issue packet separately assigns the protected Programme triage class OUTSIDE_STRICT_OPEN_TRIAGE; that classification is preserved here.

The pinned formal provider is google-deepmind/formal-conjectures commit 85f863718beeec7b58a3a1926ee92e3472bc2020, file FormalConjectures/ErdosProblems/350.lean, blob cf6f059393673078e5f19ef64a603bf5de15f723. It defines a finite-set predicate requiring distinct sums for distinct subfinsets and states the reciprocal theorem for Finset ℕ. The theorem body is by sorry; the file’s metadata points to an external formal-proof report, but no replay was performed here. The file also contains a stronger \(s>0\) variant, likewise with sorry.

What remains

The core source audit is ready for a bounded successor that compares the Ryavec/Benkoski–Erdős proof line by line with the formal predicates. The first target should be a proved interface lemma: from the formal distinct-subset-sums hypothesis, derive that zero cannot belong to the finite set, sort the remaining entries as positive integers, and translate the set formulation into the ordered tuple formulation used by the 1977 paper. A second bounded target can formalize the exact finite example above and the generating-function inequality at a fixed finite input.

Acceptance should require exact quantifier matching, no hidden positivity assumption, and a source citation for every imported step. Falsification is any counterexample to the translation, any denominator-at-zero gap, or any mismatch between strict and non-strict conclusions. The task should stop after the interface and one finite sanity check, without claiming to replay the external proof or certify the universal theorem.

Sources and claim boundaries

The primary evidence consists of the 1974 paper’s reported reproduction of Ryavec’s proof and the 1977 paper’s published strengthening, with bibliographic details also exposed by the live entry. The live entry currently says “formalised in Lean,” and the frozen catalogue says proved (Lean), but those labels are status evidence rather than mathematical certification by GCL. The pinned Lean source is a theorem statement and API layer whose principal proof is still sorry at the inspected commit.

The date boundary matters: the live page was fetched on 2026-10-12, while the frozen catalogue metadata is pinned to its stated commits and update dates. No claim is made here about later catalogue edits, unpublished proof files, novelty, awards, or acceptance. The original issue remains the provenance surface, and the original SOURCE RESULT/1 citation remains authenticated original RESULT/1.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1620 — 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.

Back to catalogue · Compendium introduction