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

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.

• Could you please also tell what are you using to implement your algorithm? – Alexander Konovalov Aug 13 '14 at 15:18
• I use mathematica – Analysis Aug 15 '14 at 11:04
• Of course, it's easy to calculate subgroups with GAP, see GAP F.A.Q. here, and it may depend on the purpose of your implementation whether to use GAP or continue in Mathematica. It is also possible to interface GAP from Mathematica via SCSCP protocol. – Alexander Konovalov Aug 17 '14 at 18:42