Erdős Problem #43

declared status 'disproved'. Formalized: yes. If $A,B\subset \{1,\ldots,N\}$ are two Sidon sets such that $(A-A)\cap(B-B)=\{0\}$ then is it true that$$\binom{\lvert A\rvert}{2}+\binom{\lvert B\rvert}{2}\leq\binom{f(N)}{2}+O(1),$$where $f(N)$ is the maximum possible size of a Sidon set in $\{1,\ldots,N\}$? If $\lvert A\rvert=\lvert B\rvert$ then can this bound be improved to$$\binom{\lvert A\rvert}{2}+\binom{\lvert B\rvert}{2}\leq (1-c+o(1))\binom{f(N)}{2}$$for some constant $c>0$? Current best: Since it is known that $f(N)\sim \sqrt{N}$ (see [30]) the latter question is equivalent to asking whether, if $\lvert A\rvert=\lvert B\rvert$,$$\lvert A\rvert \leq \left(\frac{1}{\sqrt{2}}-c+o(1)\right)\sqrt{N}$$for some constant $c>0$. In the comments Tao has given a proof of this upper bound without the $-c$. Prize: $100. OEIS: A003022, A143824, A227590. Tags: additive combinatorics, number theory, sidon sets.

Notation is rendered from the stored source. The pinned checkout remains the exact record.