Generalized set-stabilizer problem

This article describes a group-finding problem, that is, a problem where we have to explicitly find a generating set of a group that is specified through certain conditions

This problem is polynomial-time equivalent to the following basic problem: set-stabilizer problem

Description

Given data

• A group $G$ acting faithfully on a finite set $S$, is specified by a generating set $A$ (each element of $A$ is expressed as a permutation).
• We are given a colouring $C$ of $S$, viz a map from $S$ to $\{1,2,3,\ldots ,|S|\}$ where each $i$ in the range set is viewed as a colour

Goal

We need to find a generating set for the group $Stab_{G}(C)$, viz the group of elements of $G$ which preserve the colouring $C$, or equivalently, which stabilize each colour class of $S$.

Idea=

The idea is to break the group as a union of cosets, and try to find the set of elements which stabilize the colouring in every coset. For this, we thus need to solve the problem of finding the stabilizer of the coloouring $C$ in a coset. More precisely, the idea is:

• Suppose we have solved the problem for a particular subgroup $H$ of $G$. That is, we have a generating set $A$ for $Stab_{H}(C)$.
• Then, write: $G=\bigcup _{i}H\tau _{i}$
• For each coset $H\tau _{i}$, find out whether there is an element in the coset that stabilizes the colouring. If there is no such element, $H\tau _{i}\cap Stab_{G}(C)$ is empty. If there is such an element (say $\sigma$, then $H\tau _{i}\cap Stab_{G}(C)=Stab_{H}(C)\sigma$).
• Pick the $\sigma$s for all the relevant cosets, and combine all of these with the generating set $A$.
• Hence, obtain a generating set for $Stab_{G}(C)$. Now, trim this generating set down using any of the filters to obtain a small generating set.

Thus, the problem could be solved if we were able to do the following:

• Find a series of subgroups where the index at any successive pair is polynomially bounded
• Find a way to solve the problem of determining whether there is an element in a coset which stabilizes the given colouring, and which concretely gives such an element if it exists.

The first of these is solved by means of a structure tree. The second problem is solved by using the following idea. Think of each coset of $H$ as a union of cosets of $Stab_{H}(C)$. Now it is true that there will be at most one coset of $Stab_{H}(C)$ that will be of relevance. It thus suffices to check a representative of each such coset.

Solution outline

1. Construct a structure forest for the group's action (viz a disjoint union of structure trees).
2. It suffices to solve the problem separately for each structure tree. Hence, assume without loss of generality that the action is transitive.
3. Now, use the structure tree to obtain a chain of subgroups of the group, each being maximal in its successor
4. Now inductively find the generalized set-stabilizer in each subgroup. While finding the set-stabilizer in a particular subgroup, find the stabilizer in every coset of the smaller subgroup, by using what we have inductively learnt.

The only problem with this general solution outline is that in the general structure tree, the index of the normal core of the maximal subgroup may not in general have small value. To ensure this, we need special additiona assumptions on the structure of $G$.