1############################################################################# 2## 3## This file is part of GAP, a system for computational discrete algebra. 4## This file's authors include Frank Celler, Alexander Hulpke. 5## 6## Copyright of GAP belongs to its developers, whose names are too numerous 7## to list here. Please refer to the COPYRIGHT file for details. 8## 9## SPDX-License-Identifier: GPL-2.0-or-later 10## 11## This file contains the methods for complements in pc groups 12## 13 14BindGlobal("HomomorphismsSeries",function(G,h) 15local r,img,i,gens,img2; 16 r:=ShallowCopy(h); 17 img:=Image(h[Length(h)],G); 18 for i in [Length(h)-1,Length(h)-2..1] do 19 gens:=GeneratorsOfGroup(img); 20 img2:=Image(h[i],G); 21 r[i]:=GroupHomomorphismByImagesNC(img,img2,gens,List(gens,j-> 22 Image(h[i],PreImagesRepresentative(h[i+1],j)))); 23 SetKernelOfMultiplicativeGeneralMapping(r[i], 24 Image(h[i+1],KernelOfMultiplicativeGeneralMapping(h[i]))); 25 img:=img2; 26 od; 27 return r; 28end); 29 30# test function for relators 31BindGlobal("OCTestRelators",function(ocr) 32 if not IsBound(ocr.relators) then return true;fi; 33 return ForAll(ocr.relators,i->ExponentsOfPcElement(ocr.generators, 34 Product(List([1..Length(i.generators)], 35 j->ocr.generators[i.generators[j]]^i.powers[j]))) 36 =List(ocr.generators,i->0)); 37end); 38 39############################################################################# 40## 41#F COAffineBlocks( <S>,<Sgens>,<mats>,<orbs> ) 42## 43## Divide the vectorspace into blocks using the affine operations of <S> 44## described by <mats>. Return representative for these blocks and their 45## normalizers in <S>. 46## if <orbs> is true orbits are kept. 47## 48InstallGlobalFunction( COAffineBlocks, function( S, Sgens,mats,orbs ) 49local dim, p, nul, one, C, L, blt, B, O, Q, i, j, v, w, n, z, root,r; 50 51 # The affine operation of <S> is described via <mats> as 52 # 53 # ( lll 0 ) 54 # ( lll 0 ) 55 # ( ttt 1 ) 56 # 57 # where l describes the linear operation and t the translation the 58 # dimension of the vectorspace is of dimension one less than the 59 # matrices <mats>. 60 # 61 dim:=Length(mats[1]) - 1; 62 one:=One(mats[1][1][1]); 63 nul:=0 * one; 64 root:=Z(Characteristic(one)); 65 p:=Characteristic( mats[1][1][1] ); 66 C:=List( [1..dim], x -> p ); 67 Q:=List( [0..dim-1], x -> p ^x ); 68 L:=[]; 69 for i in [1..p-1] do 70 L[LogFFE( one * i,root ) + 1]:=i; 71 od; 72 73 # Make a boolean list of length <p> ^ <dim>. 74 blt:=BlistList( [1..p ^ dim], [] ); 75 Info(InfoComplement,3,"COAffineBlocks: ", p^dim, " elements in H^1" ); 76 i:=1; # was: Position( blt, false ); 77 B:=[]; 78 79 # Run through this boolean list. 80 while i <> fail do 81 v:=CoefficientsQadic(i-1,p); 82 while Length(v)<dim do 83 Add(v,0); 84 od; 85 v:=v*one; 86 w:=ImmutableVector(p,v); 87 Add(v, one); 88 v:=ImmutableVector(p,v); 89 O:=OrbitStabilizer( S,v, Sgens,mats); 90 for v in O.orbit do 91 n:=1; 92 for j in [1..dim] do 93 z:=v[j]; 94 if z <> nul then 95 n:=n + Q[j] * L[LogFFE( z,root ) + 1]; 96 fi; 97 od; 98 blt[n]:=true; 99 od; 100 Info(InfoComplement,3,"COAffineBlocks: |block| = ", Length(O.orbit)); 101 r:=rec( vector:=w, stabilizer:=O.stabilizer ); 102 if orbs=true then r.orbit:=O.orbit;fi; 103 Add( B, r); 104 i:=Position( blt, false ); 105 od; 106 Info(InfoComplement,3,"COAffineBlocks: ", Length( B ), " blocks found" ); 107 return B; 108 109end ); 110 111 112############################################################################# 113## 114#F CONextCentralizer( <ocr>, <S>, <H> ) . . . . . . . . . . . . . . . local 115## 116## Correct the blockstabilizer and return the stabilizer of <H> in <S> 117## 118InstallGlobalFunction( CONextCentralizer, function( ocr, Spcgs, H ) 119local gens, pnt, i; 120 121 # Get the generators of <S> and correct them. 122 Info(InfoComplement,3,"CONextCentralizer: correcting blockstabilizer" ); 123 gens:=ShallowCopy( Spcgs ); 124 pnt :=ocr.complementToCocycle( H ); 125 for i in [1..Length( gens )] do 126 gens[i]:=gens[i] * 127 OCConjugatingWord( ocr, 128 ocr.complementToCocycle( H ^ gens[i] ), 129 pnt ); 130 od; 131 Info(InfoComplement,3,"CONextCentralizer: blockstabilizer corrected" ); 132 return ClosureGroup( ocr.centralizer, gens ); 133 134end ); 135 136#ocr is oc record, acts are elements that act via ^ on group elements, B 137#is the result of BaseSteinitzVectors on the 1-cocycles in ocr. 138InstallGlobalFunction(COAffineCohomologyAction,function(ocr,relativeGens,acts,B) 139local tau, phi, mats; 140 141 # Get the matrices describing the affine operations. The linear part 142 # of the operation is just conjugation of the entries of cocycle. The 143 # translation are commuators with the generators. So check if <ocr> 144 # has a small generating set. Use only these to form the commutators. 145 146 # Translation: (.. h ..) -> (.. [h,c] ..) 147 if IsBound( ocr.smallGeneratingSet ) then 148 149 Error("not yet implemented"); 150 tau:=function( c ) 151 local l, i, j, z, v; 152 l:=[]; 153 for i in ocr.smallGeneratingSet do 154 Add( l, Comm( ocr.generators[i], c ) ); 155 od; 156 l:=ocr.listToCocycle( l ); 157 v:=ShallowCopy( B.factorzero ); 158 for i in [1..Length(l)] do 159 if l[i] <> ocr.zero then 160 z:=l[i]; 161 j:=B.heads[i]; 162 if j > 0 then 163 l:=l - z * B.factorspace[j]; 164 v[j]:=z; 165 else 166 l:=l - z * B.subspace[-j]; 167 fi; 168 fi; 169 od; 170 IsRowVector( v ); 171 return v; 172 end; 173 174 else 175 176 tau:=function( c ) 177 local l, i, j, z, v; 178 l:=[]; 179 for i in relativeGens do 180 #Add( l, LeftQuotient(i,i^c)); 181 Add( l, Comm(i,c)); 182 od; 183 l:=ocr.listToCocycle( l ); 184 v:=ListWithIdenticalEntries(Length(B.factorspace),ocr.zero); 185 for i in [1..Length(l)] do 186 if l[i] <> ocr.zero then 187 z:=l[i]; 188 j:=B.heads[i]; 189 if j > 0 then 190 l:=l - z * B.factorspace[j]; 191 v[j]:=z; 192 else 193 l:=l - z * B.subspace[-j]; 194 fi; 195 fi; 196 od; 197 IsRowVector( v ); 198 return v; 199 end; 200 fi; 201 202 # Linear Operation: (.. hm ..) -> (.. (hm)^c ..) 203 phi:=function( z, c ) 204 local l, i, j, v; 205 l:=ocr.listToCocycle( List( ocr.cocycleToList(z), x -> x ^ c ) ); 206 v:=ListWithIdenticalEntries(Length(B.factorspace),ocr.zero); 207 for i in [1..Length( l )] do 208 if l[i] <> ocr.zero then 209 z:=l[i]; 210 j:=B.heads[i]; 211 if j > 0 then 212 l:=l - z * B.factorspace[j]; 213 v[j]:=z; 214 else 215 l:=l - z * B.subspace[-j]; 216 fi; 217 fi; 218 od; 219 IsRowVector( v ); 220 return v; 221 end; 222 223 # Construct the affine operations and blocks under them. 224 mats:=AffineAction( acts,B.factorspace, phi, tau ); 225 Assert(2,ForAll(mats,i->ForAll(i,j->Length(i)=Length(j)))); 226 return mats; 227end); 228 229 230############################################################################# 231## 232#F CONextCocycles( <cor>, <ocr>, <S> ) . . . . . . . . . . . . . . . . local 233## 234## Get the next conjugacy classes of complements under operation of <S> 235## using affine operation on the onecohomologygroup of <K> and <N>, where 236## <ocr>:=rec( group:=<K>, module:=<N> ). 237## 238## <ocr> is a record as described in 'OCOneCocycles'. The classes are 239## returned as list of records rec( complement, centralizer ). 240## 241InstallGlobalFunction( CONextCocycles, function( cor, ocr, S ) 242local K, N, Z, SN, B, L, LL, SNpcgs, mats, i; 243 244 # Try to split <K> over <M>, if it does not split return. 245 Info(InfoComplement,3,"CONextCocycles: computing cocycles" ); 246 K:=ocr.group; 247 N:=ocr.module; 248 Z:=OCOneCocycles( ocr, true ); 249 if IsBool( Z ) then 250 if IsBound( ocr.normalIn ) then 251 Info(InfoComplement,3,"CONextCocycles: no normal complements" ); 252 else 253 Info(InfoComplement,3,"CONextCocycles: no split extension" ); 254 fi; 255 return []; 256 fi; 257 258 ocr.generators:=CanonicalPcgs(InducedPcgs(ocr.pcgs,ocr.complement)); 259 Assert(2,OCTestRelators(ocr)); 260 261 # If there is only one complement this is normal. 262 if Dimension( Z ) = 0 then 263 Info(InfoComplement,3,"CONextCocycles: group of cocycles is trivial" ); 264 K:=ocr.complement; 265 if IsBound(cor.condition) and not cor.condition(cor, K) then 266 return []; 267 else 268 return [rec( complement:=K, centralizer:=S )]; 269 fi; 270 fi; 271 272 # If the one cohomology group is trivial, there is only one class of 273 # complements. Correct the blockstabilizer and return. If we only want 274 # normal complements, this case cannot happen, as cobounds are trivial. 275 SN:=SubgroupNC( S, Filtered(GeneratorsOfGroup(S),i-> not i in N)); 276 if Dimension(ocr.oneCoboundaries)=Dimension(ocr.oneCocycles) then 277 Info(InfoComplement,3,"CONextCocycles: H^1 is trivial" ); 278 K:=ocr.complement; 279 if IsBound(cor.condition) and not cor.condition(cor, K) then 280 return []; 281 fi; 282 S:=CONextCentralizer( ocr, 283 InducedPcgs(cor.pcgs,SN), 284 ocr.complement); 285 return [rec( complement:=K, centralizer:=S )]; 286 fi; 287 288 # If <S> = <N>, there are no new blocks under the operation of <S>, so 289 # get all elements of the one cohomology group and return. If we only 290 # want normal complements, there also are no blocks under the operation 291 # of <S>. 292 B:=BaseSteinitzVectors(BasisVectors(Basis(ocr.oneCocycles)), 293 BasisVectors(Basis(ocr.oneCoboundaries))); 294 if Size(SN) = 1 or IsBound(ocr.normalIn) then 295 L:=VectorSpace(ocr.field,B.factorspace, B.factorzero); 296 Info(InfoComplement,3,"CONextCocycles: ",Size(L)," complements found"); 297 if IsBound(ocr.normalIn) then 298 Info(InfoComplement,3,"CONextCocycles: normal complements, using H^1"); 299 LL:=[]; 300 if IsBound(cor.condition) then 301 for i in L do 302 K:=ocr.cocycleToComplement(i); 303 if cor.condition(cor, K) then 304 Add(LL, rec(complement:=K, centralizer:=S)); 305 fi; 306 od; 307 else 308 for i in L do 309 K:=ocr.cocycleToComplement(i); 310 Add(LL, rec(complement:=K, centralizer:=S)); 311 od; 312 fi; 313 return LL; 314 else 315 Info(InfoComplement,3,"CONextCocycles: S meets N, using H^1"); 316 LL:=[]; 317 if IsBound(cor.condition) then 318 for i in L do 319 K:=ocr.cocycleToComplement(i); 320 if cor.condition(cor, K) then 321 S:=ocr.centralizer; 322 Add(LL, rec(complement:=K, centralizer:=S)); 323 fi; 324 od; 325 else 326 for i in L do 327 K:=ocr.cocycleToComplement(i); 328 S:=ocr.centralizer; 329 Add(LL, rec(complement:=K, centralizer:=S)); 330 od; 331 fi; 332 return LL; 333 fi; 334 fi; 335 336 # The situation is as follows. 337 # 338 # S As <N> does act trivial on the onecohomology 339 # \ K group, compute first blocks of this group under 340 # \ / \ the operation of <S>/<N>. But as <S>/<N> acts 341 # N ? affine, this can be done using affine operation 342 # \ / (given as matrices). 343 # 1 344 345 SNpcgs:=InducedPcgs(cor.pcgs,SN); 346 mats:=COAffineCohomologyAction(ocr,ocr.generators,SNpcgs,B); 347 348 L :=COAffineBlocks( SN, SNpcgs,mats,false ); 349 Info(InfoComplement,3,"CONextCocycles:", Length( L ), " complements found" ); 350 351 # choose a representative from each block and correct the blockstab 352 LL:=[]; 353 for i in L do 354 K:=ocr.cocycleToComplement(i.vector*B.factorspace); 355 if not IsBound(cor.condition) or cor.condition(cor, K) then 356 if Z = [] then 357 S:=ClosureGroup( ocr.centralizer, i.stabilizer ); 358 else 359 S:=CONextCentralizer(ocr, 360 InducedPcgs(cor.pcgs, 361 i.stabilizer), K); 362 fi; 363 Add(LL, rec(complement:=K, centralizer:=S)); 364 fi; 365 od; 366 return LL; 367 368end ); 369 370 371############################################################################# 372## 373#F CONextCentral( <cor>, <ocr>, <S> ) . . . . . . . . . . . . . . . . local 374## 375## Get the conjugacy classes of complements in case <ocr.module> is central. 376## 377InstallGlobalFunction( CONextCentral, function( cor, ocr, S ) 378local z,K,N,zett,SN,B,L,tau,gens,imgs,A,T,heads,dim,s,v,j,i,root; 379 380 # Try to split <ocr.group> 381 K:=ocr.group; 382 N:=ocr.module; 383 384 # If <K> is no split extension of <N> return the trivial list, as there 385 # are no complements. We compute the cocycles only if the extenstion 386 # splits. 387 zett:=OCOneCocycles( ocr, true ); 388 if IsBool( zett ) then 389 if IsBound( ocr.normalIn ) then 390 Info(InfoComplement,3,"CONextCentral: no normal complements" ); 391 else 392 Info(InfoComplement,3,"CONextCentral: no split extension" ); 393 fi; 394 return []; 395 fi; 396 397 ocr.generators:=CanonicalPcgs(InducedPcgs(ocr.pcgs,ocr.complement)); 398 Assert(2,OCTestRelators(ocr)); 399 400 # if there is only one complement it must be normal 401 if Dimension(zett) = 0 then 402 Info(InfoComplement,3,"CONextCentral: Z^1 is trivial"); 403 K:=ocr.complement; 404 if IsBound(cor.condition) and not cor.condition(cor, K) then 405 return []; 406 else 407 return [rec(complement:=K, centralizer:=S)]; 408 fi; 409 fi; 410 411 # If the one cohomology group is trivial, there is only one class of 412 # complements. Correct the blockstabilizer and return. If we only want 413 # normal complements, this cannot happen, as the cobounds are trivial. 414 SN:=SubgroupNC( S, Filtered(GeneratorsOfGroup(S),i-> not i in N)); 415 if Dimension(ocr.oneCoboundaries)=Dimension(ocr.oneCocycles) then 416 Info(InfoComplement,3,"CONextCocycles: H^1 is trivial" ); 417 K:=ocr.complement; 418 if IsBound(cor.condition) and not cor.condition(cor, K) then 419 return []; 420 else 421 S:=CONextCentralizer( ocr, 422 InducedPcgs(cor.pcgs,SN),ocr.complement); 423 return [rec(complement:=K, centralizer:=S)]; 424 fi; 425 fi; 426 427 # If <S> = <N>, there are no new blocks under the operation of <S>, so 428 # get all elements of the onecohomologygroup and return. If we only want 429 # normal complements, there also are no blocks under the operation of 430 # <S>. 431 B:=BaseSteinitzVectors(BasisVectors(Basis(ocr.oneCocycles)), 432 BasisVectors(Basis(ocr.oneCoboundaries))); 433 if Size(SN)=1 or IsBound( ocr.normalIn ) then 434 if IsBound( ocr.normalIn ) then 435 Info(InfoComplement,3,"CONextCocycles: normal complements, using H^1"); 436 else 437 Info(InfoComplement,3,"CONextCocycles: S meets N, using H^1" ); 438 S:=ocr.centralizer; 439 fi; 440 L:=VectorSpace(ocr.field,B.factorspace, B.factorzero); 441 T:=[]; 442 for i in L do 443 K:=ocr.cocycleToComplement(i); 444 if not IsBound(cor.condition) or cor.condition(cor, K) then 445 Add(T, rec(complement:=K, centralizer:=S)); 446 fi; 447 od; 448 Info(InfoComplement,3,"CONextCocycles: ",Length(T)," complements found" ); 449 return T; 450 fi; 451 452 # The conjugacy classes of complements are cosets of the cocycles of 453 # 0^S. If 'smallGeneratingSet' is given, do not use this gens. 454 455 # Translation: (.. h ..) -> (.. [h,c] ..) 456 if IsBound( ocr.smallGeneratingSet ) then 457 tau:=function( c ) 458 local l; 459 l:=[]; 460 for i in ocr.smallGeneratingSet do 461 Add( l, Comm( ocr.generators[i], c ) ); 462 od; 463 return ocr.listToCocycle( l ); 464 end; 465 else 466 tau:=function( c ) 467 local l; 468 l:=[]; 469 for i in ocr.generators do 470 Add( l, Comm( i, c ) ); 471 od; 472 return ocr.listToCocycle( l ); 473 end; 474 fi; 475 gens:=InducedPcgs(cor.pcgs,SN); 476 imgs:=List( gens, tau ); 477 478 # Now get a base for the subspace 0^S. For those zero images which are 479 # not part of a base a generators of the stabilizer can be generated. 480 # B holds the base, 481 # A holds the correcting elements for the base vectors, 482 # T holds the stabilizer generators. 483 dim:=Length( imgs[1] ); 484 A:=[]; 485 B:=[]; 486 T:=[]; 487 heads:=ListWithIdenticalEntries(dim,0); 488 489 root:=Z(ocr.char); 490 # Get the base starting with the last one and go up. 491 for i in Reversed( [1..Length(imgs)] ) do 492 s:=gens[i]; 493 v:=imgs[i]; 494 j:=1; 495 # was:while j <= dim and IntFFE(v[j]) = 0 do 496 while j <= dim and v[j] = ocr.zero do 497 j:=j + 1; 498 od; 499 while j <= dim and heads[j] <> 0 do 500 z:=v[j] / B[heads[j]][j]; 501 if z <> 0*z then 502 s:=s / A[heads[j]] ^ ocr.logTable[LogFFE(z,root)+1]; 503 fi; 504 v:=v - v[j] / B[heads[j]][j] * B[heads[j]]; 505 # was: while j <= dim and IntFFE(v[j]) = 0 do 506 while j <= dim and v[j] = ocr.zero do 507 j:=j + 1; 508 od; 509 od; 510 if j > dim then 511 Add( T, s ); 512 else 513 Add( B, v ); 514 Add( A, s ); 515 heads[j]:=Length( B ); 516 fi; 517 od; 518 519 # So <T> now holds a reversed list of generators for a stabilizer. <B> 520 # is a base for 0^<S> and <cocycles>/0^<S> are the conjugacy classes of 521 # complements. 522 S:=ClosureGroup(N,T); 523 if B = [] then 524 B:=zett; 525 else 526 B:=BaseSteinitzVectors(BasisVectors(Basis(zett)),B); 527 B:=VectorSpace(ocr.field,B.factorspace, B.factorzero); 528 fi; 529 L:=[]; 530 for i in B do 531 K:=ocr.cocycleToComplement(i); 532 if not IsBound(cor.condition) or cor.condition(cor, K) then 533 Add(L, rec(complement:=K, centralizer:=S)); 534 fi; 535 od; 536 Info(InfoComplement,3,"CONextCentral: ", Length(L), " complements found"); 537 return L; 538 539end ); 540 541 542############################################################################# 543## 544#F CONextComplements( <cor>, <S>, <K>, <M> ) . . . . . . . . . . . . . local 545## S: fuser, K: Complements in, M: Complements to 546## 547InstallGlobalFunction( CONextComplements, function( cor, S, K, M ) 548local p, ocr; 549 550 Assert(1,IsSubgroup(K,M)); 551 552 if IsTrivial(M) then 553 if IsBound(cor.condition) and not cor.condition(cor, K) then 554 return []; 555 else 556 return [rec( complement:=K, centralizer:=S )]; 557 fi; 558 elif GcdInt(Size(M), Index(K,M)) = 1 then 559 560 # If <K> and <M> are coprime, <K> splits. 561 Info(InfoComplement,3,"CONextComplements: coprime case, <K> splits" ); 562 ocr:=rec( group:=K, module:=M, 563 modulePcgs:=InducedPcgs(cor.pcgs,M), 564 pcgs:=cor.pcgs, inPcComplement:=true); 565 566 if IsBound( cor.generators ) then 567 ocr.generators:=cor.generators; 568 Assert(2,OCTestRelators(ocr)); 569 Assert(1,IsModuloPcgs(ocr.generators)); 570 fi; 571 if IsBound( cor.smallGeneratingSet ) then 572 ocr.smallGeneratingSet:=cor.smallGeneratingSet; 573 ocr.generatorsInSmall :=cor.generatorsInSmall; 574 elif IsBound( cor.primes ) then 575 p:=Factors(Size( M.generators))[1]; 576 if p in cor.primes then 577 ocr.pPrimeSet:=cor.pPrimeSets[Position( cor.primes, p )]; 578 fi; 579 fi; 580 if IsBound( cor.relators ) then 581 ocr.relators:=cor.relators; 582 Assert(2,OCTestRelators(ocr)); 583 fi; 584 585 #was: ocr.complement:=CoprimeComplement( K, M ); 586 OCOneCocycles( ocr, true ); 587 588 OCOneCoboundaries( ocr ); 589 if IsBound( cor.normalComplements ) 590 and cor.normalComplements 591 and Dimension( ocr.oneCoboundaries ) <> 0 then 592 return []; 593 else 594 K:=ocr.complement; 595 if IsBound(cor.condition) and not cor.condition(cor, K) then 596 return []; 597 fi; 598 S:=SubgroupNC( S, Filtered(GeneratorsOfGroup(S),i->not i in M)); 599 S:=CONextCentralizer( ocr, 600 InducedPcgs(cor.pcgs,S), K ); 601 return [rec( complement:=K, centralizer:=S )]; 602 fi; 603 else 604 605 # In the non-coprime case, we must construct cocycles. 606 ocr:=rec( group:=K, module:=M, 607 modulePcgs:=InducedPcgs(cor.pcgs,M), 608 pcgs:=cor.pcgs, inPcComplement:=true); 609 610 if IsBound( cor.generators ) then 611 ocr.generators:=cor.generators; 612 Assert(2,OCTestRelators(ocr)); 613 Assert(1,IsModuloPcgs(ocr.generators)); 614 fi; 615 if IsBound( cor.normalComplement ) and cor.normalComplements then 616 ocr.normalIn:=S; 617 fi; 618 619# if IsBound( cor.normalSubgroup ) then 620# L:=cor.normalSubgroup( S, K, M ); 621# if IsTrivial(L) = [] then 622# return CONextCocycles(cor, ocr, S); 623# else 624# return CONextNormal(cor, ocr, S, L); 625# fi; 626# else 627 628 if IsBound( cor.smallGeneratingSet ) then 629 ocr.smallGeneratingSet:=cor.smallGeneratingSet; 630 ocr.generatorsInSmall :=cor.generatorsInSmall; 631 elif IsBound( cor.primes ) then 632 p:=Factors(Size( M.generators))[1]; 633 if p in cor.primes then 634 ocr.pPrimeSet:=cor.pPrimeSets[Position(cor.primes,p)]; 635 fi; 636 fi; 637 if IsBound( cor.relators ) then 638 ocr.relators:=cor.relators; 639 Assert(2,OCTestRelators(ocr)); 640 fi; 641 if ( cor.useCentral and IsCentral( Parent(M), M ) ) 642 or ( cor.useCentralSK and IsCentral(S,M) and IsCentral(K,M) ) then 643 return CONextCentral(cor, ocr, S); 644 else 645 return CONextCocycles(cor, ocr, S); 646 fi; 647 648 fi; 649 650end ); 651 652 653############################################################################# 654## 655#F COComplements( <cor>, <G>, <N>, <all> ) . . . . . . . . . . . . . . local 656## 657## Compute the complements in <G> of the normal subgroup N[1]. N is a list 658## of normal subgroups of G s.t. N[i]/N[i+1] is elementary abelian. 659## If <all> is true, find all (conjugacy classes of) complements. 660## Otherwise try to find just one complement. 661## 662InstallGlobalFunction( COComplements, function( cor, G, E, all ) 663local r,a,a0,FG,nextStep,C,found,i,time,hpcgs,ipcgs; 664 665 # give some information and start timing 666 Info(InfoComplement,3,"Complements: initialize factorgroups" ); 667 time:=Runtime(); 668 669 # we only need the series beginning from position <n> 670 r:=Length(E); 671 672 # Construct the homomorphisms <a>[i] = <G>/<E>[i+1] -> <G>/<E>[i]. 673 674 675 a0:=[]; 676 for i in [1..Length(E)-1] do 677 # to get compatibility we must build the natural homomorphisms 678 # ourselves. 679 ipcgs:=InducedPcgs(cor.home,E[i]); 680 hpcgs:=cor.home mod ipcgs; 681 FG:=PcGroupWithPcgs(hpcgs); 682 a:=GroupHomomorphismByImagesNC(G,FG,cor.home, 683 Concatenation(FamilyPcgs(FG),List(ipcgs,i->One(FG)))); 684 SetKernelOfMultiplicativeGeneralMapping( a, E[i] ); 685 Add(a0,a); 686 od; 687 688 # hope that NHBNS deals with the trivial subgroup sensibly 689# a0:=List(E{[1..Length(E)-1]},i->NaturalHomomorphismByNormalSubgroup(G,i)); 690 691 hpcgs:=List([1..Length(E)-1], 692 i->PcgsByPcSequenceNC(FamilyObj(One(Image(a0[i]))), 693 List(cor.home mod InducedPcgs(cor.home,E[i]), 694 j->Image(a0[i],j)))); 695 Add(hpcgs,cor.home); 696 cor.hpcgs:=hpcgs; 697 a :=HomomorphismsSeries( G, a0 ); 698 a0:=a0[1]; 699 700 # <FG> contains the factorgroups <G>/<E>[1], ..., <G>/<E>[<r>]. 701 FG:=List( a, Range ); 702 Add( FG, G ); 703 704 # As all entries in <cor> are optional, initialize them if they are not 705 # present in <cor> with the following defaults. 706 # 707 # 'generators' : standard generators 708 # 'relators' : pc-relators 709 # 'useCentral' : false 710 # 'useCentralSK' : false 711 # 'normalComplements' : false 712 # 713 if not IsBound( cor.useCentral ) then 714 cor.useCentral:=false; 715 fi; 716 if not IsBound( cor.useCentralSK ) then 717 cor.useCentralSK:=false; 718 fi; 719 if not IsBound( cor.normalComplements ) then 720 cor.normalComplements:=false; 721 fi; 722 if IsBound( cor.generators ) then 723 cor.generators:= 724 InducedPcgsByGeneratorsNC(cor.hpcgs[1], 725 List(cor.generators,x->Image(a0,x))); 726 else 727 cor.generators:=CanonicalPcgs( InducedPcgs(cor.hpcgs[1],FG[1] )); 728 fi; 729 cor.gele:=Length(cor.generators); 730 Assert(1,cor.generators[1] in FG[1]); 731 732 #if not IsBound( cor.normalSubgroup ) then 733 cor.group :=FG[1]; 734 cor.module:=TrivialSubgroup( FG[1] ); 735 cor.modulePcgs:=InducedPcgs(cor.hpcgs[1],cor.module); 736 OCAddRelations(cor,cor.generators); 737 #fi; 738 Assert(2,OCTestRelators(cor)); 739 740 # The following function will be called recursively in order to descend 741 # the tree and reach a complement. <nr> is the current level. 742 # it lifts the complement K over the nr-th step and fuses under the action 743 # of (the full preimage of) S 744 nextStep:=function( S, K, nr ) 745 local M, NC, X; 746 747 # give information about the level reached 748 Info(InfoComplement,2,"Complements: reached level ", nr, " of ", r); 749 750 # if this is the last level we have a complement, add it to <C> 751 if nr = r then 752 Add( C, rec( complement:=K, centralizer:=S ) ); 753 Info(InfoComplement,3,"Complements: next class found, ", 754 "total ", Length(C), " complement(s), ", 755 "time=", Runtime() - time); 756 found:=true; 757 758 # otherwise try to split <K> over <M> = <FE>[<nr>+1] 759 else 760 S:=PreImage( a[nr], S ); 761 M:=KernelOfMultiplicativeGeneralMapping(a[nr]); 762 cor.module:=M; 763 cor.pcgs:=cor.hpcgs[nr+1]; 764 cor.modulePcgs:=InducedPcgs(cor.pcgs,M); 765 766 # we cannot take the 'PreImage' as this changes the gens 767 768cor.oldK:=K; 769cor.oldgens:=cor.generators; 770 771 K:=PreImage(a[nr],K); 772 cor.generators:=CanonicalPcgs(InducedPcgs(cor.pcgs,K)); 773 cor.generators:=cor.generators mod InducedPcgs(cor.pcgs,cor.module); 774 Assert(1,Length(cor.generators)=cor.gele); 775 Assert(2,OCTestRelators(cor)); 776 777 # now 'CONextComplements' will try to find the complements 778 NC:=CONextComplements( cor, S, K, M ); 779Assert(1,cor.pcgs=cor.hpcgs[nr+1]); 780 781 # try to step down as fast as possible 782 for X in NC do 783 Assert(2,OCTestRelators(rec( 784 generators:=CanonicalPcgs(InducedPcgs(cor.hpcgs[nr+1],X.complement)), 785 relators:=cor.relators))); 786 nextStep( X.centralizer, X.complement, nr+1 ); 787 if found and not all then 788 return; 789 fi; 790 od; 791 fi; 792 end; 793 794 # in <C> we will collect the complements at the last step 795 C:=[]; 796 797 # ok, start 'nextStep' with trivial module 798 Info(InfoComplement,2," starting search, time=",Runtime()-time); 799 found:=false; 800 nextStep( TrivialSubgroup( FG[1] ), 801 SubgroupNC( FG[1], cor.generators ), 1 ); 802 803 # some timings 804 Info(InfoComplement,2,"Complements: ",Length(C)," complement(s) found, ", 805 "time=", Runtime()-time ); 806 807 # add the normalizer 808 Info(InfoComplement,3,"Complements: adding normalizers" ); 809 for i in [1..Length(C)] do 810 C[i].normalizer:=ClosureGroup( C[i].centralizer, 811 C[i].complement ); 812 od; 813 return C; 814 815end ); 816 817 818############################################################################# 819## 820#M COComplementsMain( <G>, <N>, <all>, <fun> ) . . . . . . . . . . . . . local 821## 822## Prepare arguments for 'ComplementCO'. 823## 824InstallGlobalFunction( COComplementsMain, function( G, N, all, fun ) 825local H, E, cor, a, i, fun2,pcgs,home; 826 827 home:=HomePcgs(G); 828 pcgs:=home; 829 # Get the elementary abelian series through <N>. 830 E:=ElementaryAbelianSeriesLargeSteps( [G,N,TrivialSubgroup(G)] ); 831 E:=Filtered(E,i->IsSubset(N,i)); 832 833 # we require that the subgroups of E are subgroups of the Pcgs-Series 834 835 if Length(InducedPcgs(home,G))<Length(home) # G is not the top group 836 # nt not in series 837 or ForAny(E,i->Size(i)>1 and 838 not i=SubgroupNC(G,home{[DepthOfPcElement(home, 839 InducedPcgs(home,i)[1])..Length(home)]})) 840 then 841 842 Info(InfoComplement,3,"Computing better pcgs" ); 843 # create a better pcgs 844 845 pcgs:=InducedPcgs(home,G) mod InducedPcgs(home,N); 846 for i in [2..Length(E)] do 847 pcgs:=Concatenation(pcgs, 848 InducedPcgs(home,E[i-1]) mod InducedPcgs(home,E[i])); 849 od; 850 851 if not IsPcGroup(G) then 852 # for non-pc groups arbitrary pcgs may become unfeasibly slow, so 853 # convert to a pc group in this case 854 pcgs:=PcgsByPcSequenceCons(IsPcgsDefaultRep, 855 IsPcgs and IsPrimeOrdersPcgs,FamilyObj(One(G)),pcgs,[]); 856 857 H:=PcGroupWithPcgs(pcgs); 858 home:=pcgs; # this is our new home pcgs 859 a:=GroupHomomorphismByImagesNC(G,H,pcgs,GeneratorsOfGroup(H)); 860 E:=List(E,i->Image(a,i)); 861 if IsFunction(fun) then 862 fun2:=function(x) 863 return fun(PreImage(a,x)); 864 end; 865 else 866 pcgs:=home; 867 fun2:=fun; 868 fi; 869 Info(InfoComplement,3,"transfer back" ); 870 return List( COComplementsMain( H, Image(a,N), all, fun2 ), x -> rec( 871 complement :=PreImage( a, x.complement ), 872 centralizer:=PreImage( a, x.centralizer ) ) ); 873 else 874 pcgs:=PcgsByPcSequenceNC(FamilyObj(home[1]),pcgs); 875 IsPrimeOrdersPcgs(pcgs); # enforce setting 876 H:= GroupByGenerators( pcgs ); 877 home:=pcgs; 878 fi; 879 880 fi; 881 882 # if <G> and <N> are coprime <G> splits over <N> 883 if false and GcdInt(Size(N), Index(G,N)) = 1 then 884 Info(InfoComplement,3,"Complements: coprime case, <G> splits" ); 885 cor:=rec(); 886 887 # otherwise we compute a hall system for <G>/<N> 888 else 889 #AH 890 #Info(InfoComplement,2,"Complements: computing p prime sets" ); 891 #a :=NaturalHomomorphism( G, G / N ); 892 #cor:=PPrimeSetsOC( Image( a ) ); 893 #cor.generators:=List( cor.generators, x -> 894 # PreImagesRepresentative( a, x ) ); 895 cor:=rec(home:=home,generators:=pcgs mod InducedPcgs(pcgs,N)); 896 cor.useCentralSK:=true; 897 fi; 898 899 # if a condition was given use it 900 if IsFunction(fun) then cor.condition:=fun; fi; 901 902 # 'COComplements' will do most of the work 903 return COComplements( cor, G, E, all ); 904 905end ); 906 907 908InstallMethod( ComplementClassesRepresentativesSolvableNC, "pc groups", 909 IsIdenticalObj, [CanEasilyComputePcgs,CanEasilyComputePcgs], 0, 910function(G,N) 911 return List( COComplementsMain(G, N, true, false), G -> G.complement ); 912end); 913 914 915# Solvable factor group case 916# find complements to (N\cap H)M/M in H/M where H=N_G(M), assuming factor is 917# solvable 918InstallGlobalFunction(COSolvableFactor,function(arg) 919local G,N,M,keep,H,K,f,primes,p,A,S,L,hom,c,cn,nc,ncn,lnc,lncn,q,qs,qn,ser, 920 pos,i,pcgs,z,qk,j,ocr,bas,mark,k,orb,shom,shomgens,subbas,elm, 921 acterlist,free,nz,gp,actfun,mat,cond,pos2; 922 923 G:=arg[1]; 924 N:=arg[2]; 925 M:=arg[3]; 926 if Length(arg)>3 then 927 keep:=arg[4]; 928 else 929 keep:=false;; 930 fi; 931 H:=Normalizer(G,M); 932 Info(InfoComplement,2,"Call COSolvableFactor ",Index(G,N)," ", 933 Size(N)," ",Size(M)," ",Size(H)); 934 if Size(ClosureGroup(N,H))<Size(G) then 935 #Print("discard\n"); 936 return []; 937 fi; 938 939 K:=ClosureGroup(M,Intersection(H,N)); 940 f:=Size(H)/Size(K); 941 942 # find prime that gives normal characteristic subgroup 943 primes:=PrimeDivisors(f); 944 if Length(primes)=1 then 945 p:=primes[1]; 946 A:=H; 947 else 948 while Length(primes)>0 do 949 p:=primes[1]; 950 A:=ClosureGroup(K,SylowSubgroup(H,p)); 951 #Print(Index(A,K)," in ",Index(H,K),"\n"); 952 A:=Core(H,A); 953 if Size(A)>Size(K) then 954 # found one. Doesn't need to be elementary abelian 955 if not IsPrimePowerInt(Size(A)/Size(K)) then 956 Error("multiple primes"); 957 else 958 primes:=[]; 959 fi; 960 else 961 primes:=primes{[2..Length(primes)]}; # next one 962 fi; 963 od; 964 fi; 965 966 #if HasAbelianFactorGroup(A,K) then 967 # pcgs:=ModuloPcgs(A,K); 968 # S:=LinearActionLayer(H,pcgs); 969 # S:=GModuleByMats(S,GF(p)); 970 # L:=MTX.BasesMinimalSubmodules(S); 971 # if Length(L)>0 then 972 # Sort(L,function(a,b) return Length(a)<Length(b);end); 973 # L:=List(L[1],x->PcElementByExponents(pcgs,x)); 974 # A:=ClosureGroup(K,L); 975 ## fi; 976 #else 977 # Print("IDX",Index(A,K),"\n"); 978 #fi; 979 980 S:=ClosureGroup(M,SylowSubgroup(A,p)); 981 L:=Normalizer(H,S); 982 983 # determine complements up to L-conjugacy. Currently brute-force 984 hom:=NaturalHomomorphismByNormalSubgroup(L,M); 985 986 q:=Image(hom); 987 if IsSolvableGroup(q) and not IsPcGroup(q) then 988 hom:=hom*IsomorphismSpecialPcGroup(q); 989 q:=Image(hom); 990 fi; 991 #q:=Group(SmallGeneratingSet(q),One(q)); 992 qs:=Image(hom,S); 993 qn:=Image(hom,Intersection(L,K)); 994 qk:=Image(hom,Intersection(S,K)); 995 shom:=NaturalHomomorphismByNormalSubgroup(qs,qk); 996 ser:=ElementaryAbelianSeries([q,qs,qk]); 997 pos:=Position(ser,qk); 998 Info(InfoComplement,2,"Series ",List(ser,Size),pos); 999 c:=[qs]; 1000 cn:=[q]; 1001 for i in [pos+1..Length(ser)] do 1002 pcgs:=ModuloPcgs(ser[i-1],ser[i]); 1003 nc:=[]; 1004 ncn:=[]; 1005 for j in [1..Length(c)] do 1006 ocr:=OneCocycles(c[j],pcgs); 1007 shomgens:=List(ocr.generators,x->Image(shom,x)); 1008 if ocr.isSplitExtension then 1009 subbas:=Basis(ocr.oneCoboundaries); 1010 1011 bas:=BaseSteinitzVectors(BasisVectors(Basis(ocr.oneCocycles)), 1012 BasisVectors(subbas)); 1013 lnc:=[]; 1014 lncn:=[]; 1015 Info(InfoComplement,2,"Step ",i,",",j,": ", 1016 p^Length(bas.factorspace)," Complements"); 1017 elm:=VectorSpace(GF(p),bas.factorspace,Zero(ocr.oneCocycles)); 1018 if Length(bas.factorspace)=0 then 1019 elm:=AsSSortedList(elm); 1020 else 1021 elm:=Enumerator(elm); 1022 fi; 1023 mark:=BlistList([1..Length(elm)],[]); 1024 1025 # we act on cocycles, not cocycles modulo coboundaries. This is 1026 # because orbits are short, and we otherwise would have to do a 1027 # double stabilizer calculation to obtain the normalizer. 1028 acterlist:=[]; 1029 free:=FreeGroup(Length(ocr.generators)); 1030 #cn[j]:=Group(SmallGeneratingSet(cn[j])); 1031 for z in GeneratorsOfGroup(cn[j]) do 1032 nz:=[z]; 1033 gp:=List(ocr.generators,x->Image(shom,x^z)); 1034 if gp=shomgens then 1035 # no action on qs/qk -- action on cohomology is affine 1036 1037 # linear part 1038 mat:=[]; 1039 for k in BasisVectors(Basis(GF(p)^Length(Zero(ocr.oneCocycles)))) do 1040 k:=ocr.listToCocycle(List(ocr.cocycleToList(k),x->x^z)); 1041 Add(mat,k); 1042 od; 1043 mat:=ImmutableMatrix(GF(p),mat); 1044 Add(nz,mat); 1045 1046 # affine part 1047 mat:=ocr.listToCocycle(List(ocr.complementGens,x->Comm(x,z))); 1048 ConvertToVectorRep(mat,GF(p)); 1049 MakeImmutable(mat); 1050 Add(nz,mat); 1051 1052 if IsOne(nz[2]) and IsZero(nz[3]) then 1053 nz[4]:=fail; # indicate that element does not act 1054 fi; 1055 1056 else 1057 gp:=GroupWithGenerators(gp); 1058 SetEpimorphismFromFreeGroup(gp,GroupHomomorphismByImages(free, 1059 gp,GeneratorsOfGroup(free),GeneratorsOfGroup(gp))); 1060 Add(nz,List(shomgens,x->Factorization(gp,x))); 1061 fi; 1062 1063 Add(acterlist,nz); 1064 od; 1065 actfun:=function(cy,a) 1066 local genpos,l; 1067 genpos:=PositionProperty(acterlist,x->a=x[1]); 1068 if genpos=fail then 1069 if IsOne(a) then 1070 # the action test always does the identity, so its worth 1071 # catching this as we have many short orbits 1072 return cy; 1073 else 1074 return ocr.complementToCocycle(ocr.cocycleToComplement(cy)^a); 1075 fi; 1076 elif Length(acterlist[genpos])=4 then 1077 # no action 1078 return cy; 1079 elif Length(acterlist[genpos])=3 then 1080 # affine case 1081 l:=cy*acterlist[genpos][2]+acterlist[genpos][3]; 1082 else 1083 l:=ocr.cocycleToList(cy); 1084 l:=List([1..Length(l)],x->(ocr.complementGens[x]*l[x])^a); 1085 if acterlist[genpos][2]<>fail then 1086 l:=List(acterlist[genpos][2], 1087 x->MappedWord(x,GeneratorsOfGroup(free),l)); 1088 fi; 1089 l:=List([1..Length(l)],x->LeftQuotient(ocr.complementGens[x],l[x])); 1090 l:=ocr.listToCocycle(l); 1091 fi; 1092 1093 #if l<>ocr.complementToCocycle(ocr.cocycleToComplement(cy)^a) then Error("ACT");fi; 1094 return l; 1095 end; 1096 pos:=1; 1097 repeat 1098 #z:=ClosureGroup(ser[i],ocr.cocycleToComplement(elm[pos])); 1099 1100 orb:=OrbitStabilizer(cn[j],elm[pos],actfun); 1101 mark[pos]:=true; 1102 #cnt:=1; 1103 for k in [2..Length(orb.orbit)] do 1104 pos2:=Position(elm,SiftedVector(subbas,orb.orbit[k])); 1105 #if mark[pos2]=false then cnt:=cnt+1;fi; 1106 mark[pos2]:=true; # mark orbit off 1107 od; 1108 #Print(cnt,"/",Length(orb.orbit),"\n"); 1109 if IsSubset(orb.stabilizer,qn) then 1110 cond:=Size(orb.stabilizer)=Size(q); 1111 else 1112 cond:=Size(ClosureGroup(qn,orb.stabilizer))=Size(q); 1113 fi; 1114 if cond then 1115 # normalizer is still large enough to keep the complement 1116 Add(lnc,ClosureGroup(ser[i],ocr.cocycleToComplement(elm[pos]))); 1117 Add(lncn,orb.stabilizer); 1118 fi; 1119 1120 pos:=Position(mark,false); 1121 until pos=fail; 1122 Info(InfoComplement,2,Length(lnc)," good normalizer orbits"); 1123 1124 Append(nc,lnc); 1125 Append(ncn,lncn); 1126 fi; 1127 od; 1128 c:=nc; 1129 cn:=ncn; 1130 od; 1131 1132 c:=List(c,x->PreImage(hom,x)); 1133 #c:=SubgroupsOrbitsAndNormalizers(K,c,false); 1134 #c:=List(c,x->x.representative); 1135 1136 # only if not cyclic 1137 if Length(c)>1 and not IsCyclic(c[1]) then 1138 nc:=PermPreConjtestGroups(K,c); 1139 else 1140 nc:=[[K,c]]; 1141 fi; 1142 1143 Info(InfoComplement,2,Length(c)," Preimages in ",Length(nc)," clusters "); 1144 c:=[]; 1145 for i in nc do 1146 cn:=SubgroupsOrbitsAndNormalizers(i[1],i[2],false); 1147 Add(c,List(cn,x->x.representative)); 1148 od; 1149 1150 Info(InfoComplement,1,"Overall ",Sum(c,Length)," Complements ", 1151 Size(qs)/Size(qk)); 1152 1153 if keep then 1154 return c; 1155 else 1156 c:=Concatenation(c); 1157 fi; 1158 if Size(A)<Size(H) then 1159 # recursively do the next step up 1160 cn:=List(c,x->COSolvableFactor(G,N,x)); 1161 nc:=Concatenation(cn); 1162 c:=nc; 1163 fi; 1164 return c; 1165end); 1166 1167 1168 1169############################################################################# 1170## 1171#M ComplementClassesRepresentatives( <G>, <N> ) . . . . find all complement 1172## 1173InstallMethod( ComplementClassesRepresentatives, 1174 "solvable normal subgroup or factor group", 1175 IsIdenticalObj, [IsGroup,IsGroup],0, 1176function( G, N ) 1177 local C; 1178 1179 # if <G> and <N> are equal the only complement is trivial 1180 if G = N then 1181 C:=[TrivialSubgroup(G)]; 1182 1183 # if <N> is trivial the only complement is <G> 1184 elif Size(N) = 1 then 1185 C:=[G]; 1186 1187 elif not IsNormal(G,N) then 1188 Error("N must be normal in G"); 1189 elif IsSolvableGroup(N) then 1190 # otherwise we have to work 1191 C:=ComplementClassesRepresentativesSolvableNC(G,N); 1192 elif HasSolvableFactorGroup(G,N) then 1193 C:=COSolvableFactor(G,N,TrivialSubgroup(G)); 1194 else 1195 TryNextMethod(); 1196 fi; 1197 1198 # return what we have found 1199 return C; 1200 1201end); 1202 1203 1204############################################################################# 1205## 1206#M ComplementcClassesRepresentatives( <G>, <N> ) 1207## 1208InstallMethod( ComplementClassesRepresentatives, 1209 "tell that the normal subgroup or factor must be solvable", IsIdenticalObj, 1210 [ IsGroup, IsGroup ], {} -> -2*RankFilter(IsGroup), 1211function( G, N ) 1212 if IsSolvableGroup(N) or HasSolvableFactorGroup(G, N) then 1213 TryNextMethod(); 1214 fi; 1215 Error("cannot compute complements if both N and G/N are nonsolvable"); 1216end); 1217 1218 1219############################################################################# 1220## 1221#M ComplementcClassesRepresentatives( <G>, <N> ) . from conj. cl. subgroups 1222## 1223InstallMethod( ComplementClassesRepresentatives, 1224 "using conjugacy classes of subgroups", IsIdenticalObj, 1225 [ IsGroup and HasConjugacyClassesSubgroups, IsGroup ], 0, 1226 1227function( G, N ) 1228 1229 local C, Hc, H; 1230 1231 # if <N> is trivial the only complement is <G> 1232 if IsTrivial(N) then 1233 C := [ G ]; 1234 # if <G> and <N> are equal the only complement is trivial 1235 elif G = N then 1236 C := [ TrivialSubgroup(G) ]; 1237 elif not IsNormal(G, N) then 1238 Error("N must be normal in G"); 1239 else 1240 C := [ ]; 1241 for Hc in ConjugacyClassesSubgroups(G) do 1242 H := Representative(Hc); 1243 if (( CanComputeSize(G) and CanComputeSize(N) and CanComputeSize(H) and 1244 Size(G) = Size(N)*Size(H) ) or G = ClosureGroup(N, H) ) 1245 and IsTrivial(Intersection(N, H)) then 1246 Add(C, H); 1247 fi; 1248 od; 1249 fi; 1250 return C; 1251end); 1252