2021-05-05 01:10:28 +02:00
|
|
|
## "Abstract" definitions
|
|
|
|
|
|
|
|
"""
|
|
|
|
AbstractFPGroup
|
|
|
|
|
2022-10-13 23:30:55 +02:00
|
|
|
An Abstract type representing finitely presented groups. Every instance must implement
|
2021-05-05 01:10:28 +02:00
|
|
|
* `KnuthBendix.alphabet(G::MyFPGroup)`
|
2021-05-05 02:32:27 +02:00
|
|
|
* `rewriting(G::MyFPGroup)` : return the rewriting object which must implement
|
2022-10-13 23:30:55 +02:00
|
|
|
> `KnuthBendix.rewrite!(u, v, rewriting(G))`.
|
2022-10-14 01:03:19 +02:00
|
|
|
E.g. for `G::FreeGroup` `alphabet(G)` is returned, which amounts to free rewriting.
|
|
|
|
* `ordering(G::MyFPGroup)[ = KnuthBendix.ordering(rewriting(G))]` : return the
|
|
|
|
(implicit) ordering for the alphabet of `G`.
|
2021-05-05 02:35:12 +02:00
|
|
|
* `relations(G::MyFPGroup)` : return a set of defining relations.
|
2021-05-05 01:10:28 +02:00
|
|
|
|
2022-10-13 23:30:55 +02:00
|
|
|
AbstractFPGroup may also override `word_type(::Type{MyFPGroup}) = Word{UInt8}`,
|
|
|
|
which controls the word type used for group elements.
|
|
|
|
If a group has more than `255` generators you need to define e.g.
|
2021-05-24 01:41:37 +02:00
|
|
|
> `word_type(::Type{MyFPGroup}) = Word{UInt16}`
|
2021-05-05 01:10:28 +02:00
|
|
|
"""
|
|
|
|
abstract type AbstractFPGroup <: GroupsCore.Group end
|
|
|
|
|
|
|
|
word_type(G::AbstractFPGroup) = word_type(typeof(G))
|
|
|
|
# the default:
|
2021-05-16 23:23:16 +02:00
|
|
|
word_type(::Type{<:AbstractFPGroup}) = Word{UInt8}
|
2021-05-05 01:10:28 +02:00
|
|
|
|
2021-12-18 21:57:41 +01:00
|
|
|
"""
|
|
|
|
rewriting(G::AbstractFPGroup)
|
2022-10-13 23:30:55 +02:00
|
|
|
Return a "rewriting object" for elements of `G`.
|
|
|
|
|
|
|
|
The rewriting object must must implement
|
|
|
|
KnuthBendix.rewrite!(u::AbstractWord, v::AbstractWord, rewriting(G))
|
2021-12-18 21:57:41 +01:00
|
|
|
|
2022-10-13 23:30:55 +02:00
|
|
|
For example if `G` is a `FreeGroup` then `alphabet(G)` is returned which results
|
|
|
|
in free rewriting. For `FPGroup` a rewriting system is returned which may
|
|
|
|
(or may not) rewrite word `v` to its normal form (depending on e.g. its confluence).
|
2021-12-18 21:57:41 +01:00
|
|
|
"""
|
|
|
|
function rewriting end
|
2021-05-05 02:32:27 +02:00
|
|
|
|
2022-10-14 01:03:19 +02:00
|
|
|
KnuthBendix.ordering(G::AbstractFPGroup) = ordering(rewriting(G))
|
|
|
|
KnuthBendix.alphabet(G::AbstractFPGroup) = alphabet(ordering(G))
|
|
|
|
|
2021-12-11 13:55:47 +01:00
|
|
|
Base.@propagate_inbounds function (G::AbstractFPGroup)(
|
|
|
|
word::AbstractVector{<:Integer},
|
|
|
|
)
|
2023-03-15 19:07:14 +01:00
|
|
|
@boundscheck @assert all(l -> 1 <= l <= length(alphabet(G)), word)
|
2021-05-05 01:10:28 +02:00
|
|
|
return FPGroupElement(word_type(G)(word), G)
|
|
|
|
end
|
|
|
|
|
|
|
|
## Group Interface
|
|
|
|
|
|
|
|
Base.one(G::AbstractFPGroup) = FPGroupElement(one(word_type(G)), G)
|
|
|
|
|
2023-03-15 19:07:14 +01:00
|
|
|
function Base.eltype(::Type{FPG}) where {FPG<:AbstractFPGroup}
|
|
|
|
return FPGroupElement{FPG,word_type(FPG)}
|
|
|
|
end
|
2021-05-05 01:10:28 +02:00
|
|
|
|
2021-05-07 18:14:13 +02:00
|
|
|
include("iteration.jl")
|
2021-05-05 01:10:28 +02:00
|
|
|
|
|
|
|
GroupsCore.ngens(G::AbstractFPGroup) = length(G.gens)
|
|
|
|
|
|
|
|
function GroupsCore.gens(G::AbstractFPGroup, i::Integer)
|
2021-05-16 23:22:33 +02:00
|
|
|
@boundscheck 1 <= i <= GroupsCore.ngens(G)
|
2021-05-05 02:33:36 +02:00
|
|
|
l = alphabet(G)[G.gens[i]]
|
|
|
|
return FPGroupElement(word_type(G)([l]), G)
|
2021-05-05 01:10:28 +02:00
|
|
|
end
|
2023-03-15 19:07:14 +01:00
|
|
|
function GroupsCore.gens(G::AbstractFPGroup)
|
|
|
|
return [gens(G, i) for i in 1:GroupsCore.ngens(G)]
|
|
|
|
end
|
2021-05-05 01:10:28 +02:00
|
|
|
|
2023-03-15 19:07:14 +01:00
|
|
|
function Base.isfinite(::AbstractFPGroup)
|
|
|
|
return (
|
|
|
|
@warn "using generic isfinite(::AbstractFPGroup): the returned `false` might be wrong"; false
|
|
|
|
)
|
|
|
|
end
|
2021-05-24 15:35:28 +02:00
|
|
|
|
2021-05-05 01:10:28 +02:00
|
|
|
## FPGroupElement
|
|
|
|
|
2021-06-29 16:52:35 +02:00
|
|
|
abstract type AbstractFPGroupElement{Gr} <: GroupElement end
|
|
|
|
|
2023-05-25 11:58:32 +02:00
|
|
|
Base.copy(g::AbstractFPGroupElement) = one(g) * g
|
|
|
|
word(f::AbstractFPGroupElement) = f.word
|
|
|
|
|
2021-12-11 13:55:47 +01:00
|
|
|
mutable struct FPGroupElement{Gr<:AbstractFPGroup,W<:AbstractWord} <:
|
|
|
|
AbstractFPGroupElement{Gr}
|
2021-05-05 01:10:28 +02:00
|
|
|
word::W
|
|
|
|
savedhash::UInt
|
2021-06-29 16:52:35 +02:00
|
|
|
parent::Gr
|
2021-05-05 01:10:28 +02:00
|
|
|
|
2023-03-15 19:07:14 +01:00
|
|
|
function FPGroupElement(
|
2021-12-11 13:55:47 +01:00
|
|
|
word::W,
|
|
|
|
G::AbstractFPGroup,
|
2023-03-15 19:07:14 +01:00
|
|
|
hash::UInt = UInt(0),
|
|
|
|
) where {W<:AbstractWord}
|
|
|
|
return new{typeof(G),W}(word, hash, G)
|
|
|
|
end
|
2021-07-05 15:05:03 +02:00
|
|
|
|
2023-03-15 19:07:14 +01:00
|
|
|
function FPGroupElement{Gr,W}(word::AbstractWord, G::Gr) where {Gr,W}
|
|
|
|
return new{Gr,W}(word, UInt(0), G)
|
|
|
|
end
|
2021-05-05 01:10:28 +02:00
|
|
|
end
|
2021-12-11 13:55:31 +01:00
|
|
|
|
2023-05-25 11:58:32 +02:00
|
|
|
function Base.copy(f::FPGroupElement)
|
|
|
|
return FPGroupElement(copy(word(f)), parent(f), f.savedhash)
|
|
|
|
end
|
2021-05-05 01:10:28 +02:00
|
|
|
|
|
|
|
#convenience
|
2021-06-29 16:52:35 +02:00
|
|
|
KnuthBendix.alphabet(g::AbstractFPGroupElement) = alphabet(parent(g))
|
2021-05-05 01:10:28 +02:00
|
|
|
|
2021-06-29 16:52:35 +02:00
|
|
|
function Base.show(io::IO, f::AbstractFPGroupElement)
|
2021-05-05 01:10:28 +02:00
|
|
|
f = normalform!(f)
|
2021-12-11 13:55:47 +01:00
|
|
|
return KnuthBendix.print_repr(io, word(f), alphabet(f))
|
2021-05-05 01:10:28 +02:00
|
|
|
end
|
|
|
|
|
|
|
|
## GroupElement Interface for FPGroupElement
|
|
|
|
|
2021-06-29 16:52:35 +02:00
|
|
|
Base.parent(f::AbstractFPGroupElement) = f.parent
|
2021-05-05 01:10:28 +02:00
|
|
|
|
2021-06-29 16:52:35 +02:00
|
|
|
function Base.:(==)(g::AbstractFPGroupElement, h::AbstractFPGroupElement)
|
2021-05-05 01:10:28 +02:00
|
|
|
@boundscheck @assert parent(g) === parent(h)
|
2021-05-07 18:11:11 +02:00
|
|
|
normalform!(g)
|
|
|
|
normalform!(h)
|
2024-02-12 12:35:09 +01:00
|
|
|
# I. compare hashes of the normalform
|
|
|
|
# II. compare some data associated to FPGroupElement,
|
|
|
|
# e.g. word, image of the domain etc.
|
2021-05-05 01:10:28 +02:00
|
|
|
hash(g) != hash(h) && return false
|
2024-02-12 12:35:09 +01:00
|
|
|
equality_data(g) == equality_data(h) && return true # compares
|
|
|
|
|
|
|
|
# if this failed it is still possible that the words together can be
|
|
|
|
# rewritten even further, so we
|
|
|
|
# 1. rewrite word(g⁻¹·h) w.r.t. rewriting(parent(g))
|
|
|
|
# 2. check if the result is empty
|
|
|
|
G = parent(g)
|
|
|
|
|
|
|
|
g⁻¹h = append!(inv(word(g), alphabet(G)), word(h))
|
|
|
|
# similar + empty preserve the storage size
|
|
|
|
# saves some re-allocations if res does not represent id
|
|
|
|
res = similar(word(g))
|
|
|
|
resize!(res, 0)
|
|
|
|
res = KnuthBendix.rewrite!(res, g⁻¹h, rewriting(G))
|
|
|
|
return isone(res)
|
2021-05-05 01:10:28 +02:00
|
|
|
end
|
|
|
|
|
|
|
|
function Base.deepcopy_internal(g::FPGroupElement, stackdict::IdDict)
|
2024-02-12 12:33:57 +01:00
|
|
|
haskey(stackdict, g) && return stackdict[g]
|
|
|
|
cw = Base.deepcopy_internal(word(g), stackdict)
|
|
|
|
h = FPGroupElement(cw, parent(g), g.savedhash)
|
|
|
|
stackdict[g] = h
|
|
|
|
return h
|
2021-05-05 01:10:28 +02:00
|
|
|
end
|
|
|
|
|
2021-12-11 13:55:47 +01:00
|
|
|
function Base.inv(g::GEl) where {GEl<:AbstractFPGroupElement}
|
2021-06-29 16:52:35 +02:00
|
|
|
G = parent(g)
|
2022-10-13 23:27:50 +02:00
|
|
|
return GEl(inv(word(g), alphabet(G)), G)
|
2021-06-29 16:52:35 +02:00
|
|
|
end
|
2021-05-05 01:10:28 +02:00
|
|
|
|
2021-12-11 13:55:47 +01:00
|
|
|
function Base.:(*)(g::GEl, h::GEl) where {GEl<:AbstractFPGroupElement}
|
2021-05-05 01:10:28 +02:00
|
|
|
@boundscheck @assert parent(g) === parent(h)
|
2023-03-22 21:44:09 +01:00
|
|
|
A = alphabet(parent(g))
|
|
|
|
k = 0
|
|
|
|
while k + 1 ≤ min(length(word(g)), length(word(h)))
|
|
|
|
if inv(word(g)[end-k], A) == word(h)[k+1]
|
|
|
|
k += 1
|
|
|
|
else
|
|
|
|
break
|
|
|
|
end
|
|
|
|
end
|
|
|
|
w = @view(word(g)[1:end-k]) * @view(word(h)[k+1:end])
|
|
|
|
res = GEl(w, parent(g))
|
|
|
|
return res
|
2021-05-05 01:10:28 +02:00
|
|
|
end
|
|
|
|
|
2023-03-15 19:07:14 +01:00
|
|
|
function GroupsCore.isfiniteorder(g::AbstractFPGroupElement)
|
|
|
|
return isone(g) ? true :
|
|
|
|
(
|
2021-12-11 13:55:47 +01:00
|
|
|
@warn "using generic isfiniteorder(::AbstractFPGroupElement): the returned `false` might be wrong"; false
|
|
|
|
)
|
2023-03-15 19:07:14 +01:00
|
|
|
end
|
2021-05-05 01:10:28 +02:00
|
|
|
|
|
|
|
# additional methods:
|
2021-06-29 16:52:35 +02:00
|
|
|
Base.isone(g::AbstractFPGroupElement) = (normalform!(g); isempty(word(g)))
|
2021-05-05 01:10:28 +02:00
|
|
|
|
|
|
|
## Free Groups
|
|
|
|
|
2021-12-18 19:33:37 +01:00
|
|
|
struct FreeGroup{T,O} <: AbstractFPGroup
|
2021-05-05 01:10:28 +02:00
|
|
|
gens::Vector{T}
|
2021-12-18 19:33:37 +01:00
|
|
|
ordering::O
|
2021-05-05 01:10:28 +02:00
|
|
|
|
2021-12-18 19:33:37 +01:00
|
|
|
function FreeGroup(gens, ordering::KnuthBendix.WordOrdering)
|
2021-05-05 01:10:28 +02:00
|
|
|
@assert length(gens) == length(unique(gens))
|
2022-10-13 23:21:42 +02:00
|
|
|
@assert all(l -> l in alphabet(ordering), gens)
|
2021-12-18 19:33:37 +01:00
|
|
|
return new{eltype(gens),typeof(ordering)}(gens, ordering)
|
2021-05-05 01:10:28 +02:00
|
|
|
end
|
|
|
|
end
|
|
|
|
|
2024-02-12 12:17:48 +01:00
|
|
|
function FreeGroup(n::Integer)
|
|
|
|
symbols =
|
|
|
|
collect(Iterators.flatten((Symbol(:f, i), Symbol(:F, i)) for i in 1:n))
|
|
|
|
inverses = collect(Iterators.flatten((2i, 2i - 1) for i in 1:n))
|
|
|
|
return FreeGroup(Alphabet(symbols, inverses))
|
|
|
|
end
|
|
|
|
|
|
|
|
FreeGroup(A::Alphabet) = FreeGroup(KnuthBendix.LenLex(A))
|
2021-12-18 19:33:37 +01:00
|
|
|
|
2024-02-12 12:17:48 +01:00
|
|
|
function __group_gens(A::Alphabet)
|
2023-03-15 19:07:14 +01:00
|
|
|
@boundscheck @assert all(KnuthBendix.hasinverse(l, A) for l in A)
|
2022-10-13 23:21:42 +02:00
|
|
|
gens = Vector{eltype(A)}()
|
|
|
|
invs = Vector{eltype(A)}()
|
|
|
|
for l in A
|
2021-06-21 17:52:51 +02:00
|
|
|
l ∈ invs && continue
|
|
|
|
push!(gens, l)
|
2022-10-13 23:27:50 +02:00
|
|
|
push!(invs, inv(l, A))
|
2021-06-21 17:52:51 +02:00
|
|
|
end
|
2024-02-12 12:17:48 +01:00
|
|
|
return gens
|
2021-05-05 01:10:28 +02:00
|
|
|
end
|
|
|
|
|
2024-02-12 12:17:48 +01:00
|
|
|
function FreeGroup(O::KnuthBendix.WordOrdering)
|
|
|
|
grp_gens = __group_gens(alphabet(O))
|
|
|
|
return FreeGroup(grp_gens, O)
|
2021-05-26 12:12:26 +02:00
|
|
|
end
|
|
|
|
|
2023-03-15 19:07:14 +01:00
|
|
|
function Base.show(io::IO, F::FreeGroup)
|
|
|
|
return print(io, "free group on $(ngens(F)) generators")
|
|
|
|
end
|
2021-05-05 01:10:28 +02:00
|
|
|
|
|
|
|
# mandatory methods:
|
2021-12-18 19:33:37 +01:00
|
|
|
KnuthBendix.ordering(F::FreeGroup) = F.ordering
|
2022-10-14 01:03:19 +02:00
|
|
|
rewriting(F::FreeGroup) = alphabet(F) # alphabet(F) = alphabet(ordering(F))
|
|
|
|
relations(F::FreeGroup) = Pair{eltype(F),eltype(F)}[]
|
2021-05-05 02:35:12 +02:00
|
|
|
|
2021-05-24 15:35:28 +02:00
|
|
|
# GroupsCore interface:
|
|
|
|
# these are mathematically correct
|
|
|
|
Base.isfinite(::FreeGroup) = false
|
|
|
|
|
2023-03-15 19:07:14 +01:00
|
|
|
function GroupsCore.isfiniteorder(g::AbstractFPGroupElement{<:FreeGroup})
|
|
|
|
return isone(g) ? true : false
|
|
|
|
end
|
2021-05-24 15:35:28 +02:00
|
|
|
|
2021-05-05 02:35:12 +02:00
|
|
|
## FP Groups
|
|
|
|
|
2022-10-14 01:03:19 +02:00
|
|
|
struct FPGroup{T,RW,S} <: AbstractFPGroup
|
2021-05-05 02:35:12 +02:00
|
|
|
gens::Vector{T}
|
2021-05-16 23:22:33 +02:00
|
|
|
relations::Vector{Pair{S,S}}
|
2022-10-14 01:03:19 +02:00
|
|
|
rw::RW
|
2021-05-05 02:35:12 +02:00
|
|
|
end
|
|
|
|
|
|
|
|
relations(G::FPGroup) = G.relations
|
2022-10-14 01:03:19 +02:00
|
|
|
rewriting(G::FPGroup) = G.rw
|
2021-05-05 02:35:12 +02:00
|
|
|
|
|
|
|
function FPGroup(
|
|
|
|
G::AbstractFPGroup,
|
2021-05-16 23:22:33 +02:00
|
|
|
rels::AbstractVector{<:Pair{GEl,GEl}};
|
2023-03-15 19:07:14 +01:00
|
|
|
ordering = KnuthBendix.ordering(G),
|
|
|
|
kwargs...,
|
2021-05-16 23:22:33 +02:00
|
|
|
) where {GEl<:FPGroupElement}
|
2021-05-05 02:35:12 +02:00
|
|
|
for (lhs, rhs) in rels
|
|
|
|
@assert parent(lhs) === parent(rhs) === G
|
|
|
|
end
|
2021-05-16 23:22:33 +02:00
|
|
|
word_rels = [word(lhs) => word(rhs) for (lhs, rhs) in [relations(G); rels]]
|
2021-12-18 19:33:37 +01:00
|
|
|
rws = KnuthBendix.RewritingSystem(word_rels, ordering)
|
2021-05-05 02:35:12 +02:00
|
|
|
|
2022-10-13 23:38:18 +02:00
|
|
|
rws = KnuthBendix.knuthbendix(rws, KnuthBendix.Settings(; kwargs...))
|
2021-05-05 02:35:12 +02:00
|
|
|
|
2022-10-13 23:41:05 +02:00
|
|
|
return FPGroup(G.gens, rels, KnuthBendix.IndexAutomaton(rws))
|
2021-05-05 02:35:12 +02:00
|
|
|
end
|
|
|
|
|
2021-12-18 19:34:04 +01:00
|
|
|
function Base.show(io::IO, ::MIME"text/plain", G::FPGroup)
|
2024-02-12 12:38:28 +01:00
|
|
|
println(
|
|
|
|
io,
|
|
|
|
"Finitely presented group generated by $(ngens(G)) element",
|
|
|
|
ngens(G) > 1 ? 's' : "",
|
|
|
|
": ",
|
|
|
|
)
|
|
|
|
join(io, gens(G), ", ", ", and ")
|
|
|
|
println(
|
|
|
|
io,
|
|
|
|
"\n subject to relation",
|
|
|
|
length(relations(G)) > 1 ? 's' : "",
|
|
|
|
)
|
2021-12-18 19:34:04 +01:00
|
|
|
return Base.print_array(io, relations(G))
|
|
|
|
end
|
|
|
|
|
2021-05-05 02:35:12 +02:00
|
|
|
function Base.show(io::IO, G::FPGroup)
|
|
|
|
print(io, "⟨")
|
2021-12-18 19:34:04 +01:00
|
|
|
Base.print_array(io, permutedims(gens(G)))
|
|
|
|
println(io, " | ")
|
|
|
|
print(io, "\t ")
|
|
|
|
Base.print_array(io, permutedims(relations(G)))
|
|
|
|
return print(io, " ⟩")
|
2021-05-05 02:35:12 +02:00
|
|
|
end
|
2021-05-28 14:20:17 +02:00
|
|
|
|
2023-03-15 19:07:14 +01:00
|
|
|
function Base.show(io::IO, ::Type{<:FPGroup{T}}) where {T}
|
|
|
|
return print(io, FPGroup, "{$T, …}")
|
|
|
|
end
|
2021-12-11 13:55:31 +01:00
|
|
|
|
2021-05-28 14:20:17 +02:00
|
|
|
## GSymbol aka letter of alphabet
|
|
|
|
|
|
|
|
abstract type GSymbol end
|
|
|
|
Base.literal_pow(::typeof(^), t::GSymbol, ::Val{-1}) = inv(t)
|
2021-06-21 17:53:29 +02:00
|
|
|
|
|
|
|
function subscriptify(n::Integer)
|
|
|
|
subscript_0 = Int(0x2080) # Char(0x2080) -> subscript 0
|
|
|
|
return join([Char(subscript_0 + i) for i in reverse(digits(n))], "")
|
|
|
|
end
|