Welcome to MathOverflow

Question

6

2

Suppose we are given a set S of points on which two different groups G and G' (given by sets of generating permutations) act. Is there an efficient algorithm for finding generators the largest pair of subgroups H and H' of G and G' whose action on S coincide?

flag	asked Mar 17 2012 at 2:33 Maxime 177●4

2

I don't understand this question. We have two different groups $H$ and $H'$ acting on the same set $S$. What does it mean for these actions to "coinicide"? – Steven Landsburg Mar 17 2012 at 2:38

@Steven: $H$ may coincide with $H'$ even if $G\ne G'$. In general $H$ and $H'$ can act with kernels $N, N'$ and the actions of $H/N$ and $H'/N'$ may coincide (i.e. these two permutation groups may be the same). – Mark Sapir Mar 17 2012 at 2:43

3

In fact the question asks for an algorithm of finding the intersection of two subgroups of $S_n$ (I assume the set to be finite). Each subgroup is given by generating permutations. I guess the problem is NP-hard (at least). – Mark Sapir Mar 17 2012 at 2:49

I couldnt understand why this question has a vote to close and then by accident my stubby finger hit to vote to close when I was checking the reason. Sorry. This is a good question. I vote to undo my accidental vote. – Benjamin Steinberg Mar 17 2012 at 16:59

1

Benjamin Steinberg: The vote to close was mine, for the reason given in my comment above. I see now that the question is both meaningful and interesting, though I continue to believe that the wording makes it unnecessarily obscure. – Steven Landsburg Mar 17 2012 at 19:38

Mark Sapir · Accepted Answer · 2012-03-17 18:55:28Z UTC

This paper studies the (easier) problem of checking if the intersection of two subgroups of $S_n$ is trivial. In particular, it is shown that the graph isomorphism problem polynomially reduces to that problem. The converse reduction is not known. Thus the problem of checking that the intersection is trivial is at least as hard as the graph isomorphism problem. It is difficult but not known to be NP-hard.

Update Also look at this ICM talk by Babai.

Derek Holt · Answer 2 · 2012-03-17 16:34:45Z UTC

It is known that the following three computational problems for subgroups $G$ of $S_n$ are polynomially equivalent:

Computing (generators of) the centralizer $C_G(g)$ of an element $g \in S_n$ (and also testing $g,h \in S_n$ for conjugacy in $G$).
Computing (generators of) the setwise stabilizer of a subset of the set of size $n$ on which $S_n$ acts (and also testing two such subsets for being in the same orbit under $S_n$).
Computing (generators of) the intersection of $G$ with another subgroup $H \le S_n$.

As Mark says, these are all at least as difficult as graph isomorphism.

The proofs are clever but basically elementary and interesting, so I recommend them! One reference is:

E.M. Luks, ``Permutation groups and polynomial-time computation'', in L. Finkelstein and W.M. Kantor (eds.), Groups and Computation, Dimacs Series in Discrete Mathematics and Theoretical Computer Science vol. 11, American Math. Soc., 139-176, 1993.

I have just noticed that Luks has a recently published book with the same title, which I have not seen yet.

Added later: It should also be mentioned that the implementations of the above algorithms in GAP and Magma involve backtrack searches, and so are potentially exponential, but in practice they run fast for most examples of moderate degree.

Two groups acting on a set.

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.