of natural numbers in which all pairwise sums
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,[1] is to find the maximum number of elements that a Sidon sequence can contain, up to some bound
Despite a large body of research,[2] the question has remained unsolved.
[3] Paul Erdős and Pál Turán proved that, for every
Several years earlier, James Singer had constructed Sidon sequences with
[5] In 1994 Erdős offered 500 dollars for a proof or disproof of the bound
The structure of dense Sidon sets has a rich literature[7][8] and classic constructions by Erdős–Turán,[9] Singer,[10] Bose,[11] Spence,[12][13] Hughes[14] and Cilleruelo[15] have established that a dense Sidon set
As remarked by Ruzsa, "somehow all known constructions of dense Sidon sets involve the primes".
[16] A recent result of Balasubramanian and Dutta[17] shows that if a dense Sidon set
This directly gives some useful asymptotic results including
Erdős also showed that, for any particular infinite Sidon sequence
That is, infinite Sidon sequences are thinner than the densest finite Sidon sequences.
For the other direction, Chowla and Mian observed that the greedy algorithm gives an infinite Sidon sequence with
[18] Ajtai, Komlós, and Szemerédi improved this with a construction[19] of a Sidon sequence with
The best lower bound to date was given by Imre Z. Ruzsa, who proved[20] that a Sidon sequence with
Erdős conjectured that an infinite Sidon set
He and Rényi showed[21] the existence of a sequence
with the conjectural density but satisfying only the weaker property that there is a constant
Erdős further conjectured that there exists a nonconstant integer-coefficient polynomial whose values at the natural numbers form a Sidon sequence.
Ruzsa came close to this by showing that there is a real number
denotes the integer part.
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
(meaning that every sufficiently large natural number
in 2023 as a preprint,[25][26] this later one was posed as a problem in a paper of Erdős, Sárközy and Sós in 1994.
[27] All finite Sidon sets are Golomb rulers, and vice versa.
is a Sidon set and not a Golomb ruler.
Therefore all Sidon sets must be Golomb rulers.
By a similar argument, all Golomb rulers must be Sidon sets.