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