On Gelman’s Subgroup Counting Theorem

Abstract

In a recent paper, E. Gelman provided an exact formula for the number of subgroups of a given index for the Baumslag-Solitar groups $\text{BS}(p,q)$ when $p$ and $q$ are coprime. We use Gelman’s proof as the basis for an algorithm that computes a maximal set of inequivalent permutation representations of $\text{BS}(p,q)$ with degree $n$. The computational complexity of this algorithm is linear in both space and time with respect to the index. We compare the performance of this algorithm with the Todd-Coxeter procedure, which generally lacks a polynomial bound on the number of cosets used during the enumeration process.