Chapter 8 Cayley Theorem and Puzzles “As for everything else, so for a mathematical theory: beauty can be perceived but not explained.”(Arthur Cayley) We have seen that the symmetric group Sn of all the permutations of n objects has order n!, and that the dihedral group D3 of symmetries of the equilateral triangle is isomorphic to S3 , while the cyclic group C2 is isomorphic to S2 . We now wonder whether there are more connections between finite groups and the group Sn . There is in fact a very powerful one, known as Cayley Theorem: Theorem 15. Every finite group is isomorphic to a group of permutations (that is to some subgroup of Sn ). This might be surprising but recall that given any finite group G = {g1 , g2 , . . . , gn }, every row of its Cayley table g1 = e g2 g3 ··· gn gr g1 gr g3 ··· gr gn g1 g2 .. . gr .. . gr g2 gn is simply a permutation of the elements of G (gr gs ∈ {g1 , g2 , . . . , gn }). 171 172 CHAPTER 8. CAYLEY THEOREM AND PUZZLES Groups and Permutation Groups • We saw that D3=S3 and C2=S2. • Is there any link in general between a given group G and groups of permutations? • The answer is given by Cayley Theorem! Cayley Theorem Theorem Every finite group is isomorphic to a group of permutations. This means a subgroup of some symmetric group. One known link: for a group G, we can consider its multiplication (Cayley) table. Every row contains a permutation of the elements of the group. 173 Proof. Let (G, ·) be a group. We shall exhibit a group of permutations (Σ, ◦) that is isomorphic to G. We have seen that the Cayley table of (G, ·) has rows that are permutations of {g1 , g2 , . . . , gn }, the elements of G. Therefore let us define Σ = {σg : G → G, σg (x) = gx, ∀x ∈ G} for g ∈ G. In words we consider the permutation maps given by the rows of the Cayley table. We verify that Σ is a group under map composition. 1. To prove that Σ is closed under composition, we will to prove that σg2 ◦ σg1 = σg2 g1 , g1 ∈ G, g2 ∈ G. Indeed, for every x ∈ G, σg2 (σg1 (x)) = σg2 (g1 x) = g2 (g1 x) = (g2 g1 )x = σg2 g1 (x) ∈ Σ since g2 g1 ∈ G. 2. Map composition is associative. 3. The identity element is σe (x) = ex, since σg ◦ σe = σg·e = σg , σe ◦ σg = σe·g = σg . 4. The inverse. Consider g and g −1 , we have gg −1 = g −1 g = e. From σg2 ◦ σg1 = σg2 g1 we have σg ◦ σg−1 = σe = σg−1 ◦ σg . P Now we claim that (G, ·) and ( , ◦) are isomorphic, where the group isomorphism is given by φ : G → Σ, g 7→ σg . Clearly if σg1 = σg2 then g1 e = g2 e ⇒ g1 = g2 . If g1 = g2 , then σg1 = σg2 . Hence the map is one-to-one and onto, by construction! Let us check that φ is a group homomorphism. If g1 , g2 ∈ G, φ(g1 g2 ) = σg1 g2 = σg1 ◦ σg2 = φ(g1 ) ◦ φ(g2 ), and hence we are done, φ is an isomorphism between (G, ·) and a permutation group! 174 CHAPTER 8. CAYLEY THEOREM AND PUZZLES Proof of Cayley Theorem (I) • We need to find a group Σ of permutations isomorphic to G. • Define Σ={ σg : G →G, σg(x)=gx , g in G} • The set Σ forms a group of permutations: These are the permutations given by the rows of the Cayley table! o It is a set of permutations (bijections). o The identity is σ1 since it maps x to x. o Associativity is that of map composition. o Closure: we have that σg1 σg2 = σg1g2. o Inverse: we have that σg σg(-1) = σ1. Proof of Cayley Theorem (II) • Left to prove: G and Σ are isomorphic. • We define a group isomorphism φ: G →Σ , φ(g)=σg. o The map φ is a bijection. o The map φ is a group homomorphism: φ(g1g2)=φ(g1) φ(g2). [Indeed: φ(g1g2)= σg1g2 = σg1 σg2 =φ(g1) φ(g2).] 175 Now that we saw that all finite groups are subgroups of Sn , we can understand better why we could describe the symmetries of bounded shapes by the cyclic group Cn or the dihedral group Dn which can be mapped in a natural way to permutations of the vertex locations in the plane. Example 30. Consider the group of integers modulo 3, whose Cayley table is 0 1 2 0 0 1 2 1 1 2 0 2 2 0 1 We have σ0 (x) = x + 0 corresponding to the permutation identity (). Then σ1 (x) = x + 1 corresponding to the permutation (123), σ2 (x) = x + 2 corresponding to (132). Since we have a group homomorphism, addition in G = {0̄, 1̄, 2̄} corresponds to composition in Σ = {σ0 , σ1 , σ2 }. For example 1̄ + 1̄ = 2̄ ⇐⇒ (123)(123) = (132). We next illustrate how the techniques we learnt from group theory can be used to solve puzzles. We start with the 15 puzzle. The goal is to obtain a configuration where the 14 and 15 have been switched. Since this puzzle involves 16 numbers, we can look at it in terms of permutations of 16 elements. Let us assume that when the game starts, the empty space is in position 16. Every move consists of switching the empty space 16 and some other piece. To switch 14 and 15, we need to obtain the permutation (14 15) as a product of transpositions, each involving the empty space 16. Now the permutation (14 15) has parity -1, while the product of transpositions will always have parity 1, since 16 must go back to its original position, and thus no matter which moves are done, the number of vertical moves are even, and the number of horizontal moves are even as well. 176 CHAPTER 8. CAYLEY THEOREM AND PUZZLES Example Take G={0,1,2} the group of integers mod 3. 0 1 2 0 0 1 2 1 1 2 0 (123) 2 2 0 1 (132) () • You can check the consistency of the operations! (homomorphism) • For example: 1+1 =2 ↔ (123)(123)=(132) This is a subgroup of S3. A Historical Point of View Lagrange ~1770 Galois ~1830 Cauchy~1820-1840 Kronecker~1870 Klein ~1880 Lie ~1880 Number Theory Geometry Permutations (Jordan ~1880) Group Theory [The symmetric group is complicated! Needs more tools.] Cayley ~1854 (modern definition of group) 177 Some Applications • Symmetries • Cryptography • Puzzles Symmetries One of the main focuses of this class • Symmetries of finite planar shapes (cyclic and dihedral groups) • Symmetries of some infinite planar shapes (Frieze groups, later!) One could also study symmetries of 3-dimensional shapes! A tetrahedral AB4 molecule (ex. methane CH4) with symmetric group A4. 178 CHAPTER 8. CAYLEY THEOREM AND PUZZLES 15 Puzzle 15 14 • 1870, New England • 1890, price of 1000$ to who could solve it. Impossibility of the 15 Puzzle (I) Every move involves switching the empty space (say 16) and some other piece. 11 12 11 15 15 (12 16) 11 12 15 (11 16) 15 12 (15 16) Solving the puzzle means we can write: (14 15)= (an 16)(an-1 16) …(a2 16)(a1 16) 11 15 12 12 (12 16) 11 179 We next consider a solitaire puzzle. The goal of the game is to finish with a single stone in the middle of the board. This does not seem very easy! We might ask whether it would be easier to finish the game by having a single stone anywhere instead. To answer this question, we consider the Klein group, and label every position of the board with an element of the Klein group, such that two adjacent cells multiplied together give as result the label of the third cell (this is done by horizontally and vertically). The value of the board is given by multiplying all the group elements corresponding to board positions where a stone is. The key observation is that the value does not change when a move is made. When the game starts, and only one stone is missing in the middle, the total value of the board is h (with the labeling shown on the slides). Since a move does not change the total value, we can only be left with a position containing an h. Since the board is unchanged under horizontal and vertical reflections, as well as under rotations by 90, 180, and 270 degrees, this further restricts the possible positions containing a valid h, and in fact, the easiest version is as hard as the original game! Other applications of group theory can be found in the area of cryptography. We already saw Caesar cipher, and affine ciphers. We will see some more: (1) check digits and (2) the RSA cryptosystem. 180 CHAPTER 8. CAYLEY THEOREM AND PUZZLES Impossibility of the 15 Puzzle (II) Solving the puzzle means we can write: (14 15)= (an 16)(an-1 16) …(a2 16)(a1 16) parity = -1 parity = 1 16 must return to its place, thus both number of horizontal and vertical moves are even! Solitaire (I) 181 Solitaire (II) • A move = pick up a marble, jump it horizontally or vertically (but not diagonally) over a single marble into a vacant hole, removing the marble that was jumped over. • A win = finish with a single marble left in the central hole. • Would it be easier if a win = finish with a single marble anywhere? Solitaire (III) • G={1,f,g,h} = Klein group • Label the board such that labels of two cells multiplied together give the label of the third cell. Binary operation of the Klein group 182 CHAPTER 8. CAYLEY THEOREM AND PUZZLES Solitaire (IV) • total value of the board = the group element obtained by multiplying together the labels of all of the holes that have marbles in them. • the total value does not change when we make a move! Solitaire (V) Total value =h Total value= ? • (fgh)15= fgh=e • without h, we have fg=h. Since a move does not change the total value, we can only be left with h! 183 Solitaire (VI) A Solitaire board is unchanged under reflection in the horizontal and vertical axes, and rotation through 90°, 180°, 270° and 360°. if this h is valid, then f is valid! Solitaire (VII) If we can solve this position, then we can solve the middle one! We just shown: the “easiest version” is as hard!! 184 CHAPTER 8. CAYLEY THEOREM AND PUZZLES Cryptography: Modular Arithmetic Modular arithmetic (integers modulo n) enables • Caesar’s cipher eK: x → eK(x)=x+K mod 26, K=3 • Affine ciphers eK: x → eK(x)=K1x+K2 mod 26, (K1,26)=1, K=(K1,K2) • RSA cryptosystem eK: x → eK(x)=xe mod n, K=(n,e) Cryptography: Discrete Log Problem • “Regular” logarithm: loga(b) is defined as the solution x of the equation ax = b. • Example: : log2(8)=3 since 23=8. • Discrete logarithm: let G be a finite cyclic group, take g and h in G, logg(h) in G is defined as a solution x of the equation gx = h. • Example: log3(13)=x in the group of invertible integers modulo 17 means that 3x ≡ 13 (mod 17) , and x=4 is a solution. Need to check this is a cyclic group! This is useful in cryptography because solving the discrete log problem is hard! 185 Cryptography: Check Digit (I) Take a message formed by a string of digits. A check digit consists of a single digit, computed from the other digits, appended at the end of the message. It is a form of redundancy to enable error detection. We will look at the Check Digit introduced by J. Verhoeff in 1969, based on the dihedral group D5. Cryptography: Check Digit (II) Multiplication table of D5 with 0=do-nothing, 1-4=rotations, 59=reflections, *=binary operation in D5. * 0 1 2 3 4 5 6 7 8 9 0 0 1 2 3 4 5 6 7 8 9 1 1 2 3 4 0 6 7 8 9 5 2 2 3 4 0 1 7 8 9 5 6 3 3 4 0 1 2 8 9 5 6 7 4 4 0 1 2 3 9 5 6 7 8 5 5 9 8 7 6 0 4 3 2 1 6 6 5 9 8 7 1 0 4 3 2 7 7 6 5 9 8 2 1 0 4 3 8 8 7 6 5 9 3 2 1 0 4 9 9 8 7 6 5 4 3 2 1 0 186 CHAPTER 8. CAYLEY THEOREM AND PUZZLES Cryptography: Check Digit (III) How does it work?Let σ be a permutation in S10. To any string a1a2… an-1 of digits, we append the check digit an so that σ(a1)* σ2(a2)* …*σn-1(an-1)* σn(an)=0. Binary operation Composition of the permutation σ of D5 Single-digit errors are detected: if the digit a is replaced by b, then σi(a) is replaced by σi(b) (σi(a)≠ σi(b) when a≠b) thus the check digit is changed and an error is detected. Cryptography: Check Digit (IV) Example. Take σ=(1,7,9)(2,5,10,4,6) and the digit 12345 (n-1=5). [23456] 2 3 4 5 • σ(2)=5, σ (3)=3, σ (4)=5, σ (5)=2, σ (6)=6. • 5*3*5*2*6* σ6(a6)=0 5* σ6(a6)=0 σ6(a6)= 5 and a6=2. • We get [234562] that is 123451. Check digit 8 on a German banknote. 187 Application of Euler Theorem: RSA RSA is an encryption scheme discovered by River, Shamir and Adleman (in 1978). Alice and Bob Story Alice and Bob want to exchange confidential data in the presence of an eavesdropper Eve. 188 CHAPTER 8. CAYLEY THEOREM AND PUZZLES Alice and Bob story by xkcd RSA Protocol (I) • Select two distinct large primes p and q (“large” means 100 digits ). This function counts the integers coprime to n. • Compute n=pq. • The Euler totient function of n is = (p-1)(q-1). • Pick an odd integer e such that e is coprime to • Find d such that ed = 1 modulo . e exists because it is coprime to the Euler totient function! Publish e and n as public keys, keep d private. . 189 RSA Protocol (II) • Alice: public key = (n,e), d is private. • Bob sends m to Alice via the following encryption: c =me mod n. • Alice decrypts: m = cd mod n. Why can Alice decrypt? Step 1 cd mod n = (me)d mod n. Step 2 We have ed =1 +k . Step 3 Now (me)d mod n = m 1+k coprime to n. = m mod n when m is 190 CHAPTER 8. CAYLEY THEOREM AND PUZZLES Exercises for Chapter 8 Exercise 40. • Let G be the Klein group. Cayley’s Theorem says that it is isomorphic to a subgroup of S4 . Identify this subgroup. • Let G be the cyclic group C4 . Cayley’s Theorem says that it is isomorphic to a subgroup of S4 . Identify this subgroup. Exercise 41. Show that any rearrangement of pieces in the 15-puzzle starting from the standard configuration (pieces are ordered from 1 to 15, with the 16th position empty) which brings the empty space back to its original position must be an even permutation of the other 15 pieces. Exercise 42. Has this following puzzle a solution? The rule of the game is the same as the solitaire seen in class, and a win is a single marble in the middle of the board. If a win is a single marble anywhere in the board, is that any easier?