This post provides an introduction to algorithms on permutation groups, building towards Stabilizer Chains, the most important data structure for computing with permutation groups.
In this post, we will assume we are working with finite permutation groups in GAP. Before reading this post, please go and install GAP so you can play along! You can download all the code from this post here:
Let’s begin with a simple permutation group:
There are many obvious questions we might want to answer about
G, some simple examples include:
How does GAP calculate each of these values? If we exhaustively calculated every element of
G then calculating each of these results will be fairly trivial, but for larger groups that rapidly becomes impractical.
We will begin by calculating the orbits. This is the easiest thing to calculate, and a vital building block towards stabilizer chains.
Calculating the orbit of an integer is mathematically simple – keep applying the generators to the point, it’s image, its image’s images… until a fixed point is reached. This is easier to understand in GAP! This function is a little inefficient, but will serve our early purposes.
Let’s write a couple of simple tests, to convince ourselves our function works.
This function has two limitations: Firstly, it is a inefficient because the line
p^g in knownOrbit is slow – it has to search through the whole orbit we have seen so far. Secondly, in practice we often want to know the permutation which will get us to each point in the orbit, but we throw that information away!
So, let’s do an improved version. Here we will start with a
base value, and then track whenever we find a new value in the orbit, which permutation got us there. By following the permutations we will be able to get back to the
Enough chat, I find this data structure is easier to understand once you have it:
Notice that line
img := p/g. You might not have seen
/. This returns the value
p maps to
g. It’s the same as applying
g to the inverse of
p, but is more efficient.
Why do we do this? Well, we want to be able to get back to the base. We could instead store the inverse of
p, but that would require inverting the permutations.
So, what is this vector useful for? It’s main use is to let us find a permutation which maps any integer back to our ``base’’ point. I would play with this function for a while, to be sure you really understand why it works!
Let’s see how this function works in practice. It gives a permutation which maps it’s first argument back to the base point, or returns
fail if no such permutation exists.
Given these two together, we can take a permutation and a group and find another permutation , where is in if and only if is, and fixes the base point of our schreier vector. This function looks like this:
This function takes a permutation and multiplies it by a permutation in our group, to fix the base point (or returns fail if no such permutation exists).
So, we have turned the problem of finding if a permutation is in our group to the problem of finding if a different permutation is in the stabilizer of a single point in that group.
So how do we solve this problem? Well, build
Stabilizer(G,1), build a schreier vector for that, and recurse until no group is left!
Now we have a stabilizer chain, we are (finally) in a position to implement checking if a permutation is in a group. This function is quite long, but follows a basic recursive design:
- Look where the permutation (p) maps the base point. Is that outside the orbit of the base point? Then it is not in our group (G).
- Calculate a permutation (q) in (G) such that (p.q) maps the base point to itself, then search in the stabilizer.
The final terminating case is to detect when we reach the bottom of the stabilizer chain, in which case we must have the identity permutation left.
So, what else can we do with a stabilizer chain? Lots of things, almost anything which explores a group. Here is one easy thing we can do – find the size of the group using the orbit - stabilizer theorem.
We can do much more interesting calculations, like begin to build a group intersection algorithm.