Counting supersolvable and solvable group orders

ABSTRACT

For more than 100 years, group and number theorists have been interested in quesitons such as: (a) If a group G has order $|\mathit{G}|=\prod p_i^{{\alpha }_i}$ (p_i distinct primes), what conditions on the primes p_i and their exponents α_i ensure that G is cyclic, or G is abelian, or G is nilpotent, or supersolvable, or solvable? (b) How fast does $\mathit{g}(\mathit{n})=|\{\mathit{m}\le \mathit{n}\mid$ every group G of order m has one of these properties$\}|$ grow as a function of n? Questions (a) and (b) have been answered when the property is either cyclic, abelian, or nilpotent. However, when the property is supersolvable or solvable, only question (a) has been fully answered. We greatly increase the current lower bounds for g(n) when the property is supersolvable or solvable. In the latter case, our lower bound is just below the best upper bound known. We used the MANA high performance computing cluster of the University of Hawaii at Manoa to greatly increase the current lower bounds for g(n) when the property is supersolvable or solvable.

KEYWORDS:

• Group theory
• supersolvable
• high performance computing

MATHEMATICS SUBJECT CLASSIFICATION:

• 20F16

1. Introduction

All groups here are finite. A group G is cyclic if there is an element $\mathit{g}\in \mathit{G}$ such that every element of G may be expressed as a power g^m of g (where m is an integer). A group G is abelian if for every pair $\mathit{a},\mathit{b}\in \mathit{G}$, ab = ba. A sequence $1=N_0\le N_1\le \cdots \le N_r=\mathit{G}$ of normal subgroups of G is a central series for G if for $1\le \mathit{i}\le \mathit{r}$ we have $N_i/N_{\mathit{i}-1}\le \mathit{Z}(\mathit{G}/N_{\mathit{i}-1})$, the center of $\mathit{G}/N_{\mathit{i}-1}$. A group is nilpotent if it has a central series. G is nilpotent if and only if every maximal subgroup of G is normal. G is supersolvable if there exist normal subgroups N_i of G with $1=N_0\le N_1\le \cdots \le N_r=\mathit{G}$ where each factor $N_i/N_{\mathit{i}-1}$ is cyclic. G is supersolvable if and only if every maximal subgroup $\mathit{M}\le \mathit{G}$ has prime index $[\mathit{G}:\mathit{M}]$ (Huppert, 1954). G is solvable if there exist normal subgroups N_i of G with $1=N_0\le N_1\le \cdots \le N_r=\mathit{G}$ where each $N_i/N_{\mathit{i}-1}$ is abelian.

There is exactly one isomorphism class of groups of order n if and only if every group of order n is cyclic. Miller (1935, Collected Works I) was the first to discover that there is exactly one isomorphism class of groups of order n if and only if $(\mathit{n},\mathit{\phi }(\mathit{n}))=1$, where $\mathit{\phi }(\mathit{n})\text{ (Eulers totient function)}=|\{\mathit{m}\le \mathit{n}\mid (\mathit{m},\mathit{n})=1\}|=\mathit{n}\prod _{\text{primes }\mathit{p}\mid \mathit{n}}(1-\frac{1}{p})$. Thus, for example, every group of order 15 is cyclic. If we set

$\begin{array}{l}\mathit{C}(\mathit{n})=|\{\mathit{m}\le \mathit{n}\mid \text{every group of order }\mathit{m}\text{ is cyclic}\}|\end{array}$

then $\mathit{C}(\mathit{n})=|\{\mathit{m}\le \mathit{n}\mid \mathit{m}$ is square free and no two prime factors p,q of m satisfy p ≡ 1 (mod q)}|.

Similarly,(Dickson, 1905), a group of order $\mathit{n}=\prod p_i^{{\alpha }_i}$ (p_i distinct primes) is abelian if and only if (i) each ${\alpha }_i\le 2$ and (ii) $(p_i,p_j^{{\alpha }_j}-1)=1$ for every $\mathit{i},\mathit{j}$. Thus, for example, every group of order 45 is abelian. If we set

$\begin{array}{l}\mathit{A}(\mathit{n})=|\{\mathit{m}\le \mathit{n}\mid \text{every group of order }\mathit{m}\text{ is abelian}\}|\end{array}$

then $\mathit{A}(\mathit{n})=|\{\mathit{m}\le \mathit{n}\mid \mathit{m}=\prod p_i^{{\alpha }_i}$ where each ${\alpha }_i\le 2$ and $(p_i,p_j^{{\alpha }_j}-1)=1$ for every $\mathit{i},\mathit{j}\}|$.

Also, Bachman (1960) proved that a group of order $\mathit{n}=\prod p_i^{{\alpha }_i}$ is nilpotent if and only if for every $\mathit{i},\mathit{j}$, $(p_i,\prod _{\mathit{\lambda }=1}^{{\alpha }_j}(p_j^{\lambda }-1))=1$. Thus, for example, every group of order $135=3^3\cdot 5$ is nilpotent. If we set

$\begin{array}{l}\mathit{N}(\mathit{n})=|\{\mathit{m}\le \mathit{n}\mid \text{every group of order }\mathit{m}\text{ is nilpotent}\}|\end{array}$

then $\mathit{N}(\mathit{n})=|\{\mathit{m}\le \mathit{n}\mid \mathit{m}=\prod p_i^{{\alpha }_i}\text{ and for every}$ $\mathit{i},\mathit{j},(p_i,\prod _{\mathit{\lambda }=1}^{{\alpha }_j}(p_j^{\lambda }-1))=1\}|$.

Finally, let $\mathit{\psi }(p^k)$ be the multiplicative function defined on prime powers by $\mathit{\psi }(p^k)=(p^k-1)(p^{\mathit{k}-1}-1)\dots (\mathit{p}-1)$. Then, in [Pazderski (1959), pg. 335], we find a proof that a group of order $\mathit{n}=\prod _{\mathit{i}=1}^t{p}_i^{{\alpha }_i}$ $(p_1<p_2<\cdots <p_t)$ is supersolvable if and only if:

1. For all $1\le \mathit{i}\le \mathit{t}$, the distinct prime factors of $(\mathit{n},\mathit{\psi }(p_i^{{\alpha }_i}))$ are the same as those of $(\mathit{n},p_i-1)$.

2. If there exists $\mathit{i}\ne \mathit{k}$ such that $p_i\le {\alpha }_k$ (i.e. some prime factor of n is less than or equal to the multiplicity of another prime factor of n), then

   1. There does not exist a prime p_j such that $p_i\mid (p_j-1)$ and $p_j\mid (p_k-1)$, and

   2. ${\alpha }_i\le 2$, and if ${\alpha }_i=2$ then $p_i^2\mid (p_k-1)$. Thus, for example, every group of order 54 is supersolvable. If we set

$\begin{array}{ll}\mathit{U}(\mathit{n})=& |\{\mathit{m}\le \mathit{n}\mid \text{every group of order }\mathit{m}\\ & \text{is supersolvable}\}|\end{array}$

then $\mathit{U}(\mathit{n})=|\{\mathit{m}\le \mathit{n}\mid \mathit{m}=\prod _{\mathit{i}=1}^t{p}_i^{{\alpha }_i}(p_1<p_2<\cdots <p_t)$ and m (replacing n) satisfies (1) and (2)(a),(b) above$\}|$. Finally, set

$\begin{array}{l}\mathit{S}(\mathit{n})=|\{\mathit{m}\le \mathit{n}\mid \text{every group of order }\mathit{m}\text{ is solvable}\}|\end{array}$

and note that $\mathit{C}(\mathit{n})\le \mathit{A}(\mathit{n})\le \mathit{N}(\mathit{n})\le \mathit{U}(\mathit{n})\le \mathit{S}(\mathit{n})$.

In Pakianathan & Shankar (2000), we find criteria based on J. Thompson’s deep result (Thompson, 1968) on minimal simple groups, for the positive integer m to be a solvable group order, that is every group of order m is solvable: m is a solvable group order if and only if m is not a multiple of any of (i) $2^p(2^p-1)$, p a prime (ii) $3^p(3^{2\mathit{p}}-1)/2$, p an odd prime (iii) $\mathit{p}(p^2-1)/2$, p a prime >3 and $\mathit{p}\equiv 2$ or 3 (mod 5) (iv) $2^4{3}^{3}13$ (v) $2^{2\mathit{p}}(2^{2\mathit{p}}+1)(2^{2\mathit{p}}-1)$, p an odd prime. The On-Line Encyclopedia of Integer Sequences (OEIS) has a list of many such m (A056866).

Erdös (1948) found the asymptotic behavior of $\mathit{C}(\mathit{n})=\sum _{\begin{array}{l}\mathit{m}\le \mathit{n}\\ (\mathit{m},\mathit{\phi }(\mathit{m}))=1\end{array}}1$, proving that $\mathit{C}(\mathit{n})=(1+\mathit{o}(1))\frac{\mathit{n}{\mathit{e}}^{-\mathit{\gamma }}}{\mathit{log}\mathit{log}\mathit{log}\mathit{n}}$ where $\mathit{\gamma }=0.57721\dots$ is Euler’s constant. Mays (1978) proved that A(n) and N(n) also $=(1+\mathit{o}(1))\frac{\mathit{n}{\mathit{e}}^{-\mathit{\gamma }}}{\mathit{log}\mathit{log}\mathit{log}\mathit{n}}$, so C(n), A(n) and N(n) each grow more slowly than n. Using an old result of Burnside and the Feit-Thompson Theorem that every non-abelian finite simple group has even order, Mays (1978) proved that $\mathit{S}(\mathit{n})>0.869\mathit{n}$ for $\mathit{n}>N_0$.

Using Pazderski’s criteria, we check that every group of square-free order $\mathit{n}=\prod p_i$ (distinct primes) is supersolvable. ζ is the Riemann Zeta function and $\mathit{\zeta }(2)=\sum _{\mathit{k}=1}^{\mathrm{\infty }}1/k^2={\pi }^2/6$. Since (Montgomery & Vaughan, 1981) the number of square-free integers $\le \mathit{n}$ is equal to $\frac{n}{\mathit{\zeta }(2)}+\mathit{O}(\sqrt{\mathit{n}})>\left(\frac{6}{{\pi }^2}\right)\mathit{n}>0.6079\mathit{n}$, we know that $\mathit{U}(\mathit{n})>0.6079\mathit{n}$.

Zhang & Fan (1981) reformulated Pazderski’s criteria and gave a different proof that their criteria characterize those integers n for which every group of order n is supersolvable: A group of order n is supersolvable if and only if $\mathit{n}=\prod _{\mathit{i}=1}^r{p}_i^{{\lambda }_i}$ ($p_1<p_2<\cdots <p_r$) and

1. For any $\mathit{i},\mathit{j}$, $(p_i,\prod _{\mathit{s}=1}^{{\lambda }_j}(p_j^s-1))=(p_i,p_j-1)$

2. When $p_i\le {\lambda }_j$ ($1\le \mathit{i}<\mathit{j}\le \mathit{r}$), we must have $1\le {\lambda }_i\le 2$ and $p_i^{{\lambda }_i}\mid (p_j-1)$, and moreover no p_k exists $(\mathit{i}<\mathit{k}<\mathit{j})$ such that $p_i\mid (p_k-1)$ and $p_k\mid (p_j-1)$.

Finally, Hughes (1980) stated that n is a supersolvable order if and only if three criteria are satisfied:

Suppose $\mathit{n}=\prod _{\mathit{i}=1}^s{p}_i^{a_i}$, $p_1<p_2<\cdots <p_s$ (primes). Then, n is a supersolvable order if and only if there exist $\mathit{p},\mathit{q},\mathit{r}$ (distinct) prime divisors of n, such that

1. If $p^d\mid (q^t-1)$ ($\mathit{t}\le a_q,\mathit{d}\le a_p$) then $p^d\mid (\mathit{q}-1)$.

2. If $p^3\mid \mathit{n}$ and $p^3\mid (\mathit{q}-1)$ then $a_q<\mathit{p}$.

3. If $\mathit{p}<\mathit{q}<\mathit{r}$, $\mathit{p}\mid (\mathit{q}-1)$ and $\mathit{pq}\mid (\mathit{r}-1)$ then $a_r<\mathit{p}$.

Hughes stated that his proof is “to appear”, but the proof has never appeared. We decided to count the number of supersolvable orders between 2 and 10^k when $1\le \mathit{k}\le 13$, using each author’s criteria. As expected, the authors’ counts agree and are displayed as $\mathit{U}({10}^k)$ in the Table below for $1\le \mathit{k}\le 13$. The average time it took the three counts for each k, is also displayed.

Table

k	$\mathit{U}({10}^k)$	Average Time (Rounded)
1	9	0.00064 (seconds)
2	88	0.00187 (seconds)
3	871	0.00269 (seconds)
4	8,682	0.00494 (seconds)
5	86,772	0.01354 (seconds)
6	867,683	0.08478 (seconds)
7	8,676,833	1.0221 (seconds)
8	86,768,040	17.3962 (seconds)
9	867,679,854	323.582 (seconds)
10	8,676,796,466	0.0620 (days)
11	86,767,961,313	0.8528 (days)
${}^{\ast }$12	867,679,598,773	10.061 (days)${}^{\ast }$
${}^{\ast }$13	8,676,795,952,899	133.475 (days)${}^{\ast }$

${}^{\ast }$When k = 12 (or 13), these are the times it would take one computer to run the program. The HPC is a cluster of computers, and 10 computers were run concurrently. For example, when k = 12, each computer counts in an interval of length 10”. To get a closer estimate of the HPC runtime (not including queue times), divide the time by 10.

Here is the public repository for the project:

https://github.com/guanhongl/supersolubility

The files ss.c, ss_pazderski.c, and ss_h.c correspond to the three criteria.

Below these, readers will find the directions for running the program locally.

Our table of U(n) reveals that $\mathit{U}(\mathit{n})>0.8676\mathit{n}$ without using the results of Burnside and Feit-Thompson.

In order to find S(n), we found $\mathit{NS}(\mathit{n})=\mathit{n}-\mathit{S}(\mathit{n})$, the number of integers $\mathit{m}\le \mathit{n}$ such that some group of order m is not solvable. For example, since some group of order 60 (namely Alt(5)) is not solvable, and m = 60 is the only $\mathit{m}\le {10}^2$ for which some group of order m is not solvable, we have $\mathit{NS}({10}^2)=1$. Using the criteria based on J. Thompson’s result on minimal simple groups, we know that some group of order m is not solvable if and only if m is a multiple of at least one of (i), (ii), (iii), (iv) or (v) (listed earlier). For example, some group of order $1344=2^6\cdot 3\cdot 7$ is not solvable since $1344=(24)\cdot 2^p(2^p-1)$ where p = 3. Using a (2017) Lenovo Y520-151KBM desktop computer and source code written in Mathematica (modified slightly from that at OEIS AO56866), we found for $3\le \mathit{k}\le 8$, keeping track of the time taken in seconds:

Table

k	$\mathit{NS}({10}^k)$	Time (Rounded)
3	20
4	224	0.66
5	2240	7.29
6	22416	110.35
7	224132	1,872.89
8	2241423	32,924.33

Since there are $86,400$ seconds/day, it took approximately 0.38 days to find the number of $\mathit{m}\le {10}^8$ for which some group of order m is not solvable. We stopped at 10⁸, since we estimate that it will take at least a week to find $\mathit{NS}({10}^9)$ with not much information gained. Since $\mathit{S}(\mathit{n})=\mathit{n}-\mathit{NS}(\mathit{n})$, we have the following:

Table

k	$\mathit{S}({10}^k)$	$\mathit{S}({10}^k)/{10}^k$
3	980	0.980
4	9776	0.9776
5	97760	0.9776
6	977584	0.977584
7	9775868	0.97758680
8	97758577	0.97758577

As noted earlier [Mays, Thm. 5, Mays (1978)] proved that for n large enough: $0.869\mathit{n}<\mathit{S}(\mathit{n})<0.978\mathit{n}$. We see from the above table how close to his upper bound S(n) is.

Disclosure statement

No potential conflict of interest was reported by the author(s).