301 Abstract Algebra 2:00 - 2:50 MWF Hentzel 432 Carver hentzel@iastate.edu Web Page http://www.math.iastate.edu/hentzel/class.301 Text: A First Course in Abstract Algebra, sixth Edition by John B. Fraleigh Course: Chapter 1,2,3,4,5 The material we are covering today is on Page 197 to 208 Section 2.3 beginning with "Group Action on a Set." Friday September 14, 2001 Previous Problems: (1) How many ways can you paint the faces of a cube with 2 colors? I ()()()()()() 1*64 = 64 3 Face 2 ()()( , , , ) 6* 8 = 48 1 ()()( , )( , ) 3*16 = 48 4 Corner 2 ( , , )( , ,) 8* 4 = 32 6 Edge ( , )( , )( , ) 6* 8 = 48 ----- ----- 24 240/24 = 10 <----answer (6,0) (5,1) (4,2) (3,3) 2 2 4 2 <---number of each type (2) How many ways can you paint the faces of a cube with 3 colors? I ()()()()()() 1*729 = 729 3 Face 2 ()()( , , , ) 6* 27 = 162 1 ()()( , )( , ) 3* 81 = 243 4 Corner 2 ( , , )( , ,) 8* 9 = 72 6 Edge ( , )( , )( , ) 6* 27 = 162 ----- ----- 24 1368/24 = 57 (3) How many 8 bead necklaces are there with 2 colors? I (12345678) 4 Edge Flips ( , )( , )( , )( , ) (1357)(2468) 4 Corner Flips ()()( , )( , )( , ) (14725836) (15)(26)(37)(48) (16385274) (1753)(2864) (18765432) 1 ()()()()()()()() 1*256 = 256 4 ( , , , , , , , ) 4* 2 = 8 2 ( , , , )( , , , ) 2* 4 = 8 5 ( , )( , )( , )( , ) 5* 16 = 80 4 ()()( , )( , )( , ) 4* 32 = 128 -------------- ---------- 16 480/16 = 30 <--answer (8,0) (7,1) (6,2) (5,3) (4,4) 2 2 8 10 8 (4) How many 8 bead necklaces are there with 3 colors? 1 ()()()()()()()() 1*6561 = 6561 4 ( , , , , , , , ) 4* 3 = 12 2 ( , , , )( , , , ) 2* 9 = 18 5 ( , )( , )( , )( , ) 5* 81 = 405 4 ()()( , )( , )( , ) 4* 243 = 972 -------------- ---------- answer 16 7968/16 = 498 Main Idea: All that computation of Wednesday has a rational explanation. Key Words: Groups acting on Sets, F(s), orbit, same, related, equivalent. Objective: Prove Burnside's Counting Theorem page 205. A group G acts on a set S if for each g in G and s in S, there is an element g*s in S and the product * satisfies: (a) e*s = s for all s in S. (b) (g1g2)*s = g1*(g2*s) for all s in S and g1,g2 in G. Essentially, two objects in S are considered the "same", or are "equivalent", or are "related" if there is an element in the group G which maps one object into the other. The set of objects equivalent to an element s of S is called the orbit of s. It is relatively obvious that S is partitioned into these orbits. Objects within one orbit of the partion are all related to each other. Objects in different orbits are not related. The number of orbits is the number of distinct objects. We now show a relation between cosets in the group and the elements of the orbit. The Group The Set |-------------------| _________________ | | .. | | |-------------------| | | | | .. | | |-------------------| | o o | | | bH | o o | |-------------------| | o o | | | aH | s o | |-------------------| | o o | | | H=Stabilizer(s) | orbit of s | |-------------------| ----------------- Pick any s in S, then the stabilizer of s written Stabilizer(s) is the set of all elements g of G such that g*s = s. Stabilizer(s) is a subgroup of G. Furthermore, each element of the orbit of s corresponds to a coset of G/Stabilizer(s). In short, the size of the orbit of s in S is the index of the Stabilizer of s. Proof. gH*s = g*(H*s) = g*s. So every element of gH sends s into the same element. This says that there cannot be more elements in the orbit of s than there are cosets. Now suppose that two cosets, aH and bH send s to the same element. Then aH*s = bH*s. Then a*s = b*s -1 -1 b a*s = s and so b a is in H, the stabilizer. -1 We conclude that bH contains b(b a) = a and as aH n bH is not empty, aH = bH. Thus if two of the cosets map s to the same element, then these two cosets are in fact the same coset. So the size of the orbit of s is the same as the number of cosets of the stabilizer of s. Now each element in an orbit generates that orbit. All elements in the orbit of s generate the same orbit. They therefore all have the same size orbit. They also, consequently, all have a stabilizer of the same size as well. If we sum the size of these stabilizers we get over the elements in this one orbit we get: (size of the orbit)*(size of each stabilizer). But this is just: (number of cosets)*(size of the stabilizer) = size of G. This proves half of Bernside's theorem: Theorem (Bernside); The number of orbits is 1 ---- SUM (number of elements in G which fix s) |G| s in S The other half of the Bernside Theorem is: Theorem (Bernside): The number of orbits is 1 ------ SUM F(g) where F(g) is the number of elements in S |G| g in G which are fixed by g in G. Proof. All we have to show is that SUM (number of elements in G which fix s) = SUM F(g) s in S g in G Proof: Simply count the number of elements in this set in two ways. W = { (g,s) | g*s = s }. If we sort by g's, for each g in G we count the number of elements in s which are fixed by that g. If we sort by s's, for each s in S, we count the number of elements in G which fix s. Both ways give us the number of elements in W. Thus both Sums give the same value. The reasoning behind the algorithm for counting given in the previous lecture is this. The answer we want is the number of orbits. By Burnside's theorem 1 number of orbits = ----- SUM F(g). |G| g in G For each g in G we compute the number of elements that it fixes. We compute this from the cycle structure. If after the object was moved by g the object appears not to have been changed, then the colors of the vertices in the same cycle have to be the same color. So the number of objects left fixed by g is the number of ways to color the object so that vertices in the same cycle of g are the same color. This is what we count when we count the number of ways to color the cycles. Problems: 1(a). How many 6 bead necklaces are there using exactly 2 red, 2 blue, and 2 green beads? (b). How many 8 bead necklaces are there using exactly 3 red and 5 blue beads? (c). How many 8 bead necklaces are there using exactly 4 red and 4 blue beads? 2. Suppose that G is a finite group. Let H be a subgroup of G. -1 For fixed element g of G, prove that gHg is also a subgroup of G. 3. Let S be the collection of all subgroups of G. Show that the action * of G acting of S where if g is in G and H is in S, -1 then g*H = g H g satisfies the requirements of a group acting -1 -1 -1 on a set. Hint: Show (ab) = b a . 4. How many elements are there in the group of symmetries of: (a) the equilateral triangle, (b) the square, (c) the pentagon, (d) the octahedron, (e) the dodecahedron.