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

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.