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@gap-system.org
> https://mail.gap-system.org/mailman/listinfo/forum
>
--
------------------------------------------------------------------------
goetz.pfeif...@nuigalway.ie http://schmidt.nuigalway.ie/~goetz
Mathematics, NUI Galway, Ireland. phone +353-91-49-3591
_______________________________________________
Forum mailing list
Forum@gap-system.org
https://mail.gap-system.org/mailman/listinfo/forum
