Not really blogging

A. Makelov

Google Summer of Code 2012: Week 3

Hi all,

there wasn’t much coding done on my project this week; I’ve been going over the different versions of the Schreier-Sims algorithm as described in [1]; there is currently an implementation with using Jerrum’s filter as an optimization (see this), and I’ve almost implemented the faster randomized version described in [1]. It remains to see how to integrate both so that the output of the randomized version can be verified, and how to use the deterministic implementation in order to do variations of the Schreier-Sims algorithm, for example when the order of the group is known in advance, or when a base is known. Also, it might be appropriate to switch between storing transversals explicitly (requires a lot of memory, but increases speed) and using schreier vectors insted (much less memory, slower access to transversal elements) depending on the degree of the permutation group.

Apart from that, there’s been work on:

  • Finding the degree of transitivity for a permutation group: using the function orbit as acting on tuples of points, but the algorithm is sort of brute-force and becomes large for groups of large degree or large degree of transitivity.
  • Constructing abelian groups as permutation groups, by their decomposition as a direct sum of cyclic groups of given orders (per the classification of finite abelian groups), i.e. A = \text{AbelianGroup}([3,4,5]) is the group isomorphic to C_3 \oplus C_4 \oplus C_5

My code from the first two weeks is not yet merged, so next week I’ll focus on getting my pull requests reviewed, and will probably do a combined pull request next week including the code from this week. The discussion I started on the mailing list received some attention and it is now a bit clearer what changes to the interface are going to be desirable. Also, it seems that a wider array of available groups to work with will be helpful for testing purposes (i.e., groups of large degree with a small base and other interesting types of groups).

[1] Holt, D., Eick, B., O’Brien, E. “Handbook of computational group theory”


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

  1. mario June 11, 2012 at 12:19 pm

    A change in PermutationGroup should be done for the following case:
    In some cases the strong generating set is known in advance; in that case
    it is not necessary to use Schreier-Sims. It woould be convenient to pass
    this information to PermutationGroup. One application is when
    constructing the stabilizer subgroup on the first element of the strong
    base; another application is in the Butler-Portugal algorithm for tensor
    canonicalization; in that case it is trivial to compute the strong generating
    set of the dummy indices group, while using Schreier-Sims is fairly slow.


  2. mario June 11, 2012 at 1:28 pm

    > or when a base is known.
    I missed this, which I guess is the change I suggested in the previous comment.


  3. amakelov June 17, 2012 at 8:25 am

    I’m not sure if we’re talking about the same thing. What do you mean by “it is not necessary to use Schreier-Sims” – that when the strong generating set is known in advance, we can just deduce the base from it and calculate the basic orbits (i.e., the orbit of \beta_i under the stabilzier of \beta_1,\ldots,\beta_{i-1}, where \beta_1,\beta_2,\ldots is the base) and their transversals (so that we end up with what Schreier-Sims gives us)?
    If that’s the case, I can implement something like a function that calculates a base, basic orbits and transversal elements (or schreier vectors, if we want to spare memory) given a generating set that is known to be strong.


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

Leave a Reply

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

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

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s


Exploring and venting about quantitative issues

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

Most of the blog moved to

%d bloggers like this: