How few integers below N can fail to be a unique sum of two elements of A? (Erdős #14)
Statement
Let $A \subseteq \mathbb{N}$, and let $B \subseteq \mathbb{N}$ be the set of integers which are representable in exactly one way as the sum of two elements of $A$ (as an unordered pair, repeats allowed). Is it true that for all $\epsilon > 0$ and all large $N$ $$\lvert \{1,\ldots,N\} \setminus B \rvert \gg_\epsilon N^{1/2-\epsilon}?$$ Or is it possible that $$\lvert \{1,\ldots,N\} \setminus B \rvert = o(N^{1/2})?$$
Acceptance. FULLY RESOLVES: a proof that every $A \subseteq \mathbb{N}$ satisfies $\lvert \{1,\ldots,N\} \setminus B \rvert \gg_\epsilon N^{1/2-\epsilon}$ for all $\epsilon>0$ and large $N$; OR an explicit construction of $A$ together with a proof that $\lvert \{1,\ldots,N\} \setminus B \rvert = o(N^{1/2})$. Machine-checkable proof (Lean/Coq) preferred, else a full written proof. ADVANCES: (a) any nontrivial universal lower bound — a proof that every $A$ has $\lvert \{1,\ldots,N\} \setminus B \rvert \ge N^{\theta}$ for an explicit $\theta>0$ (for all large $N$, or for infinitely many $N$), since no universal lower bound is stated in the background; (b) resolution of the Erdős–Freud finite-analogue constant — an explicit construction with verification code beating the $2^{3/2}$ bound stated in the background, or a proof that $2^{3/2}$ is optimal; (c) exact extremal values of the finite analogue for an initial range of $N$ with exhaustive-search certificates (code plus a machine-checkable log establishing exhaustiveness). Deliver the proof file, or the constructions/values plus search code and certificates.
Background
Apparently first considered by Erdős and Nathanson, though Erdős later attributed it to Erdős, Sárközy and Szemerédi without giving a reference [Er92c, Er97, Er97e]; listed as open on erdosproblems.com/14 (fetched 2026-07-13, status 'open', tagged 'number theory | sidon sets | additive combinatorics'). Erdős claimed a construction of a set $A$ whose complement count satisfies $\lvert \{1,\ldots,N\} \setminus B \rvert \ll_\epsilon N^{1/2+\epsilon}$ for every $\epsilon>0$ and all large $N$, yet for every $\epsilon>0$ there are infinitely many $N$ with $\lvert \{1,\ldots,N\} \setminus B \rvert \gg_\epsilon N^{1/3-\epsilon}$ — so the known construction hugs the $N^{1/2}$ threshold from above while still showing $N^{1/3}$-size fluctuations, and the question is whether the $N^{1/2-\epsilon}$ floor is universal or can be beaten. In [ErFr91], Erdős and Freud studied the finite analogue: they produced $A \subseteq \{1,\ldots,N\}$ for which fewer than $2^{3/2} N^{1/2}$ integers fail to be representable in exactly one way as a sum of two elements of $A$, suggesting that the constant $2^{3/2}$ may be best possible. The site tentatively links OEIS A143824 (largest subset of $\{1,\ldots,n\}$ with all pairwise differences distinct) as possibly related. Related in spirit to the venue's Sidon-set problems (e.g. maximum Sidon sets in $\{1,\ldots,N\}$, Erdős #30), but the unique-representation complement question is distinct. Attacker's tool: exact computation of the finite-analogue extremum — for each small $N$, an exhaustive or ILP/branch-and-bound search for $A \subseteq \{1,\ldots,N\}$ minimizing the count of integers in $\{1,\ldots,N\}$ not represented exactly once — to test the $2^{3/2}$ constant and map the true growth.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #14 (T. F. Bloom) | website |
| REF-02 | OEIS A143824 — largest subset of {1,...,n} with all pairwise differences distinct (linked as possibly related) | website |
| REF-03 | Formalised statement (Lean, google-deepmind/formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.