Group recognition
The idea of constructive group recognition is to compute a recognition tree for a given (permutation or matrix) group, which describes the structure of this group in a recursive way: Each non-leaf node of the tree describes an epimorphism such that the kernel and the image belong to the two subtrees of the node. Each leaf node describes a group for which efficient methods are available that allow one to decide whether a group element is an element of this group, and if yes to write the element as a word in terms of suitable generators.
The recognition tree has enough information to decide whether a group element is an element of the given group, and if yes to write the element as a word in terms of suitable generators of the given group.
recognize — Function
recognize(G::Union{PermGroup, MatrixGroup})Return a GroupRecognitionTree object that describes the structure of G in a recursive way. If the recognition was successful (see is_ready) then the result provides a membership test that is usually more efficient than the membership test without the recognition information.
Examples
julia> recognize(symmetric_group(5))
Recognition tree: MovesOnlySmallPoints Size=120
julia> g = general_linear_group(4, 9);
julia> s = sub(g, [rand(g), rand(g)])[1];
julia> rec = recognize(s); is_ready(rec)
true
julia> rand(s) in rec
truenice_gens — Function
nice_gens(tree::GroupRecognitionTree)Return the vector of generators of the group of tree w.r.t. which the straight line programs for group elements computed by straight_line_program are written.
Examples
julia> rec = recognize(GL(4, 2)); is_ready(rec)
true
julia> x = rand(group(rec));
julia> slp = straight_line_program(rec, x);
julia> evaluate(slp, nice_gens(rec)) == x
true