Opened 11 years ago
Closed 10 years ago
#12339 closed enhancement (fixed)
Free Groups
Reported by: | Miguel Marco | Owned by: | joyner |
---|---|---|---|
Priority: | major | Milestone: | sage-5.7 |
Component: | group theory | Keywords: | free groups, finitely presented groups, braids |
Cc: | combinatorics, Syed ahmad Lavasani, Vincent Delecroix, John Palmieri, Timo Jolivet, Rob Beezer, Dima Pasechnik | Merged in: | sage-5.7.beta3 |
Authors: | Miguel Marco, Volker Braun | Reviewers: | Volker Braun |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | #6391, #13687, #13588 | Stopgaps: |
Description (last modified by )
I aim to write some classes to implement free groups, finitely presented groups and braid groups. Mostly it would consist in wrapping gap functions, so maybe it would need to be rewritten in the future if libgap is finished.
I don't have any previous experience in implementing new classes or using the category framework, but so far i have started with a little proof of concept. I would really apreciate any feedback or help.
This is an example of some things that you can do so far:
Basic arithmetic in Free and Finitely presented groups:
sage: G.<a,b,c,d,e> = FreeGroup() sage: a*b*c*d/a/a/e a*b*c*d*a^-2*e^-1 sage: H = G / [a*b*a*b,a^2,b^2,c^2,d^2,e^2,a*b*c*d*e*a*b,c*d*e*c*d*e,d*e*d*e] sage: H.gens() (a, b, c, d, e) sage: H([1,2,3]) / H([3,2,1]) a*b*c*a^-1*b^-1*c^-1
Fox derivatives of free group elements, and Alexander matrices of finitely presented groups (the result is given on the group algebra):
sage: G<a,b,c> = FreeGroup() sage: a*b*c/a/a/c a*b*c*a^-2*c^-1 sage: H = G.quotient([a*b*a*b,a^2,b^2,c^2,a*b*c*a*b*c]) sage: H.gens() (a, b, c) sage: H([1,2,3])/H([3,2,1]) a*b*c*a^-1*b^-1*c^-1 sage: (a*b*a/b/a).fox_derivative(a) B[1] + B[a*b] - B[a*b*a*b^-1*a^-1] sage: H.alexander_matrix() [ B[1] + B[x0] 0 0] [ 0 B[1] + B[x1] 0] [ 0 0 B[1] + B[x2] + B[x2^2]] [ B[1] + B[x0*x1] B[x0] + B[x0*x1*x0] 0] [ B[1] + B[x0*x2] 0 B[x0] + B[x0*x2*x0]] [ 0 B[1] + B[x1*x2] + B[x1*x2*x1*x2] B[x1] + B[x1*x2*x1] + B[x1*x2*x1*x2*x1]]
Some properties of finitely presented groups.
sage: G = FreeGroup(3) sage: G.inject_variables() Defining x0, x1, x2 sage: H = G / [x0*x1*x2*x0*x1*x2,x1*x2*x0*x1*x2,x2^2] sage: H.simplification_isomorphism() Generic morphism: From: Finitely presented group < x0, x1, x2 | x0*x1*x2*x0*x1*x2, x1*x2*x0*x1*x2, x2^2 > To: Finitely presented group < x1, x2 | x2^2, x1*x2*x1*x2 > sage: H.abelian_invariants() (2, 2) sage: H.simplification_isomorphism()(x0) 1 sage: H.simplification_isomorphism()(x1) x1 sage: H.simplification_isomorphism()(x2) x2 sage: H.abelian_invariants() (2, 2)
Caution: some methods are no granted to finish, specially if the group is infinite. In that case, the system memory would be exhausted, and the underlying gap session killed, leaving orphaned objects. It would be nice to have a security system that would interrupt the computation before arriving to that, giving just an error message. It's on the to-do list.
sage: G = FreeGroup(3) sage: G.inject_variables() Defining x0, x1, x2 sage: H = G.quotient([x0^2,x1^2,x2^3,(x0*x1)^2,(x0*x2)^2,(x1*x2)^3]) sage: H.abelian_invariants() (2,) sage: H.simplification_isomorphism() Generic morphism: From: Finitely presented group < x0, x1, x2 | x0^2, x1^2, x2^3, x0*x1*x0*x1, x0*x2*x0*x2, x1*x2*x1*x2*x1*x2 > To: Finitely presented group < x0, x1, x2 | x0^2, x1^2, x2^3, x0*x1*x0*x1, x0*x2*x0*x2, x1*x2*x1*x2*x1*x2 > sage: H.cardinality() 24 sage: H.as_permutation_group() Permutation Group with generators [(1,2)(3,6)(4,8)(5,7)(9,14)(10,13)(11,16)(12,15)(17,22)(18,21)(19,24)(20,23), (1,3)(2,6)(4,11)(5,12)(7,15)(8,16)(9,17)(10,18)(13,21)(14,22)(19,20)(23,24), (1,4,5)(2,7,8)(3,9,10)(6,13,14)(11,18,19)(12,20,17)(15,22,23)(16,24,21)]
For Braid groups, the way to work is similar.
sage: B=BraidGroup(4) sage: B Braid group on 4 strands sage: B([1,2,3,-1,2,-1]) s0*s1*s2*s0^-1*s1*s0^-1 sage: b=B([1,2,3,-1,2,-1]) sage: b.left_normal_form() [s0^-1*s1^-1*s2^-1*s0^-1*s1^-1*s0^-2*s1^-1*s2^-1*s0^-1*s1^-1*s0^-1, s0*s1*s2*s1*s0, s0*s2*s1*s0, s0*s1*s0*s2*s1] sage: b.permutation() [4, 3, 2, 1] sage: b.burau_matrix() [ -t + 1 -t^2 + t -t^3 + t^2 t^3] [ -1 + t^-1 -t + 2 - t^-1 t 0] [ -1 + 2*t^-1 - t^-2 -t + 3 - 2*t^-1 + t^-2 t - 1 0] [ t^-1 1 - t^-1 0 0] sage: b.LKB_matrix() [ 0 0 -x^6*y + x^5*y - x^3*y + 2*x^2*y - x*y 0 -x^6*y + x^5*y - x^3*y + x^2*y -x^6*y + x^5*y - x^4*y] [ 0 0 -x^5*y + x^4*y - x^2*y + x*y 0 -x^5*y + x^4*y - x^2*y -x^5*y + x^4*y] [ 0 0 -x^4*y + x^3*y - x^2*y 0 -x^4*y + x^3*y 0] [ -x^-3*y^-2 + x^-4*y^-2 -y^-1 + 2*x^-1*y^-1 - 2*x^-2*y^-1 + x^-2*y^-2 + x^-3*y^-1 - 2*x^-3*y^-2 + x^-4*y^-2 x^5*y - 2*x^4*y + x^3*y + x^2*y - x^2 - 2*x*y + 3*x + y - 3 + x^-1 + x^-1*y^-1 - 2*x^-2*y^-1 + x^-2*y^-2 + x^-3*y^-1 - 2*x^-3*y^-2 + x^-4*y^-2 -y^-1 + x^-1*y^-1 - x^-2*y^-1 x^5*y - 2*x^4*y + x^3*y + x^2*y - x^2 - x*y + 2*x - 1 + x^-1*y^-1 - x^-2*y^-1 x^5*y - 2*x^4*y + x^3*y - x^3 + x^2] [ -x^-2*y^-1 + x^-3*y^-1 -x^2*y + x*y - x - y + 3 - 3*x^-1 + x^-1*y^-1 + x^-2 - 2*x^-2*y^-1 + x^-3*y^-1 x^4*y - 2*x^3*y + 2*x^2*y - x*y - x + 3 - 3*x^-1 + x^-1*y^-1 + x^-2 - 2*x^-2*y^-1 + x^-3*y^-1 -x^2*y + x*y - x + 2 - x^-1 x^4*y - 2*x^3*y + x^2*y - x + 2 - x^-1 0] [ -x^-3*y^-1 -1 + 2*x^-1 - x^-2 + x^-2*y^-1 - x^-3*y^-1 x^3*y - 2*x^2*y + 2*x*y - y - 1 + 2*x^-1 - x^-2 + x^-2*y^-1 - x^-3*y^-1 -1 + x^-1 x^3*y - 2*x^2*y + x*y - 1 + x^-1 0]
Also b.plot() and b.plot3d() would plot the braid.
There is a new version to be used with the libgap interface (much faster than the old pexpect one). Since libgap seems to be stable and ready, i plan to focus on this version.
To install it, just make sure you have applied #6391, #13211, and then apply
Attachments (16)
Change History (98)
Changed 11 years ago by
Attachment: | freegroups.py added |
---|
Changed 11 years ago by
Attachment: | freegroups.2.py added |
---|
comment:2 Changed 11 years ago by
Authors: | → Miguel Marco |
---|---|
Cc: | combinatorics added |
Status: | new → needs_review |
comment:3 Changed 11 years ago by
I have added a patch with the free groups, finitely presented groups and braid groups.
comment:4 Changed 11 years ago by
It isn't a bad idea, if you write in the desc that people need to apply all three patches.
comment:5 Changed 11 years ago by
Cc: | Syed ahmad Lavasani added |
---|
comment:7 Changed 11 years ago by
Status: | needs_review → needs_work |
---|
Hello,
It will be nice to have that in Sage. First of all, before putting a patch in "needs review" you have to verify few things that are in the Developer Guide of Sage. In particular, you should correct:
0.a) There are many trailing whitespaces that you should remove (you can use sed in a console).
0.b) There are 8 doctests that fail (you may use "sage -t my_file.py").
0.c) You should pay attention to the documentation: comment your examples and explain how do they work (both from mathematical and user point of vue). This is very important the reviewer and the future Sage user.
Then there are other possible ways of improvement.
1) I can not multiply braids
sage: B = BraidGroup(4) isage: B.inject_variables() Defining sigma0, sigma1, sigma2, sigma3 sage: b=sigma0*sigma1 --------------------------------------------------------------------------- TypeError Traceback (most recent call last) ... TypeError: unsupported operand type(s) for *: 'Braid' and 'Braid'
2) I think that the free group should go in a dedicated file (you can not consider it simply as a particular case of a finitely presented group). There are many notions, algorithms and techniques which apply only to it: the notion of rank for subgroups, the notion of free factor, the automorphism dynamics (reducibility, decomposition into Nielsen transformations, action on CV space, train-track representations, ...). I have the same feeling for braid groups.
3) I don't know if a systematic call to GAP is needed for the free group especially in terms of efficiency
sage: F = FreeGroup('a,b') sage: a,b = F.generators() sage: a*b a*b sage: timeit("a*b") 5 loops, best of 3: 512 ms per loop
I have a naive implementation of it which is based on sage.combinat.words.* and works more than 1000 times faster! But don't be to careful with that, it is dedicated to another patch.
... and many more to come. In other words, the patch is not ready at all but it is an important piece that Sage needs.
Vincent
comment:8 Changed 11 years ago by
Cc: | Vincent Delecroix added |
---|
comment:9 Changed 11 years ago by
Thanks for the comments, Vincent. I will keep working on it (and any help would be more than welcome).
You are right about the problem of multiplying braids. It is strange, since at some point it did work, but i can't identify what did i change that produces the error. It should work, since the _mul_ methods works fine.
I will try to improve the documentation and examples.
comment:10 Changed 11 years ago by
I have updated the patch. I have separated braid group from the rest. Free groups and finitely presented groups can not be separated, since FreeGroup?.quotient() calls FinitelyPresentdGroup?, and FinitelyPresentedGroup? calls FreeGroup?, so splitting them in separated files makes circular dependencies.
Changed 11 years ago by
Attachment: | 12339-minor.patch added |
---|
solved a minor issue, apply over the previous one
Changed 11 years ago by
Attachment: | 12339-cmp.patch added |
---|
added comparison of braids, apply over 12339-minor.patch
Changed 11 years ago by
Attachment: | 16192.patch added |
---|
for using with libgap. apply over 16190.patch. deppends on 6391
comment:11 Changed 11 years ago by
Added patches 12339-minor.patch and 12339-cmp.patch. They solve an issue with left normal form, and adds comparison of braids.
All doctests passed, but the testuite fails in pickling (no clue about how to solve it, i think its a problem with gap objects).
As an experiment, i have also added a 16192.patch to make this work with libgap. It deppends on #6391. To make it work, apply #6391, and 16190.patch and then 16192.patch. It works much faster, but there are two problems related to libgap: random segfaults occur, and libgap doesn't handle the simplification isomorphism for finite presentations.
comment:12 Changed 11 years ago by
Added a new patch with a cleaned up version. All doctests passed (except a few related with the r interface, but thos failed also on my clean sage install, so i don't think they are related with the patch).
Testsuites for free groups and finitely presented groups passed. _test_category for braids fails, but i really don't understand why, since finitely presented groups pass it, and braid inherit directly from them.
comment:13 Changed 11 years ago by
Status: | needs_work → needs_review |
---|
comment:14 Changed 10 years ago by
Description: | modified (diff) |
---|
comment:16 Changed 10 years ago by
Description: | modified (diff) |
---|
comment:18 Changed 10 years ago by
Cc: | John Palmieri added |
---|
comment:19 Changed 10 years ago by
Cc: | Timo Jolivet added |
---|
comment:20 Changed 10 years ago by
Several comments:
- I'm very excited that we can get this into Sage soon; I would like to use this for computing fundamental groups of simplicial complexes, among other things.
FreeGroup(n)
should work if n is zero!
FreeGroup(gens)
should allow gens to be much more general. For simplicial complexes, for instance, I would want to label the generators as edges in a graph. Take a look at CombinatorialFreeModule (in sage.combinat.free_module): you can have the generators be given by any family of mathematical objects (and not just strings for them, but the objects themselves). That sort of functionality would be very useful. Anyway, I'm imagining that gens could be a string of the current form, but also any iterable, or possibly something more general like the families that you can use in CombinatorialFreeModule.
comment:21 Changed 10 years ago by
I have been thinking about how to rewrite the code to allow arbitrary objects as generators, but i don't see how to do it. My code is basically a wrapper around gap freegroups and finitely generated groups. So internally we have to stick to the gap structure. Maybe it could be possible to "cheat" by just creating a dictionary that relates the arbitrary generators and the string generators, in such a way that you can change the output.
Right now i am in a conference, so i can't work on the code until next week. And even then, there are other things that have higher priority on my to-do list. But if someone wants to step up and make a patch with the feature you mentioned, that would be great.
Anyways, i think that it would be better to have something simpler but that works fine for the moment, and once that is merged, start working on extending functionalty.
comment:22 Changed 10 years ago by
First of all, thanks for writing in this code, this is something that we totally need to get into Sage!
I have been playing around with some finitely presented groups and found a few oddities
sage: G = FreeGroup("x,y") sage: G.inject_variables() Defining x, y sage: H = G.quotient([x^5, y^4, y*x*y^3*x^3]) sage: xx = H(x) sage: xx^5 x^5
I expected that to show 1 or Identity
. GAP also behaves strangely on this front.
At least equality seems to behave properly:
sage: xx^5 == H(1) True
However, it gets completely broken when going to the group ring, which is bad:
sage: R = GroupAlgebra(H) sage: R(xx)^5 x^5 sage: R(xx)^5 == R(1) False sage: R(xx^5) == R(1) False
Finally there are some constructions that I'd expect to work but don't, for instance H
is an almost dihedral group of order 20, which can be computed in GAP but not in Sage:
sage: H.order() --------------------------------------------------------------------------- NotImplementedError Traceback (most recent call last) ...
I haven't really read the code, but if you are wrapping the GAP code this can be sorted out by calling the gap.Order()
method on the underlying gap object. Which, incidentally, also doesn't work:
sage: gap(H) --------------------------------------------------------------------------- TypeError Traceback (most recent call last) ... sage: H._gap_() --------------------------------------------------------------------------- TypeError ...
This last part should be very easy to fix and would probably ease wrapping up other GAP functions.
comment:23 Changed 10 years ago by
Gap doesn't try to reduce elements of finitely presented groups to normal form because, in general, it is an undecideable problem. The package kbmag has some algorithms to look for confluent rewriting systems and automatic structures, which would allow a normal form reduction in some cases. I have thought about including this in my code, but since it deppends on an external package (which is not even in the optional gap_packes spkg) i would prefear to tackle that in an external spkg that would include also kbmag.
I don't know why comparison doesn't work in the group algebra. I should take a look at the group algebra code to see what is going on.
To compute the order of a group, use the .size method. You will either get an answer or exhaust the system memory, kill the internal gap session, and get a mess. You can even get an expression as symmetric group.
In your example:
sage: G = FreeGroup("x,y") sage: G.inject_variables() Defining x, y sage: H = G.quotient([x^5, y^4, y*x*y^3*x^3]) sage: H.size() 20 sage: H.permutation_group() Permutation Group with generators [(1,2,6,9,3)(4,12,10,7,13)(5,15,8,11,16)(14,18,20,19,17), (1,4,14,5)(2,7,17,8)(3,10,18,11)(6,12,19,16)(9,13,20,15)]
Finally, the method .gap() gives you the gap representation of the objects (that is, an object of the class sage.interfaces.gap.GapElement?). So if you want to call some gap function foo on one of this objects, you just need to call something like H.gap().foo() .
Maybe i should write a comprehensive documentation. That's another item on the to-do list.
comment:24 Changed 10 years ago by
I am aware of the problem of finding a normal form for elements. My (badly made) point is that it should be clearly documented as this is the kind of thing that would get a student easily confused. The group algebra comparison is a real problem, though.
Something that might be useful here would be to allow the user give some reduction rules. In my example, it is very clear that all the group elements can be written as x^ay^b
for suitable a
and b
; in an ideal world, I could tell Sage to simplify my elements by repeatedly using the three rules
- "Reduce powers of
x
modulo 5" - "Reduce powers of
y
modulo 4" - "Replace each
y^ax^b
byx^(2a+2b)y^b
"
until none of them can be further applied. Mathematica excels at this type of operation (reduction by pattern matching). Perhaps the combinat guys have just the right tool for doing this, but anyway this is certainly a matter for a follow-up ticket once we have the basic functionality running.
The .gap()
method didn't work for me with your patch, but maybe I didn't use it properly, I will try again when I get home.
comment:25 Changed 10 years ago by
Cc: | Rob Beezer added |
---|
comment:26 follow-up: 27 Changed 10 years ago by
I would suggest replacing size
with cardinality
. That's more in line with other components of Sage. I would also suggest having a method which returns the codomain of G.simplification_isomorphism()
; if I have generators and relations, I would like to see if there is a nice accessible simplification. Also, and this is probably related to one of my comments above:
sage: G = FreeGroup('g') sage: E = G.quotient((G.gen(0),)) sage: E.simplification_isomorphism()
doesn't work, complaining that ValueError: variable name must be nonempty
.
The .gap method seems to work okay, although I haven't tested it very thoroughly. From looking at other files in sage/groups/, it looks like you should instead implement both G._gap_()
(to return the GAP object corresponding to G) and G._gap_init_()
(to return the string representation of the corresponding GAP object). But I'm not sure about this: maybe you only need one of these methods. Anyway, if you do it right, then gap(G)
will return the GAP version of G.
Overall, your code should be consistent with the other groups available in Sage, both in terms of public methods (for example, using cardinality
instead of size
) and private ones (_gap_
, _gap_init_
, etc.)
comment:27 Changed 10 years ago by
Replying to jhpalmieri:
I would suggest replacing
size
withcardinality
.
Can we have order
as an alias for cardinality()
in the case of groups? It seems totally foreign to not have it.
The .gap method seems to work okay, although I haven't tested it very thoroughly. From looking at other files in sage/groups/, it looks like you should instead implement both
G._gap_()
(to return the GAP object corresponding to G) andG._gap_init_()
(to return the string representation of the corresponding GAP object). But I'm not sure about this: maybe you only need one of these methods. Anyway, if you do it right, thengap(G)
will return the GAP version of G.
I've only just figured out some of this in the last 48 hours as I have been building an automorphism group of permutation groups. I think that if _gap_init_()
returns a string which would cause GAP to create the desired object, then everything else, like _gap_()
for sure, and I'd guess gap()
as well, just seems to come along for the ride. gap.eval(<command>)
outputs strings you can save/manipulate to use as return values for _gap_init_()
.
Changed 10 years ago by
Attachment: | trac_12339_fpgroups.2.patch added |
---|
Apply over 12339_fpgroups.patch
comment:28 Changed 10 years ago by
I have added the _gap_ and the _gap_init_ methods for free groups, but still gap(self) does not work its magic. I couldn't find an acceptable way for FinitelyPresentedGroup?._gap_init_ since gap requires to create first the free group (and give it a name) in order to create a FPGroup.
Solved the problem with free groups of rank 0.
Added cardinality and order as aliases for size.
Added FinitelyPresentedGroup?.simplify_presentation that returns the codomain of simplification_isomorphisms.
It is all implemented in a new patch that should be aplyed over the previous one.
comment:30 follow-up: 31 Changed 10 years ago by
Can you please make simple speed benchmarks in different systems? I have observed a big speed difference from my gentoo box to a mandriva system (where sage runs in a ubuntu chroot). I suspect it has to do with the sage-gap communication (maybe something with the way shm or pts work?)
Here are my benchmarks:
In my gentoo box (intel core i7, 6GB RAM)
sage: time F=FreeGroup(4) Time: CPU 0.00 s, Wall: 0.00 s sage: time F.inject_variables() Defining x0, x1, x2, x3 Time: CPU 0.03 s, Wall: 0.04 s sage: time x=F([1,2,3,4,1,2,3,4]) Time: CPU 0.01 s, Wall: 0.01 s sage: time x^2 x0*x1*x2*x3*x0*x1*x2*x3*x0*x1*x2*x3*x0*x1*x2*x3 Time: CPU 0.07 s, Wall: 0.08 s
In the mandriva-chroot-ubuntu (two AMD-opteron 6100, 16 cores in total, 128 GB RAM):
sage: time F=FreeGroup(4) Time: CPU 0.03 s, Wall: 0.50 s sage: time F.inject_variables() Defining x0, x1, x2, x3 Time: CPU 0.04 s, Wall: 2.32 s sage: time x=F([1,2,3,4,1,2,3,4]) Time: CPU 0.02 s, Wall: 0.86 s sage: time x^2 x0*x1*x2*x3*x0*x1*x2*x3*x0*x1*x2*x3*x0*x1*x2*x3 Time: CPU 0.10 s, Wall: 5.34 s
It really makes no sense such a slowdown. Any ideas?
comment:31 Changed 10 years ago by
Replying to mmarco:
It really makes no sense such a slowdown. Any ideas?
There was a definite problem with Sage-GAP communication in Ubuntu. It was Ubuntu's fault if I recall correctly. Do you have a recent Ubuntu? I first noticed this about a year ago, and it seems to be better (fixed?) now (with 12.04).
Here's one indicator (I didn't look very hard for the root explanation):
https://groups.google.com/d/msg/sage-release/vLGiLlGXH-U/X4qsKwTK57kJ
Try doctesting the sandpile.py module, it takes forever in the presence of this problem.
Rob
comment:32 follow-up: 33 Changed 10 years ago by
The ubuntu chroot is 12.04. Also, i have similar slowdowns in previous versions of sage under mandriva (i couldn't compile the last versions because of the bug in the time command).
Testing sandpile takes forever indeed.
In the link you gave Dima says that the kernel is to blame.
Can you test it in different systems?
comment:33 Changed 10 years ago by
Replying to mmarco:
Can you test it in different systems?
Any machine with I have with Sage is Ubuntu 12.04. That won't help, will it?
comment:34 Changed 10 years ago by
Well, at least it would help to know that ubuntu 12.04 is not affected.
comment:35 Changed 10 years ago by
On OS X 10.7:
sage: time F=FreeGroup(4) Time: CPU 0.00 s, Wall: 0.00 s sage: time F.inject_variables() Defining x0, x1, x2, x3 Time: CPU 0.04 s, Wall: 0.06 s sage: time x=F([1,2,3,4,1,2,3,4]) Time: CPU 0.01 s, Wall: 0.02 s sage: time x^2 x0*x1*x2*x3*x0*x1*x2*x3*x0*x1*x2*x3*x0*x1*x2*x3 Time: CPU 0.09 s, Wall: 0.09 s
Wall time is completely reasonable.
comment:36 Changed 10 years ago by
On 64-bit Ubuntu 12.05, Sage 5.1.rc1, hardware is a 4-core Intel about 18 months old.
Seems similar to what John is seeing (roughly).
sage: time F=FreeGroup(4) Time: CPU 0.02 s, Wall: 0.08 s sage: time F.inject_variables() Defining x0, x1, x2, x3 Time: CPU 0.03 s, Wall: 0.04 s sage: time x=F([1,2,3,4,1,2,3,4]) Time: CPU 0.02 s, Wall: 0.02 s sage: sage: time x^2 x0*x1*x2*x3*x0*x1*x2*x3*x0*x1*x2*x3*x0*x1*x2*x3 Time: CPU 0.06 s, Wall: 0.08 s
comment:37 Changed 10 years ago by
Thanks, so it seems that the issue is specific on some older kernels.
comment:38 Changed 10 years ago by
Cc: | Dima Pasechnik added |
---|---|
Description: | modified (diff) |
comment:39 Changed 10 years ago by
Looks great! Some libgap notes:
- libgap makes sure to lazy import itself, since gap startup takes some time. Hence
sage/libs/all.py
definesfrom sage.misc.lazy_import import lazy_import lazy_import('sage.libs.gap.libgap', 'libgap')
You should either follow the same pattern and lazily import your own code fromsage/groups/all.py
. This will help Sage in the long run to avoid long startup times. Also, its better to import libgap asfrom sage.libs.all import libgap
, then you get the lazy importer.
There are a couple of code style and documentation issues:
- Always put an empty line before function/method declarations (that is, before "def ...")
- Space after comma:
def __init__(self, ll=[], parent=None)
instead ofdef __init__(self,ll=[],parent=None)
- Use
EXAMPLES:: sage: 1+1
instead of the multi-lineEXAMPLES: :: sage: 1+1
- Its encouraged to generate intermediate variables instead of very long lines:
self._gap_repr_=parent.gap().One().FamilyObj().ElementOfFpGroup(libgap.eval(str(l)).AbstractWordTietzeWord(parent.gap().FreeGroupOfFpGroup().GeneratorsOfGroup()))
would be more legible asgap = parent.gap() gens = gap.FreeGroupOfFpGroup().GeneratorsOfGroup() element = gap.One().FamilyObj().ElementOfFpGroup(libgap.eval(str(l)) self._gap_rep = element.AbstractTietzeWord(gens)
- Module-level documentation for the new files, and add them to the reference manual index (that is, to
doc/en/reference/groups.rst
) so the documentation is actually built. - Input parameters need to be documented consistently. That is, consistently use
INPUT:
andOUTPUT:
sections in the docstrings. You know what the methods are for, but we don't ;-)
comment:40 Changed 10 years ago by
Dependencies: | → #6391 |
---|---|
Milestone: | → sage-5.5 |
Priority: | minor → major |
Reviewers: | → Volker Braun |
comment:43 Changed 10 years ago by
This is a really nice contribution!
ParentWithGens
is deprecated, see the beginning of sage/structure/parent_gens.pyx
. You should use Parents.__init__(self, gens=..., category=Groups())
or so. I know thats not as well-documented as it should be. You do already import Groups
but don't use it. Did you have any problems with the new parents?
For comparison you should override _cmp_
in elements, otherwise you circumvent the coercion system.
Another minor issue, don't use catch-all except:
. You almost certainly don't want to catch KeyboardInterrupt
, for example. Use except StandardError:
to catch all errors.
Since there isn't any example yet for how to use libGAP, I though it would be nice to use the finitely generated groups to demonstrate what it can be used for. Do you have any other patches that you have already based on this ticket? Otherwise I'd like to make some changes to use libgap better.
comment:44 Changed 10 years ago by
Ok, i will try to wee if swtiching from parentwithgens to parents is not too painful.
I remember i tried different ways of inheritingt, and finally decided this one, but i don't remember exactly why.
What do you mean exactly by overrode _cmp_? isn't that what i do already?
I have no ither patches that deppend on this, but i was just planning to start with something to give support to the kbmag gap package, which would allow to deal with reduced forms of the elements of finitely presented groups (when Knuth-Bendix or the search for automatic structure succeeds).
comment:45 Changed 10 years ago by
I see the problem now: Group inherits from ParentWithGens?. Should i not inherit from Group then?
Changed 10 years ago by
Attachment: | trac_12339_fpgroups_libgap_minor_changes.patch added |
---|
minor changes to the previous version. Should be applied over the previous one.
comment:46 Changed 10 years ago by
I think i have addressed the issues you commented. Made a small patch with the changes. Please check it up and tell me what you think.
On a side question: do you have any clue about why the testsuite for braid groups fails?
Oh, and by the way, feel more than welcome to make any improvements that you consider.
comment:47 Changed 10 years ago by
The Element
class has a __cmp__
method, you are still overriding it. You should only provide a _cmp_
. The parent __cmp__
will then call _cmp_
, possibly after coercing arguments.
I guess one should change Group to derive from Parent, though that might be a bigger effort. I'll send an email to sage-devel to gauge interest ;-)
comment:48 Changed 10 years ago by
Hm, i am now forgeting about the cmp method, and just implementing comparison through _cmp_ ... but that makes comparison by equality not working.
I get something like this:
sage: F=FreeGroup('a,b,c') sage: F.inject_variables() Defining a, b, c sage: a._cmp_(a*b/b) 0 sage: cmp(a,a*b/b) 0 sage: a.__cmp__(a*b/b) 0
but
sage: a==a*b/b False
That didn't happen in the previous version.
comment:49 Changed 10 years ago by
Something is wrong with trac_12339_fpgroups_libgap.patch, it seems like two concatenated patches. Patch creates sage/groups/braid.py
twice, for example.
Getting cmp
and/or richcmp
right is usually tricky. The best reference is reading sage/structure/element.pyx
, I'm afraid. I can give it a whirl if you fix the original patch ;-)
comment:50 Changed 10 years ago by
Dependencies: | #6391 → #6391, #13687 |
---|---|
Status: | needs_review → needs_work |
Can you rebase it the patch on top of #13687? Also, the current patch is corrupted.
For elements implemented in Python you are supposed to override __cmp__
, I think. So ignore my previous comment on that.
comment:51 Changed 10 years ago by
Ok, i have submited a rebased version of the patch, with the cmp methods overriden.
Now the classes inherit from Parent, but not from Group, so a few generic methods for groups are lost (very few in fact). It shouldn't be hard to get back to Group when it derives from Parent.
comment:52 Changed 10 years ago by
Sorry if I wasn't clear, #13687 bases sage.groups.group.Group
on Parent
. So you should just derive from Group
.
comment:53 Changed 10 years ago by
Ok, thanks for the work. It is all fixed now.
Although this tocket is starting to depend on so many others (gap update, libgap, parent...) that i just fear it will never get merged ;)
I have some new features and improvements in mind, but i think it is better to get this stabilized and merged first, and then start working in improving it.
comment:54 Changed 10 years ago by
Description: | modified (diff) |
---|---|
Keywords: | finitely presented braids added |
comment:55 Changed 10 years ago by
Description: | modified (diff) |
---|
I've factored out repeated code for implementing Sage parents/elements on top of LibGAP groups/elements into libgap_wrapper.pyx
.
- Don't import everything into the global namespace. Lots of doctests
were failing because lazy importing '*' is not what you want. Generally speaking, never import
*
. Group.__init__
already callsParent.__init__
, don't call it twice- Support the
G.<a,b> = FreeGroup()
syntax - use
_assign_names()
to store generator names, no point in storing them again in_gens_str_
. - The first line of the docstring should be imperative: "Return x" instead of "Returns x"
- I've shortened some method names, e.g.
g.TietzeList()
->g.Tietze
- I don't think we need
G.size()
in addition toG.cardinality()
andG.order()
. - Method names shouldn't sound like they mutate the object,
e.g.
G.simplified()
instead ofG.simplify()
- To convert different group presentations I'd prefer
G.as_permutation_group()
instead ofG.permutation_group()
. In particular since GAP knows so many ways to write a group, so it'll be less confusing in the long run.
I worked my way through everything but the braid group stuff. That is, I think anything but braid.py
is good to go. The braid groups still need some work as the base classes changed a bit. The following still needs to be done:
- Support
B.<s,t,u> = BraidGroup()
syntax - remove
__cmp__
to use GAP's internal comparison methods - remove unused imports
- move imports that are used only once (e.g. plotting) into the method that uses them. This helps to avoid circular imports in the long run.
I won't have time to work on this for at least a week, if you are interested please give it a try!
comment:56 Changed 10 years ago by
Wow, thanks for the great work. I will try to go through the braid code following your steps.
I have an issue thoough. I don't know which patch is exactly to blame, but the documentation does not build:
mmarco@neumann ~/sage-5.5.beta0 $ ./sage -docbuild reference html gap: halving pool size. gap: halving pool size. gap: halving pool size. gap: halving pool size. gap: halving pool size. gap: halving pool size. gap: halving pool size. gap: halving pool size. gap: halving pool size. gap: halving pool size. gap: halving pool size. gap: halving pool size. gap: halving pool size. gap: halving pool size. gap: halving pool size. gap: halving pool size. gap: halving pool size. gap: halving pool size. gap: halving pool size. gap: halving pool size. gap: halving pool size. gap: halving pool size. gap: halving pool size. gap: halving pool size. gap: halving pool size. gap: halving pool size. gap: halving pool size. gap: halving pool size. gap: halving pool size. gap: halving pool size. gap: halving pool size. gap: halving pool size. Traceback (most recent call last): File "/home/mmarco/sage-5.5.beta0/devel/sage/doc/common/builder.py", line 1083, in <module> getattr(get_builder(name), type)() File "/home/mmarco/sage-5.5.beta0/devel/sage/doc/common/builder.py", line 347, in _wrapper self.write_auto_rest_file(module_name) File "/home/mmarco/sage-5.5.beta0/devel/sage/doc/common/builder.py", line 606, in write_auto_rest_file title = self.get_module_docstring_title(module_name) File "/home/mmarco/sage-5.5.beta0/devel/sage/doc/common/builder.py", line 564, in get_module_docstring_title __import__(module_name) File "/home/mmarco/sage-5.5.beta0/local/lib/python2.7/site-packages/sage/groups/braid.py", line 446, in <module> class BraidGroup(FinitelyPresentedGroup): NameError: name 'FinitelyPresentedGroup' is not defined
comment:57 Changed 10 years ago by
With the previous patch (trac_12339_fpgroups_libgap.patch), the file devel/sage/sage/groups/finitely_presented.py
passes all tests. With the new patches, I get a ton of doctest failures in both finitely_presented.py
and free_group.py
.
comment:58 Changed 10 years ago by
I've recently updated the libgap patch #13687, make sure that you have the newest version.
If you just apply trac_12339_fpgroups.3.patch then everything should be fine. At least all doctests pass for me. The braid patchs needs to be updated, though.
Also note that I've removed FinitelyPresentedGroup
from the global namespace. Since you need to constrcut a FreeGroup
first there is no point in having an extra symbol; just create finitely presented groups as quotients.
comment:59 Changed 10 years ago by
Dependencies: | #6391, #13687 → #6391, #13687, #13588 |
---|
I meant the updated libgap patch at #13588. I just noticed that its wasn't in the dependencies, sorry about the confusion.
comment:60 follow-up: 67 Changed 10 years ago by
And about Miguel's error
Traceback (most recent call last): File "/home/mmarco/sage-5.5.beta0/devel/sage/doc/common/builder.py", line 1083, in <module> getattr(get_builder(name), type)() File "/home/mmarco/sage-5.5.beta0/devel/sage/doc/common/builder.py", line 347, in _wrapper self.write_auto_rest_file(module_name) File "/home/mmarco/sage-5.5.beta0/devel/sage/doc/common/builder.py", line 606, in write_auto_rest_file title = self.get_module_docstring_title(module_name) File "/home/mmarco/sage-5.5.beta0/devel/sage/doc/common/builder.py", line 564, in get_module_docstring_title __import__(module_name) File "/home/mmarco/sage-5.5.beta0/local/lib/python2.7/site-packages/sage/groups/braid.py", line 446, in <module> class BraidGroup(FinitelyPresentedGroup): NameError: name 'FinitelyPresentedGroup' is not defined
if you only apply trac_12339_fpgroups.3.patch: You should delete the file $SAGE_ROOT//devel/sage/doc/en/reference/sage/groups/braid.rst
in the Sage source tree. Sphinx doesn't remove its intermediate files under some circumstances, breaking the docbuild if these files reference no longer existing modules.
comment:61 Changed 10 years ago by
Good, the patch from #13588 fixes things. Thanks.
I'm running into another problem, which I found by working on #13254. I'm not sure what the issue is: two different presentations for the same group? Anyway, I'm getting a segfault, at least on OS X 10.8:
sage: G.<e0, e1, e2, e3, e4, e5, e6, e7, e8, e9> = FreeGroup() sage: rels = [e6, e5, e3, e9, e4*e7^-1*e6, e9*e7^-1*e0, e0*e1^-1*e2, e5*e1^-1*e8, e4*e3^-1*e8, e2] sage: G.quotient(rels) Finitely presented group < e0, e1, e2, e3, e4, e5, e6, e7, e8, e9 | e6, e5, e3, e9, e4*e7^-1*e6, e9*e7^-1*e0, e0*e1^-1*e2, e5*e1^-1*e8, e4*e3^-1*e8, e2 > sage: G.quotient(rels).simplified() Finitely presented group < e0 | e0^2 > sage: H.<e0, e1, e2, e3, e4, e5, e6, e7, e8, e9, e10, e11, e12, e13, e14, e15, e16, e17, e18, e19, e20, e21, e22, e23, e24, e25, e26, e27, e28, e29, e30, e31, e32, e33, e34, e35, e36, e37, e38, e39, e40> = FreeGroup() sage: rels = [e31*e20^-1*e23, e6, e4*e8^-1*e37, e24*e5^-1*e33, e36*e38^-1*e4, e35, e7*e25^-1*e24, e27*e5^-1*e23, e25, e26*e13^-1*e40, e3*e37^-1*e40, e31*e14^-1*e15, e28*e20^-1*e5, e21, e10*e20^-1*e34, e18*e34^-1*e23, e32*e13^-1*e37, e39*e34^-1*e21, e32*e26^-1*e3, e38, e28, e27, e3, e13*e12^-1*e33, e26, e1, e15, e36*e29^-1*e1, e31, e35*e9^-1*e8, e11*e9^-1*e37, e10*e11^-1*e6, e25*e16^-1*e17, e17*e33^-1*e19, e32, e39*e25^-1*e8, e9, e28*e9^-1*e24, e14, e19, e6*e16^-1*e2, e34, e38*e27^-1*e3, e0*e21^-1*e23, e38*e29^-1*e2, e1*e21^-1*e19, e39*e18^-1*e0, e26*e30^-1*e15, e18*e16^-1*e15, e10*e14^-1*e16, e30, e35*e14^-1*e1, e37*e22^-1*e33, e6*e34^-1*e22, e8, e35*e11^-1*e4, e32*e12^-1*e22, e29*e5^-1*e19, e24*e29^-1*e17, e13*e30^-1*e17, e36*e27^-1*e0, e7, e24, e11*e14^-1*e2, e12, e11*e20^-1*e22, e40*e15^-1*e17, e36*e5^-1*e21, e28*e31^-1*e27, e4*e0^-1*e3, e30*e12^-1*e19, e39, e7*e16^-1*e29, e18*e25^-1*e40, e22, e0*e8^-1*e40, e9*e20^-1*e33, e4*e1^-1*e2, e10*e31^-1*e18, e7*e6^-1*e38] sage: H.quotient(rels) Finitely presented group < e0, e1, e2, e3, e4, e5, e6, e7, e8, e9, e10, e11, e12, e13, e14, e15, e16, e17, e18, e19, e20, e21, e22, e23, e24, e25, e26, e27, e28, e29, e30, e31, e32, e33, e34, e35, e36, e37, e38, e39, e40 | e31*e20^-1*e23, e6, e4*e8^-1*e37, e24*e5^-1*e33, e36*e38^-1*e4, e35, e7*e25^-1*e24, e27*e5^-1*e23, e25, e26*e13^-1*e40, e3*e37^-1*e40, e31*e14^-1*e15, e28*e20^-1*e5, e21, e10*e20^-1*e34, e18*e34^-1*e23, e32*e13^-1*e37, e39*e34^-1*e21, e32*e26^-1*e3, e38, e28, e27, e3, e13*e12^-1*e33, e26, e1, e15, e36*e29^-1*e1, e31, e35*e9^-1*e8, e11*e9^-1*e37, e10*e11^-1*e6, e25*e16^-1*e17, e17*e33^-1*e19, e32, e39*e25^-1*e8, e9, e28*e9^-1*e24, e14, e19, e6*e16^-1*e2, e34, e38*e27^-1*e3, e0*e21^-1*e23, e38*e29^-1*e2, e1*e21^-1*e19, e39*e18^-1*e0, e26*e30^-1*e15, e18*e16^-1*e15, e10*e14^-1*e16, e30, e35*e14^-1*e1, e37*e22^-1*e33, e6*e34^-1*e22, e8, e35*e11^-1*e4, e32*e12^-1*e22, e29*e5^-1*e19, e24*e29^-1*e17, e13*e30^-1*e17, e36*e27^-1*e0, e7, e24, e11*e14^-1*e2, e12, e11*e20^-1*e22, e40*e15^-1*e17, e36*e5^-1*e21, e28*e31^-1*e27, e4*e0^-1*e3, e30*e12^-1*e19, e39, e7*e16^-1*e29, e18*e25^-1*e40, e22, e0*e8^-1*e40, e9*e20^-1*e33, e4*e1^-1*e2, e10*e31^-1*e18, e7*e6^-1*e38 > sage: H.quotient(rels).simplified() # should be Finitely presented group < e0 | e0^2 > Exception RuntimeError: "Error, no method found! For debugging hints type ?Recovery from NoMethodFound\nError, no 1st choice method found for `<' on 2 arguments\n" in 'sage.libs.gap.util.error_handler' ignored ------------------------------------------------------------------------ Unhandled SIGSEGV: A segmentation fault occurred in Sage. This probably occurred because a *compiled* component of Sage has a bug in it and is not properly wrapped with sig_on(), sig_off(). You might want to run Sage under gdb with 'sage -gdb' to debug this. Sage will now terminate. ------------------------------------------------------------------------
comment:62 Changed 10 years ago by
I have done the changes you suggested to braid groups, except for the cmp method: we make use of the fact that word problem is solvable in braid groups, because of the normal form. This way, we really check if two braids, that can look really different, are the same or not.
It seems to solve the problem with the documentation building.
Changed 10 years ago by
Attachment: | trac_12339_braid_groups_4.patch added |
---|
apply over volker's last patch.
comment:63 Changed 10 years ago by
For what it's worth, I get the same error as above on sage.math. A simpler example:
sage: G.<e0> = FreeGroup() sage: relns_G = [e0^2] sage: H.<e0, e1> = FreeGroup() sage: relns_H = [e0^2, e1] sage: G2 = G / relns_G sage: H2 = H / relns_H sage: G2.simplified() Finitely presented group < e0 | e0^2 > sage: H2.simplified() Exception RuntimeError: "Error, no method found! For debugging hints type ?Recovery from NoMethodFound\nError, no 1st choice method found for `<' on 2 arguments\n" in 'sage.libs.gap.util.error_handler' ignored /scratch/palmieri/sage-5.5.rc0/local/lib/libcsage.so(print_backtrace+0x31)[0x7f5a11f63207] /scratch/palmieri/sage-5.5.rc0/local/lib/libcsage.so(sigdie+0x14)[0x7f5a11f63239] /scratch/palmieri/sage-5.5.rc0/local/lib/libcsage.so(sage_signal_handler+0x216)[0x7f5a11f62e16] /lib/libpthread.so.0[0x7f5a171797d0] [0x7f58e53e47d0] ------------------------------------------------------------------------ Unhandled SIGSEGV: A segmentation fault occurred in Sage. This probably occurred because a *compiled* component of Sage has a bug in it and is not properly wrapped with sig_on(), sig_off(). You might want to run Sage under gdb with 'sage -gdb' to debug this. Sage will now terminate. ------------------------------------------------------------------------
It looks like the issue is using the same generator names for G
and H
: if I change it so H
is defined by H.<f0, f1> = FreeGroup()
, I don't get this problem. I think this needs to be dealt with, and a doctest needs to be added verifying that it has been dealt with.
comment:64 Changed 10 years ago by
Description: | modified (diff) |
---|
The problem was that GAP doesn't allow comparison of some objects (e.g. FreeGroup). Since the finitely presented group is unique, you could only call wrap_FreeGroup
once; the second time fails. Because the comparison in libgap wasn't properly wrapped in sig_on/off
this then aborted. Fixed in the attached patch and the updated libgap at #13588.
comment:65 follow-up: 66 Changed 10 years ago by
Thanks, Volker, your new patches fixed my problem. It sounds like you're saying that there is no good way to have
sage: G.<e0> = FreeGroup() sage: relns_G = [e0^2] sage: H.<e0, e1> = FreeGroup() sage: relns_H = [e0^2, e1] sage: G2 = G / relns_G sage: H2 = H / relns_H sage: G2 == H2
return True? That's unfortunate. Should __eq__
raise a NotImplementedError
instead, or is that too unpythonic?
comment:66 Changed 10 years ago by
Replying to jhpalmieri:
Thanks, Volker, your new patches fixed my problem. It sounds like you're saying that there is no good way to have
sage: G.<e0> = FreeGroup() sage: relns_G = [e0^2] sage: H.<e0, e1> = FreeGroup() sage: relns_H = [e0^2, e1] sage: G2 = G / relns_G sage: H2 = H / relns_H sage: G2 == H2return True? That's unfortunate. Should
__eq__
raise aNotImplementedError
instead, or is that too unpythonic?
it seems to be more subtle, as the group presentations are different. GAP has several different classes of objects for finitely presented groups, with some of them having presentation explicit.
GAP can check for finite group isomorphism.
The concept of free group in Sage ought to be better defined, i.e. currently it seems to be a group with an attached presentation. It would be good to have this explicitly explained in documentation.
comment:67 Changed 10 years ago by
Replying to vbraun:
And about Miguel's error
[snip ...]
if you only apply trac_12339_fpgroups.3.patch: You should delete the file
$SAGE_ROOT//devel/sage/doc/en/reference/sage/groups/braid.rst
in the Sage source tree. Sphinx doesn't remove its intermediate files under some circumstances, breaking the docbuild if these files reference no longer existing modules.
I think the issue is that line 93 of braid.py should be changed from
from sage.groups.finitely_presented import FinitelyPresentedGroupElement
to
from sage.groups.finitely_presented import FinitelyPresentedGroup, FinitelyPresentedGroupElement
comment:68 Changed 10 years ago by
Description: | modified (diff) |
---|---|
Status: | needs_work → needs_review |
The final patch adds:
- Indentation & spacing fixed
- Renamed
BraidGroup_class.MappingClassGroup()
->BraidGroup_class.mapping_class_group()
. Use CamelCase for classes, lower-case underscore names for methods.
- Let the coercion system discover mapping group actions on suitable free groups, so the following works without further ado:
sage: B.<b0,b1,b2> = BraidGroup() sage: F.<f0,f1,f2,f3> = FreeGroup() sage: f1 * b1 f1*f2*f1^-1
As far as I'm concerned this ticket is good (enough) to go.
Comparison should be fixed, of course. By default, ==
should just compare the presentation of the group and not up to isomorphism. Checking up to isomorphism should be done with an is_isomorphic()
method so its not used in caching.
comment:69 Changed 10 years ago by
Description: | modified (diff) |
---|
comment:70 Changed 10 years ago by
Volker, since you have contributed significantly to the code, would it be apropriate if you gave the positive review? Or should somebody else review it?
comment:71 Changed 10 years ago by
Authors: | Miguel Marco → Miguel Marco, Volker Braun |
---|
Its fairly common that the set of authors equals the set of reviewers. As I said before, I'm fine with the current state and everything that I wanted changed is changed. If you agree with my changes then add yourself to the reviewers and let's call it a day!
Changed 10 years ago by
Attachment: | trac_12339_pickling.patch added |
---|
Solved minor issue with braid pickling
comment:72 Changed 10 years ago by
Description: | modified (diff) |
---|---|
Status: | needs_review → positive_review |
comment:73 Changed 10 years ago by
Ok, i just added a minor correction to braid pickling. Now all doctests and testsuites run fine.
comment:74 Changed 10 years ago by
Milestone: | sage-5.5 → sage-pending |
---|
comment:75 Changed 10 years ago by
Status: | positive_review → needs_info |
---|
I have some comments regarding this patch. I myself can not give much technical input, but I have a colleague here who has been trying to use this and has come across some inconsistencies.
- Is there a reason why a
FreeGroupElement
does not have the__call__
method? AFreeMonoidElement
does have the__call__
method. This is needed to make the following worksage: G.<a,b> = FreeGroup() sage: a.subs(a=1,b=2) # We would expect the answer to be 1 a
- Related to the implementation of the
__call__
method is the following problem. Suppose in order to makesubs()
work, we implement the__call__
method. The current code has to calla.Tietze()
to get the index of the free generatora
and its exponent. For a more complicated expression the output is as follows, and we would have to go along and parse the output tuple to find out the exponent by counting. Is there any method (maybe in GAP) which outputs just a list of tuples[(generator1, exponent1), (generator2, exponent2),...]
. This is again howFreeMonoid
is implemented.sage: (a^2 * b^-3).Tietze() (1, 1, -2, -2, -2) sage: (a^2 * b^-3).some_function() # some function which gives (generator, exponent) tuples [(a, 2), (b, -3)]
- There is also this inconsistency in the output of the following two functions. In language, they say the same thing, but they are not mathematically equal (according to the current implementation):
sage: G.<a,b> = FreeGroup() sage: test = (a).fox_derivative(a) sage: f = test.parent() sage: g = GroupAlgebra(G, ZZ) sage: print f Group algebra of Free Group on generators {a, b, c, d, e} over Integer Ring sage: print g Group algebra of group "Free Group on generators {a, b, c, d, e}" over base ring Integer Ring sage: print f == g False
comment:76 Changed 10 years ago by
Status: | needs_info → needs_review |
---|
Can you open a new ticket for feature requests? I'm happy to help but not on this ticket.
3) is a consequence of the combinat guys having their own group algebra implementation:
sage: type(f) <class 'sage.combinat.free_module.CombinatorialFreeModule_with_category'> sage: type(g) <class 'sage.algebras.group_algebra_new.GroupAlgebra_with_category'>
comment:77 Changed 10 years ago by
Status: | needs_review → positive_review |
---|
comment:78 Changed 10 years ago by
I posted your observation to combinat-devel, let's see what they have to say: https://groups.google.com/d/topic/sage-combinat-devel/f_Und2NDyFE/discussion
comment:80 Changed 10 years ago by
Milestone: | sage-pending → sage-5.7 |
---|
comment:81 Changed 10 years ago by
The ticket is ready, and their dependencies are either already merged or almost ready to be merged. So i moved its milestone from sage-pending to sage-5.7
comment:82 Changed 10 years ago by
Merged in: | → sage-5.7.beta3 |
---|---|
Resolution: | → fixed |
Status: | positive_review → closed |
a proof of concept of the free group implementation