The homomorphism class

At the beginning of the week, all of my previous PRs got merged. This is good. Also, the homomorphism class is now mostly written with the exception of the kernel computation. The kernel is the only tricky bit. I don’t think there is any general method of computing it, but there is a way for finite groups. Suppose we have a homomorphism phi from a finite group G. If g is an element of G and phi.invert(h) returns an element of the preimage of h under phi, then g*phi.invert(phi(g))**-1 is an element of the kernel (note that this is not necessarily the identity as the preimage of phi(g) can contain other elements beside g). With this in mind, we could start by defining K to be the trivial subgroup of G. If K.order()*phi.image().order() == G.order(), then we are done. If not, generate some random elements until g*phi.invert(phi(g))**-1 is not the identity, and redefine K to be the subgroup generated by g*phi.invert(phi(g))**-1. Continue adding generators like this until K.order()*phi.image().order() == G.order() or finite G this will always terminate (or rather almost always considering that the elements are generated randomly - though it would only not terminate if at least one of the elements of G is never generated which is practically impossible).

This is how I am going to implement it. I haven’t already because I’ve been thinking about some of the details of the implementation. One thing that could be problematic is multiple calls to reidemeister_presentation() to compute the presentation of K at each step. As I’ve discovered when I was implementing the search for finite index subgroups last week, this can be very inefficient if the index of K is large (which it could well be for a small number of generators at the start). After giving it some thought, I realised that actually we could completely avoid finding the presentation because K’s coset table would be enough to calculate the order and check if an element belongs to it. Assuming G is finite, K.order() can be calculated as the order of G divided by the length of the coset table so the knowledge of the generators is enough. And for membership testing, all that’s necessary is to check if a given element stabilises K with the respect to the action on the cosets described by the coset table. And that should be a huge improvement over the obvious calls to the subgroup() method.

Actually, FpGroups doesn’t currently have a __contains__() method so one can’t check if a word w is in a group G using w in G. This is easy to correct. What I was wondering was if we wanted to be able to check if words over G belong to a subgroup of G created with the subgroup() method - that wouldn’t be possible directly because subgroup() returns a group on a different set of generators but it wouldn’t be too unreasonable to have SymPy do this:

>>> F, a, b = free_group('a, b')
>>> G = FpGroup(F, [a**3, b**2, (a*b)**2])
>>> K = G.subgroup([a])
>>> a**2 in K
True

I asked Kalevi about it earlier today and they said that it would be preferable to treat K in this case as a different group that happens to be linked to G through an injective homomorphism (essentially the canonical inclusion map). If we call this homomorphism phi, then the user can check if an element of G belongs to the subgroup represented by K like so: a**2 in phi.image(). Here phi.image() wouldn’t be an instance of FpGroup but rather of a new class FpSubgroup that I wrote today - it is a way to represent a subgroup of a group while keeping the same generators as in the original group. It’s only attributes are generators, parent (the original group) and C (the coset table of the original group by the subgroup) and it has a __contains__, an order() and a to_FpGroup() methods (the names are self-explanatory). For finite parent groups, the order is calculated as I described above for the kernel and for the infinite ones redeimeister_presentation() has to be called. The injective homomorphism from an instance of FpGroup returned by subgroup() would need to be worked out during the running of reidemeister_presentation() when the schreier generators are defined - this is still to be done.

Another thing I implemented this week was an improved method for generating random elements of finitely presented groups. However, when I tried it out to see how random the elements looked, I got huge words even for small groups so I didn’t send a PR with it yet. Once I implement rewriting systems, these words could be reduced to much shorter ones. Speaking of rewriting systems, I think it could be good if the rewriting was applied automatically much like x*x**-1 is removed for FreeGroupElements. Though I suppose this could be too inefficient some times - this would need testing. This is what I’ll be working on this week.