If a group is presented to me (by one of the methods discussed in the preceding post, or as a black box), one of the first things I might want to know is “which group is it?” This presupposes that we have a name for the group.
Now expertise in computational group theory requires a wide-ranging knowledge of traditional group theory as well as a completely different take on it. There are very many groups; in some sense, the extreme cases are p-groups and (nearly) simple groups.
Groups of prime power order
In 2000, the classification and counting of groups of order less than 2000 was announced by Hans Ulrich Besche, Bettina Eick and Eamonn O’Brien. There are 49 910 529 484 of them, of which almost all (approximately 49.5 billion) have order 210 = 1024.
So we could give names to these groups by giving their number in the Besche–Eick–O’Brien catalogue; each group could have a 36-bit name.
Of course, unless we are much cleverer, this method cannot be extended to groups of order 211 or larger powers of 2.
We can compromise. I will stick to the prime 2 here, though the same comments apply to powers of other primes. A group of order 2n has a “power-commutator presentation”: it is generated by elements x1,…xn, with defining relations giving the squares xi2 and the commutators [xi,xj] (for i < j) in terms of the generators. These expressions have a very special form: each is a product, over k running from i+1 to n (for the squares) or max(i,j)+1 to n (for the commutators); and the kth term is either the identity or xk.
The number of expressions for the squares is thus at most (n−1)+…+1+0 = n(n-1)/2 for the squares, and (n−2)+2(n−3)+…+(n−2) = n(n−1)(n−2)/6 for the commutators, or in total (n+1)n(n−1)/6 choices.
So the number of groups of order 2n is at most, roughly, 2(1/6)n3. Moreover, the power-commutator presentation gives us an easily-decodable name for each group, the name having length (n+1)n(n−1)/6.
But there is a problem: not all these groups are different. The actual number of groups of order 2n is asymptotically 2(2/27)n3. (The lower bound was proved by Graham Higman, and the upper bound by Charles Sims.) We don’t have easily decodable names of length about (2/27)n3 for all groups of order n, and we don’t have an efficient way of testing isomorphism for the longer names.
This is mildly shocking, given that “most” groups of order 2n have “φ-class 2”, which means that they can be described in terms of two
vector spaces over GF(2) with dimensions summing to n, together with a bilinear and a quadratic form from one space to the other, the forms related by polarisation. Here is a “simple” problem in linear algebra for which we don’t have a computationally efficient solution!
Nearly simple groups
At the other end of the scale, the non-abelian finite simple groups have short names. There are a small finite number of families of “groups of Lie type”: the classical ones are parametrised by a positive integer (the rank) and a prime power (the field order), while the exceptional groups are parametrised just by a field order. The alternating groups require a single positive integer (the degree), and there are only finitely many sporadic groups.
Even if we include groups which are “nearly simple”, that is simple groups possibly extended a bit in both directions, the description is still fairly simple. This was the hypothesis behind the celebrated ATLAS of Finite Groups. The extending means that we are allowed to have a normal subgroup at the bottom which is contained in the Schur multiplier of the simple group (that is, form a central extension), and we are allowed to have a subgroup of the outer automorphism group at the top. Both the Schur multipliers and the outer automorphism groups of finite simple groups are small and well-understood.
So we might modify our requirement and say: if the group is nearly simple in this sense, give it a name; otherwise, just provide some information about it.
The ground between
Probably, if a group is not “nearly simple”, we would be satisfied with some partial information about it. One thing that might be useful is a composition series for the group, telling us which simple groups go into its construction.
This tells us almost everything in the case of a nearly simple group, and almost nothing in the case of a group of prime power order. Each of the 49.5 billion groups of order 1024 has ten composition factors isomorphic to the cyclic group of order 2.
In some algorithms, such as Sylow subgroups for black box groups, rather than use traditional mathematical methods, we find a composition series first; then produce Sylow subgroups for the composition factors (these are known groups) and piece them together.
Black box groups
Recognising nearly simple groups as permutation groups has a long history. Indeed, my work with John Cannon addressed this question. To show that a group of permutations on n points is Sn or An, for example, it suffices to show that its action is primitive (which is easy), and to find a transposition or 3-cycle in the group (not so easy, but for example if we can find two elements whose supports meet in a single point then their commutator is a 3-cycle).
Recognising black-box groups is a bit more challenging. This problem was addressed for symmetric and alternating groups by Sergey Bratus and Igor Pak in 2000, and other authors have contributed subsequently. The Bratus–Pak paper (perhaps surprisingly at first view, but it makes sense on a moment’s thought) requires Goldbach’s conjecture to prove the correctness of the algorithm (the ternary Goldbach conjecture will do, and indeed the original conjecture has been verified up to values far beyond the dreams of computational group theorists), and some stronger versions of Goldbach’s conjecture are relevant to discussion of its running time. These stronger versions, concerning the number of representations of an even number as the sum of two primes, are derived from heuristics similar to that of Hardy and Littlewood for twin primes, and pose interesting challenges to number theorists.
Sad to say, a controversy has arisen over this. Igor Pak, in a blog post (I will give you the address later, but I cannot tell you what he says since the content of his blog is copyright), has alleged academic malpractice or something. Eamonn O’Brien, perhaps the only person not personally involved but having copies of all relevant emails, has posted a document giving some context not present in Pak’s original post. If you read Pak’s version, please read O’Brien’s also. The documents in question are here and here.
Recognition algorithms for other close-to-simple groups have also been given.
From some points of view, matrix groups over finite fields are perhaps the closest concrete groups to black-box groups, and the black-box algorithms are especially relevant to the matrix group recognition project, a long-term project masterminded by Charles Leedham-Green, whose aim is to find names and/or information (including composition series) for groups generated by sets of matrices. The object of the program is to produce code which can be included in the two standard computer algebra packages, Magma and GAP.
Peter Cameron's Blog 
There are species that Adam had no opportunity to name. And not even knowing they existed, he would have had no way to ask his assisting djinn to fetch them forth for classification. It might have provided him some comfort had he known he might always reconstruct a name from the pedigree of a thing, from the algorithm of its descent. Or, if not from the pedigree, perhaps from the names he had already bestowed upon its proper parts. Were this so, he might have achieved the greatest possible recognition with least possible effort.
Pingback: What we’ve got here is failure to communicate | Igor Pak's blog