Normalizing 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 normalizing subgroup for $G_{2}$, viz every element of $G_{1}$ normalizes the subgroup $G_{2}$ of $U$.

Goal

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

Solution

The underlying descending chain

We have the goal of computing $G_{1}\cap G_{2}$. First, consider the descending chain of subgroups:

$G_{2}\geq G_{2}^{(1)}\geq G_{2}^{(2)}\geq \ldots \geq G_{2}^{(n-1)}$

Here, $G_{2}^{(i)}$ denotes the subgroup of $G_{2}$ comprising permutations that fix the first $i$ elements in the set. In other words $G_{2}^{(i)}=G_{2}\cap Stab_{1,2,...,i}(Sym(S))$.

Multiplying all terms by $G_{1}$:

$G_{1}G_{2}\geq G_{1}G_{2}^{(1)}\geq G_{1}G_{2}^{(2)}\ldots G_{1}G_{2}^{(n=1)}=G_{1}$

Each of these is a subgroup because $G_{1}$ normalizes every element of $G_{2}$.

Now, intersect each member of this descending chain with $G_{2}$, to get:

$G_{2}\geq G_{2}\cap G_{1}G_{2}^{(1)}\geq \ldots G_{2}\cap G_{1}$

Now notice that at each stage (intersection the pointwise stabilizer with <math.G_2</math>, multiplying with $G_{1}$, and again intersecting with $G_{2}$, the index does not increse. Since we know that $[G_{2}^{(i)}:G_{2}^{(i+1)}]\leq n-i$, we conclude that even in the final descending chain, the indices are bounded by $n-i$.

The idea is now to start from a generating set of $G_{2}\cap G_{1}G_{2}^{(i)}$ and use that to manufacture a generating set of $G_{2}\cap G_{1}G_{2}^{(i+1)}$.

The outline for doing that

We now need to justify how, at each step, we can use a generating set for $G_{2}\cap G_{1}G_{2}^{(i)}$ to manufacture a generating set of $G_{2}\cap G_{1}G_{2}^{(i+1)}$.

First, do the following:

• Using the Schreier-Sims algorithm (in a white box fashion) compute generating sets for all the $G_{2}^{(i)}$s.
• From this, thus compute generating sets for all the groups $G_{1}G_{2}^{(i)}$ (by taking union with the generating set for $G_{1}$).
• From this, obtain a membership test for $G_{1}G_{2}^{(i)}$ (use here the fact that the membership testing problem can be solved for permutation groups).
• Using this and the membership test for $G_{2}$, obtain a membership test for $G_{2}\cap G_{1}G_{2}^{(i)}$ for every $i$.

Now that we have membership tests for everything in the descending chain, we can use the method for finding a generating set from a membership test, one by one at each step of the chain.

Note the following:

• At each step of the chain, the index is bounded by $n$. Hence, the size of the new generating set is at most $n$ times that of its predecessor.
• We can apply a filter at each step to make sure that the overall size of the generating set remains bounded.

Analysis of running time

Time for the preprocessing:

• One application of Schreier-Sims algorithm
• Using these to get generating sets for $G_{1}G_{2}^{(i)}$
• Using these to construct membership tests for $G_{1}G_{2}^{(i)}$ -- note that this again requires the use of Schreier-Sims for each group of the form $G_{1}G_{2}^{(i)}$

The critical step is thus the third step. Since Schreier-Sims can be done in $O(n^{6})$, and this step involves the application of Schreier-Sims about $n$ times, and hence it comes to $O(n^{7})$.

Time for computing the actual generating sets: Here we start with a generating set for $G_{2}\cap G_{1}G_{2}^{(i)}$ and compute a generating set for $G_{2}\cap G_{1}G_{2}^{(i+1)}$. This again needs to be done $n$ times. For each time we do this, we need to d othe following:

• Compute coset representatives: This can take as much time as the current generating set times $n^{2}$
• Use coset representatives to find a generating set for the smaller subgroup: This can take as much time as the current generating set times $n^{2}$
• Trim the generating set using the Sims filter: This can take as much time the current generating set times $n^{3}$.

Thus, if the current generating set is always kept to a size at most $n^{2}$, we get a bound of $O(n^{6})$ on this step.

The overall bound for the normalizing group intersection problem is thus $O(n^{7})$.