Opened 11 years ago

Closed 10 years ago

# Free Groups

Reported by: Owned by: Miguel Marco joyner major sage-5.7 group theory free groups, finitely presented groups, braids combinatorics, Syed ahmad Lavasani, Vincent Delecroix, John Palmieri, Timo Jolivet, Rob Beezer, Dima Pasechnik sage-5.7.beta3 Miguel Marco, Volker Braun Volker Braun N/A #6391, #13687, #13588

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

### Changed 11 years ago by Miguel Marco

a proof of concept of the free group implementation

### comment:1 Changed 11 years ago by Miguel Marco

Added a new version with finitely presented groups.

### comment:2 Changed 11 years ago by Miguel Marco

Authors: → Miguel Marco combinatorics added new → needs_review

### comment:3 Changed 11 years ago by Miguel Marco

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

### comment:4 Changed 11 years ago by Syed ahmad Lavasani

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

### comment:6 Changed 11 years ago by Miguel Marco

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

### comment:7 Changed 11 years ago by Vincent Delecroix

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:9 Changed 11 years ago by Miguel Marco

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 11 years ago by Miguel Marco

Updated, fully doctested

### comment:10 Changed 11 years ago by Miguel Marco

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 Miguel Marco

solved a minor issue, apply over the previous one

### Changed 11 years ago by Miguel Marco

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

### Changed 11 years ago by Miguel Marco

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

### comment:11 Changed 11 years ago by Miguel Marco

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 Miguel Marco

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 Miguel Marco

Status: needs_work → needs_review

### comment:14 Changed 10 years ago by Miguel Marco

Description: modified (diff)

### comment:15 Changed 10 years ago by Karl-Dieter Crisman

It looks like this resolves #876.

### comment:16 Changed 10 years ago by Miguel Marco

Description: modified (diff)

### comment:17 Changed 10 years ago by Miguel Marco

apply trac_12339_fpgroups.patch

### comment:20 Changed 10 years ago by John Palmieri

• 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 Miguel Marco

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 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 10 years ago by Miguel Marco

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.

```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 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:26 follow-up:  27 Changed 10 years ago by John Palmieri

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 10 years ago by John Palmieri (previous) (diff)

### comment:27 in reply to:  26 Changed 10 years ago by Rob Beezer

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 10 years ago by Miguel Marco

Apply over 12339_fpgroups.patch

### comment:28 Changed 10 years ago by Miguel Marco

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 10 years ago by Miguel Marco

apply trac_12339_fpgroups.patch trac_12339_fpgroups.2.patch

### comment:30 follow-up:  31 Changed 10 years ago by Miguel Marco

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 10 years ago by Rob Beezer

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

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 Miguel Marco

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 10 years ago by Rob Beezer

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 Miguel Marco

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

### comment:35 Changed 10 years ago by John Palmieri

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 Rob Beezer

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 Miguel Marco

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

### comment:38 Changed 10 years ago by Miguel Marco

Cc: Dima Pasechnik added modified (diff)

### comment:39 Changed 10 years ago by Volker Braun

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
```
```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 10 years ago by Volker Braun

Dependencies: → #6391 → sage-5.5 minor → major → Volker Braun

### comment:42 Changed 10 years ago by Miguel Marco

apply trac_12339_fpgroups_libgap.patch

### comment:43 Changed 10 years ago by Volker Braun

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 Miguel Marco

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 Miguel Marco

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

### Changed 10 years ago by Miguel Marco

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

### comment:46 Changed 10 years ago by Miguel Marco

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 Volker Braun

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 Miguel Marco

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 Volker Braun

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 Volker Braun

Dependencies: #6391 → #6391, #13687 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 Miguel Marco

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 Volker Braun

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

Rebased version

### comment:53 Changed 10 years ago by Miguel Marco

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 Volker Braun

Description: modified (diff) finitely presented braids added

Improved patch

split patch

### comment:55 Changed 10 years ago by Volker Braun

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 10 years ago by Miguel Marco

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 John Palmieri

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 Volker Braun

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 Volker Braun

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 Volker Braun

```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 John Palmieri

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 Miguel Marco

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 Miguel Marco

apply over volker's last patch.

### comment:63 Changed 10 years ago by John Palmieri

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]
[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.

Improved patch

### comment:64 Changed 10 years ago by Volker Braun

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 John Palmieri

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 10 years ago by Dima Pasechnik

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 10 years ago by John Palmieri

[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
```

Initial patch

### comment:68 Changed 10 years ago by Volker Braun

Description: modified (diff) needs_work → needs_review

• 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 Volker Braun

Description: modified (diff)

### comment:70 Changed 10 years ago by Miguel Marco

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 Volker Braun

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 Miguel Marco

Solved minor issue with braid pickling

### comment:72 Changed 10 years ago by Miguel Marco

Description: modified (diff) needs_review → positive_review

### comment:73 Changed 10 years ago by Miguel Marco

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

### comment:74 Changed 10 years ago by Jeroen Demeyer

Milestone: sage-5.5 → sage-pending

### comment:75 Changed 10 years ago by Punarbasu Purkayastha

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.

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 10 years ago by Volker Braun

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 Volker Braun

Status: needs_review → positive_review

### comment:78 Changed 10 years ago by Volker Braun

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 10 years ago by Punarbasu Purkayastha

Opened #14010 to track the discussion.

### comment:80 Changed 10 years ago by Miguel Marco

Milestone: sage-pending → sage-5.7

### comment:81 Changed 10 years ago by Miguel Marco

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 Jeroen Demeyer

Merged in: → sage-5.7.beta3 → fixed positive_review → closed
Note: See TracTickets for help on using tickets.