\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}]<\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]<\frac{3}{\sqrt{2}}\sqrt{|G|}$ and, therefore,
its basis characteristic $\delta[G]<\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}}<
\sqrt{2+\max_{0<\varphi<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}}<\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