Algorithm for lattice of subgroups

Question

In spite of my repeated efforts I have not been able to find the algorithm for calculating lattice of subgroups for any group. GAP does it very well but I need algorithm as I am trying to implement things myself as well.

Answer 1

To compute subgroup lattice of small groups such as $S_6$, you may find that the method of Zuppos is easy to understand, not too hard to implement, and is reasonably quick.

The method is described in Butler's textbook. It was originally described by Neubüser (1960).

The idea is big subgroups $H$ come from small subgroups $K$. In fact we can require $K \lhd H$ and $[H:K] =p$ (unless $H$ is very special). So we start with $K=1$, and then find all the subgroups of prime order. For each of those, we check which elements of appropriate order normalize $K$, and adjoin them. If $x$ normalizes $K$, then $|\langle x,K\rangle| = |xK| \cdot |K|$, where the first factor $|xK|$ is the order of $x$ mod $K$.

To make this more efficient we precompute a list of zuppos (cyclic subgroups of prime power order), and just figure out which zuppos lie in the group. Subgroups are listed as binary vectors, with the $i$th position's boolean value describing whether the $i$th zuppo is contained in the subgroup.

Implementation details, examples, and discussion are included in the book.

This technique should get you to the symmetric group $S_8$ or so, but you'll need the list of perfect groups (the special $H$ that don't come from a $K$). It is available on microfiche! Also in GAP.

GAP's implementation is line 259 of lib/grplatt.gi

• Neubüser, J. “Untersuchungen des Untergruppenverbandes endlicher Gruppen auf einer programmgesteuerten electronischen Dualmaschine.” Numer. Math. 2 (1960) 280–292. MR117939 DOI:10.1007/BF01386229
• Butler, G. Fundamental algorithms for permutation groups. Lecture Notes in Computer Science, 559. Springer-Verlag, Berlin, 1991. xii+238 pp. ISBN: 3-540-54955-2 MR1225579 DOI:10.1007/3-540-54955-2