Is there any efficient algorithm for finding subgroups of a given finite group?

Question

I am implementing an algorithm which finds every subgroup of given group.

Here's my algorithm.

Let $G$ be a group of order $n$ with elements $g_1,\cdots,g_n$.

Then I consider each $\langle g_i\rangle $ which are all cyclic subgroups of $G$.

Of course, if $\langle g_i\rangle =\langle g_j\rangle $, we append only $\langle g_i\rangle $ into our result set.

We call all distinct subgroups of the form $\langle g_i\rangle $ to be the first-generation. (Note that the number of the first-generation subgroups is at most $n$.)

To get $(i+1)$-th generation from $i$-th generation inductively, we construct the subgroup $S$ from each two elements of $i$-th generation $S_1, S_2$ to be

$$S=\langle S_1,S_2\rangle .$$

Obviously, if generated subgroup is already in previous generations, we do not call it $(i+1)$-th generation, hence every subgroups of $G$ has the unique generation number.

We do this construction until the number of the typical generation subgroups to be $0$, since we get all subgroups of $G$.

This works perfectly to any groups, but unfortunately, it is not fast although I implemented additional steps to avoid repeated computation.

So I searched some other algorithms but they are all vague to understand.

One of the algorithm is called the cyclic extension algorithm, but I can not get it easily unless I have studied some backgrounds for this method.

If you have enough knowledge about the cyclic extension algorithm or some other algorithms, please give me an easy explanation. I am in undergrad. course of math dept. Thanks.

Answer 1

I don't know the details of any of the standard algorithms currently in use. Regardless, here are some things you can do to speed up your initial implementation (at least the on-average running time).

1) Every subgroup is a union of cyclic subgroups. So, you enumerate the cyclic subgroups as you have done. Then, start forming unions of those and check whether or not you have a subgroup (this of course is the time-consuming part).

2) Discard any union of cyclic subgroups whose size does not divide the size of the group (because of Lagrange).

3) Using Sylow you can get some information on the number of subgroups of certain prime power order, and that means you can stop the search for a given size when you found all possible subgroups of that size that can exist.

4) Of course if the group is abelian than there are less potential products to check and you can use other structure theorems to speed things up.