Problem 30

Erdős Problem #30: declared status 'open'. Formalized: yes. Let $h(N)$ be the maximum size of a Sidon set in $\{1,\ldots,N\}$. Is it true that, for every $\epsilon>0$,$$h(N) = N^{1/2}+O_\epsilon(N^\epsilon)?$$ Current best: Erd\H{o}s and Tur\'{a}n [ErTu41] proved an upper bound of $N^{1/2}+O(N^{1/4})$, with an alternative proof by Lindstr\"{o}m [Li69]. The current record is$$h(N)\leq N^{1/2}+0.98183N^{1/4}+O(1),$$due to Carter, Hunter, and O'Bryant [CHO25]. and Roy, S., An upper bound on the size of Sidon sets. Prize: $1000. OEIS: A003022, A143824, A227590. Tags: additive combinatorics, number theory, sidon sets.