> < ^ From:

^ Subject:

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 ________________________________________________________

> < [top]