[GAP Forum] algorithms for subgroups of a permutation group

[muhammad shah]

Dear Bill,
One such algorithm is implemented in GAP package SONATA which works as under:
gap> LoadPackage("sonata");:
gap>  D16 := DihedralGroup( 16 );
<pc group of size 16 with 4 generators>
gap>  S := Subgroups( D16 );
[ Group([  ]), Group([ f4 ]), Group([ f1 ]), Group([ f1*f3 ]), Group([ f1*f4 ]), Group([ f1*f3*f4 ]),
  Group([ f1*f2 ]), Group([ f1*f2*f3 ]), Group([ f1*f2*f4 ]), Group([ f1*f2*f3*f4 ]), Group([ f4, f3 ]),
  Group([ f4, f1 ]), Group([ f1*f3, f4 ]), Group([ f4, f1*f2 ]), Group([ f1*f2*f3, f4 ]), Group([ f4, f3, f1 ]),
  Group([ f4, f3, f2 ]), Group([ f4, f3, f1*f2 ]), Group([ f4, f3, f1, f2 ]) ]
For permutation groups,
gap> a:=AllSmallGroups(10);
[ <pc group of size 10 with 2 generators>, <pc group of size 10 with 2 generators> ]
gap> iso:=IsomorphismPermGroup(a[1]);
<action isomorphism>
gap> h:=Image(iso);
Group([ (1,2)(3,10)(4,9)(5,8)(6,7), (1,3,5,7,9)(2,4,6,8,10) ])
gap> S:= Subgroups( h );
[ Group(()), Group([ (1,2)(3,10)(4,9)(5,8)(6,7) ]), Group([ (1,8)(2,7)(3,6)(4,5)(9,10) ]), Group([ (1,4)(2,3)(5,10)
  (6,9)(7,8) ]), Group([ (1,10)(2,9)(3,8)(4,7)(5,6) ]), Group([ (1,6)(2,5)(3,4)(7,10)(8,9) ]), Group([ (1,3,5,7,9)
  (2,4,6,8,10) ]), Group([ (1,3,5,7,9)(2,4,6,8,10), (1,2)(3,10)(4,9)(5,8)(6,7) ]) ]
gap> a:=AllSmallGroups(1000);;
gap> iso:=IsomorphismPermGroup(a[1]);
<action isomorphism>
gap> h:=Image(iso);
<permutation group of size 1000 with 6 generators>
gap> S:= Subgroups( h );;
gap> Size(last);
168
Muhammad Shah


________________________________
From: Bill Allombert <Bill.Allombert at math.u-bordeaux.fr>
Sent: Friday, September 20, 2019 3:30 AM
To: GAP Forum <forum at gap-system.org>
Subject: [GAP Forum] algorithms for subgroups of a permutation group

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