Name: Gaurav Dhingra

University: Indian Institute of Technology, Roorkee

Major: Applied Mathematics

email: [email protected]

github username: gxyd

IRC Handle: gxyd at freenode.net

Blog: https://gxyd.github.io/

Time Zone: IST (UTC +5:30)

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 when added with vim-extensions using Vundle. I have been programming for 2 years now, i am proficient in Python, C++. I started using Python in parallel with contributing to SymPy. Python's list comprehension is a cool feature missing in other programming languages. I contributed to Pi-Producing Program which uses SymPy to generated "PI" in different ways. I like Python since as a math major Python allows me to convert mathematical ideas into code without much programming langauge barriers. Editing wikipedia articles is something that i also like so i have often edited the SymPy wikipedia article quite a few times.

My favourite feature of SymPy is its printing, and also i don't need to write LaTex manually to convert mathematical expressions to corresponding LaTex expressions.

>>> print(latex(Integral(x**2/(1 + x**4), (x, 0, oo))))
\int_{0}^{\infty} \frac{x^2}{1 + x^4} dx

I know Mercurial and Git, after contributing to SymPy for almost 1 year, i am now very much familiar with git.

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) M.row_insert() and M.col_insert() now act in-place for all indices #9477
• (Unmerged) transpose(MatMul(<Symbol>, Matrix)) now works properly #9507
• (Merged) y*(x*M) != x*(y*M) for non-commutative symbols x and y #9520
• (Merged) multiplicity(n, 0) raises error for any `n` #9528
• (Merged) Mod(zoo, 0) now returns nan and fixed one typo #9546
• (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 #9736
• (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
• (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 AccumBounds (different from Limit) in SymPy #10051
• (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
• (Merged) Equality and printing of S.Complexes #10505
• (Merged) printing of Permutations for max element taken care #10558

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). I also looked at the GAP software for some inspiration. They have the most powerful group theory software. My intention is to create a module for computation with Finite Groups and Finitely Presented Groups. I will focus upon:

• How to represent the Finitely Presented Groups, free groups, semi group, free semigroup, monoids, free monoid, magma, free magmas, free abelian group, general Group and examples of groups represented by such presentations like fibonacci group and other group related algebraic structures?
• How to represent the elements of respective Groups?
• If respective groups of infinite order are there, then how to deal with those groups?
• Implement respective algorithms for the computation of normalizers, centralizers, center, order, subgroups, orbit etc.

After taking a basic course in Abstract Algebra, i realised that computations in even the "small" (i.e small order) FpGroup is difficult to do manually. Also i have been contributing to SymPy for almost 1 year now, so i think adding its functionality to it would be good to SymPy and Python world in general. On the way i came across Magma software, i enjoyed reading its documentation (i haven't used it though). Alas! it is a proprietary software, so i would like to add Group Theory functionality that i could use in further studies.

The project can be divided into 3 parts:

1. Implementation of classes like Group, GroupElm, FreeGroup, FreeGroupElm, FpGroup, Magmas, Semigroup, FreeSemiGroup, Monoid, FreeMonoid, FreeAbeliangroup, Coset/RightCoset and classes for elements of these groups. Though these will not be created before the other 2 parts, but rather run in parallel with the other 2 parts.
2. Implementation of algorithms: Todd Coxeter for Coset Enumeration, Reducing words of FreeGroups.
3. Rewriting Systems and Knuth Bendix Completion procedure for strings, Reidemeister-Schreier algorithm.

"Bottom up" or "parallel" approach will be used for the implementation of classes of different groups. Like the implementation of FreeGroup and Group classs would not affect other.

We will approach the implementation of groups in a "bottom up" manner instead of trying to find a common API to begin with. Kalevi Suominen said:

    Elements of different types of groups may require quite different methods.
    Elements of permutation groups are permutations with their own methods.
    Elements of free groups (perhaps of class FreeGroupElm) are best described
    as "words" in an alphabet consisting of the generators and their inverses
    (and possibly other integer powers). Elements of matrix groups again have
    their own multiplication and inversion. There will be common abstract
    classes like Group, GroupElm but their contents would remain rather meagre.

1. The construction of fp-groups in terms of generators and relations.

The methods are similar to inverse finite automata in Theory of Computation.

FreeGroup: Class FreeGroup will be used to have create a Free Group. The input API of the FreeGroup will be only either a 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 is better to create a GroupSymbol object, than to use strings. Otherwise there will always have annoying indirection, since we can not 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 [ ( generator[0] , exp_0 ), ( generator[1] , exp_1 ) .... , ( generator[n-1] , exp_n-1 ) ] will be internal representation of a "word" generated by a FreeGroup (this will be called the "letter represenation of associative words", called sparse representation in Polynomial Rings). Not all the mathematically equal elements are printed in the same way.

• One of the key aspects of our implementation will that since GAP was written at a time when memory was an expensive resource, so some good improvements are possible. Some work regarding the implementation of FreeGroup and FreeGroupElm classes is already done by us(with @jksuom) here https://github.com/sympy/sympy/pull/10350 . Though one change is necessary in that PR: The connection between FreeGroup and FreeGroupElm has to be changed. The situation is similar to that in sympy.polys.rings. The class PolyRing has the attribute dtype that points to the corresponding PolyElement and also methods for constructing such elements. There is no new method in PolyElement.
• Equality of FreeGroups: a definition saying that no two FreeGroup's are equal.
• Would any finite set of generators as input to FreeGroup? To see for this, let us see this example from GAP:

gap> f := FreeGroup( 2 );;
gap> g := FreeGroup( 2 );;
gap> h := Group(f.1, g.1);
Error

Even this seems reasonable the new group h was made to contain generator of f and g which can not be operated on each other. So the question seems answered.

Making factor_group

API: factor_group( G , relations ) The method factor_group will be used to make a Factor Group of FpGroup, where relations is a set of elements of group G. This will be similar to way we make FpGroup out of FreeGroup, but here we will be making FpGroup out of FpGroup, by factoring out the relations.

Method in FpGroup

is_subgroup_fpgroup, is_fpgroup, set_reduced_multiplication, orbit

set_reduced_multiplication

definition: set_reduced_multiplication( fpgrp ) This method will be used to automatically reduce the elements of an FpGroup. For every FpGroup there will be a variable "reduce" with default=False which will be used to check whether user wants the elements of concerned group to be reduced automatically. "How the reduction of elements be done?", though this method will do something only if the group is "small" (defined below, what small means here).

small group

Defined here "what will be the order for small group?". We will have to decide upon a certain definition for groups below certain order to be small, since sometimes we have to restrict upon certain computations.

2. The construction of particular types of quotient groups: abelian quotient, p-quotient, nilpotent quotient and soluble quotient.

Comparing elements of an FpGroup may run into problems: There exist finitely presented groups for which no algorithm exists (it is known that no such algorithm can exist). Comparison of Elements of Finitely Presented Groups: Two elements of FpGroup are equal if they are equal in the group. Because of the fundamental problems (in algorithm) such a test may take very long and cannot be guaranteed to finish.

Though mathematically Free Group 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 = FpGroup( 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 Presented 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?

First of all don't go straight into the execution of algorithm, since there are certain mathematical method which can be used to check whether the group has infinite order.

Ways to check (for infinite order of group)

• If the free group has n generators associated with fpgroup, and the "number of relators < n" then the fpgroup has infinite order.

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.

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.

Consider this:

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

>>> (g[0]**2*g[1]**4).equals(g[0]**0)       ### 2
True

API 1 seems way more intuitive that API 2

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 = FpGroup(f, set([f[0]**2, f[1]**3, (f[0]*f[1])**5]))
>>> g2 = FpGroup(f, set([f[0]**2, f[1]**3, (f[0]*f[1])**5]))
>>> g1 == g2;
False

Here though g1 and g2 have the same FreeGroup and relators from which they are constructed the groups g1 and g2 are different.

• Centralizer
• Center
• Associative words: There will be a file named sympy.groups.wordassoc.py which will contain all the methods of associative words like "syllable representation", "shortlex ordering", "Sub Syllables" etc. for computing with it.

Examples

>>> f = FreeGroup(2)
>>> f[0]*f[1]**2*f[1]**-1
f[0]*f[1]

There will be no relation between words of different family.

>>> g = FreeGroup(2)
>>> g[0] == f[0]
False

There are some things which work slow (unknown reason) in GAP. I believe that better implementations are possible in Python. For example

gap> f:=FreeGroup(2)
gap> f.1^1000;
f1^1000      # this takes about 4 seconds to complete

Group class

Implementation idea is from this gist made by Kalevi Suominen. A little similar thing for internal data structure has been in my PR, but i didn't explain in detail.

Groups defined by generators (and relators) are analogous to polynomial rings (and their quotient rings). In SymPy there are three different ways of representing polynomials: general expressions, and then dense and sparse representations. Expressions are convenient to use as they are essentially self-contained. But they are less efficient in computations while the other two are each best for specific purposes.

There could also be three types of representations for elements of groups.

Expressions would belong to a class GroupExpr or GrpExpr. They could be constructed from GrpSyms by means of GrpPow and GrpMul together with GrpUnit. There would also be methods such as GrpInverse.

Moreover, group elements could be represented more efficiently as 'words', i.e., lists or tuples, over an alphabet that consists of (representatives of) generating symbols and their inverses. It seems that there are two practical alphabet implementations that are called 'syllables' and 'letters' in GAP. Syllables are essentially pairs of a symbol and an integer exponent. This allows for representing all positive and negative powers of a generator in addition to the inverse. Letters are just integers indexing the generators. Negative integers denote the inverse generators. Both of these could be implemented in SymPy.

In addition, there are different kinds of 'words' in GAP. When there are less than 128 generators, it is possible to pack a 'letter' into a single byte. However, it should be noted that GAP was conceived in a time when memory was an expensive resource. Since shuffling of bytes in a long word is not very efficient, it might be reasonable to be satisfied with standard Python lists and tuples instead of strings in a SymPy implementation.

Objects of class FreeGroup could be constructed by giving their generators as GrpSyms. In mathematics, two free groups are usually considered equal when they have the same generators. I think that could be so also in SymPy. Representations of elements should not be visible on this level. In fact, it seems that a single group object could allow all three different representations.

A GrpExpr would be considered as denoting an element of a group whenever its GrpSyms are among the generators. The group class would have methods transforming these into the two other representations. In addition, the two dense representations could be transformed into each other.

The dense representations would each belong to their own class. (I have not thought about their names yet.) Methods of these classes would include , and inverse. As attributes they should probably have the group and the representation of unit.

Although the external interface to FreeGroup would not include representations, I think they would probably have to be taken into account in the way the generators are given as arguments. Mathematically, two free groups are considered equal when they have the same generators as sets. As the 'letter' representation obviously demands that the generators can be uniquely indexed, we have to add some order to the generator sets. The easiest way would probably be to just give a sequence of GrpSyms as an argument to FreeGroup. Another possibility could be defining a global order among all GrpSymss.

The above remarks could be easily extended to non-free groups. They would have two sets of parameters, generator GrpSyms and relator GrpExprs. The elements of such groups are mathematically sets (called 'cosets'), but they would be represented by suitably chosen representatives.

FactorGroup

This file will contain the declarations of operations for factor group maps. Containing methods of Homomorphism from one group to another, method CommutatorFactorGrp for computing the FactorGroup G/N for the group G. The FactorGrp(G, N) will have an optional argument strict with "default=False", (similar to the current implementation in PermutationGroup), which will test whether the input N is infact normal in G or not. Method HomomorphismByNrmlSubGrp(G, N) will compute one of the homomorphism from G to a group with kernel N.

Printing

Printing of Groups can be divided into 3 parts:

• With almost no information about the group.
• Group with known generators but not size.
• Group with known geneators and known size.
• Groups with infinite size and generators.

>>> f = FreeGroup(2);
>>> g = FpGroup(f, set([f[0]**4, f[1]**2, f[0]*f[1]*f[0]*f[1]]))
>>> g
<fp group on the generators [ f0, f1 ]>    # normal printing with known generators
>>> g.order()
8
>>> g
<fp group of order 8 on the generators [ f0, f1 ]>  # normal printing with known size and generators

Representing Coset

API: RightCoset( H, x ) where H is a group and x is an element of a larger group G. There will be methods in this class for operating upon it as a whole, like CosetDecomposition. This is class will represent any general Coset not just for FpGroup. GAP does not have any LeftCoset method.

Ordering of elements Elements of every group will have an order to them "shortlex".

DoubleCoset method will also be created to make a double coset. API: DoubleCoset( U_1, g, U_2 )

For Magma make sympy.groups.magma.py. Dealing with Magma can be difficult, since of their possible "non-associative" behavior.

Data Structure that can be used

Tuples inside tuples. For example to represent: (a*(b*c))*d we can use, ((a, (b, c)), d). This way we can also operate between Magma elements. Using tuples rather than lists could be benficial since tuples are immutable, and more efficient while creating new elements rather than modifying the existing ones.

• Currently even SymPy doesn't support operations between non-associative symbols. This paper describes computation in non-associative algebra
• Return corresponding magma if input of more-specific algebraic structure is given.

>>> Magma(Permutation(1, 2, 3), Permutation(4, 5, 2))
PermutationGroup(Permutation(1, 2, 3), Permutation(4, 5, 2))

Printing

Magmas will have 4 different printings:

• For a general magma
• for a magma with generators
• for a magma-with-one with generators
• for a magma-with-inverses with generators

Monoid

For monoid make sympy.groups.monoid.py, for semigroup make sympy.groups.semigrp.py

SemiGroup and Monoids are almost the same (since they are studied together in Semi Group theory). Use MagmaWithOne and IsAssosciative, to check whether it is infact a Monoid. While the same thing in SemiGroup is checked with Magma and IsAssosciative whether it a SemiGroup.

SemiGroup

class SemiGroup( Basic ): API: SemiGroup( gens ) where gens is a homogeneous list of elements, may be of integers, or permutations, matrices ...

• A subclass of Basic
• Should we keep a check whether the entered elements are infact "Assosciative" under the operation?
• SemiGroupByGenerators method of SemiGroup which will do the calling to the SetGensOfMagma (since SemiGroup, Monoids are derived from Magmas with some specifically defined properties).
• Regarding SemiGroup there will be methods to check its behavior like: IsRegularSemiGroup, IsRegularSemiGrpElm, IsSimpleSemiGrp, IsZeroGrp, IsZeroSimpleSemiGrp etc.
• The semigroup similar to the groups will have Subsemigroup
• AsSemiGrp( G ) method will try to convert the underlying group G into a SemiGroup, and if the operation fails then TypeError is raised.

>>> s = SemiGrp( [1, 2, 3] )
>>> s
<semigroup with 4 generators>
>>> f = Subsemigroup( s, [1] )
>>> f
<semigroup with 1 generator>
>>> IsSemigroup( f )
True

Similar to the implementation of FreeGroup, the FreeSemiGroup would be created for Free SemiGroup, the caveats of implementation of FreeSemiGroup would not be much different from FreeGroup. Same will be the case with the methods associated with it.

FreeMonoid

Similar to the FpGroup implementation.

FreeSemigroup

Similar to the FpGroup implementation.

Checking Equality of elements FpSemigroup and FpMonoid

A confluent term rewriting system is required to perform this operation of equality checking. The often used algorithm for this is Knuth Bendix Rewriting System, which i will implement.

FreeAbeliangroup

For constructing Free Abelian Group, its input API same as that of Free Group.

Example of FpGroup: FibonacciGroup

class FibonacciGroup(Basic):
    is_group = True
    def __new__(cls, *args):
        if len(args) == 1:
            r = 2
            n = args[0]
        else:
            r = args[0]
            n = args[1]
        f = FreeGroup(n)
        gens = list([GensOfGrp(f)])   # list Generators of Group
        # use the definition on relators of FibonacciGrp
        rels = list(range(n), i-> Product([0..r-1], j-> gens[((i+j-1)mod n)+1])/gens[((i+r-1)mod n)+1])
        return f / set([rels])
    
    def order(self):
        if self.args[0] == 2:
            p = self.args[1]
            if p not in (1, 2, 3, 5, 7):
                return S.Infinity
        else:
            return Order(self)

    ## other methods

Finitely Presented Abelian Groups

Its implementation will be almost the same as FpGroup, apart from few simplifications in it. Some algorithms of FpGroup can be given a simplifed form here.

(Detailed treatment of both theoretical and practical aspects of coset enumeration is there in Charles Sims book on computation with finitely presented groups [Sim94])

• Even the simplest versions of coset enumeration seems rather complicated. For checking whether G is finite or non-finite or G is trivial or non-trivial, this algorithm can be semi-decidable algorithm i.e the algorithm terminates only when we know that group G is actually having Finite index under the subgroup H. Though the algorithm may also take large amount time since of relatively "large" group. The FGA package of GAP uses the version called "extended coset enumeration".
• A prominent variation of coset-enumeration is Low-Index algorithm, implement it from cgt-notes (by Alexandar Hulpke).

This method will generate Permutation representation of FpGroup G on the cosets of a subgroup H. Though internally this method will call respective method to generate Coset Table.

Input API: CosetTable( G, H, limit=4096000 ) where G is a group and H a subgroup of G, having an optional argument limit. Limit – integer (default: 4096000). The maximal number of cosets before the computation is aborted.

Output: It will return a list of size twice the number of generators of FreeGroup of G(since of A = X U X^-1, i.e containing inverses of generators as well) of Permutations, where each permutation Can be used with an alias as_permutation_group

This method will return the coset table of the finitely presented group G on the cosets of the subgroup H. Basically a coset table is the permutation representation of the finitely presented group on the cosets of a subgroup.

• Though this method alone will not be used but other helper methods will also be there. For example to calculate the action of G on the cosets of its subgroup FactorCosetAction method will be used.
• The standard installation of GAP provides methods for Coset Enumeration, instead of seeing the functions in standard installation using the "ACE"(Advanced Coset Enumerator) package for seeing their this implementation is better, since it contains even more of the feature from improving the speed of the algorithm, it is available here
• One of the problems with the suggested API i.e with limit=4096000 as an argument is that. For a finite index value with limit = val < 4096000 is specified and an error is raised for limit exceeding, then with limit again specified the whole process will start from the beginning, so we will have to think about some SymPy decorator to solve that.

The main internal function coset_table_gens_rels will generate the Coset Table with input parameters f_gens, g_rels, standardize_table method using what?? (Can do this using Matrix manipulation or )

.rewriting_system method

The method will return rewriting system corresponding to the FpGroup. It can be used to used to reduce the elements of word (uniquely if it is confluent).

>>> f = FreeGroup(2)
>>> a = f[0]
>>> b = f[1]
>>> G = f / set([a**2, b**3, (a*b*a**-1)**3, b*a*b*a])
>>> k = G.rewriting_system()
>>> k
Rewriting system of Finitely presented group < a, b | a**2, b**3, a*b**3*a**-1, (b*a)**2 >
with rules: a**2    --->    1; b**3    --->    1; (b*a)**2    --->    1; a*b**3*a**-1    --->    1

>>> G([1, 1, 2, 2, 2])
a**2*b**3
>>> k.reduce(G([1, 1, 2, 2, 2]))
1
>>> k.reduce(G([2, 2, 1]))
b**2*a
>>> k.make_confluent()
>>> k.reduce(G([2, 2, 1]))
a*b

=== Knuth Bendix === (Mentioned in 52.6 in GAP manual)

Return the rewriting system corresponding to the finitely presented group. This rewriting system can be used to reduce words with respect to the relations. This algorithm is somewhat similar to Buchbergers algorithm for computing Gröbner bases, which has already been implemented in SymPy.

The reduced Reidemeister-Schreier algorithm is used to compute a presentation of a subgroup of an FpGroup. The implementation by Havas of the Reidemeister-Schreier algorithm for computing and simplifying a presentation of a subgroup of finite index in a finitely presented group.

Steps involved in setting up Reidemeister Algorithm:

• Set up Coset Table: Given G = <g_1, g_2, ... , g_n | R_1 = R_2 = ... = R_m = e> with H = <h_1, h_2, ... , h_p> the coset table of H in G using Todd-Coxeter Algorithm.
• Compute Coset Representative:
• Computer Schreier Generators
• Computer Reidemeister Relators
• Eliminate redundant generator
• Simplify the presentation: There are various techniques for simplification.

Reidemeister-Schreier Abelianised: For abelian subgroups of a group, it is better to perform another version of the algorithm abelianize, in which each relator is abelianized at each stage of the computation, and this greatly simplifies the ensuing presentation.

The GAP software provides powerful tools for analyzing groups, so it would not be very hard to verify the correctness of the code with some fairly sophisticated examples. Also documentation of Magma can be helpful in seeing the functionality.

Community Bonding Period (22 April - 22 May). My vacations will start from 9th May. The important thing to will be to learn more about the Todd Coxeter Algorithm, since there are also improved versions of algorithm (specifically for computing purposes), notably the addition of classical strategies of V. Felsch and HLT (Haselgrove, Leech and Trotter).

• First complete the Pull Request on FreeGroup, by taking into consideration some of the discussions in the private channel https://gitter.im/gxyd/group_theory_implementation . It includes things like changing the connection between FreeGroup and FreeGroupElm classes by something similar to the relation between Poly and PolyElement in sympy.polys.rings.
• Though it would not take much time implementing these remaining methods, in this period we would also forsee what notations should be used. Since the rest of whole implementation of all different representations of Groups would ultimately depend upon this. It would be good be good to get a consensus from the community for the different notations used in user API in this period.

• Implement Magmas, FreeMagma, SemiGroup, FreeSemiGroup, Monoid, FreeMonoid.

• The implementation of Todd-Coxeter would be a major task and a good basis for other operations. Probably that could be a large part of a GSoC job, since a large number of methods would depend upon it, this will the most tricky and interesting part of GSoC period as well.
• Implement the low-index algorithm of Coset-Enumeration.
• Testing will be done in this period, majorly with the use of GAP software.
• Merge the PR of Group, FreeGroup, FpGroup.
• Implement Tietze Transformation (it can be time defying to include it)

• Implement Rewriting Systems.
• Knuth Bendix Rewriting System for checking the equality of elements of FreeSemiGroup, FreeMonoid, FpGroup and related algebraic structures.
• Implement Reidemesteir Schreier method using the paper http://staff.itee.uq.edu.au/havas/1974h.pdf by George Havas.
• Complete any task if remaining.
• Removing Bugs

I have been working with SymPy for quite sometime now (almost a year now). I am very much familiar with the things that require my attention and to what extent in SymPy. I feel i have the mathematical background for the project, since i have already taken a basic course in Abstract Algebra (we were taught using I N Herstien), with an ongoing course in Theory of Computation. Also after that i started reading the "Rotman JJ" book (which is a little more advanced). More positive point being i already have spent quite sometime trying to implement the some of the PRs for FpGroup in SymPy though it has not been merged since i could not get enough time during my ongoing college semester and i want to take GSoC as an opportunity to get all that work done in the coming summers.

I am now also familiar with the working of GAP software, using it for more than 4 months now, i have asked quite a few questions about its source code on its mailing list. Though there may be some loose ends since it may be hard to explain the ideas in my proposal without getting too deeply involved in the implementation, since getting very strictly to the point of implementation of complicated algorithms like Todd Coxeter Algorithm is not easy. Though these gaps can be filled in since i can use the community boding period to look deeply into the implementation of the algorithms.

I have got no major plans for summer and i will contribute full time 40 - 50 hours a week. My college restart in mid July but i will still be able to contribute full time since there will be no exams or tests. After contributing to SymPy till now, i feel like i should take up one module and be responsible for the future developments (like done in GAP, they have authors listed in top of modules), so i will chose module of Group Theory. So i "will" stick around for quite sometime even after the summer ends.

I think this project will be a great boon in Group Theory implementation. I have developed this proposal in consultation with my mentors. I have had discussions with Kalevi Suominen, Aaron Meurer, Harsh Gupta.

1. Hulpke CGT-Notes

2. Knuth Bendix Algorithm

3. 2012 Google Groups Alexandar Makelov Proposal Discussion

4. GAP FGA Manual

5. Magma Handbook

6. SageMath Documentation

7. Reidemeister Schreier Algorithm paper by George Havas

8. Kalevi Suominen's gist on Group Implementation in SymPy