Problem Statement
Let $k\geq 3$ and $g_k(N)$ be minimal such that if $A\subseteq \{1,\ldots,2N\}$ has $\lvert A\rvert \geq N+g_k(N)$ then there exist integers $b_1,\ldots,b_k$ such that all $\binom{k}{2}$ pairwise sums are in $A$ (but the $b_i$ themselves need not be in $A$).
Estimate $g_k(N)$.
Estimate $g_k(N)$.
Categories:
Number Theory Additive Combinatorics
Progress
A problem of Choi, Erdős, and Szemerédi. It is clear that, for the set of odd numbers in $\{1,\ldots,2N\}$, no such $b_i$ exist, whence $g_k(N)\geq 0$ always. Choi, Erdős, and Szemerédi proved that $g_3(N)=2$ and $g_4(N) \ll 1$. van Doorn has shown that $g_4(N)\leq 2032$.Choi, Erdős, and Szemerédi also proved that\[g_5(N)\asymp \log N\]and\[g_6(N)\asymp N^{1/2}.\]In general they proved that\[g_k(N) \ll_k N^{1-2^{-k}}\]and for every $\epsilon>0$ if $k$ is sufficiently large then\[g_k(N) > N^{1-\epsilon}.\]As an example, taking $A$ to be the set of all odd integers and the powers of $2$ shows that $g_5(N)\gg \log N$.
Source: erdosproblems.com/866 | Last verified: January 19, 2026