- Notifications
You must be signed in to change notification settings - Fork2
An implementation of finitely-presented groups
License
kalmarek/Groups.jl
Folders and files
| Name | Name | Last commit message | Last commit date | |
|---|---|---|---|---|
Repository files navigation
An implementation of finitely-presented groups together with normalization (using Knuth-Bendix procedure).
The package implementsAbstractFPGroup with three concrete types:FreeGroup,FPGroup andAutomorphismGroup. Here's an example usage:
julia>using Groups, GroupsCorejulia> A=Alphabet([:a,:A,:b,:B,:c,:C], [2,1,4,3,6,5])Alphabet of Symbol1. 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 on3 generatorsjulia> a,b,c=gens(F)3-element Vector{FPGroupElement{FreeGroup{Symbol, KnuthBendix.LenLex{Symbol}},…}}: a b cjulia> a*inv(a)(id)julia> (a*b)^2a*b*a*bjulia>commutator(a, b)A*B*a*bjulia> x= a*b; y=inv(b)*a;julia> x*ya^2
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:8Finitely 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 toapproximate the word problem inG, i.e. if the equality (==) of two group elements may returnfalse 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 thetrue mathematical equality. Note thatG 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 ofG.
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 wa*b*c*B*C*A*c^3*A*B^2julia>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 Ga*b*c^3julia>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 wordw (of typeWord <: AbstractWord) is just a sequence of numbers -- indices of letters of anAlphabet. Without the alphabetw has no intrinsic meaning.
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 on3 generatorsjulia> 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== gtrue
This is what is happening behind the scenes:
- words are reduced using a rewriting system
- if resulting words are equal
trueis returned - if they are not equal
Groups.equality_datais 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 ofequality_daata is lazily stored in each group element and used as needed. Essentially only iftrue is returned, but comparison of words returnsfalse recomputation of images is needed (to guard against hash collisions).
This package was developed for computations in1712.07167 and in1812.03456. If you happen to use this package please cite either of them.
About
An implementation of finitely-presented groups