[GAP Forum] algorithms for subgroups of a permutation group

[Hulpke,Alexander]

Dear Forum, Dear Bill,

> 
> I have a question about computational group theory:
> 
> Is there an algorithm to compute all the subgroups of a permutation
> group ?

Yes. The earliest is cyclic extension:
Joachim Neubueser,Untersuchungen des Untergruppenverbandes endlicher Gruppen auf einer programmgesteuerten elektronischen Dualmaschine, Numer. Math. 2 (1960), 280–292 

then a significant improvement (solvable radical method)
John Cannon, Bruce Cox, and Derek Holt, Computing the subgroup lattice of a permutation group, J. Symbolic Comput. 31 (2001), no. 1/2, 149–161.

and an article of mine
Calculation of the subgroups of a trivial-Fitting group. Proc. ISSAC 2013, 205-210

They become subsequently harder, all require at minimum information (e.g. presentations and generators) for the possible perfect subgroups of simple groups.

If you wanted to implement something from scratch, probably cyclic extension (with its idea of storing subgroups as bit lists of ""Zuppos") is the easiest in that it requires little underlying machinery (indeed they ran it on machines with < 1k of memory in the 1960s), while the other two do.

A terse description of cyclic extension can be found in section VI.4 in my "notes": https://www.math.colostate.edu/~hulpke/CGT/cgtnotes.pdf, and (much more detail) in chapter 6 of Butler's "Fundamental Algorithms for Permutation Groups", LNCS 559, 1991

I think it would be hard to avoid any use of perfect groups, but if the group order is bound by 1000 there really are just a few possibilities.

All the best,

   Alexander


-- Alexander Hulpke, Colorado State University, Department of Mathematics,
Weber Building, 1874 Campus Delivery, Fort Collins, CO 80523-1874, USA
email: hulpke at colostate.edu, 
http://www.math.colostate.edu/~hulpke