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 if-then 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^(m-1). 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 m-1, which implies g^(k-j)=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. 