[GAP Forum] Re: Fp group (was: Orfi)

[Alexander Hulpke]

Thank you to all of you (so far: Eamonn O'Brien, Mike Newman, Derek Holt,
Werner Nickel) who pointed out that I misread a relation in the group as two
relators. The proper group is a bit bigger:

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 and proceed as
before:
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 for some of the smaller subgroups might become a bit
memory intensive. We therefore treat cyclic normal subgroups differently:
Instead of using `GeneratorsOfGroup' (which computes Schreier generators
using a coset table) we just take preimages for (permutation) generators
under the homomorphism:

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(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 ]

and treat the rest in the same way:

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 ] ]

Best wishes,

  Alexander Hulpke