Free Groups

Free groups and finitely presented groups are implemented as a wrapper over the corresponding GAP objects.

A free group can be created by giving the number of generators, or their names. It is also possible to create indexed generators:

Sage

sage: G.<x,y,z> = FreeGroup();  G
Free Group on generators {x, y, z}
sage: FreeGroup(3)
Free Group on generators {x0, x1, x2}
sage: FreeGroup('a,b,c')
Free Group on generators {a, b, c}
sage: FreeGroup(3,'t')
Free Group on generators {t0, t1, t2}

Python

>>> from sage.all import *
>>> G = FreeGroup(names=('x', 'y', 'z',)); (x, y, z,) = G._first_ngens(3);  G
Free Group on generators {x, y, z}
>>> FreeGroup(Integer(3))
Free Group on generators {x0, x1, x2}
>>> FreeGroup('a,b,c')
Free Group on generators {a, b, c}
>>> FreeGroup(Integer(3),'t')
Free Group on generators {t0, t1, t2}

Sage Live

G.<x,y,z> = FreeGroup();  G
FreeGroup(3)
FreeGroup('a,b,c')
FreeGroup(3,'t')

The elements can be created by operating with the generators, or by passing a list with the indices of the letters to the group:

EXAMPLES:

Sage

sage: G.<a,b,c> = FreeGroup()
sage: a*b*c*a
a*b*c*a
sage: G([1,2,3,1])
a*b*c*a
sage: a * b / c * b^2
a*b*c^-1*b^2
sage: G([1,1,2,-1,-3,2])
a^2*b*a^-1*c^-1*b

Python

>>> from sage.all import *
>>> G = FreeGroup(names=('a', 'b', 'c',)); (a, b, c,) = G._first_ngens(3)
>>> a*b*c*a
a*b*c*a
>>> G([Integer(1),Integer(2),Integer(3),Integer(1)])
a*b*c*a
>>> a * b / c * b**Integer(2)
a*b*c^-1*b^2
>>> G([Integer(1),Integer(1),Integer(2),-Integer(1),-Integer(3),Integer(2)])
a^2*b*a^-1*c^-1*b

Sage Live

G.<a,b,c> = FreeGroup()
a*b*c*a
G([1,2,3,1])
a * b / c * b^2
G([1,1,2,-1,-3,2])

You can use call syntax to replace the generators with a set of arbitrary ring elements:

Sage

sage: g =  a * b / c * b^2
sage: g(1,2,3)
8/3
sage: M1 = identity_matrix(2)
sage: M2 = matrix([[1,1],[0,1]])
sage: M3 = matrix([[0,1],[1,0]])
sage: g([M1, M2, M3])
[1 3]
[1 2]

Python

>>> from sage.all import *
>>> g =  a * b / c * b**Integer(2)
>>> g(Integer(1),Integer(2),Integer(3))
8/3
>>> M1 = identity_matrix(Integer(2))
>>> M2 = matrix([[Integer(1),Integer(1)],[Integer(0),Integer(1)]])
>>> M3 = matrix([[Integer(0),Integer(1)],[Integer(1),Integer(0)]])
>>> g([M1, M2, M3])
[1 3]
[1 2]

Sage Live

g =  a * b / c * b^2
g(1,2,3)
M1 = identity_matrix(2)
M2 = matrix([[1,1],[0,1]])
M3 = matrix([[0,1],[1,0]])
g([M1, M2, M3])

AUTHORS:

• Miguel Angel Marco Buzunariz

• Volker Braun

sage.groups.free_group.FreeGroup(n=None, names='x', index_set=None, abelian=False, **kwds)

Construct a Free Group.

INPUT:

• n – integer (default: None); the number of generators (if not specified the names are counted)

• names – string or list/tuple/iterable of strings (default: 'x'); the generator names or name prefix

• index_set – (optional) an index set for the generators; if specified then the optional keyword abelian can be used

• abelian – boolean (default: False); whether to construct a free abelian group or a free group

Note

If you want to create a free group, it is currently preferential to use Groups().free(...) as that does not load GAP.

EXAMPLES:

Sage

sage: G.<a,b> = FreeGroup();  G
Free Group on generators {a, b}
sage: H = FreeGroup('a, b')
sage: G is H
True
sage: FreeGroup(0)
Free Group on generators {}

Python

>>> from sage.all import *
>>> G = FreeGroup(names=('a', 'b',)); (a, b,) = G._first_ngens(2);  G
Free Group on generators {a, b}
>>> H = FreeGroup('a, b')
>>> G is H
True
>>> FreeGroup(Integer(0))
Free Group on generators {}

Sage Live

G.<a,b> = FreeGroup();  G
H = FreeGroup('a, b')
G is H
FreeGroup(0)

The entry can be either a string with the names of the generators, or the number of generators and the prefix of the names to be given. The default prefix is 'x'

Sage

sage: FreeGroup(3)
Free Group on generators {x0, x1, x2}
sage: FreeGroup(3, 'g')
Free Group on generators {g0, g1, g2}
sage: FreeGroup()
Free Group on generators {x}

Python

>>> from sage.all import *
>>> FreeGroup(Integer(3))
Free Group on generators {x0, x1, x2}
>>> FreeGroup(Integer(3), 'g')
Free Group on generators {g0, g1, g2}
>>> FreeGroup()
Free Group on generators {x}

Sage Live

FreeGroup(3)
FreeGroup(3, 'g')
FreeGroup()

We give two examples using the index_set option:

Sage

sage: FreeGroup(index_set=ZZ)                                                   # needs sage.combinat
Free group indexed by Integer Ring
sage: FreeGroup(index_set=ZZ, abelian=True)                                     # needs sage.combinat
Free abelian group indexed by Integer Ring

Python

>>> from sage.all import *
>>> FreeGroup(index_set=ZZ)                                                   # needs sage.combinat
Free group indexed by Integer Ring
>>> FreeGroup(index_set=ZZ, abelian=True)                                     # needs sage.combinat
Free abelian group indexed by Integer Ring

Sage Live

FreeGroup(index_set=ZZ)                                                   # needs sage.combinat
FreeGroup(index_set=ZZ, abelian=True)                                     # needs sage.combinat

class sage.groups.free_group.FreeGroupElement(parent, x)

Bases: ElementLibGAP

A wrapper of GAP’s Free Group elements.

INPUT:

• x – something that determines the group element; either a GapElement or the Tietze list (see Tietze()) of the group element

• parent – the parent FreeGroup

EXAMPLES:

Sage

sage: G = FreeGroup('a, b')
sage: x = G([1, 2, -1, -2])
sage: x
a*b*a^-1*b^-1
sage: y = G([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: y*x
b^3*a*b^-3*a*b*a^-1*b^-1
sage: x^(-1)
b*a*b^-1*a^-1
sage: x == x*y*y^(-1)
True

Python

>>> from sage.all import *
>>> G = FreeGroup('a, b')
>>> x = G([Integer(1), Integer(2), -Integer(1), -Integer(2)])
>>> x
a*b*a^-1*b^-1
>>> y = G([Integer(2), Integer(2), Integer(2), Integer(1), -Integer(2), -Integer(2), -Integer(2)])
>>> y
b^3*a*b^-3
>>> x*y
a*b*a^-1*b^2*a*b^-3
>>> y*x
b^3*a*b^-3*a*b*a^-1*b^-1
>>> x**(-Integer(1))
b*a*b^-1*a^-1
>>> x == x*y*y**(-Integer(1))
True

Sage Live

G = FreeGroup('a, b')
x = G([1, 2, -1, -2])
x
y = G([2, 2, 2, 1, -2, -2, -2])
y
x*y
y*x
x^(-1)
x == x*y*y^(-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: tuple of integers

EXAMPLES:

Sage

sage: G.<a,b> = FreeGroup()
sage: a.Tietze()
(1,)
sage: x = a^2 * b^(-3) * a^(-2)
sage: x.Tietze()
(1, 1, -2, -2, -2, -1, -1)

Python

>>> from sage.all import *
>>> G = FreeGroup(names=('a', 'b',)); (a, b,) = G._first_ngens(2)
>>> a.Tietze()
(1,)
>>> x = a**Integer(2) * b**(-Integer(3)) * a**(-Integer(2))
>>> x.Tietze()
(1, 1, -2, -2, -2, -1, -1)

Sage Live

G.<a,b> = FreeGroup()
a.Tietze()
x = a^2 * b^(-3) * a^(-2)
x.Tietze()

fox_derivative(gen, im_gens=None, ring=None)

Return the Fox derivative of self with respect to a given generator gen of the free group.

Let \(F\) be a free group with free generators \(x_1, x_2, \ldots, x_n\). Let \(j \in \left\{ 1, 2, \ldots , n \right\}\). Let \(a_1, a_2, \ldots, a_n\) be \(n\) invertible elements of a ring \(A\). Let \(a : F \to A^\times\) be the (unique) homomorphism from \(F\) to the multiplicative group of invertible elements of \(A\) which sends each \(x_i\) to \(a_i\). Then, we can define a map \(\partial_j : F \to A\) by the requirements that

\[\partial_j (x_i) = \delta_{i, j} \qquad \qquad \text{ for all indices } i \text{ and } j\]

and

\[\partial_j (uv) = \partial_j(u) + a(u) \partial_j(v) \qquad \qquad \text{ for all } u, v \in F .\]

This map \(\partial_j\) is called the \(j\)-th Fox derivative on \(F\) induced by \((a_1, a_2, \ldots, a_n)\).

The most well-known case is when \(A\) is the group ring \(\ZZ [F]\) of \(F\) over \(\ZZ\), and when \(a_i = x_i \in A\). In this case, \(\partial_j\) is simply called the \(j\)-th Fox derivative on \(F\).

INPUT:

• gen – the generator with respect to which the derivative will be computed. If this is \(x_j\), then the method will return \(\partial_j\).

• im_gens – (optional) the images of the generators (given as a list or iterable). This is the list \((a_1, a_2, \ldots, a_n)\). If not provided, it defaults to \((x_1, x_2, \ldots, x_n)\) in the group ring \(\ZZ [F]\).

• ring – (optional) the ring in which the elements of the list \((a_1, a_2, \ldots, a_n)\) lie. If not provided, this ring is inferred from these elements.

OUTPUT:

The fox derivative of self with respect to gen (induced by im_gens). By default, it is an element of the group algebra with integer coefficients. If im_gens are provided, the result lives in the algebra where im_gens live.

EXAMPLES:

Sage

sage: G = FreeGroup(5)
sage: G.inject_variables()
Defining x0, x1, x2, x3, x4
sage: (~x0*x1*x0*x2*~x0).fox_derivative(x0)
-x0^-1 + x0^-1*x1 - x0^-1*x1*x0*x2*x0^-1
sage: (~x0*x1*x0*x2*~x0).fox_derivative(x1)
x0^-1
sage: (~x0*x1*x0*x2*~x0).fox_derivative(x2)
x0^-1*x1*x0
sage: (~x0*x1*x0*x2*~x0).fox_derivative(x3)
0

Python

>>> from sage.all import *
>>> G = FreeGroup(Integer(5))
>>> G.inject_variables()
Defining x0, x1, x2, x3, x4
>>> (~x0*x1*x0*x2*~x0).fox_derivative(x0)
-x0^-1 + x0^-1*x1 - x0^-1*x1*x0*x2*x0^-1
>>> (~x0*x1*x0*x2*~x0).fox_derivative(x1)
x0^-1
>>> (~x0*x1*x0*x2*~x0).fox_derivative(x2)
x0^-1*x1*x0
>>> (~x0*x1*x0*x2*~x0).fox_derivative(x3)
0

Sage Live

G = FreeGroup(5)
G.inject_variables()
(~x0*x1*x0*x2*~x0).fox_derivative(x0)
(~x0*x1*x0*x2*~x0).fox_derivative(x1)
(~x0*x1*x0*x2*~x0).fox_derivative(x2)
(~x0*x1*x0*x2*~x0).fox_derivative(x3)

If im_gens is given, the images of the generators are mapped to them:

Sage

sage: F = FreeGroup(3)
sage: a = F([2,1,3,-1,2])
sage: a.fox_derivative(F([1]))
x1 - x1*x0*x2*x0^-1
sage: R.<t> = LaurentPolynomialRing(ZZ)
sage: a.fox_derivative(F([1]),[t,t,t])
t - t^2
sage: S.<t1,t2,t3> = LaurentPolynomialRing(ZZ)
sage: a.fox_derivative(F([1]),[t1,t2,t3])
-t2*t3 + t2
sage: R.<x,y,z> = QQ[]
sage: a.fox_derivative(F([1]),[x,y,z])
-y*z + y
sage: a.inverse().fox_derivative(F([1]),[x,y,z])
(z - 1)/(y*z)

Python

>>> from sage.all import *
>>> F = FreeGroup(Integer(3))
>>> a = F([Integer(2),Integer(1),Integer(3),-Integer(1),Integer(2)])
>>> a.fox_derivative(F([Integer(1)]))
x1 - x1*x0*x2*x0^-1
>>> R = LaurentPolynomialRing(ZZ, names=('t',)); (t,) = R._first_ngens(1)
>>> a.fox_derivative(F([Integer(1)]),[t,t,t])
t - t^2
>>> S = LaurentPolynomialRing(ZZ, names=('t1', 't2', 't3',)); (t1, t2, t3,) = S._first_ngens(3)
>>> a.fox_derivative(F([Integer(1)]),[t1,t2,t3])
-t2*t3 + t2
>>> R = QQ['x, y, z']; (x, y, z,) = R._first_ngens(3)
>>> a.fox_derivative(F([Integer(1)]),[x,y,z])
-y*z + y
>>> a.inverse().fox_derivative(F([Integer(1)]),[x,y,z])
(z - 1)/(y*z)

Sage Live

F = FreeGroup(3)
a = F([2,1,3,-1,2])
a.fox_derivative(F([1]))
R.<t> = LaurentPolynomialRing(ZZ)
a.fox_derivative(F([1]),[t,t,t])
S.<t1,t2,t3> = LaurentPolynomialRing(ZZ)
a.fox_derivative(F([1]),[t1,t2,t3])
R.<x,y,z> = QQ[]
a.fox_derivative(F([1]),[x,y,z])
a.inverse().fox_derivative(F([1]),[x,y,z])

The optional parameter ring determines the ring \(A\):

Sage

sage: u = a.fox_derivative(F([1]), [1,2,3], ring=QQ)
sage: u
-4
sage: parent(u)
Rational Field
sage: u = a.fox_derivative(F([1]), [1,2,3], ring=R)
sage: u
-4
sage: parent(u)
Multivariate Polynomial Ring in x, y, z over Rational Field

Python

>>> from sage.all import *
>>> u = a.fox_derivative(F([Integer(1)]), [Integer(1),Integer(2),Integer(3)], ring=QQ)
>>> u
-4
>>> parent(u)
Rational Field
>>> u = a.fox_derivative(F([Integer(1)]), [Integer(1),Integer(2),Integer(3)], ring=R)
>>> u
-4
>>> parent(u)
Multivariate Polynomial Ring in x, y, z over Rational Field

Sage Live

u = a.fox_derivative(F([1]), [1,2,3], ring=QQ)
u
parent(u)
u = a.fox_derivative(F([1]), [1,2,3], ring=R)
u
parent(u)

syllables()

Return the syllables of the word.

Consider a free group element \(g = x_1^{n_1} x_2^{n_2} \cdots x_k^{n_k}\). The uniquely-determined subwords \(x_i^{e_i}\) consisting only of powers of a single generator are called the syllables of \(g\).

OUTPUT:

The tuple of syllables. Each syllable is given as a pair \((x_i, e_i)\) consisting of a generator and a nonzero integer.

EXAMPLES:

Sage

sage: G.<a,b> = FreeGroup()
sage: w = a^2 * b^-1 * a^3
sage: w.syllables()
((a, 2), (b, -1), (a, 3))

Python

>>> from sage.all import *
>>> G = FreeGroup(names=('a', 'b',)); (a, b,) = G._first_ngens(2)
>>> w = a**Integer(2) * b**-Integer(1) * a**Integer(3)
>>> w.syllables()
((a, 2), (b, -1), (a, 3))

Sage Live

G.<a,b> = FreeGroup()
w = a^2 * b^-1 * a^3
w.syllables()

class sage.groups.free_group.FreeGroup_class(generator_names, gap_group=None)

Bases: CachedRepresentation, Group, ParentLibGAP

A class that wraps GAP’s FreeGroup.

See FreeGroup() for details.

Element

alias of FreeGroupElement

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

\[\ZZ / (i_1) \times \dots \times \ZZ / (i_j)\]

EXAMPLES:

Sage

sage: F.<a,b> = FreeGroup()
sage: F.abelian_invariants()
(0, 0)

Python

>>> from sage.all import *
>>> F = FreeGroup(names=('a', 'b',)); (a, b,) = F._first_ngens(2)
>>> F.abelian_invariants()
(0, 0)

Sage Live

F.<a,b> = FreeGroup()
F.abelian_invariants()

quotient(relations, **kwds)

Return the quotient of self by the normal subgroup generated by the given elements.

This quotient is a finitely presented groups with the same generators as self, and relations given by the elements of relations.

INPUT:

• relations – list/tuple/iterable with the elements of the free group

• further named arguments, that are passed to the constructor of a finitely presented group

OUTPUT:

A finitely presented group, with generators corresponding to the generators of the free group, and relations corresponding to the elements in relations.

EXAMPLES:

Sage

sage: F.<a,b> = FreeGroup()
sage: F.quotient([a*b^2*a, b^3])
Finitely presented group < a, b | a*b^2*a, b^3 >

Python

>>> from sage.all import *
>>> F = FreeGroup(names=('a', 'b',)); (a, b,) = F._first_ngens(2)
>>> F.quotient([a*b**Integer(2)*a, b**Integer(3)])
Finitely presented group < a, b | a*b^2*a, b^3 >

Sage Live

F.<a,b> = FreeGroup()
F.quotient([a*b^2*a, b^3])

Division is shorthand for quotient()

Sage

sage: F /  [a*b^2*a, b^3]
Finitely presented group < a, b | a*b^2*a, b^3 >

Python

>>> from sage.all import *
>>> F /  [a*b**Integer(2)*a, b**Integer(3)]
Finitely presented group < a, b | a*b^2*a, b^3 >

Sage Live

F /  [a*b^2*a, b^3]

Relations are converted to the free group, even if they are not elements of it (if possible)

Sage

sage: F1.<a,b,c,d> = FreeGroup()
sage: F2.<a,b> = FreeGroup()
sage: r = a*b/a
sage: r.parent()
Free Group on generators {a, b}
sage: F1/[r]
Finitely presented group < a, b, c, d | a*b*a^-1 >

Python

>>> from sage.all import *
>>> F1 = FreeGroup(names=('a', 'b', 'c', 'd',)); (a, b, c, d,) = F1._first_ngens(4)
>>> F2 = FreeGroup(names=('a', 'b',)); (a, b,) = F2._first_ngens(2)
>>> r = a*b/a
>>> r.parent()
Free Group on generators {a, b}
>>> F1/[r]
Finitely presented group < a, b, c, d | a*b*a^-1 >

Sage Live

F1.<a,b,c,d> = FreeGroup()
F2.<a,b> = FreeGroup()
r = a*b/a
r.parent()
F1/[r]

rank()

Return the number of generators of self.

Alias for ngens().

OUTPUT: integer

EXAMPLES:

Sage

sage: G = FreeGroup('a, b');  G
Free Group on generators {a, b}
sage: G.rank()
2
sage: H = FreeGroup(3, 'x')
sage: H
Free Group on generators {x0, x1, x2}
sage: H.rank()
3

Python

>>> from sage.all import *
>>> G = FreeGroup('a, b');  G
Free Group on generators {a, b}
>>> G.rank()
2
>>> H = FreeGroup(Integer(3), 'x')
>>> H
Free Group on generators {x0, x1, x2}
>>> H.rank()
3

Sage Live

G = FreeGroup('a, b');  G
G.rank()
H = FreeGroup(3, 'x')
H
H.rank()

sage.groups.free_group.is_FreeGroup(x)

Test whether x is a FreeGroup_class.

INPUT:

• x – anything

OUTPUT: boolean

EXAMPLES:

Sage

sage: from sage.groups.free_group import is_FreeGroup
sage: is_FreeGroup('a string')                                                  # needs sage.combinat
False
sage: is_FreeGroup(FreeGroup(0))
True
sage: is_FreeGroup(FreeGroup(index_set=ZZ))                                     # needs sage.combinat
True

Python

>>> from sage.all import *
>>> from sage.groups.free_group import is_FreeGroup
>>> is_FreeGroup('a string')                                                  # needs sage.combinat
False
>>> is_FreeGroup(FreeGroup(Integer(0)))
True
>>> is_FreeGroup(FreeGroup(index_set=ZZ))                                     # needs sage.combinat
True

Sage Live

from sage.groups.free_group import is_FreeGroup
is_FreeGroup('a string')                                                  # needs sage.combinat
is_FreeGroup(FreeGroup(0))
is_FreeGroup(FreeGroup(index_set=ZZ))                                     # needs sage.combinat

Make live