Date: Mon, 22 Jan 96 13:24:22 CST
From: rusin (Dave Rusin)
To: kasdan@news.cs.columbia.edu
Subject: Re: Order of elements in the Symmetric Group
Newsgroups: sci.math

In article <4ddoga$12r@ground.cs.columbia.edu> you write:
>I was wondering how big the order of an element in S_n can be,
>relative to n.  

This came up a couple of months ago. Someone -- maybe
Richard Pinch? -- posted a table with the maxima for  n<=100 or so.

>From consideration of cycle lengths, it seems that the largest order
>for an element of S_n should be (letting P_n be the set of all
>partitions of n and lcm(s) the least common multiple of the elements
>of the set of integers, s)
>
>     max(p \in P_n) lcm(p).
Right.

>So, if I am right so far, it seems that numbers of the form
>n = p_1 + p_2 + ... + p_n, where p_i is the i-th prime, have
>exceptionally large maximum cycle sizes, namely p_1*p_2*...*p_n.

Right, but not maximal in general.

Suppose you have a partition  n=Sum(a_i)  in which some summand (say a1) is
not a prime power (or 1). Write  a_1=b*c  where  gcd(b,c)=1; then b+c < a_1 and
lcm(b,c)=a_1, so the new partition  n = (b, c, a_1-b-c, a2, a3, ...) gives
rise to elements of order  lcm(a1-b-c, a1,a2,a3,...), which is at least
as large as  lcm(a1, a2, a3,...). By induction on the size of the largest
non-prime-power  a_i, we see that the optimal partition involves only 
prime powers (possibly including some  1's).

Clearly a partition  (a1, a2, ...)  in which  a1  and  a2  are powers of
the same prime (with say  a1 | a2) leads to elements of the same order as
(1, 1, 1, ... [a1 times], ...1, a2, a3, ...), so we may assume each  a_i
is a product of a different prime (or  1).

Now, _in general_, it makes sense not to use prime powers with exponents 
greater than 1. Indeed, we can replace any summand  p^r  in a partitition with
(p^(r-1), q, and some  1's)  as long as  q <= p^(r-1)*(p-1) -- a very 
generous range of values in which there are almost certainly many primes -- 
and in so doing replace a factor  p^r  of the order of the group element with
p^(r-1)*q, which is larger as long as  q > p.  However, it only increases
the order of the group element if  q  is a prime not already occuring in
the other  a_i. Thus an optimal group order will be square-free _or_ will
involve prime powers  p^r  such that every prime  q  in the interval
( p, p^(r-1)*(p-1) ) is also in the partition. For example, it seems quite
possible for an optimal partition to use  a_1=4.

Likewise there is in general no advantage to skipping primes, but in
some circumstances this may occur. For example, when  n=8, the decompositions
of  n  into relatively prime prime-power parts are
	8               -> 8
	7 1             -> 7
	5 3             -> 15 (*)
	5 2 1           -> 10
	4 3 1           -> 12
	4 1 1 1 1       -> 4
	3 2 1 1 1       -> 6
	3 1 1 1 1 1     -> 3
	2 1 1 1 1 1 1   -> 2
	1 1 1 1 1 1 1 1 -> 1
which shows the optimal plan involves skipping over  p=2. One rule of thumb
is that if a prime  p  does not occur but  q  is the largest prime occuring
(with an exponent of  r)  then it pays to replace  q^r  with  (p^r, Q, 1,1,...)
as long as a prime  Q  can be found in the interval  [q, q^r-p^r] with
q^r < p^r*Q, i.e., there needs to be a prime in the interval
	[max(q, (q/p)^r), q^r-p^r]
For  r>1, this will hold automatically (there's always a prime in [n, 2n]),
so you shouldn't skip primes if you end with a proper power, but it might
make sense to skip primes if your largest prime occurs only to the first power,
which we have already shown to be the usual case.

So I would have to say that your intuition is correct but incomplete.

The following pointer to the literature was posted:
Hope this helps.
dave

OLD POST:================================
Newsgroups: sci.math
Subject: Re: Interesting serie (was Re: HELP ON ABSTRACT ALGEBRA NEEDED)
From: mann@kineret.huji.ac.il (Avinoam Mann)
Date: 8 Oct 1995 02:51 IST  

>: In article <450vf6$otn@utrhcs.cs.utwente.nl> faase@cs.utwente.nl 
(Frans F.J. Faase) writes:
>:  > For given n, find maximal scm(a_1, .., a_k) such that a_1+ .. +a_k = n.
>:  > (scm = smallest common multiplier)

Equivalently, find the maximal order of an element of the symmetric group S_n.
(this was the original problem). Our library is going to be closed for about
10 days. What I found out meanwhile is that the problem was discussed by
E.Landau in 1909, in his book on prime numbers. Denoting the maximum by f(n),
Landau proved that log f(n) is asymptotic to  sqrt(n)logn. This information is
from the MR review of a paper by J.L.Nicolas (Acta Arith. 14; MR 37), where
more references and some properties of f(n) can be found. Nicolas has written
several papers on this function.
                                                             Avinoam Mann