6
$\begingroup$

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.

$\endgroup$
4
  • 21
    $\begingroup$ The odds can't approach 1; with probability 1/4, both permutations are alternating. You might want to check your code for bugs. $\endgroup$ Nov 10, 2010 at 1:35
  • $\begingroup$ 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. $\endgroup$ Nov 10, 2010 at 2:54
  • 2
    $\begingroup$ 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 $\endgroup$
    – Igor Pak
    Nov 10, 2010 at 3:25
  • $\begingroup$ 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. $\endgroup$ Nov 11, 2010 at 0:18

4 Answers 4

18
$\begingroup$

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.

$\endgroup$
10
  • 7
    $\begingroup$ What's classical about 1989!? $\endgroup$
    – HJRW
    Nov 10, 2010 at 2:10
  • 2
    $\begingroup$ @Henry: sometimes papers become classical rather quickly. See bit.ly/d8Nub7 which finds a "classical 1998 paper" reference in a 2004 paper! $\endgroup$
    – Igor Pak
    Nov 10, 2010 at 3:11
  • 2
    $\begingroup$ Igor - huh, nice! So it's not just mathematicians that confuse 'classical' with 'classic'. $\endgroup$
    – HJRW
    Nov 10, 2010 at 3:50
  • 6
    $\begingroup$ The way I've heard it, "classical" means "it was known when I was in grad school". $\endgroup$ Nov 10, 2010 at 4:04
  • 7
    $\begingroup$ @Henry: "classical" means "before the arXiv". $\endgroup$ Nov 10, 2010 at 5:37
15
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ On reflection, I suppose that also follows from the result of Dixon. Still, this is another way to think about it. $\endgroup$
    – HJRW
    Nov 10, 2010 at 2:03
  • $\begingroup$ 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$? $\endgroup$ Nov 10, 2010 at 4:14
  • $\begingroup$ Ross - er, no. Eg $J(n)=2$ (which also satisfies part 2). $\endgroup$
    – HJRW
    Nov 10, 2010 at 4:28
  • $\begingroup$ Perhaps this is the point of confusion: 'function' in this context just means 'set map'. $\endgroup$
    – HJRW
    Nov 10, 2010 at 14:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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