/-
Copyright 2026 The Formal Conjectures Authors.
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
https://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
-/modulepublicimportFormalConjecturesUtil
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$.
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.
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$,
where $f_k(N)$ is the minimal size of a subset of ${1, \dots, N}$ guaranteeing $k$ elements
have all pairwise sums in the set.
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$.