Erdős Problem #865

There exists a constant \(C>0\) such that, for all large \(N\), if \(A\subseteq \{1,\ldots,N\}\) has size at least \(\frac{5}{8}N+C\) then there are distinct \(a,b,c\in A\) such that \(a+b,a+c,b+c\in A\). 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). This problem was solved in the affirmative by Cipollini and GPT Pro [Ci26]. This is true. The linked proof gives it in the contrapositive and with the constant cleared: every triple-free \(A\subseteq\{1,\ldots,N\}\) satisfies \(8\lvert A\rvert\leq 5N+C\) for a fixed \(C\), for every \(N\) rather than only for large \(N\). It also shows the threshold is sharp, by exhibiting triple-free sets of size \((5N+16)/8\) for every \(N\) divisible by \(8\).