Problem Statement
Let $h(n)$ be maximal such that if $A\subseteq \mathbb{Z}$ with $\lvert A\rvert=n$ then there is $B\subseteq A$ with $\lvert B\rvert \geq h(n)$ such that if $a_1+\cdots+a_r=b_1+\cdots+b_s$ with $a_i,b_i\in B$ then $r=s$.
Estimate $h(n)$.
Estimate $h(n)$.
Categories:
Additive Combinatorics
Progress
Erdős [Er62c] proved $h(n) \ll n^{5/6}$. Straus [St66] proved $h(n) \ll n^{1/2}$. Erdős noted the bound $h(n)\gg n^{1/3}$, taking\[B=\{ a: \{ \alpha a\} \in n^{-1/3}+\tfrac{1}{2} (-n^{-2/3},n^{-2/3})\}\]for a random $\alpha\in [0,1]$. [Er62c] and Choi [Ch74b] improved this to $h(n) \gg (n\log n)^{1/3}$.See also [186] and [874].
Source: erdosproblems.com/789 | Last verified: January 16, 2026