-
Notifications
You must be signed in to change notification settings - Fork 0
GSoC 2012 Application Aleksandar Makelov: Group theory
Hi, my name is Aleksandar Makelov and I'm currently a freshman at Harvard University. I haven't declared my concentration (major) yet, but I'm certain my main focus will be on mathematics (my primary interest), with strong focus of computer science and physics (my other scientific interests).
I'm from Bulgaria, and my background in the sciences includes many national and international competitions in mathematics and physics (most notably, the International Mathematical Olympiad and the International Physics Olympiad) - and of course the theoretical preparation behind them. Also, now and then during the last five years I taught myself various concepts from computer science (recursive/iterative algorithms, complexity analysis, data structures,...).
Please don't hesitate to contact me by email ([email protected], [email protected]), GitHub (amakelov), or Skype (petko_voivoda).
I've done coding in several high-level languages (C, C++, C#, Python, Scheme); What I like about Python, as a mathematician, is the simplicity and readability of the language which allow for what I find to be very elegant programs. In the fall of the academic year I took a formal introductory course in computer science taught in C which was in part review and in part new to me (especially the part about web programming). The course culminated in an open-ended project, and I chose to write a PHP-based website aimed at extracting information solely from the number of Google/Yahoo/Bing search results for a given query by cross-comparing it with numbers for related queries. I found the idea extremely interesting and immensely enjoyed implementing it!
For over half a year now I've been coding on a Linux workstation (in a virtual machine running under Windows). I've been doing work mainly in gedit recently; several years ago when I was learning Python I was working under Windows using IDLE; I've also done coding in Dr. Racket and Microsoft Visual Studio.
I cannot say I'm considerably fluent in Python, and I see my level somewhere around intermediate. I'm counting on my background in computer science and mathematics, and my experience in other programming languages, and I'm eager to learn how to write programs that are really "pythonic".
I'd heard of git before, but I started using it because of my involvement in the sympy project. I'm still learning the little tricks, but now that I've submitted my first patch I feel more confident about using it.
My intention is to create a module for computation with (exclusively finite and finitely presented) groups. My proposal was motivated by the following discussion on the mailing list:
http://groups.google.com/group/sympy/browse_thread/thread/999f0ad35dd85994?tvc=2
This idea was not originally on the list, but there is some work already done in this direction in sympy (the combinatorics module). I chose the subject because I enjoy abstract algebra and combinatorics and I'm interested in learning more about these subjects and the efficient ways they can be handled by a computer. Also, this academic year I convinced myself that computations, even in rather "small" groups, can become impossible for a human to carry out manually. That's why I'd be extremely happy to have a software for this purpose that I completely understand and I can change as I find appropriate.
I feel I have the mathematical background for the project - this year I'm taking rigorous high-level treatments of Abstract algebra covering Galois theory and Representation theory (see http://www.registrar.fas.harvard.edu/Courses/Mathematics.html : Mathematics 55 and Mathematics 123), and I acquired a solid understanding of many combinatorial concepts through my participation in math Olympiads. Thus I think what makes me a suited candidate is my strong mathematical and not as strong but present CS background and my motivation for the subject at hand.
At first, the group-theoretical framework will be developed by itself (i.e., without relation to other more general abstract-algebraic objects like semigroups or even magmas as is done in GAP), because groups are fairly general and appear in practice more frequently; if there is need to generalize the notion at a later stage this won't be too hard to do.
There will be a Group class with a constructor accepting different presentations of the group in the sort of obvious way:
- if given a list of permutations on the natural numbers, the group object returned will be the group generated by them. It'll be nice to have some basic groups (S_n, A_n, C_n, D_n, ...) hardcoded as a list of generators so that they can be called by name
- if given a list of matrices, the group object returned will be the group generated by them (by multiplication). There are many reservations here. Firstly, if the field (if we use matrix multiplication as the operation, a ring won't work in most cases) in which the matrix entries live is infinite the group may be infinite as well. I was advised on the mailing list that sticking with finite groups only would be a better idea - what would you suggest? Secondly, if the field is finite, the group is guaranteed to be finite as well -- but finite fields are not implemented in sympy. Would it be hard to do along the way? There isn't much theory involved, and I'm familiar with it; but the "Handbook on computational group theory" says that computation in finite fields F_q can be made far more efficient by storing certain information in lookup tables for q up to 10^6. Any suggestions here?
- (optional) if given a list of generators and relations between them, e.g. [(a,b),(a^5,b^2,baba^-1)] meaning generators a,b such that a^5,b^2 and baba^-1 are the identity element, the group object returned will be the corresponding group. This enters the realm of finitely presented groups which are not necessarily finite. Again, I was advised that this can be a bit too much for one summer, but if I find the time to do something in that direction I'll try to.
Important information about the group will be stored in it once computed, to avoid computing it again. This includes:
- basic boolean properties: Abelian, (finite), symmetric, alternating, dihedral, cyclic, simple
- size of the group
- a generating set for the group, in particular one that has nice properties, such as the one produced from the Schreier-Sims algorithm (as a list)
- a base for the group, corresponding to the strong generating set from the previous point
- references to group objects representing subgroups already computed.
Storing the group as the set of all its elements will be avoided at all costs, as it is not necessary for successful computing and it is highly inefficient for large groups (and impossible for sufficiently large groups). The strong generating set from the Schreier-Sims algorithm has the advantage that group elements can be expressed as reasonably short words in this set [1].
- Weeks 1, 2 and 3 (April 23th - May 14th)
- Getting familiar with the book/software sources (e.g. GAP)
- Finding a way to represent groups in sympy that would facilitate eventual extensions of the functionality and the incorporation of groups into a more abstract classification of algebraic objects.
- Week 4 (May 14th - May 21st): Start of coding
- Basic functionality: implementing the group object and the basic methods like handling different representations, and placeholders for basic group properties like finite, finitely presented, Abelian, cyclic, simple, ... that will be used later.
- Redesigning the permutation class for better performance - for example, excluding singleton cycles from the cycle decomposition.
- Weeks 5 & 6 (May 21st - June 4th)
- Orbits & Stabilizers - probably the most basic algorithms, but they are needed all the time in advanced computations
- Schreier vectors and the Schreier-Sims algorithm, base & strong generating sets for a group of permutations - most group-theoretical algorithms rely heavily on first getting such a set for the group at hand.
- Weeks 7 & 8 (June 4th - June 18th)
- Coset enumeration by the Todd-Coxeter algorithm, and consequences: presentations of subgroups H < G of finite index in terms of the presentation of G.
To be continued!
Here's a link to my first pull request that got merged to sympy: https://github.com/sympy/sympy/pull/1146#issuecomment-4600000
Currently I'm working on a small module for manual manipulation of character tables (entering characters, taking direct sums, tensor products and duals of representations, decomposing representations into irreducible ones,...) which was motivated by a math course I'm taking this spring. Also, I have to brush up an even smaller module for determination of the Galois group of polynomials with rational coefficients of degrees up to 4.