COUNTING FINITE GROUPS

M. Ram Murty^{1} To Professor K.R. Parthasarathy

1. Introduction

Let G(n) denote the number of non-isomorphic groups of order n. We can ask whether there is a formula for G(n) in terms of the arithmetic structure of n. In the absence of such a formula, we can ask if there are upper and lower bounds for G(n). We can study the growth of G(n). Interestingly enough, these questions have partial (and, in some cases, complete) answers. Their investigations take us into the domain of both finite group theory and analytic number theory. It is the purpose of this article to survey these investigations and to adumbrate problems and topics for further research.

At the outset, we have the trivial estimate

(1)  G(n) ≤ n^{n^{2}}

simply by counting all of the possible multiplication tables. This can be substantially improved. With the classification of the finite simple groups, one knows from the work of Neumann [N] that if ω(n) denotes the total number of prime factors of n, counted with multiplicity, then

(2)  G(n) ≤ n^{ω(n)^{2}}

This is a substantial improvement because by a famous result of Hardy and Ramanujan [HR], ω(n) has normal order log log n. Even otherwise, ω(n) has a much smaller order than n. It is trivial to see that ω(n) ≤ (log n)/ log 2, and Ramanujan [R] has shown that

(3)  ω(n) = O(\frac{log n}{log log n}).

This gives the estimate

(4)  log G(n) = O(\frac{log^{3}n}{(log log n)^{2}} ).

Recently, McIver and Neumann [MN] obtained the estimate:

G(n) ≤ n^{ω(n)^{2}/2}

This result has been improved by Pyber [Py] in the following way. Let p_{1}, ..., p_{k} be distinct primes and let P = {P_{1}, ..., P_{k}} be a set of groups such that P_{i} is a p_{i}-group of order p_{i}^{g_{i}} (say). We say that G is a group with Sylow set P if

|G| = ∏_{i=1}^{k} p_{i}^{g_{i}}

1 Research partially supported by NSERC, FCAR and CICMA. and the Sylow p_{i}-subgroups of G are isomorphic to P_{i}. Pyber [Py] has proved that the number of groups of order

n = ∏_{i=1}^{k} p_{i}^{g_{i}}

with a given Sylow set P is at most

n^{75μ+16}

where

μ = max g_{i}.

As a corollary, he obtains

G(n) ≤ n^{( \frac{2}{27} +\underline{o}(1))μ^{2}}

as

μ → ∞.

However, these estimates do not reflect the truth because usually G(n) is much smaller. For example, when μ = 1, we shall see below that G(n) ≤ n. If we confine our attention to various classes of groups, like p-groups, or if we constrain the arithmetic nature of n, like squarefree numbers or numbers with bounded prime power exponents, then these estimates are sharp.

2. Counting abelian groups.

Since every finite abelian group is isomorphic to a direct product of cyclic groups of prime power order, it is easy to derive an explicit formula for G_{A}(n), denoting the number of abelian groups of order n. If p(α) denotes the number of partitions of α, then

(5)  G_{A}(n) = p(α_{1})p(α_{2}) ... p(α_{r})

where

(6)  n = p_{1}^{α_{1}} ... p_{r}^{α_{r}}

is the unique factorization of n into distinct prime powers. We see that G_{A}(n) is a multiplicative function of n. As such, the Dirichlet series attached to G_{A}(n) has a beautiful expression in terms of the classical Riemann ζ-function:

(7)  ∑_{n=1}^{∞} \frac{G_{A}(n)}{n^{s}} = ∏_{k=1}^{∞} ζ(ks)

Therefore, the methods of analytic number theory can be utilised to study

∑_{n≤x} G_{A}(n)

In fact, noting that the right hand side of (7) is analytic for Re(s) ≥ 1 except for a simple pole at s = 1, we get by the Wiener-Ikehara Tauberian theorem (see for example [M, p. 37 ]) that

(8)  ∑_{n≤x}G_{A}(n) ∼ C_{1}x

where

C_{1} = ∏_{k=2}^{∞} ζ(k).

Kendall and Rankin [KR] proved

(9)  ∑_{n≤x} G_{A}(n) = C_{1}x + C_{2}x^{1/2} + O(x^{1/3}log^{2}x)

with

C_{2} = ∏_{k=3}^{∞} ζ(k/2).

One can improve these results further by invoking subtler properties of the Riemann ζ-function and we will not go into the details here. We will refer the reader to the paper by Balasubramanian and Ramachandra [BR] where the oscillation of the error term is investigated.

3. Counting p-groups. If p is prime, there are reasonable estimates for G(p^{n}) due to Higman and Sims. For instance, Sims [S] proves that

log G(p^{n}) = n^{3} (\frac{2}{27} + O(n^{−1/3}))

as n → ∞ and with p fixed.

Let G_{N}(n) denote the number of nilpotent groups of order n (up to isomorphism). Since every nilpotent group is isomorphic to a direct product of its Sylow subgroups, we find that

G_{N}(n) = ∏_{p^{α}∥n} G(p^{α})

where the notation p^{α} ∥ n means that p^{α} | n and p^{α+1}|/n. This multiplicative property however is unwieldy to give any asymptotic information on the sum

∑_{n≤x} G_{N}(n).

At present, we have no such asymptotic formula. Neither do we have a proof of the plausible conjecture:

lim_{x→∞} \frac{_{∑n≤x}G_{N}(n)}{_{∑n≤x}G(n)} = 0 ,

which is the assertion that the set of nilpotent groups has ‘density’ zero in the set of all finite groups.

4. Groups of squarefree order.

When n is squarefree, one can give a remarkable explicit formula for G(n). Apparently, this formula was originally discovered by O. Hölder [H] in 1895. It was rediscovered by the authors in [MM] almost a century later.

Let v(p, n) denote the number of prime divisors q of n which are ≡ 1 (mod p). Then, for n squarefree,

(10)  G(n) = ∑_{d|n} ∏_{p|d} \frac{p^{v(p, n/d)} − 1}{p − 1}.

The authors in [MM] derive a more general formula. Define v(p^{j}, m) by

p^{v(p^{j},m)} = ∏_{q|m}(p^{j}, q − 1)

where p and q denote prime numbers. If m is squarefree, this coincides with the definition of v(p, m) above.

Let us call a C-group a finite group all of whose Sylow subgroups are cyclic. Thus any group of squarefree order is a C-group. Let C(n) denote the number of non-isomorphic C-groups of order n. Then the formula

(11)  C(n) = ∑_{{d|n \atop (d,n/d)=1}} ∏_{p^{α}∥d}(∑_{j=1}^{α} \frac{p^{v(p^{j},n/d)} − p^{v(p^{j−1},n/d)}}{p^{j−1}(p − 1)} )

is derived in [MM]. Letting g(n) be defined by

(12)  g(n) = ∏_{p|n}(n, p − 1),

one can show that

(13)  C(n) ≤ g(n).

In particular, if n is squarefree, we deduce

(14)  G(n) ≤ ϕ(n)

where ϕ denotes Euler’s ϕ-function.

This is a substantial improvement over the trivial bound (1) and the general non-trivial bound (2). By means of these equalities and inequalities, one can derive the asymptotic behaviour of the sums

∑_{n≤x} log C(n)

and

∑_{n≤x} μ^{2}(n) log G(n).

More precisely, let

∧(n) = \{ \begin{matrix}log p & if n = p^{a} \\ 0 & otherwise \end{matrix}

be the familiar von Mangoldt function of number theory. Then the asymptotic formulas

(15)  ∑_{n≤x} log C(n) = (∑_{n=1}^{∞} \frac{∧(n)}{nϕ(n)} + \underline{o}(1))x log log x

and

(16)  ∑_{n≤x} μ^{2}(n) log G(n) = (\frac{6}{π^{2}} ∑_{p} \frac{log p}{p^{2} − 1} + \underline{o}(1))x log log x

as x → ∞ are proved in [MM].

In [MM], the authors asked if the upper bound (14) is sharp. If not, we must answer the question: if n ranges over squarefree numbers, is it true that

(17)  G(n) = \underline{o}(ϕ(n))?

More generally, is it true that

(18)  C(n) = \underline{o}(ϕ(n))

as n tends to infinity? This conjecture was proved by R. Murty and S. Srinivasan [MS] in 1987. They established that for some constant A > 0,

(19)  C(n) = O(\frac{ϕ(n)}{(log n)^{A log log log n}} ).

Moreover, this is the true order (apart from the constant A) of C(n). The authors in [MS] prove that there is a constant B > 0 so that

(20)  G(n) > \frac{ϕ(n)}{(log n)^{B log log log n}}

for infinitely many squarefree numbers n.

In this context, it is to be observed that from the explicit formulae (10) and (11), the asymptotic behavior of

∑_{n≤x} C(n)

and

∑_{n≤x} μ^{2}(n)G(n)

seems difficult to determine. The result (19) allows us to deduce

(21)  ∑_{n≤x} C(n) = \underline{o}(x^{2})

as x → ∞. Pomerance [P] has shown that the asymptotic behaviour of the sum in (21) is intimately connected with the Halberstam-Elliott conjecture about the distribution of prime numbers. If π(x, q, a ) denotes the number of primes p ≤ x such that p ≡ a(mod q), then the Halberstam-Elliott conjecture predicts that for any ϵ > 0,

(22)  ∑_{q<x^{1−ϵ}}|π(x, q, a ) − \frac{li x}{ϕ(q)}| ≪ \frac{x}{log^{A}x}

for any A > 0. Let us recall the definition of li x:

li x = ∫_{2}^{x} \frac{dt}{log t}.

The Halberstam-Elliott conjecture is to be viewed as an extension of the celebrated theorem of Bombieri-Vinogradov which asserts that an estimate of the form (21) holds if we sum over q < x^{1/2−ϵ}.

Thus, assuming (22), Pomerance [P] shows that

(22)  ∑_{n≤x} C(n) > x^{2−ϵ}.

Utilizing a key theorem of Balog-Fouvry-Rousselet, Pomerance shows unconditionally that

(23)  ∑_{n≤x} μ^{2}(n)G(n) ≥ x^{1.68}.

He conjectures that

(24)  ∑_{n≤x} μ^{2}(n)G(n) = x^{2} exp(−(1 + \underline{o}(1))\frac{(log x)(log log log x)}{log log x}).

The upper bound implied by (24) has been established in [P].

5. Value distribution of G(n).

Let F_{k}(x) denote the number of n ≤ x such that G(n) = k. For k = 1, this counts the number of n ≤ x such that all groups of order n are cyclic. By group theory, one can show that any group of order n is cyclic if and only if (n, ϕ(n)) = 1.

Using the sieve of Eratosthenes and Brun’s sieve, Erdös [E] showed that the number of such n ≤ x satisfies as x → ∞

(25)  F_{1}(x) ∼ \frac{xe^{−γ}}{log log log x},

where γ is Euler’s constant. The authors in [MM2] proved that

(26)  F_{2}(x) = O(\frac{x log log log log x}{(log log log x)^{2}})

and conjectured that

(27)  F_{2}(x) ∼ \frac{xe^{−γ}}{(log_{3}x)^{2}}

where log_{k}x = log(log_{k−1} x) and log_{1}x = log x.

This conjecture was subsequently proved by Kumar Murty, Ram Murty and P. Erdös in [EMM]. They also observed a striking disparity in the asymptotic behaviour of F_{k}(x) when k is a power of 2 and when k is not. If k = 2^{a}, they proved

(28)  F_{k}(x) = \frac{e^{−γ}(1 + \underline{o}(1))x}{a!(log log log x)^{a+1}}

and if k ≠ 2^{a}, then

(29)  F_{k}(x) ≪ \frac{x}{(log log x)^{1−ϵ}} .

They suggested that with some care (29) can be improved to

F_{k}(x) = \underline{o}(\frac{x}{log log x}).

Thus, G(n) prefers to take powers of 2 more often than not.

In the same paper, they remark that for n squarefree,

\frac{log G(n)}{log log n}

has a continuous distribution function.

6. Distribution of integers attached to various classes of groups.

Let D be a class of finite groups like

C : cyclic groups A : abelian groups N : nilpotent groups SS : supersolvable groups S : solvable groups

Perhaps it will be convenient for the reader if we briefly recall the definitions of these concepts. A finite group G is said to be nilpotent if the upper central series terminates at G. That is, we define inductively (using the correspondence theorem):

Z_{0}(G) = 1, Z_{i}(G)/Z_{i−1}(G) = Z(G/Z_{i−1}(G)) i ≥ 1

where Z(G) denotes the center of G and say that G is nilpotent if for some i, Z_{i}(G) = G. A finite group is called supersolvable if there is a chain of subgroups

1 = G_{0} ⊆ G_{1} ⊆ G_{2} ⊆ ⋯ ⊆ G_{m} = G

such that each G_{i} is normal in G and G_{i+1}/G_{i} is cyclic of prime order. A finite group is called solvable if in the above, each G_{i} is required to be normal in G_{i+1}. Thus, supersolvability is a stronger condition than solvability.

Let H_{D}(x) denote the number of n ≤ x such that any group of order n belongs to D. For example, by the result of Erdös [E] cited in the previous section,

H_{C}(x) = \frac{e^{−γ}(1 + \underline{o}(1))x}{log_{3}x}

as x → ∞. In [MM3], the authors consider H_{A}(x), H_{N} (x), H_{SS}(x), H_{S}(x) and prove that

(30)  H_{N} (x) = \frac{e^{−γ}(1 + \underline{o}(1))x}{log_{3}x}

as x → ∞. Thus H_{C}(x), H_{A}(x) and H_{N} (x) have the same asymptotic behaviour as x → ∞.

In the case of solvable and supersolvable groups, they establish the existence of certain positive constants C_{1} and C_{2} so that

(31)  H_{SS}(X) ∼ C_{1}x

and

(32)  H_{S}(x) ∼ C_{2}x

as x → ∞.

7. Concluding remarks.

Can one derive the asymptotic behaviour of

∑_{n≤x} G_{s}(n)

where G_{s}(n) denotes the number of solvable groups of order n? Is it true that

lim_{x→∞} \frac{∑_{n≤x}G_{s}(n)}{∑_{n≤x}G(n)} = 0,

implying that the set of finite solvable groups has ’density’ zero?

These questions often involve group theory to reduce the problem to one amenable by sieve theory. Perhaps the methods indicated in this paper as well as those listed in the references will be useful in answering them. In any event, these investigations reveal the exciting interplay between finite group theory and analytic number theory.

References

[BR] R. Balasubramanian and K. Ramachandra, Effective and non-effective results on certain arithmetical functions, Journal of Number Theory, 12 (1980) no. 1, p. 10 - 19.

[E] P. Erdös, Some asymptotic formulae in number theory, J. Indian Math.Soc., 12(1948) p.75-78.

[EMM] P. Erdös, M. Ram Murty and V. Kumar Murty, On the enumeration of finite groups, Journal of Number Theory, Vol. 25, No. 3, (1987), p.360-378.

[H] O. Hölder, Die Gruppen mit quadratfreier Ordnungszahl, Nachr. Königl. Ges. Wiss. Gottingen Math.-Phys. K1 (1895) p. 211 - 229.

[HR] G.H. Hardy and S. Ramanujan, The normal order number of prime factors of a number n, Quart. J. Math., 48 (1917) p. 76 - 92.

[KR] D.G. Kendall and R.A. Rankin, On the number of abelian groups of a given order, Quart. J. Math., Oxford Series, 18 (1947) p. 197-208.

[M] M. Ram Murty, Topics in Number Theory, MRI Lecture Notes 1, Mehta Research Institute, Allahabad, 1993.

[MM] M. Ram Murty and V. Kumar Murty, On groups of squarefree order, Math. Annalen, 267 (1984) p. 299-309.

[MM2] M. Ram Murty and V. Kumar Murty, On the number groups of a given order, Journal of Number Theory, Vol. 18., No. 1, (1984) p.178-191.

[MM3] M. Ram Murty and V. Kumar Murty, On the density of various classes of groups,Journal of Number Theory, Vo. 17, No. 1, (1983) p.29-36.

[MN] A. McIver and P. Neumann, Enumerating finite groups, Quart. J. Math. Oxford, 38 (1987) p. 473-488.

[MS] M. Ram Murty and S. Srinivasan, On the number of groups of squarefree order, Canad. Math. Bulletin 30 (1987) p.412-420.

[N] P. Neumann, An enumeration theorem for finite groups, Quart. J. Math. Oxford, (2) 20 (1969) p. 395-401.

[P] C. Pomerance, On the average number of groups of squarefree order, Proc. Amer. Math. Soc., 99 (1987) no. 2, p. 223 - 231.

[Py] L. Pyber, Enumerating finite groups of given order, Annals of Mathematics, 137 (1993) p.203-220.

[R] S. Ramanujan, Collected Papers, Chelsea, New York, 1962.

[S] C. Sims, Enumerating p-groups, Proc. London Math. Soc. (3) 15 (1965), p. 151 - 166.

Address of Author: M. Ram Murty Department of Mathematics McGill University Montreal (Que) H3A 2K6 CANADA