wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Largest Order Element In S_n
        
(Message started by: william wu on Jan 27^th, 2004, 10:35pm)

Title: Largest Order Element In S_n
Post by william wu on Jan 27^th, 2004, 10:35pm

Does anyone know if there's a good way to compute what is the largest order of the elements in the permutation group S_n? (E.g. for S₅, the largest order is 6.)It seems like a dynamic programming style problem, but I was hoping for better ways.

Title: Re: Largest Order Element In S_n
Post by towr on Jan 28^th, 2004, 12:58am

I can't say I understand the problem.. What is 'S_n' and what is 'order' in this context?
And isn't this more of a CS than putnam problem?

Title: Re: Largest Order Element In S_n
Post by william wu on Jan 28^th, 2004, 1:56am

Oh, this is group theory. S_n 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 = xⁿ = e, where e is the identity element.

The permutation group S_n 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 S_n. 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.

Title: Re: Largest Order Element In S_n
Post by towr on Jan 28^th, 2004, 2:26am

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 (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1052846356;start=11)

Title: Re: Largest Order Element In S_n
Post by Barukh on Jan 28^th, 2004, 3:42am

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).

Title: Re: Largest Order Element In S_n
Post by towr on Jan 28^th, 2004, 3:51am

here's wikipedia on Landau's function (http://en.wikipedia.org/wiki/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 (http://en.wikipedia.org/wiki/Symmetric_group) S_n. 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 (http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A000793).

mathworld doesn't seem to have any info on this unfortunately..

Title: Re: Largest Order Element In S_n
Post by klmreddy on Aug 17^th, 2004, 12:08am

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