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
true

source

is_ready — Function

is_ready(tree::GroupRecognitionTree)

Return true if the recognition procedure for the group of tree was successful, and false otherwise.

Examples

julia> rec = recognize(GL(4, 2));  is_ready(rec)
true

source

nice_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

source

straight_line_program — Method

straight_line_program(tree::GroupRecognitionTree, g::GAPGroupElem)

Return a straight line program for the element g of the group of tree. The inputs of this program correspond to nice_gens(tree), see nice_gens for an example.

source