1
$\begingroup$

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.

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

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Derek Holt
    Mar 18 '18 at 15:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.