home *** CD-ROM | disk | FTP | other *** search
/ Math Solutions 1995 October / Math_Solutions_CD-ROM_Walnut_Creek_October_1995.iso / pc / mac / discrete / doc / tom.tex < prev    next >
Encoding:
Text File  |  1993-05-05  |  27.8 KB  |  705 lines
  1. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  2. %%
  3. %A  tom.tex                  GAP documentation                Goetz Pfeiffer.
  4. %%
  5. %A  @(#)$Id: tom.tex,v 3.11 1993/02/19 10:48:42 gap Exp $
  6. %%
  7. %Y  Copyright 1991-1992,  Lehrstuhl D fuer Mathematik,  RWTH Aachen,  Germany
  8. %%
  9. %%  This file describes the functions dealing with Tables Of Marks.
  10. %%
  11. %H  $Log: tom.tex,v $
  12. %H  Revision 3.11  1993/02/19  10:48:42  gap
  13. %H  adjustments in line length and spelling
  14. %H
  15. %H  Revision 3.10  1993/02/12  17:02:59  felsch
  16. %H  examples adjusted to line length 72
  17. %H
  18. %H  Revision 3.9  1993/02/11  17:46:09  martin
  19. %H  changed '@' to '&'
  20. %H
  21. %H  Revision 3.8  1993/02/02  12:46:54  felsch
  22. %H  long lines fixed
  23. %H
  24. %H  Revision 3.7  1993/01/22  19:35:52  martin
  25. %H  changed |"<order>"| to '\"<order>\"' etc.
  26. %H
  27. %H  Revision 3.6  1993/01/22  17:23:17  goetz
  28. %H  deleted some lines.
  29. %H
  30. %H  Revision 3.5  1993/01/21  17:04:47  goetz
  31. %H  added references, formatted examples.
  32. %H
  33. %H  Revision 3.4  1993/01/20  15:41:23  goetz
  34. %H  corrections and additions.
  35. %H
  36. %H  Revision 3.3  1993/01/19  13:40:17  goetz
  37. %H  extensions and corrections.
  38. %H
  39. %H  Revision 3.2  1992/12/01  14:29:10  goetz
  40. %H  added formula.
  41. %H
  42. %H  Revision 3.1  1992/12/01  14:23:51  goetz
  43. %H  formatted displayed material.
  44. %H
  45. %H  Revision 3.0  1992/11/15  15:47:46  goetz
  46. %H  Initial Revision.
  47. %H
  48. %%
  49. \Chapter{Tables of Marks}
  50.  
  51. The concept of a table of marks was introduced by W.~Burnside in his book
  52. <Theory of Groups of Finite  Order> \cite{Bur55}.   Therefore a table  of
  53. marks is sometimes called a Burnside matrix.
  54.  
  55. The table  of marks of  a finite group $G$  is  a  matrix whose rows  and
  56. columns are labelled by  the conjugacy classes of subgroups  of  $G$  and
  57. where for  two subgroups $A$ and $B$ the $(A, B)$--entry is the number of
  58. fixed points of $B$ in the transitive action of  $G$ on the cosets of $A$
  59. in   $G$.   So   the  table   of  marks  characterizes   all  permutation
  60. representations of $G$.
  61.  
  62. Moreover,  the table of marks gives a compact description of the subgroup
  63. lattice of $G$,  since from the numbers  of  fixed points the numbers  of
  64. conjugates of a subgroup $B$ contained in a subgroup $A$ can be derived.
  65.  
  66. This chapter describes a  function (see  "TableOfMarks") which restores a
  67. table  of  marks from the  {\GAP}  library  of tables  of marks (see "The
  68. Library of Tables of Marks") or which computes the table  of marks  for a
  69. given  group from  the  subgroup lattice  of  that group.   Moreover this
  70. package   contains   a   function  to  display  a  table  of  marks  (see
  71. "DisplayTom"), a function to  check the consistency of  a table  of marks
  72. (see  "TestTom"),  functions   which  switch  between  several  forms  of
  73. representation (see "Marks", "NrSubs", "MatTom", and "TomMat"), functions
  74. which derive  information about the  group  from  the table of marks (see
  75. "DecomposedFixedPointVector",     "NormalizerTom",    "IntersectionsTom",
  76. "IsCyclicTom",   "FusionCharTableTom",    "PermCharsTom",   "MoebiusTom",
  77. "CyclicExtensionsTom",     "IdempotentsTom",     "ClassTypesTom",     and
  78. "ClassNamesTom"),  and  some  functions for the generic construction of a
  79. table of marks (see "TomCyclic", "TomDihedral", and "TomFrobenius").
  80.  
  81. The  functions described  in this  chapter are  implemented  in the  file
  82. 'LIBNAME/\"tom.g\"'.
  83.  
  84. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  85. \Section{More about Tables of Marks}
  86.  
  87. Let  $G$ be a finite  group with $n$ conjugacy classes of subgroups $C_1,
  88. \ldots, C_n$ and representatives $H_i \in  C_i$, $i = 1, \ldots, n$.  The
  89. *table of  marks*  of $G$  is defined  to  be the  $n  \times  n$  matrix
  90. $M  = (m_{ij})$  where $m_{ij}$  is the  number  of fixed points  of  the
  91. subgroup $H_j$ in the action of $G$ on the cosets of $H_i$ in $G$.
  92.  
  93. Since $H_j$ can only have fixed points if it is contained in a one  point
  94. stablizer the  matrix $M$ is  lower  triangular  if the classes $C_i$ are
  95. sorted according to the following condition; if $H_i$ is  contained in  a
  96. conjugate of $H_j$ then $i \leq j$.
  97.  
  98. Moreover, the diagonal entries $m_{ii}$ are nonzero since $m_{ii}$ equals
  99. the index of  $H_i$  in its normalizer in $G$.  Hence  $M$ is invertible.
  100. Since  any transitive action of  $G$ is  equivalent  to an action on  the
  101. cosets of a subgroup of $G$, one sees that the table of  marks completely
  102. characterizes permutation representations of $G$.
  103.  
  104. The entries $m_{ij}$  have further  meanings.  If  $H_1$  is the  trivial
  105. subgroup of  $G$ then  each mark $m_{i1}$  in the first column  of $M$ is
  106. equal to the index of $H_i$ in  $G$ since the trivial  subgroup fixes all
  107. cosets of $H_i$.  If $H_n = G$ then each $m_{nj}$  in the last row of $M$
  108. is equal  to 1 since there is only  one coset of $G$ in $G$.  In general,
  109. $m_{ij}$  equals the  number of conjugates of $H_i$ which  contain $H_j$,
  110. multiplied by the index of $H_i$ in its normalizer in $G$.  Moreover, the
  111. number $c_{ij}$ of  conjugates of $H_j$ which are contained in $H_i$  can
  112. be derived from the marks $m_{ij}$ via the formula
  113.  
  114. \[ c_{ij} = \frac{m_{ij} m_{j1}}{m_{i1} m_{jj}}. \]
  115.  
  116. Both the marks $m_{ij}$  and the numbers of subgroups $c_{ij}$ are needed
  117. for the functions described in this chapter.
  118.  
  119. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  120. \Section{Table of Marks Records}
  121.  
  122. A table of marks is represented by a record.   This record has at least a
  123. component  'subs' which is  a  list  where for each  conjugacy  class  of
  124. subgroups the class  numbers  of its  subgroups  are  stored.  These  are
  125. exactly  the positions in the  corresponding row of  the  table of  marks
  126. which have nonzero entries.
  127.  
  128. The marks  themselves  can be stored in the component 'marks' which is  a
  129. list   that  contains   for  each  entry  in  the  component  'subs'  the
  130. corresponding nonzero value of the table of marks.
  131.  
  132. The same information is, however, given by the three components 'nrSubs',
  133. 'length', and  'order', where 'nrSubs' is a  list which contains for each
  134. entry  in  the  component 'subs'  the  corresponding number of conjugates
  135. which are contained in a subgroup,  'length' is a list which contains for
  136. each class of subgroups its  length, and 'order' is a list which contains
  137. for each class of subgroups their order.
  138.  
  139. So a table of marks consists either of the components 'subs' and  'marks'
  140. or of  the  components  'subs',  'nrSubs',  'length', and  'order'.   The
  141. functions 'Marks' (see  "Marks") and 'NrSubs' (see "NrSubs")  will derive
  142. one representation from the other when needed.
  143.  
  144. Additional  information  about  a  table  of  marks  is  needed  by  some
  145. functions.  The class  numbers of normalizers are stored in the component
  146. 'normalizer'.   The number of  the derived subgroup of the whole group is
  147. stored in the component 'derivedSubgroup'.
  148.  
  149. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  150. \Section{The Library of Tables of Marks}
  151.  
  152. This  package  of  functions comes together  with a library of tables  of
  153. marks.   The library files are stored in a directory 'TOMNAME'.  The file
  154. 'TOMNAME/\"tmprimar.tom\"' is the  primary file of the library  of tables
  155. of  marks.   It contains the  information where  to find  a table and the
  156. function 'TomLibrary' which restores a table from the library.
  157.  
  158. The secondary files are
  159.  
  160. |    tmaltern.tom  tmmath24.tom  tmsuzuki.tom  tmunitar.tom
  161.     tmlinear.tom  tmmisc.tom    tmsporad.tom  tmsymple.tom |
  162.  
  163. The list 'TOMLIST' contains for each table an entry with its name and the
  164. name of the file where it is stored.
  165.  
  166. A table  of marks which is restored from  the library will be stored as a
  167. component of the record 'TOM'.
  168.  
  169. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  170. \Section{TableOfMarks}
  171.  
  172. 'TableOfMarks( <str> )'
  173.  
  174. If  the  argument  <str>  given   to  'TableOfMarks'  is  a  string  then
  175. 'TableOfMarks'  will  search  the  library of tables  of marks  (see "The
  176. Library of  Tables of  Marks") for  a table with  name  <str>.  If such a
  177. table is found then  'TableOfMarks' will  return  a  copy of  that table.
  178. Otherwise 'TableOfMarks' will return 'false'.
  179.  
  180. |    gap> a5 := TableOfMarks( "A5" );
  181.     rec(
  182.       derivedSubgroup := 9,
  183.       nrSubs := [ [ 1 ], [ 1, 1 ], [ 1, 1 ], [ 1, 3, 1 ], [ 1, 1 ], 
  184.           [ 1, 3, 1, 1 ], [ 1, 5, 1, 1 ], [ 1, 3, 4, 1, 1 ], 
  185.           [ 1, 15, 10, 5, 6, 10, 6, 5, 1 ] ],
  186.       order := [ 1, 2, 3, 4, 5, 6, 10, 12, 60 ],
  187.       subs := [ [ 1 ], [ 1, 2 ], [ 1, 3 ], [ 1, 2, 4 ], [ 1, 5 ], 
  188.           [ 1, 2, 3, 6 ], [ 1, 2, 5, 7 ], [ 1, 2, 3, 4, 8 ], 
  189.           [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ] ],
  190.       length := [ 1, 15, 10, 5, 6, 10, 6, 5, 1 ] )
  191.     gap> TableOfMarks( "A10" );
  192.     &W  TableOfMarks: no table of marks A10 found.
  193.     false |
  194.  
  195. 'TableOfMarks( <grp> )'
  196. \index{TableOfMarks}
  197.  
  198. If  'TableOfMarks' is called with a  group <grp> as its argument then the
  199. table of marks  of  that  group  will  be  computed and  returned in  the
  200. compressed format.  The computation of the  table of  marks  requires the
  201. knowledge of the  complete subgroup  lattice  of the group <grp>.  If the
  202. lattice is not yet known  then  it will be  constructed (see  "Lattice").
  203. This  may  take a  while  if the group  <grp>  is  large.
  204.  
  205. Moreover,  as  the 'Lattice'  command  is  involved  the applicability of
  206. 'TableOfMarks' underlies  the  same  restrictions  with  respect  to  the
  207. soluble residuum of <grp> as  described in section "Lattice".  The result
  208. of  'TableOfMarks' is  assigned to the  component  'tableOfMarks' of  the
  209. group record <grp>, so that the next call to 'TableOfMarks' with the same
  210. argument can just return this component 'tableOfMarks'.
  211.  
  212. *Warning*\:\  Note  that  'TableOfMarks'  has  changed with  the  release
  213. {\GAP}  3.2.  It  now returns  the table  of  marks  in compressed  form.
  214. However, you  can apply the 'MatTom' command (see "MatTom") to convert it
  215. into  the square  matrix  which was  returned by 'TableOfMarks' in {\GAP}
  216. version 3.1.
  217.  
  218. |    gap> alt5 := AlternatingPermGroup( 5 );;
  219.     gap> TableOfMarks( alt5 );
  220.     rec(
  221.       subs := [ [ 1 ], [ 2, 1 ], [ 3, 1 ], [ 4, 1, 2 ], [ 5, 1 ], 
  222.           [ 6, 1, 2, 3 ], [ 7, 1, 2, 5 ], [ 8, 1, 2, 3, 4 ], 
  223.           [ 9, 1, 2, 3, 4, 5, 6, 7, 8 ] ],
  224.       marks := [ [ 60 ], [ 2, 30 ], [ 2, 20 ], [ 3, 15, 3 ], [ 2, 12 ], 
  225.           [ 1, 10, 2, 1 ], [ 1, 6, 2, 1 ], [ 1, 5, 1, 2, 1 ], 
  226.           [ 1, 1, 1, 1, 1, 1, 1, 1, 1 ] ] )
  227.     gap> last = alt5.tableOfMarks;
  228.     true |
  229.  
  230. For a pretty print display of a table of marks see "DisplayTom".
  231.  
  232. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  233. \Section{Marks}
  234.  
  235. 'Marks( <tom> )'
  236.  
  237. 'Marks' returns the list of lists of marks  of the table of  marks <tom>.
  238. If  these are not yet stored in the  component 'marks' of <tom> then they
  239. will be computed and assigned to the component 'marks'.
  240.  
  241. |    gap> Marks( a5 );
  242.     [ [ 60 ], [ 30, 2 ], [ 20, 2 ], [ 15, 3, 3 ], [ 12, 2 ], 
  243.       [ 10, 2, 1, 1 ], [ 6, 2, 1, 1 ], [ 5, 1, 2, 1, 1 ], 
  244.       [ 1, 1, 1, 1, 1, 1, 1, 1, 1 ] ] |
  245.  
  246. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  247. \Section{NrSubs}
  248.  
  249. 'NrSubs( <tom> )'
  250.  
  251. 'NrSubs' returns the list of lists of numbers  of subgroups of the  table
  252. of marks <tom>.  If these are not yet stored in the component 'nrSubs' of
  253. <tom> then they will be computed and assigned to the component 'nrSubs'.
  254.  
  255. 'NrSubs' also has to compute the orders and lengths from the marks.
  256.  
  257. |    gap> NrSubs( a5 );
  258.     [ [ 1 ], [ 1, 1 ], [ 1, 1 ], [ 1, 3, 1 ], [ 1, 1 ], [ 1, 3, 1, 1 ], 
  259.       [ 1, 5, 1, 1 ], [ 1, 3, 4, 1, 1 ], [ 1, 15, 10, 5, 6, 10, 6, 5, 1 ] 
  260.      ]|
  261.  
  262. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  263. \Section{WeightsTom}
  264.  
  265. 'WeightsTom( <tom> )'
  266.  
  267. 'WeightsTom' extracts the weights from a table of  marks <tom>, i.e., the
  268. diagonal entries, indicating the index of a subgroup in its normalizer.
  269.  
  270. |    gap> wt := WeightsTom( a5 ); 
  271.     [ 60, 2, 2, 3, 2, 1, 1, 1, 1 ] |
  272.  
  273. This  information  may  be  used  to  obtain  the  numbers  of  conjugate
  274. supergroups from the marks.
  275.  
  276. |    gap> marks := Marks( a5 );; 
  277.     gap> List( [ 1 .. 9 ], x -> marks[x] / wt[x] );
  278.     [ [ 1 ], [ 15, 1 ], [ 10, 1 ], [ 5, 1, 1 ], [ 6, 1 ], [ 10, 2, 1, 1 ],
  279.       [ 6, 2, 1, 1 ], [ 5, 1, 2, 1, 1 ], [ 1, 1, 1, 1, 1, 1, 1, 1, 1 ] ]|
  280.  
  281. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  282. \Section{MatTom}
  283.  
  284. 'MatTom( <tom> )'
  285.  
  286. 'MatTom'  produces a square matrix corresponding  to the  table  of marks
  287. <tom> in compressed form.  For large tables this may need a lot of space.
  288.  
  289. |    gap> MatTom( a5 );
  290.     [ [ 60, 0, 0, 0, 0, 0, 0, 0, 0 ], [ 30, 2, 0, 0, 0, 0, 0, 0, 0 ], 
  291.       [ 20, 0, 2, 0, 0, 0, 0, 0, 0 ], [ 15, 3, 0, 3, 0, 0, 0, 0, 0 ], 
  292.       [ 12, 0, 0, 0, 2, 0, 0, 0, 0 ], [ 10, 2, 1, 0, 0, 1, 0, 0, 0 ], 
  293.       [ 6, 2, 0, 0, 1, 0, 1, 0, 0 ], [ 5, 1, 2, 1, 0, 0, 0, 1, 0 ], 
  294.       [ 1, 1, 1, 1, 1, 1, 1, 1, 1 ] ] |
  295.  
  296. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  297. \Section{TomMat}
  298.  
  299. 'TomMat( <mat> )'
  300.  
  301. Given a matrix <mat> which contains the marks of a group as  its entries,
  302. 'TomMat' will produce the corresponding table of marks record.
  303.  
  304. |    gap> mat:= 
  305.     > [ [ 60, 0, 0, 0, 0, 0, 0, 0, 0 ], [ 30, 2, 0, 0, 0, 0, 0, 0, 0 ], 
  306.     >   [ 20, 0, 2, 0, 0, 0, 0, 0, 0 ], [ 15, 3, 0, 3, 0, 0, 0, 0, 0 ], 
  307.     >   [ 12, 0, 0, 0, 2, 0, 0, 0, 0 ], [ 10, 2, 1, 0, 0, 1, 0, 0, 0 ], 
  308.     >   [ 6, 2, 0, 0, 1, 0, 1, 0, 0 ], [ 5, 1, 2, 1, 0, 0, 0, 1, 0 ], 
  309.     >   [ 1, 1, 1, 1, 1, 1, 1, 1, 1 ] ];;
  310.     gap> TomMat( mat );
  311.     rec(
  312.       subs := [ [ 1 ], [ 1, 2 ], [ 1, 3 ], [ 1, 2, 4 ], [ 1, 5 ], 
  313.           [ 1, 2, 3, 6 ], [ 1, 2, 5, 7 ], [ 1, 2, 3, 4, 8 ], 
  314.           [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ] ],
  315.       marks := [ [ 60 ], [ 30, 2 ], [ 20, 2 ], [ 15, 3, 3 ], [ 12, 2 ], 
  316.           [ 10, 2, 1, 1 ], [ 6, 2, 1, 1 ], [ 5, 1, 2, 1, 1 ], 
  317.           [ 1, 1, 1, 1, 1, 1, 1, 1, 1 ] ] )
  318.     gap> TomMat( IdentityMat( 7 ) );
  319.     rec(
  320.       subs := [ [ 1 ], [ 2 ], [ 3 ], [ 4 ], [ 5 ], [ 6 ], [ 7 ] ],
  321.       marks := [ [ 1 ], [ 1 ], [ 1 ], [ 1 ], [ 1 ], [ 1 ], [ 1 ] ] ) |
  322.  
  323. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  324. \Section{DecomposedFixedPointVector}
  325.  
  326. 'DecomposedFixedPointVector( <tom>, <fix> )'
  327.  
  328. Let the group with table of marks <tom> act as a permutation group on its
  329. conjugacy  classes of subgroups, then  <fix> is assumed to be a vector of
  330. fixed  point numbers, i.e., a vector which contains  for  each  class  of
  331. subgroups   the   number   of   fixed   points    under    that   action.
  332. 'DecomposedFixedPointVector' returns the decomposition of <fix> into rows
  333. of the table of marks. This decomposition  corresponds to a decomposition
  334. of  the action into transitive constituents. Trailing  zeros in <fix> may
  335. be omitted.
  336.  
  337. |    gap> DecomposedFixedPointVector( a5, [ 16, 4, 1, 0, 1, 1, 1 ] );
  338.     [ ,,,,, 1, 1 ] |
  339.  
  340. The  vector  <fix>  may  be  any  vector  of  integers.    The  resulting
  341. decomposition, however, will not be integral, in general.
  342.  
  343. |    gap> DecomposedFixedPointVector( a5, [ 0, 0, 0, 0, 1, 1 ] );
  344.     [ 2/5, -1, -1/2,, 1/2, 1 ] |
  345.  
  346. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  347. \Section{TestTom}
  348.  
  349. 'TestTom( <tom> )'
  350.  
  351. 'TestTom' decomposes  all  tensor products of rows of  the table of marks
  352. <tom>.  It returns 'true' if all  decomposition  numbers are  nonnegative
  353. integers and 'false' otherwise.  This provides a strong consistency check
  354. for a table of marks.
  355.  
  356. |    gap> TestTom( a5 );
  357.     true |
  358.  
  359. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  360. \Section{DisplayTom}
  361.  
  362. 'DisplayTom( <tom> )'
  363.  
  364. 'DisplayTom' produces a formatted  output for the  table of  marks <tom>.
  365. Each line of output begins with the number of the corresponding  class of
  366. subgroups.  This number is repeated if  the  output spreads  over several
  367. pages.
  368.  
  369. |    gap> DisplayTom( a5 );
  370.     1:  60
  371.     2:  30 2
  372.     3:  20 . 2
  373.     4:  15 3 . 3
  374.     5:  12 . . . 2
  375.     6:  10 2 1 . . 1
  376.     7:   6 2 . . 1 . 1
  377.     8:   5 1 2 1 . . . 1
  378.     9:   1 1 1 1 1 1 1 1 1 |
  379.  
  380. 'DisplayTom( <tom>, <arec> )'
  381.  
  382. In  this  form  'DisplayTom'  takes  a  record  <arec> as  an  additional
  383. parameter.   If this record  has a component  'classes' which contains  a
  384. list of  class  numbers then only  the  rows  and  columns of  the matrix
  385. corresponding to this list are printed.
  386.  
  387. |    gap> DisplayTom( a5, rec( classes := [ 1, 2, 3, 4, 8 ] ) );
  388.     1:  60
  389.     2:  30 2
  390.     3:  20 . 2
  391.     4:  15 3 . 3
  392.     8:   5 1 2 1 1 |
  393.  
  394. The record <arec> may also  have a  component  'form' which  enables  the
  395. printing of  tables of  numbers of subgroups.  If <arec>.'form'  has  the
  396. value '\"subgroups\"' then  at position $(i,j)$  the number of conjugates
  397. of $H_j$  contained  in  $H_i$  will  be  printed.  If it  has  the value
  398. '\"supergroups\"' then at position $(i,j)$  the  number  of conjugates of
  399. $H_i$ which contain $H_j$ will be printed.
  400.  
  401. |    gap> DisplayTom( a5, rec( form := "subgroups" ) );
  402.     1:  1
  403.     2:  1  1
  404.     3:  1  .  1
  405.     4:  1  3  . 1
  406.     5:  1  .  . . 1
  407.     6:  1  3  1 . .  1
  408.     7:  1  5  . . 1  . 1
  409.     8:  1  3  4 1 .  . . 1
  410.     9:  1 15 10 5 6 10 6 5 1
  411.     
  412.     gap> DisplayTom( a5, rec( form := "supergroups" ) );
  413.     1:   1
  414.     2:  15 1
  415.     3:  10 . 1
  416.     4:   5 1 . 1
  417.     5:   6 . . . 1
  418.     6:  10 2 1 . . 1
  419.     7:   6 2 . . 1 . 1
  420.     8:   5 1 2 1 . . . 1
  421.     9:   1 1 1 1 1 1 1 1 1 |
  422.  
  423. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  424. \Section{NormalizerTom}
  425.  
  426. 'NormalizerTom( <tom>, <u> )'
  427.  
  428. 'NormalizerTom' tries  to  find conjugacy  class  of the normalizer  of a
  429. subgroup with class number <u>.  It will return the list of class numbers
  430. of those subgroups which have the right size and contain the subgroup and
  431. all  subgroups  which  clearly contain it as  a normal subgroup.   If the
  432. normalizer is uniquely determined by these conditions then only its class
  433. number  will be returned.   'NormalizerTom' should  never return an empty
  434. list.
  435.  
  436. |    gap> NormalizerTom( a5, 4 );
  437.     8 |
  438.  
  439. The example shows that a subgroup with class number 4 in $A_5$ (which  is
  440. a Kleinan four group) is normalized by a subgroup in class 8.  This class
  441. contains the subgroups of $A_5$ which are isomorphic to $A_4$.
  442.  
  443. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  444. \Section{IntersectionsTom}
  445.  
  446. 'IntersectionsTom( <tom>, <a>, <b> )'
  447.  
  448. The intersections of  the two  conjugacy classes of subgroups  with class
  449. numbers <a> and <b>, respectively, are determined by the decomposition of
  450. the tensor product of their rows  of  marks.   'IntersectionsTom' returns
  451. this decomposition.
  452.  
  453. |    gap> IntersectionsTom( a5, 8, 8 );
  454.     [ ,, 1,,,,, 1 ] |
  455.  
  456. Any two subgroups of class number 8 ($A_4$) of $A_5$ are either equal and
  457. their intersection has again  class number  8, or their intersection  has
  458. class number $3$, and is a cyclic subgroup of order 3.
  459.  
  460. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  461. \Section{IsCyclicTom}
  462.  
  463. 'IsCyclicTom( <tom>, <n> )'
  464.  
  465. A subgroup is cyclic if and only if the sum over the corresponding row of
  466. the inverse table of marks is nonzero (see \cite{Ker91}, page 125).  Thus
  467. we only have to decompose the corresponding idempotent.
  468.  
  469. |    gap> for i in [ 1 .. 6 ] do                       
  470.     > Print( i, ": ", IsCyclicTom(a5, i), "  " );
  471.     > od;  Print( "\n" );
  472.     1: true  2: true  3: true  4: false  5: true  6: false   |
  473.  
  474. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  475. \Section{FusionCharTableTom}
  476.  
  477. 'FusionCharTableTom( <tbl>, <tom> )'
  478.  
  479. 'FusionCharTableTom' determines  the fusion of the  classes  of  elements
  480. from  the  character table <tbl> into classes of cyclic subgroups  on the
  481. table of marks <tom>.
  482.  
  483. |    gap> a5c := CharTable( "A5" );;
  484.     gap> fus := FusionCharTableTom( a5c, a5 );
  485.     [ 1, 2, 3, 5, 5 ] |
  486.  
  487. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  488. \Section{PermCharsTom}
  489.  
  490. 'PermCharsTom( <tom>, <fus> )'
  491.  
  492. 'PermCharsTom' reads the list of permutation characters from the table of
  493. marks <tom>.  It therefore has to  know  the fusion map <fus> which sends
  494. each conjugacy  class of elements  of the group to the conjugacy class of
  495. subgroups  they generate.
  496.  
  497. |    gap> PermCharsTom( a5, fus );
  498.     [ [ 60, 0, 0, 0, 0 ], [ 30, 2, 0, 0, 0 ], [ 20, 0, 2, 0, 0 ], 
  499.       [ 15, 3, 0, 0, 0 ], [ 12, 0, 0, 2, 2 ], [ 10, 2, 1, 0, 0 ], 
  500.       [ 6, 2, 0, 1, 1 ], [ 5, 1, 2, 0, 0 ], [ 1, 1, 1, 1, 1 ] ] |
  501.  
  502. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  503. \Section{MoebiusTom}
  504.  
  505. 'MoebiusTom( <tom> )'
  506.  
  507. 'MoebiusTom' computes the M{\accent127 o}bius values both of the subgroup
  508. lattice of  the  group with table of  marks  <tom>  and of  the  poset of
  509. conjugacy classes of  subgroups.  It returns a record where the component
  510. 'mu' contains the M{\accent127 o}bius values of the subgroup lattice, and
  511. the component 'nu' contains the M{\accent127  o}bius values of the poset.
  512. Moreover, according to  a conjecture  of Isaacs et al. (see \cite{HIO89},
  513. \cite{Pah93}), the  values  on the poset of conjugacy classes are derived
  514. from  those  of  the subgroup  lattice.   These  theoretical  values  are
  515. returned  in  the  component 'ex'.  For  that  computation,  the  derived
  516. subgroup  must be known in the component 'derivedSubgroup' of <tom>.  The
  517. numbers  of those subgroups where the theoretical value does not coincide
  518. with the actual value are returned in the component 'hyp'.
  519.  
  520. |    gap> MoebiusTom( a5 );
  521.     rec(
  522.       mu := [ -60, 4, 2,,, -1, -1, -1, 1 ],
  523.       nu := [ -1, 2, 1,,, -1, -1, -1, 1 ],
  524.       ex := [ -60, 4, 2,,, -1, -1, -1, 1 ],
  525.       hyp := [  ] ) |
  526.  
  527. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  528. \Section{CyclicExtensionsTom}
  529.  
  530. 'CyclicExtensionsTom( <tom>, <p> )'
  531.  
  532. According  to  A.~Dress  \cite{Dre69}, two columns of the table  of marks
  533. <tom>  are equal modulo the prime <p> if  and only  if  the corresponding
  534. subgroups are connected  by a chain  of normal extensions  of order  <p>.
  535. 'CyclicExtensionsTom' returns the classes of this equivalence relation.
  536.  
  537. This  information is  not used by  'NormalizerTom' although it might give
  538. additional restrictions in the search of normalizers.
  539.  
  540. |    gap> CyclicExtensionsTom( a5, 2 );
  541.     [ [ 1, 2, 4 ], [ 3, 6 ], [ 5, 7 ], [ 8 ], [ 9 ] ] |
  542.  
  543. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  544. \Section{IdempotentsTom}
  545.  
  546. 'IdempotentsTom( <tom> )'
  547.  
  548. 'IdempotentsTom' returns the list of idempotents of the integral Burnside
  549. ring  described  by  the  table  of marks <tom>.   According  to A.~Dress
  550. \cite{Dre69},  these  idempotents  correspond to the  classes of  perfect
  551. subgroups, and each such idempotent is the characteristic function of all
  552. those  subgroups which arise by cyclic  extension from  the corresponding
  553. perfect subgroup.
  554.  
  555. |    gap> IdempotentsTom( a5 );
  556.     [ 1, 1, 1, 1, 1, 1, 1, 1, 9 ] |
  557.  
  558. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  559. \Section{ClassTypesTom}
  560.  
  561. 'ClassTypesTom( <tom> )'
  562.  
  563. 'ClassTypesTom'   distinguishes  isomorphism  types  of  the  classes  of
  564. subgroups of the  table of marks <tom> as  far  as this is possible.  Two
  565. subgroups  are  clearly  not  isomorphic  if  they have different orders.
  566. Moreover, isomorphic subgroups must contain the  same number of subgroups
  567. of each type.
  568.  
  569. The types are represented by  numbers.   'ClassTypesTom' returns  a  list
  570. which contains for each class of subgroups its corresponding number.
  571.  
  572. |    gap> a6 := TableOfMarks( "A6" );;
  573.     gap> ClassTypesTom( a6 );
  574.     [ 1, 2, 3, 3, 4, 5, 6, 6, 7, 7, 8, 9, 10, 11, 11, 12, 13, 13, 14, 15,
  575.       15, 16 ] |
  576.  
  577. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  578. \Section{ClassNamesTom}
  579.  
  580. 'ClassNamesTom( <tom> )'
  581.  
  582. 'ClassNamesTom' constructs generic  names  for  the conjugacy classes  of
  583. subgroups of the table of marks <tom>.
  584.  
  585. In general, the generic name of a class of non--cyclic subgroups consists
  586. of three  parts, '\"(<order>)\"', '\"\_\{<type>\}\"', and '\"<letter>\"',
  587. and hence has the form '\"(<order>)\_\{<type>\}<letter>\"', where <order>
  588. indicates  the  order   of  the  subgroups,   <type>  is  a  number  that
  589. distinguishes  different  types  of  subgroups  of  the  same order,  and
  590. <letter> is a letter which distinguishes classes of subgroups of the same
  591. type  and order.  The type  of a subgroup is determined by the numbers of
  592. its  subgroups of other  types  (see "ClassTypesTom").  This  is slightly
  593. weaker than isomorphism.
  594.  
  595. The  letter is omitted  if there is only  one class of subgroups  of that
  596. order and  type, and the  type is  omitted if there is only one  class of
  597. that order.  Moreover, the braces round the type are  omitted if the type
  598. number has only one digit.
  599.  
  600. For classes of cyclic subgoups, the parentheses  round  the order and the
  601. type are omitted.  Hence  the most general form of their generic names is
  602. '\"<order>\,<letter>\"'.  Again, the  letter is omitted if there  is only
  603. one class of cyclic subgroups of that order.
  604.  
  605. |    gap> ClassNamesTom( a6 );
  606.     [ "1", "2", "3a", "3b", "5", "4", "(4)_2a", "(4)_2b", "(6)a", "(6)b",
  607.       "(9)", "(10)", "(8)", "(12)a", "(12)b", "(18)", "(24)a", "(24)b", 
  608.       "(36)", "(60)a", "(60)b", "(360)" ] |
  609.  
  610. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  611. \Section{TomCyclic}
  612.  
  613. 'TomCyclic( <n> )'
  614.  
  615. 'TomCyclic' constructs the table  of marks  of the cyclic group  of order
  616. <n>.  A cyclic  group of order <n>  has as its subgroups for each divisor
  617. $d$ of <n> a cyclic subgroup  of order $d$.  The record which is returned
  618. has an additional  component 'name'  where for each subgroup its order is
  619. given as a string.
  620.  
  621. |    gap> c6 := TomCyclic( 6 );
  622.     rec(
  623.       name := [ "1", "2", "3", "6" ],
  624.       subs := [ [ 1 ], [ 1, 2 ], [ 1, 3 ], [ 1, 2, 3, 4 ] ],
  625.       marks := [ [ 6 ], [ 3, 3 ], [ 2, 2 ], [ 1, 1, 1, 1 ] ] )
  626.     gap> DisplayTom( c6 );
  627.     1:  6
  628.     2:  3 3
  629.     3:  2 . 2
  630.     4:  1 1 1 1 |
  631.  
  632. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  633. \Section{TomDihedral}
  634.  
  635. 'TomDihedral( <m> )'
  636.  
  637. 'TomDihedral' constructs  the table  of  marks  of  the dihedral group of
  638. order  <m>.  For  each divisor $d$ of <m>, a dihedral group of order $m =
  639. 2n$ contains  subgroups of order $d$ according to the following rule.  If
  640. $d$ is odd  and divides $n$ then there is  only  one cyclic  subgroup  of
  641. order  $d$.  If  $d$ is even and  divides  $n$ then  there  are  a cyclic
  642. subgroup of order $d$ and two classes of dihedral subgroups of  order $d$
  643. which  are  cyclic,  too,  in the  case  $d  =  2$, see  example  below).
  644. Otherwise, (i.e. if  $d$  does not divide $n$, there is just one class of
  645. dihedral subgroups of order $d$.
  646.  
  647. |    gap> d12 := TomDihedral( 12 );
  648.     rec(
  649.       name := [ "1", "2", "D_{2}a", "D_{2}b", "3", "D_{4}", "6", 
  650.           "D_{6}a", "D_{6}b", "D_{12}" ],
  651.       subs := [ [ 1 ], [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 1, 5 ], 
  652.           [ 1, 2, 3, 4, 6 ], [ 1, 2, 5, 7 ], [ 1, 3, 5, 8 ], 
  653.           [ 1, 4, 5, 9 ], [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ] ],
  654.       marks := [ [ 12 ], [ 6, 6 ], [ 6, 2 ], [ 6, 2 ], [ 4, 4 ], 
  655.           [ 3, 3, 1, 1, 1 ], [ 2, 2, 2, 2 ], [ 2, 2, 2, 2 ], 
  656.           [ 2, 2, 2, 2 ], [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ] ] )
  657.     gap> DisplayTom( d12 );
  658.      1:  12
  659.      2:   6 6
  660.      3:   6 . 2
  661.      4:   6 . . 2
  662.      5:   4 . . . 4
  663.      6:   3 3 1 1 . 1
  664.      7:   2 2 . . 2 . 2
  665.      8:   2 . 2 . 2 . . 2
  666.      9:   2 . . 2 2 . . . 2
  667.     10:   1 1 1 1 1 1 1 1 1 1 |
  668.  
  669. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  670. \Section{TomFrobenius}
  671.  
  672. 'TomFrobenius( <p>, <q> )'
  673.  
  674. 'TomFrobenius' computes the table of marks of a Frobenius  group of order
  675. $p q$, where $p$ is a prime and $q$ divides $p-1$.
  676.  
  677. |    gap> f20 := TomFrobenius( 5, 4 );
  678.     rec(
  679.       name := [ "1", "2", "4", "5:1", "5:2", "5:4" ],
  680.       subs := [ [ 1 ], [ 1, 2 ], [ 1, 2, 3 ], [ 1, 4 ], [ 1, 2, 4, 5 ], 
  681.           [ 1, 2, 3, 4, 5, 6 ] ],
  682.       marks :=
  683.        [ [ 20 ], [ 10, 2 ], [ 5, 1, 1 ], [ 4, 4 ], [ 2, 2, 2, 2 ],
  684.           [ 1, 1, 1, 1, 1, 1 ] ] )
  685.     gap> DisplayTom( f20 );
  686.     1:  20
  687.     2:  10 2
  688.     3:   5 1 1
  689.     4:   4 . . 4
  690.     5:   2 2 . 2 2
  691.     6:   1 1 1 1 1 1 |
  692.  
  693. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  694. %%
  695. %E  Emacs . . . . . . . . . . . . . . . . . . . . . . . local emacs variables
  696. %%
  697. %%  Local Variables:
  698. %%  mode:               outline
  699. %%  outline-regexp:     "\\\\Chapter\\|\\\\Section"
  700. %%  fill-column:        73
  701. %%  eval:               (hide-body)
  702. %%  End:
  703. %%
  704.  
  705.