Test if a finite group is a symmetric group algorithmically

Question

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?

Answer 1

The goal should be to do it in time $O(n!^2)$, which is the size of the input (the multiplication table).

First determine the partition of $G$ into conjugacy classes. This can be done efficiently with a union-find-type data structure. Check that there is a conjugacy class $C$ of cardinality $\binom n2$ consisting of involutions.

Make $C$ into a graph by defining $g_1 \sim g_2$ for $g_1, g_2 \in C$ if $g_1$ and $g_2$ do not commute. If $G$ is truly a copy of $S_n$ then $g_1$ and $g_2$ are transpositions and this relation means their supports are not disjoint. Find a maximal clique $K$ in $C$ of size greater than $3$. Check that $K$ has cardinality $n-1$.

Compute the normalizer $H = \{g \in G: K^g = K\}$. Check that $H$ has index $n$. Check that $H$ has trivial normal core.

If any check failed, reject isomorphism. If all checks passed then $G$ has a subgroup $H$ of index $n$ with trivial normal core, so the action of $G$ on the cosets of $H$ defines a homomorphism $G \to S_n$ with trivial kernel, hence an isomorphism.

Answer 2

By the Coxeter presentation of the symmetric group, a homomorphism $S_n \to G$ can be described equivalently as a sequence of elements $s_1,\dotsc,s_{n-1} \in G$ such that $$s_i^2 = 1,\, (s_i s_{i+1})^3 = 1,\, s_i s_j = s_j s_i \text{ if } |i-j| > 1.$$ If $G$ is of order $n!$, the homomorphism is an isomorphism if and only if it is injective. By List of symmetric group elements from the usual presentation this can be checked as follows: setting $t^j_i = s_{j-1} s_{j-2} \cdots s_i$ for $1 \leq i \leq j \leq n$, build the elements $t^1_{a(1)} t^2_{a(2)} \cdots t^n_{a(n)}$ of $G$ for $1 \leq a(i) \leq i$, and verify that they are pairwise distinct (equivalenty, that they cover all of $G$).

Pseudocode:

# generator yielding all isomorphisms S_n ---> G
isomorphisms_from_symmetric_group(n,G):
  if order(G) == n! yield from monomorphisms_from_symmetric_group(n,G)

# generator yielding all monomorphisms S_n ---> G
monomorphisms_from_symmetric_group(n,G):
  involutions := list of all g in G with g^2 = 1, g != 1
  for all mappings s : [1,...,n-1] -> involutions:
    if the following are true:
      (1) s(i)^2 = 1 for all i
      (2) (s(i) * s(i+1))^3 = 1 for all i
      (3) s(i) commutes with s(j) for all i,j with i < j-1
      (4) is_injective(s,G)
    then yield s

# returns true iff the homomorphism S_n ---> G, (i i+1) |-> s_i is injective
is_injective(s,G):
  n := length(s) + 1
  elements := []
  t(i,j) := s(j-1) * ... * s(i)  
  for every sequence a(1),...,a(n) with 1 <= a(i) <= i:
    add t(a(1),1) * .... * t(a(n),n) to elements
  return length(elements) == n! 
    

Answer 3

Combining the two answers gives something faster than the input size of the table. If we imagine an "oracle" type of problem, where we have functions that can invert, multiply, or sample from the group, then we can do an algorithm like this.

1. Iterate through all the all elements and check if $x^2=1$. Put all such order-2 elements in a list $S$. If there are not exactly $n!$ elements in the entire group, reject (meaning $G$ is not isomorphic to $S_n$). $S$ will be all products of disjoint transpositions.
2. Iterate through the group again and compute all conjugacy classes of $S$. Each conjugacy class will represent elements with a different number of disjoint transpositions.
3. There should be one conjugacy class of size $\binom{n}{2}$, and this will contain all the transpositions. Look for elements that form the Coxeter representation. This can be done in time $O(n^4)$, I think (find a sequence of disjoint transpositions, distinguishable because they commute with each other, then look for the transpositions "in between").

If this process terminates with a Coxeter representation, then $G\cong S_n$, otherwise it is not.

The runtime is dominated by step 2. I think $\vert S\vert = O(\sqrt{n!})$, so in the worst-case step 2 runs in time $\tilde{O}(n!^{\frac{3}{2}})$ (by computing the conjugate of every element in $S$ by every element in $G$).

I suspect there are ways to show that step 2 is even faster, since there should only be $n/2$ conjugacy classes.

I'm really curious about whether there are probabilistic algorithms less than $\Theta(n!)$ time. Randomly sampling should give even-order elements with constant probability (?) and then we can generate an order-2 element from those.