Wednesday, June 15, 2005

Math Post the Fifth: Cosets, Lagrange's Theorem, Generation

I'm sorry for the lateness of this; I've had a busy weekend/early week.

I asked two questions last time, and while I was planning to answer the second one first, I realized there was a reason I asked them in that order. Silly me. The question was about the cosets of the subgroup H=5Z in the group G=Z (Z is the group of integers under addition). To answer it, let's start by doing out a few simple examples. For these, I'm going to break down and write the group operation with a + rather than simply omitting it, since if I leave it out it'll look like integer multiplication, which is not what I mean. The easiest coset to consider is 0+H; this is pretty obviously H back again. Slightly (but only slightly) less obviously, there is the coset 5+H, which is also H back again, since the element 5 in is the subgroup H. In fact, any element of H will simply give back H again as the corresponding coset, because H is closed under multiplication and inversion.

What about elements not in H? Well, 1+H is a coset -- it contains -4, 1, 6, 11, and so on in both directions. By the same principle that any element of H gives H back H, any other element of 1+H gives back 1+H: 6+H=1+(5+H)=1+H. A little more thought shows that there are exactly five cosets of H, one for each of the numbers 0-4. These are the possible remainders upon dividing by five, which I'll touch on again later, but for now just think of them as elements.

As to the second question, the first part is obvious: of course cosets of H cover G, since for any element g in G the coset gH contains g (the identity is in H). Whether they overlap is harder, and will be my first major invocation of equations on this string of posts. Say that two cosets, gH and g'H, for elements g and g' in G, overlap; this means there are elements h and h' in H such that gh=g'h', so g'=ghh'^(-1). So g and g' differ on the right by elements of H, meaning that they give the same coset by the reasoning in the first paragraph.

This non-overlapping of cosets yields an interesting result. Say the group G is finite (has only finitely many elements, like permutations of a set, symmetries of a regular polygon, or is a 'clock arithmetic' type group). Then if H is a subgroup of G, the cosets of H cover G without overlapping and are all the same size (they all have the same number of elements as H). This means that the number of elements in H divides the number of elements of G, so, for instance, a group with twelve elements can only have subgroups of size 1, 2, 3, 4, and 6. This fact is called Lagrange's Theorem, and has a fairly giant list of obvious corollaries of decreasing size (the professor who taught me this quipped, "we'll eventually get to the empty corollary."), which eventually end in most of the facts underlying public-key cryptography.

For next time, I'll leave you with one definition and one question which should now be soluble. If S is a set of elements in a group G, the subgroup generated by S, written with angle brackets usually but because I can't remember the way to get escape characters in HTML written here as [S], is the subgroup you get by starting with S and adding all the elements you can make by multiplying and inverting until you can't get any more. As an example, the subgroup H from the example way back at the beginning is generated by the number 5 (or equally by -5), so I might also write it as [5]. With this definition, the following question should be easy: describe all groups of prime order (that is, with a prime number of elements). It sounds big, but in spite of this it's easy enough I can bear to give only one hint: pick an element g in G.

Next time: what that act of "describing" really was...

2 Comments:

Blogger Rousseau said...

Sorry, I'm unsure what you mean by "describe".

My only thought so far is that this prime-factorizes the order of the superset.

10:29 AM  
Blogger Dennis said...

So what I mean (details next time) is characterize all possible isomorphism classes of groups of prime order. For the moment you make take describe literally: say everything you can. How many generators? How many subgroups? Of what kinds? Abelian/nonabelian?

(hint the second: the right answer (without proof) is under two sentences long)

1:53 PM  

Post a Comment

<< Home