Bilddatei

products/Sources/formale Sprachen/GAP/pkg/ctbllib/tst/multfree.g

, , , #F , ) ## ## Let be a character table, be a list of characters of , ## a character of , a matrix, the $i$-th entry being the ## coefficients of the decomposition of the induced character of $[i]$ ## to a supergroup $G$, say, of , the decomposition of ## induced to $G$, and a positive integer. ## ## `CharactersInducingWithBoundedMultiplicity' returns the list ## $C( , , )$; ## this is the list of all those characters $ + \vartheta$ of ## multiplicity at most such that all constituents of $\vartheta$ are ## contained in the list . ## ## Let $G$ be a group and $H$ a subgroup of $G$. For a set $S$ of ## characters of $H$ and a character $\chi$ of $H$, define $C( S, \chi, k )$ ## to be the set of all those possible permutation characters $\pi$ of $H$ ## of the form $\pi = \chi + \sum_{\varphi \in S^{\prime}} \varphi$, ## for a subset $S^{\prime}$ of $S$, with the property that $\pi^G$ has ## multiplicity at most $k$. ## ## Then the following holds. ## \begin{items} ## \item ## We need to consider only elements in the set $Rat(H)$ of rational ## irreducible characters of $H$ as constituents of $\pi$ since Galois ## conjugate constituents in a permutation character have the same ## multiplicity. ## ## \item ## If $\pi$ is a possible permutation character of $H$ such that $\pi^G$ ## has multiplicity at most $k$ then ## $C( \emptyset, \pi, k ) = \{ \pi \}$, ## otherwise $C( \emptyset, \pi, k ) = \emptyset$. ## ## \item ## Given a character $\psi$ of $H$ and $S \not= \emptyset$, ## fix $\chi \in S$ and set ## \[ ## S^{\prime}_i = ## \{ \varphi \in S | ## (\varphi^G + i \cdot \chi^G, \vartheta) \leq k ## \forall \vartheta \in Irr(H) \} . ## \] ## Then $C( S, \psi, k ) = C( S \setminus \{ \chi \}, \psi, k ) ## \cup \bigcup_{i=1}^k C( S^{\prime}, \psi + i \cdot \chi, k )$. ## ## \item ## $C( Rat(H), 1_H, k )$ is the set of all possible permutation ## characters $\pi$ of $H$ ## such that $\pi^G$ has multiplicity at most $k$. ## ## \item ## Each nontrivial irreducible constituent of each character in ## $C( Rat(H), 1_H, k )$ is contained in the set ## \[ ## S_0 = \{ \chi \in Rat(H) | \chi \not= 1_H, ## \chi^G + 1_H^G \mbox{\ has multiplicity at most $k$\ } \} , ## \] ## so $C( Rat(H), 1_H, k ) = C( S_0, 1_H, k )$. ## \end{items} ## ## (For the case $k = 1$, complex irreducible characters whose second ## Frobenius-Schur indicator is $-1$ could be excluded from the list of ## possible constituents.) ## DeclareGlobalFunction( "CharactersInducingWithBoundedMultiplicity" ); InstallGlobalFunction( CharactersInducingWithBoundedMultiplicity, function( H, S, psi, scprS, scprpsi, k ) local result, # the list $S( .. )$ chi, # $\chi$ scprchi, # decomposition of $\chi^G$ i, # loop from `1' to `k' allowed, # indices of possible constituents Sprime, # $S^{\prime}_i$ scprSprime; # decomposition of characters in $S^{\prime}_i$, # induced to $G$ if IsEmpty( S ) then # Test whether `psi' is a possible permutation character. if TestPerm( H, psi ) then result:= [ psi ]; else result:= []; fi; else # Fix a character $\chi$. chi := S[1]; scprchi := scprS[1]; # Form the union. result:= CharactersInducingWithBoundedMultiplicity( H, S{ [ 2 .. Length( S ) ] }, psi, scprS{ [ 2 .. Length( S ) ] }, scprpsi, k ); for i in [ 1 .. k ] do allowed := Filtered( [ 2 .. Length( S ) ], j -> Maximum( i * scprchi + scprS[j] ) <= k ); Sprime := S{ allowed }; scprSprime := scprS{ allowed }; Append( result, CharactersInducingWithBoundedMultiplicity( H, Sprime, psi + i * chi, scprSprime, scprpsi + i * scprchi, k ) ); od; fi; return result; end ); ############################################################################# ## #F MultAtMost( , , ) ## ## Let and be character tables of groups $G$ and $H$, respectively, ## such that $H$ is a subgroup of $G$ and the class fusion from to ## is stored on . ## `MultAtMost' returns the list of all characters $\varphi^G$ of $G$ ## of multiplicity at most such that $\varphi$ is a possible permutation ## character of $H$. ## BindGlobal( "MultAtMost", function( G, H, k ) local triv, # $1_H$ permch, # $(1_H)^G$ scpr1H, # decomposition of $(1_H)^G$ rat, # rational irreducible characters of $H$ ind, # induced rational irreducible characters mat, # decomposition of `ind' allowed, # indices of possible constituents S0, # $S_0$ scprS0, # decomposition of characters in $S_0$, # induced to $G$, with $Irr(G)$ cand; # list of multiplicity-free candidates, result # Compute $(1_H)^G$ and its decomposition into irreducibles of $G$. triv := TrivialCharacter( H ); permch := Induced( H, G, [ triv ] ); scpr1H := MatScalarProducts( G, Irr( G ), permch )[1]; # If $(1_H)^G$ has multiplicity larger than `k' then we are done. if Maximum( scpr1H ) > k then return []; fi; # Compute the set $S_0$ of all possible nontrivial # rational constituents of a candidate of multiplicity at most `k', # that is, all those rational irreducible characters of # $H$ that induce to $G$ with multiplicity at most `k'. rat:= RationalizedMat( Irr( H ) ); ind:= Induced( H, G, rat ); mat:= MatScalarProducts( G, Irr( G ), ind ); allowed:= Filtered( [ 1.. Length( mat ) ], x -> Maximum( mat[x] + scpr1H ) <= k ); S0 := rat{ allowed }; scprS0 := mat{ allowed }; # Compute $C( S_0, 1_H, k )$. cand:= CharactersInducingWithBoundedMultiplicity( H, S0, triv, scprS0, scpr1H, k ); # Induce the candidates to $G$, and return the sorted list. cand:= Induced( H, G, cand ); Sort( cand ); return cand; end ); ############################################################################ ## #F MultFree( , ) ## ## `MultFree' returns `MultAtMost( , , 1 )'. ## BindGlobal( "MultFree", function( G, H ) return MultAtMost( G, H, 1 ); end ); ############################################################################ ## #F PossiblePermutationCharactersWithBoundedMultiplicity( , ) ## ## Let be a character table with known `Maxes' value, ## and be a positive integer. ## The function `PossiblePermutationCharactersWithBoundedMultiplicity' ## returns a record with the following components. ## \beginitems ## `identifier' & ## the `Identifier' value of , ## ## `maxnames' & ## the list of names of the maximal subgroups of , ## ## `permcand' & ## at the $i$-th position the list of those possible permutation ## characters of whose multiplicity is at most ## and which are induced from the $i$-th maximal subgroup of , ## and ## ## `k' & ## the given bound for the multiplicity. ## \enditems ## BindGlobal( "PossiblePermutationCharactersWithBoundedMultiplicity", function( tbl, k ) local permcand, # list of all mult. free perm. character candidates maxname, # loop over tables of maximal subgroups max; # one table of a maximal subgroup if not HasMaxes( tbl ) then return fail; fi; permcand:= []; # Loop over the tables of maximal subgroups. for maxname in Maxes( tbl ) do max:= CharacterTable( maxname ); if max = fail or GetFusionMap( max, tbl ) = fail then Print( "#E no fusion `", maxname, "' -> `", Identifier( tbl ), "' stored\n" ); Add( permcand, Unknown() ); else # Compute the possible perm. characters inducing through `max'. Add( permcand, MultAtMost( tbl, max, k ) ); fi; od; # Return the result record. return rec( identifier := Identifier( tbl ), maxnames := Maxes( tbl ), permcand := permcand, k := k ); end ); ############################################################################# ## #E