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}.