# How to compute commutator subgroup efficiently?

Let $G$ be a finite group of size $n$ given by table representation. Now let commutator subgroup be $[G,G] = \langle\{xyx^{-1}y^{-1}\mid x,y \in G\}\rangle$. Suppose that $a.b$ operation can be done in a $O(1)$ time. How much time does it takes to compute $[G,G]$. I can do in $O(n^2)$ ( assume that inverse of one element takes constant time ) time. Is there any faster way to do it?

Edit : Even I am not sure $O(n^2)$ will work, For all $x,y \in G$, I will be only able to find the generating set of $[G,G]$ not all the elements of commutator subgroup of $G$. I want all the elements of commutator subgroup.

• How much time does it take for the inverse calculation? $O(n)$ or $O(1)$?
– ChoF
Mar 18 '18 at 13:36
• @ ChoF You can assume in constant time.
– old
Mar 18 '18 at 13:39

Since you are assuming that you can multiply group elements in constant time, you are effectively assuming that the multiplication table of $G$ is stored in random access memory, which is reasonable for moderate sized groups, but would not be practical for groups of order more than about $10^6$. So this is not a realistic exercise.
Anyway, with that assumption you can compute $H=[G,G]$ in $O(n^2)$. First compute the set $C$ of all commutators, and initialize $H$ to $C$. We can also initialize a characteristic function vector for $H$ so that we can test group elements for membership of $H$ in constant time. That is consistent with your previous assumption.
Now multiply every element of $H$ by every element of $C$, test the results for membership in $H$ and, if an element is found that is not in $H$, then adjoin it to $H$. At the end of this process we will have $H = [G,G]$, and we have done at most $n^2$ multiplications and membership tests.
Since the input has size $O(n^2)$ you cannot expect to do better than this. But in practice, multiplication tables are not used for computations within finite groups. In general, groups are represented as subgroups of $S_n$ or of matrix groups ${\rm GL}(n,q)$ over finite fields, and you store only a generating set for the group rather than all of its elements. Finite solvable groups can be efficiently represented by power-conjugate presentations.
• If $G = \langle X \rangle$ then $[G,G]$ is the normal cloure in $G$ of the set $\{[x,y] :x,y \in X \}$. There are good algorithms for normal closure but they are complicated, and involve probabilistic estimates. Mar 18 '18 at 15:54