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 ${B}_{h}[g]$ sets. A set $A$ is called a ${B}_{h}[g]$ set if for every $n\in \mathbb{N}$ the equation $n={a}_{1}+\mathrm{\dots}+{a}_{h}$ has at most $g$ different solutions with ${a}_{1}\le \mathrm{\cdots}\le {a}_{h}$ being elements of $A$. The Sidon sets are ${B}_{2}[1]$ sets.
Define ${F}_{h}(n,g)$ as the size of the largest ${B}_{h}[g]$ set contained in the interval $[1,n]$. Whereas it is known that ${F}_{2}(n,1)={n}^{1/2}+O({n}^{5/16})$[3, p. 85], no asymptotical results are known for $g>1$ or $h>2$ [2].
Every finite set^{} has a rather large ${B}_{h}[1]$ subset. Komlós, Sulyok, and Szemerédi[4] proved that in every $n$-element set there is a ${B}_{h}[1]$ subset of size at least $c{F}_{h}(n,1)$ for $c=\frac{1}{8}{(2h)}^{-6}$. For Sidon sets Abbott[1] improved that to $c=2/25$. It is not known whether one can take $c=1$.
The infinite^{} ${B}_{h}[g]$ sets are understood even worse. Erdős [3, p. 89] proved that for every infinite Sidon set $A$ we have $$ for some constant $C$. On the other hand, for a long time no example of a set for which $\left|A\cap [1,n]\right|>{n}^{1/3+\u03f5}$ for some $\u03f5>0$ was known. Only recently Ruzsa[6] used an extremely clever construction to prove the existence of a set $A$ for which $\left|A\cap [1,n]\right|>{n}^{\sqrt{2}-1-\u03f5}$ for every $\u03f5>0$ and for all sufficiently large $n$.
For an excellent survey of Sidon sets see [5].
References
- 1 Harvey Leslie Abbott. Sidon sets. Canad. Math. Bull., 33(3):335–341, 1990. http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an=0715.11004Zbl 0715.11004.
- 2 Ben Green. ${B}_{h}[g]$ sets: The current state of affairs. http://www.dpmms.cam.ac.uk/ bjg23/papers/bhgbounds.dvihttp://www.dpmms.cam.ac.uk/ bjg23/papers/bhgbounds.dvi, 2000.
- 3 Heini Halberstam and Klaus Friedrich Roth. Sequences^{}. Springer-Verlag, second edition, 1983. http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an=0498.10001Zbl 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. http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an=0303.10058Zbl 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/0407117http://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.htmlhttp://www.math-inst.hu/ 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 | ${B}_{h}[g]$ set |