Timeline for recognition of symmetric groups in GAP
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 18, 2017 at 15:12 | comment | added | Jay Taylor | @FriederLadisch Thanks for the details. Apologies if my second comment wasn't clear. I was saying what the function does for a general group, i.e., possibly not a permutation group. In this case I think my comment is accurate. I should have made that clearer. I'd seen it invokes IsNaturalSymmetricGroup first, for permutation groups, but couldn't figure out exactly what that was doing. Thanks for finding where that function is defined. | |
| Nov 18, 2017 at 1:00 | comment | added | Mikhail Tikhomirov | Schreier-Sims-like algorithm could possibly work reasonably fast on groups of this order, assuming the action is known. With the obtained coset representation, it is a field day to check basically any property of a permutation group. | |
| Nov 17, 2017 at 22:26 | comment | added | Frieder Ladisch | (A comment in the GAP-code refers to Seress, Permutation group algorithms, Section 10.2.) | |
| Nov 17, 2017 at 22:22 | comment | added | Frieder Ladisch | 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$. | |
| Nov 17, 2017 at 17:27 | vote | accept | Vladimir Dotsenko | ||
| Nov 17, 2017 at 17:27 | comment | added | Vladimir Dotsenko | @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. | |
| Nov 17, 2017 at 16:02 | comment | added | Jay Taylor | 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'. | |
| Nov 17, 2017 at 15:39 | comment | added | Jay Taylor | 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. | |
| Nov 17, 2017 at 15:37 | answer | added | Igor Rivin | timeline score: 12 | |
| Nov 17, 2017 at 15:26 | history | asked | Vladimir Dotsenko | CC BY-SA 3.0 |