1############################################################################# 2## 3## This file is part of GAP, a system for computational discrete algebra. 4## This file's authors include Volkmar Felsch. 5## 6## Copyright of GAP belongs to its developers, whose names are too numerous 7## to list here. Please refer to the COPYRIGHT file for details. 8## 9## SPDX-License-Identifier: GPL-2.0-or-later 10## 11## This file contains the methods for Tietze transformations of presentation 12## records (i.e., of presentations of finitely presented groups (fp groups). 13## 14 15############################################################################# 16## 17#F TzTestInitialSetup(<Tietze object>) 18## 19## This function calls TzHandleLength1Or2Relators on a presentation for 20## which is has not yet been called. (Needed because we cannot yet call it 21## while the presentation is created, as it may remove generators.) 22TzTestInitialSetup := function( T ) 23 if not IsBound( T!.hasRun1Or2 ) then 24 TzHandleLength1Or2Relators( T ); 25 T!.hasRun1Or2:=true; 26 TzSort( T ); 27 fi; 28end; 29 30 31############################################################################# 32## 33#M AddGenerator( <Tietze record> ) . . . . . . . . . . . . add a generator 34## 35## extends the given Tietze presentation by a new generator. 36## 37## Let i be the smallest positive integer which has not yet been used as 38## a generator number and for which no component T!.i exists so far in the 39## given presentation T, say. `AddGenerator' defines a new abstract 40## generator _xi and adds it, as component T!.i, to the given presentation. 41## 42InstallGlobalFunction( AddGenerator, function ( T ) 43 44 local gen, numgens, tietze; 45 46 # check the given argument to be a Tietze record. 47 TzCheckRecord( T ); 48 49 # define an abstract generator and add it to the set of generators. 50 gen := TzNewGenerator( T ); 51 52 # display a message. 53 if TzOptions(T).printLevel >= 1 then 54 tietze := T!.tietze; 55 numgens := tietze[TZ_NUMGENS]; 56 Print( "#I now the presentation has ", numgens, 57 " generators, the new generator is ", gen, "\n"); 58 fi; 59 60 # if there is a tree of generators, delete it. 61 if IsBound( T!.tree ) then Unbind( T!.tree ); fi; 62 63 # if generator images and preimages are being traced through the 64 # Tietze transformations applied to T, delete them. 65 if IsBound( T!.imagesOldGens ) then 66 TzUpdateGeneratorImages( T, -1, 0 ); 67 fi; 68 69 tietze[TZ_MODIFIED] := true; 70 tietze[TZ_OCCUR]:=false; 71end ); 72 73 74############################################################################# 75## 76#M AddRelator( <Tietze record>, <word> ) . . . . . . . . . . add a relator 77## 78## adds the given relator to the given Tietze presentation. 79## 80InstallGlobalFunction( AddRelator, function ( T, word ) 81 82 local flags, leng, lengths, numrels, rel, rels, tietze; 83 84 # check the first argument to be a Tietze record. 85 TzCheckRecord( T ); 86 87 if TzOptions(T).printLevel >= 3 then 88 Print( "#I adding relator ",word,"\n" ); 89 fi; 90 91 tietze := T!.tietze; 92 rels := tietze[TZ_RELATORS]; 93 numrels := tietze[TZ_NUMRELS]; 94 flags := tietze[TZ_FLAGS]; 95 lengths := tietze[TZ_LENGTHS]; 96 97 # add rel to the relators of T, and make the Tietze lists consistent. 98 rel := TzRelator( T, word ); 99 leng := Length( rel ); 100 if leng > 0 then 101 numrels := numrels + 1; 102 rels[numrels] := rel; 103 lengths[numrels] := leng; 104 flags[numrels] := 1; 105 tietze[TZ_NUMRELS] := numrels; 106 tietze[TZ_TOTAL] := tietze[TZ_TOTAL] + leng; 107 tietze[TZ_MODIFIED] := true; 108 tietze[TZ_OCCUR]:=false; 109 fi; 110end ); 111 112############################################################################# 113## 114#M TzRelatorOldImages( <Tietze record>, <word> ) . . . . . rewrite relator 115## 116## adds the given relator, possibly in old generators, write it in the 117## current generators. 118## to the given Tietze presentation. 119## 120InstallGlobalFunction( TzRelatorOldImages, function ( T, word ) 121 122local flags, leng, lengths, numrels, rel, rels, tietze,l,imgs,i,j,a,fam; 123 124 # do we need to translate? 125 if IsBound(T!.imagesOldGens) then 126 imgs:=T!.imagesOldGens; 127 l:=word^0; 128 for i in LetterRepAssocWord(word) do 129 if i<0 then 130 a:=-Reversed(imgs[-i]); 131 else 132 a:=imgs[i]; 133 fi; 134 for j in a do 135 if j>0 then 136 l:=l*T!.generators[j]; 137 else 138 l:=l/T!.generators[-j]; 139 fi; 140 od; 141 od; 142 143 word:=l; 144 145 fi; 146 return word; 147end ); 148 149 150############################################################################# 151## 152#M DecodeTree( <Tietze record> ) . . . . decode a subgroup generators tree 153## 154## `DecodeTree' applies the tree decoding method to a subgroup presentation 155## provided by the Reduced Reidemeister-Schreier or by the Modified Todd- 156## Coxeter method. 157## 158## rels is the set of relators. 159## gens is the set of generators. 160## total is the total length of all relators. 161## 162InstallGlobalFunction( DecodeTree, function ( T ) 163 164 local count, decode, looplimit, primary, protected, tietze, trlast; 165 166 # check the given argument to be a Presentation. 167 if not IsPresentation( T ) then 168 Error( "argument must be a Presentation" ); 169 fi; 170 tietze := T!.tietze; 171 protected := TzOptions(T).protected; 172 173 # check if there is a tree of generators. 174 if not IsBound( T!.tree ) then 175 Error( "there is not tree to decode it" ); 176 fi; 177 decode := true; 178 TzOptions(T).protected := Maximum( protected, T!.tree[TR_PRIMARY] ); 179 180 # if generator images are being traced, delete them. 181 if IsBound( T!.imagesOldGens ) then 182 Unbind( T!.imagesOldGens ); 183 fi; 184 185 # substitute substrings by shorter ones. 186 TzSearch( T ); 187 188 # now run our standard strategy and repeat it. 189 looplimit := TzOptions(T).loopLimit; 190 count := 0; 191 while count < looplimit and tietze[TZ_TOTAL] > 0 do 192 193 # replace substrings by substrings of equal length. 194 TzSearchEqual( T ); 195 if tietze[TZ_MODIFIED] then TzSearch( T ); fi; 196 197 # eliminate generators. 198 TzEliminateGens( T, decode ); 199 if tietze[TZ_MODIFIED] then 200 TzSearch( T ); 201 if tietze[TZ_MODIFIED] then TzSearch( T ); fi; 202 if tietze[TZ_MODIFIED] then TzSearchEqual( T ); fi; 203 if tietze[TZ_MODIFIED] then TzSearch( T ); fi; 204 count := count + 1; 205 else 206 count := looplimit; 207 fi; 208 209 if TzOptions(T).printLevel = 1 then TzPrintStatus( T, true ); fi; 210 od; 211 212 # check if the tree decoding has been finished. 213 primary := T!.tree[TR_PRIMARY]; 214 trlast := T!.tree[TR_TREELAST]; 215 if trlast <= primary then 216 # if yes, delete the tree ... 217 Unbind( T!.tree ); 218 # ... and reinitialize the tracing of generator images images if 219 # it had been initialized before. 220 if IsBound( T!.preImagesNewGens ) then 221 TzInitGeneratorImages( T ); 222 if TzOptions(T).printLevel > 0 then 223 Print( "#I Warning: ", 224 "the generator images have been reinitialized\n" ); 225 fi; 226 fi; 227 else 228 # if not, display a serious warning. 229 Print( "\n", "#I ********** WARNING: the tree decoding is", 230 " incomplete ! **********\n\n", 231 "#I hence the isomporphism type of the presented group may", 232 " have changed,\n", 233 "#I you should continue by first calling the `DecodeTree'", 234 " command again,\n", 235 "#I possibly after changing the Tietze option parameters", 236 " appropriately\n\n" ); 237 fi; 238 239 TzOptions(T).protected := protected; 240end ); 241 242 243############################################################################# 244## 245#M FpGroupPresentation( <Tietze record> ) . . . . converts the given Tietze 246#M presentation to a fin. pres. group 247## 248## `FpGroupPresentation' constructs the group defined by the given Tietze 249## presentation and returns the group record. 250## 251InstallGlobalFunction( FpGroupPresentation, function (arg) 252 253local P,F, fgens, freegens, frels, G, gens, names, numgens, origin, 254 redunds, rels, T, tietze, tzword; 255 256 P:=arg[1]; 257 258 if TzOptions(P).printLevel >= 3 then 259 Print( "#I converting the Tietze presentation to a group\n" ); 260 fi; 261 262 # check the given argument to be a Tietze record. 263 TzCheckRecord( P ); 264 265 # do not change the given presentation, so work on a copy. 266 T := ShallowCopy( P ); 267 268 # get some local variables. 269 tietze := T!.tietze; 270 gens := tietze[TZ_GENERATORS]; 271 numgens := tietze[TZ_NUMGENS]; 272 rels := tietze[TZ_RELATORS]; 273 redunds := tietze[TZ_NUMREDUNDS]; 274 275 # tidy up the Tietze presentation. 276 if redunds > 0 then TzRemoveGenerators( T ); fi; 277 TzSort( T ); 278 279 # create an appropriate free group. 280 freegens := tietze[TZ_FREEGENS]; 281 names := List( gens, g -> 282 FamilyObj( gens[1] )!.names[Position( freegens, g )] ); 283 284 if Length(arg)>1 then 285 F:=FreeGroup(Length(names),arg[2]); 286 else 287 F := FreeGroup( names ); 288 fi; 289 290 fgens := GeneratorsOfGroup( F ); 291 292 # convert the relators from Tietze words to words in the generators of F. 293 frels := [ ]; 294 for tzword in rels do 295 if tzword <> [ ] then 296 Add( frels, AbstractWordTietzeWord( tzword, fgens ) ); 297 fi; 298 od; 299 300 # get the resulting finitely presented group. 301 G := F / frels; 302 303 # save the generator images, if available. 304 origin := rec( ); 305 if IsBound( T!.imagesOldGens ) then 306 origin!.imagesOldGens := Immutable( T!.imagesOldGens ); 307 origin!.preImagesNewGens := Immutable( T!.preImagesNewGens ); 308 fi; 309 SetTietzeOrigin( G, origin ); 310 311 return G; 312end ); 313 314 315############################################################################# 316## 317#M PresentationFpGroup( <G> [,<print level>] ) . . . create a Tietze record 318## 319## `PresentationFpGroup' creates a presentation, i.e. a Tietze record, for 320## the given finitely presented group. 321## 322InstallGlobalFunction( PresentationFpGroup, function ( arg ) 323 324 local F, G, fggens, freegens, frels, gens, grels, i, invs, lengths, 325 numgens, numrels, printlevel, rels, T, tietze, total; 326 327 # check the first argument to be a finitely presented group. 328 G := arg[1]; 329 if not ( IsSubgroupFpGroup( G ) and IsGroupOfFamily( G ) ) then 330 Error( "<G> must be a finitely presented group" ); 331 fi; 332 333 # check the second argument to be an integer. 334 printlevel := 1; 335 if Length( arg ) = 2 then printlevel := arg[2]; fi; 336 if not IsInt( printlevel ) then 337 Error( "second argument must be an integer" ); 338 fi; 339 340 # Create the Presentation. 341 T := Objectify( NewType( PresentationsFamily, 342 IsPresentationDefaultRep 343 and IsPresentation 344 and IsMutable ), 345 rec() ); 346 tietze := ListWithIdenticalEntries( TZ_LENGTHTIETZE, 0 ); 347 tietze[TZ_OCCUR]:=false; 348 T!.tietze := tietze; 349 350 # initialize the Tietze stack. 351 fggens := FreeGeneratorsOfFpGroup( G ); 352 grels := RelatorsOfFpGroup( G ); 353 F := FreeGroup( IsLetterWordsFamily,infinity, "_x", 354 ElementsFamily( FamilyObj( FreeGroupOfFpGroup( G ) ) )!.names ); 355 freegens := GeneratorsOfGroup( F ); 356 tietze[TZ_FREEGENS] := freegens; 357 numgens := Length( fggens ); 358 tietze[TZ_NUMGENS] := numgens; 359 gens := List( [ 1 .. numgens ], i -> freegens[i] ); 360 tietze[TZ_GENERATORS] := gens; 361 invs := ShallowCopy( numgens - [ 0 .. 2 * numgens ] ); 362 tietze[TZ_INVERSES] := invs; 363 frels := List( grels, rel -> MappedWord( rel, fggens, gens ) ); 364 numrels := Length( frels ); 365 rels := List( [ 1 .. numrels ], i -> TzRelator( T, frels[i] ) ); 366 lengths := List( [ 1 .. numrels ], i -> Length( rels[i] ) ); 367 total := Sum( lengths ); 368 tietze[TZ_NUMRELS] := numrels; 369 tietze[TZ_RELATORS] := rels; 370 tietze[TZ_LENGTHS] := lengths; 371 tietze[TZ_FLAGS] := ListWithIdenticalEntries( numrels, 1 ); 372 tietze[TZ_TOTAL] := total; 373 tietze[TZ_STATUS] := [ 0, 0, -1 ]; 374 tietze[TZ_MODIFIED] := false; 375 T!.generators := tietze[TZ_GENERATORS]; 376 T!.components := [ 1 .. numgens ]; 377 for i in [ 1 .. numgens ] do 378 T!.(String( i )) := gens[i]; 379 od; 380 T!.nextFree := numgens + 1; 381 SetOne(T,Identity( F )); 382 T!.identity:=Identity( F ); 383 384 # since T is mutable, we must set this attribute "manually" 385 SetTzOptions(T,TzOptions(T)); 386 387 # initialize some Tietze options 388 TzOptions(T).protected := 0; 389 TzOptions(T).printLevel:=printlevel; 390 391 # print the status line. 392 if TzOptions(T).printLevel >= 2 then TzPrintStatus( T, true ); fi; 393 394 # return the Tietze record. 395 return T; 396end ); 397 398 399############################################################################# 400## 401#M PrintObj( <T> ) . . . . . . . . . . . pretty print a presentation record 402## 403InstallMethod( PrintObj, 404 "for a presentation in default representation", 405 true, 406 [ IsPresentation and IsPresentationDefaultRep ], 0, 407 function( T ) 408 409 local numgens, numrels, tietze, total; 410 411 # get number of generators, number of relators, and total length. 412 tietze := T!.tietze; 413 numgens := tietze[TZ_NUMGENS] - tietze[TZ_NUMREDUNDS]; 414 numrels := tietze[TZ_NUMRELS]; 415 total := tietze[TZ_TOTAL]; 416 417 # print the Tietze status line. 418 Print( "<presentation with ", numgens, " gens and ", numrels, 419 " rels of total length ", total, ">" ); 420 421end ); 422 423 424############################################################################# 425## 426#M ShallowCopy( <T> ) 427## 428InstallMethod( ShallowCopy, 429 "for a presentation in default representation", true, 430 [ IsPresentation and IsPresentationDefaultRep ], 0, StructuralCopy ); 431 432 433############################################################################# 434## 435#M PresentationRegularPermutationGroup(<G>) . . . construct a presentation 436#M from a regular permutation group 437## 438## `PresentationRegularPermutationGroup' constructs a presentation from the 439## given regular permutation group using John Cannon's relations finding 440## algorithm. 441## 442InstallGlobalFunction( PresentationRegularPermutationGroup, function ( G ) 443 444 # check G to be a regular permutation group. 445 if not ( IsPermGroup( G ) and IsRegular( G ) ) then 446 Error( "the given group must be a regular permutation group" ); 447 fi; 448 return PresentationRegularPermutationGroupNC( G ); 449end ); 450 451 452############################################################################# 453## 454#M PresentationRegularPermutationGroupNC(<G>) . . construct a presentation 455#M from a regular permutation group 456## 457## `PresentationRegularPermutationGroupNC' constructs a presentation from 458## the given regular permutation group using John Cannon's relations finding 459## algorithm. 460## 461## In this NC version it is assumed, but not checked that G is a regular 462## permutation group. 463## 464InstallGlobalFunction( PresentationRegularPermutationGroupNC, function ( G ) 465 local cosets, # right cosets of G by its trivial subgroup H 466 F, # given free group 467 R, # record containing an fp group isomorphic to G 468 P, # presentation to be consructed 469 ng1, # position number of identity element in G 470 idword, # identity element of F 471 table, # columns in the table for gens 472 rels, # representatives of the relators 473 relsGen, # relators sorted by start generator 474 subgroup, # rows for the subgroup gens 475 i, j, # loop variables 476 gen, # loop variables for generator 477 gen0, inv0, # loop variables for generator cols 478 g, g1, # loop variables for generator cols 479 c, # loop variable for coset 480 rel, # loop variables for relator 481 rels1, # list of relators 482 app, # arguments list for `MakeConsequences' 483 index, # index of the table 484 col, # generator col in auxiliary table 485 perm, # variable for permutations 486 fgens, # generators of F 487 gens2, # the above abstract gens and their inverses 488 perms, # permutation generators of G 489 moved, # list of points on which G acts, 490 ngens, # number of generators of G 491 ngens2, # twice the above number 492 order, # order of a generator 493 actcos, # part 1 of Schreier vector of G by H 494 actgen, # part 2 of Schreier vector of G by H 495 tab0, # auxiliary table in parallel to table <table> 496 cosRange, # range from 1 to index (= number of cosets) 497 genRange, # range of the odd integers from 1 to 2*ngens-1 498 geners, # order in which the table cols are worked off 499 next, # local coset number 500 n; # number of subgroup element 501 502 # initialize some local variables. 503 perms := GeneratorsOfGroup( G ); 504 ngens := Length( perms ); 505 ngens2 := ngens * 2; 506 ng1 := 1; 507 index := NrMovedPoints( perms ); 508 tab0 := []; 509 table := []; 510 subgroup := []; 511 cosRange := [ 1 .. index ]; 512 genRange := List( [ 1 .. ngens ], i -> 2*i-1 ); 513 rels := []; 514 F := FreeGroup( ngens ); 515 fgens := GeneratorsOfGroup( F ); 516 gens2 := []; 517 idword := One( fgens[1] ); 518 519 # ensure that the permutations act on the points 1 to index (note that 520 # index is the degree of G). 521 if LargestMovedPoint( perms ) > index then 522 moved := MovedPoints( perms ); 523 perm := MappingPermListList( moved, [ 1 .. index ] ); 524 perms := OnTuples( perms, perm ); 525 fi; 526 527 # get a coset table from the permutations, 528 # and introduce appropriate relators for the involutory generators 529 for i in [ 1 .. ngens ] do 530 Add( gens2, fgens[i] ); 531 Add( gens2, fgens[i]^-1 ); 532 perm := perms[i]; 533 col := OnTuples( cosRange, perm ); 534 gen := ListWithIdenticalEntries( index, 0 ); 535 Add( tab0, col ); 536 Add( table, gen ); 537 order := Order( perms[i] ); 538 if order = 2 then 539 Add( rels, fgens[i]^2 ); 540 else 541 col := OnTuples( cosRange, perm^-1 ); 542 gen := ListWithIdenticalEntries( index, 0 ); 543 fi; 544 Add( tab0, col ); 545 Add( table, gen ); 546 od; 547 548 # define an appropriate ordering of the cosets, 549 # enter the definitions in the table, 550 # and construct the Schreier vector, 551 cosets := ListWithIdenticalEntries( index, 0 ); 552 actcos := ListWithIdenticalEntries( index, 0 ); 553 actgen := ListWithIdenticalEntries( index, 0 ); 554 cosets[1] := ng1; 555 actcos[ng1] := ng1; 556 j := 1; 557 i := 0; 558 while i < index do 559 i := i + 1; 560 c := cosets[i]; 561 g := 0; 562 while g < ngens2 do 563 g := g + 1; 564 next := tab0[g][c]; 565 if next > 0 and actcos[next] = 0 then 566 g1 := g + 2*(g mod 2) - 1; 567 table[g][c] := next; 568 table[g1][next] := c; 569 tab0[g][c] := 0; 570 tab0[g1][next] := 0; 571 actcos[next] := c; 572 actgen[next] := g; 573 j := j + 1; 574 cosets[j] := next; 575 if j = index then 576 g := ngens2; 577 i := index; 578 fi; 579 fi; 580 od; 581 od; 582 583 # compute the representatives for the relators 584 rels := RelatorRepresentatives( rels ); 585 586 # make the structure that is passed to `MakeConsequences' 587 app := ListWithIdenticalEntries( 12, 0 ); 588 589 # note: we have, in particular, set app[12] to zero as we do not want 590 # minimal gaps to be marked in the coset table 591 592 app[1] := table; 593 app[5] := subgroup; 594 595 # run through the coset table and find the next undefined entry 596 geners := [ 1 .. ngens2 ]; 597 for i in cosets do 598 for j in geners do 599 if table[j][i] <= 0 then 600 601 # define the entry appropriately, 602 g := j + 2*(j mod 2) - 1; 603 c := tab0[j][i]; 604 table[j][i] := c; 605 table[g][c] := i; 606 tab0[j][i] := 0; 607 tab0[g][c] := 0; 608 609 # construct the associated relator 610 rel := idword; 611 while c <> ng1 do 612 g := actgen[c]; 613 rel := rel * gens2[g]^-1; 614 c := actcos[c]; 615 od; 616 rel := rel^-1 * gens2[j]^-1; 617 c := i; 618 while c <> ng1 do 619 g := actgen[c]; 620 rel := rel * gens2[g]^-1; 621 c := actcos[c]; 622 od; 623 624 # compute its representative, 625 # and add it to the set of relators 626 rels1 := RelatorRepresentatives( [ rel ] ); 627 if Length( rels1 ) > 0 then 628 rel := rels1[1]; 629 if not rel in rels then 630 Add( rels, rel ); 631 fi; 632 fi; 633 634 # make the rows for the relators and distribute over relsGen 635 relsGen := RelsSortedByStartGen( fgens, rels, table, true ); 636 app[4] := relsGen; 637 638 # mark all already defined entries of table by a zero in 639 # tab0 640 for g in genRange do 641 gen := table[g]; 642 gen0 := tab0[g]; 643 inv0 := tab0[g+1]; 644 for c in cosRange do 645 if gen[c] > 0 then 646 gen0[c] := 0; 647 inv0[gen[c]] := 0; 648 fi; 649 od; 650 od; 651 652 # continue the enumeration and find all consequences 653 for g in genRange do 654 gen0 := tab0[g]; 655 for c in cosRange do 656 if gen0[c] = 0 then 657 app[10] := g; 658 app[11] := c; 659 n := MakeConsequences( app ); 660 fi; 661 od; 662 od; 663 fi; 664 od; 665 od; 666 667 # construct a finitely presented group from the relations, 668 # add the Schreier vector to its components, and return it 669 P := PresentationFpGroup( F / rels, 0 ); 670 TzOptions(P).protected := ngens; 671 TzGoGo( P ); 672 TzOptions(P).protected := 0; 673 TzOptions(P).printLevel := 1; 674 675 # return the resulting presentation 676 return P; 677end ); 678 679 680############################################################################# 681## 682#M PresentationViaCosetTable(<G>) . . . . . . . . construct a presentation 683#M PresentationViaCosetTable(<G>,<F>,<words>) . . . . . for the given group 684## 685## `PresentationViaCosetTable' constructs a presentation for a given 686## concrete group. It applies John Cannon's relations finding algorithm 687## which has been described in 688## 689## John J. Cannon: Construction of defining relators for finte groups. 690## Discrete Math. 5 (1973), 105-129, and in 691## 692## Joachim Neubueser: An elementary introduction to coset table methods in 693## computational group theory. Groups-St Andrews 1981, edited by C. M. 694## Campbell and E. F. Robertson, pp. 1-45. London Math. Soc. Lecture Note 695## Series no. 71, Cambridge Univ. Press, Cambridge, 1982. 696## 697## If only a group <G> has been specified, the single stage algorithm is 698## applied. 699## 700## If the two stage algorithm is to be used, `PresentationViaCosetTable' 701## expects a subgroup <H> of <G> to be described by two additional arguments 702## <F> and <words>, where <F> is a free group with the same number of 703## generators as <G>, and <words> is a list of words in the generators of 704## <F> which supply a list of generators of <H> if they are evaluated as 705## words in the corresponding generators of <G>. 706## 707InstallGlobalFunction( PresentationViaCosetTable, function ( arg ) 708 local G, # given group 709 F, # given or constructed free group 710 fgens, # generators of F 711 words, # words (in the generators of F) defing H 712 twords, # tidied up list of words 713 H, # subgroup 714 elts, # elements of G or H 715 cosets, # right cosets of G with respect to H 716 R1, # record containing an fp group isomorphic to H 717 R2, # record containing an fp group isomorphic to G 718 P, # resulting presentation 719 ggens, # concrete generators of G 720 hgens, # concrete generators of H 721 thgens, # tidied up list of generators of H 722 ngens, # number of generators of G 723 one, # identity element of G 724 size, # size of G 725 F1, # free group with same number of generators as H 726 FP2, # fp group isomorphic to G 727 i; # loop variable 728 729 # check the first argument to be a group 730 G := arg[1]; 731 if not IsGroup( G ) then 732 Error( "first argument must be a group" ); 733 fi; 734 ggens := GeneratorsOfGroup( G ); 735 ngens := Length( ggens ); 736 737 # check if a subgroup has been specified 738 if Length( arg ) = 1 then 739 740 # apply the single stage algorithm 741 Info( InfoFpGroup, 1, 742 "calling the single stage relations finding algorithm" ); 743 744 # use a special method for regular permutation groups 745 if IsPermGroup( G ) then 746 # compute the size of G to speed up the regularity check 747 size := Size( G ); 748 if IsRegular( G ) then 749 return PresentationRegularPermutationGroupNC( G ); 750 fi; 751 fi; 752 753 # construct a presentation for G 754 elts := AsSSortedList( G ); 755 F := FreeGroup( ngens ); 756 R2 := RelsViaCosetTable( G, elts, F ); 757 758 else 759 760 # check the second argument to be an fp group. 761 F := arg[2]; 762 if not IsFreeGroup( F ) then 763 Error( "second argument must be a free group" ); 764 fi; 765 766 # check F for having the same number of generators as G 767 fgens := GeneratorsOfGroup( F ); 768 if Length( fgens ) <> ngens then 769 Error( "the given groups have different number of generators" ); 770 fi; 771 772 # get the subgroup H 773 words := arg[3]; 774 hgens := List( words, w -> MappedWord( w, fgens, ggens ) ); 775 H := Subgroup( G, hgens ); 776 777 if Size( H ) = 1 or Size( H ) = Size( G ) then 778 779 # apply the single stage algorithm 780 Info( InfoFpGroup, 1, 781 "calling the single stage relations finding algorithm" ); 782 elts := AsSSortedList( G ); 783 R2 := RelsViaCosetTable( G, elts, F ); 784 785 else 786 787 # apply the two stage algorithm 788 Info( InfoFpGroup, 1, 789 "calling the two stage relations finding algorithm" ); 790 Info( InfoFpGroup, 1, 791 "using a subgroup of size ", Size( H ), " and index ", 792 Size( G ) / Size( H ) ); 793 # eliminate words which define the identity of G 794 one := One( ggens[1] ); 795 thgens := []; 796 twords := []; 797 for i in [ 1 .. Length( hgens ) ] do 798 if hgens[i] <> one and not hgens[i] in thgens 799 and not hgens[i]^-1 in thgens then 800 Add( thgens, hgens[i] ); 801 Add( twords, words[i] ); 802 fi; 803 od; 804 hgens := thgens; 805 words := twords; 806 807 # construct a presentation for the subgroup H 808 elts := AsSSortedList( H ); 809 F1 := FreeGroup( Length( hgens ) ); 810 R1 := RelsViaCosetTable( H, elts, F1, hgens ); 811 812 # construct a presentation for the group G 813 cosets := RightCosets( G, H ); 814 R2 := RelsViaCosetTable( G, cosets, F, words, H, R1 ); 815 816 fi; 817 fi; 818 819 # simplify the resulting presentation by Tietze transformations, 820 # but do not eliminate any generators 821 FP2 := R2.fpGroup; 822 P := PresentationFpGroup( FP2, 0 ); 823 TzOptions(P).protected := ngens; 824 TzGoGo( P ); 825 TzOptions(P).protected := 0; 826 TzOptions(P).printLevel := 1; 827 828 # return the resulting presentation 829 return P; 830end ); 831 832 833############################################################################# 834## 835#M RelsViaCosetTable(<G>,<cosets>,<F>) . . . . . construct relators for the 836#M RelsViaCosetTable(<G>,<cosets>,<F>,<ggens>) . . . . . . . given concrete 837#M RelsViaCosetTable(<G>,<cosets>,<F>,<words>,<H>,<R1>) . . . . . . . group 838## 839## `RelsViaCosetTable' constructs a defining set of relators for the given 840## concrete group using John Cannon's relations finding algorithm. 841## 842## It is a subroutine of function `PresentationViaCosetTable'. Hence its 843## input and output are specifically designed only for this purpose, and it 844## does not check the arguments. 845## 846 847InstallGlobalFunction( RelsViaCosetTable, function ( arg ) 848 local G, # given group 849 cosets, # right cosets of G with respect to H 850 F, # given free group 851 words, # given words for the generators of H 852 H, # subgroup, if specified 853 F1, # free group associated to H 854 R1, # record containing an fp group isomorphic to H 855 R2, # record containing an fp group isomorphic to G 856 FP1, # fp group isomorphic to H 857 fhgens, # generators of F1 858 hrels, # relators of F1 859 helts, # list of elements of H 860 ng1, # position number of identity element in G 861 nh1, # position number of identity element in H 862 idword, # identity element of F 863 perms, # permutations induced by the gens on the cosets 864 stage, # 1 or 2 865 table, # columns in the table for gens 866 rels, # representatives of the relators 867 relsGen, # relators sorted by start generator 868 subgroup, # rows for the subgroup gens 869 i, j, # loop variables 870 gen, # loop variables for generator 871 gen0, inv0, # loop variables for generator cols 872 g, g1, # loop variables for generator cols 873 c, # loop variable for coset 874 rel, # loop variables for relator 875 rels1, # list of relators 876 app, # arguments list for `MakeConsequences' 877 index, # index of the table 878 col, # generator col in auxiliary table 879 perm, # permutations induced by a generator on the cosets 880 fgens, # generators of F 881 gens2, # the above abstract gens and their inverses 882 ggens, # concrete generators of G 883 ngens, # number of generators of G 884 ngens2, # twice the above number 885 order, # order of a generator 886 actcos, # part 1 of Schreier vector of G by H 887 actgen, # part 2 of Schreier vector of G by H 888 tab0, # auxiliary table in parallel to table <table> 889 cosRange, # range from 1 to index (= number of cosets) 890 genRange, # range of the odd integers from 1 to 2*ngens-1 891 geners, # order in which the table cols are worked off 892 next, # local coset number 893 left1, # part 1 of Schreier vector of H by trivial group 894 right1, # part 2 of Schreier vector of H by trivial group 895 n, # number of subgroup element 896 words2, # words for the generators of H and their inverses 897 h; # subgroup element 898 899 # get the arguments, and initialize some local variables 900 901 G := arg[1]; 902 cosets := arg[2]; 903 F := arg[3]; 904 if Length( arg ) = 4 then 905 ggens := arg[4]; 906 else 907 ggens := GeneratorsOfGroup( G ); 908 fi; 909 ngens := Length( ggens ); 910 ngens2 := ngens * 2; 911 if cosets[1] in G then 912 ng1 := PositionSorted( cosets, cosets[1]^0 ); 913 else 914 ng1 := 1; 915 fi; 916 index := Length( cosets ); 917 tab0 := []; 918 table := []; 919 subgroup := []; 920 cosRange := [ 1 .. index ]; 921 genRange := List( [ 1 .. ngens ], i -> 2*i-1 ); 922 923 if Length( arg ) < 5 then 924 stage := 1; 925 rels := []; 926 else 927 stage := 2; 928 words := arg[4]; 929 H := arg[5]; 930 helts := AsSSortedList( H ); 931 nh1 := PositionSorted( helts, helts[1]^0 ); 932 R1 := arg[6]; 933 FP1 := R1.fpGroup; 934 F1 := FreeGroupOfFpGroup( FP1 ); 935 fhgens := GeneratorsOfGroup( F1 ); 936 hrels := RelatorsOfFpGroup( FP1 ); 937 # initialize the relators of F2 by the rewritten relators of F1 938 rels := List( hrels, rel -> MappedWord( rel, fhgens, words ) ); 939 # get the Schreier vector for the elements of H 940 left1 := R1.actcos; 941 right1 := R1.actgen; 942 # extend the list of the generators of F1 as words in the abstract 943 # generators of F2 by their inverses 944 words2 := []; 945 for i in [ 1 .. Length( words ) ] do 946 Add( words2, words[i] ); 947 Add( words2, words[i]^-1 ); 948 od; 949 fi; 950 951 fgens := GeneratorsOfGroup( F ); 952 gens2 := []; 953 idword := One( fgens[1] ); 954 955 # get the permutations induced by the generators of G on the given 956 # cosets 957 perms := List( ggens, gen -> Permutation( gen, cosets, OnRight ) ); 958 959 # get a coset table from the permutations, 960 # and introduce appropriate relators for the involutory generators 961 for i in [ 1 .. ngens ] do 962 Add( gens2, fgens[i] ); 963 Add( gens2, fgens[i]^-1 ); 964 perm := perms[i]; 965 col := OnTuples( cosRange, perm ); 966 gen := ListWithIdenticalEntries( index, 0 ); 967 Add( tab0, col ); 968 Add( table, gen ); 969 order := Order( ggens[i] ); 970 if order = 2 then 971 Add( rels, fgens[i]^2 ); 972 else 973 col := OnTuples( cosRange, perm^-1 ); 974 gen := ListWithIdenticalEntries( index, 0 ); 975 fi; 976 Add( tab0, col ); 977 Add( table, gen ); 978 od; 979 980 # define an appropriate ordering of the cosets, 981 # enter the definitions in the table, 982 # and construct the Schreier vector, 983 cosets := ListWithIdenticalEntries( index, 0 ); 984 actcos := ListWithIdenticalEntries( index, 0 ); 985 actgen := ListWithIdenticalEntries( index, 0 ); 986 cosets[1] := ng1; 987 actcos[ng1] := ng1; 988 j := 1; 989 i := 0; 990 while i < index do 991 i := i + 1; 992 c := cosets[i]; 993 g := 0; 994 while g < ngens2 do 995 g := g + 1; 996 next := tab0[g][c]; 997 if next > 0 and actcos[next] = 0 then 998 g1 := g + 2*(g mod 2) - 1; 999 table[g][c] := next; 1000 table[g1][next] := c; 1001 tab0[g][c] := 0; 1002 tab0[g1][next] := 0; 1003 actcos[next] := c; 1004 actgen[next] := g; 1005 j := j + 1; 1006 cosets[j] := next; 1007 if j = index then 1008 g := ngens2; 1009 i := index; 1010 fi; 1011 fi; 1012 od; 1013 od; 1014 1015 # compute the representatives for the relators 1016 rels := RelatorRepresentatives( rels ); 1017 1018 # make the structure that is passed to `MakeConsequences' 1019 app := ListWithIdenticalEntries( 12, 0 ); 1020 1021 # note: we have, in particular, set app[12] to zero as we do not want 1022 # minimal gaps to be marked in the coset table 1023 1024 app[1] := table; 1025 app[5] := subgroup; 1026 1027 # in case stage = 2 we have to handle subgroup relators 1028 if stage = 2 then 1029 1030 # make the rows for the relators and distribute over relsGen 1031 relsGen := RelsSortedByStartGen( fgens, rels, table, true ); 1032 app[4] := relsGen; 1033 1034 # start the enumeration and find all consequences 1035 for g in genRange do 1036 gen0 := tab0[g]; 1037 for c in cosRange do 1038 if gen0[c] = 0 then 1039 app[10] := g; 1040 app[11] := c; 1041 n := MakeConsequences( app ); 1042 fi; 1043 od; 1044 od; 1045 fi; 1046 1047 # run through the coset table and find the next undefined entry 1048 geners := [ 1 .. ngens2 ]; 1049 for i in cosets do 1050 for j in geners do 1051 if table[j][i] <= 0 then 1052 1053 # define the entry appropriately, 1054 g := j + 2*(j mod 2) - 1; 1055 c := tab0[j][i]; 1056 table[j][i] := c; 1057 table[g][c] := i; 1058 tab0[j][i] := 0; 1059 tab0[g][c] := 0; 1060 1061 # construct the associated relator 1062 rel := idword; 1063 while c <> ng1 do 1064 g := actgen[c]; 1065 rel := rel * gens2[g]^-1; 1066 c := actcos[c]; 1067 od; 1068 rel := rel^-1 * gens2[j]^-1; 1069 c := i; 1070 while c <> ng1 do 1071 g := actgen[c]; 1072 rel := rel * gens2[g]^-1; 1073 c := actcos[c]; 1074 od; 1075 if stage = 2 then 1076 h := MappedWord( rel, fgens, ggens ); 1077 n := PositionSorted( helts, h ); 1078 while n <> nh1 do 1079 g := right1[n]; 1080 rel := rel * words2[g]^-1; 1081 n := left1[n]; 1082 od; 1083 fi; 1084 1085 # compute its representative, 1086 # and add it to the set of relators 1087 rels1 := RelatorRepresentatives( [ rel ] ); 1088 if Length( rels1 ) > 0 then 1089 rel := rels1[1]; 1090 if not rel in rels then 1091 Add( rels, rel ); 1092 fi; 1093 fi; 1094 1095 # make the rows for the relators and distribute over relsGen 1096 relsGen := RelsSortedByStartGen( fgens, rels, table, true ); 1097 app[4] := relsGen; 1098 1099 # mark all already defined entries of table by a zero in 1100 # tab0 1101 for g in genRange do 1102 gen := table[g]; 1103 gen0 := tab0[g]; 1104 inv0 := tab0[g+1]; 1105 for c in cosRange do 1106 if gen[c] > 0 then 1107 gen0[c] := 0; 1108 inv0[gen[c]] := 0; 1109 fi; 1110 od; 1111 od; 1112 1113 # continue the enumeration and find all consequences 1114 for g in genRange do 1115 gen0 := tab0[g]; 1116 for c in cosRange do 1117 if gen0[c] = 0 then 1118 app[10] := g; 1119 app[11] := c; 1120 n := MakeConsequences( app ); 1121 fi; 1122 od; 1123 od; 1124 fi; 1125 od; 1126 od; 1127 1128 # construct a finitely presented group from the relations, 1129 # add the Schreier vector to its components, and return it 1130 R2 := rec( ); 1131 R2.fpGroup := F / rels; 1132 R2.actcos := actcos; 1133 R2.actgen := actgen; 1134 return R2; 1135end ); 1136 1137 1138############################################################################# 1139## 1140#M RemoveRelator( <Tietze record>, <n> ) . . . . . . . . . remove a relator 1141#M from a presentation 1142## 1143## removes the <n>-th relator from the given Tietze presentation. 1144## 1145InstallGlobalFunction( RemoveRelator, function ( T, n ) 1146 1147 local invs, leng, lengths, num, numgens1, numrels, rels, tietze; 1148 1149 # check the first argument to be a Tietze record. 1150 TzCheckRecord( T ); 1151 1152 # get some local variables. 1153 tietze := T!.tietze; 1154 rels := tietze[TZ_RELATORS]; 1155 numrels := tietze[TZ_NUMRELS]; 1156 lengths := tietze[TZ_LENGTHS]; 1157 invs := tietze[TZ_INVERSES]; 1158 numgens1 := tietze[TZ_NUMGENS] + 1; 1159 1160 # check the second argument to be in range. 1161 if ( n < 1 or n > numrels ) then 1162 Error( "relator number out of range" ); 1163 fi; 1164 1165 # print a message. 1166 if TzOptions(T).printLevel >= 3 then 1167 Print( "#I removing the ", n, "th relator\n" ); 1168 fi; 1169 1170 # check if the nth relator has defined an involution. 1171 leng := lengths[n]; 1172 if leng = 2 and rels[n][1] = rels[n][2] then 1173 num := rels[n][1]; 1174 if num < 0 then num := -num; fi; 1175 if invs[numgens1+num] = num then invs[numgens1+num] := -num; fi; 1176 fi; 1177 1178 # remove the nth relator, and make the Tietze lists consistent. 1179 rels[n] := [ ]; 1180 lengths[n] := 0; 1181 tietze[TZ_TOTAL] := tietze[TZ_TOTAL] - leng; 1182 TzSort( T ); 1183 if TzOptions(T).printLevel >= 2 then TzPrintStatus( T, true ); fi; 1184end ); 1185 1186 1187############################################################################# 1188## 1189#M AbstractWordTietzeWord( <word>, <fgens> ) . . . . convert a Tietze word 1190#M to an abstract word 1191## 1192InstallGlobalFunction( AbstractWordTietzeWord, 1193function(w,gens) 1194 return AssocWordByLetterRep(FamilyObj(gens[1]),w,gens); 1195end); 1196 1197 1198############################################################################# 1199## 1200#M TzCheckRecord( <Tietze record> ) . . . . check Tietze record components 1201## 1202## `TzCheckRecord' checks some components of the given Tietze record to be 1203## consistent. 1204## 1205InstallGlobalFunction( TzCheckRecord, function ( T ) 1206 1207 local tietze; 1208 1209 # check the given argument to be a Presentation. 1210 if not IsPresentation( T ) then 1211 Error( "argument must be a Presentation" ); 1212 fi; 1213 1214 # check the generator lists to be consistent. 1215 tietze := T!.tietze; 1216 if not ( IsIdenticalObj( T!.generators, tietze[TZ_GENERATORS] ) ) or 1217 Length( tietze[TZ_GENERATORS] ) <> tietze[TZ_NUMGENS] then 1218 Error( "inconsistent generator lists" ); 1219 fi; 1220 1221 # check the inverses list. 1222 if Length( tietze[TZ_INVERSES] ) <> 2 * tietze[TZ_NUMGENS] + 1 then 1223 Error( "inconsistent generator inverses" ); 1224 fi; 1225 1226 # check the relator list. 1227 if Length( tietze[TZ_RELATORS] ) <> tietze[TZ_NUMRELS] or 1228 Length( tietze[TZ_LENGTHS] ) <> tietze[TZ_NUMRELS] or 1229 Length( tietze[TZ_FLAGS] ) <> tietze[TZ_NUMRELS] then 1230 Error( "inconsistent relators" ); 1231 fi; 1232 1233end ); 1234 1235 1236############################################################################# 1237## 1238#M TzEliminate( <Tietze record> ) . . . . . . . . . . eliminates a generator 1239#M TzEliminate( <Tietze record>, <gen> ) . . . . . eliminates generator gen 1240#M TzEliminate( <Tietze record>, <n> ) . . . . . . . eliminates n generators 1241## 1242## If a generator has been specified, then `TzEliminate' eliminates it if 1243## possible, i. e. if it can be isolated in some appropriate relator. If no 1244## generator has been specified , then `TzEliminate' eliminates some 1245## appropriate generator if possible and if the resulting total length of 1246## the relators will not exceed the parameter TzOptions(T).lengthLimit or 1247## the value 2^31-1. 1248## 1249InstallGlobalFunction( TzEliminate, function ( arg ) 1250 1251 local eliminations, gennum, n, numgens, numgenslimit, T, tietze; 1252 1253 # check the number of arguments. 1254 if Length( arg ) > 2 or Length( arg ) < 1 then 1255 Error( "usage: TzEliminate( <Tietze record> [, <generator> ] )" ); 1256 fi; 1257 1258 # check the first argument to be a Tietze record. 1259 T := arg[1]; 1260 TzCheckRecord( T ); 1261 TzTestInitialSetup(T); # run `1Or2Relators' if not yet done 1262 tietze := T!.tietze; 1263 1264 # get the arguments. 1265 gennum := 0; 1266 n := 1; 1267 if Length( arg ) = 2 then 1268 if IsInt( arg[2] ) then 1269 n := arg[2]; 1270 else 1271 gennum := Position( tietze[TZ_GENERATORS], arg[2] ); 1272 if gennum = fail then Error( 1273 "usage: TzEliminate( <Tietze record> [, <generator> ] )" ); 1274 fi; 1275 fi; 1276 fi; 1277 1278 if n = 1 then 1279 1280 # call the appropriate routine to eliminate one generator. 1281 if gennum = 0 then TzEliminateGen1( T ); 1282 else TzEliminateGen( T, gennum ); fi; 1283 if tietze[TZ_NUMREDUNDS] > 0 then TzRemoveGenerators( T ); fi; 1284 1285 # handle relators of length 1 or 2. 1286 TzHandleLength1Or2Relators( T ); 1287 1288 # sort the relators and print the status line. 1289 TzSort( T ); 1290 if TzOptions(T).printLevel >= 1 then TzPrintStatus( T, true ); fi; 1291 1292 else 1293 1294 # eliminate n generators. 1295 numgens := tietze[TZ_NUMGENS]; 1296 eliminations := TzOptions(T).eliminationsLimit; 1297 numgenslimit := TzOptions(T).generatorsLimit; 1298 TzOptions(T).eliminationsLimit := n; 1299 TzOptions(T).generatorsLimit := numgens - n; 1300 TzEliminateGens( T ); 1301 TzOptions(T).eliminationsLimit := eliminations; 1302 TzOptions(T).generatorsLimit := numgenslimit; 1303 fi; 1304end ); 1305 1306# eliminate generators by removing first those that ocur rarely, up to 1307# frequency lim 1308BindGlobal("TzEliminateRareOcurrences",function(pres,lim) 1309local prepare,gens,rels,sel,cnt,i,alde,freq; 1310 prepare:=function() 1311 local r,j,idx; 1312 gens:=List(pres!.generators,x->LetterRepAssocWord(x)[1]); 1313 rels:=pres!.tietze[TZ_RELATORS]; 1314 cnt:=List([1..Maximum(gens)],x->0); 1315 for r in rels do 1316 for j in r do 1317 j:=AbsInt(j); 1318 cnt[j]:=cnt[j]+1; 1319 od; 1320 od; 1321 sel:=[]; 1322 1323 repeat 1324 idx:=Filtered([1..Length(cnt)],x->cnt[x]>0 and cnt[x]<=freq); 1325 idx:=Difference(idx,alde); 1326 idx:=Difference(idx,sel); 1327 sel:=Concatenation(sel,idx); 1328 if Length(sel)<20 and freq<lim then 1329 freq:=freq+1; 1330 fi; 1331 until Length(sel)>=20 or freq=lim; 1332 1333 alde:=Union(alde,sel); 1334 end; 1335 1336 alde:=[]; 1337 TzSearch(pres); 1338 if Length(pres!.generators)=0 then return alde;fi; 1339 freq:=1; 1340 prepare(); 1341 while Length(sel)>0 do 1342 sel:=pres!.generators{sel}; 1343 for i in sel do 1344 #Print("elim ",i,"\n"); 1345 TzEliminateGen(pres,Position(pres!.generators,i)); 1346 od; 1347 TzHandleLength1Or2Relators(pres); 1348 TzSearchEqual(pres); 1349 TzFindCyclicJoins(pres); 1350 TzSearch(pres); 1351 if Length(pres!.generators)=0 then return alde;fi; 1352 prepare(); 1353 od; 1354 return alde; 1355end); 1356 1357 1358############################################################################# 1359## 1360#M TzEliminateFromTree( <Tietze record> ) . . eliminates the last generator 1361#M from the tree 1362## 1363## `TzEliminateFromTree' eliminates the last Tietze generator. If that 1364## generator cannot be isolated in any Tietze relator, then it's definition 1365## is taken from the tree and added as an additional Tietze relator, 1366## extending the set of Tietze generators appropriately, if necessary. 1367## However, the elimination will not be performed if the resulting total 1368## length of the relators cannot be guaranteed to not exceed the parameter 1369## TzOptions(T).lengthLimit or the value 2^31-1. 1370## 1371InstallGlobalFunction( TzEliminateFromTree, function ( T ) 1372 1373 local exp, factor, flags, gen, gens, i, invnum, invs, leng, length, 1374 lengths, num, numgens, numrels, occRelNum, occur, occTotal, pair, 1375 pair1, pointers, pos, primary, ptr, rel, rels, space, 1376 spacelimit, tietze, tree, treelength, treeNums, trlast, word; 1377 1378 # check the first argument to be a Presentation. 1379 if not IsPresentation( T ) then 1380 Error( "argument must be a Presentation" ); 1381 fi; 1382 TzTestInitialSetup(T); # run `1Or2Relators' if not yet done 1383 1384 # get some local variables. 1385 tietze := T!.tietze; 1386 gens := tietze[TZ_GENERATORS]; 1387 numgens := tietze[TZ_NUMGENS]; 1388 invs := tietze[TZ_INVERSES]; 1389 rels := tietze[TZ_RELATORS]; 1390 numrels := tietze[TZ_NUMRELS]; 1391 flags := tietze[TZ_FLAGS]; 1392 lengths := tietze[TZ_LENGTHS]; 1393 1394 # get some more local variables. 1395 tree := T!.tree; 1396 treelength := tree[TR_TREELENGTH]; 1397 primary := tree[TR_PRIMARY]; 1398 trlast := tree[TR_TREELAST]; 1399 treeNums := tree[TR_TREENUMS]; 1400 pointers := tree[TR_TREEPOINTERS]; 1401 1402 spacelimit := Minimum( TzOptions(T).lengthLimit, 2^31 - 1 ); 1403 tietze[TZ_MODIFIED] := false; 1404 occTotal := 0; 1405 1406 # get the number of the last occurring generator. 1407 while occTotal = 0 do 1408 1409 # get the number of the last generator. 1410 while trlast > primary and pointers[trlast] <= treelength do 1411 trlast := trlast - 1; 1412 od; 1413 tree[TR_TREELAST] := trlast; 1414 if trlast <= primary then return; fi; 1415 1416 # determine the number of occurrences of the last generator. 1417 num := pointers[trlast] - treelength; 1418 occur := TzOccurrences( tietze, num ); 1419 occTotal := occur[1][1]; 1420 1421 # if the last generator does not occur in the relators, mark it to 1422 # be redundant. 1423 if occTotal = 0 then 1424 invs[numgens+1-num] := 0; 1425 tietze[TZ_NUMREDUNDS] := tietze[TZ_NUMREDUNDS] + 1; 1426 trlast := trlast - 1; 1427 fi; 1428 od; 1429 1430 if occur[3][1] > 1 then 1431 1432 # print a message. 1433 if TzOptions(T).printLevel >= 2 then 1434 Print( "#I adding relator from tree position ", trlast, "\n" ); 1435 fi; 1436 1437 # get the defining word from the tree. 1438 pair := [ 0, 0 ]; 1439 for i in [ 1 .. 2 ] do 1440 1441 exp := 1; 1442 ptr := tree[i][trlast]; 1443 if ptr < 0 then 1444 exp := - exp; 1445 ptr := - ptr; 1446 fi; 1447 1448 if pointers[ptr] = ptr then 1449 # add this tree generator to the list of generators. 1450 gen := TzNewGenerator( T ); 1451 numgens := tietze[TZ_NUMGENS]; 1452 gens := tietze[TZ_GENERATORS]; 1453 invs := tietze[TZ_INVERSES]; 1454 treeNums[numgens] := ptr; 1455 pointers[ptr] := treelength + numgens; 1456 if TzOptions(T).printLevel >= 2 then 1457 Print( "#I adding generator ", gens[numgens], 1458 " from tree position ", ptr, "\n" ); 1459 fi; 1460 else 1461 # find this tree generator in the list of generators. 1462 while ptr > 0 and pointers[ptr] <= treelength do 1463 ptr := pointers[ptr]; 1464 if ptr < 0 then 1465 exp := - exp; 1466 ptr := - ptr; 1467 fi; 1468 od; 1469 fi; 1470 1471 # now get the generator number of the current factor. 1472 if ptr = 0 then 1473 factor := 0; 1474 else 1475 factor := pointers[ptr] - treelength; 1476 if treeNums[factor] < 0 then exp := - exp; fi; 1477 if exp < 0 then factor := invs[numgens+1+factor]; fi; 1478 fi; 1479 pair[i] := factor; 1480 od; 1481 1482 # invert the defining word, if necessary. 1483 if treeNums[num] < 0 then 1484 pair1 := pair[1]; 1485 pair[1] := invs[numgens+1+pair[2]]; 1486 pair[2] := invs[numgens+1+pair1]; 1487 fi; 1488 1489 # add the corresponding relator to the set of relators. 1490 invnum := invs[numgens+1+num]; 1491 if pair[1] = invs[numgens+1+pair[2]] then 1492 rel := [ invnum ]; leng := 1; 1493 elif pair[1] = 0 then 1494 rel := [ invnum, pair[2] ]; leng := 2; 1495 elif pair[2] = 0 then 1496 rel := [ invnum, pair[1] ]; leng := 2; 1497 else 1498 rel := [ invnum, pair[1], pair[2] ]; leng := 3; 1499 fi; 1500 numrels := numrels + 1; 1501 rels[numrels] := rel; 1502 lengths[numrels] := leng; 1503 flags[numrels] := 1; 1504 tietze[TZ_NUMRELS] := numrels; 1505 tietze[TZ_TOTAL] := tietze[TZ_TOTAL] + leng; 1506 tietze[TZ_MODIFIED] := true; 1507 tietze[TZ_OCCUR]:=false; 1508 1509 # if the new relator has length at most 2, handle it by calling the 1510 # appropriate subroutine, and then return. 1511 if leng <= 2 then 1512 TzHandleLength1Or2Relators( T ); 1513 trlast := trlast - 1; 1514 while trlast > primary and pointers[trlast] <= treelength do 1515 trlast := trlast - 1; 1516 od; 1517 tree[TR_TREELAST] := trlast; 1518 return; 1519 fi; 1520 1521 # else update the number of occurrences of the last generator, and 1522 # continue. 1523 occTotal := occTotal + 1; 1524 occur[1][1] := occTotal; 1525 occur[2][1] := numrels; 1526 occur[3][1] := 1; 1527 fi; 1528 1529 occRelNum := occur[2][1]; 1530 1531 length := lengths[occRelNum]; 1532 space := (occTotal - 1) * (length - 1) - length; 1533 1534 if tietze[TZ_TOTAL] + space <= spacelimit then 1535 1536 # find the substituting word. 1537 gen := num; 1538 rel := rels[occRelNum]; 1539 length := lengths[occRelNum]; 1540 pos := Position( rel, gen ); 1541 if pos = fail then 1542 gen := -gen; 1543 pos := Position( rel, gen ); 1544 fi; 1545 word := Concatenation( rel{ [pos+1..length] }, rel{ [1..pos-1] } ); 1546 1547 # replace all occurrences of gen by word^-1. 1548 if TzOptions(T).printLevel >= 2 then 1549 Print( "#I eliminating ", gens[num], " = " ); 1550 if gen > 0 then 1551 Print( AbstractWordTietzeWord( word, gens )^-1, "\n"); 1552 else 1553 Print( AbstractWordTietzeWord( word, gens ), "\n" ); 1554 fi; 1555 fi; 1556 TzSubstituteGen( tietze, -gen, word ); 1557 1558 # mark gen to be redundant. 1559 invs[numgens+1-num] := 0; 1560 tietze[TZ_NUMREDUNDS] := tietze[TZ_NUMREDUNDS] + 1; 1561 tietze[TZ_MODIFIED] := true; 1562 tietze[TZ_OCCUR]:=false; 1563 trlast := trlast - 1; 1564 while trlast > primary and pointers[trlast] <= treelength do 1565 trlast := trlast - 1; 1566 od; 1567 tree[TR_TREELAST] := trlast; 1568 elif TzOptions(T).printLevel >= 1 then 1569 Print( "#I replacement of generators stopped by length limit\n" ); 1570 fi; 1571end ); 1572 1573 1574############################################################################# 1575## 1576#M TzEliminateGen( <Tietze record>, <n> ) . . . eliminates the nth generator 1577## 1578## `TzEliminateGen' eliminates the Tietze generator tietze[TZ_GENERATORS][n] 1579## if possible, i. e. if that generator can be isolated in some appropriate 1580## Tietze relator. However, the elimination will not be performed if the 1581## resulting total length of the relators cannot be guaranteed to not exceed 1582## the parameter TzOptions(T).lengthLimit or the value 2^31-1. 1583## 1584InstallGlobalFunction( TzEliminateGen, function ( T, num ) 1585 1586 local gen, gens, invs, length, lengths, numgens, numrels, occRelNum, 1587 occur, occTotal, pos, rel, rels, space, spacelimit, tietze, word; 1588 1589 # check the first argument to be a Presentation. 1590 if not IsPresentation( T ) then 1591 Error( "argument must be a Presentation" ); 1592 fi; 1593 TzTestInitialSetup(T); # run `1Or2Relators' if not yet done 1594 tietze := T!.tietze; 1595 spacelimit := Minimum( TzOptions(T).lengthLimit, 2^31 - 1 ); 1596 1597 tietze[TZ_MODIFIED] := false; 1598 1599 gens := tietze[TZ_GENERATORS]; 1600 numgens := tietze[TZ_NUMGENS]; 1601 invs := tietze[TZ_INVERSES]; 1602 rels := tietze[TZ_RELATORS]; 1603 numrels := tietze[TZ_NUMRELS]; 1604 lengths := tietze[TZ_LENGTHS]; 1605 1606 # check the second argument to be a generator number in range. 1607 if not IsInt( num ) or num <= 0 or num > numgens then Error( 1608 "TzEliminateGen: second argument is not a valid generator number" ); 1609 fi; 1610 1611 # determine the number of occurrences of the given generator. 1612 occur := TzOccurrences( tietze, num ); 1613 occTotal := occur[1][1]; 1614 if occTotal > 0 and occur[3][1] = 1 then 1615 1616 occRelNum := occur[2][1]; 1617 1618 length := lengths[occRelNum]; 1619 space := (occTotal - 1) * (length - 1) - length; 1620 1621 if tietze[TZ_TOTAL] + space <= spacelimit then 1622 1623 # if there is a tree of generators and if the generator to be 1624 # deleted is not the last generator, then delete the tree. 1625 if num < numgens and IsBound( T!.tree ) then 1626 Unbind( T!.tree ); 1627 fi; 1628 1629 # find the substituting word. 1630 gen := num; 1631 rel := rels[occRelNum]; 1632 length := lengths[occRelNum]; 1633 pos := Position( rel, gen ); 1634 if pos = fail then 1635 gen := -gen; 1636 pos := Position( rel, gen ); 1637 fi; 1638 word := Concatenation( rel{ [pos+1..length] }, 1639 rel{ [1..pos-1] } ); 1640 1641 # replace all occurrences of gen by word^-1. 1642 if TzOptions(T).printLevel >= 2 then 1643 Print( "#I eliminating ", gens[num], " = " ); 1644 if gen > 0 then 1645 Print( AbstractWordTietzeWord( word, gens )^-1, "\n" ); 1646 else 1647 Print( AbstractWordTietzeWord( word, gens ), "\n" ); 1648 fi; 1649 fi; 1650 TzSubstituteGen( tietze, -gen, word ); 1651 1652 # update the generator images, if available. 1653 if IsBound( T!.imagesOldGens ) then 1654 if gen > 0 then word := -1 * Reversed( word ); fi; 1655 TzUpdateGeneratorImages( T, num, word ); 1656 fi; 1657 1658 # mark gen to be redundant. 1659 invs[numgens+1-num] := 0; 1660 tietze[TZ_NUMREDUNDS] := tietze[TZ_NUMREDUNDS] + 1; 1661 tietze[TZ_MODIFIED] := true; 1662 tietze[TZ_OCCUR]:=false; 1663 elif TzOptions(T).printLevel >= 1 then 1664 Print( "#I replacement of generators stopped by length limit\n" ); 1665 fi; 1666 fi; 1667end ); 1668 1669 1670############################################################################# 1671## 1672#M TzEliminateGen1( <Tietze record> ) . . . . . . . eliminates a generator 1673## 1674## `TzEliminateGen1' tries to eliminate a Tietze generator: If there are 1675## Tietze generators which occur just once in certain Tietze relators, then 1676## one of them is chosen for which the product of the length of its minimal 1677## defining word and the number of its occurrences is minimal. However, 1678## the elimination will not be performed if the resulting total length of 1679## the relators cannot be guaranteed to not exceed the parameter 1680## TzOptions(T).lengthLimit or the value 2^31-1. 1681## 1682InstallGlobalFunction( TzEliminateGen1, function ( T ) 1683 1684 local gen, gens, i,j, invs, ispace, length, lengths, modified, num, 1685 numgens, numrels, occur, occMultiplicities, occRelNum, occRelNums, 1686 occTotals, pos, protected, rel, rels, space, spacelimit, tietze, 1687 total, word,k,max,oldlen,bestlen,stoplen,oldrels,changed,olen; 1688 1689 # check the given argument to be a Presentation. 1690 if not IsPresentation( T ) then 1691 Error( "argument must be a Presentation" ); 1692 fi; 1693 TzTestInitialSetup(T); # run `1Or2Relators' if not yet done 1694 tietze := T!.tietze; 1695 protected := TzOptions(T).protected; 1696 spacelimit := Minimum( TzOptions(T).lengthLimit, 2^31 - 1 ); 1697 1698 gens := tietze[TZ_GENERATORS]; 1699 numgens := tietze[TZ_NUMGENS]; 1700 invs := tietze[TZ_INVERSES]; 1701 rels := tietze[TZ_RELATORS]; 1702 oldrels:=ShallowCopy(rels); 1703 #oldrels1:=List(rels,ShallowCopy); 1704 numrels := tietze[TZ_NUMRELS]; 1705 lengths := tietze[TZ_LENGTHS]; 1706 1707 if not IsList(tietze[TZ_OCCUR]) then 1708 occur := TzOccurrences( tietze ); 1709 else 1710 occur :=tietze[TZ_OCCUR]; 1711 #Print("used\n"); 1712 fi; 1713#OLD_OCCUR:=List(occur,ShallowCopy); 1714 occTotals := occur[1]; 1715 occRelNums := occur[2]; 1716 occMultiplicities := occur[3]; 1717 oldlen:=ShallowCopy(tietze[TZ_LENGTHS]); 1718 1719#NEW_OCCUR:=TzOccurrences(tietze); 1720#if occTotals<>false and occTotals <> NEW_OCCUR[1] then 1721#Error("cla1"); 1722#elif occTotals<>false and occRelNums <> NEW_OCCUR[2] then 1723#Error("cla2"); 1724#elif occTotals<>false and occMultiplicities <> NEW_OCCUR[3] then 1725# Error("cla3"); fi; 1726 1727 modified := false; 1728 num := 0; 1729 space := 0; 1730 1731 for i in [ protected + 1 .. numgens ] do 1732 if IsBound( occMultiplicities[i] ) and occMultiplicities[i] = 1 then 1733 total := occTotals[i]; 1734 length := lengths[occRelNums[i]]; 1735 ispace := (total - 1) * (length - 1) - length; 1736 if num = 0 or ispace <= space then 1737 num := i; 1738 space := ispace; 1739 fi; 1740 fi; 1741 od; 1742 1743 if num > 0 then 1744 if tietze[TZ_TOTAL] + space <= spacelimit then 1745 1746 # if there is a tree of generators and if the generator to be deleted 1747 # is not the last generator, then delete the tree. 1748 if num < numgens and IsBound( T!.tree ) then 1749 Unbind( T!.tree ); 1750 fi; 1751 1752 # find the substituting word. 1753 gen := num; 1754 occRelNum := occRelNums[num]; 1755 rel := rels[occRelNum]; 1756 length := lengths[occRelNum]; 1757 pos := Position( rel, gen ); 1758 if pos = fail then 1759 gen := -gen; 1760 pos := Position( rel, gen ); 1761 fi; 1762 word := Concatenation( rel{ [pos+1..length] }, rel{ [1..pos-1] } ); 1763 1764 # replace all occurrences of gen by word^-1. 1765 if TzOptions(T).printLevel >= 2 then 1766 Print( "#I eliminating ", gens[num], " = " ); 1767 if gen > 0 then 1768 Print( AbstractWordTietzeWord( word, gens )^-1, "\n" ); 1769 else 1770 Print( AbstractWordTietzeWord( word, gens ), "\n" ); 1771 fi; 1772 fi; 1773 changed:=TzSubstituteGen( tietze, -gen, word ); 1774 #if Length(changed)>100 then Error("longchanged!!"); fi; 1775 #if oldrels1<>oldrels then Error("differ!"); fi; 1776 1777 # update the generator images, if available. 1778 if IsBound( T!.imagesOldGens ) then 1779 if gen > 0 then word := -1 * Reversed( word ); fi; 1780 TzUpdateGeneratorImages( T, num, word ); 1781 fi; 1782 1783 # mark gen to be redundant. 1784 invs[numgens+1-num] := 0; 1785 tietze[TZ_NUMREDUNDS] := tietze[TZ_NUMREDUNDS] + 1; 1786 1787 #update occurrence numbers 1788 gen:=AbsInt(gen); 1789 Unbind(occRelNums[num]); 1790 Unbind(occMultiplicities[num]); 1791 occTotals[gen]:=0; 1792 1793 # now check whether the data for the other generators is still OK 1794 # and correct if necessary 1795 rels:=tietze[TZ_RELATORS]; 1796 for i in [1..numgens] do 1797 1798 if IsBound(occRelNums[i]) then 1799 # verify that the relator we store for the shortest 1800 #length is still OK. 1801 num:=occMultiplicities[i]; 1802 olen:=oldlen[occRelNums[i]]; 1803 1804 #What can happen is two things: 1805 #a) A changed relator now is shorter and better. If so we take it 1806 #b) The best relator got changed and now is not best any more. 1807 1808 # first check the changed relators, whether they give any 1809 # improvement 1810 for j in changed do 1811 total:=0; 1812 for k in rels[j] do 1813 if AbsInt(k)=i then total:=total+1;fi; 1814 od; 1815 #if total>0 then Print(j,":",i,":",total,"\n");fi; 1816 if total>0 and 1817 (total<num or 1818 (total=num and Length(rels[j])<olen) or 1819 (total=num and Length(rels[j])=olen and j<occRelNums[i]) 1820 ) then 1821 # found a better one 1822 pos:=j; 1823 num:=total; 1824 olen:=Length(rels[j]); 1825 occMultiplicities[i]:=false; # force change 1826 fi; 1827 1828 #update occurrence numbers 1829 # because of cancellation, we need to check with the changed 1830 # relators vs. their old selves 1831 for k in oldrels[j] do 1832 if AbsInt(k)=i then total:=total-1;fi; 1833 od; 1834 occTotals[i]:=occTotals[i]+total; 1835 1836 od; 1837 1838 if num<>occMultiplicities[i] or 1839 olen<>oldlen[occRelNums[i]] then 1840 occMultiplicities[i]:=num; 1841 occRelNums[i]:=pos; 1842 else 1843 # the changed relators did not give any improvement. We thus 1844 # need to check whether the best stored got worse 1845 if occRelNums[i] in changed then 1846 total:=0; 1847 for k in rels[occRelNums[i]] do 1848 if AbsInt(k)=i then total:=total+1;fi; 1849 od; 1850 if total=0 or total>num or 1851 Length(rels[occRelNums[i]])>oldlen[occRelNums[i]] then 1852 #Print("fixin' ",i,"\n"); 1853 # the relator changed and might not be good anymore. We 1854 # need to find another one. 1855 1856 #TODO: Be more clever in checking the later relators first 1857 num:=infinity; 1858 olen:=infinity; 1859 pos:=fail; 1860 for j in [1..Length(rels)] do 1861 total:=0; 1862 for k in rels[j] do 1863 if AbsInt(k)=i then total:=total+1;fi; 1864 od; 1865 if total>0 and 1866 (total<num or (total=num and Length(rels[j])<olen)) then 1867 # found a better one 1868 pos:=j; 1869 num:=total; 1870 olen:=Length(rels[j]); 1871 fi; 1872 od; 1873 #Print("fixing ",i," from ",num,"\n"); 1874 if pos=fail then 1875 Unbind(occRelNums[i]); 1876 Unbind(occMultiplicities[i]); 1877 else 1878 occRelNums[i]:=pos; 1879 occMultiplicities[i]:=num; 1880 fi; 1881 1882 fi; 1883 fi; 1884 fi; 1885 1886 fi; 1887 od; 1888 1889 modified := true; 1890 elif TzOptions(T).printLevel >= 1 then 1891 Print( "#I replacement of generators stopped by length limit\n" ); 1892 fi; 1893 1894 #NEW_OCCUR:=TzOccurrences(tietze); 1895 #if occTotals<>false and occTotals <> NEW_OCCUR[1] then 1896 #Error("bla1"); 1897 # elif occTotals<>false and occRelNums <> NEW_OCCUR[2] then 1898 #Error("bla2"); 1899 # elif occTotals<>false and occMultiplicities <> NEW_OCCUR[3] then 1900 # Error("bla3"); fi; 1901 fi; 1902 1903 tietze[TZ_MODIFIED] := modified; 1904 if 0 in occTotals then 1905 # code might not work if generators vanish. 1906 tietze[TZ_OCCUR]:=false; 1907 else 1908 tietze[TZ_OCCUR]:=[occTotals,occRelNums,occMultiplicities]; 1909 fi; 1910 1911 #if tietze[TZ_OCCUR]<>TzOccurrences(tietze) then Error("occur!"); fi; 1912 1913end ); 1914 1915 1916############################################################################# 1917## 1918#M TzEliminateGens( <Tietze record> [, <decode>] ) . Eliminates generators 1919## 1920## `TzEliminateGens' repeatedly eliminates generators from the presentation 1921## of the given group until at least one of the following conditions is 1922## violated: 1923## 1924## (1) The current number of generators is greater than the parameter 1925## TzOptions(T).generatorsLimit. 1926## (2) The number of generators eliminated so far is less than 1927## the parameter TzOptions(T).eliminationsLimit. 1928## (3) The total length of the relators has not yet grown to a percentage 1929## greater than the parameter TzOptions(T).expandLimit. 1930## (4) The next elimination will not extend the total length to a value 1931## greater than the parameter TzOptions(T).lengthLimit or the value 1932## 2^31-1. 1933## 1934## If a second argument has been specified, then it is assumed that we 1935## are in the process of decoding a tree. 1936## 1937## If not, then the function will not eliminate any protected generators. 1938## 1939InstallGlobalFunction( TzEliminateGens, function ( arg ) 1940 1941 local bound, decode, maxnum, modified, num, redundantsLimit, T, tietze; 1942 1943 # check the number of arguments. 1944 if Length( arg ) > 2 or Length( arg ) < 1 then 1945 Error( "usage: TzEliminateGens( <Tietze record> [, <decode> ] )" ); 1946 fi; 1947 1948 # check the first argument to be a Tietze record. 1949 T := arg[1]; 1950 TzCheckRecord( T ); 1951 TzTestInitialSetup(T); # run `1Or2Relators' if not yet done 1952 1953 if TzOptions(T).printLevel >= 3 then 1954 Print( "#I eliminating generators\n" ); 1955 fi; 1956 1957 # get the second argument. 1958 decode := Length( arg ) = 2; 1959 1960 tietze := T!.tietze; 1961 redundantsLimit := 5; 1962 maxnum := TzOptions(T).eliminationsLimit; 1963 bound := tietze[TZ_TOTAL] * (TzOptions(T).expandLimit / 100); 1964 modified := false; 1965 tietze[TZ_MODIFIED] := true; 1966 num := 0; 1967 while tietze[TZ_MODIFIED] and num < maxnum and 1968 tietze[TZ_TOTAL] <= bound and 1969 tietze[TZ_NUMGENS] - tietze[TZ_NUMREDUNDS] > TzOptions(T).generatorsLimit do 1970 if decode then 1971 TzEliminateFromTree( T ); 1972 else 1973 TzEliminateGen1( T ); 1974 fi; 1975 if tietze[TZ_NUMREDUNDS] = redundantsLimit then 1976 TzRemoveGenerators( T ); 1977 fi; 1978 modified := modified or tietze[TZ_MODIFIED]; 1979 num := num + 1; 1980 od; 1981 tietze[TZ_MODIFIED] := modified; 1982 if tietze[TZ_NUMREDUNDS] > 0 then TzRemoveGenerators( T ); fi; 1983 1984 if modified then 1985 # handle relators of length 1 or 2. 1986 TzHandleLength1Or2Relators( T ); 1987 # sort the relators and print the status line. 1988 TzSort( T ); 1989 if TzOptions(T).printLevel >= 2 then TzPrintStatus( T, true ); fi; 1990 fi; 1991end ); 1992 1993 1994############################################################################# 1995## 1996#M TzFindCyclicJoins( <Tietze record> ) . . . . . . handle cyclic subgroups 1997## 1998## `TzFindCyclicJoins' searches for power and commutator relators in order 1999## to find pairs of generators which generate a common cyclic subgroup. 2000## It uses these pairs to introduce new relators, but it does not introduce 2001## any new generators as is done by `TzSubstituteCyclicJoins'. 2002## 2003InstallGlobalFunction( TzFindCyclicJoins, function ( T ) 2004 2005 local e, exp, exponents, fac, flags, gen, gens, ggt, i, invs, j, k, l, 2006 length, lengths, n, newstart, next, num, numgens, numrels, prev, 2007 powers, rel, rels, tietze, word; 2008 2009 if TzOptions(T).printLevel >= 3 then 2010 Print( "#I searching for cyclic joins\n" ); 2011 fi; 2012 2013 # check the given argument to be a Tietze record. 2014 TzCheckRecord( T ); 2015 TzTestInitialSetup(T); # run `1Or2Relators' if not yet done 2016 tietze := T!.tietze; 2017 tietze[TZ_MODIFIED] := false; 2018 2019 # start the routine and repeat it whenever a generator has been 2020 # eliminated. 2021 newstart := true; 2022 while newstart do 2023 2024 # try to find exponents for the generators. 2025 exponents := TzGeneratorExponents( T ); 2026 if Sum( exponents ) = 0 then return; fi; 2027 2028 # initialize some local variables. 2029 newstart := false; 2030 gens := tietze[TZ_GENERATORS]; 2031 numgens := tietze[TZ_NUMGENS]; 2032 rels := tietze[TZ_RELATORS]; 2033 numrels := tietze[TZ_NUMRELS]; 2034 lengths := tietze[TZ_LENGTHS]; 2035 invs := tietze[TZ_INVERSES]; 2036 flags := tietze[TZ_FLAGS]; 2037 2038 # now work off all commutator relators of length 4. 2039 i := 0; 2040 while i < numrels do 2041 2042 # find the next commutator. 2043 i := i + 1; 2044 rel := rels[i]; 2045 if lengths[i] = 4 and rel[1] = invs[numgens+1+rel[3]] and 2046 rel[2] = invs[numgens+1+rel[4]] then 2047 2048 # There is a commutator relator of the form [a,b]. Check if 2049 # there are also power relators of the form a^m or b^n. 2050 2051 num := [ AbsInt( rel[1] ), AbsInt( rel[2] ) ]; 2052 exp := [ exponents[num[1]], exponents[num[2]] ]; 2053 fac := [ 0, 0 ]; 2054 e := [ 0, 0 ]; 2055 2056 # If there is at least one relator of the form a^m or b^n, then 2057 # search for a relator of the form a^s * b^t (modulo [a,b]) 2058 # with s prime to m or t prime to n, respectively. For, if s is 2059 # prime to m, then we can use the Euclidean algorithm to 2060 # express a as a power of b and then eliminate a. 2061 2062 if exp[1] > 0 or exp[2] > 0 then 2063 2064 j := 0; 2065 while j < numrels do 2066 2067 # get the next relator. 2068 j := j + 1; 2069 if lengths[j] > 0 and j <> i then 2070 rel := rels[j]; 2071 2072 # check whether rel is a word in a and b. 2073 length := lengths[j]; 2074 e[1] := 0; 2075 e[2] := 0; 2076 powers := 0; 2077 prev := 0; 2078 l := 0; 2079 while l < length do 2080 l := l + 1; 2081 next := rel[l]; 2082 if next <> prev then 2083 powers := powers + 1; 2084 prev := next; 2085 fi; 2086 if next = num[1] then e[1] := e[1] + 1; 2087 elif next = num[2] then e[2] := e[2] + 1; 2088 elif next = -num[1] then e[1] := e[1] - 1; 2089 elif next = -num[2] then e[2] := e[2] - 1; 2090 else l := length + 1; 2091 fi; 2092 od; 2093 2094 if l = length and powers > 1 then 2095 2096 # reduce exponents, if possible. 2097 for k in [ 1, 2 ] do 2098 fac[k] := num[k]; 2099 if exp[k] > 0 then 2100 e[k] := e[k] mod exp[k]; 2101 if e[k] > exp[k]/2 then 2102 e[k] := exp[k] - e[k]; 2103 fac[k] := - fac[k]; 2104 fi; 2105 elif e[k] < 0 then 2106 e[k] := - e[k]; 2107 fac[k] := - fac[k]; 2108 fi; 2109 if fac[k] < 0 then 2110 fac[k] := invs[numgens+1-fac[k]]; 2111 fi; 2112 od; 2113 2114 # now the e[k] are non-negative. 2115 for k in [ 1, 2 ] do 2116 if e[k] > 0 and e[3-k] = 0 then 2117 exp[k] := GcdInt( e[k], exp[k] ); 2118 if exp[k] <> exponents[num[k]] then 2119 exponents[num[k]] := exp[k]; 2120 e[k] := exp[k]; 2121 fi; 2122 fi; 2123 od; 2124 2125 # reduce the current relator, if possible. 2126 if e[1] + e[2] < length or powers > 2 then 2127 rel := [ ]; 2128 if e[1] > 0 then rel := Concatenation( 2129 rel, ListWithIdenticalEntries( e[1], fac[1] ) ); 2130 fi; 2131 if e[2] > 0 then rel := Concatenation( 2132 rel, ListWithIdenticalEntries( e[2], fac[2] ) ); 2133 fi; 2134 rels[j] := rel; 2135 lengths[j] := e[1] + e[2]; 2136 tietze[TZ_TOTAL] := tietze[TZ_TOTAL] - length 2137 + lengths[j]; 2138 flags[j] := 1; 2139 tietze[TZ_MODIFIED] := true; 2140 if TzOptions(T).printLevel >= 3 then Print( 2141 "#I rels[",j,"] reduced to ",rels[j],"\n" ); 2142 fi; 2143 fi; 2144 2145 # try to find a generator that can be deleted. 2146 if e[1] = 1 then n := num[1]; 2147 elif e[2] = 1 then n := num[2]; 2148 else n := 0; 2149 for k in [ 1, 2 ] do 2150 if n = 0 and e[k] > 1 and 2151 GcdInt( e[k], exp[k] ) = 1 then 2152 ggt := Gcdex( e[k], exp[k] ); 2153 gen := [gens[num[1]], gens[num[2]]]; 2154 if fac[1] < 0 then gen[1] := gen[1]^-1; fi; 2155 if fac[2] < 0 then gen[2] := gen[2]^-1; fi; 2156 word := gen[k] * gen[3-k]^(e[3-k]*ggt.coeff1); 2157 AddRelator( T, word ); 2158 numrels := tietze[TZ_NUMRELS]; 2159 n := num[k]; 2160 fi; 2161 od; 2162 fi; 2163 2164 # eliminate a generator if it is possible and allowed. 2165 if n <> 0 and TzOptions(T).generatorsLimit < numgens then 2166 TzEliminate( T ); 2167 tietze[TZ_MODIFIED] := true; 2168 j := numrels; 2169 i := numrels; 2170 if tietze[TZ_NUMGENS] < numgens then 2171 newstart := true; 2172 fi; 2173 fi; 2174 fi; 2175 fi; 2176 od; 2177 fi; 2178 fi; 2179 od; 2180 od; 2181 2182 if tietze[TZ_MODIFIED] then 2183 tietze[TZ_OCCUR]:=false; 2184 # handle relators of length 1 or 2. 2185 TzHandleLength1Or2Relators( T ); 2186 # sort the relators and print the status line. 2187 TzSort( T ); 2188 if TzOptions(T).printLevel >= 1 then TzPrintStatus( T, true ); fi; 2189 fi; 2190end ); 2191 2192 2193############################################################################# 2194## 2195#M TzGeneratorExponents( <Tietze record> ) . . . list of generator exponents 2196## 2197## `TzGeneratorExponents' tries to find exponents for the Tietze generators 2198## and return them in a list parallel to the list of the generators. 2199## 2200InstallGlobalFunction( TzGeneratorExponents, function ( T ) 2201 2202 local exp, exponents, flags, i, invs, j, length, lengths, num, num1, 2203 numgens, numrels, rel, rels, tietze; 2204 2205 # check the given argument to be a Presentation. 2206 if not IsPresentation( T ) then 2207 Error( "argument must be a Presentation" ); 2208 fi; 2209 2210 if TzOptions(T).printLevel >= 3 then 2211 Print( "#I trying to find generator exponents\n" ); 2212 fi; 2213 TzTestInitialSetup(T); # run `1Or2Relators' if not yet done 2214 2215 tietze := T!.tietze; 2216 2217 numgens := tietze[TZ_NUMGENS]; 2218 rels := tietze[TZ_RELATORS]; 2219 numrels := tietze[TZ_NUMRELS]; 2220 lengths := tietze[TZ_LENGTHS]; 2221 invs := tietze[TZ_INVERSES]; 2222 flags := tietze[TZ_FLAGS]; 2223 2224 # Initialize the exponents list. 2225 exponents := ListWithIdenticalEntries( numgens, 0 ); 2226 2227 # Find all relators which are powers of a single generator. 2228 for i in [ 1 .. numrels ] do 2229 if lengths[i] > 0 then 2230 rel := rels[i]; 2231 length := lengths[i]; 2232 num1 := rel[1]; 2233 j := 2; 2234 while j <= length and rel[j] = num1 do j := j + 1; od; 2235 if j > length then 2236 num := AbsInt( num1 ); 2237 if exponents[num] = 0 then exp := length; 2238 else exp := GcdInt( exponents[num], length ); fi; 2239 exponents[num] := exp; 2240 if exp < length then 2241 rels[i] := ListWithIdenticalEntries( exp, num ); 2242 lengths[i] := exp; 2243 tietze[TZ_TOTAL] := tietze[TZ_TOTAL] - length + exp; 2244 flags[i] := 1; 2245 tietze[TZ_MODIFIED] := true; 2246 tietze[TZ_OCCUR]:=false; 2247 elif num1 < 0 then 2248 rels[i] := List( rel, num -> -num ); 2249 fi; 2250 fi; 2251 fi; 2252 od; 2253 2254 return exponents; 2255end ); 2256 2257 2258############################################################################# 2259## 2260#M TzGo( <Tietze record> [, <silent> ) . . . . . run Tietze transformations 2261## 2262## `TzGo' automatically performs suitable Tietze transformations of the 2263## presentation in the given Tietze record. 2264## 2265## If "silent" is specified as true, then the printing of the status line 2266## by `TzGo' is suppressed if the Tietze option `printLevel' (see "Tietze 2267## Options") has a value less than 2. 2268## 2269## rels is the set of relators. 2270## gens is the set of generators. 2271## total is the total length of all relators. 2272## 2273InstallGlobalFunction( TzGo, function ( arg ) 2274 2275 local count, looplimit, printstatus, T, tietze; 2276 2277 # get the arguments. 2278 T := arg[1]; 2279 printstatus := TzOptions(T).printLevel = 1 and 2280 not ( Length( arg ) > 1 and IsBool( arg[2] ) and arg[2] ); 2281 2282 # check the first argument to be a Presentation. 2283 if not IsPresentation( T ) then 2284 Error( "argument must be a Presentation" ); 2285 fi; 2286 TzTestInitialSetup(T); # run `1Or2Relators' if not yet done 2287 tietze := T!.tietze; 2288 2289 # substitute substrings by shorter ones. 2290 TzSearch( T ); 2291 2292 # now run our standard strategy and repeat it. 2293 looplimit := TzOptions(T).loopLimit; 2294 count := 0; 2295 while count < looplimit and tietze[TZ_TOTAL] > 0 do 2296 2297 # replace substrings by substrings of equal length. 2298 TzSearchEqual( T ); 2299 if tietze[TZ_MODIFIED] then TzSearch( T ); fi; 2300 2301 # eliminate generators. 2302 TzEliminateGens( T ); 2303 if tietze[TZ_MODIFIED] then 2304 TzSearch( T ); 2305 count := count + 1; 2306 else 2307 count := looplimit; 2308 fi; 2309 2310 if printstatus then TzPrintStatus( T, true ); fi; 2311 od; 2312 2313 # try to find cyclic subgroups by looking at power and commutator 2314 # relators. 2315 if tietze[TZ_TOTAL] > 0 then 2316 TzFindCyclicJoins( T ); 2317 if tietze[TZ_MODIFIED] then TzSearch( T ); fi; 2318 if printstatus then TzPrintStatus( T, true ); fi; 2319 fi; 2320 2321end ); 2322 2323 2324############################################################################# 2325## 2326#M TzGoGo( <Tietze record> ) . . . . . run the Tietze go command repeatedly 2327## 2328## `TzGoGo' calls the `TzGo' command again and again until it does not 2329## reduce the presentation any more. `TzGo' automatically performs suitable 2330## Tietze transformations of the presentation in the given Tietze record. 2331## 2332## rels is the set of relators. 2333## gens is the set of generators. 2334## total is the total length of all relators. 2335## 2336InstallGlobalFunction( TzGoGo, function ( T ) 2337 2338 local count, numgens, numrels, silentGo, tietze, total; 2339 2340 # check the given argument to be a Presentation. 2341 if not IsPresentation( T ) then 2342 Error( "argument must be a Presentation" ); 2343 fi; 2344 TzTestInitialSetup(T); # run `1Or2Relators' if not yet done 2345 2346 # initialize the local variables. 2347 tietze := T!.tietze; 2348 numgens := tietze[TZ_NUMGENS]; 2349 numrels := tietze[TZ_NUMRELS]; 2350 total := tietze[TZ_TOTAL]; 2351 silentGo := TzOptions(T).printLevel = 1; 2352 count := 0; 2353 2354 #loop over the Tietze transformations. 2355 while count < 5 do 2356 TzGo( T, silentGo ); 2357 count := count + 1; 2358 if silentGo and ( tietze[TZ_NUMGENS] < numgens or 2359 tietze[TZ_NUMRELS] < numrels ) then 2360 TzPrintStatus( T, true ); 2361 fi; 2362 if tietze[TZ_NUMGENS] < numgens or tietze[TZ_NUMRELS] < numrels or 2363 tietze[TZ_TOTAL] < total then 2364 numgens := tietze[TZ_NUMGENS]; 2365 numrels := tietze[TZ_NUMRELS]; 2366 total := tietze[TZ_TOTAL]; 2367 count := 0; 2368 fi; 2369 od; 2370 2371 if silentGo then TzPrintStatus( T, true ); fi; 2372end ); 2373 2374 2375############################################################################# 2376## 2377#M TzHandleLength1Or2Relators( <Tietze record> ) . . . handle short relators 2378## 2379## `TzHandleLength1Or2Relators' searches for relators of length 1 or 2 and 2380## performs suitable Tietze transformations for each of them: 2381## 2382## Generators occurring in relators of length 1 are eliminated. 2383## 2384## Generators occurring in square relators of length 2 are marked to be 2385## involutions. 2386## 2387## If a relator of length 2 involves two different generators, then the 2388## generator with the larger number is substituted by the other one in all 2389## relators and finally eliminated from the set of generators. 2390## 2391InstallGlobalFunction( TzHandleLength1Or2Relators, function ( T ) 2392 2393 local absrep2, done, flags, gens, i, idword, invs, length, lengths, 2394 numgens, numgens1, numrels, pointers, protected, ptr, ptr1, ptr2, 2395 redunds, rels, rep, rep1, rep2, tietze, tracingImages, tree, 2396 treelength, treeNums,topl; 2397 2398 topl:=TzOptions(T).printLevel; 2399 if topl >= 3 then Print( "#I handling short relators\n" ); fi; 2400 2401 # check the given argument to be a Presentation. 2402 if not IsPresentation( T ) then 2403 Error( "argument must be a Presentation" ); 2404 fi; 2405 tietze := T!.tietze; 2406 protected := TzOptions(T).protected; 2407 tracingImages := IsBound( T!.imagesOldGens ); 2408 2409 gens := tietze[TZ_GENERATORS]; 2410 invs := tietze[TZ_INVERSES]; 2411 rels := tietze[TZ_RELATORS]; 2412 lengths := tietze[TZ_LENGTHS]; 2413 flags := tietze[TZ_FLAGS]; 2414 numgens := tietze[TZ_NUMGENS]; 2415 numrels := tietze[TZ_NUMRELS]; 2416 redunds := tietze[TZ_NUMREDUNDS]; 2417 numgens1 := numgens + 1; 2418 done := false; 2419 idword := One(T); 2420 2421 tree := 0; 2422 if IsBound( T!.tree ) then 2423 tree := T!.tree; 2424 treelength := tree[TR_TREELENGTH]; 2425 pointers := tree[TR_TREEPOINTERS]; 2426 treeNums := tree[TR_TREENUMS]; 2427 fi; 2428 2429 while not done do 2430 2431 done := true; 2432 2433 # loop over all relators and find those of length 1 or 2. 2434 i := 0; 2435 while i < numrels do 2436 i := i + 1; 2437 length := lengths[i]; 2438 if length <= 2 and length > 0 and flags[i] <= 2 then 2439 2440 # find the current representative of the first factor. 2441 rep1 := rels[i][1]; 2442 while invs[numgens1-rep1] <> rep1 do 2443 rep1 := invs[numgens1-rep1]; 2444 od; 2445 2446 if length = 1 then 2447 2448 # handle a relator of length 1. 2449 rep1 := AbsInt( rep1 ); 2450 if rep1 > protected then 2451 # eliminate generator rep1. 2452 invs[numgens1-rep1] := 0; 2453 invs[numgens1+rep1] := 0; 2454 if tree <> 0 then 2455 ptr1 := AbsInt( treeNums[rep1] ); 2456 pointers[ptr1] := 0; 2457 treeNums[rep1] := 0; 2458 fi; 2459 if topl >= 2 then 2460 Print( "#I eliminating ", gens[rep1], 2461 " = idword\n" ); 2462 fi; 2463 # update the generator images, if available. 2464 if tracingImages then 2465 TzUpdateGeneratorImages( T, rep1, [] ); 2466 fi; 2467 redunds := redunds + 1; 2468 done := false; 2469 fi; 2470 else 2471 2472 # find the current representative of the second factor. 2473 rep2 := rels[i][2]; 2474 while invs[numgens1-rep2] <> rep2 do 2475 rep2 := invs[numgens1-rep2]; 2476 od; 2477 2478 # handle a relator of length 2. 2479 if AbsInt( rep2 ) < AbsInt( rep1 ) then 2480 rep := rep1; rep1 := rep2; rep2 := rep; 2481 fi; 2482 if rep1 < 0 then rep1 := - rep1; rep2 := - rep2; fi; 2483 if rep1 = 0 then 2484 2485 # the relator is in fact of length at most 1. 2486 rep2 := AbsInt( rep2 ); 2487 if rep2 > protected then 2488 # eliminate generator rep1. 2489 invs[numgens1-rep2] := 0; 2490 invs[numgens1+rep2] := 0; 2491 if tree <> 0 then 2492 ptr2 := AbsInt( treeNums[rep2] ); 2493 pointers[ptr2] := 0; 2494 treeNums[rep2] := 0; 2495 fi; 2496 if topl >= 2 then 2497 Print( "#I eliminating ", gens[rep2], 2498 " = idword\n" ); 2499 fi; 2500 # update the generator images, if available. 2501 if tracingImages then 2502 TzUpdateGeneratorImages( T, rep2, [] ); 2503 fi; 2504 redunds := redunds + 1; 2505 done := false; 2506 fi; 2507 2508 elif rep1 <> - rep2 then 2509 2510 if rep1 <> rep2 then 2511 2512 # handle a non-square relator of length 2. 2513 if invs[numgens1-rep2] = invs[numgens1+rep2] 2514 and invs[numgens1+rep1] < 0 then 2515 # add a new square relator for rep1. 2516 numrels := numrels + 1; 2517 rels[numrels] := [ rep1, rep1 ]; 2518 lengths[numrels] := 2; 2519 flags[numrels] := 1; 2520 tietze[TZ_NUMRELS] := numrels; 2521 tietze[TZ_TOTAL] := tietze[TZ_TOTAL] + 2; 2522 fi; 2523 2524 absrep2 := AbsInt( rep2 ); 2525 if absrep2 > protected then 2526 invs[numgens1-rep2] := invs[numgens1+rep1]; 2527 invs[numgens1+rep2] := rep1; 2528 if tree <> 0 then 2529 2530 ptr1 := AbsInt( treeNums[rep1] ); 2531 ptr2 := AbsInt( treeNums[absrep2] ); 2532 if ptr2 < ptr1 then 2533 ptr := ptr2; 2534 if treeNums[rep1] * treeNums[absrep2] 2535 * rep2 > 0 then 2536 ptr := - ptr; 2537 treeNums[rep1] := ptr; 2538 pointers[ptr2] := treelength + rep1; 2539 fi; 2540 ptr2 := ptr1; 2541 ptr1 := AbsInt( ptr ); 2542 fi; 2543 if rep2 > 0 then 2544 ptr1 := - ptr1; 2545 fi; 2546 pointers[ptr2] := ptr1; 2547 treeNums[absrep2] := 0; 2548 fi; 2549 if tracingImages or topl >= 2 then 2550 if rep2 > 0 then 2551 rep1 := invs[numgens1+rep1]; 2552 fi; 2553 if topl >= 2 then 2554 Print( "#I eliminating ", gens[absrep2], 2555 " = ", AbstractWordTietzeWord( 2556 [ rep1 ], gens ), "\n"); 2557 fi; 2558 # update the generator images, if available. 2559 if tracingImages then 2560 TzUpdateGeneratorImages( T, absrep2, 2561 [ rep1 ] ); 2562 fi; 2563 fi; 2564 redunds := redunds + 1; 2565 done := false; 2566 fi; 2567 2568 else 2569 2570 # handle a square relator. 2571 if invs[numgens1+rep1] < 0 then 2572 # make the relator a square relator, ... 2573 rels[i][1] := rep1; 2574 rels[i][2] := rep1; 2575 # ... mark it appropriately, ... 2576 flags[i] := 3; 2577 # ... and mark rep1 to be an involution. 2578 invs[numgens1+rep1] := rep1; 2579 done := false; 2580 fi; 2581 2582 fi; 2583 2584 fi; 2585 fi; 2586 fi; 2587 od; 2588 2589 if not done then 2590 2591 # for each generator determine its current representative. 2592 for i in [ 1 .. numgens ] do 2593 if invs[numgens1-i] <> i then 2594 rep := invs[numgens1-i]; 2595 invs[numgens1-i] := invs[numgens1-rep]; 2596 invs[numgens1+i] := invs[numgens1+rep]; 2597 fi; 2598 od; 2599 2600 # perform the replacements. 2601 TzReplaceGens( tietze ); 2602 fi; 2603 od; 2604 2605 # tidy up the Tietze generators. 2606 tietze[TZ_NUMREDUNDS] := redunds; 2607 if redunds > 0 then TzRemoveGenerators( T ); fi; 2608 2609 # Print( "#I total length = ", tietze[TZ_TOTAL], "\n" ); 2610end ); 2611 2612 2613############################################################################# 2614## 2615#M GeneratorsOfPresentation( <P> ) 2616## 2617InstallGlobalFunction(GeneratorsOfPresentation,function(T) 2618 return ShallowCopy(T!.generators); 2619end); 2620 2621 2622############################################################################# 2623## 2624#M TzInitGeneratorImages( T ) . . . . . . . initialize the generator images 2625#M under Tietze transformations 2626## 2627InstallGlobalFunction( TzInitGeneratorImages, function ( T ) 2628local numgens,gens; 2629 2630 # check the argument to be a Tietze record. 2631 TzCheckRecord( T ); 2632 2633 # initialize the lists. 2634 gens:=GeneratorsOfPresentation(T); 2635 numgens := Length( gens ); 2636 T!.oldGenerators := gens; 2637 T!.imagesOldGens := List( [ 1 .. numgens ], i -> [i] ); 2638 T!.preImagesNewGens := List( [ 1 .. numgens ], i -> [i] ); 2639 2640end ); 2641 2642 2643############################################################################# 2644## 2645#M OldGeneratorsOfPresentation( <P> ) 2646## 2647InstallGlobalFunction(OldGeneratorsOfPresentation,function(T) 2648 return ShallowCopy(T!.oldGenerators); 2649end); 2650 2651 2652############################################################################# 2653## 2654#M TzImagesOldGens( <P> ) 2655## 2656InstallGlobalFunction(TzImagesOldGens,function(T) 2657local g; 2658 g:=GeneratorsOfPresentation(T); 2659 if Length(g)>0 then 2660 return List(T!.imagesOldGens,i->AbstractWordTietzeWord(i,g)); 2661 else 2662 return List(T!.imagesOldGens,i->One(T)); 2663 fi; 2664end); 2665 2666 2667############################################################################# 2668## 2669#M TzPreImagesNewGens( <P> ) 2670## 2671InstallGlobalFunction(TzPreImagesNewGens,function(T) 2672local g; 2673 g:=OldGeneratorsOfPresentation(T); 2674 return List(T!.preImagesNewGens,i->AbstractWordTietzeWord(i,g)); 2675end); 2676 2677 2678############################################################################# 2679## 2680#M TzMostFrequentPairs( <Tietze record>, <n> ) . . . . occurrences of pairs 2681## 2682## `TzMostFrequentPairs' returns a list describing the n most frequently 2683## occurruing relator subwords of the form g1 * g2, where g1 and g2 are 2684## different generators or their inverses. 2685## 2686InstallGlobalFunction( TzMostFrequentPairs, function ( T, nmax ) 2687 2688 local gens, i, j, k, max, n, numgens, occlist, pairs, tietze; 2689 2690 # check the first argument to be a Presentation. 2691 if not IsPresentation( T ) then 2692 Error( "argument must be a Presentation" ); 2693 fi; 2694 2695 # check the second argument. 2696 if not IsInt( nmax ) or nmax <= 0 then 2697 Error( "second argument must be a positive integer" ); 2698 fi; 2699 2700 # intialize some local variables. 2701 tietze := T!.tietze; 2702 gens := tietze[TZ_GENERATORS]; 2703 numgens := tietze[TZ_NUMGENS]; 2704 occlist := [ ]; occlist[4*numgens] := 0; 2705 pairs := [ ]; 2706 n := 0; 2707 2708 if nmax = 1 then 2709 max := 0; 2710 2711 # find a pair [gen[i], gen[j]] of generators or inverse generators 2712 # such that the word gen[i] * gen[j] is a most often occurring 2713 # relator subword. 2714 for i in [ 1 .. numgens-1 ] do 2715 occlist := TzOccurrencesPairs( tietze, i, occlist ); 2716 for j in [ i+1 .. numgens ] do 2717 for k in [ 1 .. 4 ] do 2718 if occlist[(4-k)*numgens+j] >= max then 2719 max := occlist[(4-k)*numgens+j]; 2720 pairs[1] := [ max, i, j, 4 - k ]; 2721 n := 1; 2722 fi; 2723 od; 2724 od; 2725 od; 2726 2727 else 2728 2729 # compute a sorted list which for each word of the form 2730 # gen[i]^+-1 * gen[j]^+-1, with i not equal to j, contains the 2731 # (negative) number of occurrences of that word as relator subword, 2732 # the (negative) two indices i and j, and a sign flag (the negative 2733 # values will make the list be sorted in reversed order). 2734 for i in [ 1 .. numgens-1] do 2735 occlist := TzOccurrencesPairs( tietze, i, occlist ); 2736 for j in [ i+1 .. numgens ] do 2737 for k in [ 0 .. 3 ] do 2738 if occlist[k*numgens+j] > 0 then 2739 n := n + 1; 2740 pairs[n] := [ - occlist[k*numgens+j], - i, - j, k ]; 2741 fi; 2742 od; 2743 od; 2744 if n > nmax then 2745 Sort( pairs ); 2746 pairs := pairs{ [1..nmax] }; 2747 n := nmax; 2748 fi; 2749 od; 2750 2751 # sort the list, and then invert the negative entries. 2752 Sort( pairs ); 2753 for i in [ 1 .. n ] do 2754 pairs[i][1] := - pairs[i][1]; 2755 pairs[i][2] := - pairs[i][2]; 2756 pairs[i][3] := - pairs[i][3]; 2757 od; 2758 fi; 2759 2760 return pairs; 2761end ); 2762 2763 2764############################################################################# 2765## 2766#M TzNewGenerator( <Tietze record> ) . . . . . . . . . adds a new generator 2767## 2768## defines a new abstract generator and adds it to the given presentation. 2769## 2770## Let i be the smallest positive integer which has not yet been used as 2771## a generator number and for which no component T!.i exists so far in the 2772## given Tietze record T, say. A new abstract generator _xi is defined 2773## and then added as component T!.i to the given Tietze record. 2774## 2775## Warning: `TzNewGenerator' is an internal subroutine of the Tietze 2776## routines. You should not call it. Instead, you should call the function 2777## `AddGenerator', if needed. 2778## 2779InstallGlobalFunction( TzNewGenerator, function ( T ) 2780 2781 local freegens, freenames, gen, gens, names, numgens, recnames, new, 2782 tietze; 2783 2784 # get some local variables. 2785 tietze := T!.tietze; 2786 freegens := tietze[TZ_FREEGENS]; 2787 gens := tietze[TZ_GENERATORS]; 2788 numgens := tietze[TZ_NUMGENS]; 2789 freenames := FamilyObj( One(T) )!.names; 2790 names := List( gens, g -> freenames[Position( freegens, g )] ); 2791 2792 # determine the next free generator number. 2793 new := T!.nextFree; 2794 recnames := REC_NAMES_COMOBJ( T ); 2795 while String( new ) in recnames or freenames[new] in names do 2796 new := new + 1; 2797 od; 2798 T!.nextFree := new + 1; 2799 2800 # define the new abstract generator. 2801 gen := freegens[new]; 2802 T!.(String( new )) := gen; 2803 2804 # add the new generator to the presentation. 2805 numgens := numgens + 1; 2806 gens[numgens] := gen; 2807 T!.components[numgens] := new; 2808 tietze[TZ_NUMGENS] := numgens; 2809 tietze[TZ_INVERSES] := Concatenation( [numgens], tietze[TZ_INVERSES], 2810 [-numgens] ); 2811 2812 return gen; 2813end ); 2814 2815 2816############################################################################# 2817## 2818#M TzPrint( <Tietze record> [,<list>] ) . print internal Tietze presentation 2819## 2820## `TzPrint' prints the current generators and relators of the given Tietze 2821## record in their internal representation. The optional second parameter 2822## can be used to specify the numbers of the relators to be printed. 2823## Default: all relators are printed. 2824## 2825InstallGlobalFunction( TzPrint, function ( arg ) 2826 2827 local gens, i, lengths, list, numrels, rels, T, tietze; 2828 2829 # check the first argument to be a Tietze record. 2830 T := arg[1]; 2831 TzCheckRecord( T ); 2832 2833 # initialize the local variables. 2834 tietze := T!.tietze; 2835 gens := tietze[TZ_GENERATORS]; 2836 rels := tietze[TZ_RELATORS]; 2837 numrels := tietze[TZ_NUMRELS]; 2838 lengths := tietze[TZ_LENGTHS]; 2839 2840 # print the generators. 2841 if gens = [] then 2842 Print( "#I there are no generators\n" ); 2843 else 2844 Print( "#I generators: ", gens, "\n" ); 2845 fi; 2846 2847 # if the relators list is empty, print an appropriate message. 2848 if numrels = 0 then 2849 Print( "#I there are no relators\n" ); 2850 return; 2851 fi; 2852 2853 # else print the relators. 2854 Print( "#I relators:\n" ); 2855 if Length( arg ) = 1 then 2856 for i in [1 .. numrels] do 2857 Print( "#I ", i, ". ", lengths[i], " ", rels[i], "\n" ); 2858 od; 2859 else 2860 list := arg[2]; 2861 for i in list do 2862 if 1 <= i and i <= numrels then 2863 Print( "#I ", i, ". ", lengths[i], " ", rels[i], "\n" ); 2864 fi; 2865 od; 2866 fi; 2867end ); 2868 2869 2870############################################################################# 2871## 2872#M TzPrintGeneratorImages( <Tietze record> ) . . . . print generator images 2873## 2874## `TzPrintGeneratorImages' assumes that <T> is a presentation record for 2875## which the generator images and preimages under the Tietze transformations 2876## applied to <T> are being traced. It displays the preimages of the current 2877## generators as Tietze words in the old generators, and the images of the 2878## old generators as Tietze words in the current generators. 2879## 2880InstallGlobalFunction( TzPrintGeneratorImages, function ( T ) 2881 2882 local i, images; 2883 2884 # check T to be a Tietze record. 2885 TzCheckRecord( T ); 2886 2887 # check if generator images are available. 2888 if IsBound( T!.imagesOldGens ) then 2889 2890 # display the preimages of the current generators. 2891 images := T!.preImagesNewGens; 2892 Print( "#I preimages of current generators as Tietze words", 2893 " in the old ones:\n" ); 2894 for i in [1 .. Length( images ) ] do 2895 Print( "#I ", i, ". ", images[i], "\n" ); 2896 od; 2897 2898 # display the images of the old generators. 2899 images := T!.imagesOldGens; 2900 Print( "#I images of old generators as Tietze words in the", 2901 " current ones:\n" ); 2902 for i in [1 .. Length( images ) ] do 2903 Print( "#I ", i, ". ", images[i], "\n" ); 2904 od; 2905 2906 else 2907 2908 # if not, display an appropriate message. 2909 Print( "#I generator images are not available\n" ); 2910 2911 fi; 2912 2913end ); 2914 2915 2916############################################################################# 2917## 2918#M TzPrintGenerators( <Tietze record> [,<list>] ) . . . . . print generators 2919## 2920## `TzPrintGenerators' prints the generators of the given Tietze presenta- 2921## tion together with the number of their occurrences. The optional second 2922## parameter can be used to specify the numbers of the generators to be 2923## printed. Default: all generators are printed. 2924## 2925InstallGlobalFunction( TzPrintGenerators, function ( arg ) 2926 2927 local gens, i, invs, leng, list, max, min, num, numgens, occur, T, 2928 tietze; 2929 2930 # check the first argument to be a Tietze record. 2931 T := arg[1]; 2932 TzCheckRecord( T ); 2933 2934 # initailize some local variables. 2935 tietze := T!.tietze; 2936 gens := tietze[TZ_GENERATORS]; 2937 invs := tietze[TZ_INVERSES]; 2938 numgens := tietze[TZ_NUMGENS]; 2939 2940 # if the generators list is empty, print an appropriate message. 2941 if numgens = 0 then 2942 Print( "#I there are no generators\n" ); 2943 return; 2944 fi; 2945 2946 # else determine the list of generators to be printed. 2947 if Length( arg ) = 1 then 2948 list := [ 1 .. numgens ]; 2949 min := 1; 2950 max := numgens; 2951 else 2952 # check the second argument to be a list. 2953 list := arg[2]; 2954 if not ( IsList( list ) ) then 2955 Error( "second argument must be a list" ); 2956 fi; 2957 if list = [] then list := [ 0 ]; fi; 2958 leng := Length( list ); 2959 2960 if IsRange( list ) then 2961 min := Maximum( list[1], 1 ); 2962 max := Minimum( list[leng], numgens ); 2963 list := [ min .. max ]; 2964 else 2965 min := Maximum( Minimum( list ), 1 ); 2966 max := Minimum( Maximum( list ), numgens ); 2967 fi; 2968 fi; 2969 2970 if min = max then 2971 2972 # determine the number of occurrences of the specified generator. 2973 occur := TzOccurrences( tietze, max ); 2974 2975 # print the generator. 2976 num := occur[1][1]; 2977 if num = 1 then 2978 Print( "#I ",max,". ",gens[max]," ",num," occurrence " ); 2979 else 2980 Print( "#I ",max,". ",gens[max]," ",num," occurrences" ); 2981 fi; 2982 if invs[numgens+1+max] > 0 then Print( " involution" ); fi; 2983 Print( "\n" ); 2984 2985 elif min < max then 2986 2987 # determine the number of occurrences for all generators. 2988 occur := TzOccurrences( tietze ); 2989 2990 # print the generators. 2991 for i in list do 2992 if 1 <= i and i <= numgens then 2993 num := occur[1][i]; 2994 if num = 1 then 2995 Print( "#I ",i,". ",gens[i]," ",num," occurrence " ); 2996 else 2997 Print( "#I ",i,". ",gens[i]," ",num," occurrences" ); 2998 fi; 2999 if invs[numgens+1+i] > 0 then Print( " involution" ); fi; 3000 Print( "\n" ); 3001 fi; 3002 od; 3003 fi; 3004end ); 3005 3006 3007############################################################################# 3008## 3009#M TzPrintLengths( <Tietze record> ) . . . . . . . . print relator lengths 3010## 3011## `TzPrintLengths' prints a list of all relator lengths of the given 3012## presentation record. 3013## 3014InstallGlobalFunction( TzPrintLengths, function ( T ) 3015 3016 local tietze; 3017 3018 # check the argument to be a Tietze record. 3019 TzCheckRecord( T ); 3020 tietze := T!.tietze; 3021 3022 # print the list of relator lengths; 3023 Print( tietze[TZ_LENGTHS], "\n" ); 3024end ); 3025 3026 3027############################################################################# 3028## 3029#M TzOptions(<P>) 3030## 3031InstallMethod(TzOptions,"set default values",true,[IsPresentation],0, 3032function(P) 3033 return rec( 3034 # initialize the Tietze options by their default values. 3035 eliminationsLimit := 100, 3036 expandLimit := 150, 3037 generatorsLimit := 0, 3038 lengthLimit := 2^31 - 1, 3039 loopLimit := infinity, 3040 printLevel := 0, 3041 saveLimit := 10, 3042 searchSimultaneous := 20, 3043 protected:=0 3044 ); 3045end); 3046 3047 3048 3049############################################################################# 3050## 3051#M TzPrintOptions( <Tietze record> ) . . . . . print Tietze record options 3052## 3053## `TzPrintOptions' prints the components of a Tietze record, suppressing 3054## all those components which are not options of the Tietze transformations 3055## routines. 3056## 3057InstallGlobalFunction( TzPrintOptions, function ( T ) 3058 3059 local i, len, lst, nam; 3060 3061 # check the argument to be a Tietze record. 3062 TzCheckRecord( T ); 3063 3064 # determine the maximal name length of the option compoents. 3065 len := 0; 3066 for nam in RecNames( TzOptions(T) ) do 3067 if nam in TzOptionNames then 3068 if len < Length( nam ) then 3069 len := Length( nam ); 3070 fi; 3071 lst := nam; 3072 fi; 3073 od; 3074 3075 # now print all components of T which are options. 3076 for nam in TzOptionNames do 3077 if nam in RecNames( TzOptions(T) ) then 3078 Print( "#I ", nam ); 3079 for i in [Length(nam)..len] do 3080 Print( " " ); 3081 od; 3082 Print( "= ", TzOptions(T).(nam), "\n" ); 3083 fi; 3084 od; 3085 3086end ); 3087 3088 3089############################################################################# 3090## 3091#M TzPrintPairs( <Tietze record> [,<n>] ) . . . . print occurrences of pairs 3092## 3093## `TzPrintPairs' prints the n most often occurring relator subwords of the 3094## form a * b, where a and b are different generators or their inverses, 3095## together with their numbers of occurrences. The default value of n is 10. 3096## If n has been specified to be zero, then it is interpreted as "infinity". 3097## 3098InstallGlobalFunction( TzPrintPairs, function ( arg ) 3099 3100 local geni, genj, gens, k, m, n, num, pairs, T, tietze; 3101 3102 # check the first argument to be a Tietze record. 3103 T := arg[1]; 3104 TzCheckRecord( T ); 3105 3106 # get the second argument. 3107 n := 10; 3108 if Length( arg ) > 1 then n := arg[2]; fi; 3109 if not IsInt( n ) or n < 0 then 3110 Error( "second argument must be a positive integer" ); 3111 fi; 3112 if n = 0 then n := "infinity"; fi; 3113 3114 # intialize the local variables. 3115 tietze := T!.tietze; 3116 gens := tietze[TZ_GENERATORS]; 3117 3118 # determine the n most frequently occurring pairs. 3119 pairs := TzMostFrequentPairs( T, n ); 3120 3121 # print them. 3122 n := Length( pairs ); 3123 for m in [ 1 .. n ] do 3124 num := pairs[m][1]; 3125 k := pairs[m][4]; 3126 geni := gens[pairs[m][2]]; 3127 if k > 1 then geni := geni^-1; fi; 3128 genj := gens[pairs[m][3]]; 3129 if k mod 2 = 1 then genj := genj^-1; fi; 3130 if num = 1 then Print( 3131 "#I ",m,". ",num," occurrence of ",geni," * ",genj,"\n" ); 3132 elif num > 1 then Print( 3133 "#I ",m,". ",num," occurrences of ",geni," * ",genj,"\n" ); 3134 fi; 3135 od; 3136end ); 3137 3138 3139############################################################################# 3140## 3141#M TzPrintPresentation( <Tietze record> ) . . . . . . . . print presentation 3142## 3143## `TzPrintGenerators' prints the generators and the relators of a Tietze 3144## presentation. 3145## 3146InstallGlobalFunction( TzPrintPresentation, function ( T ) 3147 3148 # check the given argument to be a Tietze record. 3149 TzCheckRecord( T ); 3150 3151 # print the generators. 3152 Print( "#I generators:\n" ); 3153 TzPrintGenerators( T ); 3154 3155 # print the relators. 3156 Print( "#I relators:\n" ); 3157 TzPrintRelators( T ); 3158 3159 # print the status line. 3160 TzPrintStatus( T ); 3161end ); 3162 3163 3164############################################################################# 3165## 3166#M TzPrintRelators( <Tietze record> [,<list>] ) . . . . . . . print relators 3167## 3168## `TzPrintRelators' prints the relators of the given Tietze presentation. 3169## The optional second parameter can be used to specify the numbers of the 3170## relators to be printed. Default: all relators are printed. 3171## 3172InstallGlobalFunction( TzPrintRelators, function ( arg ) 3173 3174 local gens, i, list, numrels, rels, T, tietze; 3175 3176 # check the first argument to be a Tietze record. 3177 T := arg[1]; 3178 TzCheckRecord( T ); 3179 3180 # initailize the local variables. 3181 tietze := T!.tietze; 3182 gens := tietze[TZ_GENERATORS]; 3183 rels := tietze[TZ_RELATORS]; 3184 numrels := tietze[TZ_NUMRELS]; 3185 3186 # if the relators list is empty, print an appropriate message. 3187 if numrels = 0 then 3188 Print( "#I there are no relators\n" ); 3189 return; 3190 fi; 3191 3192 # else print the relators. 3193 if Length( arg ) = 1 then 3194 for i in [1 .. numrels] do 3195 Print( "#I ", i, ". ", 3196 AbstractWordTietzeWord( rels[i], gens ), "\n" ); 3197 od; 3198 else 3199 list := arg[2]; 3200 for i in list do 3201 if 1 <= i and i <= numrels then 3202 Print( "#I ", i, ". ", 3203 AbstractWordTietzeWord( rels[i], gens ), "\n" ); 3204 fi; 3205 od; 3206 fi; 3207end ); 3208 3209 3210############################################################################# 3211## 3212#M TzPrintStatus( <Tietze record> [, <norepeat> ] ) . . . print status line 3213## 3214## `TzPrintStatus' prints the number of generators, the number of relators, 3215## and the total length of all relators in the Tietze presentation of the 3216## given group. If "norepeat" is specified as true, then the printing is 3217## suppressed if none of the three values has changed since the last call. 3218## 3219InstallGlobalFunction( TzPrintStatus, function ( arg ) 3220 3221 local norepeat, numgens, numrels, status, T, tietze, total; 3222 3223 # get the arguments. 3224 T := arg[1]; 3225 norepeat := Length( arg ) > 1 and IsBool( arg[2] ) and arg[2]; 3226 3227 # check the first argument to be a Presentation. 3228 if not IsPresentation( T ) then 3229 Error( "first argument must be a Presentation" ); 3230 fi; 3231 tietze := T!.tietze; 3232 total := tietze[TZ_TOTAL]; 3233 3234 # get number of generators and number of relators. 3235 numgens := tietze[TZ_NUMGENS] - tietze[TZ_NUMREDUNDS]; 3236 numrels := tietze[TZ_NUMRELS]; 3237 3238 status := [ numgens, numrels, total ]; 3239 if not ( status = tietze[TZ_STATUS] and norepeat ) then 3240 3241 # print the Tietze status line. 3242 if HasName( T ) then Print( "#I ", Name(T), " has " ); 3243 else Print( "#I there are " ); fi; 3244 if status[1] = 1 then Print( status[1], " generator" ); 3245 else Print( status[1], " generators" ); fi; 3246 if status[2] = 1 then Print( " and ", status[2], " relator" ); 3247 else Print( " and ", status[2], " relators" ); fi; 3248 Print( " of total length ", status[3], "\n" ); 3249 3250 # save the new status. 3251 tietze[TZ_STATUS] := status; 3252 fi; 3253end ); 3254 3255 3256############################################################################# 3257## 3258#M TzRelator( <Tietze record>, <word> ) . . . . . . convert an abstract word 3259#M to a Tietze relator 3260## 3261## `TzRelator' assumes <word> to be an abstract word in the group generators 3262## associated to the given Tietze record, and converts it to a Tietze 3263## relator, i.e. a free and cyclically reduced Tietze word. 3264## 3265InstallGlobalFunction( TzRelator, function ( T, word ) 3266local gens, i, invs, j, length, numgens1, tietze; 3267 3268 # get some local variables 3269 tietze := T!.tietze; 3270 gens := tietze[TZ_GENERATORS]; 3271 invs := tietze[TZ_INVERSES]; 3272 numgens1 := tietze[TZ_NUMGENS] + 1; 3273 3274 # make a tietze word from the given abstract word 3275 word := ShallowCopy(TietzeWordAbstractWord( word, gens )); 3276 3277 # adjust the occurring inverses of involutory generators and reduce 3278 # the word by squares of these generators 3279 length := Length( word ); 3280 j := 0; 3281 for i in [ 1 .. length ] do 3282 if invs[numgens1+invs[numgens1+word[i]]] <> word[i] then 3283 word[i] := -word[i]; 3284 fi; 3285 if j > 0 and word[j] = invs[numgens1+word[i]] then 3286 j := j - 1; 3287 else 3288 j := j + 1; 3289 word[j] := word[i]; 3290 fi; 3291 od; 3292 3293 # cyclically reduce the word 3294 i := 1; 3295 while i < j and word[i] = invs[numgens1+word[j]] do 3296 i := i + 1; 3297 j := j - 1; 3298 od; 3299 3300 return word{ [ i .. j ] }; 3301end ); 3302 3303 3304############################################################################# 3305## 3306#M TzRemoveGenerators( <Tietze record> ) . . . . Remove redundant generators 3307## 3308## `TzRemoveGenerators' deletes the redundant Tietze generators and 3309## renumbers the non-redundant ones accordingly. The redundant generators 3310## are assumed to be marked in the inverses list by an entry 3311## invs[numgens+1-i] <> i. 3312## 3313InstallGlobalFunction( TzRemoveGenerators, function ( T ) 3314 3315 local comps, gens, i, image, invs, j, newim, numgens, numgens1, 3316 pointers, preimages, redunds, tietze, tracingImages, 3317 tree, treelength, treeNums; 3318 3319 if TzOptions(T).printLevel >= 3 then 3320 Print( "#I renumbering the Tietze generators\n" ); 3321 fi; 3322 3323 # check the given argument to be a Presentation. 3324 if not IsPresentation( T ) then 3325 Error( "argument must be a Presentation" ); 3326 fi; 3327 3328 tietze := T!.tietze; 3329 redunds := tietze[TZ_NUMREDUNDS]; 3330 if redunds = 0 then return; fi; 3331 3332 tracingImages := IsBound( T!.imagesOldGens ); 3333 if tracingImages then preimages := T!.preImagesNewGens; fi; 3334 comps := T!.components; 3335 gens := tietze[TZ_GENERATORS]; 3336 invs := tietze[TZ_INVERSES]; 3337 numgens := tietze[TZ_NUMGENS]; 3338 numgens1 := numgens + 1; 3339 tree := 0; 3340 3341 if IsBound( T!.tree ) then 3342 3343 tree := T!.tree; 3344 treelength := tree[TR_TREELENGTH]; 3345 treeNums := tree[TR_TREENUMS]; 3346 pointers := tree[TR_TREEPOINTERS]; 3347 3348 # renumber the non-redundant generators in the relators. 3349 j := 0; 3350 for i in [ 1 .. numgens ] do 3351 if invs[numgens1-i] = i then 3352 j := j + 1; 3353 if j < i then 3354 comps[j] := comps[i]; 3355 treeNums[j] := treeNums[i]; 3356 pointers[AbsInt(treeNums[j])] := treelength + j; 3357 invs[numgens1-i] := j; 3358 if invs[numgens1+i] > 0 then invs[numgens1+i] := j; 3359 else invs[numgens1+i] := -j; fi; 3360 fi; 3361 else 3362 Unbind( T!.(String(comps[i])) ); 3363 invs[numgens1-i] := 0; 3364 invs[numgens1+i] := 0; 3365 fi; 3366 od; 3367 3368 else 3369 3370 # renumber the non-redundant generators in the relators. 3371 j := 0; 3372 for i in [ 1 .. numgens ] do 3373 if invs[numgens1-i] = i then 3374 j := j + 1; 3375 if j < i then 3376 comps[j] := comps[i]; 3377 invs[numgens1-i] := j; 3378 if invs[numgens1+i] > 0 then invs[numgens1+i] := j; 3379 else invs[numgens1+i] := -j; fi; 3380 fi; 3381 else 3382 Unbind( T!.(String(comps[i])) ); 3383 invs[numgens1-i] := 0; 3384 invs[numgens1+i] := 0; 3385 fi; 3386 od; 3387 3388 fi; 3389 3390 if j <> numgens - redunds then 3391 Error( "This is a bug. You should never get here.\n", 3392 "Please send a copy of your job to the GAP administrators.\n" ); 3393 fi; 3394 TzRenumberGens( tietze ); 3395 3396 # update the generator images, if available. 3397 if tracingImages then 3398 for i in [ 1 .. Length( T!.imagesOldGens ) ] do 3399 image := T!.imagesOldGens[i]; 3400 newim := []; 3401 for j in [ 1 .. Length( image ) ] do 3402 Add( newim, invs[numgens1-image[j]] ); 3403 od; 3404 T!.imagesOldGens[i] := ReducedRrsWord( newim ); 3405 od; 3406 fi; 3407 3408 # update the other generators list and the lists related to it. 3409 for i in [ 1 .. numgens ] do 3410 j := invs[numgens1-i]; 3411 if j < i and j > 0 then 3412 gens[j] := gens[i]; 3413 invs[numgens1-j] := j; 3414 invs[numgens1+j] := invs[numgens1+i]; 3415 if tracingImages then 3416 preimages[j] := preimages[i]; 3417 fi; 3418 fi; 3419 od; 3420 j := numgens; 3421 numgens := numgens - redunds; 3422 tietze[TZ_INVERSES] := invs{ [numgens1-numgens..numgens1+numgens] }; 3423 while j > numgens do 3424 Unbind( gens[j] ); 3425 Unbind( comps[j] ); 3426 if tree <> 0 then Unbind( treeNums[j] ); fi; 3427 if tracingImages then Unbind( preimages[j] ); fi; 3428 j := j - 1; 3429 od; 3430 3431 tietze[TZ_NUMGENS] := numgens; 3432 tietze[TZ_NUMREDUNDS] := 0; 3433 tietze[TZ_OCCUR]:=false; 3434end ); 3435 3436 3437############################################################################# 3438## 3439#M TzSearch( <Tietze record> ) . . . . . . . search subwords and substitute 3440## 3441## `TzSearch' searches for relator subwords which in some relator have a 3442## complement of shorter length and which occur in other relators, too, and 3443## uses them to reduce these other relators. 3444## 3445InstallGlobalFunction( TzSearch, function ( T ) 3446 3447 local altered, flags, i, flag, j, k, lastj, leng, lengths, lmax, loop, 3448 modified, numrels, oldtotal, rels, save, simultan, 3449 simultanlimit, tietze; 3450 3451 if TzOptions(T).printLevel >= 3 then Print( "#I searching subwords\n" ); fi; 3452 3453 # check the given argument to be a Tietze record. 3454 TzCheckRecord( T ); 3455 TzTestInitialSetup(T); # run `1Or2Relators' if not yet done 3456 tietze := T!.tietze; 3457 simultanlimit := TzOptions(T).searchSimultaneous; 3458 3459 rels := tietze[TZ_RELATORS]; 3460 lengths := tietze[TZ_LENGTHS]; 3461 flags := tietze[TZ_FLAGS]; 3462 tietze[TZ_MODIFIED] := false; 3463 save := TzOptions(T).saveLimit / 100; 3464 3465 loop := tietze[TZ_TOTAL] > 0; while loop do 3466 3467 TzSort( T ); 3468 numrels := tietze[TZ_NUMRELS]; 3469 modified := false; 3470 oldtotal := tietze[TZ_TOTAL]; 3471 3472 # search subwords with shorter complements, and substitute. 3473 flag := 0; 3474 i := 1; 3475 while i < numrels do 3476 if flags[i] <= 1 and lengths[i] > 0 then 3477 leng := lengths[i]; 3478 lmax := leng + (leng + 1) mod 2; 3479 if flag < flags[i] then flag := flags[i]; fi; 3480 simultan := 1; 3481 j := i; 3482 lastj := 0; 3483 k := i + 1; 3484 while k <= numrels and lengths[k] <= lmax and 3485 simultan < simultanlimit do 3486 if flags[k] <= 1 and 3487 ( lengths[k] = leng or lengths[k] = lmax ) then 3488 lastj := j; 3489 j := k; 3490 simultan := simultan + 1; 3491 fi; 3492 k := k + 1; 3493 od; 3494 while k <= numrels and ( lengths[k] < leng or 3495 flags[k] > 1 or flag = 0 and flags[k] = 0 ) do 3496 k := k + 1; 3497 od; 3498 if k > numrels then j := lastj; fi; 3499 if i <= j then 3500 altered := TzSearchC( tietze, i, j ); 3501 modified := modified or altered > 0; 3502 i := j; 3503 fi; 3504 fi; 3505 i := i + 1; 3506 od; 3507 3508 # reset the Tietze flags. 3509 for i in [ 1 .. numrels ] do 3510 if flags[i] = 1 or flags[i] = 2 then 3511 flags[i] := flags[i] - 1; 3512 fi; 3513 od; 3514 3515 if modified then 3516 if tietze[TZ_TOTAL] < oldtotal then 3517 tietze[TZ_MODIFIED] := true; 3518 # handle relators of length 1 or 2. 3519 TzHandleLength1Or2Relators( T ); 3520 # sort the relators and print the status line. 3521 TzSort( T ); 3522 if TzOptions(T).printLevel >= 2 then TzPrintStatus( T, true ); fi; 3523 fi; 3524 fi; 3525 3526 loop := tietze[TZ_TOTAL] < oldtotal and tietze[TZ_TOTAL] > 0 and 3527 (oldtotal - tietze[TZ_TOTAL]) / oldtotal >= save; 3528 od; 3529end ); 3530 3531 3532############################################################################# 3533## 3534#M TzSearchEqual( <Tietze record> ) . . . . search subwords of equal length 3535## 3536## `TzSearchEqual' searches for Tietze relator subwords which in some 3537## relator have a complement of equal length and which occur in other 3538## relators, too, and uses them to modify these other relators. 3539## 3540InstallGlobalFunction( TzSearchEqual, function ( T ) 3541 3542 local altered, equal, i, j, k, lastj, leng, lengths, modified, numrels, 3543 oldtotal, rels, simultan, simultanlimit, tietze; 3544 3545 if TzOptions(T).printLevel >= 3 then 3546 Print( "#I searching subwords of equal length\n" ); 3547 fi; 3548 3549 # check the given argument to be a Tietze record. 3550 TzCheckRecord( T ); 3551 TzTestInitialSetup(T); # run `1Or2Relators' if not yet done 3552 tietze := T!.tietze; 3553 simultanlimit := TzOptions(T).searchSimultaneous; 3554 3555 TzSort( T ); 3556 3557 rels := tietze[TZ_RELATORS]; 3558 lengths := tietze[TZ_LENGTHS]; 3559 numrels := tietze[TZ_NUMRELS]; 3560 modified := false; 3561 oldtotal := tietze[TZ_TOTAL]; 3562 equal := true; 3563 3564 # substitute substrings by substrings of equal length. 3565 i := 1; 3566 while i < numrels do 3567 leng := lengths[i]; 3568 if leng > 3 and leng mod 2 = 0 then 3569 simultan := 1; 3570 j := i; 3571 lastj := 0; 3572 k := i + 1; 3573 while k <= numrels and lengths[k] <= leng and 3574 simultan < simultanlimit do 3575 if lengths[k] = leng then 3576 lastj := j; 3577 j := k; 3578 simultan := simultan + 1; 3579 fi; 3580 k := k + 1; 3581 od; 3582 while k <= numrels and lengths[k] < leng do 3583 k := k + 1; 3584 od; 3585 if k > numrels then j := lastj; fi; 3586 if i <= j then 3587 altered := TzSearchC( tietze, i, j, equal ); 3588 modified := modified or altered > 0; 3589 i := j; 3590 fi; 3591 fi; 3592 i := i + 1; 3593 od; 3594 3595 if modified then 3596 tietze[TZ_OCCUR]:=false; 3597 if tietze[TZ_TOTAL] < oldtotal then 3598 tietze[TZ_MODIFIED] := true; 3599 # handle relators of length 1 or 2. 3600 TzHandleLength1Or2Relators( T ); 3601 # sort the relators and print the status line. 3602 TzSort( T ); 3603 if TzOptions(T).printLevel >= 2 then TzPrintStatus( T, true ); fi; 3604 fi; 3605 fi; 3606end ); 3607 3608 3609############################################################################# 3610## 3611#M TzSort( <Tietze record> ) . . . . . . . . . . . . . . . . . sort relators 3612## 3613## sorts the relators list of the given presentation <P> and, 3614## in parallel, the search flags list. Note: All relators of length 0 are 3615## removed from the list. 3616## 3617## The sorting algorithm used is the same as in the GAP function Sort. 3618## 3619InstallGlobalFunction( TzSort, function ( T ) 3620 3621 if TzOptions(T).printLevel >= 3 then Print( "#I sorting the relators\n" ); fi; 3622 3623 # check the given argument to be a Presentation. 3624 if not IsPresentation( T ) then 3625 Error( "argument must be a Presentation" ); 3626 fi; 3627 3628 if T!.tietze[TZ_NUMRELS] > 0 then 3629 TzSortC( T!.tietze ); 3630 T!.tietze[TZ_OCCUR]:=false; 3631 fi; 3632end ); 3633 3634 3635############################################################################# 3636## 3637#M TzSubstitute( <Tietze record>, <word> ) . . . . . . . . . . . substitute 3638#M TzSubstitute( <Tietze record> [, <n> [,<elim> ] ] ) . . . a new generator 3639## 3640## In its first form, `TzSubstitute' just calls the function 3641## `TzSubstituteWord'. 3642## 3643## In its second form, `TzSubstitute' first determines the n most frequently 3644## occurring relator subwords of the form g1 * g2, where g1 and g2 are 3645## different generators or their inverses, and sorts them by decreasing 3646## numbers of occurrences. 3647## 3648## Let a * b be the last word in that list, and let i be the smallest 3649## positive integer for which there is no component T!.i so far in the given 3650## Tietze record T, then `TzSubstitute' adds to the given presentation a new 3651## generator T!.i and a new relator T!.i^-1 * a * b, and it replaces all 3652## occurrences of a * b in the relators by T!.i. Finally, if elim = 1 or 3653## elim = 2, it eliminates the generator a or b, respectively. Otherwise it 3654## eliminates some generator by just calling subroutine `TzEliminateGen1'. 3655## 3656## The two arguments are optional. If they are specified, then n is expected 3657## to be a positive integer, and elim is expected to be 0, 1, or 2. The 3658## default values are n = 1 and elim = 0. 3659## 3660InstallGlobalFunction( TzSubstitute, function ( arg ) 3661 3662 local elim, gen, gens, i, invs, j, k, n, narg, numgens, pair, pairs, 3663 printlevel, T, tietze, word; 3664 3665 # just call `TzSubstituteWord' if the second argument is a word. 3666 narg := Length( arg ); 3667 if ( narg > 1 ) and ( IsList( arg[2] ) or IsWord( arg[2] ) ) then 3668 TzSubstituteWord( arg[1], arg[2] ); 3669 return; 3670 fi; 3671 3672 # check the number of arguments. 3673 if narg < 1 or narg > 3 then Error( 3674 "usage: TzSubstitute( <Tietze record> [, <n> [, <elim> ] ] )" ); 3675 fi; 3676 3677 # check the first argument to be a Tietze record. 3678 T := arg[1]; 3679 TzCheckRecord( T ); 3680 3681 # get the second argument, and check it to be a positive integer. 3682 n := 1; 3683 if narg >= 2 then 3684 n := arg[2]; 3685 if not IsInt( n ) or n < 1 then 3686 Error( "second argument must be a positive integer" ); 3687 fi; 3688 fi; 3689 3690 # get the third argument, and check it to be 0, 1, or 2. 3691 elim := 0; 3692 if narg = 3 then 3693 elim := arg[3]; 3694 if not IsInt( elim ) or elim < 0 or elim > 2 then 3695 Error( "third argument must be 0, 1, or 2" ); 3696 fi; 3697 fi; 3698 3699 # check the number of generators to be at least 2. 3700 tietze := T!.tietze; 3701 numgens := tietze[TZ_NUMGENS]; 3702 if numgens < 2 then return; fi; 3703 3704 # initialize some local variables. 3705 gens := tietze[TZ_GENERATORS]; 3706 invs := tietze[TZ_INVERSES]; 3707 printlevel := TzOptions(T).printLevel; 3708 3709 # determine the n most frequently occurring relator subwords of the form 3710 # g1 * g2, where g1 and g2 are different generators or their inverses, 3711 # and sort them by decreasing numbers of occurrences. 3712 pairs := TzMostFrequentPairs( T, n ); 3713 if Length( pairs ) < n then 3714 if narg > 1 and printlevel >= 1 then 3715 Print( "#I TzSubstitute: second argument is out of range\n" ); 3716 fi; 3717 return; 3718 fi; 3719 3720 # get the nth pair [ a, b ], say, from the list. 3721 i := pairs[n][2]; 3722 j := pairs[n][3]; 3723 k := pairs[n][4]; 3724 if k > 1 then i := invs[numgens+1+i]; fi; 3725 if k mod 2 = 1 then j := invs[numgens+1+j]; fi; 3726 pair := [i, j]; 3727 3728 # add the word a * b as a new generator. 3729 gen := TzNewGenerator( T ); 3730 word := AbstractWordTietzeWord( pair, gens ); 3731 if TzOptions(T).printLevel >= 1 then Print( 3732 "#I substituting new generator ",gen," defined by ",word,"\n" ); 3733 fi; 3734 AddRelator( T, gen^-1 * word ); 3735 3736 # if there is a tree of generators, delete it. 3737 if IsBound( T!.tree ) then Unbind( T!.tree ); fi; 3738 3739 # update the generator preimages, if available. 3740 if IsBound( T!.imagesOldGens ) then 3741 TzUpdateGeneratorImages( T, 0, pair ); 3742 fi; 3743 3744 # replace all relator subwords of the form a * b by the new generator. 3745 TzOptions(T).printLevel := 0; 3746 TzSearch( T ); 3747 TzOptions(T).printLevel := printlevel; 3748 3749 # eliminate a generator. 3750 if printlevel = 1 then TzOptions(T).printLevel := 2; fi; 3751 if elim > 0 then 3752 TzEliminateGen( T, AbsInt( pair[elim] ) ); 3753 else 3754 TzEliminateGen1( T ); 3755 fi; 3756 TzOptions(T).printLevel := printlevel; 3757 if tietze[TZ_MODIFIED] then TzSearch( T ); fi; 3758 if tietze[TZ_NUMREDUNDS] > 0 then TzRemoveGenerators( T ); fi; 3759 3760 if TzOptions(T).printLevel >= 1 then TzPrintStatus( T, true ); fi; 3761end ); 3762 3763 3764############################################################################# 3765## 3766#M TzSubstituteCyclicJoins( <Tietze record> ) . . common roots of generators 3767## 3768## `TzSubstituteCyclicJoins' tries to find pairs of commuting generators a 3769## and b, say, such that exponent(a) is prime to exponent(b). For each such 3770## pair, their product a * b is substituted as a new generator, and a and b 3771## are eliminated. 3772## 3773InstallGlobalFunction( TzSubstituteCyclicJoins, function ( T ) 3774 3775 local exp1, exp2, exponents, gen, gen2, gens, i, invs, lengths, 3776 num1, num2, numgens, numrels, printlevel, rel, rels, 3777 tietze; 3778 3779 # check the given argument to be a Tietze record. 3780 TzCheckRecord( T ); 3781 TzTestInitialSetup(T); # run `1Or2Relators' if not yet done 3782 3783 if TzOptions(T).printLevel >= 3 then 3784 Print( "#I substituting cyclic joins\n" ); 3785 fi; 3786 3787 # Try to find exponents for the generators. 3788 exponents := TzGeneratorExponents( T ); 3789 tietze := T!.tietze; 3790 tietze[TZ_MODIFIED] := false; 3791 3792 if Sum( exponents ) = 0 then return; fi; 3793 3794 # sort the relators by their lengths. 3795 TzSort( T ); 3796 3797 # initialize some local variables. 3798 gens := tietze[TZ_GENERATORS]; 3799 numgens := tietze[TZ_NUMGENS]; 3800 rels := tietze[TZ_RELATORS]; 3801 numrels := tietze[TZ_NUMRELS]; 3802 lengths := tietze[TZ_LENGTHS]; 3803 invs := tietze[TZ_INVERSES]; 3804 printlevel := TzOptions(T).printLevel; 3805 3806 # Now work off all commutator relators of length 4. 3807 i := 1; 3808 while i <= numrels and lengths[i] <= 4 do 3809 3810 rel := rels[i]; 3811 if lengths[i] = 4 and rel[1] = invs[numgens+1+rel[3]] and 3812 rel[2] = invs[numgens+1+rel[4]] then 3813 3814 # There is a commutator relator of the form [a,b]. Check if 3815 # there are also power relators of the form a^m or b^n. 3816 3817 num1 := AbsInt( rel[1] ); exp1 := exponents[num1]; 3818 num2 := AbsInt( rel[2] ); exp2 := exponents[num2]; 3819 3820 # If there are relators a^m and b^n with m prime to n, then 3821 # a = (a*b)^n, b = (a*b)^m, and (a*b)^(m*n) = 1. Hence we 3822 # may define a new generator g, say, by a*b together with the 3823 # two relations a = g^n and b = g^m, and then eliminate a 3824 # and b. (Note that we can take a^-1 instead of a or b^-1 3825 # instead of b.) 3826 3827 if exp1 > 0 and exp2 > 0 and GcdInt( exp1, exp2 ) = 1 then 3828 3829 gen := TzNewGenerator( T ); 3830 numgens := tietze[TZ_NUMGENS]; 3831 invs := tietze[TZ_INVERSES]; 3832 3833 if printlevel >= 1 then 3834 Print( "#I substituting new generator ",gen, 3835 " defined by ",gens[num1]*gens[num2],"\n" ); 3836 fi; 3837 3838 AddRelator( T, gens[num1] * gen^-exp2 ); 3839 AddRelator( T, gens[num2] * gen^-exp1 ); 3840 3841 # if there is a tree of generators, delete it. 3842 if IsBound( T!.tree ) then Unbind( T!.tree ); fi; 3843 3844 # update the generator preimages, if available. 3845 if IsBound( T!.imagesOldGens ) then 3846 TzUpdateGeneratorImages( T, 0, [ num1, num2 ] ); 3847 fi; 3848 3849 # save gens[num2] before eliminating gens[num1] because 3850 # its number may change. 3851 gen2 := gens[num2]; 3852 if printlevel = 1 then TzOptions(T).printLevel := 2; fi; 3853 TzEliminate( T, gens[num1] ); 3854 num2 := Position( gens, gen2 ); 3855 TzEliminate( T, gens[num2] ); 3856 TzOptions(T).printLevel := printlevel; 3857 numgens := tietze[TZ_NUMGENS]; 3858 numrels := tietze[TZ_NUMRELS]; 3859 invs := tietze[TZ_INVERSES]; 3860 tietze[TZ_MODIFIED] := true; 3861 i := 0; 3862 fi; 3863 fi; 3864 i := i + 1; 3865 od; 3866 3867 if tietze[TZ_MODIFIED] then 3868 # handle relators of length 1 or 2. 3869 TzHandleLength1Or2Relators( T ); 3870 # sort the relators and print the status line. 3871 TzSort( T ); 3872 if printlevel >= 1 then TzPrintStatus( T, true ); fi; 3873 fi; 3874end ); 3875 3876 3877############################################################################# 3878## 3879#M TzSubstituteWord( <Tietze record>, <word> ) . . . substitute a given word 3880#M as a new generator 3881## 3882## `TzSubstituteWord' expects <T> to be a Tietze record and <word> to be a 3883## word in the generators of <T>. It adds a new generator, gen say, and a 3884## new relator of the form gen^-1 * <Word> to <T>. 3885## 3886## The second argument, <word>, may be either an abstract word or a Tietze 3887## word, i. e., a list of positive or negative generator numbers. 3888## 3889## More precisely: The effect of a call 3890## 3891## TzSubstituteWord( T, word ); 3892## 3893## is more or less equivalent to that of 3894## 3895## AddGenerator( T ); 3896## gen := T!.generators[Length( T!.generators )]; 3897## AddRelator( T, gen^-1 * word ); 3898## 3899## The essential difference is, that `TzSubstituteWord', as a Tietze 3900## transformation of T, saves and updates the lists of generator images and 3901## preimages, in case they are being traced under the Tietze transformations 3902## applied to T, whereas a call of the function `AddGenerator' (which does 3903## not perform a Tietze transformation) will delete these lists and hence 3904## terminate the tracing. 3905## 3906InstallGlobalFunction( TzSubstituteWord, function ( T, word ) 3907 3908 local aword, gen, gens, images, tzword; 3909 3910 # check the first argument to be a Tietze record. 3911 TzCheckRecord( T ); 3912 3913 # check the second argument to be an abstract word or a Tietze word in 3914 # the generators. 3915 gens := T!.generators; 3916 if IsList( word ) then 3917 tzword := ReducedRrsWord( word ); 3918 aword := AbstractWordTietzeWord( tzword, gens ); 3919 else 3920 aword := word; 3921 tzword := TietzeWordAbstractWord( aword, gens ); 3922 fi; 3923 3924 # if generator images and preimages are being traced through the Tietze 3925 # transformations of T, save them from being deleted by `AddGenerator'. 3926 images := 0; 3927 if IsBound( T!.imagesOldGens ) then 3928 images := T!.imagesOldGens; 3929 Unbind( T!.imagesOldGens ); 3930 fi; 3931 3932 # add a new generator. 3933 AddGenerator( T ); 3934 gen := T!.generators[Length( T!.generators )]; 3935 3936 # add the corresponding relator. 3937 if TzOptions(T).printLevel >= 1 then Print( 3938 "#I substituting new generator ",gen," defined by ",aword,"\n" ); 3939 fi; 3940 AddRelator( T, gen^-1 * aword ); 3941 3942 # restore the generator images and update the generator preimages, if 3943 # available. 3944 if IsList( images ) then 3945 T!.imagesOldGens := images; 3946 TzUpdateGeneratorImages( T, 0, tzword ); 3947 fi; 3948 3949 if TzOptions(T).printLevel >= 1 then TzPrintStatus( T, true ); fi; 3950end ); 3951 3952 3953############################################################################# 3954## 3955#M TzUpdateGeneratorImages( T, n, word ) . . . . update the generator images 3956#M after a Tietze transformation 3957## 3958## `TzUpdateGeneratorImages' assumes that it is called by a function that 3959## performs Tietze transformations to a presentation record <T> in which 3960## images of the old generators are being traced as Tietze words in the new 3961## generators as well as preimages of the new generators as Tietze words in 3962## the old generators. 3963## 3964## If <n> is zero, it assumes that a new generator defined by the Tietze 3965## word <word> has just been added to the presentation. It converts <word> 3966## from a Tietze word in the new generators to a Tietze word in the old 3967## generators and adds that word to the list of preimages. 3968## 3969## If <n> is greater than zero, it assumes that the <n>-th generator has 3970## just been eliminated from the presentation. It updates the images of the 3971## old generators by replacing each occurrence of the <n>-th generator by 3972## the given Tietze word <word>. 3973## 3974## If <n> is less than zero, it terminates the tracing of generator images, 3975## i. e., it deletes the corresponding record components of <T>. 3976## 3977## Note: `TzUpdateGeneratorImages' is considered to be an internal function. 3978## Hence it does not check the arguments. 3979## 3980InstallGlobalFunction( TzUpdateGeneratorImages, function ( T, n, word ) 3981local i, image, invword, j, newim, num, oldnumgens,replace,mn,oldi; 3982 3983 if n = 0 then 3984 3985 # update the preimages of the new generators. 3986 newim := []; 3987 for num in word do 3988 if num > 0 then 3989 Append( newim, T!.preImagesNewGens[num] ); 3990 else 3991 Append( newim, -1 * Reversed( T!.preImagesNewGens[-num] ) ); 3992 fi; 3993 od; 3994 Add( T!.preImagesNewGens, ReducedRrsWord( newim ) ); 3995 3996 elif n > 0 then 3997 3998 mn:=-n; 3999 # update the images of the old generators: 4000 # run through all images and replace the n-th generator by word. 4001 invword := -1 * Reversed( word ); 4002 oldi:=T!.imagesOldGens; 4003 oldnumgens := Length( oldi ); 4004 for i in [ 1 .. oldnumgens ] do 4005 image := oldi[i]; 4006 if Length(image)=1 then 4007 # the image is a single generator. This happens often. 4008 if image[1]=n then 4009 oldi[i]:=ReducedRrsWord(word); 4010 elif image[1]=mn then 4011 oldi[i]:=ReducedRrsWord(invword); 4012 fi; 4013 else 4014 replace:=false; 4015 j:=1; 4016 while replace=false and j<=Length(image) do 4017 replace:=image[j]=n or image[j]=mn; 4018 j:=j+1; 4019 od; 4020 if replace then 4021 newim := []; 4022 replace:=false; 4023 for j in [ 1 .. Length( image ) ] do 4024 if image[j] = n then 4025 Append( newim, word ); 4026 elif image[j] = mn then 4027 Append( newim, invword ); 4028 else 4029 Add( newim, image[j] ); 4030 fi; 4031 od; 4032 oldi[i] := ReducedRrsWord( newim ); 4033 fi; 4034 fi; 4035 od; 4036 4037 else 4038 4039 # terminate the tracing of generator images. 4040 Unbind( T!.imagesOldGens ); 4041 Unbind( T!.preImagesNewGens ); 4042 if IsBound( T!.oldGenerators ) then 4043 Unbind( T!.oldGenerators ); 4044 fi; 4045 if TzOptions(T).printLevel >= 1 then 4046 Print( "#I terminated the tracing of generator images\n" ); 4047 fi; 4048 4049 fi; 4050end ); 4051