Group intersection problem

This article describes the subgroup operator computation problem for the subgroup operator: [[subgroup intersection]]

This problem is polynomial-time equivalent to the following basic problem: Set stabilizer problem

This article describes a problem in the setup where the group(s) involved is/are defined by means of an embedding in a suitable universe group (such as a linear or a permutation group) -- viz in terms of generators described as elements sitting inside this universe group

Description

Given data

Our universe is some group $U$ (such as a linear group or a permutation group) in which products and inverses can be readily computed.

Two groups $G_{1}$ and $G_{2}$ in $U$ are specified by means of their generating sets $A_{1}$ and $A_{2}$.

Goal

We are required to determine a generating set for $G_{1}$ ∩ $G_{2}$.

Relation with other problems

Problems that can be solved using it

• Set-stabilizer problem: This problem asks us to compute, for a group $G$ acting faithfully on a set $S$, the set-stabilizer of a subset $T$ of $S$ within $G$. Here, $G$ is given by a generating set $A$ of permutations.

The set-stabilizer problem reduces many-one to the group intersection problem as follows: the set stabilizer of $T$ in $G$ is the intersection of $G$ with the set-stabilizer of $T$ in $Sym(S)$. The latter group is simply $Sym(T)$ × $Sym(S-T)$.

• Graph-automorphism finding: This problem asks us to compute the automorphism group of a graph. Graph-automorphism finding has a many-one reduction to the set-stabilizer problem, and hence, by the transitivity of many-one reductions, it has a many-one reduction to the group intersection problem.

• Graph isomorphism: The decision problem of graph isomorphism can be solved using graph-automorphism finding, and hence, using the group intersection problem.

Easier problems

• Normalizing group intersection problem: This can be solved for permutation groups
• Subnormalizing group intersection problem: This can also be solved for permutation groups