How many sums in $[1,N]$ can a set of $\lfloor N^{1/2}\rfloor$ integers produce? Estimate $f(N)$ (Erdős #819)
Statement
Let $f(N)$ be maximal such that there exists $A\subseteq \{1,\ldots,N\}$ with $\lvert A\rvert=\lfloor N^{1/2}\rfloor$ such that $\lvert (A+A)\cap [1,N]\rvert=f(N)$. (Here $A+A=\{a+b: a,b\in A\}$; one counts only the distinct pairwise sums that land back in $[1,N]$.) Estimate $f(N)$.
Acceptance. FULLY RESOLVES: determine the asymptotic constant — a proof that $f(N)=(c+o(1))N$ for an explicit constant $c$, comprising both a construction achieving $c$ and a matching upper-bound proof. Machine-checkable (Lean/Coq) proof preferred; otherwise a complete written proof with all steps. ADVANCES: (a) an explicit family of sets improving the lower-bound constant strictly beyond the best lower bound stated in the background, with proof (finite-$N$ certificates plus a rigorous asymptotic argument); (b) an upper bound with constant strictly below the best upper bound stated in the background, with full proof; (c) exact values of $f(N)$ for a range of small $N$ via reproducible ILP/exhaustive search with optimality certificates, plus witness sets and an empirical estimate of the constant. Deliver the proof file, or the construction + verification, or the search code + table of exact values and witnesses.
Background
A problem of Erdős and Freud, appearing in [Er91]; listed as open on erdosproblems.com/819 (fetched 2026-07-13, status 'open', tagged 'additive combinatorics'). A set of size $\lfloor N^{1/2}\rfloor$ has at most $\binom{\lvert A\rvert+1}{2}\approx N/2$ pairwise sums, so trivially $f(N)\leq (1/2+o(1))N$; a Sidon set attains $\sim N/2$ distinct sums, but those sums spread over $[1,2N]$ and the problem charges only the ones inside $[1,N]$. Erdős and Freud [ErFr91] proved $$\left(\frac{3}{8}-o(1)\right)N \leq f(N) \leq \left(\frac{1}{2}+o(1)\right)N,$$ and the true constant is unknown. They note the problem is closely connected to the size of the largest quasi-Sidon set, which is Erdős #840 (erdosproblems.com/840). As of the fetch date the site flags comment activity claiming partial results that has not yet been incorporated into the page remarks (forum thread at erdosproblems.com/forum/thread/819) — a solver should check that thread first. The attacker's tools: search-guided constructions (ILP / simulated annealing over $\lfloor\sqrt{N}\rfloor$-subsets at concrete $N$) to estimate the true constant and suggest asymptotic families, exact computation of $f(N)$ for small $N$ with optimality certificates, and refinement of the Erdős–Freud construction on the analytic side.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #819 (T. F. Bloom) | website |
| REF-02 | Erdős Problem #840 — quasi-Sidon sets (closely related) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.