This mail contains a bugfix for two dangerous problems in GAP 3.4.3.
Note that bugfix01 already provided a workaround for these problems.
The problems are in 'TzFindCyclicJoins' for presentations of groups,
and may cause 'FpGroup' (when called for subgroups of finitely
presented groups), 'SimplifyPresentation', 'SimplifiedFpGroup', 'TzGo',
and 'TzGoGo' to produce incorrect presentations without a warning.
HOW TO APPLY
Note that bugfix01 already provided a workaround for these problems.
Thus the priority of this bugfix is low.Before applying this bugfix you *must* already have applied bugfix01.
Go to the GAP directory (the directory with the 'lib/' subdirectory),
name this file 'bugfix04.dif', and issue the command:patch -p0 < bugfix04.difThis bugfix changes only the library. Thus you need not recompile the
GAP kernel.
VERSION
GAP 3.4.3.1
DESCRIPTION
'TzFindCyclicJoins', which is is called directly or indirectly from
'FpGroup' (when called for subgroups of finitely presented groups),
'SimplifyPresentation', 'SimplifiedFpGroup', 'TzGo', and 'TzGoGo',
may produce incorrect presentations.
CORRECT BEHAVIOUR
gap> G := FreeGroup( 3 ); Group( f.1, f.2, f.3 ) gap> a := G.generators[1];; gap> b := G.generators[2];; gap> c := G.generators[3];; gap> G.relators := [ > a^7, c^4, > Comm( a,b ), Comm( a,c ), Comm( b,c ), > c * c * a * a * a * c * a ];; gap> gap> P := PresentationFpGroup( G );; gap> SimplifyPresentation( P ); #I there are 3 generators and 6 relators of total length 30 #I there are 2 generators and 4 relators of total length 37 #I there are 1 generator and 0 relators of total length 0 gap> gap> P; << presentation with 1 gens and 0 rels of total length 0 >>
DESCRIPTION
'TzFindCyclicJoins', which is is called directly or indirectly from
'FpGroup' (when called for subgroups of finitely presented groups),
'SimplifyPresentation', 'SimplifiedFpGroup', 'TzGo', and 'TzGoGo',
may signalError: Integer operations: <divisor> must be nonzero.
CORRECT BEHAVIOUR
gap> K := FreeGroup(8); Group( f.1, f.2, f.3, f.4, f.5, f.6, f.7, f.8 ) gap> g1 := K.generators[1];; gap> g2 := K.generators[2];; gap> g3 := K.generators[3];; gap> g4 := K.generators[4];; gap> g5 := K.generators[5];; gap> g6 := K.generators[6];; gap> g7 := K.generators[7];; gap> g8 := K.generators[8];; gap> K.relators := > [ g1^2*g8^-1*g4^-1, g2^2, g3^2, g4^3, g5^3, g6^2*g8^-1, g7^2*g8^-1, g8^2, > g2^-1*g1^-1*g2*g1*g5^-2*g4^-1, g3^-1*g1^-1*g3*g1*g2^-1, g4^-1*g1^-1*g4*g1, > g5^-1*g1^-1*g5*g1*g5^-1, g6^-1*g1^-1*g6*g1, g7^-1*g1^-1*g7*g1*g8^-1, > g8^-1*g1^-1*g8*g1, g3^-1*g2^-1*g3*g2, g4^-1*g2^-1*g4*g2*g4^-1, > g5^-1*g2^-1*g5*g2*g5^-1, g6^-1*g2^-1*g6*g2, g7^-1*g2^-1*g7*g2, > g8^-1*g2^-1*g8*g2, g4^-1*g3^-1*g4*g3*g5^-1*g4^-2, > g5^-1*g3^-1*g5*g3*g5^-2*g4^-1, g6^-1*g3^-1*g6*g3, g7^-1*g3^-1*g7*g3, > g8^-1*g3^-1*g8*g3, g5^-1*g4^-1*g5*g4, g6^-1*g4^-1*g6*g4, g7^-1*g4^-1*g7*g4, > g8^-1*g4^-1*g8*g4, g6^-1*g5^-1*g6*g5, g7^-1*g5^-1*g7*g5, g8^-1*g5^-1*g8*g5, > g7^-1*g6^-1*g7*g6*g8^-1, g8^-1*g6^-1*g8*g6, g8^-1*g7^-1*g8*g7 ];; gap> gap> P := PresentationFpGroup( K );; gap> SimplifyPresentation( P ); #I there are 4 generators and 17 relators of total length 122 #I there are 4 generators and 13 relators of total length 84 #I there are 4 generators and 12 relators of total length 74 gap> gap> P; << presentation with 4 gens and 12 rels of total length 74 >>
COMMENT
This bugfix replaces the faulty function 'TzFindCyclicJoins' by a
corrected one.'TzFindCyclicJoins' has the following purpose. If the presentation being
simplified contains a commutator relator 'Comm(<a>,<b>)' and at least one
power relator of the form '<a>^<n>' or '<b>^<m>', where <a> and <b> are
generators or inverses of generators, then the subroutine searches for
further relators which are words in <a> and <b> and their inverses only,
and then it tries to reduce these relators by applying the Euclidean
algorithm to the occurring exponents.The fact that this bug has been discovered only now in a routine which is
being used since 1993 seems to indicate that it only occurs in rather
rare situations. Unfortunately, however, it is one of those nasty bugs
which may produce wrong results without giving any evidence of that fact.
Therefor we strongly recommend that you implement this bugfix in your
local GAP installation.
PATCH
Prereq: 3.4.1.3 --- lib/fptietze.g 1996/02/16 09:58:00 +++ lib/fptietze.g 1996/03/12 14:03:41 @@ -2,7 +2,7 @@ ## #A fptietze.g GAP library Volkmar Felsch ## -#A @(#)$Id: 1.html,v 1.2 2004/04/21 15:06:18 felsch Exp $ +#A @(#)$Id: 1.html,v 1.2 2004/04/21 15:06:18 felsch Exp $ ## #Y Copyright 1990-1992, Lehrstuhl D fuer Mathematik, RWTH Aachen, Germany ## @@ -10,6 +10,9 @@ ## finitely presented groups. ## #H $Log: 1.html,v $ #H Revision 1.2 2004/04/21 15:06:18 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.6 2003/06/12 19:20:33 gap #H Further update. AH #H #H Revision 1.5 2003/06/12 17:28:25 gap #H Address updates by JN. AH #H #H Revision 1.4 1999/03/18 10:17:42 gap #H Fixed a mail that was corrupted in the files stemming from Martin. #H #H Revision 1.3 1997/08/15 11:19:30 gap #H New forum setup. AH #H #H Revision 1.2 1997/04/24 15:32:10 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:02 gap #H added forum archive and translation files. #H +#H Revision 3.4.1.4 1996/03/12 14:03:41 vfelsch +#H corrected bugs in TzFindCyclicJoins +#H #H Revision 3.4.1.3 1996/02/16 09:58:00 vfelsch #H commented out the call of TzFindCyclicJoins which contains a bug #H @@ -1137,9 +1140,9 @@ ## TzFindCyclicJoins := function ( T )
- local e, exp, exponents, fac, flags, gen, gens, i, invs, j, k, l, length,
- lengths, n, next, num, numgens, numrels, ggt, rel, rels, T, tietze,
- word;
+ local e, exp, exponents, fac, flags, gen, gens, ggt, i, invs, j, k, l,
+ length, lengths, n, newstart, next, num, numgens, numrels, prev,
+ powers, rel, rels, T, tietze, word;
if T.printLevel >= 3 then
Print( "#I searching for cyclic joins\n" );
@@ -1147,117 +1150,142 @@
# check the given argument to be a Tietze record.
TzCheckRecord( T );
-
- # Try to find exponents for the generators.
- exponents := TzGeneratorExponents( T );
tietze := T.tietze;
tietze[TZ_MODIFIED] := false;
- if Sum( exponents ) = 0 then return; fi;
-
- # initialize some local variables.
- gens := tietze[TZ_GENERATORS];
- numgens := tietze[TZ_NUMGENS];
- rels := tietze[TZ_RELATORS];
- numrels := tietze[TZ_NUMRELS];
- lengths := tietze[TZ_LENGTHS];
- invs := tietze[TZ_INVERSES];
- flags := tietze[TZ_FLAGS];
-
- # Now work off all commutator relators of length 4.
- i := 1;
- while i <= numrels do
+ # start the routine and repeat it whenever a generator has been
+ # eliminated.
+ newstart := true;
+ while newstart do
+
+ # try to find exponents for the generators.
+ exponents := TzGeneratorExponents( T );
+ if Sum( exponents ) = 0 then return; fi;
+
+ # initialize some local variables.
+ newstart := false;
+ gens := tietze[TZ_GENERATORS];
+ numgens := tietze[TZ_NUMGENS];
+ rels := tietze[TZ_RELATORS];
+ numrels := tietze[TZ_NUMRELS];
+ lengths := tietze[TZ_LENGTHS];
+ invs := tietze[TZ_INVERSES];
+ flags := tietze[TZ_FLAGS];
+
+ # now work off all commutator relators of length 4.
+ i := 0;
+ while i < numrels do
+ # find the next commutator.
+ i := i + 1;
rel := rels[i];
if lengths[i] = 4 and rel[1] = invs[numgens+1+rel[3]] and
- rel[2] = invs[numgens+1+rel[4]] then
-
- # There is a commutator relator of the form [a,b]. Check if
- # there are also power relators of the form a^m or b^n.
+ rel[2] = invs[numgens+1+rel[4]] then
- num := [ AbsInt( rel[1] ), AbsInt( rel[2] ) ];
- exp := [ exponents[num[1]], exponents[num[2]] ];
+ # There is a commutator relator of the form [a,b]. Check if
+ # there are also power relators of the form a^m or b^n.
- # If there is at least one relator of the form a^m or b^n, then
- # search for a relator of the form a^s * b^t (modulo [a,b])
- # with s prime to m or t prime to n, respectively. For, if s is
- # prime to m, then we can use the Euclidian algorithm to
- # express a as a power of b and then eliminate a.
-
- if exp[1] > 0 or exp[2] > 0 then
-
- j := 0; while j < numrels do
- j := j + 1;
- if lengths[j] > 0 and j <> i then
- rel := rels[j];
- length := lengths[j];
- e := [0, 0];
- n := 0;
- l := 0; while l < length do
- l := l + 1;
- next := rel[l];
- if next = num[1] then e[1] := e[1] + 1;
- elif next = num[2] then e[2] := e[2] + 1;
- elif next = -num[1] then e[1] := e[1] - 1;
- elif next = -num[2] then e[2] := e[2] - 1;
- else e := [0, 0]; l := length;
- fi;
- od;
+ num := [ AbsInt( rel[1] ), AbsInt( rel[2] ) ];
+ exp := [ exponents[num[1]], exponents[num[2]] ];
+ fac := [ 0, 0 ];
+ e := [ 0, 0 ];
+
+ # If there is at least one relator of the form a^m or b^n, then
+ # search for a relator of the form a^s * b^t (modulo [a,b])
+ # with s prime to m or t prime to n, respectively. For, if s is
+ # prime to m, then we can use the Euclidian algorithm to
+ # express a as a power of b and then eliminate a.
+
+ if exp[1] > 0 or exp[2] > 0 then
+
+ j := 0;
+ while j < numrels do
+
+ # get the next relator.
+ j := j + 1;
+ if lengths[j] > 0 and j <> i then
+ rel := rels[j];
+
+ # check whether rel is a word in a and b.
+ length := lengths[j];
+ e[1] := 0;
+ e[2] := 0;
+ powers := 0;
+ prev := 0;
+ l := 0;
+ while l < length do
+ l := l + 1;
+ next := rel[l];
+ if next <> prev then
+ powers := powers + 1;
+ prev := next;
+ fi;
+ if next = num[1] then e[1] := e[1] + 1;
+ elif next = num[2] then e[2] := e[2] + 1;
+ elif next = -num[1] then e[1] := e[1] - 1;
+ elif next = -num[2] then e[2] := e[2] - 1;
+ else l := length + 1;
+ fi;
+ od;
- if e[1] <> 0 or e[2] <> 0 then
+ if l = length and powers > 1 then
- # reduce exponents, if possible.
- fac := [ num[1], num[2] ];
- for k in [ 1, 2 ] do
- if e[k] < 0 then
- fac[k] := invs[numgens+1+k];
- e[k] := - e[k];
+ # reduce exponents, if possible.
+ for k in [ 1, 2 ] do
+ fac[k] := num[k];
+ if exp[k] > 0 then
+ e[k] := e[k] mod exp[k];
+ if e[k] > exp[k]/2 then
+ e[k] := exp[k] - e[k];
+ fac[k] := - fac[k];
fi;
- if e[3-k] = 0 or exp[3-k] > 0 and
- e[3-k] mod exp[3-k] = 0 then
- e[k] := GcdInt( exp[k], e[k] );
- if e[k] < exp[k] then
- exp[k] := e[k];
- exponents[num[k]] := exp[k];
- AddRelator( T, gens[num[k]]^exp[k] );
- numrels := tietze[TZ_NUMRELS];
- tietze[TZ_MODIFIED] := true;
- fi;
- fi;
- od;
+ elif e[k] < 0 then
+ e[k] := - e[k];
+ fac[k] := - fac[k];
+ fi;
+ if fac[k] < 0 then
+ fac[k] := invs[numgens+1-fac[k]];
+ fi;
+ od;
- # reduce the curent relator, if possible.
- if e[1] > 0 and e[2] > 0 and e[1] + e[2] < length
- then
- e[1] := e[1] mod exp[1];
- e[2] := e[2] mod exp[2];
- rel := [ ];
- if e[1] > 0 then rel := Concatenation(
- rel, fac[1] + 0 * [1..e[1]] );
- fi;
- if e[2] > 0 then rel := Concatenation(
- rel, fac[2] + 0 * [1..e[2]] );
- fi;
- rels[j] := rel;
- lengths[j] := e[1] + e[2];
- tietze[TZ_TOTAL] := tietze[TZ_TOTAL] - length
- + e[1] + e[2];
- flags[i] := 1;
- tietze[TZ_MODIFIED] := true;
- if T.printLevel >= 3 then Print(
- "#I rels[",j,"] reduced to ",rels[j],"\n" );
+ # now the e[k] are non-negative.
+ for k in [ 1, 2 ] do
+ if e[k] > 0 and e[3-k] = 0 then
+ exp[k] := GcdInt( e[k], exp[k] );
+ if exp[k] <> exponents[num[k]] then
+ exponents[num[k]] := exp[k];
+ e[k] := exp[k];
fi;
fi;
+ od;
- # try to find a generator that can be deleted.
- if e[2] = 1 then n := num[2];
- elif e[1] = 1 then n := num[1];
+ # reduce the current relator, if possible.
+ if e[1] + e[2] < length or powers > 2 then
+ rel := [ ];
+ if e[1] > 0 then rel := Concatenation(
+ rel, fac[1] + 0 * [1..e[1]] );
+ fi;
+ if e[2] > 0 then rel := Concatenation(
+ rel, fac[2] + 0 * [1..e[2]] );
fi;
+ rels[j] := rel;
+ lengths[j] := e[1] + e[2];
+ tietze[TZ_TOTAL] := tietze[TZ_TOTAL] - length
+ + lengths[j];
+ flags[j] := 1;
+ tietze[TZ_MODIFIED] := true;
+ if T.printLevel >= 3 then Print(
+ "#I rels[",j,"] reduced to ",rels[j],"\n" );
+ fi;
+ fi;
+ # try to find a generator that can be deleted.
+ if e[1] = 1 then n := num[1];
+ elif e[2] = 1 then n := num[2];
+ else n := 0;
for k in [ 1, 2 ] do
if n = 0 and e[k] > 1 and
- GcdInt( e[k],exp[k] ) = 1
- then
+ GcdInt( e[k], exp[k] ) = 1 then
ggt := Gcdex( e[k], exp[k] );
gen := [gens[num[1]], gens[num[2]]];
if fac[1] < 0 then gen[1] := gen[1]^-1; fi;
@@ -1270,20 +1298,22 @@
od;
fi;
- if n <> 0 then
- TzEliminate( T, gens[n] );
- numgens := tietze[TZ_NUMGENS];
- numrels := tietze[TZ_NUMRELS];
- invs := tietze[TZ_INVERSES];
+ # eliminate a generator if it is possible and allowed.
+ if n <> 0 and T.generatorsLimit < numgens then
+ TzEliminate( T );
tietze[TZ_MODIFIED] := true;
j := numrels;
- i := 0;
+ i := numrels;
+ if TZ_NUMGENS < numgens then
+ newstart := true;
+ fi;
fi;
fi;
- od;
- fi;
+ fi;
+ od;
+ fi;
fi;
- i := i + 1;
+ od;
od;
if tietze[TZ_MODIFIED] then
@@ -1318,8 +1348,6 @@
fi;
tietze := T.tietze;
- tietze[TZ_MODIFIED] := false;
-
numgens := tietze[TZ_NUMGENS];
rels := tietze[TZ_RELATORS];
numrels := tietze[TZ_NUMRELS];
@@ -1415,11 +1443,11 @@
# try to find cyclic subgroups by looking at power and commutator
# relators.
- ## if tietze[TZ_TOTAL] > 0 then
- ## TzFindCyclicJoins( T );
- ## if tietze[TZ_MODIFIED] then TzSearch( T ); fi;
- ## if printstatus then TzPrintStatus( T, true ); fi;
- ## fi;
+ if tietze[TZ_TOTAL] > 0 then
+ TzFindCyclicJoins( T );
+ if tietze[TZ_MODIFIED] then TzSearch( T ); fi;
+ if printstatus then TzPrintStatus( T, true ); fi;
+ fi;
end;
END OF bugfix04.dif ________________________________________________________