Normalizing group intersection problem

From Groupprops
Jump to: navigation, search

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

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


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.


We are required to determine a generating set for G_1G_2.

Relation with other problems

Problems that reduce to it

Problems it reduces to

Actually, the solution that we describe for this problem works for the more general mutually permuting group intersection problem.


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_1G_2 \geq G_1G_2^{(1)} \geq G_1G_2^{(2)} \ldots G_1G_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_1G_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_1G_2^{(i)} and use that to manufacture a generating set of G_2 \cap G_1G_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_1G_2^{(i)} to manufacture a generating set of G_2 \cap G_1G_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_1G_2^{(i)} (by taking union with the generating set for G_1).
  • From this, obtain a membership test for G_1G_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_1G_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_1G_2^{(i)}
  • Using these to construct membership tests for G_1G_2^{(i)} -- note that this again requires the use of Schreier-Sims for each group of the form G_1G_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_1G_2^{(i)} and compute a generating set for G_2 \cap G_1G_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).