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