What are the odds two permutations in S_n do NOT generate the whole group? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T14:47:40Z http://mathoverflow.net/feeds/question/45505 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/45505/what-are-the-odds-two-permutations-in-s-n-do-not-generate-the-whole-group What are the odds two permutations in S_n do NOT generate the whole group? John Mangual 2010-11-10T01:32:09Z 2010-11-10T09:22:46Z <p><b>What are the odds two uniformly chosen elements of S_n span the whole group (or just the alternating group)?</b> 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?</p> <p>Also, <b>how can you <em>efficiently</em> find the size of the subgroup $\langle a,b\rangle$ in S_n ?</b> 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. <hr> You <em>can</em> 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.</p> http://mathoverflow.net/questions/45505/what-are-the-odds-two-permutations-in-s-n-do-not-generate-the-whole-group/45506#45506 Answer by Gerry Myerson for What are the odds two permutations in S_n do NOT generate the whole group? Gerry Myerson 2010-11-10T01:41:42Z 2010-11-10T01:41:42Z <p>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$. </p> <p>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. </p> http://mathoverflow.net/questions/45505/what-are-the-odds-two-permutations-in-s-n-do-not-generate-the-whole-group/45508#45508 Answer by HW for What are the odds two permutations in S_n do NOT generate the whole group? HW 2010-11-10T02:01:54Z 2010-11-10T02:01:54Z <p>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.</p> <p><strong>Theorem (Jordan, 1871):</strong> There is a function $J :\mathbb{N} \to \mathbb{N}$ with the following properties:</p> <ol> <li>$J(n)\to\infty$ as $n\to\infty$;</li> <li>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$.</li> </ol> <p>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$. </p> http://mathoverflow.net/questions/45505/what-are-the-odds-two-permutations-in-s-n-do-not-generate-the-whole-group/45509#45509 Answer by Igor Pak for What are the odds two permutations in S_n do NOT generate the whole group? Igor Pak 2010-11-10T02:06:52Z 2010-11-10T02:06:52Z <p>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. </p> <p>For asymptotics for general simple groups, see <a href="http://www.springerlink.com/content/r32065tp23lu7847/" rel="nofollow">this paper</a> by Liebeck and Shalev, and a recent <a href="http://www.emis.ams.org/journals/DMJDMV/xvol-icm/02/Shalev.MAN.ps.gz" rel="nofollow">short survey</a> by Shalev. </p> http://mathoverflow.net/questions/45505/what-are-the-odds-two-permutations-in-s-n-do-not-generate-the-whole-group/45539#45539 Answer by Derek Holt for What are the odds two permutations in S_n do NOT generate the whole group? Derek Holt 2010-11-10T09:22:46Z 2010-11-10T09:22:46Z <p>Concerning the second part of the OP's question:</p> <blockquote> <p>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. </p> </blockquote> <p>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.</p> <p>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 &lt; p &lt; n-2$, then $G = A_n$ or $S_n$.</p> <p>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.</p>