What are the odds two permutations in S_n do NOT generate the whole group? - MathOverflow

What are the odds two permutations in S_n do NOT generate the whole group?

2010-11-10T01:32:09Z

What are the odds two uniformly chosen elements of S_n span the whole group (or just the alternating group)? Mathematica experements suggest those odds approach 1 - this might have been proven a long time ago. How likely is it to get the alternating group or something much smaller?

Also, how can you efficiently find the size of the subgroup $\langle a,b\rangle$ in S_n ? My crude tests consists of randomly multiplying the two permutations and seeing how many different elements you get. Maybe there's a more efficient way to generate all the elements spanned by two permutation.

You can generate the whole permutation group using a swap (12) and a shift (12...n). I wonder if all two element generating sets are conjugate to this.

Answer by Gerry Myerson for What are the odds two permutations in S_n do NOT generate the whole group?

2010-11-10T01:41:42Z

See John D Dixon, The probability of generating the symmetric group, Math Z 110 (1969) 199-205. Theorem 1. The proportion of ordered pairs $(x,y)$, $x$ and $y$ in $S_n$, which generate either $A_n$ or $S_n$ is greater than $1-2/(\log\log n)^2$ for all sufficiently large $n$.

Whether you get $A_n$ or $S_n$ is just a question of whether both permutations are even, so the chances of spanning the whole group approach 3/4.

Answer by HW for What are the odds two permutations in S_n do NOT generate the whole group?

2010-11-10T02:01:54Z

Regarding the last part of your question: no, there are other two-element generating sets. I don't have an explicit example to hand, though they should be easy enough to write down, but their existence can be deduced from the following theorem of Jordan.

Theorem (Jordan, 1871): There is a function $J :\mathbb{N} \to \mathbb{N}$ with the following properties:

$J(n)\to\infty$ as $n\to\infty$;
if $\Gamma\to S_n$ is primitive with minimal degree at most $J(n)$ then the image of $\Gamma$ is the symmetric group $S_n$ or the alternating group $A_n$.

In particular, this means that a large cycle $(1,\ldots, p)$ for $p$ prime and another cycle $(1,\ldots,2n)$ for $2n\leq J(p)$ will together generate $S_p$.

Answer by Igor Pak for What are the odds two permutations in S_n do NOT generate the whole group?

2010-11-10T02:06:52Z

The probability of generation of $A_n$ or $S_n$ by two random permutations is $1 - 1/n - O(1/n^2)$. The $1/n$ term comes from both permutations having the same fixed point. This is a classical result of L. Babai: The probability of generating the symmetric group, Journal of Combinatorial Theory, Series A, 1989. Warning: it uses the classification of finite simple groups.

For asymptotics for general simple groups, see this paper by Liebeck and Shalev, and a recent short survey by Shalev.

Answer by Derek Holt for What are the odds two permutations in S_n do NOT generate the whole group?

2010-11-10T09:22:46Z

Concerning the second part of the OP's question:

Also, how can you efficiently find the size of the subgroup $\langle a,b \rangle$ in $S_n$ ? My crude tests consists of randomly multiplying the two permutations and seeing how many different elements you get. Maybe there's a more efficient way to generate all the elements spanned by two permutation.

There is a "classical" polynomial-time method known as the "Schreier-Sims" algorithm for finding the order of the subgroup of $S_n$ generated by a given set of permutations - just google it for further details. It has a number of improvements for dealing with groups of very large degree. Refinements of this were used by Sims to prove the existence of some of the large sporadic finite simple groups, including the Lyons group and the Baby Monster.

There are also very fast "one-sided Monte-Carlo" probabilistic algorithms for verifying that the group generated by a given set of permutations is $A_n$ or $S_n$. If they do, then "yes" will be returned rapidly with high probability. If they do not, then the algorithm does not terminate, so normally you would give up and use Schreier-Sims instead. This method is based on old results due to Jordan and others, which say that if $G \le S_n$ is transitive and contains an element of prime order $p$ with $n/2 < p < n-2$, then $G = A_n$ or $S_n$.

For further details, see Akos Seress' book "Permutation Group Algorithms" Cambridge University Press, 2003, or my own book, with B. Eick and E.A. O'Brien, "Handbook of Computational Group Theory", CRC Press, 2005.