GSoC Week 6
Hi everyone.
First of all the good news, I have passed the mid-term evaluations. I received the feedback from Kalevi, “I have had some problems with the blog posts.”. Though Kalevi, mentioned to not take the post seriously. Well, not to say, that is definitely true. I don’t claim that I will be able to remedy this, but lets see what happens.
Kalevi, had sent me a mail, mentioning “next things to do”, it included “Cosets in Permuations group” and “Finitely Presented Abelian groups”. (its been quite sometime since that mail). It was more of my decision to implement the topic of “presentation of subroups”. To be true, I particularly chose this topic, since that makes the output of out work done till now, to look beautiful :) . Earlier I had a constant doubts when I was making proposal about what it exactly means by “presentation of subgroups”. So while I read the examples from the Handbook, it became clear to me.
As to the progress in the topic, here’s what we have done, I opened the PR on sunday. This week we started with the implementation of subgroup presentations. There are two methods to compute “presentation of a subgroup”, first being called “computing presentations on schreier generators” also called the Reidemeister Schreier procedure. Since we have already implemented the “Todd Coxeter” procedure, which is used as the first step in Reidemeister Schreier for coset enumeration. It uses a routine which is called “define_schreier_generators” Second being “computing presentation on the generators of subgroup”. Well the pseudo code is there for both the two implementations. The code of
| The important part of finding the “presentation of subgroup” being simplifying the “presentations”, i.e reducing the three factors | X | (no. of subgroup generators), | R | (no. of subgroup relators) and l (total length of subgroup relators). Though there doesn’t seem to any pseudo code available anywhere for the implementation (this makes it quite interesting to implement). But the paper by Havas Reidemeister Schreier program neatly explains the things. |
Last 2 days were spent on trying to make elimination_technique_1 work. Its still not
fully functional, since it still returns some dependent relators as a part of the presentation.
As for an example, currently Reidemeister Schreier procedure presentation works this way.
>>> F, x, y = free_group("x, y")
>>> f = FpGroup(F, [x**2*y**2, y**-1*x*y*x**-3])
>>> H = [x]
>>> reidemeister_presentation(f, H)
([x_1], [x_1**-4, x_1**-8])
Two things need to be fixed here. First being, removal of -ve powers of single syllable relators, $x_1^{-4}$ -> $x_1^4$, similarly for the other relator. Second thing being, since $x_1^4 = 0$ implies that $x_1^8 = 0$ (dependent relator) so the relator should be removed. Perhaps the issue with this is, where should the code for checking this dependence be introduced? Kalevi seems a bit busy these days with other project. That is not the issue. I believe there may be something more to the simplification in the “Handbook”, (have been referring to [2] for the elimination of generators, relators and simplification of presentations).
Yesterday, I Thought of focussing on a new topic “simplification of presentations”, the method
is short descripted in [2], but that is sufficient enough. It starts by checking whether any relator
is of the form $gen^n$, where $n \in \mathbb{N}$. If any such relators are found then all other relators
are processed for strings in the $gen$ known order. All string length exceeding length $n/2$ are
replaced by their shortest equivalent. Further, for even n strings gen$^{-n/2}$ replaced by
gen$^{n/2}$. I have written its code, perhaps it only requires a few more tests to be added
to it.
I think I will be busy with “presentation of subgroups”, this week and next week as well.
##References
-
Derek F. Holt, Bettina Eick, Bettina, Eamonn A. O’Brien, “Handbook of computational group theory”, Discrete Mathematics and its Applications (Boca Raton). Chapman & Hall/CRC, Boca Raton, FL, 2005. ISBN 1-5848-372-3 .