Problem 530

Erdős Problem #530: declared status 'open'. Formalized: no. Let $\ell(N)$ be maximal such that in any finite set $A\subset \mathbb{R}$ of size $N$ there exists a Sidon subset $S$ of size $\ell(N)$ (i.e. the only solutions to $a+b=c+d$ in $S$ are the trivial ones). Determine the order of $\ell(N)$. In particular, is it true that $\ell(N)\sim N^{1/2}$? Current best: Erd\H{o}s noted the bounds$$N^{1/3} \ll \ell(N) \leq (1+o(1))N^{1/2}$$(the upper bound following from the case $A=\{1,\ldots,N\}$). The lower bound was improved to $N^{1/2}\ll \ell(N)$ by Koml\'{o}s, Sulyok, and Szemer\'{e}di [KSS75]. The correct constant is unknown, but it is likely that the upper bound is true, so that $\ell(N)\sim N^{1/2}$. Prize: no. OEIS: A143824. Tags: number theory, sidon sets.