Maximum size of a Sidon set

Open

erdos-sidon-set-size

Statement

A Sidon set in ${1, \dots, N}$ has all pairwise sums distinct. Its maximum size is $N^{1/2} + E (N)$ ; determine the true order of the error $E (N)$ (conjectured $O (N^{ε})$ for every $ε > 0$ ).

Current frontier

erdosproblems.com/30, OPEN. Singer's construction gives $(1 + o (1)) N^{1/2}$ ; the error satisfies $- O (N^{5/16}) ≲ E (N) \leq N^{1/4} + 1$ (upper bound Erdős–Turán 1941 / Lindström 1969; lower bound Chowla–Erdős, from Singer). Whether $E (N) = O (N^{ε})$ is open.

When this counts as solved

QUANTITATIVE

PROOF_COMPLETE for the true order of $E (N)$ with matching bounds (notably settling the $O (N^{ε})$ question). BREAKTHROUGH for any rigorous improvement to the $N^{1/4}$ upper or $N^{5/16}$ lower error bound.

Classification

Quantitative

Mine this problem →