Not really blogging

A. Makelov

Google Summer of Code 2012: Week 6

Hi all,

here’s a brief summary of what I’ve been doing for the sixth week of my GSoC:

  • Submitting, fixing and finally getting merged my second pull request. Thanks a lot to Stefan and my mentor David for reviewing it! now we have a lot more functionality for handling permutation groups.
  • Some more debugging on PRINTELEMENTS (I was talking about it in the third bullet of my post from last week). It turned out that it was still doing something slightly wrong but now it’s the way it should be. Apart from that, its speed was optimized by a different means of storing computed subwords of the group element being computed as a word in elements from the basic transversals (this assumes some knowledge of the theory of bases and strong generating sets; for a discussion, see [1],  pp.87-88,  pp.108-110)
  • In the comments on my post from last week, I got a clarification from Mario on the struggles with _coset_repr that I discussed in the third bullet of last week’s post. Now I’ll be able to use the current deterministic implementation of the Schreier-Sims algorithm whenever a BSGS is needed (after some minor modifications to the attributes of a PermutationGroup that are assigned after running Schreier-Sims).
  • Finally, the implementation of the algorithm BASESWAP ([1],  pp.102-103). This function is necessary for SUBGROUPSEARCH ([1], p.117) which in turn is necessary for the group intersection algorithm. This deserves some special attention – I have strong reasons to believe that the pseudocode & its discussion in [1], pp. 102-103 contain the same mistake repeated several times. Namely, I think that line 3 of the pseudocode for BASESWAP should read |\beta_i^{\left\langle T\right\rangle}|\neq s instead of |\beta_{i+1}^{\left\langle T\right\rangle}|\neq s. At first I implemented the algorithm the way it was given is pseudocode, and lost many hours (it wasn’t working) until I discovered that this little detail might be wrong. Now, I shall assume the notation used in [1] in order to follow their argument as closely as possible. My reasoning is as follows: as we change the set T during the run of BASESWAP, we finally want to have \left\langle T\right\rangle = H := G^{(i)}_{\beta_{i+1}}=G_{\beta_1, \beta_2, \ldots, \beta_{i-1}, \beta_{i+1}}. The last line |G^{(i)}| = |\Delta^{(i)}||\Delta^{(i+1)}||G^{(i+2)}| = |\beta_{i+1}^{G^{(i)}}||H| on page 102 of [1] is indeed correct by a straightforward application of the orbit-stabilizer theorem; so if we put s = \frac{|\Delta^{(i)}||\Delta^{(i+1)}|}{ |\beta_{i+1}^{G^{(i)}}|} we indeed have |H| = s|G^{(i+2)}|. Up to this point, I believe the book. However, after that they say that the last equation implies that s = |\beta_{i+1}^H|. Looking more closely, by definitions we recall that H = G_{\beta_1, \beta_2, \ldots, \beta_{i-1}, \beta_{i+1}}, G^{(i+2)} = G_{\beta_1, \beta_2,\ldots, \beta_{i+1}}. Hence, G^{(i+2)} is the stabilizer of \beta_i in H, thus by the orbit-stabilizer theorem we have |H| = |\beta_i^H||G^{(i+2)}|, hence we must have |\beta_i^H| = s, not |\beta_{i+1}^H|=s. This same mistake (\beta_{i+1} instead of \beta_i) appears several other times (in fact, all the times) in the discussion of BASESWAP and once in the pseudocode. Now that I changed it to \beta_i, the implementation doesn’t break and behaves as expected. I also implemented the randomized version described in [1], p.103 and [2], p.98, and it also behaves as expected. I’d be extremely happy if anyone else is willing to go over this and check whether what I’m saying is true; I’m pretty sure it is, but I didn’t expect to find such a serious mistake in that book. I’m willing to provide their argument in its entirety or clarify the notation, just shoot me a comment below.

So, that’s it for now. I’m in the process of furnishing my code for the next pull request (which will hopefully be submitted tomorrow), and then I’ll resume my work on subgroup intersections.

Edit: My pull request has not been submitted yet since writing the docstrings and tests took me longer than expected. The current state of it is available here, if anyone wants to take a look at how things are going. I still have to write some more tests, and hopefully will push it today for review.

Edit#2: The pull request is finally out. It is some 1300 lines of code, so if people object I can remove some of the stuff and save them for a future pull request.

[1] 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-58488-372-3

[2] Permutation Group Algorithms, Ákos Seress, Cambridge University Press

About these ads

3 responses to “Google Summer of Code 2012: Week 6

  1. Aaron Meurer July 5, 2012 at 7:47 pm

    This is why it’s important to fully understand the theory, even when implementing algorithms that are given in pseudocode. Sometimes the pseudocode will have typos!

    Like

  2. amakelov July 5, 2012 at 7:57 pm

    I totally agree with that. From now on, I’ll be closely (and skeptically) following the math behind the algorithms…

    Like

  3. Pingback: Google Summer of Code 2012: Week 8 « Not really blogging

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Rational Altruist

Adventures of a would-be do-gooder.

Gowers's Weblog

Mathematics related discussions

What's new

Updates on my research and expository papers, discussion of open problems, and other maths-related topics. By Terence Tao

Stefan's Blog (archive, for news see blog.krastanov.org)

Most of the blog moved to blog.krastanov.org

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: