GSoC 2013 Application Tarang Patel: Group Theory

Name: Tarang Patel

IRC Nick: tarang

Github: Tarang1993

Background and Programming Skills

I am second year undergraduate student, pursuing my computer science engineering at DA-IICT (Dhirubhai Ambani Institute of Information and Communication Technology), India. I have a good command over python. I have been using python since two years. Mostly I prefer to code in python. My interviewstreet and codechef codes are mostly in python. Besides python, I also have good programming skills in C, C++, Java, C#, PHP, JavaScript, HTML5/CSS3. Also, I was selected among the top 15 programmers from India in a competition called National Programming League (NPL) held by National Institute of Technology (Warangal). I work on Ubuntu 12.04 distro of GNU/Linux distribution. My favourite text editor is Vim editor. Usually, I prefer to work in vim. Also, I have pretty good mathematical background for my project. I am good at mathematics and enjoy doing mathematics from my school time. Also, I had done a course on Group Theory and abstract algebra in my last semester. I have also done a course on Calculus and Discrete mathematics in my first year. All these inspired me to contribute to SymPy and to work on the project of Group Theory. Also, I think, I have mastered the basics of version control tool: git and now I can use it smoothly without much trouble.

I can be contacted any time at my email address. I remain online on IRC occasionally but will be easily available on Gmail.

Contributions to SymPy

My first PR was about adding Double Implies : https://github.com/sympy/sympy/pull/1745
I added the test case and fixed issue 1640. (Merged) : https://github.com/sympy/sympy/pull/1843

The Project

My project is about the group theory. Some parts of group theory are already implemented in SymPy during the last summer as a part of GSoC project. But still there are some things that needs to be implemented in group theory.

Hence for my GSoC project I plan to implement the things related to group theory that are lacking in combinatorics module of sympy. I feel I have the mathematical background for the project. I had done a course on Group Theory and abstract algebra in my last semester and I acquired solid understanding of concepts of group theory. I referred to the texts like: Derek F. Holt, Bettina Eick, Bettina, Eamonn A. O'Brien, "Handbook of computational group theory", Jin-Quan Chen, Jialun Ping & Fan Wang, "Group Representation Theory for Physicists", I.N. Herstein, "Topics in Algebra" 2nd ed. This motivated me to select this project and I think I can implement the lacking parts in combinatorics module for group theory.

The discussions related to this topic on mailing list including: https://groups.google.com/forum/?fromgroups=#!searchin/sympy/group$20theory/sympy/NsRAQf8O95I/MUm6xhJ1HmgJ motivated me to include the lacking concepts of Group theory in present combinatorics module of SymPy.

I plan to implement following things for Group Theory:

Presently, there is no module on Young Tableaux in sympy. I plan to implement a module on Young Tableaux. Hence, this will be useful for labeling the irreducible representations of various groups. I would also like to implement the functionality of character tables as it is still missing in sympy. Also, there is no method or functionality for Quotient group for permutation groups in sympy. I would like to implement it. I think it would be nice if we have method for the conjugacy classes that can give list of representatives of conjugacy class of groups and subgroups in permutation group. Hence, I think of implementing the support for conjugacy class representatives. Also, there is no implementation of Todd-Coxeter algorithm for coset enumeration. Hence, I would implement Todd-Coxeter algortithm which will be helpful for finding coset enumeration. Also ,it would be helpful if we have the support for Sylow p-subgroup in SymPy.

Implementation details

Since at present there is no method for finding quotient group, I would like to implement the method for quotient group in perm_groups.py. If G be the permutation group with H is its normal subgroup (gH = Hg) then the set G/H of cosets of H in G is the factor group or quotient group of H in G. The order of the quotient group is |G|/|H|. Hence, if we find the permutation group isomorphic to the quotient group, we can represent the quotient group in terms of its isomorphic permutation group. The necessary help to implement it is provided in [1]. Hence, It would be something like this :

    # Quotient of permutation group G by permutation group H 
    >>> G = PermutationGroup(Permutation(1,2,3),Permutation(2,3))
    >>> G.order()
    >>> 6
    
    # H should be the normal subgroup in G.
    >>> H = PermutationGroup(Permutation(1,2,3))
    >>> H.order()
    >>> 3
    >>> H.is_normal(G)
    >>> True
    >>> Q = G.quotient(H)
    # Output the permutation group which is isomorphic to quotient group G/H.
    >>> Q
    >>> PermutationGroup([Permutation(1,2)])
    >>> Q.order()
    # Order of factor groups Q is equal to |G|/|H|
    >>> 2

I would also like to implement some methods of Young Tableaux. Young Tableaux would be useful for calulating the dimension of irreducible representations of corresponding Sn Symmetric group. It can be calculated by hook's rule as done in [2] and [3].
Also, Young Tableaux are useful for labeling irreps of various groups.

(1) The k-box Young diagrams label all irreps of the corresponding symmetric group Sk.

(2) The standard tableaux of k-box Young diagrams with no more than n rows label the irreps of General Linear group of order n.

(3) The standard tableaux of k-box Young diagrams with no more than n − 1 rows label the irreps of Special Linear group of order n.

    >>> k = 4
    >>> Y = YoungTableaux(4)

    # Find the young partitions for a given number.
    
    >>> Y.young_partition()
    >>> [ [4],[3,1],[2,2],[2,1,1],[1,1,1,1] ] 
    
    # Young transpose of given young partition
    
    >>> S4 = Y.young_transpose([3,1])
    >>> S4
    >>> [2,1,1]
    >>> Y.young_transpose([4])
    >>> [1,1,1,1]
    
    # Dimension of the given young diagram or partition which is also equal to the dimension of the corresponding irreducible representation of Sn Symmetric group
     
    >>> Y.dimension(S4)
    >>> 3

Representations of conjugacy classes representatives are also needed to be implemented in sympy. There is no support for it at present. I think of implementing it as it is given in [1]. If G is a permutation Group then G.conjugacy_classes_representatives() yields the list of representatives of each conjugacy classes of elements of G i.e the elements that are conjugate to the elements of G. The size of the each conjugacy class is equal to order of the group divided by the order of the centralizer of an element of the class.The interface for the same can be as follows as it is done in sage and GAP :

     >>> G = PermutationGroup(Permutation(1,2)(3,4), Permutation(1,2,3,4))
     >>> G.order()
     >>> 8
     >>> C = G.conjugacy_classes_representatives()
     
     # Yields the list of conjugacy classes representatives of each conjugacy classes of G.
     >>> C
     >>> [(), (2,4), (1,2)(3,4), (1,2,3,4), (1,3)(2,4)]
     >>> size=[]
     # Calculate the size of each conjugacy class of G. 
     >>> for i in C:
               size.append(G.order()/G.centralizer(i).order())
     >>> size
     >>> [1,2,2,2,1]  # Sizes of each conjugacy class of elements of G.
     >>> sum(size)   
     >>> 8            # Sum of sizes of each conjugacy class of G is always equal to the order of G.

Solvable Radical of any permutation group G yields the largest normal solvable subgroup of G. At present, there is no method for solvable radical in sympy. I would like to implement the same. The algorithms to implement it is given [1] in 4.7.5 section (Computing Solvable Radical). After implementing, it would be looking something like this :

     >>> G = SymmetricGroup(4)
     >>> G.solvable_radical()
     # Gives the solvable radical of given permutation group G.
     
     >>> PermutationGroup(Permutation(1,2)(1,2,3,4))
     >>> H = SymmetricGroup(5)
     >>> H.solvable_radical() 
     >>> PermutationGroup(Permutation())

Todd-Coxeter algorithm for coset enumeration is not yet implemented in SymPy. Coset enumeration is a procedure to obtain the permutation representation of permutation group of G on the set of cosets of a subgroup of a finite index. Todd-Coxeter algorithm can be used to describe the permutation representation of a Group G over a set of cosets with respect to its subgroup H. In this process of coset enumeration, three kinds of tables are produced.:

(1)Subgroup Table : It is made for every generator of the subgroup. It contains information on the specific generator of the subgroup.

(2)Relator tables: The specific relator is expressed in terms of the generators of the group.

(3)Coset Tables: Contains all the cosets and the action of the generators of H on the cosets of H.
```
The implementation details for the same is as given in [4]. Hence, I would also like to implement   
```

Todd-Coxeter algorithm for coset enumeration as other CAS have.

Sylow Subgroups: If in any group G, p^n (where p is prime) divides the order of group G, then G must have subgroup with order p^n. Sylow theorem will help to find such sub-group. Hence, for any prime p of the order of finite group G, there exists a Sylow p-subgroup of G. The order of a Sylow p-subgroup of a finite group G is p^n. So, it would then become easy to find the subgroup with order of p^n as Sylow subgroup will only take the argument as p (prime no.) and not any power to p. Hence, it would be nice to have Sylow subgroups in sympy. The algorithm for implementing sylow subgroup is as given in [1]. It would look like follows as done in sage and GAP :

     >>> G = PermutationGroup([Permutation(1,2,3), Permutation(2,3)]
     >>> G.sylow_subgroup(2)
     
     # Compute the sylow subgroup (2 is the given prime no.)
     
     >>> PermutationGroup(Permutation(2,3))
     >>> G.sylow_subgroup(5)
     >>> PermutationGroup(Permutation())

Timeline

I intend to follow the following tentative timeline during the summer for my project. I will be working about 35-40 hours/week for my project during the summer

Pre-Coding and Community Bonding Period:

During this course of time, I will spend my time to get familiar with books that I will be referring to implement my project. I will brush up my concepts that I will be implementing in my project.

Week 1-2
- I will start with the class on YoungTableaux. I will figure out the things that I will be implementing in the Young Tableaux module like whether to implement Young diagrams or not and how to implement it.
- Then, I will implement the complete structure of Young Tableaux and will generate the PR to merge my work until this time.
- Add tests for the same and generate the PR for the same.
Week 2-3
- During this time, I will implement the support for quotient group. I think, it is bit difficult to implement the Quotient group in sympy as it is in Sage and GAP. The necessary help and algorithms to implement the Quotient group is provided in [1].
- Add the necessary tests and generate the PR for it.
Week 4-5
- Implement the support for conjugacy classes representatives.
- Add tests for the same and generate PR for the unmerged work.
Week 6-7
- Coset enumeration by Todd-Coxeter algorithm and its consequences: represents the group over a set of cosets with respect to its subgroup.
- Add tests and the PR for the same.
Week 8-9
- Implementation of p-core and solvable radical
- Adding the tests and PR for the same.
Week 10-11
- Implement the support for sylow p-subroup.
- Add necessary tests for the same and generate the pull request.
Week 12-13
- Going through the entire code and see if it needs any changes or improvement and some code cleaning.
- Will work on unmerged PR's.
- Adding the Sphinx documentation and add some more complex test cases, if needed.