# 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

• bring a laptop
• if possible, get an eduroam account

You might also want to

• install a recent GAP version (ideally GAP 4.10.1 or later) on your laptop

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.

• register a free GitHub account via http://github.com/join
• install and set up git so that you can easily retrieve the latest version of recog
• execute git clone https://github.com/gap-packages/recog into the pkg folder of your GAP installation

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:

• green: This project welcomes the contributions of people without prior GAP experience
• orange: This project requires some basic GAP knowledge
• red: This project requires advanced GAP knowledge.
• purple: This project requires Magma knowledge

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.

• go through existing documentation, check for correctness and comprehensibility.
• improve/correct incorrect or incomprehensible parts
• add How-tos (e.g. as chapters in the manual); see later section for details
• add (or improve) the general overview of how the package works and how all pieces fit together
• document undocumented functions (where it seems sensible to do so; this involves a decision as to what should be officially “documented”, which means that it is difficult to change later on)
• e.g. document EmptyRecognitionInfoRecord
• Use AutoDoc (and convert bits of the existing documentation to use it)
• generate more parts of the documentation automatically

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.

• Write How-Tos: This might possibly be done in advance
• Apply How-Tos on actual code and ultimately improve and extend them

Possible topics for How-Tos:

• how to add new recognition method implementations
• how to use recog for various applications / examples
• … ? ask participants for suggestions

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

• What are typical groups in applications?
• What would you like recog to do, what should the output be?

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

• Find out references for the algorithm proving correctness and giving complexity estimates
• Identify algorithms that could be replaced by newer and faster methods and add these to the 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.

• Convert Magma tests to GAP
• Design new tests to increase the test coverage of the code
• What do we want/need to test?
• Identify poor performance, and create bench-marking 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.

• How? What are the concepts
• Document for various verification methods

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.

• Can we implement your algorithms?
• What is missing in GAP to do your research 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.

• What are the types of leaf nodes (simple, nearly simple, almost simple?)
• Are/should classical groups in non-natural representation in defining characteristic be leaf nodes?
• Document relevant papers
• What can we already do, what is missing?
• Are there newer, better algorithms that are not yet implemented?

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

• Where are theoretical bottlenecks
• Where are bottlenecks in the GAP implementation?

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

• Find magic constants in code and mark them with a uniform searchable comment
• Explain and provide references from which papers the constants come from as a comment

## 12. Review and resolve GitHub issues of the recog package

• Classify existing issues into different categories:
• Mathematical
• Infrastructure
• Code Bugs
• Tests
• ….
• Label the categories
• Look into the bug reports and try to fix some of them

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

• Asks authors what is in the code, where it comes from…
• Decide whether it should, must, or shouldn’t be integrate properly into the recog package?
• Possibly delete code and properly set up further strategies

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:

• 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
• clarify how 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 gensN

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.

• Can this be achieved via the Chop package?
• Can one improve the GAP meataxe? If so, how?
• The minimal polynomial gets recomputed all the time, previously computed information is not exploited efficiently. Can this be improved?
• Can the user friendliness of the functionality be improved so that all potential uses of the Meataxe are easily achievable?

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

• Is everything there in Magma?
• What can’t Magma do, where is it slow..

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