> < ^ From:

< ^ Subject:

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.

==============================================================================

> < [top]