OPEN
This is open, and cannot be resolved with a finite computation.
- $500
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}.\]
Erdős called this 'perhaps my first serious problem' (in
[Er98] he dates it to 1931). The powers of $2$ show that $2^n$ would be best possible here. The trivial lower bound is $N \gg 2^{n}/n$, since all $2^n$ distinct subset sums must lie in $[0,Nn)$. Erdős and Moser
[Er56] proved\[ N\geq (\tfrac{1}{4}-o(1))\frac{2^n}{\sqrt{n}}.\](In
[Er85c] Erdős offered \$100 for any improvement of the constant $1/4$ here.)
A number of improvements of the constant have been given (see
[St23] for a history), with the current record $\sqrt{2/\pi}$ first proved in unpublished work of Elkies and Gleason. Two proofs achieving this constant are provided by Dubroff, Fox, and Xu
[DFX21], who in fact prove the exact bound $N\geq \binom{n}{\lfloor n/2\rfloor}$.
In
[Er73] and
[ErGr80] the generalisation where $A\subseteq (0,N]$ is a set of real numbers such that the subset sums all differ by at least $1$ is proposed, with the same conjectured bound. (The second proof of
[DFX21] applies also to this generalisation.)
This problem appears in Erdős' book with Spencer
[ErSp74] in the final chapter titled 'The kitchen sink'. As Ruzsa writes in
[Ru99] "it is a rich kitchen where such things go to the sink".
The sequence of minimal $N$ for a given $n$ is
A276661 in the OEIS.
See also
[350].
This is discussed in problem C8 of Guy's collection
[Gu04].
View the LaTeX source
This page was last edited 30 September 2025.
