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  interact with each other. Since The different routines being:
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
scan routines. There was one typo in  for
scan routine, which I somehow intuitively passed initially while writing code from pseudo-code, but came across it when reading the pseudo-code again. (I didn’t expected the book to contain such a type in pseudo-code). 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  while one from the original Todd Coxeter paper .
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
dict as its data structure.
For next week
Coset TablePR, 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 the
Lookaheadversion of Todd Coxeter is there, which specifies a whole new data-structure for different compoents involved in Enumeration.
Later, implement different methods for
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!
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 1-5848-372-3 .
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)