Open
Posted online: 2024-03-22 16:13:14Z by Stefan Steinerberger67
Cite as: P-240322.2
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?
No solutions added yet
Created at: 2024-03-22 16:13:14Z
No remarks yet