Let $S_n$ be the set of all permutations that act on $1...n$. You are given a subset $P\subseteq S_n$, and you are to compute the size of the set $G(P) \subseteq S_n$, where $G(P)$ meets the following requirements:

  1. $G(P)$ contains the identity permutation,
  2. $P \subseteq G(P)$,
  3. $G(P)$ is closed under taking inverses and multiplications (if $a, b \in G(P)$, then $ab \in G(P)$, if $a \in G(P)$, then $a^{-1} \in G(P)$),
  4. $G(P)$ is a minimal possible set that meets requirements 1,2 and 3.

Is there a method or algorithm that can solve this?

  • 9
    $\begingroup$ So in other words $G(P)$ is the subgroup of $S_n$ generated by $P$. The principal algorithm for this (which is polynomial-time) is known as the Schreier-Sims algorithm. $\endgroup$ – Derek Holt Apr 27 '12 at 8:30
  • $\begingroup$ @Derek: poly time in what? The size of output? $\endgroup$ – Igor Rivin Apr 27 '12 at 15:42
  • 2
    $\begingroup$ @Igor: Size of input. Lwins.Gafield just asked for the order of the group, but the output is actually a data structure, known as a base and strong generating set, that tells you the order, and also allows you to test quickly whether a given permutation in $S_n$ is in $G(P)$ and, if so, to express it as a word (more precisely a Straight Line Program) in $P$. Almost all other algorithms for computing structural information about $G(P)$ make use of this data structure. $\endgroup$ – Derek Holt Apr 27 '12 at 21:28

Your Answer

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

Browse other questions tagged or ask your own question.