Sidon sequence
In number theory, a Sidon sequence is a sequence formula_1 of natural numbers in which all pairwise sums formula_2 (for formula_3) 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 formula_4. Despite a large body of research, the question remained unsolved. Early results. Paul Erdős and Pál Turán proved  that, for every formula_5, the number of elements smaller than formula_4 in a Sidon sequence is at most formula_7. Several years earlier, James Singer had constructed Sidon sequences with formula_8 terms less than "x". Infinite Sidon sequences. Erdős also showed that, for any particular infinite Sidon sequence formula_9 with formula_10 denoting the number of its elements up to formula_4, formula_12 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 formula_13 for every formula_4. Ajtai, Komlós, and Szemerédi improved  this with a construction of a Sidon sequence with formula_15 The best lower bound to date was given by Imre Z. Ruzsa, who proved that a Sidon sequence with formula_16 exists. Erdős conjectured that an infinite Sidon set formula_9 exists for which formula_18 holds. He and Rényi showed the existence of a sequence formula_19 with the conjectural density but satisfying only the weaker property that there is a constant formula_20 such that for every natural number formula_21 there are at most formula_20 solutions of the equation formula_23. (To be a Sidon sequence would require that formula_24.) 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 formula_25 with formula_26 such that the range of the function formula_27 is a Sidon sequence, where formula_28 denotes the integer part. As formula_25 is irrational, this function formula_30 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 . Relationship to Golomb rulers. All finite Sidon sets are Golomb rulers, and vice versa. To see this, suppose for a contradiction that formula_31 is a Sidon set and not a Golomb ruler. Since it is not a Golomb ruler, there must be four members such that formula_32. It follows that formula_33, which contradicts the proposition that formula_31 is a Sidon set. Therefore all Sidon sets must be Golomb rulers. By a similar argument, all Golomb rulers must be Sidon sets.