> :load Math.Combinatorics.GraphAuts
> mapM_ print $ graphAuts2 $ q 3
[[0,1],[2,3],[4,5],[6,7]]
[[0,2,3,1],[4,6,7,5]]
[[0,3],[4,7]]
[[0,4,6,7,3,1],[2,5]]
[[0,5,3],[2,4,7]]
[[0,6,5,3],[1,2,4,7]]
[[0,7],[1,3],[2,5],[4,6]]
[[1,2],[5,6]]
[[1,4,2],[3,5,6]]
[[2,4],[3,5]]Now, a few weeks back I set a puzzle: Given just the list returned by graphAuts2, how can I instantly tell how many symmetries there are in total?
Well, think of it like this.
First of all, I'm trying to find all the different places that I can move the 0 vertex to. Hopefully it's obvious that I can move the 0 vertex to any of the eight vertices. The first seven elements returned by graphAuts2 are symmetries which move 0 to 1,2,3,4,5,6,7 respectively - plus of course I can always just leave the cube as it is and leave 0 at 0.
Now, suppose that I have decided to leave 0 where it is. Next, I try to find all the different places that I can move 1 to, but leaving 0 where it is. If you look at the picture, I hope you can see that having fixed 0, our only choices for 1 are 1, 2, and 4. The next two elements returned by graphAuts2 are symmetries which move 1 to 2 and 4 respectively - plus of course, the identity element leaves the cube as it is, so leaves 0 at 0 and 1 at 1.
Now, suppose that I have decided to leave 0 and 1 where they are. Next I try to find all the different places that I can move 2 to. If you look at the picture, you'll see that if we fix 0 and 1, our only choices for 2 are 2 and 4. The identity leaves 2 where it is, and the last element returned by graphAuts2 moves 2 to 4.
Now, suppose that we decide to leave 0, 1 and 2 where they are. Next I try to find all the different places I can move 3 to. graphAuts2 didn't return any more elements. What it is telling us is that once I have decided to fix 0, 1, and 2, I have no choice but to fix 3 and all the other vertices too.
Okay, so how many symmetries are there in total? Well, I had 8 choices for the first vertex, then 3 choices for the second vertex, then 2 choices for the third vertex, then no more choices. So that gives us 8*3*2 = 48. Let's just check:
> length $ elts $ graphAuts2 $ q 3
48
We can write code to do this for us.
orderTGS tgs =
let transversals = map (1:) $ L.groupBy (\g h -> minsupp g == minsupp h) tgs
in product $ map L.genericLength transversals
This code needs a bit of explaining:
- The order of a group means the number of elements. That's what we're trying to calculate.
- TGS stands for transversal generating set. This is my name for a generating set of the type returned by graphAuts2. (I'll explain the name in a little bit.)
- Given a TGS, the first thing we need to do is group the elements into levels based on what I call the minimum support - the least vertex that they move. In the case of the cube, we have three levels - seven elements that move 0, two elements that fix 0 and move 1, and one element that fixes 0 and 1 but moves 2
- Next we add the identity element (called 1) to each level, to show that we can also just leave the vertex where it is
- Finally, to calculate the order, we multiply the number of elements in each level.
> orderTGS $ graphAuts2 $ q 3
48
Let's think a little more about how this works. What are transversals, and what's so special about "transversal generating sets"? Well, consider the following picture:
On the left, the 48 dots represent the 48 symmetries of the cube. The eight columns divide the elements according to whether they send 0 to 0, 1, 2, 3, 4, 5, 6, or 7. The red dot in the top left is the identity, which sends 0 to 0. Then graphAuts2 finds us one dot (the blue one) in each column. So we have a representative from each column. This set of representatives is called a transversal.
Next, on the right, we confine our attention to only the first column, the elements that send 0 to 0. The three blocks divide the elements by whether they send 1 to 1, 2, or 4. The red dot in the top block is again the identity. Then graphAuts2 finds us a blue dot in each of the other two blocks. So we have another transversal.
Finally (not shown), we divide the top left block by whether the elements send 2 to 2 or 4. In this case we have just two divisions, consisting of a single element each - the identity, and the last element found by graphAuts2. Taken together, these two elements constitute our third transversal.
So a transversal generating set - it should really be called a transversal generating sequence, because the order matters - is a sequence of transversals (but omitting the identity), starting at the outermost layer and going successively inwards, that generates the group.
And now it should be totally clear why this method of calculating the order of the group works. The only thing which perhaps isn't clear is, how do we know that there are the same number of elements in each column, and in each block, at each stage? (This is clearly required, if the method is to work.) Well, the answer is simply that multiplication by the blue dot in any column gives a one-to-one correspondence between the elements in the left hand column and the elements in that column, so the number of elements must be the same.
As this last remark perhaps suggests, we can also use these transversals to list the elements of a group:
eltsTGS tgs =
let transversals = map (1:) $ L.groupBy (\g h -> minsupp g == minsupp h) tgs
in map product $ sequence transversals
So once again, we construct some transversals by grouping the TGS into levels, and then adding the identity to each level. Then what the last line is saying is, to get an element of the group, just pick an element from each of the transversals (levels), and multiply them together. To get all the elements of the group, consider all possible such choices.
The reason that transversal generating sets and the orderTGS function are important, is that they are the first step towards being able to work with large or very large groups. Previously, if we wanted to know how many elements there are in a group, we would have had to use the "elts" function to generate them all, and then count them. This is okay for small groups, but for graphs with thousands or millions of symmetries, it is not going to be practical. With the orderTGS function, we will be able to find out how many symmetries a graph has, even if it is in the thousands or millions, so long as we can find a TGS.
Our next stumbling block is that the graphAuts2 function itself is not efficient enough to handle these larger graphs. So next time, we'll look at a more efficient way to find a TGS for a graph. After that, we'll look at something called a strong generating set, and an algorithm called the Schreier-Sims algorithm, that can always find us a strong generating set, given only some generators for the group.
No comments:
Post a Comment