Skip to content

An Annoying Open Problem

October 8, 2011
tags: , , , , , , ,
by


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 {\mathsf{GROUP}}–{\mathsf{ISO}} problem. What is annoyingly open is whether this problem belongs to {\mathsf{P}}, 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

\displaystyle (x,y) \rightarrow x \circ y.

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 Problem

The precise definition of the {\mathsf{GROUP}}–{\mathsf{ISO}} problem is: given two tables that define the groups {G} and {H}, are they isomorphic? That is, is there a bijective mapping from the elements of {G} to the elements of {H}, say {\pi}, so that for all {x,y} in {G}:

\displaystyle \pi(x \circ y) = \pi(x) \circ \pi(y).

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 ({\mathsf{GI}}). 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 {n}, the number of elements. For instance, if {n} is a prime there is exactly one group—the cyclic group {\mathbb{Z}_{p}}.
  • Groups always have automorphisms, provided {n>2}. Graphs can have many automorphisms—for instance the complete graph has {n!}—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 {\mathsf{GROUP}}–{\mathsf{ISO}} can be solved in space {O(\log^{2} n)}. Bob Tarjan independently noticed at the same time that it could be done in {n^{\log n +O(1)}} time. Both results are really the same: they both exploit the fact that a group of {n} elements always has a generating set of size {\log_2 n}. This is a direct consequence of Lagrange’s Theorem, as follows:

Let {G} be a group with {n} elements. Let {H_{1}} the trivial group that contains only the identity element of {G}. If {H_{k}} is all of {G}, then stop and we have found {k} generators. If {H_{k}} is not {G} add any element of {G} that is not in {H_{k}}. By Lagrange’s Theorem this must have at least twice as many elements as {H_{k}}: call it {H_{k+1}}. The last point is key: let {H_{k}} have {\ell} elements and {H_{k+1}} have {m} elements. Clearly {m \ge l+1}. But {\ell | m}, which implies that {m \ge 2\ell}.

Complexity Approach

One of the success stories of complexity theory, and potentially a great story, is its application to solve the {\mathsf{GROUP}}–{\mathsf{ISO}} 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 {\mathsf{GROUP}}–{\mathsf{ISO}} problem is almost in {\mathsf{NP} \cap \mathsf{coNP}}. Namely, there is an {\mathsf{NP}}-machine for the complement of this language that works correctly on all but a quasi-polynomial number of inputs of length {n}. 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, {\mathsf{GROUP}}–{\mathsf{NON}}–{\mathsf{ISO}}, has an Arthur-Merlin protocol in which Arthur uses only {O(\log^6 n)} random bits and Merlin uses only {O(\log^2 n)} nondeterminism. This makes various kinds of de-randomization easier to apply. The existence of a language in {\mathsf{EXP}} that is bi-immune to polynomial space, i.e. the assumption {\mathsf{EXP}\not\subseteq\mathsf{i.o.}\mbox{-}\mathsf{PSPACE}}, suffices to de-randomize this completely and thus put {\mathsf{GROUP}}–{\mathsf{ISO}} into {\mathsf{NP} \cap \mathsf{coNP}}.

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 {p}–groups. A group {G} is a {p}-group if the order of the group—the number of elements in the group—is {p^m} where {p} is a prime and {m \ge 1}. Every such group is solvable.

One of the outstanding issues in group theory is that there is no general structure theorem for {p}-groups. They are very complex, and even understanding the structure of all such groups of size {p^{n}} for modest values of {n} is non-trivial.

The groups of order {p^n} for {0 \le n \le 4} were classified early in the history of group theory, and modern work has extended these classifications to groups whose order divides {p^{7}}. According to our friends at Wikepedia–see here:

{\dots} 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, {p}-groups is exponential:

\displaystyle p^{\frac{2}{27}n^3 +O(n^{8/3})}.

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 {n}, but they are not that hard to understand in some sense. What makes {p}-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

\displaystyle n^{1/2 \log n + O(1)}

for {p}-groups.

Open Problems

Please solve the {\mathsf{GROUP}}–{\mathsf{ISO}} problem. Or at least break below the {n^{\log n +O(1)}} time, which is the best known now for decades. Can you prove

\displaystyle n^{\alpha \log n + O(1)},

for some {\alpha <1}? Good hunting.

from → P=NP, People, Proofs
32 Comments leave one →
  1. Anonymous permalink
    October 8, 2011 10:07 am

    How about a simpler definition of the problem to enable people which are not mathematically lyric to solve the problem?

    greetings

    Reply
  2. ohwowk permalink
    October 8, 2011 10:47 am

    > This is a fancy way of saying that except for the names of the elements the groups are the same.

    I am not in a position to argue, but isn’t it true only if the group operation (multiplication in your example) are the same?

    Reply
    • Javaid Aslam permalink
      October 11, 2011 2:37 pm

      Yes– it follows from the mapping (pi).

      Reply
  3. Noah Snyder permalink
    October 8, 2011 11:20 am

    It might be possible to make precise the idea that it’s not the vast number of p-groups that makes the problem hard. A result of Sims (based on earlier work of Higman) shows that most p-groups are of a very specific form (3-step nilpotent). If you had an algorithm that distinguished these 3-step nilpotent p-groups from each other, then that would make it clear that it’s not the vast number that’s the problem.

    (In fact, the same sort of result saying that the generic situation is 3-step nilpotent holds for several different algebraic structures, see the beginning of Section 10 of this paper of Bjorn Poonen’s, which is also where I heard about the Sims-Higman result.)

    Reply
  4. Douglas permalink
    October 8, 2011 11:55 am

    I was enjoying this post until I got to the end and saw this annoying advert: imgur.com/mb8aX

    Reply
  5. David Locke permalink
    October 8, 2011 12:10 pm

    This problem seems like an ideal candidate for a polymath project. The problem is both easy to describe and easy to understand.

    Reply
    • gowers permalink
      October 11, 2011 8:13 am

      Interesting idea. My current view about polymath projects is that whether or not they actually solve the problems they set out to solve, they almost automatically lead very quickly to an incredibly thorough understanding of those problems. This question is, as you say, very easy to state, so it is highly plausible that a polymathematical conversation would at least get quickly to the heart of the difficulty.

      Reply
      • rjlipton permalink*
        October 11, 2011 6:10 pm

        Tim Gowers,

        I agree. Perhaps we should discuss doing this.

  6. Scottie Barbarossa permalink
    October 8, 2011 3:11 pm

    Is graph isomorphism known to be in P or not in P?

    Reply
    • rjlipton permalink*
      October 9, 2011 8:40 am

      Scottie Barbarossa,

      Sorry. It is open. The best result is that bounded degree graphs are in P. But the general case is wide open.

      Reply
  7. Javaid Aslam permalink
    October 10, 2011 12:55 pm

    Prof. Lipton,
    It might help if you could provide an example or two for two non-isomorphic groups.
    Thanks,

    Reply
    • anonymous permalink
      October 10, 2011 5:51 pm

      See http://en.wikipedia.org/wiki/List_of_small_groups

      Two non-isomorphic groups are e.g.
      the cyclic group of order 4, Z_4, and the Klein four-group, V_4,
      they have the following multiplication tables.

      Z_4 = [[1,a,b,c],[a,b,c,1],[b,c,1,a],[c,1,a,b]]
      V_4 = [[1,a,b,c],[a,1,c,b],[b,c,1,a],[c,b,a,1]]

      Reply
  8. Javaid Aslam permalink
    October 11, 2011 12:28 pm

    You might call this a far fetched hunch…

    There is possibility that there might be common paradigm (or a theory) that is holding the secret to the solution of such seemingly easy as well as NP-hard problems including #P-complete problems (of course in P-time).

    Reply
  9. Joey permalink
    October 13, 2011 5:11 am

    Nice post. By gradually stripping off the group axioms, is there a known point at which the problem becomes equivalent to graph isomorphism? For instance, what if we consider semigroup isomorphism? What is known about algebra isomorphism (for general algebras, with operations presented as tables) in general?

    Reply
  10. Leonid permalink
    October 15, 2011 2:57 pm

    Hi,
    sorry for asking such a probably naive question but:

    We are limiting the problem to finite groups, are we?
    warmest regards
    Leo

    PS: Thanks for the great post, which is understandable for a beginning maths student as myself, and still stays as interesing.

    Reply
    • rjlipton permalink*
      October 15, 2011 4:58 pm

      Lenoid

      Yes this is for finite groups

      Reply
  11. anonymous permalink
    November 2, 2011 2:51 pm

    Please excuse my naivete, but knowing whether two permutation groups are isomorphic is known to be in P, is it not? By constructing a strong generating set for the two permutation groups in question, then making sure that each generator in the first can be written in terms of the second’s and vice verse?

    Am I mistaken in thinking this would imply isomorphism? Why doesn’t this apply to the Cayley table representation?

    Reply
    • rjlipton permalink*
      November 2, 2011 8:11 pm

      No. That is not know to be in P to my knowledge. Groups can have many different generator sets. So you would have to cycle through all possible ones to be sure that not isomorphic. That is the whole point of the $latex n^{log_2 n} bound that is known. In permutation form it is even harder, since the groups can be huge.

      Reply
      • anonymous permalink
        November 3, 2011 2:55 pm

        Now I am very confused. I hope you’ll indulge me to see where the flaw in my logic is.

        I was under the impression that finding a strong generating set was polynomial in time in the number of generating set given. I was also under the impression that given a strong generating set, member inclusion was also polynomial time. Given two permutation groups, $G$ and $H$ given by their strong generating sets $$ and $$ respectively, one can test for member inclusion. i.e. test that every $h_k$ can be written in terms of $$ which would prove that $H \le G$. By then showing that every $g_k$ can be rewritten in terms of $$ one can then show that $G \le H$, proving isomorphism.

        Am I to understand that either there is a flaw in my above logic, finding strong generating sets is not polynomial time solvable or that member inclusion is not polynomial time solvable?

      • rjlipton permalink*
        November 3, 2011 5:50 pm

        anonymous,

        The issue is that the groups are permuting the elements with the labels 1,…,n. Each can have a different view what the labels mean. Consider two cyclic groups. One could permute 1 to 2 to … to n to 1; while the other could permute 11 to 31 to 15 to … 188 to 11. These are the same groups—both are cyclic on n elements—but they “look” very different. No? Of course for this case of cyclic it is easy, but for general groups it is really hard.

  12. mkatkov permalink
    November 22, 2011 5:08 am

    If you need crazy idea, there is one, don’t know how far one can go with it. I was looking for tables of simple groups (http://www.math.niu.edu/~beachy/aaol/grouptables1.html). One can look at all 2×2 minors ((a_1,a_2) \times (a_3,a_4) \rightarrow \approx n^4 entries) and create the structure like this: (a_1,a_2,a_3,a_4),( a_1 \circ a_3, a_1 \circ a_4, a_2 \circ a_3, a_2 \circ a_4) for both groups. Lets ignore for a moment left bracket. Right bracket encodes multiplication table up to renaming, therefore, if one can find correspondence between right brackets for 2 groups, and find consistent assignment for the left brackets the groups are isomorphic. Right brackets have different multiplicity, so one can reduce representation to the list ((a...), (a...), (a...) ), ( a_1 \circ a_3, a_1 \circ a_4, a_2 \circ a_3, a_2 \circ a_4), possibly up to local 2×2 permutations. If two groups are isomorphic 1) the multiplicities should coincide, 2) the structure of the left brackets should also coincide. Now we working with left brackets in multiplicity representation (so there is only one such line for each distinct right bracket, and looking for small groups, it seems that subgroups will be connected, and we need to look only at entries with identity elements entering twice on the right site bracket). So the connectedness of the elements in the left brackets show the structure of the group. Now one need to check the consistency of corresponding groups.

    Reply
  13. Hal Swyers permalink
    February 24, 2014 6:01 am

    I am curious as to opinion on whether the Cayley table is really the best way to represent a group. If one translates the group into a Cayley graph, and the develops the appropriate distance table, then one gets a more “dynamic” representation of the group.

    http://thefurloff.com/2014/02/23/100th-post-discrete-logs-and-cayley-graphs/

    Reply
  14. obscuremuseumsite permalink
    April 5, 2017 3:28 pm

    The paper by Fabian Wagner http://dl.acm.org/citation.cfm?id=2805607&CFID=920425961&CFTOKEN=16261980 purports to break the n^log n barrier for p-groups — Glen Whitney

    Reply

Trackbacks

  1. Bookmarks for October 8th from 15:56 to 16:16 « Mark's life
  2. Thirteenth Linkfest
  3. The Group Isomorphism Problem: A Possible Polymath Problem? « Gödel’s Lost Letter and P=NP
  4. The Lonely Runner Conjecture « Gödel’s Lost Letter and P=NP
  5. 100th Post…discrete logs and cayley graphs | The Furloff
  6. New, Old, Ancient Results | Gödel's Lost Letter and P=NP
  7. An Annoying Problem | Gödel's Lost Letter and P=NP

Leave a Reply

Discover more from Gödel's Lost Letter and P=NP

Subscribe now to keep reading and get access to the full archive.

Continue reading