Free Groups

[miguelmarco]

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

• attachment: trac_12339_fpgroups_vb.patch,
• attachment: trac_12339_braids.patch
• attachment: trac_12339_braid_groups_4.patch
• attachment: trac_12339_braid_groups_review.patch
• attachment: trac_12339_pickling.patch

Depends on #6391
Depends on #13687
Depends on #13588

CC: @sagetrac-sage-combinat @sagetrac-sydahmad @videlec @jhpalmieri @sagetrac-tjolivet @rbeezer @dimpase

Component: group theory

Keywords: free groups, finitely presented groups, braids

Author: Miguel Marco, Volker Braun

Reviewer: Volker Braun

Merged: sage-5.7.beta3

Issue created by migration from https://trac.sagemath.org/ticket/12339

[miguelmarco]

a proof of concept of the free group implementation

[miguelmarco]

Attachment: freegroups.py.gz

[miguelmarco]

comment:1

Attachment: freegroups.2.py.gz

Added a new version with finitely presented groups.

[miguelmarco]

Author: Miguel Marco

[miguelmarco]

comment:3

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

[sagetrac-sydahmad]

comment:4

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

[miguelmarco]

comment:6

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

[videlec]

comment:7

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