<p>The answer to the first part of your question is <em>yes</em>.</p>

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

<p>Also, this question can be solved in practice by using <strong>GAP</strong> <span class="math-container">$\texttt{IsSymmetricGroup}$</span> (<a href="https://www.gap-system.org/Manuals/doc/ref/chap43.html" rel="nofollow noreferrer">https://www.gap-system.org/Manuals/doc/ref/chap43.html</a>), which implements this method.</p>

CC BY-SA 4.0
2020-01-08T15:31:13.850Z
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$.
Emil Jeřábek
CC BY-SA 4.0
2020-01-08T14:32:00.640Z
2020-01-08T14:32:00.640Z
thibo
<ol>
<li><p>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.</p></li>
<li><p>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?</p></li>
</ol>

CC BY-SA 4.0
2020-01-07T15:02:16.797Z
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).
thibo
CC BY-SA 4.0
2020-01-07T15:12:49.947Z
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" https://link.springer.com/article/10.1007%2FBF01110210)
thibo
<gr.group-theory>
Generating set of a group and relation to diameter?
Turbo
# Generating set of a group and relation to diameter?

(Asked by: username_0 on 2019-12-17)

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?

**Tags:** gr.group-theory
> **Comments:**
> **username_1**: 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).  
> **username_1**: 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" https://link.springer.com/article/10.1007%2FBF01110210)  

---

## 1 answers

### Answer by username_1 on 2020-01-08. Score: 2

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.

> **Comments:**
> **username_2**: 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$.  

---

