Difference bases in dihedral groups

Abstract

A subset $B$ of a group $G$ is called a difference basis of $G$ if each element $g\in G$ can be written as the difference $g=a{b}^{-1}$ 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]$. The fraction $ð[G]:=\Delta [G]/\sqrt{|G|}$ is called the difference characteristic of $G$. We prove that for every $n\in \mathbb{N}$ the dihedral group $D_{2n}$ of order $2n$ has the difference characteristic $\sqrt{2}\le ð[D_{2n}]\le \frac{48}{\sqrt{586}}\approx 1.983$. Moreover, if $n\ge 2\cdot 10^{15}$, then $ð[D_{2n}]<\frac{4}{\sqrt{6}}\approx 1.633$. Also we calculate the difference sizes and characteristics of all dihedral groups of cardinality $\le 80$.

5 pages