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 '10 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$. – dvitek Sep 12 '10 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 '10 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. – Tsuyoshi Ito Sep 12 '10 at 11:05
• @Ricky Yes, but I don't want to wait that long. :) @Tsuyoshi Thanks! – dvitek Sep 12 '10 at 15:28

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

• @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$. – dvitek Sep 12 '10 at 15:34
• @drvitek: No problem, sounds good. If you need better definitions of "small", then there are improvements in the journal literature. Theorem 2 of Liebeck-Saxl 1991 ams.org/mathscinet-getitem?mr=1114511 shows that if k is smaller than n/3, then either G contains the alternating group or it is contained (nicely) in a specific product-action wreath product of symmetric groups acting on subsets. The second case would mean H would have a lot of alternating groups as minimal subnormal subgroups, so might be easy to rule out some other way. For H≥An and G nice, the books should be enough. – Jack Schmidt Sep 12 '10 at 17:10
• Sorry, the results for primitive groups containing a cycle are much stronger than I claimed: if 2 ≤ k ≤ n−6, then G contains An. Most of the results I mentioned earlier are for permutations that move at most k points. At any rate, so "small" is k ≤ n−6, and you can get away with k ≤ n−4 as long as n ≥ 25. – Jack Schmidt Sep 12 '10 at 18:24