GSoC 2016 Application Gaurav Dhingra: Group Theory - Shekharrajak/sympy GitHub Wiki

Name: Gaurav Dhingra

University: Indian Institute of Technology, Roorkee

Major: Applied Mathematics

email: [email protected]

IRC Handle: gxyd at freenode.net

github username: gxyd

Hello, I am Gaurav Dhingra a third year undergraduate student at IIT Roorkee, India. I am pursuing a degree in Applied Mathematics. I work on Elementary OS Freya 0.3 (based on Ubuntu 14.04 LTS) with vim as my primary text editor. I do my work with vim since it allows me work quickly with the code. I am proficient in Python, C++. I love Python since i am a math major and Python allows me to convert mathematical ideas into code without much langauge barriers.

I first started contributing to SymPy in January 2015 on issue #8746 but stalled since of the lack of motivation and confidence.

Then i started contributing to SymPy again in June 2015 and here is list of all of my Contributions in chronological order:

• (Merged) M.row_del(index) and M.col_del(index) now raise IndexError for out of bound Index #9468
• (Unmerged) * ('''Merged''') <code>y*(x*M) != x*(y*M) for non-commutative symbols x and y #9520
• (Unmerged) transpose(MatMul(<Symbol>, Matrix)) now works properly #9507
• (Merged) Mod(zoo, 0) now returns nan and fixed one typo #9528
• (Merged) splitting simplify.py #9553
• (Merged) solveset(Abs(x) + 1, x) now returns EmptySet() typo fixed #9570
• (Merged) redudant declaration removed fixes issue #9573 *9574
• (Unmerged) Union of set containing UniversalSet with non-intersecting Interval #9578
• (Closed) Complement of UniversalSet with Union of Sets works #9579
• (Merged) Limit(x, x, a).free_symbols now returns set([a]) #9581
• (Merged) invert_real for sin and cos now operates correctly #9591
• (Unmerged) invert_complex added for trigonometric func. #9604
• (Merged) Interval - FiniteSet(x) is now returned unevaluated #9682
• (Closed) Intersection(Interval, FiniteSet(m, n), FiniteSet(n)) now works correct #9683
• (Merged) solveset_real(Eq(x, 1), x) fixed #9688
• (Merged) combsimp for work on factorials #9711
• (Merged) Range Function for rational functions #9719
• (Merged) imageset for Piecewise under Interval added #9763
• (Closed) solveset_real(abs(f1/f2), x) for f1,f2 polynomials in x #9772
• (Merged) not_empty_in added to codomain.py #9779
• (Merged) soleveset title_doc changed #9781
• (Closed) ImageSet(Lambda(n, nan), any_set) now returns EmptySet #9734
• (Merged) reference to sphinx docs for normalize_theta_set #9735
• (Merged) solveset(1/exp(x), x) returns S.EmptySet #9735
• (Closed) singularities((x**2 - 1)/(x**3 - 1), x) returns (1,) #9741
• (Closed) solveset_complex(sinh(x), x) returns ImageSet(Lambda(n, n*I*pi), Integers) #9750
• (Merged) soleveset title_doc changed #9781
• (Closed) [WIP] matrix.rank() with unkown .is_zero raise NotImplementedError #9793
• (Merged) solveset_real(x**3+1, x) returns FiniteSet(-1) #9804
• (Merged) Complements of FiniteSet with Symbols returned unevaluated #9814
• (Merged) test for solveset(Piecewise(((x - 2)**2, x >= 0), (0, True)), x, S.Reals) #9851
• (Unmerged) [WIP] Implementation of arbitrarily indexed Unions and Intersecions #9853
• (Merged) solveset(Abs(sin(x)) + 1, x, S.Reals) returns EmptySet #9857
• (Merged) ConditionSet API changed #9864
• (Merged) symbols -> Dummy_symbols in ComplexPlane #9867
• (Merged) ComplexPlane->ComplexRegion name changed #9873
• (Closed) Parenthesize printing of Unions having Complement #9878
• (Closed) [WIP] fuzzy_set implementation #9897
• (Merged) is_convergent method implementation for Sum #9906
• (Closed) real_bound added to Function class #9911
• (Merged) solveset(2*x + 1/(x - 10)**2, x, S.Reals) works #9930
• (Merged) Docstring Python escaping backslash in latex strings added #9938
• (Merged) is_increasing(), is_decreasing() signature changed #9951
• (Merged) Union(Interval(-oo, oo), FiniteSet(1)) returns Interval(-oo, oo) #9958
• (Closed) solve_univariate_inequality(x**2>=0, x) returns (-oo, oo) #9960
• (Merged) is_convergent() for Product #9982
• (Merged) Probability for empty set returns S.Zero #10004
• (Merged) oo**e for non-real complex e handling #10029
• (Merged) docs changes in rv.py #10039
• (Merged) Implementation of Limits (different from Limit) in SymPy #10051
• (Merged) P(X < oo) and P(X > oo) for True, False probability #10053
• (Merged) Intersection of sets containing common symbols handled #10079
• (Merged) X.pdf(x) for invalid x in DieDistribution raises ValueError #10083
• (Merged) imageset of first interval of singularities included #10115
• (Merged) pretty printing of Cycle works #10183
• (Merged) docs and code fixes for Combinatorics module #10229
• (Merged) .is_group for PermutationGroup now returns True #10230
• (Merged) latex printing of Cycle, Permutation #10261
• (Closed) [WIP] FiniteGroup in SymPy #10263
• (Unmerged) [WIP] FreeGroup implementation in SymPy #10350
• (Unmerged) [WIP] SymmetricGroup is now a class not function #10363
• (Merged) Simplification of an expression with exponent containing assumption symbol #10378
• (Merged) normalizing an open Interval now works #10421
• (Merged) ComplexRegion satisfies the Key Invariant property #10470
• (Closed) zeta(x) for (Re(x) - 1) nonzero is Finite #10479
• (Unmerged) [WIP] singularities functions returns exp, log singularities #10495
• (Unmerged) Equality and printing of S.Complexes #10505

It would be awesome to have a Group Theory module. Presently only Combinatorics module has been implemented in Sympy, which is fairly well developed(though some changes can still be made). We presently have a combinatorics module but other than much more can be done. I also look at the GAP project for some inspiration. They have the most powerful group theory software (AFAIK). than that, My intention is to create a module for computation with Finite and Finitely Presented Groups.

Though all Finite Groups are isomporphic to the permutation groups, but the there are also other presentations of groups which we can make use of to represent infinite groups.

FreeGroup: Class `FreeGroup` will be used to have create a Free Group. The input API of the FreeGroup will be only either an positive integer or `infinity`. Since the FreeGroup can also have infinite order. Though GAP also uses string based API's like `FreeGroup( "a", "b" )` though that should not be used in SymPy since, it's better to create a GroupSymbol object, than to use strings. Otherwise there will always have annoying indirection, since we can't actually multiply strings together. For the output:

>>> f = FreeGroup( 4 )
>>> f
<free group on the generators [ f0, f1, f2, f3 ]>

There will also be a `FreeGroupElm` class that will represent elements internally using the data structure as `[(]` will be internal representation of a `word` generated by a `FreeGroup` (this will be called the "letter represenation of assosciative words")

Q1. Why do you want this behavior to work this way? The whole idea behind Basic. is that == works as structural (not mathematical) equality, which tends to be the most useful thing when dealing with symbolic objects.

Free Group:

Though mathematically `Free Groups` is just a type of Finitely Presented Groups i.e Free Group is a Finitely Presented Group with no relators, i.e `R = ∅` . But from implementation point of view `Finitely Presnted Groups` API will look like `g = FpGroup( f, r )` here `f` denotes a `FreeGroup` like `f = FreeGroup( 4 )` and `r` being a set of relators used for making the Finitely Presnted Group `g`.

>>> f = FreeGroup(2)
>>> g = f / set([f[0]**2, f[1]**3, (f[0]*f[1])**2)
>>> g
<fp Group on generators >
>>> f.is_fpGroup   # even the FreeGroup is a Finitely Presnted Group
True

The Group Class: This will be a central class for all groups from which all the objects like mathematical groups, cosets will be derived from.

>>> f = FreeGroup( 2 )
>>> f.is_Group
True
>>> h = LeftCoset(Permutation(1,2), PermutationGroup((1,3,2),(1,4))
>>> h.is_group
False

Equality checking of any elements of FpGroup? How to do this?

Normal form ??

Algorithms that are used in this regard include: If the FpGroup is known to be of finite order then use the faithful permutation representation by a bounded Todd-Coxeter. If this fails, a Knuth-Bendix[3] is attempted and the words are compared via their normal form. <------ what is normal form here?

It can be sort of a debate if we want to use `==` for checking `structural equality` or `mathematical equality` my opinion: We should go with `==` refering to `mathematical equality` since checking the structural equality if not much of a use in the case of `Groups`. Since defining `mathematical equality` is to be done anyway since that is a fundamental operation in Group Theory Now if we don not define the `mathematical equality` using `==` then other methods like `.equals` will have to be used that don not seem to be good from the user point of view.

Consider this:

>>> f = FreeGroup( 2 )
>>> g = FpGroup( f, [ f.1**2, f.2**4, (f.1*f.2)**6] )
>>> g.1**2*g.2**4 == g.1**0							---- 1
True

>>> (g.1**2*g.2**4).equals(g.1**0)					---- 2
True

Now for equality of `FpGroup`s since the `Groups` are abstract objects even if they are constructed from same `FreeGroup` and `relators` they should be different the same is true for `FreeGroup` Example

>>> f:=FreeGroup(2);
>>> g1:=f/[f[0]**2, f[1]**3, (f[0]*f[1])**5];
>>> g2:=f/[f[0]**2, f[1]**3, (f[0]*f[1])**5];
>>> g1 == g2;
False

... 1 http://www.math.colostate.edu/~hulpke/talks/tala.pdf Hulpke Notes

... 2 https://en.wikipedia.org/wiki/Presentation_of_a_group Wiki article

... 3 http://homepage.cs.uiowa.edu/~astump/papers/thesis-wehrman.pdf (Knuth Bendix ALgorithm)

... 4 https://groups.google.com/forum/#!topic/sympy/mZ8K013YWZQ 2012 Google Groups Alexandar Makelov Proposal Discussion

... 5 https://github.com/sympy/sympy/wiki/GSoC-2012-Application-Aleksandar-Makelov:-Group-theory (why this? -- Since the project initially stated that he would implement Finite and Finitely Presented Groups, though later diverged towards only Permutation Groups and it's algorithms)

... 6 http://www.gap-system.org/Manuals/pkg/fga/doc/manual.pdf GAP FGA (free group algorithms) Manual

... 7 Obviuosly the GAP Documentation for using them for how they work (in terms of API). I strongly believe that it would be best for us to go ahead make the SymPy have functionality similar to GAP, since that would save a lot of time as they already have thought much more than us for how to implement that.