Erdős Problem #864

Erdős Problem 864 --- collection record

PROVENANCE AND STATUS

Official problem: https://www.erdosproblems.com/864

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/864.tex.

REUSED SOURCE 1

Original attribution: gpt_pro_5.2. Original file: attacks/erdos/gpt_pro_5.2/864.tex.

FORMAL RESTATEMENT. Let $N\in\mathbb{N}$, and let $A\subseteq [N]:=\{1,2,\dots,N\}$. For each integer $n$ define \[ r_A(n):=\left|\{(a,b)\in A\times A: a\le b,\ a+b=n\}\right|. \] Assume there exists at most one integer $n_0$ such that $r_A(n_0)\ge 2$, and for all $n\ne n_0$ we have $r_A(n)\le 1$. Let \[ F(N):=\max\{|A|:A\subseteq [N]\text{ satisfies the above property}\}. \] The problem asks for estimates on $F(N)$ and in particular whether \[ F(N)\le (1+o(1))\frac{2}{\sqrt 3}\,N^{1/2}\qquad (N\to\infty) \] holds.

QUICK LITERATURE/CONTEXT CHECK. The problem statement itself records a lower-bound construction (Erdős--Freud) giving $F(N)\ge (1+o(1))\tfrac{2}{\sqrt 3}N^{1/2}$ via a Sidon set in $[1,N/3]$ and its reflection in $N$. No upper bound matching this constant is stated in the problem text. (Per the project integrity constraints, I do not use or assert any additional literature beyond what is stated in the problem file.)

ATTACK PLAN.

• Proof track: (i) verify the stated Sidon + reflection construction rigorously; (ii) obtain general upper bounds by counting distinct pair-sums; (iii) try to force "two-block" structure when $|A|$ is large.
• Disproof track: attempt explicit constructions exceeding $\tfrac{2}{\sqrt 3}\sqrt N$ asymptotically, guided by small-$N$ computer search.

I succeed only at (i) and at weak upper bounds; no matching $\tfrac{2}{\sqrt 3}$ upper bound is obtained.

WORK.

Lemma 864.1 (Sidon reflection gives a single exceptional sum). Fix $N$. Let $B\subseteq \{1,2,\dots,\lfloor N/3\rfloor\}$ be a Sidon set in the following ("sum") sense: for all $b_1\le b_2$ and $b_3\le b_4$ in $B$, if $b_1+b_2=b_3+b_4$ then $\{b_1,b_2\}=\{b_3,b_4\}$. Define \[ A:=B\ \cup\ \{N-b: b\in B\}\ \subseteq\ [N]. \] Then $A$ satisfies the property of Problem 864 with the unique possible exceptional sum equal to $N$.

Proof. Write $C:=\{N-b:b\in B\}$, so $A=B\cup C$ and $B\cap C=\varnothing$ because $B\subseteq[1,N/3]$ implies $C\subseteq[2N/3,N-1]$. Consider two representations \[ x=a_1+a_2=a_3+a_4\qquad (a_1\le a_2,\ a_3\le a_4,\ a_i\in A). \] We show that if $x\ne N$ then the representations coincide. There are three pair-types:

• $1$ $B+B$: both summands in $B$;
• $2$ $C+C$: both summands in $C$;
• $3$ $B+C$: one summand in $B$, the other in $C$.

We first record where these sums can lie.

• If $x\in B+B$, then $x\le 2\lfloor N/3\rfloor\le 2N/3$.
• If $x\in C+C$, then $x\ge 2\lceil 2N/3\rceil\ge 4N/3$.
• If $x\in B+C$, write $x=b+(N-b')=N+(b-b')$ for $b,b'\in B$. Then $|b-b'|\le \lfloor N/3\rfloor-1$, hence $x\in [N-(\lfloor N/3\rfloor-1),\ N+(\lfloor N/3\rfloor-1)]\subseteq [2N/3+1,\ 4N/3-1]$.

Therefore, the ranges of $B+B$, $B+C$ (excluding the endpoint $N$), and $C+C$ are pairwise disjoint. Consequently, if $x\ne N$ then both representations of $x$ must be of the same pair-type.

Case 1: $x\in B+B$. Then $a_1,a_2,a_3,a_4\in B$ and the Sidon property of $B$ implies $\{a_1,a_2\}=\{a_3,a_4\}$. Since we impose $a_1\le a_2$ and $a_3\le a_4$, the representation is unique.

Case 2: $x\in C+C$. Write $a_i=N-b_i$ with $b_i\in B$. Then \[ (N-b_1)+(N-b_2)=(N-b_3)+(N-b_4)\iff b_1+b_2=b_3+b_4. \] Again, the Sidon property of $B$ forces $\{b_1,b_2\}=\{b_3,b_4\}$, hence $\{a_1,a_2\}=\{a_3,a_4\}$.

Case 3: $x\in B+C$ and $x\ne N$. Write $a_1=b_1\in B$, $a_2=N-b_2\in C$ and similarly $a_3=b_3\in B$, $a_4=N-b_4\in C$. Then \[ b_1+(N-b_2)=b_3+(N-b_4)\iff b_1-b_2=b_3-b_4. \] Rearranging gives $b_1+b_4=b_3+b_2$. By the Sidon property of $B$ applied to the (unordered) sums, $\{b_1,b_4\}=\{b_3,b_2\}$. Since $x\ne N$, we have $b_1\ne b_2$ and $b_3\ne b_4$ (otherwise the sum would be $N$). Thus the only possibility is $b_1=b_3$ and $b_2=b_4$, so the $B+C$ representation is unique.

The only remaining collisions are at $x=N$, where every $b\in B$ contributes the representation $N=b+(N-b)$. Hence $A$ has at most one sum with multiple representations, namely $N$. $\square$

Lemma 864.2 (General upper bound $F(N)\le 2\sqrt N+O(1)$). For every $N$ and every admissible $A\subseteq [N]$, \[ |A|\le \frac{1+\sqrt{16N-15}}{2} \;<\; 2\sqrt N+1. \]

Proof. Let $k:=|A|$. Consider the multiset of unordered pairs with repetition \[ \mathcal{P}:=\{\{a,b\}: a,b\in A,\ a\le b\}. \] Then $|\mathcal{P}|=k(k+1)/2$. Each pair $\{a,b\}$ contributes the sum $a+b\in\{2,3,\dots,2N\}$. Let $n_0$ be the (possible) exceptional sum with $t:=r_A(n_0)\ge 2$ representations; for all other $n$, $r_A(n)\le 1$. Thus the number of distinct sums arising from $\mathcal{P}$ equals $|\mathcal{P}|-(t-1)$. Since there are only $2N-1$ possible sums in $[2,2N]$, \[ \frac{k(k+1)}{2}-(t-1)\le 2N-1. \] Also $t\le k$ because for fixed $n_0$, each $a\in A$ determines at most one $b=n_0-a\in A$ with $a\le b$. Therefore \[ \frac{k(k+1)}{2}-(k-1)\le 2N-1\quad\Longrightarrow\quad \frac{k(k-1)}{2}+1\le 2N-1. \] Equivalently $k(k-1)\le 4N-4$, i.e. $k^2-k-(4N-4)\le 0$, which solves to $k\le \frac{1+\sqrt{16N-15}}{2}$. $\square$

FAST REALITY CHECK (small $N$). I ran an exact backtracking search for $F(N)$ for $N\le 40$. The exact maxima found were \[ \begin{array}{c|cccc} N & 10 & 20 & 30 & 40\\\hline F(N) & 5 & 8 & 9 & 11 \end{array} \] One extremal example for each is: \begin{align*} N=10:&\ \{1,2,3,7,10\},\\ N=20:&\ \{1,2,4,8,13,17,19,20\},\\ N=30:&\ \{1,2,4,8,13,18,22,24,25\},\\ N=40:&\ \{1,3,4,9,13,20,27,31,36,37,39\}. \end{align*} In each case there is exactly one repeated sum.

VERIFICATION.

• Lemma 864.1: the only point where a collision could arise between different pair-types is overlap of the sum ranges; the interval check shows disjointness except at $N$.
• Lemma 864.2: the bound uses only (i) counting pairs, (ii) that all sums lie in $[2,2N]$, and (iii) $t\le k$.
• Computation: verified by exhaustive backtracking (exact) for $N\le 40$.

FINAL. UNRESOLVED

(i) Strongest proved partial result. There is an explicit construction (Lemma 864.1) showing $F(N)\ge 2|B|$ when $B$ is a Sidon set in $[1,\lfloor N/3\rfloor]$, and a universal upper bound (Lemma 864.2) giving $F(N)\le 2\sqrt N+1$.

(ii) First gap (crisp). Prove (or disprove) the asymptotic upper bound $F(N)\le (1+o(1))\tfrac{2}{\sqrt 3}\sqrt N$. Even a structural theorem forcing an extremal $A$ to be close to a "two-block reflection" configuration is missing.

(iii) Top 3 next moves.

• Prove a stability statement: if $|A|\ge (\tfrac{2}{\sqrt 3}-\eta)\sqrt N$ then (after an affine change/translation of the exceptional sum) most of $A$ lies in two intervals of length $\approx N/3$.
• Strengthen Lemma 864.2 by counting overlaps between $A+A$ coming from different regions of $A$ (e.g. a three-interval decomposition of $[1,N]$) to force $N/3$-type geometry.
• Extend exact/heuristic computation to larger $N$ (e.g. $N\le 500$) to see whether $F(N)/\sqrt N$ appears to approach $2/\sqrt 3$ or a larger constant.

(iv) Minimal counterexample structure. If the conjectured constant $2/\sqrt 3$ is false, one expects a family of sets $A_N$ with $|A_N|\ge (\tfrac{2}{\sqrt 3}+\delta)\sqrt N$ and exactly one heavily-colliding sum; such a counterexample would likely require using more than two "blocks" or a non-reflection geometry so that cross-sums avoid colliding despite overlapping sum ranges.

COMPLETION ESTIMATE

The primary source supplies no extractable numerical completion estimate. Its mathematical progress is not numerically assessed here.

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. Let $N\in\mathbb{N}$, and let $A\subseteq [N]:=\{1,2,\dots,N\}$. For each integer $n$ define \[ r_A(n):=\left|\{(a,b)\in A\times A: a\le b,\ a+b=n\}\right|. \] Assume there exists at most one integer $n_0$ such that $r_A(n_0)\ge 2$, and for all $n\ne n_0$ we have $r_A(n)\le 1$. Let \[ F(N):=\max\{|A|:A\subseteq [N]\text{ satisfies the above property}\}. \] The problem asks for estimates on $F(N)$ and in particular whether \[ F(N)\le (1+o(1))\frac{2}{\sqrt 3}\,N^{1/2}\qquad (N\to\infty) \] holds.

QUICK LITERATURE/CONTEXT CHECK. The problem statement itself records a lower-bound construction (Erdős--Freud) giving $F(N)\ge (1+o(1))\tfrac{2}{\sqrt 3}N^{1/2}$ via a Sidon set in $[1,N/3]$ and its reflection in $N$. No upper bound matching this constant is stated in the problem text. (Per the project integrity constraints, I do not use or assert any additional literature beyond what is stated in the problem file.)

ATTACK PLAN.

• Proof track: (i) verify the stated Sidon + reflection construction rigorously; (ii) obtain general upper bounds by counting distinct pair-sums; (iii) try to force "two-block" structure when $|A|$ is large.
• Disproof track: attempt explicit constructions exceeding $\tfrac{2}{\sqrt 3}\sqrt N$ asymptotically, guided by small-$N$ computer search.

I succeed only at (i) and at weak upper bounds; no matching $\tfrac{2}{\sqrt 3}$ upper bound is obtained.

WORK.

Lemma 864.1 (Sidon reflection gives a single exceptional sum). Fix $N$. Let $B\subseteq \{1,2,\dots,\lfloor N/3\rfloor\}$ be a Sidon set in the following ("sum") sense: for all $b_1\le b_2$ and $b_3\le b_4$ in $B$, if $b_1+b_2=b_3+b_4$ then $\{b_1,b_2\}=\{b_3,b_4\}$. Define \[ A:=B\ \cup\ \{N-b: b\in B\}\ \subseteq\ [N]. \] Then $A$ satisfies the property of Problem 864 with the unique possible exceptional sum equal to $N$.

Proof. Write $C:=\{N-b:b\in B\}$, so $A=B\cup C$ and $B\cap C=\varnothing$ because $B\subseteq[1,N/3]$ implies $C\subseteq[2N/3,N-1]$. Consider two representations \[ x=a_1+a_2=a_3+a_4\qquad (a_1\le a_2,\ a_3\le a_4,\ a_i\in A). \] We show that if $x\ne N$ then the representations coincide. There are three pair-types:

• $1$ $B+B$: both summands in $B$;
• $2$ $C+C$: both summands in $C$;
• $3$ $B+C$: one summand in $B$, the other in $C$.

We first record where these sums can lie.

• If $x\in B+B$, then $x\le 2\lfloor N/3\rfloor\le 2N/3$.
• If $x\in C+C$, then $x\ge 2\lceil 2N/3\rceil\ge 4N/3$.
• If $x\in B+C$, write $x=b+(N-b')=N+(b-b')$ for $b,b'\in B$. Then $|b-b'|\le \lfloor N/3\rfloor-1$, hence $x\in [N-(\lfloor N/3\rfloor-1),\ N+(\lfloor N/3\rfloor-1)]\subseteq [2N/3+1,\ 4N/3-1]$.

Therefore, the ranges of $B+B$, $B+C$ (excluding the endpoint $N$), and $C+C$ are pairwise disjoint. Consequently, if $x\ne N$ then both representations of $x$ must be of the same pair-type.

Case 1: $x\in B+B$. Then $a_1,a_2,a_3,a_4\in B$ and the Sidon property of $B$ implies $\{a_1,a_2\}=\{a_3,a_4\}$. Since we impose $a_1\le a_2$ and $a_3\le a_4$, the representation is unique.

Case 2: $x\in C+C$. Write $a_i=N-b_i$ with $b_i\in B$. Then \[ (N-b_1)+(N-b_2)=(N-b_3)+(N-b_4)\iff b_1+b_2=b_3+b_4. \] Again, the Sidon property of $B$ forces $\{b_1,b_2\}=\{b_3,b_4\}$, hence $\{a_1,a_2\}=\{a_3,a_4\}$.

Case 3: $x\in B+C$ and $x\ne N$. Write $a_1=b_1\in B$, $a_2=N-b_2\in C$ and similarly $a_3=b_3\in B$, $a_4=N-b_4\in C$. Then \[ b_1+(N-b_2)=b_3+(N-b_4)\iff b_1-b_2=b_3-b_4. \] Rearranging gives $b_1+b_4=b_3+b_2$. By the Sidon property of $B$ applied to the (unordered) sums, $\{b_1,b_4\}=\{b_3,b_2\}$. Since $x\ne N$, we have $b_1\ne b_2$ and $b_3\ne b_4$ (otherwise the sum would be $N$). Thus the only possibility is $b_1=b_3$ and $b_2=b_4$, so the $B+C$ representation is unique.

The only remaining collisions are at $x=N$, where every $b\in B$ contributes the representation $N=b+(N-b)$. Hence $A$ has at most one sum with multiple representations, namely $N$. $\square$

Lemma 864.2 (General upper bound $F(N)\le 2\sqrt N+O(1)$). For every $N$ and every admissible $A\subseteq [N]$, \[ |A|\le \frac{1+\sqrt{16N-15}}{2} \;<\; 2\sqrt N+1. \]

Proof. Let $k:=|A|$. Consider the multiset of unordered pairs with repetition \[ \mathcal{P}:=\{\{a,b\}: a,b\in A,\ a\le b\}. \] Then $|\mathcal{P}|=k(k+1)/2$. Each pair $\{a,b\}$ contributes the sum $a+b\in\{2,3,\dots,2N\}$. Let $n_0$ be the (possible) exceptional sum with $t:=r_A(n_0)\ge 2$ representations; for all other $n$, $r_A(n)\le 1$. Thus the number of distinct sums arising from $\mathcal{P}$ equals $|\mathcal{P}|-(t-1)$. Since there are only $2N-1$ possible sums in $[2,2N]$, \[ \frac{k(k+1)}{2}-(t-1)\le 2N-1. \] Also $t\le k$ because for fixed $n_0$, each $a\in A$ determines at most one $b=n_0-a\in A$ with $a\le b$. Therefore \[ \frac{k(k+1)}{2}-(k-1)\le 2N-1\quad\Longrightarrow\quad \frac{k(k-1)}{2}+1\le 2N-1. \] Equivalently $k(k-1)\le 4N-4$, i.e. $k^2-k-(4N-4)\le 0$, which solves to $k\le \frac{1+\sqrt{16N-15}}{2}$. $\square$

FAST REALITY CHECK (small $N$). I ran an exact backtracking search for $F(N)$ for $N\le 40$. The exact maxima found were \[ \begin{array}{c|cccc} N & 10 & 20 & 30 & 40\\\hline F(N) & 5 & 8 & 9 & 11 \end{array} \] One extremal example for each is: \begin{align*} N=10:&\ \{1,2,3,7,10\},\\ N=20:&\ \{1,2,4,8,13,17,19,20\},\\ N=30:&\ \{1,2,4,8,13,18,22,24,25\},\\ N=40:&\ \{1,3,4,9,13,20,27,31,36,37,39\}. \end{align*} In each case there is exactly one repeated sum.

VERIFICATION.

• Lemma 864.1: the only point where a collision could arise between different pair-types is overlap of the sum ranges; the interval check shows disjointness except at $N$.
• Lemma 864.2: the bound uses only (i) counting pairs, (ii) that all sums lie in $[2,2N]$, and (iii) $t\le k$.
• Computation: verified by exhaustive backtracking (exact) for $N\le 40$.

FINAL. UNRESOLVED

(i) Strongest proved partial result. There is an explicit construction (Lemma 864.1) showing $F(N)\ge 2|B|$ when $B$ is a Sidon set in $[1,\lfloor N/3\rfloor]$, and a universal upper bound (Lemma 864.2) giving $F(N)\le 2\sqrt N+1$.

(ii) First gap (crisp). Prove (or disprove) the asymptotic upper bound $F(N)\le (1+o(1))\tfrac{2}{\sqrt 3}\sqrt N$. Even a structural theorem forcing an extremal $A$ to be close to a "two-block reflection" configuration is missing.

(iii) Top 3 next moves.

• Prove a stability statement: if $|A|\ge (\tfrac{2}{\sqrt 3}-\eta)\sqrt N$ then (after an affine change/translation of the exceptional sum) most of $A$ lies in two intervals of length $\approx N/3$.
• Strengthen Lemma 864.2 by counting overlaps between $A+A$ coming from different regions of $A$ (e.g. a three-interval decomposition of $[1,N]$) to force $N/3$-type geometry.
• Extend exact/heuristic computation to larger $N$ (e.g. $N\le 500$) to see whether $F(N)/\sqrt N$ appears to approach $2/\sqrt 3$ or a larger constant.

(iv) Minimal counterexample structure. If the conjectured constant $2/\sqrt 3$ is false, one expects a family of sets $A_N$ with $|A_N|\ge (\tfrac{2}{\sqrt 3}+\delta)\sqrt N$ and exactly one heavily-colliding sum; such a counterexample would likely require using more than two "blocks" or a non-reflection geometry so that cross-sums avoid colliding despite overlapping sum ranges.