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.