jheimann@bbncc5.UUCP (John Heimann) (11/14/85)
*** I'm afraid I've forgotten most of my group theory. Is there a general way to determine the number of unique (up to isomorphism) groups of order N there are for arbitrary N, other than to count them? John
hen@bu-cs.UUCP (Bill Henneman) (11/14/85)
I spent some time in the early 70's writing a program which helped enumerate the solvable groups of order N. The only practical group-theoretic tricks I could make use of were: Factoring N and using the Sylow theorems can give an upper bound on the possible number of groups of order N: when you have found this many, you're done. For example, N=15 has only 1 group, no search necessary. If you're allowing non-abelian simple groups, I don't know how to get the upper bound, but it can probably be derived. The Sylow theorems also tell you something about the structure of the subgroup lattice, and something about the normal subgroup lattice: you can build all the groups N= 21 as extensions of groups of order 7 (since 7k+1 divides 21 only when k=0). The Todd-Coxeter algorithm can be used to generate candidate extensions of A by B, but you still have to do an isomorphism check on the candidates. Keeping the spectrum (a list of indices of the elements of the group) can cut the search space for possible isomorphic groups. For the special case of enumerating groups of prime-power order, this gives a great saving. That's all I know. Hope it helps.
leimkuhl@uiucdcsp.CS.UIUC.EDU (11/16/85)
This is a very hard question for most n. It is easy to show, however, that the number of nonisomorphic groups of order n is at most n^(n^2).
ashby@uiucdcsp.CS.UIUC.EDU (11/17/85)
Hire a grad student to count them.
amo@alice.UucP (n) (11/20/85)
In general, the problem of determining the number of non-isomorphic groups
of a given order is very hard, and it seems hardest when the order is
a prime power. (The latest result on groups of order 2**k is due to
E. Rodemich, but I don't have the reference at hand.) On the other hand,
when the order is square-free, there is a remarkable formula for this
number, due to O. Hoelder (Nachr. Koenigl. Ges. Wiss. Goettingen Math.-Phys.
Klasse 1 (1895), pp. 211-229). Define
f( n, m ) = product( gcd( n, q-1 ), q runs over prime divisors of m ).
Then, for n square-free, the number of non-isomorphic groups of order n is
sum( g( n, d ), sum over d dividing n ),
where
g( n, d ) = product( ( f(p,n/d) - 1 ) / ( p - 1 ), product over primes
p dividing d ).
References: <1208@bbncc5.UUCP>bhuber@sjuvax.UUCP (B. Huber) (11/25/85)
> > > > This is a very hard question for most n. It is easy to show, however, that > the number of nonisomorphic groups of order n is at most n^(n^2). The method amounts to counting the number of distinct ways of filling in the entries of a multiplication table for the group; it is an n X n table, with n possibilities for each entry. One can vastly improve upon this estimate with the following elementary observations: 1. Because a group always has an identity element, only an (n-1) X (n-1) subtable needs to be determined; 2. Because every element in a group has an inverse, every row and every column of the table has no repeated entries. A crude way of utilizing these results, then, is to overcount the number of multiplication tables like this: There are (n-1)! ways of filling in the first row of the subtable; there are (n-1)! ways at most of filling each of the next rows; but: the last row is completely determined by those preceding it. This gives at most ((n-1)!) ** (n-2) different multiplication tables. Now, if we permute the rows or permute the columns, we get a different table, for the same group. Thus we can divide our count by (n-1)! at least (but not by the square of (n-1)!, because certain combinations of row and column permutations will fix the entries in the table). That nets ((n-1!)) ** (n-3) different, nonisomorphic tables of order n. This is much smaller than n ** (n**2), but still is (probably) much larger than the actual number, since we haven't considered the consequences of the associative property.