Please Login to access more options.


Today

« November 2016 »

Sun

Mon

Tue

Wed

Thu

Fri

Sat

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

From Ben: We finished Wed on 90.

What should you work on?

  • 90 - Show that $Ha=Hb$ iff $b\in Ha$. CRUCIAL PROPERTY.
  • 91 - Prove that right and left cosets of the kernel are equal. This is almost an exact copy of something we already showed about the special linear group.
  • 92 - Similar to 90, just add a few more properties.
  • 93 - SUPER IMPORTANT. You are proving that we can define a way of multiplying cosets.
  • 94 - You are creating a collection of counterexamples.
  • 95 - An interesting example that leads to more understanding of the Euler phi function.
  • 96 - With 92 under your belt, you can quickly prove that the order of every subgroup divides the order of the group.
  • 97 - Show that a few subgroups are normal, so show that $Ha=aH$ for every $a\in G$.
  • 98 - MOST IMPORTANT PROBLEM. We need to see this before thanksgiving.

Problem 82 (Properties Of Cosets)

Let $G$ be a group, and let $H$ be a subgroup of $G$. Let $a,b \in G$. Prove the following:

  1. The function $f:H\to Ha$ defined by $f(h)=ha$ is a bijection.
  2. We have $|H|=|Ha|$.
  3. We know $b\in Ha$ if and only if $Hb=Ha$.

We've seen that when we create an identification graph of $G$ using right cosets of $H$, we sometimes get a Cayley graph, and we sometimes don't. Today, we'll be focusing on the question, "When is an identification graph of $G$ using cosets of $H$ another Cayley graph?" To answer this question, we'll need to explore the properties of cosets in depth.

When working with the determinant map $f:GL(2,\mathbb{Z}_p)\to U(p)$, we have already shown that the kernel of this map is the special linear group $K=SL(2,\mathbb{Z}_p)$. We've also shown that the coset $Ka$ equals the set of all matrices whose determinant matches the determinant of $a$. Another way to say this is that $Ka$ equals the set of values $b\in G(2,\mathbb{Z}_p)$ such that $f(b)=f(a)$. A similar argument would show that $aK$ is the exact same set, which means we have $Ka=aK$. The next problem has you show that for any homomorphism $f:G\to H$ with kernel $K$, we always have $Ka=aK$ and that $Ka$ equals the set of $b\in G$ such that $f(b)=f(a)$.

Problem 83 (The Right And Left Cosets Of The Kernel Are Equal)

Suppose that $f:G\to H$ is a homomorphism. Let $K$ be the kernel of $f$ and let $a\in G$. Prove the following:

  1. The right coset $Ka$ equals the set of values $b\in G$ such that $f(b)=f(a)$, or symbolically we have $$Ka = \{b\in G\mid f(b)=f(a)\} = f^{-1}(f(a)).$$
  2. The left coset $aK$ equals the same set $\{b\in G\mid f(b)=f(a)\}$, which means the left and right cosets are the same or $Ka=aK$.

In the previous problem, we saw that any time $K$ is the kernel of a homomorphism, we can talk about left or right cosets and obtain the exact same result, namely $Ka=aK$ for every $a\in G$. Any time a subgroup of $G$ satisfies this result, we'd like to have a special name for that subgroup. We call these subgroups normal.

Definition (Normal Subgroup $N\trianglelefteq G$)

We say that a subgroup $N$ of $G$ is a normal subgroup of $G$ if for each $a\in G$ the right coset $Na$ and left coset $aN$ are equal, so we have $Na=aN$ for every $a\in G$. We write $N\trianglelefteq G$ to mean that $N$ is a normal subgroup of $G$.

Before we can move too much farther, we need to prove some additional properties about cosets. We have already shown the following for a subgroup $H$ of the group $G$ with $a,b\in G$:

  • We know $a\in Ha$.
  • We know $Ha=H$ if and only if $a\in H$.
  • We know $b\in Ha$ if and only if $Hb=Ha$.
  • The function $f:H\to Ha$ defined by $f(h)=ha$ is a bijection.
  • We have $|H|=|Ha|$.

Let's add to this list of properties.

Problem 84 (Properties Of Cosets Part Two)

Let $H$ be a subgroup of $G$. Let $a,b\in G$. Prove the following facts about cosets.

  1. We have $Ha=Hb$ if and only if $ab^{-1}\in H$.
  2. We must have $Ha=Hb$ or $Ha\cap Hb=\emptyset$.
  3. We have $Ha=aH$ if and only if $aHa^{-1}=H$.

We've already seen all of these properties before when studying modular arithmetic. Let $G=\mathbb{Z}$ and let $H=n\mathbb{Z}$ for some $n\in\mathbb{N}$. The cosets of $H$ are $r+n\mathbb{Z}$ for $0\leq r<n$.

  • The first property above states that $a+n\mathbb{Z}=b+n\mathbb{Z}$ if and only if $a-b\in n\mathbb{Z}$. Wait, this just says two numbers have the same remainder if and only if their difference is a multiple of $n$.
  • The second property above states that either $a$ and $b$ have the same remainder, or they don't. It basically states that remainders are unique.
  • The third property is trivial for $\mathbb{Z}$ because $\mathbb{Z}$ is an Abelian group and we always know $a+n\mathbb{Z}=n\mathbb{Z}+a$.

Problem 85 (The Set Product Is A Binary Operation On Cosets Of Normal Subgroups)

Suppose that $N$ is a normal subgroup of $G$. Let $a,b\in G$, and consider the two cosets $Na$ and $Nb$. Show that the set product $(Na)(Nb)$ is again a coset of $N$, and that we have $(Na)(Nb)=N(ab)$.

This shows that the set product is a binary operation on right cosets (and left cosets) of a normal subgroup $N$.

Click if you want a hint.

You've got to make use of the fact that $Na=aN$ for every $a\in G$. So we have $Nb=bN$, $Nc=cN$, $Nx=xN$, etc. Why is this useful? Any time you see $na$ in your work for some $n\in N$, you know that $na\in Na$ which means $na\in aN$ which means there exists some $n'\in N$ with $na=an'$. You don't have the ability to commute, but we get ALMOST commutativity. We can write $na=an'$ for some different $n'\in N$. The $'$ symbol just means that it's a different element. It's not a derivative.

So in your work if you ever see $bn_1a$, you can instead either write $bn=n_2b$ or you could write $na=an_3$ for some $n_2,n_3\in N$, and then you have $bn_1a = n_2ba=ban_3$. Similarly, if you see $n_1an_2b$, then you should be able to write this, after some work, in either the form $n_3ab$ or the form $abn_4$ (you'll need to use the closure of the operation in $N$ to combine elements in $N$).

You can't use the commutative law, but you have something pretty close.

We need some more examples of homomorphisms. Simple shift permutations from cryptography provides us with quite a few. Make sure you can prove the following exercise.

Exercise (A Homomorphism From $\mathbb{Z}_n$ to $\mathbb{Z}_d$ when $d$ is a divisor of $n$)

Consider the map $f:\mathbb{Z}_{n}\to \mathbb{Z}_d$ defined by $f(x)=x\pmod d$ where $d$ is a divisor of $n$. Show that $f$ is a homomorphism.

Click to see a solution

We need to show that $((x+y)\pmod n)\pmod d = (x\pmod d+y\pmod d)\pmod d$. We know that $a\pmod d=b\pmod d$ if and only if $a-b$ is a multiple of $d$ (does this look like the coset property that says $Ha=Hb$ if and only if $ab^{-1}\in H$?). We just need to show that $(x+y)\pmod n - (x\pmod d+y\pmod d)$ is a multiple of $d$. To do this, first note that using the division algorithm we can write $x\pmod d = x-q_xd$ and $y\pmod d = y-q_yd$ for some integers $q_x$ and $q_y$, and we can write $(x+y)\pmod n = (x+y)-qn$ for some integer $q$. Since we know $d$ is a divisor of $n$, we can also write $n=md$ for some integer $m$. We then compute $$\begin{align} (x+y)\pmod n - (x\pmod d+y\pmod d) &=(x+y-qn)-(x-q_xd)-(y-q_yd)\\ &=-qmd+q_xd+q_yd\\ &=d(q_x+q_y-qm), \end{align}$$ which is a multiple of $d$ as desired.

What happens if $d$ is not a divisor of $n$? Does the map $f:\mathbb{Z}_n\to \mathbb{Z}_d$ defined by $f(x)=x\mod d$ result in a homomorphism?

Problem 94 (When is $x \pmod d$ a homomorphism from $\mathbb{Z}_n$ to $\mathbb{Z}_d$)

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

  1. Is the map $f:G\to H$ a homomorphism? Either prove that it is, or produce a counter example.
  2. Let $n$ be an integer and suppose that the positive integer $d<n$ is not a divisor of $n$. Is the map $f:\mathbb{Z}_n\to \mathbb{Z}_d$ defined by $f(x)=x\mod d$ a homomorphism?

The problems above also give us homomorphisms from $U(n)$ to $U(d)$, as the next problem shows. These maps are crucial in understanding cryptography.

Problem 95 (The set $U_d(n)$ and the homomorphism from $U(n)$ to $U(d)$)

For each integer $n\geq 2$ and each divisor $d$ of $n$, consider the map $f:U(n)\to U(d)$ defined by $f(x)=x\pmod d$.

  1. Show that this map is a homomorphism. [Hint: You will probably want to use the fact that $a\pmod k=b\pmod k$ if and only if $a-b$ is a multiple of $k$. This is the easiest way to prove statements about modular arithmetic. You have to show that two things are equal, namely that $((x\cdot y)\pmod n)\pmod d = ((x \pmod d)\cdot (y \pmod d))\pmod d$. You can remove the outermost $\pmod d$ by instead showing that the difference is a multiple of $d$.]
  2. Then explain why the set $U_d(n)=\{x\in U(n)\mid x\pmod d = 1\}$ is a subgroup of $U(n)$. (Hint: What is the kernel of $f$?)
  3. List the elements of $U_{5}(60)$.

The next theorem should come as no surprise. We've already shown that given any subgroup $H$ of $G$, that every element of $H$ is in one of the cosets of $H$. We've also shown that the cosets of $H$ are disjoint. These two facts together show that we can partition $G$ into a disjoint union of cosets of $H$. We also know that the size of each coset matches the order of $H$. So if we have $r$ disjoint cosets $Ha_1$, $Ha_2$, $Ha_3$, ..., $Ha_r$, all of which have the same number of elements, then we should be able to use this information to show that the order of $H$ divides the order of the group. This fact is called Lagrange's theorem.

Problem 86 (Lagrange's Theorem Proof)

Prove Lagrange's Theorem.

Theorem (Lagrange's Theorem)

Suppose that $G$ is a finite group and that $H$ is a subgroup of $G$. Then the order of $H$ divides the order of $G$. In particular, we know that $|G|/|H|$ equals the number of distinct right (or left) cosets of $H$ in $G$.

We now have shown that the $|G|/|H|$ is precisely the number of cosets of $H$ there are in $G$. From a Cayley graph perspective, this is how many copies of $H$ are visible in the graph, as they are translated throughout the graph. The number of such cosets is called the index of $H$ in $G$, and written $|G:H|$.

Definition (Index of $H$ in $G$, or $|G:H|$)

If $H$ is a subgroup of $G$, then the index of $H$ in $G$, written $|G:H|$, is the number of distinct right (or left) cosets of $H$. Because of Lagrange's theorem, we know that $|G:H|=|G|/|H|$.

We'll now return to looking at when the left and right cosets of a subgroup agree, namely we'll be looking at normal subgroups. Let's first get ourselves a collection of subgroups that are normal.

Problem 87 (Some Normal Subgroups)

Prove the following facts.

  1. If $G$ is Abelian, then every subgroup of $G$ is normal.
  2. The center $Z(G)$ of any group $G$ is always a normal subgroup of $G$.

We are now ready to define a new group using the cosets of a normal subgroup. If $N$ is a normal subgroup of $G$, then we've already shown that the binary operation on the collection of cosets, defined by $(Na)(Nb)=N(ab)$, is well defined. Is this binary operation enough to forma a group? To say yes, we need to show that the operation is associative, that there is there an identity coset, and that every coset has an inverse coset. We're now ready to prove that the collection of cosets of a normal subgroup is actually a group, and we call this the factor group of $G$ by $N$, or the quotient group of $G$ by $N$, and we write $G/N$ to talk about this group of cosets.

Definition (Factor Group or Quotient Group of $G$ by $N$, or $G/N$)

Let $G$ be a group. Let $N$ be a normal subgroup of $G$. Then we define the factor group of $G$ by $N$, or the quotient group of $G$ by $N$, to be the set $G/N = \{Na\mid a\in G\}$, i.e the collection of right cosets of $N$ using the set product $(Na)(Nb)=N(ab)$ as the binary operation.

Problem 88 (The Quotient Group $G/N$ Is A Group)

Let $G$ be a group and let $N$ be a normal subgroup of $G$. Prove that the set $G/N$ is actually a group under the operation of coset products.

For more problems, see AllProblems