Subnormalizing group intersection problem

This article describes a group-finding problem of the following form: two groups are given (by means of their generating sets) and we need to find a generating set for their intersection

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}$ . We are also given that $G_{1}$ is a subnormalizing subgroup for $G_{2}$ , or in other words, $G_{1}$ is a subnormal subgroup in the subgroup generated by $G_{1}$ and $G_{2}$ .

Goal

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

Relation with other problems

Problems that reduce to it

Subnormal-and-arbitrary group intersection problem: This is the problem of determining the intersection of a subnormal subgroup and an arbitrary subgroup. Since a subnormal subgroup subnormalizes every subgroup, the problem clearly reduces to the subnormalizing group intersection problem.
Normalizing group intersection problem: Since the condition of being normalizing is clearly stronger than the condition of being subnormalizing, the normalizing group intersection problem easily reduces to the subnormalizing group intersection problem.

Solution

Idea

The idea is to use the solution approach that we already saw for the normalizing group intersection problem, by the fact that every subnormal subgroup has a subnormal series. There are thus two steps:

Write a subnormal series for $G_{1}$ in the subgroup $<G_{1},G_{2}>$ , say something of the form:

$G_{1}=K_{r}\triangleleft K_{r-1}\triangleleft K_{r-2}\triangleleft \ldots \triangleleft K_{0}=<G_{1},G_{2}>$

Suppose inductively that we have computed $M_{i}=G_{2}\cap K_{i}$ . Then we can try computing $G_{2}\cap K_{i+1}$ by computing $M_{i}\cap K_{i+1}$ . To do this, appeal to the normalizing group intersection problem.

Writing the subnormal series

To write a subnormal series for a subgroup known to be subnormal, we use the following fact:

Consider the descending chain $K_{i}$ defined as follows: $K_{0}=G$ and $K_{i+1}$ is the normal closure of $H$ in $G_{i}$ . Then, there exists an $n$ for which $G_{n}=H$ . The smallest such $n$ is termed the subnormal depth of $H$ . The decreasing sequence $K_{i}$ where $K_{0}=G$

Clearly, the above gives a canonical choice for a subnormal series.

Computing the above subnormal series simply requires repeated invocation of the normal closure-finding problem, which in turn relies on the membership testing problem. Since the membership testing problem can be solved for all the groups involved, we are in good shape.

Inductively computing the intersection

Let $M_{i}$ denote $G_{2}\cap K_{i}$ . Clearly $M_{0}=G_{2}$ which is explicitly known to us, and $M_{r}=G_{1}\cap G_{2}$ which is what we want to find. Thus, it suffices if we can get $M_{i+1}$ from $M_{i}$ .

First, observe that:

$M_{i+1}=K_{i+1}\cap M_{i}$

Note that both $K_{i+1}$ and $M_{i}$ are contained in $K_{i}$ , hence the subgroup generated is contained inside $K_{i}$ . Further, since $K_{i+1}\triangleleft K_{i}$ , it will also be normal in the subgroup generated with $M_{i}$ . In other words, $K_{i+1}$ normalizes $M_{i}$ , and we can invoke the normalizing group intersection problem.

Analysis of running time

PLACEHOLDER FOR INFORMATION TO BE FILLED IN: [SHOW MORE]