Logo
All Random Solved Random Open
OPEN
Let $A\subseteq \mathbb{N}$ be a finite set of size $N$. Is it true that, for any fixed $t$, there are \[\ll \frac{2^N}{N^{3/2}}\] many $S\subseteq A$ such that $\sum_{n\in S}n=t$?

If we further ask that $\lvert S\rvert=l$ (for any fixed $l$) then is the number of solutions \[\ll \frac{2^N}{N^2},\] with the implied constant independent of $l$ and $t$?

Erdős and Moser proved the first bound with an additional factor of $(\log n)^{3/2}$. This was removed by Sárközy and Szemerédi [SaSz65], thereby answering the first question in the affirmative. Stanley [St80] has shown that this quantity is maximised when $A$ is an arithmetic progression and $t=\tfrac{1}{2}\sum_{n\in A}n$.
Additional thanks to: Zachary Chase