Ben Green's Open Problem 31

The question

green_31.lower. Can we improve the lower bound $N^{1/2}+O(1)$, at least for infinitely many $N$?

green_31.upper. Can we improve the upper bound $N^{1/2}+0.94349N^{1/4}+O(1)$ [HZ26], at least for infinitely many $N$?

Write $F(N)$ for the largest Sidon subset of $[N]$. Improve, at least for infinitely many $N$, the bounds $N^{1/2}+O(1)\le F(N)\le N^{1/2}+N^{1/4}+O(1)$.

Note: the upper bound was improved to $N^{1/2}+0.98183N^{1/4}+O(1)$ in [CHO25], and then to $N^{1/2}+0.94349\dots N^{1/4}+O(1)$ in [HZ26].

Related to Erdős Problem 30.

Formal statement (Lean 4)

From Formal Conjectures, module FormalConjectures.GreensOpenProblems.«31» (2 statements). answer(sorry) marks a yes/no question: a proof of the statement on the right of ↔, or of its negation, answers it.

theorem green_31.lower :
    let ans := (answer(sorry) : ℕ → ℝ)
    Filter.Tendsto (fun N ↦ ans N - Real.sqrt (N : ℝ)) atTop atTop ∧ -- Break the O(1) barrier
    ∃ᶠ N in atTop, ans N ≤ F N

theorem green_31.upper :
    let ans := (answer(sorry) : ℕ → ℝ)
    (∃ᶠ N in atTop, F N ≤ ans N) ∧
    ∃ c < (0.94349 : ℝ), ∃ C : ℝ, ∀ᶠ N in atTop, ans N - Real.sqrt (N : ℝ) ≤ c * (N : ℝ) ^ (4⁻¹ : ℝ) + C

What counts as progress

• A Lean proof of one of the statements above, pinned as the claim's formal statement.
• Partial results: special cases, weaker bounds, reductions — as verified claims.
• Computations and numerical evidence with published code (reproducible).
• Literature: the problem may have been solved or partly solved already. Report it as a literature claim.
• A precise flaw in the formal statement (a misformalisation) — report it upstream too.

Variants

• green_31.variants.lower_eventually — Can we improve the lower bound N^1/2 + O(1), for all sufficiently large N?
• green_31.variants.upper_eventually — Can we improve the upper bound N^1/2 + 0.94349 N^1/4 + O(1) [HZ26], for all sufficiently large N?
• green_31.variants.zmod_p — It is not known whether or not there exists a Sidon subset of ℤ/pℤ of size (1 + o(1))√(p), for all p [Gr24].
• green_31.variants.abelian — It is not known whether, if G is an abelian group of size n, there always exists a Sidon subset of G of size 0.01√(n) [Gr24].
• green_31.variants.sidon_01n — Another very nice old problem is whether there is a Sidon subset of 0, 1^n of size N^0.51, where N = 2^n [Gr24].

References

• [Gr24] [Ben Green's Open Problem 31](https://people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf#section.7 Problem 31)
• [Gr01] Green, Ben. "The number of squares and $B_h[g]$ sets." Acta Arithmetica 100.4 (2001): 365-390.
• [BFR23] Balogh, József, Zoltán Füredi, and Souktik Roy. "An upper bound on the size of Sidon sets." The American Mathematical Monthly 130.5 (2023): 437-445.
• [CHO25] Carter, Daniel, Zach Hunter, and Kevin O’Bryant. "On the diameter of finite Sidon sets." Acta Mathematica Hungarica 175.1 (2025): 108-126.
• [HZ26] Hou, Jianfeng, and Hongbin Zhao. "An Improved Upper Bound for Finite Sidon Sets via Vector-Valued Smoothing." arXiv:2607.01169 (2026).
• [ET41] Erdos, Paul, and Pál Turán. "On a problem of Sidon in additive number theory, and on some related problems." J. London Math. Soc 16.4 (1941): 212-215.
• [Li69] Lindström, Bernt. “A remark on B4-Sequences.” Journal of Combinatorial Theory, Series A 7 (1969): 276-277.
• [CLZ01] Cohen, G.D., Litsyn, S., & Zémor, G. (2001). Binary B2-Sequences : A New Upper Bound. J. Comb. Theory A, 94, 152-155.

Source and licence

Imported from Formal Conjectures (Ben Green's 100 open problems), commit e6d1743831c2. Statements and descriptions © The Formal Conjectures Authors, Apache License 2.0; reformatted for this page.