Skip to main content
2 of 3
added 525 characters in body
Emil Jeřábek
  • 47.8k
  • 4
  • 151
  • 209

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$, 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]$.

Emil Jeřábek
  • 47.8k
  • 4
  • 151
  • 209