GAP

Main BranchesDownloads Installation Overview Data Libraries Packages Documentation Contacts FAQ GAP 3 

Find us on GitHubSitemapNavigation Tree

Lifting a quotient of type McL of a finitely presented groupThis is an example from a paper by Alexander Hulpke. The example was triggered by a question of D. Pasechnik in the GAP Forum of January 1998. It demonstrates how a known (nonsolvable) quotient of a finitely presented group can be extended with solvable normal subgroups. So the example can be seen as enriching the family of methods such as the pquotient, nilpotent quotient, and soluble quotient methods for finitely presented groups. A main tool in the example is the representation of subgroups of finitely presented groups as preimages of subgroups of quotients. The input file and the original example page are also available. The following is a slightly edited and truncated transcript of a GAP 4 session in which we find the first quotient described in the paper. In the following listing we have suppressed some lines because they are not interesting, but marked where this has happened. We set the info level for fp groups higher, so GAP will print some information as it goes. gap> SizeScreen([76, ]);; gap> SetInfoLevel(InfoFpGroup,2); We start by creating a certain finitely presented group G from generators and relations. 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 a quotient M of F, given by extra relators, which was known to be isomorphic to McL. 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*f1*f3*f2*f1*f3*f2, f10*f3*f1*f10*f3*f1*f10*f3*f1*f10*f3*f1*f10*f3*f1*f10*f3*f1*f10*f3*f1 ] gap> relsM:=Concatenation(relsM,relsG);; gap> M := F / relsM;; We also know subgroup generators for a subgroup of index 275 of M. 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. gap> tab:=CosetTable(M,UM);; #I CosetTableFromGensAndRels called: #I 167748 167473 275 128000 gap> Length(tab[1]); 275 gap> perm:=List(tab{[1,3..Length(tab)1]},PermList);; gap> mcl:=Group(perm); <permutation group with 10 generators> gap> Size(mcl); 898128000 gap> DisplayCompositionSeries(mcl); G (10 gens, size 898128000)  Mc 1 (0 gens, size 1) Finally we define the corresponding quotient hom from the finitely presented group G onto McL. This is the quotient we want to lift. gap> hom:=GroupHomomorphismByImages(G,mcl,GeneratorsOfGroup(G),perm); #I CosetTableFromGensAndRels called: #I 2 1 1 2 #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)(22, 24)(23,35)(28,44)(29,41)(30,46)(33,51)(36,60)(37,58)(38,63)(42,65)(43, 67)(45,72)(47,75)(48,78)(50,54)(52,84)(53,59)(56,87)(57,92)(61,71)(62, 102)(66,80)(68,79)(69,107)(70,83)(73,119)(74,82)(76,77)(81,127)(85, 96)(86,106)(88,134)(89,90)(91,141)(93,130)(94,113)(95,137)(97,145)(98, [ ... 123 lines deleted ... ]
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. gap> s:=PreImage(hom,Stabilizer(mcl,1)); Group(<fp, no generators known>) gap> Index(G,s); 275 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 [ ... 692 lines deleted ... ] #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>, [ ... 41 lines deleted ... ] 11, 1, 15, 1, 33, 1, 34, 1, 25, 1, 25, 1, 12, 1 ] ]> ] > [ 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)(23,36, 52)(24,25,39)(28,33,47)(32,49,40)(34,41,55)(35,108,89)(38,48,61)(42, [ ... 43 lines deleted ... ] 264,66)(69,139,198,118)(71,221,231,78)(72,196,189,76)(73,207,180, 141)(74,163,150,95)( [...] ) ] gap> h3:=GroupHomomorphismByImages(q,Subgroup(mcl,gens), > GeneratorsOfGroup(q),gens); #I CosetTableFromGensAndRels called: #I 2 1 1 2 #I CosetTableFromGensAndRels called: #I 2 1 1 2 [ 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)(23,36, 52)(24,25,39)(28,33,47)(32,49,40)(34,41,55)(35,108,89)(38,48,61)(42, [ ... 43 lines deleted ... ] 264,66)(69,139,198,118)(71,221,231,78)(72,196,189,76)(73,207,180, 141)(74,163,150,95)( [...] ) ] 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 3^{4}.A_{6}). Again we take 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 5 generators> gap> DisplayCompositionSeries(t); G (5 gens, size 29160)  A(6) ~ A(1,9) = L(2,9) ~ B(1,9) = O(3,9) ~ C(1,9) = S(2,9) ~ 2A(1,9) = \ U(2,9) 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); 112 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 [ ... 895 lines deleted ... ] #I there are 10 generators and 925 relators of total length 115239 [ ... 6 lines deleted ... ] [ <[ [ 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>, [ ... 707 lines deleted ... ] 1, 59, 1, 327, 1, 325, 1, 271, 1, 234, 1, 18, 1, 320, 1 ] ]> ] > [ <identity> of ..., <identity> of ..., <identity> of ..., <identity> of ..., f1^2, <identity> of ..., <identity> of ..., f1^2, f1^2, <identity> of ... ] gap> Size(Image(maxab)); 3 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); 30800 gap> Ugens:=GeneratorsOfGroup(U);; #I RRS defined 30 primary and 126892 secondary subgroup generators gap> Length(Ugens); 30 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, [ ... 30 lines deleted ... ] f3*f10*f1*f3*f1*f2*f1*f3*f1*f2*f1*f9^1*f8^1*f2^1*f1^1*f3^1*f1^ 1*f3^1*f2^1*f10^1*f1^1*f3^1 ] > [ <identity> of ..., <identity> of ..., <identity> of ..., [ ... 7 lines deleted ... ] <identity> of ..., f1, <identity> of ..., <identity> of ..., <identity> of ... ] 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: (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)(17,129)(18, [ ... 125 lines deleted ... ] 217)(225,303)(226,336)(227,302)(228,309)( [...] ) ] 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)(17,353)(18, [ ... 124 lines deleted ... ] 251)(126,252)(130,172)( [...] ) ] gap> NrMovedPoints(perms); 92400 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 [ ... 41 lines deleted ... ] #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)(8, 344)(9,345)(10,346)(11,347)(12,348)(13,349)(14,350)(15,351)(16, [ ... 61 lines deleted ... ] 170)(123,171)(124,250)(125,251)(126,252)(130,172)( [...] )> ] gap> P:=Group(p3); <permutation group with 5 generators> To save time, we enforce a randomized (nonguaranteed) 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 3^{104}.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); 37492873537139989690410295685885170095161272386096844368000 gap> last/Size(mcl); 41745579179292917813953351511015323088870709282081 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, [ ... 6 lines deleted ... ] 1732, 2026, 2029, 2032, 2035, 2038, 2041, 2044, 2068 ] gap> Length(bas); 104 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 3^{104}. 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)(685,686, [ ... 11 lines deleted ... ] 948,947)(952,954,953)(955,957,956)(964,965,966)( [...] )> gap> Order(elm); 3 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) also 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); true 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. 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)(106, [ ... 1561 lines deleted ... ] 936)(943,944,945)(946,948,947)(952,954,953)(955,957,956)(964,965, 966)( [...] )> ]) 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. 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); true
As described in the paper, a second
lift calculation for another subgroup yields overall a quotient
(3^{104}.3.3^{21}.3 ×3^{104}).McL
of the finitely presented group. 1Nov2001 Alexander Hulpke Department of Mathematics Colorado State University Weber Building Fort Collins, CO 80523 USA email: hulpke@math.colostate.edu 

The GAP Group Last updated: Mon Oct 21 14:45:20 2019 