GSoC 2015 Application: Representing Groups in Terms of Finite Applications - gxyd/sympy GitHub Wiki

Project Proposal Information

Aim

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