Sets with Few Subset Sums

Abstract

It is a classical fact that every $n$-element set of positive reals has at least $\left(\genfrac{}{}{0ex}{}{n+1}{2}\right)+1$ distinct subset sums, with equality exactly for homogeneous arithmetic progressions (when $n\ge 4$). We establish stability versions of this inverse theorem in two regimes. First, for any parameter $M\le n-4$, we precisely characterize the $n$-element sets of positive reals with at most $\left(\genfrac{}{}{0ex}{}{n+1}{2}\right)+1+M$ subset sums. Second, for any constant $C$, we provide a characterization, sharp up to constants, of the $n$-element sets of positive reals with at most $C{n}^2$ distinct subset sums. Along the way, we constrain (for any fixed $d\ge 2$) the structure of $n$-element subsets of ${\mathbb{R}}^d$ with $o(n^{d+1})$ subset sums.

20 pages