Problem Statement
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$?
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$?
Categories:
Number Theory
Progress
Erdős and Moser [Er65] 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=\{-\lfloor \frac{N-1}{2}\rfloor,\ldots,\lfloor\frac{N}{2}\rfloor\}$.The second question was answered in the affirmative by Halász [Ha77], as a consequence of a more general multi-dimensional result.
Source: erdosproblems.com/362 | Last verified: January 14, 2026