|
|
|
|
|
A set of natural numbers is called a Sidon set if all pairwise sums of its elements are distinct. Equivalently, the equation  has only the trivial solution
 in elements of the set.
Sidon sets are a special case of so-called ![$ B_h[g]$](http://images.planetmath.org:8080/cache/objects/4771/l2h/img3.png "$ B_h[g]$") sets. A set  is called a ![$ B_h[g]$](http://images.planetmath.org:8080/cache/objects/4771/l2h/img5.png "$ B_h[g]$") set if for every
 the equation
 has at most  different solutions with
 being elements of  . The Sidon sets are ![$ B_2[1]$](http://images.planetmath.org:8080/cache/objects/4771/l2h/img11.png "$ B_2[1]$") sets.
Define  as the size of the largest ![$ B_h[g]$](http://images.planetmath.org:8080/cache/objects/4771/l2h/img13.png "$ B_h[g]$") set contained in the interval ![$ [1,n]$](http://images.planetmath.org:8080/cache/objects/4771/l2h/img14.png "$ [1,n]$") . Whereas it is known that
 [3, p. 85], no asymptotical results are known for  or  [2].
Every finite set has a rather large ![$ B_h[1]$](http://images.planetmath.org:8080/cache/objects/4771/l2h/img18.png "$ B_h[1]$") subset. Komlós, Sulyok, and Szemerédi[4] proved that in every  -element set there is a ![$ B_h[1]$](http://images.planetmath.org:8080/cache/objects/4771/l2h/img20.png "$ B_h[1]$") subset of size at least  for
 . For Sidon sets Abbott[1] improved that to  . It is not known whether one can take  .
The infinite ![$ B_h[g]$](http://images.planetmath.org:8080/cache/objects/4771/l2h/img25.png "$ B_h[g]$") sets are understood even worse. Erdős [3, p. 89] proved that for every infinite Sidon set  we have
![$ \liminf_{n\to\infty}(n/\log n)^{-1/2} \left\lvert A\cap [1,n]\right\rvert <C$](http://images.planetmath.org:8080/cache/objects/4771/l2h/img27.png "$ \liminf_{n\to\infty}(n/\log n)^{-1/2} \left\lvert A\cap [1,n]\right\rvert <C$") for some constant  . On the other hand, for a long time no example of a set for which
![$ \left\lvert A\cap [1,n]\right\rvert >n^{1/3+\epsilon}$](http://images.planetmath.org:8080/cache/objects/4771/l2h/img29.png "$ \left\lvert A\cap [1,n]\right\rvert >n^{1/3+\epsilon}$") for some
 was known. Only recently Ruzsa[6] used an extremely clever construction to prove the existence of a set  for which
![$ \left\lvert A\cap [1,n]\right\rvert >n^{\sqrt{2}-1-\epsilon}$](http://images.planetmath.org:8080/cache/objects/4771/l2h/img32.png "$ \left\lvert A\cap [1,n]\right\rvert >n^{\sqrt{2}-1-\epsilon}$") for every
 and for all sufficiently large  .
For an excellent survey of Sidon sets see [5].
- 1
- Harvey Leslie Abbott.
Sidon sets.
Canad. Math. Bull., 33(3):335-341, 1990.
Zbl 0715.11004.
- 2
- Ben Green.
![$ B_h[g]$](http://images.planetmath.org:8080/cache/objects/4771/l2h/img35.png "$ B_h[g]$") sets: The current state of affairs.
http://www.dpmms.cam.ac.uk/˜bjg23/papers/bhgbounds.dvi, 2000.
- 3
- Heini Halberstam and Klaus Friedrich Roth.
Sequences.
Springer-Verlag, second edition, 1983.
Zbl 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.
Zbl 0303.10058.
- 5
- Kevin O'Bryant.
A complete annotated bibliography of work related to Sidon sequences.
Electronic Journal of Combinatorics.
http://arxiv.org/abs/math.NT/0407117.
- 6
- Imre Ruzsa.
An infinite Sidon sequence.
J. Number Theory, 68(1):63-71, 1998.
Available at http://www.math-inst.hu/˜ruzsa/cikkek.html.
|
"Sidon set" is owned by bbukh.
|
|
(view preamble)
Cross-references: even, infinite, subset, finite set, interval, contained, size, solution, equation, sums, natural numbers
This is version 9 of Sidon set, born on 2003-10-11, modified 2004-12-07.
Object id is 4771, canonical name is SidonSet.
Accessed 5470 times total.
Classification:
| AMS MSC: | 11B05 (Number theory :: Sequences and sets :: Density, gaps, topology) | | | 11B34 (Number theory :: Sequences and sets :: Representation functions) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|
