Logo
All Random Solved Random Open
OPEN - $1000
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)?\]
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}$, which has been further optimised by O'Bryant [OB22] to yield \[h(N)\leq N^{1/2}+0.99703N^{1/4}\] for sufficiently large $N$.
Additional thanks to: Zachary Hunter