If I have a range from 0-N (0,1,2,3...N) and I want to cover that set with some number of Sidon sets, is there a tighter bound than N for how many sets I would need.
For instance: 0,1,2,3 can be split into Sidon Sets {{0,1,2}, {3}}
clearly any range 0-N can be made into sets {{0},{1} ...{N}} so the limit is less than or equal to N.
Is there a known bound?
The minimal number of such Sidon sets is $(1+o(1))\sqrt N$.
On the one hand, any Sidon set in $[0,N]$ has size at most $\sqrt N+O(\sqrt[4]N)$ (due to Erdős and Turán), hence the minimal number of Sidon sets that cover $[0,N]$ is at least $\sqrt N+O(\sqrt[4]N)$. More precisely, Lindström’s bound implies that one needs at least $\sqrt N-\sqrt[4]N$ sets.
For the upper bound, observe that if $S$ is any Sidon set, then the translates of $S$ are nearly disjoint: $|(S+a)\cap(S+b)|\le1$ for any $a\ne b$. (Sidon sets are Golomb rulers, but if $u\ne v$ belong to $(S+a)\cap(S+b)$, then $u-v$ is the difference of two different pairs of elements of $S$.) Thus, if $|S|=s$, then the $s$ sets $S-a$ for $a\in S$ have only the element $0$ in their pairwise intersections, and as such cover $s^2-s+1$ distinct elements.
This holds not just for Sidon sets in $\mathbb Z$ (where we have an issue that some elements covered by the translates stick out of $[0,N]$), but also for Sidon sets in any finite abelian group. In particular, let $p\sim\sqrt N$ be the least odd prime power such that $m=p^2+p+1>N$, and let $S$ be a Sidon set of size $p+1$ in the cyclic group $C_m$, constructed by Singer. Then the $p+1$ translates $S-a$ for $a\in S$ (computed in $C_m$, i.e., modulo $m$) cover all $(p+1)^2-(p+1)+1=m$ elements of $C_m$. If we identify $C_m$ with $[0,m)$, then these sets are also Sidon sets in $\mathbb Z$, and they cover $[0,m)\supseteq[0,N]$.
