Take the 2-minute tour ×

I know that for some small groups, one could just brute force all combinations of elements to find its subgroups, but is there some sort of an algorithm, at least for finite groups?

share|improve this question
There cannot exist a group with 3 elements?!?!? That is not true at all. For every positive integer $n$ there is at least one group of order $n$. –  KCd Dec 9 '12 at 5:57
There is a group with the order of any $n \in \mathbb{N}$: Take $\mathbb{Z}/n\mathbb{Z}$. –  Jair Taylor Dec 9 '12 at 5:58
there exists a group of 3 elements, $\langle\mathbb{Z}_3,+\rangle$, and by the fundamental theorem of arithmetic there exists a group of $n$ elements for all $n\in{\mathbb{N}}$, are you sure you didn't make a mistake on your question? –  Camilo Arosemena Dec 9 '12 at 5:58
The most direct method I know of to find subgroups of finite groups is related to Sylow theory. –  Clayton Dec 9 '12 at 6:03
okay, disregard that comment about group of order 3, its clearly false. I was thinking about something else. But what about the question about finding subgroups of a given group (upto isomorphism, of course)? –  chubbycantorset Dec 9 '12 at 6:03
add comment

2 Answers

up vote 6 down vote accepted

There is a method called the cyclic extension method, which can find the subgroups of a finite soluble group. (It is possible to enhance this algorithm with knowledge of perfect groups to deal with groups that are insoluble.) The basic idea is to build up the subgroups in layers, starting with the subgroups of prime order. To get things rolling, start with the subgroups $\langle g\rangle$ of prime order. Now you've got layer $1$, and you can proceed inductively. Once you have a subgroup $H$ in, say, the $i$th layer, a subgroup in the $(i+1)$st layer can be constructed as $\langle H, u\rangle$, where $u$ is an element of the normaliser of $H$ such that $u^p$ belongs to $H$, for some prime $p$. Putting it all together and making it efficient is rather complicated, but there is a description of it in Chapter 6 of the book "Fundamental Algorithms for Permutation Groups", by Gregory Butler (LNCS #559). Another, more sophisticated method is described in Section 10.4 of "Handbook of Computational Group Theory", by Holt, Eick and O'Brien (Chapman & Hall/CRC, 2005).

share|improve this answer
add comment

This is just to add a couple of comments to James' answer, as applied to finite groups. As he mentioned, to extend the cyclic extension method to non-solvable groups, you need a knowledge of the finite perfect groups, and these are only classified up to some specific order.

In fact all of the current practical methods use by Computer Algebra Systems rely on some kind of database lookup, so they are not complete algorithms. There are effective methods (based on results proved in the 1980s by Aschbacher, Scott, Kovacs and probably others) for reducing the problem to the subgroups of almost simple groups (which are groups $G$ with $S \le G \le {\rm Aut}(S)$ with $S$ nonabelian simple).

For the smaller almost simple groups, it is helpful simply to store (conjugacy class representatives) of their subgroups. This becomes impractical for larger groups, but recursively it is sufficient to store their maximal subgroups, and there is a vast amount of literature about the maximal subgroups of almost simple groups, much of which can be used algorithmically. For example the geometric maximal subgroups of the classical groups (i.e. things like stabilizers of subspaces, systems of imprimitivity) can be constructed generically. There are unfortunately other types of maximal subgroups that have to be classified dimension-by-dimension, but we now have a just about complete description of the maximal subgroups of the classical groups up to dimension 12.

The situation for the alternating groups is similar. I think their maximal subgroups are known and listed up to degree about 4095. Apart from a small number of remaining uncertainties about the Monster, the maximal subgroups of the sporadic groups are completely known and, except for the very large instances, effectively constructible. There is much less known in general about the larger exceptional groups of Lie type.

share|improve this answer
add comment

Your Answer


