[GAP Forum] algorithms for subgroups of a permutation group

[Pfeiffer, Gotz]

Dear Bill, dear Forum,

A naïve algorithm for listing all subgroups of a
small group G can be built on the following observation:

The monoid P(G) (the powerset of the set of elements of G)
with set union as its multiplication acts on the set of
subgroups H of G via H.B = <H, B> for subsets B of G,
and is generated by the singleton sets {a}, a \in G.

The set of all subgroups of G then simply is the
orbit of the trivial subgroup under P(G).

Implementatsion:

orbit:= function(A, x, under)
     local a, y, z, list;
     list:= [x];
     for y in list do
         for a in A do
             z:= under(y, a);
             if not z in list then Add(list, z); fi;
         od;
     od;
     return list;
end;

onGroups:= function(x, a)
     return Group(Union(GeneratorsOfGroup(x), a));
end;

subgroups:= function(group)
     return orbit(List(Elements(group), a-> [a]),
                  Subgroup(group, []), onGroups);
end;

Application:

     gap> G:= SymmetricGroup(5);
     Sym( [ 1 .. 5 ] )
     gap> Size(G);
     120
     gap> subs:= subgroups(G);;
     gap> time;
     4903
     gap> Length(subs);
     156

Obviously, there is room for improvement ...

Götz





On 19/09/2019 23:30, Bill Allombert wrote:
> Dear Forum,
> 
> I have a question about computational group theory:
> 
> Is there an algorithm to compute all the subgroups of a permutation
> group ?
> 
> I know there is an algorithm for solvable groups.
> 
> However I am looking for an algorithm that would work for small
> permutation groups (say degree <=100, order <=1000)
> preferably without having precomputed tables for all perfect groups.
> 
> Thanks,
> Bill
> 
> _______________________________________________
> Forum mailing list
> Forum at gap-system.org
> https://mail.gap-system.org/mailman/listinfo/forum
> 

-- 
------------------------------------------------------------------------
goetz.pfeiffer at nuigalway.ie           http://schmidt.nuigalway.ie/~goetz
Mathematics, NUI Galway, Ireland.                  phone +353-91-49-3591