#12339: Free Groups
--------------------------------+-------------------------------------------
Reporter: mmarco | Owner: joyner
Type: enhancement | Status: needs_review
Priority: minor | Milestone:
Component: group theory | Resolution:
Keywords: free groups | Work issues:
Report Upstream: N/A | Reviewers:
Authors: Miguel Marco | Merged in:
Dependencies: | Stopgaps:
--------------------------------+-------------------------------------------
Changes (by mmarco):
* cc: dimpase (added)
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=FreeGroup('a,b,c,d,e')
> sage: G.inject_variables()
> Defining a, b, c, d, e
> sage: a*b*c*d/a/a/e
> a*b*c*d*a^-2*e^-1
> sage:
> H=G.quotient([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=FreeGroup('a,b,c')
> sage: G.inject_variables()
> Defining a, b, c
> 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[<identity ...>] + B[a*b] - B[a*b*a*b^-1*a^-1]
> sage: H.alexander_matrix()
> [ B[<identity ...>] + B[a*b] B[a] + B[a*b*a]
> 0]
> [ B[<identity ...>] + B[a] 0
> 0]
> [ 0 B[<identity ...>] + B[b]
> 0]
> [ 0 0
> B[<identity ...>] + B[c]]
> [B[<identity ...>] + B[a*b*c] B[a] + B[a*b*c*a] B[a*b]
> + B[a*b*c*a*b]]
> }}}
>
> Some properties of finitely presented groups.
>
> {{{
> sage: G=FreeGroup(3)
> sage: G.inject_variables()
> Defining x0, x1, x2
> sage: H=G.quotient([x0*x1*x2*x0*x1*x2,x1*x2*x0*x1*x2,x2^2])
> sage: H.simplification_isomorphism()
> Generic morphism:
> From: Finitely Presented Group on generators ('x0', 'x1', 'x2')
> and relations (x0*x1*x2*x0*x1*x2, x1*x2*x0*x1*x2, x2^2)
> To: Finitely Presented Group on generators ('x1', 'x2')
> and relations (x2^2, x1*x2*x1*x2)
> sage: H.abelian_invariants()
> [2, 2]
> sage: H.simplification_isomorphism()(x0)
> <identity ...>
> 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 on generators ('x0', 'x1', 'x2')
> and relations (x0^2, x1^2, x2^3, x0*x1*x0*x1, x0*x2*x0*x2,
> x1*x2*x1*x2*x1*x2)
> To: Finitely Presented Group on generators ('x0', 'x1', 'x2')
> and relations (x0^2, x1^2, x2^3, x0*x1*x0*x1, x0*x2*x0*x2,
> x1*x2*x1*x2*x1*x2)
> sage: H.size()
> 24
> sage: H.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.
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=FreeGroup('a,b,c,d,e')
sage: G.inject_variables()
Defining a, b, c, d, e
sage: a*b*c*d/a/a/e
a*b*c*d*a^-2*e^-1
sage:
H=G.quotient([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=FreeGroup('a,b,c')
sage: G.inject_variables()
Defining a, b, c
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[<identity ...>] + B[a*b] - B[a*b*a*b^-1*a^-1]
sage: H.alexander_matrix()
[ B[<identity ...>] + B[a*b] B[a] + B[a*b*a]
0]
[ B[<identity ...>] + B[a] 0
0]
[ 0 B[<identity ...>] + B[b]
0]
[ 0 0 B[<identity
...>] + B[c]]
[B[<identity ...>] + B[a*b*c] B[a] + B[a*b*c*a] B[a*b] +
B[a*b*c*a*b]]
}}}
Some properties of finitely presented groups.
{{{
sage: G=FreeGroup(3)
sage: G.inject_variables()
Defining x0, x1, x2
sage: H=G.quotient([x0*x1*x2*x0*x1*x2,x1*x2*x0*x1*x2,x2^2])
sage: H.simplification_isomorphism()
Generic morphism:
From: Finitely Presented Group on generators ('x0', 'x1', 'x2')
and relations (x0*x1*x2*x0*x1*x2, x1*x2*x0*x1*x2, x2^2)
To: Finitely Presented Group on generators ('x1', 'x2')
and relations (x2^2, x1*x2*x1*x2)
sage: H.abelian_invariants()
[2, 2]
sage: H.simplification_isomorphism()(x0)
<identity ...>
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 on generators ('x0', 'x1', 'x2')
and relations (x0^2, x1^2, x2^3, x0*x1*x0*x1, x0*x2*x0*x2,
x1*x2*x1*x2*x1*x2)
To: Finitely Presented Group on generators ('x0', 'x1', 'x2')
and relations (x0^2, x1^2, x2^3, x0*x1*x0*x1, x0*x2*x0*x2,
x1*x2*x1*x2*x1*x2)
sage: H.size()
24
sage: H.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_libgap.patch]
--
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12339#comment:38>
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.
