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+ϵ}$ for some $ϵ>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-ϵ}$ for every $ϵ>0$ and for all sufficiently large $n$.

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

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