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