Part of the motivation for this summer school is to improve the state of group recognition within the computer algebra system GAP, in particular in the recog package for GAP.
We hope that some of the participants will be interested in assisting with this. To this end, we are describing some possible projects in this direction that could already be started during the conference. Different projects require different kinds of skills. It would be great if people with different skills could team up and collaborate on some of these projects.
One possible way to achieve this is to team up people who are familiar with the theory of the underlying algorithms with those who are familiar with GAP software development (use of git, GitHub, pull requests, etc.) thereby contributing jointly to these projects.
If you are interested in contributing to any of these projects, you may wish to prepare in advance. We will also try to provide support for some of these steps during the meeting.
It would be great if everyone could
You might also want to
If you are willing to contribute GAP code you could already execute the following steps. If you encounter any problems, we provide assistance during the meeting.
recoggit clone https://github.com/gap-packages/recog into the
pkg folder of your GAP installationHere we list some possible projects that we work on during the summer school. If you are interested in participating in a particular project, your contributions are greatly valued. Please send an email registering your interest to MGRAachen@math.rwth-aachen.de , so that we can team up people interested in the same projects.
The project titles are colour coded as follows:
If the title is followed by a coloured dot, the team working on this project also requires participation from someone with the colour coded expertise.
Someone with GAP experience will be assisting in each project.
The aim of this project is to improve the documentation of the recog package.
EmptyRecognitionInfoRecordRelevant issue: https://github.com/gap-packages/recog/issues/51
There are two types of mathematicians who would like to find out how to do something: The working mathematician wanting to find out how to use the recog package and the researchers who are interested in writing their own recognition functions and would like to find out how to integrate them into the recog package. The aim of this project is to provide such How-To guides.
Possible topics for How-Tos:
The aim of this project is to identify possible applications of the
functionality of the matrix group recognition package and to evaluate
what further functionality should be available as part of the recog package.
recog to do, what should the output be?The matrix group recognition project spans a wide variety of papers and algorithms. However, much of the code does not indicate where the algorithms come from. The aim of this project is to look through the existing code and identify the algorithms and add references in comments.
Relevant recog issue: https://github.com/gap-packages/recog/issues/45
A comprehensive test suite is essential to test the correctness of the code. We need to provide a comprehensive set of test examples which test every aspect of the code. The aim of this project is to consider test examples.
Relevant recog issues:
Working with projective groups is technically challenging as the elements of projective groups are cosets and thus the algorithms for matrix groups need to be modified.
In recog, this is avoided by working with matrices “modulo scalars”. This is in parts discussed in Max Neunhöffer’s habil thesis. Unfortunately, there are various bugs in the code related to this; some have been fixed in the mean time, but some remain, and it is not quite clear how to resolve them, as we lack understanding of this technique.
In particular, there seem to be some doubt whether this can really deal with all cases (e.g. for representations of PGL(d,q) over a prime field, working modulo scalars of the prime field would not be correct; why does that not matter?)
This is perhaps a more theoretical project, trying to understand how (and whether) this works; however, fixing related bugs (resp. giving input as to what the correct fix might be)also is possible.
Potentially relevant recog issues:
Many of the algorithms in are randomised. The result of a recognition must be verified for correctness at the end. The aim of this project is to review the verification methods, document them and identify gaps.
Relevant recog issue: https://github.com/gap-packages/recog/issues/48
The aim of this project is to determine whether some of the functionality for working with matrix groups over fields of characteristic 0 can or has been implemented in GAP.
The base cases of the recognition tree are called the leaf nodes. The aim of this project is to identify which leaf nodes are allowable and what the algorithmic specifications are in order to run code on a leaf node. We also need to find out for which leaf nodes GAP code is missing.
The recognition code is very complex and intricate. What are the current bottlenecks when running the code on specific examples and how can they be improved? What are the bottlenecks in the MAGMA implementation? The aim of this project is to provide answers to these questions.
Many of the algorithms in the code are randomised. Often they are supported by a probability analysis which requires a certain number of random selections. The aim of this project is to look for “constants”, i.e. fixed numbers, in the code and identify their origin.
recog package There are some code fragments stored within the recog package, which are not (yet) used in the package. The aim of this project is to find out what code there is, what it does and whether and where it should be called in the recog package.
recog package?Relevant recog issue: https://github.com/gap-packages/recog/issues/55
Our note with proposals for new names: https://hackmd.io/bsihJmkLQ06Sm-Zxv8oAWA?view
Many names of methods in recog are rather cryptic, even among those which are
“documented” in the manual. We should give them better, more “GAP like” names.
For this, some care should be taken regarding the internal consistency of
these names.
Also, various things should receive concise standard GAP names so that they may
be referred to in texts in a way that is easy to understand; those names
should also be listed in the index of the recog manual. They should also have
a “standard shortname” for use in function names.
E.g. “recognition info record” is used in some places; we might want to keep that,
or refine it; and then decide on a standard shortname, such as RI or RecogInfo or …
Some potential examples for function names:
pregensfac => e.g. PreimagesOfNiceGenerators (resp. PreImages...) or …RIFac => e.g. RecogInfoOfFactorGroup or RecogInfoFactor or FactorOfRecogInfo or …
(note: we may want to keep RIFac as an alias for the new name to allow writing concise code)RIKer => e.g. RecogInfoOfKernel or KernelOfRecogInfo or …RIParent => e.g. RecogInfoOfParent or RecogInfoOfParentGroup or RecogParent or ParentOfRecogInfo…slpforelement => e.g. SLPforElement (but that does not make it clear
that it returns a function which takes a recog info and an element, and returns an SLP!);
or ElementSLPGeneratorOfRecogInfo or SLPforElementGenerator or …gensN => GeneratorsOfKernel of GeneratorsOfRecogInfoKernel
gensN(ri) differs from GeneratorsOfGroup(KernelOfRecogInfo(ri))findgensNmeth => new name should be compatible with the new name of gensN, e.g.
MethodForFindingFOO, where FOO = new name of gensNIt would be useful if the names of things made it easier to
decide what kind of thing they are; and how to use them. For example,
slpforelement is an attribute, but without any methods; instead, one is
supposed to use Setslpforelement to specify it.
While SLPforElementGeneric is a function that is set as the default value
for slpforelement. So in particular, SLPforElement(ri) returns SLPforElementGeneric
(and not e.g. SLPforElementGeneric(ri)).
Caveat: The paper “A data structure for a uniform approach to computations with finite groups”
by Max Neunhöffer and Ákos Seress references (and explains) many of these
names. So in order to retain its usefulness as a reference, perhaps it would
be wise to at least mention the old names in the documentation (e.g. if
pregensfac were renamed to PreimagesOfNiceGenerators, then the
documentation for the latter might mention the former).
The matrix group recognition project needs access to an efficient Meataxe.
The aim of this project is to take stock and determine which functionalities are available in Magma but not yet in the GAP recog package.
There is a vast body of literature on the subject of group recognitions. Here are just a few publications which might serve as a good starting point in the particular context of recog. Let us know if you think we should add something here.
Max Neunhöffer and Ákos Seress, “A data structure for a uniform approach to computations with finite groups”, 2006 – general overview of recog and a good start to learn about its internals
Max Neunhöffer, “Constructive Recognition of Finite Groups”, 2009, habilitation thesis (source code) – more in-depth information on much of the mathematics behind recog
Henrik Bäärnhielm, Derek Holt, Charles R Leedham-Green, and Eamonn A O’Brien, A practical model for computation with matrix groups, 2014 – survey of matrix group recognition as implemented in Magma, with an extensive bibliography