Testing permutations to see if they generate $S_n$

Question

Alright, so a similar question was recently asked about the theoretical bound for generating certain permutations in polynomial time. I had been thinking about a related problem in algorithms (with applications to a specific problem in graph theory - namely, discrete moves of sets of points among the vertices of a graph) and H A Helfgott's question inspired me to ask here.

Suppose I have some "black box" that spits out permutations $\rho_i \in S_n$. I know the following things about the permutations it spits out:

• $\rho_i$ is of cycle type $(k_i,1,1,\cdots,1)$.
• This "black box" is fast in $n$ (linear in $n$ or so, maybe plus a few log terms).
• If I run this black box long enough, it will spit out all of the $k$-cycles in some subgroup $H \subseteq S_n$. I don't know what $H$ is a priori, although I can tell you (based on other constraints of the general problem) if $H \subseteq A_n$.

Let $G \subseteq S_n$ be the group generated by the $\rho_i$. (Note that $G$ may not in fact be either $H$ or $S_n$.)

I'd like to test if $A_n \subseteq G$.

1. Is there a computationally efficient test to see if the $\rho_i$ act primitively on $[1,n]$? I want to say that if they act transitively and if the $k_i$ do not all share some nontrivial factor, they act primitively, but I am not sure of this.
2. Assuming that the answer to (1) is yes, I can guarantee that the natural action of $G$ on $[1,n]$ is transitive and primitive. Does this guarantee that $G = A_n$? If not, what computationally non-intensive criterion do I need to add to guarantee that $G = A_n$?

Note: right now my algorithm for solving this problem is somewhere in that scary, scary territory beyond $O(n!)$ (yeah, that's how I'm testing to see if the darn thing is the alternating group), so any polynomial-time algorithm here would be super-awesome.

Answer 1

The answer to (1) is yes, primitivity can be checked in O(n^3) time and practical computer implementations have been widely available for decades. See Butler's Fundamental Algorithms for Permutation Groups p.76 for this and various related algorithms (such as testing transitivity) explained in a friendly manner. Holt et al.'s Handbook of Computational Group Theory also contains this material in textbook form. GAP contains open-source implementations of most of the algorithms mentioned (for instance IsTransitive and IsPrimitive would be useful).

The answer to (2) is usually yes, since proper primitive groups do not tend to contain many k-cycles. You are just looking for what are called "giant tests" that can be applied to your restricted setting. Some old theorems of Jordan can be used for this in ways that are described in Seress's Permutation group algorithms, especially 10.2.1 and 10.2.2. These are refined to give probabilistic runtime estimates, some of which you could probably use if your black box had a (vaguely) known probability distribution. See also Holt's textbook and GAP's DoSnAnGiantTest.

Section 3.3 of Dixon–Mortimer's book also contains results which can be used (with other results) to rule out "small" k. In some ways this is done in section 5.3 and 5.4: if k is smaller than √n, then G contains the alternating group.

Be careful about your guarantee in (2). In particular, can you tell if H is transitive and primitive from the graph? If you are only gathering information from the group G, then be careful that G may not be transitive even if H is (where G is generated by all of the elements of H that happen to be cycles).