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 h1 = g h2 ⇔
h1 = h2
k ∈ xH ∩ yH ⇒ xH = yH :
must have, k = x h1 = y h2,
so x = y h2 h1-1,
so xH = y h2 h1-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,
{g0, ..., gm-1}.
A permutation, p, is a member of G if and only if
p can be expressed as a product of generators.
Sn, the symmetric groupn,
is the group of all permutations of {1, ..., n}.Sn has n! members.
Sn 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.
An, the alternating groupn, is
the group of all the even permutations of {1, ..., n}.An has n!/2 members.
Dihn, the dihedral groupn,
is the group of symmetries of a polygon with n vertices.
Dihn has 2n members.
Dihn 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,
G = G0 ≥ G1 ≥ G2 ≥
... ≥ Gn-1 = Gn = {ι},
where Gipointwise stabilises
(fixes) {1, ..., i}(that is, g∈Gi & 1≤m≤i ⇒ g(m)=m).
Membership test.
For i = 1, ..., n, choose a representative of each coset of
Gi in Gi-1
(choose the identity, ι, for Gi itself).
g is a member of G iff g can be expressed as a product of
coset representatives, one for each Gi in Gi-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(n3)-space,
built in O(n6)-time (p.38).
M. Jerrum,
A compact representation for permutation groups,
J. of Algorithms, 7, pp.60-78, 1986.
Reduced O(n2)-space complexity,
built in O(n5)-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.