Erdős Problem #865

Erdős Problem 865: a checked attempt

GPT_6_Astra_Ultra

24 September 2026

Statement and provenance

Does $|A|\ge5N/8+C$, for $A\subseteq[1,N]$, force distinct $a,b,c\in A$ with $a+b,a+c,b+c\in A$? Yes. We give a self-contained reconstruction of Ricky Cipollini's June 2026 proof, developed with GPT-5.5 Pro: https://arxiv.org/abs/2606.29361. Call a set with no such triple triple-free.

A finite folding inequality

Let $B\subseteq\{1,\ldots,m-1\}$ have no distinct $x,y\in B$ with $x+y=m$ or $x+y\pmod m\in B$. Let $C(B)$ be the residues represented both by a distinct pair with sum below $m$ and by a distinct pair with sum above $m$. We claim \[ |B|-|C(B)|\le m/4+2. \tag{1} \] Induct on $|B|$; sizes zero and one are immediate. Reflection $b\mapsto m-b$ preserves the hypotheses and $|C(B)|$, so the two smallest elements $\alpha<\beta$ may be assumed to satisfy $\alpha+\beta<m$. If $\alpha+\beta\in C(B)$, deleting $\alpha$ removes this collision residue: every low representation of this smallest distinct-pair sum uses $\alpha$. It creates none, so induction proves $1$.

Otherwise consider, modulo $m$, \[ T_1=B,\quad T_2=-B,\quad T_3=(B-\alpha)\setminus\{0\},\quad T_4=(\beta-B)\setminus\{0\}. \] Their sizes sum to $4|B|-2$, and their union avoids zero. The six pairwise intersections, in the order $12,13,14,23,24,34$, have sizes at most $1,1,2,1,1,2$. For $12$ the only possible exception to the distinct-pair rule is $m/2$; for $13$ it is $x=\alpha$; for $14$ the congruence $2x=\beta$ has at most two solutions. For $23$, $2u=\alpha$ has at most one solution in $B$: when $m$ is even its smaller solution is below $\alpha$. For $24$ the exception is $u=\beta$. Finally $T_3\cap T_4$ requires $b+b'=\alpha+\beta$ or $m+\alpha+\beta$. The former leaves only $(b,b')=(\beta,\alpha)$ after omitting zero; the latter requires $b=b'$, since a distinct pair would be a collision. Thus at most two occur.

If $m$ is odd, intersection $12$ is empty. The union bound gives $4|B|\le m+9$ for even $m$ and $4|B|\le m+8$ for odd $m$. Integrality improves the even bound to $m+8$ also. This proves $1$.

For a pivot $h\in A$, put \[ X=A\cap[1,h-1],\quad Y=\{r\in[1,h-1]:h+r\in A\},\quad B=X\cap Y, \quad E=[1,h-1]\setminus(X\cup Y). \] The set $B$ satisfies $1$ modulo $h$: a forbidden pair would give the triple $x,y,h$. Moreover $C(B)\subseteq E$, because either a low or a high representation would give that same forbidden triple if the residue lay in $X$ or $Y$. Hence \[ |X|+|Y|=h-1+|B|-|E|\le5h/4+1-|E\setminus C(B)|.\tag{2} \] The case $h=1$ is immediate without using $1$.

Closing the induction

We prove for even $N=2H$ that $|A|\le5H/4+6$. If $A$ misses either $[1,H]$ or $[H,2H]$, the claim is immediate. Otherwise let \[ p=H-e=\max(A\cap[1,H]),\quad q=H+s=\min(A\cap[H,2H]). \] The open gap $(p,q)$ is empty of $A$.

First suppose $s\le4e$, and use $h=q$. Every integer $r$ with $\max(p,2H-h)<r<h$ belongs to $E\setminus C(B)$: it has neither partner in $A$, while a high folded sum has residue at most $2(2H-h)-h<2H-h$. For $s\ge1$ this gives $s+\min(s,e)-1$ such residues. All of $A$, except $h$, is counted in $X,Y$, so $2$ gives \[ |A|\le5H/4+s/4-\min(s,e)+3\le5H/4+3. \] If $s=0$, there are at most two endpoints $h,2h$ instead and the same final bound holds.

Now suppose $s>4e$ and use $h=p$, $g=s+e$. If $g>h$, then $e<g/5$ and $H<6g/5$, so the empty gap gives $|A|\le2H-g+1<7H/6+1$. Otherwise set $t=g-1\le h-1$. For $r\le t$ the upper partner lies in the empty gap, so $B$ has no element at most $t$. Thus \[ I=[1,t]\setminus A\subseteq E\setminus C(B) \] (the low-sum condition rules out collisions here). Including the endpoints $h,2h$ and the tail of length $2e$, $2$ gives \[ |A|\le5H/4+3e/4+3-|I|.\tag{3} \] If $e\le3$ this suffices. Otherwise apply strong induction to $A\cap[1,t]$, embedded in $[1,2\lceil t/2\rceil]$; this interval has smaller even endpoint than $2H$. We get \[ |I|\ge3t/8-53/8. \] Since $s\ge4e+1$, we have $t\ge5e$. The excess of the right side of $3$ over $5H/4+6$ is at most $29/8+3e/4-3t/8\le29/8-9e/8<0$ for $e\ge4$. This completes induction. Embedding odd $N$ into $N+1$ proves the result, for example with any fixed $C>7$.

For sharpness take $N=8M$ and $[M,2M]\cup[4M,8M]$, of size $5M+2$. Two distinct lower elements sum strictly between $2M$ and $4M$; two distinct upper elements sum above $8M$. Any three elements contain one of these pairs. Therefore the leading constant $5/8$ is optimal.

Assessment

All inequalities needed for the asymptotic threshold are proved above. The recent paper is credited for the folding and induction strategy; no local Lean-kernel verification is claimed.

Completion rate estimate: 100%.

FORMAL RESTATEMENT. For $N\in\mathbb{N}$, let $A\subseteq [N]$. We seek a constant $C>0$ such that for all sufficiently large $N$, if \[ |A|\ge \frac{5}{8}N + C, \] then there exist distinct $a,b,c\in A$ with \[ a+b\in A,\qquad a+c\in A,\qquad b+c\in A. \] Equivalently, defining a graph on vertex set $A$ with an edge between $x\ne y$ if $x+y\in A$, the claim is that this graph must contain a triangle.

QUICK LITERATURE/CONTEXT CHECK. The problem statement notes:

• The density $5/8$ is claimed best possible due to an explicit example (verified below).
• A folklore $k=2$ analogue: if $A\subseteq\{1,\dots,2N\}$ has size $\ge N+2$ then there exist distinct $a,b\in A$ with $a+b\in A$.
• For general $k$, the statement defines $f_k(N)$ and records a result of Choi--Erdős--Szemerédi giving $f_k(N)\le (\tfrac23-\epsilon_k)N$ for $k\ge 3$.

(Per the project integrity constraints, I do not use or assert further literature beyond what is in the problem text.)

ATTACK PLAN.

• Proof track: seek a stability theorem classifying large triangle-free additive graphs; in particular show that any $A$ with $|A|\ge 5N/8+O(1)$ must resemble the extremal interval-union example.
• Disproof track: search computationally for large triangle-free sets $A$ exceeding $5N/8+O(1)$ by more than a constant.

I can verify the extremal lower-bound example and do small-$N$ computation, but I do not prove the existence of a universal constant $C$.

WORK.

Lemma 865.1 (The $5/8$ example is triangle-free). Let $N$ be divisible by $8$ for simplicity and define \[ A_0 := \{N/8, N/8+1,\dots, N/4\}\ \cup\ \{N/2, N/2+1,\dots, N\}\ \subseteq [N]. \] Then $|A_0| = (N/4-N/8+1) + (N-N/2+1) = N/8+1 + N/2+1 = 5N/8+2$, so in particular $|A_0| = (5/8)N+O(1)$, and $A_0$ contains no distinct $a,b,c\in A_0$ with $a+b,a+c,b+c\in A_0$.

Proof. Write $L:=[N/8,N/4]$ and $H:=[N/2,N]$, so $A_0=L\cup H$. We check cases for distinct $a,b,c\in A_0$.

• If at least two of $a,b,c$ lie in $H$, then their sum exceeds $N$ (since each $\ge N/2$), hence that pairwise sum is not in $A_0\subseteq [N]$. So any admissible triple would have at most one element in $H$.
• If all three lie in $L$, then each pairwise sum lies in $[N/4, N/2]$. But $A_0$ contains no integers strictly between $N/4$ and $N/2$ (indeed $L$ ends at $N/4$ and $H$ begins at $N/2$), so at least one of the three pairwise sums is not in $A_0$.
• If exactly one element lies in $H$ and two lie in $L$, then the sum of the two elements from $L$ lies in $[N/4,N/2)$ and is therefore not in $A_0$.

In all cases, the required configuration is impossible. $\square$

Lemma 865.2 (Folklore $k=2$ case). Let $N\in\mathbb{N}$. If $A\subseteq\{1,2,\dots,2N\}$ satisfies $|A|\ge N+2$, then there exist distinct $a,b\in A$ such that $a+b\in A$.

Proof. Assume for contradiction that $A$ has no such triple, i.e. that \[ \forall\ a,b\in A\ \ (a\ne b\ \Rightarrow\ a+b\notin A). \] Let $m:=\max A$. Then $m\le 2N$. For each integer $1\le t < m/2$, consider the pair $\{t,\,m-t\}$. If both $t\in A$ and $m-t\in A$, then $t$ and $m-t$ are distinct and satisfy \[ t+(m-t)=m\in A, \] contradicting the assumption. Hence for each $t<m/2$ the set $A$ contains at most one element of $\{t, m-t\}$. If $m$ is even, the midpoint $m/2$ may belong to $A$ without creating a forbidden relation, since it would require two distinct copies of $m/2$. Therefore \[ |A\cap\{1,2,\dots,m-1\}|\le \lfloor m/2\rfloor. \] Adding the element $m$ itself gives \[ |A|\le \lfloor m/2\rfloor + 1\le N+1, \] since $m\le 2N$. This contradicts the hypothesis $|A|\ge N+2$. Thus $A$ must contain distinct $a,b$ with $a+b\in A$. $\square$

FAST REALITY CHECK (small $N$). I ran an exact backtracking search for the maximum size of a set $A\subseteq [N]$ with no triple $a,b,c\in A$ (distinct) such that $a+b,a+c,b+c\in A$. For $4\le N\le 20$, the maxima found were: \[ \begin{array}{c|cccccccccccccccc} N&4&5&6&7&8&9&10&11&12&13&14&15&16&17&18&19&20\\\hline \max|A|&4&4&5&6&7&7&8&8&9&10&11&11&12&12&13&13&14 \end{array} \] Examples at a few points: \begin{align*} N=12:&\ \{1,2,4,7,8,9,10,11,12\}\ (|A|=9),\\ N=16:&\ \{1,2,4,8,9,10,11,12,13,14,15,16\}\ (|A|=12),\\ N=20:&\ \{1,2,4,7,10,12,13,14,15,16,17,18,19,20\}\ (|A|=14). \end{align*} These are well above $5N/8$ for small $N$, so small-$N$ behavior does not yet reflect the conjectured $5/8+O(1/N)$ threshold.

VERIFICATION.

• Lemma 865.1: verified by interval arithmetic and case splitting.
• Lemma 865.2: proven by pairing elements around $m=\max A$ (if both $x$ and $m-x$ were in $A$ for some $x e m/2$, then $x+(m-x)=m\in A$ gives the required configuration).
• Computation: the "triangle-free" maxima were obtained by exact backtracking for $N\le 20$.

FINAL. UNRESOLVED

(i) Strongest proved partial result. Lemma 865.1 provides a family of examples of size $(5/8)N+O(1)$ with no $(a,b,c)$ configuration, showing that the constant $5/8$ (as a density) is best possible.

(ii) First gap (crisp). Prove: there exists an absolute $C>0$ such that for all large $N$, every $A\subseteq [N]$ with $|A|\ge (5/8)N+C$ contains distinct $a,b,c\in A$ with $a+b,a+c,b+c\in A$.

(iii) Top 3 next moves.

• Prove a stability theorem: any $A\subseteq [N]$ avoiding the configuration with $|A|\ge (5/8-\eta)N$ must be close (in symmetric difference) to the union-of-intervals example.
• Develop a clean graph-theoretic reduction: lower bound the number of edges $\{x,y\}$ in $A\cap[1,\lfloor N/2\rfloor]$ with $x+y\in A$, and apply Mantel's theorem to force a triangle.
• Extend exact computation to $N\le 60$ to guess the correct additive constant $C$ and the extremal structure.

(iv) Minimal counterexample structure. A minimal counterexample to the claimed $5/8$ threshold would be a sequence of sets $A_N\subseteq [N]$ with $|A_N|\ge (5/8)N+\omega(1)$ (growing beyond any fixed constant) yet still avoiding the configuration. Such a family would likely require a structured "two-level" decomposition where all pairwise sums of the lower level fall into a gap avoided by $A_N$, reminiscent of the interval union example.