## Groups.jl

An implementation of finitely-presented groups
Author kalmarek
Popularity
8 Stars
Updated Last
1 Year Ago
Started In
January 2017

# 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.

### Used By Packages

No packages found.