For a set A ⊆ N, call A a Sidon set if all pairwise sums of its elements are distinct, i.e. if for all a_i, a_j, a_k, a_l ∈ A, a_i + a_j = a_k + a_l ;Longrightarrow; a_i, a_j = a_k, a_l. For a real number x > 0 let F(x) = max, |A cap [1,x)| ;:; A ⊆ N is a Sidon set , be the largest possible number of elements smaller than x in a Sidon set. Then for every varepsilon > 0, F(x) = √x + o!(x^varepsilon) qquad (x → ∞), that is, lim_x → ∞ ( F(x) - √x ) x^-varepsilon = 0 for each fixed varepsilon > 0.

Sidon set problem

About 94 years old · traced to 1932

For a set $A \subseteq \mathbb{N}$ , call $A$ a Sidon set if all pairwise sums of its elements are distinct, i.e. if for all $a_i, a_j, a_k, a_l \in A$ ,

a_i + a_j = a_k + a_l \;\Longrightarrow\; \{a_i, a_j\} = \{a_k, a_l\}.

For a real number $x > 0$ let

F(x) = \max\{\, |A \cap [1,x)| \;:\; A \subseteq \mathbb{N} \text{ is a Sidon set} \,\}

be the largest possible number of elements smaller than $x$ in a Sidon set.

Then for every $\varepsilon > 0$ ,

F(x) = \sqrt{x} + o\!\left(x^{\varepsilon}\right) \qquad (x \to \infty),

that is, $\lim_{x \to \infty} \left( F(x) - \sqrt{x} \right) x^{-\varepsilon} = 0$ for each fixed $\varepsilon > 0$ .

References

Primary source

Wikipedia

Additional references

Wikipedia, Sidon sequence, the article this problem comes from.

unsolved-problem

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed progress

The conjecture remains unproved: newer work has only reduced the known error term instead of achieving the claimed near-square-root precision.

This is the Erdős conjecture that the largest Sidon subset below $n$ differs from $\sqrt{n}$ by less than every fixed positive power of $n$ . Public sources continue to describe it as open.

Known results

Erdős and Turán (1941): $S(n)\le \sqrt{n}+O(n^{1/4})$ .
Lindström (1969): $S(n)\le \sqrt{n}+n^{1/4}+1$ .
Balogh, Füredi, and Roy (2021): $S(n)<\sqrt{n}+(1-\gamma)n^{1/4}$ for some $\gamma\ge 0.002$ .
O’Bryant, then Carter and Hunter: the coefficient of $n^{1/4}$ was reduced to $0.99703$ , then $0.98183$ .

July 2026 sharper upper bound

A newer result gives $F(N)\le N^{1/2}+0.94601N^{1/4}+O(1)$ , improving the constant but not proving the Erdős conjecture.

Current status (as of August 2026): The conjecture remains open; the best retrieved progress only improves the coefficient in the $n^{1/4}$ error term.

Sources

No solutions have been posted yet.