1############################################################################## 2## 3#W idrels.gi IdRel Package Chris Wensley 4#W & Anne Heyworth 5## Implementation file for functions of the IdRel package. 6## 7#Y Copyright (C) 1999-2018 Anne Heyworth and Chris Wensley 8## 9## This file contains generic methods for identities among relators 10 11############################################*##################*############## 12## 13#M GroupRelatorSequenceLessThan 14## 15InstallMethod( GroupRelatorSequenceLessThan, "for two grp rel sequences", 16 true, [ IsList, IsList ], 0, 17function( y, z ) 18 if ( Length( y ) < Length( z ) ) then 19 return true; 20 elif ( Length( y ) > Length( z ) ) then 21 return false; 22 else 23 return ( y < z ); 24 fi; 25end ); 26 27############################################################################## 28## 29#M ModuleRelatorSequenceReduce 30## 31InstallMethod( ModuleRelatorSequenceReduce, "generic method for a Ysequence", 32 true, [ IsList ], 0, 33function( y ) 34 35 local k, leny, w; 36 37 leny := Length( y ); 38 k := 1; 39 ## remove consecutive terms when one is the inverse of the other 40 while ( k < leny ) do 41 if ( ( y[k][1] = y[k+1][1]^(-1) ) and ( y[k][2] = y[k+1][2] ) ) then 42 y := Concatenation( y{[1..k-1]}, y{[k+2..leny]} ); 43 k := k - 2; 44 leny := leny - 2; 45 if ( ( k = -1 ) and ( leny > 0 ) ) then 46 k := 0; 47 fi; 48 fi; 49 k := k + 1; 50 od; 51 ## remove first and last terms when one is the inverse of the other 52 if ( ( leny > 1 ) and ( y[1][1] = y[leny][1]^(-1) ) 53 and ( y[1][2] = y[leny][2] ) ) then 54 y := y{[2..leny-1]}; 55 leny := leny - 2; 56 fi; 57 return y; 58end ); 59 60############################################################################## 61## 62#M YSequenceConjugateAndReduce 63## 64InstallMethod( YSequenceConjugateAndReduce, "generic method for a Ysequence", 65 true, [ IsList, IsHomogeneousList ], 0, 66function( y, rws ) 67 68 local k, leny, w; 69 70 leny := Length( y ); 71 if ( leny > 0 ) then 72 w := y[1][2]^(-1); 73 y := List( y, c -> [ c[1], ReduceWordKB( c[2]*w, rws ) ] ); 74 fi; 75 return y; 76end ); 77 78############################################################################## 79## 80#M ConvertToGroupRelatorSequences 81## 82## this operation takes a list of monoid relator sequences mseq for the 83## group G which involve numbers for the relators and monoid conjugating 84## words and replaces them with the relators and conjugating words in G 85## 86InstallMethod( ConvertToGroupRelatorSequences, 87 "generic method for an fp-group and a monoid relator sequence", true, 88 [ IsFpGroup, IsHomogeneousList ], 0, 89function( G, mseq ) 90 91 local monG, mu, FM, genFM, numgenM, F, genF, idF, freerels, FR, genFR, 92 omega, len, gseq, i, s0, s1, s2, s3, s4, leni, t, t1, rt, wt, 93 z, z1, z2; 94 monG := MonoidPresentationFpGroup( G ); 95 mu := HomomorphismOfPresentation( monG ); 96 FM := FreeGroupOfPresentation( monG ); 97 genFM := GeneratorsOfGroup( FM ); 98 numgenM := Length( genFM ); 99 F := FreeGroupOfFpGroup( G ); 100 genF := GeneratorsOfGroup( F ); 101 idF := One( F ); 102 freerels := RelatorsOfFpGroup( G ); 103 FR := FreeRelatorGroup( G ); 104 genFR := GeneratorsOfGroup( FR ); 105 omega := GroupHomomorphismByImages( FR, F, genFR, freerels ); 106 107 len := Length( mseq ); 108 gseq := ListWithIdenticalEntries( len, 0 ); 109 for i in [1..len] do 110 s0 := mseq[i]; 111 s1 := ShallowCopy( s0[2] ); 112 s2 := ShallowCopy( s0[2] ); 113 leni := Length( s1 ); 114 for t in [1..leni] do 115 t1 := s1[t][1]; 116 if ( t1 > 0 ) then 117 rt := genFR[ t1 - numgenM ]; 118 else 119 rt := genFR[ - t1 - numgenM ]^-1; 120 fi; 121 wt := Image( mu, s1[t][2] ); 122 s2[t] := [ rt, wt ]; 123 od; 124 s3 := ModuleRelatorSequenceReduce( s2 ); 125 ## check that this really is an identity 126 leni := Length( s3 ); 127 if ( leni > 0 ) then 128 s4 := ShallowCopy( s3 ); 129 for t in [1..Length(s4)] do 130 z := s4[t]; 131 z1 := Image( omega, z[1] ); 132 z2 := z[2]; 133 s4[t] := z1^z2; 134 od; 135 if not( Product( s4 ) = idF ) then 136 Print( "s0 = ", s0, "\n" ); 137 Print( "s1 = ", s1, "\n" ); 138 Print( "s2 = ", s2, "\n" ); 139 Print( "s3 = ", s3, "\n" ); 140 Print( "s4 = ", s4, "\n" ); 141 Error( "supposed identity fails to reduce to idF" ); 142 fi; 143 fi; 144 gseq[i] := [ s0[1], s3 ]; 145 od; 146 return gseq; 147end ); 148 149############################################################################## 150## 151#M IdentityRelatorSequences 152## 153InstallMethod( IdentityRelatorSequences, "generic method for an fp-group", 154 true, [ IsFpGroup ], 0, 155function( G ) 156 157 local genG, monG, amg, FM, genFM, invgenFM, idM, numgenM, invrels, 158 invrules1, invrules2, grprels, mu, genpos, logrws, rws, F, genF, 159 idF, numgenF, genrangeF, g, k, genFMpos, freerels, numrel, relrange, 160 FR, genFR, idR, omega, uptolen, words, fam, iwords, numelts, 161 edgesT, mseq, e, elt, rho, numa, ide, r, lenr, edgelist, 162 edge, w, lw, v, posv, inv, lenv, j, numids, gseq, lenseq; 163 164 genG := GeneratorsOfGroup( G ); 165 monG := MonoidPresentationFpGroup( G ); 166 amg := ArrangementOfMonoidGenerators( G ); 167 FM := FreeGroupOfPresentation( monG ); 168 genFM := GeneratorsOfGroup( FM ); 169 invgenFM := InverseGeneratorsOfFpGroup( FM ); 170 idM := One( FM ); 171 numgenM := Length( genFM ); 172 invrels := InverseRelatorsOfPresentation( monG ); 173 invrules1 := ListWithIdenticalEntries( Length( genFM ), 0 ); 174 invrules2 := Concatenation( List( invrels, r -> [ r, idM ] ), 175 List( invrels, r -> [r^-1, idM ] ) ); 176 grprels := GroupRelatorsOfPresentation( monG ); 177 mu := HomomorphismOfPresentation( monG ); 178 genpos := MonoidGeneratorsFpGroup( G ); 179 logrws := LoggedRewritingSystemFpGroup( G ); 180 #? WHY?? rws := Filtered( logrws, r -> not( r[1] in invrels ) ); 181 rws := List( logrws, r -> [ r[1], r[3] ] ); 182 if ( InfoLevel( InfoIdRel ) > 2 ) then 183 Print( "logrws = \n" ); 184 Display( logrws ); 185 Print( "\nrws = \n" ); 186 Display( rws ); 187 Print( "\n" ); 188 fi; 189 F := FreeGroupOfFpGroup( G ); 190 genF := GeneratorsOfGroup( F ); 191 idF := One( F ); 192 numgenF := Length( genF ); 193 genrangeF := [1..numgenF]; 194 for g in genrangeF do 195 k := g + numgenF; 196 invrules1[g] := [ genFM[g]^-1, genFM[k] ]; 197 invrules1[k] := [ genFM[k]^-1, genFM[g] ]; 198 od; 199 genFMpos := genFM{ genrangeF }; 200 freerels := RelatorsOfFpGroup( G ); 201 numrel := Length( freerels ); 202 relrange := [1..numrel]; 203 FR := FreeRelatorGroup( G ); 204 idR := One( FR ); 205 genFR := GeneratorsOfGroup( FR ); 206 omega := GroupHomomorphismByImages( FR, F, genFR, freerels ); 207 if ( InfoLevel( InfoIdRel ) > 1 ) then 208 Print( "\nhom from FR to F is: \n", omega, "\n\n" ); 209 fi; 210 211 ## construct the first few elements in the group 212 uptolen := 2; ###################### temporary value 213 if ( HasPartialElements( G ) and 214 ( PartialElementsLength( G ) >= uptolen ) ) then 215 words := PartialElements( G ); 216 uptolen := PartialElementsLength( G ); 217 else 218 words := PartialElementsOfMonoidPresentation( G, uptolen ); 219 fi; 220 fam := FamilyObj( words[1] ); 221 iwords := PartialInverseElements( G ); 222 numelts := Length( words ); 223 edgesT := GenerationTree( G ); 224 mseq := [ ]; 225 ## now work through the list of elements, adding each relator in turn 226 e := 0; ## this is the number of monoid elements processed so far 227 while ( e < numelts ) do 228 e := e+1; 229 elt := words[e]; 230 for rho in relrange do 231 Info( InfoIdRel, 2, "[e,rho] = ", [e,rho] ); 232 numa := (e-1)*numrel + rho; 233 ide := [ [ -(rho+numgenM), iwords[e] ] ]; 234 ### cycle [g,r] (from vertex g and reading r along edges) 235 ### is converted to a list of its component edges: 236 ### [source vertex, edge label] (some may be inverse edges) 237 r := grprels[rho]; 238 lenr := Length( r ); 239 edgelist := ListWithIdenticalEntries( lenr, 0 ); 240 edgelist[1] := [ elt, Subword(r,1,1) ]; 241 ### Edges of the cycle which are in the tree are removed, 242 ### and the rest are represented by their position in the 243 ### list of alpha edges. 244 for k in [1..lenr] do 245 edge := edgelist[k]; 246 w := Product( edge ); 247 lw := LoggedReduceWordKB( w, logrws ); 248 v := lw[2]; ## the new vertex 249 posv := Position( words, v ); 250 if ( v = w ) then ## no reduction 251 if ( posv = fail ) then ## v=w is not yet in the tree 252 Add( words, v ); 253 inv := InverseWordInFreeGroupOfPresentation( FM, v ); 254 Add( iwords, inv ); 255 Add( edgesT, edge ); 256 j := Position( genFM, edge[2] ); 257 Add( edgesT, [ v, iwords[j] ] ); 258 fi; 259 else ## v<>w, so there is some logging to include in the ide 260 if ( posv = fail ) then 261 Add( words, v ); 262 inv := InverseWordInFreeGroupOfPresentation( FM, v ); 263 Add( iwords, inv ); 264 lenv := Length( v ); 265 g := Subword( v, lenv, lenv ); 266 Add( edgesT, [ Subword( v, 1, lenv-1 ), g ] ); 267 j := Position( genFM, g ); 268 Add( edgesT, [ v, iwords[j] ] ); 269 fi; 270 Append( ide, lw[1] ); 271 fi; 272 if ( k < lenr ) then 273 edgelist[k+1] := [ v, Subword(r,k+1,k+1) ]; 274 else 275 if not ( v = elt ) then 276 Error( "v <> elt" ); 277 fi; 278 fi; 279 od; 280 w := ide[1][2]^(-1); 281 for k in [1..Length(ide)] do 282 ide[k][2] := ide[k][2]*w; 283 od; 284 ide := RelatorSequenceReduce( G, ide ); 285 if ( ide <> [ ] ) then 286 posv := Position( mseq, ide ); 287 if ( posv = fail ) then 288 Add( mseq, ide ); 289 fi; 290 fi; 291 od; 292 od; 293 Info( InfoIdRel, 1, "mseq has length: ", Length(mseq), "\n" ); 294 Info( InfoIdRel, 3, mseq ); 295 ### convert relator sequences to Y-sequences 296 lenseq := Length( mseq ); 297 mseq := List( [1..lenseq], i -> [ i, mseq[i] ] ); 298 gseq := ConvertToGroupRelatorSequences( G, mseq ); 299 gseq := ReduceGroupRelatorSequences( gseq ); 300 lenseq := Length( gseq ); 301 gseq := List( [1..lenseq], i -> [ i, gseq[i][1], gseq[i][2] ] ); 302 return gseq; 303end ); 304 305############################################################################## 306## 307#M ReduceGroupRelatorSequences 308## 309InstallMethod( ReduceGroupRelatorSequences, "for a list of Ysequences", true, 310 [ IsHomogeneousList ], 0, 311function( L ) 312 313 local changed, L2, lenL, i, idi, leni, rho, j, idj, lenj, k, w, c, ok; 314 315 ### search for conjugate of one identity lying within another 316 changed := true; 317 L2 := ShallowCopy( L ); 318 while changed do 319 Info( InfoIdRel, 1, "## new iteration in ReduceGroupRelatorSequences" ); 320 L2 := Filtered( L2, y -> not ( y[2] = [ ] ) ); 321 lenL := Length( L2 ); 322 Sort( L2, function( K, L ) 323 return GroupRelatorSequenceLessThan( K[2], L[2] ); 324 end ); 325 Info( InfoIdRel, 1, "after sorting:" ); 326 Info( InfoIdRel, 1, "number of identities = ", lenL ); 327 if ( InfoLevel( InfoIdRel ) > 1 ) then 328 Perform( L2, Display ); 329 fi; 330 changed := false; 331 for i in [1..lenL] do 332 idi := L2[i][2]; 333 leni := Length( idi ); 334 if ( leni > 0 ) then 335 rho := idi[1][1]; 336 for j in [i+1..lenL] do 337 idj := L2[j][2]; 338 lenj := Length( idj ); 339 k := 1; 340 while ( k <= (lenj-leni+1) ) do 341 if ( idj[k][1] = rho ) then 342 w := idj[k][2]; 343 c := 1; 344 ok := true; 345 while ( ok and ( c < leni ) ) do 346 c := c+1; 347 if ([idi[c][1],idi[c][2]*w]<>idj[k+c-1]) then 348 ok := false; 349 fi; 350 od; 351 if ok then 352 idj := Concatenation( idj{[1..k-1]}, 353 idj{[(k+leni)..lenj]} ); 354 L2[j][2] := idj; 355 lenj := lenj - leni; 356 if ( InfoLevel( InfoIdRel ) > 0 ) then 357 if ( lenj = 0 ) then 358 Print( "** id ", L2[j][1], 359 " reduced by id ", L2[i][1], 360 " to ", idj, " at [i,j] = ", 361 [i,j], " **\n"); 362 fi; 363 fi; 364 changed := true; 365 k := k-1; 366 fi; 367 fi; 368 k := k+1; 369 od; 370 od; 371 idi := Reversed( List( idi, c -> [ c[1]^-1, c[2] ] ) ); 372 w := idi[1][2]^(-1); 373 for j in [1..Length(idi)] do 374 idi[j][2] := idi[j][2]*w; 375 od; 376 rho := idi[1][1]; 377 for j in [i+1..lenL] do 378 idj := L2[j][2]; 379 lenj := Length( idj ); 380 k := 1; 381 while ( k <= (lenj-leni+1) ) do 382 if ( idj[k][1] = rho ) then 383 w := idj[k][2]; 384 c := 1; 385 ok := true; 386 while ( ok and ( c < leni ) ) do 387 c := c+1; 388 if ([idi[c][1],idi[c][2]*w]<>idj[k+c-1]) then 389 ok := false; 390 fi; 391 od; 392 if ok then 393 idj := Concatenation( idj{[1..k-1]}, 394 idj{[(k+leni)..lenj]} ); 395 L2[j][2] := idj; 396 lenj := lenj - leni; 397 if ( InfoLevel( InfoIdRel ) > 0 ) then 398 if ( lenj = 0 ) then 399 Print( "** id ", L2[j][1], 400 " reduced by reversed id ", L2[i][1], 401 " to ", idj, " at [i,j] = ", 402 [i,j], " **\n"); 403 fi; 404 fi; 405 changed := true; 406 k := k-1; 407 fi; 408 fi; 409 k := k+1; 410 od; 411 od; 412 fi; 413 od; 414 od; 415 return L2; 416end ); 417 418############################################################################# 419## 420#M ConvertToYSequences( <G> ) 421## 422InstallMethod( ConvertToYSequences, "for an fp-group and group relator seq", 423 true, [ IsFpGroup, IsFreeGroup, IsHomogeneousList ], 0, 424function( G, FY, gseq ) 425 426 local monG, elmon, oneM, frgp, frgens, FM, FMfam, L, FYgens, lrws, rws, 427 numids, polys, k, j, pos, ident, leni, irange, gp, npols, i, i1, 428 w, len, rp, nyp, yp, lp, lbest; 429 430 monG := MonoidPresentationFpGroup( G ); 431 if HasElementsOfMonoidPresentation( G ) then 432 elmon := ElementsOfMonoidPresentation( G ); 433 elif HasPartialElements( G ) then 434 elmon := PartialElements( G ); 435 elif ( HasIsFinite( G ) and IsFinite( G ) ) then 436 elmon := ElementsOfMonoidPresentation( G ); 437 else 438 ## using 3 as a suitable word length 439 elmon := PartialElementsOfMonoidPresentation( G, 3 ); 440 fi; 441 oneM := elmon[1]; 442 frgp := FreeRelatorGroup( G ); 443 frgens := GeneratorsOfGroup( frgp ); 444 FM := FreeGroupOfPresentation( monG ); 445 FMfam := ElementsFamily( FamilyObj( FM ) ); 446 lrws := LoggedRewritingSystemFpGroup( G ); 447 rws := List( lrws, r -> [ r[1], r[3] ] ); 448 L := ArrangementOfMonoidGenerators( G ); 449 FYgens := GeneratorsOfGroup( FY ); 450 numids := Length( gseq ); 451 polys := [ ]; 452 k := 0; 453 for j in [1..numids] do 454 Info( InfoIdRel, 2, "=============== j = ", j, " ===============" ); 455 pos := gseq[j][1]; 456 ident := gseq[j][3]; 457 Info( InfoIdRel, 2, "gseq[j] = ", gseq[j] ); 458 leni := Length( ident ); 459 if ( leni > 0 ) then 460 k := k+1; 461 Info( InfoIdRel, 2, "k = ", k ); 462 irange := [1..leni]; 463 gp := ListWithIdenticalEntries( leni, 0 ); 464 npols := ListWithIdenticalEntries( leni, 0 ); 465 for i in irange do 466 i1 := ident[i][1]; 467 w := MonoidWordFpWord( ident[i][2], FMfam, L ); 468 w := ReduceWordKB( w, rws ); 469 if i1 in frgens then 470 gp[i] := i1; 471 npols[i] := MonoidPolyFromCoeffsWords( [+1], [w] ); 472 else 473 gp[i] := i1^(-1); 474 npols[i] := MonoidPolyFromCoeffsWords( [-1], [w] ); 475 fi; 476 od; 477 Info( InfoIdRel, 2, "npols = ", npols ); 478 rp := ModulePolyFromGensPolys( gp, npols ); 479 Info( InfoIdRel, 2, "rp = ", rp ); 480 len := Length( rp ); 481 if not ( len = 0 ) then 482 nyp := MonoidPolyFromCoeffsWords( [ 1 ], [ oneM ] ); 483 Info( InfoIdRel, 2, "nyp = ", nyp ); 484 yp := ModulePolyFromGensPolys( [ FYgens[pos] ], [ nyp ] ); 485 Info( InfoIdRel, 2, "yp = ", yp ); 486 lp := LoggedModulePolyNC( yp, rp ); 487 Info( InfoIdRel, 2, "lp = ", lp ); 488 lbest := MinimiseLeadTerm( lp, G, rws ); 489 lp := lbest*(-1); 490 Info( InfoIdRel, 2, "lp = ", lp ); 491 if ( lbest < lp ) then 492 Add( polys, lbest ); 493 else 494 Add( polys, lp ); 495 fi; 496 fi; 497 fi; 498 od; 499 Sort( polys ); 500 return polys; 501end ); 502 503############################################################################# 504## 505#M ReduceModulePolyList( <L> ) 506## 507InstallMethod( ReduceModulePolyList, "for a list of identities", true, 508 [ IsFpGroup, IsHomogeneousList, IsHomogeneousList, IsHomogeneousList ], 0, 509function( G, elmon, rws, modpols ) 510 511 local irrepols, irrerems, sats, irrenum, m1, m0, i, lp, rp, leadgp, yp, 512 logrem, remyp, remrp, rem, remsat, m, r; 513 514 irrepols := [ ]; 515 irrerems:= [ ]; 516 sats := [ ]; 517 irrenum := 0; 518 m1 := RelatorModulePoly( modpols[1] ); 519 m0 := m1 - m1; 520 for i in [1..Length(modpols)] do 521 lp := modpols[i]; 522 if ( InfoLevel( InfoIdRel ) > 2 ) then 523 Print( "\n\n", i, " : "); Display( lp ); Print( "\n" ); 524 fi; 525 rp := RelatorModulePoly( lp ); 526 leadgp := LeadGenerator( rp ); 527 yp := YSequenceModulePoly( lp ); 528 if ( InfoLevel( InfoIdRel ) > 2 ) then 529 Print( "\nlooking at polynomial number ", i, ": \n" ); 530 Display( lp ); 531 Print( "\n" ); 532 fi; 533 ##################### saturation used here: ####################### 534 if ( sats = [ ] ) then 535 logrem := lp; 536 remyp := yp; 537 remrp := rp; 538 else 539 rem := LoggedReduceModulePoly( rp, rws, sats, m0 ); 540 remyp := yp + YSequenceModulePoly( rem ); 541 remrp := RelatorModulePoly( rem ); 542 logrem := LoggedModulePoly( remyp, remrp ); 543 fi; 544 if ( remrp = m0 ) then 545 if ( InfoLevel( InfoIdRel ) > 2 ) then 546 Print( "reduced to zero by:\n" ); 547 Display( remyp ); 548 Print( "\n" ); 549 fi; 550 else 551 if ( LeadGenerator( remrp ) <> leadgp ) then 552 if ( InfoLevel( InfoIdRel ) > 2 ) then 553 Print( "\n! minimising leading term: !\n\n" ); 554 logrem := MinimiseLeadTerm( logrem, G, rws ); 555 fi; 556 fi; 557 if ( InfoLevel( InfoIdRel ) > 2 ) then 558 Print( "logrem = " ); Display(logrem); Print("\n"); 559 fi; 560 irrenum := irrenum + 1; 561 remsat := SaturatedSetLoggedModulePoly( logrem, elmon, rws, sats ); 562 if ( InfoLevel( InfoIdRel ) > 2 ) then 563 Print( "\nsaturated set:\n" ); 564 for m in [1..Length(remsat)] do 565 Print( m, ": "); Display(remsat[m]); Print("\n"); 566 od; 567 Print( "irreducible number ", irrenum, " :-\n" ); 568 Display( lp ); 569 Print( "\n" ); 570 fi; 571 Add( irrepols, lp ); 572 Add( irrerems, logrem ); 573 Add( sats, remsat ); 574 SortParallel( irrerems, sats ); 575 if ( InfoLevel( InfoIdRel ) > 2 ) then 576 Print( "\ncurrent state of reduced list, irrerems:\n" ); 577 for r in irrerems do 578 Display( r ); 579 Print( "\n" ); 580 od; 581 fi; 582 fi; 583 od; 584 return [ irrepols, irrerems, irrenum, sats ]; 585end ); 586 587############################################################################# 588## 589#M IdentitiesAmongRelators( <G> ) 590## 591InstallMethod( IdentitiesAmongRelators, "for an fp-group", true, 592 [ IsFpGroup ], 0, 593function( G ) 594 595 local L, monG, elmon, rws, F, FR, genFR, FM, FMgens, FY, FYgens, 596 gseq, modpols, redpols, irrepols, irrerems, irrenum, sats, 597 r, ids, pol, ymp, gymp, pos, seq; 598 599 if HasArrangementOfMonoidGenerators( G ) then 600 L := ArrangementOfMonoidGenerators( G ); 601 else 602 L := ArrangeMonoidGenerators( G ); 603 fi; 604 monG := MonoidPresentationFpGroup( G ); 605 if HasPartialElements( G ) then 606 elmon := PartialElements( G ); 607 else 608 elmon := ElementsOfMonoidPresentation( G ); 609 fi; 610 rws := List( LoggedRewritingSystemFpGroup( G ), r -> [ r[1], r[3] ] ); 611 F := FreeGroupOfFpGroup( G ); 612 FR := FreeGroupOfPresentation( monG ); 613 genFR := GeneratorsOfGroup( FR ); 614 FM := FreeGroupOfPresentation( monG ); 615 FMgens := GeneratorsOfGroup( FM ); 616 gseq := IdentityRelatorSequences( G ); 617 FY := FreeYSequenceGroup( G ); 618 FYgens := GeneratorsOfGroup( FY ); 619 modpols := ConvertToYSequences( G, FY, gseq ); 620 redpols := ReduceModulePolyList( G, elmon, rws, modpols ); 621 irrepols := redpols[1]; 622 irrerems := redpols[2]; 623 irrenum := redpols[3]; 624 sats := redpols[4]; 625 if ( InfoLevel( InfoIdRel ) > 0 ) then 626 Print( "\nThere were ", irrenum, " irreducibles found.\n" ); 627 Print( "The corresponding saturated sets have size:\n" ); 628 Print( List( sats, L -> Length(L) ), "\n\n" ); 629 Print( "The irreducibles and the (reordered) remainders are:\n\n" ); 630 for r in [1..irrenum] do 631 Print( r, " : ", irrepols[r], "\n" ); 632 od; 633 Print( "-------------------------------------------------------\n\n" ); 634 for r in [1..irrenum] do 635 Print( r, " : ", irrerems[r], "\n" ); 636 od; 637 fi; 638 SetIdentityYSequences( G, irrepols ); 639 ## now pick out the relator sequences corresponding to these polys 640 ids := ListWithIdenticalEntries( irrenum, 0 ); 641 for r in [1..irrenum] do 642 pol := irrepols[r]; 643 ymp := YSequenceModulePoly( pol ); 644 gymp := GeneratorsOfModulePoly( ymp )[1]; 645 pos := Position( FYgens, gymp ); 646 seq := gseq[pos]; 647 ids[r] := seq[3]; 648 od; 649 #? return [ irrepols, irrerems ]; 650 return ids; 651end ); 652 653############################################################################# 654## 655#M IdentitiesAmongRelatorsKB( <G> ) 656## 657InstallMethod( IdentitiesAmongRelatorsKB, "for an FpGroup", true, 658 [ IsFpGroup ], 0, 659function( G ) 660 661 local L, monG, elmon, rws, F, FR, genFR, FM, FMgens, FY, FYgens, mseq, 662 lenseq, gseq, modpols, redpols, irrepols, irrerems, irrenum, sats, 663 r, ids, pol, ymp, gymp, pos, seq; 664 665 L := ArrangementOfMonoidGenerators( G ); 666 monG := MonoidPresentationFpGroup( G ); 667 if HasElementsOfMonoidPresentation( G ) then 668 elmon := ElementsOfMonoidPresentation( G ); 669 elif HasPartialElements( G ) then 670 elmon := PartialElements( G ); 671 else 672 Error( "no list of elements available" ); 673 fi; 674 rws := List( LoggedRewritingSystemFpGroup( G ), r -> [ r[1], r[3] ] ); 675 F := FreeGroupOfFpGroup( G ); 676 FR := FreeGroupOfPresentation( monG ); 677 genFR := GeneratorsOfGroup( FR ); 678 FM := FreeGroupOfPresentation( monG ); 679 FMgens := GeneratorsOfGroup( FM ); 680 if not HasIdentityRelatorSequencesKB( G ) then 681 Error( "G does not yet have IdentityRelatorSequencesKB" ); 682 fi; 683 gseq := IdentityRelatorSequencesKB( G ); 684 lenseq := Length( gseq ); 685 FY := FreeYSequenceGroupKB( G ); 686 FYgens := GeneratorsOfGroup( FY ); 687 modpols := ConvertToYSequences( G, FY, gseq ); 688 redpols := ReduceModulePolyList( G, elmon, rws, modpols ); 689 irrepols := redpols[1]; 690 irrerems := redpols[2]; 691 irrenum := redpols[3]; 692 sats := redpols[4]; 693 if ( InfoLevel( InfoIdRel ) > 0 ) then 694 Print( "\nThere were ", irrenum, " irreducibles found.\n" ); 695 Print( "The corresponding saturated sets have size:\n" ); 696 Print( List( sats, L -> Length(L) ), "\n\n" ); 697 Print( "The irreducibles and the (reordered) remainders are:\n\n" ); 698 for r in [1..irrenum] do 699 Print( r, " : ", irrepols[r], "\n" ); 700 od; 701 Print( "-------------------------------------------------------\n\n" ); 702 for r in [1..irrenum] do 703 Print( r, " : ", irrerems[r], "\n" ); 704 od; 705 fi; 706 SetIdentityYSequencesKB( G, irrepols ); 707 ## now pick out the relator sequences corresponding to these polys 708 ids := ListWithIdenticalEntries( irrenum, 0 ); 709 for r in [1..irrenum] do 710 pol := irrepols[r]; 711 ymp := YSequenceModulePoly( pol ); 712 gymp := GeneratorsOfModulePoly( ymp )[1]; 713 pos := Position( FYgens, gymp ); 714 seq := gseq[pos]; 715 ids[r] := seq[3]; 716 od; 717 #? return [ irrepols, irrerems ]; 718 return ids; 719end ); 720 721############################################################################# 722## 723#M RootIdentities( <G> ) 724## 725InstallMethod( RootIdentities, "for an FpGroup", true, [ IsFpGroup ], 0, 726function( G ) 727 728 local idsR, idsY, len, rng; 729 730 if ( HasIdentitiesAmongRelators( G ) and HasIdentityYSequences( G ) ) then 731 idsR := IdentitiesAmongRelators( G ); 732 idsY := IdentityYSequences( G ); 733 len := List( idsY, i -> Length( RelatorModulePoly(i) ) ); 734 rng := Filtered( [1..Length(len)], i -> len[i]=1 ); 735 return idsR{rng}; 736 else 737 Print( "direct method not yet implemented\n" ); 738 return fail; 739 fi; 740end ); 741 742###############*############################################################# 743## 744#E idrels.gi . . . . . . . . . . . . . . . . . . . . . . . . . . . ends here 745## 746