Difference bases in cyclic groups

Abstract

A subset $B$ of an Abelian group $G$ is called a difference basis of $G$ if each element $g\in G$ can be written as the difference $g=a-b$ of some elements $a,b\in B$. The smallest cardinality $|B|$ of a difference basis $B\subset G$ is called the difference size of $G$ and is denoted by $\Delta [G]$. We prove that for every $n\in \mathbb{N}$ the cyclic group $C_n$ of order $n$ has difference size $\frac{1+\sqrt{4|n|-3}}{2}\le \Delta [C_n]\le \frac{3}{2}\sqrt{n}$. If $n\ge 9$ (and $n\ge 2\cdot 10^{15}$), then $\Delta [C_n]\le \frac{12}{\sqrt{73}}\sqrt{n}$ (and $\Delta [C_n]<\frac{2}{\sqrt{3}}\sqrt{n}$). Also we calculate the difference sizes of all cyclic groups of cardinality $\le 100$.

11 pages