Group Theory module for sympy ( GSoC 2015 )

[vamsi kaushik]

Hi,

I am an undergrad CS student. I have done one semesters of Algebra(linear and abstract). I would like to implement group theory module as a part of gsoc 2015. Is it too early, if not is there any development going on in this lines so that I can help ?.

thanks,

kaushik varanasi

[Aaron Meurer]

It's never too early. The earlier you start the better.

There has been some work already, but with group theory, there is
always more to do. I believe there is some stuff on the ideas page
about it. Most of what is already there is in the combinatorics
submodule.

Aaron Meurer

> --
> You received this message because you are subscribed to the Google Groups
> "sympy" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to sympy+un...@googlegroups.com.
> To post to this group, send email to sy...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sympy.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/sympy/eed40389-22d9-43bb-82d1-4de270607732%40googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.

[vamsi kaushik]

Hi Aaron,

I have gone through the source code for group theory currently( Okay, just a part of it !). I see that most of the implementation is centered around permutation groups. I would like to introduce a generic Finite group object from which someone can take off to implement complex groups and structures as well as changing the permutation groups in sympy to inherit from this object. I had an idea of implementing Finitely presented groups for this summer(at least most of the focus would be around this) -  their representation, properties, coset enumeration, Quotient groups and Tietze transformations are a few things that came to mind first. I feel that these would be the basic building blocks of group theory to start with. I would like to discuss details in depth about the idea but I want to know whats your take on this idea itself ?

[Joy merwin monteiro]

Not that it matters, but I would be interested to see something similar to what is being

proposed by Vamsi. It would be nice to have a Group class from which FiniteGroup

could be subclassed, and which I could use as well, if I get around to writing a LieGroup.

Joy

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/fe9141ea-2a0d-4e6f-9a77-7681ece42f08%40googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

--

The best ruler, when he finishes his
tasks and completes his affairs,
the people say
“It all happened naturally”
                                      
                                         - Te Tao Ch'ing

[vamsi kaushik]

Hi Aaron,

I would like to start off by implementing Finitely presented groups in sympy. They and any other work in group theory like the Galios group, Lie group will be subclassed from the generic group class that I would implement first.

So the properties of group would be

• is_finite
• is_multiplicative
• is_abelian
• order
• ....

A finite Group class which creates a finite group specified by the elements and relations among them. A good way to construct a finite group( as given in GAP) is by first constructing a Free Group of these elements and then declaring the Finite Group as the quotient group of this free group eg.

F = FreeGroup("a", "b")

G = f/[(a**2)/b]

Now G is The finite group with elements "a", "b" with the relation a**2 = b. would this be a good idea ?

On Sunday, December 28, 2014 1:35:53 AM UTC+5:30, Aaron Meurer wrote:

[Aaron Meurer]

Yes, I like this. We should be able to define groups by symbolic generators, rather than being forced to use permutations. We will need to be able to support infinite groups as well for this to work (already in your example FreeGroup(a, b) is an infinite group).

Following GAP seems like a good plan, as they have already thought about these things much harder than we have. 

Aaron Meurer

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/9a4d915d-34bb-4fc3-a905-7c2242db93c8%40googlegroups.com.

[vamsi kaushik]

Hi Aaron,

Thanks for the interest. I had actually created a rough draft of my proposal. But I am very doubtful it has the minute implementation details. However I had outlined my idea very briefly in the wiki here. As you have mentioned in an other thread, the implementation is more in the lines of sympy.polys which works on modules. I would like to know your feedback regarding this.

 >We will need to be able to support infinite groups as well for this to work (already in your example FreeGroup(a, b) is an infinite group).

Yes, we can definitely aim to support their representations but i am highly doubtful about being able to implement any algorithms by the end of this summer( But could do that later ). If I were to take up this project, I might want to completely focus on the Finite Groups implementation thoroughly. What do you think ?

Thanks,

kaushik 

> For more options, visit https://groups.google.com/d/op all .

[Aaron Meurer]

On Fri, Jan 30, 2015 at 5:01 PM, vamsi kaushik <kaushik....@gmail.com> wrote:

Hi Aaron,

Thanks for the interest. I had actually created a rough draft of my proposal. But I am very doubtful it has the minute implementation details. However I had outlined my idea very briefly in the wiki here. As you have mentioned in an other thread, the implementation is more in the lines of sympy.polys which works on modules. I would like to know your feedback regarding this.

 >We will need to be able to support infinite groups as well for this to work (already in your example FreeGroup(a, b) is an infinite group).

Yes, we can definitely aim to support their representations but i am highly doubtful about being able to implement any algorithms by the end of this summer( But could do that later ). If I were to take up this project, I might want to completely focus on the Finite Groups implementation thoroughly. What do you think ?

That's fine. Some problems on infinite groups are unsolvable anyway. We can always raise NotImplementedError, or return unevaluated objects.

Aaron Meurer

 

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/28c868af-3c74-4d99-9f80-232599e05dc2%40googlegroups.com.

[Joachim Durchholz]

Am 31.01.2015 um 00:01 schrieb vamsi kaushik:
> Hi Aaron,
>
> Thanks for the interest. I had actually created a rough draft of my
> proposal. But I am very doubtful it has the minute implementation details.
> However I had outlined my idea very briefly in the wiki here

> <https://github.com/kaushik94/Proposal/wiki>.

That looks like a lot of thought and code reading went into it, which is
great.

What's the reasoning behind not subclassing from magma/semi-group?

Regards,
Jo

[Aaron Meurer]

I don't remember if I mentioned this earlier, but for Abelian groups, we should try to reuse as much of the stuff from the AGCA module as possible. It already implements a lot of what you are suggesting for modules, and since Abelian groups are just Z-modules. IMHO, Abelian groups are better thought of in terms of module theory than group theory, but it would be nice to have a group theory interface on top of Z-modules. 

Perhaps we should structure the classes along the definition of a module that a module is a ring and an Abelian group, so that the Z-module representation is just an extension of the Abelian group representation (rather than the other way around). Take a look at the AGCA stuff and see what you think.

Aaron Meurer

--
You received this message because you are subscribed to the Google Groups "sympy" group.

To unsubscribe from this group and stop receiving emails from it, send an email to sympy+unsubscribe@googlegroups.com.

To post to this group, send email to sy...@googlegroups.com.
Visit this group at http://groups.google.com/group/sympy.

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/54CD54F9.5060201%40durchholz.org.

[vamsi kaushik]

Hi Aaron

>I don't remember if I mentioned this earlier, but for Abelian groups, we should try to reuse as much of the stuff from the AGCA module as possible. It already implements a lot of what you are suggesting for modules, and since Abelian groups are just Z-modules

I completely agree.

> Perhaps we should structure the classes along the definition of a module that a module is a ring and an Abelian group, IMHO, Abelian groups are better thought of in terms of module theory than group theory, but it would be nice to have a group theory interface on top of Z-modules.

I am not quite sure about this. I might be completely wrong, but just my two cents: Module theory is more about ring action like group actions rather than the group itself, like vector spaces for fields. So by definition even though ring action over an abelian group is a module ( If that is what you meant by "Ring and abelian group"), I think we should better not use this as a subclass structure because they are fundamentally different. And moreover I feel Module theory should be left aside to study ring actions extensively, while being able to have their representations in group theory as well. Like you said Z-modules can inherit a lot from AbelianGroups while still being a part of module theory. Again I have little knowledge of ring theory so clarify me if I am wrong. what do you think ? 

> so that the Z-module representation is just an extension of the Abelian group representation (rather than the other way around).

Yes.

> Take a look at the AGCA stuff and see what you think.

It looks a lot like what I had in mind. Though I din't read every line of it, I am sure it would be a lot helpful for me and will focus more when I start implementing.

I have few doubts,

What do you think so far ?

Are there any areas in group theory where sympy would like to focus ?

Thanks,

kaushik

--
You received this message because you are subscribed to a topic in the Google Groups "sympy" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/sympy/xH18C-g-ySQ/unsubscribe.
To unsubscribe from this group and all its topics, send an email to sympy+un...@googlegroups.com.

To post to this group, send email to sy...@googlegroups.com.
Visit this group at http://groups.google.com/group/sympy.

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/CAKgW%3D6KfH6Bw%3D2yfS6R1iBjHeXC10On_Uk4gr6sNBqyiWDM6Bw%40mail.gmail.com.

[vamsi kaushik]

Hi Jo,

> That looks like a lot of thought and code reading went into it, which is great.

Thanks for the interest Jo. But it still needs work, in the sense that I can't narrow down on things that should/ can be implemented in the summers. Would be great if you could think of areas where I should focus more.

> What's the reasoning behind not sub classing from magma/semi-group? 

I was very wrong about the semi-groups part. But the reason behind magma is that it is not so widely used in real world applications. My aim is to write a module for group theory so that it helps to see quantum mechanics, polynomials, geometry from a different viewpoint. So I am more focusing on things that have a wider impact. I also found SE discussion quite informative. Tell me what you think.

Thanks,

kaushik

[Joachim Durchholz]

Am 01.02.2015 um 22:33 schrieb vamsi kaushik:
> Hi Jo,
>
>> That looks like a lot of thought and code reading went into it, which is
> great.
> Thanks for the interest Jo. But it still needs work, in the sense that I
> can't narrow down on things that should/ can be implemented in the summers.
> Would be great if you could think of areas where I should focus more.

I know what groups, magmas etc. are, but I have far too little
understanding of these areas of math to determine what would be useful
and what wouldn't, so I can't advise.

I'm coming from the program architecture side of things, so if you're
unsure which of two design choices are more extensible, maintainable and
whatnot, I can help - but I wouldn't know what kinds of extensibility
are the most useful.

>> What's the reasoning behind not sub classing from magma/semi-group?
> I was very wrong about the semi-groups part. But the reason behind magma is
> that it is not so widely used in real world applications. My aim is to
> write a module for group theory so that it helps to see quantum mechanics,
> polynomials, geometry from a different viewpoint. So I am more focusing on
> things that have a wider impact. I also found SE discussion

> <http://math.stackexchange.com/questions/324253/are-there-real-world-applications-of-finite-group-theory>

> quite
> informative. Tell me what you think.

Sounds like it's a nice guidance about what kinds of things one might
want to solve with a computer algebra system, and if these things aren't
possible right now, implementing these would make SymPy more useful.

My own angle is more along the lines of "please check whether the SymPy
representation of Magma/Group/whatever already has what you can use for
your work, and see what changes might uncover more synergies of that kind".
I.e. try to keep code duplication down, try to leverage what code
exists, that kind of stuff.
Don't worry if you don't find anything. If somebody else finds
exploitable parallels later, the code can still be reworked. It would be
nice you were around to do that at that point in time, but if your code
is well-written, somebody else should be able to do that, too.

HTH
Jo

[Aaron Meurer]

To be clear, I don't think that a Module class should necessarily subclass an AbelianGroup class. Using subclasses to represent shared relationships between mathematical objects is tricky. I personally don't think of every module as being an Abelian group. I think of every module as containing an Abelian group as part of its structure. Mathematically we might say a module is a triple (R, M, *) where R is a unital ring, M is an Abelian group, and *: R x M -> M is an operation satisfying some identities. 

From a programming perspective, I would expect an AbelianGroup object to have a lot of methods on it that are very group theoretic, and it would be distracting at best to have these methods all be inherited directly into a Module object. I would rather expect to be able to do something like M.as_abelian_group().some_group_theory_method.  

Aaron Meurer

To unsubscribe from this group and stop receiving emails from it, send an email to sympy+un...@googlegroups.com.

To post to this group, send email to sy...@googlegroups.com.
Visit this group at http://groups.google.com/group/sympy.

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/CAK61vZooxm6N%2BmNaUCeRKoDkziCYw%3D3At_FGH6MCwd2spjze%3DA%40mail.gmail.com.

[Joachim Durchholz]

Am 01.02.2015 um 23:51 schrieb Aaron Meurer:
> To be clear, I don't think that a Module class should necessarily subclass
> an AbelianGroup class. Using subclasses to represent shared relationships
> between mathematical objects is tricky.

It's usually impossible to do cleanly if the class offers ways to modify
its data. E.g. if you have a Rectangle class with a transform(matrix)
function that updates the Rectangle in-place, then there's no way to
make a clean Square subclass because it cannot uphold the contract for
transform().

If you avoid in-place updates (as SymPy does), that's not a problem.

> I personally don't think of every
> module as being an Abelian group. I think of every module as containing an
> Abelian group as part of its structure. Mathematically we might say a
> module is a triple (R, M, *) where R is a unital ring, M is an Abelian
> group, and *: R x M -> M is an operation satisfying some identities.

Agreed. Inheritance does not work well in this case.

I have spent quite some years toying with exactly this kind of problem,
and I now know for a fact that it's a relatively unique issue.
For Module, it would actually work; the real issues arise with Ring,
which is "twice a Monoid", once for + and once for *. This works fine
until you pass a Ring object to a function that expects a Monoid,
because the function won't know whether the caller meant to use + or *
for the Monoid operator.

The tricky part here is to judge whether one should favor composition or
inheritance; for Module, I don't know, there's no real reason to avoid
the inheritance because the multiplication is not even a Monoid, so
there's (probably) no room for confusion.
I'd probably still stick with composition, simply to be similar with
Ring. Similarities make it easier to think about the code, there's a
vague possibility that there might be a function that could work on both
structures (not so vague if Ring can be made into a subclass of Module,
I'd have to spend an hour validating that).

Then there's the question whether inheritance is buying us anything at
all. If no Group code ever reuses anything from Monoid, then yes it's
structurally nice to see the mathematical is-a relationship expressed in
the code, but we're just restricting what the subclass can do just to
conform with the design choices that made sense for the superclass.

> From a programming perspective, I would expect an AbelianGroup object to
> have a lot of methods on it that are very group theoretic, and it would be
> distracting at best to have these methods all be inherited directly into a
> Module object.

Yep.

There's one point that's still in favor of using subclasses wherever
possible: Serendipity. If you take the extra pain and put all the
structures into an inheritance hierarchy, somebody might be able to do
something extraordinary, whacky, novel, and useful with that.
I have no idea what that could be. It would be an attempt to create room
for invention, so others with a different mind for creativity can fill it.
That said, it would be some serious effort and a rather vague
usefulness. If the SymPy project is running at the limit of the effort
that its contributors can do, extra effort isn't available.

> I would rather expect to be able to do something like
> M.as_abelian_group().some_group_theory_method.

That might be a circular argument - if that expectation follows from the
habit of favoring composition over inheritance.

[vamsi kaushik]

>To be clear, I don't think that a Module class should necessarily subclass an AbelianGroup class. Using subclasses to represent shared relationships between mathematical objects is tricky.

That was what I was thinking, but couldn't say it properly.The idea of decomposing the Module into abelian groups seems to be a good idea. But its not something that had seen on other CAS systems before, but i really like it.

Regarding the group theory another important addition I would like to make to the current AGCA module is StructureDescription() which would act like a man page every time. like for example:

`StructureDescription(Group)` would print:

1 : trivial group

C(size) : cyclic group

S(degree) : Symmetric group

.... and so on all the group structures and a small description. This can be extended to other structures like modules and any other.

And a similar addition to my group theory module, like some more descriptive.

Currently I am following `An introduction to theory of groups`. 

What do you think ?

 

kaushik

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/CAKgW%3D6KZowdcKBPa-SouHArANu9c2tnQTQkmze04dbLm0uWinw%40mail.gmail.com.

[vamsi kaushik]

Hi Aaron,

I have submitted the first iteration of my proposal here. Please take a look and leave a comment.

Thanks,
kaushik

On Tuesday, February 3, 2015 at 3:58:16 AM UTC+5:30, vamsi kaushik wrote:

>To be clear, I don't think that a Module class should necessarily subclass an AbelianGroup class. Using subclasses to represent shared relationships between mathematical objects is tricky.

That was what I was thinking, but couldn't say it properly.The idea of decomposing the Module into abelian groups seems to be a good idea. But its not something that had seen on other CAS systems before, but i really like it.

Regarding the group theory another important addition I would like to make to the current AGCA module is StructureDescription() which would act like a man page every time. like for example:

`StructureDescription(Group)` would print:

1 : trivial group

C(size) : cyclic group

S(degree) : Symmetric group

.... and so on all the group structures and a small description. This can be extended to other structures like modules and any other.

And a similar addition to my group theory module, like some more descriptive.

Currently I am following `An introduction to theory of groups`. 

What do you think ?

 

kaushik

To unsubscribe from this group and all its topics, send an email to sympy+unsubscribe@googlegroups.com.

To post to this group, send email to sy...@googlegroups.com.
Visit this group at http://groups.google.com/group/sympy.

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/CAKgW%3D6KfH6Bw%3D2yfS6R1iBjHeXC10On_Uk4gr6sNBqyiWDM6Bw%40mail.gmail.com.

For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "sympy" group.

To unsubscribe from this group and stop receiving emails from it, send an email to sympy+unsubscribe@googlegroups.com.
To post to this group, send email to sy...@googlegroups.com.
Visit this group at http://groups.google.com/group/sympy.

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/CAK61vZooxm6N%2BmNaUCeRKoDkziCYw%3D3At_FGH6MCwd2spjze%3DA%40mail.gmail.com.

For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to a topic in the Google Groups "sympy" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/sympy/xH18C-g-ySQ/unsubscribe.

To unsubscribe from this group and all its topics, send an email to sympy+unsubscribe@googlegroups.com.

To post to this group, send email to sy...@googlegroups.com.
Visit this group at http://groups.google.com/group/sympy.

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/CAKgW%3D6KZowdcKBPa-SouHArANu9c2tnQTQkmze04dbLm0uWinw%40mail.gmail.com.