> < ^ Date: Thu, 19 Sep 1996 17:10:00 +0100 (MET)
> < ^ From: Martin Schoenert <martin.schoenert@math.rwth-aachen.de >
^ Subject: FIX 24 for DANGEROUS bug in GAP/lib 3.4.3.0 permutation groups

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.dif

If '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 ________________________________________________________

> < [top]