10. Coset Enumeration over General Groups

In Section 2 we explained, that instead of studying the index of the subgroup generated by $U \cup N(R)$ in $\mathcal{F}$ for $R = R_1 \cup R_2$ we can instead study the index of the subgroup generated by $U \cup N(R_2)$ in $\mathcal{G}_1$ where $\mathcal{G}_1$ is the group generated by $<\Sigma, R_1>$, respectively $<\Sigma, \widetilde{R_1}>$. This is done in this section by choosing relators from $R$, i.e. splitting $R = R_1 \cup R_2$, and then trying to complete $R_1$ with respect to the ordering chosen using the Knuth-Bendix completion procedure. When this can be done successfully, Gröbner basis techniques in more general group rings can be applied. For example, provided the relators are of the form $\sigma^{n}$, where $\sigma \in \Sigma$ and $n \in \mathbb {N}$, we can use the Knuth-Bendix completion procedure to get a finite, convergent presentation of the underlying group. For the examples $(2, 5, 7; 2) \vert E$, $G^{3, 7, 17} \vert <ab, c>$, $PSL_2(11) \vert E$, $(2, 3, 7; 7) \vert E$, $M_{11}^{(1)} \vert <a>$, $(2,8 \vert 2,3) \vert <a^2, a^{-1}b>$, $Neu \vert <a, c>$ and $G^{3,7,16}\vert E$ all relators having this form were used to define the new respective groups $\mathcal{G}_1$ (see Table 2).

Table 2: Presentations of the Groups used for the Examples

Group	$R_1$	$R_2$
$(2, 5, 7; 2)$	$a^2 = b^5 = 1$	$(ab)^7 = [a, b]^2 = 1$
$G^{3, 7, 17}$	$a^3 = b^7 = c^{17} = 1$	$(ab)^2 = (bc)^2 = (ca)^2 = (abc)^2 = 1$
$PSL_2(11)$	$a^{11} = b^2 = 1$	$(ab)^3 = (a^4bA^5b)^2 = 1$
$(2, 3, 7; 7)$	$a^2 = b^3 = 1$	$(ab)^7 = [a, b]^7 = 1$
$M_{11}^{(1)}$	$a^{11} = b^5 = c^4 = 1$	$(a^4c^2)^3 = (bc^2)^2 = (abc)^3 = BabA^4 = CbcB^2 = 1$
$(8, 7 \vert 2, 3)$	$a^8 = b^7 = 1$	$(ab)^2 = (Ab)^3 = 1$
$Neu$	$a^3 = b^3 = c^3 = 1$	$(ab)^5 = (Ab)^5 = (ac)^4 = (aC)^4 = aBabCacaC = (bc)^3 = (Bc)^4 = 1$
$G^{3,7,16}$	$a^3 = b^7 = c^{16} = 1$	$(ab)^2 = (bc)^2 = (ca)^2 = (abc)^2 = 1$

The results for the modified coset enumeration using completed group presentations for the respective $<\Sigma, R_1>$ are tabulated in Appendix E. Notice, that each ordering may yield a different complete set of relators $\widetilde{R_1}$ for a given set of relators $R_1$. As for all other examples computed, there is no uniform behaviour detectable. The combination of ordering, framework, and additional elements strategy influences whether the results are better or worse compared to the coset enumeration modulo the free group.

The example $(2, 5, 7; 2) \vert E$ in general gives better results than before, that is, fewer cosets are enumerated. The best result is now 45/45 cosets enumerated maximal/total for syl-l-abAB and I-ALL compared to 143/143 for kbo-A and NONE.

For $G^{3, 7, 17} \vert <ab, c>$ on the other hand we get worse results, that is for most combinations more cosets have to be enumerated. The best result now is 913/1045 cosets enumerated maximal/total for syl-l-CcBbAa and P-R compared to 821/867 for kbo-a and P-ALL.

For $PSL_2(11) \vert E$ we get optimal results for all orderings combined with strategy NONE. All other combinations are equally good or better, with two exceptions, namely strategy I-R combined with the syllable ordrings.

For $(2, 3, 7; 7) \vert E$ we get better results for most combinations but the are quite some combinations which behave worse. The best result improved to 1092/1103 cosets enumerated maximal/total for kbo-B and NONE compared to 1105/1566 for kbo-A and P-R.

For $M_{11}^{(1)} \vert <a>$ most combinations are worse and only a few are better. The best result which was already optimal remained the same.

For $(2,8 \vert 2,3) \vert <a^2, a^{-1}b>$ we have almost as many combinations which are better as those which are worse. The best result improved to 448/549 cosets enumerated maximal/total for syl-l-abAB and I-R compared to 766/773 for kbo-A and NONE.

For $Neu \vert <a, c>$ holds the same. The best result improved to 560/656 cosets enumerated maximal/total for syl-l-CcBbAa and NONE compared to 1637/1671 for ll-CcBbAa and I-R.

For $G^{3,7,16}\vert E$ again we have a mix of better and worse combinations. The best result improved to 30949/42538 cosets enumerated maximal/total for ll-abcABC and P-ALL compared to 43931/56621 for syl-l-CcBbAa and P-ALL. But it is still worse than the best results for Felsch. Nevertheless, we are about as good as the default strategy of Felsch type.

Overall, we have the same problem as before. We have no hints about which combination to choose to get good results for the coset enumeration process. Nevertheless, we have an additional parameter to further improve this process. It should be noted, that we also have the choice not to add all of the relators having the form $\sigma^n$. That is, we can move only some of them or even other relators, provided that there exists a finite and convergent presentation of the underlying group.

For example, in Appendix E.3 the results for the example $G^{3, 7, 17} \vert <ab, c>$ are tabulated but this time we split the set of relators $R$ into $R_1: a^3 = b^7 = 1$ and $R_2: c^{17} = (ab)^2 = (bc)^2 = (ca)^2 = (abc)^2 = 1$. This was inspired by the fact that $c$ is one of the generators of the subgroup. As before some combinations yielded better results some worse. The best result was 911/995 cosets enumerated maximal/total for kbo-C and P-ALL and lies between the best result for the standard enumeration, which was 821/867 for kbo-a and P-ALL, and the best result for the first modified enumeration, which is 913/1045 for syl-l-CcBbAa and P-R.