# Group Theory in Haskell

## Table of Contents

- 1. Introduction
- 2. Definition of a group
- 3. The Symmetric Group
- 4. Group homomorphims
- 5. Appendix

## 1. Introduction

There are a lot of introductions to group theory, but I wanted to do one in the Haskell programming language. For more about Haskell see the haskellbook, this article will assume some Haskell programming knowledge.

### 1.1. Motivation

There are two major motivations for group theory. The first comes from geometry. The geometer Felix Klein tried to find the essence of Euclidean geometry. His answer was that geometry is essentially about transformations of the plane that preserve distance. Another way to express this:

When a geometer makes a proof that triangle \(ABC\) is congruent to triangle \(DEF\) what they are saying is that there exists some transformation of the plane \({\color{red} f : \mathbb{R}^2 \to \mathbb{R}^2}\), so that \(f(ABC) = DEF\). The distance-preserving property could be expressed precisely as \(d(p,q) = d(f(p),f(q))\).

When you consider the set of all such transformations of the plane, you get a structured object called a group. These objects are worthy of study on their own because they show up in many other seemingly unrelated contexts. Like algebra.

Another major motivation for studying groups came from algebra. A young frenchman named Évariste Galois was studying algebra, particularly the existence of solutions to polynomial equations, like:

\[x^3 + 6x^2 + 11x - 20 = 0\]

He developed a theory of how to transform the "zeros" of the polynomial equations, and these also form a group, like Klein's geometric transformations. Galois worked out a theory for why some equations (like quadratics and cubics) have general solutions, and why others don't. The Galois group is central to that theory.

So the idea of a group arises in both algebra and geometry. It shows up in physics too, it's one of those fundamental ideas whose time came in the 19th century. Groups are essential to understanding symmetry, and symmetry is essential to understanding the physical world. The Standard Model of Particle Physics is a glorified study of one particular group: \(U(1) \times SU(2) \times SU(3)\), and the application of that one group is… *all the particles and forces in the universe except gravity*. What's extraordinary is how we can start studying groups here on paper and in a Haskell REPL.

## 2. Definition of a group

A ** group** is a pair, \((G, * )\) where \(G\) is a non-empty set, and \(*:G\times G \to G\) where the following laws apply:

- Associativity: \((a * b) * c = a * (b * c)\) for all \(a,b,c \in G\)
- Identity: There exists an \(e \in G\) such that \(e * a = a * e = a\) for all \(a \in G\)
- Invertibility: there's a \(b\) for every \(a\) such that \(a * b = b * a = e\)

### 2.1. Haskell definition of a group

In Haskell, a type `g`

is an instance of a `Group`

if it's a `Monoid`

with an `invert`

function:

class Monoid g => Group g where invert :: m -> m

Such that

a <> (invert a) == (invert a) <> a == mempty

`mempty`

is the `Monoid`

unit, it's the \(e\) in the mathmetical definition above.

The notation used for the inverse of a group element is the superscript -1, so \(a * a^{-1} = e\) means that \(a^{-1}\) is the inverse of \(a\).

Another convention used is to drop the infix \(*\) and just use multiplication notation, so \(aa^{-1}=a^{-1}a=e\)

## 3. The Symmetric Group

The first example of a group we should introduce is the Symmetric group \(\text{Sym}(X)\) on a set \(X\). The informal definition is that it's the set of all permutations of a set \(X\). The formal definition of this group is: \[\text{Sym}(X) = \{ f:X \to X | \text{ where \(f^{-1}\) exists} \}\]

Where the group operation is \(\circ\), function composition. Let's check the definition of group above. The identity function exists (it's the trivial permutation that permutes nothing). Inverses are in the set by definition. What about associativity?

#### 3.0.1. Proof that function composition is associative:

Function types have an instance of `Monoid`

typeclass which proves that function composition is associative.

instance Monoid m => Monoid (r -> m) where mempty _ = mempty f `mappend` g = \x -> f x `mappend` g x

Exercise: Check that this Haskell code compiles.

### 3.1. Examples of Symmetric Groups on Finite sets

There are two special notations for permutations. We defined \(\text{Sym}(X)\) using functions with inverses, but since we are thinking about these functions as objects in themselves, let's introduce a special syntax.

#### 3.1.1. pmatrix notation

Let's start with \(X = \{0, 1, 2\}\), the three-element set. To represent an invertible function, we can just make a two-row table like this:

\[\begin{pmatrix} 0 & 1 & 2 \\ 1 & 0 & 2 \\ \end{pmatrix}\]

The permutation notation takes the set \(X\) as the first row, and then the set \(f(X)\) as the second row:

\[\begin{pmatrix} x_0 & ... & x_n \\ f(x_0) & ... & f(x_n) \\ \end{pmatrix}\]

Another name used for the Symmetric group on an n-element set is \(S_n\). The group operation for \(S_3\) is function composition, so as an example,

\[\begin{pmatrix} 0 & 1 & 2 \\ 1 & 0 & 2 \\ \end{pmatrix}\circ\begin{pmatrix} 0 & 1 & 2 \\ 1 & 0 & 2 \\ \end{pmatrix} = \begin{pmatrix} 0 & 1 & 2 \\ 0 & 1 & 2 \\ \end{pmatrix}\]

The \(\begin{pmatrix} 0 & 1 & 2 \\ 0 & 1 & 2 \\ \end{pmatrix}\) element is the identity, since it takes each element of \(X\) to itself.

#### 3.1.2. Cycle notation

Notice in 3.1.1 what the \(\begin{pmatrix} 0 & 1 & 2 \\ 1 & 0 & 2 \\ \end{pmatrix}\) element is doing. It is swapping 0 and 1. This is a transposition, whic means it swaps two elements. In cycle notation it would be \((0 \space 1)\).

If you chain together transpositions \((0\space 1)\) and \((1\space 2)\) you get longer cycles (by convention I am dropping the \(\circ\) and just juxtaposing the elements):

\[(0 \space 1)(1\space 2) = (0\space 1 \space 2)\]

The cycle notation is more compact, but harder to implement in code. We will do both in the next section to demonstrate how to implement different notations on Haskell's algebraic type system.

Now let's implement \(S_3\) in Haskell and make it easy to interactively work with at the REPL.

### 3.2. `Data.Group.Permutation`

in Haskell

Since `Monoid`

is so central to Haskell code, it's easy to work with Groups, since they are just Monoids with an inverse function (see 2.1). In Haskell, the analog of a set is a type. So taking our set \(X = \{0,1,2\}\), the statement \(1 \in X\) is expressed as `1 :: X`

in Haskell. The elements of a set are analogous to the *inhabitants* of a type. In the example below, we define a type `X`

with three inhabitants.

#### 3.2.1. data type definition to build a permutation group upon

data X = Zero | One | Two deriving (Bounded, Enum, Eq, Show)

#### 3.2.2. generating all permutations on the `X`

type

We can enumerate all `X`

values using `[Zero ..]`

Then we need to generate all \(n!\) permutations of that list,
then we can `zip`

them together and generate the `(x, f x)`

pairs in that way.

#### 3.2.3. show function for pmatrix notation

import Data.Group.Permutation import Data.List data X = Zero | One | Two deriving (Bounded, Enum, Eq, Show) -- pmatrix notation pmn :: Permutation X -> String pmn p = "\\begin{pmatrix}" ++ (concat $ intersperse " & " $ map (show . fromEnum) xs) ++ "\\\\" ++ (concat $ intersperse " & " $ map (show . fromEnum . to) xs) ++ "\\end{pmatrix}" where (to, _) = pairwise p xs = [Zero, One, Two] -- show permutations in the notation above instance Show (Permutation X) where show p = pmn p -- Defining the elements of S₃ s0 = permute id id -- identity permutation s1 = permute zo zo where -- transpose Zero/One zo = (\x -> case x of Zero -> One One -> Zero Two -> Two)

The string output of `show s1`

looks like this:
`\begin{pmatrix}0 & 1 & 2\\1 & 0 & 2\end{pmatrix}`

which renders as:

\[\begin{pmatrix}0 & 1 & 2\\1 & 0 & 2\end{pmatrix}\]

#### 3.2.4. show function for cycle notation

This is an alternative `show`

function that uses cycle notation.
The problem in Haskell is collecting all the cycles. Consider our \(S_3\) example so far, notice how
\((0 \space 1)\) is a transposition, which is also a 2-cycle. It *turns out* that we can prove that all
permutations can be decomposed into transpositions. (Proof: 5.3.1)

An example of decomposing a permutation into transpositions is the 3-cycle: \((0 \space 1 \space 2) = (1 \space 2)(0 \space 1)\)

Think about it using function composition, the rightmost function maps \(0\) to \(1\), then the next one sends \(1\)
to \(2\). So we need a generic algorithm for generating the cycle notation for a general `Permutation X`

.

One way to do it is to define a **cycle set**, and observe that the cycle sets will be disjoint, and that they will partition the set \(X\).

- Take an element \(x_1 \in X\)
- Define the
**cycle set**of \(x_1\) as \(\{x_1, f(x_1), f(f(x_1)), ..., f^n(x_1)\}\) - Take the collection of cycle sets for all elements \(x_i\). This partitions \(X\)
- Display the sets as cycles in the output:
`(x1 f(x1) f(f(x1)) ... f(f(...f(x1))))`

import Data.Group.Permutation import Data.List (take) import Data.Set (fromList) data X = Zero | One | Two deriving (Bounded, Enum, Eq, Show) -- cyclesets take a perm to from and an x and then compute [x, to(x), to(to(x),...)..] cycleset p x = fromList $ (take 3 $ iterate f x) where (f, _) = pairwise p -- cycle notation pmc :: Permutation X -> String pmc p = show p -- Defining the elements of S₃ s0 = permute id id -- identity permutation s1 = permute zo zo where -- transpose Zero/One zo = (\x -> case x of Zero -> One One -> Zero Two -> Two)

### 3.3. Exercises (in Haskell)

- Define the group \(S_3\)
- Let \(g_1, ..., g_n \in G\) where \(G\) is a group, prove that \[(g_1g_2...g_n)^{-1} = (g_n^{-1}g_{n-1}^{-1}...g_2^{-1}g_1^{-1})\]

## 4. Group homomorphims

Given two groups \(G\) and \(H\), a function \(f:G \to H\) is a ** homomorphism** if for every \(a,b \in G\):

\[f(a*b) = f(a)*f(b)\]

A linear transformation between vector spaces is an example of a homomorphism. As is the logarithm (remember \(\log(ab)=\log(a) + \log(b)\).

Homomorphisms are like "structure preserving" maps for groups.

If \(|G| = |H|\) and the function \(f\) is invertible, then it's an ** isomorphism**, and this means that the
two groups \(G\) and \(H\) are "the same".

## 5. Appendix

### 5.1. Errors

If spot any errors, you can either submit a Pull Request or you can just email me: mail@tobilehman.com

### 5.2. Haskell

#### 5.2.1. Correspondence between `Hask`

and `Set`

categories

`Hask`

is the Category of all Haskell types. The objects of Hask are Haskell types, and the morphisms
between the types are Haskell functions.
The green \(\color{green}{F}\) is a functor that maps Haskell types to the set of their values.

You can also define \((\mathbb{N}, \leq)\) as a poset category, where the objects are natural numbers,
the morphisms are the less than or equal to relation, and then the cardinality of finite sets can be
represented as a functor from `Set`

to this poset category. Here we define the `Countable`

typeclass
to implement the "cardinality" of a type. The implementation will compute \(|\color{green}{F}(X)|\)

Then finish by introducing `Countable`

typeclass to get the cardinality

### 5.3. proofs

#### 5.3.1. Proof that all permutations are decomposable into transpositions

Bubble sort exists. Think about it. QED.

### 5.4. My literate programming workflow for this document

I wrote this document in org-mode in Emacs. I export the org file to html to generate the website, and then I run `org-babel-tangle`

to produce the Haskell code. To speed up the workflow I made the function below and then bound it to <F5>

(defun org-babel-tangle-and-compile-perms () "Tangle and compile perms.hs" (interactive) (progn (org-babel-tangle) (compile "/opt/homebrew/bin/stack exec -- ghc perms.hs")))

### 5.5. files

#### 5.5.1. The `main`

function

./perms.hs is a literate program that this org-mode document produces. Supporting code to make the file compile and run is defined down here in the appendix.

{-# LANGUAGE FlexibleInstances #-} module Main where import Data.Group.Permutation import Data.List data X = Zero | One | Two deriving (Bounded, Enum, Eq, Show) -- pmatrix notation pmn :: Permutation X -> String pmn p = "\\begin{pmatrix}" ++ (concat $ intersperse " & " $ map (show . fromEnum) xs) ++ "\\\\" ++ (concat $ intersperse " & " $ map (show . fromEnum . to) xs) ++ "\\end{pmatrix}" where (to, _) = pairwise p xs = [Zero, One, Two] -- show permutations in the notation above instance Show (Permutation X) where show p = pmn p -- Defining the elements of S₃ s0 = permute id id -- identity permutation s1 = permute zo zo where -- transpose Zero/One zo = (\x -> case x of Zero -> One One -> Zero Two -> Two) main :: IO () main = do print s1

#### 5.5.2. the `package.yaml`

file, where we add dependencies

name: perms-example version: 0.0.2 executables: perms-example: main: perms.hs source-dirs: . dependencies: - base >= 4.7 && < 5 - group-theory == 0.2.2 - containers == 0.6.5.1

#### 5.5.3. the `stack.yaml`

file, where we define the overall package

resolver: lts-18.17 extra-deps: - group-theory-0.2.2 - containers-0.6.5.1