###### tags: `GAP`, `recog`
# How to write a recognition method for the recog package

## THIS IS NOW INCLUDED IN THE RECOG MANUAL

HackMD has a feature that allows you to [add comments, click here for details](https://hackmd.io/c/tutorials/%2Fs%2Fhow-to-use-comments).

## Purpose of this document

The purpose of this How-To is to explain how to integrate a newly developed group recognition method into the framework provided by the GAP package [recog]. For further details on individual commands, please refer to the [recog manual], in particular to [chapter 4].

Feedback on the content of this How-To is also welcome. If you spot a mistake, think something could be explained better, or should be improved, please let us know by submitting an issue to the [recog issue tracker] or by sending an email to <[e-mail]>.

## A quick overview on how group recognition works

The basic problem of constructive group recognition is the following: Given any g ∈ G, G = ⟨ X ⟩, we want to have a *straight line program* (SLP) from X to g, i.e. we want to solve the constructive membership problem.
If g ∉ G (in the situation that G is naturally embedded into some bigger group), then the algorithm should fail. The problem is solved by constructing some nice generators and then writing an SLP from the nice generators to g and concatenating with an SLP from X to the nice generators.
The process is organised recursively along a composition tree for G, which is often called *recognition tree*.
Below, we go into more details and distinguish between two cases:
1. The group that is supposed to be constructively recognised is (almost) simple, possibly modulo scalars, a so-called *leaf node*.
2. The group that is supposed to be constructively recognised can be split (by some method involving a homomorphism), a so-called *splitting node*.

By *constructively recognising* the group we mean that the isomorphism type of the group is known, i.e. it has a name (for example $M_{11}$ or $PSL_2(9)$), and that constructive membership is solved as explained above.

TODO: For many more details see (e.g. the excellent survey article by Eamonn, Charles, et al).

More terminology:
A *recognition method* is a GAP function together with an agreement about what arguments it takes and what result it returns.

## A brief note on projective groups

TODO: explain the concept... matrix group in $GL(d,p)$ + implicit notation of working "modulo scalars in $F_p^*$".

## Input and return value for recognition methods

In [recog], each recognition methods takes two arguments:
1. a *recognition info record* `ri` and
2. a GAP group `G`.

The group `G` must be a GAP group object with generators, and it is usually a permutation group or a matrix group, possibly a projective group.
The job of the recognition method is to constructively recognize the group `G`, and if succesful, add information about the group to `ri`.

There are four possible return values for a recognition method. We point out that this might not be what is expected from a user perspective, but instead
recog minimizes the amount of information provided.

1. `Success`
- means that the method was successful and no more methods have to be tried.

2. `NeverApplicable`
- means that the method was not successful and that there is no point to call the method again in this situation whatsoever.

3. `TemporaryFailure`
- means that the method temporarily failed, that it however could be sensible to call it again in this situation at a later stage. This value is typical for a Las Vegas algorithm using randomised methods, which has failed, but which may succeed when called again.

4. `NotEnoughInformation`
- means that the method for some reason refused to do its work. However, it is possible that it will become applicable later such that it makes sense to call it again, when maybe there is more information available.

If the method happend to be successful, then it is also supposed to store additional information inside the recognition info record `ri`. We already described in general terms what that information is supposed to be from the perspective of a user of a recognition method. But when implementing a recognition method, this is slightly different; in particular, [recog] tries to minimize the amount of information that a recognition method *must* provide (see below) to the absolute minimum, and derives as much of the missing information as it can from the provided information.

1. *leaf methods* constructively recognize leaf nodes of the composition tree; typically that would be (almost) simple groups, or groups which otherwise are "easy" to deal with;

2. *splitting methods* construct a homomorphism $\phi:G\to H$, and thereby *split* the recognition task into recognizing $H$, and recognizing the kernel $N:=\ker(\phi)$.

The next two sections describe these two types of methods in more details, and include example code.

## Leaf methods

A leaf method must at the very least do the following:

1. Provide the order of the recognized group via `SetSize(ri, NNN)`.
2. Provide a set of SLPs which map the original generators $X$ to the nice generators $Y$, as entry for the attribute `slptonice`.
3. Provide a function which maps any element $g\in G$ to a corresponding SLP in terms of the nice generators $Y$, as entry for the attribute `slpforelement`.
4. Call `SetFilterObj(ri, IsLeaf);` to mark the node as a leaf node.

There are further values that can be provided, in particular to speed up computations; we'll come back to that later. Let's first look at an example: The following method recognizes trivial groups, and is actually used like that in [recog], as a base case for the recursive group recognition algorithm. It works for arbitrary groups.

FindHomMethodsGeneric.TrivialGroup := function(ri, G)
  local gens;
  # get the generators of the group
  gens := GeneratorsOfGroup(G);

  # check whether all generators are trivial
  # ri!.isone is explained below
  if not ForAll(gens, ri!.isone) then   
    # NeverApplicble because it makes
    # no sense to call this method
    return NeverApplicable;
  fi;

  # The group is trivial! Provide required information:

  # size of the group
  SetSize(ri, 1);

  # explained below
  Setslpforelement(ri, SLPforElementFuncs.TrivialGroup);
  
  # SLP from given generators to nice generators
  Setslptonice(ri, StraightLineProgramNC([[[1,0]]],
                   Length(gens)));
                   
                   
  # We have reached a leaf node.        
  SetFilterObj(ri, IsLeaf);
  return Success;
end;

The input is in the format described above, and the return value is "Success".

Two more comments:
1. When we check whether all generators are the identity, we call `ri!.isone`, instead of `IsOne`. The reason for this is the need to support *projective groups*. For permutation groups and matrix groups, `ri!.isone` is simply defined to be `IsOne`. For projective groups, it is set to `IsOneProjective`, which can be read as "is one modulo scalars".
2. The function `SLPforElementFuncs.TrivialGroup` takes `ri` as well as an element `g` as input.
If $g \in G$, then it is supposed to return an SLP for $g$ in terms of the nice gens $Y$. Otherwise it returns `fail`. Here is the concrete implementation:

SLPforElementFuncs.TrivialGroup := function(ri, g)
  if not ri!.isone(g) then
    return fail;
  fi;
  return StraightLineProgramNC( [ [1,0] ], 1 );
end;

Finally, we need to let `recog` know about this new recognition method. This is done via the `AddMethod` function. Another example!

AddMethod(FindHomDbPerm,
          FindHomMethodsGeneric.TrivialGroup,
          300,
          "TrivialGroup",
          "go through generators, compare to identity");

The function `AddMethod` takes four mandatory arguments `db`, `meth`, `rank`, `stamp`, and an optional fifth argument `comment`. Their meaning is as follows:

- `db` is the "method database", and determines to which type of groups the methods should be applied. Allowed values are:
- `FindHomDbPerm`
- `FindHomDbMatrix`
- `FindHomDbProj`

- `meth` is the recognition method we have defined. In our example this is `FindHomMethodsGeneric.TrivialGroup`.

- `rank` is the relative rank of the recognition method, given as an integer. The idea is that methods with a high rank get called before methods with a low rank, so [recog] tries recognition methods starting from the highest rank. What the "right" rank for a given method is depends on which other methods exist and what their ranks are. As a rule of thumb, methods which are either very fast or very likely to be applicable should be tried before slower methods, or methods which are less likely to be relevant.
- `stamp` holds a string value that uniquely describes the method. This is used for bookkeeping. It is also used in the manual, for printing the recognition tree, and for debugging purposes.
- `comment` is a string valued comment which in the example above has beend used to explain what he method does. This argument is optional and can be left out.

Note that above, we only installed our method into `FindHomDbPerm`. But in recog, it is actually also installed for matrix and projective groups. We reproduce the corresponding `AddMethod` calls here. Note that the ranks differ, so the same method can be called with varying priority depending on the type of group.

AddMethod( FindHomDbMatrix,
           FindHomMethodsGeneric.TrivialGroup,
           3100,
           "TrivialGroup",
           "check whether all generators are equal to the identity matrix" );

AddMethod( FindHomDbProjective,
           FindHomMethodsGeneric.TrivialGroup,
           3000,
           "TrivialGroup",
           "check if all generators are scalar multiples of the identity matrix" );

- TODO: more advanced example?
- TODO: we need something that demonstrates the other two return values (Oh yes, good point.)

## Splitting methods

Recall that splitting recognition methods produce an epimorphism $\phi:G\to H$ and then delegate the work to the image $H$ and the kernel $N:=\ker(\phi)$.
This means that now $N$ and $H$ have to be constructively recognized. Such a splitting recognition method only needs to provide a homomorphism, by calling `SetHomom(ri, hom);`. However, in practice one will want to provide additional data.

We start with an example, similar to a method used in `recog`. This refers to permutation groups only!

FindHomMethodsPerm.NonTransitive := function(ri, G)
  local hom, la, o;

  # test whether we can do something:
  if IsTransitive(G) then
    # the action is transitive, so we can't do
    # anything, and there is no point in calling us again.
    return NeverApplicable;
  fi;

  # compute orbit of the largest moved point
  la := LargestMovedPoint(G);
  o := Orbit(G, la, OnPoints);

  # compute homomorphism into Sym(o), i.e, restrict
  # the permutation action of G to the orbit o
  hom := ActionHomomorphism(G, o);
  
  # store the homomorphism into the recognition info record
  SetHomom(ri, hom);
  
  # indicate success
  return Success;
end;

AddMethod(FindHomDbPerm,
          FindHomMethodsPerm.NonTransitive,
          90, "NonTransitive",
          "try to restrict to orbit");

TODO: More complex example:

FindHomMethodsMatrix.BlockLowerTriangular := function(ri, G)
  # This is only used coming from a hint, we know what to do:
  # A base change was done to get block lower triangular shape.
  # We first do the diagonal blocks, then the lower p-part:
  local H, data, hom, newgens;

  # we need to construct a homomorphism, but to defined it,
  # we need the image, but of course the image is defined in
  # terms of the homomorphism... to break this cycle, we do
  # the following: we first map the input generators using
  # the helper function RECOG.HomOntoBlockDiagonal; this
  # function is later also used as the underlying mapping
  # of the homomorphism.
  data := rec( blocks := ri!.blocks );
  newgens := List(GeneratorsOfGroup(G),
                  x -> RECOG.HomOntoBlockDiagonal(data, x));
  Assert(0, not fail in newgens);

  # now that we have the images of the generators, we can
  # defined the image group
  H := Group(newgens);

  # finally, we define the homomorphism
  hom := GroupHomByFuncWithData(G, H, RECOG.HomOntoBlockDiagonal, data);
  
  # ... and store it in the recognition info record
  SetHomom(ri, hom);

  # since we know exactly what kind of group we are looking
  # at, we don't want to run generic recognition on the
  # factor group and the kernel. So we provide "hints" to
  # ensure more appropriate recognition methods are applied
  # first.

  # Give hint to factor
  forfactor(ri).blocks := ri!.blocks;
  Add(forfactor(ri).hints,
      rec( method := FindHomMethodsMatrix.BlockDiagonal,
           rank := 2000,
           stamp := "BlockDiagonal" ) );

  # Tell recog that we have a better method for finding kernel 
  findgensNmeth(ri).method := FindKernelLowerLeftPGroup;
  findgensNmeth(ri).args := [];

  # Give hint to kernel N
  Add(forkernel(ri).hints, 
      rec( method := FindHomMethodsMatrix.LowerLeftPGroup,
           rank := 2000,
           stamp := “LowerLeftPGroup" ));
  forkernel(ri).blocks := ri!.blocks;

  # This function always succeeds, because it is only
  # called for inputs for which it is known to apply.
  return Success;
end;

## 3. More advanced

TODO

## 4. Misc and FAQ

TODO: Tips, examples, links

[recog]: https://gap-packages.github.io/recog/
[recog manual]: https://gap-packages.github.io/recog/doc/chap0.html
[recog issue tracker]: https://github.com/gap-packages/recog/issues
[chapter 4]: https://gap-packages.github.io/recog/doc/chap4.html