Group Theory Problems: Proving Subgroups and Isomorphisms for Different Groups

[AKG]

Problem 1

\alpha ,\, \beta \in S_n,\ \alpha \beta = \beta \alpha and \alpha is an n-cycle. Prove that \beta is a power of \alpha. I know that either \beta = \epsilon, or \beta permutes all the elements, but I don't know how to prove that it must specifically be a power of \alpha.

Problem 2

Define R_m to be the group consisting of the set \{x \in \mathbb{N}\ :\ \mathop{\rm GCD}\nolimits (x,m) = 1,\ x < m\} together with multiplication modulo m as the group operation. Show that if \mathop{\rm GCD}\nolimits (m,n) = 1 then R_{mn} is isomorphic to R_m \times R_n.

Problem 3

Prove or disprove that the alternating group A_5 contains subgroup of order m for each m that divides |A_5| = 60. I've found:

1: {e}
2: {e, (12)(34)} = <(12)(34)>
3: {e, (123), (321)} = <(123)>
4: {e, (12)(34), (13)(24), (14)(23)}
5: {e, (12345), (13524), (14253), (15432)} = <(12345)>
6: {e, (123), (321), (12)(45), (13)(45), (23)(45)}
10: <(12345)> U {(13)(45), (14)(23), (15)(24), (25)(34), (12)(35)}

I found the subgroups of orders 4, 6, and 10 basically hoping to prove that they didn't exist, then after getting stuck, ending up finding that I could find subgroups of that order. However, this brute force type of approach will not work in finding subgroups of order 12, 15, 20, or 30. So is there any way to solve this problem that isn't overwhelmingly time-consuming?

Problem 4

Suppose p is prime, and R_p is as defined in problem 2, then show that it is cyclic.

Problem 5

Suppose G is a group with |G| = 4n+2. Show that there is a subgroup H < G such that |H| = 2n + 1. Use Cauchy's theorem, Cayley's theorem and the fact that any subgroup of S_n has either all of its elements or precisely half of its elements being even.

 

[CarlB]

A_4 has size 4!/2 = 12 and is clearly a subgroup of A_5. That leaves 15, 20 and 30. It wouldn't surprise me if these three were impossible.

Carl

 

[AKG]

Thanks Carl, 1 down, 3 to go. For problem 5, Cayley's theorem tells me that G is isomorphic to a subgroup of S_{4n+2}. Since 2 is a prime divisor of 4n+2, Cauchy's theorem tells me that G contains a subgroup of order 2, hence an element of order 2. The only permutations of order 2 are those which are products of disjoint transpositions. Suppose G were isomorphic to a subgroup of S_{4n+2} that contained an element of order 2 which was a product of an odd number of disjoint transpositions. By the extra fact, we know that precisely half the elements of this subgroup will be even, and half is 2n+1. Clearly, these elements would form a subgroup since an even permutation multiplied with an even permutation is even, the inverse of an even permutation is even, and the identity is even. So the subgroup of S_{4n+2} which is isomorphic to G has a subgroup of order 2n+1. It follows that G does as well.

It remains to show that the subgroup of S_{4n+2} which G is isomorphic to has an element of order 2 that is odd. I am thinking that I should use the fact that 2n+1 is odd, that is, that the order of G is 2 x an odd number. I've used the fact that the order of G is 2 x something already, but not the fact that it is something x an old number, I'm guessing that's significant.

 

[CarlB]

Okay, how about this. Any subgroup of A_5 of size 15 must have subgroups of size 3 and and also subgroups of size 5. But these subgroups are cyclic, and so must have very particular forms. Without loss of generality, suppose that the subgroup of size 5 is (12345). Can you classify all possible subgroups of size 3 and show that including any of them would produce a generated subgroup that is larger in size than 15?

For example, what is the size of the subgroup generated by { (123), (12345) }? If it's size is 15, then you have an example for 15. If it's larger, then maybe it's a clue on how to show impossibility.

Best of luck. I recall with great pleasure the mental challenges of (I presume) a graduate class in algebra.

My own interest at the moment is in applying Clifford algebra to elementary particles and fields.

Carl

 

[AKG]

That approach seems okay. There won't be too many posibilities for the 3 cycle since considering the case (123) includes the case (321) since that's just its inverse, and (12345) = (23451) = ... = (51234), so I'll try that. It's not a graduate class, it's like something between second and third year. It's an independent "research" project. It's basically like an award or scholarship (I get money) but instead of just getting money, I also learn something over the summer. I say "research" because I think it's normally for engineering or science students who would do research with a professor over the summer.

 

[mathwonk]

one nice way to visualize A5 is as the group of rotations of an icoashedron, or equivalebntly as the group of roitations of a dodecahedron. this let's you literally see all the elements and subgroups of orders 2,3,5. as fixed groups for the edges, vertices and faces.

also their conjugation relations are that conjugating an element fixing say the vertex a by a rotatio taking a to b takes you to the elements fixing b, etc...


the homomorphism of Sn to {-1,1} takes all even elements to 1 all odd elements to -1. so if you can embed in =Sn with exactly half the elem ents even then composing gives as kernel a subgerroup of order half the given order, i.e. 2n+1.

if they are all even you have an embedding into A(4n+2), what then?

 

[mathwonk]

and do you know that A5 is simple? that would imply no subgroups of order 15, 20, or 30.

i.e. if G has a subgroup H of index d, then the action of G on the cosets of H gives a homomorphism of G to a transitive subgroup of S(d). But A(5) has no non constant homomorphisms into anything smaller, hence no non trivial homomorphisms into either S(4), S(3), or S(2).

i.e. no subgroups of index 2,3, or 4.

there is an easy proof that the icosahedral group is simple in my book of math 843 notes at the very bottom of my webpage http://www.math.uga.edu/~roy/.

and a hint for a problem that every simple group of order 60 is isomorphic to A(5).

 

[AKG]

if they are all even you have an embedding into A(4n+2), what then?

This is what I'm not sure of.

As for problem 3, I don't understand the hints you've given, so it wouldn't make sense for me to use them to solve the problem. However, I'm not too concerned with that problem. Problems 1, 2, and 4 are my main concern. Problem 5 would be nice to get too. I've already been able to prove it if G is isomorphic to a subgroup of S(4n+2) that's not contained entirely in A(4n+2), but I don't know what to do if it is contained in A(4n+2).

Anyways, problem 1 should be done with only the most basic facts about permutation groups and groups in general. No reference to Lagrange, Cauchy, homomorphisms, isomorphisms, etc. Problems 2 and 4 can refer to Lagrange, isomorphisms, and basic facts about group products. But again, no reference to homomorphism, conjugation, etc.

 

[matt grime]

1 I thought was goign to be hard but is actually a straight forward consequence of the orbit stabilizer theorem, which is about the only thing it could be I suppose. As this is for extra credit and moeny, I think that's sufficiently big a hint.

2 Define a map from R{mn} to R_{n} in the only possible way and think a little.


4 is a classical, standard, result and easily found in textbooks and so on.

How can something be allowd to refer to isomorphims but not homomorphisms? I mean, an iso is a homomorphism.

Do we get a share of the prize?

 

[AKG]

This isn't for money (well, whether I do these problems or not doesn't affect whether I get the money), and since I haven't learned the orbit-stabilizer theorem yet, I won't be able to use it. You can learn things about isomorphisms without learning about homomorphisms. If there are special theorems for homomorphism, I don't think I should be using them.

 

[mathwonk]

if you don't want to use homomorphisms i don't know what to say. that is the most basic idea in group theory, after the definition of group, and the concept of subgroup and coset.

 

[AKG]

All of these questions come before the chapter on homomorphisms. The chapter on isomorphisms comes well before the chapter on homomorphisms. I think this is because the first theorem proved in the chapter on homomorphisms says that the kernel of a homomorphism is a normal subgroup and makes reference to some isomorphism as well, and the concepts of normal subgroups and conjugacy are introduced well after isomorphisms are. Do you mean to say that someone who didn't know what a homomorphism was couldn't solve these problems?

 

[matt grime]

Why on Earth can you not use other theorems? You are able to learn these things, there is nothing precluding you from doing this if it makes your life easier. I presume these must be exercises at the end of a chapter then. What in the chapter can help you? (We aren't psychic?) Personally I would teach orbit stabilizer as the most fundamental thing in an introduction to groups.

Perhaps for 1. you could tell us what "basic facts" about permutation groups you know - ie do you know what the conjugacy classes and centralizers are?

 

[matt grime]

Oh, and you can write down an explicit bijection between R_{mn} and R_{m}xR_{n}

How many maps can there be? I can only think of one way to send x to an element (u,v).

 

[AKG]

Yes, these are problems at the end of various chapters. I tried to give a general idea of what I "know" for each problem, I didn't want to get too specific (listing all the theorems in the preceeding chapters) unless someone asked, like you have, so I'll be more specific.

For 1, although I know conjugacy classes and am just about to read something on centralizers, the only stuff preceeding question 1 in the text is:

Rotational symmetries of the tetrahedron (kind of an informal introduction to groups)
Axioms (formal introduction)
Numbers (examples of groups made up of numbers)
Dihedral Groups
Subgroups and Generators
- (\forall x, y \in H,\ xy^{-1} \in H)\Rightarrow(H&lt;G) provided H\subseteq G is nonempty
- (H&lt;G \mbox{ and } J &lt; G) \Rightarrow H\cap J &lt; G
- Every subgroup of \mathbb{Z} is cyclic
- Every subgroup of a cyclic groups is cyclic
Permutations
- The transpositions generate the symmetric group
- some other theorems about generators of the symmetric group
- The alternating group has order n!/2
- For n > 2, the 3-cycles generate the alternating group

Oh, and you can write down an explicit bijection between R_{mn} and R_{m}xR_{n}

How many maps can there be? I can only think of one way to send x to an element (u,v).

First of all, how do I know that \phi (m)\phi (n) = \phi (mn)? Also, there are (\phi (mn))! bijections, I would need to find one that is homomorphic, so how can I be certain that there is one?

note: H < G means H is a subgroup of G
note: \phi (m) = |R_m|, i.e. \phi is Euler's phi function

 

[CarlB]

Problem 1

\alpha ,\, \beta \in S_n,\ \alpha \beta = \beta \alpha and \alpha is an n-cycle. Prove that \beta is a power of \alpha. I know that either \beta = \epsilon, or \beta permutes all the elements, but I don't know how to prove that it must specifically be a power of \alpha.

If you look through all those various powers of alpha, surely you can find one that undoes one of the permutations of beta. That is, if, for example, beta takes 1 to 2, then there is a power of alpha that takes 2 to 1. That would mean that if you choose k correctly, you'll have either that \alpha^k\beta is the identity, or it doesn't permute all the elements.

Carl

 

[AKG]

Thanks carl, that appears to work. Suppose \alpha ^k \beta fixes some element x \in \{1, 2, \dots , n\}. Since \alpha \beta = \beta \alpha, then \alpha (\alpha ^k \beta) = (\alpha ^k \beta )\alpha. Therefore:

\alpha (\alpha ^k \beta)(x) = (\alpha ^k \beta )\alpha(x)

\alpha (x) = (\alpha ^k \beta )\alpha(x)

So \alpha ^k \beta fixes \alpha (x). Repeating this process n times shows that \alpha ^k\beta fixes all of {1, 2, ..., n} since \alpha is an n-cycle, so

\alpha ^k \beta = e

\beta = \alpha ^{n - k}

as required. Thanks!

 

[matt grime]

YFirst of all, how do I know that \phi (m)\phi (n) = \phi (mn)?

Because it is obvious (in the sense, of intuitively true), reasonably easy to prove and appears in almost every introduction to number theory. If you know what phi is, then surely you know phi is a multiplicative function.

Also, there are (\phi (mn))! bijections

Yes, but how many of them can you write out explicitly? If this is a map for all coprime m and n then it's going to have to be *special*, ie easy to write out. Now, I can only think of one *specia l* way of sending some equivalence class mod (mn) to some pair of equivalence classes mod(m) and mod(n)

Hint: true or false, if [z] is some equivalence class in mod (mn), then for any choice of x and y in [z] x=y mod (m)? So how can i send equivalence classes in mod(mn) to equivalence classes in mod (m)? and mod (n)? And now what about getting a pair of equivalence classes (,[v]) in mod(m)xmod(n)? Does this send invertible elements to invertible elements? Is it a bijection?

 

[AKG]

Because it is obvious (in the sense, of intuitively true), reasonably easy to prove and appears in almost every introduction to number theory. If you know what phi is, then surely you know phi is a multiplicative function.

Since this is a group theory textbook, they don't say much about the phi function except to define it. They do give a couple theorems (Fermat's little theorem, and one that I think is called Euler's theorem) involving phi, but those don't appear to help. Also, I don't know what you mean by "phi is a multiplicative function". phi(4) = 2, phi(6) = 2, but phi (4x6) = 8 != 2x2. phi(3) = 2, phi(8) = 4, and phi(3x8) = 8 = 2x4. So phi (as the problem suggests) is only multiplicative when gcd(m,n) = 1.

Yes, but how many of them can you write out explicitly?

What do you mean, "write out explicitly"? If I list all the elements of R(3) x R(8), and all the elements of R(24), I can "explicitly" write out any of the 8! bijections. I think you might mean that there is one special isomorphism?

Hint: true or false, if [z] is some equivalence class in mod (mn), then for any choice of x and y in [z] x=y mod (m)?

True, assuming you mean that x,y are in the same equivalence class in (mod x) iff x = y (mod x).

So how can i send equivalence classes in mod(mn) to equivalence classes in mod (m)? and mod (n)?

I could send x in R(mn) to (x (mod m), x (mod n)). Suppose (y (mod m), y (mod n)) = (x (mod m), x (mod n)), then:

y = x + mp, y = x + nq
mp = nq

Let y < x without loss of generality. We know 0 < p < n, 0 < q < m, otherwise y = x + mp > x + mn > mn, which is impossible. But since m and n are co-prime, they share no prime divisors, but if mp = nq, then mp and nq must share all prime divisors, so p would have to bring all of the divisors of n to the left side unless it's zero, i.e. p would have to be a positive multiple of n unless it's zero, but there no positive multiples of n in {0, 1, ..., n-1} so p is 0, and y = x. So this mapping is 1-1. It preserves multiplication because, if we let \psi be our mapping:

\psi (xy) = (xy (\mathop{\rm mod} m), xy (\mathop{\rm mod} n))

\psi (x)\psi(y) = (x (\mathop{\rm mod} m), x (\mathop{\rm mod} n))(y (\mathop{\rm mod} m), y (\mathop{\rm mod} n)) = ([x (\mathop{\rm mod} m)][y (\mathop{\rm mod} m)] (\mathop{\rm mod} m), [x (\mathop{\rm mod} n)][y (\mathop{\rm mod} n)] (\mathop{\rm mod} n))

It remains to show that:

[x (\mathop{\rm mod} p)][y (\mathop{\rm mod} p)] \equiv xy (\mathop{\rm mod} p)

but

[x (\mathop{\rm mod} p)][y (\mathop{\rm mod} p)] = (x - p\left\lfloor{x/p}\right\rfloor )(y - p\left\lfloor{y/p}\right\rfloor ) = xy - p(\left\lfloor{x/p}\right\rfloor y - \left\lfloor{y/p}\right\rfloor x + p\left\lfloor{x/p}\right\rfloor \left\lfloor{y/p}\right\rfloor ) \equiv xy (\mathop{\rm mod} p)

as required. All that's left is to show that the mapping is onto.

 

[matt grime]

Multiplicative in number theory means exactly the f(ab)=f(a)f(b) when a and b are coprime.

Ok, you can write out the bijections when m=3,n=8, but can you do it *in general*? No, of course not: it's ahrd to write out any bijection explicitly except for the *special* one that you come up with.

The map is injective between sets of the same size so surjective comes for free. You should prove that multiplicative property of phi, or work out the inverse function by, say, the chinese remainder theorem.

 

[CarlB]

So, which problems are still giving you fits?

Carl

 

[AKG]

I've more or less given up on finding the subsets of A5 (or proving they don't exist). Thanks to you, I got the question involving powers of n-cycles, and thanks to matt grime, I got the problem on showing R(mn) is isomorphic to R(m) x R(n). The Chinese Remainder Theorem was exactly what I needed. So from this list, the only one's still bugging me are 4th and 5th ones. The fourth one says to prove that R(p) is cyclic if p is prime. I guess I finished "half" of problem 5, but I need to prove that if G is a subset of A(4n+2) and G has order 4n+2, then it contains a subgroup of order 2n+1, knowing that it contains a subgroup of order 2.

 

[CarlB]

Hi AKG;

Maybe another hint is necessary. Let me be more explicit. A subgroup G of size 15 must have subgroups of size 3 and 5. (I can give hints on this, if needed, but I bet you can show this.)

The only group of size 5 is a "5-cycle", and the only group of size 3 is a "3-cycle". (Hints available, but I doubt they are needed.) Without loss of generality, we can assume that the 5-cycle is (12345), and the 3-cycle is (12x), where x is 3,4 or 5. (Just a matter of replacing (12345) with (12345)^n.) There are therefore only three possible subgroups, those generated by:

(12345) & (123),
(12345) & (124),
(12345) & (125).

If none of these are of size 15, then no such subgroup exists.

Carl

 

[AKG]

Well there would still be the issue of proving that there's no subgroup of order 20, and proving that there's no subgroup of order 30 without using the fact that it is simple.

 

[CarlB]

Did you quote problem 4 exactly? My read of "Prove or disprove that the alternating group A5 contains subgroup of order m for each m that divides |A5|." is that by finding the example of no subgroup of size 15, you've disproved the proposition. If the author had wanted you to verify the status of all the possible sized subgroups, he could have asked for it.

But it does make the problem more interesting. I'll look at it again, it's good exercise.

By the way, about problem 4, did you know that if p is prime, and is not 2 or 5, then there always exists an integer q with the fraction p/q having a repeating length equal to p-1?

Honestly, how to prove it with elementary methods eludes me at the moment.

[edit] The cool thing about knowing that a subgroup of size 5 exists in a subgroup of A_5 is that you can use the group elements (54321) and (12345) to easily translate an additional element around. For example, translating (12)(34) around gives:

(54321)^0 [(12)(34)] (12345)^0 = (12)(34)
(54321)^1 [(12)(34)] (12345)^1 = (51)(23)
(54321)^2 [(12)(34)] (12345)^2 = (45)(12)
(54321)^3 [(12)(34)] (12345)^3 = (34)(51)
(54321)^4 [(12)(34)] (12345)^4 = (23)(45)

The reason this is handy is because it reduces the effort needed to show that (12345), along with some other group elements, generate the whole group A5 rather than some desired subgroup. With this technique, I believe that it's fairly easy to show that no subgroups exist of size 20 or 30.

Carl

 

[AKG]

Did you quote problem 4 exactly? My read of "Prove or disprove that the alternating group A5 contains subgroup of order m for each m that divides |A5|." is that by finding the example of no subgroup of size 15, you've disproved the proposition.

You're right, I haven't looked at the problem in a while so I forgot that that's what it was about. So it would be sufficient to prove that no subgroup of order 15 exists. If I decide to try it, I don't think it will be too hard given your suggestions, but I'll let you know if I try it and have problems.

By the way, about problem 4, did you know that if p is prime, and is not 2 or 5, then there always exists an integer q with the fraction p/q having a repeating length equal to p-1?

No, I had no idea!

 

[matt grime]

Ok, here is the proof (outline) for the fact that R_p is cyclic. It is quite long but each step is quite basic. Let me know if you want any extra explanations of any parts. I'm not sure how you'd do it with the knowledge you've said is in the book, though.

1. The only possible orders of elements are the divisors of p-1.

2. If t divides p-1 there are either 0 elements of order t or exactly \phi(t) of them (Euler's totient). This follows from general number theory facts which we give now


2.1 if f(x) is a poly in Z_p (ie residues mod p not just the invertble ones) and deg f is n, then f has n distinct roots iff f divides x^p-x (all mod p of course), in particular if t divides p-1 then x^t-1 divides x^p-x

2.2 If a has order t the only roots of x^t=1 mod p are the powers of a (there are t of these all distinct so tey m ust be all the roots by 2.1), and those that have order t are the powers a^n where (n,t)=1, ie the ones with exponent coprime to t, and there are phi(t) of them.

3. If we let O(t) denote the number elements of order t, then it must follow that the sum over t dividing p-1 of O(t)=p-1

4. We know that the sum over t dividing p-1 of \phi(t)=p-1

5. combining 2.2, 3, and 4 it must follow that actually O(t)=\phi(t), and in particular that \phi(p-1)=/=0 and that there is a cyclic generator (in fact \phi(t) of them