1############################################################################# 2## 3## This file is part of GAP, a system for computational discrete algebra. 4## This file's authors include Hans Ulrich Besche, Thomas Breuer. 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 character table methods for solvable groups. 12## 13 14 15############################################################################# 16## 17#M CharacterDegrees( <G>, <p> ) . . . . . . . . . . . for an abelian group 18## 19InstallMethod( CharacterDegrees, 20 "for an abelian group, and an integer p (just strip off the p-part)", 21 [ IsGroup and IsAbelian, IsInt ], 22 {} -> RankFilter(IsZeroCyc), # There is a method for groups for 23 # the integer zero which is worse 24 function( G, p ) 25 G:= Size( G ); 26 if p <> 0 then 27 while G mod p = 0 do 28 G:= G / p; 29 od; 30 fi; 31 return [ [ 1, G ] ]; 32 end ); 33 34 35############################################################################# 36## 37#F AppendCollectedList( <list1>, <list2> ) 38## 39BindGlobal( "AppendCollectedList", function( list1, list2 ) 40 local pair1, pair2, toadd; 41 for pair2 in list2 do 42 toadd:= true; 43 for pair1 in list1 do 44 if pair1[1] = pair2[1] then 45 pair1[2]:= pair1[2] + pair2[2]; 46 toadd:= false; 47 break; 48 fi; 49 od; 50 if toadd then 51 AddSet( list1, pair2 ); 52 fi; 53 od; 54end ); 55 56 57############################################################################# 58## 59#F KernelUnderDualAction( <N>, <Npcgs>, <v> ) . . . . . . . local function 60## 61## <Npcgs> is a PCGS of an elementary abelian group <N>. 62## <v> is a vector in the dual space of <N>, w.r.t. <Npcgs>. 63## The kernel of <v> is returned. 64## 65BindGlobal( "KernelUnderDualAction", function( N, Npcgs, v ) 66 local gens, # generators list 67 i, j; 68 69 gens:= []; 70 for i in Reversed( [ 1 .. Length( v ) ] ) do 71 if IsZero( v[i] ) then 72 Add( gens, Npcgs[i] ); 73 else 74 # `i' is the position of the last nonzero entry of `v'. 75 for j in Reversed( [ 1 .. i-1 ] ) do 76 Add( gens, Npcgs[j]*Npcgs[i]^( Int(-v[j]/v[i]) ) ); 77 od; 78 return SubgroupNC( N, Reversed( gens ) ); 79 fi; 80 od; 81end ); 82 83 84############################################################################# 85## 86#F ProjectiveCharDeg( <G> ,<z> ,<q> ) 87## 88InstallGlobalFunction( ProjectiveCharDeg, function( G, z, q ) 89 local oz, # the order of `z' 90 N, # normal subgroup of `G' 91 t, 92 r, # collected list of character degrees, result 93 h, # natural homomorphism 94 img, 95 k, 96 c, 97 ci, 98 zn, 99 i, 100 p, # prime divisor of the size of `N' 101 P, # Sylow `p' subgroup of `N' 102 O, 103 L, 104 Gpcgs, # PCGS of `G' 105 Ppcgs, # PCGS of `P' 106 Opcgs, # PCGS of `O' 107 mats, 108 orbs, 109 orb, # loop over `orbs' 110 stab; # stabilizer of canonical representative of `orb' 111 112 oz:= Order( z ); 113 114 # For abelian groups, there are only linear characters. 115 if IsAbelian( G ) then 116 G:= Size( G ); 117 if q <> 0 then 118 while G mod q = 0 do 119 G:= G / q; 120 od; 121 fi; 122 return [ [ 1, G/oz ] ]; 123 fi; 124 125 # Now `G' is not abelian. 126 h:= NaturalHomomorphismByNormalSubgroupNC( G, SubgroupNC( G, [ z ] ) ); 127 img:= ImagesSource( h ); 128 N:= ElementaryAbelianSeriesLargeSteps( img ); 129 N:= N[ Length( N )-1 ]; 130 if not IsPrime( Size( N ) ) then 131 N:= ChiefSeriesUnderAction( img, N ); 132 N:= N[ Length( N )-1 ]; 133 fi; 134 135 # `N' is a normal subgroup such that `N/<z>' is a chief factor of `G' 136 # of order `i' which is a power of `p'. 137 N:= PreImagesSet( h, N ); 138 i:= Size( N ) / oz; 139 p:= Factors( i )[1]; 140 141 if not IsAbelian( N ) then 142 143 h:= NaturalHomomorphismByNormalSubgroupNC( G, SubgroupNC( G, [ z ] ) ); 144 145 # `c' is a list of complement classes of `N' modulo `z' 146 c:= List( ComplementClassesRepresentatives( ImagesSource( h ), ImagesSet( h, N ) ), 147 x -> PreImagesSet( h, x ) ); 148 r:= Centralizer( G, N ); 149 for L in c do 150 if IsSubset( L, r ) then 151 152 # L is a complement to N in G modulo <z> which centralizes N 153 r:= RootInt( Size(N) / oz ); 154 return List( ProjectiveCharDeg( L, z, q ), 155 x -> [ x[1]*r, x[2] ] ); 156 157 fi; 158 od; 159 Error( "this should not happen" ); 160 161 fi; 162 163 # `N' is abelian, `P' is its Sylow `p' subgroup. 164 P:= SylowSubgroup( N, p ); 165 166 if p = q then 167 168 # Factor out `P' (lies in the kernel of the repr.) 169 h:= NaturalHomomorphismByNormalSubgroupNC( G, P ); 170 return ProjectiveCharDeg( ImagesSource( h ), ImageElm( h, z ), q ); 171 172 elif i = Size( P ) then 173 174 # `z' is a p'-element, `P' is elementary abelian. 175 # Find the characters of the factor group needed. 176 h:= NaturalHomomorphismByNormalSubgroupNC( G, P ); 177 r:= ProjectiveCharDeg( ImagesSource( h ), ImageElm( h, z ), q ); 178 179 if p = i then 180 181 # `P' has order `p'. 182 zn:= First( GeneratorsOfGroup( P ), g -> not IsOne( g ) ); 183 t:= Stabilizer( G, zn ); 184 i:= Size(G) / Size(t); 185 AppendCollectedList( r, 186 List( ProjectiveCharDeg( t, zn*z, q ), 187 x -> [ x[1]*i, x[2]*(p-1)/i ] ) ); 188 return r; 189 190 else 191 192 # `P' has order strictly larger than `p'. 193 # `mats' describes the contragredient operation of `G' on `P'. 194 Gpcgs:= Pcgs( G ); 195 Ppcgs:= Pcgs( P ); 196 mats:= List( List( Gpcgs, Inverse ), 197 x -> TransposedMat( List( Ppcgs, 198 y -> ExponentsConjugateLayer( Ppcgs, y,x ) )*Z(p)^0 ) ); 199 orbs:= ExternalOrbitsStabilizers( G, 200 NormedRowVectors( GF(p)^Length( Ppcgs ) ), 201 Gpcgs, mats, OnLines ); 202 orbs:= Filtered( orbs, 203 o -> not IsZero( CanonicalRepresentativeOfExternalSet( o ) ) ); 204 205 for orb in orbs do 206 207 # `k' is the kernel of the character. 208 stab:= StabilizerOfExternalSet( orb ); 209 h:= NaturalHomomorphismByNormalSubgroupNC( stab, 210 KernelUnderDualAction( P, Ppcgs, 211 CanonicalRepresentativeOfExternalSet( orb ) ) ); 212 img:= ImagesSource( h ); 213 214 # `zn' is an element of `img'. 215 # Note that the image of `P' under `h' has order `p'. 216 zn:= First( GeneratorsOfGroup( ImagesSet( h, P) ), 217 g -> not IsOne( g ) ) 218 * ImageElm( h, z ); 219 220 # `c' is stabilizer of the character, 221 # `ci' is the number of orbits of characters with equal kernels 222 if p = 2 then 223 c := img; 224 ci := 1; 225 else 226 c := Stabilizer( img, zn ); 227 ci := Size( img ) / Size( c ); 228 fi; 229 k:= Size( G ) / Size( stab ) * ci; 230 AppendCollectedList( r, 231 List( ProjectiveCharDeg( c, zn, q ), 232 x -> [ x[1]*k, x[2]*(p-1)/ci ] ) ); 233 234 od; 235 return r; 236 237 fi; 238 239 elif IsCyclic( P ) then 240 241 # Choose a generator `zn' of `P'. 242 zn := Pcgs( P )[1]; 243 t := Stabilizer( G, zn, OnPoints ); 244 if G = t then 245 # `P' is a central subgroup of `G'. 246 return List( ProjectiveCharDeg( G, zn*z, q ), 247 x -> [ x[1], x[2]*p ] ); 248 else 249 # `P' is not central in `G'. 250 return List( ProjectiveCharDeg( t, zn*z, q ), 251 x -> [ x[1]*p, x[2] ] ); 252 fi; 253 254 fi; 255 256 # `P' is the direct product of the Sylow `p' subgroup of `z' 257 # and an elementary abelian `p' subgroup. 258 O:= Omega( P, p ); 259 Opcgs:= Pcgs( O ); 260 Gpcgs:= Pcgs( G ); 261 262 # `zn' is a generator of the intersection of <z> and `O' 263 zn := z^(oz/p); 264 r := []; 265 mats:= List( List( Gpcgs, Inverse ), 266 x -> TransposedMat( List( Opcgs, 267 y -> ExponentsConjugateLayer( Opcgs, y,x ) ) * Z(p)^0 ) ); 268 orbs:= ExternalOrbitsStabilizers( G, 269 NormedRowVectors( GF(p)^Length( Opcgs ) ), 270 Gpcgs, mats, OnLines ); 271 orbs:= Filtered( orbs, 272 o -> not IsZero( CanonicalRepresentativeOfExternalSet( o ) ) ); 273 274 # In this case the stabilzers of the kernels are already the 275 # stabilizers of the characters. 276 for orb in orbs do 277 k:= KernelUnderDualAction( O, Opcgs, 278 CanonicalRepresentativeOfExternalSet( orb ) ); 279 if not zn in k then 280 # The kernel avoids `zn'. 281 t:= StabilizerOfExternalSet( orb ); 282 h:= NaturalHomomorphismByNormalSubgroupNC( t, k ); 283 img:= ImagesSource( h ); 284 t:= Size(G) / Size(t); 285 AppendCollectedList( r, List( ProjectiveCharDeg( img, 286 ImageElm( h, z ), q ), 287 x -> [ x[1]*t, x[2] ] ) ); 288 fi; 289 od; 290 return r; 291end ); 292 293 294############################################################################# 295## 296#M CharacterDegrees( <G>, <p> ) . . . . . . . . . . . for a solvable group 297## 298## The algorithm used is based on~\cite{Con90b}, 299## its main tool is Clifford theory. 300## 301## Given a solvable group $G$ and a nonnegative integer $q$, 302## we first choose an elementary abelian normal subgroup $N$. 303## (Note that $N$ need not be a *minimal* normal subgroup, this requirement 304## in~\cite{Con90b} applies only to the computation of projective degrees 305## where nonabelian normal subgroups $N$ occur.) 306## By recursion, the $q$-modular character degrees of the factor group $G/N$ 307## are computed next. 308## So it remains to compute the degrees of those $q$-modular irreducible 309## characters whose kernels do not contain $N$. 310## This last step follows~\cite{Con90b}, for the special case of a *trivial* 311## central subgroup $Z$. 312## Namely, we compute the $G$-orbits on the linear spaces of the nontrivial 313## irreducible characters of $N$, under projective action. 314## (The orbit consisting of the trivial character corresponds to those 315## $q$-modular irreducible $G$-characters with $N$ in their kernels.) 316## For each orbit, we use the function `ProjectiveCharDeg' to compute the 317## degrees arising from a representative $\chi$, 318## in the group $S/K$ with central cyclic subgroup $N/K$, 319## where $S$ is the (subspace) stabilizer of $\chi$ and $K$ is the kernel of 320## $\chi$. 321## 322## One recursive step of the algorithm is described in the following. 323## 324## Let $G$ be a solvable group, $z$ a central element in $G$, 325## and let $q$ be the characteristic of the algebraic closed field $F$. 326## Without loss of generality, we may assume that $G$ is nonabelian. 327## Consider a faithful linear character $\lambda$ of $\langle z \rangle$. 328## We calculate the character degrees $(G,z,q)$ of those absolutely 329## irreducible characters of $G$ whose restrictions to $\langle z \rangle$ 330## are a multiple of $\lambda$. 331## 332## We choose a normal subgroup $N$ of $G$ such that the factor 333## $N / \langle z \rangle$ is a chief factor in $G$, and consider 334## the following cases. 335## 336## If $N$ is nonabelian then we calculate a subgroup $L$ of $G$ such that 337## $N \cap L = \langle z \rangle$, $L$ centralizes $N$, and $N L = G$. 338## One can show that the order of $N / \langle z \rangle$ is a square $r^2$, 339## and that the degrees $(G,z,q)$ are obtained from the degrees $(L,z,q)$ 340## on multiplying each with $r$. 341## 342## If $N$ is abelian then the order of $N / \langle z \rangle$ is a prime 343## power $p^i$. 344## Let $P$ denote the Sylow $p$ subgroup of $N$. 345## Following Clifford's theorem, we calculate orbit representatives and 346## inertia subgroups with respect to the action of $G$ on those irreducible 347## characters of $P$ that restrict to multiples of $\lambda_P$. 348## For that, we distinguish three cases. 349## \beginlist 350## \item{(a)} 351## $z$ is a $p^{\prime}$ element. 352## Then we compute first the character degrees $(G/P,zP,q)$, 353## corresponding to the (orbit of the) trivial character. 354## The action on the nontrivial irreducible characters of $P$ 355## is dual to the action on the nonzero vectors of the vector space 356## $P$. 357## For each representative, we compute the kernel $K$, and the degrees 358## $(S/K,zK,q)$, where $S$ denotes the inertia subgroup. 359## 360## \item{(b)} 361## $z$ is not a $p^{\prime}$ element, and $P$ cyclic (not prime order). 362## Let $y$ be a generator of $P$. 363## If $y$ is central in $G$ then we have to return $p$ copies of the 364## degrees $(G,zy,q)$. 365## Otherwise we compute the degrees $(C_G(y),zy,q)$, and multiply 366## each with $p$. 367## 368## \item{(c)} 369## $z$ is not a $p^{\prime}$ element, and $P$ is not cyclic. 370## We compute $O = \Omega(P)$. 371## As above, we consider the dual operation to that in $O$, 372## and for each orbit representative we check whether its restriction 373## to $O$ is a multiple of $\lambda_O$, and if yes compute the degrees 374## $(S/K,zK,q)$. 375## \endlist 376## 377BindGlobal( "CharacterDegreesConlon", function( G, q ) 378 local r, # list of degrees, result 379 N, # elementary abelian normal subgroup of `G' 380 p, # prime divisor of the order of `N' 381 z, # one generator of `N' 382 t, # stabilizer of `z' in `G' 383 i, # index of `t' in `G' 384 Gpcgs, # PCGS of `G' 385 Npcgs, # PCGS of `N' 386 mats, # matrices describing the action of `Gpcgs' w.r.t. `Npcgs' 387 orbs, # orbits of the action 388 orb, # loop over `orbs' 389 rep, # canonical representative of `orb' 390 stab, # stabilizer of `rep' 391 h, # nat. hom. by the kernel of a character 392 img, # image of `h' 393 c, 394 ci, 395 k; 396 397 Info( InfoCharacterTable, 1, 398 "CharacterDegrees: called for group of order ", Size( G ) ); 399 400 # If the group is abelian, we must give up because this method 401 # needs a proper elementary abelian normal subgroup for its 402 # reduction step. 403 # (Note that we must not call `TryNextMethod' because the method 404 # for abelian groups has higher rank.) 405 if IsAbelian( G ) then 406 r:= CharacterDegrees( G, q ); 407 Info( InfoCharacterTable, 1, 408 "CharacterDegrees: returns ", r ); 409 return r; 410 elif not ( q = 0 or IsPrimeInt( q ) ) then 411 Error( "<q> mut be zero or a prime" ); 412 fi; 413 414 # Choose a normal elementary abelian `p'-subgroup `N', 415 # not necessarily minimal. 416 N:= ElementaryAbelianSeriesLargeSteps( G ); 417 N:= N[ Length( N ) - 1 ]; 418 r:= CharacterDegrees( G / N, q ); 419 p:= Factors( Size( N ) )[1]; 420 421 if p = q then 422 423 # If `N' is a `q'-group we are done. 424 Info( InfoCharacterTable, 1, 425 "CharacterDegrees: returns ", r ); 426 return r; 427 428 elif Size( N ) = p then 429 430 # `N' is of prime order. 431 z:= Pcgs( N )[1]; 432 t:= Stabilizer( G, z, OnPoints ); 433 i:= Size( G ) / Size( t ); 434 AppendCollectedList( r, List( ProjectiveCharDeg( t, z, q ), 435 x -> [ x[1]*i, x[2]*(p-1)/i ] ) ); 436 437 else 438 439 # `N' is an elementary abelian `p'-group of nonprime order. 440 Gpcgs:= Pcgs( G ); 441 Npcgs:= Pcgs( N ); 442 mats:= List( Gpcgs, x -> TransposedMat( List( Npcgs, 443 y -> ExponentsConjugateLayer( Npcgs, y,x ) ) * Z(p)^0 )^-1 ); 444 orbs:= ExternalOrbitsStabilizers( G, 445 NormedRowVectors( GF( p )^Length( Npcgs ) ), 446 Gpcgs, mats, OnLines ); 447#T may fail because the list is too long! 448 orbs:= Filtered( orbs, 449 o -> not IsZero( CanonicalRepresentativeOfExternalSet( o ) ) ); 450 451 for orb in orbs do 452 453 stab:= StabilizerOfExternalSet( orb ); 454 rep:= CanonicalRepresentativeOfExternalSet( orb ); 455 h:= NaturalHomomorphismByNormalSubgroupNC( stab, 456 KernelUnderDualAction( N, Npcgs, rep ) ); 457 img:= ImagesSource( h ); 458 459 # The kernel has index `p' in `stab'. 460 z:= First( GeneratorsOfGroup( ImagesSet( h, N ) ), 461 g -> not IsOne( g ) ); 462 if p = 2 then 463 c := img; 464 ci := 1; 465 else 466 c := Stabilizer( img, z ); 467 ci := Size( img ) / Size( c ); 468 fi; 469 k:= Size( G ) / Size( stab ) * ci; 470 AppendCollectedList( r, List( ProjectiveCharDeg( c, z, q ), 471 x -> [ x[1]*k, x[2]*(p-1)/ci ] ) ); 472 473 od; 474 475 fi; 476 477 Info( InfoCharacterTable, 1, 478 "CharacterDegrees: returns ", r ); 479 return r; 480 end ); 481 482InstallMethod( CharacterDegrees, 483 "for a solvable group and an integer (Conlon's algorithm)", 484 [ IsGroup and IsSolvableGroup, IsInt ], 485 {} -> RankFilter(IsZeroCyc), # There is a method for groups for 486 # the integer zero which is worse 487 function( G, q ) 488 if HasIrr( G ) then 489 # Use the known irreducibles. 490 TryNextMethod(); 491 else 492 return CharacterDegreesConlon( G, q ); 493 fi; 494 end ); 495 496 497############################################################################# 498## 499#F CoveringTriplesCharacters( <G>, <z> ) . . . . . . . . . . . . . . . local 500## 501InstallGlobalFunction( CoveringTriplesCharacters, function( G, z ) 502 local oz, 503 h, 504 img, 505 N, 506 t, 507 r, 508 k, 509 c, 510 zn, 511 i, 512 p, 513 P, 514 O, 515 Gpcgs, 516 Ppcgs, 517 Opcgs, 518 mats, 519 orbs, 520 orb; 521 522 # The trivial character will be dealt with separately. 523 if IsTrivial( G ) then 524 return []; 525 fi; 526 527 oz:= Order( z ); 528 if Size( G ) = oz then 529 return [ [ G, TrivialSubgroup( G ), z ] ]; 530 fi; 531 532 h:= NaturalHomomorphismByNormalSubgroupNC( G, SubgroupNC( G, [ z ] ) ); 533 img:= ImagesSource( h ); 534 N:= ElementaryAbelianSeriesLargeSteps( img ); 535 N:= N[ Length( N ) - 1 ]; 536 if not IsPrime( Size( N ) ) then 537 N:= ChiefSeriesUnderAction( img, N ); 538 N:= N[ Length( N ) - 1 ]; 539 fi; 540 N:= PreImagesSet( h, N ); 541 542 if not IsAbelian( N ) then 543 Info( InfoCharacterTable, 2, 544 "#I misuse of `CoveringTriplesCharacters'!\n" ); 545 return []; 546 fi; 547 548 i:= Size( N ) / oz; 549 p:= Factors( i )[1]; 550 P:= SylowSubgroup( N, p ); 551 552 if i = Size( P ) then 553 554 # `z' is a p'-element, `P' is elementary abelian. 555 # Find the characters of the factor group needed. 556 h:= NaturalHomomorphismByNormalSubgroupNC( G, P ); 557 r:= List( CoveringTriplesCharacters( ImagesSource( h ), 558 ImageElm( h, z ) ), 559 x -> [ PreImagesSet( h, x[1] ), 560 PreImagesSet( h, x[2] ), 561 PreImagesRepresentative( h, x[3] ) ] ); 562 563 if p = i then 564 565 # `P' has order `p'. 566 zn:= First( GeneratorsOfGroup( P ), g -> not IsOne( g ) ); 567 return Concatenation( r, 568 CoveringTriplesCharacters( Stabilizer( G, zn ), zn*z ) ); 569 570 else 571 572 Gpcgs:= Pcgs( G ); 573 Ppcgs:= Pcgs( P ); 574 mats:= List( List( Gpcgs, Inverse ), 575 x -> TransposedMat( List( Ppcgs, 576 y -> ExponentsConjugateLayer( Ppcgs, y,x ) )*Z(p)^0 ) ); 577 orbs:= ExternalOrbitsStabilizers( G, 578 NormedRowVectors( GF(p)^Length( Ppcgs ) ), 579 Gpcgs, mats, OnLines ); 580 orbs:= Filtered( orbs, 581 o -> not IsZero( CanonicalRepresentativeOfExternalSet( o ) ) ); 582 583 for orb in orbs do 584 h:= NaturalHomomorphismByNormalSubgroupNC( 585 StabilizerOfExternalSet( orb ), 586 KernelUnderDualAction( P, Ppcgs, 587 CanonicalRepresentativeOfExternalSet( orb ) ) ); 588 img:= ImagesSource( h ); 589 zn:= First( GeneratorsOfGroup( ImagesSet( h, P ) ), 590 g -> not IsOne( g ) ) 591 * ImageElm( h, z ); 592 593 if p = 2 then 594 c:= img; 595 else 596 c:= Stabilizer( img, zn ); 597 fi; 598 Append( r, List( CoveringTriplesCharacters( c, zn ), 599 x -> [ PreImagesSet( h, x[1] ), 600 PreImagesSet( h, x[2] ), 601 PreImagesRepresentative( h, x[3] ) ] ) ); 602 od; 603 return r; 604 605 fi; 606 607 elif IsCyclic( P ) then 608 609 zn:= Pcgs( P )[1]; 610 return CoveringTriplesCharacters( Stabilizer( G, zn ), zn*z ); 611 612 fi; 613 614 O:= Omega( P, p ); 615 Opcgs:= Pcgs( O ); 616 Gpcgs:= Pcgs( G ); 617 618 zn := z^(oz/p); 619 r := []; 620 mats:= List( List( Gpcgs, Inverse ), 621 x -> TransposedMat( List( Opcgs, 622 y -> ExponentsConjugateLayer( Opcgs, y,x ) )*Z(p)^0 ) ); 623 orbs:= ExternalOrbitsStabilizers( G, 624 NormedRowVectors( GF(p)^Length( Opcgs ) ), 625 Gpcgs, mats, OnLines ); 626 orbs:= Filtered( orbs, 627 o -> not IsZero( CanonicalRepresentativeOfExternalSet( o ) ) ); 628 629 for orb in orbs do 630 k:= KernelUnderDualAction( O, Opcgs, 631 CanonicalRepresentativeOfExternalSet( orb ) ); 632 if not zn in k then 633 t:= StabilizerOfExternalSet( orb ); 634 Assert( 1, IsIdenticalObj( Parent( t ), G ) ); 635 h:= NaturalHomomorphismByNormalSubgroupNC( t, k ); 636 img:= ImagesSource( h ); 637 Append( r, 638 List( CoveringTriplesCharacters( img, ImageElm( h, z ) ), 639 x -> [ PreImagesSet( h, x[1] ), 640 PreImagesSet( h, x[2] ), 641 PreImagesRepresentative( h, x[3] ) ] ) ); 642 fi; 643 od; 644 return r; 645end ); 646 647 648############################################################################# 649## 650#M IrrConlon( <G> ) 651## 652## This algorithm is a generalization of the algorithm to compute the 653## absolutely irreducible degrees of a solvable group to the computation 654## of the absolutely irreducible characters of a supersolvable group, 655## using an idea like in 656## 657## S. B. Conlon, J. Symbolic Computation (1990) 9, 535-550. 658## 659## The function `CoveringTriplesCharacters' is used to compute a list of 660## triples describing linear representations of subgroups of <G>. 661## These linear representations are induced to <G> and then evaluated on 662## representatives of the conjugacy classes. 663## 664## For every irreducible character the monomiality information is stored as 665## value of the attribute `TestMonomial'. 666## 667InstallMethod( IrrConlon, 668 "for a group", 669 [ IsGroup ], 670 function( G ) 671 local mulmoma, # local function: multiply monomial matrices 672 ct, # character table of `G' 673 ccl, # conjugacy classes of `G' 674 Gpcgs, # PCGS of `G' 675 irr, # matrix of character values 676 irredinfo, # monomiality info 677 evl, # encode class representatives as words in `Gpcgs' 678 i, 679 t, 680 chi, 681 j, 682 mat, 683 k, 684 triple, 685 hom, 686 zi, 687 oz, 688 ee, 689 zp, 690 co, # cosets 691 coreps, # representatives of `co' 692 dim, 693 rep, # matrix representation 694 bco, 695 p, 696 i1, # loop variable in `mulmoma' 697 re; # result of `mulmoma' 698 699 # Compute the product of the monomial matrices `a' and `b'; 700 # The diagonal elements are powers of a fixed `oz'-th root of unity. 701 mulmoma:= function( a, b ) 702 re:= rec( perm:= [], diag:= [] ); 703 for i1 in [ 1 .. Length( a.perm ) ] do 704 re.perm[i1]:= b.perm[ a.perm[i1] ]; 705 re.diag[ b.perm[i1] ]:= ( b.diag[ b.perm[i1] ] + a.diag[i1] ) mod oz; 706 od; 707 return re; 708 end; 709 710 ct:= CharacterTable( G ); 711 ccl:= ConjugacyClasses( ct ); 712 Gpcgs:= Pcgs( G ); 713 irr:= []; 714 irredinfo:= [ rec( inducedFrom:= rec( subgroup:= G, kernel:= G ) ) ]; 715 716 # `evl' is a list describing representatives of the nontrivial 717 # conjugacy classes. 718 # the entry for the element $g.1^2*g.2^0*g.3^1$ is $[ 1, 1, 3 ]$. 719 evl:= []; 720 for i in [ 2 .. Length( ccl ) ] do 721 k:= ExponentsOfPcElement( Gpcgs, Representative( ccl[i] ) ); 722 t:= []; 723 for j in [ 1 .. Length( k ) ] do 724 if 0 < k[j] then 725 Append( t, [ 1 .. k[j] ]*0 + j ); 726 fi; 727 od; 728 Add( evl, t ); 729 od; 730 731 for triple in CoveringTriplesCharacters( G, One( G ) ) do 732 733 hom:= NaturalHomomorphismByNormalSubgroupNC( triple[1], triple[2] ); 734 zi:= ImagesRepresentative( hom, triple[3] ); 735 oz:= Order( zi ); 736 ee:= E( oz ); 737 zp:= List( [ 1 .. oz ], x -> zi^x ); 738 co:= RightCosets( G, triple[1] ); 739 coreps:= List( co, Representative ); 740 dim:= Length( co ); 741 742 # `rep' describes a matrix representation on a module with basis 743 # a transversal of the stabilizer in `G'. 744 # (The monomial matrices are the same as in `RepresentationsPGroup'.) 745 rep:= []; 746 for i in Gpcgs do 747 mat:= rec( perm:= [], diag:= [] ); 748 for j in [ 1 .. dim ] do 749 bco:= co[j]*i; 750 p:= Position( co, bco, 0 ); 751 Add( mat.perm, p ); 752 mat.diag[p]:= Position( zp, 753 ImageElm( hom, coreps[j]*i*Inverse( coreps[p] ) ), 0 ); 754 od; 755 Add( rep, mat ); 756 od; 757 758 # Compute the representing matrices for class representatives, 759 # and their traces. 760 chi:= [ dim ]; 761 for j in evl do 762 mat:= Iterated( rep{ j }, mulmoma ); 763 t:= 0; 764 for k in [ 1 .. dim ] do 765 if mat.perm[k] = k then 766 t:= t + ee^mat.diag[k]; 767 fi; 768 od; 769 Add( chi, t ); 770 od; 771 772 # Test if `chi' is known and add `chi' and its Galois-conjugates 773 # to the list. 774 # Also compute the monomiality information. 775 if not chi in irr then 776 chi:= GaloisMat( [ chi ] ).mat; 777 Append( irr, chi ); 778 for j in chi do 779 Add( irredinfo, rec( subgroup:= triple[1], kernel:= triple[2] ) ); 780 od; 781 fi; 782 783 od; 784 785 # Construct the characters from their values lists, 786 # and set the monomiality info. 787 irr:= Concatenation( [ TrivialCharacter( G ) ], 788 List( irr, chi -> Character( ct, chi ) ) ); 789 for i in [ 1 .. Length( irr ) ] do 790 SetTestMonomial( irr[i], irredinfo[i] ); 791 od; 792 793 # Return the characters. 794 return irr; 795 end ); 796 797 798############################################################################# 799## 800#M Irr( <G>, 0 ) . . . . . . for a supersolvable group (Conlon's algorithm) 801## 802InstallMethod( Irr, 803 "for a supersolvable group (Conlon's algorithm)", 804 [ IsGroup and IsSupersolvableGroup, IsZeroCyc ], 805 function( G, zero ) 806 local irr; 807 irr:= IrrConlon( G ); 808 SetIrr( OrdinaryCharacterTable( G ), irr ); 809 return irr; 810 end ); 811 812InstallMethod( Irr, 813 "for a supersolvable group with known `IrrConlon'", 814 [ IsGroup and IsSupersolvableGroup and HasIrrConlon, IsZeroCyc ], 815 function( G, zero ) 816 local irr; 817 irr:= IrrConlon( G ); 818 SetIrr( OrdinaryCharacterTable( G ), irr ); 819 return irr; 820 end ); 821 822 823############################################################################# 824## 825#M Irr( <G>, 0 ) . . . . for a supersolvable group (Baum-Clausen algorithm) 826## 827InstallMethod( Irr, 828 "for a supersolvable group (Baum-Clausen algorithm)", 829 [ IsGroup and IsSupersolvableGroup, IsZeroCyc ], 830 function( G, zero ) 831 local irr; 832 irr:= IrrBaumClausen( G ); 833 SetIrr( OrdinaryCharacterTable( G ), irr ); 834 return irr; 835 end ); 836 837InstallMethod( Irr, 838 "for a supersolvable group with known `IrrBaumClausen'", 839 [ IsGroup and IsSupersolvableGroup and HasIrrBaumClausen, IsZeroCyc ], 840 function( G, zero ) 841 local irr; 842 irr:= IrrBaumClausen( G ); 843 SetIrr( OrdinaryCharacterTable( G ), irr ); 844 return irr; 845 end ); 846 847 848############################################################################# 849## 850#V BaumClausenInfoDebug . . . . . . . . . . . . . . testing BaumClausenInfo 851## 852InstallValue( BaumClausenInfoDebug, rec( 853 makemat:= function( record, e ) 854 local dim, mat, diag, gcd, i; 855 dim:= Length( record.diag ); 856 mat:= NullMat( dim, dim ); 857 diag:= record.diag; 858 gcd:= Gcd( diag ); 859 if gcd = 0 then 860 e:= 1; 861 else 862 gcd:= GcdInt( gcd, e ); 863 e:= E( e / gcd ); 864 diag:= diag / gcd; 865 fi; 866 for i in [ 1 .. dim ] do 867 mat[i][ record.perm[i] ]:= e^diag[ record.perm[i] ]; 868 od; 869 return mat; 870 end, 871 872 testrep:= function( pcgs, rep, e ) 873 local images, hom; 874 images:= List( rep, 875 record -> BaumClausenInfoDebug.makemat( record, e ) ); 876 hom:= GroupGeneralMappingByImagesNC( Group( pcgs ), Group( images ), 877 pcgs, images ); 878 return IsGroupHomomorphism( hom ); 879 end, 880 881 checkconj:= function( pcgs, i, lg, j, rep1, rep2, X, e ) 882 local ii, exps, mat, jj; 883 X:= BaumClausenInfoDebug.makemat( X, e ); 884 for ii in [ i .. lg ] do 885 exps:= ExponentsOfPcElement( pcgs, pcgs[ii]^pcgs[j], [ i .. lg ] ); 886 mat:= One( X ); 887 for jj in [ 1 .. lg-i+1 ] do 888 mat:= mat * BaumClausenInfoDebug.makemat( rep1[jj], e )^exps[jj]; 889 od; 890 if X * mat <> 891 BaumClausenInfoDebug.makemat( rep2[ ii-i+1 ], e ) * X then 892 return false; 893 fi; 894 od; 895 return true; 896 end ) ); 897 898MakeImmutable(BaumClausenInfoDebug); 899 900 901############################################################################# 902## 903#M BaumClausenInfo( <G> ) . . . . . info about irreducible representations 904## 905#T generalize to characteristic p !! 906## 907InstallMethod( BaumClausenInfo, 908 "for a (solvable) group", 909 [ IsGroup ], 910 function( G ) 911 local e, # occurring roots of unity are `e'-th roots 912 pcgs, # Pcgs of `G' 913 lg, # length of `pcgs' 914 cs, # composition series of `G' corresp. to `pcgs' 915 abel, # position of abelian normal comp. subgroup 916 ExtLinRep, # local function 917 indices, # sizes of composition factors in `cs' 918 linear, # list of linear representations 919 i, # current position in the iteration: $G_i$ 920 p, # size of current composition factor 921 pexp, # exponent vector of `pcgs[i]^p' 922 root, # value of an extension 923 roots, # list of $p$-th roots (relative to `e') 924 mulmoma, # product of two monomial matrices 925 poweval, # representing matrix for power of generator 926 pilinear, # action of $g_1, \ldots, g_i$ on `linear' 927 d, j, k, l, # loop variables 928 u, v, w, # loop variables 929 M, # 930 pos, # position in a list 931 nonlin, # list of nonlinear representations 932 pinonlin, # action of $g_1, \ldots, g_i$ on `nonlin' 933 Xlist, # conjugating matrices: 934 # for $X = `Xlist[j][k]'$, we have 935 # $X \cdot {`nonlin[k]'}^{g_j} \cdot X^{-1} = 936 # `nonlin[ pinonlin[j][k] ]'$ 937 min, # 938 minval, # 939 ssr, # 940 next, # 941 X, # one matrix for `Xlist' 942 nextlinear, # extensions of `linear' 943 nextnonlin1, # nonlinear repr. arising from `linear' 944 nextnonlin2, # nonlinear repr. arising from `nonlin' 945 pinextlinear, # action of $g_1, \ldots, g_i$ on `nextlinear' 946 pinextnonlin1, # action of $g_1, \ldots, g_i$ on `nextnonlin1' 947 pinextnonlin2, # action of $g_1, \ldots, g_i$ on `nextnonlin2' 948 nextXlist1, # conjugating matrices for `nextnonlin1' 949 nextXlist2, # conjugating matrices for `nextnonlin2' 950 cexp, # exponent vector of `pcgs[i]^pcgs[j]' 951 poli, # list that encodes `pexp' 952 rep, # one representation 953 D, C, # 954 value, # 955 image, # 956 used, # boolean list 957 Dpos1, # positions of extension resp. induced repres. 958 # that arise from linear representations 959 Dpos2, # positions of extension resp. induced repres. 960 # that arise from nonlinear representations 961 dim, # dimension of the current representation 962 invX, # inverse of `X' 963 D_gi, # 964 hom, # homomorphism to adjust the composition series 965 orb, # 966 Forb, # 967 sigma, pi, # permutations needed in the fusion case 968 constants, # vector $(c_0, c_1, \ldots, c_{p-1})$ 969 kernel; # kernel of `hom' 970 971 if not IsSolvableGroup( G ) then 972 Error( "<G> must be solvable" ); 973 fi; 974 975 976 # Step 0: 977 # Treat the case of the trivial group, 978 # and initialize some variables. 979 980 pcgs:= SpecialPcgs( G ); 981#T because I need a ``prime orders pcgs'' 982 lg:= Length( pcgs ); 983 984 if lg = 0 then 985 return rec( pcgs := pcgs, 986 kernel := G, 987 exponent := 1, 988 nonlin := [], 989 lin := [ [] ] 990 ); 991 fi; 992 993 cs:= PcSeries( pcgs ); 994 995 if HasExponent( G ) then 996 e:= Exponent( G ); 997 else 998 e:= Size(G); 999#T better adjust on the fly 1000 fi; 1001 1002 1003 # Step 1: 1004 # If necessary then adjust the composition series of $G$ 1005 # and get the largest factor group of $G$ that has an abelian normal 1006 # subgroup such that the factor group modulo this subgroup is 1007 # supersolvable. 1008 1009 abel:= 1; 1010 while IsNormal( G, cs[ abel ] ) and not IsAbelian( cs[ abel ] ) do 1011 abel:= abel + 1; 1012 od; 1013 1014 # If `cs[ abel ]' is abelian then we compute its representations first, 1015 # and then loop over the initial part of the composition series; 1016 # note that the factor group is supersolvable. 1017 # If `cs[ abel ]' is not abelian then we try to switch to a better 1018 # composition series, namely one through the derived subgroup of the 1019 # supersolvable residuum. 1020 1021 if not IsNormal( G, cs[ abel ] ) then 1022 1023 # We have reached a non-normal nonabelian composition subgroup 1024 # so we have to adjust the composition series. 1025 1026 Info( InfoGroup, 2, 1027 "BaumClausenInfo: switching to a suitable comp. ser." ); 1028 1029 ssr:= SupersolvableResiduumDefault( G ); 1030 hom:= NaturalHomomorphismByNormalSubgroupNC( G, 1031 DerivedSubgroup( ssr.ssr ) ); 1032 1033 # `SupersolvableResiduumDefault' contains a component `ds', 1034 # a list of subgroups such that any composition series through 1035 # `ds' from `G' down to the residuum is a chief series. 1036 pcgs:= []; 1037 for i in [ 2 .. Length( ssr.ds ) ] do 1038 j:= NaturalHomomorphismByNormalSubgroupNC( ssr.ds[ i-1 ], ssr.ds[i] ); 1039 Append( pcgs, List( SpecialPcgs( ImagesSource( j ) ), 1040 x -> PreImagesRepresentative( j, x ) ) ); 1041 od; 1042 Append( pcgs, SpecialPcgs( ssr.ds[ Length( ssr.ds ) ]) ); 1043 G:= ImagesSource( hom ); 1044 pcgs:= List( pcgs, x -> ImagesRepresentative( hom, x ) ); 1045 pcgs:= Filtered( pcgs, x -> Order( x ) <> 1 ); 1046 pcgs:= PcgsByPcSequence( ElementsFamily( FamilyObj( G ) ), pcgs ); 1047 cs:= PcSeries( pcgs ); 1048 lg:= Length( pcgs ); 1049 1050 # The image of `ssr' under `hom' is abelian, 1051 # compute its position in the composition series. 1052 abel:= Position( cs, ImagesSet( hom, ssr.ssr ) ); 1053 1054 # If `G' is supersolvable then `abel = lg+1', 1055 # but the last *nontrivial* member of the chain is normal and abelian, 1056 # so we choose this group. 1057 # (Otherwise we would have the technical problem in step 4 that the 1058 # matrix `M' would be empty.) 1059 if lg < abel then 1060 abel:= lg; 1061 fi; 1062 1063 fi; 1064 1065 # Step 2: 1066 # Compute the representations of `cs[ abel ]', 1067 # each a list of images of $g_{abel}, \ldots, g_{lg}$. 1068 1069 # The local function `ExtLinRep' computes the extensions of the 1070 # linear $G_{i+1}$-representations $F$ in the list `linear' to $G_i$. 1071 # The only condition that must be satisfied is that 1072 # $F(g_i)^p = F(g_i^p)$. 1073 # (Roughly speaking, we just compute $p$-th roots.) 1074 1075 ExtLinRep:= function( i, linear, pexp, roots ) 1076 1077 local nextlinear, rep, j, shift; 1078 1079 nextlinear:= []; 1080 if IsZero( pexp ) then 1081 1082 # $g_i^p$ is the identity 1083 for rep in linear do 1084 for j in roots do 1085 Add( nextlinear, Concatenation( [ j ], rep ) ); 1086 od; 1087 od; 1088 1089 else 1090 1091 pexp:= pexp{ [ i+1 .. lg ] }; 1092#T cut this outside the function! 1093 for rep in linear do 1094 1095 # Compute the value of `rep' on $g_i^p$. 1096 shift:= pexp * rep; 1097 1098 if shift mod p <> 0 then 1099 # We must enlarge the exponent. 1100 Error("wrong exponent"); 1101#T if not integral then enlarge the exponent! 1102#T (is this possible here at all?) 1103 fi; 1104 shift:= shift / p; 1105 for j in roots do 1106 Add( nextlinear, Concatenation( [ (j+shift) mod e ], rep ) ); 1107 od; 1108 1109 od; 1110 1111 fi; 1112 1113 return nextlinear; 1114 end; 1115 1116 1117 indices:= RelativeOrders( pcgs ); 1118#T here set the exponent `e' to `indices[ lg ]' ! 1119 Info( InfoGroup, 2, 1120 "BaumClausenInfo: There are ", lg, " steps" ); 1121 1122 linear:= List( [ 0 .. indices[lg]-1 ] * ( e / indices[lg] ), 1123 x -> [ x ] ); 1124 1125 for i in [ lg-1, lg-2 .. abel ] do 1126 1127 Info( InfoGroup, 2, 1128 "BaumClausenInfo: Compute repres. of step ", i, 1129 " (central case)" ); 1130 1131 p:= indices[i]; 1132 1133 # `pexp' describes $g_i^p$. 1134 pexp:= ExponentsOfRelativePower( pcgs,i); 1135# { ? } ?? 1136 1137 root:= e/p; 1138#T enlarge the exponent if necessary! 1139 roots:= [ 0, root .. (p-1)*root ]; 1140 linear:= ExtLinRep( i, linear, pexp, roots ); 1141 1142 od; 1143 1144 # We are done if $G$ is abelian. 1145 if abel = 1 then 1146 return rec( pcgs := pcgs, 1147 kernel := TrivialSubgroup( G ), 1148 exponent := e, 1149 nonlin := [], 1150 lin := linear 1151 ); 1152 fi; 1153 1154 1155 # Step 3: 1156 # Define some local functions. 1157 # (We did not need them for abelian groups.) 1158 1159 # `mulmoma' returns the product of two monomial matrices. 1160 mulmoma:= function( a, b ) 1161 local prod, i; 1162 prod:= rec( perm := b.perm{ a.perm }, 1163 diag := [] ); 1164 for i in [ 1 .. Length( a.perm ) ] do 1165 prod.diag[ b.perm[i] ]:= ( b.diag[ b.perm[i] ] + a.diag[i] ) mod e; 1166 od; 1167 return prod; 1168 end; 1169 1170 # `poweval' evaluates the representation `rep' on the $p$-th power of 1171 # the conjugating element. 1172 # This $p$-th power is described by `poli'. 1173 poweval:= function( rep, poli ) 1174 local pow, i; 1175 if IsEmpty( poli ) then 1176 return rec( perm:= [ 1 .. Length( rep[1].perm ) ], 1177 diag:= [ 1 .. Length( rep[1].perm ) ] * 0 ); 1178 fi; 1179 pow:= rep[ poli[1] ]; 1180 for i in [ 2 .. Length( poli ) ] do 1181 pow:= mulmoma( pow, rep[ poli[i] ] ); 1182 od; 1183 return pow; 1184 end; 1185 1186 1187 # Step 4: 1188 # Compute the actions of $g_j$, $j < abel$, on the representations 1189 # of $G_{abel}$. 1190 # Let $g_i^{g_j} = \prod_{k=1}^n g_k^{\alpha_{ik}^j}$, 1191 # and set $A_j = [ \alpha_{ik}^j} ]_{i,k}$. 1192 # Then the representation that maps $g_i$ to the root $\zeta_e^{c_i}$ 1193 # is mapped to the representation that has images exponents 1194 # $A_j * (c_1, \ldots, c_n)$ under $g_j$. 1195 1196 Info( InfoGroup, 2, 1197 "BaumClausenInfo: Initialize actions on abelian normal subgroup" ); 1198 1199 pilinear:= []; 1200 for j in [ 1 .. abel-1 ] do 1201 1202 # Compute the matrix $A_j$. 1203 M:= List( [ abel .. lg ], 1204 i -> ExponentsOfPcElement( pcgs, pcgs[i]^pcgs[j], 1205 [ abel .. lg ] ) ); 1206 1207 # Compute the permutation corresponding to the action of $g_j$. 1208 pilinear[j]:= List( linear, 1209 rep -> Position( linear, 1210 List( M * rep, x -> x mod e ) ) ); 1211 1212 od; 1213 1214 1215 # Step 5: 1216 # Run up the composition series from `abel' to `1', 1217 # and compute extensions resp. induced representations. 1218 # For each index, we have to update `linear', `pilinear', 1219 # `nonlin', `pinonlin', and `Xlist'. 1220 1221 nonlin := []; 1222 pinonlin := []; 1223 Xlist := []; 1224 1225 for i in [ abel-1, abel-2 .. 1 ] do 1226 1227 p:= indices[i]; 1228 1229 # `poli' describes $g_i^p$. 1230 #was pexp:= ExponentsOfPcElement( pcgs, pcgs[i]^p ); 1231 pexp:= ExponentsOfRelativePower( pcgs, i ); 1232 poli:= Concatenation( List( [ i+1 .. lg ], 1233 x -> List( [ 1 .. pexp[x] ], 1234 y -> x-i ) ) ); 1235 1236 # `p'-th roots of unity 1237 roots:= [ 0 .. p-1 ] * ( e/p ); 1238 1239 Info( InfoGroup, 2, 1240 "BaumClausenInfo: Compute repres. of step ", i ); 1241 1242 # Step A: 1243 # Compute representations of $G_i$ arising from *linear* 1244 # representations of $G_{i+1}$. 1245 1246 used := BlistList( [ 1 .. Length( linear ) ], [] ); 1247 nextlinear := []; 1248 nextnonlin1 := []; 1249 d := 1; 1250 1251 pexp:= pexp{ [ i+1 .. lg ] }; 1252 1253 # At position `d', store the position of either the first extension 1254 # of `linear[d]' in `nextlinear' or the position of the induced 1255 # representation of `linear[d]' in `nextnonlin1'. 1256 Dpos1:= []; 1257 1258 while d <> fail do 1259 1260 rep:= linear[d]; 1261 used[d]:= true; 1262 1263 # `root' is the value of `rep' on $g_i^p$. 1264 root:= ( pexp * rep ) mod e; 1265 1266 if pilinear[i][d] = d then 1267 1268 # `linear[d]' extends to $G_i$. 1269 Dpos1[d]:= Length( nextlinear ) + 1; 1270 1271 # Take a `p'-th root. 1272 root:= root / p; 1273#T enlarge the exponent if necessary! 1274 1275 for j in roots do 1276 Add( nextlinear, Concatenation( [ root+j ], rep ) ); 1277 od; 1278 1279 else 1280 1281 # We must fuse the representations in the orbit of `d' 1282 # under `pilinear[i]'; 1283 # so we construct the induced representation `D'. 1284 1285 Dpos1[d]:= Length( nextnonlin1 ) + 1; 1286 1287 D:= List( rep, x -> rec( perm := [ 1 .. p ], 1288 diag := [ x ] 1289 ) ); 1290 pos:= d; 1291 for j in [ 2 .. p ] do 1292 1293 pos:= pilinear[i][ pos ]; 1294 for k in [ 1 .. Length( rep ) ] do 1295 D[k].diag[j]:= linear[ pos ][k]; 1296 od; 1297 used[ pos ]:= true; 1298 Dpos1[ pos ]:= Length( nextnonlin1 ) + 1; 1299 1300 od; 1301 1302 Add( nextnonlin1, 1303 Concatenation( [ rec( perm := Concatenation( [p], [1..p-1]), 1304 diag := Concatenation( [ 1 .. p-1 ] * 0, 1305 [ root ] ) ) ], 1306 D ) ); 1307 Assert( 2, BaumClausenInfoDebug.testrep( pcgs{ [ i .. lg ] }, 1308 nextnonlin1[ Length( nextnonlin1 ) ], e ), 1309 Concatenation( "BaumClausenInfo: failed assertion in ", 1310 "inducing linear representations ", 1311 "(i = ", String( i ), ")\n" ) ); 1312 1313 fi; 1314 1315 d:= Position( used, false, d ); 1316 1317 od; 1318 1319 1320 # Step B: 1321 # Now compute representations of $G_i$ arising from *nonlinear* 1322 # representations of $G_{i+1}$ (if there are some). 1323 1324 used:= BlistList( [ 1 .. Length( nonlin ) ], [] ); 1325 nextnonlin2:= []; 1326 if Length( nonlin ) = 0 then 1327 d:= fail; 1328 else 1329 d:= 1; 1330 fi; 1331 1332 # At position `d', store the position of the first extension resp. 1333 # of the induced representation of `nonlin[d]'in `nextnonlin2'. 1334 Dpos2:= []; 1335 1336 while d <> fail do 1337 1338 used[d]:= true; 1339 rep:= nonlin[d]; 1340 1341 if pinonlin[i][d] = d then 1342 1343 # The representation $F = `rep'$ has `p' different extensions. 1344 # For `X = Xlist[i][d]', we have $`rep ^ X' = `rep'^{g_i}$, 1345 # i.e., $X^{-1} F X = F^{g_i}$. 1346 # Representing matrix $F(g_i)$ is $c X$ with $c^p X^p = F(g_i^p)$, 1347 # so $c^p X^p.diag[k] = F(g_i^p).diag[k]$ for all $k$ ; 1348 # for determination of $c$ we look at `k = X^p.perm[1]'. 1349 1350 X:= Xlist[i][d]; 1351 image:= X.perm[1]; 1352 value:= X.diag[ image ]; 1353 for j in [ 2 .. p ] do 1354 1355 image:= X.perm[ image ]; 1356 value:= X.diag[ image ] + value; 1357 # now `image = X^j.perm[1]', `value = X^j.diag[ image ]' 1358 1359 od; 1360 1361 # Subtract this from $F(g_i^p).diag[k]$; 1362 # note that `image' is the image of 1 under `X^p', so also 1363 # under $F(g_i^p)$. 1364 value:= - value; 1365 image:= 1; 1366 for j in poli do 1367 image:= rep[j].perm[ image ]; 1368 value:= rep[j].diag[ image ] + value; 1369 od; 1370 1371 value:= ( value / p ) mod e; 1372#T enlarge the exponent if necessary! 1373 1374 Dpos2[d]:= Length( nextnonlin2 ) + 1; 1375 1376 # Compute the `p' extensions. 1377 for k in roots do 1378 Add( nextnonlin2, Concatenation( 1379 [ rec( perm := X.perm, 1380 diag := List( X.diag, 1381 x -> ( x + k + value ) mod e ) ) ], rep ) ); 1382 Assert( 2, BaumClausenInfoDebug.testrep( pcgs{ [ i .. lg ] }, 1383 nextnonlin2[ Length( nextnonlin2 ) ], e ), 1384 Concatenation( "BaumClausenInfo: failed assertion in ", 1385 "extending nonlinear representations ", 1386 "(i = ", String( i ), ")\n" ) ); 1387 od; 1388 1389 else 1390 1391 # `$F$ = nonlin[d]' fuses with `p-1' partners given by the orbit 1392 # of `d' under `pinonlin[i]'. 1393 # The new irreducible representation of $G_i$ will be 1394 # $X Ind( F ) X^{-1}$ with $X$ the block diagonal matrix 1395 # consisting of blocks $X_{i,F}^{(k)}$ defined by 1396 # $X_{i,F}^{(0)} = Id$, 1397 # and $X_{i,F}^{(k)} = X_{i,\pi_i^{k-1} F} X_{i,F}^{(k-1)}$ 1398 # for $k > 0$. 1399 1400 # The matrix for $g_i$ in the induced representation $Ind( F )$ is 1401 # of the form 1402 # | 0 F(g_i^p) | 1403 # | I 0 | 1404 # Thus $X Ind(F) X^{-1} ( g_i )$ is the block diagonal matrix 1405 # consisting of the blocks 1406 # $X_{i,F}, X_{i,\pi_i F}, \ldots, X_{i,\pi_i^{p-2} F}$, and 1407 # $F(g_i^p) \cdot ( X_{i,F}^{(p-1)} )^{-1}$. 1408 1409 dim:= Length( rep[1].diag ); 1410 Dpos2[d]:= Length( nextnonlin2 ) + 1; 1411 1412 # We make a copy of `rep' because we want to change it. 1413 D:= List( rep, record -> rec( perm := ShallowCopy( record.perm ), 1414 diag := ShallowCopy( record.diag ) 1415 ) ); 1416 1417 # matrices for $g_j, i\< j \leq n$ 1418 pos:= d; 1419 for j in [ 1 .. p-1 ] * dim do 1420 pos:= pinonlin[i][ pos ]; 1421 for k in [ 1 .. Length( rep ) ] do 1422 Append( D[k].diag, nonlin[ pos ][k].diag ); 1423 Append( D[k].perm, nonlin[ pos ][k].perm + j ); 1424 od; 1425 1426 used[ pos ]:= true; 1427 Dpos2[ pos ]:= Length( nextnonlin2 ) + 1; 1428 1429 od; 1430 1431 # The matrix of $g_i$ is a block-cycle with blocks 1432 # $X_{i,\pi_i^k(F)}$ for $0 \leq k \leq p-2$, 1433 # and $F(g_i^p) \cdot (X_{i,F}^{(p-1)})^{-1}$. 1434 1435 X:= Xlist[i][d]; # $X_{i,F}$ 1436 pos:= d; 1437 for j in [ 1 .. p-2 ] do 1438 pos:= pinonlin[i][ pos ]; 1439 X:= mulmoma( Xlist[i][ pos ], X ); 1440 od; 1441 1442 # `invX' is the inverse of `X'. 1443 invX:= rec( perm := [], diag := [] ); 1444 for j in [ 1 .. Length( X.diag ) ] do 1445 invX.perm[ X.perm[j] ]:= j; 1446 invX.diag[j]:= e - X.diag[ X.perm[j] ]; 1447 od; 1448#T improve this using the {} operator! 1449 1450 X:= mulmoma( poweval( rep, poli ), invX ); 1451 D_gi:= rec( perm:= List( X.perm, x -> x + ( p-1 ) * dim ), 1452 diag:= [] ); 1453 1454 pos:= d; 1455 for j in [ 0 .. p-2 ] * dim do 1456 1457 # $X_{i,\pi_i^j F}$ 1458 Append( D_gi.diag, Xlist[i][ pos ].diag); 1459 Append( D_gi.perm, Xlist[i][ pos ].perm + j); 1460 pos:= pinonlin[i][ pos ]; 1461 1462 od; 1463 1464 Append( D_gi.diag, X.diag ); 1465 1466 Add( nextnonlin2, Concatenation( [ D_gi ], D ) ); 1467 Assert( 2, BaumClausenInfoDebug.testrep( pcgs{ [ i .. lg ] }, 1468 nextnonlin2[ Length( nextnonlin2 ) ], e ), 1469 Concatenation( "BaumClausenInfo: failed assertion in ", 1470 "inducing nonlinear representations ", 1471 "(i = ", String( i ), ")\n" ) ); 1472 1473 fi; 1474 1475 d:= Position( used, false, d ); 1476 1477 od; 1478 1479 1480 # Step C: 1481 # Compute `pilinear', `pinonlin', and `Xlist'. 1482 1483 pinextlinear := []; 1484 pinextnonlin1 := []; 1485 nextXlist1 := []; 1486 1487 pinextnonlin2 := []; 1488 nextXlist2 := []; 1489 1490 for j in [ 1 .. i-1 ] do 1491 1492 pinextlinear[j] := []; 1493 pinextnonlin1[j] := []; 1494 nextXlist1[j] := []; 1495 1496 # `cexp' describes $g_i^{g_j}$. 1497 cexp:= ExponentsOfPcElement( pcgs, pcgs[i]^pcgs[j], [ i .. lg ] ); 1498 1499 # Compute `pilinear', and the parts of `pinonlin', `Xlist' 1500 # arising from *linear* representations for the next step, 1501 # that is, compute the action of $g_j$ on `nextlinear' and 1502 # `nextnonlin1'. 1503 1504 for k in [ 1 .. Length( linear ) ] do 1505 1506 if pilinear[i][k] = k then 1507 1508 # Let $F = `linear[k]'$ extend to 1509 # $D = D_0, D_1, \ldots, D_{p-1}$, 1510 # $C$ the first extension of $\pi_j(F)$. 1511 # We have $D( g_i^{g_j} ) = D^{g_j}(g_i) = ( C \chi^l )(g_i)$ 1512 # where $\chi^l(g_i)$ is the $l$-th power of the chosen 1513 # primitive $p$-th root of unity. 1514 1515 D:= nextlinear[ Dpos1[k] ]; 1516 1517 # `pos' is the position of $C$ in `nextlinear'. 1518 pos:= Dpos1[ pilinear[j][k] ]; 1519 l:= ( ( cexp * D # $D( g_i^{g_j} )$ 1520 - nextlinear[ pos ][1] ) # $C(g_i)$ 1521 * p / e ) mod p; 1522 1523 for u in [ 0 .. p-1 ] do 1524 Add( pinextlinear[j], pos + ( ( l + u * cexp[1] ) mod p ) ); 1525 od; 1526 1527 elif not IsBound( pinextnonlin1[j][ Dpos1[k] ] ) then 1528 1529 # $F$ fuses with its conjugates under $g_i$, 1530 # the conjugating matrix describing the action of $g_j$ 1531 # is a permutation matrix. 1532 # Let $D = F^{g_j}$, then the permutation corresponds to 1533 # the mapping between the lists 1534 # $[ D, (F^{g_i})^{g_j}, \ldots, (F^{g_i^{p-1}})^{g_j} ]$ 1535 # and $[ D, D^{g_i}, \ldots, D^{g_i^{p-1}} ]$; 1536 # The constituents in the first list are the images of 1537 # the induced representation of $F$ under $g_j$, 1538 # and those in the second list are the constituents of the 1539 # induced representation of $D$. 1540 1541 # While `u' runs from $1$ to $p$, 1542 # `pos' runs over the positions of $(F^{g_i^u})^{g_j}$ in 1543 # `linear'. 1544 # `orb' is the list of positions of the $(F^{g_j})^{g_i^u}$, 1545 # cyclically permuted such that the smallest entry is the 1546 # first. 1547 1548 pinextnonlin1[j][ Dpos1[k] ]:= Dpos1[ pilinear[j][k] ]; 1549 pos:= pilinear[j][k]; 1550 orb:= [ pos ]; 1551 min:= 1; 1552 minval:= pos; 1553 for u in [ 2 .. p ] do 1554 pos:= pilinear[i][ pos ]; 1555 orb[u]:= pos; 1556 if pos < minval then 1557 minval:= pos; 1558 min:= u; 1559 fi; 1560 od; 1561 if 1 < min then 1562 orb:= Concatenation( orb{ [ min .. p ] }, 1563 orb{ [ 1 .. min-1 ] } ); 1564 fi; 1565 1566 # Compute the conjugating matrix `X'. 1567 # Let $C$ be the stored representation $\tau_j D$ 1568 # equivalent to $D^{g_j}$. 1569 # Compute the position of $C$ in `pinextnonlin1'. 1570 1571 C:= nextnonlin1[ pinextnonlin1[j][ Dpos1[k] ] ]; 1572 D:= nextnonlin1[ Dpos1[k] ]; 1573 1574 # `sigma' is the bijection of constituents in the restrictions 1575 # of $D$ and $\tau_j D$ to $G_{i-1}$. 1576 # More precisely, $\pi_j(\pi_i^{u-1} F) = \Phi_{\sigma(u-1)}$. 1577 sigma:= []; 1578 pos:= k; 1579 for u in [ 1 .. p ] do 1580 sigma[u]:= Position( orb, pilinear[j][ pos ] ); 1581 pos:= pilinear[i][ pos ]; 1582 od; 1583 1584 # Compute $\pi = \sigma^{-1} (1,2,\ldots,p) \sigma$. 1585 pi:= []; 1586 pi[ sigma[p] ]:= sigma[1]; 1587 for u in [ 1 .. p-1 ] do 1588 pi[ sigma[u] ]:= sigma[ u+1 ]; 1589 od; 1590 1591 # Compute the values $c_{\pi^u(0)}$, for $0 \leq u \leq p-1$. 1592 # Note that $c_0 = 1$. 1593 # (Here we encode of course the exponents.) 1594 constants:= [ 0 ]; 1595 l:= 1; 1596 1597 for u in [ 1 .. p-1 ] do 1598 1599 # Compute $c_{\pi^u(0)}$. 1600 # (We have $`l' = 1 + \pi^{u-1}(0)$.) 1601 # Note that $B_u = [ [ 1 ] ]$ for $0\leq u\leq p-2$, 1602 # and $B_{p-1} = \Phi_0(g_i^p)$. 1603 1604 # Next we compute the image under $A_{\pi^{u-1}(0)}$; 1605 # this matrix is in the $(\pi^{u-1}(0)+1)$-th column block 1606 # and in the $(\pi^u(0)+1)$-th row block of $D^{g_j}$. 1607 # Since we do not have this matrix explicitly, 1608 # we use the conjugate representation and the action 1609 # encoded by `cexp'. 1610 # Note the necessary initial shift because we use the 1611 # whole representation $D$ and not a single constituent; 1612 # so we shift by $\pi^u(0)+1$. 1613#T `perm' is nontrivial only for v = 1, this should make life easier. 1614 value:= 0; 1615 image:= pi[l]; 1616 for v in [ 1 .. lg-i+1 ] do 1617 for w in [ 1 .. cexp[v] ] do 1618 image:= D[v].perm[ image ]; 1619 value:= value + D[v].diag[ image ]; 1620 od; 1621 od; 1622 1623 # Next we divide by the corresponding value in 1624 # the image of the first standard basis vector under 1625 # $B_{\sigma\pi^{u-1}(0)}$. 1626 value:= value - C[1].diag[ sigma[l] ]; 1627 constants[ pi[l] ]:= ( constants[l] - value ) mod e; 1628 l:= pi[l]; 1629 1630 od; 1631 1632 # Put the conjugating matrix together. 1633 X:= rec( perm := [], 1634 diag := constants ); 1635 for u in [ 1 .. p ] do 1636 X.perm[ sigma[u] ]:= u; 1637 od; 1638 1639 Assert( 2, BaumClausenInfoDebug.checkconj( pcgs, i, lg, j, 1640 nextnonlin1[ Dpos1[k] ], 1641 nextnonlin1[ pinextnonlin1[j][ Dpos1[k] ] ], 1642 X, e ), 1643 Concatenation( "BaumClausenInfo: failed assertion on ", 1644 "conjugating matrices for linear repres. ", 1645 "(i = ", String( i ), ")\n" ) ); 1646 nextXlist1[j][ Dpos1[k] ]:= X; 1647 1648 fi; 1649 1650 od; 1651 1652 1653 # Compute the remaining parts of `pinonlin' and `Xlist' for 1654 # the next step, namely for those *nonlinear* representations 1655 # arising from *nonlinear* ones. 1656 1657 nextXlist2[j] := []; 1658 pinextnonlin2[j] := []; 1659 1660 # `cexp' describes $g_i^{g_j}$. 1661 cexp:= ExponentsOfPcElement( pcgs, pcgs[i]^pcgs[j], [ i .. lg ] ); 1662 1663 # Compute the action of $g_j$ on `nextnonlin2'. 1664 1665 for k in [ 1 .. Length( nonlin ) ] do 1666 1667 if pinonlin[i][k] = k then 1668 1669 # Let $F = `nonlin[k]'$ extend to 1670 # $D = D_0, D_1, \ldots, D_{p-1}$, 1671 # $C$ the first extension of $\pi_j(F)$. 1672 # We have $X_{j,F} \cdot F^{g_j} = \pi_j(F) \cdot X_{j,F}$, 1673 # thus $X_{j,F} \cdot D( g_i^{g_j} ) 1674 # = X_{j,F} \cdot D^{g_j}(g_i) 1675 # = ( C \chi^l )(g_i) \cdot X_{j,F}$ 1676 # where $\chi^l(g_i)$ is the $l$-th power of the chosen 1677 # primitive $p$-th root of unity. 1678 1679 D:= nextnonlin2[ Dpos2[k] ]; 1680 1681 # `pos' is the position of $C$ in `nextnonlin2'. 1682 pos:= Dpos2[ pinonlin[j][k] ]; 1683 1684 # Find a nonzero entry in $X_{j,F} \cdot D( g_i^{g_j} )$. 1685 image:= Xlist[j][k].perm[1]; 1686 value:= Xlist[j][k].diag[ image ]; 1687 for u in [ 1 .. lg-i+1 ] do 1688 for v in [ 1 .. cexp[u] ] do 1689 image:= D[u].perm[ image ]; 1690 value:= value + D[u].diag[ image ]; 1691 od; 1692 od; 1693 1694 # Subtract the corresponding value in $C(g_i) \cdot X_{j,F}$. 1695 C:= nextnonlin2[ pos ]; 1696 Assert( 2, image = Xlist[j][k].perm[ C[1].perm[1] ], 1697 "BaumClausenInfo: failed assertion on conj. matrices" ); 1698 value:= value - 1699 ( C[1].diag[ C[1].perm[1] ] + Xlist[j][k].diag[ image ] ); 1700 l:= ( value * p / e ) mod p; 1701 1702 for u in [ 0 .. p-1 ] do 1703 pinextnonlin2[j][ Dpos2[k] + u ]:= 1704 pos + ( ( l + u * cexp[1] ) mod p ); 1705 nextXlist2[j][ Dpos2[k] + u ]:= Xlist[j][k]; 1706 od; 1707 1708 Assert( 2, BaumClausenInfoDebug.checkconj( pcgs, i, lg, j, 1709 nextnonlin2[ Dpos2[k] ], 1710 nextnonlin2[ pinextnonlin2[j][ Dpos2[k] ] ], 1711 Xlist[j][k], e ), 1712 Concatenation( "BaumClausenInfo: failed assertion on ", 1713 "conjugating matrices for nonlinear repres. ", 1714 "(i = ", String( i ), ")\n" ) ); 1715 1716 elif not IsBound( pinextnonlin2[j][ Dpos2[k] ] ) then 1717 1718 # $F$ fuses with its conjugates under $g_i$, yielding $D$. 1719 1720 dim:= Length( nonlin[k][1].diag ); 1721 1722 # Let $C$ be the stored representation $\tau_j D$ 1723 # equivalent to $D^{g_j}$. 1724 # Compute the position of $C$ in `pinextnonlin2'. 1725 pinextnonlin2[j][ Dpos2[k] ]:= Dpos2[ pinonlin[j][k] ]; 1726 1727 C:= nextnonlin2[ pinextnonlin2[j][ Dpos2[k] ] ]; 1728 D:= nextnonlin2[ Dpos2[k] ]; 1729 1730 # Compute the positions of the constituents; 1731 # `orb[k]' is the position of $\Phi_{k-1}$ in `nonlin'. 1732 pos:= pinonlin[j][k]; 1733 orb:= [ pos ]; 1734 min:= 1; 1735 minval:= pos; 1736 for u in [ 2 .. p ] do 1737 pos:= pinonlin[i][ pos ]; 1738 orb[u]:= pos; 1739 if pos < minval then 1740 minval:= pos; 1741 min:= u; 1742 fi; 1743 od; 1744 if 1 < min then 1745 orb:= Concatenation( orb{ [ min .. p ] }, 1746 orb{ [ 1 .. min-1 ] } ); 1747 fi; 1748 1749 # `sigma' is the bijection of constituents in the restrictions 1750 # of $D$ and $\tau_j D$ to $G_{i-1}$. 1751 # More precisely, $\pi_j(\pi_i^{u-1} F) = \Phi_{\sigma(u-1)}$. 1752 sigma:= []; 1753 pos:= k; 1754 for u in [ 1 .. p ] do 1755 sigma[u]:= Position( orb, pinonlin[j][ pos ] ); 1756 pos:= pinonlin[i][ pos ]; 1757 od; 1758 1759 # Compute $\pi = \sigma^{-1} (1,2,\ldots,p) \sigma$. 1760 pi:= []; 1761 pi[ sigma[p] ]:= sigma[1]; 1762 for u in [ 1 .. p-1 ] do 1763 pi[ sigma[u] ]:= sigma[ u+1 ]; 1764 od; 1765 1766 # Compute the positions of the constituents 1767 # $F_0, F_{\pi(0)}, \ldots, F_{\pi^{p-1}(0)}$. 1768 Forb:= [ k ]; 1769 pos:= k; 1770 for u in [ 2 .. p ] do 1771 pos:= pinonlin[i][ pos ]; 1772 Forb[u]:= pos; 1773 od; 1774 1775 # Compute the values $c_{\pi^u(0)}$, for $0 \leq u \leq p-1$. 1776 # Note that $c_0 = 1$. 1777 # (Here we encode of course the exponents.) 1778 constants:= [ 0 ]; 1779 l:= 1; 1780 1781 for u in [ 1 .. p-1 ] do 1782 1783 # Compute $c_{\pi^u(0)}$. 1784 # (We have $`l' = 1 + \pi^{u-1}(0)$.) 1785 # Note that $B_u = X_{j,\pi_j^u \Phi_0}$ for $0\leq u\leq p-2$, 1786 # and $B_{p-1} = 1787 # \Phi_0(g_i^p) \cdot ( X_{j,\Phi_0}^{(p-1)} )^{-1}$ 1788 1789 # First we get the image and diagonal value of 1790 # the first standard basis vector under $X_{j,\pi^u(0)}$. 1791 image:= Xlist[j][ Forb[ pi[l] ] ].perm[1]; 1792 value:= Xlist[j][ Forb[ pi[l] ] ].diag[ image ]; 1793 1794 # Next we compute the image under $A_{\pi^{u-1}(0)}$; 1795 # this matrix is in the $(\pi^{u-1}(0)+1)$-th column block 1796 # and in the $(\pi^u(0)+1)$-th row block of $D^{g_j}$. 1797 # Since we do not have this matrix explicitly, 1798 # we use the conjugate representation and the action 1799 # encoded by `cexp'. 1800 # Note the necessary initial shift because we use the 1801 # whole representation $D$ and not a single constituent; 1802 # so we shift by `dim' times $\pi^u(0)+1$. 1803 image:= dim * ( pi[l] - 1 ) + image; 1804 for v in [ 1 .. lg-i+1 ] do 1805 for w in [ 1 .. cexp[v] ] do 1806 image:= D[v].perm[ image ]; 1807 value:= value + D[v].diag[ image ]; 1808 od; 1809 od; 1810 1811 # Next we divide by the corresponding value in 1812 # the image of the first standard basis vector under 1813 # $B_{\sigma\pi^{u-1}(0)} X_{j,\pi^{u-1}(0)}$. 1814 # Note that $B_v$ is in the $(v+2)$-th row block for 1815 # $0 \leq v \leq p-2$, in the first row block for $v = p-1$, 1816 # and in the $(v+1)$-th column block of $C$. 1817 v:= sigma[l]; 1818 if v = p then 1819 image:= C[1].perm[1]; 1820 else 1821 image:= C[1].perm[ v*dim + 1 ]; 1822 fi; 1823 value:= value - C[1].diag[ image ]; 1824 image:= Xlist[j][ Forb[l] ].perm[ image - ( v - 1 ) * dim ]; 1825 value:= value - Xlist[j][ Forb[l] ].diag[ image ]; 1826 constants[ pi[l] ]:= ( constants[l] - value ) mod e; 1827 l:= pi[l]; 1828 1829 od; 1830 1831 # Put the conjugating matrix together. 1832 X:= rec( perm:= [], 1833 diag:= [] ); 1834 pos:= k; 1835 for u in [ 1 .. p ] do 1836 Append( X.diag, List( Xlist[j][ pos ].diag, 1837 x -> ( x + constants[u] ) mod e ) ); 1838 X.perm{ [ ( sigma[u] - 1 )*dim+1 .. sigma[u]*dim ] }:= 1839 Xlist[j][ pos ].perm + (u-1) * dim; 1840 pos:= pinonlin[i][ pos ]; 1841 od; 1842 1843 Assert( 2, BaumClausenInfoDebug.checkconj( pcgs, i, lg, j, 1844 nextnonlin2[ Dpos2[k] ], 1845 nextnonlin2[ pinextnonlin2[j][ Dpos2[k] ] ], 1846 X, e ), 1847 Concatenation( "BaumClausenInfo: failed assertion on ", 1848 "conjugating matrices for nonlinear repres. ", 1849 "(i = ", String( i ), ")\n" ) ); 1850 nextXlist2[j][ Dpos2[k] ]:= X; 1851 1852 fi; 1853 1854 od; 1855 1856 od; 1857 1858 # Finish the update for the next index. 1859 linear := nextlinear; 1860 pilinear := pinextlinear; 1861 1862 nonlin := Concatenation( nextnonlin1, nextnonlin2 ); 1863 pinonlin := List( [ 1 .. i-1 ], 1864 j -> Concatenation( pinextnonlin1[j], 1865 pinextnonlin2[j] + Length( pinextnonlin1[j] ) ) ); 1866 Xlist := List( [ 1 .. i-1 ], 1867 j -> Concatenation( nextXlist1[j], nextXlist2[j] ) ); 1868 1869 od; 1870 1871 1872 # Step 6: If necessary transfer the representations back to the 1873 # original group. 1874 1875 if IsBound( hom ) 1876 and not IsTrivial( KernelOfMultiplicativeGeneralMapping( hom ) ) then 1877 Info( InfoGroup, 2, 1878 "BaumClausenInfo: taking preimages in the original group" ); 1879 1880 kernel:= KernelOfMultiplicativeGeneralMapping( hom ); 1881 k:= Pcgs( kernel ); 1882 pcgs:= PcgsByPcSequence( ElementsFamily( FamilyObj( kernel ) ), 1883 Concatenation( List( pcgs, 1884 x -> PreImagesRepresentative( hom, x ) ), 1885 k ) ); 1886 k:= ListWithIdenticalEntries( Length( k ), 0 ); 1887 1888 linear:= List( linear, rep -> Concatenation( rep, k ) ); 1889 1890 for rep in nonlin do 1891 dim:= Length( rep[1].perm ); 1892 M:= rec( perm:= [ 1 .. dim ], 1893 diag:= [ 1 .. dim ] * 0 ); 1894 for i in k do 1895 Add( rep, M ); 1896 od; 1897 od; 1898 1899 else 1900 kernel:= TrivialSubgroup( G ); 1901 fi; 1902 1903 # Return the result (for nonabelian groups). 1904 return Immutable( rec( pcgs := pcgs, 1905 kernel := kernel, 1906 exponent := e, 1907 nonlin := nonlin, 1908 lin := linear 1909 ) ); 1910 end ); 1911 1912 1913############################################################################# 1914## 1915#F IrreducibleRepresentationsByBaumClausen( <G> ) . for a supersolv. group 1916## 1917BindGlobal( "IrreducibleRepresentationsByBaumClausen", function( G ) 1918 local mrep, # list of images lists for the result 1919 info, # result of `BaumClausenInfo' 1920 lg, # composition length of `G' 1921 rep, # loop over the representations 1922 gcd, # g.c.d. of the exponents in `rep' 1923 Ee, # complex root of unity needed for `rep' 1924 images, # one list of images 1925 dim, # current dimension 1926 i, k, # loop variabes 1927 mat; # one representing matrix 1928 1929 mrep:= []; 1930 info:= BaumClausenInfo( G ); 1931 lg:= Length( info.pcgs ); 1932 1933 if info.lin=[[]] then # trivial group 1934 return [GroupHomomorphismByImagesNC(G,Group([[1]]),[],[])]; 1935 fi; 1936 1937 # Compute the images of linear representations on the pcgs. 1938 for rep in info.lin do 1939 gcd := Gcd( rep ); 1940 if gcd = 0 then 1941 Add( mrep, List( rep, x -> [ [ 1 ] ] ) ); 1942 else 1943 gcd:= GcdInt( gcd, info.exponent ); 1944 Ee:= E( info.exponent / gcd ); 1945 Add( mrep, List( rep / gcd, x -> [ [ Ee^x ] ] ) ); 1946 fi; 1947 od; 1948 1949 # Compute the images of nonlinear representations on the pcgs. 1950 for rep in info.nonlin do 1951 images:= []; 1952 dim:= Length( rep[1].perm ); 1953 gcd:= GcdInt( Gcd( List( rep, x -> Gcd( x.diag ) ) ), info.exponent ); 1954 Ee:= E( info.exponent / gcd ); 1955 for i in [ 1 .. lg ] do 1956 mat:= NullMat( dim, dim, Rationals ); 1957 for k in [ 1 .. dim ] do 1958 mat[k][ rep[i].perm[k] ]:= 1959 Ee^( rep[i].diag[ rep[i].perm[k] ] / gcd ); 1960 od; 1961 images[i]:= mat; 1962 od; 1963 Add( mrep, images ); 1964 od; 1965 1966 return List( mrep, images -> GroupHomomorphismByImagesNC( G, 1967 GroupByGenerators( images ), info.pcgs, images ) ); 1968 end ); 1969 1970 1971############################################################################# 1972## 1973#M IrreducibleRepresentations( <G> ) . for an abelian by supersolvable group 1974## 1975InstallMethod( IrreducibleRepresentations, 1976 "(abelian by supersolvable) finite group", 1977 [ IsGroup and IsFinite ], 1, # higher than Dixon's method 1978 function( G ) 1979 if IsAbelian( SupersolvableResiduum( G ) ) then 1980 return IrreducibleRepresentationsByBaumClausen( G ); 1981 else 1982 TryNextMethod(); 1983 fi; 1984 end ); 1985 1986 1987############################################################################# 1988## 1989#M IrreducibleRepresentations( <G>, <F> ) . . for a group and `Cyclotomics' 1990## 1991InstallMethod( IrreducibleRepresentations, 1992 "finite group, Cyclotomics", 1993 [ IsGroup and IsFinite, IsCyclotomicCollection and IsField ], 1994 function( G, F ) 1995 if F <> Cyclotomics then 1996 TryNextMethod(); 1997 else 1998 return IrreducibleRepresentations( G ); 1999 fi; 2000 end ); 2001 2002 2003############################################################################# 2004## 2005#M IrreducibleRepresentations( <G>, <f> ) 2006## 2007InstallMethod( IrreducibleRepresentations, 2008 "for a finite group over a finite field", 2009 [ IsGroup and IsFinite, IsField and IsFinite ], 2010 function( G, f ) 2011 local md, hs, gens, M, mats, H, hom; 2012 2013 md := IrreducibleModules( G, f, 0 ); 2014 gens:=md[1]; 2015 md:=md[2]; 2016 hs := []; 2017 for M in md do 2018 mats := M.generators; 2019 H := Group( mats, IdentityMat( M.dimension, f ) ); 2020 hom := GroupHomomorphismByImagesNC( G, H, gens, mats ); 2021 Add( hs, hom ); 2022 od; 2023 return hs; 2024 end ); 2025 2026 2027############################################################################# 2028## 2029#M IrrBaumClausen( <G>) . . . . irred. characters of a supersolvable group 2030## 2031InstallMethod( IrrBaumClausen, 2032 "for a (solvable) group", 2033 [ IsGroup ], 2034 function( G ) 2035 local mulmoma, # local function to multiply monomial matrices 2036 ccl, # conjugacy classes of `G' 2037 tbl, # character table of `G' 2038 info, # result of `BaumClausenInfo' 2039 pcgs, # value of `info.pcgs' 2040 lg, # composition length 2041 evl, # list encoding exponents of class representatives 2042 i, j, k, # loop variables 2043 exps, # exponent vector of a group element 2044 t, # intermediate representation value 2045 irreducibles, # list of irreducible characters 2046 rep, # loop over the representations 2047 gcd, # g.c.d. of the exponents in `rep' 2048 q, # 2049 Ee, # complex root of unity needed for `rep' 2050 chi, # one character values list 2051 deg, # character degree 2052 idmat, # identity matrix 2053 trace; # trace of a matrix 2054 2055 mulmoma:= function( a, b ) 2056 local prod, i; 2057 prod:= rec( perm := b.perm{ a.perm }, 2058 diag := [] ); 2059 for i in [ 1 .. deg ] do 2060 prod.diag[ b.perm[i] ]:= b.diag[ b.perm[i] ] + a.diag[i]; 2061 od; 2062 return prod; 2063 end; 2064 2065 tbl:= CharacterTable( G ); 2066 ccl:= ConjugacyClasses( tbl ); 2067 SetExponent( G, Exponent( tbl ) ); 2068 info:= BaumClausenInfo( G ); 2069 2070 # The trivial group does not admit matrix arithmetic for evaluations. 2071 if IsTrivial( G ) then 2072 return [ Character( G, [ 1 ] ) ]; 2073 fi; 2074 2075 pcgs:= info.pcgs; 2076 lg:= Length( pcgs ); 2077 2078 exps:= List( ccl, 2079 c -> ExponentsOfPcElement( pcgs, Representative( c ) ) ); 2080 2081 # Compute the linear irreducibles. 2082 # Compute the roots of unity only once for all linear characters. 2083 # ($q$-th roots suffice, where $q$ divides the number of linear 2084 # characters and the known exponent; we do *not* compute the smallest 2085 # possible roots for each representation.) 2086 q:= Gcd( info.exponent, Length( info.lin ) ); 2087 gcd:= info.exponent / q; 2088 Ee:= E(q); 2089 Ee:= List( [ 0 .. q-1 ], i -> Ee^i ); 2090 irreducibles:= List( info.lin, rep -> 2091 Character( tbl, Ee{ ( ( exps * rep ) / gcd mod q ) + 1 } ) ); 2092 2093 # Compute the nonlinear irreducibles. 2094 if not IsEmpty( info.nonlin ) then 2095 evl:= []; 2096 for i in [ 2 .. Length( ccl ) ] do 2097 t:= []; 2098 for j in [ 1 .. lg ] do 2099 for k in [ 1 .. exps[i][j] ] do 2100 Add( t, j ); 2101 od; 2102 od; 2103 evl[ i-1 ]:= t; 2104 od; 2105 for rep in info.nonlin do 2106 gcd:= GcdInt( Gcd( List( rep, x -> Gcd( x.diag ) ) ), info.exponent ); 2107 Ee:= E( info.exponent / gcd ); 2108 deg:= Length( rep[1].perm ); 2109 chi:= [ deg ]; 2110 idmat:= rec( perm := [ 1 .. deg ], diag := [ 1 .. deg ] * 0 ); 2111 for j in evl do 2112 2113 # Compute the value of the representation at the representative. 2114 t:= idmat; 2115 for k in j do 2116 t:= mulmoma( t, rep[k] ); 2117 od; 2118 2119 # Compute the character value. 2120 trace:= 0; 2121 for k in [ 1 .. deg ] do 2122 if t.perm[k] = k then 2123 trace:= trace + Ee^( t.diag[k] / gcd ); 2124 fi; 2125 od; 2126 Add( chi, trace ); 2127 2128 od; 2129 Add( irreducibles, Character( tbl, chi ) ); 2130 od; 2131 fi; 2132 2133 # Return the result. 2134 return irreducibles; 2135 end ); 2136 2137 2138############################################################################# 2139## 2140#F InducedRepresentationImagesRepresentative( <rep>, <H>, <R>, <g> ) 2141## 2142## Let $<rep>_H$ denote the restriction of the group homomorphism <rep> to 2143## the group <H>, and $\phi$ the induced representation of $<rep>_H$ to $G$, 2144## where <R> is a transversal of <H> in $G$. 2145## `InducedRepresentationImagesRepresentative' returns the image of the 2146## element <g> of $G$ under $\phi$. 2147## 2148InstallGlobalFunction( InducedRepresentationImagesRepresentative, 2149 function( rep, H, R, g ) 2150 local len, blocks, i, k, kinv, j; 2151 2152 len:= Length( R ); 2153 blocks:= []; 2154 2155 for i in [ 1 .. len ] do 2156 k:= R[i] * g; 2157 kinv:= Inverse( k ); 2158 j:= PositionProperty( R, r -> r * kinv in H ); 2159 blocks[i]:= [ i, j, ImagesRepresentative( rep, k / R[j] ) ]; 2160 od; 2161 2162 return BlockMatrix( blocks, len, len ); 2163end ); 2164 2165 2166############################################################################# 2167## 2168#F InducedRepresentation( <rep>, <G> ) . . . . induced matrix representation 2169#F InducedRepresentation( <rep>, <G>, <R> ) 2170#F InducedRepresentation( <rep>, <G>, <R>, <H> ) 2171## 2172## Let <rep> be a matrix representation of the group $H$, which is a 2173## subgroup of the group <G>. 2174## `InducedRepresentation' returns the induced matrix representation of <G>. 2175## 2176## The optional third argument <R> is a right transversal of $H$ in <G>. 2177## If the fourth optional argument <H> is given then it must be a subgroup 2178## of the source of <rep>, and the induced representation of the restriction 2179## of <rep> to <H> is computed. 2180## 2181InstallGlobalFunction( InducedRepresentation, function( arg ) 2182 local rep, G, H, R, gens, images, map; 2183 2184 # Get and check the arguments. 2185 if Length( arg ) = 2 and IsGroupHomomorphism( arg[1] ) 2186 and IsGroup( arg[2] ) then 2187 rep := arg[1]; 2188 G := arg[2]; 2189 H := Source( rep ); 2190 R := RightTransversal( G, H ); 2191 2192 elif Length( arg ) = 3 and IsGroupHomomorphism( arg[1] ) 2193 and IsGroup( arg[2] ) 2194 and IsHomogeneousList( arg[3] ) then 2195 rep := arg[1]; 2196 G := arg[2]; 2197 R := arg[3]; 2198 H := Source( rep ); 2199 2200 elif Length( arg ) = 4 and IsGroupHomomorphism( arg[1] ) 2201 and IsGroup( arg[2] ) 2202 and IsHomogeneousList( arg[3] ) 2203 and IsGroup( arg[4] ) then 2204 rep := arg[1]; 2205 G := arg[2]; 2206 R := arg[3]; 2207 H := arg[4]; 2208 2209 else 2210 Error( "usage: InducedRepresentation(<rep>,<G>[,<R>[,<H>]])" ); 2211 fi; 2212 2213 # Handle a trivial case. 2214 if Length( R ) = 1 then 2215 return rep; 2216 fi; 2217 2218 # Construct the images of the generators of <G>. 2219 gens:= GeneratorsOfGroup( G ); 2220 images:= List( gens, 2221 g -> InducedRepresentationImagesRepresentative( rep, H, R, g ) ); 2222 2223 # Construct and return the homomorphism. 2224 map:= GroupHomomorphismByImagesNC( G, GroupByGenerators( images ), 2225 gens, images ); 2226 SetIsSurjective( map, true ); 2227 return map; 2228end ); 2229 2230 2231############################################################################# 2232## 2233#M <rep> ^ <G> 2234## 2235InstallOtherMethod( \^, 2236 "for group homomorphism and group (induction)", 2237 [ IsGroupHomomorphism, IsGroup ], 2238 function( rep, G ) 2239 if IsMatrixGroup( Range( rep ) ) and IsSubset( Source( rep ), G ) then 2240 return InducedRepresentation( rep, G ); 2241 else 2242 TryNextMethod(); 2243 fi; 2244 end ); 2245