GSoC Week 5

Jun 21, 2016 • Gaurav Dhingra

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

In the 5th week we worked upon the implementation of Low Index Subgroups algorithm. The basic problem dealt with by this algorithm is: *find all subgroups H such that the index G:H is at most a specified number N > 0.*

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.