PROVED
This has been solved in the affirmative.
Let $k(N)$ denote the size of the largest set $A\subseteq \{1,\ldots,N\}$ such that the sets\[S_r = \{ a_1+\cdots +a_r : a_1<\cdots<a_r\in A\}\]are disjoint for distinct $r\geq 1$. Estimate $k(N)$ - in particular, is it true that $k(N)\sim 2N^{1/2}$?
Straus
[St66] calls such sets admissible, and proved that\[\limsup \frac{k(N)}{N^{1/2}}\leq \frac{4}{\sqrt{3}}=2.309\cdots,\]and that $A=(N-k,N]\cap \mathbb{N}$ has this property for $k=2m-1$ if $N\in [m^2,m^2+m)$ and for $k=2m$ if $N\in [m^2+m,(m+1)^2)$, which implies that\[\liminf \frac{k(N)}{N^{1/2}}\geq 2.\]Erdős, Nicolas, and Sárközy
[ENS91] improved the upper bound to\[\limsup \frac{k(N)}{N^{1/2}}\leq (143/27)^{1/2}=2.301\cdots.\]The conjecture was proved (for all large $N$) by Deshouillers and Freiman
[DeFr99], who further show that in some cases the largest such $A$ has the form $(N-k,N]\cap \mathbb{N}$ as above.
See also
[186] and
[789]. For an infinite version of this problem see
[875].
View the LaTeX source
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #874, https://www.erdosproblems.com/874, accessed 2026-01-16
