GSoC 2016 Week 1
Hi everyone. Here is a brief summary of what we have been doing for the first week of GSoC.
In last week we opened the PR #11140 for working on implementing the Finitely Presented Groups and Coset Enumeration. Implementing the Coset Enumeration first understanding how the routine mentioned in [1] interact with each other. Since The different routines being: define
, scan
, coincidence
, merge
, rep
. Most of these methods have different versions as well, which can be made to be suitable for a particular class of groups.
Coset Table
: We represented it using list of lists data structure, inner lists are of fixed length, twice the number of generators, the outer list can grow as much as needed. We started with writing code for the define
, scan
routines. There was one typo in [1] for scan
routine, which I somehow intuitively passed initially while writing code from pseudocode, but came across it when reading the pseudocode again. (I didn’t expected the book to contain such a type in pseudocode). Intially we started with 1
as an entry for undefined slots but since 1
may lead to problems as Python will accept it as an index with no error indications, allowing the bugs to pass silently. So we chose None
as a better option to opt for.
We wanted to make sure, these implemeted methods work as expected, so I wrote extensive tests (currently in doctests), 4 of which have been taken from [1] while one from the original Todd Coxeter paper [2].
Just yesterday we decided to make Coset Table
a class
, since every Coset Table
in itself has certain attributes which are changed along the execution of the Enumeration, which can be better represented by a class
. It’s struture is be something like
class CosetTable(list): def __init__(self, fp_grp, subgroup): self.fp_group = fp_grp self.subgroup = subgroup self._A = list(chain.from_iterable((gen, gen**1) for gen in self.fp_group.generators)) self.append([None]*len(self.A)) @property def is_complete(self): for coset in self: for res in coset: if res is None: return False return True # other methods
On the other side we are working on PR#11150, which deals with implementation of FreeAbelianGroup
, it wouldn’t be tough to get along with this PR, since it is just similar to the previously implemented FreeGroup
, with dict
as its data structure.
For next week

Complete the
Coset Table
PR, i.e implement the different strategies of Felsch, HLT. I am pretty sure, this task would take more than 1 week, since there are whole lot of other strategies which if we decide to implement would take up a lot of time, even theLookahead
version of Todd Coxeter is there, which specifies a whole new datastructure for different compoents involved in Enumeration. 
Later, implement different methods for
FpGroup
.
Anyway, I’m really enthusiastic about my project and hope that we’ll have some nice and reasonably fast algorithms in CGT by the end of the summer!
References

Derek F. Holt, Bettina Eick, Bettina, Eamonn A. O’Brien, “Handbook of computational group theory”, Discrete Mathematics and its Applications (Boca Raton). Chapman & Hall/CRC, Boca Raton, FL, 2005. ISBN 158483723 .

A practical method for enumerating cosets of a finite abstract group by J. A. TODD (University of Manchester), and H.S.M. Coxeter (University of Cambridge)