Problem 30

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)?

Source: erdosproblems.com/30

Number theory
Sidon sets
Additive combinatorics

Wiki page

Status

Open

No claim settles this problem.

Open, the site's label (OPEN; page last edited 2026-04-06). The site's proof-claims thread carries one partial claim (2026-10-02): Haoyu Chen's write-up An explicit second-order bound for Sidon sets (Zenodo; the proofs are credited to GPT-6 Astra and the referee reports to Claude Opus, and a Lean proof of the bound carries no formal-verification credit in this corpus) claims $h(N)\le\sqrt N+(2\sqrt2/3)N^{1/4}+1$ for $N\ge120^4$ , with $2\sqrt2/3=0.9428\ldots$ below the $0.98183$ of [CHO25]. It settles no instance of the question, so it has no claim page; the thread (as of 2026-10-07) lists it without comment. The discussion thread (as of 2026-10-07) reports further bounds on the same $N^{1/4}$ coefficient, among them $0.9435$ by Hou and Zhao (arXiv:2607.01169, 2026), none of which touches the $O_\epsilon(N^\epsilon)$ question.

BFR21: Balogh, J. and Füredi, Z. and Roy, S., An upper bound on the size of Sidon sets. arXiv:2103.15850 (2021).
CHO25: Carter, D. and Hunter, Z. and O'Bryant, K., On the diameter of finite Sidon sets. Acta Math. Hungar. (2025), 108-126.
ErTu41: Erdős, P. and Turán, P., On a problem of Sidon in additive number theory, and on some related problems. J. London Math. Soc. (1941), 212-215.
Gu04: Guy, Richard K., Unsolved problems in number theory. Third edition, Problem Books in Mathematics, Springer, New York (2004), xviii+437 pp.; section C9 "Packing sums of pairs", pp. 175--176: the Erdős--Turán question whether $m=n^{1/2}+O(1)$ , with the prize offer, Lindström's upper bound and Singer's lower bound. Library home: Guy 2004.
Li69: Lindström, B., An inequality for $B_2$ -sequences. J. Combinatorial Theory (1969), 211-212.
OB04: O'Bryant, Kevin, A complete annotated bibliography of work related to Sidon sequences. Electron. J. Combin. (2004), 39.
OB22: O'Bryant, K., On the size of finite Sidon sets. arXiv:2207.07800 (2022).
Si38: Singer, James, A theorem in finite projective geometry and some applications to number theory. Trans. Amer. Math. Soc. (1938), 377-385.

Problem 30

Status

Proof claims

Discussion