# 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}+\ldots+a_{h}$ has at most $g$ different solutions with $a_{1}\leq\cdots\leq 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 $cF_{h}(n,1)$ for $c=\tfrac{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 $\liminf_{n\to\infty}(n/\log n)^{-1/2}\left\lvert A\cap[1,n]\right\rvert for some constant $C$. 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}$ for some $\epsilon>0$ was known. Only recently Ruzsa[6] used an extremely clever construction to prove the existence of a set $A$ for which $\left\lvert A\cap[1,n]\right\rvert>n^{\sqrt{2}-1-\epsilon}$ for every $\epsilon>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. 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. , 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 SidonSet 2013-03-22 13:59:40 2013-03-22 13:59:40 bbukh (348) bbukh (348) 12 bbukh (348) Definition msc 11B05 msc 11B34 Sidon sequence ErdHosTuranConjecture $B_{h}[g]$ set