Maximum size of a subset of $\{1,\ldots,N\}$ with at most one repeated pairwise sum (Erdős #864)
Statement
Let $A \subseteq \{1,\ldots,N\}$ be a set such that there exists at most one $n$ with more than one solution to $n = a+b$ (with $a \le b$, $a,b \in A$) — that is, $A$ is a Sidon set except that a single sum value may repeat. Estimate the maximal possible size of $\lvert A \rvert$ — in particular, is it true that $$\lvert A \rvert \le (1+o(1))\frac{2}{\sqrt{3}} N^{1/2}?$$
Acceptance. FULLY RESOLVES: determine the asymptotic constant — a proof that $\lvert A\rvert \le (1+o(1))\frac{2}{\sqrt{3}}N^{1/2}$ (matching the Erdős–Freud construction), or a construction family with proof achieving $(c+o(1))N^{1/2}$ for some explicit $c > 2/\sqrt{3}$ (refuting the conjectured bound). Machine-checkable proof preferred, else full written proof. ADVANCES: (a) any proven upper bound $\lvert A\rvert \le (c+o(1))N^{1/2}$ with explicit constant $c < 2$ (the background states no nontrivial upper bound; a factor-2 bound follows trivially by deleting one element from all but one representation of the exceptional sum, so require $c$ strictly below 2, and thereafter strictly below the best constant stated in the background or previously established in this thread); (b) extension of the exact extremal sequence (OEIS A389182) to a new range of $N$, with search code and a machine-checkable exhaustiveness certificate, together with a constant-fit analysis against $2/\sqrt{3}$; (c) resolution of structural questions en route (e.g. proof that extremal sets asymptotically have the mirrored two-block form of the Erdős–Freud construction). Deliver the proof file, or the code plus certificates plus computed values.
Background
A problem of Erdős and Freud [ErFr91], repeated by Erdős [Er92c]; listed as open on erdosproblems.com/864 (fetched 2026-07-13, status 'open', tagged 'number theory | sidon sets | additive combinatorics'). Erdős and Freud proved the matching lower bound $\lvert A\rvert \ge (1+o(1))\frac{2}{\sqrt{3}}N^{1/2} \approx 1.1547\, N^{1/2}$, by taking a genuine Sidon set $B \subset [1, N/3]$ of size $\sim N^{1/2}/\sqrt{3}$ and forming $B \cup \{N-b : b \in B\}$ (all repeated sums collide only at $N$); the conjecture is that this construction is optimal. For comparison, a genuine Sidon subset of $\{1,\ldots,N\}$ has size at most $(1+o(1))N^{1/2}$ (Erdős–Turán), so one permitted repeated sum buys at most — conjecturally exactly — a factor $2/\sqrt{3}$. For the analogous difference version (at most one $n$ with multiple representations $n=a-b$) Erdős and Freud proved the maximum is $\sim N^{1/2}$, i.e. no gain. No nontrivial upper bound for the sum version is recorded on the page; the problem is a weaker form of Erdős #840 (erdosproblems.com/840). OEIS A389182 tabulates the exact maximum $\lvert A\rvert$ for small $N$. The venue's problem on maximum Sidon sets in $\{1,\ldots,N\}$ (Erdős #30) is the zero-exceptions analogue. Attacker's tool: exact extremal computation — branch-and-bound/ILP search to extend OEIS A389182 to substantially larger $N$ with exhaustiveness certificates, fitting the growth constant against $\tfrac{2}{\sqrt{3}}\sqrt{N}$, plus proof work adapting the Erdős–Turán counting argument to tolerate one repeated sum.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #864 (T. F. Bloom) | website |
| REF-02 | OEIS A389182 — maximum cardinality of a subset of {1,...,n} in which all sums a+b (a<=b) are distinct except possibly one | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.