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 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 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