GAP:OneIsomorphismCheck

This article is about a GAP function.

This GAP function outputs a Boolean variable, i.e., it returns either true or false. View other GAP functions with Boolean output

Definition

Function type

This function takes as input a pair of groups, typically both finite groups.

Behavior

The function returns true if the two groups are 1-isomorphic groups and in particular 1-isomorphic finite groups(i.e., there is a 1-isomorphism between them) and false otherwise.

Packages used

The function depends on the Grape package, which has graph capabilities.

Related functions

• DirectedPowerGraph
• UndirectedPowerGraph
• OneIsomorphicToGroup

Method

Idea

The key idea is to use the fact that for finite groups, there are multiple equivalent definitions of 1-isomorphic. In particular:

• finite groups are 1-isomorphic iff their directed power graphs are isomorphic
• undirected power graph determines directed power graph for finite group

Thus, to test 1-isomorphism, we can construct the directed power graphs of both groups, and check for isomorphism. Equivalently we can construct the undirected power graphs for both groups, and check for isomorphism.

Since the construction of the directed power graph and testing for graph isomorphism can take some time, we can speed up the process of rejection by first checking whether some basic element information, such as the orders of the groups, the order statistics of the groups, power statistics of the groups, and order-cum-power statistics of the groups match.

Code

Note that all versions require the Grape package.

Version that tests using undirected power graphs alone, along with the defining code for undirected power graphs:

UndirectedPowerGraph := function(G)
        local L,o,f;
        o := Order(G);
        L := AsList(Set(G));
        f := function(x,y)
                return(IsSubgroup(Group(L[x]),Group(L[y])) or IsSubgroup(Group(L[y]),Group(L[x])));
        end;;
        return(Graph(TrivialSubgroup(SymmetricGroup(o)),[1..o],OnPoints,f,true));
end;;

OneIsomorphismCheck := function(G,H)
        return(not(GraphIsomorphism(UndirectedPowerGraph(G),UndirectedPowerGraph(H)) = fail));
end;;

Version that tests using directed power graphs alone, along with the defining code for directed power graphs:

DirectedPowerGraph := function(G)
        local L,o,f;
        o := Order(G);
        L := AsList(Set(G));
        f := function(x,y)
                return(IsSubgroup(Group(L[x]),Group(L[y])));
        end;;
        return(Graph(TrivialSubgroup(SymmetricGroup(o)),[1..o],OnPoints,f,true));
end;;

OneIsomorphismCheck := function(G,H)
        return(not(GraphIsomorphism(DirectedPowerGraph(G),DirectedPowerGraph(H)) = fail));
end;;

Version that tests using directed power graphs, but with preliminary testing for order and order statistics. The function OrderStatistics is also defined, since that's used as one of the preliminary tests:

DirectedPowerGraph := function(G)
        local L,o,f;
        o := Order(G);
        L := AsList(Set(G));
        f := function(x,y)
                return(IsSubgroup(Group(L[x]),Group(L[y])));
        end;;
        return(Graph(TrivialSubgroup(SymmetricGroup(o)),[1..o],OnPoints,f,true));
end;;

OrderStatistics := function(G)
        local L,D;
        L := List(Set(G),Order);
        D := DivisorsInt(Order(G));
        return(List(D,x->Length(Filtered(L,y->x=y))));
end;;

OneIsomorphismCheck := function(G,H)
        if (not(Order(G) = Order(H))) then Print("Orders do not match\n"); return false;fi;
        if (not(OrderStatistics(G) = OrderStatistics(H))) then Print("Order statistics do not match\n"); return false; fi;
        return(not(GraphIsomorphism(DirectedPowerGraph(G),DirectedPowerGraph(H)) = fail));
end;;

Version that tests using order-cum-power statistics and order-cum-root statistics:

DirectedPowerGraph := function(G)
        local L,o,f;
        o := Order(G);
        L := AsList(Set(G));
        f := function(x,y)
                return(IsSubgroup(Group(L[x]),Group(L[y])));
        end;;
        return(Graph(TrivialSubgroup(SymmetricGroup(o)),[1..o],OnPoints,f,true));
end;;

OrderStatistics := function(G)
        local L,D;
        L := List(Set(G),Order);
        D := DivisorsInt(Order(G));
        return(List(D,x->Length(Filtered(L,y->x=y))));
end;;

OrderCumPowerStatistics := function(G)
        local L,D,E;
        D := DivisorsInt(Order(G));
        L := List(D,a -> Set(List(Set(G),g -> g^a)));
        return(List(L,A -> List(D,x->Length(Filtered(A,g -> Order(g) = x)))));
end;;

OrderCumRootStatistics := function(G)
        local D;
        D := DivisorsInt(Order(G));
        return(SortedList(List(Set(G),x -> [Order(x),List(D,d -> Length((Filtered(Set(G),y->y^d = x))))])));
end;;

OneIsomorphismCheck := function(G,H)
        if (not(Order(G) = Order(H))) then Print("Orders do not match\n"); return false;fi;
        if (not(OrderStatistics(G) = OrderStatistics(H))) then Print("Order statistics do not match\n"); return false; fi;
        if (not(OrderCumPowerStatistics(G) = OrderCumPowerStatistics(H))) then Print("Order-cum-power statistics do not match\n"); return false; fi;
        if (not(OrderCumRootStatistics(G) = OrderCumRootStatistics(H))) then Print("Order-cum-root statistics do not match\n"); return false; fi;
        return(not(GraphIsomorphism(DirectedPowerGraph(G),DirectedPowerGraph(H)) = fail));
end;;