This file is indexed.

/usr/share/gap/doc/ref/chap48.html is in gap-doc 4r8p8-3.

This file is owned by root:root, with mode 0o644.

The actual contents of the file can be viewed below.

   1
   2
   3
   4
   5
   6
   7
   8
   9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43
  44
  45
  46
  47
  48
  49
  50
  51
  52
  53
  54
  55
  56
  57
  58
  59
  60
  61
  62
  63
  64
  65
  66
  67
  68
  69
  70
  71
  72
  73
  74
  75
  76
  77
  78
  79
  80
  81
  82
  83
  84
  85
  86
  87
  88
  89
  90
  91
  92
  93
  94
  95
  96
  97
  98
  99
 100
 101
 102
 103
 104
 105
 106
 107
 108
 109
 110
 111
 112
 113
 114
 115
 116
 117
 118
 119
 120
 121
 122
 123
 124
 125
 126
 127
 128
 129
 130
 131
 132
 133
 134
 135
 136
 137
 138
 139
 140
 141
 142
 143
 144
 145
 146
 147
 148
 149
 150
 151
 152
 153
 154
 155
 156
 157
 158
 159
 160
 161
 162
 163
 164
 165
 166
 167
 168
 169
 170
 171
 172
 173
 174
 175
 176
 177
 178
 179
 180
 181
 182
 183
 184
 185
 186
 187
 188
 189
 190
 191
 192
 193
 194
 195
 196
 197
 198
 199
 200
 201
 202
 203
 204
 205
 206
 207
 208
 209
 210
 211
 212
 213
 214
 215
 216
 217
 218
 219
 220
 221
 222
 223
 224
 225
 226
 227
 228
 229
 230
 231
 232
 233
 234
 235
 236
 237
 238
 239
 240
 241
 242
 243
 244
 245
 246
 247
 248
 249
 250
 251
 252
 253
 254
 255
 256
 257
 258
 259
 260
 261
 262
 263
 264
 265
 266
 267
 268
 269
 270
 271
 272
 273
 274
 275
 276
 277
 278
 279
 280
 281
 282
 283
 284
 285
 286
 287
 288
 289
 290
 291
 292
 293
 294
 295
 296
 297
 298
 299
 300
 301
 302
 303
 304
 305
 306
 307
 308
 309
 310
 311
 312
 313
 314
 315
 316
 317
 318
 319
 320
 321
 322
 323
 324
 325
 326
 327
 328
 329
 330
 331
 332
 333
 334
 335
 336
 337
 338
 339
 340
 341
 342
 343
 344
 345
 346
 347
 348
 349
 350
 351
 352
 353
 354
 355
 356
 357
 358
 359
 360
 361
 362
 363
 364
 365
 366
 367
 368
 369
 370
 371
 372
 373
 374
 375
 376
 377
 378
 379
 380
 381
 382
 383
 384
 385
 386
 387
 388
 389
 390
 391
 392
 393
 394
 395
 396
 397
 398
 399
 400
 401
 402
 403
 404
 405
 406
 407
 408
 409
 410
 411
 412
 413
 414
 415
 416
 417
 418
 419
 420
 421
 422
 423
 424
 425
 426
 427
 428
 429
 430
 431
 432
 433
 434
 435
 436
 437
 438
 439
 440
 441
 442
 443
 444
 445
 446
 447
 448
 449
 450
 451
 452
 453
 454
 455
 456
 457
 458
 459
 460
 461
 462
 463
 464
 465
 466
 467
 468
 469
 470
 471
 472
 473
 474
 475
 476
 477
 478
 479
 480
 481
 482
 483
 484
 485
 486
 487
 488
 489
 490
 491
 492
 493
 494
 495
 496
 497
 498
 499
 500
 501
 502
 503
 504
 505
 506
 507
 508
 509
 510
 511
 512
 513
 514
 515
 516
 517
 518
 519
 520
 521
 522
 523
 524
 525
 526
 527
 528
 529
 530
 531
 532
 533
 534
 535
 536
 537
 538
 539
 540
 541
 542
 543
 544
 545
 546
 547
 548
 549
 550
 551
 552
 553
 554
 555
 556
 557
 558
 559
 560
 561
 562
 563
 564
 565
 566
 567
 568
 569
 570
 571
 572
 573
 574
 575
 576
 577
 578
 579
 580
 581
 582
 583
 584
 585
 586
 587
 588
 589
 590
 591
 592
 593
 594
 595
 596
 597
 598
 599
 600
 601
 602
 603
 604
 605
 606
 607
 608
 609
 610
 611
 612
 613
 614
 615
 616
 617
 618
 619
 620
 621
 622
 623
 624
 625
 626
 627
 628
 629
 630
 631
 632
 633
 634
 635
 636
 637
 638
 639
 640
 641
 642
 643
 644
 645
 646
 647
 648
 649
 650
 651
 652
 653
 654
 655
 656
 657
 658
 659
 660
 661
 662
 663
 664
 665
 666
 667
 668
 669
 670
 671
 672
 673
 674
 675
 676
 677
 678
 679
 680
 681
 682
 683
 684
 685
 686
 687
 688
 689
 690
 691
 692
 693
 694
 695
 696
 697
 698
 699
 700
 701
 702
 703
 704
 705
 706
 707
 708
 709
 710
 711
 712
 713
 714
 715
 716
 717
 718
 719
 720
 721
 722
 723
 724
 725
 726
 727
 728
 729
 730
 731
 732
 733
 734
 735
 736
 737
 738
 739
 740
 741
 742
 743
 744
 745
 746
 747
 748
 749
 750
 751
 752
 753
 754
 755
 756
 757
 758
 759
 760
 761
 762
 763
 764
 765
 766
 767
 768
 769
 770
 771
 772
 773
 774
 775
 776
 777
 778
 779
 780
 781
 782
 783
 784
 785
 786
 787
 788
 789
 790
 791
 792
 793
 794
 795
 796
 797
 798
 799
 800
 801
 802
 803
 804
 805
 806
 807
 808
 809
 810
 811
 812
 813
 814
 815
 816
 817
 818
 819
 820
 821
 822
 823
 824
 825
 826
 827
 828
 829
 830
 831
 832
 833
 834
 835
 836
 837
 838
 839
 840
 841
 842
 843
 844
 845
 846
 847
 848
 849
 850
 851
 852
 853
 854
 855
 856
 857
 858
 859
 860
 861
 862
 863
 864
 865
 866
 867
 868
 869
 870
 871
 872
 873
 874
 875
 876
 877
 878
 879
 880
 881
 882
 883
 884
 885
 886
 887
 888
 889
 890
 891
 892
 893
 894
 895
 896
 897
 898
 899
 900
 901
 902
 903
 904
 905
 906
 907
 908
 909
 910
 911
 912
 913
 914
 915
 916
 917
 918
 919
 920
 921
 922
 923
 924
 925
 926
 927
 928
 929
 930
 931
 932
 933
 934
 935
 936
 937
 938
 939
 940
 941
 942
 943
 944
 945
 946
 947
 948
 949
 950
 951
 952
 953
 954
 955
 956
 957
 958
 959
 960
 961
 962
 963
 964
 965
 966
 967
 968
 969
 970
 971
 972
 973
 974
 975
 976
 977
 978
 979
 980
 981
 982
 983
 984
 985
 986
 987
 988
 989
 990
 991
 992
 993
 994
 995
 996
 997
 998
 999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
<?xml version="1.0" encoding="UTF-8"?>

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
         "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">

<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head>
<title>GAP (ref) - Chapter 48: Presentations and Tietze Transformations</title>
<meta http-equiv="content-type" content="text/html; charset=UTF-8" />
<meta name="generator" content="GAPDoc2HTML" />
<link rel="stylesheet" type="text/css" href="manual.css" />
<script src="manual.js" type="text/javascript"></script>
<script type="text/javascript">overwriteStyle();</script>
</head>
<body class="chap48"  onload="jscontent()">


<div class="chlinktop"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a>  <a href="chap1.html">1</a>  <a href="chap2.html">2</a>  <a href="chap3.html">3</a>  <a href="chap4.html">4</a>  <a href="chap5.html">5</a>  <a href="chap6.html">6</a>  <a href="chap7.html">7</a>  <a href="chap8.html">8</a>  <a href="chap9.html">9</a>  <a href="chap10.html">10</a>  <a href="chap11.html">11</a>  <a href="chap12.html">12</a>  <a href="chap13.html">13</a>  <a href="chap14.html">14</a>  <a href="chap15.html">15</a>  <a href="chap16.html">16</a>  <a href="chap17.html">17</a>  <a href="chap18.html">18</a>  <a href="chap19.html">19</a>  <a href="chap20.html">20</a>  <a href="chap21.html">21</a>  <a href="chap22.html">22</a>  <a href="chap23.html">23</a>  <a href="chap24.html">24</a>  <a href="chap25.html">25</a>  <a href="chap26.html">26</a>  <a href="chap27.html">27</a>  <a href="chap28.html">28</a>  <a href="chap29.html">29</a>  <a href="chap30.html">30</a>  <a href="chap31.html">31</a>  <a href="chap32.html">32</a>  <a href="chap33.html">33</a>  <a href="chap34.html">34</a>  <a href="chap35.html">35</a>  <a href="chap36.html">36</a>  <a href="chap37.html">37</a>  <a href="chap38.html">38</a>  <a href="chap39.html">39</a>  <a href="chap40.html">40</a>  <a href="chap41.html">41</a>  <a href="chap42.html">42</a>  <a href="chap43.html">43</a>  <a href="chap44.html">44</a>  <a href="chap45.html">45</a>  <a href="chap46.html">46</a>  <a href="chap47.html">47</a>  <a href="chap48.html">48</a>  <a href="chap49.html">49</a>  <a href="chap50.html">50</a>  <a href="chap51.html">51</a>  <a href="chap52.html">52</a>  <a href="chap53.html">53</a>  <a href="chap54.html">54</a>  <a href="chap55.html">55</a>  <a href="chap56.html">56</a>  <a href="chap57.html">57</a>  <a href="chap58.html">58</a>  <a href="chap59.html">59</a>  <a href="chap60.html">60</a>  <a href="chap61.html">61</a>  <a href="chap62.html">62</a>  <a href="chap63.html">63</a>  <a href="chap64.html">64</a>  <a href="chap65.html">65</a>  <a href="chap66.html">66</a>  <a href="chap67.html">67</a>  <a href="chap68.html">68</a>  <a href="chap69.html">69</a>  <a href="chap70.html">70</a>  <a href="chap71.html">71</a>  <a href="chap72.html">72</a>  <a href="chap73.html">73</a>  <a href="chap74.html">74</a>  <a href="chap75.html">75</a>  <a href="chap76.html">76</a>  <a href="chap77.html">77</a>  <a href="chap78.html">78</a>  <a href="chap79.html">79</a>  <a href="chap80.html">80</a>  <a href="chap81.html">81</a>  <a href="chap82.html">82</a>  <a href="chap83.html">83</a>  <a href="chap84.html">84</a>  <a href="chap85.html">85</a>  <a href="chap86.html">86</a>  <a href="chap87.html">87</a>  <a href="chapBib.html">Bib</a>  <a href="chapInd.html">Ind</a>  </div>

<div class="chlinkprevnexttop">&nbsp;<a href="chap0.html">[Top of Book]</a>&nbsp;  <a href="chap0.html#contents">[Contents]</a>&nbsp;  &nbsp;<a href="chap47.html">[Previous Chapter]</a>&nbsp;  &nbsp;<a href="chap49.html">[Next Chapter]</a>&nbsp;  </div>

<p id="mathjaxlink" class="pcenter"><a href="chap48_mj.html">[MathJax on]</a></p>
<p><a id="X782985197BE809BF" name="X782985197BE809BF"></a></p>
<div class="ChapSects"><a href="chap48.html#X782985197BE809BF">48 <span class="Heading">Presentations and Tietze Transformations</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss">&nbsp;</span><a href="chap48.html#X867D00387957450F">48.1 <span class="Heading">Creating Presentations</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap48.html#X797867B287AD92F8">48.1-1 PresentationFpGroup</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap48.html#X8637837A79422445">48.1-2 TzSort</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap48.html#X849429BC7D435F77">48.1-3 GeneratorsOfPresentation</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap48.html#X7D6F40A87F24D3D6">48.1-4 FpGroupPresentation</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap48.html#X84E056C57AFEDEA8">48.1-5 PresentationViaCosetTable</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap48.html#X7E1F2658827FC228">48.1-6 SimplifiedFpGroup</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss">&nbsp;</span><a href="chap48.html#X8118FECE7AD1879B">48.2 <span class="Heading">Subgroup Presentations</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap48.html#X7DB32FA97DAC5AC8">48.2-1 PresentationSubgroup</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap48.html#X857365CD87ADC29E">48.2-2 <span class="Heading">PresentationSubgroupRrs</span></a>
</span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap48.html#X7FCE7ED581CF7897">48.2-3 PrimaryGeneratorWords</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap48.html#X80BA10F780EAE68E">48.2-4 PresentationSubgroupMtc</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap48.html#X7D6A52837BEE5C3D">48.2-5 PresentationNormalClosureRrs</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap48.html#X7A7E5D0084DB0B4F">48.2-6 PresentationNormalClosure</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss">&nbsp;</span><a href="chap48.html#X7BC960AB7E8DE419">48.3 <span class="Heading">Relators in a Presentation</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap48.html#X8365BAFA785FCD8D">48.3-1 TietzeWordAbstractWord</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap48.html#X8573E91C838B1D13">48.3-2 AbstractWordTietzeWord</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss">&nbsp;</span><a href="chap48.html#X867F64FA840B3F81">48.4 <span class="Heading">Printing Presentations</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap48.html#X847EA6737C21171C">48.4-1 TzPrintGenerators</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap48.html#X821B63DD82894443">48.4-2 TzPrintRelators</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap48.html#X852C52C37FAAB7DD">48.4-3 TzPrintLengths</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap48.html#X7D7B3F46865443E4">48.4-4 TzPrintStatus</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap48.html#X85F8DAE27F06C32B">48.4-5 TzPrintPresentation</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap48.html#X7CA8BA51802655FC">48.4-6 TzPrint</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap48.html#X82F6B0EE7C7C7901">48.4-7 TzPrintPairs</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss">&nbsp;</span><a href="chap48.html#X82455E5885D73FFF">48.5 <span class="Heading">Changing Presentations</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap48.html#X7F632A6D8685855D">48.5-1 AddGenerator</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap48.html#X83A5667086FD538A">48.5-2 TzNewGenerator</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap48.html#X78D1BCE67FA852D8">48.5-3 AddRelator</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap48.html#X7B11E89E78A22EBF">48.5-4 RemoveRelator</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss">&nbsp;</span><a href="chap48.html#X829B634286471AB7">48.6 <span class="Heading">Tietze Transformations</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap48.html#X7C4A30328224C466">48.6-1 TzGo</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap48.html#X78C3D23387DAC35A">48.6-2 SimplifyPresentation</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap48.html#X801D3D8984E1CA55">48.6-3 TzGoGo</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss">&nbsp;</span><a href="chap48.html#X7D19E30080290FC7">48.7 <span class="Heading">Elementary Tietze Transformations</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap48.html#X85989AF886EC2BF6">48.7-1 <span class="Heading">TzEliminate</span></a>
</span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap48.html#X7DF4BBDF839643DD">48.7-2 TzSearch</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap48.html#X87F7A87A7ACF2445">48.7-3 TzSearchEqual</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap48.html#X80D31A0F7C2A51BD">48.7-4 TzFindCyclicJoins</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss">&nbsp;</span><a href="chap48.html#X7D2FACCF79F57040">48.8 <span class="Heading">Tietze Transformations that introduce new Generators</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap48.html#X846DB23E8236FF8A">48.8-1 <span class="Heading">TzSubstitute</span></a>
</span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap48.html#X7ADE3B437C19B94D">48.8-2 TzSubstituteCyclicJoins</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss">&nbsp;</span><a href="chap48.html#X85E703997A0212EE">48.9 <span class="Heading">Tracing generator images through Tietze transformations</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap48.html#X7D855FA08242898A">48.9-1 TzInitGeneratorImages</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap48.html#X7AB9A06F80FB3659">48.9-2 OldGeneratorsOfPresentation</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap48.html#X798B38F87C082C45">48.9-3 TzImagesOldGens</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap48.html#X7AC41B117DBB87D6">48.9-4 TzPreImagesNewGens</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap48.html#X7F086D0E7AD6173B">48.9-5 TzPrintGeneratorImages</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss">&nbsp;</span><a href="chap48.html#X7D9E283D81CCCF1A">48.10 <span class="Heading">The Decoding Tree Procedure</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap48.html#X7ACBFE2F78D72A31">48.10-1 DecodeTree</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss">&nbsp;</span><a href="chap48.html#X856F37537E9927EE">48.11 <span class="Heading">Tietze Options</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap48.html#X8178683283214D88">48.11-1 TzOptions</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap48.html#X7BC90B6882DE6D10">48.11-2 TzPrintOptions</a></span>
</div></div>
</div>

<h3>48 <span class="Heading">Presentations and Tietze Transformations</span></h3>

<p>A finite presentation describes a group, but usually there is a multitude of presentations that describe isomorphic groups. Therefore a presentation in <strong class="pkg">GAP</strong> is different from a finitely presented group though there are ways to translate between both.</p>

<p>An important feature of presentations is that they can be modified (see sections <a href="chap48.html#X82455E5885D73FFF"><span class="RefLink">48.5</span></a> to <a href="chap48.html#X7D2FACCF79F57040"><span class="RefLink">48.8</span></a>).</p>

<p>If you only want to get new presentations for subgroups of a finitely presented group (and do not want to manipulate presentations yourself), chances are that the operation <code class="func">IsomorphismFpGroup</code> (<a href="chap47.html#X7F28268F850F454E"><span class="RefLink">47.11-1</span></a>) already does what you want (see <a href="chap47.html#X826604AA7F18BFA3"><span class="RefLink">47.12</span></a>).</p>

<p><a id="X867D00387957450F" name="X867D00387957450F"></a></p>

<h4>48.1 <span class="Heading">Creating Presentations</span></h4>

<p>Most of the functions creating presentations and all functions performing Tietze transformations on them sort the relators by increasing lengths. The function <code class="func">PresentationFpGroup</code> (<a href="chap48.html#X797867B287AD92F8"><span class="RefLink">48.1-1</span></a>) is an exception because it is intended to reflect the relators that were used to define the involved f. p. group. You may use the command <code class="func">TzSort</code> (<a href="chap48.html#X8637837A79422445"><span class="RefLink">48.1-2</span></a>) to sort the presentation.</p>

<p><a id="X797867B287AD92F8" name="X797867B287AD92F8"></a></p>

<h5>48.1-1 PresentationFpGroup</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; PresentationFpGroup</code>( <var class="Arg">G</var>[, <var class="Arg">printlevel</var>] )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
<p>creates a presentation, i. e., a Tietze object, for the given finitely presented group <var class="Arg">G</var>. This presentation will be exactly as the presentation of <var class="Arg">G</var> and <em>no</em> initial Tietze transformations are applied to it.</p>

<p>The optional <var class="Arg">printlevel</var> parameter can be used to restrict or to extend the amount of output provided by Tietze transformation commands when being applied to the created presentation. The default value 1 is designed for interactive use and implies explicit messages to be displayed by most of these commands. A <var class="Arg">printlevel</var> value of 0 will suppress these messages, whereas a <var class="Arg">printlevel</var> value of 2 will enforce some additional output.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">f := FreeGroup( "a", "b" );</span>
&lt;free group on the generators [ a, b ]&gt;
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">g := f / [ f.1^3, f.2^2, (f.1*f.2)^3 ];</span>
&lt;fp group on the generators [ a, b ]&gt;
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">p := PresentationFpGroup( g );</span>
&lt;presentation with 2 gens and 3 rels of total length 11&gt;
</pre></div>

<p><a id="X8637837A79422445" name="X8637837A79422445"></a></p>

<h5>48.1-2 TzSort</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; TzSort</code>( <var class="Arg">P</var> )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
<p>sorts the relators of the given presentation <var class="Arg">P</var> by increasing lengths. There is no particular ordering defined for the relators of equal length. Note that <code class="func">TzSort</code> does not return a new object. It changes the given presentation.</p>

<p><a id="X849429BC7D435F77" name="X849429BC7D435F77"></a></p>

<h5>48.1-3 GeneratorsOfPresentation</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; GeneratorsOfPresentation</code>( <var class="Arg">P</var> )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
<p>returns a list of free generators that is a shallow copy (see <code class="func">ShallowCopy</code> (<a href="chap12.html#X846BC7107C352031"><span class="RefLink">12.7-1</span></a>)) of the current generators of the presentation <var class="Arg">P</var>.</p>

<p><a id="X7D6F40A87F24D3D6" name="X7D6F40A87F24D3D6"></a></p>

<h5>48.1-4 FpGroupPresentation</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; FpGroupPresentation</code>( <var class="Arg">P</var>[, <var class="Arg">nam</var>] )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
<p>constructs an f. p. group as defined by the given Tietze presentation <var class="Arg">P</var>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">h := FpGroupPresentation( p );</span>
&lt;fp group on the generators [ a, b ]&gt;
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">h = g;</span>
false
</pre></div>

<p><a id="X84E056C57AFEDEA8" name="X84E056C57AFEDEA8"></a></p>

<h5>48.1-5 PresentationViaCosetTable</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; PresentationViaCosetTable</code>( <var class="Arg">G</var>[, <var class="Arg">F</var>, <var class="Arg">words</var>] )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
<p>constructs a presentation for a given concrete finite group. It applies the relations finding algorithm which has been described in <a href="chapBib.html#biBCan73">[Can73]</a> and <a href="chapBib.html#biBNeu82">[Neu82]</a>. It automatically applies Tietze transformations to the presentation found.</p>

<p>If only a group <var class="Arg">G</var> has been specified, the single stage algorithm is applied.</p>

<p>The operation <code class="func">IsomorphismFpGroup</code> (<a href="chap47.html#X7F28268F850F454E"><span class="RefLink">47.11-1</span></a>) in contrast uses a multiple-stage algorithm using a chief series and stabilizer chains. It usually should be used rather than <code class="func">PresentationViaCosetTable</code>. (It does not apply Tietze transformations automatically.)</p>

<p>If the two stage algorithm is to be used, <code class="func">PresentationViaCosetTable</code> expects a subgroup <var class="Arg">H</var> of <var class="Arg">G</var> to be provided in form of two additional arguments <var class="Arg">F</var> and <var class="Arg">words</var>, where <var class="Arg">F</var> is a free group with the same number of generators as <var class="Arg">G</var>, and <var class="Arg">words</var> is a list of words in the generators of <var class="Arg">F</var> which supply a list of generators of <var class="Arg">H</var> if they are evaluated as words in the corresponding generators of <var class="Arg">G</var>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">G := GeneralLinearGroup( 2, 7 );</span>
GL(2,7)
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">GeneratorsOfGroup( G );</span>
[ [ [ Z(7), 0*Z(7) ], [ 0*Z(7), Z(7)^0 ] ], 
  [ [ Z(7)^3, Z(7)^0 ], [ Z(7)^3, 0*Z(7) ] ] ]
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">Size( G );</span>
2016
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">P := PresentationViaCosetTable( G );</span>
&lt;presentation with 2 gens and 5 rels of total length 46&gt;
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">TzPrintRelators( P );</span>
#I  1. f2^3
#I  2. f1^6
#I  3. (f1^-1*f2^-1)^6
#I  4. f1*f2*f1^-1*f2^-1*f1*f2^-1*f1^-1*f2*f1*f2^-1*f1^-1*f2^-1
#I  5. f1^-3*f2*f1*f2*(f1^-1*f2^-1)^2*f1^-2*f2
</pre></div>

<p>The two stage algorithm saves an essential amount of space by constructing two coset tables of lengths <span class="SimpleMath">|H|</span> and <span class="SimpleMath">|G|/|H|</span> instead of just one coset table of length <span class="SimpleMath">|G|</span>. The next example shows an application of this option in the case of a subgroup of size 7920 and index 12 in a permutation group of size 95040.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">M12 := Group( [ (1,2,3,4,5,6,7,8,9,10,11), (3,7,11,8)(4,10,5,6),</span>
<span class="GAPprompt">&gt;</span> <span class="GAPinput">(1,12)(2,11)(3,6)(4,8)(5,9)(7,10) ], () );;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">F := FreeGroup( "a", "b", "c" );</span>
&lt;free group on the generators [ a, b, c ]&gt;
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">words := [ F.1, F.2 ];</span>
[ a, b ]
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">P := PresentationViaCosetTable( M12, F, words );</span>
&lt;presentation with 3 gens and 10 rels of total length 97&gt;
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">G := FpGroupPresentation( P );</span>
&lt;fp group on the generators [ a, b, c ]&gt;
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">RelatorsOfFpGroup( G );</span>
[ c^2, b^4, (a*c)^3, (a*b^-2)^3, a^11, 
  a^2*b*a^-2*b^-1*(b^-1*a)^2*a*b^-1, (a*(b*a^-1)^2*b^-1)^2, 
  a^2*b*a^2*b^-2*a^-1*b*(a^-1*b^-1)^2, 
  (a*b)^2*a^2*b^-1*a^-1*b^-1*a*c*b*c, a^2*(a^2*b)^2*a^-2*c*a*b*a^-1*c 
 ]
</pre></div>

<p>Before it is returned, the resulting presentation is being simplified by appropriate calls of the function <code class="func">SimplifyPresentation</code> (<a href="chap48.html#X78C3D23387DAC35A"><span class="RefLink">48.6-2</span></a>) (see <a href="chap48.html#X829B634286471AB7"><span class="RefLink">48.6</span></a>), but without allowing any eliminations of generators. This restriction guarantees that we get a bijection between the list of generators of <var class="Arg">G</var> and the list of generators in the presentation. Hence, if the generators of <var class="Arg">G</var> are redundant and if you don't care for the bijection, you may get a shorter presentation by calling the function <code class="func">SimplifyPresentation</code> (<a href="chap48.html#X78C3D23387DAC35A"><span class="RefLink">48.6-2</span></a>), now without this restriction, once more yourself.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">H := Group(</span>
<span class="GAPprompt">&gt;</span> <span class="GAPinput">[ (2,5,3), (2,7,5), (1,8,4), (1,8,6), (4,8,6), (3,5,7) ], () );;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">P := PresentationViaCosetTable( H );</span>
&lt;presentation with 6 gens and 12 rels of total length 42&gt;
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">SimplifyPresentation( P );</span>
#I  there are 4 generators and 10 relators of total length 36
</pre></div>

<p>If you apply the function <code class="func">FpGroupPresentation</code> (<a href="chap48.html#X7D6F40A87F24D3D6"><span class="RefLink">48.1-4</span></a>) to the resulting presentation you will get a finitely presented group isomorphic to <var class="Arg">G</var>. Note, however, that the function <code class="func">IsomorphismFpGroup</code> (<a href="chap47.html#X7F28268F850F454E"><span class="RefLink">47.11-1</span></a>) is recommended for this purpose.</p>

<p><a id="X7E1F2658827FC228" name="X7E1F2658827FC228"></a></p>

<h5>48.1-6 SimplifiedFpGroup</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; SimplifiedFpGroup</code>( <var class="Arg">G</var> )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
<p>applies Tietze transformations to a copy of the presentation of the given finitely presented group <var class="Arg">G</var> in order to reduce it with respect to the number of generators, the number of relators, and the relator lengths.</p>

<p><code class="func">SimplifiedFpGroup</code> returns a group isomorphic to the given one with a presentation which has been tried to simplify via Tietze transformations.</p>

<p>If the connection to the original group is important, then the operation <code class="func">IsomorphismSimplifiedFpGroup</code> (<a href="chap47.html#X78D87FA68233C401"><span class="RefLink">47.12-1</span></a>) should be used instead.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">F6 := FreeGroup( 6, "G" );;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">G := F6 / [ F6.1^2, F6.2^2, F6.4*F6.6^-1, F6.5^2, F6.6^2,</span>
<span class="GAPprompt">&gt;</span> <span class="GAPinput">F6.1*F6.2^-1*F6.3, F6.1*F6.5*F6.3^-1, F6.2*F6.4^-1*F6.3,</span>
<span class="GAPprompt">&gt;</span> <span class="GAPinput">F6.3*F6.4*F6.5^-1, F6.1*F6.6*F6.3^-2, F6.3^4 ];;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">H := SimplifiedFpGroup( G );</span>
&lt;fp group on the generators [ G1, G3 ]&gt;
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">RelatorsOfFpGroup( H );</span>
[ G1^2, (G1*G3^-1)^2, G3^4 ]
</pre></div>

<p>In fact, the command</p>


<div class="example"><pre>
H := SimplifiedFpGroup( G );
</pre></div>

<p>is an abbreviation of the command sequence</p>


<div class="example"><pre>
P := PresentationFpGroup( G, 0 );;
SimplifyPresentation( P );
H := FpGroupPresentation( P );
</pre></div>

<p>which applies a rather simple-minded strategy of Tietze transformations to the intermediate presentation <var class="Arg">P</var>. If, for some concrete group, the resulting presentation is unsatisfying, then you should try a more sophisticated, interactive use of the available Tietze transformation commands (see <a href="chap48.html#X829B634286471AB7"><span class="RefLink">48.6</span></a>).</p>

<p><a id="X8118FECE7AD1879B" name="X8118FECE7AD1879B"></a></p>

<h4>48.2 <span class="Heading">Subgroup Presentations</span></h4>

<p><a id="X7DB32FA97DAC5AC8" name="X7DB32FA97DAC5AC8"></a></p>

<h5>48.2-1 PresentationSubgroup</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; PresentationSubgroup</code>( <var class="Arg">G</var>, <var class="Arg">H</var>[, <var class="Arg">string</var>] )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
<p><code class="func">PresentationSubgroup</code> is a synonym for <code class="func">PresentationSubgroupRrs</code> (<a href="chap48.html#X857365CD87ADC29E"><span class="RefLink">48.2-2</span></a>).</p>

<p><a id="X857365CD87ADC29E" name="X857365CD87ADC29E"></a></p>

<h5>48.2-2 <span class="Heading">PresentationSubgroupRrs</span></h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; PresentationSubgroupRrs</code>( <var class="Arg">G</var>, <var class="Arg">H</var>[, <var class="Arg">string</var>] )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; PresentationSubgroupRrs</code>( <var class="Arg">G</var>, <var class="Arg">table</var>[, <var class="Arg">string</var>] )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
<p>uses the Reduced Reidemeister-Schreier method to compute a presentation <var class="Arg">P</var>, say, for a subgroup <var class="Arg">H</var> of a finitely presented group <var class="Arg">G</var>. The generators in the resulting presentation will be named <var class="Arg">string</var><code class="code">1</code>, <var class="Arg">string</var><code class="code">2</code>, <span class="SimpleMath">...</span>, the default string is <code class="code">"_x"</code>. You may access the <span class="SimpleMath">i</span>-th of these generators by <var class="Arg">P</var><code class="code">!.</code><span class="SimpleMath">i</span>.</p>

<p>Alternatively to the subgroup <var class="Arg">H</var>, its coset table <var class="Arg">table</var> in <var class="Arg">G</var> may be given as second argument.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">f := FreeGroup( "a", "b" );;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">g := f / [ f.1^2, f.2^3, (f.1*f.2)^5 ];</span>
&lt;fp group on the generators [ a, b ]&gt;
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">g1 := Size( g );</span>
60
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">u := Subgroup( g, [ g.1, g.1^g.2 ] );</span>
Group([ a, b^-1*a*b ])
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">p := PresentationSubgroup( g, u, "g" );</span>
&lt;presentation with 3 gens and 4 rels of total length 12&gt;
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">gens := GeneratorsOfPresentation( p );</span>
[ g1, g2, g3 ]
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">TzPrintRelators( p );</span>
#I  1. g1^2
#I  2. g2^2
#I  3. g3*g2*g1
#I  4. g3^5
</pre></div>

<p>Note that you cannot call the generators by their names. These names are not variables, but just display figures. So, if you want to access the generators by their names, you first will have to introduce the respective variables and to assign the generators to them.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">gens[1] = g1;</span>
false
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">g1;</span>
60
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">g1 := gens[1];; g2 := gens[2];; g3 := gens[3];;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">g1;</span>
g1
</pre></div>

<p>The Reduced Reidemeister-Schreier algorithm is a modification of the Reidemeister-Schreier algorithm of George Havas <a href="chapBib.html#biBHav74b">[Hav74]</a>. It was proposed by Joachim Neubüser and first implemented in 1986 by Andrea Lucchini and Volkmar Felsch in the SPAS system <a href="chapBib.html#biBSpa89">[SPA89]</a>. Like the Reidemeister-Schreier algorithm of George Havas, it needs only the presentation of <var class="Arg">G</var> and a coset table of <var class="Arg">H</var> in <var class="Arg">G</var> to construct a presentation of <var class="Arg">H</var>.</p>

<p>Whenever you call the command <code class="func">PresentationSubgroupRrs</code>, it first obtains a coset table of <var class="Arg">H</var> in <var class="Arg">G</var> if not given. Next, a set of generators of <var class="Arg">H</var> is determined by reconstructing the coset table and introducing in that process as many Schreier generators of <var class="Arg">H</var> in <var class="Arg">G</var> as are needed to do a Felsch strategy coset enumeration without any coincidences. (In general, though containing redundant generators, this set will be much smaller than the set of all Schreier generators. That is why we call the method the <em>Reduced</em> Reidemeister-Schreier.)</p>

<p>After having constructed this set of <em>primary subgroup generators</em>, say, the coset table is extended to an <em>augmented coset table</em> which describes the action of the group generators on coset representatives, i.e., on elements instead of cosets. For this purpose, suitable words in the (primary) subgroup generators have to be associated to the coset table entries. In order to keep the lengths of these words short, additional <em>secondary subgroup generators</em> are introduced as abbreviations of subwords. Their number may be large.</p>

<p>Finally, a Reidemeister rewriting process is used to get defining relators for <var class="Arg">H</var> from the relators of <var class="Arg">G</var>. As the resulting presentation of <var class="Arg">H</var> is a presentation on primary <em>and</em> secondary generators, in general you will have to simplify it by appropriate Tietze transformations (see <a href="chap48.html#X829B634286471AB7"><span class="RefLink">48.6</span></a>) or by the command <code class="func">DecodeTree</code> (<a href="chap48.html#X7ACBFE2F78D72A31"><span class="RefLink">48.10-1</span></a>) before you can use it. Therefore it is returned in the form of a presentation, <var class="Arg">P</var> say.</p>

<p>Compared with the Modified Todd-Coxeter method described below, the Reduced Reidemeister-Schreier method (as well as Havas' original Reidemeister-Schreier program) has the advantage that it does not require generators of <var class="Arg">H</var> to be given if a coset table of <var class="Arg">H</var> in <var class="Arg">G</var> is known. This provides a possibility to compute a presentation of the normal closure of a given subgroup (see <code class="func">PresentationNormalClosureRrs</code> (<a href="chap48.html#X7D6A52837BEE5C3D"><span class="RefLink">48.2-5</span></a>)).</p>

<p>For certain applications you may be interested in getting not only just a presentation for <var class="Arg">H</var>, but also a relation between the involved generators of <var class="Arg">H</var> and the generators of <var class="Arg">G</var>. The subgroup generators in the presentation are sorted such that the primary generators precede the secondary ones. Moreover, for each secondary subgroup generator there is a relator in the presentation which expresses this generator as a word in preceding ones. Hence, all we need in addition is a list of words in the generators of <var class="Arg">G</var> which express the primary subgroup generators. In fact, such a list is provided in the attribute <code class="func">PrimaryGeneratorWords</code> (<a href="chap48.html#X7FCE7ED581CF7897"><span class="RefLink">48.2-3</span></a>) of the resulting presentation.</p>

<p><a id="X7FCE7ED581CF7897" name="X7FCE7ED581CF7897"></a></p>

<h5>48.2-3 PrimaryGeneratorWords</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; PrimaryGeneratorWords</code>( <var class="Arg">P</var> )</td><td class="tdright">(&nbsp;attribute&nbsp;)</td></tr></table></div>
<p>is an attribute of the presentation <var class="Arg">P</var> which holds a list of words in the associated group generators (of the underlying free group) which express the primary subgroup generators of <var class="Arg">P</var>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">PrimaryGeneratorWords( p );</span>
[ a, b^-1*a*b ]
</pre></div>

<p><a id="X80BA10F780EAE68E" name="X80BA10F780EAE68E"></a></p>

<h5>48.2-4 PresentationSubgroupMtc</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; PresentationSubgroupMtc</code>( <var class="Arg">G</var>, <var class="Arg">H</var>[, <var class="Arg">string</var>][, <var class="Arg">print</var>, <var class="Arg">level</var>] )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
<p>uses the Modified Todd-Coxeter coset representative enumeration method to compute a presentation <span class="SimpleMath">P</span>, say, for a subgroup <var class="Arg">H</var> of a finitely presented group <var class="Arg">G</var>. The presentation returned is in generators corresponding to the generators of <var class="Arg">H</var>. The generators in the resulting presentation will be named <var class="Arg">string</var><code class="code">1</code>, <var class="Arg">string</var><code class="code">2</code>, <span class="SimpleMath">...</span>, the default string is <code class="code">"_x"</code>. You may access the <span class="SimpleMath">i</span>-th of these generators by <span class="SimpleMath">P</span><code class="code">!.</code><span class="SimpleMath">i</span>.</p>

<p>The default print level is <span class="SimpleMath">1</span>. If the print level is set to <span class="SimpleMath">0</span>, then the printout of the implicitly called function <code class="func">DecodeTree</code> (<a href="chap48.html#X7ACBFE2F78D72A31"><span class="RefLink">48.10-1</span></a>) will be suppressed.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">p := PresentationSubgroupMtc( g, u );</span>
#I  there are 3 generators and 4 relators of total length 12
#I  there are 2 generators and 3 relators of total length 14
&lt;presentation with 2 gens and 3 rels of total length 14&gt;
</pre></div>

<p>The so called Modified Todd-Coxeter method was proposed, in slightly different forms, by Nathan S. Mendelsohn and William O. J. Moser in 1966. Moser's method was proved in <a href="chapBib.html#biBBC76">[BC76]</a>. It has been generalized to cover a broad spectrum of different versions (see the survey <a href="chapBib.html#biBNeu82">[Neu82]</a>).</p>

<p>The <em>Modified Todd-Coxeter</em> method performs an enumeration of coset representatives. It proceeds like an ordinary coset enumeration (see <a href="chap47.html#X7BD0CEBA7B225416"><span class="RefLink">47.6</span></a>), but as the product of a coset representative by a group generator or its inverse need not be a coset representative itself, the Modified Todd-Coxeter has to store a kind of correction element for each coset table entry. Hence it builds up a so called <em>augmented coset table</em> of <var class="Arg">H</var> in <var class="Arg">G</var> consisting of the ordinary coset table and a second table in parallel which contains the associated subgroup elements.</p>

<p>Theoretically, these subgroup elements could be expressed as words in the given generators of <var class="Arg">H</var>, but in general these words tend to become unmanageable because of their enormous lengths. Therefore, a highly redundant list of subgroup generators is built up starting from the given ("primary") generators of <var class="Arg">H</var> and adding additional ("secondary") generators which are defined as abbreviations of suitable words of length two in the preceding generators such that each of the subgroup elements in the augmented coset table can be expressed as a word of length at most one in the resulting (primary <em>and</em> secondary) subgroup generators.</p>

<p>Then a rewriting process (which is essentially a kind of Reidemeister rewriting process) is used to get relators for <var class="Arg">H</var> from the defining relators of <var class="Arg">G</var>.</p>

<p>The resulting presentation involves all the primary, but not all the secondary generators of <var class="Arg">H</var>. In fact, it contains only those secondary generators which explicitly occur in the augmented coset table. If we extended this presentation by those secondary generators which are not yet contained in it as additional generators, and by the definitions of all secondary generators as additional relators, we would get a presentation of <var class="Arg">H</var>, but, in general, we would end up with a large number of generators and relators.</p>

<p>On the other hand, if we avoid this extension, the current presentation will not necessarily define <var class="Arg">H</var> although we have used the same rewriting process which in the case of the <code class="func">PresentationSubgroupRrs</code> (<a href="chap48.html#X857365CD87ADC29E"><span class="RefLink">48.2-2</span></a>) command computes a defining set of relators for <var class="Arg">H</var> from an augmented coset table and defining relators of <var class="Arg">G</var>. The different behaviour here is caused by the fact that coincidences may have occurred in the Modified Todd-Coxeter coset enumeration.</p>

<p>To overcome this problem without extending the presentation by all secondary generators, the <code class="func">PresentationSubgroupMtc</code> command applies the so called <em>decoding tree</em> algorithm which provides a more economical approach. The reader is strongly recommended to carefully read section <a href="chap48.html#X7D9E283D81CCCF1A"><span class="RefLink">48.10</span></a> where this algorithm is described in more detail. Here we will only mention that this procedure may add a lot of intermediate generators and relators (and even change the isomorphism type) in a process which in fact eliminates all secondary generators from the presentation and hence finally provides a presentation of <var class="Arg">H</var> on the primary, i.e., the originally given, generators of <var class="Arg">H</var>. This is a remarkable advantage of the command <code class="func">PresentationSubgroupMtc</code> compared to the command <code class="func">PresentationSubgroupRrs</code> (<a href="chap48.html#X857365CD87ADC29E"><span class="RefLink">48.2-2</span></a>). But note that, for some particular subgroup <var class="Arg">H</var>, the Reduced Reidemeister-Schreier method might quite well produce a more concise presentation.</p>

<p>The resulting presentation is returned in the form of a presentation, <span class="SimpleMath">P</span> say.</p>

<p>As the function <code class="func">PresentationSubgroupRrs</code> (<a href="chap48.html#X857365CD87ADC29E"><span class="RefLink">48.2-2</span></a>) described above (see there for details), the function <code class="func">PresentationSubgroupMtc</code> returns a list of the primary subgroup generators of <var class="Arg">H</var> in the attribute <code class="func">PrimaryGeneratorWords</code> (<a href="chap48.html#X7FCE7ED581CF7897"><span class="RefLink">48.2-3</span></a>) of <span class="SimpleMath">P</span>. In fact, this list is not very exciting here because it is just a shallow copy of the value of <code class="func">GeneratorsOfPresentation</code> (<a href="chap48.html#X849429BC7D435F77"><span class="RefLink">48.1-3</span></a>) of <var class="Arg">H</var>, however it is needed to guarantee a certain consistency between the results of the different functions for computing subgroup presentations.</p>

<p>Though the decoding tree routine already involves a lot of Tietze transformations, we recommend that you try to further simplify the resulting presentation by appropriate Tietze transformations (see <a href="chap48.html#X829B634286471AB7"><span class="RefLink">48.6</span></a>).</p>

<p><a id="X7D6A52837BEE5C3D" name="X7D6A52837BEE5C3D"></a></p>

<h5>48.2-5 PresentationNormalClosureRrs</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; PresentationNormalClosureRrs</code>( <var class="Arg">G</var>, <var class="Arg">H</var>[, <var class="Arg">string</var>] )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
<p>uses the Reduced Reidemeister-Schreier method to compute a presentation <span class="SimpleMath">P</span>, say, for the normal closure of a subgroup <var class="Arg">H</var> of a finitely presented group <var class="Arg">G</var>. The generators in the resulting presentation will be named <var class="Arg">string</var><code class="code">1</code>, <var class="Arg">string</var><code class="code">2</code>, <span class="SimpleMath">...</span>, the default string is <code class="code">"_x"</code>. You may access the <span class="SimpleMath">i</span>-th of these generators by <span class="SimpleMath">P</span><code class="code">!.</code><span class="SimpleMath">i</span>.</p>

<p><a id="X7A7E5D0084DB0B4F" name="X7A7E5D0084DB0B4F"></a></p>

<h5>48.2-6 PresentationNormalClosure</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; PresentationNormalClosure</code>( <var class="Arg">G</var>, <var class="Arg">H</var>[, <var class="Arg">string</var>] )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
<p><code class="func">PresentationNormalClosure</code> is a synonym for <code class="func">PresentationNormalClosureRrs</code> (<a href="chap48.html#X7D6A52837BEE5C3D"><span class="RefLink">48.2-5</span></a>).</p>

<p><a id="X7BC960AB7E8DE419" name="X7BC960AB7E8DE419"></a></p>

<h4>48.3 <span class="Heading">Relators in a Presentation</span></h4>

<p>In order to speed up the Tietze transformation routines, each relator in a presentation is internally represented by a list of positive or negative generator numbers, i.e., each factor of the proper <strong class="pkg">GAP</strong> word is represented by the position number of the corresponding generator with respect to the current list of generators, or by the respective negative number, if the factor is the inverse of a generator. Note that the numbering of the generators in Tietze words is always relative to a generator list and bears no relation to the internal numbering of generators in a family of associative words.</p>

<p><a id="X8365BAFA785FCD8D" name="X8365BAFA785FCD8D"></a></p>

<h5>48.3-1 TietzeWordAbstractWord</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; TietzeWordAbstractWord</code>( <var class="Arg">word</var>, <var class="Arg">fgens</var> )</td><td class="tdright">(&nbsp;operation&nbsp;)</td></tr></table></div>
<p>assumes <var class="Arg">fgens</var> to be a list of free group generators and <var class="Arg">word</var> to be an abstract word in these generators. It converts <var class="Arg">word</var> into a Tietze word, i. e., a list of positive or negative generator numbers.</p>

<p>This function simply calls <code class="func">LetterRepAssocWord</code> (<a href="chap37.html#X7BD7647C7B088389"><span class="RefLink">37.6-8</span></a>).</p>

<p><a id="X8573E91C838B1D13" name="X8573E91C838B1D13"></a></p>

<h5>48.3-2 AbstractWordTietzeWord</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; AbstractWordTietzeWord</code>( <var class="Arg">word</var>, <var class="Arg">fgens</var> )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
<p>assumes <var class="Arg">fgens</var> to be a list of free group generators and <var class="Arg">word</var> to be a Tietze word in these generators, i. e., a list of positive or negative generator numbers. It converts <var class="Arg">word</var> to an abstract word.</p>

<p>This function simply calls <code class="func">AssocWordByLetterRep</code> (<a href="chap37.html#X7AC8EC757CFB9A51"><span class="RefLink">37.6-9</span></a>).</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">F := FreeGroup( "a", "b", "c" ,"d");</span>
&lt;free group on the generators [ a, b, c, d ]&gt;
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">tzword := TietzeWordAbstractWord(</span>
<span class="GAPprompt">&gt;</span> <span class="GAPinput">Comm(F.4,F.2) * (F.3^2 * F.2)^-1, GeneratorsOfGroup( F ){[2,3,4]} );</span>
[ -3, -1, 3, -2, -2 ]
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">AbstractWordTietzeWord( tzword, GeneratorsOfGroup( F ){[2,3,4]} );</span>
d^-1*b^-1*d*c^-2
</pre></div>

<p><a id="X867F64FA840B3F81" name="X867F64FA840B3F81"></a></p>

<h4>48.4 <span class="Heading">Printing Presentations</span></h4>

<p>Whenever you create a presentation <span class="SimpleMath">P</span>, say, or assign it to a variable, <strong class="pkg">GAP</strong> will respond by printing <span class="SimpleMath">P</span>. However, as <span class="SimpleMath">P</span> may contain a lot of generators and many relators of large length, it would be annoying if the standard print facilities displayed all this information in detail. So they restrict the printout to just one line of text containing the number of generators, the number of relators, and the total length of all relators of <span class="SimpleMath">P</span>. As compensation, <strong class="pkg">GAP</strong> offers some special print commands which display various details of a presentation. Note that there is also a function <code class="func">TzPrintOptions</code> (<a href="chap48.html#X7BC90B6882DE6D10"><span class="RefLink">48.11-2</span></a>). It is described in Section <a href="chap48.html#X856F37537E9927EE"><span class="RefLink">48.11</span></a>.</p>

<p><a id="X847EA6737C21171C" name="X847EA6737C21171C"></a></p>

<h5>48.4-1 TzPrintGenerators</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; TzPrintGenerators</code>( <var class="Arg">P</var>[, <var class="Arg">list</var>] )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
<p>prints the generators of the given Tietze presentation <var class="Arg">P</var> together with the number of their occurrences in the relators. The optional second argument can be used to specify the numbers of the generators to be printed. Default: all generators are printed.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">G := Group( [ (1,2,3,4,5), (2,3,5,4), (1,6)(3,4) ], () );</span>
Group([ (1,2,3,4,5), (2,3,5,4), (1,6)(3,4) ])
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">P := PresentationViaCosetTable( G );</span>
&lt;presentation with 3 gens and 6 rels of total length 28&gt;
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">TzPrintGenerators( P );</span>
#I  1.  f1   11 occurrences
#I  2.  f2   10 occurrences
#I  3.  f3   7 occurrences   involution
</pre></div>

<p><a id="X821B63DD82894443" name="X821B63DD82894443"></a></p>

<h5>48.4-2 TzPrintRelators</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; TzPrintRelators</code>( <var class="Arg">P</var>[, <var class="Arg">list</var>] )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
<p>prints the relators of the given Tietze presentation <var class="Arg">P</var>. The optional second argument <var class="Arg">list</var> can be used to specify the numbers of the relators to be printed. Default: all relators are printed.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">TzPrintRelators( P );</span>
#I  1. f3^2
#I  2. f2^4
#I  3. (f2^-1*f3)^2
#I  4. f1^5
#I  5. f1^2*f2*f1*f2^-1
#I  6. f1^-1*f3*f1*f3*f1^-1*f2^2*f3
</pre></div>

<p><a id="X852C52C37FAAB7DD" name="X852C52C37FAAB7DD"></a></p>

<h5>48.4-3 TzPrintLengths</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; TzPrintLengths</code>( <var class="Arg">P</var> )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
<p>prints just a list of all relator lengths of the given presentation <var class="Arg">P</var>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">TzPrintLengths( P );</span>
[ 2, 4, 4, 5, 5, 8 ]
</pre></div>

<p><a id="X7D7B3F46865443E4" name="X7D7B3F46865443E4"></a></p>

<h5>48.4-4 TzPrintStatus</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; TzPrintStatus</code>( <var class="Arg">P</var>[, <var class="Arg">norepeat</var>] )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
<p>is an internal function which is used by the Tietze transformation routines to print the number of generators, the number of relators, and the total length of all relators in the given Tietze presentation <var class="Arg">P</var>. If <var class="Arg">norepeat</var> is specified as <code class="keyw">true</code>, the printing is suppressed if none of the three values has changed since the last call.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">TzPrintStatus( P );</span>
#I  there are 3 generators and 6 relators of total length 28
</pre></div>

<p><a id="X85F8DAE27F06C32B" name="X85F8DAE27F06C32B"></a></p>

<h5>48.4-5 TzPrintPresentation</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; TzPrintPresentation</code>( <var class="Arg">P</var> )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
<p>prints the generators and the relators of a Tietze presentation. In fact, it is an abbreviation for the successive call of the three commands <code class="func">TzPrintGenerators</code> (<a href="chap48.html#X847EA6737C21171C"><span class="RefLink">48.4-1</span></a>), <code class="func">TzPrintRelators</code> (<a href="chap48.html#X821B63DD82894443"><span class="RefLink">48.4-2</span></a>), and <code class="func">TzPrintStatus</code> (<a href="chap48.html#X7D7B3F46865443E4"><span class="RefLink">48.4-4</span></a>), each with the presentation <var class="Arg">P</var> as only argument.</p>

<p><a id="X7CA8BA51802655FC" name="X7CA8BA51802655FC"></a></p>

<h5>48.4-6 TzPrint</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; TzPrint</code>( <var class="Arg">P</var>[, <var class="Arg">list</var>] )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
<p>prints the current generators of the given presentation <var class="Arg">P</var>, and prints the relators of <var class="Arg">P</var> as Tietze words (without converting them back to abstract words as the functions <code class="func">TzPrintRelators</code> (<a href="chap48.html#X821B63DD82894443"><span class="RefLink">48.4-2</span></a>) and <code class="func">TzPrintPresentation</code> (<a href="chap48.html#X85F8DAE27F06C32B"><span class="RefLink">48.4-5</span></a>) do). The optional second argument can be used to specify the numbers of the relators to be printed. Default: all relators are printed.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">TzPrint( P );</span>
#I  generators: [ f1, f2, f3 ]
#I  relators:
#I  1.  2  [ 3, 3 ]
#I  2.  4  [ 2, 2, 2, 2 ]
#I  3.  4  [ -2, 3, -2, 3 ]
#I  4.  5  [ 1, 1, 1, 1, 1 ]
#I  5.  5  [ 1, 1, 2, 1, -2 ]
#I  6.  8  [ -1, 3, 1, 3, -1, 2, 2, 3 ]
</pre></div>

<p><a id="X82F6B0EE7C7C7901" name="X82F6B0EE7C7C7901"></a></p>

<h5>48.4-7 TzPrintPairs</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; TzPrintPairs</code>( <var class="Arg">P</var>[, <var class="Arg">n</var>] )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
<p>prints the <var class="Arg">n</var> most often occurring relator subwords of the form <span class="SimpleMath">a b</span>, where <span class="SimpleMath">a</span> and <span class="SimpleMath">b</span> are different generators or inverses of generators, together with the number of their occurrences. The default value of <var class="Arg">n</var> is 10. A value <var class="Arg">n</var> = 0 is interpreted as <code class="func">infinity</code> (<a href="chap18.html#X8511B8DF83324C27"><span class="RefLink">18.2-1</span></a>).</p>

<p>The function <code class="func">TzPrintPairs</code> is useful in the context of Tietze transformations which introduce new generators by substituting words in the current generators (see <a href="chap48.html#X7D2FACCF79F57040"><span class="RefLink">48.8</span></a>). It gives some evidence for an appropriate choice of a word of length 2 to be substituted.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">TzPrintPairs( P, 3 );</span>
#I  1.  3  occurrences of  f2 * f3
#I  2.  2  occurrences of  f2^-1 * f3
#I  3.  2  occurrences of  f1 * f3
</pre></div>

<p><a id="X82455E5885D73FFF" name="X82455E5885D73FFF"></a></p>

<h4>48.5 <span class="Heading">Changing Presentations</span></h4>

<p>The functions described in this section may be used to change a presentation. Note, however, that in general they do not perform Tietze transformations because they change or may change the isomorphism type of the group defined by the presentation.</p>

<p><a id="X7F632A6D8685855D" name="X7F632A6D8685855D"></a></p>

<h5>48.5-1 AddGenerator</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; AddGenerator</code>( <var class="Arg">P</var> )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
<p>extends the presentation <var class="Arg">P</var> by a new generator.</p>

<p>Let <span class="SimpleMath">i</span> be the smallest positive integer which has not yet been used as a generator number in the given presentation. <code class="func">AddGenerator</code> defines a new abstract generator <span class="SimpleMath">x_i</span> with the name <code class="code">"_x</code><span class="SimpleMath">i</span><code class="code">"</code> and adds it to the list of generators of <var class="Arg">P</var>.</p>

<p>You may access the generator <span class="SimpleMath">x_i</span> by typing <var class="Arg">P</var><code class="code">!.</code><span class="SimpleMath">i</span>. However, this is only practicable if you are running an interactive job because you have to know the value of <span class="SimpleMath">i</span>. Hence the proper way to access the new generator is to write <code class="code">GeneratorsOfPresentation(P)[Length(GeneratorsOfPresentation(P))]</code>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">G := PerfectGroup( 120 );;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">H := Subgroup( G, [ G.1^G.2, G.3 ] );;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">P := PresentationSubgroup( G, H );</span>
&lt;presentation with 4 gens and 7 rels of total length 21&gt;
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">AddGenerator( P );</span>
#I  now the presentation has 5 generators, the new generator is _x7
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">gens := GeneratorsOfPresentation( P );</span>
[ _x1, _x2, _x4, _x5, _x7 ]
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">gen := gens[Length( gens )];</span>
_x7
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">gen = P!.7;</span>
true
</pre></div>

<p><a id="X83A5667086FD538A" name="X83A5667086FD538A"></a></p>

<h5>48.5-2 TzNewGenerator</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; TzNewGenerator</code>( <var class="Arg">P</var> )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
<p>is an internal function which defines a new abstract generator and adds it to the presentation <var class="Arg">P</var>. It is called by <code class="func">AddGenerator</code> (<a href="chap48.html#X7F632A6D8685855D"><span class="RefLink">48.5-1</span></a>) and by several Tietze transformation commands. As it does not know which global lists have to be kept consistent, you should not call it. Instead, you should call the function <code class="func">AddGenerator</code> (<a href="chap48.html#X7F632A6D8685855D"><span class="RefLink">48.5-1</span></a>), if needed.</p>

<p><a id="X78D1BCE67FA852D8" name="X78D1BCE67FA852D8"></a></p>

<h5>48.5-3 AddRelator</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; AddRelator</code>( <var class="Arg">P</var>, <var class="Arg">word</var> )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
<p>adds the relator <var class="Arg">word</var> to the presentation <var class="Arg">P</var>, probably changing the group defined by <var class="Arg">P</var>. <var class="Arg">word</var> must be an abstract word in the generators of <var class="Arg">P</var>.</p>

<p><a id="X7B11E89E78A22EBF" name="X7B11E89E78A22EBF"></a></p>

<h5>48.5-4 RemoveRelator</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; RemoveRelator</code>( <var class="Arg">P</var>, <var class="Arg">n</var> )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
<p>removes the <var class="Arg">n</var>-th relator from the presentation <var class="Arg">P</var>, probably changing the group defined by <var class="Arg">P</var>.</p>

<p><a id="X829B634286471AB7" name="X829B634286471AB7"></a></p>

<h4>48.6 <span class="Heading">Tietze Transformations</span></h4>

<p>The commands in this section can be used to modify a presentation by Tietze transformations.</p>

<p>In general, the aim of such modifications will be to <em>simplify</em> the given presentation, i.e., to reduce the number of generators and the number of relators without increasing too much the sum of all relator lengths which we will call the <em>total length</em> of the presentation. Depending on the concrete presentation under investigation one may end up with a nice, short presentation or with a very huge one.</p>

<p>Unfortunately there is no algorithm which could be applied to find the shortest presentation which can be obtained by Tietze transformations from a given one. Therefore, what <strong class="pkg">GAP</strong> offers are some lower-level Tietze transformation commands and, in addition, some higher-level commands which apply the lower-level ones in a kind of default strategy which of course cannot be the optimal choice for all presentations.</p>

<p>The design of these commands follows closely the concept of the ANU Tietze transformation program <a href="chapBib.html#biBHav69">[Hav69]</a> and its later revisions (see <a href="chapBib.html#biBHKRR84">[HKRR84]</a>, <a href="chapBib.html#biBRob88">[Rob88]</a>).</p>

<p><a id="X7C4A30328224C466" name="X7C4A30328224C466"></a></p>

<h5>48.6-1 TzGo</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; TzGo</code>( <var class="Arg">P</var>[, <var class="Arg">silent</var>] )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
<p>automatically performs suitable Tietze transformations of the given presentation <var class="Arg">P</var>. It is perhaps the most convenient one among the interactive Tietze transformation commands. It offers a kind of default strategy which, in general, saves you from explicitly calling the lower-level commands it involves.</p>

<p>If <var class="Arg">silent</var> is specified as <code class="keyw">true</code>, the printing of the status line by <code class="func">TzGo</code> is suppressed if the Tietze option <code class="code">printLevel</code> (see <a href="chap48.html#X856F37537E9927EE"><span class="RefLink">48.11</span></a>) has a value less than <span class="SimpleMath">2</span>.</p>

<p><a id="X78C3D23387DAC35A" name="X78C3D23387DAC35A"></a></p>

<h5>48.6-2 SimplifyPresentation</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; SimplifyPresentation</code>( <var class="Arg">P</var> )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
<p><code class="func">SimplifyPresentation</code> is a synonym for <code class="func">TzGo</code> (<a href="chap48.html#X7C4A30328224C466"><span class="RefLink">48.6-1</span></a>).</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">F2 := FreeGroup( "a", "b" );;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">G := F2 / [ F2.1^9, F2.2^2, (F2.1*F2.2)^4, (F2.1^2*F2.2)^3 ];;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">a := G.1;; b := G.2;;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">H := Subgroup( G, [ (a*b)^2, (a^-1*b)^2 ] );;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">Index( G, H );</span>
408
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">P := PresentationSubgroup( G, H );</span>
&lt;presentation with 8 gens and 36 rels of total length 111&gt;
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">PrimaryGeneratorWords( P );</span>
[ b, a*b*a ]
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">TzOptions( P ).protected := 2;</span>
2
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">TzOptions( P ).printLevel := 2;</span>
2
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">SimplifyPresentation( P );</span>
#I  eliminating _x7 = _x5^-1
#I  eliminating _x5 = _x4
#I  eliminating _x18 = _x3
#I  eliminating _x8 = _x3
#I  there are 4 generators and 8 relators of total length 21
#I  there are 4 generators and 7 relators of total length 18
#I  eliminating _x4 = _x3^-1*_x2^-1
#I  eliminating _x3 = _x2*_x1^-1
#I  there are 2 generators and 4 relators of total length 14
#I  there are 2 generators and 4 relators of total length 13
#I  there are 2 generators and 3 relators of total length 9
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">TzPrintRelators( P );</span>
#I  1. _x1^2
#I  2. _x2^3
#I  3. (_x2*_x1)^2
</pre></div>

<p>Roughly speaking, <code class="func">TzGo</code> (<a href="chap48.html#X7C4A30328224C466"><span class="RefLink">48.6-1</span></a>) consists of a loop over a procedure which involves two phases: In the <em>search phase</em> it calls <code class="func">TzSearch</code> (<a href="chap48.html#X7DF4BBDF839643DD"><span class="RefLink">48.7-2</span></a>) and <code class="func">TzSearchEqual</code> (<a href="chap48.html#X87F7A87A7ACF2445"><span class="RefLink">48.7-3</span></a>) described below which try to reduce the relator lengths by substituting common subwords of relators, in the <em>elimination phase</em> it calls the command <code class="func">TzEliminate</code> (<a href="chap48.html#X85989AF886EC2BF6"><span class="RefLink">48.7-1</span></a>) described below (or, more precisely, a subroutine of <code class="func">TzEliminate</code> (<a href="chap48.html#X85989AF886EC2BF6"><span class="RefLink">48.7-1</span></a>) in order to save some administrative overhead) which tries to eliminate generators that can be expressed as words in the remaining generators.</p>

<p>If <code class="func">TzGo</code> (<a href="chap48.html#X7C4A30328224C466"><span class="RefLink">48.6-1</span></a>) succeeds in reducing the number of generators, the number of relators, or the total length of all relators, it displays the new status before returning (provided that you did not set the print level to zero). However, it does not provide any output if all these three values have remained unchanged, even if the command <code class="func">TzSearchEqual</code> (<a href="chap48.html#X87F7A87A7ACF2445"><span class="RefLink">48.7-3</span></a>) involved has changed the presentation such that another call of <code class="func">TzGo</code> (<a href="chap48.html#X7C4A30328224C466"><span class="RefLink">48.6-1</span></a>) might provide further progress. Hence, in such a case it makes sense to repeat the call of the command for several times (or to call the command <code class="func">TzGoGo</code> (<a href="chap48.html#X801D3D8984E1CA55"><span class="RefLink">48.6-3</span></a>) instead).</p>

<p><a id="X801D3D8984E1CA55" name="X801D3D8984E1CA55"></a></p>

<h5>48.6-3 TzGoGo</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; TzGoGo</code>( <var class="Arg">P</var> )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
<p>calls the command <code class="func">TzGo</code> (<a href="chap48.html#X7C4A30328224C466"><span class="RefLink">48.6-1</span></a>) again and again until it does not reduce the presentation any more.</p>

<p>The result of the Tietze transformations can be affected substantially by the options parameters (see <a href="chap48.html#X856F37537E9927EE"><span class="RefLink">48.11</span></a>). To demonstrate the effect of the <code class="code">eliminationsLimit</code> parameter, we will give an example in which we handle a subgroup of index 240 in a group of order 40320 given by a presentation due to B. H. Neumann. First we construct a presentation of the subgroup, and then we apply to it the command <code class="func">TzGoGo</code> for different values of the parameter <code class="code">eliminationsLimit</code> (including the default value 100). In fact, we also alter the <code class="code">printLevel</code> parameter, but this is only done in order to suppress most of the output. In all cases the resulting presentations cannot be improved any more by applying the command <code class="func">TzGoGo</code> again, i.e., they are the best results which we can get without substituting new generators.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">F3 := FreeGroup( "a", "b", "c" );;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">G := F3 / [ F3.1^3, F3.2^3, F3.3^3, (F3.1*F3.2)^5,</span>
<span class="GAPprompt">&gt;</span> <span class="GAPinput">(F3.1^-1*F3.2)^5, (F3.1*F3.3)^4, (F3.1*F3.3^-1)^4,</span>
<span class="GAPprompt">&gt;</span> <span class="GAPinput">F3.1*F3.2^-1*F3.1*F3.2*F3.3^-1*F3.1*F3.3*F3.1*F3.3^-1,</span>
<span class="GAPprompt">&gt;</span> <span class="GAPinput">(F3.2*F3.3)^3, (F3.2^-1*F3.3)^4 ];;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">a := G.1;; b := G.2;; c := G.3;;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">H := Subgroup( G, [ a, c ] );;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">for i in [ 61, 62, 63, 90, 97 ] do</span>
<span class="GAPprompt">&gt;</span> <span class="GAPinput">Pi := PresentationSubgroup( G, H );</span>
<span class="GAPprompt">&gt;</span> <span class="GAPinput">TzOptions( Pi ).eliminationsLimit := i;</span>
<span class="GAPprompt">&gt;</span> <span class="GAPinput">Print("#I eliminationsLimit set to ",i,"\n");</span>
<span class="GAPprompt">&gt;</span> <span class="GAPinput">TzOptions( Pi ).printLevel := 0;</span>
<span class="GAPprompt">&gt;</span> <span class="GAPinput">TzGoGo( Pi );</span>
<span class="GAPprompt">&gt;</span> <span class="GAPinput">TzPrintStatus( Pi );</span>
<span class="GAPprompt">&gt;</span> <span class="GAPinput">od;</span>
#I eliminationsLimit set to 61
#I  there are 2 generators and 104 relators of total length 7012
#I eliminationsLimit set to 62
#I  there are 2 generators and 7 relators of total length 56
#I eliminationsLimit set to 63
#I  there are 3 generators and 97 relators of total length 5998
#I eliminationsLimit set to 90
#I  there are 3 generators and 11 relators of total length 68
#I eliminationsLimit set to 97
#I  there are 4 generators and 109 relators of total length 3813
</pre></div>

<p>Similarly, we demonstrate the influence of the <code class="code">saveLimit</code> parameter by just continuing the preceding example for some different values of the <code class="code">saveLimit</code> parameter (including its default value 10), but without changing the <code class="code">eliminationsLimit</code> parameter which keeps its default value 100.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">for i in [ 7 .. 11 ] do</span>
<span class="GAPprompt">&gt;</span> <span class="GAPinput">Pi := PresentationSubgroup( G, H );</span>
<span class="GAPprompt">&gt;</span> <span class="GAPinput">TzOptions( Pi ).saveLimit := i;</span>
<span class="GAPprompt">&gt;</span> <span class="GAPinput">Print( "#I saveLimit set to ", i, "\n" );</span>
<span class="GAPprompt">&gt;</span> <span class="GAPinput">TzOptions( Pi ).printLevel := 0;</span>
<span class="GAPprompt">&gt;</span> <span class="GAPinput">TzGoGo( Pi );</span>
<span class="GAPprompt">&gt;</span> <span class="GAPinput">TzPrintStatus( Pi );</span>
<span class="GAPprompt">&gt;</span> <span class="GAPinput">od;</span>
#I saveLimit set to 7
#I  there are 3 generators and 99 relators of total length 2713
#I saveLimit set to 8
#I  there are 2 generators and 103 relators of total length 11982
#I saveLimit set to 9
#I  there are 2 generators and 6 relators of total length 41
#I saveLimit set to 10
#I  there are 3 generators and 118 relators of total length 13713
#I saveLimit set to 11
#I  there are 3 generators and 11 relators of total length 58
</pre></div>

<p><a id="X7D19E30080290FC7" name="X7D19E30080290FC7"></a></p>

<h4>48.7 <span class="Heading">Elementary Tietze Transformations</span></h4>

<p><a id="X85989AF886EC2BF6" name="X85989AF886EC2BF6"></a></p>

<h5>48.7-1 <span class="Heading">TzEliminate</span></h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; TzEliminate</code>( <var class="Arg">P</var>[, <var class="Arg">gen</var>] )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; TzEliminate</code>( <var class="Arg">P</var>[, <var class="Arg">n</var>] )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
<p>tries to eliminate a generator from a presentation <var class="Arg">P</var> via Tietze transformations.</p>

<p>Any relator which contains some generator just once can be used to substitute that generator by a word in the remaining generators. If such generators and relators exist, then <code class="func">TzEliminate</code> chooses a generator for which the product of its number of occurrences and the length of the substituting word is minimal, and then it eliminates this generator from the presentation, provided that the resulting total length of the relators does not exceed the associated Tietze option parameter <code class="code">spaceLimit</code> (see <a href="chap48.html#X856F37537E9927EE"><span class="RefLink">48.11</span></a>). The default value of that parameter is <code class="func">infinity</code> (<a href="chap18.html#X8511B8DF83324C27"><span class="RefLink">18.2-1</span></a>), but you may alter it appropriately.</p>

<p>If a generator <var class="Arg">gen</var> has been specified, <code class="func">TzEliminate</code> eliminates it if possible, i. e. if there is a relator in which <var class="Arg">gen</var> occurs just once. If no second argument has been specified, <code class="func">TzEliminate</code> eliminates some appropriate generator if possible and if the resulting total length of the relators will not exceed the Tietze options parameter <code class="code">lengthLimit</code>.</p>

<p>If an integer <var class="Arg">n</var> has been specified, <code class="func">TzEliminate</code> tries to eliminate up to <var class="Arg">n</var> generators. Note that the calls <code class="code">TzEliminate(<var class="Arg">P</var>)</code> and <code class="code">TzEliminate(<var class="Arg">P</var>,1)</code> are equivalent.</p>

<p><a id="X7DF4BBDF839643DD" name="X7DF4BBDF839643DD"></a></p>

<h5>48.7-2 TzSearch</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; TzSearch</code>( <var class="Arg">P</var> )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
<p>searches for relator subwords which, in some relator, have a complement of shorter length and which occur in other relators, too, and uses them to reduce these other relators.</p>

<p>The idea is to find pairs of relators <span class="SimpleMath">r_1</span> and <span class="SimpleMath">r_2</span> of length <span class="SimpleMath">l_1</span> and <span class="SimpleMath">l_2</span>, respectively, such that <span class="SimpleMath">l_1 ≤ l_2</span> and <span class="SimpleMath">r_1</span> and <span class="SimpleMath">r_2</span> coincide (possibly after inverting or conjugating one of them) in some maximal subword <span class="SimpleMath">w</span>, say, of length greater than <span class="SimpleMath">l_1/2</span>, and then to substitute each copy of <span class="SimpleMath">w</span> in <span class="SimpleMath">r_2</span> by the inverse complement of <span class="SimpleMath">w</span> in <span class="SimpleMath">r_1</span>.</p>

<p>Two of the Tietze option parameters which are listed in section <a href="chap48.html#X856F37537E9927EE"><span class="RefLink">48.11</span></a> may strongly influence the performance and the results of the command <code class="func">TzSearch</code>. These are the parameters <code class="code">saveLimit</code> and <code class="code">searchSimultaneous</code>. The first of them has the following effect:</p>

<p>When <code class="func">TzSearch</code> has finished its main loop over all relators, then, in general, there are relators which have changed and hence should be handled again in another run through the whole procedure. However, experience shows that it really does not pay to continue this way until no more relators change. Therefore, <code class="func">TzSearch</code> starts a new loop only if the loop just finished has reduced the total length of the relators by at least <code class="code">saveLimit</code> per cent.</p>

<p>The default value of <code class="code">saveLimit</code> is 10 per cent.</p>

<p>To understand the effect of the option <code class="code">searchSimultaneous</code>, we have to look in more detail at how <code class="func">TzSearch</code> proceeds:</p>

<p>First, it sorts the list of relators by increasing lengths. Then it performs a loop over this list. In each step of this loop, the current relator is treated as <em>short relator</em> <span class="SimpleMath">r_1</span>, and a subroutine is called which loops over the succeeding relators, treating them as <em>long relators</em> <span class="SimpleMath">r_2</span> and performing the respective comparisons and substitutions.</p>

<p>As this subroutine performs a very expensive process, it has been implemented as a C routine in the <strong class="pkg">GAP</strong> kernel. For the given relator <span class="SimpleMath">r_1</span> of length <span class="SimpleMath">l_1</span>, say, it first determines the <em>minimal match length</em> <span class="SimpleMath">l</span> which is <span class="SimpleMath">l_1/2+1</span>, if <span class="SimpleMath">l_1</span> is even, or <span class="SimpleMath">(l_1+1)/2</span>, otherwise. Then it builds up a hash list for all subwords of length <span class="SimpleMath">l</span> occurring in the conjugates of <span class="SimpleMath">r_1</span> or <span class="SimpleMath">r_1^{-1}</span>, and finally it loops over all long relators <span class="SimpleMath">r_2</span> and compares the hash values of their subwords of length <span class="SimpleMath">l</span> against this list. A comparison of subwords which is much more expensive is only done if a hash match has been found.</p>

<p>To improve the efficiency of this process we allow the subroutine to handle several short relators simultaneously provided that they have the same minimal match length. If, for example, it handles <span class="SimpleMath">n</span> short relators simultaneously, then you save <span class="SimpleMath">n - 1</span> loops over the long relators <span class="SimpleMath">r_2</span>, but you pay for it by additional fruitless subword comparisons. In general, you will not get the best performance by always choosing the maximal possible number of short relators to be handled simultaneously. In fact, the optimal choice of the number will depend on the concrete presentation under investigation. You can use the parameter <code class="code">searchSimultaneous</code> to prescribe an upper bound for the number of short relators to be handled simultaneously.</p>

<p>The default value of <code class="code">searchSimultaneous</code> is 20.</p>

<p><a id="X87F7A87A7ACF2445" name="X87F7A87A7ACF2445"></a></p>

<h5>48.7-3 TzSearchEqual</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; TzSearchEqual</code>( <var class="Arg">P</var> )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
<p>searches for Tietze relator subwords which, in some relator, have a complement of equal length and which occur in other relators, too, and uses them to modify these other relators.</p>

<p>The idea is to find pairs of relators <span class="SimpleMath">r_1</span> and <span class="SimpleMath">r_2</span> of length <span class="SimpleMath">l_1</span> and <span class="SimpleMath">l_2</span>, respectively, such that <span class="SimpleMath">l_1</span> is even, <span class="SimpleMath">l_1 ≤ l_2</span>, and <span class="SimpleMath">r_1</span> and <span class="SimpleMath">r_2</span> coincide (possibly after inverting or conjugating one of them) in some maximal subword <span class="SimpleMath">w</span>, say, of length at least <span class="SimpleMath">l_1/2</span>. Let <span class="SimpleMath">l</span> be the length of <span class="SimpleMath">w</span>. Then, if <span class="SimpleMath">l &gt; l_1/2</span>, the pair is handled as in <code class="func">TzSearch</code> (<a href="chap48.html#X7DF4BBDF839643DD"><span class="RefLink">48.7-2</span></a>). Otherwise, if <span class="SimpleMath">l = l_1/2</span>, then <code class="func">TzSearchEqual</code> substitutes each copy of <span class="SimpleMath">w</span> in <span class="SimpleMath">r_2</span> by the inverse complement of <span class="SimpleMath">w</span> in <span class="SimpleMath">r_1</span>.</p>

<p>The Tietze option parameter <code class="code">searchSimultaneous</code> is used by <code class="func">TzSearchEqual</code> in the same way as described for <code class="func">TzSearch</code> (<a href="chap48.html#X7DF4BBDF839643DD"><span class="RefLink">48.7-2</span></a>). However, <code class="func">TzSearchEqual</code> does not use the parameter <code class="code">saveLimit</code>: The loop over the relators is executed exactly once.</p>

<p><a id="X80D31A0F7C2A51BD" name="X80D31A0F7C2A51BD"></a></p>

<h5>48.7-4 TzFindCyclicJoins</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; TzFindCyclicJoins</code>( <var class="Arg">P</var> )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
<p>searches for power and commutator relators in order to find pairs of generators which generate a common cyclic subgroup. It uses these pairs to introduce new relators, but it does not introduce any new generators as is done by <code class="func">TzSubstituteCyclicJoins</code> (<a href="chap48.html#X7ADE3B437C19B94D"><span class="RefLink">48.8-2</span></a>).</p>

<p>More precisely: <code class="func">TzFindCyclicJoins</code> searches for pairs of generators <span class="SimpleMath">a</span> and <span class="SimpleMath">b</span> such that (possibly after inverting or conjugating some relators) the set of relators contains the commutator <span class="SimpleMath">[a,b]</span>, a power <span class="SimpleMath">a^n</span>, and a product of the form <span class="SimpleMath">a^s b^t</span> with <span class="SimpleMath">s</span> prime to <span class="SimpleMath">n</span>. For each such pair, <code class="func">TzFindCyclicJoins</code> uses the Euclidean algorithm to express <span class="SimpleMath">a</span> as a power of <span class="SimpleMath">b</span>, and then it eliminates <span class="SimpleMath">a</span>.</p>

<p><a id="X7D2FACCF79F57040" name="X7D2FACCF79F57040"></a></p>

<h4>48.8 <span class="Heading">Tietze Transformations that introduce new Generators</span></h4>

<p>Some of the Tietze transformation commands listed so far may eliminate generators and hence change the given presentation to a presentation on a subset of the given set of generators, but they all do <em>not</em> introduce new generators. However, sometimes there will be the need to substitute certain words as new generators in order to improve a presentation. Therefore <strong class="pkg">GAP</strong> offers the two commands <code class="func">TzSubstitute</code> (<a href="chap48.html#X846DB23E8236FF8A"><span class="RefLink">48.8-1</span></a>) and <code class="func">TzSubstituteCyclicJoins</code> (<a href="chap48.html#X7ADE3B437C19B94D"><span class="RefLink">48.8-2</span></a>) which introduce new generators.</p>

<p><a id="X846DB23E8236FF8A" name="X846DB23E8236FF8A"></a></p>

<h5>48.8-1 <span class="Heading">TzSubstitute</span></h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; TzSubstitute</code>( <var class="Arg">P</var>, <var class="Arg">word</var> )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; TzSubstitute</code>( <var class="Arg">P</var>[, <var class="Arg">n</var>[, <var class="Arg">eliminate</var>]] )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
<p>In the first form <code class="func">TzSubstitute</code> expects <var class="Arg">P</var> to be a presentation and <var class="Arg">word</var> to be either an abstract word or a Tietze word in the generators of <var class="Arg">P</var>. It substitutes the given word as a new generator of <var class="Arg">P</var>. This is done as follows: First, <code class="func">TzSubstitute</code> creates a new abstract generator, <span class="SimpleMath">g</span> say, and adds it to the presentation, then it adds a new relator <span class="SimpleMath">g^{-1} ⋅ <var class="Arg">word</var></span>.</p>

<p>In its second form, <code class="func">TzSubstitute</code> substitutes a squarefree word of length 2 as a new generator and then eliminates a generator from the extended generator list. We will describe this process in more detail below.</p>

<p>The parameters <var class="Arg">n</var> and <var class="Arg">eliminate</var> are optional. If you specify arguments for them, then <var class="Arg">n</var> is expected to be a positive integer, and <var class="Arg">eliminate</var> is expected to be 0, 1, or 2. The default values are <var class="Arg">n</var> <span class="SimpleMath">= 1</span> and <var class="Arg">eliminate</var> <span class="SimpleMath">= 0</span>.</p>

<p><code class="func">TzSubstitute</code> first determines the <var class="Arg">n</var> most frequently occurring relator subwords of the form <span class="SimpleMath">g_1 g_2</span>, where <span class="SimpleMath">g_1</span> and <span class="SimpleMath">g_2</span> are different generators or their inverses, and sorts them by decreasing numbers of occurrences.</p>

<p>Let <span class="SimpleMath">a b</span> be the last word in that list, and let <span class="SimpleMath">i</span> be the smallest positive integer which has not yet been used as a generator number in the presentation <var class="Arg">P</var> so far. <code class="func">TzSubstitute</code> defines a new abstract generator <span class="SimpleMath">x_i</span> named <code class="code">"_x<var class="Arg">i</var>"</code> and adds it to <var class="Arg">P</var> (see <code class="func">AddGenerator</code> (<a href="chap48.html#X7F632A6D8685855D"><span class="RefLink">48.5-1</span></a>)). Then it adds the word <span class="SimpleMath">x_i^{-1} a b</span> as a new relator to <var class="Arg">P</var> and replaces all occurrences of <span class="SimpleMath">a b</span> in the relators by <span class="SimpleMath">x_i</span>. Finally, it eliminates some suitable generator from <var class="Arg">P</var>.</p>

<p>The choice of the generator to be eliminated depends on the actual value of the parameter <var class="Arg">eliminate</var>:</p>

<p>If <var class="Arg">eliminate</var> is zero, <code class="func">TzSubstitute</code> just calls the function <code class="func">TzEliminate</code> (<a href="chap48.html#X85989AF886EC2BF6"><span class="RefLink">48.7-1</span></a>). So it may happen that it is the just introduced generator <span class="SimpleMath">x_i</span> which now is deleted again so that you don't get any remarkable progress in simplifying your presentation. On the first glance this does not look reasonable, but it is a consequence of the request that a call of <code class="func">TzSubstitute</code> with <var class="Arg">eliminate</var> = 0 must not increase the total length of the relators.</p>

<p>Otherwise, if <var class="Arg">eliminate</var> is 1 or 2, <code class="func">TzSubstitute</code> eliminates the respective factor of the substituted word <span class="SimpleMath">a b</span>, i. e., it eliminates <span class="SimpleMath">a</span> if <var class="Arg">eliminate</var> = 1 or <span class="SimpleMath">b</span> if <var class="Arg">eliminate</var> = 2. In this case, it may happen that the total length of the relators increases, but sometimes such an intermediate extension is the only way to finally reduce a given presentation.</p>

<p>There is still another property of the command <code class="func">TzSubstitute</code> which should be mentioned. If, for instance, <code class="code">word</code> is an abstract word, a call</p>


<div class="example"><pre>
TzSubstitute( P, word );
</pre></div>

<p>is more or less equivalent to</p>


<div class="example"><pre>
AddGenerator( P );
g := GeneratorsOfPresentation(P)[Length(GeneratorsOfPresentation(P))];
AddRelator( P, g^-1 * word );
</pre></div>

<p>However, there is a difference: If you are tracing generator images and preimages of <var class="Arg">P</var> through the Tietze transformations applied to <var class="Arg">P</var> (see <a href="chap48.html#X85E703997A0212EE"><span class="RefLink">48.9</span></a>), then <code class="func">TzSubstitute</code>, as a Tietze transformation of <var class="Arg">P</var>, will update and save the respective lists, whereas a call of the function <code class="func">AddGenerator</code> (<a href="chap48.html#X7F632A6D8685855D"><span class="RefLink">48.5-1</span></a>) (which does not perform a Tietze transformation) will delete these lists and hence terminate the tracing.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">G := PerfectGroup( IsSubgroupFpGroup, 960, 1 );</span>
A5 2^4
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">P := PresentationFpGroup( G );</span>
&lt;presentation with 6 gens and 21 rels of total length 84&gt;
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">GeneratorsOfPresentation( P );</span>
[ a, b, s, t, u, v ]
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">TzGoGo( P );</span>
#I  there are 3 generators and 10 relators of total length 81
#I  there are 3 generators and 10 relators of total length 80
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">TzPrintGenerators( P );</span>
#I  1.  a   31 occurrences   involution
#I  2.  b   26 occurrences
#I  3.  t   23 occurrences   involution
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">a := GeneratorsOfPresentation( P )[1];;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">b := GeneratorsOfPresentation( P )[2];;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">TzSubstitute( P, a*b );</span>
#I  now the presentation has 4 generators, the new generator is _x7
#I  substituting new generator _x7 defined by a*b
#I  there are 4 generators and 11 relators of total length 83
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">TzGo( P );</span>
#I  there are 3 generators and 10 relators of total length 74
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">TzPrintGenerators( P );</span>
#I  1.  a   23 occurrences   involution
#I  2.  t   23 occurrences   involution
#I  3.  _x7   28 occurrences
</pre></div>

<p>As an example of an application of the command <code class="func">TzSubstitute</code> in its second form we handle a subgroup of index 266 in the Janko group <span class="SimpleMath">J_1</span>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">F2 := FreeGroup( "a", "b" );;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">J1 := F2 / [ F2.1^2, F2.2^3, (F2.1*F2.2)^7,</span>
<span class="GAPprompt">&gt;</span> <span class="GAPinput">Comm(F2.1,F2.2)^10, Comm(F2.1,F2.2^-1*(F2.1*F2.2)^2)^6 ];;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">a := J1.1;; b := J1.2;;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">H := Subgroup ( J1, [ a, b^(a*b*(a*b^-1)^2) ] );;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">P := PresentationSubgroup( J1, H );</span>
&lt;presentation with 23 gens and 82 rels of total length 530&gt;
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">TzGoGo( P );</span>
#I  there are 3 generators and 47 relators of total length 1368
#I  there are 2 generators and 46 relators of total length 3773
#I  there are 2 generators and 46 relators of total length 2570
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">TzGoGo( P );</span>
#I  there are 2 generators and 46 relators of total length 2568
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">TzGoGo( P );</span>
</pre></div>

<p>Here we do not get any more progress without substituting a new generator.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">TzSubstitute( P );</span>
#I  substituting new generator _x28 defined by _x6*_x23^-1
#I  eliminating _x28 = _x6*_x23^-1
</pre></div>

<p><strong class="pkg">GAP</strong> cannot substitute a new generator without extending the total length, so we have to explicitly ask for it by using the second form of the command <code class="func">TzSubstitute</code>. Our problem is to choose appropriate values for the arguments <var class="Arg">n</var> and <var class="Arg">eliminate</var>. For this purpose it may be helpful to print out a list of the most frequently occurring squarefree relator subwords of length 2.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">TzPrintPairs( P );</span>
#I  1.  504  occurrences of  _x6 * _x23^-1
#I  2.  504  occurrences of  _x6^-1 * _x23
#I  3.  448  occurrences of  _x6 * _x23
#I  4.  448  occurrences of  _x6^-1 * _x23^-1
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">TzSubstitute( P, 2, 1 );</span>
#I  substituting new generator _x29 defined by _x6^-1*_x23
#I  eliminating _x6 = _x23*_x29^-1
#I  there are 2 generators and 46 relators of total length 2867
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">TzGoGo( P );</span>
#I  there are 2 generators and 45 relators of total length 2417
#I  there are 2 generators and 45 relators of total length 2122
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">TzSubstitute( P, 1, 2 );</span>
#I  substituting new generator _x30 defined by _x23*_x29^-1
#I  eliminating _x29 = _x30^-1*_x23
#I  there are 2 generators and 45 relators of total length 2192
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">TzGoGo( P );</span>
#I  there are 2 generators and 42 relators of total length 1637
#I  there are 2 generators and 40 relators of total length 1286
#I  there are 2 generators and 36 relators of total length 807
#I  there are 2 generators and 32 relators of total length 625
#I  there are 2 generators and 22 relators of total length 369
#I  there are 2 generators and 18 relators of total length 213
#I  there are 2 generators and 13 relators of total length 141
#I  there are 2 generators and 12 relators of total length 121
#I  there are 2 generators and 10 relators of total length 101
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">TzPrintPairs( P );</span>
#I  1.  19  occurrences of  _x23 * _x30^-1
#I  2.  19  occurrences of  _x23^-1 * _x30
#I  3.  14  occurrences of  _x23 * _x30
#I  4.  14  occurrences of  _x23^-1 * _x30^-1
</pre></div>

<p>If we save a copy of the current presentation, then later we will be able to restart the computation from the current state.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">P1 := ShallowCopy( P );</span>
&lt;presentation with 2 gens and 10 rels of total length 101&gt;
</pre></div>

<p>Just for demonstration we make an inconvenient choice:</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">TzSubstitute( P, 3, 1 );</span>
#I  substituting new generator _x31 defined by _x23*_x30
#I  eliminating _x23 = _x31*_x30^-1
#I  there are 2 generators and 10 relators of total length 122
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">TzGoGo( P );</span>
#I  there are 2 generators and 9 relators of total length 105
</pre></div>

<p>This presentation is worse than the one we have saved, so we restart from that presentation again.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">P := ShallowCopy( P1 );</span>
&lt;presentation with 2 gens and 10 rels of total length 101&gt;
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">TzSubstitute( P, 2, 1);</span>
#I  substituting new generator _x31 defined by _x23^-1*_x30
#I  eliminating _x23 = _x30*_x31^-1
#I  there are 2 generators and 10 relators of total length 107
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">TzGoGo( P );</span>
#I  there are 2 generators and 9 relators of total length 84
#I  there are 2 generators and 8 relators of total length 75
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">TzSubstitute( P, 2, 1);</span>
#I  substituting new generator _x32 defined by _x30^-1*_x31
#I  eliminating _x30 = _x31*_x32^-1
#I  there are 2 generators and 8 relators of total length 71
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">TzGoGo( P );</span>
#I  there are 2 generators and 7 relators of total length 56
#I  there are 2 generators and 5 relators of total length 36
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">TzPrintRelators( P );</span>
#I  1. _x32^5
#I  2. _x31^5
#I  3. (_x31^-1*_x32^-1)^3
#I  4. _x31*(_x32*_x31^-1)^2*_x32*_x31*_x32^-2
#I  5. _x31^-1*_x32^2*(_x31*_x32^-1*_x31)^2*_x32^2
</pre></div>

<p><a id="X7ADE3B437C19B94D" name="X7ADE3B437C19B94D"></a></p>

<h5>48.8-2 TzSubstituteCyclicJoins</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; TzSubstituteCyclicJoins</code>( <var class="Arg">P</var> )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
<p>tries to find pairs of commuting generators <span class="SimpleMath">a</span> and <span class="SimpleMath">b</span>, say, such that the exponent of <span class="SimpleMath">a</span> (i. e. the least currently known positive integer <span class="SimpleMath">n</span> such that <span class="SimpleMath">a^n</span> is a relator in <var class="Arg">P</var>) is prime to the exponent of <span class="SimpleMath">b</span>. For each such pair, their product <span class="SimpleMath">a b</span> is substituted as a new generator, and <span class="SimpleMath">a</span> and <span class="SimpleMath">b</span> are eliminated.</p>

<p><a id="X85E703997A0212EE" name="X85E703997A0212EE"></a></p>

<h4>48.9 <span class="Heading">Tracing generator images through Tietze transformations</span></h4>

<p>Any sequence of Tietze transformations applied to a presentation, starting from some presentation <span class="SimpleMath">P_1</span> and ending up with some presentation <span class="SimpleMath">P_2</span>, defines an isomorphism, <span class="SimpleMath">φ</span> say, between the groups defined by <span class="SimpleMath">P_1</span> and <span class="SimpleMath">P_2</span>, respectively. Sometimes it is desirable to know the images of the (old) generators of <span class="SimpleMath">P_1</span> or the preimages of the (new) generators of <span class="SimpleMath">P_2</span> under <span class="SimpleMath">φ</span>. The <strong class="pkg">GAP</strong> Tietze transformation functions are able to trace these images. This is not automatically done because the involved words may grow to tremendous length, but it will be done if you explicitly request for it by calling the function <code class="func">TzInitGeneratorImages</code> (<a href="chap48.html#X7D855FA08242898A"><span class="RefLink">48.9-1</span></a>).</p>

<p><a id="X7D855FA08242898A" name="X7D855FA08242898A"></a></p>

<h5>48.9-1 TzInitGeneratorImages</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; TzInitGeneratorImages</code>( <var class="Arg">P</var> )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
<p>expects <var class="Arg">P</var> to be a presentation. It defines the current generators to be the "old generators" of <var class="Arg">P</var> and initializes the (pre)image tracing. See <code class="func">TzImagesOldGens</code> (<a href="chap48.html#X798B38F87C082C45"><span class="RefLink">48.9-3</span></a>) and <code class="func">TzPreImagesNewGens</code> (<a href="chap48.html#X7AC41B117DBB87D6"><span class="RefLink">48.9-4</span></a>) for details.</p>

<p>You can reinitialize the tracing of the generator images at any later state by just calling the function <code class="func">TzInitGeneratorImages</code> again.</p>

<p>Note: A subsequent call of the function <code class="func">DecodeTree</code> (<a href="chap48.html#X7ACBFE2F78D72A31"><span class="RefLink">48.10-1</span></a>) will imply that the images and preimages are deleted and reinitialized after decoding the tree.</p>

<p>Moreover, if you introduce a new generator by calling the function <code class="func">AddGenerator</code> (<a href="chap48.html#X7F632A6D8685855D"><span class="RefLink">48.5-1</span></a>) described in Section <a href="chap48.html#X82455E5885D73FFF"><span class="RefLink">48.5</span></a>, this new generator cannot be traced in the old generators. Therefore <code class="func">AddGenerator</code> (<a href="chap48.html#X7F632A6D8685855D"><span class="RefLink">48.5-1</span></a>) will terminate the tracing of the generator images and preimages and delete the respective lists whenever it is called.</p>

<p><a id="X7AB9A06F80FB3659" name="X7AB9A06F80FB3659"></a></p>

<h5>48.9-2 OldGeneratorsOfPresentation</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; OldGeneratorsOfPresentation</code>( <var class="Arg">P</var> )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
<p>assumes that <var class="Arg">P</var> is a presentation for which the generator images and preimages are being traced under Tietze transformations. It returns the list of old generators of <var class="Arg">P</var>.</p>

<p><a id="X798B38F87C082C45" name="X798B38F87C082C45"></a></p>

<h5>48.9-3 TzImagesOldGens</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; TzImagesOldGens</code>( <var class="Arg">P</var> )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
<p>assumes that <var class="Arg">P</var> is a presentation for which the generator images and preimages are being traced under Tietze transformations. It returns a list <span class="SimpleMath">l</span> of words in the (current) <code class="func">GeneratorsOfPresentation</code> (<a href="chap48.html#X849429BC7D435F77"><span class="RefLink">48.1-3</span></a>) value of <var class="Arg">P</var> such that the <span class="SimpleMath">i</span>-th word <span class="SimpleMath">l[i]</span> represents the <span class="SimpleMath">i</span>-th old generator of <var class="Arg">P</var>, i. e., the <span class="SimpleMath">i</span>-th entry of the <code class="func">OldGeneratorsOfPresentation</code> (<a href="chap48.html#X7AB9A06F80FB3659"><span class="RefLink">48.9-2</span></a>) value of <var class="Arg">P</var>.</p>

<p><a id="X7AC41B117DBB87D6" name="X7AC41B117DBB87D6"></a></p>

<h5>48.9-4 TzPreImagesNewGens</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; TzPreImagesNewGens</code>( <var class="Arg">P</var> )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
<p>assumes that <var class="Arg">P</var> is a presentation for which the generator images and preimages are being traced under Tietze transformations. It returns a list <span class="SimpleMath">l</span> of words in the old generators of <var class="Arg">P</var> (the <code class="func">OldGeneratorsOfPresentation</code> (<a href="chap48.html#X7AB9A06F80FB3659"><span class="RefLink">48.9-2</span></a>) value of <var class="Arg">P</var>) such that the <span class="SimpleMath">i</span>-th entry of <span class="SimpleMath">l</span> represents the <span class="SimpleMath">i</span>-th (current) generator of <var class="Arg">P</var> (the <code class="func">GeneratorsOfPresentation</code> (<a href="chap48.html#X849429BC7D435F77"><span class="RefLink">48.1-3</span></a>) value of <var class="Arg">P</var>).</p>

<p><a id="X7F086D0E7AD6173B" name="X7F086D0E7AD6173B"></a></p>

<h5>48.9-5 TzPrintGeneratorImages</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; TzPrintGeneratorImages</code>( <var class="Arg">P</var> )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
<p>assumes that <var class="Arg">P</var> is a presentation for which the generator images and preimages are being traced under Tietze transformations. It displays the preimages of the current generators as Tietze words in the old generators, and the images of the old generators as Tietze words in the current generators.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">G := PerfectGroup( IsSubgroupFpGroup, 960, 1 );</span>
A5 2^4
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">P := PresentationFpGroup( G );</span>
&lt;presentation with 6 gens and 21 rels of total length 84&gt;
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">TzInitGeneratorImages( P );</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">TzGo( P );</span>
#I  there are 3 generators and 11 relators of total length 96
#I  there are 3 generators and 10 relators of total length 81
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">TzPrintGeneratorImages( P );</span>
#I  preimages of current generators as Tietze words in the old ones:
#I  1. [ 1 ]
#I  2. [ 2 ]
#I  3. [ 4 ]
#I  images of old generators as Tietze words in the current ones:
#I  1. [ 1 ]
#I  2. [ 2 ]
#I  3. [ 1, -2, 1, 3, 1, 2, 1 ]
#I  4. [ 3 ]
#I  5. [ -2, 1, 3, 1, 2 ]
#I  6. [ 1, 3, 1 ]
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">gens := GeneratorsOfPresentation( P );</span>
[ a, b, t ]
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">oldgens := OldGeneratorsOfPresentation( P );</span>
[ a, b, s, t, u, v ]
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">TzImagesOldGens( P );</span>
[ a, b, a*b^-1*a*t*a*b*a, t, b^-1*a*t*a*b, a*t*a ]
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">for i in [ 1 .. Length( oldgens ) ] do</span>
<span class="GAPprompt">&gt;</span> <span class="GAPinput">Print( oldgens[i], " = ", TzImagesOldGens( P )[i], "\n" );</span>
<span class="GAPprompt">&gt;</span> <span class="GAPinput">od;</span>
a = a
b = b
s = a*b^-1*a*t*a*b*a
t = t
u = b^-1*a*t*a*b
v = a*t*a
</pre></div>

<p><a id="X7D9E283D81CCCF1A" name="X7D9E283D81CCCF1A"></a></p>

<h4>48.10 <span class="Heading">The Decoding Tree Procedure</span></h4>

<p><a id="X7ACBFE2F78D72A31" name="X7ACBFE2F78D72A31"></a></p>

<h5>48.10-1 DecodeTree</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; DecodeTree</code>( <var class="Arg">P</var> )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
<p>assumes that <var class="Arg">P</var> is a subgroup presentation provided by the Reduced Reidemeister-Schreier or by the Modified Todd-Coxeter method (see <code class="func">PresentationSubgroupRrs</code> (<a href="chap48.html#X857365CD87ADC29E"><span class="RefLink">48.2-2</span></a>), <code class="func">PresentationNormalClosureRrs</code> (<a href="chap48.html#X7D6A52837BEE5C3D"><span class="RefLink">48.2-5</span></a>), <code class="func">PresentationSubgroupMtc</code> (<a href="chap48.html#X80BA10F780EAE68E"><span class="RefLink">48.2-4</span></a>)). It eliminates the secondary generators of <var class="Arg">P</var> (see Section <a href="chap48.html#X8118FECE7AD1879B"><span class="RefLink">48.2</span></a>) by applying the so called "decoding tree" procedure.</p>

<p><code class="func">DecodeTree</code> is called automatically by the command <code class="func">PresentationSubgroupMtc</code> (<a href="chap48.html#X80BA10F780EAE68E"><span class="RefLink">48.2-4</span></a>) where it reduces <var class="Arg">P</var> to a presentation on the given (primary) subgroup generators.</p>

<p>In order to explain the effect of this command we need to insert a few remarks on the subgroup presentation commands described in section <a href="chap48.html#X8118FECE7AD1879B"><span class="RefLink">48.2</span></a>. All these commands have the common property that in the process of constructing a presentation for a given subgroup <var class="Arg">H</var> of a finitely presented group <var class="Arg">G</var> they first build up a highly redundant list of generators of <var class="Arg">H</var> which consists of an (in general small) list of "primary" generators, followed by an (in general large) list of "secondary" generators, and then construct a presentation <span class="SimpleMath">P_0</span>, say, <em>on a sublist of these generators</em> by rewriting the defining relators of <var class="Arg">G</var>. This sublist contains all primary, but, at least in general, by far not all secondary generators.</p>

<p>The role of the primary generators depends on the concrete choice of the subgroup presentation command. If the Modified Todd-Coxeter method is used, they are just the given generators of <var class="Arg">H</var>, whereas in the case of the Reduced Reidemeister-Schreier algorithm they are constructed by the program.</p>

<p>Each of the secondary generators is defined by a word of length two in the preceding generators and their inverses. By historical reasons, the list of these definitions is called the <em>subgroup generators tree</em> though in fact it is not a tree but rather a kind of bush.</p>

<p>Now we have to distinguish two cases. If <span class="SimpleMath">P_0</span> has been constructed by the Reduced Reidemeister-Schreier routines, it is a presentation of <var class="Arg">H</var>. However, if the Modified Todd-Coxeter routines have been used instead, then the relators in <span class="SimpleMath">P_0</span> are valid relators of <var class="Arg">H</var>, but they do not necessarily define <var class="Arg">H</var>. We handle these cases in turn, starting with the latter one.</p>

<p>In fact, we could easily receive a presentation of <var class="Arg">H</var> also in this case if we extended <span class="SimpleMath">P_0</span> by adding to it all the secondary generators which are not yet contained in it and all the definitions from the generators tree as additional generators and relators. Then we could recursively eliminate all secondary generators by Tietze transformations using the new relators. However, this procedure turns out to be too inefficient to be of interest.</p>

<p>Instead, we use the so called <em>decoding tree</em> procedure (see <a href="chapBib.html#biBAMW82">[AMW82]</a>, <a href="chapBib.html#biBAR84">[AR84]</a>). It proceeds as follows.</p>

<p>Starting from <span class="SimpleMath">P = P_0</span>, it runs through a number of steps in each of which it eliminates the current "last" generator (with respect to the list of all primary and secondary generators). If the last generator <var class="Arg">g</var>, say, is a primary generator, then the procedure terminates. Otherwise it checks whether there is a relator in the current presentation which can be used to substitute <var class="Arg">g</var> by a Tietze transformation. If so, this is done. Otherwise, and only then, the tree definition of <var class="Arg">g</var> is added to <var class="Arg">P</var> as a new relator, and the generators involved are added as new generators if they have not yet been contained in <var class="Arg">P</var>. Subsequently, <var class="Arg">g</var> is eliminated.</p>

<p>Note that the extension of <var class="Arg">P</var> by one or two new generators is <em>not</em> a Tietze transformation. In general, it will change the isomorphism type of the group defined by <var class="Arg">P</var>. However, it is a remarkable property of this procedure, that at the end, i.e., as soon as all secondary generators have been eliminated, it provides a presentation <span class="SimpleMath">P = P_1</span>, say, which defines a group isomorphic to <var class="Arg">H</var>. In fact, it is this presentation which is returned by the command <code class="func">DecodeTree</code> and hence by the command <code class="func">PresentationSubgroupMtc</code> (<a href="chap48.html#X80BA10F780EAE68E"><span class="RefLink">48.2-4</span></a>).</p>

<p>If, in the other case, the presentation <span class="SimpleMath">P_0</span> has been constructed by the Reduced Reidemeister-Schreier algorithm, then <span class="SimpleMath">P_0</span> itself is a presentation of <var class="Arg">H</var>, and the corresponding subgroup presentation command (<code class="func">PresentationSubgroupRrs</code> (<a href="chap48.html#X857365CD87ADC29E"><span class="RefLink">48.2-2</span></a>) or <code class="func">PresentationNormalClosureRrs</code> (<a href="chap48.html#X7D6A52837BEE5C3D"><span class="RefLink">48.2-5</span></a>)) just returns <span class="SimpleMath">P_0</span>.</p>

<p>As mentioned in section <a href="chap48.html#X8118FECE7AD1879B"><span class="RefLink">48.2</span></a>, we recommend to further simplify this presentation before you use it. The standard way to do this is to start from <span class="SimpleMath">P_0</span> and to apply suitable Tietze transformations, e. g., by calling the commands <code class="func">TzGo</code> (<a href="chap48.html#X7C4A30328224C466"><span class="RefLink">48.6-1</span></a>) or <code class="func">TzGoGo</code> (<a href="chap48.html#X801D3D8984E1CA55"><span class="RefLink">48.6-3</span></a>). This is probably the most efficient approach, but you will end up with a presentation on some unpredictable set of generators. As an alternative, <strong class="pkg">GAP</strong> offers you the <code class="func">DecodeTree</code> command which you can use to eliminate all secondary generators (provided that there are no space or time problems). For this purpose, the subgroup presentation commands do not only return the resulting presentation, but also the tree (together with some associated lists) as a kind of side result in a component <var class="Arg">P</var><code class="code">!.tree</code> of the resulting presentation <var class="Arg">P</var>.</p>

<p>Note, however, that the decoding tree routines will not work correctly any more on a presentation from which generators have already been eliminated by Tietze transformations. Therefore, to prevent you from getting wrong results by calling <code class="func">DecodeTree</code> in such a situation, <strong class="pkg">GAP</strong> will automatically remove the subgroup generators tree from a presentation as soon as one of the generators is substituted by a Tietze transformation.</p>

<p>Nevertheless, a certain misuse of the command is still possible, and we want to explicitly warn you from this. The reason is that the Tietze option parameters described in Section <a href="chap48.html#X856F37537E9927EE"><span class="RefLink">48.11</span></a> apply to <code class="func">DecodeTree</code> as well. Hence, in case of inadequate values of these parameters, it may happen that <code class="func">DecodeTree</code> stops before all the secondary generators have vanished. In this case <strong class="pkg">GAP</strong> will display an appropriate warning. Then you should change the respective parameters and continue the process by calling <code class="func">DecodeTree</code> again. Otherwise, if you would apply Tietze transformations, it might happen because of the convention described above that the tree is removed and that you end up with a wrong presentation.</p>

<p>After a successful run of <code class="func">DecodeTree</code> it is convenient to further simplify the resulting presentation by suitable Tietze transformations.</p>

<p>As an example of an explicit call of <code class="func">DecodeTree</code> we compute two presentations of a subgroup of order <span class="SimpleMath">384</span> in a group of order <span class="SimpleMath">6912</span>. In both cases we use the Reduced Reidemeister-Schreier algorithm, but in the first run we just apply the Tietze transformations offered by the <code class="func">TzGoGo</code> (<a href="chap48.html#X801D3D8984E1CA55"><span class="RefLink">48.6-3</span></a>) command with its default parameters, whereas in the second run we call the <code class="func">DecodeTree</code> command before.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">F2 := FreeGroup( "a", "b" );;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">G := F2 / [ F2.1*F2.2^2*F2.1^-1*F2.2^-1*F2.1^3*F2.2^-1,</span>
<span class="GAPprompt">&gt;</span> <span class="GAPinput">               F2.2*F2.1^2*F2.2^-1*F2.1^-1*F2.2^3*F2.1^-1 ];;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">a := G.1;;  b := G.2;;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">H := Subgroup( G, [ Comm(a^-1,b^-1), Comm(a^-1,b), Comm(a,b) ] );;</span>
</pre></div>

<p>We use the Reduced Reidemeister Schreier method and default Tietze transformations to get a presentation for <var class="Arg">H</var>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">P := PresentationSubgroupRrs( G, H );</span>
&lt;presentation with 18 gens and 35 rels of total length 169&gt;
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">TzGoGo( P );</span>
#I  there are 3 generators and 20 relators of total length 488
#I  there are 3 generators and 20 relators of total length 466
</pre></div>

<p>We end up with 20 relators of total length 466. Now we repeat the procedure, but we call the decoding tree algorithm before doing the Tietze transformations.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">P := PresentationSubgroupRrs( G, H );</span>
&lt;presentation with 18 gens and 35 rels of total length 169&gt;
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">DecodeTree( P );</span>
#I  there are 9 generators and 26 relators of total length 185
#I  there are 6 generators and 23 relators of total length 213
#I  there are 3 generators and 20 relators of total length 252
#I  there are 3 generators and 20 relators of total length 244
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">TzGoGo( P );</span>
#I  there are 3 generators and 19 relators of total length 168
#I  there are 3 generators and 17 relators of total length 138
#I  there are 3 generators and 15 relators of total length 114
#I  there are 3 generators and 13 relators of total length 96
#I  there are 3 generators and 12 relators of total length 84
</pre></div>

<p>This time we end up with a shorter presentation.</p>

<p>As an example of an implicit call of the function <code class="func">DecodeTree</code> via the command <code class="func">PresentationSubgroupMtc</code> (<a href="chap48.html#X80BA10F780EAE68E"><span class="RefLink">48.2-4</span></a>) we handle a subgroup of index 240 in a group of order 40320 given by a presentation due to B. H. Neumann. Note that we increase the level of <code class="func">InfoFpGroup</code> (<a href="chap47.html#X8370BF3B78D0B14D"><span class="RefLink">47.1-3</span></a>) temporarily to get some additional output.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">F3 := FreeGroup( "a", "b", "c" );;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">a := F3.1;;  b := F3.2;;  c := F3.3;;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">G := F3 / [ a^3, b^3, c^3, (a*b)^5, (a^-1*b)^5, (a*c)^4,</span>
<span class="GAPprompt">&gt;</span> <span class="GAPinput">    (a*c^-1)^4, a*b^-1*a*b*c^-1*a*c*a*c^-1, (b*c)^3, (b^-1*c)^4 ];;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">a := G.1;;  b := G.2;;  c := G.3;;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">H := Subgroup( G, [ a, c ] );;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">SetInfoLevel( InfoFpGroup, 1 );</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">P := PresentationSubgroupMtc( G, H );;</span>
#I  index = 240  total = 4737  max = 4507
#I  MTC defined 2 primary and 4444 secondary subgroup generators
#I  there are 246 generators and 617 relators of total length 2893
#I  calling DecodeTree
#I  there are 114 generators and 385 relators of total length 1860
#I  there are 69 generators and 294 relators of total length 1855
#I  there are 43 generators and 235 relators of total length 2031
#I  there are 35 generators and 207 relators of total length 2348
#I  there are 25 generators and 181 relators of total length 3055
#I  there are 19 generators and 165 relators of total length 3290
#I  there are 20 generators and 160 relators of total length 5151
#I  there are 23 generators and 159 relators of total length 8177
#I  there are 25 generators and 159 relators of total length 12241
#I  there are 29 generators and 159 relators of total length 18242
#I  there are 34 generators and 159 relators of total length 27364
#I  there are 38 generators and 159 relators of total length 41480
#I  there are 41 generators and 159 relators of total length 62732
#I  there are 45 generators and 159 relators of total length 88872
#I  there are 46 generators and 159 relators of total length 111092
#I  there are 44 generators and 155 relators of total length 158181
#I  there are 32 generators and 155 relators of total length 180478
#I  there are 7 generators and 133 relators of total length 29897
#I  there are 4 generators and 119 relators of total length 28805
#I  there are 3 generators and 116 relators of total length 35209
#I  there are 2 generators and 111 relators of total length 25658
#I  there are 2 generators and 111 relators of total length 22634
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">TzGoGo( P );</span>
#I  there are 2 generators and 108 relators of total length 11760
#I  there are 2 generators and 95 relators of total length 6482
#I  there are 2 generators and 38 relators of total length 1464
#I  there are 2 generators and 8 relators of total length 116
#I  there are 2 generators and 7 relators of total length 76
#I  there are 2 generators and 6 relators of total length 66
#I  there are 2 generators and 6 relators of total length 52
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">TzPrintGenerators( P );</span>
#I  1.  _x1   26 occurrences
#I  2.  _x2   26 occurrences
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">TzPrint( P );</span>
#I  generators: [ _x1, _x2 ]
#I  relators:
#I  1.  3  [ 1, 1, 1 ]
#I  2.  3  [ 2, 2, 2 ]
#I  3.  8  [ 2, -1, 2, -1, 2, -1, 2, -1 ]
#I  4.  8  [ 2, 1, 2, 1, 2, 1, 2, 1 ]
#I  5.  14  [ -1, -2, 1, 2, 1, -2, -1, 2, 1, -2, -1, -2, 1, 2 ]
#I  6.  16  [ 1, 2, 1, -2, 1, 2, 1, -2, 1, 2, 1, -2, 1, 2, 1, -2 ]
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">K :=  FpGroupPresentation( P );</span>
&lt;fp group on the generators [ _x1, _x2 ]&gt;
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">SetInfoLevel( InfoFpGroup, 0 );</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">Size( K );</span>
168
</pre></div>

<p><a id="X856F37537E9927EE" name="X856F37537E9927EE"></a></p>

<h4>48.11 <span class="Heading">Tietze Options</span></h4>

<p>Several of the Tietze transformation commands described above are controlled by certain parameters, the <em>Tietze options</em>, which often have a tremendous influence on their performance and results. However, in each application of the commands, an appropriate choice of these option parameters will depend on the concrete presentation under investigation. Therefore we have implemented the Tietze options in such a way that they are associated to the presentation: Each presentation keeps its own set of Tietze option parameters as an attribute.</p>

<p><a id="X8178683283214D88" name="X8178683283214D88"></a></p>

<h5>48.11-1 TzOptions</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; TzOptions</code>( <var class="Arg">P</var> )</td><td class="tdright">(&nbsp;attribute&nbsp;)</td></tr></table></div>
<p>is a record whose components direct the heuristics applied by the Tietze transformation functions.</p>

<p>You may alter the value of any of these Tietze options by just assigning a new value to the respective record component.</p>

<p>The following Tietze options are recognized by <strong class="pkg">GAP</strong>:</p>


<dl>
<dt><strong class="Mark"><code class="code">protected</code>:</strong></dt>
<dd><p>The first <code class="code">protected</code> generators in a presentation <var class="Arg">P</var> are protected from being eliminated by the Tietze transformations functions. There are only two exceptions: The option <code class="code">protected</code> is ignored by the functions <code class="func">TzEliminate</code> (<a href="chap48.html#X85989AF886EC2BF6"><span class="RefLink">48.7-1</span></a>) and <code class="func">TzSubstitute</code> (<a href="chap48.html#X846DB23E8236FF8A"><span class="RefLink">48.8-1</span></a>) because they explicitly specify the generator to be eliminated. The default value of <code class="code">protected</code> is 0.</p>

</dd>
<dt><strong class="Mark"><code class="code">eliminationsLimit</code>:</strong></dt>
<dd><p>Whenever the elimination phase of the <code class="func">TzGo</code> (<a href="chap48.html#X7C4A30328224C466"><span class="RefLink">48.6-1</span></a>) command is entered for a presentation <var class="Arg">P</var>, then it will eliminate at most <code class="code">eliminationsLimit</code> generators (except for further ones which have turned out to be trivial). Hence you may use the <code class="code">eliminationsLimit</code> parameter as a break criterion for the <code class="func">TzGo</code> (<a href="chap48.html#X7C4A30328224C466"><span class="RefLink">48.6-1</span></a>) command. Note, however, that it is ignored by the <code class="func">TzEliminate</code> (<a href="chap48.html#X85989AF886EC2BF6"><span class="RefLink">48.7-1</span></a>) command. The default value of <code class="code">eliminationsLimit</code> is 100.</p>

</dd>
<dt><strong class="Mark"><code class="code">expandLimit</code>:</strong></dt>
<dd><p>Whenever the routine for eliminating more than 1 generators is called for a presentation <var class="Arg">P</var> by the <code class="func">TzEliminate</code> (<a href="chap48.html#X85989AF886EC2BF6"><span class="RefLink">48.7-1</span></a>) command or the elimination phase of the <code class="func">TzGo</code> (<a href="chap48.html#X7C4A30328224C466"><span class="RefLink">48.6-1</span></a>) command, then it saves the given total length of the relators, and subsequently it checks the current total length against its value before each elimination. If the total length has increased to more than <code class="code">expandLimit</code> per cent of its original value, then the routine returns instead of eliminating another generator. Hence you may use the <code class="code">expandLimit</code> parameter as a break criterion for the <code class="func">TzGo</code> (<a href="chap48.html#X7C4A30328224C466"><span class="RefLink">48.6-1</span></a>) command. The default value of <code class="code">expandLimit</code> is 150.</p>

</dd>
<dt><strong class="Mark"><code class="code">generatorsLimit</code>:</strong></dt>
<dd><p>Whenever the elimination phase of the <code class="func">TzGo</code> (<a href="chap48.html#X7C4A30328224C466"><span class="RefLink">48.6-1</span></a>) command is entered for a presentation <var class="Arg">P</var> with <span class="SimpleMath">n</span> generators, then it will eliminate at most <span class="SimpleMath">n -</span><code class="code">generatorsLimit</code> generators (except for generators which turn out to be trivial). Hence you may use the <code class="code">generatorsLimit</code> parameter as a break criterion for the <code class="func">TzGo</code> (<a href="chap48.html#X7C4A30328224C466"><span class="RefLink">48.6-1</span></a>) command. The default value of <code class="code">generatorsLimit</code> is 0.</p>

</dd>
<dt><strong class="Mark"><code class="code">lengthLimit</code>:</strong></dt>
<dd><p>The Tietze transformation commands will never eliminate a generator of a presentation <var class="Arg">P</var>, if they cannot exclude the possibility that the resulting total length of the relators exceeds the maximal <strong class="pkg">GAP</strong> list length of <span class="SimpleMath">2^31-1</span> or the value of the option <code class="code">lengthLimit</code>. The default value of <code class="code">lengthLimit</code> is <span class="SimpleMath">2^31-1</span>.</p>

</dd>
<dt><strong class="Mark"><code class="code">loopLimit</code>:</strong></dt>
<dd><p>Whenever the <code class="func">TzGo</code> (<a href="chap48.html#X7C4A30328224C466"><span class="RefLink">48.6-1</span></a>) command is called for a presentation <var class="Arg">P</var>, then it will loop over at most <code class="code">loopLimit</code> of its basic steps. Hence you may use the <code class="code">loopLimit</code> parameter as a break criterion for the <code class="func">TzGo</code> (<a href="chap48.html#X7C4A30328224C466"><span class="RefLink">48.6-1</span></a>) command. The default value of <code class="code">loopLimit</code> is <code class="func">infinity</code> (<a href="chap18.html#X8511B8DF83324C27"><span class="RefLink">18.2-1</span></a>).</p>

</dd>
<dt><strong class="Mark"><code class="code">printLevel</code>:</strong></dt>
<dd><p>Whenever Tietze transformation commands are called for a presentation <var class="Arg">P</var> with <code class="code">printLevel</code> <span class="SimpleMath">= 0</span>, they will not provide any output except for error messages. If <code class="code">printLevel</code> <span class="SimpleMath">= 1</span>, they will display some reasonable amount of output which allows you to watch the progress of the computation and to decide about your next commands. In the case <code class="code">printLevel</code> <span class="SimpleMath">= 2</span>, you will get a much more generous amount of output. Finally, if <code class="code">printLevel</code> <span class="SimpleMath">= 3</span>, various messages on internal details will be added. The default value of <code class="code">printLevel</code> is 1.</p>

</dd>
<dt><strong class="Mark"><code class="code">saveLimit</code>:</strong></dt>
<dd><p>Whenever the <code class="func">TzSearch</code> (<a href="chap48.html#X7DF4BBDF839643DD"><span class="RefLink">48.7-2</span></a>) command has finished its main loop over all relators of a presentation <var class="Arg">P</var>, then it checks whether during this loop the total length of the relators has been reduced by at least <code class="code">saveLimit</code> per cent. If this is the case, then <code class="func">TzSearch</code> (<a href="chap48.html#X7DF4BBDF839643DD"><span class="RefLink">48.7-2</span></a>) repeats its procedure instead of returning. Hence you may use the <code class="code">saveLimit</code> parameter as a break criterion for the <code class="func">TzSearch</code> (<a href="chap48.html#X7DF4BBDF839643DD"><span class="RefLink">48.7-2</span></a>) command and, in particular, for the search phase of the <code class="func">TzGo</code> (<a href="chap48.html#X7C4A30328224C466"><span class="RefLink">48.6-1</span></a>) command. The default value of <code class="code">saveLimit</code> is 10.</p>

</dd>
<dt><strong class="Mark"><code class="code">searchSimultaneous</code>:</strong></dt>
<dd><p>Whenever the <code class="func">TzSearch</code> (<a href="chap48.html#X7DF4BBDF839643DD"><span class="RefLink">48.7-2</span></a>) or the <code class="func">TzSearchEqual</code> (<a href="chap48.html#X87F7A87A7ACF2445"><span class="RefLink">48.7-3</span></a>) command is called for a presentation <var class="Arg">P</var>, then it is allowed to handle up to <code class="code">searchSimultaneous</code> short relators simultaneously (see the description of the <code class="func">TzSearch</code> (<a href="chap48.html#X7DF4BBDF839643DD"><span class="RefLink">48.7-2</span></a>) command for more details). The choice of this parameter may heavily influence the performance as well as the result of the <code class="func">TzSearch</code> (<a href="chap48.html#X7DF4BBDF839643DD"><span class="RefLink">48.7-2</span></a>) and the <code class="func">TzSearchEqual</code> (<a href="chap48.html#X87F7A87A7ACF2445"><span class="RefLink">48.7-3</span></a>) commands and hence also of the search phase of the <code class="func">TzGo</code> (<a href="chap48.html#X7C4A30328224C466"><span class="RefLink">48.6-1</span></a>) command. The default value of <code class="code">searchSimultaneous</code> is 20.</p>

</dd>
</dl>
<p><a id="X7BC90B6882DE6D10" name="X7BC90B6882DE6D10"></a></p>

<h5>48.11-2 TzPrintOptions</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; TzPrintOptions</code>( <var class="Arg">P</var> )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
<p>prints the current values of the Tietze options of the presentation <var class="Arg">P</var>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">TzPrintOptions( P );</span>
#I  protected          = 0
#I  eliminationsLimit  = 100
#I  expandLimit        = 150
#I  generatorsLimit    = 0
#I  lengthLimit        = 2147483647
#I  loopLimit          = infinity
#I  printLevel         = 1
#I  saveLimit          = 10
#I  searchSimultaneous = 20
</pre></div>


<div class="chlinkprevnextbot">&nbsp;<a href="chap0.html">[Top of Book]</a>&nbsp;  <a href="chap0.html#contents">[Contents]</a>&nbsp;  &nbsp;<a href="chap47.html">[Previous Chapter]</a>&nbsp;  &nbsp;<a href="chap49.html">[Next Chapter]</a>&nbsp;  </div>


<div class="chlinkbot"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a>  <a href="chap1.html">1</a>  <a href="chap2.html">2</a>  <a href="chap3.html">3</a>  <a href="chap4.html">4</a>  <a href="chap5.html">5</a>  <a href="chap6.html">6</a>  <a href="chap7.html">7</a>  <a href="chap8.html">8</a>  <a href="chap9.html">9</a>  <a href="chap10.html">10</a>  <a href="chap11.html">11</a>  <a href="chap12.html">12</a>  <a href="chap13.html">13</a>  <a href="chap14.html">14</a>  <a href="chap15.html">15</a>  <a href="chap16.html">16</a>  <a href="chap17.html">17</a>  <a href="chap18.html">18</a>  <a href="chap19.html">19</a>  <a href="chap20.html">20</a>  <a href="chap21.html">21</a>  <a href="chap22.html">22</a>  <a href="chap23.html">23</a>  <a href="chap24.html">24</a>  <a href="chap25.html">25</a>  <a href="chap26.html">26</a>  <a href="chap27.html">27</a>  <a href="chap28.html">28</a>  <a href="chap29.html">29</a>  <a href="chap30.html">30</a>  <a href="chap31.html">31</a>  <a href="chap32.html">32</a>  <a href="chap33.html">33</a>  <a href="chap34.html">34</a>  <a href="chap35.html">35</a>  <a href="chap36.html">36</a>  <a href="chap37.html">37</a>  <a href="chap38.html">38</a>  <a href="chap39.html">39</a>  <a href="chap40.html">40</a>  <a href="chap41.html">41</a>  <a href="chap42.html">42</a>  <a href="chap43.html">43</a>  <a href="chap44.html">44</a>  <a href="chap45.html">45</a>  <a href="chap46.html">46</a>  <a href="chap47.html">47</a>  <a href="chap48.html">48</a>  <a href="chap49.html">49</a>  <a href="chap50.html">50</a>  <a href="chap51.html">51</a>  <a href="chap52.html">52</a>  <a href="chap53.html">53</a>  <a href="chap54.html">54</a>  <a href="chap55.html">55</a>  <a href="chap56.html">56</a>  <a href="chap57.html">57</a>  <a href="chap58.html">58</a>  <a href="chap59.html">59</a>  <a href="chap60.html">60</a>  <a href="chap61.html">61</a>  <a href="chap62.html">62</a>  <a href="chap63.html">63</a>  <a href="chap64.html">64</a>  <a href="chap65.html">65</a>  <a href="chap66.html">66</a>  <a href="chap67.html">67</a>  <a href="chap68.html">68</a>  <a href="chap69.html">69</a>  <a href="chap70.html">70</a>  <a href="chap71.html">71</a>  <a href="chap72.html">72</a>  <a href="chap73.html">73</a>  <a href="chap74.html">74</a>  <a href="chap75.html">75</a>  <a href="chap76.html">76</a>  <a href="chap77.html">77</a>  <a href="chap78.html">78</a>  <a href="chap79.html">79</a>  <a href="chap80.html">80</a>  <a href="chap81.html">81</a>  <a href="chap82.html">82</a>  <a href="chap83.html">83</a>  <a href="chap84.html">84</a>  <a href="chap85.html">85</a>  <a href="chap86.html">86</a>  <a href="chap87.html">87</a>  <a href="chapBib.html">Bib</a>  <a href="chapInd.html">Ind</a>  </div>

<hr />
<p class="foot">generated by <a href="http://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a></p>
</body>
</html>