Google Summer of Code 2012: Week 11

Hi all, here’s a brief summary of the 11th week of my GSoC.

• Yay! Subgroup searching now works with the use of .stabilizer(), as I discussed in my previous blog post. Surprisingly, the running time is similar to that of the flawed version using .baseswap() (whenever the one using .baseswap() works), you can play around with the two versions on my week6 (has a bug, using .baseswap()) and week9 (seems to work, using .stabilizer()) branches.
• Consequently, I made a new pull request containing the incremental version of Schreier-Sims, the remove_gens utility for getting rid of redundant generators in a strong generating set, and the new (working) subgroup_search algorithm. You’re most welcome to help with the review!

• I worked on several applications of subgroup_search() and the incremental Schreier-Sims algorithm. Namely, the pointwise stabilizer of a set of points (via the incremental Schreier-Sims algorithm):

In [4]: from sympy.combinatorics.named_groups import *
In [5]: A = AlternatingGroup(9)
In [6]: G = A.pointwise_stabilizer([2, 3, 5])
In [7]: G == A.stabilizer(2).stabilizer(3).stabilizer(5)
Out[7]: True

(this is much faster than the naive implementation using .stabilizer() repeatedly), and the centralizer of a group inside a group :

In [11]: from sympy.combinatorics.named_groups import *
In [12]: S = SymmetricGroup(6)
In [13]: A = AlternatingGroup(6)
In [14]: C = CyclicGroup(6)
In [15]: S_els = list(S.generate())
In [16]: G = S.centralizer(A)
In [17]: G.order()
Out[17]: 1
In [18]: temp = [[el*gen for gen in A.generators] == [gen*el for gen in A.generators] for el in S_els]
In [19]: temp.count(False)
Out[19]: 719
In [20]: temp.count(True)
Out[20]: 1
In [21]: G = S.centralizer(C)
In [22]: G == C
Out[22]: True
In [23]: temp = [[el*gen for gen in C.generators] == [gen*el for gen in C.generators] for el in S_els]
In [24]: temp.count(True)
Out[24]: 6

(it takes some effort to see that these calculations indeed prove that .centralizer() returned the needed centralizer). The centralizer algorithm uses a pruning criterion described in [1], and even though it’s exponential in complexity, it’s fast for practical purposes. Both of the above functions are available (albeit not documented yet) on my week10 branch.

• The next steps are an algorithm for the centre in polynomial time, and an algorithm to find the intersection of two subgroups! And after that, I hope to be able to implement the Todd-Coxeter algorithm…

That’s it for now!

[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