1############################################################################# 2## 3#W CWcomplexThings.gi HAPcryst package Marc Roeder 4## 5## 6 7## 8## 9#Y Copyright (C) 2006 Marc Roeder 10#Y 11#Y This program is free software; you can redistribute it and/or 12#Y modify it under the terms of the GNU General Public License 13#Y as published by the Free Software Foundation; either version 2 14#Y of the License, or (at your option) any later version. 15#Y 16#Y This program is distributed in the hope that it will be useful, 17#Y but WITHOUT ANY WARRANTY; without even the implied warranty of 18#Y MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 19#Y GNU General Public License for more details. 20#Y 21#Y You should have received a copy of the GNU General Public License 22#Y along with this program; if not, write to the Free Software 23#Y Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA 24## 25############################################################################# 26## 27## undirectedBoundary calculates just the cells occuring in the boundary. 28## signs and multiplicities are ignored. 29## 30InstallMethod(UndirectedBoundaryOfFreeZGLetter, 31 [IsHapResolutionRep,IsInt,IsDenseList], 32 function(resolution,dim,cell) 33 if not IsFreeZGLetter(resolution,dim,cell) 34 then 35 Error("invalid letter"); 36 fi; 37 return UndirectedBoundaryOfFreeZGLetterNC(resolution,dim,cell); 38end); 39 40InstallMethod(UndirectedBoundaryOfFreeZGLetterNC, 41 [IsHapResolutionRep,IsInt,IsDenseList], 42 function(resolution,dim,cell) 43 return Set(BoundaryOfFreeZGLetterNC(resolution,dim,cell),i->[AbsInt(i[1]),i[2]]); 44end); 45 46 47 48############################################################################# 49## 50## undirectedBoundary for words 51## 52InstallMethod(UndirectedBoundaryOfFreeZGWord, 53 [IsHapResolutionRep,IsInt,IsDenseList], 54 function(resolution,dim,word) 55 if not IsFreeZGWord(resolution,dim,word) 56 then 57 Error("invalid word"); 58 fi; 59 return UndirectedBoundaryOfFreeZGWordNC(resolution,dim,word); 60end); 61 62InstallMethod(UndirectedBoundaryOfFreeZGWordNC, 63 [IsHapResolutionRep,IsInt,IsDenseList], 64 function(resolution,dim,word) 65 return Union(List(word,cell->UndirectedBoundaryOfFreeZGLetterNC(resolution,dim,cell))); 66end); 67 68 69 70############################################################################# 71## 72## 73InstallMethod(SubspaceListFromWord, 74 [IsHapResolutionRep,IsInt,IsDenseList], 75 function(resolution,dim,word) 76 if not IsFreeZGWord(resolution,dim,word) 77 then 78 Error("<word> is not a valid word"); 79 fi; 80 return SubspaceListFromWordNC(resolution,dim,word); 81end); 82 83InstallMethod(SubspaceListFromWordNC, 84 [IsHapResolutionRep,IsInt,IsDenseList], 85 function(resolution,dim,word) 86 local subspaces, i; 87 subspaces:=List([0..dim],i->[]); 88 subspaces[dim+1]:=Set(word,i->[AbsInt(i[1]),i[2]]); 89 for i in [dim-1,dim-2..0] 90 do 91 subspaces[i+1]:=Union(List(subspaces[i+2], 92 j->UndirectedBoundaryOfFreeZGLetter(resolution,i+1,j)) 93 ); 94 od; 95 return subspaces; 96end); 97 98 99 100 101 102############################################################################# 103## 104## Tests if a word represents a connected supspace. 105## 106InstallMethod(IsConnectedWord, 107 [IsHapResolutionRep,IsInt,IsDenseList], 108 function(resolution,dim,word) 109 if not IsFreeZGWord(resolution,dim,word) 110 then 111 Error("<word> is not a valid word"); 112 fi; 113 return IsConnectedWordNC(resolution,dim,word); 114end); 115 116 117InstallMethod(IsConnectedWordNC, 118 [IsHapResolutionRep,IsInt,IsDenseList], 119 function(resolution,dim,word) 120 local lettersAndBound, startblob, blobbound, addToBlob, 121 addToBlobBound; 122 123 lettersAndBound:=Set(word,letter-> 124 [letter,UndirectedBoundaryOfFreeZGLetter(resolution,dim,letter)] 125 ); 126 # a "blob" is just that. A connected part of word. 127 # We don't generate the blob. As we are just interesed in it's size. 128 startblob:=Remove(lettersAndBound); 129 blobbound:=startblob[2]; 130 131 repeat 132 addToBlob:=Filtered(lettersAndBound,i->Intersection(i[2],blobbound)<>[]); 133 if addToBlob<>[] 134 then 135 SubtractSet(lettersAndBound,addToBlob); 136 addToBlobBound:=Union(List(addToBlob,i->i[2])); 137 blobbound:=Union(blobbound,addToBlobBound); 138 fi; 139 until lettersAndBound=[] or addToBlob=[]; 140 141 if lettersAndBound=[] 142 then 143 return true; 144 elif addToBlob=[] 145 then 146 return false; 147 fi; 148end); 149 150 151 152 153 154############################################################################# 155## 156## connect a cell <cell> to the subspace <cellblob>. 157## 158InstallMethod(ConnectingPath, 159 [IsHapResolutionRep,IsInt,IsDenseList,IsDenseList,IsDenseList], 160 function(resolution,dim,area,cellblob,cell) 161 162 if not (IsFreeZGWord(resolution,dim,area) 163 and IsFreeZGWord(resolution,dim,cellblob) 164 ) 165 then 166 Error("<area> and <cellblob> must be valid words"); 167 elif not IsFreeZGLetter(resolution,dim,cell) 168 then 169 Error("<cell> is not a valid letter"); 170 elif not IsSubset(area,cellblob) and cell in area 171 then 172 Error("<area> does not contain <cellblob> and <cell>"); 173 fi; 174 return ConnectingPathNC(resolution,dim,area,cellblob,cell); 175end); 176 177 178InstallMethod(ConnectingPathNC, 179 [IsHapResolutionRep,IsInt,IsDenseList,IsDenseList,IsDenseList], 180 function(resolution,dim,area,cellblob,cell) 181 local pathfinder, sphereAndBounds, path; 182 183 ################################################## 184 ## 185 ## The recursive function "pathfinder" assumes that connectTo is not empty. 186 ## It calculates a path from a "disk" that connects a given starting part 187 ## with the space of known homotopies. 188 ## 189 pathfinder:=function(resolution, connectTo, sphereAndBounds, startingBit,startingbitboundary) 190 local thingsThatCouldBeAdded, endpoint, addface, 191 newSphereAndBounds, newstartingbitboundary, 192 newstartingBit, returnpath; 193 194 thingsThatCouldBeAdded:=Filtered(sphereAndBounds,i->Intersection(i[2],startingbitboundary)<>[]); 195 196 endpoint:=First(thingsThatCouldBeAdded,i->Intersection(i[2],connectTo)<>[]); 197 if endpoint<>fail 198 then 199 return Concatenation(startingBit,[endpoint[1]]); 200 else 201 newSphereAndBounds:=Difference(sphereAndBounds,thingsThatCouldBeAdded); 202 repeat 203 if thingsThatCouldBeAdded=[] 204 then 205 return []; 206 fi; 207 addface:=Remove(thingsThatCouldBeAdded); 208 newstartingbitboundary:=Union(startingbitboundary,addface[2]); 209 newstartingBit:=Concatenation(startingBit,[addface[1]]); 210 returnpath:=pathfinder(resolution, 211 connectTo, 212 newSphereAndBounds, 213 newstartingBit, 214 newstartingbitboundary 215 ); 216 until returnpath<>[]; 217 return Unique(returnpath); 218 fi; 219 end; 220 221 222 if cell in cellblob 223 then 224 return []; 225 fi; 226 sphereAndBounds:=Set(area,i->[i,UndirectedBoundaryOfFreeZGLetter(resolution,dim,i)]); 227 path:=pathfinder(resolution, 228 # undirectedReducedBoundaryOfWord(resolution,dim,cellblob), 229 UndirectedBoundaryOfFreeZGLetter(resolution,dim,cell), 230 sphereAndBounds, 231 [cell], 232 UndirectedBoundaryOfFreeZGLetter(resolution,dim,cell) 233 ); 234 if path=[] 235 then 236 return fail; 237 else 238 return path; 239 fi; 240end); 241 242 243############################################################################# 244## 245## given a word in the <dim>th term of <resolution>, this returns true 246## if and only if this word represents a contractible subspace. 247## 248## connectedness is not tested. 249## Is this right, anyway? 250## 251InstallMethod(IsContractibleWordNC, 252 [IsHapResolutionRep,IsInt,IsDenseList], 253 function(resolution,dim,subspace) 254 local chaincomplex, i; 255 chaincomplex:=ChainComplexFromWordNC(resolution,dim,subspace); 256 return Homology(chaincomplex,dim)=[]; 257end); 258 259InstallMethod(IsContractibleWord, 260 [IsHapResolutionRep,IsInt,IsDenseList], 261 function(resolution,dim,subspace) 262 if not IsFreeZGWord(resolution,dim,subspace) 263 then 264 Error("subspace is not a valid word"); 265 fi; 266 return IsContractibleWordNC(resolution,dim,subspace); 267end); 268 269############################################################################# 270## 271## 272InstallMethod(IsContractiblePartialSpace, 273 [IsHapResolutionRep,IsInt,IsDenseList], 274 function(resolution,dim,spacelist) 275 if not ForAll(spacelist,subspace->IsFreeZGWord(resolution,dim,subspace)) 276 then 277 Error("subspace is not a valid word"); 278 fi; 279 return IsContractiblePartialSpaceNC(resolution,dim,spacelist); 280end); 281 282InstallMethod(IsContractiblePartialSpaceNC, 283 [IsHapResolutionRep,IsInt,IsDenseList], 284 function(resolution,dim,spacelist) 285 local chaincomplex; 286 chaincomplex:=ChainComplexFromPartialSpaceNC(resolution,dim,spacelist); 287 return Homology(chaincomplex,dim)=[]; 288end); 289 290 291 292############################################################################# 293## 294## find the sphere that contains <cell>. 295## The list of cells <space> must induce a chain complex with <dim>th 296## homology [0]. 297## 298############################################################################# 299## 300## check the input and delegate... 301## 302InstallMethod(SphereContainingCell, 303 [IsHapResolutionRep,IsInt,IsDenseList,IsDenseList], 304 function(resolution,dim,space,cell) 305 local complex; 306 if not IsFreeZGLetter(resolution,dim,cell) 307 then 308 Error("<cell> is not a valid letter"); 309 elif not IsFreeZGWord(resolution,dim,space) 310 then 311 Error("<space> is not a valid word"); 312 elif not cell in space 313 then 314 Error("<cell> not in <space>"); 315 fi; 316 complex:=ChainComplexFromPartialSpace(resolution,dim,space); 317 if not Homology(complex,dim)=[0] 318 then 319 Error("<space> does not contain a unique sphere"); 320 fi; 321 return SphereContainingCellNC(resolution,dim,space,cell); 322end); 323 324############################################################################# 325## 326## 327InstallMethod(SphereContainingCellNC, 328 [IsHapResolutionRep,IsInt,IsDenseList,IsDenseList], 329 function(resolution,dim,space,cell) 330 local space_and_bounds, sphere, spherebound, sphere_done, 331 subspacelist, complex, newcells, new_subspaces, i; 332 333 space_and_bounds:=List(space,i->[i,UndirectedBoundaryOfFreeZGWord(resolution,dim,i)]); 334 sphere:=[cell]; 335 spherebound:=UndirectedBoundaryOfFreeZGWord(resolution,dim,sphere); 336 sphere_done:=false; 337 subspacelist:=SubspaceListFromWord(resolution,dim,sphere); 338 complex:=ChainComplexFromPartialSpace(resolution, 339 dim, 340 subspacelist 341 ); 342 while not Homology(complex,dim)=[0] 343 do 344 newcells:=Filtered(space_and_bounds,c->ForAny(c[2],i->i in spherebound)); 345 SubtractSet(space_and_bounds,newcells); 346 UniteSet(sphere,List(newcells,i->i[1])); 347 UniteSet(spherebound,Concatenation(List(newcells,i->i[2]))); 348 new_subspaces:=SubspaceListFromWord(resolution, 349 dim, 350 List(newcells,i->i[1]) 351 ); 352 for i in [1..Size(new_subspaces)] 353 do 354 UniteSet(subspacelist[i],new_subspaces[i]); 355 od; 356 od; 357 return Set(sphere); 358end); 359 360 361 362 363 364 365############################################################################# 366## 367## Generate a chain complex from a word 368## 369InstallMethod(ChainComplexFromWord, 370 [IsHapResolutionRep,IsInt,IsDenseList], 371 function(resolution,dim,subspace) 372 if not IsFreeZGWord(resolution,dim,subspace) 373 then 374 Error("<subspace> is not a proper word"); 375 fi; 376 return ChainComplexFromWordNC(resolution,dim,subspace); 377end); 378 379InstallMethod(ChainComplexFromWordNC, 380 [IsHapResolutionRep,IsInt,IsDenseList], 381 function(resolution,dim,subspace) 382 local spaces; 383 spaces:=SubspaceListFromWord(resolution,dim,subspace); 384 return ChainComplexFromPartialSpaceNC(resolution,spaces); 385end); 386 387 388 389############################################################################# 390## 391## Generate a chain complex from a list of words 392## 393InstallMethod(ChainComplexFromPartialSpace, 394 [IsHapResolutionRep,IsDenseList], 395 function(resolution,subspaces) 396 if not ForAll([1..Size(subspaces)],dim-> 397 IsFreeZGWord(resolution,dim-1,subspaces[dim]) 398 ) 399 then 400 Error("subspace list contains invalid words"); 401 fi; 402 return ChainComplexFromPartialSpaceNC(resolution,subspaces); 403end); 404 405 406############################################################################# 407## 408InstallMethod(ChainComplexFromPartialSpaceNC, 409 [IsHapResolutionRep,IsDenseList], 410 function(resolution,subspaces) 411 local undirectedLetter, word2vec, boundary, dimension, 412 complex, properties; 413 414 undirectedLetter:=function(letter) 415 return [AbsInt(letter[1]),letter[2]]; 416 end; 417 418 word2vec:=function(generators,word) 419 local vec, letter, pos; 420 vec:=List([1..Size(generators)],i->0); 421 for letter in word 422 do 423 pos:=Position(generators,undirectedLetter(letter)); 424 if pos<>fail 425 then 426 vec[pos]:=vec[pos]+SignInt(letter[1]); 427 else 428 Error("word-vector conversion error"); 429 fi; 430 od; 431 return vec; 432 end; 433 434 435 boundary:=function(k,j) 436 local letter, boundaryAsWord; 437 if k=Size(subspaces+1) 438 then 439 return []; 440 fi; 441 letter:=subspaces[k+1][j]; 442 boundaryAsWord:=BoundaryOfFreeZGLetterNC(resolution,k,letter); 443 return word2vec(subspaces[k],boundaryAsWord); 444 end; 445 446 447 dimension:=function(k) 448 if k<Size(subspaces) 449 then 450 return Size(subspaces[k+1]); 451 elif k=Size(subspaces) 452 then 453 return 0; 454 else 455 Error("chain complex too short"); 456 fi; 457 end; 458 459 complex:=Objectify(HapChainComplex, 460 rec(dimension:=dimension, 461 boundary:=boundary, 462 subspaces:=List(subspaces), 463 properties:= 464 [["length", Size(subspaces)-1], 465 ["characteristic", 0], 466 ["type", "chainComplex"] 467 ]) 468 ); 469 return complex; 470end); 471 472 473 474 475