2
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ What's to stop you from taking $q$ to be $p^{-1}$? $\endgroup$ – Gerry Myerson Jul 3 '14 at 5:42
  • $\begingroup$ If q is p_1, the product pq is the identity which is certainly not cyclic. $\endgroup$ – TwinPrimes Jul 3 '14 at 5:44
  • 3
    $\begingroup$ Then I guess I don't know what you mean by cyclic. But, anyway, if there is a cyclic element $x$ in $S_n$, what's to stop you from taking $q$ to be $p^{-1}x$? $\endgroup$ – Gerry Myerson Jul 3 '14 at 5:51
  • $\begingroup$ You're right, I fixed an error in my original statement and added clarification of what a cyclic permutation is. $\endgroup$ – TwinPrimes Jul 3 '14 at 6:11
  • 1
    $\begingroup$ Ah, so it's what the rest of us call an $n$-cycle. $\endgroup$ – Gerry Myerson Jul 3 '14 at 9:19
1
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ For C' a subset of C the n cycles, one issue is how big C'C is: this might give a clue how big pC intersect C is. Any thoughts on how big a transversal T is with T contained in C? $\endgroup$ – The Masked Avenger Jul 4 '14 at 17:21
  • $\begingroup$ @TheMaskedAvenger: Not quite sure what you mean by "transversal" in this context, could you explain ? $\endgroup$ – TwinPrimes Jul 12 '14 at 16:00
  • $\begingroup$ It would be great if you could choose a simple set H so that for any q and p with distinct inverses in H, and C the set of n-cycles, that pC and qC were disjoint: you could then get a smaller H that way. If C were a subgroup, then find coset representatives of C, and you're done. This is not the case. For some p, pC intersect C can be large. How large? Depends on p. Another way to see this is to ask which p are in CC (since C is closed under inverse). A transversal C' is a subset of C that does a good job of covering C by translates, and indirectly relates to how small an H you can get. $\endgroup$ – The Masked Avenger Jul 12 '14 at 16:23
  • $\begingroup$ It appears that $CC = A_n$ (see arxiv.org/pdf/math/0303036.pdf) $\endgroup$ – TwinPrimes Jul 12 '14 at 18:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.