# Algorithm for finding intersection of two groups from generators

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?

• 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? Commented Jun 12 at 20:57
• 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. Commented Jun 12 at 21:33

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.