Improved Lower Bound for Difference Bases

A difference basis with respect to $n$ is a subset $A\subseteq \mathbb{Z}$ such that $A-A\supseteq \{1,\dots ,n\}$. R'{e}dei and R'{e}nyi showed that the minimum size of a difference basis with respect to $n$ is $(c+o(1))\sqrt{n}$ for some positive constant $c$. The best previously known lower bound on $c$ is $c⩾1.5602\dots$, which was obtained by Leech using a version of an earlier argument due to R'{e}dei and R'{e}nyi. In this note we use Fourier-analytic tools to show that the Leech–R'{e}dei–R'{e}nyi lower bound is not sharp.