Normalizing 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
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
Our universe is some group (such as a linear group or a permutation group) in which products and inverses can be readily computed.
We are required to determine a generating set for ∩ .
Relation with other problems
Problems that reduce to it
- Normal-and-arbitrary group intersection problem: This is the problem of finding a generating set for the intersection of two subgroups, one of which is known to be normal
Problems it reduces to
- Group intersection problem: This is the problem of finding a small generating set for the intersection of any two arbitrary subgroups
- Mutually permuting group intersection problem: This is the problem of finding a small generating set for the intersection of two subgroups given that one of them permutes with every subgroup of the other.
- Subnormalizing group intersection problem: This is the problem of finding a small generating set for the intersection of two subgroups given that one of them is subnormal in the subgroup generated by both of them.
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 . First, consider the descending chain of subgroups:
Here, denotes the subgroup of comprising permutations that fix the first elements in the set. In other words .
Multiplying all terms by :
Each of these is a subgroup because normalizes every element of .
Now, intersect each member of this descending chain with , to get:
Now notice that at each stage (intersection the pointwise stabilizer with <math.G_2</math>, multiplying with , and again intersecting with , the index does not increse. Since we know that , we conclude that even in the final descending chain, the indices are bounded by .
The idea is now to start from a generating set of and use that to manufacture a generating set of .
The outline for doing that
We now need to justify how, at each step, we can use a generating set for to manufacture a generating set of .
First, do the following:
- Using the Schreier-Sims algorithm (in a white box fashion) compute generating sets for all the s.
- From this, thus compute generating sets for all the groups (by taking union with the generating set for ).
- From this, obtain a membership test for (use here the fact that the membership testing problem can be solved for permutation groups).
- Using this and the membership test for , obtain a membership test for for every .
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 . Hence, the size of the new generating set is at most 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
- Using these to construct membership tests for -- note that this again requires the use of Schreier-Sims for each group of the form
The critical step is thus the third step. Since Schreier-Sims can be done in , and this step involves the application of Schreier-Sims about times, and hence it comes to .
Time for computing the actual generating sets: Here we start with a generating set for and compute a generating set for . This again needs to be done 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
- Use coset representatives to find a generating set for the smaller subgroup: This can take as much time as the current generating set times
- Trim the generating set using the Sims filter: This can take as much time the current generating set times .
Thus, if the current generating set is always kept to a size at most , we get a bound of on this step.
The overall bound for the normalizing group intersection problem is thus .