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

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), 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. Most computational questions about finitely presented groups are semi-decidable.

The project can be divided into 3 parts: 1. Implementation of classes like Group, GroupElm, Identity, FreeGroup, FreeGroupElm, FpGroup, FpGroupElm, Monoid, Semigroup etc. 2. Implementation of algorithms like Todd Coxeter for Coset Enumeration, Reducing words of FreeGroups. 3. Rewriting Systems and Knuth Bendix Completion procedure for strings, Reidemeister-Schreier algorithm.

For the first part:

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

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'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"). Not all the mathematically equal elements are printed in the same way.

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

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.

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 = 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**04---- 1
True

>>> (g.1**2*g.2**4).equals(g.1**0)FreeGroup---- 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

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
• Assosciative words

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

These type of improvements are possible in Python.

(Detailed treatment of both theoretical and practical aspects of coset enumeration is there in Sim94)

Even the simplest versions of coset enumeration seem rather complicated. Basic questions like "is G finite?" or "is G trivial?" can be semi-decidably answered by this 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.

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

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.

Return the rewriting system corresponding to the finitely presented group. This rewriting system can be used to reduce words with respect to the relations.

The GAP software provides powerful tools for analyzing groups, so it won't 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 and i can start coding right away.

The implementation of Todd-Coxeter would be a substantial task and a good basis for other operations. Probably that could be a large part of a GSoC job.

I have been working with SymPy for quite sometime now (almost a year now). I'm 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 Herstien). 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 OOP classes for FpGroup in SymPy though they have not been merged since i could not get enough time during my ongoing semester and i want to take GSoC as an opportunity to get all that work done in the coming summers.

Though there may be some loose ends, it may be hard to explain the ideas without getting too deeply involved in the implementation. since getting very strictly to the point 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 algorithm.

1. Hulpke Notes

2. Wiki article

3. Knuth Bendix ALgorithm

4. 2012 Google Groups Alexandar Makelov Proposal Discussion

5. 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. GAP FGA Manual

7. Magma Handbook

8. SageMath Documentation