Projects

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.

Suggested preparations

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.

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

Colour-coding

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.

1. Documentation </svg

The aim of this project is to improve the documentation of the recog package.

Relevant issue: https://github.com/gap-packages/recog/issues/51

2. How-Tos

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:

3. Applications of recog

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.

4. Identify algorithms and document what is there and what is not

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

5. Tests

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:

6. Understand how “projective groups” (are meant to) work in Akos & Max N.s’ model

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:

7. Verification

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

8. Characteristic 0 in GAP

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.

9. Leaf nodes

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.

10. Identify bottlenecks

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.

11. Magic constants

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.

12. Review and resolve GitHub issues of the recog package

13. Contrib/Misc code

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.

Relevant recog issue: https://github.com/gap-packages/recog/issues/55

14. Improve names of functions, introduce uniform terminology </svg

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:

It 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).

15. Meataxe - Chop package

The matrix group recognition project needs access to an efficient Meataxe.

16. Comparison with Magma

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.

Literature

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.