Erdős Problem #1

declared status 'open'. Formalized: yes. 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}.$$ Current best: 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 [Er56] proved$$N\geq (\tfrac{1}{4}-o(1))\frac{2^n}{\sqrt{n}}.$$(In [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}$. Prize:$500. OEIS: A276661. Tags: additive combinatorics, number theory.

Notation is rendered from the stored source. The pinned checkout remains the exact record.