# Training quantum measurement devices to discriminate unknown non-orthogonal
quantum states

D. Concha<EMAIL_ADDRESS>Instituto Milenio de Investigación en Óptica y
Departamento de Física, Universidad de Concepción, casilla 160-C, Concepción,
Chile  L. Pereira  Instituto de Física Fundamental IFF-CSIC, Calle Serrano
113b, Madrid 28006, Spain  L. Zambrano  Instituto Milenio de Investigación en
Óptica y Departamento de Física, Universidad de Concepción, casilla 160-C,
Concepción, Chile  A. Delgado  Instituto Milenio de Investigación en Óptica y
Departamento de Física, Universidad de Concepción, casilla 160-C, Concepción,
Chile

###### Abstract

Here, we study the problem of decoding information transmitted through unknown
quantum states. We assume that Alice encodes an alphabet into a set of
orthogonal quantum states, which are then transmitted to Bob. However, the
quantum channel that mediates the transmission maps the orthogonal states into
non-orthogonal states, possibly mixed. If an accurate model of the channel is
unavailable, then the states received by Bob are unknown. In order to decode
the transmitted information we propose to train a measurement device to
achieve the smallest possible error in the discrimination process. This is
achieved by supplementing the quantum channel with a classical one, which
allows the transmission of information required for the training, and
resorting to a noise-tolerant optimization algorithm. We demonstrate the
training method in the case of minimum-error discrimination and show that it
achieves error probabilities very close to the optimal one. In particular, in
the case of two unknown pure states our proposal approaches the Helstrom
bound. A similar result holds for a larger number of states in higher
dimensions. We also show that a reduction of the search space, which is used
in the training process, leads to a considerable reduction in the required
resources. Finally, we apply our proposal to the case of the dephasing channel
reaching an accurate value of the optimal error probability.

###### pacs:

03.67.-a, 0365.-w, 02.60.Pn

##  I Introduction

The states of quantum systems exhibit properties that distinguish them from
their classical counterparts. Unknown quantum states cannot be perfectly and
deterministically copied [1] and entangled states achieve correlations without
classical equivalence [2]. These are deeply related to the impossibility of
discriminating non-orthogonal quantum states. If this were the case, then
unknown quantum states could be perfectly and deterministically copied and
entangled states could be used to implement super luminal communications [3].
Consequently, the discrimination of non-orthogonal quantum states has become
an important research subject due to its implications for the foundations of
the quantum theory [4, 5] and quantum communications [6, 7].

The discrimination of quantum states can be naturally stated in the context of
two parties that attempt to communicate: Alice encodes information
representing the letters of an alphabet through a set of orthogonal pure
quantum states, which transmits through a communication channel. The channel
transforms the orthogonal states into a new set of states, which might become
non-orthogonal and mixed. Bob then receives them and performs a generalized
quantum measurement to discriminate the states and to retrieve the information
encoded by Alice. Both parties are assumed to know the generation
probabilities of the orthogonal states and the set of non-orthogonal states in
advance. To decode the transmitted information, the parties agree on a figure
of merit which is subsequently optimized to obtain the best single-shot
generalized quantum measurement. This leads to several discrimination
strategies such as minimum-error discrimination [8, 9, 10], pretty-good
measurement, unambiguous discrimination [11, 12, 13, 14], maximum-confidence
discrimination [15, 16], and fixed-rate of inconclusive result [17, 18].
Various discrimination strategies have already been experimentally
demonstrated [19, 20, 21, 22, 23, 24]. The typical figures of merit for state
discrimination are functions of the generation probabilities and the
conditional probabilities between the states transmitted by Alice and Bob’s
measurement outcomes, which in turn also depend on the generalized measurement
used by Bob and the states received by Bob. Thereby, optimizing any figure of
merit and choosing the best generalized measurement become difficult problems.
This imposes the use of numerical optimization techniques such as semidefinite
programming (SDP). Recently, the distinguishability between two known families
of non-orthogonal quantum states has been studied by training quantum circuits
through neural networks [25, 26]. Quantum state discrimination has also been
studied in the context of unknown quantum states. In this case, the
communication channel connecting Alice and Bob maps the states transmitted by
Alice into a new set of states that both parties are unaware of. An example of
this situation is free-space quantum communication [27, 28, 29, 30, 31], where
information is encoded into states of light and transmitted through the
atmosphere. This exhibits local and temporal variations in the refractive
index, which can greatly modify the state of light and makes it difficult to
characterize the transmitted states. Given that neither Alice nor Bob have
access to the density matrices of the communicated states, standard approaches
can not be applied. This problem been studied assuming that the unknown states
can be stored in quantum registers that control the action of a measurement
device [32, 33, 34, 35, 36, 37], or programmable discriminator.

In this article, we propose the training of a measurement device to optimally
discriminate a set of unknown non-orthogonal quantum states. We assume that
the action of this device is defined by a large set of control parameters,
such that a set of parameter values corresponds to the realization of a
positive operator-valued measure (POVM). Given a fixed figure of merit for the
discrimination process, it is iteratively optimized in the space of the
control parameters. The optimization is driven by a gradient-free stochastic
optimization algorithm [38, 39], which approximates the gradient by a finite
difference of the figure of merit. This requires at each iteration evaluations
of the figure of merit at two different points in the control parameter space.
Thereby, the training is driven by experimentally acquired data. Furthermore,
stochastic optimization methods have been shown to be robust against noise
[40], so they are a standard choice in experimental contexts. The training of
the measurement device is carried out until approaching the optimal value of
the figure of merit within a prescribed tolerance.

We illustrate our approach by studying minimum-error discrimination, where the
figure of merit is the average retrodiction error. This figure of merit can be
experimentally evaluated if, during the training step, Alice communicates the
labels of the states that she sent to Bob through a classical channel.
Minimum-error discrimination plays key role in quantum imaging [41], quantum
reading [42], image discrimination [43], error correcting codes [44], and
quantum repeaters [45]. This problem does not have a closed analytical
solution, except for sets of states with high symmetry. Our approach may also
implement other discrimination strategies at the expense of resorting to more
elaborate optimization algorithms. We first consider the minimum-error
discrimination of two unknown non-orthogonal pure states. In this case the
minimum of the average error probability, which can be analytically
calculated, is given by the Helstrom bound. We show that it is possible to
train the measuring device to reach values very close to the Helstrom bound.
We extend our analysis to $d$ unknown non-orthogonal quantum states using
$d$-dimensional symmetric states. Discrimination of this class of states plays
an important role in processes such as quantum teleportation [46, 47],
entanglement swapping [48], and dense coding [49] when carried out with
partially entangled states and has already been implemented experimentally
[24]. In this case, our approach also leads to the optimal single-shot
generalized quantum measurement. However, it requires a large number of
iterations. This is a consequence of the dimension of the control parameter
space that scales as $d^{4}$. We also show that the use of a priori
information effectively reduces the number of iterations, where we consider
the use of initial conditions close to the optimal measurement as well as the
reduction of the dimension of the control parameter space by assuming a
particular property of the optimal measurement. Finally, we consider the
discrimination of unknown mixed quantum states generated by quantum channels
such as dephasing. This article is organized as follows: in Sec. II we
introduce our approach to the discrimination of unknown orthogonal quantum
states. In Sec. III we study the properties of our approach by means of
several numerical experiments. In Sec. IV we summarize and conclude.

##  II Method

Alice encodes the information to be transmitted into a set of $N$ mutually
orthogonal pure states $\\{|\psi_{q}\rangle\\}$ that are generated with
probabilities $\\{\eta_{q}\\}$. The communication channel transforms the
states $\\{|\psi_{q}\rangle\\}$ into the states $\\{\rho_{q}\\}$, pure or
mixed. For simplicity, we assume that the relation between states
$|\psi_{q}\rangle$ and $\rho_{q}$ is one to one and that the action of the
channel does not change the generation (or a priori) probabilities. Upon
receiving each state, Bob tries to decode the information sent by Alice using
a positive operator-valued measure $\\{E_{m}\\}$ composed of positive semi-
definite matrices $E_{m}$ such that $\sum_{m}E_{m}=\emph{I}$, the identity
operator. The probability of obtaining the $m$-th measurement outcome given
that the state $\rho_{q}$ was sent is $P(E_{m}|\rho_{q})=Tr(E_{m}\rho_{q})$.
We assume that if Bob obtains the $m$-th measurement result, he concludes that
Alice attempted to transmit the state $|\psi\rangle_{m}$. This decoding rule
leads to errors unless the states $\\{\rho_{q}\\}$ are mutually orthogonal,
which leads Bob to seek to minimize the occurrence of errors in the
discrimination process. Thereby, Bob needs to find the optimal POVM that
minimizes the figure of merit that accounts for the errors.

Several quantum state discrimination strategies are known, each defined by a
particular figure of merit. Here, we focus on minimum-error discrimination,
where the number of states to be identified equals the number of elements of
the POVM. The probability of correctly identifying the state
$|\psi\rangle_{q}$ is given by $P(E_{q}|\rho_{q})$. Since the states
$\\{|\psi\rangle_{q}\\}$ are generated with probabilities $\\{\eta_{q}\\}$,
the average probability of correctly identifying all states is given by

$p_{corr}=\sum_{l=1}^{N}\eta_{l}Tr(E_{l}\rho_{l}).$ (1)

The average error probability is $p_{err}=1-p_{corr}$. This probability, which
is a function of the POVM $\\{E_{m}\\}$ and of the unknown states
$\\{\rho_{k}\\}$, is minimized over the POVM space in order to train the
measurement device of Bob. We assume that the states are fixed, that is, that
every time Alice aims to transmit the state $|\psi_{k}\rangle$, Bob receives
the same state $\rho_{k}$. Thereby, the set of states $\\{\rho_{q}\\}$ behaves
as a set of unknown fixed parameters.

The value of $p_{err}$ corresponds to a sum over probabilities
$\eta_{l}Tr(\rho_{l}E_{l})$, which must be independently estimated. In order
to do this Alice sends $N$ copies of each state $|\psi_{l}\rangle$ to Bob,
communicating classically the label of them. These states play the role of
training set. Bob measures the states with the corresponding POVM, which
allows estimate the value of $Tr(\rho_{l}E_{l})$. We simulate the experiment
that allows us to estimate this value. For simulation purposes the states
$\\{\rho_{l}\\}$ are known and thus we calculate the probabilities

$p_{l}=Tr(\rho_{l}E_{l})~{}{\rm and}~{}q_{l}=1-p_{l}=1-\sum_{m\neq
l}Tr(\rho_{k}E_{m}).$ (2)

These are employed to generate a random number $n_{l}$ from a binomial
distribution with success probability $p_{l}$ on a sample of size $N$. The
probability $p_{l}$ is estimated as $n_{l}/N$. This procedure is repeated for
each state in the set $\\{\rho_{k}\\}$ and for each one of the POVMs at each
iteration. Thereby, the average error probability is estimated as

$p_{err}=1-\sum_{l}\eta_{l}\frac{n_{l}}{N}.$ (3)

We consider that the measurement device implements a POVM using the direct sum
extension. According to this, the Hilbert space ${\cal H}_{s}$ of the states
to be discriminated is complemented with an ancilla space ${\cal H}_{a}$,
obtaining an extended Hilbert space ${\cal H}_{e}={\cal H}_{s}\oplus{\cal
H}_{a}$. The POVM is implemented by applying a unitary transformation $U$ on
${\cal H}_{e}$ followed by a projective measurement on ${\cal H}_{e}$. This
procedure requires the least added dimensions than tensor product extension
[50]. To generate the unitary matrix $U$ we use a complex matrix $Z$ of order
$dn\times d$, where $d$ is the dimension of ${\cal H}$ and $n$ is the number
of states to be discriminated, and through the QR decomposition, we project it
into an isometric matrix $S$, that is, a matrix such $S^{\dagger}S=I_{d\times
d}$. Reshaping $S$ into a rank-3 tensor $S_{ijk}$ of size $n\times d\times d$,
we can generate a full-rank POVM as $E_{i}=M_{i}^{\dagger}M_{i}$, where the
components of the matrices $M_{i}$ are $M_{i,jk}=S_{ijk}$. To physically
realize the unitary transformation $U$ of order $dn\times dn$ one would need
to fill the matrix $S$ with free parameters only determined up to unitarity.
The average error probability $p_{err}$ can be thus regarded as a function of
the complex vector ${\bm{z}}$ whose coefficients are given by the matrix
elements of $U$, that is, we have $f(\bm{z})=p_{err}({\bm{z}})$.

We assume that neither Alice and Bob have access to the density matrices
$\\{\rho_{q}\\}$. Thereby, we cannot evaluate numerically the error
probability $p_{err}$ or it derivatives. Besides, given that we consider POVMs
implemented by direct sum extension, the shift parameter rule can not be
applied to evaluate the gradient [51, 52]. Therefore, the optimization problem
cannot be carried out using SDP or gradient-based optimization algorithms. To
overcome this problem, we optimize $p_{err}$ using the Complex simultaneous
perturbation stochastic approximation (CSPSA) [38, 39], a gradient-free
algorithm. This is based on the iterative rule

${\bm{z}}_{k+1}={\bm{z}}_{k}-a_{k}{\bm{g}}_{k}$ (4)

where ${\bm{z}}_{k}$ is a complex vector in the control parameter space at the
$k$-th iteration, $a_{k}$ is a positive gain coefficient, and ${\bm{g}}_{k}$
is an approximation of the gradient of the figure of merit $f({\bm{z}})$ whose
components are given by

$g_{k,i}=\frac{f({\bm{z}_{k,+}})-f({\bm{z}_{k,-}})+\zeta_{k,+}-\zeta_{k,+}}{2c_{k}\Delta^{*}_{k,i}}.$
(5)

In the expression above, the quantities $f({\bm{z}_{k,+}})$ and
$f({\bm{z}_{k,-}})$ are the values of the figure of merit at the vectors

${\bm{z}_{k,\pm}}={\bm{z}_{k}}\pm c_{k}\Delta_{k},$ (6)

where $c_{k}$ is a positive gain coefficient and $\Delta_{k}$ is a vector
whose components are at each iteration randomly generated from the set
$\\{1,-1,i,-i\\}$. CSPSA allows for the existence of noise $\zeta_{k,\pm}$ in
the evaluations $f({\bm{z}_{k,\pm}})$.

##  III Results

We start to analyze our approach by considering the simplest case, namely, the
discrimination of two unknown orthogonal pure states. We assume that Alice
prepares the states $\\{|0\rangle,|1\rangle\\}$ with a priori probabilities
$\eta_{0}$ and $\eta_{1}$, respectively. These orthogonal states are
transformed by the communication channel into the states

$\displaystyle|\,{\psi_{0}}\,\rangle=\sqrt{\frac{1+s}{2}}|\,{0}\,\rangle+\sqrt{\frac{1-s}{2}}|\,{1}\,\rangle,$
(7)
$\displaystyle|\,{\psi_{1}}\,\rangle=\sqrt{\frac{1+s}{2}}|\,{0}\,\rangle-\sqrt{\frac{1-s}{2}}|\,{1}\,\rangle,$
(8)

where the parameter $s$ corresponds to the real-valued inner product
$\langle\psi_{0}|\psi_{1}\rangle$. In this scenario, the optimal average error
probability is given by the Helstrom bound [10]

$p_{err}=\frac{1}{2}(1-\sqrt{1-4\eta_{0}\eta_{1}s^{2}}),$ (9)

which can be achieved by measuring an observable.

We assume that the value of $s$ is unknown. The training of the measurement
device is carried out without the use of a priori information. In particular,
the training does not use the facts that the transmitted states are pure and
that the optimal measurement is an observable. For a given value of $s$ our
training procedure leads to a quantum measurement characterized by a value
$\tilde{p}_{err}$ close to the optimal value given by the Helstrom bound. This
is depicted in Fig. 1(a), which shows the value of $\tilde{p}_{err}$ achieved
by the training procedure as a function of $s$ for $\eta_{0}=\eta_{1}=1/2$.
Since the optimization algorithm is stochastic, for each value of $s$ we
repeat the procedure considering 100 randomly chosen initial guesses in the
control parameter space and 100 iterations. The statistic generated by each
POVM is simulated using an ensemble size $N=150$. In Fig. 1(a) the solid black
line describes the Helstrom bound while the solid blue dots indicate the
median of $\tilde{p}_{err}$ calculated over the 100 repetitions. The blue
error bars describe the interquartile range. As is apparent from this figure,
the training of the measurement device provides a median of $\tilde{p}_{err}$
that is very close to the Helstrom bound, where the difference
$|\tilde{p}_{err}-p_{err}|$ is on the order of $10^{-2}$. The training
procedure leads to similar results for other values of generation
probabilities.

The total ensemble $N_{t}$ employed along the training process is given by
$N_{t}=2Nk_{t}$, where $k_{t}$ is the total of iterations. Thus, the total
ensemble can be split among the total number of iterations and the ensemble
used to estimate the statistic of each POVM. This raises the question whether
for a fixed total ensemble better accuracy is achieved by increasing $k_{t}$
or $N$. Figures 1(b) and 1(c) show the impact on $\tilde{p}_{err}$ for
different splittings of $N_{t}=15\times 10^{3}$. In Fig. 1(b) we have $N=1500$
and $k_{t}=10$ and in Fig. 1(c) we have $N=50$ and $k_{t}=300$. As these two
figures indicate, a much better accuracy is obtained by splitting the total
ensemble in a small ensemble $N$ and a large number $k_{t}$ of iterations. In
particular, in Fig. 1(c) the difference $|\tilde{p}_{err}-p_{err}|$ is in the
order of $10^{-3}$, that is, one order of magnitude smaller than in the case
of Fig. 1(a). Furthermore, the interquartile range becomes narrower indicating
less variability in the set of estimates $\\{\tilde{p}_{err}\\}$ for a given
$p_{err}$.

(a)

(b)

(c)

Figure 1: Median of the estimated minimum-error probability $\tilde{p}_{err}$
as a function of the inner product $s$ between two unknown pure states given
by Eq. (8) for $\eta_{0}=\eta_{1}=1/2$. Solid black line corresponds to the
minimum-error probability $p_{err}$ given by the Helstrom bound in Eq. (9).
Solid blue dots corresponds to the median of $\tilde{p}_{err}$ calculated over
100 initial conditions for each value of $s$. Blue error bars indicate
interquartile range.(a) $N=150$ and $k_{t}=100$, (b) $N=1500$ and $k_{t}=10$,
and (c) $N=50$ and $k_{t}=300$.

The training of the measurement device for the discrimination of a larger
number of states is demonstrated via symmetric states. These are given by the
expression

$|\,{\psi_{j}}\,\rangle=\sum_{k=0}^{d-1}c_{k}\omega^{jk}|\,{k}\,\rangle,~{}j\in\\{0,\cdots,d-1\\},$
(10)

where $d$ is the dimension of ${\cal H}_{s}$, $\omega=\exp{(2\pi i/d)}$, and
the coefficients $c_{k}$ are constrained by the normalization condition. As
long as the generation probabilities are equal, $d$ non-orthogonal symmetric
states can be identified by measuring an observable whose eigenstates are
given by the Fourier transform of the canonical base $\\{|k\rangle\\}$ (with
$k=0,\dots,d-1$). The minimum-error discrimination of symmetric states has
been experimentally demonstrated with high accuracy in dimensions up to $d=21$
[24]. The discrimination of symmetric states typically arises in the processes
of quantum teleportation, entanglement swapping and dense coding. These use a
maximally entangled quantum channel as resource. If the entanglement decreases
along the generation of the channel, then the performance of the process can
be enhanced by resorting to the local discrimination of symmetric states,
where the coefficients $c_{k}$ entering in Eq. (10) are given by the real
coefficients of the partially entangled state. If in addition, the channel
coefficients are unknown, then our approach can be used.

In the case of three symmetric states, the channel coefficients are
parameterized as $c_{0}=\cos(\theta_{1}/2)\cos(\theta_{2}/2)$ and
$c_{1}=\sin(\theta_{1}/2)\cos(\theta_{2}/2)$ with $\theta_{1}$ and
$\theta_{2}$ in the interval $[0,\pi]$. Figure 2(a) shows $\tilde{p}_{err}$ as
a function of $\theta_{1}$ for a particular value of $\theta_{2}$. The solid
black line corresponds to the optimal minimum error discrimination probability
$p_{err}$ while the solid blue dots indicate the median of $\tilde{p}_{err}$
calculated over 100 initial conditions for each value of $\theta_{1}$ after
$10^{3}$ iterations using an ensemble size $N=10^{3}$. The difference
$|p_{err}-\tilde{p}_{err}|$ is on the order of $10^{-2}$, as in the case of
Fig. 1, but obtained with a higher number of iterations and a larger ensemble
size. In the case of a higher number states we resort to a bi-parametric
family of symmetric states given by $c^{2}_{k}\propto
1-\sqrt[d]{[(k-j_{0}+1)/(d-j_{0})]\alpha}$ if $k\geq j_{0}$ and
$c^{2}_{k}\propto 1$ if $k<j_{0}$, where $j_{0}=1,\dots,d-1$ and
$\alpha\in[0,1]$. Figures 2(b) and 2(c) show the behavior of $\tilde{p}_{err}$
as a function of $\alpha$ and $j_{0}=2$ for $d=4$ and $d=5$, respectively. In
both cases the ensemble size is $N=300$ and the median was calculated over 100
initial conditions for each value of $\alpha$. As in Fig. 2(a), the difference
$|p_{err}-\tilde{p}_{err}|$ is on the order of $10^{-2}$. To achieve this
result, however, it was necessary to increase the number of iterations to
$6\times 10^{3}$ and $1.2\times 10^{4}$ for $d=4$ and $d=5$, respectively.

Thus, as we increase the number $n$ of states to be discriminated and the
dimension $d$ of the Hilbert space, the number of iterations $k_{t}$ and the
ensemble size $N$ required to achieve a given tolerance also increase. This is
due to the fact that the dimension of the search space, that is, the number of
parameters that control the measuring device, increases as $(nd)^{2}$.
Besides, the probabilities entering in the estimate of $p_{err}$ of Eq. (3)
are obtained using as a resource a given ensemble size. As the number of
probabilities increases it is necessary to increase the ensemble size $N$ to
obtain probability estimates that lead to a given tolerance.

(a)

(b)

(c)

Figure 2: Median of the estimated minimum-error probability $\tilde{p}_{err}$
for symmetric states as a function of: (a) $\theta_{1}$ for $d=3$, (b)
$\alpha$ for $d=4$, and (c) $\alpha$ for $d=5$. Solid black line corresponds
to the optimal minimum-error probability $p_{err}$. Solid blue dots correspond
to the median of $\tilde{p}_{err}$ calculated over 100 initial conditions for
each set of symmetric states. Blue error bars indicate interquartile range.
(a) $N=300$ and $k_{t}=300$. (b) $N=300$ and $k_{t}=6\times 10^{3}$. (c)
$N=300$ and $k_{t}=1.2\times 10^{4}$.

So far we have considered the training of the measurement device assuming the
most general quantum measurement. This typically conveys an increase in the
resources required for the training. As our previous simulations indicate, as
we increase the number $n$ of states to discriminate, as well as the dimension
$d$, the training of the measurement device consumes even more resources, that
is, larger ensembles and higher iteration numbers.

To reduce the resources required for training, it is customary to reduce the
dimension of the search space. This is done by imposing a set of conditions
onto the measurement device. This occurs when we have a priori information
that allows us to ascertain that the optimal measurement satisfy a given
condition. For instance, if the non-orthogonal states to be discriminated via
the minimum-error strategy are pure and $n=d$, then we can assume that the
optimal POVM is an observable. This effectively decreases the dimension of the
search space. Another possibility is that we are interested in reaching a
given value of the minimum-error probability in a particular family of
measurement devices, in which case we don’t need the optimal measurement.

(a)

(b)

(c)

Figure 3: Median of the estimated minimum-error probability $\tilde{p}_{err}$
as a function of the inner product $s$ between two unknown pure states given
by Eq. (8). Solid black line corresponds to the minimum-error probability
$p_{err}$ given by the Helstrom bound in Eq. (9). Solid blue dots indicate the
median of $\tilde{p}_{err}$ calculated over 100 initial conditions for each
value of $s$. Blue error bars indicate interquartile range. (a)
$\eta_{0}=\eta_{1}=1/2$, (b) $\eta_{0}=1/3$ and $\eta_{1}=2/3$, and (c)
$\eta_{0}=2/5$ and $\eta_{1}=3/5$. Simulations are carried out with an
ensemble size $N=50$ and total number of iterations $k_{t}=50$.

This is depicted in Fig. 3, where we reproduce the Helstrom bound for states
in Eq. (8) by optimizing in the set of observables. In Fig. 3(a) we show the
case of equal generation probabilities. In this case, the training was carried
out using an ensemble size $N=50$ and a total number of iterations $k_{t}=50$,
which leads to a difference $|p_{err}-\tilde{p}_{err}|$ is on the order of
$10^{-3}$. This result can be compared to the one illustrated in Fig.1(c),
where the same ensemble size is used but with much larger number of iterations
$k_{t}=300$. Thereby, the reduction in the dimension of the search space leads
to a reduction of the total ensemble $N_{tot}$ by a factor 6. A similar result
holds in Figs. 3(b) and 3(c) for different values of the generation
probabilities. Let us note that the initial condition in the search space is
randomly chosen, that is, we do not assume as initial condition an observable
close to the optimal one.

(a)

(b)

Figure 4: Discrimination of two unknown non-orthogonal mixed single-qubit
states generated by dephasing channel. (a) Solid green line indicates median
value of $\tilde{p}_{err}$, calculated over 100 repetitions, as a function of
the number of iterations. Solid red line correspond to the optimal value of
$p_{err}$ obtained via semidefinite programming. (b) Solid green line
indicates the median value of $|\tilde{p}_{err}-p_{err}|$ calculated over 100
repetitions, as a function of the number of iterations. (a) y (b) Shaded blue
area corresponds to interquartile range and ensemble size $N=300$.

Finally, we consider a more realistic scenario in which two single-qubit
orthogonal states emitted by Alice are subjected to the action of a dephasing
channel. The action of this channel onto a single-qubit density matrix $\rho$
is defined by the relation

$\varepsilon(\rho)=p\rho+\left(1-p\right)\sigma_{z}\rho\sigma_{z},$ (11)

where the parameter $p$ represent the strength of the channel and
$\sigma_{z}=|0\rangle\langle 0|-|1\rangle\langle 1|$. The dephasing channel
nullifies the off-diagonal terms in the density operator with respect to the
canonical basis $\\{|0\rangle,|1\rangle\\}$ while decreasing the purity. We
assume that the states transmitted by Alice are random pure states and that
the value of $p=3/5$ is unknown. The fidelity between the states pure states
and the noisy states is 0.785, respectively.

Figure 4 shows the result of training the measurement device to discriminate
the states generated by the dephasing channel. The training was initialized
from the measurement that optimally discriminates the pure states sent by
Alice. In Fig. 4(a) displays the median (continuous green line) of
$\tilde{p}_{err}$, calculated over 100 independent repetitions, as a function
of the number of iterations. The continuous red line corresponds to the
solution $p_{err}$ of the optimization of the minimum error for the states
generated by the dephasing channel via semidefinite programming. Clearly, the
value of $\tilde{p}_{err}$ obtained by training the measurement device
converges to the optimal value $p_{err}$. The interquartile range, described
by the shaded area, is very narrow indicating a very small variability of the
training with respect to the initial conditions. Similar results hold for
other values of the parameter $p$, which controls the convergence rate toward
the optimal value of $p_{err}$. Figure 4(b) displays the median of
$|\tilde{p}_{err}-p_{err}|$ as a function of the number of iterations.

##  IV Conclusions

Here, we have studied the problem of discriminating unknown non-orthogonal
that are generated when a party, Alice, encodes an alphabet in orthogonal
states and transmits them through a quantum channel to a second party, Bob.
This party tries to decoded the transmitted information by discriminating the
non-orthogonal state with the help of a measurement device that performs a
single-shot quantum measurement. We consider the case that this measurement
minimizes the average error probability. Provided that the non-orthogonal
states and its generation probabilities are known, the solution of the
optimization problem is generally obtained through semidefinite programming.
Given that neither Alice nor Bob know the states generated by the channel,
standard approaches can not be applied. Instead, we propose the training of a
measurement device to optimally discriminate a set of unknown non-orthogonal
quantum states. This device is controlled by a large set of parameters, such
that a set of parameter values corresponds to the realization of a positive
operator-valued measure (POVM). The measurement device is iteratively
optimized in the space of the control parameters, or search space, to achieve
the minimum value of the error probability, that is, we seek to implement the
minimum-error discrimination strategy. The optimization is driven by a
gradient-free stochastic optimization algorithm that approximates the gradient
of the error probability by a finite difference. This requires at each
iteration evaluation of the error probability at two different points in the
search space. Thereby, the training is driven by experimentally acquired data.
The choice of a stochastic optimization methods is based on its robustness
against noise.

We have studied the proposed approach using numerical simulations. First, we
have shown that our approach leads to values of the error probability that are
very close to the optimum. This was done in the case of two 2-dimensional
unknown non-orthogonal pure states, where the optimal value of the average
error probability is given by the Helstrom bound. Since the training method
requires the estimation of probabilities, the total ensemble is regarded as a
resource. This is divided evenly throughout the iterations of the training
method. We have shown that best results, that is, a value of the error
probability closer to the Helstrom bound, can be obtained for a fixed total
ensemble size by increasing the number of iterations. Thereafter, we have
extended our result to the case of $d$ $d$-dimensional symmetric states for
$d=3,4,5$, where our method also provides accurate results. However, to
achieve a fixed accuracy as we increase the number of states and the
dimension, its necessary to increase the ensemble size and, consequently, the
number of iterations. To avoid this, we have reduced the dimension of the
search space by assuming that the required measurement has some special
property. In particular, we have assumed that the optimal measurement is an
observable. Thereby, in the case of two non-orthogonal pure states we have
achieved a considerable reduction by a factor $1/6$ in the ensemble size,
which leads to a equal reduction in the number of iterations. Finally, we have
applied the training procedure to the dephasing channel and shown that it is
possible to achieve a value of the error probability close to the optimal one.

Our proposal finds application whenever two parties intend to communicate
through a channel whose characterization is difficult or costly. For instance,
it has been shown that processes such as quantum teleportation, entanglement
swapping and dense coding, when performed through a partially entangled
channel, can become a problem of local discrimination of non-orthogonal
states. If the description of the entangled channel is not available, then the
states to be discriminated are unknown, in which case our method can also be
applied. Recently, the problem of optimally discriminating between different
configurations of a complex scattering system has been studied [53] from point
of view of quantum state discrimination. Here, several non-orthogonal quantum
states of light are associated to different hypothesis about an scattering
system. These must be resolved with the best possible accuracy, which is
limited by the Helstrom bound in the simplest case. Our training method can
also be applied to this problem by finding the best average error probability.

###### Acknowledgements.

This work was supported by ANID – Millennium Science Initiative Program –
ICN17-012\. AD was supported by FONDECYT Grant 1180558. LP was supported by
ANID-PFCHA/DOCTORADO-BECAS-CHILE/2019-72200275. LZ was supported by ANID-
PFCHA/DOCTORADO-NACIONAL/2018-21181021.

## References

  * Wootters and Zurek [1982] W. K. Wootters and W. H. Zurek, Nature 299, 802 (1982).
  * Bell [1964] J. S. Bell, Physics Physique 1, 195 (1964).
  * Gisin [1998] N. Gisin, Physics Letters A 242, 1 (1998).
  * Pusey  _et al._ [2012] M. F. Pusey, J. Barrett, and T. Rudolph, Nature Physics 8, 475 (2012).
  * Schmid and Spekkens [2018] D. Schmid and R. W. Spekkens, Physical Review X 8, (2018).
  * Chefles [2000] A. Chefles, Contemporary Physics 41, 401 (2000).
  * Bae and Kwek [2015] J. Bae and L.-C. Kwek, Journal of Physics A: Mathematical and Theoretical 48, 083001 (2015).
  * Holevo [1973] A. Holevo, Journal of Multivariate Analysis 3, 337 (1973).
  * Yuen  _et al._ [1975] H. Yuen, R. Kennedy, and M. Lax, IEEE Transactions on Information Theory 21, 125 (1975).
  * Helstrom [1969] C. W. Helstrom, Journal of Statistical Physics 1, 231 (1969).
  * Ivanovic [1987] I. Ivanovic, Physics Letters A 123, 257 (1987).
  * Dieks [1988] D. Dieks, Physics Letters A 126, 303 (1988).
  * Peres [1988] A. Peres, Physics Letters A 128, 19 (1988).
  * Chefles and Barnett [1998] A. Chefles and S. M. Barnett, Physics Letters A 250, 223 (1998).
  * Croke  _et al._ [2006] S. Croke, E. Andersson, S. M. Barnett, C. R. Gilson, and J. Jeffers, Physical Review Letters 96, (2006).
  * Jiménez  _et al._ [2011] O. Jiménez, M. A. Solís-Prosser, A. Delgado, and L. Neves, Physical Review A 84, (2011).
  * Bagan  _et al._ [2012] E. Bagan, R. Muñoz-Tapia, G. A. Olivares-Rentería, and J. A. Bergou, Physical Review A 86, (2012).
  * Herzog [2012] U. Herzog, Physical Review A 86, (2012).
  * Cook  _et al._ [2007] R. L. Cook, P. J. Martin, and J. M. Geremia, Nature 446, 774 (2007).
  * Barnett and Riis [1997] S. M. Barnett and E. Riis, Journal of Modern Optics 44, 1061 (1997).
  * Clarke  _et al._ [2001] R. B. M. Clarke, V. M. Kendon, A. Chefles, S. M. Barnett, E. Riis, and M. Sasaki, Physical Review A 64, (2001).
  * Mohseni  _et al._ [2004] M. Mohseni, A. M. Steinberg, and J. A. Bergou, Physical Review Letters 93, (2004).
  * Waldherr  _et al._ [2012] G. Waldherr, A. C. Dada, P. Neumann, F. Jelezko, E. Andersson, and J. Wrachtrup, Physical Review Letters 109, (2012).
  * Solís-Prosser  _et al._ [2017] M. Solís-Prosser, M. Fernandes, O. Jiménez, A. Delgado, and L. Neves, Physical Review Letters 118, (2017).
  * Chen  _et al._ [2020] H. Chen, L. Wossnig, S. Severini, H. Neven, and M. Mohseni, Quantum Machine Intelligence 3, (2020).
  * Patterson  _et al._ [2021] A. Patterson, H. Chen, L. Wossnig, S. Severini, D. Browne, and I. Rungger, Physical Review Research 3, (2021).
  * Ursin  _et al._ [2007] R. Ursin, F. Tiefenbacher, T. Schmitt-Manderbach, H. Weier, T. Scheidl, M. Lindenthal, B. Blauensteiner, T. Jennewein, J. Perdigues, P. Trojek, B. Ömer, M. Fürst, M. Meyenburg, J. Rarity, Z. Sodnik, C. Barbieri, H. Weinfurter, and A. Zeilinger, Nature Physics 3, 481 (2007).
  * Toyoshima  _et al._ [2008] M. Toyoshima, Y. Takayama, W. Klaus, H. Kunimori, M. Fujiwara, and M. Sasaki, Acta Astronautica 63, 179 (2008).
  * Jin  _et al._ [2010] X.-M. Jin, J.-G. Ren, B. Yang, Z.-H. Yi, F. Zhou, X.-F. Xu, S.-K. Wang, D. Yang, Y.-F. Hu, S. Jiang, T. Yang, H. Yin, K. Chen, C.-Z. Peng, and J.-W. Pan, Nature Photonics 4, 376 (2010).
  * Steinlechner  _et al._ [2017] F. Steinlechner, S. Ecker, M. Fink, B. Liu, J. Bavaresco, M. Huber, T. Scheidl, and R. Ursin, Nature Communications 8, (2017).
  * Liao  _et al._ [2018] S.-K. Liao, W.-Q. Cai, J. Handsteiner, B. Liu, J. Yin, L. Zhang, D. Rauch, M. Fink, J.-G. Ren, W.-Y. Liu, Y. Li, Q. Shen, Y. Cao, F.-Z. Li, J.-F. Wang, Y.-M. Huang, L. Deng, T. Xi, L. Ma, T. Hu, L. Li, N.-L. Liu, F. Koidl, P. Wang, Y.-A. Chen, X.-B. Wang, M. Steindorfer, G. Kirchner, C.-Y. Lu, R. Shu, R. Ursin, T. Scheidl, C.-Z. Peng, J.-Y. Wang, A. Zeilinger, and J.-W. Pan, Physical Review Letters 120, (2018).
  * Dušek and Bužek [2002] M. Dušek and V. Bužek, Physical Review A 66, (2002).
  * Bergou and Hillery [2005] J. A. Bergou and M. Hillery, Physical Review Letters 94, (2005).
  * Hayashi  _et al._ [2005] A. Hayashi, T. Hashimoto, and M. Horibe, Physical Review A 72, (2005).
  * Bergou  _et al._ [2006] J. A. Bergou, V. Bužek, E. Feldman, U. Herzog, and M. Hillery, Physical Review A 73, (2006).
  * Probst-Schendzielorz  _et al._ [2007] S. T. Probst-Schendzielorz, A. Wolf, M. Freyberger, I. Jex, B. He, and J. A. Bergou, Physical Review A 75, (2007).
  * Zhou [2011] T. Zhou, Quantum Information Processing 11, 1669 (2011).
  * Utreras-Alarcón  _et al._ [2019] A. Utreras-Alarcón, M. Rivera-Tapia, S. Niklitschek, and A. Delgado, Scientific Reports 9, (2019).
  * Zambrano  _et al._ [2020] L. Zambrano, L. Pereira, S. Niklitschek, and A. Delgado, Scientific Reports 10, (2020).
  * Rambach  _et al._ [2021] M. Rambach, M. Qaryan, M. Kewming, C. Ferrie, A. G. White, and J. Romero, Physical Review Letters 126, (2021).
  * Tan  _et al._ [2008] S.-H. Tan, B. I. Erkmen, V. Giovannetti, S. Guha, S. Lloyd, L. Maccone, S. Pirandola, and J. H. Shapiro, Physical Review Letters 101, (2008).
  * Pirandola [2011] S. Pirandola, Physical Review Letters 106, (2011).
  * Nair and Yen [2011] R. Nair and B. J. Yen, Physical Review Letters 107, (2011).
  * Lloyd  _et al._ [2011] S. Lloyd, V. Giovannetti, and L. Maccone, Physical Review Letters 106, (2011).
  * van Loock  _et al._ [2006] P. van Loock, T. D. Ladd, K. Sanaka, F. Yamaguchi, K. Nemoto, W. J. Munro, and Y. Yamamoto, Physical Review Letters 96, (2006).
  * Roa  _et al._ [2003] L. Roa, A. Delgado, and I. Fuentes-Guridi, Physical Review A 68, (2003).
  * Neves  _et al._ [2012] L. Neves, M. A. Solís-Prosser, A. Delgado, and O. Jiménez, Physical Review A 85, (2012).
  * Solís-Prosser  _et al._ [2014] M. A. Solís-Prosser, A. Delgado, O. Jiménez, and L. Neves, Physical Review A 89, (2014).
  * Pati  _et al._ [2005] A. K. Pati, P. Parashar, and P. Agrawal, Physical Review A 72, (2005).
  * Chen  _et al._ [2007] P.-X. Chen, J. A. Bergou, S.-Y. Zhu, and G.-C. Guo, Physical Review A 76, (2007).
  * Li  _et al._ [2017] J. Li, X. Yang, X. Peng, and C.-P. Sun, Physical Review Letters 118, (2017).
  * Schuld  _et al._ [2019] M. Schuld, V. Bergholm, C. Gogolin, J. Izaac, and N. Killoran, Physical Review A 99, (2019).
  * Bouchet  _et al._ [2021] D. Bouchet, L. M. Rachbauer, S. Rotter, A. P. Mosk, and E. Bossy, Optimal control of coherent light scattering for binary decision problems (2021), arXiv:2108.03755 .


# Minimal cover groups

Peter J. Cameron111School of Mathematics and Statistics, University of St
Andrews, St Andrews, Fife KY16 9SS, UK and Hamid Reza Dorbidi222Department of
Mathematics, Faculty of Science, University of Jiroft, Jiroft 78671-61167,
Iran

###### Abstract

Let $\mathcal{F}$ be a set of finite groups. A finite group $G$ is called an
$\mathcal{F}$-cover if every group in $\mathcal{F}$ is isomorphic to a
subgroup of $G$. An $\mathcal{F}$-cover is called minimal if no proper
subgroup of $G$ is an $\mathcal{F}$-cover; co-minimal if no proper quotient of
$G$ is an $\mathcal{F}$-cover; and minimum if its order is minimum among all
$\mathcal{F}$-covers. Thus a minimum $\mathcal{F}$-cover is both minimal and
co-minimal.

We prove several results about minimal and minimum $\mathcal{F}$-covers: for
example, every minimal cover of a set of $p$-groups (for $p$ prime) is a
$p$-group; every minimal cover of a set of perfect groups is perfect; and a
minimum cover of a set of two non-abelian simple groups is either their direct
product or simple. We give examples to show that a given set $\mathcal{F}$ can
have finitely or infinitely many minimal covers. We also define a dual concept
where subgroups are replaced by quotients, and pose a number of problems.

##  1 Introduction

Cayley’s celebrated theorem asserts that every group of order $n$ is a
subgroup of the symmetric group $S_{n}$. Motivated by this, we ask: given a
finite set $\mathcal{F}$ of finite groups, find a group $G$ which contains all
the groups in $\mathcal{F}$ as subgroups. We call $G$ an _$\mathcal{F}$
-cover_. If $\mathcal{F}$ consists of all the groups of order $n$, then we say
that $G$ is an _$n$ -cover_. Thus $S_{n}$ is an $n$-cover.

It is natural to ask about an $\mathcal{F}$-cover which is small in some
sense. We make the following definitions:

Let $G$ be an $\mathcal{F}$-cover. We say that $G$ is

  * •

_minimal_ if no proper subgroup of $G$ is an $\mathcal{F}$-cover;

  * •

_co-minimal_ if no proper quotient of $G$ is an $\mathcal{F}$-cover;

  * •

_strongly minimal_ if it is both minimal and co-minimal;

  * •

_minimum_ if no $\mathcal{F}$-cover has smaller order.

Note that a minimum cover is strongly minimal. In this paper we are mainly
concerned with minimal and minimum covers.

We begin with a simple result to illustrate these concepts, showing in
particular that any finite set of finite groups has a cover.

###### Proposition 1.1

Let $\mathcal{F}$ be a finite set of finite groups, and $G$ an
$\mathcal{F}$-cover.

  1. (a)

$\mathop{\mathrm{lcm}}\\{|F|:F\in\mathcal{F}\\}$ divides $|G|$.

  2. (b)

If $G$ is minimum, then $|G|\leq\prod_{F\in\mathcal{F}}|F|$.

  3. (c)

If the orders of the groups in $\mathcal{F}$ are pairwise coprime, then
equality holds in (b).

###### Proof

(a) is immediate from Lagrange’s Theorem; (b) follows from the fact that the
direct product of the groups in $\mathcal{F}$ is a cover; and (c) is immediate
from (a) and (b). $\Box$

Note that, if the orders of the groups in $\mathcal{F}$ are powers of distinct
primes, then a minimum $\mathcal{F}$-cover is a group which has these as its
Sylow subgroups.

###### Example 1.2

A minimum cover of $\\{\mathbb{Z}_{3}$,
$(\mathbb{Z}_{2})^{2},\mathbb{Z}_{5}\\}$ has order $60$; any group of order
$60$ having these three groups as its Sylow subgroups is an example. This
holds for seven of the $13$ groups of order 60, including $D_{3}\times D_{5}$,
$A_{4}\times\mathbb{Z}_{5}$, and $A_{5}$.

Proposition 1.1 shows that the order of a minimum $\mathcal{F}$-cover is
bounded by a function of $\mathcal{F}$ (namely, the product of the orders of
the groups in $\mathcal{F}$). In particular, there are only finitely many
minimum $\mathcal{F}$-covers. The main question, which we cannot answer in
general, is the following:

###### Question 1.3

For which finite sets $\mathcal{F}$ of finite groups is it true that there are
only finitely many minimal $\mathcal{F}$-covers?

In particular, in the next section we give two examples to show that, for sets
consisting of two cyclic groups of prime order, some have this property while
others do not. There are some general things we can say:

###### Theorem 1.4

Let $p$ be a prime, and let $\mathcal{F}$ be a finite set of finite
$p$-groups. Then every minimal $\mathcal{F}$-cover is a $p$-group.

###### Proof

Let $G$ be a minimal $\mathcal{F}$-cover, and $P$ a Sylow $p$-subgroup of $G$.
Then every group in $\mathcal{F}$ is embedded in $G$, and so conjugate to a
subgroup of $P$. Hence $P$ is an $\mathcal{F}$-cover. By minimality, $P=G$.
$\Box$

However, one question we have not been able to resolve is the following:

###### Question 1.5

Let $\mathcal{F}$ be a finite set of finite $p$-groups, where $p$ is prime. Is
the order of a minimal $\mathcal{F}$-cover bounded by a function of
$\mathcal{F}$? What about strongly minimal covers (covers for which no proper
subgroup of quotient is a cover)?

###### Theorem 1.6

Let $\mathcal{A}$ be a class of groups which is closed under the taking of
subgroups and direct products. If $\mathcal{F}$ is a subset of $\mathcal{A}$
then there exists an $\mathcal{A}$-group which is a minimal
$\mathcal{F}$-cover.

###### Proof

Let $G=\Pi_{H\in\mathcal{F}}H$ . Then $G$ is an $\mathcal{A}$-group which is
also an $\mathcal{F}$-cover. So $G$ contains a minimal $\mathcal{F}$-cover
which is an $\mathcal{A}$-group. $\Box$

It is not clear when we can obtain a minimum $\mathcal{F}$-cover in this way.
We will see in the next section that it is the case for nilpotent groups, but
for the apparently easier case of abelian groups we have been unable to decide
the question.

###### Theorem 1.7

Let $n=p_{1}^{\alpha_{1}}\cdots p_{k}^{\alpha_{k}}$ and $G$ be a minimal
$n$-cover. If $P_{i}$ is a Sylow subgroup of $G$ then $P_{i}$ is a
$p_{i}^{\alpha_{i}}$-cover group.

###### Proof

Let $P$ be a group of order $p_{i}^{\alpha_{i}}$. Then $H=P\times\Pi_{j\neq
i}\mathbb{Z}_{p_{j}^{\alpha_{j}}}$ is a group of order $n$. So $H$ is
isomorphic to a subgroup of $G$. Hence $P$ is isomorphic to a subgroup of
$P_{i}$. $\Box$

###### Question 1.8

In the above situation, when is $P_{i}$ a minimal $p_{i}^{\alpha_{i}}$-cover
group?

###### Remark 1.9

If the groups in $\mathcal{F}$ are solvable $\pi$-groups, then every solvable
minimal $\mathcal{F}$-cover is a $\pi$-group, by Philip Hall’s theorem. Also
for every minimum $\mathcal{F}$-cover $G$ (for $\mathcal{F}$ a set of
$\pi$-groups) we have $O_{\pi^{\prime}}(G)=\\{1\\}$

We consider minimal covers of sets of $p$-groups further in Section 3.

A general question, which motivates much of what follows, is:

###### Question 1.10

Given a group-theoretic property $\mathbf{P}$, is it true that if every group
in $\mathcal{F}$ has property $\mathbf{P}$, then every (or perhaps some)
minimum (or minimal) $\mathcal{F}$-cover has property $\mathbf{P}$?

We consider this question for the properties cyclic, abelian, nilpotent in
Section 4; for simplicity in Section 5; and for perfectness and related
properties in Section 6. We conclude with a section on a dual version of these
notions and one on some open problems and further directions.

In this paper $\mathbb{Z}_{n}$ is the cyclic group of order $n$, $D_{n}$ the
dihedral group of order $2n$, and $S_{n}$ and $A_{n}$ the symmetric and
alternating groups of degree $n$. For undefined properties of finite groups
and more detailed information, we refer to Hall [4], Robinson [6] or Suzuki
[9].

##  2 Two examples

In this section we give examples of sets $\mathcal{F}$ consisting of two
cyclic groups of prime order, where there number of minimal
$\mathcal{F}$-covers may be finite or infinite.

###### Theorem 2.1

Let $G$ be a minimal $\\{\mathbb{Z}_{2},\mathbb{Z}_{3}\\}$-cover. Then $G$ is
isomorphic to one of the groups $S_{3}$, $\mathbb{Z}_{6}$ or $A_{4}$.

We split the proof into several cases.

###### Proposition 2.2

Let $G$ be a solvable minimal $\\{\mathbb{Z}_{2},\mathbb{Z}_{3}\\}$-cover.
Then $G\cong S_{3},\mathbb{Z}_{6},A_{4}$.

###### Proof

Since $G$ is solvable, so $G$ is a $\\{2,3\\}$-group. If $G^{\prime}=\\{1\\}$
then $G$ has a subgroup of order $6$. So $|G|=6$ by minimality of $G$. If
$|G^{\prime}|>1$ then $G^{\prime}$ is a $p$-group where $p\in\\{2,3\\}$. Let
$g$ be a $p^{\prime}$-element. If $N$ is a non-trivial characteristic subgroup
of $G^{\prime}$ then $\langle g\rangle N$ is a
$\\{\mathbb{Z}_{2},\mathbb{Z}_{3}\\}$-cover and by minimality we have
$G=\langle g\rangle N<\langle g\rangle G^{\prime}$ which is a contradiction.
So $G^{\prime}$ is characteristically simple. Hence $G^{\prime\prime}=\\{1\\}$
which implies $G^{\prime}$ is an elementary abelian $p$-group. Every element
in $G^{\prime}$ has $p$ conjugates under action of $\langle g\rangle$. If $N$
is the group generated by $\langle g\rangle$-conjugates of a $p$-element of
$G^{\prime}$ then $N$ is a normal subgroup of $G$ and $|N|\leq
p^{p^{\prime}}$. Hence $\langle g\rangle N=G$ and $|G|\mid
p^{\prime}p^{p^{\prime}}$. So $|G|\mid 24$ (if $p=2,p^{\prime}=3$) or $|G|\mid
18$ (if $p=3,p^{\prime}=2$). An easy calculation implies $G\cong
S_{3},\mathbb{Z}_{6},A_{4}$. The proof is complete. $\Box$

###### Proposition 2.3

Let $G$ be a simple group. Then $G$ is not a minimal
$\\{\mathbb{Z}_{2},\mathbb{Z}_{3}\\}$-cover.

###### Proof

According to the classification of maximal subgroups of simple groups, if
$6\mid|G|$ then there is a maximal subgroup $M$ of $G$ such that $6\mid|M|$.
So $G$ is not a minimal $\\{\mathbb{Z}_{2},\mathbb{Z}_{3}\\}$-cover. $\Box$

###### Proposition 2.4

Let $G$ be a non-solvable group. Then $G$ is not a minimal
$\\{\mathbb{Z}_{2},\mathbb{Z}_{3}\\}$-cover.

###### Proof

Assume $G$ is a minimal $\\{\mathbb{Z}_{2},\mathbb{Z}_{3}\\}$-cover. So $G$ is
not simple by Proposition 2.3. Let $N$ be a maximal normal subgroup of $G$. If
$2\nmid|N|$ then $N$ is solvable. If $g$ is an involution then $\langle
g\rangle N=G$ by minimality of $G$. So $G=\langle g\rangle N$ is solvable
which is a contradiction. So assume $2\mid|N|$. By minimality $3\nmid|N|$. Let
$g$ be an element of order three. So $\langle g\rangle N=G$ by minimality of
$G$. So $N$ is not solvable. If $N$ has a characteristic subgroup $T$ then
$\langle g\rangle T<G$ is a $\\{\mathbb{Z}_{2},\mathbb{Z}_{3}\\}$-cover which
is a contradiction. So $N$ is a characteristically simple group. Hence it is
direct product of $m$ copy of a non abelian simple group $S$. Since
$3\nmid|N|$ we conclude $3\nmid|S|$. Hence $S$ is a suzuki group $Sz(q)$.First
assume $m>1$. Let $S_{i}=g^{i}Sg^{-i}<N$ and $T=S_{0}S_{1}S_{2}$. Hence $g\in
N_{G}(T)$. So $\langle g\rangle T$ is a
$\\{\mathbb{Z}_{2},\mathbb{Z}_{3}\\}$-cover which implies $T=N$. Then
$K=\\{agag^{-1}g^{2}ag^{-2}:a\in S\\}$ is the fixed subgroup of conjugation by
$g$. So $g\in N_{G}(K)$. Hence $\langle g\rangle K<G$ is a
$\\{\mathbb{Z}_{2},\mathbb{Z}_{3}\\}$-cover which is a contradiction. Hence
$m=1$ and $N$ is isomorphic to $Sz(q)$. It is clear that $N$ contains all the
involutions of $G$. Let $t\in N$ be an involution. Since all the involution of
$Sz(q)$ are conjugate, so there is $n\in N$ such that $gtg^{-1}=ntn^{-1}$.
hence $x=g^{-1}n\in C_{G}(t)\backslash N$. Since $x^{3}\in N$, so $3\mid|x|$.
So $H=\langle x,t\rangle$ is a $\\{\mathbb{Z}_{2},\mathbb{Z}_{3}\\}$-cover
which is a contradiction by minimality of $G$. $\Box$

In the other direction, we have the following result.

###### Proposition 2.5

Let $q$ and $r$ be distinct primes greater than $5$. Then there are infinitely
many minimal $\\{\mathbb{Z}_{q},\mathbb{Z}_{r}\\}$-covers.

###### Proof

By Dirichlet’s theorem, there are infinitely many primes $p$ satisfying
$p\equiv 1$ (mod $q$) and $p\equiv-1$ (mod $r$). We claim that, for any such
prime $p$, the group $G=\mathop{\mathrm{PSL}}(2,p)$ is a minimal
$\mathcal{F}$-cover, where $\mathcal{F}=\\{\mathbb{Z}_{q},\mathbb{Z}_{r}\\}$.
To see this, the list of subgroups of $\mathop{\mathrm{PSL}}(2,p)$ given in
Suzuki [9, p. 404] shows that the only maximal subgroups of $G$ containing
$\mathbb{Z}_{q}$ and $\mathbb{Z}_{r}$ are dihedral groups of orders $p-1$ and
$p+1$ respectively, and so no proper subgroup of $G$ contains both. $\Box$

Since $\mathop{\mathrm{PSL}}(2,p)$ is simple, we see that these covers are
strongly minimal.

##  3 Groups of prime power order

In this section we examine sets of $p$-groups, for $p$ prime.

###### Remark 3.1

It is well known that the only groups of order $8$ are
$\mathbb{Z}_{8},\mathbb{Z}_{4}\times\mathbb{Z}_{2},\mathbb{Z}_{2}\times\mathbb{Z}_{2}\times\mathbb{Z}_{2},D_{4},Q_{8}$.
So the only $4$-cover groups of order $8$ are
$\mathbb{Z}_{4}\times\mathbb{Z}_{2}$ and $D_{4}$. Similarly there are five
groups of order $p^{3}$ for an odd prime $p$ which are
$\mathbb{Z}_{p^{3}},\mathbb{Z}_{p^{2}}\times\mathbb{Z}_{p},\mathbb{Z}_{p}\times\mathbb{Z}_{p}\times\mathbb{Z}_{p}$,
and the two non-abelian groups

$\displaystyle G_{p}$ $\displaystyle=$
$\displaystyle\left\\{\left[\begin{array}[]{ll}a&b\\\
0&1\end{array}\right]:a\in
1+p\mathbb{Z}_{p^{2}},b\in\mathbb{Z}_{p^{2}}\right\\},$
$\displaystyle\hbox{and }\mathrm{Heis}(\mathbb{Z}_{p})$ $\displaystyle=$
$\displaystyle\left\\{\left[\begin{array}[]{lll}1&a&b\\\ 0&1&c\\\
0&0&1\end{array}\right]:a,b,c\in\mathbb{Z}_{p}\right\\}$

with exponent $p^{2}$ and $p$ respectively. This implies the only
$p^{2}$-cover groups of order $p^{3}$ are $G_{p}$ and
$\mathbb{Z}_{p}\times\mathbb{Z}_{p^{2}}$

###### Proposition 3.2

Let $p$ be a prime number. Then

  1. (a)

for $p=2$ the only minimal $4$-cover groups are
$\mathbb{Z}_{4}\times\mathbb{Z}_{2}$ and $D_{4}$;

  2. (b)

for $p>2$ then the only minimal $p^{2}$-cover groups are
$\mathbb{Z}_{p^{2}}\times\mathbb{Z}_{p}$ and $G_{p}$.

###### Proof

Let $G$ be a minimal $p^{2}$-cover group. It is well known that
$\mathbb{Z}_{p^{2}}$ and $\mathbb{Z}_{p}\times\mathbb{Z}_{p}$ are the only two
group of order $p^{2}$ up to isomorphism. Let $H$ and $K=\langle a\rangle$ be
subgroups of $G$ which are isomorphic to $\mathbb{Z}_{p}\times\mathbb{Z}_{p}$
and $\mathbb{Z}_{p^{2}}$. Also $G$ contains a normal subgroup $N$ of order
$p^{2}$. If $N$ is cyclic then there is an element $g\in H\backslash N$. Then
$\langle g\rangle N$ is a $p^{2}$-cover of order $p^{3}$ and the proof is
complete by Remark 3.1. So assume $N\cong\mathbb{Z}_{p}\times\mathbb{Z}_{p}$.
First assume $|N\cap K|=1$. Then $NK$ is a $p^{2}$-cover of order $p^{4}$.
Hence $G=NK$. Since $N_{G}(N)/C_{G}(N)$ is isomorphic to a subgroup of
$\mathop{\mathrm{Aut}}(N)\cong\mathop{\mathrm{GL}}(2,p)$, so
$|N_{G}(N)/C_{G}(N)|\mid p$. Thus $a^{p}\in C_{G}(N)$. So $a^{p}\in Z(G)$.
Also $N\cap Z(G)$ is nontrivial so there is an element $g\in Z(G)\cap N$ of
order $p$. Hence $\langle g\rangle K$ is a $p^{2}$-cover of order $p^{3}$
which is a contradiction by minimality of $G$. Hence $|N\cap K|=p$. So
$|NK|=p^{3}$ and $NK$ is a $p^{2}$-cover. So the proof is complete by Remark
3.1. $\Box$

In the next case, we have the following.

###### Theorem 3.3

  1. (a)

There are two minimum $2^{3}$-covers groups, both of order $2^{5}$.

  2. (b)

For prime $p>2$, there is no $p^{3}$-cover of order $p^{5}$, but there is one
of order $p^{7}$; so a minimum $p^{3}$-cover has order $p^{6}$ or $p^{7}$.

###### Proof

Part (a) can be proved by computer: we used the computer algebra system GAP
[3]. The two $8$-covers are the groups SmallGroup(32,40) and SmallGroup(32,43)
in the GAP library. (There is no $8$-cover of order $16$. For suppose that $G$
was an $8$-cover of order $16$. Then $G$ contains subgroups
$A\cong\mathbb{Z}_{8}$ and $B\cong(\mathbb{Z}_{2})^{3}$; clearly $|A\cap
B|\leq 2$, so $|AB|=|A|\cdot|B|/|A\cap B|\geq 32$.)

For (b), the case $p=3$ can also be shown using GAP. For $p\geq 5$, we proceed
as follows. Let $G$ be a $p^{3}$-cover of order $p^{5}$. Then $G$ has
nilpotency class at most $4$, so smaller than $p$; hence $G$ is a regular
$p$-group [4, p. 183]. Now [4, Theorem 12.4.5] shows that the elements of
order $p$ in $G$, together with the identity, form a subgroup $H$ of $G$. Now
since $G$ contains both the elementary abelian group $(\mathbb{Z}_{p})^{3}$ of
order $p^{3}$ and the non-abelian group $\mathrm{Heis}(p)$ of order $p^{3}$
and exponent $p$; so the subgroup $H$ must satisfy $|H|>p^{3}$, so $|H|\geq
p^{4}$. Now $G$ must also contain the cyclic group $K=\mathbb{Z}_{p^{3}}$, and
$|H\cap K|\leq p$, so $|HK|\geq p^{4}\cdot p^{3}/p=p^{6}$. So no $p^{3}$-cover
of order $p^{5}$ can exist.

For the example, take for $G$ the central product of the cyclic group and the
two nonabelian groups $G_{p}$ and $\mathrm{Heis}(p)$ of order $p^{3}$ – that
is, take the direct product and identify the central subgroups of order $p$ in
the three groups. In other words, $G$ is generated by elements $a,b,c,d,e$
with a central element $z$ such that

  * •

$a,\ldots,e$ have orders $p^{3},p^{2}$, $p$, $p$, $p$ respectively, with
$a^{p^{2}}=b^{p}=z$;

  * •

$[b,c]=[d,e]=z$;

  * •

members of distinct sets from $\\{a\\}$, $\\{b,c\\}$ and $\\{d,e\\}$ commute.

Then $G$ has order $p^{7}$ and embeds the groups of order $p^{3}$ as follows:

  * •

$\mathbb{Z}_{p^{3}}\cong\langle a\rangle$;

  * •

$\mathbb{Z}_{p^{2}}\times\mathbb{Z}_{p}\cong\langle a^{p},c\rangle$;

  * •

$(\mathbb{Z}_{p})^{3}\cong\langle c,d,z\rangle$;

  * •

$G_{p}\cong\langle b,c\rangle$.

  * •

$\mathrm{Heis}(p)\cong\langle d,e\rangle$. $\Box$

###### Question 3.4

Is there a $p^{3}$-cover of order $p^{6}$, for $p$ an odd prime?

###### Question 3.5

We have seen that a minimum $8$-cover has order $32$. Moreover, there exist
minimal $8$-covers of order $64$; indeed there are $40$ such groups. Do there
exist minimal $8$-covers of arbitrarily large order?

Computation with GAP shows that, for $p=3$, there are many examples of
$p^{3}$-covers of order $p^{6}$: SmallGroup(729,$i$) has the property for each
of the values $16$, $19$, $70$, $71$, $86$, $90$, $244$, $254$, $261$, $262$,
$263$, $264$, $284$, $285$, $477$, $478$.

The lower bound given by Proposition 1.1 is $p^{n}$, which is too small, as we
now show.

We begin with a brief note. The fraction
$|\mathop{\mathrm{GL}}(n,p)|/p^{n^{2}}$ is the probability that an $n\times n$
matrix over the field of order $p$ is invertible. It can be written as

$\prod_{i=1}^{n}(1-p^{-i}).$

The theory of infinite products shows that, as $n\to\infty$ with $p$ fixed, it
decreases to a positive limit $\theta(p)$, which is an evaluation of a Jacobi
theta-function. It is easily seen that $\theta(p)$ is an increasing function
of $p$. The value of $\theta(2)$ is $0.2887\dots$. So the probability that an
$n\times n$ matrix over the $p$-element field is invertible is at least
$\theta(2)$ for any $n$ and $p$.

###### Lemma 3.6

Let $G$ be a group of order $p^{n}$ whose Frattini subgroup has index $p^{k}$.
Then the number of $n$-tuples of elements of $G$ whose first $k$ elements
generate $G$ is at least $cp^{n^{2}}$, with $c=\theta(2)$.

###### Proof

By the Burnside basis theorem, a $k$-tuple $g_{1},\ldots,g_{k}$ generates $G$
if and only if the images of $g_{1}$, …, $g^{k}$ in $G/\Phi(G)$ form a basis
for this quotient, which is isomorphic to a $k$-dimensional vector space over
the $p$-element field. The number of such bases is the order of
$\mathop{\mathrm{GL}}(k,p)$, which as noted is at least $cp^{k^{2}}$. For each
basis element, there are $p^{n-k}$ elements of the corresponding coset of
$\Phi(G)$ in $G$. Also, we can complete the $n$-tuple by choosing arbitrary
elements of $G$, each in $p^{n}$ ways. So the number of $n$-tuples is

$|\mathop{\mathrm{GL}}(k,p|\cdot p^{k(n-k)}\cdot p^{(n-k)n}\geq cp^{n^{2}},$

as required. $\Box$

###### Theorem 3.7

The order of a minimum $p^{n}$-cover is at least $p^{(2/27+o(1))n^{2}}$.

###### Proof

Suppose that $G$ is a minimum $p^{n}$-cover, of order $p^{N}$. There are
$p^{Nn}$ $n$-tuples of elements of $G$; among them are generating tuples for
all groups of order $p^{n}$. By Lemma 3.6, each group of order $p^{n}$ has at
least $cp^{n^{2}}$ generating $n$-tuples (since it has at least this many for
which the first $k$ elements generate, where $k$ is the minimum number of
generators). So the number of groups of order $p^{n}$ is at most

$p^{nN}/(cp^{n^{2}})=c^{-1}p^{n(N-n)}.$

However, it is known (see [5, 8]) that the number of different groups of order
$p^{n}$ is $p^{(2/27+o(1))n^{3}}$. So

$c^{-1}p^{n(N-n)}\geq p^{(2/27+o(1))n^{3}},$

from which we find that $N\geq(2/27+o(1))n^{2}$. $\Box$

###### Question 3.8

Find better bounds for the order of a minimum $p^{n}$-cover. In particular, is
there an upper bound of the form $p^{F(n)}$, where $F$ is independent of $p$?

In the next section, we will find the smallest abelian group which contains
all abelian groups of order $p^{n}$; its order is roughly $p^{n\log n}$.

##  4 Cyclic, abelian, and nilpotent

The observation that $A_{5}$ is a minimum cover for
$\\{\mathbb{Z}_{3},(\mathbb{Z}_{2})^{2},\mathbb{Z}_{5}\\}$ shows that it is
not true that, if all groups in $\mathcal{F}$ are abelian, nilpotent, or
solvable, then every minimum $\mathcal{F}$-cover has the same property.
Moreover, $\\{\mathbb{Z}_{2},\mathbb{Z}_{3}\\}$ has two minimum covers,
$\mathbb{Z}_{6}$ and $S_{3}$ So the best we can hope is that, if all groups in
$\mathcal{F}$ have a certain property, then at least one minimum
$\mathcal{F}$-cover has this property. This is the case for cyclic groups:

###### Theorem 4.1

Let $n_{1},\ldots,n_{k}$ be positive integers and
$N=\mathop{\mathrm{lcm}}(n_{1},\ldots,n_{k})$. Then $\mathbb{Z}_{N}$ is a
minimum cover for
$\mathcal{F}=\\{\mathbb{Z}_{n_{1}},\ldots,\mathbb{Z}_{n_{k}}\\}$.

###### Proof

Clearly $\mathbb{Z}_{N}$ is an $\mathcal{F}$-cover, and by Proposition 1.1 it
is minimum. $\Box$

Perhaps the next simplest example of Question 1.10 is one which we have not
been able to settle:

###### Question 4.2

Let $\mathcal{F}$ be a set of abelian $p$-groups, for some prime $p$. Is there
a minimum $\mathcal{F}$-cover which is an abelian $p$-group?

###### Theorem 4.3

Suppose that $\mathcal{F}$ is a finite set of finite nilpotent groups. Then
there is a minimum $\mathcal{F}$-cover which is nilpotent. If Question 4.2 has
an affirmative answer, then the same holds with “abelian” replacing
“nilpotent”.

###### Proof

Let $\mathcal{F}=\\{F_{1},\ldots,F_{r}\\}$ be a finite set of finite nilpotent
groups, and let $G$ be a minimum $\mathcal{F}$-cover. For each prime $p$, let
$F_{i}(p)$ be the Sylow $p$-subgroup of $F_{i}$, and let
$\mathcal{F}(p)=\\{F_{1}(p),\ldots,F_{r}(p)\\}$. Let $H(p)$ be a minimum
$\mathcal{F}(p)$-cover, and note that $H(p)$ is a $p$-group, by Theorem 1.4.
Let $H$ be the direct product of the groups $H(p)$. Now a Sylow $p$-subgroup
$G(p)$ of $G$ is an $\mathcal{F}_{p}$-cover, so $|G(p)|\geq|H(p)|$, and thus
$|G|\geq|H|$. But since each group in $\mathcal{F}$ is the direct product of
its Sylow subgroups, it is embeddable in $H$, and thus by minmality $|G|=|H|$.
So $H$ is a nilpotent cover of $\mathcal{F}$ with smallest possible order.

Now suppose that all the groups in $\mathcal{F}$ are abelian, and that
Question 4.2 has an affirmative answer. The same argument then applies, using
the fact that a nilpotent group is abelian if and only if all its Sylow
subgroups are. $\Box$

What is the order of the minimum cover? The theorem shows that it is enough to
find the order of a minimal cover of a set of $p$-groups. We can answer this
question in the case of abelian $p$-groups, again assuming that Question 4.2
has an affirmative answer.

Suppose that $\mathcal{F}=\\{F_{1},\ldots,F_{r}\\}$ is a set of abelian
$p$-groups. We can write each one in canonical form:

$F_{i}=\mathbb{Z}_{p^{a(i,1)}}\times\cdots\times\mathbb{Z}_{p^{a(i,k)}},$

where $a(i,1)\geq a(i,2)\geq\cdots\geq a(i,k)$; by adding extra zero terms if
necessary we can assume that the value of $k$ is the same for each group. Let

$c(j)=\max\\{a(1,j),a(2,j),\ldots,a(r,j)\\}$

for $j=1,\ldots,k$. We claim that

$c(1)\geq c(2)\geq\cdots\geq c(k).$

For suppose that $c(j+1)=a(i,j+1)$. Then $c(j)\geq a(i,j)\geq
a(i,j+1)=c(j+1)$.

Let

$P=\mathbb{Z}_{p^{c(1)}}\times\cdots\times\mathbb{Z}_{p^{c(k)}}.$

The above claim shows that this is the canonical form for $P$.

###### Proposition 4.4

With the above notation, $P$ is the smallest abelian $\mathcal{F}$-cover.

The proof depends on the following lemma:

###### Lemma 4.5

Let

$A=\mathbb{Z}_{p^{a(1)}}\times\cdots\times\mathbb{Z}_{p^{a(k)}}\hbox{ and
}B=\mathbb{Z}_{p^{b(1)}}\times\cdots\times\mathbb{Z}_{p^{b(k)}}$

be abelian $p$-groups in canonical form. Then $B$ is embeddable in $A$ if and
only if $b(j)\leq a(j)$ for $j=1,\ldots,k$.

###### Proof

Suppose that the inequalities hold. Then for each $j$ we can choose a subgroup
$\mathbb{Z}_{p^{b(j)}}$ of $\mathbb{Z}_{p^{a(j)}}$; the direct product of
these subgroups is isomorphic to $B$.

Conversely, suppose that $B$ is embeddable in $A$. Then $B$ contains a
subgroup $(\mathbb{Z}_{p^{b(j)}})^{j}$; in order to embed this in $A$, we
require that at least $j$ of $a(1),\ldots,a(k)$ are greater than or equal to
$b(j)$ for each $j$. Since the $a$ are non-decreasing, this requires $a(j)\geq
b(j)$. $\Box$

Now, to complete the proof of Proposition 4.4, note that in the notation
before the Proposition, $P$ embeds all the $F_{i}$ if and only if $c(j)\geq
a(i,j)$ for all $i$. So $P$ is the smallest abelian $\mathcal{F}$-cover.
$\Box$

We can use this result to find the smallest abelian group containing every
abelian group of order $p^{n}$.

Define a function $f$ by the rule

$f(n)=\sum_{k=1}^{n}\lfloor n/k\rfloor.$

###### Corollary 4.6

Let $\mathcal{F}$ be the set of abelian groups of order $p^{n}$. There is a
unique smallest abelian $\mathcal{F}$-cover; its order is $p^{f(n)}$. If the
answer to Question 4.2 is affirmative, it is a minimum $\mathcal{F}$-cover.

###### Proof

In the notation introduced before Proposition 4.4, we have $c(k)=\lfloor
n/k\rfloor$ for $k=1,\ldots,n$. For if the factors in the canonical
decomposition of an abelian group of order $p^{n}$ have orders $p^{a(1)}$,
$p^{a(2)}$, …, then

$ka(k)\leq a(1)+\cdots+a(k)\leq n,$

so $a(k)\leq\lfloor n/k\rfloor$; but there is a group of order $p^{n}$ with
$k$ invariant factors which are of nearly equal orders (that is, orders
$p^{\lfloor n/k\rfloor}$ or $p^{\lceil n/k\rceil}$); the $k$th of these in
non-decreasing order has order $p^{\lfloor n/k\rfloor}$.

So the smallest abelian group covering $\mathcal{F}$ has order $p^{\sum\lfloor
n/k\rfloor}=p^{f(n)}$, as required. $\Box$

For $p^{n}=2^{2}$ and $2^{3}$, this gives respectively $8$ and $32$ for the
smallest abelian group containing all abelian groups of order $p^{n}$. We have
seen that these are also the orders of minimal covers for all groups of these
orders. Furthermore, no smaller group can cover all abelian groups of these
orders. (For order $2^{2}$, this is clear. For order $2^{3}$, if
$A=\mathbb{Z}_{8}$ and $B=(\mathbb{Z}_{2})^{3}$ are subgroups of $G$, then
$|A\cap B|\leq 2$, so $|G|\geq|AB|\geq 32$.) So Question 4.2 has an
affirmative answer in these cases.

We note that the order of the smallest abelian cover of the class of abelian
groups of order $p^{n}$ is roughly $p^{n\log n}$, which can be contrasted with
the lower bound of $p^{cn^{2}}$ for a group covering every group of order
$p^{n}$. More precisely, $f(n)=n(\log n+2\gamma-1)+O(\sqrt{n})$, where
$\gamma$ is the Euler–Mascheroni constant (Dirichlet [2]).

The sequence of values of the function $f$ is sequence A006218 in the On-Line
Encyclopedia of Integer Sequences [7]. This gives many interpretations of the
sequence, but the one given here appears to be new.

We could ask whether similar results exist for solvable groups. But there is
an easy example to show that the minimum cover of a set of solvable groups
need not be solvable:

###### Example 4.7

Let $A$ be the alternating group $A_{4}$ and $B$ the dihedral group $D_{5}$ of
order $10$. Then $\mathop{\mathrm{lcm}}(|A|,|B|)=60$, and both groups are
embeddable in $A_{5}$, so $A_{5}$ is a minimum cover. There is no other cover
of order $60$. For such a group $G$ would act on the five cosets of $A$; it is
easily seen that either the action is faithful (whence $G\cong A_{5}$) or $A$
lies in the kernel (in which case $G\cong A_{4}\times\mathbb{Z}_{5}$); but in
the second case $G$ does not embed the dihedral group.

##  5 Simple groups

###### Theorem 5.1

Let $\mathcal{F}$ be a finite set of finite simple groups of size $n$ and $G$
be a minimum $\mathcal{F}$-cover. Let $N_{0}<N_{1}<\cdots<N_{k}=G$ be a
composition series of $G$ and $\mathcal{F}_{i}=\\{H\in\mathcal{F}:H$ is
isomorphic to a subgroup of $N_{i}/N_{i-1}\\}$. Then

  1. (a)

$k\leq n$.

  2. (b)

$\cup_{i=1}^{k}\mathcal{F}_{i}=\mathcal{F}$.

  3. (c)

$N_{i}/N_{i-1}$ is a minimum $\mathcal{F}_{i}$-cover.

  4. (d)

$\Pi_{i=1}^{k}N_{i}/N_{i-1}$ is a minimum $\mathcal{F}$-cover.

###### Proof

The proof is by induction on $k$. For $k=1$ all the statements are trivial.
Now assume $k\geq 2$. Let $\mathcal{F}^{\prime}=\\{H\in\mathcal{F}:H$ is
isomorphic to a subgroup of $N_{k-1}\\}$. Then every simple subgroup of $G$ is
isomorphic to a subgroup of $N_{k-1}$ or a subgroup of $G/N_{k-1}$. So
$\mathcal{F}=\mathcal{F}^{\prime}\cup\mathcal{F}_{k}$ Since $G$ is a minimum
$\mathcal{F}$-cover, so $\mathcal{F}^{\prime}$ and $\mathcal{F}_{k}$ are non
empty. Also $N_{k-1}$ is an $\mathcal{F}^{\prime}$-cover and $G/N_{k-1}$ is an
$\mathcal{F}_{k}$-cover. If $N_{k-1}$ is not a minimum
$\mathcal{F}^{\prime}$-cover and $M$ is a minimum $\mathcal{F}^{\prime}$-cover
then $M\times G/N_{k-1}$ is an $\mathcal{F}$-cover whose order is less than
$|G|$ which is a contradiction. Similarly $G/N_{k-1}$ is a minimum
$\mathcal{F}_{k}$-cover. So by induction $k-1\leq|\mathcal{F}^{\prime}|\leq
n-1$ which implies $k\leq n$. Also by induction
$\bigcup_{i=1}^{k-1}\mathcal{F}_{i}=\mathcal{F}^{\prime}$ and $N_{i}/N_{i-1}$
is a minimum $\mathcal{F}_{i}$-cover for $1\leq i\leq k-1$ and
$\Pi_{i=1}^{k-1}N_{i}/N_{i-1}$ is a minimum $\mathcal{F}^{\prime}$-cover. So
$\Pi_{i=1}^{k}N_{i}/N_{i-1}$ is a minimum $\mathcal{F}$-cover. $\Box$

###### Theorem 5.2

Let $M$ and $N$ be non-abelian simple groups, and $\mathcal{F}=\\{M,N\\}$. Let
$G$ be a minimum $\mathcal{F}$-cover. Then either

  1. (a)

$G=M\times N$; or

  2. (b)

$|G|\leq|M|\cdot|N|$ and $G$ is simple.

In particular, if there is an $\mathcal{F}$-cover of order less than
$|M|\cdot|N|$, then any minimum $\mathcal{F}$-cover is simple.

Both possibilities can occur. We give two examples before proving the theorem.

###### Example 5.3

Let $M=A_{5}$ and $N=\mathop{\mathrm{PSL}}(2,8)$. The orders of these groups
are $60$ and $504$. Their least common multiple is $2520$ and their product is
$30240$. The only simple groups with order divisible by $2520$ and not greater
than $30240$ are $A_{7}$, $A_{8}$ and $\mathop{\mathrm{PSL}}(3,4)$; none of
these embed $\mathop{\mathrm{PSL}}(2,8)$. By the theorem, the unique minimum
$\\{M,N\\}$-cover is $M\times N$.

###### Example 5.4

Let $M=A_{6}$ and $N=\mathop{\mathrm{PSL}}(2,7)$. Their orders are $360$ and
$168$, with least common multiple $2520$. There is a unique simple group of
order $2520$, namely $A_{7}$, which embeds both $M$ and $N$; so $A_{7}$ is the
unique minimum $\\{M,N\\}$-cover.

### Proof of Theorem 5.2

By Theorem 5.1, either $G$ is simple, or it has a composition series of length
$2$ with composition factors $M$ and $N$.

Suppose, without loss of generality, that $G$ has a normal subgroup isomorphic
to $M$ with quotient isomorphic to $N$. Hence $C_{G}(M)\lhd G$ and $M\cap
C_{G}(M)=Z(M)=\\{1\\}$. Each element of $G$ acts on $M$ by conjugation. A
consequence of the Classification of Finite Simple Groups is that the outer
automorphism group of $M$ is solvable. Since $G$ has no non-trivial solvable
quotient, we see that each element of $G$ induces an inner automorphism of
$M$. Let $g\in G$. Then there exists $m\in M$ such that for all $x\in M$, we
have $gxg^{-1}=mxm^{-1}$. So $m^{-1}g\in C_{G}(M)$ which implies $g\in
MC_{G}(M)$. Hence $G=MC_{G}(M)$. Thus $G$ has normal subgroups $M$ and
$C_{G}(M)$ intersecting trivially (and commuting), so is their direct product.
$\Box$

###### Corollary 5.5

There is a function $f$ such that, if $\mathcal{F}=\\{M,N\\}$ where $M$ and
$N$ are non-abelian finite simple groups with $|N|>f(|M|)$, then $M\times N$
is the unique minimum $\mathcal{F}$-cover.

###### Proof

Suppose not, and let $G$ be a minimum $\mathcal{F}$-cover. Then $G$ is simple,
and has a subgroup $N$ with index at most $|M|$. Now $G$ acts faithfully on
the cosets of $N$, and so it is embeddable in the symmetric group of degree
$|M|$, with $N$ as the point stabiliser. So $N$ is embeddable in the symmetric
group of degree $|M|-1$, and $|N|\leq(|M|-1)!$. $\Box$

###### Question 5.6

Is it possible for a set of two non-abelian finite simple groups to have two
non-isomorphic minimum covers?

If this happens for $\mathcal{F}=\\{M,N\\}$, then we must have either

  1. (a)

there are two simple groups of the same order (smaller than $|M|\cdot|N|$)
which are minimum $\mathcal{F}$-covers; or

  2. (b)

there is a simple group of order $|M|\cdot|N|$ which is a minimum
$\mathcal{F}$-cover.

Regarding (a), it is known from the Classification that the only pairs of
finite simple groups which have the same order are
$\\{\mathop{\mathrm{PSL}}(3,4),A_{8}\\}$ and
$\\{\mathrm{PSp}(2m,q),\mathrm{P}\Omega(2m+1,q)\\}$ for $m\geq 3$ and $q$ an
odd prime power. Regarding (b), we can pose another problem:

###### Question 5.7

Classify the triples $\\{M,N,G\\}$ of finite simple groups such that
$|M|\cdot|N|=|G|$.

###### Question 5.8

If it is true that cases (a) and (b) cannot occur, then pairs of finite simple
groups are classified into two types, as in Theorem 5.2. What can be said
about the relative frequency of the two types? Corollary 5.5 shows that, given
a finite simple group $M$, there are only finitely many simple groups $N$ such
that the minimum cover of $\\{M,N\\}$ is not the direct product.

##  6 Top and bottom

###### Theorem 6.1

Suppose that $\mathcal{X}$ is a subgroup-closed class of finite groups. Let
$\mathcal{F}$ be a finite set of finite groups, none of which have a non-
trivial $\mathcal{X}$-group as a quotient, and let $G$ be a minimal
$\mathcal{F}$-cover. Then $G$ has no non-trivial $\mathcal{X}$-group as a
quotient.

###### Proof

Suppose that $G/N\in\mathcal{X}$. Then for any group $H\in\mathcal{F}$,
$H/H\cap N\cong HN/N\leq G/N\in\mathcal{X}$. So $H/H\cap N\in\mathcal{X}$
which implies $H\subseteq N$.. By minimality of $G$, we have $N=G$. $\Box$

Applications:

  * •

Let $\mathcal{X}$ be the class of finite abelian groups. The condition that
$G$ has no non-trivial homomorphism to an $\mathcal{X}$-group means that $G$
is perfect. So we deduce that, if every group in $\mathcal{F}$ is perfect,
then any minimal $\mathcal{F}$-cover is perfect.

  * •

Let $\mathcal{X}$ be the class of finite solvable groups. The condition that
$G$ has no non-trivial homomorphism to an $\mathcal{X}$-group means that $G$
is equal to its solvable residual. So, if every group in $\mathcal{F}$ is
equal to its solvable residual, then the same is true of any minimal
$\mathcal{F}$-cover.

There is a dual result, as follows.

###### Theorem 6.2

Suppose that $\mathcal{X}$ is a subgroup-closed class of finite groups. Let
$\mathcal{F}$ be a finite set of finite groups, and suppose that no group in
$\mathcal{F}$ has a non-trivial normal $\mathcal{X}$-subgroup. Let $G$ be a
co-minimal cover of $\mathcal{F}$. Then $G$ has no non-trivial normal
$\mathcal{X}$-subgroup.

###### Proof

Let $G$ be a co-minimal cover of $\mathcal{F}$, and suppose that $G$ has a
normal $\mathcal{X}$-subgroup $N$. For each group $H\in\mathcal{F}$, we have
$H\cap N\in\mathcal{X}$. So $H\cap N=\\{1\\}$. Hence $H\cong H/H\cap N\cong
HN/N\leq G/N$. By co-minimality, $G/N\cong G$, so $N=\\{1\\}$. $\Box$

Again this gives applications:

  * •

Let $\mathcal{X}$ be the class of finite abelian groups. If no group in
$\mathcal{F}$ has a non-trivial abelian normal subgroup, then a co-minimal
$\mathcal{F}$-cover has no non-trivial abelian normal subgroup.

  * •

Let $\mathcal{X}$ be the class of finite solvable groups. The condition “no
non-trivial normal $\mathcal{X}$-subgroup” means that the solvable radical is
trivial. So, if all groups in $\mathcal{F}$ have trivial solvable radical,
then the same is true of a co-minimal cover.

##  7 Dual covers

The definitions earlier can be dualized.

Let $\mathcal{F}$ be a set of finite groups. A group $G$ is a _dual
$\mathcal{F}$-cover_ if every group in $\mathcal{F}$ is a quotient of $G$. We
say that a dual $\mathcal{F}$-cover $G$ is

  * •

_minimal_ if no proper quotient of $G$ is a dual $\mathcal{F}$-cover;

  * •

_co-minimal_ if no proper subgroup of $G$ is a dual $\mathcal{F}$-cover;

  * •

_strongly minimal_ if it is both minimal and co-minimal;

  * •

_minimum_ if no dual $\mathcal{F}$-cover has smaller order.

Note that a minimum dual cover is strongly minimal.

We have not investigated this concept except to note that, in the class of
abelian groups, subgroups and quotients coincide (because of duality for
abelian groups), and so (for example) an abelian group is a minimum dual cover
of a class of abelian groups if and only if it is a minimum cover.

###### Question 7.1

Investigate dual covers along the lines we have followed for covers.

##  8 Open problems

In addition to questions posed earlier, we conclude with a few more.

###### Question 8.1

For which classes $\mathcal{X}$ of groups, closed under the taking of
subgroups and direct product, is it true that, if $\mathcal{F}$ is a finite
set of $\mathcal{X}$-groups, then there is a minimum $\mathcal{F}$-cover which
is an $\mathcal{X}$-group? We showed earlier that this is true for cyclic
groups and for nilpotent groups; but we have been unable to resolve it for for
abelian or solvable groups.

###### Question 8.2

Can we characterise sets $\mathcal{F}$ for which the order of a minimum
$\mathcal{F}$-cover is the least common multiple of the orders of the groups
in $\mathcal{F}$? Is it true that any prime divisor of the order of a minimum
$\mathcal{F}$-cover must divide the order of at least one group in
$\mathcal{F}$?

###### Question 8.3

For which groups $G$ is it the case that $G$ is not a minimal cover of the set
of its proper subgroups (equivalently, the set of its maximal subgroups)? We
note that this is false if all the maximal subgroups of $G$ are isomorphic;
such groups were determined by Ćepulić [1]. A related question: Is there any
group $G$ with two maximal subgroups $M,N$ such that $N$ is isomorphic to a
proper subgroup of $M$?

## References

  * [1] V. Ćepulić, On finite 2-groups all of whose subgroups are mutually isomorphic, Science in China Series A: Mathematics 52 (2009), 254–260.
  * [2] P. G. L. Dirichlet, Werke (ed. L. Kronecker), Vol. ii (1849), pp. 49–66. Reprinted Wentworth Press, 2018.
  * [3] The GAP Group, GAP – Groups, Algorithms, and Programming, Version 4.12.2; 2022. (https://www.gap-system.org)
  * [4] Marshall Hall Jr., The Theory of Groups, MacMillan, New York, 1959.
  * [5] Graham Higman, Enumerating $p$‐groups. I: Inequalities, Proc. London Math. Soc. (3) 10 (1960), 24–30.
  * [6] D. J. S. Robinson, A Course in the Theory of Groups (second edition), Springer, New York, 1996.
  * [7] The On-Line Encyclopedia of Integer Sequences, https://oeis.org
  * [8] Charles C. Sims, Enumerating $p$‐groups, Proc. London Math. Soc. (3) 15 (1965), 151–166.
  * [9] M. Suzuki, Group Theory I, Grundlehren der math. Wissenschaften 247, Springer-Verlag, Berlin, 2014.