The Erdos Distinct Subset Sum Problem

Problem's Description

Let $a_1 \leq a_2 \leq \dots \leq a_n$ be a set of $n$ positive integers such that all $2^n$ subsets of the set are uniquely identified by the sum of their elements. An example of such a sequence are the powers of 2 (this is the uniqueness of the binary expansion in disguise). The question, due to Erdos in 1931 or 1932, is whether sets with such a property have to always have a large number.

Problem. Does this property force $a_n \geq c\cdot 2^n$?

We note that the largest sum is $a_1 + \dots + a_n$ and thus, if all the subsets are distinct, we have to have $$ 2^n \leq a_1 + \dots + a_n \leq n \cdot a_n$$ and thus $$ a_n \geq \frac{2^n}{n}.$$ The currently best result is due to Erdos-Moser $$ a_n \geq c \frac{2^n}{\sqrt{n}}.$$ Many people have worked on improving the constant $c$. Conway-Guy showed that the powers of 2 are not extremal: there are examples with smaller $a_n$. Elkies notes the equivalence to a completely analytic question: If $a_1, \dots, a_n$ are positive integers, then $$ \int_0^1 \prod_{i=1}^{n} \cos(2 \pi a_i x)^2 dx \geq \frac{1}{2^n}$$ with equality if and only if all subset sums are distinct. The question is thus: if the integral is small, does this force $a_n$ to be large?

1. Conference Paper Problems and results in additive number theory

   • Paul Erdos

   Colloque sur la Theorie des Nombres, Bruxelles, 1955

2. Article An improved lower bound on the greatest element of a sum-distinct set of fixed order.

   • Noam Elkies

   Journal of Combinatorial Theory, Series A, 89-94, 1986

3. Article Sets of natural numbers with distinct sums

   • J. Conway,
   • R. K. Guy

   Notices of the American Mathematical Society, 345, 1968