1############################################################################# 2## 3#W grphoms.gi Polycyc Bettina Eick 4## 5 6############################################################################# 7## 8## Functions to deal with homomorphisms to and from pcp groups. 9## 10## This function is modified version of GAP's DoGGMBINC 11 12BindGlobal( "GroupGeneralMappingByImages_for_pcp", function( G, H, gens, imgs ) 13 local mapi, filter, type, hom, pcgs, p, l, obj_args; 14 15 hom := rec( ); 16 if Length(gens)<>Length(imgs) then 17 Error("<gens> and <imgs> must be lists of same length"); 18 fi; 19 20# if not HasIsHandledByNiceMonomorphism(G) and ValueOption("noassert")<>true then 21# Assert( 2, ForAll( gens, x -> x in G ) ); 22# fi; 23# if not HasIsHandledByNiceMonomorphism(H) and ValueOption("noassert")<>true then 24# Assert( 2, ForAll( imgs, x -> x in H ) ); 25# fi; 26 27 mapi := [Immutable(gens), Immutable(imgs)]; 28 29 filter := IsGroupGeneralMappingByImages and HasSource and HasRange 30 and HasMappingGeneratorsImages; 31 32 if IsPcpGroup(G) then 33 hom!.igs_gens_to_imgs := IgsParallel( gens, imgs ); 34 filter := filter and IsFromPcpGHBI; 35 elif IsPcGroup( G ) and IsPrimeOrdersPcgs(Pcgs(G)) then 36 filter := filter and IsPcGroupGeneralMappingByImages; 37 pcgs := CanonicalPcgsByGeneratorsWithImages( Pcgs(G), mapi[1], mapi[2] ); 38 hom.sourcePcgs := pcgs[1]; 39 hom.sourcePcgsImages := pcgs[2]; 40 if pcgs[1]=Pcgs(G) then 41 filter := filter and IsTotal; 42 fi; 43 elif IsPcgs( gens ) then 44 filter := filter and IsGroupGeneralMappingByPcgs; 45 hom.sourcePcgs := mapi[1]; 46 hom.sourcePcgsImages := mapi[2]; 47 48 # Do we map a subgroup of a free group or an fp group by a subset of its 49 # standard generators? 50 # (So we can used MappedWord for mapping)? 51 elif IsSubgroupFpGroup(G) then 52 if HasIsWholeFamily(G) and IsWholeFamily(G) 53 # total on free generators 54 and Set(FreeGeneratorsOfFpGroup(G))=Set(List(gens,UnderlyingElement)) 55 then 56 l:=List(gens,UnderlyingElement); 57 p:=List(l,i->Position(FreeGeneratorsOfFpGroup(G),i)); 58 # test for duplicate generators, same images 59 if Length(gens)=Length(FreeGeneratorsOfFpGroup(G)) or 60 ForAll([1..Length(gens)],x->imgs[x]=imgs[Position(l,l[x])]) then 61 filter := filter and IsFromFpGroupStdGensGeneralMappingByImages; 62 hom.genpositions:=p; 63 else 64 filter := filter and IsFromFpGroupGeneralMappingByImages; 65 fi; 66 else 67 filter := filter and IsFromFpGroupGeneralMappingByImages; 68 fi; 69 elif IsPermGroup(G) then 70 filter := filter and IsPermGroupGeneralMappingByImages; 71 fi; 72 73 if IsPermGroup(H) then 74 filter := filter and IsToPermGroupGeneralMappingByImages; 75 elif IsPcGroup(H) then 76 filter := filter and IsToPcGroupGeneralMappingByImages; 77 elif IsSubgroupFpGroup(H) then 78 filter := filter and IsToFpGroupGeneralMappingByImages; 79 elif IsPcpGroup(H) then 80 hom!.igs_imgs_to_gens := IgsParallel( imgs, gens ); 81 filter := filter and IsToPcpGHBI; 82 fi; 83 84 obj_args := [ 85 hom, 86 , # Here the type will be inserted 87 Source, G, 88 Range, H, 89 MappingGeneratorsImages, mapi ]; 90 91 if HasGeneratorsOfGroup(G) 92 and IsIdenticalObj(GeneratorsOfGroup(G),mapi[1]) then 93 Append(obj_args, [PreImagesRange, G]); 94 filter := filter and IsTotal and HasPreImagesRange; 95 fi; 96 97 if HasGeneratorsOfGroup(H) 98 and IsIdenticalObj(GeneratorsOfGroup(H),mapi[2]) then 99 Append(obj_args, [ImagesSource, H]); 100 filter := filter and IsSurjective and HasImagesSource; 101 fi; 102 103 obj_args[2] := 104 NewType( GeneralMappingsFamily( ElementsFamily( FamilyObj( G ) ), 105 ElementsFamily( FamilyObj( H ) ) ), 106 filter ); 107 108 CallFuncList(ObjectifyWithAttributes, obj_args); 109 110 return hom; 111end ); 112 113############################################################################# 114## 115#M GGMBI( G, H ) . . . . . . . . . . . . . . . . . . . for G and H pcp groups 116## 117InstallMethod( GroupGeneralMappingByImagesNC, 118 "for pcp group, pcp group, list, list", 119 [IsPcpGroup, IsPcpGroup, IsList, IsList], 120 GroupGeneralMappingByImages_for_pcp ); 121 122############################################################################# 123## 124#M GGMBI( G, H ) . . . . . . . . . . . . . . . . . . . . . . for G pcp group 125## 126InstallMethod( GroupGeneralMappingByImagesNC, 127 "for pcp group, group, list, list", 128 [IsPcpGroup, IsGroup, IsList, IsList], 129 GroupGeneralMappingByImages_for_pcp ); 130 131############################################################################# 132## 133#M GGMBI( G, H ) . . . . . . . . . . . . . . . . . . . . . . for H pcp group 134## 135InstallMethod( GroupGeneralMappingByImagesNC, 136 "for group, pcp group, list, list", 137 [IsGroup, IsPcpGroup, IsList, IsList], 138 GroupGeneralMappingByImages_for_pcp ); 139 140############################################################################# 141## 142#M IsSingleValued( <IsFromPcpGHBI> ) 143## 144## This method is very similar to our CoKernelOfMultiplicativeGeneralMapping 145## method. However, a crucial difference is the call to 'NormalClosure' 146## at the end of CoKernelOfMultiplicativeGeneralMapping, which won't 147## terminate if the range is e.g. an infinite matrix group. 148InstallMethod( IsSingleValued, 149 "for IsFromPcpGHBI", 150 [ IsFromPcpGHBI ], 151function( hom ) 152 local gens, imgs, i, j, a, b, mapi; 153 154 if IsTrivial(Range(hom)) then 155 return true; 156 fi; 157 158 gens := hom!.igs_gens_to_imgs[1]; 159 imgs := hom!.igs_gens_to_imgs[2]; 160 161 # check relators 162 for i in [1..Length( gens )] do 163 if RelativeOrderPcp( gens[i] ) > 0 then 164 a := gens[i]^RelativeOrderPcp( gens[i] ); 165 a := MappedVector(ExponentsByIgs(gens, a), imgs); 166 b := imgs[i]^RelativeOrderPcp( gens[i] ); 167 if a <> b then return false; fi; 168 fi; 169 for j in [1..i-1] do 170 a := gens[i] ^ gens[j]; 171 a := MappedVector(ExponentsByIgs(gens, a), imgs); 172 b := imgs[i] ^ imgs[j]; 173 if a <> b then return false; fi; 174 175 if RelativeOrderPcp( gens[i] ) = 0 then 176 a := gens[i] ^ (gens[j]^-1); 177 a := MappedVector(ExponentsByIgs(gens, a), imgs); 178 b := imgs[i] ^ (imgs[j]^-1); 179 if a <> b then return false; fi; 180 fi; 181 od; 182 od; 183 184 # we still need to test any additional generators. This matters 185 # for generalized mappings which are not total or not single valued, 186 # such as the "inverse" of a non-surjective / non-injective group 187 # homomorphism. 188 mapi := MappingGeneratorsImages( hom ); 189 for i in [1..Length(mapi[1])] do 190 a := mapi[1][i]; 191 a := MappedVector(ExponentsByIgs(gens, a), imgs); 192 b := mapi[2][i]; 193 if a <> b then return false; fi; 194 od; 195 196 return true; 197end ); 198 199 200############################################################################# 201## 202#M CoKernelOfMultiplicativeGeneralMapping 203## 204InstallMethod( CoKernelOfMultiplicativeGeneralMapping, 205 "for IsFromPcpGHBI", 206 [ IsFromPcpGHBI ], 207function( hom ) 208 local C, gens, imgs, i, j, a, b, mapi; 209 210 if IsTrivial(Range(hom)) then 211 return Range(hom); 212 fi; 213 214 gens := hom!.igs_gens_to_imgs[1]; 215 imgs := hom!.igs_gens_to_imgs[2]; 216 217 C := TrivialSubgroup(Range(hom)); # the cokernel 218 219 # check relators 220 for i in [1..Length( gens )] do 221 if RelativeOrderPcp( gens[i] ) > 0 then 222 a := gens[i]^RelativeOrderPcp( gens[i] ); 223 a := MappedVector(ExponentsByIgs(gens, a), imgs); 224 b := imgs[i]^RelativeOrderPcp( gens[i] ); 225 C := ClosureSubgroupNC(C, a/b); 226 fi; 227 for j in [1..i-1] do 228 a := gens[i] ^ gens[j]; 229 a := MappedVector(ExponentsByIgs(gens, a), imgs); 230 b := imgs[i] ^ imgs[j]; 231 C := ClosureSubgroupNC(C, a/b); 232 233 if RelativeOrderPcp( gens[i] ) = 0 then 234 a := gens[i] ^ (gens[j]^-1); 235 a := MappedVector(ExponentsByIgs(gens, a), imgs); 236 b := imgs[i] ^ (imgs[j]^-1); 237 C := ClosureSubgroupNC(C, a/b); 238 fi; 239 od; 240 od; 241 242 # we still need to test any additional generators. This matters 243 # for generalized mappings which are not total or not single valued, 244 # such as the "inverse" of a non-surjective / non-injective group 245 # homomorphism. 246 mapi := MappingGeneratorsImages( hom ); 247 for i in [1..Length(mapi[1])] do 248 a := mapi[1][i]; 249 a := MappedVector(ExponentsByIgs(gens, a), imgs); 250 b := mapi[2][i]; 251 C := ClosureSubgroupNC(C, a/b); 252 od; 253 254 C := NormalClosure(ImagesSource(hom),C); 255 return C; 256end ); 257 258 259############################################################################# 260## 261#M Images 262## 263InstallMethod( ImagesRepresentative, 264 "for FromPcpGHBI", 265 FamSourceEqFamElm, 266 [ IsFromPcpGHBI, IsPcpElement ], 267function( hom, elm ) 268 local e; 269 if Length(hom!.igs_gens_to_imgs[1]) = 0 then return One(Range(hom)); fi; 270 e := ExponentsByIgs( hom!.igs_gens_to_imgs[1], elm ); 271 if e = fail then return fail; fi; 272 return MappedVector( e, hom!.igs_gens_to_imgs[2] ); 273end ); 274 275# TODO: Also implement ImagesSet methods, like we have PreImagesSet methods ? 276# Any particular reason for / against each? 277 278############################################################################# 279## 280#M PreImages 281## 282InstallMethod( PreImagesRepresentative, 283 "for ToPcpGHBI", 284 FamRangeEqFamElm, 285 [ IsToPcpGHBI, IsPcpElement ], 286function( hom, elm ) 287 local e; 288 if Length(hom!.igs_imgs_to_gens[1]) = 0 then return One(hom!.Source); fi; 289 e := ExponentsByIgs(hom!.igs_imgs_to_gens[1], elm); 290 if e = fail then return fail; fi; 291 return MappedVector(e, hom!.igs_imgs_to_gens[2]); 292end ); 293 294InstallMethod( PreImagesSet, 295 "for PcpGHBI", 296 CollFamRangeEqFamElms, 297 [ IsFromPcpGHBI and IsToPcpGHBI, IsPcpGroup ], 298function( hom, U ) 299 local prei, kern; 300 prei := List( Igs(U), x -> PreImagesRepresentative(hom,x) ); 301 if fail in prei then 302 TryNextMethod(); 303 # Potential solution: Intersect U with ImagesSource(hom) 304 # and then compute the preimage of that. 305 #gens := GeneratorsOfGroup( Intersection( ImagesSource(hom), U ) ); 306 #prei := List( gens, x -> PreImagesRepresentative(hom,x) ); 307 fi; 308 kern := Igs( KernelOfMultiplicativeGeneralMapping( hom ) ); 309 return SubgroupByIgs( Source(hom), kern, prei ); 310end ); 311 312############################################################################# 313## 314#M KernelOfMultiplicativeGeneralMapping 315## 316InstallMethod( KernelOfMultiplicativeGeneralMapping, 317 "for PcpGHBI", 318 [ IsFromPcpGHBI and IsToPcpGHBI], 319function( hom ) 320 local A, a, B, b, D, u, kern, i, g; 321 322 # set up 323 A := Source(hom); 324 a := MappingGeneratorsImages(hom)[1]; 325 B := Range(hom); 326 b := MappingGeneratorsImages(hom)[2]; 327 D := DirectProduct(B,A); 328 u := Cgs(Subgroup(D, List([1..Length(a)], x -> 329 Image(Embedding(D,1),b[x])*Image(Embedding(D,2),a[x])))); 330 331 # filter kernel gens 332 kern := []; 333 for i in [1..Length(u)] do 334 g := Image(Projection(D,1),u[i]); 335 if g = One(B) then 336 Add(kern, Image(Projection(D,2),u[i])); 337 fi; 338 od; 339 340 # create group 341 return Subgroup( Source(hom), kern); 342end ); 343 344# TODO: Add KernelOfMultiplicativeGeneralMapping method for IsToPcpGHBI 345# Slower than the one above but more general. 346 347############################################################################# 348## 349#M IsInjective( <hom> ) 350## 351InstallMethod( IsInjective, 352 "for PcpGHBI", 353 [ IsFromPcpGHBI and IsToPcpGHBI], 354function( hom ) 355 return Size( KernelOfMultiplicativeGeneralMapping(hom) ) = 1; 356end ); 357 358############################################################################# 359## 360#M KnowsHowToDecompose( <G>, <gens> ) 361## 362InstallMethod( KnowsHowToDecompose, 363 "pcp group and generators: always true", 364 IsIdenticalObj, 365 [ IsPcpGroup, IsList ], 0, 366 ReturnTrue); 367