Notation: We often write 'xy' for 'x · y' when convenient.
H is a subgroup of G, H ≤ G, iff
H ⊆ G as a set, and
H is a group (with the same operator as G).
For g ∈ G, and H a subgroup of G,
gH = {g · h | h ∈ H} is a left-coset of H, and
Hg = {h · g | h ∈ H} is a right-coset of H.
Left-cosets partition G (ditto right-) :
|gH| = |H| :
g h_{1} = g h_{2} ⇔
h_{1} = h_{2}
k ∈ xH ∩ yH ⇒ xH = yH :
must have, k = x h_{1} = y h_{2},
so x = y h_{2} h_{1}^{-1},
so xH = y h_{2} h_{1}^{-1} H = yH.
Either xH = yH, or xH ∩ yH = ∅.
It also follows that |H| divides |G|.
If gH = Hg, ∀g ∈G,
H is said to be a normal subgroup of G.
Permutations
A permutation, p, over {1,...,n},
can be thought of as a mapping (function) on {1,...,n}, e.g.,
p =
(
1
2
3
4
5
6
)
--input
or p = [2 3 1 4 6 5],
2
3
1
4
6
5
--output
p(1)=2, p(2)=3, etc., and
inverse(p) = [3 1 2 4 6 5].
(There is also a cycle notation,
e.g., p = (1 2 3)(4)(5 6) meaning
1→2→3→1,4→4, and
5→6→5.)
The natural group operation is function-composition.
A (permutation) group, G,
can be specified by a set of generators,
{g_{0}, ..., g_{m-1}}.
A permutation, p, is a member of G if and only if
p can be expressed as a product of generators.
S_{n}, the symmetric group_{n},
is the group of all permutations of {1, ..., n}.S_{n} has n! members.
S_{n} is, for example, generated by
the set of n-1 transposition
{[2, 1, 3, 4, ..., n],[1, 3, 2, 4, ..., n],[1, 2, 4, 3, ..., n],
...
[1, 2, ..., n, n-1]},
or by an n-cycle and a transposition,
{[2, ..., n, 1],[2, 1, 3, ..., n]},
say.
A_{n}, the alternating group_{n}, is
the group of all the even permutations of {1, ..., n}.A_{n} has n!/2 members.
Dih_{n}, the dihedral group_{n},
is the group of symmetries of a polygon with n vertices.
Dih_{n} has 2n members.
Dih_{n} is, for example, generated by
a unit rotation, [2, 3, ..., n, 1], plus
a reflection, [n, n-1, ..., 2, 1].
Given a permutation group, G, on {1, ..., n},
there is a natural chain of subgroups,
where G_{i}pointwise stabilises
(fixes) {1, ..., i}(that is, g∈G_{i} & 1≤m≤i ⇒ g(m)=m).
Membership test.
For i = 1, ..., n, choose a representative of each coset of
G_{i} in G_{i-1}
(choose the identity, ι, for G_{i} itself).
g is a member of G iff g can be expressed as a product of
coset representatives, one for each G_{i} in G_{i-1},
i = 1, ..., n:move '1' to g(1), then move '2' to g(2), and so on.
If successful, the expression is unique.
Beware,
there are no data validity checks in the FORM:
Reading
M. Furst, J. Hopcroft & E. Luks,
Polynomial time algorithms for permutation groups,
Proc. 21st Annual Symp. on the Foundations of Comp. Sci.,
pp.36-41, 1980.
Data-structure O(n^{3})-space,
built in O(n^{6})-time (p.38).
M. Jerrum,
A compact representation for permutation groups,
J. of Algorithms, 7, pp.60-78, 1986.
Reduced O(n^{2})-space complexity,
built in O(n^{5})-time.
C. C. Sims.
Computation with permutation groups,
Proc. 2nd Symposium on Symbolic and Algebraic Manipulation,
pp.23-28, 1971.
J. A. Todd & H. S. M. Coxeter,
A practical method for enumerating cosets of a finite abstract group,
Proc. Edinb. Math. Soc., II., Ser. 5, pp.26-34, 1936.