Sidon sequence

From Wikipedia, the free encyclopedia

In number theory, a Sidon sequence is a sequence of natural numbers in which all pairwise sums (for ) 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,[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]

Early results[edit]

Paul Erdős and Pál Turán proved that, for every , the number of elements smaller than in a Sidon sequence is at most . Several years earlier, James Singer had constructed Sidon sequences with terms less than x. The bound was improved to in 1969[4] and to in 2023.[5]

In 1994 Erdős offered 500 dollars for a proof or disproof of the bound .[6]

Infinite Sidon sequences[edit]

Erdős also showed that, for any particular infinite Sidon sequence with denoting the number of its elements up to ,

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

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

exists. Erdős conjectured that an infinite Sidon set exists for which holds. He and Rényi showed[10] the existence of a sequence with the conjectural density but satisfying only the weaker property that there is a constant such that for every natural number there are at most solutions of the equation . (To be a Sidon sequence would require that .)

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 with such that the range of the function is a Sidon sequence, where denotes the integer part. As is irrational, this function 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.

Sidon sequences which are asymptotic bases[edit]

The existence of Sidon sequences that form an asymptotic basis of order (meaning that every sufficiently large natural number can be written as the sum of numbers from the sequence) has been proved for in 2010,[11] in 2014,[12] (the sum of four terms with one smaller than , for arbitrarily small positive ) in 2015[13] and in 2023 as a preprint,[14][15] this later one was posed as a problem in a paper of Erdős, Sárközy and Sós in 1994.[16]

Relationship to Golomb rulers[edit]

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

To see this, suppose for a contradiction that 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 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[edit]


  1. ^ Erdős, P.; Turán, P. (1941), "On a problem of Sidon in additive number theory and on some related problems" (PDF), J. London Math. Soc., 16 (4): 212–215, doi:10.1112/jlms/s1-16.4.212. Addendum, 19 (1944), 208.
  2. ^ O'Bryant, K. (2004), "A complete annotated bibliography of work related to Sidon sequences", Electronic Journal of Combinatorics, 11: 39, doi:10.37236/32.
  3. ^ Guy, Richard K. (2004), "C9: Packing sums in pairs", Unsolved problems in number theory (3rd ed.), Springer-Verlag, pp. 175–180, ISBN 0-387-20860-7, Zbl 1058.11001
  4. ^ Linström, Bern (1969). "An inequality for B2-sequences". Journal of Combinatorial Theory. 6 (2): 211–212. doi:10.1016/S0021-9800(69)80124-9.
  5. ^ Balogh, József; Füredi, Zoltán; Roy, Souktik (2023-05-28). "An Upper Bound on the Size of Sidon Sets". The American Mathematical Monthly. 130 (5): 437–445. doi:10.1080/00029890.2023.2176667. ISSN 0002-9890. S2CID 232417382.
  6. ^ Erdős, Paul (1994). "Some problems in number theory, combinatorics and combinatorial geometry" (PDF). Mathematica Pannonica. 5 (2): 261–269.
  7. ^ Mian, Abdul Majid; Chowla, S. (1944), "On the B2 sequences of Sidon", Proc. Natl. Acad. Sci. India A, 14: 3–4, MR 0014114.
  8. ^ Ajtai, M.; Komlós, J.; Szemerédi, E. (1981), "A dense infinite Sidon sequence", European Journal of Combinatorics, 2 (1): 1–11, doi:10.1016/s0195-6698(81)80014-5, MR 0611925.
  9. ^ Ruzsa, I. Z. (1998), "An infinite Sidon sequence", Journal of Number Theory, 68: 63–71, doi:10.1006/jnth.1997.2192, MR 1492889.
  10. ^ Erdős, P.; Rényi, A. (1960), "Additive properties of random sequences of positive integers" (PDF), Acta Arithmetica, 6: 83–110, doi:10.4064/aa-6-1-83-110, MR 0120213.
  11. ^ Kiss, S. Z. (2010-07-01). "On Sidon sets which are asymptotic bases". Acta Mathematica Hungarica. 128 (1): 46–58. doi:10.1007/s10474-010-9155-1. ISSN 1588-2632. S2CID 96474687.
  12. ^ Kiss, Sándor Z.; Rozgonyi, Eszter; Sándor, Csaba (2014-12-01). "On Sidon sets which are asymptotic bases of order $4$". Functiones et Approximatio Commentarii Mathematici. 51 (2). arXiv:1304.5749. doi:10.7169/facm/2014.51.2.10. ISSN 0208-6573. S2CID 119121815.
  13. ^ Cilleruelo, Javier (November 2015). "On Sidon sets and asymptotic bases". Proceedings of the London Mathematical Society. 111 (5): 1206–1230. doi:10.1112/plms/pdv050. S2CID 34849568.
  14. ^ Pilatte, Cédric (2023-03-16). "A solution to the Erd\H{o}s-S\'ark\"ozy-S\'os problem on asymptotic Sidon bases of order 3". arXiv:2303.09659v1 [math.NT].
  15. ^ "First-Year Graduate Finds Paradoxical Number Set". Quanta Magazine. 2023-06-05. Retrieved 2023-06-13.
  16. ^ Erdős, P.; Sárközy, A.; Sós, V. T. (1994-12-31). "On additive properties of general sequences". Discrete Mathematics. 136 (1): 75–99. doi:10.1016/0012-365X(94)00108-U. ISSN 0012-365X. S2CID 38168554.