GAP (recog) - Chapter 3: Recog package for user

This chapter provides a user-friendly introduction to the recog package. It presents the basic theoretical background, functionality, representative applications, and the most important commands needed to get you started with group recognition.

In Section 3.1, we explain the theoretical background needed to understand how group recognition works in this package. Section 3.2 presents the main functions provided by this package to recognise groups. In Section 3.3, we show some instructive examples of the usage of this package. Finally, Section 3.4 explains possible applications of a completed recognition tree.

3.1 Theoretical background

At its core, recog uses a "divide and conquer" strategy to understand the structure of a given group G. This process builds a data structure called a recognition tree (also referred to as a composition tree).

A recognition tree breaks down the group G into smaller, more manageable groups. The process typically involves finding a homomorphism φ : G -> H, and then recursively analysing both the kernel ker(φ) = N ⊴ G and the image im(φ) ≅ G/N. 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 G, where the root is given by G 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 G is recognised.

In order to work with group elements efficiently and constructively throughout this process, recog uses Straight-Line Programs (or SLPs). An SLP is a highly efficient way to record how a group element g ∈ G is built from the group's generators. Instead of a potentially very long word in terms of the generators that evaluates to g, an SLP is a short sequence of steps to compute the element g. This makes it possible to work with very large groups effectively. More details about Straight-Line Programs in GAP can be found in Reference: Straight Line Programs.

A key problem that recog helps to solve is the constructive membership problem. Given a group G = ⟨ X ⟩ by a set of generators X ⊆ G and an element g, the problem is twofold. First, is g an element of G? Second, if it is, how can g be written as a word in the generators X? The "constructive" part of the solution is providing this representation, and recog does this by producing an SLP for g. 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].

3.2 Functions

3.2-1 RecogniseGroup

H must be a GAP group object. This function automatically dispatches to one of the two previous functions RecognisePermGroup (3.2-2), or RecogniseMatrixGroup (3.2-3), according to the type of the group H. Note that since currently there is no implementation of projective groups in the GAP library, one cannot recognise a matrix group H as a projective group using this function.

Alternatively, 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

3.2-2 RecognisePermGroup

H must be a GAP permutation group object. This function calls RecogniseGeneric (4.1-1) with the method database used for permutation groups, which is stored in the global variable FindHomDbPerm (5.2-2), and no prior knowledge.

3.2-3 RecogniseMatrixGroup

H must be a GAP matrix group object over a finite field. This function calls RecogniseGeneric (4.1-1) with the method database used for matrix groups, which is stored in the global variable FindHomDbMatrix (5.2-3), and no prior knowledge.

3.2-4 RecogniseProjectiveGroup

H must be a GAP matrix group object over a finite field. Since as of now no actual projective groups are implemented in the GAP 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 RecogniseGeneric (4.1-1) with the method database used for projective groups, which is stored in the global variable FindHomDbProjective (5.2-4), and no prior knowledge.

Each of these functions returns a recognition node which is a GAP component object. Further details to this data structure as well as its attributes are given in 4.2. Some examples of what a user can do with a recognition node are given in 3.4.

3.3 Examples

In 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 RecogniseGroup (3.2-1) may yield slightly different results when called multiple times.

gap> G := SL(10,5);
SL(10,5)
gap> RecogniseGroup(G);
<recognition node GoProjective Dim=10 Field=5
 F:<recognition node (projective) ClassicalNatural Comment=PSLd Simple Size=
749746041218752566202615590039253234863281250000000000000000000000000 Dim=10 Field=5>
 K:<recognition node DiagonalMatrices Dim=10 Field=5
    F:<recognition node Scalar Dim=1 Field=5>
    K:<trivial kernel>>

The output is a recognition node that visualises the structure of the recognition tree. Each node representing a group H has two children: a factor of H (abbreviated with F which stands for Factor) and a normal subgroup of H (abbreviated with K which stands for Kernel).

In this example the root node represents the input group SL(10,5). Starting at this root node the method GoProjective (6.3-5) finds a homomorphism from the group SL(10,5) to itself modular scalar matrices. The image of this homomorphism is the group PSL(10,5) which is a leaf node in the recognition tree. The kernel of this homomorphism is the group of diagonal matrices a ⋅ Id_10 for a ∈ F_5^*. This group is recognised to be isomorphic to F_5^* itself.

gap> G := SymmetricGroup(10);
Sym( [ 1 .. 10 ] )
gap> ri := RecogniseGroup(G);
<recognition node MovesOnlySmallPoints Size=3628800>

This recognition tree only consists of the root node representing the input group S_10. The group is recognised to only move a few points. Its size is also recognised.

3.4 Possible applications

This section explains what you can do with recognition nodes after a successful recognition.

gap> G := DirectProduct(SymmetricGroup(12),SymmetricGroup(5));;
gap> ri := RecogniseGroup(G);
<recognition node NonTransitive
 F:<recognition node MovesOnlySmallPoints Size=120>
 K:<recognition node Giant AlmostSimple Size=479001600>>

This tells us that the group was split into a factor (indicated by F:) of size 120, and a kernel (K:) of size 479001600.

We can obtain some more information about the recognition process itself by setting a so-called InfoLevel:

gap> SetInfoLevel(InfoRecog, 2);
gap> SetInfoLevel(InfoMethSel, 2);
gap> G := DirectProduct(SymmetricGroup(12),SymmetricGroup(5));;
gap> ri := RecogniseGroup(G);
#I  Finished rank 90 method "NonTransitive": success.
#I  Going to the image (depth=0, try=1).
#I  Finished rank 95 method "MovesOnlySmallPoints": success.
#I  Back from image (depth=0).
#I  Calculating preimages of nice generators.
#I  Creating 6 random generators for kernel.
#I  Going to the kernel (depth=0).
#I  Finished rank 80 method "Giant": success.
#I  Back from kernel (depth=0).
#I  Doing immediate verification (depth=0).
<recognition node NonTransitive
 F:<recognition node MovesOnlySmallPoints Size=120>
 K:<recognition node Giant Size=479001600>>

The lines starting with #I 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 Giant).

In order to analyse the recognised group G, you can look at the stored attribute values of the returned recognition node. A list of all attributes can be found in Section 4.2. As an example we demonstrate how to compute the size of a recognised group.

3.4-1 Size

This 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.

gap> Size(ri);
57480192000

Moreover, constructive membership tests can be performed which is explained above in Section 3.1. For this you can use the function SLPforElement (4.2-15) 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 NiceGens (4.2-8). If fail is returned, then the element in question does not lie in the recognised group or the recognition made an error.

gap> x := PseudoRandom(G);
(1,12)(2,5,9,11,10,3,4)(7,8)(13,14,16,15,17)
gap> slp := SLPforElement(ri,x);
<straight line program>
gap> ResultOfStraightLineProgram(slp,NiceGens(ri));
(1,12)(2,5,9,11,10,3,4)(7,8)(13,14,16,15,17)

A convenient function for testing membership of an element is the following function.

3.4-2 \in

This method tests, whether the element x lies in the group recognised by the recognition node ri. Note that this is only a convenience method, in fact SLPforElement (4.2-15) is used and the resulting straight line program is thrown away.

If you need an element explicitly written in terms of the original generators, you can use the following function.

3.4-3 SLPforNiceGens

This 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.

You 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.

Lastly, a function to compute the composition series of a recognised group is the following.

3.4-4 DisplayCompositionFactors

This function displays a composition series by using the recursive recognition tree. It only works, if the usual operation CompositionSeries (Reference: CompositionSeries) works for all leaves. THIS DOES CURRENTLY NOT WORK FOR PROJECTIVE GROUPS AND THUS FOR MATRIX GROUPS!

3 Recog package for user