Sidon Sequence - Infinite Sidon Sequences

Infinite Sidon Sequences

Erdős also showed that if we consider any particular infinite Sidon sequence A and let A(x) denote the number of its elements up to x, then

.

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 for every x. Ajtai, Komlós, and Szemerédi improved this with a construction of a Sidon sequence with

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

exists. Erdős conjectured that an infinite Sidon set A exists for which holds. He and Rényi showed the existence of a sequence {a₀,a₁,...} with the conjectural density but satisfying only the weaker property that there is a constant k such that for every natural number n there are at most k solutions of the equation a_i + a_j = n. (To be a Sidon sequence would require that k = 1.)

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 c with 0 < c < 1 such that the range of the function f(x) = x5 + is a Sidon sequence, where denotes integer part. As c is irrational, this function 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.