Finding low-index normal subgroups of finitely presented groups in GAP

I implemented a GAP package that provides an algorithm for computing normal subgroups of a finitely presented group up to a given index bound. (This algorithm is based on the thesis of David Firth at Warwick, 2005, but nothing beyond the thesis has been published.)

The implemented algorithm is not based on CosetTable methods and hopefully runs reasonable fast in practice.

Note that the package is currently WIP. If you have any suggestions or something does not work as expected, feel free to open an Issue on GitHub. Any feedback is highly appreciated.

The package is available on GitHub here: https://github.com/FriedrichRober/LINS

The algorithm is called LowIndexNormal.

gap> LoadPackage("LINS");;
gap> F := FreeGroup("a","b");;
gap> G := F / [ F.1^4, F.2^5, (F.1*F.2)^2 ];;
gap> L := LowIndexNormal(G,200);
[ rec( Group := <fp group on the generators [ a, b ]>, Index := 1, 
      Supergroups := [  ], 
      TriedPrimes := [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 
          47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 
          113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 
          191, 193, 197, 199 ] ), 
  rec( Group := Group([ a^-2, b ]), Index := 2, Supergroups := [ 1 ], 
      TriedPrimes := [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 
          47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 ] ), 
  rec( Group := Group([ a^-2, (b*a^-1)^2, b^-1*a*b^-1*a^-1, (b^2*a^-1)^2 ]), 
      Index := 10, Supergroups := [ 1, 2 ], TriedPrimes := [ 2, 5, 11 ] ), 
  rec( 
      Group := Group([ (b*a^-1*b^2*a^-1)^2, (b*(b*a^-1)^2)^2, 
          ((b^-1*a)^2*b^-1)^2, (b^-1*a*b^-2*a)^2, a*(b*a^-1*b^2*a^-1)^2*a^-1, 
          a*(b*(b*a^-1)^2)^2*a^-1, a^-1*b^-1*a*b*a^-1*b^-2*a^-1*b*a*b^-1*a^-1,
          a^-1*((b^-1*a)^2*b^-1)^2*a ]), Index := 120, 
      Supergroups := [ 1, 2 ], TriedPrimes := [  ] ), 
  rec( Group := Group(<fp, no generators known>), Index := 160, 
      Supergroups := [ 1, 2, 3 ], TriedPrimes := [  ] ) ]
gap> List(L, x -> x!.Index);
[ 1, 2, 10, 120, 160 ]
gap> last = List(L, x -> Index(G, x!.Group));
true

What I would do is to look at normal subgroups with solvable and nonsolvable factor group separately. First take the nonsolvable factor groups. There are just a few candidates:

gap> l:=AllSmallGroups(Size,[1..200],IsSolvable,false);;List(l,Size);
[ 60, 120, 120, 120, 168, 180 ]

Then test which ones can be quotients of $G$, and take the respective kernels.

gap> lq:=Concatenation(List(l,x->GQuotients(G,x)));
[ [ a, b ] -> [ (2,5,4,3), (1,2,3,4,5) ] ]
gap> k1:=List(lq,KernelOfMultiplicativeGeneralMapping);
[ Group(<fp, no generators known>) ]

Normal subgroups with solvable factor group must lie above some subgroup in the derived series. Here we find the third derived subgroup of index 160 (that is if the bound is 200 there cannot be a smaller normal subgroup:

gap> d:=DerivedSubgroup(G);;Index(G,d);AbelianInvariants(d);
2
[ 5 ]
gap> d:=DerivedSubgroup(d);;Index(G,d);AbelianInvariants(d);
10
[ 2, 2, 2, 2 ]
gap> d:=DerivedSubgroup(d);;Index(G,d);AbelianInvariants(d);
160
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]

Note that we now have an infinite abelianization. If we were looking for indices $\ge 320$, we would need to enumerate maximal submodules of this Z-module of suitable index, which is a bit more complicated than I can describe here.

Now take the natural homomorphism:

gap> q:=NaturalHomomorphismByNormalSubgroup(G,d);
gap> q:=q*IsomorphismSpecialPcGroup(Image(q));
[ a, b ] -> [ f1*f3*f5, f2*f4*f5*f6 ]

Note: In general, using the solvable quotient algorithm here would be far more effective, but it is harder to adjust it to find everything bounded index, which is the reason for this pedestrian approach.

Now take normal subgroups of the image of $q$ (of suitable index) and take their pre-images:

gap> k2:=Filtered(NormalSubgroups(Image(q)),x->Index(Image(q),x)<=200);;
gap> k2:=List(k2,x->PreImage(q,x));
gap> k:=Concatenation(k1,k2);;List(k,x->Index(G,x));
[ 120, 160, 10, 2, 1 ]

and we find 5 normal subgroups in total of indices 120,160,10,2 and 1.