Final Report

GSoC is coming to an end, and it’s time for the final report (which is not to say that I won’t make a couple more posts after this). In this post I will summarise the work I’ve done so far with links to PRs in approximately the order they were submitted.

First of all, looking at my proposal, I’d say that I have done all that was planned plus some minor additional things here and there (discovering and fixing bugs, modifying existing functions and occasionally adding new ones beyond what was planned). However, there is certainly room for improvement, and I will mention where the work could continue as I go through the PRs. So here it is.

1. The subgroup method PR. Here I added subgroup() methods to the PermutationGroup and FpGroup classes. There were some discussions as I wondered if FreeGroup class could be implemented differently, but it was mostly straightforward. Perhaps, it would be useful to add a keyword argument or something like that to FpGroup’s subgroup() to allow the user to get hold of the injective homomorphism from the subgroup to the parent group.

2. Improvements to simplifying subgroup presentations. I didn’t look at _elimination_technique_2 because it is not used anywhere in the code at the moment but it could probably be improved as well, especially now that some new FreeGroupElement methods are available: one of them is the general substitution of words that I implemented in this PR and, as I recall, I modified a few other FreeGroupElement methods there, as I discovered that some of them were buggy or not general enough. In a later PR (#9), I united the main elimination technique (which removes redundant generators) and the simplification of relators into one function simplify_presentation that can be applied to any group, not just as part of reidemeister_presentation (used for finding presentations of subgroups).

3. The Smith Normal form PR. This is the only time I did work somewhere other than the combinatorics module during the project. I implemented the Smith Normal form for principal ideal domains because it could be used to test if a group is infinite (not a definitive test, as if the test is negative, we can’t conclude the group isn’t infinite). It’s a bit awkward to use at the moment because the user has to add manually a certain attribute to their matrix and it won’t be resolved until some further work is done on matrices. I wrote a bit more about it in the relevant post.

4. Changing the order method. The previous PR allowed returning S.Infinity as the order of the group in some cases where in the past the order() method wouldn’t terminate. This PR extended it even further by calculating the order in stages. First, it attempts to find a finite index subgroup and, if it succeeds, it finds the presentation of this subgroup and applies order() to it. In some cases, other methods can determine that this subgroup is infinite in which case, of course, the whole group is infinite. If it’s finite, then the order of the group is the index times the order of the subgroup. It is still possible that this never terminates if a finite index subgroup is not found, but it’s an improvement. It can be faster than direct coset enumeration on the trivial subgroup (that was used before) but occasionally it seems too slow for even smallish groups. Usually, the slowest part is finding the subgroup’s presentation but sometimes it’s the search for this subgroup that takes up the time. I feel that more work should be done here to make it more efficient.

5. The homomorphism PR. This was a substantial PR: not only did it introduce two new classes (GroupHomomorphism and FpSubgroup), it also involved quite a lot of work in the PermutationGroup class in order to implement the method that expresses a given permutation in terms of the group’s strong generators. At this stage only homomorphisms from FpGroup to PermutationGroup were fully implemented. The kernel computation can’t handle infinite domains - maybe, this could be addressed in the future.

6. The Rewriting System PR. This was probably the hardest thing in the project and it probably took the longest to get merged after its review started (or at least it felt the longest). Even after it did, some problems kept coming up. It seems stable at the moment but it could certainly do with more work. One thing that comes to mind is the reduction method: it is possible to do it more efficiently with an automaton which is built and modified as more reduction rules are added to the system. Also, perhaps, the completion algorithm could be made more efficient in some way.

7. Fixing a bug in reidemester_presentation. Discovered by accident, there was a small bug in reidemeister_presentation that led to order() returning wrong answers in some specific cases.

8. FpSubgroup’s __contains__ method. After the homomorphism PR was merged, it was discovered that occasionally the tests involving kernels would time out. This was because FpSubgroup’s __contains__ method would go into an infinite loop on encountering elements of the conjugate form a**-1*w*a. It took some time to work out a way of dealing with it.

9. Finite presentation of permutation groups. This is something I keep working on. The general algorithm is implemented and merged, however, the efficiency could potentially be improved by using a different method based on the group’s strong generating set. I have tried one implementation but it’s not clear when exactly it is more efficient. Currently, I am trying to implement a different, hopefully more consistently efficient, algorithm.

10. Fixing a bug in minimal_block. A small bug in minimal_block was discovered during the implementation of sylow subgroups.

11. Adding the other homomorphism cases. This PR enabled homomorphisms with FpGroup as codomain (became possible after merging the rewriting PR) and PermutationGroup as domain (provided the keyword argument check was set to False).

12. Sylow subgroups PR. This one also took a while. The main function is fairly long and it required implementation of two types of action homomorphisms and a method for finding all minimal block systems of a group. At the moment another related PR (#16) is being reviewed: it treats symmetric and alternating groups separately as the generators of their Sylow subgroups can be written down.

13. PermutationGroup methods for FpGroup. This is something that gave me the idea for the project in the first place: many methods for permutation groups are already available while finitely presented groups have limited functionality. However, it’s possible to use an isomorphism between a finite FpGroup and a relevant permutation group to perform computations in the latter and then go back to the former. This is precisely what this PR does for many permutation group methods. It is still being reviewed.

14. Storing coset tables in _finite_index_subgroup. Until the presentation PR, it wasn’t possible to get hold of an incomplete coset table for which coset enumeration returned with an error (for example if the maximum number of entries was exceeded). After it was merged, I made use of this new feature in the search for a finite index subgroup (used by FpGroup’s order() method). This somewhat decreased the required time as coset tables didn’t have to be recomputed.

15. Checking that a homomorphism from PermutationGroup is well defined. After the presentation PR was merged, it became possible to complete the homomorphism class by enabling the check for whether given generator images define a homomorphism when the domain is a permutation group. Not merged yet.

16. Sylow subgroups for Sym(n) and Alt(n). A separate method for computing Sylow subgroups of alternating and symmetric groups, to be used as part of the main sylow_subgroup method. This hugely improves the performance in the case of alternating and symmetric groups. Still being reviewed.

A couple other PRs had to do with renaming attributes (this one and this one) or moving code around (for example, moving all of the coset table and coset enumeration functions to the file coset_table.py in this PR). These didn’t include any actual work so I didn’t include them in the main list.

Hopefully, this report will be of use to whoever else might be interested in developing the group theory module. I plan to continue working on it myself for some time, though probably less productively as the new academic year starts soon.

Overall, this was a fun summer and I enjoyed working on this project. I’d like to thank Google for sponsoring it, SymPy for giving me the opportunity to participate and my mentor Kalevi (jksuom) for giving me guidance and useful suggestions on my code and generally being very helpful. :)