The algorithms introduced by Besche–Eick (1999) were used to construct (or count) the groups of order up to 2000 in Besche–Eick–O'Brien (2002), yet I find the algorithms somewhat inaccessible.

How should I start with this topic? What references are necessary for me to understand those algorithms?

Note that Bettina Eick's papers are available from her homepage including software implementations of many of these results.

  • 2
    $\begingroup$ References? What do you mean by "construct finite groups"? It sounds to me like the work you're referring to is specifically about trying to construct all finite groups of a given order; the quantifier here is quite important. $\endgroup$ Jun 17, 2013 at 0:31
  • 2
    $\begingroup$ exactly all finite groups $\endgroup$
    – user82770
    Jun 17, 2013 at 0:36
  • 4
    $\begingroup$ Dear user, Note that questions can be closed by any 5 of the many users who have enough rep (3000 ?) to vote to close; it doesn't mean so much. In this particular case, your question is imperfectly worded (see Qiaochu Yuan's comment), and I suspect some people misunderstood what you were asking. I would rewrite your question slightly (e.g. add links which explain what BESCHE and EICK are), and say slightly more about what you mean by "construct finite groups". Then put a post on meta asking for your question to be reopened. I'm confident that it will be. Regards, $\endgroup$
    – Matt E
    Jun 17, 2013 at 3:17
  • 2
    $\begingroup$ @user82770: if you edit this question, then I have written an answer. The short version is to read Holt's Handbook of Computational Group Theory. A fair amount of the book is a pre-requisite. $\endgroup$ Jun 17, 2013 at 17:33
  • 3
    $\begingroup$ @user82770: I gave some example edits. You should probably also include what parts you understand, and what parts you don't. For instance: do you know the use of second cohomology to compute extensions of a group by an abelian normal subgroup? Do you understand the representation of solvable groups by polycyclic presentations? $\endgroup$ Jun 17, 2013 at 17:46

1 Answer 1


I recommend the Handbook of Computation Group Theory, especially chapter 2 (omitting 2.4.4 and 2.5) and chapter 8.1 and 8.7.


Constructing groups of order $n$ is inductive: we assume that one has constructed all groups whose order properly divides $n$ and have them sorted nicely.

To construct the group $G$ we try a few things:

  • If $G$ is solvable and $G/\Phi(G)$ is already constructed, use the Frattini extension method to construct $G$
  • If $G$ is solvable and $\Phi(G) = 1$, then Gaschütz showed $G = M \ltimes \operatorname{Fit(G)}$ and $\operatorname{Fit}(G)$ is a (direct product of) elementary abelian group(s) on which $G$ acts semi-simply, so $M$ is on the list kindly computed for us by M.W. Short.

Hence if $G$ is solvable, then either we use cohomology to find $G$ from $G/\Phi(G)$, or we use ordinary character theory of $M$ (already constructed) to find $G$ when $\Phi(G)=1$.

If $G$ is not solvable, then the paper mostly cheats because the possibilities for not-solvable groups of this order are quite limited.

  • If $G$ is not solvable, but $G' < G$, then $G$ has a maximal normal subgroup $M$ of index a prime $p$. We've already constructed $M$, so we use the theory of cyclic extensions (the upward extension method) to find $G$ from $M$ and $C_p$
  • If $G$ is not solvable, and $G' = G$, then $G$ is on the list of perfect groups which Derek Holt and Wilhelm Plesken kindly computed for us.


Extension theory is only used in the first bullet point of each case. The second bullet point uses table lookup, because someone else has already done the work here (and written a book about their techniques).

The two types of extensions are completely different, and best learned separately.

The first type is (non-split) extension by a minimal normal abelian subgroup. Since the quotient group is polycyclic (finite solvable in fact), we use the techniques of 8.7.2 (tails) to turn this into a linear algebra nullspace calculation. If you understand collection and/or polycyclic generating sequences, this stuff is pretty clear. It boils down to “multiplication is associative, so when I define what g*h equals, I need to make sure it is still associative.” The marvelous thing is that in this case the rules for associativity are linear. In particular, you don't particularly need to know what second cohomology “is” if you understand collection and tails.

The second type is (upwards) cyclic extension. This is in principle easy, but is a little bit of a hassle since it requires fairly detailed calculations in automorphism groups.


There are two main times one has difficulties: construction and isomorphism rejection.

Computation time during construction is usually not a problem, but things get bad when $H^2(G/M,M)$ is large as we need to find orbits on a large vector space. For example if $G/M$ is very nearly (or is) a $p$-group, then the cohomology quickly gets out of control. For this reason, $p$-groups are handled using O'Brien's $p$-group generation algorithm, and $p^nq$ groups are handled using the “split extension” method.

Isomorphism rejection is very hard if the same group is constructed many, many times. During construction, groups with the same recipe that are isomorphic are automatically rejected. However, different recipes can give the same group. It is important to minimize this, but in the range Besche–Eick was working in, the Frattini subgroup was enough: all recipes had to specify $G/\Phi(G)$, but one could specify $\Phi(G)$ in many (many) different ways. Since ingredients for $\Phi(G)$ are reasonably rare for the allowed $G/\Phi(G)$, this worked out. For $G/\Phi(G)$ a $p$-group, things go very badly, so that is why the other algorithms had to be used.

  • $\begingroup$ Thanks ,this is more than I expected $\endgroup$
    – user82770
    Jun 20, 2013 at 16:21
  • 2
    $\begingroup$ I should mention Max Horn and Bettina Eick have revisited this and have addressed my worries by generalizing the p-group generation algorithm to solvable groups. They have used these methods to recheck the groups of order less than 2000, and find the 15 million groups of order 2304. arxiv.org/abs/1306.4239 $\endgroup$ Jun 21, 2013 at 18:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .