## 1. Introduction

### 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:

1. Associativity: $$(a * b) * c = a * (b * c)$$ for all $$a,b,c \in G$$
2. Identity: There exists an $$e \in G$$ such that $$e * a = a * e = a$$ for all $$a \in G$$
3. 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$$.

1. Take an element $$x_1 \in X$$
2. Define the cycle set of $$x_1$$ as $$\{x_1, f(x_1), f(f(x_1)), ..., f^n(x_1)\}$$
3. Take the collection of cycle sets for all elements $$x_i$$. This partitions $$X$$
4. 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)


1. Define the group $$S_3$$
2. 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.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


### 5.6. TODOs

#### 5.6.2.TODO Define a show :: Permutation X -> String that displays Zero as 0, etc.

1. TODO display One as 1 using fromEnum

#### 5.6.3.TODO remove magic number 3 and find way of computing $$|X|$$

Created: 2024-09-09 Mon 09:13

Validate