Commutator subgroup-finding 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.

A group $G$ in $U$ is specified by a generating set $A$.

Goal

We need to find a generating set for the commutator subgroup of $G$, whose size is bounded as a polynomial in the size of the generating set for $G$ and the logarithm of the size of $G$.

Relation with other problems

Problems that reduce to it

• Solvability testing problem: Here, we need to check whether the given group (specified in terms of its generating set) is solvable. The idea is to repeatedly take the commutator subgroup and check whether we reach the trivial subgroup after finitely many steps.
• Perfectness testing problem: Here, we need to check whether the commutator subgroup equals the whole group. To do this, after computing the commutator subgroup, we simply invoke the membership testing problem to check whether every generator of the original group lies inside the commutator subgroup.

Solution

Idea

The following are the steps:

• Consider the set of all commutators $[x,y]$ where $x,y\in A$. Let us say these generate a subgroup $H$ of $G$.
• Now, invoke the normal closure-finding problem to find the normal closure of $H$ within $G$. This is precisely the commutator subgroup of $G$.

Note that this generalizes to solve the problem of finding the commutator subgroup of any two normal subgroups -- find the commutators of pairs of generator elements, and then take the normal closure.