Computing a transversal of a subgroup $H$ of $G$ in expected $O(|G : H|^2 \log |G : H| + |H|)$ time

Question

I have the book "Handbook of Computational Group Theory", by Derek Holt, and in it is a section on finding the transversal of a subgroup. Recall a transversal of a subgroup $H$ of $G$ is a single representative from each of the cosets of $H$ in $G$ (either left or right cosets). Two methods are given to find a transversal without any theoretical guarantees, mentioning at worst case they involve a backtrack search through the elements of $G$.

I'll admit I have not studied the algorithms mentioned thoroughly, as there is a fair amount of prerequisite material regarding strongly generating sets and bases. However, the initial claim of requiring a full backtrack search through $G$ seems unnecessary with an appropriate sized subgroup $H$ if you allow a bit of randomness in your algorithm.

Namely, there are $O(|G : H|)$ different cosets that need a single representative. Randomly sampling from $G$ can be seen as an application of coupon collecting. After $O(|G : H| \log |G : H|)$ many samples, the expectation is that all cosets have been represented. To trim this to a proper transversal, we can keep a list of unique cosets and run the coset test as we sample elements, maintaining only one representative of each unique coset and stopping when $|G : H|$ representatives have been found.

To do this efficiently requires storing the elements of $H$ in a dictionary. With $O(1)$ time lookup, the above algorithm can be completed in $O(|G : H|^2 \log |G : H| + |H|)$ time, though it could possibly be made to be more efficient. In any case, if $H$ is $o(|G|)$ and $\omega(\sqrt{|G|})$, then this algorithm is more efficient than a backtrack search through $G$.

The algorithm is pretty obvious, so I'm wondering why it's not mentioned in the book. Also, if there are any other good sources for transversal computation I would like to hear them. Thanks.

Answer 1

I guess I should try and answer that!

I don't really have a good answer to the question of why the random method is not mentioned in the book, and I would agree that it might to be the fastest method if you simply want to compute and store a complete transversal.

I guess the point is that in many applications you want to do something a little different from that, and the two methods described in the book are geared towards two different types of applications.

The first method described allows you to seach through the transversal elements in a well-defined order, without needing to store any of them. You would use that if you were looking for an element with a certain property. It is particularly suitable if the index of the subgroup is large, and storing a complete transversal would cause storage space problems on your computer.

The second method described has larger storage overheads (although you don't need to store the complete permutations in the transversal - the transversal elements can be stored more efficiently in a tree-like structure), but the data structures computed allow you to identify the coset representative of a given group element quickly. Sois this is particularly suitable if you also want to compute the action of the group by multiplication of the cosets of the subgroup, which is a very frequent application. Finding a transversal using random methods might be quicker, but it would not be suitable for this application.

It is also worth mentioning that although these algorithms both involve backtrack searches, in practice the difficulties tend to arise from large output size when the index if big rather than from the backtrack search. In other words, it is $|G:H|$ that is the significant term in the complexity, and so the $|G:H|^2$ factor in the complexity estimate for the random method might make it slower in examples with large index. (In particular, I am very sceptical about your claim that the random method is more efficient for subgroups of order about $\sqrt{|G|}$.)

Interestingly random methods are used a lot in practice when searching for double coset representatives of two subgroups, but in that case they suffer from the problem that the double cosets do not all have the same size, and representatives of the smaller double cosets can be hard to find.

Answer 2

Apparently I can't comment because I don't have a "high enough reputation", but I wanted to add... You don't have to store the elements of H in a dictionary if you have a characterization of H that lends itself to an easy check of whether a given permutation is in H. Also, I believe that a common problem in CGT, which I'm not sure if the author addresses, is that sets as containers that implement insertion and removal, etc., are hard to implement if, like the elements of a factor group set, they do not have unique representations. This would greatly affect the time-complexity of the random search method, as well as others for the same or other problems.