Finding Isomorphisms Between Finite Groups
November 23, 2012
One of the most interesting problems I came across as I was building my Abstract Algebra package was that of finding an isomorphism between two finite groups G and H, represented by their Cayley tables, or proving that G and H aren't isomorphic. Before reading further, give it a little thought--how would you do it?
The naive algorithm, of course, is to look at all bijections between the elements of G and H, and check whether each bijection is a group isomorphism. If |G| = |H| = n, then this runs in worst case O(n! * n^2) = O((n+2)!), since there are n! possible bijections and checking whether a bijection f is a group isomorphism takes O(n^2) time, (because you need to check whether f(g * g') = f(g) * f(g') for all elements g and g' in G). This is obviously a terrible algorithm--if the groups are not isomorphic, you'll need to check all n! bijections, and if they are isomorphic, you have no guarantee that you'll find an isomorphism quickly.
A smarter algorithm, attributed to Robert Tarjan, is to find a set of generators of G, attempt to match those generators with elements of H, and then see if the matching induces an isomorphism. In pseudocode, this algorithm is:
find a set of generators G' = {g_1, ... , g_p} of G.
for every subset H' of H with size |H'| == |G'|:
for every bijection f': G' -> H':
/* See if f' extends to an isomorphism f */
define f: G -> H by, for any g = g_1^(k_1) * ... * g_p^(k_p) in G,
f(g) = f'(g_1)^(k_1) * ... * f'(g_p)^(k_p)
if f is an isomorphism:
return f
return None
My python implementation of this algorithm can be found here.
The key reason that this algorithm runs quickly is that every group G has an easily computable generator set of size at most log_2(n). This is due to Lagrange's theorem, which implies that the order of every subgroup of G must divide the order of G. Thus, if {g_1, ... , g_k} generate a proper subgroup G' of G, then if g_(k+1) is not if G', the subgroup generated by {g_1, ... , g_k, g_(k+1)} must have order at least twice as large as the order of G'. So the following algorithm, which I implemented here, returns a set of generators of G of size at most log_2(|G|) for non-trivial groups:
pick g in G that isn't the identity, and set S = {g}
while <S> != G:
pick g in G \ <S>, and add g to S
return S
Armed with a generator set of size at most log_2(n), we need only examine at most n * (n-1) * ... * (n - log_2(n) + 1) = O(n^(log_2(n))) bijections f'. Since finding a generating set as above and checking whether f' extends to an isomorphism f both take only polynomial time, (with constants depending on your cleverness!), Tarjan's algorithm runs in O(n^(log_2(n) + O(1))), a substantial improvement over O((n+2)!).
In practice, the algorithm can run even faster, because the generating set found above may be smaller than the worst case size of log_2(n). If, for example, the group is a cyclic group of prime order, then the generating set will have only one element in it. Thus, the algorithm's actual speed depends on the complexity of groups it's applied to. As another example, checking that the dihedral and symmetric groups of order 120 are not isomorphic takes about 34 seconds with my code on my machine, (as below), even though 120^log_2(120) is about 230 trillion. And more careful implementations of the above algorithms would cut that time down by much, much more.
>>> from absalg import *
>>> from timeit import timeit
>>> S5 = Sn(5); D60 = Dn(60)
>>> timeit("D60.is_isomorphic(S5)", "from __main__ import D60, S5", number=1)
34.25785708427429
