Permutation Groups
We want to look at permutations of the numbers 1 to n. The simplest way to represent a permutation is as a table showing where each number goes:(1 2 3 4 5 6)
(2 3 1 5 4 6)
However, it's usually more convenient to list the cycles:
(1 2 3)(4 5)
Given a set of permutations, we want to find out about the group that they generate - how big is it, is a given permutation a member of it. For example, we can represent Rubik's cube as a permutation group. How many different positions are possible? Is some given position possible?
The core algorithm which lets us answer these questions is the Schreier-Sims algorithm.
module PermutationGroups
PermutationGroups.hsThis module defines permutations, the group structure on them, and some functions to do with cycle structure.
Exports
newtype Permutation = PL [Int]
(.^) :: Int -> Permutation -> Int - action on a point
(*>) :: Permutation -> Permutation -> Permutation - multiplication (acting on the right)
inverse :: Permutation -> Permutation
fromCycles' :: Int -> [[Int]] -> Permutation - construct a permutation from a list of cycles
cycleType :: Permutation -> [Int] - a list of the number of cycles of each length in the permutation
parity :: Permutation -> Int
orderPerm :: Permutation -> Int - the order of the permutation as a group element
generatorsSn :: Int -> [Permutation] - generators for the symmetric group Sn
generatorsAn :: Int -> [Permutation] - generators for the alternating group An
generatorsCn :: Int -> [Permutation] - generators for the cyclic group Cn of order n
generatorsD2n :: Int -> [Permutation] - generators for the dihedral group D2n of order 2n (the symmetry group of a regular n-gon)
Examples
The permutation from the top of this page is represented internally as PL [2,3,1,5,4,6]. Alternatively, we can construct it from cycles as g = fromCycles' 6 [[1,2,3],[4,5]]. (The "6" says that this is a permutation on 6 points). Then
3 .^ g returns 1, the action of g on the point 3.
inverse g returns [[1,3,2],[4,5]].
orderPerm g returns 6.
orderPerm (f *> r) - using the permutation representation of the Rubik's cube (see examples module below), this asks for the order of the element consisting of a quarter turn of the front face followed by a quarter turn of the right face. This is the number of times you would have to repeat that sequence of moves before the cube got back to its start state. The answer is 105.
module SchreierSims
SchreierSims.hsTwo implementations are provided. The deterministic algorithm is guaranteed to give the right answer. The random algorithm is not, but is much faster. I recommend using the deterministic algorithm for small groups. For large groups, if you know the order of the group, use the random algorithm, and check that the answer has the right order. (If it doesn't try using a different seed - however, in theory the random algorithm is unlikely to be wrong.) If you don't know the order, it might be worth running the deterministic algorithm once to find it, and then using the random algorithm thereafter.
Exports
schreierSimsTransversals
randomSchreierSimsTransversals
isMemberSS - test whether a given permutation is a member of a group, given the Schreier-Sims transversals
orderSS - calculate the order of the group, given the Schreier-Sims transversals
randomEltSS - generate a random element of a group
Examples
(See PermutationGroupExamples below)
module PermutationOrbits
PermutationOrbits.hsThis module is about getting a permutation to act on the vertex set of a graph or set system, and looking at the induced action on the edges of the graph or the blocks of the set system. A permutation of the vertices is an automorphism of the graph or set system if it takes edges to edges or blocks to blocks.
Exports
class Permutable a where
action :: Permutation -> a -> a
newtype Edge = E (Int,Int)
type Graph = [Edge]
newtype Block = B [Int]
type SetSystem = [Block]
orbit :: (Ord a, Permutable a) => [Permutation] -> a -> [a]
Examples
(See below)
module PermutationGroupExamples
PermutationGroupExamples.hsThis module contains several examples.
The Petersen graph is famous.
petersenGraph = toGraph [(1,2),(2,3),(3,4),(4,5),(5,1),(6,8),(7,9),(8,10),(9,6),(10,7),(1,6),(2,7),(3,8),(4,9),(5,10)] - this means the graph on 10 points which has an edge between every pair of numbers in the list.
The automorphism group of the Petersen graph can be generated by two permutations:
alphaPetersen = fromCycles [[1,2,3,4,5],[6,7,8,9,10]]
betaPetersen = fromCycles [[1,2,3,4,9,6],[5,7,8],[10]]
We can now calculate the Schreier-Sims representation of the automorphism group:
petersenSS = schreierSimsTransversals 10 [alphaPetersen, betaPetersen]
orderSS petersenSS returns 120 - in fact, the group is isomorphic to S5.
Similarly, we can define the Fano plane as the Steiner Triple System on 7 points:
sts7 = toSetSystem [[1,2,4],[2,3,5],[3,4,6],[4,5,7],[5,6,1],[6,7,2],[7,1,3]]
We can study its automorphism group in the same way.
f, b, l, r, u, d :: Permutation - the six generators of the Rubik's cube group - clockwise quarter turns of each face.
rubikCube - the Schreier-Sims representation of the Rubik's cube group. From this we can do things like find out the order of the group (hence the number of possible positions of the cube), or find out whether a particular position is a member of the group. Also, we can generate a random element of the group.
Finally, there are permutation representations of some of the Mathieu groups, the "oldest" sporadic finite simple groups. These can be used to construct a Steiner system S(5,8,24) having 759 blocks, and a Steiner system S(5,6,12) having 132 blocks. (See code for details.)