1############################################################################# 2## 3## This file is part of GAP, a system for computational discrete algebra. 4## This file's authors include Thomas Breuer, Alexander Hulpke, Heiko Theißen. 5## 6## Copyright of GAP belongs to its developers, whose names are too numerous 7## to list here. Please refer to the COPYRIGHT file for details. 8## 9## SPDX-License-Identifier: GPL-2.0-or-later 10## 11## 1. Functions for creating group general mappings by images 12## 2. Functions for creating natural homomorphisms 13## 3. Functions for conjugation action 14## 4. Functions for ... 15## 16 17 18############################################################################# 19## 20#F GroupHomomorphismByImages( <G>, <H>, <Ggens>, <Hgens> ) 21#F GroupHomomorphismByImages( <G>, <H>, <Hgens> ) 22#F GroupHomomorphismByImages( <G>, <H> ) 23## 24InstallGlobalFunction( GroupHomomorphismByImages, 25 26function( arg ) 27 28 local hom, G, H, Ggens, Hgens,arrgh; 29 30 arrgh:=arg; 31 if not Length(arrgh) in [2..4] 32 or not IsGroup(arrgh[1]) #or not IsGroup(arrgh[2]) 33 then Error("for usage, see ?GroupHomomorphismByImages"); fi; 34 35 if not IsGroup(arrgh[2]) then 36 arrgh:=Concatenation([arrgh[1],Group(arrgh[Length(arrgh)])], 37 arrgh{[2..Length(arrgh)]}); 38 fi; 39 40 G := arrgh[1]; H := arrgh[2]; 41 42 if Length(arrgh) = 2 43 then Ggens := GeneratorsOfGroup(G); Hgens := GeneratorsOfGroup(H); 44 elif Length(arrgh) = 3 45 then Ggens := GeneratorsOfGroup(G); Hgens := arrgh[3]; 46 elif Length(arrgh) = 4 47 then Ggens := arrgh[3]; Hgens := arrgh[4]; 48 fi; 49 50 if Length(Ggens)>0 then 51 if not (IsDenseList(Ggens) and IsHomogeneousList(Ggens) and 52 FamilyObj(Ggens)=FamilyObj(G)) then 53 Error("The generators do not all belong to the source"); 54 fi; 55 fi; 56 57 if Length(Hgens)>0 then 58 if not (IsDenseList(Hgens) and IsHomogeneousList(Hgens) and 59 FamilyObj(Hgens)=FamilyObj(H)) then 60 Error("The images do not all belong to the range"); 61 fi; 62 fi; 63 64 hom:= GroupGeneralMappingByImages( G, H, Ggens, Hgens ); 65 66 if IsMapping( hom ) then 67 return hom; 68 # was GroupHomomorphismByImagesNC( G, H, Ggens, Hgens ), but why 69 # should we create a new object again?; 70 else 71 return fail; 72 fi; 73 74 end ); 75 76 77############################################################################# 78## 79#M RestrictedMapping(<hom>,<U>) 80## 81InstallMethod(RestrictedMapping,"try if restriction is proper", 82 CollFamSourceEqFamElms,[IsGroupGeneralMapping,IsGroup],SUM_FLAGS, 83function(hom, U) 84 if IsSubset (U, Source (hom)) then 85 return hom; 86 fi; 87 TryNextMethod(); 88end); 89 90 91############################################################################# 92## 93#M RestrictedMapping(<hom>,<U>) 94## 95InstallMethod(RestrictedMapping,"create new GHBI", 96 CollFamSourceEqFamElms,[IsGroupHomomorphism,IsGroup],0, 97function(hom,U) 98local rest,gens,imgs,imgp; 99 100 gens:=GeneratorsOfGroup(U); 101 imgs:=List(gens,i->ImageElm(hom,i)); 102 103 if HasImagesSource(hom) then 104 imgp:=ImagesSource(hom); 105 else 106 imgp:=Subgroup(Range(hom),imgs); 107 fi; 108 rest:=GroupHomomorphismByImagesNC(U,imgp,gens,imgs); 109 if HasIsInjective(hom) and IsInjective(hom) then 110 SetIsInjective(rest,true); 111 fi; 112 if HasIsTotal(hom) and IsTotal(hom) then 113 SetIsTotal(rest,true); 114 fi; 115 116 return rest; 117end); 118 119 120############################################################################# 121## 122#M RestrictedMapping(<hom>,<U>) 123## 124InstallMethod(RestrictedMapping,"injective case: use GeneralRestrictedMapping", 125 CollFamSourceEqFamElms,[IsGroupHomomorphism and IsInjective,IsGroup],0, 126function(hom,U) 127 128 if IsGroupGeneralMappingByImages(hom) then # restrictions of GHBI should be GHBI 129 TryNextMethod(); 130 fi; 131 132 return GeneralRestrictedMapping (hom, U, Range(hom)); 133end); 134 135 136############################################################################# 137## 138#M <a> = <b> . . . . . . . . . . . . . . . . . . . . . . . . . . via images 139## 140InstallMethod( \=, "compare source generator images", IsIdenticalObj, 141 [ IsGroupGeneralMapping, IsGroupGeneralMapping ], 0, 142 function( a, b ) 143 local i; 144 145 # try to fall back on homomorphism routines 146 if IsSingleValued(a) and IsSingleValued(b) then 147 # As both are single valued (and the appropriate flags are now set) 148 # we will automatically fall in the routines for homomorphisms. 149 # So this is not an infinite recursion. 150#T is this really safe? 151 a:=MappingGeneratorsImages(a); 152 return a[2]=List(a[1],i->ImagesRepresentative(b,i)); 153 fi; 154 155 # now do the hard test 156 if Source(a)<>Source(b) 157 or Range(a)<>Range(b) 158 or PreImagesRange(a)<>PreImagesRange(b) 159 or ImagesSource(a)<>ImagesSource(b) then 160 return false; 161 fi; 162 for i in PreImagesRange(a) do 163 if Set(Images(a,i))<>Set(Images(b,i)) then 164 return false; 165 fi; 166 od; 167 return true; 168 end ); 169 170############################################################################# 171## 172#M IsOne( <hom> ) 173## 174InstallMethod(IsOne,"using `MappingGeneratorsImages'",true, 175 [IsGroupHomomorphism and HasMappingGeneratorsImages],0, 176function(a) 177 local m; 178 # if a is total it is defined on all of the source, if gens and images are 179 # the same it automatically is bijective 180 if Source(a)=Range(a) and IsTotal(a) then 181 m:=MappingGeneratorsImages(a); 182 return ForAll([1..Length(m[1])],i->m[1][i]=m[2][i]); 183 fi; 184 return false; 185end); 186 187############################################################################# 188## 189#M CompositionMapping2( <hom1>, <hom2> ) . . . . . . . . . . . . via images 190## 191## The composition of two group general mappings can be computed as 192## a group general mapping by images, *provided* that 193## - elements of the source of the first map can be cheaply decomposed 194## in terms of the generators 195## (This is needed for computing images with a 196## group general mapping by images.) 197## and 198## - we are *not* in the situation of the composition of a general mapping 199## with a nice monomorphism. 200## (Here it will usually be better to store the explicit composition 201## of two mappings, think of an isomorphism from a matrix group to a 202## permutation group, where both the action homomorphism and the 203## isomorphism of two permutation groups can compute (pre)images 204## efficiently, contrary to the composition when this is written as 205## homomorphism by images.) 206## 207## (If both general mappings know that they are in fact homomorphisms 208## then also the result will be a homomorphism; this is not done 209## here, however, but rather in function CompositionMapping.) 210## 211InstallMethod( CompositionMapping2, 212 "for gp. hom. and gp. gen. mapp., using `MappingGeneratorsImages'", 213 FamSource1EqFamRange2, 214 [ IsGroupHomomorphism, IsGroupGeneralMapping ], 0, 215function( hom1, hom2 ) 216local mapi; 217 if (not KnowsHowToDecompose(Source(hom2))) or IsNiceMonomorphism(hom2) then 218 TryNextMethod(); 219 fi; 220 if not IsSubset(Source(hom1),ImagesSource(hom2)) then 221 TryNextMethod(); 222 fi; 223 mapi:=MappingGeneratorsImages(hom2); 224 return GroupGeneralMappingByImagesNC( Source( hom2 ), Range( hom1 ), 225 mapi[1], List( mapi[2], img -> 226 ImagesRepresentative( hom1, img ) ) ); 227end); 228 229 230InstallOtherMethod( SetInverseGeneralMapping,"transfer the AsGHBI", true, 231 [ IsGroupGeneralMappingByAsGroupGeneralMappingByImages and 232 HasAsGroupGeneralMappingByImages, 233 IsGeneralMapping ], 0, 234function( hom, inv ) 235 SetInverseGeneralMapping( AsGroupGeneralMappingByImages( hom ), inv ); 236 TryNextMethod(); 237end ); 238 239InstallOtherMethod( SetRestrictedInverseGeneralMapping,"transfer the AsGHBI", true, 240 [ IsGroupGeneralMappingByAsGroupGeneralMappingByImages and 241 HasAsGroupGeneralMappingByImages, 242 IsGeneralMapping ], 0, 243function( hom, inv ) 244 SetRestrictedInverseGeneralMapping( AsGroupGeneralMappingByImages( hom ), inv ); 245 TryNextMethod(); 246end ); 247 248 249############################################################################# 250## 251#M ImagesRepresentative( <hom>, <elm> ) . . . . . . . . . . . . via images 252## 253InstallMethod( ImagesRepresentative, "for `ByAsGroupGeneralMapping' hom", 254 FamSourceEqFamElm, 255 [ IsGroupGeneralMappingByAsGroupGeneralMappingByImages, 256 IsMultiplicativeElementWithInverse ], 0, 257function( hom, elm ) 258 return ImagesRepresentative( AsGroupGeneralMappingByImages( hom ), elm ); 259end ); 260 261 262############################################################################# 263## 264#M PreImagesRepresentative( <hom>, <elm> ) . . . . . . . . . . . via images 265## 266InstallMethod( PreImagesRepresentative, "for PBG-Hom", FamRangeEqFamElm, 267 [ IsPreimagesByAsGroupGeneralMappingByImages, 268 IsMultiplicativeElementWithInverse ], 0, 269function( hom, elm ) 270 if HasIsHandledByNiceMonomorphism(Source(hom)) then 271 # if we use the `AsGGMBI' directly, it will be a composite through a big 272 # group 273 return ImagesRepresentative( RestrictedInverseGeneralMapping( hom ), elm ); 274 else 275 return PreImagesRepresentative( AsGroupGeneralMappingByImages( hom ), elm ); 276 fi; 277end ); 278 279InstallAttributeMethodByGroupGeneralMappingByImages( CoKernelOfMultiplicativeGeneralMapping ); 280InstallAttributeMethodByGroupGeneralMappingByImages( KernelOfMultiplicativeGeneralMapping ); 281InstallAttributeMethodByGroupGeneralMappingByImages( PreImagesRange ); 282InstallAttributeMethodByGroupGeneralMappingByImages( ImagesSource ); 283InstallAttributeMethodByGroupGeneralMappingByImages( IsSingleValued ); 284InstallAttributeMethodByGroupGeneralMappingByImages( IsInjective ); 285InstallAttributeMethodByGroupGeneralMappingByImages( IsTotal ); 286InstallAttributeMethodByGroupGeneralMappingByImages( IsSurjective ); 287 288 289############################################################################# 290## 291#M GroupGeneralMappingByImages( <G>, <H>, <gens>, <imgs> ) . . . . make GHBI 292## 293BindGlobal("DoGGMBINC",function( G, H, gens, imgs ) 294local filter, hom,pcgs,imgso,mapi,l,obj_args,p; 295 296 hom := rec(); 297 # generators := Immutable( gens ), 298 # genimages := Immutable( imgs ) ); 299 if Length(gens)<>Length(imgs) then 300 Error("<gens> and <imgs> must be lists of same length"); 301 fi; 302 303 if not HasIsHandledByNiceMonomorphism(G) and ValueOption("noassert")<>true then 304 Assert( 2, ForAll( gens, x -> x in G ) ); 305 fi; 306 if not HasIsHandledByNiceMonomorphism(H) and ValueOption("noassert")<>true then 307 Assert( 2, ForAll( imgs, x -> x in H ) ); 308 fi; 309 310 mapi:=[Immutable(gens),Immutable(imgs)]; 311 filter := IsGroupGeneralMappingByImages and HasSource and HasRange 312 and HasMappingGeneratorsImages; 313 314 if IsPermGroup( G ) then 315 filter := filter and IsPermGroupGeneralMappingByImages; 316 fi; 317 if IsPermGroup( H ) then 318 filter := filter and IsToPermGroupGeneralMappingByImages; 319 fi; 320 321 pcgs:=false; # default: no pc groups code 322 if IsPcGroup( G ) and IsPrimeOrdersPcgs(Pcgs(G)) then 323 filter := filter and IsPcGroupGeneralMappingByImages; 324 pcgs := CanonicalPcgsByGeneratorsWithImages( Pcgs(G), mapi[1], mapi[2] ); 325 if pcgs[1]=Pcgs(G) then 326 filter:=filter and IsTotal; 327 fi; 328 elif IsPcgs( gens ) then 329 filter := filter and IsGroupGeneralMappingByPcgs; 330 pcgs:=mapi; 331 fi; 332 333 if pcgs<>false then 334 hom.sourcePcgs := pcgs[1]; 335 hom.sourcePcgsImages := pcgs[2]; 336 fi; 337 338 if IsPcGroup( H ) then 339 filter := filter and IsToPcGroupGeneralMappingByImages; 340 fi; 341 342 # Do we map a subgroup of a free group or an fp group by a subset of its 343 # standard generators? 344 # (So we can used MappedWord for mapping)? 345 if IsSubgroupFpGroup(G) then 346 if HasIsWholeFamily(G) and IsWholeFamily(G) 347 # total on free generators 348 and Set(FreeGeneratorsOfFpGroup(G))=Set(List(gens,UnderlyingElement)) 349 then 350 l:=List(gens,UnderlyingElement); 351 p:=List(l,i->Position(FreeGeneratorsOfFpGroup(G),i)); 352 # test for duplicate generators, same images 353 if Length(gens)=Length(FreeGeneratorsOfFpGroup(G)) or 354 ForAll([1..Length(gens)],x->imgs[x]=imgs[Position(l,l[x])]) then 355 filter := filter and IsFromFpGroupStdGensGeneralMappingByImages; 356 hom.genpositions:=p; 357 else 358 filter := filter and IsFromFpGroupGeneralMappingByImages; 359 fi; 360 else 361 filter := filter and IsFromFpGroupGeneralMappingByImages; 362 fi; 363 fi; 364 if IsSubgroupFpGroup(H) then 365 filter := filter and IsToFpGroupGeneralMappingByImages; 366 fi; 367 368 obj_args := [ 369 hom, 370 , # Here the type will be inserted 371 Source, G, 372 Range, H, 373 MappingGeneratorsImages, mapi ]; 374 375 if HasGeneratorsOfGroup(G) 376 and IsIdenticalObj(GeneratorsOfGroup(G),mapi[1]) then 377 Append(obj_args, [PreImagesRange, G]); 378 filter := filter and IsTotal and HasPreImagesRange; 379 fi; 380 381 if HasGeneratorsOfGroup(H) 382 and IsIdenticalObj(GeneratorsOfGroup(H),mapi[2]) then 383 Append(obj_args, [ImagesSource, H]); 384 filter := filter and IsSurjective and HasImagesSource; 385 elif pcgs <> false then 386 # The following code is only guaranteed to be correct if the map is 387 # single valued. 388 #if RankFilter(filter) = RankFilter(filter and IsSingleValued) then 389 # imgso:=SubgroupNC( H, pcgs[2]); 390 # Append(obj_args, [ImagesSource, imgso]); 391 #fi; 392 fi; 393 394 obj_args[2] := 395 NewType( GeneralMappingsFamily( ElementsFamily( FamilyObj( G ) ), 396 ElementsFamily( FamilyObj( H ) ) ), 397 filter ); 398 399 CallFuncList(ObjectifyWithAttributes, obj_args); 400 401 return hom; 402end ); 403 404InstallMethod( GroupGeneralMappingByImagesNC, "for group, group, list, list", 405 true, [ IsGroup, IsGroup, IsList, IsList ], 0, DoGGMBINC); 406 407InstallMethod( GroupGeneralMappingByImagesNC, "make onto", 408 true, [ IsGroup, IsList, IsList ], 0, 409function( G, gens, imgs ) 410 return GroupGeneralMappingByImagesNC(G,GroupWithGenerators(imgs),gens,imgs); 411end); 412 413InstallMethod( GroupGeneralMappingByImages, "for group, group, list, list", 414 true, [ IsGroup, IsGroup, IsList, IsList ], 0, 415function( G, H, gens, imgs ) 416 if not ForAll(gens,x->x in G) then 417 Error("generators must lie in source group"); 418 elif not ForAll(imgs,x->x in H) then 419 Error("images must lie in range group"); 420 fi; 421 return GroupGeneralMappingByImagesNC(G,H,gens,imgs); 422end); 423 424InstallMethod( GroupGeneralMappingByImages, "make onto", 425 true, [ IsGroup, IsList, IsList ], 0, 426function( G, gens, imgs ) 427 if not ForAll(gens,x->x in G) then 428 Error("generators must lie in source group"); 429 fi; 430 return GroupGeneralMappingByImagesNC(G,gens,imgs); 431end); 432 433InstallMethod( GroupHomomorphismByImagesNC, "for group, group, list, list", 434 true, [ IsGroup, IsGroup, IsList, IsList ], 0, 435function( G, H, gens, imgs ) 436local hom; 437 hom := GroupGeneralMappingByImagesNC( G, H, gens, imgs ); 438 if not (HasIsHandledByNiceMonomorphism(G) or 439 HasIsHandledByNiceMonomorphism(H)) 440 and ValueOption("noassert")<>true 441 and not IsSubgroupFpGroup(H) then 442 Assert( 3, IsMapping( hom ) ); 443 fi; 444 SetIsMapping( hom, true ); 445 return hom; 446end ); 447 448InstallMethod( GroupHomomorphismByImagesNC, "for group, list, list", 449 true, [ IsGroup, IsList, IsList ], 0, 450function( G, gens, imgs ) 451local hom; 452 hom := GroupGeneralMappingByImagesNC( G, gens, imgs ); 453 if not HasIsHandledByNiceMonomorphism(G) and ValueOption("noassert")<>true then 454 Assert( 3, IsMapping( hom ) ); 455 fi; 456 SetIsMapping( hom, true ); 457 return hom; 458end ); 459 460InstallOtherMethod( GroupHomomorphismByImagesNC, "for group, group, list", 461 true, [ IsGroup, IsGroup, IsList ], 0, 462 463 function( G, H, imgs ) 464 return GroupHomomorphismByImagesNC( G, H, GeneratorsOfGroup(G), imgs ); 465 end ); 466 467InstallOtherMethod( GroupHomomorphismByImagesNC, "for group, group", 468 true, [ IsGroup, IsGroup ], 0, 469 470 function( G, H ) 471 return GroupHomomorphismByImagesNC( G, H, GeneratorsOfGroup(G), 472 GeneratorsOfGroup(H) ); 473 end ); 474 475############################################################################# 476## 477#M MappingGeneratorsImages( <map> ) . . . . . . . . for group homomorphism 478## 479InstallMethod( MappingGeneratorsImages, "for group homomorphism", 480 true, [ IsGroupHomomorphism ], 0, 481function( map ) 482local gens; 483 # temporary workaround for compatibility with external code. 484 if IsBound(map!.generators) and IsBound(map!.genimages) then 485 Info(InfoWarning,1,"still using !.gen(erators/images)"); 486 return [map!.generators,map!.genimages]; 487 fi; 488 gens:= GeneratorsOfGroup( PreImagesRange( map ) ); 489 return [gens, List( gens, g -> ImagesRepresentative( map, g ) ) ]; 490end ); 491 492RedispatchOnCondition(MappingGeneratorsImages,true, 493 [IsGeneralMapping],[IsGroupHomomorphism],0); 494 495 496############################################################################# 497## 498#M AsGroupGeneralMappingByImages( <map> ) . . . . . for group homomorphism 499## 500InstallMethod( AsGroupGeneralMappingByImages, "for group homomorphism", 501 true, [ IsGroupHomomorphism ], 0, 502function( map ) 503local mapi,hom; 504 Range(map); # for surjective action homomorphisms thsi enforces 505 # computation of the MappingGeneratorsImages as well 506 mapi:=MappingGeneratorsImages(map); 507 hom:=GroupHomomorphismByImagesNC(Source(map),Range(map),mapi[1],mapi[2]); 508 CopyMappingAttributes(map,hom); 509 return hom; 510end ); 511 512InstallMethod( AsGroupGeneralMappingByImages, "for group general mapping", 513 true, [ IsGroupGeneralMapping ], 0, 514function( map ) 515local mapi, cok,hom; 516 mapi:=MappingGeneratorsImages(map); 517 cok := GeneratorsOfGroup( CoKernelOfMultiplicativeGeneralMapping( map ) ); 518 hom:=GroupGeneralMappingByImagesNC( Source( map ), Range( map ), 519 Concatenation( mapi[1],List(cok,g->One(Source(map)))), 520 Concatenation( mapi[2],cok ) ); 521 CopyMappingAttributes(map,hom); 522 return hom; 523end ); 524 525############################################################################# 526## 527#M AsGroupGeneralMappingByImages( <hom> ) . . . . . . . . . . . . for GHBI 528## 529InstallMethod( AsGroupGeneralMappingByImages, "for GHBI", true, 530 [ IsGroupGeneralMappingByImages ], 531 SUM_FLAGS, # better than everything else 532 IdFunc ); 533 534############################################################################# 535## 536#M MappingOfWhichItIsAsGGMBI 537## 538InstallMethod(SetAsGroupGeneralMappingByImages, 539 "assign MappingOfWhichItIsAsGGMBI",true, 540 [ IsGroupGeneralMapping and IsAttributeStoringRep, 541 IsGroupGeneralMapping],0, 542function(map,as) 543 SetMappingOfWhichItIsAsGGMBI(as,map); 544 TryNextMethod(); 545end); 546 547############################################################################# 548## 549#M <hom1> = <hom2> . . . . . . . . . . . . . . . . . . . . . . . . for GHBI 550## 551InstallMethod( \=, 552 "homomorphism by images with homomorphism: compare generator images", 553 IsIdenticalObj, 554 [ IsGroupHomomorphism and IsGroupGeneralMappingByImages, 555 IsGroupHomomorphism ], 1, 556 function( hom1, hom2 ) 557 local i,mapi; 558 559 if Source( hom1 ) <> Source( hom2 ) 560 or Range ( hom1 ) <> Range ( hom2 ) then 561 return false; 562 fi; 563 mapi:=MappingGeneratorsImages(hom1); 564 if IsGroupGeneralMappingByImages( hom2 ) 565 and Length(MappingGeneratorsImages(hom2)[1]) < Length(mapi[1]) then 566 return hom2 = hom1; 567 fi; 568 for i in [ 1 .. Length( mapi[1] ) ] do 569 if ImagesRepresentative( hom2, mapi[1][i] ) <> mapi[2][ i ] then 570 return false; 571 fi; 572 od; 573 return true; 574end ); 575 576InstallMethod( \=, 577 "homomorphism with general mapping: test b=a", 578 IsIdenticalObj, 579 [ IsGroupHomomorphism, 580 IsGroupHomomorphism and IsGroupGeneralMappingByImages ], 0, 581 function( hom1, hom2 ) 582 return hom2 = hom1; 583end ); 584 585InstallMethod( ImagesSmallestGenerators,"group homomorphisms", true, 586 [ IsGroupHomomorphism ], 0, 587function(a) 588 return List(GeneratorsSmallest(Source(a)),i->Image(a,i)); 589end); 590 591InstallMethod( \<,"group homomorphisms: Images of smallest generators", 592 IsIdenticalObj, [ IsGroupHomomorphism, IsGroupHomomorphism ], 0, 593function(a,b) 594 if Source(a)<>Source(b) then 595 return Source(a)<Source(b); 596 elif Range(a)<>Range(b) then 597 return Range(a)<Range(b); 598 else 599 return ImagesSmallestGenerators(a)<ImagesSmallestGenerators(b); 600 fi; 601end); 602 603 604############################################################################# 605## 606#M ImagesSource( <hom> ) . . . . . . . . . . . . . . for group homomorphism 607## 608InstallMethod( ImagesSource, "for group homomorphism", true, 609 [ IsGroupHomomorphism ], 610 # rank higher than the method for IsGroupGeneralMappingByImages, 611 # as we can exploit more structure here 612 {} -> RankFilter(IsGroupHomomorphism and IsGroupGeneralMappingByImages) 613 - RankFilter(IsGroupHomomorphism), 614function(hom) 615local gens, G; 616 gens := GeneratorsOfGroup(Source(hom)); 617 if Length(MappingGeneratorsImages(hom)[1]) > 2*Length(gens) then 618 gens := List(gens, i->ImageElm(hom,i)); 619 else 620 gens := MappingGeneratorsImages(hom)[2]; 621 fi; 622 G := SubgroupNC(Range(hom), gens); 623 624 # Transfer some knowledge about the source group to its image. 625 if HasIsInjective(hom) and IsInjective(hom) then 626 UseIsomorphismRelation( Source(hom), G ); 627 elif HasKernelOfMultiplicativeGeneralMapping(hom) then 628 UseFactorRelation( Source(hom), KernelOfMultiplicativeGeneralMapping(hom), G ); 629 else 630 UseFactorRelation( Source(hom), fail, G ); 631 fi; 632 633 return G; 634end); 635 636############################################################################# 637## 638#M ImagesSource( <hom> ) . . . . . . . . . . . . . . . . . . . . . for GHBI 639## 640InstallMethod( ImagesSource, "for GHBI", true, 641 [ IsGroupGeneralMappingByImages ], 0, 642 hom -> SubgroupNC( Range( hom ), MappingGeneratorsImages(hom)[2] ) ); 643 644############################################################################# 645## 646#M PreImagesRange( <hom> ) . . . . . . . . . . . . . . . . . . . . for GHBI 647## 648InstallMethod( PreImagesRange, "for GHBI", true, 649 [ IsGroupGeneralMappingByImages ], 0, 650 hom -> SubgroupNC( Source( hom ), MappingGeneratorsImages(hom)[1] ) ); 651 652 653############################################################################# 654## 655#M InverseGeneralMapping( <hom> ) . . . . . . . . . . . . . . . . for GHBI 656## 657InstallMethod( InverseGeneralMapping, "via generators/images", true, 658 [ IsGroupGeneralMapping ], 0, 659function( hom ) 660local mapi; 661 mapi:=MappingGeneratorsImages(hom); 662 mapi:=GroupGeneralMappingByImagesNC( Range( hom ), Source( hom ), 663 mapi[2], mapi[1] ); 664 if HasIsSurjective(hom) then 665 SetIsTotal(mapi,IsSurjective(hom)); 666 fi; 667 if HasIsTotal(hom) then 668 SetIsSurjective(mapi, IsTotal(hom)); 669 fi; 670 if HasIsSingleValued(hom) then 671 SetIsInjective(mapi, IsSingleValued(hom) ); 672 fi; 673 if HasIsInjective(hom) then 674 SetIsSingleValued(mapi,IsInjective(hom)); 675 fi; 676 SetInverseGeneralMapping( mapi, hom ); 677 return mapi; 678end ); 679 680InstallMethod( InverseGeneralMapping, "for bijective GHBI", true, 681 [ IsGroupGeneralMappingByImages and IsBijective ], 0, 682function( hom ) 683local mapi; 684 mapi:=MappingGeneratorsImages(hom); 685 mapi:=GroupHomomorphismByImagesNC( Range( hom ), Source( hom ), 686 mapi[2], mapi[1]); 687 SetIsBijective( mapi, true ); 688 return mapi; 689end ); 690 691############################################################################# 692## 693#M RestrictedInverseGeneralMapping( <hom> ) .. . . . . . . . . . for GHBI 694## 695InstallMethod( RestrictedInverseGeneralMapping, "via generators/images", true, 696 [ IsGroupGeneralMapping ], 0, 697function( hom ) 698local mapi; 699 mapi:=MappingGeneratorsImages(hom); 700 mapi:=GroupGeneralMappingByImagesNC( Image( hom ), Source( hom ), 701 mapi[2], mapi[1]:noassert ); 702 SetIsTotal(mapi,true); 703 if HasIsTotal(hom) then 704 SetIsSurjective(mapi, IsTotal(hom)); 705 fi; 706 if HasIsSingleValued(hom) then 707 SetIsInjective(mapi, IsSingleValued(hom) ); 708 fi; 709 if HasIsInjective(hom) then 710 SetIsSingleValued(mapi,IsInjective(hom)); 711 fi; 712 SetRestrictedInverseGeneralMapping( mapi, hom ); 713 return mapi; 714end ); 715 716InstallMethod( RestrictedInverseGeneralMapping, "for surjective GHBI", true, 717 [ IsGroupGeneralMappingByImages and IsSurjective ], 0, 718 InverseGeneralMapping); 719 720InstallMethod( RestrictedInverseGeneralMapping, "inverse exists", true, 721 [ IsGroupGeneralMappingByImages and HasInverseGeneralMapping ], 0, 722function(hom) 723 if IsTotal(InverseGeneralMapping(hom)) then 724 return InverseGeneralMapping(hom); 725 else 726 TryNextMethod(); 727 fi; 728end); 729 730 731############################################################################# 732## 733#F MakeMapping( <hom> ) . . . . . . . . . . . . . . . . . . . . . for GHBI 734## 735InstallGlobalFunction( MakeMapping, function( hom ) 736 local elms, # elements of subgroup of '<hom>.source' 737 elmr, # representatives of <elms> in '<hom>.elements' 738 homelms,homimgs, # intermediate storage 739 imgs, # elements of subgroup of '<hom>.range' 740 imgr, # representatives of <imgs> in '<hom>.images' 741 rep, # one new element of <elmr> or <imgr> 742 mapi, # generators and images 743 i, j, k; # loop variables 744 745 if HasIsFinite(Source(hom)) and not IsFinite(Source(hom)) then 746 Error("cannot enumerate an infinite domain"); 747 fi; 748 # if necessary compute the mapping with a Dimino algorithm 749 if not IsBound( hom!.elements ) then 750 751 homelms := [ One( Source( hom ) ) ]; 752 homimgs := [ One( Range ( hom ) ) ]; 753 mapi:=MappingGeneratorsImages(hom); 754 for i in [ 1 .. Length( mapi[1] ) ] do 755 elms := ShallowCopy( homelms ); 756 elmr := [ One( Source( hom ) ) ]; 757 imgs := ShallowCopy( homimgs ); 758 imgr := [ One( Range( hom ) ) ]; 759 j := 1; 760 while j <= Length( elmr ) do 761 for k in [ 1 .. i ] do 762 rep := elmr[j] * mapi[1][k]; 763 if not rep in homelms then 764 Append( homelms, elms * rep ); 765 Add( elmr, rep ); 766 rep := imgr[j] * mapi[2][k]; 767 Append( homimgs, imgs * rep ); 768 Add( imgr, rep ); 769 fi; 770 od; 771 j := j + 1; 772 od; 773 SortParallel( homelms, homimgs ); 774 IsSSortedList( homelms ); # give a hint that this is a set 775#T MakeImmutable! 776 od; 777 hom!.elements:=homelms; 778 hom!.images:=homimgs; 779 fi; 780end ); 781 782############################################################################# 783## 784#M CoKernelOfMultiplicativeGeneralMapping( <hom> ) . . . . . . . . for GHBI 785## 786InstallMethod( CoKernelOfMultiplicativeGeneralMapping, "for GHBI", true, 787 [ IsGroupGeneralMappingByImages ], 0, 788 function( hom ) 789 local C, # co kernel of <hom>, result 790 gen, # one generator of <C> 791 mapi, # generators/images 792 i, k; # loop variables 793 794 # make sure we have the mapping 795 if not IsBound( hom!.elements ) then 796 MakeMapping( hom ); 797 fi; 798 mapi:=MappingGeneratorsImages(hom); 799 800 # start with the trivial co kernel 801 C := TrivialSubgroup( Range( hom ) ); 802 803 # for each element of the source and each generator of the source 804 for i in [ 1 .. Length( hom!.elements ) ] do 805 for k in [ 1 .. Length( mapi[1] ) ] do 806 807 # the co kernel must contain the corresponding Schreier generator 808 gen := hom!.images[i] * mapi[2][k] 809 / hom!.images[ Position( hom!.elements, 810 hom!.elements[i]*mapi[1][k])]; 811 #NC is safe 812 C := ClosureSubgroupNC( C, gen ); 813 814 od; 815 od; 816 817 # return the co kernel 818 return C; 819end ); 820 821############################################################################# 822## 823#M KernelOfMultiplicativeGeneralMapping( <hom> ) . . . . . . . . . for GHBI 824## 825InstallMethod( KernelOfMultiplicativeGeneralMapping, 826 "for GHBI", 827 true, 828 [ IsGroupGeneralMappingByImages ], 0, 829 hom -> CoKernelOfMultiplicativeGeneralMapping( 830 RestrictedInverseGeneralMapping( hom ) ) ); 831 832############################################################################# 833## 834#M IsInjective( <hom> ) . . . . . . . . . . . . . . . . . . . . . for GHBI 835## 836InstallMethod( IsInjective, 837 "for GHBI", 838 true, 839 [ IsGroupGeneralMappingByImages ], 0, 840 hom -> IsSingleValued( RestrictedInverseGeneralMapping( hom ) ) ); 841 842############################################################################# 843## 844#F ImagesRepresentativeGMBIByElementsList( <hom>, <elm> ) 845## 846InstallGlobalFunction( ImagesRepresentativeGMBIByElementsList, 847function( hom, elm ) 848local p,mapi; 849 if not IsBound( hom!.elements ) then 850 mapi:=MappingGeneratorsImages(hom); 851 # catch a few trivial cases 852 if Length(mapi[1])>0 then 853 if CanEasilyCompareElements(mapi[1][1]) then 854 p:=Position(mapi[1],elm); 855 if p<>fail then 856 return mapi[2][p]; 857 fi; 858 else 859 p:=PositionProperty(mapi[1],i->IsIdenticalObj(i,elm)); 860 if p<>fail then 861 return mapi[2][p]; 862 fi; 863 fi; 864 fi; 865 866 MakeMapping( hom ); 867 fi; 868 p := Position( hom!.elements, elm ); 869 if p <> fail then return hom!.images[ p ]; 870 else return fail; fi; 871end ); 872 873############################################################################# 874## 875#M ImagesRepresentative( <hom>, <elm> ) . . . . . . . . . . . . . for GHBI 876## 877InstallMethod( ImagesRepresentative, 878 "parallel enumeration of source and range", 879 FamSourceEqFamElm, 880 [ IsGroupGeneralMappingByImages, 881 IsMultiplicativeElementWithInverse ], 0, 882 ImagesRepresentativeGMBIByElementsList); 883 884############################################################################# 885## 886#M PreImagesRepresentative( <hom>, <elm> ) . . . . . . . . . . . . for GHBI 887## 888InstallMethod( PreImagesRepresentative, 889 "for GHBI and mult.-elm.-with-inverse", 890 FamRangeEqFamElm, 891 [ IsGroupGeneralMappingByImages, 892 IsMultiplicativeElementWithInverse ], 0, 893 function( hom, elm ) 894 if IsBound( hom!.images ) and elm in hom!.images then 895 return hom!.elements[ Position( hom!.images, elm ) ]; 896 else 897 return ImagesRepresentative( RestrictedInverseGeneralMapping( hom ), elm ); 898 fi; 899end ); 900 901 902############################################################################# 903## 904#M ViewObj( <hom> ) . . . . . . . . . . . . . . . . . . . . . . . for GHBI 905## 906InstallMethod( ViewObj, "for GHBI", true, 907 [ IsGroupGeneralMappingByImages ], 0, 908function( hom ) 909local mapi; 910 mapi:=MappingGeneratorsImages(hom); 911 View(mapi[1]); 912 Print(" -> "); 913 View(mapi[2]); 914end ); 915 916############################################################################# 917## 918#M String( <hom> ) . . . . . . . . . . . . . . . . . . . . . . . for GHBI 919## 920InstallMethod( String, "for GHBI", true, 921 [ IsGroupGeneralMappingByImages ], 0, 922function( hom ) 923local mapi; 924 mapi:=MappingGeneratorsImages(hom); 925 return Concatenation(String(mapi[1])," -> ",String(mapi[2])); 926end ); 927 928 929############################################################################# 930## 931#M PrintObj( <hom> ) . . . . . . . . . . . . . . . . . . . . . . . for GHBI 932## 933InstallMethod( PrintObj, "for group general mapping b.i.", true, 934 [ IsGroupGeneralMappingByImages ], 0, 935function( hom ) 936local mapi; 937 mapi:=MappingGeneratorsImages(hom); 938 Print( "GroupGeneralMappingByImages( ", 939 Source( hom ), ", ", Range( hom ), ", ", 940 mapi[1], ", ", mapi[2], " )" ); 941end ); 942 943InstallMethod( PrintObj, "for GHBI", true, 944 [ IsGroupGeneralMappingByImages and IsMapping ], 0, 945function( hom ) 946local mapi; 947 mapi:=MappingGeneratorsImages(hom); 948 Print( "GroupHomomorphismByImages( ", 949 Source( hom ), ", ", Range( hom ), ", ", 950 mapi[1], ", ", mapi[2], " )" ); 951end ); 952 953 954############################################################################# 955## 956## 3. Functions for conjugation action 957## 958 959############################################################################# 960## 961#M ConjugatorOfConjugatorIsomorphism(<hom>) 962## 963InstallOtherMethod(ConjugatorOfConjugatorIsomorphism, 964 "default -- try RepresentativeAction",true, 965 [IsGroupHomomorphism and IsConjugatorIsomorphism],0, 966function(hom) 967local gi,x,p; 968 gi:=MappingGeneratorsImages(hom); 969 p:=Parent(Source(hom)); 970 # in the case of permutation group there is the natural parent S_n which 971 # is used by `IsConjugatorIsomorphism'. 972 if IsPermGroup(p) then 973 p:=SymmetricGroup(MovedPoints(p)); 974 fi; 975 x:=RepresentativeAction(p,gi[1],gi[2],OnTuples); 976 if x=fail then TryNextMethod();fi; 977 return x; 978end); 979 980 981############################################################################# 982## 983#M ConjugatorIsomorphism( <G>, <g> ) 984## 985InstallMethod( ConjugatorIsomorphism, 986 "for group and mult.-elm.-with-inverse", 987 IsCollsElms, 988 [ IsGroup, IsMultiplicativeElementWithInverse ], 0, 989 function( G, g ) 990 local fam, hom; 991 992 fam:= ElementsFamily( FamilyObj( G ) ); 993 hom:= Objectify( NewType( GeneralMappingsFamily( fam, fam ), 994 IsConjugatorIsomorphism 995 and IsSPGeneralMapping 996 and IsAttributeStoringRep ), 997 rec() ); 998 SetConjugatorOfConjugatorIsomorphism( hom, g ); 999 SetSource( hom, G ); 1000 SetRange( hom, ConjugateGroup( G, g ) ); 1001 return hom; 1002 end ); 1003 1004 1005############################################################################# 1006## 1007#M ConjugatorAutomorphismNC( <G>, <g> ) 1008## 1009InstallMethod( ConjugatorAutomorphismNC, 1010 "group and mult.-elm.-with-inverse", 1011 IsCollsElms, 1012 [ IsGroup, IsMultiplicativeElementWithInverse ], 0, 1013 function( G, g ) 1014 local fam, hom; 1015 1016 fam:= ElementsFamily( FamilyObj( G ) ); 1017 hom:= Objectify( NewType( GeneralMappingsFamily( fam, fam ), 1018 IsConjugatorAutomorphism 1019 and IsSPGeneralMapping 1020 and IsAttributeStoringRep ), 1021 rec() ); 1022 SetConjugatorOfConjugatorIsomorphism( hom, g ); 1023 SetSource( hom, G ); 1024 SetRange( hom, G ); 1025 return hom; 1026 end ); 1027 1028 1029############################################################################# 1030## 1031#F ConjugatorAutomorphism( <G>, <g> ) 1032## 1033InstallGlobalFunction( ConjugatorAutomorphism, function( G, g ) 1034local rep; 1035 if IsCollsElms( FamilyObj( G ), FamilyObj( g ) ) 1036 and IsNormal( Group( g ), G ) then 1037 # ensure that g is chosen in G if possible 1038 if not g in G then 1039 rep:=RepresentativeAction(G,GeneratorsOfGroup(G), 1040 List(GeneratorsOfGroup(G),x->x^g),OnTuples); 1041 if rep<>fail then 1042 Info(InfoPerformance,2,"changed conjugator to make it inner"); 1043 g:=rep; 1044 fi; 1045 fi; 1046 return ConjugatorAutomorphismNC( G, g ); 1047 else 1048 return fail; 1049 fi; 1050end ); 1051 1052 1053############################################################################# 1054## 1055#M InnerAutomorphismNC( <G>, <g> ) . . . . . . . . . . . inner automorphism 1056## 1057InstallMethod( InnerAutomorphismNC, 1058 "for group and mult.-elm.-with-inverse", 1059 IsCollsElms, 1060 [ IsGroup, IsMultiplicativeElementWithInverse ], 0, 1061 function( G, g ) 1062 local hom; 1063 hom:= ConjugatorAutomorphismNC( G, g ); 1064 SetIsInnerAutomorphism( hom, true ); 1065 return hom; 1066 end ); 1067 1068 1069############################################################################# 1070## 1071#F InnerAutomorphism( <G>, <g> ) 1072## 1073InstallGlobalFunction( InnerAutomorphism, function( G, g ) 1074 if g in G then 1075 return InnerAutomorphismNC( G, g ); 1076 else 1077 return fail; 1078 fi; 1079end ); 1080 1081 1082############################################################################# 1083## 1084#M MappingGeneratorsImages( <hom> ) . . . for conjugator isomorphism 1085## 1086InstallMethod( MappingGeneratorsImages, 1087 "for conjugator isomorphism", true, [ IsConjugatorIsomorphism ], 0, 1088function( hom ) 1089local gens; 1090 gens:= GeneratorsOfGroup( Source(hom) ); 1091 return [gens,OnTuples( gens, ConjugatorOfConjugatorIsomorphism( hom ) )]; 1092end ); 1093 1094############################################################################# 1095## 1096#M AsGroupGeneralMappingByImages( <hom> ) . . . for conjugator isomorphism 1097## 1098InstallMethod( AsGroupGeneralMappingByImages, 1099 "for conjugator isomorphism", true, [ IsConjugatorIsomorphism ], 0, 1100function( hom ) 1101 local G, gens, map; 1102 1103 G:= Source( hom ); 1104 gens:= GeneratorsOfGroup( G ); 1105 map:= GroupHomomorphismByImagesNC( G, Range( hom ), gens, 1106 OnTuples( gens, ConjugatorOfConjugatorIsomorphism( hom ) ) ); 1107 SetIsBijective( map, true ); 1108 return map; 1109end ); 1110 1111 1112############################################################################# 1113## 1114#M InverseGeneralMapping( <hom> ) . . . . . . . for conjugator isomorphism 1115## 1116InstallMethod( InverseGeneralMapping, 1117 "for conjugator isomorphism", 1118 true, 1119 [ IsConjugatorIsomorphism ], 0, 1120 hom -> ConjugatorIsomorphism( Range( hom ), 1121 Inverse( ConjugatorOfConjugatorIsomorphism( hom ) ) ) ); 1122 1123 1124############################################################################# 1125## 1126#M InverseGeneralMapping( <hom> ) . . . . . . . for conjugator automorphism 1127## 1128InstallMethod( InverseGeneralMapping, 1129 "for conjugator automorphism", 1130 true, 1131 [ IsConjugatorAutomorphism ], 0, 1132 hom -> ConjugatorAutomorphismNC( Range( hom ), 1133 Inverse( ConjugatorOfConjugatorIsomorphism( hom ) ) ) ); 1134 1135 1136############################################################################# 1137## 1138#M InverseGeneralMapping( <inn> ) . . . . . . . . . for inner automorphism 1139## 1140InstallMethod( InverseGeneralMapping, 1141 "for inner automorphism", 1142 true, 1143 [ IsInnerAutomorphism ], 0, 1144 inn -> InnerAutomorphismNC( Source( inn ), 1145 Inverse( ConjugatorOfConjugatorIsomorphism( inn ) ) ) ); 1146 1147 1148############################################################################# 1149## 1150#M CompositionMapping2( <hom1>, <hom2> ) . . for two conjugator isomorphisms 1151## 1152InstallMethod( CompositionMapping2, 1153 "for two conjugator isomorphisms", 1154 true, 1155 [ IsConjugatorIsomorphism, IsConjugatorIsomorphism ], 0, 1156 function( hom1, hom2 ) 1157 if not IsIdenticalObj( Source( hom1 ), Range( hom2 ) ) then 1158 TryNextMethod(); 1159 fi; 1160 return ConjugatorIsomorphism( Source( hom2 ), 1161 ConjugatorOfConjugatorIsomorphism( hom2 ) 1162 * ConjugatorOfConjugatorIsomorphism( hom1 ) ); 1163 end ); 1164 1165 1166############################################################################# 1167## 1168#M CompositionMapping2( <aut1>, <aut2> ) . for two conjugator automorphisms 1169## 1170InstallMethod( CompositionMapping2, 1171 "for two conjugator automorphisms", 1172 true, 1173 [ IsConjugatorAutomorphism, IsConjugatorAutomorphism ], 0, 1174 function( aut1, aut2 ) 1175 if not IsIdenticalObj( Source( aut1 ), Range( aut2 ) ) then 1176 TryNextMethod(); 1177 fi; 1178 return ConjugatorAutomorphismNC( Source( aut2 ), 1179 ConjugatorOfConjugatorIsomorphism( aut2 ) 1180 * ConjugatorOfConjugatorIsomorphism( aut1 ) ); 1181 end ); 1182 1183 1184############################################################################# 1185## 1186#M CompositionMapping2( <inn1>, <inn2> ) . . . . for two inner automorphisms 1187## 1188InstallMethod( CompositionMapping2, 1189 "for two inner automorphisms", 1190 IsIdenticalObj, 1191 [ IsInnerAutomorphism, IsInnerAutomorphism ], 0, 1192 function( inn1, inn2 ) 1193 if not IsIdenticalObj( Source( inn1 ), Source( inn2 ) ) then 1194 TryNextMethod(); 1195 fi; 1196 return InnerAutomorphismNC( Source( inn1 ), 1197 ConjugatorOfConjugatorIsomorphism( inn2 ) 1198 * ConjugatorOfConjugatorIsomorphism( inn1 ) ); 1199 end ); 1200 1201 1202############################################################################# 1203## 1204#M ImagesRepresentative( <hom>, <g> ) . . . . . for conjugator isomorphism 1205## 1206InstallMethod( ImagesRepresentative, 1207 "for conjugator isomorphism", 1208 FamSourceEqFamElm, 1209 [ IsConjugatorIsomorphism, IsMultiplicativeElementWithInverse ], 0, 1210 function( hom, g ) 1211 return g ^ ConjugatorOfConjugatorIsomorphism( hom ); 1212 end ); 1213 1214 1215############################################################################# 1216## 1217#M ImagesSet( <hom>, <U> ) . . . . . . . . . . . for conjugator isomorphism 1218## 1219InstallMethod( ImagesSet, 1220 "for conjugator isomorphism, and group", 1221 CollFamSourceEqFamElms, 1222 [ IsConjugatorIsomorphism, IsGroup ], 0, 1223 function( hom, U ) 1224 return U ^ ConjugatorOfConjugatorIsomorphism( hom ); 1225 end ); 1226 1227 1228############################################################################# 1229## 1230#M PreImagesRepresentative( <hom>, <g> ) . . . . for conjugator isomorphism 1231## 1232InstallMethod( PreImagesRepresentative, 1233 "for conjugator isomorphism", 1234 FamRangeEqFamElm, 1235 [ IsConjugatorIsomorphism, IsMultiplicativeElementWithInverse ], 0, 1236 function( hom, g ) 1237 return g ^ ( ConjugatorOfConjugatorIsomorphism( hom ) ^ -1 ); 1238 end ); 1239 1240 1241############################################################################# 1242## 1243#M PreImagesSet( <hom>, <U> ) . . . . . . . . . for conjugator isomorphism 1244## 1245InstallMethod( PreImagesSet, 1246 "for conjugator isomorphism, and group", 1247 CollFamRangeEqFamElms, 1248 [ IsConjugatorIsomorphism, IsGroup ], 0, 1249 function( hom, U ) 1250 return U ^ ( ConjugatorOfConjugatorIsomorphism( hom ) ^ -1 ); 1251 end ); 1252 1253 1254############################################################################# 1255## 1256#M ViewObj( <hom> ) . . . . . . . . . . . . . . for conjugator isomorphism 1257## 1258InstallMethod( ViewObj, "for conjugator isomorphism", 1259 true, [ IsConjugatorIsomorphism ], 0, 1260function( hom ) 1261 Print("^"); 1262 View( ConjugatorOfConjugatorIsomorphism( hom ) ); 1263end ); 1264 1265############################################################################# 1266## 1267#M String( <hom> ) . . . . . . . . . . . . . . for conjugator isomorphism 1268## 1269InstallMethod( String, "for conjugator isomorphism", 1270 true, [ IsConjugatorIsomorphism ], 0, 1271function( hom ) 1272 return Concatenation("^",String(ConjugatorOfConjugatorIsomorphism( hom ) )); 1273end ); 1274 1275 1276############################################################################# 1277## 1278#M PrintObj( <hom> ) . . . . . . . . . . . . . . for conjugator isomorphism 1279## 1280InstallMethod( PrintObj, 1281 "for conjugator isomorphism", 1282 true, 1283 [ IsConjugatorIsomorphism ], 0, 1284 function( hom ) 1285 if IsIdenticalObj( Source( hom ), Range( hom ) ) then 1286 Print( "ConjugatorAutomorphism( ", Source( hom), ", ", 1287 ConjugatorOfConjugatorIsomorphism( hom ), " )" ); 1288 else 1289 Print( "ConjugatorIsomorphism( ", Source( hom ), ", ", 1290 ConjugatorOfConjugatorIsomorphism( hom ), " )" ); 1291 fi; 1292 end ); 1293 1294 1295############################################################################# 1296## 1297#M PrintObj( <inn> ) . . . . . . . . . . . . . . . . for inner automorphism 1298## 1299InstallMethod( PrintObj, 1300 "for inner automorphism", 1301 true, 1302 [ IsInnerAutomorphism ], 0, 1303 function( inn ) 1304 Print( "InnerAutomorphism( ", Source( inn ), ", ", 1305 ConjugatorOfConjugatorIsomorphism( inn ), " )" ); 1306 end ); 1307 1308 1309############################################################################# 1310## 1311#M IsConjugatorIsomorphism( <hom> ) 1312## 1313## There are methods of higher rank for special kinds of groups. 1314## The default method can only check whether <hom> is an inner automorphism, 1315## and whether some necessary conditions are satisfied. 1316## 1317InstallMethod( IsConjugatorIsomorphism, 1318 "for a group general mapping", 1319 true, 1320 [ IsGroupGeneralMapping ], 0, 1321 function( hom ) 1322 if not ( IsBijective( hom ) and IsGroupHomomorphism( hom ) ) then 1323 return false; 1324 elif IsEndoGeneralMapping( hom ) and IsInnerAutomorphism( hom ) then 1325 return true; 1326 else 1327 TryNextMethod(); 1328 fi; 1329 end ); 1330 1331 1332############################################################################# 1333## 1334#M IsInnerAutomorphism( <hom> ) 1335## 1336InstallMethod( IsInnerAutomorphism, 1337 "for a group general mapping", 1338 true, 1339 [ IsGroupGeneralMapping ], 0, 1340 function( hom ) 1341 local s, gens, rep; 1342 if not ( IsEndoGeneralMapping( hom ) and IsBijective( hom ) 1343 and IsGroupHomomorphism( hom ) ) then 1344 return false; 1345 fi; 1346 s:= Source( hom ); 1347 gens:= GeneratorsOfGroup( s ); 1348 if HasConjugatorOfConjugatorIsomorphism(hom) then 1349 rep:=ConjugatorOfConjugatorIsomorphism(hom); 1350 return rep in s; 1351 else 1352 rep:= RepresentativeAction( s, gens, 1353 List( gens, i -> ImagesRepresentative( hom, i ) ), OnTuples ); 1354 if rep <> fail then 1355 SetConjugatorOfConjugatorIsomorphism( hom, rep ); 1356 return true; 1357 else 1358 return false; 1359 fi; 1360 fi; 1361 end ); 1362 1363 1364############################################################################# 1365## 1366## 4. Functions for ... 1367## 1368 1369 1370############################################################################# 1371## 1372#M NaturalHomomorphismByNormalSubgroup( <G>, <N> ) check whether N \unlhd G? 1373## 1374InstallGlobalFunction( NaturalHomomorphismByNormalSubgroup, function(G,N) 1375 if not (IsSubgroup(G,N) and IsNormal(G,N)) then 1376 Error("<N> must be a normal subgroup of <G>"); 1377 fi; 1378 return NaturalHomomorphismByNormalSubgroupNC(G,N); 1379end ); 1380 1381InstallMethod( NaturalHomomorphismByNormalSubgroupOp, 1382 "for group, and trivial group (delegate to `IdentityMapping')", 1383 IsIdenticalObj, [ IsGroup, IsGroup and IsTrivial ], 1384 SUM_FLAGS, # better than everything else 1385function( G, T ) 1386 return IdentityMapping( G ); 1387end ); 1388 1389############################################################################# 1390## 1391#M IsomorphismPermGroup( <G> ) . . . . . . . . . by right regular operation 1392## 1393InstallMethod( IsomorphismPermGroup, 1394 "right regular operation", 1395 [ IsGroup and IsFinite ], 1396function ( G ) 1397 if not HasIsAbelian( G ) and IsAbelian( G ) then 1398 # Redispatch to give the special methods for abelian groups a chance. 1399 return IsomorphismPermGroup( G ); 1400 # MH: Disabled the following code for now, as computing IsNilpotentGroup 1401 # can be very expensive, depending on the group type. We could 1402 # re-enable it for e.g. pc groups, but I am not sure whether it is 1403 # worth the hassle. 1404# elif not HasIsNilpotentGroup(G) and IsNilpotentGroup(G) then 1405# # Redispatch to give the special methods for nilpotents groups a chance. 1406# return IsomorphismPermGroup( G ); 1407 fi; 1408 return RegularActionHomomorphism( G ); 1409end ); 1410 1411# Since permutation groups are finite, IsomorphismPermGroup can only 1412# work for finite groups. In order to allow IsomorphismPermGroup 1413# methods to assume that they are invoked with a finite group, we 1414# redispatch upon that condition. 1415RedispatchOnCondition(IsomorphismPermGroup,true,[IsGroup],[IsFinite],0); 1416 1417 1418############################################################################# 1419## 1420## The following function computes a compact permutation or pc representation 1421## for an abelian group using IndependentGeneratorsOfAbelianGroup and 1422## IndependentGeneratorExponents. 1423## 1424## Since the default method for IndependentGeneratorsOfAbelianGroup uses 1425## IsomorphismPermGroup, we must take care to not end up in an infinite 1426## loop. In particular, we cannot just install this method for all 1427## abelian groups, but rather only for those which can easily compute 1428## IndependentGeneratorsOfAbelianGroup and IndependentGeneratorExponents. 1429## 1430## For the computed isomorphism to be effectively computable, the source 1431## group should be in either the filter KnowsHowToDecompose or the filter 1432## CanEasilyComputeWithIndependentGensAbelianGroup. 1433BindGlobal( "IsomorphismAbelianGroupViaIndependentGenerators", function ( filter, G ) 1434 local gens, imgs, off, i, n, g, K, inv, nice; 1435 1436 if IsTrivial( G ) then 1437 K := TrivialGroup( filter ); 1438 nice := GroupHomomorphismByImagesNC( G, K, [], [] ); 1439 SetIsBijective( nice, true ); 1440 return nice; 1441 fi; 1442 1443 gens := IndependentGeneratorsOfAbelianGroup( G ); 1444 K := AbelianGroup( filter, AbelianInvariants( G ) ); 1445 UseIsomorphismRelation( G, K ); 1446 imgs := IndependentGeneratorsOfAbelianGroup( K ); 1447 if List(gens,Order) <> List(imgs,Order) then 1448 Error("IndependentGeneratorsOfAbelianGroup results inconsistent"); 1449 fi; 1450 1451 # Construct the isomorphism. 1452 if KnowsHowToDecompose( G ) then 1453 # G knows how decompose elements in terms of generators, so 1454 # we can use a simple GHBI. 1455 nice := GroupHomomorphismByImagesNC( G, K, gens, imgs ); 1456 else 1457 # G does not know how to decompose elements in general. So we 1458 # assume that IndependentGeneratorExponents works effectively, 1459 # and use it to construct a homomorphism. 1460 nice := GroupHomomorphismByFunction( G, K, function ( g ) 1461 local exps; 1462 exps := IndependentGeneratorExponents( G, g ); 1463 return Product( List( [ 1..Length(exps) ], 1464 i -> imgs[i]^exps[i] ) ); 1465 end); 1466 fi; 1467 SetIsBijective( nice, true ); 1468 return nice; 1469end ); 1470 1471# Apply IsomorphismAbelianGroupViaIndependentGenerators if the group can 1472# easily compute independent abelian generators, and decompose using them. 1473InstallMethod( IsomorphismPermGroup, 1474 [ IsGroup and IsFinite and IsAbelian and CanEasilyComputeWithIndependentGensAbelianGroup ], 1475 0, 1476 G -> IsomorphismAbelianGroupViaIndependentGenerators( IsPermGroup, G ) 1477 ); 1478 1479 1480############################################################################# 1481## 1482#M IsomorphismPermGroup( <G> ) . . . . . . . . . for finite nilpotent groups 1483## 1484InstallMethod( IsomorphismPermGroup, "for finite nilpotent groups", true, 1485 [ IsNilpotentGroup and IsFinite and KnowsHowToDecompose ], 0, 1486function ( G ) 1487 local S, isoS, gens, imgs, H, i, phi, g, nice; 1488 1489 if IsAbelian(G) and CanEasilyComputeWithIndependentGensAbelianGroup(G) then 1490 # Use the special method for abelian groups 1491 return IsomorphismAbelianGroupViaIndependentGenerators( IsPermGroup, G ); 1492 fi; 1493 1494 # This method works by exploiting that finite nilpotent groups 1495 # are the direct product of their Sylow subgroups. For p-groups, 1496 # we for now rely on other code (hopefully) providing a good 1497 # way to find a small permutation presentation. 1498 if IsPGroup(G) then 1499 TryNextMethod(); 1500 fi; 1501 1502 # Determine all Sylow subgroups and a permutation presentations for each 1503 S := SylowSystem( G ); 1504 isoS := List( S, IsomorphismPermGroup ); 1505 1506 # Compute isomorphic image H of G from this 1507 H := DirectProduct( List( isoS, ImagesSource ) ); 1508 UseIsomorphismRelation( G, H ); 1509 1510 # Construct the actual isomorphism 1511 gens := []; 1512 imgs := []; 1513 for i in [ 1 .. Length( S ) ] do 1514 phi := isoS[i] * Embedding( H, i ); 1515 for g in GeneratorsOfGroup( S[i] ) do 1516 Add(gens, g); 1517 Add(imgs, ImageElm(phi, g)); 1518 od; 1519 od; 1520 1521 nice := GroupHomomorphismByImagesNC( G, H, gens, imgs ); 1522 SetIsBijective( nice, true ); 1523 return nice; 1524end ); 1525 1526 1527############################################################################# 1528## 1529#M IsomorphismPcGroup( <G> ) . . . . . . . . via permutation representation 1530## 1531InstallMethod( IsomorphismPcGroup, "via permutation representation", true, 1532 [ IsGroup and IsFinite ], 0, 1533function( G ) 1534local p,a; 1535 p:=IsomorphismPermGroup(G); 1536 a:=IsomorphismPcGroup(Image(p)); 1537 if a=fail then 1538 return a; 1539 else 1540 return p*a; 1541 fi; 1542end); 1543 1544# Since pc groups are finite, IsomorphismPcGroup can only work for 1545# finite groups. In order to allow IsomorphismPcGroup methods to assume 1546# that they are invoked with a finite group, we redispatch upon that 1547# condition. 1548RedispatchOnCondition(IsomorphismPcGroup,true,[IsGroup],[IsFinite],0); 1549 1550 1551############################################################################# 1552## 1553#F GroupHomomorphismByFunction( <D>, <E>, <fun> ) 1554#F GroupHomomorphismByFunction( <D>, <E>, <fun>, <invfun> ) 1555## 1556InstallGlobalFunction( GroupHomomorphismByFunction, function ( arg ) 1557local map,type,prefun; 1558 1559 # no inverse function given 1560 if Length(arg) in [3,5] then 1561 type:=IsSPMappingByFunctionRep and IsSingleValued and IsTotal 1562 and IsGroupHomomorphism; 1563 1564 if Length(arg)=5 and IsFunction(arg[5]) then 1565 prefun:=arg[5]; 1566 else 1567 prefun:=fail; 1568 if IsPermGroup(arg[2]) or IsPcGroup(arg[2]) then 1569 type:=type and IsPreimagesByAsGroupGeneralMappingByImages; 1570 fi; 1571 fi; 1572 1573 # make the general mapping 1574 map:= Objectify( 1575 NewType(GeneralMappingsFamily(ElementsFamily(FamilyObj(arg[1])), 1576 ElementsFamily(FamilyObj(arg[2]))),type), 1577 rec( fun:= arg[3] ) ); 1578 if prefun<>fail then 1579 map!.prefun:=arg[5]; 1580 fi; 1581 1582 # inverse function given 1583 elif Length(arg) = 4 then 1584 1585 # make the mapping 1586 map:= Objectify( 1587 NewType(GeneralMappingsFamily(ElementsFamily(FamilyObj(arg[1])), 1588 ElementsFamily(FamilyObj(arg[2]))), 1589 IsSPMappingByFunctionWithInverseRep 1590 and IsBijective 1591 and IsGroupHomomorphism), 1592 rec( fun := arg[3], 1593 invFun := arg[4], 1594 prefun := arg[4]) ); 1595 1596 # otherwise signal an error 1597 else 1598 Error( "usage: GroupHomomorphismByFunction( <D>, <E>, <fun>[, <inv>] )" ); 1599 fi; 1600 1601 SetSource(map,arg[1]); 1602 SetRange(map,arg[2]); 1603 # return the mapping 1604 return map; 1605end ); 1606 1607InstallMethod(RegularActionHomomorphism,"generic",[IsGroup and IsFinite], 1608function(G) 1609local hom; 1610 if HasSize(G) and Size(G) > 10^6 then 1611 Info(InfoWarning, 1, 1612 "Trying regular permutation representation of group of order >10^6"); 1613 fi; 1614 hom:=ActionHomomorphism(G, G, OnRight, "surjective"); 1615 SetIsBijective(hom, true); 1616 # Do not set IsRegular for the range, as the range has not yet been computed 1617 # and we should not needlessly trigger this computation. 1618 # It is comparatively cheap to compute IsRegular anyway. 1619# SetIsRegular(Range(hom), true); 1620 return hom; 1621end); 1622 1623# Since permutation groups are finite, RegularActionHomomorphism can only 1624# work for finite groups. In order to allow RegularActionHomomorphism 1625# methods to assume that they are invoked with a finite group, we 1626# redispatch upon that condition. 1627RedispatchOnCondition(RegularActionHomomorphism,true,[IsGroup],[IsFinite],0); 1628