Author |
Topic: Largest Order Element In S_n (Read 6076 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
Largest Order Element In S_n
« on: Jan 27th, 2004, 10:35pm » |
 Quote  Modify
|
Does anyone know if there's a good way to compute what is the largest order of the elements in the permutation group Sn? (E.g. for S5, the largest order is 6.)It seems like a dynamic programming style problem, but I was hoping for better ways.
|
|
 IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Largest Order Element In S_n
« Reply #1 on: Jan 28th, 2004, 12:58am » |
Quote Modify
|
I can't say I understand the problem.. What is 'Sn' and what is 'order' in this context?
And isn't this more of a CS than putnam problem?
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Largest Order Element In S_n
« Reply #2 on: Jan 28th, 2004, 1:56am » |
Quote Modify
|
Oh, this is group theory. Sn is the symmetric group, otherwise known as the permutation group.
A group is a pair (G,[cdot]), where G is a set of elements and [cdot] is a binary operation, such that all of the following hold
1) Identity: There exists an identity element e such that x[cdot]e = e[cdot]x = x
2) Closure: For any two elements x,y[in]G, x[cdot]y [in] G
3) Associativity: For x,y,z[in]G, (x[cdot]y)[cdot]z = x[cdot](y[cdot]z)
4) Inverses: For any x[in]G, there exists a x-1[in]G such that x[cdot]x-1 = x-1[cdot]x = e.
In a group, the order of an element x is the smallest natural number n such that x[cdot]x[cdot]x .... [cdot]x = xn = e, where e is the identity element.
The permutation group Sn is the set of all ways to permute n objects, paired with the binary operation of composition.
So my question is, for a given n, what is the order of the highest order element in Sn. It seems like dynamic programming could find a solution, but since I only know a few weeks of a first course in group theory, I was wondering if maybe there is an O(1) algorithm for finding the answer (i.e. a simple equation).
It wouldn't be game for a Putnam but it is a pure math question anyways.
|
| « Last Edit: Jan 28th, 2004, 1:57am by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Largest Order Element In S_n
« Reply #3 on: Jan 28th, 2004, 2:26am » |
Quote Modify
|
I may be mistaken, but this seems similar to that puzzle about the typewriter with the keys randomly reassigned, and where you need to find out how many times you need to type the output before you get the correct message.
Of course there you needed the least common multiple of all the orders..
here's the thread: Typewriter Gibberish
|
| « Last Edit: Jan 28th, 2004, 3:44am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Largest Order Element In S_n
« Reply #4 on: Jan 28th, 2004, 3:42am » |
Quote Modify
|
towr is right. And I don't believe there exists a closed formula to compute this.
It's sometimes called Landau's function in math literature and denoted G(n). Landau proved that asymptotically, log G(n) ~ sqrt(nlogn).
|
| « Last Edit: Jan 28th, 2004, 3:42am by Barukh » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Largest Order Element In S_n
« Reply #5 on: Jan 28th, 2004, 3:51am » |
Quote Modify
|
here's wikipedia on Landau's function
Quote:Landau's function g(n) is defined for every positive integer n to be the largest order of an element of the symmetric group Sn. Equivalently, g(n) is the largest least common multiple of any partition of n.
For instance, 5 = 2 + 3 and lcm(2,3) = 6. No other partition of 5 yields a bigger lcm, so g(5) = 6. An element of order 6 in the group S5 can be written in cycle notation as (1 2 3) (4 5).
The integer sequence g(1) = 1, g(2) = 2, g(3) = 3, g(4) = 4, g(5) = 6, g(6) = 6, g(7) = 12, g(8) = 15, ... is A000793. |
|
mathworld doesn't seem to have any info on this unfortunately..
|
| « Last Edit: Jan 28th, 2004, 3:53am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
klmreddy
Guest
|
|
Re: Largest Order Element In S_n
« Reply #6 on: Aug 17th, 2004, 12:08am » |
Quote Modify
 Remove
|
every permutation can be written as product of disjoint cycles .
since the length of the cycle is equals order the cycle. We can simply find
the order of a permutation by the following way.
suppose a permutation is written as product of n1 , n2 , ... , nk length disjoint cycles then the order of permutation is L.C.M(n1 , n2 , ... , nk ).
now the question comes " how could we know all possibilities of permutations decompositions into disjoint cycles "?
suppose in S4 we are considering promutations on 4 elements set.
4 = 4+0
= 3+1
= 2+2
= 2+1+1
= 1+1+1+1 are called cycle types
so every permutation on four symbols( elements) is
4 cycle (or) order 4
3 cycle X 1 cycle order 3
2 cycle X 2 cycle order L.C.M(2,2)=2
2 cycle X 1 cycle X 1 cycle order LCM(2,1,1) = 2
All 1 cycles i.e identity permutation order 1
So now in S5
5 = 5+0 order 5
= 4+1 order 4
= 3+2 order 6
= 3+1+1 order 3
= 2+2+1 order 2
= 2+1+1+1 order 2
= 1+1+1+1+1 order 1
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print