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

Strong Presentation problems

The final evaluation period has started, and I’ll be writing a post with the list of all submitted PRs and some summarising comments later this week (perhaps, tomorrow). Overall, I have done all that was planned though there is room for improvement as is the case with the finite presentation of permutation groups algorithm.

I have tried out computing a presentation on basic stabilizers, i.e. starting with the presentation of the smallest basic stabilizer and building up from it. This should probably be available in any case because it gives a strong presentation which could be desirable (it has more generators but on the other hand, fewer relators; theoretically, if known, these relators could be used to check if a homomorphism is well-defined a bit quicker). However, I was looking to see if this would be faster than the general version. What I found was that in some cases it’s considerably faster and in others much slower, with no clear pattern. For example, it doesn’t perfectly correlate with the size of the group or the number of strong generators. The slowest part is filling in the coset tables for intermediate presentations so I looked if the difference correlates with the index of the subgroup on which a presentation is built, or the difference between the generators of the subgroup and the original group, or their multiple (i.e. the size of the unfilled part of the table) and none of it properly accounts for the difference. There would seem to be a number of factors at play. I’m thinking of writing a simple function that generates a random group with a fixed degree and use it to collect data for the various parameters of many different groups. That might give me more to go on than the examples I make up myself. Not sure how successful this would be though. At the moment, I’m not certain I’d be able to figure it out by the end of this week. I’ll probably carry on the work until after the end of GSoC.

I sent a couple of small PRs last week. One for checking homomorphisms with permutation group domains (using the general presentation method for now) and the other is with the more efficient method of computing Sylow subgroups of alternating and symmetric groups that I mentioned in the previous post. These two and the PR implementing permutation group methods for finitely presented groups are still being reviewed.

On a different note, lately I’ve been thinking of extending the FreeGroupElement class to handle group words with symbolic powers, e.g. a**n where n is an instance of Symbol. I don’t see any reason why it shouldn’t be available in general (though we’d have to be careful to raise errors where appropriate when someone tries to use this in methods; or to modify some methods to handle them if possible) and I was thinking of using something like this when implementing the FpSubgroup class so it can probably be put to use in some situations. One would also need to have a subs method for substituting desirable powers. This, along with the earlier idea of grouping things like a*b*a*b into (a*b)**2, could be another thing I could work on after GSoC.

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.

Completing homomorphisms

I sent the PR with the other homomorphism cases a week ago, so about a day after my last post. The work required for the main part of the PR wasn’t really complicated but it took a while to get merged (earlier today) because some more problems showed up in the rewriting system part.

It started off with Kalevi noticing that in the case of a free abelian group, the list of rewriting rules after initiation seemed incomplete - it so happened that the test didn’t pick up on it because it didn’t need the missing rules. In itself, that wouldn’t be much of a problem because the missing rules could be added during the run of make_confluent but is_confluent was already True - that was definitely wrong. So for one thing, _check_confluence wasn’t working properly and also I thought that the type of rules that wasn’t added during rule initiation, could be added as another case - if it could be done in place, why wait till it’s discovered by the double loop in make_confluent. I made a few little changes throughout the code to fix things but ultimately, it was the inadequacy of add_rule that was causing problems.

When a pair of words is given to add_rule, it first multiplies them by the inverse of the first element of the longer word until the length difference is 0, 1 or 2 (greater length differences are redundant when the smaller length differences are in the rules dictionary). Then it does the same on the other (right) side which leads to a different set of rules. We could obtain even more rules right here, without waiting for make_confluent, if we allow switching sides, i.e. not just continuously multiplying on the right or on the left, but perform some left multiplications after several on the right, etc. This makes make_confluent a little more efficient as more rules are discovered at one time but trying all possible combinations of sides would probably take too much time without actually being productive. At the moment, when the length difference becomes sufficiently small, instead of adding the rule directly, add_rule calls itself recursively which allows for some side switching. Perhaps in the future, it would seem fit to try all combinations. A couple of days ago I added a rules cache to prevent repeating the work that has already been done by the function so maybe it won’t cause too much of a slow-down in practice.

After this, one rule was still missing. I reread the code several times and it took a while to work out that the problem was what seems quite obvious now. When a pair of words w1, w2 of the same length is given to add_rule, the only rule that was added was w1: w2 for w1 > w2. But another possibility right there could be w2**-1: w1**-1 provided w2**-1 > w1**-1. Normally, this inverse rule doesn’t need to be added because if len(w1) > len(w2), then w1**-1 > w2**-1 and w**-1: w2**-1 is implied by how word reduction is set up. Adding this last case solved the issue.

There were some other little improvements. For example, make_confluent has been made to returns a boolean at all times, not just when checking if the system is confluent. This could be used to see if it is successful. I also spotted an error in the kernel computation method that hadn’t come up before only by sheer luck.

Now that all the basic homomorphism functionality is available, I can have a go at extending the FpGroup class with PermutationGroup methods. I might be able to get it to work without the finite presentation of permutation groups PR (it hasn’t been reviewed yet) but I’m not entirely sure yet.

Another thing on my hands is sylow subgroups. I actually thought I got them to work several days ago but then one of the test groups (SymmetricGroup(10)) revealed a bug in the _strong_gens_slp attribute. It wasn’t caused by the sylow method and only comes up after computing a stabilizer or a normalizer - something I only realised yesterday; this bug really confused me for a while. I did fix it now but a different problem came up and what worked before no longer does. I don’t see why the bug fix would lead to it but evidently it did… So still trying to sort it out.

Update: Have just worked out that sylow thing. Turned out minimal blocks weren’t being computed properly (my fault: I wrote a separate function that should have outputed all minimal block systems but failed on minimality). So now all that remains is to do some more testing and tidy up the code, and I can send a PR with it in a day or so (if no other bugs turn up, that is).

The rewriting PR and Sylow Subgroups

The rewriting PR only got merged today. Firstly, it took several days to sort out the FpSubgroup’s __contains__ method (in this PR). Secondly, my mentor pointed out a case I overlooked in the add_rule routine, and once I corrected it, another problem presented itself. It wasn’t to do with add_rule but adding the overlooked case made it possible for the tests to pick up on it (luckily). The problem was that sometimes make_confluent would try to use a non-existent key for the dictionary of rewriting rules. This happened because make_confluent is set up in such a way that if sufficiently many rules are added, _remove_redundancies method is called, and this removes or modifies some of the existing rules, and the function didn’t account for this change properly. It took me several goes until I finally got it. And while I was at it, I noticed yet another bug which took some time to track down. Turned out that “for” loops don’t always properly iterate over lists that are changed inside the loop (spefically, they ignore newly appended elements). I didn’t think it would be a problem because I have done similar things before in python. I ended up replacing it with a “while” loop like:

>>> while i < len(some_list):
>>>    some_list.append(new_element)
>>>    i += 1

and that worked properly. Still not entirely sure what happened there: appending elements inside a for loop in the terminal shell doesn’t cause such problems - I should probably look into that more at some point, for future reference.

So I only began working on completing the other homomorphism cases today (not counting what I have sketched in the previous couple of weeks). I’ll try to send a PR with some of it in several days. At this point, I should be able to do everything except checking that a homomorphism from a permutation group is well defined. For that I’ll need the presentation PR and it’s quite substantial so its review will almost certaintly take more than several days. I’m planning to add the keyword argument check to the homomorphism function so that if check==False, the given images are assumed to define a homomorphism. I found it useful in some of the work I was doing last week.

I decided to work on computing sylow subgroups, and as part of it, wrote two new homomorphism functions specifically for permutation groups: orbit_action_homomorphism and block_action_homomorphism for defining homomorphisms induced by the action of the group on a union of orbits or a block system respectively. These are of course homomorphisms between permutation groups and there is no need to check if they are well-defined so it was possible to create them without the presentation PR. I don’t know if it will stay that way as it hasn’t been discussed yet but it seemed appropriate to have them as separate functions in the homomorphisms file. Also, I found a bug in the minimal_block method while testing block_action_homomorphism yesterday but it’s not anything major and the fix for it will likely be merged soon. There was some trouble with Travis today though.

The actual computation of sylow subgroups is going to be a PermutationGroup method sylow_subgroup() and it already works for some cases so it’s going well. However, I am going to pause it for now to finish homomorphisms.