Call a subset $H \subset S_n$ "simple" if for every $q \in S_n$, there is some $p \in H$ such that $pq$ is cyclic (i.e. consists of a single cycle of length $n$).

Is there some characterization known of either simple on non-simple subsets ? I'm interested in any computational techniques for implementing a fast test. In my case $n$ is in the range 10..20 and the sets are not large -- 50 elements at most but there are a large number of them -- around 400M and computing products of each with the full symmetric group is prohibitive. Thanks.

In my case the identity permutation is always a member of the candidate subsets $H$ so we can make that assumption if it is useful. Let $C \subset S_n$ be the set of cyclic permutations. As @Aaron observes below, the criterion is equivalent to $CH = S_n$ and $H$ must have at least $n$ elements. We see also that $H$ must include at least one cyclic permutation in order to cover the identity and also, if $H$ is simple, so is $pHp^{-1}$.

As an example, for $n = 3$, $S_n = \{I, p_1, p_2, p_3, p_4, p_5\}$ where $p_1 = (12), p_2 = (01), p_3 = (012), p_4 = (021), p_5 = (02)$, there are 6 simple sets which include $I$: $H_1 = \{I, p_1, p_2, p_3\}$, $H_2 = \{I, p_1, p_2, p_4\}$, $H_3 = \{I, p_1, p_3, p_5\}$, $H_4 = \{I, p_1, p_4, p_5\}$, $H_5 = \{I, p_2, p_3, p_5\}$, $H_6 = \{I, p_2, p_4, p_5\}$.

For $n = 4$, the smallest simple set (containing $I$) has 6 elements and there are 36 of them. But what is interesting here is that $|H| > 18 \implies H$ is simple. Not sure how to go about deriving a tight upper bound like this for non-simple sets in the general case but it would obviously yield a very quick test for all sufficiently large sets.

3more comments