This mail contains a bugfix for a dangerous problem in GAP 3.4.3.
*You should apply this bugfix as soon as possible.*
The problem happens for multi-valued 'GroupHomomorphismByImages'
from a permutation group to a non-permutation group. It may cause
'Images' to return sets of images that are too small or too large.
It may also cause 'IsMapping' and 'IsHomomorphism' to return 'true'.
HOW TO APPLY
The problem is a dangerous problem, because it may cause a computation
to produce incorrect results without a warning. Thus the bugfix has
high priority, and we recommend that you apply it as soon as possible.Go to the GAP directory (the directory with the 'lib/' subdirectory),
name this mail 'bugfix12.dif', and issue the command:patch -p0 < bugfix12.difIf 'patch' writes "I can't seem to find a patch in there" try 'patch -v'.
If 'patch -v' gives an error message or reports a version older than 2.1,
get 2.1 from 'ftp://FTP.Math.RWTH-Aachen.DE/pub/gap/utils/patch2_1.zoo'.This bugfix changes only the library.
Thus you need not recompile the GAP kernel.
VERSION
GAP 3.4.3.0
DESCRIPTION
If one creates a mapping with 'GroupHomomorphismByImages', that maps
from a permutation group to a non-permutation group, and that is a
multi-valued mapping (i.e., where each image has more than one image),
then GAP may compute an incorrect cokernel (which is the set of images of
the identity), namely one which is too small. This causes 'Images' to
return incorrect sets of images for each element (such a set is a coset
of the cokernel), which are also too small. If GAP incorrectly computes
a trivial cokernel, then 'IsMapping' and 'IsHomomorphism' will
incorrectly return 'true'.If one creates a mapping with 'GroupHomomorphismByImages', that maps from
a permutation group to a non-permutation group, that is a multi-valued
mapping, and that is not surjective, then GAP may compute an incorrect
cokernel, namely one which is too large. This causes 'Images' to return
incorrect sets of images for each element, which are also too large.
COMMENT
There are actually two problems. One causes the computation to return a
cokernel that may be too small, and the other causes the computation to
return a cokernel that may be too large (unfortunately the two bugs do
not cancel each other ;-).`PermGroupHomomorphismByImagesOps.MakeMapping' constructs a stabiliser
chain for the source group (for which the size is known) by the following
method:1. The top level of the chain is constructed, the levels below remain
empty.2. A random element is built from the generators and is sifted down the
chain.3. If it does not sift through, the remainder is used to extend the level
where it ``fell out''.4. Steps 2 and 3 are repeated until the product of the basic orbit
lengths equals the size of the source group.The problem is that elements which are added further down the chain must
also be added to the levels above. They do not move the base point, but
they must be added to the `generators' lists and may extend the basic
orbits. These elements are not added in the incorrect version.The cokernel of a 'GroupHomomorphismByImages' from a permutation group to
a non-permutation group is calculated as the normal closure of images of
relators in the *range* of the map. It should be the normal closure in
the *image* of the map.
CORRECT BEHAVIOUR
gap> G := Group( (2,7)(3,6)(4,5), (1,8)(3,5)(4,6), (1,8)(3,5,6,4) );; gap> H1 := Group( (1,2), (4,10)(5,9)(6,8), (3,4,5,6,7,8,9,10) );; gap> H2 := AgGroup( H1 );; gap> H3 := Subgroup( H2, List( H1.generators, > h -> PreImagesRepresentative(H2.bijection,h) ) );; gap> h := GroupHomomorphismByImages( G, H3, G.generators, H3.generators );; gap> IsHomomorphism( h ); false gap> G := Group( () );; gap> H := Group( [[1,1],[0,1]]*Z(2), [[0,1],[1,0]]*Z(2) );; gap> h := GroupHomomorphismByImages( G, H, [G.identity], [H.1] );; gap> Size( Images( h, G.identity ) ); 2
PATCH
Prereq: 3.22.1.6
--- lib/permhomo.g 1995/12/19 09:27:13
+++ lib/permhomo.g 1996/06/10 13:06:45
@@ -3,13 +3,19 @@
#A permhomo.g GAP library Martin Schoenert
#A & Udo Polis
##
-#A @(#)$Id: 1.html,v 1.2 2004/04/21 15:06:55 felsch Exp $
+#A @(#)$Id: 1.html,v 1.2 2004/04/21 15:06:55 felsch Exp $
##
#Y Copyright 1990-1992, Lehrstuhl D fuer Mathematik, RWTH Aachen, Germany
##
## This file contains functions that implement homomorphisms for permgroups.
##
#H $Log: 1.html,v $
#H Revision 1.2 2004/04/21 15:06:55 felsch
#H Corrected links in the Forum Archive pages. VF
#H
#H Revision 1.1.1.1 2004/04/20 13:39:39 felsch
#H The final GAP-Forum archive until 2003.
#H
#H Revision 1.5 2003/06/12 19:20:33 gap
#H Further update. AH
#H
#H Revision 1.4 2003/06/12 17:28:25 gap
#H Address updates by JN. AH
#H
#H Revision 1.3 1997/08/15 11:19:33 gap
#H New forum setup. AH
#H
#H Revision 1.2 1997/04/24 15:32:47 gap
#H These files were replaced by the versions in WWW. The content is basically the
#H same but the formatting has been much more friendly towards the HTML-Converter.
#H AH
#H
#H Revision 1.1 1996/10/30 13:07:04 gap
#H added forum archive and translation files.
#H
+#H Revision 3.22.1.8 1996/06/10 13:06:45 mschoene
+#H fixed 'PGHBIO.CoKernel', it is a normal subgroup of the image
+#H
+#H Revision 3.22.1.7 1996/06/10 12:39:16 mschoene
+#H fixed 'MakeMapping' to add Schreier generators on all levels
+#H
#H Revision 3.22.1.6 1995/12/19 09:27:13 mschoene
#H fixed 'GHBI' to avoid identities in stabilizer chains
#H
@@ -163,7 +169,7 @@
orb, # orbit
len, # length of the orbit before extension
bpt, # base point
- i, j; # loop variables
+ i, j, S; # loop variables
# handle trivial case
if hom.generators = [] then
@@ -261,39 +267,42 @@
fi;
# divide the size of stabilizer chain by the old orbit length
- size := size / Length( stb.orbit );
-
- # add the element to the generators
- Add( stb.generators, elm );
- Add( stb.genimages, img );
-
- # extend orbit and transversal
- orb := stb.orbit;
- len := Length(orb);
- i := 1;
- while i <= len do
- if not IsBound(stb.transversal[orb[i]/elm]) then
- stb.transversal[orb[i]/elm] := elm;
- stb.transimages[orb[i]/elm] := img;
- Add( orb, orb[i]/elm );
- fi;
- i := i + 1;
- od;
- while i <= Length(orb) do
- for j in [1..Length(stb.generators)] do
- elm := stb.generators[j];
- img := stb.genimages[j];
- if not IsBound(stb.transversal[orb[i]/elm]) then
- stb.transversal[orb[i]/elm] := elm;
- stb.transimages[orb[i]/elm] := img;
+ S := hom;
+ repeat
+ S := S.stabilizer;
+
+ # add the element to the generators
+ Add( S.generators, elm );
+ Add( S.genimages, img );
+
+ # extend orbit and transversal
+ orb := S.orbit;
+ len := Length(orb);
+ size := size / len;
+ i := 1;
+ while i <= len do
+ if not IsBound(S.transversal[orb[i]/elm]) then
+ S.transversal[orb[i]/elm] := elm;
+ S.transimages[orb[i]/elm] := img;
Add( orb, orb[i]/elm );
fi;
+ i := i + 1;
od;
- i := i + 1;
- od;
-
- # multiply the size of stabilizer chain by the new orbit length
- size := size * Length( stb.orbit );
+ while i <= Length(orb) do
+ for j in [1..Length(S.generators)] do
+ elm := S.generators[j];
+ img := S.genimages[j];
+ if not IsBound(S.transversal[orb[i]/elm]) then
+ S.transversal[orb[i]/elm] := elm;
+ S.transimages[orb[i]/elm] := img;
+ Add( orb, orb[i]/elm );
+ fi;
+ od;
+ i := i + 1;
+ od;
+ size := size * Length( orb );
+
+ until S.orbit[ 1 ] = stb.orbit[ 1 ];
fi;
@@ -319,8 +328,12 @@
fi;
# make sure we have a stabilizer chain for <hom>
+ # (for perm->perm homs. this automatically computes the coKernel)
if not IsBound( hom.stabilizer ) then
hom.operations.MakeMapping( hom );
+ if IsBound( hom.coKernel ) then
+ return hom.coKernel;
+ fi;
fi;
# loop over the stabilizer chain
@@ -375,7 +388,7 @@
od;
# return the cokernel
- return AsSubgroup( Parent( C ), NormalClosure( hom.range, C ) );
+ return AsSubgroup( Parent( C ), NormalClosure( hom.image, C ) );
end;
CoKernelGensPermHom := function ( hom ) END OF bugfix12.dif ________________________________________________________