Sidon set

A set of natural numbers is called a Sidon set if all pairwise sums of its elements are distinct. Equivalently, the equation a+b=c+d has only the trivial solution {a,b}={c,d} in elements of the set.

Sidon sets are a special case of so-called Bh[g] sets. A set A is called a Bh[g] set if for every n the equation n=a1++ah has at most g different solutions with a1ah being elements of A. The Sidon sets are B2[1] sets.

Define Fh(n,g) as the size of the largest Bh[g] set contained in the interval [1,n]. Whereas it is known that F2(n,1)=n1/2+O(n5/16)[3, p. 85], no asymptotical results are known for g>1 or h>2 [2].

Every finite setMathworldPlanetmath has a rather large Bh[1] subset. Komlós, Sulyok, and Szemerédi[4] proved that in every n-element set there is a Bh[1] subset of size at least cFh(n,1) for c=18(2h)-6. For Sidon sets Abbott[1] improved that to c=2/25. It is not known whether one can take c=1.

The infiniteMathworldPlanetmath Bh[g] sets are understood even worse. Erdős [3, p. 89] proved that for every infinite Sidon set A we have lim infn(n/logn)-1/2|A[1,n]|<C for some constant C. On the other hand, for a long time no example of a set for which |A[1,n]|>n1/3+ϵ for some ϵ>0 was known. Only recently Ruzsa[6] used an extremely clever construction to prove the existence of a set A for which |A[1,n]|>n2-1-ϵ for every ϵ>0 and for all sufficiently large n.

For an excellent survey of Sidon sets see [5].


  • 1 Harvey Leslie Abbott. Sidon sets. Canad. Math. Bull., 33(3):335–341, 1990. 0715.11004.
  • 2 Ben Green. Bh[g] sets: The current state of affairs. bjg23/papers/bhgbounds.dvi bjg23/papers/bhgbounds.dvi, 2000.
  • 3 Heini Halberstam and Klaus Friedrich Roth. SequencesMathworldPlanetmath. Springer-Verlag, second edition, 1983. 0498.10001.
  • 4 János Komlós, Miklos Sulyok, and Endre Szemerédi. Linear problems in combinatorial number theory. Acta Math. Acad. Sci. Hung., 26:113–121, 1975. 0303.10058.
  • 5 Kevin O’Bryant. A completePlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath annotated bibliography of work related to Sidon sequences. Electronic Journal of Combinatorics.
  • 6 Imre Ruzsa. An infinite Sidon sequence. J. Number TheoryMathworldPlanetmathPlanetmath, 68(1):63–71, 1998. Available at ruzsa/cikkek.html ruzsa/cikkek.html.
Title Sidon set
Canonical name SidonSet
Date of creation 2013-03-22 13:59:40
Last modified on 2013-03-22 13:59:40
Owner bbukh (348)
Last modified by bbukh (348)
Numerical id 12
Author bbukh (348)
Entry type Definition
Classification msc 11B05
Classification msc 11B34
Synonym Sidon sequence
Related topic ErdHosTuranConjecture
Defines Bh[g] set