GSoC 2016 Week 1

May 29, 2016 • Gaurav Dhingra

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 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 [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 the Lookahead version of Todd Coxeter is there, which specifies a whole new data-structure 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

  1. 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 .

  2. 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)