GAP QA #10

Subgroups of a large finitely presented group

Keywords: Subgroups, finitely presented

Respondent:

Alexander Hulpke ( hulpke@math.colostate.edu)

Question:

I need all normalsubgroups of this group 

g=<x,y! x^3=y^3,(xy)^3xy^-1xyx^-1yxy^-1>

And my computer can not list all
normalsubgroups of g .
please help me.

Answer:

Usually these types of calculations are easiest done in an isomorphic
permutation group: 

gap> f:=FreeGroup("x","y");x:=f.1;y:=f.2;
<free group on the generators [ x, y ]>
x
y
gap> n:=[x^3/y^3,(x*y)^3*x/y*x*y/x*y*x/y];
[ x^3*y^-3, x*y*x*y*x*y*x*y^-1*x*y*x^-1*y*x*y^-1 ]
gap> g:=f/n;
<fp group on the generators [ x, y ]>
gap> hom:=IsomorphismPermGroup(g);;
gap> h:=Image(hom);;
gap> Size(h);
360000

IsomorphismPermGroup tries the action on the cosets of some cyclic
subgroups. In this case it fails and returns the regular representation. 

gap> NrMovedPoints(h);
360000

Before continuing, lets therefore devote a bit of work to get the degree
smaller (the default GAP function for this would be
`SmallerDegreePErmutationRepresentation' but as it is very opportunistic and
does not try to spend too much time, it does not give an improvement):
Try to find some cyclic subgroup in the permutation group such that the
action on its cosets is faithful. 

gap> r:=Random(h);;
gap> Order(r);
120
gap> r:=Random(h);;Order(r);
60
gap> u:=Subgroup(h,[r]);;
gap> v:=List(ConjugacyClassesSubgroups(u),Representative);;
gap> List(v,Size);
[ 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60 ]
gap> v:=Filtered(v,i->Size(Core(h,i))=1);
[ Group(()), <permutation group of size 5 with 1 generators> ]

This is not good enough. Try again 

gap> r:=Random(h);;Order(r);
30
gap> u:=Subgroup(h,[r]);;
gap> v:=List(ConjugacyClassesSubgroups(u),Representative);;
gap> v:=Filtered(v,i->Size(Core(h,i))=1);;
gap> List(v,Size);
[ 1, 2, 5, 10 ]
gap> u:=v[4];;

As the permutation action of h is regular, the action on the cosets of u is
given by action on the sets given by orbits of u: 

gap> b:=Orbit(h,Set(Orbit(u,1)),OnSets);;
gap> h1:=ActionHomomorphism(h,b,OnSets);
<action homomorphism>

We thus get a smaller degree permutation representation. We calculate the
permutation group image and calculatre normal subgroups in this image.
Finally we take preimages in the finitely presenetd group. 

gap> hom:=hom*h1;;
gap> h:=Image(hom);;
gap> n:=NormalSubgroups(h);;
gap> List(n,Size);
[ 1, 3, 2, 6, 4, 12, 8, 24, 5, 15, 10, 30, 20, 60, 40, 120, 125, 375, 250, 
  250, 750, 750, 500, 500, 1500, 1500, 1000, 1000, 3000, 3000, 250, 750,
  500, 1500, 1000, 3000, 2000, 6000, 15000, 45000, 30000, 90000, 60000,
  180000, 120000, 360000 ]
gap> np:=List(n,i->PreImage(hom,i));;
gap> Length(np);
46

Calculating generators will become more memory intensive for subgroups of
large index. We therefore treat cyclic (which are smaller) and noncyclic
subgroups differently.


For noncyclic subgroups, we just ask GAP to compute generators (This will
compute a coset table for each subgroup and use a Modified Todd-Coxeter
algorithm). 


gap> c:=Filtered([1..46],i->IsCyclic(n[i]));
 [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 ]
gap> List(np{Difference([1..46],c)},GeneratorsOfGroup);
 [ [ y*x*y*x*y^-1*x*y^-1*x^-1*y^-1*x^-1*y*x^-1, 
      y*x*y*x^-1*y*x^-1*y^-1*x^-1*y^-1*x*y^-1*x, 
      y*x^-1*y*x*y*x*y^-1*x*y^-1*x^-1*y^-1*x^-1 ], 
  [ y*x*y*x*y*x^-1*y^-1*x^-1*y^-1*x^-1, y*x*y*x*y^-1*x^-1*y^-1*x^-1*y^-1*x, 
      y*x*y*x^-1*y^-1*x^-1*y^-1*x^-1*y*x ], 
  [ y*x*y^-1*x*y*x*y^-1*x, y*x^-1*y^-1*x^-1*y*x^-1*y^-1*x^-1, 
      y^-1*x^-1*y*x^-1*y^-1*x^-1*y*x^-1, y^2*x*y^-1*x*y*x*y^-1*x*y^-1 ], 
  [ x^-12, y*x*y*x*y^-1*x*y^-1*x^-1*y^-1*x^-1*y*x^-1, 
      y*x*y*x^-1*y*x^-1*y^-1*x^-1*y^-1*x*y^-1*x ], 
  [ y*x*y*x*y*x^-1*y^-1*x^-1*y^-1*x^-1, y*x*y*x*y^-1*x^-1*y^-1*x^-1*y^-1*x, 
      y*x*y*x^-1*y^-1*x^-1*y^-1*x^-1*y*x, x^-12 ], 
  [ y*x*y*x^-1*y*x*y*x^-1, y*x*y^-1*x*y*x*y^-1*x, 
      y*x^-1*y^-1*x^-1*y*x^-1*y^-1*x^-1 ], 
  [ x^-1*y*x*y^-1*x*y*x^-2*y^-1*x^-1, x^-1*y^-1*x*y*x*y^-1*x*y^-2*x^-1, 
      y*x^2*y^2*x^-1*y*x^-1*y^-1*x^-1, y^-1*x*y^-1*x*y*x*y^-1*x^-2*y^-1 ], 
  [ x^-6, y*x*y*x*y^-1*x*y^-1*x^-1*y^-1*x^-1*y*x^-1, 
      y*x*y*x^-1*y*x^-1*y^-1*x^-1*y^-1*x*y^-1*x ], 
  [ x^-6, y*x*y*x*y*x^-1*y^-1*x^-1*y^-1*x^-1, 
      y*x*y*x*y^-1*x^-1*y^-1*x^-1*y^-1*x, y*x*y*x^-1*y^-1*x^-1*y^-1*x^-1*y*x ]
    , [ x^-1*y*x*y^-1*x*y*x^-2*y^-1*x^-1, x^-1*y*x^-1*y*x*y*x^-1*y^-2*x^-1, 
      x^-1*y^-1*x*y*x*y^-1*x*y^-2*x^-1 ], 
  [ x^-6, x^2*y*x^-1*y^-1*x^-1*y*x^-1*y^-1,
x^2*y^-1*x^-1*y*x^-1*y^-1*x^-1*y, 
      x*y*x^-1*y^-1*x^-1*y*x^-1*y^-1*x, y*x^-1*y*x^-1*y^-1*x^-1*y*x^-1*y ], 
  [ x^3, y*x*y*x*y^-1*x*y^-1*x^-1*y^-1*x^-1*y*x^-1, 
      y*x*y*x^-1*y*x^-1*y^-1*x^-1*y^-1*x*y^-1*x ], 
  [ x^3, y*x*y*x*y*x^-1*y^-1*x^-1*y^-1*x^-1, 
      y*x*y*x*y^-1*x^-1*y^-1*x^-1*y^-1*x,
y*x*y*x^-1*y^-1*x^-1*y^-1*x^-1*y*x, 
      y*x*y^-1*x^-1*y^-1*x^-1*y^-1*x*y*x ], 
  [ x^-6, x^2*y*x*y*x^-1*y*x*y, x^2*y*x^-1*y^-1*x^-1*y*x^-1*y^-1, 
      x^2*y^-1*x*y^-1*x^-1*y^-1*x*y^-1 ], 
  [ x^-1*y*x*y^-1*x^-2*y^-2*x^-2*y^-1*x^-1, 
      x^-1*y^-1*x*y*x^-2*y^-1*x^-2*y^-2*x^-1, y*x^2*y^2*x^2*y*x^2*y^-1*x^-1, 
      y*x*y*x^-1*y*x^-1*y^-1*x^-1*y^-1*x*y^-1*x ], 
  [ y*x*y*x*y*x^-1*y^-1*x^-1*y^-1*x^-1, y*x*y*x*y^-1*x^-1*y^-1*x^-1*y^-1*x, 
      y*x*y*x^-1*y^-1*x^-1*y^-1*x^-1*y*x, y*x^-1*y*x^-1*y*x^-1*y*x^-1*y*x^-1 ]
    , 
  [ y*x*y^-1*x*y*x*y^-1*x, y*x^-1*y^-1*x^-1*y*x^-1*y^-1*x^-1, y^-1*x^-1*y*x^
        -1*y^-1*x^-1*y*x^-1, y^2*x*y^-1*x*y*x*y^-1*x*y^-1, x^-12 ], 
  [ y*x*y*x^-1*y*x*y*x^-1, y*x*y^-1*x*y*x*y^-1*x, 
      y*x^-1*y^-1*x^-1*y*x^-1*y^-1*x^-1, y*x^-1*y*x^-1*y*x^-1*y*x^-1*y*x^-1 ],
  [ x^-6, y*x*y^-1*x*y*x*y^-1*x, y*x^-1*y^-1*x^-1*y*x^-1*y^-1*x^-1, 
      y^-1*x^-1*y*x^-1*y^-1*x^-1*y*x^-1, y^2*x*y^-1*x*y*x*y^-1*x*y^-1 ], 
  [ x^-6, y*x*y*x^-1*y*x*y*x^-1, y*x*y^-1*x*y*x*y^-1*x, 
      y*x^-1*y^-1*x^-1*y*x^-1*y^-1*x^-1 ], 
  [ x^3, y*x*y^-1*x*y*x*y^-1*x, y*x^-1*y^-1*x^-1*y*x^-1*y^-1*x^-1, 
      y^-1*x^-1*y*x^-1*y^-1*x^-1*y*x^-1, y*x^-1*y*x^-1*y^-1*x^-1*y*x^-1*y ], 
  [ x^3, y*x*y*x^-1*y*x*y*x^-1, y*x*y^-1*x*y*x*y^-1*x, 
      y*x^-1*y^-1*x^-1*y*x^-1*y^-1*x^-1 ], 
  [ y*x*y^-1*x^-1, y*x^-1*y^-1*x, y^-1*x*y*x^-1, y^-1*x^-1*y*x ], 
  [ y*x^-1, y^-1*x ], [ x^-4, y*x*y^-1*x^-1, y*x^-1*y^-1*x, y^-1*x*y*x^-1 ], 
  [ y*x^-1, y^-1*x, x^-4 ], [ x^-2, y*x*y^-1*x^-1, y^-1*x*y*x^-1 ], 
  [ x^-2, y*x^-1 ], [ x, y*x*y^-1, y^-1*x*y ], [ x, y ] ]

For the cyclic subgroups instead, we just take preimages for (permutation)
generators under the homomorphism. In general this will produce words that
are longer (that is why we did not use it in the general case), but the
result works fine here: 

gap> List(n{c},i->PreImagesRepresentative(hom,GeneratorOfCyclicGroup(i)));
 [ <identity ...>, y^-1*x*y^-1*x^-1*y^-1*x^-1*y^-1*x*y^-1*x^-1*y^-1*x^-1*y^
    -1*x*y^-1*x^-1*y^-1*x^-1*y^-1*x*y^-1*x^-1*y^-1*x^-2*y*x^-1*y*x^-2*y^-2*x^
    -1*y^-1*x^-2, y^-1*x*y^-1*x^-1*y^-1*x^-1*y^-1*x*y^-1*x^-1*y^-1*x^-1*y^
    -1*x*y^-1*x^-1*y^-1*x^-1*y^-1*x*y^-1*x^-1*y^-1*x^-1*y^-1*x*y^-1*x^-1*y^
    -1*x^-1, x^2*y*x*y*x*y*x*y^2*x^2*y^-1*x*y^-1*x^-1*y^-1*x*y*x*y*x^-1, 
  y^2*x*y^2*x*y^2*x^2*y*x^2*y^2*x^8*y^-1*x^-1*y^-1*x^-1*y*x*y, 
  x^2*y*x^2*y*x*y*x*y*x*y*x^2*y^-1*x^2*y*x*y*x^-1*y*x*y*x*y*x^-1*y, 
  x*y*x*y*x^-1*y*x*y*x*y*x^-1*y*x^-1*y^-2*x^-2*y^-1*x^-1*y^-1*x^-1*y^-1*x^
    -1*y^-1*x^-1*y^-1*x^-1*y^-1*x^-2*y^-1*x^-2, 
  y^-1*x*y^-1*x^-1*y^-1*x^-1*y^-1*x*y^-1*x^-1*y^-1*x^-2*y^-2*x^-2*y^-2*x^-2*y^
    -2*x^-1*y^-2*x^-2*y^-1*x^-1*y^-1*x^-2, x*y*x*y*x^-1*y*x*y*x*y*x^-1*y*x^
    -1*y^-2*x^-5*y^-1*x^-1*y^-1*x^-1*y^-1*x^-1*y^-1*x^-1*y^-1*x^-1*y^-1*x^
    -2*y^-1*x^-2, x*y*x^2*y^2*x*y^2*x^4*y^2*x*y^-1*x^-1*y^-1*x*y*x*y*x^-1, 
  x^12, x*y*x*y*x^-1*y*x*y*x*y*x^-1*y*x^-1*y^-2*x^-1*y^-1*x^-1*y^-1*x^-2*y^
    -2*x^-1*y^-2*x^-1*y^-1*x^-1*y^-1*x^-1*y^-1, x^-18, 
  x*y*x*y*x^-1*y*x*y*x*y*x^-1*y*x*y*x*y*x^-1*y*x*y*x*y*x^-1*y*x^-1*y*x^-2*y^
    -1*x^-1*y^-1*x^-2*y^-1*x^-2, y^-1*x^-1*y^-1*x*y*x*y*x^-11*y^-2*x^-2*y^
    -1*x^-2*y^-2*x^-1*y^-2*x^-1*y^-2, y*x^2*y^2*x*y*x*y^2*x^2*y*x*y^2*x^5*y*x^
    2*y^-1*x^-1*y^-1*x^-1*y*x*y ]

Back to the GAP QA list