A sharp 5 / 8 5/8 bound for an Erdős–Sós pairwise-sums problem
Ricky Cipollini · 2026
Read A sharp 5 / 8 5/8 bound for an Erdős–Sós pairwise-sums problem by Ricky Cipollini (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-29361.txt.
Introduction
Cipollini settles a problem posed by Erdős about sums inside large sets of whole numbers. Take a set of integers drawn from one up to N. How large must the set be before it must contain three distinct elements whose three pairwise sums also lie in the set? The threshold function for this question was known only within a range.
He proves the threshold is at most five eighths of N, up to a bounded error. A standard construction shows that five eighths is also necessary, so the value is pinned down exactly apart from the small error term. That resolves Erdős Problem 865. His proof is self-contained. A conditional version of the reduction, developed earlier, was also formalised in the Lean proof assistant, with no gaps and no added axioms. The manuscript's note credits the proof's development jointly to Cipollini and an AI system.
Catalog record
| CREATOR | Ricky Cipollini |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 14 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.29361
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A sharp 5 / 8 5/8 bound for an Erdős–Sós pairwise-sums problem Thanks: This manuscript was written by GPT-5.5 Pro from a proof developed by Ricky Cipollini together with GPT-5.5 Pro. The associated Lean formalization was carried out with Aristotle. Ricky Cipollini Abstract . Let f 3 ( N ) f_{3}(N) be the least integer such that every set A ⊆ { 1 , … , N } A\subseteq\{1,\ldots,N\} of size at least f 3 ( N ) f_{3}(N) contains distinct a , b , c ∈ A a,b,c\in A with a + b , a + c , b + c ∈ A . a+b,\quad a+c,\quad b+c\in A. We prove f 3 ( N ) ≤ 5 8 N + O ( 1 ) . f_{3}(N)\leq\frac{5}{8}N+O(1). Together with the standard construction [ N / 8 , N / 4 ] ∪ [ N / 2 , N ] [N/8,N/4]\cup[N/2,N] , this gives f 3 ( N ) = 5 N / 8 + O ( 1 ) f_{3}(N)=5N/8+O(1) and in particular resolves Erdős Problem 865. The proof is self-contained. An earlier conditional version of the reduction has also been formalized in Lean 4/Mathlib with no sorries and no added axioms. 1. Introduction For a positive integer N , let [1,N] denote the set of integers \{1,\ldots,N\} . We say that A\subseteq[1,N] contains a pairwise-sum triple if there are distinct a,b,c\in A such that a+b,\quad a+c,\quad b+c\in A. Let f_{3}(N) be the least integer such that every A\subseteq[1,N] with |A|\geq f_{3}(N) contains such a triple. The problem considered here is the k=3 case of an Erdős–Sós conjecture on pairwise sums. The example A=\left[\frac{N}{8},\frac{N}{4}\right]\cup\left[\frac{N}{2},N\right] shows that the constant 5/8 is best possible up to lower-order terms. The goal is to prove the matching upper bound. The proof is self-contained. We prove the following theorem. Theorem 1.1 . There is a constant C>0 such that for all N , every A\subseteq[1,N] with |A|\geq\frac{5}{8}N+C contains a pairwise-sum triple. Equivalently, every pairwise-sum-triple-free set A\subseteq[1,N] satisfies |A|\leq\frac{5}{8}N+O(1). All implicit constants in the proof are absolute. Remark 1.2 (Formalization) . An earlier version of the reduction from a coarse 2/3 theorem to Theorem 1.1 has been formalized in Lean 4/Mathlib with no sorries and no added axioms. The formalization proves a slightly weaker version of the folded additive lemma, the folding reduction, the centering argument, and the sharpness construction. It is currently outdated for the present version of the paper, since Lemma 2.1 has been sharpened and Section 4 below replaces the coarse theorem by an induction argument. 2. The folded additive lemma We first prove a finite additive lemma on a folded interval. Let m\geq 2 and let B\subseteq\{1,\ldots,m-1\}. Assume that for all distinct x,y\in B , (1) x+y\neq m,\qquad x+y\notin B\pmod{m}. Define S_{0}(B)=\{x+y:x\neq y,\ x,y\in B,\ x+y<m\}, S_{1}(B)=\{x+y-m:x\neq y,\ x,y\in B,\ x+y>m\}, and C(B)=S_{0}(B)\cap S_{1}(B). Thus C(B) is the set of residues which occur both as a non-wrapped and as a wrapped pair-sum of two distinct elements of B . Lemma 2.1 (Folded additive lemma) . For every m and B satisfying ( 1 ), |B|-|C(B)|\leq\frac{m}{4}+2. Proof. We induct on |B| . First observe the reflection symmetry. Put -B=\{m-b:b\in B\}\subseteq\{1,\ldots,m-1\}. Replacing B by -B preserves ( 1 ); low sums for B become high sums for -B , and high sums for B become low sums for -B . Hence (2) |C(-B)|=|C(B)|. Assume |B|\geq 2 . After replacing B by -B if necessary, we may suppose that the two smallest elements of B , \alpha<\beta, satisfy (3) \alpha+\beta<m. Indeed, if the two smallest elements of B have sum at least m , then the two largest elements v<u of B have u+v>m , since equality would give a forbidden sum equal to m . Reflecting sends them to the two smallest elements m-u<m-v of -B , whose sum is 2m-u-v<m . We now split into two cases. Case 1: \alpha+\beta\in C(B) . Let B^{\prime}=B\setminus\{\alpha\}. Since \alpha and \beta are the two smallest elements of B , every low representation of \alpha+\beta uses \alpha . Therefore, after deleting \alpha , the residue \alpha+\beta no longer lies in C(B^{\prime}) . Deleting elements cannot create new collisions, so |C(B^{\prime})|\leq|C(B)|-1. Consequently |B|-|C(B)|\leq|B^{\prime}|-|C(B^{\prime})|. The induction hypothesis applied to B^{\prime} gives the desired bound. Case 2: \alpha+\beta\notin C(B) . Work in the cyclic group \mathbb{Z}/m\mathbb{Z} . Consider the four sets T_{1}=B,\qquad T_{2}=-B,\qquad T_{3}=(B-\alpha)\setminus\{0\},\qquad T_{4}=(\beta-B)\setminus\{0\}, where these are viewed as subsets of \mathbb{Z}/m\mathbb{Z} . Their total size is (4) |T_{1}|+|T_{2}|+|T_{3}|+|T_{4}|=4|B|-2. We record the required intersection bounds. First, |T_{1}\cap T_{2}|\leq 1, and if m is odd then T_{1}\cap T_{2}=\varnothing , since an element in this intersection gives two elements of B whose sum is m , except possibly the single residue m/2 . Also |T_{1}\cap T_{3}|\leq 1, since x\in T_{1}\cap T_{3} gives x\in B and x\equiv b-\alpha for some b\in B , so \alpha+x\equiv b\pmod{m}; unless x=\alpha , this is a forbidden sum of two distinct elements of B landing back in B . Similarly, |T_{1}\cap T_{4}|\leq 2, since such an intersection gives x+b\equiv\beta\pmod{m} with x,b\in B ; unless x=b , this is forbidden, while x=b forces 2x\equiv\beta\pmod{m} , which has at most two solutions modulo m . Next, |T_{2}\cap T_{3}|\leq 1. Indeed, such an intersection gives u+b\equiv\alpha\pmod{m} with u,b\in B . Unless u=b , this is forbidden, so 2u\equiv\alpha\pmod{m} . This congruence has at most one solution in B : if m is odd there is only one residue solution, while if m is even then either there is no solution, or the two residue solutions are \alpha/2 and \alpha/2+m/2 ; the first is smaller than \alpha , so at most the second can lie in B . Finally, |T_{2}\cap T_{4}|\leq 1; indeed, such an intersection gives a congruence u+\beta\equiv b\pmod{m} with u,b\in B , which is forbidden unless u=\beta . It remains to bound T_{3}\cap T_{4} . Suppose b-\alpha\equiv\beta-b^{\prime}\pmod{m} with b,b^{\prime}\in B . Then b+b^{\prime}\equiv\alpha+\beta\pmod{m}. Since 0<\alpha+\beta<m , this means either b+b^{\prime}=\alpha+\beta or b+b^{\prime}=m+\alpha+\beta. The zero omissions in the definitions of T_{3} and T_{4} mean that b\neq\alpha and b^{\prime}\neq\beta . Thus in the first equality, since \alpha,\beta are the two smallest elements of B , the only possible ordered contribution is (b,b^{\prime})=(\beta,\alpha) . In the second equality, if b\neq b^{\prime} , then \alpha+\beta has both the low representation \alpha+\beta and the high representation b+b^{\prime}-m , contrary to \alpha+\beta\notin C(B) . If b=b^{\prime} , then 2b=m+\alpha+\beta , so there is at most one further possible residue. Hence |T_{3}\cap T_{4}|\leq 2. Thus the total pairwise overlap is at most 8 if m is even and at most 7 if m is odd. Also 0 lies in none of the sets T_{i} , so \left|\bigcup_{i=1}^{4}T_{i}\right|\leq m-1. By the elementary union bound in the form \sum_{i=1}^{4}|T_{i}|\leq\left|\bigcup_{i=1}^{4}T_{i}\right|+\sum_{1\leq i<j\leq 4}|T_{i}\cap T_{j}|, we get 4|B|-2\leq m+7 if m is even and 4|B|-2\leq m+6 if m is odd. Thus 4|B|\leq m+9 in the even case and 4|B|\leq m+8 in the odd case. Since 4|B| is divisible by 4 , the even case also gives 4|B|\leq m+8 . Hence in all cases |B|\leq\frac{m}{4}+2. Since |C(B)|\geq 0 , this proves |B|-|C(B)|\leq\frac{m}{4}+2. Together with the induction case, this proves the lemma. ∎ 3. Folding a triple-free set around a pivot Call a set