7
$\begingroup$

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?

Improve this question
$\endgroup$
7
  • 4
    $\begingroup$ The beauty about GAP is that it's open source, so you can just look up the code. A quick grep of the source code shows the command is defined in the file 'grpnames.gi' in the lib folder. It seems to check whether the derived subgroup is an alternating group using the command 'IsAlternatingGroup', which is defined in the same file. $\endgroup$
    – Jay Taylor
    Commented Nov 17, 2017 at 15:39
  • $\begingroup$ As far as I can tell from the source its general method for an arbitrary group $G$ is as follows: see if $G$ is finite, see if $[G,G]$ is simple by determining normal closures of conjugacy classes, see if $G \cong \mathrm{A}_n$ with $n\in \{5,6\}$ by ad-hoc methods, now check if $|G| = n!/2$ for some $n\geqslant 7$, then by CFSG we have $G \cong \mathrm{A}_n$. Checkout the command 'IsomorphismTypeInfoFiniteSimpleGroup' in 'grp.gi'. $\endgroup$
    – Jay Taylor
    Commented Nov 17, 2017 at 16:02
  • $\begingroup$ @JayTaylor I don't think that the program could possibly compute the order of the group directly, without knowing the answer. All the groups I have been working with are too big for that. It is more plausible that an algorithm like Igor Rivin describes in his answer is used. $\endgroup$
    – Vladimir Dotsenko
    Commented Nov 17, 2017 at 17:27
  • 3
    $\begingroup$ The function IsSymmetricGroup checks whether a group is isomorphic to some symmetric group (so may return true even for a matrix group). The function IsNaturalSymmetricGroup checks whether a given subgroup is in fact all of $S_n$. But for a subgroup of $S_n$, IsSymmetricGroup first invokes IsNaturalSymmetricGroup... The implementation of the latter function is in the file 'gpprmsya.gi', and Igor Rivin's answer seems to be rather accurate: Check transitivity, and try to find randomly a $p$-cycle with $n/2 < p < n-2$. $\endgroup$
    – Frieder Ladisch
    Commented Nov 17, 2017 at 22:22
  • $\begingroup$ (A comment in the GAP-code refers to Seress, Permutation group algorithms, Section 10.2.) $\endgroup$
    – Frieder Ladisch
    Commented Nov 17, 2017 at 22:26

1 Answer 1

Reset to default
12
$\begingroup$

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, Random Struct. Algorithms 49, No. 3, 409-428 (2016). ZBL1349.05337.

Improve this answer
$\endgroup$
7
  • 5
    $\begingroup$ Deciding between $A_n$ and $S_n$ is not a matter of luck: just check whether any of the given generators is odd. $\endgroup$
    – Noam D. Elkies
    Commented Nov 17, 2017 at 15:47
  • 2
    $\begingroup$ @Igor Rivin you wrote that "You rule out $A_n$ by randomly generating an odd permutation". But for a subgroup generated by a given subset $S$ of $S_n$, the subgroup is contained in $A_n$ iff $S$ is, which can be tested without "randomly generating" anything. $\endgroup$
    – Noam D. Elkies
    Commented Nov 17, 2017 at 18:00
  • 1
    $\begingroup$ @NoamD.Elkies Yes, of course. I was thinking of a slightly different problem (finding the Galois group of a polynomial), so did not reboot properly :) $\endgroup$
    – Igor Rivin
    Commented Nov 17, 2017 at 18:26
  • 1
    $\begingroup$ @NoamD.Elkies I fixed it, at last. $\endgroup$
    – Igor Rivin
    Commented Nov 17, 2017 at 21:04
  • 4
    $\begingroup$ If $p=2^r-1$ is a Mersenne prime, then the image of the embedding of $PGL_2({\mathbf F}_{2^r})$ in $S_{p+2}$ determined by the natural action on $1$-spaces contains a $p$-cycle. So, it seems that you need a cycle of prime order at most $n-3$. $\endgroup$
    – John Shareshian
    Commented Nov 17, 2017 at 22:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .