68.14 Computing Possible Permutation Characters

GAP provides several algorithms to determine possible permutation characters from a given character table. They are described in detail in BP98. The algorithm is selected from the choice of the record components of the optional argument record arec. The user is encouraged to try different approaches, especially if one choice fails to come to an end.

Regardless of the algorithm used in a specific case, PermChars returns a list of all possible permutation characters with the properties described by arec. There is no guarantee that a character of this list is in fact a permutation character. But an empty list always means there is no permutation character with these properties (e.g., of a certain degree).

In the first form PermChars returns the list of all possible permutation characters of the group with character table tbl. This list might be rather long for big groups, and its computation might take much time. The algorithm is described in Section 3.2 in BP98; it depends on a preprocessing step, where the inequalities arising from the condition p(g) ³ 0 are transformed into a system of inequalities that guides the search (see Inequalities). So the following commands compute the list of 39 possible permutation characters of the Mathieu group M₁₁.

gap> m11:= CharacterTable( "M11" );;
gap> SetName( m11, "m11" );
gap> perms:= PermChars( m11 );;
gap> Length( perms );
39

In the second form PermChars returns the list of all possible permutation characters of tbl that have degree degree. For that purpose, a preprocessing step is performed where essentially the rational character table is inverted in order to determine boundary points for the simplex in which the possible permutation characters of the given degree must lie (see PermBounds). The algorithm is described at the end of Section 3.2 in BP98; Note that inverting big integer matrices needs a lot of time and space. So this preprocessing is restricted to groups with less than 100 classes, say.

gap> deg220:= PermChars( m11, 220 );
[ Character( m11, [ 220, 4, 4, 0, 0, 4, 0, 0, 0, 0 ] ),
  Character( m11, [ 220, 12, 4, 4, 0, 0, 0, 0, 0, 0 ] ),
  Character( m11, [ 220, 20, 4, 0, 0, 2, 0, 0, 0, 0 ] ) ]

In the third form PermChars returns the list of all possible permutation characters that have the properties described by the argument record arec. One such situation has been mentioned above. If arec contains a degree as value of the record component degree then PermChars will behave exactly as in the second form.

gap> deg220 = PermChars( m11, rec( degree:= 220 ) );
true

Instead of degree, arec may have the component torso bound to a list that contains some known values of the required characters at the right positions; at least the degree arec.torso[1] must be an integer. In this case, the algorithm described in Section 3.3 in BP98 is chosen. The component chars, if present, holds a list of all those rational irreducible characters of tbl that might be constituents of the required characters.

(Note: If arec.chars is bound and does not contain all rational irreducible characters of tbl, GAP checks whether the scalar products of all class functions in the result list with the omitted rational irreducible characters of tbl are nonnegative; so there should be nontrivial reasons for excluding a character that is known to be not a constituent of the desired possible permutation characters.)

gap> PermChars( m11, rec( torso:= [ 220 ] ) );
[ Character( m11, [ 220, 4, 4, 0, 0, 4, 0, 0, 0, 0 ] ),
  Character( m11, [ 220, 20, 4, 0, 0, 2, 0, 0, 0, 0 ] ),
  Character( m11, [ 220, 12, 4, 4, 0, 0, 0, 0, 0, 0 ] ) ]
gap> PermChars( m11, rec( torso:= [ 220,,,,, 2 ] ) );
[ Character( m11, [ 220, 20, 4, 0, 0, 2, 0, 0, 0, 0 ] ) ]

An additional restriction on the possible permutation characters computed can be forced if arec contains, in addition to torso, the components normalsubgroup and nonfaithful, with values a list of class positions of a normal subgroup N of the group G of tbl and a possible permutation character p of G, respectively, such that N is contained in the kernel of p. In this case, PermChars returns the list of those possible permutation characters y of tbl coinciding with torso whereever its values are bound and having the property that no irreducible constituent of y-p has N in its kernel. If the component chars is bound in arec then the above statements apply. An interpretation of the computed characters is the following. Suppose there exists a subgroup V of G such that p = (1_V)^G; Then N £ V, and if a computed character is of the form (1_U)^G for a s ubgroup U of G then V = UN.

gap> s4:= CharacterTable( "Symmetric", 4 );;
gap> nsg:= ClassPositionsOfDerivedSubgroup( s4 );;
gap> pi:= TrivialCharacter( s4 );;
gap> PermChars( s4, rec( torso:= [ 12 ], normalsubgroup:= nsg,
>                        nonfaithful:= pi ) );
[ Character( CharacterTable( "Sym(4)" ), [ 12, 2, 0, 0, 0 ] ) ]
gap> pi:= Sum( Filtered( Irr( s4 ),
>              chi -> IsSubset( ClassPositionsOfKernel( chi ), nsg ) ) );
Character( CharacterTable( "Sym(4)" ), [ 2, 0, 2, 2, 0 ] )
gap> PermChars( s4, rec( torso:= [ 12 ], normalsubgroup:= nsg,
>                        nonfaithful:= pi ) );
[ Character( CharacterTable( "Sym(4)" ), [ 12, 0, 4, 0, 0 ] ) ]

The class functions returned by PermChars have the properties tested by TestPerm1, TestPerm2, and TestPerm3. So they are possible permutation characters. See TestPerm1 for criteria whether a possible permutation character can in fact be a permutation character.

The first three of these functions implement tests of the properties of possible permutation characters listed in Section Possible Permutation Characters, The other two implement test of additional properties. Let tbl be the ordinary character table of a group G, say, char a rational character of tbl, and chars a list of rational characters of tbl. For applying TestPerm5, the knowledge of a p-modular Brauer table modtbl of G is required. TestPerm4 and TestPerm5 expect the characters in chars to satisfy the conditions checked by TestPerm1 and TestPerm2 (see below).

The return values of the functions were chosen parallel to the tests listed in NPP84.

TestPerm1 return 1 or 2 if char fails because of (T1) or (T2), respectively; this corresponds to the criteria (b) and (d). Note that only those power maps are considered that are stored on tbl. If char satisfies the conditions, 0 is returned.

TestPerm2 returns 1 if char fails because of the criterion (c), it returns 3, 4, or 5 if char fails because of (T3), (T4), or (T5), respectively; these tests correspond to (g), a weaker form of (h), and (j). If char satisfies the conditions, 0 is returned.

TestPerm3 returns the list of all those class functions in the list chars that satisfy criterion (h); this is a stronger version of (T6).

TestPerm4 returns the list of all those class functions in the list chars that satisfy (T8) and (T9) for each prime divisor p of the order of G; these tests use modular representation theory but do not require the knowledge of decomposition matrices (cf. TestPerm5 below).

(T8) implements the test of the fact that in the case that p divides |G| and the degree of a transitive permutation character p exactly once, the projective cover of the trivial character is a summand of p. (This test is omitted if the projective cover cannot be identified.)

Given a permutation character p of a group G and a prime integer p, the restriction p_B to a p-block B of G has the following property, which is checked by (T9). For each g Î G such that gⁿ is a p-element of G, p_B(gⁿ) is a nonnegative integer that satisfies |p_B(g)| £ p_B(gⁿ) £ p(gⁿ). (This is Corollary A on p. 113 of Sco73.)

TestPerm5 requires the p-modular Brauer table modtbl of G, for some prime p dividing the order of G, and checks whether those characters in the list chars whose degree is divisible by the p-part of the order of G can be decomposed into projective indecomposable characters; TestPerm5 returns the sublist of all those characters in chars that either satisfy this condition or to which the test does not apply.

gap> tbl:= CharacterTable( "A5" );;
gap> rat:= RationalizedMat( Irr( tbl ) );          
[ Character( CharacterTable( "A5" ), [ 1, 1, 1, 1, 1 ] ), 
  Character( CharacterTable( "A5" ), [ 6, -2, 0, 1, 1 ] ), 
  Character( CharacterTable( "A5" ), [ 4, 0, 1, -1, -1 ] ), 
  Character( CharacterTable( "A5" ), [ 5, 1, -1, 0, 0 ] ) ]
gap> tup:= Filtered( Tuples( [ 0, 1 ], 4 ), x -> not IsZero( x ) );  
[ [ 0, 0, 0, 1 ], [ 0, 0, 1, 0 ], [ 0, 0, 1, 1 ], [ 0, 1, 0, 0 ], 
  [ 0, 1, 0, 1 ], [ 0, 1, 1, 0 ], [ 0, 1, 1, 1 ], [ 1, 0, 0, 0 ], 
  [ 1, 0, 0, 1 ], [ 1, 0, 1, 0 ], [ 1, 0, 1, 1 ], [ 1, 1, 0, 0 ], 
  [ 1, 1, 0, 1 ], [ 1, 1, 1, 0 ], [ 1, 1, 1, 1 ] ]
gap> lincomb:= List( tup, coeff -> coeff * rat );;
gap> List( lincomb, psi -> TestPerm1( tbl, psi ) );
[ 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0 ]
gap> List( lincomb, psi -> TestPerm2( tbl, psi ) );
[ 0, 5, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1 ]
gap> Set( List( TestPerm3( tbl, lincomb ), x -> Position( lincomb, x ) ) );
[ 1, 4, 6, 7, 8, 9, 10, 11, 13 ]
gap> tbl:= CharacterTable( "A7" );
CharacterTable( "A7" )
gap> perms:= PermChars( tbl, rec( degree:= 315 ) );
[ Character( CharacterTable( "A7" ), [ 315, 3, 0, 0, 3, 0, 0, 0, 0 ] ), 
  Character( CharacterTable( "A7" ), [ 315, 15, 0, 0, 1, 0, 0, 0, 0 ] ) ]
gap> TestPerm4( tbl, perms );
[ Character( CharacterTable( "A7" ), [ 315, 15, 0, 0, 1, 0, 0, 0, 0 ] ) ]
gap> perms:= PermChars( tbl, rec( degree:= 15 ) ); 
[ Character( CharacterTable( "A7" ), [ 15, 3, 0, 3, 1, 0, 0, 1, 1 ] ), 
  Character( CharacterTable( "A7" ), [ 15, 3, 3, 0, 1, 0, 3, 1, 1 ] ) ]
gap> TestPerm5( tbl, perms, tbl mod 5 );
[ Character( CharacterTable( "A7" ), [ 15, 3, 0, 3, 1, 0, 0, 1, 1 ] ) ]

Let tbl be the ordinary character table of the group G. All G-characters p satisfying p(g) > 0 and p(1) = d , for a given degree d, lie in a simplex described by these conditions. PermBounds computes the boundary points of this simplex for d = 0, from which the boundary points for any other d are easily derived. (Some conditions from the power maps of tbl are also involved.) For this purpose, a matrix similar to the rational character table of G has to be inverted. These boundary points are used by PermChars (see PermChars) to construct all possible permutation characters (see Possible Permutation Characters) of a given degree. PermChars either calls PermBounds or takes this information from the bounds component of its argument record.

PermComb computes possible permutation characters of the character table tbl by the improved combinatorial approach described at the end of Section 3.2 in BP98.

For computing the possible linear combinations without prescribing better bounds (i.e., when the computation of bounds shall be suppressed), enter arec:= rec( degree := degree, bounds := false ), where degree is the character degree; this is useful if the multiplicities are expected to be small, and if this is forced by high irreducible degrees.

Upper bounds on the multiplicities of the constituents can be explicitly prescribed via a maxmult component in arec.

Let tbl be the ordinary character table of a group G. The condition p(g) ³ 0 for every possible permutation character p of G places restrictions on the multiplicities a_i of the irreducible constituents c_i of p = å_{i = 1}^r a_i c_i. For every element g Î G, we have å_{i = 1}^r a_i c_i(g) ³ 0. The power maps provide even stronger conditions.

This system of inequalities is kind of diagonalized, resulting in a system of inequalities restricting a_i in terms of a_j, j < i. These inequalities are used to construct characters with nonnegative values (see PermChars). PermChars either calls Inequalities or takes this information from the ineq component of its argument record.

The number of inequalities arising in the process of diagonalization may grow very strongly.

There are two ways to organize the projection. The first, which is chosen if no option argument is present, is the straight approach which takes the rational irreducible characters in their original order and by this guarantees the character with the smallest degree to be considered first. The other way, which is chosen if the string "small" is entered as third argument, tries to keep the number of intermediate inequalities small by eventually changing the order of characters.

[Top] [Previous] [Up] [Next] [Index]