Logo
All Random Solved Random Open
OPEN
Let $A\subseteq \mathbb{N}$. Let $B\subseteq \mathbb{N}$ be the set of integers which are representable in exactly one way as the sum of two elements from $A$. Is it true that for all $\epsilon>0$ and large $N$ \[\lvert \{1,\ldots,N\}\backslash B\rvert \gg_\epsilon N^{1/2-\epsilon}.\]
Asked by Erdős, Sárközy, and Szemerédi, who constructed 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 'a recent Hungarian paper', 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.