Problem 865

Erdős Problem #865: declared status 'open'. Formalized: yes. 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$. Current best: Erd\H{o}s and S\'{o}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\H{o}s, and Szemer\'{e}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.$$ References [CES75] Choi, S. Prize: no. Tags: additive combinatorics, number theory.