An Annoying Open Problem
How do we tell if two groups are isomorphic?
Vikraman Arvind and Jacobo Torán are both complexity theorists, both with wide interests, but both who have worked extensively on the graph isomorphism problem. See their survey here, for example.
Today I want to talk about about an open problem, and their paper on the problem, which makes some progress. But the problem is still open—I find this an embarrassment—we should be able to solve this problem.
The problem is: Given two groups defined by tables, are they isomorphic? This is the – problem. What is annoyingly open is whether this problem belongs to , or alternatively, whether it is equivalent to Graph Isomorphism.
A Cayley table, after the 19th century British mathematician Arthur Cayley, is just the table of the multiplication function
There are many ways to represent a finite group. The above is natural: just give the multiplication table. There are many others: we could give the group as a “black box,” as a set of generators and relationships, or as a set of matrices. It should be clear that the easiest representation to deal with must be Cayley tables. Many questions that are hard in other representations are easy, even simple, in this representation. Note that this representation is larger than the size of the group itself, basically its square. The other representations, by contrast, are more succinct.
The precise definition of the – problem is: given two tables that define the groups and , are they isomorphic? That is, is there a bijective mapping from the elements of to the elements of , say , so that for all in :
This is a fancy way of saying that except for the names of the elements the groups are the same.
The Short History
I find this problem very annoying. I have spent uncountable hours working on this over the last decades, especially jointly with Zeke Zalcstein. One reason the problem is so annoying is that it is easy to prove that it can be reduced to Graph Isomorphism (). But surely the additional structure of groups must help make the problem much easier to solve. Here are some encouraging differences between groups and graphs:
- Every subset of elements of a graph is a graph; only certain subsets of elements of a group form a group.
- Groups have a tight structure that varies with the prime factorization of , the number of elements. For instance, if is a prime there is exactly one group—the cyclic group .
- Groups always have automorphisms, provided . Graphs can have many automorphisms—for instance the complete graph has —or they can have as little as no nontrivial automorphisms.
- I could go on and on with the many structural differences.
Yet for all these differences, the best Zeke and I could do was prove, in 1976, that – can be solved in space . Bob Tarjan independently noticed at the same time that it could be done in time. Both results are really the same: they both exploit the fact that a group of elements always has a generating set of size . This is a direct consequence of Lagrange’s Theorem, as follows:
Let be a group with elements. Let the trivial group that contains only the identity element of . If is all of , then stop and we have found generators. If is not add any element of that is not in . By Lagrange’s Theorem this must have at least twice as many elements as : call it . The last point is key: let have elements and have elements. Clearly . But , which implies that .
One of the success stories of complexity theory, and potentially a great story, is its application to solve the – question—almost. The well-known Merlin-Arthur protocol for graph isomorphism works also for group isomorphism—see here and here for details.
What Arvind and Torán prove is that at least for a large class of groups, namely the solvable groups, the – problem is almost in . Namely, there is an -machine for the complement of this language that works correctly on all but a quasi-polynomial number of inputs of length . This may not sound very impressive, but it is. By the famous Feit-Thompson theorem, all groups of odd order are solvable. Note that solvable groups play an important role in others ways in complexity theory, which I have discussed a number of times before.
What they actually first show is that the complementary task, ––, has an Arthur-Merlin protocol in which Arthur uses only random bits and Merlin uses only nondeterminism. This makes various kinds of de-randomization easier to apply. The existence of a language in that is bi-immune to polynomial space, i.e. the assumption , suffices to de-randomize this completely and thus put – into .
The Group Approach
Recall that groups come in various types: there are simpsle groups, there are solvable groups, there are abelian groups, and more. One type of groups that are very important are called –groups. A group is a -group if the order of the group—the number of elements in the group—is where is a prime and . Every such group is solvable.
One of the outstanding issues in group theory is that there is no general structure theorem for -groups. They are very complex, and even understanding the structure of all such groups of size for modest values of is non-trivial.
The groups of order for were classified early in the history of group theory, and modern work has extended these classifications to groups whose order divides . According to our friends at Wikepedia–see here:
the sheer number of families of such groups grows so quickly that further classifications along these lines are judged difficult for the human mind to comprehend.
The number of different, non-isomorphic, -groups is exponential:
As a complexity theorist I would disagree a bit with the idea that many implies hard to understand. There are many boolean strings of length , but they are not that hard to understand in some sense. What makes -groups hard, is that they can have complex structure, and we do not understand it, at all.
Zeke and I worked hard trying to understand these groups enough so that we could get a better isomorphism algorithm. We never made any progress. I would be excited if we could even prove there is an algorithm that runs in
Please solve the – problem. Or at least break below the time, which is the best known now for decades. Can you prove
for some ? Good hunting.