Not really blogging

A. Makelov

Google Summer of Code 2012: Week 8

Hi everyone, here’s a brief summary of what I’ve been doing for the 8th week of my GSoC:

  • The issue with the BASESWAP function on page 103 of [1] that I discussed here is now resolved: one of the authors, Professor Derek Holt at Warwick, replied to me that this is indeed a typo and added it to the errata page here.
  • I studied the SUBGROUPSEARCH algorithm described in [1] in more depth. It takes as input a group G with a BSGS, a subgroup K < G with a BSGS having the same base as that of G, a property P such that P(g) for g \in G is either true or false, P(g) is always true for $g \in K$, and the elements of G satisfying P form a subgroup H, and tests \text{TEST}(g, l) used to rule out group elements (i.e., make sure they don’t satisfy P) based on the image of the first l base points of G, the so-called partial base image. It modifies K by adding generators until K = H, and returns a strong generating set for H. It performs a depth-first search over all possible base images (which by the definition of a base determine uniquely every element of G), but uses several conditions to prune the search tree and is said to be fast in practice. This algorithm is the basis for finding normalizers and centralizers and intersections of subgroups, so it’s pretty fundamental. One of its features is the frequent change of base for K: at level l in the search tree we want to make sure that the base for K starts with the current partial base image (i.e., the image of the first l points in the base). In [1] it is said that this requires only one application of BASESWAP (which swaps two neighbouring base points). This was confusing me for a while. However, since we want to only change the l-th base point at any base change, and the base after the l-th point doesn’t matter at level l, it seems that we can do the following. Treat the partial base image, denote it by c_1 c_2 \ldots c_l, as a base, and then run BASESWAP on c_1 c_2 \ldots c_l c, interchanging the last two elements, where c is the new l-th point in the base. Now I’m more confident that I can implement SUBGROUP search (the other parts of the procedure are easily approachable). But there is one other problem with it:
  • We want K, the group we initialize H with, to have the same base as G. The current deterministic implementation of the Schreier-Sims algorithm (using Jerrum’s filther) always produces a BSGS from scratch, and therefore we can’t tell it to make a BSGS for K with respect to some particular base. Hence we need an implementation of the so-called “incremental” Schreier-Sims algorithm, which takes a sequence of points and a generating set and extends them to a BSGS. This is also described in [1], together with some optimizations, and it won’t be very hard to go through the pseudocode and implement it – so that’ going to be the next step. It would also be a useful addition to the entire group-theoretical module since often in algorithms we want a BSGS with respect to some convenient base.

More or less, that’s it for now. In the next few days I’ll try to write some actual code implementing the above two bullets and get some more reviewing for my most recent 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

 

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: