Erdős Problem #866

Erdős Problem 866 --- collection record

PROVENANCE AND STATUS

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/866.tex.

REUSED SOURCE 1

FORMAL RESTATEMENT. Fix an integer $k\ge 3$. For $N\in\mathbb{N}$ define $g_k(N)$ to be the least integer $g\ge 0$ such that: for every set $A\subseteq [2N]:=\{1,2,\dots,2N\}$ with \[ |A|\ge N+g, \] there exist distinct positive integers $b_1,\dots,b_k$ such that for every $1\le i<j\le k$ the pairwise sum $b_i+b_j$ lies in $A$. (Ambiguity note. The problem text says "integers $b_i$" without stating distinctness/positivity. If the $b_i$ could repeat, the problem becomes degenerate (one even sum in $A$ would allow taking all $b_i$ equal), contradicting the nontrivial values reported in the statement. Thus I adopt "distinct positive" as the minimal correction consistent with the rest of the text.)

The problem asks to estimate $g_k(N)$ as a function of $N$.

QUICK LITERATURE/CONTEXT CHECK. The problem statement itself records several results of Choi--Erdős--Szemerédi and later work, including: $g_3(N)=2$, $g_4(N)\ll 1$ (and an explicit bound $\le 2032$), $g_5(N)\asymp\log N$, $g_6(N)\asymp N^{1/2}$, and general upper/lower bounds in $k$. (Per the project integrity constraints, I do not use or assert further literature beyond what is in the problem text.)

ATTACK PLAN.

• For $k=3$, derive a concrete characterization in terms of triples in $A$ and check small $N$ computationally.
• For general $k$, I do not attempt to reproduce the deep bounds stated in the problem file; instead I record basic necessary conditions and sanity checks.

WORK.

Lemma 866.1 ($k=3$ reformulation via triangle inequalities). Let $A\subseteq[2N]$. There exist distinct positive integers $b_1,b_2,b_3$ with \[ b_1+b_2\in A,\quad b_1+b_3\in A,\quad b_2+b_3\in A \] if and only if there exist distinct $x,y,z\in A$ such that \[ x+y>z,\quad x+z>y,\quad y+z>x,\quad\text{and}\quad x+y+z\equiv 0\pmod 2. \]

Proof. ($\Rightarrow$) Let $x=b_1+b_2$, $y=b_1+b_3$, $z=b_2+b_3$. Then $x,y,z\in A$ and are distinct because if $x=y$ then $b_2=b_3$, etc. Also $x+y+z=2(b_1+b_2+b_3)$ is even. Finally, triangle inequalities hold because, e.g. $x+y=(b_1+b_2)+(b_1+b_3)=2b_1+b_2+b_3> b_2+b_3=z$ since $b_1>0$, and similarly for the others.

($\Leftarrow$) Given distinct $x,y,z\in A$ satisfying the parity and strict triangle inequalities, define \[ b_1:=\frac{x+y-z}{2},\qquad b_2:=\frac{x+z-y}{2},\qquad b_3:=\frac{y+z-x}{2}. \] Parity ensures each $b_i\in\mathbb{Z}$. The strict triangle inequalities ensure $b_i>0$. A direct calculation shows $b_1+b_2=x$, $b_1+b_3=y$, $b_2+b_3=z$, so all required pairwise sums lie in $A$. Distinctness of $x,y,z$ implies $b_1,b_2,b_3$ are distinct (e.g. $b_1=b_2\iff y=z$). $\square$

Lemma 866.2 (Lower bound $g_3(N)\ge 2$ for $N\ge 2$). For $N\ge 2$, let \[ A:=\{2\}\ \cup\ \{1,3,5,\dots,2N-1\}\ \subseteq [2N]. \] Then $|A|=N+1$ and $A$ contains no triple of distinct positive integers $b_1,b_2,b_3$ with all pairwise sums in $A$. In particular $g_3(N)\ge 2$.

Proof. Every sum of two distinct positive integers is at least $1+2=3$. In $A$, the only even element is $2$. By Lemma 866.1, any $(b_1,b_2,b_3)$ configuration would produce three distinct sums $x,y,z\in A$ with even total $x+y+z$. But among three distinct elements of $A$, at most one can be even, so $x+y+z$ would be even only if there are exactly two odd sums and one even sum. The only even sum available is $2$. However, $2$ cannot be expressed as a sum of two distinct positive integers. Therefore no such configuration exists. $\square$

FAST REALITY CHECK (small $N$, $k=3$). Using the characterization in Lemma 866.1, I exhaustively computed $g_3(N)$ for $2\le N\le 10$. The exact values found were: \[ \begin{array}{c|ccccccccc} N & 2&3&4&5&6&7&8&9&10\\\hline g_3(N) & 3&3&2&2&2&2&2&2&2 \end{array} \] So for $N\ge 4$ the computation is consistent with the statement $g_3(N)=2$.

VERIFICATION.

• Lemma 866.1: checked both directions algebraically; the triangle inequalities are exactly positivity of the reconstructed $b_i$.
• Lemma 866.2: the obstruction is that the only even sum present is $2$, which cannot be a sum of two distinct positive integers.
• Computation: brute force over all $A\subseteq[2N]$ for $N\le 10$.

FINAL. UNRESOLVED

(i) Strongest proved partial result. For $k=3$, Lemma 866.1 gives an exact reformulation in terms of finding an even-perimeter triangle $(x,y,z)$ inside $A$; Lemma 866.2 gives a sharp lower bound $g_3(N)\ge 2$ for $N\ge 2$. Computation shows $g_3(N)=2$ for $4\le N\le 10$.

(ii) First gap (crisp). For general $k\ge 4$, I do not prove any nontrivial asymptotic upper bound on $g_k(N)$ beyond the trivial $g_k(N)\ge 0$. Even for $k=3$, I do not provide a complete gap-free proof that every $A\subseteq[2N]$ with $|A|\ge N+2$ contains an even-perimeter triangle triple for all large $N$.

(iii) Top 3 next moves.

• Prove the $k=3$ upper bound $g_3(N)\le 2$ for all $N\ge 4$ by a direct combinatorial argument on dense subsets of $[2N]$ guaranteeing an even-perimeter triangle.
• Generalize Lemma 866.1 to $k=4$ by characterizing 6 pairwise sums as an "additive $K_4$" and derive finite forbidden-configuration conditions.
• Use computer search for small $N$ to guess the true constant value of $g_4(N)$ and identify extremal constructions.

(iv) Minimal counterexample structure. A minimal counterexample for fixed $k$ would be a set $A\subseteq[2N]$ with $|A|=N+g_k(N)-1$ that avoids all $k$-cliques of pairwise sums; for $k=3$ this means avoiding all triples $x<y<z$ with $x+y>z$ and even total sum. Such an extremal $A$ would likely concentrate on one parity class together with a carefully chosen sparse subset of the other parity (as in Lemma 866.2).

COMPLETION ESTIMATE

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.

FORMAL RESTATEMENT. Fix an integer $k\ge 3$. For $N\in\mathbb{N}$ define $g_k(N)$ to be the least integer $g\ge 0$ such that: for every set $A\subseteq [2N]:=\{1,2,\dots,2N\}$ with \[ |A|\ge N+g, \] there exist distinct positive integers $b_1,\dots,b_k$ such that for every $1\le i<j\le k$ the pairwise sum $b_i+b_j$ lies in $A$. (Ambiguity note. The problem text says "integers $b_i$" without stating distinctness/positivity. If the $b_i$ could repeat, the problem becomes degenerate (one even sum in $A$ would allow taking all $b_i$ equal), contradicting the nontrivial values reported in the statement. Thus I adopt "distinct positive" as the minimal correction consistent with the rest of the text.)

The problem asks to estimate $g_k(N)$ as a function of $N$.

QUICK LITERATURE/CONTEXT CHECK. The problem statement itself records several results of Choi--Erdős--Szemerédi and later work, including: $g_3(N)=2$, $g_4(N)\ll 1$ (and an explicit bound $\le 2032$), $g_5(N)\asymp\log N$, $g_6(N)\asymp N^{1/2}$, and general upper/lower bounds in $k$. (Per the project integrity constraints, I do not use or assert further literature beyond what is in the problem text.)

ATTACK PLAN.

• For $k=3$, derive a concrete characterization in terms of triples in $A$ and check small $N$ computationally.
• For general $k$, I do not attempt to reproduce the deep bounds stated in the problem file; instead I record basic necessary conditions and sanity checks.

WORK.

Lemma 866.1 ($k=3$ reformulation via triangle inequalities). Let $A\subseteq[2N]$. There exist distinct positive integers $b_1,b_2,b_3$ with \[ b_1+b_2\in A,\quad b_1+b_3\in A,\quad b_2+b_3\in A \] if and only if there exist distinct $x,y,z\in A$ such that \[ x+y>z,\quad x+z>y,\quad y+z>x,\quad\text{and}\quad x+y+z\equiv 0\pmod 2. \]

Proof. ($\Rightarrow$) Let $x=b_1+b_2$, $y=b_1+b_3$, $z=b_2+b_3$. Then $x,y,z\in A$ and are distinct because if $x=y$ then $b_2=b_3$, etc. Also $x+y+z=2(b_1+b_2+b_3)$ is even. Finally, triangle inequalities hold because, e.g. $x+y=(b_1+b_2)+(b_1+b_3)=2b_1+b_2+b_3> b_2+b_3=z$ since $b_1>0$, and similarly for the others.

($\Leftarrow$) Given distinct $x,y,z\in A$ satisfying the parity and strict triangle inequalities, define \[ b_1:=\frac{x+y-z}{2},\qquad b_2:=\frac{x+z-y}{2},\qquad b_3:=\frac{y+z-x}{2}. \] Parity ensures each $b_i\in\mathbb{Z}$. The strict triangle inequalities ensure $b_i>0$. A direct calculation shows $b_1+b_2=x$, $b_1+b_3=y$, $b_2+b_3=z$, so all required pairwise sums lie in $A$. Distinctness of $x,y,z$ implies $b_1,b_2,b_3$ are distinct (e.g. $b_1=b_2\iff y=z$). $\square$

Lemma 866.2 (Lower bound $g_3(N)\ge 2$ for $N\ge 2$). For $N\ge 2$, let \[ A:=\{2\}\ \cup\ \{1,3,5,\dots,2N-1\}\ \subseteq [2N]. \] Then $|A|=N+1$ and $A$ contains no triple of distinct positive integers $b_1,b_2,b_3$ with all pairwise sums in $A$. In particular $g_3(N)\ge 2$.

Proof. Every sum of two distinct positive integers is at least $1+2=3$. In $A$, the only even element is $2$. By Lemma 866.1, any $(b_1,b_2,b_3)$ configuration would produce three distinct sums $x,y,z\in A$ with even total $x+y+z$. But among three distinct elements of $A$, at most one can be even, so $x+y+z$ would be even only if there are exactly two odd sums and one even sum. The only even sum available is $2$. However, $2$ cannot be expressed as a sum of two distinct positive integers. Therefore no such configuration exists. $\square$

FAST REALITY CHECK (small $N$, $k=3$). Using the characterization in Lemma 866.1, I exhaustively computed $g_3(N)$ for $2\le N\le 10$. The exact values found were: \[ \begin{array}{c|ccccccccc} N & 2&3&4&5&6&7&8&9&10\\\hline g_3(N) & 3&3&2&2&2&2&2&2&2 \end{array} \] So for $N\ge 4$ the computation is consistent with the statement $g_3(N)=2$.

VERIFICATION.

• Lemma 866.1: checked both directions algebraically; the triangle inequalities are exactly positivity of the reconstructed $b_i$.
• Lemma 866.2: the obstruction is that the only even sum present is $2$, which cannot be a sum of two distinct positive integers.
• Computation: brute force over all $A\subseteq[2N]$ for $N\le 10$.

FINAL. UNRESOLVED

(i) Strongest proved partial result. For $k=3$, Lemma 866.1 gives an exact reformulation in terms of finding an even-perimeter triangle $(x,y,z)$ inside $A$; Lemma 866.2 gives a sharp lower bound $g_3(N)\ge 2$ for $N\ge 2$. Computation shows $g_3(N)=2$ for $4\le N\le 10$.

(ii) First gap (crisp). For general $k\ge 4$, I do not prove any nontrivial asymptotic upper bound on $g_k(N)$ beyond the trivial $g_k(N)\ge 0$. Even for $k=3$, I do not provide a complete gap-free proof that every $A\subseteq[2N]$ with $|A|\ge N+2$ contains an even-perimeter triangle triple for all large $N$.

(iii) Top 3 next moves.

• Prove the $k=3$ upper bound $g_3(N)\le 2$ for all $N\ge 4$ by a direct combinatorial argument on dense subsets of $[2N]$ guaranteeing an even-perimeter triangle.
• Generalize Lemma 866.1 to $k=4$ by characterizing 6 pairwise sums as an "additive $K_4$" and derive finite forbidden-configuration conditions.
• Use computer search for small $N$ to guess the true constant value of $g_4(N)$ and identify extremal constructions.

(iv) Minimal counterexample structure. A minimal counterexample for fixed $k$ would be a set $A\subseteq[2N]$ with $|A|=N+g_k(N)-1$ that avoids all $k$-cliques of pairwise sums; for $k=3$ this means avoiding all triples $x<y<z$ with $x+y>z$ and even total sum. Such an extremal $A$ would likely concentrate on one parity class together with a carefully chosen sparse subset of the other parity (as in Lemma 866.2).