# Not really blogging

A. Makelov

## Google Summer of Code 2012: Week 7

Hi all,

here’s a brief summary of what I’ve been doing during the 7th week of my GSoC, as well as a general overview of what’s going on and where things are going with computational group theory in sympy.

Things I did during the week.

This week I focused on:

• improving the existing code for the functions I recently added – the randomized Schreier-Sims algorithm, the function BASESWAP that changes two points in a base, and the PRINTELEMENTS function (I talk about these here and here). I included some comments in the bodies of the functions since these tend to be quite long. Also, I adopted some new naming conventions for handling all the structures related to a base and a strong generating set. It’d be nice if this naming convention is used throughout the combinatorics module (which for now depends mostly on me, as it seems 🙂 ), and it’d be nice if people provide some feedback on the names I chose. So here we go:
• making possible the interaction with the deterministic Schreier-Sims algorithm. After some insights from Mario on the values returned by his implementation, I extracted from it the data necessary to make the algorihtms described in [1] that use a base and strong generating set possible.
• splitting the code further, with the sympy.combinatorics.util file which now holds the internal functions used to handle permutaion groups (this can be later expanded with other internal functions across the combinatorics module).
• Finally, adding docstrings, tests and making a pull request which is available here . It’s about 1300 lines of code, which is sort of bad, but I can remove some of the stuff and keep it for a future pull request.

So here are the naming conventions for working with a BSGS:

degree – the degree of the permutation group.

base – This is sort of obvious. A base for a permutation group $G$ is an ordered tuple of points $(b_1, b_2,\ldots, b_k)$ such that no group element $g \in G$ fixes all the points $b_1, b_2, \ldots, b_k$ (the significance of the ordering will become apparent later). This is implemented as a list.

base_len – the number of elements in a base.

strong_gens – the strong generating set (relative to some base). This is implemented as a list of Perm objects.

basic_stabilizers – For a base $(b_1, b_2,\ldots, b_k)$, the basic stabilizers are defined as $G^{(i)} = G_{b_1, \ldots, b_{i-1}} := \{ g \in G | g(b_1) = b_1, \ldots, g(b_{i-1}) = b_{i-1}\}$ for $i \in \{1, 2, \ldots, k\}$ so that we have $G^{(1)} = G$. This is implemented as a list of permutation groups.

distr_gens – the strong generators distributed according to the basic stabilizers. This means: for a base $(b_1, b_2,\ldots, b_k)$ and a strong generating set $S= \{ g_1, g_2, \ldots, g_t\}$, distribute the $g_i$ in sets $S^{(i)} = G^{(i)} \cap S$ for $i \in \{1, 2,\ldots, k\}$ where the $G^{(i)}$ are defined as above. This is implemented as a list of lists holding the elements of the $S^{(i)}$

basic_orbits – these are the orbits of $b_i$ under $G^{(i)}$. These are implemented as a list of lists, being the list of lists of keys for the basic transversals, see below.

basic_transversals – these are transversals for the basic orbits. Notice that the choice for these may not (and in most cases won’t be) unique. For one thing, it depends on the set of strong generators present (which is also not uniquely determined for a given base). They are implemented as a list of dictionaries indexed according to the base $(b_1, b_2,\ldots, b_k)$, with keys – the elements of the basic orbits, and values – transversal elements sending the current $b_i$ to the key.

I wrote functions extracting basic_orbits, basic_transversals, basic_stabilizers, distr_gens from only a base and strong generating set, as well as functions for extracting all of them from a base, strong generating set, and a part of them, so that if any of them is available, it can be supplied in order to avoid recalculations.

Also, there is a straightforward test _verify_bsgs in sympy.combinatorics.util that tests a sequence of points and group elements for being a base and strong generating set. It simply verifies the definition of a base and strong generating set relative to it. There will likely be other ways to do that in the future – more effective, but surely more complicated and thus error-prone. This will serve as a robust testing tool

Where we are.

So, here’s a checklist of what I’ve promised in my proposal on the melange website, and which parts of it have already been implemented. This is reading the optimistic timeline. This all pertains to permutation groups, unless specified:

• handling different representations – NO
• excluding singleton cycles from the cycle decomposition – NO
• powers and orders of elements – YES. This was actually already there for permutations.
• orbits – YES.
• stabilizers – YES.
• schreier vectors – YES.
• randomized Schreier-Sims algorithm – YES
• handling bases and strong generating sets – YES
• membership testing – YES (the function _strip in sympy.combinatorics.util)
• rewriting algorithm – NO.
• actions on cosets – NO.
• quotient groups – NO.
• order of a group – YES. This was already there.
• subgroup testing – NO.
• coset enumeration by the Todd-Coxeter algorithm & consequences – NO.
• primitivity testing – YES.
• finding (minimal) block systems – YES.
• general backtrack search for a certain property – No, however easy to do by modifying PRINTELEMENTS.
• outputting all group elements – YES. This was already there, however PRINTELEMENTS does it in lexicographical order according to a base.
• Sylow subgroups – NO.
• calculating the center – NO.
• pointwise stabilizers (of more than one point, see above) – NO.
• change of base – YES.
• product groups – YES.
• more on finitely presented groups (…) – NO.
• the p-core – NO.
• the solvable radical – NO.
• database of known groups – NO.

Things yet to be done.

Apart from the things that got a “NO” on the list above, the following currently come to mind (I’ll update this list periodically):

• Work on removing redundant generators from a strong/any generating set, as described in [1].
• Precompute more properties for the groups in the named groups module (transitivity degrees, bases and strong generating sets, etc.)
• Add more groups to the named groups module.
• Fix the issues pointed out in the review of my second pull request.
• Finally do something for handling representations of finite groups over vector spaces, like working with character tables. It’d be cool to have a function that computes the conjugacy classes for a given group, but I don’t know right now how possible that is.
• Finally implement the group intersection algorithm… I’m currently starting to work my way through the SUBGROUPSEARCH function which is fundamental for implementing backtracking algorithms for group intersection, centralizers, etc.
• Upgrade the randomized version of Schreier-Sims to Las Vegas type in the case when the order of the group is known.
• Currently, transversal elements for the basic orbits for a stabilizer chain are stored explicitly. This requires too much memory for large groups. An alternative solution (which slows down execution) is to use Schreier vectors to describe the orbits. This means supplying some more arguments and adding code to many of the functions already present, and is a significant challenge by itself. The good news is that it can be carried out without modifying what is already there.
• Come up with a more concise functionality to relate the different structures used to describe a base and strong generating set: the generators for basic stabilizers, the basic orbits, the basic transversals… There are many situations in which some of these are given and we need some of the other ones; sometimes it’s more convenient to get the orbits as sets, and sometimes as lists, and so on… the current approach is to write a new utility function whenever the present ones don’t suffice.
• Handle the case when the identity element is provided as a generator for a permutation group – this can make some algorithms less efficient.
• Optimize the behavior of BASESWAP so that only the $i$-th and $i+1$-th transversals are calculated.
• Reduce side effects as much as possible (let’s be pythonic!)
• Improve the docstring quality: it might be reasonable to lay out the theory/notation/definitions behind the Schreier-Sims algorithm in one place in some of the files and then simply refer to it as necessary. Otherwise the descriptions get unnecessarily long.
.

Well, that’s it for now it seems. If anything else pops up soon, I’ll add it here!

### 4 responses to “Google Summer of Code 2012: Week 7”

1. wdjoyner July 8, 2012 at 11:27 pm

Since you asked, my first thought is that distr_gens is more confusing than strong_gens_distr or strong_gens_stab (helps finding it with tab completion too). Not a big deal though.

I don’t understand “It’d be cool to have a function that computes the conjugacy classes for a given group, but I don’t know right now how possible that is.” What does that mean? Input a perm group and output a list a complete set of representatives for the set of conjugacy classes? If so, one way to do this is to use GAP to build a database for groups up to a certain size, and include that in sympy/combinatorics somewhere. An obvious algorithm is to construct such a list by using a “greedy” algorithm: randomly grab one that is not in the union of the classes already selected. There are probably better ones known. In any case, it is possible (and a necessity) if you are going to deal with character tables.

Like

• amakelov July 9, 2012 at 9:30 am

Yes, my first idea was strong_gens_distributed, but thought that it’s way too long. strong_gens_distr seems more informative than distr_gens, so I can change it to that.
And about the conjugacy classes, yes, something like a list of representatives will work (we can’t list all the group elements in most cases, after all). I should look into the GAP database at some point in the future (and not only because of character tables… but that’s another compelling reason).
By the way, Professor Holt replied to me that what I spotted in the BASESWAP procedure is indeed a typo. Yay! : )

Like

2. mario July 9, 2012 at 6:40 am

Here are some comments on this list.
handling different representations:
you mean that a group can be represented by permutation groups
with different degrees, right? So this is related to group isomorphism
testing

subgroup testing:
for permutation groups with the same degree this is already implemented
with is_subgroup; in the case of different degrees it is related to group isomorphism testing

calculating the center:
I read that it can be done in polynomial time, but do not know how.
In general, could you add in this list of things (to be) implemented
if they are implemented in polynomial time?

Like

• amakelov July 9, 2012 at 9:43 am

About different representations: I was talking about representing groups as permutation groups and by a finite presentation, i.e. a list of generators and relations: http://en.wikipedia.org/wiki/Presentation_of_a_group
About subgroup testing: yes, I’ll look into that algorithm, sorry for missing it.
About the center: A polynomial-time algorithm is described in the “Handbook…”, in the chapter dealing with normalizers and centralizers.
I’ll try to amend the list with polynomial/non-polynomial time information in the next couple of days 🙂

Like

mathbabe

Exploring and venting about quantitative issues

Rational Altruist