GSOC Wrapup

Well, GSOC 2013 is officially over.  I thought I’d write up a summary of what I accomplished over the last 14 weeks.

-Classes for types A, B, C, D, E, F, and G which stores information about their Dynkin diagrams, Cartan matrices, roots, and size

-A class, RootSystem, which allows users to work with the root system of a given Lie algebra.  It can generate all the roots of a Lie algebra, and has methods for adding roots together.

-A class WeylGroup, which is about the Weyl group of a given Lie algebra.  It gives the size and name of a given Weyl group as well as the matrix form of an element, and an element’s order.

-Methods for displaying the Cartan matrix and Dynkin diagram of a Lie algebra.

 

That’s pretty much it.  I had a great time working with SymPy this summer!

A late update

This week has been work on the WeylGroup module, unsurprisingly.  I’ve implemented element_order and matrix_form for types A, B, C, D and G2, and matrix_form for E and F.  I think that implementing order for E and F is going to be much more difficult, because it’s not easy at all to realise those two groups as permutations.  I’m going to look for the next day or two to see if I can find a clever way of doing it, but otherwise I’ll just utilise matrix_form to get the matrix representation of the element of the WeylGroup and then just brute force it to find the order of the element by just finding what power of the matrix gives the identity. 

I also changed bits in in the root_system PR to utilise Rational(x, y) instead of using floating point numbers. 

I’m hoping to have most major coding done by the 13th, so I can spend the last 10 days of GSOC writing up more detailed docstrings and fixing other minor errors.

 

Sorry for the short update, but I’m not feeling particularly verbose today.

More thoughts on the Weyl group module

So this week has been a lot more thinking about the Weyl group module.  I feel as though I didn’t accomplish much, but I have spent a fair amount of time researching and thinking.  I should note that I also did some fixes on the RootSystem module (fixing some doctests and whatnot). 

After conferring with David, I’ve concluded that I want to implement a method that displays the Coxeter diagram corresponding to a Weyl group (i.e. the undirected Dynkin diagram), and that the best way to proceed with the Weyl group module is to implement all the Weyl groups as permutation groups.  This makes sense, because as I noted in my last post, the Weyl group for type A is the symmetric group, and the Weyl group for B&C is the hyperoctahedral groups, which canb e thought of as permutations on the set [-n, …, -1, 1, … n].  The Weyl group for type D is is a subgroup of the hyperoctahedral group. 

This would make things like computing the order of an element of the Weyl group quite easy, as I could take input from the user and then get the permutation associated with it, and then use methods from the Permutation class to do what I want.  Now, the obvious challenge with this is that the Permutation class only allows permutations on positive integers like [0, … , n].  So this presents problems with the hyperoctahedral group, since it include permutations on negative integers.  I reckon that I do not have the time to rewrite the entire Permutation class to allow it to act on an arbitrary set.  So, I am going to map the set [-n, …., -1, 1, …. n] to a set of positive integers.  So I’m still thinking about how I want to do that. 

Furthermore, upon the suggestion of David, I think that I will try to include information about the hyperoctahedral group in the named groups module. 

Lastly I am also trying to find more concrete information about the Weyl group of type D; I know that it is a subgroup of index 2, but I’m not sure what exact permutations and stuff that it corresponds to. 

So yeah.  This coming week, my plan is to figure out how I want to write the permutations of the hyperoctahedral group as permutations on positive integers, and then to take input from the user in the form of products of simple reflections, and generate the corresponding permutation, at least for types A, B, and C.  

For example, given A3, the Coxeter diagram is 0—0–0, and the generating reflections are r1, r2, r3, and the Weyl group is S4.   We can think of r1 as the permutation (1,2), r2 as (2,3), and r3 as (3,4).  So if the user gave the input r1r2 that would be the permutation (1,2)(2,3) = (1 3 2).  Oh, I also need to remember that the Permutation class starts with 0 instead of 1, so I need to remember to take that into account.

This week I will also implement a method that gives the Coxeter diagram of a given Weyl group.  This should be very easy, given the Coxeter diagram is the undirected Dynkin diagram. 

Weyl Groups

So, for each semisimple Lie group, we have a Weyl group.  It is a subgroup of the isometry group of the root system.  Specifically, it’s the subgroup that is generated by reflections through the hyperplanes orthogonal to the roots.  Therefore, Weyl groups are reflection groups, and so a Weyl group is a finite Coxeter group. 

Now, if we take a Lie algebra’s Dynkin diagram and delete all arrows from it, we have its Coxeter diagram, which encodes information about the reflections which generate the Weyl group, as follows.  The vertices of the Coxeter diagram represent the generating reflections of the Weyl group, s_i.  An edge is drawn between s_i and s_j if the order m(i, j) of s_i*s_j is greater than two.  If there is one edge, the order m(i, j) is 3.  If there are two edges, the order m(i, j) is 4, and if there are three edges, the order m(i, j) is 5. 

We note that the B series and the C series have the same Coxeter diagram, and hence have the same Weyl group, which is the hyperoctahedral group, which is the group of symmetries of a hypercube.  Considered as a permutation group, it is the signed symmetric group of permutations of the set  { −n, −n + 1, …, −1, 1, 2, …, n } such that π(i) = −π(−i) for all i.  The Weyl group of D_n is a subgroup of index two in the hyperoctahedral group.  The Weyl group of A_n is the symmetric group on n variables. 

So, I’m now looking at working on the class WeylGroup.  Obviously it’s easy enough to write out the generating reflections, but I’m not sure how exactly I want to proceed from there.  Perhaps a function where a user can specify a reflection as a product of the generating reflections (e.g. input s1s2s5 or something…) and then have the function output its order?  I’m also thinking about how to I want to represent a given reflection.  I’m leaning towards representing it at the product of the generating reflections.  We’ll see.  I also have included a function which returns the order of a given Weyl group.  So yeah, that’s where I’m at.  This week has been generally slow in terms of concrete output, but I’ve been spending a lot of time reading and researching (as Weyl groups aren’t my specialty) and generally contemplating where I want to go with this class.

Week 9

This week I have been doing more work with the RootSystem class.   I created a PR (https://github.com/sympy/sympy/pull/2382) with everything that I accomplished on it last week, just so that it’s up there and people can comment on it. 

This week, I implemented the root adding functions.  One function just takes any two simple roots and adds them together, and returns the new root.  It functions by having the user input two integers (which must be less than the rank of the lie algebra) and takes these integers to be the keys in the dictionary of positive roots, and retrieves the corresponding simple root.  Then it just add adds the lists corresponding to the roots (by adding together the two first elements, the two second elements, etc) and returns a new list, which is the new root. 

 

Then, I also implemented a function which takes two roots as input, and if their sum is a root, returns their sum as a new root.  To do this, I first needed to have all the roots of a given Lie algebra available.  That is why last week I implemented a method for generating all the positive roots for A, B, C, and D.  This week I also did that for E, F, and G.  This enabled me to implement a method in RootSystem that generates all the roots of a given Lie algebra, by first getting the positive roots, and then using the positive roots to generate the negative roots (by multiplying each positive root by -1). 

 

Then the method add_as_root works by checking the dictionary of all roots to see if the sum of the two input roots is also a root.  If it’s not, it returns a string saying “The sum of these two roots is not a root”.  Otherwise it returns the sum as a list, as usual.

This week I also worked on documentation and the like for all my functions.  This weekend I’m going to make sure all the doctests pass.  Then, my plan for next week is to start work on the the WeylGroup class.

Week 8

This week I have been working on the class RootSystem. 

The first major decision that I had to make about this class was how to encode the CartanType data, for lack of a better way of phrasing it.   There are numerous ways of doing this, but I think that my solution is somewhat elegant.  Effectively, when one calls an instance of the class RootSystem, it takes an argument, cartantype.  Then, the __new__ function takes the input and sets an attribute of RootSystem called cartan_type as CartanType(cartantype).  The code is:

class RootSystem(Basic):

    def __new__(cls, cartantype):
        “””
        Creates a new RootSystem object.  This method assigns an attribute
        called cartan_type to each instance of a RootSystem object.  When
        an instance of RootSystem is called, it needs an argument, which
        should be an instance of a simple Lie algebra.  We then take the
        CartanType of this argument and set it as the cartan_type attribute
        of the RootSystem instance.  
        “””
        obj = Basic.__new__(cls, cartantype)
        obj.cartan_type = CartanType(cartantype)
        return obj

By doing this, it means that I don’t need to check the argument and see if it is “A” or “B” or “G” or whatever, and then importing the associated class.  I can just call self.cartan_type.rank() or self.cartan_type.simple_root(i), which I think is quite neat. 

 

I’ve also decided to add a method to the base classes that generates all of their positive roots (and since the negative roots are just minus the positive roots, we effectively have the entire root system).  I think that this will facilitate some of the addition methods that I want to implement in RootSystem.  I have so far done this for types A, B, C, and D. 

 

At this point, in RootSystem I have so far implemented a method that generates all the simple roots,  a method for displaying the root space, and then methods which return the Cartan matrix and Dynkin diagram of the Lie algebra.  I am currently pondering on how I want to implement some root addition methods.

 

So yeah, that’s been my week!  To be honest, I think it has been fairly productive, and I am quite pleased about that.

Week 7

(Or maybe week 6. See last week’s post).

This week, I’ve started one new PR (https://github.com/sympy/sympy/pull/2344) which includes the Dynkin diagram functionality for all classes. I had PR 2297 merged, and I’m pretty sure I’ve fixed the merge conflicts for PR 2337 (which is the Cartan matrix stuff).

Talking with David this week, he suggested that I include more technical information and sources in my code, to help explain some of the concepts in Lie algebras. I thought this was a very good idea, and so I’ve started writing some more detailed docstrings, including sources.

Additionally, I changed some of the classes in my code so that instead of using __init__ they use __new__ instead, as is the norm in the sympy code base.

Currently, I am contemplating the root system class I want to write, and what it should contain/accomplish. First off, it will need to generate all the simple roots for a given Lie algebra. This is easy enough to accomplish, using functions from the individual classes, though I need to figure out how exactly I want to go about importing data from things type type_a.py, type_b.py, etc. I think that it would be best to store these simple roots in a dictionary, with the keys being like, alpha1, alpha2, etc and then the values being vector representations of the roots.

I’d also like to have an addition method for adding simple roots together, and as David suggests, a method which would only add roots if the sum was a root.

I’m still internally debating if I want to have the RootSystem class hold all the roots (well, hold all the positive roots, as a reflection would then generate the negative roots) or not. I think it may make some of the above methods simpler, but then it might also just be overkill.

I’ll also have a method returns the root space of a given root system, which is just the span of all the simple roots.

So, yeah, that’s what I’m thinking and planning at the moment. Hopefully I’ll be starting this stuff this weekend.

Week 6

Or is it week 5? I’m no longer sure. My ability to count has decreased dramatically as my number of years studying mathematics has increased.

Excitingly, this week I’ve have two PRs merged, 2259 and 2237. Other than that, this week has been fairly slow. I’ve been battling illness and haven’t accomplished overly much. I’ve generally been cleaning up code for all the types (type_A and type_B are done, since those were in the PRs), and I’ve made definite progress with types C-F. I also think I’ve figured out the ascii art for the Dynkin diagrams.

To do the Dynkin diagrams, I learnt about the join function for strings in python, which made things 100 times easier. For instance, the code to generate the Dynkin diagram of A_n is:

>>> diag = “—“.join(“0” for i in range(1, n+1)) + “\n”
>>> diag += ” “.join(str(i) for i in range(1, n+1))

For example for A_3 it produces a Dynkin diagram that looks like:
0—0—0
1    2     3
which I’m quite happy with. I though that I was going to have to use a loop, but the join command is much more elegant. The code for the other types looks very similar.

So yeah, that’s pretty much where I am. I seem to be getting over this illness, so I hope that I will be much more productive this weekend.

Dynkin diagrams and Cartan matrices

First off, I’ll start by saying I’ve just made another PR (https://github.com/sympy/sympy/pull/2297) which includes the code for the C and D series, as well as the exception Lie algebras of type E, F, and G.

So, this week so far has really been a mix of things, as far as what I’ve been working on. I’ve done a fair amount of (attempting to) clean up code for type_A.py so as to make it ready to actually be merged with sympy master. I think I’m heading in the right direction on that front, though I doubt that I’m all the way there. There are always more typos or trailing white spaces to fix.

I’ve also (more or less) put together Cartan_Matrix.py. Originally, this was going to be a subclass (I think of CartanType? Not really sure what exactly I was thinking when I wrote my proposal). However, once I actually started thinking about things (and after consulting with David), I think it actually makes much more sense to just have a single method, called CartanMatrix. As written, it takes an argument t, and then returns CartanType(t).cartan_matrix. Then, the user can do things like
>>> CartanMatrix(“A2”)
[2 -1]
[-1 2]

As written, the naming convention obviously goes against camel case, and is named as if it were a class. However I’d like to keep it this way. I’m finding it difficult to be able to vocalise /why/ exactly, so I suppose some discussion on this front would be useful/necessary.

This sort of leads on to dynkin_diagram.py. I’m still trying to think/decide whether or not I should go in the same way that I did with cartan_matrix, or if I should make it an actual class. Currently I don’t have anything about dynkin diagrams coded into type_A, type_B etc but it would be easy enough (once I get past figuring out how to do the ascii art and whatnot) to add that into those files. Alternatively, I could just hardcode it into dynkin_diagram.py. I’m thinking that it might make more sense to do things in the same fashion as cartan_matrix, since I don’t really want to have this (potential) class do anything /other/ than display the Dynkin diagram, so it would probably be overkill to have it be a class.

In any case, I suppose that I have a little bit more time to think about this, because I need to figure out how exactly to do the ascii art that will be the actual diagrams. Type A is obviously very easy, because the diagram has no double/triple lines or arrows or weird angles. I want type A to look like:

0–0–0….-0

Type B is again fairly easy:
0–0–0….0=>=0

as is C:
0–0–0…0=<=0
and type F is very similar.

However, type G has a triple line with an arrow, and I'm not sure how to do that. Type E has one edge that sticks up, so it'll take up two or three lines, and I'll need to figure out how to print that out, and similarly for D.

So….that's pretty much what's going on right now. Having typed that all out, I think that I have come to a conclusion on how I want to structure dynkin_diagram.py which is good. It should also be pretty easy to implement things for type_A at the very least, so that's what I'm going to work on tomorrow and Friday. We'll see where that gets me!

On Semisimple Lie Algebras (Part 2)

Let’s continue on from last week.  So, we have a Lie algebra g, with a root system.  Specifically, we want to consider the simple roots of g.  We can define the Cartan matrix A of g as the matrix whose elements a_{i,j} are defined by

a_{i,j} = 2 (alpha_i, alpha_j)/(alpha_i, alpha_i) = <alpha_i, alpha_j>

where the inner product (a, b) is the Killing form: (a, b) = Tr (ad a) (ad b) where ad denotes the adjoint action.  Effectively, the Cartan matrix is one way of encoding the simple roots (and by extension, the entire root system) of the Lie algebra.

Next we want to understand a bit more about Dynkin diagrams.   Given g and its simple roots, we may construct its Dynkin diagram as follows.

For every simple root, draw a dot.  Join the ith dot to the jth dot with <alpha_i, alpha_j><alpha_j, alpha_i> edges.  If the two simple roots alpha_i and alpha_j have different length, add an arrow pointing to the shorter root.  Now, it can be shown that one can classify the irreducible root systems by classifying the connected Dynkin diagrams.  Thus, if we have an irreducible root system Φ of rank l, then its Dynkin diagram is one of the following:

(From wikipedia)

So again, Dynkin diagrams are another way of classifying simple and semisimple Lie algebras.  I think that more or less covers the basics of simple and semisimple Lie algebras, so I’ll leave things there.

 

On the coding front, I’ve finished writing and commenting type_A.py, type_B.py, type_C.py, type_D.py, type_E.py, type_F.py, and type_G.py as well as writing tests.  I’ve got pull requests up for type_A and type_B, and I’ll do the rest this weekend. I’m about to write start writing tests for cartan_type.py.  That will be tomorrow’s project.

I’ve realised that implementing the commutation relations is a huge undertaking (I’d need to first implement matrix representations of every Lie algebra, the adjoint action, actual physical bases and so on) so I’m going to leave that until the end of the project, if I have time.    I’m currently right on schedule, if perhaps a bit ahead, and I want to accomplish everything I listed in my project proposal, and I fear I’d be derailed from that if I were to focus so specifically on commutation relations.

So…that about sums things up.  Til next week!