20131115

Please Login to access more options.

Today

You can either jump straight into these problems, or revisit problems 3,4, and 6 from Wednesday. If you are stuck on Wednesday's, then instead please just start on the problems below, and then go back to Wednesday's (they're in the open problem list now). The problems below are specific examples of the ideas you are asked to prove on Wednesday's work.

Many of you need to revisit part 2 of problem 3 from Wednesday. You needed to show that either $Ha\cap Hb=\emptyset$ or $Ha=Hb$. THere are two cases. Either we have $Ha\cap Hb=\emptyset$ or we have $Ha\cap Hb\neq\emptyset$. In the second case you have to prove that $Ha=Hb$. This problem is equivalent to proving "If $Ha\cap Hb\neq \emptyset$ then $Ha=Hb$." I have a feeling that many of you can prove the latter, but your logical structure for proving an "Either/Or" statement is off (there are two cases). Please take a look at this problem again.

The problems below are very computational in nature. They ask you to repeatedly look at subgroups, cosets, identification graphs, and analyzing the relationship between them. The goal of doing these problems is to look for patterns, not blindly do hundreds of computations. So as you do these problems, ask yourself what general patterns you see. When you see the general pattern, describe it. Make conjectures. These conjectures are crucial to understanding. When you have made the conjecture yourself, you're more motivated to take the time to prove that your conjecture is true.

If you see the general pattern on the problems below, state the pattern. Then try to state a generalized version of the pattern you see. Most of mathematics is built because someone took the time to carefully study a single example in excruciating detail, extract the key principle from that problem, and then abstract the idea into an abstract setting that applies the principle in thousands of other places.

Problem (Practice With Homomorphisms from $\mathbb{Z}_n$ to $\mathbb{Z}_d$)

Let $G=\mathbb{Z}_{12}$ and $H=\mathbb{Z}_3$. Consider the map $f:G\to H$ defined by $f(x)=x\mod 3$.

1. Show that $f$ is a homomorphism. What is the kernel $K$ of $f$.
2. Draw Cayley graphs of $G$ and $H$ using the generating set $S=\{1\}$ in both cases, and then draw the identification graph of $G$ using right (or left) cosets of $K$.
3. How many elements are in $G$, $H$, and $K$? What relationship is there between these?
4. Repeat parts 1-3 if you use $H=\mathbb{Z}_2$ with $f(x)=x\mod 2$.
5. Repeat parts 1-3 if you use $H=\mathbb{Z}_4$ with $f(x)=x\mod 4$.
6. Repeat parts 1-3 if you use $H=\mathbb{Z}_6$ with $f(x)=x\mod 6$.
7. Pick a positive integer $n$ and a divisor $d$ of $n$. Then repeat 1-3 if $G=\mathbb{Z}_n$, $H=\mathbb{Z}_d$, and $f$ is defined by $f(x)=x\mod d$.

You're welcome to stop when you see a general pattern, provided you describe the general pattern if $G=\mathbb{Z}_{n}$ and $H=\mathbb{Z}_d$.

Problem (Problem.Practice With Identification Graphs Of $\mathbb{Z}$)

Let $G=\mathbb{Z}$ and consider the subgroup $N=3\mathbb{Z}$.

1. There are infinitely many possible ways to write cosets of $N$, namely we have $0+3\mathbb{Z}$, $1+3\mathbb{Z}$, $2+3\mathbb{Z}$, $3+3\mathbb{Z}$, $4+3\mathbb{Z}$, etc. Show that there are finitely many different cosets.
2. Draw Cayley graphs of $G$ using the generating set $S=\{1\}$ in both cases, and then draw the identification graph of $G$ using right (or left) cosets of $N$. As there are only finitely many cosets, you should obtain a finite graph for the identification graph.
3. Can you think of a group $H$ and a homomorphism $f:\mathbb{Z}\to H$ so that the kernel of $f$ is the subgroup $N=3\mathbb{Z}$? Hint: look at the previous problem.
4. Repeat parts 1-3 if you use $H=\mathbb{Z}_5$ with $f(x)=x\mod 5$.
5. Repeat parts 1-3 if you use $H=\mathbb{Z}_n$ with $f(x)=x\mod n$.
6. What does this problem have to do with modular arithmetic?

Problem (Subgroups Cosets And Identification Graphs Of The Automorphisms Of The Square)

Let $G$ be the automorphism group of the square, so the dihedral group of order 8.

1. Make a list of all the subgroups of $G$. You should have 1+5+3+1=10, namely 1 of order 1, 5 of order 2, 3 of order 4, and 1 of order 8. Think about the game "generate/don't generate" and build these subgroups by spanning elements of $G$.
2. For each subgroup $H$, make a list of the right cosets of $H$. Then construct an identification graph of $G$ using the right cosets of $H$. What relationship is there between $|G|$, $|H|$, and the number of vertices in the identification graph?
3. A Cayley graph has exactly one arrow of each color leaving each vertex. Some of your graphs above satisfy this property, and some have more than one arrow of each color leaving each vertex. Go through your list and decide which cannot be Cayley graphs and and which can be.
4. Pick one of the graphs that is a Cayley graph (preferably not $H=\{e\}$ nor $H=G$). For that subgroup $H$, compute the right cosets of $H$.
5. Pick one of the graphs that is not a Cayley graph. For that subgroup $H$, compute the right cosets of $H$.
6. Is there a connection between left and right cosets and when identification graphs are Cayley graphs? What do you notice. Check if you are correct by looking at another subgroup of $H$.

Problem (Coset Products Of The Automorphisms Of The Square)

You'll need your work from the previous problem to continue with this problem.

1. Pick a subgroup $H$ from the previous problem where the indentification graph of $G$ using right cosets of $H$ resulted in a Cayley graph. Compute the set products $(Ha)(Hb)$ for each pair of cosets. Organize your work into a multiplication table. Then repeat this with a different $H$.
2. Pick a subgroup $H$ where the identification graph was not a Cayley graph. Compute the set products $(Ha)(Hb)$ for each pair of cosets. Organize your work into a multiplication table.
3. Does the set product $(Ha)(Hb)$ always result in another coset of $H$? What did you find?

Problem (Continue Working On Open Problems)

Please look at the Open Problems list, and continue working on these. In your preparation, please tell me which of the problems on the list you would feel comfortable presenting to the class. When we have a critical mass of students ready to present each problems, we'll discuss it in class (sometimes with a presentation, sometimes with just a discussion).

For more problems, see AllProblems