Vito Prosciutto: Teaching community college math on the road to a PhD.

Wednesday, September 10, 2003

My little mathematical breakthrough 

Nothing major, nothing new, but at the beginning of the semester I set out a challenge for myself to find a group with infinite order, but with all of its elements having finite order.

For readers who may not have studied abstract algebra, let me back up and explain what these terms mean.

First, a group consists of a set and a binary operation (for example, the set of integers and the operation +) with the following requirements:

  1. There exists an identity (we'll call it e) such that e+a=a+e=a for all a in the set (note that I'm using + as my operation here).
  2. The associative law applies.
  3. For each a in the set there exists an element a-1 such that a+a-1=a-1+a=e
For integers and addition, the identity is 0 and we get the associative law axiomatically and the inverse will be the negative of a number (so, for example, 5-1=-5).

Note that we do not require a commutative law, and there are plenty of groups which meet the above requirements but are not commutative (one of the most notable being the set of invertible 2x2 matrices with the operation being binary multiplication).

When we talk about the order of a group, it's the number of elements in the group. The order of the group defined by integers and addition is infinite. On the other hand, if we choose the set of complex numbers {1, -1, i, -i} and the operation multiplication, the order of this group will be 4.

When we talk about the order of an element we mean the smallest positive integer k such that ak=e. The order of the identity is always 1, and with addition and integers all non-0 integers have infinite order (note that in this instance when we talk about ak, we really mean ka.

For our second example, the order of -1 will be 2 ((-1)2=1), the order of i will be 4 (i4=1), and the order of -i will also be 4.

One of the easiest ways to verify that you have a group is to construct the multiplication table and if you can have each element of the set appear exactly once in each row and column, then you have a group. I played around with some ideas using the set of whole numbers for a while trying to make a2=e for all elements and this morning I finally hit upon an arrangement which worked. Looking at patterns I realized that my binary operation was a bitwise binary exclusive or. For non-CS types reading this, the operation works by expressing the two non-negative integers in binary. In each bit position, the result will be 1 if only one of the two integers has that bit position on, 0 otherwise. So, for example, 5$3 will have the bits 101 and 011 and will result in 110 or 6 as its result. For any number a 0$a=a and a$a=0.

In fact, we can extend this to an infinite number of groups by taking the breakdown of an integer in base n and having a$b being the sum of each digit position being taken mod n. This is actually the additive group of polynomials Z/nZ[x] but without the upper limit on the power of polynomials (although it seems to me that the upper limit of the exponents should be n-1. In this instance, the order of each element will be no greater than n.

After coming up with this, I also realized that if we take the set of complex numbers with the property that xk=1 for some integer k, we also have a finite order for every element in the group, although here it's not bounded.

I'm afraid this might not be as clear as I'd like it to be, but it should be possible for someone with some basic group theory to follow this argument at least in outline.

This page is powered by Blogger. Isn't yours? Site Meter Listed on Blogwise