From: gerry@mpce.mq.edu.au (Gerry Myerson) Subject: Re: Max Order of a Group Element Date: Wed, 10 Feb 1999 09:02:03 +1100 Newsgroups: sci.math Keywords: max order of elements in the symmetric group S_n In article <79q8tl$ca9@sjx-ixn5.ix.netcom.com>, "Daniel Giaimo" wrote: > Bruce W. Colletti wrote in message > news:79ps7f$hcf$1@geraldo.cc.utexas.edu... > >Is there a formula for the max order of a permutation in the symmetric > >group on n-letters? > > Sure. Here it is: > > Let S = {A | A is a subset of {1,2,...,n}, and gcd(A) = 1} > Let T = {prod(a in A)(a) | A in S) > > Then the max order of a permutation in S_n is max{T}. It's OK to be a wise guy, if you get the answer right. I think you'll find that your formula predicts the existence of an element of order 6 in S_3 (take A = {2, 3}), which would be a surprising development at this late stage in the game. I suspect the original poster was hoping for an answer in the form of a function that a 1st-year calculus student would recognize; there is none. Next best thing would be an asymptotic estimate. There is a lot of literature on this, and I'd suggest DG take it on as a project to track down the appropriate papers & then report back to us. As a very, very rough answer: if you add up all the positive integers not exceeding square root of 2n, you get n, give or take a bit. If you only add the primes, you get a fair bit less than n. If you multiply all the primes up to that bound, you get, roughly, e-to-the-sqrt(2n) (this is well-known but not at all obvious). So, for large n, it's safe to say there's an element of order greater than e-to-the-sqrt(2n). Gerry Myerson (gerry@mpce.mq.edu.au) ============================================================================== From: mareg@lily.csv.warwick.ac.uk (Dr D F Holt) Subject: Re: Max Order of a Group Element Date: 10 Feb 1999 09:34:48 GMT Newsgroups: sci.math In article <79ps7f$hcf$1@geraldo.cc.utexas.edu>, bcolletti@mail.utexas.edu (Bruce W. Colletti) writes: >Is there a formula for the max order of a permutation in the symmetric >group on n-letters? > >Bruce > There is (almost certainly) no simple algebraic formula of the kind you are presumably looking for, but asymptotically the max order grows like exp(sqrt(n*log(n))) To save you the arduous exercise of looking up references, which some cruel poster set you, I quote from a similar thread about a year ago. I can compute specific values up to about n=25000 if you are interested. >This was apparently first proved by E. Landau in 1903. >The only reference I have is the German book >E. Landau, "Handbuch der Lehre von der Verteilung der Primzahlen", >Leipzig & Berlin, B.G. Teubner, 1909. > >> Two trivial properties of the array of results, r_n, are >> 1) r_n is monotonically non-decreasing, > >there are arbitrarily big n with r_n = r_{n+1} > >The reference I found for this (in French this time) proves that r_n is >constant on arbitrarily large intervals. > >Jean Louis Nicolas, `Ordre maximal d'un element du groupe S_n ... ', >Bulletin Societe Math. France 97 (1969), 129-191. > >I have a simple-minded C program (which anyone is welcome to), which >calculates the largest order of an element in S_n, together with its >prime factorisation. So far I have run it up to 24500. At this order >of degree it is starting to use rather a lot of memory. Derek Holt. ============================================================================== From: bcolletti@mail.utexas.edu (Bruce W. Colletti) Subject: Re: Max Order of a Group Element Date: 11 Feb 1999 00:59:46 GMT Newsgroups: sci.math In article <79rjro$scb$1@holly.csv.warwick.ac.uk>, mareg@lily.csv.warwick.ac.uk (Dr D F Holt) says: > >In article <79ps7f$hcf$1@geraldo.cc.utexas.edu>, > bcolletti@mail.utexas.edu (Bruce W. Colletti) writes: >>Is there a formula for the max order of a permutation in the symmetric >>group on n-letters? >> >>Bruce >> > >There is (almost certainly) no simple algebraic formula of the kind you are >presumably looking for, but asymptotically the max order grows like >exp(sqrt(n*log(n))) Derek Holt and Gerry Myerson Thanks for your replies (Derek, will keep your computational offer in mind). The only thing I found on this was Erdos' 1967 paper "On Some Problems of a statistical Group-theory III", Acta Mathematica Academiae Scientiarum Hungaricae Tomus 18, 309-320. In it he proves ln(X) is standard normally distributed, where X denotes the order of a permutation in S(n). Although Derek's reply also appears at the beginning of Erdos' paper, I was hoping research since then may have shed new light on the original question. But knowing this result is still the one is useful to know. Bruce ============================================================================== From: John George Subject: Order of a permutation. Date: Sat, 13 Feb 1999 22:52:25 GMT Newsgroups: sci.math.research What's the largest order of a permutation in the symmetric group S_n? I believe it's easy to see that the answer is: The maximum (over all partitions x1, x2, ... xk of n) of the least common multiple of the set {x1, ... xk}. But is there a closed formula? I suspect not, since partitions are notorious for not admitting closed formulae, but I thought I'd ask and see if anybody knows for sure. Thanks, John George ============================================================================== From: yerman@advicom.zapthis.net (Niall Graham) Subject: Re: Order of a permutation. Date: 13 Feb 1999 23:36:15 -0600 Newsgroups: sci.math.research [above article quoted -- djr] This is a well-studied function (call it g(n)) Landau showed that log g(n) ~ {nlogn}^1/2 It is easy to show that it is sufficient to consider permutations whose cycle lengths are powers of primes. The most recent article that I know of is On Landau's function g(n) by Jean-Louis Nicolas in The Mathematics of Paul Erdos Vol 1. Springer 1997 There was also a survey by W. Miller in a 1987 issue of the Monthly. Niall Graham