1############################################################################# 2## 3## This file is part of GAP, a system for computational discrete algebra. 4## This file's authors include Thomas Breuer, Götz Pfeiffer. 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 declaration of those functions that are needed to 12## compute and test possible permutation characters. 13## 14#T TODO: 15#T - small improvement: 16#T if a prescribed value is equal to the degree then restrict the 17#T constituents to those having this class in the kernel 18#T - use roots in `PermCandidates' (cf. `PermCandidatesFaithful'), 19#T in order to guarantee property (d) already in the construction! 20#T - check and document `PermCandidatesFaithful' 21#T - `IsPermChar( <tbl>, <pc> )' 22#T (check whether <pc> can be a permutation character of <tbl>; 23#T use also the kernel of <pc>, i.e., check whether the kernel factor 24#T of <pc> can be a permutation character of the factor of <tbl> by the 25#T kernel; one example where this helps is the sum of characters of S3 26#T in O8+(2).3.2) 27#T - `Constituent' und `Maxdeg' - Optionen in `PermComb' 28 29 30############################################################################# 31## 32## <#GAPDoc Label="[1]{ctblpope}"> 33## <Index Subkey="permutation">characters</Index> 34## <Index Subkey="for permutation characters">candidates</Index> 35## <Index>possible permutation characters</Index> 36## <Index Subkey="possible">permutation characters</Index> 37## For groups <M>H</M> and <M>G</M> with <M>H \leq G</M>, 38## the induced character <M>(1_G)^H</M> is called the 39## <E>permutation character</E> of the operation of <M>G</M> 40## on the right cosets of <M>H</M>. 41## If only the character table of <M>G</M> is available and not the group 42## <M>G</M> itself, 43## one can try to get information about possible subgroups of <M>G</M> 44## by inspection of those <M>G</M>-class functions that might be 45## permutation characters, 46## using that such a class function <M>\pi</M> must have at least the 47## following properties. 48## (For details, see <Cite Key="Isa76" Where="Theorem 5.18."/>), 49## 50## <List> 51## <Mark>(a)</Mark> 52## <Item> 53## <M>\pi</M> is a character of <M>G</M>, 54## </Item> 55## <Mark>(b)</Mark> 56## <Item> 57## <M>\pi(g)</M> is a nonnegative integer for all <M>g \in G</M>, 58## </Item> 59## <Mark>(c)</Mark> 60## <Item> 61## <M>\pi(1)</M> divides <M>|G|</M>, 62## </Item> 63## <Mark>(d)</Mark> 64## <Item> 65## <M>\pi(g^n) \geq \pi(g)</M> for <M>g \in G</M> and integers <M>n</M>, 66## </Item> 67## <Mark>(e)</Mark> 68## <Item> 69## <M>[\pi, 1_G] = 1</M>, 70## </Item> 71## <Mark>(f)</Mark> 72## <Item> 73## the multiplicity of any rational irreducible <M>G</M>-character 74## <M>\psi</M> as a constituent of <M>\pi</M> is at most 75## <M>\psi(1)/[\psi, \psi]</M>, 76## </Item> 77## <Mark>(g)</Mark> 78## <Item> 79## <M>\pi(g) = 0</M> if the order of <M>g</M> does not divide 80## <M>|G|/\pi(1)</M>, 81## </Item> 82## <Mark>(h)</Mark> 83## <Item> 84## <M>\pi(1) |N_G(g)|</M> divides <M>\pi(g) |G|</M> 85## for all <M>g \in G</M>, 86## </Item> 87## <Mark>(i)</Mark> 88## <Item> 89## <M>\pi(g) \leq (|G| - \pi(1)) / (|g^G| |Gal_G(g)|)</M> 90## for all nonidentity <M>g \in G</M>, 91## where <M>|Gal_G(g)|</M> denotes the number of conjugacy classes 92## of <M>G</M> that contain generators of the group 93## <M>\langle g \rangle</M>, 94## </Item> 95## <Mark>(j)</Mark> 96## <Item> 97## if <M>p</M> is a prime that divides <M>|G|/\pi(1)</M> only once then 98## <M>s/(p-1)</M> divides <M>|G|/\pi(1)</M> and is congruent to <M>1</M> 99## modulo <M>p</M>, 100## where <M>s</M> is the number of elements of order <M>p</M> in the 101## (hypothetical) subgroup <M>H</M> for which <M>\pi = (1_H)^G</M> 102## holds. 103## (Note that <M>s/(p-1)</M> equals the number of Sylow <M>p</M> 104## subgroups in <M>H</M>.) 105## </Item> 106## </List> 107## 108## Any <M>G</M>-class function with these properties is called a 109## <E>possible permutation character</E> in &GAP;. 110## <P/> 111## (Condition (d) is checked only for those power maps that are stored in 112## the character table of <M>G</M>; 113## clearly (d) holds for all integers if it holds for all prime divisors of 114## the group order <M>|G|</M>.) 115## <P/> 116## &GAP; provides some algorithms to compute 117## possible permutation characters (see <Ref Func="PermChars"/>), 118## and also provides functions to check a few more criteria whether a 119## given character can be a transitive permutation character 120## (see <Ref Func="TestPerm1"/>). 121## <P/> 122## Some information about the subgroup <M>U</M> can be computed from the 123## permutation character <M>(1_U)^G</M> using <Ref Func="PermCharInfo"/>. 124## <#/GAPDoc> 125## 126 127 128############################################################################# 129## 130#F PermCharInfo( <tbl>, <permchars>[, <format> ] ) 131## 132## <#GAPDoc Label="PermCharInfo"> 133## <Index Subkey="for permutation characters">LaTeX</Index> 134## <ManSection> 135## <Func Name="PermCharInfo" Arg='tbl, permchars[, format ]'/> 136## 137## <Description> 138## Let <A>tbl</A> be the ordinary character table of the group <M>G</M>, 139## and <A>permchars</A> either the permutation character <M>(1_U)^G</M>, 140## for a subgroup <M>U</M> of <M>G</M>, or a list of such permutation 141## characters. 142## <Ref Func="PermCharInfo"/> returns a record with the following components. 143## <List> 144## <Mark><C>contained</C>:</Mark> 145## <Item> 146## a list containing, for each character <M>\psi = (1_U)^G</M> in 147## <A>permchars</A>, a list containing at position <M>i</M> the number 148## <M>\psi[i] |U| /</M> <C>SizesCentralizers( </C><A>tbl</A><C> )</C><M>[i]</M>, 149## which equals the number of those elements of <M>U</M> 150## that are contained in class <M>i</M> of <A>tbl</A>, 151## </Item> 152## <Mark><C>bound</C>:</Mark> 153## <Item> 154## a list containing, 155## for each character <M>\psi = (1_U)^G</M> in <A>permchars</A>, 156## a list containing at position <M>i</M> the number 157## <M>|U| / \gcd( |U|,</M> <C>SizesCentralizers( <A>tbl</A> )</C><M>[i] )</M>, 158## which divides the class length in <M>U</M> of an element in class <M>i</M> 159## of <A>tbl</A>, 160## </Item> 161## <Mark><C>display</C>:</Mark> 162## <Item> 163## a record that can be used as second argument of <Ref Oper="Display"/> 164## to display each permutation character in <A>permchars</A> and the 165## corresponding components <C>contained</C> and <C>bound</C>, 166## for those classes where at least one character of <A>permchars</A> is 167## nonzero, 168## </Item> 169## <Mark><C>ATLAS</C>:</Mark> 170## <Item> 171## a list of strings describing the decomposition of the permutation 172## characters in <A>permchars</A> into the irreducible characters of 173## <A>tbl</A>, given in an &ATLAS;-like notation. 174## This means that the irreducible constituents are indicated by their 175## degrees followed by lower case letters <C>a</C>, <C>b</C>, <C>c</C>, 176## <M>\ldots</M>, 177## which indicate the successive irreducible characters of <A>tbl</A> 178## of that degree, 179## in the order in which they appear in <C>Irr( </C><A>tbl</A><C> )</C>. 180## A sequence of small letters (not necessarily distinct) after a single 181## number indicates a sum of irreducible constituents all of the same 182## degree, an exponent <A>n</A> for the letter <A>lett</A> means that 183## <A>lett</A> is repeated <A>n</A> times. 184## The default notation for exponentiation is 185## <C><A>lett</A>^{<A>n</A>}</C>, 186## this is also chosen if the optional third argument <A>format</A> is 187## the string <C>"LaTeX"</C>; 188## if the third argument is the string <C>"HTML"</C> then exponentiation 189## is denoted by <C><A>lett</A><sup><A>n</A></sup></C>. 190## </Item> 191## </List> 192## <P/> 193## <Example><![CDATA[ 194## gap> t:= CharacterTable( "A6" );; 195## gap> psi:= Sum( Irr( t ){ [ 1, 3, 6 ] } ); 196## Character( CharacterTable( "A6" ), [ 15, 3, 0, 3, 1, 0, 0 ] ) 197## gap> info:= PermCharInfo( t, psi ); 198## rec( ATLAS := [ "1a+5b+9a" ], bound := [ [ 1, 3, 8, 8, 6, 24, 24 ] ], 199## contained := [ [ 1, 9, 0, 8, 6, 0, 0 ] ], 200## display := 201## rec( 202## chars := [ [ 15, 3, 0, 3, 1, 0, 0 ], [ 1, 9, 0, 8, 6, 0, 0 ], 203## [ 1, 3, 8, 8, 6, 24, 24 ] ], classes := [ 1, 2, 4, 5 ], 204## letter := "I" ) ) 205## gap> Display( t, info.display ); 206## A6 207## 208## 2 3 3 . 2 209## 3 2 . 2 . 210## 5 1 . . . 211## 212## 1a 2a 3b 4a 213## 2P 1a 1a 3b 2a 214## 3P 1a 2a 1a 4a 215## 5P 1a 2a 3b 4a 216## 217## I.1 15 3 3 1 218## I.2 1 9 8 6 219## I.3 1 3 8 6 220## gap> j1:= CharacterTable( "J1" );; 221## gap> psi:= TrivialCharacter( CharacterTable( "7:6" ) )^j1; 222## Character( CharacterTable( "J1" ), [ 4180, 20, 10, 0, 0, 2, 1, 0, 0, 223## 0, 0, 0, 0, 0, 0 ] ) 224## gap> PermCharInfo( j1, psi ).ATLAS; 225## [ "1a+56aabb+76aaab+77aabbcc+120aaabbbccc+133a^{4}bbcc+209a^{5}" ] 226## ]]></Example> 227## </Description> 228## </ManSection> 229## <#/GAPDoc> 230## 231DeclareGlobalFunction( "PermCharInfo" ); 232 233 234############################################################################# 235## 236#F PermCharInfoRelative( <tbl>, <tbl2>, <permchars> ) 237## 238## <#GAPDoc Label="PermCharInfoRelative"> 239## <ManSection> 240## <Func Name="PermCharInfoRelative" Arg='tbl, tbl2, permchars'/> 241## 242## <Description> 243## Let <A>tbl</A> and <A>tbl2</A> be the ordinary character tables of two 244## groups <M>H</M> and <M>G</M>, respectively, 245## where <M>H</M> is of index two in <M>G</M>, 246## and <A>permchars</A> either the permutation character <M>(1_U)^G</M>, 247## for a subgroup <M>U</M> of <M>G</M>, 248## or a list of such permutation characters. 249## <Ref Func="PermCharInfoRelative"/> returns a record with the same 250## components as <Ref Func="PermCharInfo"/>, the only exception is that the 251## entries of the <C>ATLAS</C> component are names relative to <A>tbl</A>. 252## <P/> 253## More precisely, the <M>i</M>-th entry of the <C>ATLAS</C> component is a 254## string describing the decomposition of the <M>i</M>-th entry in 255## <A>permchars</A>. 256## The degrees and distinguishing letters of the constituents refer to 257## the irreducibles of <A>tbl</A>, as follows. 258## The two irreducible characters of <A>tbl2</A> of degree <M>N</M>, say, 259## that extend the irreducible character <M>N</M> <C>a</C> of <A>tbl</A> 260## are denoted by <M>N</M> <C>a</C><M>^+</M> and <M>N </M><C>a</C><M>^-</M>. 261## The irreducible character of <A>tbl2</A> of degree <M>2N</M>, say, whose 262## restriction to <A>tbl</A> is the sum of the irreducible characters 263## <M>N</M> <C>a</C> and <M>N</M> <C>b</C> is denoted as <M>N</M> <C>ab</C>. 264## Multiplicities larger than <M>1</M> of constituents are denoted by 265## exponents. 266## <P/> 267## (This format is useful mainly for multiplicity free permutation 268## characters.) 269## <P/> 270## <Example><![CDATA[ 271## gap> t:= CharacterTable( "A5" );; 272## gap> t2:= CharacterTable( "A5.2" );; 273## gap> List( Irr( t2 ), x -> x[1] ); 274## [ 1, 1, 6, 4, 4, 5, 5 ] 275## gap> List( Irr( t ), x -> x[1] ); 276## [ 1, 3, 3, 4, 5 ] 277## gap> permchars:= List( [ [1], [1,2], [1,7], [1,3,4,4,6,6,7] ], 278## > l -> Sum( Irr( t2 ){ l } ) ); 279## [ Character( CharacterTable( "A5.2" ), [ 1, 1, 1, 1, 1, 1, 1 ] ), 280## Character( CharacterTable( "A5.2" ), [ 2, 2, 2, 2, 0, 0, 0 ] ), 281## Character( CharacterTable( "A5.2" ), [ 6, 2, 0, 1, 0, 2, 0 ] ), 282## Character( CharacterTable( "A5.2" ), [ 30, 2, 0, 0, 6, 0, 0 ] ) ] 283## gap> info:= PermCharInfoRelative( t, t2, permchars );; 284## gap> info.ATLAS; 285## [ "1a^+", "1a^{\\pm}", "1a^++5a^-", 286## "1a^++3ab+4(a^+)^{2}+5a^+a^{\\pm}" ] 287## ]]></Example> 288## </Description> 289## </ManSection> 290## <#/GAPDoc> 291## 292DeclareGlobalFunction( "PermCharInfoRelative" ); 293 294 295############################################################################# 296## 297#F TestPerm1( <tbl>, <char> ) . . . . . . . . . . . . . . . . test permchar 298#F TestPerm2( <tbl>, <char> ) . . . . . . . . . . . . . . . . test permchar 299#F TestPerm3( <tbl>, <chars> ) . . . . . . . . . . . . . . . test permchars 300#F TestPerm4( <tbl>, <chars> ) . . . . . . . . . . . . . . . test permchars 301#F TestPerm5( <tbl>, <chars>, <modtbl> ) . . . . . . . . . . test permchars 302## 303## <#GAPDoc Label="TestPerm1"> 304## <ManSection> 305## <Heading>TestPerm1, ..., TestPerm5</Heading> 306## <Func Name="TestPerm1" Arg='tbl, char'/> 307## <Func Name="TestPerm2" Arg='tbl, char'/> 308## <Func Name="TestPerm3" Arg='tbl, chars'/> 309## <Func Name="TestPerm4" Arg='tbl, chars'/> 310## <Func Name="TestPerm5" Arg='tbl, chars, modtbl'/> 311## 312## <Description> 313## The first three of these functions implement tests of the properties of 314## possible permutation characters listed in 315## Section <Ref Sect="Possible Permutation Characters"/>, 316## The other two implement test of additional properties. 317## Let <A>tbl</A> be the ordinary character table of a group <M>G</M>, say, 318## <A>char</A> a rational character of <A>tbl</A>, 319## and <A>chars</A> a list of rational characters of <A>tbl</A>. 320## For applying <Ref Func="TestPerm5"/>, the knowledge of a <M>p</M>-modular 321## Brauer table <A>modtbl</A> of <M>G</M> is required. 322## <Ref Func="TestPerm4"/> and <Ref Func="TestPerm5"/> expect the characters 323## in <A>chars</A> to satisfy the conditions checked by 324## <Ref Func="TestPerm1"/> and <Ref Func="TestPerm2"/> (see below). 325## <P/> 326## The return values of the functions were chosen parallel to the tests 327## listed in <Cite Key="NPP84"/>. 328## <P/> 329## <Ref Func="TestPerm1"/> return <C>1</C> or <C>2</C> if <A>char</A> fails 330## because of (T1) or (T2), respectively; 331## this corresponds to the criteria (b) and (d). 332## Note that only those power maps are considered that are stored on 333## <A>tbl</A>. 334## If <A>char</A> satisfies the conditions, <C>0</C> is returned. 335## <P/> 336## <Ref Func="TestPerm2"/> returns <C>1</C> if <A>char</A> fails because of 337## the criterion (c), 338## it returns <C>3</C>, <C>4</C>, or <C>5</C> if <A>char</A> fails because 339## of (T3), (T4), or (T5), respectively; 340## these tests correspond to (g), a weaker form of (h), and (j). 341## If <A>char</A> satisfies the conditions, <C>0</C> is returned. 342## <P/> 343## <Ref Func="TestPerm3"/> returns the list of all those class functions in 344## the list <A>chars</A> that satisfy criterion (h); 345## this is a stronger version of (T6). 346## <P/> 347## <Ref Func="TestPerm4"/> returns the list of all those class functions in 348## the list <A>chars</A> that satisfy (T8) and (T9) for each prime divisor 349## <M>p</M> of the order of <M>G</M>; 350## these tests use modular representation theory but do not require the 351## knowledge of decomposition matrices 352## (cf. <Ref Func="TestPerm5"/> below). 353## <P/> 354## (T8) implements the test of the fact that in the case that <M>p</M> 355## divides <M>|G|</M> and the degree of a transitive permutation character 356## <M>\pi</M> exactly once, 357## the projective cover of the trivial character is a summand of <M>\pi</M>. 358## (This test is omitted if the projective cover cannot be identified.) 359## <P/> 360## Given a permutation character <M>\pi</M> of a group <M>G</M> and a prime 361## integer <M>p</M>, 362## the restriction <M>\pi_B</M> to a <M>p</M>-block <M>B</M> of <M>G</M> has 363## the following property, which is checked by (T9). 364## For each <M>g \in G</M> such that <M>g^n</M> is a <M>p</M>-element of 365## <M>G</M>, <M>\pi_B(g^n)</M> is a nonnegative integer that satisfies 366## <M>|\pi_B(g)| \leq \pi_B(g^n) \leq \pi(g^n)</M>. 367## (This is <Cite Key="Sco73" Where="Corollary A on p. 113"/>.) 368## <P/> 369## <Ref Func="TestPerm5"/> requires the <M>p</M>-modular Brauer table 370## <A>modtbl</A> of <M>G</M>, for some prime <M>p</M> dividing the order of 371## <M>G</M>, 372## and checks whether those characters in the list <A>chars</A> whose degree 373## is divisible by the <M>p</M>-part of the order of <M>G</M> can be 374## decomposed into projective indecomposable characters; 375## <Ref Func="TestPerm5"/> returns the sublist of all those characters in 376## <A>chars</A> that either satisfy this condition or to which the test does 377## not apply. 378## <P/> 379## <!-- Say a word about (T7)?--> 380## <!-- This is the check whether the cycle structure of elements is well-defined;--> 381## <!-- the check is superfluous (at least) for elements of prime power order--> 382## <!-- or order equal to the product of two primes (see <Cite Key="NPP84"/>);--> 383## <!-- note that by construction, the numbers of <Q>cycles</Q> are always integral,--> 384## <!-- the only thing to test is whether they are nonnegative.--> 385## <Example><![CDATA[ 386## gap> tbl:= CharacterTable( "A5" );; 387## gap> rat:= RationalizedMat( Irr( tbl ) ); 388## [ Character( CharacterTable( "A5" ), [ 1, 1, 1, 1, 1 ] ), 389## Character( CharacterTable( "A5" ), [ 6, -2, 0, 1, 1 ] ), 390## Character( CharacterTable( "A5" ), [ 4, 0, 1, -1, -1 ] ), 391## Character( CharacterTable( "A5" ), [ 5, 1, -1, 0, 0 ] ) ] 392## gap> tup:= Filtered( Tuples( [ 0, 1 ], 4 ), x -> not IsZero( x ) ); 393## [ [ 0, 0, 0, 1 ], [ 0, 0, 1, 0 ], [ 0, 0, 1, 1 ], [ 0, 1, 0, 0 ], 394## [ 0, 1, 0, 1 ], [ 0, 1, 1, 0 ], [ 0, 1, 1, 1 ], [ 1, 0, 0, 0 ], 395## [ 1, 0, 0, 1 ], [ 1, 0, 1, 0 ], [ 1, 0, 1, 1 ], [ 1, 1, 0, 0 ], 396## [ 1, 1, 0, 1 ], [ 1, 1, 1, 0 ], [ 1, 1, 1, 1 ] ] 397## gap> lincomb:= List( tup, coeff -> coeff * rat );; 398## gap> List( lincomb, psi -> TestPerm1( tbl, psi ) ); 399## [ 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0 ] 400## gap> List( lincomb, psi -> TestPerm2( tbl, psi ) ); 401## [ 0, 5, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1 ] 402## gap> Set( List( TestPerm3(tbl, lincomb), x -> Position(lincomb, x) ) ); 403## [ 1, 4, 6, 7, 8, 9, 10, 11, 13 ] 404## gap> tbl:= CharacterTable( "A7" ); 405## CharacterTable( "A7" ) 406## gap> perms:= PermChars( tbl, rec( degree:= 315 ) ); 407## [ Character( CharacterTable( "A7" ), [ 315, 3, 0, 0, 3, 0, 0, 0, 0 ] ) 408## , Character( CharacterTable( "A7" ), 409## [ 315, 15, 0, 0, 1, 0, 0, 0, 0 ] ) ] 410## gap> TestPerm4( tbl, perms ); 411## [ Character( CharacterTable( "A7" ), [ 315, 15, 0, 0, 1, 0, 0, 0, 0 412## ] ) ] 413## gap> perms:= PermChars( tbl, rec( degree:= 15 ) ); 414## [ Character( CharacterTable( "A7" ), [ 15, 3, 0, 3, 1, 0, 0, 1, 1 ] ), 415## Character( CharacterTable( "A7" ), [ 15, 3, 3, 0, 1, 0, 3, 1, 1 ] ) 416## ] 417## gap> TestPerm5( tbl, perms, tbl mod 5 ); 418## [ Character( CharacterTable( "A7" ), [ 15, 3, 0, 3, 1, 0, 0, 1, 1 ] ) 419## ] 420## ]]></Example> 421## </Description> 422## </ManSection> 423## <#/GAPDoc> 424## 425DeclareGlobalFunction( "TestPerm1" ); 426DeclareGlobalFunction( "TestPerm2" ); 427DeclareGlobalFunction( "TestPerm3" ); 428DeclareGlobalFunction( "TestPerm4" ); 429DeclareGlobalFunction( "TestPerm5" ); 430 431 432############################################################################# 433## 434#F PermChars( <tbl> ) 435#F PermChars( <tbl>, <degree> ) 436#F PermChars( <tbl>, <arec> ) 437## 438## <#GAPDoc Label="PermChars"> 439## <ManSection> 440## <Func Name="PermChars" Arg='tbl[, cond]'/> 441## 442## <Description> 443## &GAP; provides several algorithms to determine 444## possible permutation characters from a given character table. 445## They are described in detail in <Cite Key="BP98"/>. 446## The algorithm is selected from the choice of the optional argument 447## <A>cond</A>. 448## The user is encouraged to try different approaches, 449## especially if one choice fails to come to an end. 450## <P/> 451## Regardless of the algorithm used in a specific case, 452## <Ref Func="PermChars"/> returns a list of <E>all</E> 453## possible permutation characters with the properties described by 454## <A>cond</A>. 455## There is no guarantee that a character of this list is in fact 456## a permutation character. 457## But an empty list always means there is no permutation character 458## with these properties (e.g., of a certain degree). 459## <P/> 460## Called with only one argument, a character table <A>tbl</A>, 461## <Ref Func="PermChars"/> returns the list of all possible permutation 462## characters of the group with this character table. 463## This list might be rather long for big groups, 464## and its computation might take much time. 465## The algorithm is described in <Cite Key="BP98" Where="Section 3.2"/>; 466## it depends on a preprocessing step, where the inequalities 467## arising from the condition <M>\pi(g) \geq 0</M> are transformed into 468## a system of inequalities that guides the search 469## (see <Ref Oper="Inequalities"/>). 470## So the following commands compute the list of 39 possible permutation 471## characters of the Mathieu group <M>M_{11}</M>. 472## <P/> 473## <Example><![CDATA[ 474## gap> m11:= CharacterTable( "M11" );; 475## gap> SetName( m11, "m11" ); 476## gap> perms:= PermChars( m11 );; 477## gap> Length( perms ); 478## 39 479## ]]></Example> 480## <P/> 481## There are two different search strategies for this algorithm. 482## The default strategy simply constructs all characters with nonnegative 483## values and then tests for each such character whether its degree 484## is a divisor of the order of the group. 485## The other strategy uses the inequalities to predict 486## whether a character of a certain degree can lie 487## in the currently searched part of the search tree. 488## To choose this strategy, enter a record as the second argument of 489## <Ref Func="PermChars"/>, 490## and set its component <C>degree</C> to the range of degrees 491## (which might also be a range containing all divisors of the group order) 492## you want to look for; 493## additionally, the record component <C>ineq</C> can take the inequalities 494## computed by <Ref Oper="Inequalities"/> if they are needed more than once. 495## <P/> 496## If a positive integer is given as the second argument <A>cond</A>, 497## <Ref Func="PermChars"/> returns the list of all 498## possible permutation characters of <A>tbl</A> that have degree 499## <A>cond</A>. 500## For that purpose, a preprocessing step is performed where 501## essentially the rational character table is inverted 502## in order to determine boundary points for the simplex 503## in which the possible permutation characters of the given degree 504## must lie (see <Ref Func="PermBounds"/>). 505## The algorithm is described at the end of 506## <Cite Key="BP98" Where="Section 3.2"/>. 507## Note that inverting big integer matrices needs a lot of time and space. 508## So this preprocessing is restricted to groups with less than 100 classes, 509## say. 510## <P/> 511## <Example><![CDATA[ 512## gap> deg220:= PermChars( m11, 220 ); 513## [ Character( m11, [ 220, 4, 4, 0, 0, 4, 0, 0, 0, 0 ] ), 514## Character( m11, [ 220, 12, 4, 4, 0, 0, 0, 0, 0, 0 ] ), 515## Character( m11, [ 220, 20, 4, 0, 0, 2, 0, 0, 0, 0 ] ) ] 516## ]]></Example> 517## <P/> 518## If a record is given as the second argument <A>cond</A>, 519## <Ref Func="PermChars"/> returns the list of all 520## possible permutation characters that have the properties described by 521## the components of this record. 522## One such situation has been mentioned above. 523## If <A>cond</A> contains a degree as value of the record component 524## <C>degree</C> 525## then <Ref Func="PermChars"/> will behave exactly as if this degree was 526## entered as <A>cond</A>. 527## <P/> 528## <Example><![CDATA[ 529## gap> deg220 = PermChars( m11, rec( degree:= 220 ) ); 530## true 531## ]]></Example> 532## <P/> 533## For the meaning of additional components of <A>cond</A> besides 534## <C>degree</C>, see <Ref Func="PermComb"/>. 535## <P/> 536## Instead of <C>degree</C>, <A>cond</A> may have the component <C>torso</C> 537## bound to a list that contains some known values of the required 538## characters at the right positions; 539## at least the degree <A>cond</A><C>.torso[1]</C> must be an integer. 540## In this case, the algorithm described in 541## <Cite Key="BP98" Where="Section 3.3"/> is chosen. 542## The component <C>chars</C>, if present, holds a list of all those 543## <E>rational</E> irreducible characters of <A>tbl</A> that might be 544## constituents of the required characters. 545## <P/> 546## (<E>Note</E>: If <A>cond</A><C>.chars</C> is bound and does not contain 547## <E>all</E> rational irreducible characters of <A>tbl</A>, 548## &GAP; checks whether the scalar products of all class functions in the 549## result list with the omitted rational irreducible characters of 550## <A>tbl</A> are nonnegative; 551## so there should be nontrivial reasons for excluding a character 552## that is known to be not a constituent of the desired possible permutation 553## characters.) 554## <P/> 555## <Example><![CDATA[ 556## gap> PermChars( m11, rec( torso:= [ 220 ] ) ); 557## [ Character( m11, [ 220, 4, 4, 0, 0, 4, 0, 0, 0, 0 ] ), 558## Character( m11, [ 220, 20, 4, 0, 0, 2, 0, 0, 0, 0 ] ), 559## Character( m11, [ 220, 12, 4, 4, 0, 0, 0, 0, 0, 0 ] ) ] 560## gap> PermChars( m11, rec( torso:= [ 220,,,,, 2 ] ) ); 561## [ Character( m11, [ 220, 20, 4, 0, 0, 2, 0, 0, 0, 0 ] ) ] 562## ]]></Example> 563## <P/> 564## An additional restriction on the possible permutation characters computed 565## can be forced if <A>con</A> contains, in addition to <C>torso</C>, 566## the components <C>normalsubgroup</C> and <C>nonfaithful</C>, 567## with values a list of class positions of a normal subgroup <M>N</M> of 568## the group <M>G</M> of <A>tbl</A> and a possible permutation character 569## <M>\pi</M> of <M>G</M>, respectively, such that <M>N</M> is contained in 570## the kernel of <M>\pi</M>. 571## In this case, <Ref Func="PermChars"/> returns the list of those possible 572## permutation characters <M>\psi</M> of <A>tbl</A> coinciding with 573## <C>torso</C> wherever its values are bound 574## and having the property that no irreducible constituent of 575## <M>\psi - \pi</M> has <M>N</M> in its kernel. 576## If the component <C>chars</C> is bound in <A>cond</A> then the above 577## statements apply. 578## An interpretation of the computed characters is the following. 579## Suppose there exists a subgroup <M>V</M> of <M>G</M> such that 580## <M>\pi = (1_V)^G</M>; 581## Then <M>N \leq V</M>, and if a computed character is of the form 582## <M>(1_U)^G</M>, for a subgroup <M>U</M> of <M>G</M>, then <M>V = UN</M>. 583## <P/> 584## <Example><![CDATA[ 585## gap> s4:= CharacterTable( "Symmetric", 4 );; 586## gap> nsg:= ClassPositionsOfDerivedSubgroup( s4 );; 587## gap> pi:= TrivialCharacter( s4 );; 588## gap> PermChars( s4, rec( torso:= [ 12 ], normalsubgroup:= nsg, 589## > nonfaithful:= pi ) ); 590## [ Character( CharacterTable( "Sym(4)" ), [ 12, 2, 0, 0, 0 ] ) ] 591## gap> pi:= Sum( Filtered( Irr( s4 ), 592## > chi -> IsSubset( ClassPositionsOfKernel( chi ), nsg ) ) ); 593## Character( CharacterTable( "Sym(4)" ), [ 2, 0, 2, 2, 0 ] ) 594## gap> PermChars( s4, rec( torso:= [ 12 ], normalsubgroup:= nsg, 595## > nonfaithful:= pi ) ); 596## [ Character( CharacterTable( "Sym(4)" ), [ 12, 0, 4, 0, 0 ] ) ] 597## ]]></Example> 598## <P/> 599## The class functions returned by <Ref Func="PermChars"/> have the 600## properties tested by <Ref Func="TestPerm1"/>, <Ref Func="TestPerm2"/>, 601## and <Ref Func="TestPerm3"/>. 602## So they are possible permutation characters. 603## See <Ref Func="TestPerm1"/> for criteria whether a 604## possible permutation character can in fact be a permutation character. 605## </Description> 606## </ManSection> 607## <#/GAPDoc> 608## 609DeclareGlobalFunction( "PermChars" ); 610 611 612############################################################################# 613## 614#O Inequalities( <tbl>, <chars>[, <option>] ) 615## 616## <#GAPDoc Label="Inequalities"> 617## <ManSection> 618## <Oper Name="Inequalities" Arg='tbl, chars[, option]'/> 619## 620## <Description> 621## Let <A>tbl</A> be the ordinary character table of a group <M>G</M>. 622## The condition <M>\pi(g) \geq 0</M> for every possible permutation 623## character <M>\pi</M> of <M>G</M> places restrictions on the 624## multiplicities <M>a_i</M> of the irreducible constituents <M>\chi_i</M> 625## of <M>\pi = \sum_{{i = 1}}^r a_i \chi_i</M>. 626## For every element <M>g \in G</M>, 627## we have <M>\sum_{{i = 1}}^r a_i \chi_i(g) \geq 0</M>. 628## The power maps provide even stronger conditions. 629## <P/> 630## This system of inequalities is kind of diagonalized, 631## resulting in a system of inequalities restricting <M>a_i</M> 632## in terms of <M>a_j</M>, <M>j < i</M>. 633## These inequalities are used to construct characters with nonnegative 634## values (see <Ref Func="PermChars"/>). 635## <Ref Func="PermChars"/> either calls <Ref Oper="Inequalities"/> or takes 636## this information from the <C>ineq</C> component of its argument record. 637## <P/> 638## The number of inequalities arising in the process of diagonalization may 639## grow very strongly. 640## <P/> 641## There are two ways to organize the projection. 642## The first, which is chosen if no <A>option</A> argument is present, 643## is the straight approach which takes the rational irreducible 644## characters in their original order and by this guarantees the character 645## with the smallest degree to be considered first. 646## The other way, which is chosen if the string <C>"small"</C> is entered as 647## third argument <A>option</A>, tries to keep the number of intermediate 648## inequalities small by eventually changing the order of characters. 649## <P/> 650## <Example><![CDATA[ 651## gap> tbl:= CharacterTable( "M11" );; 652## gap> PermComb( tbl, rec( degree:= 110 ) ); 653## [ Character( CharacterTable( "M11" ), 654## [ 110, 6, 2, 2, 0, 0, 2, 2, 0, 0 ] ), 655## Character( CharacterTable( "M11" ), 656## [ 110, 6, 2, 6, 0, 0, 0, 0, 0, 0 ] ), 657## Character( CharacterTable( "M11" ), [ 110, 14, 2, 2, 0, 2, 0, 0, 0, 658## 0 ] ) ] 659## gap> # Now compute only multiplicity free permutation characters. 660## gap> bounds:= List( RationalizedMat( Irr( tbl ) ), x -> 1 );; 661## gap> PermComb( tbl, rec( degree:= 110, maxmult:= bounds ) ); 662## [ Character( CharacterTable( "M11" ), 663## [ 110, 6, 2, 2, 0, 0, 2, 2, 0, 0 ] ) ] 664## ]]></Example> 665## </Description> 666## </ManSection> 667## <#/GAPDoc> 668## 669DeclareOperation( "Inequalities", [ IsOrdinaryTable, IsList ] ); 670DeclareOperation( "Inequalities", [ IsOrdinaryTable, IsList, IsObject ] ); 671 672 673############################################################################# 674## 675#F Permut( <tbl>, <arec> ) 676## 677## <ManSection> 678## <Func Name="Permut" Arg='tbl, arec'/> 679## 680## <Description> 681## <C>Permut</C> computes possible permutation characters of the character table 682## <A>tbl</A> by the algorithm that solves a system of inequalities. 683## This is described in <Cite Key="BP98" Where="Section 3.2"/>. 684## <P/> 685## <A>arec</A> must be a record. 686## Only the following components are used in the function. 687## <List> 688## <Mark><C>ineq</C> </Mark> 689## <Item> 690## the result of <Ref Func="Inequalities"/>, 691## will be computed if it is not present, 692## <C>degree</C> & 693## the list of degrees for which the possible permutation characters 694## shall be computed, 695## this will lead to a speedup only if the range of degrees is 696## restricted. 697## </Item> 698## </List> 699## </Description> 700## </ManSection> 701## 702DeclareGlobalFunction( "Permut" ); 703 704 705############################################################################# 706## 707#F PermBounds( <tbl>, <d> ) . . . . . . . . . . boundary points for simplex 708## 709## <#GAPDoc Label="PermBounds"> 710## <ManSection> 711## <Func Name="PermBounds" Arg='tbl, d'/> 712## 713## <Description> 714## Let <A>tbl</A> be the ordinary character table of the group <M>G</M>. 715## All <M>G</M>-characters <M>\pi</M> satisfying <M>\pi(g) > 0</M> and 716## <M>\pi(1) = <A>d</A></M>, 717## for a given degree <A>d</A>, lie in a simplex described by these 718## conditions. 719## <Ref Func="PermBounds"/> computes the boundary points of this simplex for 720## <M>d = 0</M>, 721## from which the boundary points for any other <A>d</A> are easily derived. 722## (Some conditions from the power maps of <A>tbl</A> are also involved.) 723## For this purpose, a matrix similar to the rational character table of 724## <M>G</M> has to be inverted. 725## These boundary points are used by <Ref Func="PermChars"/> 726## to construct all possible permutation characters 727## (see <Ref Sect="Possible Permutation Characters"/>) of a given 728## degree. 729## <Ref Func="PermChars"/> either calls <Ref Func="PermBounds"/> or takes 730## this information from the <C>bounds</C> component of its argument record. 731## </Description> 732## </ManSection> 733## <#/GAPDoc> 734## 735DeclareGlobalFunction( "PermBounds" ); 736 737 738############################################################################# 739## 740#F PermComb( <tbl>, <arec> ) . . . . . . . . . . . . permutation characters 741## 742## <#GAPDoc Label="PermComb"> 743## <ManSection> 744## <Func Name="PermComb" Arg='tbl, arec'/> 745## 746## <Description> 747## <Ref Func="PermComb"/> computes possible permutation characters of the 748## character table <A>tbl</A> by the improved combinatorial approach 749## described at the end of <Cite Key="BP98" Where="Section 3.2"/>. 750## <P/> 751## For computing the possible linear combinations <E>without</E> prescribing 752## better bounds (i.e., when the computation of bounds shall be suppressed), 753## enter 754## <P/> 755## <C><A>arec</A>:= rec( degree := <A>degree</A>, bounds := false )</C>, 756## <P/> 757## where <A>degree</A> is the character degree; 758## this is useful if the multiplicities are expected to be small, 759## and if this is forced by high irreducible degrees. 760## <P/> 761## A list of upper bounds on the multiplicities of the rational irreducibles 762## characters can be explicitly prescribed as a <C>maxmult</C> component in 763## <A>arec</A>. 764## </Description> 765## </ManSection> 766## <#/GAPDoc> 767## 768DeclareGlobalFunction( "PermComb" ); 769 770 771############################################################################# 772## 773#F PermCandidates( <tbl>, <characters>, <torso> ) 774## 775## <ManSection> 776## <Func Name="PermCandidates" Arg='tbl, characters, torso'/> 777## 778## <Description> 779## <C>PermCandidates</C> computes possible permutation characters of the 780## character table <A>tbl</A> with the strategy using Gaussian elimination, 781## which is described in <Cite Key="BP98" Where="Section 3.3"/>. 782## <P/> 783## The class functions in the result have the additional properties that 784## only the (necessarily rational) characters <A>characters</A> occur as 785## constituents, and that they are all completions of <A>torso</A>. 786## (Note that scalar products with rational irreducible characters of 787## <A>tbl</A> that are omitted in <A>characters</A> may be negative, 788## so not all class functions in the result list are necessarily characters 789## if <A>characters</A> does not contain all rational irreducible characters 790## of <A>tbl</A>.) 791## <P/> 792## Known values of the candidates must be nonnegative integers in 793## <A>torso</A>, the other positions of <A>torso</A> are unbound; 794## at least the degree <C><A>torso</A>[1]</C> must be an integer. 795## <!-- what about choice lists ??--> 796## </Description> 797## </ManSection> 798## 799DeclareGlobalFunction( "PermCandidates" ); 800 801 802############################################################################# 803## 804#F PermCandidatesFaithful( <tbl>, <chars>, <norm_subgrp>, <nonfaithful>, 805#F <lower>, <upper>, <torso> ) 806## 807## <ManSection> 808## <Func Name="PermCandidatesFaithful" 809## Arg='tbl, chars, norm_subgrp, nonfaithful, lower, upper, torso'/> 810## 811## <Description> 812## computes certain possible permutation characters of the character table 813## <A>tbl</A> with a generalization of the strategy 814## using Gaussian elimination (see <Ref Func="PermCandidates"/>). 815## These characters are all with the following properties. 816## <P/> 817## <Enum> 818## <Item> 819## Only the (necessarily rational) characters <A>chars</A> occur as 820## constituents, 821## </Item> 822## <Item> 823## they are completions of <A>torso</A>, and 824## </Item> 825## <Item> 826## have the character <A>nonfaithful</A> as maximal constituent with kernel 827## <A>norm_subgrp</A>. 828## </Item> 829## </Enum> 830## <P/> 831## Known values of the candidates must be nonnegative integers in 832## <A>torso</A>, the other positions of <A>torso</A> are unbound; 833## at least the degree <C><A>torso</A>[1]</C> must be an integer. 834## </Description> 835## </ManSection> 836## 837DeclareGlobalFunction( "PermCandidatesFaithful" ); 838