The largest Sidon set in {1, …, N}

A Sidon set is a set of integers whose pairwise sums are all different. The largest Sidon set in $\{1,\dots,N\}$ has about $\sqrt N$ elements, and Erdős and Turán asked how small the error in this approximation is. Since 1941 the error has been known to be at most of order $N^{1/4}$ , and only the constant in front of $N^{1/4}$ has improved.

Problem

A set $A$ of integers is a Sidon set if all sums $a+b$ with $a,b\in A$ , $a\le b$ , are distinct (equivalently, all differences $a-b$ with $a\neq b$ are distinct). Let $h(N)$ be the maximum size of a Sidon set contained in $\{1,\dots,N\}$ . Is it true that for every $\varepsilon>0$

h(N)=N^{1/2}+O_\varepsilon(N^{\varepsilon})\,?

Erdős offered $1000 for this. He remarked that perhaps even $h(N)=N^{1/2}+O(1)$ , though this may be too optimistic.

Background

The problem goes back to Erdős and Turán (1941), who proved $h(N)\le N^{1/2}+O(N^{1/4})$ . On the other side, Singer's 1938 construction of perfect difference sets from finite projective planes shows that $h(N)\ge(1-o(1))N^{1/2}$ . Sidon sets in $\{1,\dots,N\}$ are the same objects as Golomb rulers of length less than $N$ . The problem is C9 in Guy's Unsolved Problems in Number Theory and Problem 31 on Ben Green's list of open problems.

What is known

Upper bounds. The argument of Erdős and Turán and a different one by Lindström (1969) both give $h(N)\le N^{1/2}+N^{1/4}+1$ . The coefficient of $N^{1/4}$ was lowered to $0.998$ by Balogh, Füredi and Roy (2023), then further by O'Bryant, and to $0.98183$ by Carter, Hunter and O'Bryant (2025), whose proof uses substantial computer assistance. Hou and Zhao (2026, preprint) obtained $h(N)\le N^{1/2}+0.9435\,N^{1/4}+O(1)$ with a certificate checked in exact rational arithmetic. Claims posted on the problem's forum and its proof-claims page between August and October 2026, one of them with a Lean formalisation, lower the coefficient to about $2\sqrt2/3\approx0.94281$ and indicate that this is the limit of the smoothing method; they have not been refereed.
Lower bounds. Singer's construction gives $h(N)\ge(1-o(1))N^{1/2}$ for all $N$ .
No upper bound of the form $N^{1/2}+O(N^{c})$ with $c<1/4$ is known.

What would count as progress

Any power saving in the error term: a proof that $h(N)\le N^{1/2}+O(N^{1/4-\delta})$ for some $\delta>0$ .
A smaller constant in front of $N^{1/4}$ , together with a certificate that can be checked in exact arithmetic, as in the work of Carter, Hunter and O'Bryant and of Hou and Zhao.
A disproof: Sidon sets with $h(N)\ge N^{1/2}+N^{c}$ for some $c>0$ and infinitely many $N$ , given explicitly or by a checkable construction.
A formal proof against the Lean statement in formal-conjectures.

References

P. Erdős and P. Turán, On a problem of Sidon in additive number theory, and on some related problems, J. London Math. Soc. 16 (1941), 212–215. doi:10.1112/jlms/s1-16.4.212
J. Singer, A theorem in finite projective geometry and some applications to number theory, Trans. Amer. Math. Soc. 43 (1938), 377–385. doi:10.1090/S0002-9947-1938-1501951-4
B. Lindström, An inequality for $B_2$ -sequences, J. Combin. Theory 6 (1969), 211–212. doi:10.1016/S0021-9800(69)80124-9
D. Carter, Z. Hunter and K. O'Bryant, On the diameter of finite Sidon sets, Acta Math. Hungar. 175 (2025), 108–126. doi:10.1007/s10474-024-01499-8
J. Hou and H. Zhao, An improved upper bound for finite Sidon sets via vector-valued smoothing (2026). arXiv:2607.01169
K. O'Bryant, A complete annotated bibliography of work related to Sidon sequences, Electron. J. Combin., Dynamic Survey DS11 (2004). doi:10.37236/32

Source

Imported from Erdős Problems 30, curated by Thomas Bloom. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.