Groups.jl/README.md

Groups

An implementation of finitely-presented groups together with normalization (using Knuth-Bendix procedure).

The package implements AbstractFPGroup with three concrete types: FreeGroup, FPGroup and AutomorphismGroup. Here's an example usage:

julia> using Groups, GroupsCore

julia> A = Alphabet([:a, :A, :b, :B, :c, :C], [2, 1, 4, 3, 6, 5])
Alphabet of Symbol
  1. a   (inverse of: A)
  2. A   (inverse of: a)
  3. b   (inverse of: B)
  4. B   (inverse of: b)
  5. c   (inverse of: C)
  6. C   (inverse of: c)

julia> F = FreeGroup(A)
free group on 3 generators

julia> a,b,c = gens(F)
3-element Vector{FPGroupElement{FreeGroup{Symbol, KnuthBendix.LenLex{Symbol}}, …}}:
 a
 b
 c

julia> a*inv(a)
(id)

julia> (a*b)^2
a*b*a*b

julia> commutator(a, b)
A*B*a*b

julia> x = a*b; y = inv(b)*a;

julia> x*y
a^2

FPGroup

Let's create a quotient of the free group above:

julia> ε = one(F)
(id)

julia> G = FPGroup(F, [a^2 => ε, b^3=> ε, (a*b)^7=>ε, (a*b*a*inv(b))^6 => ε, commutator(a, c) => ε, commutator(b, c) => ε ], max_rules=100)
┌ Warning: Maximum number of rules (100) reached.
│ The rewriting system may not be confluent.
│ You may retry `knuthbendix` with a larger `max_rules` kwarg.
└ @ KnuthBendix ~/.julia/packages/KnuthBendix/6ME1b/src/knuthbendix_base.jl:8
Finitely presented group generated by:
        { a  b  c },
subject to relations:
                                             a^2 => (id)
                                             b^3 => (id)
                     a*b*a*b*a*b*a*b*a*b*a*b*a*b => (id)
 a*b*a*B*a*b*a*B*a*b*a*B*a*b*a*B*a*b*a*B*a*b*a*B => (id)
                                         A*C*a*c => (id)
                                         B*C*b*c => (id)

As you can see from the warning, the Knuth-Bendix procedure has not completed successfully. This means that we only are able to approximate the word problem in G, i.e. if the equality (==) of two group elements may return false even if group elements are equal. Let us try with a larger maximal number of rules in the underlying rewriting system.

julia> G = FPGroup(F, [a^2 => ε, b^3=> ε, (a*b)^7=>ε, (a*b*a*inv(b))^6 => ε, commutator(a, c) => ε, commutator(b, c) => ε ], max_rules=500)
Finitely presented group generated by:
        { a  b  c },
subject to relations:
                                             a^2 => (id)
                                             b^3 => (id)
                     a*b*a*b*a*b*a*b*a*b*a*b*a*b => (id)
 a*b*a*B*a*b*a*B*a*b*a*B*a*b*a*B*a*b*a*B*a*b*a*B => (id)
                                         A*C*a*c => (id)
                                         B*C*b*c => (id)

This time there was no warning, i.e. Knuth-Bendix completion was successful and we may treat the equality (==) as the true mathematical equality. Note that G is the direct product of ℤ = ⟨ c ⟩ and a quotient of van Dyck (2,3,7)-group. Let's create a random word and reduce it as an element of G.

julia> using Random; Random.seed!(1); w = Groups.Word(rand(1:length(A), 16));

julia> length(w), w # word of itself
(16, 1·3·5·4·6·2·5·5·5·2·4·3·2·1·4·4)

julia> f = F(w) # freely reduced w
a*b*c*B*C*A*c^3*A*B^2

julia> length(word(f)), word(f) # the underlying word in F
(12, 1·3·5·4·6·2·5·5·5·2·4·4)

julia> g = G(w) # w as an element of G
a*b*c^3

julia> length(word(g)), word(g) # the underlying word in G
(5, 1·3·5·5·5)

As we can see the underlying words change according to where they are reduced. Note that a word w (of type Word <: AbstractWord) is just a sequence of numbers -- indices of letters of an Alphabet. Without the alphabet w has no intrinsic meaning.

Automorphism Groups

Relatively complete is the support for the automorphisms of free groups generated by transvections (or Nielsen generators):

julia> saut = SpecialAutomorphismGroup(F, max_rules=1000)
automorphism group of free group on 3 generators

julia> S = gens(saut)
12-element Vector{Automorphism{FreeGroup{Symbol, KnuthBendix.LenLex{Symbol}}, …}}:
 ϱ₁.₂
 ϱ₁.₃
 ϱ₂.₁
 ϱ₂.₃
 ϱ₃.₁
 ϱ₃.₂
 λ₁.₂
 λ₁.₃
 λ₂.₁
 λ₂.₃
 λ₃.₁
 λ₃.₂

julia> x, y, z = S[1], S[12], S[6];

julia> f = x*y*inv(z);

julia> g = inv(z)*y*x;

julia> word(f), word(g)
(1·23·12, 12·23·1)

Even though there is no known finite, confluent rewriting system for automorphism groupsof the free group (so Knuth-Bendix did not finish successfully) we have another ace in our sleeve to solve the word problem: evaluation. Lets have a look at the images of generators under those automorphisms:

julia> evaluate(f) # or to be more verbose...
(a*b, b, b*c*B)

julia> Groups.domain(g)
(a, b, c)

julia> Groups.evaluate!(Groups.domain(g), g)
(a*b, b, b*c*B)

Since these automorphism map the standard generating set to the same new generating set, they should be considered as equal! And indeed they are:

julia> f == g
true

This is what is happening behind the scenes:

1. words are reduced using a rewriting system
2. if resulting words are equal true is returned
3. if they are not equal Groups.equality_data is computed for each argument (here: the images of generators) and the result of comparison is returned.

Moreover we try to amortize the cost of computing those images. That is a hash of equality_daata is lazily stored in each group element and used as needed. Essentially only if true is returned, but comparison of words returns false recomputation of images is needed (to guard against hash collisions).

---

This package was developed for computations in 1712.07167 and in 1812.03456. If you happen to use this package please cite either of them.