The start

GSoC officially starts tomorrow but I’ve already begun working on my project because of exams later in June. So far everything is going according to plan. I’ve implemented the subgroup() method for PermutationGroups and FpGroups as well as is_subgroup() for FpGroups. That was straight-forward except this one moment where I wanted to avoid creating a new instance of FreeGroup and rewriting the relators returned by reidemeister_presentation() in terms of this new instance because it seemed inelegant. I spend quite a while trying to come up with a better way and even started thinking of reimplementing the FreeGroup class but after a discussion with one of my mentors on SymPy’s Group Theory channel decided to create a new instance after all. It shouldn’t affect the performance too much anyway and reimplementing a whole class would be quite extreme.

Then I looked into improving the techniques for simplifying the presentation of subgroups. I hadn’t been sure about whether there would be much to do but actually I found that the code had quite a few redundant bits and there were some more serious potential problems with it, like a loop that deleted elements of the list over which it iterated. I ended up rewriting it to be more readable and making sure the list of relators is traversed properly. Additionally, the reidemeister_presentation() code used to apply the simplification techniques 20 times in a for loop which in some cases would be excessive and in others not enough - I replaced it with a while loop so that the representaion is simplified until no further improvement is achieved.

While I was at it, I found myself modifying some of the FreeGroupElement methods either to extend their functionality or because I noticed that their implementation would lead to bugs in some special cases. I also added a couple of new methods for manipulation of group words. Intuitively, FreeGroupElement words are just symbolic expressions on non-commutative (in the general case) symbols that only admit integer powers. But their implementation in SymPy is different from the regular symbolic expressions which are instances of the Expr class. As a result, the Expr methods, e.g. subs() or simplify() can’t be used with them directly (though of course, theoretically, one could build an equivalent symbolic expression out of a FreeGroupElement, apply the desired Expr method, make sure no fractional powers appear and go back) so equivalent methods have to be written separately. I have extended the group word substitution to probably all (or at least most) cases one might need. Simplification, on the other hand, is still missing. That said, the simplify() method of the Exrp class doesn’t currently do much in terms of simplification of non-commutative expressions so it couldn’t be used anyway (perhaps, some other method would be appropriate but I’m not sure which). However, unlike instances of Expr, group elements only involve one binary operation so the problem is somewhat easier (conceptually). The only real simplification one can make is finding powers of subwords and collecting them into one thing. Say, if we have the word x*y*x*y*x*y, a simpler way to write it would be (x*y)**3 and it would be good to have that done automatically. I might work on implementing that sort of thing somewhere along the way because then simplifications for reidemeister_presentation() can be improved even further, and the output relators will be more readable. Plus it’s just a nice feature to have, though at present I’m not sure about how exactly I would go about that efficiently and how to best store the simplification so that it doesn’t need to be done again.

The PRs I’ve sent so far are here and here and are currently still being reviewed.

The next thing I’m going to work on are a couple of methods that could be used to determine if a given FpGroup is infinite. The one I plan to do first is considering the abelianisation of the group, writing the relators in the form of an integer matrix and essentially finding its Smith Normal form. This will probably occupy me for the next week.