chap6.txt

  
  6 New GAP Objects and Utility Functions Provided by the AtlasRep Package
  
  This  chapter  describes  GAP objects and functions that are provided by the
  AtlasRep package but that might be of general interest.
  
  The  new objects are straight line decisions (see Section 6.1) and black box
  programs (see Section 6.2).
  
  The  new functions are concerned with representations of minimal degree, see
  Section 6.3.
  
  
  6.1 Straight Line Decisions
  
  Straight   line  decisions  are  similar  to  straight  line  programs  (see
  Section 'Reference:  Straight  Line  Programs')  but return true or false. A
  straight  line  decisions  checks  a  property  for its inputs. An important
  example  is  to  check whether a given list of group generators is in fact a
  list of standard generators (cf. Section3.3) for this group.
  
  A  straight  line  decision in GAP is represented by an object in the filter
  IsStraightLineDecision (6.1-1) that stores a list of lines each of which has
  one of the following three forms.
  
  1   a nonempty dense list l of integers,
  
  2   a  pair  [  l,  i  ]  where l is a list of form 1. and i is a positive
        integer,
  
  3   a list ["Order", i, n ] where i and n are positive integers.
  
  The first two forms have the same meaning as for straight line programs (see
  Section 'Reference:  Straight  Line  Programs'), the last form means a check
  whether the element stored at the label i-th has the order n.
  
  For  the  meaning  of  the  list  of lines, see ResultOfStraightLineDecision
  (6.1-6).
  
  Straight  line  decisions  can  be  constructed  using  StraightLineDecision
  (6.1-5),    defining    attributes   for   straight   line   decisions   are
  NrInputsOfStraightLineDecision   (6.1-3)   and   LinesOfStraightLineDecision
  (6.1-2),     an     operation     for    straight    line    decisions    is
  ResultOfStraightLineDecision (6.1-6).
  
  Special  methods applicable to straight line decisions are installed for the
  operations  Display (Reference: Display), IsInternallyConsistent (Reference:
  IsInternallyConsistent),   PrintObj   (Reference:   PrintObj),  and  ViewObj
  (Reference: ViewObj).
  
  For  a straight line decision prog, the default Display (Reference: Display)
  method  prints  the  interpretation  of prog as a sequence of assignments of
  associative  words  and  of order checks; a record with components gensnames
  (with  value  a  list  of strings) and listname (a string) may be entered as
  second  argument  of  Display (Reference: Display), in this case these names
  are  used,  the  default  for  gensnames is [ g1, g2, ... ], the default for
  listname is r.
  
  6.1-1 IsStraightLineDecision
  
  IsStraightLineDecision( obj )  Category
  
  Each    straight    line    decision    in    GAP   lies   in   the   filter
  IsStraightLineDecision.
  
  6.1-2 LinesOfStraightLineDecision
  
  LinesOfStraightLineDecision( prog )  operation
  Returns:  the list of lines that define the straight line decision.
  
  This   defining   attribute   for  the  straight  line  decision  prog  (see
  IsStraightLineDecision  (6.1-1))  corresponds  to LinesOfStraightLineProgram
  (Reference: LinesOfStraightLineProgram) for straight line programs.
  
    Example  
    gap> dec:= StraightLineDecision( [ [ [ 1, 1, 2, 1 ], 3 ],
    > [ "Order", 1, 2 ], [ "Order", 2, 3 ], [ "Order", 3, 5 ] ] );
    <straight line decision>
    gap> LinesOfStraightLineDecision( dec );
    [ [ [ 1, 1, 2, 1 ], 3 ], [ "Order", 1, 2 ], [ "Order", 2, 3 ], 
      [ "Order", 3, 5 ] ]
  
  
  6.1-3 NrInputsOfStraightLineDecision
  
  NrInputsOfStraightLineDecision( prog )  operation
  Returns:  the number of inputs required for the straight line decision.
  
  This   defining   attribute   corresponds  to  NrInputsOfStraightLineProgram
  (Reference: NrInputsOfStraightLineProgram).
  
    Example  
    gap> NrInputsOfStraightLineDecision( dec );
    2
  
  
  6.1-4 ScanStraightLineDecision
  
  ScanStraightLineDecision( string )  function
  Returns:  a record containing the straight line decision, or fail.
  
  Let  string  be  a string that encodes a straight line decision in the sense
  that  it  consists  of the lines listed for ScanStraightLineProgram (7.4-1),
  except  that  oup  lines are not allowed, and instead lines of the following
  form may occur.
  
  chor a b
        means  that  it is checked whether the order of the element at label a
        is b.
  
  ScanStraightLineDecision  returns  a  record  containing as the value of its
  component   program   the   corresponding   GAP   straight   line   decision
  (see IsStraightLineDecision  (6.1-1))  if  the  input  string  satisfies the
  syntax  rules  stated above, and returns fail otherwise. In the latter case,
  information  about the first corrupted line of the program is printed if the
  info level of InfoCMeatAxe (7.1-2) is at least 1.
  
    Example  
    gap> str:= "inp 2\nchor 1 2\nchor 2 3\nmu 1 2 3\nchor 3 5";;
    gap> prg:= ScanStraightLineDecision( str );
    rec( program := <straight line decision> )
    gap> prg:= prg.program;;
    gap> Display( prg );
    # input:
    r:= [ g1, g2 ];
    # program:
    if Order( r[1] ) <> 2 then  return false;  fi;
    if Order( r[2] ) <> 3 then  return false;  fi;
    r[3]:= r[1]*r[2];
    if Order( r[3] ) <> 5 then  return false;  fi;
    # return value:
    true
  
  
  6.1-5 StraightLineDecision
  
  StraightLineDecision( lines[, nrgens] )  function
  StraightLineDecisionNC( lines[, nrgens] )  function
  Returns:  the straight line decision given by the list of lines.
  
  Let  lines  be  a list of lists that defines a unique straight line decision
  (see IsStraightLineDecision  (6.1-1));  in  this  case  StraightLineDecision
  returns this program, otherwise an error is signalled. The optional argument
  nrgens specifies the number of input generators of the program; if a list of
  integers  (a  line  of form 1. in the definition above) occurs in lines then
  this  number  is  not determined by lines and therefore must be specified by
  the argument nrgens; if not then StraightLineDecision returns fail.
  
  StraightLineDecisionNC  does  the  same as StraightLineDecision, except that
  the internal consistency of the program is not checked.
  
  6.1-6 ResultOfStraightLineDecision
  
  ResultOfStraightLineDecision( prog, gens[, orderfunc] )  operation
  Returns:  true if all checks succeed, otherwise false.
  
  ResultOfStraightLineDecision    evaluates   the   straight   line   decision
  (see IsStraightLineDecision  (6.1-1)) prog at the group elements in the list
  gens.
  
  The  function for computing the order of a group element can be given as the
  optional  argument orderfunc. For example, this may be a function that gives
  up  at  a  certain  limit if one has to be aware of extremely huge orders in
  failure cases.
  
  The  result  of  a straight line decision with lines p_1, p_2, ..., p_k when
  applied to gens is defined as follows.
  
  (a)
        First  a  list  r of intermediate values is initialized with a shallow
        copy of gens.
  
  (b)
        For  i  ≤ k, before the i-th step, let r be of length n. If p_i is the
        external  representation  of  an  associative  word  in  the  first  n
        generators  then the image of this word under the homomorphism that is
        given  by  mapping r to these first n generators is added to r. If p_i
        is  a  pair [ l, j ], for a list l, then the same element is computed,
        but  instead  of being added to r, it replaces the j-th entry of r. If
        p_i  is a triple ["Order", i, n ] then it is checked whether the order
        of r[i] is n; if not then false is returned immediately.
  
  (c)
        If  all k lines have been processed and no order check has failed then
        true is returned.
  
  Here are some examples.
  
    Example  
    gap> dec:= StraightLineDecision( [ ], 1 );
    <straight line decision>
    gap> ResultOfStraightLineDecision( dec, [ () ] );
    true
  
  
  The  above  straight  line  decision  dec returns true –for any input of the
  right length.
  
    Example  
    gap> dec:= StraightLineDecision( [ [ [ 1, 1, 2, 1 ], 3 ],
    >       [ "Order", 1, 2 ], [ "Order", 2, 3 ], [ "Order", 3, 5 ] ] );
    <straight line decision>
    gap> LinesOfStraightLineDecision( dec );
    [ [ [ 1, 1, 2, 1 ], 3 ], [ "Order", 1, 2 ], [ "Order", 2, 3 ], 
      [ "Order", 3, 5 ] ]
    gap> ResultOfStraightLineDecision( dec, [ (), () ] );
    false
    gap> ResultOfStraightLineDecision( dec, [ (1,2)(3,4), (1,4,5) ] );
    true
  
  
  The  above  straight  line  decision admits two inputs; it tests whether the
  orders of the inputs are 2 and 3, and the order of their product is 5.
  
  
  6.1-7 Semi-Presentations and Presentations
  
  We  can  associate  a  finitely  presented group F / R to each straight line
  decision  dec,  say, as follows. The free generators of the free group F are
  in  bijection  with  the inputs, and the defining relators generating R as a
  normal  subgroup  of F are given by those words w^k for which dec contains a
  check whether the order of w equals k.
  
  So  if  dec  returns  true  for  the  input list [ g_1, g_2, ..., g_n ] then
  mapping the free generators of F to the inputs defines an epimorphism Φ from
  F  to  the  group  G, say, that is generated by these inputs, such that R is
  contained in the kernel of Φ.
  
  (Note  that  satisfying  dec  is  a  stronger  property  than  satisfying  a
  presentation.  For  example, ⟨ x ∣ x^2 = x^3 = 1 ⟩ is a presentation for the
  trivial  group, but the straight line decision that checks whether the order
  of x is both 2 and 3 clearly always returns false.)
  
  The  ATLAS  of  Group  Representations  contains  the following two kinds of
  straight line decisions.
  
      A  presentation  is a straight line decision dec that is defined for a
        set  of  standard generators of a group G and that returns true if and
        only  if  the  list  of  inputs is in fact a sequence of such standard
        generators  for G. In other words, the relators derived from the order
        checks  in  the  way  described above are defining relators for G, and
        moreover these relators are words in terms of standard generators. (In
        particular  the  kernel  of  the  map  Φ equals R whenever dec returns
        true.)
  
      A  semi-presentation  is  a straight line decision dec that is defined
        for  a  set  of standard generators of a group G and that returns true
        for a list of inputs that is known to generate a group isomorphic with
        G  if  and  only  if  these inputs form in fact a sequence of standard
        generators  for G. In other words, the relators derived from the order
        checks  in  the  way  described  above  are  not  necessarily defining
        relators for G, but if we assume that the g_i generate G then they are
        standard  generators. (In particular, F / R may be a larger group than
        G  but  in  this  case  Φ  maps  the  free generators of F to standard
        generators of G.)
  
        More about semi-presentations can be found in [NW05].
  
  Available    presentations    and    semi-presentations    are   listed   by
  DisplayAtlasInfo  (3.5-1),  they  can  be accessed via AtlasProgram (3.5-3).
  (Clearly   each   presentation   is   also   a   semi-presentation.   So   a
  semi-presentation  for  some  standard  generators of a group is regarded as
  available  whenever  a  presentation  for these standard generators and this
  group is available.)
  
  Note   that  different  groups  can  have  the  same  semi-presentation.  We
  illustrate  this  with  an  example  that is mentioned in [NW05]. The groups
  L_2(7)  ≅  L_3(2) and L_2(8) are generated by elements of the orders 2 and 3
  such that their product has order 7, and no further conditions are necessary
  to define standard generators.
  
    Example  
    gap> check:= AtlasProgram( "L2(8)", "check" );
    rec( groupname := "L2(8)", 
      identifier := [ "L2(8)", "L28G1-check1", 1, 1 ], 
      program := <straight line decision>, standardization := 1 )
    gap> gens:= AtlasGenerators( "L2(8)", 1 );
    rec( charactername := "1a+8a", 
      generators := [ (1,2)(3,4)(6,7)(8,9), (1,3,2)(4,5,6)(7,8,9) ], 
      groupname := "L2(8)", id := "", 
      identifier := [ "L2(8)", [ "L28G1-p9B0.m1", "L28G1-p9B0.m2" ], 1, 9 
         ], isPrimitive := true, maxnr := 1, p := 9, rankAction := 2, 
      repname := "L28G1-p9B0", repnr := 1, size := 504, 
      stabilizer := "2^3:7", standardization := 1, transitivity := 3, 
      type := "perm" )
    gap> ResultOfStraightLineDecision( check.program, gens.generators );
    true
    gap> gens:= AtlasGenerators( "L3(2)", 1 );
    rec( generators := [ (2,4)(3,5), (1,2,3)(5,6,7) ], 
      groupname := "L3(2)", id := "a", 
      identifier := [ "L3(2)", [ "L27G1-p7aB0.m1", "L27G1-p7aB0.m2" ], 1, 
          7 ], isPrimitive := true, maxnr := 1, p := 7, rankAction := 2, 
      repname := "L27G1-p7aB0", repnr := 1, size := 168, 
      stabilizer := "S4", standardization := 1, transitivity := 2, 
      type := "perm" )
    gap> ResultOfStraightLineDecision( check.program, gens.generators );
    true
  
  
  6.1-8 AsStraightLineDecision
  
  AsStraightLineDecision( bbox )  attribute
  Returns:  an  equivalent  straight  line  decision  for  the given black box
            program, or fail.
  
  For    a    black    box   program   (see   IsBBoxProgram   (6.2-1))   bbox,
  AsStraightLineDecision    returns    a    straight    line   decision   (see
  IsStraightLineDecision  (6.1-1))  with the same output as bbox, in the sense
  of  AsBBoxProgram (6.2-5), if such a straight line decision exists, and fail
  otherwise.
  
    Example  
    gap> lines:= [ [ "Order", 1, 2 ], [ "Order", 2, 3 ],
    >              [ [ 1, 1, 2, 1 ], 3 ], [ "Order", 3, 5 ] ];;
    gap> dec:= StraightLineDecision( lines, 2 );
    <straight line decision>
    gap> bboxdec:= AsBBoxProgram( dec );
    <black box program>
    gap> asdec:= AsStraightLineDecision( bboxdec );
    <straight line decision>
    gap> LinesOfStraightLineDecision( asdec );
    [ [ "Order", 1, 2 ], [ "Order", 2, 3 ], [ [ 1, 1, 2, 1 ], 3 ], 
      [ "Order", 3, 5 ] ]
  
  
  6.1-9 StraightLineProgramFromStraightLineDecision
  
  StraightLineProgramFromStraightLineDecision( dec )  operation
  Returns:  the  straight  line  program associated to the given straight line
            decision.
  
  For  a  straight  line  decision  dec  (see  IsStraightLineDecision (6.1-1),
  StraightLineProgramFromStraightLineDecision   returns   the   straight  line
  program   (see   IsStraightLineProgram   (Reference:  IsStraightLineProgram)
  obtained  by  replacing  each  line of type 3. (i.e, each order check) by an
  assignment of the power in question to a new slot, and by declaring the list
  of these elements as the return value.
  
  This  means that the return value describes exactly the defining relators of
  the  presentation  that  is  associated  to  the straight line decision, see
  6.1-7.
  
  For  example,  one  can  use the return value for printing the relators with
  StringOfResultOfStraightLineProgram                              (Reference:
  StringOfResultOfStraightLineProgram),  or  for  explicitly  constructing the
  relators   as   words   in   terms   of   free   generators,   by   applying
  ResultOfStraightLineProgram  (Reference: ResultOfStraightLineProgram) to the
  program and to these generators.
  
    Example  
    gap> dec:= StraightLineDecision( [ [ [ 1, 1, 2, 1 ], 3 ],
    > [ "Order", 1, 2 ], [ "Order", 2, 3 ], [ "Order", 3, 5 ] ] );
    <straight line decision>
    gap> prog:= StraightLineProgramFromStraightLineDecision( dec );
    <straight line program>
    gap> Display( prog );
    # input:
    r:= [ g1, g2 ];
    # program:
    r[3]:= r[1]*r[2];
    r[4]:= r[1]^2;
    r[5]:= r[2]^3;
    r[6]:= r[3]^5;
    # return values:
    [ r[4], r[5], r[6] ]
    gap> StringOfResultOfStraightLineProgram( prog, [ "a", "b" ] );
    "[ a^2, b^3, (ab)^5 ]"
    gap> gens:= GeneratorsOfGroup( FreeGroup( "a", "b" ) );
    [ a, b ]
    gap> ResultOfStraightLineProgram( prog, gens );
    [ a^2, b^3, (a*b)^5 ]
  
  
  
  6.2 Black Box Programs
  
  Black  box  programs  formalize the idea that one takes some group elements,
  forms  arithmetic  expressions  in  terms of them, tests properties of these
  expressions,  executes  conditional  statements  (including jumps inside the
  program)  depending  on  the  results of these tests, and eventually returns
  some result.
  
  A specification of the language can be found in [Nic06], see also
  
  http://brauer.maths.qmul.ac.uk/Atlas/info/blackbox.html.
  
  The  inputs  of  a black box program may be explicit group elements, and the
  program  may  also  ask  for random elements from a given group. The program
  steps  form  products,  inverses,  conjugates,  commutators,  etc.  of known
  elements,  tests  concern essentially the orders of elements, and the result
  is a list of group elements or true or false or fail.
  
  Examples that can be modeled by black box programs are
  
  straight line programs,
        which  require  a  fixed  number of input elements and form arithmetic
        expressions  of  elements  but  do  not  use  random  elements, tests,
        conditional statements and jumps; the return value is always a list of
        elements; these programs are described in Section 'Reference: Straight
        Line Programs'.
  
  straight line decisions,
        which  differ  from straight line programs only in the sense that also
        order  tests  are admissible, and that the return value is true if all
        these  tests  are  satisfied, and false as soon as the first such test
        fails; they are described in Section 6.1.
  
  scripts for finding standard generators,
        which take a group and a function to generate a random element in this
        group  but  no  explicit input elements, admit all control structures,
        and  return  either  a  list  of  standard  generators  or  fail;  see
        ResultOfBBoxProgram (6.2-4) for examples.
  
  In  the  case of general black box programs, currently GAP provides only the
  possibility  to read an existing program via ScanBBoxProgram (6.2-2), and to
  run  the  program  using  RunBBoxProgram (6.2-3). It is not our aim to write
  such programs in GAP.
  
  The  special  case of the find scripts mentioned above is also admissible as
  an  argument of ResultOfBBoxProgram (6.2-4), which returns either the set of
  generators or fail.
  
  Contrary  to  the  general  situation, more support is provided for straight
  line  programs  and  straight line decisions in GAP, see Section 'Reference:
  Straight  Line  Programs'  for  functions  that  manipulate  them  (compose,
  restrict etc.).
  
  The   functions  AsStraightLineProgram  (6.2-6)  and  AsStraightLineDecision
  (6.1-8)  can  be used to transform a general black box program object into a
  straight line program or a straight line decision if this is possible.
  
  Conversely,  one  can  create an equivalent general black box program from a
  straight  line  program  or from a straight line decision with AsBBoxProgram
  (6.2-5).
  
  (Computing a straight line program related to a given straight line decision
  is  supported  in  the  sense of StraightLineProgramFromStraightLineDecision
  (6.1-9).)
  
  Note that none of these three kinds of objects is a special case of another:
  Running  a  black  box  program with RunBBoxProgram (6.2-3) yields a record,
  running a straight line program with ResultOfStraightLineProgram (Reference:
  ResultOfStraightLineProgram)  yields  a  list  of  elements,  and  running a
  straight line decision with ResultOfStraightLineDecision (6.1-6) yields true
  or false.
  
  6.2-1 IsBBoxProgram
  
  IsBBoxProgram( obj )  Category
  
  Each black box program in GAP lies in the filter IsBBoxProgram.
  
  6.2-2 ScanBBoxProgram
  
  ScanBBoxProgram( string )  function
  Returns:  a  record  containing  the  black box program encoded by the input
            string, or fail.
  
  For  a  string  string  that describes a black box program, e.g., the return
  value  of  StringFile  (GAPDoc:  StringFile),  ScanBBoxProgram computes this
  black  box  program. If this is successful then the return value is a record
  containing  as  the  value  of  its  component program the corresponding GAP
  object that represents the program, otherwise fail is returned.
  
  As  the  first  example, we construct a black box program that tries to find
  standard generators for the alternating group A_5; these standard generators
  are  any  pair  of  elements  of the orders 2 and 3, respectively, such that
  their product has order 5.
  
    Example  
    gap> findstr:= "\
    >   set V 0\n\
    > lbl START1\n\
    >   rand 1\n\
    >   ord 1 A\n\
    >   incr V\n\
    >   if V gt 100 then timeout\n\
    >   if A notin 1 2 3 5 then fail\n\
    >   if A noteq 2 then jmp START1\n\
    > lbl START2\n\
    >   rand 2\n\
    >   ord 2 B\n\
    >   incr V\n\
    >   if V gt 100 then timeout\n\
    >   if B notin 1 2 3 5 then fail\n\
    >   if B noteq 3 then jmp START2\n\
    >   # The elements 1 and 2 have the orders 2 and 3, respectively.\n\
    >   set X 0\n\
    > lbl CONJ\n\
    >   incr X\n\
    >   if X gt 100 then timeout\n\
    >   rand 3\n\
    >   cjr 2 3\n\
    >   mu 1 2 4   # ab\n\
    >   ord 4 C\n\
    >   if C notin 2 3 5 then fail\n\
    >   if C noteq 5 then jmp CONJ\n\
    >   oup 2 1 2";;
    gap> find:= ScanBBoxProgram( findstr );
    rec( program := <black box program> )
  
  
  The second example is a black box program that checks whether its two inputs
  are standard generators for A_5.
  
    Example  
    gap> checkstr:= "\
    > chor 1 2\n\
    > chor 2 3\n\
    > mu 1 2 3\n\
    > chor 3 5";;
    gap> check:= ScanBBoxProgram( checkstr );
    rec( program := <black box program> )
  
  
  6.2-3 RunBBoxProgram
  
  RunBBoxProgram( prog, G, input, options )  function
  Returns:  a  record  describing the result and the statistics of running the
            black box program prog, or fail, or the string "timeout".
  
  For a black box program prog, a group G, a list input of group elements, and
  a record options, RunBBoxProgram applies prog to input, where G is used only
  to compute random elements.
  
  The  return value is fail if a syntax error or an explicit fail statement is
  reached  at  runtime,  and  the  string  "timeout" if a timeout statement is
  reached.  (The  latter  might  mean  that  the random choices were unlucky.)
  Otherwise a record with the following components is returned.
  
  gens
        a list of group elements, bound if an oup statement was reached,
  
  result
        true  if  a  true  statement  was  reached,  false  if  either a false
        statement or a failed order check was reached,
  
  The  other  components serve as statistical information about the numbers of
  the  various  operations (multiply, invert, power, order, random, conjugate,
  conjugateinplace, commutator), and the runtime in milliseconds (timetaken).
  
  The following components of options are supported.
  
  randomfunction
        the  function  called  with  argument  G  in order to compute a random
        element of G (default PseudoRandom (Reference: PseudoRandom))
  
  orderfunction
        the  function  for  computing  element  orders  (the  default is Order
        (Reference: Order)),
  
  quiet
        if true then ignore echo statements (default false),
  
  verbose
        if  true  then  print  information  about  the  line that is currently
        processed, and about order checks (default false),
  
  allowbreaks
        if  true  then call Error (Reference: Error) when a break statement is
        reached, otherwise ignore break statements (default true).
  
  As  an example, we run the black box programs constructed in the example for
  ScanBBoxProgram (6.2-2).
  
    Example  
    gap> g:= AlternatingGroup( 5 );;
    gap> res:= RunBBoxProgram( find.program, g, [], rec() );;
    gap> IsBound( res.gens );  IsBound( res.result );
    true
    false
    gap> List( res.gens, Order );
    [ 2, 3 ]
    gap> Order( Product( res.gens ) );
    5
    gap> res:= RunBBoxProgram( check.program, "dummy", res.gens, rec() );;
    gap> IsBound( res.gens );  IsBound( res.result );
    false
    true
    gap> res.result;
    true
    gap> othergens:= GeneratorsOfGroup( g );;
    gap> res:= RunBBoxProgram( check.program, "dummy", othergens, rec() );;
    gap> res.result;
    false
  
  
  6.2-4 ResultOfBBoxProgram
  
  ResultOfBBoxProgram( prog, G )  function
  Returns:  a  list  of  group  elements  or  true, false, fail, or the string
            "timeout".
  
  This  function  calls RunBBoxProgram (6.2-3) with the black box program prog
  and  second argument either a group or a list of group elements; the default
  options  are  assumed.  The  return  value is fail if this call yields fail,
  otherwise  the  gens  component  of  the  result,  if  bound,  or the result
  component if not.
  
  As  an example, we run the black box programs constructed in the example for
  ScanBBoxProgram (6.2-2).
  
    Example  
    gap> g:= AlternatingGroup( 5 );;
    gap> res:= ResultOfBBoxProgram( find.program, g );;
    gap> List( res, Order );
    [ 2, 3 ]
    gap> Order( Product( res ) );
    5
    gap> res:= ResultOfBBoxProgram( check.program, res );
    true
    gap> othergens:= GeneratorsOfGroup( g );;
    gap> res:= ResultOfBBoxProgram( check.program, othergens );
    false
  
  
  6.2-5 AsBBoxProgram
  
  AsBBoxProgram( slp )  attribute
  Returns:  an  equivalent  black  box  program  for  the  given straight line
            program or straight line decision.
  
  Let  slp  be  a straight line program (see IsStraightLineProgram (Reference:
  IsStraightLineProgram))     or     a    straight    line    decision    (see
  IsStraightLineDecision  (6.1-1)).  Then  AsBBoxProgram  returns  a black box
  program bbox (see IsBBoxProgram (6.2-1)) with the same output as slp, in the
  sense  that  ResultOfBBoxProgram  (6.2-4) yields the same result for bbox as
  ResultOfStraightLineProgram   (Reference:   ResultOfStraightLineProgram)  or
  ResultOfStraightLineDecision (6.1-6), respectively, for slp.
  
    Example  
    gap> f:= FreeGroup( "x", "y" );;  gens:= GeneratorsOfGroup( f );;
    gap> slp:= StraightLineProgram( [ [1,2,2,3], [3,-1] ], 2 );
    <straight line program>
    gap> ResultOfStraightLineProgram( slp, gens );
    y^-3*x^-2
    gap> bboxslp:= AsBBoxProgram( slp );
    <black box program>
    gap> ResultOfBBoxProgram( bboxslp, gens );
    [ y^-3*x^-2 ]
    gap> lines:= [ [ "Order", 1, 2 ], [ "Order", 2, 3 ],
    >              [ [ 1, 1, 2, 1 ], 3 ], [ "Order", 3, 5 ] ];;
    gap> dec:= StraightLineDecision( lines, 2 );
    <straight line decision>
    gap> ResultOfStraightLineDecision( dec, [ (1,2)(3,4), (1,3,5) ] );
    true
    gap> ResultOfStraightLineDecision( dec, [ (1,2)(3,4), (1,3,4) ] );
    false
    gap> bboxdec:= AsBBoxProgram( dec );
    <black box program>
    gap> ResultOfBBoxProgram( bboxdec, [ (1,2)(3,4), (1,3,5) ] );
    true
    gap> ResultOfBBoxProgram( bboxdec, [ (1,2)(3,4), (1,3,4) ] );
    false
  
  
  6.2-6 AsStraightLineProgram
  
  AsStraightLineProgram( bbox )  attribute
  Returns:  an  equivalent  straight  line  program  for  the  given black box
            program, or fail.
  
  For    a    black    box   program   (see   AsBBoxProgram   (6.2-5))   bbox,
  AsStraightLineProgram    returns    a    straight    line    program    (see
  IsStraightLineProgram  (Reference:  IsStraightLineProgram))  with  the  same
  output as bbox if such a straight line program exists, and fail otherwise.
  
    Example  
    gap> Display( AsStraightLineProgram( bboxslp ) );
    # input:
    r:= [ g1, g2 ];
    # program:
    r[3]:= r[1]^2;
    r[4]:= r[2]^3;
    r[5]:= r[3]*r[4];
    r[3]:= r[5]^-1;
    # return values:
    [ r[3] ]
    gap> AsStraightLineProgram( bboxdec );
    fail
  
  
  
  6.3 Representations of Minimal Degree
  
  This   section   deals  with  minimal  degrees  of  permutation  and  matrix
  representations.  We do not provide an algorithm that computes these degrees
  for  an  arbitrary  group,  we  only provide some tools for evaluating known
  databases,    mainly   concerning   bicyclic   extensions   (see   [CCNPW85,
  Section 6.5])  of simple groups, in order to derive the minimal degrees, see
  Section 6.3-4.
  
  In  the  AtlasRep  package,  this  information  can  be used for prescribing
  minimality conditions in DisplayAtlasInfo (3.5-1), OneAtlasGeneratingSetInfo
  (3.5-5),  and  AllAtlasGeneratingSetInfos (3.5-6). An overview of the stored
  minimal degrees can be shown with BrowseMinimalDegrees (3.6-1).
  
  6.3-1 MinimalRepresentationInfo
  
  MinimalRepresentationInfo( grpname, conditions )  function
  Returns:  a record with the components value and source, or fail
  
  Let  grpname be the GAP name of a group G, say. If the information described
  by conditions about minimal representations of this group can be computed or
  is   stored   then  MinimalRepresentationInfo  returns  a  record  with  the
  components value and source, otherwise fail is returned.
  
  The following values for conditions are supported.
  
      If  conditions  is  NrMovedPoints  (Reference:  NrMovedPoints  (for  a
        permutation))  then  value,  if  known,  is  the  degree  of a minimal
        faithful  (not  necessarily transitive) permutation representation for
        G.
  
      If  conditions  consists of Characteristic (Reference: Characteristic)
        and  a  prime  integer  p  then value, if known, is the dimension of a
        minimal  faithful  (not necessarily irreducible) matrix representation
        in characteristic p for G.
  
      If  conditions  consists of Size (Reference: Size) and a prime power q
        then  value,  if  known,  is  the dimension of a minimal faithful (not
        necessarily  irreducible) matrix representation over the field of size
        q for G.
  
  In  all  cases,  the value of the component source is a list of strings that
  describe  sources  of  the information, which can be the ordinary or modular
  character  table  of G (see [CCNPW85], [JLPW95], [HL89]), the table of marks
  of  G,  or  [Jan05].  For  an overview of minimal degrees of faithful matrix
  representations  for  sporadic  simple groups and their covering groups, see
  also
  
  http://www.math.rwth-aachen.de/~MOC/mindeg/.
  
  Note  that  MinimalRepresentationInfo  cannot  provide any information about
  minimal representations over prescribed fields in characteristic zero.
  
  Information  about  groups that occur in the AtlasRep package is precomputed
  in MinimalRepresentationInfoData (6.3-2), so the packages CTblLib and TomLib
  are  not  needed  when MinimalRepresentationInfo is called for these groups.
  (The  only  case  that  is not covered by this list is that one asks for the
  minimal  degree  of  matrix  representations  over  a  prescribed  field  in
  characteristic coprime to the group order.)
  
  One of the following strings can be given as an additional last argument.
  
  "cache"
        means  that the function tries to compute (and then store) values that
        are  not  stored  in MinimalRepresentationInfoData (6.3-2), but stored
        values are preferred; this is also the default.
  
  "lookup"
        means  that  stored  values  are  returned  but  the function does not
        attempt    to    compute    values    that    are    not   stored   in
        MinimalRepresentationInfoData (6.3-2).
  
  "recompute"
        means that the function always tries to compute the desired value, and
        checks the result against stored values.
  
    Example  
    gap> MinimalRepresentationInfo( "A5", NrMovedPoints );
    rec( 
      source := [ "computed (alternating group)", 
          "computed (char. table)", "computed (subgroup tables)", 
          "computed (subgroup tables, known repres.)", 
          "computed (table of marks)" ], value := 5 )
    gap> MinimalRepresentationInfo( "A5", Characteristic, 2 );
    rec( source := [ "computed (char. table)" ], value := 2 )
    gap> MinimalRepresentationInfo( "A5", Size, 2 );
    rec( source := [ "computed (char. table)" ], value := 4 )
  
  
  6.3-2 MinimalRepresentationInfoData
  
  MinimalRepresentationInfoData global variable
  
  This  is  a  record  whose  components  are  GAP  names  of groups for which
  information  about minimal permutation and matrix representations were known
  in  advance  or have been computed in the current GAP session. The value for
  the group G, say, is a record with the following components.
  
  NrMovedPoints
        a  record with the components value (the degree of a smallest faithful
        permutation  representation  of G) and source (a string describing the
        source of this information).
  
  Characteristic
        a  record  whose components are at most 0 and strings corresponding to
        prime  integers, each bound to a record with the components value (the
        degree  of  a  smallest  faithful  matrix  representation of G in this
        characteristic)  and  source  (a  string describing the source of this
        information).
  
  CharacteristicAndSize
        a  record whose components are strings corresponding to prime integers
        p,  each bound to a record with the components sizes (a list of powers
        q  of  p), dimensions (the corresponding list of minimal dimensions of
        faithful  matrix representations of G over a field of size q), sources
        (the  corresponding  list  of  strings  describing  the source of this
        information),  and complete (a record with the components val (true if
        the minimal dimension over any finite field in characteristic p can be
        derived from the values in the record, and false otherwise) and source
        (a string describing the source of this information)).
  
  The values are set by SetMinimalRepresentationInfo (6.3-3).
  
  6.3-3 SetMinimalRepresentationInfo
  
  SetMinimalRepresentationInfo( grpname, op, value, source )  function
  Returns:  true  if  the values were successfully set, false if stored values
            contradict the given ones.
  
  This function sets an entry in MinimalRepresentationInfoData (6.3-2) for the
  group G, say, with GAP name grpname.
  
  Supported values for op are
  
      "NrMovedPoints"  (see  NrMovedPoints  (Reference: NrMovedPoints (for a
        permutation))),  which  means  that  value  is  the  degree of minimal
        faithful  (not  necessarily transitive) permutation representations of
        G,
  
      a   list   of  length  two  with  first  entry  "Characteristic"  (see
        Characteristic  (Reference:  Characteristic))  and  second  entry char
        either  zero  or  a  prime  integer,  which  means  that  value is the
        dimension  of  minimal  faithful  (not necessarily irreducible) matrix
        representations of G in characteristic char,
  
      a  list  of  length  two with first entry "Size" (see Size (Reference:
        Size)) and second entry a prime power q, which means that value is the
        dimension  of  minimal  faithful  (not necessarily irreducible) matrix
        representations of G over the field with q elements, and
  
      a  list  of  length  three  with  first  entry  "Characteristic"  (see
        Characteristic  (Reference:  Characteristic)),  second  entry  a prime
        integer p, and third entry the string "complete", which means that the
        information  stored for characteristic p is complete in the sense that
        for any given power q of p, the minimal faithful degree over the field
        with q elements equals that for the largest stored field size of which
        q is a power.
  
  In each case, source is a string describing the source of the data; computed
  values are detected from the prefix "comp" of source.
  
  If the intended value is already stored and differs from value then an error
  message is printed.
  
    Example  
    gap> SetMinimalRepresentationInfo( "A5", "NrMovedPoints", 5,
    >      "computed (alternating group)" );
    true
    gap> SetMinimalRepresentationInfo( "A5", [ "Characteristic", 0 ], 3,
    >      "computed (char. table)" );
    true
    gap> SetMinimalRepresentationInfo( "A5", [ "Characteristic", 2 ], 2,
    >      "computed (char. table)" );
    true
    gap> SetMinimalRepresentationInfo( "A5", [ "Size", 2 ], 4,
    >      "computed (char. table)" );
    true
    gap> SetMinimalRepresentationInfo( "A5", [ "Size", 4 ], 2,
    >      "computed (char. table)" );
    true
    gap> SetMinimalRepresentationInfo( "A5", [ "Characteristic", 3 ], 3,
    >      "computed (char. table)" );
    true
  
  
  
  6.3-4 Criteria Used to Compute Minimality Information
  
  The information about the minimal degree of a faithful matrix representation
  of  G  in  a  given  characteristic  or  over  a  given  field  in  positive
  characteristic  is derived from the relevant (ordinary or modular) character
  table  of  G, except in a few cases where this table itself is not known but
  enough information about the degrees is available in [HL89] and [Jan05].
  
  The  following  criteria  are  used  for  deriving  the  minimal degree of a
  faithful  permutation  representation  of  G from the information in the GAP
  libraries of character tables and of tables of marks.
  
      If the name of G has the form "An" or "An.2" (denoting alternating and
        symmetric  groups,  respectively) then the minimal degree is n, except
        if n is smaller than 3 or 2, respectively.
  
      If  the  name  of  G has the form "L2(q)" (denoting projective special
        linear  groups  in  dimension  two)  then the minimal degree is q + 1,
        except if q ∈ { 2, 3, 5, 7, 9, 11 }, see [Hup67, Satz II.8.28].
  
      If  the  largest  maximal subgroup of G is core-free then the index of
        this  subgroup  is  the  minimal  degree.  (This  is used when the two
        character  tables  in  question  and the class fusion are available in
        GAP's  Character  Table  Library  ([Bre13]);  this  happens  for  many
        character tables of simple groups.)
  
      If  G  has a unique minimal normal subgroup then each minimal faithful
        permutation representation is transitive.
  
        In  this  case,  the  minimal degree can be computed directly from the
        information  in  the table of marks of G if this is available in GAP's
        Library of Tables of Marks ([NMP13]).
  
        Suppose  that  the  largest maximal subgroup of G is not core-free but
        simple  and normal in G, and that the other maximal subgroups of G are
        core-free.  In  this  case,  we take the minimum of the indices of the
        core-free  maximal  subgroups  and of the product of index and minimal
        degree  of  the  normal  maximal  subgroup.  (This  suffices  since no
        core-free  subgroup of the whole group can contain a nontrivial normal
        subgroup of a normal maximal subgroup.)
  
        Let  N be the unique minimal normal subgroup of G, and assume that G/N
        is  simple  and has minimal degree n, say. If there is a subgroup U of
        index n ⋅ |N| in G that intersects N trivially then the minimal degree
        of G is n ⋅ |N|. (This is used for the case that N is central in G and
        N × U occurs as a subgroup of G.)
  
      If  we  know a subgroup of G whose minimal degree is n, say, and if we
        know either (a class fusion from) a core-free subgroup of index n in G
        or  a  faithful permutation representation of degree n for G then n is
        the  minimal  degree  for  G. (This happens often for tables of almost
        simple groups.)