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 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:

  • Miguel Angel Marco Buzunariz
class sage.groups.finitely_presented.FinitelyPresentedGroup(free_group, relations)

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'>
Element

alias of FinitelyPresentedGroupElement

abelian_invariants()

Return the abelian invariants of self.

The abelian invariants are given by a list of integers i_1 \dots i_j, such that the abelianization of the group is isomorphic to \mathbb{Z}/(i_1) \times \dots \times
\mathbb{Z}/(i_j).

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.
alexander_matrix()

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 group algebra-valued matrix. It 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]]

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]
as_permutation_group(limit=4096000)

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:

  • limit – integer (default: 4096000). The maximal number of cosets before the computation is aborted.

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.

cardinality(limit=4096000)

Compute the size of self.

INPUT:

  • limit – integer (default: 4096000). The maximal number of cosets before the computation is aborted.

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.

free_group()

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
order(limit=4096000)

Compute the size of self.

INPUT:

  • limit – integer (default: 4096000). The maximal number of cosets before the computation is aborted.

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.

relations()

Return the relations of the group.

OUTPUT:

The relations as a touple 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
simplification_isomorphism()

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.
simplified()

Return an isomorphic group with a (hopefully) simpler presentation.

OUTPUT:

A new finitely presented group. Use :meth: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 >
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)
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 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:

  • 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 >

Previous topic

Free Groups

Next topic

Braid groups

This Page