Good Math/Bad Math

Friday, April 28, 2006

Cyclic Groups

There's an interesting kind of group called a cyclic group. Cyclic groups are interesting buggers: they express the symmetry of rotation in 2 dimensions, and the symmetric properties of addition in integers. They even tie together the idea of an exponential power series with the basic structure of the integers.

So what is a cyclic group?

A cyclic group of size N (often written Z_N) is a set of N values with a "circular" relationship. The reason for the scare-quotes is that there is an infinite cyclic group, which doesn't close - it's the set of integers. If the cyclic group is finite, then you can see it as a circle of values. You can draw a cyclic group very easily: here's the cyclic group of size 5:

To really explain what a cyclic group is, we can formulate it in two ways: modulo arithmetic, and power series. They're quite different formulations at first glance, but they are entirely isomorphic, and the correspondance is quite easy to see.

Cyclic Groups as Modulo-Arithmetics

The first way is something called modulo arithmetic. Modulo arithmetic a kind of arithmetic that uses a finite number of positive integers. For each positive integer N, there is a modulo N arithmetic (sometimes called modN for short). In modN, N=0=identity; if you add two numbers in modN, and the result is greater than N-1, you wrap back around zero.

Since that sounds confusing, here are a few examples in mod5:

1+2=3
2+2=4
2+3=0 (2+3 = 5 in non-modulo; in mod5, it wraps back to 0)
3+3=1 (3+3 = 6 in non-modulo; in mod5, it's 3+2+1=0+1=1)
4+4=3 (4+4=8 in non-modulo; in mod5, it's 4+1+3=0+3=3)

Another way of thinking of modulo-N arithmetic is that after every addition, you do an integer divide by N, and take the remainder. The remainder is the result in modulo arithmetic.

And finally, the easiest way to think of modulo-N arithmetic: remember the idea of a number line from elementary school? Take the number line starting at zero. Cut it at N. Take what's left, and curl it around so that it forms a circle.

Just like you can do addition by stepping on the number line (3+4 is start on three, and take four steps forward), you can do addition by stepping around the modulo-N number circle: 3+4 is start on 3, and take four steps forward along the circle.

Cyclic Groups as Generated Power Series

The other way of viewing a cyclic groups is as a power series generated by a single value. For a number X, there is a cyclic group of size N whose values are X^0 (the identity value), X^1, X^2, X^3, ... , X^(N-1). (note: this was corrected based on comments: the last entry was originally X^N, which is a group of size N+1, not N.)

The group operator in this formulation is basically just multiplication; the identity is thus X^0. The one little catch is: if we're looking at a finite cyclic group, then the multiplication operation "rolls back" in a manner exactly like modulo arithmetic. Again, it will get clearer with some examples. For a cyclic group of size 5:

N^0 * N^4 = N^4
N^3 * N^1 = N^4
N^3 * N^3 = N^1 (N^3*N^3 = N^6, which "rolls over" to N^1.)
N^4 * N^3 = N^2 (N^3*N^4 = N^7 which rolls over to N^2.)

As you can see, if you look at the members in terms of exponents, then the multiplication operation behaves as modulo arithmetic on the exponents.

Cyclic Groups and Rotational Symmetry

If you look at my corrected explanation of group operations from the other day, you should be able to see how a cyclic group expresses rotational symmetries. For example, if you take a set of the vertices of a pentagon, and look at Z_5 as a group operation, then the values in Z5 correspond to the five possible symmetric rotations of the pentagon. For example, the member of Z_5 labeled as "1" in the diagram above is the permutation function:

{v1->v2, v2->v3, v3->v4, v4->v5, v5->v1}.

Concluding Note

Today's going to be my last post on group theory for a while. There's plenty more to say about it, but group theory isn't my specialty, and since the next couple of weeks are going to be very busy for me, both at work and at home, so I'm not going to have the time to write about something that requires so much background reading. So I'll be moving on to other things for a while after today, and I'll get back to more group theory at some point.

5 Comments:

  • One minor correction to the Power Series section: X^0, X^1...X^N is N+1 elements. You should have stopped at X^(N-1).

    By Anonymous Anonymous, at 10:23 PM  

  • Also note that this usage of the phrase power series, while descriptively correct, is not standard usage.

    By Anonymous Anonymous, at 6:54 PM  

  • anonymous:

    Thanks for the correction; off by one errors are the plague of computer scientists :-)

    ivan:

    Yeah, I know it's not the usual formal use of the term, but it's descriptive, and since I also defined what I meant, I thought it was reasonable to use it since it had the proper descriptive sense.

    By Blogger MarkCC, at 10:08 AM  

  • Wouldn't "power sequence" be both descriptive and precise?

    By Blogger ebohlman, at 8:28 PM  

  • Our clock system would be the most familiar version of modulo arithmetic (12 or 24), wouldn't it?

    By Anonymous Anonymous, at 11:04 AM  

Post a Comment

<< Home