0
$\begingroup$
  1. Is there an efficient algorithm to test if a given subset of symmetric group generates the symmetric group? Drawing the Cayley graph and testing for all pairs reachability is one way however that scales in the size of the group.

  2. Is there a relation between maximum distance between generating elements where distance betwee two elements of generating elements is with respect to transpositions and diameter of Cayley graph of the group with respect to the generating set?

$\endgroup$
2
  • $\begingroup$ These questions might find more answers on mathoverflow where people doing group theory. To partially answer (1), you might first rule out some trivial cases where the answer is no by computing the signature of your permutations and check if all points are moved (ie if the group is transitive). $\endgroup$
    – thibo
    Jan 7 '20 at 15:02
  • 1
    $\begingroup$ From the theoretical side, a theorem of Jordan states that a subgroup of $S_n$ which is transitive, primitive and contains a large enough cycle is the symmetric group (see ie Dixon's article "The probability of generating the symmetric group" link.springer.com/article/10.1007%2FBF01110210) $\endgroup$
    – thibo
    Jan 7 '20 at 15:12
2
$\begingroup$

The answer to the first part of your question is yes.

Given a permutation group $G = \langle S \rangle$, there is a polynomial time algorithm (clearly more efficient than the brute force approach which has factorial complexity), the Schreier-Sims algorithm (https://en.wikipedia.org/wiki/Schreier%E2%80%93Sims_algorithm) which computes a base and strong generating set (BSGS) that can be used to compute the order of the group (hence decide if $G=S_n$). A good reference seems to be Seress' Permutation Group Algorithms and especially chapter 4.

Also, this question can be solved in practice by using GAP $\texttt{IsSymmetricGroup}$ (https://www.gap-system.org/Manuals/doc/ref/chap43.html), which implements this method.

$\endgroup$
1
  • 1
    $\begingroup$ My reading of the manual suggests that the right function is IsNaturalSymmetricGroup (while also checking NrMovedPoints) rather than IsSymmetricGroup. For example, IsSymmetricGroup should give a false positive answer for a group generated by an arbitrary involution, as it is isomorphic to $S_2$. $\endgroup$ Jan 8 '20 at 15:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.