# Testing permutations to see if they generate $S_n$

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.

• Since you mention the runtime of your black box, I'll assume it's an unknown algorithm rather than an oracle. Do you know that you control all inputs to your black box? Do you know the black box to be deterministic? Do you know how long is long enough (to get all the k-cycles in H)?
– user5810
Sep 12, 2010 at 3:20
• @Ricky: The black box is a randomized algorithm. This is really a problem on a graph $G = (V,E)$ with $|V| = n$, and the black box has running time something like $|V| log |E|$. Since the black box is randomized, there isn't an upper bound on generating everything in $H$. Sep 12, 2010 at 4:54
• So, wouldn't it be "Almost surely, if you this black box long enough, it will spit out all of the k-cycles in some subgroup H⊆Sn."?
– user5810
Sep 12, 2010 at 5:31
• Many properties of permutation groups can be computed in polynomial time. See ams.org/notices/199706/seress.pdf and gap-system.org/Manuals/doc/htm/ref/CHAP041.htm. GAP has IsPrimitive function to test whether a given group acts primitively on a given set. Sep 12, 2010 at 11:05
• @Ricky Yes, but I don't want to wait that long. :) @Tsuyoshi Thanks! Sep 12, 2010 at 15:28

• @Jack Thanks for the great answer. The black box's probability distribution is unfortunately tied in a complex manner to the structure of the graph. And yes, I can guarantee transitivity either from the permutations or from the graph. I haven't a good estimate on the runtime of the graph-based algorithm, though, whereas I know the permutation-based algorithm is at most quadratic in $n$. Sep 12, 2010 at 15:34