This article covers a broad range of computations you can do with finite groups, using the FiniteGroup<'T> type from the previous article. I hope to show that generic functions in F# are a powerful tool for exploring algebraic structures in all their generality.
For conciseness, I'll use a new version of the FiniteGroup<'T> type with abbreviated property names.
type FiniteGroup<'T> = {
Elts : 'T list // elements of the group
Op : 'T -> 'T -> 'T // group operation, or "product"
Id : 'T // identity element
Inv : 'T -> 'T // invert an element
}The most comprehensive calculation you can do for a finite group is to calculate its Caley table, sometimes called a multiplication table which shows the result of every possible product in the group. Here's the table for $\mathbb{Z}/3\mathbb{Z}$.
$$\begin{array}{c|ccc} + & 0 & 1 & 2 \\ \hline 0 & 0 & 1 & 2 \\ 1 & 1 & 2 & 0 \\ 2 & 2 & 0 & 1 \end{array}$$In our definition of a FiniteGroup we have enough information to compute the whole multiplication table automatically. In the source code forthis article, you can find a function called multTableLaTeX that automatically generates code to display a pretty multiplication table. Its signature is
val multTableLatex : FiniteGroup<'T> -> ('T -> string) -> stringso it can take a finite group as well as a way to convert its elements to LaTeX strings. Internally, it computes all products of pairs of elements of the group and generates LaTeX code to display them in a table. Here's are two examples:
multTableLaTeX (integersModN 7) stringlet permToString : Permutation -> string =
(Array.map string >> String.concat "" >> sprintf "(%s)")
multTableLaTeX (symmetricGroup 3) stringOne game you can play is to start with a few elements of a group $G$ and see how much of the group you can reconstruct by taking their products and inverses. For instance, if you start with the set $\{1\}$ and the operation of addition mod 3, you can get $2$ as $1+1$ and $0$ as $1+1+1$, thereby recovering the whole group $\mathbb{Z}/3\mathbb{Z}$ under addition. On the other hand, if you start with the set $\{2,4\}$ and addition mod 6, you can only get $\{0,2,4\}$. That is, there's no way to get $1$, $3$, or $5$ by repeatedly adding or subtracting $2$ and $4$ in mod 6.
When you can build a whole group out of a few elements like this, those elements are called generators and are said to generate the group. To attempt to generate a group, you can start with a few elements and an operation. After making all possible products of those elements, you may have discovered some new elements. You can then take all possible products of those elements plus the original elements and see if you produce even more new elements. If you have a finite group, you will only have to repeat this process a finite number of times before you stop getting new elements. Here's a recursive function to do this process recursively in F#, where you pass in a list of generators and an operation and it generates all the possible elements from them.
let rec generate<'T when 'T : equality and 'T : comparison>
(operate:'T -> 'T -> 'T) (generators:'T list) =
// get the next set of elements by composing all current elements
let next =
[for x in generators do
for y in generators do
yield operate x y]
|> List.append generators
|> List.distinct
|> List.sort
// if the set of elements hasn'te expanded, you're done
if next = generators then
next
// otherwise, proceed recursively
else
generate operate nextThis function confirms that $\{1\}$ generates all of $\mathbb{Z}/6\mathbb{Z}$ with addition mod 6, while $\{2,4\}$ does not generate the whole group.
> generate (Modular.add 6) [1];;
val it : int list = [0; 1; 2; 3; 4; 5]
> generate (Modular.add 6) [2;4];;
val it : int list = [0; 2; 4]This is actually an important insight: the set $\{0,2,4\}$ equipped with addition (mod 6) is a group. Here's a test:
{
Elts = [0;2;4]
Op = Modular.add 6
Id = 0
Inv = Modular.subtract 6 0
}
|> Test.group // [true; true; true; true]
Such a group, using the same operation as another group but only a subset of the elements, is called a subgroup. If you're sure that you're working with some elements that belong to a finite group, and you know the correct operation for that group, then generate will either produce the whole group or a subgroup. You do need to be careful that the result is finite. If you try generate (+) [1], for instance, F# will try to generate the whole group of the integers. This computation will probably end with you running out of memory.
As a final useful trick, we can generate all the data of a FiniteGroup from a collection of generators and an operation. We use the generate function to find the elements, and then we can search for the identity element and an inverse for every element.
let generateFiniteGroup<'T when 'T : comparison>
(operation:'T->'T->'T) (generators:'T list) : FiniteGroup<'T> =
// get all the elements
let elements = generate operation generators
// find the identity
let (*) = operation
let identity =
elements
|> List.find (fun e ->
elements
|> List.forall (fun x -> e*x = x && x*e = x)
)
// create a Map, element -> inverse
let inverseMap =
[for elt in elements ->
let inverse =
elements
|> Seq.find (fun elt' -> elt * elt' = identity)
elt, inverse]
|> Map.ofList
// create FiniteGroup from all relevant data
{
Elts = elements
Op = operation
Inv = fun elt -> inverseMap.[elt]
Id = identity
}
An interesting fact about permutation groups $S_n$ is that even though their size is very large ($n!$), they can all be generated by just two elements. Namely, you can pick any transposition, which is a permutation that swaps only two elements, as well as an $n$-cycle, which shifts every number by one position, and they generate the whole group. Here's generating the $6! = 720$ elements of $S_6$:
[
[|2;1;3;4;5;6|] // "transposition" of 1 & 2
[|2;3;4;5;6;1|] // 6-cycle
]
|> generateFiniteGroup Permutation.compose
|> fun grp -> grp.Elts.Length // = 720With a group fully constructed, there are a bunch of simple things we can calculate. One obvious one is the number of elements of the group $G$, called the order of the group and written $|G|$.
let order grp = grp.Elts.LengthAny single element $g$ in a finite group $G$ generates a subgroup of $G$, consisting of $g$, $gg$, $ggg$, and so on. Since we're using the multiplicative notation, these are often written as "powers" of $g$, like $g$, $g^2$, $g^3$, etc. It turns out that for any element $g$, there is some smallest power $n$ such that $g^n$ is the identity. The order of an element $g$ is that number $n$, the smallest positive integer such that $g^n = e$, which also happens to be the size of the subgroup generated by $g$. We can compute the order of an element $g$ of a finite group in F# by creating a sequence of powers of $g$ and finding the index of the identity in that sequence.
let eltOrder (grp:FiniteGroup<'T>) (g:'T) =
Seq.unfold (fun x -> Some (grp.Op g x, grp.Op g x)) grp.Id
|> Seq.findIndex ((=) grp.Id)
|> ((+) 1)
This might be a surprising result if you're seeing it for the first time. Because every permutation group $S_n$ is finite, this implies that no matter what permutation you choose, if you apply it over and over to a collection of elements, you'll eventually restore it to its original ordering.
An abelian group is a group $G$ whose operation is commutative, that is $gh = hg$ for every pair of $g$ and $h$ in $G$. For finite groups, we can test commutativity for every pair of elements.
module Test =
let abelian grp =
grp.Elts |> List.forall (fun g ->
grp.Elts |> List.forall (fun h ->
grp.Op g h = grp.Op h g))You can't prove anything with this function, but you can test to see that every group of integers mod $n$ under addition is abelian. You can also see that any symmetric group $S_n$ for $n>2$ is non-abelian.
> Test.abelian (integersModN 15);;
val it : bool = true
> Test.abelian (symmetricGroup 2);;
val it : bool = true
> Test.abelian (symmetricGroup 5);;
val it : bool = falseThe center of a group $G$ is the set of elements that commute with every element in the whole group. In other words, it contains the elements $g$ such that for all $h$ in $G$, $gh = hg$. It's computed like this:
let center<'T when 'T:equality> (grp:FiniteGroup<'T>) =
grp.Elts |> List.filter (fun g ->
grp.Elts |> List.forall (fun h -> grp.Op g h = grp.Op h g))To compute an interesting center, let's look at a kind of group we haven't covered so far: a group of invertible matrices with entries in $\mathbb{F}_p$. These groups will be contained in $M_n(\mathbb{F}_p)$, the set of $n$-by-$n$ matrices with entries in the set $\{0,\ldots,p-1\}$, where operations on entries are done in mod $p$. Living in the set $M_n(\mathbb{F}_p)$ is a subset of the matrices which have inverses under matrix multiplication. The matrices form a group called the general linear group of degree $n$ over $\mathbb{F}_p$, denoted $GL_n(\mathbb{F}_p)$. We can compute such a group as a FiniteGroup object, but it takes a few steps.
// compute all lists of length n with entries in given list
let rec allLists<'T> (n:int) (entries:'T list) =
match n with
| 0 -> [[]]
| _ -> entries
|> List.collect (fun e ->
allLists (n-1) entries
|> List.map (fun lst -> e::lst))
// find lists of length size*size and shape them into matrices
let allSquareMatrices size entries =
allLists (size * size) entries
|> List.map (Array.ofList >> Array.chunkBySize size)
// for a matrix m, return the pair of m and its inverse
// among the matrices, or None otherwise
let withInverse n matrices p m =
let id = Matrix.diag n 1 0
matrices
|> Seq.tryFind (fun m' ->
Matrix.multiply (Modular.add p) (Modular.multiply p) m m' = id)
|> Option.map (fun m' -> m,m')
// build the FiniteGroup by finding invertible matrices
let gl (n:int) (p:int) =
let matrices = allSquareMatrices n [0..p-1]
let pairsOfInverses =
matrices
|> List.choose (withInverse n matrices p)
let inverseLookup = pairsOfInverses |> Map.ofList
{
Elts = pairsOfInverses |> List.map fst
Op = Matrix.multiply (Modular.add p) (Modular.multiply p)
Id = Matrix.diag n 1 0
Inv = fun m -> inverseLookup.Item m
} To see this in action, we can compute a small example: $GL_2(\mathbb{F}_2)$, the $2$-by-$2$ invertible matrices with entries in $\{0,1\}$ and entry arithmetic done in mod 2.
> (gl 2 2).Elts;;
val it : Matrix list =
[[|[|0; 1|]; [|1; 0|]|]; [|[|0; 1|]; [|1; 1|]|]; [|[|1; 0|]; [|0; 1|]|];
[|[|1; 0|]; [|1; 1|]|]; [|[|1; 1|]; [|0; 1|]|]; [|[|1; 1|]; [|1; 0|]|]] There are 6 total matrices. The center of this group is only the identity:
> center (gl 2 2);;
val it : Matrix list = [[|[|1; 0|]; [|0; 1|]|]] The center of $GL_2(\mathbb{F}_7)$ is the set of six "scalar" matrcies, having the same non-zero member of $\mathbb{F}_7$ in both diagonal entries and zeroes on the off-diagonals.
> center (gl 2 7);;
val it : Matrix list =
[[|[|1; 0|]; [|0; 1|]|]; [|[|2; 0|]; [|0; 2|]|]; [|[|3; 0|]; [|0; 3|]|];
[|[|4; 0|]; [|0; 4|]|]; [|[|5; 0|]; [|0; 5|]|]; [|[|6; 0|]; [|0; 6|]|]] This is a general phenomenon -- the center of $GL_n(\mathbb{F}_p)$ consists of non-zero scalar matrices. The sets $GL_n(\mathbb{F}_p)$ grow rapidly, so the inefficient approach above doesn't scale far beyond $GL_2(\mathbb{F}_7)$. In a deeper study of computational group theory, you could learn much more about efficient algorithms for computations in many finite groups.
There are plenty of other things we can compute in a generic manner about FiniteGroup objects, but I can't cover them all here. Hopefully in the future I'll write articles about other computations I've implemented, including an algorithm for detecting whether two finite groups are isomorphic.