GSoC 2015 : Finitely presented groups in Sympy - sympy/sympy GitHub Wiki

Name            : Kaushik Varanasi
Github Handle   : kaushik94
E-mail          : [email protected]

I am a pre-final year CS Undergrad student at DA-IICT(Dhirubhai Ambani Institute of Information and Communication Technology).

In mathematics, one method of defining a group is by a finite presentation. One specifies a set S of generators so that every element of the group can be written as a product of powers of some of these generators, and a set R of relations among those generators. We then say G has presentation:

< S | R >

Informally, G has the above presentation if it is the "freest group" generated by S subject only to the relations R. Formally, the group G is said to have the above presentation if it is isomorphic to the quotient of a free group on S by the normal subgroup generated by the relations R. Currently sympy represents the groups as groups of permutation on a finite set. It would be great to be able to represent groups as finitely presented groups, a more ambitious plan would be to incorporate matrix representation of groups as well but its beyond the scope of this proposal.

I code on a Fedora 19, with gedit as my text editor and python 2.7.X as my primary language. Its simple and clean. Though the focus of my university is on C and Java, I self taught myself python(from "learn python the hard way") and it has been my primary programming language since 2 years. I like it because its almost as simple as writing pseudo-code and I need not worry about pointers and seg-faults. For the past 3 years I have been competitive programming and implemented few projects in python like training a naive-bayes classifier through grid computing, and a website of mine which got funding from the university. It helps you know the people around you who like the same music as you do.

As the concept of abstract algebra and group theory is very diverse, I would like to turn my focus to implementing some of the basic and core functionality during the summers. The idea is to be able to represent finite and finitely presented groups in sympy so that these can be inherited by more complex group objects that I(or someone else) might implement after the summers. Some amount of work regarding permutation groups has been done already but we do not have a proper way to represent a group.

One of the best software around for this purpose is GAP which is written in C. So most of the implementation and representation and the underlying algorithms are in the lines of GAP.

The context of implementation is strictly specific to finite groups. Infinite groups(though a few of them hard-coded) are not supported.

Even Though theoretically groups subclass magmas and semi-groups( as done in GAP ), I would like to ignore this structure and present groups as the basic objects(Group objects are constructed from group elements which would work like symbols with assumptions in sympy currently) for abstract algebra since these are the most commonly used. Later the hierarchy can be built up when required.

general purpose

These classes can be used in any group theory module that might be constructed.

• A generic Group class from where other complex group structures like eg, FreeGroup, Galios group, Lie Groups, Matrix Groups, Mathieu groups, PermGroup etc can subclass from .
• A generic Group element class which works behind the scenes and inherits from sympy Symbol. This acts as a generator for the groups in case of presentation.

Project Specific

• FpGroup : which super-classes .....

An abstract representation or declaration of a group should be possible like for example:

>>> from Group import Group, AbelianGroup
>>> g = Group()
>>> g
<Group.Group instance at 0x7fee2e1583f8>
>>> a = AbelianGroup()
>>> a.is_abelian
True
>>> a.is_finite
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "Group.py", line 11, in is_finite
    raise NotImplementedError()
NotImplementedError

Every finite group can be represented as a finitely presented group.Finitely presented groups are created as quotient groups of Free groups.

A free group is can be constructed from group elements or by specifying the number of generators to the group(As implemented in GAP). Like for example:

>>> from Group import FreeGroup
>>> G = FreeGroup(3)
>>> print G
Free Group on generators: e0, e1, e2.

Or alternatively by passing a list of names of group generators like for example:

>>> from Group import FreeGroup
>>> G = FreeGroup(['a', 'b', 'c'])
>>> print G
Free Group on generators: a b c

Here a, b, c are the names of group elements given by us. They will be sub-classed from sympy Symbol.

>>> from Group import FreeGroup, FinitelyPresentedGroup
>>> F = FreeGroup(['a', 'b', 'c'])
>>> a, b, c = F.generators()
>>> print F/ [a**2/b, c**3]
Finitely presented Group on : < a b c | a**2/b c**3 >

The Quotient group of this Free Group by the normal subgroup generated by relations on elements a, b, c where a**2=b and c**3=e. This kind of representation is already somewhat followed for Rings and Modules in sympy.polys AGCA section. But there are already some hard-coded groups in sympy(and more can be implemented always). For example currently in sympy:

>>> from sympy.combinatorics.named_groups import DihedralGroup
>>> G = DihedralGroup(4)
>>> G
PermutationGroup([
    Permutation(0, 1, 2, 3),
    Permutation(0, 3)(1, 2)])

If we could implement a presentation for groups in sympy, it would be something like:

>>> G.isFpGroup()
False
>>> P = G.asPresentation
# This will return an FP group that is isomorphic to the given PermGroup(which in this case is D_4).
>>> P
Dihedral group of size 4  : < e0, e1 | e0**n, e1**2, (e0*e1)**2 >
>>> P.isFpGroup()
True

properties of a finitely presented group

• Boolean Properties: is_finite, abelian, cyclic, polyhedral, symmetric, alternating, trivial, multiplicative, additive, etc.
• Generators
• Relations
• size
• category : We should be able to print out the category of an abstract group.

>>> H = FiniteAbelianGroup()
>>> H.category
Category of finite abelian groups
### Even more
>>> H.super_category
[Group, AbelianGroup, FiniteGroup] 

• cayley_table

# continuing
>>> P.cayley_table
[ [  1,  2 ],
  [  2,  1 ] ]

Functions of a group

• Morphisms: homomorphisms
• Coset Enumeration: word problems, semi-solvable functions like isFinite, order etc.
• Direct_products
• Tietze Transformations
• basic : Conjugacy class, subgroups, cosets, actions and stabilizers.
• very ambitious : group cohomology.

Most of the ways in which I would be implementing the above functionality are in the lines of a book that I am currently reading " Handbook of computational Group theory ". For reference purposes I would be using " Advanced modern Algebra " by Rottman.

community bonding

coding period

• week 1(May 25 - June 1):
• week 2(June 1 - June 8):
• week 3(June 8 - June 15):
• week 4(June 15 - June 22):
• week 5(June 22 - June 29):
• week 6(June 29 - July 6):
• week 7(July 6 - July 23):
• week 8(July 23 - July 30):
• week 9(July 30 - Aug 6):
• week 10(Aug 6 - Aug 23):

Off season

[1] Derek F. Holt, Bettina Eick, Bettina, Eamonn A. O'Brien, "Handbook of computational group theory", Discrete Mathematics and its Applications (Boca Raton). Chapman & Hall/CRC, Boca Raton, FL, 2005. ISBN 1-58488-372-3

[2] Joseph J. Rotman, "Advanced Modern Algebra". Prentice Hall, 2002. IBSN 0-13-087868-5