Erdős Problem #863 — Let $r\geq 2$ and let $A\subseteq \{1,\ldots,N\}$ be a set of maximal size such that there are at most $r$ solutions to $n=a+b$ with $a\leq b$ for any $n$.

Erdős formulated the question in conversation with Berend and later reformulated it independently with Freud. It asks whether the asymptotic constant for maximal sets with bounded difference representations is smaller than the corresponding sum-representation constant.

Known results

• The case $r=1$ is settled: $c_1=c'_1=1$.
• Cilleruelo, Ruzsa, and Trujillo (2002) supplied the construction giving $c_r\geq (r+\lfloor r/2\rfloor)/\sqrt{r+2\lfloor r/2\rfloor}$.
• An adaptation of the Erdős–Turán bound gives $c'_r\leq\sqrt r$.
• Consequently, $c'_r< c_r$ for every $r\geq 2$; for $r=2$, $c'_2\leq\sqrt2<3/2\leq c_2$.

GPT-5.4 Pro observation

Boon Suan Ho and GPT-5.4 Pro observed that the positive answer follows from the existing estimates and the 2002 construction. A purported self-contained write-up is available, but no independently published or peer-reviewed proof was found; the claim therefore remains unverified.

Current status (as of June 2026): The inequality $c'_r<c_r$ for $r\geq 2$ is supported by recorded bounds and a cited construction, while the advertised self-contained proof remains independently unverified.