10
$\begingroup$

Let $G,H$ be two Groups. How to check with GAP whether they are isomorphic or not?

For example, GAP has IsNilpotentGroup to check whether the group $G$ is nilpotent. Is there a similar function named like AreIsomorphicGroups to check whether $G$ and $H$ are isomorphic or not?

$\endgroup$
6
  • 3
    $\begingroup$ Look for the function IsomorphismGroups in GAP's reference manual. But also have a look at this. $\endgroup$ Mar 27, 2016 at 7:47
  • $\begingroup$ The question is not clearly formulated. Are you looking for a command to check isomorphism or to the code of the function which does this? Assuming the former, follow the link to IsomorphismGroup given by @Jean-ClaudeArbaut and observe two other functions suggested in its documentation. It also matters whether do you want to check that the groups are isomorphic or not, or do you need to find a particular isomorphism. $\endgroup$ Mar 27, 2016 at 12:29
  • $\begingroup$ @AlexanderKonovalov: I want a program for this do you want to check that the groups are isomorphic or not? For Example this program there exists for check nilpotentcy of group $G$, " gap> IsNilpotentGroup<G>;" . Do there same program for to check isimorphism between two Groups? $\endgroup$
    – A.G
    Mar 27, 2016 at 12:51
  • 1
    $\begingroup$ IsomorphismGroups returns the actual isomorphism or fail if the groups are not isomorphic. For small groups, you can just calculate IdGroup for both and check that they are equal - that's why IdGroup is mentioned in the manual section for IsomorphismGroups. $\endgroup$ Mar 27, 2016 at 13:12
  • 2
    $\begingroup$ @A.G: if IsomorphismGroups(G,H) <> fail then ... or (after checking that the order of the group is <2000 and not 1024) checking that IdGroup(G)=IdGroup(H) $\endgroup$ Mar 27, 2016 at 13:38

1 Answer 1

18
$\begingroup$

There are two aspects here: how to search such information in GAP, and how to actually check the isomorphism of two groups.

First, the OP was quite close to guessing the name of the function, since most of the documented GAP functions follow these naming conventions. Functions that return true or false usually have the name of the form IsSomething (even in the cases when AreSomething could make sense). So one could expect that GAP has something named like IsIsomorph....

Making such a guess, one could now use the help system to find all help entries starting with IsIsom. To do this, enter ?IsIsom in GAP (one could also try ??IsIsom to find all entries containing a substring IsIsom). This will produce a list of entries, and those which are relevant are

ANUPQ (not loaded): IsIsomorphicPGroup                                                

and

SONATA (not loaded): IsIsomorphicGroup                                                

(this also demonstrates a very useful feature of the help system - searching in the manuals of packages even when they are not loaded).

Now in more details about the actual isomorphism check. If one would open the documentation of SONATA's IsIsomorphicGroup, that would lead to the GAP function IsomorphismGroups which constructs and returns the actual isomorphism, if it is possible, or returns fail if the groups are non-isomorphic (see here). For example:

gap> G:=DihedralGroup(8);
<pc group of size 8 with 3 generators>
gap> H:=Group( (1,5)(2,3)(4,8)(6,7), (1,2)(3,8)(4,6)(5,7) );
Group([ (1,5)(2,3)(4,8)(6,7), (1,2)(3,8)(4,6)(5,7) ])
gap> IsomorphismGroups(H,G);
[ (1,5)(2,3)(4,8)(6,7), (1,2)(3,8)(4,6)(5,7) ] -> [ f1*f3, f1*f2 ]
gap> T:=Group([ (1,7,4,3)(2,8,6,5), (1,4)(2,6)(3,7)(5,8) ]);
Group([ (1,7,4,3)(2,8,6,5), (1,4)(2,6)(3,7)(5,8) ])
gap> IsomorphismGroups(T,G);
fail

One could inspect the source code of this function entering

PageSource(IsomorphismGroups);

to see that before attempting to construct the isomorphism it does some checks of necessary conditions and will immediately return fail if e.g. the groups have different orders or different number of conjugacy classes. Also, for groups of the order that allows identification of the group in the GAP Small Groups Library (see IdGroup here) it checks that both groups have the same ID and returns fail if not.

This may be useful if one is only interested whether two groups are isomorphic, but not interested in the actual homomorphism: in this case G and H are isomorphic if and only if IdGroup(G)=IdGroup(H). In the example above, we have:

gap> IdGroup(G);
[ 8, 3 ]
gap> IdGroup(H);
[ 8, 3 ]
gap> IdGroup(T);
[ 4, 1 ]

Identification using IdGroup is possible for all orders in the library except for the orders $512$ and $1536$ and except for the orders $p^5$, $p^6$ and $p^7$ above $2000$ (see here). Also note that ANUPQ package has an undocumented function IdStandardPresented512Group which provides identification for groups of order 512.

This approach is used by the SONATA package which provides a function IsIsomorphicGroup (see here) which returns true or false dependently on whether the two groups are isomorphic or not:

gap> LoadPackage("sonata");
true
gap> IsIsomorphicGroup(G,H);
true
gap> IsIsomorphicGroup(G,T);
false

To inspect the code of IsIsomorphicGroup, first call LoadPackage("sonata"); and then enter

PageSource(ApplicableMethod(IsIsomorphicGroup,[Group((1,2)),Group((2,3))]));

Then one could also see that this checks some necessary conditions before doing actual work in the generic method which just checks that IsomorphismGroups( G, H ) <> fail. These necessary conditions could work fast for small groups but not work very efficiently for very large ones (e.g. comparing the number of elements of each order), so this should be used with care.

In case of a $p$-group, the ANUPQ package (requires compilation, not available in the GAP distribution for Windows) provides the function IsIsomorphicPGroup (see here) which is applicable only to groups of prime power order and may be more efficient in this case. See more details about the algorithm it uses here.

For very large groups, checking whether they are isomorphic or not may be quite time-consuming. One could try to calculate some other invariants to try to show that they are different, and/or try to find better representation of the group (e.g. convert a group given by generators and relators to a permutation group) so that GAP will operate with it faster. In case of any challenging examples, I suggest to post them in separate questions.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .