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