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.
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?
$\begingroup$
$\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$– thiboCommented Jan 7, 2020 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$– thiboCommented Jan 7, 2020 at 15:12
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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.
-
1$\begingroup$ My reading of the manual suggests that the right function is
IsNaturalSymmetricGroup(while also checkingNrMovedPoints) rather thanIsSymmetricGroup. For example,IsSymmetricGroupshould give a false positive answer for a group generated by an arbitrary involution, as it is isomorphic to $S_2$. $\endgroup$ Commented Jan 8, 2020 at 15:31