#12339: Free Groups
------------------------------------------------------------------+---------
Reporter: mmarco |
Owner: joyner
Type: enhancement |
Status: needs_work
Priority: major |
Milestone: sage-5.5
Component: group theory |
Resolution:
Keywords: free groups, finitely presented groups, braids | Work
issues:
Report Upstream: N/A |
Reviewers: Volker Braun
Authors: Miguel Marco | Merged
in:
Dependencies: #6391, #13687 |
Stopgaps:
------------------------------------------------------------------+---------
Old description:
> 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, and then apply
> [attachment:trac_12339_fpgroups.patch],
> [attachment:trac_12339_braids.patch]
New description:
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, and then apply
[attachment:trac_12339_fpgroups.3.patch],
[attachment:trac_12339_braids.patch]
--
Comment (by vbraun):
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!
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12339#comment:55>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
