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&nbsp;<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&nbsp;<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&nbsp;<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>&lt;sup><A>n</A>&lt;/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&nbsp;<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&nbsp;<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.&nbsp;<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&nbsp;<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&nbsp;<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&nbsp;<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&nbsp;<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&nbsp;<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&nbsp;<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 &lt; i</M>.
633##  These inequalities are used to construct characters with nonnegative
634##  values (see&nbsp;<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&nbsp;<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&nbsp;<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