Q: "What's commutative and purple?"
A: "An abelian grape".
 Ancient Math Joke
"In 1910 the mathematician Oswald Veblen and the physicist James
Jeans were discussing the reform of the mathematical curriculum
at Princeton University. `We may as well cut out group theory,` said
Jeans. `That is a subject which will never be of any use to physics.`
It is not recorded whether Veblen disputed Jeans' point, or whether
he argued for the retention of group theory on purely mathematical
grounds. All we know is that group theory continued to be taught.
And Veblen's disregard for Jeans' advice continued to be of some
importance to the history of science at Princeton. By the irony of
fate group theory later grew into one of the central themes of
physics, and it still dominates the thinking of all of us who are
struggling to understand the fundamental particles of nature."
Freeman J. Dyson
SCIENTIFIC AMERICAN, Sep, 1964
GROUPS, I
Let X be any finite set and let S_X denote the set of all
permutations of X onto itself:
S_X = { f : X > X  f is a bijection }.
This set has the following properties:
(1) if f, g belong to S_X then fg (the composition of these
permutations) also belongs to S_X,
(2) if f, g, h all belong to S_X then (fg)h = f(gh),
("associativity"),
(3) the identity permutation I : X > X, I(x) = x for all
x in X, belongs to S_X ("existence of the identity"),
(4) if f belongs to S_X then the inverse permutation f^(1)
of X also belongs to S_X ("existence of the inverse").
The set S_X is called the "symmetric group of X". We shall
usually take for the set X a set of the form {1, 2, ..., n},
in which case we shall denote the symmetric group by Sn.
This group is also called the "symmetric group on n letters.
Example: Suppose X = {1,2,3}. We can describe S_X as
S_X = { I, s1=(1 2), s2=(2 3), s3=(1 3 2),
s4=(1 2 3), s5=(1 3)}.
The multiplication table is
 I s1 s2 s3 s4 s5

I  I s1 s2 s3 s4 s5

s1  s1 I s3 s2 s5 s4

s2  s2 s4 I s5 s1 s3

s3  s3 s5 s1 s4 I s2

s4  s4 s2 s5 I s3 s1

s5  s5 s3 s4 s1 s2 I
Exercise: Verify the four properties of S_X mentioned above in
the case of the above example. Note that associativity follows from the
associative property of the composition of functions (see the
exercise at the end of chapter 2).
We take these four properties as the four defining
properties of a group:
Definition: Let G be a set and suppose that there is a function
* : GxG > G
(g1,g2) > g1*g2
(called the group's "operation") satisfying
(G1) if g1, g2 belong to G thn g1*g2 belongs to G ("G is
closed under *"),
(G2) if g1, g2, g3 belong to G then (g1*g2)*g3 = g1*(g2*g3)
("associativity"),
(G3) there is an element 1 in G such that 1*g = g*1 = g for
all g in G ("existence of an identity"),
(G4) if g belongs to G then there is an element g^(1) in G
such that g*g^(1) = g^(1)*g = 1.
Then G (along with the operation *) is a "group".
Definition: Let g and h be two elements of a group G. We say
that g "commutes" with h (or that "g, h commute") if
g*h = h*g. We call a group "abelian" (or "commutative") if every
pair of elements g, h belonging to G commute. If G is a group
for which there exists some pair g,h in G which do not
commute then we call G "nonabelian" or "noncommutative".
Example: The integers, with ordinary addition as the group
operation, is an abelian group.
Exercise: Show that any group having exactly 2 elements is
abelian.
Now the reader should understand the punchline to the
joke quoted at the beginning!
Convention: When dealing with groups in general we often drop
the * and denote multiplication simply by juxtaposition (that
is, sometimes we write gh in place of g*h), with one exception.
If the group G is abelian then one often replaces * by + and
then + is NOT dropped.
Now that we know the definition of a group, the question
arises: how might they be described? The simplest answer is
that we describe a group much as we might describe a set: we
could list all its elements and give the multiplication table
or we could describe all its elements and their multiplication
in terms of some property from which we can verify the four
properties of group. Though the first way has the distinct
advantage of being explicit, it is this second alternative
which is the most common since it is usually more concise.
Our objective is to introduce terminology and techniques
which enable us to analyse mathematically permutation puzzles.
The type of groups which arise in this context are defined next.
Definition: Let X be a finite set. Let g1, g2, ..., gn be a
finite set of elements of permutations of X. Let G be the set
of all possible products of the form
g = x1*x2...*xm, m>0,
where each of the x1, ..., xm is taken from the set
{g1, g1^(1), ..., gn, gn^(1)}. The set G, together with
the group operation given by composition of permutations,
is called a "permutation group" with "generators"
g1, ..., gn. We sometimes write
G = subset S_X.
Remark: The above definition can be generalized: Replace S_X
by any group S which includes all the generators g1, ..., gn.
The resulting set G is called the "group generated by the
elements g1, ..., gn".
Algorithm:
Input: The generators g1, ..., gn (as permutations in S_X),
Output: The elements of G
S = {g1, ..., gn, g1^(1), ..., gn^(1) },
L = S union {1},
for g in S do
for h in L do
if g*h not in L then L = L union {g*h} endif
endfor
endfor
Note that the size of the list L in the for loop changes after
each iteration of the loop. The meaning of this is that the
ifthen command is to be executed exactly once for each element
of the list.
Exercise: Verify that a permutation group G satisfies the four
properties of a group (G1)(G4).
Definition: If G is a group then the "order" of G, denoted
G, is the number of elements of G. If g is an element of
the group G then the order of g, denoted ord(g), is the
smallest positive integer m such that g^m=1, if it exists.
If such an integer m does not exist then we say that g has
"infinite order".
Exercise: Let X = {1,2,3}.
(a) Let G be the permutation group with generator s1, G = .
What is the order of G?
(b) What is the order of s5?
(c) Let G be the permutation group with generator s3, G = .
What is the order of G?
(d) Find the order of s4.
(e) Show that S_X = .
If G is a permutation group G with only one generator
then we say that G is "cyclic".
Lemma: If G = is cyclic with generator g then G=ord(g).
proof: Let m=ord(g), so g^m = 1. We can list all the elements
of G as follows:
1, g, g^2, ..., g^(m1).
There are m elements in this list (we can prove this by contradiction:
if not then g^j=g^k, some j < k in between 0 and m1, which implies
g^(kj)=1, so 0 be a cyclic subgroup
generated by a permuattion g of the set {1,2,...,n}. With
respect to the equivalence relation in the previous exercise,
show that a subgroup K of G belongs to the equivalence
class [H] of H in G if any only if K is cyclic and is
generated by an element k of G conjugate to g in G.