GSoC 2012: Group Theory
Aleksandar Makelov
here's a preliminary version of my proposal to work on group theory:
https://github.com/sympy/sympy/wiki/GSoC-2012-Application-Aleksandar-Makelov:-Group-theory
I still have to complete the timeline and provide some more concrete
objectives and ways for implementation. Any feedback will be greatly
appreciated!
Tom Bachmann
as you say, a couple of important things are missing (or implicit in the
timeline): What algorithms do you intend do implement? What data
structures/classes will you implement to support this? Somewhat less
importantly in this case of rather well-defined problems, what is the
interface going to look like?
Best,
Tom
David Joyner
In general, I find it hard to comment on this proposal without knowing
how much group theory you know and how well you know it. I have done some python
programming in group theory, but need to know how much group
theory you know and which algorithms are familiar with. At this stage, it seems
much more important to say something realistic with a definite useful
product in the end, than to lay out a great plan which might
or might not get completely implemented.
So:
* Which group theory books have you read and feel you know well?
* Which algorithms do you feel you can implement? A number of
issues arising in abelian groups boil down to a problem in (integer)
lattices.
* How much linear algebra do you know? How much lattice
theory (which you can regard as "linear algebra over the integers"
or "linear algebra over a finite ring such as ZZ/nZZ") do you know?
I hope this doesn't come out sounding critical. I'm trying to be very
encouraging, but I think a good workable plan would have a better
chance of being accepted by the powers that be. It will also be best for
you in the long run.
>
> --
> You received this message because you are subscribed to the Google Groups "sympy" group.
> To post to this group, send email to sy...@googlegroups.com.
> To unsubscribe from this group, send email to sympy+un...@googlegroups.com.
> For more options, visit this group at http://groups.google.com/group/sympy?hl=en.
>
Aleksandar Makelov
and thanks a lot for the feedback! I don't find it critical at all - I
find it helpful because it helps me to see this project from a new
perspective.
On Mar 31, 4:18 pm, David Joyner <wdjoy...@gmail.com> wrote:
> In general, I find it hard to comment on this proposal without knowing
> how much group theory you know and how well you know it. I have done some python
> programming in group theory, but need to know how much group
> theory you know and which algorithms are familiar with. At this stage, it seems
> much more important to say something realistic with a definite useful
> product in the end, than to lay out a great plan which might
> or might not get completely implemented.
>
> So:
> * Which group theory books have you read and feel you know well?
55a - the course in
abstract and linear algebra I took in the fall. However the problem
sets covered a great deal of other material - and in most cases,
harder material (if you want to take a look, here they are:
http://isites.harvard.edu/icb/icb.do?keyword=k80832). What makes the
course unusual is that the instructor has the freedom to choose
various topics that are not in the book. So I probably know "parts" of
other books as well, I just don't know which they are :). We
introduced a lot of group theoretical concepts (normal subgroups,
normalizers, commutators, Sylow subgroups, simple groups, group action
(orbits, stabilizers, transitivity), Galois groups,...) in the course,
and established some major results in group theory, such as the
structure theorem for Abelian groups and the three Sylow theorems.
The same book is used in Mathematics 123, one of my math courses this
term, for Galois theory and (in April) structure theorems for rings
and modules.
"Linear representations of finite groups", Jean Pierre Serre, Chapters
1,2
"Representation theory", William Fulton & Joe Harris, Lectures 1,2,3
These two books are used in the abstract algebra course I'm taking now
(Mathematics 123 http://isites.harvard.edu/icb/icb.do?keyword=k84948&pageid=icb.page489376
) in its second unit which is about representations. We covered the
above chapters and the problem sets used exercises from the same
books.
If some unknown to me major theoretical concept shows up during the
summer (given the background material assumed in the "Handbook", the
only such thing will probably be cohomology), I don't think it's going
to be a huge obstacle for me to understand it and then apply this
understanding in Python.
> * Which algorithms do you feel you can implement? A number of
> issues arising in abelian groups boil down to a problem in (integer)
> lattices.
I find it pretty accessible. I admit
I'm not familiar with all the algorithms in the book, but the ones
I've seen so far (picking random group elements,
computing orbits and stabilizers, testing for the symmetric/
alternating group) seem pretty doable.
> * How much linear algebra do you know? How much lattice
> theory (which you can regard as "linear algebra over the integers"
> or "linear algebra over a finite ring such as ZZ/nZZ") do you know?
the structure theorem for finite abelian groups.
We showed that for example a matrix with entries in ZZ can be
simplified by row/column operations to a form in which
the only nonzero entries a_1, a_2,..., a_n are on the diagonal with
a_1 \mid a_2 \mid ... \mid a_n. We established basic results
such as the Chinese Remainder Theorem. I can't say we formally did
"lattice" theory but I feel it has a lot to do with number theory
which I'm
really familiar with from the math olympiads.
Also, what do you mean by "something realistic with a definite useful
product in the end,"? Do you think that the algorithms in the
preliminary version of my proposal would
be too difficult to implement (or would not be very useful)?
> I hope this doesn't come out sounding critical. I'm trying to be very
> encouraging, but I think a good workable plan would have a better
> chance of being accepted by the powers that be. It will also be best for
> you in the long run.
Aleksandar Makelov
On Mar 30, 2:31 am, Tom Bachmann <e_mc...@web.de> wrote:
> Hi,
>
> as you say, a couple of important things are missing (or implicit in the
> timeline): What algorithms do you intend do implement? What data
> structures/classes will you implement to support this? Somewhat less
> importantly in this case of rather well-defined problems, what is the
> interface going to look like?
>
> Best,
> Tom
and thanks for your feedback as well. This week I'll try to spend time
on the exact algorithms I'd like to include in my proposal,
and also think about the data structures/classes - this is something
very important for the entire project, and it's hard to tell from the
beginning which structures are going to work best. For the interface,
I guess it's going to be somewhat similar to GAP's. You'll ideally be
able to name groups, define them in terms of generators (permutations,
matrices) or using a free group and relations imposed on it, and then
do the natural things with them (preferably using the natural words
for the corresponding functions) and ask them the natural questions
(are you simple? :) ).
David Joyner
Okay, you have an unusual background for a freshman. Based on
your background, you could implement some algorithms for abelian groups,
matrix groups, and permutations groups. I'm not familiar with the basic
algorithms with free groups or finitely presented groups, so can't really
comment on that part.
>
>> * Which algorithms do you feel you can implement? A number of
>> issues arising in abelian groups boil down to a problem in (integer)
>> lattices.
>
> Well I'm now reading the "Handbook of computational group theory" and
> I find it pretty accessible. I admit
> I'm not familiar with all the algorithms in the book, but the ones
> I've seen so far (picking random group elements,
> computing orbits and stabilizers, testing for the symmetric/
> alternating group) seem pretty doable.
Good.
>
>> * How much linear algebra do you know? How much lattice
>> theory (which you can regard as "linear algebra over the integers"
>> or "linear algebra over a finite ring such as ZZ/nZZ") do you know?
>
> In the fall we did a bit of that, especially because we needed it for
> the structure theorem for finite abelian groups.
> We showed that for example a matrix with entries in ZZ can be
> simplified by row/column operations to a form in which
> the only nonzero entries a_1, a_2,..., a_n are on the diagonal with
> a_1 \mid a_2 \mid ... \mid a_n. We established basic results
> such as the Chinese Remainder Theorem. I can't say we formally did
> "lattice" theory but I feel it has a lot to do with number theory
> which I'm
> really familiar with from the math olympiads.
That is excellent. For your timeline, perhaps you would implement
abelian groups in 2-3 weeks?
>
> Also, what do you mean by "something realistic with a definite useful
> product in the end,"? Do you think that the algorithms in the
> preliminary version of my proposal would
> be too difficult to implement (or would not be very useful)?
I would be specific:
Abelian groups:
"the basic methods like handling different representations" means
implementing invariants (elementary divisors) both in the additive case
and in the multiplicative case?
Matrix groups:
"Implementing ... basic group properties like finite, finitely
presented, Abelian, cyclic, simple..."
Determining if a matrix group defined by a finite number of matrices
over a finite field
is simple or not is actually not easy. You have to be able to find
normal subgroups.
In fact, I am not even sure how well finite fields are implemented in SymPy.
For time reasons, I would drop "finitely presented" and assume
everything is defined using
finitely many generators, either as an abelian group, a matrix group, or a
permutation group.
Permutation groups:
"Implementing ... basic group properties like finite, finitely
presented, Abelian, cyclic, simple..."
Again, determining if a permutation group defined by a finite number
of permutations
is simple or not is actually not easy.
Do you really think all this can be done in one week?
Do you plan on implementing quotient groups? For that coset
enumeration, in week 7 and 8, might be
needed sooner.
>
>> I hope this doesn't come out sounding critical. I'm trying to be very
>> encouraging, but I think a good workable plan would have a better
>> chance of being accepted by the powers that be. It will also be best for
>> you in the long run.
>
>
> Yep I agree - thanks again!
>
Aleksandar Makelov
substantial algorithms. What I had in my head when I was writing this
was only giving the group object various properties with names like
isFinite, isAbelian,... that would later be used (and indeed,
evaluated and stored in the object to avoid computing them again).
As for matrices, I haven't really studied groups of matrices with
entries in finite fields in detail. But it's clear that they are
always finite - so one should be able to present them using
permutations and forget about the matrix structure? Anyway, this is
what GAP does for all matrix groups (most of the time), I think.
Though the size of the presentation should be optimized - it won't be
very reasonable to consider the regular representation of, say, the
general linear group of 3x3 matrices with entries in the field of 8
elements F_8 because that has dimension (approximately) 8^9, whereas
there might be other faithful permutation representations of much
smaller dimension. This needs further investigation...
And yeah quotients are a must, they are going to show up on the
timeline sometime this coming week...
Cheers,
Alex
Aleksandar Makelov
character tables by manual input from the user.
This was *motivated* by a recent problem set in which one of the
problems was about decomposing 4 representations of S4 into
irreducible ones, which takes about 300 multiplications and 100
additions when done by hand (...). It will allow people to manually
input the cardinalities of conjugacy classes and a bunch of characters
of irreducible representations and then mess around with them (take
direct sums, tensor them, take duals, decompose, check for
irreducibility,...). It will probably make good use of the complex
numbers already in sympy - but is it going to be a valuable addition
to the library? (I mean, there's no representation theory in sympy
(yet))
David Joyner
<amak...@college.harvard.edu> wrote:
> Oh I was being foolish... Of course, simplicity will require some more
> substantial algorithms. What I had in my head when I was writing this
> was only giving the group object various properties with names like
> isFinite, isAbelian,... that would later be used (and indeed,
> evaluated and stored in the object to avoid computing them again).
>
> As for matrices, I haven't really studied groups of matrices with
> entries in finite fields in detail. But it's clear that they are
> always finite - so one should be able to present them using
> permutations and forget about the matrix structure? Anyway, this is
Yes, that helps in some cases.
> what GAP does for all matrix groups (most of the time), I think.
I think GAP does this for the projective versions but not the
linear versions, eg, PSL(2, p) but not SL(2, q).
> Though the size of the presentation should be optimized - it won't be
> very reasonable to consider the regular representation of, say, the
> general linear group of 3x3 matrices with entries in the field of 8
> elements F_8 because that has dimension (approximately) 8^9, whereas
Is GF(8) implemented in SymPy?
David Joyner
This could be very useful. GAP does a great job with characters, so
most people would just use
GAP for that though. Still, some functionality would be nice.
Ondrej wrote some notes on group theory here:
http://theoretical-physics.net/dev/src/math/groups.html
Being able to do those in SymPy would be nice.
Tom Bachmann
>
You can type GF(8), but I think this yields ZZ/8ZZ.
David Joyner
>> Is GF(8) implemented in SymPy?
>>
>
> You can type GF(8), but I think this yields ZZ/8ZZ.
>
Yes, in 0.7.1, I get this:
>>> F = GF(8)
>>> F(7)
7 mod 8