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 with a BSGS, a subgroup with a BSGS having the same base as that of , a property such that for is either true or false, is always true for $g \in K$, and the elements of satisfying form a subgroup , and tests used to rule out group elements (i.e., make sure they don’t satisfy ) based on the image of the first base points of , the so-called partial base image. It modifies by adding generators until , and returns a strong generating set for . It performs a depth-first search over all possible base images (which by the definition of a base determine uniquely every element of ), 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 : at level in the search tree we want to make sure that the base for starts with the current partial base image (i.e., the image of the first 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 -th base point at any base change, and the base after the -th point doesn’t matter at level , it seems that we can do the following. Treat the partial base image, denote it by , as a base, and then run BASESWAP on , interchanging the last two elements, where is the new -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 , the group we initialize with, to have the same base as . 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 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