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.
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.
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.
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.
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,c) );; 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 ] ]
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>.
Prereq: 220.127.116.11 --- 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 18.104.22.168 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 22.214.171.124 1997/04/10 13:05:02 mschoene +#H fixed 'LowIndexSubgroups' for the case that a subgroup is given +#H #H Revision 126.96.36.199 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 := 2; @@ -2229,9 +2239,7 @@
- # if the old is smaller one very good - elif table[g][c] < r[ table[g][d] ] then - later[x] := nract; + done := true;
END OF fix29lib.dif ________________________________________________________