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