On the Diameter of Finite Sidon Sets

Abstract

We prove that the diameter of a Sidon set (also known as a Babcock sequence, Golomb ruler, or $B_2$ set) with $k$ elements is at least $k^2-b{k}^{3/2}-O(k)$ where $b\le 1.96365$, a comparatively large improvement on past results. Equivalently, a Sidon set with diameter $n$ has at most $n^{1/2}+0.98183n^{1/4}+O(1)$ elements. The proof is conceptually simple but very computationally intensive, and the proof uses substantial computer assistance. We also provide a proof of $b\le 1.99058$ that can be verified by hand, which still improves on past results. Finally, we prove that $g$-thin Sidon sets (aka $g$-Golomb rulers) with $k$ elements have diameter at least $g^{-1}{k}^2-(2-\epsilon )g^{-1}{k}^{3/2}-O(k)$, with $\epsilon \ge 0.02g^{-2}$.

16 pages, 1 figure