Opened 6 years ago

Closed 5 years ago

#12339 closed enhancement (fixed)

Free Groups

Reported by: mmarco Owned by: joyner
Priority: major Milestone: sage-5.7
Component: group theory Keywords: free groups, finitely presented groups, braids
Cc: combinatorics, sydahmad, vdelecroix, jhpalmieri, tjolivet, rbeezer, dimpase 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 mmarco)

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)

freegroups.py (4.0 KB) - added by mmarco 6 years ago.
a proof of concept of the free group implementation
freegroups.2.py (12.5 KB) - added by mmarco 6 years ago.
16190.patch (54.6 KB) - added by mmarco 5 years ago.
Updated, fully doctested
12339-minor.patch (535 bytes) - added by mmarco 5 years ago.
solved a minor issue, apply over the previous one
12339-cmp.patch (842 bytes) - added by mmarco 5 years ago.
added comparison of braids, apply over 12339-minor.patch
16192.patch (7.9 KB) - added by mmarco 5 years ago.
for using with libgap. apply over 16190.patch. deppends on 6391
trac_12339_fpgroups.patch (66.7 KB) - added by mmarco 5 years ago.
Newer version
trac_12339_fpgroups.2.patch (8.8 KB) - added by mmarco 5 years ago.
Apply over 12339_fpgroups.patch
trac_12339_fpgroups_libgap_minor_changes.patch (4.9 KB) - added by mmarco 5 years ago.
minor changes to the previous version. Should be applied over the previous one.
trac_12339_fpgroups_libgap.patch (76.0 KB) - added by mmarco 5 years ago.
Rebased version
trac_12339_fpgroups.3.patch (55.3 KB) - added by vbraun 5 years ago.
Improved patch
trac_12339_braids.patch (28.9 KB) - added by vbraun 5 years ago.
split patch
trac_12339_braid_groups_4.patch (12.2 KB) - added by mmarco 5 years ago.
apply over volker's last patch.
trac_12339_fpgroups_vb.patch (56.7 KB) - added by vbraun 5 years ago.
Improved patch
trac_12339_braid_groups_review.patch (47.1 KB) - added by vbraun 5 years ago.
Initial patch
trac_12339_pickling.patch (1.4 KB) - added by mmarco 5 years ago.
Solved minor issue with braid pickling

Download all attachments as: .zip

Change History (98)

Changed 6 years ago by mmarco

a proof of concept of the free group implementation

Changed 6 years ago by mmarco

comment:1 Changed 6 years ago by mmarco

Added a new version with finitely presented groups.

comment:2 Changed 6 years ago by mmarco

  • Authors set to Miguel Marco
  • Cc combinatorics added
  • Status changed from new to needs_review

comment:3 Changed 5 years ago by mmarco

I have added a patch with the free groups, finitely presented groups and braid groups.

comment:4 Changed 5 years ago by sydahmad

It isn't a bad idea, if you write in the desc that people need to apply all three patches.

comment:5 Changed 5 years ago by sydahmad

  • Cc sydahmad added

comment:6 Changed 5 years ago by mmarco

Actuually, you don't. The last patch does all the work.

comment:7 Changed 5 years ago by vdelecroix

  • Status changed from needs_review to 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 5 years ago by vdelecroix

  • Cc vdelecroix added

comment:9 Changed 5 years ago by mmarco

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.

Changed 5 years ago by mmarco

Updated, fully doctested

comment:10 Changed 5 years ago by mmarco

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 5 years ago by mmarco

solved a minor issue, apply over the previous one

Changed 5 years ago by mmarco

added comparison of braids, apply over 12339-minor.patch

Changed 5 years ago by mmarco

for using with libgap. apply over 16190.patch. deppends on 6391

comment:11 Changed 5 years ago by mmarco

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 5 years ago by mmarco

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 5 years ago by mmarco

  • Status changed from needs_work to needs_review

comment:14 Changed 5 years ago by mmarco

  • Description modified (diff)

comment:15 Changed 5 years ago by kcrisman

It looks like this resolves #876.

Changed 5 years ago by mmarco

Newer version

comment:16 Changed 5 years ago by mmarco

  • Description modified (diff)

comment:17 Changed 5 years ago by mmarco

apply trac_12339_fpgroups.patch

comment:18 Changed 5 years ago by jhpalmieri

  • Cc jhpalmieri added

comment:19 Changed 5 years ago by tjolivet

  • Cc tjolivet added

comment:20 Changed 5 years ago by jhpalmieri

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 5 years ago by mmarco

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 5 years ago by jlopez

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 5 years ago by mmarco

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 5 years ago by jlopez

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

  1. "Reduce powers of x modulo 5"
  2. "Reduce powers of y modulo 4"
  3. "Replace each y^ax^b by x^(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 5 years ago by rbeezer

  • Cc rbeezer added

comment:26 follow-up: Changed 5 years ago by jhpalmieri

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.)

Last edited 5 years ago by jhpalmieri (previous) (diff)

comment:27 in reply to: ↑ 26 Changed 5 years ago by rbeezer

Replying to jhpalmieri:

I would suggest replacing size with cardinality.

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) 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.

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 5 years ago by mmarco

Apply over 12339_fpgroups.patch

comment:28 Changed 5 years ago by mmarco

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:29 Changed 5 years ago by mmarco

apply trac_12339_fpgroups.patch trac_12339_fpgroups.2.patch

comment:30 follow-up: Changed 5 years ago by mmarco

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 in reply to: ↑ 30 Changed 5 years ago by rbeezer

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: Changed 5 years ago by mmarco

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 in reply to: ↑ 32 Changed 5 years ago by rbeezer

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 5 years ago by mmarco

Well, at least it would help to know that ubuntu 12.04 is not affected.

comment:35 Changed 5 years ago by jhpalmieri

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 5 years ago by rbeezer

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 5 years ago by mmarco

Thanks, so it seems that the issue is specific on some older kernels.

comment:38 Changed 5 years ago by mmarco

  • Cc dimpase added
  • Description modified (diff)

comment:39 Changed 5 years ago by vbraun

Looks great! Some libgap notes:

  • libgap makes sure to lazy import itself, since gap startup takes some time. Hence sage/libs/all.py defines
    from 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 from sage/groups/all.py. This will help Sage in the long run to avoid long startup times. Also, its better to import libgap as from 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 of def __init__(self,ll=[],parent=None)
  • Use
    EXAMPLES::
       
        sage: 1+1
    
    instead of the multi-line
    EXAMPLES: 
    
    :: 
    
        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 as
    gap = 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: and OUTPUT: sections in the docstrings. You know what the methods are for, but we don't ;-)

comment:40 Changed 5 years ago by vbraun

  • Dependencies set to #6391
  • Milestone set to sage-5.5
  • Priority changed from minor to major
  • Reviewers set to Volker Braun

comment:41 Changed 5 years ago by mmarco

I have addressed the issues. Please review it.

comment:42 Changed 5 years ago by mmarco

apply trac_12339_fpgroups_libgap.patch

comment:43 Changed 5 years ago by vbraun

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 5 years ago by mmarco

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 5 years ago by mmarco

I see the problem now: Group inherits from ParentWithGens?. Should i not inherit from Group then?

Changed 5 years ago by mmarco

minor changes to the previous version. Should be applied over the previous one.

comment:46 Changed 5 years ago by mmarco

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 5 years ago by vbraun

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 5 years ago by mmarco

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 5 years ago by vbraun

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 5 years ago by vbraun

  • Dependencies changed from #6391 to #6391, #13687
  • Status changed from needs_review to 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 5 years ago by mmarco

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 5 years ago by vbraun

Sorry if I wasn't clear, #13687 bases sage.groups.group.Group on Parent. So you should just derive from Group.

Changed 5 years ago by mmarco

Rebased version

comment:53 Changed 5 years ago by mmarco

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 5 years ago by vbraun

  • Description modified (diff)
  • Keywords finitely presented braids added

Changed 5 years ago by vbraun

Improved patch

Changed 5 years ago by vbraun

split patch

comment:55 Changed 5 years ago by vbraun

  • 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 calls Parent.__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 to G.cardinality() and G.order().
  • Method names shouldn't sound like they mutate the object, e.g. G.simplified() instead of G.simplify()
  • To convert different group presentations I'd prefer G.as_permutation_group() instead of G.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 5 years ago by mmarco

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 5 years ago by jhpalmieri

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 5 years ago by vbraun

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 5 years ago by vbraun

  • Dependencies changed from #6391, #13687 to #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: Changed 5 years ago by vbraun

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 5 years ago by jhpalmieri

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 5 years ago by mmarco

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 5 years ago by mmarco

apply over volker's last patch.

comment:63 Changed 5 years ago by jhpalmieri

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.

Changed 5 years ago by vbraun

Improved patch

comment:64 Changed 5 years ago by vbraun

  • 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: Changed 5 years ago by 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 == H2

return True? That's unfortunate. Should __eq__ raise a NotImplementedError instead, or is that too unpythonic?

comment:66 in reply to: ↑ 65 Changed 5 years ago by dimpase

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 == H2

return True? That's unfortunate. Should __eq__ raise a NotImplementedError 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 in reply to: ↑ 60 Changed 5 years ago by jhpalmieri

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

Changed 5 years ago by vbraun

Initial patch

comment:68 Changed 5 years ago by vbraun

  • Description modified (diff)
  • Status changed from needs_work to 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 5 years ago by vbraun

  • Description modified (diff)

comment:70 Changed 5 years ago by mmarco

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 5 years ago by vbraun

  • Authors changed from Miguel Marco to 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 5 years ago by mmarco

Solved minor issue with braid pickling

comment:72 Changed 5 years ago by mmarco

  • Description modified (diff)
  • Status changed from needs_review to positive_review

comment:73 Changed 5 years ago by mmarco

Ok, i just added a minor correction to braid pickling. Now all doctests and testsuites run fine.

comment:74 Changed 5 years ago by jdemeyer

  • Milestone changed from sage-5.5 to sage-pending

comment:75 Changed 5 years ago by ppurka

  • Status changed from positive_review to 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.

  1. Is there a reason why a FreeGroupElement does not have the __call__ method? A FreeMonoidElement does have the __call__ method. This is needed to make the following work
    sage: G.<a,b> = FreeGroup()
    sage: a.subs(a=1,b=2) # We would expect the answer to be 1
    a
    
  2. Related to the implementation of the __call__ method is the following problem. Suppose in order to make subs() work, we implement the __call__ method. The current code has to call a.Tietze() to get the index of the free generator a 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 how FreeMonoid 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)]
    
  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 5 years ago by vbraun

  • Status changed from needs_info to 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 5 years ago by vbraun

  • Status changed from needs_review to positive_review

comment:78 Changed 5 years ago by vbraun

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:79 Changed 5 years ago by ppurka

Opened #14010 to track the discussion.

comment:80 Changed 5 years ago by mmarco

  • Milestone changed from sage-pending to sage-5.7

comment:81 Changed 5 years ago by mmarco

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 5 years ago by jdemeyer

  • Merged in set to sage-5.7.beta3
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.