Suppose $G$ is a finite group with $|G|=n!$ for some $n \in \mathbb{N}$. Suppose that we have the entire Cayley table of the group stored and we can perfom multiplication in the group as fast as it takes us to perform a lookup in the table.
What's an efficient algorithm to test whether $G \cong S_n$? I.e. it returns true
if $G \cong S_n$, false
otherwise. Any group theoretic object or property we may wish to find (e.g. abelianness, the centre of the group, the orders of elements, the conjugacy classes...) are all programmed in.
If desired, suppose we also have a group known as $S_n$ also within the program that we can compare to the group somehow.
Here's what I've thought of so far. Iterating through all maps $G \to S_n$ to check if it is an isomorphism would be awfully slow, since there's $(n!)^{n!}$ such maps which obviously grows incredibly fast. We may be able to reduce this if we have nice methods to find all homomorphisms, or all bijections, or whatever else, but it'd still be incredibly large.
We can rule out some groups quickly by checking certain things that are fast to compute and whether they match $S_n$ such as
- The abelianness of $G$ matches $S_n$ (i.e. $G$ non-abelian, unless $n = 2$)
- The sizes of conjugacy classes
- The orders of elements of the group
- The size of the center
- Etc.
But this would be a necessary but not sufficient condition.
So how can we improve on this?