Sidon set

A set of natural numbers is called a Sidon set if allpairwise sums of its elements are distinct. Equivalently, the equation$a+b=c+d$ has only the trivial solution $\{a,b\}=\{c,d\}$ inelements 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]$ setcontained 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, andSzemerédi[4] provedthat in every $n$-element set there is a $B_h[1]$ subset of size atleast $c{F}_h(n,1)$ for $c=\frac{1}{8}{(2h)}^{-6}$. For Sidon setsAbbott[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 everyinfinite Sidon set $A$ we have for some constant $C$. On the otherhand, for a long time no example of a set for which $\left|A\cap [1,n]\right|>n^{1/3+ϵ}$ for some $ϵ>0$ was known. Onlyrecently Ruzsa[6] used an extremelyclever construction to prove the existence of a set $A$ for which$\left|A\cap [1,n]\right|>n^{\sqrt{2}-1-ϵ}$ for every$ϵ>0$ and for all sufficiently large $n$.

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