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