This chapter describes a generic framework for group recognition. The basic problem is, we want to solve the constructive membership problem: given any \(g \in G\), \(G = \langle X \rangle\), write a straight line program (SLP) from \(X\) to \(g\), for \(g \notin G\) (in the situation that \(G\) is naturally embedded into some bigger group), the algorithm should fail. This is usually done by constructing some nice generators (and then writing an SLP from the nice generators to \(g\) and concatenating with an SLP from \(X\) to the nice generators). Often, for efficiency reasons, we will just store the nice generators and then only be interested in the SLP from those to \(g\). The framework presented here deals with exactly this process.
The generic framework was designed having three situations in mind: permutation groups, matrix groups and projective groups. Although the methods used are quite different for those cases, there is a common pattern in the procedure of recognition. Namely, first we have to find a homomorphism, solve the constructive membership problem recursively in image and kernel, then put it together. The recursion ends in groups where we can solve the constructive membership problem directly. The general framework reflects this idea and separates it from the rest of the recognition methods.
Solution of the constructive membership problem comes in two stages: first a recognition phase
and then a verification phase
. The recognition phase usually consists of randomised algorithms with certain error or failure probabilities. The result is some kind of recognition information
that will describe the group already very well, but which is not yet proven to be correct. However, one can already write arbitrary elements in the group as product of the given generators. In the verification phase a presentation of the group is calculated, thereby proving that the group generated by the given generators is in fact isomorphic to the group described by the recognition information. In many cases the verification phase will be much more expensive than the recognition phase.
In the following sections, we describe the generic framework. We begin in Section 3.1 with a technical description of the recursive procedure behind our main function RecogniseGroup (3.1-5). In Section 3.2 we describe the return type of RecogniseGroup (3.1-5) which we call recognition nodes
. The methods to find homomorphisms are described in Section 3.3. Finally, we have three sections in which we collect conventions for the recognition of different types of groups.
At the heart of the recognition procedure is a function called RecogniseGeneric (3.1-1) which gets a GAP group object and returns a so-called recognition node
(see Subsection 3.2 for details). Success or failure will be indicated by this record being in the filter IsReady (3.2-5) or not.
To know how to find homomorphisms the function gets as another argument a database of methods (see Section 3.3 for a description of the setup for methods for finding homomorphisms and Section 4.1 in Chapter 4 for details about method databases). This database will be different according to the type of group in question.
To describe the algorithm executed by RecogniseGeneric (3.1-1) we first summarise it in steps:
Create a new, empty recognition node.
Use the database of FindHomomorphism methods and the method selection procedure described in Chapter 4 to try to find a homomorphism onto a smaller group or an isomorphism onto another known group. Terminate with failure if this does not work.
If an isomorphism is found or a method somehow else recognises the group in question, such that we can write elements as straight line programs in the generators from now on, then make the recognition node a leaf of the recognition tree and return success.
Otherwise the function sets up all the data for the homomorphism and calls itself with the image of the homomorphism. Note that this might use another database of recognition methods because the homomorphism might change the representation of the group.
After successful recognition of the image group the procedure has to recognise the kernel of the homomorphism. The first step for this is to find generators. If they are not already known from the FindHomomorphism method, they are created by producing random elements in the group, mapping them through the homomorphism, writing them as a straight line program in the images of the generators and applying this straight line program to the original generators. The quotient of the random element and the result of the straight line program lies in the kernel of the homomorphism. After creating 20 (FIXME: is 20 correct?) random generators of the kernel we assume for the moment that they generate the kernel.
The function RecogniseGeneric (3.1-1) can now call itself for the kernel. After successful recognition of the kernel all the data for the node is completed and success is returned.
The function RecogniseGeneric (3.1-1) now acquires preimages of the nice generators behind the homomorphism and appends the nice generators of the kernel. This list of generators is now the list of nice generators for the current node.
Note that with the collected data one can write arbitrary elements of the group as a straight line program in the generators as follows:
Map the element through the homomorphism.
Write the element in the image group as a product of the nice generators in the image group.
Apply the resulting straight line program to the preimages of those nice generators and calculate the quotient, which will now lie in the kernel.
Write the kernel element as a straight line program in the kernel generators.
Assemble both straight line programs to one bigger straight line program (which is now in terms of our own nice generators) and return it.
If this procedure fails in the fourth step, this indicates that our random generators for the kernel did not yet generate the full kernel and makes further recognition steps necessary. This will not happen after a successful verification phase.
The latter procedure to write elements as straight line programs in the generators is implemented in the function SLPforElementGeneric (3.3-2) which will be called automatically if one calls the SLPforElement (3.2-15) function of the resulting recognition node (see slpforelement (3.2-14)).
It is now high time to give you the calling details of the main recursive recognition function:
‣ RecogniseGeneric( H, methoddb, depthString, knowledge ) | ( function ) |
‣ RecognizeGeneric( H, methoddb, depthString, knowledge ) | ( function ) |
Returns: fail for failure or a recognition node.
H must be a GAP group object, methoddb must be a method database in the sense of Section 4.2 containing FindHomomorphism methods in the sense of Section 3.3. depthString is a string whose length measures the depth in the recognition tree. It will be increased by one character for each step we go into the tree, namely by F for a image node, and K for a kernel. The top level begins with an empty string. knowledge is an optional record the components of which are copied into the new recognition node which is created for the group H. Especially the component hints can contain a list of additional find homomorphism methods (described by records as in Section 4.2). The methods in hints and in methoddb are merged and sorted into rank-descending order. The result is passed to CallMethods (4.3-1). This feature is intended to give hints about prior knowledge about which find homomorphism method might succeed.
The function performs the algorithm described above and returns either fail in case of failure or a recognition node in case of success. For the content and definition of recognition nodes see Section 3.2.
The user will usually not call this function directly, but will use the following convenience functions:
‣ RecognisePermGroup( H ) | ( function ) |
‣ RecognizePermGroup( H ) | ( function ) |
Returns: fail for failure or a recognition node.
H must be a GAP permutation group object. This function calls RecogniseGeneric (3.1-1) with the method database used for permutation groups, which is stored in the global variable FindHomDbPerm (4.2-2), and no prior knowledge.
‣ RecogniseMatrixGroup( H ) | ( function ) |
‣ RecognizeMatrixGroup( H ) | ( function ) |
Returns: fail for failure or a recognition node.
H must be a GAP matrix group object over a finite field. This function calls RecogniseGeneric (3.1-1) with the method database used for matrix groups, which is stored in the global variable FindHomDbMatrix (4.2-3), and no prior knowledge.
‣ RecogniseProjectiveGroup( H ) | ( function ) |
‣ RecognizeProjectiveGroup( H ) | ( function ) |
Returns: fail for failure or a recognition node.
H must be a GAP matrix group object over a finite field. Since as of now no actual projective groups are implemented in the GAP library we use matrix groups instead. The recognition will however view the group as the projective group, i.e. the matrix group modulo its scalar matrices. This function calls RecogniseGeneric (3.1-1) with the method database used for projective groups, which is stored in the global variable FindHomDbProjective (4.2-4), and no prior knowledge.
‣ RecogniseGroup( H ) | ( function ) |
‣ RecognizeGroup( H ) | ( function ) |
Returns: fail for failure or a recognition node.
H must be a GAP group object. This function automatically dispatches to one of the two previous functions RecognisePermGroup (3.1-2), or RecogniseMatrixGroup (3.1-3), according to the type of the group H. Note that since currently there is no implementation of projective groups in the GAP library, one cannot recognise a matrix group H as a projective group using this function.
‣ TryFindHomMethod( H, method, projective ) | ( function ) |
Returns: fail or false or a recognition node.
Use this function to try to run a given find homomorphism method method on a group H. Indicate by the boolean projective whether or not the method works in projective mode. For permutation groups, set this to false. The result is either fail or false if the method fails or a recognition node ri. If the method created a leaf then ri will be a leaf, otherwise it will have the attribute Homom (3.2-7) set, but no image or kernel have been created or recognised yet. You can use for example the methods in FindHomMethodsPerm (4.4-1) or FindHomMethodsMatrix (4.4-2) or FindHomMethodsProjective (4.4-3) as the method argument.
GAP homomorphisms are not required to give a sensible answer when given a value not in their source, and in practice often enter the break loop, or return an incorrect answer. This causes problems when checking if a value is not in the represented group. To avoid this problem, validatehomominput (3.2-18) can be set to a function. This function is used to filter possible group elements, before they are passed to Homom (3.2-7).
A recognition node is a GAP component object. It is a member of the family
‣ RecogNodeFamily | ( family ) |
and is in the category
‣ IsRecogNode | ( category ) |
and is IsAttributeStoringRep (Reference: IsAttributeStoringRep), such that we can define attributes for it, the values of which are stored once they are known. A recognition node always represents a whole binary tree of such records, see the attributes ImageRecogNode (3.2-10) and KernelRecogNode (3.2-11) below.
Recognition nodes can be created via:
‣ RecogNode( H[, projective][, r] ) | ( operation ) |
‣ RecogNode( r, H, projective ) | ( operation ) |
Returns: a recognition node.
Create an IsRecogNode (3.2-2) object node representing the group H. The optional boolean projective defaults to false and specifies, in the case that H is a matrix group, whether H is to be interpreted as a projective group. The optional record r defaults to an empty record and is used to initialize the returned node.
For backwards-compatibility, also the order of arguments r, H, projective is accepted.
The following filters are defined for recognition nodes:
‣ IsLeaf | ( flag ) |
This flag indicates, whether or not a recognition node represents a leaf in the recognition tree. If it is not set, one finds at least one of the attributes ImageRecogNode (3.2-10) and KernelRecogNode (3.2-11) set for the corresponding node. This flag is normally reset and has to be set by a find homomorphism method to indicate a leaf.
‣ IsReady | ( flag ) |
This flag is set for a IsRecogNode (3.2-2) object node by RecogniseGeneric (3.1-1), if recognition of the subtree rooted in node finished successfully. Recognition of a node is considered successful, if two conditions hold. First, the call of CallMethods (4.3-1) for this node reports Success, that is a method from the respective method database (see Section 4.2) was successful. Secondly, the construction of the kernel generators was successful.
Thus, if the IsReady flag is set, this does not necessarily mean, that the result of the recognition procedure was verified and proven to be mathematically correct!
In particular, any computations using the datastructure set up by the recognition procedure, like Size (5.1-3) and membership testing via \in (5.1-2), will error if IsReady is not set.
The following attributes are defined for recognition nodes:
‣ Grp( ri ) | ( attribute ) |
The value of this attribute is the group that is to be recognised by this recognition node ri. This attribute is always present during recognition and after completion. Note that the generators of the group object stored here always have a memory attached to them, such that elements that are generated from them remember, how they were acquired.
‣ Homom( ri ) | ( attribute ) |
The value of this attribute is the homomorphism that was found from the group described by the recognition node ri as a GAP object. It is set by a find homomorphism method that succeeded to find a homomorphism (or isomorphism). It does not have to be set in leaf nodes of the recognition tree.
‣ NiceGens( ri ) | ( attribute ) |
The value of this attribute must be set for all nodes and contains the nice generators. The SLPforElement (3.2-15) function of the node will write its straight line program in terms of these nice generators. For leaf nodes, the find homomorphism method is responsible to set the value of NiceGens. By default, the original generators of the group at this node are taken. For a homomorphism (or isomorphism), the NiceGens will be the concatenation of preimages of the NiceGens of the image group (see pregensfac (3.2-9)) and the NiceGens of the kernel. A find homomorphism method does not have to set NiceGens if it finds a homomorphism. Note however, that such a find homomorphism method has to ensure somehow, that preimages of the NiceGens of the image group can be acquired. See calcnicegens (3.2-20), CalcNiceGens (3.2-23) and slptonice (3.2-24) for instructions.
‣ pregensfac( ri ) | ( attribute ) |
The value of this attribute is only set for homomorphism nodes. In that case it contains preimages of the nice generators in the image group. This attribute is set automatically by the generic recursive recognition function using the mechanism described with the attribute calcnicegens (3.2-20) below. A find homomorphism does not have to touch this attribute.
‣ ImageRecogNode( ri ) | ( attribute ) |
The value of this attribute is the recognition node of the image of the homomorphism that was found from the group described by the recognition node ri. It is set by the generic recursive procedure after a find homomorphism method has succeeded to find a homomorphism (or isomorphism). It does not have to be set in leaf nodes of the recognition tree. This attribute value provides the link to the image
subtree of the recognition tree.
‣ KernelRecogNode( ri ) | ( attribute ) |
The value of this attribute is the recognition node of the kernel of the homomorphism that was found from the group described by the recognition node ri. It is set by the generic recursive procedure after a find homomorphism method has succeeded to find a homomorphism (or isomorphism). It does not have to be set in leaf nodes of the recognition tree or if the homomorphism is known to be an isomorphism. In the latter case the value of the attribute is set to fail. This attribute value provides the link to the kernel
subtree of the recognition tree.
‣ ParentRecogNode( ri ) | ( attribute ) |
The value of this attribute is the recognition node of the parent of this node in the recognition tree. The top node does not have this attribute set.
‣ fhmethsel( ri ) | ( attribute ) |
The value of this attribute is the record returned by the method selection (see Section 4.3) after it ran to find a homomorphism (or isomorphism). It is there to be able to see which methods were tried until the recognition of the node was completed.
‣ slpforelement( ri ) | ( attribute ) |
After the recognition phase is completed for the node ri, we are by definition able to write arbitrary elements in the group described by this node as a straight line program (SLP) in terms of the nice generators stored in NiceGens (3.2-8). This attribute value is a function taking the node ri and a group element as its arguments and returning the above mentioned straight line program. For the case that a find homomorphism method succeeds in finding a homomorphism, the generic recursive function sets this attribute to the function SLPforElementGeneric (3.3-2) which does the job for the generic homomorphism situation. In all other cases the successful find homomorphism method has to set this attribute to a function doing the job. The find homomorphism method is free to store additional data in the recognition node or the group object such that the SLPforElement (3.2-15) function can work.
‣ SLPforElement( ri, x ) | ( function ) |
Returns: a straight line program expressing x in the nice generators.
This is a wrapper function which extracts the value of the attribute slpforelement (3.2-14) and calls that function with the arguments ri and x.
‣ StdPresentation( ri ) | ( attribute ) |
After the verification phase, the presentation is stored here. Details have still to be decided upon.
‣ methodsforimage( ri ) | ( attribute ) |
This attribute is initialised at the beginning of the recursive recognition function with the database of find homomorphism methods that was used to recognise the group corresponding to the recognition node ri. If the found homomorphism changes the representation of the group (going for example from a matrix group to a permutation group), the find homomorphism method can report this by exchanging the database of find homomorphism methods to be used in the recognition of the image of the homomorphism by setting the value of this attribute to something different. It lies in the responsibility of the find homomorphism method to do so, if the representation changes through the homomorphism.
‣ validatehomominput( ri, x ) | ( attribute ) |
The value of this attribute, if there is any, must be a function with two arguments: a recognition record ri, and an element x. The function must return a boolean. If it returns false, then this means that x is not in the source of the homomorphism returned by Homom (3.2-7). If true is returned, then either x is in the source of that homomorphism, or passing x to the homomorphism returns fail.
For example, if ri represents a matrix group that preserves a subspace, then the source of Homom (3.2-7) will be matrices which preserve that subspace, and passing matrices which do not preserve this subspace to Homom (3.2-7) may produce incorrect answers. validatehomominput can be used to filter out such elements. The function ValidateHomomInput (3.2-19) provides a simple wrapper to this attribute, which calls validatehomominput unless it is not defined, in which case ValidateHomomInput (3.2-19) returns true.
‣ ValidateHomomInput( ri, x ) | ( function ) |
Returns: a boolean.
This is a wrapper function which calls validatehomominput (3.2-18) of ri with x, or returns true if ri does not define validatehomominput (3.2-18).
The following two attributes are concerned with the relation between the original generators and the nice generators for a node. They are used to transport this information from a successful find homomorphism method up to the recursive recognition function:
‣ calcnicegens( ri ) | ( attribute ) |
To make the recursion work, we have to acquire preimages of the nice generators in image groups under the homomorphism found. But we want to keep the information, how the nice generators were found, locally at the node where they were found. This attribute solves this problem of acquiring preimages in the following way: Its value must be a function, taking the recognition node ri as first argument, and a list origgens of preimages of the original generators of the current node, and has to return corresponding preimages of the nice generators. Usually this task can be done by storing a straight line program writing the nice generators in terms of the original generators and executing this with inputs origgens. Therefore the default value of this attribute is the function CalcNiceGensGeneric (3.2-21) described below.
‣ CalcNiceGensGeneric( ri, origgens ) | ( function ) |
Returns: a list of preimages of the nice generators
This is the default function for leaf nodes for the attribute calcnicegens (3.2-20) described above. It does the following: If the value of the attribute slptonice (3.2-24) is set, then it must be a straight line program expressing the nice generators in terms of the original generators of this node. In that case, this straight line program is executed with origgens as inputs and the result is returned. Otherwise, origgens is returned as is. Therefore a leaf node just has to do nothing if the nice generators are equal to the original generators, or can simply store the right straight line program into the attribute slptonice (3.2-24) to fulfill its duties.
‣ CalcNiceGensHomNode( ri, origgens ) | ( function ) |
Returns: a list of preimages of the nice generators
This is the default function for homomorphism node for the attribute calcnicegens (3.2-20). It just delegates to image and kernel of the homomorphism, as the nice generators of a homomorphism (or isomorphism) node are just the concatenation of the preimages of the nice generators of the image with the nice generators of the kernel. A find homomorphism method finding a homomorphism or isomorphism does not have to do anything with respect to nice generators.
‣ CalcNiceGens( ri, origgens ) | ( function ) |
Returns: a list of preimages of the nice generators
This is a wrapper function which extracts the value of the attribute calcnicegens (3.2-20) and calls that function with the arguments ri and origgens.
‣ slptonice( ri ) | ( attribute ) |
As described above, the value, if set, must be a straight line program expressing the nice generators at this node in terms of the original generators. This is for leaf nodes, that choose to use the default function CalcNiceGensGeneric (3.2-21) installed in the calcnicegens (3.2-20) attribute.
The following three attributes are concerned with the administration of the kernel of a found homomorphism. Find homomorphism methods use them to report to the main recursive recognition function their knowledge about the kernel:
‣ gensN( ri ) | ( attribute ) |
The value of this mutable attribute is a list of generators of the kernel of the homomorphism found at the node ri. It is initialised as an empty list when the recursive recognition function starts. Successful find homomorphism methods may append generators of the kernel to this list if they happen to stumble on them. After successful recognition of the image of the homomorphism the main recursive recognition function will try to create a few more generators of the kernel and append them to the list which is the value of the attribute gensN. The exact behaviour depends on the value of the attribute findgensNmeth (3.2-26) below. The list of generators after that step is used to recognise the kernel. Note that the generators in gensN have a memory attached to them, how they were obtained in terms of the original generators of the current node.
‣ findgensNmeth( ri ) | ( attribute ) |
This attribute decides about how generators of the kernel of a found homomorphism are produced. Its value has to be a record with at least two components bound. The first is method which holds a function taking at least one argument ri and possibly more, and does not return anything. The second is args which holds a list of arguments for the above mentioned function. The real list of arguments is derived by prepending the recognition node to the list of arguments in args. That is, the following code is used to call the method:
gensNmeth := findgensNmeth(ri);
CallFuncList(gensNmeth.method,Concatenation([ri],gensNmeth.args));
The record is initialised upon creation of the recognition node to calling FindKernelFastNormalClosure (3.2-29) with arguments [6, 3] (in addition to the first argument ri). See below for a choice of possible find kernel methods.
‣ FindKernelRandom( ri, n ) | ( function ) |
Returns: true or false.
n random elements are generated, mapped through the homomorphism, written as a straight line program in the generators. Then the straight line program is executed with the original generators thereby producing elements in the same coset. The quotients are then elements of the kernel. The kernel elements created are stored in the attribute gensN (3.2-25). Returns false if the generation of the straight line program for some element fails.
‣ FindKernelDoNothing( ri, n1, n2 ) | ( function ) |
Returns: true.
Does nothing. This function is intended to be set as method for producing kernel elements if the kernel is known to be trivial or if one knows, that the attribute gensN (3.2-25) already contains a complete set of generators for the kernel.
‣ FindKernelFastNormalClosure( ri, n1, n2 ) | ( function ) |
Returns: true or false.
n1 random elements of the kernel are generated by calling FindKernelRandom. Then this function computes a probable generating set of the normal closure in G of the group generated by the random elements. The integer n2 indicates how hard it should try. Returns false if the call to FindKernelRandom (3.2-27) returns false.
‣ gensNslp( ri ) | ( attribute ) |
The recursive recognition function calculates a straight line program that computes the generators of the kernel stored in gensN (3.2-25) in terms of the generators of the group recognised by ri. This straight line program is stored in the value of this mutable attribute. It is used by the generic function SLPforElementGeneric (3.3-2).
‣ immediateverification( ri ) | ( attribute ) |
Sometimes a find homomorphism has information that it will be difficult to create generators for the kernel, for example if it is known that the kernel will need lots of generators. In that case this attribute with the default boolean value false can be set to true. In that case, the generic recursive recognition function will perform an immediate verification phase after the kernel has been recognised. This is done as follows: A few random elements are created, mapped through the homomorphism and written as an SLP in the nice generators there. Then this SLP is executed with preimages of those nice generators. The quotient lies then in the kernel and is written as an SLP in terms of the nice generators of the would be kernel. If this is not possible, then probably the creation of kernel generators was not complete and a few more kernel elements are produced and recognition in the kernel starts all over again. This is for example done in case of the Imprimitive
method which maps onto the action on a block system. In that case, the kernel often needs lots of generators.
The following attributes are used to give a successful find homomorphism method further possibilities to transport knowledge about the group recognised by the current recognition node to the image or kernel of the found homomorphism:
‣ InitialDataForKernelRecogNode( ri ) | ( attribute ) |
This attribute is initialised to a record with only the component hints bound to an empty list at the beginning of the recursive recognition function. Find homomorphism methods can put acquired knowledge about the group to be recognised (like for example an invariant subspace of a matrix group) into this record. When a homomorphism is found and recognition goes on in its kernel, the value of this attribute is taken as initialisation data for the newly created recognition node for the kernel. Thus, information is transported down to the recognition process for the kernel. The component hints is special insofar as it has to contain records describing find homomorphism methods which might be particularly successful. They are prepended to the find homomorphism method database such that they are called before any other methods. This is a means to give hints to the recognition procedure in the kernel, because often during the finding of a homomorphism knowledge is acquired which might help the recognition of the kernel.
‣ InitialDataForImageRecogNode( ri ) | ( attribute ) |
This attribute is initialised to a record with only the component hints bound to an empty list at the beginning of the recursive recognition function. Find homomorphism methods can put acquired knowledge about the group to be recognised (like for example an invariant subspace of a matrix group) into this record. When a homomorphism is found and recognition goes on in its image, the value of this attribute is taken as initialisation data for the newly created recognition node for the image. Thus, information is transported down to the recognition process for the image. The component hints is special insofar as it has to contain records describing find homomorphism methods which might be particularly successful. They are prepended to the find homomorphism method database such that they are called before any other methods. This is a means to give hints to the recognition procedure in the image, because often during the finding of a homomorphism knowledge is acquired which might help the recognition of the image.
‣ isone( ri ) | ( attribute ) |
This attribute returns a function that tests, whether or not an element of the group is equal to the identity or not. Usually this is just the operation IsOne (Reference: IsOne) but for projective groups it is a special function returning true for scalar matrices. In generic code, one should always use the result of this attribute to compare an element to the identity such that the code works also for projective groups. Find homomorphism methods usually do not have to set this attribute.
‣ isequal( ri ) | ( attribute ) |
This attribute returns a function that compares two elements of the group being recognised. Usually this is just the operation EQ (Reference: equality of records) but for projective groups it is a special function checking for equality up to a scalar factor. In generic code, one should always use the result of this attribute to compare two elements such that the code works also for projective groups. Find homomorphism methods usually do not have to set this attribute.
‣ OrderFunc( ri ) | ( attribute ) |
This attribute returns a function that computes the order of an element of the group being recognised. Usually this is just the operation Order (Reference: Order) but for projective groups it is a special function. In generic code, one should always use the result of this attribute to compute the order of an element such that the code works also for projective groups. Find homomorphism methods usually do not have to set this attribute.
In this subsection we describe a few more components of recognition nodes that can be queried or set by find homomorphism methods. Not all of these components are bound in all cases. See the individual descriptions about the conventions. Remember to use the !. notation to access these components of a recognition node.
leavegensNuntouchedIf this component is bound to true by a find homomorphism method or a find kernel generators method, the generic mechanism to remove duplicates and identities in the generator for the kernel is not used. This is important if your methods rely on the generating set of the kernel being exactly as it was when found.
A find homomorphism method
has the objective to, given a group \(G\), either find a homomorphism from \(G\) onto a group, or to find an isomorphism, or to solve the constructive membership problem directly for \(G\), or to fail.
In case a homomorphism is found, it has to report that homomorphism back to the calling recursive recognition function together with as much information about the kernel as possible.
If a find homomorphism method determines that the node is a leaf in the recognition tree (by solving the constructive membership problem directly), then it has to ensure, that arbitrary elements can be written in terms of the nice generators of \(G\). It does so by returning a function together with possible extra data, that can perform this job.
Of course, the find homomorphism method also has to report, how the nice generators were acquired in terms of the original generators.
If the find homomorphism method fails, it has to report, whether it has failed forever or if it possibly makes sense to try to call this method again later.
Find homomorphism methods have to fit into the framework for method selection described in Chapter 4. We now begin to describe the technical details of how a find homomorphism method has to look like and what it has to do and what it is not allowed to do. We first explain the calling convention by means of a hypothetical function:
‣ FindHomomorphism( ri, G ) | ( function ) |
Returns: One of the values Success, NeverApplicable, TemporaryFailure, or NotEnoughInformation.
Find homomorphism methods take two arguments ri and G, of which ri is a recognition node and G is a GAP group object. The return value is one of the four possible values in the framework for method selection described in Chapter 4 indicating success, failure, or (temporary) non-applicability. The above mentioned additional information in case of success are all returned by changing the recognition node ri. For the conventions about what a find homomorphism method has to do and return see below.
A failed or not applicable find homomorphism method does not have to report or do anything in the recognition node ri. However, it can collect information and store it either in the group object or in the recognition node. Note that for example it might be that a failed find homomorphism method acquires additional information that allows another find homomorphism method to become applicable.
A not applicable find homomorphism method should find out so relatively quickly, because otherwise the whole process might be slowed down, because a find homomorphism method repeatedly ponders about its applicability. Usually no big calculations should be triggered just to decide applicability.
A successful find homomorphism method has the following duties:
First it has to report whether the current node is a leaf or not in the recognition tree. That is, in case a leaf was found the method has to do SetFilterObj(ri,IsLeaf); thereby setting the IsLeaf (3.2-4) flag.
A method finding a homomorphism which is not an isomorphism indicates so by not touching the flags. FIXME: What does that mean? Which flags? The IsLeaf filter? But then this sounds as if isomorphisms require settings some flag.. but which?!? perhaps remove that sentence?
SLPforElement (3.2-15) functionIf a find homomorphism method has produced a leaf in the recognition tree, then it has to set the attribute slpforelement (3.2-14) to a function like SLPforElementGeneric (3.3-2) that can write an arbitrary element in G as a straight line program in the nice generators of G. The method may store additional data into the recognition node for this to work. It does not have to set any other value in ri.
If a find homomorphism method has produced a leaf in the recognition tree, then it has to report what are the nice generators of the group described by the leaf. To this end, it has three possibilities: Firstly to do nothing, which means, that the original generators are the nice generators. Secondly to store a straight line program expressing the nice generators in terms of the original generators into the attribute slptonice (3.2-24). In that case, the generic frame work takes care of the rest. The third possibility is to store a function into the value of the attribute calcnicegens (3.2-20) which can calculate preimages of the nice generators in terms of preimages of the original generators. See the function CalcNiceGensGeneric (3.2-21) for an example of such a function.
If a find homomorphism method has found a homomorphism, it has to store it as a GAP homomorphism object from G to the image group in the attribute Homom (3.2-7). Note that if your homomorphism changes the representation (for example going from matrix groups to permutation groups), you will have to set the attribute methodsforimage (3.2-17) accordingly. Also, ValidateHomomInput (3.2-19) may be set to a function which returns false for values which may cause Homom (3.2-7) to produce the wrong answer, or error.
If a find homomorphism method has found a homomorphism, it has to provide information about already known generators of the kernel. This is done firstly by appending known generators of the kernel to the attribute value of gensN (3.2-25) and secondly by leaving or changing the attribute findgensNmeth (3.2-26) to a record describing the method that should be used (for details see findgensNmeth (3.2-26)). If one does not change the default value, the recursive recognition function will generate 20 (FIXME: is 20 correct?) random elements in G and produce random generators of the kernel by dividing by a preimage of an image under the homomorphism. Note that generators in gensN (3.2-25) have to have a memory attached to them that stores, how they were acquired from the generators of G.
A find homomorphism method may store any data into the attributes InitialDataForKernelRecogNode (3.2-32) and InitialDataForImageRecogNode (3.2-33), which both are records. Components in these record that are bound during the recognition will be copied into the recognition node of the kernel and image respectively of a found homomorphism upon creation and thus are available to all find homomorphism methods called for the kernel and image. This feature might be interesting to transport information that is relevant for the recognition of the kernel or image and was acquired during the recognition of G itself.
A special role is played by the component hints in both of the above records, which can hold a list of records describing find homomorphism methods that shall be tried first when recognising the kernel or image.
In addition, a find homomorphism method might set the attribute immediateverification (3.2-31) to true, if it considers the problem of finding kernel generators particularly difficult.
To explain the calling conventions for SLPforElement (3.2-15) functions and for the sake of completeness we present now the function SLPforElementGeneric (3.3-2) which is used for the case of a homomorphism node
:
‣ SLPforElementGeneric( ri, x ) | ( function ) |
Returns: A GAP straight line program.
This function takes as arguments a recognition node ri and a group element x. It returns a GAP straight line program that expresses the element x in terms of the nice generators of the group \(G\) recognised by ri.
This generic function here does exactly this job for the generic situation that we found a homomorphism from \(G\) to some other group say \(H\) with kernel \(N\). It first maps x via the homomorphism to \(H\) and uses the recognition information there to write it as a straight line program in terms of the nice generators of \(H\). Then it applies this straight line program to the preimages of those nice generators (see pregensfac (3.2-9)) thereby finding an element \(y\) of \(G\) with \(x \cdot y^{-1}\) lying in the kernel \(N\).
Then the function writes this element as a straight line program in the nice generators of \(N\) again using the recursively acquired recognition info about \(N\). In the end a concatenated straight line program for \(x\) is built, which is in terms of the nice generators of the current node.
generated by GAPDoc2HTML