<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{center}
\vskip 1cm{\LARGE\bf
Bases in Dihedral and Boolean Groups
}
\vskip 1cm
\large
Volodymyr Gavrylkiv \\
Vasyl Stefanyk Precarpathian National University \\
Department of Algebra and Geometry \\
Shevchenko str., 57 \\
Ivano-Frankivsk \\
Ukraine\\
{\tt vgavrylkiv@gmail.com}\\
\end{center}

\vskip .2in

\begin{abstract} A subset $B$ of a group $G$ is called a {\em basis} of $G$ if $G=B^2$. The smallest
cardinality of a  basis  of $G$ is called the {\em basis size} of $G$. 
We prove upper bounds for  basis sizes of  dihedral and Boolean groups.
We find a lower bound for the basis size of a Boolean group.
We also calculate  basis sizes  for
dihedral and Boolean groups of small orders.
\end{abstract}



\section{Introduction}

A subset $B$ of a group $G$ is called a {\em  basis} of  $G$ if each element $g\in G$ can be written as $g=ab$ for some $a,b\in B$.
The smallest cardinality of a basis of $G$ is called the {\em basis size} of $G$ and is denoted
by $r[G]$. The problem of estimating $r[G]$ for a cyclic group $G$ was first proposed by Schur and various bounds
were obtained by Rohrbach~\cite{Rohrbach}, Moser~\cite{Moser}, St\"{o}hr~\cite{Stohr}, Klotz~\cite{Klotz} and
others. Bases for arbitrary groups were dealt by Rohrbach~\cite{Rohrbach2} and lately by Cherly~\cite{Cherly}, Bertram and Herzog~\cite{BH},
Nathanson~\cite{Nat}, Kozma and Lev \cite{KL}.

A family $\mathcal G$ of finite groups  is {\em well-based} if there exists a constant $c\in\mathbb R_+$ such that
$r[G]\leq c\sqrt{|G|}$ for each $G\in\mathcal G$.
Bertram and Herzog \cite{BH} showed that the families of nilpotent groups, as well as the families of the
alternating and symmetric groups, are well-based. Kozma and Lev \cite{KL} proved  (using the classification of finite simple groups)
that $r[G]\leq \frac{4}{\sqrt{3}}\sqrt{|G|}$ for any finite group $G$. Therefore, the family of all finite groups  is well-based.

The definition of a basis $B$ for a  group $G$ implies that $|G|\le |B|^2$, and hence $r[G]\ge \sqrt{|G|}$.
The fraction $$\delta[G]:=\frac{r[G]}{\sqrt{|G|}}\ge 1$$ is called the {\em basis characteristic} of $G$.

In this paper we shall  evaluate  basis characteristics of dihedral  and Boolean groups.
We recall that the {\em dihedral group} $D_{2n}$ of order $2n$ is the isometry group of a regular $n$-gon. 
The dihedral group $D_{2n}$ contains a normal cyclic subgroup of index $2$. A standard model of a cyclic group of order $n$ is the multiplicative 
group $$C_n=\{z\in\mathbb C:z^n=1\}$$ of $n$-th roots of $1$.  The group $C_n$ is isomorphic to the additive group of the ring $\mathbb Z_n=\mathbb Z/n\mathbb Z$.
A group $G$ is called {\em Boolean} if $g^{-1}=g$ for every $g\in G$. It is well-known that Boolean groups are Abelian and are isomorphic to the
powers of the two-element cyclic group $C_2$.

Kozma and Lev \cite{KL} proved  that each finite group $G$ has the basis characteristic $\delta[G]\le\frac{4}{\sqrt{3}}\approx 2.3094$.
Until now, the best estimate for an upper bound of the basis characteristic was the estimate for the class of cyclic groups:
each cyclic group $C_n$ has the basis characteristic $\delta[C_n]\leq 2$.
We shall show that for dihedral groups this upper bound can be improved to $\delta[D_{2n}]\leq\frac{24}{\sqrt{146}}\approx 1.9862$.
Moreover, if $n\ge 2\cdot 10^{15}$, then  $\delta[D_{2n}]&lt;\frac{4}{\sqrt{6}}\approx 1.633$.
Also we prove that each Boolean group $G$ has the  basis size $\frac{1+\sqrt{8|G|-7}}2\leq r[G]&lt;\frac{3}{\sqrt{2}}\sqrt{|G|}$ and, therefore,
its basis characteristic $\delta[G]&lt;\frac{3}{\sqrt{2}}\approx 2.1213$.

For a class $\mathcal G$ of finite groups the  number
$$\delta[\mathcal G]=\sup_{G\in\mathcal G}\delta[G]$$ is called the {\em basis characteristic}
of the class $\mathcal G$. 

For a real number $x$ we put $$\lceil x\rceil=\min\{n\in\mathbb Z:n\ge x\}\mbox{ and }\lfloor
x\rfloor=\max\{n\in\mathbb Z:n\le x\}.$$


\section{Known results}

In this section we recall some known results on  bases in finite groups. Kozma and Lev
\cite{KL} proved the following fundamental fact.

\begin{theorem}\label{t:KL} Each finite group $G$ has the basis characteristic $\delta[G]\le\frac{4}{\sqrt{3}}$.
\end{theorem}

Bertram and Herzog \cite{BH} proved the following proposition.

\begin{proposition}\label{p:BH} Let $G$
be a finite group. Then
\begin{enumerate}
\item[1)] $r[G]\le|G:H|\cdot r[H]$ for any subgroup $H\subset G$;
\item[2)] $r[G]\le r[G/H]\cdot|H|$ for any normal subgroup $H\subset G$;
\item[3)] $r[G]\le2r[G/H]\cdot r[H]$ for any normal subgroup $H\subset G$;
\item[4)] $r[G]\le |H|+|G:H|-1$ for any subgroup $H\subset G$.
\end{enumerate}
\end{proposition}

In evaluating  basis characteristics of dihedral groups we shall use  difference characteristics of cyclic groups.
A subset $B$ of a group $G$ is called a {\em difference basis} of  $G$ if each element $g\in G$ can be written as $g=xy^{-1}$ for some $x,y\in B$.
The smallest cardinality of a difference basis of $G$ is called the {\em difference size} of $G$ and is denoted
by $\Delta[G]$. The definition of a difference basis $B$ for a  group $G$ implies that $|G|\le |B|^2$, and hence $\Delta[G]\ge \sqrt{|G|}$.
The fraction $$\eth[G]:=\frac{\Delta[G]}{\sqrt{|G|}}\ge1$$ is called the {\em difference characteristic} of $G$.

Difference basis have applications in the study of structure of superextensions of groups, see \cite{BGt, BGN}.

Difference sizes of finite cyclic groups were evaluated in \cite{BG} with the help of  difference sizes
of the order-intervals $[1,n]\cap\mathbb Z$ in the additive group $\mathbb Z$ of integer numbers. 
For a natural number $n\in\mathbb N$ by $\Delta[n]$ we shall denote the difference size of
the order-interval $[1,n]\cap\mathbb Z$ and by $\eth[n]:=\frac{\Delta[n]}{\sqrt{n}}$ its difference characteristic.
The asymptotics of the sequence $(\eth[n])_{n=1}^\infty$ was studied by R\'edei and R\'enyi \cite{RR}, Leech \cite{Leech} 
and Golay \cite{Golay} who eventually proved that $$\sqrt{2+\tfrac4{3\pi}}&lt;
\sqrt{2+\max_{0&lt;\varphi&lt;2\pi}\tfrac{2\sin(\varphi)}{\varphi+\pi}}\le \lim_{n\to\infty}\eth[n]=\inf_{n\in\mathbb N}\eth[n]\le
\eth[6166]=\frac{128}{\sqrt{6166}}&lt;\eth[6]=\sqrt{\tfrac{8}3}.$$

Banakh and Gavrylkiv \cite{BG} applied difference sizes of the order-intervals $[1,n]\cap\mathbb Z$
to give upper bounds for  difference sizes of finite cyclic groups.

\begin{proposition}\label{p:c&lt;n} For every $n\in\mathbb N$ the cyclic group $C_n$ has the difference
size $\Delta[C_n]\le\Delta\big[\lceil\frac{n-1}2\rceil\big]$, which implies that
$$\limsup_{n\to\infty}\eth[C_n]\le\frac1{\sqrt{2}}\inf_{n\in\mathbb N}\eth[n]\le\frac{64}{\sqrt{3083}}&lt;\frac{2}{\sqrt{3}}.$$
\end{proposition}

Banakh and Gavrylkiv \cite{BG} proved the following upper bound for difference characteristics of cyclic groups.

\begin{theorem}\label{t:cyclic} For any $n\in\mathbb N$ the cyclic group $C_n$ has the difference characteristic:
\begin{enumerate}
\item[1)] $\eth[C_n]\le\eth[C_4]=\frac32$;
\item[2)] $\eth[C_n]\le\eth[C_2]=\eth[C_8]=\sqrt{2}$ if $n\ne 4$;
\item[3)] $\eth[C_n]\le\frac{12}{\sqrt{73}}&lt;\sqrt{2}$ if $n\ge 9$;
\item[4)] $\eth[C_n]\le\frac{24}{\sqrt{293}}&lt;\frac{12}{\sqrt{73}}$ if $n\ge 9$ and $n\ne 292$;
\item[5)] $\eth[C_n]&lt;\frac2{\sqrt{3}}$ if $n\ge 2\cdot 10^{15}$.
\end{enumerate}
\end{theorem}

The following Table~\ref{tab:cycl} of difference sizes and characteristics of cyclic groups $C_n$ for $\le 100$ is taken from \cite{BG}.

\begin{table}[ht]
\centering \small
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
\!$n$\!   &amp; \!$\Delta[C_n]$\! &amp; $\eth[C_n]$&amp;$n$   &amp; \!$\Delta[C_n]$\! &amp; $\eth[C_n]$&amp;$n$   &amp; \!$\Delta[C_n]$\! &amp; $\eth[C_n]$&amp;$n$   &amp; \!$\Delta[C_n]$\! &amp; $\eth[C_n]$\\
\hline
1 &amp; 1 &amp; 1            &amp;26 &amp; 6 &amp; 1.1766\ldots\!\! &amp; 51 &amp; 8 &amp; 1.1202\ldots\!\!&amp; 76 &amp; 10 &amp; 1.1470\ldots\\
2 &amp; 2 &amp;1.4142\ldots  &amp;27 &amp; 6 &amp; 1.1547\ldots\!\! &amp; 52 &amp; 9 &amp; 1.2480\ldots\!\!&amp; 77 &amp; 10 &amp; 1.1396\ldots\!\!\\
3 &amp; 2 &amp;1.1547\ldots  &amp;28 &amp; 6 &amp; 1.1338\ldots\!\! &amp; 53 &amp; 9 &amp; 1.2362\ldots\!\!&amp; 78 &amp; 10 &amp; 1.1322\ldots\!\!\\
4 &amp; 3 &amp;1.5           &amp;29 &amp; 7 &amp; 1.2998\ldots\!\! &amp; 54 &amp; 9 &amp; 1.2247\ldots\!\!&amp; 79 &amp; 10 &amp; 1.1250\ldots\!\!\\
5 &amp; 3 &amp;1.3416\ldots  &amp;30 &amp; 7 &amp; 1.2780\ldots\!\! &amp; 55 &amp; 9 &amp; 1.2135\ldots\!\!&amp; 80 &amp; 11 &amp; 1.2298\ldots\!\!\\
6 &amp; 3 &amp; 1.2247\ldots &amp;31 &amp; 6 &amp; 1.0776\ldots\!\! &amp; 56 &amp; 9 &amp; 1.2026\ldots\!\!&amp; 81 &amp; 11 &amp; 1.2222\ldots\!\!\\
7 &amp; 3 &amp; 1.1338\ldots &amp;32 &amp; 7 &amp; 1.2374\ldots\!\! &amp; 57 &amp; 8 &amp; 1.0596\ldots\!\!&amp; 82 &amp; 11 &amp; 1.2147\ldots\!\!\\
8 &amp; 4 &amp; 1.4142\ldots &amp;33 &amp; 7 &amp; 1.2185\ldots\!\! &amp; 58 &amp; 9 &amp; 1.1817\ldots\!\!&amp; 83 &amp; 11 &amp; 1.2074\ldots\!\!\\
9 &amp; 4 &amp; 1.3333\ldots  &amp;34 &amp; 7 &amp; 1.2004\ldots\!\! &amp; 59 &amp; 9 &amp; 1.1717\ldots\!\!&amp; 84 &amp; 11 &amp; 1.2001\ldots\!\!\\
10 &amp; 4 &amp; 1.2649\ldots &amp;35 &amp; 7 &amp; 1.1832\ldots\!\! &amp; 60 &amp; 9 &amp; 1.1618\ldots\!\!&amp; 85 &amp; 11 &amp; 1.1931\ldots\!\!\\
11 &amp; 4 &amp; 1.2060\ldots &amp;36 &amp; 7 &amp; 1.1666\ldots\!\! &amp; 61 &amp; 9 &amp; 1.1523\ldots\!\!&amp; 86 &amp; 11 &amp; 1.1861\ldots\!\!\\
12 &amp; 4 &amp; 1.1547\ldots &amp;37 &amp; 7 &amp; 1.1507\ldots\!\! &amp; 62 &amp; 9 &amp; 1.1430\ldots\!\!&amp; 87 &amp; 11 &amp; 1.1793\ldots\!\!\\
13 &amp; 4 &amp; 1.1094\ldots &amp;38 &amp; 8 &amp; 1.2977\ldots\!\! &amp; 63 &amp; 9 &amp; 1.1338\ldots\!\!&amp; 88 &amp; 11 &amp; 1.1726\ldots\!\!\\
14 &amp; 5 &amp; 1.3363\ldots &amp;39 &amp; 7 &amp; 1.1208\ldots\!\! &amp; 64 &amp; 9 &amp; 1.125\!\!       &amp; 89 &amp; 11 &amp; 1.1659\ldots\!\!\\
15 &amp; 5 &amp; 1.2909\ldots &amp;40 &amp; 8 &amp; 1.2649\ldots\!\! &amp; 65 &amp; 9 &amp; 1.1163\ldots\!\!&amp; 90 &amp; 11 &amp; 1.1595\ldots\!\!\\
16 &amp; 5 &amp; 1.25         &amp;41 &amp; 8 &amp; 1.2493\ldots\!\! &amp; 66 &amp; 10 &amp; 1.2309\ldots\!\!&amp; 91 &amp; 10 &amp; 1.0482\ldots\!\!\\
17 &amp; 5 &amp; 1.2126\ldots &amp;42 &amp; 8 &amp; 1.2344\ldots\!\! &amp; 67 &amp; 10 &amp; 1.2216\ldots\!\!&amp; 92 &amp; 11 &amp; 1.1468\ldots\!\!\\
18 &amp; 5 &amp; 1.1785\ldots &amp;43 &amp; 8 &amp; 1.2199\ldots\!\! &amp; 68 &amp; 10 &amp; 1.2126\ldots\!\!&amp; 93 &amp; 12 &amp; 1.2443\ldots\!\!\\
19 &amp; 5 &amp; 1.1470\ldots &amp;44 &amp; 8 &amp; 1.2060\ldots\!\! &amp; 69 &amp; 10 &amp; 1.2038\ldots\!\!&amp; 94 &amp; 12 &amp; 1.2377\ldots\!\!\\
20 &amp; 6 &amp; 1.3416\ldots &amp;45 &amp; 8 &amp; 1.1925\ldots\!\! &amp; 70 &amp; 10 &amp; 1.1952\ldots\!\!&amp; 95 &amp; 12 &amp; 1.2311\ldots\!\!\\
21 &amp; 5 &amp; 1.0910\ldots &amp;46 &amp; 8 &amp; 1.1795\ldots\!\! &amp; 71 &amp; 10 &amp; 1.1867\ldots\!\!&amp; 96 &amp; 12 &amp; 1.2247\ldots\!\!\\
22 &amp; 6 &amp; 1.2792\ldots &amp;47 &amp; 8 &amp; 1.1669\ldots\!\! &amp; 72 &amp; 10 &amp; 1.1785\ldots\!\!&amp; 97 &amp; 12 &amp; 1.2184\ldots\!\!\\
23 &amp; 6 &amp; 1.2510\ldots &amp;48 &amp; 8 &amp; 1.1547\ldots\!\! &amp; 73 &amp; 9 &amp; 1.0533\ldots\!\!&amp; 98 &amp; 12 &amp; 1.2121\ldots\!\!\\
24 &amp; 6 &amp; 1.2247\ldots &amp;49 &amp; 8 &amp; 1.1428\ldots\!\! &amp; 74 &amp; 10 &amp; 1.1624\ldots\!\!&amp; 99 &amp; 12 &amp; 1.2060\ldots\!\!\\
25 &amp; 6 &amp; 1.2          &amp;50 &amp; 8 &amp; 1.1313\ldots\!\! &amp; 75 &amp; 10 &amp; 1.1547\ldots\!\!&amp; 100 &amp; 12 &amp; 1.2\\
\hline
\end{tabular}
\caption{Difference sizes and characteristics of cyclic groups $C_n$ for $n \le 100$.}\label{tab:cycl}
\end{table}


\section{Basis sizes and characteristics of  dihedral groups}

In this section we shall  evaluate  basis sizes and characteristics of dihedral  groups.
The following proposition yields some upper bounds for the basis size of  a dihedral group.

\begin{proposition}\label{p:dihedr} For any numbers $n,m\in\mathbb N$ the dihedral group
$D_{2nm}$ has the basis size
\begin{enumerate}
\item[1)] $r[D_{2nm}]\le 2n\cdot r[C_m]$;
\item[2)] $r[D_{2nm}]\le r[D_{2n}]\cdot m$;
\item[3)] $r[D_{2nm}]\le2r[D_{2n}]\cdot r[C_m]$.
\end{enumerate}
\end{proposition}

\begin{proof} It is well-known that the dihedral group $D_{2nm}$ contains a normal cyclic subgroup of order $nm$, which can be identified
with the cyclic group $C_{nm}$. The subgroup $C_m\subset C_{nm}$ is normal in $D_{2mn}$ and the quotient group $D_{2mn}/C_m$ is
isomorphic to $D_{2n}$. Applying Proposition~\ref{p:BH}(1-3), we obtain the desired upper bounds.
\end{proof}

\begin{theorem}\label{t:dihedral} For any $n\in\mathbb N$ the dihedral group $D_{2n}$ has the basis size
$r[D_{2n}]\le 2\Delta[C_n]$.
\end{theorem}

\begin{proof}  It is well-known that the group $D_{2n}$ contains a cyclic
subgroup $C_n$ and an element $s\in D_{2n}\setminus C_n$ such that $s=s^{-1}$ and $sxs=x^{-1}$ for all $x\in C_n$.
Fix a difference basis $B\subset C_{n}$ of cardinality $|B|=\Delta[C_{n}]$. Therefore, $BB^{-1}=C_n$ and $sBs=B^{-1}$.
We claim that $B^{-1}\cup sB$ is a basis. Indeed,
$$(B^{-1}\cup sB)(B^{-1}\cup sB)=B^{-1}B^{-1}\cup B^{-1}sB\cup sBB^{-1}\cup sBsB\supset s(BB^{-1})\cup (sBs)B$$
$$=sC_n\cup B^{-1}B=(D_{2n}\setminus C_n)\cup BB^{-1}=(D_{2n}\setminus C_n)\cup C_n=D_{2n}.$$
Therefore, $r[D_{2n}]\leq |B^{-1}\cup sB|=2|B|=2\Delta[C_n]$.
\end{proof}

In Table~\ref{tab:d} we present the results of computer calculations of
basis sizes and characteristics of dihedral groups of order $\le 80$.

\begin{table}[ht]
\centering 
\begin{tabular}{|c|c|c|c||c|c|c|c|}
\hline
$2n$   &amp;  $r[D_{2n}]$ &amp;$2\Delta[C_n]$   &amp; \!$\delta[D_{2n}]$ &amp; $2n$  &amp; $r[D_{2n}]$ &amp;$2\Delta[C_n]$   &amp; \!$\delta[D_{2n}]$\\
\hline
2 &amp;  2 &amp; 2 &amp; 1.4142\ldots\!\! &amp; 42 &amp;  9 &amp; 10 &amp; 1.3887\ldots\!\!\\
4 &amp;  3 &amp; 4 &amp; 1.5\!\! &amp; 44 &amp; 9 &amp;  12 &amp; 1.3568\ldots\!\!\\
6 &amp;  3 &amp; 4 &amp; 1.2247\ldots\!\! &amp; 46 &amp;  9 &amp; 12 &amp; 1.3269\ldots\!\!\\
8 &amp;  4 &amp; 6 &amp; 1.4142\ldots\!\! &amp; 48 &amp;  9 &amp; 12 &amp; 1.2990\ldots\!\!\\
10 &amp; 4 &amp; 6 &amp; 1.2649\ldots\!\! &amp; 50 &amp; 9  &amp; 12 &amp; 1.2727\ldots\!\!\\
12 &amp; 5 &amp; 6 &amp; 1.4433\ldots\!\! &amp; 52 &amp;  10 &amp; 12 &amp; 1.3867\ldots\!\!\\
14 &amp; 5 &amp;  6 &amp; 1.3363\ldots\!\! &amp; 54 &amp;  10 &amp; 12 &amp; 1.3608\ldots\!\!\\
16 &amp; 5 &amp;  8 &amp; 1.25\!\! &amp; 56 &amp; 10 &amp;  12 &amp; 1.3363\ldots\!\!\\
18 &amp; 6 &amp;  8 &amp; 1.4142\ldots\!\! &amp; 58 &amp;  10 &amp; 14 &amp; 1.3130\ldots\!\!\\
20 &amp; 6 &amp; 8 &amp; 1.3416\ldots\!\! &amp; 60 &amp;  10 &amp; 14 &amp; 1.2909\ldots\!\!\\
22 &amp; 7 &amp; 8 &amp; 1.4924\ldots\!\! &amp; 62 &amp;  10 &amp; 12 &amp; 1.2700\ldots\!\!\\
24 &amp; 6 &amp; 8 &amp; 1.2247\ldots\!\! &amp; 64 &amp;  11 &amp; 14 &amp; 1.375\!\!\\
26 &amp; 7 &amp; 8 &amp; 1.3728\ldots\!\! &amp; 66 &amp;  10 &amp; 14 &amp; 1.2309\ldots\!\!\\
28 &amp; 7 &amp; 10 &amp; 1.3228\ldots\!\! &amp; 68 &amp; 11  &amp; 14 &amp; 1.3339\ldots\!\!\\
30 &amp; 7 &amp; 10 &amp; 1.2780\ldots\!\! &amp; 70 &amp; 10  &amp; 14 &amp; 1.1952\ldots\!\!\\
32 &amp; 7 &amp; 10 &amp; 1.2374\ldots\!\! &amp; 72 &amp; 11  &amp; 14 &amp; 1.2963\ldots\!\!\\
34 &amp; 8 &amp; 10 &amp; 1.3719\ldots\!\! &amp; 74 &amp; 11 &amp; 14 &amp; 1.2787\ldots\!\!\\
36 &amp; 8 &amp; 10 &amp; 1.3333\ldots\!\! &amp; 76 &amp;  12 &amp; 16 &amp; 1.3764\ldots\!\!\\
38 &amp; 8 &amp; 10 &amp; 1.2977\ldots\!\! &amp; 78  &amp; 11 &amp; 14 &amp; 1.2455\ldots\!\!\\
40 &amp; 8 &amp; 12 &amp; 1.2649\ldots\!\! &amp; 80 &amp;  12 &amp; 16 &amp; 1.3416\ldots\!\!\\
\hline
\end{tabular}
\caption{Basis sizes and characteristics of dihedral groups $D_{2n}$ for $2n \le 80$.}\label{tab:d}
\end{table}

\begin{theorem}\label{t:max} Let $D_{2n}$ be a dihedral group of order $2n$. Then for any 
number $n\in \mathbb N$, the basis characteristic of the dihedral group is $\delta[D_{2n}]\leq\frac{24}{\sqrt{146}}$. 
If $n\ge 2\cdot 10^{15}$, then  $\delta[D_{2n}]&lt;\frac{4}{\sqrt{6}}$.
\end{theorem}

\begin{proof}
It is well-known that the dihedral group $D_{2n}$ contains a normal cyclic subgroup of order $n$, which can be identified with the
cyclic group $C_{n}$. Applying Theorem~\ref{t:dihedral}, we obtain the upper bound
$$\delta[D_{2n}]=\frac{r[D_{2n}]}{\sqrt{2n}}\le \frac{2\Delta[C_n]}{\sqrt{2n}} = \sqrt{2}\cdot\eth[C_{n}].$$
If $n\ge 9$, then  using part $3$ of Theorem~\ref{t:cyclic}, we get $\eth[C_n]\le\frac{12}{\sqrt{73}}$. Therefore,
$$\delta[D_{2n}]\leq\sqrt{2}\cdot\frac{12}{\sqrt{73}}=\frac{24}{\sqrt{146}}.$$

Analyzing the data from Table~\ref{tab:d}, one can check that $\delta[D_{2n}]\le \frac{24}{\sqrt{146}}\approx 1.9863$ for all $n\le 8$.

If $n\ge 2\cdot 10^{15}$, then using part $5$ of Theorem~\ref{t:cyclic}, we get $\eth[C_{n}]&lt;\frac{2}{\sqrt{3}}$, and hence
$$\delta[D_{2n}]\leq\sqrt{2}\cdot\eth[C_{n}]&lt;\frac{4}{\sqrt{6}}.$$
\end{proof}

The results of computer calculations given in Table~\ref{tab:d} and Theorem \ref{t:max} imply the following lower and upper bounds for the
basis characteristic of the class $\mathsf{Dihedral}$ of dihedral groups.

\begin{proposition}\label{p:diff-d} The class $\mathsf{Dihedral}$ of dihedral groups has the basis characteristic
$$1.5=\frac{3}{\sqrt{4}}=\delta[D_{4}]\le\delta[\mathsf{Dihedral}]\le \frac{24}{\sqrt{146}}\approx 1.9863.$$
\end{proposition}

\begin{proof} Theorem \ref{t:max} yields the upper bound
$$\delta[\mathsf{Dihedral}]=\sup_{n\in\mathbb N}\delta[D_{2n}]\le \frac{24}{\sqrt{146}}.$$

On the other hand, the basis size $r[D_{4}]=3$ of the dihedral group $D_{4}$ witnesses that
$$1.5=\delta[D_{4}]\le\delta[\mathsf{Dihedral}].$$

\end{proof}

\begin{question} Is
$\delta[\mathsf{Dihedral}]=\delta[D_{4}]=1.5$?
\end{question}


\section{Basis sizes and characteristics of Boolean groups}

In this section we evaluate  basis sizes and characteristics of finite Boolean groups.
A group $G$ is called {\em Boolean} if $g^{-1}=g$ for every $g\in G$. It
is well-known that Boolean groups are Abelian and are isomorphic to the
powers of the two-element cyclic group $C_2$. Let $\mathsf{Boolean}$  denote the
class of finite Boolean groups and let
$\mathsf{Boolean_0}:=\{G\in\mathsf{Boolean}:\sqrt{|G|}\in\mathbb N\}$.

We start with  the lower bound for $r[G]$.

\begin{theorem}\label{t:lower} Each Boolean group $G$ has $r[G]\ge \frac{1+\sqrt{8|G|-7}}2$.
\end{theorem}

\begin{proof} Take a basis $B\subset G$ of cardinality $|B|=r[G]$ and
consider the surjective map $\xi:B\times B\to G$, $\xi:(x,y)\mapsto xy$.
Observe that for the unit $e$ of the group $G$ the preimage $\xi^{-1}(e)$
coincides with the diagonal $\{(x,y)\in B\times B:x=y\}$ of the square $B\times B$,
and hence has cardinality $|\xi^{-1}(e)|=|B|$. Observe also that for any element
$g\in G\setminus\{e\}$ and any $(x,y)\in \xi^{-1}(g)$, we get $x\neq y$ and $yx=xy=g$, which implies that $|\xi^{-1}(g)|\ge 2$.
Then
$$|B|^2=|B\times B|=|\xi^{-1}(e)|+\sum_{g\in G\setminus\{e\}}|\xi^{-1}(g)|\ge |B|+2(|G|-1).$$
Therefore, $|B|^2-|B|-2(|G|-1)\geq0$, and hence
$r[G]=|B|\ge \frac{1+\sqrt{1+8(|G|-1)}}2=\frac{1+\sqrt{8|G|-7}}2$.
\end{proof}

\begin{theorem}\label{t:Boolean} Each finite Boolean group $G$ has
$$\frac{1+\sqrt{8|G|-7}}2\le r[G]&lt;
\begin{cases}
2\sqrt{|G|}, &amp; \text{if $G\in\mathsf{Boolean_0}$};\\
\frac3{\sqrt{2}}\sqrt{|G|}, &amp; \text{otherwise}.
\end{cases}
$$
\end{theorem}

\begin{proof} The lower bound $\frac{1+\sqrt{8|G|-7}}2\le r[G]$
follows from Theorem~\ref{t:lower}.

The group $G$, being Boolean, is isomorphic to $(C_2)^n$ for some $n\ge
0$. Let $k=\lfloor\frac n2\rfloor$ and find a subgroup $H\subset G$ of
order $2^k$. By Proposition~\ref{p:BH}(4), $r[G]\le |H|+|G/H|-1$.

If $G\in\mathsf{Boolean_0}$, then $n=2k$ is even and $$r[G]\le
|H|+|G/H|-1=2^k+2^k-1&lt;2\sqrt{2^{2k}}=2\sqrt{|G|}.$$
If $G\notin\mathsf{Boolean_0}$, then $n=2k+1$ is odd and$$r[G]\le
|H|+|G/H|-1=
2^k+2^{k+1}-1&lt;\frac3{\sqrt{2}}\sqrt{2^{2k+1}}=\tfrac{3}{\sqrt{2}}\sqrt{|G|}.
$$
\end{proof}

In the following Table~\ref{tab:bool} we present the results of computer calculations of basis sizes and characteristics 
of Boolean groups $(C_2)^n$ for $n\le 6$. In this table  $$lb[G]:=\left\lceil\frac{1+\sqrt{8|G|-7}}2\right\rceil\mbox{ \ and \ }
ub[G]:=\left\lfloor\sqrt{\frac{9|G|}{2}}\right\rfloor$$
are the lower and upper bounds given in Theorems~\ref{t:lower} and \ref{t:Boolean}.

\begin{table}[ht]
\centering 
\begin{tabular}
{|c|c|c|c|c|c|c|}
\hline
$G$  &amp; $C_2$ &amp; $(C_2)^2$ &amp; $(C_2)^3$ &amp; $(C_2)^4$ &amp; $(C_2)^5$ &amp; $(C_2)^6$\\
\hline
$lb[G]$ &amp; 2 &amp; 3 &amp; 5 &amp; 6 &amp; 9 &amp; 12\\
$r[G]$  &amp; 2 &amp; 3 &amp; 5 &amp; 6 &amp; 10 &amp; 14 \\
$ub[G]$ &amp; 3 &amp; 4 &amp; 6 &amp; 8 &amp; 12 &amp; 16 \\
$\delta[G]$ &amp; 1.4142\ldots &amp; 1.5 &amp; 1.7677\ldots &amp; 1.5 &amp; 1.7677\ldots &amp; 1.75\\
\hline
\end{tabular}
\caption{Basis sizes and characteristics of Boolean groups $(C_2)^n$ for $n\le 6$.}\label{tab:bool}
\end{table}

Theorem~\ref{t:Boolean} implies the following corollaries.

\begin{corollary} The class $\mathsf{Boolean}$ of finite Boolean groups has the basis characteristic
$$
1.7677...=\frac{5}{\sqrt{8}}=\delta[(C_2)^3]\le\delta[\mathsf{Boolean}]\le
\frac3{\sqrt{2}}=2.1213...
$$
\end{corollary}

\begin{proof} The upper bound $\delta[\mathsf{Boolean}]\le\frac3{\sqrt{2}}$
follows from Theorem~\ref{t:Boolean} and the lower bound $\delta[\mathsf{Boolean}]\ge\delta[(C_2)^3]=\frac{5}{\sqrt{8}}$
follows from the known value $r[(C_2)^3]=5$.
\end{proof}

\begin{corollary} The class $\mathsf{Boolean_0}$  has the basis characteristic
$$
1.75=\frac{14}{\sqrt{64}}=\delta[(C_2)^6]\le\delta[\mathsf{Boolean_0}]\le2
$$
\end{corollary}

\begin{proof} The upper bound $\delta[\mathsf{Boolean_0}]\le 2$
follows from Theorem~\ref{t:Boolean} and the lower bound $\delta[\mathsf{Boolean_0}]\ge\delta[(C_2)^6]=1.75$
follows from the known value $r[(C_2)^6]=14$.
\end{proof}


\begin{thebibliography}{9}

\bibitem{BGt} T.~Banakh and V.~Gavrylkiv, Algebra in the superextensions of twinic groups, {\em Dissertationes Math.} {\bf 473} (2010), 3--74.

\bibitem{BG} T.~Banakh and V.~Gavrylkiv, Difference bases in cyclic groups,  preprint, 2017, \\ \url{https://arxiv.org/abs/1702.02631}.

\bibitem{BGN} T.~Banakh, V.~Gavrylkiv, and O.~Nykyforchyn, Algebra in
superextension of groups, I: zeros and commutativity, {\em Algebra Discrete Math.} {\bf 3} (2008), 1--29.

\bibitem{BH} E.~A.~Bertram and M.~Herzog, On medium-size subgroups and bases of finite groups,
{\em J. Combin. Theory Ser. A} {\bf 57} (1991), 1--14.

\bibitem{Cherly} J.~Cherly, On complementary sets of group elements, {\em Arch. Math.} {\bf 35}
(1980), 313--318.

\bibitem{Golay} M.~Golay, Notes on the representation of $1,\,2,\ldots,n$ by differences, {\em J. London Math. Soc.} {\bf 4} (1972) 729--734.

\bibitem{Klotz} W.~Klotz, Eine obere Schranke f\"{u}r die Reichweite einer Extremalbasis zweiter Ordnung,
{\em  J. Reine Angew. Math.} {\bf 238} (1969), 161--168.

\bibitem{KL} G.~Kozma and A.~Lev, Bases and decomposition numbers of
finite groups, {\em Arch. Math. (Basel)} {\bf 58} (1992), 417--424.

\bibitem{Leech} J.~Leech, On the representation of $1,2,\ldots,n$ by
differences, {\em J. London Math. Soc.} {\bf 31} (1956), 160--169.

\bibitem{Moser} L.~Moser, On the representation of $1,2,\ldots,n$ by sums, {\em Acta Arith.} {\bf 6} (1960), 11--13.

\bibitem{Nat} M.~B.~Nathanson, On a problem of Rohrbach for finite groups, {\em J. Number Theory} {\bf 41} (1992), 69--76.

\bibitem{RR} L.~R\'edei and A.~R\'enyi, On the representation of the
numbers $1,2,\dots,N$ by means of differences, {\em Mat. Sbornik N.S.}
{\bf 24} (1949), 385--389.

\bibitem{Rohrbach} H.~Rohrbach, Ein Beitrag zur additiven Zahlentheorie, {\em Math. Z.} {\bf 42} (1937), 1--30.

\bibitem{Rohrbach2} H.~Rohrbach, Anwendung eines Satzes der additiven Zahlentheorie auf eine gruppentheoretische
Frage, {\em Math. Z.} {\bf 42} (1937), 538--542.

\bibitem{Stohr} A.~St\"{o}hr,  Gel\"{o}ste und ungel\"{o}ste Fragen \"{u}ber Basen der nat\"{u}rlichen Zahlenreihe,
I, {\em J. Reine Angew. Math.} {\bf 194} (1955), 40--65.

\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 
2010 \textit{Mathematics Subject Classification}: Primary 05B10; Secondary 05E15, 20D60.

\noindent 
\textit{Keywords:}  dihedral group, Boolean group, basis, basis size, basis characteristic.
 
\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received  April 18 2017;
revised versions received   April 20 2017; June 24 2017; June 26 2017; 
July 6 2017.
Published in {\it Journal of Integer Sequences}, July 31 2017.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}

                                                                                

</pre></body></html>