Finitely presented groups

Introduction

A finitely presented group is a group generated by a finite set of generators subject to a finite set of relations that these generators satisfy.

A finitely presented group arises as a quotient $G$ of a free group $F$ by the normal subgroup of $F$ that is defined as the normal closure of a vector of elements in $F$; these elements are called the defining relators of $G$, see relators.

Finitely presented groups in Oscar have the type FPGroup, their elements have the type FPGroupElem.

Basic Creation

In order to create a finitely presented group, one first creates a free group (see free_group). This group is already a finitely presented group, it has an empty vector of defining relators.

julia> F = free_group(2)
Free group of rank 2

julia> gens(F)
2-element Vector{FPGroupElem}:
 f1
 f2

julia> f1, f2 = gens(F);

(See @free_group for ways to automatically assign variables corresponding to the generators of a free group.)

If one wants a finitely presented group with nontrivial defining relators then one chooses these defining relators, and then calls quo(G::T, elements::Vector{S}) where T <: GAPGroup where S <: GAPGroupElem.

julia> rels = [f1^2, f2^3, f1*f2*f1*f2^2]
3-element Vector{FPGroupElem}:
 f1^2
 f2^3
 (f1*f2)^2*f2

julia> G, epi = quo(F, rels)
(Finitely presented group, Hom: F -> G)

julia> gens(G)
2-element Vector{FPGroupElem}:
 f1
 f2

julia> order(G)
6

Note that the generators of the free group F and its quotient group G (and the way how they are printed) correspond to each other, but one cannot compare or multiply an element of F with an element of G; use the epimorphism returned by quo to map elements from F to G.

julia> map(epi, gens(F)) == gens(G)
true

Subgroups of finitely presented groups in Oscar have the type SubFPGroup, their elements have the type SubFPGroupElem. We distinguish between full finitely presented groups and their subgroups because different methods are needed for them, and because functions such as relators(G::FPGroup) make sense only for full finitely presented groups.

julia> S, emb = sylow_subgroup(G, 2)
(Sub-finitely presented group of order 2, Hom: S -> G)

julia> gens(S)
1-element Vector{SubFPGroupElem}:
 f1

Note that although finitely presented groups arise naturally in many situations, it is very often computationally much more efficient to work with groups in other representations (even the regular permutation representation).

julia> iso = isomorphism(PermGroup, G)
Group homomorphism
  from finitely presented group of order 6
  to permutation group of degree 5 and order 6

Functions for elements of (subgroups of) finitely presented groups

letters — Method

letters(g::Union{FPGroupElem, SubFPGroupElem})

Return the letters of g as a list of integers, each entry corresponding to a group generator. Inverses of the generators are represented by negative numbers.

Examples

julia> F = @free_group(:F1, :F2);

julia> letters(F1^5*F2^-3)
8-element Vector{Int64}:
  1
  1
  1
  1
  1
 -2
 -2
 -2

julia> letters(one(F))
Int64[]

julia> G, epi = quo(F, [F1^10, F2^10]);

julia> letters(epi(F1^5*F2^-3))
8-element Vector{Int64}:
  1
  1
  1
  1
  1
 -2
 -2
 -2

source

syllables — Method

syllables(g::Union{FPGroupElem, SubFPGroupElem})

Return the syllables of g as a list of pairs gen => exp where gen is the index of a generator and exp is an exponent.

Examples

julia> F = @free_group(:F1, :F2);

julia> syllables(F1^5*F2^-3)
2-element Vector{Pair{Int64, ZZRingElem}}:
 1 => 5
 2 => -3

julia> syllables(one(F))
Pair{Int64, ZZRingElem}[]

julia> G, epi = quo(F, [F1^10, F2^10]);

julia> syllables(epi(F1^5*F2^-3))
2-element Vector{Pair{Int64, ZZRingElem}}:
 1 => 5
 2 => -3

source

length — Method

length(g::Union{FPGroupElem, SubFPGroupElem})

Return the length of g as a word in terms of the generators of its parent or of the full group of its parent if g is an element of a free group, otherwise an exception is thrown.

Examples

julia> F = @free_group(:F1, :F2);

julia> length(F1*F2^-2)
3

julia> length(one(F))
0

julia> length(one(quo(F, [F1])[1]))
ERROR: ArgumentError: the element does not lie in a free group
[...]

source

map_word — Method

map_word(g::Union{FPGroupElem, SubFPGroupElem}, genimgs::Vector; genimgs_inv::Vector = Vector(undef, length(genimgs)), init = nothing)
map_word(v::Vector{Union{Int, Pair{Int, Int}}}, genimgs::Vector; genimgs_inv::Vector = Vector(undef, length(genimgs)), init = nothing)

If init is nothing, then return the product $R_1 R_2 \cdots R_n$ that is described by g or v, respectively. Otherwise return the product $xR_1 R_2 \cdots R_n$ where $x =$ init.

If g is an element of a free group $G$, say, then the rank of $G$ must be equal to the length of genimgs, g is a product of the form $g_{i_1}^{e_1} g_{i_2}^{e_2} \cdots g_{i_n}^{e_n}$ where $g_i$ is the $i$-th generator of $G$ and the $e_i$ are nonzero integers, and $R_j =$ genimgs[$i_j$]$^{e_j}$.

If g is an element of (a subgroup of) a finitely presented group then the result is defined as map_word applied to a representing element of the underlying free group of full_group(parent(g)). In particular, genimgs are interpreted as the images of the generators of this free group, not of gens(parent(g)).

If the first argument is a vector v of integers $k_i$ or pairs k_i => e_i, respectively, then the absolute values of the $k_i$ must be at most the length of genimgs, and $R_j =$ genimgs[$|k_i|$]$^{\epsilon_i}$ where $\epsilon_i$ is the sign of $k_i$ (times $e_i$).

If a vector genimgs_inv is given then its assigned entries are expected to be the inverses of the corresponding entries in genimgs, and the function will use (and set) these entries in order to avoid calling inv (more than once) for entries of genimgs.

The behaviour if v has length zero (or g == one(g)) is as follows: If init is different from nothing, then init is returned. Otherwise one(genimgs[1]) is returned unless genimgs is empty. If init == nothing and genimgs is empty, an error occurs. Thus the intended value for the empty word must be specified as init whenever it is possible that the elements in genimgs do not support one.

Examples

julia> F = @free_group(:F1, :F2);

julia> imgs = gens(symmetric_group(4))
2-element Vector{PermGroupElem}:
 (1,2,3,4)
 (1,2)

julia> map_word(F1^2, imgs)
(1,3)(2,4)

julia> map_word(F2, imgs)
(1,2)

julia> map_word([1, 2], imgs)
(2,3,4)

julia> map_word([1 => 2], imgs)
(1,3)(2,4)

julia> map_word(one(F), imgs)
()

julia> map_word(one(F), imgs, init = imgs[1])
(1,2,3,4)

julia> map_word([], [], init=imgs[1])
(1,2,3,4)

julia> invs = Vector(undef, 2);

julia> map_word(F1^-2*F2, imgs, genimgs_inv = invs)
(1,3,2,4)

julia> invs
2-element Vector{Any}:
    (1,4,3,2)
 #undef

source

Functions for (subgroups of) finitely presented groups

free_group — Function

free_group(n::Int, s::VarName = :f; eltype::Symbol = :letter) -> FPGroup
free_group(L::VarName... ; eltype::Symbol = :letter) -> FPGroup
free_group(varnames_specifiers... ; eltype::Symbol = :letter) -> FPGroup

Return a free group.

The first form returns a free group of rank n, where the generators are printed as "$s1", "$s2", ..., the default being f1, f2, ...

The second form returns a free group of rank n, where n is the length of L, and L consists of strings, symbols or characters giving the variable names.

In the final form, the argument list consists of a sequence of one or more of the following:

A vector L of variable names.
A pair of the form A => B, where A is a VarName (so a string, symbol or character) and B is a range or more generally an AbstractVector. Then length(B) generators are defined whose names derive from a combination of A and the respective element of B. For example :x => 1:3 defines three generators x[1], x[2], x[3].
A pair of the form A => C, where A is again a VarName, and C is a tuple of ranges or v. For example "a" => (1:2, 1:2) defines four generators a[1, 1], a[2, 1], a[1, 2], a[2, 2].

For the second and third type, optionally the A part can contain the placeholder # to modify where the indices are inserted. For example "a#" => (1:2, 1:2) defines four generators a11, a21, a12, a22.

Also, instead of a range, any vector can be used. For example "#" => ([:x,:y], [:A, :B]) defines four generators xA, yA, xB, yB.

In all variants, if the optional keyword argument eltype is given and has the value :syllable then each element in the free group is internally represented by a vector of syllables, whereas a representation by a vector of integers is chosen in the default case of eltype == :letter.

Warning

Julia variables named like the group generators are not created by this function. However, the macro @free_group does just that.

Examples

julia> F = free_group(:a, :b)
Free group of rank 2

julia> w = F[1]^3 * F[2]^F[1] * F[-2]^2
a^2*b*a*b^-2

Here we show some of the different ways to create a free group.

julia> gens(free_group(2))
2-element Vector{FPGroupElem}:
 f1
 f2

julia> gens(free_group(2, :a))
2-element Vector{FPGroupElem}:
 a1
 a2

julia> gens(free_group(:u, :v))
2-element Vector{FPGroupElem}:
 u
 v

julia> gens(free_group([:a, :b], "x" => 1:2, 'y' => (1:2, 1:2)))
8-element Vector{FPGroupElem}:
 a
 b
 x[1]
 x[2]
 y[1, 1]
 y[2, 1]
 y[1, 2]
 y[2, 2]

source

@free_group — Macro

@free_group(args...)

Return the free group obtained from free_group(args...) and introduce its generators as Julia variables into the current scope.

Examples

julia> F = @free_group(:a, :b)
Free group of rank 2

julia> a^2*b*a*b^-2
a^2*b*a*b^-2

Note that the varname => vector syntax for specifying a vector or matrix or general array of variables behaves slightly differently compared to free_group, as the following example demonstrates.

julia> U1 = free_group("x" => 1:3); gens(U1)
3-element Vector{FPGroupElem}:
 x[1]
 x[2]
 x[3]

julia> U2 = @free_group("x" => 1:3); gens(U2)
3-element Vector{FPGroupElem}:
 x1
 x2
 x3

julia> (x2^x1)^-1
x1^-1*x2^-1*x1

source

full_group — Method

full_group(G::T) where T <: Union{SubFPGroup, SubPcGroup}
full_group(G::T) where T <: Union{FPGroup, PcGroup}

Return F, emb where F is the full pc group of f.p. group of which G is a subgroup, and emb is an embedding of G into F.

Examples

julia> G = perfect_group(FPGroup, 60, 1);

julia> H = sylow_subgroup(G, 2)[1];

julia> full_group(H)[1] == G
true

julia> full_group(G)[1] == G
true

source

relators — Method

relators(G::FPGroup)

Return a vector of relators for the full finitely presented group G, i.e., elements $[w_1, w_2, \ldots, w_n]$ in $F =$ free_group(ngens(G)) such that G is isomorphic with $F/[w_1, w_2, \ldots, w_n]$.

Examples

julia> f = @free_group(:x, :y);

julia> q = quo(f, [x^2, y^2, comm(x, y)])[1];  relators(q)
3-element Vector{FPGroupElem}:
 x^2
 y^2
 x^-1*y^-1*x*y

source

simplified_fp_group — Method

simplified_fp_group(G::FPGroup)

Return a group H of type FPGroup and an isomorphism f from G to H, where the presentation of H was obtained from the presentation of G by applying Tietze transformations in order to reduce it with respect to the number of generators, the number of relators, and the relator lengths.

Examples

julia> F = free_group(3)
Free group of rank 3

julia> G = quo(F, [gen(F,1)])[1]
Finitely presented group of infinite order

julia> simplified_fp_group(G)[1]
Finitely presented group of infinite order

source

epimorphism_from_free_group — Method

epimorphism_from_free_group(G::GAPGroup)

Return an epimorphism epi from a free group F == domain(epi) onto G, where F has the same number of generators as G and such that for each i it maps gen(F,i) to gen(G,i).

A useful application of this function is expressing an element of G as a word in its generators.

Examples

julia> G = symmetric_group(4);

julia> epi = epimorphism_from_free_group(G)
Group homomorphism
  from free group of rank 2
  to Sym(4)

julia> pi = G([2,4,3,1])
(1,2,4)

julia> w = preimage(epi, pi);

julia> map_word(w, gens(G))
(1,2,4)

source

Technicalities

FPGroup — Type

FPGroup

Finitely presented group. Such groups can be constructed a factors of free groups, see free_group.

For a group G of type FPGroup, the elements in gens(G) satisfy the relators of the underlying presentation.

Functions that compute subgroups of G return groups of type SubFPGroup.

source

FPGroupElem — Type

FPGroupElem

Element of a finitely presented group.

The generators of a finitely presented group are displayed as f1, f2, f3, etc., and every element of a finitely presented group is displayed as product of the generators.

source

SubFPGroup — Type

SubFPGroup

Subgroup of a finitely presented group, a group that is defined by generators that are elements of a group G of type FPGroup.

Operations for computing subgroups of a group of type FPGroup or SubFPGroup, such as derived_subgroup and sylow_subgroup, return groups of type SubFPGroup.

Note that functions such as relators do not make sense for proper subgroups of a finitely presented group.

source

SubFPGroupElem — Type

SubFPGroupElem

Element of a subgroup of a finitely presented group.

The elements are displayed in the same way as the elements of full finitely presented groups, see FPGroupElem.

source