# Reply to charles

Hi Charles,

>
>
> On 21. Jun 2024, at 23:03, Charles Leedham-green <[e-mail]> wrote:
>
> Hi Max,
>
> I am VERY glad to see this advance.

Thank you! We are indeed very happy it worked out so well.
But of course we were standing on the shoulders of giants such as you and Eamonn, and also we still have a lot more to deal with.

>
> However, the fundamental use of constructive recognition is constructive membership, and constructive membership calls constructive recognition once
> and then requires one to write random elements of the group as SLP’s in the standard generators, and this second stage will take longer, and will contribute
> more to the final SLP that has to be evaluated in the parent group.
>
> I was wondering if your success with the stingray elements had inspired you to improve this second stage. I don’t see any dramatic improvement, but careful
> organisation of the code might be possible. I ought to look at the current code, but I haven’t.

You are of course right that overall the cost for constructive membership is crucial for applications of the overall composition tree.

For the second stage (i.e., rewriting random elements in terms of standard generaotrs), we are not using stingrays at this moment.
Instead we use the method outlined in <https://arxiv.org/abs/1305.5617> (see also the attached PDF), based on the Bruhat decomposition, which is using a new twist to avoid taking a discrete logarithm at all. This has been implemented by our student Daniel Rademacher in GAP.

The stingrays might still be helpful in so far as the steep descent (going from dimension d to roughly log(d)) reduces the number of recursions and thus the length of the SLPs for expressing the standard generators for the base case groups in terms of the original generators.

>
> What is the status of matrix group recognition in OSCAR, or indeed in GAP? As OSCAR embraces GAP I suppose that it comes to the same thing.

This is a really important question. Indeed there is currently a lot of work being done by us and our team on the matrix group recognition project in GAP as well as in OSCAR, led my myself and the group of Alice in Aachen. In the next few years we plan to continue our close collaboration on advancing the project so that it is well integrated in OSCAR, and filling in gaps in the feature set for composition trees. We are trying to realise the plans we all made in Banff a few years past. We were lucky to have had some funding in the past few years which enabled some nice advances. If our luck on funding holds we will have a much better version of the recognition project available in GAP and OSCAR within 2-3 years.

Both Alice and I consider this an important service to the Computational Group Theory community. The work you, Eamonn and others have done in MAGMA is of course wonderful, and a great inspiration. But as Eamonn has frequently stressed having another implementation in GAP and OSCAR would surely be beneficial to both sides, and to researchers everywhere.

>
> As you surely know the initial constructive classical group recognition paper was due to Kantor and Seress, and it occurred to me that a divide and conquer
> algorithm must be better. But the complexity is such that the first subdivision and subsequent glueing are dominant in the recursion. Fine. But the procedure
> was too fast in the sense that everything around it was slower. However, if we want a presentation of the group on a given generating set, that might
> take full advantage of the efficient algorithm for finding standard generators. To get a short presentation for a classical group the critical step is to get a
> short presentation for the Weyl group. Hence our short presentations for the symmetric and alternating groups, also based on divide and conquer. I don’t suppose
> you can stingray these. As again you will know we use these short presentations to verify the correctness of the composition tree, and stingray will of course
> shorten the SLP’s

You raise some very interesting points. At this time we rely entierly on the 2020 paper by you and Eamonn (and available in GAP and OSCAR through the package <https://www.gap-system.org/Packages/classicpres.html>), but we also did not yet have an opportunity to think much about this, as we were busy with the constructive recognition. However, we would love to think more about this and ideally also talk to you about it. Perhaps some interesting applications of stingray elements are possible, since the probablility that two random stingray elements generate the whole classical group is very high.

One of our main goals for the next year is to take all the various parts for classical groups and combine them together in GAP and OSCAR into a coherent whole. Then we will build on this and extend it (besides novel algorithms, we also still need to play a lot of catch-up on other parts, were we need to just implement the state of the art algorithms).

Best wishes
Max