Finitely Presented Groups¶
Finitely presented groups are constructed as quotients of
free_group
:
sage: F.<a,b,c> = FreeGroup()
sage: G = F / [a^2, b^2, c^2, a*b*c*a*b*c]
sage: G
Finitely presented group < a, b, c | a^2, b^2, c^2, (a*b*c)^2 >
One can create their elements by multiplying the generators or by
specifying a Tietze list (see
Tietze()
)
as in the case of free groups:
sage: G.gen(0) * G.gen(1)
a*b
sage: G([1,2,-1])
a*b*a^-1
sage: a.parent()
Free Group on generators {a, b, c}
sage: G.inject_variables()
Defining a, b, c
sage: a.parent()
Finitely presented group < a, b, c | a^2, b^2, c^2, (a*b*c)^2 >
Notice that, even if they are represented in the same way, the elements of a finitely presented group and the elements of the corresponding free group are not the same thing. However, they can be converted from one parent to the other:
sage: F.<a,b,c> = FreeGroup()
sage: G = F / [a^2,b^2,c^2,a*b*c*a*b*c]
sage: F([1])
a
sage: G([1])
a
sage: F([1]) is G([1])
False
sage: F([1]) == G([1])
False
sage: G(a*b/c)
a*b*c^-1
sage: F(G(a*b/c))
a*b*c^-1
Finitely presented groups are implemented via GAP. You can use the
gap()
method to access
the underlying LibGAP object:
sage: G = FreeGroup(2)
sage: G.inject_variables()
Defining x0, x1
sage: H = G / (x0^2, (x0*x1)^2, x1^2)
sage: H.gap()
<fp group on the generators [ x0, x1 ]>
This can be useful, for example, to use GAP functions that are not yet wrapped in Sage:
sage: H.gap().LowerCentralSeries()
[ Group(<fp, no generators known>), Group(<fp, no generators known>) ]
The same holds for the group elements:
sage: G = FreeGroup(2)
sage: H = G / (G([1, 1]), G([2, 2, 2]), G([1, 2, -1, -2])); H
Finitely presented group < x0, x1 | x0^2, x1^3, x0*x1*x0^-1*x1^-1 >
sage: a = H([1])
sage: a
x0
sage: a.gap()
x0
sage: a.gap().Order()
2
sage: type(_) # note that the above output is not a Sage integer
<type 'sage.libs.gap.element.GapElement_Integer'>
You can use call syntax to replace the generators with a set of arbitrary ring elements. For example, take the free abelian group obtained by modding out the commutator subgroup of the free group:
sage: G = FreeGroup(2)
sage: G_ab = G / [G([1, 2, -1, -2])]; G_ab
Finitely presented group < x0, x1 | x0*x1*x0^-1*x1^-1 >
sage: a,b = G_ab.gens()
sage: g = a * b
sage: M1 = matrix([[1,0],[0,2]])
sage: M2 = matrix([[0,1],[1,0]])
sage: g(3, 5)
15
sage: g(M1, M1)
[1 0]
[0 4]
sage: M1*M2 == M2*M1 # matrices do not commute
False
sage: g(M1, M2)
Traceback (most recent call last):
...
ValueError: the values do not satisfy all relations of the group
Warning
Some methods are not guaranteed to finish since the word problem for finitely presented groups is, in general, undecidable. In those cases the process may run until the available memory is exhausted.
REFERENCES:
AUTHOR:
- Miguel Angel Marco Buzunariz
-
sage.groups.finitely_presented.
FinitelyPresentedGroup
¶ A class that wraps GAP’s Finitely Presented Groups.
Warning
You should use
quotient()
to construct finitely presented groups as quotients of free groups.EXAMPLES:
sage: G.<a,b> = FreeGroup() sage: H = G / [a, b^3] sage: H Finitely presented group < a, b | a, b^3 > sage: H.gens() (a, b) sage: F.<a,b> = FreeGroup('a, b') sage: J = F / (F([1]), F([2, 2, 2])) sage: J is H True sage: G = FreeGroup(2) sage: H = G / (G([1, 1]), G([2, 2, 2])) sage: H.gens() (x0, x1) sage: H.gen(0) x0 sage: H.ngens() 2 sage: H.gap() <fp group on the generators [ x0, x1 ]> sage: type(_) <type 'sage.libs.gap.element.GapElement'>
-
class
sage.groups.finitely_presented.
FinitelyPresentedGroupElement
(parent, x, check=True)¶ Bases:
sage.groups.free_group.FreeGroupElement
A wrapper of GAP’s Finitely Presented Group elements.
The elements are created by passing the Tietze list that determines them.
EXAMPLES:
sage: G = FreeGroup('a, b') sage: H = G / [G([1]), G([2, 2, 2])] sage: H([1, 2, 1, -1]) a*b sage: H([1, 2, 1, -2]) a*b*a*b^-1 sage: x = H([1, 2, -1, -2]) sage: x a*b*a^-1*b^-1 sage: y = H([2, 2, 2, 1, -2, -2, -2]) sage: y b^3*a*b^-3 sage: x*y a*b*a^-1*b^2*a*b^-3 sage: x^(-1) b*a*b^-1*a^-1
-
Tietze
()¶ Return the Tietze list of the element.
The Tietze list of a word is a list of integers that represent the letters in the word. A positive integer \(i\) represents the letter corresponding to the \(i\)-th generator of the group. Negative integers represent the inverses of generators.
OUTPUT:
A tuple of integers.
EXAMPLES:
sage: G = FreeGroup('a, b') sage: H = G / (G([1]), G([2, 2, 2])) sage: H.inject_variables() Defining a, b sage: a.Tietze() (1,) sage: x = a^2*b^(-3)*a^(-2) sage: x.Tietze() (1, 1, -2, -2, -2, -1, -1)
-
-
class
sage.groups.finitely_presented.
GroupMorphismWithGensImages
¶ Bases:
sage.categories.morphism.SetMorphism
Class used for morphisms from finitely presented groups to other groups. It just adds the images of the generators at the end of the representation.
EXAMPLES:
sage: F = FreeGroup(3) sage: G = F / [F([1, 2, 3, 1, 2, 3]), F([1, 1, 1])] sage: H = AlternatingGroup(3) sage: HS = G.Hom(H) sage: from sage.groups.finitely_presented import GroupMorphismWithGensImages sage: GroupMorphismWithGensImages(HS, lambda a: H.one()) Generic morphism: From: Finitely presented group < x0, x1, x2 | (x0*x1*x2)^2, x0^3 > To: Alternating group of order 3!/2 as a permutation group Defn: x0 |--> () x1 |--> () x2 |--> ()
-
class
sage.groups.finitely_presented.
RewritingSystem
(G)¶ Bases:
object
A class that wraps GAP’s rewriting systems.
A rewriting system is a set of rules that allow to transform one word in the group to an equivalent one.
If the rewriting system is confluent, then the transformed word is a unique reduced form of the element of the group.
Warning
Note that the process of making a rewriting system confluent might not end.
INPUT:
G
– a group
REFERENCES:
EXAMPLES:
sage: F.<a,b> = FreeGroup() sage: G = F / [a*b/a/b] sage: k = G.rewriting_system() sage: k Rewriting system of Finitely presented group < a, b | a*b*a^-1*b^-1 > with rules: a*b*a^-1*b^-1 ---> 1 sage: k.reduce(a*b*a*b) (a*b)^2 sage: k.make_confluent() sage: k Rewriting system of Finitely presented group < a, b | a*b*a^-1*b^-1 > with rules: b^-1*a^-1 ---> a^-1*b^-1 b^-1*a ---> a*b^-1 b*a^-1 ---> a^-1*b b*a ---> a*b sage: k.reduce(a*b*a*b) a^2*b^2
Todo
- Include support for different orderings (currently only shortlex is used).
- Include the GAP package kbmag for more functionalities, including automatic structures and faster compiled functions.
AUTHORS:
- Miguel Angel Marco Buzunariz (2013-12-16)
-
finitely_presented_group
()¶ The finitely presented group where the rewriting system is defined.
EXAMPLES:
sage: F = FreeGroup(3) sage: G = F / [ [1,2,3], [-1,-2,-3], [1,1], [2,2] ] sage: k = G.rewriting_system() sage: k.make_confluent() sage: k Rewriting system of Finitely presented group < x0, x1, x2 | x0*x1*x2, x0^-1*x1^-1*x2^-1, x0^2, x1^2 > with rules: x0^-1 ---> x0 x1^-1 ---> x1 x2^-1 ---> x2 x0^2 ---> 1 x0*x1 ---> x2 x0*x2 ---> x1 x1*x0 ---> x2 x1^2 ---> 1 x1*x2 ---> x0 x2*x0 ---> x1 x2*x1 ---> x0 x2^2 ---> 1 sage: k.finitely_presented_group() Finitely presented group < x0, x1, x2 | x0*x1*x2, x0^-1*x1^-1*x2^-1, x0^2, x1^2 >
-
free_group
()¶ The free group after which the rewriting system is defined
EXAMPLES:
sage: F = FreeGroup(3) sage: G = F / [ [1,2,3], [-1,-2,-3] ] sage: k = G.rewriting_system() sage: k.free_group() Free Group on generators {x0, x1, x2}
-
gap
()¶ The gap representation of the rewriting system.
EXAMPLES:
sage: F.<a,b>=FreeGroup() sage: G=F/[a*a,b*b] sage: k=G.rewriting_system() sage: k.gap() Knuth Bendix Rewriting System for Monoid( [ a, A, b, B ] ) with rules [ [ a^2, <identity ...> ], [ a*A, <identity ...> ], [ A*a, <identity ...> ], [ b^2, <identity ...> ], [ b*B, <identity ...> ], [ B*b, <identity ...> ] ]
-
is_confluent
()¶ Return
True
if the system is confluent andFalse
otherwise.EXAMPLES:
sage: F = FreeGroup(3) sage: G = F / [F([1,2,1,2,1,3,-1]),F([2,2,2,1,1,2]),F([1,2,3])] sage: k = G.rewriting_system() sage: k.is_confluent() False sage: k Rewriting system of Finitely presented group < x0, x1, x2 | (x0*x1)^2*x0*x2*x0^-1, x1^3*x0^2*x1, x0*x1*x2 > with rules: x0*x1*x2 ---> 1 x1^3*x0^2*x1 ---> 1 (x0*x1)^2*x0*x2*x0^-1 ---> 1 sage: k.make_confluent() sage: k.is_confluent() True sage: k Rewriting system of Finitely presented group < x0, x1, x2 | (x0*x1)^2*x0*x2*x0^-1, x1^3*x0^2*x1, x0*x1*x2 > with rules: x0^-1 ---> x0 x1^-1 ---> x1 x0^2 ---> 1 x0*x1 ---> x2^-1 x0*x2^-1 ---> x1 x1*x0 ---> x2 x1^2 ---> 1 x1*x2^-1 ---> x0*x2 x1*x2 ---> x0 x2^-1*x0 ---> x0*x2 x2^-1*x1 ---> x0 x2^-2 ---> x2 x2*x0 ---> x1 x2*x1 ---> x0*x2 x2^2 ---> x2^-1
-
make_confluent
()¶ Applies Knuth-Bendix algorithm to try to transform the rewriting system into a confluent one.
Note that this method does not return any object, just changes the rewriting system internally.
Warning
This algorithm is not granted to finish. Although it may be useful in some occasions to run it, interrupt it manually after some time and use then the transformed rewriting system. Even if it is not confluent, it could be used to reduce some words.
ALGORITHM:
Uses GAP’s
MakeConfluent
.EXAMPLES:
sage: F.<a,b> = FreeGroup() sage: G = F / [a^2,b^3,(a*b/a)^3,b*a*b*a] sage: k = G.rewriting_system() sage: k Rewriting system of Finitely presented group < a, b | a^2, b^3, a*b^3*a^-1, (b*a)^2 > with rules: a^2 ---> 1 b^3 ---> 1 (b*a)^2 ---> 1 a*b^3*a^-1 ---> 1 sage: k.make_confluent() sage: k Rewriting system of Finitely presented group < a, b | a^2, b^3, a*b^3*a^-1, (b*a)^2 > with rules: a^-1 ---> a a^2 ---> 1 b^-1*a ---> a*b b^-2 ---> b b*a ---> a*b^-1 b^2 ---> b^-1
-
reduce
(element)¶ Applies the rules in the rewriting system to the element, to obtain a reduced form.
If the rewriting system is confluent, this reduced form is unique for all words representing the same element.
EXAMPLES:
sage: F.<a,b> = FreeGroup() sage: G = F/[a^2, b^3, (a*b/a)^3, b*a*b*a] sage: k = G.rewriting_system() sage: k.reduce(b^4) b sage: k.reduce(a*b*a) a*b*a
-
rules
()¶ Return the rules that form the rewriting system.
OUTPUT:
A dictionary containing the rules of the rewriting system. Each key is a word in the free group, and its corresponding value is the word to which it is reduced.
EXAMPLES:
sage: F.<a,b> = FreeGroup() sage: G = F / [a*a*a,b*b*a*a] sage: k = G.rewriting_system() sage: k Rewriting system of Finitely presented group < a, b | a^3, b^2*a^2 > with rules: a^3 ---> 1 b^2*a^2 ---> 1 sage: k.rules() {a^3: 1, b^2*a^2: 1} sage: k.make_confluent() sage: sorted(k.rules().items()) [(a^-2, a), (a^-1*b^-1, a*b), (a^-1*b, b^-1), (a^2, a^-1), (a*b^-1, b), (b^-1*a^-1, a*b), (b^-1*a, b), (b^-2, a^-1), (b*a^-1, b^-1), (b*a, a*b), (b^2, a)]
-
sage.groups.finitely_presented.
wrap_FpGroup
(libgap_fpgroup)¶ Wrap a GAP finitely presented group.
This function changes the comparison method of
libgap_free_group
to comparison by Pythonid
. If you want to put the LibGAP free group into a container(set, dict)
then you should understand the implications of_set_compare_by_id()
. To be safe, it is recommended that you just work with the resulting SageFinitelyPresentedGroup
.INPUT:
libgap_fpgroup
– a LibGAP finitely presented group
OUTPUT:
A Sage
FinitelyPresentedGroup
.EXAMPLES:
First construct a LibGAP finitely presented group:
sage: F = libgap.FreeGroup(['a', 'b']) sage: a_cubed = F.GeneratorsOfGroup()[0] ^ 3 sage: P = F / libgap([ a_cubed ]); P <fp group of size infinity on the generators [ a, b ]> sage: type(P) <type 'sage.libs.gap.element.GapElement'>
Now wrap it:
sage: from sage.groups.finitely_presented import wrap_FpGroup sage: wrap_FpGroup(P) Finitely presented group < a, b | a^3 >