1)if false 2\documentclass{article} 3\usepackage{axiom} 4\usepackage{url} 5\begin{document} 6\title{Group Presentations} 7\author{Martin J Baker} 8\maketitle 9\begin{abstract} 10This file implements group structures related to algebraic topology, 11specifically its homotopy and homology. 12 13There are two such structures in this file: 14\begin{itemize} 15\item GroupPresentation - Defines a group by its generators and 16relations. Used to hold fundamental group (homotopy). 17\item Homology - Intended to hold homology which is calculated using 18integer Smith normal form. This is an abelian group. 19\end{itemize} 20I have put a fuller explanation of this code here: 21\url{http://www.euclideanspace.com/prog/scratchpad/mycode/discrete/finiteGroup/presentation/} 22\end{abstract} 23 24\section{Introduction} 25Group represented by its generators and relations. 26Here we use it to hold homotopy group such as fundamental group. 27for more documentation see: 28\url{http://www.euclideanspace.com/prog/scratchpad/mycode/topology/} 29 30Representation holds the group as a set of generators and a set of 31relations 32Each generator is a NNI 33Each relation is a list of indexes to generators. Negative values 34indicate the inverse of the generator. So if '1' represents the 35generator 'A' then '-1' represents its inverse 'A^-1'. 36 37Note that the use of negative indices to represent the inverse does 38not imply an abelian group. This is just a convenient way to code 39the representation and, in general, the group is not necessarily 40abelian. 41The notation uses the following conventions. 42\begin{itemize} 43\item If index is positive it represents a generator shown as an 44alphabetic digit followed by number if required. 45\item If index is zero it represents identity shown as 'e'. 46\item If index is negative it represents an inverse generator. 47The notation uses '-' to indicate an inverse generator (I know this is 48an abuse of notation, because the group is not necessarily Abelian). 49\end{itemize} 50This convention is not ambiguous and I don't like the alternatives, 51'-1' exponent uses too much space and upper case alpha for inverses 52may not be clear to people who don't read documentation. 53 54\section{Homotopy Group} 55The homotopy group is finitely presented by generators and relations. 56This representation of a group is not, in general, algorithmically 57computable into other representations of a group. 58 59We can therefore compute 'a' (not 'the') homotopy group for a given 60simplicial complex. We may also be able to apply some simplifications 61to this group. However, in the general case, we cannot determine if 62this is the simplest representation or determine if two such groups 63are isomophic (their corresponding simplicial complexes are 64homeomorphic). 65 66Despite these fundamental limits on what is theoretically possible 67I still believe it is worthwhile to have the capability to generate 68'a' homotopy group for a given structure. 69 70\section{Conversion between Finitely Presented and Permutation Groups} 71 72In FriCAS the main group functionality is in PermutationGroup so it 73is useful to be able to convert to and from it. For conversions to 74PermutationGroup we use a well known algorithm called the 75Todd-Coxeter algorithm. 76 77If you wish to see how the algorithm works (or does not work) try 78calling the function, with trace set to 'true', like this: 79 80\begin{verbatim} 81(7) -> d3 := dihedralGroup(3)$GroupPresentation 82 83 (7) <a b | a*a*a, b*b, a*b*a*b> 84 Type: GroupPresentation 85(8) -> toPermutationIfCan(d3,true) 86 87 addPoint: cannot deduce more so adding a point 88 adding:1 at row:1 89 +2 2 2+ +0 0+ +2 0 2 0+ 90 relatorTables=[| |,| |,| |] 91 +0 0 0+ +0 0+ +0 0 0 0+ 92 addPoint: cannot deduce more so adding a point 93 adding:2 at row:1 94 +2 2 2+ +3 3+ +2 3 2 3+ 95 | | | | | | 96 relatorTables=[|0 0 0|,|0 0|,|0 0 0 0|] 97 | | | | | | 98 +0 0 0+ +0 0+ +0 0 0 0+ 99 inferFromRelations found a gap of 1 so deduction made 100 gap is in relator table:[2,2] 101 distance from start:1 from end:0 102 row at start:1 103 row to change:3 new value:1 104 generator index=2 invm=false 105 forwardSequence:[1,3] backwardSequence:[1,0] 106 inferFromRelations genIn=2 gb=1 107 +2 2 2+ +3 3+ +2 3 2 3+ 108 | | | | | | 109 relatorTables=[|0 0 0|,|0 0|,|0 0 0 0|] 110 | | | | | | 111 +0 0 0+ +1 1+ +0 1 0 1+ 112 addPoint: cannot deduce more so adding a point 113 adding:1 at row:2 114 +2 2 2+ +3 3+ +2 3 2 3+ 115 | | | | | | 116 |4 4 4| |0 0| |4 0 4 0| 117 relatorTables=[| |,| |,| |] 118 |0 0 0| |1 1| |0 1 0 1| 119 | | | | | | 120 +0 0 0+ +0 0+ +0 0 0 0+ 121 inferFromRelations found a gap of 1 so deduction made 122 gap is in relator table:[1,1,1] 123 distance from start:2 from end:0 124 row at start:1 125 row to change:4 new value:1 126 generator index=1 invm=false 127 forwardSequence:[1,2,4] backwardSequence:[1,0,0] 128 inferFromRelations genIn=1 gb=2 129 +2 2 2+ +3 3+ +2 3 2 3+ 130 | | | | | | 131 |4 4 4| |0 0| |4 0 4 0| 132 relatorTables=[| |,| |,| |] 133 |0 0 0| |1 1| |0 1 0 1| 134 | | | | | | 135 +1 1 1+ +0 0+ +1 0 1 0+ 136 addPoint: cannot deduce more so adding a point 137 adding:2 at row:2 138 +2 2 2+ +3 3+ +2 3 2 3+ 139 | | | | | | 140 |4 4 4| |5 5| |4 5 4 5| 141 | | | | | | 142 relatorTables=[|0 0 0|,|1 1|,|0 1 0 1|] 143 | | | | | | 144 |1 1 1| |0 0| |1 0 1 0| 145 | | | | | | 146 +0 0 0+ +0 0+ +0 0 0 0+ 147 inferFromRelations found a gap of 1 so deduction made 148 gap is in relator table:[2,2] 149 distance from start:1 from end:0 150 row at start:2 151 row to change:5 new value:2 152 generator index=2 invm=false 153 forwardSequence:[2,5] backwardSequence:[2,0] 154 inferFromRelations genIn=2 gb=1 155 +2 2 2+ +3 3+ +2 3 2 3+ 156 | | | | | | 157 |4 4 4| |5 5| |4 5 4 5| 158 | | | | | | 159 relatorTables=[|0 0 0|,|1 1|,|0 1 0 1|] 160 | | | | | | 161 |1 1 1| |0 0| |1 0 1 0| 162 | | | | | | 163 +0 0 0+ +2 2+ +0 2 0 2+ 164 inferFromRelations found a gap of 1 so deduction made 165 gap is in relator table:[1,2,1,2] 166 distance from start:2 from end:1 167 row at start:1 168 row to change:5 new value:3 169 generator index=1 invm=false 170 forwardSequence:[1,2,5,0] backwardSequence:[1,3,0,0] 171 inferFromRelations genIn=1 gb=2 172 +2 2 2+ +3 3+ +2 3 2 3+ 173 | | | | | | 174 |4 4 4| |5 5| |4 5 4 5| 175 | | | | | | 176 relatorTables=[|0 0 0|,|1 1|,|0 1 0 1|] 177 | | | | | | 178 |1 1 1| |0 0| |1 0 1 0| 179 | | | | | | 180 +3 3 3+ +2 2+ +3 2 3 2+ 181 addPoint: cannot deduce more so adding a point 182 adding:1 at row:3 183 +2 2 2+ +3 3+ +2 3 2 3+ 184 | | | | | | 185 |4 4 4| |5 5| |4 5 4 5| 186 | | | | | | 187 |6 6 6| |1 1| |6 1 6 1| 188 relatorTables=[| |,| |,| |] 189 |1 1 1| |0 0| |1 0 1 0| 190 | | | | | | 191 |3 3 3| |2 2| |3 2 3 2| 192 | | | | | | 193 +0 0 0+ +0 0+ +0 0 0 0+ 194 inferFromRelations found a gap of 1 so deduction made 195 gap is in relator table:[1,1,1] 196 distance from start:1 from end:1 197 row at start:3 198 row to change:6 new value:5 199 generator index=1 invm=false 200 forwardSequence:[3,6,0] backwardSequence:[3,5,0] 201 inferFromRelations genIn=1 gb=1 202 +2 2 2+ +3 3+ +2 3 2 3+ 203 | | | | | | 204 |4 4 4| |5 5| |4 5 4 5| 205 | | | | | | 206 |6 6 6| |1 1| |6 1 6 1| 207 relatorTables=[| |,| |,| |] 208 |1 1 1| |0 0| |1 0 1 0| 209 | | | | | | 210 |3 3 3| |2 2| |3 2 3 2| 211 | | | | | | 212 +5 5 5+ +0 0+ +5 0 5 0+ 213 inferFromRelations found a gap of 1 so deduction made 214 gap is in relator table:[1,2,1,2] 215 distance from start:1 from end:2 216 row at start:2 217 row to change:4 new value:6 218 generator index=2 invm=false 219 forwardSequence:[2,4,0,0] backwardSequence:[2,5,6,0] 220 inferFromRelations genIn=2 gb=1 221 +2 2 2+ +3 3+ +2 3 2 3+ 222 | | | | | | 223 |4 4 4| |5 5| |4 5 4 5| 224 | | | | | | 225 |6 6 6| |1 1| |6 1 6 1| 226 relatorTables=[| |,| |,| |] 227 |1 1 1| |6 6| |1 6 1 6| 228 | | | | | | 229 |3 3 3| |2 2| |3 2 3 2| 230 | | | | | | 231 +5 5 5+ +0 0+ +5 0 5 0+ 232 inferFromRelations found a gap of 1 so deduction made 233 gap is in relator table:[2,2] 234 distance from start:1 from end:0 235 row at start:4 236 row to change:6 new value:4 237 generator index=2 invm=false 238 forwardSequence:[4,6] backwardSequence:[4,0] 239 inferFromRelations genIn=2 gb=1 240 +2 2 2+ +3 3+ +2 3 2 3+ 241 | | | | | | 242 |4 4 4| |5 5| |4 5 4 5| 243 | | | | | | 244 |6 6 6| |1 1| |6 1 6 1| 245 relatorTables=[| |,| |,| |] 246 |1 1 1| |6 6| |1 6 1 6| 247 | | | | | | 248 |3 3 3| |2 2| |3 2 3 2| 249 | | | | | | 250 +5 5 5+ +4 4+ +5 4 5 4+ 251 252 (8) <(1 2 4)(3 6 5),(1 3)(2 5)(4 6)> 253 Type: Union(PermutationGroup(Integer),...) 254\end{verbatim} 255 256This will display the relatorTables at each stage and the deductions 257being made from the tables. 258 259The conversions in both directions can be improved by implementing 260better simplifications but since there is no canonical form the 261simplifications can never be perfect. The Todd-Coxeter does not yet 262detect and remove 'coincidences', that is, duplicated points. So 263this in the next improvement that needs to be made. 264 265\section{Direct Product of Groups} 266 267If G = < Sg | Rg > and H = < Sh | Rh > 268Then G*H = < Sg,Sh | Rg,Rh,Rp > 269 270where: 271G*H is the direct product of G and H. 272Rp is a set of relations specifying that each element of Sg 273anti-commutes with each element of Sh. 274See: 275\url{https://en.wikipedia.org/wiki/Direct_product_of_groups} 276 277This assumes that Sg and Sh are disjoint. In order to assure this the 278generators will be renumbered before doing the product. 279 280\section{Quotients} 281 282We can generate a quotient by removing a generator (more precisely 283adding relation equating this generator to neutral element) or 284more generaly by adding a relation. 285 286A quotient is an example of a surjective mapping 287(epimorphism) on the group. It is easy to work with functions 288between finitely presented groups, all we have to do is map 289the generators and check that the relations still equal 1. 290 291\section{Simplify Finitely Presented Groups} 292 293There may not be a simplest form but it is possible to do some 294simplifications. 295 296In order to try to simplify a finitely generated presentation 297to produce simpler but isomorphic groups we can apply certain 298transformations or automorphisms (isomorphisms of the group 299back to itself). 300 301For example: 302\begin{itemize} 303\item Remove all zero terms in relations. 304\item If a relation consists of a single generator then remove 305 that generator. 306\item If a relation consists of a pair of generators then make 307 the second generator the inverse of the first. 308\item If a generator is adjacent to its inverse then cancel 309 them out. 310\item Remove duplicate relations. 311\item Substitute one relation in another. 312\end{itemize} 313 314These automorphisms were studied and categorised by Tietze 315and Nielsen. 316 317\subsection{Tietze Transformations} 318 319\begin{table}[] 320\label{Tietze transformations are of 4 kinds} 321\begin{tabular}{lll} 322 \ Kind \ Examples \\ 323T1 \ Add a relation \ < A | A^3 > -> < A | A^3 , A^6 > \\ 324T2 \ Remove a relation \ for example we can reverse the above 325< A | A^3 , A^6> -> < A | A^3> \\ 326T3 \ Add a generator \ < A | A^3 > -> <A , B | A^3, B = A^2 > \\ 327T4 \ Remove a generator \ for example we can reverse the above 328<A , B | A^3, B = A^2 > -> < A | A^3 > \\ 329\end{tabular} 330\end{table} 331We are interested in simplifying so we are mostly interested 332in T2 and T4. 333\subsection{T2} 334 335T2 allows us to remove a relation but not generators. This 336happens when a relation is redundant, that is it contains no 337additional information than is already contained in the 338other relations. 339 340This happens, for example, where: 341 342One relation is a multiple of another - In this case we can 343remove the highest multiple but not the lowest. 344 345One relation is the inverse of another - In this case we can 346remove any one, but not both. 347 348We can also simplify relations, for example, where an element 349and its inverse are next to each other they can be 350canceled out and removed. 351\subsection{T4} 352 353T4 allows us to remove a generator and corresponding relations. 354\subsection{Nielsen Transformations} 355 356The following transformations on a finitely generated free group 357produce isomorphic groups. 358 359\begin{itemize} 360\item Switch A and B 361\item Cyclically permute A, B, ... to B, ..., A. 362\item Replace A with A^(-1) 363\item Replace A with A*B 364\item Substitute one relation in another 365\end{itemize} 366 367Most of these rules are self explanatory except substitute which 368does the following: 369 370If a generator is contained in exactly 2 relations then we may be 371able to substitute one relation in another and remove that generator. 372If, in at least one of these relations, the generator is contained 373only once then we can move it to one side of the equation and 374substitute it in the other relation. 375 376This is done by a local function TTSubstitute. 377 378Here is an example of its use from SimplicialComplex without 379substitution: 380\begin{verbatim} 381(1) -> tS := torusSurface()$SimplicialComplexFactory 382 383 (1) 384 (1,2,3) 385 (2,3,5) 386 (2,4,5) 387 (2,4,7) 388 (1,2,6) 389 (2,6,7) 390 (3,4,6) 391 (3,5,6) 392 (3,4,7) 393 (1,3,7) 394 (1,4,5) 395 (1,4,6) 396 (5,6,7) 397 (1,5,7) 398 Type: FiniteSimplicialComplex(VertexSetAbstract) 399 400(2) -> fundamentalGroup(tS) 401 402 (2) <o t w | o*w*t, o*t*w> 403 Type: GroupPresentation 404\end{verbatim} 405This needs to be further simplified, 406 407<o t w | -o = w*t, -o = t*w> 408 409Substituting for -o we have: 410 411w*t = t*w 412 413That is, two edges that commute. 414 415Moving everything to one side of the equation we have: 416t * w * -t * -w 417\begin{verbatim} 418(2) -> fundamentalGroup(tS) 419 420 (2) <s v | -s*v*s*-v> 421 Type: GroupPresentation 422\end{verbatim} 423This is the same as above with v=w and s= -t. 424 425\section{Testing and Validating this Code} 426 427Some functions are very difficult to test, for example in 428the SimplicialComplex code here: 429\url{http://www.euclideanspace.com/prog/scratchpad/mycode/topology/simplex/} 430and here: 431\url{http://www.euclideanspace.com/prog/scratchpad/mycode/topology/delta/} 432there are functions such as fundamentalGroup which output a 433GroupPresentation. The reason for the difficulty is that they 434do not have a canonical form, that is, there may 435be more than one correct result and none of them are better 436than the others and there is no general algorithm for testing 437if they are equal. 438 439So some change to the code may change the result but the result 440may be just as correct as the other result. So testing that 441fundamentalGroup generates a given output for a given input 442is not a useful test for correctness. 443 444I think that all we can do in this situation is to test 445fundamentalGroup with very simple inputs such as a 446topological sphere. This should always produce an empty 447presentation. 448)endif 449 450)abbrev domain GROUPP GroupPresentation 451++ Author: Martin Baker 452++ Description: 453++ Group represented by its generators and relations. 454++ Here we use it to hold homotopy group such as fundamental group. 455++ for more documentation see: 456++ http://www.euclideanspace.com/prog/scratchpad/mycode/discrete/finiteGroup/presentation/ 457++ Date Created: Jan 2016 458++ Basic Operations: 459++ Related packages: 460++ Related categories: 461++ Related Domains: PermutationGroup 462++ Also See: 463++ AMS Classifications: 464++ Keywords: 465++ Examples: 466++ References: 467 468GroupPresentation() : Exports == Impl where 469 NNI ==> NonNegativeInteger 470 PI ==> PositiveInteger 471 x<<y ==> hconcat(x::OutputForm, y::OutputForm) 472 GENMAP ==> List(Record(OldGen : NNI, NewGen : NNI)) 473 Exports ==> SetCategory() with 474 groupPresentation : (v : List(NNI), rels1 : List(List(Integer))) -> % 475 ++ construct from generators and relations 476 groupPresentation : (v : List(NNI)) -> % 477 ++ construct free group with generators but no relations 478 groupPresentation : () -> % 479 ++ construct trivial group with no generators or relations 480 simplify : (s : %) -> % 481 ++ There may not be a simplest form but it is possible to 482 ++ do some simplifications as follows: 483 ++ 1. Remove all zero terms in relations. 484 ++ 2. If a relation consists of a single generator then remove 485 ++ that generator. 486 ++ 3. If a relation consists of a pair of generators then make the 487 ++ second generator the inverse of the first. 488 ++ 4. If a generator is adjacent to its inverse then cancel them out. 489 ++ 5. Remove duplicate relations. 490 ++ 6. Substitute one relation in another. 491 simplify : (s : %, trace : Boolean) -> % 492 ++ simplify with option to trace 493 refactor : (a : %) -> % 494 ++ actual value of generators is not important, it is only important that 495 ++ they correspond to the appropriate entries in the relations. 496 ++ Therefore we can refactor the generators without changing the 497 ++ group represented. 498 quotient : (a : %, remgen : List(NNI)) -> % 499 ++ take quotient by removing generators specified by remgen 500 quotient : (a : %, addrel : List(List(Integer))) -> % 501 ++ take quotient by adding relations specified by addrel 502 directProduct : (a : %, b : %) -> % 503 ++ directProduct of two groups 504 cyclicGroup : (n : PI) -> % 505 ++ cyclicGroup(n) constructs the cyclic group of order n acting 506 ++ on the integers 1, ..., n. 507 dihedralGroup : (n : PI) -> % 508 ++ dihedralGroup(n) constructs the dihedral group of order 2n 509 ++ acting on integers 1, ..., N. 510 symmetricGroup : (n : PI) -> % 511 ++ symmetricGroup(n) constructs the symmetric group of order n-1. 512 ++ Note: generates all possible relations may not be minimal. 513 toPermutationIfCan : (a : %) -> Union(PermutationGroup Integer, "failed") 514 ++ convert to permutation group return "failed" for infinite groups. 515 ++ For more information about the algorithm see: 516 ++ \url{http://www.euclideanspace.com/prog/scratchpad/mycode/discrete/finiteGroup/pres2perm/} 517 toPermutationIfCan : (a : %, trace : Boolean) 518 -> Union(PermutationGroup Integer, "failed") 519 ++ convert to permutation group return "failed" for infinite groups. 520 ++ For more information about the algorithm see: 521 ++ \url{http://www.euclideanspace.com/prog/scratchpad/mycode/discrete/finiteGroup/pres2perm/} 522 toPermutationIfCan : (a : %, sg : List(List(Integer)), trace : Boolean) 523 -> Union(PermutationGroup Integer, "failed") 524 ++ toPermutationIfCan(a, sg, trace) returns permutation 525 ++ representation of a on cosets of subgroup generate by sg 526 ++ or "failed" if computation exceed resource limit. 527 ++ trace activates debugging printouts. 528 529 Impl ==> add 530 531 -- Representation holds the group as a set of generators and a set of 532 -- relations. 533 -- Each generator is a NNI 534 -- Each relation is a list of indexes to generators. 535 -- if index is positive it represents a generator output as an 536 -- alphabetic digit followed by number if required. 537 -- if index is zero it represents identity output as 'e'. 538 -- if index is negative it represents an inverse generator. 539 540 Rep := Record(gens : PrimitiveArray(NNI), rels : List(List(Integer))) 541 542 -- construct from generators and relations 543 groupPresentation(gens1 : List(NNI), rels1 : List(List(Integer))) : % == 544 -- print(" groupPresentation construct (" << gens1 << ", " 545 -- << rels1<< ")") 546 g := construct(gens1)$PrimitiveArray(NNI) 547 --print("groupPresentation constuct : " << rels1) 548 -- remove empty relations since this simplifies equality function 549 [g, [r for r in rels1 | not(empty?(r))]] 550 551 -- construct free group with generators but no relations 552 groupPresentation(gens1 : List(NNI)) : % == 553 -- print(" groupPresentation construct (" << gens1 << ", " 554 -- << rels1<< ")") 555 g := construct(gens1)$PrimitiveArray(NNI) 556 rels2 := []$List(List(Integer)) 557 [g, rels2] 558 559 -- construct trivial group with no generators or relations 560 groupPresentation() : % == 561 gens1 := []$List(NNI) 562 rels1 := []$List(List(Integer)) 563 groupPresentation(gens1, rels1) 564 565 -- Local function used by refactor to map a given generator in a relation. 566 mapGen(a : Integer, ms : GENMAP) : Integer == 567 for m in ms repeat 568 if abs(a) = m.OldGen then return m.NewGen 569 if abs(a) = -m.OldGen then return -m.NewGen 570 error concat(["cant map ", string(a), " in refactor"]) 571 a 572 573 -- Actual value of generators is not important, it is only important that 574 -- they correspond to the appropriate entries in the relations. 575 -- Therefore we can refactor the generators (to be ascending integers 576 -- starting as 1) without changing the group represented. 577 refactor(a : %) : % == 578 -- first generate a map from existing generators to new generators 579 gms : GENMAP := empty()$GENMAP 580 for g in entries(a.gens) for gn in 1..(#(a.gens)) repeat 581 gm : Record(OldGen : NNI, NewGen : NNI) := [g, gn] 582 gms := concat(gms, gm) 583 -- now use this map to change elements of relations 584 rels1 := []$List(List(Integer)) 585 for rel in a.rels repeat 586 newRel : List(Integer) := empty()$List(Integer) 587 for ele in rel repeat 588 newEle : Integer := mapGen(ele, gms) 589 newRel := concat(newRel, newEle) 590 rels1 := concat(rels1, newRel) 591 gens1 : List(NNI) := [gn for gn in 1..(#(a.gens))] 592 groupPresentation(gens1, rels1) 593 594 -- Isomorphism is the most useful level of 'equality' for 595 -- groups but unfortunately this is not computable in 596 -- the general case for presentations. 597 -- Although exact equality is less useful it is still useful to 598 -- compare very simple presentations in the validation code which 599 -- is useful to give some level of confidence that the 600 -- correct presentation was generated. 601 -- TODO result can be dependent on initial generator order, for 602 -- example <a, b | a*a, b*b*b> = <b, a | a*a, b*b*b> would be false 603 -- should really check all permutations of generators and return 604 -- true if any of them gives equality. 605 _=(a : %, b : %) : Boolean == 606 ar : % := refactor(a) 607 br : % := refactor(b) 608 ags : List(NNI) := entries(ar.gens) 609 bgs : List(NNI) := entries(br.gens) 610 if set(ags)$Set(NNI) ~= set(bgs)$Set(NNI) then return false 611 ars : List(List(Integer)) := entries(ar.rels) 612 brs : List(List(Integer)) := entries(br.rels) 613 set(ars)$Set(List(Integer)) = set(brs)$Set(List(Integer)) 614 615 -- Display generators as alphabetic digits 616 -- Local function used by coerce to OutputForm and other functions. 617 -- if i2 is positive it represents a generator shown as an 618 -- alphabetic digit followed by number if required. 619 -- if i2 is zero it represents identity shown as 'e'. 620 -- if i2 is negative it represents an inverse generator. 621 -- The notation uses '-' to indicate an inverse generator (I know 622 -- this is an abuse of notation, because the group is not 623 -- necessarily Abelian). I don't like the alternatives, 624 -- '-1' exponent uses too much space and upper case for inverses 625 -- may not be clear to people who don't read documentation. 626 outputGen(i2 : Integer) : OutputForm == 627 (suffix, i) := divide(abs(i2), 25) 628 letters : String := "eabcdfghijklmnopqrstuvwxyz" 629 n : OutputForm := (letters(i + 1))::OutputForm 630 -- print(" groupPresentation outputGen(" << i2 << 631 -- ") gives " << n) 632 if suffix > 0 then n := hconcat(n, outputForm(suffix + 1)) 633 if i2 < 0 then return hconcat(message"-", n) 634 n 635 636 -- display a relation using alphabetic digits 637 outputRel(r : List(Integer)) : OutputForm == 638 eleout : OutputForm := message("") 639 seperator : OutputForm := message(" ") 640 for ele in r repeat 641 newterm : OutputForm := outputGen(ele) 642 eleout := hconcat([eleout, seperator, newterm])$OutputForm 643 seperator := message("*") 644 eleout 645 646 -- display a list of relations using alphabetic digits 647 outputRelList(i2 : List(List(Integer))) : OutputForm == 648 rels1 : List(OutputForm) := []$List(OutputForm) 649 for r in i2 repeat 650 rels1 := concat(rels1,outputRel(r)) 651 if #rels1 > 0 then return commaSeparate(rels1) 652 message(" ") 653 654 -- display a list of generators using alphabetic digits 655 outputGenList(ps : List(NNI)) : OutputForm == 656 gens1 : List(OutputForm) := []$List(OutputForm) 657 for p in ps repeat 658 gens1 := concat(gens1, outputGen(p::Integer)) 659 if #gens1 > 0 then return blankSeparate(gens1) 660 message(" ") 661 662 -- local function to return indexes to each relation containing a given 663 -- generator. 664 indexesOfRelUsingGen(s : %, gen : NNI) : List(NNI) == 665 res : List(NNI) := [] 666 r : List(List(Integer)) := s.rels 667 for rel in r for reln in 1..(#r) repeat 668 if member?(gen::Integer,rel) then res := concat(res,reln) 669 if gen > 0 and member?(-(gen::Integer),rel) 670 then res := concat(res,reln) 671 res 672 673 -- local function to remove generator 'val' from generators 674 removeGen(gens1 : PrimitiveArray(NNI), val : NNI) : PrimitiveArray(NNI) == 675 remove(val, gens1) 676 677 -- local function to remove generator 'val' from relations 678 removeGen2(rels1 : List(List(Integer)), val : NNI) : List(List(Integer)) == 679 [remove(-val, remove(val::Integer, rel)) for rel in rels1] 680 681 -- local function to replace generator 'val1' with 'val2' 682 -- in relations 683 replaceGen(rels1 : List(List(Integer)), val1 : NNI, val2 : Integer 684 ) : List(List(Integer)) == 685 --print(" groupPresentation replaceGen=" << rels1 << _ 686 -- " val1=" << val1 << " val2=" << val2) 687 rels2 := []$List(List(Integer)) 688 for rel in rels1 repeat 689 rel2 := []$List(Integer) 690 for ele in rel repeat 691 e : Integer := abs(ele) 692 if e = val1 then e := val2 693 if ele < 0 then e := -e 694 rel2 := concat(rel2, e) 695 rels2 := concat(rels2, rel2) 696 rels2 697 698 -- Tietze Transformation to remove a generator that is equal to 699 -- the identity element. That is there is a relation containing only one 700 -- generator. 701 -- This procedure searches for a single element relation, if found, it 702 -- removes the corresponding generator and also removes it from 703 -- any relations containing it. 704 -- This procedure only removes one generator, if there are several 705 -- such relations then this procedure needs to be called several times. 706 -- This is a local function used by simplify. 707 TTRemoveGeneratorIfIdentity(s : %, trace : Boolean) : % == 708 gens1 : PrimitiveArray(NNI) := s.gens 709 rels1 : List(List(Integer)) := s.rels 710 toBeRemoved : NNI := 0 711 for rel in rels1 repeat 712 if #rel = 1 and toBeRemoved = 0 then 713 toBeRemoved := qcoerce(abs(first(rel))) 714 if toBeRemoved = 0 then return s 715 if trace then 716 print hconcat([message("simplify: generator '"), _ 717 outputGen(toBeRemoved), _ 718 message("' is identity so remove it")]) 719 gens1 := removeGen(gens1, toBeRemoved) 720 rels1 := removeGen2(rels1, toBeRemoved) 721 if trace then print outputRelList(rels1) 722 [gens1, rels1] 723 724 -- Tietze Transformation to rename a generator. 725 -- If a relation consists of a pair of generators then make the 726 -- second generator the inverse of the first. 727 -- This procedure searches for a two element relation, if found, it 728 -- replaces the second element with the inverse of the first. 729 -- This procedure only replaces one generator, if there are several 730 -- such relations then this procedure needs to be called several times. 731 -- This is a local function used by simplify. 732 TTRenameGenerator(s : %, trace : Boolean) : % == 733 gens1 : PrimitiveArray(NNI) := s.gens 734 rels1 : List(List(Integer)) := s.rels 735 replaceFrom : NNI := 0 736 replaceTo : Integer := 0 737 for rel in rels1 repeat 738 if #rel = 2 and replaceFrom = 0 then 739 replaceTo := second(rel) 740 replaceFrom := qcoerce(abs(first(rel))) 741 if first(rel) > 0 then replaceTo := -replaceTo 742 -- don't replace an element with itself or its inverse 743 if replaceFrom = abs(replaceTo) then replaceFrom := 0 744 if replaceFrom=0 then return s 745 if trace then 746 print hconcat([message("simplify: generator '"), _ 747 outputGen(replaceFrom), _ 748 message("' is replaced by '"), _ 749 outputGen(replaceTo), _ 750 message("'")]) 751 gens1 := removeGen(gens1, replaceFrom) 752 rels1 := replaceGen(rels1, replaceFrom, replaceTo) 753 if trace then print outputRelList(rels1) 754 [gens1, rels1] 755 756 -- This is a local function used by simplify. 757 TTRemoveEmpty(s : %, trace : Boolean) : % == 758 gens1 : PrimitiveArray(NNI) := s.gens 759 rels1 : List(List(Integer)) := s.rels 760 rels2 : List(List(Integer)) := empty()$List(List(Integer)) 761 for rel in rels1 repeat 762 --print(" groupPresentation simplify rel=" << rel) 763 if not empty?(rel) then 764 rels2 := concat(rels2, rel) 765 [gens1, rels2] 766 767 -- This is a local function used by simplify. 768 TTRemoveZero(s : %, trace : Boolean) : % == 769 gens1 : PrimitiveArray(NNI) := s.gens 770 rels1 : List(List(Integer)) := s.rels 771 gens1 := removeGen(gens1, 0) 772 rels1 := removeGen2(rels1, 0) 773 [gens1, rels1] 774 775 776 -- This is a local function used by simplify. 777 TTRemoveEleTimesInverse(s : %, trace : Boolean) : % == 778 gens1 : PrimitiveArray(NNI) := s.gens 779 rels1 : List(List(Integer)) := s.rels 780 --print("TTRemoveEleTimesInverse relations in =" << rels1) 781 rels2 : List(List(Integer)) := empty()$List(List(Integer)) 782 changed : Boolean := false 783 for rel in rels1 repeat 784 --print("TTRemoveEleTimesInverse rel=" << rel) 785 rel2 : List(Integer) := empty()$List(Integer) 786 lastele : Integer := 0 787 for ele in rel repeat 788 if abs(ele) = abs(lastele) and sign(ele) ~= sign(lastele) then 789 if trace then print hconcat([_ 790 message("simplify: generator '"), _ 791 outputGen(ele), _ 792 message("' is adjacent to its inverse")]) 793 changed := true 794 lastele := 0 795 else 796 if lastele ~= 0 then rel2 := concat(rel2, lastele) 797 lastele := ele 798 if lastele ~= 0 then rel2 := concat(rel2, lastele) 799 if not empty?(rel2) then rels2 := concat(rels2, rel2) 800 if trace and changed then print outputRelList(rels2) 801 [gens1, rels2] 802 803 -- local function to invert relation. Used by TTSubstitute, 804 -- TTMinimiseInverses and relationEquivalent. 805 -- We invert each element and then reverse the order. 806 -- A bit like De Morgan's laws 807 invertRelation(relationIn : List(Integer)) : List(Integer) == 808 relationOut := []$List(Integer) 809 for ele in relationIn repeat 810 relationOut := concat(-ele, relationOut) 811 relationOut 812 813 -- local function to cycle relation. Used by relationEquivalent. 814 -- The effect of a relation is not changed by cycling 815 cycleRelation(relationIn : List(Integer)) : List(Integer) == 816 relationOut : List(Integer) := concat(relationIn.rest,relationIn.first) 817 --print(message "cycleRelation " << relationIn << message " to " << relationOut) 818 relationOut 819 820 -- Local function to test equivalence of two relations. 821 -- Used by TTRemoveDuplicateRelation. 822 -- Relations are considered equivalent if they are identical or 823 -- if they are the same after being cycled or if they are the 824 -- same after being inverted. 825 relationEquivalent(relA : List(Integer),relB : List(Integer)) : Boolean == 826 -- first filter out cases where relations are different lengths 827 if #relA ~= #relB then return false 828 -- test for equality 829 if relA = relB then return true 830 -- test for equality with inverted. 831 if relA = invertRelation(relB) then return true 832 -- test for equality with cycle 833 relBCycle : List(Integer) := copy relB 834 for n in 1..(#relA) repeat 835 relBCycle := cycleRelation(relBCycle) 836 if relA = relBCycle then return true 837 if relA = invertRelation(relBCycle) then return true 838 false 839 840 -- This is a local function used by simplify. 841 -- It looks for and removes any duplicated relations. 842 -- Relations are considered duplicates if they are identical or 843 -- if they are the same after being cycled or if they are the 844 -- same after being inverted. 845 TTRemoveDuplicateRelation(s : %, trace : Boolean) : % == 846 gens1 : PrimitiveArray(NNI) := s.gens 847 rels1 : List(List(Integer)) := s.rels 848 rels2 := []$List(List(Integer)) 849 --print(message "TTRemoveDuplicateRelation =" << rels1) 850 for rela in rels1 for nrela in 1..(#rels1) repeat 851 -- include relation 852 include : Boolean := true 853 for relb in rels1 for nrelb in 1..(#rels1) repeat 854 if nrela > nrelb then 855 if relationEquivalent(rela,relb) then 856 include : Boolean := false 857 if trace then 858 m ==> "TTRemoveDuplicateRelation duplicate found " 859 print(message m << rela << message "=" << relb) 860 if include then 861 rels2 := concat(rels2, rela) 862 [gens1, rels2] 863 864 -- This is a local function used by simplify. 865 -- If a relation contains more inverted elements that non-inverted 866 -- elements then it is easier to read if we invert all the terms. 867 TTMinimiseInverses(s : %, trace : Boolean) : % == 868 gens1 : PrimitiveArray(NNI) := s.gens 869 rels1 : List(List(Integer)) := s.rels 870 rels2 := []$List(List(Integer)) 871 for rel in rels1 repeat 872 numInverts : NNI := 0 873 numNonInverts : NNI := 0 874 for ele in rel repeat 875 if ele < 0 then 876 numInverts := numInverts + 1 877 else 878 numNonInverts := numNonInverts + 1 879 if numInverts > numNonInverts then 880 rels2 := concat(rels2, invertRelation(rel)) 881 else 882 rels2 := concat(rels2, rel) 883 [gens1, rels2] 884 885 -- This is a local function used by TTSubstitute. 886 -- Counts the number of times a generator (or its inverse) occurs 887 -- in a relation. 888 generatorOccurrences(rel : List(Integer),gen : NNI) : NNI == 889 res : NNI := 0 890 for g in rel repeat 891 if g = gen then res := res + 1 892 if gen > 0 and g = -gen then res := res + 1 893 res 894 895 -- local function to remove relations containing given generator 896 removeRelations(rels1 : List(List(Integer)), val : NNI 897 ) : List(List(Integer)) == 898 res : List(List(Integer)) := []$List(List(Integer)) 899 for rel in rels1 repeat 900 if (not member?(val,rel)) and (not member?(-val,rel))then 901 res := concat(res,rel) 902 res 903 904 -- This is a local function used by simplify. 905 -- If a generator is contained in exactly 2 relations then we may be 906 -- able to substitute one relation in another and remove that generator. 907 -- If, in at least one of these relations, the generator is contained 908 -- only once then we can move it to one side of the equation and 909 -- substitute it in the other relation. 910 TTSubstitute(s : %, trace : Boolean) : % == 911 gs : List(NNI) := entries(s.gens) 912 rs : List(List(Integer)) := s.rels 913 r1 : List(Integer) := [] 914 r2 : List(Integer) := [] 915 n1 : NNI := 0 916 n2 : NNI := 0 917 genToBeRemoved : NNI := 0 918 for g in gs repeat 919 indexes : List(NNI) := indexesOfRelUsingGen(s, g) 920 if #indexes = 2 and genToBeRemoved=0 then 921 -- we have a candidate for substitution but, to be 922 -- sure generator must occur once in a relation 923 genToBeRemoved := g 924 r1 := rs.(indexes.1) 925 r2 := rs.(indexes.2) 926 n1 := generatorOccurrences(r1,g) 927 n2 := generatorOccurrences(r2,g) 928 if n1 ~= 1::NNI then 929 -- swap first and second relations 930 r3 : List(Integer) := r1 ; n3 : NNI := n1 931 r1 := r2 ; n1 := n2 932 r2 := r3 ; n2 := n3 933 if n1 ~= 1::NNI then 934 genToBeRemoved := 0 935 if n1 ~= 1::NNI then return s 936 -- If we have got to this point then we know a substitution 937 -- is possible. 938 if trace then 939 print(message("simplify: TTSubstitute (") << s << message(")")) 940 print(message("genToBeRemoved=") << outputGen(genToBeRemoved) << _ 941 message(" r1=") << outputRel(r1) << 942 message(" r2=") << outputRel(r2)) 943 print(message("n1=") << n1 << message(" n2=") << n2) 944 restr : List(Integer) := r1 945 prer : List(Integer) := [] 946 found : Boolean := false 947 genInverted : Boolean := false 948 while (not empty?(restr)) and (not found)repeat 949 x : Integer := first(restr) 950 restr := rest(restr) 951 if x=genToBeRemoved or x= -genToBeRemoved 952 then 953 found := true 954 if x<0 then genInverted := true 955 else prer := concat(prer,x) 956 postr : List(Integer) := [] 957 while not empty?(restr) repeat 958 x : Integer := first(restr) 959 restr := rest(restr) 960 postr := concat(postr,x) 961 replacement := concat(invertRelation(prer),invertRelation(postr)) 962 -- now substitute replacement for genToBeRemoved in r2 963 if trace then 964 print(message("we will substitute ") << outputRel(replacement) << 965 message(" for ") << outputGen(genToBeRemoved) << 966 message(" in ") << outputRel(r2)) 967 newRel : List(Integer) := [] 968 for x in r2 repeat 969 if abs(x)=abs(genToBeRemoved) 970 then 971 if genInverted 972 then newRel := concat(newRel,invertRelation(replacement)) 973 else newRel := concat(newRel,replacement) 974 else newRel := concat(newRel,x) 975 if trace then print(message("newRel=") << outputRel(newRel)) 976 gens1 : PrimitiveArray(NNI) := s.gens 977 rels1 : List(List(Integer)) := s.rels 978 gens1 := removeGen(gens1, genToBeRemoved) 979 rels1 := removeRelations(rels1, genToBeRemoved) 980 rels1 := concat(rels1,newRel) 981 if trace then print(message("gens=") << outputGenList(entries(gens1)) 982 << message(" rels=") << outputRelList(rels1)) 983 [gens1, rels1] 984 985 -- true if 'a' is simpler than 'b'. 986 -- There may not be an absolute measure of whether one presentation 987 -- is simpler than another but this procedure is used only in specific 988 -- circumstances, that is where we have attempted to simplify the 989 -- presentation and we want to test if it is actually simpler. 990 -- We do this by testing if the number of generators or relations has 991 -- reduced or if the complexity of the relations has reduced. 992 -- This is a local function used by simplify. 993 isSimpler?(a : %, b : %) : Boolean == 994 gensa : PrimitiveArray(NNI) := a.gens 995 relsa : List(List(Integer)) := a.rels 996 gensb : PrimitiveArray(NNI) := b.gens 997 relsb : List(List(Integer)) := b.rels 998 if #gensa < #gensb then return true 999 if #relsa < #relsb then return true 1000 relationCompleityA : NNI := 0 1001 for rel in relsa repeat 1002 relationCompleityA := relationCompleityA + #rel 1003 relationCompleityB : NNI := 0 1004 for rel in relsb repeat 1005 relationCompleityB := relationCompleityB + #rel 1006 if relationCompleityA < relationCompleityB then return true 1007 false 1008 1009 simplify(s : %) : % == 1010 simplify(s, false) 1011 1012 -- There may not be a simplest form but it is possible to 1013 -- do some simplifications as follows: 1014 -- 1) remove all zero terms in relations 1015 -- 2) if a relation consists of a single generator then remove that 1016 -- generator 1017 -- 3) if a relation consists of a pair of generators then make the 1018 -- second generator the inverse of the first 1019 -- 4) if a generator is adjacent to its inverse then cancel them out. 1020 -- 5) remove duplicate relations 1021 -- 6) Substitute one relation in another 1022 simplify(s : %, trace : Boolean) : % == 1023 if trace then 1024 print(message("simplify(") << s << message(")")) 1025 res : % := s 1026 lastpass : % := s 1027 level : NNI := 0 1028 loopBreaker : NNI := 0 1029 while loopBreaker < 10000 repeat 1030 loopBreaker := loopBreaker + 1 1031 if level=0 then res := TTRemoveEmpty(res, trace) 1032 if level=1 then res := TTRemoveZero(res, trace) 1033 if level=2 then res := TTRemoveGeneratorIfIdentity(res, trace) 1034 if level=3 then res := TTRenameGenerator(res, trace) 1035 if level=4 then res := TTRemoveEleTimesInverse(res, trace) 1036 if level=5 then res := TTRemoveDuplicateRelation(res, trace) 1037 if level=6 then res := TTSubstitute(res, trace) 1038 if level=7 then return TTMinimiseInverses(res, trace) 1039 if isSimpler?(res, lastpass) 1040 then level := 0 1041 else level := level + 1 1042 if trace then 1043 print(message(" level=") << level << _ 1044 message(" loop=") << loopBreaker << _ 1045 message(" res=") << res) 1046 lastpass := res 1047 print(message("simplify excessive time - loop suspected") << s) 1048 res 1049 1050 -- local function used by directProduct to offset indexes 1051 offsetIndexes(a : %, offset : NNI) : % == 1052 ga : List(NNI) := entries(a.gens) 1053 ra : List(List(Integer)) := a.rels 1054 gb := [x+offset for x in ga] 1055 rb := [[(if y > 0 then y + offset else y - offset) for y in z] 1056 for z in ra] 1057 groupPresentation(gb, rb) 1058 1059 -- take quotient by removing generators specified by remgen 1060 quotient(a : %, remgen : List(NNI)) : % == 1061 gens1 : PrimitiveArray(NNI) := a.gens 1062 rels1 : List(List(Integer)) := a.rels 1063 for toBeRemoved in remgen repeat 1064 gens1 := removeGen(gens1, toBeRemoved) 1065 rels1 := removeGen2(rels1, toBeRemoved) 1066 simplify(groupPresentation(entries(gens1), rels1)) 1067 1068 -- take quotient by adding relations specified by addrel 1069 quotient(a : %, addrel : List(List(Integer))) : % == 1070 gens1 : List(NNI) := entries(a.gens) 1071 rels1 : List(List(Integer)) := a.rels 1072 simplify(groupPresentation(entries(gens1), concat(rels1,addrel))) 1073 1074 -- directProduct of two groups 1075 directProduct(a : %, b : %) : % == 1076 a2 : % := refactor(a) 1077 ga : List(NNI) := entries(a2.gens) 1078 ra : List(List(Integer)) := a2.rels 1079 sa : NNI := #ga 1080 b2 : % := offsetIndexes(refactor(b), sa) 1081 gb : List(NNI) := entries(b2.gens) 1082 rb : List(List(Integer)) := b2.rels 1083 rc : List(List(Integer)) := [] 1084 for gax in ga repeat 1085 for gbx in gb repeat 1086 gcx : List(Integer) := [gax::Integer, gbx::Integer, 1087 gax::Integer, gbx::Integer] 1088 rc := concat(rc,gcx) 1089 groupPresentation(concat(entries(ga), gb), concat([ra, rb, rc])) 1090 1091 -- cyclicGroup(n) constructs the cyclic group of order n acting 1092 -- on the integers 1, ..., n. 1093 cyclicGroup(n : PI) : % == 1094 ga : List(NNI) := [1] 1095 ra : List(List(Integer)) := [[1 for x in 1..(n@Integer)]] 1096 groupPresentation(ga, ra) 1097 1098 -- dihedralGroup(n) constructs the dihedral group of order 2n 1099 -- acting on integers 1, ..., n. 1100 dihedralGroup(n : PI) : % == 1101 c1 : % := cyclicGroup(n) 1102 c2 : % := cyclicGroup(2) 1103 directProduct(c1, c2) 1104 1105 -- symmetricGroup(n) constructs the symmetric group of order n-1. 1106 symmetricGroup(n : PI) : % == 1107 if n<2 then return groupPresentation([]) 1108 m : PI := (n-1) :: PI 1109 ga : List(NNI) := [x for x in 1..m] 1110 r : List(List(Integer)) := []$List(List(Integer)) 1111 for a in 1..m repeat 1112 for b in 1..m repeat 1113 if a = b then 1114 -- all generators square to 1 1115 y : List(Integer) := [a,a] 1116 r := cons(y, r) 1117 if a + 1 < b then 1118 -- non squares commute 1119 y : List(Integer) := [a,b,-a,-b] 1120 r := cons(y, r) 1121 if a+1 = b then 1122 -- swapping the ith and (i + 1)th position cubed 1123 y : List(Integer) := [a,b,a,b,a,b] 1124 r := cons(y, r) 1125 groupPresentation(ga, reverse!(r)) 1126 1127 A2D ==> TwoDimensionalArray NNI 1128 A1D ==> OneDimensionalArray NNI 1129 1130 -- TC_state (Todd-Cox State) 1131 -- This holds tables while they are being built up during the 1132 -- Todd-Cox algorithm. Initially the elements of coset tables 1133 -- are set to zero then index values are incrementally 1134 -- derived during the algorithm. When complete the coset table 1135 -- will be used to determine the coset permutations. 1136 -- The components of this state are: 1137 -- coset_table : A 2D array with 1138 -- a row for each point 1139 -- only 'number_of_indices' are used 1140 -- other rows are empty. 1141 -- a column for a generator/coset 1142 -- equiv_table : Tracks coincidences 1143 -- non-coincidences are self loops 1144 -- coincidences are chained to non-coincidences 1145 -- inverse_table : Inverse of generators (not yet used). 1146 -- number_of_generators : Actual number of distinct cosets. 1147 -- So we can compress tables if there are 1148 -- too many coincidences. 1149 -- number_of_indices : allocated rows (may not be used) of 1150 -- coset table. 1151 -- number_of_points : size of set being permuted. 1152 TC_state ==> Record(coset_table : A2D, equiv_table : A1D, 1153 inverse_table : A1D, closed_point : NNI, 1154 number_of_generators : NNI, 1155 number_of_indices : NNI, number_of_points : NNI, 1156 max_number_of_indices : NNI) 1157 1158 -- Local function to print CosetTable 1159 -- Using this avoids displaying empty rows that are not used yet. 1160 outCosetTable(ct : A2D,np : NNI) : OutputForm == 1161 if np < 1 then return ct::OutputForm 1162 if nrows(ct) > np then 1163 part1 : NNI := np 1164 part2 : NNI := subtractIfCan(nrows(ct),np) :: NNI 1165 cts : List(A2D) := vertSplit(ct,[part1,part2]) 1166 ct := cts.1 1167 --return ct::OutputForm << cts.2 1168 ct::OutputForm 1169 1170 -- Local function to print status 1171 -- Using this avoids displaying empty rows that are not used yet. 1172 outStatus(state : TC_state) : OutputForm == 1173 ct : A2D := state.coset_table 1174 np : NNI := state.number_of_indices 1175 outCosetTable(ct,np) 1176 1177 -- Local function to find an index in equiv_table. 1178 -- Parameter information: 1179 -- et = equiv_table 1180 -- ind = index to be found 1181 find(et : A1D, ind : NNI) : NNI == 1182 ind = 0 => ind 1183 qelt(et, ind) = ind => ind 1184 j := ind 1185 -- starting at ind follow pointer until j=pj 1186 pj := 0 1187 while not(j = pj) repeat 1188 pj := j 1189 j := qelt(et, j) 1190 j := ind 1191 -- track compression 1192 while not(j = pj) repeat 1193 nj := qelt(et, j) 1194 qsetelt!(et, j, pj) 1195 j := nj 1196 pj 1197 1198 -- Local function to infer coincidencies 1199 -- Parameter information: 1200 -- ct = coset_table 1201 -- et = equiv_table 1202 -- pb = pointer begin 1203 -- pe = pointer end 1204 infer_coincidencies(ct : A2D, et : A1D, pb : NNI, pe : NNI,_ 1205 trace : Boolean) : Void == 1206 if trace then print(message("coincidence: begin=") << pb _ 1207 << message(" end=") << pe) 1208 if pe < pb then 1209 (pb, pe) := (pe, pb) 1210 qsetelt!(et, pe, pb) 1211 nn := maxColIndex(ct) 1212 for i in 1..nn repeat 1213 i1 := qelt(ct, pb, i) 1214 i2 := qelt(ct, pe, i) 1215 i2 = 0 => "skip" 1216 if i1 = 0 then 1217 qsetelt!(ct, pb, i, i2) 1218 for i in 1..nn repeat 1219 i1 := qelt(ct, pb, i) 1220 i1 = 0 => "skip" 1221 i2 := qelt(ct, pe, i) 1222 i2 = 0 => "skip" 1223 i1 := find(et, i1) 1224 i2 := find(et, i2) 1225 i1 = i2 => "skip" 1226 infer_coincidencies(ct, et, i1, i2, trace) 1227 1228 add_point ==> 1229 if n_ind >= o_size then 1230 n_ind = state.max_number_of_indices => return true 1231 n_size : NNI := 1232 qcoerce(min(2*o_size, state.max_number_of_indices)) 1233 n_ct_cols := maxColIndex(ct) 1234 nct := new(n_size, qcoerce(n_ct_cols), 0)$A2D 1235 net := new(n_size, 0)$A1D 1236 for i in 1..o_size repeat 1237 qsetelt!(net, i, qelt(et, i)) 1238 for j in 1..n_ct_cols repeat 1239 qsetelt!(nct, i, j, qelt(ct, i, j)) 1240 for i in (o_size + 1)..n_size repeat 1241 qsetelt!(net, i, qcoerce(i)) 1242 ct := nct 1243 et := net 1244 o_size := n_size 1245 state.coset_table := ct 1246 state.equiv_table := et 1247 n_ind := n_ind + 1 1248 if trace then 1249 print(message("adding action of ") << add_gen << 1250 message(" on ") << add_to << message(" to be ") 1251 << n_ind) 1252 qsetelt!(ct, add_to, add_gen, n_ind) 1253 add_gen := inv_tab(add_gen) 1254 qsetelt!(ct, n_ind, add_gen, add_to) 1255 if trace then print outStatus(state) 1256 state.number_of_indices := n_ind 1257 1258 1259 -- Local function used by toPermutationIfCan. 1260 -- If we still have gaps (zeroes) in permutations then we may 1261 -- be able to infer a step from the relations. 1262 -- If there is a single step gap then we can use this to fill in 1263 -- information because relations are loops and therefore start and 1264 -- end with the same value. 1265 -- If permutations are changed then we return true. 1266 -- If so permutations is mutated. 1267 -- gensR is called as a Reference in case we need to 1268 -- eliminate duplicate points. 1269 inferFromRelations(state : TC_state, rels : List(List(NNI)), 1270 rrels : List(List(NNI)), rel_lens : List(NNI), 1271 trace : Boolean) : Boolean == 1272 ct := state.coset_table 1273 et := state.equiv_table 1274 n_ind : NNI := state.number_of_indices 1275 inv_tab := state.inverse_table 1276 if trace then print(message "inferFromRelations rels=" << rels) 1277 add_to : NNI := 0 1278 add_gen : Integer := 0 1279 add_gap : Integer := 0 1280 pn := state.closed_point + 1 1281 pn > n_ind => false 1282 state.closed_point := pn 1283 not(qelt(et, pn) = pn) => true 1284 o_size := maxRowIndex(ct) 1285 closed := false 1286 while not(closed) repeat 1287 closed := true 1288 not(qelt(et, pn) = pn) => break 1289 for rel in rels for rrel in rrels for r_len in rel_lens repeat 1290 -- in rel look for gap of length 1 1291 gb : NNI := 0 -- generator index in forward sequence 1292 pb : NNI := pn -- point index in forward sequence 1293 -- how far can we get from beginning 1294 i : NNI := pn 1295 genIn : Integer := 0 1296 for genIndex in rel repeat 1297 genIn := genIndex 1298 i := qelt(ct, i, genIndex) 1299 i = 0 => break 1300 i := find(et, i) 1301 gb := gb + 1 1302 pb := i 1303 gap := r_len - gb 1304 ge : NNI := 0 -- generator index in backward sequence 1305 pe : NNI := pn -- point index in backward sequence 1306 -- how far can we get from end 1307 i : NNI := pn 1308 genInv : Integer := 0 1309 for genIndex in rrel while ge < gap repeat 1310 genInv := genIndex 1311 i := qelt(ct, i, genIndex) 1312 i = 0 => break 1313 i := find(et, i) 1314 ge := ge + 1 1315 pe := i 1316 gap := gap - ge 1317 if gap > 1 then 1318 add_to := pb 1319 add_gen := genIn 1320 add_point 1321 gap := gap - 1 1322 prel := rel 1323 for i in 0..gb repeat 1324 prel := rest(prel) 1325 gb := gb + 1 1326 while gap > 1 repeat 1327 add_to := n_ind 1328 add_gen := first(prel) 1329 prel := rest(prel) 1330 add_point 1331 gap := gap - 1 1332 gb := gb + 1 1333 pb := n_ind 1334 genIn := first(prel) 1335 gap = 1 => 1336 not((npe := qelt(ct, pb, genIn)) = 0) => 1337 npe = pe => "skip" 1338 if trace then 1339 print(message("coincidence: ") << pe << 1340 message(" ") << npe << 1341 message(" rel = ") << rel << 1342 message(" pn = ") << pn) 1343 infer_coincidencies(ct, et, pe, npe, trace) 1344 if trace then 1345 print(message "inferFromRelations genIn=" << genIn << _ 1346 message " gb=" << gb) 1347 not(qelt(inv_tab, genIn) = genInv) => error "impossible 3" 1348 qsetelt!(ct, pb, genIn, pe) 1349 not((npb := qelt(ct, pe, genInv)) = 0) => 1350 npb = pb => "skip" 1351 if trace then 1352 print(message("coincidence: ") << npb << 1353 message(" ") << pb << 1354 message(" rel = ") << rel << 1355 message(" pn = ") << pn) 1356 infer_coincidencies(ct, et, pb, npb, trace) 1357 qsetelt!(ct, pe, genInv, pb) 1358 gap = 0 => 1359 pb = pe => "skip" 1360 -- coincidence 1361 if trace then 1362 print(message("coincidence: ") << pb << message(" ") << 1363 pe << message(" rel = ") << rel << message(" pn = ") 1364 << pn) 1365 -- print(ct::OutputForm) 1366 infer_coincidencies(ct, et, pb, pe, trace) 1367 error "impossible 4" 1368 1369 if not(closed) then 1370 error "impossible 5" 1371 true 1372 1373 -- Local function used by relatorTables. 1374 -- Invert a map that is implemented as a 1D table 1375 invertMap(a : TwoDimensionalArray NNI) : TwoDimensionalArray NNI == 1376 invm : TwoDimensionalArray NNI := new(nrows(a),ncols(a),0) 1377 for x in 1..nrows(a) repeat 1378 i : NNI := elt(a,x,1) 1379 if i ~= 0 then 1380 setelt!(invm,i,1,x) 1381 --print(message "invertMap a=" << a << message " invm=" << invm) 1382 invm 1383 1384 -- Local function to construct relator tables. 1385 -- Although relator tables are used when manually calculating 1386 -- Todd-Cod for computations it seems easier to construct 1387 -- dynamically as required. So this function only used for trace 1388 -- output. 1389 relatorTables(state : TC_state,_ 1390 rels : List(List(Integer))) : List A2D == 1391 ct := state.coset_table 1392 np : NNI := state.number_of_indices 1393 --generators : A2D := deref(gensR) 1394 genLists : List A2D := _ 1395 horizSplit(ct,ncols(ct) :: PositiveInteger) 1396 invGenLists : List A2D := 1397 [invertMap(a) for a in genLists] 1398 relators : List A2D := [] 1399 for r in rels repeat 1400 relator : A2D := new(0,0,0) 1401 fst : Boolean := true 1402 for g in r repeat 1403 gNum : NNI := abs(g) :: NNI 1404 relatorn : A2D := _ 1405 if g>0 then genLists.gNum else invGenLists.gNum 1406 --print(message "relatorTables genLists=" << genLists << _ 1407 -- message " gNum=" << gNum) 1408 if fst 1409 then 1410 relator := relatorn 1411 fst := false 1412 else 1413 relator := horizConcat(relator,relatorn) 1414 relatorTrim := relator 1415 if nrows(relatorTrim) > np then 1416 part1 : NNI := np 1417 part2 : NNI := subtractIfCan(nrows(relatorTrim),np) :: NNI 1418 cts : List(A2D) := vertSplit(relatorTrim,[part1,part2]) 1419 relatorTrim := cts.1 1420 relators := concat(relators,relatorTrim) 1421 relators 1422 1423 -- convert list of generators to PermutationGroup 1424 generators2Permutation(state : TC_state, 1425 trace : Boolean) : PermutationGroup Integer == 1426 ct := state.coset_table 1427 if trace then print(message "generators2Permutation generators=") 1428 n_gens := state.number_of_generators 1429 n_inds := state.number_of_indices 1430 et := state.equiv_table 1431 net := new(n_inds, 0)$A1D 1432 j : SingleInteger := 0 1433 for i in 1..n_inds repeat 1434 not(qelt(et, i) = i) => "skip" 1435 j := j + 1 1436 qsetelt!(net, i, qcoerce(convert(j))) 1437 perm_lists := new(n_gens, empty())$Vector(List(Integer)) 1438 for i in 1..n_inds repeat 1439 not(qelt(et, i) = i) => "skip" 1440 for j in 1..n_gens repeat 1441 kk := qelt(ct, i, j) 1442 kk = 0 => 1443 print(message("i = ") << i << message(" j = ") << 1444 j << message(" ct(i) = ") << row(ct, i)) 1445 error "incomplete coset table" 1446 kk := qelt(net, find(et, kk)) 1447 qsetelt!(perm_lists, j, cons(kk, qelt(perm_lists, j))) 1448 pl : List(Permutation(Integer)) := [] 1449 if trace then print(perm_lists::OutputForm) 1450 for j in 1..n_gens repeat 1451 gl := reverse!(perm_lists(j)) 1452 p := coerceImages(gl)$Permutation(Integer) 1453 pl := cons(p, pl) 1454 pl := reverse!(pl) 1455 permutationGroup(pl) 1456 1457 -- Convert to permutation group. Return "failed" for infinite groups. 1458 toPermutationIfCan(a : %) : Union(PermutationGroup Integer, "failed") == 1459 toPermutationIfCan(a,false) 1460 1461 -- Convert to permutation group. Return "failed" for infinite groups. 1462 -- This function implements the Todd-Coxeter algorithm. 1463 -- For more information about the algorithm see: 1464 -- \url{http://www.euclideanspace.com/prog/scratchpad/mycode/discrete/finiteGroup/pres2perm/} 1465 1466 toPermutationIfCan(a : %,trace : Boolean 1467 ) : Union(PermutationGroup Integer, "failed") == 1468 toPermutationIfCan(a, [], trace) 1469 1470 convert_words(words : List(List(Integer)), inv_tab : A1D 1471 ) : List(List(List(NNI))) == 1472 nwords : List(List(NNI)) := [] 1473 nrwords : List(List(NNI)) := [] 1474 for word in words repeat 1475 nword : List(NNI) := [] 1476 for i in word repeat 1477 gen := 1478 i > 0 => i 1479 inv_tab(-i) 1480 nword := cons(qcoerce(gen)@NNI, nword) 1481 nwords := cons(nword, nwords) 1482 nrwords := cons(reverse!([inv_tab(i) for i in nword]), nrwords) 1483 nwords := reverse!(nwords) 1484 nrwords := reverse!(nrwords) 1485 [nwords, nrwords] 1486 1487 toPermutationIfCan(a : %, sg : List(List(Integer)), trace : Boolean 1488 ) : Union(PermutationGroup Integer, "failed") == 1489 numberPoints : NNI := 1 1490 -- numberPoints is the number of points being permuted. This starts 1491 -- at 1 and increases when required to fill in a gap in relator tables. 1492 gs : List(NNI) := entries(a.gens) 1493 rs : List(List(Integer)) := a.rels 1494 if #gs = 0 and #rs = 0 then 1495 -- if no generators return trivial group 1496 unit : Permutation(Integer) := 1 1497 return permutationGroup([unit]) 1498 if #gs > #rs then 1499 -- if more generators than relations then must be infinite. 1500 return "failed" 1501 numGens : NNI := #gs 1502 ct := new(10, 2*numGens, 0)$A2D 1503 et := new(10, 0)$A1D 1504 for i in 1..10 repeat 1505 qsetelt!(et, i, i) 1506 inv_tab := new(2*numGens, 0)$A1D 1507 for i in 1..numGens repeat 1508 qsetelt!(inv_tab, i, i + numGens) 1509 qsetelt!(inv_tab, i + numGens, i) 1510 (nrels, nrrels) := convert_words(rs, inv_tab) 1511 rel_lens : List(NNI) := [#rel for rel in nrels] 1512 loopLimit : NNI := 5000000 quo numGens 1513 state := [ct, et, inv_tab, 0, numGens, 1, 1, loopLimit]$TC_state 1514 (nsgens, nrsgens) := convert_words(sg, inv_tab) 1515 sgens_lens := [#word for word in nsgens] 1516 dummy := inferFromRelations(state, concat(nsgens, nrels), 1517 concat(nrsgens, nrrels), 1518 concat(sgens_lens, rel_lens), 1519 trace) 1520 -- Permutations will hold a permutation for each generator. This will 1521 -- be built up as we get more information. 1522 while true repeat 1523 changedByDeduction : Boolean := 1524 inferFromRelations(state, nrels, nrrels, rel_lens, trace) 1525 if not(changedByDeduction) then 1526 if trace then 1527 print(message("finished using ") << state.number_of_indices) 1528 return generators2Permutation(state, trace) 1529 if trace then print(message "relatorTables=" << 1530 relatorTables(state,rs)) 1531 state.number_of_indices >= loopLimit => break 1532 "failed" 1533 1534 -- output 1535 coerce(s : %) : OutputForm == 1536 ps : List(NNI) := parts(s.gens) 1537 g : OutputForm := outputGenList(ps) 1538 rs : List(List(Integer)) := s.rels 1539 r : OutputForm := outputRelList(rs) 1540 hconcat([message("<"), g, message(" | "), r, message(">")]) 1541 1542 1543)abbrev package GROUPPF1 GroupPresentationFunctions1 1544GroupPresentationFunctions1(S : SetCategory) : with 1545 convert : (List(S), List(FreeGroup(S))) -> GroupPresentation 1546 ++ convert(lg, lr) builds group presentation from list 1547 ++ of generators \spad{lg} and list of relations \spad{lr}. 1548 == add 1549 1550 convert(lg, lr) == 1551 n := #lg 1552 nlr : List(List(Integer)) := [] 1553 for r in lr repeat 1554 nr : List(Integer) := [] 1555 fr := factors(r) 1556 for t in fr repeat 1557 k := position(t.gen, lg) 1558 k < 1 => error "convert: relation contains generator" 1559 "not in list of generators" 1560 m := t.exp 1561 k := 1562 m < 0 => -k 1563 k 1564 m := abs(m) 1565 for l in 1..m repeat 1566 nr := cons(k, nr) 1567 nlr := cons(reverse!(nr), nlr) 1568 groupPresentation([l for l in 1..n], reverse!(nlr)) 1569 1570)if false 1571\section{Homology} 1572 1573Intended to hold homology which is calculated using integer 1574Smith normal form. This is an abelian group. 1575 1576It would be good if this could be modified to be based on 1577FreeModule by Manuel Bronstein. 1578)endif 1579 1580)abbrev domain HOMOL Homology 1581++ Author: Martin Baker 1582++ Description: 1583++ Intended to hold homology which is calculated using SmithNormalForm: 1584++ http://www.euclideanspace.com/prog/scratchpad/mycode/topology/homology/ 1585++ Date Created: June 2016 1586++ Basic Operations: 1587++ Related packages: 1588++ Related categories: 1589++ Related Domains: FreeModule, FiniteSimplicialComplex 1590++ Also See: 1591++ AMS Classifications: 1592++ Keywords: 1593++ Examples: 1594++ References: 1595 1596Homology() : Exports == Impl where 1597 NNI ==> NonNegativeInteger 1598 GENI ==> Record(vec : Vector(Integer), ord : Integer) 1599 SMNI ==> SmithNormalForm(Integer, _ 1600 Vector(Integer), _ 1601 Vector(Integer), _ 1602 Matrix(Integer)) 1603 SRESI ==> Record(Smith : Matrix(Integer), _ 1604 leftEqMat : Matrix(Integer), _ 1605 rightEqMat : Matrix(Integer)) 1606 x<<y ==> hconcat(x::OutputForm, y::OutputForm) 1607 1608 Exports ==> SetCategory() with 1609 homologyGroup : (AInt : Matrix(Integer), BInt : Matrix(Integer)) -> % 1610 ++ construct from differential over integers 1611 ++ uses method described by Waldek Hebisch here: 1612 ++ https://groups.google.com/forum/?hl=en#!topic/fricas-devel/mLOdQ-fwbO0 1613 homology : (torsionVec : List(List(Integer)), torsionOrd : List(Integer), 1614 free1 : List(List(Integer))) -> % 1615 ++ construct from lists 1616 homology0 : () -> % 1617 ++ construct empty homology, useful in validation code 1618 homologyz : () -> % 1619 ++ construct Z homology, useful in validation code 1620 homologyzz : () -> % 1621 ++ construct Z*Z homology, useful in validation code 1622 homologyc2 : () -> % 1623 ++ construct C2 homology, useful in validation code 1624 homologyzc2 : () -> % 1625 ++ construct Z+C2 homology, useful in validation code 1626 dispGenerators : (s : %) -> OutputForm 1627 ++ more detailed output with generators 1628 1629 Impl ==> add 1630 -- Representation holds torsion as vector+order 1631 Rep := Record(torsionPart : List(GENI), freePart : List(Vector(Integer))) 1632 1633 -- construct from differential over integers 1634 -- AInt is input delta as matrix 1635 -- BInt is output delta as matrix 1636 -- where BInt*AInt = 0 1637 homologyGroup(AInt : Matrix(Integer), BInt : Matrix(Integer)) : % == 1638 -- 1639 -- validate input 1640 -- 1641 --if not empty?(BInt) then 1642 if nrows(AInt) ~= ncols(BInt) then 1643 print(message("homologyGroup validation error - A rows : ") <<_ 1644 nrows(AInt) << message("~= B cols : ") << ncols(BInt)) 1645 else 1646 zero : Matrix(Integer) := zero(nrows(BInt), ncols(AInt)) 1647 if BInt*AInt ~= zero then 1648 print(message("homologyGroup validation error - B*A ~= 0 : ") 1649 << BInt*AInt << message(" ~= 0 : ") << zero) 1650 -- 1651 -- calculate torsion part 1652 -- 1653 res : List(GENI) := empty()$List(GENI) 1654 smit : SRESI := completeSmith(AInt)$SMNI 1655 left : Matrix(Integer) := smit.leftEqMat 1656 m : Matrix(Integer) := smit.Smith 1657 leftNRows : NNI := nrows(left) 1658 mNRows : NNI := nrows(m) 1659 mNCols : NNI := ncols(m) 1660 for nr in 1..leftNRows repeat 1661 r : Vector(Integer) := row(left, nr) 1662 order : Integer := 1::Integer 1663 if nr <= mNRows and nr <= mNCols then 1664 order := elt(m, nr, nr) 1665 order <= 1 => "iterate" 1666 g : GENI := [r, order] 1667 res := concat(res, g) 1668 -- 1669 -- calculate free part 1670 -- 1671 augmented : Matrix(Integer) := vertConcat(transpose(AInt), BInt) 1672 --print("homologyGroup free: augmented=" << augmented) 1673 smitFree : SRESI := completeSmith(augmented)$SMNI 1674 leftFree : Matrix(Integer) := smitFree.leftEqMat 1675 mFree : Matrix(Integer) := smitFree.Smith 1676 n_rows := nrows(mFree) 1677 n_cols := ncols(mFree) 1678 kernelFree := []$List(Vector(Integer)) 1679 for i in 1..n_cols repeat 1680 if i > n_rows or mFree(i, i) = 0 then 1681 v := new(n_cols, 0)$Vector(Integer) 1682 v(i) := 1 1683 kernelFree := cons(smitFree.rightEqMat*v, kernelFree) 1684 [res, reverse!(kernelFree)] 1685 1686 -- construct from lists 1687 homology(torsionVec : List(List(Integer)), torsionOrd : List(Integer), 1688 free1 : List(List(Integer))) : % == 1689 if #torsionVec ~= #torsionOrd then 1690 error "attempt to construct homology with #torsionVec ~= #torsionOrd" 1691 res : List(GENI) := empty()$List(GENI) 1692 for r1 in torsionVec for r2 in torsionOrd repeat 1693 r3 : GENI := [vector(r1), r2] 1694 res := concat(res, r3) 1695 kernelFree : List(Vector(Integer)) := [vector(v) for v in free1] 1696 [res, kernelFree] 1697 1698 -- construct empty homology 1699 homology0() : % == 1700 homology([], [], []) 1701 1702 -- construct Z homology 1703 homologyz() : % == 1704 homology([], [], [[1]]) 1705 1706 -- construct ZZ homology 1707 homologyzz() : % == 1708 homology([], [], [[1, 0], [0, 1]]) 1709 1710 -- construct C2 homology 1711 homologyc2() : % == 1712 homology([[1]], [2], []) 1713 1714 -- construct Z+C2 homology 1715 homologyzc2() : % == 1716 homology([[1, 0]], [2], [[0, 1]]) 1717 1718 -- more detailed output with generators 1719 dispGenerators(s : %) : OutputForm == 1720 res : OutputForm := empty()$OutputForm 1721 s1 := s::Rep 1722 for g in s1.torsionPart repeat 1723 ln := hconcat([message("gen="), (g.vec)::OutputForm, _ 1724 message(" ord="), (g.ord)::OutputForm])$OutputForm 1725 res := vconcat(res, ln) 1726 ln2 := hconcat([message(" free part="), 1727 (s1.freePart)::OutputForm])$OutputForm 1728 res := vconcat(res, ln2) 1729 res 1730 1731 -- equal if same Betti numbers and torsion coefficient 1732 -- This form of equality is useful for validating code. We want to check 1733 -- that generated homology is essentially the same as we are expecting. 1734 _=(a : %, b : %) : Boolean == 1735 --print("homologyGroup torsionPart a : " << a.torsionPart <<_ 1736 -- " torsionPart b : " << b.torsionPart << _ 1737 -- " freePart a : " << a.freePart << _ 1738 -- " numfree a : " << #(a.freePart) << _ 1739 -- " freePart b : " << b.freePart<< _ 1740 -- " numfree b : " << #(b.freePart)) 1741 tora : List(GENI) := a.torsionPart 1742 torb : List(GENI) := b.torsionPart 1743 noTorsionA : Boolean := true 1744 noTorsionB : Boolean := true 1745 for ta in tora repeat 1746 if (ta.ord ~= 0) and (ta.ord ~= 1) then noTorsionA := false 1747 for tb in torb repeat 1748 if (tb.ord ~= 0) and (tb.ord ~= 1) then noTorsionB := false 1749 if noTorsionA ~= noTorsionA then return false 1750 #(a.freePart) = #(b.freePart) 1751 1752 -- output in terms of Z (free) and C (cycles) 1753 -- TODO perhaps this should check if vectors are independant 1754 coerce(s : %) : OutputForm == 1755 res : OutputForm := empty()$OutputForm 1756 firstTermRead : Boolean := false 1757 s1 := s::Rep 1758 --print("homologyGroup torsionPart : " << s1.torsionPart <<_ 1759 -- " freePart : " << s1.freePart) 1760 nFree := #(s1.freePart) 1761 if nFree > 0 then 1762 -- TODO should check for empty list here 1763 res := hconcat(res, message("Z")) 1764 if nFree > 1 then 1765 res := hconcat([res, message("*"), 1766 nFree::OutputForm])$OutputForm 1767 firstTermRead := true 1768 for t in s1.torsionPart repeat 1769 if not (t.ord = 0 or t.ord = 1) then 1770 if firstTermRead then 1771 res := hconcat(res, message("+")) 1772 ln2 := hconcat([message("C"), 1773 (t.ord)::OutputForm])$OutputForm 1774 res := hconcat(res, ln2) 1775 firstTermRead := true 1776 if not firstTermRead then 1777 res := hconcat(res, message("0")) 1778 res 1779 1780--Copyright (c) 2016, Martin J Baker. 1781--All rights reserved. 1782-- 1783--Redistribution and use in source and binary forms, with or without 1784--modification, are permitted provided that the following conditions are 1785--met: 1786-- 1787-- - Redistributions of source code must retain the above copyright 1788-- notice, this list of conditions and the following disclaimer. 1789-- 1790-- - Redistributions in binary form must reproduce the above copyright 1791-- notice, this list of conditions and the following disclaimer in 1792-- the documentation and/or other materials provided with the 1793-- distribution. 1794-- 1795-- - Neither the name of Martin J Baker. nor the 1796-- names of its contributors may be used to endorse or promote products 1797-- derived from this software without specific prior written permission. 1798-- 1799--THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS 1800--IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 1801--TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A 1802--PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER 1803--OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 1804--EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 1805--PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 1806--PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 1807--LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 1808--NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 1809--SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 1810 1811)if false 1812\eject 1813\begin{thebibliography}{99} 1814For more details see: 1815[1] I have put a fuller explanation of this code here: 1816\url{http://www.euclideanspace.com/prog/scratchpad/mycode/discrete/finiteGroup/presentation/} 1817 1818[2] Wikipedia 1819\url{http://https://en.wikipedia.org/wiki/Simplicial_complex/} 1820 1821[3] Finite simplicial complexes in Sage 1822\url{http://doc.sagemath.org/html/en/reference/homology/sage/homology/simplicial_complex.html} 1823 1824[4] Finite simplicial complexes in NPM 1825\url{https://www.npmjs.com/package/simplicial-complex} 1826 1827[5] Simpcomp - a GAP package for working with simplicial complexes 1828\url{https://code.google.com/p/simpcomp/} 1829 1830[6] A Macaulay2 package for working with simplicial complexes 1831\url{http://www.math.uiuc.edu/Macaulay2/doc/Macaulay2-1.8.2/share/doc/Macaulay2/SimplicialComplexes/html} 1832 1833[7] Homology group method described by Waldek Hebisch here: 1834\url{https://groups.google.com/forum/?hl=en#!topic/fricas-devel/mLOdQ-fwbO0} 1835 1836\end{thebibliography} 1837\end{document} 1838)endif 1839