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?

Conference Paper
Problems and results in additive number theory

Notices of the American Mathematical Society, 345, 1968

No solutions added yet

No remarks yet

Created at: 2024-03-22 16:13:14Z

Follow the problem

Social share

Get email updates when

Advanced search

Single or several?

If you plan to formulate more than one problem all sharing the same background (e.g. they are all from the same paper) then please choose "Group", otherwise select "Single" option.

No remarks yet