> < ^ From:

^ Subject:

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 ________________________________________________________

> < [top]