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

1. 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
2. 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
3. B. Lindström, An inequality for $B_2$-sequences, J. Combin. Theory 6 (1969), 211–212. doi:10.1016/S0021-9800(69)80124-9
4. 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
5. J. Hou and H. Zhao, An improved upper bound for finite Sidon sets via vector-valued smoothing (2026). arXiv:2607.01169
6. 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.