# 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.

Like

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.

Like

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.

Like

mathbabe

Exploring and venting about quantitative issues

Rational Altruist