[PDF] Group Theory and the Rubik's Cube - Harvard University

View - Download Group Theory and the Rubik's Cube - Harvard University

Previous PDF

Next PDF

Group Theory and the Rubik's Cube

Janet Chen

A Note to the Reader

These notes are based on a 2-week course that I taught for high school students at the Texas State Honors

Summer Math Camp. All of the students in my class had taken elementary number theory at the camp, so

I have assumed in these notes that readers are familiar with the integers modnas well as the units modn.

Because one goal of this class was a complete understanding of the Rubik's cube, I have tried to use notation

that makes discussing the Rubik's cube as easy as possible. For example, I have chosen to use right group

actions rather than left group actions. 2

Introduction

Here is some notation that will be used throughout.

Zthe set of integers:::;3;2;1;0;1;2;3;:::

Nthe set of positive integers 1;2;3;:::

Qthe set of rational numbers (fractions)

Rthe set of real numbers

Z=nZthe set of integers modn

(Z=nZ)the set of units modn

The goal of these notes is to give an introduction to the subject of group theory, which is a branch of the

mathematical area called algebra (or sometimes abstract algebra). You probably think of algebra as addition,

multiplication, solving quadratic equations, and so on. Abstract algebra deals with all of this but, as the

name suggests, in a much more abstract way! Rather than looking at a specic operation (like addition) on

a specic set (like the set of real numbers, or the set of integers), abstract algebra is algebra done without

really specifying what the operation or set is. This may be the rst math you've encountered in which objects other than numbers are really studied!

A secondary goal of this class is to solve the Rubik's cube. We will both develop methods for solving the

Rubik's cube and prove (using group theory!) that our methods always enable us to solve the cube.

References

Douglas Hofstadter wrote an excellent introduction to the Rubik's cube in the March 1981 issue ofScientic

American. There are several books about the Rubik's cube; my favorite isInside Rubik's Cube and Beyond

by Christoph Bandelow. David Singmaster, who developed much of the usual notation for the Rubik's cube,

also has a book calledNotes on Rubik's 'Magic Cube,'which I have not seen.

For an introduction to group theory, I recommendAbstract Algebraby I. N. Herstein. This is a wonderful

book with wonderful exercises (and if you are new to group theory, you should do lots of the exercises). If

you have some familiarity with group theory and want a good reference book, I recommendAbstract Algebra

by David S. Dummit and Richard M. Foote. 3

1. Functions

To understand the Rubik's cube properly, we rst need to talk about some dierent properties of functions.

Denition 1.1.Afunction ormapffrom a domainDto a rangeR(we writef:D ! R) is a rule which assigns to each elementx2 Da unique elementy2 R. We writef(x) =y. We say thatyis theimage ofx and thatxis apreimage ofy. Note that an element inDhas exactly one image, but an element ofRmay have0,1, or more than1preimage. Example 1.2.We can dene a functionf:R!Rbyf(x) =x2. Ifxis any real number, its image is the real numberx2. On the other hand, ifyis a positive real number, it has two preimages,pyandpy. The real number 0 has a single preimage, 0; negative numbers have no preimages.v

Functions will provide important examples of groups later on; we will also use functions to \translate"

information from one group to another. Denition 1.3.A functionf:D ! Ris calledone-to-one ifx16=x2impliesf(x1)6=f(x2)forx1;x22 D. That is, each element ofRhas at most one preimage. Example 1.4.Consider the functionf:Z!Rdened byf(x) =x+ 1. This function is one-to-one since, ifx16=x2, thenx1+ 16=x2+ 1. Ifx2Ris an integer, then it has a single preimage (namely,x1). If x2Ris not an integer, then it has no preimage. The functionf:Z!Zdened byf(x) =x2is not one-to-one, sincef(1) =f(1) but 16=1. Here, 1 has two preimages, 1 and1.v Denition 1.5.A functionf:D ! Ris calledonto if, for everyy2 R, there existsx2 Dsuch that f(x) =y. Equivalently, every element ofRhas at least one preimage. Example 1.6.The functionf:Z!Rdened byf(x) =x+ 1 is not onto since non-integers do not have preimages. However, the functionf:Z!Zdened byf(x) =x+ 1 is onto. The functionf:Z!Zdened byf(x) =x2is not onto because there is nox2Zsuch thatf(x) = 2.v

Exercise 1.7.Can you nd a ...

1. . ..functionwhich is neither one-to-one nor on to? 2. . ..functionwhich is one-to-one but not onto? 3. . ..functionwhich is onto but not one-to-one? 4. . ..functionwhich is b othone-to-one and on to? Denition 1.8.A functionf:D ! Ris called abijection if it is both one-to-one and onto. Equivalently, every element ofRhas exactly one preimage. Example 1.9.The functionf:Z!Zdened byf(x) =x+ 1 is a bijection.v Example 1.10.IfSis any set, then we can dene a mapf:S ! Sbyf(x) =xfor allx2 S. This map is called theidentitymap, and it is a bijection.v Denition 1.11.Iff:S1! S2andg:S2! S3, then we can dene a new functionfg:S1! S3by (fg)(x) =g(f(x)). The operationis calledcomposition. Remark 1.12.One usually writes(gf)(x) =g(f(x))rather than(fg)(x) =g(f(x)). However, as long

as we are consistent, the choice does not make a big dierence. We are using this convention because it

matches the convention usually used for the Rubik's cube. 4

Exercises

1. Whic hof the follo wingf unctionsare one-to-one? Whic hare on to? (a)f:Z!Zdened byf(x) =x2+ 1. (b)f:N!Ndened byf(x) =x2+ 1. (c)f:Z!Zdened byf(x) = 3x+ 1. (d)f:R!Rdened byf(x) = 3x+ 1. 2. Supp osef1:S1!S2andf2:S2!S3are one-to-one. Prove thatf1f2is one-to-one. 3. Supp osef1:S1!S2andf2:S2!S3are onto. Prove thatf1f2is onto. 4. Let f1:S1!S2,f2:S2!S3, andf3:S3!S4. Prove thatf1(f2f3) = (f1f2)f3. 5.

Let Sbe a set.

(a) Pro veth atthere exists a function e:S!Ssuch thatef=fandfe=ffor all bijections f:S!S. Prove thateis a bijection.S. (b) Pro vethat, for ev erybijection f:S!S, there exists a bijectiong:S!Ssuch thatfg=e andgf=e. 6. If f:D ! Ris a bijection andDis a nite set withnelements, prove thatRis also a nite set with nelements. 5

2. Groups

Example 2.1.To get an idea of what groups are all about, let's start by looking at two familiar sets.

First, consider the integers mod 4. Remember thatZ=4Zis a set with 4 elements: 0, 1, 2, and 3. One of

the rst things you learned in modular arithmetic was how to add numbers modn. Let's write an addition

table forZ=4Z. +0 1 2 3

00 1 2 3

11 2 3 0

22 3 0 1

33 0 1 2

Now, we're going to rewrite the addition table in a way that might seem pretty pointless; we're just going

to use the symbolinstead of + for addition, and we'll writee= 0,a= 1,b= 2, andc= 3. Then, our addition table looks likee a b c ee a b c aa b c e bb c e a cc e a b

Let's do the same thing for (Z=5Z), the set of units mod 5. The units mod 5 are 1, 2, 3, and 4. If you add

two units, you don't necessarily get another unit; for example, 1 + 4 = 0, and 0 is not a unit. However, if

you multiply two units, you always get a unit. So, we can write down a multiplication table for (Z=5Z).

Here it is:1 2 4 3

11 2 4 3

22 4 3 1

44 3 1 2

33 1 2 4

Again, we're going to rewrite this using new symbols. Letmean multiplication, and lete= 1,a= 2,b= 4, andc= 3. Then, the multiplication table for (Z=5Z)looks like e a b c ee a b c aa b c e bb c e a cc e a b Notice that this is exactly the same as the table for addition onZ=4Z!

Why is it interesting that we get the same tables in these two dierent situations? Well, this enables us to

translate algebraic statements about addition of elements ofZ=4Zinto statements about multiplication of

elements of (Z=5Z). For example, the equationx+x= 0 inZ=4Zhas two solutions,x= 0 andx= 2. With our alternate set of symbols, this is the same as saying that the equationxx=ehas solutionsx=e andx=b. If we translate this to (Z=5Z), this says that the solutions ofxx= 1 in (Z=5Z)arex= 1 andx= 4. That is, 1 and 4 are the square roots of 1 in (Z=5Z), which is exactly right! In mathematical language, we say thatZ=4Zwith addition and (Z=5Z)with multiplication are \isomorphic

groups." The word \isomorphic" means roughly that they have the same algebraic structure; we'll get into

this later. For now, let's just see what a \group" is.v Denition 2.2.Agroup(G;)consists of a setGand an operationsuch that: 6

1.Gis closed under. That is, ifa;b2G, thenab2G.

Examples:

Z=4Zis closed under+; after all, we wrote down the addition table, which tells us how to add any two elements ofZ=4Zand get another element ofZ=4Z. Similarly,(Z=5Z)is closed under multiplication. Zis closed under+: ifa;b2Z, thena+b2Z. Similarly,Zis also closed under. Ris closed under multiplication: if we multiply two real numbers, we get a real number. The set of negative numbers is not closed under multiplication: if we multiply two negative num- bers, we get a positive number.

2.is associative. That is, for anya;b;c2G,a(bc) = (ab)c.

Examples:

Addition and multiplication are associative.

Subtraction is not associative becausea(bc)6= (ab)c. 3. Ther eis an \identity element" e2Gwhich satisesg=eg=gefor allg2G.

Examples:

For(Z=4Z;+),0is an identity element becauseg= 0 +g=g+ 0for anyg2Z=4Z. For ((Z=5Z);),1is an identity element becauseg= 1g=g1for anyg2(Z=5Z). For(Z;+),0is an identity element becauseg= 0 +g=g+ 0for anyg2Z. For(R;),1is an identity element becauseg= 1g=g1for anyg2R. 4. Inverses exist; that is, for any g2G, there exists an elementh2Gsuch thatgh=hg=e. (his called aninverse ofg.)

Examples:

Using the addition table forZ=4Z, we can nd inverses of all the elements ofZ=4Z. For instance, we can see from the table that1 + 3 = 3 + 1 = 0, so3is the inverse of1. Similarly, since the table for(Z=5Z)is identical, all elements of(Z=5Z)have inverses. For(Z;+), the inverse ofn2Zisnbecausen+ (n) = (n) +n= 0. For(R;), not every element has an inverse | namely,0does not have an inverse. However, if x6= 0, then1x is an inverse ofxbecausex1x =1x x= 1.

Example 2.3.

1. ( Z=4Z;+) and ((Z=5Z);) are groups. In fact, as we said earlier, these should be thought of as the \same" group, but we won't go into this until later. 2. ( Z;+) is a group. However, (Z;) is not a group because subtraction is not associative. 3. ( R;) is not a group since 0 does not have an inverse under multiplication. However, (R f0g;) is a group. 4. The set of negativ en umbersis not closed under m ultiplication,so the set of negativ en umberswith multiplication is not a group. 5. W ecan construct a group ( G;) whereGis a set with just one element. SinceGmust have an identity element, we will call this single elemente. To dene the group operation, we just need to say what eeis. There is only one choice sinceGhas only one element:eemust bee. This denes a group which is called thetrivialgroup. As you might guess, the trivial group isn't very interesting. 6. So on,w ewill see ho wto mak ethe mo vesof a Rubik's cub ein toa group! 7 v The examples of groups we have seen so far all have another special property: for everyg;h2G,gh=hg;

that is, theoperation is commutative. This isnottrue of all groups. If it is true of (G;), we say (G;) isabelian. We will soon see examples of nonabelian groups.

Now, we will prove two important properties of groups. Lemma 2.4.A group has exactly one identity element. Proof.Let (G;) be a group, and supposeeande0are identity elements ofG(we know thatGhas at least one identity element by the denition of a group). Then,ee0=esincee0is an identity element. On the

other hand,ee0=e0sinceeis an identity element. Therefore,e=e0because both are equal toee0.Lemma 2.5.If(G;)is a group, then eachg2Ghas exactly one inverse.

Proof.Letg2G, and supposeg1;g2are inverses ofG(we know there is at least one by the denition of a group); that is,gg1=g1g=eandgg2=g2g=e. By associativity, (g1g)g2=g1(gg2). Sinceg1is an inverse ofg, (g1g)g2=eg2=g2. Sinceg2is an inverse ofg,g1(gg2) =g1e=g1.

Therefore,g2=g1.In general, we write the unique inverse ofgasg1. However, if we know that the group operation is addition,

then we write the inverse ofgasg.

Exercises

1. Whic hof the follo wingare groups? Pro vey ouransw er. (a) ( f1g;) (b) ( S;+), whereSis the set of non-negative integersf0;1;2;3;:::g (c) (2 Z;+), where 2Zis the set of even integers (d) ( Z;) (e) ( Z;?) wherea?bis dened to bea+b1. (f) ( Q f0g;) (g) ( R;H) whereaHbis dened to be (a1)(b1). (h) ( G;) whereGis the set of bijections from some setSto itself anddenotes composition of functions. 2.

Let ( G;) be a group anda;b;c2G. Prove:

(a)

If ab=ac, thenb=c.

(b)

If ba=ca, thenb=c.

That is, we can cancel in groups.

3.

If ( G;) is a group andg2G, prove that (g1)1=g.

4. If ( G;) is a group andg;h2Gsuch thatgh=e, prove thathg=e. (That is, ifgh=e, thenh is the inverse ofgandgis the inverse ofh.) 5. If ( G;) is a group andg;h2Gsuch thatgh=h, prove thatgis the identity element ofG. 6. Let ( G;) be a nite group; that is, (G;) is a group andGhas nitely many elements. Letg2G. Prove that there exists a positive integernsuch thatgn=e(here,gnmeansgggwithncopies ofg). The smallest such integernis called theorder ofg. 8

7.Find the order of 5 in ( Z=25Z;+). Find the order of 2 in ((Z=17Z);).

8. If ( G;) is a group in whichgg=efor allg2G, show that (G;) is abelian. 9. If ( G;) is a group whereGhas 4 elements, show that (G;) is abelian. 10. Let ( G;) be a nite group. Prove that there is a positive integernsuch thatgn=efor allg2G. (This is dierent from Problem 6 in that y ouneed to sho wthat the same nworks for allg2G.) 11. Let Gbe a set andbe an operation onGsuch that the following four properties are satised: (a)Gis closed under. (b)is associative. (c) There exists e2Gsuch thatge=gfor allg2G. (We callea \right identity.") (d) F oreac hg2G, there existsh2Gsuch thatgh=e. (We callha \right inverse" ofg.)quotesdbs_dbs11.pdfusesText_17

[PDF] there is almost always a good reason for slow downs on an expressway

[PDF] there is no additive powder or tablet

[PDF] there is only single copy of member function in memory when a class is loaded

[PDF] therefore however nevertheless although exercises

[PDF] thermal decarboxylation

[PDF] thermochimie cours pdf psi

[PDF] thermodynamics 2 pdf

[PDF] thermodynamics notes pdf

[PDF] thermodynamics open system problems and solutions

[PDF] thermodynamics solution

[PDF] thermodynamics steam table problems pdf

[PDF] thermodynamics: closed system problems and solutions

[PDF] thermodynamique chimique smc s4 pdf

[PDF] thermodynamique cours pdf

[PDF] thermodynamique cours pdf mpsi