11institutetext: Indian Institute of Technology Gandhinagar, Gandhinagar
22institutetext: Indian Institute of Information Technology, Una, India
22email<EMAIL_ADDRESS>
22email<EMAIL_ADDRESS>
# Linear Space Data Structures for Finite Groups with Constant Query-time

Bireswar Das 11 Anant Kumar 11 Shivdutt Sharma 22 Dhara Thakkar Funded by
CSIR-UGC NET JRF Fellowship.11

###### Abstract

A finite group of order $n$ can be represented by its Cayley table. In the
word-RAM model the Cayley table of a group of order $n$ can be stored using
$O(n^{2})$ words and can be used to answer a multiplication query in constant
time. It is interesting to ask if we can design a data structure to store a
group of order $n$ that uses $o(n^{2})$ space but can still answer a
multiplication query in constant time.

We design a constant query-time data structure that can store any finite group
using $O(n)$ words where $n$ is the order of the group.

Farzan and Munro (ISSAC 2006) gave an information theoretic lower bound of
$\Omega(n)$ on the number of words to store a group of order $n$. Since our
data structure achieves this lower bound and answers queries in constant time,
it is optimal in both space usage and query-time.

A crucial step in the process is essentially to design linear space and
constant query-time data structures for nonabelian simple groups. The data
structures for nonableian simple groups are designed using a lemma that we
prove using the Classification Theorem for Finite Simple Groups (CFSG).

Related Version: A preliminary version of this article appeared in the
proceedings of the 39th International Symposium on Theoretical Aspects of
Computer Science (STACS 2022).

###### Keywords:

Compact Data Structures Space Efficient Representations Finite Groups Simple
Groups Classification Theorem for Finite Simple Groups

##  1 Introduction

The Cayley table of a group of order $n$ is a two dimensional table whose
$(i,j)$th entry is the product of the $i$th and $j$th element of the group. In
the word-RAM model while it takes $O(n^{2})$ words to store the Cayley table
of a group of order $n$, a multiplication query can be answered in constant
time by accessing the appropriate location of the table.

For many computational problems in group theory the input group is given by
its Cayley table. Some of these problems include the minimum generating set
problem, various problems in property testing, the group factoring problem,
and the group isomorphism problem [20, 2, 17, 21]. Among these, the group
isomorphism problem is probably the most prominent one because of its
unresolved complexity status despite years of extensive research [5, 15, 3, 6,
22, 16].

The Cayley table is very fast in terms of query processing but it takes
quadratic space to store a group. It is interesting to ask if we can design a
data structure for finite groups using $o(n^{2})$ space111In this paper we use
the word-RAM model. The space used by a data structure or an algorithm refers
to the number of words used by them. which can still answer multiplication
query in constant time. We note that while quasigroups, and semigroups can
also be stored using their Cayley tables, it is not possible to store
quasigroups, and semigroups using $o(n^{2})$ space. This is simply because the
numbers of quasigroups, and semigroups are too large [28, 19] and the
information theoretic lower bound is $\Omega(n^{2}\log n)$ bits or
$\Omega(n^{2})$ words.

Das et al. [11] showed that for any finite group $G$ of order $n$ and for any
$\delta\in[1/\log{n},1]$, a data structure can be constructed for $G$ that
uses $O(n^{1+\delta}/\delta)$ space and answers a multiplication query in time
$O(1/\delta)$. Their result implies that there exist constant query-time data
structures for finite groups of order $n$ that use $O(n^{1.01})$ space.
However, the result cannot be used to design a constant query-time data
structure even if we are allowed to use $\Theta(n.polylog(n))$ space.

In this paper we design constant query-time data structures for finite group
that can be stored using $O(n)$ words where $n$ is the order of the group. An
information theoretic argument by Farzan and Munro shows that a lower bound to
store a group of order $n$ is $\Omega(n\log n)$ bits or $\Omega(n)$ words
[13]. Our data structure is optimal in the sense that it achieves the lower
bound. A data structure that achieves the optimum information theoretic lower
bound asymptotically is known as _a compact data structure_. Therefore our
data structure is a constant query-time compact data structure for finite
groups. We note that compact query-time data structures were designed for some
restricted classes of groups such as abelian groups and Dedekind groups [10].

In the process of designing the data structure we first prove two results,
which we call _extension theorems_ , on the construction of data structures
for a group when we already have a data structure for a subgroup of the given
group. The extra space used by the newly constructed data structure depends on
the index of the subgroup in one of the results and the structure222The
subgroup needs to be normal and quotient needs to be cyclic. of the subgroup
in the other result. This indicates that finding suitable subgroups of a group
might be useful.

The Jordan-Hölder theorem provides us with a supply of subgroups in the form
of composition series. In our process we try to pick some suitable subgroups
that are elements of the composition series of the given group. However,
picking suitable groups is not always possible. This happens, as we will see
in Section 4, when there is a “large” composition factor sitting in a certain
position of the composition series. The composition factors are simple groups.
In a sense the hard cases for constructing the data structure are for the
simple groups.

Simple groups are sometimes considered as the building blocks for finite
groups. The Classification Theorem for Finite Simple Groups (CFSG) is one of
the most important theorems in group theory. Informally, this theorem
classifies the finite simple groups into cyclic groups, alternating groups,
certain groups of Lie-type and into 26 sporadic simple groups. The precise
statement of the theorem could be queries found in Section 5. Except for the
26 sporadic simple groups the other group classes are infinite. We use CFSG to
prove a key lemma that allows us to handle the case for the nonabelian simple
groups.

We note that for solvable groups the design of the data structure is
_independent_ of CFSG. The composition factors of a solvable group are cyclic
of prime order. Such cases are handled using one of the extension theorems
proved in Section 3.

_Related work_ : Farzan and Munro [13] gave a succinct representations for
finite abelian groups in a specific model of computation. In their model _a
compression algorithm_ first produces labels of each group element. The
queries are processed by a _query processing unit_ which is similar to the
word-RAM model. However, along with the common arithmetic, logical and
comparison operations the query processing unit can also perform bit-reversal
in constant time. A user issuing a query, supplies the labels of two group
elements that were generated by the compression algorithm to the query
processing unit which then returns the label of the product of the two
elements.

Das et al. [11] and Das and Sharma [10] have used Erdös-Réyni cube generating
sequences, Remak-Krull-Schmidt decomposition and the structure of
indecomposable groups to design their space and query-time efficient data
structures. Our approach is quite different in the sense that we use the
extension theorems (Section 3) and the Classification Theorem for Finite
Simple groups to design the data structures.

_Remark_ : There are several ways to represent a finite group apart from the
Cayley table representation. The permutation group representation, the
polycyclic presentations and the generator-relator presentations are some of
the common group representations. These representations are often
incomparable. For example in the generator-relator presentation we can
represent infinite groups. However, many problems such as the membership
testing, testing if a group is finite becomes undecidable in the generator-
relator presentation (c.f. [27]). In the permutation group representation the
membership testing takes superlinear time in terms of the degree of the
representation and polylogarithmic in the order of the group [26, 25, 14]. We
contrast this with the Cayley table representation where membership testing
can be done in constant time since the elements are known and are already used
as row and column indices of the Cayley table. In the Cayley representation
the user knows the labels or the names of each group element explicitly and
has a direct access to each element. The labels of the elements are often
taken to be $1,2,\ldots,n$ where $n$ is the order of the group. The situation
is quite different for permutation group representation, polycyclic
presentation or generator-relator presentation. In these cases the user does
not have an explicit representation for each element.

##  2 Preliminary

In this section we recall some definitions and notations which we use in this
paper. In this paper we only consider finite groups. The number of elements in
a group $G$ is called the _order of $G$_ and is denoted by $|G|$. A group $G$
is abelian if $g_{1}g_{2}=g_{2}g_{1}$ for all $g_{1},g_{2}\in G.$ For a
subgroup $H$ of $G$ and $g\in G$, the set $gH=\\{gh\,|\,h\in H\\}$ is called a
left coset. Similarly, we can define right coset of $G$. The number of the
left (or right) cosets of $H$ in $G$ is called the _index of $H$ in $G$_ and
is denoted by $[G:H].$ A _left traversal_ of $H$ in $G$ is a set containing
exactly one element from each left coset and similarly we can define right
traversals. The size of left (right) traversal is the same as the index
$[G:H].$ For $g\in G$, the set $gHg^{-1}=\\{gag^{-1}\,|\,a\in H\\}$ is called
a conjugate of the subgroup $H$. A subgroup $H$ of G is said to be _normal_ in
$G$ (denoted $H\trianglelefteq G$) if $gHg^{-1}=H$ for all $g\in G.$ We define
the _normalizer_ of $H$ in $G$ to be the set $N_{G}{(H)}=\\{g\in
G\,|\,gHg^{-1}=H\\}.$ Note that, $N_{G}{(H)}$ is the largest subgroup in $G$
in which $H$ is normal.

A group $G$ is called _simple_ if $G$ has no nontrivial normal subgroup. The
Classification Theorem of Finite Simple Groups states that all the finite
simple groups can be classified into the following five classes: (1) cyclic
groups of prime order, (2) alternating groups, (3) classical groups, (4)
exceptional groups of Lie type and (5) 26 sporadic simple groups.

We list all the classes of the finite simple groups later in the
Classification Theorem for Simple Groups in Section 5. If $G$ is a finite
simple group of Lie-type over $\mathbb{F}_{q}$ where $q$ is a power of some
prime $p$, the Borel subgroup $B$ of $G$ is defined as the semidirect product
of the Sylow $p$-subgroup of $G$ with the maximal split torus $T$. The Borel
subgroup is also the normalizer of the Sylow $p$-subgroup of the finite simple
group (see [8], [29]).

For the purpose of this paper it might be sufficient to know some results on
the _orders_ of certain subgroups of simple groups. The reader may choose to
skip the details of the structure of these groups. We indicate what kind of
subgroups we are interested in and the results regarding the order of those
subgroups as and when required. An interested reader may refer to the books by
Carter [8], Wilson [29], or Aschbacher [4] for more details.

######  Definition 1 (see e.g., [12])

A _subnormal series_ of a group $G$ is chain of subgroups

$1=G_{k}\leq G_{k-1}\leq\dots\leq G_{1}\leq G_{0}=G$

such that $G_{i}\trianglelefteq G_{i-1},$ for all $i.$

######  Definition 2 (see e.g., [12])

In a group $G$ a sequence of subgroups

$1=G_{k}\leq G_{k-1}\leq\dots\leq G_{1}\leq G_{0}=G$

is called a _composition series_ if $G_{i}\trianglelefteq G_{i-1}$ and
$G_{i-1}/G_{i}$ is simple for all $i\in[k].$ Here, $k$ is the _composition
length_ of $G.$

######  Theorem 2.1 (Jordan-Hölder Theorem see e.g., [12])

Let $G$ be a finite group with $G\neq 1$. Then

  1. (i)

$G$ has a composition series.

  2. (ii)

The composition factors in a composition series are unique, namely, if
$1=N_{r}\leq N_{r-1}\leq\cdots\leq N_{1}\leq N_{0}=G$ and $1=M_{s}\leq
M_{s-1}\leq\cdots\leq M_{1}\leq M_{0}=G$ are two composition series for $G$,
then $r=s$ and there is some permutation $\pi$ of $\\{1,2,\dots,r\\}$ such
that,

$\frac{M_{\pi(i)}}{M_{\pi(i)+1}}\cong\frac{N_{i}}{N_{i+1}},\text{for}\,1\leq
i\leq r.$

######  Theorem 2.2 (Correspondence Theorem see e.g., [23])

Let K $\trianglelefteq$ G and let $v:G\longrightarrow G/K$ be the canonical
map i.e. $v(g)=Kg$ for all $g.$ Then $S\mapsto v(S)=S/K$ is a bijection from
the family of all those subgroups S of G which contain K to the family of all
the subgroups of $G/K$.

Model of computation : In this paper, we use an abstract model of computation
known as the word-RAM model. In this model, data is stored in resisters and
memory units. Each memory unit and resister can store $O(\log n)$ bits where
$n$ is the size of the input. The unit of storage is called _word_. The
machine in the word-RAM model can access a word and do the usual arithmetic,
logical, and comparison operations in constant time. The input size for our
purpose is the order of the group. Without loss of generality, we can assume
that the elements of groups are $1,2,3,...,n$. Thus, every group element can
be stored in a word and can be accessed in constant time.

There are two phases in the construction of a data structure: _the
preprocessing phase_ and _the query phase_. In the preprocessing phase, we
assume that we have been given a finite group by its Cayley table. Using the
Cayley table, we construct a data structure that consists of some arrays and
tables. In the query phase, we process multiplication queries. In a
multiplication query, two group elements $g_{1}$ and $g_{2}$ are given by the
user. The task is to find the product of $g_{1}$ and $g_{2}$. In this phase,
the data structure constructed in the preprocessing phase is accessed to
answer the query. The time taken to answer a single query is called the query-
time.

The time and space used in preprocessing stage to build the data structure are
generally not considered. However we show that the data structure in our case
can be computed in polynomial time. Our primary concern is to consider the
space used by the constructed data structure and the time it takes to answer a
query to multiply the group elements.

###### Definition 3

Let $G$ be a group and $s$ and $t$ be two positive real numbers. We say that
$G$ has an $(s,t)$-data structure, if $G$ can be stored in a data structure
that uses at most $s$ space and can answer a multiplication query in time at
most $t$.

###### Definition 4

Let $\mathcal{G}$ be a class of group and let
$s,t:\mathbb{N}\rightarrow\mathbb{R}_{\geq 0}$ be two functions. If for every
group $G\in\mathcal{G}$ of order $n$ there is a data structure that uses
$O(s(n))$ space to store $G$ and can answer a multiplication query in time at
most $O(t(n))$ then we say that $\mathcal{G}$ has an $(O(s(n)),O(t(n)))$-data
structure.

##  3 Extension Theorems

In this section, we discuss how to use data structures for subgroups to build
new data structures for groups containing the subgroups.

###### Theorem 3.1

There exist positive constants $c$ and $d$ such that for any group $G$ and a
subgroup $H$ of $G$ if $H$ has an $(s,t)$-data structure for some $s$ and $t$
then $G$ has an $(s+c([G:H]^{2}+|G|),2t+d)$-data structure.

###### Proof

First we fix a left traversal $L$ and a right traversal $R$ of $H$ in $G$.
Each $g\in G$ can be uniquely written as $g=hr$ where $h\in H$ and $r\in R$.
Thus we can define functions $s_{R}:G\longrightarrow H$ and
$c_{R}:G\longrightarrow R$ such that $g=s_{R}(g)c_{R}(g)$. Similarly we can
define $c_{L}:G\longrightarrow L$ and $s_{L}:G\longrightarrow H$ such that
$g=c_{L}(g)s_{L}(g)$. We can store these four functions in four arrays each of
length $|G|$.

Suppose we need to find the product of $g_{1}$ and $g_{2}$. Note that,

$g_{1}g_{2}=c_{L}(g_{1})s_{L}(g_{1})s_{R}(g_{2})c_{R}(g_{2}).$

Since $s_{L}(g_{1}),s_{R}(g_{2})\in H$, we can use the data structure for $H$
to find $s_{L}(g_{1})s_{R}(g_{2})$ within time $t$. Let
$h_{1}=s_{L}(g_{1})s_{R}(g_{2})$. Therefore, we can write
$g_{1}g_{2}=c_{L}(g_{1})h_{1}c_{R}(g_{2})$.

Given $l\in L$ and $h\in H$, we know that there exist unique elements
$h^{\prime}\in H$ and $r\in R$ such that $lh=h^{\prime}r$. Thus, we can define
two functions $Flip_{H}:L\times H\longrightarrow H$ and $Flip_{R}:L\times
H\longrightarrow R$ such that $lh=Flip_{H}(l,h)Flip_{R}(l,h)$. We can store
$Flip_{H}$ and $Flip_{R}$ in two $2$-dimensional arrays using space linear in
$|H\times L|=|G|$. With the help of these functions, we can write

$g_{1}g_{2}=Flip_{H}(c_{L}(g_{1}),h_{1})Flip_{R}(c_{L}(g_{1}),h_{1})c_{R}(g_{2})=h_{2}r_{1}r_{2}$

where $h_{2}=Flip_{H}(c_{L}(g_{1}),h_{1})$,
$r_{1}=Flip_{R}(c_{L}(g_{1}),h_{1})$ and $r_{2}=c_{R}(g_{2})$.

Again we use the fact that any element $g$ of $G$ can be uniquely written as
$g=hr$ where $h\in H$ and $r\in R$ to define the functions $Cross_{H}:R\times
R\longrightarrow H$ and $Cross_{R}:R\times R\longrightarrow R$ such that for
all $r,r^{\prime}\in R$ we have
$rr^{\prime}=Cross_{H}(r,r^{\prime})Cross_{R}(r,r^{\prime})$. Note that we can
store these functions in two $2$-dimensional arrays each requiring size linear
in $|R\times R|=(|G|/|H|)^{2}$. With the help of these functions we can write

$g_{1}g_{2}=h_{2}Cross_{H}(r_{1},r_{2})Cross_{R}(r_{1},r_{2})=h_{2}h_{3}r_{3}$

where $Cross_{H}(r_{1},r_{2})=h_{3}$ and $r_{3}=Cross_{R}(r_{1},r_{2})$.

Again we can use the data structure for $H$ to compute the product
$h_{4}=h_{2}h_{3}$ within time $t$. Thus $g_{1}g_{2}=h_{4}r_{3}$. Finally, we
define a function $Fuse:H\times R\longrightarrow G$ simply as $Fuse(h,r)=hr$
for all $h\in H$ and $r\in R$. Clearly, a $2$-dimensional array to store
$Fuse$ would take space linear in $|H\times R|=|G|$. Thus, to produce the
final result we just return $g_{1}g_{2}=Fuse(h_{4},r_{3})$.

All the functions except for $Cross_{R}$ and $Cross_{H}$ take space linear in
$|G|$, while $Cross_{R}$ and $Cross_{H}$ take space linear in $(|G|/|H|)^{2}$.
The data structure for $H$ takes space at most $s$. Therefore, the total space
required is linear in $|G|+(|G|/|H|)^{2}$. We note that each function defined
in this proof is queried exactly once. Thus, the time to query all the nine
functions is bounded by some constant d. Additionally, the time taken to query
the data structure for $H$ is at most $2t$. Therefore, we have the required
data structure for $G$.

###### Remark 1

We note that if the $(s,t)$-data structure for $H$ is given then the above
data structure for $G$ can also be _computed_ in polynomial time.

An immediate corollary of the above theorem is the following.

###### Corollary 1

Let $0<c_{1}\leq c_{2}$ be two constants. Let $\mathcal{G}_{c_{1},c_{2}}$ be
the class of groups $G$ that has a subgroup H with $c_{1}\sqrt{|G|}\leq|H|\leq
c_{2}\sqrt{|G|}$. Then $\mathcal{G}_{c_{1},c_{2}}$ has $(O(n),O(1))$-data
structures.

###### Proof

The Cayley table for $H$ takes size at most $c_{2}^{2}|G|$ and answers queries
in constant time. Since $|G|/|H|\leq(1/c_{1})\sqrt{|G|}$, we have
$(|G|/|H|)^{2}\leq(1/c_{1})^{2}|G|$. Hence the result follows from Theorem
3.1.

In the next theorem we show how to use the data structure for a normal
subgroup of a group to build a data structure for the group when the quotient
group is cyclic.

###### Theorem 3.2

There are positive constants $c$ and $d$ such that for every group $G$ and any
normal subgroup $N$ of $G$, if $G/N$ is cyclic and $N$ has an $(s,t)$-data
structure for some $s$ and $t$, then $G$ has an $(s+c|G|,2t+d)$-data
structure.

###### Proof

Since $G/N$ is cyclic it is generated by an element $g_{0}N$ where $g_{0}\in
G$. The cosets of $N$ in $G$ are $N,g_{0}N,g_{0}^{2}N,\ldots,g_{0}^{k-1}N$
where $k$ is the order of the group $G/N$, i.e., $k=[G:N]$. Clearly,
$k\leq|G|$. Let $S=\\{0,1,\ldots,k-1\\}$.

The set $\\{g_{0}^{0},g_{0}^{1},\ldots,g_{0}^{k-1}\\}$ is a left as well as a
right traversal of $N$ in $G$. Hence any element $g$ could be uniquely written
as $g=g_{0}^{r}n=n^{\prime}g_{0}^{r}$ for some $r\in S$ and $n,n^{\prime}\in
N$. This enables us to define functions $e:G\longrightarrow S$,
$s_{R}:G\longrightarrow N$ and $s_{L}:G\longrightarrow N$ such that for all
$g\in G$

$g=g_{0}^{e(g)}s_{R}(g)=s_{L}(g)g_{0}^{e(g)}.$

These three functions could be stored in arrays each having size $|G|$. To
multiply $g_{1}$ and $g_{2}$ we first observe that
$g_{1}g_{2}=g_{0}^{e(g_{1})}s_{R}(g_{1})s_{L}(g_{2})g_{0}^{e(g_{2})}$. These
expression could be obtained by querying each of the functions once. The
product $n_{1}=s_{R}(g_{1})s_{L}(g_{2})$ can be obtained using the data
structure for $N$ within query-time $t$. Thus
$g_{1}g_{2}=g_{0}^{\alpha}n_{1}g_{0}^{\beta}$, where $\alpha=e(g_{1})$ and
$\beta=e(g_{2})$.

Next we define a function $Flip:N\times S\longrightarrow N$ with the property
that for all $n\in N$ and $i\in S$, $ng_{0}^{i}=g_{0}^{i}Flip(n,i)$. In other
words, $Flip(n,i)$ is just $g_{0}^{-i}ng_{0}^{i}$. This function can be stored
in space linear in $|N\times S|=|G|$. Now we can write
$g_{1}g_{2}=g_{0}^{\alpha}g_{0}^{\beta}Flip(n_{1},\beta)=g_{0}^{\alpha+\beta}n_{2}$
where $n_{2}=Flip(n_{1},\beta)$.

Next we compute $g_{0}^{\alpha}g_{0}^{\beta}=g_{0}^{\alpha+\beta}$. Observe
that $\alpha+\beta\in\\{0,1,\ldots,2k-2\\}$. We define two functions
$red_{e}:\\{0,1,\ldots,2k-2\\}\longrightarrow S$ and
$red_{N}:\\{0,1,\ldots,2k-2\\}\longrightarrow N$ such that
$g_{0}^{\ell}=g_{0}^{red_{e}(\ell)}red_{N}(\ell)$ for all
$\ell\in\\{0,\ldots,2k-2\\}$. Note that for $\ell<k$, $red_{e}(\ell)=\ell$ and
$red_{N}(\ell)=id$. These two functions can be stored using space linear in
$k$. Since $k\leq|G|$, the space required is at most linear in $G$.

Therefore,

$g_{1}g_{2}=g_{0}^{\alpha+\beta}n_{2}=g_{0}^{red_{e}(\alpha+\beta)}red_{N}(\alpha+\beta)n_{2}.$

As before the product $n_{3}$ of $red_{N}(\alpha+\beta)$ and $n_{2}$ can be
found using the data structure for $N$. Let $red_{e}(\alpha+\beta)=\gamma$.
Hence, $g_{1}g_{2}=g_{0}^{\gamma}n_{3}$.

We finally define a function $Fuse:S\times N\longrightarrow G$ as
$Fuse(i,n)=g_{0}^{i}n$ for all $i\in S$ and $n\in N$. Clearly, the function
$Fuse$ can be stored using space linear in $|G|$.

The product $g_{1}g_{2}$ is just $Fuse(\gamma,n_{3})$.

Each function defined in this proof takes space linear in $|G|$ and the data
structure for $N$ takes space at most $s$. Each function is queried exactly
once and the data structure for $N$ is queried twice. This proves the theorem.

###### Remark 2

This is similar to Remark 1. In this case too, if the data structure for $H$
in Theorem 3.2 is given then the data structure for $G$ can be computed in
polynomial time.

##  4 Compact Data Structures for Finite Groups

Let $G$ be a group of order $n$. Our goal is to design a constant query-time
data structure for $G$ of size linear in $n$. We first consider a composition
series $1=G_{k}\lhd\ldots G_{1}\lhd G_{0}=G$ of $G$. In case there is a
subgroup $G_{i}$ in the composition series with size within a constant factor
of $\sqrt{n}$, we can apply Corollary 1 to obtain a $(O(n),O(1))$-data
structure for $G$. Otherwise we consider the smallest subgroup $G_{i}$ of
order more than $\sqrt{n}$. Note that here $|G_{i+1}|$ is at most $\sqrt{n}$
and therefore $G_{i+1}$ will have its Cayley table of size at most $n$. This
Cayley table can be used to answer a multiplication query involving elements
in $G_{i+1}$ in constant time.

Now we consider the composition factor $G_{i}/G_{i+1}$. This quotient is a
simple group. If this is an abelian group it must be cyclic (of prime order)
and we can use Theorem 3.2 to get a data structure for $G_{i}$. Then an
application of Theorem 3.1 with $G$ and its subgroup $G_{i}$ will give us the
required data structure for $G$.

The nontrivial case is when $G_{i}/G_{i+1}$ is nonabelian. This is where we
use the Classification Theorem of Finite Simple Groups. The classification
theorem allows us to split the nonabelian case into various subcases. In each
of the subcases we show that we can insert two subgroups $G_{i_{2}}$ and
$G_{i_{1}}$ such that $G_{i+1}<G_{i_{2}}<G_{i_{1}}<G_{i}$ in such a manner
that the indices $[G_{i_{2}}:G_{i+1}]$, $[G_{i_{1}}:G_{i_{2}}]$ and
$[G_{i}:G_{i_{1}}]$ are all “small”. Since $G_{i+1}$ already has a constant
query-time data structure (namely its Cayley table) of size linear in $n$,
this allows us to use Theorem 3.1 successively to the group and subgroup pairs
$(G_{i_{2}},G_{i+1})$, $(G_{i_{1}},G_{i_{2}})$, and $(G_{i},G_{i_{1}})$ to
obtain a constant query-time data structure for $G_{i}$ of size linear in $n$.
Finally, another application of Theorem 3.1 with $G$ and its subgroup $G_{i}$
will give us the required data structure for $G$.

###  4.1 Solvable Finite Groups

In this subsection we consider the class $\mathcal{G}_{solv}$ of finite
solvable groups. We do this case first before going to the general case for
the class of all finite groups because it is independent of the Classification
Theorem for Finite Simple Groups.

###### Theorem 4.1

The class $\mathcal{G}_{solv}$ has $(O(n),O(1))$-data structures.

###### Proof

Let $G$ be a group and $1=G_{k}\lhd\ldots G_{1}\lhd G_{0}=G$ be a composition
series of $G$. Let $n=|G|$.

_Case 1_ : There is $i$ such that $\sqrt{n}/2\leq|G_{i}|\leq\sqrt{n}$. We
simply apply Corollary 1 to get the desired data structure.

_Case 2:_ There is no $i$ such that $\sqrt{n}/2\leq|G_{i}|\leq\sqrt{n}$. Let
$i$ be the largest index such that $\sqrt{n}<|G_{i}|$. We will have
$|G_{i+1}|<\sqrt{n}/2$. The Cayley table for $G_{i+1}$ has at most $n/4$
entries. Since $G$ is solvable $G_{i}/G_{i+1}$ is cyclic of prime order. This
allows us to use Theorem 3.2 to obtain a constant query-time data structure
for $G_{i}$ which is linear in $n$. Next we observe that $[G:G_{i}]$ is at
most $\sqrt{n}$. If we apply Theorem 3.1 on $G$ and its subgroup $G_{i}$ we
get the required data structure for $G$.

Since a composition series of a group can be computed in polynomial time, it
is easy to check that the data structure in Theorem 4.1 can be constructed in
polynomial time.

###  4.2 The General Case

Before considering the case for general finite groups we need the following
result for nonabelian simple groups.

###### Lemma 1

There are positive constants $b_{1}$ and $b_{2}$ such that for any nonabelian
simple group $H$ there exist subgroups $H_{1}$ and $H_{2}$ such that $1\leq
H_{2}\leq H_{1}\leq H$ and $|H_{2}|\leq\sqrt{|H|}$, $[H:H_{1}]\leq
b_{1}\sqrt{|H|}$, and $[H_{1}:H_{2}]\leq b_{2}\sqrt{|H|}$.

###### Proof

The proof uses the Classification Theorem of Finite Simple Group (CFSG). The
proof idea is given in Section 5 and the details are given in the Appendix.

Next we prove the main theorem of the paper. We note that Case 2 in the proof
of the following theorem can be viewed as a generalized version of the problem
of designing linear space and constant query-time data structure for
nonableian simple groups.

###### Theorem 4.2

The class $\mathcal{G}_{fin}$ of all finite groups has $(O(n),O(1))$-data
structures.

###### Proof

Let $G$ be a group of order $n$. We start by considering a composition series
$1=G_{k}\lhd\ldots G_{1}\lhd G_{0}=G$ be a composition series of $G$.

_Case 1:_ This is the case when there is $i$ such that
$\sqrt{n}/2\leq|G_{i}|\leq\sqrt{n}$. This case is exactly similar to the case
for solvable groups.

_Case 2:_ As before in this case we assume that there is no composition series
element $G_{i}$ with order more that $\sqrt{n}/2$ but less than $\sqrt{n}$.
Let $i$ be the largest index such $\sqrt{n}<|G_{i}|$. We will then have
$|G_{i+1}|<\sqrt{n}/2$. Clearly, the Cayley table of $G_{i+1}$ will have at
most $n/4$ entries. Since $[G:G_{i}]<\sqrt{n}$, by Theorem 3.1 it is enough to
design constant query-time data structure for $G_{i}$ of size linear in $n$.
In the rest of the proof we therefore concentrate on designing a constant
query-time data structure for $G_{i}$ that uses $O(n)$ space.

If the composition factor $G_{i}/G_{i+1}$ is abelian then we are again in the
same situation as in the second case of solvable groups. Therefore we assume
that $G_{i}/G_{i+1}$ is nonabelian.

We apply Lemma 1 to $H=G_{i}/G_{i+1}$ to obtain subgroups $H_{1}$ and $H_{2}$
such that $1\leq H_{2}\leq H_{1}\leq H=G_{i}/G_{i+1}$. By the correspondence
theorem of groups, $H_{1}$ and $H_{2}$ will be of the form $G_{i_{1}}/G_{i+1}$
and $G_{i_{2}}/G_{i+1}$ respectively for some subgroups $G_{i_{1}}$ and
$G_{i_{2}}$ such that $G_{i+1}\leq G_{i_{2}}\leq G_{i_{1}}\leq G_{i}$. From
Lemma 1 we have $[H_{1}:H_{2}]\leq b_{2}|H|$. Since, $H_{1}=G_{i_{1}}/G_{i+1}$
and $H_{2}=G_{i_{2}}/G_{i+1}$, we have
$[G_{i_{1}}/G_{i+1}:G_{i_{2}}/G_{i+1}]\leq b_{2}\sqrt{|G_{i}/G_{i+1}|}\leq
b_{2}\sqrt{n}$.

Therefore, $[G_{i_{1}}:G_{i_{2}}]\leq b_{2}\sqrt{n}$. Similarly,
$[G_{i}:G_{i_{1}}]\leq b_{1}\sqrt{n}$. Again from Lemma 1, we have
$H_{2}\leq\sqrt{|H|}$. This implies,
$[G_{i_{2}}:G_{i+1}]\leq\sqrt{|G_{i}/G_{i+1}|}\leq\sqrt{n}$.

Since $G_{i+1}$ has a Cayley table of size at most $n$ and
$[G_{i_{2}}:G_{i+1}]\leq\sqrt{n}$, we will have a constant query-time data
structure for the subgroup $G_{i_{2}}$ of size at most $n$ by Theorem 3.1.
Since $[G_{i_{1}}:G_{i_{2}}]\leq b_{2}\sqrt{n}$ and $[G_{i}:G_{i_{1}}]\leq
b_{1}\sqrt{n}$, another two applications of Theorem 3.1 with the group and
subgroup pairs $(G_{i_{1}},G_{i_{2}})$ and $(G_{i},G_{i_{1}})$ will give a
data structure for $G_{i}$ of size linear in $n$ which can answer a
multiplication query in constant time.

A discussion on how to construct the above data structure in polynomial time
is given at the end of Section 5.

##  5 Proof Sketch for Lemma 1

In this section we sketch the proof idea behind Lemma 1. We first state the
Classification Theorem of Finite Simple Groups.

######  Theorem 5.1 ([29])

(The Classification Theorem of Finite Simple Group)

Every finite simple group is isomorphic to one of the following:

  1. (i)

a cyclic group $C_{p}$ of prime order $p$;

  2. (ii)

an alternating group $A_{m},$ for $m\geq 5$;

  3. (iii)

a classical group;

    1. (a)

linear: $A_{\rm m}(q)(\text{or}\,\,{\rm PSL}_{{\rm m}+1}(q)),{\rm m}\geq 1$,
except ${\rm PSL}_{2}(2)$ and ${\rm PSL}_{2}(3)$;

    2. (b)

unitary: ${}^{2}A_{\rm m}(q^{2})(\text{or}\,{\rm PSU}_{{\rm m}+1}(q))\,,{\rm
m}\geq 2,$ except ${\rm PSU}_{3}(2)$;

    3. (c)

symplectic: $C_{\rm m}(q))(\text{or~{}}\,{\rm PS}_{{\rm p}_{2{\rm
m}}}(q)),{\rm m}\geq 2$ except ${{\rm PS}_{p}}_{4}(2)$;

    4. (d)

orthogonal: $B_{\rm m}(q)(\text{or~{}}\,{\rm P}\Omega_{2{\rm m}+1}(q)),{\rm
m}\geq 3,q$ odd;

$D_{\rm m}(q)(\text{or~{}}\,{\rm P}\Omega_{2{\rm m}}^{+}(q)),{\rm m}\geq 4$;

${}^{2}D_{\rm m}(q^{2})(\text{or~{}}\,{\rm P}\Omega_{2{\rm m}}^{-}(q))\,,{\rm
m}\geq 4$

where $q$ is a power $p^{a}$ of some prime;

  4. (iv)

an exceptional group of Lie type:

$\rm{G_{2}(q),q\geq
3;F_{4}(q);E_{6}(q);^{2}E_{6}(q);^{3}D_{4}(q);E_{7}(q);E_{8}(q)\,\,\text{or}}$

where $q$ is a power $p^{a}$ of some prime;

$\rm{{}^{2}B_{2}(2^{2m+1})},{\rm m}\geq 1;^{2}G_{2}(3^{2{\rm m}+1}),{\rm
m}\geq 1;^{2}F_{4}(2^{2{\rm m}+1}),{\rm m}\geq 1$

or the Tits group ${}^{2}F_{4}(2)^{{}^{\prime}}$;

  5. (v)

one of 26 sporadic simple groups:

    1. (a)

the five Mathieu groups $\rm{M_{11},M_{12},M_{22},M_{23},M_{24}}$;

    2. (b)

the seven Leech Lattice groups $\rm{Co_{1},Co_{2},Co_{3},McL,HS,Suz,J_{2}}$;

    3. (c)

the three Fischer groups $\rm{Fi_{22},Fi_{23},Fi_{24}^{{}^{\prime}};}$

    4. (d)

the Monstrous groups $\mathbb{M},\mathbb{B},\rm{Th,HN,He}$;

    5. (e)

the six pariahs $\rm{J_{1},J_{2},J_{4},O^{\prime}N,Ly,Ru.}$

The definition of each of the group classes mentioned in the above theorem can
be found in the standard texts on CFSG (see e.g., [8], [29], [4]).

Since Lemma 1 is about nonabelian simple groups we need to consider cases (ii)
to (v) in Theorem 5.1. We take each subcases under these cases and show that
there are subgroups $H_{1}$ and $H_{2}$ satisfying the conditions of the
lemma.

We note that the 26 sporadic simple groups listed in the case (v) are of
constant sizes. Therefore, we can ignore these groups for the purpose of the
proof by simply taking $H_{2}$ to be the identity subgroup and $H_{1}$ to be
$H$. Of course if we do so we need to pick extremely large constant $b_{2}$ as
some the sporadic simple groups are of huge sizes. Fortunately, there are
known results on the groups listed under case (v) that helps us to keep the
constants $b_{1}$ and $b_{2}$ under $5$.

For an alternating group $A_{m}$ (case (ii)) it is easy to show that
$H_{1}=A_{i}$ and $H_{2}=A_{i-1}$ for some suitably chosen $i<m$ does the job.
The details are in the Appendix.

For the remaining groups we use the following two methods for the choices of
$H_{1}$ and $H_{2}$. The methods are as follows:

  1. 1.

Method 1: In this method, we first choose $H_{2}$ to be a certain Sylow
subgroup of the given simple group $H$. Next we pick $H_{1}$ to be the
normalizer of $H_{2}$ in $H$ or the Borel subgroup containing $H_{2}$.

_Example:_ Let us take $H$ to be a simple group $A_{m}(q)$ for some $q>2$
which appears in case (iii) of Theorem 5.1. Here $q$ is power of some prime
$p$. It is known that $A_{m}(q)$ has order
$q^{{m(m+1)}/{2}}\prod_{i=1}^{m}(q^{i+1}-1)/{(q-1,m+1)}$ where $(q-1,m+1)$
denotes the gcd of $q-1$ and $m+1$ (see [4], p. 252). Clearly, $H$ will have a
Sylow $p$-subgroup of order $q^{{m(m+1)}/{2}}$. We set $H_{2}$ to be this
subgroup. Next we pick $H_{1}$ to be the normailzer of $H_{2}$ in $H$. It is
also known that the order of $H_{1}$ is $q^{{m(m+1)}/{2}}(q-1)^{m}$ (see [29],
p. 46). One can check that with $b_{1}=2$ and $b_{2}=1$, these choices satisfy
the conditions of Lemma 1 (see Appendix for the details).

  2. 2.

Method 2: In this method, we choose $H_{1}$ to be a maximal subgroup of the
simple group $H$ and $H_{2}$ to certain Sylow subgroup of $H_{1}$.

_Example:_ In the example under Method 1 we consider the case for $A_{m}(q)$
when $q>2$. In this example we take the case when $q=2$. Here $H=A_{m}(q)$
will have order $2^{m(m+1)/2}\prod_{i=1}^{m}(2^{i+1}-1)$ (see [4], p. 252). It
is known that the maximal subgroup of $H$ is of order $|H|/(2^{m}-1)$ (see
[18], p. 175). We take this subgroup as $H_{1}$. Next we take $H_{2}$ as a
Sylow $2$-subgroup of $H_{1}$ which has order $2^{m(m+1)/2}$. It is easy to
verify that these choices of $H_{1}$ and $H_{2}$ along with $b_{1}=b_{2}=1$
satisfy the conditions of Lemma 1 (see Appendix for the details).

Table 1 lists the methods that we have used for choosing the suitable
subgroups in the corresponding nonabelian simple group. The last two columns
represent the constant factors $b_{1}$ and $b_{2}$ for the corresponding
simple group (see Table 1).

For case (v), we use Method 2 to get the suitable subgroups.

Case | $H$ | Condition on $q$ | Method | $b_{1}$ | $b_{2}$
---|---|---|---|---|---
(iii) | $A_{m}(q)$ | $q>2$ | Method 1 | $2$ | $1$
$q=2$ | Method 2 | $1$ | $1$
${}^{2}A_{m}(q^{2});m>1$ | $q>2$ | Method 1 | $2$ | $1$
$q=2;6\nmid(m-1)$ | Method 2 | $1$ | $1$
$q=2;6\mid(m-1)$ | Method 2 | $1$ | $1$
$C_{m}(q);m>2$ | $q>2$ | Method 1 | $2$ | $1$
$q=2$ | Method 2 | $1$ | $1$
$B_{m}(q);m>1$ |  $q$ odd | Method 1 | $2$ | $1$
$D_{m}(q);m>3$ | $q>2$ | Method 1 | $2$ | $1$
$q=2$ | Method 2 | $1$ | $1$
${}^{2}D_{m}(q^{2});m>3$ | $q>2$ | Method 1 | $3$ | $1$
$q=2$ | Method 2 | $1$ | $1$
(iv) | $G_{2}(q)$ | $q\geq 3$ | Method 1 | $1$ | $1$
$F_{4}(q)$ | All $q$ | Method 2 | $1$ | $1$
$E_{6}(q)$ | $q>2$ | Method 1 | $1$ | $1$
$q=2$ | Method 2 | $1$ | $1$
${}^{2}E_{6}(q)$ | All $q$ | Method 1 | $1$ | $1$
${}^{3}D_{4}(q)$ | All $q$ | Method 1 | $1$ | $1$
$E_{7}(q)$ | $q>2$ | Method 1 | $1$ | $1$
$q=2$ | Method 2 | $1$ | $1$
$E_{8}(q)$ | $q>2$ | Method 1 | $1$ | $1$
$q=2$ | Method 2 | $1$ | $1$
${}^{2}B_{2}(q)$ | $q=2^{2t+1},t\geq 1$ | Method 1 | $1$ | $1$
${}^{2}G_{2}(q)$ | $q=3^{2t+1},t\geq 1$ | Method 1 | $1$ | $1$
${}^{2}F_{4}(q)$ | $q=2^{2t+1},t\geq 1$ | Method 1 | $1$ | $1$
${}^{2}F_{4}(2)^{\prime}$ | $q=2$ | Method 2 | $1$ | $1$
Table 1: Table representing the constant factor and method used for choosing
suitable subgroups

In Appendix, Section 6.4 contains two comprehensive tables listing the orders
of subgroups used in the proof of Lemma 1 for different cases of CFSG.

###### Remark 3

Now we discuss how to construct the data structure given in Theorem 4.2 in
polynomial time. Apart from some simple polynomial time computations, one can
check that to construct the data structure in polynomial time it is enough to
perform the following four tasks in polynomial time.

  1. 1.

Computing a composition series,

  2. 2.

Computing a Sylow $p$-subgroup,

  3. 3.

Computing the normalizer of a subgroup, and

  4. 4.

Computing maximal subgroups of simple groups.

It is well known that the tasks (1), (2) and (3) can be performed in
polynomial time even for permutation groups (See e.g., [24]). For (4), we note
that any maximal subgroup of a simple group is generated by at most 4 elements
[7]. Therefore, we can in fact enumerate all the maximal subgroups of a simple
group given by its Cayley table in polynomial time.

There is one more subtlety: How do we determine which method (Method 1 or
Method 2) to apply to get the correct subgroups as required by Lemma 11 and
Theorem 12? There are two ways to address this issue. a) We just apply both
the methods. One of them is bound to produce the subgroups of required sizes
by Lemma 11. b) We can identify the type of the simple group by doing
isomorphism tests. Note that the isomorphism of simple groups can be tested in
polynomial time as any simple group is generated by just two elements. We also
need the well-known fact that there are at most 2 simple groups of any given
order.

## References

  * [1] N. Ahanjideh and A. Iranmanesh.  On the Sylow normalizers of some simple classical groups.  Bull. Malays. Math. Sci. Soc. (2), 35(2):459–467, 2012.
  * [2] Vikraman Arvind and Jacobo Torán.  The complexity of quasigroup isomorphism and the minimum generating set problem.  In International Symposium on Algorithms and Computation, pages 233–242. Springer, 2006.
  * [3] Vikraman Arvind and Jacobo Torán.  Solvable group isomorphism is (almost) in NP $\cap$ conp.  ACM Trans. Comput. Theory, 2(2):4:1–4:22, 2011.
  * [4] M. Aschbacher.  Finite Group Theory.  Cambridge Studies in Advanced Mathematics. Cambridge University Press, 2 edition, 2000.
  * [5] László Babai, Paolo Codenotti, and Youming Qiao.  Polynomial-time isomorphism test for groups with no abelian normal subgroups.  In International Colloquium on Automata, Languages, and Programming, pages 51–62. Springer, 2012.
  * [6] László Babai and Youming Qiao.  Polynomial-time isomorphism test for groups with abelian sylow towers.  In STACS’12 (29th Symposium on Theoretical Aspects of Computer Science), volume 14, pages 453–464. LIPIcs, 2012.
  * [7] Timothy C Burness, Martin W Liebeck, and Aner Shalev.  Generation and random generation: from simple groups to maximal subgroups.  Advances in Mathematics, 248:59–95, 2013.
  * [8] Roger W. Carter.  Finite groups of Lie type.  Wiley Classics Library. John Wiley & Sons, Ltd., Chichester, 1993.  Conjugacy classes and complex characters, Reprint of the 1985 original, A Wiley-Interscience Publication.
  * [9] J. H. Conway, R. T. Curtis, S. P. Norton, R. A. Parker, and R. A. Wilson.  ATLAS of Finite Groups.  Oxford University Press, Eynsham, 1985.  Maximal subgroups and ordinary characters for simple groups, With computational assistance from J. G. Thackray.
  * [10] Bireswar Das and Shivdutt Sharma.  Compact data structures for dedekind groups and finite rings.  In WALCOM, pages 90–102, 2021.
  * [11] Bireswar Das, Shivdutt Sharma, and P. R. Vaidyanathan.  Space efficient representations of finite groups.  J. Comput. Syst. Sci., 114:137–146, 2020.
  * [12] David S. Dummit and Richard M. Foote.  Abstract algebra.  John Wiley & Sons, Inc., Hoboken, NJ, third edition, 2004.
  * [13] Arash Farzan and J. Ian Munro.  Succinct representation of finite abelian groups.  In ISSAC 2006, pages 87–92. ACM, New York, 2006.
  * [14] Merrick Furst, John Hopcroft, and Eugene Luks.  Polynomial-time algorithms for permutation groups.  In 21st Annual Symposium on Foundations of Computer Science (sfcs 1980), pages 36–41. IEEE, 1980.
  * [15] Francois Le Gall.  Efficient isomorphism testing for a class of group extensions.  arXiv preprint arXiv:0812.2298, 2008.
  * [16] T. Kavitha.  Linear time algorithms for abelian group isomorphism and related problems.  J. Comput. System Sci., 73(6):986–996, 2007.
  * [17] Neeraj Kayal and Timur Nezhmetdinov.  Factoring groups efficiently.  In International colloquium on automata, languages, and programming, pages 585–596. Springer, 2009.
  * [18] Peter B. Kleidman and Martin W. Liebeck.  The Subgroup Structure of the Finite Classical Groups.  London Mathematical Society Lecture Note Series. Cambridge University Press, 1990.
  * [19] Daniel J. Kleitman, Bruce R. Rothschild, and Joel H. Spencer.  The number of semigroups of order $n$.  Proc. Amer. Math. Soc., 55(1):227–232, 1976.
  * [20] S Ravi Kumar and Ronitt Rubinfeld.  Property testing of abelian group operations, 1998.
  * [21] Gary L. Miller.  On the $n^{\log n}$ isomorphism technique: A preliminary report.  In Richard J. Lipton, Walter A. Burkhard, Walter J. Savitch, Emily P. Friedman, and Alfred V. Aho, editors, Proceedings of the 10th Annual ACM Symposium on Theory of Computing, May 1-3, 1978, San Diego, California, USA, pages 51–58. ACM, 1978.
  * [22] Youming Qiao, Jayalal Sarma, and Bangsheng Tang.  On isomorphism testing of groups with normal hall subgroups.  J. Comput. Sci. Technol., 27(4):687–701, 2012.
  * [23] Joseph J. Rotman.  An introduction to the theory of groups, volume 148 of Graduate Texts in Mathematics.  Springer-Verlag, New York, fourth edition, 1995.
  * [24] Ákos Seress.  Permutation group algorithms, volume 152 of Cambridge Tracts in Mathematics.  Cambridge University Press, Cambridge, 2003.
  * [25] Charles C. Sims.  Computational methods in the study of permutation groups.  In John Leech, editor, Computational Problems in Abstract Algebra, pages 169–183. Pergamon, 1970.
  * [26] Charles C Sims.  Computation with permutation groups.  In Proceedings of the second ACM symposium on Symbolic and algebraic manipulation, pages 23–28, 1971.
  * [27] Charles C. Sims.  Computation with finitely presented groups, volume 48 of Encyclopedia of Mathematics and its Applications.  Cambridge University Press, Cambridge, 1994.
  * [28] J. H. van Lint and R. M. Wilson.  A course in combinatorics.  Cambridge University Press, Cambridge, 1992.
  * [29] Robert A. Wilson.  The finite simple groups, volume 251 of Graduate Texts in Mathematics.  Springer-Verlag London, Ltd., London, 2009.
  * [30] Robert A. Wilson.  Maximal subgroups of sporadic groups.  In Finite simple groups: thirty years of the atlas and beyond, volume 694 of Contemp. Math., pages 57–72. Amer. Math. Soc., Providence, RI, 2017.

Appendix

##  6 Proof of Lemma 1

In this section we prove Lemma 1 in detail. We present the detailed
calculations in the ordering mentioned in the Classification Theorem of Finite
Simple Group, i.e., Theorem 5.1. As we mentioned in Section 2, we just need to
use some known results on the _order_ of certain subgroups of simple groups.
The detailed description of these groups may be skipped for the purpose of the
proof. The results that are used in the proof are on the orders of the finite
simple groups, on the orders of maximal subgroups of simple groups and the
normalizers of certain types of Sylow subgroups of simple groups. The
information about the order of these simple groups can be obtained from [4]
(see p. 252).

In case (ii) of Theorem 5.1, $H$ is an alternating group. The stabilizer of
any set is a subgroup of an alternating group under natural action. The
subgroups $H_{1}$ and $H_{2}$ are suitably picked stabilizer subgroups of the
given alternating group $H$.

For the cases (iii) and (iv) of Theorem 5.1, we use Method 1 and Method 2 to
get the desired subgroups as required in Lemma 1. In this cases the finite
simple group $H$ is of Lie-type and is defined over a finite field
$\mathbb{F}_{q}$ where $q$ is a power of some prime $p$. In Method 1, we take
$H_{2}$ to be certain Sylow $p$-subgroup of $H$. The existence of such $H_{2}$
follows from the well-known Sylow theorem. For the existence of $H_{1}$, we
take the normalizer of $H_{2}$ or the Borel subgroup. The information about
the order of normalizer has been obtained from (see [8], p. 76, [29], p. 46).

For the groups in which we use Method 2, we consider a maximal subgroup of $H$
as $H_{1}$ and $H_{2}$ to be some Sylow $p$-subgroup of $H_{1}$. The index of
a maximal subgroup (and hence its order) can be obtained from [18], p. 175 and
[29], p. 156.

For the simple groups in case (v), we use Method 2 and the information about
order of maximal subgroup ($H_{1}$) can be obtained from [30]. Also, for the
choice of $H_{2}$, we choose certain Sylow subgroup of $H_{1}$.

Remarks

The inequalities in the following two remarks are used in the calculation
multiple times. For the sake of completeness we provide proofs of the
inequalities.

###### Remark 4

For all integer $q>2,$ we have $\frac{q}{(q-1)^{2}}<1.$

###### Proof

$\displaystyle 1-\frac{q}{(q-1)^{2}}=$
$\displaystyle\frac{(q-1)^{2}-q}{(q-1)^{2}}$ $\displaystyle=$
$\displaystyle\frac{q^{2}-3q+1}{(q-1)^{2}}$ $\displaystyle=$
$\displaystyle\frac{(q-\frac{3+\sqrt{5}}{2})(q-\frac{3-\sqrt{5}}{2})}{(q-1)^{2}}$
$\displaystyle>$ $\displaystyle 0.$

Hence, $\frac{q}{(q-1)^{2}}<1$, for $q>2$

###### Remark 5

$\prod_{i=1}^{i=m}(q^{i+1}-(-1)^{i+1})<q^{\sum_{i=1}^{i=m}(i+1)}$

.

###### Proof

We can observe that the sign of 1 changes alternatively. When $i$ is even then
sign of 1 is negative and when $i$ is odd then sign of 1 is positive.

Now,

$(q^{2j-1}-(-1)^{2j-1})(q^{2j}-(-1)^{2j})=(q^{4j-1}-1-q^{2j}+q^{2j-1})<q^{4j-1}\,(j\geq
1).$

If $m$ is even, then it is easy to see that we can pair two consecutive odd
and even term, the product of these terms is less than the sum of powers of
$q$. If $m$ is odd, then the term which is not paired is $q^{m}-1$. Notice
that, $(q^{m}-1)<q^{m}$. Thus, in this case also the product of all the terms
is less than the sum of powers of $q$.

###### Remark 6

The greatest common divisor (gcd) of two natural numbers $m$ and $n$, both not
zero, is denoted by $(m,n)$.

###  6.1 Alternating group

The _Alternating group_ $A_{m}$ is a group of all even permutations of a
finite set. It is well known that $A_{m}$ is simple group, when $m\geq 5.$
Notice that, with respect to the natural action, the _stabilizer_ of a point
$\alpha$ or a set $S\subset[m]$ is a subgroup of $A_{m}.$ In particular, the
stabilizer of the set $\\{i+1,...,m\\}$ is a subgroup of $A_{m}$ and is
isomorphic to $A_{i}.$

Thus, there exists a subgroup $K_{j}$ of $A_{m}$ such that $K_{j}\cong A_{j},$
$\forall$ j and $\lvert K_{j}\rvert=\frac{j!}{2}.$ Let $k\in\mathbb{Z}$ such
that $\frac{k!}{2}\leq\sqrt{\frac{m!}{2}}<\frac{(k+1)!}{2},$ and

$H_{2}\cong A_{k}\text{ amd }H_{1}\cong A_{k+1}.$

Thus, $A_{k}$ is subgroup of $A_{k+1}$ as $A_{k}$ is stabilizer which fixes
the point $k+1$ and $H_{2}\leq H_{1}.$ Notice that,

$\lvert H_{2}\rvert^{2}=\Big{(}\frac{k!}{2}\Big{)}^{2}\leq\frac{m!}{2}.$

Now, consider

$\displaystyle{\frac{m!}{2}}$
$\displaystyle<\Big{(}\frac{(k+1)!}{2}\Big{)}^{2}$
$\displaystyle\frac{(k+2)(k+3)\cdots m}{2}$ $\displaystyle<\frac{1\cdot
2\cdots k+1}{4}$ $\displaystyle(k+2)(k+3)\cdots m$ $\displaystyle<3\cdot
4\cdots k+1.$

Notice that, each term in right hand side is less than that of each term in
left hand side. Thus, the number of terms in left hand side must be strictly
less than the number of terms in the right hand side which implies that

$\displaystyle m-(k+1)$ $\displaystyle<(k+1)-2$ $\displaystyle m-2k$
$\displaystyle<0$ $\displaystyle\frac{m}{2}$ $\displaystyle<k.$

Thus, $k>\frac{m}{2}$ and it is easy to find such $k.$
Consider,

$\Big{(}\frac{\lvert H_{1}\rvert}{\lvert
H_{2}\rvert}\Big{)}^{2}=\Big{(}\frac{\frac{(k+1)!}{2}}{\frac{k!}{2}}\Big{)}^{2}=(k+1)^{2}.$

Now, when $m=5,k=3$ and $m=6,k=4$ , we can see that the following inequality
holds:

$(k+1)^{2}<\frac{m!}{2}.$

Consider, $m\geq 7$ and $k\geq 4,$ then,

$\displaystyle\frac{k!}{2}$ $\displaystyle\leq\sqrt{\frac{m!}{2}}$
$\displaystyle\Big{(}\frac{k!}{2}\Big{)}^{2}$ $\displaystyle\leq\frac{m!}{2}$
$\displaystyle\frac{k^{2}(k-1)^{2}(k-2)^{2}}{4}$
$\displaystyle\leq\Big{(}\frac{k!}{2}\Big{)}^{2}\leq\frac{m!}{2}.$

Let,

$\displaystyle\frac{4(k+1)^{2}}{k^{2}(k-1)^{2}(k-2)^{2}}$
$\displaystyle=\frac{4(1+\frac{1}{k})^{2}}{(k-1)^{2}(k-2)^{2}}$
$\displaystyle<\frac{4}{4\cdot 9}\frac{25}{16}$ $\displaystyle<1$
$\displaystyle(k+1)^{2}<\frac{k^{2}(k-1)^{2}(k-2)^{2}}{4}$
$\displaystyle\leq\Big{(}\frac{k!}{2}\Big{)}^{2}\leq\frac{m!}{2}.$

Thus, it implies that,

$\Big{(}\frac{\lvert H_{1}\rvert}{\lvert
H_{2}\rvert}\Big{)}^{2}=(k+1)^{2}\leq\frac{m!}{2}.$

Clearly,

$\Big{(}\frac{\lvert H\rvert}{\lvert
H_{1}\rvert}\Big{)}^{2}=\Big{(}\frac{\frac{(m)!}{2}}{\frac{(k+1)!}{2}}\Big{)}^{2}<\Big{(}\frac{\frac{m!}{2}}{\sqrt{\frac{m!}{2}}}\Big{)}^{2}=\frac{m!}{2}.$

###  6.2 The Classical Groups

In this section, we consider $H$ to be a classical simple group described in
case (iii) of Theorem 5.1. Let $q$ be a power of some prime $p$. As described
earlier, we use Method 1 and Method 2 to show the existence of subgroups
$H_{2}$ and $H_{1}$ of the simple group $H$.

####  6.2.1 A Classical Groups of Linear Type:

  1. 1.1

$H=A_{m}(q)$; $m\geq 1$, $q>2$ (Method 1)

The finite simple group $A_{m}(q)$ is isomorphic to the _projective special
linear group_ $\rm{PSL}_{{\rm m}+1}(q)$, where ${\rm PSL}_{m+1}(q)$ is the
group obtained by taking special linear group ${\rm SL}_{m+1}(q)$ and
quotienting out by its center, i.e. $A_{m}(q)\cong\frac{{\rm
SL}_{m+1}(q)}{Z({\rm SL}_{m+1}(q))}$ (see [29], p. 44). It is known that (see
[4], p. 252) its order is,

$\lvert
H\rvert=\frac{q^{\frac{m(m+1)}{2}}\prod_{i=1}^{m}(q^{i+1}-1)}{(q-1,m+1)}.$

Let $H_{2}$ be the Sylow $p$-subgroup of $A_{m}(q)$, then $\lvert
H_{2}\rvert=q^{\frac{m(m+1)}{2}}.$ Notice that $\lvert
H_{2}\rvert^{2}\leq\lvert H\rvert.$ Consider the Borel subgroup $H_{1}$ of
$H$, its order is (see [29], p. 46),

$|H_{1}|=\frac{q^{\frac{m(m+1)}{2}}}{(q-1,m+1)}(q-1)^{m}.$

Consider,

$\displaystyle\frac{\lvert H_{1}\rvert}{\lvert H_{2}\rvert^{2}}$
$\displaystyle=\frac{\frac{q^{\frac{m(m+1)}{2}}}{(q-1,m+1)}(q-1)^{m}}{q^{m(m+1)}}$
$\displaystyle=\frac{1}{(q-1,m+1)}\frac{(q-1)^{m}}{q^{\frac{m(m+1)}{2}}}$
$\displaystyle<\frac{1}{(q-1,m+1)}\frac{q^{m}}{q^{\frac{m(m+1)}{2}}}$
$\displaystyle<\frac{q^{m}}{q^{1+2+3+\ldots+m}}$ $\displaystyle<1.$

Thus,

$\Big{(}\frac{|H_{1}|}{\lvert H_{2}\rvert}\Big{)}^{2}<|H_{1}|<|H|.$

Also,

$\displaystyle\frac{\lvert H\rvert}{|H_{1}|^{2}}$
$\displaystyle=\frac{\frac{q^{\frac{m(m+1)}{2}}\prod_{i=1}^{m}(q^{i+1}-1)}{(q-1,m+1)}}{(\frac{q^{\frac{m(m+1)}{2}}}{(q-1,m+1)}(q-1)^{m})^{2}}$
$\displaystyle=\frac{(q-1,m+1)\prod_{i=1}^{m}(q^{i+1}-1)}{q^{\frac{m(m+1)}{2}}(q-1)^{2m}}$
$\displaystyle<\frac{q^{1+2+\ldots+m}q^{m+1}}{q^{\frac{m(m+1)}{2}}(q-1)^{2m}}$
$\displaystyle=\frac{q^{m+1}}{(q-1)^{m+1}(q-1)^{m-1}}$
$\displaystyle=\frac{1}{(1-\frac{1}{q})^{m+1}(q-1)^{m-1}}$
$\displaystyle=\frac{1}{(1-\frac{1}{q})^{2}(1-\frac{1}{q})^{m-1}(q-1)^{m-1}}$
$\displaystyle=\frac{1}{(1-\frac{1}{q})^{2}(q-2+\frac{1}{q})^{m-1}}$
$\displaystyle<3.$

Therefore,

$\Big{(}\frac{\lvert H\rvert}{\lvert H_{1}\rvert}\Big{)}^{2}<3\,\lvert
H\rvert\implies\frac{\lvert H\rvert}{\lvert H_{1}\rvert}<2\,\sqrt{\lvert
H\rvert}.$

  2. 1.2

$A_{m}(q)$; $m\geq 1$, $q=2$ (Method 2)

The finite simple group $A_{m}(2)$ is of order
$2^{\frac{m(m+1)}{2}}\prod_{i=1}^{m}(2^{i+1}-1)/(q-1,m+1)$ and is isomorphic
to _projective special linear group_ ${\rm PSL}_{m+1}(2)$ or ${\rm
L}_{m+1}(2).$ It has a maximal subgroup of index $(2^{m+1}-1)$ (see [18], p.
175). Let $H_{1}$ be one such maximal subgroup of $A_{m}(2)$. Then,

$\displaystyle\lvert H_{1}\rvert$
$\displaystyle=\frac{|A_{m}(2)|}{(2^{m+1}-1)}$
$\displaystyle=\frac{2^{\frac{m(m+1)}{2}}\prod_{i=1}^{m}(2^{i+1}-1)}{(2^{m+1}-1)}.$

Let $H_{2}$ be the Sylow $2$-subgroup of $H_{1}.$ Then, $H_{2}$ has order
$2^{\frac{m(m+1)}{2}}$ and $|H_{2}|^{2}<|A_{m}(2)|.$ This implies that

$\frac{\lvert H_{1}\rvert}{\lvert H_{2}\rvert}=\prod_{i=1}^{m-1}(2^{i+1}-1).$

Consider,

$\displaystyle\frac{\Big{(}\frac{\lvert H_{1}\rvert}{\lvert
H_{2}\rvert}\Big{)}^{2}}{|A_{m}(2)|}$
$\displaystyle=\frac{\big{(}\prod_{i=1}^{m-1}(2^{i+1}-1)\big{)}^{2}}{2^{\frac{m(m+1)}{2}}\prod_{i=1}^{m}(2^{i+1}-1)}$
$\displaystyle=\frac{\prod_{i=1}^{m-1}(2^{i+1}-1)}{2^{\frac{m(m+1)}{2}(2^{m+1}-1)}}$
$\displaystyle<\frac{2^{\frac{m(m+1)}{2}-1}}{2^{\frac{m(m+1)}{2}(2^{m+1}-1)}}$
$\displaystyle<1.$

Thus, we get

$\Big{(}\frac{\lvert H_{1}\rvert}{\lvert H_{2}\rvert}\Big{)}^{2}<\lvert
A_{m}(2)\rvert.$

Now,

$\displaystyle\Big{(}\frac{|A_{m}(2)|}{\lvert H_{1}\rvert}\Big{)}^{2}$
$\displaystyle=(2^{m+1}-1)^{2}$
$\displaystyle<2^{\frac{m(m+1)}{2}}\prod_{i=1}^{m}(2^{i+1}-1)$
$\displaystyle=\lvert A_{m}(q)\rvert.$

####  6.2.2 A Classical Groups of Unitary Type:

  1. 1.1

$H=~{}^{2}A_{m}(q^{2})$; $m\geq 2$, $q>2$ (Method 1)

The finite simple group ${}^{2}A_{m}(q^{2})$ is isomorphic to the _projective
special unitary group_ ${\rm PSU}_{m+1}(q)$. The group ${\rm PSU}_{m+1}(q)$ is
the group obtain by taking special unitary group ${\rm SU}_{m+1}(q)$ and
quotienting it by its center, i.e. ${}^{2}A_{m}(q^{2})\cong\frac{{\rm
SU}_{m+1}(q)}{Z(\rm{SU}_{m+1}(q))}$ (see [29], p. 66). It is known that (see
[4], p. 252) the order of ${}^{2}A_{m}(q^{2})$ is,

$\lvert
H\rvert=\frac{q^{\frac{m(m+1)}{2}}}{(q+1,m+1)}\prod_{i=1}^{m}(q^{i+1}-(-1)^{i+1}).$

Let $H_{2}$ be the Sylow $p$-subgroup of ${}^{2}A_{m}(q^{2})$, then $\lvert
H_{2}\rvert=q^{\frac{m(m+1)}{2}}$ and $\lvert H_{2}\rvert^{2}\leq\lvert
H\rvert.$ Let $H_{1}$ be the Borel subgroup of $H$ of order (see [29], [8]),

$|H_{1}|=\frac{q^{\frac{m(m+1)}{2}}}{(q+1,m+1)}(q-1)^{\lfloor
m/2\rfloor}(q+1)^{\lceil\frac{m-1}{2}\rceil}$.

Consider,

$\displaystyle\Big{(}\frac{\lvert H_{1}\rvert}{\lvert H_{2}\rvert}\Big{)}^{2}$
$\displaystyle=\Big{(}\frac{(q-1)^{\lfloor
m/2\rfloor}(q+1)^{\lceil\frac{m-1}{2}\rceil}}{(q+1,m+1)}\Big{)}^{2}$
$\displaystyle\leq\frac{(q-1)^{m}(q+1)^{m}}{(q+1,m+1)^{2}}$
$\displaystyle=\frac{(q^{2}-1)^{m}}{(q+1,m+1)^{2}}$ $\displaystyle\leq\lvert
H_{1}\rvert.$

Thus,

$\Big{(}\frac{\lvert H_{1}\rvert}{\lvert H_{2}\rvert}\Big{)}^{2}\leq\lvert
H_{1}\rvert<\lvert H\rvert.$

Also,

$\displaystyle\frac{\lvert H\rvert}{\lvert H_{1}\rvert^{2}}$
$\displaystyle=\frac{\frac{q^{\frac{m(m+1)}{2}}}{(q+1,m+1)}\prod_{i=1}^{m}(q^{i+1}-(-1)^{i+1})}{\Big{(}\frac{(q-1)^{\lfloor
m/2\rfloor}(q+1)^{\lceil\frac{m-1}{2}\rceil}q^{\frac{m(m+1)}{2}}}{(q+1,m+1)}\Big{)}^{2}}$
$\displaystyle=\frac{(q+1,m+1)\prod_{i=1}^{m}(q^{i+1}-(-1)^{i+1})}{(q-1)^{m}(q+1)^{m-1}q^{\frac{m(m+1)}{2}}}$
$\displaystyle<\frac{(q+1,m+1)q^{\frac{(m+1)(m+2)}{2}-1}}{(q-1)^{m}(q+1)^{m-1}q^{{\frac{m^{2}+m}{2}}}}\quad\quad\quad(\text{by
Remark}\,\ref{Remark-2})$
$\displaystyle=\frac{(q+1,m+1)q^{\frac{(m+1)(m+2)}{2}-1}}{(q-1)(q^{2}-1)^{m-1}q^{\frac{m^{2}+m}{2}}}$
$\displaystyle=\frac{(q+1,m+1)q^{m}}{(q-1)(q^{2}-1)^{m-1}}$
$\displaystyle<2\,\frac{q}{\big{(}q-\frac{1}{q}\big{)}^{m-1}}$
$\displaystyle<4.$

Thus,

$\Big{(}\frac{\lvert H\rvert}{\lvert H_{1}\rvert}\Big{)}^{2}\leq 4\lvert
H\rvert\implies\frac{\lvert H\rvert}{\lvert H_{1}\rvert}\leq 2\sqrt{\lvert
H\rvert}$

  2. 1.2

$H=~{}^{2}A_{m}(q^{2})$; $m\geq 2$, $q=2$ (Method 2)

The finite simple group ${}^{2}A_{m}(2^{2})$ is of order
$2^{\frac{m(m+1)}{2}}\prod_{i=1}^{m}(2^{i+1}-(-1)^{i+1})/{(3,m+1)}$ and is
isomorphic to _projective special unitary group_ ${\rm PSU}_{m+1}(2)$ or ${\rm
U}_{m+1}(q)$. The group ${\rm U}_{m+1}(q)$ has a maximal subgroup of index
${\frac{(2^{m+1}-(-1)^{m+1})(2^{m}-(-1)^{m})}{3}}$ when $6\nmid(m-1)$ and of
index $\frac{2^{m}(2^{m+1}-1)}{3},$ when $6\mid(m-1)$ (see [18], p. 175) .

    1. (Case 1)

$6\nmid(m-1)$

Let $H_{1}$ be corresponding maximal subgroup of ${}^{2}A_{m}(2^{2})$ whose
index is

${\frac{(2^{m+1}-(-1)^{m+1})(2^{m}-(-1)^{m})}{3}}$

in ${}^{2}A_{m}(2^{2}).$ Then, the order of $H_{1}$ is,

$\displaystyle\lvert H_{1}\rvert$
$\displaystyle=\frac{|~{}^{2}A_{m}(2^{2})|}{{\frac{(2^{m+1}-(-1)^{m+1})(2^{m}-(-1)^{m})}{3}}}$
$\displaystyle=\frac{3}{(3,m+1)}\frac{{2^{\frac{m(m+1)}{2}}}\prod_{i=1}^{m}(2^{i+1}-(-1)^{i+1})}{(2^{m+1}-(-1)^{m+1})(2^{m}-(-1)^{m})}.$

Let $H_{2}$ be the Sylow 2-subgroup of $H_{1}.$ Then, $\lvert
H_{2}\rvert=2^{\frac{m(m+1)}{2}}$ and $\lvert
H_{2}\rvert^{2}<\lvert~{}^{2}A_{m}(2^{2})\rvert.$ Also,

$\frac{\lvert H_{1}\rvert}{\lvert
H_{2}\rvert}=\frac{3}{(3,m+1)}\frac{\prod_{i=1}^{m}(2^{i+1}-(-1)^{i+1})}{(2^{m+1}-(-1)^{m+1})(2^{m}-(-1)^{m})}.$

Consider,

$\displaystyle\frac{\Big{(}\frac{\lvert H_{1}\rvert}{\lvert
H_{2}\rvert}\Big{)}^{2}}{|~{}^{2}A_{m}(2^{2})|}$
$\displaystyle=\frac{\Big{(}\frac{3}{(3,m+1)}\frac{\prod_{i=1}^{m}(2^{i+1}-(-1)^{i+1})}{(2^{m+1}-(-1)^{m+1})(2^{m}-(-1)^{m})}\Big{)}^{2}}{\frac{2^{\frac{m(m+1)}{2}}}{(3,m+1)}\prod_{i=1}^{m}(2^{i+1}-(-1)^{i+1})}$
$\displaystyle=\frac{9}{(3,m+1)}\frac{\prod_{i=1}^{m}(2^{i+1}-(-1)^{i+1})}{2^{\frac{m(m+1)}{2}}((2^{m+1}-(-1)^{m+1})(2^{m}-(-1)^{m}))^{2}}$
$\displaystyle<\frac{9}{(3,m+1)}\frac{2^{\frac{(m+1)(m+2)}{2}-1}}{2^{\frac{m(m+1)}{2}}((2^{m+1}-(-1)^{m+1})(2^{m}-(-1)^{m}))^{2}}\quad\quad\quad(\text{by
Remark}\,\ref{Remark-2})$
$\displaystyle=\frac{9}{(3,m+1)}\frac{2^{m}}{((2^{m+1}-(-1)^{m+1})(2^{m}-(-1)^{m}))^{2}}$
$\displaystyle<\frac{9}{(3,m+1)}\frac{1}{\Big{(}\big{(}2^{\lfloor\frac{m+1}{2}\rfloor}-\frac{(-1)^{m+1}}{2^{\lfloor\frac{m}{2}+1\rfloor}}\big{)}(2^{m}-(-1)^{m})\Big{)}^{2}}$
$\displaystyle<1.$

Therefore,

$\Big{(}\frac{\lvert H_{1}\rvert}{\lvert
H_{2}\rvert}\Big{)}^{2}<\rvert~{}^{2}A_{m}(2^{2})\lvert$

Now,

$\displaystyle\Big{(}\frac{|~{}^{2}A_{m}(2^{2})|}{\lvert
H_{1}\rvert}\Big{)}^{2}$
$\displaystyle=\Big{(}{\frac{(2^{m+1}-(-1)^{m+1})(2^{m}-(-1)^{m})}{3}}\Big{)}^{2}$
$\displaystyle<\frac{2^{\frac{m(m+1)}{2}}}{(3,m+1)}\prod_{i=1}^{m}(2^{i+1}-(-1)^{i+1})$
$\displaystyle=\lvert~{}^{2}A_{m}(2^{2})\rvert.$

    2. (Case 2)

$6|(m-1)$ (i.e. $m\geq 7$)

In this case, as we know that the group ${}^{2}A_{m}(q^{2})$ has a maximal
subgroup of index $\frac{2^{m}(2^{m+1}-1)}{3}.$ Let $H_{1}$ be one such
maximal subgroup. Then,

$\displaystyle\lvert H_{1}\rvert$
$\displaystyle=\frac{|~{}^{2}A_{m}(2^{2})|}{\frac{2^{m}(2^{m+1}-1)}{3}}$
$\displaystyle=\frac{\frac{2^{\frac{m(m+1)}{2}}}{(3,m+1)}\prod_{i=1}^{m}(2^{i+1}-(-1)^{i+1})}{\frac{2^{m}(2^{m+1}-1)}{3}}$
$\displaystyle=\frac{3}{(3,m+1)}{2^{\frac{m(m-1)}{2}}}\prod_{i=1}^{m-1}(2^{i+1}-(-1)^{i+1}).$

Let $H_{2}$ be the Sylow $2$-subgroup of $H_{1},$ then $H_{2}$ has order
$2^{\frac{m(m-1)}{2}}$ and $\lvert
H_{2}\rvert^{2}<\lvert~{}^{2}A_{m}(2^{2})\rvert.$ Also,

$\frac{\lvert H_{1}\rvert}{\lvert
H_{2}\rvert}=\frac{3}{(3,m+1)}\prod_{i=1}^{m-1}(2^{i+1}-(-1)^{i+1}).$

Consider,

$\displaystyle\frac{\Big{(}\frac{\lvert H_{1}\rvert}{\lvert
H_{2}\rvert}\Big{)}^{2}}{|~{}^{2}A_{m}(2^{2})|}$
$\displaystyle=\frac{\Big{(}\frac{3}{(3,m+1)}\prod_{i=1}^{m-1}(2^{i+1}-(-1)^{i+1})\Big{)}^{2}}{\frac{2^{\frac{m(m+1)}{2}}}{(3,m+1)}\prod_{i=1}^{m}(2^{i+1}-(-1)^{i+1})}$
$\displaystyle=\frac{9}{(3,m+1)}\frac{\prod_{i=1}^{m-1}(2^{i+1}-(-1)^{i+1})}{2^{\frac{m(m+1)}{2}}(2^{m+1}-(-1)^{m+1})}$
$\displaystyle<\frac{9}{(3,m+1)}\frac{2^{\frac{m^{2}+m-2}{2}}}{2^{\frac{m^{2}+m}{2}}(2^{m+1}-(-1)^{m+1})}\quad\quad\quad(\text{by
Remark}\,\ref{Remark-2})$
$\displaystyle=\frac{9}{(3,m+1)}\frac{1}{2\,(2^{m+1}-(-1)^{m+1})}$
$\displaystyle<1.\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad(\text{since}\,{m\geq
7})$

This implies that,

$\Big{(}\frac{\lvert H_{1}\rvert}{\lvert
H_{2}\rvert}\Big{)}^{2}<\lvert~{}^{2}A_{m}(2^{2})\rvert.$

Now,

$\displaystyle\Big{(}\frac{\lvert~{}^{2}A_{m}(2^{2})\rvert}{\lvert
H_{1}\rvert}\Big{)}^{2}$
$\displaystyle=\Big{(}\frac{2^{m}(2^{m+1}-1)}{3}\Big{)}^{2}$
$\displaystyle=\frac{2^{2m}(2^{m+1}-1)^{2}}{9}$
$\displaystyle<\frac{2^{\frac{m(m+1)}{2}}}{(3,m+1)}\prod_{i=1}^{m}(2^{i+1}-(-1)^{i+1})$
$\displaystyle=\lvert~{}^{2}A_{m}(2^{2})\rvert.$

####  6.2.3 Classical Groups of Symplectic Linear Type:

  1. 1.1

$H=C_{m}(q)$; $m\geq 2$, $q>2$ (Method 1)

The order of the finite simple group $C_{m}(q)$ could be found in (see [4], p.
252) and it is,

$\lvert H\rvert=\frac{q^{m^{2}}\prod_{i=1}^{m}(q^{2i}-1)}{(2,q-1)}.$

Let $H_{2}$ be the Sylow $p$-subgroup of $H$, then $\lvert
H_{2}\rvert=q^{m^{2}}$ and $\lvert H_{2}\rvert^{2}\leq\lvert H\rvert.$ Let
$H_{1}$ be the normalizer of $H_{2}$ in $H$ then the order of $H_{1}$ (see
[1], p. 3) is,

$\lvert H_{1}\rvert=\frac{q^{m^{2}}}{(2,q-1)}(q-1)^{m}.$

Consider,

$\displaystyle\frac{\lvert H_{1}\rvert}{\lvert H_{2}\rvert^{2}}$
$\displaystyle=\frac{\frac{q^{m^{2}}}{(2,q-1)}(q-1)^{m}}{q^{2m^{2}}}$
$\displaystyle=\frac{1}{(2,q-1)}\frac{(q-1)^{m}}{q^{m^{2}}}$
$\displaystyle<\frac{1}{(2,q-1)}\frac{q^{m}}{q^{m^{2}}}$ $\displaystyle<1.$

Thus,

$\Big{(}\frac{\lvert H_{1}\rvert}{\lvert
H_{2}\rvert}\Big{)}^{2}<|H_{1}|<\lvert H\rvert.$

Also,

$\displaystyle\frac{\lvert H\rvert}{\lvert H_{1}\rvert^{2}}$
$\displaystyle=\frac{\frac{q^{m^{2}}\prod_{i=1}^{m}(q^{2i}-1)}{(2,q-1)}}{(\frac{q^{m^{2}}}{(2,q-1)}(q-1)^{m})^{2}}$
$\displaystyle=\frac{(2,q-1)\prod_{i=1}^{m}(q^{2i}-1)}{q^{m^{2}}(q-1)^{2m}}$
$\displaystyle<\frac{(2,q-1)}{q^{m^{2}}}\frac{\prod_{i=1}^{m}q^{2i}}{(q-1)^{2m}}$
$\displaystyle=(2,q-1)\frac{q^{m+m^{2}}}{q^{m^{2}}(q-1)^{2m}}$
$\displaystyle=(2,q-1)(\frac{q}{(q-1)^{2}})^{m}$ $\displaystyle\leq
2\quad\quad\quad(\text{by Remark}\,\ref{Remark-1})$

Therefore,

$\Big{(}\frac{\lvert H\rvert}{|H_{1}|}\Big{)}^{2}\leq 2\,\lvert
H\rvert\implies\frac{\lvert H\rvert}{|H_{1}|}<2\,\sqrt{\lvert H\rvert}.$

  2. 1.2

$H=C_{m}(q)$; $m\geq 2$, $q=2$ (Method 2)

The simple group $C_{m}(q)$ (or ${\rm PSp}_{2m}(q)$) has order
$2^{m^{2}}\prod_{i=1}^{m}(2^{2i}-1)$. It is known that the group ${\rm
PSp}_{2m}(q)$ has a maximal subgroup of index $2^{m-1}(2^{m}-1)$ (see [18], p.
175). Let $H_{1}$ be one such subgroup, then the order of $H_{1}$ is,

$\displaystyle\lvert H_{1}\rvert$
$\displaystyle=\frac{|C_{m}(2)|}{2^{m-1}(2^{m}-1)}$
$\displaystyle=\frac{2^{m^{2}}\prod_{i=1}^{m}(2^{2i}-1)}{2^{m-1}(2^{m}-1)}$
$\displaystyle=\frac{2^{m^{2}-m+1}(2^{2m}-1)\prod_{i=1}^{m-1}(2^{2i}-1)}{(2^{m}-1)}$
$\displaystyle=2^{m^{2}-m+1}(2^{m}+1)\prod_{i=1}^{m-1}(2^{2i}-1).$

Let $H_{2}$ be the Sylow $2$-subgroup of $H_{1}.$ Then, the order of $H_{2}$
is $2^{m^{2}-m+1}.$ Notice that $\lvert H_{2}\rvert^{2}<\lvert
C_{m}(2)\rvert.$ Thus,

$\frac{\lvert H_{1}\rvert}{\lvert
H_{2}\rvert}=(2^{m}+1)\prod_{i=1}^{m-1}(2^{2i}-1).$

Consider,

$\displaystyle\frac{\Big{(}\frac{\lvert H_{1}\rvert}{\lvert
H_{2}\rvert}\Big{)}^{2}}{\lvert C_{m}(2)\rvert}$
$\displaystyle=\frac{((2^{m}+1)\prod_{i=1}^{m-1}(2^{2i}-1))^{2}}{2^{m^{2}}\prod_{i=1}^{m}(2^{2i}-1)}$
$\displaystyle=\frac{(2^{m}+1)^{2}(\prod_{i=1}^{m-1}(2^{2i}-1))^{2}}{2^{m^{2}}(2^{2m}-1)\prod_{i=1}^{m-1}(2^{2i}-1)}$
$\displaystyle=\frac{(2^{m}+1)\prod_{i=1}^{m-1}(2^{2i}-1)}{2^{m^{2}}(2^{m}-1)}$
$\displaystyle<\frac{(2^{m}+1)\prod_{i=1}^{m-1}2^{2i}}{2^{m^{2}}(2^{m}-1)}$
$\displaystyle=\frac{(2^{m}+1)2^{m(m-1)}}{2^{m^{2}}(2^{m}-1)}$
$\displaystyle=\frac{(1+2^{-m})}{(2^{m}-1)}$ $\displaystyle<1.$

Therefore,

$\Big{(}\frac{\lvert H_{1}\rvert}{\lvert H_{2}\rvert}\Big{)}^{2}<\lvert
C_{m}(2)\rvert.$

Now,

$\displaystyle\Big{(}\frac{|C_{m}(2)|}{\lvert H_{1}\rvert}\Big{)}^{2}$
$\displaystyle=(2^{m-1}(2^{m}-1))^{2}$ $\displaystyle=2^{2m-2}(2^{m}-1)^{2}$
$\displaystyle<2^{m^{2}}(2^{m}-1)(2^{m}+1)$
$\displaystyle<2^{m^{2}}\prod_{i=1}^{m}(2^{2i}-1)$ $\displaystyle=\lvert
C_{m}(2)\rvert.$

####  6.2.4 Classical Groups of Orthogonal Type:

  1. 1.1

$H=B_{m}(q);$ $m\geq 3$ and $q$ odd (Method 1)

The finite simple group $B_{m}(q)$ has order (see [4], p. 252),

$\lvert H\rvert=\frac{q^{m^{2}}\prod_{i=1}^{m}(q^{2i}-1)}{(2,q-1)}.$

Let $H_{2}$ be the Sylow $p$-subgroup of $H$, then $\lvert
H_{2}\rvert=q^{m^{2}}$ and $\lvert H_{2}\rvert^{2}\leq\lvert H\rvert.$ Let
$H_{1}$ be the normalizer of $H_{1}$ in $H$ then its order is (see [1], p. 3),

$\lvert H_{1}\rvert=\frac{q^{m^{2}}}{(2,q-1)}(q-1)^{m}.$

Since, $\lvert B_{m}(q)\rvert=\lvert C_{m}(q)\rvert$ and the order of the
normalizer of $H_{1}$ in both the groups are also equal and thus, all the
calculations will also work for $B_{m}(q).$

  2. 2.1

$H=D_{m}(q)$; $m\geq 4$, $q>2$ (Method 1)

The order of the finite simple group $D_{m}(q)$ could be found in (see [4], p.
252) and it is,

$|H|=\frac{q^{{m(m-1)}}(q^{m}-1)\prod_{i=1}^{m-1}(q^{2i}-1)}{(4,q^{m}-1)}.$

Let $H_{2}$ be the Sylow $p$-subgroup of $D_{m}(q)$, then $\lvert
H_{2}\rvert=q^{{m(m-1)}}$ and $\lvert H_{2}\rvert^{2}\leq\lvert H\rvert.$ Let
$H_{1}$ be the Borel subgroup of $H$. It has order (see [29], [8]),

$\lvert H_{1}\rvert=\frac{q^{{m(m-1)}}}{(4,q^{m}-1)}(q-1)^{m}.$

Consider,

$\displaystyle\frac{\lvert H_{1}\rvert}{\lvert H_{2}\rvert^{2}}$
$\displaystyle=\frac{\frac{q^{{m(m-1)}}}{(4,q^{m}-1)}(q-1)^{m}}{q^{2m(m-1)}}$
$\displaystyle=\frac{1}{(4,q^{m}-1)}\frac{(q-1)^{m}}{q^{m(m-1)}}$
$\displaystyle<\frac{1}{(4,q^{m}-1)}\frac{q^{m}}{q^{m(m-1)}}$
$\displaystyle<1.$

Thus,

$\Big{(}\frac{\lvert H_{1}\rvert}{\lvert
H_{2}\rvert}\Big{)}^{2}<|H_{1}|<\lvert H\rvert$

Also,

$\displaystyle\frac{\lvert H\rvert}{\lvert H_{1}\rvert^{2}}$
$\displaystyle=\frac{\frac{q^{{m(m-1)}}(q^{m}-1)\prod_{i=1}^{m-1}(q^{2i}-1)}{(4,q^{m}-1)}}{(\frac{q^{{m(m-1)}}}{(4,q^{m}-1)}(q-1)^{m})^{2}}$
$\displaystyle=\frac{(4,q^{m}-1)(q^{m}-1)\prod_{i=1}^{m}(q^{2i}-1)}{q^{{m(m-1)}}(q-1)^{2m}}$
$\displaystyle<\frac{(4,q^{m}-1)(q^{m}-1)}{q^{{m(m-1)}}}\frac{\prod_{i=1}^{m-1}q^{2i}}{(q-1)^{2m}}$
$\displaystyle<\frac{(4,q^{m}-1)q^{m}}{q^{{m(m-1)}}}\frac{q^{{m(m-1)}}}{(q-1)^{2m}}$
$\displaystyle=(4,q^{m}-1)\Big{(}\frac{q}{(q-1)^{2}}\Big{)}^{m}$
$\displaystyle\leq 4.\quad\quad\quad(\text{by Remark}\,\ref{Remark-1})$

Thus,

$\Big{(}\frac{\lvert H\rvert}{|H_{1}|}\Big{)}^{2}\leq 4\,\lvert
H\rvert\implies\frac{\lvert H\rvert}{|H_{1}|}\leq 2\sqrt{\lvert H\rvert}.$

  3. 2.2

$H=D_{m}(q)$; $m\geq 4$, $q=2$ (Method 2)

The simple group $D_{m}(q)$ (or ${\rm P\Omega}_{2m}^{+}(q)$) is of order
$2^{{m(m-1)}}(2^{m}-1)\prod_{i=1}^{m-1}(2^{2i}-1)$. The group ${\rm
P\Omega}_{2m}^{+}(2)$ has a maximal subgroup of index $2^{m-1}(2^{m}-1)$ (see
[18], p. 175). Let $H_{1}$ be a corresponding maximal subgroup of $D_{m}(2)$
whose index is $2^{m-1}(2^{m}-1).$ Then the order of $H_{1}$ is,

$\displaystyle\lvert H_{1}\rvert$
$\displaystyle=\frac{|D_{m}(2)|}{2^{m-1}(2^{m}-1)}$
$\displaystyle=\frac{2^{{m(m-1)}}(2^{m}-1)\prod_{i=1}^{m-1}(2^{2i}-1)}{2^{m-1}(2^{m}-1)}$
$\displaystyle=2^{m^{2}-2m+1}\prod_{i=1}^{m-1}(2^{2i}-1).$

Let $H_{2}$ be the Sylow 2-subgroup of $H_{1},$ then $H_{2}$ has order
$2^{m^{2}-2m+1}$ and $\lvert H_{2}\rvert^{2}<\lvert D_{m}(2)\rvert.$ Also,

$\frac{\lvert H_{1}\rvert}{\lvert H_{2}\rvert}=\prod_{i=1}^{m-1}(2^{2i}-1).$

Consider,

$\displaystyle\frac{\Big{(}\frac{\lvert H_{1}\rvert}{\lvert
H_{2}\rvert}\Big{)}^{2}}{|D_{m}(2)|}$
$\displaystyle=\frac{(\prod_{i=1}^{m-1}(2^{2i}-1))^{2}}{2^{{m(m-1)}}(2^{m}-1)\prod_{i=1}^{m-1}(2^{2i}-1)}$
$\displaystyle=\frac{\prod_{i=1}^{m-1}(2^{2i}-1)}{2^{{m(m-1)}}(2^{m}-1)}$
$\displaystyle<\frac{\prod_{i=1}^{m-1}2^{2i}}{2^{{m(m-1)}}(2^{m}-1)}$
$\displaystyle=\frac{2^{m(m-1)}}{2^{{m(m-1)}}(2^{m}-1)}$
$\displaystyle=\frac{1}{(2^{m}-1)}$ $\displaystyle<1$

Thus,

$\Big{(}\frac{\lvert H_{1}\rvert}{\lvert H_{2}\rvert}\Big{)}^{2}<\lvert
D_{m}(2)\rvert.$

Now,

$\displaystyle\Big{(}\frac{\lvert D_{m}(2)\rvert}{\lvert
H_{1}\rvert}\Big{)}^{2}$ $\displaystyle=2^{2(m-2)}(2^{m}-1)^{2}$
$\displaystyle<2^{{m(m-1)}}(2^{m}-1)\prod_{i=1}^{m-1}(2^{2i}-1)$
$\displaystyle=\lvert D_{m}(2)\rvert.$

  4. 3.1

$H=~{}^{2}D_{m}(q^{2})$; $m\geq 4$, $q>2$ (Method 1)

The order of the finite simple group ${}^{2}D_{m}(q^{2})$ could be found in
(see [4], p. 252) and it is,

$\lvert
H\rvert=\frac{q^{m(m-1)}(q^{m}+1)}{(4,q^{m}+1)}\prod_{i=1}^{m-1}(q^{2i}-1).$

Let $H_{2}$ be the Sylow $p$-subgroup of ${}^{2}D_{m}(q^{2})$, then $\lvert
H_{2}\rvert=q^{m(m-1)}$ and $\lvert H_{2}\rvert^{2}\leq\lvert H\rvert.$ Let
$H_{1}$ to be the Borel subgroup of $H$. The order of $H_{1}$ is (see [29],
[8]). Thus,

$|B|=\frac{q^{{m(m-1)}}}{(4,q^{n}+1)}(q-1)^{m}$.

Consider,

$\displaystyle\frac{\lvert H_{1}\rvert}{\lvert H_{2}\rvert^{2}}$
$\displaystyle=\frac{\frac{q^{{m(m-1)}}}{(4,q^{n}+1)}(q-1)^{m}}{q^{2m(m-1)}}$
$\displaystyle=\frac{1}{(4,q^{n}+1)}\frac{(q-1)^{m}}{q^{m(m-1)}}$
$\displaystyle<\frac{1}{(4,q^{n}+1)}\frac{q^{m}}{q^{m(m-1)}}$
$\displaystyle\leq 1.$

Thus, we have

$\Big{(}\frac{\lvert H_{1}\rvert}{\lvert
H_{2}\rvert}\Big{)}^{2}<|H_{1}|<\lvert H\rvert.$

Also,

$\displaystyle\frac{\lvert H\rvert}{\lvert H_{1}\rvert^{2}}$
$\displaystyle=\frac{\frac{q^{m(m-1)}(q^{m}+1)}{(4,q^{m}+1)}\prod_{i=1}^{m-1}(q^{2i}-1)}{(\frac{q^{{m(m-1)}}}{(4,q^{m}+1)}(q-1)^{m})^{2}}$
$\displaystyle=\frac{(4,q^{m}+1)(q^{m}+1)\prod_{i=1}^{m-1}(q^{2i}-1)}{q^{m(m-1)}(q-1)^{2m}}$
$\displaystyle<\frac{(4,q^{m}+1)(q^{m}+1)}{q^{m(m-1)}}\frac{\prod_{i=1}^{m-1}q^{2i}}{(q-1)^{2m}}$
$\displaystyle=(4,q^{m}+1)(q^{m}+1)\frac{q^{m(m-1)}}{q^{m(m-1)}(q-1)^{2m}}$
$\displaystyle<\frac{4(2q^{m})}{(q-1)^{2m}}$
$\displaystyle<8\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad(\text{by
Remark}\,\ref{Remark-1})$

This implies that,

$\Big{(}\frac{\lvert H\rvert}{|H_{1}|}\Big{)}^{2}<8\,\lvert
H\rvert\implies\frac{\lvert H\rvert}{|H_{1}|}<3\,\sqrt{\lvert H\rvert}.$

  5. 3.2

$H=~{}^{2}D_{m}(q^{2})$; $m\geq 4$, $q=2$ (Method 2)

We know that the group ${}^{2}D_{m}(2^{2})$(or ${\rm P\Omega}_{2m}^{-}(2)$) is
of order $2^{m(m-1)}(2^{m}+1)\prod_{i=1}^{m-1}(2^{2i}-1)/(4,2^{m}+1).$ The
group ${\rm P\Omega}_{2m}^{-}(2)$ has a maximal subgroup of index
$(2^{m}+1)(2^{m-1}-1)$ (see [18], p. 175). Let $H_{1}$ be one such subgroup
then its order is,

$\displaystyle\lvert H_{1}\rvert$
$\displaystyle=\frac{|~{}^{2}D_{m}(2^{2})|}{(2^{m}+1)(2^{m-1}-1)}$
$\displaystyle=\frac{\frac{2^{m(m-1)}(2^{m}+1)}{(4,2^{m}+1)}\prod_{i=1}^{m-1}(2^{2i}-1)}{(2^{m}+1)(2^{m-1}-1)}$
$\displaystyle=2^{m(m-1)}(2^{m-1}+1)\prod_{i=1}^{m-2}(2^{2i}-1).$

Let $H_{2}$ be the Sylow $2$-subgroup of $H_{1},$ then $\lvert
H_{2}\rvert=2^{m(m-1)}$ and $|H_{2}|^{2}<|~{}^{2}D_{m}(2^{2})|.$ Thus,

$\frac{\lvert H_{1}\rvert}{\lvert
H_{2}\rvert}=(2^{m-1}+1)\prod_{i=1}^{m-2}(2^{2i}-1).$

Consider,

$\displaystyle\frac{\Big{(}\frac{\lvert H_{1}\rvert}{\lvert
H_{2}\rvert}\Big{)}^{2}}{\lvert~{}^{2}D_{m}(2^{2})\rvert}$
$\displaystyle=\frac{((2^{m-1}+1)\prod_{i=1}^{m-2}(2^{2i}-1))^{2}}{\frac{2^{m(m-1)}(2^{m}+1)}{(4,2^{m}+1)}\prod_{i=1}^{m-1}(2^{2i}-1)}$
$\displaystyle=\frac{(2^{m-1}+1)^{2}\prod_{i=1}^{m-2}(2^{2i}-1)}{2^{{m(m-1)}}(2^{2m-2}-1)(2^{m}+1)}$
$\displaystyle=\frac{(2^{m-1}+1)\prod_{i=1}^{m-2}(2^{2i}-1)}{2^{{m(m-1)}}(2^{m-1}-1)(2^{m}+1)}$
$\displaystyle<\frac{(2^{m-1}+1)\prod_{i=1}^{m-2}2^{2i}}{2^{{m(m-1)}}(2^{m-1}-1)(2^{m}+1)}$
$\displaystyle=\frac{(2^{m-1}+1)2^{(m-2)(m-1)}}{2^{{m(m-1)}}(2^{m-1}-1)(2^{m}+1)}$
$\displaystyle=\frac{(2^{m-1}+1)}{(2^{m-1}-1)(2^{m}+1)}\cdot\frac{2^{(m-2)(m-1)}}{2^{{m(m-1)}}}$
$\displaystyle<1.$ $\displaystyle\Big{(}\frac{\lvert H_{1}\rvert}{\lvert
H_{2}\rvert}\Big{)}^{2}$ $\displaystyle<\lvert~{}^{2}D_{m}(2^{2})\rvert.$

Now,

$\displaystyle\Big{(}\frac{|~{}^{2}D_{m}(2^{2})|}{\lvert
H_{1}\rvert}\Big{)}^{2}$ $\displaystyle=((2^{m}+1)(2^{m-1}-1))^{2}$
$\displaystyle<2^{m(m-1)}(2^{m}+1)(2^{m-1}-1)(2^{m-1}+1)\prod_{i=1}^{m-2}(2^{2i}-1)$
$\displaystyle<2^{m(m-1)}(2^{m}+1)\prod_{i=1}^{m-1}(2^{2i}-1)$
$\displaystyle=\lvert~{}^{2}D_{m}(2^{2})\rvert.$

###  6.3 Exceptional Group of Lie Type

  1. (1)

$H=G_{2}(q)$; $q\geq 3$ (Method 1)

The group $G_{2}(q)$ is simple for all $q\geq 3$. It has order (see [4], p.
252),

$|G_{2}(q)|=q^{6}(q^{6}-1)(q^{2}-1).$

Thus, $G_{2}(q)$ has a Sylow $p$-subgroup $H_{2}$ of order $q^{6}$ and $\lvert
H_{2}\rvert^{2}\leq\rvert G_{2}(q)\lvert.$ Also, it has the Borel subgroup
$H_{1}$ of order $q^{6}(q-1)^{2}$ (see [29], p. 124).

Consider,

$\displaystyle\frac{\lvert H_{1}\rvert}{\lvert H_{2}\rvert^{2}}$
$\displaystyle=\frac{q^{6}(q-1)^{2}}{q^{12}}$
$\displaystyle=\frac{(q-1)^{2}}{q^{6}}$ $\displaystyle<1.$

Therefore,

$\Big{(}\frac{\lvert H_{1}\rvert}{\lvert H_{2}\rvert}\Big{)}^{2}\leq\lvert
H_{1}\rvert\leq\lvert H\rvert.$

Now,

$\displaystyle\frac{\lvert H\rvert}{|H_{1}|^{2}}$
$\displaystyle=\frac{q^{6}(q^{6}-1)(q^{2}-1)}{(q^{6}(q-1)^{2})^{2}}$
$\displaystyle<\frac{q^{6+2}}{q^{6}(q-1)^{4}}$
$\displaystyle<\frac{q^{2}}{(q-1)^{4}}$
$\displaystyle<1\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad(\text{by
Remark}\,\ref{Remark-1})$

Thus,

$\Big{(}\frac{|H|}{\lvert H_{1}\rvert}\Big{)}^{2}<\lvert H\rvert.$

  2. (2)

$H=F_{4}(q)$ (Method 2)

The finite simple group $F_{4}(q)$ has order (see [4], p. 252),

$|F_{4}(q)|=q^{24}(q^{12}-1)(q^{8}-1)(q^{6}-1)(q^{2}-1).$

It is known that (see [29], p. 156) the group $F_{4}(q)$ has a maximal
subgroup $q^{1+14}:Sp_{6}(q).C_{q-1}$ of order
$q^{24}(q^{6}-1)(q^{4}-1)(q^{2}-1)(q-1)$ say $H_{1}$. This subgroup has a
Sylow $p$-subgroup say $H_{2}$ of order $q^{24}$ and $\lvert
H_{2}\rvert^{2}\leq|F_{4}(q)|.$ Now,

$\displaystyle\frac{|H_{1}|}{\lvert H_{2}\rvert^{2}}$
$\displaystyle=\frac{q^{24}(q^{6}-1)(q^{4}-1)(q^{2}-1)(q-1)}{q^{48}}$
$\displaystyle<\frac{q^{1+2+4+6}}{q^{24}}$ $\displaystyle<1.$

Therefore,

$\Big{(}\frac{|H_{1}|}{\lvert H_{2}\rvert}\Big{)}^{2}<|H_{1}|<\lvert H\rvert.$

Now,

$\displaystyle\frac{\lvert H\rvert}{|H_{1}|^{2}}$
$\displaystyle=\frac{q^{24}(q^{12}-1)(q^{8}-1)(q^{6}-1)(q^{2}-1)}{(q^{24}(q^{6}-1)(q^{4}-1)(q^{2}-1)(q-1))^{2}}$
$\displaystyle=\frac{(q^{4}-1)^{2}(q^{8}+q^{4}+1)(q^{4}+1)}{q^{24}(q^{6}-1)(q^{4}-1)^{2}(q^{2}-1)(q-1)^{2}}$
$\displaystyle=(1+\frac{1}{q^{4}}+\frac{1}{q^{8}})(1+\frac{1}{q^{4}})\frac{1}{q^{12}(q^{6}-1)(q^{2}-1)(q-1)^{2}}$
$\displaystyle<1.$

Thus, we get

$\Big{(}\frac{\lvert H\rvert}{|H_{1}|}\Big{)}^{2}<\lvert H\rvert.$

  3. (3)

$H=E_{6}(q)$; $q>2$ (Method 1)

The group $E_{6}(q)$ is a finite simple group. The order of $H=E_{6}(q)$ is
(see [4], p. 252),

$|E_{6}(q)|=\frac{q^{36}}{(3,q-1)}(q^{12}-1)(q^{9}-1)(q^{8}-1)(q^{6}-1)(q^{5}-1)(q^{2}-1).$

Clearly, it has a Sylow $p$-subgroup $H_{2}$ of order $q^{36}$ and $\lvert
H_{2}\rvert^{2}\leq|E_{6}(q)|.$ Let $H_{1}$ be the Borel subgroup of $H$ then
the order of $H_{1}$ is $q^{36}(q-1)^{6}$ (see [29], [8]). Consider,

$\displaystyle\frac{\lvert H_{1}\rvert}{\lvert H_{2}\rvert^{2}}$
$\displaystyle=\frac{q^{36}(q-1)^{6}}{q^{72}}$
$\displaystyle<\frac{q^{6}}{q^{36}}$ $\displaystyle<1.$

Thus,

$\Big{(}\frac{\lvert H_{1}\rvert}{\lvert H_{2}\rvert}\Big{)}^{2}<\lvert
H_{1}\rvert<\lvert H\rvert.$

Now,

$\displaystyle\frac{\lvert H\rvert}{\lvert H_{1}\rvert^{2}}$
$\displaystyle=\frac{q^{36}(q^{12}-1)(q^{9}-1)(q^{8}-1)(q^{6}-1)(q^{5}-1)(q^{2}-1)}{(3,q-1)(q^{36}(q-1)^{8})^{2}}$
$\displaystyle<\frac{q^{12+9+8+6+5+2}}{(3,q-1)q^{36}(q-1)^{16}}$
$\displaystyle=\frac{q^{42}}{(3,q-1)q^{36}(q-1)^{16}}$
$\displaystyle=\frac{q^{6}}{(3,q-1)(q-1)^{16}}$
$\displaystyle=\frac{1}{(3,q-1)(q-1)^{4}}\frac{q^{6}}{(q-1)^{12}}$
$\displaystyle<\frac{q^{6}}{(q-1)^{12}}$
$\displaystyle<1.\quad\quad\quad\quad\quad\quad\quad\quad\quad(\text{by
Remark}\,\ref{Remark-1})$

This implies that,

$\Big{(}\frac{\lvert H\rvert}{\lvert H_{1}\rvert}\Big{)}^{2}\leq\lvert
H\rvert.$

Notice that, the group $E_{6}(2)$ is of constant order. However, we can use
Method 2 to reduce the constants $b_{1}$, $b_{2}$ to $1$. By taking $H_{1}$ to
be maximal subgroup of order (see [9]) $2^{36}\cdot 3^{3}\cdot 5\cdot 7\cdot
31$ and $H_{2}$ to be its Sylow $2$-subgroup of order $2^{36}$.

  4. (4)

$H=~{}^{2}E_{6}(q)$ (Method 1)

The group ${}^{2}E_{6}(q)$ is simple for all $q$ and it has order (see [4], p.
252),

$|~{}^{2}E_{6}(q)|=\frac{q^{36}(q^{2}-1)(q^{5}+1)(q^{6}-1)(q^{8}-1)(q^{9}+1)(q^{12}-1)}{(3,q+1)}.$

The group $~{}^{2}E_{6}(q)$ has a Sylow $p$-subgroup $H_{2}$ of order $q^{36}$
and $\lvert H_{2}\rvert^{2}\leq|H|.$ It is well known that the order of the
Borel subgroup is a product of the order of the Sylow $p$-subgroup and the
maximal torus. The order of the maximal torus in $H$ is $(q+1)^{6}$(see [29],
p. 173). Thus, the order of the Borel subgroup $H_{1}$ of $H$ is
$q^{36}(q+1)^{6}$.

Consider,

$\displaystyle\frac{\lvert H_{1}\rvert}{\lvert H_{2}\rvert^{2}}$
$\displaystyle=\frac{q^{36}(q+1)^{6}}{q^{72}}$
$\displaystyle<\frac{(q+1)^{6}}{q^{36}}$
$\displaystyle<\frac{(q+q)^{6}}{q^{36}}$ $\displaystyle<1.$

Thus,

$\Big{(}\frac{|H_{1}|}{\lvert H_{2}\rvert}\Big{)}^{2}<\lvert
H_{1}\rvert<\lvert H\rvert.$

Also,

$\displaystyle\frac{\lvert H\rvert}{|H_{1}|^{2}}$
$\displaystyle=\frac{q^{36}(q^{2}-1)(q^{5}+1)(q^{6}-1)(q^{8}-1)(q^{9}+1)(q^{12}-1)}{(q^{36}(q+1)^{6})^{2}}$
$\displaystyle<\frac{(q^{5}+1)(q^{9}+1)}{q^{8}(q+1)^{12}}$ $\displaystyle<1.$

Therefore,

$\Big{(}\frac{\lvert H\rvert}{\lvert H_{1}\rvert}\Big{)}^{2}<\lvert H\rvert.$

  5. (5)

$H=~{}^{3}D_{4}(q)$ (Method 1)

The group ${}^{3}D_{4}(q)$ is simple for all $q$. It is known that the order
of the group ${}^{3}D_{4}(q)$ is (see [4], p. 252),

$|~{}^{3}D_{4}(q)|=q^{12}(q^{8}+q^{4}+1)(q^{6}-1)(q^{2}-1).$

Clearly, it has a Sylow $p$-subgroup $H_{2}$ of order $q^{12}$ and the Borel
subgroup $H_{1}$ of order $q^{12}(q^{3}-1)(q-1)$ (see [29], p. 141). Also,
notice that $\lvert H_{2}\rvert^{2}\leq\lvert H\rvert.$

Consider,

$\displaystyle\frac{\lvert H_{1}\rvert}{\lvert H_{2}\rvert^{2}}$
$\displaystyle=\frac{q^{12}(q^{3}-1)(q-1)}{q^{24}}$
$\displaystyle=\frac{(q^{3}-1)(q-1)}{q^{12}}$
$\displaystyle<\frac{q^{4}}{q^{12}}$ $\displaystyle<1.$

Thus,

$\Big{(}\frac{|H_{1}|}{\lvert H_{2}\rvert}\Big{)}^{2}<|H_{1}|<\lvert H\rvert.$
$\displaystyle\frac{\lvert H\rvert}{|H_{1}|^{2}}$
$\displaystyle=\frac{q^{12}(q^{8}+q^{4}+1)(q^{6}-1)(q^{2}-1)}{(q^{12}(q^{3}-1)(q-1))^{2}}$
$\displaystyle=\frac{(q^{8}+q^{4}+1)(q^{3}+1)(q+1)}{q^{12}(q^{3}-1)(q-1)}$
$\displaystyle=\frac{(1+\frac{1}{q^{4}}+\frac{1}{q^{8}})(1+\frac{1}{q^{3}})(1+\frac{1}{q})}{(q^{3}-1)(q-1)}$
$\displaystyle<1.$

Therefore,

$\Big{(}\frac{\lvert H\rvert}{\lvert H_{1}\rvert}\Big{)}^{2}<\lvert H\rvert.$

  6. (6)

$H=E_{7}(q)$, $q>2$ (Method 1)

The simple group $E_{7}(q)$ has order (see [4], p. 252),

$|E_{7}(q)|=\frac{q^{63}}{(2,q-1)}(q^{18}-1)(q^{14}-1)(q^{12}-1)(q^{10}-1)(q^{8}-1)(q^{6}-1)(q^{2}-1).$

Clearly, it has a Sylow $p$-subgroup $H_{2}$ of order $q^{63}$ and $\lvert
H_{2}\rvert^{2}\leq\lvert H\rvert.$ Let $H_{1}$ be the borel subgroup of $H$
then its order is (see [29], [8]),

$\lvert H_{1}\rvert=q^{63}(q-1)^{7}.$

Consider,

$\displaystyle\frac{\lvert H_{1}\rvert}{\lvert H_{2}\rvert^{2}}$
$\displaystyle=\frac{q^{63}(q-1)^{7}}{q^{126}}$
$\displaystyle<\frac{q^{7}}{q^{63}}$ $\displaystyle<1$

Thus,

$\Big{(}\frac{\lvert H_{1}\rvert}{\lvert H_{2}\rvert}\Big{)}^{2}<\lvert
H_{1}\rvert<\lvert H\rvert.$ $\displaystyle\frac{\lvert H\rvert}{\lvert
B\rvert^{2}}$
$\displaystyle=\frac{\frac{q^{63}}{(2,q-1)}(q^{18}-1)(q^{14}-1)(q^{12}-1)(q^{10}-1)(q^{8}-1)(q^{6}-1)(q^{2}-1)}{(q^{63}(q-1)^{7})^{2}}$
$\displaystyle<\frac{q^{18+14+12+10+8+6+2}}{(2,q-1)q^{63}(q-1)^{14}}$
$\displaystyle=\frac{q^{70}}{(2,q-1)q^{63}(q-1)^{14}}$
$\displaystyle=\frac{1}{(2,q-1)}\frac{q^{7}}{(q-1)^{14}}$
$\displaystyle<1.\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad(q\neq
2).$

Therefore,

$\Big{(}\frac{\lvert H\rvert}{\lvert H_{1}\rvert}\Big{)}^{2}<\lvert H\rvert.$

Notice that, the group $E_{7}(2)$ is of constant order. However, we can use
Method 2 to reduce the constants $b_{1}$, $b_{2}$ to $1$. By taking $H_{1}$ to
be maximal subgroup of order (see [9]) $2^{63}\cdot 3^{4}\cdot 7^{2}\cdot 5$
and $H_{2}$ to be its Sylow $2$-subgroup of order $2^{63}$.

  7. (7)

$H=E_{8}(q)$, $q>2$ (Method 1)

We know that the group $E_{8}(q)$ is simple for all $q$ and has order (see
[4], p. 252),

$|H|=q^{120}(q^{30}-1)(q^{24}-1)(q^{20}-1)(q^{18}-1)(q^{14}-1)(q^{12}-1)(q^{8}-1)(q^{2}-1).$

The group $E_{8}(q)$ has a Sylow $p$-subgroup $H_{2},$ then $\lvert
H_{2}\rvert=q^{120}$ and $\lvert H_{2}\rvert^{2}\leq|H|.$ Let $H_{1}$ be the
Borel subgroup then order $\lvert H_{1}\rvert=q^{120}(q-1)^{8}$ (see [29], p.
176).

Consider,

$\displaystyle\frac{\lvert H_{1}\rvert}{\lvert H_{2}\rvert^{2}}$
$\displaystyle=\frac{q^{120}(q-1)^{8}}{q^{240}}$
$\displaystyle<\frac{q^{8}}{q^{120}}$ $\displaystyle<1.$

Threfore,

$\Big{(}\frac{|H_{1}|}{\lvert H_{2}\rvert}\Big{)}^{2}<|H_{1}|<\lvert H\rvert.$
$\displaystyle\frac{\lvert H\rvert}{|H_{1}|^{2}}$
$\displaystyle=\frac{q^{120}(q^{30}-1)(q^{24}-1)(q^{20}-1)(q^{18}-1)(q^{14}-1)(q^{12}-1)(q^{8}-1)(q^{2}-1)}{(q^{120}(q-1)^{8})^{2}}$
$\displaystyle=\frac{(q^{8}-1)}{(q-1)^{16}}\prod_{i\in\\{2,12,14,18,20,24,30\\}}(1-\frac{1}{q^{i}})$
$\displaystyle\leq\frac{q^{8}}{(q-1)^{16}}$ $\displaystyle\leq
1.\quad\quad\quad\quad\quad\quad\quad\quad\quad(\text{by
Remark}\,\ref{Remark-1})$

This implies that,

$\Big{(}\frac{\lvert H\rvert}{\lvert H_{1}\rvert}\Big{)}^{2}\leq\lvert
H\rvert.$

Notice that, the group $E_{8}(2)$ is of constant order. However, we can use
Method 2 to reduce the constants $b_{1}$, $b_{2}$ to $1$. By taking $H_{1}$ to
be maximal subgroup of order (see [9]) $2^{119}\cdot 3^{4}\cdot 5\cdot
7^{2}\cdot 31$ and $H_{2}$ to be its Sylow $2$-subgroup of order $2^{119}$.

  8. (8)

$H=~{}^{2}B_{2}(q)$, $q=2^{2t+1}$ and $t\geq 1$ (Method 1)

The finite simple group ${}^{2}B_{2}(q)$ has order (see [4], p. 252),

$|H|=q^{2}(q^{2}+1)(q-1).$

Thus, it has a Sylow 2-subgroup $H_{2}$ of order $q^{2}$ and $\lvert
H_{2}\rvert^{2}\leq\lvert H\rvert.$ Let $H_{1}$ be the Borel subgroup of
${}^{2}B_{2}(q)$ then the order $H_{1}$ is $q^{2}(q-1)$ (see [29], p. 117).

Consider,

$\displaystyle\frac{\lvert H_{1}\rvert}{\lvert H_{2}\rvert^{2}}$
$\displaystyle=\Big{(}\frac{q^{2}(q-1)}{q^{4}}\Big{)}$ $\displaystyle<1.$

Therefore,

$\Big{(}\frac{\lvert H_{1}\rvert}{\lvert H_{2}\rvert}\Big{)}^{2}<\lvert
H_{1}\rvert<\lvert H\rvert.$

Now,

$\displaystyle\frac{\lvert H\rvert}{|H_{1}|^{2}}$
$\displaystyle=\frac{q^{2}(q^{2}+1)(q-1)}{(q^{2}(q-1))^{2}}$
$\displaystyle=\frac{(q^{2}+1)}{q^{2}(q-1)}$
$\displaystyle=\frac{1+\frac{1}{q^{2}}}{q-1}$ $\displaystyle<1.$

Thus,

$\Big{(}\frac{\lvert H\rvert}{\lvert H_{1}\rvert}\Big{)}^{2}<|H|.$

  9. (9)

$H=~{}^{2}G_{2}(q)$; where, $q=3^{2t+1}$ and $t\geq 1$ (Method 1)

The group ${}^{2}G_{2}(q)$ has order (see [4], p. 252),

$\lvert~{}^{2}G_{2}(q)\rvert=q^{3}(q^{3}+1)(q-1).$

Thus, ${}^{2}G_{2}(q)$ has a Sylow 3-subgroup of order $q^{3}$ and $\lvert
H_{2}\rvert^{2}<\lvert H\rvert.$ Also, ${}^{2}G_{2}(q)$ has the Borel subgroup
$H_{1}$ of order $q^{3}(q-1)$ (see[29], p. 137).

Consider,

$\displaystyle\frac{\lvert H_{1}\rvert}{\lvert H_{2}\rvert^{2}}$
$\displaystyle=\frac{q^{3}(q-1)}{q^{6}}$ $\displaystyle<1.$

Therefore,

$\Big{(}\frac{\lvert H_{1}\rvert}{\lvert H_{2}\rvert}\Big{)}^{2}<\lvert
H_{1}\rvert<\lvert H\rvert.$

Now,

$\displaystyle\frac{\lvert H\rvert}{\lvert H_{1}\rvert^{2}}$
$\displaystyle=\frac{q^{3}(q^{3}+1)(q-1)}{(q^{3}(q-1))^{2}}$
$\displaystyle=\frac{(q^{3}+1)}{q^{3}(q-1)}$
$\displaystyle=\frac{1+\frac{1}{q^{3}}}{q-1}$ $\displaystyle<1.$

Therefore,

$\Big{(}\frac{\lvert H\rvert}{\lvert H_{1}\rvert}\Big{)}^{2}<\lvert H\rvert.$

  10. (10)

$H=~{}^{2}F_{4}(q)$, $q=2^{2t+1}$ and $t\geq 1$ (Method 1)

The order of the group ${}^{2}F_{4}(q)$ is
$q^{12}(q^{6}+1)(q^{4}-1)(q^{3}+1)(q-1)$ (see [4], p. 252). Thus, it has a
Sylow $2$-subgroup of order $q^{12}$ and $\lvert H_{2}\rvert^{2}<|H|.$ Also,
${}^{2}F_{4}(q)$ has the Borel subgroup $H_{1}$ of order $q^{12}(q-1)^{2}$
(see [29], p. 165).

Consider,

$\displaystyle\frac{\lvert H_{1}\rvert}{\lvert H_{2}\rvert^{2}}$
$\displaystyle=\frac{q^{12}(q-1)^{2}}{q^{24}}$ $\displaystyle<1.$

Therefore,

$\Big{(}\frac{\lvert H_{1}\rvert}{\lvert H_{2}\rvert}\Big{)}^{2}<\lvert
H_{1}\rvert<\lvert H\rvert.$ $\displaystyle\frac{\lvert H\rvert}{\lvert
H_{1}\rvert^{2}}$
$\displaystyle=\frac{q^{12}(q^{6}+1)(q^{4}-1)(q^{3}+1)(q-1)}{(q^{12}(q-1)^{2})^{2}}$
$\displaystyle=\frac{(q^{6}+1)(q^{4}-1)(q^{3}+1)(q-1)}{q^{12}(q-1)^{4}}$
$\displaystyle=\frac{(q^{6}+1)(q^{4}-1)(q^{3}+1)}{q^{12}(q-1)^{3}}$
$\displaystyle<\frac{q^{4}(1+\frac{1}{q^{6}})(1+\frac{1}{q^{3}})}{q^{3}(q-1)^{3}}$
$\displaystyle=\frac{q(1+\frac{1}{q^{6}})(1+\frac{1}{q^{3}})}{(q-1)^{3}}$
$\displaystyle<1.$

This implies that,

$\Big{(}\frac{|H)|}{\lvert H_{1}\rvert}\Big{)}^{2}<\lvert H\rvert.$

  11. (11)

$H=~{}^{2}F_{4}(2)^{\prime};$ (Method 2)

The simple group $H=~{}^{2}F_{4}(2)^{\prime};$ has order $17971200.$ It is
known that $H$ has a maximal subgroup of order $11232$. We take $H_{1}$ to be
this maximal subgroup and $H_{2}$ to be the Sylow $2$-subgroup of $H_{1}$
which has order $32$. Thus, we get $b_{1}=b_{2}=1$.

###  6.4 Tables

In this section we cover the details of Sporadic simple groups (Table 2), and
the order of all the simple groups that we define in cases (ii)-(iv) of
Theorem 5.1 in Table 3 and 4. These tables also contain the order of the
subgroups $H_{2}$ and $H_{1}$. Table 2 represents the information about the
subgroups $H_{2}$ and $H_{1}$ of the Sporadic simple groups.

$H$ |  Order of $H$ |  Order of $H_{2}$ |  Order of $H_{1}$ |  $b_{1}$ |  $b_{2}$
---|---|---|---|---|---
${\rm M_{11}}$ |  7920 |  $2^{4}$ |  720 |  $1$ |  $1$
${\rm M_{12}}$ |  95040 |  $2^{2}$ |  660 |  $1$ |  $1$
${\rm M_{22}}$ |  443520 |  $2^{6}$ |  20160 |  $1$ |  $1$
${\rm M_{23}}$ |  10200960 |  $2^{7}$ |  443520 |  $1$ |  $1$
${\rm M_{24}}$ |  244823040 |  $2^{8}$ |  887040 |  $1$ |  $1$
${\rm{Co}_{1}}$ |  4157776806543360000 |  262144 |  42305400000000 |  $1$ |  $1$
${\rm{Co}_{2}}$ |  42305400000000 |  262144 |  908328960 |  $1$ |  $1$
${\rm{Co}_{3}}$ |  495767000000 |  $2^{7}$ |  10200960 |  $1$ |  $1$
${\rm McL}$ |  $898128000$ |  $3^{6}$ |  $3^{6}\cdot 2^{7}\cdot 7\cdot 5$ |  $1$ |  $1$
${\rm HS}$ |  $44352000$ |  $2^{7}$ |  $2^{7}\cdot 3^{2}\cdot 5\cdot 7\cdot 11$ |  $1$ |  $1$
${\rm Suz}$ |  $448345497600$ |  $2^{12}$ |  $251596800$ |  $1$ |  $1$
${\rm J_{2}}$ |  604800 |  $2^{5}$ |  6048 |  $1$ |  $1$
${\rm Fi_{22}}$ |  $64561751654400$ |  $2^{16}$ |  $2^{16}(2^{6}-1)(2^{5}+1)(2^{4}-1)(2^{3}+1)$ |  $1$ |  $1$
${\rm Fi_{23}}$ |  $4089470473293004800$ |  $2^{18}$ |  $2^{18}\cdot 3^{9}\cdot 5^{2}\cdot 7\cdot 11\cdot 13$ |  $1$ |  $1$
${\rm Fi^{`}_{24}}$ |  1255205709190661721292800 |  $2^{19}$ |  $2^{19}\cdot 3^{13}\cdot 5^{2}\cdot 7\cdot 11\cdot 13\cdot 17\cdot 23$ |  $1$ |  $1$
${\rm\mathbb{M}}$ |  $t_{1}$ |  $2^{42}$ |  $t_{2}$ |  $1$ |  $1$
${\rm\mathbb{B}}$ |  $t_{3}$ |  238 |  $t_{4}$ |  $1$ |  $1$
${\rm Th}$ |  $90745943887872000$ |  $2^{15}$ |  $319979520$ |  $1$ |  $1$
${\rm HN}$ |  $273030912000000$ |  $2^{9}$ |  $239500800$ |  $1$ |  $1$
${\rm He}$ |  $4030387200$ |  $2^{8}$ |  $2^{8}\cdot 255\cdot 15$ |  $1$ |  $1$
${\rm J_{1}}$ |  175560 |  $2^{2}$ |  660 |  $1$ |  $1$
${\rm J_{3}}$ |  50232960 |  $2^{5}$ |  8160 |  $1$ |  $1$
${\rm J_{4}}$ |  86775571046077562880 |  2097152 |  57161637225 |  $1$ |  $1$
${\rm O^{\prime}N}$ |  $460815505920$ |  $2^{6}$ |  $3753792$ |  $1$ |  $1$
${\rm Ly}$ |  $51765179004000000$ |  $15625$ |  $5859000000$ |  $1$ |  $5$
${\rm Ru}$ |  $145926144000$ |  $2^{12}$ |  $35942400$ |  $1$ |  $1$
Table 2: Table representing the constant factor and Method used for choosing
suitable subgroups

In Table 2 we consider the values of $t_{i},i=1,2,3,4$ as follows.

$t_{1}=808017424794512875886459904961710757005754368000000000$

$t_{2}=2^{42}\cdot 3^{13}\cdot 5^{6}\cdot 7^{2}\cdot 11\cdot 13\cdot 17\cdot
19\cdot 23\cdot 31\cdot 47$

$t_{3}=4154781481226426191177580544000000$

$t_{4}=2^{38}\cdot(2^{12}-1)\cdot(2^{9}+1)\cdot(2^{8}-1)\cdot(2^{6}-1)\cdot(2^{5}+1)\cdot(2^{2}-1)$.

In the Table 3, the values of $c_{mi},i=1,2,3,4,5$ are as follows.

$c_{m1}=\frac{q^{\frac{m(m+1)}{2}}}{(q+1,m+1)}$ $(q-1)^{\lfloor
m/2\rfloor}(q+1)^{\lceil\frac{m-1}{2}\rceil}$,
$c_{m2}=\frac{3}{(3,m+1)}\frac{{2^{\frac{m(m+1)}{2}}}\prod_{i=1}^{m}(2^{i+1}-(-1)^{i+1})}{(2^{m+1}-(-1)^{m+1})(2^{m}-(-1)^{m})}$

$c_{m3}=\frac{3}{(3,m+1)}{2^{\frac{m(m-1)}{2}}}\prod_{i=1}^{m-1}(2^{i+1}-(-1)^{i+1})$,
$c_{m4}=2^{m^{2}-m+1}(2^{m}+1)\prod_{i=1}^{m-1}(2^{2i}-1)$

$c_{m5}=2^{m(m-1)}(2^{m-1}+1)\prod_{i=1}^{m-2}(2^{2i}-1)$.

$H$ |  $\lvert H\rvert$ |  $\lvert H_{2}\rvert$ |  $\lvert H_{1}\rvert$
---|---|---|---
$A_{m}(q)$; $q>2$ |  $\frac{q^{\frac{m(m+1)}{2}}\prod_{i=1}^{m}(q^{i+1}-1)}{(q-1,m+1)}$ |  $q^{\frac{m(m+1)}{2}}$ |  $\frac{q^{\frac{m(m+1)}{2}}}{(q-1,m+1)}(q-1)^{m}$
$A_{m}(2)$; $q=2$ |  $2^{\frac{m(m+1)}{2}}\prod_{i=1}^{m}(2^{i+1}-1)$ |  $2^{\frac{m(m+1)}{2}}$ |  $\frac{2^{\frac{m(m+1)}{2}}\prod_{i=1}^{m}(2^{i+1}-1)}{(2^{m+1}-1)}$
${}^{2}A_{m}(q^{2})$; $q>2$, $m>1$ |  $\frac{q^{\frac{m(m+1)}{2}}}{(q+1,m+1)}\prod_{i=1}^{m}(q^{i+1}-(-1)^{i+1})$ |  $q^{\frac{m(m+1)}{2}}$ |  $c_{m1}$
${}^{2}A_{m}(2^{2})$; $q=2$, $m>1$, $6\nmid(m-1)$ |  $\frac{2^{\frac{m(m+1)}{2}}}{(3,m+1)}\prod_{i=1}^{m}(2^{i+1}-(-1)^{i+1})$ |  $2^{\frac{m(m+1)}{2}}$ |  $c_{m2}$
${}^{2}A_{m}(2^{2})$; $q=2$, $m>1$, $6\mid(m-1)$ |  $\frac{2^{\frac{m(m+1)}{2}}}{(3,m+1)}\prod_{i=1}^{m}(2^{i+1}-(-1)^{i+1})$ |  $2^{\frac{m(m-1)}{2}}$ |  $c_{m3}$
$C_{m}(q)$; $q>2$, $m>2$ |  $\frac{q^{m^{2}}\prod_{i=1}^{m}(q^{2i}-1)}{(2,q-1)}$ |  $q^{m^{2}}$ |  $\frac{q^{m^{2}}}{(2,q-1)}(q-1)^{m}$
$C_{m}(2)$; $q=2$, $m>2$ |  $2^{m^{2}}\prod_{i=1}^{m}(2^{2i}-1)$ |  $2^{m^{2}-m+1}$ |  $c_{m4}$
$B_{m}(q)$; $q$ odd, $m>1$ |  $\frac{q^{m^{2}}\prod_{i=1}^{m}(q^{2i}-1)}{(2,q-1)}$ |  $q^{m^{2}}$ |  $\frac{q^{m^{2}}}{(2,q-1)}(q-1)^{m}$
$D_{m}(q)$; $q>2$, $m>3$ |  $\frac{q^{{m(m-1)}}(q^{m}-1)\prod_{i=1}^{m-1}(q^{2i}-1)}{(4,q^{m}-1)}$ |  $q^{{m(m-1)}}$ |  $\frac{q^{{m(m-1)}}}{(4,q^{m}-1)}(q-1)^{m}$
$D_{m}(2)$; $q=2$,
$m>3$ |  $2^{{m(m-1)}}(2^{m}-1)\prod_{i=1}^{m-1}(2^{2i}-1)$ |  $2^{m^{2}-2m+1}$ |  $2^{m^{2}-2m+1}\prod_{i=1}^{m-1}(2^{2i}-1)$
${}^{2}D_{m}(q^{2})$;
$q>2$, $m>3$ |  $\frac{q^{m(m-1)}(q^{m}+1)}{(4,q^{m}+1)}\prod_{i=1}^{m-1}(q^{2i}-1)$ |  $q^{{m(m-1)}}$ |  $\frac{q^{{m(m-1)}}}{(4,q^{n}+1)}(q-1)^{m}$
${}^{2}D_{m}(2^{2})$; $q=2$, $m>3$ |  $\frac{2^{m(m-1)}(2^{m}+1)}{(4,2^{m}+1)}\prod_{i=1}^{m-1}(2^{2i}-1)$ |  $2^{m(m-1)}$ |  $c_{m5}$
Table 3: Order of the simple groups (case (iii) of Theorem 5.1) and order of its subgroups $H_{2},H_{1}$.  $G_{2}(q)$ |  $q^{6}(q^{6}-1)(q^{2}-1)$ |  $q^{6}$ |  $q^{6}(q-1)^{2}$
---|---|---|---
$F_{4}(q)$ |  $q^{24}\prod_{i\in\\{2,6,8,12\\}}(q^{i}-1)$ |  $q^{24}$ |  $q^{24}\prod_{i\in\\{1,2,4,6\\}}(q^{i}-1)$
$E_{6}(q)$, $q>2$ |  $\frac{q^{36}}{(3,q-1)}\prod_{i\in\\{2,5,6,8,9,12\\}}(q^{i}-1)$ |  $q^{36}$ |  $q^{36}(q-1)^{6}$
$E_{6}(2)$ |  $2^{36}\prod_{i\in\\{2,5,6,8,9,12\\}}(2^{i}-1)$ |  $2^{36}$ |  $2^{36}\cdot 3^{3}\cdot 5\cdot 7\cdot 31$
${}^{2}E_{6}(q)$ |  $\frac{q^{36}(q^{9}+1)}{(3,q+1)}\prod_{i\in\\{2,5,6,8,12\\}}(q^{i}-1)$ |  $q^{36}$ |  $q^{36}(q-1)^{4}(q+1)^{2}$
${}^{3}D_{4}(q)$ |  $q^{12}(q^{8}+q^{4}+1)(q^{6}-1)(q^{2}-1)$ |  $q^{12}$ |  $q^{12}$ $(q^{3}-1)(q-1)$
$E_{7}(q)$, $q>2$ |  $\frac{q^{63}}{(2,q-1)}\prod_{i\in\\{2,6,8,10,12,14,18\\}}(q^{i}-1)$ |  $q^{63}$ |  $q^{63}(q-1)^{7}$
$E_{7}(2)$ |  $2^{63}\prod_{i\in\\{2,6,8,10,12,14,18\\}}(2^{i}-1)$ |  $2^{63}$ |  $2^{63}\cdot 3^{4}\cdot 7^{2}\cdot 5$
$E_{8}(q)$, $q>2$ |  $q^{120}\prod_{i\in\\{2,8,12,14,18,20,24,30\\}}(q^{i}-1)$ |  $q^{120}$ |  $q^{120}(q-1)^{8}$
$E_{8}(2)$ |  $2^{120}\prod_{i\in\\{2,8,12,14,18,20,24,30\\}}(2^{i}-1)$ |  $2^{119}$ |  $2^{119}\cdot 3^{4}\cdot 5\cdot 7^{2}\cdot 31$
${}^{2}B_{2}(q)$;
$q=2^{2t+1},$ $t\geq 1$ |  $q^{2}(q^{2}+1)(q-1)$ |  $q^{2}$ |  $q^{2}(q-1)$
${}^{2}G_{2}(q)$;
$q=3^{2t+1},$ $t\geq 1$ |  $q^{3}(q^{3}+1)(q-1)$ |  $q^{3}$ |  $q^{3}(q-1)$
${}^{2}F_{4}(q)$;
$q=2^{2t+1},$ $t\geq 1$ |  $q^{12}(q^{6}+1)(q^{4}-1)(q^{3}+1)(q-1)$ |  $q^{12}$ |  $q^{12}(q-1)^{2}$
Table 4: Order of the simple groups (case (iv) of Theorem 5.1) and order of
its subgroups $H_{2},H_{1}$.