How to find all elements of S4 that satisfy the equation x^4=e?


by AdrianZ
Tags: elements, equation, satisfy
I like Serena
I like Serena is offline
#19
Nov23-11, 04:44 PM
HW Helper
I like Serena's Avatar
P: 6,189
Yep!
I like Serena
I like Serena is offline
#20
Nov23-11, 04:46 PM
HW Helper
I like Serena's Avatar
P: 6,189
So do you think you can deduce the number of 3-cycles now?
Deveno
Deveno is offline
#21
Nov23-11, 04:49 PM
Sci Advisor
P: 906
this is how i count n-cycles in Sn (this works for any n, but i will use n = 4):

since any 4-cycle in S4 involves 1, we may as well start with it:

(1.....

i have 3 choices for my next element (the image of 1):

(1 2.....
(1 3.....
(1 4.....

after i make my next choice, i'll have them all:

(1 2 3 4)
(1 2 4 3)
(1 3 2 4)
(1 2 4 2)
(1 4 3 2)
(1 4 2 3)

that makes 6.

in general, in Sn, we'll get (n-1)(n-2)....(2) = (n-1)! possible distinct n-cycles.
AdrianZ
AdrianZ is offline
#22
Nov23-11, 04:51 PM
P: 320
Quote Quote by I like Serena View Post
So do you think you can deduce the number of 3-cycles now?
Yes. Actually I was thinking about generalizing this idea to other cases as well.
For 3-cycles, each permutation will come in 3 different variants, and we'll have 24 permutations that we can consider, so the answer should be 8 and the desired 3-cycles are as follows:
(1 2 3),(2 3 1),(3 1 2)
(1 3 2),(3 2 1),(2 1 3)
(1 2 4),(2 4 1),(4 1 2)
(1 4 2),(4 2 1),(2 1 4)
(2 3 4),(3 4 2),(4 2 3)
(2 4 3),(4 3 2),(3 2 4)
(3 4 1),(4 1 3),(1 3 4)
(3 1 4),(1 4 3),(4 3 1)

Right?
Deveno
Deveno is offline
#23
Nov23-11, 04:53 PM
Sci Advisor
P: 906
Quote Quote by AdrianZ View Post
Yes. Actually I was thinking about generalizing this idea to other cases as well.
For 3-cycles, each permutation will come in 3 different variants, and we'll have 24 permutations that we can consider, so the answer should be 8 and the desired 3-cycles are as follows:
(1 2 3),(2 3 1),(3 1 2)
(1 3 2),(3 2 1),(2 1 3)
(1 2 4),(2 4 1),(4 1 2)
(1 4 2),(4 2 1),(2 1 4)
(2 3 4),(3 4 2),(4 2 3)
(2 4 3),(4 3 2),(3 2 4)
(3 4 1),(4 1 3),(1 3 4)
(3 1 4),(1 4 3),(4 3 1)

Right?
i prefer to think of how many ways we can choose 3 objects out of 4:

4!/(3!1!) = 4, and for each set {a,b,c}, we can form two different 3-cycles:

(a b c) and (a c b)
I like Serena
I like Serena is offline
#24
Nov23-11, 04:54 PM
HW Helper
I like Serena's Avatar
P: 6,189
Right!
AdrianZ
AdrianZ is offline
#25
Nov23-11, 04:54 PM
P: 320
Quote Quote by Deveno View Post
i prefer to think of how many ways we can choose 3 objects out of 4:

4!/(3!1!) = 4, and for each set {a,b,c}, we can form two different 3-cycles:

(a b c) and (a c b)
Yea, That's exactly what I did.
Deveno
Deveno is offline
#26
Nov23-11, 05:00 PM
Sci Advisor
P: 906
so, to find the number of k-cycles in Sn, you take n choose k times (k-1)!, which is how many k-cycles you can form in Sk.
AdrianZ
AdrianZ is offline
#27
Nov23-11, 05:01 PM
P: 320
Hey man, I thought group theory sucks, but now I think group theory rocks. everything looks so beautifully consistent. I believe I should solve more problems in group theory rather than just dealing with the concepts abstractly.

I'll try to find how many solutions the equation x5=e can have in S5. then I'll try to guess how many solutions the equation xn=e can have in Sn and will write down my thoughts here. it looks to be a good food for thought. Thank you guys for your helps, especially I like Serena.

One more question, Is it always possible to solve an equation like axn=b in Sn? When it's possible?
I like Serena
I like Serena is offline
#28
Nov23-11, 05:15 PM
HW Helper
I like Serena's Avatar
P: 6,189
Quote Quote by AdrianZ View Post
Hey man, I thought group theory sucks, but now I think group theory rocks. everything looks so beautifully consistent. I believe I should solve more problems in group theory rather than just dealing with the concepts abstractly.

I'll try to find how many solutions the equation x5=e can have in S5. then I'll try to guess how many solutions the equation xn=e can have in Sn and will write down my thoughts here. it looks to be a good food for thought. Thank you guys for your helps, especially I like Serena.
Looks like a good plan!


Quote Quote by AdrianZ View Post
One more question, Is it always possible to solve an equation like axn=b in Sn? When it's possible?
No, it's not always possible.
It depends on the order of the permutations involved, and it also depends on whether the permutations are even or odd.
AdrianZ
AdrianZ is offline
#29
Nov23-11, 05:22 PM
P: 320
Quote Quote by I like Serena View Post
No, it's not always possible.
It depends on the order of the permutations involved, and it also depends on whether the permutations are even or odd.
Would you explain more please?

We found out that there are 1 one-cycle, 6 different 2-cycles, 8 different 3-cycles and 6 different 4-cycles in S4. but if we add 1+6+8+6 it'd be equal to 21, not 24. How so?
micromass
micromass is online now
#30
Nov23-11, 05:28 PM
Mentor
micromass's Avatar
P: 16,548
Quote Quote by AdrianZ View Post
Would you explain more please?

We found out that there are 1 one-cycle, 6 different 2-cycles, 8 different 3-cycles and 6 different 4-cycles in S4. but if we add 1+6+8+6 it'd be equal to 21, not 24. How so?
Because there are three elements we missed: (1 2)(3 4) is one of them. Can you find the others?
I like Serena
I like Serena is offline
#31
Nov23-11, 05:29 PM
HW Helper
I like Serena's Avatar
P: 6,189
Quote Quote by AdrianZ View Post
One more question, Is it always possible to solve an equation like axn=b in Sn? When it's possible?
Quote Quote by AdrianZ View Post
Would you explain more please?
Explained with orders:

In S4, x^4 is either identity or a 3-cycle (with order 3).
If a and b differ in order, but not by 3, there is no solution.


Explained with even and odd permutions:
(Do you know what even and odd permutations are?)

In S4, x^4 is always an even permutation.
If a is odd and b is even, then there is no solution.



Quote Quote by AdrianZ View Post
We found out that there are 1 one-cycle, 6 different 2-cycles, 8 different 3-cycles and 6 different 4-cycles in S4. but if we add 1+6+8+6 it'd be equal to 21, not 24. How so?
Yes, you're missing 3 of them.
Did you already have them in your original solution?

As a challenge (when you find them), how should you count how many there are?
AdrianZ
AdrianZ is offline
#32
Nov23-11, 05:34 PM
P: 320
Quote Quote by micromass View Post
Because there are three elements we missed: (1 2)(3 4) is one of them. Can you find the others?
Yup. (1 2)(3 4), (1 3)(2 4), (1 4)(2 3).

Quote Quote by I like Serena View Post
Explained with orders:

In S4, x^4 is either identity or a 3-cycle (with order 3).
If a and b differ in order, but not by 3, there is no solution.


Explained with even and odd permutions:

In S4, x^n is always an even permutation.
If a is odd and b is even, then there is no solution.
Why in S4, x^4 is either identity or a 3-cycle?


Yes, you're missing 3 of them.
Did you already have them in your original solution?

As a challenge (when you find them), how should you count how many there are?
well, in this case it's easy. I want to have 2 disjoint cycles, each cycle is of order 2, once I choose the first 2-cycle, the second 2-cycle will be automatically determined. I can choose the first cycle in 3 different ways, so I'll miss 3 solutions of the equation.
I like Serena
I like Serena is offline
#33
Nov23-11, 05:38 PM
HW Helper
I like Serena's Avatar
P: 6,189
Quote Quote by AdrianZ View Post
Why in S4, x^4 is either identity or a 3-cycle?
Didn't you just proof that?
You found 8 3-cycles, and the other 16 permutations obey x^4=id.



Quote Quote by AdrianZ View Post
well, in this case it's easy. I want to have 2 disjoint cycles, each cycle is of order 2, once I choose the first 2-cycle, the second 2-cycle will be automatically determined. I can choose the first cycle in 3 different ways, so I'll miss 3 solutions of the equation.
Not quite. You can choose the first cycle in 6 different ways.
AdrianZ
AdrianZ is offline
#34
Nov23-11, 05:43 PM
P: 320
Quote Quote by I like Serena View Post
Didn't you just proof that?
You found 8 3-cycles, and the other 16 permutations obey x^4=id.
Then let me re-read your post, maybe I misunderstood it.

Not quite. You can choose the first cycle in 6 different ways.
In the general case you're right, it'll be 4 choose 2. but here it won't differ.
(1 3)(2 4), (1 4)(2 3), (1 2)(3 4)
(2 3)(1 4), (2 4)(1 3)
(3 4)(1 2)

the last 2 rows are not new permutations. that's why I counted it that way for this particular case.
I like Serena
I like Serena is offline
#35
Nov23-11, 05:57 PM
HW Helper
I like Serena's Avatar
P: 6,189
Okay, you counted it right, but then, you already knew it should be 3.

Anyway, I believe you were going to set up a generalized formula for k-cycles in Sn.
When you have that, you may want to revisit this problem.
AdrianZ
AdrianZ is offline
#36
Nov23-11, 06:30 PM
P: 320
Quote Quote by I like Serena View Post
Okay, you counted it right, but then, you already knew it should be 3.

Anyway, I believe you were going to set up a generalized formula for k-cycles in Sn.
When you have that, you may want to revisit this problem.
Actually I wanted to set up a generalized formula for the number of solutions of the equation xn=e, but now I see that it can be a little bit more tricky when n is not a prime number, because then I'll have to count the number of the generated cycles as products of disjoint cycles. that would make it harder.

The number of k-cycles in Sn is (n,k)*(k-1)! as someone else mentioned. the reason is that first we have to choose k letters out of n letters for forming k-cycles, then we fix the first element and permute the others and that can be done in (k-1)! ways. so the answer will be (n,k)*(k-1)! where (n,k) is n choose k.

this gives us the ability to predict the solutions of xn=e when n is prime. since the only divisors of n are 1 and itself, we'll have (1 + (n-1)!) solutions.
so, x5=e we'll have 25 solutions in S5.

we can also predict the number of solutions of xk=e in Sn when n is prime. the answer will be (1 + (n,k)*(k-1)!).
the number of solutions of x4=e in S5 is 1 + 5*24 = 121.
the number of solutions of x2=e in S3 is 1 + 3*1 = 4. those solutions namely are: {e,(1 2),(1 3),(2 3)}.

the case where n is not prime is a bit tricky, but I'll think about it. first I'll need to prove some theorems, for example if p and q are two disjoint cycles, then o(pq)=o(p)o(q). it needs more considerations, I'll think about it later.

Thanks guys for the help, and have a nice thanksgiving holiday tomorrow.


Register to reply

Related Discussions
For an ideal gas He at T = 328 K find the two speeds v that satisfy the equation 2F.. Advanced Physics Homework 6
finding all values that satisfy the equation Precalculus Mathematics Homework 8
what values of a and b satisfy the following wave equation? Introductory Physics Homework 4
equation of a rotated parabola knowing only 3pts the equation has to satisfy General Math 7
how to satisfy Laplace's equation ? Differential Geometry 6