home *** CD-ROM | disk | FTP | other *** search
/ Math Solutions 1995 October / Math_Solutions_CD-ROM_Walnut_Creek_October_1995.iso / pc / mac / discrete / lib / tom.g < prev    next >
Encoding:
Text File  |  1993-05-05  |  35.9 KB  |  1,384 lines
  1. #############################################################################
  2. ##
  3. #A  tom.g                       GAP library                   Goetz Pfeiffer.
  4. ##
  5. #A  @(#)$Id: tom.g,v 3.7 1993/01/20 15:40:06 goetz Rel $
  6. ##
  7. #Y  Copyright 1991-1992,  Lehrstuhl D fuer Mathematik,  RWTH Aachen,  Germany
  8. ##
  9. ##  This file  contains  the  functions   dealing   with   Tables Of  Marks.
  10. ##
  11. #H  $Log: tom.g,v $
  12. #H  Revision 3.7  1993/01/20  15:40:06  goetz
  13. #H  renamed 'DecomposeLine' and 'TestLine', adjusted layout.
  14. #H
  15. #H  Revision 3.6  1993/01/19  13:05:28  goetz
  16. #H  added 'WeightsTom', extended 'DisplayTom'.
  17. #H
  18. #H  Revision 3.5  1993/01/18  17:19:05  goetz
  19. #H  reorganized and renamed 'Tom' to 'TableOfMarks', added 'MatrixTom',
  20. #H  and renamed 'TomTransformed' to 'TomMatrix'.
  21. #H
  22. #H  Revision 3.4  1992/11/14  17:34:41  goetz
  23. #H  added 'Tom', made 'NrSubs' independant of the order in field 'subs'.
  24. #H
  25. #H  Revision 3.3  1992/11/11  11:27:21  goetz
  26. #H  added essential change of flag 'test' in 'TestLine'.
  27. #H
  28. #H  Revision 3.2  1992/11/11  11:16:52  goetz
  29. #H  renamed 'DecomposeLine' to 'DecomposedLine'.
  30. #H
  31. #H  Revision 3.1  1992/11/10  19:30:13  goetz
  32. #H  added header for 'ClassTypesTom'.
  33. #H
  34. #H  Revision 3.0  1992/11/10  18:59:36  goetz
  35. #H  Initial Revision.
  36. #H
  37. ##
  38. ##  The table  of marks of  a finite group $G$  is  a  matrix whose rows  and
  39. ##  columns are labelled by  the conjugacy classes of subgroups  of  $G$  and
  40. ##  where for  two subgroups $A$ and $B$ the $(A, B)$--entry is the number of
  41. ##  fixed points of $B$ in the transitive action of  $G$ on the cosets of $A$
  42. ##  in   $G$.   So   the  table   of  marks  characterizes   all  permutation
  43. ##  representations of $G$.
  44. ##
  45. ##  Moreover  the table of marks gives a compact description  of the subgroup
  46. ##  lattice of $G$,  since from the numbers  of  fixed points the numbers  of
  47. ##  conjugates of a subgroup $B$ contained in a subgroup $A$ can be derived.
  48. ##
  49. ##  This package  provides functions that derive information about  the group
  50. ##  from the table of marks  and some functions for the generic  construction
  51. ##  of a table of marks.
  52.  
  53. #############################################################################
  54. ##
  55. #F  InfoTom1  . . . . . . . . . . . . . . . . . . . . .  package information.
  56. #F  InfoTom2  . . . . . . . . . . . . . . . . . . . . . .  debug information.
  57. ##
  58. if not IsBound(InfoTom1) then InfoTom1:= Ignore; fi;
  59. if not IsBound(InfoTom2) then InfoTom2:= Ignore; fi;
  60.  
  61.  
  62. #############################################################################
  63. ##
  64. #F  IsTom( <obj> )  . . . . . . . . . . . . . . . . . . . . . . . type check.
  65. ## 
  66. ##  A Table of Marks is a record with at least a component 'subs'.
  67. ##
  68. IsTom := function(obj)
  69.    return IsRec(obj) and IsBound(obj.subs);
  70. end;
  71.  
  72.  
  73. #############################################################################
  74. ##
  75. #F  TableOfMarks( <str> | <grp> ) . . . . . . . . .  return a table of marks.
  76. ##
  77. ##  In the first  form  'Tom' tries to recover a table of marks with the name
  78. ##  <str>  from the library.  In  the second  form  it  will check  the group
  79. ##  <grp>, this may take a while if  the group  is  big.
  80. ##
  81. TableOfMarks := function( obj )
  82.  
  83.    local tom;
  84.  
  85.    if IsString(obj) then
  86.       tom:= TomLibrary(obj);      
  87.  
  88.    elif IsGroup(obj) then
  89.       if IsBound( obj.tableOfMarks ) then
  90.          tom:= obj.tableOfMarks;
  91.       elif IsBound(obj.operations) and 
  92.            IsBound(obj.operations.TableOfMarks) then
  93.          tom:= obj.operations.TableOfMarks(obj, "compressed");
  94.          tom:= rec(subs:= tom[1], marks:= tom[2]);
  95.          obj.tableOfMarks:= tom;
  96.       else
  97.          Error( "sorry, can't compute table of marks for given group" );
  98.       fi;
  99.  
  100.    else
  101.       Error("don't know how to construct the table of marks of <obj>");
  102.    fi;
  103.  
  104.    return tom;
  105.  
  106. end;
  107.  
  108. #############################################################################
  109. ##
  110. #F  Marks( <tom> )  . . . . . . . . . . . . . . . . . . . . . . .  the marks.
  111. ##
  112. ##  'Marks' returns the list of lists of marks  of the table of  marks <tom>.
  113. ##  If  these are not yet stored in the  component 'marks' of <tom> then they
  114. ##  will be computed and assigned to the component 'marks'.
  115. ##
  116. Marks := function(tom)
  117.  
  118.    local i, j, ll, nrSubs, subs, marks, ord;
  119.  
  120.    if IsBound(tom.marks) then
  121.       return tom.marks;
  122.    fi;
  123.  
  124.    ll:= Length(tom.order);
  125.    ord:= tom.order[ll];
  126.    subs:= tom.subs;
  127.    nrSubs:= tom.nrSubs;
  128.    marks:= [[ord]];
  129.    for i in [2..ll] do
  130.       marks[i]:= [ord / tom.order[i]];
  131.       for j in [2..Length(subs[i])] do
  132.          marks[i][j]:= nrSubs[i][j] * marks[i][1] / tom.length[subs[i][j]];
  133.          if not IsInt(marks[i][j]) or marks[i][j] < 0 then
  134.             Print("#W  orbit length ", i, ", ", j, ": ", marks[i][j], ".\n");
  135.          fi;
  136.       od;
  137.    od;
  138.  
  139.    tom.marks:= marks;
  140.    return marks;
  141.  
  142. end;
  143.  
  144.  
  145. #############################################################################
  146. ##
  147. #F  NrSubs( <tom> ) . . . . . . . . . . . . . . . . . . numbers of subgroups.
  148. ##
  149. ##  'NrSubs' also has to compute the orders and lengths from the marks.
  150. ##
  151. ##  'NrSubs' returns the list of lists of numbers  of subgroups of the  table
  152. ##  of marks <tom>.  If these are not yet stored in the component 'nrSubs' of
  153. ##  <tom> then they will be computed and assigned to the component 'nrSubs'.
  154. ##
  155. NrSubs := function(tom)
  156.  
  157.    local i, j, nrSubs, subs, marks, order, length, index;
  158.  
  159.    if IsBound(tom.nrSubs) then
  160.       return tom.nrSubs;
  161.    fi;
  162.  
  163.    order:= [];
  164.    length:= [];
  165.    nrSubs:= []; 
  166.    subs:= tom.subs;
  167.    marks:= tom.marks;
  168.    for i in [1..Length(subs)] do
  169.       index:= marks[i][Position(subs[i], 1)];
  170.       order[i]:= marks[1][1] / index;
  171.       length[i]:= index / marks[i][Position(subs[i], i)];
  172.       nrSubs[i]:= [];
  173.       for j in [1..Length(subs[i])] do
  174.          nrSubs[i][j]:= marks[i][j] * length[subs[i][j]] / index;
  175.          if not IsInt(nrSubs[i][j]) or nrSubs[i][j] < 0 then
  176.             Print("#W  orbit length ",i, ", ",j, ": ", nrSubs[i][j], ".\n");
  177.          fi;
  178.       od;
  179.    od;
  180.  
  181.    tom.order:= order;
  182.    tom.length:= length;
  183.    tom.nrSubs:= nrSubs;
  184.    return nrSubs;
  185.  
  186. end;
  187.  
  188.  
  189. #############################################################################
  190. ##
  191. #F  WeightsTom( <tom> ) . . . . . . . . . . . . . . . . . . . . . .  weights.
  192. ##
  193. WeightsTom := function(tom)
  194.  
  195.    local i, wgt, subs, marks;
  196.  
  197.    marks:= Marks(tom);
  198.    subs:= tom.subs;
  199.  
  200.    wgt:= [];
  201.    for i in [1..Length(subs)] do
  202.       wgt[i]:= marks[i][Position(subs[i], i)];
  203.    od;
  204.  
  205.    return wgt;
  206.  
  207. end;
  208.  
  209.  
  210. #############################################################################
  211. ##
  212. #F  TomMat( <mat> ) . . . . .  convert matrix into compressed table of marks.
  213. ##
  214. TomMat := function(mat)
  215.  
  216.    local i, j, subs, marks, normalizer, tom;
  217.  
  218.    subs:= []; marks:= [];
  219.  
  220.    for i in [1..Length(mat)] do
  221.       subs[i]:= []; 
  222.       marks[i]:= [];
  223.       for j in [1..i] do
  224.      if mat[i][j] > 0 then
  225.         Add(subs[i], j);
  226.         Add(marks[i], mat[i][j]);
  227.      fi;
  228.       od;
  229.    od;
  230.  
  231.    tom:=  rec(subs:= subs, marks:= marks);
  232.  
  233.    return tom;
  234.  
  235. end;
  236.  
  237.  
  238. #############################################################################
  239. ##
  240. #F  MatTom( <tom> ) . . . . .  convert compressed table of marks into matrix.
  241. ##
  242. MatTom := function(tom)
  243.  
  244.    local i, j, subs, marks, ll, res;
  245.  
  246.    marks:= Marks(tom);
  247.    subs:= tom.subs;
  248.    ll:= [1..Length(subs)];
  249.  
  250.    res:= [];
  251.    for i in ll do
  252.       res[i]:= 0 * ll;
  253.       for j in [1..Length(subs[i])] do
  254.          res[i][subs[i][j]]:= marks[i][j];
  255.       od;
  256.    od;
  257.  
  258.    return res;
  259.  
  260. end;
  261.  
  262.  
  263. #############################################################################
  264. ##
  265. #F  DecomposedFixedPointVector( <tom>, <fix> )  . . . . . .  decompose marks.
  266. ##
  267. ##  'DecomposedFixedPointVector' takes  a  fix  of fixed  point numbers  and
  268. ##  returns the decomposition into rows of the table of marks.
  269. ##
  270. DecomposedFixedPointVector := function(tom, fix)
  271.  
  272.    local i, j, dec, marks, subs, working, oo;
  273.  
  274.    marks:= Marks(tom);
  275.    subs:= tom.subs;
  276.    oo:= marks[1][1];
  277.  
  278.    #  just for its side effects.
  279.    NrSubs(tom);
  280.  
  281.    dec:= [];
  282.    working:= true;
  283.    i:= Length(fix);
  284.    while working do
  285.       while i>0 and fix[i] = 0 do
  286.          i:= i-1;
  287.       od;
  288.       if i = 0 then
  289.           working:= false;
  290.       else
  291.          dec[i]:= fix[i] * tom.length[i] * tom.order[i] / oo;
  292.          for j in [1..Length(subs[i])] do
  293.             fix[subs[i][j]]:= fix[subs[i][j]] - dec[i] * marks[i][j];
  294.          od; 
  295.       fi;
  296.    od;
  297.  
  298.    return dec;
  299.  
  300. end;
  301.  
  302.  
  303. #############################################################################
  304. ##
  305. #F  TestTom( <tom> )  . . . . . . . . . consistency check for table of marks.
  306. ##
  307. TestRow := function(tom, n)
  308.  
  309.    local i, j, k, a, b, dec, test, marks, subs;
  310.   
  311.    test:= true;
  312.    marks:= Marks(tom);
  313.    subs:= tom.subs;
  314.    a:= []; 
  315.    for i in [1..Length(subs[n])] do
  316.       a[subs[n][i]]:= marks[n][i];
  317.    od;
  318.    for i in Reversed([1..n]) do
  319.       b:= [];
  320.       for j in [1..Length(subs[i])] do
  321.          k:= subs[i][j];
  322.          if IsBound(a[k]) then
  323.             b[k]:= a[k]*marks[i][j];
  324.          fi;
  325.       od;
  326.       for j in [1..Length(b)] do
  327.          if not IsBound(b[j]) then
  328.             b[j]:= 0;
  329.          fi;
  330.       od;
  331.       dec:= DecomposedFixedPointVector(tom, b);
  332.       if ForAny(Set(dec), x-> not IsInt(x) or (x < 0)) then
  333.          InfoTom2("\n#W ", n, ".", i, " = ", dec, "\n");
  334.          test:= false;
  335.       fi;
  336.    od;
  337.  
  338.    return test;
  339.  
  340. end;
  341.  
  342. TestTom := function(tom)
  343.  
  344.    local i, test;
  345.  
  346.    test:= true;
  347.  
  348.    InfoTom2("#I  ");
  349.    for i in [1..Length(tom.subs)] do
  350.       InfoTom2(i, " \c");
  351.       if not TestRow(tom, i) then
  352.          test:= false;
  353.       fi;
  354.    od;
  355.    InfoTom2(" \n");
  356.  
  357.    return test;
  358.  
  359. end;
  360.  
  361.  
  362. #############################################################################
  363. ##
  364. #F  DisplayTom( <tom> [, <arec> ] ) . . . . . . . . . display table of marks.
  365. ##
  366. DisplayTom := function(arg)
  367.  
  368.    local i, j, k, l, pr1, ll, lk, von, bis, pos, llength, pr, vals, subs,
  369.          arec, tom, classes, lc, ci, wt;
  370.  
  371.    #  scan arg.
  372.    if Length(arg) = 1 and  IsTom(arg[1]) then
  373.       tom:= arg[1];
  374.       arec:= rec();
  375.    elif Length(arg) = 2 and IsTom(arg[1]) and IsRec(arg[2]) then
  376.       tom:= arg[1];
  377.       arec:= arg[2];
  378.    else
  379.       Error("usage: 'DisplayTom( <tom> [, <arec>] )'");
  380.    fi;
  381.       
  382.    #  default values.
  383.    subs:= tom.subs;
  384.    ll:= Length(subs);
  385.    classes:= [1..ll];
  386.    vals:= Marks(tom);
  387.  
  388.    #  adjust parameters.
  389.    if IsBound(arec.classes) and IsList(arec.classes) then
  390.       classes:= arec.classes;
  391.    fi;
  392.    if IsBound(arec.form) then
  393.       if arec.form = "supergroups" then
  394.          vals:= ShallowCopy(vals);
  395.          wt:= WeightsTom(tom);
  396.          for i in [1..ll] do
  397.             vals[i]:= vals[i]/wt[i];
  398.          od;
  399.       elif arec.form = "subgroups" then
  400.          vals:= NrSubs(tom);
  401.       fi;
  402.    fi;
  403.  
  404.    llength:= SizeScreen()[1];
  405.    von:= 1; 
  406.    pr1:= LogInt(ll, 10);
  407.  
  408.    #  determine column width.
  409.    pr:= List([1..ll], x->0);
  410.    for i in [1..ll] do
  411.       for j in [1..Length(subs[i])] do
  412.          pr[subs[i][j]]:= Maximum(pr[subs[i][j]], LogInt(vals[i][j], 10));
  413.       od;
  414.    od;
  415.  
  416.    lc:= Length(classes);
  417.    while von <= lc do
  418.       bis:= von;
  419.  
  420.       #  how many columns on this page?
  421.       lk:= pr1 + 5 + pr[classes[von]];
  422.       while bis < lc and lk+2+pr[classes[bis+1]] <= llength do
  423.          bis:= bis+1;
  424.          lk:= lk+2+pr[classes[bis]];
  425.       od;
  426.  
  427.       #  loop over rows.
  428.       for i in [von..lc] do
  429.          ci:= classes[i];
  430.          for k in [1 .. pr1-LogInt(ci, 10)] do
  431.             Print(" ");
  432.          od;
  433.          Print(ci, ": ");
  434.  
  435.          #  loop over columns.
  436.          for j in [von .. Minimum(i, bis)] do
  437.             pos:= Position(subs[ci], classes[j]);
  438.             if pos > 0 and pos <> false then
  439.                l:= LogInt(vals[ci][pos], 10)-1;
  440.             else
  441.                l:= -1;
  442.             fi;
  443.             for k in [1 .. pr[classes[j]] - l] do
  444.                Print(" ");
  445.             od;
  446.             if pos = false then
  447.                Print(".\c");
  448.             else
  449.                Print(vals[ci][pos], "\c");
  450.             fi;
  451.          od;
  452.          Print("\n");
  453.       od;
  454.  
  455.       von:= bis+1;
  456.       Print("\n");
  457.    od;
  458.  
  459. end;
  460.  
  461.  
  462.  
  463.  
  464. #############################################################################
  465. ##
  466. #F  NormalizerTom( <tom>, <u> ) . . . . . . . . . . . . determine normalizer.
  467. ##
  468. ##  'NormalizerTom' tries to find the normalizer  of a subgroup <u>.  It will
  469. ##  return the list of those subgroups which have the  right size and contain
  470. ##  the subgroup <u> and all subgroups which clearly contain  <u> as a normal
  471. ##  subgroup.  If the normalizer is uniquely  determined by these  conditions
  472. ##  then only its address is returned.  The list must never be empty.
  473. ##
  474. NormalizerTom := function(tom, u)
  475.  
  476.    local i, ll, res, nord, nn, subs, nrsubs;
  477.  
  478.    subs:= tom.subs;
  479.    nrsubs:= NrSubs(tom);
  480.    ll:= Length(subs);
  481.  
  482.    #  order of normalizer.
  483.    nord:= tom.order[ll] / tom.length[u];
  484.  
  485.    #  selfnormalizing.
  486.    if nord = tom.order[u] then
  487.       return u;
  488.    fi;
  489.    #  normal.
  490.    if tom.length[u] = 1 then
  491.       return ll;
  492.    fi;
  493.  
  494.    res:= [];
  495.    for i in [u+1..ll] do
  496.       if tom.order[i] = nord then
  497.          Add(res, i);
  498.       fi;
  499.    od;
  500.  
  501.    #  the normalizer must contain <u>.
  502.    res:= Filtered(res, x-> (u in subs[x]));
  503.  
  504.    if Length(res) = 1 then
  505.       return res[1];
  506.    fi;
  507.  
  508.    #  the normalizer must contain all subgroups which contain <u> 
  509.    #  as a normal subgroup, in particular those where <u> is of index 2
  510.    #  and those which contain only one conjugate of <u>.
  511.    nn:= [];
  512.    for i in [u+1..Minimum(res)-1] do
  513.       if u in subs[i] then
  514.          if tom.order[i] = 2 * tom.order[u] or
  515.             nrsubs[i][Position(subs[i], u)] = 1 then
  516.             Add(nn, i);
  517.          fi;
  518.       fi;
  519.    od;
  520.  
  521.    res:= Filtered(res, x-> IsSubset(subs[x], nn));
  522.  
  523.    if Length(res) = 1 then
  524.       return res[1];
  525.    fi;
  526.    return res;
  527.  
  528. end;
  529.  
  530.  
  531. #############################################################################
  532. ##
  533. #F  IntersectionsTom( <tom>, <a>, <b> ) . . . . . intersections of subgroups.
  534. ##
  535. ##  The intersections of two conjugacy classes of subgroups are determined by
  536. ##  the decomposition of the tensor product of their lines of marks.
  537. ##
  538. IntersectionsTom := function(tom, a, b)
  539.  
  540.    local i, j, k, h, line, dec, marks, subs;
  541.   
  542.    marks:= Marks(tom);
  543.    subs:= tom.subs;
  544.    h:= [];   line:= [];
  545.  
  546.    for i in [1..Length(subs[a])] do
  547.       h[subs[a][i]]:= marks[a][i];
  548.    od;
  549.    for j in [1..Length(subs[b])] do
  550.       k:= subs[b][j];
  551.       if IsBound(h[k]) then
  552.          line[k]:= h[k]*marks[b][j];
  553.       fi;
  554.    od;
  555.    for j in [1..Length(line)] do
  556.       if not IsBound(line[j]) then
  557.          line[j]:= 0;
  558.       fi;
  559.    od;
  560.    dec:= DecomposedFixedPointVector(tom, line);
  561.  
  562.    return(dec);
  563.  
  564. end;
  565.  
  566.  
  567. #############################################################################
  568. ##
  569. #F  IsCyclicTom( <tom>, <n> ) . . . . . . check whether a subgroup is cyclic.
  570. ##
  571. ##  A subgroup is cyclic if  and only if  the sum of the corresponding row of
  572. ##  the inverse table of marks is nonzero (see Kerber, S. 125).  Thus we only
  573. ##  have to decompose the corresponding idempotent.
  574. ##
  575. IsCyclicTom := function(tom, n)
  576.  
  577.    local i, mline, mdec, sum;
  578.  
  579.    mline:= 0 * [1..n];
  580.    mline[n]:= 1;
  581.  
  582.    #  decompose mline w.r.t. tom.
  583.    mdec:= DecomposedFixedPointVector(tom, mline);
  584.  
  585.    #  determine sum.
  586.    sum:= 0;
  587.    for i in mdec do
  588.       sum:= sum + i;
  589.    od;
  590.  
  591.    return sum <> 0;
  592.  
  593. end;
  594.  
  595.  
  596. #############################################################################
  597. ##
  598. #F  PermCharsTom( <tom>, <fus> )  . . . . . . . . . . permutation characters.
  599. ##
  600. ##  'PermCharsTom' reads the list of permutation characters from the table of
  601. ##  marks <tom>.  It therefore has to  know  the fusion map <fus> which sends
  602. ##  each conjugacy  class of elements  of the group to the conjugacy class of
  603. ##  subgroups that they generate.
  604. ##
  605. PermCharsTom := function(tom, fus)
  606.  
  607.    local pc, i, j, line, marks, subs;
  608.  
  609.    pc:= [];
  610.  
  611.    marks:= Marks(tom);
  612.    subs:= tom.subs;
  613.  
  614.    #  for every class of subgroups.
  615.    for i in [1..Length(subs)] do
  616.  
  617.       #  initialize permutation character.
  618.       line:= 0 * fus;
  619.  
  620.       #  extract the values.
  621.       for j in [1..Length(fus)] do 
  622.          if fus[j] in subs[i] then
  623.             line[j]:= marks[i][Position(subs[i], fus[j])];
  624.          fi;
  625.       od;
  626.       pc[i]:= line;
  627.    od;
  628.  
  629.    return pc;
  630.  
  631. end;
  632.  
  633.  
  634. #############################################################################
  635. ##
  636. #F  FusionCharTableTom( <tbl>, <tom> )  . . . . . . . . . . . element fusion.
  637. ##
  638. ##  'FusionCharTableTom' determines  the fusion of the  classes  of  elements
  639. ##  from  the  character table <tbl> into classes of cyclic subgroups  on the
  640. ##  table of marks <tom>.
  641. ##
  642. FusionCharTableTom := function(tbl, tom)
  643.  
  644.    local i, j, h, hh, fus, orders, cycs, ll, ind, p, pow, subs, marks;
  645.  
  646.    #  get orders of elements.
  647.    orders:= tbl.orders;
  648.  
  649.    #  determine cyclic subgroups.
  650.    marks:= Marks(tom);
  651.    subs:= tom.subs;
  652.    ll:= Length(subs);
  653.    cycs:= [];
  654.    for i in [1..ll] do
  655.       if tom.order[i] in orders and IsCyclicTom(tom, i) then
  656.          Add(cycs, i);
  657.       fi;
  658.    od;
  659.  
  660.    #  collect candidates for each class.
  661.    fus:= [];
  662.    for i in [1..Length(orders)] do
  663.       fus[i]:= [];
  664.       for j in cycs do
  665.          if orders[i] = tom.order[j] then
  666.             Add(fus[i], j);
  667.          fi;
  668.       od;
  669.       if Length(fus[i]) = 1 then
  670.          fus[i]:= fus[i][1];
  671.       fi;
  672.    od;
  673.  
  674.    #  maybe the map is already unique.
  675.    if IsVector(fus) then
  676.       return fus;
  677.    fi;
  678.  
  679.    #  check centralizers.
  680.    for i in [1..Length(fus)] do
  681.       if IsList(fus[i]) then
  682.          h:= Length(ClassOrbitCharTable(tbl, i)) 
  683.                                        * tbl.classes[i] / Phi(tbl.orders[i]);
  684.          hh:= [];
  685.          for j in fus[i] do
  686.             if tom.length[j] = h then
  687.                Add(hh, j);
  688.             fi;
  689.          od;
  690.          if Length(hh) = 1 then
  691.             fus[i]:= hh[1];
  692.          else
  693.             fus[i]:= hh;
  694.          fi;
  695.       fi;
  696.    od;
  697.  
  698.    #  maybe the map is already unique.
  699.    if IsVector(fus) then
  700.       return fus;
  701.    fi;
  702.  
  703.    #  check powermap against incidence.
  704.    for p in [2..Length(tbl.powermap)] do
  705.       if IsBound(tbl.powermap[p]) and IsPrime(p) then
  706.          pow:= [];
  707.          for i in [1..Length(cycs)] do
  708.             h:= tom.order[cycs[i]] / GcdInt(tom.order[cycs[i]], p);
  709.             hh:= []; 
  710.             for j in cycs do
  711.                if tom.order[j] = h then
  712.                   Add(hh, j);
  713.                fi;
  714.             od;
  715.             hh:= Intersection(hh, tom.subs[cycs[i]]);
  716.             if Length(hh) = 1 then
  717.                pow[cycs[i]]:= hh[1];
  718.             else
  719.                Error("No unique cyclic subgroup found");
  720.             fi;
  721.          od;
  722.  
  723.          CommutativeDiagram(fus, pow, tbl.powermap[p], fus);
  724.  
  725.          #  maybe the map is already unique.
  726.          if IsVector(fus) then
  727.             return fus;
  728.          fi;
  729.  
  730.       fi;
  731.    od;
  732.  
  733.    #  the fusion map must onto 'cycs'.
  734.    fus:= ContainedMaps(fus);
  735.    hh:= [];
  736.    for i in fus do
  737.       if Set(i) = cycs then
  738.          Add(hh, i);
  739.       fi;
  740.    od;
  741.    fus:= hh;
  742.  
  743.    #  check powermap against incidence.
  744.    for p in [2..Length(tbl.powermap)] do
  745.       if IsBound(tbl.powermap[p]) then
  746.          pow:= [];
  747.          for i in [1..Length(cycs)] do
  748.             h:= tom.order[cycs[i]] / GcdInt(tom.order[cycs[i]], p);
  749.             hh:= []; 
  750.             for j in cycs do
  751.                if tom.order[j] = h then
  752.                   Add(hh, j);
  753.                fi;
  754.             od;
  755.             hh:= Intersection(hh, tom.subs[cycs[i]]);
  756.             if Length(hh) = 1 then
  757.                pow[cycs[i]]:= hh[1];
  758.             else
  759.                Error("No unique cyclic subgroup found");
  760.             fi;
  761.          od;
  762.  
  763.          hh:= [];
  764.          for i in fus do
  765.             if CommutativeDiagram(i, pow, tbl.powermap[p], i) <> false then
  766.                Add(hh, i);
  767.             fi;
  768.          od;
  769.          fus:= hh;
  770.  
  771.          #  maybe the map is already unique.
  772.          if Length(fus) = 1 then
  773.             return fus[1];
  774.          fi;
  775.  
  776.       fi;
  777.    od;
  778.  
  779.    return fus;
  780.  
  781. end;
  782.  
  783.  
  784. #############################################################################
  785. ##
  786. #F  MoebiusTom( <tom> ) . . . . . . . . . . . . . . . . . . moebius function.
  787. ##
  788. ##  'MoebiusTom' computes the Moebius values both of the subgroup  lattice of
  789. ##  the group with tabel of marks <tom> and of the poset of conjugacy classes
  790. ##  of subgroups.  It returns a record where the component 'mu'  contains the
  791. ##  Moebius  values  of the subgroup lattice  and the component 'nu' contains
  792. ##  the Moebius values of the poset.  Moreover  according to a  conjecture of
  793. ##  Isaacs et  al. the values on the poset of conjugacy classes  are  derived
  794. ##  from  those  of  the subgroup  lattice.   These  theoreticla  values  are
  795. ##  returned  in the  component  'ex'.   For  that  computation  the  derived
  796. ##  subgroup must be known in  the component 'derivedSubgroup' of <tom>.  The
  797. ##  numbers of those subgroups where the  theoretical value does not coincide
  798. ##  with the actual value are returned in the component 'hyp'.
  799. ##
  800. MoebiusTom := function(tom)
  801.  
  802.    local i, j, mline, nline, ll, mdec, ndec, expec, done, no, comsec,
  803.          subs, nrsubs;
  804.  
  805.    nrsubs:= NrSubs(tom);
  806.    subs:= tom.subs;
  807.  
  808.    mline:= 0 * tom.length;
  809.    nline:= 0 * tom.length;
  810.  
  811.    ll:= Length(mline);
  812.    mline[ll]:= 1;
  813.    nline[ll]:= 1;
  814.  
  815.    # decompose mline with tom
  816.    # decompose nline w.r.t. incidence
  817.  
  818.    mdec:= [];
  819.    done:= false;
  820.    i:= Length(mline);
  821.    while not done do
  822.       while i>0 and mline[i] = 0 do
  823.          i:= i-1;
  824.       od;
  825.       if i = 0 then
  826.           done:= true;
  827.       else
  828.          mdec[i]:= mline[i];
  829.          for j in [1..Length(subs[i])] do
  830.             mline[subs[i][j]]:= mline[subs[i][j]] - mdec[i]*nrsubs[i][j];
  831.          od;
  832.          mdec[i]:= mdec[i] / tom.length[i];
  833.       fi;
  834.    od;
  835.  
  836.    ndec:= [];
  837.    done:= false;
  838.    i:= Length(nline);
  839.    while not done do
  840.       while i>0 and nline[i] = 0 do
  841.          i:= i-1;
  842.       od;
  843.       if i = 0 then
  844.           done:= true;
  845.       else
  846.          ndec[i]:= nline[i];
  847.          for j in subs[i] do
  848.             nline[j]:= nline[j] - ndec[i];
  849.          od;
  850.       fi;
  851.    od;
  852.  
  853.    #  determine intersections  with derived subgroup.
  854.    expec:= [];
  855.    if tom.derivedSubgroup <> ll then
  856.       comsec:= [];
  857.       for i in [1..ll] do
  858.  
  859.          #  there is only one intersection with normal subgroups.
  860.          comsec[i]:= Length(IntersectionsTom(tom, i, tom.derivedSubgroup));
  861.       od;
  862.       for i in [1..Length(ndec)] do
  863.          if IsBound(ndec[i]) then
  864.             no:= tom.normalizer[i];
  865.             
  866.             #  maybe the normalizer is not unique.
  867.             if IsList(no) then
  868.                no:= List(no, x-> tom.order[comsec[x]]);
  869.                no:= Set(no);
  870.                if Size(no) > 1 then
  871.                   InfoTom2("#W  Size of normalizer ", i, "not unique.\n");
  872.                else
  873.                   no:= no[1];
  874.                fi;
  875.             else
  876.                no:= tom.order[comsec[no]];
  877.             fi;
  878.             expec[i]:= ndec[i] * no / tom.order[comsec[i]];
  879.          fi;
  880.       od;
  881.  
  882.    #  perfect groups.
  883.    else
  884.       for i in [1..Length(ndec)] do
  885.          if IsBound(ndec[i]) then
  886.             expec[i]:= ndec[i] * tom.order[ll]/tom.order[i]/tom.length[i];
  887.          fi;
  888.       od;
  889.    fi;
  890.  
  891.    return rec(mu:= mdec, nu:= ndec, ex:= expec,
  892.               hyp:= Filtered([1..Length(expec)], function(x) 
  893.               if IsBound(expec[x]) then 
  894.                if IsBound(mdec[x]) then
  895.                  return expec[x] <> mdec[x];
  896.                else return true; fi;
  897.               else 
  898.                if IsBound(mdec[x]) then
  899.                  return true;
  900.                else
  901.                   return false; fi; fi; end));
  902.  
  903. end;
  904.  
  905.  
  906. #############################################################################
  907. ##
  908. #F  CyclicExtensionsTom( <tom>, <p> ) . . . . . . . . . .  cyclic extensions.
  909. ##
  910. ##  According to Dress two columns of a table of  marks mod <p> are equal  if
  911. ##  and  only  if  the  corresponding subgroups are  connected by a  chain of
  912. ##  normal  extensions  of  order  <p>.   'CyclicExtensionsTom'  returns  the
  913. ##  classes of this equivalence relation.
  914. ##
  915. ##  This  information is  not used by  'NormalizerTom' although it might give
  916. ##  additional retrictions in the search of normalizers.
  917. ##
  918. CyclicExtensionsTom := function(tom, p)
  919.  
  920.    local i, j, h, ll, done, classes, pos, val, marks, subs;
  921.  
  922.    #  check arguments.
  923.    if not IsPrime(p) then 
  924.       Error("<p> must be a prime.");
  925.    fi;
  926.  
  927.    marks:= Marks(tom);
  928.    subs:= tom.subs;
  929.    ll:= Length(subs);
  930.  
  931.    pos:= [];
  932.    val:= [];
  933.  
  934.    #  take marks mod <p> and transpose.
  935.    for i in [1..ll] do
  936.       pos[i]:= [];
  937.       val[i]:= [];
  938.       for j in [1..Length(subs[i])] do
  939.          h:= marks[i][j] mod p;
  940.          if h <> 0 then
  941.             Add(pos[subs[i][j]], i);
  942.             Add(val[subs[i][j]], h);
  943.          fi;
  944.       od;
  945.    od;
  946.  
  947.    #  form classes
  948.    classes:= [];
  949.    for i in [1..ll] do
  950.       j:= 1;
  951.       done:= false;
  952.       while not done and j < i do
  953.          if pos[i] = pos[j] and val[i] = val[j] then
  954.             Add(classes[j], i);
  955.             done:= true;
  956.          fi;
  957.          j:= j+1;
  958.       od;
  959.       if not done then
  960.          classes[i]:= [i];
  961.       fi;
  962.    od;
  963.  
  964.    return Set(classes);
  965.  
  966. end;
  967.  
  968.  
  969. #############################################################################
  970. ##
  971. #F  IdempotentsTom( <tom> ) . . . . . . . . . . . . . . . . . .  idempotents.
  972. ##
  973. ##  'IdempotentsTom' returns the list of idempotents of the integral Burnside
  974. ##  ring described  by the table of  marks  <tom>.   According to Dress these
  975. ##  idempotents correspond to the  classes of perfect subgroups and each such
  976. ##  idempotent is the  characteristic function  of  all those subgroups which
  977. ##  arise by cyclic extension from the corresponding perfect subgroup.
  978. ##
  979. IdempotentsTom := function(tom)
  980.  
  981.    local i, c, classes, p, ext, marks;
  982.  
  983.    marks:= Marks(tom);
  984.    
  985.    classes:= [1..Length(marks)];
  986.  
  987.    for p in Set(Factors(marks[1][1])) do
  988.       ext:= CyclicExtensionsTom(tom, p);
  989.       for c in ext do
  990.          for i in c do
  991.              classes[i]:= classes[c[1]];
  992.          od;
  993.       od;
  994.    od;
  995.  
  996.    for i in [1..Length(classes)] do
  997.       classes[i]:= classes[classes[i]];
  998.    od;
  999.  
  1000.    return classes;
  1001.  
  1002. end;
  1003.  
  1004.  
  1005. #############################################################################
  1006. ##
  1007. #F  ClassTypesTom( <tom> )  . . . . . . . . . . . . . . . types of subgroups.
  1008. ##
  1009. ##  'ClassTypesTom'   distinguishes  isomorphism  types  of  the  classes  of
  1010. ##  subgroups of the  table of marks <tom> as  far  as this is possible.  Two
  1011. ##  subgroups  are  clearly  not  isomorphic  if  they have different orders.
  1012. ##  Moreover isomorphic subgroups must contain  the  same number of subgroups
  1013. ##  of each type.
  1014. ##
  1015. ##  The types are represented by  numbers.   'ClassTypesTom' returns  a  list
  1016. ##  which contains for each class of subgroups its corresponding number.
  1017. ##
  1018. ClassTypesTom := function(tom)
  1019.  
  1020.    local i, j, done, nrsubs, subs, type, struct, nrtypes;
  1021.  
  1022.    nrsubs:= NrSubs(tom);
  1023.    subs:= tom.subs;
  1024.  
  1025.    type:= [];
  1026.    struct:= [];
  1027.    nrtypes:= 1;
  1028.  
  1029.    for i in [1..Length(subs)] do
  1030.  
  1031.       #  determine type
  1032.       struct[i]:= [];
  1033.       for j in [2..Length(subs[i])-1] do
  1034.          if IsBound(struct[i][type[subs[i][j]]]) then
  1035.             struct[i][type[subs[i][j]]]:= 
  1036.                             struct[i][type[subs[i][j]]] + nrsubs[i][j];
  1037.          else
  1038.             struct[i][type[subs[i][j]]]:= nrsubs[i][j];
  1039.          fi;
  1040.       od;
  1041.  
  1042.       for j in [1..i-1] do
  1043.          if tom.order[j] = tom.order[i] and struct[j] = struct[i] then
  1044.             type[i]:= type[j];
  1045.          fi;
  1046.       od;
  1047.  
  1048.       if not IsBound(type[i]) then
  1049.          type[i]:= nrtypes;
  1050.          nrtypes:= nrtypes+1;
  1051.       fi;
  1052.    od;
  1053.  
  1054.    return type;
  1055.  
  1056. end;
  1057.  
  1058.  
  1059. #############################################################################
  1060. ##
  1061. #F  ClassNamesTom( <tom> )  . . . . . . . . . . . . . . . . . .  class names.
  1062. ##
  1063. ##  'ClassNamesTom'  constructs generic names  for  the  conjugacy classes of
  1064. ##  subgroups of the table of marks <tom>.  Each name consists of three parts
  1065. ##  and  has the following form, (o)_{t}l, where o indicates the order of the
  1066. ##  subgroup, t is a number that distinguishes different types  of  subgroups
  1067. ##  of  the  same  order  and  l is a letter  which distinguishes classes  of
  1068. ##  subgroups  of the  same  type  and order.   The  type  of a  subgroup  is
  1069. ##  determined by the numbers its subgroups of other types.  This is slightly
  1070. ##  weaker than isomorphism.
  1071. ##
  1072. ##  The letter is omitted if  there  is only  one  class of subgroups of that
  1073. ##  order and type and the type is omitted if there is only one class of that
  1074. ##  order.  Moreover the braces  {}  around the type are  omitted if the type
  1075. ##  number has  only  one  digit.  Cyclic subgroups will have  no parenthesis
  1076. ##  around the order and no type number.
  1077. ##
  1078. ClassNamesTom := function(tom)
  1079.  
  1080.    local i, c, classes, type, name, count, ord, alp, la;
  1081.  
  1082.    type:= ClassTypesTom(tom);
  1083.  
  1084.    #  form classes.
  1085.    classes:= List([1..Maximum(type)], x-> rec(elts:= []));
  1086.    for i in [1..Length(type)] do
  1087.       Add(classes[type[i]].elts, i);
  1088.    od;
  1089.  
  1090.    #  determine type.
  1091.    count:= rec();
  1092.    for i in [1..Length(classes)] do
  1093.       ord:= String(tom.order[classes[i].elts[1]]);
  1094.       if IsBound(count.(ord)) then
  1095.          count.(ord).nr:= count.(ord).nr + 1;
  1096.          if count.(ord).nr < 10 then
  1097.             classes[i].type:= 
  1098.                ConcatenationString("_", String(count.(ord).nr));
  1099.          else
  1100.             classes[i].type:= 
  1101.            ConcatenationString("_{", String(count.(ord).nr), "}");
  1102.          fi;
  1103.       else
  1104.          count.(ord):= rec(first:= classes[i], nr:= 1);
  1105.          classes[i].type:= "_1";
  1106.       fi;
  1107.  
  1108.       #  cyclic?
  1109.       if Set(tom.nrSubs[classes[i].elts[1]]) = [1] 
  1110.             and IsCyclicTom(tom, classes[i].elts[1]) then
  1111.          classes[i].order:= ord;
  1112.          classes[i].type:= "";
  1113.       else
  1114.          classes[i].order:= ConcatenationString("(", ord, ")");
  1115.       fi;
  1116.  
  1117.    od;
  1118.  
  1119.    #  omit unique types.
  1120.    for i in RecFields(count) do
  1121.       if count.(i).nr = 1 then
  1122.          count.(i).first.type:= "";
  1123.       fi;
  1124.    od;
  1125.  
  1126.    #  construct names.
  1127.    name:= [];
  1128.    alp:= ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", 
  1129.             "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"];
  1130.    la:= Length(alp);
  1131.    for c in classes do
  1132.       if Length(c.elts) = 1 then
  1133.          name[c.elts[1]]:= ConcatenationString(c.order, c.type);
  1134.       else
  1135.          for i in [1..Length(c.elts)] do
  1136.             if i <= la then
  1137.                name[c.elts[i]]:= ConcatenationString(c.order,c.type,alp[i]);
  1138.             elif i <= la * (la+1) then
  1139.                name[c.elts[i]]:= ConcatenationString(c.order, c.type,
  1140.                        alp[QuoInt(i-1, la)], alp[i mod la]);
  1141.             else
  1142.                Error("did not expect more than ", la * (la+1), 
  1143.                      "classes of the same type");
  1144.             fi;
  1145.          od;
  1146.       fi;
  1147.    od;
  1148.  
  1149.    return name;
  1150.  
  1151. end;
  1152.  
  1153.  
  1154. #############################################################################
  1155. ##
  1156. #F  TomCyclic( <n> )  . . . . . .  The Table of Marks of Cyclic groups $C_n$.
  1157. ##
  1158. ##  'TomCyclic' constructs the table of  marks of the  cyclic group of  order
  1159. ##  <n>.
  1160. ##
  1161. TomCyclic := function(n)
  1162.  
  1163.    local i, j, divs, index, name, subs, marks;
  1164.  
  1165.    divs:= DivisorsInt(n);
  1166.  
  1167.    name:= [];
  1168.    subs:= [];
  1169.    marks:= [];
  1170.  
  1171.    for i in [1..Length(divs)] do
  1172.       name[i]:= String(divs[i]);
  1173.       subs[i]:= [];
  1174.       marks[i]:= [];
  1175.       index:= n / divs[i];
  1176.       for j in [1..i] do
  1177.          if divs[i] mod divs[j] = 0 then
  1178.             Add(subs[i], j);
  1179.             Add(marks[i], index);
  1180.          fi;
  1181.       od;
  1182.    od;
  1183.  
  1184.    return rec(name:= name, subs:= subs, marks:= marks);
  1185.  
  1186. end;
  1187.  
  1188.  
  1189. #############################################################################
  1190. ##
  1191. #F  TomDihedral( <m> )  . . . .  The Table of Marks of dihedral groups $D_m$.
  1192. ##
  1193. ##  'TomDihedral'  constructs the table  of  marks of the  dihedral  group of
  1194. ##  order <m>.
  1195. ##
  1196. TomDihedral := function(m)
  1197.  
  1198.    local i, j, divs, n, name, marks, subs, type, nrs, pt, d, construct, ord;
  1199.  
  1200.    n:= m/2;
  1201.  
  1202.    if not IsInt(n) then 
  1203.       Error(" <m> must not be odd ");
  1204.    fi;
  1205.  
  1206.    divs:= DivisorsInt(m);
  1207.  
  1208.    construct:= [[
  1209.  
  1210.       function(i, j)
  1211.          if divs[i] mod divs[j] = 0 then
  1212.             Add(subs[nrs[i]], nrs[j]);
  1213.             Add(marks[nrs[i]], m/divs[i]);
  1214.          fi;
  1215.       end,
  1216.    
  1217.       Ignore,
  1218.    
  1219.       function(i, j)
  1220.          if divs[i] mod divs[j] = 0 then
  1221.             Add(subs[nrs[i]], nrs[j]);
  1222.             Add(marks[nrs[i]], m/divs[i]);
  1223.          fi;
  1224.       end], [
  1225.    
  1226.       function(i, j)
  1227.          if divs[i] mod divs[j] = 0 and divs[i] > divs[j] then
  1228.             Add(subs[nrs[i]], nrs[j]);
  1229.             Add(marks[nrs[i]], m/divs[i]);
  1230.          fi;
  1231.       end,
  1232.    
  1233.       function(i, j)
  1234.          if divs[i] mod divs[j] = 0 then
  1235.             Add(subs[nrs[i]], nrs[j]);
  1236.             Add(marks[nrs[i]], 1);
  1237.          fi;
  1238.       end,
  1239.    
  1240.       function(i, j)
  1241.          if divs[i] mod divs[j] = 0 then
  1242.             Append(subs[nrs[i]], [nrs[j]..nrs[j]+2]);
  1243.             Append(marks[nrs[i]], [m/divs[i], 1, 1]);
  1244.          fi;
  1245.       end], [
  1246.    
  1247.       function(i, j)
  1248.          if divs[i] mod (2*divs[j]) = 0 then
  1249.             Add(subs[nrs[i]], nrs[j]);
  1250.             Add(subs[nrs[i]+1], nrs[j]);
  1251.             Add(subs[nrs[i]+2], nrs[j]);
  1252.             Add(marks[nrs[i]], m/divs[i]);
  1253.             Add(marks[nrs[i]+1], m/divs[i]);
  1254.             Add(marks[nrs[i]+2], m/divs[i]);
  1255.          fi;
  1256.       end,
  1257.    
  1258.       Ignore,
  1259.    
  1260.       function(i, j)
  1261.          if divs[i] mod (2*divs[j]) = 0 then
  1262.             Add(subs[nrs[i]], nrs[j]);
  1263.             Append(subs[nrs[i]+1], [nrs[j], nrs[j]+1]);
  1264.             Append(subs[nrs[i]+2], [nrs[j], nrs[j]+2]);
  1265.             Add(marks[nrs[i]], m/divs[i]);
  1266.             Append(marks[nrs[i]+1], [m/divs[i], 2]);
  1267.             Append(marks[nrs[i]+2], [m/divs[i], 2]);
  1268.          elif divs[i] mod divs[j] = 0 then
  1269.             Add(subs[nrs[i]], nrs[j]);
  1270.             Add(subs[nrs[i]+1], nrs[j]+1);
  1271.             Add(subs[nrs[i]+2], nrs[j]+2);
  1272.             Add(marks[nrs[i]], m/divs[i]);
  1273.             Add(marks[nrs[i]+1], 2);
  1274.             Add(marks[nrs[i]+2], 2);
  1275.          fi;
  1276.       end]];
  1277.  
  1278.    marks:= [];
  1279.    subs:= [];
  1280.    name:= [];
  1281.  
  1282.    type:= [];
  1283.    nrs:= [];  pt:= 1;
  1284.    for d in divs do
  1285.       Add(nrs, pt);  pt:= pt+1;
  1286.       ord:= String(d);
  1287.       if n mod d = 0 then
  1288.          if d mod 2 = 0 then
  1289.             Add(type, 3);  pt:= pt+2;
  1290.             Add(name, ord);
  1291.             Add(name, ConcatenationString("D_{", ord, "}a"));
  1292.             Add(name, ConcatenationString("D_{", ord, "}b"));
  1293.          else
  1294.             Add(type, 1);
  1295.             Add(name, ord);
  1296.          fi;
  1297.       else
  1298.          Add(type, 2);
  1299.          Add(name, ConcatenationString("D_{", ord, "}"));
  1300.       fi;
  1301.    od;
  1302.  
  1303.    for i in [1..Length(divs)] do
  1304.       subs[nrs[i]]:= [];
  1305.       marks[nrs[i]]:= [];
  1306.       if type[i] = 3 then
  1307.          subs[nrs[i]+1]:= [];  subs[nrs[i]+2]:= [];
  1308.          marks[nrs[i]+1]:= [];  marks[nrs[i]+2]:= [];
  1309.       fi;
  1310.       for j in [1..i] do
  1311.          construct[type[i]][type[j]](i, j);
  1312.       od;
  1313.    od;
  1314.  
  1315.    return rec(name:= name, subs:= subs, marks:= marks);
  1316.  
  1317. end;
  1318.  
  1319.  
  1320. #############################################################################
  1321. ##
  1322. #F  TomFrobenius( <p>, <q> )  . . . . The Table of Marks of Frobenius Groups.
  1323. ##
  1324. ##  'TomFrobenius' computes  the table of marks  of a  Frobenius group $p:q$,
  1325. ##  where $p$ is a prime and $q$ divides $p-1$.
  1326. ##
  1327. TomFrobenius := function(p, q)
  1328.  
  1329.    local i, j, n, ind, subs, marks, name, divs;
  1330.  
  1331.    if not IsPrime(p) then 
  1332.       Error("not yet implemented"); 
  1333.    fi;
  1334.    if (p-1) mod q <> 0 then 
  1335.       Error("not frobenius"); 
  1336.    fi;
  1337.  
  1338.    name:= [];
  1339.    subs:= [];
  1340.    marks:= [];
  1341.    n:= p*q;
  1342.    divs:= DivisorsInt(n);
  1343.  
  1344.    for i in [1..Length(divs)] do
  1345.       ind:= n/divs[i];
  1346.       subs[i]:= [1];
  1347.       marks[i]:= [ind];
  1348.       if ind mod p = 0 then # d
  1349.          name[i]:= String(divs[i]);
  1350.          for j in [2..i] do
  1351.             if marks[j][1] mod ind = 0 then
  1352.                Add(subs[i], j);
  1353.                Add(marks[i], ind/p);
  1354.             fi;
  1355.          od;      
  1356.       else # p:d
  1357.          name[i]:= ConcatenationString(String(p), ":", String(divs[i]/p));
  1358.          for j in [2..i] do
  1359.             if marks[j][1] mod ind = 0 then
  1360.                Add(subs[i], j);
  1361.                Add(marks[i], ind);
  1362.             fi;
  1363.          od;
  1364.       fi;
  1365.    od;
  1366.  
  1367.    return rec(name:= name, subs:= subs, marks:= marks);
  1368.  
  1369. end;
  1370.  
  1371.  
  1372. #############################################################################
  1373. ##
  1374. #E  Emacs . . . . . . . . . . . . . . . . . . . . . . . local emacs variables
  1375. ##
  1376. ##  Local Variables:
  1377. ##  mode:               outline
  1378. ##  outline-regexp:     "#F\\|#V\\|#E\\|#R"
  1379. ##  fill-column:        77
  1380. ##  fill-prefix:        "##  "
  1381. ##  eval:               (hide-body)
  1382. ##  End:
  1383. ##
  1384.