9.1 Families of Groups

The question raised in the introduction is whether there exist families of examples whose members behave uniformly. That is, given such a family one can select a combination of one strategy and one ordering which is optimal for all members of this family. While it is not quite probable that such a family exists there might exist families whose members are similar enough that the selected strategy and ordering are pretty good for all the members while not being the best.

If such families exist then one could try to learn how to enumerate cosets for members of this family efficiently using the following procedure. Compute some 1000 combinations for a small member, pick those performing best plus some randomly chosen, and compute larger examples using these combinations. Of course, this is only a good idea if the computation of such a large set is feasible and one of the following two situations is met. First, if a large problem is intractable using the available resources. Then finding an optimal solution for a smaller example seems the best way to find a combination which makes it possible to treat the large one. Second, if more than one problem of a family is to be solved, using the best combinations can reduce the total time to find the solutions. Otherwise, it would be more reasonable to compute the examples directly choosing different combinations of strategies and orderings by hand.

The Macdonald groups $G(n, m)$ (see also [6]) which form a syntactic family were analyzed in order to see if they are a family with respect to coset enumeration, too. They are generated by $\{ BAbaBabA^n, ABabAbaB^m \}$ and seem to behave better in the following sense. They all have finite index though only a very bad approximation of the index is known:

$${\sf index}(G(n, m)) \quad \vert \quad 27 \cdot (n - 1) \cdot (m - 1) \cdot (gcd(n, m))^8$$

But for $n = 2$ the following holds:

$$\forall m: {\sf index}(G(2, m)) = m-1$$