Not really blogging

A. Makelov

Google Summer of Code 2012: Week 12

Hi all, here’s a brief summary of the 12th week of my GSoC:

  • Centralizers got some more attention since there were several bugs in the implementation from last week; this also exposed a bug in .subgroup_search() as it is on sympy/master right now. Fortunately, I located it and fixed it earlier today, so the fix for .subgroup_search() will be contained in my next pull request. In fact, it is just three more lines that should be added. Namely,
    # line 29: set the next element from the current branch and update
    # accorndingly
    c[l] += 1
    element = ~(computed_words[l - 1])
    

    should be replaced with

    # line 29: set the next element from the current branch and update
    # accorndingly
    c[l] += 1
    if l == 0:
        element = identity
    else:
        element = ~(computed_words[l - 1])
    

    since we might be at the bottom level with l=0. In this case, python doesn’t yell at you for looking up computed_words[-1] since negative indices wrap around the list in python. Yet another silly mistake that’s incredibly hard to track down! I hope that it will work properly from now on, and I’ll have to include some more tests to it.

  • The description of the algorithm for finding the center in polynomial time given in [1] didn’t really make sense to me, so instead a straightforward one,
    def center(self):
        return self.centralizer(self)
    

    was used. This can be updated later when I (or someone else) figures out the polynomial-time algorithm.

  • A new, faster algorithm for finding normal closures: this one uses the incremental version of Schreier-Sims, and some randomization. It’s described in [1].
  • Some applications of normal closure: the derived series, lower cenral series, the commutator of two subgroups of a group, nilpotency testing. Now we have things like this:
    In [68]: from sympy.combinatorics.named_groups import *
    In [69]: S = SymmetricGroup(4)
    In [70]: ds = S.derived_series()
    In [71]: len(ds)
    Out[71]: 4
    In [72]: ds[1] == AlternatingGroup(4)
    Out[72]: True
    In [73]: ds[2] == DihedralGroup(2)
    Out[73]: True
    In [74]: ds[3] == PermutationGroup([Permutation([0, 1, 2, 3])])
    Out[74]: True
    

    demonstrating the well-known normal series of groups e < K_4 < A_4 < S_4 that solves the symmetric group on 4 letters. Note that the normal closure algorithm was already there thanks to the work of Mario, I just improved it a bit and added some applications.

  • Moved DirectProduct() to a new file, group_constructs.py, that is planned to hold functions that treat several groups equally (for one other example, the commutator of two groups in the full symmetric group) rather than treating them in some sort of subgroup-supergroup relationship (such as .centralizer()).

I wrote docstrings for the new stuff, and my current work can be found on my week10 branch. There will be some comprehensive test following the new additions (and I’ll need GAP to verify the results of some of them, probably). It seems that Todd-Coxeter won’t happen during GSoC since there’s just one more week; instead, I plan to focus on improving disjoint cycle notation and group databases.

[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

About these ads

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: