Finitely presented groups

FPGroup

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

TODO: document this

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

The first form returns the free group of rank n, where the generators are printed as s1, s2, ..., the default being f1, f2, ... If eltype 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.

The second form, if L has length n, returns the free group of rank n, where the i-th generator is printed as L[i].

The third form, if there are n arguments L..., returns the free group of rank n, where the i-th generator is printed as L[i].

is_full_fp_group(G::FPGroup)

Return true if G has been constructed as a free group or a quotient of a free group, and false otherwise.

Note that also subgroups of groups of type FPGroup have the type FPGroup, and functions such as relators do not make sense for proper subgroups.

Examples

julia> f = free_group(2);  is_full_fp_group(f)
true

julia> s = sub(f, gens(f))[1];  is_full_fp_group(s)
false

julia> q = quo(f, [gen(f,1)^2])[1];  is_full_fp_group(q)
true

julia> u = sub(q, gens(q))[1];  is_full_fp_group(u)
false

relators(G::FPGroup)

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

An exception is thrown if G has been constructed only as a subgroup of a full finitely presented group, see is_full_fp_group.

Examples

julia> f = free_group(2);  (x, y) = gens(f);

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

length(g::FPGroupElem)

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

Examples

julia> F = free_group(2);  F1 = gen(F, 1);  F2 = gen(F, 2);

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

map_word(g::FPGroupElem, 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)

Return the product $R_1 R_2 \cdots R_n$ that is described by g or v, respectively.

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_i} 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 = $`imgs[`$ij$`]`$^{ej}$.

If g is an element of a finitely presented group then the result is defined as map_word applied to a representing element of the underlying free group.

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 = $`imgs[`$|ki|$`]`$^{\epsiloni}$ 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.

If v has length zero then init is returned if also genimgs has length zero, otherwise one(genimgs[1]) is returned. In all other cases, init is ignored.

Examples

julia> F = free_group(2);  F1 = gen(F, 1);  F2 = gen(F, 2);

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(one(F), imgs)
()

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