Erd\H{o}s called this 'perhaps my first serious problem' (in \cite{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\H{o}s and Moser \cite{Er56} proved\[ N\geq (\tfrac{1}{4}-o(1))\frac{2^n}{\sqrt{n}}.\](In \cite{Er85c} Erd\H{o}s offered \$100 for any improvement of the constant $1/4$ here.)

A number of improvements of the constant have been given (see \cite{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 \cite{DFX21}, who in fact prove the exact bound $N\geq \binom{n}{\lfloor n/2\rfloor}$.

In \cite{Er73} and \cite{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 \cite{DFX21} applies also to this generalisation.) This generalisation seems to have first appeared in \cite{Gr71}.

This problem appears in Erd\H{o}s' book with Spencer \cite{ErSp74} in the final chapter titled 'The kitchen sink'. As Ruzsa writes in \cite{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 \cite{Gu04}.


References


[DFX21] Dubroff, Q. and Fox, J. and Xu, M. W., A note on the Erd\H{o}s distinct subset sums problem. SIAM Journal on Discrete Mathematics (2021), 322-324.

[Er56] Erd\H{o}s, P., Problems and results in additive number theory. Colloque sur la Th\'{e}orie des Nombres, Bruxelles, 1955 (1956), 127-137.

[Er73] Erd\H{o}s, P., Problems and results on combinatorial number theory. A survey of combinatorial theory (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971) (1973), 117-138.

[Er85c] Erd\H{o}s, P., On some of my problems in number theory I would most like to see solved. Number theory (Ootacamund, 1984) (1985), 74-84.

[Er98] Erd\H{o}s, Paul, Some of my new and almost new problems and results in combinatorial number theory. Number theory (Eger, 1996) (1998), 169-180.

[ErGr80] Erd\H{o}s, P. and Graham, R., Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathematique (1980).

[ErSp74] Erd\H{o}s, Paul and Spencer, Joel, Probabilistic methods in combinatorics. Akad\'{e}miai Kiad\'{o} (1974).

[Gr71] Graham, R. L., On sums of integers taken from a fixed sequence. (1971), 22--40.

[Gu04] Guy, Richard K., Unsolved problems in number theory. (2004), xviii+437.

[Ru99] Ruzsa, I., Erd\H{o}s and the Integers. Journal of Number Theory (1999), 115-163.

[St23] Steinerberger, S., Some remarks on the Erd\H{o}s distinct subset sums problem. arXiv:2208.12182 (2023).