  
  [1X3 [33X[0;0YRecog package for user[133X[101X
  
  [33X[0;0YThis  chapter provides a user-friendly introduction to the [5Xrecog[105X package. It
  presents  the  basic  theoretical  background, functionality, representative
  applications, and the most important commands needed to get you started with
  group recognition.[133X
  
  [33X[0;0YIn  Section  [14X3.1[114X, we explain the theoretical background needed to understand
  how  group  recognition works in this package. Section [14X3.2[114X presents the main
  functions  provided  by this package to recognise groups. In Section [14X3.3[114X, we
  show  some  instructive  examples  of  the  usage  of this package. Finally,
  Section [14X3.4[114X explains possible applications of a completed recognition tree.[133X
  
  
  [1X3.1 [33X[0;0YTheoretical background[133X[101X
  
  [33X[0;0YAt  its  core,  [5Xrecog[105X uses a "divide and conquer" strategy to understand the
  structure  of a given group [22XG[122X. This process builds a data structure called a
  [21Xrecognition tree[121X (also referred to as a [21Xcomposition tree[121X).[133X
  
  [33X[0;0YA  recognition  tree  breaks  down the group [22XG[122X into smaller, more manageable
  groups.  The  process  typically involves finding a homomorphism [22Xφ : G -> H[122X,
  and  then recursively analysing both the kernel [22Xker(φ) = N ⊴ G[122X and the image
  im[22X(φ)  ≅  G/N[122X.  This  continues  until  the  remaining groups are (quasi- or
  almost)simple,  which are the fundamental building blocks of all groups. The
  resulting  tree  represents  the  entire  structure of the original group [22XG[122X,
  where  the  root  is  given  by  [22XG[122X and the leaves are the (quasi- or almost)
  simple  groups  obtained in the process. The leaf nodes are the groups being
  directly recognised, and the result is then assembled back up the tree until
  the group [22XG[122X is recognised.[133X
  
  [33X[0;0YIn  order  to  work  with  group  elements  efficiently  and  constructively
  throughout this process, [5Xrecog[105X uses [21XStraight-Line Programs[121X (or [21XSLPs[121X). An SLP
  is  a highly efficient way to record how a group element [22Xg ∈ G[122X is built from
  the  group's generators. Instead of a potentially very long word in terms of
  the  generators  that evaluates to [22Xg[122X, an SLP is a short sequence of steps to
  compute the element [22Xg[122X. This makes it possible to work with very large groups
  effectively.  More  details about Straight-Line Programs in [5XGAP[105X can be found
  in [14X'Reference: Straight Line Programs'[114X.[133X
  
  [33X[0;0YA  key  problem  that  [5Xrecog[105X  helps  to solve is the [21Xconstructive membership
  problem[121X. Given a group [22XG = ⟨ X ⟩[122X by a set of generators [22XX ⊆ G[122X and an element
  [22Xg[122X,  the  problem  is twofold. First, is [22Xg[122X an element of [22XG[122X? Second, if it is,
  how  can [22Xg[122X be written as a word in the generators [22XX[122X? The "constructive" part
  of  the  solution  is  providing this representation, and [5Xrecog[105X does this by
  producing  an  SLP for [22Xg[122X. This provides a concrete certificate of membership
  that  can  be used in further computations. Solving this problem efficiently
  is fundamental to many other group algorithms. For more general information,
  see e.g. [BHLO15]. For more information specific to this package, see [NS06]
  and [Neu09].[133X
  
  
  [1X3.2 [33X[0;0YFunctions[133X[101X
  
  [33X[0;0YThe main function to recognise a group is the following.[133X
  
  [1X3.2-1 RecogniseGroup[101X
  
  [33X[1;0Y[29X[2XRecogniseGroup[102X( [3XH[103X ) [32X function[133X
  [33X[1;0Y[29X[2XRecognizeGroup[102X( [3XH[103X ) [32X function[133X
  [6XReturns:[106X  [33X[0;10Y[9Xfail[109X for failure or a recognition node.[133X
  
  [33X[0;0Y[3XH[103X  must be a [5XGAP[105X group object. This function automatically dispatches to one
  of    the    two   previous   functions   [2XRecognisePermGroup[102X   ([14X3.2-2[114X),   or
  [2XRecogniseMatrixGroup[102X  ([14X3.2-3[114X),  according  to  the type of the group [3XH[103X. Note
  that  since currently there is no implementation of projective groups in the
  [5XGAP[105X  library,  one  cannot  recognise a matrix group [3XH[103X as a projective group
  using this function.[133X
  
  [33X[0;0YAlternatively,  if  you  know  the type of the given group, you can directly
  call  the  specialised  functions  for  permutation,  matrix,  or projective
  groups. These specialised functions are described in[133X
  
  [1X3.2-2 RecognisePermGroup[101X
  
  [33X[1;0Y[29X[2XRecognisePermGroup[102X( [3XH[103X ) [32X function[133X
  [33X[1;0Y[29X[2XRecognizePermGroup[102X( [3XH[103X ) [32X function[133X
  [6XReturns:[106X  [33X[0;10Y[9Xfail[109X for failure or a recognition node.[133X
  
  [33X[0;0Y[3XH[103X   must   be   a   [5XGAP[105X   permutation  group  object.  This  function  calls
  [2XRecogniseGeneric[102X  ([14X4.1-1[114X)  with  the  method  database  used for permutation
  groups, which is stored in the global variable [2XFindHomDbPerm[102X ([14X5.2-2[114X), and no
  prior knowledge.[133X
  
  [1X3.2-3 RecogniseMatrixGroup[101X
  
  [33X[1;0Y[29X[2XRecogniseMatrixGroup[102X( [3XH[103X ) [32X function[133X
  [33X[1;0Y[29X[2XRecognizeMatrixGroup[102X( [3XH[103X ) [32X function[133X
  [6XReturns:[106X  [33X[0;10Y[9Xfail[109X for failure or a recognition node.[133X
  
  [33X[0;0Y[3XH[103X must be a [5XGAP[105X matrix group object over a finite field. This function calls
  [2XRecogniseGeneric[102X  ([14X4.1-1[114X)  with  the method database used for matrix groups,
  which is stored in the global variable [2XFindHomDbMatrix[102X ([14X5.2-3[114X), and no prior
  knowledge.[133X
  
  [1X3.2-4 RecogniseProjectiveGroup[101X
  
  [33X[1;0Y[29X[2XRecogniseProjectiveGroup[102X( [3XH[103X ) [32X function[133X
  [33X[1;0Y[29X[2XRecognizeProjectiveGroup[102X( [3XH[103X ) [32X function[133X
  [6XReturns:[106X  [33X[0;10Y[9Xfail[109X for failure or a recognition node.[133X
  
  [33X[0;0Y[3XH[103X  must be a [5XGAP[105X matrix group object over a finite field. Since as of now no
  actual  projective  groups  are implemented in the [5XGAP[105X library we use matrix
  groups  instead.  The  recognition  will  however  view  the  group  as  the
  projective  group,  i.e.  the  matrix group modulo its scalar matrices. This
  function  calls  [2XRecogniseGeneric[102X  ([14X4.1-1[114X) with the method database used for
  projective    groups,    which    is   stored   in   the   global   variable
  [2XFindHomDbProjective[102X ([14X5.2-4[114X), and no prior knowledge.[133X
  
  [33X[0;0YEach  of these functions returns a recognition node which is a [5XGAP[105X component
  object. Further details to this data structure as well as its attributes are
  given  in  [14X4.2[114X.  Some examples of what a user can do with a recognition node
  are given in [14X3.4[114X.[133X
  
  
  [1X3.3 [33X[0;0YExamples[133X[101X
  
  [33X[0;0YIn  order to understand the output we consider some examples. Note that many
  methods  used to compute a recognition tree are using randomised algorithms.
  This  means  that  the  function  [2XRecogniseGroup[102X  ([14X3.2-1[114X) may yield slightly
  different results when called multiple times.[133X
  
  [33X[0;0YThe first example we consider is the special linear group.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XG := SL(10,5);[127X[104X
    [4X[28XSL(10,5)[128X[104X
    [4X[25Xgap>[125X [27XRecogniseGroup(G);[127X[104X
    [4X[28X<recognition node GoProjective Dim=10 Field=5[128X[104X
    [4X[28X F:<recognition node (projective) ClassicalNatural Comment=PSLd Simple Size=[128X[104X
    [4X[28X749746041218752566202615590039253234863281250000000000000000000000000 Dim=10 Field=5>[128X[104X
    [4X[28X K:<recognition node DiagonalMatrices Dim=10 Field=5[128X[104X
    [4X[28X    F:<recognition node Scalar Dim=1 Field=5>[128X[104X
    [4X[28X    K:<trivial kernel>>[128X[104X
  [4X[32X[104X
  
  [33X[0;0YThe  output  is  a  recognition  node  that  visualises the structure of the
  recognition  tree.  Each  node  representing  a  group [22XH[122X has two children: a
  factor  of  [22XH[122X  (abbreviated  with  [21XF[121X  which  stands for Factor) and a normal
  subgroup of [22XH[122X (abbreviated with [21XK[121X which stands for Kernel).[133X
  
  [33X[0;0YIn  this example the root node represents the input group [22XSL(10,5)[122X. Starting
  at  this root node the method [10XGoProjective[110X ([14X6.3-5[114X) finds a homomorphism from
  the  group  [22XSL(10,5)[122X  to  itself  modular scalar matrices. The image of this
  homomorphism  is the group [22XPSL(10,5)[122X which is a leaf node in the recognition
  tree.  The kernel of this homomorphism is the group of diagonal matrices [22Xa ⋅
  Id_10[122X  for  [22Xa  ∈  F_5^*[122X.  This group is recognised to be isomorphic to [22XF_5^*[122X
  itself.[133X
  
  [33X[0;0YA second example we consider is a symmetric group on a few points.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XG := SymmetricGroup(10);[127X[104X
    [4X[28XSym( [ 1 .. 10 ] )[128X[104X
    [4X[25Xgap>[125X [27Xri := RecogniseGroup(G);[127X[104X
    [4X[28X<recognition node MovesOnlySmallPoints Size=3628800>[128X[104X
  [4X[32X[104X
  
  [33X[0;0YThis  recognition tree only consists of the root node representing the input
  group  [22XS_10[122X.  The group is recognised to only move a few points. Its size is
  also recognised.[133X
  
  [33X[0;0YTODO: another nice example would be the Rubik's cube group[133X
  
  
  [1X3.4 [33X[0;0YPossible applications[133X[101X
  
  [33X[0;0YThis  section  explains  what  you  can  do  with  recognition nodes after a
  successful recognition.[133X
  
  [33X[0;0YHere is an example of a successful recognition tree:[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XG := DirectProduct(SymmetricGroup(12),SymmetricGroup(5));;[127X[104X
    [4X[25Xgap>[125X [27Xri := RecogniseGroup(G);[127X[104X
    [4X[28X<recognition node NonTransitive[128X[104X
    [4X[28X F:<recognition node MovesOnlySmallPoints Size=120>[128X[104X
    [4X[28X K:<recognition node Giant AlmostSimple Size=479001600>>[128X[104X
  [4X[32X[104X
  
  [33X[0;0YThis  tells  us  that the group was split into a factor (indicated by [10XF:[110X) of
  size 120, and a kernel ([10XK:[110X) of size 479001600.[133X
  
  [33X[0;0YWe  can obtain some more information about the recognition process itself by
  setting a so-called [10XInfoLevel[110X:[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XSetInfoLevel(InfoRecog, 2);[127X[104X
    [4X[25Xgap>[125X [27XSetInfoLevel(InfoMethSel, 2);[127X[104X
    [4X[25Xgap>[125X [27XG := DirectProduct(SymmetricGroup(12),SymmetricGroup(5));;[127X[104X
    [4X[25Xgap>[125X [27Xri := RecogniseGroup(G);[127X[104X
    [4X[28X#I  Finished rank 90 method "NonTransitive": success.[128X[104X
    [4X[28X#I  Going to the image (depth=0, try=1).[128X[104X
    [4X[28X#I  Finished rank 95 method "MovesOnlySmallPoints": success.[128X[104X
    [4X[28X#I  Back from image (depth=0).[128X[104X
    [4X[28X#I  Calculating preimages of nice generators.[128X[104X
    [4X[28X#I  Creating 6 random generators for kernel.[128X[104X
    [4X[28X#I  Going to the kernel (depth=0).[128X[104X
    [4X[28X#I  Finished rank 80 method "Giant": success.[128X[104X
    [4X[28X#I  Back from kernel (depth=0).[128X[104X
    [4X[28X#I  Doing immediate verification (depth=0).[128X[104X
    [4X[28X<recognition node NonTransitive[128X[104X
    [4X[28X F:<recognition node MovesOnlySmallPoints Size=120>[128X[104X
    [4X[28X K:<recognition node Giant Size=479001600>>[128X[104X
  [4X[32X[104X
  
  [33X[0;0YThe lines starting with [10X#I[110X indicate so-called info messages, which inform us
  about  the  progress  of  the  computation.  Here  it  first  finds that the
  permutation  action  is  not  transitive, a homomorphism is found by mapping
  onto  the  action  on  one of the orbits. The image is recognised to permute
  only  a few points. The kernel is recognised to be a full symmetric group in
  its natural action on at least 10 points (recognised as [21XGiant[121X).[133X
  
  [33X[0;0YIn  order  to  analyse  the  recognised  group [22XG[122X, you can look at the stored
  attribute  values of the returned recognition node. A list of all attributes
  can be found in Section [14X4.2[114X. As an example we demonstrate how to compute the
  size of a recognised group.[133X
  
  [1X3.4-1 Size[101X
  
  [33X[1;0Y[29X[2XSize[102X( [3Xri[103X ) [32X method[133X
  [6XReturns:[106X  [33X[0;10Ythe size of the recognised group[133X
  
  [33X[0;0YThis  method  calculates the size of the recognised group by multiplying the
  size  of the image and the kernel recursively. It is assumed that leaf nodes
  know already or can calculate the size of their group.[133X
  
  [33X[0;0YFor the group from our example above we obtain the following result.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XSize(ri);[127X[104X
    [4X[28X57480192000[128X[104X
  [4X[32X[104X
  
  [33X[0;0YMoreover,  constructive membership tests can be performed which is explained
  above  in  Section  [14X3.1[114X.  For  this  you  can use the function [2XSLPforElement[102X
  ([14X4.2-15[114X)  that  writes  an arbitrary element in terms of the nice generators
  that  were  computed  in  the  process of recognising the group and that are
  stored  in  the  attribute  [2XNiceGens[102X  ([14X4.2-8[114X). If [9Xfail[109X is returned, then the
  element  in question does not lie in the recognised group or the recognition
  made an error.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xx := PseudoRandom(G);[127X[104X
    [4X[28X(1,12)(2,5,9,11,10,3,4)(7,8)(13,14,16,15,17)[128X[104X
    [4X[25Xgap>[125X [27Xslp := SLPforElement(ri,x);[127X[104X
    [4X[28X<straight line program>[128X[104X
    [4X[25Xgap>[125X [27XResultOfStraightLineProgram(slp,NiceGens(ri));[127X[104X
    [4X[28X(1,12)(2,5,9,11,10,3,4)(7,8)(13,14,16,15,17)[128X[104X
  [4X[32X[104X
  
  [33X[0;0YA  convenient function for testing membership of an element is the following
  function.[133X
  
  [1X3.4-2 \in[101X
  
  [33X[1;0Y[29X[2X\in[102X( [3Xx[103X, [3Xri[103X ) [32X method[133X
  [6XReturns:[106X  [33X[0;10Y[9Xtrue[109X or [9Xfalse[109X[133X
  
  [33X[0;0YThis method tests, whether the element [3Xx[103X lies in the group recognised by the
  recognition  node  [3Xri[103X.  Note that this is only a convenience method, in fact
  [2XSLPforElement[102X  ([14X4.2-15[114X)  is  used and the resulting straight line program is
  thrown away.[133X
  
  [33X[0;0YIf  you  need  an  element  explicitly  written  in  terms  of  the original
  generators, you can use the following function.[133X
  
  [1X3.4-3 SLPforNiceGens[101X
  
  [33X[1;0Y[29X[2XSLPforNiceGens[102X( [3Xri[103X ) [32X function[133X
  [6XReturns:[106X  [33X[0;10Yan SLP expressing the nice generators in the original ones[133X
  
  [33X[0;0YThis  function  assembles  a  possibly  quite  large  straight  line program
  expressing  the  nice  generators in terms of the original ones by using the
  locally stored information in the recognition tree recursively.[133X
  
  [33X[0;0YYou  can  concatenate straight line programs in the nice generators with the
  result  of  this  function  to  explicitly  write an element in terms of the
  original generators.[133X
  
  [33X[0;0YLastly,  a  function to compute the composition series of a recognised group
  is the following.[133X
  
  [1X3.4-4 DisplayCompositionFactors[101X
  
  [33X[1;0Y[29X[2XDisplayCompositionFactors[102X( [3Xri[103X ) [32X function[133X
  [6XReturns:[106X  [33X[0;10Ynothing[133X
  
  [33X[0;0YThis   function  displays  a  composition  series  by  using  the  recursive
  recognition  tree.  It  only works, if the usual operation [2XCompositionSeries[102X
  ([14XReference: CompositionSeries[114X) works for all leaves. THIS DOES CURRENTLY NOT
  WORK FOR PROJECTIVE GROUPS AND THUS FOR MATRIX GROUPS![133X
  
