The Plan (Part II)

At the beginning of this week I finished writing the first draft of the homomorphism class, at least as much of it as is possible without the rewriting systems for FpGroups. Homomorphisms from FpGroups to PermutationGroups are fully implemented though I’m sure corrections will be made as the PR is reviewed. I mentioned that I wasn’t planning on sending the PR until after the rewriting systems but there is quite a bit there and a lot of it can be reviewed (and even merged) now.

It took a bit longer than I expected because the rewriting for permutation groups wasn’t quite what was necessary for homomorphisms. I knew that there was a function returning the unique normal form of a permutation in the group (the coset_factor() method) and had assumed that that would be enough but the normal form wasn’t in terms of the generators, nor was there an easy way to rewrite it in terms of the generators. So I had to modify the schreier_sims() method that finds the strong generating set and the elements that make up the normal form returned by coset_factor() to keep track of which generators in what order are multiplied to obtain them. Then I wrote a method that would write any permutation in the group as a product of the strong generators and, since I had the information about the make-up of the strong generators, this could easily be rewritten in terms of the original generators. Doing this was a bit fiddly and took a while. Though I suppose it could be counted as part of the work on rewriting systems.

The rewriting systems for FpGroups are coming along. At the moment, it is a new class RewritingSystem which FpGroups will probably have an attribute for. I’ve almost finished implementing the Knuth-Bendix completion algorithm and that was most of the work. Though there is also the matter of reduction. At the moment I’m using the eliminate_words() method from the FreeGroupElement class - it takes a dictionary of substitutions (in this case a dictionary of reduction rules) and substitutes all of them into a given word, if possible. But that isn’t very efficient for long words and large reduction dictionaries since eliminate_words() will scan the word from the start every time it tries to perform a new substitution. The approach I’ve seen described in papers on rewriting systems is to construct a finite automaton to perform the reduction and modify it every time a new rule is added. This would somewhat increase the time taken to initiate the system and to make it confluent but would also make word reductions much quicker. However, it could also take a while to actually implement. I’m unsure if it’s worth doing it now - perhaps, I could add it later, when the rest of my project is done.

Anyway, I was going to use this post to outline a schedule for this month’s work, like I did in the first post. Looking back at the Timeline I sketched in my proposal, I seem to have given myself 2 weeks for implementing the rewriting systems. This estimate wasn’t unreasonable, considering the unexpected matter of rewriting in permutation groups I had to deal with in the first half of the week and the reading I had to do to get a better idea of Knuth-Bendix. But if I don’t implement finite automatons for reductions right now, I think I should be able to send the rewriting PR by Thursday (probably earlier). With this in mind, my plan for the month is roughly as follows.

The Plan (continued)

• 3 July - 6 July: finish the RewritingSystem class.
• 6 July - 16 July: implement finite presentations for PermutationGroups (this should be plenty of time considering that I made a start on this during the application period)
• 17 July - 23 July: complete the homomorphism implementation to allow homomorphisms from PermutationGroups and to FpGroups. Implement the permutation presentation for finite FpGroups.
• 24 July - 30 July: Set up the use of PermutationGroup methods for FpGroups via homomorphisms.

So by the end of the month, the homomorphism functionality should be complete, so should be the switching between FpGroup and PermutationGroup presentations (where it is possible, i.e. finite FpGroups). Making PermutationGroup methods work for FpGroups properly could take more time but if everything goes more or less according to plan, I should have most of August to try and implement Sylow subgroups for PermutationGroups (there is a chapter on it in “The Handbook of Computational Group Theory”), look into the construction of finite automatons for word reduction or automatically grouping subwords of group words, like (a*b)**2 instead of a*b*a*b, or anything else project-related really. That’s the optimistic scenario of course, provided no sudden terrible complications arise which can never be guaranteed.