> < ^ Date: Tue, 15 Apr 1997 00:16:00 +0100 (MET)
> < ^ From: Martin Schoenert <martin.schoenert@math.rwth-aachen.de >
^ Subject: FIX 29 for DANGEROUS bug in GAP/lib 3.4.3.0 'LowIndexSubgroupsFpGroup'

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 'LowIndexSubgroupsFpGroup' when called with a
nontrivial subgroup <H> as second argument, and may cause it to
return more than one representative for some conjugacy classes.

ACKNOWLEDGEMENT

We thank Giovanni Cutolo (University Napoli `Federico II') for bringing
the problem to our attention in a message to 'GAP-Trouble' of 1997/04/09.

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 'fix29lib.dif', and issue the command:

patch -p0 < fix29lib.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

When 'LowIndexSubgroupsFpGroup' is called with a nontrivial subgroup <H>
as second argument, the returned list may contain more than one subgroup
from some conjugacy classes. It always contains the representative,
i.e., the lexicographically earliest subgroup, of each conjugacy class.
If 'LowIndexSubgroupsFpGroup' is called with trivial <H>, the returned
list will not contain any extraneous subgroups.

CORRECT BEHAVIOUR

gap> F := FreeGroup( 2 );;
gap> x := F.1;;  y := F.2;;
gap> r := [ x^3, y^3, Comm(Comm(x,y),x), Comm(Comm(x,y),y) ];;
gap> G := F / List( Combinations(r,2), c -> Comm(c[1],c[2]) );;
gap> a := G.1;;  b := G.2;;
gap> c := Comm( Comm( a, b ), a );;  d := Comm( Comm( a, b ), b );;
gap> H := Subgroup( G, [ a^3, b^3, c, d, c^a, c^b, d^a, d^b,
>                        c^(a*a), c^(a*b), c^(b*b), c^(b*a) ] );;
gap> Us := LowIndexSubgroupsFpGroup( G, H, 9 );;
gap> Collected( List( Us, U -> Index( G, U ) ) );
[ [ 1, 1 ], [ 3, 4 ], [ 9, 5 ] ]

COMMENT

To return only the representative of each conjugacy class,
'LowIndexSubgroupsFpGroup' contains a test that tests for each subgroup
<U> whether it is the representative of its class, i.e., whether <U> has
no lexicographically earlier conjugate <V> that contains <H>.
This test did let some non-representative subgroups <U> pass,
because it failed to find their lexicographically earlier conjugate <V>.
This could happened when 'LowIndexSubgroupsFpGroup' correctly noted that
<V> was lexicographically earlier than <U> but could not yet decide
whether <V> also contained <H>.

DIFFS

Prereq: 3.23.1.12
--- lib/fpgrp.g	Mon Oct 28 22:56:00 1996
+++ lib/fpgrp.g	Thu Apr 10 13:06:37 1997
@@ -2,13 +2,16 @@
 ##
 #A  fpgrp.g                     GAP library                  Martin Schoenert
 ##
-#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 1990-1992,  Lehrstuhl D fuer Mathematik,  RWTH Aachen,  Germany
 ##
 ##  This file contains the  functions dealing with finitely presented groups.
 ##
 #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.5  2003/06/12 19:43:50  gap
 #H  Removed `Jr'. AH
 #H
 #H  Revision 1.4  2003/06/12 19:20:35  gap
 #H  Further update. AH
 #H
 #H  Revision 1.3  2003/06/12 17:28:27  gap
 #H  Address updates by JN. AH
 #H
 #H  Revision 1.2  1998/03/11 15:28:36  gap
 #H  removed 3D's
 #H
 #H  Revision 1.1  1997/08/15 11:19:46  gap
 #H  New forum setup. AH
 #H
+#H  Revision 3.23.1.13  1997/04/10 13:05:02  mschoene
+#H  fixed 'LowIndexSubgroups' for the case that a subgroup is given
+#H
 #H  Revision 3.23.1.12  1996/09/12 13:52:04  mschoene
 #H  fixed handling of abelian invariants
 #H
@@ -2008,6 +2011,7 @@
             cols,
             gen,
             nums,
+            done,
             i, j;       # loop variables
 
     # give some information
@@ -2173,34 +2177,40 @@
 
                 # run through the old and the new table in parallel
                 c := 1;  y := 1;
-                while c <= nrcos  and not coinc  and later[x] = 0  do
+                done := coinc or later[x] <> 0;
+                while c <= nrcos and not done  do

# get the corresponding coset for the new table
d := s[c];

                     # loop over the entries in this row
                     g := 1;
-                    while   g < nrgens
-                        and c <= nrcos  and not coinc  and later[x] = 0  do
+                    while g < nrgens and not done  do
 
-                        # if either entry is missing we cannot decide yet
+                        # if either entry is missing, we cannot decide yet
                         if table[g][c] = 0  or table[g][d] = 0  then
-                            c := nrcos + 1;
+                            done := true;
 
-                        # if old and new both contain a definition
-                        elif r[ table[g][d] ] = 0 and table[g][c] = y+1  then
+                        # if old and new contain defs, extend the renumbering
+                        elif table[g][c] = y+1 and r[ table[g][d] ] = 0  then
                             y := y + 1;
                             r[ table[g][d] ] := y;
                             s[ y ] := table[g][d];
 
-                        # if only new is a definition
+                        # if only new contains a def, old must be earlier
                         elif r[ table[g][d] ] = 0  then
                             later[x] := nract;
+                            done := true;
 
-                        # if new is the smaller one we have a coincidence
+                        # if olds entry is smaller, old must be earlier
+                        elif table[g][c] < r[ table[g][d] ]  then
+                            later[x] := nract;
+                            done := true;
+
+                        # if news entry is smaller, test if new contains sgr
                         elif r[ table[g][d] ] < table[g][c]  then
 
-                            # check that <x> fixes <H>
+                            # test whether <x> fixes <H>
                             coinc := true;
                             for pair in subgroup  do
                                 app[1] := 2;
@@ -2229,9 +2239,7 @@
od;
-                        # if the old is smaller one very good
-                        elif table[g][c] < r[ table[g][d] ]  then
-                            later[x] := nract;
+                            done := true;
fi;
END OF  fix29lib.dif ________________________________________________________

> < [top]