Sidon sequence

In number theory, a Sidon sequence (or Sidon set), named after the Hungarian mathematician Simon Sidon, is a sequence A = {a0a1a2, ...} of natural numbers in which all pairwise sums ai + aj (i ≤ j) are different. Sidon introduced the concept in his investigations of Fourier series.

The main problem, posed by Sidon[1], is how many elements can A have up to some number x. Despite a large body of research[2] the question remained unsolved for almost 80 years. Recently, it was finally settled[3] by J. Cilleruelo, I. Ruzsa and C. Vinuesa.

Paul Erdős and Pál Turán proved that the number of elements of A up to x is at most \sqrt{x}%2BO(\sqrt[4]{x}) and using a construction of J. Singer they get a \sqrt{x}(1-o(1)) lower bound.

If, however, we consider an infinite Sidon sequence A and let A(x) denote the number of its elements up to x, then Erdos showed that

\liminf \frac{A(x)\sqrt{\log x}}{\sqrt{x}}\leq 1

that is, infinite Sidon sequences are thinner than the above bound for finite sequences.

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

A(x)>\sqrt[3]{x\log x}.

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

A(x)>x^{\sqrt{2}-1-o(1)}

exists. Erdős conjectured that an infinite Sidon set A exists for which A(x)>x^{1/2-o(1)} holds. He and Rényi showed[6] the existence of such a sequence a0,a1,...with the weaker property that for every natural number n there are at most c solutions of the equation ai+aj=n for some constant c.

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

Relationship to Golomb rulers

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

To see this, suppose for a contradiction that S is a Sidon Set and not a Golomb ruler. Since it is not a Golomb ruler, there must be four members such that a_i-a_j=a_k-a_l. It follows that a_i%2Ba_l=a_k%2Ba_j, which contradicts the proposition that S is a Sidon set. Therefore all Sidon Sets must be Golomb rulers. By a similar argument, all Golomb rulers must be Sidon sets.

See also

References