Sidon sequence
Encyclopedia
In number theory
, a Sidon sequence (or Sidon set), named after the Hungarian mathematician Simon Sidon, is a sequence A = {a0, a1, a2, ...} 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, is how many elements can A have up to some number x. Despite a large body of research the question remained unsolved for almost 80 years. Recently, it was finally settled 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
and using a construction of J. Singer they get a 
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
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
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 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.
s, 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
. It follows that 
, 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.
Number theory
Number theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...
, a Sidon sequence (or Sidon set), named after the Hungarian mathematician Simon Sidon, is a sequence A = {a0, a1, a2, ...} of natural numbers in which all pairwise sums ai + aj (i ≤ j) are different. Sidon introduced the concept in his investigations of Fourier series
Fourier series
In mathematics, a Fourier series decomposes periodic functions or periodic signals into the sum of a set of simple oscillating functions, namely sines and cosines...
.
The main problem, posed by Sidon, is how many elements can A have up to some number x. Despite a large body of research the question remained unsolved for almost 80 years. Recently, it was finally settled by J. Cilleruelo, I. Ruzsa
Imre Z. Ruzsa
Imre Z. Ruzsa is a Hungarian mathematician specializing in number theory.Ruzsa participated in the International Mathematical Olympiad for Hungary, winning a silver medal in 1969, and two consecutive gold medals with perfect scores in 1970 and 1971. He graduated from the Eötvös Loránd University...
and C. Vinuesa.
Paul Erdős
Paul Erdos
Paul Erdős was a Hungarian mathematician. Erdős published more papers than any other mathematician in history, working with hundreds of collaborators. He worked on problems in combinatorics, graph theory, number theory, classical analysis, approximation theory, set theory, and probability theory...
and Pál Turán
Pál Turán
Paul Turán was a Hungarian mathematician who worked primarily in number theory. He had a long collaboration with fellow Hungarian mathematician Paul Erdős, lasting 46 years and resulting in 28 joint papers.- Life and education :...
proved that the number of elements of A up to x is at most
and using a construction of J. Singer they get a 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
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
for every x. AjtaiMiklós Ajtai
Miklós Ajtai is a computer scientist at the IBM Almaden Research Center. In 2003 he received the Knuth Prize for his numerous contributions to the field, including a classic sorting network algorithm Miklós Ajtai (born 2 July 1946, Budapest, Hungary) is a computer scientist at the IBM Almaden...
, Komlós
János Komlós (mathematician)
János Komlós is a Hungarian-American mathematician, working in probability theory and discrete mathematics. He is a professor of mathematics at Rutgers University since 1988. He graduated from the Eötvös Loránd University, then became a fellow at the Mathematical Institute of the Hungarian Academy...
, and Szemerédi
Endre Szemerédi
Endre Szemerédi is a Hungarian mathematician, working in the field of combinatorics and theoretical computer science. He is the State of New Jersey Professor of computer science at Rutgers University since 1986...
improved this with a construction of a Sidon sequence with
The best lower bound to date was given by Imre Z. Ruzsa
Imre Z. Ruzsa
Imre Z. Ruzsa is a Hungarian mathematician specializing in number theory.Ruzsa participated in the International Mathematical Olympiad for Hungary, winning a silver medal in 1969, and two consecutive gold medals with perfect scores in 1970 and 1971. He graduated from the Eötvös Loránd University...
, who proved that a Sidon sequence with
exists. Erdős conjectured that an infinite Sidon set A exists for which
holds. He and RényiAlfréd Rényi
Alfréd Rényi was a Hungarian mathematician who made contributions in combinatorics, graph theory, number theory but mostly in probability theory.-Life:...
showed 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 rulerGolomb ruler
In mathematics, a Golomb ruler is a set of marks at integer positions along an imaginary ruler such that no two pairs of marks are the same distance apart. The number of marks on the ruler is its order, and the largest distance between two of its marks is its length...
s, 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
. It follows that , 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.