# Data.SymmetricGroup

- Package
- purescript-symmetric-groups
- Repository
- hdgarrood/purescript-symmetric-groups

One important example of a group which arises very often in group theory
and its applications is the *symmetric group* on some set X, which is
the group of bijective functions from X to itself. The group operation
here is function composition and the identity element is the identity
function. (If I've lost you by this point, the first few of chapters of
the PureScript numeric hierarchy
guide
should help.)

We often restrict our attention to just the symmetric groups on finite sets, since they are a little easier to deal with. Since we are dealing with a finite set, we might as well label the elements of the set from 1 up to n (where n is the size of the set); the group structure will be the same no matter how we have labelled the elements of the underlying set. The symmetric group on a set X can be written S(X); if X is the set {1,2,...,n} we often abuse notation and write the group S(X) as just S(n).

Some vocabulary first: if f is a function from the set X to itself, we
say that x is a *fixed point* of f if and only if f(x) = x. We sometimes
say that "f *fixes* x" instead, since this is less of a mouthful than "x
is a fixed point of f".

When attempting to represent the group S(n) in PureScript, one approach
might be to define a type constructor of kind `Type -> Type`

, where the
argument is a type-level natural number representing n. This approach
quickly runs into a problem, though, which is that there is no
(ergonomic) type for natural numbers less than or equal to a certain
number. For example, Idris has `Fin n`

, which is the type of integers
between 0 and n-1. Of course, it is possible to define a similar type in
PureScript, but without dependent types it will not be nearly as
comfortable to use as Idris' `Fin`

. However, we want to have some way of
converting elements of this set to standard PureScript functions*, but
without an ergonomic type `Fin`

we will need to use `Partial`

constraints (yuck).

We also would like to be able to do things like embed S(n) into S(n+1) without too much effort (that is, without having to convert between two different types): note that every permutation f on a set of n elements can be extended to a permutation f' on a set of n+1 elements just by saying that f' fixes n+1 and does the same as f for everything else, i.e. f'(k) = f(k) for all k ≤ n.

There is a simple trick we can use to address this. We say that a
permutation is *finitary* if and only if it fixes all but finitely many
points. For example, the permutation on the set of natural numbers which
swaps 1 and 2 and fixes everything else is finitary; the permutation
which swaps every even number with the odd number preceding it is not.
It turns out that the product of two finitary permutations is itself
finitary, and also that the inverse of a finitary permutation is
finitary (exercise!). Therefore the set of finitary permutations on a
set X is a group (in fact a subgroup of S(X)), which we will refer to as
FS(X).

The design adopted by this library is to define a type representing the group FS(ℕ) of finitary permutations on the natural numbers. Then, for any natural number n, there is a natural embedding of S(n) into FS(ℕ) by just fixing everything greater than or equal to n; in the same way there is a natural embedding of S(k) into S(n) (within FS(ℕ)) whenever k < n.

Perhaps surprisingly, Cayley's Theorem tells us that any finite group is isomorphic to a subgroup of S(n), so we can in fact represent any finite group at all using this library (although this fact might mostly just be a curiosity).

*note: we don't use standard PureScript functions directly, as it is not an efficient representation for many of the operations we would like to be able to do, and also it is harder to guarantee that the function in question is bijective.

### #Sym Source

`newtype Sym`

The type `Sym`

represents the group FS(ℕ) of finitary permutations of the
set of natural numbers. Values of this type cannot be constructed from
functions of type `Int -> Int`

, because we cannot easily verify that these
are bijective. Instead, use `fromCycle`

or `fromCycles`

.

The runtime representation of a value of this type is an array with k elements, where k is the largest number which is not a fixed point of f; if k is very large this may be a problem.

#### Instances

### #fromCycles Source

`fromCycles :: List (List Int) -> Sym`

Construct a permutation from a list of cycles.

```
f = asFunction (fromCycles ((1 : 3 : Nil) : (2 : 4 : Nil) : Nil))
f 1 == 3
f 2 == 4
f 3 == 1
f 4 == 2
```

### #asCycles Source

`asCycles :: Sym -> List (List Int)`

Represent a permutation as a list of cycles. Note that
`asCycles <<< fromCycles`

is not equal to `id`

, because in general there
are lots of different ways to write any given permutation as a product of
cycles. However, `fromCycles <<< asCycles`

is equal to `id`

.

```
asCycles (fromCycles ((1 : 2 : 3 : Nil) : Nil))
== (1 : 2 : 3 : Nil) : Nil
```

### #asFunction Source

`asFunction :: Sym -> Int -> Int`

Convert a finitary permutation into a regular function. The resulting function fixes all negative numbers.

```
f = asFunction (fromCycle (1 : 2 : 3 : Nil))
f 1 == 2
f 2 == 3
f 3 == 1
f 4 == 4
f (-1) == (-1)
```

### #parity Source

`parity :: Sym -> Parity`

The parity of a permutation. All permutations can be expressed as products of 2-cycles: for example (1 2 3) can be written as (2 3)(1 3). The parity of a permutation is defined as the parity of the number of 2-cycles when it is written as a product of 2-cycles, so e.g. (1 2 3) is even.

This function is a group homomorphism from the group Sym to the additive
group of the field of two elements (here represented by the `Parity`

type); that is,

```
parity f + parity g = parity (f <> g)
```

holds for all permutations `f`

, `g`

.

The parity of a permutation is sometimes also called the "sign" or "signature".

### #permutations Source

`permutations :: Int -> Array (Array Int)`

Returns all permutations of the array with elements from 1 up to n.

### #alternating Source

`alternating :: Int -> Array Sym`

`alternating n`

gives you every element of the group A(n) -- that is, the
subgroup of S(n) given by the even permutations -- in an array.

### #trivialSubgroup Source

`trivialSubgroup :: forall a. Ord a => Group a => Set a`

The set containing just the identity element of a group (i.e. `mempty`

).

## Re-exports from **Data.**Int

### #Parity Source

`data Parity`

A type for describing whether an integer is even or odd.

The `Ord`

instance considers `Even`

to be less than `Odd`

.

The `Semiring`

instance allows you to ask about the parity of the results
of arithmetical operations, given only the parities of the inputs. For
example, the sum of an odd number and an even number is odd, so
`Odd + Even == Odd`

. This also works for multiplication, eg. the product
of two odd numbers is odd, and therefore `Odd * Odd == Odd`

.

More generally, we have that

```
parity x + parity y == parity (x + y)
parity x * parity y == parity (x * y)
```

for any integers `x`

, `y`

. (A mathematician would say that `parity`

is a
*ring homomorphism*.)

After defining addition and multiplication on `Parity`

in this way, the
`Semiring`

laws now force us to choose `zero = Even`

and `one = Odd`

.
This `Semiring`

instance actually turns out to be a `Field`

.

#### Constructors

#### Instances

- Modules
- Data.
SymmetricGroup