What Comes Next: 1, 2, 4, 8, 16, … hint it’s not 32

A Kick in the Discovery

, ,

Cosets are Cool Sets (Even I Know This is a Lame Title!)

Published by

Valt

on

*Note that it’s assumed the reader is familiar with groups and subgroups. And note to subscribers, the way that the math (or maths for my British friends) is formatted on phones in emails is downright awful! I recommend you read this online. *

Have you ever seen a movie where the ending was so amazing that you left the theater feeling excited, energetic, and like you could do anything? For me, those movies are Avengers Endgame and Interstellar. Now I’m not saying that this blog will be like that, but…. it will be! I know that’s a bold statement! (pun intended)

Let me ask you some questions:

When can we guarantee that a group is cyclic? Can we tell when a subset cannot be a subgroup by only how large it is? Can we predict the possible orders that elements from G can have?

We will answer these questions with little effort. Little in the sense that we will prove one thing that leads to the rest. And the way we do so will make the answers soooo transparently obvious that you will wonder why they seem difficult now!

Wait there’s more! Just like for any ‘good’ infomercial…

We will (in another article) develop tools to learn when two groups are secretly the same group G. At that point, we will also develop a way to construct groups that are identical in structure to G. And it all starts with this topic!

Everything above uses this one thing called a COSET!

What’s A Coset?

We will not motivate this definition at all. Mostly, because I am not sure why someone would even think to come up with this other than curiosity at its finest. Well… I have one idea… it comes from number theory…

Definition: (Left/Right Cosets) Let G be a group and H be a subgroup of G. Fix an element g\in G. We define the left coset of H with representative g to be the set:

gH := \{ gh\;:\;h\in H\}.

Likewise, the right coset of H with representative g is the set,

Hg:= \{ hg\;:\;h\in H\}.

In plain English, find some subgroup H= \{ e,\;h_1,\;h_2\;\cdots,\;h_n \} of some group G. Then, fix some g\in G. Lastly, multiply all the elements of H with g on the left (or right) to get gH (or Hg).

Hg= \{ eg,\;h_1g,\;h_2g\;\cdots,\;h_ng \} = \{ g,\;h_1g,\;h_2g,\;\cdots,h_ng\}

For a special case, since e\in G we have He:= \{ he\;:\;h\in H\} = \{h :h\in H\} = H. So any subgroup is a right (and left) coset of that subgroup!

Now I hear you asking: “Why on Earth would we care about a coset?” I thought the same thing but trust me the payoff is awesome!

Note: A coset is not necessarily a group/subgroup. A coset is generally a set, just a set. If cosets were able to sing, they’d sing, “I’m just a set. Yes, I’m only a set...” (for those of you who remember School House Rock you get the joke).

Little Lemma

Before we begin it would be useful to know when two cosets are the same. Meaning, for a,b\in G when is Ha = Hb ? This definitely happens when a=b, but can it happen when a\neq b?

Yes, in general Ha = Hb when a\in Hb .

Little Lemma: If a\in Hb , then Ha=Hb .

Proof: Let a\in Hb. Do you recall how to prove when two sets are the same? We will show (i) Ha\subseteq Hb and (ii) Hb\subseteq Ha . This can only happen if Ha=Hb .1

(i) Let’s consider some x\in Ha and show that this implies x\in Hb too.2 Since x\in Ha , by the definition of a coset, x is of the form:

x = h_{xa}a ,

Where h_{xa} \in H. Recall, a\in Hb so a has a similar form,

a = h_ab ,

where h_a\in H . We can combine these two expressions and deduce:

x = h_{xa}a =h_{xa}(h_a b) =\underbrace{(h_{xa} h_a)}_{\in H} b \in Hb.

Since x has the form of: (element from H)b, we concluded that x \in Hb. Thus, Ha\subseteq Hb . On to step two.

(ii) Consider another y \in Hb . Then, y=h_{yb}b where h_{yb} \in H . We already know that a = h_ab , which implies

h_a^{-1}(a) = h_a^{-1}(h_ab) = ( h_a^{-1}h_a)b =eb = b

Cleanly written: b = h_a^{-1}a . Thus, we conclude,

y=h_{yb}b = h_{yb}(h_a^{-1}a) = \underbrace{(h_{yb}h_a^{-1})}_{\in H}a \in Ha.

Since y has the form of: (element from H)a, we concluded that y \in Ha. Therefore, Hb\subseteq Ha .

Since (i) Ha\subseteq Hb and (ii) Hb\subseteq Ha we conclude Ha=Hb

\square

We’re done! We will use this tool a lot!

Positively Partitioning

We claim that cosets partition all the elements of G. This means that every element in G is in one and only one coset. We can picture this by blocking off sections of a group G. Each element falls into one of these coset sections:

Proof: Since we need every element in G to be in one and only one coset, we have to show two things: (1) two cosets Ha and Hb are either equal or disjoint and (2) every element falls into some coset. To this end, let Ha and Hb by two cosets of H. If they are disjoint, then we’re done! So, we will assume they are not disjoint and show they are equal sets.

Since Ha and Hb aren’t disjoint there is some x\in Ha and x\in Hb . Then, we know by our Little Lemma that Ha = Hx and Hb =Hx. In other words, Ha = Hx = Hb .

Almost there, we just need to explain why every element in G is in a coset. Well, isn’t x\in G in the coset Hx ? Yup! We can see this since e\in H the element ex = x \in Hx.

Therefore, cosets partition the set G.

\square

Cool Correspondence between Ha and H.

A fact about cosets, is that there are as many elements in any coset Ha as in the subgroup H. This may seem obvious since the elements of Ha are the elements of H multiplied on the right by a. Indeed, this is the way to think about it.

There is a more mathy way to state this correspondence:

There is a one-to-one correspondence between elements of H and the elements of Ha.

Proof: Recall that to show a one-to-one correspondence between sets we must find a bijection.3 The first one you might think of, the one that maps x\mapsto hx , is one that works.

Let f: H \rightarrow Ha be defined by f(h) = ha. We now show that f is bijective.

Injective: Let f(h_1) = f(h_2) then h_1 a = h_2 a. By multiplying on the right by a^{-1} we conclude h_1 = h_2 . Thus, f is injective!

Surjective: This one’s not so bad. Let ha \in Ha, then h\in H is such that f(h) = ha . Therefore f is surjective.

Since f is both injective and surjective, it’s bijective.

In conclusion, there is a one-to-one corresponded between elements of H to Ha . Or, |H| = |Ha| .

\square

Short Recap

What have we learned so far?

Well first off, it hasn’t been that much work to show that cosets partition G and there is a one-to-one correspondence between elements of H to Ha . So, each coset partitions the same number of elements since each coset is the same size. This means the image showing cosets of G should have been neater. Sort of like this,

It might be really surprising but we are basically done.

Legendary Legrange

Lagrange’s Theorem: Let G be a finite group and let H be any subgroup of G. Then, the order of H divides the order of G. Or, the order of G is a multiple of the order of H.

Wowww…. how cool is that?!? Would you have thought that the number of elements in H must divide the number of element in G????

Proof: We’ve already proved it, since the collection of cosets partition G it must be that the order of G is the sum of each of the orders of the cosets,

|G| = |Ha_1| + |Ha_2| + \cdots |Ha_n| .

Where there are n cosets of H. And n is finite since |G| is finite. But, all the cosets have the same order (size) as H,

|G| = |Ha_1| + |Ha_2| + \cdots |Ha_n| = |H| + |H| + \cdots |H| = n|H|.

So that |G| = n|H| where n is the number of cosets of H.

\square

Just like that, we’re done! The reason why this theorem is so cool is because of the quick corollaries it gives.

When is a Group Guaranteed to be Cyclic?

If G has prime order p , then every nonidentity element is a generator of G. Or, G is cyclic!

Proof: Let the order of G be a prime p and a\in G be a nonidentity element of G. Denote the order of a by |a| = k. Recall \langle a\rangle = \{e, a, a^2, \cdots, a^{k-1} \} is always a subgroup and |\langle a\rangle|=|a|=k (If you are unfamiliar with these facts, I challenge you to prove them!). By Lagrange’s theorem k divides p . But, then k=1 or k=p since p is prime.

Wait, if k=1 then a=e, and we didn’t want a to be the identity!

Therefore, |a| = k , and G = \langle a\rangle = \{e, a, a^2, \cdots, a^{k-1} \} since they both have k elements!

Is there a Subgroup?

Let’s say |G| = 10. Can there be a subgroup H of order 4? NO! Since 4\nmid 10. You can do this with any |G|. How awesome!

Well, what if |G|=p is a prime number? Then, the only numbers that divide p are 1 and p. Thus |H| = 1 or |H|=p=|G|.

This means that the only subgroups of G are \{e\} and G=H itself when G has prime order.

Fermat’s Little Theorem

Fermat’s Little Theorem is a corollary too! For those in the know:

If p is a prime then,

a^{p-1} \equiv 1 \pmod{p}.

When a \in \{ 1,2,3,\cdots, p-1\}.

To see this, consider the set \langle a\rangle = \{e, a, a^2, \cdots, a^{k-1} \} again. It is still a subgroup of G= \{ 1,2,\cdots, p-1\} with multiplication. By Lagrange’s theorem the order of \langle a\rangle must divide the order of G which is |G|=p-1. Denote the order of a\in G by |\langle a\rangle| =|a| =k. Thus k must divides p-1 and therefore p-1 = kt.

Finally,

a^{p-1} \equiv a^{kt} \equiv (a^k)^t \equiv 1^t \equiv 1 \pmod{p}.

Boom. Mike drop.

Closing Remarks

This theorem is so amazing because it’s both so ‘simple’ and has a ‘how would anyone think of it?’ kind of feeling. I hope you had half as much fun as I did when I learned it for the first time. We’ve barely scratched the surface of it.

Oh, just in case you want some of the ‘kick in discovery’ fun too. Try to prove the following:

  1. If H and K are subgroups of G with |H| and |K| relatively prime (meaning \gcd{(|H|,|K|)} = 1), then H\cap K = \{e\} .
  2. Euler’s Little Theorem:4 Denote the number of elements relatively prime to n by \phi(n) (this is called Euler’s Totient function). Then for all a such that \gcd{(a,n)} = 1, we have a^{\phi(n)} \equiv 1 \pmod{n}.

Leave your proofs in the comments!

Footnotes:

  1. This is analogous to numbers. If x\leq y and y\leq x, then x=y . ↩︎
  2. For two set A and B, by showing a\in A implies a\in B, it must be that A\subseteq B. Can you see why? ↩︎
  3. A bijection is a fancy term that means a function that is an injection and surjection. And an injection is a fancy way to say that the element f(x) is unique to x. Or, no two elements x_1 and x_2 have the same f(x_1) or f(x_2) . This is equivalent to saying:
    INJECTION Criteria: if f(x_1)=f(x_2) then x_1=x_2 .
    And a surjection means that every element in Ha is equal to some f(h).
    SURJECTION Criteria: for any ha \in Ha there is some h\in H such that f(h)=ha . ↩︎
  4. This is not the standard name of this theorem! ↩︎

One response to “Cosets are Cool Sets (Even I Know This is a Lame Title!)”

  1. Newbie Number Theory (Part 6): Fermat’s Fantastic Little Theorem – A Kick in the Discovery Avatar
    Newbie Number Theory (Part 6): Fermat’s Fantastic Little Theorem – A Kick in the Discovery

    […] little theorem. If you’ve read all my articles, then you would have seen a proof using Lagrange’s theorem in the setting of group theory. This time however, we show a proof that uses only tools that we […]

    Like

    Reply

Leave a reply to Newbie Number Theory (Part 6): Fermat’s Fantastic Little Theorem – A Kick in the Discovery Cancel reply