ON THE DENSITY OF VARIOUS CLASSES OF GROUPS

M. RAM MURTY AND V. KUMAR MURTY

Abstract. Let L be a subset of the set of all isomorphism classes of finite groups. We consider the number F_{L}(x) of positive integers n ≤ x such that all groups of order n lie in L. When L consists of the isomorphism classes of all finite groups of any of the following types, we obtain an asymptotic formula for F_{L}(x): cyclic groups, abelian groups, nilpotent groups, supersolvable groups, and solvable groups. In the course of the arguments, we also obtain, for almost all n, a lower bound for the number of groups of a given order n.

1. Introduction

Let G be the set of all isomorphism classes of finite groups and L a certain subset. If T (x) (resp. G(x)) denotes the number of groups H ∈ L (resp. H ∈ G) whose orders are ≤ x, we define the density of L, denoted δ(L), as

δ(L) = lim_{x→∞} T (x)/G(x),  (1.1)

provided this limit exists. Then (1.1) represents, in a natural way, the probability that a randomly selected finite group lies in L. For example, if L consists of all isomorphism classes of finite abelian groups, then we shall see in a simple way that δ(L) = 0. If L consists of isomorphism classes of groups of squarefree order, then Mays [8] showed that δ(L) = 0. The calculation of δ requires good upper and lower bounds for T (x) and G(x) and this makes computations in a given specific case difficult. It seems reasonable to conjecture that if L consists of all isomorphism classes of finite simple groups then δ(L) = 0.

If we confine our attention to the distribution of orders of groups in L, we are led to consider the number F_{L}(x) of n ≤ x such that all groups of order n lie in L. If we set g(n) to be the number of non-isomorphic groups of order n and for fixed positive integer k,

L = L_{k} = {H : card (H) = n and g(n) = k}

then F_{L}(x)/k is just the number of n ≤ x such that g(n) = k. For k = 1, Erdös [3] showed that

F_{L}(x) = (1 + o(1)) xe^{−γ}/ log_{3} x,

where γ is Euler’s constant and we write log_{1} x = log x, log_{a} x = log(log_{a−1} x). If k is any positive integer, we shall show below that for L = L_{k},

F_{L}(x) ≪ x/ log_{4} x.

Hence δ(L_{k}) = 0.

Let L be any one of the following subsets of G: the isomorphism classes of all finite cyclic groups (C), abelian groups (A), nilpotent groups (N), supersolvable groups (SS), and solvable groups (S). Then, we shall derive an asymptotic formula for F_{L}(X). In the case that L is C, the result was obtained by Erdös. If L is A or N, this result was also obtained by Mays [9], who used a general result of Scourfield. One can derive this result in a simple way without recourse to any general result. In the case L is SS or S, Mays [9] obtained upper and lower bounds for F_{L}(x). By using a lemma of Erdös on primitive sequences, we are able to give an asymptotic formula in these cases also.

Unless otherwise specified, all groups in this paper are assumed to be finite. Also, we shall refer to a group and its isomorphism class interchangeably.

2. Scarcity of Abelian Groups

If A is the set of all isomorphism classes of abelian groups then we shall show δ(A) = 0. This is easily deduced from the following.

Theorem 2.1. For each fixed ε > 0,

g(n) ≥ (1 − ε) log_{4} n,  (2.1)

with the possible exception of at most o(x) of the n ≤ x.

Remark . It is highly unlikely that (2.1) reflects the true order of g(n). It is expected that log g(n) ≪ (log n)^{3}, but this has not been proved. (See also the concluding remarks.)

Our proof of the theorem will require the following lemmas, which seem to be of some independent interest.

Lemma 2.1. Let r(n) denote the number of prime pairs (p, q) such that pq | n and q ≡ 1 (mod p). Then g(n) ≥ r(n).

Proof. For any pair (p, q) enumerated by r(n), we can form the group H(pq) ⊕ C(n/pq), where C(a) is the cyclic group of order a and H(pq) = ⟨x, y : x^{p} = y^{q} = 1, x^{−1}yx = y^{s}⟩ with s^{p} ≡ 1 (mod q), s ≠ 1, is a non-abelian group of order pq. As it is clear that these groups are non-isomorphic for distinct pairs (p, q), the lemma is proved.

Lemma 2.2. Let f(x) be any function satisfying 1 < f(x) ≤ x, f increasing and unbounded as x → ∞. Define v_{t}(n) to be the number of distinct prime factors of n that are less than t and let ε > 0. Then, with the possible exception of x/(ε^{2} log_{2} f(x)) of the n ≤ x, we have

(1 − ε) log_{2} f(x) ≤ v_{f(x)}(n) ≤ (1 + ε) log_{2} f(x).

Proof. We shall follow the method of Turán [13]. Using well-known estimates, and writing f for f(x) we have

∑_{n≤x} v_{f}(n) = ∑_{p<f} [\frac{x}{p}] = x log_{2} f(x) + O(x)

and

∑_{n≤x} v_{f}^{2}(n) = ^{∑′} [\frac{x}{pq} ] + ∑_{p<f} [\frac{x}{p}]
= x(log_{2} f(x))^{2} + O(x log_{2} f(x)),

where square brackets denote the greatest integer function, p, q denote primes and the sum ^{∑′} is over p, q < f, p ≠ q. Hence we find

∑_{n≤x} (v_{f}(n) − log_{2} f(x))^{2} ≪ x log_{2} f(x).

Thus the number of n ≤ x for which

|v_{f}(n) − log_{2} f(x)| > ε log_{2} f(x)

is ≪ x/(ε^{2} log_{2} f(x)), as desired.

Lemma 2.3. Let p < (log_{2} x)^{a} for some fixed 0 < a < 1. Then, the number of n ≤ x, n ≡ 0(p) and having no prime divisor ≡ 1 (mod p) is O(x/(log_{2} x)^{A}) for any A > 0. Here, the implied constant depends only on A.

This is essentially what Erdös proves in [3, p. 77].

We can now prove our theorem.

Proof of Theorem 2.1. We shall show that

r(n) ≥ (1 − ε) log_{4} n  (2.2)

with at most ≪ x/ log_{4} x exceptional n ≤ x. This will, by Lemma 2.1, give the desired result.

Fix 0 < a < 1, and for each x, consider the primes p ≤ (log_{2} x)^{1−a}. By Lemma 2.3, we see that for each of these primes, the number of integers n ≤ x, n ≡ 0(p) and which have no prime factor ≡ 1 (mod p) is o(x/(log_{2} x)^{2}). Hence, with the exception of o(x/(log_{2} x)^{2})(log_{2} x)^{1−a} = o(x/ log_{2} x) values of n ≤ x, ϕ(n) is divisible by each of the prime divisors p of n, p ≤ (log_{2} x)^{1−a}. Here, ϕ(n) denotes Euler’s totient function. Taking f(x) to be (log 2x)^{1−a} in Lemma 2.2, we conclude that

r(n) ≥ v_{f}(n) ≥ (1 − ε) log_{4} x

with at most O(x/ log_{4} x) exceptional n ≤ x. This proves the theorem.

Corollary 2.1. δ(A) = 0.

Proof. Let A(x) denote the number of abelian groups of orders ≤ x. By a result of Erdös and Szekeres [6], we have A(x) ≪ x, so that by an easy calculation

A(x)/G(x) ≪ 1/ log_{4} x = o(1)

as desired.

3. Some Asymptotic Formulae

We begin with the following theorems.

Theorem 3.1. As x → ∞,

F_{C}(x) ∼ F_{A}(x) ∼ F_{N}(x) ∼ xe^{−γ}/ log_{3} x.

Proof. For F_{C}(x), the result was proved by Erdös [3], since a classical result of Burnside implies that a necessary and sufficient condition for an n to be included is that (n, ϕ(n)) = 1. As C ⊆ A ⊆ N, it is enough now to prove that F_{N}(x) is asymptotically majorized by xe^{−γ} log_{3} x. Our argument closely follows that of Erdös. Fix ε > 0, and let y = (log_{2} x)^{1−ε}. We split the set S(x) of the n ≤ x under consideration into two classes S_{1}(x) and S_{2}(x) depending on the size of their least prime divisor p. Specifically, n ∈ S_{1}(x) if p < y and n ∈ S_{2}(x) if p ≥ y. An upper bound for the cardinality of S_{2}(x) is the number of n ≤ x having no prime divisor less than y. By the sieve of Eratosthenes and Merten’s theorem, this number is equal to

x ∏_{p≤y} (1 − \frac{1}{p}) + O(2^{y}) = (1 + o(1)) xe^{−γ}/(1 − ε) log_{3} x.

Now consider those n in S_{1}(x). If all groups of order n are nilpotent, and m is the squarefree core of n, it is clear that (m, ϕ(m)) = 1. Hence, an upper bound for the number of such n is the number of n ≤ x which are divisible by p and have no prime factor ≡ 1 (mod p). By Lemma 2.3, this is o(x/(log_{2} x)^{2})·(y) = o(x/ log_{3} x). Now we let ε tend to 0 to complete the proof.

Theorem 3.2. There is a constant c_{1} ≥ 6/π^{2} such that

F_{SS}(x) ∼ c_{1}x.

Our proof will depend on the following arithmetical lemmas.

Lemma 3.1. Write n = p_{1}^{α_{1}}p_{2}^{α_{2}} ⋯ p_{s}^{α_{s}} with p_{1} < p_{2} < p_{3} · · ·. All groups of order n are supersolvable iff for p, q, r distinct prime divisors of n,

(i) p^{d} | (q^{t} − 1), t ≤ α_{q}, d ≤ α_{p} implies p^{d} | (q − 1); (ii) p^{3} | (q − 1) implies α_{q} < p; (iii) p < q < r, p | (q − 1), pq | (r − 1) implies α_{r} < p.

See Hughes [7].

Remark . The analogues of this condition for abelian groups and nilpotent groups were found by Dickson and Bachman (see [1]), respectively, and for solvable groups it was discovered by Thompson [12].

The next lemma is a special case of a well-known result of Erdös [4] which gives a criterion for a sequence of integers to have a density. A sequence of integers is called primitive if no element divides any other.

Lemma 3.2. Let m_{1} < m_{2} < ⋯ be any primitive sequence of integers and let b_{1} < b_{2} < ⋯ be the sequence composed of those integers which are divisible by at least one m_{i}. If the number of m_{i} ≤ x is O(x/ log x) then the sequence of b’s has a density.

Proof of Theorem 3.2. If we show that the sequence of integers n such that all groups of order n are supersolvable, has a density c_{1}, it will follow that c_{1} ≥ 6/π^{2} as it is easily seen from Lemma 3.1 that the groups of squarefree order are supersolvable. Actually, we will show that the complementary sequence has a density. To do this, we begin by extracting a maximal primitive subsequence, say m_{1} < m_{2} < ⋯ of the complementary sequence. Clearly, the sequence b_{1} < b_{2} < ⋯ composed of integers divisible by an m_{i} is precisely the complementary sequence. For by maximality, every element of the complement is divisible by an m_{i} and Lemma 3.1 shows that any multiple of an m_{i} must be in the complement as m_{i} itself is. Let h(x) be the number of m_{i} ≤ x. If we can show h(x) = O(x log x), then Lemma 3.2 will give the desired result.

Suppose m is one of the m_{i} and q is the largest prime divisor of m. Then, all groups of order m/q are supersolvable. Indeed, if this were not the case, m/q would be in the complementary sequence. Then for some j, we would have m_{j} | m/q and so also m_{j} | m, which is a contradiction.

We claim that this implies:

either q^{2} | m or q | (p − 1)(p^{2} − 1) ⋯ (p^{a} − 1) for some p^{a} | m.  (3.1)

Suppose q^{2} |̸ m. By the above remark, m/q satisfies conditions (1), (2), (3) of Lemma 3.1, but m fails to do so. But α_{q} = 1 implies that it satisfies both (2) and (3), and the only way (1) can fail to hold is if q | (p^{s} − 1) for some s ≤ α_{p}. This proves (3.1).

Denote by j(x) the number of integers m ≤ x having property (3.1), where q is the largest prime divisor of m. Then h(x) ≤ j(x). Write j(x) = j_{1}(x)+j_{2}(x), where j_{1}(x) is the number of integers m ≤ x satisfying (3.1) and having q > (log x)^{2}.

We can estimate j_{1}(x) directly as follows:

j_{1}(x) ≪ ∑_{q>(log x)^{2}} ∑_{t≤x} \frac{x}{q(tq + 1)}
≪ x log x ∑_{q>(log x)^{2}} q^{−2} ≪ x/ log x.

To estimate j_{2}(x), we use a method of Rankin [11]. A prime in the summation indicates that the range is only over those n all of whose prime factors are ≤ y = (log x)^{2}. Then,

j_{2}(x) ≤ \begin{matrix}∑ & ′ \\ nleqx \end{matrix} 1 ≤ \begin{matrix}∑ & ′ \\ n≤x \end{matrix} (\frac{x}{n})^{1/2} ≤ x^{1/2} ∏_{p≤y}(1 − p^{−1/2})^{−1}

= x^{1/2} ∏_{p≤y} (1 + \frac{1}{p^{1/2} − 1})

≤ exp (\frac{1}{2} log x + ∑_{p≤y} \frac{1}{p^{1/2} − 1})

≪ exp (\frac{1}{2} log x + 2y^{1/2}/ log y) ≤ x^{1/2+δ}),

where δ = (log log x)^{−1}. In the penultimate step, we used the prime number theorem. Hence h(x) ≤ j(x) = j_{1}(x) + j_{2}(x) ≪ (x log x).

Our final result in this section concerns solvable groups.

Theorem 3.3. There is a constant c_{2} such that F_{S}(x) ∼ c_{2}x.

Proof. Thompson [12] has shown the deep result that every minimal simple group is isomorphic to one of the following:

(a) L_{2}(2^{p}), p any prime,

(b) L_{2}(3^{p}), p any prime,

(c) L_{2}(p), p any prime > 3, such that p^{2} + 1 ≡ 0 (mod 5),

(d) Sz(2^{p}), p any odd prime,

(e) L_{3}(3) (see [12] for notation). Let Z be the ascending sequence of orders of the above types of groups. Then, all groups of order m are solvable if and only if no s ∈ Z divides m. Necessity is trivial to see and conversely, if G is a group of order m where no s ∈ Z divides m, then G is not simple, say H ⊲ G. By induction, H and G/H are solvable so it follows that G is solvable.

The number of s ≤ x, s ∈ Z is obviously O(x log x) as each order corresponds to a prime and each prime gives rise to at most four orders. But now, the method of the previous theorem and Lemma 3.2 complete the proof.

The value of c_{2} above is, in fact, quite close to 1, though it is clear that it must be less than 1. The above reasoning shows that

c_{2} ≥ ∏_{s∈Z′} (1 − \frac{1}{s}) ,

where Z′ is a maximal primitive sequence of Z.

4. Conclusion

If L consists of all isomorphism classes of finite simple groups, we have already conjectured that δ(L) = 0. Erdös [5] has shown that the number of n ≤ x such that there is a non-abelian simple group of order n is o(x log x). (See also Dornhoff [2].) Hence, if we let s(n) be the number of simple groups of order n, and conjecture s(n) = O(log n), then it follows that δ(L) = 0. But Neuman [10] has pointed out that even a much weaker form of such a conjecture already implies that log g(n) = O(log n)^{3}. Of course, the recent (presumed) classification of finite simple groups settles all these conjectures. In fact, it implies that s(n) = O(1).

Acknowledgments

The results of this paper were presented at the 6th British Combinatorics Conference at Royal Holloway College in June 1977. We would like to thank Professors J.D. Dixon, F. Fiala and L.D. Nel for their support, which made it possible to attend that conference. We also thank Professor Dixon for his comments on a preliminary version of this paper.

References

[1] G. Bachman, On finite nilpotent groups, Canad. J. Math. 12 (1960), 68–72. (See also L.E. Dickson, Definitions of a group and a field by independent postulates, Trans. Amer. Math. Soc. 6 (1905), 198–204.)

[2] L. Dornhoff, Simple groups are scarce, Proc. Amer. Math. Soc. 19 (1968), 692–696.

[3] P. Erdös, Some asymptotic formulas in number theory, J. Indian Math. Soc. 12 (1948), 75–78.

[4] P. Erdös, On the density of some sequences of integers, Bull. Amer. Math. Soc. 54 (1948), 685–692.

[5] P. Erdös, The scarcity of simple groups, to appear.

[6] P. Erdös, and G. Szekeres, Über die Anzahl der Abelschen Gruppen gegebener Ordnung und über ein verwandte zahlentheoretisches Problem, Acta Litt. Sci. Reg. Univ. Hungar. Fr. Jos. Sect. Sci. Math. 7 (1934), 94–103.

[7] A. Hughes, On supersolvable orders, to appear.

[8] M.E. Mays, Groups of squarefree order are scarce, Pacific J. Math. 91 (1980), 373–375.

[9] M.E. Mays, Counting abelian, nilpotent, solvable, and supersolvable groups, Arch. Math. 31 (1978), 536–538.

[10] P. Neuman, An enumeration theorem for finite groups, Quart. J. Math. Oxford 20 (1969), 395–401.

[11] R.A. Rankin, The difference between consecutive prime numbers, J. London Math. Soc. 13 (1938), 242–247.

[12] J. Thompson, Non-solvable finite groups all of whose local subgroups are solvable, Bull. Amer. Math. Soc. 74 (1968), 383–437.

[13] P. Turán, On a theorem of Hardy-Ramanujan, J. London Math. Soc. 9 (1934), 284–286.

ON THE DENSITY OF VARIOUS CLASSES OF GROUPS 7

Department of Mathematics, M.I.T., Cambridge, Massachusetts, 02138 Department of Mathematics, Harvard University, Cambridge, Massachusetts, 02138