This chapter provides an introductio to working with permutation groups. This will building towards Stabilizer Chains, the most important data structure when computing with permutation groups.
Throughout this book, 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:
G := Group((1,3,2)(5,11,6,9,7,10)(8,12)(13,15,14), (1,9,5)(2,11,6,3,10,7)(4,12,8)(14,15));
There are many obvious questions we might want to answer about
G, some simple examples include:
# What is the orbit of 1 in G? Orbit(G, 1); # [ 1, 2, 5, 6, 3, 7, 9, 10, 11 ] # What is the orbit of 4 in G? Orbit(G, 4); # [ 4, 8, 12 ] # Does G contain a given permutation? (5,9)(6,10)(7,11)(8,12) in G; # true # What is the size of G? Size(G); # 36 # Which subgroup of G fixes 4? Stabilizer(G, 4); # Group((2,3)(6,7)(10,11)(14,15), # (1,3,2)(5,11,6,9,7,10)(8,12)(13,15,14))
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.
CalculateOrbitSlow := function(G, point) local knownOrbit, p, g, gens; gens := GeneratorsOfGroup(G); knownOrbit := [point]; for p in knownOrbit do for g in gens do if not(p^g in knownOrbit) then Add(knownOrbit, p^g); fi; od; od; return knownOrbit; end;
Let's write a couple of simple tests, to convince ourselves our function works.
CalculateOrbitSlow(G, 1); # [ 1, 3, 9, 2, 10, 7, 5, 11, 6 ] CalculateOrbitSlow(G, 4); # [ 4, 12, 8 ]
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:
CalculateSchreier := function(G, point) local knownOrbit, vec, img, p, g, gens; gens := GeneratorsOfGroup(G); vec := ; knownOrbit := [point]; vec[point] := (); for p in knownOrbit do for g in gens do img := p/g; # Note this line! if not(IsBound(vec[img])) then vec[img] := g; Add(knownOrbit, img); fi; od; od; # Return everything we found return rec(generators := gens, orbit := knownOrbit, transveral := vec); end;
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!
RepresentativePerm := function(schvec, val) local ret, gen; if not(IsBound(schvec.transveral[val])) then return fail; fi; ret := (); while val <> schvec.orbit do gen := schvec.transveral[val]; val := val^gen; ret := ret*gen; od; return ret; end;
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.
sch := CalculateSchreier(G, 1);; RepresentativePerm(sch, 2); # (1,3,2)(5,11,6,9,7,10)(8,12)(13,15,14) RepresentativePerm(sch, 6); # (1,10,5,2,9,6)(3,11,7)(4,12,8)(13,14) RepresentativePerm(sch, 4); # fail
Given these two together, we can take a permutation $p$ and a group $G$ and find another permutation $q$, where $q$ is in $G$ if and only if $p$ is, and $q$ fixes the base point of our schreier vector. This function looks like this:
MapToBase := function(schvec, perm) local map; map := RepresentativePerm(schvec, schvec.orbit^perm); if map = fail then return fail; fi; return perm * map; end;
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).
sch := CalculateSchreier(G, 1);; MapToBase(sch, (1,2,3,4)); # (3,4)(5,11,6,9,7,10)(8,12)(13,15,14) MapToBase(sch, (1,4)); # fail
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!
StabilizerChain := function(G) local root, pnt, Gstab; pnt := SmallestMovedPoint(G); root := CalculateSchreier(G, pnt); Gstab := Stabilizer(G, pnt); if not IsTrivial(Gstab) then root.stabilizer := StabilizerChain(Gstab); fi; return root; end;
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:
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.
PermInGroup := function(chain, perm) local basemap; basemap := MapToBase(chain, perm); if basemap = fail then return false; fi; if not IsBound(chain.stabilizer) then return basemap = (); fi; return PermInGroup(chain.stabilizer, basemap); end;
Let's test this new function:
chain := StabilizerChain(G);; PermInGroup(chain, (1,5)(2,6)(3,7)(4,8)); # true PermInGroup(chain, (1,5)(2,6)(3,7)(4,9)); # false
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.
GroupSize := function(stabchain) if not IsBound(stabchain.stabilizer) then return Length(stabchain.orbit); fi; return Length(stabchain.orbit) * GroupSize(stabchain.stabilizer); end; GroupSize(chain); # 36
We can do much more interesting calculations, like begin to build a group intersection algorithm.