Skip to content

GSoC 2015 Application: Representing Groups in Terms of Finite Applications

Jump to bottom Edit New page
jennifercw edited this page Mar 18, 2015 · 5 revisions

Project Proposal Information

**Proposal Title (*):** SymPy - Representing Groups in Terms of Finite Presentations
**Proposal Abstract (*):** A proposal to improve the current handling of groups in SymPy by implementing the functionality to represent groups using finite presentations, algorithms for working with groups in this form, and the ability to convert from this form to SymPy's current permutation representation in the case of finite groups.

Aim

In general, there are three approaches to representing groups for the purposes of computation: as permutations of a finite set, as groups of matrices over a ring and as groups defined by some finite presentation. The former of these is used in SymPy at present to represent a limited number of groups. My aim in this project would be to allow SymPy to represent groups defined by a finite presentation. This particularly opens up the possibility of dealing with infinite groups. I aim to implement a basic module for dealing with groups of this form, implementing basic features such as coset enumeration and to investigate how this will integrate with the existing handling of groups in SymPy (for example, the possibility of using the Todd-Coxeter algorithm to determine a permutation representation of a finite group presentation and thus use the existing group infrastructure of SymPy). If possible, I would also like to be open to the possibility of implementing the computation of Galois Groups.

##**Why?**

Algebra is the area of maths that I have focused on throughout my degree including many modules focusing on groups and their properties. I think that groups are very exciting objects to work with and it would be hugely beneficial to have the structures available to allow us to work with them in SymPy. In addition to this, if there was some focus on Galois groups, this may allow the solving module to improve solving of polynomial equations with order greater than 4 through the use of Galois Theory. I find problems such as finding normal subgroups or character tables quite interesting computationally and I feel that I would enjoy working on this problem.

##How? Given symbolic generators and relations, I will first generate the free group for these generators and then take the quotient by the relations. This is the same as the procedure used in GAP [1] . I will implement the Todd-Coxeter algorithm as described in Handbook of Computational Group Theory [ [2] ] (https://github.com/sympy/sympy/wiki/GSoC-2015-Application:-Representing-Groups-in-Terms-of-Finite-Applications#references) for coset enumeration. As described in the book, this can enable us to convert to permutation representation.

###Example Use

>> a, b = symbols('a b', commutative=False)
>> G = PresentationGroup([a, b], [a**2, b**4, b*a*b*a])
>> D = DihedralGroup(4)
>> H = G.permutation_rep()
>> H == D
True

##Estimated Schedule

Start: May 25th 2015

Finish: August 24th 2015

Duration: 13 weeks

Week one

  • Gathering of all necessary research and detailed pseudocode plan of initial implementations
  • Begin coding for FreeGroup class to compute the free group of given generators

Weeks Two to Three

  • Continued work on class, creating and running tests
  • Aim to have submitted pull request for this code at the end of week three

Weeks Four to Five

  • Implement class to represent groups represented by finite presentations
  • Write tests
  • Submit pull request at end of week five

Weeks Six and Seven

  • Implement Todd-Coxeter algorithm
  • Aim to submit pull request for this at the end of week seven

Weeks Eight and Nine

  • Investigate and implement conversion from finite presentation group to permutation group
  • Aim to submit pull request for this at the end of week nine

Weeks Nine to Eleven

  • Investigate and implement calculation of normal subgroups
  • Aim to submit pull request at the end of week eleven

Week Twelve

  • Slightly reduced amount of work time due to holiday
  • Begin implementation of computation of Galois Groups

Week Thirteen

  • Finish Galois Groups
  • Do any necessary tidying up of the code
  • Ensure all tests working

#Personal Background ##University Information

  • University(*): University of Warwick
  • Major(*): Mathematics and Physics
  • Current Year and Expected Graduation date(*): Current Year: 3rd Year Expected Graduation: July 2016
  • Degree(*) (e.g. BSc, PhD): MMathPhys (Integrated Undergraduate Master's Degree)
  • Current Average Mark: 77%
  • Expected Classification: First Class
  • Relevant Modules: Scientific Programming modules working in C; Linear Algebra; Groups and Rings; Mathematics by Computer, using Matlab; Groups and Representations; Commutative Algebra; Galois Theory; Advanced Linear Algebra

##Other Background Information

###General Background and Experience

  • Maths and Physics student with enthusiasm for Computer Science and developing software;
  • Experience as an EMEA STEP Intern at Google during summer 2014 working on the Text-to-Speech team;
  • While at Google, worked on a prototype of a prosody tool over 12 weeks with a partner intern;
  • Experience documenting, commenting and maintaining code to industry standard in a large collaborative database;
  • Experience programming in Python, C++, C, Java, Matlab;
  • Proficient in LaTeX;
  • Experienced in both individual and collaborative projects;
  • Experience with UNIX;
  • Experience using Windows, Ubuntu and Raspbian.

##Programming Background

###General Experience with Programming:

  • Experienced in Python, C++, C, Java, Matlab;
  • Experience of collaborative work whilst working at Google;
  • Used Google’s internal version control system;
  • Experience of maintaining code and documentation to industry standard;
  • Experience of using code written by others;
  • Created a prosody tool for Text-to-Speech synthesis while at Google;
  • Created some basic games and experimental maths tools as personal projects;
  • Three modules of Scientific Programming in C and Matlab.

###Python:

  • Self-taught Python during Summer 2013;
  • I work in IDLE for basic work as I find it to be the most nicely integrated with the language and the most natural. I use Anaconda for anything using NumPy, SciPy or SymPy as it is designed with this sort of work in mind and I feel that it works well;
  • I love the intuitiveness of the Python language and the elegant construction of its structures;
  • I feel that Python’s list comprehension is an excellent example of this as it allows a list to be constructed in such a simple, concise and intuitive way;
  • The dynamic nature of the language allows for much more flexible working than something like C;
  • I enjoy using Python as a problem-solving language as it allows me to experiment with various methods easily and without having to worry about some of the more technical aspects;

#References [1] - http://www.gap-system.org/Manuals/doc/ref/chap47.html
[2] - Holt, D., Eick, B. and O'Brien, E. (2005). Handbook of computational group theory. Boca Raton: Chapman & Hall/CRC.

Add a custom footer
Add a custom sidebar
Clone this wiki locally