SymPy Group Theory (GSoC 2017) gsoc, sympy, computational group theory

PermutationGroup methods for FpGroups

The presentation PR got merged fairly quickly last week. Now I could try using the new functionality of resuming coset enumeration with incomplete coset tables in the _finite_index_subgroup function. I expect it should speed it up since at the moment the coset tables inside the function have to be recomputed every time the maximum number of allowed entries is increased. I could also implement a faster version of the presentation algortihm that makes use of strong generators.

Sylow subgroups required a bit more attention. One thing that we were discussing on the Group Theory channel the other day was that symmetric and alternating groups should be treated separately as the generators for their Sylow subgroups can be written down. It took some thinking to work out the details and justify the algorithm. In fact, the alternating group case still doesn’t have a formal proof; but it seems clear that it should work and, indeed, it does as I discovered yesterday on implementing the function. It was a bit fiddly to lay out the code so that it works properly and isn’t too complicated so it took a long time. Now all that remains is to tidy it up and add comments. I briefly described the algorithm in the docstring and hopefully it will make the code clear to whoever might need to work with it in the future. I think this can be added in a separate PR once the current one is merged, though if I have to make any more corrections to the current one, I might push this as well.

The title of the post is to do with the new PR I sent this week in which I added some of the PermutationGroup methods to the FpGroup class so that they can work with finite instances of FpGroup. I didn’t actually need the presentation PR for it, homomorphisms were enough. At the moment, when a permutation group method returns a group, the equivalent fp group method returns its generators. An alternative to it would be to return an instance of FpSubgroup on the generators from where its FpGroup presentation can be found via to_fp_group method. Or, now that the presentation PR is merged, another possibility would be to run presentation on the permutation group returned by the permutation method and return the result together with a homomorphism from it to the original group - though that would probably be too time-consuming so shouldn’t be the default.

For the rest of this week, I’m going to keep working on the Sylow PR and the permutation group methods one if its review starts this week. I’ll also try to speed up the _finite_index_subgroup method and look into the strong generator algorithm for FpGroup presentations.