wu :: forums
« wu :: forums - Largest Order Element In S_n »

Welcome, Guest. Please Login or Register.
Mar 28th, 2024, 3:35am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   putnam exam (pure math)
(Moderators: Grimbal, SMQ, Eigenray, towr, Icarus, william wu)
   Largest Order Element In S_n
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Largest Order Element In S_n  (Read 6007 times)
william wu
wu::riddles Administrator
*****





   
WWW

Gender: male
Posts: 1291
Largest Order Element In S_n  
« on: Jan 27th, 2004, 10:35pm »
Quote Quote Modify 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: male
Posts: 13730
Re: Largest Order Element In S_n  
« Reply #1 on: Jan 28th, 2004, 12:58am »
Quote Quote Modify 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
*****





   
WWW

Gender: male
Posts: 1291
Re: Largest Order Element In S_n  
« Reply #2 on: Jan 28th, 2004, 1:56am »
Quote Quote Modify 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: male
Posts: 13730
Re: Largest Order Element In S_n  
« Reply #3 on: Jan 28th, 2004, 2:26am »
Quote Quote Modify 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: male
Posts: 2276
Re: Largest Order Element In S_n  
« Reply #4 on: Jan 28th, 2004, 3:42am »
Quote Quote Modify 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: male
Posts: 13730
Re: Largest Order Element In S_n  
« Reply #5 on: Jan 28th, 2004, 3:51am »
Quote Quote Modify 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

Email

Re: Largest Order Element In S_n  
« Reply #6 on: Aug 17th, 2004, 12:08am »
Quote Quote Modify Modify Remove 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
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board