Final Report
25 Aug 2017GSoC 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.

The
subgroup
method PR. Here I addedsubgroup()
methods to thePermutationGroup
andFpGroup
classes. There were some discussions as I wondered ifFreeGroup
class could be implemented differently, but it was mostly straightforward. Perhaps, it would be useful to add a keyword argument or something like that toFpGroup
’ssubgroup()
to allow the user to get hold of the injective homomorphism from the subgroup to the parent group. 
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 newFreeGroupElement
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 otherFreeGroupElement
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 functionsimplify_presentation
that can be applied to any group, not just as part ofreidemeister_presentation
(used for finding presentations of subgroups). 
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. 
Changing the order method. The previous PR allowed returning
S.Infinity
as the order of the group in some cases where in the past theorder()
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 appliesorder()
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. 
The homomorphism PR. This was a substantial PR: not only did it introduce two new classes (
GroupHomomorphism
andFpSubgroup
), it also involved quite a lot of work in thePermutationGroup
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 fromFpGroup
toPermutationGroup
were fully implemented. The kernel computation can’t handle infinite domains  maybe, this could be addressed in the future. 
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.

Fixing a bug in
reidemester_presentation
. Discovered by accident, there was a small bug inreidemeister_presentation
that led toorder()
returning wrong answers in some specific cases. 
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 forma**1*w*a
. It took some time to work out a way of dealing with it. 
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.

Fixing a bug in
minimal_block
. A small bug inminimal_block
was discovered during the implementation of sylow subgroups. 
Adding the other homomorphism cases. This PR enabled homomorphisms with
FpGroup
as codomain (became possible after merging the rewriting PR) andPermutationGroup
as domain (provided the keyword argumentcheck
was set toFalse
). 
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.

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.

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 byFpGroup
’sorder()
method). This somewhat decreased the required time as coset tables didn’t have to be recomputed. 
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.

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