GSoC 2019 Application Divyanshu: Group Theory - sympy/sympy GitHub Wiki

Table of Contents

About Me

Basic Information

Heading Details
Name Divyanshu
University Indian Institute of Information Technology Manipur
Major Computer Science
Email [email protected], [email protected]
GitHub/Gitter divyanshu132
Timezone IST(UTC+5:30)

Personal Background

I am a Junior year(third year) Computer Science major at Indian Institute of Information Technology
Manipur. I started programming in the freshman year of my college. In my freshman year I had a C
course so, I started with C and C++ and my keen interest in mathematics helped me a lot to get a
good grip on competitive programming. Further, I started learning Python and I have also done most
of my course projects in Python. I have been programming for three years.
I am really passionate about programming and contributing to open source world.

Technical Background

  • I work on Ubuntu 17.10. I prefer Sublime Text as my primary text editor, because it provides
    auto-complete and it is fast. I have been using Linux and Sublime Text for about 3 years.
  • I have been programming for about 3 years. I am proficient in C/C++, STL, Python and Java.
  • I have been using Python for almost 2 years and I am pretty comfortable with it.
  • I have already submitted few patches in SymPy Group Theory section so, I have a good
    understanding of its implementation in SymPy.
  • I have done a semester work on Discrete Mathematics and Group Theory. I have a good
    understanding of Group Theory and Abstract Algebra so, I will not have any difficulty
    in understanding the new parts of Group Theory.
  • I am familiar with the Version Control Systems. Mostly I have used Git and Github only.

Contributions to SymPy

I started contributing to SymPy about three months back, and in this duration I learnt a lot
about SymPy and how impactful this Computer Algebra System is. I introduced myself to the
Gitter channel and started working on some of the Easy to Fix issues. Since, the whole
codebase is well documented it was easy for me to understand the corresponding functions
and make changes. All the members are active, In case if I had any queries, I discussed
with other members and got them resolved which mostly motivated me to keep pushing commits.

I opened multiple PR's aimed at adding new functions, optimizing existing functions,
adding tests for existing functions, improving documentation and fixing open issue.

PR’s (merged/unmerged)

  • (Merged) PR #16248 Added Elementary and Polycyclic groups in Permutation groups.
  • (Open) PR #16522 Implemented methods to check if a group is cyclic or not for both Permutation
    as well as Fp Group, also added methods for index and exponent computation.
  • (Merged) PR #16375 Added is_perfect function to check if a group is perfect or not.
  • (Open) PR #16394 Fixed error for relator elements not in the generators of the homomorphism.
  • (Merged) PR #16413 Reduce time taken by is_solvable by omitting the computation of
    derived_series if order is odd.

Above PR’s are specifically related to Group Theory.

  • (Merged) PR #15910 Updated stats, added discrete types and Rademacher in the stats.
  • (Merged) PR #15941 Avoid links to doc.sympy.org in the docs.
  • (Merged) PR #15990 Avoid infinities in _eval_sum_hyper by simplifying before substitution.
  • (Merged) PR #16009 Fixed the _discrete_log_pollard_rho method for discrete logarithm
    which was producing results even if the base of the log b was not a generator of the
    multiplicative group modulo order(n).
  • (Unmerged) PR #16115 Added function to compute the Goldbach's conjecture of a given number.
  • (Merged) PR #16044 Tests were added for the recursion error computing matrix inverse.
  • (Open) PR #15911 Removed depreciation warnings for bounded, unbounded and infinitesimal.
  • (Merged) PR #16052 Added function _eval_Eq for MatExpr.
  • (Open) PR #15963 Fixes the syntax error on lambdify.
  • (Unmerged) PR #16112 A function is implemented for deficient numbers in number theory.
  • (Merged) PR #16136 Function yielding sequence rotations has been added to iterables.py
    of the utilities module.
  • (Merged) PR #16157 Improve limit to catch ValueError from core in limit.
  • (Merged) PR #16168 Raise ValueError in ode if number of functions given is not equal to the
    number of equations.
  • (Open) PR #16188 Raise ValueError for the application of load beyond the length of the beam.
  • (Open) PR #16195 Simplification of singularity-function to calculate shear_force,
    bending_moment and deflection etc at any point on beam.
  • (Merged) PR #16064 Replace deprecated np.asscalar with item.
  • (Merged) PR #16096 Fixes the unicode support in python-2 by using string_types in place of str.
  • (Merged) PR #16061 Fixes the comparison of None with oo/-oo and finite numbers.
  • (Merged) PR #16053 Tests for deletion of newlines by sympify.
  • (Merged) PR #16016 Update year in SymPy license.
  • (Open) PR #16150 (1/x).evalf(subs={x: 0}) should return inf or zoo not 0.
  • (Merged) PR #15950 Improved docstrings of matrices/matrices.py.

Apart from these I was also involved in discussions or reviewing some of the PR’s and Issues namely:
#16384, #16339, #16155.

Issues/Bugs Reported

  • (Open) Issue #16078 integrate((sqrt(sin(x))*cos(x)**5), (x, 0, pi/2)) takes Infinite time.
  • (Open) Issue #16054 (x - 1).has(1) fails.
  • (Open) Issue #16084 integrate(log(sin(x)), (x, 0, pi/2)) does not evaluate.
  • (Closed) Issue #16113 Add function for Goldbach's conjecture.
  • (Closed) Issue #16001 No result for ask(Q.rational(x/y)).
  • (Open) Issue #16396 integrate(1/(1+sqrt(tan(x))), (x, pi/3, pi/6)) does not evaluate.

The Project

Abstract

The project mainly focuses on further development of Group Theory section of the Combinatorics module.
The whole project is divided into 3 phases :

  • Phase 1:

    • Computation of composition series and abelian invariants.
    • Implementation of polycyclic group and the elementary operations for a polycyclic group.

  • Phase 2:

    • Computation of subgroup intersection.
    • Implementation of isomorphisms for a polycyclic group.
    • Implementation of quotient group algorithms - subgroup quotient and maximum abelian quotient.
    • Implementation of hall subgroup.

  • Phase 3:

    • Computation of modulo-pcgs for a polycyclic group.
    • Computation of group automorphisms.

Implementation Details

Computation of Series

Implementation of Composition Series. To understand a group it suffices to understand the
simple groups in its composition series which represents the pieces of which original group
is built of. A composition series is a maximal subnormal series.

A method named composition_series will be added.

>>> a = Permutation(1, 2, 3, 4)
>>> b = Permutation(1, 2)
>>> G = PermutationGroup([a, b])
>>> C = G.composition_series()
>>> C[0]
PermutationGroup([
    (1 2 3 4),
    (1 3)(2 4)])

Implementation of Abelian Invariants

Implementation of Abelian Invariants algorithm to return the primary decomposition of the
commutator Quotient group of the given group, which are given as the prime-powers or zeros
and describe the structure of G/G as the direct product of cyclic groups of prime-power order.

GAP implements a method called AbelianInvariants for this purpose.

gap> G:=Group((1, 2, 3, 4), (1, 2), (5, 6));
Group([ (1,2,3,4), (1,2), (5,6) ])
gap> AbelianInvariants(G);
[ 2, 2 ]
gap> f:=FreeGroup(2);
<free group on the generators [ f1, f2 ]>
gap> g:=f/[f.1^6,f.2^6,(f.1*f.2)^6];
<fp group on the generators [ f1, f2 ]>
gap> AbelianInvariants(g);
[ 2, 2, 3, 3 ]

A similar method named abelian_invarients can be implemented in SymPy using the
derived_subgroup and the prime-power of the generators of the group.
As I have mentioned in this PR #16522, Abelian invariants can be further used to check
if an infinite order Fpgroup is cyclic or not.

Computation with Polycyclic Groups

Polycyclic groups are represented by a pc-presentation.
Implement a PcGroup subclass with additional attributes like pc_series, pc_generators.
Include function is_polycyclic in main FpGroup method, which can be computed easily with
the help of is_cyclic function implemented in PR #16522.

  • creating a polycyclic group from a polycyclic presentation.

    • GAP way of doing it is shown below, GAP also implements a method canEasilyComputePcgs(G)
      this filter indicates whether it is possible to compute a pcgs for given group cheaply,
      same can be implemented in SymPy as well.
gap> G := Group((1, 2, 3, 4), (1, 2));;
gap> p := Pcgs(G);
Pcgs([ (3,4), (2,4,3), (1,4)(2,3), (1,3)(2,4) ])
gap> IsPcgs(p);
true
gap> G := Group((1, 2, 3, 4, 5), (1, 2));;
gap> Pcgs(G);
fail
gap> CanEasilyComputePcgs(G);
false

  • Implementation of elementary operations for polycyclic group.

    • After having a basic structure of pc group other elementary operations can also be
      implemented like relative_order, is_prime_order_pcgs, pc_series, identity_pcgs.
      For reference we can look in the GAP implementation as well as the chapter 8 of the Handbook.

  • Computation of Isomorphisms.

    • Implementation of a function pcgroup_isomorphism which will return an isomorphism
      from a given group G onto an isomorphic pc group. G must be a polycyclic group of
      any kind.

      For implementation we can look into the GAP library which implements a function named
      IsomorphismPcGroup for the same functionality.

gap> G := Group((1, 2, 3), (3, 4, 1));;
gap> iso := IsomorphismPcGroup(G);
Pcgs([ (2,4,3), (1,2)(3,4), (1,3)(2,4) ]) -> [ f1, f2, f3 ]
gap> H := Image(iso);
Group([ f1, f2, f3 ])

Quotient Groups

  • An attempt has been made in GSoC 2018 to compute the quotient groups of finitely presented
    groups     but was not completed. I will work on the same approach namely the subgroup_quotient
    and maximum_abelian_quotient function of PR #14981.

  • Quotient Groups of Polycyclic Groups - Modulo pcgs

    • Modulo pcgs are often used to facilitate efficient computations with quotient groups,
      since they allow computations with quotient groups without formally defining the quotient
      group at all.

      GAP implements the method ModuloPcgs for the same, similar functionality can be added in SymPy.

gap> G := Group((1, 2, 3, 4, 5), (1, 2));;
gap> P := ModuloPcgs(G, DerivedSubgroup(G));;
gap> P;
Pcgs([ (4,5) ])
gap> NumeratorOfModuloPcgs(P);
[ (1,2,3,4,5), (1,2) ]
gap> DenominatorOfModuloPcgs(P);
[ (1,3,2), (2,4,3), (3,5,4) ]
  • If time allows we can further extend the modulo_pcgs to compute numerator_pcgs
    and denominator_pcgs.

Computation of Hall Subgroup

Implementation of a function named hall_subgroup. If for the given group is_solvable
is True then, this function will always return a subgroup else it may return a subgroup
or a list of subgroups.

>>> G = SymmetricGroup(5)
>>> H = G.hall_subgroup([2, 3])
>>> H
PermutationGroup([
    (3 4),
    (2 4 3),
    (1 4)(2 3),
    (1 2)(3 4)])
>>> H.order()
24
>>> H = G.hall_subgroup([3, 31])
>>> H
PermutationGroup([
    (1 2 3)])

Intersection of Subgroups

Implementation of a function subgroup_intersection to compute the intersection of 2 subgroups.
Let's say we have two subgroups G, H such that G,H≤K≤Sym(n), and we want to compute the
subgroup_intersection(G, H). Since in GSoC 2012 the subgroup_search function has been
implemented, Now we can easily compute the intersection(G, H).
Intersection of 2 subgroups is also a subgroup.

The complete details of the algorithm is described in Section 4.6.6 of the Handbook.

Automorphisms

Implementation of group automorphisms for permutation and pc groups. An automorphism is an
Isomorphism from a Group to Itself. Since the computation of automorphisms can be expensive,
we can implement some other functions like abelian_automorphism as well on the basis of
initial check of the group.

gap> g:=Group((1,2,3), (1,2));
Group([ (1,2,3), (1,2) ])
gap> AutomorphismGroup(g);
<group of size 6 with 2 generators>

Proposed Timeline

Community Bonding Period (May 06th - May 27th)

My semester exams will be over on 6th of may, just at the starting of community bonding period
so, I will have enough time to go through the actual algorithms to be implemented and their
implementations in GAP. I would also take this time for interacting with mentors and get concrete
details of expected work to be completed I will start the implementation from the last week of
community bonding period.

Phase-1

Week 1, 2 (May 27th - June 10th)

  • Implement composition series and abelian invariants.
  • Extend the functionality of is_cyclic for infinite groups using above abelian invariants.

Week 3, 4 (June 10th - June 24th)

  • Implement the structure of polycyclic group in SymPy with the help of pc sequences.
  • Implement the elementary functions for polycyclic group:
    • relative_order,
    • Is_prime_order_pcgs,
    • pc_series,
    • identity_pcgs.
  • Write a good amount of tests covering all the functions of polycyclic group and compare
    the results with GAP software.

Phase-2

Week 5, 6 (June 24th - July 08th)

  • Dig into the subgroup_search implementation in SymPy, work on subgroup intersection
    algorithm in the Handbook and implement function subgroup_intersection.
  • Look into GAP implementation for isomorphisms of a polycyclic group and integrate
    it with SymPy pcgroup_isomorphisms function.

Week 7, 8 (July 08th - July 22nd)

  • Implement functions to calculate quotients of groups.
    • Subgroup_quotient,
    • Maxium_abelian_quotient.
  • Implement hall subgroup.

Phase-3

Week 9, 10, 11 (July 22nd - Aug 19th)

  • Implement modulo-pcgs for polycyclic groups.
  • Implementation of group automomorphisms.

Week 12 (Aug 19th - Aug 26th)

  • Finish documentation, Sort out all PR issues, Remove bugs.
  • Submit the final report.

Notes

  • I have no other major commitments in the summer. I will be staying back home and on an
    average will be able to spend 40 - 45 hours per week on the project. My college will restart
    in the end of July but I can continue at the same pace because at the beginning of semester
    I will not have that much of work.

  • If there will be things left unimplemented or unmerged, I will try to complete that post GSoC.
    I would love to explore other modules of SymPy.

References