MaBloWriMo 30: Cyclic subgroups

Today, to wrap things up, we will use Lagrange’s Theorem to prove that if g is an element of the group G, the order of g evenly divides the order of G.

So we have a group G and an element g. In order to apply Lagrange’s Theorem we need a subgroup. Where are we going to get one of those? We will have to make one using g.

Suppose |g| = n, that is, n is the smallest natural number such that g^n = e. Then consider the set

\{ e, g^1, g^2, g^3, \dots, g^{n-1} \}

We will denote this set by \langle g \rangle. Clearly \langle g \rangle is a subset of G. But I claim it is actually a subgroup!

To prove this, let’s first introduce the notation g^0 = e. This fits nicely: for example, notice that for positive i and j, we have g^i g^j = g^{i+j}; this property continues to hold even when i or j are 0 if we define g^0 = e. (As an aside, notice this also fits nicely with the notation g^{-1} for the inverse of g—and we can extend it to g^{-i} = (g^{-1})^i = (g^i)^{-1}.) With this notation, our set \langle g \rangle is just \{ g^i \mid 0 \leq i < n \}. Now, let’s show that \langle g \rangle is a subgroup of G:

  • It is obviously nonempty.
  • It is closed under the group operation. Generally speaking, g^i  g^j = g^{i+j}. If i + j < n then all is well. On the other hand, if i + j ends up greater than n, we can always subtract n until we are left with something less than n, since g^n = e. For example, if n = 8, then g^5 g^6 = g^{11} = g^8 g^3 = e g^3 =  g^3. In general, we can say that g^i g^j = g^{(i+j) \bmod n}. You might notice that this is very much like the group \mathbb{Z}_8 we have been using as an example—in fact, when |g|  = 8 the group \langle g \rangle is isomorphic to \mathbb{Z}_8 (that is, in some sense they are really “the same” group); more generally, if |g| = n then \langle g \rangle is isommorphic to \mathbb{Z}_n, since powers of g are added \pmod n.
  • It has inverses: the inverse of g^i is g^{n-i}, since g^i  g^{n-i} = g^n = e. (This makes sense even when i = 0.)

This subgroup \langle g \rangle is called the cyclic subgroup generated by g. In any group, we can generate a subgroup from each element in this way (though the same cyclic subgroup may be generated by multiple distinct elements). For example, in the group \mathbb{Z}_8, the element 0 generates the trivial one-element subgroup; 4 generates the subgroup \{0,4\}; 2 and 6 both generate the subgroup \{0,2,4,6\}; and 1, 3, 5, and 7 all generate the entire group \mathbb{Z}_8, as you can check.

One more important thing to note is that every element of \langle g \rangle = \{g^0, \dots, g^{n-1}\} is distinct: remember, if g^i = g^j then e = g^{j-i}—but n is the smallest power of g that is equal to the identity. So this group really does have n distinct elements.

Now we have a subgroup of G, and Lagrange’s Theorem tells us that its order must be a divisor of the size of G. But the order of \langle g \rangle is the same as the order of g, that is, |\langle g \rangle| = |g|. So the order of any element must divide the order of the whole group.


And that concludes MaBloWriMo! This month of posting every day has been a lot of fun—I’m very glad I took up the challenge! I have these grand visions of stuff I want to write about, but often get bogged down writing long, monolithic posts, or sometimes I am just intimidated by the thought of it and never even start. This month, it was freeing to realize that the world would not end if I just post things in smaller chunks, perhaps without quite so much advance planning or editing. Posting frequently also meant I could maintain a lot more momentum—writing the individual posts went pretty quickly, since everything was still fresh in my head. Paradoxically, it seems that upping the posting frequency actually made things easier.

So I certainly can’t keep writing a post per day. But going forward I have decided to commit to two posts per week—I think that will be manageable while still taking advantage of the momentum generated by more frequent posting. I’m excited—I’ve got a bunch of ideas for things I want to write about, some new, and some that have been on the list for years. A small sampling: I want to explain the million-dollar P vs NP problem; write about the proof of the four-color theorem; finish my long-languishing series of posts on a certain combinatorial proof; and write some addenda to my series on hyperbinary numbers. I hope you enjoy—and please do continue to send ideas of things you might like me to write about!

Advertisements

About Brent

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in algebra, group theory, proof and tagged , , , , , . Bookmark the permalink.

6 Responses to MaBloWriMo 30: Cyclic subgroups

  1. teradil says:

    I really enjoyed following you this month. Thank you!

  2. fegleynick says:

    Following this series has made a very stressful month a little bit more enjoyable. Thank you.

    I’d love to see a continuation of the What I Do series.

    • Brent says:

      You’re very welcome! I’m glad I could bring you some enjoyment.

      Ah, yes, the What I Do series. That one is a bit more intimidating since it will require some deeper reflection to figure out what exactly I want to say. But I’ll try.

  3. janhrcek says:

    I’ve enjoyed this series of posts too. Not least because I’m reading a book on abstract algebra at the moment. I like your lighthearted, yet sufficiently rigorous presentation style 🙂 Thank you

Comments are closed.