Subnormalizing group intersection problem

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$.

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◃K_{r-1}◃K_{r-2}◃\dots ◃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 Failed to parse (unknown function "\triangleft"): {\displaystyle K_{i+1} \triangleft 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]

One of the people editing this page intended to fill in this information at a later stage, but hasn't gotten around to doing it yet. If you see this placeholder for a long time, file an error report at the error reporting page.