Apparently originally considered by Erdős and Nathanson, although later Erdős attributes this to Erdős, Sárközy, and Szemerédi (but gives no reference), and claims a construction of an $A$ such that for all $\epsilon>0$ and all large $N$\[\lvert \{1,\ldots,N\}\backslash B\rvert \ll_\epsilon N^{1/2+\epsilon},\]and yet there for all $\epsilon>0$ there exist infinitely many $N$ where\[\lvert \{1,\ldots,N\}\backslash B\rvert \gg_\epsilon N^{1/3-\epsilon}.\]Erdös and Freud investigated the finite analogue in [ErFr91], proving that there exists $A\subseteq \{1,\ldots,N\}$ such that the number of integers not representable in exactly one way as the sum of two elements from $A$ is $<2^{3/2}N^{1/2}$, and suggest the constant $2^{3/2}$ is perhaps best possible.

View the LaTeX source

This page was last edited 14 September 2025.