Erdős Problem #840

declared status 'open'. Formalized: no. Let $f(N)$ be the size of the largest quasi-Sidon subset $A\subset\{1,\ldots,N\}$, where we say that $A$ is quasi-Sidon if$$\lvert A+A\rvert=(1+o(1))\binom{\lvert A\rvert}{2}.$$How does $f(N)$ grow? Current best: The lower bound is taking a genuine Sidon set $B\subset [1,N/3]$ of size $\sim N^{1/2}/\sqrt{3}$ and taking the union with $\{N-b : b\in B\}$. The upper bound was improved by Pikhurko [Pi06] to$$f(N) \leq \left(\left(\frac{1}{4}+\frac{1}{(\pi+2)^2}\right)^{-1/2}+o(1)\right)N^{1/2}$$(the constant here is $=1.863\cdots$). Prize: no. Tags: additive combinatorics, sidon sets.

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