From: sfinch@mathsoft.com (Steven Finch)
Subject: prob of 2 elements generating S_n
Date: Wed, 09 Feb 2000 10:47:19 -0500
Newsgroups: sci.math.research
Summary: [missing]

	Hello!

	Let p(n) denote the probability that two 	elements of the 
	symmetric group, S_n, chosen at random (with replacement) 
	actually generate S_n.

	What can be said about the asymptotics of p(n)?  

	Maybe this is well-known?  If you have a favorite reference,
	please e-mail me.

	Since this is similar to questions raised in
		
	   http://www.mathsoft.com/asolve/constant/golomb/golomb.html

	I can't help but wonder if there is a connection.

	Values of p(n) for n=1,2,3,...,9 are 1, 3/4, 1/2, 3/8, 19/40, 
	53/120, 103/168, 4111/6720 and 78293/120960 (from Sloane's
	sequence database).  I believe that these are all known values.

					Thank you!

						Steve Finch






******************************************
Steven Finch                      
MathSoft, Inc.                    
101 Main St.                      
Cambridge, MA, USA 02142          
http://www.mathsoft.com/asolve/sfinch.html
==============================================================================

From: "A. Caranti" <caranti@science.unitn.it>
Subject: Re: prob of 2 elements generating S_n
Date: Wed, 09 Feb 2000 21:24:20 +0100
Newsgroups: sci.math.research

Steven Finch wrote:

>         Let p(n) denote the probability that two elements of the
>         symmetric group, S_n, chosen at random (with replacement)
>         actually generate S_n.
> 
>         What can be said about the asymptotics of p(n)?

The subject of probabilistic methods in group theory has seen exciting
developments in recent years, as a search in Math Rev will reveal.

The answer to your question (which was asked by Netto in the 19th
century) has been given by John D. Dixon in: The probability of
generating the symmetric group. Math. Z. 110 1969 199--205. I quote the
main result from MR:
Theorem 1: The proportion of ordered pairs $(x,y) (x,y\in S\sb n)$ which
generate either $A\sb n$ or $S\sb n$ is greater than
		$1-2(\log\text{}\log n)\sp 2$ 
for all sufficiently large $n$."

Andreas Caranti
==============================================================================

From: "A. Caranti" <caranti@science.unitn.it>
Subject: Re: prob of 2 elements generating S_n
Date: Thu, 10 Feb 2000 22:17:45 +0100
Newsgroups: sci.math.research

I had written, in response to a message of Steven Finch:

> The answer to your question (which was asked by Netto in the 19th
> century) has been given by John D. Dixon in: The probability of
> generating the symmetric group. Math. Z. 110 1969 199--205. I quote the
> main result from MR:
> Theorem 1: The proportion of ordered pairs $(x,y) (x,y\in S\sb n)$ which
> generate either $A\sb n$ or $S\sb n$ is greater than
>                 $1-2(\log\text{}\log n)\sp 2$
> for all sufficiently large $n$."

I quoted verbatim, and realized only later that there is a misprint in
the original review MR 40 #4985. Sorry. The correct lower bound is
		1 - 2 log(log(n))^(-2).
This bound has been improved in later papers: see Math Rev for details.

Andreas Caranti