Problem #865: There exists a constant $C>0$ such that, for all large $N$,...

---

Progress

A problem of Erdős and Sós (also earlier considered by Choi, Erdős, and Szemerédi [CES75], but Erdős had forgotten this). Taking all integers in $[N/8,N/4]$ and $[N/2,N]$ shows that $\frac{5}{8}$ would be best possible here.

It is a classical folklore fact that if $A\subseteq \{1,\ldots,2N\}$ has size $\geq N+2$ then there are distinct $a,b\in A$ such that $a+b\in A$, which establishes the $k=2$ case.

In general, one can define $f_k(N)$ to be minimal such that if $A\subseteq \{1,\ldots,N\}$ has size at least $f_k(N)$ then there are $k$ distinct $a_i\in A$ such that all $\binom{k}{2}$ pairwise sums are elements of $A$. Erdős and Sós conjectured that\[f_k(N)\sim \frac{1}{2}\left(1+\sum_{1\leq r\leq k-2}\frac{1}{4^r}\right) N,\]and a similar example shows that this would be best possible.

Choi, Erdős, and Szemerédi [CES75] have proved that, for all $k\geq 3$, there exists $\epsilon_k>0$ such that (for large enough $N$)\[f_k(N)\leq \left(\frac{2}{3}-\epsilon_k\right)N.\]