A construction for sets of integers with distinct subset sums

Tom Bohman


A set S of positive integers has distinct subset sums if there are $2^{|S|}$ distinct elements of the set $\left\{ \sum_{x \in X} x: X \subset S \right\} . $ Let $$f(n) = \min\{ \max S: |S|=n {\rm \hskip2mm and \hskip2mm} S {\rm \hskip2mm has \hskip2mm distinct \hskip2mm subset \hskip2mm sums}\}.$$ Erdős conjectured $ f(n) \ge c2^{n}$ for some constant c. We give a construction that yields $f(n) < 0.22002 \cdot 2^{n}$ for n sufficiently large. This now stands as the best known upper bound on $ f(n).$

Full Text: PDF