Permutation group algorithm for abelianness testing

Summary

Item	Value
Problem being solved	abelianness testing problem: determine whether a given group is an abelian group.
Input format	Set $S=\{1,2,3,\dots ,n\}$, generating set $A$ for group $G$ of permutations on $S$.
Output format	Yes/No depending on whether $G$ is abelian

Idea and outline

The idea is to choose the algorithm based on the size of $A$. We consider three alternate algorithmic routes we could take:

Strategy	Time complexity	Condition on $\alpha$ for this to be the preferred algorithm if $|A|=O(n^{\alpha })$	Time taken in terms of $\alpha$
black-box group algorithm for abelianness testing given a generating set directly, with the generating set $A$.	$O(|A|^{2}n)$ (requires $O(|A|^{2})$ group operations, each group operation takes $O(n)$ time.	$\alpha \leq 2$	$\!O(n^{2\alpha +1})$
first use the Sims filter to reduce the size of the generating set to $O(n^{2})$, then use black-box group algorithm for abelianness testing given a generating set on the new generating set.	$O(|A|n^{2})$ (to apply the Sims fiter) $O(n^{5})$ to apply the test once the generating set is filtered.	$2<\alpha$	$\!O(n^{\max\{\alpha +2,5\}})$
first use Jerrum's filter to reduce the size of the generating set to $O(n)$, then use black-box group algorithm for abelianness testing given a generating set on the new generating set.	$O(|A|n^{4})$ to apply Jerrum's filter $O(n^{3})$ to apply the test once the generating set is filtered.	not guaranteed to be better than the Sims filter for any $\alpha$. Although the testing is fast once we've filtered, the time taken to filter is a much more critical bottleneck.	$\!O(n^{\alpha +4})$