Harald Boegeholz writes:
Date: 21 Apr 94 11:05 +0200 From: Volkmar Felsch <volkmar.felsch@math.rwth-aachen.de>As the discussion on keeping track of Tietze transformations is too
technical to be continued in the GAP forum, I have sent my answer to
the above letter directly to Chris Wensley.Can any discussion about GAP be too technical to be continued in the
GAP forum? I for one don't think so (except maybe if we are talking
about machine specific implementation details); the traffic in the GAP
forum is so low that I can easily ignore any messages I don't
understand.So why not continue this discussion in public, i.e., in the forum?
In the past we have got several comments by GAP forum members asking
us not to overwhelm the forum by too technical discussions. That is the
reason why I hesitated to continue a public discussion on Chris Wensley's
contribution and why I sent only a short statement to the forum which
offered copies of that discussion to all who might be interested in it
only on special request.
In the meantime, I have got about half a dozen reactions to that statement
asking me for a copy of our correspondence or for a public continuation
of the discussion. I think that justifies now to provide my letter to Chris
Wensley and his reply in the forum.
Volkmar Felsch, Aachen
==============================================================================
Martin Sch"onert, in his reply to Tim Hsu, writes:
" ..use Tietze transformations.. If one keeps track of the transformations.."
Since this is precisely what I want to do, I am asking how!
Specifically, if a messy presentation with generators _x1 .. _x20 (say)
is reduced, using TzGo , to a presentation with generating set
[ _x3, _x12, _x24 ] ,I want to remember expressions for the
21 eliminated generators as words in the three remaining ones.I have not been able to discover a solution in the manual but 3 possible
methods suggest themselves. Guidance as to which way to go would be much
appreciated.1. Avoid using the high-level TzGo and use the low-level commands
so that at each elimination the required formula can be saved. Surely
this would amount to rewriting TzGo ?2. Edit appropriate parts of the file "fptietze.g" .
This file is 40 pages long, with many interdependant functions,
so I should probably create a host of bugs?
In any case, the functions use the <Tietze record> type, which
appears to be defined elsewhere, possibly in the kernel?3. Start a LOG file before using TzGo and so produce a file
containing messages of the form:
#I eliminating _x7 = _x18^5*_x5*_x4
As far as I can tell, GAP cannot Read this LOG file, but perhaps it
would be possible to write some utility to convert the LOG file into
a GAP file, Exec this utility, and Read the resulting GAP file?
Dear Dr. Wensley,
I will try to answer your above letter to the GAP forum.
The GAP Tietze transformations functions have not bee designed to keep
track of the eliminations. So, in fact, you get only the messages
which you quote in point 3 of your letter.
I must confess that I do not really understand what kind of GAP readable
output you would like to get instead, but if you just want to get the
same information in some different, GAP readable format, then, as you
said that you are prepared to do at least some small amount of editing
file 'fptietze.g', there is a reasonably simple way of inserting some
appropriate print statements for this purpose.
Essentially, what you have to do is to find the three places in file
'fptietze.g' where the above messages are printed. They are in the
functions 'TzEliminateFromTree', 'TzEliminateGen', and 'TzEliminateGen1',
and you will find them by searching for occurrences of the string
'eliminating "'. The respective statements are of the form
if T.printLevel >= 2 then
Print( "#I eliminating ", gens[num], " = " );
if gen > 0 then Print( TzWord( tietze, word )^-1, "\n" );
else Print( TzWord( tietze, word ), "\n" ); fi;
fi;
and in each case you should duplicate them by adding something like
if IsBound( P.keepTrack ) and P.keepTrack then
Print( gens[num], " := " );
if gen > 0 then Print( TzWord( tietze, word )^-1, ";\n" );
else Print( TzWord( tietze, word ), ";\n" ); fi;
fi;
(or whatever you want to print). Here I assume that 'P.keepTrack' is a
new component of your current presentation record 'P', say, which has
to be introduced by a statement like
P.keepTrack := true;
before calling the 'GoTo' command. (An alternative to such an individual
variable for each presentation record would be some global variable
'keepTrack' which you initialize at the beginning of your session.)
Note, however, that the messages printed by the three functions mentioned
above do not cover all eliminations which may be performed during a Tietze
transformations run. In general, further eliminations will be performed
by the function 'TzHandleLength1Or2Relators'. Because of your request,
I now have extended this function by some additional print statements.
(The extended version will go into the next release of GAP.)
I am sending you a copy of the new version in this letter. Again, you
will have to duplicate the print statements appropriately. To make things
easier for you, I have already added a sample of such duplications (in the
form of comments). As above, you should change these additional statements
according to your needs.
Please feel free to contact me again if you have further questions.
Volkmar Felsch, Aachen
-----------------------------------------------------------------------------
#############################################################################
##
#F TzHandleLength1Or2Relators( <Tietze record> ) . . . handle short relators
##
## 'TzHandleLength1Or2Relators' searches for relators of length 1 or 2 and
## performs suitable Tietze transformations for each of them:
##
## Generators occurring in relators of length 1 are eliminated.
##
## Generators occurring in square relators of length 2 are marked to be
## involutions.
##
## If a relator of length 2 involves two different generators, then the
## generator with the larger number is substituted by the other one in all
## relators and finally eliminated from the set of generators.
##
TzHandleLength1Or2Relators := function ( T )
local absrep2, done, flags, gens, i, invs, j, length, lengths, numgens,
numgens1, numrels, pointers, ptr, ptr1, ptr2, redunds, rels, rep,
rep1, rep2, tietze, tree, treelength, treeNums;if T.printLevel >= 3 then Print( "#I handling short relators\n" ); fi;# check the given argument to be a Tietze record.
if not ( IsBound( T.isTietze ) and T.isTietze ) then
Error( "argument must be a Tietze record" );
fi;
tietze := T.tietze;gens := tietze[TZ_GENERATORS];
invs := tietze[TZ_INVERSES];
rels := tietze[TZ_RELATORS];
lengths := tietze[TZ_LENGTHS];
flags := tietze[TZ_FLAGS];
numgens := tietze[TZ_NUMGENS];
numrels := tietze[TZ_NUMRELS];
redunds := tietze[TZ_NUMREDUNDS];
numgens1 := numgens + 1;
done := false;tree := 0; if IsBound( T.tree ) then tree := T.tree; treelength := tree[TR_TREELENGTH]; pointers := tree[TR_TREEPOINTERS]; treeNums := tree[TR_TREENUMS]; fi;while not done do
done := true; # loop over all relators and find those of length 1 or 2. for i in [ 1 .. numrels ] do length := lengths[i]; if length <= 2 and length > 0 and flags[i] <= 2 thendone := false; # find the current representative of the first factor. rep1 := rels[i][1]; while invs[numgens1-rep1] <> rep1 do rep1 := invs[numgens1-rep1]; od; if length = 1 then
# handle a relator of length 1.
if rep1 <> 0 then
rep1 := AbsInt( rep1 );
invs[numgens1-rep1] := 0;
invs[numgens1+rep1] := 0;
if tree <> 0 then
ptr1 := AbsInt( treeNums[rep1] );
pointers[ptr1] := 0;
treeNums[rep1] := 0;
fi;
if T.printLevel >= 2 then
Print( "#I eliminating ", gens[rep1],
" = IdWord\n" );
fi;
### if IsBound( T.keepTrack ) and T.keepTrack then
### Print( gens[rep1], " := IdWord;\n" );
### fi;
redunds := redunds + 1;
fi;
else
# find the current representative of the second factor.
rep2 := rels[i][2];
while invs[numgens1-rep2] <> rep2 do
rep2 := invs[numgens1-rep2];
od;# handle a relator of length 2. if AbsInt( rep2 ) < AbsInt( rep1 ) then rep := rep1; rep1 := rep2; rep2 := rep; fi; if rep1 < 0 then rep1 := - rep1; rep2 := - rep2; fi; if rep1 = 0 then
# the relator is in fact of length at most 1.
if rep2 <> 0 then
rep2 := AbsInt( rep2 );
invs[numgens1-rep2] := 0;
invs[numgens1+rep2] := 0;
if tree <> 0 then
ptr2 := AbsInt( treeNums[rep2] );
pointers[ptr2] := 0;
treeNums[rep2] := 0;
fi;
if T.printLevel >= 2 then
Print( "#I eliminating ", gens[rep2],
" = IdWord\n" );
fi;
### if IsBound( T.keepTrack ) and T.keepTrack then
### Print( gens[rep2], " := IdWord;\n" );
### fi;
redunds := redunds + 1;
fi;
elif rep1 <> - rep2 thenif invs[numgens1+rep1] < 0 and ( rep1 = rep2 or invs[numgens1-rep2] = invs[numgens1+rep2] ) then # make the relator a square relator, ... rels[i][1] := rep1; rels[i][2] := rep1; # ... mark it appropriately, ... flags[i] := 3; # ... and mark rep1 to be an involution. invs[numgens1+rep1] := rep1; fi; # handle a non-square relator of length 2. if rep1 <> rep2 then absrep2 := AbsInt( rep2 ); invs[numgens1-rep2] := invs[numgens1+rep1]; invs[numgens1+rep2] := rep1; if tree <> 0 then
ptr1 := AbsInt( treeNums[rep1] );
ptr2 := AbsInt( treeNums[absrep2] );
if ptr2 < ptr1 then
ptr := ptr2;
if treeNums[rep1] * treeNums[absrep2]
* rep2 > 0 then
ptr := - ptr;
treeNums[rep1] := ptr;
pointers[ptr1] := treelength + rep1;
fi;
ptr2 := ptr1;
ptr1 := AbsInt( ptr );
fi;
if rep2 > 0 then
ptr1 := - ptr1;
fi;
pointers[ptr2] := ptr1;
treeNums[absrep2] := 0;
fi;
if T.printLevel >= 2 then
Print( "#I eliminating ", gens[absrep2],
" = " );
if rep2 > 0 then
Print( TzWord( tietze,
[ invs[numgens1+rep1] ] ), "\n" );
else
Print( gens[rep1], "\n" );
fi;
fi;
### if IsBound( T.keepTrack ) and T.keepTrack then
### Print( gens[absrep2], " := " );
### if rep2 > 0 then
### Print( TzWord( tietze,
### [ invs[numgens1+rep1] ] ), ";\n" );
### else
### Print( gens[rep1], ";\n" );
### fi;
### fi;
redunds := redunds + 1;
fi; fi; fi; fi; od;if not done then
# for each generator determine its current representative. for i in [ 1 .. numgens ] do if invs[numgens1-i] <> i then rep := invs[numgens1-i]; invs[numgens1-i] := invs[numgens1-rep]; invs[numgens1+i] := invs[numgens1+rep]; fi; od;# perform the replacements. TzReplaceGens( tietze ); fi; od;# tidy up the Tietze generators.
tietze[TZ_NUMREDUNDS] := redunds;
if redunds > 0 then TzRemoveGenerators( T ); fi;
# Print( "#I total length = ", tietze[TZ_TOTAL], "\n" );
end;
==============================================================================
Dear Dr. Felsch,
Thank you for your very helpful message yesterday.
The significant part of the reply was:
"Here I assume that 'P.keepTrack' is a new component ...
..... to be introduced by a statement like
P.keepTrack := true;
I was amazed and delighted to discover that new components can be added
to a record so easily. (I must admit that, until today, I had only glanced
briefly at the chapter on records in the manual.)
So I propose to add a new component to a presentation record, initially
a copy of the generators component, and update this within the various
elimination functions.
Chris Wensley, Bangor.
==============================================================================