3
$\begingroup$

I have a certain family of subsets of $S_n$, and I'd like to know which subsets in this family generate $S_n$. What techniques exist for solving this type of problem?

Are there any known results on necessary or sufficient conditions for a subset of $S_n$ to generate $S_n$? Anything on calculating the order of the subgroup generated by a subset?

$\endgroup$
  • $\begingroup$ I hope this question isn't too broad, but I'm not sure how to narrow it down. $\endgroup$ – Jack M Jun 8 '16 at 14:02
  • 1
    $\begingroup$ Without knowing more, what comes to mind is to look at the classification of maximal subgroups of $S_n$; if your subset does not generate $S_n$, it must be contained in one of these. The following paper (Liebeck, Praeger, Saxl) seems to have such a classification sciencedirect.com/science/article/pii/0021869387902237 building on the O'Nan--Scott Theorem. $\endgroup$ – Denis Chaperon de Lauzières Jun 8 '16 at 14:43
  • 4
    $\begingroup$ Are you looking for theoretical results, or for an algorithm? There is a fast Monte-Carlo algorithm for verifying that $\langle S \rangle = S_n$. $\endgroup$ – Derek Holt Jun 8 '16 at 17:12
  • 2
    $\begingroup$ For general algorithms for computing $|\langle S \rangle|$ you could start by searching for "Schreier-Sims algorithm". $\endgroup$ – Derek Holt Jun 8 '16 at 17:20
  • 1
    $\begingroup$ To build on Derek Holt's comment, Bratus and Pak math.ucla.edu/~pak/papers/recfin.pdf give such an algorithm. $\endgroup$ – David E Speyer Jun 9 '16 at 13:51
8
$\begingroup$

Let $X$ be a subset of $S_n$. I suppose that the size of $X$ is small compared to the order of $S_n$. In order to quickly check whether $X$ generates $S_n$ I would do the following: For $k=1,2,3\dots$ check whether the group generated by $X$ is $k$-fold transitive. That is a cheap test: Let $\Gamma$ be the graph whose vertices are the $k$-tuples of distinct elements from $\{1,2,\dots,n\}$. Connect two vertices by an edge if an element from $X$ moves one vertex to the other one. Then the group generated by $X$ is $k$-transitive if and only if $\Gamma$ is connected, which is algorithmically easy and cheap to test.

If $X$ passes the test up to $k=6$, then you know that the generated group is $A_n$ or $S_n$, because there are no other $6$-transitive groups. Deciding between these two cases is a matter of checking the signum of the elements from $X$.

In most degrees $n$, there are no $2$-transitive groups besides $A_n$ or $S_n$, so of course you can stop with $k=2$.

Remark 1 (addressing Derek Holt's comment): Indeed, the number of $6$-tuples gets unmanageably large quickly. Instead of $k$-tuples, one can work with $k$-sets. By Kantor's 1972 paper on $k$-homogeneous groups, a $k$-homogeneous group where $k\ge5$ is $k$-transitive. So except for $n=24$ we have to look at $5$-sets at worst. Of course, certainly there are much more efficient methods available.

Remark 2 (addressing Denis Chaperon de Lauzières' comment): Right, while the algorithm is cheap, the proof of its correctness isn't. The OP didn't tell whether he wants to check many small degree cases (say $n\le30$), or some high degree cases. In the former case, one of course does not need the classification of the finite simple groups in order to classify the highly transitive permutation groups.

$\endgroup$
  • 1
    $\begingroup$ This doesn't seem a cheap test to me. The number of ordered $6$-tuples of $\{1,2,3,\ldots,n\}$ is large. $\endgroup$ – Derek Holt Jun 8 '16 at 17:19
  • $\begingroup$ It is also not mathematically cheap, since it depends on the classification of finite simple groups, but this method has at least one recent brilliant application in the work of Alexei Entin on the large finite field case of the Bateman-Horn conjecture. (Here $k$-transitivity is obtained by theoretical means related to the problem itself and the Chebotarev density theorem). $\endgroup$ – Denis Chaperon de Lauzières Jun 8 '16 at 18:16
4
$\begingroup$

One method that often works is the following: A primitive group, which contains a $p$-cycle for a prime $p<n-2$ is $A_n$ or $S_n$. If a permutation $\pi$ contains a cycle of length $p$, and no other cycle of length divisible by $p$, then some power of $\pi$ is a $p$-cycle, and the proportion of permutations having this property tends to 1. So if you have information on the cycle structure of your permutations, and are a little bit lucky, then generation of $S_n$ is the same as generation of a primitive group. From an algorithmic point of view primitivity is not a good property, but often imprimitivity can be ruled out by simple ad hoc arguments.

$\endgroup$

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.