Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated Oct 8

Problem 30

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

Status. 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.

Source. erdosproblems.com/30, accessed 2026-09-04. Cite as: T. F. Bloom, Erdős Problem #30, https://www.erdosproblems.com/30.

References.

[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_unsolved_problems_number_theory.
[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.

Formalization. Statement in formal-conjectures, tagged research open with no formal_proof attribute.

Progress

Not yet compiled.

Known Results

Not yet compiled.

Linked library material

These entries are derived from explicit links on library pages. They are navigation only and do not by themselves record mathematical progress.

Linked from (21)

Additive Bases and Sidon Sets Additive Bases and Sidon Sets An upper bound on the size of Sidon sets Theorem 1.1: a Sidon set in [n] has fewer than n^(1/2) + (1 - gamma) n^(1/4) elements for large n, gamma >= 0.002 additive_bases/carter_2025_diameter_finite_sidon_sets additive_bases/erdos_1941_problem_sidon_additive_number_theory_related Theorem (p. 212): the largest Sidon set in [1,n] exceeds (1/sqrt(2) - e) sqrt(n)Theorem (p. 212): the largest Sidon set in [1,n] has fewer than (1 + e) sqrt(n) elements additive_bases/kolountzakis_1996_density_b_h_g_sequences_minimum Theorem 1 (p. 5): an upper bound for B_h sets in [1, n] when h is even additive_bases/martin_2005_constructions_generalized_sidon_sets Theorem 2 (p. 5): lower bounds for generalized Sidon sets from unions and products additive_bases/obryant_2022_size_finite_sidon_sets Theorem 1: a k-element Sidon set has diameter at least k^2 - 2k^(3/2) + k + sqrt(k) - 1 Theorem 2: diam(A) >= k^2 - 1.99405 k^(3/2) for large k, and R_2(n) < n^(1/2) + 0.99703 n^(1/4) for large n Theorem 4: the Erdős–Turán Sidon set equation for diam(A)additive_bases/plagne_nd_recent_progress_finite_b_h_g Problem 4: improving F_{2,1}(N) <= sqrt(N) + N^{1/4} + 1 Singer: A theorem in finite projective geometry and some applications to number theory Theorem (pp. 380-381, unnumbered): a perfect difference set of order m + 1 exists when m is a prime power number_theory/guy_2004_unsolved_problems_number_theory

Graph