Group theory is one of the most beguiling topics in mathematics. The core concepts – groups, subgroups, homomorphisms, cosets, etc. – are remarkably easy to define and understand, but this apparently simple set of concepts gives rise to incredible complexity and beauty.

Ever since I was introduced to the topic, I’ve wanted to formalize these elegant concepts in a computational setting where I could explore various examples of groups, peel them apart, construct quotients and morphisms with them, look at their Cayley subgroup diagrams, and generally “play” with groups in order to understand them in a concrete and intuitive way.

In this blog post, I’ll be describing a Haskell library I’m working on to allow me to play with small finite groups and to explore group-theoretic ideas in a practical setting.

Definition of a group

Below is my definition of a group in Haskell:

data Group a = Group { set :: Set a       -- ^ Elements of the group.
                     , mul :: a -> a -> a -- ^ Group multiplication.
                     , inv :: a -> a      -- ^ Inversion.
                     , e   :: a           -- ^ Identity.
                     }

A group is just a Set of elements with multiplication, inversion, and identity, just like in mathematics. Let’s define a simple example group:

>>> z3 = znAdditive 3

The znAdditive function constructs the group of integers mod n for any positive n. We can print z3’s multiplication table:

>>> p = putStrLn . ppMulTable
>>> p z3
 |0|1|2
-+-+-+-
0|0|1|2
-+-+-+-
1|1|2|0
-+-+-+-
2|2|0|1

We can also check that the group axioms hold:

>>> checkAlgebra z3
Nothing

A result of Nothing means all the group axioms hold and this is a valid group. If we create an invalid group, this function will tell us which axiom fails and why:

>>> checkAlgebra z3 { inv = \a -> negate a }
Just (InvClosed,[1])

The result Just (InvClosed, [1]) tells us that the inverse operation is not closed, because negate 1 == -1, which is not an element of [0, 1, 2]. Let’s try another invalid group, this time changing addition slightly:

>>> checkAlgebra z3 { mul = \a b -> if (a, b) == (1,1) then 1 else (a + b) `mod` 3}
Just (MulAssoc,[1,1,2])

This tells us that our group multiplication operation is not associative, and in particular, 1*(1*2) /= (1*1)*2.

More examples

Symmetric groups

Given a set of n elements, we can construct the group of permutations of those elements:

>>> s3 = sn 3
>>> p s3
       |[1,2,3]|[1,3,2]|[2,1,3]|[2,3,1]|[3,1,2]|[3,2,1]
-------+-------+-------+-------+-------+-------+-------
[1,2,3]|[1,2,3]|[1,3,2]|[2,1,3]|[2,3,1]|[3,1,2]|[3,2,1]
-------+-------+-------+-------+-------+-------+-------
[1,3,2]|[1,3,2]|[1,2,3]|[3,1,2]|[3,2,1]|[2,1,3]|[2,3,1]
-------+-------+-------+-------+-------+-------+-------
[2,1,3]|[2,1,3]|[2,3,1]|[1,2,3]|[1,3,2]|[3,2,1]|[3,1,2]
-------+-------+-------+-------+-------+-------+-------
[2,3,1]|[2,3,1]|[2,1,3]|[3,2,1]|[3,1,2]|[1,2,3]|[1,3,2]
-------+-------+-------+-------+-------+-------+-------
[3,1,2]|[3,1,2]|[3,2,1]|[1,3,2]|[1,2,3]|[2,3,1]|[2,1,3]
-------+-------+-------+-------+-------+-------+-------
[3,2,1]|[3,2,1]|[3,1,2]|[2,3,1]|[2,1,3]|[1,3,2]|[1,2,3]

Here, the notation [a,b,c] denotes the permutation mapping 1 to a, 2 to b, and 3 to c. Let’s rename the permutations to integers to get a bit more concise-looking table:

>>> h = integerRenaming s3
>>> s3' = ghCodomain h
>>> p s3'
 |0|1|2|3|4|5
-+-+-+-+-+-+-
0|0|1|2|3|4|5
-+-+-+-+-+-+-
1|1|0|4|5|2|3
-+-+-+-+-+-+-
2|2|3|0|1|5|4
-+-+-+-+-+-+-
3|3|2|5|4|0|1
-+-+-+-+-+-+-
4|4|5|1|0|3|2
-+-+-+-+-+-+-
5|5|4|3|2|1|0

Here, h is the isomorphism that renames all the elements of s3 to integers.

Dihedral groups

The dihedral group on n vertices is the group of all rotations and symmetries of a regular n-gon. Since this is a subset of all possible permutations of the vertices, this is also a subgroup of the symmetric group on n objects. We can make this explicit:

>>> d4 = dn 4
>>> s4 = sn 4
>>> h = integerRenaming s4
>>> s4' = ghCodomain h
>>> d4' = ghCodomain (restrictHomomorphism h d4)
>>> p d4'
  |0 |5 |7 |9 |14|16|18|23
--+--+--+--+--+--+--+--+--
0 |0 |5 |7 |9 |14|16|18|23
--+--+--+--+--+--+--+--+--
5 |5 |0 |18|23|16|14|7 |9 
--+--+--+--+--+--+--+--+--
7 |7 |9 |0 |5 |18|23|14|16
--+--+--+--+--+--+--+--+--
9 |9 |7 |14|16|23|18|0 |5 
--+--+--+--+--+--+--+--+--
14|14|16|9 |7 |0 |5 |23|18
--+--+--+--+--+--+--+--+--
16|16|14|23|18|5 |0 |9 |7 
--+--+--+--+--+--+--+--+--
18|18|23|5 |0 |7 |9 |16|14
--+--+--+--+--+--+--+--+--
23|23|18|16|14|9 |7 |5 |0 

Direct products

Given two groups g and h, we can form the direct product:

>>> z2 = znAdditive 2
>>> z2xz2 = z2 `directProduct` z2
>>> p z2xz2
     |(0,0)|(0,1)|(1,0)|(1,1)
-----+-----+-----+-----+-----
(0,0)|(0,0)|(0,1)|(1,0)|(1,1)
-----+-----+-----+-----+-----
(0,1)|(0,1)|(0,0)|(1,1)|(1,0)
-----+-----+-----+-----+-----
(1,0)|(1,0)|(1,1)|(0,0)|(0,1)
-----+-----+-----+-----+-----
(1,1)|(1,1)|(1,0)|(0,1)|(0,0)

Homomorphisms

The easiest example of a homomorphism is the one that renames the elements of a group to integers:

>>> :t integerRenaming
integerRenaming :: Ord a => Group a -> GroupHomomorphism a Integer
>>> phi = integerRenaming z2xz2
>>> p $ ghCodomain phi
 |0|1|2|3
-+-+-+-+-
0|0|1|2|3
-+-+-+-+-
1|1|0|3|2
-+-+-+-+-
2|2|3|0|1
-+-+-+-+-
3|3|2|1|0
>>> morphismTable phi
[((0,0),0),((0,1),1),((1,0),2),((1,1),3)]

This is, in fact, a group isomorphism. Let’s construct another homomorphism, this time one that is not an isomorphism:

>>> :t GroupHomomorphism
GroupHomomorphism
  :: Group a -> Group b -> (a -> b) -> GroupHomomorphism a b
>>> phi = GroupHomomorphism z2xz2 z2 fst
>>> checkMorphism phi
Nothing

Here, phi is the projection homomorphism that simply forgets about the second element.

>>> morphismTable phi
[((0,0),0),((0,1),0),((1,0),1),((1,1),1)]

We can actually specify a morphism by specifying its behavior on a generative subset of the domain:

>>> z4 = znAdditive 4
>>> phi = generatedHomomorphism z4 z2 [(1, 1)]
>>> morphismTable phi
[(0,0),(1,1),(2,0),(3,1)]

Even though we didn’t specify where anything besides 1 is mapped to, the function computed the values that the other elements must be mapped to based on the homomorphism law because {1} is a generative subset of z4. {2}, however, is not generative, so let’s see what happens if we use that instead:

>>> phi = generatedHomomorphism z4 z2 [(2, 1)]
>>> morphismTable phi
[(0,0),(2,1)]
>>> set $ ghDomain phi
{0,2}

Because the homomorphism was specified for a non-generative subset of z4, we didn’t end up with a full map from z4 to z2; the domain of the resulting homomorphism was the subgroup {0, 2}.

Quotient groups

Given a homomorphism phi, we can compute its kernel:

>>> phi = generatedHomomorphism z4 z2 [(1, 1)]
>>> set $ kernel phi
{0, 2}

We know that the kernel of any homomorphism is a normal subgroup of the domain of the homomorphism:

>>> kernel phi `isNormalSubgroupOf` z4
True

This means we can take the quotient z4 / kernel phi:

>>> g = z4 `quotientGroup` kernel phi
>>> set g
{{0,2},{1,3}}
>>> p g
     |{0,2}|{1,3}
-----+-----+-----
{0,2}|{0,2}|{1,3}
-----+-----+-----
{1,3}|{1,3}|{0,2}
>>> checkAlgebra g
Nothing

Because kernel phi is normal, this is a well-formed construction. If we pick a non-normal subgroup, bad things will happen:

>>> import qualified Algebra.Finite.Set as Set
>>> h = generated s3 (Set.fromList [fromList [2, 1, 3]])
>>> p h
       |[1,2,3]|[2,1,3]
-------+-------+-------
[1,2,3]|[1,2,3]|[2,1,3]
-------+-------+-------
[2,1,3]|[2,1,3]|[1,2,3]

This is the subgroup of s3 generated by the permutation that swaps two elements. This subgroup is isomorphic to z2, but it is not a normal subgroup:

>>> h `checkNormalSubgroupOf` s3
Just [1,3,2]

This means that the permutation [1,3,2] is an example of an element a such that a * h * a^-1 /= h:

>>> conjugateSet s3 (fromList [1,3,2]) (set h)
{[1,2,3],[3,2,1]}

What happens if we still try to take the quotient group anyway?

>>> q = s3 `quotientGroup` h
>>> checkAlgebra q
Just (MulClosed,[{[1,2,3],[2,1,3]},{[1,3,2],[3,1,2]}])

The problem here is that although we can take the cosets of h, multiplication is not closed; in particular, when we multiply the cosets {[1,2,3],[2,1,3]} and {[1,3,2],[3,1,2]} we get something that is not a coset:

>>> mul q (Set.fromList [fromList [1,2,3],fromList [2,1,3]]) (Set.fromList [fromList [1,3,2],fromList [3,1,2]])
{[1,3,2],[2,3,1],[3,1,2],[3,2,1]}

Not only is this not a coset, it doesn’t even have the right number of elements to be one.

What next?

The immediate next goal I have is to produce the Cayley diagram of a group. It’s relatively straightforward to compute every nontrivial subgroup and arrange them in a lattice, so that will be fun to do whenever I get the chance.

In addition, it would be nice to create similar algebraic constructions for rings and fields. The Algebra type class (not described in this post) handles a lot of the machinery for checking that all the group laws hold, and this type class is not biased toward the group axioms or even the group operations.