## Archive for July 13th, 2012

### What are dense Sidon subsets of {1,2,…,n} like?

July 13, 2012

The short answer if you don’t feel like reading a post with some actual mathematics in it is that I don’t know.

Now for the longer answer. A subset $A$ of $\{1,2,\dots,n\}$ is called a Sidon set if the only solutions of the equation $a+b=c+d$ with $a,b,c,d\in A$ are the trivial ones with $a=c$ and $b=d$ or $a=d$ and $b=c$. Since the number of pairs $a\leq b$ with $a,b\in A$ is $|A|(|A|+1)/2$ and $2\leq a+b\leq 2n$ whenever $a,b\in A$, it is trivial that if $A$ is a Sidon set, then $|A|(|A|+1)/2\leq 2n$, which gives an upper bound for $|A|$ of around $2\sqrt{n}$.
(more…)