Paul Erdős and Pál Turán proved that, for every ${\displaystyle x>0}$ , the number of elements smaller than ${\displaystyle x}$  in a Sidon sequence is at most ${\displaystyle {\sqrt {x}}+O({\sqrt[{4}]{x}})}$ . Several years earlier, James Singer had constructed Sidon sequences with ${\displaystyle {\sqrt {x}}(1-o(1))}$  terms less than x. The bound was improved to ${\displaystyle {\sqrt {x}}+{\sqrt[{4}]{x}}+1}$  in 1969^[4] and to ${\displaystyle {\sqrt {x}}+0.998{\sqrt[{4}]{x}}}$  in 2023.^[5]

In 1994 Erdős offered 500 dollars for a proof or disproof of the bound ${\displaystyle {\sqrt {x}}+o(x^{\epsilon })}$ .^[6]

Erdős also showed that, for any particular infinite Sidon sequence ${\displaystyle A}$  with ${\displaystyle A(x)}$  denoting the number of its elements up to ${\displaystyle x}$ ,

For the other direction, Chowla and Mian observed that the greedy algorithm gives an infinite Sidon sequence with ${\displaystyle A(x)>c{\sqrt[{3}]{x}}}$  for every ${\displaystyle x}$ .^[7] Ajtai, Komlós, and Szemerédi improved this with a construction^[8] of a Sidon sequence with

The best lower bound to date was given by Imre Z. Ruzsa, who proved^[9] that a Sidon sequence with

Erdős further conjectured that there exists a nonconstant integer-coefficient polynomial whose values at the natural numbers form a Sidon sequence. Specifically, he asked if the set of fifth powers is a Sidon set. Ruzsa came close to this by showing that there is a real number ${\displaystyle c}$  with ${\displaystyle 0<c<1}$  such that the range of the function ${\displaystyle f(x)=x^{5}+\lfloor cx^{4}\rfloor }$  is a Sidon sequence, where ${\displaystyle \lfloor \ \rfloor }$  denotes the integer part. As ${\displaystyle c}$  is irrational, this function ${\displaystyle f(x)}$  is not a polynomial. The statement that the set of fifth powers is a Sidon set is a special case of the later conjecture of Lander, Parkin and Selfridge.

The existence of Sidon sequences that form an asymptotic basis of order ${\displaystyle m}$  (meaning that every sufficiently large natural number ${\displaystyle n}$  can be written as the sum of ${\displaystyle m}$  numbers from the sequence) has been proved for ${\displaystyle m=5}$  in 2010,^[11] ${\displaystyle m=4}$  in 2014,^[12] ${\displaystyle m=3+\epsilon }$  (the sum of four terms with one smaller than ${\displaystyle n^{\epsilon }}$ , for arbitrarily small positive ${\displaystyle \epsilon }$ ) in 2015^[13] and ${\displaystyle m=3}$  in 2023 as a preprint,^[14][15] this later one was posed as a problem in a paper of Erdős, Sárközy and Sós in 1994.^[16]

All finite Sidon sets are Golomb rulers, and vice versa.

To see this, suppose for a contradiction that ${\displaystyle S}$  is a Sidon set and not a Golomb ruler. Since it is not a Golomb ruler, there must be four members such that ${\displaystyle a_{i}-a_{j}=a_{k}-a_{l}}$ . It follows that ${\displaystyle a_{i}+a_{l}=a_{k}+a_{j}}$ , which contradicts the proposition that ${\displaystyle S}$  is a Sidon set. Therefore all Sidon sets must be Golomb rulers. By a similar argument, all Golomb rulers must be Sidon sets.

• Moser–de Bruijn sequence
• Sumset