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