checking that a group is $A_n$ or $S_n.$

Question

Suppose I have two (random) permutations of $[n].$ We know (Dixon, Babai) that they almost surely generate $A_n$ or $S_n$ (if both even, then $A_n,$ otherwise $S_n.$) But the question is: what is the best (theoretical or practical) algorithm to check that the generated subgroup really is one of those big groups?

Answer 1

The algorithm described in Seress' book (and also in Section 4.2, page 81 of "Handbook of Computational Group Theory" by Holt, Eick and O'Brien) is one of the best examples of a Monte-Carlo algorithm.

It is very fast (almost linear time), and its output is either "yes, the group generated is definitely $A_n$ or $S_n$" or "the group is almost certainly not $A_n$ or $S_n$. It is extremely simple to describe and program, although of course it has to be justified theoretically.

It can be given an error probability $\epsilon$ as input, which means that the probability of a false negative is less than $\epsilon$.

It works as follows. Let $G = \langle \alpha,\beta \rangle$ be the input group. First check that $G$ is transitive (that's easy) - if not, answer no.

Now choose a collection of $N(n,\epsilon)$ (pseudo)random elements $g \in G$, where $N(n,\epsilon)$ is a function to be defined below. (There are good ways of choosing random elements, which I won't go into here - the Product Replacement Algorithm is used in practice.) For each $g$ compute all powers of $g$ that have prime order $p$. If one of these is a $p$-cycle with $n/2 < p < n-2$ then, by a theorem of Jordan, $G = A_n$ or $S_n$, and so we return the answer yes. If none of them have this property then return the answer probably no.

The probability estimate for the false negative is based on a result (Lemma 10.2.3 of Seress' book) that the proportion of elements of $A_n$ and $S_n$ that power to a $p$-cycle with $n/2 < p < n-2$ is at least $$\sum_{p\ {\rm prime},\ n/2<p<n-2}\frac{1}{p},$$ which is approximately $\log(2)/\log(n)$.

Choose $c(n)$ such that this proportion is at least $c(n)\log(2)/\log(n)$ (for example, we put $c(n)=0.34$ for $8 \le n \le 16$ and $c(n) = 0.57$ for $n>16$) and then let $d(n) := c(n)\log(2)/\log(n)$. Then, setting $N(n,\epsilon) = -\log(\epsilon)/d(n)$ gives the required error probability.

To be precise, if the group really was $A_n$ or $S_n$, then the probability of choosing $N(n,\epsilon)$ random elements without finding one that powers to a $p$-cycle with $n/2<p<n-2$ is less than $\epsilon$.

Theoretically, the weakest part of the method is the difficulty of choosing genuinely random elements, but that is not a serious obstacle in practice, because Product Replacement works very well when the group is $A_n$ or $S_n$.

I should perhaps add that the standard Schreier-Sims algorithm for computing the order of $G$ runs in polynomial-time (and it has various refinements that make it run faster in practice) , so you can use that to verify a negative answer if you want to.