Problem Statement
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)?\]
Categories:
Number Theory Sidon Sets Additive Combinatorics
Progress
A problem of Erdős and Turán. It may even be true that $h(N)=N^{1/2}+O(1)$, but Erdős remarks this is perhaps too optimistic. Erdős and Turán [ErTu41] proved an upper bound of $N^{1/2}+O(N^{1/4})$, with an alternative proof by Lindström [Li69]. Both proofs in fact give\[h(N) \leq N^{1/2}+N^{1/4}+1.\]Balogh, Füredi, and Roy [BFR21] improved the bound in the error term to $0.998N^{1/4}$. This was further optimised by O'Bryant [OB22]. The current record is\[h(N)\leq N^{1/2}+0.98183N^{1/4}+O(1),\]due to Carter, Hunter, and O'Bryant [CHO25].Singer [Si38] was the first to show that $h(N)\geq (1-o(1))N^{1/2}$ for all $N$. For a detailed survey of the literature we refer to [OB04].
See also [241] and [840].
This problem is Problem 31 on Green's open problems list.
This is discussed in problem C9 of Guy's collection [Gu04].
Source: erdosproblems.com/30 | Last verified: January 13, 2026