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 is in permutation group normalizer, centralizer, stabilizer,
and intersection. They produce correct results, but if one does further
computations with the results, one may get incorrect results.
ACKNOWLEDGEMENT
We thank Erzsebet Horvath (Budapest Technical University) for bringing
the problem to our attention via private communication in September 1996.
VERSION
GAP/lib 3.4.3.0
PRIORITY
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.
HOW TO APPLY
Go to the GAP directory (the directory with the 'lib/' subdirectory),
name this mail 'fix24lib.dif', and issue the command:patch -p0 < fix24lib.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 fix changes only the library.
Thus you need not recompile the GAP kernel.
DESCRIPTION
The results of permutation group normalizer, centralizer, stabilizer,
and intersection computations may have incorrectly small known base
components in their stab chain options records, which may lead to
problems in following computations.gap> g := Group( (1,2,3,4,5), (1,2) );; gap> s := Subgroup( g, [ (1,2,3,4,5) ] );; gap> s.stabChainOptions := rec( knownBase:= [1] );; gap> n := Normalizer( g, s ); Subgroup( Group( (1,2,3,4,5), (1,2) ), [ (1,2,3,4,5), (2,3,5,4) ] ) gap> if IsBound( n.stabChainOptions ) > and IsBound( n.stabChainOptions.knownBase ) > then > Print( "known base = ", n.stabChainOptions.knownBase, "\n" ); > else > Print( "no known base\n" ); > fi; known base = [ 1 ]
CORRECT BEHAVIOUR
gap> g := Group( (1,2,3,4,5), (1,2) );; gap> s := Subgroup( g, [ (1,2,3,4,5) ] );; gap> s.stabChainOptions := rec( knownBase := [ 1 ] );; gap> n := Normalizer( g, s ); Subgroup( Group( (1,2,3,4,5), (1,2) ), [ (1,2,3,4,5), (2,3,5,4) ] ) gap> if IsBound( n.stabChainOptions ) > and IsBound( n.stabChainOptions.knownBase ) > then > Print( "known base = ", n.stabChainOptions.knownBase, "\n" ); > else > Print( "no known base\n" ); > fi; no known base
COMMENT
This fix changes 'StabChain' so that it does not enter a known base
component into the stab chain options record of a group. Of course
the problem really lies in the backtrack functions, which modify
DIFFS
Prereq: 3.13.1.3 --- lib/permstbc.g Thu Dec 21 15:30:34 1995 +++ lib/permstbc.g Tue Sep 17 14:43:14 1996 @@ -3,14 +3,17 @@ #A permstbc.g GAP library Udo Polis #A & Akos Seress ## -#H @(#)$Id: 1.html,v 1.2 2004/04/21 15:06:19 felsch Exp $ +#H @(#)$Id: 1.html,v 1.2 2004/04/21 15:06:19 felsch Exp $ ## #Y Copyright (C) 1994, Lehrstuhl D fuer Mathematik, RWTH Aachen, Germany ## ## This file contains the functions to compute and change stabilizer chains. ## #H $Log: 1.html,v $ #H Revision 1.2 2004/04/21 15:06:19 felsch #H Corrected links in the Forum Archive pages. VF #H #H Revision 1.1.1.1 2004/04/20 13:39:30 felsch #H The final GAP-Forum archive until 2003. #H #H Revision 1.4 2003/06/12 19:20:34 gap #H Further update. AH #H #H Revision 1.3 1997/08/15 11:19:38 gap #H New forum setup. AH #H #H Revision 1.2 1997/04/24 15:33:16 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:07 gap #H added forum archive and translation files. #H -#H Revision 3.13.1.3 1995/04/01 13:39:46 aseress +#H Revision 3.13.1.4 1996/09/17 12:28:56 mschoene +#H changed 'StabChain', it should not enter 'G.stabChainOptions.knownBase' +#H +#H Revision 3.13.1.3 1995/04/01 13:39:46 aseress #H improved 'StabChain' to avoid recomputing the top level #H #H Revision 3.13.1.2 1994/10/11 12:52:22 ahulpke @@ -309,6 +312,7 @@ # call this part only if grp was a permutation group, not a stabChain if IsBound( grp.operations ) then + # for compatibility copy into the group record if IsBound( chain.orbit ) then if IsEqualSet(grp.generators,chain.generators) then @@ -337,20 +341,13 @@ options.random:=Minimum( Parent(grp).stabChainOptions.random, options.random ); fi; - if IsBound(grp.stabChainOptions) then grp.stabChainOptions.random := options.random; else grp.stabChainOptions := rec(random := options.random); fi; fi; - if IsBound(grp.stabChainOptions) then - if not IsBound( grp.stabChainOptions.knownBase ) then - grp.stabChainOptions.knownBase := Base( grp ); - fi; - else - grp.stabChainOptions := rec( knownBase := Base( grp ) ); - fi; + # enter the chain in the group record and return it grp.stabChain := chain; fi; END OF fix24lib.dif ________________________________________________________