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+\dotsc+a_h$ has at most $g$ different solutions with $a_1\leq \dotsb\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})$ cite[p. 85]cite:halberstam_sequences, 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. Erdos [3, p. 89] proved that for every infinite Sidon set $A$ we have $\liminf_{n\to\infty}(n/\log n)^{-1/2} \abs{A\cap [1,n]}<C$ for some constant $C$ On the other hand, for a long time no example of a set for which $\abs{A\cap [1,n]}>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 $\abs{A\cap [1,n]}>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.
Zbl 0715.11004.

2

Ben Green.
$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.