GSoC Week 5

Hi everyone. Here’s a brief summary of 5th week of my GSoC.

The term “low” is used to indicate the impracticalness of solving the problem for large $N$ values. The Handbook [1] contains the necessary pseudo code for its implementation, in which it has been explained in a top-down approch instead of the usual bottom-up approach.

Complexity of the algorithm: exponential.

Status update: completion of Low Index Subgroup algorithm. The main function for calling the algorithm is low_index_subgroups with signature (G, N, Y=[]), here $G$ is the group for which we want to find the subgroups for, $N$ being a positive integer specifying the upper bound on the index value of subgroup generated, and $Y$ is optional argument specifying.

This routine also (coset_enumeration_c to needed this) makes use of calling cyclic conjugates of cyclic reductions of a set of relators, so I made a method in CosetTable named conjugates, which does this task now. We have a list $S$, which stores the coset tables for the founds subgroups. The algorithm later calls a routine called descendant_subgroups. One of the things being that in low_index_subgroups the descendant_subgroups routine can be called on any of the generators of inverse of generator of group $G$, though this isn’t clear in the Handbook, but I some intuition to it.

descendant_subgroups($C$, ${R_{1x}^C }$, $R_2$, $N$)

try_descendant($C$, ${R_{1x}^C}$, $R_2$, $N$, $\alpha$, $x$, $\beta$)

Here is an example of Low Index Subgroup algorithm in work, Yay :) !!

>>> from sympy.combinatorics.free_group import free_group
>>> from sympy.combinatorics.fp_groups import FpGroup, low_index_subgroups
>>> F, x, y = free_group("x, y")
>>> f = FpGroup(F, [x**2, y**3, (x*y)**4])
>>> L = low_index_subgroups(f, 10)
>>> for i in L:
...     print(i.table)

[[0, 0, 0, 0]]
[[0, 0, 1, 2], [1, 1, 2, 0], [3, 3, 0, 1], [2, 2, 3, 3]]
[[0, 0, 1, 2], [2, 2, 2, 0], [1, 1, 0, 1]]
[[0, 0, 1, 2], [3, 3, 2, 0], [4, 4, 0, 1], [1, 1, 5, 4], [2, 2, 3, 5], [5, 5, 4, 3]]
[[1, 1, 0, 0], [0, 0, 1, 1]]
[[1, 1, 0, 0], [0, 0, 2, 3], [4, 4, 3, 1], [5, 5, 1, 2], [2, 2, 5, 6], [3, 3, 6, 4], [7, 7, 4, 5], [6, 6, 7, 7]]
[[1, 1, 1, 2], [0, 0, 2, 0], [3, 3, 0, 1], [2, 2, 4, 5], [5, 5, 5, 3], [4, 4, 3, 4]]
[[1, 1, 2, 3], [0, 0, 4, 5], [5, 5, 3, 0], [4, 4, 0, 2], [3, 3, 5, 1], [2, 2, 1, 4]]

Things I would love to have for this algorithm is to give, a presentation in the form Magma gives the subgroup returned in the form of generators of subgroup. That is coding the Reidemeister Schreier and its variant algorithms.