Distinct subset sums: must n integers with all $2^n$ subset sums distinct reach $N\gg 2^n$? (Erdős #1)
Statement
If $A\subseteq \{1,\ldots,N\}$ with $\lvert A\rvert=n$ is such that the subset sums $\sum_{a\in S}a$ are distinct for all $S\subseteq A$ (such a set is called dissociated), must $$N \gg 2^{n},$$ i.e. is there an absolute constant $c>0$ such that every such $A$ forces $N\geq c\cdot 2^n$? Equivalently: if $F(x)$ denotes the maximum size of a dissociated subset of $[1,x]$, is $F(x)\leq \log_2 x+O(1)$?
Acceptance. FULLY RESOLVES: a proof that there is an absolute constant $c>0$ with $N\geq c\cdot 2^n$ for every dissociated $A\subseteq\{1,\ldots,N\}$ of size $n$ — machine-checkable (Lean/Coq) preferred, else a complete written proof; OR a disproof: an explicit infinite family of dissociated sets with $N=o(2^n)$, with a full proof of dissociativity and of the asymptotics (each finite member should be independently machine-verifiable). ADVANCES: (a) improve the lower-bound constant strictly beyond the best bound stated in the background, with proof; (b) an explicit construction family with certified distinct subset sums achieving a constant strictly below the best construction constant stated in the background, with proof valid for infinitely many $n$; (c) extend the exact values of the minimal-$N$ sequence (OEIS A276661) to new $n$, with search code and a machine-checkable optimality/exhaustiveness certificate; (d) prove or disprove the Conway–Guy conjecture $F(2^k)=k+2$ for large $k$. Deliver the proof file, or the construction + verification code + proof, or the search code + new terms + certificates.
Background
Erdős called this 'perhaps my first serious problem', dating it to 1931 [Er98]; it recurs across dozens of his papers ([Er56], [Er61], [Er73], [ErGr80, p.59], [Er85c], [Va99, 1.20], among many others) and is problem C8 of Guy's collection [Gu04]. Erdős offered $500 for a solution. Listed as open on erdosproblems.com/1 (fetched 2026-07-13, status 'open', tagged 'number theory | additive combinatorics'). Upper bounds (constructions): powers of 2 give $N\leq 2^{n-1}$ and show $2^n$ would be best possible; Conway–Guy [CoGu68] (see also [Gu82]) improved this to $N\leq 2^{n-2}$ for large $n$, and the best known construction, due to Bohman, achieves $N\leq 0.22002\cdot 2^n$. Lower bounds: trivially $N\gg 2^n/n$ (all $2^n$ sums lie in $[0,Nn)$); Erdős–Moser [Er56] proved $N\geq (\tfrac14-o(1))2^n/\sqrt{n}$, and Erdős offered $100 for improving the constant $\tfrac14$ — since achieved: after a chain of improvements (history in [St23]) the record constant is $\sqrt{2/\pi}$, first obtained in unpublished work of Elkies and Gleason; Dubroff–Fox–Xu [DFX21] give two proofs, in fact proving the clean exact bound $N\geq \binom{n}{\lfloor n/2\rfloor}$. Conway and Guy conjectured $F(2^k)=k+2$ for all large $k$ (Erdős: 'no opinion' [Er80]). The generalisation to reals $A\subseteq(0,N]$ with subset sums differing by at least 1 (first in [Gr71]) carries the same conjectured bound, and the second [DFX21] proof covers it. The minimal $N$ for each $n$ is OEIS A276661; a formalized statement exists in google-deepmind/formal-conjectures. The attacker's tool: construction search in the Conway–Guy style (explicit families with certified distinct subset sums) to push the $0.22002$ constant down, and exhaustive search to extend the exact minimal-$N$ sequence A276661; the conjecture itself is proof-shaped.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #1 (T. F. Bloom) | website |
| REF-02 | OEIS A276661 — minimal N such that {1,...,N} contains an n-element subset with distinct subset sums | website |
| REF-03 | Formalized statement of Erdős #1 (google-deepmind/formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.