Lifting a McL quotient

Alexander Hulpke
The following is a slightly edited and truncated transcript of a GAP 4.3 session in which we find the first quotient described in the paper. It might be of interest as an example on how to work with finitely presented groups. We start by creating the group from generators and relations. We also set the info level for fp groups higher, so GAP will print some information as it goes.
gap> SetInfoLevel(InfoFpGroup,2);
gap> F := FreeGroup( 10 );
< free group on the generators [ f1, f2, f3, f4, f5, f6, f7, f8, f9, f10 ]>
gap> relsG := [
>   F.1^2, F.2^2, F.3^2, F.4^2, F.5^2, F.6^2, F.7^2, F.8^2, F.9^2,
>   (F.1*F.2)^4, (F.1*F.3)^5, (F.1*F.4)^3, (F.1*F.5)^2, (F.1*F.6)^2*F.8,
>   (F.1*F.7)^2*F.9, (F.1*F.8)^2, (F.1*F.9)^2, (F.2*F.3)^2*F.4*F.7,
>   (F.2*F.4)^2, (F.2*F.5)^2, (F.2*F.6)^2*F.4, (F.2*F.7)^2, (F.2*F.8)^3,
>   (F.2*F.9)^2*F.5, (F.3*F.4)^2, (F.3*F.5)^2*F.4, (F.3*F.6)^2,
>   (F.3*F.7)^2, (F.3*F.8)^2*F.7, (F.3*F.9)^2*F.6*F.7,
>   (F.4*F.5)^2, (F.4*F.6)^2, (F.4*F.7)^2, (F.4*F.8)^2*F.6,
>   (F.4*F.9)^2*F.7, (F.5*F.6)^2*F.7, (F.5*F.7)^2, (F.5*F.8)^2*F.9,
>   (F.5*F.9)^2, (F.6*F.7)^2, (F.6*F.8)^2, (F.6*F.9)^2, (F.7*F.8)^2,
>   (F.7*F.9)^2, (F.8*F.9)^2,
>   F.10^2, (F.4*F.10)^2*F.5, Comm(F.10,F.1*F.4),
>   (F.3*F.10)^3, (F.10*F.6)^2*F.7*F.9,
>   (F.10*F.2)^2*F.5*F.7 ];;
gap> G := F / relsG;;
Next, we create the known quotient McL. This was given by extra relators. We also know subgroup generators for a subgroup of index 275.
gap> relsM := [ (F.1*F.3*F.2)^8, (F.10*F.3*F.1)^7 ];
[ f1*f3*f2*f1*f3*f2*f1*f3*f2*f1*f3*f2*f1*f3*f2*f1*f3*f2
    *f3*f1*f10*f3*f1 ]
gap> relsM:=Concatenation(relsM,relsG);;
gap> M := F / relsM;;
gap> UM:=[M.2,M.3,M.4,M.5,M.6,M.7,M.8,M.9,M.10, M.1*M.4*(M.3*M.1)^2 ];;
gap> UM := Subgroup( M, UM);
Group([ f2, f3, f4, f5, f6, f7, f8, f9, f10, f1*f4*f3*f1*f3*f1 ])
We compute a coset table for this subgroup and convert the columns corresponding to the generators (the even numbered columns represent inverses) into permutations. These generate McL, acting on 275 points. Finally we define the corresponding quotient hom from the finitely presented group G onto McL. This is the quotient we want to lift.
gap> tab:=CosetTable(M,UM);;
#I  CosetTableFromGensAndRels called:
#I  	167748	167473	275	128000
gap> Length(tab[1]);
gap> tab:=List(tab{[1,3..Length(tab)-1]},PermList);;
gap> mcl:=Group(tab);
< permutation group with 10 generators>
gap> Size(mcl);
gap> hom:=GroupHomomorphismByImages(G,mcl,GeneratorsOfGroup(G),tab);
#I  CosetTableFromGensAndRels called:
#I  	2	1	1	2
[ f1, f2, f3, f4, f5, f6, f7, f8, f9, f10 ] -> 
[ (1,2)(3,6)(4,9)(7,14)(10,17)(12,20)(15,27)(18,25)(19,26)(21,32)
  (76,77)(81,127) [...]
We let s be the subgroup which is the preimage of a point stabilizer and (by IsomorphismFpGroup) compute a presentation for it. Since rewriting alone produces too many generators, Tietze transformations are applied automatically by GAP. The resulting group has 4 generators. IsomorphismFpGroup returns an isomorphism to this new group, given by the preimages of the new generators.
(These preimages are represented as Straight line program elements. This way, they require less storage, than if we would multiply out the words. As we rarely have to refer to these preimages in a calculation this different storage does not come at a performance cost.)
gap> s:=PreImage(hom,Stabilizer(mcl,1));
Group(< fp, no generators known>)
gap> Index(G,s);
gap> hom2:=IsomorphismFpGroup(s);
#I  RRS defined 12 primary and 1447 secondary subgroup generators
#I  Presentation with 800 generators
#I  eliminating y45 = y18
#I  eliminating y63 = y44
#I  there are 4 generators and 49 relators of total length 1490
[ <[ [ 8, -1, 6, -1, 5, 1 ] ]|f1*f2*f1*f8^-1*f2^-1*f1^-1*f8^-1*f6>, 
  <[ [ 6, -1, 5, 1 ], [ 8, -1, 4, -1, 13, 1, 4, 1, 13, -1 ] ]|f1*f2*f1*f8^
    -1*f2^-1*f1^-1*f5^-1*f8^-1*f6*f5*f6^-1*f8>, [...]
 -> [ F1, F2, F3, F4 ]
gap> q:=Range(hom2);
< fp group on the generators [ F1, F2, F3, F4 ]>
Next, we compute the permutation images of the (new) generator preimages under the epimorphism onto McL and construct the corresponding epimorphism from the new fp group onto the point stabilizer in McL.
gap> gens:=List(GeneratorsOfGroup(q),
> i->Image(hom,PreImagesRepresentative(hom2,i)));
[ (2,8,6)(3,13,5)(4,7,18)(9,10,12)(11,15,21)(16,19,29)(20,31,22)
gap> h3:=GroupHomomorphismByImages(q,Subgroup(mcl,gens),
> GeneratorsOfGroup(q),gens);
[ F1, F2, F3, F4 ] -> 
[ (2,8,6)(3,13,5)(4,7,18)(9,10,12)(11,15,21)(16,19,29)(20,31,22)
It turns out that the point stabilizer has exactly one orbit of length 112. A stabilizer of a point in this orbit thus gives a subgroup of index 112 (and structure 34.A6). Again we takwe the preimage, obtaining a subgroup tp of index 112 in the new finitely presented group.
gap> o:=Orbits(Range(h3),[1..275]);;
gap> o:=First(o,i->Length(i)=112);;
gap> t:=Stabilizer(Image(h3),o[1]);
< permutation group of size 29160 with 4 generators>
brk> DisplayCompositionSeries(t);
G (4 gens, size 29160)
 | A(6)
S (5 gens, size 81)
 | Z(3)
S (4 gens, size 27)
 | Z(3)
S (2 gens, size 9)
 | Z(3)
S (1 gens, size 3)
 | Z(3)
1 (0 gens, size 1)

gap> tp:=PreImage(h3,t);
Group(< fp, no generators known>)
gap> Index(q,tp);
We now compute the epimorphism from tp onto its commutator factor group. GAP does this by first rewriting the presentation to one of tp and then abelianizing the presentation. The resulting abelian quotient of size 3 is represented as a pc group.
gap> maxab:=MaximalAbelianQuotient(tp);
#I  RRS defined 10 primary and 3514 secondary subgroup generators
#I  Presentation with 264 generators
#I  eliminating y13 = y2
#I  there are 10 generators and 925 relators of total length 115239
#I  replacement of generators stopped by length limit
[ <[ [ 2, 1 ] ]|F2^-2>, <[ [ 5, 1 ] ]|F2*F3*F2^-1>, 
  <[ [ 2, -1, 1, -1, 5, 1, 1, 1 ] ]|F2^2*F1^-1*F2*F3*F2^-1*F1>, [...]
 -> [ < identity>,< identity>,< identity>,< identity>, f1^2, < identity>,
   < identity>, f1^2, f1^2, < identity>]  ]
gap> Size(Image(maxab));
We now pull this quotient back to a subgroup of the original finitely presented group (of index 30800). For this we need a generating set for this subgroup (which is obtained by taking the primary generators of an augmented coset table.)
gap> U:=PreImage(hom2,tp);
Group(< fp, no generators known>)
gap> Index(G,U);
gap> Ugens:=GeneratorsOfGroup(U);;
gap> Length(Ugens);
gap> Umax:=RestrictedMapping(hom2,U)*maxab;
[ f7*f5^-1, f9*f5^-1, f1*f6*f5^-1*f1^-1, f2*f4*f5^-1, 
  f1*f2*f1*f4*f8^-1*f2^-1*f1^-1, f1*f3*f1*f3*f4^-1*f8^-1*f1^-1, [...]
  -> [ < identity> , < identity> , < identity>  < identity>,  [...]
  f1, < identity> , < identity> , < identity>  ]

We want to induce this representation to G. In principle, GAP will do this automatically, if we would compute the kernel of Umax. However - as it will automatically compute a stabilizer chain for the permutation image - this would take too much memory.

Instead, we induce the permutation representation ourselves:
By the Krasner-Kaloujnine embedding theorem, the induced permutation representation goes in a wreath product of the images of the original representation with the permutation representation on the cosets.
We obtain permutation images for the generators of G on 92400 points.

(Note that the DefiningQuotientHomomorphism of a subgroup is not necessarily the action on the cosets, but only some homomorphism whose kernel is contained in the subgroup. In this particular case, knowing what algorithms are used, it is this particular homomorphism.)

gap> Ucosrep:=DefiningQuotientHomomorphism(U);
[ f1, f2, f3, f4, f5, f6, f7, f8, f9, f10 ] -> 
[ (1,113)(2,114)(3,115)(4,116)(5,117)(6,118)(7,119)(8,120)(9,121)
  (10,122)(11,123)(12,124)(13,125)(14,126)(15,127)(16,128)  [...]
gap> perms:=KuKGenerators(G,Ucosrep,Umax);
[ (1,337)(2,338)(3,339)(4,340)(5,341)(6,342)(7,343)(8,344)(9,345)
  (10,346)(11,347)(12,348)(13,349)(14,350)(15,351)(16,352) [...]
gap> NrMovedPoints(perms);
We now want to see how big the permutation image is. To save some runtime, we first want to reduce the number of generators. We do this by reducing the presentation of G to find redundant generators.
gap> IsomorphismSimplifiedFpGroup(G);
#I  there are 10 generators and 51 relators of total length 220
#I  there are 5 generators and 25 relators of total length 193
[ f1, f2, f3, f4, f5, f6, f7, f8, f9, f10 ] -> 
[ f1, f2, f3, f2*f6*f2*f6, f10*f2*f6*f2*f6*f10*f2*f6*f2*f6, f6, 
  f3*f6*f2*f6*f3*f2, f1*f6*f1*f6, f1*f3*f6*f2*f6*f3*f2*f1*f3*f6*f2*f6*f3*f2, 
  f10 ]

It turns out, only the generators 1,2,3,6, and 10 are required. However creating a stabilizer chain for a permutation group of this size is very memory consuming. Because of this, we create straight line program elements from the permutations and form a group from them.

(Note: If we knew a base for the resulting group, the calculations would be much faster since we could set this base for the straight line program elements.)

gap> p2:=perms{[1,2,3,6,10]};;
gap> p3:=StraightLineProgGens(p2);
[ < [ [ 5, 1 ] ]|(1,337)(2,338)(3,339)(4,340)(5,341)(6,342)(7,343) [...]
gap> P:=Group(p3);
< permutation group with 5 generators>
To save time, we enforce a randomized (non-guaranteed) stabilizer chain calculation. (Of course, to prove the result, we could not have done this - my initial calculation did not use this shortcut.)

We find out that the permutation image has size 3104.|McL|

This stabilizer chain calculation is by far the hardest part of the whole calculation and can take a few hours.

gap> StabChainOptions(P).random:=1;
gap> Size(P);                      
gap> last/Size(mcl);
gap> Collected(Factors(last));
[ [ 3, 104 ] ]
The computed stabilizer chain provides us with a base for the group. Knowledge of this base will speed up comparisons of straight line program elements enormously (we only have to test equality on the 104 points of the base instead of 92400 points of the domain).

For the further calculations we therefore create the straight line program generators anew, this time with a base. We also create the permutation group P anew and store its size (in case another stabilizer chain calculation will be needed).

gap> bas:=BaseStabChain(StabChainMutable(P));
[ 1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 46, 52, 
  55, 58, 61, 337, 340, 343, 346, 349, 352, 355, 358, 361, 364,
  367, 370, 373, 376, 382, 
gap> Length(bas);
gap> p3:=StraightLineProgGens(p2,bas);;
gap> P:=Group(p3);
< permutation group with 5 generators>
gap> SetSize(P,Size(mcl)*3^104);
Finally we want to investigate the structure of the lift kernel 3104. We construct it as a normal closure of elements. For this we first need a kernel element:

The second relation for M above ( (F.10*F.3*F.1)^7 ) gives us a kernel element (indices shift to 5,3,1 since we only used 5 of the 10 generators).

gap> elm:=(P.5*P.3*P.1)^7; 
<[ [ 4, 1, 3, 1, 5, 1 ], [ 6, 7 ] ]|(679,681,680)(682,684,683) [...]
gap> Order(elm);
gap> S:=SubgroupNC(P,[elm]);
< permutation group with 1 generators>
Since we know, that the normal closure of this element must be a subgroup of the lift kernel, we know that it will be solvable. Using SolvableNormalClosurePermGroup then is preferrable, as it will produce (as a side effect) alsp a Pcgs for this closure (we need for investigating the module structure).

We are lucky that N is indeed the whole kernel - otherwise we would have had to add further elements. We also note that N is elementary abelian and thus an GF(3)-McL module

gap> N:=SolvableNormalClosurePermGroup(P,S);
< permutation group with 104 generators>
gap> Collected(Factors(Size(N)));
[ [ 3, 104 ] ]
gap> IsElementaryAbelian(N);
We now take a Pcgs for the normal closure. (This is an object that permits us to decompose elements of the group as normal form words in the generators. For an elementary abelian group, a Pcgs is a basis and the coefficients we get are basis coefficients.)

Using this Pcgs, we can compute matrices for the conjugation action of the group generators (respectively the factor McL) on the normal subgroup.
(Again, this calculation takes a bit, since we have to compute the coefficients for 5*104 conjugates.)

gap> pcgs:=Pcgs(N);
Pcgs([ <[ [ 93, 1 ] ]|(1,2,3)(43,45,44)(64,66,65)(67,69,68)(70,72,71)(73,75,
    74)(76,78,77)(82,84,83)(97,99,98)(100,102,101)(103,104,105) [...]
gap> mats:=LinearActionLayer(P,pcgs);
[ < immutable compressed matrix 104x104 over GF(3) >, 
  < immutable compressed matrix 104x104 over GF(3) >, 
  < immutable compressed matrix 104x104 over GF(3) >, 
  < immutable compressed matrix 104x104 over GF(3) >, 
  < immutable compressed matrix 104x104 over GF(3) > ]
We now use the MeatAxe to investigate the module structure. We form a GModule from the matrices.
An irreducibility test then shows, that this module is indeed irreducible.
gap> module:=GModuleByMats(mats,GF(3));
rec( field := GF(3), isMTXModule := true, dimension := 104, 
  generators := 
    [ < immutable compressed matrix 104x104 over GF(3) >, 
      < immutable compressed matrix 104x104 over GF(3) >, 
      < immutable compressed matrix 104x104 over GF(3) >, 
      < immutable compressed matrix 104x104 over GF(3) >, 
      < immutable compressed matrix 104x104 over GF(3) > ] )
gap> MTX.IsIrreducible(module);
As described in the paper, a second lift calculation for another subgroup yields overall a quotient (3104.3.321.3 ×3104).McL of the finitely presented group.

Back to the paper


Alexander Hulpke (