From: rusin@vesuvius.math.niu.edu (Dave Rusin)
Newsgroups: sci.math
Subject: Re: count the periods of all group elements
Date: 21 Oct 1997 20:31:39 GMT

In article <62f7c5$s39@crocus.csv.warwick.ac.uk>,
Dr D F Holt <mareg@csv.warwick.ac.uk> wrote:
>In article <19971019192501.PAA01930@ladder01.news.aol.com>,
>	[Permission pending] writes:
>>Let S(n) be the symmetric group of order n!,that is the group of all
>>  permutations of n elements.
>>How are the No(i) distributed if G=S(n)  ?
>>What is the chance for a randomly chosen permutation of 100 elements,
>> that it's period is < 1000 ?
>>What is the biggest i ("max_period(G)") , such that No(i) > 0 ?
>>Is there a polynomial p(n),such that max_period(S(n))/p(n) --> 1 ? 
>
>There is some (rather old) literature proving asymptotic results about
>the largest order of an element in S(n). I am sorry I cannot remember
>the references. My memory is that the largest order grows faster than any
>polynomial.
>
>I have a printout of largest orders up to n=500.
>For n=26 it is 1260 (cycle lengths 4,9,5,7)
>For 52 it is 180180
>        (lengths 4,9,5,7,11,13 - useful for problems about shuffling)
>For 500 it is  about 7.15 x 10^23.

It should not be a shock that the principal early results were obtained
by Erdos. Here is a sample:

Pick an element  g  at random from  S(n)  and compute  x=log( o(P) ).
Of course, for fixed  n, this  x  will take on only a finite set of values,
and we can calculate the relative frequency of their occurence. But
as  n -> oo  we find  x  to be normally distributed, with mean
mu= (1/2) log(n) ^2  and standard deviation  (1/sqrt(3)) (log n)^(3/2).
See Erdos and Turan, "On some problems of a statistical group theory, III",
Acta Math Acad Sci Hungar 18(1967) 309-320.

The log of the largest order of an element in  S(n)  is asymptotic to 
sqrt(n*log(n)).  This is essentially number theory. I think the first
proof was by Landau early this century. Some refined asymptotics are
available too. By the way, the max-order function is not strictly
increasing.

dave
==============================================================================
Date: Wed, 22 Oct 1997 15:36:31 -0400
To: rusin@vesuvius.math.niu.edu (Dave Rusin)
From: [Permission pending]
Subject: Re: count the periods of all group elements
Newsgroups: sci.math

 > It should not be a shock that the principal early results were obtained
  > by Erdos. Here is a sample:
    should I know about Erdos ?

 > Pick an element  g  at random from  S(n)  and compute  x=log( o(P) ).
    what's P ? I assume, you mean g .
 > Of course, for fixed  n, this  x  will take on only a finite set of values,
 > and we can calculate the relative frequency of their occurence. But
 > as  n -> oo  we find  x  to be normally distributed, with mean
 > mu= (1/2) log(n) ^2  and standard deviation  (1/sqrt(3)) (log n)^(3/2).
    rather astonishing to me ! So No(i) becomes symmetric around mu and 
     No(i)/mu vanishes for small i .This also implies,that all gaps between
     adjacent x become arbitrary small compared to mu ?!
    What is the asymptotics of # of those x,that is #{o(g)|g in S(n)} ?
 > See Erdos and Turan, "On some problems of a statistical group theory, III",
 > Acta Math Acad Sci Hungar 18(1967) 309-320.
    yes,thanks,I'll look at it ,when I get an opportunity.

 > The log of the largest order of an element in  S(n)  is asymptotic to 
 > sqrt(n*log(n)).  This is essentially number theory. I think the first
    log(#S(n))/log(max_order(S(n)) is asymtotic to sqrt(n*log n) too , 
     so the orders of permutations become _very_ small compared to #S(n) ;
     in some sense to the same degree as they grow in total !
 > proof was by Landau early this century. Some refined asymptotics are
 > available too. By the way, the max-order function is not strictly
 > increasing.
    are there arbitrary large n, with max_order(S(n))=max_order(S(n+1)) ?
==============================================================================
Date: Wed, 22 Oct 1997 14:47:06 -0500 (CDT)
From: Dave Rusin <rusin>
To: [Permission pending]
Subject: Re: count the periods of all group elements

> should I know about Erdos ?
Paul Erdos, recently deceased, was a truly phenomenal mathematician.
Essentially homeless, he lived and breathed mathematics rather than
focus on trivial matters such as family, food, or security. He
was author or coauthor of thousands of papers. His interests included
a lot of asymptotic number theory, not all that distant from your questions.

>> Pick an element  g  at random from  S(n)  and compute  x=log( o(P) ).
> what's P ? I assume, you mean g .
Oops; you're right.
 
> What is the asymptotics of # of those x,that is #{o(g)|g in S(n)} ?
I don't really know. The appropriate resource is probably the "Reviews on
Finite Groups" by Gorenstein, ca. 1970's.

> are there arbitrary large n, with max_order(S(n))=max_order(S(n+1)) ?
Yes. See Nicolas, "Ordre maximal d'un element du group S_n des permutations
et 'highly composite numbers' ", Bull Soc Math France 97 (1969) 129-191.

dave