home *** CD-ROM | disk | FTP | other *** search
/ Math Solutions 1995 October / Math_Solutions_CD-ROM_Walnut_Creek_October_1995.iso / pc / mac / discrete / lib / ctpermch.g < prev    next >
Encoding:
Text File  |  1993-05-05  |  72.3 KB  |  2,263 lines
  1. #############################################################################
  2. ##
  3. #A  ctpermch.g                  GAP library                     Thomas Breuer
  4. #A                                                           & Goetz Pfeiffer
  5. ##
  6. #A  @(#)$Id: ctpermch.g,v 3.21 1992/11/16 16:35:40 sam Rel $
  7. ##
  8. #Y  Copyright 1990-1992,  Lehrstuhl D fuer Mathematik,  RWTH Aachen,  Germany
  9. ##
  10. ##  This file contains those  functions  that are needed to compute and test
  11. ##  possible permutation characters.
  12. ##
  13. #N  TODO:
  14. #N  - 'IsPermChar( <tbl>, <pc> )'
  15. #N  - 'Constituent' und 'Maxdeg' - Optionen in 'PermComb'
  16. ##
  17. #H  $Log: ctpermch.g,v $
  18. #H  Revision 3.21  1992/11/16  16:35:40  sam
  19. #H  generalized 'PermCharInfo' for list of characters
  20. #H
  21. #H  Revision 3.20  1992/10/08  10:10:47  sam
  22. #H  added 'ATLAS' component in 'PermCharInfo'
  23. #H
  24. #H  Revision 3.19  1992/07/03  10:13:14  sam
  25. #H  added 'PermCharInfo'
  26. #H
  27. #H  Revision 3.18  1992/04/03  17:45:36  martin
  28. #H  changed the author line
  29. #H
  30. #H  Revision 3.17  1992/03/13  18:16:51  goetz
  31. #H  changed structure of 'PermChars'.
  32. #H
  33. #H  Revision 3.16  1991/12/20  10:15:42  sam
  34. #H  renamed 'Kernel' to 'KernelChar'
  35. #H
  36. #H  Revision 3.15  1991/12/09  14:49:48  goetz
  37. #H  changed some 'GcdInt's to 'Gcd'.
  38. #H
  39. #H  Revision 3.14  1991/12/04  13:42:44  sam
  40. #H  indented these damned functions !
  41. #H
  42. #H  Revision 3.13  1991/12/04  13:02:15  sam
  43. #H  indented ':=' in function definition
  44. #H
  45. #H  Revision 3.12  1991/11/08  17:48:18  sam
  46. #H  correction in 'Info' lines
  47. #H
  48. #H  Revision 3.11  1991/10/01  14:28:06  casper
  49. #H  changed 'Gcd' to 'GcdInt
  50. #H
  51. #H  Revision 3.10  1991/10/01  13:46:22  casper
  52. #H  changed 'E(3)' to '"infinity"'
  53. #H
  54. #H  Revision 3.9  1991/10/01  09:18:20  sam
  55. #H  changed 'VERBOSE' to 'InfoCharTable2'
  56. #H
  57. #H  Revision 3.8  1991/09/30  14:03:04  sam
  58. #H  changed 'Gcd' to 'GcdInt'
  59. #H
  60. #H  Revision 3.7  1991/09/26  07:31:46  sam
  61. #H  bug in 'PermCandidates' fixed
  62. #H
  63. #H  Revision 3.6  1991/09/06  07:29:47  sam
  64. #H  changed 'LcmList' to 'Lcm'
  65. #H
  66. #H  Revision 3.5  1991/09/05  15:49:09  sam
  67. #H  changed 'Transposed' to 'TransposedMat'
  68. #H
  69. #H  Revision 3.4  1991/09/05  15:39:50  sam
  70. #H  changed 'GcdList' to 'Gcd'
  71. #H
  72. #H  Revision 3.3  1991/09/05  15:28:59  sam
  73. #H  changed 'RankMatrix' to 'RankMat'
  74. #H
  75. #H  Revision 3.2  1991/09/05  14:52:04  sam
  76. #H  changed 'Quo' to 'QuoInt'
  77. #H
  78. #H  Revision 3.1  1991/09/03  13:22:22  goetz
  79. #H  changed 'reps' to 'orders'.
  80. #H
  81. #H  Revision 3.0  1991/09/03  13:15:27  goetz
  82. #H  Initial Revision.
  83. #H
  84. ##
  85.  
  86.  
  87. #############################################################################
  88. ##
  89. #F  InfoCharTable1( ... ) . . . info function for the character table package
  90. #F  InfoCharTable2( ... ) . . . info function for the character table package
  91. ##
  92.     if not IsBound( InfoCharTable1 )  then InfoCharTable1 := Ignore;  fi;
  93.     if not IsBound( InfoCharTable2 )  then InfoCharTable2 := Ignore;  fi;
  94.  
  95.  
  96. #############################################################################
  97. ##
  98. #F  SubClass( <tbl>, <char> ) . . . . . . . . . . . size of class in subgroup
  99. ##
  100. ##  Given a permutation character <char> of the group with character table
  101. ##  <tbl> 'SubClass' determines the sizes of the intersections of the
  102. ##  classes with the corresponding subgroup. Of course this has to be a
  103. ##  positive integer.
  104. ##
  105. SubClass  := function(tbl, char)
  106.  
  107.    local sc, i;
  108.  
  109.    sc:= [1];
  110.  
  111.    for i in [2..Length(char)] do
  112.       sc[i]:= (char[i] * tbl.classes[i]) / char[1];
  113.       if not IsInt(sc[i]) then
  114.         Print( "#E SubClass(): noninteger number of elements in class ",
  115.                i, "\n");
  116.       fi;
  117.    od;
  118.  
  119.    return(sc);
  120.  
  121. end;
  122.  
  123.  
  124. #############################################################################
  125. ##
  126. #F  TestPerm1( <tbl>, <char> ) . . . . . . . . . . . . . . . . test permchar
  127. ##
  128. ##  performs CAS test 1 and 2 for permutation characters
  129. ##
  130. TestPerm1 := function(tbl, char)
  131.    
  132.    local i, pm;
  133.  
  134.    # TEST 1:
  135.    for i in char do
  136.       if i < 0 then
  137.         return(1);
  138.       fi;
  139.    od;
  140.  
  141.    # TEST 2:
  142.    for pm in tbl.powermap do
  143.       for i in [2..Length(char)] do
  144.         if char[i] > char[pm[i]] then return(2); fi;
  145.       od;
  146.    od;
  147.  
  148.    return(0);
  149.  
  150. end;
  151.  
  152.  
  153. #############################################################################
  154. ##
  155. #F  TestPerm2( <tbl>, <char> ) . . . . . . . . . . . . test permchar
  156. ##
  157. ##  performs CAS test 3, 4, and 5 for permutation characters
  158. ##
  159. TestPerm2 := function(tbl, char)
  160.  
  161.    local i, j, nccl, subord, subclass, subfak, prime, sum;
  162.  
  163.    subord:= tbl.order / char[1];
  164.    if not IsInt(subord) then
  165.       InfoCharTable2("-\c");
  166.       return(1);
  167.    fi;
  168.    nccl:= Length(char);
  169.  
  170.    # TEST 3:
  171.    for i in [2..nccl] do
  172.       if char[i] <> 0 and subord mod tbl.orders[i] <> 0 then
  173.         InfoCharTable2("=\c");
  174.         return(3);
  175.       fi;
  176.    od;
  177.  
  178.    # TEST 4:
  179.    subclass:= [1];
  180.    for i in [2..nccl] do
  181.       subclass[i]:= (char[i] * tbl.classes[i]) / char[1];
  182.       if not IsInt(subclass[i]) then
  183.         InfoCharTable2("#\c");
  184.         return(4);
  185.       fi;
  186.    od;
  187.  
  188.    # TEST 5:
  189.    subfak:= Set(Factors(subord));
  190.    for prime in subfak do
  191.       if subord mod prime^2 <> 0 then
  192.         sum:= 0;
  193.         for j in [2..nccl] do
  194.           if tbl.orders[j] = prime then
  195.             sum:= sum + subclass[j];
  196.           fi;
  197.         od;
  198.         if (sum - prime + 1) mod (prime * (prime - 1)) <> 0 then
  199.           InfoCharTable2(":\c");
  200.           return(5);
  201.         fi;
  202.         if subord mod (sum / (prime - 1)) <> 0 then
  203.           InfoCharTable2(";\c");
  204.           return(5);
  205.         fi;
  206.       fi;
  207.    od;
  208.  
  209.    return(0);
  210.  
  211. end;
  212.  
  213.  
  214. #############################################################################
  215. ##
  216. #F  TestPerm3( <tbl>, <permch> ) . . . . . . . . . . . . . . . test permchar
  217. ##
  218. ##  'TestPerm3' performs CAS test 6
  219. ##
  220. TestPerm3 := function(tbl, permch)
  221.  
  222.    local i, j, nccl, fb, sc, corbs, lc, phii, pc;
  223.  
  224.    fb:= [];
  225.    lc:= [];
  226.    phii:= [];
  227.    nccl:= Length(tbl.orders);
  228.  
  229.    for i in [1..nccl] do
  230.       if not IsBound(lc[i]) then
  231.         corbs:= ClassOrbitCharTable(tbl, i);
  232.         lc[i]:= Length(corbs);
  233.         for j in corbs do
  234.           lc[j]:= lc[i];
  235.         od;
  236.         phii[i]:= Phi(tbl.orders[i]) / lc[i];
  237.       fi;
  238.    od;
  239.  
  240.    for pc in permch do
  241.       sc:= SubClass(tbl, pc);
  242.       for j in [2..nccl] do
  243.         if tbl.orders[j] > 2 and IsBound(phii[j]) then
  244.           if sc[j] mod phii[j] <> 0 then
  245.             AddSet(fb, pc);
  246.           fi;
  247.         fi;
  248.       od;
  249.    od;
  250.  
  251.    return(fb);
  252.  
  253. end;
  254.  
  255.  
  256. #############################################################################
  257. ##
  258. ##  Inequalities( <tbl> [, <option>] ) . .  a projected system of inequalites
  259. ##
  260. ##  There are two ways to organize the projection. The first is the straight
  261. ##  approach which takes the rationalized characters in their original order
  262. ##  and by this guarantees the character with the smallest degree to be
  263. ##  considered first. --> no option
  264. ##  The other way tries to keep the number of intermediate inequalities
  265. ##  small by eventually changing the order of characters. -->option "small"
  266. ##
  267. Inequalities := function(arg)
  268.  
  269.    local tbl, option, 
  270.          i, j, h, o, dim, nccl, ncha, c, X, dir, root, ineq, tuete, 
  271.          Conditor, Kombinat, other, mini, con, conO, conU,
  272.          proform, project;
  273.  
  274.    # scan arg
  275.    if Length(arg) = 1 and IsCharTable(arg[1]) then
  276.       tbl:= arg[1];
  277.       option:= "";
  278.    elif Length(arg) = 2 and IsCharTable(arg[1]) then
  279.       tbl:= arg[1];
  280.       option:= arg[2];
  281.    fi;
  282.  
  283.    # local functions
  284.    proform:= function(tuete, s, dir)
  285.       local i, lo, lu, conO, conU, komO, komU, res;
  286.  
  287.       conO:= []; conU:= [];
  288.       res:= 0;
  289.       for i in [1..Length(tuete)] do
  290.         if tuete[i][dir] < 0 then
  291.           Add(conO, Kombinat[i]);
  292.         elif tuete[i][dir] > 0 then
  293.           Add(conU, Kombinat[i]);
  294.         else
  295.           res:= res + 1;
  296.         fi;
  297.       od;
  298.  
  299.       lo:= Length(conO); lu:= Length(conU);
  300.  
  301.       if s = dim+1 then
  302.         return(res + lo * lu);
  303.       fi;
  304.  
  305.       for komO in conO do
  306.         if Length(komO) = 1 then
  307.           res:= res + lu;
  308.         else
  309.           for komU in conU do
  310.             if Length(Union(komO, komU)) <= dim+3 - s then
  311.               res:= res + 1;
  312.             fi;
  313.           od;
  314.         fi;
  315.       od;
  316.  
  317.       return(res);
  318.    end;
  319.  
  320.    project:= function(tuete, dir)
  321.       local i, j, k, l, C, sum, com, lo, lu, conO, conU, 
  322.             lineO, lineU, lc, kombi, res;
  323.  
  324.       InfoCharTable2("project(", dir, ")");
  325.  
  326.       conO:= []; conU:= [];
  327.       res:= []; kombi:= [];
  328.       for i in [1..Length(tuete)] do
  329.         if tuete[i][dir] < 0 then
  330.           Add(conO, rec(con:= tuete[i], kom:= Kombinat[i]));
  331.           Add(Conditor[dir], tuete[i]);
  332.         elif tuete[i][dir] > 0 then
  333.           Add(conU, rec(con:= tuete[i], kom:= Kombinat[i]));
  334.           Add(Conditor[dir], tuete[i]);
  335.         else
  336.           Add(res, tuete[i]); Add(kombi, Kombinat[i]);
  337.         fi;
  338.       od;
  339.  
  340.       lo:= Length(conO); lu:= Length(conU);
  341.  
  342.       InfoCharTable2(lo, " ", lu,"\n");
  343.  
  344.       for lineO in conO do
  345.         for lineU in conU do
  346.           com:= Union(lineO.kom, lineU.kom);
  347.           lc:= Length(com);
  348.           if lc <= dim+3 - dir then
  349.             sum:= lineU.con[dir] * lineO.con - lineO.con[dir] * lineU.con;
  350.             sum:= Gcd(sum)^-1 * sum;
  351.             if lc - Length(lineO.kom) = 1 or lc - Length(lineU.kom) = 1 then
  352.               Add(res, sum); Add(kombi, com);
  353.             else
  354.               C:= List(Sublist(ineq, com), x-> Sublist(x, [dir..dim+1]));
  355.               if RankMat(C) = lc-1 then
  356.                 Add(res, sum); Add(kombi, com);
  357.               fi;
  358.             fi;
  359.           fi;
  360.         od;
  361.       od;
  362.       Kombinat:= kombi;
  363.       return(res);
  364.    end;
  365.  
  366.    nccl:= Length(tbl.classes);
  367.    X:= RationalizedMat(tbl.irreducibles);
  368.  
  369.    c:= TransposedMat(X);
  370.  
  371.    # determine power conditions
  372.    # ie: for each class find a root and replace coloumn by difference.
  373.  
  374.    root:= ClassRootsCharTable(tbl);
  375.    ineq:= [];
  376.    other:= [];
  377.    for i in [2..nccl] do
  378.       if root[i] = [] then
  379.         AddSet(ineq, c[i]);
  380.         AddSet(other, c[i]);
  381.       else
  382.         AddSet(ineq, c[i] - c[root[i][1]]);
  383.         for j in root[i] do
  384.           AddSet(other, c[i] - c[j]);
  385.         od;
  386.       fi;
  387.    od;
  388.    ineq:= List(ineq, x->Gcd(x)^-1*x);
  389.    other:= List(other, x->Gcd(x)^-1*x);
  390.  
  391.    ncha:= Length(X);
  392.  
  393.    dim:= Length(ineq);
  394.    if dim <> Length(ineq[1])-1 then
  395.       Error("nonregular problem");
  396.    fi;
  397.  
  398.    Conditor:= List([1..dim+1], x->[]);
  399.    Kombinat:= List([1..dim+1], x->[x]);
  400.    tuete:= ineq;
  401.    
  402.    for i in Reversed([2..dim+1]) do
  403.       dir:= 0;
  404.  
  405.       if option = "small" then
  406.  
  407.          # find optimal direction
  408.          for j in [2..i] do
  409.            o:= proform(tuete, i, j);
  410.            if dir = 0 or o <= mini then
  411.              mini:= o; dir:= j;
  412.            fi;
  413.          od;
  414.  
  415.          # make it the current one
  416.          if dir <> i then
  417.            for j in [i..ncha] do
  418.              for con in Conditor[j] do
  419.                h:= con[dir]; con[dir]:= con[i]; con[i]:= h;
  420.              od;
  421.            od;
  422.            for con in tuete do
  423.              h:= con[dir]; con[dir]:= con[i]; con[i]:= h;
  424.            od;
  425.            for con in other do
  426.              h:= con[dir]; con[dir]:= con[i]; con[i]:= h;
  427.         od;
  428.  
  429.         h:= X[dir]; X[dir]:= X[i]; X[i]:= h;
  430.      fi;
  431.       fi;
  432.  
  433.       # perform projection
  434.       tuete:= project(tuete, i);
  435.  
  436.       # if regular, reinstall reference
  437.       if Length(tuete) = i-2 then
  438.      ineq:= tuete;
  439.      dim:= i-2;
  440.      Kombinat:= List([1..i-1], x->[x]);
  441.      InfoCharTable2("REGULAR !!!\n");
  442.       fi;
  443.  
  444.    od;
  445.  
  446.    # don't use too many inequalities
  447.    for i in [2..ncha] do
  448.     if Length(Conditor[i]) > 1 then
  449.       conO:= Filtered(Conditor[i], x->x[i] < 0);
  450.       conU:= Filtered(Conditor[i], x->x[i] > 0);
  451.       if Length(conO) > i then
  452.      conO:= Sublist(conO, [1..i]);
  453.       fi;
  454.       if Length(conU) > i then
  455.      conU:= Sublist(conU, [1..i]);
  456.       fi;
  457.       Conditor[i]:= Union(conO, conU);
  458.     fi;
  459.    od;
  460.  
  461.    # but don't forget original conditions
  462.    for con in other do
  463.       i:= ncha;
  464.       while con[i] = 0 do i:= i-1; od;
  465.       AddSet(Conditor[i], con);
  466.    od;
  467.  
  468.    return(rec(obj:= X, Conditor:= Conditor));
  469.  
  470. end;
  471.  
  472.  
  473. #############################################################################
  474. ##
  475. #F  Permut( <tbl>, <arec> )               2 Jul 91
  476. ##
  477. ##  determine possible permutation characters
  478. ##
  479. Permut := function(tbl, arec)
  480.  
  481.    local permel, degree,
  482.      a, amin, amax, c, ncha, len, i, j, k, l, permch, 
  483.      Conditor, comb, cond, X, divs, pm, minR, maxR,
  484.      d, sub, del, s, nccl, root, other, 
  485.      time1, time2, total, free, const, lowerBound, upperBound,
  486.      einfug, solveKnot, nextLevel, insertValue, suche;
  487.  
  488.    if Length(tbl.irreducibles) <> Length(tbl.orders) then
  489.       Error("<tbl> must be complete character table");
  490.    fi;
  491.       
  492.    if IsBound(arec.ineq) then
  493.       permel:= arec.ineq;
  494.    else 
  495.       permel:= Inequalities(tbl);
  496.    fi;
  497.  
  498.    if IsBound(arec.degree) then
  499.       degree:= arec.degree;
  500.    else
  501.       degree:= 0;
  502.    fi;
  503.  
  504.    # local functions
  505.    lowerBound:= function(cond, const, free, s)
  506.       local j, unten;
  507.  
  508.       unten:= -const;
  509.       for j in [2..s-1] do if free[j] then
  510.      if cond[j] < 0 then
  511.         unten:= unten - amin[j]*cond[j];
  512.      elif cond[j] > 0 then
  513.         unten:= unten - amax[j]*cond[j];
  514.      fi;
  515.       fi;od; 
  516.       if unten <= 0 then return(0);
  517.       else return(QuoInt(unten-1, cond[s])+1);
  518.       fi;
  519.    end;
  520.  
  521.    upperBound:= function(cond, const, free, s)
  522.       local j, oben;
  523.       oben:= const;
  524.       for j in [2..s-1] do if free[j] then
  525.      if cond[j] < 0 then
  526.         oben:= oben + amin[j]*cond[j];
  527.      elif cond[j] > 0 then
  528.         oben:= oben + amax[j]*cond[j];
  529.      fi;
  530.       fi;od; 
  531.       if oben < 0 then return(-1);
  532.       else return(QuoInt(oben, -cond[s]));
  533.       fi;
  534.    end;
  535.  
  536.    nextLevel:= function(const, free)
  537.       local h, i, j, p, c, con, cond, unten, oben, maxu, mino,
  538.         unique, first, mindeg, maxdeg;
  539.  
  540.       unique:= [];
  541.       for h in [2..ncha] do 
  542.      cond:= Conditor[h];
  543.      c:= const[h];
  544.        if free[h] then
  545.      # compute amin, amax
  546.      if not IsBound(first) then
  547.         first:= h;
  548.      fi;
  549.      maxu:= 0;
  550.      mino:= tbl.order;
  551.      for i in [1..Length(cond)] do
  552.         if cond[i][h] > 0 then
  553.            maxu:= Maximum(maxu, lowerBound(cond[i], const[h][i], free, h));
  554.         else
  555.            mino:= Minimum(mino, upperBound(cond[i], const[h][i], free, h));
  556.         fi;
  557.      od;
  558.  
  559.      amin[h]:= maxu;
  560.      amax[h]:= mino;
  561.      if mino < maxu then
  562.         return(h);
  563.      fi;
  564.  
  565.      if mino = maxu then AddSet(unique, h); fi;
  566.        else
  567.      if IsBound(first) then
  568.      # interpret inequalities for lower steps !
  569.         for i in [1..Length(cond)] do
  570.            con:= cond[i];
  571.            s:= h-1;
  572.            while s > 1  and (not free[s] or con[s] = 0) do
  573.             s:= s-1; od;
  574.            if s > 1 then
  575.            if con[s] > 0 then
  576.           unten:= lowerBound(con, c[i], free, s);
  577.           amin[s]:= Maximum(amin[s], unten);
  578.            else
  579.           oben:= upperBound(con, c[i], free, s);
  580.           amax[s]:= Minimum(amax[s], oben);
  581.            fi;
  582.            if amin[s] > amax[s] then return(s);
  583.            elif amin[s] = amax[s] then AddSet(unique, s); fi;
  584.            fi;
  585.         od;
  586.  
  587.      fi;
  588.        fi;
  589.       od;
  590.  
  591.       maxdeg:= 1;
  592.       mindeg:= 1;
  593.       for i in [2..ncha] do 
  594.      maxdeg:= maxdeg + amax[i] * X[i][1];
  595.      mindeg:= mindeg + amin[i] * X[i][1];
  596.       od;
  597.       if minR > maxdeg or maxR < mindeg then
  598.      return(0);
  599.       fi;
  600.  
  601.       if unique <> [] then return(unique);
  602.       else return(first); fi;
  603.  
  604.    end;
  605.  
  606.    insertValue:= function(const, s)
  607.       local i, j, c;
  608.  
  609.       const:= Copy(const);
  610.  
  611.       for i in [s..ncha] do
  612.      c:= const[i];
  613.      for j in [1..Length(c)] do
  614.         c[j]:= c[j] + a[s]*Conditor[i][j][s];
  615.      od;
  616.       od;
  617.  
  618.       return(const);
  619.    end;
  620.  
  621.    solveKnot:= function(const, free)
  622.       local i, p, s, char, fail;
  623.  
  624.       free:= Copy(free);
  625.       if Set(free) = [false] then
  626.      total:= total+1;
  627.      char:= X[1];
  628.      for j in [2..ncha] do
  629.         char:= char + a[j] * X[j];
  630.      od;
  631.      fail:= TestPerm2(tbl, char);
  632.      if fail = 0 then
  633.         Add(permch, char);
  634.         InfoCharTable2("\n", Length(permch), a, "\n", char, "\n");
  635.      fi;
  636.       else
  637.      s:= nextLevel(const, free);
  638.      if IsList(s) then
  639.         for i in s do
  640.            free[i]:= false;
  641.            a[i]:= amin[i];
  642.            const:= insertValue(const, i);
  643.         od;
  644.         solveKnot(const, free);
  645.      elif s > 0 then
  646.      for i in [amin[s]..amax[s]] do
  647.         a[s]:= i;
  648.         amin[s]:= i;
  649.         amax[s]:= i;
  650.         free[s]:= false;
  651.         solveKnot(insertValue(const, s), free);
  652.      od;
  653.      fi;
  654.       fi;
  655.    end;
  656.  
  657.    suche:= function(s)
  658.       local unten, oben, i, j, char, fail,
  659.         maxu, mino, c;
  660.  
  661.       unten:= [];
  662.       oben:= [];
  663.  
  664.       maxu:= 0;
  665.       for i in [1..Length(Conditor[s].u)] do
  666.      unten:= 0;
  667.      for j in [1..s-1] do
  668.         unten:= unten - a[j]*Conditor[s].u[i][j];
  669.      od;
  670.      if unten <= 0 then
  671.         unten:= 0;
  672.      else
  673.         unten:= QuoInt(unten-1, Conditor[s].u[i][s]) + 1;
  674.      fi;
  675.      maxu:= Maximum(maxu, unten);
  676.       od;
  677.       for i in [1..Length(Conditor[s].o)] do
  678.      oben:= 0;
  679.      for j in [1..s-1] do
  680.         oben:= oben + a[j]*Conditor[s].o[i][j];
  681.      od;
  682.      if oben < 0 then
  683.         oben:= -1;
  684.      else
  685.         oben:= QuoInt(oben, -Conditor[s].o[i][s]);
  686.      fi;
  687.      if not IsBound(mino) then
  688.         mino:= oben;
  689.      else
  690.         mino:= Minimum(mino, oben);
  691.      fi;
  692.       od;
  693.  
  694.       for i in [maxu..mino] do
  695.      a[s]:= i;
  696.      if s < ncha then 
  697.         suche(s+1);
  698.      else
  699.         total:= total+1;
  700.         char:= a * X;
  701.         fail:= TestPerm2(tbl, char);
  702.         if fail = 0 then
  703.            Add(permch, char);
  704.            InfoCharTable2("\n", Length(permch), a, "\n", char, "\n");
  705.         fi;
  706.      fi;
  707.       od;
  708.       a[s]:= 0;
  709.    end;
  710.  
  711.    nccl:= Length(tbl.classes);
  712.    total:= 0;
  713.    X:= permel.obj;
  714.    permch:= [];
  715.  
  716.    ncha:= Length(X);
  717.  
  718.    a:= [1];
  719.  
  720.    if IsBound(arec.degree) then
  721.       minR:= Minimum(arec.degree); maxR:= Maximum(arec.degree);
  722.       amax:= [1]; amin:= [1];
  723.       Conditor:= permel.Conditor;
  724.       free:= List(Conditor, x->true);
  725.       free[1]:= false;
  726.       const:= List(Conditor, x-> List(x, y->y[1]));
  727.       solveKnot(const, free);
  728.    else
  729.       Conditor:= [];
  730.       for i in [1..ncha] do
  731.      Conditor[i]:= rec(o:= Filtered(permel.Conditor[i], x->x[i] < 0),
  732.                u:= Filtered(permel.Conditor[i], x->x[i] > 0));
  733.       od;
  734.       suche(2);
  735.    fi;
  736.  
  737.    InfoCharTable2("\nTotal number of tested Characters:", total);
  738.    InfoCharTable2("\nSurviving:      ", Length(permch), "\n");
  739.  
  740.    return(Set(permch));
  741.  
  742. end;
  743.  
  744.  
  745. #############################################################################
  746. ##
  747. ##  PermBounds( <tbl> , <option> ) . . . . . . .  boundary points for simplex 
  748. ##
  749. PermBounds := function(tbl, degree)
  750.  
  751.    local i, j, h, o, dim, nccl, ncha, c, X, dir, root, ineq, other, rho,
  752.      vec, deglist, point;
  753.  
  754.    nccl:= Length(tbl.classes);
  755.    X:= RationalizedMat(tbl.irreducibles);
  756.  
  757.    c:= TransposedMat(X);
  758.  
  759.    # determine power conditions
  760.    # ie: for each class find a root and replace coloumn by difference.
  761.  
  762.    root:= ClassRootsCharTable(tbl);
  763.    ineq:= [];
  764.    other:= [];
  765.    for i in [2..nccl] do
  766.       if root[i] = [] then
  767.      AddSet(ineq, c[i]);
  768.      AddSet(other, c[i]);
  769.       else
  770.      AddSet(ineq, c[i] - c[root[i][1]]);
  771.      for j in root[i] do
  772.         AddSet(other, c[i] - c[j]);
  773.      od;
  774.       fi;
  775.    od;
  776.    ineq:= List(ineq, x->Gcd(x)^-1*x);
  777.    other:= List(other, x->Gcd(x)^-1*x);
  778.  
  779.    ncha:= Length(X);
  780.  
  781.    dim:= Length(ineq);
  782.    if dim <> Length(ineq[1])-1 then
  783.       Error("nonregular problem");
  784.    fi;
  785.  
  786.    # now correct inequalities ?
  787.    vec:= List(ineq, x->-x[1]);
  788.    ineq:= List(ineq, x->Sublist(x,[2..dim+1]));
  789.  
  790.    # determine boundary points
  791.    deglist:= List(Sublist(X, [2..ncha]), x->x[1]);
  792.    Add(ineq, deglist);
  793.    Add(vec, degree-1);
  794.  
  795.    point:= TransposedMat(ineq);
  796.    Add(point, -vec);
  797.  
  798.    point:= point^-1;
  799.  
  800.    dim:= Length(point[1]);
  801.  
  802.    rho:= point[dim][dim]^-1 * Sublist(point[dim], [1..dim-1]);
  803.    point:= Sublist(List(point, x-> x[dim]^-1 * Sublist(x, [1..dim-1])),
  804.            [1..dim-1]);
  805.  
  806.    return(rec(obj:= X, point:= point, rho:= rho, other:= other));
  807.  
  808. end;
  809.  
  810.  
  811. #############################################################################
  812. ##
  813. #F  PermComb( <tbl>, <arec> ) . . . . . . . . . . . .  permutation characters
  814. ##
  815. PermComb := function(tbl, arec)
  816.  
  817.    local mindeg, maxdeg, lincom, prep, xdegrees, X, total,
  818.        point, rho, permch, Constituent, maxList, minList;
  819.  
  820.    maxList:= function(list)
  821.       local i, col, max;
  822.       max:= [];
  823.       for i in [1..Length(list[1])] do
  824.          col:= Maximum(List(list, x->x[i]));
  825.          Add(max, Int(col));
  826.       od;
  827.       return max;
  828.    end;
  829.    
  830.    minList:= function(list)
  831.       local i, col, min;
  832.       min:= [];
  833.       for i in [1..Length(list[1])] do
  834.          col:= Minimum(List(list, x->x[i]));
  835.          if col <= 0 then
  836.             Add(min, 0);
  837.          elif IsInt(col) then
  838.             Add(min, col);
  839.          else
  840.             Add(min, Int(col)+1);
  841.          fi;
  842.       od;
  843.       return min;
  844.    end;
  845.  
  846.    lincom:= function()
  847.  
  848.       local i, j, k, a, d, ncha, comb, mdeg, maxb, searching, char, fail;
  849.  
  850.       ncha:= Length(xdegrees);
  851.       mdeg:= List([1..ncha], x->0);
  852.       comb:= List([1..ncha], x->0);
  853.       maxb:= [];
  854.       for i in [1..ncha-1] do
  855.          maxb[i]:= 0;
  856.          for j in [2..i] do
  857.         maxb[i]:= maxb[i] + xdegrees[j] * maxdeg[j];
  858.          od;
  859.       od;
  860.       d:= arec.degree - Constituent[1];
  861.       k:= ncha - 1;
  862.       searching:= true;
  863.    
  864.       while searching do
  865.          for j in Reversed([1..k]) do
  866.         a:= d - mdeg[j+1] - maxb[j];
  867.         if a <= 0 then
  868.            comb[j+1]:= 0;
  869.         else
  870.            comb[j+1]:= Minimum(QuoInt(a-1, xdegrees[j+1])+1, maxdeg[j+1]);
  871.         fi;
  872.         mdeg[j]:= mdeg[j+1] + comb[j+1] * xdegrees[j+1];
  873.          od;
  874.  
  875.          if mdeg[1] = d then
  876.         total:= total+1;
  877.         char:= Constituent + comb * X;
  878.         fail:= TestPerm1(tbl, char);
  879.         if fail = 0 then
  880.            fail:= TestPerm2(tbl, char);
  881.         fi;
  882.         if fail = 0 then
  883.            AddSet(permch, char);
  884.            InfoCharTable2("\n", Length(permch), comb, "\n", char, "\n");
  885.         else
  886.                InfoCharTable2("-\c");
  887.         fi;
  888.          fi;
  889.    
  890.          i:= 3;
  891.          while i <= ncha and
  892.            (comb[i] >= maxdeg[i] or mdeg[i-1]+ xdegrees[i] > d) do
  893.         i:= i+1;
  894.          od;
  895.          if i <= ncha then
  896.             mdeg[i-1]:= mdeg[i-1] + xdegrees[i];
  897.             comb[i]:= comb[i] + 1;
  898.             k:= i-2;
  899.          else
  900.         searching:= false;
  901.          fi;
  902.       od;
  903.       return();
  904.    end;
  905.  
  906.    total:= 0;
  907.    if IsBound(arec.bounds) then
  908.       prep:= arec.bounds;
  909.    else
  910.       prep:= PermBounds(tbl, 0);
  911.    fi;
  912.  
  913.    if prep = false then
  914.       X:= RationalizedMat(tbl.irreducibles);
  915.    else
  916.       X:= prep.obj;
  917.       rho:= tbl.order^-1 * (List(prep.point, x->prep.rho) - prep.point);
  918.    fi;
  919.    xdegrees:= List(X, x->x[1]);
  920.    mindeg:= List(X, x-> 0);
  921.    mindeg[1]:= 1;
  922.    permch:= [];
  923.  
  924.    if IsRec(prep) then
  925.       point:= prep.point + arec.degree * rho;
  926.       maxdeg:= [1];
  927.       Append(maxdeg, maxList(point));
  928.       mindeg:= [1];
  929.       Append(mindeg, minList(point));
  930.    else
  931.       maxdeg:= xdegrees;
  932.    fi;
  933.    # mindeg schreibt constiuenten vor:
  934.    Constituent:= mindeg * X;
  935.    maxdeg:= maxdeg - mindeg;
  936.  
  937.    lincom();
  938.  
  939.    return permch;
  940.  
  941. end;
  942.  
  943.  
  944. #############################################################################
  945. ##
  946. #F  PermCandidates( <tbl>, <characters>, <torso> )
  947. ##
  948. ##  computes all permutation character candidates of the character table
  949. ##  <tbl> which have only the (necessarily rational) characters <characters>
  950. ##  as constituents and which are completions of <torso>: Known values of the
  951. ##  candidates must be nonnegative integers in <torso>, the other positions
  952. ##  of <torso> are unbound; at least the degree '<torso>[1]' must be an
  953. ##  integer.
  954. ##
  955. PermCandidates := function( tbl, characters, torso )
  956.     local i, chi, matrix, fusion, moduls, divs, normindex, candidate,
  957.           classes, nonzerocol, possibilities, rest, images, uniques,
  958.           nccl, min_anzahl, min_class, erase_uniques, impossible, 
  959.           evaluate, ischaracter, first, localstep,
  960.           remain, ncha, pos, fusionperm, newimages, oldrows, newmatrix,
  961.           step, erster, descendclass, j, row, isnozerorow;
  962.  
  963.     ischaracter:= function( genchar )    # we know that 'genchar' is a
  964.                         # generalized character
  965.     local i, chi, classes, cand;
  966.     classes:= tbl.classes;
  967.     cand:= [];
  968.     for i in [ 1 .. Length( genchar ) ] do
  969.       cand[i]:= genchar[i] * classes[i];
  970.     od;
  971.     for chi in characters do
  972.       if cand * chi < 0 then return false; fi;
  973.     od;
  974.     return true;
  975.     end;
  976.     #
  977.     isnozerorow:= function( row )
  978.     local i;
  979.     for i in row do if i <> 0 then return true; fi; od;
  980.     return false;
  981.     end;
  982.     
  983.     # step 1: check and improve input
  984.     
  985.     if not IsInt( torso[1] ) or torso[1] <= 0 then     # degree
  986.       Error( "degree must be positive integer" );
  987.     elif tbl.order mod torso[1] <> 0 then
  988.       return [];
  989.     fi;
  990.     for i in [ 1 .. Length( characters[1] ) ] do       # necessary zeroes
  991.       if ( tbl.order / torso[1] ) mod tbl.orders[i] <> 0 then
  992.         if IsBound( torso[i] ) and IsInt( torso[i] ) and torso[i] <> 0 then
  993.           Error( "value must be zero at class ", i );
  994.         fi;
  995.         torso[i]:= 0;
  996.       fi;
  997.     od;
  998.     matrix:= [];                                        # delete impossibles
  999.     for chi in characters do
  1000.       if chi[1] < torso[1] then AddSet( matrix, chi ); fi;
  1001.     od;
  1002.     if matrix = [] then       # At most the trivial character is possible
  1003.       if ForAll( torso, x -> x = 1 ) then
  1004.         return [ List( [ 1 .. Length( tbl.centralizers ) ], x -> 1 ) ];
  1005.       fi;
  1006.     fi;
  1007.     matrix:= CollapsedMat( matrix, [ ] );
  1008.     fusion:= matrix.fusion;
  1009.     matrix:= matrix.mat;
  1010.     moduls:= [];
  1011.     for i in [ 1 .. Length( fusion ) ] do
  1012.       if IsBound( moduls[ fusion[i] ] ) then
  1013.         moduls[ fusion[i] ]:= Maximum( moduls[ fusion[i] ],
  1014.                                        tbl.centralizers[i] );
  1015.         # Would Lcm be allowed?
  1016.       else
  1017.         moduls[ fusion[i] ]:= tbl.centralizers[i];
  1018.       fi;
  1019.     od;
  1020.     divs:= [ torso[1] ];    # X[1] / Gcd( X[1], classes[g] ) | X[g]
  1021.                             # better: X[1] / Gcd( X[1], order/N(g) ) | X[g]
  1022.     for i in [ 2 .. Length( fusion ) ] do
  1023.       normindex:= ( tbl.classes[i] * Length( ClassOrbitCharTable( tbl, i ) ) )
  1024.                                                          / Phi( tbl.orders[i] );
  1025.       if IsBound( divs[ fusion[i] ] ) then
  1026.         divs[ fusion[i] ]:= Lcm( divs[ fusion[i] ],
  1027.                                  torso[1] / GcdInt( torso[1], normindex ) );
  1028.       else
  1029.         divs[ fusion[i] ]:= torso[1] / GcdInt( torso[1], normindex );
  1030.       fi;
  1031.     od;
  1032.     candidate:= [];
  1033.     nonzerocol:= [];
  1034.     classes:= [];
  1035.     for i in [ 1 .. Length( moduls ) ] do
  1036.       candidate[i]:= 0;
  1037.       nonzerocol[i]:= true;
  1038.       classes[i]:= 0;
  1039.     od;
  1040.     for i in [ 1 .. Length( fusion ) ] do
  1041.       classes[ fusion[i] ]:= classes[ fusion[i] ] + tbl.classes[i];
  1042.     od;
  1043.     possibilities:= []; # global list of all permutation character candidates
  1044.     rest:= tbl.order;
  1045.     images:= [];
  1046.     uniques:= [];
  1047.     for i in [ 1 .. Length( fusion ) ] do
  1048.       if IsBound( torso[i] ) and IsInt( torso[i] ) then
  1049.         if IsBound( images[ fusion[i] ] ) then
  1050.           if torso[i] <> images[ fusion[i] ] then
  1051.             return [];      # different values in equal columns
  1052.           fi;
  1053.         else
  1054.           images[ fusion[i] ]:= torso[i];
  1055.           AddSet( uniques, fusion[i] );
  1056.           rest:= rest - classes[ fusion[i] ] * torso[i];
  1057.           if rest < 0 then return []; fi;
  1058.         fi;
  1059.       fi;
  1060.     od;
  1061.     nccl:= Length( moduls );
  1062.     
  1063.     InfoCharTable2( "#I PermCandidates : input checked\n" );
  1064.     
  1065.     # step 2: first elimination before backtrack:
  1066.     
  1067.     erase_uniques:= function( uniques, nonzerocol, candidate, rest )
  1068.     
  1069.     # eliminate all unique columns, adapt nonzerocol;
  1070.     # then look if other columns become unique or if a contradiction occurs;
  1071.     # also look at which column the least number of values is left
  1072.     
  1073.     local i, j, extracted, col, row, quot, val, ggt, a, b, k, u, anzahl,
  1074.           firstallowed, step, gencharacter, shrink;
  1075.  
  1076.     extracted:= [];
  1077.     while uniques <> [] do
  1078.       for col in uniques do
  1079.         if col < 0 then         # nonzero entries in 'col' already eliminated
  1080.           col:= -col;
  1081.           candidate[ col ]:= ( candidate[ col ] + images[ col ] )
  1082.                              mod moduls[ col ];
  1083.           row:= false;
  1084.         else                    # eliminate nonzero entries in 'col'
  1085.           candidate[ col ]:= ( candidate[ col ] + images[ col ] )
  1086.                              mod moduls[ col ];
  1087.           row:= StepModGauss( matrix, moduls, nonzerocol, col );
  1088.     
  1089.           # delete zero rows:
  1090.           shrink:= [];
  1091.           for i in matrix do if isnozerorow( i ) then Add( shrink, i ); fi; od;
  1092.           matrix:= shrink;
  1093.         fi;
  1094.         if row <> false then
  1095.           Add( extracted, row );
  1096.           quot:= candidate[ col ] / row[ col ];
  1097.           if not IsInt( quot ) then
  1098.             impossible:= true;
  1099.             return extracted;
  1100.           fi;
  1101.           for j in [ 1 .. nccl ] do
  1102.             if nonzerocol[j] then
  1103.               candidate[j]:= ( candidate[j] - quot * row[j] ) mod moduls[j];
  1104.             fi;
  1105.           od;
  1106.         elif candidate[col] <> 0 then
  1107.           impossible:= true;
  1108.           return extracted;
  1109.         fi;
  1110.         nonzerocol[col]:= false;
  1111.       od;
  1112.       min_anzahl:= "infinity";
  1113.       uniques:= [];
  1114.     
  1115.       # compute the number of possible values 'x' for each class 'i'\:
  1116.       # 'x' must be smaller or equal 'Minimum( rest / classes[i], torso[1] )',
  1117.       #             divisible by 'divs[i]' and
  1118.       #             congruent '-candidate[i]' modulo the Gcd of column 'i'.
  1119.       for i in [ 1 .. nccl ] do
  1120.         if nonzerocol[i] then
  1121.           val:= moduls[i];
  1122.           for j in matrix do val:= GcdInt( val, j[i]); od;  # the Gcd of 'i'
  1123.           # zerocol iff val = moduls[i]
  1124.           first:= ( - candidate[i] ) mod val;  # the first possible value
  1125.                                                     # in the case 'divs[i] = 1'
  1126.           if divs[i] = 1 then
  1127.             localstep:= val;          # all values are
  1128.                                       # 'first, first + val, first + 2*val ..'
  1129.           else
  1130.             ggt:= Gcdex( divs[i], val );
  1131.             a:= ggt.coeff1;
  1132.             ggt:= ggt.gcd;
  1133.             if first mod ggt <> 0 then   # ggt divides 'divs[i]' and hence 'x';
  1134.                                          # since ggt divides 'val', which must
  1135.                                          # divide '( x + candidate[i] )',
  1136.                                          # we must have ggt dividing 'first'
  1137.               impossible:= true;
  1138.               return extracted;
  1139.             fi;
  1140.             localstep:= Lcm( divs[i], val );
  1141.             first:= ( first * a * divs[i] / ggt ) mod localstep;
  1142.                                          # satisfies the required congruences
  1143.                                          # (and that is enough here)
  1144.           fi;
  1145.           anzahl:= Int( ( Minimum( Int( rest[1] / classes[i] ), torso[1] )
  1146.                           - first + localstep ) / localstep );
  1147.           if anzahl <= 0 then       # contradiction
  1148.             impossible:= true;
  1149.             return extracted;
  1150.           elif anzahl = 1 then      # unique
  1151.             images[i]:= first;
  1152.             if val = moduls[i] then     # no elimination necessary
  1153.                                         # (the column consists of zeroes)
  1154.               Add( uniques, -i );
  1155.             else
  1156.               Add( uniques, i );
  1157.             fi;
  1158.             rest[1]:= rest[1] - classes[i] * images[i];
  1159.           elif anzahl < min_anzahl then
  1160.             min_anzahl:= anzahl;
  1161.             step:= localstep;
  1162.             firstallowed:= first;
  1163.             min_class:= i;
  1164.           fi;
  1165.         fi;
  1166.       od;
  1167.     od;
  1168.     if min_anzahl = "infinity" then
  1169.       if rest[1] = 0 then
  1170.         gencharacter:= Indirected( images, fusion );
  1171.         if ischaracter( gencharacter ) and TestPerm1( tbl, gencharacter ) = 0
  1172.            and TestPerm2( tbl, gencharacter ) = 0 then
  1173.           Add( possibilities, gencharacter );
  1174.         fi;
  1175.       fi;
  1176.       impossible:= true;
  1177.     else
  1178.       images[ min_class ]:= rec( firstallowed:= firstallowed, # first value
  1179.                                  step:= step,                 # step
  1180.                                  anzahl:= min_anzahl );       # no. of values
  1181.       impossible:= false;
  1182.     fi;
  1183.     return extracted;
  1184.     # impossible = true: calling function will return from backtrack
  1185.     # impossible = false: then min_class < E( 3 ), and images[ min_class ]
  1186.     #           contains the informations for descending at min_class
  1187.     end;
  1188.     
  1189.     rest:= [ rest ];
  1190.     erase_uniques( uniques, nonzerocol, candidate, rest );
  1191.     
  1192.     # here we may forget the extracted rows, later in the backtrack they must be
  1193.     # appended after each return.
  1194.     
  1195.     rest:= rest[1];
  1196.     if impossible then return possibilities; fi;
  1197.     
  1198.     InfoCharTable2( "#I PermCandidates : unique columns erased, there are ",
  1199.                     Length( Filtered( nonzerocol, x -> x ) ), " columns left,\n",
  1200.                     "#I    the number of constituents is ",
  1201.                     Length( matrix ), ".\n" );
  1202.     
  1203.     # step 3: collapse
  1204.     
  1205.     remain:= Filtered( [ 1 .. nccl ], x -> nonzerocol[x] );
  1206.     for i in [ 1 .. Length( matrix ) ] do
  1207.       matrix[i]:= Sublist( matrix[i], remain );
  1208.     od;
  1209.     candidate:=  Sublist( candidate, remain );
  1210.     divs:=       Sublist( divs, remain );
  1211.     nonzerocol:= Sublist( nonzerocol, remain );
  1212.     moduls:=     Sublist( moduls, remain );
  1213.     classes:=    Sublist( classes, remain );
  1214.     matrix:= ModGauss( matrix, moduls );
  1215.     ncha:= Length( matrix );
  1216.     pos:= 1;
  1217.     fusionperm:= [];
  1218.     newimages:= [];
  1219.     for i in remain do
  1220.       fusionperm[ i ]:= pos;
  1221.       if IsBound( images[i] ) then newimages[ pos ]:= images[i]; fi;
  1222.       pos:= pos + 1;
  1223.     od;
  1224.     min_class:= fusionperm[ min_class ];
  1225.     for i in Difference( [ 1 .. nccl ], remain ) do
  1226.       fusionperm[i]:= pos;
  1227.       newimages[ pos ]:= images[i];
  1228.       pos:= pos + 1;
  1229.     od;  
  1230.     images:= newimages;
  1231.     fusion:= CompositionMaps( fusionperm, fusion );
  1232.     nccl:= Length( nonzerocol );
  1233.     
  1234.     InfoCharTable2( "#I PermCandidates : known columns physically deleted,\n",
  1235.                     "#I    a backtrack search will be needed\n" );
  1236.     
  1237.     # step 4: backtrack
  1238.     
  1239.     evaluate:= function( candidate, rest, nonzerocol, uniques )
  1240.     local i, j, col, val, row, quot, extracted, step, erster, descendclass;
  1241.     rest:= [ rest ];
  1242.     extracted:= erase_uniques( [ uniques ], nonzerocol, candidate, rest );
  1243.     rest:= rest[1];
  1244.     if impossible then return extracted; fi;
  1245.     descendclass:= min_class;
  1246.     step:= images[ descendclass ].step;    # spalten-ggt
  1247.     erster:= images[ descendclass ].firstallowed;
  1248.     rest:= rest + ( step - erster ) * classes[ descendclass ];
  1249.     for i in [ 1 .. min_anzahl ] do
  1250.       images[ descendclass ]:= erster + (i-1) * step;
  1251.       rest:= rest - step * classes[ descendclass ];
  1252.       oldrows:=
  1253.               evaluate( Copy( candidate ), rest, Copy( nonzerocol ), descendclass );
  1254.       Append( matrix, oldrows );
  1255.       if Length( matrix ) > ( 3 * ncha ) / 2 then
  1256.         newmatrix:= [];         # matrix:= ModGauss( matrix, moduls );
  1257.         for j in [ 1 .. Length( matrix[1] ) ] do
  1258.           if nonzerocol[j] then
  1259.             row:= StepModGauss( matrix, moduls, nonzerocol, j );
  1260.             if row <> false then Add( newmatrix, row ); fi;
  1261.           fi;
  1262.         od;
  1263.         matrix:= newmatrix;
  1264.       fi;
  1265.     od;
  1266.     return extracted;
  1267.     end;
  1268.     
  1269.     #
  1270.     
  1271.     step:= images[min_class].step;      # spalten-ggt
  1272.     erster:= images[min_class].firstallowed;
  1273.     descendclass:= min_class;
  1274.     rest:= rest + ( step - erster ) * classes[ descendclass ];
  1275.     for i in [ 1 .. min_anzahl ] do
  1276.       images[ descendclass ]:= erster + (i-1) * step;
  1277.       rest:= rest - step * classes[ descendclass ];
  1278.       oldrows:=
  1279.             evaluate( Copy( candidate ), rest, Copy( nonzerocol ), descendclass );
  1280.       Append( matrix, oldrows );
  1281.       if Length( matrix ) > ( 3 * ncha ) / 2 then
  1282.         newmatrix:= [];          # matrix:= ModGauss( matrix, moduls );
  1283.         for j in [ 1 .. Length( matrix[1] ) ] do
  1284.           if nonzerocol[j] then
  1285.             row:= StepModGauss( matrix, moduls, nonzerocol, j );
  1286.             if row <> false then Add( newmatrix, row ); fi;
  1287.           fi;
  1288.         od;
  1289.         matrix:= newmatrix;
  1290.       fi;
  1291.     od;
  1292.     return possibilities;
  1293.     end;
  1294.  
  1295.  
  1296. #############################################################################
  1297. ##
  1298. #F  'PermCandidatesFaithful( <tbl>, <chars>, <norm\_subgrp>, <nonfaithful>,
  1299. #F                           <lower>, <upper>, <torso> )'
  1300. ##
  1301. ##  computes all permutation character candidates of the character table
  1302. ##  <tbl> which have only the (necessarily rational) characters <chars>
  1303. ##  as constituents and which are completions of <torso>: Known values of the
  1304. ##  candidates must be nonnegative integers in <torso>, the other positions
  1305. ##  of <torso> are unbound; at least the degree '<torso>[1]' must be an
  1306. ##  integer.
  1307. ##
  1308.  
  1309. # 'PermCandidatesFaithful'\\
  1310. # '      ( tbl, chars, norm\_subgrp, nonfaithful, lower, upper, torso )'
  1311. # 
  1312. # reference of variables\:
  1313. # \begin{itemize}
  1314. # \item 'tbl'\:         a character table which must contain field 'order'
  1315. # \item 'chars'\:       *rational* characters of 'tbl'
  1316. # \item 'nonfaithful'\: $(1_{UN})^G$
  1317. # \item 'lower'\:       lower bounds for $(1_U)^G$
  1318. #                       (may be unspecified, i.e. 0)
  1319. # \item 'upper'\:       upper bounds for $(1_U)^G$
  1320. #                       (may be unspecified, i.e. 0)
  1321. # \item 'torso'\:       $(1_U)^G$ (at known positions)
  1322. # \item 'faithful'\:    'torso' - 'nonfaithful'
  1323. # \item 'divs'\:        'divs[i]' divides $(1_U)^G[i]$
  1324. # \end{itemize}
  1325. # 
  1326. # The algorithm proceeds in 5 steps\:
  1327. # 
  1328. # *step 1*\: Try to improve the input data
  1329. # \begin{enumerate}
  1330. # \item Check if 'torso[1]' divides $\|G\|$, 'nonfaithful[1]' divides
  1331. #       'torso[1]'.
  1332. # \item If 'orders[i]' does not divide $U$ 
  1333. #       or if $'nonfaithful[i]' = 0$, 'torso[i]' must be 0.
  1334. # \item Transfer 'upper' and 'lower' to upper bounds and lower bounds for
  1335. #       the values of 'faithful' and try to improve them\:
  1336. # \begin{enumerate}
  1337. # \item \['lower[i]'\:= \max\{'lower[i]',0\} - 'nonfaithful[i]';\]
  1338. #       If $UN$ has only one galois family of classes for a prime
  1339. #       representative order $p$, and $p$ divides $\|G\|/'torso[1]'$,
  1340. #       or if $g_i$ is a $p$-element and $p$ does not divide $[UN\:U]$,
  1341. #       then necessarily these elements lie in $U$, and we have
  1342. #       \['lower[i]'\:= \max\{'lower[i]',1\} - 'nonfaithful[i]';\]
  1343. # \item \begin{eqnarray*}
  1344. #       'upper[i]' & \:= & \min\{'upper[i]','torso[1]',
  1345. #                                'tbl.centralizers[i]'-1,\\
  1346. #       & & 'torso[1]' \cdot 'nonfaithful[i]'/'nonfaithful[1]'\}
  1347. #       -'nonfaithful[i]'.
  1348. #       \end{eqnarray*}
  1349. # \end{enumerate}
  1350. # \item Compute divisors of the values of $(1_U)^G$\:
  1351. #       \['divs[i]'\:= 'torso[1]'/\gcd\{'torso[1]',\|G\|/\|N_G[i]\|\}
  1352. #       \mbox{\rm \ divides} (1_U)^G[i].\]
  1353. #       ($\|N_G[i]\|$ denotes the normalizer order of $\langle g_i \rangle$.)
  1354. # 
  1355. #       If $g_i$ generates a Sylow $p$ subgroup of $UN$ and $p$ does not
  1356. #       divide $[UN\:U]$ then $(1_{UN})^G(g_i)$ divides $(1_U)^G(g_i)$,
  1357. #       and we have \['divs[i]'\:= 'Lcm( divs[i], nonfaithful[i] )'.\]
  1358. # \item Compute 'roots' and 'powers' for later improvements of local bounds\:
  1359. #       $j$ is in 'roots[i]' iff there exists a prime $p$ with powermap
  1360. #       stored on 'tbl' and $g_j^p = g_i$,
  1361. #       $j$ is in 'powers[i]' iff there exists a prime $p$ with powermap
  1362. #       stored on 'tbl' and $g_i^p = g_j$.
  1363. # \item Compute the list 'matrix' of possible constituents of 'faithful'\:
  1364. #       (If 'torso[1]' = 1, we have none.)
  1365. #       Every constituent $\chi$ must have degree $\chi(1)$ lower than
  1366. #       $'torso[1]' - 'nonfaithful[1]'$, and $N \not\subseteq \ker(\chi)$;
  1367. #       also, for all i, we must have
  1368. #       $\chi[i] \geq \chi[1] - 'faithful[1]' - 'nonfaithful[i]'$.
  1369. # \end{enumerate}
  1370. # 
  1371. # *step 2*\: Collapse classes which are equal for all possible constituents
  1372. # 
  1373. # (*Note*\: We only needed the fusion of classes, but we also have to make
  1374. #         a copy.)
  1375. # 
  1376. # After that, 'fusion' induces an equivalence relation of conjugacy classes,
  1377. # 'matrix' is the new list of constituents. Let $C \:= \{i_1,\ldots,i_n\}$
  1378. # be an equivalence class; for further computation, we have to adjust the
  1379. # other informations\:
  1380. # 
  1381. # \begin{enumerate}
  1382. # \item Collapse 'faithful'; the values that are not yet known later will be
  1383. #       filled in using the decomposability test (see "ContainedCharacters");
  1384. #       the equality 
  1385. #       \['torso' = 'nonfaithful' + 'Indirection'('faithful','fusion')\]
  1386. #       holds, so later we have
  1387. #       \[(1_U)^G = (1_{UN})^G + 'Indirection( faithful , fusion )'.\]
  1388. # \item Adjust the old structures\:
  1389. # \begin{enumerate}
  1390. # \item Define as new roots \[ 'roots[C]'\:=
  1391. #       \bigcup_{1 \leq j \leq n} 'set(Indirection(fusion,roots[i_j]))', \]
  1392. # \item as new powers \[ 'powers[C]'\:=
  1393. #       \bigcup_{1 \leq j \leq n} 'set(Indirection(fusion,powers[i_j]))',\]
  1394. # \item as new upper bound \['upper[C]'\:=
  1395. #       \min_{1 \leq j \leq n}('upper[i_j]'), \]
  1396. #       try to improve the bound using the fact that for each j in
  1397. #       'roots[C]' we have
  1398. #       \['nonfaithful[j]'+'faithful[j]' \leq
  1399. #       'nonfaithful[C]'+'faithful[C]',\]
  1400. # \item as new lower bound \['lower[C]'\:=
  1401. #       \max_{1 \leq j \leq n}('lower[i_j]'),\]
  1402. #        try to improve the bound using the fact that for each j in
  1403. #        'powers[C]' we have
  1404. #        \['nonfaithful[j]'+'faithful[j]' \geq
  1405. #        'nonfaithful[C]'+'faithful[C]',\]
  1406. # \item as new divisors \['divs[C]'\:=
  1407. #       'Lcm'( 'divs'[i_1],\ldots, 'divs'[i_n] ).\]
  1408. # \end{enumerate}
  1409. # \item Define some new structures\:
  1410. # \begin{enumerate}
  1411. # \item the moduls for the basechange \['moduls[C]'\:=
  1412. #          \max_{1 \leq j \leq n}('tbl.centralizers[i_j]'),\]
  1413. # \item new classes \['classes[C]'\:=
  1414. #          \sum_{1 \leq j \leq n} 'tbl.classes[i_j]',\]
  1415. # \item \['nonfaithsum[C]'\:= \sum_{1 \leq j \leq n} 'tbl.classes[i_j]'
  1416. #       \cdot 'nonfaithful[i_j]',\]
  1417. # \item a variable 'rest', preset with $\|G\|$\: We know that
  1418. #       $\sum_{g \in G} (1_U)^G(g) = \|G\|$.
  1419. #       Let the values of $(1_U)^G$ be known for a subset
  1420. #       $\tilde{G} \subseteq G$, and define
  1421. #       $'rest'\:= \sum_{g \in \tilde{G}} (1_U)^G(g)$;
  1422. #       then for $g \in G \setminus \tilde{G}$, we
  1423. #       have $(1_U)^G(g) \leq 'rest'/\|Cl_G(g)\|$.
  1424. #       In our situation, this means
  1425. #       \[\sum_{1 \leq j \leq n} \|Cl_G(g_j)\| \cdot (1_U)^G(g_j)
  1426. #       \leq 'rest',\]
  1427. #       or equivalently
  1428. #       $'nonfaithsum[C]' + 'faithful[C]' \cdot 'classes[C]' \leq 'rest'$.
  1429. #       (*Note* that 'faithful' necessarily is constant on 'C'.).
  1430. #       So 'rest' is used to update local upper bounds.
  1431. # \end{enumerate}
  1432. # \item (possible acceleration\: If we allow to collapse classes on which
  1433. #       'nonfaithful' takes different values, the situation is a little
  1434. #       more difficult. The new upper and lower bounds will be others,
  1435. #       and the new divisors will become moduls in a congruence relation
  1436. #       that has nothing to do with the values of torso or faithful.)
  1437. # \end{enumerate}
  1438. # 
  1439. # *step 3*\: Eliminate classes for which the values of 'faithful' are known
  1440. # 
  1441. # The subroutine 'erase' successively eliminates the columns of 'matrix'
  1442. # listed up in 'uniques'; at most one row remains with a nonzero entry 'val'
  1443. # in that column 'col', this is the gcd of the former column values.
  1444. # If we can eliminate 'difference[ col ]', we proceed with the next column,
  1445. # else there is a contradiction (i.e. no generalized character exists that
  1446. # satisfies our conditions), and we set 'impossible' true and then return
  1447. # all extracted rows which must be used at lower levels of a backtrack
  1448. # which may have called 'erase'.
  1449. # Having erased all uniques without finding a contradiction, 'erase' looks
  1450. # if other columns have become unique, i.e. the bounds and divisors allow
  1451. # just one value; those columns are erased, too.
  1452. # 'erase' also updates the (local) upper and lower bounds using 'roots',
  1453. # 'powers' and 'rest'.
  1454. # If no further elimination is possible, there can be two reasons\:
  1455. # If all columns are erased, 'faithful' is complete, and if it is really a
  1456. # character, it will be appended to 'possibilities'; then 'impossible' is
  1457. # set true to indicate that this branch of the backtrack search tree has
  1458. # ended here.
  1459. # Otherwise 'erase' looks for that column where the number of possible
  1460. # values is minimal, and puts a record with informations about first
  1461. # possible value, step (of the arithmetic progression) and number of
  1462. # values into that column of 'faithful';
  1463. # the number of the column is written to 'min\_class',
  1464. # 'impossible' is set false, and the extracted rows are returned.
  1465. # 
  1466. # And this way 'erase' computes the lists of possible values\:
  1467. # 
  1468. # Let $d\:= 'divs[ i ]', z\:= 'val', c\:= 'difference[ i ]',
  1469. # n\:= 'nonfaithful[ i ]', low\:= 'local\_lower[ i ]',
  1470. # upp\:= 'local\_upper[ i ]', g\:= \gcd\{d,z\} = ad + bz$.
  1471. # 
  1472. # Then the set of allowed values is
  1473. # \[ M\:= \{x; low \leq x \leq upp; x \equiv -c \pmod{z};
  1474. #              x \equiv -n \pmod{d} \}.\]
  1475. # If $g$ does not divide $c-n$, we have a contradiction, else
  1476. # $y\:= -n -ad \frac{c-n}{g}$ defines the correct arithmetic progression\:
  1477. # \[ M = \{x;low \leq x \leq upp; x \equiv y \pmod{'Lcm'(d,z)} \} \]
  1478. # The minimum of $M$ is then given by 
  1479. # \[ L\:= low + (( y - low ) \bmod 'Lcm'(d,z)).\]
  1480. # 
  1481. # (*Note* that for the usual case $d=1$ we have $a=1, b=0, y=-c$.)
  1482. # 
  1483. # Therefore the number of values is
  1484. # $'Int( '( upp - L ) ' / Lcm'(d,z) ' )' +1$.
  1485. # 
  1486. # In step 3, 'erase' is called with the list of known values of 'faithful'
  1487. # as 'uniques'.
  1488. # Afterwards, if 'InfoCharTable2 = Print' and a backtrack search is necessary,
  1489. # a message about the found improvements and the expected expense
  1490. # for the backtrack search is printed.
  1491. # (*Note* that we are allowed to forget the rows which we have extracted in
  1492. # this first elimination.)
  1493. # 
  1494. # *step 4*\: Delete eliminated columns physically before the backtrack search
  1495. # 
  1496. # The eliminated columns (those with 'nonzerocol[i] = false') of 'matrix'
  1497. # are deleted, and the other objects are adjusted\:
  1498. # \begin{enumerate}
  1499. # \item In 'differences', 'divs', 'nonzerocol', 'moduls', 'classes',
  1500. #       'nonfaithsum', 'upper', 'lower', the columns are simply deleted.
  1501. # \item For adjusting 'fusion', first a permutation 'fusionperm' is
  1502. #       constructed that maps the eliminated columns behind the remaining
  1503. #       columns; after 'faithful\:= Indirection( faithful, fusionperm )' and
  1504. #       'fusion\:= Indirection( fusionperm, fusion )', we have again
  1505. #       \[ (1_U)^G = (1_{UN})^G + 'Indirection( faithful, fusion )'. \]
  1506. # \item adjust 'roots' and 'powers'.
  1507. # \end{enumerate}
  1508. # 
  1509. # *step 5*\: The backtrack search
  1510. # 
  1511. # The subroutine 'evaluate' is called with a column 'unique'; this (and other
  1512. # uniques, if possible) is eliminated. If there was an inconsistence, the
  1513. # extracted rows are returned; otherwise the column 'min\_class' subsequently
  1514. # will be set to all possible values and 'evaluate' is called with
  1515. # 'unique = min\_class'.
  1516. # After each return from 'evaluate', the returned rows are appended to matrix
  1517. # again; if matrix becomes too long, a call of 'ModGauss' will shrink it.
  1518. # Note that 'erase' must be able to update the value of 'rest', but any call
  1519. # of 'evaluate' must not change 'rest'; so 'rest' is a parameter of
  1520. # 'evaluate', but for 'erase' it is global (realized as '[ rest ]').
  1521.  
  1522. PermCandidatesFaithful :=
  1523.    function( tbl, chars, norm_subgrp, nonfaithful, upper, lower, torso )
  1524.  
  1525.     local i, x, N, nccl, faithful, families, j, primes, orbits, factors,
  1526.           pparts, cyclics, divs, roots, powers, matrix, fusion, inverse,
  1527.           union, moduls, classes, nonfaithsum, rest, uniques, collfaithful, 
  1528.           orig_nonfaithful, difference, nonzerocol, possibilities,
  1529.           ischaracter, isnozerorow, erase, min_number, impossible, remain,
  1530.           ncha, pos, fusionperm, shrink, ppart, myset, newfaithful,
  1531.           min_class, evaluate, step, first, descendclass, oldrows, newmatrix,
  1532.           row;
  1533.  
  1534.     #
  1535.     # step 1: Try to improve the input data
  1536.     #
  1537.     lower:= Copy( lower );
  1538.     upper:= Copy( upper );
  1539.     torso:= Copy( torso );
  1540.  
  1541.     # order of normal subgroup
  1542.     N := Sum( Indirected( tbl.classes, norm_subgrp ) );
  1543.     nccl:= Length( nonfaithful );
  1544.  
  1545.     if not IsInt( torso[1] ) or torso[1] <= 0 then
  1546.       Error( "degree must be positive integer" );
  1547.     elif tbl.order mod torso[1] <> 0 or torso[1] mod nonfaithful[1] <> 0
  1548.          or torso[1] = 1 then
  1549.       return [];
  1550.     fi;
  1551.     for i in [ 1 .. nccl ] do
  1552.       if ( tbl.order / torso[1] ) mod tbl.orders[i] <> 0
  1553.          or nonfaithful[i] = 0 then
  1554.         if IsBound( torso[i] ) and IsInt( torso[i] ) and torso[i] <> 0 then
  1555.           return [];
  1556.         fi;
  1557.         torso[i]:= 0;
  1558.       fi;
  1559.     od;
  1560.     faithful:= [];
  1561.     for i in [ 1 .. Length( torso ) ] do
  1562.       if IsBound( torso[i] ) and IsInt( torso[i] ) then
  1563.         faithful[i]:= torso[i] - nonfaithful[i];
  1564.       fi;
  1565.     od;
  1566.     # compute a list of galois families for 'tbl':
  1567.     families:= [];
  1568.     for i in [ 1 .. nccl ] do
  1569.       if not IsBound( families[i] ) then
  1570.         families[i]:= ClassOrbitCharTable( tbl, i );
  1571.         for j in families[i] do families[j]:= families[i]; od;
  1572.       fi;
  1573.     od;
  1574.     # 'primes': prime divisors of $|U|$ for which there is only one $G$-family
  1575.     # of that element order in $UN$:
  1576.     primes:= Set( Factors( tbl.order / torso[1] ) );
  1577.     orbits:= [];
  1578.     for i in [ 1 .. Length( primes ) ] do orbits[i]:= []; od;
  1579.     for i in [ 1 .. nccl ] do
  1580.       if tbl.orders[i] in primes and nonfaithful[i] <> 0 then
  1581.         AddSet( orbits[ Position( primes, tbl.orders[i] ) ], families[i] );
  1582.       fi;
  1583.     od;
  1584.     for i in [ 1 .. Length( primes ) ] do
  1585.       if Length( orbits[i] ) <> 1 then primes[i]:= 1; fi;
  1586.     od;
  1587.     primes:= Difference( Set( primes ), [ 1 ] );
  1588.     
  1589.     # which Sylow subgroups of $UN$ are contained in $U$:
  1590.     
  1591.     factors:= Factors( tbl.order / torso[1] );
  1592.     pparts:= [];
  1593.     for i in Set( factors ) do
  1594.       if ( torso[1] / nonfaithful[1] ) mod i <> 0 then
  1595.         # i is a prime divisor of $\|U\|$ not dividing
  1596.         # $|UN|/|U| = 'torso[1] / nonfaithful[1]'$:
  1597.         ppart:= 1;
  1598.         for j in factors do
  1599.           if j = i then ppart:= ppart * i; fi;
  1600.         od;
  1601.         Add( pparts, ppart );
  1602.       fi;
  1603.     od;
  1604.     cyclics:= [];           # cyclic sylow subgroups
  1605.     for i in [ 1 .. nccl ] do
  1606.       if tbl.orders[i] in pparts and nonfaithful[i] <> 0 then
  1607.         Add( cyclics, i );
  1608.       fi;
  1609.     od;
  1610.     # transfer bounds:
  1611.     if lower = 0 then
  1612.       lower:= [ torso[1] ];
  1613.       for i in [ 2 .. nccl ] do lower[i]:= 0; od;
  1614.     fi;
  1615.     if upper = 0 then
  1616.       upper:= [];
  1617.       for i in [ 1 .. nccl ] do upper[i]:= torso[1]; od;
  1618.     fi;
  1619.     upper[1]:= upper[1] - nonfaithful[1];
  1620.     lower[1]:= lower[1] - nonfaithful[1];
  1621.     for i in [ 2 .. nccl ] do
  1622.       if nonfaithful[i] <> 0 and
  1623.          ( tbl.orders[i] in primes
  1624.            or 0 in List( pparts, x -> x mod tbl.orders[i] ) ) then
  1625.         lower[i]:= Maximum( lower[i], 1 ) - nonfaithful[i];
  1626.       else
  1627.         lower[i]:= Maximum( lower[i], 0 ) - nonfaithful[i];
  1628.       fi;
  1629.       if i in norm_subgrp then
  1630.         upper[i]:= Minimum( upper[i], torso[1], tbl.centralizers[i] - 1,
  1631.                    Int( ( N * nonfaithful[1] - torso[1] ) / tbl.classes[i] ),
  1632.                         Int( torso[1] * nonfaithful[i] / nonfaithful[1] ) )
  1633.                    - nonfaithful[i];
  1634.       else
  1635.         upper[i]:= Minimum( upper[i], torso[1], tbl.centralizers[i] - 1,
  1636.                         Int( torso[1] * nonfaithful[i] / nonfaithful[1] ) )
  1637.                    - nonfaithful[i];
  1638.       fi;
  1639.     od;
  1640.     for i in [ 1 .. nccl ] do
  1641.       if IsBound( faithful[i] ) then
  1642.         if faithful[i] >= lower[i] then
  1643.           lower[i]:= faithful[i];
  1644.         else
  1645.           return [];
  1646.         fi;
  1647.         if faithful[i] <= upper[i] then
  1648.           upper[i]:= faithful[i];
  1649.         else
  1650.           return [];
  1651.         fi;
  1652.       elif lower[i] = upper[i] then
  1653.         faithful[i]:= lower[i];
  1654.       fi;
  1655.     od;
  1656.     # compute divs:
  1657.     divs:= [ torso[1] ];
  1658.     for i in [ 2 .. nccl ] do
  1659.       divs[i]:= torso[1] / GcdInt( torso[1],
  1660.                   tbl.classes[i] * Length( families[i] )
  1661.                                               / Phi( tbl.orders[i] ) );
  1662.       if i in cyclics then
  1663.         divs[i]:= Lcm( divs[i], nonfaithful[i] );
  1664.       fi;
  1665.     od;
  1666.     # compute roots and powers:
  1667.     roots:= [];
  1668.     powers:= [];
  1669.     for i in [ 1 .. Length( nonfaithful ) ] do
  1670.       roots[i]:= [];
  1671.       powers[i]:= [];
  1672.     od;
  1673.     if IsBound( tbl.powermap ) then
  1674.       for i in [ 2 .. Length( tbl.powermap ) ] do
  1675.         if IsBound( tbl.powermap[i] ) then
  1676.           for j in [ 1 .. Length( nonfaithful ) ] do
  1677.             if IsInt( tbl.powermap[i][j] ) then
  1678.               AddSet( powers[j], tbl.powermap[i][j] );
  1679.               AddSet( roots[ tbl.powermap[i][j] ], j );
  1680.             fi;
  1681.           od;
  1682.         fi;
  1683.       od;
  1684.     fi;
  1685.     # matrix of constituents:
  1686.     matrix:= [];               # delete impossibles
  1687.     for i in chars do
  1688.       if i[1] <= faithful[1]
  1689.          and Difference( norm_subgrp, KernelChar( i ) ) <> [] then
  1690.         j:= 1;
  1691.         while j <= Length( i )
  1692.               and i[j] >= i[1] - faithful[1] - nonfaithful[j] do
  1693.           j:= j + 1;
  1694.         od;
  1695.         if j > Length( i ) then Add( matrix, i ); fi;
  1696.       fi;
  1697.     od;
  1698.     if matrix = [] then return []; fi;
  1699.     
  1700.     InfoCharTable2( "#I PermCandidatesFaithful : There are ",
  1701.                     Length( matrix ), " possible constituents,\n",
  1702.                     "#I    the number of unknown values is ",
  1703.                     Length( Filtered( [ 1 .. nccl ],
  1704.                             x -> not IsBound( faithful[x] ) ) ),
  1705.                     ";\n",
  1706.                     "#I    now trying to collapse the matrix\n" );
  1707.     
  1708.     #
  1709.     # step 2: Collapse classes which are equal for all possible constituents
  1710.     #
  1711.     matrix:= CollapsedMat( matrix, [ nonfaithful ] );
  1712.     fusion:= matrix.fusion;
  1713.     matrix:= matrix.mat;
  1714.     inverse:= [];
  1715.     for i in [ 1 .. Length( fusion ) ] do
  1716.       if IsBound( inverse[ fusion[i] ] ) then
  1717.         Add( inverse[ fusion[i] ], i );
  1718.       else
  1719.         inverse[ fusion[i] ]:= [ i ];
  1720.       fi;
  1721.     od;
  1722.     #
  1723.     myset:= function( obj )
  1724.     if IsInt( obj ) then return [ obj ]; else return obj; fi; end;
  1725.     #
  1726.     lower:= List( inverse, x -> Maximum( Sublist( lower, x ) ) );
  1727.     upper:= List( inverse, x -> Minimum( Sublist( upper, x ) ) );
  1728.     divs:=  List( inverse, x -> Lcm( Sublist( divs, x ) ) );
  1729.     moduls:= List( inverse, x -> Maximum( Sublist( tbl.centralizers, x ) ) );
  1730.     roots:= List( CompositionMaps( CompositionMaps( fusion, roots ),
  1731.                                                            inverse ), myset );
  1732.     powers:= List( CompositionMaps( CompositionMaps( fusion, powers ),
  1733.                                                            inverse ), myset );
  1734.     classes:= [];
  1735.     for i in [ 1 .. Length( moduls ) ] do classes[i]:= 0; od;
  1736.     for i in [ 1 .. Length( inverse ) ] do
  1737.       for j in inverse[i] do classes[i]:= classes[i] + tbl.classes[j]; od;
  1738.     od;
  1739.     nonfaithsum:= [];
  1740.     for i in [ 1 .. Length( moduls ) ] do nonfaithsum[i]:= 0; od;
  1741.     for i in [ 1 .. Length( inverse ) ] do
  1742.       for j in inverse[i] do
  1743.         nonfaithsum[i]:= nonfaithsum[i] + tbl.classes[j] * nonfaithful[j];
  1744.       od;
  1745.     od;
  1746.     rest:= tbl.order;
  1747.     nccl:= Length( moduls );
  1748.     uniques:= [];
  1749.     collfaithful:= [];
  1750.     for i in [ 1 .. Length( fusion ) ] do
  1751.       if IsBound( faithful[i] ) then
  1752.         if IsBound( collfaithful[ fusion[i] ] ) then
  1753.           if collfaithful[ fusion[i] ] <> faithful[i] then return []; fi;
  1754.         else
  1755.           collfaithful[ fusion[i] ]:= faithful[i];
  1756.           Add( uniques, fusion[i] );
  1757.           rest:= rest - classes[fusion[i]] * ( faithful[i] + nonfaithful[i] );
  1758.           if rest < 0 then return [];  fi;
  1759.         fi;
  1760.       fi;
  1761.     od;
  1762.     faithful:= collfaithful;
  1763.     orig_nonfaithful:= Copy( nonfaithful );
  1764.     nonfaithful:= CompositionMaps( nonfaithful, inverse );
  1765.     # improvement of bounds by use of roots and powers
  1766.     for i in [ 1 .. nccl ] do
  1767.       if IsBound( faithful[i] ) then
  1768.         for j in roots[i] do
  1769.           upper[j]:= Minimum( upper[j],
  1770.                               nonfaithful[i] + faithful[i] - nonfaithful[j] );
  1771.         od;
  1772.         for j in powers[i] do
  1773.           lower[j]:= Maximum( lower[j],
  1774.                               nonfaithful[i] + faithful[i] - nonfaithful[j] );
  1775.         od;
  1776.       fi;
  1777.     od;
  1778.     
  1779.     InfoCharTable2( "#I PermCandidatesFaithful : There are ", nccl,
  1780.                     " families of classes left,\n",
  1781.                     "#I    the number of unknown values is ",
  1782.                     nccl - Length( uniques ), ",\n",
  1783.                     "#I    the numbers of possible values for each class are",
  1784.                     " appropriately\n",
  1785.                     "#I    ",
  1786.                     List( [ 1 .. nccl ],
  1787.                           x -> Int( ( upper[x] - lower[x] ) / divs[x] )+1),
  1788.                     ";\n#I    now eliminating known classes\n" );
  1789.     
  1790.     #
  1791.     # step 3: Eliminate classes for which the values of 'faithful' are known
  1792.     #
  1793.     difference:= [];
  1794.     for i in [ 1 .. Length( moduls ) ] do difference[i]:= 0; od;
  1795.     nonzerocol:= [];
  1796.     for i in [ 1 .. Length( moduls ) ] do nonzerocol[i]:= true; od;
  1797.     possibilities:= [];     # global list of permutation character candidates
  1798.     #
  1799.     # two little functions:
  1800.     #
  1801.     ischaracter:= function( gencharacter )
  1802.       local i, sum, classes, cand;
  1803.       classes:= tbl.classes;
  1804.       cand:= [];
  1805.       for i in [ 1 .. Length( gencharacter ) ] do
  1806.         cand[i]:= gencharacter[i] * classes[i];
  1807.       od;
  1808.       for i in chars do
  1809.         sum:= cand * i;
  1810.         if sum < 0 then return false; fi;
  1811.       od;
  1812.       return true;
  1813.     end;
  1814.     #
  1815.     isnozerorow:= function( row )
  1816.       local i;
  1817.       for i in row do if i <> 0 then return true; fi; od;
  1818.       return false;
  1819.     end;
  1820.     #
  1821.     # and a bigger function:
  1822.     #
  1823.     erase:= function( uniques, nonzerocol, difference, rest, locupp, loclow )
  1824.     # eliminate all unique columns, adapt nonzerocol;
  1825.     # then look if other columns become unique or if a contradiction occurs;
  1826.     # also look at which column the least number of values is left
  1827.     local i, j, extracted, col, row, quot, val, ggt, a, b, k, u, anzahl, elm,
  1828.           firstallowed, step, gencharacter, remain, update, newupdate,
  1829.           c, upp, low, g, st, y, L, number;
  1830.     extracted:= [];
  1831.     while uniques <> [] do
  1832.       for col in uniques do
  1833.         if col < 0 then       # col is zerocol, known from val = moduls[i]
  1834.           col:= -col;
  1835.           difference[ col ]:= ( difference[ col ] + faithful[ col ] )
  1836.                                                         mod moduls[ col ];
  1837.           if difference[ col ] <> 0 then
  1838.             impossible:= true;
  1839.             return extracted;
  1840.           fi;
  1841.         else
  1842.           difference[ col ]:=
  1843.                           ( difference[ col ] + faithful[ col ] )
  1844.                                                         mod moduls[ col ];
  1845.           row:= StepModGauss( matrix, moduls, nonzerocol, col );
  1846.           if row = false then
  1847.             if difference[ col ] <> 0 then
  1848.               impossible:= true;
  1849.               return extracted;
  1850.             fi;
  1851.           else 
  1852.             # delete zero rows:
  1853.             shrink:= [];
  1854.             for i in matrix do
  1855.                if isnozerorow( i ) then Add( shrink, i ); fi;
  1856.             od;
  1857.             matrix:= shrink;
  1858.             #
  1859.             Add( extracted, row );
  1860.             if difference[col] mod row[col] <> 0 then
  1861.               impossible:= true;
  1862.               return extracted;
  1863.             fi;
  1864.             quot:= difference[col] / row[col];
  1865.             for j in [ 1 .. nccl ] do
  1866.               if nonzerocol[j] then
  1867.                 difference[j]:= ( difference[j] - quot * row[j] )
  1868.                                                            mod moduls[j];
  1869.               fi;
  1870.             od;
  1871.           fi;
  1872.         fi;
  1873.         nonzerocol[col]:= false;
  1874.         locupp[ col ]:= faithful[ col ];
  1875.         loclow[ col ]:= faithful[ col ];
  1876.     #   update:= [ col ];
  1877.     #   while update <> [] do
  1878.     #     newupdate:= [];
  1879.     #     for k in update do
  1880.     #       for elm in roots[k] do
  1881.     #         if nonzerocol[ elm ] then
  1882.     #           if locupp[ elm ] >
  1883.     #              locupp[k] + nonfaithful[k] - nonfaithful[ elm ] then
  1884.     #             AddSet( newupdate, elm );
  1885.     #             locupp[ elm ]:= locupp[k] + nonfaithful[k]
  1886.     #                             - nonfaithful[ elm ];
  1887.     #           fi;
  1888.     #         fi;
  1889.     #       od;
  1890.     #     od;
  1891.     #     update:= newupdate;
  1892.     #   od;
  1893.     #   update:= [ col ];
  1894.     #   while update <> [] do
  1895.     #     newupdate:= [];
  1896.     #     for k in update do
  1897.     #       for elm in powers[k] do
  1898.     #         if nonzerocol[ elm ] then
  1899.     #           if loclow[ elm ] < loclow[k]
  1900.     #                          + nonfaithful[k] - nonfaithful[ elm ] then
  1901.     #             AddSet( newupdate, elm );
  1902.     #             loclow[ elm ]:= loclow[k] + nonfaithful[k]
  1903.     #                             - nonfaithful[ elm ];
  1904.     #           fi;
  1905.     #         fi;
  1906.     #       od;
  1907.     #     od;
  1908.     #     update:= newupdate;
  1909.     #   od;
  1910.       od;
  1911.     # now all yet known uniques have been erased, try to find new ones
  1912.       min_number:= "infinity";
  1913.       uniques:= [];
  1914.       for i in [ 1 .. nccl ] do
  1915.         if nonzerocol[i] then
  1916.           val:= moduls[i];
  1917.           for j in matrix do val:= GcdInt( val, j[i] ); od;
  1918.                                              # zerocol iff val = moduls[i]
  1919.           c:= difference[i] mod val;         # now >= 0
  1920.           upp:= Minimum( locupp[i], ( rest[1] - nonfaithsum[i] )/classes[i] );
  1921.           low:= loclow[i];
  1922.           g:= Gcdex( divs[i], val );
  1923.           a:= g.coeff1;
  1924.           b:= g.coeff2;
  1925.           g:= g.gcd;
  1926.           if ( c - nonfaithful[i] ) mod g <> 0 then
  1927.             impossible:= true;
  1928.             return extracted;
  1929.           fi;
  1930.           st:= divs[i] * val / g;
  1931.           y:= - nonfaithful[i] - ( a * divs[i] * ( c - nonfaithful[i] ) ) / g;
  1932.           L:= low + ( ( y - low ) mod st);
  1933.           if upp < L then
  1934.             impossible:= true;
  1935.             return extracted;
  1936.           else
  1937.             number:= Int( ( upp - L ) / st ) + 1;
  1938.             if number = 1 then         # unique
  1939.               faithful[i]:= L;
  1940.               if val = moduls[i] then
  1941.                 Add( uniques, -i );    # no StepModGauss necessary
  1942.               else
  1943.                 Add( uniques, i );
  1944.               fi;
  1945.               rest[1]:= rest[1] - classes[i] * faithful[i] - nonfaithsum[i];
  1946.             elif number < min_number then
  1947.               min_number:= number;
  1948.               step:= st;
  1949.               firstallowed:= L;
  1950.               min_class:= i;
  1951.             fi;
  1952.           fi;
  1953.         fi;
  1954.       od;
  1955.     od;
  1956.     if min_number = "infinity" then
  1957.       if rest[1] = 0 then
  1958.         gencharacter:= Indirected( faithful, fusion ) + orig_nonfaithful;
  1959.         if ischaracter( gencharacter ) and TestPerm1( tbl, gencharacter ) = 0
  1960.            and TestPerm2( tbl, gencharacter ) = 0 then
  1961.           Add( possibilities, gencharacter );
  1962.         fi;
  1963.       fi;
  1964.       impossible:= true;
  1965.     else
  1966.       faithful[ min_class ]:= rec( firstallowed:= firstallowed, # first value
  1967.                                    step:= step,                 # step
  1968.                                    number:= min_number );
  1969.       impossible:= false;
  1970.     fi;
  1971.     return extracted;
  1972.     # impossible = true: calling function will return from backtrack
  1973.     # impossible = false: then min_class < E( 3 ), and faithful[ min_class ]
  1974.     #                 contains the informations for descending at min_class
  1975.     end;
  1976.     #
  1977.     rest:= [ rest ];
  1978.     erase( uniques, nonzerocol, difference, rest, upper, lower );
  1979.     rest:= rest[1];
  1980.     if impossible then return possibilities; fi;
  1981.     
  1982.     InfoCharTable2( "#I PermCandidatesFaithful : A backtrack search",
  1983.                     " will be needed;\n",
  1984.                     "#I    now physically deleting known classes\n" );
  1985.     
  1986.     #
  1987.     # step 4: Delete eliminated columns physically before the backtrack search
  1988.     #
  1989.     remain:= Filtered( [ 1 .. nccl ], x->nonzerocol[x] );
  1990.     for i in [ 1 .. Length( matrix ) ] do
  1991.       matrix[i]:= Sublist( matrix[i], remain );
  1992.     od;
  1993.     difference:=    Sublist( difference, remain );
  1994.     divs:=          Sublist( divs, remain );
  1995.     nonzerocol:=    Sublist( nonzerocol, remain );
  1996.     moduls:=        Sublist( moduls, remain );
  1997.     classes:=       Sublist( classes, remain );
  1998.     nonfaithsum:=   Sublist( nonfaithsum, remain );
  1999.     nonfaithful:=   Sublist( nonfaithful, remain );
  2000.     upper:=         Sublist( upper, remain );
  2001.     lower:=         Sublist( lower, remain );
  2002.     matrix:= ModGauss( matrix, moduls );
  2003.     ncha:= Length( matrix );
  2004.     pos:= 1;
  2005.     fusionperm:= [];
  2006.     for i in [ 1 .. nccl ] do
  2007.       if i in remain then
  2008.         fusionperm[ i ]:= pos;
  2009.         pos:= pos + 1;
  2010.       fi;
  2011.     od;
  2012.     for i in Difference( [ 1 .. nccl ], remain ) do
  2013.       fusionperm[i]:= pos;
  2014.       pos:= pos + 1;
  2015.     od;  
  2016.     min_class:= fusionperm[ min_class ];
  2017.     newfaithful:= [];
  2018.     for i in [ 1 .. Length( faithful ) ] do
  2019.       if IsBound( faithful[i] ) then
  2020.         newfaithful[ fusionperm[i] ]:= faithful[i];
  2021.       fi;
  2022.     od;
  2023.     faithful:= newfaithful;
  2024.     fusion:= CompositionMaps( fusionperm, fusion );
  2025.     for i in remain do
  2026.       roots[ fusionperm[i] ]:= CompositionMaps( fusionperm,
  2027.                                      Intersection( roots[i], remain ) );
  2028.       powers[ fusionperm[i] ]:= CompositionMaps( fusionperm,
  2029.                                      Intersection( powers[i], remain ) );
  2030.     od;
  2031.     nccl:= Length( nonzerocol );
  2032.     
  2033.     InfoCharTable2( "#I PermCandidatesFaithful:",
  2034.                     " The number of unknown values is ", nccl, ";\n",
  2035.                     "#I    the numbers of possible values for each class are",
  2036.                     " appropriately\n#I    ",
  2037.                     List( [ 1 .. nccl ],
  2038.                           x -> Int( ( upper[x] - lower[x] ) / divs[x]+1)),
  2039.                     "\n#I    now beginning the backtrack search\n" );
  2040.     
  2041.     #
  2042.     # step 5: The backtrack search
  2043.     #
  2044.     evaluate:=
  2045.           function(difference,rest,nonzerocol,unique,local_upper,local_lower)
  2046.     local i, j, col, val, row, quot, extracted, step, first, descendclass;
  2047.     rest:= [ rest ];
  2048.     extracted:= erase( [ unique ], nonzerocol, difference, rest, local_upper,
  2049.                        local_lower );
  2050.     rest:= rest[1];
  2051.     if impossible then return extracted; fi;
  2052.     descendclass:= min_class;
  2053.     step:= faithful[ descendclass ].step;
  2054.     first:= faithful[ descendclass ].firstallowed;
  2055.     rest:= rest + ( step - first ) * classes[ descendclass ]
  2056.                 - nonfaithsum[ descendclass ];
  2057.     for i in [ 1 .. min_number ] do
  2058.       faithful[ descendclass ]:= first + (i-1) * step;
  2059.       rest:= rest - step * classes[ descendclass ];
  2060.       oldrows:= evaluate( Copy(difference), rest, Copy( nonzerocol ),
  2061.                           descendclass, Copy( local_upper ),
  2062.                           Copy( local_lower ) );
  2063.       Append( matrix, oldrows );
  2064.       if Length( matrix ) > ( 3 * ncha ) / 2 then
  2065.         newmatrix:= [];
  2066.         for j in [ 1 .. Length( matrix[1] ) ] do
  2067.           if nonzerocol[j] then
  2068.             row:= StepModGauss( matrix, moduls, nonzerocol, j );
  2069.             if row <> false then Add( newmatrix, row ); fi;
  2070.           fi;
  2071.         od;
  2072.         matrix:= newmatrix;
  2073.       fi;
  2074.     od;
  2075.     return extracted;
  2076.     end;
  2077.     
  2078.     #
  2079.     
  2080.     step:= faithful[min_class].step;
  2081.     first:= faithful[min_class].firstallowed;
  2082.     descendclass:= min_class;
  2083.     rest:= rest + ( step - first ) * classes[ descendclass ]
  2084.                 - nonfaithsum[ descendclass ];
  2085.     for i in [ 1 .. min_number ] do
  2086.       faithful[ descendclass ]:= first + (i-1) * step;
  2087.       rest:= rest - step * classes[ descendclass ];
  2088.       oldrows:= evaluate( Copy(difference), rest, Copy( nonzerocol ),
  2089.                 descendclass, Copy( upper ), Copy( lower ) );
  2090.       Append( matrix, oldrows );
  2091.       if Length( matrix ) > ( 3 * ncha ) / 2 then
  2092.         newmatrix:= [];
  2093.         for j in [ 1 .. Length( matrix[1] ) ] do
  2094.           if nonzerocol[j] then
  2095.             row:= StepModGauss( matrix, moduls, nonzerocol, j );
  2096.             if row <> false then Add( newmatrix, row ); fi;
  2097.           fi;
  2098.         od;
  2099.         matrix:= newmatrix;
  2100.       fi;
  2101.     od;
  2102.     return possibilities;
  2103.     end;
  2104.  
  2105.  
  2106. #############################################################################
  2107. ##
  2108. #F  PermChars( <tbl> [, <arec>] ) . . . . . . . . . . 06 Aug 91
  2109. ##
  2110. ##  Find all Candidates for Permutation Characters of the group with
  2111. ##  Character table <tbl> by use of an algorithm specified by choice of
  2112. ##  the arguments.
  2113. ##
  2114. PermChars := function(arg)
  2115.  
  2116.    local tbl, arec, fields;
  2117.  
  2118.    if Length(arg) = 1 then
  2119.       tbl:= arg[1];
  2120.       arec:= rec();
  2121.    elif Length(arg) = 2 then
  2122.       tbl:= arg[1];
  2123.       if IsRec(arg[2]) then
  2124.         arec:= arg[2];
  2125.       else
  2126.         arec:= rec(degree:= arg[2]);
  2127.       fi;
  2128.    else
  2129.  
  2130.       Error( "usage: PermChars(<tbl>), PermChars(<tbl>, <degree>) or\n",
  2131.              "       PermChars(<tbl>, <arec>)" );
  2132.  
  2133.    fi;
  2134.  
  2135.    fields:= RecFields(arec);
  2136.    if IsSubset(fields, ["degree"]) and IsInt(arec.degree) then
  2137.       return PermComb(tbl, arec);
  2138.    elif IsSubset(fields, ["normalsubgrp", "nonfaithful", 
  2139.                     "chars", "lower", "upper", "torso"]) then
  2140.       return PermCandidatesFaithful(tbl, arec.chars, arec.normalsubgrp,
  2141.             arec.nonfaithful, arec.upper, arec.lower, arec.torso);
  2142.    elif IsSubset(fields, ["torso", "chars"]) then
  2143.       return PermCandidates(tbl, arec.chars, arec.torso);
  2144.    else
  2145.       return Permut(tbl, arec);
  2146.    fi;
  2147. end;
  2148.  
  2149.  
  2150. #############################################################################
  2151. ##
  2152. #F  PermCharInfo( <tbl>, <permchars> )
  2153. ##
  2154. ##  Let <tbl> be the character table of the group $G$, and 'permchars' the
  2155. ##  permutation character $(1_U)^G$ for a subgroup $U$ of $G$, or a list
  2156. ##  of such permutation characters.
  2157. ##  'PermCharInfo' returns a record with components
  2158. ##
  2159. ##  'contained':\\
  2160. ##    a list containing for each character in <permchars> a list containing
  2161. ##    at position <i> the number of elements of $U$ that are contained in
  2162. ##    class <i> of <tbl>, this is equal to
  2163. ##    $'permchar[<i>]' \|U\| / 'tbl.centralizers[<i>]',
  2164. ##    
  2165. ##  'bound':\\
  2166. ##    a list containing for each character in <permchars> a list containing
  2167. ##    at position <i> the class length in $U$ of an element in class <i>
  2168. ##    of <tbl> must be a multiple of
  2169. ##    $'bound[<i>]' = \|U\| / \gcd( \|U\|, <tbl>.centralizers[<i>] )$,
  2170. ##
  2171. ##  'display':\\
  2172. ##    record that can be used as second argument of 'DisplayCharTable'
  2173. ##    to display each permutation character in <permchars> and the
  2174. ##    corresponding components 'contained' and 'bound',
  2175. ##    for the classes where at least one permutation character is nonzero,
  2176. ##
  2177. ##  'ATLAS':\\
  2178. ##    list of strings containing the decomposition of the permutation
  2179. ##    characters into '<tbl>.irreducibles' in {\ATLAS} notation.
  2180. ##
  2181. PermCharInfo := function( tbl, permchars )
  2182.     local i, j, k, order, cont, bound, alp, degreeset, irreds, chi,
  2183.           ATLAS, ATL, error, scprs, cont1, bound1, char, chars;
  2184.  
  2185.     cont := [];
  2186.     bound:= [];
  2187.     ATL:= [];
  2188.     chars:= [];
  2189.     if not IsList( permchars[1] ) then permchars:= [ permchars ]; fi;
  2190.  
  2191.     for char in permchars do
  2192.       cont1:= [];
  2193.       bound1:= [];
  2194.       order:= tbl.order / char[1];
  2195.       for i in [ 1 .. Length( char ) ] do
  2196.         cont1[i] := char[i] * order / tbl.centralizers[i];
  2197.         bound1[i]:= order / GcdInt( order, tbl.centralizers[i] );
  2198.       od;
  2199.       Add( cont, cont1 );
  2200.       Add( bound, bound1 );
  2201.       Append( chars, [ char, cont1, bound1 ] );
  2202.     od;
  2203.  
  2204.     if IsBound( tbl.irreducibles ) then
  2205.  
  2206.       # compute the 'ATLAS' component
  2207.       alp:= [ "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k",
  2208.               "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v",
  2209.               "w", "x", "y", "z" ];
  2210.       degreeset:= Set( List( tbl.irreducibles, x -> x[1] ) );
  2211.  
  2212.       # 'irreds[i]' contains all irreducibles of the 'i'--th degree
  2213.       irreds:= List( degreeset, x -> [] );
  2214.       for chi in tbl.irreducibles do
  2215.         Add( irreds[ Position( degreeset, chi[1] ) ], chi );
  2216.       od;
  2217.  
  2218.       # extend the alphabet if necessary
  2219.       while Length( alp ) < Maximum( List( irreds, Length ) ) do
  2220.         alp:= Concatenation( alp,
  2221.                List( alp, x -> ConcatenationString( "(", x, "')" ) ) );
  2222.       od;
  2223.  
  2224.       ATLAS:= [];
  2225.       for char in permchars do
  2226.  
  2227.         ATL:= "";
  2228.         error:= false;
  2229.         for i in irreds do
  2230.           scprs:= List( i, x -> ScalarProduct( tbl, char, x ) );
  2231.           if ForAny( scprs, x -> x < 0 ) then
  2232.             scprs:= Filtered( [ 1 .. Length( scprs ) ], x -> scprs[x] <  0 );
  2233.             Print( "#E PermCharInfo: negative scalar product(s) with X",
  2234.                    scprs, "\n" );
  2235.             error:= true;
  2236.           elif ForAny( scprs, x -> x > 0 ) then
  2237.             if ATL <> "" then
  2238.               ATL:= ConcatenationString( ATL, "+" );
  2239.             fi;
  2240.             ATL:= ConcatenationString( ATL, String( i[1][1] ) );
  2241.             for j in [ 1 .. Length( scprs ) ] do
  2242.               for k in [ 1 .. scprs[j] ] do
  2243.                 ATL:= ConcatenationString( ATL, alp[j] );
  2244.               od;
  2245.             od;
  2246.           fi;
  2247.         od;
  2248.         if error then ATL:= "Error"; fi;
  2249.         Add( ATLAS, ATL );
  2250.       od;
  2251.     else
  2252.       ATLAS:= "error, no irreducibles bound";
  2253.     fi;
  2254.  
  2255.     return rec( contained:= cont, bound:= bound,
  2256.                 display:= rec( classes:= Filtered([1..Length(tbl.classes)],
  2257.                                   x -> ForAny( permchars, y -> y[x]<>0 ) ),
  2258.                                chars:= chars,
  2259.                                letter:= "I"                               ),
  2260.                 ATLAS:= ATLAS );
  2261.     end; 
  2262.  
  2263.