Sidon also asked: Let 1 ≤ a_1 0.

Erdős Problem #30 — Maximum size of Sidon sets in $[1,n]$

Erdős

Sidon also asked: Let $1 \leq a_1 < a_2 < \cdots < a_k \leq n$ and assume that $a_i + a_j$ are all distinct. Put $h(n) = \max k$ . Determine or estimate $h(n)$ as accurately as possible. Perhaps

h(n) = n^{1/2} + O(1),

but this is perhaps too optimistic. I give 500 dollars for a proof or disproof of the conjecture

h(n) = n^{1/2} + o(n^{\varepsilon})

for any $\varepsilon > 0$ .

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Equivalent formulations 1

Other statements of this same problem, merged from separate entries. Each is equivalent to the statement above — proving any one settles them all.

Sidon set problem
In number theory, a Sidon sequence is a sequence $A=\{a_{0},a_{1},a_{2},\dots \}$ of natural numbers in which all pairwise sums $a_{i}+a_{j}$ (for $i\leq j$ ) are different. Sidon sequences are also called Sidon sets; they are named after the Hungarian mathematician Simon Sidon, who introduced the concept in his investigations of Fourier series. The main problem in the study of Sidon sequences, posed by Sidon, is to find the maximum number of elements that a Sidon sequence can contain, up to some bound $x$ . Despite a large body of research, the question has remained unsolved.
source: Wikipedia

Sources & referencesView supporting material

Primary source

P. Erdős, Some of my favourite problems in number theory, combinatorics, and geometry, Resenhas IME-USP 2 (1995), 165-186.

3 weeks ago

Progress summary

Equivalent formulations 1

Sidon set problem

Primary source