Group intersection PTIME equals set-stabilizer

This article gives the statement, and possibly proof, of a polynomial-time equivalence between two computational/decision problems in computational group theory (or related areas such as graph theory

Statement

The group intersection problem for subgroups of the permutation group is polynomial-time equivalent to the set stabilizer problem.

Definitions of the problems

Group intersection problem

Here, two subgroups $G_{1}$ and $G_{2}$ of the symmetric group on a set $S$ are specified by means of generating sets $A_{1}$ and $A_{2}$ , and we need to find a small generating set for $G_{1}$ ∩ $G_{2}$ .

Set-stabilizer problem

Here, we have a set $S$ and a group $G$ acting on $S$ . Let $T$ be a subset of $S$ . We need to find the subgroup of $G$ comprising those elements which stabilize $T$ as a set.

Proof

Set stabilizer reduces to group intersection

Consider the data $(G, S, T)$ as given for the set stabilizer problem. Now, send the following data to the group intersection problem:

Set $S$ to be the same as the $S$ for the set stabilizer problem
Set $G_{1} = G$
Set $G_{2} = S y m (T)$ × $S y m (T^{c})$ viz $G_{2}$ is the stabilizer of $S$ in the whole of the symmetric group

Note that $G_{2}$ is actually a group with a very small generating set (a generating set of size 4).

The output given by this problem is precisely the same as the set stabilizer of $S$ in $G$ .

Note that this is a many-one reduction.

Group intersection reduces to set stabilizer

Consider the data $(G_{1}, G_{2}, S)$ as given for the group intersection problem. Consider the set $S^{2}$ with $G_{1}$ acting on the first coordinate and $G_{2}$ acting on the second coordinate.

Then send the following data to the set stabilizer problem:

Set $S$ of the set stabilizer problem to $S^{2}$
Set $G$ of the set stabilizer problem to be $G_{1}$ × $G_{2}$
Set $T$ of the set stabilizer problem as the set of diagonal elements in $S^{2}$

The set stabilizer of $T$ is thus precisely those pairs of elements $(g, h)$ such that for every $s$ in $S$ , $g . s = h . s$ . This forces the set stabilizer of $T$ to comprise only elements of the form $(g, h)$ where $g = h$ , which forces the set stabilizer to be the diagonal subgroup of $G_{1}$ ∩ $G_{2}$ × $G_{1}$ × $G_{2}$ . Finding a generating set for this diagonal subgroup is the same as finding a generating set for $G_{1}$ ∩ $G_{2}$ .