When is the product of two permutations cyclic?

Question

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.

Answer 1

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