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 mutiplying 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 unil the available memory is exhausted.
REFERENCES:
AUTHOR:
Bases: sage.groups.libgap_mixin.GroupMixinLibGAP, sage.structure.unique_representation.UniqueRepresentation, sage.groups.group.Group, sage.groups.libgap_wrapper.ParentLibGAP
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'>
alias of FinitelyPresentedGroupElement
Return the abelian invariants of self.
The abelian invariants are given by a list of integers
, such that the abelianization of the group is
isomorphic to
.
EXAMPLES:
sage: G = FreeGroup(4, 'g')
sage: G.inject_variables()
Defining g0, g1, g2, g3
sage: H = G.quotient([g1^2, g2*g1*g2^(-1)*g1^(-1), g1*g3^(-2), g0^4])
sage: H.abelian_invariants()
(0, 4, 4)
ALGORITHM:
Uses GAP.
Return the Alexander matrix of the group.
This matrix is given by the fox derivatives of the relations with respect to the generators.
OUTPUT:
A matrix with coefficients in the group algebra. If im_gens is given, the coefficients will live in the same algebra as the given values. The result depends on the (fixed) choice of presentation.
EXAMPLES:
sage: G.<a,b,c> = FreeGroup()
sage: H = G.quotient([a*b/a/b, a*c/a/c, c*b/c/b])
sage: H.alexander_matrix()
[ B[1] - B[a*b*a^-1] B[a] - B[a*b*a^-1*b^-1] 0]
[ B[1] - B[a*c*a^-1] 0 B[a] - B[a*c*a^-1*c^-1]]
[ 0 B[c] - B[c*b*c^-1*b^-1] B[1] - B[c*b*c^-1]]
If we introduce the images of the generators, we obtain the result in the corresponding algebra.
sage: G.<a,b,c,d,e> = FreeGroup()
sage: H = G.quotient([a*b/a/b, a*c/a/c, a*d/a/d, b*c*d/(c*d*b), b*c*d/(d*b*c)])
sage: H.alexander_matrix()
[ B[1] - B[a*b*a^-1] B[a] - B[a*b*a^-1*b^-1] 0 0 0]
[ B[1] - B[a*c*a^-1] 0 B[a] - B[a*c*a^-1*c^-1] 0 0]
[ B[1] - B[a*d*a^-1] 0 0 B[a] - B[a*d*a^-1*d^-1] 0]
[ 0 B[1] - B[b*c*d*b^-1] B[b] - B[b*c*d*b^-1*d^-1*c^-1] B[b*c] - B[b*c*d*b^-1*d^-1] 0]
[ 0 B[1] - B[b*c*d*c^-1*b^-1] B[b] - B[b*c*d*c^-1] B[b*c] - B[b*c*d*c^-1*b^-1*d^-1] 0]
sage: R.<t1,t2,t3,t4> = LaurentPolynomialRing(ZZ)
sage: H.alexander_matrix([t1,t2,t3,t4])
[ -t2 + 1 t1 - 1 0 0 0]
[ -t3 + 1 0 t1 - 1 0 0]
[ -t4 + 1 0 0 t1 - 1 0]
[ 0 -t3*t4 + 1 t2 - 1 t2*t3 - t3 0]
[ 0 -t4 + 1 -t2*t4 + t2 t2*t3 - 1 0]
Return an isomorphic permutation group.
The generators of the resulting group correspond to the images by the isomorphism of the generators of the given group.
INPUT:
OUTPUT:
A Sage PermutationGroup(). If the number of cosets exceeds the given limit, a ValueError is returned.
EXAMPLES:
sage: G.<a,b> = FreeGroup()
sage: H = G / (a^2, b^3, a*b*~a*~b)
sage: H.as_permutation_group()
Permutation Group with generators [(1,2)(3,5)(4,6), (1,3,4)(2,5,6)]
sage: G.<a,b> = FreeGroup()
sage: H = G / [a^3*b]
sage: H.as_permutation_group(limit=1000)
Traceback (most recent call last):
...
ValueError: Coset enumeration exceeded limit, is the group finite?
ALGORITHM:
Uses GAP’s coset enumeration on the trivial subgroup.
Warning
This is in general not a decidable problem (in fact, it is not even posible to check if the group is finite or not). If the group is infinite, or too big, you should be prepared for a long computation that consumes all the memory without finishing if you do not set a sensible limit.
Compute the cardinality of self.
INPUT:
OUTPUT:
Integer or Infinity. The number of elements in the group.
EXAMPLES:
sage: G.<a,b> = FreeGroup('a, b')
sage: H = G / (a^2, b^3, a*b*~a*~b)
sage: H.cardinality()
6
sage: F.<a,b,c> = FreeGroup()
sage: J = F / (F([1]), F([2, 2, 2]))
sage: J.cardinality()
+Infinity
ALGORITHM:
Uses GAP.
Warning
This is in general not a decidable problem, so it is not guaranteed to give an answer. If the group is infinite, or too big, you should be prepared for a long computation that consumes all the memory without finishing if you do not set a sensible limit.
Return the direct product of self with finitely presented group H.
Calls GAP function DirectProduct, which returns the direct product of a list of groups of any representation.
From [JohnsonPG90] (pg 45, proposition 4): If ,
are groups
presented by
and
respectively, then their direct product has the presentation
where
denotes the
set of commutators
.
INPUT:
OUTPUT:
The direct product of self with H as a finitely presented group.
EXAMPLES:
sage: G = FreeGroup()
sage: C12 = ( G / [G([1,1,1,1])] ).direct_product( G / [G([1,1,1])]); C12
Finitely presented group < a, b | a^4, b^3, a^-1*b^-1*a*b >
sage: C12.order(), C12.as_permutation_group().is_cyclic()
(12, True)
sage: klein = ( G / [G([1,1])] ).direct_product( G / [G([1,1])]); klein
Finitely presented group < a, b | a^2, b^2, a^-1*b^-1*a*b >
sage: klein.order(), klein.as_permutation_group().is_cyclic()
(4, False)
We can keep the variable names from self and H to examine how new relations are formed:
sage: F = FreeGroup("a"); G = FreeGroup("g")
sage: X = G / [G.0^12]; A = F / [F.0^6]
sage: X.direct_product(A, new_names=False)
Finitely presented group < g, a | g^12, a^6, g^-1*a^-1*g*a >
sage: A.direct_product(X, new_names=False)
Finitely presented group < a, g | a^6, g^12, a^-1*g^-1*a*g >
Or we can attempt to reduce the output group presentation:
sage: F = FreeGroup("a"); G = FreeGroup("g")
sage: X = G / [G.0]; A = F / [F.0]
sage: X.direct_product(A, new_names=True)
Finitely presented group < a, b | a, b, a^-1*b^-1*a*b >
sage: X.direct_product(A, reduced=True, new_names=True)
Finitely presented group < | >
But we cannot do both:
sage: K = FreeGroup(['a','b'])
sage: D = K / [K.0^5, K.1^8]
sage: D.direct_product(D, reduced=True, new_names=False)
Traceback (most recent call last):
...
ValueError: cannot reduce output and keep old variable names
TESTS:
sage: G = FreeGroup()
sage: Dp = (G / [G([1,1])]).direct_product( G / [G([1,1,1,1,1,1])] )
sage: Dp.as_permutation_group().is_isomorphic(PermutationGroup(['(1,2)','(3,4,5,6,7,8)']))
True
sage: C7 = G / [G.0**7]; C6 = G / [G.0**6]
sage: C14 = G / [G.0**14]; C3 = G / [G.0**3]
sage: C7.direct_product(C6).is_isomorphic(C14.direct_product(C3))
True
sage: F = FreeGroup(2); D = F / [F([1,1,1,1,1]),F([2,2]),F([1,2])**2]
sage: D.direct_product(D).as_permutation_group().is_isomorphic(
....: direct_product_permgroups([DihedralGroup(5),DihedralGroup(5)]))
True
AUTHORS:
REFERENCES:
[JohnsonPG90] | D.L. Johnson. Presentations of Groups. Cambridge University Press. (1990). |
Return the free group (without relations).
OUTPUT:
A FreeGroup().
EXAMPLES:
sage: G.<a,b,c> = FreeGroup()
sage: H = G / (a^2, b^3, a*b*~a*~b)
sage: H.free_group()
Free Group on generators {a, b, c}
sage: H.free_group() is G
True
Compute the cardinality of self.
INPUT:
OUTPUT:
Integer or Infinity. The number of elements in the group.
EXAMPLES:
sage: G.<a,b> = FreeGroup('a, b')
sage: H = G / (a^2, b^3, a*b*~a*~b)
sage: H.cardinality()
6
sage: F.<a,b,c> = FreeGroup()
sage: J = F / (F([1]), F([2, 2, 2]))
sage: J.cardinality()
+Infinity
ALGORITHM:
Uses GAP.
Warning
This is in general not a decidable problem, so it is not guaranteed to give an answer. If the group is infinite, or too big, you should be prepared for a long computation that consumes all the memory without finishing if you do not set a sensible limit.
Return the relations of the group.
OUTPUT:
The relations as a tuple of elements of free_group().
EXAMPLES:
sage: F = FreeGroup(5, 'x')
sage: F.inject_variables()
Defining x0, x1, x2, x3, x4
sage: G = F.quotient([x0*x2, x3*x1*x3, x2*x1*x2])
sage: G.relations()
(x0*x2, x3*x1*x3, x2*x1*x2)
sage: all(rel in F for rel in G.relations())
True
Return the rewriting system corresponding to the finitely presented group. This rewriting system can be used to reduce words with respect to the relations.
If the rewriting system is transformed into a confluent one, the reduction process will give as a result the (unique) reduced form of an 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
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: G([1,1,2,2,2])
a^2*b^3
sage: k.reduce(G([1,1,2,2,2]))
1
sage: k.reduce(G([2,2,1]))
b^2*a
sage: k.make_confluent()
sage: k.reduce(G([2,2,1]))
a*b
The semidirect product of self with H via hom.
If there exists a homomorphism from a group
to the
automorphism group of a group
, then we can define the semidirect
product of
with
via
as the cartesian product of
and
with the operation
INPUT:
OUTPUT:
The semidirect product of self with H via hom as a finitely presented group. See PermutationGroup_generic.semidirect_product for a more in depth explanation of a semidirect product.
AUTHORS:
EXAMPLES:
Group of order 12 as two isomorphic semidirect products:
sage: D4 = groups.presentation.Dihedral(4)
sage: C3 = groups.presentation.Cyclic(3)
sage: alpha1 = ([C3.gen(0)],[C3.gen(0)])
sage: alpha2 = ([C3.gen(0)],[C3([1,1])])
sage: S1 = D4.semidirect_product(C3, ([D4.gen(1), D4.gen(0)],[alpha1,alpha2]))
sage: C2 = groups.presentation.Cyclic(2)
sage: Q = groups.presentation.DiCyclic(3)
sage: a = Q([1]); b = Q([-2])
sage: alpha = (Q.gens(), [a,b])
sage: S2 = C2.semidirect_product(Q, ([C2.0],[alpha]))
sage: S1.is_isomorphic(S2)
True
Dihedral groups can be constructed as semidirect products of cyclic groups:
sage: C2 = groups.presentation.Cyclic(2)
sage: C8 = groups.presentation.Cyclic(8)
sage: hom = (C2.gens(), [ ([C8([1])], [C8([-1])]) ])
sage: D = C2.semidirect_product(C8, hom)
sage: D.as_permutation_group().is_isomorphic(DihedralGroup(8))
True
You can attempt to reduce the presentation of the output group:
sage: D = C2.semidirect_product(C8, hom); D
Finitely presented group < a, b, c, d |
a^2, b^-1*a^-1*b*a*d^-1*c^-1, c^-1*a^-1*c*a*d^-1, d^-1*a^-1*d*a,
b^2*c^-1, c^-1*b^-1*c*b, d^-1*b^-1*d*b, c^2*d^-1, d^-1*c^-1*d*c, d^2 >
sage: D = C2.semidirect_product(C8, hom, reduced=True); D
Finitely presented group < a, b | a^2, (a*b)^2, b^8 >
sage: C3 = groups.presentation.Cyclic(3)
sage: C4 = groups.presentation.Cyclic(4)
sage: hom = (C3.gens(), [(C4.gens(), C4.gens())])
sage: C3.semidirect_product(C4, hom)
Finitely presented group < a, b, c |
a^3, b^-1*a^-1*b*a, c^-1*a^-1*c*a, b^2*c^-1, c^-1*b^-1*c*b, c^2 >
sage: D = C3.semidirect_product(C4, hom, reduced=True); D
Finitely presented group < a, b | a^3, b^4, b^-1*a^-1*b*a >
sage: D.as_permutation_group().is_cyclic()
True
You can turn off the checks for the validity of the input morphisms. This check is expensive but behavior is unpredictable if inputs are invalid and are not caught by these tests:
sage: C5 = groups.presentation.Cyclic(5)
sage: C12 = groups.presentation.Cyclic(12)
sage: hom = (C5.gens(), [(C12.gens(), C12.gens())])
sage: sp = C5.semidirect_product(C12, hom, check=False); sp
Finitely presented group < a, b, c, d |
a^5, b^-1*a^-1*b*a, c^-1*a^-1*c*a, d^-1*a^-1*d*a, b^2*d^-1,
c^-1*b^-1*c*b, d^-1*b^-1*d*b, c^3, d^-1*c^-1*d*c, d^2 >
sage: sp.as_permutation_group().is_cyclic(), sp.order()
(True, 60)
TESTS:
The following was fixed in Gap-4.7.2:
sage: C5.semidirect_product(C12, hom) == sp
True
A more complicated semidirect product:
sage: C = groups.presentation.Cyclic(7)
sage: D = groups.presentation.Dihedral(5)
sage: id1 = ([C.0], [(D.gens(),D.gens())])
sage: Se1 = C.semidirect_product(D, id1)
sage: id2 = (D.gens(), [(C.gens(),C.gens()),(C.gens(),C.gens())])
sage: Se2 = D.semidirect_product(C ,id2)
sage: Dp1 = C.direct_product(D);
sage: Dp1.is_isomorphic(Se1), Dp1.is_isomorphic(Se2)
(True, True)
Most checks for validity of input are left to GAP to handle:
sage: bad_aut = ([C.0], [(D.gens(),[D.0, D.0])])
sage: C.semidirect_product(D, bad_aut)
Traceback (most recent call last):
...
ValueError: images of input homomorphism must be automorphisms
sage: bad_hom = ([D.0, D.1], [(C.gens(),C.gens())])
sage: D.semidirect_product(C, bad_hom)
Traceback (most recent call last):
...
ValueError: libGAP: Error, <gens> and <imgs> must be lists of same length
Return an isomorphism from self to a finitely presented group with a (hopefully) simpler presentation.
EXAMPLES:
sage: G.<a,b,c> = FreeGroup()
sage: H = G / [a*b*c, a*b^2, c*b/c^2]
sage: I = H.simplification_isomorphism()
sage: I
Generic morphism:
From: Finitely presented group < a, b, c | a*b*c, a*b^2, c*b*c^-2 >
To: Finitely presented group < b | >
sage: I(a)
b^-2
sage: I(b)
b
sage: I(c)
b
TESTS:
sage: F = FreeGroup(1)
sage: G = F.quotient([F.0])
sage: G.simplification_isomorphism()
Generic morphism:
From: Finitely presented group < x | x >
To: Finitely presented group < | >
ALGORITM:
Uses GAP.
Return an isomorphic group with a (hopefully) simpler presentation.
OUTPUT:
A new finitely presented group. Use simplification_isomorphism() if you want to know the isomorphism.
EXAMPLES:
sage: G.<x,y> = FreeGroup()
sage: H = G / [x ^5, y ^4, y*x*y^3*x ^3]
sage: H
Finitely presented group < x, y | x^5, y^4, y*x*y^3*x^3 >
sage: H.simplified()
Finitely presented group < x, y | y^4, y*x*y^-1*x^-2, x^5 >
A more complicate example:
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: H = G.quotient(rels); H
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: H.simplified()
Finitely presented group < e0 | e0^2 >
Return a string that tries to describe the structure of G.
This methods wraps GAP’s StructureDescription method.
Requires the optional database_gap package.
For full details, including the form of the returned string and the algorithm to build it, see GAP’s documentation.
INPUT:
OUTPUT:
Warning
From GAP’s documentation: The string returned by StructureDescription is not an isomorphism invariant: non-isomorphic groups can have the same string value, and two isomorphic groups in different representations can produce different strings.
EXAMPLES:
sage: G = CyclicPermutationGroup(6)
sage: G.structure_description() # optional - database_gap
'C6'
sage: G.structure_description(latex=True) # optional - database_gap
'C_{6}'
sage: G2 = G.direct_product(G, maps=False)
sage: LatexExpr(G2.structure_description(latex=True)) # optional - database_gap
C_{6} \times C_{6}
This method is mainly intended for small groups or groups with few normal subgroups. Even then there are some surprises:
sage: D3 = DihedralGroup(3)
sage: D3.structure_description() # optional - database_gap
'S3'
We use the Sage notation for the degree of dihedral groups:
sage: D4 = DihedralGroup(4)
sage: D4.structure_description() # optional - database_gap
'D4'
Works for finitely presented groups (trac ticket #17573):
sage: F.<x, y> = FreeGroup()
sage: G=F / [x^2*y^-1, x^3*y^2, x*y*x^-1*y^-1]
sage: G.structure_description() # optional - database_gap
'C7'
And matrix groups (trac ticket #17573):
sage: groups.matrix.GL(4,2).structure_description() # optional - database_gap
'A8'
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
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 represents
the letter corresponding to the
-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)
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 transformated 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:
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
AUTHORS:
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 >
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}
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 ...> ] ]
Return True if the system is confluent and False 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
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 sytem internally.
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
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
Return the rules that form the rewritig 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)]
Wrap a GAP finitely presented group.
This function changes the comparison method of libgap_free_group to comparison by Python id. 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 Sage FinitelyPresentedGroup.
INPUT:
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 >