2
$\begingroup$

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?

$\endgroup$
3
  • 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, 2012 at 8:30
  • $\begingroup$ @Derek: poly time in what? The size of output? $\endgroup$
    – Igor Rivin
    Apr 27, 2012 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, 2012 at 21:28

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.