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.



When is the product of two permutations cyclic?
**LATER** I had a few thoughts which do not lead me to change the answer below but do make me less confident in it. A more general question is: Given two subsets $A,B$ of a group $G$ (in this case $G=S\_n$), is there an efficient way to decide if $AB=\{{ab\mid a\in A,b\in B\}}=G?$ In the case below $B$ is fixed to be the set of $(n-1)!$ $n$-cycles and $A$ is any one of a large collection of sets. My answer does not use any special properties of that fixed set, though there might well be some which are relevant. If instead I fixed $B$ to be the $(n-1)!$ permutations which fix $n$ then the criterion is simple, $A$ has to have for each $i$ an element $a\_i$ which maps $i$ to $n$ (adjust depending on how you are multiplying.) In that case we have that "translations (aka cosets) $aB$ and $a'B$ are either disjoint or identical. The same is not true for the set of $n$-cycles although it is closed under inverses and conjugation.




---


I doubt that there is a simple criteria which will decide for each set if it is or is not simple. I do show (at the end) how to get by with *only* $|H|(n-1)!$ multiplications (at worst) rather than $|H|n!.$ Maybe it will be a starting idea for an improvement. 


Let $C$ be the set of all $(n-1)!$ $n$-cycles. For a given $q \in S\_n$ there $(n-1)!$ choices of $p \in S\_n$ with $pq \in C.$ Namely $p \in Cq^{-1}.$ Say that $p$ **covers** $q$ when this happens. So certainly a set with $|H| \lt n$ will not be simple. I'd think that you could pick (at random) a $q$ and then randomly build up a set $H\_1$ by at each stage finding a $q' \ne q$ which is not yet covered and then choosing a random $p$ which covers $q'$ but not $q$. Stop when only $q$ is uncovered. We may assume that removing any one element from $H\_1$ leaves at least two elements uncovered (by reducing $H\_1$ until this is true). Now make $H\_2$ by including one more thing which does cover $q$. It would seem hard to tell that $H\_1$ is not simple while $H\_2$ is.


For a variation, leave exactly two things, $q\_1$ and $q\_2$, uncovered by $H\_1$ and then make two versions of $H\_2$ with one more element, let one cover both and the other cover $q\_2$ but not $q\_1.$ Again it would seem hard to discover which is which.


There might be criteria which are effective if your sets $H$ are of some special form.




---


I'd think that in $S\_{10}$ with a random choice of $H$ with $|H|=50$ and a random $q \in S\_{10},$ that the chance that $q$ is not covered is $(1-\frac{1}{10})^{50}\approx 0.005.$ That suggests that it would be rare for all $10!=3628800$ elements to be covered. However that reasoning may not be very sound. Experiments might tell.




---


Rather than checking that each $q \in S\_n$ is covered by at least one $p \in H$, it is more efficient to check that $H$ covers all of $S\_n.$ Let $H$ be your candidate set. You want that for each $q \in S\_n$ there is at least one $p \in H$ with $pq \in C.$ In other words that $Cq^{-1} \cap H$ is never $\emptyset.$ It is equivalent to require $C^{-1}H$ does not miss any $q^{-1}$ for $q \in Q.$ Since $S\_n$ and $C$ are unchanged by taking inverses this says $$CH=S\_n.$$


This is a big improvement over checking for each $q \in S\_n$ that $Hq \cap C \ne \emptyset$ but still not very practical. One could look at $c\_1H \cup c\_2H \cup\cdots$ one set at a time as the $c\_i$ range over $C$ and stop if and when the running union is all of $S\_n.$ Optionally, if at some stage relatively few things are still uncovered (maybe less than $\frac1n$ of them), one could switch over to checking for each of those that $q^{-1}H \cap C \ne \emptyset.$


