MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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. – Derek Holt Apr 27 '12 at 8:30
Thank you for your help :) – Lwins.Gafield Apr 27 '12 at 11:47
@Derek: poly time in what? The size of output? – Igor Rivin Apr 27 '12 at 15:42
@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. – Derek Holt Apr 27 '12 at 21:28

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.