Module

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 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.

If f is a permutation, and k is the largest number which is not a fixed point of f, then the amount of memory required to represent f at runtime is O(k). If k is very large, this may be a problem.

There does not appear to be consistent standard for which way composition goes; some authors write f <> g to indicate the permutation given by first applying g and then f, and others use the same notation to indicate the permutation given by first applying f and then applying g. This is very unfortunate! The decision taken by this library is that the group operation of Sym corresponds to normal function composition, <<< (see also: the docs for asFunction).

The time complexity of the group operation f <> g is O(max(n,m)), where n is the largest non-fixed point of f, and m is the largest non-fixed point of g. The time complexity of ginverse f is O(n).

Instances

#fromCycle Source

fromCycle :: List Int -> Sym

Generate a permutation from a single cycle. If the given cycle includes nonpositive or duplicate elements, they will be ignored.

fromCycle (1:2:Nil) == fromCycle (1:2:1:Nil)
fromCycle (1:2:Nil) == fromCycle (1:2:0:Nil)
fromCycle (1:2:Nil) == fromCycle (1:2:(-1):Nil)

Time complexity: O(n), where n is the length of the input list/cycle.

#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

Time complexity: O(nm), where n is the length of the longest cycle in the provided list, and m is the length of the list.

#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

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

Time complexity: Ω((n log n)(m log m)), where n is the length of the longest cycle in the result and m is the number of cycles in the result (note that Ω denotes a lower bound whereas O denotes an upper bound). The actual time complexity is probably worse than this but I gave up trying to calculate it.

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

This function agrees with the group operation of Sym in the following sense: for all f, g :: Sym, we have that:

asFunction f <<< asFunction g == asFunction (f <> g)

Time complexity: O(1).

#cycleOf Source

cycleOf :: Sym -> Int -> List Int

Compute the cycle containing a given point.

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

cycleOf f 1 == 1 : 3 : Nil
cycleOf f 2 == 2 : 4 : Nil
cycleOf f 5 == Nil

Time complexity: O(n), where n is the length of the resulting cycle.

#minN Source

minN :: Sym -> Int

The smallest natural number N for which the given permutation fixes all numbers greater than or equal to N.

minN (fromCycle (1:2:Nil)) == 3

Time complexity: O(1).

#inversions Source

inversions :: Sym -> Array (Tuple Int Int)

The inversions of a permutation, i.e. for a permutation f, this function returns all pairs x, y such that x < y and f x > f y.

The parity of the number of inversions of a permutation is equal to the parity of the permutation itself.

Time complexity: O(n^2), where n = minN f.

#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".

Time complexity: O(nm), where, if the permutation is expressed as a product of disjoint cycles, n is the length of the longest cycle, and m is the number of cycles.

#order Source

order :: Sym -> Int

The order of a permutation; the smallest positive integer n such that s^n is the identity. Restricting Sym to finitary permutations ensures that this is always finite.

order mempty == 1
order (fromCycle (1:2:Nil)) == 2
order (fromCycle (1:2:3:Nil)) == 3

Time complexity: O(nm), where, if the permutation is expressed as a product of disjoint cycles, n is the length of the longest cycle, and m is the number of cycles.

#permutations Source

permutations :: Int -> Array (Array Int)

permutations n gives you all permutations of the array with elements from 1 up to n. If n is not positive, the resulting array is empty.

permutations 0 == []
permutations 1 == [[1]]
permutations 2 == [[2,1], [1,2]]

Time complexity: O(n!).

#symmetric Source

symmetric :: Int -> Array Sym

symmetric n gives you every element of the group S(n) in an array.

Time complexity: O(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.

Time complexity: O(n!).

#trivialSubgroup Source

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

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

Time complexity: O(1).

#subgroup Source

subgroup :: Set Sym -> Set Sym

Given a set of permutations, form the subgroup generated by that set. This function is idempotent, that is, subgroup (subgroup a) = subgroup a.

#actLeft Source

actLeft :: forall a. Ord a => Group a => a -> Set a -> Set a

If h is a subgroup, then actLeft s h gives the coset formed by applying s to each element of h on the left.

#cosets Source

cosets :: forall a. Ord a => Group a => Set a -> Set a -> Set (Set a)

If h is a subgroup of g, then cosets h g gives the set of cosets of h in g. Otherwise, the behaviour of this function is undefined.

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