GSoC 2017 Application Valeriia Gladkova: Group Theory - sympy/sympy GitHub Wiki

About me

Name and Contact Details

Name: Valeriia Gladkova

University: University of Oxford, UK

E-mail: [email protected]

GitHub username: valglad

Personal Background

I was born and raised in Russia but about 3 years ago I came to the UK to study. I was thinking of doing Computer Science at uni but on further reflection realised that my interest in programming is a consequence of my broader interest in maths. Now I am a second-year mathematics undergraduate. I enjoy the course a lot, particularly the pure side of it, however, it doesn't involve as much programming as I'd like to so I do some in my free time.

Programming background

I started programming about 5 years ago when I was introduced to Pascal at school. I used it for writing some simple tools for code-breaking (frequency analysis, a basic substitution routine, Vigenere cipher encoder/decoder, etc.). Then I discovered Project Euler (https://projecteuler.net/about) which provided me with fun programming puzzles that appealed to my mathematical side as well. By this point I had also learnt Octave and a bit of C. Not having any programming-related courses as part of my degree, I read Computer Science lecture notes in my free time, e.g. I learnt Haskell (which I think is a really cool language) alongside CS undergrads. Additionally, I can now program in Java and Python. I've never formally learnt either of them: I picked up Java while reading the source code for a friend's coding project and tinkering with it, and Python while helping another friend to find and resolve a bug in their code. Until this summer I hadn't really worked on any big projects of my own, so I thought it was time to change that and started writing a Java app that created a bunch of particles on the screen with arbitrary velocities and let them collide around. I don't have much time to work on it so it's still very raw but there are quite a few features that I'd like to implement for it when I have time.

I code on Ubuntu 16.04 and use gedit as my editor (there's no particular reason for it: I started with it a while ago and it worked well so far). My experience with Python is somewhat limited but I have full confidence in using it because it has a very intuitive syntax. I used to find it a bit annoying that it was so fussy about indentations but now I think enforcing good-looking programming layout is ultimately a good thing. A lot of people mention how list comprehensions are a cool feature and I definitely agree. I first came across list comprehensions in Haskell and I was delighted to find them in Python too.

I only started using git fully 2 months ago but I've pretty much got the hang of it now.

Patch Requirement

  • Merged #12150
  • Merged #12222
  • Merged #12329
  • Open #12264
  • Merged #12455 - group theory related; would be useful for implementing some of the things in this proposal

Project

I'd like to work on further developing the Group Theory module because I've enjoyed linear algebra and group theory at uni. At present I've taken two Linear Algebra and one "Groups and Group Actions" courses. I've followed these up with an optional "Rings and Modules" course and have chosen to do further group theory next term. I'm considering specialising in this area as a mathematician and while I'm not sure of that yet, I'd certainly love to explore the computational aspect of the subject.

Subgroups

There have been two Group Theory GSoC projects in previous years and a lot of important work has been done, however, some basic functionality, like that related to subgroups is still missing, and the module looks incomplete without it. Firstly, I think it would be nice to have a method .subgroup(gens) for returning a subgroup of a group generated by gens. At the moment, a subgroup can only be specified as a list of generators but one would expect to be able to make it into a group in its own right. For finite index subgrous of FpGroups, this will be easy as all of the actual work is done by the already implemented Reidemeister-Schreier algorithm. It has been mentioned on the SymPy group theory gitter channel that elimination techniques for Reidemeister-Schreier can be improved so I'll look into that as well. Subgroups of PermutationGroups are even simpler as they are just PermutationGroups generated by supplied gens.

When this is done, it would make sense to give groups the attribute .parent - this could make .is_subgroup() a bit more efficient. Currently, .is_subgroup() is only available for PermutationGroups. With the introduction of the .parent attribute, it can be added for FpGroups as well, albeit with limited functionality. The latter can be later extended with homomorphisms.

>>> G = SymmetricGroup(5)
>>> H = G.subgroup([Permutation(1,2,3),Permutation(2,3)])
>>> H.parent == G
True
>>> G.parent
None

Once this is done, it remains to go through the functions that take a list of generators for a subgroup as an argument and add the possibility of passing group objects.

Special types of subgroups

The special types of subgroups that would be nice to have are normal closures, centres and centralizers. These are already implemented for PermutationGroups. For finite FpGroups, coset_enumeration() gives an isomorphism that allows moving to a PermutationGroup, performing the calculations in there and then using the isomorphism again to move back to the original FpGroup. This is great as it automatically gives a finite FpGroup all the functionality of a PermutationGroup. However, to make this work, it is necessary to have group homomorphisms and methods related to them implemented. See the homomorphisms section for details.

Additionally, Sylow subgroups could be of interest to a group theorist and they are not implemented even for PermutationGroups. An algorithm for computing them is described in [1], Chapter 4. If everything goes according to plan and I have time, I would like to implement this as well, for completion. By the use of the isomorphism described above, it would work for finite FpGroup as well.

Infinite groups handling

Infinite groups are largely a problem. A number of methods for FpGroups depend on coset enumeration which currently can take a really long time to terminate (with an error) if an infinite group is passed to it. This could be resolved by specifying a smaller maximum coset table size to allow termination in sensible time at least. The default number should be possible to change by the user when calling the functions that make use of coset enumeration. At the moment, when the (huge) maximum table size is exceeded, the returned error message says "Try with a greater value max number of cosets" but the only way to change this number is manually in the source code. Perhaps, the error message should also note that the subgroup index or the order of the group may be infinite, though there is no guarantee that it is the case just because coset_enumeration takes a long time. However, there are a couple of techniques that could help determine if a group is infinite from the start to avoid wasting time as it is done in GAP (see [2]).

One obvious check is to see if there is a generator that is not involved in any of the relators - then the subgroup generated by it is infinite (and so is the whole group).

A more sophisticated method is to consider G/G', the quotient of G by its commutator. This is an abelian group and so the primary decomposition theorem for the integers apply to it, i.e. G/G' is isomorphic to ZrxZr1x...xZrn where r1,..., rn are prime. If r =/= 0, the quotient is infinite and hence so is G (otherwise we don't learn anything about the finiteness of G). In Gap the coefficients r1,..., rn and r zeros are returned by a function called AbelianInvariants. I will implement this and it could be used with integers in the rings module and eventually generalized to all rings.

Another thing to check for is if there is a cyclic subgroup of finite index i. If there is, we can calculate the order j for the quotient by it (which will be either smaller than i or infinite) and obtain the order of G by i*j. In GAP, this is achieved by a function that again makes use of coset enumeration. There is no guarantee of successful termination for this method and trying can take a while, but if it does succeed, it can be known for sure whether or not G is infinite.

GAP also has a function called NewtonInfinityCriterion which sometimes succeeds when the above methods fail but its implementation depends on homomorphisms, certain quotient groups and central series which are not yet possible for FpGroups. This could be something to think about implementing once the homomorphisms are in place.

The algorithms for all of these functions can be found in the source code of GAP.

Homomorphisms

Create a GroupHomomorphism class. There are similar objects defined for rings and modules in sympy.polys.agca but none are group specific, e.g. they wouldn't work for noncommutative groups. A homomorphism can be defined by specifying the images of the generators of the group under the homomorphism. homomorphism(G, H, gens, images) will return a GroupHomomorphism object with domain G and codomain H. If G or H aren't specified, they will be assumed to be generated by gens or images respectively. Here gens is a list of generators of G and images is the list of their images under the homomorphism. If gens is supplied as a proper subset of all the generators of G, the other generators will be assumed to be mapped to the identity. A call to homomorphism() will first check if the specified arguments indeed induce a homomorphism using a procedure described in [1], Chapter 3. GroupHomomorphism will have .apply() (application of the homomorphism to a group element or a list of elements), .kernel and .image methods (which return subgroups of either codomain or domain). For permutation groups, an FpGroup representation is necessary for this purpose. The methods for finding relators for a given PermutationGroup are described in [1], Chapter 6 and is among the things that need to be implemented. I have made a start on this already by writing Permutation Group methods for finding a right coset transversal, coset representatives in the transversal for a given element and finally the standardised coset table for a given permutation group (this is the nature of the last PR in the Patch Requirement section).

>>> G=PermutationGroup((0,1,2,3),(0,1))
>>> H=PemutationGroup((0,1,2),(0,1))
>>> theta = homomorphism(G,H,G.generators,[(0,1),(0,2)])
>>> theta.apply((0,3))
(1,2)
>>> K = theta.kernel()
>>> K.is_subgroup(G)
True

When this is in place, I can implement isomorphisms of finite FpGroups to PermutationGroups based on coset enumeration and thus make it possible to use PermutationGroup methods on FpGroups.

Rewriting systems

This is necessary for computations with homomorphisms and will allow to test if two elements in the group are the same which is another feature one would expect to find in a group theory module. This was proposed by Gaurav Dhingra in last year's GSoC Group Theory project (see [3]) but wasn't implemented. As was suggested there, a method .rewriting_system() should be implemented using techniques similar to those used in GAP, in particular the Knuth-Bendix algorithm (see [4], [5]). This should return a RewritingSystem object which would be a separate class with attributes such as .alphabet (returning the list of the generators of the group it belongs to) and .rules (a list of reduction rules used by the system), and a method for reducing a given word of the parent group.

Proposed Timeline

My last term doesn't finish until June 24, and I am going to have exams in the last week. I will do minimum amount of work in the actual exam week and I am likely to spend only about 30 hours a week in the run-up to it. However, after that I'm completely free and will do 50+ hours a week so on average it'll be at least 40 hours a week over the whole summer.

In this timeline, when the weeks reserved for parts of the project overlap, I am going to work on two parts in parallel or spend the start of the overlapping week doing one thing and the rest doing the other.

Week 1

Implement .subgroup() method for FpGroups and look into improving the elimination techniques of Reidemeister-Schreier. .subgroup() for PermutationGroups. .parent. Go through group functions to add support for passing groups. Create a PR.

Week 1-2

Sort out infinite groups. Equip the function order() with the methods of testing if the group is infinite. Make sure things terminate by lowering the default maximum table size and allow the user to change it when calling functions. Create a PR.

Week 3-4

Somewhere around week 3 and 4 of June I have exams so I won't have much time to do work. Hence two weeks scheduled for easy things.

Start writing the GroupHomomorphism class. .apply, kernel, image, is_homomorphism functions assuming rewriting systems are already implemented (this will actually be done in the next couple of weeks).

Week 5-6

Choosing random elements of FpGroups. Rewriting systems. Knuth-Bendix. By the end of this functions written for homomorphisms can be tested.

Week 7-8

FpGroup representation for PermutationGroups.

Week 8-10

PermutationGroup representation for finite FpGroups using coset enumeration. Tests for homomorphisms using GAP. Create a PR.

Week 10

Add PermutationGroup functionality to FpGroups. Test using GAP.

Week 11

Sylow subgroups of Permutation groups. Add the function for FpGroups. Test. PR.

Week 12

Tidy up, finish documentation, sort out all PR issues, submit a report.

After summer, I have another month before the end of my vacation so I'm going to keep working on any unfinished stuff and fixing leftover bugs. After that I'll probably switch my attention to other issues, e.g. solvers unless there is something in particular that I'd like to implement for group theory.

References

⚠️ **GitHub.com Fallback** ⚠️