In GAP (<https://www.gap-system.org>), there is a function **IsSymmetricGroup**, which tells you whether a subgroup of $S\_n$ generated by given permutations is all of the $S\_n$. It looks like it takes virtually no time, even in large examples I tried ($n=50$). What is the method behind this function? Is it so easy to recognise symmetric groups?


On a related note, suppose that we know that $\sigma\_1$, ..., $\sigma\_k$ generate $S\_n$. Are there some economic algorithms to write some standard generators of $S\_n$, e.g. the adjacent transpositions, in terms of these sigmas?



recognition of symmetric groups in GAP
The method (I assume) uses Jordan's theorem, which says that an primitive subgroup of $S\_n$ with a cycle of prime order (at most $n-2,$ if memory serves) is either $A\_n$ or $S\_n.$ You rule out $A\_n$ by looking at the generators, you show transitivity by randomly generating an $n$-cycle (of which there are a lot, so it does not take long to find one, there are other ways, too), and you show primitivity by finding a permutation which has a $p$ cycle for $n/2 < p < n-1$ (raising it to a power, you just get the $p$-cycle. There are lots of such, so basically generating a few thousand elements will do the trick. Notice that if, after generating the few thousand elements you DO NOT find the sorts of elements you want, the group is almost surely NOT the symmetric group (but the NO answer will be probabilistic, while the YES answer will be deterministic).


For more on this subject, check out my paper with Pemantle and Peres on invariable generation of symmetric groups: *Pemantle, Robin; Peres, Yuval; Rivin, Igor*, [**Four random permutations conjugated by an adversary generate (\mathcal{S}\_{n}) with high probability**](http://dx.doi.org/10.1002/rsa.20632), Random Struct. Algorithms 49, No. 3, 409-428 (2016). [ZBL1349.05337](https://zbmath.org/?q=an:1349.05337).


