Two groups acting on a set. - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T15:35:53Z http://mathoverflow.net/feeds/question/91439 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/91439/two-groups-acting-on-a-set Two groups acting on a set. Maxime 2012-03-17T02:33:51Z 2012-03-17T18:55:28Z <p>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?</p> http://mathoverflow.net/questions/91439/two-groups-acting-on-a-set/91440#91440 Answer by Mark Sapir for Two groups acting on a set. Mark Sapir 2012-03-17T02:57:57Z 2012-03-17T18:55:28Z <p><a href="http://www.google.com/url?sa=t&amp;rct=j&amp;q=&amp;esrc=s&amp;source=web&amp;cd=3&amp;ved=0CDIQFjAC&amp;url=http%3A%2F%2Fwww.cs.trincoll.edu%2F~miyazaki%2Fbeijing.ps&amp;ei=k_xjT863JI_NtgfZ5rT-DQ&amp;usg=AFQjCNF0S6ua5ZOz2GBOutjjsxOVBdP0KQ" rel="nofollow">This paper</a> 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 <a href="http://en.wikipedia.org/wiki/Graph_isomorphism_problem" rel="nofollow"> graph isomorphism problem</a>. It is difficult but not known to be NP-hard. </p> <p><b>Update</b> Also look at <a href="http://www.mathunion.org/ICM/ICM1990.2/Main/icm1990.2.1479.1490.ocr.pdf" rel="nofollow">this</a> ICM talk by Babai.</p> http://mathoverflow.net/questions/91439/two-groups-acting-on-a-set/91470#91470 Answer by Derek Holt for Two groups acting on a set. Derek Holt 2012-03-17T14:57:31Z 2012-03-17T16:34:45Z <p>It is known that the following three computational problems for subgroups $G$ of $S_n$ are polynomially equivalent:</p> <ol> <li><p>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$).</p></li> <li><p>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$).</p></li> <li><p>Computing (generators of) the intersection of $G$ with another subgroup $H \le S_n$.</p></li> </ol> <p>As Mark says, these are all at least as difficult as graph isomorphism.</p> <p>The proofs are clever but basically elementary and interesting, so I recommend them! One reference is: </p> <p>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.</p> <p>I have just noticed that Luks has a recently published book with the same title, which I have not seen yet.</p> <p>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.</p>