10
$\begingroup$

Say I have two subgroups of $S_n$ defined from their generators. E.g. $G_1 = \langle (0 3 4 1), (0 3 2 1 4)\rangle$ and $G_2 = \langle (4)(0 2 3 1), (0 4 3 2 1)\rangle$. Their intersection can be written in terms of three generators: $G_1\cap G_2 = \langle (0 1 4 3), (0 4)(1 3), (0 3 4 1)\rangle$.

Of course one can find the intersection by generating all elements of $G_1$ and $G_2$. But is there a faster way, assuming each group has just a small number of generators?

$\endgroup$
2
  • $\begingroup$ If I compute a base and/or strong generating set using Schreier–Sims algorithm, can I just naively take the intersection of those as my new generators? $\endgroup$ Commented Jun 12 at 20:57
  • $\begingroup$ I also read some of math.colostate.edu/~hulpke/CGT/cgtnotes.pdf and it says you can find the stabalizer of the product group of $G_1, G_2$, that stabilizes the diagonal. But I'm not sure how that's actually easier that finding the intersection. $\endgroup$ Commented Jun 12 at 21:33

1 Answer 1

8
$\begingroup$

There is a backtrack algorithm for this problem, which is described in detail in Section 4.6.6 of "Handbook of Computational Group Theory" by Holt, Eick and O'Brien, or in Section 9.1.2 of "Permutation Group Algorithms" by Akos Seress. It works fast for groups of moderate size, but its complexity is exponential in general. I don't think that having a small number of generators is helpful - it's hard to see why it should be.

It is not known whether this problem is solvable in polynomial time. I think Babai proved that it is quasi-polynomial but not with a practical algorithm. Incidentally the problems of intersections of subgroups, centralizers of elements, and stabilizers of subsets of $\{1,\ldots,n\}$ have been proved (by Eugene Luks) to be polynomially equivalent.

$\endgroup$
1
  • $\begingroup$ Thank you. Those are great references. As far as I can understand sympy.subgroup_search implements the SUBGROUPSEARCH function described in your book. I guess this means I can't do much better than just G∩H = G.subgroup_search(H.contains), though I assume this makes at least |G∩H| calls to T.contains? $\endgroup$ Commented Jun 12 at 22:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .