Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
20  
The odds can't approach 1; with probability 1/4, both permutations are alternating. You might want to check your code for bugs. –  David Speyer Nov 10 '10 at 1:35
    
So the first order is the parity and second order is whether they fix a common element. Maybe there is a representation-theoretic way to unify these two kinds of obstructions. Certainly if they both fix the same $m$ elements, the subgroup will be smaller. The higher order "cousins" of parity are less obvious. –  john mangual Nov 10 '10 at 2:54
2  
John, there is nothing "representation-theoretic" about it - this is an elementary group theory. Read Ph. Hall's qjmath.oxfordjournals.org/content/os-7/1/134.extract to see how does this work, as well as Shalev's survey I mentioned below. Also, while I am at it, "all two element generating sets are conjugate to this" is the opposite of the truth, since conjugates of a transposition is a transposition. Finally, to see the size of the permutation subgroup use the Schreier–Sims algorithm: en.wikipedia.org/wiki/Schreier%E2%80%93Sims_algorithm –  Igor Pak Nov 10 '10 at 3:25
    
I mean... what characterizes pairs of permutations that generate all of $S_n$ (or if they're both even $A_n$)? Also Sage Online already has a way to find orders of perm groups (probably using this Schrier-Sims algorithm with GAP). Maybe a good book on permutation groups has a description. –  john mangual Nov 11 '10 at 0:18
add comment

4 Answers

up vote 15 down vote accepted

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.

share|improve this answer
7  
What's classical about 1989!? –  HJRW Nov 10 '10 at 2:10
2  
@Henry: sometimes papers become classical rather quickly. See bit.ly/d8Nub7 which finds a "classical 1998 paper" reference in a 2004 paper! –  Igor Pak Nov 10 '10 at 3:11
2  
Igor - huh, nice! So it's not just mathematicians that confuse 'classical' with 'classic'. –  HJRW Nov 10 '10 at 3:50
4  
The way I've heard it, "classical" means "it was known when I was in grad school". –  Michael Lugo Nov 10 '10 at 4:04
7  
@Henry: "classical" means "before the arXiv". –  Mariano Suárez-Alvarez Nov 10 '10 at 5:37
show 4 more comments

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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:

  1. $J(n)\to\infty$ as $n\to\infty$;
  2. 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$.

share|improve this answer
    
On reflection, I suppose that also follows from the result of Dixon. Still, this is another way to think about it. –  HJRW Nov 10 '10 at 2:03
    
Is 1. necessary to state? Aren't all functions $J :\mathbb{N} \to \mathbb{N}$ such that $J(n) \rightarrow \infty$ as $n \rightarrow \infty$? –  Ross Millikan Nov 10 '10 at 4:14
    
Ross - er, no. Eg $J(n)=2$ (which also satisfies part 2). –  HJRW Nov 10 '10 at 4:28
    
Perhaps this is the point of confusion: 'function' in this context just means 'set map'. –  HJRW Nov 10 '10 at 14:29
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.