Erdős #1 — distinct subset sums need N ≫ 2^n

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$, then $$N \gg 2^{n}.$$ Equivalent formulation (dissociated sets): let $F(x)$ be the maximal size of a set of integers in $[1,x]$ all of whose subset sums are distinct. The problem is equivalent to $F(x) < \log_2 x + O(1)$.

Facts

- Prize \$500; status open, and erdosproblems.com/1 explicitly marks it "cannot be resolved with a finite computation" (site-owner belief) — it is an asymptotic statement over all $n$, not a single checkable instance. - Falsifiable: no — needs a genuine proof (or disproof via an infinite family), not a finite counterexample. - Origin: Erdős called this "perhaps my first serious problem," dating it to 1931 in [Er98]. Restated across [Er56] [Er57] [Er59] [Er61] [Er65b] [Er69] [Er70b] [Er70c] [Er73] [BeEr74,p.619] [ErSp74] [Er75b] [Er77c] [Er80,p.97] [ErGr80,p.59] [Er81] [Er82e] [Er85c] [Er90] [Er91] [Er92b] [Er95,p.165] [Er97c] [Er98] [Va99,1.20]. Appears as the final entry ("The kitchen sink") of Erdős–Spencer's book [ErSp74]. - Upper bound chain (constructions of large dissociated sets, pushing $N$ down toward $2^n$): - Trivial: powers of $2$ give $N \leq 2^{n-1}$. - Conway & Guy [CoGu68] (see [Gu82]): $N \leq 2^{n-2}$ for large $n$, via an explicit recursive construction. - Best known: Tom Bohman, "A construction for sets of integers with distinct subset sums," Electron. J. Combin. 5 (1998), #R3, https://doi.org/10.37236/1341 — $N < 0.22002\cdot 2^n$ for $n$ sufficiently large. Still the record as of this search. - Conway–Guy conjectured (see [Gu82]) the sharper $F(2^k)=k+2$ for all large $k$ (i.e. that $2^{n-2}$-type constructions are essentially optimal), but Erdős himself wrote in [Er80] he had "no opinion" on this. - Lower bound chain (forcing $N$ up): - Trivial pigeonhole: $N \gg 2^n/n$ (all $2^n$ distinct subset sums must lie in $[0,Nn)$). This trivial bound *is* proved in the Lean formalization (see below). - Erdős & Moser [Er56]: $N \geq (\tfrac14-o(1))\frac{2^n}{\sqrt n}$, via the second-moment/variance method applied to the random $\pm1$-signed sum $X=a_1\varepsilon_1+\dots+a_n\varepsilon_n$. Erdős later offered \$100 for any improvement of the constant $\tfrac14$ [Er85c]. - Several intermediate constant improvements followed (history collected in Steinerberger, arXiv:2208.12182). - Current record constant $\sqrt{2/\pi}$: first proved in unpublished work of Elkies and Gleason. Confirmed and given two independent proofs by Quentin Dubroff, Jacob Fox, Max Wenqiang Xu, "A note on the Erdős distinct subset sums problem," arXiv:2006.12988 — who moreover prove the *exact*, sharper bound $N \geq \binom{n}{\lfloor n/2\rfloor}$ (which recovers the $\sqrt{2/\pi}\cdot 2^n/\sqrt n$ asymptotic via Stirling). One of the two DFX21 proofs also extends to the real-valued generalization below. - Stefan Steinerberger, "Some Remarks on the Erdős Distinct Subset Sums Problem," arXiv:2208.12182: an independent Fourier-analytic re-derivation of the same $\sqrt{2/\pi}$ constant via the identity $\int_{\mathbb R}\left(\frac{\sin x}{x}\right)^2\prod_{i=1}^n\cos(a_ix)^2\,dx \geq \pi/2^n$ (extending Elkies), with equality iff all subset sums are exactly $1$-separated; the key insight is that dissociation plus small $\max A$ forces the Rademacher sum $X=\pm a_1\pm\cdots\pm a_n$ to be close to Gaussian. - Generalization to reals: $A\subseteq(0,N]$ a set of reals with all subset sums pairwise $\geq 1$ apart, same conjectured bound — proposed in [Er73], [ErGr80], first appearing in [Gr71]. The second DFX21 proof (arXiv:2006.12988) applies to this version too. - Modular variant (finite-field analogue): Stijn Cambie, Jun Gao, Younjin Kim, Hong Liu, "The Erdős distinct subset sums problem in a modular setting," arXiv:2308.03748 — for subset sums distinct mod $N=2^n+t$, prove $\max A \geq (\tfrac13-o(1))N$ and show $\tfrac13$ is sharp; characterize extremal structure for small $t$. - Higher-dimensional variant: Zijie Gu, "A Generalisation on Erdős Distinct Subset Sums Problem," arXiv:2510.06032 (Oct 2025) — studies the analogue in $\mathbb Z^k$, improving bounds in some dimensions via alternative moment statistics ($\mathbb E[\lVert X\rVert_1]$, $\mathbb E[\lVert X\rVert_3^3]$) beyond the classical variance method. - Adjacent "inverse" problem (not #1 itself, opposite extreme — *few* subset sums instead of distinct): Ruben Carpenter, Colin Defant, Noah Kravitz, "Sets with Few Subset Sums," arXiv:2605.05498 — stability/inverse theorem characterizing $n$-sets with close-to-minimally-many ($\binom{n+1}2+1+M$) distinct subset sums as near-arithmetic-progressions. - Sequence: minimal $N$ for given $n$ is OEIS A276661. - Formalized in Lean: yes, google-deepmind/formal-conjectures/FormalConjectures/ErdosProblems/1.lean — states erdos_1 (the actual conjecture) with proof sorry (open); only proves the *weaker*, trivial pigeonhole bound $N \gg 2^n/n$ as erdos_1.variants.weaker. - Discussed as problem C8 in Guy's collection [Gu04]; Ruzsa on this problem's home in Erdős–Spencer's book: "it is a rich kitchen where such things go to the sink" [Ru99]. - No genuine solution attempt found in the forum/GitHub trail: github.com/teorth/erdosproblems issue #251 ("Possible solution of #10 and #1") posted an AI-generated paper invoking a fabricated "Diophantine Energy Operator" / "Major Arc Satiation Protocol" framework with no actual connection to subset sums; it was closed and is pure noise, not a lead — flagged here as a documented dead end / failure mode of naive LLM attempts on this problem. - Related problems: erdos/350.

Literature state

Not resolved. This is a genuinely open, ~95-year-old problem, actively refined on both sides but with no proof or disproof of $N\gg 2^n$ closing the gap to a determined constant. Concretely: - Best proven lower-bound constant: $\sqrt{2/\pi}\approx0.7979$ (exact form $N\geq\binom{n}{\lfloor n/2\rfloor}$, DFX21 arXiv:2006.12988, confirming unpublished Elkies–Gleason; independently re-derived by Steinerberger arXiv:2208.12182). - Best proven upper-bound constant: $0.22002$ (Bohman 1998, doi:10.37236/1341). - These leave roughly a factor-of-$3.6$ gap in the constant, and the deeper structural question (Conway–Guy's $F(2^k)=k+2$ conjecture, i.e. whether the *true* extremal behavior matches the $2^{n-2}$-type constructions) is separately open, with Erdős professing no opinion on it [Er80]. - No AI system (LLM, AlphaEvolve, Aristotle, or otherwise) is credited with any progress on this problem in any source found; the one AI-attributed artifact found (GitHub issue #251) is vacuous and was rejected. - The companion problem erdos/350 (bounding $\sum_{n\in A}1/n<2$ for dissociated $A$) is fully PROVED (Ryavec, unpublished, reproduced in [BeEr74]; sharpened by Hanson–Steele–Stenger [HSS77]) and Lean-formalized — showing the broader "dissociated set" toolkit does yield full resolutions on adjacent questions, just not on the core exponential bound itself. - Recent activity (2021–2025) is concentrated on: (i) matching/re-deriving the $\sqrt{2/\pi}$ constant by different proof techniques (variance method vs. Fourier/characteristic-function method) — suggesting this constant may be a genuine "natural" barrier reachable by multiple independent routes; (ii) variants (modular, higher-dimensional) rather than the core problem, which has resisted a matching-constant resolution since Bohman 1998.

Attack surface

- Mode: literature-resolution + derivation (not finite-search — the site itself states this cannot be resolved by finite computation, since it's a statement for all $n$). - Concrete first experiment: this problem itself is not a runnable finite search, but two genuinely scoped, finite sub-experiments exist: (1) pull the OEIS A276661 values (exact minimal $N(n)$, computed for small $n$) and check them against both the Conway–Guy conjectured formula $F(2^k)=k+2$ and Bohman's asymptotic constant, to see how far exact computation currently reaches and whether the data favors the Conway–Guy extremal structure; (2) fully read and formalize (Lean, extending the existing google-deepmind/formal-conjectures/.../1.lean stub) either Bohman's explicit greedy/probabilistic construction or one of the two DFX21 proofs of $N\geq\binom{n}{\lfloor n/2\rfloor}$ — a concrete, finishable, citable task that doesn't resolve the conjecture but produces machine-checked confidence in the best current bounds and exercises exactly the "derivation" muscle (second-moment method + Fourier/anticoncentration method) needed to attack the gap. - Oracle: none for the core asymptotic (unfalsifiable by finite means); for the sub-experiments, mechanical — OEIS values are directly comparable, and a Lean proof either compiles (verified) or doesn't. - Feasibility: honest read — famous and hard. Open since 1931, attacked by Erdős–Moser, Conway–Guy, Elkies–Gleason, Bohman, and (most recently) Dubroff–Fox–Xu and Steinerberger using genuinely different techniques (second-moment/variance method vs. Fourier/characteristic-function anticoncentration), yet the constant gap ($0.22$ to $0.80$) has not moved on the upper-bound side since 1998. Full resolution is not in reach for a direct attack. The realistic contribution is either (a) tracking/formalizing the existing best bounds, or (b) attempting the well-defined but still-hard Conway–Guy sub-conjecture computationally for specific small $k$ via ILP/SAT search over dissociated sets (ties to SAT/CP-SAT-based finite counterexample search and verification machinery already used elsewhere in this wiki), which is finite for each fixed $k$ even though "for all large $k$" is not.

Related

- erdos/350 — the "See also" companion problem on erdosproblems.com: for dissociated $A$, $\sum_{n\in A}1/n<2$. This one is fully proved (Ryavec, unpublished; reproduced in [BeEr74]; sharpened by Hanson–Steele–Stenger) and Lean-formalized — the clearest evidence that the dissociated-set toolkit *can* close some questions in this family, just not the exponential bound itself. - Second moment method / Paley–Zygmund inequality — variance-based random-structure existence proofs — Erdős–Moser's original variance-method lower bound, and one of the two DFX21 (arXiv:2006.12988) proofs. - concept/fourier-anticoncentration — the Elkies/Steinerberger (arXiv:2208.12182) characteristic-function integral $\int(\sin x/x)^2\prod\cos(a_ix)^2\,dx\geq\pi/2^n$, forcing near-Gaussianity of the Rademacher sum; the other DFX21 proof route. - concept/dissociated-sets — the equivalent Sidon-type additive-combinatorics formulation ($F(x)<\log_2 x+O(1)$) used throughout the literature (Ruzsa, Conway–Guy). - concept/greedy-probabilistic-construction — Bohman's 1998 explicit construction technique giving the best known upper bound $0.22002\cdot2^n$. - Lean 4 formalization of constructions and conditional reductions (Erdős-problem context) — google-deepmind/formal-conjectures project; problem stated but sorryd, only the trivial bound proved, a concrete formalization target. - SAT/CP-SAT-based finite counterexample search and verification — proposed mechanism for probing the finite Conway–Guy sub-conjecture ($F(2^k)=k+2$) for specific small $k$.